AES kriptoalgoritmining matematik asosi




Download 0,58 Mb.
bet10/14
Sana18.05.2024
Hajmi0,58 Mb.
#242148
1   ...   6   7   8   9   10   11   12   13   14
Bog'liq
Al-xorazmiy nomidagi tîshkånt aõbîrît

AES kriptoalgoritmining matematik asosi


AES algoritmida baytlar ustida amallar bajariladi. Baytlar GF (28 ) chekli

maydon elementlari sifatida qaraladi. GF (28 ) maydon elementlarini darajasi 7 dan katta


bo‘lmagan ko‘phad sifatida tasvirlash mumkin. Agarda baytlar


{a 7 a 6 a 5 a 4 a 3 a 2 a1 a 0 }, ai  {0,1}, i  0 ... 7


ko‘rinishda tasvirlangan bo‘lsa, u holda maydon elementlari quyidagicha ko‘phad ko‘rinishda yoziladi:

7 6 5 4 3 2 1 0
a x 7a x 6a x 5a x 4a x 3a x 2a x a



Misol uchun {11010101 }
baytga
x 7x 6x 4x 2a
ko‘rinishdagi ko‘phad mos keladi.



0
Chekli
GF (28 )
maydon elementlari uchun additivlik va multiplikativlik

xossalariga ega bo‘lgan qo‘shish va ko‘paytirish amallari aniqlangan.


AES algoritmida ko‘phadlarni qo‘shish  (XOR) (berilgan ko‘phadlarga mos keluvchi ikkilik sanoq sistemasidagi sonlarni mos bitlarini mod 2 bo‘yicha qo‘shish) amali orqali bajariladi. Masalan

x 7x 6x 4x 2x
hisoblanadi:
va x 7x 5x 3x  1
ko‘phadlar natijasi quyidagicha

( x 7x 6x 4x 2x)  ( x 7x 5x 3x  1)  ( x 6x 5x 4x 3x 2  1)


Bu amal ikkilik va o‘n oltilik sanoq sistemalarida quyidagicha ifodalanadi:

{11010110


} 2  {10101011
} 2  {01111101 } 2
va D 616 AB 16
 7 D16

Chekli maydonda istalgan nolga teng bo‘lmagan a element uchun unga teskari

bo‘lgan a
element mavjud va


a  ( a )  0
tenglik o‘rinli, bu erda nol elementi sifatida


{00 }16
qaraladi. GF (28 ) maydonda
a a  0 tenglik o‘rinli.

AES algoritmida ko‘phadlarni ko‘paytirish quyidagicha amalga oshiriladi:

  • ikkita ko‘phad o‘nlik sanoq sistemasida ko‘paytiriladi;

  • ettinchi darajadan katta bo‘lgan har qanday ko‘phadni sakkizinchi darajali

 ( x ) = x 8x 4x 3x  1 keltirilmaydigan ko‘phadga bo‘lganda qoldiqda etti


va undan kichik bo‘lgan darajadagi ko‘phadlar hosil bo‘lib, ular natija sifatida olinadi, bunda bo‘lish jarayonida bajariladigan ayirish amali ikkilik sanoq sistemasida, yuqorida keltirilgani kabi,  amali asosida bajariladi.
Ana shunday qilib kiritilgan ko‘paytirish amali bilan belgilanadi.

Masalan,
( x 6x 4x 2x  1)
va ( x 7x  1)
ko‘phadlar quyidagicha ko‘paytiriladi:




  • bu ko‘phadlar o‘nlik sanoq sistemasida ko‘paytiriladi

( x 6x 4x 2x  1)  ( x 7x  1)  ( x 13x 11x 9x 8x 6x 5x 4x 3  1) ;



  • natija  ( x)  x 8x 4x 3x  1 keltirilmaydigan ko‘phadga bo‘linadi va qoldiq

olinadi
( x 13x 11x 9x 8x 6x 5x 4x 3  1) mod


( x 8x 4x 3x  1)  ( x 7x 6  1) .


Haqiqatan ham
( x 13x 11x 9x 8x 6x 5x 4x 3  1)  ( x 5x 3 ) 




  • ( x 8x 4x 3x  1)  ( x 7x 6  1) .

Har qanday nolga teng bo‘lmagan element uchun a 1 a , tenglik o‘rinli. GF (28 )

16
maydonda bir element sifatida {01} tushiniladi.
Kiritilgan ko‘paytirish amali umumiy holda quyidagicha bajariladi. Ixtiyoriy ettinchi darajali
a7x7+ a6 x6+ a5 x5+ a4 x4+ a3 x3+ a2 x 2+a1x+ a0
ko‘phadni x ga ko‘paytirib, quyidagiga ega bo‘lamiz
a7x8+ a6 x7+ a5 x6+ a4 x5+ a3 x4+ a2 x3+ a1x2+ a0 x.
Bu ko‘phadni  x  = x8+x4+x3+x+1=1{1b} modul bo‘yicha hisoblab, chekli
GF(28) maydonga tegishli elementni hosil qilamiz. Buning uchun a7 =1 bo‘lganda x
= x8+x4+x3+x+1 ko‘phadni yuqorida olingan sakkizinchi darajali ko‘phaddan XOR
amali bilan ayirish kifoya, ya'ni :
(a71) x8+ ( a6  0) x7+( a5  0) x6+( a 4  0) x5+( a3 1) x 4 +( a2 1) x3 +
+ ( a1  0)x2+ (a0 1) x+1=( a6  0) x7+( a5  0) x6+( a 4  0) x5+
+( a3 1) x 4 +( a2 1) x3 + ( a1  0)x2+ (a0 1) x+1,
bu erda a7 =1 bo‘lgani uchun
(a71) x8 =(11) x8 =0.
Agarda a7 =0 bo‘lsa, u holda natija: a6 x7+…+a1x2+ a0 x ko‘phadning o‘zi bo‘ladi.
Ushbu x time ( ) funksiya yuqorida kiritilgan ko‘paytirish amaliga nisbatan berilgan ko‘phadni x ga ko‘paytirishni ifodalasin. Shu funksiyani n marta qo‘llab xn ga ko‘paytirish amali aniqlanadi. Bevosita hisoblash bilan quyidagilarni o‘rinli ekanligiga ishonch hosil qilish mumkin:
{57} {13} = {fe},
chunki

Bundan
{57}  {02}= x time ({57})={ae}
{57}  {04}= x time ({ae})={47}
{57}  {08}= x time ({47})={8e}
{57}  {10}= x time ({8e})={07},
{57}  {13}={57}  ({01}{02}{10})={57}{ae}{07}={fe}.

Yuqorida ta'kidlanganidek algoritm akslantirishlari baytlar va to‘rt baytli so‘zlar bilan (ustida) bajariladi. To‘rt baytli so‘zlarni koefisentlari GF(28) chekli maydondan olingan darajasi uchdan katta bo‘lmagan ko‘phadlar ko‘rinishida ifodalash mumkin:
a(x) = a3 x3+ a2 x 2+a1x+ a0 ,

bu erda
a  (a i a i a i a i a i a i a i a i ) , a i 0;1 , i=0,1,2,3; j=0, 1, …,7.

i 7 6 5 4 3 2 1 0 j

Bunday ikkita ko‘phadlarni qo‘shish o‘xshash hadlari oldidagi koeffisientlarni


 amali bilan qo‘shish orqali amalga oshiriladi, ya'ni:


a(x)+b(x)= (a3 b3 ) x3+ (a2b2) x 2+(a1 b1) x+ (a0b0).


Ko‘paytirish amali quyidagicha amalga oshiriladi. Ikkita to‘rt baytli so‘zlar mos ko‘phadlar bilan ifodalangan bo‘lsin:
a(x) = a3 x3+ a2 x 2+a1x+ a0 i b(x) = b3 x3+ b2 x 2+b1x+b0 .

Ko‘paytirish natijasi oltinchi darajadan katta bo‘lmagan ko‘phad


a(x) b(x) = s(x)= c6 x6+ c5 x5+c4 x4+ c3 x3+ c2 x 2+c1x+ c0 ,

bo`lib bu yerda
c a b , c1=a1•b0 a0•b1 , c2=a2•b0a1•b1a0•b2 ,




0 0 0
c3=a3•b0a2•b1a1•b2a0•b3 , c4 =a3• b1a2•b2a1•b3 , c5=a3•b2a2•b3 , c6=a3•b3

.
Ko‘paytirish natijasi to‘rt baytli so‘zdan iborat bo‘lishi uchun, uchinchi
darajadan katta bo‘lgan har qanday ko‘phadni to‘rtinchi darajali  ( x ) = x4+1

keltirilmaydigan ko‘phadga bo‘lganda qoldiqda uchinchi va undan kichik bo‘lgan darajadagi ko‘phadlar hosil bo‘lishini hisobga olgan holda, ular natija sifatida olinadi, bunda bo‘lish jarayonida bajariladigan ayirish amali ikkilik sanoq sistemasida, yuqorida keltirilgani kabi,  amali asosida bajariladi.


Quyidagi ifoda o‘rinli: xi mod (x4+1)=xi mod 4 .
Shunday qilib, a(x) va b(x) ko‘phadlarni  -ko`paytmasini ifodalovchi
a(x)  b(x) = d(x) = d3 x3+ d2 x 2+d1x+ d0 ,
natijaviy d(x) –ko‘phadning koefisientlari quyidagicha aniqlanadi:
d0=a0•b0a3•b1a2•b2a1•b3, d1=a1•b0a0•b1a3•b2a2•b3, d2=a2•b0a1•b1a0•b2a3•b3, d3=a3•b0a2•b1a1•b2a0•b3 .
Yuqorida keltirilgan amallarni matrisa ko‘rinishida quyidagicha ifodalash mumkin:

d 0 a 0 a 3 a 2 a1 b0


d a a a a b


b

a
1 1 0 3
2 1


2

a
d a a
2 1 0
 

2
3

   
d 3 a 3 a 2 a1 a 0 b3
Kvadrat arxitekturaga ega AES blokli shifrlash algoritmi o‘zgaruvchan uzunlikdagi kalitlar orqali shifrlanadi. Kalit va blok uzunliklari bir – biriga bog‘liq bo‘lmagan holda 128, 192 yoki 256 bit bo‘ladi. Biz mazkur o‘quv qo‘llanma ishida AES shifrlash algoritmini bloklar uzunligi 128 bit bo‘lgan holi uchun ko‘rib chiqamiz. Blok o‘lchami 128 bitga teng kirish , bu 16 baytli massiv 4 ta qator va 4 ta ustundan iboratdir (har bir satr va har bir ustun bu holda 32 razryadli (bitli) so‘z deb
qaraladi.)
Shifrlash uchun kirayotgan ma'lumot baytlari:
s00 , s10 , s20 , s30 , s01 , s11, s21, s31, s02 , s12 , s22 , s32 , s03 , s13 , s23 , s33 ,
ko‘rinishida belgilanadi. [4]

Kirayotgan ma'lumot quyidagi 1–jadvaldagi kvadrat massiv ko‘rinishida kiritiladi. Ya'ni, baytlarni tartib bilan ustun bo‘yicha to‘ldirib boriladi. Birinchi to‘rtta bayt (s00 , s10 , s20 , s30) birinchi ustunga mos tushadi, ikkinchi to‘rtta bayt
(s01 , s11, s21, s31) ikkinchi ustunga mos tushadi, uchinchi to‘rtta bayt (s02 , s12 , s22 , s32) uchinchi ustunga mos tushadi, to‘rtinchi to‘rtta bayt (s03 , s13 , s23 , s33) to‘rtinchi ustunga mos tushadi.
1.1-jadval
Kirayotgan ma'lumotlarning holat jadvali



s00

s01

s02

s03

s10

s11

s12

S13

s20

s21

s22

s23

s30

s31

s32

s33

Xuddi shunday tartibda shifrlash kaliti ham kvadrat jadval shaklida kiritiladi.


Ular 128 bit = 16 bayt = 4 so‘z (to‘rtta 32 bitlik blok) dan iborat:
k00 ,k10 , k20 , k30 , k01 , k11, k21, k31, k02 , k12 , k22 , k32 , k03 , k13 , k23 , k33 .
1.2- jadval
Shifrlash kaliti holat jadvali.



K00

k01

k02

k03

K10

k11

k12

k13

K20

k21

k22

k23

K30

k31

k32

k33

Shuningdek, AES shifrlash algoritmi raundlar soni Nr , kirish bloklar o‘lchami


Nb va kalit uzunligi Nk larga bog‘liq holda quyidagi 3-jadvalga mos holda qo‘llaniladi.
1.3-jadval
AES shifrlash algoritmi raundlar



Nr

Nb=4
128 bit

Nb=6
192 bit

Nb=8
256 bit

Nk=4
128 bit

10

12

14

Nk=6
192 bit

12

12

14

Nk=8
256 bit

14

14

14




Download 0,58 Mb.
1   ...   6   7   8   9   10   11   12   13   14




Download 0,58 Mb.

Bosh sahifa
Aloqalar

    Bosh sahifa



AES kriptoalgoritmining matematik asosi

Download 0,58 Mb.