Trivium (shifr)

Trivium shifrlash turining strukturasi

Trivium – bu simmetrik sinxron oqimli shifrlash algoritmi, Birinchi navbatda, tezlik va elementlar soni oʻrtasidagi moslashuvchan muvozanat bilan apparatni amalga oshirishga qaratilgan boʻlib, u dasturiy taʼminotni ancha samarali amalga oshirish imkoniyatiga ega.

Shifr 2008-yil dekabr oyida Yevropa eSTREAM loyihasi portfelining bir qismi sifatida 2-profil (apparatga yoʻnaltirilgan shifrlar) sifatida taqdim etilgan. Shifr mualliflari Kristof De Kannier va Bart Preneldir.

Bu oqim shifriga qadar hosil qiladi $2^{64}$ 80 bitli kalit va 80 bitli IV dan chiqish oqimi biti (boshlash vektori). Bu eSTREAM loyihasining eng oddiy shifridir, u kriptografik barqarorlik nuqtai nazaridan ajoyib natijalarni koʻrsatadi.

Trivium engil oqim shifrlash sifatida ISO/IEC 29192-3 standartiga kiritilgan.

Tavsif

Triviumning boshlangʻich holati umumiy uzunligi 288 bit boʻlgan 3 siljish registridir. Har bir takt sikli siljish registrlaridagi bitlarni oldinga uzatish va qayta aloqaning chiziqli boʻlmagan kombinatsiyasi orqali oʻzgartiradi. Shifrni ishga tushirish uchun kalit K va ishga tushirish vektori IV 3 ta registrdan 2 tasida yoziladi va algoritm 4x288 = 1152 marta bajariladi, bu esa boshlangʻich holatning har bir biti kalitning har bir bitiga va har bir bitga bogʻliqligini kafolatlaydi. ishga tushirish vektorining.

Initsializatsiya bosqichidan oʻtgandan soʻng, har bir siklda Z kalit oqimining yangi aʼzosi hosil boʻladi, u matnning keyingi aʼzosi bilan XOR protsedurasidan oʻtadi. Shifrni ochish protsedurasi teskari tartibda sodir boʻladi – shifrlangan matnning har bir aʼzosi Z kalit oqimining har bir aʼzosi bilan XORlangan.

Algoritm

Oqim shifrlari

Trivium kalit oqimi deb ataladigan Z ketma-ketligini hosil qiladi $N\le 2^{64}$ bit. Xabarni shifrlash uchun xabar va kalitlar oqimini XOR qilish kerak. Shifrni ochish xuddi shunday tarzda amalga oshiriladi, XOR operatsiyasi shifrlangan matn va kalit oqimidan amalga oshiriladi.

Initializatsiya

Algoritm 80 bitli kalit va 80 bitli ishga tushirish vektorini 288 bitli boshlangʻich holatga yuklash orqali ishga tushiriladi. Boshlash quyidagi psevdokod bilan tavsiflanishi mumkin.

$(s_1,s_2,...,s_{93})\leftarrow (K_1,...,K_{80},0,...,0)$

$(s_{94},s_{95},...,s_{177})\leftarrow (I{V}_1,...,I{V}_{80},0,...,0)$

$(s_{178},s_{179},...,s_{288})\leftarrow (0,...0,1,1,1)$

$\text{for}i=1\text{to}4\cdot 288\text{do}$

$t_1\leftarrow s_{66}+s_{91}\cdot s_{92}+s_{93}+s_{171}$

$t_2\leftarrow s_{162}+s_{175}\cdot s_{176}+s_{177}+s_{264}$

$t_3\leftarrow s_{243}+s_{286}\cdot s_{287}+s_{288}+s_{69}$

$(s_1,s_2,...,s_{93})\leftarrow (t_3,s_1,...,s_{92})$

$(s_{94},s_{95},...,s_{177})\leftarrow (t_1,s_{94},...,s_{176})$

$(s_{178},s_{179},...,s_{288})\leftarrow (t_2,s_{178},...,s_{287})$

$\text{end for}$

Boshlash protsedurasi boshlangʻich holatning har bir biti kalitning har bir bitiga va ishga tushirish vektorining har bir bitiga bogʻliqligini taʼminlaydi. Ushbu taʼsir 2 ta toʻliq oʻtishdan keyin (2 * 288 tsiklni bajarish) erishiladi. Yana 2 ta oʻtish bit munosabatlarini murakkablashtirish uchun moʻljallangan. Misol uchun, null kalit va ishga tushirish vektoridan olingan Z kalit oqimining dastlabki 128 bayti taxminan bir xil miqdordagi 1 va 0 ga teng masofada joylashgan. Hatto eng oddiy va bir xil kalitlar bilan Trivium algoritmi tasodifiyga yaqin raqamlar ketma-ketligini hosil qiladi.

Algoritm bilan ishlash

Oqim generatori holatning 3 bitini oʻzgartirish va kalit oqimining 1 bitini hisoblash uchun 288 bitli boshlangʻich holatidan 15 bitdan foydalanadi. $z_i$. Algoritm natijasida, gacha $N\le 2^{64}$ kalit oqimi biti. Algoritmni quyidagi psevdokod bilan tasvirlash mumkin.

$\text{for}i=1\text{to}N\text{do}$

$t_1\leftarrow s_{66}+s_{93}$

$t_2\leftarrow s_{162}+s_{177}$

$t_3\leftarrow s_{243}+s_{288}$

$z_i\leftarrow t_1+t_2+t_3$

$t_1\leftarrow s_{66}+s_{91}\cdot s_{92}+s_{93}+s_{171}$

$t_2\leftarrow s_{162}+s_{175}\cdot s_{176}+s_{177}+s_{264}$

$t_3\leftarrow s_{243}+s_{286}\cdot s_{287}+s_{288}+s_{69}$

$(s_1,s_2,...,s_{93})\leftarrow (t_3,s_1,...,s_{92})$

$(s_{94},s_{95},...,s_{177})\leftarrow (t_1,s_{94},...,s_{176})$

$(s_{178},s_{179},...,s_{288})\leftarrow (t_2,s_{178},...,s_{287})$

$\text{end for}$

Ushbu psevdokodda barcha hisoblar modul 2 boʻyicha amalga oshiriladi. Yaʼni qoʻshish va koʻpaytirish amallari XOR va AND amallaridir.

Davr

Boshlangʻich holat oʻzgarishlarining chiziqli boʻlmaganligi sababli kalit oqim davrini aniqlash qiyin. Agar barcha flip-floplar AND boʻlsa ham, natijada toʻliq chiziqli sxema boʻlsa ham, har qanday kalit juftligi va ishga tushirish vektori buyurtma davri bilan kalit oqimini yaratishga olib kelishini koʻrsatish mumkin. $2^{96-3}-1$ (bu kerakli kalit oqimi uzunligidan allaqachon oshib ketadi $2^{64}$).

Agar Trivium oz sonli iteratsiyalardan soʻng tasodifiy kalit oqimini yarata boshlaydi deb faraz qilsak, u holda barcha hosil qilingan ketma-ketliklar $2^{288}$ aql bovar qilmaydigan boʻladi. Shuningdek, kalit/boshlash vektor juftligidan kamroq muddatga kalit oqimini yaratish ehtimoli $2^{80}$ tartibda boʻladi $2^{-208}$.

Trivium oilaviy shifrlari

Ushbu shifrning modifikatsiyalari siljish registrlari soni va ularning uzunligi bilan farqlanadi.

Univium

Univium oqim shifrlash bitta siljish registridan iborat boʻlib, kodlash uchun faqat registr uzunligidan uzun boʻlmagan kalit kerak boʻladi.

Bivium

Trivium bilan birgalikda uning mualliflari umumiy uzunligi 177 bit boʻlgan atigi 2 ta siljish registrini amalga oshiradigan Bivium shifrini taklif qilishdi. Boshlash jarayoni Triviumga oʻxshaydi. Har bir tsiklda 2 ta holat biti oʻzgartiriladi va kalit oqimining yangi biti hosil boʻladi. Kalit oqimining avlodiga koʻra Z, 2 ta versiya mavjud: Bivium-A va Bivium-B (Bivium). Bivium-A yangi aʼzo Z ning oʻzgartirilgan status bitiga bevosita bogʻliqligini amalga oshirdi $z_i\leftarrow t_1$, Bivium-B (Bivium) da undan farqidan $z_i\leftarrow t_1+t_2$.

Trivium-oʻyinchoq va Bivium-oʻyinchoq

Oʻyinchoq versiyalari registr uzunliklarini qisqartirish yoʻli bilan olingan, bu esa barcha matematik xususiyatlarni saqlab qolgan holda algoritmning hisoblash murakkabligini pasaytirdi. Har bir registrning uzunligi 3 baravar qisqardi va Bivium-toy ham faqat ikkita registrdan iborat edi.

Trivium shifrining har bir modifikatsiyasi uning matematik tavsifini soddalashtirish uchun yaratilgan boʻlib, u axborot xavfsizligi vositalarida ulardan foydalanishdan koʻra koʻproq taʼlim maqsadiga ega.

Ishlashi

Algoritmning standart apparat amalga oshirilishi 3488 mantiqiy elementni talab qiladi va 1 sikl uchun 1 bit kalit oqimini ishlab chiqaradi. Biroq, har bir yangi bit holati kamida 64 tur davomida oʻzgarmasligi sababli, mantiqiy elementlar sonini 5504 ga oshirishda parallel ravishda yana 64 holat yaratilishi mumkin. Amaldagi elementlar soniga qarab turli xil ishlash oʻzgarishlari ham mumkin.

Ushbu algoritmning dasturiy taʼrifi ham juda samarali. AthlonXP 1600+ protsessorida Trivium C ilovasi 2,4 Mbit/s dan ortiq shifrlash tezligini taʼminlaydi.

Xavfsizlik

RC4 kabi dastlabki oqim shifrlaridan farqli oʻlaroq, Trivium algoritmi shaxsiy kalitga (K) qoʻshimcha ravishda ochiq kalit boʻlgan ishga tushirish vektoriga (IV) ham ega. IV dan foydalanish faqat 1 kalit va bir nechta ishga tushirish vektorlari (har bir seans uchun bitta) yordamida bir nechta mustaqil shifrlash/parchalash seanslariga imkon beradi. Bundan tashqari, har bir yangi xabar uchun yangi IV dan foydalanib, bir seans uchun bir nechta ishga tushirish vektorlaridan foydalanishingiz mumkin.

Hozirgi vaqtda ushbu algoritmga hujum qilishning ketma- ket roʻyxatga olishdan koʻra samaraliroq usullari maʼlum emas. Ushbu hujumning murakkabligi xabarning uzunligiga bogʻliq va buyurtma boʻyicha $2^{120}$.

Hujum usullari (masalan, kubik hujum) boʻyicha tadqiqotlar mavjud, ular samaradorlik jihatidan sanab oʻtishga yaqin. Bundan tashqari, K ni IV va kalit oqimidan tiklashga imkon beruvchi hujum usuli mavjud. Ushbu hujumning murakkabligi $2^{135}$ va bitta kalit bilan ishlatiladigan ishga tushirish vektorlari soni ortishi bilan bir oz kamayadi. Naqshlarni topish va oqimning keyingi bitlarini bashorat qilish uchun kalit oqimining psevdo-tasodifiy ketma-ketligini oʻrganish bilan ham hujumlar mumkin, ammo bu hujumlar murakkab chiziqli boʻlmagan tenglamalarni hal qilishni talab qiladi. Bunday hujumning eng kam olingan murakkabligi $2^{164}$

Tadqiqot usullari

Trivium ning deyarli barcha xakerlik yutuqlari algoritmning qisqartirilgan versiyalarida muvaffaqiyatli amalga oshirilgan hujumlardan foydalanishga urinishdir. Koʻpincha Bivium algoritmining versiyasi oʻrganilayotgani sifatida ishlatiladi, unda umumiy uzunligi 192 bit boʻlgan atigi 2 ta siljish registrlari qoʻllanadi.

Havolalar

• eSTREAM loyihasi sahifasidagi trivium Andoza:Webarxiv Arxivnaya kopiya -da arxivlangan
• eSTREAM loyihasi sahifasidagi algoritm tavsifi Andoza:Webarxiv Arxivnaya kopiya
• Oqim shifrlarini qurish tamoyillari Andoza:Webarxiv