Эллиптикалық криптография

                                                                      (24) 

тең болғаннан  кейін, 

      .                                                                         (25) 

Яғни, RSA жүйесі арқылы шифрлейтін хат алысуда  жеткілікті үлкен сан  және алынады. Олардың көбейтіндісі тең. Одан кейін саны таңдалады, ол (25) шартын қанағаттандырады. санын (24) көмегімен есептеледі және d саны (21) көмегімен есептеледі. және жарияланады, d құпия болып қалады.  

     Ривест, Шамир және Адлеман өз әдісін мысал  ретінде көрсету үшін ағылшын  сөйлемін осы әдіспен шифрлеген. Алдымен стандартты түрде (а=01, b=02, .... z=26, пробел=00) бүтін сан түрінде жазылған болатын, содан кейін (1) елестету көмегімен  

m=114381625757888867669325779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541

және  . Бұл екі сан жарияланған, сонымен қатар 64 және 65 ондық жүйесінде сәйкесінше жазылған, қосымша айтылған. Бұл сөйлемді бірінші шифрленген түрін тапқан адамға  100$ жүлде беруге ант етілген. 

, 

     Бұл оқиға тек 17 жыл өткеннен кейін  ғана, 1994 жылы D. Atkins, M. Graff, А. К. Lenstra және  Р. С. Leyland сөйлемнің шифрленген түрін айтқанда ғана біткен. және сандары тең болып шыққан. 

      ,

       

     Бұл керемет шешім алгоритмнің көбейткіштерге жіктелуінен пайда болған, ол квадраттық решета деп аталған. Есептеудің орындалуы ресурстарды қажет етті.

     RSA қауіпсіздігі үлкен сандарды  көейткіштерге жіктеу қиыншылығына  негізделген. Ашық және жабық  кілттер екі үлкен жәй сандардың (100-200 разрядты немесе оданда артық) функциялары болып табылады. Шифрамәтін және ашық кілтті қолдану арқылы ашық мәтінді қалпына келтіру екі үлкен сандар көбейткіштеріне жіктеумен балама деп шамаланады. 

                                                                              (26) 

Басқа сөзбен айтқанда, 

                                                                               (27) 

     d мен n өзара жай сандар екенін  айта кетелік.  және - бұл ашық кілттер, ал саны  - жабық.

     m хатты шифрлеу үшін алдымен  цифрлік блоктарға бөлінеді, кішісі  (екілік мәліметтерге 2 санының ең үлкен дәрежесі таңдалады, кішісі ). Яғни, егер және   - 100 разрядты жәй сандар болса, 200 разрядқа жуық болады, және әр хат блогының ұзындығы 200 разрядқа жуық болуға тиіс. Шифрленген хаты сол бұрынғы ұзындықтан  тұратын блоктан тұрады. Шифрлеу формуласы келесідегідей: 

                                                                                           (28) 

     Хатты расшифровка жасау үшін шифрленген  блогының әр қайсысын алып, есепте: 

                                                                                              (29) 

       

Бұл формула  хатты қалпына келтіреді. 

     RSA шифрлеуі 

Ашық  кілт:

n  –  p және q  екі жәй сандарының  туындысы (p және q  құпия болуы  керек)

     e  –   өзара жай сан 

Жабық кілт: 

     d  = e^-1 mod ((p-1)(q-1))                                                                        (30) 
 

Шифрлеу 

                                                                                               (31) 
 

Дешифрлеу 

                                                                                        (32) 

Дәл сол  сияқты хат d көмегімен шифрлене алады, ал кез келген таңдау е көмегімен  шифрлене алады.

     Қысқаша мысал келтірейік. Егер p=47 және q=71 болса, онда  n=pq=3337

Кілт  е ортақ көбейтіндісі болмауы  керек.

     (p-1)(q-1)=46*70=3220

-ні  -ға тең деп алайық. Бұл жағдайда

Бұл санды  есептеуде Эвклидтің кеңейтілген  алгоритмі қолданған. d құпиясына  сақтай  e және n жариялаймыз.   p және q мәндерін алып тастаймыз. Хатты шифрлеу үшін

     

Алдымен оны кішкентай блоктарға бөлеміз. Біздің жағдайымызға үш әріпті блоктар  жарайды. Хат  алты блогына бөлінеді.

     

     

     

     

     

     

Бірінші блок түрінде шифрленеді.

Келесі  блоктарға да осындай операциялар  орындалады, хаттың шифромәтіні құрылады:

     

Дешифрлеу үшін дешифрлеу кілтін қолдану арқылы алдындағы тәрізді дәрежеге шығару жасау керек.

Осыған  ұқсас хаттың қалған бөлігі қалпына  келеді.

     4.5 RSA алгоритмінің жұмыс істеу жылдамдығы

 

     RSA алгоритмінің қолтаңбасын  шифрлеу мен оны бұзуда, жасалу мен тексеру үшін де көбейтулер қатары есебінде орындалатын дәрежеге келтіру. Негізінен ашық кілтті қосымшалар үшін салыстырмалы түрде жоғары емес көрсеткішті қолданады, көбінесе әртүрлі модульды бірдей ашық кілттер қолданылады. Мұнда мәліметтерді шифрлеу шифрды бұзуға қарағанда, қолтаңбаны тексеру қол қоюға қарағанда тез жүреді. Егер k – модульдегі биттің саны болса, онда RSA үшін әдетте қолданылатын алгоритмдерді орындау үшін қолданылатын ашық кілтті пайдалану қадамы  k –ның екінші дәрежесіне пропорционал болады, жеке кілттің қадам саны k-ның үшінші дәрежесіне, кілт жасау үшін орындалатын операциялар саны – k-ның тқртінші дәрежесіне пропорционал.

     "Тез  көбейту" әдістері – мысалы, Фурьені тез түрлендіру амалдарына  негізделген (FFT – Fast Fourier Transform) – аз қадам санымен орындалады; бағдарламалық қамтамсыздандыруының күрделілігіне байланысты кең қолданылады, сондықтан кілттерінің қалыпты өлшемдерімен олар баяу жұмыс істейді.Алайда RSA–ны қолданатын алгоритм құралдарының тиімділігі мен өнімділігі тез артады.

     RSA алгоритмі DES-ке және басқа  блоқтық шифрларға қарағанда  баяу.  DES-тің бағдарламалық қолданылуы  аз дегенде  100 есе және  1,000 - 10,000 –аппараттық қолданылады. Жүргізілініп  жатқан істерге байланысты RSA алгоритмдерінің, сонымен қатар басқа блоктық шифрлар жұмысы тездетіледі. 
 

3-кесте.  Биттік ашық кілтпен қолданатын  әр түрлі модуль ұзындықтарына  арналған RSA жылдамдығы

     4.6 RSA қауіпсіздігі

 

     RSA қауіпсіздігі толығымен үлкен  сандарды көбейткіштерге жіктеу  мәселесіне байланысты. Техникалық  тұрғыдан бұл анықтама жалған  болып келеді. RSA қауіпсіздігі үлкен  сандарды көбейткіштерге жіктеуге байланысты деп айтылады. Математикалық тұрғыдан m бойынша  c-ні және е-ні қайта қалпына келтіру үшін n-ді көбейткіштерге жіктеу керек екендігі әлі дәлелденген емес. RSA криптоанализінің басқа әдісі ашылу мүмкін. Алайда, егер бұл жаңа әдіс криптоаналитикке d-ні табудың жолын ашса, онда ол үлкен сандарды көбейткіштерге жіктеуге мүмкіндік береді.

     RSA-ны ( p-1)( q-1) мәндерін анықтау арқылы  табуға болады. Бұл әдіс үлкен  сандарды көбейткіштерге жіктеу  әдісіне қарағанда әлдеқайда  жеңіл. Алайда,  RSA-ның кейбір  нұсқалары үлкен сандарды көбейткіштерге жіктеу әдісі тәрізді қиын. Анықтаудың ең тиімді жолы – сандарды n көбейткіштерге жіктеу әдісі. Кез-келген қарсылас е ашық кілтін және n модулін ала алады. d дешифрлеу кілтін табу үшін оны n көбейткіштерге жіктеу керек. Қазіргі таңда бұл технологияның алдыңғысы болып 129 ондық саннан тұратын сан болып табылады. Олай болса, n бұл мәннен артық болу керек.

     Әрине, криптоаналитик барлық мүмкін d-ларды  дұрыс мән іздеп тапқанша қарастыра  алады. Бұл әдіс n көбейткіштерге жіктеуге қарағанда әлдеқайда күрделі және тиімсіз. Уақыт өте келе RSA-ны анықтаудың тиімді жолы табылуда деген хабарлар шығып жатыр, бірақ бұлардың осы күнге дейін ешқайсысы да дәлелдене қойған жоқ. Мысалы, 1993 жылы Вильям Пейннің мақаласында Ферманың кіші теоремасына негізделген әдіс ұсынылды. Өкінішке орай, бұл әдіс  көбейткіштерге жіктеу әдісіне қарағанда ұзақ болып шықты.

     Сонымен қатар, р және q  жай сандарын көптеген жалпы қабылданған есептеу алгоритмдерінің  көбісі ықтимал болып келеді, ал егер олар құрама сан болса қалай есептеледі? Біріншіден, бұл оқиғаның болу ықтималын қажетті минимумге төмендетуге болады. Оған қоса, шифрлеу мен дешифрлеу жұмыс істемейтіндігі анықталып отыр. Жай сандарды іздеудің ықтимал алгоритмдері анықтай алмайтын Кармайкл сандары деп аталатын сандар қатары белгілі. Олар қауіпсіз емес және сирек кездеседі. 

     RSA қарсы шифромәтіннің  таңдалуымен ашу

     Кейбір  анықтаулар RSA-ның таратылуына қарсы  жұмыс жасайды. Олар оның базалық  алгоритмін емес, ал онымен өңделген протоколды бұзады. RSA-ны қолданудың өзі қауіпті екендігін білген жөн. 

     1-сценарий: Алисаның әңгімелесу линиясын  ақырын тыңдай алған Ева Алисаның  ашық кілтпен RSA арқылы  шифрленген  с хабарламаны ала алды. Ева  хабарламаны оқығысы келеді. Математика  тілінде оған m=c ^d анықтау үшін m-ді табу керек. m-ді анықтау үшін ол n-нен кіші кез-келген  r санын таңдайды.Ол Алисаның ашық е кілтін алады. Содан кейін

     x= r^e mod n

     y= x c mod n

     t= c 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^-1x^dc^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