Trivium (shifr)
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
{\displaystyle 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
≤
2
64
{\displaystyle N\leq 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
)
←
(
K
1
,
.
.
.
,
K
80
,
0
,
.
.
.
,
0
)
{\displaystyle (s_{1},s_{2},...,s_{93})\leftarrow (K_{1},...,K_{80},0,...,0)}
(
s
94
,
s
95
,
.
.
.
,
s
177
)
←
(
I
V
1
,
.
.
.
,
I
V
80
,
0
,
.
.
.
,
0
)
{\displaystyle (s_{94},s_{95},...,s_{177})\leftarrow (IV_{1},...,IV_{80},0,...,0)}
(
s
178
,
s
179
,
.
.
.
,
s
288
)
←
(
0
,
.
.
.0
,
1
,
1
,
1
)
{\displaystyle (s_{178},s_{179},...,s_{288})\leftarrow (0,...0,1,1,1)}
for
i
=
1
to
4
⋅
288
do
{\displaystyle {\mbox{for}}\ i=1\ {\mbox{to}}\ 4\cdot 288\ {\mbox{do}}}
t
1
←
s
66
+
s
91
⋅
s
92
+
s
93
+
s
171
{\displaystyle t_{1}\leftarrow s_{66}+s_{91}\cdot s_{92}+s_{93}+s_{171}}
t
2
←
s
162
+
s
175
⋅
s
176
+
s
177
+
s
264
{\displaystyle t_{2}\leftarrow s_{162}+s_{175}\cdot s_{176}+s_{177}+s_{264}}
t
3
←
s
243
+
s
286
⋅
s
287
+
s
288
+
s
69
{\displaystyle t_{3}\leftarrow s_{243}+s_{286}\cdot s_{287}+s_{288}+s_{69}}
(
s
1
,
s
2
,
.
.
.
,
s
93
)
←
(
t
3
,
s
1
,
.
.
.
,
s
92
)
{\displaystyle (s_{1},s_{2},...,s_{93})\leftarrow (t_{3},s_{1},...,s_{92})}
(
s
94
,
s
95
,
.
.
.
,
s
177
)
←
(
t
1
,
s
94
,
.
.
.
,
s
176
)
{\displaystyle (s_{94},s_{95},...,s_{177})\leftarrow (t_{1},s_{94},...,s_{176})}
(
s
178
,
s
179
,
.
.
.
,
s
288
)
←
(
t
2
,
s
178
,
.
.
.
,
s
287
)
{\displaystyle (s_{178},s_{179},...,s_{288})\leftarrow (t_{2},s_{178},...,s_{287})}
end for
{\displaystyle {\mbox{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
{\displaystyle z_{i}}
. Algoritm natijasida, gacha
N
≤
2
64
{\displaystyle N\leq 2^{64}}
kalit oqimi biti. Algoritmni quyidagi psevdokod bilan tasvirlash mumkin.
for
i
=
1
to
N
do
{\displaystyle {\mbox{for}}\ i=1\ {\mbox{to}}\ N\ {\mbox{do}}}
t
1
←
s
66
+
s
93
{\displaystyle t_{1}\leftarrow s_{66}+s_{93}}
t
2
←
s
162
+
s
177
{\displaystyle t_{2}\leftarrow s_{162}+s_{177}}
t
3
←
s
243
+
s
288
{\displaystyle t_{3}\leftarrow s_{243}+s_{288}}
z
i
←
t
1
+
t
2
+
t
3
{\displaystyle z_{i}\leftarrow t_{1}+t_{2}+t_{3}}
t
1
←
s
66
+
s
91
⋅
s
92
+
s
93
+
s
171
{\displaystyle t_{1}\leftarrow s_{66}+s_{91}\cdot s_{92}+s_{93}+s_{171}}
t
2
←
s
162
+
s
175
⋅
s
176
+
s
177
+
s
264
{\displaystyle t_{2}\leftarrow s_{162}+s_{175}\cdot s_{176}+s_{177}+s_{264}}
t
3
←
s
243
+
s
286
⋅
s
287
+
s
288
+
s
69
{\displaystyle t_{3}\leftarrow s_{243}+s_{286}\cdot s_{287}+s_{288}+s_{69}}
(
s
1
,
s
2
,
.
.
.
,
s
93
)
←
(
t
3
,
s
1
,
.
.
.
,
s
92
)
{\displaystyle (s_{1},s_{2},...,s_{93})\leftarrow (t_{3},s_{1},...,s_{92})}
(
s
94
,
s
95
,
.
.
.
,
s
177
)
←
(
t
1
,
s
94
,
.
.
.
,
s
176
)
{\displaystyle (s_{94},s_{95},...,s_{177})\leftarrow (t_{1},s_{94},...,s_{176})}
(
s
178
,
s
179
,
.
.
.
,
s
288
)
←
(
t
2
,
s
178
,
.
.
.
,
s
287
)
{\displaystyle (s_{178},s_{179},...,s_{288})\leftarrow (t_{2},s_{178},...,s_{287})}
end for
{\displaystyle {\mbox{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
{\displaystyle 2^{96-3}-1}
(bu kerakli kalit oqimi uzunligidan allaqachon oshib ketadi
2
64
{\displaystyle 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
{\displaystyle 2^{288}}
aql bovar qilmaydigan bo'ladi. Shuningdek, kalit/boshlash vektor juftligidan kamroq muddatga kalit oqimini yaratish ehtimoli
2
80
{\displaystyle 2^{80}}
tartibda bo'ladi
2
−
208
{\displaystyle 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
←
t
1
{\displaystyle z_{i}\leftarrow t_{1}}
, Bivium-B (Bivium) da undan farqidan
z
i
←
t
1
+
t
2
{\displaystyle 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
{\displaystyle 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
{\displaystyle 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
{\displaystyle 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'llaniladi.
Eslatmalar
Havolalar
uz.wikipedia.org