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

     3-сценарий: Ева Алиса оған m₃ –ке қол қойғанын қалайды. Ол m₁ және m₂ екі хабарлама жасайды. Мұнда m₃ =m₁m₂ (mod n) болады. Егер Ева Алисаға m₁ мен m₂ –ге қол қойдыра алса, ол m₃-ті былай есептей алады: m ₃^d=(m₁^dmod n)(m₂ ^dmod n)

     Демек, RSA алгоритмін ешқашан кездейсоқ  құжаттарға қол қою үшін қолданбаңыз. Әрқашан ең алдымен бірбағытты хэш-функцияны  қолданыңыз. ISO 9796 блок форматтары бұл анықтаудың алдын алады. 

     RSA криптожүйесін бұзу  тәсілдері

     RSA-ны  бұзудың бірнеше тәсілдері бар.  Ең тиімді шабуылы: ашық кілтке  сәйкес келетін жабық кілтті  анықтау. Бұл шабуылдаушыға барлық  хабарламаларды оқуға мүмкіндік  береді. Мұндай шабуылды n – p және  q-дің жалпы модулін анықтау арқылы жүзеге асыруға болады. p, q және  e негізінде шабуылдаушы d  көрсеткішін оңай анықтай алады.Негізгі қиындық- n  басты көбейткіштерін табу. RSA  қауіпсіздігі көбейткіштерге жіктеуге байланысты.Жеке кілтті қалпына келтіру есебі көбейткіштерге жіктеумен эквивалентті деуге болады: d-ны n көбейткіштерін іздеу үшін де, керісінше n-ды d көбейткіштерін іздеу үшін пайдалануға болады. Есептеу машиналарының дамуы RSA криптожүйесінің тұрақтылығын азайтпайды, егер кілт белгілі бір ұзындығын сақтайтын болса.

     RSA-ны  бұзудың басқа амалы mod n-нен  е дәрежесінің түбірлерін  анықтау  әдістерін іздеуде. С=M (mod n) болса, онда mod n-нен е дәрежесінің түбірі болып М хабарламасы табылады.түбірді анықтағаннан соң шифрленген хабарламаларды ашып, қолтаңбаны жалған қоюды жабық кілтті анықтамай-ақ орындауға болады. Мұндай шабуыл факторингке эквивалентті емес, алайда қазіргі уақытта  RSA-ны бұл тәсілмен бұзуға болатын әдістер белгілі. Алайда, ерекше жағдайда осы хабарламаларды бұзуға болатын әдістер белгілі. Хабарламаға жалғыз шабуыл - ұсынылған ашық мәтінге шабуыл. Шабуылдаушы шифрленген мәтін арқылы бұл хабарламада белгілі бір мәтін бар екендігін жормалдап, содан кейін оны алынған шифрленген мәтінмен салыстырады. Мұндай шабуылды мәтін соңына кездейсоқ биттер қосу арқылы болдырмауға болады. Жалғыз хабарламаның басқа шабуылы егер бірдей М хабарламасы 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) .

p = M*( ) болғандықтан,   p мен q мәндерін p - q айырмасы өте аз болса, оңай табуға болады.

Модульдің оптимальды өлшемі қауіпсіздік талаптарымен анықталады: жоғары өлшемді модуль жоғары қауіпсіздікпен қамтамасыз етеді, бірақ RSA алгоритмінің жұмысын баяулатады. Модуль ұзындығы ең алдымен таңдалынады, мұнда қорғалынатын ақпарат мәні ескеріледі.Қорғаудың жақсы сараптамасы модуль ұзындығымен анықталады, Rivest [Riv92a] дискреттік логарифм  модулі қолданады. RSA – мен кейін ұсынылатын қорғау факторинг арқылы талданады. 1997-жылы жүргізілген бағалау RSA  512-битті кілті факторингпен 1,000,000$ және 8 айда бұзылына алатындығын көрсетті. Бұл дегеніміз 512-битті кілттердің қауіпсіздікті қамтамасыз ете алмайды деген сөз.

     Қазіргі таңда  RSA лабораториясы қарапайым  есептер үшін 1024 битті кілттерді  ұсынады, ал маңызды есептер үшін - 2048 битті. Жақында орнатылған стандарт бойынша кілт 1024 битті болу керек. Бағалығы аздау ақпарат 768-битті  өлшемді бола алады, себебі мұндай кілтті осы күнге дейін бұзбаған.Қауіпсіздік деңгейін бағалау үшін Lenstra мен Verheul модельдерін қолдануға болады.

       Әдетте осы жеке кілттердің  жарамдылық мерзімі болады. Мерзімі  өткен соң тұтынушы жаңа кілт  жасау керек, криптожүйелер параметрлері  өзгермегендігін алдын-ала тексеру қажет. Кілтті алмастыру хабарламаға шабуылдан қорғамайды. Тұтынушылар RSA жүйесінің бұзылу уақытын ескеру керек,ал мың модульге массивті шабуыл өте қысқа мерзімді жүзеге асады. Кілтті ұзарту арқылы қауіпсіздікті қамтамасыз ету ашық кілт операция уақытын 4 есе, жеке кілт операция уақытын 8 есе арттырады. Кілттерді екі еселеу уақыты 16 есе артады, бірақ сирек кездесетін бұл операция процесс өнімділігіне әсер етпейді. RSA криптожүйесінде кілттер сенімділігі DES блоктық шифр типінің өлшемінен жоғары, алайда RSA  кілтінің сенімділігі өте жоғары. 

     RSA криптожүйесі үшін  жай сандар жиыны

     Эвклидпен 2 мың жыл бұрын дәлелденгендей жай сандардың шексіз саны бар. RSA алгоритмі белгілі бір өлшемді  кілттермен жұмыс жасағандықтан, жай  сандар саны өте жоғары. Жай сандар туралы   теорема бойынша кейбір n-нің  жай сандар мөлшері n = ln(n)-ге асимптоталық түрде жылжиды.  512 битті өлшемді кілттер ұзындығы шамамен 10¹⁵⁰ болады.  Бұл ғаламшарда белгілі атомдар санынан да артық. 
 
 
 
 

     Баланстан шығарылған  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-биттік модулі үшін   т₁= с^d (mod р) , алдын-ала  р мен d-ны  (р-1) модулі бойынша келтіру керек. Алайда, m₂ = с^d (mod q)   4500-биттік модулі үшін есептеуінде q   9³ = 729 есе көп амалдар болуын талап етеді.

     Шамир барлық амалдарды қолдану міндетті емес деген қарапайым ой тастады. Расында да, анықтама бойынша  m¹(mod р)болады.   m ашық мәтіні   р-дан кіші, олай болса   m (mod p)= т. Бұл дегеніміз т₁= т және  т₂ –ні q модулі бойынша келтіру дәл сол нәтижеге алып келеді. 

     Баланстан шығарылған  RSA және стандартты криптожүйелер көп жадты қажет етуі 10 есе артады.Осы кемшілікті жою үшін бірнеше әдістер ұсынылды.Әртүрлі қосымшалар үшін еркін жадтық өлшемді қарастырайық.

     Дербес  компьютер үшін жадтың артуы елеулі салдарға әкеледі. Алайда,    интеллектуалды  карталар үшін (Smart Card) олардың құны жадына тура пропорционал болады.Оған қоса, көптеген интеллектуалды  карталарды  512-битті модуль базасына маманданған RSA-процессорде қолданды. Сол себепті  олардың модулінің артуы негативті реакцияға әкеліп соғады. Практикалық қосымшаларда  интеллектуалды  карталар қуатты дербес компьютерлермен бірге қолданылады. Осылайша, шифрлеу мен дешифрлеу амалдарын орындаудың технологиялық базасын таңдауға мүмкіндік береді.  Мысалы, дербес   компьютер алғашқы шифрленген кілтті генерациялай алады және  шифрлік мәтін  тізбекті интерфейс картаның кіруіне р модулі бойынша беріледі.  Есептеулер барысында   интеллектуалды  карталардың RSA-процессорының 512-битті регистры қолданады.  Бұның тиімділігі модульды өзгертпей қазіргі заманғы интеллектуалды  карталардың есептеу ресурстарын пайдалана алуда. 

     Тағы  бір кемшілік ашық кілттер жадының 10 есе артуында. Алайда ашық кілттерді  баланстан шығарып, бұл мәселені шешуге болады.   G арқылы псевдокездейсоқ  тізбектер генераторын белгілейік, ол идентификациялық и ақпаратты 5000-битті ерекше көрсету үшін псевдокездейсоқ t тізбектер қолданылады.   Барлығына G белгілі деп жорамалданады. Әр тұтынушы  500-биттік  р жай санын   генерациялайды, q — [а, a+ 2⁵⁰]  интервалдағы жай сан ,мұнда а ең кіші бүтін сан, ол  t/р кіші немесе тең болады. Жай сандар өте көп болғандықтан q әрқашан да болады. Нәтижесінде модуль разрядтылығының айырмасы  n = pq және  t   550 биттен аспайды. Әр  и тұтынушы өзінің ашық кілтінің  s = n — t   санын жариялай алады. Сонда криптожүйенің әрбір абоненті  5000-битті ашық кілтпен   G(u)+s есептей алады. Сипатталған n модулінің факторизациясын бұл әдіс жеңілдетпейді.Жай сандарды орналастыру заңы біртектіліктен ерекшеленетін болғандықтан сан біртекті емес орналастырылған деп саналады.  Осындай әсерлерді қалыпқа келтіру үшін q  м шегінде таңдалынады, а + 2⁵⁰ түрінде беріледі

     Баланстан шығару 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 –ді   криптографиялық кілт есебінде бере алады. Қарсы әсер ету хабарламада кейбір арнайы идентификациялық тізбектің пайда болуына байланысты. 

     Ал, енді мынадай түрдегі хабарламадан тұратын мысалды қарастырайық «Боб есебіне  101,74 долл. Мөлшеріндегі қаржыны менің  123 шотымнан    Замухрышина қ. Аударуыңыз ды сұраймын.». Егер m > р, т хабарламасы жүзеге аспайды. Егер m < р және  m = m,онда хабарлама қабылданып, ақша аударылады.Ақша аударымы туралы факт Алисаға m < р екендігін білдіреді. Мұндай  стратегия  р битін ашуға көмектеседі. Бір битті р анықтауды азайтуға болады, егер 100 дол.сомадан аз болмаса.     Алиса   р шекарасын анықтай алда деп есептейік, мысалы, 6´2^k < р < 7´2^k. Сонда бинарлық  іздеу арқылы Алиса шамамен m –ді   13 ´2^k-1 есебінде анықтай алады. Алайда Алиса  р битін тізбекті жылжу әдісі арқылы орындай алады. Әдіс 4 битті біреуінің құнымен анықтауға мүмкіндік береді.  Әдіс көп амалдарды талап ететіндігін атап өтейік. Жоғарыда көрсетілген шабуыл ойластырылған болып көрінуі мүмкін, алайда ол әртүрлі жағдайларда шынайы болып табылады.Бұл шабуыл толық баланстанған RSA-ның компрометациясына алып келмейді, бірақ хабар алушы ешқашан дешифрленген хабарламаны алмайтындығына кепілдік берілу керек.