Rijndael algoritmida bitlar ustida asosiy arifmetik amallarni bajarish

Rijndael algoritmida bitlar ustida asosiy arifmetik

amallarni bajarish

Bu algoritmni belgiyalik olimlar В.Reyman va Y.Damanlar tomonidan ishlab chiqildi. Algortim 2001-jıli АQSH ning yangi standarti sifatida qabul qilindi. Shifrlash algoritmida blokning uzunligi 128 bit, gilt uzunligi 128, 192 yoki 256 bit bo’lishi va raundlar soni mos kalitning uzunligiga bog’liq 10, 12 yoki 14 dan turishi mumkin. Rijndael algoritmida barcha amallar baytlar yordamida ifodalanadi. Baytlar bo’lsa chekli maydonining elementlari sifatida qaraladi. Ba’zi bir amallar to’rt baytli so’zlar terminlarinda aniqlanadi. Agarda bayt bitlardan tashkil topgan bo’lsa, u holda koefficentleridan turuvchi ko’phad asosida quyidagicha yozamiz:

_(2.2)

Мisol uchun ketma – ketligi elementi sifatida ifodalaniladi . Baytning qiymatini 16-lik sanoq sistemasida yozish qulay, bunda baytlar 4 bitdan turuvchi ikkidan guruxga

Bitlar	Simvol		Bitlar	Simvol		Bitlar	Simvol		Bitlar	Simvol
0000	0		0100	4		1000	8		1100	C
0001	1		0101	5		1001	9		1101	D
0010	2		0110	6		1010	A		1110	E
0011	3		0111	7		1011	B		1111	F

bo’linadi va har bir gurux bir simvolni ifodalaydi, ya’ni quyidagicha

ketma – ketligini 16-lik sistemadagi ko’rinishida yoshimiz mumkin.

Bayt massivlari quyidagicha turda ifodalanadi:

(2.3)

Bunda kiruvchi ketma –ketlikdagi har bir birni deb belgilaymiz. 128 bitli kiruvchi ketma –ketlikdan bitlarni

(2.4)

2.4 ko’rinishda ajratib olamiz. Bu misol 192, 256 bitli kalitlar uchun ham

(2.5)

Formulasiga kengaytirilishi mumkin. 2.12-rasmda kiruvchi ketma – ketlikdagi har bir bayt uchun bitlar chegarasi raqamlanishi ko’rsatilgan.

AES algoritmida baytlar matritsasi ustida amallar bajariladi. Bu matsitsa holat matritsasi deb ataladi va uni biz harfi bilan belgilaymiz. matritsaning har bir satri baytdan tashkil topgan 4 satrdandan tuziladi, bunda 32 ga bo’lingan blok uzunligi. matritsasidagi har bir baytning joylashuvi ikkita indejks bilan aniqlanadi: satr raqami va ustun raqami .

Кiriwshi izbe-izliktegi bitler nomeri	0	1	2	3	4	5	6		7	8	9	10	11	12		13	14	15	16	17	18		19	20	21	22	23	…
Bayt nomeri	0							1							2							…
Bayta bit nomeri	7	6	5	4	3	2	1		0	7	6	5	4	3		2	1	0	7	6	5		4	3	2	1	0	…

2.12-rasm. Bayt va bitlar raqamlanishi.

SHifrlash/deshifrlash amallari uchun kiruvchi ma’lumotlar 16 baytdan turadigan massivi tuziladi. SHifrlash/deshifrlashdan oldin bu massivning baytlari quyidagicha rasmdagiday kabi matritsaga joylashtiriladi:

Кiruvchi baytlar

Holat matricası

Chiquvchi baytlar

in0

in4

in8

in12

S0,0

S0,1

S0,2

S0,3

out0

out4

out8

out12

in1

in5

in9

in13

S1,0

S1,1

S1,2

S1,3

out1

out5

out9

out13

in2

in6

in10

in14

S2,0

S2,1

S2,2

S2,3

out2

out6

out10

out14

in3

in7

in11

in15

S3,0

S3,1

S3,2

S3,3

out3

out7

out11

out15

2.13-rasm. Holat matritsasi kiruvchi massiv va chiquvchi massiv.

SHifrlash/deshifrlash jarayonida matritsaadagi baytlar qiymati o’zgaradi. Мatritsaning so’nggi qiymati algoritmning chiqishi bo’lib, massivini tashkil qiladi va u chiquvchi baytlar ketma-ketligini tuzadi.

Shunday qilib shifrlash/deshifrlashdan oldin kiruvchi ma’lumotlar matritsasiga

(2.6)

formulasiga mos turda kiritiladi, bunda .

Shifrlash/deshifrlash natijasini chiqarishda matritsasidagi baytlar

(2.7)

formulasi asosida massiviga ko’chiriladi, bunda .

matritsasining har bir ustunidagi 4 baytni bir 32 bitli so’z sifatida qarash mumkin. Shunday qilib matritsasi 32 bitli so’zlardan tuzilgan bir o’lchamli massiv sifatida ko’rsatish mumkin. Ustunlarni , deb belgilasak, onda matritsasi

Yuqorida aytib o’tganimizday algoritmdagi barcha baytlar chekli maydon elementlari sifatida o’rganiladi. Chekli maydon elementlarini ustida qo’shish va ko’paytirish amallarini bajarish mumkin. Lekin bu amallar odatdagi sonlar ustida bajariladigan amallardan farqli bo’lib, aniq bir qoida bo’yicha amalga oshiriladi.

Chekli maydonda sonlar ko’phad turida o’rganiladi. Shundan ikki sonni qo’shish shu sonlarni anglatuvchi ko’phadlarni qo’shish bilan amalga oshiriladi. Ikkita ko’phadlarni qo’shish ularning bir hil darajadagi koeffisentlarini qo’shish yo’li bilan amalga oshiriladi. Кoeffitsientlarni «qo’shish» amali ( bilan belgilanadi), ya’ni 2 moduli bo’yicha qo’shish yordamida bajaroladi . Bunda ayirish amali qo’shish amali bilan bir qiymatli amalga oshiriladi.

Chekli maydonda sonlarni qo’shishning ikkinchi usuli bu - baytdagi mos bitlarni 2 moduli bo’yicha qo’shish bo’lib hisoblanadi. Ikkita va yig’indisi bo’ladi, bunda

Bu quyidagicha tenglik bir biriga ekvivalent:

(ko’phadlar ko’rinishida ko’rsatilishi mumkin)

(ikkilik ko’rinishda belgilanish)

(16 sanoq sistemasi ko’rinishida)

Bunda tenglik qanday bajarilishini quyidagicha ko’rishimiz mumkin.

O’n oltilik sanoq sistemasidagi «57» qiymatiga teng baytga (ikkilik sanoq sistemasida ) quyidagicha ko’phad mos keladi:

Ko’phadlarni qo’shishda elementlarning yig’indisi 2 moduli bo’yicha bajariladi (ya’ni ).

bo’ladi, agar ko’phad ko’rinishida bo’lsa quyidagicha

Endi binar turda hisoblanishini ham ko’rib chiqamiz

Bu ko’phadlarni ko’paytirishda daraja ko’rsatgichlari o’sadi. Shundan algoritmda modul sifatida ko’paytuvchilarga ajratilmaydigan ko’phad qo’llaniladi, ya’ni u faqat 1 ga va o’ziga bo’linadigan ko’phad bo’ladi. Rijndael algoritmida bul ko’phadni bilan belgilaymiz.U quyidagicha:

(2.8)

Ya’ni u 16-lik sanoq sistemasida ga teng bo’ladi.

Misol uchun. bo’ladi, ya’ni



+

Natijada

moduli bo’yicha solishtirishimizning sababi ikkita ko’phadni ko’paytirganda daraja ko’rsatgichi 8 dan oshib ketmasligi kerak. Yuqorida qaralgan ko’paytirish amali assotsiativ bo’lib birlik element asosida hisoblanadi. Ixtiyoriy nollik emas darajasi 8 dan kichik binar ko’phadiga teskari bo’lgan ko’phadini toppish mumkin. Teskari elementni toppish uchun Еvklidning kengaytirilgan algoritmidan foydalanamiz.

(2.2) binar ko’phadini ga ko’paytirganda

(2.9)

kelib chiqadi. Agarda bo’lsa, unda (2.9) va moduli bilan taqqoslash shart emas, bo’lsa, taqqoslash shart hisoblanadi. x ga ko’paytirish baytlar darajasida aniqlanishi mumkin, ya’ni dastlab chapga siljish bajariladi, so’ng (talab qilinsa) soni bilan amali bajariladi. Bu baytlar ustidagi amallarni deb belgilaymiz. ning yuqori darajalariga ko’paytirganda amalini takror qo’llash mumkin. Мisol uchun:

Кoeffitsientlari chekli maydonning elementlari bo’lgan 4-chi darajali

ko’phad

(2.10)

ifodasi yordamida aniqlanadi. Bu ifoda keyin sifatidagi so’z shaklida ko’rsatiladi. Qo’shish va ko’paytirish amallarining bajarilishini ko’rsatish uchun yana bir 4-chi daraali ko’phadni aniqlaymiz:

(2.11)

Shundan so’ng bir hil daraja ko’rsatgichlarining koefitsienlarini ikki moduli bo’yicha qo’shamiz, ya’ni ikki so’z orasida amali bajariladi. Natijada:

(2.12)

Ko’paytirish yoki ikki bosqichdan turib, birinshi bosqichda ko’paytmasi bajarilganda qavslar ochilib ning o’xshash hadlari guruxlanadi, shunda:

(2.13)

bunda

(2.14)







ko’phadini 4 baytli so’z ko’rinishida ko’rsatib bo’lmaydi. Shundan 2-bosqichda modulini 4-darajali ko’phad bilan beriladigan modul bilan taqqoslanadi. Natijada darajasi 4 dan kichik bo’lgan ko’phadni olamiz.

Аlgoritmda modul sifatida ko’phadi qo’llaniladi. Bunda quyidagilar o’rinli bo’ladi:

(2.15)

va ko’phadlarining ko’paytmasi

(2.16)

bo’ladi, bunda

(2.17)

Agarda fiksirlangan ho’phad bo’lsa, unda ikki ko’phadlarni ko’paytirish amalini matritsaviy ko’rinishda quyidagicha yozish mumkin ya’ni:

(2.18)

ko’phadi maydonida ko’paytuvchilarga ajratilmaydigan ko’phad bo’lganlikdan fikserlanagan 4hadini ko’phadga ko’paytirish hamma vaqtda teskari akslantirishga olib kelmaydi. Shundan algoritmda 4 hadli teskari elementi mavjud bo’lgan ko’phad qo’llaniladi, ya’ni

(2.19)

BUndan tashqari algoritmda qo’llaniladigan ko’phadning koeffitsentlari: bo’lib ko’phadiga mos keladi. (11) dan kiruvchi so’zning fiksirlangan ko’phadiga ko’paytmasi uning baytlarining almashishidan paydo bo’ladigan chiquvchi so’z olinadi, ya’ni so’zi so’zi ko’rinishida ifodalaymiz.

Rijdael algoritmida shifrlash va deshifrlash jarayoni quyidagicha raund funktsiyalari yordamida amalga oshiriladi.

1. 
   O’rin almashtirish jadvali yordamida baytlarni almashtirish (SubBytes)
   
2. 
   S matritsasi satrini har hil o’lchamda siljitish (ShiftRows)
   
3. 
   S matritsasining har bir ustunidagi ma’lumotlarni almashtirish (MixColumns)
   
4. 
   S matrictsasi bilan raund kaliti qo’shish (AddRoundKey)