Tayyorladi: Tursunov Axmat, Tuxtayev Turon, Umirzoqov Ahror

Salsa20

MUSTAQIL ISH

Tayyorladi: Tursunov Axmat, Tuxtayev Turon, Umirzoqov Ahror

Toshkent 2022

Mavzu: SALSA20 oqimli shifrlash algoritmi va uning kriptotahlili.
Reja:

1. 
   SALSA20 Yaratilish tarixi.
   
2. 
   SALSA20 xususiyatlari.
   
3. 
   SALSA20 algoritmi.
   
4. 
   Foydalanilgan adabiyotlar
   

Daniel Julius Bernstein ( djb nomi bilan tanilgan, 1971 yil 29 oktyabrda tug'ilgan) - amerikalik nemis matematik , kriptolog va kompyuter olimi . U Bochum Ruhr universitetidagi CASA [2] bo’limi professori , shuningdek Chikagodagi Illinoys universitetida kompyuter fanlari bo‘yicha tadqiqotchi professori. Bungacha u Eyndxoven texnologiya universitetining matematika va informatika kafedrasi professori edi .
eSTREAM keng tarqalgan foydalanish uchun mos keladigan yangi oqim shifrlarini aniqlash uchun Yevropa Ittifoqi tomonidan tashkil etilgan loyihadir.
U NESSIE loyihasida taklif qilingan barcha 6 shifrni buzgandan keyin boshlangan. Algoritmlarni qabul qilish shartlari birinchi marta 2004 yilda nashr etilgan. 2008 yil aprel oyida tanlov yakunlandi. Loyiha bir necha ketma-ket bosqichlarga bo'lingan bo'lib, uning maqsadi turli xil foydalanish holatlariga mos keladigan shifrlash algoritmlarini topish edi.
Salsa20 'qo'shimcha oqim shifridir, aniqrog'i dizayn printsipiga amal qiladigan qo'shimcha oqim shifrlari oilasiga mansub. U dastlab Den Bernshteyn tomonidan ishlab chiqilgan va 2005 yilda eSTREAM loyihasiga taqdim etilgan.
Uning maqsadi pochta tizimlari orqali uzatiladigan ma'lumotlarni shifrlash bo'yicha Evropa standartlarini yaratish edi. Algoritm birinchi profil (yuqori o‘tkazuvchanlikka ega dasturiy ilovalar uchun oqim shifrlari) bo‘yicha tanlov g‘olibiga aylandi.
O'shandan beri u ko'plab Internet xavfsizligi protokollari va ilovalarida keng qo'llanilgan. Uning asosiy afzalliklari - apparat yoki dasturiy ta'minotni amalga oshirishda soddaligi va samaradorligi. Oddiy dasturiy ta'minotni amalga oshirishda, masalan, Salsa 20 o'tkazuvchanligi oqimli shifrlangan RC4 o'tkazuvchanligidan taxminan besh baravar katta. Yuqorida aytib o'tilganidek, Salsa20 noncesdan foydalanadi va shuning uchun kalitni vaqti-vaqti bilan yangilab turish unchalik muhim emas. Ushbu maqola yozilgunga qadar, Salsa20/20 va Salsa20/12 (ya'ni, Salsa20 ning atigi 12 raundli qisqartirilgan versiyasi) ga qarshi hech qanday nashr etilgan hujumlar mavjud emas. Eng mashhur hujum Salsa 20/8 ni buzishga qodir (ya'ni, Salsa20 ning 8 raundli qisqartirilgan versiyasi), ammo bu hujum amaliydan ko'ra nazariy jihatdan qiziqroq.
Salsa20 64 baytli (yoki 512 bitli) ma'lumotlar bloklarida ishlaydi, ya'ni bir bosqichda qayta ishlangan ochiq matn yoki shifrlangan matn birligi 64 bayt uzunlikda bo'ladi. Salsa20 ning shifrlash funksiyasi quyidagicha ifodalanishi mumkin:

C=E_k(m,n)=Salsa20_k^shifrlash(m,n)=mSalsa20_k^kengaytirish(n)

Ushbu iborada Salsa20^encrypt Salsa20 shifrlash funksiyasiga ishora qiladi, Salsa20^expand esa uning kengaytirish funktsiyasiga ishora qiladi. Ikkala funktsiya ham k harfi bilan (bu odatda 32 bayt uzunlikdagi) tugmachalarga ega bo’lgan 8 baytli nonce n dan foydalanadi. Oddiylik uchun biz Salsa20 shifrlash va kengaytirish funksiyalarini farqlamaymiz va biz Salsa20 atamasini ulardan biriga murojaat qilish uchun ishlatamiz.
Salsa 20 shifrlash funksiyasi va kengaytirish funksiyalaridan tashqari, 64 baytlik z argumentini oladigan va uni 64 baytlik Salsa 20 chiqish qiymatini xesh qiluvchi Salsa20 xesh funksiyasi ham mavjud. Shunday qilib, Salsa20 xesh funksiyasi argumentni siqmaydi va kengaytirmaydi, lekin uni kriptografik xesh funksiyasi (ya’ni, “oddiy” kriptografik xesh funksiyasi bilan bir xil xususiyatlarga ega, masalan, psevdor tasodifiylik) deb hisoblash mumkin. Biz Salsa20 xesh, kengaytirish va shifrlash funksiyalarini keyingi tartibda kiritamiz.
Xesh funktsiyasi
Salsa20 xesh funktsiyasi so'zga yo'naltirilgan, ya'ni 4 bayt yoki 32 bit qiymatlarga ishora qiluvchi so'zlar ustida ishlaydi.
U so'zlar ustida uchta asosiy amalni qo'llaydi:
Ikki so'zdan iborat qo'shilish moduli 2³² w₁ va w₂, w₁+ w₂ sifatida belgilanadi.
w₁ va w₂ ning qo'shilish moduli 2 (XOR) w₁  w₂ sifatida belgilanadi.
w so'zining c-bit chapga aylanishi, w>>>c sifatida belgilanadi
c>=0;
Misol uchun, 0x77777777+0x01234567=0x789ABCDE, 0x010203040x789ABCDE=0X7998BFDA, va 0x7998BFDA>>>7=01111001100110001011111111011010>>>7=11001100010111111110110100111100 = OxCC5Fed3C. Asosan ishlashiga ko'ra, Salsa20 xesh funktsiyasi faqat c (chapga aylantirish operatsiyasida) uchun doimiy qiymatlardan foydalanadi, so'zlarni ko'paytirishni va jadvalni qidirishni chaqirmaydi.
Salsa20 xesh funksiyasi quyidagi yordamchi funksiyalarda qurilish bloklari sifatida uchta asosiy operatsiyadan foydalanadi:
y 4 so‘zdan iborat yo 4 so‘zli qiymat bo‘lsin y_1, y₂ va y₃;
bu y = (y₀ y₁ y₂ y₃). Bu y 4*32 = 128 bit uzunligini anglatadi. Choraklik funksiya quyidagicha aniqlanadi quarterround(y) = z = (z₀ z₁ z₂ z₃) sifatida aniqlanadi.
z₁₌y₁((y₀ +y₃)<<<7)
z₂=y₂((z₁+y₀)<<<9)
z₃=y₃((z₂+ z₁)<<<13)
z₀=y₀((z₃ +z₂)<<<18)
Chorak funksiyasi y ning 4 ta so’zini joyida o’zgartiradi; ya'ni y₁- z₁ ga o'zgartiriladi, y₂ - z₂ ga, y₃- z₃ ga,va nihoyat y₀-z₀ ga o'zgartiriladi. U "choraklik funksiya" deb ataladi, chunki u faqat 4 ta so'zda ishlaydi, Salsa20 esa ishlaydi 16 so'z (esda tutingki, 4-16 ning chorak qismidir).

y 16 so‘zli qiymat (y₀, y₁, y₂, … y₁₅) bo‘lsin, u quyidagicha ifodalanishi mumkin.

Kvadrat matritsa

Qator funksiya y ni kiritish sifatida qabul qiladi va yuqorida aytib o‘tilgan choraklik funksiya yordamida matritsa qatorlarini parallel ravishda o‘zgartiradi. Aniqroq aytganda, u 16 so'zli chiqish qiymatini hosil qiladi z=rowround(y)=(z₀, z₁, z₂, … z₁₅) ,

Bu shuni anglatadiki, har bir satr alohida (boshqa qatorlardan mustaqil ravishda) qayta ishlanadi va har bir satrning to'rtta so'zi o'ziga xos tarzda almashtiriladi. Aslida, i qatordagi so'zlar (1 < i < 4 uchun) i – 1 pozitsiyalari uchun chapga aylantiriladi.
Bu shuni anglatadiki, birinchi qatordagi so'zlar umuman almashtirilmaydi, ikkinchi qatordagi so'zlar bir pozitsiya uchun chapga, uchinchi qatordagi so'zlar chapga ikki pozitsiyaga, to'rtinchi qatordagi so'zlar esa chapga aylantiriladi. choraklik funktsiyasi qo'llanilishidan oldin uchta pozitsiyaga qoldiriladi.
Qatorda aylanish funksiyasiga oʻxshab, ustunli funksiya 16 soʻz qiymatini oladi (y₀, y₁, y₂, ..., y₁₅) va z = columnround(y) = (z₀, z₁, z₂, …z₁₅) ga koʻra 16 soʻzli chiqish hosil qiladi.

Ustunli funksiya qaysidir ma'noda qatorli aylanish funksiyasini ko'chirishdir; ya'ni a ni to’ldirish orqali matritsa ustunlarini parallel ravishda o'zgartiradi choraklik funksiya orqali har bir ustunni almashtiradi.
Qator va ustunli funksiyalar ikki bosqichda birlashtirilishi mumkin funktsiyasi. Aniqroq qilib aytadigan bo'lsak, doubleround funksiyasi ustunli funksiya bo'lib, undan keyin qatorli funksiya mavjud. Shunday qilib, u 16 so'zdan iborat ketma-ketlikni oladi va boshqa 16 so'zli ketma-ketlikni chiqaradi. Agar y = (y₀, Y₁, Y₂, ...y₁₅) kirish boʻlsa, u holda
Z = (z₀ ,z₁ ,z₂ , …. z₁₅)
= doubleround(y)
=rowround(columnround(y)) tegishli chiqishdir.
Bu shuni anglatadiki, doubleround funktsiyasi birinchi navbatda kirish ustunlarini parallel ravishda o'zgartiradi va keyin parallel ravishda qatorlarni o'zgartiradi.
Bu, o'z navbatida, har bir so'z ikki marta o'zgartirilganligini anglatadi. Nihoyat, littleendian funksiyasi so'z yoki 4 baytlik ketma-ketlikni kodlaydi b =(b₀, b₁, b₂, b₃) o’z-endian tartibda (b₃, b₂, b₁, b₀) b₃*2²⁴+b₂*2¹⁶ + b₁*2⁸ + b₀ qiymatini ifodalaydi. Bu qiymat, o'z navbatida, odatda o'n oltilik tizimda yoziladi.
Masalan, littleendian(86, 75, 30, 9) = (9, 30, 75, 86) represents 0x091E4B56 sifatida yozilishi mumkin bo'lgan 9*2²⁴ +30*2¹⁶ +75*2⁸ +86 ni ifodalaydi. Littlendian funksiyasi teskari bo'lishi mumkinligini aytishga hojat yo'q, shuning uchun
littleendian^-1(0x091E4B56) = (86,75, 30,9). Hammasini jamlagan holda, Salsa20 xesh-funksiyasi 64 baytlik ketma-ketlikni x = (x[0], x[1],....x[63]) kiritadi va yana 64 baytlik Salsa 20(x) = xdoubleround¹⁰(x) ketma-ketligini chiqish sifatida hosil qiladi. Kiritish ketma-ketligi x 16 ta soʻzdan iborat.

u holda chiqish Salsa 20(x) xesh-funktsiyasi 16 ta soʻzning birikmasi boʻlib, ular quyidagicha hosil boʻladi:
littlendian^-1(z₀ +y₀)
littlendian^-1(z₁ +x₁)
….
littlendian '(z₁₅+x₁₅);
Salsa20 ning 20 raundlari ikki tomonlama funksiya 10 marta takrorlanganligidan kelib chiqadi va har bir iteratsiya asosan ikkita turni ifodalaydi, biri ustunli funksiya uchun, ikkinchisi esa qatorli funksiya uchun turadi.
Kengaytirish funktsiyasi
Nomidan ko'rinib turibdiki, Salsa20 kengaytirish funksiyasining maqsadi 32 yoki 16 bayt kalit va doimiy 16 baytdan foydalangan holda 16 baytlik kirish n ni 64 baytlik chiqishga kengaytirishdir. Kalit 32 yoki 16 baytdan iboratligiga qarab, doimiy baytlar va tegishli kengaytirish funktsiyalari biroz farq qiladi.
Agar kalit 32 baytdan iborat bo'lsa, u holda ikkita 16 baytli k₀ va k₁ tugmachalarini ifodalovchi ikki qismga bo'linadi. Bunday holda, doimiy baytlar quyidagicha ko'rinadi (bu erda har bir  qiymati littleendian funksiyasi yordamida kodlangan to'rt baytdan iborat):
₀ = (101, 120, 112, 97)=0x61707865
₁ = (110, 100, 32, 51)=0x3320646E
₂ = (50, 45, 98, 121)=0x79622D32
₃ = (116, 101, 32, 107)=0X6B206574
Keyin Salsa20 kengaytirish funksiyasi quyidagicha aniqlanadi:

E'tibor bering, littleendian(₀) = littleendian(101, 120,112,97) = 0x61707865, shuning uchun Salsa20 xesh funksiyasiga bo'ysunadigan argument to'rt bayt bilan boshlanadi, 0x61,0x70, 0x78 va 0x65.
Kalit 16 baytdan iborat bo'lsa, u holda bu ikki marta qo'llaniladigan bitta 16 baytli k kalitni ifodalaydi. Bunday holda, 4 baytli  konstantalarining biroz boshqacha to'plami ishlatiladi
₀ = (101, 120, 112, 97)
₁= (110, 100, 32, 49)
₂= (54, 45, 98, 121)
₃= (116, 101, 32, 107)
bu yerda tegishli o konstantalardan farq qiluvchi ikki bayt tagiga chizilgan holda belgilanadi. Bunday holda, Salsa 20 kengaytirish funktsiyasi sifatida aniqlanadi

Ikkala holatda ham  va  doimiy c sifatida qarash mumkin, k kalit, n esa Salsa20 kengaytirish funksiyasining argumenti sifatida qaralishi mumkin. Demak, funktsiyaga kiritilgan ma'lumotlarni yozish mumkin ma'lum bir matritsa tartibi:

Shubhasiz, bu tartib biroz o'zboshimchalik bilan va o'z xohishiga ko'ra o'zgartirilishi mumkin. Keyinchalik tushuntirilganidek, ChaCha20 Salsa 20 ning boshqa matritsa tartibidan foydalanadigan variantidir.
Shifrlash funktsiyasi
Salsa20 qo'shimcha oqim shifridir, ya'ni tegishli o'lchamdagi kalit oqimi yaratiladi va ochiq matnli xabarga modul 2 qo'shiladi. Salsa20 kengaytirish funksiyasi kalit oqimini yaratish uchun ishlatiladi. Aniqroq qilib aytganda, k 32 yoki 16 baytli kalit bo'lsin. n 8 baytlik bo'lgan va m shifrlanadigan l baytli ochiq matnli xabar (bu erda 0 <= l <= 2⁷⁰), k kalit ostida nonce n bilan m ning Salsa20 shifrlanishi Salsa20_k (m, n) sifatida belgilanadi. U mSalsa20_k(n') sifatida hisoblanadi, bu erda Salsa20_k(n') uzunligi 2⁷⁰ baytgacha bo'lishi mumkin bo'lgan kalit oqimini ifodalaydi va n' hisoblagich qo'shish orqali n dan olinadi. Shunday qilib, kalit oqimi iterativ ravishda quyidagicha tuzilgan:
Salsa20_k(n,0) || Salsa20_k(n,1) || ... | Salsa20_k(n,2⁶⁴ - 1)
Har bir iteratsiyada Salsa20 kengaytma funksiyasi k tugmasi bilan bosiladi va 8 baytlik nonce va 8 baytlik hisoblagichdan iborat 16 baytli kirishga qo'llaniladi. Agar i bit bo'yicha yozilsa: ya'ni, i= (i_{0 ,} i₁, i₂ , ... ,i₇) keyin tegishli hisoblagich i₀+i₁*2⁸ +i₂*2¹⁶ + ... + i₇*2⁵⁶ ni bildiradi. Salsa20 kengaytirish funksiyasining har bir iteratsiyasi 64 = 2 baytni beradi, shuning uchun kalitning maksimal uzunligi Shu tarzda yaratilishi mumkin bo'lgan oqim 2⁶⁴*2⁶ = 2⁷⁰ bayt. O'z-o'zidan ma'lumki, m xabarning 7 baytini shifrlash uchun zarur bo'lganda shuncha bayt ishlab chiqariladi.
Xulosa shuki, Salsa 20 shifrlash funksiyasi quyidagicha ifodalanishi mumkin
c=(c[0], c[1],..., c[l- 1]) = (m[0], m[1],...,m[l-1])Salsa20_k (n')
c[i] = m[i]  Salsa_k(n, [i/64])[i mod 64]
for i = 0,1...., l- 1. Salsa20 qo'shimcha oqim shifrlanganligi sababli, shifrlash va shifrni ochish funktsiyalari asosan bir xil (m va c qarama-qarshi ma'noga ega).
Noncening uzunligi jamiyatda munozarali tarzda muhokama qilinganligi sababli, Bernshteyn Salsa20 ning uzoqroq bo'lmagan holatlarga dosh bera oladigan variantini taklif qildi. Aniqrog'i. XSalsa20²⁶ da'vo qilingan xavfsizlikni kamaytirmasdan, uzunligi 192 bit (64 bit o'rniga) bo'lgan nonces olishi mumkin.

FOYDALANILGAN ADABIYOTLAR:

1. 
   FAST SOFTWARE ENCRYPTION 15th international workshop, FSE 2008 LAUSANNE.
   
2. 
   Google.com