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

     Мысалға, қол қапшықтың толық салмағы  – 70, салмақ қатары {1,3,6,13,27,52}. Ең үлкен  салмақ 52, 70 кем, сондықтан қол қапшыққа саламыз. 70–тен 52 алып, аламыз. Келесі салмақ 27, –ден үлкен, сондықтан 27 қол қапшыққа салмаймыз. салмағы –ден кіші, сондықан қол қапшыққа саламыз. –ден –ті алып, аламыз. Келесі салмағы –тен үлкен, сондықтан қол қапшыққа –ны салмаймыз. Бұл процесстің жалғасы де, те қол қапшыққа салынады. Қол қапшықтың толық салмағы –ге теңеседі, бұл шешімнің табылғанын хабарлайды.

     Күрт  өспейтін немесе қалыпты қол қапшықтар  қиын мәселені көрсетеді, олар үшін тез  алгоритм  табылмады. Қол қапшыққа қандай зат салу керектігін тек бір әдіспен, дұрыс шешіміне кездескенше, мүмкін болатын шешімдерді методикалық тексеру арқылы анықтауға болады. Қатарға тағы бір мүше қосатын болсақ, шешуін табуы екі есе қиындайды. Бұл қатарға бір зат қоссаң шешімін табу бір операцияға өсетін күрт өсетін қол қапшықтан қайда қалай қиын. Меркл-Хелман алгоритмі осы қасиетке негізделген. Жабық кілт күрт өсетін қол қапшық салмақ қатарының мәселесі болып табылады. Ашық кілт – бұрынғы шешімді қарапайым қол қапшықтың салмақ қатарының мәселесі. Меркл мен Хеллман модульдік ариметиканы қолдану арқылы күрт өсетін қол қапшық  мәселесін қарапайым қол қапшықтың мәселесіне айналдырды.  
 
 
 

     Жабық кілтті қолдану арқылы ашық кілтті құру

     Алгоритм  жұмысын сандар теориясына тереңдемей қарастырайық: қол қапшықтың  дұрыс тізбегін алу үшін, қол қапшықтың күрделі өсетін тізбегін алайық, мысалға {2,3,6,13,27,52} m модульі бойынша барлық мәндерін  n санына көбейтейік. Модуль мәні тізбектегі барлық сандардың қосындысынан үлкен болуы керек, мысалға 105. Көбейтінді модульмен өзара жәй сан болуы керек, мысалға, 31. Қол қапшықтың дұрыс тізбегі келесідей болады:

     2*31 mod 105=62

     3*31 mod 105=93

     6*31 mod 105=81

     13*31 mod 105=88

     27*31 mod 105=102

     52*31 mod 105=37

     Қорытынды – {62,93,81,88,102,37}

Қол қапшықтың күрделі өсу тізбегі жабық кілт болып табылады, ал дұрыс тізбектелген қол қапшық - ашық. 

     Шифрлеу

     Хатты шифрлеу үшін  ең алдымен  элемент  сандары бір ұзындықта болатын, қол қапшық ретімен блоктарға  бөлінеді. Содан кейін, бірді реттік мүшенің бар болуын, ал ноль жоқ болуын көрсетеді деп саналады.

     Мысалға, егер хат бинарлы түрде 011000110101101110 болса, шифрлеудің алдыңғы қол қапшықтың  ретін шифрлеуді келесідегідей  көрсетеді:

     Хат =011000110101101110

     011000 сәйкес 93+81=174

     110101 сәйкес 62+93+88+37=280

     101110 сәйкес 62+81+88+102=333

     Шифромәтінде 174, 280, 333 реті болады. 

     Дешифрлеу

     Берілген  хаттың заңды алушысы жабық кілтті біледі: түпкі күрделі өсетін ретті, сонымен қатар  қол қапшықтың  дұрыс ретке айналдыру үшін қолданылған  n және  m мәндерін. Алушы хатты дешифрлеу үшін алдымен (mod m) болатындай  n^-1 білуі қажет. Шифромәтіннің әр бір мәні n^-1 mod m көбейтіледі, содан кейін ашық мәтіннің мәнін алу үшін жабық кілттің көмегімен бөлінеді. Біздің мысалды күрделі өсу реті {2,3,6,13,27,52}, m 105 тең, ал n 31 тең. Шифромәтін 174, 280, 333. Бұл жағдайда n^-1 61 тең, сондықтан шифромәтін 61 mod 105 көбейтілуә керек.

       сәйкес 011000

       сәйкес 110101

       сәйкес 101110

Шифрленген ашық мәтін 011000, 110101, 101110 болып табылады. 

     Практикалық іске асыру

     Қатар күрт өсетін болмаған жағдайда да, алты элементтен тұратын қатардың қол  қапшық есебін шешу қиын емес. Ақиқат қол  қапшықтар кем дегенде 250 элементтен тұруы қажет. Күрт өсетін қатардың әрбір мүшесінің ұзындығы мөлшермен 200 бен 400 биттей, ал модуль ұзындығы 100 бен 200 бит болуы керек. Практикалық іске асыруда бұндай мәндерді алу үшін кездейсоқ қатар генераторын қолданады.

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

     Қол қапшық әдісінің қауіпсіздігі

     Қол қапшық мәселесіне негізделген криптожүйені миллион машина емес, жұп криптограф қана бұзған. Басында ашық кілттің  жалғыз биті ашылған еді. Содан кейін  Шамир белгілі бір жағдайда қол  қапшықты бұзуға болатынын көрсетті. Басқа да жетістіктер болған, бірақ жалпы жағдайда Мартин-Хеллман  жүйесін ешкім бұза алмаған еді. Ақырында, Шамир мен Циппел күрт өсетін қатар қол қапшықты қалыптыға өзгертуді қалпына келтіру үшін өзгерістің әлссіз жерін тапты.  

     Қол қапшықтың нұсқалары

     Меркл–Хеллман жүйесінің ашылуынан кейін қол қапшық негізінде көптеген жүйелер ұсынылған еді: бір неше ретті қол қапшық, Грэм –Шамир қол қапшықтары және т.б. Олардың барлығы талдау жасалып, бір криптографиялық әдістің қолдануымен бұзылған.

     Басқа алгоритмдерді қолданатын басқа идеялар ұсынылған, бірақ олар да бұзылған еді. Pieprzyk критожүйесі  аналогты жолмен бұзылған. Niemi криптожүйесі модульдік қол қапшыққа негізделген. Кейін ол да бұзылған.

     Қол қапшықтың нұсқалары қазіргі  уақытта қауіпсіз болғпнымен, Char-Rivest қол қапшық алгоритмі, «арнайы ашуға» қарамастан, қажетті есептеулер саны оның пайдасын азайтады. Powerline System нұсқасы қауіпсіз емес.

     4.3 RSA алгоритмі

 

     Евклид  пен Диофант, Ферма, Эйлер, Гаусс, Чебышев  пен Эрмит еңбектерінде  диофантты  теңдеулерді шешу жөнінде маңызды ойлар жатыр, сол заман үшін үлкен болып саналатын сандардың ең жақын мәнін табу үшін амалдар бар. Соңғы екі он жылдықта криптография мен ЭЕМ-нің кең таралуына байланысты сұраныстың дамуына орай сандар теориясының алгоритмдік сұрақтары даму үстінде. Есептеу машиналары мен электрондық құралдар адамның барлық қызметі мен ой-өрісіне енді. Оларсыз қазіргі заманғы  криптографияны елестету мүмкін емес. Мәтінді шифрлеу мен оны бұзуды ЭЕМ көмегімен бүтін сандарды өңдеу ретінде елестетуге болады, бұл амалдар орындалаиын тәсілдер кейбір функциялар секілді бүтін сандардың белгілі бір жиынында орындалады. Мұның бәрі қазіргі заманғы криптографияда сандар теориясының болуына жағдай жасайды. Сонымен қатар, кейбір криптожүйелердің тұрақтылығы тек кейбір сандық –теориялық есептер күрделілігімен негізделеді. Бірақ ЭЕМ мүмкіндігі шекті болып табылады. Ұзын сандық тізбекті белгілі бір өлшемді блоктарға бөлуге тура келеді және әр блокты бөлек шифрлеуге тура келеді. Одан әрі біз барлық шифрленетін сандарды теріс емес және берілген m санынан кіші емес деп санаймыз.Мұндай шектеулер одан әрі шифрлеуден алынатын сандарға да қатысты. Бұл осы сандарды бойынша есептеуге мүмкіндік береді. Шифрленетін функция есептеу сақинасының бір-біріне сыбайлас жүйе ретінде қарастырылынады:  

                                                                                                          (18) 

ал саны шифрленген түрдегі хабарламасын көрсетеді. Мұндай түрдің қарапайым шифры – алмастыру шифры, k-бүтін сан үшін болатын көрініске тән. Мұндай шифрды Юлий Цезарь де қолданған. Әрине, -тің әрбір көрінісі ақпаратты сақтау үшін қолданылады.

     1978-жылы  американдық Р. Ривест, А. Шамир және Л. Адлеман (R.L.Rivest. A.Shamir. L.Adleman) функциясына мысал ұсынды, олар ерекше қасиеттерге ие. Соның негізінде нақты қолданылатын шифрлеу жүйесі алынды, авторлардың есімдерінің алғашқы аттарына сәйкес RSA деп аталды. Бұл функция мынадай:

4. функциясының мәндерін есептейтін әлдеқайда жылдам әдіс бар;
5. кері функциясының мәндерін есетейтін жылдам әдіс бар;
6. функциясының «құпиясы» бар, егер оны анықтасақ, мәндерін тез есептеуге болады; қарсы жағдайда есептеуге ауыр, көп уақытты кетіретін, шешуге мүмкін емес есепке айналады.

 

     Мерклдың  қол қапшық алгоритмінен кейін көп  ұзамай алғашқы, нағыз, шифрлеу және цифрлік жазбада қолдануға болатын: RSA ашық кілтті қолданатын алгоритм пайда болды. RSA осы жылдар ішінде ұсынылған ашық кілтті қолданатын алгоритмдер ішінде ең оңай түсінуге және жүзеге асыруға болатын алгоритм. Массачусетс  Технологиялық институтында баспаға шықпас бұрын, RSA жүйесіне арналған доклад көшірмесі белгілі математик Мартин Гарднерге жіберілді, ол 1977-жылы Scientific American журналына шифрлеудің осы жүйесіне қатысты мақала жариялады. Тақырыбын аударатын болсақ, ол шифрын бұзу үшін миллиондаған жылдар қажет болатын жаңа шифр дегенді білдіреді. Дәл осы мақала RSA-ның дамып, белгілі болуына жағдай жасайды. Осы мақала криптографияға маман еместердің назарын аударуға және осы облыстың дамуына жағдай жасады, бұл соңғы 20 жылдықта болған жаңалық.

     4.4 RSA шифрлеу жүйесі

 

       және  натурал сандар болсын. RSA сұлбаның функциясының орындалуы келесідегідей құрылған: 

                                                                                     (19) 

 хатына расшифровка жасау  үшін келесі теңдікті шешу  жеткілікті болып табылады: 

      .                                                                                  (20) 

     Бұл теңдік  және кейбір шарттарында жалғыз ғана шешімі болады. Бұл шарттарды сипаттау үшін және шешімін табу жолын түсіндіру үшін бізге Эйлер функциясы деп аталатын бір теоритико-сандық функция қажет болады. Бұл функция  натуралды аргументтің деп белгіленеді және 1- ден -ге дейінгі кесіндінің бүтін сандар, өзара жәй санына теңестіріледі. Кез келген жәй саны мен натуралсаны үшін    және  тең болады. Сонымен қатар, кез келеген және натурал өзара жәй сандар үшін болады. Егер санының жәй көбейткіштерге жіктелуі белгілі болса, бұл қасиеттер мәнін оңай есептеп табуға мүмкіндік береді. Егер (2) салыстыруда көрсеткіш дәрежесі өзара жәй болса, (20) салыстырудың жалғыз ғана шешімі болады. Оны табу  үшін келесі шартты қанағаттандыратын бүтін санын анықтаймыз:

                                              

                                                                 (21) 

     Бұндай  сан бар, себебі және бұл жалғыз ғана. Бұл жерде арықарай да символымен  және  ең үлкен ортақ бөлгіші белгіленеді. Эйлердің классикалық теоремасы -мен өзара жәй әрбір саны үшін салыстырымыорындалады және осыдан қорытынды: 

                                                                                    (22) 

Яғни, жорамалында (20) салыстырылымның жалғыз шешімі келесі түрде табылады:  

      .                                                                   (23) 

     Егер  әр түрлі жәй көбейткіштерден тұратын деп қосымша жорамалдасақ болса, онда (23) салыстыру жорамалынсыз да орындала береді. Шынымен, және деп белгілейік. Онда -ге бөлінеді, ал (20) салыстыруынан екені көрінеді. (22) тәрізді тез табамыз. Онымен қатар те бар. алынған салыстыруды (23) –тен аламыз. 

     RSA  жүйесінде қабылдануында (1) функция   тез арада есептелуі мүмкін. кері функциясы , есептеудегі ережелермен анықталады, тек нің орнына  . (19) функциясын шешу үшін  бар жоғы және мәндерін білу жеьткілікті. Шифрлеу үшін осылар   ашық кілтті құрайды. Ал кері функцияны  есептеу үшін  санын білу қажет. Олар «құпия» болып табылады. Бір көзге санын табу қиын емес, тек жай көбейткіштерге жіктеп, мәні көмегімен, (21) салыстыруы көмегімен санын табу керек. Бұл есептеулердің барлық қадамдары жылдам орындалуы мүмкін, тек біріншісі емес. санын көбейткіштерге жіктей ең үлкен мәселені береді. Әрине, қажетті жіктеуді ға дейін жай сандарды таңдай отырып және оларды ға бөлу арқылы болады. Бірақ жай сандар дегеніміздің саны тең. Егер 100ондық сандармен жазғанда жай сандардың саны нен  аз түспейді. Дөрекі айтқанда секундына миллион бөлуді орындайтын компьютердің өзіне жіктеуін орындау үшін  жыл уақыт кетеді. Басқа да әдістер бар, бірақ оларда баяу жұмыс істейді.

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