лекция. Ашы кілтті криптографиялы жйелер. RSA шифрлау жйесі

· RSA шифрлау жйесі

· RSA схемасы

· RSA ол оюы.

 

RSA шифрлау жйесі. Бірінші болып жне е кп тараан ашы кілтті криптографиялы жйе 1978 жылы RSA деп аталатын жйе ретінде сынылан. RSA жйесіні атауы жйені рушыларды авторларыны бас ріптерінен алынан, олар Р. Ривеста, А. Шамира, Л. Адлеман. Ол те кп иын бтін сандарды арапайым кбейткіштерге жіктеуге негізделген. Кбейту нтижесінде шифрлау ашы кілтті элементі олданыла алады. Аымды арапайым сандар шифрды айта ашу шін олданылады, біра оны орнына айта келтіру мселесі криптоаналитиктерді шифрды бзу жмысына арсы трып келеді. Осылайша біржаты пия функцияны руа болады. Мысал ретінде авторларды шифрлау принципін крсетейік.

· Шифрлау ашы кілті: n жне e саны

· Шифрды ашу жабы кілті: p,q жне d саны

· апаратын шифрлау алгоритмі:

§

· с жабы апаратын айта ашу алгоритмі:

§

 

айта ашу алгоритмін табуды жалыз дісі, жне e сандары белгілі боланда, n cанын арапайым кбейткіштерге кбейтіп, p жне q сандарыны мнін, сонымен бірге d саныны мнін табу керек. p жне q сандарыны разрядтыын дрыс тадау есепті n факторизациясын іс-жзінде ммкін емес етеді (RSA авторлары бірінші 40-разрядтан тмен емес онды сандарды олдануды сынан). Келтірілген схема бойынша шифрлау келесі суретте крсетілген (сурет 1), мндаы е=7, d=3 жне n=33.

 
 

 


Сурет 1 - RSA схемасы бойынша шифрлау

RSA авторлары здеріні жйелеріні жмыс істеу принциптерін жазанда тмендегі сзді тадап алды:

 

ITS ALL GREEC TO ME (Мен шін мны брі тсініксіз)

 

Бл мтінді лкен сана айналдыру шін сзді арасындаы бос аралыты 0, А рпін – 1, В рпін – 2, С рпін – 3, ... , Z рпін – 26 деп кодтап алды. р символды крсету шін райсысына 5 екілік разряд блді. Нтижесінде келтірілген мтінге келесі сан те болды:

= 09201900011212000718050511002015001305.

 

Шифрлау шін авторлар e=9007 жне

n=114381625757888867669235779976146642010218296721242362562651842935706935245733897830597123563958705058989075147599290026879543541 сандарын тадап алды.

 

Шифрлааннан со

c = (mod n)=

санын алды. Кездейсо тадап алынан n саны 64 жне 65 дрежелі p жне q сандарыны кбейтіндісі. Егер мтін те лкен болан жадайда онымен бір сан ретінде жмыс жасау шін оны блоктара блу керек, р блокты жеке сан ретінде арастырып жне шифрлау барысында блоктар байланысын олдану ажет.

 

RSA схемасы. RSA [Schn 96] шифрлау шін де жне ол ою шін де олданылады.

P жнеq – лкен арапайым сандарын тадап аламыз. n = p×q модуль болсын, келесі функция

j(n) = (p-1)×(q-1) –Эйлерфункциясы.

 

Кез-келген 1£е<j(n) аламыз, ол ОБ(е, j(n)) = 1.

Онда тек ана жалыз

1£d <j(n) болады, ол ed(modj(n)) = 1 болады.

RSA шифрлау жйесі – ашы кілтті жйе, мндаы
е –ашы, ал d – пия кілттер. Егер 0£x<n – ашы апарат болса, онда шифрланан апарат келесі трде алынады:

С = х (mod n).

Шифрды ашу ммкіндігі келесі теорема бойынша аныталады:

Теорема 1.Егер p жне q – лкен арапайым сандар болса, ed(modj(n)) = 1, онда" х, 0£x<n:

(х ) (modn) = x.

Длелдеу.ОБ(х, n) =1 деп алайы. Онда

(х ) = х = x .

сондытан Эйлертеоремасы бойынша

(х ) (modn) = (х( x (modn)))(modn)= (x× 1)(modn) = x.

Егер

ОБ(х,n) ¹ 1

болса, онда

х =0(modn), немесеОБ(х,n) = p, немесеОБ(х,n) = q.

Егер

х =0(modn)

болса, онда

х =0(modn), ОБ(х,n) = p

деп аламыз.

Онда

х = х p,

мндаы (х , n) =1.

х = x = px p x ºy(modpq).

Егерmp= y(mod(pq)) болса, ондаmp = pqk + y, сйкесінше, y = py . онда
mºy (modq. Сйкесінше,

x ((pх ) ) ºy (modq).

Ферматеоремасы бойынша z º 1 (modq). Сондытан

x= x p(mod(pq)) = y (modn) ºх (modn),

теорема длелденді.

Ашы жне шифрланан мтіндер тиімді аныталынады, егер жылдам дрежеге жоарылату алгоритмі арылы ежнеd белгілі болса. Егер d пия кілтін белгілі е ашы кілті арылы іздейтін болса, онда j(n) –ді білу керек.

Теорема 2.j(n) = (p-1)( q-1) есептеу (полиномиалды крделілігіне длме-дл алгоритмге дейін) n = p×q факторизация санына тепе-те.

Дллдеу.n жнеj(n) белгілі болсын. онда p жне q жылдам табылады. Бл келесі тедеулерден байалады.

j(n) = (p-1)(q-1) = pq-p-q+1 = n-p-q+1.

Бдан

p+q= n-j(n)+1, pq = n.

Виет теоремасына кері теорема бойынша, p жне q квадратты тедеулерді тбірлері болып табылады:

х - (n -j(n)+1)x + n = 0.

Тбірлерін есептеу – полиномиалды алгоритм болып табылады. Керісінше, егер p жне q, pq = n белгілі болса, онда j(n) = (p-1)(q-1) болады. Теорема длелденді.

RSA ол оюы. М – ол оятын апарат болсын. ол оя келесі алгоритм бойынша алынады:

С = М (mod n),

онда (М, С) – ол ойылан апарат. ойылан ол келесі трде тексеріледі

С ( mod n) = М (mod n) = М’.

ЕгерМ = М’, болса, ойылан ол расталынады.

 

SWIFT ашаны халыаралы электронды аударымдар желісі, азіргі уаытта оны ызметін пайдаланатын банктік йымдардан тек осы криптографиялы жйені олдануды талап етіп отыр. Бл криптографиялы жйені алгоритмі тмендегіше:

· Жіберуші екі те лкен санды тадап алады, мысалы P жне Q. Содан кейін екі кбейтіндісін есептейді N = P * Q жне M = (P-1) * (Q-1);

· Одан со кез-келген ойдан M-ге атысты бтін D санын тадап алады да D * E = 1 mod M шартын анааттандыратын Е санын есептейді;

· Осы операциялардан кейін ол D мен N-ді ашы шифрлау кілті ретінде жариялап Е-ні жабы ретінде сатап алады;

· Егер S-апараты, оны зындыы рнек мні бойынша бтін сандармен аныталатын жне (1,N) интервалында болатын апарат N модулі бойынша D дрежесіне жоарылатылып шифрланады да, абылдап алушыа жіберіледі S’ = (SD) mod N;

· Апаратты абылдап алушы оны N модулі бойынша Е дрежесіне ктеру арылы шифрды айта ашады.

Мнда, S = (S’E) mod N = (S(D*E)) mod N

 

Осылайша ашы кілт ретінде N жне D сандар жбы болады да, пия кілт ретінде Е саны болады.Бл шифрлау жйесіні маынасы Ферма теоремасын ескерсек анытала тседі. Ол теоремада, арапайым Р саны жне кез-келген Р-дан кіші К бтін саны К(Р-1) = 1 mod P тедігі орындалады. Бл теорема андайда бір санны арапайым немесе рама екендігін анытауа ммкіндік береді.

RSA дісімен шифрлау процесін тмендегіше келтіруге болады:

· Ашы типтегі кез-келген файл болсын, яни рамында кез-келген апарат болатын мтіндік файлды тадап аламыз. Бл файл RSA дісіні алгоритмі бойынша шифрланады. Нтижесінде шифр мтінді файл рылады.

· Шифрланан мтіндік файлды бадарлама арылы крсетіп жне бл файлды RSA дісіні шифрды айта ашу алгоритмі бойынша ашамыз.

 

 

дебиеттер:

 

1. Дйсенов Н.Ж., Егенова .М., Кшкінбаева М.Ж. Компьютерлік жйелердегі апаратты орау.

2. Балапанов Е.., Брібаев Б., Дулетлов А.Б. Жаа информациялы технологиялар: информатикадан 30 саба.-Алматы:ЖТИ,2003,-408 б.

3. Байжманов М.., Жапсарбаева Л.. Информатика. Жоары оу орындарды студенттеріне арналан оу ралы. –Астана: Еуразия лтты университеті, 2004, -224 б.