RC2 Shifrining π Jadvali Qanday Yaratilgan

Ron Rivest tomonidan yaratilgan RC2 shifri uchun ishlatiladigan 256 ta sonli jadvalning yuzaga kelishi va π raqamlaridan foydalanish usuli haqida tushuntirish.

RC2 Shifri va PITABLE Jadvali

RC2 shifri 1980-yillarning oxirida Ron Rivest tomonidan ishlab chiqilgan blok shifri. Bu shifr kalitni uzunroq ichki kalitga aylantirish uchun har bir baytni bir nechta jadval orqali o'tkazadi. Bu jadval 0 dan 255 gacha bo'lgan sonlarni aralashtirgan holda tuzilgan. Har bir RC2 implementatsiyasida bu 256 ta son bir xil bo'lib keladi.

Shunday jadvalda dizayner qandaydir zaiflikni yashira olishi mumkin. Bu shubhalarni oldini olish uchun kriptograflar bunday jadvallarni π kabi ommaviy doimiy sonlardan olinadigan "nothing-up-my-sleeve" sonlaridan foydalanadilar. Bu sonlar faqat o'zlarining kelib chiqish usuli ommaviy bo'lsa ishonchli bo'ladi.

RC2 shifri uchun ishlatiladigan jadval π raqamlaridan olinganligi aytilgan, lekin ushbu usul hech qachon ommaviy bo'lmagan. Rivestning RFC 2268 hujjatida bu jadval "π raqamlaridan olingan 'tasodifiy' baytlar massivi" deb atalgan va usul berilmagan. 1996-yilda shifrning kodi sizib chiqganda, RSA Data Security muhandisi bu jadvalning π raqamlaridan olinganligi haqidagi savolni ommaviy ravishda ko'tardi. Bu savolga javob kelmagan va ba'zi implementatsiyalar, masalan, LibTomCrypt, hali ham bu jadvalning π raqamlaridan olinganligi haqidagi izohni saqlab kelmoqda.

Jadvalning Yaratilishi

Jadvalning yuzaga kelishi uchun Fisher–Yates aralashtirish usuli ishlatilgan. Bu usul 256 ta kartani 0 dan 255 gacha raqamlangan holda tartiblab, har bir kartani tasodifiy tanlangan kartaga almashtirishni takrorlaydi. Bu aralashtirishda tasodifiy sonlar manbai π raqamlaridir. Har bir tanlov uchun 3 ta raqam o'qiladi va natijani buzilishi mumkin bo'lgan tanlovlar rad etiladi.

PITABLE jadvali birinchi 3 raqamdan boshlanadi, ikkinchi jadval esa toʻrtta raqam keyin boshlanadi. Rivestning MD2 hash funksiyasi shu aralashtirish usulidan foydalanadi, lekin har bir tanlov uchun o'qiladigan raqamlar soni o'zgaradi. Bu sababli bu bog'liq bo'lishi e'tirof etilmagan.

Bu usul RC2 jadvalini aniq takrorlay oladi, lekin Rivest bu qoidaga qanday kelganligi haqida hech qanday hujjat mavjud emas. Bu savol 1996-yilda ommaviy ravishda ko'tarilgan, lekin hech qachon javob kelmagan.

Jadvalni Tasdiqlash

Bu aralashtirish usuli RFC 2268 hujjatidagi PITABLE jadvalini aniq takrorlay oladi. Bu usul 828 ta raqamdan foydalanadi va 21 ta tanlov rad etiladi. Bu jadvalni takrorlash uchun boshqa usullar ham sinab ko'rilgan, lekin hech qanday boshqa usul aniq takrorlashga erishmagan.

Masalan, hexadecimal raqamlaridan foydalanish usuli ham sinab ko'rilgan, lekin bu usul aniq takrorlashga erishmagan. Bu usul Google AI Overview tomonidan ham tavsiflangan, lekin bu usul aniq takrorlashga erishmagan.

Bu jadvalni takrorlash uchun boshqa implementatsiyalar ham ishlatilgan. Ikkinchi implementatsiya RFC hujjatidan va qoidaning qisqa tavsifi asosida yozilgan, birinchi implementatsiyaga kirish bo'lmagan. Uchinchi implementatsiya o'zining π hisoblash usulidan va RFC hujjatining yangi nusxasidan foydalanib, jadvalni takrorlashga erishgan.

input: d = 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, …
       (decimal digits of π)

rand(n):
  loop
    x ← next three digits of d   // 0…999
    if x < n · ⌊1000 / n⌋:
      return x mod n
    // otherwise discard x

S ← [0, 1, …, 255]
for i ← 2 to 256:
  j ← rand(i)
  swap S[j], S[i − 1]
return S                // = PITABLE

Ikkinchi Jadval

RFC 2268 hujjatining 6-bo'limida ikkinchi permutatsiya 0 dan 255 gacha bo'lgan sonlar, RFCning Table[] deb ataladi. Bu jadval RC2-CBC uchun ishlatiladigan RC2Version parametrini kodlaydi va RFC faqat bu jadval kalit kengaytirish bosqichida ishlatiladigan jadval emasligini aytdi. Bu jadval π raqamlaridan boshlangan birinchi jadvalga qaraganda beshinchi raqamdan boshlanadi (5926…). Bu jadval ham 256 ta pozitsiyada aniq takrorlanadi va 828 ta raqamdan foydalanadi, 21 ta tanlov rad etiladi.

Shu tarzda RFC hujjatidagi ikkala jadval ham bir generator orqali ikki boshlang'ich nuqtadan boshlab yaratilishi mumkin.

Asl manba: khalidhamadeh.com