Kriptografiyaning matematik asosi(rsa) shifrlash algoritmi

12-MAVZU: AES-128 blokli shifrlash algoritmining matematik asosi
AES algoritmida baytlar ustida amallar bajariladi. Baytlar (2 ) 8 GF chekli maydon elementlari sifatida qaraladi. (2 ) 8 GF maydon elementlarini darajasi 7 dan katta bo‘lmagan ko‘phad sifatida tasvirlash mumkin. Agarda baytlar {a7a6a5a4a3a2a1a0}, ai {0,1},i  0...7 , ko‘rinishda tasvirlangan bo‘lsa, u holda maydon elementlari quyidagicha ko‘phad ko‘rinishda yoziladi: 1 0 2 2 3 3 4 4 5 5 6 6 7 a7  x  a  x  a  x  a  x  a  x  a  x  a  x  a . Misol uchun {11010101} baytga 0 7 6 4 2 x  x  x  x  a ko‘rinishdagi ko‘phad mos keladi. CHekli (2 ) 8 GF maydon elementlari uchun additivlik va mulьtiplikativlik xossalariga ega bo‘lgan qo‘shish va ko‘paytirish amallari aniqlangan. Ko‘phadlarni qo‘shish AES algoritmida ko‘phadlarni qo‘shish  (XOR) (berilgan ko‘phadlarga mos keluvchi ikkilik sanoq tizimidagi sonlarning mos bitlarini mod 2 bo‘yicha qo‘shish) amali orqali bajariladi. Masalan, x  x  x  x  x 7 6 4 2 va 1 7 5 3 x  x  x  x  ko‘phadlar natijasi quyidagicha hisoblanadi: (     )  7 6 4 2 x x x x x ( 1) ( 1) 7 5 3 6 5 4 3 2 x  x  x  x   x  x  x  x  x  Bu amal ikkilik va o‘n oltilik sanoq sistemalarida quyidagicha ifodalanadi: 2 2 2 {11010110} {10101011} {01111101} va D616  AB16  7D16 . 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 16 {00} qaraladi. (2 ) 8 GF maydonda aa  0 tenglik o‘rinli.
Ko‘phadlarni ko‘paytirish
AES algoritmida ko‘phadlarni ko‘paytirish quyidagicha amalga oshiriladi: –ikkita ko‘phad o‘nlik sanoq tizimida ko‘paytiriladi; – yettinchi darajadan katta bo‘lgan har qanday ko‘phadni sakkizinchi darajali 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 tizimida, yuqorida keltirilgani kabi,  amali asosida bajariladi. SHunday qilib kiritilgan ko‘paytirish amali  bilan belgilanadi. Masalan, ( 1) 6 4 2 x  x  x  x  va ( 1) 7 x  x  ko‘phadlar quyidagicha ko‘paytiriladi: - bu ko‘phadlar o‘nlik sanoq tizimida ko‘paytiriladi ( 1) ( 1) ( 1) 6 4 2 7 1 3 1 1 9 8 6 5 4 3 x  x  x  x   x  x   x  x  x  x  x  x  x  x  ; - natija ( ) 1 8 4 3  x  x  x  x  x  keltirilmaydigan ko‘phadga bo‘linadi va qoldiq olinadi .( 1) mod ( 1) ( 1) 1 3 1 1 9 8 6 5 4 3 8 4 3 7 6 x  x  x  x  x  x  x  x  x  x  x  x   x  x  . Haqiqatan ham (        1)  (  )  1 3 1 1 9 8 6 5 4 3 5 3 x x x x x x x x x x ( 1) ( 1) 8 4 3 7 6  x  x  x  x   x  x  . Har qanday nolga teng bo‘lmagan element uchun a 1  a , tenglik o‘rinli. (2 ) 8 GF maydonda bir element sifatida 16 {01} tushuniladi.Kiritilgan ko‘paytirish amali umumiy holda quyidagicha bajariladi. Ixtiyoriyettinchidarajali a7x 7+a6 x 6+ a5 x 5+ a4 x 4+ a3 x 3+ a2 x 2+a1x+ a0 ko‘phadni x ga ko‘paytirib, quyidagiga ega bo‘lamiz a7x 8+a6 x 7+ a5 x 6+ a4 x 5+ a3 x 4+ a2 x 3+ a1x 2+ a0 x. Bu ko‘phadni x = x 8+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 = x 8+x4+x3+x+1 ko‘phadni yuqorida olingan sakkizinchi darajali ko‘phaddan XOR amali bilan ayirishkifoya, ya’ni : (a71)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 (a71)x8 =(11)x8 =0. Agarda a7=0 bo‘lsa, u holda natija: a6 x 7+…+a1x 2+ a0 x ko‘phadning o‘zi bo‘ladi
Ko‘paytirish amali quyidagicha amalga oshiriladi. Ikkita to‘rt baytli so‘zlar mos ko‘phadlar bilan ifodalangan bo‘lsin: a(x) = a3 x 3+ a2 x 2+a1x+ a0 ib(x) = b3 x 3+ b2 x 2+b1x+b0 . Ko‘paytirish natijasi oltinchi darajadan katta bo‘lmagan ko‘phad a(x) b(x) = s(x)= c6 x 6+ c5 x 5+c4 x 4+ c3 x 3+ c2 x 2+c1x+ c0 , bo‘lib, bu yerda 0 a0 b0 c   , c1=a1•b0a0•b1 , c2=a2•b0a1•b1a0•b2 , c3=a3•b0a2•b1a1•b2 a0•b3 , c4 =a3• b1a2•b2 a1•b3 , c5=a3•b2 a2•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) = x 4+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 tizimida, yuqorida keltirilgani kabi,  amali asosida bajariladi. Quyidagi ifoda o‘rinli: x imod (x 4+1)=x i mod 4 . Shunday qilib, a(x) va b(x) ko‘phadlarni  -kupaytmasini ifodalovchi a(x)  b(x) = d(x) = d3 x 3+ d2 x 2+d1x+ d0 , natijaviy d(x) –ko‘phadkoeffitsientlariquyidagichaaniqlanadi: d0=a0•b0 a3•b1 a2•b2a1•b3, d1=a1•b0 a0•b1 a3•b2 a2•b3, d2=a2•b0 a1•b1 a0•b2 a3•b3, d3=a3•b0 a2•b1 a1•b2 a0•b3 .