Диплом жұмысы 5В011100 «Информатика»

37 

 

 

 

 

4. Ашық кілтті криптожүйелер. RSA жүйесі 

 

4.1 Бір жақты функциялар. RSA жүйесінің құрылымы 

 

Криптография тарихындағы аса көрнекті кезең американдық математиктердің 

жұмысы  болды.Онда  ұсынылған  бір  жақты  функциялар  мен  құпия  функциялар 

ұғымдары  принципті  жаңа  құпия  жүйелер  мен  криптографиялық  міндеттер 

саласының роширенасын құру үшін негіз болды. 

Сонымен, бір жақты функция дегеніміз не? Бір жақты функция F функциясын 

атаймыз:Х-В, Ол келесі қасиеттерге ие: 

1) қолайлы уақыт үшін у=F(х) мәндерін есептеудің ыңғайлы алгоритмі; 

2) қолайлы  уақытта х=F  -1(у) (функцияны инвертирлеу  F) кері мәнді есептеу 

алгоритмі жоқ. 

К  құпия  функциясы  FC  кейбір  функциясы  деп  аталады:  Х-У,  бұл  К 

параметріне байланысты және келесі шарттарды қанағаттандырады : 

1) кез келген К және ыңғайлы алгоритмде в=FК (х); 

2) к белгісіз болғанда F к функциясын инвертирлеу алгоритмі жоқ; 

3)  к  белгілі  болған  кезде  және  fк  функциясын  инвертирлеудің  ыңғайлы 

алгоритмі. 

Құпия  бар  бір  жақты  функциялар  мен  функциялардың  бар  болуы  туралы 

мәселе  ашық  күйінде  қалатынын  атап  өткен  жөн.  Соңғы,  күрделі  математикалық 

есептерге  беймәлім,  яғни  олар  үшін  2-ші  сипатты  орындау  болжанатын 

инвертування функциялары бар). 

1978  жылы.  америкалықтар  Р.Ривест,  А.Шамир  және  Л.Аделман  ұсынды 

жүйені  шифрлау,  құрылған  негізінде  функциясы  f=хе(m  mоd).  Бұл  жүйе  бірінші 

әрпімен  өз  құрушыларының  аттары  -  RSA  деп  аталды.  F  функциясы  құпия 

функциясы болып табылады және келесі ереже бойынша кейбір х хабарына әрекет 

етеді: 

f: х-хе( mоd m), е, m (2. 2.1) 

сонда А=f(х) хабарламаны шифрлеу шешіміне түседі 

хе а(MOD m). (2. 2.2) 

Егер  в  (3.1.2)  дәрежесінің  көрсеткіші  АЖ  (m)  -  мен  өзара  қарапайым  болса, 

яғни 

(Е, ИС (m))=1, (2. 2.3) 

(2.2.2)  бірыңғай  шешім  бар.  Мұнда(m)  -  Эйлер  функциясы-М  өзара 

қарапайым 1-ден (m-1) - ге дейінгі табиғи сандардың саны. : 

(1)=1,(2. 2.4) 

38 

 

(р)=р-1, Мұнда р - қарапайым, (2. 2.5) 

 

 

 

(аb)=(а)*(b),(2. 2.6)  

Егер А және b - өзара қарапайым, сондықтан орама (рг)=рг-1 (р-1), Мұнда р-

қарапайым, R-табиғи.(2. 2.7)  

C(3.1.3-6)  біз  m  қарапайым  көбейткіштерге  ыдырауымыз  бар  болса,  (m) 

қарапайым анықталады. Бұдан әрі, d анықтаймыз, не: Е мена 1( Mod және M), 1≤d 

және мена (m) (2. 2.8)  

(E және (M) өзара болғандықтан, бұл D бар және жалғыз). Бұдан әрі, Икс (m) 

өзара  жай  Эйлер,  икс(m)  теоремасы  бойынша  x  x  x  x  (m)  икс  1  (mоd  M) 

орындалады, сондықтан а 

 

 

 

 

 

 

 

Сонымен,  (а,m)=1,  х=аd(mоd  m)  түрінде  конгруэнцияның  бірыңғай  шешімін 

(2.2.2) аламыз. 

M әр түрлі қарапайым көбейткіштердің  туындысы болған  жағдайда талап (а, 

m)=1 міндетті емес. Сондықтан RSA жасаушылары m пайдалануды ұсынды: 

m=рq, 

мұнда р, q-өте үлкен қарапайым сандар, онда сәйкес (3.1.5, 6): 

(m) = (РQ) = (р) (Q) = (р-1) (q-1), 

ал шарт (2.2.3) түрге ие болады: 

(Е, р-1)=НСД (е,q-1) = 1.(2. 2.10) 

 

 

 

 

 

Г=(е,  m)  жұбы  ашық,  яғни  барлық  пайдаланушыларға  белгілі  жүйе  кілті 

болып табылады. Кез келген адам ұйымдастырушыға (2.2.1) в(2.2.1) көрсетілген F 

функциясымен 

шифрланған 

хабарламаларды 

жібере 

алады, 

оларды 

ұйымдастырушы  жабық  кілттің  көмегімен  оқиды:  S=(d,  m),  шартты  таңдап 

алынған (2.2.8). 

Егер  қарсыласқа  ашық  сандар  мен  шифрлеу  принципі  белгілі  болса,  онда  m 

шағын  өлшемде  (мысалы,  8  разряд)  m  санының  барлық  қарапайым  бөлгіштерін 

табу жеткілікті, барлық сандарды 1-ден √м-ге дейін айырып. Дегенмен, m өсуімен 

асимптотикалық  тексеру  қажет  қарапайым  сандар  саны  2M  (ln  m)-1.  Мысалы, 

жүздеген  ондық таңбалар  жазылған  M үшін-бұл  оның бөлгіші  болуы  мүмкін  кем 

дегенде  4  *  1042  қарапайым  сандар.  Белгілі  алгоритмдердің  ең  жылдам  саны 

қарапайым  көбейткіштерге  бөлу  қолайлы  уақытта  нәтиже  бермейді  -  кем  дегенде 

бір  компьютерді  пайдалану  кезінде.  Сондықтан  RSА  жүйесіне  барлық  сәтті 

шабуылдар есептеулерді бөлу арқылы жүзеге асырылды. 

Өз  әдісін  суреттеу  үшін  RSА  жасаушылары  m  129  таңбалы  санды  алып, 

кейбір  хабарды  функциямен  (2.2.1)  шифрлады.  Алынған  криптограмма  ашық 

шифрлау  параметрлерімен  бірге  жарияланды,  бірінші,  кім  оны  шифрлейді, 

100$сыйлық  уәде  болды.  Сондай-ақ,  m  екі  қарапайым  санның  64  және  65 

таңбаларының  туындысы  болып  табылатыны  қосымша  көрсетілді,  алайда  шифр 

ашылғанға дейін 17 жыл өтті. Теориялық дайындықты есепке алмағанда, тек қана 

39 

 

талдауға 600 ерікті және 220 күн бойы жұмыс істеген 1600 компьютер тартылды. 

жүктеу/скачать 0,93 Mb.

Достарыңызбен бөлісу: