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

1. 
   Шабуыл түрлері қандай?
   
2. 
   Криптографиялық протоколдар деген не?
   
3. 
   Симметриялық криптожүйелер қандай?
   
4. 
   DES (Data Encryption Standard)дегеніміз не?
   
5. 
   Хабарды шифрлау және дешифрлауды қалай жүргізуге болады?
   

• 
  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, орысша состояние деп аударған). Шифрлау блогы N_bүшін бағана, ал кілт үшін N_k бағана қолданылады. N_kкілт ұзындығын 32 бөлгендегі шығатын санға тең. N_b блок ұзындығын 32 бөлгендегі шығатын санға тең.

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

7-кесте.

Nr	Nb=4	Nb=6	Nb=8
Nk	10	12	14
Nk	12	12	14
Nk	14	14	14

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

х⁶+х⁴+х²+х+1

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

(х⁶+х⁴+х²+х+1) + (х⁷+х+1) = х⁷+x⁶+x⁴+x²

немесе

01010111+10000011=11010100

a(x) = a₃x³+a₂x²+a₁x+a₀x

b(x) = b₃x³+b₂x²+b₁x+b₀x

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

c₀=a₀b₀;

c₁=a₁b₀  a₀b₁;

c₂=a₂b₀a₁b₁ a₀b₂;

c₃=a₃b₀ a₂b₁a₁b₂ a₀b₃;

c₄=a₃b₁a₂b₂ a₁b₃;

c₅=a₃b₂  a₂b₃;

c₆=a₃b₃

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

(х)х⁴+1;

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

x^іmod (x)=x^{i mod 4}

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

d(x)=d₃x³+d₂x²+d₁x¹+d₀x

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

d₀=a₀b₀ a₃b₁ a₂b₂ a₁b₃;

d₁=a₁b₀ a₀b₁ a₃b₂ a₂b₃;

d₂=a₂b₀ a₁b₁ a₀b₂ a₃b₃;

d₃=a₃b₀ a₂b₁ a₁b₂ a₀b₃;

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

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

(x⁴+1)(x7+x⁵+x⁴+x²)=1

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

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

Round(State, RoundKey)

{

ByteSub(State);

MixClumn(State);

AddRoundKey(State, RoundKey);

}

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

ByteSub(State);

ShiftRow(State);

AddRoundKey(State, RoundKey);

}

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

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

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

8-кесте

Nb	C2	C3	C4
4	1	2	3
6	1	2	3
8	1	3	4

Блок бағаналары GF(2⁸)өрісіндегі көпмүшелер ретінде қарастырылады. Көпмүше 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

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

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

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

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

• 
  Үлкен сандарды көбейткішке жіктеу.
  
• 
  Ақырлы өрістерде логарифм есептеу.
  
• 
  Алгебралық теңдеулердің түбірлерін табу.
  

• 
  Деректердің қауіпсіздігін қамтамассыз ету үшін.
  
• 
  Кілт тарату тәсілі ретінде.
  
• 
  Аутентификация үшін.
  

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

Біз 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 саны үшін келесі салыстыру орындалады

a^p-11(mod p) .

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

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

r₀ = q₁ r₁ +r₂ , 021

r₁ = q₂ r₂ +r₃< r₂

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

r_m-2 = q_m-1 r_m-1 + r_m , 0mm-1

r_m-1 = q_mr_m

ЕҮОБ (r₀ ,r₁)=r_m

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

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

t₀=0, t_1=1, t_j=t_j-2-q_j-1t_j-1, j2 (4)

Лемма. Егер ЕҮОБ (r₀ ,r₁)=1

t_mr₁^-1(mod r₀) (немесе r₁ t_m1(mod r₀)) (5)

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

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

2. 
   m хабарды шифрлау үшіноны алдын ала n-нен кіші блоктарға бөлінеді. Екілік деректер үшін ұзындығы l–ге тең блоктар алынады, мұндағы l 2^li=m_i^emod n
   
3. 
   Дешифрлау үшін m_i=c_i^d есептелінеді.
   

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) формуласы). Енді Евклид алгоритміне сүйеніп q_i мәндерін табу үшін келесі есептеулер тізбегін табамыз
160=22*7+6

7=1*6+1

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

q₁=22; q₂=1; q₃=6

t₀=0; t₁=1; t₂=0-22*1=-22; t₃=1+1*22=23;

d=t₃=23

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

C=9⁷ mod 187 =((9²)³*9) mod 187=(((81)² mod 187)*(729 mod 187)) mod 187=(16 mod 187)*(168 mod 187 ) mod 187) mod187=70

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

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

70²³ mod 187=((70²)¹¹*70) mod 187=9.

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

A: Public n_A,e_A, Private d_A

B: Public n_B, e_B, Private d_B

m c= m^d_A mod n_A

=c^e_B mod n_B

=^dB mod n_B =c^eBdBmod n_B = v^(nB)k+1 mod n_B=(c^k)^(nB) c mod n_B=c

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

Шабуыл жасау

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

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

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

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

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

x=r^e_a mod n_A,

y=xc mod n_A,

t=r^-1 mod n_A

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

x^d_A=r^e_a^d_a mod n_A= r mod n _A

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

tu mod n_A=r^-1y^d_a mod n_A=r^-1x^d_ac^d_a mod n_A=c^d_a mod n_A=m

Мысал 2. Марат Айгүлді m₁ және m₂ хабарларына қол қойып бер деп сұрайды, яғни m₁^d_a mod n_A және m₂^d_a mod n_A мәндерін алады. Енді ол

C=(m₁m₂)^d_a mod n_A

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

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

(m^e_b mod n_B)^d_amod n_A

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

(m’)^x=m mod n_B

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

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

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

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

Протокол:

1. 
   Айгүл кездейсоқ үлкен бүтін х санын таңдап алып, =g^x mod p мәнін Болатқа жібереді.
   
2. 
   Болат кездейсоқ үлкен бүтін у санын таңдап алып, =g^y mod p мәнін Айгүлге жібереді.
   
3. 
   Айгүл k=^x mod p мәнін есептейді.
   
4. 
   Болат k’=^y mod p мәнін есептейді.
   

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

1. 
   Кездейсоқ х санын {0,...,2’-1}диапазонынан таңдап алады, мұндағы l 2’
2. 
   Құпия кілт K=h(x) мәнін h хэш-функция көмегімен табады.
   
3. 
   Айгүлдің ашық кілтімен х-ты шифрлап, оны Айгүлге c=x^e mod n жібереді.
   

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

1. 
   Жабық кілтінің көмегімен Айгүл x=c^d mod n санын тауып алады.
   
2. 
   Хэш-функция көмегімен Болатпен екеуіне ортақ K=h(x) құпия кілтін табады.