Лекция. Ашық кілтті криптографиялық жүйелер. 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’ = (S^D) 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 б.