Тараз мемлекеттік педагогикалық институтының хабаршысы ғылыми-педагогикалық журнал

 
174 
y= x*c mod n 
t= (r)
-1
 mod n 
есептелінеді. 
Егер  x=  r
e
  mod  n  болса,  онда  r=x 
d
  mod  n  болады.  Содан  кейін  Алисадан  у-ті 
жабық  кілтпен  жазуын  сұрайды,  осылайша  у-тің  шифрін  табады.Алисаның  у-ті 
ешқашан кӛрмегенін ұмытпаңыз.Алиса Еваға u= y
d
 mod n жібереді. Енді  Ева, t*u mod 
n= r 
-1
 y
d
 mod = r
-1
x
d
c
d
 mod n= c 
d
 mod n=m табады. 
2-сценарий:  Трент-  бұл  компьютер-нотариус.  Егер  Алиса  құжатты  рәсімдегісі 
келсе, онда ол оны трентке жібереді. Трент оны RSA-ның сандық қолымен рәсімдеп, 
тездетіп  қайтарады.  Мэллори  Тренттің  қалыпты  жағдайда  ешқашан  қол  қоймайтын 
құжатын  рәсімдегенін  қалайды.  Бұл  авторы  басқа  адам  хабарламасы  немесе  жалған 
уақытша  хабар  болсын,  бәрібір,  Трент  оған  ешқашан  қолын  қоймайды.  Оны  біз  m
r 
 
хабарлама деп атайық. Алдымен Мэллори х-тің кез-келген мәнің таңдайды және y= x
е 
mod n есептейді. е мәнін ол оңай алады- бұл Тренттің ашық  кілті. Енді  Мэллори  m= 
уm
r 
mod  n  есептейді  және  Трентке  m-ге  қол  қою  үшін  жібереді.  Трент  m
d
  mod  n 
қайтарады.Енді  Мэллори  (m
d
  mod  n)  х
-1
  mod  n  есептейді,  ол  n 
d
  mod  n  болады  және 
қолы m
r
 болады. Шындығына келгенде, Мэллори бұл есепті бірнеше тәсілмен шығара 
алады.  Мұндай  анықтаулар  жүргізудің  әлсіз  жақтары  болып,  дәрежеге  келтіру 
кезіндегі  кірудің  мультипликативті  құрылымның  сақталуы  болып  табылады.  Яғни, 
(хm) 
d
 mod n =х 
d
 m 
d
 mod n  
3-сценарий:  Ева  Алиса  оған  m
3
  –ке  қол  қойғанын  қалайды.  Ол  m
1
  және  m
2 
  екі 
хабарлама жасайды. Мұнда m
3
 =m
1
m
2 
(mod n) болады. Егер Ева Алисаға m
1
 мен m
2 
–ге 
қол  қойдыра  алса,  ол  m
3
-ті  былай  есептей  алады:  m
3
d
=(m
1
d
mod  n)(m
2 
d
mod  n).  Демек, 
RSA алгоритмін ешқашан кездейсоқ құжаттарға қол қою үшін қолданбаңыз. Әрқашан 
ең алдымен бірбағытты хэш-функцияны қолданыңыз. ISO 9796 блок форматтары бұл 
анықтаудың алдын алады. 
 
RSA криптожүйесін бұзу тәсілдері 
RSA-ны бұзудың бірнеше тәсілдері бар. Ең тиімді шабуылы: ашық кілтке сәйкес 
келетін  жабық  кілтті  анықтау.  Бұл  шабуылдаушыға  барлық  хабарламаларды  оқуға 
мүмкіндік  береді.  Мұндай  шабуылды  n  –  p  және    q-дің  жалпы  модулін  анықтау 
арқылы жүзеге асыруға болады.  p, q және  e негізінде шабуылдаушы  d   кӛрсеткішін 
оңай анықтай алады.Негізгі қиындық- n  басты кӛбейткіштерін табу. RSA  қауіпсіздігі 
кӛбейткіштерге  жіктеуге  байланысты.Жеке  кілтті  қалпына  келтіру  есебі 
кӛбейткіштерге  жіктеумен  эквивалентті  деуге  болады:  d-ны  n  кӛбейткіштерін  іздеу 
үшін  де,  керісінше  n-ды  d  кӛбейткіштерін  іздеу  үшін  пайдалануға  болады.  Есептеу 
машиналарының  дамуы  RSA  криптожүйесінің  тұрақтылығын  азайтпайды,  егер  кілт 
белгілі бір ұзындығын сақтайтын болса. 
RSA-ны  бұзудың  басқа  амалы  mod  n-нен  е  дәрежесінің  түбірлерін    анықтау 
әдістерін іздеуде. С=M
e
(mod n) болса, онда mod n-нен е дәрежесінің түбірі болып М 
хабарламасы табылады.түбірді анықтағаннан соң шифрленген хабарламаларды ашып, 
қолтаңбаны  жалған  қоюды  жабық  кілтті  анықтамай-ақ  орындауға  болады.  Мұндай 
шабуыл факторингке эквивалентті емес, алайда қазіргі уақытта  RSA-ны бұл тәсілмен 
бұзуға болатын әдістер белгілі. Алайда, ерекше жағдайда осы хабарламаларды бұзуға 
болатын  әдістер  белгілі.  Хабарламаға  жалғыз  шабуыл  -  ұсынылған  ашық  мәтінге 
шабуыл. Шабуылдаушы шифрленген мәтін арқылы бұл хабарламада белгілі бір мәтін 
бар  екендігін  жормалдап,  содан  кейін  оны  алынған  шифрленген  мәтінмен 
салыстырады.  Мұндай  шабуылды  мәтін  соңына  кездейсоқ  биттер  қосу  арқылы 
болдырмауға  болады.  Жалғыз  хабарламаның  басқа  шабуылы  егер  бірдей  М 

 
175 
хабарламасы  3  тілшіге  берілсе,  оның  әрқайсысы  ортақ  e  =  3  кӛрсеткішін 
пайдаланады.  Мұны  біле  отырып,  шабуылдаушы  ақпаратты  қағып  алып,  М 
хабарламасын  оқи  алады.  Мұндай  шабуылды  әр  шифрлеуде  кездейсоқ  биттер  қосу 
арқылы болдырмауға болады. Шифрленген мәтінге шабуылдаушы мәтін жасап, соған 
сәйкес  ашық  мәтін  алып,  жалған  жолмен  хабарлама  шифрын  анықтауға  тырысатын 
тағы да бір әдіс белгілі.  
Крипто жүйеге бағытталған шабуылдар да болады. Мұндай шабуылдар RSA-ны 
бұзатын  шабуылдар  ретінде  қарастырылмайды,  себебі,  ол  RSA-ның  әлсіздігін  емес, 
оның  алгоритмінің  әлсіздігін  білдірмейді,  мұнда  оның  таратылымының  әлсіздігі 
қарастырылынады.Мысалы,  шабуылдаушы  жабық  кілтке  иелік  ете  алады,  егер 
мәліметтер базасында қауіпсіздік ережелері дұрыс сақталмаса. 
Тұрақты сандар және олардың  RSA криптожүйесінде қолданылуы 
RSA алгоритмін сипаттайтын әдебиеттерде n модулін жасау үшін сандар жұбын 
таңдау  кезінде,  алынған  p  және  q  сандары  тұрақты  болу  керек.  Тұрақты  сандардың  
факторингтің  нақты  дәрежесін    n  кӛбейткіштеріне  жіктеу  кезінде  ерекше  қасиеті 
болады,  мысалы,  p  -  1  және  p  +  1  үлкен  еселіктерінің  болуы.  Мұндай  шаралардың 
себебі  факторингтің  кейбір  әдістері,  мысалы  Pollard  (p  –  1)  және  Pollard  (p  +  1) 
әдістері  p  -  1  және  p  +  1  болғанда  р  тек  кіші  бӛлінділерге  ғана  қатысты.  Тұрақты 
сандар  тек  жеке  шабуылдарға  шыдамды.  ANSI  X9.31  стандартында  ғана  тұрақты 
сандар  қолдану  талабы  қойылады.  Алайда,  соңғы  зерттеулер  тұрақты  сандар 
теориясының  күшін  жояды,  мысалыкӛбейткіштерге  жіктеудің    эллипстік 
қисықтарының пайда болуы. Факторингтің жаңа әдістері p және q-дің әлсіз де, мықты 
түрлерінде  де  сәтті,  сондықтан  тұрақты  сандар  таңдауы  қауіпсіздікті  арттырмайды. 
Қауіпсіздікті қамтамасыз ету үшін ұзақтау сандар қолдану қажет. 
  Кілттің ұсынылатын ұзындығы 
RSA алгоритміндегі кілт ӛлшемі n модулінің ӛлшемімен байланысты.  p және  q 
екі  саны  туындысы  модуль  болып  табылатын,  шамамен  ұзындықтары  бірдей  болу 
керек, себебі бұл жағдайда факторларын анықтау қиынға соғады. Мысалы, егер 768-
битті модуль қолдансақ, онда әр сан 384 битті болу керек.  
M = (p+q)/2 деп алайық. p < q болса, онда  0 

 м – sqrt (n) 

 (q - p)
2/8p
. 
p  =  M*(

n)
 
-
 
(m
2
)  болғандықтан,      p  мен  q  мәндерін  p  -  q  айырмасы  ӛте  аз 
болса, оңай табуға болады.  
  Модульдің  оптимальды  ӛлшемі  қауіпсіздік  талаптарымен  анықталады:  жоғары 
ӛлшемді  модуль  жоғары  қауіпсіздікпен  қамтамасыз  етеді,  бірақ  RSA  алгоритмінің 
жұмысын  баяулатады.  Модуль  ұзындығы  ең  алдымен  таңдалынады,  мұнда 
қорғалынатын  ақпарат  мәні  ескеріледі.Қорғаудың  жақсы  сараптамасы  модуль 
ұзындығымен  анықталады,  Rivest  [Riv92a]  дискреттік  логарифм    модулі  қолданады. 
RSA  –  мен  кейін  ұсынылатын  қорғау  факторинг  арқылы  талданады.  1997-жылы 
жүргізілген  бағалау  RSA    512-битті  кілті  факторингпен  1,000,000$  және  8  айда 
бұзылына  алатындығын  кӛрсетті.  Бұл  дегеніміз  512-битті  кілттердің  қауіпсіздікті 
қамтамасыз ете алмайды деген сӛз. 
Қазіргі таңда  RSA лабораториясы қарапайым есептер үшін 1024 битті кілттерді 
ұсынады,  ал  маңызды  есептер  үшін  -  2048  битті.  Жақында  орнатылған  стандарт 
бойынша кілт 1024 битті болу керек. Бағалығы аздау ақпарат 768-битті ӛлшемді бола 
алады,  себебі  мұндай  кілтті  осы  күнге  дейін  бұзбаған.  Қауіпсіздік  деңгейін  бағалау 
үшін Lenstra мен Verheul модельдерін қолдануға болады. 
 Әдетте  осы  жеке  кілттердің  жарамдылық  мерзімі  болады.  Мерзімі  ӛткен  соң 

 
176 
тұтынушы  жаңа  кілт  жасау  керек,  криптожүйелер  параметрлері  ӛзгермегендігін 
алдын-ала  тексеру  қажет.  Кілтті  алмастыру  хабарламаға  шабуылдан  қорғамайды. 
Тұтынушылар  RSA  жүйесінің  бұзылу  уақытын  ескеру  керек,  ал  мың  модульге 
массивті шабуыл ӛте қысқа мерзімді жүзеге асады. Кілтті ұзарту арқылы қауіпсіздікті 
қамтамасыз ету ашық кілт операция уақытын 4 есе, жеке кілт операция уақытын 8 есе 
арттырады.  Кілттерді  екі  еселеу  уақыты  16  есе  артады,  бірақ  сирек  кездесетін  бұл 
операция процесс ӛнімділігіне әсер етпейді. RSA криптожүйесінде кілттер сенімділігі 
DES блоктық шифр типінің ӛлшемінен жоғары, алайда RSA  кілтінің сенімділігі ӛте 
жоғары. 
 
RSA криптожүйесі үшін жай сандар жиыны 
Эвклидпен  2  мың  жыл  бұрын  дәлелденгендей  жай  сандардың  шексіз  саны  бар. 
RSA  алгоритмі  белгілі  бір  ӛлшемді  кілттермен  жұмыс  жасағандықтан,  жай  сандар 
саны  ӛте  жоғары.  Жай  сандар  туралы      теорема  бойынша  кейбір  n-нің    жай  сандар 
мӛлшері  n  =  ln(n)-ге  асимптоталық  түрде  жылжиды.    512  битті  ӛлшемді  кілттер 
ұзындығы шамамен 10
150 
болады.  Бұл ғаламшарда белгілі атомдар санынан да артық. 
Баланстан шығарылған  RSA 
RSA криптожүйеісінің модулі жӛніндегі дау жӛнді- факторизацияға шабуыл аса 
қауіпті.Осылайша,  модуль  разрядын  таңдау  тиімділік  пен  криптожүйе  арасындағы 
сәйкессіздікті тудырады.  
Шамир  (А.  Shamir)  RSA-модульды  шешудің  жаңа  әдістерін  ұсынды.  Шамир 
әдісімен  құрылған  модулі  бар  криптожүйе  «Баланстан  шығарылған    RSA»  атына  ие 
болды.  Мұндай  криптожүйеде  n  =  pq    разрядтылығы  он  есе  үлкейтілген,ал  р 
бӛліндісінің  разрядтылығы  2  есе  арттырылған.  Сәйкесінше    q  бӛліндісіне      4500 
биттен  келеді.  Бӛлінділердің  осындау  таңдауы  Шамир  бойынша  он  жылдап 
сақталынатын криптотұрақтылықты әкеледі.  
Негізгі мәселе  оның қолданылуы 1000 есе тӛмен болуында:енді бір операцияны 
бір  минутқа  кешіктіру  секунд  пенасымен  ӛлшегенде  16  минутты  құрайды.  Ал.  Ол 
дегеніміз тиімсіз.  
RSA қолдануында кілттік синхронизм орнату кезінде  в процедуре шифрленетін 
хабарламалар р модулінен аспау керек: тіпті үшӛлшемді DES шифрлеуін үш әртүрлі 
кілтке  қолданатын  болсақ  та  хабарлама  168  биттен  аспау  керек.  Осылайша, 
шифрленетін  блок  [0,р-1]  сандық  интервалында  орналасытындығын  жорамалдауға 
болады. 
RSA  тиімділігін  шифрлеу  кезінде  тиімділігн  арттыру  үшін  қолданылатын  кең 
тараған  әдіс        с  =  m
e
(mod  n)  және  ол  кіші  е  таңдауына  негізделеді.    Берілген 
бӛлінділер бойынша е 10 модуль бойынша келтіруді жүргізбейді, себебі т хабарлама 
ұзындығы   n модулінің оннан бір бӛлігін құрайды. е < 20  болғанда m
e
 разрядтылығы 
шамамен n модулінің разрядтылығынан екі есе асады. е-ні мұндай есептеуде т
e
 (mod 
n)  модулі  бойынша  келтірілмейді  және  тек  соңғы  амал  ғана  модульды  болады. 
Осылайша,  20 <  е  <  100     5000-биттік  модульде  тез  әсер  етуі 500-битті модулі бар 
дешифрлеумен  бірдей.  т  =  с
d
  (mod  n)    дешифрлеу  шартын  қарастырайық,  егер  с,  n 
және  d–500-биттік  сандар  болса.  Қалдықтар  туралы  қытайлық  теорема  бойынша  р-
ның    500-биттік модулі  үшін    т
1
=  с
d
  (mod  р)  ,  алдын-ала    р  мен  d-ны    (р-1)  модулі 
бойынша келтіру керек. Алайда, m
2
 = с
d
 (mod q)   4500-биттік модулі үшін есептеуінде  
q   9
3
 = 729 есе кӛп амалдар болуын талап етеді. 
Шамир  барлық  амалдарды  қолдану  міндетті  емес  деген  қарапайым  ой  тастады. 
Расында да, анықтама бойынша  m
1
(mod р) болады.  m ашық мәтіні   р-дан кіші, олай 

 
177 
болса    m(mod p)= т. Бұл дегеніміз т
1
= т және  т
2
–ні q модулі бойынша келтіру дәл 
сол нәтижеге алып келеді.   
Баланстан шығарылған  RSA және стандартты криптожүйелер кӛп жадты қажет 
етуі  10  есе  артады.Осы  кемшілікті  жою  үшін  бірнеше  әдістер  ұсынылды.Әртүрлі 
қосымшалар үшін еркін жадтық ӛлшемді қарастырайық. 
Дербес  компьютер  үшін  жадтың  артуы  елеулі  салдарға  әкеледі.  Алайда,    
интеллектуалды    карталар  үшін  (Smart  Card)  олардың  құны  жадына  тура 
пропорционал  болады.Оған  қоса,  кӛптеген  интеллектуалды    карталарды    512-битті 
модуль  базасына  маманданған  RSA-процессорде  қолданды.  Сол  себепті    олардың 
модулінің  артуы  негативті  реакцияға  әкеліп  соғады.  Практикалық  қосымшаларда  
интеллектуалды    карталар  қуатты  дербес  компьютерлермен  бірге  қолданылады. 
Осылайша, шифрлеу мен дешифрлеу амалдарын орындаудың технологиялық базасын 
таңдауға мүмкіндік береді.  Мысалы, дербес   компьютер алғашқы шифрленген кілтті 
генерациялай  алады  және    шифрлік  мәтін    тізбекті  интерфейс  картаның  кіруіне  р 
модулі  бойынша  беріледі.    Есептеулер  барысында      интеллектуалды    карталардың 
RSA-процессорының  512-битті  регистры  қолданады.    Бұның  тиімділігі  модульды 
ӛзгертпей  қазіргі  заманғы  интеллектуалды    карталардың  есептеу  ресурстарын 
пайдалана алуда. Тағы бір кемшілік ашық кілттер жадының 10 есе артуында. Алайда 
ашық  кілттерді  баланстан  шығарып,  бұл  мәселені  шешуге  болады.      G  арқылы 
псевдокездейсоқ  тізбектер  генераторын  белгілейік,  ол  идентификациялық  и 
ақпаратты 5000-битті ерекше кӛрсету  үшін псевдокездейсоқ t тізбектер қолданылады.   
Барлығына    G  белгілі  деп  жорамалданады.  Әр  тұтынушы    500-биттік    р  жай  санын   
генерациялайды, q — [а, a+ 2
50
]  интервалдағы жай сан ,мұнда  а ең кіші бүтін сан, ол  
t/р кіші немесе тең болады. Жай сандар ӛте кӛп болғандықтан q әрқашан да болады. 
Нәтижесінде  модуль  разрядтылығының  айырмасы    n  =  pq  және    t      550  биттен 
аспайды. Әр  и тұтынушы  ӛзінің ашық кілтінің  s =  n — t   санын жариялай алады. 
Сонда  криптожүйенің  әрбір  абоненті    5000-битті  ашық  кілтпен      G(u)+s  есептей 
алады.  Сипатталған  n  модулінің  факторизациясын  бұл  әдіс  жеңілдетпейді.Жай 
сандарды орналастыру заңы біртектіліктен ерекшеленетін болғандықтан сан біртекті 
емес орналастырылған деп саналады.  Осындай әсерлерді қалыпқа келтіру үшін  q  м 
шегінде таңдалынады, а + 2
50 
түрінде беріледі  
Баланстан  шығару  RSA  ӛнімділігін  екі  еселеу  үшін  қолданылады.  Мұнда  МА-
қолтаңбасы  үшін  р  бӛліндісі  белгісіз.  Сонымен  қатар  белгіленген  қысқа  ашық  кілт 
ұзын болып саналады.   
Гилберт (Н.Gilbert), Гупта (D. Gupta), Одлыжко (А. Odlyzko) және Квискватер (J.J 
Quisquater)  баланстан  шығарылған    RSA  хабар  алушы  мен  діберушінің  арасындағы 
қатынастың балансы орнатылғанда сәтті шабуылданады. 
и  мен    е  —      Бобтың  ашық  кілті.  Алисаның  мақсаты  —    р  мен    q  ашу.  т  >  р 
хабарламасын  шифрлейді    және    Бобқа  шифрлік  мәтін  m
e
  mod  п  жібереді.  Боб 
шифрлік мәтінді дешифрлеп,  m-ді алады.   m > р болса,  онда  m # m. Ал, енді  что 
Алиса қандай да бір жолмен т хабарламасын алды деп жорамалдайық,  сонда ол  p(m-
m)  тексере  алады.      0  <  т,  m  <  n  және    т  #  т    шектеулерін  сақтағанда  Қытайлық  
теоремадан      q  (т  —  т  шығады).  Яғни,    Алиса      р-ні  қайта  қалпына  келтіре  алады,  
егер    (m-m,n)  ЕҮОЕ-н  анықтаса.  Кейбір  жағдайларда    Боб      Алисаға  m  бере  алады.  
Қосымша мүмкіндіктер интеллектуалды  карталарда пайда болуда (Smart Card), олар 
автоматты түрде  m –ді   криптографиялық кілт есебінде бере алады. Қарсы әсер ету 
хабарламада кейбір арнайы идентификациялық тізбектің пайда болуына байланысты. 
Ал, енді мынадай түрдегі хабарламадан тұратын мысалды қарастырайық «Боб есебіне  

 
178 
101,74  долл.  Мӛлшеріндегі  қаржыны  менің    123  шотымнан        Замухрышина  қ. 
Аударуыңыз ды сұраймын.». Егер m > р, т хабарламасы  жүзеге аспайды. Егер m < р 
және  m = m,онда хабарлама қабылданып, ақша аударылады.Ақша аударымы туралы 
факт Алисаға m < р екендігін білдіреді. Мұндай  стратегия  р битін ашуға кӛмектеседі. 
Бір битті р анықтауды азайтуға болады, егер 100 дол.сомадан аз болмаса.     Алиса  р 
шекарасын  анықтай  алда  деп  есептейік,  мысалы,  6

2
k
  <  р  <  7

2
k
.  Сонда  бинарлық  
іздеу арқылы Алиса шамамен  m–ді   13

2
k–1 
есебінде анықтай алады. Алайда Алиса  р 
битін  тізбекті  жылжу  әдісі  арқылы  орындай  алады.  Әдіс  4  битті  біреуінің  құнымен 
анықтауға  мүмкіндік  береді.    Әдіс  кӛп  амалдарды  талап  ететіндігін  атап  ӛтейік. 
Жоғарыда  кӛрсетілген  шабуыл  ойластырылған  болып  кӛрінуі  мүмкін,  алайда  ол 
әртүрлі жағдайларда шынайы болып табылады.Бұл шабуыл толық баланстанған RSA-
ның компрометациясына алып келмейді, бірақ хабар алушы ешқашан дешифрленген 
хабарламаны алмайтындығына кепілдік берілу керек. 
RSA-ның жалпы модулін анықтау 
RSA-ның қолданылуы кезінде барлық тұтынушыларға бірдей n модулін таратып, 
бірақ әрқайсысына е мен d-ның әртүрлі мәндерін беру керек. Ӛкінішке  орай, бұл әдіс 
жұмыс істемейді.Бұның себебі, егер бір хабарлама қай кезде болмасын әртүрлі дәреже 
кӛрсеткіштерімен шифрленсе, және бұл екі кӛрсеткіштер сыбайлас жай сандар болса, 
онда ашық мәтін дешифрлеу кодын білмей тұрып та анықталуы мүмкін. 
m – хабарламаның ашық  мәтіні  болсын.  е
1   
және е
2
- шифрлеу  кілттері. n- жалпы 
модуль. Шифрлік мәтіндері мынадай болады: 
с
1
= m
e1
 mod n 
с
2
= m
е2 
mod n 
Криптоаналитик n, е
1
, е
2
,
 
с
1
, с
2
 біледі. Енді m-ді табу керек. е
1  
және е
2
- сыбайлас 
жай сандар, онда Эвклидтің r мен  s кеңейтілген алгоритмі бойынша  
rе
1 
+sе
2
=1 
r-ді теріс сан деп есептей отырып, с
1
-1
 кеңейтілген алгоритмін қайта пайдалануға 
болады. Содан соң: 
(с
1
-1
)
-r
 с
2
s
= m
 
mod n. 
Бұл  жүйелерді  анықтаудың  екі  әдісі  белгілі.  Біріншісі  n-ді  кӛбейткіштерге 
жіктеудің  ықтимал  әдісін  пайдаланса,  екіншісі  құпия  кілтті  есептеудің 
детерминациялық әдісін кӛбейткіштерге жіктемей-ақ есептейді. 

жүктеу/скачать 1,94 Mb.

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