Kõige tavalisem ja tuntuim sümmeetriline krüpteerimisalgoritm on DES (Andmete krüptimise standard). Algoritm töötati välja 1977. aastal ja 1980. aastal võeti standardina kasutusele NIST (National Institute of Standards and Technology, USA).
DES on klassikaline kahe haruga Feishteli võrk. Andmed krüpteeritakse 64-bitistes plokkides, kasutades 56-bitist võtit. Algoritm teisendab 64-bitise sisendi mitme vooruga 64-bitiseks väljundiks. Võtme pikkus on 56 bitti. Krüpteerimisprotsess koosneb neljast etapist. Esimene samm on 64-bitise tavateksti esialgne permutatsioon (IP) (valgendamine), mille käigus bitid järjestatakse ümber vastavalt standardtabelile. Järgmine etapp koosneb 16 sama funktsiooni voorust, mis kasutab nihke- ja asendusoperatsioone. Kolmandas etapis vahetatakse viimase (16.) iteratsiooni väljundi vasak ja parem pool. Lõpuks viiakse neljandas etapis läbi kolmandas etapis saadud tulemuse IP-1 permutatsioon. IP-1 permutatsioon on algse permutatsiooni pöördväärtus.
Joonis 4. DES algoritm
Joonisel on kujutatud meetod, mis kasutab 56-bitist võtit. Esialgu suunatakse võti permutatsioonifunktsiooni sisendisse. Seejärel on iga 16 vooru alamvõti K i vasakpoolse tsüklilise nihke ja permutatsiooni kombinatsioon. Permutatsioonifunktsioon on iga vooru jaoks sama, kuid iga vooru alamvõtmed K i on klahvibittide korduva nihutamise tõttu erinevad.
Algne permutatsioon ja selle pöördväärtus määratakse standardtabeliga. Kui M on suvaline 64 bitti, siis X = IP(M) – permuteeritud 64 bitti. Kui rakendame pöördpermutatsiooni funktsiooni Y = IP-1 (X) = IP-1 (IP(M)), saame algse bitijada.
Ümmarguse des kirjeldus
Mõelge igas voorus kasutatavate teisenduste järjestusele.
Joonis 5. Illustratsioon DES-algoritmi voorust
64-bitine sisendplokk läbib 16 ringid, samas kui igal iteratsioonil saadakse 64-bitine vahepealne väärtus. Iga vaheväärtuse vasakut ja paremat osa käsitletakse eraldi 32-bitiste väärtustena, mida tähistatakse L ja R. Iga iteratsiooni saab kirjeldada järgmiselt:
R i = L i -1 F(R i -1, K i)
Seega on L i vasaku poole väljund võrdne R i-1 parema poole sisendiga. R i parema poole väljund on XORing L i-1 ja funktsiooni F tulemus, mis sõltub R i-1 ja K i .
Vaatleme funktsiooni F üksikasjalikumalt. Funktsiooni F sisendisse söödetud R i pikkus on 32 bitti. Esiteks laiendatakse R i 48-bitiseni, kasutades tabelit, mis määratleb permutatsiooni pluss 16-bitise laienduse. Laienemine käib nii. 32 bitti jagatakse 4-bitisteks rühmadeks ja seejärel laiendatakse 6-bitiseks, lisades kahe külgneva rühma äärmised bitid. Näiteks kui osa sisendsõnumist
Efgh ijkl mnop . . .
siis on laiendamise tulemuseks sõnum
Defghi hijklm lmnopq . . .
Saadud 48-bitine väärtus tehakse seejärel 48-bitise alamvõtmega K i XOR. Saadud 48-bitine väärtus sisestatakse seejärel asendusfunktsiooni, mille tulemuseks on 32-bitine väärtus.
Asendus koosneb kaheksast S-kastist, millest igaüks saab sisendiks 6 bitti ja väljundina toodab 4 bitti. Need teisendused on määratletud spetsiaalsete tabelitega. S-kasti sisendväärtuse esimene ja viimane bitt määravad tabelis rea numbri, keskmised 4 bitti määravad veeru numbri. Rea ja veeru ristumiskoht määrab 4-bitise väljundi. Näiteks kui sisend on 011011, siis on rea number 01 (rida 1) ja veeru number 1101 (veerg 13). 1. rea ja 13. veeru väärtus on 5, st. väljund on 0101.
Järgmisena töödeldakse saadud 32-bitist väärtust permutatsiooni P abil, mille eesmärk on bittide järjestus võimalikult ümber paigutada nii, et järgmises krüpteerimisvoorus töötleks iga bitti suure tõenäosusega erinev S. - kast.
Ühe vooru K i võti koosneb 48 bitist. Võtmed K i saadakse järgmise algoritmiga. Algoritmi sisendina kasutatav 56-bitine võti permuteeritakse esmalt vastavalt tabelile Permuted Choice 1 (PC-1). Saadud 56-bitine võti jagatakse kaheks 28-bitiseks osaks, mida tähistatakse vastavalt kui C0 ja D0. Igal ringil pööratakse C i ja D i olenevalt vooru numbrist sõltumatult 1 või 2 biti võrra vasakule. Saadud väärtused on järgmise vooru sisend. Need on ka sisendiks funktsioonile Permuted Choice 2 (PC-2), mis loob 48-bitise väljundväärtuse, mis on funktsiooni F(R i-1 , K i) sisend.
Dekrüpteerimisprotsess sarnaneb krüpteerimisprotsessiga. Algoritm kasutab sisendina šifriteksti, kuid võtmeid K i kasutatakse vastupidises järjekorras. Esimesel ringil kasutatakse K 16, viimasel ringil K 1. Olgu i-nda krüpteerimisvooru väljundiks L i ||R i . Siis on (16-i)-nda dekrüpteerimise vooru vastav sisend R i ||L i .
Pärast dekrüpteerimisprotsessi viimast vooru vahetatakse väljundi kaks poolt nii, et lõpliku permutatsiooni IP-1 sisendiks on R 16 ||L 16 . Selle etapi väljund on lihttekst.
Märkus: Üks tuntumaid privaatvõtmega krüptosüsteeme on DES – Data Encryption Standard. See süsteem sai esimesena andmete krüptimise valdkonnas riikliku standardi staatuse. Ja kuigi vana Ameerika DES-standard on nüüdseks oma ametliku staatuse kaotanud, väärib see algoritm krüptograafiat uurides siiski tähelepanu. Lisaks selgitatakse selles loengus, mis on "topelt-DES", "meet in the middle" rünnak ja kuidas seda parandada. Samas loengus räägitakse põgusalt USA uuest plokkšifri standardist, Rijndaeli algoritmist.
Loengu eesmärk: tutvustada õpilasele DES-i krüpteerimisalgoritmi põhiteavet.
Põhiandmed
Üks kuulsamaid privaatvõtmega krüptosüsteeme on DES – andmete krüptimise standard. See süsteem sai esimesena andmete krüptimise valdkonnas riikliku standardi staatuse. Selle töötasid välja IBMi spetsialistid ja see jõustus USA-s 1977. aastal. Algoritm DES laialdaselt kasutatav andmete salvestamisel ja edastamisel erinevate arvutisüsteemide vahel; postisüsteemides, elektroonilistes joonistussüsteemides ja elektroonilises teabevahetuses äriteave. Standard DES rakendatud nii tarkvaras kui riistvaras. Erinevate riikide ettevõtted on käivitanud digiseadmete masstootmise DES andmete krüptimiseks. Kõik seadmed läbisid standardile vastavuse kohustusliku sertifikaadi.
Hoolimata asjaolust, et sellel süsteemil pole mõnda aega olnud riigistandardi staatust, kasutatakse seda endiselt laialdaselt ja see väärib privaatvõtmega plokkšifrite uurimisel tähelepanu.
Võtme pikkus algoritmis DES on 56 bitti. See on see, et peamine vaidlus seoses võimega DES seista vastu erinevatele rünnakutele. Nagu teate, saab kõiki privaatvõtmega plokkšifreid murda, proovides kõiki võimalikke klahvikombinatsioone. 56-bitise võtme pikkusega on võimalikud 256 erinevat võtit. Kui arvuti loetleb ühe sekundi jooksul 1 000 000 võtit (mis on ligikaudu võrdne 220-ga), kulub kõigi 256 klahvi loetlemiseks 236 sekundit ehk veidi rohkem kui kaks tuhat aastat, mis on ründajate jaoks loomulikult vastuvõetamatu.
Küll aga kallimad ja kiiremad arvutussüsteemid kui Personaalarvuti. Näiteks kui paralleelarvutuseks on võimalik kombineerida miljon protsessorit, siis lüheneb maksimaalne võtmevaliku aeg ligikaudu 18 tunnini. See aeg ei ole liiga pikk ja nii kallite seadmetega varustatud krüptoanalüütik suudab mõistliku aja jooksul hõlpsalt sooritada DES-krüpteeritud rünnaku.
Samas võib märkida, et süsteem DES saab hästi kasutada väikestes ja keskmistes rakendustes väheväärtuslike andmete krüptimiseks. Riikliku tähtsusega või olulise kaubandusliku väärtusega andmete krüpteerimiseks süsteem DES praegu muidugi kasutada ei tohiks. 2001. aastal võeti pärast spetsiaalselt väljakuulutatud konkurssi USA-s vastu uus plokkšifri standard, nn. AES (täiustatud krüpteerimisstandard), mis põhines šifril Rijndael välja töötanud Belgia spetsialistid. Seda šifrit käsitletakse loengu lõpus.
Peamised seaded DES: ploki suurus 64 bitti, võtme pikkus 56 bitti, voorude arv - 16. DES on klassikaline kahe haruga Feishteli võrk. Algoritm teisendab 64-bitise sisendandmete ploki 64-bitiseks väljundplokiks mitmes voorus. Standard DES ehitatud permutatsiooni, asendamise ja gamutimise kombineeritud kasutamisele. Krüptitud andmed peavad olema binaarses vormis.
Krüpteerimine
Üldine struktuur DES näidatud joonisel fig. 4.1. Iga lähteandmete 64-bitise ploki krüptimise protsessi saab jagada kolme etappi:
- andmeploki esialgne ettevalmistamine;
- 16 "põhitsükli" ringi;
- andmeploki lõplik töötlemine.
Esimeses etapis, esialgne permutatsioon 64-bitine algne tekstiplokk, mille käigus bitid on teatud viisil ümber järjestatud.
Järgmises (peamises) etapis jagatakse plokk kaheks 32-bitiseks osaks (haruks). Parempoolne haru teisendatakse mõne funktsiooni F ja vastava abil osaline võti, mis saadakse peamisest krüpteerimisvõtmest spetsiaalse võtme teisendusalgoritmi abil. Seejärel toimub andmete vahetus ploki vasaku ja parema haru vahel. Seda korratakse tsükli jooksul 16 korda.
Lõpuks muudetakse kolmandas etapis pärast põhiahela kuueteistkümne sammu läbimist saadud tulemust. See permutatsioon on vastupidine algsele permutatsioonile.
Riis. 4.1.
Vaatleme üksikasjalikumalt kõiki krüptograafilise teisendamise etappe vastavalt standardile DES.
Esimeses etapis läbib 64-bitine lähteandmete plokk esialgse permutatsiooni. Kirjanduses nimetatakse seda operatsiooni mõnikord "valgendamiseks" - valgendamiseks. Algse permutatsiooni käigus järjestatakse andmeploki bitid teatud viisil ümber. See toiming annab algsele sõnumile teatud "juhuslikkuse", vähendades võimalust kasutada krüptoanalüüsi statistiliste meetodite abil.
Samaaegselt andmeploki esialgse permutatsiooniga teostatakse võtme 56 biti esialgne permutatsioon. Jooniselt fig. 4.1. on näha, et igas voorus kasutatakse vastavat 48-bitist osavõtit K i. Klahvid K i saadakse kindla algoritmi järgi, kasutades mitu korda algvõtme iga bitti. Igas voorus jagatakse 56-bitine võti kaheks 28-bitiseks pooleks. Seejärel nihutatakse pooli ühe või kahe löögi võrra vasakule, olenevalt vooru numbrist. Pärast nihet valitakse 56 bitist 48 teatud viisil. Kuna see mitte ainult ei vali bittide alamhulka, vaid muudab ka nende järjekorda, nimetatakse seda toimingut "vahetus-vahetus" operatsiooniks. Selle tulemuseks on 48-bitine komplekt. Keskmiselt kasutatakse algse 56-bitise võtme iga bitti 16-st alamvõtmest 14-s, kuigi kõiki bitte ei kasutata sama arv kordi.
Järgmisena viiakse läbi peamine teisendustsükkel, mis on korraldatud vastavalt Feishteli võrgule ja koosneb 16 identsest voorust. Sel juhul saadakse igas voorus (joonis 4.2) 64-bitine vaheväärtus, mida seejärel järgmises voorus töödeldakse.
Riis. 4.2.
Iga vaheväärtuse vasakut ja paremat haru käsitletakse eraldi 32-bitiste väärtustena, mida tähistatakse L ja R .
Esiteks laiendatakse R i ploki parem pool 48-bitiseks, kasutades tabelit, mis määratleb permutatsiooni pluss 16-bitise laienduse. See toiming reguleerib parema poole suurust, et see vastaks XOR-toimingu tegemiseks kasutatava võtme suurusele. Lisaks suureneb selle toimingu täitmise tõttu kiiremini tulemuse kõigi bittide sõltuvus algandmete ja võtme bittidest (seda nimetatakse "laviiniefektiks"). Mida tugevam on laviiniefekt ühe või teise krüpteerimisalgoritmi kasutamisel, seda parem.
Pärast laienduspermutatsiooni teostamist XOR-datakse saadud 48-bitine väärtus 48-bitise alamvõtmega K i . Seejärel juhitakse saadud 48-bitine väärtus asendusploki S sisendisse (inglise keelest. Asendamine - asendamine), tulemus mis on 32-bitine väärtus. Asendamine toimub kaheksas asenduskastis või kaheksas S-kastis. Selle DES-i täitmisel tundub see paberil üsna keeruline, rääkimata selle tarkvara rakendamisest! Töötage välja korrektselt ja optimaalselt töötav programm täielikult kooskõlas DES ilmselt ainult kogenud programmeerijatele. Teatud raskused tekivad tarkvara juurutamisel, näiteks esialgne permutatsioon või laienduspermutatsioon. Need raskused on seotud asjaoluga, et see oli algselt kavas ellu viia DES ainult riistvaras. Kõik standardis kasutatavad toimingud on riistvaraüksuste poolt hõlpsasti teostatavad ja rakendamisel pole raskusi. Kuid mõni aeg pärast standardi avaldamist otsustasid tarkvaraarendajad mitte kõrvale jääda ja asuda ka krüpteerimissüsteemide loomisele. Edasi DES rakendatud nii riist- kui ka tarkvaras.
DES-algoritmi kasutuselevõtust USA krüpteerimisstandardina on möödunud üle 30 aasta. DES on kõige rikkalikuma ja huvitavama ajalooga krüpteerimisalgoritm.
Algoritmi loomise ajalugu
Maailma üks kuulsamaid krüptolooge Bruce Schneier kirjeldas oma kuulsas raamatus Applied Cryptography 70ndate alguse infoturbe tööriistade kasutajate probleeme nii. XX sajand (muidugi räägime kasutajatest teisel pool raudset eesriiet):
Puudusid ei üldtunnustatud andmete krüptimise standardid ega lihtsalt laialdaselt kasutatavad infoturbe algoritmid, mistõttu ei tulnud kõne allagi erinevate krüpteerimistarkvarade või -riistvarade ühilduvus;
Peaaegu iga krüpteerimistööriist oli üsna ebaselge sisuga “must kast”: millist krüpteerimisalgoritmi kasutatakse, kui tugev see on krüptograafiliselt, kas see on õigesti rakendatud, kas krüpteerimisvõtmeid luuakse, salvestatakse, kasutatakse õigesti, kas on mingeid dokumenteerimata funktsioone. arendajate poolt tööriistasse sisestatud jne – kogu see väga oluline teave polnud valdavale enamusele krüptotööriistade ostjatest kättesaadav.
See probleem on lahendanud USA riikliku standardibüroo (NBS). Selle tulemusena kuulutati 1973. aastal välja esimene krüpteerimisstandardi avalik konkurss. NBS oli valmis standardi valimiseks uurima taotleja algoritme, mis vastavad järgmistele kriteeriumidele:
Algoritm peab olema krüptograafiliselt tugev;
Algoritm peab olema kiire;
Algoritmi struktuur peaks olema selge ja täpne;
Krüptimise tugevus peaks sõltuma ainult võtmest, algoritm ise ei tohiks olla salajane;
Algoritm peaks olema erinevatel eesmärkidel hõlpsasti rakendatav;
Algoritm peaks olema hõlpsasti rakendatav riistvaras olemasoleva elemendi baasil.
Eeldati, et huvitatud organisatsioonid või spetsialistid saadavad NBS-ile üksikasjalikud algoritmide spetsifikatsioonid, mis on piisavad nende rakendamiseks, st ilma "valgete laikudeta". Samuti eeldati, et NBS sertifitseerib algoritmi üldiseks kasutamiseks, sellelt eemaldatakse kõik patendi- ja ekspordipiirangud, mille tulemusena peaks selline standard lahendama kõik krüpteerimisvahendite ühilduvuse probleemid. Lisaks võttis NBS üle krüpteerimisvahendite sertifitseerimise funktsioonid – ehk siis "mustad kastid" oleksid pidanud pöördumatult minevikku jääma.
Tegelikult oli ainult üks taotleja algoritm: see oli CMM-i poolt välja töötatud Luciferi krüpteerimisalgoritm (vt punkt 3.31). Kahe aasta jooksul viimistleti algoritmi:
Esiteks viis NBS koos Ameerika Ühendriikide riikliku julgeolekuagentuuriga (NSA, NSA – National Security Agency) läbi algoritmi põhjaliku analüüsi, mille tulemuseks oli selle üsna oluline töötlemine;
Teiseks võeti arvesse kõigi huvitatud organisatsioonide ja üksikisikute kommentaarid ja kriitika.
IBM-i, NBS-i ja NSA ühistöö tulemusena avaldati DES 1977. aasta jaanuaris USA standardina (selle standardi uusim versioon on dokumendis) andmete krüpteerimisalgoritmi jaoks (välja arvatud kõrgetasemeline teave). salastatuse aste). DES-algoritmi patenteeris UM, kuid tegelikult sai NBS selle algoritmi kasutamiseks tasuta ja piiramatu litsentsi. Algoritmi alternatiivne, kuid harvem kasutatav nimi on DEA (Data Encryption Algorithm).
Algoritmi põhiomadused ja struktuur
DES-algoritm krüpteerib teabe 64-bitistes plokkides, kasutades 64-bitist krüpteerimisvõtit, mis kasutab ainult 56 bitti (võtme laiendamise protseduuri kirjeldatakse üksikasjalikult allpool).
Teabe krüpteerimine toimub järgmiselt (joonis 3.56):
1. Esialgne permutatsioon teostatakse 64-bitise andmeploki kaudu vastavalt tabelile. 3.16.
Tabel 3.16
Tabelit tõlgendatakse järgmiselt: sisendbiti 58 väärtus (edaspidi nummerdatakse kõik bitid vasakult paremale, alustades 1-st) asetatakse väljundbiti 1, biti 50 väärtus asetatakse bitti 2 jne.
2. Eelmise toimingu tulemus jagatakse kaheks 32-bitiseks alamplokiks (per
riis. 3.56 märgitud A 0 ja B 0), millele tehakse 16 ringi
järgmised teisendused:
Nagu eespool mainitud, kasutab DES-algoritm 64-bitisest krüpteerimisvõtmest ainult 56 bitti. Iga 8. bitt jäetakse kõrvale ja seda ei kasutata kuidagi algoritmis ning krüpteerimisvõtme ülejäänud bittide kasutamine DES-algoritmi teostustes ei ole standardiga piiratud. 64-bitise võtme 56 olulise biti eraldamise protseduur joonisel fig. 3.59 on tähistatud kui E. Lisaks ekstraheerimisele teostab see protseduur ka võtmebittide permutatsiooni vastavalt tabelile. 3.19 ja 3.20.
Tabel 3.19
Tabel 3.20
Permutatsiooni tulemusena moodustuvad kaks 28-bitist väärtust C ja D. Tabel 3.19 määratleb võtmebittide valiku C jaoks, tabel. 3.20 - eest D.
Seejärel sooritatakse 16 teisendusringi, millest igaüks annab ühe ümmarguse võtme K t . Võtme laiendamise protseduuri igas voorus tehakse järgmised toimingud:
1. C ja D pöörata vasakule muutuva arvu bittide võrra P. 1., 2., 9. ja 16. vooru jaoks P= 1, ülejäänud voorud pööratakse 2 bitti.
2. Koos ja D kombineeritakse 56-bitiseks väärtuseks, millele rakendatakse tihenduspermutatsiooni CP, mille tulemuseks on 48-bitine ümarklahv K (. Tihenduspermutatsioon viiakse läbi vastavalt tabelile 3.21.
Tabel 3.21
Andmete dekrüpteerimisel saate kasutada sama võtme laiendamise protseduuri, kuid rakendada ümaraid võtmeid vastupidises järjekorras. On veel üks võimalus: klahvi laiendusprotseduuri igas voorus tehke ringikujulise vasakule nihutamise asemel ringikujuline nihe n biti võrra paremale, kus rc' = 0 esimese ringi jaoks ja '=1 2. ringi jaoks , 9, 16 ja n = 2 ülejäänud voorude jaoks . Selline võtme laiendamise protseduur annab kohe dekrüpteerimiseks vajalikud ümarad võtmed.
Tasub öelda, et võtme laiendamise võimalust (eriti kui see võimalus on olemas nii krüpteerimise kui ka dekrüpteerimise ajal) peetakse krüpteerimisalgoritmide eeliseks, kuna sel juhul saab võtme laiendamist teostada paralleelselt krüpteerimisega ja mitte raisata. mälu muude võtmete salvestamiseks, muud ringid peale praeguse.
- õpetus
Tere %username%!
Paljud inimesed teavad, et DES-algoritmi on pikka aega peetud sümmeetrilise krüptimise valdkonna vaikestandardiks. Esimene edukas rünnak selle hävimatu algoritmi vastu avaldati 1993. aastal, 16 aastat pärast selle standardiks võtmist. Meetod, mida autor nimetas lineaarseks krüptoanalüüsiks, 2 47 paari lihttekstide/šifritekstide olemasolul võimaldab avada DES šifri salajase võtme 2 43 operatsiooniga.
Lõike all püüan kokku võtta selle rünnaku põhipunktid.
Lineaarne krüptoanalüüs
Lineaarne krüptoanalüüs on eriliik sümmeetriliste šifrite vastu suunatud rünnak, mille eesmärk on teadaolevatest avatud sõnumitest ja neile vastavatest šifritekstidest tundmatu krüpteerimisvõtme taastamine.Üldjuhul taandatakse lineaarsel krüptoanalüüsil põhinev rünnak järgmistele tingimustele. Ründajal on suur hulk lihtteksti/šifreeritud teksti paare, mis on saadud sama krüpteerimisvõtme K abil. Ründaja eesmärk on taastada võti K osaliselt või täielikult.
Kõigepealt uurib ründaja šifrit ja leiab nn. statistiline analoog, st. järgmise kujuga võrrand, mis kehtib tõenäosusega P ≠ 1/2 suvalise avaliku/privaatse tekstipaari ja fikseeritud võtme puhul:
P I1 ⊕ P I2 ⊕… ⊕ P Ia ⊕ C I1 ⊕ C I2 ⊕… ⊕ C Ib = K I1 ⊕ K I2 ⊕… ⊕ K Ic (1)
,
kus P n , C n , K n on teksti, šifriteksti ja võtme n-ndad bitid.
Pärast sellise võrrandi leidmist saab ründaja järgmise algoritmi abil taastada 1 biti teavet võtme kohta
Algoritm 1
Olgu T tekstide arv, mille puhul võrrandi (1) vasak pool on 0, siis
Kui T>N/2, kus N on teadaolevate tavatekstide arv.
Oletame, et K I1 ⊕ K I2 ⊕… ⊕ K Ic = 0 (kui P>1/2) või 1 (kui P<1/2).
Muidu
Oletame, et K I1 ⊕ K I2 ⊕… ⊕ K Ic = 1 (kui P>1/2) või 0 (kui P<1/2).
Ilmselt sõltub algoritmi edukus otseselt |P-1/2| väärtusest ja saadaolevate tavateksti/privaatteksti paaride N arvu kohta. Mida rohkem võrdsuse (1) tõenäosus P erineb 1/2-st, seda väiksem on rünnakuks vajalike lihttekstide arv N.
Rünnaku edukaks rakendamiseks tuleb lahendada kaks probleemi:
- Kuidas leida vormi (1) efektiivset võrrandit.
- Kuidas sellise võrrandi abil võtme kohta rohkem kui ühe bitti teavet saada.
DES kirjeldus
Kuid kõigepealt kirjeldame lühidalt, kuidas algoritm töötab. DES-ist on piisavalt räägitud. Šifri täieliku kirjelduse leiate Vikipeediast. Rünnaku täiendavaks selgitamiseks vajame aga mitmeid määratlusi, mida on kõige parem eelnevalt tutvustada.Niisiis, DES on Feisteli võrgul põhinev plokkšifr. Šifri ploki suurus on 64 bitti ja võtme suurus 56 bitti. Mõelge DES-algoritmi krüpteerimisskeemile. 
Nagu jooniselt näha, tehakse tekstiga krüptimise ajal järgmised toimingud:
- Esialgne bitivahetus. Selles etapis segatakse sisendploki bitid kindlas järjekorras.
- Pärast seda jagatakse segatud bitid kaheks pooleks, mis suunatakse Feisteli funktsiooni sisendisse. Tavalise DES jaoks sisaldab Feisteli võrk 16 ringi, kuid algoritmil on ka teisi variante.
- Viimases teisendusvoorus saadud kaks plokki kombineeritakse ja saadud plokile tehakse veel üks permutatsioon.
Feisteli võrgu igas voorus edastatakse kõige vähem olulised 32 bitti sõnumist funktsiooni f: 
Mõelge selles etapis tehtud toimingutele:
- Sisendplokk juhitakse läbi laiendusfunktsiooni E, mis muudab 32-bitise ploki 48-bitiseks.
- Saadud plokk lisatakse ümarklahvile K i .
- Eelmise sammu tulemus jagatakse 8 plokiks, millest igaüks on 6 bitti.
- Iga saadud plokk B i juhitakse läbi asendusfunktsiooni S-Box i , mis asendab 6-bitise jada 4-bitise plokiga.
- Saadud 32-bitine plokk lastakse läbi permutatsiooni P ja tagastatakse funktsiooni f tulemusel.
Meie jaoks pakuvad šifri krüptoanalüüsi seisukohalt suurimat huvi S-plokid, mis on mõeldud funktsiooni f sisend- ja väljundandmete vahelise seose varjamiseks. DES-i edukaks ründamiseks koostame esmalt iga S-kasti jaoks statistilised vasted ja seejärel laiendame neid kogu šifrile.
S-plokkide analüüs
Iga S-kast võtab sisendiks 6-bitise jada ja iga sellise jada jaoks tagastatakse fikseeritud 4-bitine väärtus. Need. Kokku on 64 sisend- ja väljundvalikut. Meie ülesandeks on näidata seost S-plokkide sisend- ja väljundandmete vahel. Näiteks DES-šifri kolmanda S-kasti puhul on sisendjada 3. bitt võrdne väljundjada 3. bitiga 38 juhul 64-st. Seetõttu leidsime kolmanda S-i jaoks järgmise statistilise analoogi -kast:S 3 (x) = x, mis on täidetud tõenäosusega P=38/64.
Võrrandi mõlemad pooled esindavad 1 bitti teavet. Seega, kui vasak ja parem osa oleksid üksteisest sõltumatud, peaks võrrand olema täidetud tõenäosusega, mis on võrdne 1/2-ga. Seega demonstreerisime just DES-algoritmi 3. S-kasti sisendite ja väljundite vahelist seost.
Mõelge, kuidas saate üldjuhul leida S-kasti statistilise analoogi.
S-kasti S a, 1 ≤ α ≤ 63 ja 1 ≤ β ≤ 15 korral kirjeldab väärtus NS a (α, β), mitu korda S sisendbittide 64-st võimalikust XOR-st on bitid α kattuvad. on võrdsed väljundbittide XOR-ga, mis on kaetud bittidega β, st:
kus sümbol on loogiline JA.
α ja β väärtused, mille puhul NS a (α, β) erineb kõige rohkem 32-st, kirjeldavad S-kasti S a kõige tõhusamat statistilist analoogi.
Kõige tõhusam analoog leiti DES-šifri 5. S-kastis, kui α = 16 ja β = 15 NS 5 (16, 15) = 12. See tähendab, et järgmine võrrand on tõene: Z=Y ⊕ Y ⊕ Y ⊕ Y, kus Z on S-kasti sisendjada ja Y on väljundjada.
Või võttes arvesse asjaolu, et DES-algoritmis lisatakse enne S-kasti sisestamist andmed modulo 2 ümara võtmega, st. Z = X ⊕ K saame
X ⊕ Y ⊕ Y ⊕ Y ⊕ Y = K, kus X ja Y on funktsiooni f sisend- ja väljundandmed ilma permutatsioonideta.
Saadud võrrand täidetakse DES-algoritmi kõikides voorudes sama tõenäosusega P=12/64.
Järgmises tabelis on loetletud efektiivsed, s.o. millel on suurim kõrvalekalle P=1/2, statistilised analoogid iga DES-algoritmi s-ploki jaoks. 
Statistiliste analoogide loomine mitme DES-vooru jaoks
Näitame nüüd, kuidas saab kombineerida mitme DES-i vooru statistilisi analooge ja selle tulemusena saada statistiline analoog kogu šifri jaoks.Selleks kaaluge algoritmi kolmevoorulist versiooni:
Kasutame 5. s-kasti efektiivset statistilist analoogi väärtuse X(2) teatud bittide arvutamiseks.
Teame, et tõenäosusega 12/64 rahuldab f-funktsioon võrdsust X ⊕ Y ⊕ Y ⊕ Y ⊕ Y = K, kus X on 5. S-kasti teine sisendbitt, siis sisuliselt on see pärast sisendbittide laiendamist saadud jada 26. bitt. Laiendusfunktsiooni analüüsides saab kindlaks teha, et X(1) jada 17. bitt osutub biti 26 asemele.
Samamoodi on Y,…, Y sisuliselt 17., 18., 19. ja 20. bitt jadast, mis on saadud enne permutatsiooni P. Uurides P permutatsiooni, leiame, et Y,…, Y bitid on tegelikult bitid Y(1 ), Y(1), Y(1), Y(1).
Võrranditesse kaasatud võtmebitt K on esimese ringi K1 26. alamvõtmebitt ja seejärel on statistiline vaste järgmisel kujul:
X(1) ⊕ Y(1) ⊕ Y(1) ⊕ Y1 ⊕ Y(1) = K1.
Seega X(1) ⊕ K1 = Y(1) ⊕ Y(1) ⊕ Y(1) ⊕ Y(1)(2) tõenäosusega P=12/64.
Teades Y(1) jada 3, 8, 14, 25 bitti, võite leida X(2) jada 3, 8, 14, 25 bitti:
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = PL ⊕ PL ⊕ PL ⊕ PL ⊕ Y(1) ⊕ Y(1) ⊕ Y(1) ⊕ Y(1) või võttes arvesse võrrandit (2)
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = PL ⊕ PL ⊕ PL ⊕ PL ⊕ X(1) ⊕ K1 (3) tõenäosusega 12/64.
Leiame viimase vooru abil sarnase väljendi. Seekord on meil võrrand
X(3) ⊕ K3 = Y(3) ⊕ Y(3) ⊕ Y(3) ⊕ Y(3).
Sest
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = СL ⊕ СL ⊕ СL ⊕ СL ⊕ Y(3) ⊕ Y(3) ⊕ Y(3) ⊕ Y(3)
me saame sellest aru
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = СL ⊕ СL ⊕ СL ⊕ СL ⊕ X(3) ⊕ K3(4)
tõenäosusega 12/64.
Võrdsustades võrrandite (3) ja (4) õiged osad saame
СL ⊕ СL ⊕ СL ⊕ СL ⊕ X(3) ⊕ K3 = PL ⊕ PL ⊕ PL ⊕ PL ⊕ X(1) ⊕ K1 tõenäosusega (12/64) 2 + (1-12/64) 2 .
Võttes arvesse asjaolu, et X(1) = PR ja X(3) = CR, saame statistilise analoogi
СL ⊕ CR ⊕ PL ⊕ PR = K1 ⊕ K3 (5)
,
mis sooritatakse tõenäosusega (12/64) 2 +(1-12/64) 2 =0,7.
Ülalkirjeldatud statistilist analoogi saab graafiliselt kujutada järgmiselt (joonisel on bitid nummerdatud paremalt vasakule ja alustades nullist): 
Kõik võrrandi vasakpoolsed bitid on ründajale teada, nii et ta saab rakendada algoritmi 1 ja leida K1 ⊕ K3 väärtuse. Näitame, kuidas selle statistilise analoogi abil on võimalik krüpteerimisvõtme K avada mitte 1, vaid 12 bitti.
Rünnak DES-ile teadaoleva lihttekstiga
Siin on viis, kuidas saate rünnakut laiendada ja saada kohe 6 bitti esimese ringi alamvõtmest.Võrrandi (5) koostamisel võtsime arvesse asjaolu, et me ei tea F1(PR, K1) väärtust. Seetõttu kasutasime selle statistilist analoogi K1 ⊕ PR.
Avaldise K1 ⊕ PR asemel tagastame väärtuse F1(PR, K1) ja saame järgmise võrrandi:
CL ⊕ CR ⊕ PL ⊕ F1(PR, K1) = K3 (6) , mis täidetakse tõenäosusega 12/64. Tõenäosus on muutunud, kuna jätsime kolmandast voorust ainult statistilise analoogi, kõik muud väärtused on fikseeritud.
Oleme juba eespool kindlaks teinud, et F1(PR, K1) väärtust mõjutavad 5. S-kasti sisendbitid, nimelt võtme K1 bitid ja PR ploki bitid. Näitame, kuidas ainult avatud/suletud tekstide komplektiga saab taastada K1 väärtuse. Selleks kasutame algoritmi 2.
Algoritm 2
Olgu N enne rünnakut teadaolevate avatud/suletud tekstipaaride arv. Seejärel peate võtme avamiseks tegema järgmised toimingud.
For (i=0; i<64; i++) do
{
For(j=0; j
if(СL j ⊕ CR j ⊕ PL j ⊕ F1(PR j , i)=0) siis
T i = T i +1
}
}
Tõenäolise jadana K1 võetakse selline i väärtus, mille puhul avaldis |T i -N/2| on maksimaalne väärtus.
Piisava arvu teadaolevate tavatekstide korral tagastab algoritm suure tõenäosusega esimese ringi alamvõtme K1 kuue biti õige väärtuse. Seda seletatakse asjaoluga, et kui muutuja i ei ole võrdne K1-ga, on funktsiooni F1(PR j , K) väärtus juhuslik ja võrrandite arv sellise i väärtuse jaoks, mille vasak pool on võrdne nulliga, kaldub N/2. Kui alamvõti arvatakse õigesti, võrdub vasakpoolne osa fikseeritud bitiga K3 tõenäosusega 12/64. Need. on oluline kõrvalekalle N/2-st.
Olles saanud K1 alamvõtme 6 bitti, saate samamoodi avada K3 alamvõtme 6 bitti. Selleks on vaja ainult asendada võrrandis (6) C P-ga ja K1 K3-ga:
PL ⊕ PR ⊕ CL ⊕ F3(CR, K3) = K1.
Algoritm 2 tagastab K3 õige väärtuse, kuna DES-algoritmi dekrüpteerimisprotsess on identne krüpteerimisprotsessiga, vaid võtmete jada on vastupidine. Nii et esimeses dekrüpteerimisvoorus kasutatakse võtit K3 ja viimasel ringil võtit K1.
Olles saanud 6 bitti alamvõtmeid K1 ja K3, taastab ründaja 12 bitti šifri K ühisest võtmest, kuna ümmargused võtmed on klahvi K tavaline permutatsioon. Edukaks rünnakuks vajalike lihttekstide arv sõltub statistilise vaste tõenäosusest. 12-bitise 3-ringilise DES-võtme murdmiseks piisab 100 avaliku/privaatse tekstipaarist. 12-bitise 16-ringilise DES-võtme murdmiseks oleks vaja umbes 244 paari teksti. Võtme ülejäänud 44 bitti avatakse tavalise loendi abil.
Algoritm DES
DES-algoritmi peamised eelised:
Kasutatakse ainult ühte 56-bitist võtit;
· pärast sõnumi krüptimist ühe paketi abil saate selle dekrüpteerimiseks kasutada mis tahes muud;
Algoritmi suhteline lihtsus tagab info töötlemise suure kiiruse;
algoritmi üsna kõrge stabiilsus.
DES krüpteerib 64-bitised andmeplokid 56-bitise võtmega. Dekrüpteerimine DES-is on krüptimise pöördoperatsioon ja seda teostatakse krüpteerimisoperatsioonide kordamisega vastupidises järjekorras (vaatamata näilisele ilmselgusele seda alati ei tehta. Hiljem käsitleme šifreid, milles krüpteerimine ja dekrüpteerimine toimub erinevate algoritmide abil).
Krüpteerimisprotsess koosneb 64-bitise ploki esialgsest bitivahetusest, kuueteistkümnest krüpteerimisvoorust ja lõpuks vastupidisest bitivahetusest (joonis 1).
Kohe tuleb märkida, et KÕIK selles artiklis toodud tabelid on STANDARDID ja seetõttu tuleks need muutumatul kujul teie algoritmi juurutada. Kõik tabelites olevad permutatsioonid ja koodid valivad arendajad nii, et võtme valimisel oleks dekrüpteerimisprotsess võimalikult keeruline. DES-algoritmi struktuur on näidatud joonisel 2.
Joonis 2. DES-i krüpteerimisalgoritmi struktuur
Lugege failist järgmine 8-baidine plokk T, mis teisendatakse algse permutatsioonimaatriksi IP abil (tabel 1) järgmiselt: ploki T bitist 58 saab bitt 1, bitist 50 - bitt 2 jne, mis tulemus : T(0) = IP(T).
Saadud bitijada T(0) jagatakse kaheks 32-bitiseks jadaks: L(0) – vasak- või kõrged bitid, R(0) – parem- või madalad bitid.
Tabel 1: IP esialgne permutatsioonimaatriks
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
Seejärel teostatakse krüpteerimine, mis koosneb 16 iteratsioonist. I-nda iteratsiooni tulemust kirjeldatakse järgmiste valemitega:
R(i) = L(i-1) xvõi f(R(i-1), K(i)) ,
kus xor on tehe EXCLUSIVE VÕI.
Funktsiooni f nimetatakse krüpteerimisfunktsiooniks. Selle argumendid on (i-1)-ndal iteratsioonil saadud 32-bitine jada R(i-1) ja 48-bitine võti K(i), mis on 64-bitise võtme K teisendamise tulemus. Krüpteerimisfunktsiooni ja võtmete K(i) tuletamise algoritmi kirjeldatakse allpool.
16. iteratsioonil saadakse jadad R(16) ja L(16) (ilma permutatsioonita), mis on ühendatud 64-bitiseks jadaks R(16)L(16).
Seejärel korraldatakse selle jada bittide asukohad ümber vastavalt maatriksile IP -1 (tabel 2).
Tabel 2: IP-1 pöördpermutatsioonimaatriks
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 ja IP maatriksid on omavahel seotud järgmiselt: IP -1 maatriksi 1. elemendi väärtus on 40 ja IP maatriksi 40. elemendi väärtus on 1, 2. IP -1 maatriksi element on 8 ja 8. maatriksi elemendi IP väärtus on 2 jne.
Andmete dekrüpteerimise protsess on krüpteerimisprotsessi pöördprotsess. Kõik toimingud tuleb läbi viia vastupidises järjekorras. See tähendab, et esmalt korraldatakse dekrüpteeritavad andmed ümber vastavalt IP-1 maatriksile ja seejärel tehakse R(16)L(16) bitijadaga samad toimingud, mis krüpteerimisprotsessis, kuid vastupidises järjekorras.
Iteratiivset dekrüpteerimisprotsessi saab kirjeldada järgmiste valemitega:
R(i-1) = L(i), i = 1, 2, ..., 16;
L(i-1) = R(i) x või f(L(i), K(i)), i = 1, 2, ..., 16.
16. iteratsioonil saadakse jadad L(0) ja R(0), mis on ühendatud 64-bitiseks jadaks L(0)R(0).
Seejärel korraldatakse selle jada bitipositsioonid ümber vastavalt IP maatriksile. Selle permutatsiooni tulemuseks on algne 64-bitine jada.
Vaatleme nüüd krüpteerimisfunktsiooni f(R(i-1),K(i)). See on skemaatiliselt näidatud joonisel fig. 3.
Joonis 3. Funktsiooni f(R(i-1), K(i)) arvutamine
Funktsiooni f väärtuse arvutamiseks kasutatakse järgmisi maatriksfunktsioone:
E - 32-bitise jada laiendamine 48-bitiseks,
S1, S2, ... , S8 - 6-bitise ploki teisendamine 4-bitiseks plokiks,
P on biti permutatsioon 32-bitises jadas.
Laiendusfunktsioon E on määratletud tabelis 3. Selle tabeli järgi on E(R(i-1)) 3 esimest bitti 32, 1 ja 2 ning viimased 31, 32 ja 1.
Tabel 3: laiendusfunktsioon 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
Funktsiooni E(R(i-1)) tulemuseks on 48-bitine jada, millele lisatakse modulo 2 (xor-operatsioon) 48-bitise võtmega K(i). Tulemuseks on 48-bitine jada, mis on jagatud kaheksaks 6-bitiseks plokiks B(1)B(2)B(3)B(4)B(5)B(6)B(7)B(8). See on:
E(R(i-1)) xvõi K(i) = B(1)B(2)...B(8) .
Funktsioonid S1, S2, ... , S8 on määratletud tabelis 4.
Tabel 4
Tabeli juurde.4. on vaja täiendavaid selgitusi. Olgu maatriksfunktsiooni Sj sisendiks 6-bitine plokk B(j) = b1b2b3b4b5b6, siis kahebitine arv b1b6 näitab maatriksi rea numbrit ja b2b3b4b5 veeru numbrit. Sj(B(j)) tulemus on 4-bitine element, mis asub määratud rea ja veeru ristumiskohas.
Näiteks B(1)=011011. Siis asub S1(В(1)) 1. rea ja 13. veeru ristumiskohas. 1. rea veerus 13 määratakse 5. Seega S1(011011)=0101.
Rakendades valikuoperatsiooni igale 6-bitisele plokile B(1), B(2), ..., B(8), saame 32-bitise jada S1(B(1))S2(B(2) ))S3( B(3))...S8(B(8)).
Lõpuks, krüpteerimisfunktsiooni tulemuse saamiseks peate selle jada bitid ümber korraldama. Selleks kasutatakse permutatsioonifunktsiooni P (tabel 5). Sisendjadas pööratakse bitid ümber nii, et bitist 16 saab bitt 1, bitist 7 bitt 2 jne.
Tabel 5: Permutatsioonifunktsioon P
Seega
f(R(i-1), K(i)) = P(S1(B(1)),...S8(B(8)))
Andmete krüpteerimisalgoritmi kirjelduse lõpetamiseks jääb üle anda algoritm 48-bitiste võtmete K(i), i=1...16 saamiseks. Igal iteratsioonil kasutatakse uut võtme väärtust K(i), mis arvutatakse algvõtmest K. K on 64-bitine plokk kaheksa paarsusbitiga, mis asuvad positsioonidel 8,16,24,32,40,48, 56, 64.
Juhtbittide eemaldamiseks ja ülejäänute ümberpaigutamiseks kasutatakse võtme esmase ettevalmistamise funktsiooni G (tabel 6).
Tabel 6
Algse võtme ettevalmistamise maatriks 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
Teisenduse tulemus G(K) jagatakse kaheks 28-bitiseks plokiks C(0) ja D(0) ning C(0) koosneb K bittidest 57, 49, ..., 44, 36 võti ja D(0 ) koosneb võtme K bitidest 63, 55, ..., 12, 4. Pärast C(0) ja D(0), C(i) ja D(i) defineerimist, i =1...16, on rekursiivselt defineeritud. Selleks rakendatakse vasakpoolset tsüklilist nihet ühe või kahe biti võrra, olenevalt iteratsiooninumbrist, nagu on näidatud tabelis 7.
Tabel 7
Nihketabel klahvi arvutamiseks
| Iteratsiooni number | Shift (bitt) |
| 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 |
Saadud väärtus "segatakse" uuesti vastavalt maatriksile H (tabel 8).
Tabel 8: Võtme viimistlusmaatriks 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
Võti K(i) koosneb jada C(i)D(i) bittidest 14, 17, ..., 29, 32. Seega:
K(i) = H(C(i)D(i))
Võtmearvutusalgoritmi plokkskeem on näidatud joonisel 4.
Joonis 4. Võtme K(i) arvutamise algoritmi plokkskeem
Algteksti taastamine toimub selle algoritmi järgi, kuid esmalt kasutate võtit
K(15), siis - K(14) ja nii edasi. Nüüd peaksite mõistma, miks autor soovitab tungivalt ülaltoodud maatriksite kasutamist. Kui hakkate omavoliliselt minema, peate hankima väga salajase šifri, kuid te ise ei saa seda hiljem avada!
DES-algoritmi töörežiimid
Kõigi kommertskrüpteerimissüsteemide nõuete võimalikult täielikuks rahuldamiseks on rakendatud mitu DES-algoritmi töörežiimi. Kõige laialdasemalt kasutatavad režiimid on:
Elektrooniline koodiraamat (Electronic Codebook) - EKP;
digitaalsete plokkide ahel (Cipher Block Chaining) - CBC;
digitaalne tagasiside (Cipher Feedback) - CFB;
Väline tagasiside (Output Feedback) – OFB.
Selles režiimis on lähtefail M jagatud 64-bitisteks plokkideks (igaüks 8 baiti): M = M(1)M(2)...M(n). Kõik need plokid on kodeeritud sõltumatult, kasutades sama krüpteerimisvõtit (joonis 5). Selle algoritmi peamine eelis on rakendamise lihtsus. Puuduseks on suhteliselt nõrk vastupidavus vilunud krüptoanalüütikute vastu.
