Algoritmus DES: popis a príklad

Štandard šifrovania údajov (DES) je štandard šifrovania údajov, ktorý bol vynájdený v Spojených štátoch v 80. rokoch dvadsiateho storočia. Medzi šiframi sa považuje za "dôchodcu", zatiaľ čo zostáva pracovným kôňom kryptografie. DES nie je vhodný pre vysokorýchlostné inžinierstvo a veľké objemy údajov kvôli obmedzeniam 56 bitov na jeden kľúč a 64 bitov na dáta. Stále sa však používa.

Čo sú blokové šifry?

DES - blokovací šifrovací algoritmus. Za posledných 20 až 30 rokov bolo vytvorených mnoho blokov, ale vytvoriť dobrú šifru, ktorá je bezpečná, je pomerne zložitá. Je dôležité, aby šifra mala vlastnosti, ktoré jej umožnia fungovať v mnohých oblastiach a odvetviach. Blokové šifry pozostávajú z niekoľkých opakovaní striedavého použitia nejakej šifry. Každá iterácia sa nazýva guľa. Ako ukazuje prax, aj niektoré primitívne algoritmy s konzistentným používaním môžu vytvoriť spoľahlivé šifry. Algoritmus DES je príkladom, ktorý zostal stabilný a nezraniteľný 20 rokov.


Tento prístup pri vývoji šifier značne uľahčuje a zjednodušuje analýzu bezpečnosti. Napríklad testovací útok na blokovú šifru začína s minimálnym počtom kôl a postupuje metodicky s nárastom počtu kôl.

Použitie DES

Aj keď je DES zastarané a nespĺňa aktuálne požiadavky, môže byť napríklad použitý ako 3DES, keď sa šifra aplikuje trikrát za sebou. Tento prístup odstraňuje obmedzenie veľkosti kľúča, ale šifrovaný dátový blok zostáva nezmenený. Vo svojom vlastnomČas DES bol dosť rýchly a kryptografický. Toto nie je práve teraz a 3DES je trikrát pomalšie. Napriek tomu sa DES stále používa v mnohých systémoch, ale jeho použitie v nových projektoch je zakázané.


Oficiálne šifrovací algoritmus DES bol štandard v Spojených štátoch až do roku 1998. V roku 1997 sa začal vytvárať nový štandard, ktorý bol nazvaný AES (Advanced Encryption System), a hoci dešifrovanie ukazuje, že pokus trhlín DES vedie k mnohým sústav nelineárnych rovníc, analytické metódy nie sú schopné pomôcť vyriešiť problém - jeho slabinou je malá množina možných kľúčov , Ich počet je 2 až 56 môže prevziať všetky možnosti s pomocou moderných technológií v relatívne krátkom čase. Algoritmus koleso

, jedna

Pre jasnosť prezentácie a opis algoritmu DES za použitia vzoru (linka graf výpočty) 4.1 znázorňuje štruktúru z jedného kola.
Každý obdĺžnik v diagrame predstavuje lineárne niektoré výpočty, aj mimo neho smerujúce šípky, ktorá bude prevedená do pracovnej jednotky. Značka plus v kruhu je označená operáciou "vylúčiť alebo" nazývanú programovanie XOR. Operácia naďalej nesie názov "bitové pridanie" alebo "pridať bez prenosu". Sieť môže nájsť algoritmus DES na C a študovať ho na lepšie pochopenie. DES prijíma 64-bitový textový blok. Prechádza počiatočným preskupením podľa určitej zásady. V algoritme analýzy sa zistilo, že má zmysel v tejto permutácie málo, pretože to nedáva akúkoľvek šifrovacie účinok. textovýJednotka je rozdelená na 2 rovnaké časti: vpravo (R) a doľava (L). Potom sa šifrované časti zmenia a zlúčia a na konci kruhového 64-bitového dátového bloku sa zašifruje.

Všeobecný algoritmus

Algoritmus DES zahŕňa 16 kôl, ktoré sa vykonávajú podľa vyššie opísanej schémy. Všetky kolá sú očíslované cez i, kde i = (1; 16). Každé i-té kolo pary (Li-1 Ri-1) dostane nový pár (Li, Ri) pomocou kľúča Ki. Hlavné transformácie prebiehajú v rámci funkcie F.

Algoritmus pre funkciu F

Ako je zrejmé z obrázku 4.1, R prechádza operáciou "Expansion". Tento blok duplikuje sériu bitov od R a dopĺňa ich s nimi a získava 48-bitovú hodnotu. Výsledný výsledok prechádza bitovým prídavkom s 48-bitovým kľúčom Ke. A výsledok tejto operácie je odovzdaný do bloku S. Blok S obsahuje 8 malých substitučných matíc, ktoré sú vybrané špeciálnym spôsobom.
Každá matica prijíma na vstupe 6 bitov informácií a vydáva 4-bitovú hodnotu. V dôsledku toho blok S prijíma 48-bitové dáta na vstupe a na výstupe je výsledok 32-bitová hodnota.
Táto 32-bitová hodnota prechádza inou permutačnou operáciou, po ktorej je sumarizovaná operáciou x alebo L. Nakoniec práva a ľavá časť menia miesta a okrúhle konce. Ako už bolo uvedené, 16 takýchto algoritmov vykonáva takéto kolá. Tu nebudeme preťažovať článok s príkladmi, ktoré zaberajú veľa priestoru. Práca šifrovacieho algoritmu DES a príklady je možné prezerať online.

Kód Fiesteelu

Algoritmus DES je založený na šifre spoločnosti Fiesteel.Jeho myšlienka je veľmi prepracovaná. Každé kolo sa skladá z L s hodnotou F (R, Ki) a zmena L pozíciu Key znaku R. Feystelya algoritmu je to, že šifrovanie a dešifrovanie rovnakých krokov, L a R sú obrátené, a potom vykonať operáciu pridanie L a F (R, Ki). To robí šifrovacie a dešifrovacie procedúry jednoduché a ľahko pochopiteľné.
V šifre Feystelya často zavádza zaujímavú zmenu - zrušenie permutácie L a R na poslednú iteráciu. To robí algoritmy šifrovania a dešifrovania úplne symetrické. Rozdiel spočíva len v použití kľúčov Ke. Tento princíp bol veľmi vhodný pre použitie na úrovni programu, pretože šifrovanie a dešifrovanie prebieha pomocou funkcie. Napríklad lakonicky DES implementácia šifrovacieho algoritmu v C

Šifrovací kľúč

pre šifrovanie dát pomocou DES šestnásť 48-bitové kľúče. Jeden kľúč na jedno kolo. Každé tlačidlo je vytvorené vzorkovaním 48 bitov z 56-bitového hlavného kľúča. Vytvorenie kľúčov alebo iných kôl je určené mechanizmom podrobne uvedeným v dokumentácii DES. Stručne povedané, algoritmus pre vzorku a kľúč je nasledujúci. Bat sa pridá do hlavného kľúča na pozícii 81624 324048 5664. To sa vykonáva tak, aby každý bajt obsahuje nepárny počet jednotiek. Dodržiavanie pravidiel pomáha identifikovať chyby pri prepínaní kľúčov. Potom pomocou špeciálneho stola, kompletný s kľúčovými zmenami a dochádza k preskupeniu, s výnimkou bitov, ktoré boli pridané. Tak takje získaný potrebný kľúč.

Komponenty DES

Každá zložka algoritmu DES rieši problém:
  • Feystelya algoritmus zjednodušuje šifrovanie a dešifrovanie, a zároveň zabezpečiť premiešanie oboch poloviciach textu.
  • Pridanie textových častí s kľúčovými rozhraniami vedľa seba otvára dáta kľúčom a šifruje ich.
  • S-blok a tabuľky zhody robia tento algoritmus nelineárny, čím zvyšuje jeho odolnosť voči rôznym útokom.
  • Rozšírenie, S-blok a permutácie poskytujú difúziu algoritmu - lavínový efekt. Inými slovami, ak sa vstupné dáta F zmenia aspoň o jeden bit, potom to spôsobí zmenu množiny bitov naraz. Ak je šifra lavínový efekt nie je pozorovaný, zmeny otvorené dát bude mať za následok zodpovedajúcu zmenu v zašifrovanej forme, ktoré môžu byť sledované a použitý pre zlom. V kryptografii existuje kritérium lavínového efektu. Algoritmus ho uspokojuje, ak sa zmení aspoň jedna polovica šifrovaných údajov pri zmene 1 bitu otvorených údajov. Algoritmus DES to vyhovuje, počínajúc 4 kruhmi. Zhrnutie - ak zmeníte 1 bit otvorených dát v šifle DES, zmení sa 29 bitov.

    Problémy s bezpečnosťou v systéme DES

    Zjavným problémom DES je výber kľúčov šifrovania so všeobecným kľúčom. Čo sa stane, ak vyberiete nulu ako kľúč (všetky kľúčové bity sú 0)? Výsledkom bude, že všetky kľúče na šifrovanie v každom kole budú rovnaké a všetky kľúče budú nulové. Nielen to, šifrovanie šifruje 16 kľúčov, pretože algoritmy šifrovania a dešifrovania DESsa líšia len v poradí používania kľúčov, budú úplne totožné. Celý význam šifrovania sa stratí.
    DES má 4 tlačidlá, ktoré sa nazývajú slabé, čo vedie k opísanému efektu. DES má 12 poloslabých a 48 pseudoslabých kľúčov, ktoré majú za následok obmedzenie variácií generovaných kľúčov v kolách. Inými slovami, je pravdepodobné, že počas šifrovania 16 kôl sa použije 16 rôznych kľúčov a 8 4 alebo dokonca 2. Menej zrejmá nevýhoda DES je vlastnosťou komplementarity. Znamená to, že ak šifrujete pomocou textových a doplnkových kľúčov s otvoreným zdrojom, potom bude výsledkom hodnota, ktorá je doplnkom šifrovaného textu. Táto nezmyselná vlastnosť môže viesť k úspešným útokom na projekty, ktoré využívajú DES na zabezpečenie bezpečnosti.

    Problém šifrovacieho kľúča

    je základom DES a je považovaný za hlavný dôvod, prečo by mal byť tento algoritmus opustený. Keďže veľkosť tlačidla DES je 56 bitov, musíte skontrolovať 2 56 možností skenovania všetkých kľúčov. Je to tak veľa? Ak vykonáte 10 miliónov kľúčových kontrol za sekundu, bude trvať asi 2000 rokov na kontrolu. Zdá sa, že algoritmus je pomerne stabilný. Bolo to tak v minulom storočí, kedy bolo vytvorenie počítača podobnej moci takmer nemožné úlohu z technického i finančného hľadiska. Ak vytvoríte počítač s miliónov čipov, hľadanie všetkých mnohých kľúčov DES bude trvať 20 hodín. Prvý takýto počítač na dekódovanie algoritmu DES sa objavil v roku 1998, čovyriešiť úlohy počas 56 hodín. Moderné technológie sietí a paralelných procesov umožňujú skrátiť čas ešte viac.

    Kryptanalýza a DES

    Je možné bez zveličenia uviesť, že DES bol príčinou vzniku aplikovanej vedy nazvanej "kryptografická analýza". Od začiatku objavenia DES boli pokusy rozbiť to, vedecká práca bola vykonaná na jeho štúdium. To všetko viedlo k vzniku takých oblastí matematiky, pretože:
  • lineárna kryptanalýza - štúdium a detekcia vzťahu medzi open source a šifrovaným;
  • diferenciálna kryptanalýza - štúdium a analýza závislosti medzi viacerými textami s otvoreným zdrojom a ich šifrovanými verziami;
  • dešifrovanie súvisiace kľúč - štúdium vzťahov medzi ciphertext získal primárne kľúče, a kľúče spojené s pôvodnou v žiadnom prípade.
  • DES trval 20 rokov globálnej kryptoanalýzy a útokov, ale zostala silnou šifrou. Ale kto hľadá - to vždy nájde
  • Byhamovo a Shamir, vedci z Izraela v roku 1991 preukázaná pomocou diferenciálnej dešifrovanie že DES možno vykonať útok, v ktorom sa počíta kľúč za predpokladu, že útok je 2 47 špeciálne vybraných párov otvorené a šifrované texty.
  • Japonský vedec Mytsuru Matsui v roku 1993 ukázala, že kľúč môže byť vypočítaná pomocou lineárnej dešifrovanie. Ak to chcete urobiť, potrebujete vedieť len 2 47 párov otvoreného textu a príslušnú zašifrovanú verziu.
  • Ďalej tieto techniky hackingu boli mierne revidované, zlepšené a zjednodušené a niekoľko novýchspôsoby zlomenia. Ale zostávajú príliš zložité, vo svojom pozadí je úplný prehľad o všetkých kľúčových možnostiach najvhodnejším útokom na DES.

    Súvisiace publikácie