AES стандарты. Rijndael алгоритмдер. (Дәріс 5)

1. Дәріс 5

AES стандарты. Rijndael
алгоритмдері

2.

AES (Advanced Encryption Standard) стандарты DES
стандартын алмастырған, бір кілтпен шифрлеудің
жаңа стандарты болып табылады. Rijndael (рейн-дал)
алгоритмі шифрлеудің жаңа стандартын құруда
конкурс жеңімпазы болжы және AES стандарты үшін
таңдап
алынды.
Ол
Фейстель
желісін
пайдаланбайтын таңы бір алгоритм болды. Бұл
алгоритмді сипаттау үшін Галуа өрістері теориясынан
және оның кеңейтілімінен біраз мәліметтер керек
және оларды төменде қарастырамыз.

3.

Галуа өрістер теориясынан біраз мағлұматтар
Бірақ анықтамалар енгізейік.
Топ деп операциялар (қосу немесе көбейту) элементтерінің әрбір жұбы
үшін анықталған элементтер жиынын атайды, оған келесі аксиома дұрыс
болады:
1. Топ оған анықталған операция бойынша тұйық, яғни a, b топтың кез
келген элементтері үшін c = a * b элементі сондай-ақ топқа жатады.
Мұнда * топта анықталған операцияны білдіреді.
2. Ассоциативтілік. Топқа жататын кез келген a, b, c үшін (a * b) * c = a *
(b * c) орындалады.
3. Топта бірлік элемент е бар, ол a * e = e * a = a. Егер топтық операция
– бұл қосу болса, онда е – топтың нолі, егер операция – көбейту, онда е –
бұл топтың бірлігі.
4. Топтың a әрбір элементі үшін a-1 кері элементі бар, яғни a-1 * a = e .

4.

Топ коммутативті немесе абелевті деп аталады, егер оның
элементтері үшін a * b = b * a орындалғанда.
Егер топтық операция * бұл көбейту болса,
онда топ
мультипликативті деп аталады. Егер * - бұл қосу болса, онда топ
аддитивті деп аталады.
Мысалы: қосуға қатысты бүтін сандар, көбейтуге қатысты оң
рационалды сандар – бұлэлементтердің шексіз санымен топтар. Екі
модулі бойынша қосу операциясына қатысты {0,1} екіэлементті жиыны
элементтердің ақырғы санымен топты құрайды.
Сақина- бұл қосымша қасиеттері салынған абелевті топ. R
сақинасы деп ондағы екі анықталған операциялармен жиын аталады.
Біріншісі қосу, екіншісі көбейту деп аталады. Сондай-ақ келесі аксиома
орын алады:
• (+) қосуға қатысты сақина абелевті топ болып табылады.
• Көбейтуг операциясына қатысты шектеулік: c = ab сақинасынан кез
келген a и b сақинаға жатады.
• Дистрибутивтілік: a(c + b) = ac + ab
• Ассоциативтілік: a(bc) = (ab)c

5.

Коммутативті деп сақинаға жататын кез келген a мен b
элементтері үшін ab = ba орындалатын сақина аталады.
Сақинада қосу операциясы ноль деп аталатын бірлік
элементке ие. Көбейту операциясы бірлік элементке міндетті
түрде ие емес. Көбейту бойынша бірлік элементке ие болған
сақина бірлігі бар сақина деп аталады. Егер көбейту бойынша
бірлік элемент бар болса, онда ол – жалғыз және 1 символымен
белгіленеді. Онда сақинадан барлық а үшін 1a = a1 = a орын бар.
Қосу операциясына қатысты әрбір элемент кері ретке ие. Көбейту
операциясына қатысты берілген элементке кері элемент міндетті
түрде бар емес, бірақ бірлікпен сақинада кері элементтер бар
болуы мүмкін. Мысалы, нақты сандар жиыны қосу және
көбейтудің қарапайым операцияларына қатысты бірлікпен
коммутативті сақина құрайды. Барлық бүтін сандар жиыны (оң,
теріс және нольді қосқанда) бірлігі бар коммутативті сақина
құрайды.

6.

Басқаша айтқанда, абелевті топ жиын болып табылады, онда
қосуға және алуға болады, ал сақинамен – қосуға, алуға және
көбейтуге болатын жиындар. Өріс деп аталатын күшті алгебралық
құрылым қосуға, алуға, көбейтуге және бөлуге болатын жиындар
болып табылады.
Өріс алгебралық құрылым деп аталады, оған келесі аксиомалар
дұрыс:
Өріс – бұл көбейту бойынша бірлігі бар коммутативті сақина.
a-1 өрістің кез келген ноль емес элементі үшін кері a-1 элемент
бар, ол aa-1 = 1.
Мысалы, нақты сандар жиыны өрісті көрсетеді. Рационалды
сандар жиыны сондай-ақ өрісті көрсетеді. Бұл өрістер
элементтердің шексіз санынан тұрады. Ары қарай элементтердің
ақырғы саны бар өрістерді ғана қарастырамыз.

7.

Өріс р элементімен, егер ол бар болса (ол барлық р
болғанда бар бола бермейді), ақырғы өріс немесе Галуа өрісі
деп аталады және GF(р) арқылы белгіленеді. Кішігірім өріс екі
элементтен 0 және 1 тұрады, егер қосу және көбейту
операцияларының келесі ережелері орындалған кезде:

8.

Бұл GF(2) өрісі. Кез келген қарапайым р үшін р әртүрлі
элементтерден тұратын өріс бар екендігін көрсетуге болады. Мұндай өріс
р модулі бойынша орындалатын қосу және көбейту операцияларының
{0,1,2,...,р -1} элементтерімен сандық өріс болып табылады.
Мысалы. р = 5 болсын. Өріс элементтері 0,1,2,3,4 болып табылады.
Қосу және көбейту кестесінің түрі

9.

GF(р) өрісінің примитивті элементі деп осы элементтің
бірінші р-1 дәрежесі өрістің барлық ноль емес элементтерін
беретін а элементі аталады. Мысалы, GF(5) өрісінде 21 = 2,
22 = 4, 23 = 3, 24 = 1 аламыз. Демек 2 GF(5) өрісінің
примитивті элементі болып табылады. Примитивті элемент
р-1 ретке ие деп айтады. Примитивті элемент а-ға ар-1 = 1
дұрыс. Жалпы жағдайда элемент реті ең кіші бүтін оң сан,
осы санға тең дәрежеге шығарылған элемент1 береді. Кез
келген b элементтің реті примитивті элемент ретінің бөлгіші
болып табыладығ яғни р -1.
Мысалы, 41 = 4, 42 = 1, 4 элементінің реті 2 тең, р -1=4.
bр-1 =1 болары анық.

10.

Енді q = рт болсын, мұнда р – қарапайым, ал m – оң бүтін.
q = рт, т > 1 элементтер саны кезінде {0,...q-1} сандар
жиыны өріс болып табылмайтынын көрсетуге болады.
Мысал қарастырайық. q = 22 болсын. Қосу және көбейту
кестесін берейік мына түрде

11.

2 элементі көбейту бойынша кері ретке ие емес екендігі көрініп тұр,
яғни құрылым
өріс емес сақина болып табылады. Бірақ, төрт
элементтен GF(4) тұратын өрісті тұрғызуға болады. GF(рm) өрісінің
алгебралық құрылымы m дәрежесімен р(х) белгілі бір көпмүше модулі
бойынша GF (р) өрісінен коэффициенттермен бірге х айнымалысының
көпмүше сақинасын қарастырудан шығады. а(х) = b(x)modр(х) полином
дейді, егер b(х) = а(х) + Q(х)р(х), мұнда Q(х) – қандайда бір көпмүше.

12.

Мысал. Примитивті полномды таңдап алайық
р(х) = х2 + х +1. онда GF(22) өрісінің элементтері мына полномдар
болады:
0, 1, х, х2 = х +1.
Қосу операциясын орындау үшін қрістің элементтерін m ұзындықты
вектор түрінде көрсету ыңғайлы, яғни берілген мысалда, 00, 01, 10, 11
тізбегі түрінде. Полиномдарды қосу сәйкес тізбектермен екі модулі
бойынша компонент бойынша соммаға келтіріледі. Өрістің элементтерін
көрсетудің тағы бір көрінісін а өрісінің примитивті элементін пайдалана
отырып алуға болады. Біздің мысалдағы р(х) полиномы сондай-ақ
примиивті полином және а өрісінің примитивті полиномы – бұл оның
түбірі болып табылады. Басқаша айтқанда, а мына қатынасты
қанағаттандырады:a2 = a +1. өрістің барлық ноль емес элементтері
примитивті элемент дәрежесі ретінде алынуы мүмкін, яғни
a0 = 1, a1 = a, a2 =a +1.

13.

Примитивті элемент дәрежесі ретінде өріс элементтерінің көрінісі
осы өрісте көбінесе көбейту үшін қолданылады. Примитивті элемент реті
рm -1 тең. Біздің мысалда a3 = a2 + a = 1.
Өрістің кез келген элемент реті примитивті элемент ретінің бөлгіші
болып табылады, яғни рm-1 саны. Демек, кез келген b элементі үшін bрm-1
= 1 теңдігі орын алады. Егер (рm -1) – қарапайым сан болса, онда өрістің
барлық ноль емес элементтері (1 басқасы) примитивті, кері жағдайда (рm 1) бөлггіш сан реті бар элементтер табылады. Мысалы, GF (24) өрісінде
1, 3, 5,15 ретті элементтер бар.
х +1 элементіне кері элементті табайық. х(х +1) = х2 + х=1
болғандықтан, х +1-ге кері элемент х болады.

14.

Галуа өрісінде немесе оның кеңейтілімінде берілген элементке керіні табу
үшін Евклид бөлгіш алгоритмі қолданылады. Алдымен бүтін сандар үшін
Евклди бөлгіш алгоритмін қарастрайық және GF(р) Галуа өрісінде кері
элементін табу үшін ол қалай қолданылатынын талқылайық, мұнда р –
қарапайым. Евклид алгоритмінің мәні екі бүтін оң сандарды (а0,а1), а0 > а1
қалдықтар тізбегін есептеу жолымен ең үлкен жалпы бөлгішін (НОД)
табудан тұрады
(1)
мұнда
Қалдық ак+1 = 0 болғанда есептеу тоқтатылады, ак-ны бүтіндей ак-1
бөледі. Сонда НОД(а0,а1)= ак. Евклидтің кеңейтілген алгоритмі екі бүтін
оң санның НОД ғана табу емес, сондақ-ақ оның НОД(а0, а1=ха0+уа1)
түріндегі көрінісін көруге мүмкіндік береді, мұнда х, у- бұл бүтін
(міндетті оң емес) сан.

15.

х, у табу үшін Евклид алгоритмі келесі түрде модификацияланады:
1. х0 = 1, х1 = 0, у0 = 0, у1 = 1, і = 1 инициализациясы.
2.
аі+1 = аі-1 – Qiai
Егер аi+1=0, онда НОД(а0, аi)=аi, х=хi, у=уi және есептеуді аяқтау,
немесе
xi+1=xi-1-Qixi
yi+1=yi-1-Qiyi
і = і +1
2 қадамға көшу.
3.
4.
Мысал. НОД(57,33) табайық және оның көрінісі НОД(57,33) = х•57 + у•33.
есептеу нәтижесі кестеде келтірілген

16.

і
аi
Qi
хi
уi
57
—
1
0
33
[57/33]=1
0
1
2
57-1x33=24
[33/24]=1
1-1х0=1
0-1х1=-1
3
33-1x24=9
[24/9]=2
0-1х1=-1
1-1х(-1)=2
4
24-2x9=6
[9/6]=1
1-2x(-1)=-1
-1-2х2=-5
5
9-1*6=3
[6/3]=2
-1-1*3=-4
2-1х(-5)=7
6
6-2хЗ=0
0
1
НОД(57,33)=3
3=57х(-4)+33х7
Демек, НОД(57,33) = 3 = 57•(-4) + 33•7 аламыз.