- Qo'llanma
Salom% foydalanuvchi nomi%!
Ko'p odamlar biladiki, DES uzoq vaqtdan beri nosimmetrik shifrlash uchun standart standart hisoblanadi. Ushbu o'ldirilmaydigan algoritmga birinchi muvaffaqiyatli hujum 1993 yilda, standart sifatida qabul qilinganidan 16 yil o'tgach nashr etilgan. Muallif 247 ta ochiq / shifrlangan matnlar ishtirokida chiziqli kriptanaliz deb atagan usul 243 ta operatsiyada DES shifrining maxfiy kalitini buzishga imkon beradi.
Kesik ostida men ushbu hujumning asosiy nuqtalarini sarhisob qilishga harakat qilaman.
Lineer kriptanaliz
Lineer kriptanaliz - bu ma'lum bo'lgan ochiq xabarlardan nomuvofiq shifrlash kalitini va ularga mos keladigan shifrlarni tiklashga qaratilgan nosimmetrik shifrlarga qarshi hujumning maxsus turi.Umuman olganda, chiziqli kriptanalizga asoslangan hujum quyidagi holatlarga kamaytiriladi. Hujumchi bir xil K shifrlash kaliti yordamida olingan juda ko'p aniq / shifrlangan juftliklarga ega. Hujumchining maqsadi K tugmachasining bir qismini yoki hammasini tiklashdir.
Avvalo, tajovuzkor shifrni tekshiradi va o'zi deb atalmish narsani topadi. statistik analog, ya'ni o'zboshimchalik bilan ochiq / yopiq matn juftligi va belgilangan kalit uchun P for 1/2 ehtimollik bilan bajarilgan quyidagi shakldagi tenglama:
P I1 ⊕ P I2 ⊕… ⊕ P Ia ⊕ C I1 ⊕ C I2 ⊕… ⊕ C Ib \u003d K I1 ⊕ K I2 ⊕… ⊕ K Ic (1)
,
bu erda P n, C n, K n - matnning n-chi bitlari, shifrlangan matn va kalit.
Shunga o'xshash tenglama topilgandan so'ng, tajovuzkor quyidagi algoritm yordamida kalit haqida 1 bit ma'lumotni tiklashi mumkin
Algoritm 1
T (1) tenglamaning chap tomoni 0 ga teng bo'lgan matnlar soni bo'lsin, keyin
Agar T\u003e N / 2 bo'lsa, bu erda N - ma'lum tekisliklarning soni.
K I1-K I2 ⊕… ⊕ K Ic \u003d 0 (P\u003e 1/2 bo'lganda) yoki 1 (P bo'lganda<1/2).
Aks holda
K I1-K I2 ⊕… ⊕ K Ic \u003d 1 (P\u003e 1/2 bo'lganda) yoki 0 (P bo'lganda<1/2).
Shubhasiz, algoritmning muvaffaqiyati to'g'ridan-to'g'ri | P-1/2 | qiymatiga bog'liq va mavjud bo'lgan ochiq / yopiq matnli juftliklar soni bo'yicha P (1) tenglik ehtimoli 1/2 dan qanchalik ko'p farq qilsa, hujum uchun shunchaki N ochiq matnlar soni kerak bo'ladi.
Hujumni muvaffaqiyatli amalga oshirish uchun ikkita muammoni hal qilish kerak:
- Shaklning samarali tenglamasini qanday topish mumkin (1).
- Bunday tenglama yordamida qanday qilib kalit haqida bir nechta ma'lumot olish mumkin.
DES tavsifi
Ammo avval algoritm qanday ishlashini qisqacha tavsiflab beraylik. DES haqida etarli narsa aytilgan. Shifrning to'liq tavsifini Vikipediyada topishingiz mumkin. Biroq, hujumni qo'shimcha ravishda tushuntirish uchun oldindan eng yaxshi kiritilgan bir qator ta'riflar kerak.Demak, DES - bu Feistel tarmog'iga asoslangan blok shifridir. Shifrning blok hajmi 64 bit, kalit hajmi 56 bit. DES shifrlash sxemasini ko'rib chiqamiz. 
Rasmdan ko'rinib turibdiki, matnni shifrlashda quyidagi amallar bajariladi:
- Dastlabki bitni almashtirish. Ushbu bosqichda kirish blokining bitlari ma'lum tartibda aralashtiriladi.
- Shundan so'ng, aralash bitlar ikkiga bo'linadi, ular Feistel funktsiyasining kirish qismiga beriladi. Standart DES uchun Feistel tarmog'i 16 turni o'z ichiga oladi, ammo algoritmning boshqa variantlari mavjud.
- Transformatsiyaning so'nggi turida olingan ikkita blok birlashtirilib, hosil bo'lgan blok ustida yana bir almashtirish amalga oshiriladi.
Feistel tarmog'ining har bir turida, xabarning eng kam 32 biti f funktsiyasi orqali o'tadi: 
Ushbu bosqichda bajarilgan operatsiyalarni ko'rib chiqamiz:
- Kirish bloki 32 bitli blokni 48 bitli blokga aylantiradigan E kengayish funktsiyasi orqali o'tadi.
- Olingan blok K i dumaloq tugmachasi bilan qo'shiladi.
- Oldingi qadamning natijasi har biri 6 bitli 8 ta blokga bo'lingan.
- Qabul qilingan B i bloklarning har biri 6-bitli ketma-ketlikni 4-bitli blok bilan almashtiradigan S-Box i almashtirish funktsiyasidan o'tadi.
- Hosil bo'lgan 32-bitli blok P permutatsiyadan o'tadi va f natijasida qaytariladi.
Shifrning kriptanalizasi nuqtai nazaridan biz uchun eng katta qiziqish, f funktsiyasining kirish va chiqish ma'lumotlari orasidagi aloqani yashirish uchun mo'ljallangan S bloklardir. DES-ga muvaffaqiyatli hujum qilish uchun avval S-qutilarining har biri uchun statistik analoglarni tuzamiz, so'ngra ularni butun shifrga uzatamiz.
S bloklarini tahlil qilish
Har bir S-quti kirish sifatida 6-bitli ketma-ketlikni qabul qiladi va har bir ketma-ketlik uchun sobit 4-bitli qiymat qaytariladi. O'sha. kirish va chiqish ma'lumotlari uchun faqat 64 ta variant mavjud. Bizning vazifamiz S bloklarining kirish va chiqish ma'lumotlari o'rtasidagi bog'liqlikni ko'rsatishdir. Masalan, DES shifrining uchinchi S-qutisi uchun kirish ketma-ketligining 3-biti 64 ta holatning 38 ta holatida chiqadigan ketma-ketlikning 3-bitiga teng. Shuning uchun biz uchinchi S-box uchun quyidagi statistik analogni topdik:S 3 (x) \u003d x, bu P \u003d 38/64 ehtimollik bilan bajariladi.
Tenglamaning ikkala tomoni 1 bit ma'lumotni ifodalaydi. Shuning uchun, agar chap va o'ng tomonlar bir-biridan mustaqil bo'lsa, tenglama 1/2 ga teng ehtimol bilan bajarilishi kerak edi. Shunday qilib, biz hozirda DES algoritmining 3-S-qutisiga kirish va chiqish o'rtasidagi bog'liqlikni namoyish etdik.
Umumiy holatda S-boxning statistik analogini qanday topish mumkinligini ko'rib chiqing.
S-quti S a, 1 ≤ a 63 va 1 ≤ ≤ 15 uchun NS a (a, β) qiymati X bitlarning 64 ta bit bitlaridan bittasi ustiga qo'yilgan XOR kirish bitlariga necha marta teng ekanligini tavsiflaydi. β, ya'ni:
bu erda belgi mantiqiy VA.
NS a (a, b) 32 dan katta farq qiladigan a va b qiymatlari S-quti S a ning eng samarali statistik analogini tavsiflaydi.
Eng samarali analog DES shifrining 5-S-blokida a \u003d 16 va ph \u003d 15 NS 5 (16, 15) \u003d 12 uchun topilgan. Bu shuni anglatadiki, quyidagi tenglama to'g'ri: Z \u003d Y ⊕ Y ⊕ Y ⊕ Y, bu erda Z - S qutining kirish ketma-ketligi va Y - chiqish ketma-ketligi.
Yoki DES algoritmida S-blokga kirishdan oldin ma'lumotlar dumaloq kalit bilan modul 2 qo'shilishini hisobga olsak, ya'ni. Z \u003d X-K ni olamiz
X ⊕ Y ⊕ Y ⊕ Y ⊕ Y \u003d K, bu erda X va Y - almashtirish funktsiyalarini hisobga olmasdan f funktsiyasining kirish va chiqish ma'lumotlari.
Olingan tenglama DES algoritmining barcha turlarida bir xil P \u003d 12/64 ehtimollik bilan bajariladi.
Quyidagi jadvalda samarali ro'yxati keltirilgan, ya'ni. P \u003d 1/2 dan eng katta og'ishga ega bo'lgan, DES algoritmining har bir s-bloki uchun statistik analoglar. 
Ko'p sonli DES turlari uchun statistik analoglarni yaratish
Keling, bir nechta DES turlarining statistik analoglarini qanday qilib birlashtirishimiz va natijada butun shifr uchun statistik analogni qanday olishimiz mumkinligini ko'rsatib o'tamiz.Buning uchun algoritmning uch bosqichli versiyasini ko'rib chiqing:
X (2) qiymatining ma'lum bitlarini hisoblash uchun 5-s-qutining samarali statistik analogini qo'llaymiz.
Bilamizki, 12/64 ehtimollik bilan f funktsiyasi tenglikni qondiradi X ⊕ Y ⊕ Y ⊕ Y ⊕ Y \u003d K, bu erda X - 5-chi S-qutining ikkinchi kirish biti, bu aslida kirish bitlarini kengaytirgandan so'ng olingan ketma-ketlikning 26-biti. Kengaytma funktsiyasini tahlil qilib, biz 26-bit o'rnida X (1) ketma-ketlikning 17-biti borligini aniqlay olamiz.
Xuddi shunday, Y, ..., Y asosan P permutatsiyasidan oldin olingan ketma-ketlikning 17, 18, 19 va 20-bitlari bo'lib, P permutatsiyasini o'rganib chiqib, Y, ..., Y bitlari aslida bitlar ekan Y (1), Y (1), Y (1), Y (1).
Tenglamalarda ishtirok etgan K kalitining biti birinchi tur K1 pastki tugmachasining 26-biti bo'lib, keyin statistik analog quyidagi shaklga ega:
X (1) ⊕ Y (1) ⊕ Y (1) ⊕ Y1 ⊕ Y (1) \u003d K1.
Shuning uchun, X (1) ⊕ K1 \u003d Y (1) ⊕ Y (1) ⊕ Y (1) ⊕ Y (1)(2) ehtimollik bilan P \u003d 12/64.
Y (1) ketma-ketlikning 3, 8, 14, 25 bitlarini bilib, X (2) ketma-ketligining 3, 8, 14, 25 bitlarini topishingiz mumkin:
X (2) ⊕ X (2) ⊕ X (2) ⊕ X (2) \u003d PL ⊕ PL ⊕ PL ⊕ PL ⊕ Y (1) ⊕ Y (1) ⊕ Y (1) ⊕ Y (1)yoki (2) tenglamani hisobga olgan holda
X (2) ⊕ X (2) ⊕ X (2) ⊕ X (2) \u003d PL ⊕ PL ⊕ PL ⊕ PL ⊕ X (1) ⊕ K1 (3) 12/64 ehtimollik bilan.
Oxirgi turdan foydalanib shunga o'xshash iborani topamiz. Bu safar bizda tenglama mavjud
X (3) ⊕ K3 \u003d Y (3) ⊕ Y (3) ⊕ Y (3) ⊕ Y (3).
Chunki
X (2) ⊕ X (2) ⊕ X (2) ⊕ X (2) \u003d SL ⊕ SL ⊕ SL ⊕ SL ⊕ Y (3) ⊕ Y (3) ⊕ Y (3) ⊕ Y (3)
biz buni tushunamiz
X (2) ⊕ X (2) ⊕ X (2) ⊕ X (2) \u003d SL ⊕ SL ⊕ SL ⊕ SL ⊕ X (3) ⊕ K3(4)
12/64 ehtimollik bilan.
(3) va (4) tenglamalarning o'ng tomonlarini tenglashtirsak, biz olamiz
SL ⊕ SL ⊕ SL ⊕ SL ⊕ X (3) ⊕ K3 \u003d PL ⊕ PL ⊕ PL ⊕ PL ⊕ X (1) ⊕ K1 ehtimollik bilan (12/64) 2 + (1-12 / 64) 2.
X (1) \u003d PR va X (3) \u003d CR ekanligini hisobga olsak, statistik analogni olamiz
SL ⊕ CR ⊕ PL ⊕ PR \u003d K1 ⊕ K3 (5)
,
ehtimolligi (12/64) 2 + (1-12 / 64) 2 \u003d 0,7 bilan ishlaydi.
Yuqorida tavsiflangan statistik analog grafik tarzda quyidagicha ifodalanishi mumkin (rasmdagi bitlar o'ngdan chapga va noldan boshlab raqamlangan): 
Tenglamaning chap qismidagi barcha bitlar tajovuzkorga ma'lum, shuning uchun u 1-algoritmni qo'llashi va K1-K3 qiymatini bilishi mumkin. Keling, ushbu statistik analogdan foydalanib, qanday qilib K shifrlash kalitining 1 emas, balki 12 bitini sindirish mumkinligini ko'rsatamiz.
DES hujumi ma'lum bo'lgan oddiy matn bilan amalga oshiriladi
Bu erda siz hujumni kengaytirish va bir vaqtning o'zida birinchi davra pastki kalitining 6 bitini olishingiz mumkin bo'lgan usul.(5) tenglamani tuzishda biz F1 (PR, K1) qiymatini bilmasligimizni hisobga oldik. Shuning uchun biz uning K1 ⊕ PR statistik analogidan foydalandik.
K1-PR ifodasi o'rniga F1 (PR, K1) qiymatini qaytaramiz va quyidagi tenglamani olamiz:
CL-CR-PL-F1 (PR, K1) \u003d K3 (6) 12/64 ehtimollik bilan bajariladigan. Uchinchi turdan faqat statistik analogni qoldirganimizdan beri ehtimollik o'zgargan, qolgan barcha qiymatlar aniqlangan.
Yuqorida biz F1 (PR, K1) qiymatiga 5-S-qutining kirish bitlari, ya'ni K1 tugmachasi va PR blokining bitlari ta'sir qilishini allaqachon aniqladik. Keling, faqat bitta ochiq / yopiq matnlar to'plamiga ega bo'lgan holda, siz K1 qiymatini qanday qilib tiklashingiz mumkinligini ko'rsatamiz. Buning uchun biz 2-algoritmdan foydalanamiz.
Algoritm 2
Hujumdan oldin ma'lum bo'lgan ochiq / yopiq matn juftlari soni N bo'lsin. Keyin kalitni ochish uchun quyidagi amallarni bajarishingiz kerak.
Uchun (i \u003d 0; i<64; i++) do
{
Uchun (j \u003d 0; j
agar (CL j ⊕ CR j ⊕ PL j ⊕ F1 (PR j, i) \u003d 0) bo'lsa
T i \u003d T i +1
}
}
Mumkin bo'lgan ketma-ketlik K1 sifatida | T i -N / 2 | ifodasi uchun i ning shunday qiymati olinadi maksimal qiymatga ega.
Ma'lum bo'lgan oddiy matnlarning etarli miqdorini hisobga olgan holda, algoritm, birinchi navbatda, K1 pastki tugmachasining to'g'ri oltitasini qaytaradi. Buning sababi shundaki, agar i o'zgaruvchisi K1 ga teng bo'lmasa, unda F1 (PR j, K) funktsiyasining qiymati tasodifiy bo'ladi va chap tomoni nolga teng bo'lgan bunday i qiymati uchun tenglamalar soni N / 2 ga moyil bo'ladi. Agar pastki kalit to'g'ri taxmin qilingan bo'lsa, chap tomoni 12/64 ehtimollik bilan belgilangan K3 bitiga teng bo'ladi. O'sha. N / 2 dan sezilarli og'ish bo'ladi.
6 bit K1 pastki kalitini olganingizdan so'ng, xuddi shu tarzda 6 bitli K3 pastki kalitini ham ochishingiz mumkin. Buning uchun kerak bo'lgan narsa (6) tenglamani P ga almashtirish va K1 ni K3 ga almashtirishdir.
PL ⊕ PR ⊕ CL ⊕ F3 (CR, K3) \u003d K1.
2-algoritm to'g'ri qiymatni qaytaradi K3, chunki DES algoritmining parolini hal qilish jarayoni shifrlash jarayoni bilan bir xil, u shunchaki tugmalar ketma-ketligini o'zgartiradi. Shunday qilib, parolni hal qilishning birinchi bosqichida K3 tugmachasi va oxirgi K1 tugmasi ishlatiladi.
6 bitli K1 va K3 pastki kalitlarini olgan holda, tajovuzkor K bitli shifrning 12 bit umumiy kalitini tiklaydi, chunki dumaloq tugmachalar - K tugmachasining keng tarqalgan almashinuvi. Muvaffaqiyatli hujum uchun zarur bo'lgan aniq matnlar soni statistik hamkasbning ehtimoliga bog'liq. 3 dumaloq DES tugmachasining 12 bitini sindirish uchun 100 ta ochiq matn / ochiq matn juftligi etarli. 16 ta DES tugmachasining 12 bitini sindirish uchun taxminan 244 matn juftligi kerak bo'ladi. Qolgan 44 bit kalit muntazam ravishda qo'pol hujum bilan ochiladi.
Algoritm DES
DES algoritmining asosiy afzalliklari:
· 56 bit uzunlikdagi faqat bitta kalit ishlatiladi;
· Xabarni bitta paket bilan shifrlaganingizdan so'ng, parolni ochish uchun istalgan boshqa usuldan foydalanishingiz mumkin;
· Algoritmning nisbatan soddaligi axborotni ishlashning yuqori tezligini ta'minlaydi;
· Algoritmning etarlicha yuqori barqarorligi.
DES 56 bitli kalit yordamida 64 bitli ma'lumotlar bloklarini shifrlaydi. DES parolini hal qilish - bu shifrlashning teskari ishlashi va teskari tartibda shifrlash operatsiyalarini takrorlash orqali amalga oshiriladi (aniq ko'rinishga qaramay, bu har doim ham amalga oshirilmaydi. Keyinchalik shifrlash va parol hal qilish turli algoritmlar yordamida amalga oshiriladigan shifrlarni ko'rib chiqamiz).
Shifrlash jarayoni 64 bitli blokning boshlang'ich bit almashtirishidan, o'n oltita shifrlash davridan va nihoyat teskari bit almashtirishdan iborat (1-rasm).
Shuni darhol ta'kidlash kerakki, ushbu maqolada keltirilgan BARCHA jadvallar STANDART bo'lib, shuning uchun algoritmni amalga oshirishda o'zgarmagan holda kiritilishi kerak. Jadvaldagi barcha almashtirishlar va kodlar ishlab chiquvchilar tomonidan kalitni tanlash orqali parol hal qilish jarayonini iloji boricha qiyinlashtiradigan tarzda tanlangan. DES algoritmining tuzilishi 2-rasmda keltirilgan.
Shakl.2. DES shifrlash algoritmi tuzilishi
Keyingi 8 baytli T bloki fayldan o'qilsin, u dastlabki almashtirish IP matritsasi yordamida o'zgartirilgan (1-jadval) quyidagicha: T blokning 58 biti 1 bitga, 50 bit 2 ga aylanadi va hokazo. : T (0) \u003d IP (T).
Olingan T (0) bitlar ketma-ketligi har biri 32 bitli ikkita ketma-ketlikka bo'linadi: L (0) - chap yoki eng muhim bitlar, R (0) - o'ng yoki unchalik ahamiyatsiz bitlar.
Jadval 1: IP-ning dastlabki permutatsiya matritsasi
58 50 42 34 26 18 10 02
60 52 44 36 28 20 12 04
62 54 46 38 30 22 14 06
64 56 48 40 32 24 16 08
57 49 41 33 25 17 09 01
59 51 43 35 27 19 11 03
61 53 45 37 29 21 13 05
63 55 47 39 31 23 15 07
Keyin 16 ta takrorlashdan iborat shifrlash amalga oshiriladi. I-takrorlash natijasi quyidagi formulalar bilan tavsiflanadi:
R (i) \u003d L (i-1) xor f (R (i-1), K (i)),
bu erda xor - eksklyuziv yoki operatsiya.
F funktsiyasi shifrlash funktsiyasi deb ataladi. Uning argumentlari (i-1) th takrorlanishida olingan 32-bitli R (i-1) ketma-ketligi va 48-bitli K (i) tugmachasi bo'lib, bu 64-bitli K tugmachasini o'zgartirish natijasidir, batafsil ravishda shifrlash funktsiyasi va K (i) tugmachalarini olish algoritmi quyida tavsiflangan.
16-takrorlashda R (16) va L (16) ketma-ketliklar olinadi (almashtirishsiz), ular 64-bitli R (16) L (16) ketma-ketlikda birlashadi.
Keyin ushbu ketma-ketlikning bit pozitsiyalari IP -1 matritsasiga muvofiq ravishda almashtiriladi (2-jadval).
Jadval 2: IP -1 teskari almashtirish matritsasi
40 08 48 16 56 24 64 32
39 07 47 15 55 23 63 31
38 06 46 14 54 22 62 30
37 05 45 13 53 21 61 29
36 04 44 12 52 20 60 28
35 03 43 11 51 19 59 27
34 02 42 10 50 18 58 26
33 01 41 09 49 17 57 25
IP -1 va IP matritsalari quyidagicha bog'liq: IP -1 matritsasining 1-elementi qiymati 40 ga, IP matritsasining 40-elementi qiymati 1 ga, IP -1 matritsasining 2-elementi qiymati 8 ga va 8-qiymati IP matritsasining elementi 2 ga teng va boshqalar.
Ma'lumotlarni parolini hal qilish jarayoni shifrlash jarayonining teskari tomonidir. Barcha qadamlar teskari tartibda bajarilishi kerak. Bu shuni anglatadiki, parol hal qilingan ma'lumotlar avval IP-1 matritsasiga muvofiq qayta tuziladi, so'ngra xuddi shu harakatlar R (16) L (16) bit ketma-ketlikda shifrlash jarayonida bo'lgani kabi, lekin teskari tartibda amalga oshiriladi.
Shifrni echish jarayonini quyidagi formulalar bilan tavsiflash mumkin:
R (i-1) \u003d L (i), i \u003d 1, 2, ..., 16;
L (i-1) \u003d R (i) xor f (L (i), K (i)), i \u003d 1, 2, ..., 16.
16-takrorlashda L (0) va R (0) ketma-ketliklar olinadi, ular 64-bitli L (0) R (0) ketma-ketlikda tutashtiriladi.
Ushbu ketma-ketlikning bit pozitsiyalari keyinchalik IP-matritsaga muvofiq qayta tartibga solinadi. Bunday almashtirishning natijasi asl 64-bitli ketma-ketlikdir.
Endi f (R (i-1), K (i)) shifrlash funktsiyasini ko'rib chiqing. Bu rasmda sxematik tarzda ko'rsatilgan. 3.
Shakl.3. F (R (i-1), K (i)) funktsiyasini hisoblash
F funktsiyasining qiymatini hisoblash uchun quyidagi matritsa funktsiyalari qo'llaniladi:
E - 32-bitli ketma-ketlikni 48-bitgacha kengaytirish,
S1, S2, ..., S8 - 6 bitli blokni 4 bitli blokga aylantirish,
P - 32-bitli ketma-ketlikdagi bitlarni almashtirish.
Kengayish funktsiyasi E 3-jadvalda aniqlangan. Ushbu jadvalga binoan E ning birinchi 3 biti (R (i-1)) 32, 1 va 2 bit, oxirgisi 31, 32 va 1 dir.
3-jadval: kengaytirish funktsiyasi E
32 01 02 03 04 05
04 05 06 07 08 09
08 09 10 11 12 13
12 13 14 15 16 17
16 17 18 19 20 21
20 21 22 23 24 25
24 25 26 27 28 29
28 29 30 31 32 01
E (R (i-1)) funktsiyasining natijasi 48-bitli ketma-ketlik bo'lib, unga 48-bitli K (i) tugmachasi bilan modul 2 (xor operatsiyasi) qo'shiladi. Natijada sakkizta 6-bitli B (1) B (2) B (3) B (4) B (5) B (6) B (7) B (8) bloklarga bo'linadigan 48-bitli ketma-ketlik hosil bo'ladi. Ya'ni:
E (R (i-1)) xor K (i) \u003d B (1) B (2) ... B (8).
S1, S2, ..., S8 funktsiyalari 4-jadvalda aniqlangan.
Jadval 4
Jadval 4. qo'shimcha tushuntirish talab etiladi. 6-bitli B (j) \u003d b1b2b3b4b5b6 bloki Sj matritsa funktsiyasining kiritilishiga kiritsin, u holda ikki bitli b1b6 matritsaning qator raqamini, b2b3b4b5 esa ustun sonini bildiradi. Sj (B (j)) natijasi belgilangan satr va ustun chorrahasida joylashgan 4-bitli element hisoblanadi.
Masalan, B (1) \u003d 011011. Keyin S1 (B (1)) 1-satr va 13-ustun kesishgan joyda joylashgan. 1-satrning 13-ustuni 5 ga o'rnatiladi. Shunday qilib S1 (011011) \u003d 0101.
Tanlash operatsiyasini B (1), B (2), ..., B (8) 6-bitli bloklarning har biriga qo'llasak, biz 32 bitli S1 (B (1)) S2 (B (2)) S3 ( B (3)) ... S8 (B (8)).
Nihoyat, shifrlash funktsiyasi natijasini olish uchun ushbu ketma-ketlik bitlarini almashtirish kerak. Buning uchun P almashtirish funktsiyasi ishlatiladi (5-jadval). Kirish ketma-ketligida bitlar almashtiriladi, shunda bit 16 bit 1, 7 bit 2 bit bo'ladi va hokazo.
5-jadval: P uzatish funktsiyasi
Shunday qilib,
f (R (i-1), K (i)) \u003d P (S1 (B (1)), ... S8 (B (8)))
Ma'lumotlarni shifrlash algoritmining tavsifini bajarish uchun 48 bitli K (i), i \u003d 1 ... 16 tugmachalarini olish algoritmini berish qoladi. Har bir takrorlashda yangi boshlang'ich K qiymati (i) ishlatiladi, bu boshlang'ich K tugmachasidan hisoblanadi. K 8,16,24,32,40,48,56 pozitsiyalarida joylashgan sakkizta pariteli 64-bitli blok, 64.
Boshqaruv bitlarini olib tashlash va qolganlarini almashtirish uchun dastlabki kalit tayyorlashning G funktsiyasidan foydalaniladi (6-jadval).
Jadval 6
Boshlang'ich kalitlarni tayyorlash matritsasi G
57 49 41 33 25 17 09
01 58 50 42 34 26 18
10 02 59 51 43 35 27
19 11 03 60 52 44 36
63 55 47 39 31 23 15
07 62 54 46 38 30 22
14 06 61 53 45 37 29
21 13 05 28 20 12 04
Transformatsiya natijasi G (K) ikkita 28-bitli C (0) va D (0) bloklarga bo'linadi va C (0) K va D (0) tugmalarining 57, 49, ..., 44, 36 bitlaridan iborat bo'ladi. ) K tugmachasining 63, 55, ..., 12, 4 bitlaridan iborat bo'ladi C (0) va D (0) ni aniqlagandan so'ng, C (i) va D (i), i \u003d 1 ... 16 rekursiv ravishda aniqlanadi. Buning uchun 7-jadvalda ko'rsatilgandek takrorlanish soniga qarab tsikli chap siljishni bir yoki ikkita bitga qo'llang.
Jadval 7
Kalitni hisoblash uchun Shift jadvali
| Takrorlash raqami | Shift (bit) |
| 01 | 1 |
| 02 | 1 |
| 03 | 2 |
| 04 | 2 |
| 05 | 2 |
| 06 | 2 |
| 07 | 2 |
| 08 | 2 |
| 09 | 1 |
| 10 | 2 |
| 11 | 2 |
| 12 | 2 |
| 13 | 2 |
| 14 | 2 |
| 15 | 2 |
| 16 | 1 |
Olingan qiymat yana H matritsasiga muvofiq "aralashtiriladi" (8-jadval).
Jadval 8: Keyingi qayta ishlash matritsasi H
14 17 11 24 01 05
03 28 15 06 21 10
23 19 12 04 26 08
16 07 27 20 13 02
41 52 31 37 47 55
30 40 51 45 33 48
44 49 39 56 34 53
46 42 50 36 29 32
K (i) kaliti C (i) D (i) ketma-ketlikning 14, 17, ..., 29, 32 bitlaridan iborat bo'ladi. Shunday qilib:
K (i) \u003d H (C (i) D (i))
Kalitlarni hisoblash algoritmining blok diagrammasi 4-rasmda keltirilgan.
Shakl.4. K (i) tugmachasini hisoblash algoritmining blok diagrammasi
Asl matnni tiklash ushbu algoritm yordamida amalga oshiriladi, lekin avval siz kalitdan foydalanasiz
K (15), keyin K (14) va boshqalar. Endi muallif nima uchun berilgan matritsalardan foydalanishni qat'iyan tavsiya qilishi sizga aniq bo'lishi kerak. Agar siz o'zingizni odil tutishni boshlasangiz, siz juda maxfiy shifrni olishingiz kerak, ammo keyinchalik uni o'zingiz ham ochib berolmaysiz!
DES ishlash rejimlari
Tijorat shifrlash tizimlariga qo'yiladigan barcha talablarni to'liq qondirish uchun DES algoritmining bir necha ish rejimlari amalga oshiriladi. Eng keng tarqalgan rejimlar:
· Elektron kod kitobi (Elektron kod kitobi) - ECB;
· Raqamli bloklar zanjiri (Cipher Block Chaining) - CBC;
· Raqamli teskari aloqa (Cipher Feedback) - CFB;
· Tashqi teskari aloqa (Chiqish bo'yicha teskari aloqa) - OFB.
Ushbu rejimda M manba fayli 64 bitli bloklarga bo'linadi (har biri 8 bayt): M \u003d M (1) M (2) ... M (n). Ushbu bloklarning har biri bir xil shifrlash tugmachasi yordamida mustaqil ravishda shifrlanadi (5-rasm). Ushbu algoritmning asosiy afzalligi uning amalga oshirilish qulayligi. Kamchilik - malakali kriptanalizatorlarga nisbatan nisbatan zaif qarshilik.
DES (Ma'lumotlarni shifrlash standarti) - Simmetrik shifrlash algoritmi, unda bitta kalit ma'lumotni shifrlash va parolini hal qilish uchun ishlatiladi. DES IBM tomonidan ishlab chiqilgan va 1977 yilda AQSh hukumati tomonidan rasmiy standart sifatida tasdiqlangan (FTPS 46-3). DES-da 64-bitli bloklar va 16-bosqichli Feistel tarmoq tuzilishi mavjud; u shifrlash uchun 56-bitli kalitdan foydalanadi. Algoritmda chiziqli bo'lmagan (S-qutilar) va chiziqli (almashtirishlar E, IP, IP-1) kombinatsiyalaridan foydalaniladi. DES uchun bir nechta rejimlar tavsiya etiladi:Shifrni bloklash
Blok shifrining kirish ma'lumotlari n-bitli blok va k-bitli kalit hisoblanadi. Chiqish paytida, shifrlash transformatsiyasini qo'llaganidan so'ng, n-bitli shifrlangan blok olinadi va kirish ma'lumotlarining ahamiyatsiz farqlari odatda natijada sezilarli o'zgarishlarga olib keladi. Blokirovka shifrlari ba'zi bir asosiy transformatsiyalarni birlamchi matn bloklariga qayta-qayta qo'llash orqali amalga oshiriladi.Asosiy konversiyalar:
Feistel Network Transforms
Bu smenali registrning chap va o'ng yarmini ifodalovchi vektorlar (bloklar) bo'yicha o'zgarishdir. DES shifrlashda oldinga Feistel konvertatsiyasidan foydalanadi (1-rasmga qarang) va teskari Feistel konvertatsiyasini parolini echishga (2-rasmga qarang).
DES-ni shifrlash sxemasi
Asl matn 64 bitli blokdan iborat. Shifrlangan matn 64 bitli blokdan iborat.
Shifrlash jarayoni dastlabki almashtirish, 16 shifrlash tsikli va yakuniy almashtirishdan iborat.
DES algoritmining batafsil diagrammasini ko'rib chiqamiz:
L i R i \u003d 1,2 \\ ldots.Li R i 64-bitli blokning chap va o'ng yarimlari
k i - 48 bitli tugmalar
f - shifrlash funktsiyasi
IP - dastlabki almashtirish
IP -1 - bu oxirgi almashtirish. 
Jadvalga ko'ra, IP-ning dastlabki joylashtirilishidan so'ng hosil bo'lgan IP (T) blokining dastlabki 3 biti T kirish blokining 58, 50, 42 bitlari va uning oxirgi 3 bitlari kirish blokining 23, 15, 7 bitlari. Bundan tashqari, 64-bitli IP (T) blok Feistel konvertatsiyasining 16 tsiklida qatnashadi.
Feistelning 16 tsikli:
IP (T) ni L 0, R 0 ikki qismiga bo'ling, bu erda L 0, R 0 - 32 ta eng muhim bit va T0 blokining 32 ta eng muhim bitlari (T) \u003d L 0 R 0
T i -1 \u003d L i -1 R i -1 (i-1) takrorlanish natijasi bo'lsin, keyin i-chi takrorlash natijasi T i \u003d L i R i aniqlanadi:
L i \u003d R i - 1 L i ning chap yarmi oldingi L i - 1 R i - 1 vektorining o'ng yarmiga teng. Va R i ning o'ng yarmi L i - 1 va f (R i - 1, k i) modul 2 ning bit qo'shilishi.
16 tsikli Feistel konvertatsiyasida f funktsiyasi shifrlash rolini o'ynaydi. F funktsiyasini batafsil ko'rib chiqamiz.
$ F $ uchun argumentlar - bu 32 bitli vektor R i - 1, 48 bitli k i, bu 56 bitli asl shifr k ning o'zgarishi natijasidir.
F funktsiyasini hisoblash uchun kengayish funktsiyasi E, S-qutilarning 8 ta transformatsiyasidan tashkil topgan S transformatsiyasi va P permutatsiyasi qo'llaniladi.
E funktsiya 32 bitli vektor R i - 1 dan 48 bitli vektor E (R i - 1) ni ba'zi bitlarni R i - 1 dan takrorlash orqali kengaytiradi, shu bilan E (R i - 1) vektor bitlarining tartibi 2-jadvalda ko'rsatilgan. 
E vektorining dastlabki uchta biti (R i - 1) R i -1 vektorining 32, 1, 2 bitlari. 2-jadvalda 1, 4, 5, 8, 9, 12, 13, 16, 17, 20, 21, 24, 25, 28, 29, 32 bitlar takrorlanganligi ko'rsatilgan. E vektorining so'nggi 3 biti (Ri - 1) R i - 1 vektorining 31, 32, 1 bitlari. O'zgartirilgandan so'ng olingan E (R i -1) blokga k i tugmachalari bilan 2 modul qo'shiladi va keyin ketma-ket sakkizta B 1, B 2, ... B 8 bloklari sifatida ifodalanadi.
E (R i - 1) \u003d B 1 B 2 ... B 8
Har bir B j 6-bitli blokdir. Bundan tashqari, B j bloklarning har biri S j transformatsiyalaridan foydalangan holda 4-bitli B "j blokga aylantiriladi. S j o'zgarishlari 3-jadval bilan aniqlanadi. B 3 \u003d 101111 va biz B" 3 ni topmoqchimiz. B 3 ning birinchi va oxirgi bitlari bu a sonining ikkilik yozuvi, 0 f (R i - 1, ki) funktsiyasining qiymati (32 bit) 32 bitli B "1 B" 2 ... B "8 blokiga tatbiq etilgan P almashtirish orqali olinadi. P 4-jadval orqali berilgan. 
f (R i - 1, k i) \u003d P (B "1 B" 2 ... B "8)
4-jadvalga binoan f funktsiyasi ta'siridan keyin hosil bo'lgan vektorning dastlabki to'rt biti B "1 B" 2 ... B "8 vektorining 16, 7, 20, 21 bitlari.
K i tugmachalarini yaratish.
K i kalitlari shu tarzda dastlabki k dan olinadi (56 bit \u003d 7 bayt yoki ASCII da 7 ta belgi). 8, 16, 24, 32, 40, 48, 56, 64 pozitsiyalarida topilgan sakkiz bit k kalitiga qo'shiladi, shunda har bir baytda toq sonda bittasi bo'ladi. Bu kalitlarni almashtirish va saqlashdagi xatolarni aniqlash uchun ishlatiladi. Keyin kengaytirilgan tugmachani o'chiring (qo'shilgan 8, 16, 24, 32, 40, 48, 56, 64 bitlaridan tashqari). Ushbu almashtirish 5-jadvaldagi kabi aniqlangan. 
Ushbu almashtirish har biri 28 bit bo'lgan ikkita C 0 va D 0 bloklari bilan belgilanadi. C 0 ning dastlabki 3 biti kengaytirilgan kalitning 57, 49, 41 bitlari. Va D 0 ning dastlabki uchta biti kengaytirilgan kalitning 63, 55, 47 bitlari. C i, D i i \u003d 1,2,3 ... 6-jadvalga binoan C i - 1, D i - 1 dan bir yoki ikkita chap tsiklik siljishlar bilan olinadi. 
K i, i \u003d 1, ... 16 kaliti 7-jadvalga muvofiq C i D i (56 bit) vektorining bitlaridan tanlangan 48 bitdan iborat. Birinchi va ikkinchi bitlar i i C i D i vektorining 14, 17 bitlari. 
Oxirgi IP-1 almashtirish T 16 da ishlaydi va holatni tiklash uchun ishlatiladi. Bu IP-ni almashtirishning teskari tomoni. Yakuniy almashtirish 8-jadval orqali aniqlanadi. 
DES foydalanish rejimlari DES to'rt rejimda ishlatilishi mumkin.
Ma'lumotlarni shifrlash standarti (DES) - bu AQShda 1980 yillarda ixtiro qilingan ma'lumotlarni shifrlash standarti. Shifrlar orasida u haqli ravishda "nafaqaga chiqqan" deb hisoblanadi, shu bilan birga kriptografiyaning oti bo'lib qoladi. DES ultra tezkor texnologiya va katta miqdordagi ma'lumotlar sharoitida foydali bo'lishni to'xtatdi, chunki har bir kalit uchun 56 bit va ma'lumotlar uchun 64 bit. Biroq, u hali ham ishlatilmoqda.
Blok shifrlari nima?
DES - bu blok shifrlash algoritmi. So'nggi 20-30 yil ichida ko'plab blok shifrlari yaratildi, ammo xavfsiz bo'lgan yaxshi shifr yaratish qiyin vazifa. Shifrning ko'plab sohalarda va sohalarda ishlashiga imkon beradigan xususiyatlarga ega bo'lishi muhimdir.
Blok shifrlari bir nechta shifrlarni o'z navbatida ishlatishning bir necha takrorlanishidan iborat. Har bir takrorlash dumaloq deyiladi. Amaliyot shuni ko'rsatadiki, hatto ba'zi bir ibtidoiy algoritmlar ketma-ket ishlatilganda ishonchli shifrlarni yaratishga qodir. DES 20 yildan beri ishonchli va buzilmasdan saqlanib kelinayotgan misoldir.
Shifrlarni ishlab chiqishda ushbu yondashuv jarayonni sezilarli darajada osonlashtiradi va xavfsizlik tahlilini soddalashtiradi. Masalan, blok shifrga o'tkazilgan sinov hujumi minimal sonli turdan boshlanadi va uslubiy ravishda tur sonining ko'payishi bilan davom etadi.
DES-dan foydalanish
DES eskirgan va zamonaviy emasligiga qaramay, masalan, uchburchak ketma-ket uch marta qo'llanganda, masalan, 3DES shaklida foydalanish mumkin. Ushbu yondashuv kalit o'lchamidagi cheklovni olib tashlaydi, ammo shifrlangan ma'lumotlar bloki bir xil bo'ladi. Bir paytlar DES juda tezkor va kuchli kripto shifrlari bo'lgan. Endi bunday emas va 3DES aslida uch baravar sekinroq. Shunga qaramay, DES hali ham bir qator tizimlarda qo'llaniladi, ammo uni yangi loyihalarda qo'llash taqiqlanadi.
DES 1998 yilgacha Qo'shma Shtatlarda rasmiy shifrlash algoritmi edi. 1997 yilda System) deb nomlangan yangi standartni yaratish boshlandi va kriptanaliz DESni buzishga urinish ko'plab chiziqli tenglamalar tizimiga olib kelishini ko'rsatsa-da, analitik usullar muammoni hal qilishga yordam bera olmaydi - uning zaif tomoni bu mumkin bo'lgan tugmachalarning kichik to'plamidir. Ularning soni 2 56 ga teng va barcha variantlarni nisbatan qisqa vaqt ichida zamonaviy texnologiyalar yordamida sanab o'tish mumkin.
Algoritmda bitta tur
Taqdimotning aniqligi va DES algoritmining tavsifi uchun biz bitta turning tuzilishini ko'rsatuvchi 4.1-rasmdan (hisob-kitoblarning chiziqli diagrammasi) foydalanamiz.
Chiziqli diagrammadagi har bir to'rtburchak qandaydir hisob-kitoblarni aks ettiradi va undan chiqadigan o'q blok natijalari qaerga uzatilishini bildiradi. Doira ichiga kiritilgan plyus belgisi dasturlashda XOR nomi bilan ma'lum bo'lgan "eksklyuziv yoki" operatsiyani bildiradi. Amaliyot, shuningdek, "bitli qo'shimchalar" yoki "tashishsiz qo'shish" deb nomlanadi. Tarmoqda siz DES algoritmini C da topishingiz va uni yaxshiroq tushunish uchun o'rganishingiz mumkin.
DES 64-bitli matn blokini qabul qiladi. U ma'lum bir printsipga muvofiq dastlabki almashtirishdan o'tadi. Algoritmni tahlil qilganda, bu almashtirishda hech qanday ma'no yo'qligi aniqlandi, chunki u hech qanday kriptografik effekt bermaydi. Matn bloki ikkita teng qismga bo'lingan: o'ng (R) va chap (L). Keyin shifrlangan qismlar almashtiriladi va birlashtiriladi va raund oxirida 64 bitli ma'lumotlar bloki olinadi, faqat shifrlanadi.
Umumiy algoritm
DES algoritmi yuqorida tavsiflangan sxema bo'yicha bajarilgan 16 turni o'z ichiga oladi. Barcha turlar i orqali raqamlanadi, bu erda i \u003d (1; 16). (Li-1, Ri-1) juftligidan har bir i-chi turda Ki tugmachasi yordamida yangi juftlik (Li, Ri) olinadi. Asosiy o'zgarishlar F funktsiyasi ichida sodir bo'ladi.
F funktsiyasining algoritmi
4.1-rasmdan ko'rinib turibdiki, R Expand operatsiyasidan o'tadi. Ushbu blok R ning bir nechta bitlarini takrorlaydi va ular bilan qo'shilib, 48 bitli qiymatga ega bo'ladi. Olingan natija 48 bitli Ki tugmachasi bilan bitikli qo'shimchadan o'tadi. Va ushbu operatsiya natijasi S. blokiga o'tkaziladi. B blok S 8 ta kichik almashtirish matritsalarini o'z ichiga oladi, ular maxsus usulda tanlanadi.
Har bir matritsa kirish sifatida 6 bit ma'lumot oladi va 4 bitli qiymatni chiqaradi. Natijada S bloki kirishda 48 bitli ma'lumotlarni qabul qiladi va chiqishda u natijani 32 bitli qiymat sifatida ifodalaydi.
Ushbu 32-bitlik qiymat yana bitta almashtirish operatsiyasidan o'tib, so'ngra u L bilan xor operatsiyasi bilan yig'iladi. Nihoyat, o'ng va chap tomonlar almashtiriladi va dumaloq uchlari tugaydi. Avval aytib o'tganimizdek, algoritm 16 ta shunday turni tashkil qiladi.
Bu erda biz maqolani juda ko'p joy egallaydigan misollar bilan ortiqcha yuklamaymiz. DES ishi va misollarini tarmoqdan ko'rish mumkin.
Feystel shifri
DES Feistel shifriga asoslangan. Uning g'oyasi juda oqlangan. Har bir turda L qismi F (R, Ki) qiymati bilan qo'shiladi va L pozitsiyani R bilan o'zgartiradi. Feystel algoritmining asosiy xususiyati shundaki, parol hal qilish va shifrlash bir xil bosqichlardan iborat: L va R qismlari almashtiriladi, so'ngra L qo'shilish amallari bajariladi. va F (R, Ki). Bu shifrlash va parol hal qilish protseduralarini sodda va tushunarli qiladi.
Feystel shifrlarida ko'pincha bitta qiziqarli o'zgarish kiritiladi - oxirgi takrorlanishda L va R permutatsiyasini bekor qilish. Bu shifrlash va parol hal qilish algoritmlarini to'liq nosimmetrik qiladi. Faqatgina farq Ki tugmalaridan foydalanish tartibida. Ushbu tamoyil dasturiy ta'minot darajasida foydalanish uchun juda qulay bo'lib chiqdi, chunki shifrlash va parol hal qilish bitta funktsiya yordamida amalga oshiriladi. Masalan, C da DES shifrlash algoritmining lakonik bajarilishi.
Shifrlash kalitlari
Ma'lumotlarni shifrlash uchun DES o'n oltita 48 bitli tugmachalardan foydalanadi. Har bir turda bitta kalit. Har bir kalit 56 bitli asosiy kalitdan 48 bitni tanlab olish orqali hosil bo'ladi. Belgilangan tur uchun kalitlarni yaratish DES hujjatlarida batafsil tavsiflangan mexanizm bilan belgilanadi.
Qisqacha, i tugmachasini olish algoritmi quyidagicha. Bitlar asosiy kalitga 8, 16, 24, 32, 40, 48, 56, 64 pozitsiyalarida qo'shiladi. Bu shunday amalga oshiriladiki, har bir baytda toq sonli bittasi bo'lishi kerak. Qoidalarga rioya qilish asosiy almashinuv xatolarini aniqlashda yordam beradi. Keyinchalik, maxsus jadvallar yordamida to'ldirilgan kalit qo'shilgan bitlar bundan mustasno, almashtirish va siljishlarga uchraydi. Shunday qilib, kerakli kalit olinadi.
DES komponentlari
DES algoritmining har bir komponenti ma'lum bir masalani hal qiladi:
- Feystel algoritmi shifrlash va parol hal qilishni soddalashtiradi, shu bilan birga matnning ikkala yarmi ham aralashganligini ta'minlaydi.
- Matn qismlarini tugmachalar yordamida bitikli yig'indisi umumiy ma'lumotlarni kalit bilan aralashtirib, ularni shifrlaydi.
- S-box va qidirish jadvallari algoritmni chiziqli emas qilib, uni turli xil hujumlarga chidamli qiladi.
- Kengayish, S-box va permutations algoritmning tarqalishini ta'minlaydi - ko'chki effekti. Boshqacha qilib aytganda, agar F funktsiyasining kirish ma'lumotlarida kamida 1 bit o'zgarsa, u holda bu bir vaqtning o'zida ko'plab bitlarning o'zgarishiga olib keladi. Agar shifrda ko'chki effekti kuzatilmasa, u holda ochiq ma'lumotlarning o'zgarishi kuzatilgan va yorilish uchun ishlatilishi mumkin bo'lgan shifrlangan shaklda teng o'zgarishlarga olib keladi. Kriptografiyada qor ko'chkisi ta'sirining mezonlari mavjud. Agar 1 bitli ochiq ma'lumotlar o'zgarganda shifrlangan ma'lumotlarning kamida yarmi o'zgarsa, algoritm uni qondiradi. DES algoritmi uni 4-turdan boshlab qondiradi. Xulosa - DES shifridagi 1 bit ochiq ma'lumotni o'zgartirish 29 bitni o'zgartiradi.
DES-dagi xavfsizlik muammolari
DES bilan bog'liq aniq muammo ochiq kalitdan shifrlash kalitlarini olishdir. Agar kalit sifatida nol qiymat tanlansa (tugmachaning barcha bitlari 0 ga teng bo'lsa) nima bo'ladi? Bu har bir turda shifrlash uchun barcha kalitlarning namunasi bir xil bo'lishiga va barcha kalitlarning nolga teng bo'lishiga olib keladi. 16 ta shifrlash bitta kalit bilan o'tibgina qolmay, balki DES shifrlash va parol hal qilish algoritmlari faqat kalitlarning ishlatilish tartibida farq qilishi sababli ular aynan bir xil bo'ladi. Shifrlashning butun nuqtasi yo'qoladi.
DES-da 4 ta tugmachalar mavjud bo'lib, ular zaif tugmachalar deb nomlanadi va bu tasvirlangan effektga olib keladi. DES-da 12 ta yarim zaif va 48 ta psevdo-zaif tugmachalar mavjud bo'lib, ular yaratilgan tugmachalarning turlarda o'zgarishini cheklaydi. Boshqacha qilib aytganda, 16 turda shifrlash jarayonida 16 xil tugmachalardan emas, balki 8, 4 yoki hatto 2 dan foydalanish imkoniyati mavjud.
DESning unchalik aniq ko'rinmaydigan kamchiliklari bu to'ldiruvchi xususiyatdir. Bu shuni anglatadiki, agar siz oddiy matnni to'ldiruvchi va shifrlash uchun kalit qo'shimchadan foydalansangiz, natijada siz shifrlangan matnning to'ldiruvchisi bo'lgan qiymatga ega bo'lasiz. Ushbu bema'ni xususiyat xavfsizlik uchun DES dan foydalanadigan loyihalarga muvaffaqiyatli hujumlarga olib kelishi mumkin.
Shifrlash kaliti muammosi
Bu DES uchun juda muhimdir va uni tark etishning asosiy sababi hisoblanadi. DES-dagi kalit hajmi 56 bit bo'lganligi sababli, barcha tugmachalarni takrorlash uchun siz 2 56 variantni ko'rib chiqishingiz kerak. Bu juda ko'pmi?
Agar biz soniyada 10 million kalit tekshirishni amalga oshiradigan bo'lsak, unda tekshirish taxminan 2000 yil davom etadi. Algoritm juda ishonchli ko'rinadi. O'tgan asrda, xuddi shunday kuchga ega kompyuterni yaratish texnik va moliyaviy nuqtai nazardan deyarli imkonsiz vazifa bo'lganida edi.
Agar siz million chipli kompyuter yaratadigan bo'lsangiz, DES tugmalarining butun to'plami orqali takrorlash uchun 20 soat vaqt ketadi. DES algoritmidan foydalanib parolini hal qilish uchun ushbu turdagi birinchi kompyuter 1998 yilda paydo bo'ldi va bu vazifani 56 soat ichida bajardi. Tarmoqlarning zamonaviy texnologiyalari va parallel jarayonlar bu vaqtni yanada qisqartirishi mumkin.
Kriptanaliz va DES
Mubolag'asiz aytish mumkinki, DES tomonidan "Kriptografik tahlil" nomli amaliy fan paydo bo'ldi. DES paydo bo'lishining boshidanoq uni buzishga urinishlar qilingan, uni o'rganish bo'yicha ilmiy ishlar olib borilgan. Bularning barchasi matematikaning quyidagi yo'nalishlarini tug'ilishiga olib keldi:
- chiziqli kriptanaliz - oddiy matn va shifr matni o'rtasidagi munosabatni o'rganish va aniqlash;
- differentsial kriptanaliz - bir nechta ochiq matnlar va ularning shifrlangan versiyalari o'rtasidagi bog'liqlikni o'rganish va tahlil qilish;
- bog'langan kalitlarda kriptanaliz - birlamchi kalitda va birlamchi bilan bog'langan kalitlarda biron-bir tarzda olingan shifr matnlari o'rtasidagi bog'liqlikni o'rganish.
DES butun dunyo bo'ylab 20 yillik kriptanaliz va hujumlarga qarshi turdi, ammo kuchli shifr bo'lib qolmoqda. Ammo izlagan har doim topadi ...
- Isroillik olimlar Biham va Shamir 1991 yilda differentsial kriptoanaliz yordamida DESga hujum qilish mumkinligini ko'rsatib o'tdilar, unda kalit hisoblanadiki, tajovuzkorda oddiy matn va shifrlangan 247 juftlik mos keladi.
- Yapon olimi Mitsuru Matsui 1993 yilda kalitni chiziqli kriptanaliz yordamida hisoblash mumkinligini ko'rsatdi. Buning uchun siz faqat 247 juft oddiy matnni va tegishli shifrlangan variantni bilishingiz kerak.
Keyinchalik, ushbu xakerlik usullari biroz takomillashtirildi, takomillashtirildi va soddalashtirildi va bir qator yangi xakerlik usullari paydo bo'ldi. Ammo ular juda murakkab bo'lib qolmoqda, ularning fonida barcha asosiy variantlarning to'liq ro'yxati DES-ga eng munosib hujumga o'xshaydi.
Izoh: Shaxsiy kalitlarning eng yaxshi tanilganlaridan biri bu DES - Ma'lumotlarni Shifrlash Standarti. Ushbu tizim birinchi bo'lib ma'lumotlarni shifrlash sohasida davlat standarti maqomini oldi. Amerikaning eski DES standarti endi rasmiy maqomini yo'qotgan bo'lsa-da, kriptografiyani o'rganishda ushbu algoritm hali ham e'tiborga loyiqdir. Bundan tashqari, ushbu ma'ruzada er-xotin DES nima ekanligini, o'rtada uchrashish hujumi va uni qanday tuzatish kerakligi tushuntiriladi. Xuddi shu ma'ruzada blokirovka shifrlari uchun AQShning yangi standarti - Rijndael algoritmi haqida qisqacha gap boradi.
Ma'ruzaning maqsadi: Talabani DES shifrlash algoritmi asoslari bilan tanishtirish.
Asosiy ma'lumotlar
Kriptografik tizimning taniqli shaxsiy kalitlaridan biri DES - Ma'lumotlarni shifrlash standarti... Ushbu tizim birinchi bo'lib ma'lumotlarni shifrlash sohasida davlat standarti maqomini oldi. U IBM firmasi mutaxassislari tomonidan ishlab chiqilgan va 1977 yilda AQShda kuchga kirgan. Algoritm DES turli xil hisoblash tizimlari o'rtasida ma'lumotlarni saqlash va uzatish uchun keng foydalaniladi; pochta tizimlarida, elektron chizma tizimlarida va elektron almashinuvda tijorat ma'lumotlari... Standart DES ham dasturiy ta'minot, ham apparat ta'minotini amalga oshirdi. Turli mamlakatlar korxonalari raqamli qurilmalardan foydalangan holda ommaviy ishlab chiqarishni yo'lga qo'ydilar DES ma'lumotlarni shifrlash uchun. Barcha qurilmalar standartga muvofiqligi uchun majburiy sertifikatdan o'tdilar.
Ma'lum vaqtdan beri ushbu tizim davlat standarti maqomiga ega bo'lmaganiga qaramay, u hali ham keng qo'llanilib kelinmoqda va shaxsiy kalit bilan blok shifrlarini o'rganishda e'tiborga loyiqdir.
Algoritmdagi kalit uzunligi DES 56 bit. Qobiliyat bilan bog'liq bo'lgan asosiy tortishuvlar aynan shu haqiqat bilan DES turli xil hujumlarga qarshi turing. Ma'lumki, shaxsiy kalitga ega bo'lgan har qanday blok shifrini barcha mumkin bo'lgan tugmalar birikmasini sinab ko'rish orqali buzish mumkin. Kalit uzunligi 56 bit bo'lsa, 2 56 xil tugma mumkin. Agar kompyuter bir soniyada 1000000 tugmachani sanab chiqsa (bu taxminan 2 20 ga teng bo'lsa), unda hamma 2 56 ta tugmachani takrorlash uchun 2 36 soniya yoki ikki ming yildan sal ko'proq vaqt talab etiladi, bu, albatta, bosqinchilar uchun qabul qilinishi mumkin emas.
Biroq, nisbatan qimmatroq va tezroq hisoblash tizimlari mumkin shaxsiy kompyuter... Misol uchun, agar siz parallel hisoblash uchun million protsessorni birlashtirish qobiliyatiga ega bo'lsangiz, unda maksimal kalit tanlash vaqti taxminan 18 soatgacha qisqartiriladi. Bu vaqt unchalik katta emas va bunday qimmat texnika bilan jihozlangan kriptanalizator oqilona vaqt ichida DES-shifrlangan hujumni amalga oshirishi mumkin.
Shu bilan birga, tizimni ta'kidlash mumkin DES kichik va o'rta o'lchamdagi dasturlarda juda kam qiymatga ega ma'lumotlarni shifrlash uchun yaxshi qo'llanilishi mumkin. Milliy ahamiyatga ega bo'lgan yoki muhim tijorat qiymatlari tizimidagi ma'lumotlarni shifrlash uchun DES hozirda, albatta, ishlatilmasligi kerak. 2001 yilda Qo'shma Shtatlarda maxsus e'lon qilingan tanlovdan so'ng blok shifrlash uchun yangi standart qabul qilindi AES (kengaytirilgan shifrlash standarti), bu shifrga asoslangan edi Rijdaelbelgiyalik mutaxassislar tomonidan ishlab chiqilgan. Ushbu shifr ma'ruza oxirida muhokama qilinadi.
asosiy parametrlar DES: blok hajmi 64 bit, kalit uzunligi 56 bit, tur soni - 16. DES bu ikkita shoxli klassik Feistel tarmog'i. Algoritm bir necha turda ma'lumotlarning 64 bitli kirish blokini 64 bitli chiqish blokiga o'zgartiradi. Standart DES almashtirish, almashtirish va gammingni birgalikda ishlatish asosida qurilgan. Shifrlangan ma'lumotlar ikkilik shaklda bo'lishi kerak.
Shifrlash
Umumiy tuzilish DES rasmda ko'rsatilgan. 4.1. Manba ma'lumotlarining har bir 64-bitli bloki uchun shifrlash jarayonini uch bosqichga bo'lish mumkin:
- ma'lumotlar blokini dastlabki tayyorlash;
- "Asosiy tsikl" ning 16 tur;
- ma'lumotlar blokini yakuniy qayta ishlash.
Birinchi bosqichda, dastlabki almashtirish Matnning 64-bitli manba bloki, uning davomida bitlar ma'lum tartibda tartiblanadi.
Keyingi (asosiy) bosqichda blok ikki qismga (filiallarga) bo'linadi, ularning har biri 32 bit. To'g'ri filial ba'zi funktsiyalar yordamida o'zgartiriladi F va mos keladigan qisman kalitmaxsus shifrlash algoritmi yordamida asosiy shifrlash kalitidan olingan. Keyin ma'lumotlar blokning chap va o'ng filiallari o'rtasida almashinadi. Bu ko'chadan 16 marta takrorlanadi.
Nihoyat, uchinchi bosqichda, asosiy tsiklning o'n olti qadamidan keyin olingan natija qayta tuziladi. Ushbu almashtirish birinchi almashtirishga teskari.
Shakl: 4.1.
Kriptografik transformatsiyaning barcha bosqichlarini standart bo'yicha batafsil ko'rib chiqamiz DES.
Birinchi bosqichda 64-bitli asl ma'lumotlar bloki dastlabki almashtirishga uchraydi. Adabiyotda bu operatsiya ba'zan "oqartirish" deb nomlanadi. Dastlabki almashtirishda ma'lumotlar blokining bitlari ma'lum tartibda tartiblanadi. Ushbu operatsiya asl xabarga biroz "tasodifiylik" beradi va kriptanalizni statistik usullar bilan ishlatish imkoniyatini kamaytiradi.
Ma'lumotlar blokining dastlabki almashtirilishi bilan bir vaqtning o'zida kalitning 56 bitli dastlabki almashinuvi amalga oshiriladi. Anjir. 4.1. har bir turda mos keladigan 48 bitli qisman K i ishlatilganligini ko'rish mumkin. K i tugmachalari ma'lum bir algoritmga muvofiq, boshlang'ich tugmachaning har bir bitidan bir necha marta foydalanib olinadi. Har bir turda 56-bitli kalit 28-bitli ikkiga bo'linadi. Keyin yarmlar dumaloq raqamga qarab chapga bir yoki ikkita bit bilan siljiydi. Shiftdan keyin 56 bitdan 48 tasi ma'lum bir tarzda tanlanadi. Bu nafaqat bitlarning pastki qismini tanlabgina qolmay, balki ularning tartibini o'zgartirganligi sababli, bu operatsiya "siqish bilan almashtirish" deb nomlanadi. Natijada 48 bitlik to'plam mavjud. O'rtacha, asl 56-bitli kalitning har bir biti 16 ta pastki tugmachadan 14 tasida ishlatiladi, ammo barcha bitlar bir xil marta ishlatilmaydi.
Keyinchalik, asosiy transformatsiya aylanishi Feistel tarmog'i bo'yicha tashkil etilgan va 16 ta bir xil turdan iborat. Bunday holda, har bir turda (4.2-rasm) oraliq 64-bitli qiymat olinadi, keyinchalik keyingi bosqichda ishlov beriladi.
Shakl: 4.2.
Har bir oraliq qiymatning chap va o'ng tarmoqlari L va R bilan belgilanadigan alohida 32 bitli qiymatlar sifatida ko'rib chiqiladi.
Birinchidan, R i blokining o'ng tomoni permutatsiyani va 16 bitli kengaytmani belgilaydigan jadval yordamida 48 bitgacha kengaytiriladi. Ushbu operatsiya XOR operatsiyasi uchun kalit o'lchamiga mos keladigan o'ng yarmini o'zgartiradi. Bundan tashqari, ushbu operatsiyani bajarish orqali natijaning barcha bitlarining asl ma'lumotlarning bitlariga va kalitiga bog'liqligi tezroq oshadi (bu "ko'chki effekti" deb nomlanadi). Bir yoki boshqa shifrlash algoritmidan foydalanganda ko'chki effekti qanchalik kuchli bo'lsa, shuncha yaxshi bo'ladi.
Permutatsiyani kengayish bilan amalga oshirgandan so'ng, natijada 48-bitli qiymat 48-bitli pastki kalit bilan XORed qilinadi. Keyin hosil bo'lgan 48-bitlik qiymat S o'rnini bosuvchi blok (ingliz tilidan) kiritilishiga beriladi. O'zgartirish - almashtirish), natija bu 32-bitli qiymat. Almashtirish sakkizta almashtirish qutilarida yoki sakkizta S-qutilarda amalga oshiriladi. Ushbu DES-ni qog'ozga qo'yish juda qiyin ko'rinadi, dasturiy ta'minotni amalga oshirish u yoqda tursin! To'g'ri va maqbul ishlaydigan dasturni to'liq mos ravishda ishlab chiqing DES, ehtimol, buni faqat tajribali dasturchilar amalga oshirishi mumkin. Dasturiy ta'minotni amalga oshirishda ba'zi bir qiyinchiliklar paydo bo'ladi, masalan, dastlabki almashtirish yoki kengaytirilgan almashtirish. Ushbu qiyinchiliklar dastlab uni amalga oshirish rejalashtirilganligi bilan bog'liq DES faqat apparat. Standartda ishlatiladigan barcha operatsiyalar apparat birliklari tomonidan osonlikcha bajariladi va amalga oshirishda hech qanday qiyinchilik tug'dirmaydi. Biroq, standart nashr etilgandan bir muncha vaqt o'tgach, dasturiy ta'minot ishlab chiquvchilari chetda turmaslikka qaror qildilar va shuningdek, shifrlash tizimlarini yaratishni boshladilar. Kelajakda DES apparat va dasturiy ta'minotda ham amalga oshiriladi.
