Кестені жаласы
Кіріспе
Курсты жмысты масаты - крипографиялы діспен телекоммуникациялы жйелердегі апараттарды орау жйесін математикалы негіз арылы трызуды студенттерге таныстыру. Курсты жмыс мліметтерді орауды жзеге асыруды дістері мен принциптері туралы студенттерді жйеленген ойыны алыптасуына баытталан.
Курсты жмыс жабы кілтпен шифрлеу жйесін оытуа арналан. №1 тапсырма жабы кілтпен шифрлеуге арналан. RSA алгоритмдері арастырылады, сонымен атар хеш-функциялы олдануы бар электронды олтабалар бойынша есептеулер сынылады.
№2 тапсырма ассиметриялы шифрлеуге немесе ашы кілт арылы шифлеуге арналан. Дифи –Хелман, Шамир, Эль-Гамаль алгоритмдері арастырылады..
Тапсырма
1.1 Тапсырма
Симметриялы емес шифрлеу –дешифрлеу.
Келесі таратуа арналан апаратты RSA дісі арылы шифлеу керек.
пия кілтті екі нсамен, сынылан діспен жне кеейтілген Эвклид алгоритмімен генерирлеу керек.
Тапсырманы нсасы студенттік билетті соы сандарымен аныталады. I нмері арылы (соы саннын алдындаы сан) студент шифлеу шін хабарды тадайды,ал j –бойынша осы алгоритмні жзеге асуына керек р жне q сандарын тадайды.
Кесте -Бастапы мліметтер
| i | |||||
| Хабар | Принтер | Интеграл | Минус | Модуль | Плюс |
| j | |||||
| p q | 7.11 | 5.17 | 3.11 | 11.19 | 13.17 |
Кестені жаласы
| i | |||||
| Хабар | Число | Дробь | Корень | Остаток | Степень |
| j | |||||
| p q | 7.17 | 5.11 | 7.13 | 11.17 | 5.13 |
Тапсырманы орындауа арналан дістемелік нсаулар
RSA алгоритмі олданылатын, ашы кілтпен шифлеу дісі - симметриялы емес шифрлеу-дешифлеу дістеріні е ке тараан трі болып табылады.
ртрлі АКЖ-ні (ашы кілт жйесі) саны кп боланына арамастан, 1977 жылы растырылан жне зіні растырушыларыны Рона Ривест, Ади Шамир жне Леонард Эйдельман есімдерімен аталан RSA криптожйесі, лдеайда ке олданыса ие.
Олар санау жадайында жай лкен сандарды табу оай жзеге асатындыын олданды, біра осындай екі санны нтижесін кбеіткішке жіктеу практикада ммкін емес. RSA шифріні ашылуы осындай жіктеуге эквивалентті екендігі длелденген (теорема Рабина). Сондытан шифрді ашу шін кез келген кілт зындыына тмен баалы операциялар санын беруге болады, жне азіргі компьютерлерді німділігін ескере отырып, оан кететін уаытты да баалау керек.
Баса он шаты АКЖ слбаларыны асында RSA алгоритміні оралуын баалауына кепілдік беруі, оны ататы болу себептеріні бірі. Сондытан RSA алгоритмі банктік компьютерлік желілерде, сіресе жойылан клиенттермен (кредиттік карталара ызмет крсету) жмыс істеу шін олданылады.
Осы алгоритмні негізіне ойылан математикалы нтижелерді арастырайы.
1 Теорема. (Ферманы кіші теоремасы.)
Егер р – жай сан,онда
xp-1 = 1(mod p) (1)
р-а атысты жай сан болатын ,кез келген х шін жне
xp = x(mod p) (2)
кез келген х шін.
Длелдеу. xp шін (1) жне (2) тедеулеріні ділеттілігін длелдеу жеткілікті. Длелдеуді индукция дісімен жргіземіз.
(3) тедеу х=0 жне 1 боланда орындалатындыы аны.Ары арай
xp = (x –1 + 1)p = C(p,j)(x –1)j = (x –1)p + 1(mod 2),
0<j<р боланда C(р,j)=0(mod р). Осы тесіздікті ескере отырып жне длелдеу дісіні сыныстарымен индукция теоремасы длелденді.
Анытама. Эйлер функциясы (n) деп теріс емес бтін,кіші n жне n ге атысты жай сандарды айтамыз.
1.2 Кесте – Бастапы мліметтер:
| n | |||||||||||
| (n) |
2 Теоремасы. Егер n = рq, (р жне q – бір біріне атысты жай сандар),онда
(n)=(р-1)(q-1)
3 Теорема. Егер n = рq, (жне q – бір біріне атысты жай сандар) жне х –р жне q атысты жай сан, онда
x(n) = 1(mod n)
Салдар. Егер n = рq, (жне q – бір біріне атысты жай сандар) жне е (n)-ге атысты жай сан, онда рнек
Eв,n : xxв(mod n)
Zn-ге атысты зара бірмнді болып табылады .
Егер е саны f(n) санына атысты жай сан болса,онда келесі рнекке те болатын, бтін d саныныны бары аны,
ed 1 (mod (n)) (3)
RSA ататы алгоритмі осы математикалы фактілерге негізделген.
n = рq те болсын, мндаы р жне q – ртрлі жай сандар.Егер e жне d онда Еe,n жне Еd,n рнектері Zn-ге инверсті болып келеді. Егер e, d, р, q сандары белгілі болса, Еd,n рнегі Еe,n сияты оай есептеледі.
Егер e жне n сандары белгілі болып, біра р жне q сандары белгісіз болса,онда Еe,n біржаты функция болады; Еd,n-ды берілген n бойынша табу, n жіктегенге те болады . Егер р жне q – жеткілікті трде лкен жай сандар болса,онда n-ді жіктеу ммкін емес. Осы RSA шифрлеу жйесіні негізіне ойылан.
RSA шифржйесі
азіргі кезде е ке таралан ашы кілтпен шифлеу жйесі ,RSA жйесі болып табылады.
n = pq – p, q екі лкен санны туындысы трінде сынылатын бтін сан болсын. Алгоритмні шифленуі мен шифрді ажыратуын анытайтын e жне d сандары сйкесінше,келесі шарта жауап беруі керек
ed (mod (n)), (1)
мндаы (n) = (p-1)(q-1) – n санына атысты Эйлера функциясыны мні. k = (n,p,q,e,d) – k1 = (n,e) ашы кілтінен жне пия k2 = (n,p,q,d) кілтінен тратын, тадап алынан кілт болсын. M – ашы мтінні блогы болып жне C –шифрленген мтін блогына сйкес келетін болсын.Сонда шифлеу жне шифрді ажырату ережелері келесі формулалармен аныталады:
С = Ek (M) =Me (mod n), Dk(C) = Cd (mod n) (2)
(2) формуланы Dk(C) = M рнегімен сйкес екендігін ескереміз.
(1) шартты анааттандыратын, e жне d мндерін табу кезінде, е санын (n) санымен зара жай болатындай етіп тадайды, ал d-ны мнін келесі тедеуден анытайды
(n)x + ed = 1 (3)
Жалпы жадайда (3) тедеу ax + by = c тріне сйкес келеді (мндаы a = (n), b = e, y = d) жне ол Диафантты тедеу деп аталады.
Ол тедеуді шешімі
y = (–1) · a-1 · x = (–1)+1 · b -1 (4)
a/b атынасын тізбекті блшек трінде жіктеу кмегімен алуа болады:
мндаы – тізбекті блшекті реті,яни алдыы нлге болатын, блшек коэффициентіні индексі,
(5)
шіншіден бастап алан мшелеріні барлыына келесі тедіктер орындалады
(6)
Осылай (3) тедеуді шешу шін a/b атынасын блшекті тізбек ретінде сынып, r0, r1…r жне . мндерін анытау керек. Содан кейін (4) – (6) тедіктерді сйкес болуы арылы ai, bi мндері, сонымен атар x жне y мндері аныталады.
Мысал
p = 17, q = 31 олдана отырып, RSA аббревиатурасын шифлейік.Ол шін n = pq = 527 жне (n) = (p-1)(q-1) = 480 мндерін есептейік. e саны ретінде, (n) санымен зара жай болып келетін санды тадаймыз,мселен, e = 7. (n)x + ey = 1 атынасын анааттандыратын,блшек тізбегі арылы бтін x жне y сандарын табамыз. 480x + 7y = 1 трінде жазамыз
сйкесінше,
= 3, a0 = 68, b0 = 1, a1 = 69, a2 = 1·69 + 68 = 137, b2 = 1·1 + 1 = 2.
осылай, x = –2, y = –137.
–137 (mod 480) = 343 те боландытан, онда d = 343.
тексеру
7 · 343 = 2401 = 1(mod 480).
Енді берілген хабарды 0…526 интервалында ралатын сандарды тізбегі ретінде сынамыз.Ол шін R, S жне A ріптерін бестік екілік векторлармен, яни оларды алфавиттегі реттік номерлеріні екілік жазбасын олданып,кодтаймыз:
R = 18 = (10010), S = 19 (10011), A = 1 (00001).
Сонда RSA = (100101001100001). 0…526 берілген интервалында жіктеліп, келесі кріністі аламыз:
RSA = (100101001), (100001) = (M1 = 297, M2 = 33).
Содан кейін M1 жне M2 мндерін шифлейміз:
C1 = Ek (M1) = M1в = 2977 (mod 527) = 474
Мнда біз мына тедікті олданды 
Нтижесінде шифромтінді аламыз: С1 = 474, С2 = 407.
Шифрді ажырату кезінде келесі рекеттерді тізбегін орындау керек. Біріншіден, есептеу керек
343 = 256 + 64 + 16 + 4 + 2 + 1 есептеуіне араанда дрежеге шыарып олдану ыайлы екенін ескереміз. Осы айтыланны негізінде келесі рнектерді аламыз :
Осыан сйкес
Жне сол сияты
ріптік жазуа айта оралып, RSA айта шифлеуінен кейін аламыз.
2.2.т. Шамир алгоритмінде толы суреттелген, Эвклид кеейтілген алгоритмін олдана отырып, жабы кілтті генерациясын жргізу керек.
1.2 Тапсырма
1.2 Хештау жне жаттарды санды олтабасы.
1.1 тапсырмасыны мліметтерін олдана отырып, МККТТ Х.509 сынысынан алынан Н хеш – функциясыны кмегімен М хабарламасы шін m хеш – кодын есептеу. Н0 инициализациялау векторын нлге те деп алу.
Есептелген m хеш – коды мен пия кілт d-ны олданып, М электронды жатыны астындаы санды олтабаны RSA дісімен анытау.
Санды олтабаны слбасын жмыс істеуіні толы сипаттамасымен келтіру ажет.
МККТТ Х.509 хеш – функциясын келесі трде жазамыз:
Hi=[(Hi-1 Å Mi)2] (mod n), мнда i=l,n, H0 – инициализациялау векторы, Мi =М1,М2,М3…,Мn - блок зындыы.
Барлы блоктарды ортасынан бледі де рбір жартыа те бірлерді саны осылады. Осылайша трленген блоктармен интеграциялы амалдар орындалады.
p=3, q=11 параметрлері бар Х.509 хеш – функциясыны кмегімен ПРЕДЕЛ хабарламасыны хеш – кодын алу.
Хеш-кодты анытау реті:
а) n=pq= 3*11=33 модуліні мнін есептеу;
б)Хабарды орыс ліпбиіні рітеріні саны ретінде онды жне екілік трлерде келтіру:
П Р Е Д Е Л
16 17 6 5 6 12
00010000, 00010001, 00000110, 00000101, 00000110, 00001100:
в) Байтты ортасынан бліп, жартыбайтты басына бірлерді осу жне Мi хешталатын блоктарын алу:
1№3 Кесте-Бастапы мліметтер:
| M1 | M2 | M3 | M4 | M5 | M6 |
| M7 | M8 | M9 | M10 | M11 | M12 |
г) Интеративті адамдарды орындау:
Бірінші интерация
| М1 | |
| Å | |
| Н0=0 | |
| Н0 Å М1 | 11110001=24110 |
| [(H0Å M1)2] (mod 33) | 2412 mod 33 = 10 |
| Н1 | 1010=00001010 |
Екінші интерация
| М2 | |
| Å | |
| Н1 | |
| Н1 Å М2 | 11111010=25010 |
| [(H1Å M2)2] (mod 33) | 2502 mod 33 = 19 |
| Н1 |
шінші интерация
| М3 | |
| Å | |
| Н2 | |
| Н2 Å М3 | 11100010=22610 |
| [(H2Å M3)2] (mod 33) | 2262 mod 33 = 28 |
| Н3 |
Тртінші интерация
| М4 | |
| Å | |
| Н3 | |
| Н3 Å М4 | 11101101=23710 |
| [(H3Å M4)2] (mod 33) | 2372 mod 33 = 6 |
| Н4 |
Бесінші интерация
| М5 | |
| Å | |
| Н4 | |
| Н4 Å М5 | 11110110=24610 |
| [(H4Å M5)2] (mod 33) | 2462 mod 33 = 15 |
| Н5 |
Алтыншы интерация
| М6 | |
| Å | |
| Н5 | |
| Н5 Å М6 | 11111001=24910 |
| [(H5Å M6)2] (mod 33) | 2492 mod 33 =18 |
| Н6 |
Жетінші интерация
| М7 | |
| Å | |
| Н6 | |
| Н6 Å М7 | 11100010 = 22610 |
| [(H6Å M7)2] (mod 33) | 2262 mod 33 = 28 |
| Н7 |
Сегізінші интерация
| М8 | |
| Å | |
| Н7 | |
| Н7 Å М8 | 11101001= 233 |
| [(H7Å M8)2] (mod 33) | 2332 mod 33 = 2 |
| Н8 |
Тоызыншы интерация
| М9 | |
| Å | |
| Н8 | |
| Н8 Å М9 | 11110010 = 24210 |
| [(H8Å M9)2] (mod 33) | 2422 mod 33 = 11 |
| Н9 |
Оныншы интерация
| М10 | |
| Å | |
| Н9 | |
| Н9 Å М10 | 11111101 = 253 |
| [(H9Å M10)2] (mod 33) | 2532 mod 33 = 22 |
| Н10 |
Он бірінші интерация
| М11 | |
| Å | |
| Н10 | |
| Н10 Å М11 | 11100110 =23010 |
| [(H10ÅM11)2] (mod 33) | 2302 mod 33 = 32 |
| Н11 |
Он екінші интерация
| М12 | |
| Å | |
| Н11 | |
| Н11 Å М12 | 11011100 = 22010 |
| [(H11ÅM12)2] (mod 33) | 2202 mod 33 = 22 |
| Н12 |
Осылайша, бастапы ПРЕДЕЛ хабарламасы m=22 хеш-кодына ие.
Санды олтабаны есептеу шін келесі формуланы олданамыз:
S=md (mod n) = 223 mod 33 = 22
(M, S) жбы абылдаушыа S санды олтабасы ойылан М электронды жаты ретінде жіберіледі, мндаы олтаба S пия кілт d-ны иесімен жасалан.
(M, S) жбын алан со абылдаушы М хабарыны хеш-кодын екі діспен анытайды:
1) m’ хеш – кодын е ашы кілті кмегімен S олтабасыны криптографиялы трлендірілуін олданып алпына келтіреді:
m’=Se (mod n) =227 mod 33 = 22
2) Сол хеш – функцияны кмегімен абылданан хабарды хешталу нтижесін табады: m=H(M) =22.
Есептелген m’ жне m мндері те болса, онда абылдаушы (M, S) жбын тпнса деп мойындайды.
Баылау сратары
1. Ашы кілтті шифрлеу жйесін олданатын пия байланысты йымдастыруды принципиалды слбасын суреттеіз.
2. Санды олтабамен расталан жаттармен алмасуды йымдастыруды принципиалды слбасын суреттеіз.
3. жаттарды санды олтабасын есептеу кезінде жарамды хеш-функциялара ойылатын негізгі талаптарды атап тііз.
4. Тпнсалылыы санды олтабамен расталан шифрленген хабарларды RSA криптожйесі арылы таратуды алайша йымдастыруа болады? Мысалдар келтірііз.
Тапсырма
2.1 Тапсырма
Ашы кілтті Диффи-Хеллман жйесі
Диффи-Хеллман (DH) дісімен бес абонент шін пия кілттерді генерациялаыз. Ол шін 1 кестеден пия кілтті х мнін алыыз. Ашы кілтті сйкес мндерін анытаыз жне нтижелерді кестеге енгізііз. Тапсырманы нсасы i (соысыны алдындаы сан) жне j (сына кітапшасыны соы саны) нмірлері – бл алгоритмді іске асыру шін х саны. j саны – х санын тадаудаы екінші абонент шін бастапы нмір. Бес абонентпен байланысу шін х-ті сына кітапшасыны соы санымен циклдік процедура бойынша тадаймыз. Мысалы, сына кітапшасындаы сандар (15). Бірінші абонент шін x=11 тадаймыз, себебі i =1. Екінші абонент шін екінші сан бойынша x =29, себебі j= 5. шіншісі шін (j +1)=i формуласы бойынша x= 31 аламыз, себебі j =6. Тртіншісі шін x = 37, j =7. Бесіншіге x = 39 тадаймыз, йткені j=8. Мысалы, егер соы сан (27) бестен лкен - j =7 болсын. Онда x = 31,37, 39,41, 7 тадаймыз.
сынылатын мндер p = 30803, g = 2.
2.1 Кесте - Бастапы мліметтер:
| I | |||||
| x |
| I | |||||
| x |
Тапсырманы орындауа арналан дістемелік нсаулар
Ашы кілтті бірінші жйе —Диффи-Хеллман жйесі.
Бл криптожйені 70-жылдарды ортасында американды алымдар Диффи (Whitfield Diffie) жне Хеллман (Martin Hell-man) ашты жне криптография мен оны практикалы олданылуында наыз революцияа келді. Бл оралан арналар бойынша таратылатын пия кілттерді олданбай-а апаратты орауа ммкіндік берген бірінші жйе. Мндай жйелерді олданатын слбаларды бірін крсету шін N олданушысы бар байланыс желісін арастырайы, мндаы N-лкен сан. Оларды рбір жбы шін пия байланысты йымдастырымыз келеді делік. Егер біз пия кілттерді лестіруді арапайым жйесін оладанатын болса, онда абоненттерді р жбы зіні пия кілтімен амтамасыз етілуі керек, яни барлыы 
кілт ажет болады.
Егер абоненттер 100 болса, онда 5000 кілт, егер 104 абонент болса, онда 5*107 кілт ажет болады. Кріп транымыздай, абоненттерді саны кп боланда, оларды пия кілттермен амтамасыз ету жйесі те лкен жне ымбата тседі.
Диффи жне Хеллман бл мселені кілттерді ашы тарату жне есептеу арылы шешті. Енді олар сынан жйені суреттейік.
А,В,С,... абонеттері шін байланыс жйесі рылсын. рбір абонентті зіні пия жне ашы апараты бар. Бл жйені йымдастыру шін лкен жай сан р жне {1, 2, ,р — 1} атарындаы сандар g mod p – ны ртрлі држесінде келтірілетін лдебір g саны тадалады, 1 < g < р-1 (g-ны табуды р трлі тсілдері бар, соларды бірі тменде крсетіледі). р мен g сандары барлы абоненттерге белгілі.
Абоненттер пияда саталатын Xa,Xb,Xc лкен сандарын тадайды (детте мндай тадауды кездейсо сандар бергішін олданып, кездейсо жасау сынылады). рбір абонент баса абоненттерге ашы таратылатын сйкес санын анытайды,
YА = gXa mod р ,
YB = gXb mod р.. (1)
Yс = gXc mod р.
Нтижесінде келесі кестені аламыз.
2.2 Кесте- Диффи-Хеллман жйесіндегі абонеттерді кілттері
| Абонент | Секретное число | Открытый ключ | Закрытый ключ |
| A B C | XA XB XC | YA YB YC | ZAB, ZAC ZBA, ZBC ZCA, ZCB |
А абоненті В абонентімен байланыс сеансын йымдастыруды шешті делік жне екеуіне де 2 –кестедегі мліметтер белгілі. А абоненті В – а ашы арнамен хабар жіберетіндігін хабарлайды. Кейін А келесі мнді есептейді
ZAB = (YB)ХА modp (2)
А-дан баса ешкім мны істей алмады, себебі ХА саны пия.
з кезегінде В абоненті
ZBA = (YA)XBmodp (3)
мнін табады.
1-суретте Диффи-Хеллман жйесіндегі кілттерді алмасу слбасы крсетілген.
Енді жоарыда айтылан р санын тадау есебіне тоталайы. Егер g еркін тадалатын болса, онда бл есеп g – 1 санын жай сандара жіктеумен байланысты иын есеп болуы ммкін. Мселен, арастырылан жйені жоары тратылыын амтамасыз ету шін g - 1 санында міндетті трде жай лкен кбейткіш болуы керек. Сондытан келесі дісті олдану жиі сынылады.
р=2q+1 (мндаы q- жай сан)
тедігі орындалатындай р саны тадалады жне
1 < g < р - 1 и gq mod р 
1
тесіздігі анааттандырылуы ажет.
Жйе криптоанализге траты болуы шін р санын те лкен етп тадау ажет.
1 Сурет - Диффи-Хеллман жйесіндегі кілттермен алмасу слбасы
Мысал
g = 43 болсын. р параметрін тадайы. q=17 401 алып крейік.
Сйкесінше р=2*17 401+1=34 803. Тексерейік: 4317401 mod 34 803 = 17 746. ажет шарттар орындалады, яни мндай р келеді. Сонымен, біз мы р = 34 803, g = 43 параметрлерін тадады. Енді рбір абонент пия санды тадайды жне оан сйкес ашы санды есептейді. ХA = 7, ХB = 13 тадалсын. YA = 437 mod 34 803 = 11 689, YB = 4313 mod 34 803 = 14 479 анытаймыз. А мен В орта пия кілтті жасаылары келсін делік. Ол шін А ZAB = 144797 mod 34 803=6 415, ал В ZBA = 11 68913 mod 34 803 = 6 415 есептейді . Енді олар арнамен жіберілмеген 6 415 орта кілтіне.
Баылау сратары
1. Жабы кілтті баса алгоритмдерді алдында Диффи-Хеллман жйесі андай артышылытара ие?
2. Диффи-Хеллман жйесіне ысаша сипаттама берііз.
3. пия кілттерді есептеуде ажетті р санын неліктен лкен етіп тадау ажеттілігін тсіндірііз?
2.2 Тапсырма
Шамир алгоритмі бойынша шифрлеу
3-кестеден m хабарыны жне р-ны мндерін алып, ш абонент шін Шамир алгоритмі бойынша хабарды шифрлеу. і нмірі бойынша (соысыны алдындаы сан) студент шифрленетін хабарды, j бойынша – осы алгоритмді іске асыруа арналан р санын тадайды. Баса абоненттер шін мліметтерді (I + 1) жне (G + 1) процедурасына сйкес циклді жргізу. Мысалы, сына кітапшасыны соы сандары - (26). ш абонент шін (хабар,р) - (16,49), (18,51), (20,53)тадаймыз.
Кесте 3 – Бастапы мліметтер:
| I | |||||
| Хабар | |||||
| G | |||||
| p |
| I | |||||
| Хабар | |||||
| G | |||||
| p |
№2.2 тапсырманы орындауа арналан дістемелік нсаулар
Шамир (Adi Shamir) сынан бл шифр оралан арналары жне пия кілттері жо, рі, ммкін, ешашан бірін-бірі крмеген адамдара, ашы байланыс желісі бойынша пия хабарларды алмасуды йымдастыруа ммкіндік беретін болды. (Естеріізхге сала кетейік, Диффи-Хеллман жйесі тек пия сзді жасауа ммкіндік береді, ал хабарды тарату шін ол кілт болып олданылатын баса шифрді олдануды ажет етеді).
Жйені сипаттауа телік. А жне В абоненттері байланыс желісі арылы байланыссын. А абонентті В абонентіне ешандай баса абонент мазмнын білмейтіндей етіп, m хабарды бергісі келеді. А кездейсо лкен жай сан р тадайды жне оны В а ашы трде береді. Содан со А екі санды сА жне dA тадайды, олар
сАdA mod (р - 1) = 1 (2.1) болуы тиіс.
Бл сандарды А пияда сатайды жне В абонентіне жібермейді. В да екі пия санды св жне dв тадайды , олар
свdв mod (p - 1) = 1 (2.2)
Бдан со А шсатылы протоколды олданып зіні m хабарын береді. Егер m < р (m сан ретінде арастырылады) болса, онда т хабары лезде жіберіледі. Ал егер m 
р болса, онда хабар m1, m2,..., mt трінде беріледі. Мндаы mi < р, жне m1, m2,..., mt тізбектеліп беріледі. Осыан байланысты рбір mi кодалау шін кездейсо жаа жпты тадаан дрыс – арсы жадайда жйені сенімділігі тмендейді. азіргі кезде ереже ретінде мндай шифр сандарды жіберу шін олданылады. Мысалы: пия кілт р-дан аз делік. Сонымен, біз m < р жадайды ана арастырамыз.
Протоколды сипаттау.
1 адам. А х1 =mСА mod p (2.3) санын есептеп шыарады. Мнда m —бастапы хабар, жне х1 –ді В а жібереді.
2 адам.х1 хабарды алан В х2 = х1CB mod p (2.4) санын есептеп шыарады жне х2 ні А а береді.
3 адам.А х3 = х2dA mod p (2.5) есептеп шыарады жне оны В а береді.
4 адам.х3 хабарды алан В х4 = x3dB mod p (2.6) санын есепеп шыарады.
Шамир алгаритмі бойынша кілт алмасу слбасы 2-суретте крсетілген.
Сурет 2 – Шамир жйесіндегі кілт алмасу слбасы
Бекіту (Шамир протоколыны асиеттері):
1) х4 = m, яни протоколды тарату барысында шынында да А жне В дан бастапы хабар беріледі;
2) иратушы андай хабар берілгенін біле алмайды.
Длелдеу. Алашында кез-келген е 0 бтін сан, е = k(р — 1)+r трінде берілетінін байайы, мнда r = е mod (p - 1). Сондытанда Ферма теоремасына негізделген.
(2.7)
Бекітуді бірінші пункті келесі тедек тізбегінен пайда болады.
