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

     EXPTIME  мәселелер қатары бар. Бұл мәселелер экспоненциалды уақытта шешіледі. EXPTIME-толық мәселелер расында да детерминацияланған полиномиальды уақыт аралығында шешіле алмайтындығы дәлелденуі мүмкін. Сонымен қатар, Р EXPTIME-ге тең болмайтындығы дәлелденген.

 

      2.2 Сандар теориясы

 

     Айыру арифметикасы

     Айыру арифметикасын барлығымызға мектеп кезінен мәлім. Оны кейде «арифметикалық сағат» деп те атаған. Егер Милдред  әкесіне үйде 10:00 болам деп айтып, 13 сағатқа кешігіп қалса, онда үйіне  ол қашан келеді және неше жылға әкесі оны жүргізуші құқығынан айырады? Бұл арифметика 12 модуль бойынша. Жиырма үш 12 модулі бойынша 11 болады.

     (10+13) mod 12 = 23 mod 12 = 11 mod 12

Бұны  басқаша 23 пен 11 эквиваленттігі бойынша 12 модулімен жазуға болады:

     10+13 =11(mod 12)

Көбінесе, егер а = b+кn кейбір бүтін к үшін болса, а = b (с) болады. Егер а кері  емес болса және b 0 мен n аралығында орналасса, онда b-ны а-ның n-ға қатынасы кезіндегі қалдығы деп қарастыруға болады. Кейде b а n модулі бойынша  есептен алу деп аталады. Кейде а n модулі бойынша конгруэнтты b деп аталады. Екеуі де бір мағынаны береді.

     0-ден  n-1-ге дейінгі сандар жиыны  n модулі бойынша есептен алудың  толық жиынын құрайды. Бұл дегеніміз  кез-келген бүтін а үшін оның  қалдығы n модулі бойынша  0 мен n-1 аралығында орналасқан кез-келген сан болады.

     а mod n операциясы 0 мен n-1 аралығында орналасқан  кез-келген бүтін а-ның қалдығын білдіреді. Бұл операция модульге келтіру деп аталады. Мысалы, 5 mod 3= 2.

     Бұл mod анықтамасы бағдарламалау тілінде  көрсетілген анықтамалардан ерекшеленуі мүмкін. Мысалы, PASСAL тілінде қалдықты алу операторы кейде кері  сан шығарады. Ол -(n-1) және n-1 аралығындағы санды қайтарады. С тілінде % операторы бірінші өрнекті екіншісіне бөлуден алынған қалдықты қайтарады, ол егер операндалардың кез-келгені кері  сан болса кері  мән береді. Бұл кітаптағы барлық алгоритмдер үшін егер ол кері  санды шығарып тұрса, қалдықты алу операциясының нәтижесін алу үшін не қосатындығын тексеріңдер.

     Қалдықтар арифметикасы жай арифметикаға өте  ұқсас:ол коммутативті және дистрибутивті. Сонымен қатар, әрбір аралық нәтижені n модулі бойынша келтіру жалпы есептеудегі соңғы нәтижені n модулі бойынша келтіргендегі нәтижені береді. 

     (а+b) mod n=((а mod n)+(b mod n)) ) mod n                                             (1) 

     (а-b) mod n=((а mod n)-(b mod n)) ) mod n                                               (2) 

     (а*b) mod n=(( а mod n)*(b mod n)) ) mod n                                              (3) 

     (а*(b+с)) mod n=(((а*b) mod n)+((а*с) mod n)) mod n                              (4) 

     mod n есептеу әдетте криптографияда  көп қолданылады, себебі дискретті  логарифмдер мен mod n  квадраттық  түбірін есептеу оңай емес  мәселе болуы мүмкін. Есептен  шығару арифметикасы компьютерлерде  оңай жүзеге асады, себебі ол аралық мәндер мен нәтижелер диапазонын шектейді. n –ның к-битті есептеулеріне кез-келген қосу, алу, көбейтудің аралық нәтижелері 2 к биттен артық болмайды. Сондықтан есептеу арифметикасында дәрежеге келтіру үшін үлкен аралық нәтижелерді қолданбай орындауға болады. Кейбір санның дәрежесін басқа санның модулі бойынша есептеу көбейту мен бөлудің тізбегі болады, алайда оларды тездететін тәсілдер бар: 

     а^х mod n.                                                                                                (5) 

     Сондай  тәсілдің бірі модуль бойынша көбейтулер санын  азайтуға тырысады, екіншісі – модуль бойынша жеке есептеулерді қолдану. Операциялар дистрибутивті  болғандықтан, дәрежеге келтіруді тізбекті көбейтулер ағынын әр ретте олардың  нәтижелерін ала отырып тез орындауға болады. Қазір сіздер айырмашылықты байқамайсыңдар, бірақ ол тек 200-биттік сандарды көбейткен кезде білінеді.

     Мысалы, егер сіз а⁸ mod n есептегіңіз келсе, оны 7 рет көбейтіп, 1 рет модулі бойынша келтірудің қажеті жоқ:

     (а*а*а*а*а*а*а) mod n

Оның орнына 3 кіші көбейтулер мен 3 кіші модульге келтіруді орындаңыз:

     ((а² mod n)² mod n²) mod n

Дәл осылай,

     a¹⁶ mod n =(((а² mod n)² mod n)² mod n)² mod n

a^х есептеу, мұнда х 2-нің дәрежесі болмайды, аса қиын емес. Екілік жазба х-ті 2:25 дәрежелер қосындысы түрінде береді- бұл бинарлық 11001, сондықтан 25=24+23+20. Сондықтан

     a²⁵ mod n=(а*а²⁴) mod n=(а*а⁸*а¹⁶) ) mod n=(а*((а²)²)²)(((а²)²)²)²) mod n=(а*а(((а*а²)²)²)²) ) mod n

       Аралық нәтижелерді ойластырылған  сақтаумен  енді тек 6 есептеу  қажет:

     (((((((а²mod n)*а) ²mod n) ² mod n) ² mod n) ² mod n) ²*а) mod n

Мұндай  әдіс қосу тізбегі немесе екілік квадрат  пен көбейту әдісі деп аталады. Ол негізінде санның екілік көрінісі жататын қосудың жай және айқын  тізбегін қолданады. 

     Модуль  бойынша кері  мәндер

     Кері  мән дегеніміз не екендігі естеріңізде ме? 4-1/4 үшін кері мән, себебі 4*1/4=1. Есептеу әлемінде мәселе күрделенеді: 4*х=1(mod 7)

Бұл теңдеу х пен к анықталуына эквивалентті, 4х=7 к+1

Мұнда, х пен к –бүтін сандар. Жалпы есеп мақсаты х-ті табу, ол 

     1=(а*х) mod n                                                                                        (6) 

Бұны  былай да жазуға болады: 

     а^-1=х(mod n)                                                                                           (7) 

     Модуль  бойынша кері мәндерді есептеу оңай емес. Кейде оның шешімі болады, кейде болмайды. Мысалы, 5 санының модулі бойынша  кері мәні 14 модулі бойынша 3-ке тең. Басқа жағынан 2 санында 14 модулі бойынша кері мәні болмайды.

     Жалпы жағдайда, (7) теңдеуінде а мен n сыбайлас жай болса, тек қана 1 шешімі болады. Егер а мен n сыбайлас жай болмаса, онда (7) теңдеуінің шешімі болмайды. Егер n жай сан болса, онда 1-ден (n -1)-ге дейінгі кез-келген сан n-мен сыбайлас жай болады және n модулі бойынша дәл сондай кері мәнге ие болады. 

     Эйлер функциясы

     Кері  мәнді есептеудің басқа да әдісі  бар, алайда оны әр кезде қолдана  беруге болмайды. mod n берілген қалдықтар жиынтығы деп қалдықтардың толық жиынын жиын бөлігі және оның мүшелері n-мен сыбайлас жай болады. Мысалы, mod 12-нің келтірілген қалдықтар жиыны –{1,5,7,11}. Егер n –жай сан болса, онда mod n-нің келтірілген қалдықтар жиыны бұл- 1-ден n-1-ге дейінгі сандардың жиыны. 1-ге тең емес кез-келген сан үшін 0 саны ешқашан берілген қалдықтар жиынының құрамына кірмейді.

     Эйлер функциясын φ(n) түрінде жазады, - бұл n модулі бойынша берілген қалдықтар жиынындағы элементтер саны. Басқаша айтқанда, φ(n)- n-нен кіші және онымен сыбайлас жай сан болатын  бүтін оң сандар саны.

Егер n-жай  сан болса, онда 

     φ(n) = n-1                                                                                               (8) 

Егер мынадай теңдеу белгілі болса, 

     n =рq                                                                                                      (9) 

мұндағы р мен q-жай сандар болса, онда 

     φ(n) =(р-1)(q-1)                                                                                     (10) 

болады. Бұл сандар кейбір алгоритмдерде  ашық кілтпен келеді. Бұның себебі мынада: Эйлер теоремасы мен  Ферманың кіші теоремасын сәйкес жалпылағанда, егер ЕҮОБ(а, n )=1 болса, онда 

     а ^φ(n) mod n=1                                                                                       (11) 

Енді  а^-1 mod n есептеу қиын емес: 

     х=а ^φ(n)-1 mod n                                                                                      (12) 

     Мысалы, қандай  сан 7 модулі бойынша 5 санына кері мәнге ие болады? 7 жай сан  болғандықтан, φ(7) =7-1=6.

Осылайша 5 санына 7 модулі бойынша кері мән  мынаған тең болады:

     5^6-1 mod 7=5⁵ mod 7=3.

Бұл  кері  мәндерді есептеу тәсілін  х мәнін табудың ортақ мәселесіне кеңейтуге болады: 

     (а*х) mod n= b                                                                                      (13) 

Эйлер жалпыламасын қолдана отырып, мынаны шешеміз: 

     х= (b* а ^φ(n)-1) mod n                                                                              (14) 
 

Эвклид  алгоритмін қолдана отырып, мынаны табамыз: 

     х= (b* (а^-1 mod n)) mod n                                                                    (15) 

     Жалпы жағдайда кері мәндер алгоритмін есептегенде  Эвклид алгоритмі Эйлердің жалпыламасына қарағанда тезірек, әсіресе 500 битті сандар үшін. Егер ЕҮОБ(а, n )≠1 болса да шешімін табуға болады. Бұл жағдайда (а*х) mod n= b, не бірнеше шешімі, не бірде-бір шешімі болмайды. 

     Лежандр символы

     Лежандр символы L(а,р) егер а – кез келген бүтін сан болса, ал р-2-ден үлкен жай сан болса анықталған болады. Ол 0,1 немесе -1-ге тең болады.

     L (а, р) =0, егер а р-ға бөлінсе.

     L (а, р) =1, егер а –р модулі бойынша квадраттық есептен алу болса.

     L (а, р) =-1, егер а –р модулі бойынша квадраттық есептен алу болмаса. 

     L (а, р) = а^(р-1)/2 mod р.                                                                        (16) 

Немесе  келесі алгоритмді қолдануға болады:

1. Егер а=1 болса, онда L(а,р) =1
2. Егер а жұп болса, онда L(а,р) = L(а/2,р)*(-1)^(у2-1)/8
3. Егер а жұп болмаса, онда L(а,р) = L(р mod а,р)*(-1)^{(а-1)(р-1)/4}

 
 

     Көбейтінділерге жіктеу

     Көбейтінділерге жіктеу дегеніміз – оның жай көбейтінділерін  табу деген сөз. 

10=2*5

60=2*2*3*5

252601=41*61*101

2113-1=3391*23279*1868569*65993*1066818132868207 

Көбейтінділерге жіктеу сандар теориясының ең көне мәселесі болып табылады. Бұл процесс қиын емес, тек уақыт талап етеді. Қазіргі таңда ең күшті алгоритм болып мынау табылады:

     Сандардың сандық өрісінің торы – бұл 110 және одан да көп бөлік үшін ең  тез алгоритм болып табылады. Алғашқыда ол пайдалы болған жоқ, алайда соңғы жылдары ол жақсартылған. Ол көбейтінділерге жіктеуді өте тез орындау үшін әлі біршама жаңа, алайда жақын арада барлығы өзгереді.

     Квадраттық  тор – бұл 110 ондық бөліктен кіші сандарды көбейтінділерге жәіктеудегі ең тез әдіс. Бұл әдістің жаңартылған нұсқасы полиномиальды квадраттық тор болып табылады. Ең тез нұсқасы полиномиальды квадраттық тордың үлкен санды екілік вариациялау әдісі болып табылады.

     Эллипстік қисық әдісі – 43 бөлікті көбейтінділерді жіктеуде қолданылды.

     Монте-Карло  Поллард әдісі; Үзіліссіз  бөлшектер алгоритмі – бұл алгоритм орындалу уақытына сай келмейді. 

     Екілік  санау жүйесі