«Ақпаратты қорғау» ПӘнін оқыту-әдістемелік кешен



бет9/15
Дата14.06.2016
өлшемі2.22 Mb.
#135154
1   ...   5   6   7   8   9   10   11   12   ...   15

Бекіту сұрақтары:

  1. Шабуыл түрлері қандай?

  2. Криптографиялық протоколдар деген не?

  3. Симметриялық криптожүйелер қандай?

  4. DES (Data Encryption Standard)дегеніміз не?

  5. Хабарды шифрлау және дешифрлауды қалай жүргізуге болады?



Дәріс 14. AES. Ашық кілтті криптожүйе. RSA криптожүйесі. Алгоритм Диффи-Хеллмана. Гибрид криптожүйелер

Мақсаты: AES және ашық кілтті криптожүйе, RSA криптожүйесі, алгоритм Диффи-Хеллмана, гибрид криптожүйелерімен танысу, олардың ұқсастықтарымен ерекшеліктері.

Жоспары:

  • AES

  • Ашық кілтті криптожүйе

  • RSA криптожүйесі

  • Алгоритм Диффи-Хеллмана

  • Гибрид криптожүйелер

АҚШ стандарттар және технологиялар ұлттық институты (NIST) 1997 жылы жаңа крипографиялық стандарт таңдап алу үшін сынақ жариялады (www.nist.gov). Дүние жүзіендегі ең әйгілі криптологиялық ұйымдар NIST жұмысына үлес қосты.

Сынаққа 15 ұсыныс келіп түсті. Комитет мамандары екі жыл бойы жұмыс жасап, ең жақсы деген 5 талапкерді таңдап алды.

Конкурс финалына келесі алгоритмдер шықты: MARS, TWOFICH, RC6 (АҚШ), RIJNDAEL (Белгия), SERPENT (Ұлыбритания, Израйль, Норвегия), Конкурс 2000 жылы мынандай нәтижелермен аяқталды:

MARS – 13 дауыс (Д. Коппермит және басқалары)

TWOFICH – 31 дауыс (Б. Шнайер және басқалары)

RC6 – 23 дауыс (Р. Ривест және басқалары)

RIJNDAEL – 86 дауыс

SERPENT – 59 дауыс (Р. Андерсон).

Жеңімпаз болып бельгиялық RIJNDAEL алгоритмі аталды (www.nist.gov/encription/aes қара) Авторлары - JoanDaemenVincentRijmen.

Осы уақыттан бастап алгоритмнен алдындағы патенттік шектеулер алынып тасталған. Алгоритмді сіз тегін шектеусіз қолдануыңызға рұқсат бар.

RIJNDAEL алгоритмнің атауы жайындағы Р. Андерсонның ([І], 93 б. қара) ескертуін келтіріп кетейік: “Егер сіз Голландия, Белгия немесе Оңтүстік Африкадан болсаңыз, онда Rijndael сөзінің аталуы ойыңдағыңыздай болады. Әйтпесе ол “ rain-dahl ” тәріздес оқылады. Rijmen сөзі “Ridgmen”, емес “Raymen” деп оқылады.

15 алгоритмнің толық сипаттамасын жоғарыда жазылған NIST институтының серверында таба аласыз. Біз RIJNDAEL алгоритмінің негізгі қадамдарын ғана қарастырамыз. Программаның коды 9-ші бөлімде келтірілген.

RIJNDAEL итерациялық блоктық шифрға жатады. Кілт мен блоктардың ұзындығы бір-біріне байланыссыз. 128, 192, 256 битке тең болуы мүмкін.

Аралық нәтижелер 4 жолы бар массивте жатады. Төменде оны сәйкесінше нәтижелер массиві мен кілтшілер массиві деп атайтын. (Ағылшынша state, орысша состояние деп аударған). Шифрлау блогы Nbүшін бағана, ал кілт үшін Nk бағана қолданылады. Nkкілт ұзындығын 32 бөлгендегі шығатын санға тең. Nb блок ұзындығын 32 бөлгендегі шығатын санға тең.

Раунд саны Nb және N сандарына тәуелді (7-кестеге қараңыз).

7-кесте.

Nr

Nb=4

Nb=6

Nb=8

Nk

10

12

14

Nk

12

12

14

Nk

14

14

14

Криптоалгоритмде қолданылатын операцияларGF(28)өрісіне тиісті элементтерде анықталған. GF(28) өрісінің элементтері болып дәрежесі екілік көпмүшелер саналады. 0 1 0 1 0 1 1 1 байтына келесі көпмүше сәйкес.

х642+х+1

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

642+х+1) + (х7+х+1) = х7+x6+x4+x2

немесе

01010111+10000011=11010100



Екі көпмүше үшін көбейту амалын қарастырайық:

a(x) = a3x3+a2x2+a1x+a0x

b(x) = b3x3+b2x2+b1x+b0x

Нәтиже ретінде коэффиценттері келесідей С(х) көпмүшесін аламыз.

c0=a0b0;

c1=a1b0  a0b1;

c2=a2b0a1b1 a0b2;

c3=a3b0 a2b1a1b2 a0b3;

c4=a3b1a2b2 a1b3;

c5=a3b2  a2b3;

c6=a3b3

Енді нәтижені дәрежесі 4-тен аспайтын көпмүше модулі бойынша алу қажет. Алгоритм құрастырушылар келесі көпмүшені ұсынған:

(х)х4+1;

Бұл мүше үшін келесі теңдік орындалады.

xіmod (x)=xi mod 4

Ақыры нәтижеміз

d(x)=d3x3+d2x2+d1x1+d0x

көпмүшесі болады, мұндағы

d0=a0b0 a3b1 a2b2 a1b3;

d1=a1b0 a0b1 a3b2 a2b3;

d2=a2b0 a1b1 a0b2 a3b3;

d3=a3b0 a2b1 a1b2 a0b3;

Ақырлы өрісте кез келген нөлге тең емес z элементі үшін мультипликативный кері элемент z-1 анықталған және zz-1=1

Өзара кері көпмүшелер мысалы:

(x4+1)(x7+x5+x4+x2)=1

Раунд төрт түрлендіруден тұрады: нәтижелер массивындағы байттарды ауыстыру; жолдарды жылжыту; бағандарды араластыру; раундтық кілтті қосу.

Раунд сипаттамасы:

Round(State, RoundKey)

{

ByteSub(State);



ShiftRow(State);

MixClumn(State);

AddRoundKey(State, RoundKey);

}

Соңғы раундта бағаналарды алмастыру операциясы орындалмайды:



{

ByteSub(State);

ShiftRow(State);

AddRoundKey(State, RoundKey);

}

1-ші қадам. Байт ауыстыру



Әрбір нәтиже массивындағы байттар үшін ауыстыру процедурасы орындалады. Ауыстыру таблицаларын келесі теңдеумен анықтауға болады: S(x)=M(1/x)+b мұндағы M таңдап алған матрица, b – тұрақты вектор.

2-ші қадам. Жол жылжыту

Нәтижелер массивының 1-ші жолы жылжымайды. Келесі жолдар Сі, і2..4 коэффицентіне блок ұзындығына байланысты.

8-кесте


Nb

C2

C3

C4

4

1

2

3

6

1

2

3

8

1

3

4

3-ші қадам. Бағаналарды алмастыру

Блок бағаналары GF(28)өрісіндегі көпмүшелер ретінде қарастырылады. Көпмүше c(x)=’03’x3+’01’x2+’01’x+02’ көпмүшесіне көбейтіледі, бұл операция келесі матрицаға көбейткенмен тепе-тең:



02

03

01

01

01

02

03

01

01

01

02

03

03

01

01

02

4-ші қадам. Раундтік кілтті қосу

XOR операциясының көмегімен нәтижелер массивы кілтшелер массивына қосылады.

Кілт жасау алгоритмі. Алдымен кілт кеңейту процедурасы орындалады. Алғашқы Nk сөз шифрлау кілтінен тұрады. Қалғандары индексі кішіректерінен рекурсия арқылы анықталады.

Раундтық кілттер кеңейтілген кілттен келесі ереже бойывнша алынады: бірінші раундтық кілт алғашқы Nb сөзге тең, екіншісі – келесі Nb сөзге т.с.с.



Ашық кілтті криптожүйе. Ашық кілтті криптографияның негізін қалаған Уитфилдом Диффи (Whitfield Diffie) және Мартином Хеллманом (Martin Hellman). Алдыңғы азаматтарға тәуелсіз Ральфом Мерклом (Ralph Merkle) де ойлап тапқан. Симметриялық криптография бір кілтті қолданса мұнда екі кілт – біріншісі шифрлау үшін, екіншісі дешифрлау үшін қолданылады. Сіз бірінші кілтті біле отырып екіншісін біріншісінен есептеп таба алмайсыз. Диффи және Хеллман бұл идеяны алғаш рет 1976 жылы ұсынған және “New Directions in Cryptography” атты жұмысында жариялаған.

Бүгінгі таңда ашық кілтті криптография негізінен келесі түрлендірулердің бірін қолданады:



  • Үлкен сандарды көбейткішке жіктеу.

  • Ақырлы өрістерде логарифм есептеу.

  • Алгебралық теңдеулердің түбірлерін табу.

Ашық кілтті криптожүйені келесі 3 бағытта қолдануға болады:

  • Деректердің қауіпсіздігін қамтамассыз ету үшін.

  • Кілт тарату тәсілі ретінде.

  • Аутентификация үшін.


RSA криптожүйесі. RSA криптожүйесін Рон Ривест (Ron Rivest), Ади Шамир (Adi Shamir) және Леонард Адлеман (Leonard Adleman) ойлап тапқан. Алгоритм үлкен санды жай көбейткіштерге жіктеу есебінің қиындығына сүйенген.

Алгоритм сипаттамасын берер алдында сандар теориясынан кейбір мәліметтерді еске түсірейік.



Анықтама. a және b бүтін сандарын n модулі бойынша салыстырмалы дейді егер a-b айырымы n–ге қалдықсыз бөлінетін болса.

Біз n1 деп есептейміз. a, b, n сандарының арасындағы қатынас былай жазылады a  b(mod n).

Мысал 25  4(mod 7), -5  34 (mod 13)

Анықтама. n модулі бойынша белгілі бір a санымен салыстырмалы сандардың жэиыны сынып деп аталады. Ол a деп белгіленеді.

Мысал. 6 модулі бойынша 5 сыныбы: {...-7, -1, 5, 11, 178, 23 ...}

Модулярлық арифметиканы компьютерлік есептеулерге қолдану үшін біз тек қана шектелген мәндер диапозонын қарастырумыз керек. Сондықтан негізінен a сыныбындағы ең кіші оң санмен жұмыс істейді. Сандар теориясында мұндай санның бар екендігі және де ол а-ны n-ге бөлгендегі қалдыққа тең екендігі дәлелденген.

Ескерту. Программалау тілдерінде mod функциясы басқаша анықталуы мүмкін.

Модулярлық арифметика қарапайым арифметикаға ұқсас. Ол коммутативті, ассоциативті және дистрибутивті.

(a+b) mod n = ((a mod n) + (b mod n)) mod n

(a-b) mod n = ((a mod n) - (b mod n)) mod n (1)

(a*b) mod n = ((a mod n) * (b mod n)) mod n

(a*(b+c)) mod n = (((a*b) mod n)+((a*c) mod n)) mod n

Анықтама. Эйлер функциясы n-нан кіші және n-мен жай оң бүтін сандардың санына тең функцияны айтады. Функция (n) деп белгіленеді.

Мысалға, (10)=4. Эйлер функциясының келесі тамаша қасиеті бар: егер n=pq, мұндағы p және q – жай сандар, онда

(n)=(p-1)(q-1). (2)

Теорема 1 (Эйлер). Кез-келген р жай саны үшін және р-ға бөлінбейтін кез-келген а1 саны үшін келесі салыстыру орындалады

ap-11(mod p) .



Теорема 2 (Эйлер). Кез-келген n модулі мен n-мен өзара жай саны үшін келесі салыстыру ақиқат

a (p)-11(mod n). (3)



Евклид алгоритмі

r0 > r1>0 оң бүтін сандары берілсін. Олардың ең үлкен ортақ бөлгішін (ЕҮОБ) табу үшін келесі есептеулер тізбегі орындалады.

r0 = q1 r1 +r2 , 021

r1 = q2 r2 +r3< r2

...........................

rm-2 = qm-1 rm-1 + rm , 0mm-1

rm-1 = qmrm

ЕҮОБ (r0 ,r1)=rm

Кеңейтілген Евклид алгоритмі.

Келесі сандық тізбек анықтайық {ti}mi=0 мұндағы

t0=0, t1=1, tj=tj-2-qj-1tj-1, j2 (4)

Лемма. Егер ЕҮОБ (r0 ,r1)=1

tmr1-1(mod r0) (немесе r1 tm1(mod r0)) (5)

Ал енді алгоитмді сипаттайық:


  1. Екі үлкен кездейсоқ жай p және q сандары таңдап алынады. Көбейтіндісі табылады n = pq. Енді (p-1)(q-1) санымен өзара жай кездейсоқ е саны таңдап алынады. Кеңейтілген алгоритмнің көмегімен келесі кері саны есептелінеді

de  1 (mod(p-1)(q-1))

  1. m хабарды шифрлау үшіноны алдын ала n-нен кіші блоктарға бөлінеді. Екілік деректер үшін ұзындығы l–ге тең блоктар алынады, мұндағы l 2li=miemod n

  2. Дешифрлау үшін mi=cid есептелінеді.

Расында, (1), (2) және (3) формулаларын қолдана отырып, алатынбыз
cid mod n=(mie mod n)d mod n=mied mod n = mik (n)+1 mod n = (((mik) (n)mod n) * (mi mod n )) mod n = mi
Тұтынушы n, e кілттерін ашық деп (Public Key) жариялайды, ал b кілті жабық кілт болып саналады (Private key).

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

ITS ALL GREEC TO ME

Әр символға 5 разряд арнап, бос орынды – 0, А әрпін – 1, В әрпін – 2,......,Z әрпін – 26 деп кодтаған. Келесі үлкен сан алған m1=

09201900011212000718050511002015001305.

Ашық кілттердің мәні ретінде е = 9007, n =

11438162575788886766923577997614661201021829672124236256265184293

570693524573389783059712356395870505898907514759920026879543541


деп алған.

Сонда шифрланған санның түрі келесідей болып шықты:

c = 19993513149780510045231712274026064742320401705839146310370371

7406259971608948922750439920962672582675012893554461353823769748026


Енді біз есептеу алгоритмін толық сипаттайтын мысал келтірейік.

Мысал. Жай сандар ретінде p=11, q=17 таңдап алайық. Онда n=pq=187, (n)=(p-1)*(q-1)=160.

Кез-келген (n)–мен өзара жай е санын таңдайық, яғни (e, 160)=1. Мысалға, e=7 болсын. Келесі теңдеуден d жабық кілтін табу керек:

7d=1 mod 160

Алдында келтірілген кеңейтілген Евклид алгоритмін қолданамыз ((5) формуласы). Енді Евклид алгоритміне сүйеніп qi мәндерін табу үшін келесі есептеулер тізбегін табамыз
160=22*7+6

7=1*6+1


6=6*1

Ақыры алатынымыз:

q1=22; q2=1; q3=6

t0=0; t1=1; t2=0-22*1=-22; t3=1+1*22=23;

d=t3=23

Ашық кілттер e=7, n=187 жариялап, жабық кілтті d=23 құпияда сақтаймыз. Қолайлылық үшін бастапқы мәтін ретінде M=9 деп алып, С шифрланған мәтінін табамыз.

C=97 mod 187 =((92)3*9) mod 187=(((81)2 mod 187)*(729 mod 187)) mod 187=(16 mod 187)*(168 mod 187 ) mod 187) mod187=70

Шифрлау кезінде өте үлкен сандармен жұмыс істемеу үшін сандарды біртіндеп алдымен квадраттап нәтижені n модулі бойынша алады. Сонда n2 санынан артық сан пайда болмайды. Бұл тәсілді «квадраттау да, көбейту» (ағылшынша «square-and-multiply») деп атайды.

Хабарды алушы оны дешифрлау үшін d жабық кілтін қолданады:

7023 mod 187=((702)11*70) mod 187=9.

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

A: Public nA,eA, Private dA

B: Public nB, eB, Private dB

m c= mdA mod nA

=ceB mod nB

=dB mod nB =ceBdBmod nB = v(nB)k+1 mod nB=(ck)(nB) c mod nB=c

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

Шабуыл жасау

Ұсынылған алгоритмнің қауіпсіздігі үлкен сандардың жай сандарға жіктеу есебінің қиындығына сүйенген. Басқа сөзбен айтқанда факторизация есебін шешуге болады, бірақ ол тым көп уақыт алады. Қазір келесі жіктеу алгоритмдері белгілі: (Number Field Sieve), QS (Quadratic Sieve), ECM (Elliptic Curve Method) және басқалары. Ең тез алгоритм болып бүгінше NSA саналады.

Есептеу қабілеттілігі MIPS–жылдарымен саналады. MIPS–жыл дегеніміз – секундына миллион операция (million instructions per second) орындайтын компьютердің жылдық жұмысы, яғни шамамен 3*10 13операция. Мысалы, 1024-биттік сөзді NSA алгоритмімен жіктеу үшін 3*107 MIPS жыл кетеді.

Кілттің ұзындығын дұрыс таңдап алу үшін керекті қауіпсіздік дәрежесін анықтау қажет және жаңадан жасалып жатқан жіктеу алгоритмдерінің мүмкіндіктерін ұмытпау қажет. Ашық кілтіңіздің ұзындығын 2048 бит етіп алсаңыз алдыңғы 20 жылға оған сенімді болуыңызға болады. Бірақ әрине мұндай болжаулар орындалмай кетуі де мүмкін.

Енді біз алгоритмнің өзін емес сол алгоритмді қолданып отырған криптографиялық протоколға жасалатын шабуыл мысалдарын келтірейік.

Мысал 1. Марат уысына Айгүлдің әлдебіреуге жіберген шифрланған с хабары түсті. Марат кездейсоқ r

x=rea mod nA,

y=xc mod nA,

t=r-1 mod nA

Осыдан r-1 xda1(mod nA) екендігі көрініп тұр. Сонымен қатар

xdA=reada mod nA= r mod n A

Енді Марат Айгүлден у-ге қол таңба қоюды сұрайды да u=yda mod nAмәнін табады. Марат бастапқы хабарды келесі есептеулерді жасап тауып алады:

tu mod nA=r-1yda mod nA=r-1xdacda mod nA=cda mod nA=m

Мысал 2. Марат Айгүлді m1 және m2 хабарларына қол қойып бер деп сұрайды, яғни m1da mod nA және m2da mod nA мәндерін алады. Енді ол

C=(m1m2)da mod nA

Мәнін есептесе Айгүл өзі ешқашан көрмеген m3=m1m2 құжатына қол қойған болып шығады.

Мысал 3. Бұл мысал қол қою алгоритмінде орындалатын қадамдардың ретін бұзатын протоколдарға қалай шабуыл жасауға болатынын көрсетеді. Мысалы Айгүл Болатқа шифрланған және қол қойылған хабарды жіберсін. Бірақ алгоритмді қолданғанда Айгүл алдымен m хабарын Болаттың ашық кілтімен, ал соңынан өзінің жабық кілтімен қол қояды:

(meb mod nB)damod nA

Болат өзінің ашық кілті nB-нің жіктелуін білетіндіктен, келесі теңдік орындалатындай х санын таба алады

(m’)x=m mod nB

Енді ол өзінің жаңа ашық кілттерін жариялайтын болса, Айгүл m’ құжатына қол қойды деп айта алады.

Кішкентай мәнді құжаттарды шифрлағанда тағыда бір қатерлікті атап өтейік. Мысалы, e=5 және m<√n болсын, онда c=m5 mod n=m5 . Бұзғыш Маратқа бастапқы хабарды тауып алу үшін √c мәнін есептеп алу жеткілікті.


Алгоритм Диффи-Хеллмана. Тарихи Диффи-Хеллмана алгоритмі бірінші ашық кілтті алгоритм болды. Оның қауіпсіздігі арқылы өрісте дискреттік логарифм есептеу есебінің қиындығына сүйенген.

Яғни, егер y=ax mod n мінін берілген х арқылы оңай таба алсаңыз, берілген у арқылы х-тің мәнін табу қиынға түседі.

Төменде Диффи-Хеллмана кілт ауыстыру протоколы көрсетілген. Айгүл мен Марат алдын ала үлкен жай p мен n модулі бойынша примитивтік түбір g сандары туралы келісіп алады.

Протокол:



  1. Айгүл кездейсоқ үлкен бүтін х санын таңдап алып, =gx mod p мәнін Болатқа жібереді.

  2. Болат кездейсоқ үлкен бүтін у санын таңдап алып, =gy mod p мәнін Айгүлге жібереді.

  3. Айгүл k=x mod p мәнін есептейді.

  4. Болат k’=y mod p мәнін есептейді.

Табылған k және k’ мәндері gxy mod p санына тең. Сонда Айгүл мен Болат ортақ бір кілтке ие болады. Бұзғыш Марат ашық каналды жасырын қадағалап отырса да қолына түсетін сандар арқылы құпия кілтті анықтай алмайды.

Гибрид криптожүйелер. Практикада RSA алгоритмі хабарды шифрлау үшін қолданылмайды. Алгоритмнің жылдамдығы DES алгоритмімен салыстырғанда 1000 есе баяу. Сондықтан көбінесе гибрид криптожүйелер қолданылады. Гибрид криптожүйелер ашық кілтті және жабық кілтті алгоритмдерді бірдей қолданады. Мұндай алгоритмнің орындалу реті келесідей болуы мүмкін. Жабық K кілтін RSA алгоритмінің көмегімен шифрлауға болады. Бастапқы құжаттар блоктық немесе ағында алгоритмімен К құпия кілтімен шифрланады. Сонда RSA алгоритмін бір рет қана орындауға болады. Симметриялық алгоритмдердің кемшілігі – құпия кілт ауысу процедурасы болып табылады. Төменде бұл есеп шешуінің қарапайым жолын келтірдік. Болат ашық каналмен Айгүлге К құпия кілтін былай жібереді.

Жіберуші (Болат):



  1. Кездейсоқ х санын {0,...,2’-1}диапазонынан таңдап алады, мұндағы l 2’

  2. Құпия кілт K=h(x) мәнін h хэш-функция көмегімен табады.

  3. Айгүлдің ашық кілтімен х-ты шифрлап, оны Айгүлге c=xe mod n жібереді.

Алушы (Айгүл):



  1. Жабық кілтінің көмегімен Айгүл x=cd mod n санын тауып алады.

  2. Хэш-функция көмегімен Болатпен екеуіне ортақ K=h(x) құпия кілтін табады.



Достарыңызбен бөлісу:
1   ...   5   6   7   8   9   10   11   12   ...   15




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет