Ühiskonnas hästi tuntud termin "protsessori jõudlus" on objektiivne, arvutatud parameeter, mida mõõdetakse floppides. Enamus mõõdab seda aga gigahertsides, uskudes naiivselt, et tegu on sama asjaga. Keegi ei tea terminit "koodi jõudlus" ja ma selgitan kohe, miks.

Põhjus on selles, et ma tulin selle peale alles hiljuti ja pole sellest veel kellelegi rääkinud. Kuid koodi jõudlusel, nagu protsessori jõudlusel, on objektiivsed omadused, mida saab mõõta. See artikkel käsitleb konkreetselt protsessori tuuma käivitatava koodi jõudlust.

Kuidas koodi jõudlust mõõdetakse? Kuna mina sellest esimesena rääkisin, siis avastaja õigusega mõõdan seda RTT-skaalades;).

Nüüd tõsiselt. Kaasaegsetes protsessorites on peamised teisendused toimingud 32-bitiste numbritega, kõik muu on suures plaanis eksootiline. Seetõttu võtame arvesse peamist - toiminguid 32-bitiste numbritega. Kui palju 32-bitist toimingut suudab kaasaegse protsessori tuum teie arvates üheaegselt täita?

Õpilane vastab – üks, tema õpetaja mõtleb ja ütleb, et neli, professionaal –, et siiani on tehtud vaid kaksteist operatsiooni.

Seega on programmikoodil, mis laadib kõik protsessori täitevseadmed samaaegselt kogu koodi täitmise aja jooksul, jõudlus 12 RTT NIS-i. Maksimaalne! Ausalt öeldes pole ma kunagi varem sellist koodi kirjutanud, kuid selles artiklis püüan enda kallal pingutada.

Tõestan, et kood kaheteistkümne 32-bitise operatsiooni samaaegse täitmisega on võimalik

Programmikoodil, mis kasutab protsessori tuumas ühte täitmisüksust, on loomulikult 1 RTT jõudlus. Kõrgetasemeliste keelekompilaatorite ja virtuaalmasinatõlkide loodud programmid võivad sellise koodi jõudlusega "kiidelda". Ei tohiks eeldada, et OS-i tegumihalduris kuvatav protsessori kasutamise indikaator võib olla koodi tõhususe objektiivne kriteerium. Protsessori tuumakoormus võib olla 100%, kuid programmikood kasutab selles ühte täitmisseadet (jõudlus 1 RTT). Sel juhul töötab protsessori tuum 100% koormuse korral 1/12 oma maksimaalsest jõudlusest. Teisisõnu, kui Windows Task Manager näitab maksimaalset CPU kasutust, võib selle tegelik jõudlus varieeruda vahemikus 1 kuni 12 RTT. Nähes jõudlusaknas mis tahes protsessorituuma 100% koormust, on vale eeldada, et kõik täitevseadmed töötavad selles tuumas, mitte mingil juhul!

Ainus kaudne kriteerium protsessori tuuma maksimaalse jõudluse hindamisel on selle energiatarve ja sellest tulenevalt jahuti müra. Kui nüüd jahuti mürab, siis jah - koormus on läinud maksimumi. Siiski on aeg lõpetada üldiste kontseptsioonidega ja liikuda edasi karmi praktika juurde.

GOST 28147-89 traditsiooniline rakendamine

Ma ei ole infoturbe alal professionaal, kuid krüpteerimise teemaga olen siiski kursis. Just minu vestlused professionaalse krüptograafiga, keda ma sügavalt austan, inspireerisid mind tegelema spetsiifiliselt sümmeetrilise vookrüptimisega. Ja olles selle teema üles võtnud, püüdsin seda teha hästi ja mitte ainult hästi, vaid ka kiiresti, tehes ajaühikus maksimaalse arvu toiminguid. Teisisõnu seisin silmitsi ülesandega kirjutada programmi kood maksimaalse RTT väärtusega.

Krüptograafilist teisendamist vastavalt standardile GOST 28147-89 kasutatakse teabe voogesitamiseks krüptimiseks sidekanalites ja kettaseadmetes.

Praegu kasutatakse laialdaselt selle GOST-i tarkvararakendust keskprotsessori RON-il. Tuntud GOST-i juurutamismeetodites paigutatakse kogu salajane teave (krüpteerimisvõtmed, asendusplokid) RAM-i. See vähendab krüptimise usaldusväärsust, kuna RAM-i prügila olemasolul on võimalik kõik krüptotransformatsiooni salajased elemendid täielikult paljastada. Lisaks on meetodil kiiruspiirangud, mis tulenevad krüptotransformatsiooni peamiste objektide asukohast OP-s ja ALU täitevseadmete mittetäielikust laadimisest. Kaasaegsed protsessorid, mis rakendavad krüptoprotseduuri tuntud meetodil, suudavad pakkuda krüpteerimiskiirust 40–60 megabaiti sekundis. Ja kui sa sellest tõesti lõpuni aru saad, siis krüptokonversiooni madala jõudluse ja nõrga turvalisuse põhjuseks on asendusploki tarkvaraline juurutamine. Vaadake selle kirjeldust GOST-is joonisel fig. 1.

Vastavalt GOST-i punktile 1.2 rakendab see plokk tetrad (neli bitti) permutatsioone 32-bitises sõnas, kuid protsessori x86 / 64 arhitektuur ja selle käsustik ei ole võimelised tetrade tõhusalt manipuleerima.

Asendusploki tarkvaraliseks juurutamiseks kasutatakse RAM-is spetsiaalseid tabeleid, mis koostatakse krüptofunktsiooni initsialiseerimise etapis. Need tabelid ühendavad külgnevate tetraadide asendussõlmed 8 × 8-bitiste tabelitega, seega on RAM-is neli 256-baidist tabelit.

Täpsemates rakendustes on need tabelid 1024 baiti (256 sõna neljast baidist). Seda tehakse selleks, et rakendada tabelites asendamise tulemusena saadud 32-bitise sõna täiendav tsükliline nihe 11 positsiooni võrra (järgmine teisendusalgoritmi toiming vastavalt GOST-ile). Selle meetodi GOST-i rakendamise näide on näidatud lisas 1 (kettal).

Asendusploki teave on krüptofunktsiooni salajane komponent (nagu see on sõnastatud GOST-is, vt joonis 2).

Nende tabelite paigutamine asendusploki võtmetega OP-is on vastuolus GOST-i nõuetega (punkt 1.7), kuna salajane teave muutub kättesaadavaks arvuti installimisel töötavatele kolmandate osapoolte programmidele. FSB, mis sertifitseerib ka GOST-i järgi krüptimise tarkvararakendusi, vaatab seda rikkumist pehmelt öeldes alandlikult. Kui võtmete OP-i paigutamiseks nõuab FSB ikkagi “viigilehte” - võtmete maskeerimist XOR-operatsiooniga, siis OP-i asendusplokkide jaoks pole midagi vaja, need salvestatakse selge tekstina.

Lühidalt öeldes jätab FSB sellised krüptoprotseduuri tarkvararakendused vahele, hoolimata sellise lahenduse tugevuse ilmsest vähenemisest ja oma nõuete otsesest rikkumisest vastavalt GOST-ile (punkt 1.7). Ja seda hoolimata tuntud meetoditest šifrite purustamiseks mäluprügi eemaldamise kaudu ...

Protsessori siseregistrites võtmete ja asendusplokkide hoidmise teema juurde tuleme veidi hiljem tagasi (olemas ilus ja kiire lahendus), kuid praegu salvestame krüpteerimisvõtmeid ainult MMX registritesse, nii on töökindlam.

Aga laulusõnadest piisab, vaadeldava teema raames on oluline, et selle programmikoodi jõudlus oleks 1 RTT-shku. Nüüd kirjutame koodi, mille jõudlus on 2 RTT-d.

GOST 28147-89 mitmelõimeline rakendamine

Ainus viis krüptoprotseduuride kiirendamiseks tuntud algoritmis on mitme lõimega töötlemine. Sellise algoritmi teostuse muudatuse mõte on arvutada mitu andmeplokki paralleelselt korraga.

Enamik programmeerijaid mõtleb paralleelse töötlemise all vaid mitme protsessorituuma tööd, mis on sünkroonitud mälu katkestuste ja semaforide kaudu.

Siiski on veel üks paralleelse andmetöötluse variant ühel protsessori tuumal. Lubage mul selgitada seda ebaselge mõtet.

Kaasaegsed protsessorid sisaldavad vähemalt kahte ja isegi kolme kuni kuut aritmeetilist loogikaüksust. Need ALU-d (FPU-d, aadressi aritmeetilised ühikud jne) võivad töötada üksteisest sõltumatult, nende paralleelse toimimise ainsaks tingimuseks on mittekattuvad tarkvaraobjektid, millel nad töötavad. Teisisõnu, käskudes, mis käivitavad samaaegselt ALU-d, peavad mäluaadressid ja registrinumbrid olema erinevad. Või ei tohiks teha mingeid kirjutustoiminguid tavalistele registritele ja mäluaadressidele, millele pääsevad juurde protsessori erinevad täitevseadmed.

Kõigi ALU-de töö laadimist juhib protsessori tuuma sees olev spetsiaalne riistvaraplokk – planeerija, mis vaatab läbi käivitatava koodi edasi, 32-64 baiti sügavusele. Kui planeerija leiab käsud, mida saab ALU-s konfliktideta käivitada, siis käivitab ta need samaaegselt erinevates täitmisüksustes. Sel juhul osutab täidetavate käskude loendur käivitatavale käsule (neid on sellises skeemis mitu), misjärel on kõik käsud juba täidetud.

Enamik automaatselt (kompilaatorite poolt) genereeritud programmijadasid ei saa laadida kõiki protsessori tuumas olevaid ALU-sid ja FPU-sid. Sel juhul on protsessori riistvara jõude, mis vähendab oluliselt selle tulemuslikkust. Protsessori arendajad mõistavad seda ja võtavad kasutusele režiimid tuumsageduse suurendamiseks, kui seadet ei kasutata täielikult. Selle jaoks on loodud ka hüperkauplemissüsteemid ning selle süsteemiga hakkan edaspidi koodi maksimaalselt “vajutama”.

Kompilaatorid, isegi kõige optimeeritumad, ja veelgi enam - virtuaalmasina mootorid, ei suuda jõudluse osas optimeeritud koodi genereerida. Sellist optimeeritud koodi saab kirjutada ainult inseneriteadmistega programmeerija ja selle kirjutamise tööriist on eranditult assembler.

Iseloomulik näide võimalusest käivitada mitu sõltumatut programmilõimi ühel protsessorituumil on GOST-i teostus, mis täidetakse kahes lõimes ühes protsessori tuumas. Koodi idee on lihtne: krüptimiseks/dekrüpteerimiseks on kaks andmeplokki, kuid üks protsessori tuum, mis teostab teisenduse. Nende kahe andmeploki teisendusi on võimalik teostada järjestikku ja seda on tehtud siiani. Sel juhul kahekordistub teisenduste sooritamiseks kuluv aeg.

Kuid võite teha teisiti: alternatiivsed käsud, mis on seotud erinevate andmeplokkide töötlemisega. Graafiliselt on need valikud näidatud joonisel fig. 3.

Joonisel on ülemisel näitel kahe sõltumatu andmeploki töötlemise tavapärane järjekord. Esiteks töödeldakse esimest plokki, seejärel jätkab protsessor teise ploki töötlemist. Loomulikult on saadud aeg võrdne kahekordse ajaga, mis kulub ühe ploki töötlemiseks ja protsessori tuuma täitmisüksused ei ole täielikult laetud.

Järgnevalt on toodud näide erinevate töötlemislõimede põimimiskäskude kohta. Sel juhul on erinevate andmeplokkidega seotud käsud põimitud. Planeerija valib üksteisest sõltumatud käsud ja edastab need täitmiseks ALU1-le ja ALU2-le. Nende ALU-de esimese ja teise lõime käskude rühmitamine toimub automaatselt, kuna planeerija tööalgoritm sisaldab käskude rühmitamist koos ülekandega sama täitevseadme tavaliste andmete alusel.

Selleks, et selline programmikood töötaks ilma ALU jõudeolekuta, on vajalik, et iga programmilõng töötaks oma registrikomplektiga. Vahemälu selles skeemis muutub kitsaskohaks (sellel on ainult kaks andmeväljundporti), seega salvestame võtmed MMX registritesse. Kuna sel juhul on asendus- (ja nihke) sõlmed mälus kirjutuskaitstud, saab neid jagada mõlema programmilõimega.

See on muidugi väga lihtsustatud selgitus programmilõimede paralleelse täitmise põhimõttest ühel tuumal, tegelikult on kõik palju keerulisem. Praktikas on vaja arvesse võtta täitmisüksuste torujuhtme arhitektuuri, vahemälu ja RON-registrite ploki samaaegse juurdepääsu piiranguid, aadressi aritmeetiliste sõlmede, lülitite olemasolu ja palju muud ... Nii et see on teema professionaalidele, keda saab ... ühe käe sõrmedel üles lugeda.

Paralleelkrüptimise meetodit rakendatakse tõhusalt ainult 64-bitise protsessori töörežiimi jaoks, kuna selles režiimis on piisav kogus RON-i (kuni 16 tükki!). Selle meetodi GOST-i rakendamise näide on toodud 2. lisas (kettal).

On selge, et selle GOST-i teostuse koodi jõudlus on 2 RTT-d. Nüüd vaatame, kuidas see täitmisaega mõjutab.

Ühe voo krüpteerimistsükkel (lisa 1) on 352 tsüklit ja selle aja jooksul arvutatakse 8 baiti andmeid, GOST-i kahe voo rakendamiseks (lisa 2) on vaja 416 protsessori tsüklit, kuid arvutatakse 16 baiti. Seega suureneb saadud teisenduskiirus 3,6 GHz protsessori puhul 80-lt 144-le megabaidile.

Saadakse huvitav pilt: kood sisaldab täpselt kaks korda rohkem juhiseid ja see võtab vaid 15% kauem aega, kuid arvan, et lugejad on selle nähtuse põhjusest juba aru saanud ...

Teoreetiliselt peaks teise näite koodi käivitama sama tsüklite arvuga kui esimese näite koodi, kuid kuigi planeerija sõlme arendavad Inteli insenerid, on nemadki inimesed ja me kõik pole kaugeltki täiuslikud. Seega on võimalus hinnata nende loomise tõhusust. See kood töötab ka AMD protsessoriga ja saate nende tulemusi võrrelda.

Kui keegi mu sõna ei võta, siis sellistele uskmatutele on kettale lisatud kellalugejatega testprogrammid. Programmid lähtekoodides muidugi assembleris, nii et on võimalus mu sõnu kontrollida ja samal ajal ka mõnda professionaalse kodeerimise nippi piiluda.

Kaasaegsete protsessorite SSE-registrite ja AVX-käskude kasutamine GOST 28147-89 rakendamiseks

Kaasaegsed x86/64 arhitektuuriga protsessorid sisaldavad 16-baidiste SSE-registrite komplekti ja spetsiaalseid FPU-sid (vähemalt kahte), et teha nendes registritega erinevaid toiminguid. Sellel seadmel on võimalik GOST-i rakendada ja sel juhul saab asendussõlmed paigutada mitte RAM-i tabelite kujul, vaid otse spetsiaalsetesse SSE-registritesse.

Ühele SSE-registrile saab korraga paigutada kaks 16-realist tabelit. Seega mahutavad neli SSE registrit täielikult kõik asendustabelid. Sellise paigutuse ainsaks tingimuseks on interleaving nõue, mille kohaselt tuleb sama baidi tetrad paigutada erinevatesse SSE registritesse. Lisaks on soovitav paigutada sisendbaitide madalad ja kõrged tetradid vastavalt SSE registrite madalatesse ja kõrgetesse tetraadidesse.

Need nõuded määratakse olemasoleva AVX-käskude komplekti optimeerimisega. Seega sisaldab SSE registri iga bait kahte tetradi, mis vastavad asendusploki sisendregistri erinevatele baitidele, samas kui baidi asukoht SSE registris vastab üheselt asendusploki asendustabelis olevale indeksile.

Asendussõlmede ühe võimaliku paigutuse skeem SSE registrites on näidatud joonisel fig. 4.

Asendussõlmede salajase teabe paigutamine SSE registritesse suurendab krüptoprotseduuri turvalisust, kuid selle salajase teabe täielik isoleerimine on võimalik järgmistel tingimustel:

• Protsessori tuum on viidud hüperviisori hostirežiimi ja katkestusplokk (APIC) on sunniviisiliselt keelatud. Sel juhul on protsessori tuum täielikult isoleeritud operatsioonisüsteemist ja arvutiinstallatsioonis töötavatest rakendustest.
• SSE registrite laadimine ja arvutustuuma isoleerimine toimub enne OS-i käivitamist, optimaalne on neid protseduure teha usaldusväärsest alglaadimismoodulist (TDM).
• Krüptoprotseduuride programmid vastavalt GOST-ile paigutatakse arvutusüksuse (kas BIOS või MDZ välkmälu) mittemodifitseeritavasse mälupiirkonda.

Nende nõuete järgimine tagab krüptoprotseduuride programmikoodi ja nendes kasutatava salajase teabe täieliku isolatsiooni ja muutumatuse.

Tõhusaks diskreetimiseks tetraadide SSE registritest kasutatakse FPU üksustes saadaolevaid mitmesisendilisi baidilüliteid. Need lülitid võimaldavad spetsiaalses SSE indeksiregistris asuvate indeksite abil ülekandeid allika mis tahes baidist sihtkoha mis tahes baiti. Lisaks toimub ülekanne paralleelselt kõigi SSE-registri-vastuvõtja 16 baidi jaoks.

Kuna SSE registrites on asendusmälusõlmed ja FPU-seadmetes on mitmesisendiline lüliti, on asendusüksuses võimalik korraldada järgmine teisendus (joonis 5).

Selles skeemis määrab iga tetradi sisendregister aadressi vastavale lülitile, mis edastab teabe asendussõlme draividest andmesiini kaudu väljundregistrisse. Sellist skeemi saab korraldada kolmel viisil:

• Looge sobiv kiibikujundus, kuid see on meie jaoks fantastiline.
• Mikrokoodi ümberprogrammeerimine ja oma protsessori juhiste loomine selle funktsiooni rakendamiseks olemasolevatel protsessoritel pole enam fantaasia, kuid kahjuks on see praegustes tingimustes ebareaalne.
• Kirjutage programm ametlike AVX-käskude abil. Valik, ehkki mitte eriti tõhus, kuid me saame selle rakendada "siin ja praegu". Nii et seda me järgmisena teemegi.

Lüliteid juhitakse spetsiaalse kolmeaadressilise käsuga AVX VPSHUFB. Selle esimene operand on lülitite teabe vastuvõtja, teine ​​on allikas, millega lülitite sisendid on ühendatud. Kolmas operaand on lülitite juhtregister, mille iga bait on seotud vastava lülitiga; selles olev väärtus määrab suuna numbri, kust lüliti teavet loeb. Selle käsu kirjeldust ametlikust Inteli dokumentatsioonist leiate joonisest fig. 5. Joonisel fig. Joonisel 6 on näidatud selle käsu toimimine - näidatud on ainult pooled SSE registritest, teisel poolel on kõik sarnased.

Lüliti kasutab lülitussuuna määramiseks ainult kõige vähemtähtsat nelja bitti, iga baidi viimast bitti kasutatakse vastava vastuvõtjabaidi nullimiseks, kuid see lüliti funktsioon pole meie puhul veel vajalik.

Kirjutati programm FPU-lülitite kaudu sülearvutite valikuga, kuid ma ei pannud seda isegi rakendusse - see on liiga kehv. 128-bitise registri omamine ja ainult 32 biti kasutamine selles on ebaprofessionaalne.

Nagu öeldakse: "Meie viimistlus on horisont", nii et pigistage see niimoodi välja... me vajutame selle ja paneme kottidesse!

See ei ole sõnamäng, vaid karm FPU reaalsus – SSE registrid saab jagada võrdseteks osadeks ja ühe käsuga teha nendel osadel samu teisendusi. Selleks, et protsessor sellest aru saaks, on olemas maagiline täht "P" - pakett, mis asetatakse käskluse ette, ja mitte vähem maagilised tähed "Q", "D", "W", "B", mis asetatakse lõppu ja deklareerivad, millisteks osadeks on SSE registrid selles käsus jagatud.

Oleme huvitatud sarivõtterežiimist, mille SSE register on jagatud neljaks 32-bitiseks plokiks; vastavalt sellele on kõikide käskude eesliide "P" ja lõpetatakse sümboliga "D". See võimaldab töödelda nelja 32-bitist plokki paralleelselt ühe protsessori käsuga, st arvutada paralleelselt neli andmeplokki.

Seda meetodit rakendav programm on saadaval lisas 3, seal on kõik selgitused.

Siiski vajuta nii vajuta! Kaasaegsetel protsessoritel on vähemalt kaks FPU-d ja nende täielikuks laadimiseks saab kasutada kahte sõltumatut käsuvoogu. Kui sisestate sõltumatute voogude käsud õigesti, saate mõlemad FPU-d täielikult laadida ja saada korraga kaheksa paralleelselt töödeldud andmevoogu. Selline programm on kirjutatud ja seda näete lisas 4, kuid peate hoolikalt vaatama - võite hulluks minna. Seda nimetatakse "kood ei ole kõigile ...".

Väljalaske hind

SSE registrite kasutamine asendussõlmede salvestamiseks on arusaadav - see annab teatud garantii salajase teabe eraldamiseks, kuid krüptofunktsiooni enda arvutamise tähendus FPU-s pole ilmne. Seetõttu mõõdeti standardprotseduuride täitmise aega, kasutades GOST-i kohaselt nelja ja kaheksa voogu otseasendusmeetodit.

Nelja lõime puhul saadi 472 protsessoritsükli täitmiskiirus. Seega 3,6 GHz sagedusega protsessori puhul arvestatakse ühte lõime kiirusega 59 megabaiti sekundis ja nelja lõime vastavalt kiirusega 236 megabaiti sekundis.

Kaheksa lõime jaoks saadi täitmiskiiruseks 580 protsessoritsüklit. Seega 3,6 GHz protsessori puhul arvestatakse ühte lõime kiirusega 49 megabaiti sekundis ja kaheksa lõime kiirusega 392 megabaiti sekundis.

Nagu lugeja võib märgata, on näites #3 oleva koodi läbilaskevõime 4 RTT, samas kui näite #4 koodi läbilaskevõime on 8 RTT. Nendes näidetes on SSE registrite mustrid samad, mis RON-i kasutamisel, ainult ajakava on vähendanud oma tõhusust. See suurendab nüüd koodi pikkust 2 korda 20% võrra.

Lisaks saadi need tulemused universaalsete AVX-käskude abil, mis on saadaval nii Inteli kui ka AMD protsessorites. Kui optimeerite AMD protsessori jaoks, on tulemus palju parem. See kõlab vastupidiselt suundumusele, kuid sellest hoolimata on see tõsi ja põhjus on siin: AMD protsessoritel on täiendav juhiste komplekt, nn XOP laiendus, ja selles täiendavas juhiste komplektis on neid, mis lihtsustavad oluliselt juhiste rakendamist. GOST algoritm.

See viitab baitide loogilise paketinihke ja topeltsõnade pakettide tsüklilise nihutamise käskudele. Lisades 3 ja 4 toodud näidetes on kasutatud universaalsete käskude jadasid, mis teostavad vajalikku teisendust: esimesel juhul üks "ekstra" käsk ja teisel juhul neli lisakäsku korraga. Seega on optimeerimisreserve ja märkimisväärseid.

Kui me räägime edasisest optimeerimisest, siis tasub meeles pidada 256-bitiste registrite (YMM-registrite) olemasolu, mille abil saate teoreetiliselt kahekordistada arvutuste kiirust. Kuid praegu on see ainult väljavaade, hetkel aeglustavad protsessorid 256-bitiste käskude täitmisel (FPU-de tee laius on 128 bitti) palju. Katsed on näidanud, et tänapäevaste protsessorite puhul ei anna YMM-registrite 16 lõime arv mingit kasu. Kuid see on ainult praegu, uutel protsessorimudelitel suurendatakse kahtlemata 256-bitiste käskude kiirust ja siis muutub 16 paralleelse lõime kasutamine otstarbekaks ja toob kaasa krüptoprotseduuri kiiruse veelgi suurema tõusu.

Teoreetiliselt võite arvestada kiirusega 600–700 megabaiti sekundis, kui protsessoril on kaks FPU-d, mille töötee laius on 256 bitti. Sel juhul saame rääkida koodi kirjutamisest efektiivsusega 16 RTT ja see pole fantaasia, vaid lähitulevik.

segarežiim

Taas kerkib küsimus registrite arvust, neist ei piisa sellise algoritmi propageerimiseks. Kuid hüperkauplemisrežiim aitab meid. Protsessori tuumal on loogilise protsessori režiimis saadaval teine ​​​​registrite komplekt. Seetõttu käivitame sama koodi kahel loogilisel protsessoril korraga. Selles režiimis meil muidugi rohkem juhtseadmeid ei ole, kuid vaheldumise tõttu saame täiskoormuse kõiki täitevseadmeid.

50% kasvuga siin loota ei saa, kitsaskohaks on vahemälu, kuhu hoitakse tehnoloogilisi maske, aga 100 megabaidi juurde saab siiski juurde. Seda valikut lisades ei ole (makrod on samad, mis 8 RTT koodis kasutatud), kuid see on saadaval programmifailides. Nii et kui keegi ei usu krüptimise võimalusse kiirusega 500 megabaiti sekundis ühe protsessori tuumaga, las ta käivitab testfailid. Seal on ka tekstid koos kommentaaridega, et keegi ei arvaks, et ma olen kaval.

See keskendumine on võimalik ainult Inteli protsessoritel, AMD-l on ainult kaks FPU-d kahe protsessorimooduli kohta (analoogselt hüperkauplemisrežiimile). Kuid on veel neli ALU-d, mida on patt mitte kasutada.

Saate juhtida Bulldozeri protsessorimoodulid hüperkauplemisrežiimiga sarnasesse režiimi, kuid ühes lõimes käivitage erinevatel moodulitel RON-i ja teises lõimes SSE-registriteks teisendamine ja saate sama 12 RTT-d. Ma pole seda võimalust testinud, kuid arvan, et 12 RTT kood töötab AMD-s tõhusamalt. Soovijad saavad proovida, testprogrammid saab üsna lihtsalt "Buldooserite" peal tööle sättida.

Kellele seda vaja on?

Tõsine küsimus, kuid lihtsa vastusega – seda on kõigil vaja. Varsti istume kõik pilvede peale maha, talletame sinna nii andmed kui programmid ja seal, oi, kuidas sa tahad oma privaatset nurka sisustada. Selleks peate liikluse krüpteerima ja krüptokonversiooni kiirus on pilves mugava töötamise peamine määrav tegur. Meie krüpteerimisalgoritmi valik on väike – kas GOST või AES.

Veelgi enam, kummalisel kombel osutub protsessoritesse sisseehitatud AES-algoritmi krüptimine palju aeglasemaks, testid näitavad kiirust 100–150 megabaiti sekundis ja seda algoritmi riistvaralise rakendamisega! Probleem seisneb ühelõimelises loendamises ja asendusplokis, mis töötab baitidel (tabel 256 rida). Nii et GOST osutub x86 / 64 arhitektuuri rakendamisel tõhusamaks, kes oleks arvanud ...

Seda siis, kui räägime krüpteerimiskiiruse saavutatud tasemest. Ja kui pidada silmas teoreetilisi täpsustusi koodi efektiivsuse parandamise vallas, siis tõenäoliselt pole seda kellelgi vaja. Taseme 3–6 RTT spetsialiste praktiliselt pole, kompilaatorid genereerivad üldjuhul koodi tasemel 1–2,5 RTT ja enamik programmeerijaid ei tunne assemblerit ja kui nad teavad selle õigekirja, siis ei saa aru ka selle seadmest. kaasaegne protsessor. Ja ilma selle teadmiseta, mis on assembler, mis mingi SI-sharp – vahet pole.

Kuid mitte kõik pole nii kurb: pärast nädalast unetuid öid on "alumisel real" uus GOST-i rakendamise algoritm, mida on patt mitte patenteerida. Ja patenditaotlused (koguni kolm) on juba koostatud ja sisse antud, nii et härrased, ärimehed, rivistage - naistele ja lastele on allahindlus.

). Samal ajal kasvab Venemaa meedias ja Venemaa kasutajate ajaveebides selle algoritmi kohta käivate märkmete arv: nii kajastatakse erineva usaldusväärsusega Venemaa standardile suunatud rünnakute tulemusi ja sisaldavad arvamusi selle tööomaduste kohta. Nende märkmete autoritele (ja sellest tulenevalt ka lugejatele) jääb sageli mulje, et kodumaine krüpteerimisalgoritm on vananenud, aeglane ja sellel on haavatavused, mis muudavad selle rünnakutele palju vastuvõtlikumaks kui sarnase võtme pikkusega välismaised krüpteerimisalgoritmid. Selle märkmete seeriaga soovime juurdepääsetaval kujul rääkida Venemaa standardi hetkeseisust. Esimene osa hõlmab kõiki rahvusvahelisele krüptograafilisele kogukonnale teadaolevaid GOST 28147-89 rünnakuid, selle tugevuse praeguseid hinnanguid. Tulevastes väljaannetes käsitleme üksikasjalikult ka standardi omadusi tõhusate rakenduste ehitamise võimaluse seisukohalt.

Nicolas Courtois - "suur ja kohutav"

Alustame looga Nicolas Courtois' tegevusest, kes on terve rea Vene plokkrüpteerimisstandardit käsitlevate tööde autor ().

2010. aasta oktoobris alustati GOST 28147-89 algoritmi lisamise kaalumist rahvusvahelisse standardisse ISO/IEC 18033-3. Juba 2011. aasta mais ilmus ePrinti elektroonilises arhiivis kuulsa krüptograafi Nicolas Courtoisi artikkel, mida iseloomustas maailma krüptograafide kogukonna väga kahemõtteline suhtumine temasse. Courtois' publikatsioonid on kurb näide mõistetega manipuleerimisest, mis ei paljasta kõnealuse objekti uusi omadusi, kuid provotseerib sensatsioonipretensiooniga ebakompetentses keskkonnas ekslike arvamuste levikut selle tegelike omaduste kohta.

Algebraline meetod

Courtois' arutluskäik on üles ehitatud kahe krüptoanalüüsi meetodite klassi ümber: algebralised meetodid ja diferentsiaalmeetodid. Mõelge esimesele meetodite klassile.

Lihtsustatult võib algebralise krüptoanalüüsi meetodit kirjeldada kui suure võrrandisüsteemi koostamist ja lahendamist, mille iga lahendus vastab krüptoanalüütiku eesmärgile (näiteks kui süsteem on koostatud ühe paari abil lihtteksti ja šifreeritud tekstiga, siis vastavad kõik selle süsteemi lahendused võtmetele, mille alusel see lihttekst teisendatakse antud krüpteerituks). See tähendab, et plokkšifri krüptoanalüüsi probleemi puhul on krüptoanalüüsi algebralise meetodi olemus selles, et võti leitakse polünoomvõrrandisüsteemi lahendamise tulemusena. Peamine raskus seisneb võimaluses koostada võimalikult lihtne süsteem, võttes arvesse konkreetse šifri omadusi, nii et selle lahendamise protsess võtaks võimalikult vähe aega. Siin mängivad võtmerolli iga konkreetse analüüsitud šifri omadused.

Courtois' kasutatud algebralist meetodit saab lühidalt kirjeldada järgmiselt. Esimeses etapis kasutatakse selliseid GOST 28147-89 omadusi kui fikseeritud punkti olemasolu krüpteeringu teisenduse osa jaoks, samuti nn peegelduspunkti. Nende omaduste tõttu valitakse piisavalt suure hulga avatud šifreeritud tekstipaaride hulgast mitu paari, mis võimaldab arvestada teisendustega mitte 32, vaid ainult 8 voorus. Teine etapp seisneb selles, et esimeses etapis saadud 8-ringiliste teisenduste tulemuste põhjal konstrueeritakse mittelineaarsete võrrandite süsteem, milles võtmebitideks on tundmatud. Seejärel see süsteem lahendatakse (see kõlab lihtsalt, kuid on tegelikult meetodi kõige aeganõudvam osa, kuna süsteem koosneb mittelineaarsetest võrranditest).

Nagu eespool märgitud, ei ole töös kusagil võtme määramise teise ja peamise etapi keerukuse üksikasjalikku kirjeldust ja analüüsi. Just teise etapi keerukus määrab kogu meetodi kui terviku keerukuse. Selle asemel toob autor välja kurikuulsad "faktid", mille põhjal teeb hinnanguid töömahukuse kohta. Väidetavalt põhinevad need "faktid" katsetulemustel. Courtois' teoste "faktide" analüüs tervikuna on antud kodumaiste autorite töödes. Selle töö autorid märgivad, et paljud Courtoisi "faktid", mis esitati ilma tõenditeta, osutusid eksperimentaalse kontrolli käigus valeks. Artikli autorid läksid kaugemale ja analüüsisid Courtoisi jaoks teise etapi keerukust, kasutades selleks hästi põhjendatud algoritme ja hinnanguid. Saadud keerukuse hinnangud näitavad esitatud rünnaku täielikku kohaldamatust. Lisaks kodumaistele autoritele märgiti töös ära ka näiteks suured probleemid, mis Courtois’l on oma meetodite hinnangute ja põhjendamisega.

Diferentsiaalne meetod

Mõelge teisele Courtois' meetodile, mis põhineb diferentsiaalkrüptoanalüüsil.

Üldine diferentsiaalkrüptoanalüüsi meetod põhineb krüptograafilistes primitiivides kasutatavate mittelineaarsete vastenduste omaduste ärakasutamisel, mis on seotud võtmeväärtuse mõjuga nende sisend- ja väljundväärtuste paaride vaheliste erinevuste sõltuvustele. kaardistused. Kirjeldame plokkšifri krüptograafilise analüüsi diferentsiaalmeetodi peamist ideed. Tavaliselt teisendavad plokkšifrid sisendandmeid etappide kaupa, kasutades mitmeid nn ümmargusi teisendusi ja iga ümmargune teisendus ei kasuta kogu võtit, vaid ainult osa sellest. Mõelge veidi "kärbitud" šifrile, mis erineb algsest selle poolest, et sellel pole viimast ringi. Oletame, et on kindlaks tehtud, et kahe mõnes fikseeritud positsioonis erineva lihtteksti krüpteerimisel sellise "kärbitud" šifri abil saadakse suure tõenäosusega šifritekste, mis erinevad ka mõnes fikseeritud positsioonis. See omadus näitab, et "kärbitud" šifr jätab suure tõenäosusega mõne lihtteksti ja nende krüptimise tulemuste vahele sõltuvuse. Selle ilmse vea abil osa võtmest taastamiseks on vaja eelvalitud lihttekste krüpteerida võtmega, mida tahame taastada (nn "valitud lihtteksti rünnak"). Võtme avamise protseduuri alguses genereeritakse juhuslikult hulk lihttekstide paare, mis erinevad samades fikseeritud positsioonides. Kõik tekstid krüpteeritakse "täieliku" šifri abil. Saadud šifreeritud tekstipaare kasutatakse viimase vooru teisenduses kasutatud võtmebittide taastamiseks järgmiselt. Võtme vajalike bittide mõne juhuslikult valitud väärtuse abil rakendatakse kõikidele šifritekstidele teisendus, mis on viimase ümmarguse teisenduse vastupidine. Tegelikult, kui arvasime ära võtmebittide soovitud väärtuse, saame "kärbitud" šifri tulemuse ja kui me ei arvanud, siis tegelikult "krüpteerime andmeid veelgi", mis ainult vähendab sõltuvus ülalmainitud plokkide vahel (erinevus mõnes fikseeritud asendis). Teisisõnu, kui sellise šifritekstide “täiendava töötlemise” tulemuste hulgas oli päris palju meile teadaolevaid fikseeritud positsioonide poolest erinevaid paare, siis see tähendab, et oleme ära arvanud vajalikud võtmebitid. Muidu on selliseid paare oluliselt vähem. Kuna igas voorus kasutatakse ainult osa võtmest, ei ole otsitavaid bitte (st viimases voorus kasutatud võtmebitte) sama palju kui täisvõtme bitte ja neid saab lihtsalt korrata, korrates ülaltoodud sammud. Sel juhul komistame kindlasti kunagi õige väärtuse otsa.

Ülaltoodud kirjeldusest järeldub, et diferentsiaalanalüüsi meetodi puhul on kõige olulisem just nende tava- ja šifritekstide positsioonide arvud, mille erinevused mängivad võtmebittide taastamisel võtmerolli. Nende positsioonide põhimõtteline olemasolu ja ka nende arvude komplekt sõltub otseselt nende mittelineaarsete teisenduste omadustest, mida kasutatakse mis tahes plokkšifris (tavaliselt on kogu "mittelineaarsus" koondunud nn S-i. -kastid või asendussõlmed).

Courtois kasutab diferentsiaalmeetodi veidi muudetud versiooni. Märgime kohe, et Courtois viib läbi S-kastide analüüsi, mis erinevad praegustest ja ISO-s pakututest. Töös esitatakse väikese arvu voorude diferentsiaalkarakteristikud (sama arvud, mille poolest plokid peaksid erinema). Põhjendus statistika pikendamiseks rohkemate voorude jaoks põhineb nagu tavaliselt "faktidel". Courtois väljendab jällegi ainult oma autoriteediga põhjendamatut oletust, et S-kastide vahetamine ei mõjuta GOST 28147-89 vastupanuvõimet selle rünnakule (samal ajal, teadmata põhjustel, S-kastid alates 1. töökorrast standardi ISO/IEC 18033-3 täienduse eelnõud ei ole arvesse võetud). Artikli autorite läbiviidud analüüs näitab, et isegi kui võtta Courtoisi alusetud "faktid" usku ja analüüsida GOST 28147-89 koos teiste S-kastidega, ei osutu rünnak jällegi paremaks kui täielik loendus.

Courtois' tööde üksikasjalik analüüs koos üksikasjaliku põhjendusega kõigi Vene standardi stabiilsuse vähenemist puudutavate väidete alusetuse kohta viidi läbi [ , ].

Samas tunnistab arvutuste absoluutset täpsuse puudumist isegi Courtois ise! Järgmine slaid on võetud Courtoisi ettekandest FSE 2012 lühiteate rubriigis.

Tuleb märkida, et Courtois’ teoseid kritiseerisid korduvalt ka välismaa teadlased. Näiteks sisaldas tema töö AES-i plokkšifreerimisalgoritmi rünnakute ehitamisel XSL-meetodil samu põhimõttelisi vigu kui Vene standardi analüüsi töö: enamik töömahukuse hinnanguid on tekstis täiesti alusetu ja põhjendamatu - üksikasjalikku kriitikat võib leida näiteks tööst . Lisaks tunnistab Courtois ise laialdasi keeldumisi avaldada oma töid suurtel krüptograafiakonverentsidel ja väljakujunenud eelretsenseeritavates ajakirjades, jättes talle sageli võimaluse esineda vaid lühikuulutuste rubriigis. Seda saab lugeda näiteks töö 3. osas. Siin on mõned Courtoisi enda tsitaadid, mis on seotud tema tööga:

• "Ma arvan, et Asiacrypti publik ei pea seda huvitavaks." Asiacrypt 2011 arvustaja.
• "... on suur, suur, suur probleem: see rünnak, mis on paberi peamine panus, on juba FSE'11-l avaldatud (see oli isegi parim artikkel) ...". Krüptoülevaataja 2011.

Seega suhtub rahvusvahelise krüptokogukonna professionaalne osa Courtois' töö kvaliteeti vähema kahtlusega kui näiteks mõne Venemaa spetsialisti ütlused nende võime kohta murda AES 2100 eest või järgmised "tõestused" kahel leheküljel. hüpotees, mida ei kinnita ükski järjepidev arvutus.keerukusklasside P ja NP ebavõrdsuse kohta.

Isobe ja Dinur-Dunkelman-Shamir ründavad

Isobe rünnakute () ja Dinur-Dankelman-Shamiri (edaspidi: DDSH rünnak) () üldine idee on konstrueerida teatud (võtmest sõltuva) kitsa lihttekstide komplekti jaoks selle komplekti teisenduse ekvivalent, millel on lihtsam struktuur kui krüpteeringu teisendus ise. Isobe meetodi puhul on see 64-bitiste plokkide komplekt x nii, et F 8 -1 (Vahetus(F 8 (z))) = z, kus z = F 16 (x) kuni F 8 ( x) ja F 16 (x) on vastavalt esimesed 8 ja esimesed 16 krüpteerimisvooru GOST 28147-89 Swapi kaudu - 64-baidise sõna poolte vahetamise toiming. Kui lihttekst satub sellesse komplekti, langeb GOST 28147-89 täieliku 32-ringilise teisenduse tulemus kokku 16-voorulise teisenduse tulemusega, mida rünnaku autor kasutab. DDS-meetodi puhul on see x-i hulk, nii et F 8 (x) = x (teisnduse F 8 fikseeritud punkt). Selle komplekti mis tahes lihtteksti puhul töötab GOST 28147-89 teisendus täpselt samamoodi nagu selle viimased 8 vooru, mis lihtsustab analüüsi.

Isobe rünnaku keerukus on 2224 krüpteerimistoimingut, LDS-i rünnak on 2192. Kõik küsimused selle kohta, kas sellest järeldub, et Isobe ja DDSH rünnakud kehtestavad meie algoritmi kasutamise tingimustele uusi piiranguid, eemaldatakse aga iga rünnaku läbiviimiseks vajaliku materjali koguse nõuete hindamisel: Isobe meetod nõuab 2 32 paari lihtteksti ja šifritekste ning DDSH-2 meetodi puhul 64 . Selliste materjalide koguste töötlemine ilma võtit muutmata on a priori vastuvõetamatu iga plokkšifri puhul, mille ploki pikkus on 64: materjalil, mille maht on 2 32 , võttes arvesse sünnipäevade probleemi (vt nt sissetungijale oskus teha salatekstide kohta teatud järeldusi ilma võtit määramata. Samal võtmel saadud 264 paari avatud ja šifreeritud tekstide olemasolu võimaldab tegelikult vastasel sooritada krüpteerimis- ja dekrüpteerimistoiminguid seda võtit üldse teadmata. See on tingitud puhtalt kombinatoorsest omadusest: vastasel on sel juhul kogu krüpteerimise teisendustabel. Selline olukord on täiesti vastuvõetamatu mistahes mõistlike tegevusnõuete korral. Näiteks CryptoPro CSP-s on krüptitud (ilma võtme teisendamiseta) materjali hulga tehniline piirang 4 MB (vt.). Seega on sellise mahuga materjalil võtme kasutamise range keeld omane igale plokkšifrile, mille ploki pikkus on 64 bitti, ja seetõttu ei kitsenda Isobe ja DDSH rünnakud kuidagi kasutusala. GOST 28147-89 algoritmi järgi, säilitades samal ajal maksimaalse võimaliku turvalisuse 2256 .

Muidugi tuleb märkida, et teadlased (Isobe ja Dinur-Dankelman-Shamir) näitasid, et GOST 28147-89 algoritmi mõned omadused võimaldavad leida analüüsiteid, mida algoritmi loojad ei võtnud arvesse. Võtmegraafiku lihtne vorm, mis oluliselt lihtsustab tõhusate rakenduste konstrueerimist, võimaldab koostada ka lihtsamaid kirjeldusi algoritmi poolt sooritatavatest teisendustest mõnel harvaesineva võtmete ja lihttekstide puhul.

Töö demonstreerib, et seda algoritmi negatiivset omadust saab tööomaduste täieliku säilitamisega hõlpsasti kõrvaldada, kuid kahjuks on see algoritmi lahutamatu osa oma üldkasutataval kujul.

Märgime, et Dinuri, Dankelmani ja Shamiri töödes esineb ka teatud hooletusi keskmise tööpanuse hinnangutes. Seega ei pöörata rünnaku koostamisel piisavalt tähelepanu järgmisele punktile: olulise osa klahvide puhul on lihttekstide hulk x, nii et F 8 (x) = x, tühi: 8 teisendusringi ei pruugi lihtsalt olla. on kindlad punktid. Püsipunktide olemasolu sõltub ka asendussõlmede valikust. Seega on rünnak rakendatav ainult teatud asendussõlmede ja võtmete puhul.

Samuti väärib märkimist veel üks töö GOST 28147-89 rünnakuga. 2012. aasta veebruaris ilmus rahvusvahelise krüptograafilise ühenduse ePrint elektroonilises arhiivis artikli uuendatud versioon (kuupäev novembris 2011), mis sisaldas uut rünnakut GOST 28147-89 vastu. Esitatud rünnaku omadused on järgmised: materjali maht on 232 (nagu Isobe puhul) ja töömahukus on 2192 (nagu DDSh puhul). Seega parandas see rünnak rekordilise LDS-rünnaku materjali mahu osas 2 64-lt 2 32-le. Eraldi märgime, et autorid esitasid ausalt kõik arvutused koos materjali keerukuse ja mahu põhjendusega. 9 kuu möödudes leiti ülaltoodud arvutustes põhimõtteline viga ning alates 2012. aasta novembrist ei sisalda elektroonilise arhiivi artikli uuendatud versioon kodumaise algoritmi kohta enam tulemusi.

Rünnakud, mis põhinevad eeldusel, et ründaja teab klahvidest "midagi".

Lõpuks märgime, et kirjanduses on ka mitmeid teoseid (vt näiteks ja ), mis on pühendatud GOST 28147-89 rünnakutele nn lingitud võtmetega mudelis. See mudel sisaldab põhimõtteliselt eeldust sissetungija võimaluse kohta pääseda analüüsimiseks juurde mitte ainult avatud ja krüptitud tekstide paaridele, kasutades soovitud võtit, vaid ka avatud ja šifreeritud tekstide paaridele, mis on saadud (samuti tundmatute) võtmetega, mis erinevad võtmetest. otsitud teadaolev tavapärane viis (näiteks fikseeritud bitipositsioonides). Selles mudelis on tõepoolest võimalik saada huvitavaid tulemusi GOST 28147-89 kohta, kuid selles mudelis ei saa vähem tugevaid tulemusi näiteks kaasaegsetes avalikes võrkudes kõige levinumaks muutunud AES-standardi kohta (vt. , näiteks,). Pange tähele, et selliste rünnakute läbiviimise tingimused tekivad siis, kui teatud protokollis kasutatakse šifrit. Tuleb märkida, et sedalaadi tulemused, kuigi need pakuvad krüptograafiliste teisenduste omaduste uurimise seisukohalt kahtlemata akadeemilist huvi, ei kehti tegelikult praktikas. Näiteks vastavad kõik Venemaa FSB poolt sertifitseeritud krüptograafilise teabe kaitse tööriistad krüpteerimisvõtme genereerimise skeemide rangeimatele nõuetele (vt näiteks). Nagu analüüsi tulemused näitavad, on 18 lingitud võtme ja 210 paari avatud ja šifreeritud tekstiplokkide olemasolul privaatvõtme täieliku avamise keerukus, mille õnnestumise tõenäosus on 1-10-4 . 2 26 . Kui aga ülaltoodud nõuded võtmematerjali väljatöötamisel on täidetud, on selliste võtmete leidmise tõenäosus 2 -4352 ehk 24096 korda väiksem kui siis, kui proovite esimesel katsel salavõtit lihtsalt ära arvata.

Lingitud võtmetega mudeliga seotud teoste hulgas on ka teos , mis tekitas 2010. aastal palju kära Venemaa elektroonilistes väljaannetes, mis ei kannata harjumust aistingute tagaajamise käigus materjali hoolikalt kontrollida. Selles esitatud tulemusi ei toetanud ükski range põhjendus, vaid need sisaldasid valjuhäälseid avaldusi võimaluse kohta mõne sekundiga nõrgal sülearvutil häkkida Vene Föderatsiooni riiklikku standardit - üldiselt oli artikkel kirjutatud parimate traditsioonide järgi. Nicolas Courtois'st. Kuid vaatamata lugejale täiesti ilmselgele, teaduspublikatsioonide põhiprintsiipidega enam-vähem tuttavale artikli alusetusele, oli just nimelt Vene avalikkuse rahustamiseks, et Rudski kirjutas pärast teost üksikasjaliku ja üksikasjaliku teksti, mis sisaldas selle puuduse põhjalik analüüs. Kõneka pealkirjaga artikkel "Töö "Võtmete taastamise rünnak täielikule GOST-ploki šifrile nullaja ja mäluga" praktilisest nullist" põhjendab asjaolu, et meetodis antud meetodi keskmine keerukus ei ole väiksem kui täieliku loenduse keerukus.

Kuiv jääk: milline on resistentsus praktikas?

Kokkuvõtteks esitame tabeli, mis sisaldab andmeid rangelt kirjeldatud ja õigustatud rünnakute tulemuste kohta GOST 28147-89 vastu, mis on rahvusvahelisele krüptokogukonnale teada. Pange tähele, et keerukus on antud GOST 28147-89 algoritmi krüpteerimistoimingutes ning mälu ja materjal on määratud algoritmi plokkides (64 bitti = 8 baiti).

Rünnak	Tööjõu intensiivsus	Mälu	Vajalik materjal
Isobe	2 224	2 64	2 32
Dinur-Dunkelman-Shamir, FP, 2DMitM	2 192	2 36	2 64
Dinur-Dunkelman-Shamir, FP, vähese mäluga	2 204	2 19	2 64
	2 224	2 36	2 32
Dinur-Dunkelman-Shamir, peegeldus, 2DMitM	2 236	2 19	2 32
toores jõud	2 256	1	4
Nanosekundite arv alates universumi algusest	2 89

Vaatamata üsna ulatuslikule uurimistsüklile GOST 28147-89 algoritmi turvalisuse valdkonnas, pole hetkel teada ühtegi rünnakut, mille rakendamise tingimused oleksid saavutatavad kaasneva ploki pikkusega 64 bitti. tegevusnõuetest. Ühe võtmega töödeldava materjali koguse piirangud, mis tulenevad šifri parameetritest (võtme biti pikkus, ploki biti pikkus), on oluliselt rangemad kui minimaalne kogus, mis on vajalik mis tahes toimingute tegemiseks. praegu teadaolevatest rünnakutest. Seetõttu ei võimalda ükski seni pakutud GOST 28147-89 krüptoanalüüsi meetod, kui olemasolevad töönõuded on täidetud, määrata võtit, mille töömahukus on väiksem kui ammendav otsing.

Meie riigis on ühtne algoritm andmete krüptograafiliseks esitamiseks infotöötlussüsteemide jaoks arvutivõrkudes, üksikutes arvutisüsteemides ja arvutites, mille määrab kindlaks GOST 28147-89.

See krüptoandmete teisendusalgoritm on 256-bitise võtmega 64-bitine plokk-algoritm, mis on mõeldud riist- ja tarkvara juurutamiseks, vastab krüptograafilistele nõuetele ega sea piiranguid kaitstava teabe salastatuse astmele.

Algoritmi kirjeldamisel kasutatakse järgmist tähistust:

L ja R on bitijadad;
LR on jadade L ja R konkatenatsioon, milles jada R bitid järgivad jada L bitte;
(+) - bitipõhise liitmise modulo 2 ("eksklusiivne VÕI" operatsioon);
[+] - 32-bitiste arvude liitmine modulo 2 32 ;
(+) - 32-bitiste arvude liitmine modulo 2 32 -1.

Arvud liidetakse järgmise reegli järgi:

A[+]B=A+B, kui A+B< 2 32 ,
A [+] B = A + B - 2 32, kui A + B >= 2 32 . A (+) B = A + B, kui A + B< 2^32 - 1, A {+} B = A + B - (2^32 - 1), если A + B >= 2^32 - 1.

Algoritm pakub nelja töörežiimi:

Igal juhul kasutatakse andmete krüptimiseks 256-bitist võtit K, mis on esitatud kaheksa 32-bitise alamvõtmena K i:

K = K 7 K 6 K 5 K 4 K 3 K 2 K 1 K 0.

Dekrüpteerimine toimub sama võtmega kui krüptimine, kuid see protsess on andmete krüpteerimisprotsessi pöördvõrdeline.

Lihtne vahetusrežiim

Esimene ja lihtsaim režiim - asendamine. Krüpteeritavad andmed on jagatud 64-bitisteks plokkideks. Avaandmete ploki T 0 krüpteerimisprotseduur sisaldab 32 tsüklit (j=1...32).

Plokk T0 on jagatud kaheks 32-bitiseks jadaks: B(0)A(0), kus B(0) on vasakpoolsed või kõige olulisemad bitid, A(0) on parempoolsed või vähima tähtsusega bitid.

Need jadad sisestatakse draividesse N 1 ja N 2 enne esimese krüpteerimistsükli algust.

64-bitise andmeploki krüpteerimisprotseduuri esimest tsüklit (j=1) kirjeldatakse järgmiste valemitega:

Siin tähistab i iteratsiooninumbrit (i = 1, 2,..., 32).

Funktsiooni f nimetatakse krüpteerimisfunktsiooniks. Selle argumendiks on eelmises iteratsioonietapis saadud arvu A(i) ja võtme numbri X(j) summa modulo 2 32 (iga nende numbrite mõõde on 32 numbrit).

Krüpteerimisfunktsioon sisaldab kahte toimingut saadud 32-bitise summaga. Esimest operatsiooni nimetatakse asenduseks K. Asendusplokk K koosneb 8 asendussõlmest K(1) ... K(8), millest igaühe mälu on 64 bitti. Asendusplokki saabuv 32-bitine vektor jagatakse 8 järjestikuseks 4-bitiseks vektoriks, millest igaüks teisendab 4-bitiseks vektoriks vastav asendussõlm, mis on tabel 16 täisarvuga vahemikus 0. .15.

Sisendvektor määrab tabelis selle rea aadressi, mille number on väljundvektor. Seejärel kombineeritakse 4-bitised väljundvektorid järjestikku 32-bitiseks vektoriks. Asendusplokkide tabel K sisaldab arvutivõrgule ühiseid ja harva muudetud võtmeelemente.

Teine operatsioon on 32-bitise vektori tsükliline nihe vasakule, mis saadakse K asendamisel. 64-bitine krüptitud andmeplokk Tw on esitatud kui T w =A(32)B(32).

Ülejäänud lihtsa asendusrežiimi avatud andmeplokid krüpteeritakse samal viisil.

Pidage meeles, et lihtsat asendusrežiimi saab andmete krüptimiseks kasutada ainult piiratud juhtudel. Need juhtumid hõlmavad võtme genereerimist ja selle krüptimist imitatsioonikaitsega (kaitse valeandmete kehtestamise eest) sidekanalite kaudu edastamiseks või arvuti mällu salvestamiseks.

Gamma režiim

Avaandmed, mis on jagatud 64-bitisteks plokkideks T(i) (i=1, 2,..., m, kus m määratakse krüptitud andmete hulga järgi), krüpteeritakse gammarežiimis bitipõhise liitmise mooduliga 2 koos šifri gamma Гw, mis toodetakse 64-bitistes plokkides, st Гw = (Г(1),Г(2),...,Г(i),...,Г(m)).

Gammarežiimis olevate andmete krüptimise võrrandit saab esitada järgmiselt:

W(i) = A (Y(i-1) [+] C2, Z(i-1) (+) C1) (+) T(i) = G(i) (+) T(i) .
Siin on W(i) 64-bitine šifreeritud tekstiplokk,
A - krüpteerimisfunktsioon lihtsas asendusrežiimis (selle funktsiooni argumendid on kaks 32-bitist numbrit),
C1 ja C2 - GOST 28147-89 määratletud konstandid,
Y(i) ja Z(i) on suurused, mis määratakse iteratiivselt, kui gamma moodustub järgmiselt:
(Y(0), Z(0)) = A(S), kus S on 64-bitine binaarjada (sünkroonimisteade);
(Y(i), Z(i)) = (Y(i-1) [+] C2, Z(i-1) (+) C1) kui i = 1, 2,...,m.

Andmete dekrüpteerimine on võimalik ainult siis, kui on olemas sünkroonimisteade, mis ei ole šifri salajane element ja mida saab salvestada arvuti mällu või edastada sidekanalite kaudu koos krüpteeritud andmetega.

Tagasiside gamma režiim

Režiim skaleerimine tagasisidega on väga sarnane gammarežiimiga. Nagu gammarežiimis, krüpteeritakse 64-bitisteks plokkideks T(i) (i=1, 2,..., m , kus m määratakse krüptitud andmete hulga järgi) jagatud avatud andmed bitipõhise liitmise mooduliga 2 gamma G sh šifriga, mis on toodetud 64-bitistes plokkides:

Гw = (Г(1),Г(2),...,Г(i),...,Г(m)).

Plokis T(m) võib bittide arv olla väiksem kui 64, samas kui plokist G(m) pärinev šifri gamma osa, mida krüptimiseks ei kasutata, jäetakse kõrvale.

Andmete krüptimise võrrandit gammarežiimis koos tagasisidega saab esitada järgmiselt:

Siin on W(i) 64-bitine šifreeritud tekstiplokk,
A - krüpteerimisfunktsioon lihtsas asendusrežiimis. Iteratiivse algoritmi esimese sammu funktsiooni argument on 64-bitine sünkroonimisteade ja kõigis järgnevates etappides - eelmine krüpteeritud andmete plokk W(i-1).

Imitatsioonid

Arendusprotsess imitatsioonivirnad on ühtne kõigi andmete krüpteerimisrežiimide jaoks.

Imitatsiooni sisestamine on p-bitist koosnev plokk (imitation insertion Ip), mis luuakse kas enne kogu sõnumi krüptimist või paralleelselt plokkide kaupa krüpteerimisega. Esimesed avaandmete plokid, mis on kaasatud sisestussimulatsiooni väljatöötamisse, võivad sisaldada teenuseteavet (näiteks aadressiosa, kellaaeg, sünkroonimissõnum) ja olla krüpteerimata. Parameetri p väärtus (simuleeritud sisestuse kahendnumbrite arv) määratakse krüptograafiliste nõuetega, võttes arvesse asjaolu, et valehäirete tekitamise tõenäosus on 1/2^p.

Sisestusimitatsiooni saamiseks esitatakse avaandmed 64-bitiste plokkidena T(i) (i = 1, 2,..., m , kus m määratakse krüpteeritud andmete hulga järgi). Avaandmete esimene plokk T(1) allutatakse lihtsas asendusrežiimis krüpteerimisalgoritmi esimesele 16 tsüklile vastavale teisendusele. Lisaks kasutatakse andmete krüptimiseks kasutatavat võtit imitatsiooni sisestamise genereerimiseks võtmena.

Pärast 16 töötsüklit saadud 64-bitine arv liidetakse moodul 2 teise avatud andmeplokiga T(2). Summeerimistulemus allutatakse uuesti teisendusele, mis vastab krüpteerimisalgoritmi esimesele 16 tsüklile lihtsas asendusrežiimis. Saadud 64-bitine arv lisatakse modulo 2 kolmandasse avatud andmeplokki T(3) ja nii edasi. Viimane plokk T(m), mis on vajadusel polsterdatud täis 64-bitiseks nullidega plokiks, liidetakse moodul 2 sammuga m-1 tehtud töö tulemusega, misjärel see krüpteeritakse lihtsas asendusrežiimis üle esimese. Algoritmi 16 tsüklit. Vastuvõetud 64-bitise arvu hulgast valitakse segment Ip pikkusega p bitti.

Imitatsioonisisend Ip edastatakse pärast krüpteeritud andmeid sidekanali kaudu või arvuti mällu. Sissetulevad krüptitud andmed dekrüpteeritakse ja vastuvõetud avaandmete T(i) plokkidest genereeritakse imitatsioonisisend Ip, mida seejärel võrreldakse sidekanalist või arvuti mälust saadud imitatsioonilisa IR-ga. ei ühti, loetakse kõik dekrüpteeritud andmed valeks.

Krüpteerimisalgoritm GOST 28147-89, selle kasutamine ja tarkvara juurutamine Intel x86 platvormi arvutites.

Andrei Vinokurov

Algoritmi kirjeldus.

Tingimused ja nimetused.

Vene Föderatsiooni krüpteerimisstandardi kirjeldus sisaldub väga huvitavas dokumendis pealkirjaga "GOST 28147-89 Cryptographic Transformation Algorithm". Asjaolu, et selle pealkirjas on termini "krüptimine" asemel üldisem mõiste " krüptograafiline teisendus ' ei ole juhus. Lisaks mitmele tihedalt seotud krüpteerimisprotseduurile kirjeldatakse dokumendis üht genereerimise algoritmi imitatsioonid . Viimane pole midagi muud kui krüptograafiline juhtkombinatsioon, st algandmetest salajase võtme abil genereeritud kood. imitatsioonikaitse või kaitsta andmeid volitamata muudatuste eest.

GOST-algoritmide erinevatel etappidel tõlgendatakse ja kasutatakse andmeid, millega nad töötavad, erineval viisil. Mõnel juhul käsitletakse andmeelemente sõltumatute bittide massiividena, mõnel juhul märgita täisarvuna, mõnel juhul keeruka, mitmest lihtsamast elemendist koosneva struktuurielemendina. Seetõttu tuleb segaduse vältimiseks kokku leppida kasutatavas tähises.

Selle artikli andmeelemendid on tähistatud suurte ladina tähtedega ja kaldkirjaga (näiteks X). Läbi | X| tähistab andmeelemendi suurust X bittides. Seega, kui tõlgendame andmeelementi X mittenegatiivse täisarvuna võime kirjutada järgmise ebavõrdsuse:

Kui andmeelement koosneb mitmest väiksema suurusega elemendist, näidatakse seda asjaolu järgmiselt: X=(X 0 ,X 1 ,…,X n –1)=X 0 ||X 1 ||…||X n-1. Nimetatakse protseduuri mitme andmeelemendi üheks ühendamiseks konkatenatsioon andmed ja seda tähistatakse sümboliga "||". Loomulikult peab andmeelementide suuruste puhul kehtima järgmine seos: | X|=|X 0 |+|X 1 |+…+|X n-1 |. Komplekssete andmeelementide ja liitmisoperatsiooni määramisel loetletakse koostisosad olevad andmeelemendid kasvavas tähtsuse järjekorras. Teisisõnu, kui tõlgendame liitelementi ja kõiki selles sisalduvaid andmeelemente märgita täisarvudena, saame kirjutada järgmise võrdsuse:

Algoritmis saab andmeelementi tõlgendada üksikute bittide massiivina, mille puhul bitid on tähistatud massiiviga sama tähega, kuid väikese tähega, nagu on näidatud järgmises näites:

X=(x 0 ,x 1 ,…,x n –1)=x 0 +2 1 x 1 +…+2 n-1 · x n –1 .

Seega, kui tähelepanu pöörata, siis nn. numbrite "little-endian" nummerdamine, st. mitmebitiste andmesõnade sees on üksikud kahendnumbrid ja nende väiksemate arvudega rühmad vähem olulised. See on sõnaselgelt kirjas standardi punktis 1.3: "Kakskomponentide lisamisel ja tsükliliselt nihutamisel on kõrgeimad bitid suurte arvudega akumulaatorite bitid." Edasi näevad standardi punktid 1.4, 2.1.1 jt ette hakata virtuaalse krüpteerimisseadme salvestusregistreid täitma alumiste andmetega, s.o. vähemtähtsad auastmed. Täpselt sama nummerdamisjärjestus on kasutusele võetud ka Intel x86 mikroprotsessori arhitektuuris, mistõttu ei nõua šifri tarkvaraline juurutamine sellel arhitektuuril andmesõnade sees mingeid täiendavaid bittide permutatsioone.

Kui andmeelementidega tehakse mingi toiming, millel on loogiline tähendus, siis eeldatakse, et see toiming sooritatakse elementide vastavate bittidega. Teisisõnu A B=(a 0 b 0 ,a 1 b 1 ,…,a n –1 b n-1), kus n=|A|=|B| ja sümbol " " tähistab suvalist binaarset loogilist operatsiooni; viitab tavaliselt operatsioonile eksklusiivne või , mis on ka summeerimismooduli 2 toiming:

Šifri koostamise loogika ja GOST-i põhiteabe struktuur.

Kui uurite hoolikalt originaalset GOST 28147–89, märkate, et see sisaldab mitme taseme algoritmide kirjeldust. Kõige tipus on praktilised algoritmid, mis on loodud andmemassiivide krüptimiseks ja nende jaoks võltsitud lisade väljatöötamiseks. Kõik need põhinevad kolmel madalama taseme algoritmil, mida tekstis nimetatakse GOSTiks tsüklid . Nendele põhialgoritmidele viidatakse selles artiklis kui põhitsüklid et eristada neid kõigist teistest ahelatest. Neil on järgmised nimed ja tähistused, viimased on antud sulgudes ja nende tähendust selgitatakse hiljem:

• krüpteerimistsükkel (32-3);
• dekrüpteerimistsükkel (32-P);
• imitatsiooni vahetüki genereerimise tsükkel (16-З).

Iga põhitsükkel on omakorda ühe protseduuri mitmekordne kordamine, mida selles artiklis nõutakse täpsuse kohta. krüptotransformatsiooni peamine etapp .

Seega, GOST-i mõistmiseks peate mõistma järgmist kolme asja:

• mis on juhtunud põhisamm krüptoteisendused;
• kuidas põhisammudest moodustuvad põhitsüklid;
• nagu kolmest põhitsüklid liitke kokku kõik GOST-i praktilised algoritmid.

Enne nende probleemide uurimise alustamist peaksime rääkima GOST-i algoritmide kasutatavast põhiteabest. Vastavalt Kirchhoffi põhimõttele, mida rahuldavad kõik laiemale avalikkusele tuntud kaasaegsed šifrid, tagab krüpteeritud sõnumi salastatuse just selle salastatus. GOSTis koosneb põhiteave kahest andmestruktuurist. Lisaks võti nõutav kõigi šifrite jaoks, sisaldab see ka asendustabel . Allpool on toodud GOST-i võtmestruktuuride peamised omadused.

Krüptotransformatsiooni peamine samm.

Peamine krüpto teisendamise etapp on sisuliselt operaator, mis määratleb 64-bitise andmeploki teisendamise. Selle operaatori lisaparameeter on 32-bitine plokk, mida kasutatakse võtme mis tahes elemendina. Peamise sammu algoritmi skeem on näidatud joonisel 1.

Joonis 1. Algoritmi GOST 28147-89 krüptotransformatsiooni põhietapi skeem.

Allpool on peamise sammu algoritmi selgitused:

Samm 0

• N– 64-bitine andmeplokk, mis tuleb teisendada, sammu täitmise ajal on see kõige vähem oluline ( N 1) ja vanemad ( N 2) osi käsitletakse eraldiseisvate 32-bitiste märgita täisarvudena. Seega võib kirjutada N=(N 1 ,N 2).
• X– 32-bitine võtmeelement;

Samm 1

Lisamine võtmega. Teisendatud ploki alumisele poolele lisatakse modulo 2 32 etapis kasutatud võtmeelemendiga, tulemus edastatakse järgmisele sammule;

2. samm

Ploki asendamine. Eelmises etapis saadud 32-bitist väärtust tõlgendatakse kaheksa 4-bitise koodiploki massiivina: S=(S 0 , S 1 , S 2 , S 3 , S 4 , S 5 , S 6 , S 7) ja S 0 sisaldab 4 kõige väiksemat ja S 7–4 kõige olulisemat bitti S.

Järgmisena asendatakse iga kaheksa ploki väärtus uuega, mis valitakse asendustabelist järgmiselt: ploki väärtus Si muutub Si- järjekorras element (nummerdamine nullist) i-sellest asendussõlmest (st. i-asenduste tabeli rida, nummerdades ka nullist). Teisisõnu, ploki väärtuse asendusena valitakse asendustabelist element, mille rea number on võrdne asendusploki numbriga ja veeru number, mis on võrdne asendusploki väärtusega 4-bitise mittenegatiivse täisarvuna. Sellest selgub asendustabeli suurus: selles olevate ridade arv on võrdne 4-bitiste elementide arvuga 32-bitises andmeplokis, see tähendab kaheksa ja veergude arv võrdub 4-bitise andmeploki erinevate väärtuste arv, mis on teadaolevalt 2 4, kuusteist.

3. samm

Pööra vasakule 11 bitti. Eelmise sammu tulemust nihutatakse tsükliliselt 11 biti võrra kõrgemate bittide suunas ja kantakse üle järgmisse etappi. Algoritmiskeemis tähistab sümbol oma argumendi tsüklilise nihke funktsiooni 11 biti võrra vasakule, s.o. kõrgemate tasemete suunas.

4. samm

Bitipõhine liitmine: etapis 3 saadud väärtus lisatakse modulo 2 biti kaupa teisendatava ploki kõrgele poolele.

5. samm

Nihutamine mööda ketti: teisendatud ploki alumine osa nihutatakse vanema kohale ja selle asemele asetatakse eelmise sammu tulemus.

6. samm

Saadud teisendatava ploki väärtus tagastatakse põhilise krüpto-teisendusetapi algoritmi täitmise tulemusena.

Krüptograafiliste teisenduste põhitsüklid.

Nagu selle artikli alguses märgitud, kuulub GOST plokkšifrite klassi, see tähendab, et selles sisalduv teabetöötlusüksus on andmeplokk. Seetõttu on üsna loogiline eeldada, et see määratleb algoritmid krüptograafilisteks teisendusteks, st krüpteerimiseks, dekrüpteerimiseks ja "arvestamiseks" ühe andmeploki juhtimiskombinatsioonis. Neid algoritme nimetatakse põhitsüklid GOST, mis rõhutab nende põhilist tähtsust selle šifri ehitamisel.

Põhitsüklid on üles ehitatud põhilised sammud krüptograafiline teisendus, mida käsitleti eelmises jaotises. Põhietapi täitmisel kasutatakse ainult ühte 32-bitist võtmeelementi, samas kui GOST-võti sisaldab kaheksat sellist elementi. Seetõttu peab iga põhisilmus võtme täielikuks kasutamiseks peamist sammu oma erinevate elementidega korduvalt läbi viima. Samas tundub üsna loomulik, et igas põhitsüklis tuleb võtme kõiki elemente kasutada sama palju kordi, šifri turvalisuse huvides peaks see arv olema rohkem kui üks.

Kõik ülaltoodud, lihtsalt tervele mõistusele tuginevad oletused osutusid õigeks. Põhitsüklid on korduv täitmine peamine samm kasutades võtme erinevaid elemente ja erinevad üksteisest ainult sammu korduste arvu ja võtmeelementide kasutamise järjekorra poolest. See järjekord on toodud allpool erinevate tsüklite jaoks.

Krüpteerimistsükkel 32-3:

K 0 ,K 1 ,K 2 ,K 3 ,K 4 ,K 5 ,K 6 ,K 7 ,K 0 ,K 1 ,K 2 ,K 3 ,K 4 ,K 5 ,K 6 ,K 7 ,K 0 ,K 1 ,K 2 ,K 3 ,K 4 ,K 5 ,K 6 ,K 7 ,K 7 ,K 6 ,K 5 ,K 4 ,K 3 ,K 2 ,K 1 ,K 0 .

Joonis 2a. Krüpteerimistsükli skeem 32-3

Dekrüpteerimistsükkel 32-P:

K 0 ,K 1 ,K 2 ,K 3 ,K 4 ,K 5 ,K 6 ,K 7 ,K 7 ,K 6 ,K 5 ,K 4 ,K 3 ,K 2 ,K 1 ,K 0 ,K 7 ,K 6 ,K 5 ,K 4 ,K 3 ,K 2 ,K 1 ,K 0 ,K 7 ,K 6 ,K 5 ,K 4 ,K 3 ,K 2 ,K 1 ,K 0 .

Joonis 2b. 32-P dekrüpteerimisahela skeem

Imitatsioonitüki 16-З tootmise tsükkel:

K 0 ,K 1 ,K 2 ,K 3 ,K 4 ,K 5 ,K 6 ,K 7 ,K 0 ,K 1 ,K 2 ,K 3 ,K 4 ,K 5 ,K 6 ,K 7 .

Joonis 2c. Imitatsiooni vahetüki 16-З tootmistsükli skeem.

Igal tsüklil on oma tähtnumbriline tähistus, mis vastab mustrile " n-X", kus nimetuse esimene element ( n), määrab tsükli põhietapi korduste arvu ja tähise teise elemendi ( X), täht, määrab võtmeelementide kasutamisel šifreerimise ("З") või dekrüpteerimise ("Р") järjekorra. See tellimus vajab rohkem selgitust:

Dekrüpteerimistsükkel peaks olema krüpteerimistsükli vastupidine, see tähendab, et nende kahe tsükli järjestikune rakendamine suvalisele plokile peaks andma algse ploki, mida peegeldab järgmine seos: C 32-R ( C 32-З ( T))=T, Kus T- suvaline 64-bitine andmeplokk, C X( T) on tsükli tulemus X andmeploki kohal T. Selle tingimuse täitmiseks GOST-ile sarnaste algoritmide puhul on vajalik ja piisav, et võtmeelementide kasutusjärjekord vastavate tsüklite poolt on vastastikku pöördvõrdeline. Kirjaliku tingimuse kehtivust vaadeldava juhtumi puhul on lihtne kontrollida, võrreldes ülaltoodud järjestusi tsüklite 32-3 ja 32-R jaoks. Eelnevast tuleneb üks huvitav tagajärg: tsükli omadus olla teise tsükli pöördväärtus on vastastikune, st tsükkel 32-3 on pöördvõrdeline tsükli 32-P suhtes. Ehk siis andmeploki krüpteerimist saaks teoreetiliselt teha dekrüpteerimistsükliga, sel juhul tuleks andmeploki dekrüpteerimine teha krüpteerimistsükliga. Kahest vastastikku pöördtsüklist saab krüptimiseks kasutada kumbagi, siis teist tuleb andmete dekrüpteerimiseks kasutada, kuid standard GOST28147-89 määrab tsüklitele rollid ega anna kasutajale selles küsimuses valikuõigust .

Sisestusimitatsiooni genereerimise tsükkel on poole pikem krüpteerimistsüklitest, võtmeelementide kasutamise järjekord selles on sama, mis krüpteerimistsükli esimeses 16 etapis, mida on ülaltoodud jadasid arvestades lihtne näha, seetõttu on see järjestus tsükli tähistuses kodeeritud sama tähega "Z".

Põhitsüklite skeemid on näidatud joonistel 2a-c. Igaüks neist võtab argumendina ja tagastab selle tulemusel 64-bitise andmeploki, mis on näidatud diagrammidel N. Sümbol Step( N,X) tähistab andmeploki peamise krüptoteisendusetapi täitmist N võtmeelemendi kasutamine X. Eespool nimetamata krüptimise ja sisestamise jäljendamise arvutamise tsüklite vahel on veel üks erinevus: krüptimise põhitsüklite lõpus vahetatakse tulemusploki kõrge ja madal osa, see on vajalik nende vastastikuse pöörduvuse tagamiseks. .

Põhilised krüpteerimisrežiimid.

GOST 28147-89 näeb ette kolm järgmist andmete krüpteerimisrežiimi:

• lihtne asendamine,
• mängimine,
• tagasiside gamma,

ja üks täiendav režiim imitatsiooni sisestamise genereerimiseks.

Kõigis nendes režiimides töödeldakse andmeid 64-bitistes plokkides, milleks massiiv jagatakse, allutatakse krüptograafilisele teisendusele, mistõttu GOST viitab plokkšifritele. Kahes mängurežiimis on aga võimalik töödelda mittetäielikku andmeplokki, mis on väiksem kui 8 baiti, mis on hädavajalik suvalise suurusega andmemassiivide krüptimisel, mis ei pruugi olla 8-baidi kordne.

Enne krüptograafiliste teisenduste konkreetsete algoritmide käsitlemist on vaja selgitada järgmistes jaotistes diagrammides kasutatud tähistusi:

T O, T w on vastavalt avatud ja krüptitud andmete massiivid;

, – i- 64-bitised avatud ja krüptitud andmete plokid: , , viimane plokk võib olla mittetäielik: ;

n– 64-bitiste plokkide arv andmemassiivis;

C X on funktsioon 64-bitise andmeploki teisendamiseks põhitsükli "X" algoritmi järgi.

Nüüd kirjeldame peamisi krüptimisrežiime:

Lihtne asendus.

Selle režiimi krüptimine seisneb 32-3 tsükli rakendamises avatud andmeplokkidele, dekrüpteerimises - 32-P tsükli rakendamises krüpteeritud andmeplokkidele. See on režiimidest kõige lihtsam, selles töödeldakse 64-bitisi andmeplokke üksteisest sõltumatult. Lihtsa asendusrežiimi krüpteerimis- ja dekrüpteerimisalgoritmide skeemid on näidatud vastavalt joonistel 3a ja b, need on triviaalsed ja ei vaja kommentaare.

Joonistamine. 3a. Andmete krüpteerimisalgoritm lihtsas asendusrežiimis

Joonistamine. 3b. Andmete dekrüpteerimise algoritm lihtsas asendusrežiimis

Avatud või krüptitud andmete massiivi suurus, mis kuulub vastavalt krüpteerimisele või dekrüpteerimisele, peab olema 64 biti kordne: | T o |=| T w |=64 n , pärast toimingu sooritamist vastuvõetud andmemassiivi suurus ei muutu.

Lihtsal asenduskrüpteerimisrežiimil on järgmised funktsioonid:

• Kuna andmeplokke krüpteeritakse üksteisest ja nende asukohast andmemassiivis sõltumatult, siis kahe identse lihtteksti ploki krüptimisel saadakse identsed šifriplokid ja vastupidi. Märgitud omadus võimaldab krüptoanalüütikul järeldada, et algandmete plokid on identsed, kui ta kohtab krüptitud andmete massiivi identseid plokke, mis on tõsise šifri jaoks vastuvõetamatu.
• Kui krüptitud andmemassiivi pikkus ei ole 8 baidi või 64 biti kordne, tekib probleem, kuidas ja kuidas massiivi viimane mittetäielik andmeplokk täis 64 bitti täita. See ülesanne pole nii lihtne, kui esmapilgul tundub. Ilmsed lahendused nagu "mittetäieliku ploki lisamine nullbitiga" või üldisemalt "mittetäieliku ploki täitmine fikseeritud nulli ja ühe biti kombinatsiooniga" võivad teatud tingimustel anda krüptoanalüütikule võimaluse määrata selle sisu mittetäielik plokk loendusmeetoditega ja see asjaolu tähendab turvašifri vähenemist. Lisaks muutub šifriteksti pikkus, suurenedes lähima 64-bitise täisarvuni, mis on sageli ebasoovitav.

Esmapilgul muudavad ülaltoodud funktsioonid lihtsa asendusrežiimi kasutamise praktiliselt võimatuks, kuna sellega saab krüpteerida vaid andmemassiivid, mille suurus on 64-bitise kordne ja mis ei sisalda korduvaid 64-bitisi plokke. Näib, et nende tingimuste täitmist ei ole võimalik tagada tegelike andmete puhul. See on peaaegu tõsi, kuid on üks väga oluline erand: pidage meeles, et võtme suurus on 32 baiti ja asendustabeli suurus on 64 baiti. Lisaks näitab korduvate 8-baidiste plokkide olemasolu võtmes või asendustabelis nende väga halba kvaliteeti, seega ei saa tegelikes võtmeelementides sellist kordust esineda. Nii saime teada, et lihtne asendusrežiim on võtmeteabe krüptimiseks üsna sobiv, eriti kuna teised režiimid on selleks vähem mugavad, kuna need nõuavad täiendavat sünkroonimisandmeelementi - sünkroonimissõnumit (vt järgmist jaotist). Meie oletus on õige, GOST näeb ette lihtsa asendusrežiimi kasutamise eranditult võtmeandmete krüptimiseks.

Hasartmängud.

Kuidas vabaneda lihtsa asendusrežiimi puudustest? Selleks on vaja võimaldada alla 64-bitiste plokkide krüpteerimist ja tagada, et šifreeritud tekstiplokk sõltuks selle arvust, teisisõnu randomiseerida krüpteerimisprotsess. GOSTis saavutatakse see kahel erineval viisil kahes krüpteerimisrežiimis, pakkudes skaleerimine . Hasartmängud - see on krüptograafilise vahemiku kehtestamine (eemaldamine) avatud (krüpteeritud) andmetele, st andmeelementide jadale, mis on loodud krüpteeritud (avatud) andmete saamiseks mõne krüptoalgoritmi abil. Gamma ülekatteks krüptimise ajal ja selle eemaldamiseks dekrüptimise ajal tuleb kasutada vastastikku pöördvõrdeid binaaroperatsioone, näiteks 64-bitiste andmeplokkide puhul liitmise ja lahutamise modulo 2 64. GOST-is kasutatakse sel eesmärgil bitipõhise liitmise modulo 2 toimimist, kuna see on iseenda pöördväärtus ja pealegi on see kõige lihtsam riistvaras rakendatud. Gamming lahendab mõlemad mainitud probleemid: esiteks on kõik gammaelemendid reaalsete krüpteeritud massiivide puhul erinevad ja seetõttu on isegi kahe identse ploki krüpteerimise tulemus ühes andmemassiivis erinev. Teiseks, kuigi gammaelemente toodetakse võrdsetes 64-bitistes osades, saab kasutada ka osa sellisest plokist, mille suurus on võrdne krüptitud ploki suurusega.

Nüüd läheme otse gammarežiimi kirjelduse juurde. Selle režiimi gamma saadakse järgmiselt: mõne algoritmilise korduva numbrijada generaatori (RGCH) abil genereeritakse 64-bitised andmeplokid, mis seejärel allutatakse 32-3 teisendusele, st krüptimisele lihtsas asendusrežiimis, mille tulemuseks on gammaplokkides. Kuna gamma ülekate ja eemaldamine toimub sama bitipõhise XOR-operatsiooniga, on gammarežiimis krüpteerimis- ja dekrüpteerimisalgoritmid identsed, nende üldine skeem on näidatud joonisel 4.

Skaala genereerimiseks kasutatav RGHR on korduv funktsioon: – korduva jada elemendid, f on teisendusfunktsioon. Seetõttu tekib paratamatult küsimus selle initsialiseerimise ehk elemendi kohta.Tegelikult on see andmeelement gammarežiimide algoritmi parameeter, diagrammidel on see märgitud kui S, ja seda nimetatakse krüptograafias sünkrooni sõnum ja meie GOSTis - esialgne täitmine üks kodeerija registritest. Teatud põhjustel otsustasid GOST-i arendajad kasutada RGHR-i lähtestamiseks mitte otse sünkroonimissõnumit, vaid selle teisendamise tulemust vastavalt tsüklile 32-3: . RGHR-i poolt genereeritud elementide jada sõltub täielikult selle esialgsest täitmisest, see tähendab, et selle jada elemendid sõltuvad nende arvust ja RGHR-i esialgsest täitmisest: kus fi(X)=f(fi –1 (X)), f 0 (X)=X. Võttes arvesse teisendust lihtsa asendusalgoritmi järgi, lisatakse ka sõltuvus võtmest:

Kus G i– i- skaala element, K- võti.

Seega on gammarežiimis kasutatavate gammaelementide jada üheselt määratud võtmeandmete ja sünkroonimissõnumiga. Loomulikult, et krüpteerimisprotseduur oleks pöörduv, tuleb dekrüpteerimisel ja dekrüpteerimisel kasutada sama sünkroonimissõnumit. Gamma unikaalsuse nõudest, mille rike toob kaasa šifri tugevuse katastroofilise vähenemise, tuleneb, et kahe erineva andmemassiivi krüpteerimiseks samal võtmel on vaja tagada šifri tugevuse katastroofiline vähenemine. erinevaid sünkroonimissõnumeid. See toob kaasa vajaduse salvestada või edastada sünkroonimissõnum mööda sidekanaleid koos krüpteeritud andmetega, kuigi mõnel erijuhtudel saab selle eelnevalt määratleda või erilisel viisil arvutada, kui kahe massiivi krüpteerimine samal võtmel on välistatud.

Nüüd vaatame lähemalt RGHR-i, mida GOST-is kasutatakse gammaelementide genereerimiseks. Kõigepealt tuleb märkida, et genereeritud numbrijada statistilisi karakteristikuid ei nõuta. RGHR-i kujundasid GOST-i arendajad, lähtudes vajadusest täita järgmised tingimused:

• RGHR-i genereeritud numbrijada kordusperiood ei tohiks (protsentides) oluliselt erineda antud ploki suuruse maksimaalsest võimalikust väärtusest 2 64;
• RGHR-i toodetud naaberväärtused peavad igas baidis üksteisest erinema, vastasel juhul lihtsustatakse krüptoanalüütiku ülesannet;
• RGHR-i peaks olema üsna lihtne rakendada nii riist- kui ka tarkvaras levinumate protsessoritüüpide puhul, millest enamik on teatavasti 32-bitise mahuga.

Nendele põhimõtetele tuginedes kujundasid GOSTi loojad väga eduka RGHR-i, millel on järgmised omadused:

Kus C 0 =1010101 16 ;

Kus C 1 =1010104 16 ;

Arvu tähistuses olev alaindeks tähendab selle arvusüsteemi, seega kirjutatakse selles etapis kasutatavad konstandid kuueteistkümnendsüsteemis.

Teine avaldis vajab kommentaare, kuna GOST-i tekstis on antud midagi muud: , sama konstandi väärtusega C 1 . Kuid edasi on standardi tekstis antud kommentaar, et selgub, et ülejäänud osa võtmisel moodul 2 32 -1 seal ei mõisteta samamoodi kui matemaatikas. Erinevus seisneb selles, et vastavalt GOST-ile (2 32 -1) mod(2 32 –1)=(2 32 –1), mitte 0. Tegelikult lihtsustab see valemi rakendamist ja selle matemaatiliselt õige avaldis on toodud eespool.

• jada kordusperiood noorema osa jaoks on 2 32, vanema osa jaoks 2 32 -1, kogu jada jaoks on periood 2 32 (2 32 -1), selle tõestuseks on väga lihtne võta endale. Esimene valem neist kahest on rakendatud ühes käsus, teine, vaatamata selle näilisele kohmakusele, kahes käsus kõigil kaasaegsetel 32-bitistel protsessoritel - esimene käsk on tavaline lisamoodul 2 32 koos kandebiti salvestamisega ja teine ​​käsk lisab vastuvõetud väärtusele kandebiti.

Gammarežiimis krüpteerimisalgoritmi skeem on näidatud joonisel 4, allpool on skeemi selgitused:

Joonis 4. Andmete krüptimise (dekrüpteerimise) algoritm gammarežiimis.

Samm 0

Määratleb peamise krüpto teisenduse etapi algandmed:

• T o(w) - suvalise suurusega avatud (krüptitud) andmete massiiv, mis allutatakse krüpteerimis- (dekrüpteerimis-) protseduurile, protseduuri käigus teisendatakse massiiv 64-bitiste osadena;
• S – sünkrooni sõnum , 64-bitine andmeelement, mis on vajalik gammageneraatori lähtestamiseks;

Samm 1

Sünkroonimissõnumi esialgne teisendus, mis viiakse läbi selle "juhuslikuks muutmiseks", st selles esinevate statistiliste mustrite kõrvaldamiseks, kasutatakse tulemust RGHR-i esialgseks täitmiseks;

2. samm

Üks samm RGHRi tööst, mis rakendab oma korduvat algoritmi. Selle etapi ajal on vanem ( S 1) ja noorem ( S 0) andmejada osad genereeritakse üksteisest sõltumatult;

3. samm

Hasartmängud. Järgmine RGHR-i toodetud 64-bitine element allutatakse krüpteerimisprotseduurile 32-3 tsüklis, tulemust kasutatakse gammaelemendina järgmise sama suurusega avatud (krüpteeritud) andmete ploki krüpteerimiseks (dekrüpteerimiseks).

4. samm

Algoritmi tulemuseks on krüptitud (dekrüpteeritud) andmemassiivi.

Gamma kui krüpteerimisrežiimi omadused on järgmised:

1. Avatud andmemassiivi identsed plokid annavad krüptimisel erinevad šifritekstiplokid, mis võimaldavad nende identiteedi fakti varjata.
2. Kuna gamma teostatakse bittide kaupa, on mittetäieliku andmeploki krüptimine hõlpsasti teostatav selle mittetäieliku ploki bittide krüptimisena, mille jaoks kasutatakse gammaploki vastavaid bitte. Seega tuleks mittetäieliku 1-bitise ploki krüptimiseks vastavalt standardile kasutada gammaploki kõige vähem olulist bitti.
3. Krüptimisel kasutatav sünkroonimissõnum tuleb kuidagi edastada, et seda dekrüpteerimisel kasutada. Seda saab saavutada järgmistel viisidel:

• salvestada või edastada sünkroonimissõnum koos krüpteeritud andmemassiiviga, mis suurendab krüptimise ajal andmemassiivi suurust sünkroonimissõnumi suuruse võrra, st 8 baiti võrra;
• kasutada sünkroonimisteate etteantud väärtust või genereerida see allika ja vastuvõtja poolt sünkroonselt vastavalt teatud seadusele, sel juhul ei muutu edastatava või salvestatava andmemassiivi suurus;

Mõlemad meetodid täiendavad üksteist ja neil harvadel juhtudel, kui esimene, kõige levinum neist ei tööta, võib kasutada teist, eksootilisemat. Teisel meetodil on palju vähem rakendust, kuna on võimalik muuta sünkroonimissõnum eelmääratletuks ainult siis, kui antud võtmeteabe komplektis on ilmselgelt krüptitud mitte rohkem kui üks andmemassiv, mida ei juhtu nii sageli. Samuti ei ole alati võimalik sünkroonimissõnumit genereerida sünkroonselt andmemassiivi allikas ja adressaadis, kuna see nõuab tugevat ühendust millegagi süsteemis. Seega näiliselt mõistlik idee kasutada krüpteeritud sõnumite edastamise süsteemis sünkroonimissõnumina edastatud sõnumi numbrit ei sobi, kuna sõnum võib kaduma minna ega jõua adressaadini, sel juhul allika krüpteerimissüsteemid. ja vastuvõtja on sünkroonist väljas. Seetõttu ei ole vaadeldaval juhul alternatiivi sünkroonimissõnumi saatmisele koos krüpteeritud sõnumiga.

Teisalt võib tuua ka vastupidise näite. Oletame, et andmete krüptimist kasutatakse kettal oleva teabe kaitsmiseks ja see on rakendatud madalal tasemel, andmed krüpteeritakse sektorite kaupa, et tagada sõltumatu juurdepääs. Sel juhul ei saa sünkroonimissõnumit koos krüptitud andmetega salvestada, kuna sektori suurust ei saa muuta, kuid seda saab arvutada funktsioonina ketta lugemispea numbrist, raja (silindri) numbrist, ja sektori number rajal. Sel juhul seotakse sünkroonimisteade kettal oleva sektori asukohaga, mis ilma ketta ümbervormindamiseta, st sellel olevaid andmeid hävitamata, peaaegu ei muutu.

Gammarežiimil on veel üks huvitav funktsioon. Selles režiimis krüpteeritakse andmemassiivi bitid üksteisest sõltumatult. Seega sõltub iga šifriteksti bitt lihtteksti vastavast bitist ja loomulikult biti järjekorranumbrist massiivis: . Sellest järeldub, et krüptteksti biti muutmine vastupidiseks toob kaasa lihtteksti biti sarnase muutumise vastupidiseks:

kus tähistab tagurpidi t biti väärtus ().

See omadus annab ründajale võimaluse mõjutada šifriteksti bitte, et teha pärast selle dekrüpteerimist saadud vastavas lihttekstis ennustatavaid ja isegi sihipäraseid muudatusi ilma salajast võtit omamata. See illustreerib krüptoloogias tuntud tõsiasja, et salastatus ja autentsus on erinevad omadused krüptosüsteemid . Teisisõnu, krüptosüsteemi omadused, mis tagavad kaitse loata juurdepääsu eest sõnumi sisule ja loata muutmise eest, on sõltumatud ja võivad ristuda vaid mõnel juhul. Eelnev tähendab, et on olemas krüptoalgoritmid, mis tagavad krüpteeritud andmete teatud salastatuse ja samas ei kaitse muudatuste eest ning vastupidi, tagavad andmete autentsuse ega piira nendega tutvumise võimalust. Seetõttu ei tohiks gammarežiimi kaalutud omadust pidada selle puuduseks.

Hasartmängud tagasisidega.

See režiim on väga sarnane gammarežiimiga ja erineb sellest ainult gammaelementide genereerimise viisi poolest - järgmine gammaelement genereeritakse teisenduse tulemusel eelmise krüptitud andmete ploki 32-3 tsükli jooksul ja krüptida andmemassiivi esimene plokk, gamma-element genereeritakse teisenduse tulemusena sama sünkroonimistsükli järgi. Sellega saavutatakse plokkide linkimine – iga šifriteksti plokk selles režiimis sõltub vastavast ja kõigist eelnevatest lihtteksti plokkidest. Seetõttu nimetatakse seda režiimi mõnikord skaleerimine võrkplokkidega . See, et plokid on lingitud, ei mõjuta šifri turvalisust.

Tagasiside gamma režiimis dekodeerimise ja dekrüpteerimise algoritmide skeem on näidatud joonisel 5 ja oma lihtsuse tõttu ei vaja kommentaare.

Joonis 5. Algoritm andmete krüptimiseks (dekrüpteerimiseks) gammarežiimis koos tagasisidega.

Krüpteerimisel suletud ahelaga gammarežiimis on samad omadused, mis krüptimisel tavalises gammarežiimis, välja arvatud šifriteksti rikumise mõju vastavale tavatekstile. Võrdluseks kirjutame mõlema mainitud režiimi plokkide dekrüpteerimise funktsioonid:

Mängimine;

Mängimine tagasisidega;

Kui tavalises skaleerimisrežiimis mõjutavad šifriteksti teatud bittide muutused ainult vastavaid tavateksti bitte, siis tagasiside skaleerimise režiimis on pilt mõnevõrra keerulisem. Nagu on näha vastavast võrrandist, siis suletud ahela gammarežiimis andmeploki dekrüpteerimisel sõltub avatud andmeplokk vastavatest ja eelnevatest krüpteeritud andmeplokkidest. Seega, kui sisestame krüptitud plokki moonutusi, siis pärast dekrüpteerimist moonutatakse kahte avaandmete plokki - vastavat ja sellele järgnevat ning moonutused on esimesel juhul samasugused kui gammas. režiim ja teisel juhul - nagu režiimis lihtne asendamine. Ehk siis vastavas avaandmete plokis rikutakse samad bitid mis krüpteeritud andmeplokis ja järgmises avaandmete plokis on kõik bitid üksteisest sõltumatud tõenäosusega 1 / 2 muudab nende väärtusi.

Andmete massiivi sisestamise simulatsiooni väljatöötamine.

Eelmistes osades oleme arutanud krüptitud andmete riknemise mõju vastavatele selgetele andmetele. Leidsime, et lihtasendusrežiimis dekrüpteerides moondub vastav avaandmete plokk ettearvamatult ning ploki dekrüpteerimisel gammarežiimis on muutused etteaimatavad. Suletud ahela skaleerimise režiimis on kaks plokki moonutatud, üks ennustatavalt ja teine ​​ettearvamatult. Kas see tähendab, et valeandmete pealesurumise vastase kaitse seisukohalt on gammarežiim halb, samas kui lihtsa asendus- ja tagasisidegamma režiimid on head? - Mitte mingil juhul. Selle olukorra analüüsimisel tuleb arvestada asjaoluga, et ettearvamatuid muutusi dekrüpteeritud andmeplokis on võimalik tuvastada ainult nende samade andmete liiasuse korral ning mida suurem on liiasuse aste, seda tõenäolisem on tuvastada moonutusi. Väga suur liiasus leiab aset näiteks loomulike ja tehiskeelsete tekstide puhul, mille puhul on moonutamise fakt peaaegu vältimatu. Kuid muudel juhtudel, näiteks tihendatud digiteeritud helipiltide moonutamisel, saame lihtsalt teistsuguse pildi, mida meie kõrv suudab tajuda. Sel juhul jääb moonutus avastamata, välja arvatud juhul, kui heli olemuse kohta on a priori teavet. Järeldus on järgmine: kuna mõnede krüpteerimisrežiimide võime tuvastada krüptitud andmetesse sisestatud moonutusi sõltub suuresti krüptitud andmete olemasolust ja liiasuse astmest, ei ole see võime vastavate režiimide immanentne omadus ja seda ei saa pidada nende eelis.

Krüpteeritud andmemassiivis teatud tõenäosusega moonutuste tuvastamise probleemi lahendamiseks näeb GOST ette täiendava krüptograafilise teisendamise režiimi - imiteeritud sisestamise genereerimise. Võltsitud sisestus on juhtkombinatsioon, mis sõltub avatud andmetest ja salajase võtme teabest. Sisestusmiimika kasutamise eesmärk on tuvastada kõik juhuslikud või tahtlikud muudatused teabemassiivis. Eelmises lõigus kirjeldatud probleemi saab edukalt lahendada, lisades krüptitud andmetele võltsitud sisestuse. Potentsiaalse ründaja jaoks on järgmised kaks ülesannet praktiliselt lahendamatud, kui tal ei ole võtit:

• sisestamise simulatsiooni arvutamine etteantud avatud teabemassiivi jaoks;
• avatud andmete valik antud simulatsiooni lisa jaoks;

Simuleeritud sisestuse genereerimise algoritmi skeem on näidatud joonisel 6.

Joonis 6. Algoritm andmemassiivi simuleeritud sisestuse genereerimiseks.

Väljundis vastuvõetud ploki osa võetakse imitatsioonina, tavaliselt selle 32 vähima tähtsusega bitti. Simuleeritud sisestuse suuruse valimisel tuleb arvestada, et valeandmete eduka pealesurumise tõenäosus on võrdne 2 –| I | ühe jõhkra jõu katse kohta, välja arvatud juhul, kui ründajal on tõhusam toore jõu meetod kui lihtne oletamine. 32-bitise võltsitud sisestuse kasutamisel on see tõenäosus

GOST-i krüptoalgoritmide arutelu.

GOST-i krüptograafiline tugevus.

Konkreetse arenduse jaoks kasutatava krüptoalgoritmi valimisel on üheks määravaks teguriks selle tugevus, st vastupidavus vastase katsetele seda paljastada. Šifreerimise tugevuse küsimus taandub lähemal uurimisel kahele omavahel seotud küsimusele:

• kas seda šifrit on üldse võimalik avada;
• kui jah, siis kui raske see praktikas on;

Šifraid, mida ei saa üldse murda, nimetatakse absoluutselt või teoreetiliselt turvaliseks. Selliste šifrite olemasolu tõestab Shannoni teoreem, kuid selle tugevuse hind on vajadus kasutada iga sõnumi krüpteerimiseks võtit, mis ei ole väiksem kui sõnumi enda suurus. Kõikidel juhtudel, välja arvatud mitmed erilised, on see hind liigne, seetõttu kasutatakse praktikas peamiselt šifreid, millel puudub absoluutne turvalisus. Seega on enamkasutatavad krüpteerimisskeemid lahendatavad piiratud aja jooksul, täpsemalt, lõpliku arvu sammudega, millest igaüks on mingi tehte arvudega. Nende jaoks on kõige olulisem praktilise stabiilsuse mõiste, mis väljendab nende avalikustamise praktilist raskust. Selle raskuse kvantitatiivseks mõõdupuuks võib olla elementaarsete aritmeetiliste ja loogiliste toimingute arv, mis tuleb sooritada šifri lahendamiseks, see tähendab, et määrata antud šifri jaoks vastav lihttekst tõenäosusega, mis ei ole väiksem kui etteantud väärtus. Samas võib krüptoanalüütikul lisaks dekrüpteeritud andmemassiivile olla avaandmete ja vastavate krüptitud andmete plokid või isegi võimalus hankida vastavaid krüptitud andmeid mis tahes tema valitud avaandmete jaoks – olenevalt loetletud ja paljudest. muud täpsustamata seisundid, eristatakse eraldi krüptoanalüüsi liike.

Kõik kaasaegsed krüptosüsteemid on üles ehitatud Kirchhoffi põhimõttel, st krüpteeritud sõnumite salastatuse määrab võtme saladus. See tähendab, et isegi kui krüpteerimisalgoritm ise on krüptoanalüütikule teada, ei saa ta ikkagi sõnumit lahti krüpteerida, kui tal puudub vastav võti. Šifr loetakse hästi kavandatuks, kui seda pole võimalik tõhusamalt purustada kui toore jõuga otsimine kogu võtmeruumi ulatuses, s.t. üle kõigi võimalike võtmeväärtuste. Tõenäoliselt vastab GOST sellele põhimõttele - intensiivse uurimistöö aastate jooksul pole selle krüptoanalüüsi jaoks välja pakutud ühtegi tõhusat meetodit. Tugevuse poolest on see mitu suurusjärku parem kui kunagine Ameerika krüpteerimisstandard DES.

GOST kasutab 256-bitist võtit ja võtmeruumi suurus on 2256 . Ükski praegu eksisteeriv või lähitulevikus kasutusele võetav elektroonikaseade ei suuda võtit kätte saada vähem kui sadade aastatega. Sellest väärtusest on tänapäeval saanud sümmeetriliste krüptoalgoritmide de facto võtmesuuruse standard ja seda toetab ka USA uus krüpteerimisstandard. Endine Ameerika standard DES, mille reaalne võtme suurus on 56 bitti ja võtmeruumi suurus vaid 256, ei ole tänapäevaste arvutusvahendite võimaluste valguses enam piisavalt tugev. Seda näitasid 1990. aastate lõpus mitmed edukad toore jõu rünnakud DES-i vastu. Lisaks kasutati DES-i jaoks spetsiaalseid krüptoanalüüsi meetodeid, nagu diferentsiaal- ja lineaaranalüüs. Sellega seoses võib DES pakkuda rohkem uurimistööd või teaduslikku huvi kui praktilist huvi. 1998. aastal tunnistati selle krüptograafiline nõrkus ametlikult – USA riiklik standardiinstituut soovitas kasutada kolmekordset DES-krüptimist. Ja 2001. aasta lõpus kiideti ametlikult heaks uus USA krüpteerimisstandard AES, mis oli üles ehitatud erinevatel põhimõtetel ja vaba eelkäija puudustest.

Märkused GOST-i arhitektuuri kohta.

Teatavasti esindab kodumaine krüpteerimisstandard tervet samadel põhimõtetel üles ehitatud šifrite perekonda. Selle kuulsaim "sugulane" on endine Ameerika krüpteerimisstandard, DES-algoritm. Kõik need šifrid, nagu ka GOST, sisaldavad kolme taseme algoritme. Aluseks on alati mingi kindel “põhisamm”, mille alusel ehitatakse sarnaselt “põhitsüklid” ning nende alusele ehitatakse juba praktilised krüpteerimise ja imitatsiooni sisestamise arendamise protseduurid. Seega seisneb selle perekonna iga šifri eripära just selle põhietapis või õigemini isegi selle osas. Kuigi klassikaliste plokkšifrite arhitektuur, kuhu GOST kuulub, jääb selle artikli ulatusest kaugele kaugemale, tasub selle kohta siiski paar sõna öelda.

Krüptotransformatsiooni põhietappide algoritmid selliste šifrite jaoks nagu GOST on üles ehitatud identsel viisil ja seda arhitektuuri nimetatakse tasakaalustatud Feisteli võrk (tasakaalustatud Feisteli võrk) sai nime selle isiku järgi, kes selle esimesena välja pakkus. Andmete teisendusskeem ühel tsüklil või, nagu seda tavaliselt nimetatakse, ümmargune , näidatud joonisel 7.

Joonis 7. GOST-ile sarnaste plokkšifrite peamise krüpto-teisendusetapi sisu.

Põhiastme sisendisse juhitakse ühtlase suurusega plokk, mille ülemine ja alumine pool töödeldakse üksteisest eraldi. Teisenduse käigus asetatakse ploki alumine pool vanema asemele ja vanem kombineeritakse bitipõhise " eksklusiivne või » mõne funktsiooni arvutamise tulemusega, noorema asemel. See funktsioon, mis võtab argumendina ploki alumise poole ja võtmeteabe elemendi ( X), on šifri sisuosa ja seda nimetataksegi selleks krüpteerimisfunktsioon . Erinevatel põhjustel osutus soodsaks jagada krüpteeritud plokk kaheks ühesuuruseks osaks: | N 1 |=|N 2 | - just see asjaolu peegeldab arhitektuuri nimetuses sõna "tasakaalustatud". Siiski kasutatakse aeg-ajalt ka krüptimisega tasakaalustamata võrke, kuigi mitte nii sageli kui tasakaalustatud võrke. Lisaks nõuavad šifri tugevuse kaalutlused, et võtmeelemendi suurus ei oleks väiksem kui poole ploki suurus: GOST-is on kõik kolm suurust 32 bitti. .

Kui rakendame ülaltoodut GOST-algoritmi põhietapi skeemile, saab selgeks, et algoritmi plokid 1,2,3 (vt joonis 1) määravad selle krüpteerimisfunktsiooni arvutuse ning plokid 4 ja 5 seatakse. põhietapi väljundploki moodustamine sisendploki sisu ja krüpteerimisfunktsiooni väärtuse alusel. Täpsemat infot tänapäevaste salavõtmega plokkšifrite arhitektuuride kohta leiab klassikalistest töödest või mugandatud kujul minu töödest.

Eelmises osas võrdlesime juba vastupidavuse osas DES ja GOST, nüüd võrdleme neid funktsionaalse sisu ja teostamise lihtsuse poolest. GOST-i krüpteerimistsüklites korratakse põhietappi 32 korda, DES-i puhul on see väärtus 16. GOST-i krüpteerimisfunktsioon ise on aga palju lihtsam kui sarnane DES-funktsioon, milles on palju ebaregulaarseid bitipermutatsioone. Neid toiminguid rakendatakse kaasaegsetes spetsialiseerimata protsessorites äärmiselt ebaefektiivselt. GOST ei sisalda selliseid toiminguid, seega on see tarkvara juurutamiseks palju mugavam.

Ükski autori poolt Intel x86 platvormi jaoks käsitletud DES-rakendustest ei saavuta poole võrra paremat jõudlust kui selles artiklis teile pakutud GOST-i teostus, vaatamata kaks korda lühemale tsüklile. Kõik eelnev viitab sellele, et GOST-i arendajad võtsid arvesse nii DES-i positiivseid kui ka negatiivseid külgi ning hindasid realistlikumalt krüptoanalüüsi praegusi ja tulevasi võimalusi. DES-i võtmine šifri rakenduste jõudluse võrdlemisel ei ole aga enam asjakohane. USA uuel krüpteerimisstandardil läheb efektiivsusega palju paremini – 256-bitise GOST-iga sama võtmesuurusega AES töötab sellest umbes 14% kiiremini – seda võrreldakse "elementaartoimingute" arvuga. Lisaks on GOST-i praktiliselt võimatu paralleelstada, samas kui AES-il on selles osas palju rohkem võimalusi. Mõne arhitektuuri puhul võib see AES-i eelis olla väiksem, teistel võib see olla suurem. Seega ulatub Intel Pentium protsessoril see 28% -ni. Üksikasjad leiate aadressilt.

Peamised teabe kvaliteedinõuded ja peamised allikad.

Mitte kõik võtmed ja asendustabelid ei taga maksimaalset šifritugevust. Igal krüpteerimisalgoritmil on võtmeteabe hindamiseks oma kriteeriumid. Niisiis, DES-algoritmi jaoks on nn. nõrgad klahvid ”, milles avatud ja krüptitud andmete vaheline seos ei ole piisavalt maskeeritud ning šifrit on suhteliselt lihtne murda.

Ammendava vastuse küsimusele võtmete ja GOST-i asendustabelite kvaliteedikriteeriumide kohta, kui seda üldse kuskilt saada on, on ainult algoritmi arendajatelt. Vastavaid andmeid avatud ajakirjanduses ei avaldatud. Kuid vastavalt kehtestatud korrale tuleb templiga varustatud teabe krüpteerimiseks kasutada volitatud organisatsioonilt saadud võtmeandmeid. Kaudselt võib see viidata "täide" võtmeandmete kontrollimise meetodite olemasolule. Kui nõrkade võtmete olemasolu GOSTis on vaieldav probleem, siis nõrkade asendussõlmede olemasolu on väljaspool kahtlust. On ilmselge, et "triviaalne" asendustabel, mille järgi mis tahes väärtus asendatakse iseendaga, on nii nõrk, et selle kasutamisel läheb šifr lihtsalt katki, ükskõik mis võtmega ka poleks.

Nagu eespool märgitud, ei ole põhiteabe hindamise kriteeriumid saadaval, kuid nende kohta saab siiski teha mõningaid üldisi kaalutlusi.

Võti

Võti peab olema statistiliselt sõltumatute bittide massiiv, mis võtavad võrdse tõenäosusega väärtused 0 ja 1. Ei saa täielikult välistada, et mõned konkreetsed võtmeväärtused võivad osutuda "nõrgaks", st šifr ei pruugi nende kasutamisel pakkuda teatud turbetaset. Kuid arvatavasti on selliste väärtuste osatähtsus kõigi võimalike võtmete kogumassis tühine. Vähemalt ei ole intensiivsed šifriuuringud veel ühegi teadaoleva (st FAPSI pakutud) asendustabeli jaoks sellist võtit näidanud. Seetõttu on teatud tõeliselt juhuslike arvude generaatori abil genereeritud võtmed kvaliteetsed tõenäosusega, mis erineb ühtsusest tühiselt väikese summa võrra. Kui võtmed genereeritakse pseudojuhuslike arvude generaatori abil, peab kasutatav generaator pakkuma ülaltoodud statistilisi omadusi ja lisaks olema kõrge krüptograafiline tugevus, mitte vähem kui GOST-il endal. Teisisõnu ei tohiks generaatori poolt genereeritud elementide jada puuduvate liikmete määramine olla lihtsam kui šifri purustamine. Lisaks saab halva statistilise jõudlusega võtmete tagasilükkamiseks kasutada erinevaid statistilisi kriteeriume. Praktikas piisab tavaliselt kahest kriteeriumist - võtmebittide võrdse tõenäosuse jaotuse kontrollimiseks väärtuste 0 ja 1 vahel kasutatakse tavaliselt Pearsoni kriteeriumi ("chi ruut") ja võtmebittide sõltumatuse kontrollimiseks on seeriakriteerium. kasutatud. Mainitud kriteeriumide kohta saate lugeda matemaatilise statistika õpikutest või teatmeteostest.

Parim viis võtmete genereerimiseks oleks kasutada riistvaralisi MF-andureid, kuid see pole majanduslikel põhjustel alati vastuvõetav. Väikese võtmeteabe massiivi genereerimisel kasutatakse ja kasutatakse praktikas laialdaselt mõistlikku alternatiivi sellise anduri kasutamisele "elektroonilise ruleti" meetodil, kui juhuslike bittide järgmine genereeritud osa sõltub hetkest, mil operaator teatud klahvi vajutab. arvuti klaviatuuril. Selles skeemis on juhuslike andmete allikaks arvutikasutaja, täpsemalt tema reaktsiooni ajalised omadused. Sellisel juhul saab ühe klahvivajutuse kohta genereerida vaid paar bitti juhuslikke andmeid, seega on võtmeteabe genereerimise üldine kiirus väike – kuni mitu bitti sekundis. Ilmselgelt ei sobi see lähenemine suurte võtmemassiivide saamiseks.

Juhul, kui on vaja välja töötada suur hulk põhiteavet, on võimalik ja väga laialt levinud kasutada erinevaid pseudojuhuslike arvude tarkvaraandureid. Kuna selline andur nõuab suurt krüptograafilist tugevust, on loomulik kasutada šifri gammageneraatorit ennast - "lõigasime" šifri genereeritud gamma lihtsalt soovitud suurusega "tükkideks", GOST jaoks - igaüks 32 baiti. Loomulikult vajame selle lähenemisviisi jaoks "peavõtit", mille saame ülalkirjeldatud elektroonilise ruleti meetodi abil, ja selle abiga, kasutades gammageneraatori režiimis šifrit, saame hulga võtmeteavet maht, mida vajame. Nii et need kaks võtmete genereerimise viisi - "käsitsi" ja "algoritmiline" - töötavad paralleelselt, täiendades üksteist. Võtmete genereerimise skeemid "madala eelarvega" teabe krüptograafilistes kaitsesüsteemides on peaaegu alati üles ehitatud selle põhimõtte järgi.

Asendustabel

Asendustabel on pikaajaline võtmeelement, see tähendab, et see kehtib palju kauem kui üks võti. Eeldatakse, et see on ühine ühe krüptokaitsesüsteemi kõikidele krüpteerimissõlmedele. Isegi kui asendustabeli konfidentsiaalsust rikutakse, jääb šifri tugevus äärmiselt kõrgeks ega lange alla lubatud piiri. Seetõttu pole erilist vajadust tabelit salajas hoida ja enamikus GOST-i kommertsrakendustes tehakse seda just nii. Teisest küljest on asendustabel kogu šifri tugevuse tagamiseks kriitiline element. Vale tabeli valimisel võib teadaolevate krüptoanalüüsi meetodite abil šifr kergesti puruneda. Asendussõlmede väljatöötamise kriteeriumid on seitsme pitsatiga saladus ja tõenäoliselt ei jaga FAPSI seda lähitulevikus avalikkusega. Lõppkokkuvõttes, selleks, et öelda, kas see konkreetne asendustabel on hea või halb, peate kulutama tohutult tööd – tuhandeid inim- ja masinatunde. Kui tabel on valitud ja kasutatud, saab ta välja vahetada siis ja ainult siis, kui selle kasutamisega šifr osutus ühe või teise krüptoanalüüsi tüübi suhtes haavatavaks. Seetõttu on šifri keskmise kasutaja jaoks parim valik võtta üks mitmest avalikuks saanud tabelist. Näiteks räsifunktsiooni standardist on see ka "keskpangandus"; infot nende tabelite kohta leiab avalikust ajakirjandusest ja isegi internetist, kui hästi otsida.

Neile, kes pole harjunud kasutama lihtsat teed, on allpool toodud üldine skeem kvaliteeditabelite saamiseks:

1. Ühte või teist meetodit kasutades töötate välja kaheksa asendussõlme komplekti, millel on garanteeritud mittelineaarsus. Selliseid meetodeid on mitu, üks neist on nn painutatud funktsioonide kasutamine.
2. Kontrollite kõige lihtsamate "kvaliteedikriteeriumide" rakendamist – näiteks DES asendussõlmede jaoks avaldatud. Siin on mõned üldisemad kaalutlused selle skoori kohta: Iga asendussõlme saab kirjeldada nelja loogilise funktsiooniga neljast loogilisest argumendist. Kui need funktsioonid on sisse kirjutatud minimaalne vorm(st minimaalse võimaliku avaldise pikkusega) ei ole piisavalt keerukad, selline asendussõlm lükatakse tagasi. Lisaks peavad üksikud funktsioonid kogu asendustabeli piires üksteisest piisaval määral erinema. Selles etapis kõrvaldatakse paljud tahtlikult madala kvaliteediga lauad.
3. Teie valitud tabelitega šifri jaoks koostage erinevad ümmargused mudelid, mis vastavad erinevat tüüpi krüptoanalüüsile, ja mõõtke vastavad "profiili" omadused. Nii et lineaarse krüptoanalüüsi jaoks koostage krüpteerimisvooru lineaarne statistiline analoog ja arvutage "profiili" tunnus - mittelineaarsuse indeks. Kui see osutub ebapiisavaks, lükatakse asendustabel tagasi.
4. Lõpuks, kasutades eelmise lõigu tulemusi, allutage šifr oma valitud tabeliga intensiivsele uurimistööle – krüptoanalüüsi katsele kõigi teadaolevate meetoditega. See etapp on kõige raskem ja aeganõudvam. Kuid kui see on tehtud kvaliteetselt, siis võib suure tõenäosusega väita, et teie valitud tabelitega šifrit ei avane lihtsurelik ja võimalik, et see on liiga karm. eriteenused.

Siiski on võimalik teha palju lihtsamalt. Asi on selles, et mida rohkem on šifris voore, seda vähem mõjutavad ühe šifri turvaomadused kogu šifri turvalisust. GOST-is on koguni 32 ringi - rohkem kui peaaegu kõigis sarnase arhitektuuriga šifrites. Seetõttu piisab enamiku kodumaiste ja kaubanduslike rakenduste jaoks asendussõlmede hankimisest sõltumatute juhuslike numbrite 0 kuni 15 permutatsioonidena. Seda saab praktiliselt rakendada näiteks kuueteistkümnest kaardist koosneva paki segamise teel, millest igaühele on määratud üks määratud vahemiku väärtustest.

Asenduste tabeliga seoses tuleb märkida veel üks huvitav fakt. Krüpteerimistsüklite 32-3 ja 32-R pööratavus ei nõua, et asendussõlmed oleksid numbrite permutatsioonid vahemikus 0 kuni 15. Kõik toimib ka siis, kui asendussõlmes on dubleerivad elemendid ja asendus määratakse sellise sõlmega. , on pöördumatu – sel juhul aga šifri tugevus väheneb. Miks see nii on, selles artiklis ei käsitleta, kuid fakti enda kontrollimine pole keeruline. Selleks piisab, kui proovite andmeplokki esmalt krüpteerida ja seejärel dekrüpteerida, kasutades sellist "alaväärtuslikku" asendustabelit, mille sõlmed sisaldavad dubleerivaid väärtusi.

Variatsioonid GOST-i teemal

Väga sageli on krüptograafilises andmekaitsesüsteemis kasutamiseks vaja GOST-ist suurema teostuskiirusega algoritmi ja nii kõrget krüptograafilist tugevust pole vaja. Selliste ülesannete tüüpiline näide on mitmesugused elektroonilised börsikauplemissüsteemid, mis haldavad kauplemisseansse reaalajas. Siin on vaja kasutatavaid krüpteerimisalgoritme, et teha võimatuks süsteemi tööandmete dekrüpteerimine seansi ajal (andmed tehtud tellimuste, tehtud tehingute jms kohta), misjärel on need andmed ründajate jaoks reeglina juba kasutud. . Teisisõnu on vaja vaid paar tundi garanteeritud visadust, mis on kauplemisseansi tüüpiline pikkus. On selge, et täisväärtusliku GOST-i kasutamine selles olukorras oleks varblaste pihta kahurist tulistamine.

Kuidas sel ja sarnastel juhtudel edasi toimida, et krüpteerimise kiirust suurendada? Vastus peitub pinnal – kasutage põhitsüklites šifri modifikatsiooni, milles on vähem põhietappe (ringe). Mitu korda me krüpteerimisringide arvu vähendame, suureneb jõudlus sama palju. Seda muutust on võimalik saavutada kahel viisil – vähendades võtme pikkust ja vähendades võtme "otsingutsüklite" arvu. Tuletage meelde, et põhiliste krüpteerimistsüklite põhietappide arv on N=n m, Kus n on võtmes olevate 32-bitiste elementide arv, m- põhielementide kasutustsüklite arv standardis n=8, m=4. Saate neid numbreid vähendada, kuid lihtsaim võimalus on vähendada võtme pikkust, ilma et see mõjutaks selle kasutusskeemi.

On selge, et töö kiirendamise hind on šifri tugevuse vähenemine. Peamine raskus seisneb selles, et selle languse suurust on üsna raske enam-vähem täpselt hinnata. Ilmselgelt on ainus võimalik viis seda teha šifrivariantide uurimine vähendatud krüptograafilise teisenduse tsüklitega "täielikult". On selge, et esiteks nõuab see salastatud teabe kasutamist, mida omavad ainult GOST-i arendajad, ja teiseks on see väga töömahukas. Seetõttu püüame nüüd anda väga-väga ligikaudse hinnangu, mis põhineb ainult üldistel mustritel.

Mis puudutab šifri vastupanuvõimet “laiaulatuslike” meetoditega purustamisele, st “toore jõu” rünnakule, siis siin on kõik enam-vähem selge: 64-bitine võti on kuskil selle tüübi jaoks ligipääsetavuse äärel. ründe korral on 96-bitise ja suurema võtmega šifr (pidage meeles, et võti peab sisaldama täisarvu 32-bitisi elemente) selle vastu üsna vastupidav. Tõepoolest, mõni aasta tagasi sattus USA endisesse krüpteerimisstandardisse DES korduvalt toore jõuga sissemurdmine – esmalt häkkis sisse globaalse interneti baasil organiseeritud arvutivõrk ja seejärel spetsialiseerunud, s.o. spetsiaalselt selleks otstarbeks loodud arvuti. Oletame, et GOST-i standardversioon, kui see on kaasaegsete protsessorite tarkvaras rakendatud, töötab neli korda kiiremini kui DES. Siis töötab 8-ringiline "vähendatud GOST" 16 korda kiiremini kui DES. Oletame ka, et aja jooksul pärast DES-i häkkimist on arvutustehnoloogia jõudlus Moore'i seaduse järgi neljakordistunud. Selle tulemusena saame, et nüüd on "vähendatud GOST" ühe 64-bitise võtme kontrollimine kaheksa tsükliga 64 korda kiirem, kui kunagi tehti ühe DES-võtme kontrollimine. Seega väheneb selle GOST-i versiooni eelis DES-i ees jõhkra jõu rünnaku keerukuse osas 2 64–56 = 2 8 = 256-lt 256-le. / 64 = 4 korda. Nõus, see on väga illusoorne erinevus, peaaegu mitte midagi.

Palju keerulisem on hinnata GOST-i nõrgestatud modifikatsioonide vastupidavust "intensiivsetele" krüptoanalüüsi meetoditele. Üldmustrit saab aga jälgida ka siin. Fakt on see, et paljude praegu kõige tugevamate krüptoanalüüsi tüüpide "profiili" omadused sõltuvad eksponentsiaalselt krüpteerimisvoorude arvust. Seega on lineaarse krüptoanalüüsi (LCA) puhul see lineaarsuse karakteristik L :

Kus C ja on konstandid, R on voorude arv. Sarnane seos on ka diferentsiaalkrüptoanalüüsi puhul. Vastavalt nende "füüsilisele tähendusele" on kõik seda tüüpi omadused tõenäosused. Tavaliselt on krüptoanalüüsiks vajalike algandmete hulk ja selle keerukus pöördvõrdeline selliste tunnustega. Sellest järeldub, et need töömahukuse näitajad kasvavad plahvatuslikult koos põhiliste krüptimisetappide arvu kasvuga. Seega, kui voorude arvu mitu korda vähendada, muutub kõige tuntumate analüüsitüüpide keerukus väga ligikaudselt ja jämedalt selle võimsuse juureks algsest summast. See on vastupidavuse väga suur langus.

Teisest küljest loodi GOST suure ohutusvaruga ja on tänapäeval vastupidav kõigile teadaolevatele krüptoanalüüsidele, sealhulgas diferentsiaal- ja lineaaranalüüsile. Seoses LCA-ga tähendab see, et selle edukaks rakendamiseks on vaja rohkem "avatud plokk – krüpteeritud plokk" paare kui "looduses olemas", st rohkem kui 2 64 . Ülaltoodut silmas pidades tähendab see, et 16-ringilise GOST-i edukaks LCA-ks on vaja vähemalt plokke või 2 35 baiti või 32 GB andmemahtu ja 8-ringilise GOST-i jaoks vähemalt plokke või 2 19 baiti või 0,5 MB.

Järeldused kõigest ülaltoodust on toodud järgmises tabelis, mis võtab kokku GOSTi vähendatud versioonide omadused.

Ringide arv	Võtme suurus, bitt	Kiire tegevuse indeks	Šifri tõenäolised omadused (väga ligikaudne hinnang)
24	192	1,33	Vastupidav enamikele tuntud KA tüüpidele või olla vastupanu piiril. KA praktiline rakendamine on võimatu kõrgete algandmete ja töömahukuse nõuete tõttu.
16	128	2	Teoreetiliselt on see teatud tüüpi krüptoanalüüsi jaoks ebastabiilne, kuid nende praktiline rakendamine on enamikul juhtudel raske algandmete ja töömahukuse kõrgete nõuete tõttu.
12	95	2,67	See ei ole vastupidav mõnele teadaolevale krüptoanalüüsi tüübile, küll aga sobib väikese andmemahu (kuni kümnete või sadade KB) lühiajalise salastatuse tagamiseks.
8	64	4	See ei ole vastupidav mõnele teadaolevale krüptoanalüüsi tüübile, kuid sobib väikese andmemahu (kuni kümneid kilobaiteid) salastatuse tagamiseks lühiajaliselt.

Viimased kaks võimalust, 12 ja 8 ringiga, suudavad pakkuda ajaliselt väga-väga piiratud kaitset. Nende kasutamine on õigustatud vaid ülesannetes, kus on nõutav vaid lühiajaline suletud andmete saladus, suurusjärgus mitu tundi. Nende nõrkade šifrite võimalik rakendusvaldkond on elektrooniliste börsikaubandussüsteemide UDP-liikluse sulgemine. Sel juhul krüpteeritakse iga andmepakett (datagramm, keskmine "D" UDP-lühendist) eraldi 64-bitise võtmega ja võti ise krüpteeritakse seansivõtmega (võti, mille ulatus on üks suhtlusseanss kahe arvuti vahel ) ja edastatakse koos andmetega.

Enne GOST-i vähendatud versioonidega lõpetamist ütlen, et kõik ülaltoodud kaalutlused on väga spekulatiivsed. Standard tagab vastupidavuse ainult ühe, 32-ringilise variandi jaoks. Ja keegi ei saa teile anda garantiid, et šifri vähendatud variantide vastupidavus purunemisele muutub ülaltoodud viisil. Kui otsustad neid siiski oma arendustes kasutada, pea meeles, et oled seadnud sammud väga raputavale maapinnale, mis võib iga hetk su jalge alt välja libiseda. Kuna krüpteerimiskiirus on teie jaoks ülioluline, peaksite võib-olla kaaluma kiirema šifri või võimsama arvuti kasutamist? Veel üks kaalutlus, mida tasub teha, on see, et GOST-i nõrgestatud versioonid oleksid kasutatavate asendusüksuste kvaliteedi suhtes võimalikult tundlikud.

Käsitletaval probleemil on ka varjukülg. Mis siis, kui krüpteerimiskiirus pole kriitiline ja tugevusnõuded on väga ranged? GOST-i vastupidavuse suurendamiseks on kaks võimalust - me nimetame neid tinglikult "laiaulatuslikuks" ja "intensiivseks". Esimene neist ei ole midagi muud kui lihtne krüpteerimisvoorude arvu suurendamine. Mulle pole täiesti selge, miks seda tegelikult vaja võib minna, sest kodumaine standard annab juba ilma selleta vajaliku stabiilsuse. Kui aga sind vaevab üle nõutava taseme paranoia (ja kõik "infokaitsjad" on lihtsalt kohustatud seda kannatama, see on kutsesobivuse tingimus, küsimus on vaid juhtumi tõsiduses :), see aitab teil rahune veidi maha. Kui te pole selle KGB šifri või kasutatava asendustabeli osas kindel, tehke lihtsalt kahekordne, neljakordne jne. voorude arv – valige kordus juhtumi tõsiduse põhjal. Selline lähenemine võimaldab tõesti šifri tugevust suurendada – kui varem oli krüptoanalüüs lihtsalt võimatu, siis nüüd on see ruudus võimatu!

Keerulisem ja huvitavam on küsimus, kas šifri tugevust on võimalik suurendada ilma peamiste krüptimisetappide arvu ja struktuuri muutmata. Üllataval kombel on vastus sellele küsimusele jah, kuigi me astume taas spekulatsioonide kõikuval pinnasel. Fakt on see, et GOST-is peaks see põhikonversioonietapil 4 asendama 4 bitiga, kuid praktikas (sellest räägime hiljem) teostavad kõik tarkvararakendused baithaaval asendamise, s.t. 8 x 8 bitti – seda tehakse tõhususe huvides. Kui kujundada selline asendus kohe 8-bitisena, siis parandame oluliselt ühe ringi omadusi. Esiteks suureneb "hajutuse" tunnus või "laviini" indikaator - üks lähteandmete bitt ja / või võti mõjutab rohkemate tulemuse bitte. Teiseks saab suuremate asendussõlmede puhul saada madalamaid diferentsiaal- ja lineaarkarakteristikuid, vähendades seeläbi šifri vastuvõtlikkust sarnast tüüpi krüptoanalüüsile. See kehtib eriti vähendatud GOST-i tsüklite kohta ning 8- ja 12-ringiliste valikute puhul on selline samm lihtsalt vajalik. See kompenseerib mõnevõrra nende vastupidavuse kaotust voorude arvu vähenemise tõttu. Selle tehnika kasutamise muudab keeruliseks see, et peate sellised "suurenenud" asendussõlmed ise kujundama. Ja ka see, et suuremaid sõlme on üldiselt märgatavalt keerulisem kujundada kui väiksemaid.

Standardi mittestandardne kasutamine.

Loomulikult on GOST-i krüptoalgoritmide põhieesmärk andmete krüpteerimine ja imitatsioonikaitse. Neid võib aga leida muudest rakendustest, mis on loomulikult seotud teabe kaitsmisega. Räägime neist lühidalt:

1. Gammarežiimis krüptimiseks näeb GOST ette krüptograafilise gamma genereerimise - heade statistiliste omaduste ja kõrge krüptograafilise tugevusega bittide jada. Lisaks kasutatakse seda gammat avatud andmete muutmiseks, mille tulemuseks on krüptitud andmed. See pole aga krüptograafilise gamma ainus võimalik rakendus. Fakt on see, et selle väljatöötamise algoritm on suurepäraste omadustega pseudojuhuslike arvujadade generaator (PRNG). Muidugi ei ole väga mõistlik kasutada sellist PRNG-d, kus on vaja ainult genereeritud jada statistiliste karakteristikute saamist ja krüptograafilist tugevust pole vaja, see pole eriti mõistlik - nendeks puhkudeks on palju tõhusamad generaatorid. Kuid mitmesuguste infoturbega seotud rakenduste jaoks on selline allikas väga kasulik:

• Nagu eespool märgitud, saab gammat kasutada võtmete genereerimiseks "toorainena". Selleks peate lihtsalt hankima soovitud pikkusega gammasegmendi - 32 baiti. Nii saab võtmeid teha vastavalt vajadusele ja neid pole vaja salvestada – kui sellist võtit uuesti vaja läheb, on selle uuesti genereerimine piisavalt lihtne. Tuleb vaid meeles pidada, millisel võtmel see algselt genereeriti, millist sünkroonimissõnumit kasutati ja millisest genereeritud gamma baidist võti alguse sai. Kogu teave, välja arvatud kasutatud võti, ei ole salajane. See lähenemine muudab üsna keeruka ja hargnenud võtmesüsteemi juhtimise lihtsaks, kasutades ainult ühte "peavõtit".
• Sarnaselt eelmisele saab paroolide genereerimisel kasutada algse "toorainena" gammat. Siin võib tekkida küsimus, miks neid üldse genereerida on vaja, kas pole lihtsam neid lihtsalt vastavalt vajadusele välja mõelda. Selle lähenemisviisi läbikukkumist näitasid selgelt rida vahejuhtumeid arvutivõrkudes, millest suurim oli 1988. aasta novembris 1988. aasta novembris Interneti ööpäevane halvatus, mille põhjustas "Morrise uss". Üks viise, kuidas pahatahtlik programm arvutisse tungis, oli parooli arvamine: programm üritas süsteemi siseneda, sorteerides järjest mitusada parooli oma sisemisest loendist, ja märkimisväärsel osal juhtudest suutis see seda teha. Inimese fantaasia paroolide väljamõtlemisel osutus väga kehvaks. Seetõttu genereerib ja jagab paroolid nendes organisatsioonides, kus turvalisusele pööratakse piisavalt tähelepanu, turvasüsteemi administraator. Parooli genereerimine on veidi keerulisem kui võtme genereerimine, kuna sel juhul tuleb “toores” binaarne gamma teisendada märgikujuliseks, mitte lihtsalt “tükkideks lõigata”. Lisaks võib olla vaja üksikutest väärtustest loobuda tagamaks, et kõik tähestiku märgid ilmuvad paroolis võrdselt.
• Teine võimalus krüptograafilise ulatuse kasutamiseks on magnetkandjal olevate andmete tagatud kustutamine. Fakt on see, et isegi teabe ülekirjutamisel magnetkandjale jäävad jäljed varasematest andmetest, mida saab vastava uuringuga taastada. Nende jälgede hävitamiseks tuleb sellist ülekirjutamist teha mitu korda. Selgus, et infot oleks vaja vähem kordi meediasse ümber kirjutada, kui selline protseduur kasutab juhuslikke või pseudojuhuslikke andmeid, mis jäävad ülekirjutatud infot taastada püüdvatele asjatundjatele teadmata. Siin tuleb kasuks gamma-šifr.

2. Mitte ainult krüptograafilist gammat, vaid ka krüptograafilist teisendust ennast saab kasutada vajaduste jaoks, mis ei ole otseselt krüpteerimisega seotud:

• Teame, et üks sellistest GOST-i kasutamise võimalustest on andmemassiivide jaoks simuleeritud sisestuse väljatöötamine. Kuid mis tahes plokkšifri, sealhulgas GOST-i põhjal on üsna lihtne koostada skeemi ühesuunalise räsifunktsiooni arvutamiseks, mida kirjanduses nimetatakse ka MDC-ks ja mis erinevates allikates tähistab tuvastuskoodi muutmine / manipuleerimine (M modifikatsioon/ M anipulatsioon D leidmine C ood) või sõnumi kokkuvõte (M essee D igest C ood). Esimene dekodeerimine ilmus kirjandusse palju varem, teise, lühema, mõtlesid ma arvan välja need, kes esimest ei suutnud meeles pidada :) - see oli nali. MDC-d saab vahetult kasutada imitatsioonikaitsesüsteemides imitatsiooni sisestamise analoogina, mis aga ei sõltu salavõtmest. Lisaks on MDC laialdaselt kasutusel elektrooniliste digitaalallkirjade (EDS) skeemides, kuna enamik neist skeemidest on loodud nii, et fikseeritud suurusega andmeplokki on mugav allkirjastada. Nagu teate, on käsitletud standardi GOST 28147-89 põhjal koostatud Vene Föderatsiooni standard ühesuunalise räsifunktsiooni arvutamiseks GOST R34.11-94.
• Vähem teatakse, et mis tahes plokkšifri, sealhulgas GOST-i alusel saab ehitada täielikult toimiva EDS-skeemi, millel on salajane allkirjavõti ja avatud kinnituskombinatsioon. Mitmel põhjusel ei ole see skeem leidnud laialdast praktilist levikut, kuid mõnel juhul võib seda siiski pidada väga atraktiivseks alternatiiviks praegu maailmas domineerivatele "matemaatilistele" EDS-skeemidele.

Kirjandus

Infotöötlussüsteemid. Krüptograafiline kaitse. Krüptograafiline teisendusalgoritm GOST 28147-89. osariik. Com. NSVL vastavalt standarditele, M., 1989. ftp://ftp.wtc-ural.ru/pub/ru.crypt/GOST-28147
Shannon Claude. Salasüsteemide matemaatiline teooria. Kogumikus "Teoseid teabeteooriast ja küberneetikast", M., IL, 1963, lk. 333-369. http://www.enlight.ru/crypto/articles/shannon/shann__i.htm
Teatab föderaalse teabetöötlusstandardi (FIPS) 197, Advanced Encryption Standard (AES), Federal Register Vol. 66, nr. 235 / Neljapäev, 6. detsember 2001 / Teated, lk 63369–63371. http://csrc.nist.gov/encryption/aes/
Feistel Horst. Krüptograafia ja arvutiturvalisus. A. Vinokurovi tõlge, kirjastus Horst Feistel. Krüptograafia ja arvutite privaatsus, Scientific American, mai 1973, kd. 228, nr. 5, lk. 15-23. http://www.enlight.ru/crypto/articles/feistel/feist_i.htm
Schneier Bruce. Rakenduslik krüptograafia. 2. väljaanne Protokollid, algoritmid ja lähtetekstid C-keeles., M., "Triumph", 2002 http://www.ssl.stu.neva.ru/psw/crypto/appl_rus/appl_cryp.htm
Menezes Alfred, van Oorschot Paul, Vanstone Scott. Rakenduskrüptograafia käsiraamat. http://www.cacr.math.uwaterloo.ca/hac/
Andrei Vinokurov. Kuidas on plokkšifr struktureeritud? Käsikiri. http://www.enlight.ru/crypto/articles/vinokurov/blcyph_i.htm
Andrei Vinokurov. Krüptograafiaga seotud probleemid elektroonilise ajakirja iNFUSED BYTES jaoks veebis. http://www.enlight.ru/crypto/articles/ib/ib.htm
Vinokurov Andrei, Primenko Eduard. Raporti tekst "Vene Föderatsiooni ja USA krüpteerimisstandardite tarkvara juurutamise kohta", informatiseerimise konverents, Moskva, MEPhI, 28.-29.01.2001. Avaldatud konverentsi kogumikus.
Infotehnoloogia. Teabe krüptograafiline kaitse. Räsifunktsioon GOST R34.11-94, Gosstandart RF, M., 1994.

See algoritm on kohustuslik krüpteerimisalgoritmina kasutamiseks Vene Föderatsiooni riiklikes organisatsioonides ja paljudes kaubanduslikes organisatsioonides.

Algoritmi kirjeldus

Algoritmi skeem on näidatud joonisel fig. 3.1. Nagu näete, on selle algoritmi skeem üsna lihtne, mis lihtsustab üheselt selle tarkvara või riistvara rakendamist.

Algoritm GOST 28147-89 krüpteerib teabe 64-bitistes plokkides, mis on jagatud kaheks 32-bitiseks alamplokiks (N1 ja N2). Alamplokki N1 töödeldakse teatud viisil, misjärel lisatakse selle väärtus

alamploki väärtusega N2 (liitmine toimub modulo 2), siis alamplokid vahetatakse. Selline teisendus viiakse läbi teatud arvu voorude jaoks: 16 või 32, olenevalt algoritmi töörežiimist (kirjeldatud allpool). Igas voorus tehakse järgmised toimingud:

1. Klahvi ülekate. /VI alamploki sisu lisatakse võtme Kx osale modulo 2 32.

Algoritmi GOST 28147-89 krüpteerimisvõtme mõõde on 256 bitti ja Kx on selle 32-bitine osa, st 256-bitine krüpteerimisvõti on kujutatud 32-bitiste alamvõtmete konkatenatsioonina (joonis 3.2):

SH ATI, AG2, Yu, AG4, K5, Kb, K7.

Krüpteerimisprotsessi käigus kasutatakse ühte neist alamvõtmetest olenevalt ümmargusest numbrist ja algoritmi töörežiimist.

Riis. 3.1. Algoritmi skeem GOST 28147-

Riis. 3.2. Algoritmi GOST 28147-89 krüpteerimisvõti

2. Tabeli asendamine. Pärast võtme katmist jagatakse /VI alamplokk 8 4-bitiseks osaks, millest igaühe väärtus asendatakse eraldi vastavalt alamploki selle osa asendustabelile. Tabeliasendused (Asenduskast, S-kast) on tänapäevastes krüpteerimisalgoritmides sageli kasutusel, mistõttu tasub neid lähemalt käsitleda.

Tabeliasendust kasutatakse nii: sisendisse suunatakse teatud mõõtmega (antud juhul 4-bitine) andmeplokk, mille numbriline esitus määrab väljundväärtuse arvu. Näiteks on meil järgmise kujuga S-kast:

4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1.

Laske sisendisse tulla 4-bitine plokk “0100”, st väärtus on 4. Tabeli järgi saab väljundi väärtuseks 15, s.o. "1111" (0 asendatakse 4-ga, 1 asendatakse 11-ga, 2 väärtust ei muudeta jne).

Nagu näete, on algoritmi skeem väga lihtne, mis tähendab, et suurim andmete krüpteerimise koormus langeb asendustabelitele. Kahjuks on algoritmil see omadus, et on olemas "nõrgad" asendustabelid, mille abil saab algoritmi krüptoanalüütiliste meetoditega paljastada. Nõrkade hulka kuuluvad näiteks tabel, milles väljund võrdub sisendiga:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15.

3. Bitide kaupa tsükliline nihe vasakule 11 biti võrra.

Algoritmi režiimid

Algoritmil GOST 28147-89 on 4 töörežiimi:

□ lihtne asendusrežiim;

□ gammarežiim;

P mängurežiim tagasisidega;

□ imitatsioonimanuste tootmisviis.

Need režiimid erinevad mõnevõrra üldtunnustatud režiimidest (kirjeldatud jaotises 1.4), mistõttu tasub neid üksikasjalikumalt kaaluda.

Nendel režiimidel on erinevad eesmärgid, kuid need kasutavad sama krüpteeringu teisendust, mida on kirjeldatud eespool.

Lihtne vahetusrežiim

Lihtsa asendusrežiimi korral tehakse ülalkirjeldatud 32 vooru lihtsalt iga 64-bitise teabeploki krüptimiseks. 32-bitiseid alamvõtmeid kasutatakse järgmises järjestuses:

□ KO, Kl, K2, K3, K4, K5, Kb, AG7, KO, ATI jne - voorudes 1-24;

□ K1, Kb, K5, K4, K3, K2, K\, KO - voorudes 25-32.

Dekrüpteerimine lihtsas asendusrežiimis toimub täpselt samamoodi, kuid veidi erineva alamvõtmete kasutamise järjestusega:

□ KO, K\, K2, KZ, K4, K5, Kb, KP - voorudes 1 kuni 8;

□ KP, Kb, K5, K4, K3, K2, K\, KO, K1, Kb jne – voorudes 9-32.

Sarnaselt tavalisele EKP režiimile ei ole plokkide eraldi krüptimise tõttu lihtne asendusrežiim tegelike andmete krüpteerimiseks tungivalt soovitatav; seda tuleks kasutada ainult teiste krüpteerimisvõtmete krüptimiseks mitme võtmega skeemides.

Gamma režiim

Gammarežiimis (joonis 3.3) lisatakse iga lihtteksti plokk bittide kaupa modulo 2 šifri gammaplokile suurusega 64 bitti. Šifreeritud gamma on spetsiaalne jada, mis genereeritakse ülalkirjeldatud teisenduste abil järgmiselt:

1. Registrites N1 ja N2 kirjutatakse nende esialgne täitmine - 64-bitine väärtus, mida nimetatakse "sünkroonimisteateks" (tegelikult on sünkroonimisteade lähtestamisvektori analoog CBC, CFB ja OFB režiimides ).

2. /VI ja N2 registrite sisu (antud juhul sünkroonimissõnumid) krüpteeritakse lihtsa asendusrežiimis.

3. N1 sisu liidetakse modulo (2 32 - 1) konstandiga CI = 2 24 + 2 16 + 2 8 + 4, liitmise tulemus kirjutatakse /VI registrisse.

4. N2 sisu lisatakse moodul 2 konstandiga C2 = 2 24 + 2 16 + 2 8 +1, liitmise tulemus kirjutatakse registrisse N2.

5. /VI ja N2 registrite sisu väljastatakse 64-bitise šifri gammaplokina (st antud juhul moodustavad /VI ja N2 esimese gammaploki).

6. Kui on vaja järgmist gammaplokki (st krüpteerimist või dekrüpteerimist tuleb jätkata), naaske 2. sammu juurde.

Dekrüpteerimiseks genereeritakse samamoodi gamma, seejärel rakendatakse XOR-operatsioon uuesti šifritekstile ja gammabittidele.

Sama gamma šifri genereerimiseks peab krüptogrammi dekrüpteerival kasutajal olema sama võti ja sama sünkroonimissõnumi väärtus, mida kasutati teabe krüptimiseks. Vastasel juhul ei saa te krüpteeritud tekstist originaalteksti kätte.

Enamikus GOST 28147-89 algoritmi rakendustes ei ole sünkroonimissõnum salajane element, kuid sünkroonimissõnum võib olla sama salajane kui krüpteerimisvõti. Sel juhul võime arvestada, et algoritmi võtme efektiivset pikkust (256 bitti) suurendatakse sünkroonimisteate veel 64 biti võrra, mida võib käsitleda täiendava võtmeelemendina.

Tagasiside gamma režiim

Tagasiside gamma režiimis, alates 2. plokist, ei täideta /VI ja L/2 registrid mitte eelmise gammaplokiga, vaid eelmise tavateksti ploki krüpteerimise tulemusega (joonis 3.4). Esimene plokk selles režiimis genereeritakse täpselt samamoodi nagu eelmine.

Riis. 3.4. Šifreeritud gamma genereerimine gammarežiimis koos tagasisidega

Imitaatori genereerimise režiim

Pettus on krüptograafiline kontrollsumma, mis arvutatakse krüpteerimisvõtme abil ja mille eesmärk on kontrollida sõnumite terviklikkust. Selle arvutamiseks on GOST 28147-89 algoritmi spetsiaalne režiim.

Imitatsiooni eesliite genereerimine toimub järgmiselt:

1. Esimene 64-bitine infoplokk, mille jaoks jäljendaja arvutatakse, kirjutatakse registritesse N1 ja N2 ning krüpteeritakse vähendatud lihtasendusrežiimis, milles sooritatakse esimesed 16 ringi 32-st.

2. Saadud tulemus summeeritakse moodul 2 järgmise infoplokiga, salvestades tulemuse N1 ja N2.

3. M ja N2 krüpteeritakse taas lihtasenduse vähendatud režiimis ja nii edasi kuni viimase infoplokini.

Prefiks loetakse registrite N1 ja N2 64-bitiseks tulemuseks või selle osaks. Kõige sagedamini kasutatakse 32-bitist imitatsiooni eesliidet, see tähendab pool registrite sisust. Sellest piisab, sest nagu iga kontrollsumma, on ka imiteeriv eesliide mõeldud eelkõige kaitsma teabe juhusliku moonutamise eest. Andmete tahtliku muutmise eest kaitsmiseks kasutatakse muid krüptograafilisi meetodeid – eelkõige elektroonilist digitaalallkirja (vt punkt 1.1).

Imitatsiooni eesliidet kasutatakse järgmiselt:

1. Mis tahes teabe krüptimisel arvutatakse lihtteksti imitaator ja saadetakse koos šifreeritud tekstiga.

2. Pärast dekodeerimist arvutatakse imitatsiooni eesliide uuesti ja võrreldakse saadetuga.

3. Kui arvutatud ja saadetud imitatsiooniprefiksid ei ühti, moonutati edastamisel šifriteksti või kasutati dekrüpteerimisel valesid võtmeid.

Imiteeriv eesliide on eriti kasulik võtmeteabe õige dekrüpteerimise kontrollimiseks mitme võtmega skeemide kasutamisel.

Eesliide imitatsioon on CBC-režiimis arvutatud MAC-sõnumi autentimiskoodi analoog; erinevus seisneb selles, et prefiksi arvutamisel ei kasutata sünkroonimissõnumit, samas kui MAC-i arvutamisel kasutatakse lähtestamisvektorit.

Algoritmi krüptograafiline tugevus

1994. aastal tõlgiti inglise keelde ja avaldati GOST 28147-89 algoritmi kirjeldus; pärast seda hakkasid ilmnema tema välisekspertide tehtud analüüsi tulemused; siiski ei leitud märkimisväärse aja jooksul ühtegi võimalikule lähenevat rünnakut.

□ suur võtme pikkus - 256 bitti; koos salajase sünkroonimissõnumiga suureneb efektiivne võtme pikkus 320 bitini;

□ 32 teisendusringi; juba 8 vooru järel saavutatakse sisendandmete hajutamise täielik efekt: lihtteksti ploki ühe biti muutmine mõjutab šifreeritud tekstiploki kõiki bitte ja vastupidi, st tekib mitmekordne ohutusvaru.

Mõelge GOST 28147-89 algoritmi krüptoanalüüsi tulemustele.

Asendustabelite analüüs

Kuna asendustabeleid standardis ei ole, viitavad mitmed tööd (näiteks in) sellele, et "pädev organisatsioon" võib väljastada nii "head" kui "halb" asendustabeleid. Kuulus ekspert Bruce Schneier nimetab aga selliseid oletusi "kuulujuttudeks". Selge on see, et algoritmi krüptograafiline tugevus sõltub suuresti kasutatavate asendustabelite omadustest, vastavalt on nõrku asendustabeleid (vt näidet eespool), mille kasutamine võib lihtsustada algoritmi rünnakut. Sellegipoolest tundub erinevate asendustabelite kasutamise võimalus olevat igati väärt idee, mida toetavad kaks järgmist fakti DES-i krüpteerimisstandardi ajaloost (üksikasju vt jaotisest 3.15):

□ DES-algoritmi lineaarset ja diferentsiaalset krüptoanalüüsi kasutavad rünnakud kasutavad asendustabelite spetsiifilisi omadusi; teiste tabelite kasutamisel tuleb krüptoanalüüsi otsast alustada;

□ On tehtud katseid tugevdada DES-i lineaarse ja diferentsiaalse krüptoanalüüsi vastu, kasutades tugevamaid asendustabeleid; selliseid tabeleid, mis on tõepoolest stabiilsemad, on välja pakutud näiteks s 5 DES algoritmis; kuid paraku oli võimatu asendada DES-i s 5 DES-iga, kuna asendustabelid on vastavalt standardis jäigalt määratletud, tõenäoliselt ei toeta algoritmi teostused võimalust tabeleid teisteks muuta.

Paljudes töödes (näiteks , ja ) jõutakse ekslikult järeldusele, et GOST 28147-89 algoritmi salajased asendustabelid võivad olla võtme osaks ja suurendada selle efektiivset pikkust (mis ei ole oluline, kuna algoritmil on väga suur 256-bitine võti). Kuid töö tõestab, et salajased asendustabeleid saab arvutada järgmise rünnaku abil, mida saab praktiliselt rakendada:

1. Seadke nullklahv ja otsige "nullvektorit", st väärtust z = /(0), kus /() on algoritmi ümarfunktsioon. See etapp võtab umbes 2 krüpteerimistoimingut.

2. Nullvektori abil arvutatakse asendustabelite väärtused, mis ei võta rohkem kui 2 11 toimingut.

Algoritmi modifikatsioonid ja nende analüüs

Töös viidi läbi GOST 28147-89 algoritmi modifikatsioonide krüptoanalüüs:

□ GOST-H algoritm, milles võrreldes algse algoritmiga muudetakse alamvõtmete kasutamise järjekorda, nimelt kasutatakse voorudes 25. kuni 32. alamvõtmeid otseses järjekorras, st samamoodi nagu eelmises. algoritmi ringid ;

□ 20-ringiline GOST®-algoritm, mis kasutab võtme ülekatte jaoks XOR-i modulo 2 32 asemel.

Analüüsi tulemuste põhjal jõuti järeldusele, et GOST-H ja GOST© on nõrgemad kui algne GOST 28147-89 algoritm, kuna mõlemal on nõrkade võtmete klassid. Väärib märkimist, et GOST© krüptoanalüüsi osas kordab teos sõna-sõnalt GOST 28147-89 algoritmi krüptoanalüüsi osa, mis avaldati 2000. aastal ühes tuntud teoses (ilma igasuguse viiteta originaalile). See seab kahtluse alla töö autorite professionaalsuse ja selle muud tulemused.

Töös on välja pakutud väga huvitav algoritmi modifikatsioon: tabelid S \ ... Ss peavad tingimata olema erinevad; algoritmi igas voorus peavad need olema teatud seaduse järgi permuteeritud. See permutatsioon võib sõltuda krüpteerimisvõtmest või olla salajane (st olla osa suuremast krüpteerimisvõtmest kui algne 256-bitine võti). Mõlemad variandid suurendavad nende autorite sõnul oluliselt algoritmi vastupidavust lineaarsele ja diferentsiaalsele krüptoanalüüsile.

Ja töös on antud veel üks asendustabelitega seotud modifikatsioon, milles analüüsitakse üht võimalikku meetodit asendustabelite arvutamiseks krüpteerimisvõtme alusel. Töö autorid jõudsid järeldusele, et selline sõltuvus nõrgendab algoritmi, kuna see toob kaasa nõrkade võtmete olemasolu ja mõned algoritmi potentsiaalsed haavatavused.

Algoritmi täisringanalüüs

Rünnakud on ka täieliku GOST 28147-89 vastu ilma muudatusteta. Üks esimesi avatud töid, mille käigus viidi läbi algoritmi analüüs, tuntud töö, on pühendatud rünnakutele, mis kasutavad ära mitmete tuntud krüpteerimisalgoritmide võtme laiendamise protseduuri nõrkusi. Eelkõige saab täisringi algoritmi GOST 28147-89 murda lingitud võtmete diferentsiaalkrüptoanalüüsi abil, kuid ainult siis, kui kasutatakse nõrku asendustabeleid. Algoritmi 24-ringiline versioon (millest puuduvad esimesed 8 vooru) avatakse samamoodi mis tahes asendustabelite jaoks, kuid tugevad asendustabelid (näiteks toodud aastal) muudavad sellise rünnaku absoluutselt ebapraktiliseks.

Koduteadlased A. G. Rostovtsev ja E. B. Makhovenko pakkusid 2001. aastal välja põhimõtteliselt uudse krüptoanalüüsi meetodi (autorite sõnul on see oluliselt tõhusam kui lineaarne ja diferentsiaalne krüptoanalüüs), moodustades sellele šifritekstile ja soovitud väärtusele vastavast teadaolevast lihttekstist objektiivse funktsiooni. võtme tegelikule väärtusele vastava ekstreemumi leidmine. Samuti leidsid nad suure klassi algoritmi GOST 28147-89 nõrku võtmeid, mis võimaldavad avada algoritmi, kasutades ainult 4 valitud lihtteksti ja neile vastavaid üsna madala keerukusega šifritekste. Töös jätkatakse algoritmi krüptoanalüüsiga.

2004. aastal pakkus rühm Korea eksperte välja ründe, mille abil on seotud võtmete diferentsiaalkrüptoanalüüsi abil võimalik saada 91,7% tõenäosusega 12 bitti salajast võtit. Rünnak nõuab 235 valitud lihtteksti ja 236 krüpteerimistoimingut. Nagu näete, on see rünnak algoritmi tegelikuks avamiseks praktiliselt kasutu.