Krüptimisalgoritm GOST 28147-89. Lihtne asendusmeetod. - Arhiiv WASM.RU

„Elu ajal ärge surege, vaadake seda maailma.
Paljudel siinsetel inimestel on surnud hing - nad on seest surnud.
Kuid nad kõnnivad ja naeravad, teadmata, et nad seda pole,
Ärge kiirustage oma surmatunniga, "ütles ta mulle.

Aaria, "Kõrgel seal"

2.1 Feisteli võrgud.
2.2 Blokeeri šifr GOST 28147-89

3.1 Põhiteave
3.2 Krüptotransformatsiooni peamine samm

3.3 Põhilised tsüklid:“ 32-Z” , “ 32-R” .

4.1 Krüptotransformatsiooni põhietapi rakendamine
4.2 Algoritmi kiiruse suurendamine
5. Põhiteabe nõuded
6. Kasutatud kirjanduse loetelu
7. Tänuavaldused.

Sissejuhatus.

See dokument on minu katse kirjeldada meetodit GOST 28147-89 krüptimisalgoritmi asendamiseks lihtsaima, kuid sellegipoolest tehniliselt pädeva keelega. Pärast esimese kuue punkti lugemist annab lugeja oma arvamuse selle kohta, kuidas ma seda tegin.

Selleks, et minu tööst oleks rohkem kasu, soovitan teil varustada end kasutatud kirjanduse loendis märgitud autorite töödega. Samuti on soovitatav, et kalkulaatoril oleks toimingu arvutamiseks funktsioon. XOR aastast Artiklit lugedes eeldatakse, et lugeja kavatses seda krüpteerimisalgoritmi uurida. Kuigi see sobib ka viitamiseks, kirjutasin selle artikli just koolitusena.

Eelteave plokkšifrite kohta.

Enne kui hakkame vaatama algoritmi, peame tutvuma seda tüüpi šifrite loomise ajalooga. Algoritm kuulub plokkšifrite kategooriasse, mille arhitektuuris on teave jagatud piiratud arvuks plokkideks, lõplik ei pruugi loomulikult täielik olla. Krüpteerimisprotsess toimub täielikes plokkides, mis moodustavad šifri. Viimast plokki, kui see on puudulik, täiendatakse millegagi (selle täitmise nüansside kohta ütlen allpool) ja see krüpteeritakse samamoodi nagu täisplokid. Šifri all pean ma silmas krüpteerimisfunktsiooni tulemust, mis toimib teatud andmehulgale, mille kasutaja krüptimiseks esitas. Teisisõnu, šifr on krüptimise lõpptulemus.

Plokkšifrite väljatöötamise ajalugu on seotud 70ndate algusega, mil IBM, mõistes vajadust kaitsta teavet arvuti edastamiskanalite kaudu andmete edastamisel, alustas oma uurimisprogrammi, mis on pühendatud teabe kaitsmisele elektroonilistes võrkudes, sealhulgas krüptograafia.

Rühma teadlasi - arendajaid IBMist, kes hakkasid uurima sümmeetrilise võtme kasutamise skeemiga krüpteerimissüsteeme, juhtis dr. Horst Feistel.

2.1 Feisteli võrgud

Feisteli pakutud uue krüpteerimismeetodi arhitektuur klassikalises kirjanduses kannab nime "The Feistel Architecture", kuid hetkel kasutatakse vene ja väliskirjanduses rohkem väljakujunenud terminit - "Feisteli võrk" ehk Feisteli võrk. Seejärel ehitati sellele arhitektuurile šifr "Lucifer" - mis hiljem avaldati ja tekitas uue huvi laine krüptograafia vastu üldiselt.

"Feisteli võrgu" arhitektuuri idee on järgmine: teabe sisendvoog on jagatud n -bitisteks plokkideks, kus n on paarisarv. Iga plokk on jagatud kaheks osaks-L ja R, seejärel sisestatakse need osad iteratiivsesse plokkšifrisse, milles j-nda etapi tulemus määratakse eelmise etapi j-1 tulemuse järgi! Seda saab illustreerida näitega:

Riis. 1

Kus funktsioon A on plokkšifri põhitegevus. See võib olla lihtne toiming, näiteks XOR -toiming, või võib sellel olla keerukam vorm lihtsate toimingute jada - mooduli lisamine, vasakpoolne nihutamine, elementide asendamine jne - koos, need lihtsad toimingud moodustavad nn - krüptotransformatsiooni peamine samm.

Tuleb märkida, et funktsiooni toimimise põhielemendid on võtmeelementide pakkumine ja XOR -toiming ning sellest, kui hästi on nende toimingute töö läbi mõeldud, räägib see šifri kui terviku krüptograafilisest tugevusest.

Selleks, et Feisteli võrkude idee oleks lõpuks selge, kaaluge lihtsamat juhtumit, mis on näidatud riis. 1, kus funktsioonis A - toiminguid “mod 2” (“xor”), kuid see kõige lihtsam juhtum, tõsisemas olukorras, näiteks riikliku tähtsusega teabe varjamine, võib funktsioon A olla keerulisem (minu arvates on funktsioon A tõesti väga keeruline):

Esialgsed andmed:

L = 1110b, R = 0101, K = 1111b

Hankige šifr

1. (R + K) mod 2 4 = Smod, Smod = 0100b

2. (Smod + L) mod 2 = Sxor, Sxor = 1010b

3. L = R, R = Sxor

L = 0101b, R = 1010b

Selgitame oma tegevust:

1. See toiming on lisamoodul 2 4. Praktikas taandatakse selline toiming lihtsaks liitmiseks, kus peame lisama kaks numbrit ja ignoreerima ülekandmist 5. numbrile. Kuna kui paneme eksponendid arvu binaarse esituse numbrite kohale, on viienda numbri kohal eksponent neli, siis vaatame allolevat joonist, mis näitab meie toiminguid:

Riis. 2

Siin osutasin noolega eksponentidele, nagu näete, oleks tulemus pidanud olema 10100, kuid kuna mod 2 4 toimingu ajal eiratakse ülekannet, saame 0100.

2. Seda toimingut kirjanduses nimetatakse mod 2, koostamiskeeles rakendab seda käsk XOR... Kuid selle õigem nimi on mod 2 1. Ilma selle ainulaadse toiminguta on vaevalt võimalik luua kiiret ja hõlpsasti rakendatavat krüpteerimisalgoritmi ja samal ajal nii, et see oleks endiselt üsna krüptograafiliselt tugev. Selle toimingu ainulaadsus seisneb selles, et see ise on vastupidine! Näiteks kui number A on XORitud numbriga B, saame selle tulemusel B, tulevikus piisab, kui arvud B ja C üksteise vahel uuesti XOR -i saada, et saada varasem väärtus A!

Selle toimingu käigus saime 1010 numbritega 1110 ja 0100, 1110 tagasisaamiseks piisab numbrite 0100 ja 1010 ületamisest! Selle toimingu kohta leiate lisateavet saidile lisatud artiklist. www.wasm.ru, « Elementaarne juhendCRC_ vigade tuvastamise algoritmid»Autor, kes Ross N. Williams... Sellel tööl on mõte - " 5. Kahendaritmeetika ilma sidekriipsuta". Selles artiklis kirjeldatakse toimingut. xor! Ma hüüan, sest selles artiklis on see toiming nii planeeritud, et lugeja mitte ainult ei mõista, kuidas see toiming töötab, vaid isegi alustab seda. näha, kuulda ja tunda!

3. See toiming on vajalik selleks, et dekrüpteerimise ajal saaks krüpteerimisest algväärtusi.

2.2 Plokkšifr GOST 28147-89

Krüpteerimisalgoritm GOST 28147 - 89 kuulub plokkšifrite kategooriasse, mis töötab tasakaalustatud Feisteli võrkude arhitektuuri järgi, kus valitud infobloki kaks osa on võrdse suurusega. Algoritm töötati välja KGB kaheksanda osakonna sügavustes, nüüd muudeti see FAPSI -ks ja see kinnitati NSV Liidu ajal 1989. aastal Vene Föderatsiooni krüptimisstandardina.

Selle algoritmi meetodi toimimiseks on vaja jagada teave 64 -bitisteks plokkideks. Looge või sisestage krüpteerimissüsteemi järgmine põhiteave: võti ja asendustabel. Krüpteerimise võtme- ja asendustabeli valikut tuleks võtta väga tõsiselt, sest see on teie teabe turvalisuse alus. Teavet selle kohta, millised nõuded võtmele esitatakse, ja asenduste tabelit leiate punktist "Nõuded põhiteabele".

Meetodi kaalumisel ei keskendu me sellele, sest see artikkel, nagu ma eespool ütlesin, on kirjutatud eesmärgiga õpetada lugejat andmete krüptimiseks selle krüpteerimisalgoritmi lihtsa asendamise meetodil, kuid kindlasti puudutame seda küsimust artikli lõpus.

Teoreetiline miinimum.

3.1 Põhiteave

Nagu ma eespool ütlesin, on andmete krüptimisega aktiivselt seotud järgmised:

3.1.1. Võti on kaheksa elemendi jada, igaüks 32 bitti. Järgnevalt tähistame sümboliga K ja elemendid, millest see koosneb, on k1, k2, k3, k4, k5, k6, k7, k8.

3.1.2 Asendustabel - kaheksa rea ​​ja kuueteistkümne veeru maatriks, edaspidi - Hij. Iga rea ​​i ja veeru ristumiskohas olev element võtab 4 bitti.

3.2 Krüptotransformatsiooni põhietapp

Krüpteerimisprotsessi peamine samm on - krüptotransformatsiooni peamine samm. See pole midagi muud kui toiming andmete krüptimiseks vastavalt teatud algoritmile, ainult arendajad on nimetuse liiga tülikaks toonud.

Enne krüptimise alustamist jagatakse plokk kaheks osaks L ja R, kumbki 32 bitti. Valitakse võtmeelement ja alles siis sisestatakse need kaks ploki osa, võtmeelement, asendustabel, põhietapi funktsiooni, põhietapi tulemus on üks baastsükli iteratsioon, mida arutatakse peatükis järgmine lõik. Peamine samm koosneb järgmistest:

1. Ploki R liitmisosa summeeritakse võtmeelemendiga K mod 2 32. Ma kirjeldasin sarnast toimingut ülalpool, siin on sama asi ainult astendaja mitte "4", vaid "32" - selle operatsiooni tulemust tähistatakse tulevikus Smodiga.
2. Jagage eelnevalt saadud tulemus Smod neljabitisteks elementideks s7, s6, s5, s4, s3, s2, s1, s0 ja sisestage see asendusfunktsioonile. Asendamine on järgmine: element Smod - si on valitud, alustame algusest madalaima elemendiga ja asendame asenduste tabeli väärtusega i - rida ja veerg, millele osutab elemendi s väärtus i. Me läheme elemendile s i +1 ja jätkame samamoodi ning jätkame nii, kuni muudame viimase elemendi Smod väärtust - selle toimingu tulemust tähistatakse kui Ssimple.
3. Selles toimingus nihutame Ssimple'i väärtust tsükliliselt 11 bitti vasakule ja saame Srol.
4. Valime L -ploki teise osa ja lisame selle Sroliga mod 2, mille tulemuseks on Sxor.
5. Selles etapis muutub L -ploki osa võrdseks R -osa väärtusega ja R -osa omakorda initsialiseeritakse Sxori tulemusega ja sel juhul on põhisammu funktsioon täidetud!

3.3 Põhitsüklid: "32-З", "32-Р".

Teabe krüpteerimiseks on vaja see jagada 64 -bitisteks plokkideks, muidugi võib viimane plokk olla väiksem kui 64 bitti. See asjaolu on selle "lihtsa asendamise" meetodi Achilleuse kand. Kuna selle lisamine 64 bitile on väga oluline ülesanne šifriprogrammi krüptograafilise tugevuse suurendamiseks ja sellesse tundlikku kohta, kui see on infomassis olemas, kuid seda ei pruugi olemas olla (näiteks 512 baiti sisaldav fail! ), Tuleb suhtuda suure vastutusega!

Kui olete teabe plokkideks jaganud, jagage võti elementideks:

K = k1, k2, k3, k4, k5, k6, k7, k8

Krüptimine ise seisneb nn põhitsüklite kasutamises. Mis omakorda sisaldab krüptotransformatsiooni põhisammude n-ndat arvu.

Põhitsüklid on märgistatud, kuidas seda panna: n - m. Kus n on krüptotransformatsiooni põhisammude arv baastsüklis ja m on baastsükli "tüüp", s.t. mis see on, kas "Z" või andmete "R" krüptimine.

Põhiline krüptimistsükkel 32-З koosneb 32 krüptotransformatsiooni põhietapist. Plokk N ja võtme K element sisestatakse funktsiooni, mis rakendab sammu toiminguid, ja esimene samm toimub k1 -ga, teine ​​elemendiga k2 saadud tulemuse üle jne. vastavalt järgmisele skeemile:

k1, k2, k3, k4, k5, k6, k7, k8, k1, k2, k3, k4, k5, k6, k7, k8, k1, k2, k3, k4, k5, k6, k7, k8k8, k7, k6, k5, k4, k3, k2, k1

32-P dekrüpteerimisprotsess toimub sarnaselt, kuid põhielemendid on esitatud vastupidises järjekorras:

k1, k2, k3, k4, k5, k6, k7, k8, k8, k7, k6, k5, k4, k3, k2, k1, k8, k7, k6, k5, k4, k3, k2, k1, k8, k7, k6, k5, k4, k3, k2, k1

Harjuta.

4.1 Krüptotransformatsiooni põhietapi rakendamine

Kui olime tutvunud teabe krüptimise teooriaga, oli aeg näha, kuidas krüptimine praktikas toimub.

Esialgsed andmed:

Võtke infoblokk N = 0102030405060708h, siin on osad L ja R võrdsed:

L = 01020304h, R = 05060708h, võtame võtme:

K = ' nagu 28 zw37 q839 7342ui23 8e2t wqm2 ewp1 '(need on ASCII -koodid, kuueteistkümnendes esituse vaatamiseks saate selle faili Total Commanderis kuvamisrežiimis avada, vajutades klahvi F3"Ja siis võti" 3 "). Selles võtmes on elementide väärtused järgmised:

k1 = 'as28', k2 = 'zw37', k3 = 'q839', k4 = '7342'

k5 = 'ui23', k6 = '8e2t', k7 = 'wqm2', k8 = 'ewp1'

Võtke ka järgmine asendustabel:

Riis. 3

Siin on read nummerdatud 0 kuni 7, veerud 0 kuni F.

Hoiatus: Algoritmi kaalumisel on eeskujuks kogu teave, sealhulgas võti koos asendustabeliga!

Kasutades "lähteandmeid", on vaja saada krüptotransformatsiooni põhietapi toimingu tulemus.

1. Valige osa R = 05060708h ja võtmeelement k1 = 'as28', kuueteistkümnendsüsteemis näeb võtmeelement välja selline: 61733238h. Nüüd teeme summeerimistoimingu mod 2 32:

Riis. 4

Nagu jooniselt näha, ei olnud meil ülekannet 33 bitiga punasega ja eksponendiga “ 32 ". Ja kui meil oleks R ja võtmeelemendi muud väärtused, oleks see võinud juhtuda ja siis oleksime seda ignoreerinud ning kasutanud edasi ainult kollasega märgitud bitte.

Teen selle toimingu käsuga assembler lisama:

; eax = R, ebx = 'as28'

Selle operatsiooni tulemus Smod = 66793940h

2. Nüüd kõige keerulisem operatsioon, aga kui seda tähelepanelikult vaadata, pole see enam nii hirmutav, kui esmapilgul tundub. Kujutleme Smodi järgmiselt:

Riis. 5

Proovisin joonisel Smodi elemente visualiseerida, kuid selgitan siiski:

s0 = 0, s1 = 4, s2 = 9 jne.

Alustades madalaimast elemendist s0, teeme asendamise. Meenutades lõiku " 3.2 Krüptotransformatsiooni põhietapp»I - rida, s i - veerg, otsige väärtust nullreast ja nullveerust:

Joonis 6

Seega pole Smodi praegune väärtus 6679394 0 h ja 6679394 5 h.

Jätkame s1 asendamist, st. neli. Kasutades esimest rida ja neljandat veergu (s1 = 4!). Vaatame pilti:

Riis. 7

Nüüd juba Smodi väärtus, mitte 667939 4 5h, 667939 2 5h. Eeldan, et nüüd on asendusalgoritm lugejale selge ja võin öelda, et pärast Ssimple'i lõpptulemust on järgmine väärtus - 11e10325h.

Sellest, kuidas seda on kõige lihtsam rakendada, kogujate käskude kujul, räägin järgmises lõigus, pärast laiendatud tabelist rääkimist.

1. Peame saadud Ssimple'i väärtuse 11 bitti nihutama vasakule.

Riis. kaheksa

Nagu näete, on see toiming üsna lihtne ja seda rakendab montaažikeele üks käsk - roll ja selle Srol -operatsiooni tulemus on 0819288Fh.

4. Nüüd tuleb meie teabepaketi L osa XOR -iga määrata Srol -väärtusega. Võtan w2k sp4 -st kalkulaatori ja saan Sxor = 091b2b8bh.

5. See toiming on lõplik ja me lihtsalt määrame, puhastame R osa L väärtuse ja lähtestame L osa Sxori väärtusega.

Lõpptulemus:

L = 091b2b8bh, R = 01020304h

4.2 Algoritmi kiiruse suurendamine

Nüüd räägime algoritmi optimeerimisest kiiruse jaoks. Projekti elluviimisel tuleb arvestada, et programm, mis töötab registritega sagedamini kui mäluga, töötab kõige kiiremini ja siin on ka see otsus väga oluline, kuna üle ühe teabeploki koguni 32 krüptimistoimingut!

Kui rakendasin oma programmis krüptimisalgoritmi, tegin järgmist.

1. Valitud osa plokist L eax -registrisse ja R edx -i.

2. Esiregistris, mis on initsialiseeritud laiendatud võtme aadressiga, lähemalt allpool.

3. Registris ebx määras laiendatud asendustabeli aadressi väärtuse, sellest lähemalt allpool

4. Edastas punktide 1, 2, 3 teabe olenevalt olukorrast põhitsükli 32 - З või 32 - Р funktsioonile.

Kui vaatate lõigu põhielementide vooskeemi " Põhitsüklid: "32-З", "32-Р"", Siis saab meie põhitsükli 32 - 3 võtit kujutada järgmiselt:

K 32-Z =

„As28”, „zw37”, „q839”, „7342”, „ui23”, „8e2t”, „wqm2”, „ewp1”,

„As28”, „zw37”, „q839”, „7342”, „ui23”, „8e2t”, „wqm2”, „ewp1”,

„Ewp1”, „wqm2”, „8e2t”, „ui23”, „7342”, „q839”, „zw37”, „as28”

Need. algusest peale on k1, k2, k3, k4, k5, k6, k7, k8 - ‘ nagu 28 ','zw37 ','q839 ',' 7342 ','ui23 ',' 8e2t ','wqm2 ','ewp1 ' seda järjestust korratakse kolm korda. Seejärel lähevad elemendid vastupidises järjekorras, st: k8, k7, k6, k5, k4, k3, k2, k1 - „Ewp1”, „wqm2”, „8e2t”, „ui23”, „7342”, „q839”, „zw37”, „as28”.

Paigutasin massiivi elemendid ette sellises järjekorras, nagu neid tuleks sisestada 32 - Z. Seega suurendasin võtmed kätte põhimõttel nõutavat mälu, kuid päästsin end mõnest mõtlemisprotsessist, mida ma ei vajanud, ja suurendasin kiirust algoritmi, vähendades mälule juurdepääsu aega! Siin kirjeldasin ainult klahvi 32 - З, tsükli 32 jaoks - Р tegin sama, kuid kasutades erinevat elementide varustamise skeemi, mida kirjeldasin ka lõigus " Põhitsüklid: “32-Z”, “32-P».

Nüüd on aeg kirjeldada asendusfunktsiooni rakendamist, nagu ma eespool lubasin. Ma ei osanud varem kirjeldada, sest see eeldab uue mõiste - laiendatud asendustabeli - kasutuselevõttu. Ma ei saa teile selgitada, mis see on. Selle asemel näitan teile seda ja teie ise sõnastate, mis see on - asenduste laiendatud tabel?

Niisiis, selleks, et mõista, mis on laiendatud asendustabel, vajame näiteks asendustabelit, võtan joonisel fig. 3.

Näiteks oli meil vaja asendada number 66793940h. Esitan selle järgmiselt:

Riis. üheksa

Kui nüüd võtta elemendid s1, s0, s.t. kõige vähem oluline bait, asendusfunktsiooni tulemus on 25 tundi! Pärast Andrei Vinokurovi artikli lugemist, mida ma lõigus tsiteerisin " Kasutatud kirjanduse loetelu", Tegelikult leiate, et kui valite kaks rida, saate massiivi, mis võimaldab teil kiiresti leida asenduselemente, kasutades käsku assembler xlat. Nad ütlevad, et seda saab teha muul viisil kiiremini, kuid Andrei Vinokurov uuris umbes neli aastat GOST -i rakendamise kiireid algoritme! Ma ei arva, et peaksite ratast uuesti leiutama, kui teil see juba on.

Niisiis, massiivi kohta:

Võtame kaks esimest rida nulli ja esimese, loome 256 baiti massiivi. Nüüd täheldame ühte eripära, et kui on vaja muuta 00h, siis on tulemuseks 75h (joonise 3 alusel) - paneme selle väärtuse massiivi nihkega 00h. Võtame väärtuse 01h, asendusfunktsiooni 79h tulemuse, paneme selle massiivi nihkega 01 ja nii edasi kuni 0FFh, mis annab meile 0FCh, mille paneme massiivi nihkega 0FFh. Nii saime laiendatud asendustabeli esimese rea ridade jaoks: esimene ja null. Aga ikkagi on kolm rühma: teine ​​lehekülg 2, leht 3, kolmas leht 4, lehekülg 5, neljas leht 6, lehekülg 7. Nende kolme rühmaga tegeleme samamoodi nagu esimesega. Tulemuseks on laiendatud asendustabel!

Nüüd saame rakendada algoritmi, mis teostab asendamise. Selleks võtame lähtekoodid, mille Andrei Vinokurov oma lehele postitas, vt " Bibliograafia».

lea ebx, laiendatud_tabeli_lihtne

mov eax, [pane asendatav number]

lisage ebx, 100h; hüpata järgmise kahe sõlme juurde

sub ebx, 300h; nii et tulevikus osutab ebx lauale

Nüüd veel üks funktsioon, eelmiste toimingutega me mitte ainult ei asendanud, vaid ka nihutasime numbrit 8 bitti vasakule! Peame lihtsalt veel 3 bitti vasakule nihutama:

ja saame operatsiooni tulemuse rol eax, 11!

Ma ei saa optimeerimise kohta rohkem midagi lisada, ainus, mida saan rõhutada, on see, mida ma eespool ütlesin - kasutage registreid sagedamini kui juurdepääsu mälule. Ma arvan, et need sõnad on mõeldud ainult algajatele, kogenud ja ilma minu sõnadeta saavad sellest suurepäraselt aru.

Nõuded põhiteabele.

Nagu Andrei Vinokurovi artiklis öeldud, valitakse võti kahe kriteeriumi järgi:

Bittide võrdse jaotuse kriteerium väärtuste 1 ja 0. Tavaliselt on bittide võrdse jaotuse kriteerium Pearsoni kriteerium ("chi-square").

See tähendab põhimõtteliselt võtit, mida saab iga number. See tähendab, et võtme järgmise biti moodustamisel on selle initsialiseerimise tõenäosus ühe või nulliga 50/50!

Pange tähele, et võti koosneb kaheksast elemendist, millest igaüks on 32 bitti, seega on võtmes ainult 32 * 8 = 256 bitti ja võimalike võtmete arv on 2 256! Kas see teile ei löö?

Seeria kriteerium.

Kui me vaatame oma võtit, mille ma lõigus andsin " 4.1 Krüptotransformatsiooni põhietapi rakendamine», Siis märkate, et kehtib järgmine märge:

Riis. kümme

Ühes fraasis ei tohiks k 1 väärtust korrata mitte k 2, mitte üheski teises võtme elemendis.

See tähendab, et võti, mille oleme valinud krüptimisalgoritmi kaalumiseks, vastab täielikult kahele ülaltoodud kriteeriumile.

Nüüd aga asenduste tabeli valiku kohta:

Nüüd räägime sellest, kuidas valida õige asendustabel. Asendustabelite valiku põhinõue on elementide „mittekorratavuse” nähtus, millest igaüks on 4-bitine. Nagu ülal nägite, koosneb iga asendustabeli rida väärtustest 0h, 1h, 2h, 3h,…, 0fh. Seega on peamine nõue, et iga rida sisaldab väärtusi 0h, 1h, 2h, ..., 0fh ja iga selline väärtus ühes eksemplaris. Näiteks jada:

1 2 3 4 5 6 7 8 9 A B C D E F

See vastab täielikult sellele nõudele, kuid siiski! Sellist jada pole soovitatav valida stringina. Kuna kui sisestate väärtuse funktsiooni sisendile, mis tugineb sellisele stringile, saate väljundis sama väärtuse! Ei usu mind? Seejärel võtke asendustabelina number 332DA43Fh ja kaheksa sellist rida. Tehke asendustoiming ja ma kinnitan teile, et väljund on number 332DA43Fh! See tähendab, et sama, mille esitasite operatsiooni sisendile! Ja see pole märk heast vormist krüpteerimisel ja kas oli?

See oli üks nõue, järgmine kriteerium ütleb, et - iga väljundploki bitt peab olema statistiliselt sõltumatu sisendploki igast bitist!

Kuidas see lihtsam välja näeb? Ja siin on näiteks see, kuidas oleme ülaltoodud arvu hulgast valinud elemendi s0 = 0Fh, 01111b. Tõenäosus, et asendame nüüd esimese biti ühe või nulliga, on 0,5! Iga bitti teise, kolmanda ja neljanda bitti asendamise tõenäosus, mida me eraldi kaalume, ühe või nulliga, on samuti 0, 5. Valides s1 = 0Eh, on tõenäosus, et oleme nullbitt, ja see on "0" , asendatakse nulliga või üks on võrdne - 0,5! Seega selle kriteeriumi järgi puudub korrapärasus elementide s0, s1 nullbittide asendamise vahel! Jah, võite asendada need, kuid võite asendada ka nullid.

Tabeli hindamiseks selle kriteeriumi järgi saate koostada tabeli korrelatsioonikoefitsientidest, mis arvutatakse järgmise valemi abil:

Kui p = 1, siis on bitti j väärtus väljundis võrdne bitti i väärtusega sisendis mis tahes bitikombinatsioonide korral sisendis;

Kui p = -1, siis biti j väärtus väljundis on alati sisendbiti i pöördväärtus;

Kui p = 0, võtab väljundbitt j võrdse tõenäosusega väärtused 0 ja 1 sisendbiti i mis tahes fikseeritud väärtuse jaoks.

Võtame ühe rea näite:

Jagame selle "komponentideks":

Arvutame ühe koefitsiendi vastavalt ülaltoodud valemile. Et seda oleks lihtsam mõista, selgitan seda üksikasjalikumalt:

Võtame sisendil 0 -nda (0) 0 -bitti ja väljundis (1) 0 -nda numbri 0 -nda bitti, teeme operatsiooni 0 XOR 1 = 1.

Võtame sisendist 1. numbri (1) 0 -bitti ja väljundis (1) 1 -nda numbri 0 -bitti, teeme operatsiooni 1 XOR 1 = 0.

Võtame sisendisse 2. numbri (0) 0 -bitti ja väljundis (0) teise numbri 0 -bitti, teostame toimingu 0 XOR 0 = 0.

Võtame sisendisse kolmanda numbri (1) 0 -bitti ja väljundis (1) kolmanda numbri 0 -nda bitti, teeme operatsiooni 1 XOR 1 = 0.

Sellises järjestuses järjestikuste XOR-toimingute tegemisel loendame kõigi nulliväliste väärtuste arvu, saame väärtuse 6. Seega P 00 = 1- (6/2 4-1) = 0,25. Niisiis, selgus, et bitti 0 väärtus väljundis on võrdne bitti 0 väärtusega sisendis 4 juhul 16 -st;

Lõplik koefitsientide tabel:

Nagu korrelatsioonikoefitsientide tabelist näha, on sisendil olev bitt 3 inverteeritud väljundi biti 0 suhtes 14 juhul 16 -st, mis on 87,5%. Tavaliste krüpteerimissüsteemide puhul pole see enam vastuvõetav. Võtame vahelduseks veel ühe näite:

Koefitsientide tabel on järgmine (kellele pole laisk ümber arvutada)

Selles tabelis on asjad veelgi hullemad - grupi bitid 1 ja 2 jäävad muutumatuks! Cryptanalystil on, kuhu pöörduda. Võttes arvesse kõiki neid nõudeid, leiti näidatud teooriale vastavad permutatsioonitabelid (täna - 1276 kombinatsiooni) lihtsa otsingu ("peaga") abil. Siin on mõned neist:

09 0D 03 0E-06 02 05 08-0A 07 00 04-0C 01 0F 0B

00 05 0A 07-03 08 0F 0C-0E 0B 04 09-0D 06 01 02

06 0B 0F 00-0C 01 02 0D-08 07 09 04-05 0A 03 0E

04 0E 00 09-0B 01 0F 06-03 0D 07 0A-0C 02 08 05

04 02 08 0E-05 0F 03 09-0B 01 0D 07-0A 0C 06 00

07 03 09 0C-08 00 06 0F-0E 04 01 0A-0D 0B 02 05

06 0F 03 08-0D 04 0A 01-09 02 05 0C-00 0B 0E 07

0C 06 08 01-03 09 07 0E-0B 05 0F 02-04 0A 00 0D

04 0B 09 06-0E 01 00 0F-0A 05 03 0C-0D 02 07 08

00 0E 0F 01-07 08 09 06-04 0B 0A 05-03 0D 0C 02

0F 09 01 07-04 0A 08 06-0E 00 02 0C-05 03 0B 0D

0A 03 04 01-05 0C 0B 0E-08 06 0F 0D-07 09 00 02

0B 06 0F 01-04 0A 08 05-00 0D 0C 02-07 09 03 0E

0C 03 02 08-0D 06 0B 05-07 09 04 0F-0A 00 01 0E

02 0B 0F 04-09 00 06 0D-05 0E 01 08-0C 07 0A 03

Kasutatud kirjanduse loetelu.

1. Andrei Vinokurovi artikkel:

Krüpteerimisalgoritm GOST 28147-89, selle kasutamine ja rakendamine

Intel x86 platvormi arvutite jaoks.

Samuti on olemas krüpteerimisalgoritmi rakendamise lähtekoodid.

1. Horst Feisteli artikkel:

Krüptograafia ja arvuti turvalisus.

(leiad eelmise artikliga samal aadressil)

1. Ross N. Williams:

Elementaarne juhend CRC vigade tuvastamise algoritmide kohta

Postitatud saidile www.wasm.ru.

Tänuavaldused.

Soovin avaldada tänu kõigile foorumi www.wasm.ru külastajatele. Kuid ma tahaksin eriti tänada ChS -i, kes on praegu tuntud kui SteelRat, ta aitas mul mõista asju, millest ma ilmselt poleks kunagi aru saanud, samuti abi lõigu kirjutamisel: „ Põhiteabe nõuded”, Selle lõigu põhiosa on kirjutanud tema. Samuti olen sügavalt tänulik KSTU töötajale A.N. Tupolev Anikin Igor Vjatšeslavovitš ja patt oleks jätta mainimata Chris Kaspersky selle eest, et ta on, ja Volodya / wasm.ru tema juhiste eest. Oh, ja ma saan seda temalt. Tahan märkida ka Sega-Zero / Callipso, kuid see tõi mulle meelde mõne matemaatilise džungli.

See on võib -olla kõik, mida ma tahaksin teile öelda.

Oleksin tänulik selle artikliga seotud kriitika või küsimuste või lihtsalt nõuannete eest. Minu kontaktandmed: [e -post kaitstud], ICQ - 337310594.

Parimate soovidega, kurja katkestus.

P.S .: Selle artikliga ei püüdnud ma kedagi edestada. See oli kirjutatud kavatsusega, et hõlbustada GOSTi uurimist ja kui teil on raskusi, ei tähenda see, et olen selles süüdi. Ole mõistlik ja kannatlik, kõike head sulle!

„Elu ajal ärge surege, vaadake seda maailma.
Paljudel siinsetel inimestel on surnud hing - nad on seest surnud.
Kuid nad kõnnivad ja naeravad, teadmata, et nad seda pole,
Ärge kiirustage oma surmatunniga, "ütles ta mulle.

Aaria, "Kõrgel seal"

1. Sissejuhatus

1. Eelteave plokkšifrite kohta

2.1 Feisteli võrgud.
2.2 Blokeeri šifr GOST 28147-89

1. Teoreetiline miinimum

3.1 Põhiteave
3.2 Krüptotransformatsiooni peamine samm

3.3 Põhilised tsüklid:“ 32-Z” , “ 32-R” .

1. Harjuta

4.1 Krüptotransformatsiooni põhietapi rakendamine
4.2 Algoritmi kiiruse suurendamine
5.
6. Kasutatud kirjanduse loetelu
7. Tänuavaldused.

Sissejuhatus.

See dokument on minu katse kirjeldada meetodit GOST 28147-89 krüptimisalgoritmi asendamiseks lihtsaima, kuid sellegipoolest tehniliselt pädeva keelega. Pärast esimese kuue punkti lugemist annab lugeja oma arvamuse selle kohta, kuidas ma seda tegin.

Selleks, et minu tööst oleks rohkem kasu, soovitan teil varustada end kasutatud kirjanduse loendis märgitud autorite töödega. Samuti on soovitatav, et kalkulaatoril oleks toimingu arvutamiseks funktsioon. XOR aastast Artiklit lugedes eeldatakse, et lugeja kavatses seda krüpteerimisalgoritmi uurida. Kuigi see sobib ka viitamiseks, kirjutasin selle artikli just koolitusena.

Eelteave plokkšifrite kohta.

Enne kui hakkame vaatama algoritmi, peame tutvuma seda tüüpi šifrite loomise ajalooga. Algoritm kuulub plokkšifrite kategooriasse, mille arhitektuuris on teave jagatud piiratud arvuks plokkideks, lõplik ei pruugi loomulikult täielik olla. Krüpteerimisprotsess toimub täielikes plokkides, mis moodustavad šifri. Viimast plokki, kui see on puudulik, täiendatakse millegagi (selle täitmise nüansside kohta ütlen allpool) ja see krüpteeritakse samamoodi nagu täisplokid. Šifri all pean ma silmas krüpteerimisfunktsiooni tulemust, mis toimib teatud andmehulgale, mille kasutaja krüptimiseks esitas. Teisisõnu, šifr on krüptimise lõpptulemus.

Plokkšifrite väljatöötamise ajalugu on seotud 70ndate algusega, mil IBM, mõistes vajadust kaitsta teavet arvuti edastamiskanalite kaudu andmete edastamisel, alustas oma uurimisprogrammi, mis on pühendatud teabe kaitsmisele elektroonilistes võrkudes, sealhulgas krüptograafia.

Rühma teadlasi - arendajaid IBMist, kes hakkasid uurima sümmeetrilise võtme kasutamise skeemiga krüpteerimissüsteeme, juhtis dr. Horst Feistel.

2.1 Feisteli võrgud

Feisteli pakutud uue krüpteerimismeetodi arhitektuuri nimetati klassikalises kirjanduses “The Feisteli arhitektuuriks”, kuid praegu kasutatakse vene ja väliskirjanduses rohkem väljakujunenud terminit - “Feisteli võrk” või Feisteli võrk. Seejärel ehitati sellele arhitektuurile šifr "Lucifer" - mis hiljem avaldati ja tekitas uue huvi laine krüptograafia vastu üldiselt.

"Feisteli võrgu" arhitektuuri idee on järgmine: teabe sisendvoog on jagatud n -bitisteks plokkideks, kus n on paarisarv. Iga plokk on jagatud kaheks osaks-L ja R, seejärel sisestatakse need osad iteratiivsesse plokkšifrisse, milles j-nda etapi tulemus määratakse eelmise etapi j-1 tulemuse järgi! Seda saab illustreerida näitega:

Riis. 1

Kus funktsioon A on plokkšifri põhitegevus. See võib olla lihtne toiming, näiteks XOR -toiming, või võib sellel olla keerukam vorm lihtsate toimingute jada - mooduli lisamine, vasakpoolne nihutamine, elementide asendamine jne - koos, need lihtsad toimingud moodustavad nn - krüptotransformatsiooni peamine samm.

Tuleb märkida, et funktsiooni toimimise põhielemendid on võtmeelementide pakkumine ja XOR -toiming ning sellest, kui hästi on nende toimingute töö läbi mõeldud, räägib see šifri kui terviku krüptograafilisest tugevusest.

Selleks, et Feisteli võrkude idee oleks lõpuks selge, kaaluge lihtsamat juhtumit, mis on näidatud riis. 1, kus funktsioonis A - toiminguid “mod 2” (“xor”), kuid see kõige lihtsam juhtum, tõsisemas olukorras, näiteks riikliku tähtsusega teabe varjamine, võib funktsioon A olla keerulisem (minu arvates on funktsioon A tõesti väga keeruline):

Esialgsed andmed:

L = 1110b, R = 0101, K = 1111b

Hankige šifr

1. (R + K) mod 2 4 = Smod, Smod = 0100b
2. (Smod + L) mod 2 = Sxor, Sxor = 1010b
3. L = R, R = Sxor

L = 0101b, R = 1010b

Selgitame oma tegevust:

1. See toiming on mod 2 4 lisamine. Praktikas taandatakse selline toiming lihtsaks liitmiseks, kus peame lisama kaks numbrit ja ignoreerima ülekandmist 5. numbrile. Kuna kui paneme eksponendid arvu binaarse esituse numbrite kohale, on viienda numbri kohal eksponent neli, siis vaatame allolevat joonist, mis näitab meie toiminguid:

Riis. 2

Siin osutasin noolega eksponentidele, nagu näete, oleks tulemus pidanud olema 10100, kuid kuna mod 2 4 toimingu ajal eiratakse ülekannet, saame 0100.

1. Seda toimingut kirjanduses nimetatakse mod 2, koostamiskeeles rakendatakse seda käsuga XOR... Kuid selle õigem nimi on mod 2 1. Ilma selle ainulaadse toiminguta on vaevalt võimalik luua kiiret ja hõlpsasti rakendatavat krüpteerimisalgoritmi ja samal ajal nii, et see oleks endiselt üsna krüptograafiliselt tugev. Selle toimingu ainulaadsus seisneb selles, et see ise on vastupidine! Näiteks kui number A on XORitud numbriga B, saame selle tulemusel B, tulevikus piisab, kui arvud B ja C üksteise vahel uuesti XOR -i saada, et saada varasem väärtus A!

Selle toimingu käigus saime 1010 numbritega 1110 ja 0100, 1110 tagasisaamiseks piisab numbrite 0100 ja 1010 ületamisest! Selle toimingu kohta leiate lisateavet saidile lisatud artiklist. www.wasm.ru, « Elementaarne juhendCRC_ vigade tuvastamise algoritmid»Autor, kes Ross N. Williams... Sellel tööl on mõte - " 5. Kahendaritmeetika ilma sidekriipsuta". Selles artiklis kirjeldatakse toimingut. xor! Ma hüüan, sest selles artiklis on see toiming nii planeeritud, et lugeja mitte ainult ei mõista, kuidas see toiming töötab, vaid isegi alustab seda. näha, kuulda ja tunda!

1. See toiming on vajalik selleks, et dekrüpteerimise ajal saaks algväärtused šifrist kätte.

2.2 Plokkšifr GOST 28147-89

Krüpteerimisalgoritm GOST 28147 - 89 kuulub plokkšifrite kategooriasse, mis töötab tasakaalustatud Feisteli võrkude arhitektuuri järgi, kus valitud infobloki kaks osa on võrdse suurusega. Algoritm töötati välja KGB kaheksanda osakonna sügavustes, nüüd muudeti see FAPSI -ks ja see kinnitati NSV Liidu ajal 1989. aastal Vene Föderatsiooni krüptimisstandardina.

Selle algoritmi meetodi toimimiseks on vaja jagada teave 64 -bitisteks plokkideks. Looge või sisestage krüpteerimissüsteemi järgmine põhiteave: võti ja asendustabel. Krüpteerimise võtme- ja asendustabeli valikut tuleks võtta väga tõsiselt, sest see on teie teabe turvalisuse alus. Teavet selle kohta, millised nõuded võtmele esitatakse, ja asenduste tabelit leiate punktist "Nõuded põhiteabele".

Meetodi kaalumisel ei keskendu me sellele, sest see artikkel, nagu ma eespool ütlesin, on kirjutatud eesmärgiga õpetada lugejat andmete krüptimiseks selle krüpteerimisalgoritmi lihtsa asendamise meetodil, kuid kindlasti puudutame seda küsimust artikli lõpus.

Teoreetiline miinimum.

3.1 Põhiteave

Nagu ma eespool ütlesin, on andmete krüptimisega aktiivselt seotud järgmised:

3.1.1. Võti on kaheksa elemendi jada, igaüks 32 bitti. Järgnevalt tähistame sümboliga K ja elemendid, millest see koosneb, on k1, k2, k3, k4, k5, k6, k7, k8.

3.1.2 Asendustabel - kaheksa rea ​​ja kuueteistkümne veeru maatriks, edaspidi - Hij. Iga rea ​​i ja veeru ristumiskohas olev element võtab 4 bitti.

Krüpteerimisprotsessi peamine samm on - krüptotransformatsiooni peamine samm. See pole midagi muud kui toiming andmete krüptimiseks vastavalt teatud algoritmile, ainult arendajad on nimetuse liiga tülikaks toonud :).

Enne krüptimise alustamist jagatakse plokk kaheks osaks L ja R, kumbki 32 bitti. Valitakse võtmeelement ja alles siis sisestatakse need kaks ploki osa, võtmeelement, asendustabel, põhietapi funktsiooni, põhietapi tulemus on üks baastsükli iteratsioon, mida arutatakse peatükis järgmine lõik. Peamine samm koosneb järgmistest:

1. Ploki R liitmisosa summeeritakse võtmeelemendiga K mod 2 32. Ma kirjeldasin sarnast toimingut ülalpool, siin on sama asi ainult astendaja mitte "4", vaid "32" - selle operatsiooni tulemust tähistatakse tulevikus Smodiga.
2. Jagage eelnevalt saadud tulemus Smod neljabitisteks elementideks s7, s6, s5, s4, s3, s2, s1, s0 ja sisestage see asendusfunktsioonile. Asendamine on järgmine: element Smod - si on valitud, algusest alustame madalaima elemendiga ja asendame asenduste tabeli väärtusega i - rida ja veerg, millele osutab elemendi väärtus s i. Me läheme elemendile s i +1 ja jätkame samamoodi ning jätkame nii, kuni muudame viimase elemendi Smod väärtust - selle toimingu tulemust tähistatakse kui Ssimple.
3. Selles toimingus nihutame Ssimple'i väärtust tsükliliselt 11 bitti vasakule ja saame Srol.
4. Valime L -ploki teise osa ja lisame selle Sroliga mod 2, mille tulemuseks on Sxor.
5. Selles etapis muutub ploki L osa võrdseks osa R väärtusega ja osa R omakorda initsialiseeritakse Sxori tulemusega ja sel hetkel täidetakse põhisammu funktsioon!

3.3 Põhitsüklid: "32-З", "32-Р".

Teabe krüpteerimiseks on vaja see jagada 64 -bitisteks plokkideks, muidugi võib viimane plokk olla väiksem kui 64 bitti. See asjaolu on selle "lihtsa asendamise" meetodi Achilleuse kand. Kuna selle lisamine 64 bitile on väga oluline ülesanne šifriprogrammi krüptograafilise tugevuse suurendamiseks ja sellesse tundlikku kohta, kui see on infomassis olemas, kuid seda ei pruugi olemas olla (näiteks 512 baiti sisaldav fail! ), Tuleb suhtuda suure vastutusega!

Kui olete teabe plokkideks jaganud, jagage võti elementideks:

K = k1, k2, k3, k4, k5, k6, k7, k8

Krüptimine ise seisneb nn põhitsüklite kasutamises. Mis omakorda sisaldab krüptotransformatsiooni põhisammude n-ndat arvu.

Põhitsüklid on märgistatud, kuidas seda panna: n - m. Kus n on krüptotransformatsiooni põhisammude arv baastsüklis ja m on baastsükli "tüüp", s.t. mis see on, kas "Z" või andmete "R" krüptimine.

Põhiline krüptimistsükkel 32-З koosneb 32 krüptotransformatsiooni põhietapist. Plokk N ja võtme K element sisestatakse funktsiooni, mis rakendab sammu toiminguid, ja esimene samm toimub k1 -ga, teine ​​elemendiga k2 saadud tulemuse üle jne. vastavalt järgmisele skeemile:

k1, k2, k3, k4, k5, k6, k7, k8, k1, k2, k3, k4, k5, k6, k7, k8, k1, k2, k3, k4, k5, k6, k7, k8k8, k7, k6, k5, k4, k3, k2, k1

32-P dekrüpteerimisprotsess toimub sarnaselt, kuid põhielemendid on esitatud vastupidises järjekorras:

k1, k2, k3, k4, k5, k6, k7, k8, k8, k7, k6, k5, k4, k3, k2, k1, k8, k7, k6, k5, k4, k3, k2, k1, k8, k7, k6, k5, k4, k3, k2, k1

Harjuta.

Kui olime tutvunud teabe krüptimise teooriaga, oli aeg näha, kuidas krüptimine praktikas toimub.

Esialgsed andmed:

Võtke infoblokk N = 0102030405060708h, siin on osad L ja R võrdsed:

L = 01020304h, R = 05060708h, võtame võtme:

K = ' nagu 28 zw37 q839 7342ui23 8e2t wqm2 ewp1 '(need on ASCII -koodid, kuueteistkümnendes esituse vaatamiseks saate selle faili Total Commanderis kuvamisrežiimis avada, vajutades klahvi F3"Ja siis võti" 3 "). Selles võtmes on elementide väärtused järgmised:

k1 = 'as28', k2 = 'zw37', k3 = 'q839', k4 = '7342'

k5 = 'ui23', k6 = '8e2t', k7 = 'wqm2', k8 = 'ewp1'

Võtke ka järgmine asendustabel:

Riis. 3

Siin on read nummerdatud 0 kuni 7, veerud 0 kuni F.

Hoiatus: Algoritmi kaalumisel on eeskujuks kogu teave, sealhulgas võti koos asendustabeliga!

Kasutades "lähteandmeid", on vaja saada krüptotransformatsiooni põhietapi toimingu tulemus.

1. Valime osa R = 05060708h ja võtmeelemendi k1 = 'as28', kuueteistkümnendsüsteemis näeb võtmeelement välja selline: 61733238h. Nüüd teeme summeerimistoimingu mod 2 32:

Riis. 4

Nagu jooniselt näha, ei olnud meil ülekannet 33 bitiga punasega ja eksponendiga “ 32 ". Ja kui meil oleks R ja võtmeelemendi muud väärtused, oleks see võinud juhtuda ja siis oleksime seda ignoreerinud ning kasutanud edasi ainult kollasega märgitud bitte.

Teen selle toimingu käsuga assembler lisama:

; eax = R, ebx = 'as28'

Selle operatsiooni tulemus Smod = 66793940h

1. Nüüd kõige keerulisem operatsioon, kuid kui te vaatate tähelepanelikult, pole see enam nii kohutav, kui esmapilgul tundub. Kujutleme Smodi järgmiselt:

JOONIST EI SALVESTATUD

Riis. 5

Proovisin joonisel Smodi elemente visualiseerida, kuid selgitan siiski:

s0 = 0, s1 = 4, s2 = 9 jne.

Alustades madalaimast elemendist s0, teeme asendamise. Meenutades lõiku " 3.2 Krüptotransformatsiooni põhietapp»I - rida, s i - veerg, otsige väärtust nullreast ja nullveerust:

Joonis 6

Seega pole Smodi praegune väärtus 6679394 0 h ja 6679394 5 h.

Jätkame s1 asendamist, st. neli. Kasutades esimest rida ja neljandat veergu (s1 = 4!). Vaatame pilti:

Riis. 7

Nüüd juba Smodi väärtus, mitte 667939 4 5h, 667939 2 5h. Eeldan, et nüüd on asendusalgoritm lugejale selge ja võin öelda, et pärast Ssimple'i lõpptulemust on järgmine väärtus - 11e10325h.

Sellest, kuidas seda on kõige lihtsam rakendada, kogujate käskude kujul, räägin järgmises lõigus, pärast laiendatud tabelist rääkimist.

1. Peame saadud Ssimple'i väärtuse 11 bitti nihutama vasakule.

Riis. kaheksa

Nagu näete, on see toiming üsna lihtne ja seda rakendab montaažikeele üks käsk - roll ja selle Srol -operatsiooni tulemus on 0819288Fh.

1. Nüüd jääb meie teabeploki L -osaks XOR -i määramine Srol -väärtusega. Võtan w2k sp4 -st kalkulaatori ja saan Sxor = 091b2b8bh.
2. See toiming on lõplik ja me lihtsalt määrame, puhastame R, L -osa väärtuse ja lähtestame L -osa Sxori väärtusega.

Lõpptulemus:

L = 091b2b8bh, R = 01020304h

4.2 Algoritmi kiiruse suurendamine

Nüüd räägime algoritmi optimeerimisest kiiruse jaoks. Projekti elluviimisel tuleb arvestada, et programm, mis töötab registritega sagedamini kui mäluga, töötab kõige kiiremini ja siin on ka see otsus väga oluline, kuna üle ühe teabeploki koguni 32 krüptimistoimingut!

Kui rakendasin oma programmis krüptimisalgoritmi, tegin järgmist.

1. Valitud osa plokist L eax -registrisse ja R edx -i.
2. Esiregistris, mis on initsialiseeritud laiendatud võtme aadressiga, lähemalt allpool.
3. Registris ebx määras laiendatud asendustabeli aadressi väärtuse, sellest lähemalt allpool
4. Edastas punktide 1, 2, 3 teabe olenevalt olukorrast põhitsükli 32 - З või 32 - Р funktsioonile.

Kui vaatate lõigu põhielementide vooskeemi " Põhitsüklid: "32-З", "32-Р"", Siis saab meie põhitsükli 32 - 3 võtit kujutada järgmiselt:

K 32-Z =

„As28”, „zw37”, „q839”, „7342”, „ui23”, „8e2t”, „wqm2”, „ewp1”,

„As28”, „zw37”, „q839”, „7342”, „ui23”, „8e2t”, „wqm2”, „ewp1”,

„Ewp1”, „wqm2”, „8e2t”, „ui23”, „7342”, „q839”, „zw37”, „as28”

Need. algusest peale on k1, k2, k3, k4, k5, k6, k7, k8 - ‘ nagu 28 ','zw37 ','q839 ',' 7342 ','ui23 ',' 8e2t ','wqm2 ','ewp1 ' seda järjestust korratakse kolm korda. Seejärel lähevad elemendid vastupidises järjekorras, st: k8, k7, k6, k5, k4, k3, k2, k1 - „Ewp1”, „wqm2”, „8e2t”, „ui23”, „7342”, „q839”, „zw37”, „as28”.

Paigutasin massiivi elemendid ette sellises järjekorras, nagu neid tuleks sisestada 32 - Z. Seega suurendasin võtmed kätte põhimõttel nõutavat mälu, kuid päästsin end mõnest mõtlemisprotsessist, mida ma ei vajanud, ja suurendasin kiirust algoritmi, vähendades mälule juurdepääsu aega! Siin kirjeldasin ainult klahvi 32 - З, tsükli 32 jaoks - Р tegin sama, kuid kasutades erinevat elementide varustamise skeemi, mida kirjeldasin ka lõigus " Põhitsüklid: “32-Z”, “32-P».

Nüüd on aeg kirjeldada asendusfunktsiooni rakendamist, nagu ma eespool lubasin. Ma ei osanud varem kirjeldada, sest see eeldab uue mõiste - laiendatud asendustabeli - kasutuselevõttu. Ma ei saa teile selgitada, mis see on. Selle asemel näitan teile seda ja teie ise sõnastate, mis see on - asenduste laiendatud tabel?

Niisiis, selleks, et mõista, mis on laiendatud asendustabel, vajame näiteks asendustabelit, võtan joonisel fig. 3.

Näiteks oli meil vaja asendada number 66793940h. Esitan selle järgmiselt:

JOONIST EI SALVESTATUD

Riis. üheksa

Kui nüüd võtta elemendid s1, s0, s.t. kõige vähem oluline bait, asendusfunktsiooni tulemus on 25 tundi! Pärast Andrei Vinokurovi artikli lugemist, mida ma lõigus tsiteerisin " Kasutatud kirjanduse loetelu", Tegelikult leiate, et kui valite kaks rida, saate massiivi, mis võimaldab teil kiiresti leida asenduselemente, kasutades käsku assembler xlat. Nad ütlevad, et seda saab teha muul viisil kiiremini, kuid Andrei Vinokurov uuris umbes neli aastat GOST -i rakendamise kiireid algoritme! Ma ei arva, et peaksite ratast uuesti leiutama, kui teil see juba on.

Niisiis, massiivi kohta:

Võtame kaks esimest rida nulli ja esimese, loome 256 baiti massiivi. Nüüd täheldame ühte eripära, et kui on vaja muuta 00h, siis on tulemuseks 75h (joonise 3 alusel) - paneme selle väärtuse massiivi nihkega 00h. Võtame väärtuse 01h, asendusfunktsiooni 79h tulemuse, paneme selle massiivi nihkega 01 ja nii edasi kuni 0FFh, mis annab meile 0FCh, mille paneme massiivi nihkega 0FFh. Nii saime laiendatud asendustabeli esimese rea ridade jaoks: esimene ja null. Aga ikkagi on kolm rühma: teine ​​lehekülg 2, leht 3, kolmas leht 4, lehekülg 5, neljas leht 6, lehekülg 7. Nende kolme rühmaga tegeleme samamoodi nagu esimesega. Tulemuseks on laiendatud asendustabel!

Nüüd saame rakendada algoritmi, mis teostab asendamise. Selleks võtame lähtekoodid, mille Andrei Vinokurov oma lehele postitas, vt " Bibliograafia».

lea ebx, laiendatud_tabeli_lihtne

mov eax, [pane asendatav number]

lisage ebx, 100h; hüpata järgmise kahe sõlme juurde

sub ebx, 300h; nii et tulevikus osutab ebx lauale

Nüüd veel üks funktsioon, eelmiste toimingutega me mitte ainult ei asendanud, vaid ka nihutasime numbrit 8 bitti vasakule! Peame lihtsalt veel 3 bitti vasakule nihutama:

ja saame operatsiooni tulemuse rol eax, 11!

Ma ei saa optimeerimise kohta rohkem midagi lisada, ainus, mida saan rõhutada, on see, mida ma eespool ütlesin - kasutage registreid sagedamini kui juurdepääsu mälule. Ma arvan, et need sõnad on ainult algajatele, kogenud ja ilma minu sõnadeta saavad sellest suurepäraselt aru :).

Nõuded põhiteabele.

Nagu Andrei Vinokurovi artiklis öeldud, valitakse võti kahe kriteeriumi järgi:

- kriteerium bittide võrdseks jaotamiseks väärtuste 1 ja 0 vahel. Tavaliselt kasutatakse bittide võrdse jaotuse kriteeriumina Pearsoni kriteeriumi ("chi-square").

See tähendab põhimõtteliselt võtit, mida saab iga number. See tähendab, et võtme järgmise biti moodustamisel on selle initsialiseerimise tõenäosus ühe või nulliga 50/50!

Pange tähele, et võti koosneb kaheksast elemendist, millest igaüks on 32 bitti, seega on võtmes ainult 32 * 8 = 256 bitti ja võimalike võtmete arv on 2 256! Kas see teile ei löö? 🙂

- seeria kriteerium.

Kui me vaatame oma võtit, mille ma lõigus andsin " 4.1 Krüptotransformatsiooni põhietapi rakendamine», Siis märkate, et kehtib järgmine märge:

Riis. kümme

Ühes fraasis ei tohiks k 1 väärtust korrata mitte k 2, mitte üheski teises võtme elemendis.

See tähendab, et võti, mille oleme valinud krüptimisalgoritmi kaalumiseks, vastab täielikult kahele ülaltoodud kriteeriumile.

Nüüd aga asenduste tabeli valiku kohta:

Nüüd räägime sellest, kuidas valida õige asendustabel. Asendustabelite valiku põhinõue on elementide „mittekorratavuse” nähtus, millest igaüks on 4-bitine. Nagu ülal nägite, koosneb iga asendustabeli rida väärtustest 0h, 1h, 2h, 3h,…, 0fh. Seega on peamine nõue, et iga rida sisaldab väärtusi 0h, 1h, 2h, ..., 0fh ja iga selline väärtus ühes eksemplaris. Näiteks jada:

1 2 3 4 5 6 7 8 9 A B C D E F

See vastab täielikult sellele nõudele, kuid siiski! Sellist jada pole soovitatav valida stringina. Kuna kui sisestate väärtuse funktsiooni sisendile, mis tugineb sellisele stringile, saate väljundis sama väärtuse! Ei usu mind? Seejärel võtke asendustabelina number 332DA43Fh ja kaheksa sellist rida. Tehke asendustoiming ja ma kinnitan teile, et väljund on number 332DA43Fh! See tähendab, et sama, mille esitasite operatsiooni sisendile! Ja see pole märk heast vormist krüpteerimisel ja kas oli? 🙂

See oli üks nõue, järgmine kriteerium ütleb, et - iga väljundploki bitt peab olema statistiliselt sõltumatu sisendploki igast bitist!

Kuidas see lihtsam välja näeb? Ja siin on näiteks see, kuidas oleme ülaltoodud arvu hulgast valinud elemendi s0 = 0Fh, 01111b. Tõenäosus, et asendame nüüd esimese biti ühe või nulliga, on 0,5! Iga bitti teise, kolmanda ja neljanda bitti asendamise tõenäosus, mida me eraldi kaalume, ühe või nulliga, on samuti 0, 5. Valides s1 = 0Eh, on tõenäosus, et oleme nullbitt, ja see on "0" , asendatakse nulliga või üks on võrdne - 0,5! Seega selle kriteeriumi järgi puudub korrapärasus elementide s0, s1 nullbittide asendamise vahel! Jah, võite asendada need, kuid võite asendada ka nullid. 🙂

Tabeli hindamiseks selle kriteeriumi järgi saate koostada tabeli korrelatsioonikoefitsientidest, mis arvutatakse järgmise valemi abil:

- kui p = 1, siis on bitti j väärtus väljundis võrdne bitti i väärtusega sisendis mis tahes bitikombinatsioonide korral sisendis;

- kui p = -1, siis biti j väärtus väljundis on alati sisendbiti i pöördväärtus;

- kui p = 0, siis väljundbitt j võrdse tõenäosusega võtab sisendbiti i mis tahes fikseeritud väärtuse väärtused 0 ja 1.

Võtame ühe rea näite:

D	B	4	1	3	F	5	9	0	A	E	7	6	8	2	C

Jagame selle "komponentideks":

Arvutame ühe koefitsiendi vastavalt ülaltoodud valemile. Et seda oleks lihtsam mõista, selgitan seda üksikasjalikumalt:

- võtame sisendil 0 -nda (0) 0 -bitti ja väljundis (1) 0 -nda numbri 0 -nda bitti, teostame operatsiooni 0 XOR 1 = 1.

- võtame sisendist 1. numbri (1) 0 -bitti ja väljundis (1) esimese numbri 0 -nda bitti, teeme operatsiooni 1 XOR 1 = 0.

- võtame sisendist teise numbri (0) 0 -bitti ja väljundis (0) teise numbri 0 -nda bitti, teeme operatsiooni 0 XOR 0 = 0.

- võtame sisendisse kolmanda numbri (1) 0. bitti ja väljundis (1) kolmanda numbri 0. bitti, teeme operatsiooni 1 XOR 1 = 0.

Sellises järjestuses järjestikuste XOR-toimingute tegemisel loendame kõigi nulliväliste väärtuste arvu, saame väärtuse 6. Seega P 00 = 1- (6/2 4-1) = 0,25. Niisiis, selgus, et bitti 0 väärtus väljundis on võrdne bitti 0 väärtusega sisendis 4 juhul 16 -st;

Lõplik koefitsientide tabel:

Koefitsientide tabel on järgmine (kellele pole laisk ümber arvutada)

	sissepääs
Väljund		0	1	2	3
	0	-0,25	0,00	0,00	0,00
	1	0,00	1,00	0,00	0,00
	2	0,00	0,00	1,00	0,00
	3	0,00	0,00	0,00	-0,50

Selles tabelis on asjad veelgi hullemad - grupi bitid 1 ja 2 jäävad muutumatuks! Krüptanalüütikul on, kuhu pöörduda 🙂 Võttes arvesse kõiki neid nõudeid, leidis lihtne otsing ("peaga") näidatud teooriale vastavad permutatsioonitabelid (täna - 1276 kombinatsiooni) Siin on mõned neist:

09 0D 03 0E-06 02 05 08-0A 07 00 04-0C 01 0F 0B

00 05 0A 07-03 08 0F 0C-0E 0B 04 09-0D 06 01 02

06 0B 0F 00-0C 01 02 0D-08 07 09 04-05 0A 03 0E

04 0E 00 09-0B 01 0F 06-03 0D 07 0A-0C 02 08 05

04 02 08 0E-05 0F 03 09-0B 01 0D 07-0A 0C 06 00

07 03 09 0C-08 00 06 0F-0E 04 01 0A-0D 0B 02 05

06 0F 03 08-0D 04 0A 01-09 02 05 0C-00 0B 0E 07

0C 06 08 01-03 09 07 0E-0B 05 0F 02-04 0A 00 0D

04 0B 09 06-0E 01 00 0F-0A 05 03 0C-0D 02 07 08

00 0E 0F 01-07 08 09 06-04 0B 0A 05-03 0D 0C 02

0F 09 01 07-04 0A 08 06-0E 00 02 0C-05 03 0B 0D

0A 03 04 01-05 0C 0B 0E-08 06 0F 0D-07 09 00 02

0B 06 0F 01-04 0A 08 05-00 0D 0C 02-07 09 03 0E

0C 03 02 08-0D 06 0B 05-07 09 04 0F-0A 00 01 0E

02 0B 0F 04-09 00 06 0D-05 0E 01 08-0C 07 0A 03

Kasutatud kirjanduse loetelu.

1. Andrei Vinokurovi artikkel:

Krüpteerimisalgoritm GOST 28147-89, selle kasutamine ja rakendamine

Intel x86 platvormi arvutite jaoks.

(leiate aadressilt: http://www.enlight.ru/crypto/frame.htm).

Samuti on olemas krüpteerimisalgoritmi rakendamise lähtekoodid.

1. Horst Feisteli artikkel:

Krüptograafia ja arvuti turvalisus.

(leiad eelmise artikliga samal aadressil)

1. Ross N. Williams:

Elementaarne juhend CRC vigade tuvastamise algoritmide kohta

Postitatud saidile www.wasm.ru.

Tänuavaldused.

Tahan avaldada tänu kõigile foorumi www.wasm.ru külastajatele. Kuid ma tahaksin eriti tänada ChS -i, kes on praegu tuntud kui SteelRat, ta aitas mul mõista asju, millest ma ilmselt poleks kunagi aru saanud, samuti abi lõigu kirjutamisel: „ Põhiteabe nõuded”, Selle lõigu põhiosa on kirjutanud tema. Samuti olen sügavalt tänulik KSTU töötajale A.N. Tupolev Anikin Igor Vjatšeslavovitš ja patt oleks jätta mainimata Chris Kaspersky selle eest, et ta on, ja Volodya / wasm.ru tema juhiste eest. Oh, ja ma saan seda temalt :). Tahan märkida ka Sega-Zero / Callipso, kuid see tõi mulle meelde mõne matemaatilise džungli.

See on võib -olla kõik, mida ma tahaksin teile öelda.

Oleksin tänulik selle artikliga seotud kriitika või küsimuste või lihtsalt nõuannete eest. Minu kontaktandmed: [e -post kaitstud], ICQ - 337310594.

Parimate soovidega, kurja katkestus.

P.S .: Selle artikliga ei püüdnud ma kedagi edestada. See oli kirjutatud kavatsusega, et hõlbustada GOSTi uurimist ja kui teil on raskusi, ei tähenda see, et olen selles süüdi. Ole mõistlik ja kannatlik, kõike head sulle!

See algoritm on kohustuslik kasutamiseks krüpteerimisalgoritmina 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.

GOST 28147-89 algoritm krüpteerib teabe 64-bitiste plokkidena, 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, sõltuvalt algoritmi töörežiimist (kirjeldatud allpool). Igas voorus tehakse järgmised toimingud:

1. Võtmekate. Alamploki / VI sisu lisatakse modulo 2 32 koos osa Kx võtmega.

GOST 28147-89 algoritmi krüptimisvõtme mõõtmed on 256 bitti ja Kx on selle 32-bitine osa, see tähendab, et 256-bitine krüpteerimisvõti on kujutatud 32-bitiste alamvõtmete ühendamisena (joonis 3.2). :

SH ATI, AG2, YU, AG4, K5, KB, K7.

Krüpteerimisprotsessis kasutatakse ühte neist alamvõtmetest, olenevalt ümmargusest numbrist ja algoritmi töörežiimist.

Riis. 3.1. Algoritmi skeem GOST 28147-

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

2. Tabelite asendamine. Pärast võtme sisestamist jagatakse alamplokk / VI kaheksaks 4-bitiseks osaks, millest igaühe väärtus asendatakse individuaalselt vastavalt alamploki selle osa asendustabelile. Kaasaegsetes krüpteerimisalgoritmides kasutatakse sageli asenduskaste (S-box), seega tasub neid üksikasjalikumalt kaaluda.

Tabel-asendust kasutatakse sel viisil: sisendisse juhitakse teatud mõõtmetega andmeplokk (antud juhul 4-bitine), mille numbriline esitus määrab väljundväärtuse arvu. Näiteks on meil järgmise vormi S-kast:

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

Laske sisendile tulla 4-bitine plokk "0100", see tähendab väärtus 4. Tabeli kohaselt on väljundväärtus 15, see tähendab. "1111" (0 asendatakse 4 -ga, 1 asendatakse 11 -ga, väärtus 2 ei muutu jne).

Nagu näete, on algoritmi skeem väga lihtne, mis tähendab, et suurim andmete krüptimise koormus langeb asendustabelitele. Kahjuks on algoritmil omadus, et on olemas “nõrgad” asendustabelid, mille kasutamisel saab algoritmi krüptanalüütiliste meetoditega avalikustada. Nõrkade hulka kuulub näiteks tabel, kus väljund võrdub sisendiga:

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

3. Bittide kaupa tsükliline vasakpoolne nihe 11 bitti.

Algoritmi töörežiimid

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

□ lihtne asendusrežiim;

□ gamma režiim;

P gamma režiim koos tagasisidega;

□ simulaatorite tootmisviis.

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

Nendel režiimidel on erinevad eesmärgid, kuid kasutatakse sama ülalkirjeldatud krüpteerimistransformatsiooni.

Lihtne asendusrež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, KZ, K4, K5, Kb, AG7, KO, ATI jne - voorudes 1 kuni 24;

□ K1, Kb, K5, K4, KZ, K2, K \, KO - ringides 25. – 32.

Lihtsa asendusrežiimi dekrüptimine toimub täpselt samamoodi, kuid alamvõtmete pisut erineva järjestusega:

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

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

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

Gamma režiim

Gammarežiimis (joonis 3.3) lisatakse igale lihttekstiplokile bitipõhiselt modulo 2 koos 64-bitise šifrilise gammaplokiga. Šifri gamma on spetsiaalne jada, mis luuakse ülalkirjeldatud teisenduste abil järgmiselt:

1. Registritesse N1 ja N2 kirjutatakse nende esialgne täitmine-64-bitine väärtus, mida nimetatakse "sünkro-purskeks" (sünkro-purske on tegelikult CBC, CFB ja OFB režiimides initsialiseerimisvektori analoog).

2. Registrite / VI ja N2 (antud juhul sünkroonimisteadete) sisu krüpteerimine toimub lihtsas asendusrežiimis.

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

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

5. Registrite / VI ja N2 sisu väljastatakse 64-bitise šifr-gammablokina (st antud juhul moodustavad / VI ja N2 esimese gammaploki).

6. Kui on vaja järgmist gammaplokki (st peate jätkama krüptimist või dekrüpteerimist), naasete sammu 2 juurde.

Dekrüptimiseks genereeritakse gamma sarnasel viisil, seejärel rakendatakse XOR -toiming uuesti šifreeritud tekstile ja gammabittidele.

Sama šifrivaliku genereerimiseks peab krüptogrammi dekrüpteerival kasutajal olema sama võti ja sama sünkroonimisväärtus, mida kasutati teabe krüptimiseks. Vastasel juhul ei ole võimalik algteksti krüpteeritud tekstist kätte saada.

Enamikus GOST 28147-89 algoritmi rakendustes pole sünkroonimisteade salajane element, kuid sünkroonimisteade võib olla sama salajane kui krüptimisvõti. Sel juhul võime eeldada, et algoritmivõtme tegelikku pikkust (256 bitti) suurendatakse sünkroonimisteate veel 64 bitti, mida võib pidada täiendavaks võtmeelemendiks.

Gamma režiim koos tagasisidega

Tagasisidega gammarežiimis, registrite / VI ja L / 2 täitmisena, alates 2. plokist, ei kasutata eelmist gammaplokki, vaid eelmise lihtteksti ploki krüptimise tulemust (joonis 3.4) . Selle režiimi esimene plokk genereeritakse täiesti sarnaselt eelmisele.

Riis. 3.4. Šifri gamma genereerimine tagasiside gamma režiimis

Simulaatori tootmisviis

Eesliide on krüptograafiline kontrollsumma, mis arvutatakse krüpteerimisvõtme abil sõnumite terviklikkuse kontrollimiseks. Selle arvutamiseks on GOST 28147-89 algoritmi erirežiim.

Simulaatori genereerimine toimub järgmiselt.

1. Esimene 64-bitine teabeplokk, mille jaoks arvutatakse eesliide, kirjutatakse registritesse N1 ja N2 ning krüpteeritakse lihtsa asendamise vähendatud režiimis, milles tehakse esimesed 16 vooru 32-st.

2. Saadud tulemus summeeritakse modulo 2 koos järgmise teabeplokiga, salvestades tulemuse N1 ja N2.

3. M ja N2 krüpteeritakse uuesti lihtsa asendamise vähendatud režiimis ja nii kuni viimase infoblokini.

Jäljendaja on registrite N1 ja N2 64-bitine sisu või selle osa. Kasutatakse kõige sagedamini kasutatavat 32-bitist eesliidet, st poolt registri sisust. Sellest piisab, sest nagu iga kontrollsumma, on ka simulaator mõeldud eelkõige kaitseks juhusliku teabe moonutamise eest. Andmete tahtliku muutmise eest kaitsmiseks kasutatakse muid krüptograafilisi meetodeid - esiteks elektroonilist digitaalallkirja (vt punkt 1.1).

Imitaatorit kasutatakse järgmiselt:

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

2. Pärast dekrüpteerimist arvutatakse eesliide uuesti ja võrreldakse saadetud eesliitega.

3. Kui arvutatud ja saadetud eesliited ei ühti - salastatud tekst oli edastamise ajal moonutatud või dekrüpteerimisel kasutati valesid võtmeid.

Eesliide on eriti kasulik võtmeinfo õige dekrüpteerimise kontrollimiseks mitme võtmega skeemide kasutamisel.

Jäljendaja on CBC -režiimis arvutatud MAC -sõnumite autentimiskoodi mingi analoog; erinevus seisneb selles, et sünkroonimisteadet ei kasutata eesliite arvutamisel, samas kui initsialiseerimisvektorit kasutatakse MAC -i arvutamisel.

Algoritmi krüptograafiline tugevus

1994. aastal tõlgiti GOST 28147-89 algoritmi kirjeldus inglise keelde ja avaldati; just pärast seda hakkasid ilmnema tema analüüsi tulemused, mille viisid läbi väliseksperdid; siiski pole pikka aega leitud, et rünnakuid oleks võimalik teostada.

□ suur võtme pikkus - 256 bitti; koos salajase sünkroonimissõnumiga suurendatakse võtme tegelikku pikkust 320 bitini;

□ 32 ümberkujundamisvooru; pärast 8 vooru saavutatakse sisendandmete hajutamise täielik efekt: tavalise teksti ploki ühe biti muutmine mõjutab kõiki šifriteksti ploki bitte ja vastupidi, see tähendab, et turvavaru on mitmekordne.

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

Asendustabelite analüüs

Kuna asendustabeleid standardis ei esitata, näitavad mitmed tööd (näiteks c), et "pädev organisatsioon" suudab koostada nii "häid" kui "halbu" asendustabeleid. Kuulus ekspert Bruce Schneier nimetab selliseid oletusi aga "kuulujuttudeks". On selge, et algoritmi krüptograafiline tugevus sõltub suuresti kasutatud asendustabelite omadustest, vastavalt on olemas nõrgad asendustabelid (vt ülaltoodud näidet), mille kasutamine võib lihtsustada rünnakut algoritmi vastu. Sellegipoolest tundub võimalus kasutada erinevaid asendustabeleid väga korraliku ideena, mille kasuks võib tuua kaks fakti DES -i krüptimisstandardi ajaloost (üksikasju vt jaotisest 3.15):

□ DES -algoritmi lineaarset ja diferentsiaalset krüptanalüüsi kasutavad rünnakud kasutavad asendustabelite eripära; teiste tabelite kasutamisel tuleb krüptanalüüsi uuesti alustada;

□ DES -i on püütud tugevdada lineaarse ja diferentsiaalse krüptanalüüsi vastu, kasutades tugevamaid asendustabeleid; sellised tabelid, mis on tõepoolest tugevamad, pakuti välja näiteks s 5 DES algoritmis; kuid kahjuks oli võimatu asendada DES -i s 5 DES -iga, kuna asendustabelid on vastavalt standardis jäigalt määratletud, ei toeta algoritmi rakendamine tõenäoliselt võimalust muuta tabeleid teisteks.

Mitmed tööd (näiteks ja) järeldavad ekslikult, et algoritmi GOST 28147-89 asenduste salajased tabelid võivad olla võtme osa ja suurendada selle tegelikku pikkust (mis on ebaoluline, kuna algoritmil on väga suur 256- biti võti). Kuid töö tõestas, et salajasi asendustabeleid saab arvutada järgmise rünnaku abil, mida saab praktikas rakendada:

1. Seadistatakse nullvõti ja teostatakse „nullvektori” otsing, st väärtused z = / (0), kus / () on algoritmivooru funktsioon. See etapp võtab umbes 2 krüptimistoimingut.

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

Algoritmi modifikatsioonid ja nende analüüs

Töö viis läbi GOST 28147-89 algoritmi muudatuste krüptanalüüsi:

□ GOST-H algoritm, mille puhul algse algoritmiga võrreldes muudetakse alamvõtmete kasutamise järjekorda, nimelt 25. kuni 32. voorus kasutatakse alamvõtmeid otseses järjekorras, st samamoodi nagu algoritmi eelmised voorud;

□ 20-vooruline GOST®-i algoritm, mis kasutab võtme rakendamiseks XOR-i modulo 32 lisamise asemel.

Analüüsi tulemuste põhjal järeldati, 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üptanalüüsi osas kordab töö sõna-sõnalt jaotist, mis on pühendatud GOST 28147-89 algoritmi krüptanalüüsile, mis avaldati 2000. aastal tuntud teosega (ilma viideteta originaalile) . See seab kahtluse alla töö autorite professionaalsuse ja ülejäänud selle tulemused.

Töös pakutakse välja väga huvitav algoritmi modifikatsioon: tabelid S \… Ss peavad olema erinevad; igas algoritmi voorus tuleb need vastavalt teatud seadusele ümber korraldada. See permutatsioon võib sõltuda krüpteerimisvõtmest või olla salajane (st see võib olla osa krüptimisvõtmest, mis on suurem kui algne 256-bitine võti). Mõlemad võimalused suurendavad nende autorite sõnul oluliselt algoritmi vastupidavust lineaarse ja diferentsiaalse krüptanalüüsi suhtes.

Ja töös on toodud veel üks asendustabelitega seotud modifikatsioon, mis analüüsib ü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 võimalikud algoritmi haavatavused.

Täisringi algoritmi analüüs

On rünnakuid kogu vooru GOST 28147-89 vastu ilma muudatusteta. Üks esimesi avatud dokumente, mis analüüsis algoritmi, tuntud paber, on pühendatud rünnakutele, mis kasutavad ära mitmete tuntud krüpteerimisalgoritmide võtme laiendamise protseduuri nõrkusi. Täisringi GOST 28147-89 algoritmi saab lõhkuda, kasutades lingitud võtmete diferentsiaalset krüptanalüüsi, kuid ainult siis, kui kasutatakse nõrku asendustabeleid. Algoritmi 24-vooruline variant (millel puuduvad esimesed 8 vooru) avatakse samamoodi kõikide vahetustabelite jaoks, kuid tugevad vahetustabelid (näiteks näidatud punktis c) muudavad sellise rünnaku täiesti ebapraktiliseks.

Kodumaised teadlased A. G. Rostovtsev ja E. B. Makhovenko pakkusid 2001. aastal oma töös välja põhimõtteliselt uue krüptoanalüüsi meetodi (autorite sõnul palju tõhusam kui lineaarne ja diferentsiaalne krüptanalüüs), moodustades objektiivse funktsiooni teadaolevast lihttekstist, mis vastab sellele šifritekstile ja soovitud võtmeväärtus ja leida selle äärmus, mis vastab tegelikule võtmeväärtusele. Samuti leidsid nad suure hulga GOST 28147-89 algoritmi nõrku võtmeid, mis võimaldavad algoritmi avada, kasutades ainult 4 valitud lihtteksti ja vastavaid üsna väikese keerukusega šifreeritud tekste. Töös jätkatakse algoritmi krüptanalüüsi.

2004. aastal pakkus grupp Korea spetsialiste välja rünnaku, millega lingitud võtmete diferentsiaalset krüptanalüüsi kasutades on võimalik 91,7% tõenäosusega saada 12 bitti salajast võtit. Rünnak nõuab 2 35 valitud tavateksti ja 2 36 krüptimistoimingut. Nagu näete, on see rünnak algoritmi tõelise rünnaku jaoks praktiliselt kasutu.

Algoritm GOST 28147-89 ja šifr "Magma" (GOST R 34.12-2015)

Algoritmi üldine skeem. GOST 28147-89 „Infotöötlussüsteemid. Krüptograafiline kaitse. Krüptograafilise teisendamise algoritm ", on sümmeetrilise krüptimise siseriiklik standard (enne 1. jaanuari 2016) ja see on kohustuslik rakendamiseks sertifitseeritud krüptograafilise teabe kaitse tööriistades, mida kasutatakse osariigi infosüsteemides ja mõnel juhul ka kommertssüsteemides. Teabe krüptograafilise kaitse vahendite sertifitseerimine on vajalik Vene Föderatsiooni riigisaladust moodustava teabe ja teabe kaitsmiseks, mille konfidentsiaalsus tuleb tagada vastavalt kehtivatele õigusaktidele. Ka Vene Föderatsioonis on panganduse infosüsteemide kaitseks soovitatav kasutada algoritmi GOST 28147-89.

GOST 28147-89 algoritm (joonis 2.21) põhineb Feisteli skeemil ja krüpteerib teabe 64-bitiste plokkidena, mis on jagatud kaheks 32-bitiseks alamplokiks (I ja R). Alamblokk R, töödeldakse ümmarguse teisendamise funktsiooniga, misjärel lisatakse selle väärtus alamploki Lj väärtusele, seejärel vahetatakse alamplokid. Algoritmil on sõltuvalt krüpteerimisrežiimist (imitatsiooni sisestamise või muude krüpteerimisrežiimide arv) 16 või 32 vooru.

Riis. 2.21.

Algoritmi igas voorus tehakse järgmised teisendused.

1. Võtme ülekate. Sisu alamblokeerimine R i lisatud ümmarguse võtmega moodul 2 32 K. Kj on ümmarguse võtmena kasutatud algse võtme 32-bitine osa. GOST 28147-89 ns algoritm kasutab võtmete laiendamise protseduuri, algne 256-bitine krüpteerimisvõti on kujutatud kaheksa 32-bitise alamvõtme ühendamisena (joonis 2.22): K 0, K (, K t K, K A, K 5, K 6, K 7.

Krüpteerimisprotsess kasutab ühte neist alamvõtmetest. TO

1. kuni 24. voor - otseses järjekorras:

25. kuni 32. voor - vastupidises järjekorras:

Riis. 2.22. GOST 28147-89 algoritmi krüptimisvõtme struktuur

2. Tabeli asendamine. Pärast võtme rakendamist alamplokk R i on jagatud kaheksaks osaks, kuid 4-bitiseks, millest igaühe väärtus asendatakse individuaalselt vastavalt asendustabelile (S-kast). Kokku kasutatakse kaheksat S -kasti - S 0, S, S 2, S 3, S 4, S 5, S 6, S 7. GOST 28147-89 algoritmi iga S-kast on vektor (ühemõõtmeline massiiv), mille ^ elemendid on nummerdatud vahemikus 0 kuni 15. S-kasti väärtused on 4-bitised numbrid; täisarvud 0 kuni 15.

S-kasti tabelist võetakse element, mille järjekorranumber langeb kokku asendussisendile saabunud väärtusega.

Näide 2.6.

Olgu S-plokk järgmisel kujul:

Olgu selle S-kasti sisendile antud väärtus 0100 2 = 4. S-kasti väljundiks on asendustabeli 4. element, st. 15 = 1111 2 (elemendid on nummerdatud alates nullist).

asendusisikud pole standardis määratletud, nagu seda tehakse näiteks DES -šifris. Asendustabelite muudetavad väärtused raskendavad oluliselt algoritmi krüptanalüüsi. Samal ajal sõltub algoritmi töökindlus oluliselt nende õigest valikust.

Kahjuks on GOST 28147-89 algoritmil “nõrgad” asendustabelid, mille kasutamisel saab algoritmi krüptanalüütiliste meetoditega üsna hõlpsasti paljastada. "Nõrkade" hulka kuulub näiteks tühine asenduste tabel, milles sisend võrdub väljundiga (tabel 2.16).

Tabel 2.16

Näide nõrgast S-kastist

Arvatakse, et asendustabelite konkreetsed väärtused tuleks hoida saladuses ja need on pikaajaline võtmeelement, s.t. kehtivad palju kauem kui üksikud võtmed. Kuid asendustabelite salajased väärtused ei kuulu võtmesse ega saa selle tegelikku pikkust suurendada.

Tõepoolest, salajasi asendustabeleid saab arvutada järgmise rünnaku abil, mida saab praktikas rakendada:

• määratakse nullvõti ja otsitakse "nullvektorit", s.t. tähendus z = F ( 0), kus F - algoritmi ümmarguse teisendamise funktsioon. See nõuab umbes 2 32 testkrüpteerimistoimingut;
• kasutades nullvektorit, arvutatakse asendustabelite väärtused, mis ei võta rohkem kui 2 11 toimingut.

Kuid isegi kui asendustabelite konfidentsiaalsust rikutakse, jääb šifri tugevus äärmiselt kõrgeks ega jää alla lubatud piiri.

Samuti eeldatakse, et asendustabelid on sama krüptograafilise kaitsesüsteemi kõigi krüpteerimissõlmede jaoks tavalised.

S-kastide struktuuri parandamine on sümmeetriliste plokkšifrite valdkonnas üks intensiivsemalt uuritud probleeme. Põhimõtteliselt on nõutav, et kõik muudatused S-kastide sisendites leviksid juhuslik näiliselt muutes väljundit. Ühest küljest, mida suuremad on S-kastid, seda vastupidavam on algoritm lineaarse ja diferentsiaalse krüptanalüüsi meetodite suhtes. Teisest küljest on suurt asenduslauda keerulisem kujundada.

Kaasaegsetes algoritmides on S-kastid tavaliselt vektor (ühemõõtmeline massiiv), mis sisaldab 2 "t- bitielemendid. Plokisisend määrab elemendi numbri, mille väärtus toimib S-ploki väljundina.

S-kastide kujundamisel on esitatud mitmeid kriteeriume. Asendustabel peab vastama:

• range laviini kriteerium;
• natuke sõltumatuse kriteerium;
• mittelineaarsuse nõue sisendväärtustest.

Viimase nõude täitmiseks tehti ettepanek määrata lineaarne kombinatsioon i bitti ( ma = 1, ..., T) asendustabeli väärtused painutatud funktsioonid(eng, kõver - lineaarsetest funktsioonidest kõrvale kaldudes). Kumerad funktsioonid moodustavad Boole'i ​​funktsioonide eriklassi, mida iseloomustab kõrgeim mittelineaarsuse klass ja range laviini kriteeriumi järgimine.

Mõnes töös tehakse S-kastide puhul ettepanek kontrollida tellimuse y garanteeritud laviiniefekti rakendamist-kui üks sisendbitt muutub, muutuvad vähemalt S-kasti väljundbittid. Garanteeritud laviiniefekti suurusjärk y 2 kuni 5 tagab S-kastide piisavalt head difusioonikarakteristikud mis tahes krüpteerimisalgoritmi jaoks.

Piisavalt suurte asenduslaudade kujundamisel saab kasutada järgmisi lähenemisviise:

• juhuslik valik (väikeste S-kastide puhul võib see kaasa tuua nõrkade asendustabelite loomise);
• juhuslik valik, millele järgneb erinevate kriteeriumide täitmise kontrollimine ja nõrkade S-kastide tagasilükkamine;
• käsitsi valimine (suurte S-plokkide jaoks liiga töömahukas);
• matemaatiline lähenemine, näiteks põlvkond, kasutades painutatud funktsioone (seda lähenemist rakendatakse CAST algoritmis).

GOST 28147-89 algoritmi üksikute S-plokkide kavandamiseks võib välja pakkuda järgmise protseduuri:

• iga S-kasti saab kirjeldada nelja loogikafunktsiooniga, igal funktsioonil peab olema neli loogilist argumenti;
• need funktsioonid peavad olema piisavalt keerulised. Seda keerukuse nõuet ei saa ametlikult väljendada, kuid vajaliku tingimusena võib nõuda, et vastavad loogilised funktsioonid, mis on kirjutatud minimaalsel kujul (st minimaalse võimaliku avaldise pikkusega), kasutades põhilisi loogilisi toiminguid, ei tohiks olla lühemad kui teatud nõutav väärtus;
• üksikud funktsioonid, isegi kui neid kasutatakse erinevates asendustabelites, peavad olema üksteisest piisavalt erinevad.

Aastal pakuti välja uus rünnak “refleksiivne kohtumine keskel”, mis vähendab veidi GOST 28147-89 vastupanu (2256-lt 2225-le). Algoritmi parim krüptanalüüsi tulemus 2012. aasta seisuga vähendab selle tugevust 2192-ni, nõudes suhteliselt suurt šifreeritud teksti suurust ja eelvormitud andmete mahtu. Hoolimata kavandatavatest rünnakutest jääb GOST 28147-89 arvutitehnoloogia praegusel arengutasemel praktiliselt stabiilseks.

Kood "Magma" (GOST R 34.12-2015). GOST 28147-89 on Venemaal kehtinud juba üle 25 aasta. Selle aja jooksul on see näidanud tarkvara ja riistvara, sealhulgas vähese ressursiga seadmete puhul, piisavat vastupidavust ja head tõhusust. Kuigi on välja pakutud krüptanalüütilisi rünnakuid, mis vähendavad selle resistentsuse hinnanguid (parim on kuni 2192), pole need kaugeltki teostatavad. Seetõttu otsustati lisada GOST 28147-89 algoritm äsja välja töötatud sümmeetrilisse krüptimisstandardisse.

2015. aasta poes võeti vastu kaks uut riiklikku krüptograafia standardit: GOST R 34.12-2015 „Infotehnoloogia. Krüptograafilise teabe kaitse. Plokkšifrid "ja GOST R 34.13-2015" Infotehnoloogia. Krüptograafilise teabe kaitse. Plokkšifrite töörežiimid ", mis jõustuvad 1. jaanuaril 2016.

Standard GOST R 34.12-2015 sisaldab kahe plokksiferi kirjeldust ploki pikkusega 128 ja 64 bitti. GOST 28147-89 šifr koos fikseeritud mittelineaarsete asendusplokkidega sisaldub uues GOST R 34.12-2015 64-bitise šifrina nimega "Magma".

Allpool on standardis fikseeritud asendusplokid:

Standardis toodud S-kastide komplekt pakub parimaid omadusi, mis määravad krüptoalgoritmi vastupidavuse diferentsiaal- ja lineaarsele krüptanalüüsile.

Standardimise tehnilise komitee "Informatsiooni krüptograafiline kaitse" (TC 26) andmetel muudab mittelineaarsete asendusplokkide fikseerimine GOST 28147-89 algoritmi ühtsemaks ja aitab vältida "nõrkade" mittelineaarsete asendusplokkide kasutamist. Lisaks vastab šifri kõigi pikaajaliste parameetrite standardis fikseerimine aktsepteeritud rahvusvahelisele praktikale. Uus standard GOST R 34.12-2015 on terminoloogiliselt ja kontseptuaalselt seotud rahvusvaheliste standarditega ISO / IEC 10116 “Infotehnoloogia. Turvameetodid. Töörežiimid "-bitiste plokkšifrite" jaoks (ISO / IEC 10116: 2006 Infotehnoloogia - Turvatehnikad - N -bitise plokksiferi töörežiimid) ja ISO / IEC 18033 seeria "Infotehnoloogia. Ohutuse tagamise meetodid ja vahendid. Krüpteerimisalgoritmid ": ISO / IEC 18033-1: 2005" 1. osa. Üldist "(ISO / IEC 18033-1: 2005 Infotehnoloogia - Turvavõtted. Krüpteerimisalgoritmid - Osa 1: Üldine) ja ISO / IEC 18033-3: 2010 "Osa 3. Blokeeri šifrid" (ISO / IEC 18033-3: 2010 (Infotehnoloogia - Turvatehnikad - Krüptimisalgoritmid - Osa 3: Blokeeritud šifrid)).

GOST P 34.12-2015 standard sisaldab ka uut plokksifrit ("Grasshopper"), mille ploki suurus on 128 bitti. Eeldatakse, et see šifr on kõigi täna tuntud plokkšifrirünnakute vastu vastupidav.

Plokkšifrite töörežiimid (lihtne asendamine, gamma, gamma koos tagasiside tagasisidega, gamma koos šifreeritud teksti tagasisidega, lihtne asendamine kaasamisega ja imitatsioonisisu väljatöötamine) on lisatud eraldi standardisse GOST R 34.13-2015, mis vastab aktsepteeritud rahvusvahelist tava. Need režiimid on rakendatavad nii Magma šifri kui ka uue Grasshopperi šifri puhul.

• Sooritatakse ringikujuline ringikujuline nihutamine 11 bitti. Dekrüpteerimine toimub sama skeemi kohaselt, kuid erineva võtmekasutuse ajakavaga: 1. kuni 8. dekrüpteerimisvooru - otseses järjekorras: 9. kuni 32. dekrüpteerimisvooru - vastupidises järjekorras: Võrreldes GES 28147-89 DES-šifril on järgmised eelised: oluliselt pikem võti (256 bitti versus 56 DES-šifri puhul), rünnak, mille puhul võtmekomplekti toore jõuga loendamine tundub praegu võimatu; lihtne ajakava võtme kasutamiseks, mis lihtsustab algoritmi rakendamist ja suurendab arvutuste kiirust. S-plokkide disain GOST 28147-89. On ilmne, et GOST 28147-89 algoritmi skeem on väga lihtne. See tähendab, et suurim krüptimiskoormus langeb asendustabelitele. Vahekaardi väärtused
• Panasepko S.P. krüptimisalgoritmid: spetsiaalne teatmeteos. SPb.: BHV-Peter-Burg, 2009.
• Kara O. Peegeldusrünnakud toote šifridele. URL: http://eprint.iacr.org/2007/043.pdf
• Vene krüptimisstandard: tugevus on vähenenud. URL: http://cryptofaq.ru/index.php/2010-12-23-18-20-21/2010-12-23-18-22-09/90-2011-02-01-07-47- 27
• Achekseev E. K., Smyshlyaev S. V. GOST 28147-89: "Ärge kiirustage teda matma."

Tuntud teadlane, algebralise krüptanalüüsi asutaja Nicolas Courtois väidab, et GOST-plokkšifer, millest pidi lähitulevikus saama rahvusvaheline standard, on tegelikult katki ja ootab tulevikus palju väljaandeid, mis peaksid tema ideid arendama selle algoritmi ebastabiilsuse kohta.

Järgnevad lühikesed katkendid sellest teosest, mida võib pidada ärevaks rünnakuks keset rahvusvahelist standardimist (autor oli tuntud sarnaste liialduste osas seoses AES -iga, kuid tema töö avaldas siis krüptanalüüsile suurt teoreetilist mõju, kuid ei viinud praktiliste rünnakuteni AES -i enda vastu). Kuid võib-olla on see ka tõeline hoiatus "õhusõiduki sabaotsasse sukeldumise" etapi alguse kohta, mis võib lõppeda riikliku krüptimisstandardi kokkuvarisemisega, nagu juhtus SHA-1 räsimisalgoritmi ja de facto MD5 räsimisalgoritm.

GOST 28147-89 standardiseeriti 1989. aastal ja sai esmakordselt konfidentsiaalse teabe kaitse ametlikuks standardiks, kuid šifri spetsifikatsioon jäi suletuks. 1994. aastal salastati standard, avaldati ja tõlgiti inglise keelde. Analoogselt AES -iga (ja erinevalt DES -st) on GOSTil lubatud kaitsta salastatud teavet ilma piiranguteta vastavalt Venemaa standardis täpsustatud viisile. See. GOST ei ole DES analoog, vaid 3-DES konkurent kolme sõltumatu võtmega või AES-256. Ilmselgelt on GOST üsna tõsine šifr, mis vastab sõjalistele kriteeriumidele ja mis on loodud kõige tõsisemate rakenduste ootuses. Vene pankade kasutatavate rakenduste põhjal on tuvastatud vähemalt kaks GOST S-kastide komplekti. Need pangad peavad pidama salajast suhtlust sadade filiaalidega ja kaitsma miljardeid dollareid pettuslike varguste eest.

GOST on lihtsa Feisteli struktuuriga plokkšifr, mille ploki suurus on 64 bitti, 256-bitine võti ja 32 vooru. Iga voor sisaldab modulo 2 ^ 32 võtme lisamist, kaheksa 4-bitise S-kasti komplekti ja lihtsat 11-bitist tsüklilist nihet. GOST-i eripära on võimalus salvestada S-plokke salaja, mida saab esitada teise võtmena, mis suurendab efektiivset võtmematerjali 610 bitini. Üks S-kastide komplekt ilmus 1994. aastal osana räsifunktsiooni spetsifikatsioonist GOST-R 34.11-94 ja nagu Schneier kirjutas, kasutas seda Vene Föderatsiooni keskpank. See sisaldub ka standardis RFC4357 jaotises "id-GostR3411-94-CryptoProParamSet". Schneieri raamatu lõpus (S-kasti järjekorras) oli viga lähtekoodis. Venekeelse päritolu kõige täpsema viiterakenduse leiate nüüd OpenSSL -i teegist. Kui kusagil kasutatakse salajasi S-kaste, siis saab neid tarkvara juurutustest ja mikrolülitustest välja võtta, tegelikult avaldati vastavad tööd.

GOST on tõsine konkurent

Lisaks väga suurele võtme suurusele on GOST -il oluliselt madalamad täitmiskulud võrreldes AES -i ja teiste sarnaste krüpteerimissüsteemidega. Tegelikult maksab see palju vähem kui AES, mis nõuab tunduvalt madalama väidetava turvataseme jaoks neli korda rohkem riistvara loogika väravaid.

Pole üllatav, et GOSTist on saanud Interneti -standard, eriti see on kaasatud paljudesse krüptoraamatukogudesse, nagu OpenSSL ja Crypto ++, ning muutub üha populaarsemaks ka väljaspool oma päritoluriiki. 2010. aastal kuulutati GOST ISO standardimiseks ülemaailmseks krüpteerimisstandardiks. Äärmiselt väike arv algoritme on suutnud saada rahvusvahelisteks standarditeks. ISO / IEC 18033-3: 2010 kirjeldab järgmisi algoritme: neli 64-bitist šifrit-TDEA, MISTY1, CAST-128, HIGHT-ja kolm 128-bitist šifrit-AES, Camellia, SEED. GOST soovitatakse lisada samale ISO / IEC 18033-3 standardile.

Esimest korda tööstuse standardimise ajaloos on meil tegemist sellise konkurentsivõimelise algoritmiga, mis käsitleb optimaalsust kulude ja turvataseme vahel. GOSTil on 20 aastat krüptanalüüsi jõupingutusi ja kuni viimase ajani ei ole selle sõjalise turvalisuse osas kahtlusi seatud.

Nagu autor hiljuti eraviisilisest kirjavahetusest õppis, oli enamik riike Singapuris toimunud ISO hääletusel GOST -i vastu, kuid selle hääletuse tulemusi arvestatakse endiselt ISO SC27 täiskogu istungil, nii et GOST on standardimise ajal veel standardimisprotsessis selle töö avaldamine.

Eksperdiarvamused GOSTi kohta

Miski olemasolevast teabest ja kirjandusest GOSTi kohta ei anna alust arvata, et šifr võib olla ohtlik. Vastupidi, võtme suur suurus ja suur hulk vooru muudavad GOST -i esmapilgul aastakümnete pikkuseks kasutamiseks sobivaks.

Igaüks, kes tunneb Moore'i seadust, mõistab, et teoreetiliselt jäävad 256-bitised võtmed turvaliseks vähemalt 200 aastaks. GOST -i on põhjalikult uurinud juhtivad krüptograafiaeksperdid, kes on tuntud plokkšifreerimise analüüsi valdkonnas, nagu Schneier, Biryukov, Dankelman, Wagner, paljud Austraalia, Jaapani ja Venemaa teadlased, ISO krüptograafiaeksperdid ja kõik teadlased väljendas, et kõik näeb välja selline, et ta võib olla või peaks olema ohutu. Kuigi arvamus jõudis laiale arusaamale, et näiteks GOSTi struktuur on näiteks DESiga võrreldes äärmiselt nõrk, ei ole difusioon nii hea, kuid see oli alati tingitud asjaolust, et seda tuleks kompenseerida suur voorude arv (32), samuti täiendav mittelineaarsus ja difusioon, mida pakub mooduli liitmine.

Biryukov ja Wagner kirjutasid: "Suur voorude arv (32) ja hästi uuritud Feisteli konstruktsioon koos Shannoni järjestikuste permutatsioonidega annavad kindla aluse GOSTi turvalisusele." Samas teoses loeme: "pärast märkimisväärset aja- ja vaevainvesteeringut ei ole avatud kirjanduse standardi krüptanalüüsis tehtud edusamme." Seega puudusid olulised rünnakud, mis võimaldaksid dekrüpteerimist või võtmete taastamist realistliku stsenaariumi korral, kus GOST -i kasutatakse krüptimisel paljude erinevate juhuslike võtmetega. Seevastu on teada palju töid GOST-i nõrkade võtmete rünnakute, nendega seotud võtmetega rünnakute, salajaste S-kastide taastamise rünnakute kohta. Crypto-2008-l esitleti sellel šifril põhinevat räsifunktsiooni häkkimist. Kõigil rünnakutel on ründajal oluliselt suurem vabadus, kui tal tavaliselt oleks lubatud. Traditsioonilistes juhuslikult valitud võtmeid kasutavates krüpteerimisrakendustes ei ole siiani leitud tõsiseid krüptograafilisi rünnakuid GOST -i vastu, mida 2010. aastal väljendas viimane lause: "vaatamata krüptanalüütikute viimase 20 aasta märkimisväärsetele pingutustele ei ole GOST -i veel tehtud krakitud "(Axel Poschmann, San Ling ja Huaxiong Wang: 256 Bit Standardized Crypto for 650 GE GOST Revisited, In CHES 2010, LNCS 6225, lk 219-233, 2010).

Lineaarne ja diferentsiaalne analüüs GOST

Schneieri tuntud raamatust loeme: "Diferentsiaalse ja lineaarse krüptanalüüsi vastu on GOST tõenäoliselt tugevam kui DES." Peamise hinnangu GOSTi turvalisusele andsid 2000. aastal Gabidulin jt. Nende tulemused on väga muljetavaldavad: kui turvatase on 2 ^ 256, piisab viiest voorust, et kaitsta GOSTi lineaarse krüptanalüüsi eest. Veelgi enam, isegi kui asendada S -kastid identsete ja ainsa mittelineaarse šifreerimistoiminguga - lisamoodul 2 ^ 32 -, on šifr pärast 6 vooru 32 -st endiselt lineaarse krüptanalüüsi suhtes vastupidav. GOST -i diferentsiaalne krüptanalüüs tundub suhteliselt lihtsam ja köidab rohkem tähelepanu. Turvalisuse taseme 2 ^ 128 puhul eeldasid teadlased (Vitali V. Shorin, Vadim V. Jelezniakov ja Ernst M. Gabidulin: lineaarne ja diferentsiaalne krüptanalüüs Vene GOSTist, 4. aprillil 2001 Elsevier Preprintile esitatud eeltrükk) piisavat vastupidavust 7 vooru ajal . Nende sõnul on GOSTi rikkumine rohkem kui viies voorus "äärmiselt raske". Veelgi enam, kaks Jaapani teadlast on näidanud, et klassikalisel ühe diferentsiaalkarakteristikuga rünnakul on äärmiselt väike tõenäosus läbida suur arv raunde. Tuginedes asjaolule, et uuritakse piiratud arvu voorude jaoks piisavalt "head" iteratiivset diferentsiaalomadust (mille tõenäosus läbida ei ole parem kui 2-11,4 vooru kohta), on sobivate klahvide komplekti väärtus alla poole . Täisringi GOST-i korral töötab selline ühe omadusega rünnak ainult tühise osa klahvidega suurusjärgus 2-62 (ja isegi selles väikeses osas on tõenäosus, et see läbib mitte rohkem kui 2-360 ).

Keerukamad rünnakud hõlmavad mitut diferentsiaali, mis järgivad teatud mustreid, näiteks kasutavad üksikuid S-lahtreid, millel on null diferentsiaali, samas kui teistel bittidel on nullist erinevad. Me räägime diskrimineerivatest rünnakutest, mis põhinevad GOST -i halbadel difusiooniomadustel. Parim neist rünnakutest töötab 17 GOST -i vooru vastu, sõltub võtmest ja sellel on väljundi enda juhuslike andmete äärmiselt nõrk diskrimineerija, nii et seda saab kuidagi kasutada võtme kohta teabe saamiseks.

Libistage ja suunake rünnakud kõrvale

Biryukovi ja Wagneri sõnul muudab GOST-struktuur, mis sisaldab alamvõtmete vastupidist järjekorda viimastes voorudes, libisemisrünnakute (nn "slaidirünnakud") suhtes vastupidavaks. Kuid kuna šifris on suur enesesarnasus, võimaldab see teatud nõrkade võtmete puhul klahvide ümberpööramise rünnakuid fikseeritud punktide ja "peegeldusomaduste" kombinatsioonide (nn "peegeldavad rünnakud") vastu. Selle rünnaku keerukus on 2 ^ 192 ja 2 ^ 32 sobivat tavateksti.

Viimased tulemused

Uued rünnakud kasutavad ka peegeldust ja purustasid tegelikult GOST -i, mis esitati konverentsil FSE 2011. Need rünnakud avastas ka käesoleva artikli autor iseseisvalt. Rünnak nõuab 2 ^ 132 baiti mälu, mis on tegelikult hullem kui aeglasemad, väiksema mälunõudlusega rünnakud.

Mitmed uued enesesarnasuse rünnakud töötavad kõigi GOST-võtmete vastu ja võimaldavad teil 256-bitise võtmega katkestada täisringi GOST-i, mitte ainult nõrkade võtmete jaoks, nagu see oli varem. Kõik need rünnakud nõuavad oluliselt vähem mälu ja on oluliselt kiiremad.

Neid uusi rünnakuid võib vaadelda kui näiteid uuest üldisest paradigmast plokkšifrite krüptanalüüsi kohta, mida nimetatakse "algebralise keerukuse vähendamiseks", kusjuures need rünnakud on üldistatud paljudele teadaolevate fikseeritud punktide, slaidide, involutsioonide ja tsüklite rünnakute erijuhtumitele. On oluline, et kõigi nende rünnakute perekonnas oleks neid, mis võimaldavad GOST -i krüptanalüüsi ilma igasuguste peegeldusteta ja ilma arvutuste käigus ilmuvate sümmeetriliste punktideta. Üks näide on lihtne GOST -i häkkimisrünnak ilma selles töös kajastamata.

Algebraline krüptanalüüs ja vähese keerukusega andmete rünnakud vähendatud voorude šifridele

Algebralisi rünnakuid plokkide ja voogude šifrite vastu võib kujutada probleemina suure Boole'i ​​algebralise võrrandi süsteemi lahendamisel, mis järgib konkreetse krüptograafilise skeemi geomeetriat ja struktuuri. Idee pärineb Shannonist. Praktikas esitati see DES -i jaoks (esmakordselt selle töö autor) formaalse kodeerimismeetodina ja võib murda 6 vooru vaid ühes teadaolevas lihttekstis. Võrrandiga manipuleerimine põhineb XL algoritmidel, Gröbneri alustel, ElimLini meetodil, SAT -i lahendajatel.

Praktikas on algebralisi rünnakuid rakendatud väga väikese arvu plokkšifrite voorude vastu, kuid need on juba viinud ojašifrite pragunemiseni, samuti on saavutatud edu mikroseadmete ülikergete šifrite purustamisel. Mälu suuruse ja arvutuskulude prognoosimise raskuste tõttu kombineeritakse need teiste rünnakutega.

Kuidas häkkida GOST -i?

Selles väljaandes on üksikasjalikumalt esitatud algebraline rünnak täisringi GOST-i vastu. Eelmises töös on autor juba välja toonud 20 algebralist rünnakut GOST -ile ja ootab lähiajal neist suurt hulka. Selles töös välja pakutud rünnak ei ole neist parim, kuid see avab lihtsa (vähemalt krüptograafide mõistmiseks) tee edasisteks arenguteks, et luua konkreetne metoodika GOST -i lõhkumiseks.

Praktiline tulemus on endiselt tagasihoidlik: 2 ^ 64 teadaolevat lihtteksti ja 2 ^ 64 mälu lihtteksti / šifriteksti paaride salvestamiseks võimaldavad GOST 2 ^ 8 lõhkuda kiiremini kui lihtne toore jõud. Kuid krüptanalüüsi osas on see väide, et "GOST on häkkinud", täiesti õiglane.

järeldused

GOST eesmärk on pakkuda sõjalist turvalisust 200 aastaks. Enamik juhtivaid eksperte, kes on GOSTi uurinud, on jõudnud üksmeelele, et "vaatamata märkimisväärsetele krüptanalüütilistele pingutustele 20 aasta jooksul, pole GOST -i veel pragunenud". 2010. aastal tõsteti GOST ülemaailmseks krüpteerimisstandardiks ISO 18033.

Algebralise krüptanalüüsi ideede alus tekkis üle 60 aasta tagasi. Kuid alles viimase 10 aasta jooksul on välja töötatud tõhusad tarkvaratööriistad paljude NP-täielike probleemide (osaliseks) lahendamiseks. Mitu voo šifrit on murtud. Selle meetodiga on lõhutud vaid üks plokksifer - nõrk KeeLoq ise. Selles töös murrab autor olulise, tegelikult kasutatud GOST -i šifri. Ta märgib, et see on esimene kord ajaloos, kui algebraline krüptanalüüs on rikkunud standardseisundi šifri.

Lihtne GIT -i rünnak "MITM koos peegeldusega" on juba esitatud konverentsil FSE 2011. Käesolevas artiklis käsitletud töös esitatakse teine ​​rünnak ainult selleks, et illustreerida seda, kui palju GOST -i rünnakuid on juba ilmunud, millest paljud on kiiremad ja algebraline rünnak nõuab palju vähem mälu ning avab vastasele peaaegu ammendamatu võimaluste ruumi rünnata šifrit erineval viisil. Ka selles dokumendis on näidatud, et häkkimise omadust pole häkkimiseks vaja kasutada.

Autor väidab, et on ilmne, et GOSTil on tõsiseid vigu ja see ei taga nüüd ISO poolt nõutavat vastupidavuse taset. Paljud rünnakud GOST -i vastu on esitatud algebralise keerukuse vähendamise paradigma kinnitamise raames.

Lõpetuseks märgib teadlane eriti mõningaid fakte, mis pole lugejale veel kättesaadavad, kuid teadlasele teada ja mis on ISO standardimisprotsessi käigus olulised. See rünnak ei ole lihtsalt "sertifitseerimise" rünnak GOST -i vastu, mis on kiirem kui toorjõu toorjõu rünnak. Tegelikult oleks GOSTi standardimine nüüd äärmiselt ohtlik ja vastutustundetu. Seda seetõttu, et mõned rünnakud on praktikas teostatavad. Praktikas saab mõnda GOST -võtit isegi dekrüpteerida, olenemata sellest, kas need on nõrgad või GOST -i privaatsete rakenduste võtmed. Eelmises töös käsitleb autor üksikasjalikult praktiliste rünnakute võimalikkuse juhtumeid. Tähelepanuväärne on see, et "see on esimene kord ajaloos, kui tõsist standardiseeritud plokkšifrit, mis on loodud sõjaväelise saladuse kaitsmiseks ja mille eesmärk on kaitsta valitsuste, suurte pankade ja muude organisatsioonide riigisaladusi, on matemaatiline rünnak ohtu seadnud."