Yhteiskunnassa hyvin tunnettu termi "prosessorin suorituskyky" on objektiivinen, laskettu parametri, jota mitataan floppeina. Suurin osa kuitenkin mittaa sen gigahertseinä uskoen naiivisti, että tämä on sama asia. Kukaan ei tiedä termiä "koodin suorituskyky", ja selitän heti miksi.

Syynä on se, että keksin sen vasta äskettäin enkä ole vielä kertonut siitä kenellekään. Kuitenkin koodin suorituskyvyllä, kuten prosessorin suorituskyvyllä, on objektiivisia ominaisuuksia, jotka voidaan mitata. Tämä artikkeli käsittelee erityisesti suoritinytimen suorittaman koodin suorituskykyä.

Miten koodin suorituskykyä mitataan? Koska puhuin tästä ensimmäisenä, niin mittaan sen löytäjän oikeudella RTT-asteikoissa;).

Nyt tosissaan. Nykyaikaisissa prosessoreissa tärkeimmät muunnokset ovat operaatioita 32-bittisillä numeroilla, kaikki muu on suurelta osin eksoottista. Siksi otamme huomioon pääasia - toiminnot 32-bittisillä numeroilla. Kuinka monta 32-bittistä toimintoa nykyaikaisen prosessorin ydin voi mielestäsi suorittaa samanaikaisesti?

Opiskelija vastaa - yksi, hänen opettajansa ajattelee ja sanoo, että neljä, ammattilainen - että operaatioita on toistaiseksi vain kaksitoista.

Joten ohjelmakoodilla, joka lataa kaikki prosessorin executive-laitteet samanaikaisesti koko koodin suoritusajan ajan, suorituskyky on 12 RTT NIS. Enimmäismäärä! Ollakseni rehellinen, en ole koskaan aiemmin kirjoittanut tällaista koodia, mutta tässä artikkelissa yritän yrittää itseni.

Todistan, että koodi kahdentoista 32-bittisen toiminnon samanaikainen suorittaminen on mahdollista

Prosessorin ytimessä yhtä suoritusyksikköä käyttävän ohjelmakoodin suorituskyky on luonnollisesti 1 RTT. Korkean tason kielenkääntäjien ja virtuaalikoneen tulkkien luomat ohjelmat voivat "kerskua" sellaisella koodin suorituskyvyllä. Ei pidä olettaa, että prosessorin käyttöilmaisin, joka näkyy käyttöjärjestelmän tehtävähallinnassa, voi toimia objektiivisena kriteerinä koodin tehokkuudelle. Prosessorin ytimen kuormitus voi olla 100%, mutta ohjelmakoodi käyttää siinä yhtä suorituslaitetta (suorituskyky 1 RTT). Tässä tapauksessa 100 %:n kuormituksella prosessoriydin toimii 1/12 sen maksimitehosta. Toisin sanoen, kun Windowsin Tehtävienhallinta näyttää maksimisuorittimen käytön, sen todellinen suorituskyky voi vaihdella 1 - 12 RTT. Nähdessään suorituskykyikkunassa 100 %:n kuormituksen mille tahansa prosessorin ytimelle, on väärin olettaa, että kaikki executive-laitteet toimivat tässä ytimessä, ei suinkaan!

Ainoa epäsuora kriteeri prosessorin ytimen maksimaalisen suorituskyvyn arvioimiseksi on sen virrankulutus ja sen seurauksena jäähdyttimen melu. Nyt, jos jäähdytin on meluisa, niin kyllä ​​- kuorma on mennyt maksimiin. On kuitenkin aika lopettaa yleiset käsitteet ja siirtyä koviin käytäntöihin.

GOST 28147-89:n perinteinen toteutus

En ole tietoturva-alan ammattilainen, mutta salauksen aihe on minulle silti tuttu. Keskusteluni ammatti kryptografin kanssa, jota kunnioitan syvästi, inspiroivat minua ryhtymään erityisen symmetriseen virtasalaukseen. Ja otettuani tämän aiheen, yritin tehdä sen hyvin, enkä vain hyvin, vaan myös nopeasti suorittaen maksimimäärän toimintoja aikayksikköä kohden. Toisin sanoen minun edessäni oli tehtävä kirjoittaa ohjelmakoodi maksimi RTT-arvolla.

GOST 28147-89:n mukaista kryptografista muuntamista käytetään tiedonsiirron salaukseen viestintäkanavissa ja levyasemissa.

Tällä hetkellä tämän GOST:n ohjelmistototeutusta keskusprosessorin RON:lla käytetään laajalti. Tunnetuissa GOST-toteutusmenetelmissä kaikki salaiset tiedot (salausavaimet, korvaavat lohkot) sijoitetaan RAM-muistiin. Tämä vähentää salauksen luotettavuutta, koska RAM-vedosten avulla on mahdollista paljastaa täysin salausmuunnoksen salaiset elementit. Lisäksi menetelmällä on nopeusrajoituksia, jotka johtuvat kryptomuunnoksen pääobjektien sijainnista OP:ssa ja ALU:n toimeenpanolaitteiden epätäydellisestä latauksesta. Nykyaikaiset prosessorit, jotka toteuttavat kryptoproseduurin tunnetulla menetelmällä, voivat tarjota salausnopeuden 40–60 megatavua sekunnissa. Ja jos ymmärrät sen todella loppuun asti, syy kryptomuunnoksen heikon suorituskyvyn ja heikon turvallisuuden vuoksi on korvauslohkon ohjelmistototeutus. Katso sen kuvaus GOST:ssa kuvassa 2. 1.

GOST:n kohdan 1.2 mukaan tämä lohko toteuttaa tetradi-permutaatioita (neljä bittiä) 32-bittisessä sanassa, mutta x86 / 64-prosessorin arkkitehtuuri ja sen käskyjoukko eivät pysty manipuloimaan tetradeja tehokkaasti.

Korvauslohkon ohjelmistototeutukseen käytetään erityisiä RAM-taulukoita, jotka valmistetaan kryptotoiminnon alustusvaiheessa. Nämä taulukot yhdistävät vierekkäisten tetradien korvaussolmut 8 × 8 bitin tavutaulukoiksi, joten RAM-muistissa on neljä 256-tavuista taulukkoa.

Edistyneemmissä toteutuksissa nämä taulukot ovat kooltaan 1024 tavua (256 sanaa neljästä tavusta). Tämä tehdään, jotta taulukoissa voidaan toteuttaa ylimääräinen syklinen siirto 11 paikalla 32-bittisestä sanasta, joka on saatu korvaamisen seurauksena (muunnosalgoritmin seuraava operaatio GOST:n mukaan). Esimerkki GOST:n toteutuksesta tämän menetelmän mukaisesti on esitetty liitteessä 1 (levyllä).

Korvauslohkon tiedot ovat salaustoiminnon salainen komponentti (kuten se on muotoiltu GOST:ssa, katso kuva 2).

Näiden taulukoiden sijoittaminen korvauslohkon avaimilla OP:ssa on ristiriidassa GOST:n vaatimusten kanssa (lauseke 1.7), koska salaiset tiedot tulevat saataville kolmannen osapuolen ohjelmille, jotka toimivat tietokoneasennuksessa. FSB, joka myös sertifioi GOST-salauksen ohjelmistototeutuksia, suhtautuu tähän rikkomukseen lievästi sanottuna alentuvasti. Jos avaimien sijoittamiseksi OP:iin, FSB vaatii edelleen "viikunanlehteä" - peittää avaimet XOR-toiminnolla, OP:n korvaaville lohkoille ei tarvita mitään, ne tallennetaan selkeänä tekstinä.

Lyhyesti sanottuna FSB ohittaa tällaiset salausmenettelyn ohjelmistototeutukset huolimatta tällaisen ratkaisun voimakkuuden ilmeisestä heikkenemisestä ja sen omien vaatimusten suorasta rikkomisesta GOST:n mukaan (lauseke 1.7). Ja tämä huolimatta tunnetuista salausmenetelmistä poistamalla muistivedos ...

Palaamme kysymykseen avainten ja korvaavien lohkojen tallentamisesta prosessorin sisäisiin rekistereihin hieman myöhemmin (on kaunis ja nopea ratkaisu), mutta toistaiseksi tallennamme salausavaimia vain MMX-rekistereihin, tämä on luotettavampaa.

Mutta sanoituksista riittää, tarkasteltavan aiheen puitteissa on tärkeää, että tämän ohjelmakoodin suorituskyky on 1 RTT-shku. Nyt kirjoitetaan koodi, jonka suorituskyky on 2 RTT:tä.

GOST 28147-89:n monisäikeinen toteutus

Ainoa tapa nopeuttaa kryptoproseduureja tunnetussa algoritmissa on monisäikeistyksen käyttöönotto. Tällaisen algoritmin toteutuksen muutoksen tarkoitus on laskea useita tietolohkoja rinnakkain kerralla.

Useimmat ohjelmoijat tarkoittavat rinnakkaiskäsittelyllä vain useiden prosessoriytimien työtä, jotka on synkronoitu muistissa olevien keskeytysten ja semaforien kautta.

On kuitenkin olemassa toinen muunnelma rinnakkaisesta tietojenkäsittelystä yhdessä prosessoriytimessä. Sallikaa minun selittää tämä ei-ilmiselvä ajatus.

Nykyaikaisissa prosessoreissa on vähintään kaksi, jopa kolmesta kuuteen aritmeettista logiikkayksikköä. Nämä ALU:t (FPU:t, osoitearitmeettiset yksiköt ja niin edelleen) voivat toimia toisistaan ​​riippumatta, ainoa ehto niiden rinnakkaiselle toiminnalle on ei-päällekkäiset ohjelmistoobjektit, joita ne käyttävät. Toisin sanoen käskyissä, jotka suorittavat samanaikaisesti ALU:n, muistiosoitteiden ja rekisterinumeroiden on oltava erilaisia. Tai prosessorin eri johtavien laitteiden käyttämiin yleisiin rekistereihin ja muistiosoitteisiin ei tule suorittaa kirjoitustoimintoja.

Kaikkien ALU:iden työn lataamista ohjaa prosessorin ytimen sisällä oleva erityinen laitteistolohko - ajastin, joka katselee suoritettavaa koodia eteenpäin 32–64 tavun syvyyteen. Jos ajastin löytää komennot, jotka voidaan suorittaa ALU:ssa ilman ristiriitoja, se suorittaa ne samanaikaisesti eri suoritusyksiköissä. Tässä tapauksessa suoritettujen komentojen laskuri osoittaa suoritettavaa komentoa (niitä on useita sellaisessa järjestelmässä), jonka jälkeen kaikki komennot on jo suoritettu.

Useimmat automaattisesti (kääntäjien) luomat ohjelmasekvenssit eivät voi ladata kaikkia prosessorin ytimessä olevia ALU:ita ja FPU:ita. Tässä tapauksessa prosessorilaitteisto on käyttämättömänä, mikä heikentää merkittävästi sen tuloksena olevaa suorituskykyä. Prosessorikehittäjät ymmärtävät tämän ja ottavat käyttöön tiloja ydintaajuuden lisäämiseksi, kun laitteita ei käytetä täysin. Hyper-kaupankäyntijärjestelmät on myös suunniteltu tähän, ja käytän tätä järjestelmää koodin "painamiseen" jatkossa maksimiin.

Kääntäjät, jopa optimoiduimmat, ja vielä enemmän - virtuaalikoneen moottorit, eivät voi luoda optimoitua koodia suorituskyvyn kannalta. Vain ohjelmoija, jolla on teknistä tietämystä, voi kirjoittaa tällaista optimoitua koodia, ja työkalu sen kirjoittamiseen on yksinomaan assembler.

Tyypillinen esimerkki mahdollisuudesta suorittaa useita itsenäisiä ohjelmasäikeitä yhdessä prosessoriytimessä on GOST-toteutus, joka suoritetaan kahdessa säikeessä yhdessä prosessoriytimessä. Koodin idea on yksinkertainen: salaukseen/salauksen purkamiseen on kaksi tietolohkoa, mutta yksi prosessoriydin, joka suorittaa muuntamisen. Näiden kahden tietolohkon muunnos on mahdollista suorittaa peräkkäin, ja tämä on tehty tähän asti. Tässä tapauksessa muunnosten suorittamiseen tarvittava aika kaksinkertaistuu.

Mutta voit tehdä toisin: vaihtoehtoiset komennot, jotka liittyvät eri tietolohkojen käsittelyyn. Graafisesti nämä vaihtoehdot on esitetty kuvassa. 3.

Kuvassa ylempi esimerkki esittää tavallista järjestystä, jossa kaksi itsenäistä tietolohkoa käsitellään. Ensin käsitellään ensimmäinen lohko, jonka jälkeen prosessori etenee toisen lohkon käsittelyyn. Luonnollisesti tuloksena oleva aika on yhtä suuri kuin kaksi kertaa yhden lohkon käsittelyyn tarvittava aika, eikä prosessoriytimen suoritusyksiköitä ole ladattu täyteen.

Seuraavassa on esimerkki lomituskomennoista eri käsittelysäikeistä. Tässä tapauksessa eri tietolohkoihin liittyvät komennot limitetään. Ajastin valitsee toisistaan ​​riippumattomat käskyt ja välittää ne ALU1:lle ja ALU2:lle suoritettaviksi. Ensimmäisen ja toisen säikeen komentojen ryhmittely näissä ALU:issa tapahtuu automaattisesti, koska ajoittajan toiminta-algoritmi sisältää komentojen ryhmittelyn vaihteistoineen saman toimeenpanolaitteen yhteisten tietojen mukaan.

Jotta tällainen ohjelmakoodi toimisi ilman ALU:n joutoaikaa, on välttämätöntä, että jokainen ohjelmasäie toimii omilla rekisteriillään. Tämän mallin välimuistista tulee pullonkaula (sillä on vain kaksi datalähtöporttia), joten tallennamme avaimet MMX-rekistereihin. Koska tässä tapauksessa korvaavat (ja siirto) solmut ovat vain luku -muistissa, ne voidaan jakaa molemmille ohjelmasäikeille.

Tämä on tietysti hyvin yksinkertaistettu selitys ohjelmasäikeiden rinnakkaisen suorittamisen periaatteesta yhdessä ytimessä, todellisuudessa kaikki on paljon monimutkaisempaa. Käytännössä on tarpeen ottaa huomioon suoritusyksiköiden putkiarkkitehtuuri, välimuistin ja RON-rekisterien lohkon samanaikaisen käytön rajoitukset, osoitearitmeettisten solmujen, kytkimien ja paljon muuta ... Joten tämä on aihe ammattilaisille, jotka voidaan laskea ... yhden käden sormilla.

Rinnakkaissalausmenetelmä on toteutettu tehokkaasti vain 64-bittisen prosessorin toimintatilassa, koska tässä tilassa RON:ia on riittävästi (jopa 16 kappaletta!). Esimerkki GOST:n toteutuksesta tämän menetelmän mukaisesti on esitetty liitteessä 2 (levyllä).

On selvää, että tämän GOST-toteutuksen koodin suorituskyky on 2 RTT:tä. Katsotaan nyt kuinka tämä vaikuttaa suoritusaikaan.

Yhden virran salausjakso (Liite 1) on 352 jaksoa, ja tänä aikana lasketaan 8 tavua dataa, kaksivirtaiseen GOST-toteutukseen (Liite 2) tarvitaan 416 prosessorijaksoa, mutta lasketaan 16 tavua. Siten tuloksena saatu muunnosnopeus kasvaa 80 megatavusta 144 megatavuun 3,6 GHz:n prosessorilla.

Mielenkiintoinen kuva saadaan: koodi sisältää täsmälleen kaksi kertaa enemmän ohjeita, ja se kestää vain 15% kauemmin, mutta luulen, että lukijat ovat jo ymmärtäneet tämän ilmiön syyn ...

Teoriassa toisen esimerkin koodi pitäisi suorittaa samassa jaksomäärässä kuin ensimmäisen esimerkin koodi, mutta vaikka Intelin insinöörit kehittävät ajoitussolmua, he ovat myös ihmisiä, emmekä kaikki ole täydellisiä. Joten on mahdollisuus arvioida niiden luomisen tehokkuutta. Tämä koodi toimii myös AMD-prosessorilla, ja voit verrata niiden tuloksia.

Jos joku ei usko sanaani, niin sellaisille epäuskoisille on levyllä testiohjelmia kellolaskureineen. Ohjelmat lähdekoodeissa tietysti assemblerissä, joten on mahdollisuus tarkistaa sanani ja samalla kurkistaa joitain ammattikoodauksen temppuja.

Nykyaikaisten prosessorien SSE-rekisterien ja AVX-komentojen käyttäminen GOST 28147-89:n toteuttamiseen

Nykyaikaiset x86/64-arkkitehtuuriprosessorit sisältävät joukon 16-tavuisia SSE-rekistereitä ja erikoistuneita FPU:ita (vähintään kaksi) suorittamaan erilaisia ​​toimintoja näille rekistereille. GOST on mahdollista toteuttaa tässä laitteessa, ja tässä tapauksessa korvaavat solmut voidaan sijoittaa ei taulukoiden muodossa RAM-muistiin, vaan suoraan omistettuihin SSE-rekistereihin.

Yhteen SSE-rekisteriin voit sijoittaa kaksi 16 rivin taulukkoa kerralla. Näin ollen neljä SSE-rekisteriä mahtuu täysin kaikki korvaavat taulukot. Ainoa ehto tällaiselle sijoittamiselle on lomitusvaatimus, jonka mukaan saman tavun tetradit on sijoitettava eri SSE-rekistereihin. Lisäksi on suositeltavaa sijoittaa syöttötavujen matalat ja korkeat tetradit vastaavasti SSE-rekisterien matalaan ja ylätetradiin.

Nämä vaatimukset määritetään optimoimalla olemassa oleva AVX-komentosarja. Siten jokainen SSE-rekisterin tavu sisältää kaksi tetradia, jotka vastaavat korvauslohkon tulorekisterin eri tavuja, kun taas tavun sijainti SSE-rekisterissä vastaa yksiselitteisesti korvauslohkon korvaustaulukon indeksiä.

Kaavio yhdestä mahdollisesta korvaavien solmujen sijoittelusta SSE-rekistereihin on esitetty kuvassa. 4.

Korvaussolmujen salaisten tietojen sijoittaminen SSE-rekistereihin lisää kryptomenettelyn turvallisuutta, mutta tämän salaisen tiedon täydellinen eristäminen on mahdollista seuraavissa olosuhteissa:

• Prosessorin ydin on asetettu hypervisor-isäntätilaan ja keskeytyslohko (APIC) on pakotettu pois käytöstä. Tässä tapauksessa prosessorin ydin on täysin eristetty käyttöjärjestelmästä ja tietokoneasennuksessa käynnissä olevista sovelluksista.
• SSE-rekisterien lataaminen ja laskennallisen ytimen eristäminen suoritetaan ennen käyttöjärjestelmän käynnistystä; on optimaalista suorittaa nämä toimenpiteet luotetusta käynnistysmoduulista (TDM).
• GOST:n mukaiset kryptoprosessien ohjelmat sijoitetaan laskentayksikön (joko BIOS tai flash-muisti MDZ) ei-muokattavaan muistialueeseen.

Näiden vaatimusten noudattaminen varmistaa kryptomenetelmien ohjelmakoodin ja niissä käytetyn salaisen tiedon täydellisen eristämisen ja muuttumattomuuden.

Tehokkaaseen näytteenottoon tetradien SSE-rekistereistä käytetään FPU-yksiköissä olevia monituloisia tavukytkimiä. Nämä kytkimet mahdollistavat siirron mistä tahansa lähteen tavusta mihin tahansa kohteen tavuun erityisessä SSE-indeksirekisterissä olevien indeksien avulla. Lisäksi siirto suoritetaan rinnakkain kaikille SSE-rekisteri-vastaanottimen 16 tavulle.

Kun SSE-rekistereissä on korvausmuistisolmut ja FPU-yksiköissä on monitulokytkin, on mahdollista järjestää seuraava muunnos korvausyksikössä (kuva 5).

Tässä menetelmässä kunkin tetradin tulorekisteri asettaa osoitteen vastaavalle kytkimelle, joka siirtää tiedot korvaavista solmuasemista lähtörekisteriin dataväylän kautta. Tällainen järjestelmä voidaan järjestää kolmella tavalla:

• Luo sopiva sirusuunnittelu, mutta se on meille fantastinen.
• Mikrokoodin uudelleenohjelmointi ja oman prosessoriohjeen luominen tämän toiminnon toteuttamiseksi olemassa oleviin prosessoreihin ei ole enää fantasiaa, mutta valitettavasti se on epärealistista nykyolosuhteissa.
• Kirjoita ohjelma virallisten AVX-komentojen avulla. Vaihtoehto, vaikkakaan ei kovin tehokas, mutta voimme toteuttaa sen "tässä ja nyt". Joten sitä teemme seuraavaksi.

Kytkimiä ohjataan erityisellä kolmen osoitteen komennolla AVX VPSHUFB. Sen ensimmäinen operandi on tiedon vastaanottaja kytkimistä, toinen on lähde, johon kytkinten tulot on kytketty. Kolmas operandi on kytkimien ohjausrekisteri, jonka jokainen tavu liittyy vastaavaan kytkimeen; siinä oleva arvo määrittää sen suunnan numeron, josta kytkin lukee tietoa. Katso tämän komennon kuvaus virallisesta Intelin dokumentaatiosta, katso kuva. 5. Kuvassa Kuva 6 esittää tämän komennon toiminnan - vain puolet SSE-rekistereistä näytetään, toisella puoliskolla kaikki on samanlaista.

Kytkin käyttää vain vähiten merkitseviä neljää bittiä kytkentäsuunnan määrittämiseen, kunkin tavun viimeisellä bitillä pakotetaan vastaava vastaanotintavu nollaan, mutta tätä kytkintoimintoa ei meidän tapauksessamme vielä vaadita.

Ohjelma, jossa on valikoima muistikirjoja FPU-kytkimien kautta, kirjoitettiin, mutta en edes laittanut sitä sovellukseen - se on liian huono. 128-bittisen rekisterin käyttäminen ja vain 32 bitin käyttäminen siinä on epäammattimaista.

Kuten he sanovat: "Meidän viimeistelymme on horisontti", joten purista se ulos niin... puristamme sen ja laitamme sen pusseihin!

Tämä ei ole sanaleikkiä, vaan ankara FPU-todellisuus - SSE-rekisterit voidaan jakaa yhtä suuriin osiin ja näille osille voidaan tehdä samat muunnokset yhdellä komennolla. Jotta prosessori ymmärtäisi tämän, on olemassa maaginen kirjain "P" - paketti, joka sijoitetaan ennen komentomuistomerkkiä, eikä vähemmän maagisia kirjaimia "Q", "D", "W", "B", jotka sijoitetaan loppuun ja ilmoittavat, mihin osiin SSE-rekisterit on jaettu tässä komennossa.

Olemme kiinnostuneita pursketilasta, jossa SSE-rekisteri on jaettu neljään 32-bittiseen lohkoon; vastaavasti kaikkien komentojen etuliitteenä on "P" ja ne päätetään "D"-symbolilla. Tämä mahdollistaa neljän 32-bittisen lohkon käsittelyn rinnakkain yhdellä prosessorikäskyllä, eli neljän tietolohkon laskemisen rinnakkain.

Tämän menetelmän toteuttava ohjelma löytyy liitteestä 3, siinä on kaikki selitykset.

Paina kuitenkin niin paina! Nykyaikaisissa prosessoreissa on vähintään kaksi FPU:ta, ja niiden lataamiseen voidaan käyttää kahta itsenäistä käskyvirtaa. Jos lomitat oikein komennot itsenäisistä virroista, voit ladata molemmat FPU:t kokonaan ja saada kahdeksan rinnakkaista käsiteltyä tietovirtaa kerralla. Tällainen ohjelma on kirjoitettu, ja näet sen liitteessä 4, mutta sinun on katsottava huolellisesti - voit mennä hulluksi. Tätä kutsutaan "koodi ei ole kaikille ...".

Emissiohinta

SSE-rekisterien käyttö korvaavien solmujen tallentamiseen on ymmärrettävää - se antaa tietyn takuun salaisen tiedon eristämisestä, mutta itse kryptofunktion laskemisen merkitys FPU:ssa ei ole ilmeinen. Siksi standarditoimenpiteiden suoritusaika mitattiin suoralla korvausmenetelmällä GOST:n mukaisesti neljälle ja kahdeksalle virralle.

Neljälle säikeelle saatiin 472 prosessorisyklin suoritusnopeus. Siten prosessorissa, jonka taajuus on 3,6 GHz, yhtä säiettä pidetään nopeudella 59 megatavua sekunnissa ja neljää säiettä vastaavasti nopeudella 236 megatavua sekunnissa.

Kahdeksalle säikeelle saatiin 580 prosessorisyklin suoritusnopeus. Siten 3,6 GHz:n prosessorissa yhden säikeen katsotaan olevan 49 megatavua sekunnissa ja kahdeksan säiettä nopeudella 392 megatavua sekunnissa.

Kuten lukija saattaa huomata, esimerkin #3 koodin suoritusteho on 4 RTT, kun taas esimerkin #4 koodin suorituskyky on 8 RTT. Näissä esimerkeissä SSE-rekistereissä kuviot ovat samat kuin käytettäessä RON:ia, vain ajoittaja on vähentänyt tehokkuuttaan. Se tarjoaa nyt 20 % lisäyksen kestoon ja kaksinkertaistaa koodin pituutta.

Lisäksi nämä tulokset saatiin käyttämällä yleisiä AVX-komentoja, jotka ovat saatavilla sekä Intel- että AMD-prosessoreissa. Jos optimoit AMD-prosessorille, tulos on paljon parempi. Se kuulostaa trendin vastaiselta, mutta se on kuitenkin totta, ja tästä syystä: AMD-prosessoreissa on lisäohjeita, niin sanottu XOP-laajennus, ja tässä lisäohjesarjassa on niitä, jotka yksinkertaistavat huomattavasti ohjeiden toteutusta. GOST-algoritmi.

Tämä viittaa tavujen loogisen pakettisiirron ja kaksoissanojen pakettisyklisen siirron komentoihin. Liitteiden 3 ja 4 esimerkeissä käytetään universaaleja komentoja, jotka toteuttavat tarvittavan muunnoksen: ensimmäisessä tapauksessa yksi "ylimääräinen" komento ja toisessa tapauksessa neljä ylimääräistä komentoa kerralla. Optimointivaroja on siis ja niitä on huomattavia.

Jos puhumme lisäoptimoinnista, kannattaa muistaa 256-bittisten rekisterien (YMM-rekisterien) olemassaolo, joiden avulla voit teoriassa kaksinkertaistaa laskennan nopeuden. Mutta toistaiseksi tämä on vain mahdollisuus, tällä hetkellä prosessorit hidastavat paljon suorittaessaan 256-bittisiä ohjeita (FPU:iden polun leveys on 128 bittiä). Kokeet ovat osoittaneet, että nykyaikaisissa prosessoreissa 16 säikeen lukumäärä YMM-rekistereissä ei anna mitään voittoa. Mutta tämä on vain toistaiseksi, uusissa prosessorimalleissa 256-bittisten käskyjen nopeus epäilemättä kasvaa, ja sitten 16 rinnakkaisen säikeen käyttö tulee tarkoituksenmukaiseksi ja johtaa salausprosessin nopeuden vieläkin suurempaan nousuun.

Teoriassa voit laskea 600-700 megatavun sekuntinopeudeksi, jos prosessorissa on kaksi FPU:ta, joiden työpolun leveys on 256 bittiä. Tässä tapauksessa voimme puhua koodin kirjoittamisesta tehokkuudella 16 RTT, ja tämä ei ole fantasiaa, vaan lähitulevaisuutta.

sekoitettu tila

Jälleen herää kysymys rekisterien lukumäärästä, ne eivät riitä edistämään tällaista algoritmia. Mutta hyperkaupankäyntitila auttaa meitä. Prosessoriytimessä on toinen joukko rekistereitä, jotka ovat käytettävissä loogisessa prosessoritilassa. Siksi suoritamme saman koodin kahdella loogisella prosessorilla kerralla. Tässä tilassa meillä ei tietenkään ole enempää executive-laitteita, mutta vuorottelun ansiosta voimme saada täyden kuorman kaikkia executive-laitteita.

Tässä ei voi luottaa 50 %:n kasvuun, pullonkaula on välimuisti, johon tekniset maskit tallennetaan, mutta voit silti saada 100 megatavua lisäystä. Tätä vaihtoehtoa ei ole lueteltu liitteissä (makrot ovat samat kuin 8 RTT-koodissa), mutta se löytyy ohjelmatiedostoista. Joten jos joku ei usko mahdollisuuteen salata 500 megatavua sekunnissa yhdellä prosessoriytimellä, anna hänen suorittaa testitiedostot. Siellä on myös kommentteja sisältäviä tekstejä, jotta kukaan ei usko, että olen ovela.

Tämä keskittyminen on mahdollista vain Intel-prosessoreissa, AMD:llä on vain kaksi FPU:ta kahta prosessorimoduulia kohden (analogisesti hyper-trading-tilassa). Mutta on vielä neljä ALU:ta, joita on synti olla käyttämättä.

Voit ohjata Bulldozerin prosessorimoduulit hyperkaupankäyntimoodin kaltaiseen tilaan, mutta suorittaa muunnoksen RON:ksi eri moduuleissa yhdessä säikeessä ja SSE-rekistereiksi toisessa säikeessä ja saat saman 12 RTT:n. En ole testannut tätä vaihtoehtoa, mutta uskon, että 12 RTT:n koodi toimii tehokkaammin AMD:llä. Halukkaat voivat kokeilla, testiohjelmat voidaan säätää toimimaan "Bulldozereissa" melko helposti.

Kuka sitä tarvitsee?

Vakava kysymys, mutta siihen on yksinkertainen vastaus - kaikki tarvitsevat sitä. Pian istumme kaikki alas pilvien päälle, tallennamme sinne sekä dataa että ohjelmia, ja sinne, oi kuinka haluatte varustaa oman, yksityisen kulman. Tätä varten sinun on salattava liikenne, ja kryptomuunnoksen nopeus on tärkein määräävä tekijä mukavassa pilvityössä. Salausalgoritmivalikoimamme on pieni - joko GOST tai AES.

Lisäksi, kummallista kyllä, prosessoreihin sisäänrakennettu AES-algoritmin salaus osoittautuu paljon hitaammaksi, testit osoittavat nopeuden 100-150 megatavua sekunnissa, ja tämä tapahtuu algoritmin laitteistototeutuksen kanssa! Ongelmana on yksisäikeinen laskeminen ja korvaava lohko, joka toimii tavuilla (taulukko 256 riviä). Joten GOST osoittautuu tehokkaammaksi toteutettaessa x86 / 64 -arkkitehtuuria, kuka olisi uskonut ...

Tämä on jos puhumme saavutetusta salausnopeuden tasosta. Ja jos pidämme mielessä teoreettiset tarkennukset koodin tehokkuuden parantamisen alalla, niin todennäköisesti kukaan ei tarvitse sitä. Tasojen 3–6 RTT:n asiantuntijoita ei käytännössä ole, kääntäjät generoivat yleensä koodin tasolla 1–2,5 RTT, ja suurin osa ohjelmoijista ei tunne assembleria, ja jos he tuntevat sen oikeinkirjoituksen, he eivät ymmärrä sen laitetta. moderni prosessori. Ja ilman tätä tietämystä, mikä on assembler, mikä on jonkinlainen SI-sharp - sillä ei ole väliä.

Mutta kaikki ei ole niin surullista: "alarivillä" viikon unettomien öiden jälkeen on uusi algoritmi GOSTin toteuttamiseksi, jota on synti olla patentoimatta. Ja patenttihakemukset (jopa kolme) on jo laadittu ja jätetty, joten herrat, liikemiehet, riviin - naiset ja lapset saavat alennusta.

). Samaan aikaan tätä algoritmia koskevien muistiinpanojen määrä venäläisissä tiedotusvälineissä ja venäläisten käyttäjien blogeissa kasvaa: molemmat kattavat venäläistä standardia vastaan ​​tehtyjen hyökkäysten tulokset vaihtelevalla luotettavuudella ja sisältävät mielipiteitä sen toiminnallisista ominaisuuksista. Näiden muistiinpanojen kirjoittajat (ja siten myös lukijat) saavat usein vaikutelman, että kotimainen salausalgoritmi on vanhentunut, hidas ja siinä on haavoittuvuuksia, jotka tekevät siitä paljon herkemmän hyökkäyksille kuin ulkomaiset salausalgoritmit, joilla on samanlainen avaimen pituus. Tällä muistiinpanosarjalla haluamme kertoa ymmärrettävässä muodossa Venäjän standardin nykytilasta. Ensimmäinen osa kattaa kaikki kansainvälisen salausyhteisön tuntemat hyökkäykset GOST 28147-89:ää vastaan, tämänhetkiset arviot sen vahvuudesta. Tulevissa julkaisuissa pohditaan myös yksityiskohtaisesti standardin ominaisuuksia tehokkaiden toteutusten rakentamisen mahdollisuudesta.

Nicolas Courtois - "suuri ja kauhea"

Aloitetaan tarinalla Nicolas Courtoisin toiminnasta, joka on kirjoittanut koko sarjan venäläistä lohkosalausstandardia ().

Lokakuussa 2010 aloitettiin prosessi GOST 28147-89 -algoritmin sisällyttämiseksi kansainväliseen standardiin ISO/IEC 18033-3. Jo toukokuussa 2011 kuuluisan kryptografin Nicolas Courtois'n artikkeli ilmestyi ePrint-sähköiseen arkistoon, jota leimaa erittäin moniselitteinen asenne häntä kohtaan maailman kryptografiyhteisössä. Courtois'n julkaisut ovat surullinen esimerkki käsitteiden manipuloinnista, joka ei paljasta kohteen uusia ominaisuuksia, mutta väittäen sensaatioon provosoi virheellisten mielipiteiden leviämistä sen todellisista ominaisuuksista epäpätevässä ympäristössä.

Algebrallinen menetelmä

Courtois'n päättely rakentuu kahden kryptoanalyysimenetelmien luokan ympärille: algebralliset menetelmät ja differentiaalimenetelmät. Harkitse ensimmäistä menetelmäluokkaa.

Yksinkertaistetusti algebrallisen kryptaanalyysin menetelmää voidaan kuvata suuren yhtälöjärjestelmän kokoamiseksi ja ratkaisemiseksi, jonka jokainen ratkaisu vastaa kryptanalyytikon tavoitetta (esim. jos järjestelmä on käännetty yhdellä parilla selväteksti ja salateksti, silloin kaikki tämän järjestelmän ratkaisut vastaavat avaimia, joilla tämä selväteksti muunnetaan tietyksi salatuksi). Toisin sanoen lohkosalauksen kryptausanalyysin ongelman tapauksessa salausanalyysin algebrallisen menetelmän ydin on, että avain löydetään polynomiyhtälöjärjestelmän ratkaisemisen tuloksena. Suurin vaikeus on pystyä muodostamaan mahdollisimman yksinkertainen järjestelmä ottaen huomioon tietyn salauksen ominaisuudet, jotta sen ratkaiseminen vie mahdollisimman vähän aikaa. Tässä avainrooli on kunkin tietyn analysoitavan salauksen ominaisuudet.

Courtoisin käyttämää algebrallista menetelmää voidaan kuvata lyhyesti seuraavasti. Ensimmäisessä vaiheessa tällaisia ​​GOST 28147-89:n ominaisuuksia käytetään kiinteän pisteen olemassaolona osalle salausmuunnosta sekä niin kutsuttuna heijastuspisteenä. Näistä ominaisuuksista johtuen useita pareja valitaan riittävän suuresta määrästä avoimen salatekstin pareja, jolloin voimme tarkastella muunnoksia ei 32:ssa, vaan vain 8 kierroksella. Toinen vaihe koostuu siitä, että ensimmäisessä vaiheessa saatujen 8-kierrosten muunnosten tulosten perusteella muodostetaan epälineaarinen yhtälöjärjestelmä, jossa avainbittejä ovat tuntemattomat. Tämä järjestelmä on sitten ratkaistu (tämä kuulostaa yksinkertaiselta, mutta on itse asiassa menetelmän aikaavievin osa, koska järjestelmä koostuu epälineaarisista yhtälöistä).

Kuten edellä todettiin, missään työssä ei ole yksityiskohtaista kuvausta ja analyysiä avaimen määrittämisen toisen ja päävaiheen monimutkaisuudesta. Toisen vaiheen monimutkaisuus määrää koko menetelmän monimutkaisuuden. Sen sijaan kirjoittaja antaa pahamaineisia "faktoja", joiden perusteella hän tekee arvioita työvoimaintensiteetistä. Näiden "faktien" sanotaan perustuvan kokeellisiin tuloksiin. Kotimaisten kirjailijoiden teoksissa on analyysi Courtoisin työstä kokonaisuudessaan. Tämän työn kirjoittajat huomauttavat, että monet Courtois'n "faktaista", jotka esitettiin ilman todisteita, osoittautuivat vääriksi kokeellisen tarkastuksen aikana. Artikkelin kirjoittajat menivät pidemmälle ja analysoivat Courtoisin osalta toisen vaiheen monimutkaisuutta perusteltujen algoritmien ja arvioiden avulla. Tuloksena saadut arviot monimutkaisuudesta osoittavat esitetyn hyökkäyksen täydellisen soveltumattomuuden. Kotimaisten tekijöiden lisäksi työssä havaittiin muun muassa ne suuret ongelmat, joita Courtoisilla on menetelmiensä arvioiden ja perustelun kanssa.

Differentiaalinen menetelmä

Tarkastellaan toista Courtois'n menetelmää, joka perustuu differentiaaliseen kryptausanalyysiin.

Yleinen differentiaalisen krypta-analyysin menetelmä perustuu salausprimitiivissä käytettävien epälineaaristen kuvausten ominaisuuksien hyödyntämiseen, jotka liittyvät avaimen arvon vaikutukseen näiden tulo- ja lähtöarvoparien välisiin riippuvuuksiin. kartoituksia. Kuvataanpa lohkosalauksen differentiaalisen kryptografisen analyysin pääideaa. Yleensä lohkosalaukset muuntavat syötetiedot vaiheittain käyttämällä useita ns. pyöreitä muunnoksia, ja jokainen kierrosmuunnos ei käytä koko avainta, vaan vain osaa siitä. Harkitse hieman "katkaistua" salausta, joka eroaa alkuperäisestä siinä, että sillä ei ole viimeistä kierrosta. Oletetaan, että on todettu, että salaamalla kaksi selkotekstiä, jotka eroavat joissakin kiinteissä paikoissa käyttämällä tällaista "katkaistua" salausta, saadaan suurella todennäköisyydellä salatekstejä, jotka eroavat myös joissain kiinteissä paikoissa. Tämä ominaisuus osoittaa, että "katkaistu" salaus jättää erittäin todennäköisesti riippuvuuden joidenkin selkeiden tekstien ja niiden salauksen tulosten välille. Jotta osa avaimesta voidaan palauttaa käyttämällä tätä ilmeistä virhettä, on välttämätöntä kyetä salaamaan ennalta valitut selkeät tekstit avaimella, jonka haluamme palauttaa (ns. "valittu selväkielihyökkäys"). Avaimen avausmenettelyn alussa luodaan satunnaisesti useita selkeitä tekstipareja, jotka eroavat samoista kiinteistä paikoista. Kaikki tekstit on salattu "täydellä" salauksella. Saatuja salatekstipareja käytetään palauttamaan ne avainbitit, joita käytetään viimeisen kierroksen muunnoksessa seuraavasti. Avaimen vaadittujen bittien jonkin satunnaisesti valitun arvon avulla kaikkiin salateksteihin sovelletaan muunnos, käänteinen viimeiselle kierrokselle. Itse asiassa, jos arvasimme avainbittien halutun arvon, saamme "katkaistun" salauksen tuloksen, ja jos emme arvannut, "salaamme tiedot vielä enemmän", mikä vain vähentää edellä mainittujen lohkojen välinen riippuvuus (ero joissakin kiinteissä asennoissa). Toisin sanoen, jos tällaisen salatekstien "lisäkäsittelyn" tulosten joukossa oli melko paljon pareja, jotka eroavat kiinteissä paikoissa tiedossamme, niin tämä tarkoittaa, että olemme arvaaneet tarvittavat avainbitit. Muuten tällaisia ​​pareja on huomattavasti vähemmän. Koska kullakin kierroksella käytetään vain osaa avaimesta, etsittävät bitit (eli viimeisellä kierroksella käytetyt näppäinbitit) eivät ole yhtä monta kuin täyden avaimen bittejä ja ne voidaan yksinkertaisesti iteroida toistamalla yllä olevat vaiheet. Tässä tapauksessa törmäämme varmasti jonain päivänä oikeaan arvoon.

Yllä olevasta kuvauksesta seuraa, että tärkeintä differentiaalianalyysimenetelmässä ovat selkotekstien ja salatekstien juuri niiden paikkojen lukumäärät, joiden eroilla on keskeinen rooli avainbittien palauttamisessa. Näiden paikkojen perustavanlaatuinen läsnäolo sekä niiden numeroiden joukko riippuu suoraan niiden epälineaaristen muunnosten ominaisuuksista, joita käytetään missä tahansa lohkosalauksessa (yleensä kaikki "epälineaarisuus" keskittyy ns. -laatikot tai korvaussolmut).

Courtois käyttää hieman muokattua versiota differentiaalimenetelmästä. Huomaamme välittömästi, että Courtois tekee analyysinsä S-laatikoista, jotka eroavat nykyisistä ja ISO:ssa ehdotetuista. Paperissa esitetään eroominaisuudet (niin ne numerot, joissa lohkojen tulisi erota) pienelle määrälle kierroksia. Syitä tilastojen laajentamiselle useammille kierroksille perustuu, kuten tavallista, "faktoihin". Courtois ilmaisee jälleen pelkällä auktoriteetilla perusteettoman oletuksen, jonka mukaan S-laatikoiden vaihtaminen ei vaikuta GOST 28147-89:n kestävyyteen sen hyökkäyksiä vastaan ​​(samaan aikaan tuntemattomista syistä S-laatikot ensimmäisestä toiminnasta lähtien standardin ISO/IEC 18033-3 lisäyksen luonnosta ei ole otettu huomioon). Artikkelin tekijöiden suorittama analyysi osoittaa, että vaikka otamme Courtoisin perusteettomat "faktat" uskoon ja analysoimme GOST 28147-89:ää muiden S-laatikoiden kanssa, hyökkäys ei jälleen osoittautunut paremmaksi kuin täydellinen luettelointi.

Courtois'n teosten yksityiskohtainen analyysi ja yksityiskohtainen perustelu kaikkien venäläisen standardin vakauden heikkenemistä koskevien väitteiden perusteettomuudelle suoritettiin [ , ].

Samaan aikaan jopa Courtois itse tunnustaa laskelmien täydellisen epätarkkuuden! Seuraava dia on otettu Courtoisin esityksestä FSE 2012 Short Announcement -osiossa.

On huomattava, että myös ulkomaiset tutkijat kritisoivat Courtoisin teoksia toistuvasti. Esimerkiksi hänen työnsä hyökkäysten rakentamisesta AES-lohkosalausalgoritmia vastaan ​​XSL-menetelmällä sisälsi samat perustavanlaatuiset puutteet kuin venäläisen standardin analyysi: suurin osa työvoimaintensiteetin arvioista esiintyy tekstissä täysin perusteettomina ja perustelemattomina - yksityiskohtaista kritiikkiä löytyy esimerkiksi työstä . Lisäksi Courtois itse tunnustaa laajat kieltäytymiset julkaista hänen töitään suurissa kryptografisissa konferensseissa ja vakiintuneissa vertaisarvioiduissa aikakauslehdissä, jättäen hänelle usein vain mahdollisuuden puhua lyhyessä ilmoitusosiossa. Tämä voidaan lukea esimerkiksi teoksen luvusta 3. Tässä on joitain Courtoisin itsensä lainaamia ja hänen työhönsä liittyviä lainauksia:

• "Uskon, että Asiacryptin yleisö ei koe sitä kiinnostavana." Asiacrypt 2011 arvostelija.
• "...on iso, iso, iso ongelma: tämä hyökkäys, joka on lehden tärkein panos, on jo julkaistu FSE'11:ssä (se oli jopa paras lehti)...". Crypto Reviewer 2011.

Kansainvälisen kryptografisen yhteisön ammatillinen osa suhtautuu siten Courtoisin työn laatuun yhtä epäilevästi kuin esimerkiksi joidenkin venäläisten asiantuntijoiden lausunnot heidän kyvystään murtaa AES 2 100:lla tai seuraavat "todisteet" kahdella sivulla. hypoteesi, jota ei ole vahvistettu millään johdonmukaisilla laskelmilla.. monimutkaisuusluokkien P ja NP epätasa-arvosta.

Isobe ja Dinur-Dunkelman-Shamir hyökkäävät

Isobe-hyökkäysten () ja Dinur-Dankelman-Shamir (jäljempänä: DDSH-hyökkäys) () yleinen idea on rakentaa tietylle (avainriippuvaiselle) kapealle selkotekstien joukolle muunnosvastine tälle joukolle, jolla on yksinkertaisempi rakenne kuin itse salausmuunnos. Isobe-menetelmän tapauksessa tämä on joukko 64-bittisiä lohkoja x siten, että F 8 -1 (Swap(F 8 (z))) = z, missä z = F 16 (x) - F 8 ( x) ja F 16 (x) ovat ensimmäiset 8 ja 16 ensimmäistä salauskierrosta GOST 28147-89, vastaavasti Swap-toiminnolla - 64-tavuisen sanan puoliskojen vaihtamisella. Kun selkeä teksti pääsee tähän joukkoon, GOST 28147-89:n täyden 32 kierroksen muunnoksen tulos osuu yhteen 16 kierroksen tuloksen kanssa, jota hyökkäyksen kirjoittaja käyttää hyväkseen. DDS-menetelmän tapauksessa tämä on x:n joukko siten, että F 8 (x) = x (muunnoksen F 8 kiinteä piste). GOST 28147-89 -muunnos toimii täsmälleen samalla tavalla kuin sen 8 viimeistä kierrosta, mikä yksinkertaistaa analyysiä.

Isobe-hyökkäyksen monimutkaisuus on 2224 salausoperaatiota, LDS-hyökkäys on 2192. Kaikki kysymykset siitä, aiheuttavatko Isobe- ja DDSH-hyökkäykset uusia rajoituksia algoritmimme käyttöedellytyksiin, poistetaan kuitenkin arvioimalla kunkin hyökkäyksen suorittamiseen tarvittavan materiaalin vaatimukset: Isobe-menetelmä vaatii 2 32 paria selkeää tekstiä ja salatekstejä ja DDSH - 2 -menetelmälle 64 . Tällaisten materiaalimäärien käsittely ilman avainta vaihtamatta on ennakolta mahdotonta hyväksyä millekään lohkosalaukselle, jonka lohkon pituus on 64: materiaalilla, jonka tilavuus on 2 32 , kun otetaan huomioon syntymäpäivien ongelma (katso esimerkiksi tunkeilijalle) kyky tehdä tiettyjä johtopäätöksiä selkeistä teksteistä salateksteistä ilman avaimen määrittämistä. Samalla avaimella saatujen 264 avoimen ja salatun tekstin parin läsnäolo mahdollistaa itse asiassa vihollisen suorittaa salaus- ja salauksenpurkutoimia tietämättä tätä avainta ollenkaan. Tämä johtuu puhtaasti kombinatorisesta ominaisuudesta: vastustajalla on tässä tapauksessa koko salausmuunnostaulukko. Tämä tilanne on täysin mahdoton hyväksyä minkään kohtuullisen toimintavaatimuksen mukaisesti. Esimerkiksi CryptoPro CSP:ssä on tekninen rajoitus salatun (ilman avaimen muuntamista) materiaalin määrälle 4 Mt (katso). Siten tiukka kielto käyttää avainta tällaisen tilavuuden materiaalissa on luontainen kaikille lohkosalauksille, joiden lohkon pituus on 64 bittiä, ja siksi Isobe- ja DDSH-hyökkäykset eivät millään tavalla kavenna käyttöaluetta. GOST 28147-89 -algoritmista säilyttäen samalla suurimman mahdollisen suojauksen 2256 .

Tietenkin on huomattava, että tutkijat (Isobe ja Dinur-Dankelman-Shamir) osoittivat, että jotkin GOST 28147-89 -algoritmin ominaisuudet mahdollistavat analyysipolkujen löytämisen, joita algoritmin luojat eivät ottaneet huomioon. Avainaikataulun yksinkertainen muoto, joka yksinkertaistaa huomattavasti tehokkaiden toteutusten rakentamista, mahdollistaa myös yksinkertaisempien kuvausten rakentamisen algoritmin suorittamista muunnoksista joillekin harvinaisille avaimien ja selkotekstien tapauksille.

Työ osoittaa, että tämä algoritmin negatiivinen ominaisuus voidaan helposti eliminoida säilyttämällä toimintaominaisuudet täysin, mutta valitettavasti se on kiinteä osa algoritmia yleisesti käytetyssä muodossaan.

Huomaa, että tiettyjä laiminlyöntejä keskimääräisen työpanoksen arvioissa on myös Dinurin, Dankelmanin ja Shamirin työssä. Siten hyökkäystä rakennettaessa ei kiinnitetä asianmukaista huomiota seuraavaan kohtaan: merkittävälle osalle näppäimistä selkeiden tekstien joukko x, jolloin F 8 (x) = x, on tyhjä: 8 muunnoskierrosta ei välttämättä yksinkertaisesti onnistu. on kiinteitä pisteitä. Kiinteiden pisteiden olemassaolo riippuu myös korvaavien solmujen valinnasta. Siten hyökkäys koskee vain tiettyjä korvaavia solmuja ja avaimia.

On myös syytä mainita vielä yksi työ, jossa on hyökkäys GOST 28147-89:ää vastaan. Helmikuussa 2012 artikkelin päivitetty versio (päivätty marraskuussa 2011) ilmestyi kansainvälisen salausyhdistyksen ePrint-sähköiseen arkistoon, joka sisälsi uuden hyökkäyksen GOST 28147-89:ää vastaan. Esitetyn hyökkäyksen ominaisuudet ovat seuraavat: materiaalin tilavuus on 232 (kuten Isoben) ja työvoimaintensiteetti on 2192 (kuten DDSh:lla). Siten tämä hyökkäys paransi ennätysmäisen LDS-hyökkäyksen materiaalimäärän suhteen 2 64:stä 2 32:een. Huomaamme erikseen, että kirjoittajat esittivät rehellisesti kaikki laskelmat materiaalin monimutkaisuuden ja tilavuuden perustella. Yhdeksän kuukauden kuluttua yllä olevista laskelmista löytyi perustavanlaatuinen virhe, ja marraskuusta 2012 lähtien sähköisen arkiston artikkelin päivitetty versio ei enää sisällä tuloksia kotimaisesta algoritmista.

Hyökkäykset perustuvat olettamukseen, että hyökkääjä tietää "jotain" avaimista

Lopuksi huomautamme, että kirjallisuudessa on myös useita teoksia (katso esimerkiksi ja ), jotka on omistettu hyökkäyksille GOST 28147-89:ää vastaan ​​niin sanotussa mallissa linkitetyillä avaimilla. Tämä malli sisältää pohjimmiltaan oletuksen tunkeilijan mahdollisuudesta päästä analysointia varten halutulla avaimella avoimien ja salattujen tekstien pareihin, mutta myös avoimien ja salattujen tekstien pareihin, jotka on saatu käyttämällä (myös tuntemattomia) avaimia, jotka eroavat avaimista. etsitty tunnettu säännöllinen tapa (esimerkiksi kiinteissä bittipaikoissa). Tässä mallissa on todellakin mahdollista saada mielenkiintoisia tuloksia GOST 28147-89:stä, mutta tässä mallissa yhtä vahvoja tuloksia voidaan saada esimerkiksi AES-standardista, joka on yleistynyt nykyaikaisissa julkisissa verkoissa (katso , esimerkiksi,). Huomaa, että ehdot tällaisten hyökkäysten suorittamiselle syntyvät, kun salausta käytetään tietyssä protokollassa. On huomattava, että tällaiset tulokset, vaikka ne ovatkin kiistatta akateemista mielenkiintoa kryptografisten muunnosten ominaisuuksien tutkimisen kannalta, eivät itse asiassa sovellu käytännössä. Esimerkiksi kaikki Venäjän FSB:n sertifioimat kryptografisten tietojen suojaustyökalut täyttävät tiukimmatkin salausavainten luontijärjestelmien vaatimukset (katso esim.). Kuten analyysin tuloksista käy ilmi, 18 linkitetyn avaimen ja 2 10 avoimen ja salatun tekstilohkon parin läsnä ollessa yksityisen avaimen täydellisen avaamisen monimutkaisuus onnistumisen todennäköisyydellä 1-10 -4 2 26 . Kuitenkin, jos yllä olevat vaatimukset avainmateriaalin kehittämiselle täyttyvät, tällaisten avainten löytämisen todennäköisyys on 2 -4352, eli 24096 kertaa pienempi kuin jos yrität vain arvata salaisen avaimen ensimmäisellä kerralla.

Linkitetyillä avaimilla varustettuun malliin liittyviin töihin kuuluu myös vuonna 2010 paljon melua aiheuttanut työ venäläisissä sähköisissä julkaisuissa, jotka eivät kärsi tottumuksesta tarkastaa materiaalia huolellisesti jahtaaessaan sensaatioita. Siinä esitettyjä tuloksia ei tuettu millään tiukalla perustelulla, mutta ne sisälsivät äänekkäitä lausuntoja mahdollisuudesta hakkeroida Venäjän federaation valtion standardi heikkoon kannettavaan tietokoneeseen muutamassa sekunnissa - yleensä artikkeli kirjoitettiin parhaiden perinteiden mukaisesti Nicolas Courtois'sta. Mutta huolimatta tieteellisten julkaisujen perusperiaatteet enemmän tai vähemmän tutusta lukijalle täysin itsestään selvästä, artikkelin perusteettomuudesta, juuri Venäjän yleisön vakuuttamiseksi, että Rudski kirjoitti teoksen jälkeen yksityiskohtaisen ja yksityiskohtaisen tekstin, joka sisälsi kattava analyysi tästä puutteesta. Artikkeli, jolla on puhuva otsikko "Teoksen nollasta käytännön merkityksestä "Avainpalautushyökkäys koko GOST-lohkosalaukseen ilman aikaa ja muistia"" perustelee sitä tosiasiaa, että menetelmässä esitetyn menetelmän keskimääräinen monimutkaisuus ei ole pienempi kuin täydellisen luettelon monimutkaisuus.

Kuiva jäännös: mikä on resistanssi käytännössä?

Lopuksi esitämme taulukon, joka sisältää tiedot kaikista kansainvälisen kryptografisen yhteisön tiedossa olevien tiukasti kuvattujen ja perusteltujen GOST 28147-89 -hyökkäysten tuloksista. Huomaa, että monimutkaisuus on annettu GOST 28147-89 -algoritmin salaustoiminnoissa ja muisti ja materiaali on määritelty algoritmin lohkoissa (64 bittiä = 8 tavua).

Hyökkäys	Työvoiman intensiteetti	Muisti	Tarvittava materiaali
Isobe	2 224	2 64	2 32
Dinur-Dunkelman-Shamir, FP, 2DMitM	2 192	2 36	2 64
Dinur-Dunkelman-Shamir, FP, heikko muisti	2 204	2 19	2 64
	2 224	2 36	2 32
Dinur-Dunkelman-Shamir, Heijastus, 2DMitM	2 236	2 19	2 32
raaka voima	2 256	1	4
Nanosekuntien määrä universumin alusta	2 89

Huolimatta melko laajasta tutkimussyklistä GOST 28147-89 -algoritmin turvallisuuden alalla, tällä hetkellä ei ole tiedossa yhtään hyökkäystä, jonka toteuttamisen edellytykset olisivat saavutettavissa mukana tulevalla 64 bitin lohkopituudella. toimintavaatimuksista. Salauksen parametreista (avaimen bittipituus, lohkon bittipituus) johtuvat rajoitukset yhdellä avaimella käsiteltävän materiaalin määrälle ovat huomattavasti tiukemmat kuin minkä tahansa suorituksen suorittamiseen tarvittava vähimmäismäärä. tällä hetkellä tunnetuista hyökkäyksistä. Siksi, kun olemassa olevat toiminnalliset vaatimukset täyttyvät, mikään tähän mennessä ehdotetuista GOST 28147-89 -kryptausanalyysimenetelmistä ei salli avaimen määrittämistä, joka on vähemmän työlästä kuin tyhjentävä haku.

Maassamme yhtenäinen algoritmi tietojen salauskuvaukselle tietojenkäsittelyjärjestelmille tietokoneverkoissa, yksittäisissä tietokonejärjestelmissä ja tietokoneissa, jonka määrää GOST 28147-89.

Tämä salaustietojen muunnosalgoritmi on 64-bittinen lohkoalgoritmi 256-bittisellä avaimella, suunniteltu laitteisto- ja ohjelmistototeutukseen, täyttää kryptografiset vaatimukset eikä rajoita suojattavan tiedon salassapitoastetta.

Algoritmia kuvattaessa käytetään seuraavaa merkintää:

L ja R ovat bittisarjoja;
LR on sekvenssien L ja R ketju, jossa sekvenssin R bitit seuraavat sekvenssin L bittejä;
(+) - bittikohtainen lisäys modulo 2 ("yksinomainen TAI"-toiminto);
[+] - 32-bittisten lukujen yhteenlasku modulo 2 32 ;
(+) - 32-bittisten lukujen yhteenlasku modulo 2 32 -1.

Luvut lasketaan yhteen seuraavan säännön mukaan:

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

Algoritmi tarjoaa neljä toimintatilaa:

Joka tapauksessa datan salaamiseen käytetään 256-bittistä avainta K, joka esitetään kahdeksana 32-bittisenä aliavaimana K i:

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

Salauksen purku suoritetaan samalla avaimella kuin salaus, mutta tämä prosessi on käänteinen tietojen salausprosessille.

Helppo vaihtotila

Ensimmäinen ja helpoin tila - korvaus. Salattava data on jaettu 64-bittisiin lohkoihin. Avoimen datalohkon T0 salausproseduuri sisältää 32 jaksoa (j=1...32).

Lohko T0 on jaettu kahteen 32-bitin sekvenssiin: B(0)A(0), jossa B(0) ovat vasen tai eniten merkitsevä bitti, A(0) ovat oikeat tai vähiten merkitsevät bitit.

Nämä sekvenssit syötetään asemiin N 1 ja N 2 ennen ensimmäisen salausjakson alkua.

64-bittisen datalohkon salausmenettelyn ensimmäinen jakso (j=1) kuvataan seuraavilla kaavoilla:

Tässä i tarkoittaa iteraationumeroa (i = 1, 2,..., 32).

Funktiota f kutsutaan salausfunktioksi. Sen argumentti on edellisessä iteraatiovaiheessa saadun luvun A(i) ja avaimen luvun X(j) summa modulo 2 32 (kunkin näistä luvuista on 32 numeroa).

Salaustoiminto sisältää kaksi operaatiota tuloksena olevalle 32-bittiselle summalle. Ensimmäistä operaatiota kutsutaan substituutioksi K. Korvauslohko K ​​koostuu kahdeksasta korvaussolmusta K(1) ... K(8), joissa kussakin on 64 bitin muisti. Korvauslohkoon saapuva 32-bittinen vektori jaetaan kahdeksaan peräkkäiseen 4-bittiseen vektoriin, joista jokainen muunnetaan 4-bittisiksi vektoriksi vastaavalla korvaussolmulla, joka on taulukko, jossa on 16 kokonaislukua välillä 0. .15.

Tulovektori määrittää sen taulukon rivin osoitteen, jonka numero on lähtövektori. 4-bittiset lähtövektorit yhdistetään sitten peräkkäin 32-bittiseksi vektoriksi. Korvauslohkotaulukko K sisältää tietoverkolle yhteisiä ja harvoin muuttuvia avainelementtejä.

Toinen operaatio on 32-bittisen vektorin syklinen siirto vasemmalle, joka saadaan korvaamalla K. 64-bittinen salattu datalohko Tw esitetään muodossa Tw =A(32)B(32).

Loput avoimet datalohkot yksinkertaisessa korvaustilassa salataan samalla tavalla.

Muista, että yksinkertaista vaihtotilaa voidaan käyttää tietojen salaukseen vain rajoitetuissa tapauksissa. Näihin tapauksiin kuuluu avaimen luominen ja sen salaus jäljitelmäsuojauksella (suojaus väärien tietojen määräämistä vastaan) tiedonsiirtokanavien kautta tapahtuvaa siirtoa tai tietokoneen muistiin tallentamista varten.

Gamma-tila

Avoin data, joka on jaettu 64-bittisiin lohkoihin T(i) (i=1, 2,..., m, missä m määräytyy salatun tiedon määrän mukaan), salataan gammatilassa bittikohtaisella lisäyksellä modulo 2 salausgamma Гw, joka tuotetaan 64-bittisinä lohkoina, eli Гw = (Г(1),Г(2),...,Г(i),...,Г(m)).

Datan salausyhtälö gammatilassa voidaan esittää seuraavasti:

W(i) = A (Y(i-1) [+] C2, Z(i-1) (+) C1) (+) T(i) = G(i) (+) T(i) .
Tässä W(i) on 64-bittinen salatekstilohko,
A - salaustoiminto yksinkertaisessa korvaustilassa (tämän funktion argumentit ovat kaksi 32-bittistä numeroa),
C1 ja C2 - GOST 28147-89:ssä määritellyt vakiot,
Y(i) ja Z(i) ovat suureita, jotka määritetään iteratiivisesti, kun gamma muodostuu seuraavasti:
(Y(0), Z(0)) = A(S), missä S on 64-bittinen binaarisekvenssi (synkronointiviesti);
(Y(i), Z(i)) = (Y(i-1) [+] C2, Z(i-1) (+) C1) arvolle i = 1, 2,...,m.

Tietojen salauksen purku on mahdollista vain, jos on olemassa synkronointiviesti, joka ei ole salauksen salainen elementti ja joka voidaan tallentaa tietokoneen muistiin tai lähettää viestintäkanavia pitkin salatun tiedon mukana.

Palaute gamma -tila

tila skaalaus palaute on hyvin samanlainen kuin gammatila. Kuten gammatilassa, avoin data, joka on jaettu 64-bittisiin lohkoihin T(i) (i=1, 2,..., m , missä m määräytyy salatun datan määrällä), salataan bittikohtaisella lisäyksellä modulo 2 gamma G sh -salauksella, joka tuotetaan 64-bittisinä lohkoina:

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

Lohkon T(m) bittien määrä voi olla pienempi kuin 64, kun taas se osa lohkon G(m) salauksen gammasta, jota ei käytetä salaukseen, hylätään.

Datan salausyhtälö gammatilassa palautetta käyttäen voidaan esittää seuraavasti:

Tässä W(i) on 64-bittinen salatekstilohko,
A - salaustoiminto yksinkertaisessa vaihtotilassa. Iteratiivisen algoritmin ensimmäisessä vaiheessa funktioargumentti on 64-bittinen synkronointiviesti ja kaikissa myöhemmissä vaiheissa - edellinen salatun datan lohko W(i-1).

Jäljitelmälisäkkeet

Kehitysprosessi jäljitelmäpinot on yhtenäinen mille tahansa tiedon salausmoodille.

Jäljitelmälisäys on p-bitin lohko (imitation insertion Ip), joka tuotetaan joko ennen koko viestin salausta tai rinnakkain lohkokohtaisen salauksen kanssa. Ensimmäiset avoimen datan lohkot, jotka ovat mukana lisäyssimulaation kehittämisessä, voivat sisältää palveluinformaatiota (esimerkiksi osoiteosan, ajan, synkronointiviestin) eivätkä olla salattuja. Parametrin p arvo (binäärinumeroiden lukumäärä simuloidussa lisäyksessä) määräytyy salausvaatimusten mukaan ottaen huomioon, että väärien häiriöiden aiheuttamisen todennäköisyys on 1/2^p.

Lisäysjäljitelmän saamiseksi avoin data esitetään 64-bittisinä lohkoina T(i) (i = 1, 2,..., m, missä m määräytyy salatun datan määrän mukaan). Ensimmäiselle avoimen datan lohkolle T(1) suoritetaan muunnos, joka vastaa salausalgoritmin 16 ensimmäistä jaksoa yksinkertaisessa korvausmoodissa. Lisäksi tietojen salaamiseen käytettyä avainta käytetään avaimena jäljitelmälisäyksen luomiseen.

16 työjakson jälkeen saatu 64-bittinen luku summataan modulo 2 toisen avoimen datalohkon T(2) kanssa. Summatulokseen kohdistetaan jälleen salausalgoritmin 16 ensimmäistä jaksoa vastaava muunnos yksinkertaisessa korvaustilassa. Tuloksena oleva 64-bittinen luku lisätään modulo 2 kolmanteen avoimeen datalohkoon T(3) ja niin edelleen. Viimeinen lohko T(m), joka on tarvittaessa pehmustettu täyteen 64-bittiseen lohkoon nollien kanssa, summataan modulo 2 työn tuloksella vaiheessa m-1, jonka jälkeen se salataan yksinkertaisessa korvaustilassa ensimmäiseen. 16 algoritmin sykliä. Vastaanotetusta 64-bittisestä luvusta valitaan segmentti Ip, jonka pituus on p bittiä.

Jäljitelmäliite Ip välitetään tietoliikennekanavaa pitkin tai tietokoneen muistiin salatun tiedon jälkeen. Saapuvan salatun tiedon salaus puretaan ja vastaanotetuista avoimen datan T(i) lohkoista muodostetaan jäljitelmälisäys Ip, jota sitten verrataan viestintäkanavalta tai tietokoneen muistista saatuun jäljitelmälisäkkeeseen IR. eivät täsmää, kaikki salatut tiedot katsotaan vääriksi.

Salausalgoritmi GOST 28147-89, sen käyttö ja ohjelmistototeutus Intel x86 -alustan tietokoneille.

Andrei Vinokurov

Algoritmin kuvaus.

Termit ja nimitykset.

Venäjän federaation salausstandardin kuvaus sisältyy erittäin mielenkiintoiseen asiakirjaan, jonka otsikko on "GOST 28147-89 Cryptographic Transformation Algorithm". Se, että sen otsikossa sanan "salaus" sijasta yleisempi käsite " kryptografinen muunnos ' ei ole sattumaa. Useiden läheisesti liittyvien salaustoimenpiteiden lisäksi dokumentissa kuvataan yksi generointialgoritmi jäljitelmät lisäkkeet . Jälkimmäinen ei ole muuta kuin kryptografinen ohjausyhdistelmä, eli koodi, joka on generoitu alkuperäisestä tiedosta salaisella avaimella jäljitelmäsuojaus tai suojaa tietoja luvattomilta muutoksilta.

GOST-algoritmien eri vaiheissa dataa, jolla ne toimivat, tulkitaan ja käytetään eri tavoin. Joissakin tapauksissa tietoelementtejä käsitellään itsenäisten bittien taulukoina, toisissa etumerkittömänä kokonaislukuna, toisissa monimutkaisena rakenteena, joka koostuu useista yksinkertaisemmista elementeistä. Siksi sekaannusten välttämiseksi on tarpeen sopia käytetystä merkinnästä.

Tämän artikkelin tietoelementit on merkitty isoilla latinalaisilla kirjaimilla ja kursiivilla (esim. X). kautta | X| ilmaisee tietoelementin koon X bitteinä. Jos siis tulkitsemme tietoelementin X ei-negatiivisena kokonaislukuna voimme kirjoittaa seuraavan epäyhtälön:

Jos tietoelementti koostuu useista pienempikokoisista elementeistä, tämä tosiasia ilmoitetaan seuraavasti: X=(X 0 ,X 1 ,…,X n –1)=X 0 ||X 1 ||…||X n-1. Proseduuria useiden tietoelementtien yhdistämiseksi yhdeksi kutsutaan ketjuttaminen tiedot ja se on merkitty symbolilla "||". Luonnollisesti tietoelementtien koolle tulee päteä seuraava suhde: | X|=|X 0 |+|X 1 |+…+|X n-1 |. Kun määritetään monimutkaisia ​​tietoelementtejä ja ketjutusoperaatiota, osatietoelementit luetellaan nousevassa tärkeysjärjestyksessä. Toisin sanoen, jos tulkitsemme yhdistelmäelementin ja kaikki siihen sisältyvät tietoelementit etumerkittämättöminä kokonaislukuina, voimme kirjoittaa seuraavan yhtälön:

Algoritmissa tietoelementti voidaan tulkita yksittäisten bittien joukoksi, jolloin bitit merkitään samalla kirjaimella kuin taulukko, mutta pienellä kirjaimella, kuten seuraavassa esimerkissä näkyy:

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

Jos siis kiinnitit huomiota, ns. numeroiden "little-endian" numerointi, ts. monibittisissä datasanoissa yksittäiset binäärinumerot ja niiden ryhmät pienemmillä numeroilla ovat vähemmän tärkeitä. Tämä on nimenomaisesti todettu standardin kohdassa 1.3: "Kun lisätään ja syklisesti siirretään binäärivektoreita, suurimmat bitit ovat suurilukuisten akkujen bitit." Edelleen standardin 1.4, 2.1.1 ja muut kappaleet määräävät, että virtuaalisen salauslaitteen tallennusrekisterit on alettava täyttää tiedoilla alemmista eli alemmista tiedoista. vähemmän merkittäviä rivejä. Täsmälleen sama numerointijärjestys on otettu käyttöön Intel x86 -mikroprosessoriarkkitehtuurissa, minkä vuoksi salauksen ohjelmistototeutus tässä arkkitehtuurissa ei vaadi ylimääräisiä bittien permutaatioita datasanojen sisällä.

Jos jokin operaatio suoritetaan dataelementeille, joilla on looginen merkitys, niin oletetaan, että tämä operaatio suoritetaan elementtien vastaaville biteille. Toisin sanoen A B=(a 0 b 0 ,a 1 b 1 ,…,a n –1 b n-1), missä n=|A|=|B|, ja symboli " " tarkoittaa mielivaltaista binaarista loogista toimintoa; viittaa yleensä operaatioon yksinomainen tai , joka on myös summausmoduulin 2 operaatio:

Salauksen rakentamisen logiikka ja GOST:n avaintietojen rakenne.

Jos tutkit huolellisesti alkuperäistä GOST 28147–89:ää, huomaat, että se sisältää kuvauksen useiden tasojen algoritmeista. Huipulla ovat käytännölliset algoritmit, jotka on suunniteltu salaamaan tietoryhmiä ja kehittämään niille väärennettyjä lisäyksiä. Ne kaikki perustuvat kolmeen alemman tason algoritmiin, joita kutsutaan tekstissä GOSTiksi syklit . Näihin perusalgoritmeihin viitataan tässä artikkelissa nimellä perussyklit erottamaan ne kaikista muista silmukoista. Niillä on seuraavat nimet ja nimitykset, viimeksi mainitut on annettu suluissa ja niiden merkitys selitetään myöhemmin:

• salausjakso (32-3);
• salauksenpurkujakso (32-P);
• jäljitelmälisäkkeen (16-Z) generointisykli.

Jokainen perussykli puolestaan ​​on yhden toimenpiteen moninkertainen toisto, jota tässä työssä vaaditaan lisää. kryptomuunnoksen tärkein vaihe .

Joten GOST:n ymmärtämiseksi sinun on ymmärrettävä seuraavat kolme asiaa:

• mitä on tapahtunut perusaskel kryptomuunnokset;
• miten perussyklit muodostuvat päävaiheista;
• kuin kolmesta perussyklit laske yhteen kaikki GOSTin käytännön algoritmit.

Ennen kuin jatkamme näiden asioiden tutkimista, meidän pitäisi puhua GOST-algoritmien käyttämistä keskeisistä tiedoista. Kirchhoff-periaatteen mukaisesti, jonka tyydyttävät kaikki nykyaikaiset suuren yleisön tuntemat salaukset, sen salassapito takaa salatun viestin salaisuuden. GOST:ssa avaintieto koostuu kahdesta tietorakenteesta. Lisäksi avain tarvitaan kaikille salakirjoille, se sisältää myös korvaustaulukko . Alla on GOSTin avainrakenteiden pääominaisuudet.

Kryptomuunnoksen päävaihe.

Pääasiallinen kryptomuunnosvaihe on olennaisesti operaattori, joka määrittelee 64-bittisen datalohkon muuntamisen. Tämän operaattorin lisäparametri on 32-bittinen lohko, jota käytetään minkä tahansa avaimen elementtinä. Pääaskelalgoritmin kaavio on esitetty kuvassa 1.

Kuva 1. Kaavio GOST 28147-89 -algoritmin kryptomuunnoksen päävaiheesta.

Alla on selitykset päävaihealgoritmista:

Vaihe 0

• N– 64-bittinen muunnettava datalohko, jonka vaiheen suorituksen aikana se on vähiten merkittävä ( N 1) ja vanhempi ( N 2) osia käsitellään erillisinä 32-bittisinä etumerkittöminä kokonaislukuina. Näin ollen voi kirjoittaa N=(N 1 ,N 2).
• X– 32-bittinen avainelementti;

Vaihe 1

Lisäys avaimella. Muunnetun lohkon alapuolikas lisätään modulo 2 32 vaiheessa käytetyllä avainelementillä, tulos siirretään seuraavaan vaiheeseen;

Vaihe 2

Lohkon vaihto. Edellisessä vaiheessa saatu 32-bittinen arvo tulkitaan kahdeksan 4-bittisen koodilohkon joukoksi: S=(S 0 , S 1 , S 2 , S 3 , S 4 , S 5 , S 6 , S 7), ja S 0 sisältää 4 pienintä ja S 7 - 4 tärkeintä bittiä S.

Seuraavaksi jokaisen kahdeksan lohkon arvo korvataan uudella, joka valitaan korvaustaulukosta seuraavasti: lohkon arvo Si muuttuu Si- peräkkäinen elementti (numerointi nollasta) i-korvaussolmun (ts. i-korvaustaulukon rivi, numerointi myös nollasta). Toisin sanoen lohkoarvon korvaamiseksi korvaustaulukosta valitaan elementti, jonka rivinumero on yhtä suuri kuin korvauslohkonumero ja sarakkeen numero, joka vastaa korvauslohkon arvoa 4-bittisenä ei-negatiivisena kokonaislukuna. Tästä selviää korvaustaulukon koko: siinä olevien rivien määrä on yhtä suuri kuin 4-bittisten elementtien lukumäärä 32-bittisessä tietolohkossa, eli kahdeksan, ja sarakkeiden lukumäärä on yhtä suuri kuin 4-bittisen datalohkon eri arvojen lukumäärä, jonka tiedetään olevan 2 4, kuusitoista.

Vaihe 3

Kierrä vasemmalle 11 bittiä. Edellisen vaiheen tulosta siirretään syklisesti 11 bittiä kohti korkeampia bittejä ja siirretään seuraavaan vaiheeseen. Algoritmikaaviossa symboli tarkoittaa argumenttinsa syklisen siirron funktiota 11 bittiä vasemmalle, ts. kohti korkeampia tasoja.

Vaihe 4

Bitittainen lisäys: Vaiheessa 3 saatu arvo lisätään modulo 2 bitti kerrallaan muunnettavan lohkon ylimpään puolikkaaseen.

Vaihe 5

Siirtyminen ketjua pitkin: muunnetun lohkon alaosa siirretään vanhemman paikalle ja edellisen vaiheen tulos asetetaan paikalleen.

Vaihe 6

Tuloksena oleva muunnettavan lohkon arvo palautetaan pääsalausmuunnosvaiheen algoritmin suorittamisen tuloksena.

Salausmuunnosten perussyklit.

Kuten tämän artikkelin alussa todettiin, GOST kuuluu lohkosalausten luokkaan, eli siinä oleva tietojenkäsittelyyksikkö on tietolohko. Siksi on varsin loogista odottaa, että se määrittelee algoritmit kryptografisille muunnoksille, eli salaukselle, salauksen purkamiselle ja "kirjanpidolle" yhden tietolohkon ohjausyhdistelmässä. Näitä algoritmeja kutsutaan perussyklit GOST, joka korostaa niiden perustavaa merkitystä tämän salauksen rakentamisessa.

Perussyklit on rakennettu perusvaiheet edellisessä osiossa käsitelty kryptografinen muunnos. Päävaiheen suorittamisen aikana käytetään vain yhtä 32-bittistä avainelementtiä, kun taas GOST-avain sisältää kahdeksan tällaista elementtiä. Siksi, jotta avainta voidaan käyttää täysin, jokaisen perussilmukan on suoritettava toistuvasti päävaihe eri elementeineen. Samalla vaikuttaa aivan luonnolliselta, että jokaisessa perussyklissä avaimen kaikkia elementtejä tulee käyttää yhtä monta kertaa, salausturvasyistä tätä lukua tulisi olla enemmän kuin yksi.

Kaikki yllä tehdyt, yksinkertaisesti terveeseen järkeen perustuvat oletukset osoittautuivat oikeiksi. Perussilmukat ovat toistuvia suorituksia päävaihe käyttämällä avaimen eri elementtejä ja eroavat toisistaan ​​vain vaiheen toistojen määrässä ja avainelementtien käyttöjärjestyksessä. Tämä järjestys on annettu alla eri sykleille.

Salausjakso 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 .

Kuvio 2a. Salausjakson 32-Z kaavio

Salauksen purkujakso 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 .

Kuvio 2b. 32-P-salauksenpurkukaavio

Jäljitelmälisäkkeen 16-З valmistussykli:

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 .

Kuvio 2c. Jäljitelmälisäkkeen 16-З tuotantosyklin kaavio.

Jokaisella syklillä on oma aakkosnumeerinen merkintä, joka vastaa kuviota " n-X", jossa nimityksen ensimmäinen osa ( n), määrittää syklin päävaiheen toistojen lukumäärän ja merkinnän toisen elementin ( X), kirjain, määrittää salausjärjestyksen ("З") tai salauksen purkamisen ("Р") avainelementtien käytössä. Tämä tilaus vaatii lisäselvitystä:

Salauksen purkujakson tulisi olla salausjakson käänteinen, eli näiden kahden jakson peräkkäisen soveltamisen mielivaltaiseen lohkoon pitäisi johtaa alkuperäiseen lohkoon, mikä näkyy seuraavalla suhteella: C 32-R ( C 32-З ( T))=T, Missä T- mielivaltainen 64-bittinen tietolohko, C X( T) on silmukan tulos X tietolohkon yläpuolella T. Tämän ehdon täyttämiseksi GOST:n kaltaisille algoritmeille on välttämätöntä ja riittävää, että järjestys, jossa vastaavat syklit käyttävät avainelementtejä, on keskenään käänteinen. Kirjallisen ehdon pätevyys tarkasteltavassa tapauksessa on helppo varmistaa vertaamalla yllä olevia jaksoja jaksoille 32-3 ja 32-P. Edellisestä seuraa yksi mielenkiintoinen seuraus: syklin ominaisuus olla käänteinen toiselle jaksolle on molemminpuolinen, eli jakso 32-3 on käänteinen syklin 32-P suhteen. Toisin sanoen tietolohkon salaus voitaisiin teoriassa tehdä salauksenpurkusilmukalla, jolloin tietolohkon salauksen purku olisi tehtävä salaussilmukalla. Kahdesta keskenään käänteisestä syklistä jompaakumpaa voidaan käyttää salaukseen, sitten toista on käytettävä tietojen salauksen purkamiseen, mutta GOST28147-89-standardi määrittää jaksoille roolit eikä anna käyttäjälle oikeutta valita tässä asiassa .

Lisäysjäljitelmän generointisykli on puolet salausjaksoista pidempi, avainelementtien käyttöjärjestys siinä on sama kuin salausjakson 16 ensimmäisessä vaiheessa, mikä on helppo nähdä yllä olevat sekvenssit huomioiden, siksi tämä järjestys syklin nimeämisessä on koodattu samalla kirjaimella "Z".

Perussyklien kaaviot on esitetty kuvioissa 2a-c. Jokainen niistä ottaa argumentiksi ja palauttaa tuloksena 64-bittisen tietolohkon, joka on merkitty kaavioihin N. Symbol Step( N,X) tarkoittaa pääsalauksen muunnosvaiheen suorittamista datalohkolle N käyttämällä avainelementtiä X. Salausjaksojen ja lisäyksen matkimisen laskennan välillä on vielä yksi ero, jota ei mainita yllä: salauksen perusjaksojen lopussa tuloslohkon ylä- ja alaosat vaihdetaan, tämä on välttämätöntä niiden keskinäisen palautuvuuden vuoksi. .

Perussalaustilat.

GOST 28147-89 tarjoaa seuraavat kolme tietojen salaustilaa:

• yksinkertainen vaihto,
• pelaaminen,
• palaute gamma,

ja yksi lisämuoto jäljitelmän lisäyksen tuottamiseksi.

Kaikissa näissä tiloissa dataa käsitellään 64-bittisinä lohkoina, joihin matriisi jaetaan ja joille tehdään kryptografinen muunnos, minkä vuoksi GOST viittaa lohkosalauksiin. Kahdessa pelitilassa on kuitenkin mahdollista käsitellä alle 8 tavun epätäydellinen tietolohko, mikä on välttämätöntä salattaessa mielivaltaisen kokoisia tietoryhmiä, jotka eivät saa olla 8 tavun kerrannaisia.

Ennen kuin siirrytään tarkastelemaan tiettyjä salausmuunnosten algoritmeja, on tarpeen selventää seuraavien osien kaavioissa käytettyä merkintää:

T Oi T w ovat avoimen ja salatun datan ryhmiä;

, – i- 64-bittiset avoimen ja salatun tiedon lohkot: , , viimeinen lohko voi olla epätäydellinen: ;

n– 64-bittisten lohkojen määrä tietojoukossa;

C X on toiminto, jolla muunnetaan 64-bittinen datalohko perussyklin "X" algoritmin mukaisesti.

Kuvataan nyt tärkeimmät salaustilat:

Yksinkertainen vaihto.

Salaus tässä tilassa koostuu 32-3-syklin soveltamisesta avoimiin tietolohkoihin, salauksen purkamiseen - 32-P-jakson soveltamiseen salattuihin tietolohkoihin. Tämä on muodoista yksinkertaisin, siinä käsitellään 64-bittisiä datalohkoja toisistaan ​​riippumatta. Salaus- ja salauksenpurkualgoritmien kaaviot yksinkertaisessa korvaustilassa on esitetty kuvioissa 3a ja b, vastaavasti, ne ovat triviaaleja eivätkä kaipaa kommentteja.

Piirustus. 3a. Tietojen salausalgoritmi yksinkertaisessa vaihtotilassa

Piirustus. 3b. Tietojen salauksen purkualgoritmi yksinkertaisessa korvaustilassa

Salauksen tai salauksen purkamisen kohteena olevan avoimen tai salatun tiedon joukon koon on oltava 64 bitin kerrannainen: | T o |=| T w |=64 n , toiminnon suorittamisen jälkeen vastaanotetun datataulukon koko ei muutu.

Yksinkertaisessa korvaavassa salaustilassa on seuraavat ominaisuudet:

• Koska tietolohkot salataan toisistaan ​​riippumatta ja niiden sijainnista datataulukossa, kun kaksi identtistä selkotekstilohkoa salataan, saadaan identtiset salatekstilohkot ja päinvastoin. Mainitun ominaisuuden avulla kryptausanalyytikko voi päätellä, että alkuperäisen datan lohkot ovat identtisiä, jos hän kohtaa identtisiä lohkoja salatun datan ryhmässä, mikä ei ole hyväksyttävää vakavalle salaukselle.
• Jos salatun datataulukon pituus ei ole 8 tavun tai 64 bitin kerrannainen, syntyy ongelma, kuinka ja miten taulukon viimeinen epätäydellinen datalohko täytetään täyteen 64 bittiin. Tämä tehtävä ei ole niin yksinkertainen kuin miltä näyttää ensi silmäyksellä. Ilmeiset ratkaisut, kuten "täytä epätäydellinen lohko nollabitillä" tai yleisemmin "täytä epätäydellinen lohko kiinteällä nollan ja yhden bitin yhdistelmällä", voivat tietyissä olosuhteissa antaa kryptanalyytikolle mahdollisuuden määrittää tämän juuri tämän sisällön epätäydellinen lohko luettelointimenetelmillä, ja tämä tosiasia tarkoittaa suojaussalauksen vähenemistä. Lisäksi salatekstin pituus muuttuu ja kasvaa lähimpään 64 bitin kokonaislukukerrokseen, mikä on usein ei-toivottavaa.

Ensi silmäyksellä yllä luetellut ominaisuudet tekevät yksinkertaisen korvaustilan käyttämisen käytännössä mahdottomaksi, koska sillä voidaan salata vain 64 bitin kerrannaisia ​​dataryhmiä, jotka eivät sisällä toistuvia 64-bittisiä lohkoja. Näyttää siltä, ​​että näiden ehtojen täyttymistä on mahdotonta taata minkään todellisen tiedon osalta. Tämä on melkein totta, mutta on yksi erittäin tärkeä poikkeus: muista, että avaimen koko on 32 tavua ja korvaavan taulukon koko on 64 tavua. Lisäksi toistuvien 8-tavuisten lohkojen läsnäolo avain- tai korvaustaulukossa osoittaa niiden erittäin huonoa laatua, joten todellisissa avainelementeissä ei voi olla tällaista toistoa. Siten havaitsimme, että yksinkertainen korvaustila on varsin sopiva avaintietojen salaamiseen, varsinkin kun muut tilat ovat vähemmän käteviä tähän tarkoitukseen, koska ne vaativat ylimääräisen synkronointitietoelementin - synkronointiviestin (katso seuraava osa). Oletuksemme on oikea, GOST määrää yksinkertaisen korvaustilan käytön yksinomaan avaintietojen salaamiseen.

Uhkapelit.

Kuinka pääset eroon yksinkertaisen vaihtotilan puutteista? Tätä varten on välttämätöntä mahdollistaa alle 64 bitin lohkojen salaus ja varmistaa, että salatekstilohko riippuu sen lukumäärästä, toisin sanoen satunnaistaa salausprosessi. GOST:ssa tämä saavutetaan kahdella eri tavalla kahdessa salaustilassa, tarjoten skaalaus . Uhkapelit - tämä on salausalueen asettaminen (poistaminen) avoimelle (salatulle) datalle, toisin sanoen tietoelementtien sarjalle, joka on luotu käyttämällä jotakin kryptografista algoritmia salatun (avoimen) tiedon saamiseksi. Vastavuoroisesti käänteisiä binäärioperaatioita on käytettävä gamman päällekkäisyyteen salauksen aikana ja sen poistamiseen salauksen purkamisen aikana, esimerkiksi yhteen- ja vähennysmodulo 2 64 64-bittisille tietolohkoille. GOST:ssa tähän tarkoitukseen käytetään bittikohtaista lisäystä modulo 2, koska se on itsensä käänteinen ja lisäksi se on yksinkertaisimmin toteutettu laitteistossa. Gamming ratkaisee molemmat mainitut ongelmat: ensinnäkin kaikki gammaelementit ovat erilaisia ​​todellisissa salatuissa taulukoissa, ja siksi jopa kahden identtisen lohkon salaustulos yhdessä tietojoukossa on erilainen. Toiseksi, vaikka gammaelementit tuotetaan yhtä suurena 64 bitin osuuksina, voidaan käyttää myös sellaisen lohkon osaa, jonka koko on yhtä suuri kuin salatun lohkon koko.

Siirrytään nyt suoraan gammatilan kuvaukseen. Tämän tilan gamma saadaan seuraavasti: käyttämällä jotakin algoritmista toistuvan numerosekvenssin generaattoria (RGCH) luodaan 64-bittiset datalohkot, joille suoritetaan sitten 32-3-muunnos, eli salaus yksinkertaisessa korvaustilassa, jolloin tuloksena on gammalohkoissa. Koska päällekkäisyys ja gamman poistaminen suoritetaan käyttämällä samaa bittikohtaista XOR-toimintoa, salaus- ja salauksenpurkualgoritmit gammatilassa ovat identtisiä, niiden yleinen kaavio on esitetty kuvassa 4.

Asteikon luomiseen käytetty RGHR on toistuva toiminto: – toistuvan sekvenssin elementit, f on muunnosfunktio. Siksi väistämättä herää kysymys sen alustamisesta, eli elementistä, itse asiassa tämä tietoelementti on algoritmiparametri gammamoodille, se on merkitty kaavioihin S, ja sitä kutsutaan kryptografiassa synkronoida viesti ja GOSTissamme - alkutäyttö yksi kooderirekistereistä. Tietyistä syistä GOST:n kehittäjät päättivät käyttää RGHR:n alustamiseen ei suoraan synkronointiviestiä, vaan sen muuntamisen tulosta 32-3-syklin mukaisesti: . RGHR:n muodostama elementtisarja riippuu täysin sen alkutäytöstä, eli tämän sekvenssin elementit ovat lukumääränsä ja RGHR:n alkutäytön funktio: missä fi(X)=f(fi –1 (X)), f 0 (X)=X. Kun otetaan huomioon muunnos yksinkertaisen korvausalgoritmin mukaan, lisätään myös riippuvuus avaimesta:

Missä G i– i- asteikon elementti, K- avain.

Siten gamma-tilassa käytettävien gammaelementtien järjestys määräytyy yksiselitteisesti avaindatan ja synkronointiviestin perusteella. Luonnollisesti salauksen purku- ja purkuprosesseissa on käytettävä samaa synkronointisanomaa, jotta salausprosessi olisi palautuva. Gamman ainutlaatuisuuden vaatimuksesta, jonka epäonnistuminen johtaa salauksen voimakkuuden katastrofaaliseen heikkenemiseen, seuraa, että kahden erilaisen dataryhmän salaamiseksi samalla avaimella on varmistettava erilaisia ​​synkronointiviestejä. Tämä johtaa tarpeeseen tallentaa tai lähettää synkronointisanoma viestintäkanavia pitkin yhdessä salatun datan kanssa, vaikka joissakin erikoistapauksissa se voidaan määrittää ennalta tai laskea erityisellä tavalla, jos kahden taulukon salaus samalla avaimella on poissuljettu.

Katsotaanpa nyt tarkemmin RGHR:ää, jota käytetään GOST:ssa gammaelementtien luomiseen. Ensinnäkin on huomattava, että generoidusta numerosarjasta ei vaadita tilastollisia ominaisuuksia. GOST-kehittäjät suunnittelivat RGHR:n seuraavien ehtojen täyttämisen perusteella:

• RGHR:n generoiman numerosarjan toistojakson ei tulisi poiketa suuresti (prosentteina) suurimmasta mahdollisesta arvosta 2 64 tietylle lohkokoolle;
• RGHR:n tuottamien naapuriarvojen tulee erota toisistaan ​​jokaisessa tavussa, muuten kryptanalyytikon tehtävä yksinkertaistuu;
• RGHR:n pitäisi olla melko helppo toteuttaa sekä laitteistossa että ohjelmistossa yleisimmillä prosessoreilla, joista useimmat, kuten tiedät, on 32-bittisiä.

Näiden periaatteiden perusteella GOSTin luojat suunnittelivat erittäin onnistuneen RGHR:n, jolla on seuraavat ominaisuudet:

Missä C 0 =1010101 16 ;

Missä C 1 =1010104 16 ;

Luvun merkinnässä oleva alaindeksi tarkoittaa sen numerojärjestelmää, joten tässä vaiheessa käytetyt vakiot kirjoitetaan heksadesimaalilukujärjestelmään.

Toinen lauseke tarvitsee kommentteja, koska GOST-tekstissä annetaan jotain muuta: , samalla vakion arvolla C 1 . Mutta edelleen standardin tekstissä annetaan kommentti, että käy ilmi, että operaatiossa otetaan loput modulo 2 32 -1 siellä ei ymmärretä samalla tavalla kuin matematiikassa. Ero on siinä, että GOST:n (2 32 -1) mukaan mod(2 32 –1)=(2 32 –1), ei 0. Itse asiassa tämä yksinkertaistaa kaavan toteutusta, ja matemaattisesti oikea lauseke sille on annettu yllä.

• sarjan toistojakso nuoremmalle osalle on 2 32, vanhemmalle osalle 2 32 -1, koko jaksolle jakso on 2 32 (2 32 -1), todiste tästä tosiasiasta, hyvin yksinkertainen, tulet Hanki itsellesi. Ensimmäinen kaava näistä kahdesta on toteutettu yhdellä käskyllä, toinen, ilmeisestä vaivallisuudestaan ​​huolimatta, kahdella käskyllä ​​kaikilla nykyaikaisilla 32-bittisillä prosessoreilla - ensimmäinen käsky on tavallinen additio modulo 2 32 siirtobitin tallennuksella, ja toinen käsky lisää siirtobitin vastaanotettuun arvoon.

Salausalgoritmin kaavio gammatilassa on esitetty kuvassa 4, alla on kaavion selitykset:

Kuva 4. Tietojen salausalgoritmi (salauksen purku) gammatilassa.

Vaihe 0

Määrittää alkutiedot pääsalausmuunnosvaiheelle:

• T o(w) - mielivaltaisen kokoisen avoimen (salatun) datan joukko, jolle suoritetaan salaus (salauksen purku) proseduurin aikana, taulukko muunnetaan 64 bitin osissa;
• S – synkronoida viesti 64-bittinen dataelementti, joka tarvitaan gammageneraattorin alustamiseen;

Vaihe 1

Synkronointisanoman alkumuunnos, joka suoritetaan sen "satunnaistamiseksi" eli siinä olevien tilastollisten mallien eliminoimiseksi, tulosta käytetään RGHR:n alkutäyttönä;

Vaihe 2

Yksi askel RGHR:n työstä, joka toteuttaa sen toistuvan algoritmin. Tämän vaiheen aikana vanhempi ( S 1) ja nuorempi ( S 0) datasekvenssin osat muodostetaan toisistaan ​​riippumatta;

Vaihe 3

Uhkapelit. Seuraava RGHR:n tuottama 64-bittinen elementti alistetaan salausmenettelyyn 32-3 jaksossa, jonka tulosta käytetään gamma-elementtinä seuraavan samankokoisen avoimen (salatun) datan lohkon salaamiseen (salauksen purkamiseen).

Vaihe 4

Algoritmin tulos on salattu (salauksesta purettu) tietojoukko.

Seuraavat ovat gamman ominaisuudet salaustilana:

1. Identtiset lohkot avoimessa datataulukossa antavat salattuna erilaisia ​​salatekstilohkoja, mikä mahdollistaa niiden henkilöllisyyden piilottamisen.
2. Koska gamma suoritetaan bitti kerrallaan, epätäydellisen datalohkon salaus onnistuu helposti tämän epätäydellisen lohkon bittien salauksena, johon käytetään gammalohkon vastaavia bittejä. Joten epätäydellisen 1 bitin lohkon salaamiseksi standardin mukaan tulee käyttää vähiten merkitsevää bittiä gammalohkosta.
3. Salauksessa käytetty synkronointisanoma on jotenkin välitettävä, jotta sitä voidaan käyttää salauksen purkamisessa. Tämä voidaan saavuttaa seuraavilla tavoilla:

• tallentaa tai lähettää synkronointiviestin yhdessä salatun datataulukon kanssa, mikä kasvattaa dataryhmän kokoa salauksen aikana synkronointiviestin koolla eli 8 tavulla;
• käyttää synkronointisanoman ennalta määrättyä arvoa tai generoi se synkronisesti lähteen ja vastaanottimen toimesta tietyn lain mukaisesti, jolloin lähetetyn tai tallennetun dataryhmän koko ei muutu;

Molemmat menetelmät täydentävät toisiaan, ja niissä harvoissa tapauksissa, joissa ensimmäinen, yleisin niistä ei toimi, voidaan käyttää toista, eksoottisempaa. Toisella menetelmällä on paljon vähemmän sovelluskohdetta, koska on mahdollista tehdä synkronointiviesti ennalta määrätyksi vain, jos vain yksi tietojoukko on ilmeisesti salattu tietylle avaintietojoukolle, mitä ei tapahdu kovin usein. Synkronointiviestiä ei myöskään aina ole mahdollista generoida synkronisesti datataulukon lähteellä ja vastaanottajalla, koska se vaatii kovaa yhteyttä johonkin järjestelmässä. Joten näennäisen järkevä ajatus käyttää lähetetyn viestin numeroa synkronointisanomana salattujen viestien välitysjärjestelmässä ei sovellu, koska viesti saattaa kadota eikä pääse vastaanottajalle, jolloin lähteen salausjärjestelmät ja vastaanotin ei ole synkronoitu. Siksi tarkasteltavassa tapauksessa ei ole vaihtoehtoa synkronointiviestin lähettämiselle salatun viestin mukana.

Toisaalta voidaan antaa myös päinvastainen esimerkki. Oletetaan, että tietojen salausta käytetään suojaamaan levyllä olevia tietoja, ja se on toteutettu alhaisella tasolla, tiedot salataan sektoreittain riippumattoman pääsyn varmistamiseksi. Tässä tapauksessa synkronointiviestin tallentaminen salatun tiedon mukana on mahdotonta, koska sektorin kokoa ei voi muuttaa, mutta se voidaan laskea levyn lukupään numeron, raidan (sylinterin) numeron funktiona, ja sektorin numero radalla. Tässä tapauksessa synkronointiviesti on sidottu levyllä olevan sektorin sijaintiin, joka tuskin voi muuttua ilman levyn alustamista, eli tuhoamatta sillä olevia tietoja.

Gamma-tilassa on toinen mielenkiintoinen ominaisuus. Tässä tilassa datataulukon bitit salataan toisistaan ​​riippumatta. Näin ollen jokainen salatekstin bitti riippuu vastaavasta selkeän tekstin bitistä ja tietysti bitin järjestysnumerosta taulukossa: . Tästä seuraa, että salatekstin bitin muuttaminen vastakkaiseen arvoon johtaa samanlaiseen selkeän tekstin bitin muutokseen päinvastaiseksi:

jossa tarkoittaa käänteistä suhteessa t bitin arvo ().

Tämä ominaisuus antaa hyökkääjälle mahdollisuuden vaikuttaa salatekstin bitteihin tehdäkseen ennustettavia ja jopa kohdennettuja muutoksia vastaavaan selkeään tekstiin, joka on saatu sen salauksen purkamisen jälkeen, ilman salaista avainta. Tämä havainnollistaa kryptologiassa hyvin tunnettua tosiasiaa, että salaisuus ja aitous ovat eri ominaisuuksia kryptografiset järjestelmät . Toisin sanoen salausjärjestelmän ominaisuudet, jotka tarjoavat suojan luvattomalta pääsyltä viestin sisältöön ja viestin luvattomilta muutoksilta, ovat riippumattomia ja voivat leikata vain joissain tapauksissa. Edellä oleva tarkoittaa, että on olemassa salausalgoritmeja, jotka tarjoavat tietyn salaisuuden salatuille tiedoille eivätkä samalla suojaa muutoksilta, ja päinvastoin, varmistavat tietojen aitouden eivätkä rajoita mahdollisuutta tutustua niihin. Tästä syystä gammatilan harkittua ominaisuutta ei pitäisi pitää sen haittapuolena.

Uhkapeli palautteen kera.

Tämä tila on hyvin samanlainen kuin gammatila ja eroaa siitä vain gamma-elementtien luontitavassa - seuraava gamma-elementti syntyy edellisen salatun datalohkon 32-3-syklin muunnoksen tuloksena ja salaa tietotaulukon ensimmäinen lohko, gamma-elementti generoidaan muunnoksen tuloksena saman synkronointijakson mukaisesti. Tällä saavutetaan lohkolinkitys - jokainen salatekstin lohko tässä tilassa riippuu vastaavista ja kaikista aiemmista selkeän tekstin lohkoista. Siksi tätä tilaa kutsutaan joskus skaalaus verkkopaloilla . Se, että lohkot on linkitetty, ei vaikuta salauksen turvallisuuteen.

Palaute-gamma-moodin dekoodauksen ja salauksen purkamisen algoritmikaavio on esitetty kuvassa 5, eikä se yksinkertaisuutensa vuoksi tarvitse kommentteja.

Kuva 5. Algoritmi tietojen salaukselle (salauksen purkamiselle) gammatilassa palautteen kanssa.

Suljetun silmukan gammatilan salauksella on samat ominaisuudet kuin salauksella normaalissa gammatilassa, lukuun ottamatta salatekstin vioittumisen vaikutusta vastaavaan selkeään tekstiin. Vertailun vuoksi kirjoitetaan lohkon salauksenpurkutoiminnot molemmille mainituille tiloille:

Peli;

Pelaaminen palautteen avulla;

Kun normaalissa skaalaustilassa muutokset tietyissä salatekstin bitteissä vaikuttavat vain vastaaviin puhtaan tekstin bitteihin, palauteskaalaustilassa kuva on hieman monimutkaisempi. Kuten vastaavasta yhtälöstä voidaan nähdä, avattaessa datalohkon salausta suljetun silmukan gammamoodissa avoin datalohko riippuu vastaavasta ja aikaisemmasta salatusta datalohkosta. Siksi, jos tuomme vääristymiä salattuun lohkoon, niin salauksen purkamisen jälkeen kaksi avoimen datan lohkoa vääristyy - vastaava ja sitä seuraava, ja ensimmäisessä tapauksessa vääristymät ovat luonteeltaan samanlaisia ​​kuin gammassa. tilassa, ja toisessa tapauksessa - kuten tilassa yksinkertainen vaihto. Toisin sanoen vastaavassa avoimessa datalohkossa samat bitit korruptoituvat kuin salatussa datalohkossa ja seuraavassa avoimessa datalohkossa kaikki bitit ovat toisistaan ​​riippumattomia todennäköisyydellä 1 / 2 muuttaa arvojaan.

Lisäyssimulaation kehittäminen datajoukolle.

Aiemmissa osioissa olemme käsitelleet salattujen tietojen korruption vaikutusta vastaaviin selkeään dataan. Havaitsimme, että salausta purettaessa yksinkertaisessa korvaustilassa vastaava avoimen datan lohko vääristyy arvaamattomalla tavalla ja gammatilassa lohkon salauksen purkamisessa muutokset ovat ennakoitavissa. Suljetun silmukan skaalaustilassa kaksi lohkoa vääristyy, toinen ennustettavasti ja toinen arvaamattomalla tavalla. Tarkoittaako tämä sitä, että väärien tietojen pakottamista vastaan ​​suojautumisen kannalta gammatila on huono, kun taas yksinkertaisen vaihto- ja palautegamman tilat ovat hyviä? - Ei missään tapauksessa. Tätä tilannetta analysoitaessa on otettava huomioon se, että salauksesta puretussa tietolohkossa voidaan havaita arvaamattomia muutoksia vain näiden samojen tietojen redundanssin tapauksessa ja mitä suurempi redundanssiaste on, sitä todennäköisemmin on havaita vääristymä. Erittäin suuri redundanssi tapahtuu esimerkiksi luonnollisilla ja keinotekoisilla kielillä oleville teksteille, jolloin vääristymä on lähes väistämätöntä. Kuitenkin muissa tapauksissa, esimerkiksi vääristäessään pakattuja digitoituja äänikuvia, saamme yksinkertaisesti toisenlaisen kuvan, jonka korvamme pystyy havaitsemaan. Vääristymä jää tässä tapauksessa havaitsematta, ellei luonnollisesti ole ennakkotietoa äänen luonteesta. Johtopäätös tästä on seuraava: koska joidenkin salausmoodien kyky havaita salattuun dataan tuotuja vääristymiä riippuu suuresti salatun datan olemassaolosta ja redundanssin asteesta, tämä kyky ei ole vastaavien tilojen immanentti ominaisuus, eikä sitä voida pitää heidän etunsa.

Ongelman ratkaisemiseksi, joka koskee vääristymien havaitsemista salatussa tietojoukossa tietyllä todennäköisyydellä, GOST tarjoaa ylimääräisen salausmuunnostavan - jäljitellyn lisäyksen luomisen. Väärennetty liite on ohjausyhdistelmä, joka riippuu avoimesta tiedosta ja salaisen avaimen tiedoista. Lisäysmimiikan käytön tarkoituksena on havaita kaikki vahingossa tapahtuneet tai tahalliset muutokset tietojoukossa. Edellisessä kappaleessa kuvattu ongelma voidaan ratkaista onnistuneesti lisäämällä salattuihin tietoihin väärennös. Potentiaaliselle hyökkääjälle seuraavat kaksi tehtävää ovat käytännössä ratkaisemattomia, jos hän ei omista avainta:

• lisäyssimuloinnin laskeminen tietylle avoimelle informaatiojoukolle;
• avoimen datan valinta tietylle simulaatioinserteelle;

Simuloidun insertin generointialgoritmin kaavio on esitetty kuvassa 6.

Kuva 6. Algoritmi simuloidun lisäyksen luomiseksi datataulukolle.

Lähdössä vastaanotettu lohkon osa otetaan jäljitelmäksi, yleensä sen 32 vähiten merkitsevää bittiä. Simuloidun lisäyksen kokoa valittaessa tulee ottaa huomioon, että virheellisen tiedon onnistumisen todennäköisyys on 2 –| minä | brute force -yritystä kohti, ellei hyökkääjällä ole tehokkaampaa raa'an voiman menetelmää kuin yksinkertainen arvaus. Käytettäessä 32-bittistä väärennettyä lisäosaa tämä todennäköisyys on

Keskustelu GOST-salausalgoritmeista.

GOSTin kryptografinen vahvuus.

Valittaessa salausalgoritmia käytettäväksi tietyssä kehitystyössä, yksi määräävistä tekijöistä on sen vahvuus, eli vastustuskyky vastustajan yrityksille paljastaa se. Salauksen vahvuus, kun tarkastellaan lähemmin, tiivistyy kahteen toisiinsa liittyvään kysymykseen:

• onko tämä salaus ollenkaan mahdollista avata;
• jos on, kuinka vaikeaa se on käytännössä;

Salauksia, joita ei voi rikkoa ollenkaan, kutsutaan ehdottoman tai teoreettisesti turvallisiksi. Tällaisten salausten olemassaolon todistaa Shannonin lause, mutta tämän vahvuuden hinta on tarve käyttää avainta, joka ei ole pienempi kuin itse viestin kokoinen salaamaan jokainen viesti. Kaikissa tapauksissa, lukuun ottamatta useita erityisiä, tämä hinta on kohtuuton, joten käytännössä käytetään pääasiassa salauksia, joilla ei ole absoluuttista turvallisuutta. Siten yleisimmin käytetyt salausmenetelmät voidaan ratkaista rajallisessa ajassa tai tarkemmin sanottuna äärellisessä määrässä vaiheita, joista jokainen on jokin lukujen operaatio. Heille tärkein käsite on käytännön vakauden käsite, joka ilmaisee niiden paljastamisen käytännön vaikeutta. Tämän vaikeuden kvantitatiivinen mitta voi olla aritmeettisten ja loogisten perusoperaatioiden lukumäärä, jotka on suoritettava salauksen ratkaisemiseksi, toisin sanoen vastaavan selkeän tekstin määrittämiseksi tietylle salatekstille todennäköisyydellä, joka ei ole pienempi kuin annettu arvo. Samalla kryptaanalyytikolla voi olla salatun datataulukon lisäksi avoimen datan lohkoja ja sitä vastaavaa salattua dataa tai jopa mahdollisuus saada vastaavat salatut tiedot mihin tahansa valitsemaansa avoimeen dataan - riippuen listatuista ja monista muut määrittelemättömät olosuhteet erotetaan erilliset kryptaanalyysityypit.

Kaikki nykyaikaiset kryptojärjestelmät on rakennettu Kirchhoff-periaatteen mukaan, eli salattujen viestien salassapito määräytyy avaimen salassapitoisuuden mukaan. Tämä tarkoittaa, että vaikka itse salausalgoritmi olisi kryptanalyytikon tiedossa, hän ei silti pysty purkamaan viestiä, jos hänellä ei ole vastaavaa avainta. Salausta pidetään hyvin suunniteltuna, jos sitä ei voida murtaa tehokkaammin kuin raa'alla voimalla etsimällä koko avainavaruudesta, ts. yli kaikkien mahdollisten avainarvojen. GOST todennäköisesti vastaa tätä periaatetta - vuosien intensiivisen tutkimuksen aikana ei ole ehdotettu yhtä tehokasta menetelmää sen kryptausanalyysiin. Vahvuudeltaan se on monta suuruusluokkaa parempi kuin entinen amerikkalainen salausstandardi DES.

GOST käyttää 256-bittistä avainta ja avaintilan koko on 2256 . Mikään tällä hetkellä olemassa olevista tai lähitulevaisuudessa otettavissa olevista elektronisista laitteista ei voi poimia avainta alle monessa sadassa vuodessa. Tästä arvosta on tullut nykyään symmetristen salausalgoritmien de facto avaimen kokostandardi, ja myös Yhdysvaltain uusi salausstandardi tukee sitä. Entinen amerikkalainen standardi DES, jonka todellinen avainkoko on 56 bittiä ja avaintilan koko vain 256, ei ole enää tarpeeksi vahva nykyaikaisten laskentatyökalujen ominaisuuksien valossa. Tämän osoittivat 1990-luvun lopulla useat onnistuneet raa'an voiman hyökkäykset DES:ää vastaan. Lisäksi DES:ssä käytettiin erityisiä kryptausanalyysimenetelmiä, kuten differentiaalista ja lineaarista. Tässä suhteessa DES voi olla enemmän tutkimusta tai tieteellistä mielenkiintoa kuin käytännön merkitystä. Vuonna 1998 sen kryptografinen heikkous tunnustettiin virallisesti - Yhdysvaltain kansallinen standardointiinstituutti suositteli kolminkertaisen DES-salauksen käyttöä. Ja vuoden 2001 lopussa hyväksyttiin virallisesti uusi yhdysvaltalainen AES-salausstandardi, joka on rakennettu eri periaatteille ja vapaa edeltäjänsä puutteista.

Huomautuksia GOST-arkkitehtuurista.

On tunnettua, että kotimainen salausstandardi edustaa kokonaista salausperhettä, joka on rakennettu samoilla periaatteilla. Sen tunnetuin "sukulainen" on entinen amerikkalainen salausstandardi, DES-algoritmi. Kaikki nämä salaukset, kuten GOST, sisältävät kolmen tason algoritmeja. Pohja on aina tietty ”perusaskel”, jonka pohjalta rakennetaan samalla tavalla ”perussyklit”, joiden pohjalle rakennetaan jo käytännön menettelyt salaukseen ja jäljitelmän lisäyksen kehittämiseen. Siten tämän perheen jokaisen salauksen spesifisyys on juuri sen päävaiheessa tai pikemminkin jopa sen osassa. Vaikka klassisten lohkosalausten arkkitehtuuri, johon GOST kuuluu, on kaukana tämän artikkelin soveltamisalasta, on silti syytä sanoa muutama sana siitä.

Algoritmit "salauksen muuntamisen perusvaiheille" salauksille, kuten GOST, on rakennettu samalla tavalla, ja tämä arkkitehtuuri on ns. tasapainoinen Feistelin verkko (tasapainoinen Feistel-verkko), joka on nimetty sitä ensimmäisenä ehdottajan mukaan. Datan muunnosmalli yhdellä jaksolla tai, kuten sitä yleisesti kutsutaan, pyöristää , näkyy kuvassa 7.

Kuva 7. Pääsalauksen muunnosvaiheen sisältö GOST:n kaltaisille lohkosalauksille.

Pääaskelman tuloon syötetään tasakokoinen lohko, jonka ylä- ja alapuoliskot käsitellään erikseen toisistaan. Muunnoksen aikana lohkon alempi puolisko sijoitetaan vanhemman tilalle ja vanhempi yhdistetään käyttämällä bittikohtaista " yksinomainen tai » jonkin funktion laskennan tuloksella nuoremman tilalle. Tämä funktio, joka ottaa argumenttina lohkon alaosan ja avaininformaation elementin ( X), on salauksen sisältöosa ja sitä kutsutaan nimellä salaustoiminto . Eri syistä osoittautui edulliseksi jakaa salattu lohko kahteen samankokoiseen osaan: | N 1 |=|N 2 | - tämä tosiasia heijastaa sanaa "tasapainoinen" arkkitehtuurin nimessä. Kuitenkin myös salauksen epätasapainoisia verkkoja käytetään ajoittain, joskaan ei niin usein kuin balansoituja. Lisäksi salauksen vahvuusnäkökohdat edellyttävät, että avainelementin koko on vähintään puolet lohkosta: GOST:ssa kaikki kolme kokoa ovat 32 bittiä. .

Jos sovellamme yllä olevaa GOST-algoritmin päävaiheen kaavioon, tulee ilmeiseksi, että algoritmin lohkot 1,2,3 (katso kuva 1) määrittävät sen salausfunktion laskennan ja lohkot 4 ja 5 asettuvat. päävaiheen lähtölohkon muodostus tulolohkon sisällön ja salausfunktion arvon perusteella. Lisätietoa nykyaikaisten salaisen avaimen lohkosalausten arkkitehtuurista löytyy klassikoista tai muokattuna teoksistani.

Edellisessä osiossa verrattiin jo DES:ää ja GOST:ia kestävyyden suhteen, nyt verrataan niitä toiminnallisen sisällön ja toteutuksen helppouden suhteen. GOST-salausjaksoissa päävaihe toistetaan 32 kertaa, DES:lle tämä arvo on 16. Itse GOST-salaustoiminto on kuitenkin paljon yksinkertaisempi kuin vastaava DES-toiminto, jossa on monia epäsäännöllisiä bittipermutaatioita. Nämä toiminnot toteutetaan erittäin tehottomasti nykyaikaisissa erikoistumattomissa prosessoreissa. GOST ei sisällä tällaisia ​​​​toimintoja, joten se on paljon kätevämpi ohjelmistojen toteuttamisessa.

Yksikään kirjoittajan Intel x86 -alustalle harkitsemista DES-toteutuksista ei saavuta edes puolta tässä artikkelissa sinulle tarjotun GOST-toteutuksen suorituskyvystä huolimatta kaksi kertaa lyhyemmästä syklistä. Kaikki yllä oleva osoittaa, että GOST-kehittäjät ottivat huomioon sekä DES:n positiiviset että negatiiviset puolet ja arvioivat myös realistisemmin kryptausanalyysin nykyisiä ja tulevia mahdollisuuksia. DES:n käyttäminen perustana salaustoteutusten suorituskyvyn vertailussa ei kuitenkaan ole enää relevanttia. Uusi yhdysvaltalainen salausstandardi pärjää huomattavasti tehokkaammin - samalla avaimen koolla kuin GOST:lla, 256 bittiä, AES toimii sitä nopeammin noin 14 % - tätä verrataan "perustoimintojen" lukumäärään. Lisäksi GOST:ia on käytännössä mahdoton rinnastaa, kun taas AES:llä on paljon enemmän mahdollisuuksia tässä suhteessa. Joissakin arkkitehtuureissa tämä AES:n etu voi olla pienempi, toisissa enemmän. Joten Intel Pentium -prosessorilla se saavuttaa 28%. Yksityiskohdat löytyvät osoitteesta.

Keskeiset tiedon laatuvaatimukset ja keskeiset lähteet.

Kaikki avaimet ja korvaustaulukot eivät tarjoa maksimaalista salauksen voimakkuutta. Jokaisella salausalgoritmilla on omat kriteerinsä avaintietojen arvioimiseksi. Joten DES-algoritmille on olemassa ns. heikot näppäimet ”, jossa avoimen ja salatun tiedon välinen yhteys ei ole tarpeeksi peitetty ja salaus on suhteellisen helppo murtaa.

Tyhjentävä vastaus kysymykseen avainten ja GOST-korvaustaulukoiden laatukriteereistä, jos voit saada sen mistä tahansa, on vain algoritmin kehittäjiltä. Asiaa koskevia tietoja ei julkaistu avoimessa lehdistössä. Vakiintuneen menettelyn mukaan valtuutetulta organisaatiolta saatuja avaintietoja on kuitenkin käytettävä leimattujen tietojen salaamiseen. Epäsuorasti tämä voi viitata menetelmien olemassaoloon keskeisten tietojen tarkistamiseksi "täiden" varalta. Jos heikkojen avainten läsnäolo GOSTissa on kiistanalainen ongelma, heikkojen korvaussolmujen läsnäolo on kiistaton. On selvää, että "triviaali" korvaustaulukko, jonka mukaan mikä tahansa arvo korvataan itsestään, on niin heikko, että sitä käytettäessä salaus yksinkertaisesti katkeaa, olipa avain mikä tahansa.

Kuten edellä todettiin, keskeisten tietojen arviointikriteereitä ei ole saatavilla, mutta joitain yleisiä huomioita niistä voidaan silti tehdä.

Avain

Avaimen tulee olla joukko tilastollisesti riippumattomia bittejä, jotka saavat arvot 0 ja 1 yhtä suurella todennäköisyydellä. Ei voida täysin sulkea pois sitä mahdollisuutta, että jotkin tietyt avainarvot voivat osoittautua "heikoiksi", eli salaus ei välttämättä tarjoa tiettyä suojaustasoa, jos niitä käytetään. Oletettavasti tällaisten arvojen osuus kaikkien mahdollisten avainten kokonaismassasta on kuitenkin mitätön. Intensiivinen salaustutkimus ei ole ainakaan vielä paljastanut mitään sellaista avainta yhdellekään tunnetulle (eli FAPSI:n ehdottamalle) korvaustaulukolle. Siksi tietyn todella satunnaislukugeneraattorin avulla generoidut avaimet ovat korkealaatuisia todennäköisyydellä, joka eroaa yksiköstä merkityksettömän pienellä määrällä. Jos avaimet luodaanla, käytetyn generaattorin on tarjottava yllä olevat tilastolliset ominaisuudet, ja lisäksi sillä on oltava korkea kryptografinen vahvuus, vähintään GOSTin itse. Toisin sanoen generaattorin luoman elementtisarjan puuttuvien jäsenten määrittäminen ei saisi olla helpompaa kuin salauksen murtaminen. Lisäksi erilaisia ​​tilastollisia kriteerejä voidaan käyttää hylkäämään avaimia, joiden tilastollinen suorituskyky on heikko. Käytännössä riittää yleensä kaksi kriteeriä - avainbittien tasatodennäköisen jakauman tarkistamiseksi arvojen 0 ja 1 välillä käytetään yleensä Pearsonin kriteeriä ("chi-neliö") ja avainbittien riippumattomuuden tarkistamiseen sarjakriteeri on käytetty. Mainituista kriteereistä voit lukea matemaattisten tilastojen oppikirjoista tai hakuteoista.

Paras tapa avainten luomiseen olisi käyttää laitteistollisia MF-antureita, mutta tämä ei ole aina hyväksyttävää taloudellisista syistä. Kun luodaan pieni joukko avaintietoja, järkevä vaihtoehto tällaisen anturin käytölle on ja on laajalti käytössä käytännössä "elektroninen ruletti" -menetelmä, jolloin seuraava satunnaisten bittien generoitu osa riippuu hetkestä, jolloin käyttäjä painaa tiettyä näppäintä. tietokoneen näppäimistöllä. Tässä mallissa satunnaisten tietojen lähde on tietokoneen käyttäjä, tarkemmin sanottuna hänen reaktionsa ajalliset ominaisuudet. Tässä tapauksessa vain muutama bitti satunnaista dataa voidaan tuottaa yhtä näppäinpainallusta kohden, joten avaininformaation generoinnin kokonaisnopeus on alhainen - jopa useita bittejä sekunnissa. Ilmeisesti tämä lähestymistapa ei sovellu suurten avainryhmien hankkimiseen.

Siinä tapauksessa, että on tarpeen kehittää suuri joukko avaintietoja, on mahdollista ja erittäin laajalle levinnyt käyttää erilaisia ​​näennäissatunnaisten lukujen ohjelmistoantureita. Koska tällainen anturi vaatii suurta salausvoimakkuutta, on luonnollista käyttää itse salauksen gammageneraattoria sellaisenaan - "leikkaamme" salauksen tuottaman gamman halutun kokoisiksi "palasiksi", GOST:lle - 32 tavua kukin. Tietenkin tätä lähestymistapaa varten tarvitsemme "pääavaimen", jonka voimme saada käyttämällä yllä kuvattua elektronista rulettimenetelmää, ja sen avulla, käyttämällä salausta gammageneraattoritilassa, saamme joukon avaintietoja. tarvitsemamme volyymi. Joten nämä kaksi tapaa luoda avaimet - "manuaalinen" ja "algoritminen" - toimivat rinnakkain täydentäen toisiaan. "Pienen budjetin" tiedon kryptografisten suojausjärjestelmien avainten luontijärjestelmät rakennetaan lähes aina tämän periaatteen mukaisesti.

Korvaustaulukko

Korvaava taulukko on pitkän aikavälin avainelementti, eli se on voimassa paljon pidempään kuin yksi avain. Oletetaan, että se on yhteinen kaikille salaussolmuille yhden kryptografisen suojausjärjestelmän sisällä. Vaikka korvaustaulukon luottamuksellisuutta rikotaan, salauksen vahvuus pysyy erittäin korkeana eikä laske sallitun rajan alapuolelle. Siksi ei ole erityistä tarvetta pitää taulukkoa salassa, ja useimmissa GOSTin kaupallisissa sovelluksissa se tehdään näin. Toisaalta korvaustaulukko on kriittinen elementti koko salauksen vahvuuden varmistamiseksi. Väärän taulukon valinta voi johtaa siihen, että salaus rikkoutuu helposti tunnetuilla kryptausanalyysimenetelmillä. Korvaussolmujen kehittämiskriteerit ovat seitsemän sinetin salaisuus, ja FAPSI ei todennäköisesti jaa sitä yleisölle lähitulevaisuudessa. Viime kädessä, jotta voit sanoa, onko tämä korvaustaulukko hyvä vai huono, sinun on käytettävä valtava määrä työtä - useita tuhansia mies- ja konetunteja. Kun taulukko on valittu ja käytetty, se voidaan vaihtaa, jos ja vain, jos salaus sen käytössä osoittautui haavoittuvaksi jollekin toiselle kryptausanalyysille. Siksi paras valinta salauksen keskimääräiselle käyttäjälle on valita yksi useista julkisiksi tulleista taulukoista. Esimerkiksi hash-funktiostandardista se on myös "keskuspankkitoimintaa"; tietoa näistä taulukoista löytyy avoimesta lehdestä ja jopa Internetistä, jos etsit hyvin.

Niille, jotka eivät ole tottuneet ottamaan helpointa tietä, alla on yleinen kaavio laatutaulukoiden hankkimiseksi:

1. Ympärillä tai toisella menetelmällä kehität kahdeksan korvaavan solmun joukon, joilla on taatut epälineaarisuusominaisuudet. Tällaisia ​​menetelmiä on useita, yksi niistä on ns. taivutettujen funktioiden käyttö.
2. Tarkistat yksinkertaisimpien "laatukriteerien" toteutumisen - esimerkiksi ne, jotka on julkaistu DES-korvaussolmuille. Tässä on joitain yleisempiä huomioita tästä pistemäärästä: Jokainen korvaussolmu voidaan kuvata neljällä loogisella funktiolla neljästä loogisesta argumentista. Jos nämä toiminnot ovat kirjoitettu minimaalinen muoto(eli pienimmällä mahdollisella lausekkeen pituudella) eivät ole tarpeeksi monimutkaisia, tällainen korvaava solmu hylätään. Lisäksi koko korvaustaulukon yksittäisten funktioiden tulee erota toisistaan ​​riittävästi. Tässä vaiheessa monet tarkoituksellisesti huonolaatuiset pöydät poistetaan.
3. Rakenna valitsemiesi taulukoiden salausta varten erilaisia ​​pyöreitä malleja, jotka vastaavat erilaisia ​​kryptausanalyysityyppejä, ja mittaa vastaavat "profiilin" ominaisuudet. Joten lineaarista kryptausanalyysiä varten rakenna salauskierroksen lineaarinen tilastollinen analogi ja laske "profiilin" ominaisuus - epälineaarisuusindeksi. Jos se osoittautuu riittämättömäksi, korvaustaulukko hylätään.
4. Lopuksi, käyttämällä edellisen kappaleen tuloksia, kohdista salaus valitsemasi taulukon kanssa intensiiviseen tutkimukseen - yritä kryptausanalyysiä kaikilla tunnetuilla menetelmillä. Tämä vaihe on vaikein ja aikaa vievin. Mutta jos se tehdään laadukkaasti, niin suurella todennäköisyydellä voidaan todeta, ettei pelkkä kuolevainen avaa salausta valitsemillasi taulukoilla, ja on mahdollista, että se on liian kovaa. erikoispalvelut.

On kuitenkin mahdollista tehdä paljon helpommin. Asia on siinä, että mitä enemmän salauskierroksia on, sitä vähemmän yhden kierroksen turvallisuusominaisuuksilla on vaikutusta koko salauksen turvallisuuteen. GOSTissa on jopa 32 kierrosta - enemmän kuin melkein kaikissa samanlaisen arkkitehtuurin salakirjoissa. Siksi useimmissa kotimaisissa ja kaupallisissa sovelluksissa riittää korvaussolmujen hankkiminen itsenäisinä satunnaisina numeroiden 0-15 permutaatioina. Tämä voidaan käytännössä toteuttaa esimerkiksi sekoittamalla kuudentoista kortin pakkaa, joista jokaiselle on määritetty yksi määritellyn alueen arvoista.

Korvaustaulukon osalta on syytä huomata vielä yksi mielenkiintoinen seikka. 32-3- ja 32-R-salausjaksojen palautuvuus ei edellytä, että korvaavat solmut ovat lukujen permutaatioita 0-15. Kaikki toimii, vaikka korvaavassa solmussa olisi päällekkäisiä elementtejä ja korvauksen määrää tällainen solmu. , on peruuttamaton - tässä tapauksessa salauksen vahvuus kuitenkin heikkenee. Miksi näin on, sitä ei käsitellä tässä artikkelissa, mutta itse tosiasian tarkistaminen ei ole vaikeaa. Tätä varten riittää, että yrität ensin salata ja sitten purkaa tietolohko käyttämällä tällaista "alempi" korvaustaulukkoa, jonka solmut sisältävät päällekkäisiä arvoja.

Muunnelmia GOST-teemaan

Hyvin usein salaustietojen suojausjärjestelmässä käytettäväksi tarvitaan algoritmi, jonka toteutusnopeus on suurempi kuin GOST:n, eikä niin suurta kryptografista vahvuutta tarvita. Tyypillinen esimerkki tällaisista tehtävistä ovat erilaiset sähköiset pörssikaupankäyntijärjestelmät, jotka hallitsevat kaupankäyntiistuntoja reaaliajassa. Tässä tarvitaan salausalgoritmeja, jotka tekevät mahdottomaksi järjestelmän toimintatietojen salauksen purkamisen istunnon aikana (tiedot tehdyistä tilauksista, tehdyistä kaupoista jne.), minkä jälkeen nämä tiedot ovat pääsääntöisesti jo hyödyttömiä hyökkääjille. . Toisin sanoen vaaditaan vain muutaman tunnin taattua sinnikkyyttä, mikä on kaupankäyntiistunnon tyypillinen pituus. On selvää, että täysimittaisen GOST:n käyttö tässä tilanteessa olisi tykin ampumista varpusiin.

Miten tässä ja vastaavissa tapauksissa edetä salauksen nopeuden lisäämiseksi? Vastaus on pinnalla - käytä salauksen muunnelmaa, jossa on vähemmän perusvaiheita (kierroksia) perusjaksoissa. Kuinka monta kertaa vähennämme salauskierrosten määrää, suorituskyky kasvaa saman verran. Tämä muutos voidaan saavuttaa kahdella tavalla - lyhentämällä avaimen pituutta ja vähentämällä avaimen "hakujaksojen" määrää. Muista, että perussalausjaksojen perusvaiheiden määrä on N=n m, Missä n on avaimen 32-bittisten elementtien lukumäärä, m- avainelementtien käyttöjaksojen lukumäärä standardissa n=8, m=4. Voit pienentää mitä tahansa näistä numeroista, mutta yksinkertaisin vaihtoehto on lyhentää avaimen pituutta vaikuttamatta sen käyttöjärjestelmään.

On selvää, että työn nopeuttamisen hinta on salauksen vahvuuden heikkeneminen. Suurin vaikeus on siinä, että tämän laskun suuruutta on melko vaikea arvioida enemmän tai vähemmän tarkasti. Ilmeisesti ainoa mahdollinen tapa tehdä tämä on tutkia salausmuunnoksia, joissa on "täysin" supistettu salausmuunnosjakso. On selvää, että ensinnäkin tämä edellyttää turvaluokiteltujen tietojen käyttöä, jotka vain GOSTin kehittäjät omistavat, ja toiseksi se on erittäin työlästä. Siksi yritämme nyt antaa erittäin, hyvin karkean arvion, joka perustuu vain yleisiin kaavoihin.

Mitä tulee salauksen kestävyyteen "laajuisilla" menetelmillä tapahtuvalle murtautumiselle eli "raakavoiman" hyökkäykselle, kaikki on enemmän tai vähemmän selvää: 64-bittinen avain on jossain partaalla, että se on tämän tyyppisen saatavilla. hyökkäyksen salaus, jonka avaimella on vähintään 96 bittiä (muista, että avaimen tulee sisältää kokonaislukumäärä 32-bittisiä elementtejä) on varsin vahva sitä vastaan. Todellakin, muutama vuosi sitten yhdysvaltalainen entinen salausstandardi DES joutui toistuvasti raa'alla voimalla hakkeroitumaan - ensin se hakkeroitiin maailmanlaajuisen Internetin pohjalta järjestetyn tietokoneverkon ja sitten erikoistuneen, ts. erityisesti tähän tarkoitukseen suunniteltu tietokone. Oletetaan, että GOST:n vakioversio, kun se on toteutettu nykyaikaisten prosessorien ohjelmistoissa, toimii neljä kertaa nopeammin kuin DES. Sitten 8-kierroksen "alennettu GOST" toimii 16 kertaa nopeammin kuin DES. Oletetaan myös, että DES-hakkeroinnin jälkeen laskentatekniikan suorituskyky on Mooren lain mukaan nelinkertaistunut. Tuloksena saamme, että nyt yhden 64-bittisen avaimen varmennus "pienennetylle GOST:lle" kahdeksalla jaksolla on 64 kertaa nopeampi kuin kerran yhden DES-avaimen varmennus suoritettiin. Näin ollen tämän GOST-version etu DES:iin verrattuna raa'an voiman hyökkäyksen monimutkaisuuden suhteen pienenee arvosta 2 64–56 = 2 8 = 256 arvoon 256 / 64 = 4 kertaa. Samaa mieltä, tämä on hyvin harhaanjohtava ero, melkein ei mitään.

On paljon vaikeampaa arvioida GOST:n heikenneiden muutosten kestävyyttä "intensiivisille" kryptausanalyysimenetelmille. Yleinen kuvio voidaan kuitenkin jäljittää tässäkin. Tosiasia on, että monien tällä hetkellä vahvimpien kryptausanalyysityyppien "profiili"-ominaisuudet riippuvat eksponentiaalisesti salauskierrosten lukumäärästä. Joten lineaarisessa krypta-analyysissä (LCA) tämä on lineaarisuusominaisuus L :

Missä C ja ovat vakioita, R on kierrosten lukumäärä. Samanlainen suhde on olemassa myös differentiaalisella kryptoanalyysillä. "Fyysisen merkityksensä" mukaan kaikki tämänkaltaiset ominaisuudet ovat todennäköisyyksiä. Yleensä kryptausanalyysiin tarvittavan alkudatan määrä ja sen monimutkaisuus ovat kääntäen verrannollisia tällaisiin ominaisuuksiin. Tästä seuraa, että nämä työvoimaintensiteetin indikaattorit kasvavat eksponentiaalisesti perussalausvaiheiden määrän kasvaessa. Siksi, kun kierrosten määrää vähennetään useita kertoja, tunnetuimpien analyysityyppien monimutkaisuus muuttuu hyvin likimääräisesti ja karkeasti tämän tehon juureksi alkuperäisestä määrästä. Tämä on erittäin suuri kestävyyden lasku.

Toisaalta GOST on suunniteltu suurella turvamarginaalilla ja se kestää nykyään kaikkia tunnettuja kryptoanalyysityyppejä, mukaan lukien differentiaali- ja lineaarianalyysi. Mitä tulee LCA:han, tämä tarkoittaa, että sen onnistuneeseen toteutukseen tarvitaan enemmän "avoin lohko – salattu lohko" -pareja kuin "luonnossa on", eli enemmän kuin 2 64 . Edellä esitetyn perusteella tämä tarkoittaa, että 16 kierroksen GOST:n onnistunut LCA edellyttää vähintään lohkoja tai 2 35 tavua tai 32 Gt tietoa ja 8 kierroksen GOST:n osalta vähintään lohkoja tai 2 19 tavua tai 0,5 megatavua.

Päätelmät kaikesta edellä mainitusta on esitetty seuraavassa taulukossa, jossa on yhteenveto GOST:n supistettujen versioiden ominaisuuksista.

Kierrosten lukumäärä	Avaimen koko, bitti	Nopean toiminnan indeksi	Salauksen todennäköiset ominaisuudet (erittäin karkea arvio)
24	192	1,33	Kestää useimpia tunnetuimpia KA-tyyppejä tai on vastustuksen partaalla. Varmentajan käytännön toteutus on mahdotonta lähtötiedon korkeiden vaatimusten ja työvoimaintensiteetin vuoksi.
16	128	2	Teoreettisesti se on epävakaa joillekin kryptausanalyysityypeille, mutta niiden käytännön toteutus on useimmissa tapauksissa vaikeaa lähtötiedon korkeiden vaatimusten ja työvoimaintensiteetin vuoksi.
12	95	2,67	Se ei kestä joitain tunnettuja kryptausanalyysityyppejä, mutta soveltuu pienten tietomäärien (jopa kymmenien tai satojen kilotavuiden) salassapitoon lyhyeksi ajaksi.
8	64	4	Se ei kestä joitain tunnettuja kryptausanalyysityyppejä, mutta se soveltuu varmistamaan pienten tietomäärien (jopa kymmenien kilotavujen) salassapito lyhyeksi ajaksi.

Kaksi viimeistä vaihtoehtoa, 12 ja 8 kierrosta, pystyvät tarjoamaan erittäin, hyvin rajoitetun suojan ajallisesti. Niiden käyttö on perusteltua vain tehtävissä, joissa vaaditaan vain lyhytaikaista, useiden tuntien luokkaa olevaa suljetun tiedon salassapitoa. Yksi mahdollinen sovellusalue näille heikkoille salakirjoille on sähköisten pörssikauppajärjestelmien UDP-liikenteen sulkeminen. Tässä tapauksessa jokainen datapaketti (datagrammi, keskimmäinen "D" UDP-lyhenteestä) salataan erillisellä 64-bittisellä avaimella ja itse avain on salattu istuntoavaimella (avain, jonka laajuus on yksi viestintäistunto kahden tietokoneen välillä ) ja lähetetään tietojen mukana.

Ennen kuin lopetan GOSTin supistettujen versioiden kanssa, sanon, että kaikki yllä olevat näkökohdat ovat erittäin spekulatiivisia. Standardi tarjoaa kestävyyden vain yhdelle, 32-kierroksiselle vaihtoehdolle. Ja kukaan ei voi antaa sinulle takuita siitä, että salauksen supistettujen muunnelmien murtumisvastus muuttuu yllä kuvatulla tavalla. Jos kuitenkin päätät käyttää niitä kehitystyössäsi, muista, että olet astunut hyvin horjuvalle maalle, joka voi pudota jalkojen alta minä hetkenä hyvänsä. Koska salausnopeus on sinulle kriittinen, sinun pitäisi ehkä harkita nopeamman salauksen tai tehokkaamman tietokoneen käyttöä? Toinen seikka, jonka vuoksi tämä kannattaa tehdä, on se, että heikennetyt GOST-versiot ovat mahdollisimman herkkiä käytettyjen korvaavien yksiköiden laadulle.

Käsillä olevalla ongelmalla on myös varjopuolensa. Entä jos salausnopeus ei ole kriittinen ja vahvuusvaatimukset ovat erittäin tiukat? GOSTin vastustuskyvyn lisäämiseksi on kaksi tapaa - kutsumme niitä ehdollisesti "laajaksi" ja "intensiiviseksi". Ensimmäinen näistä ei ole muuta kuin pelkkä salauskierrosten määrän lisääminen. Minulle ei ole täysin selvää, miksi tätä saattaisi todella tarvita, koska kotimainen standardi antaa jo ilman sitä tarvittavan vakauden. Jos kuitenkin kärsit paranoiasta yli vaaditun tason (ja kaikki "tiedonpuolustajat" ovat yksinkertaisesti velvollisia kärsimään siitä, tämä on ammattisoveltuvuuden ehto, ainoa kysymys on tapauksen vakavuus :), tämä auttaa sinua rauhoitu vähän. Jos olet epävarma tästä KGB-salauksesta tai käyttämästäsi korvaustaulukosta, tupla, nelinkertaista jne. kierrosten määrä - valitse moninkertaisuus tapauksesi vakavuuden perusteella. Tämän lähestymistavan avulla voit todella lisätä salauksen vahvuutta - jos aiemmin kryptausanalyysi oli yksinkertaisesti mahdotonta, nyt se on mahdotonta neliössä!

Hankalempi ja mielenkiintoisempi on kysymys siitä, onko mahdollista lisätä salauksen vahvuutta muuttamatta pääsalausvaiheiden määrää ja rakennetta. Yllättäen vastaus tähän kysymykseen on kyllä, vaikka poljemme jälleen spekulaation horjuvalla pohjalla. Tosiasia on, että GOST:ssa sen on tarkoitus korvata päämuunnosvaiheessa 4 bitillä 4, mutta käytännössä (puhumme tästä myöhemmin) kaikki ohjelmistototeutukset suorittavat korvaamisen tavu kerrallaan, ts. 8 x 8 bittiä - tämä tehdään tehokkuussyistä. Jos suunnittelemme tällaisen korvaavan välittömästi 8-bittiseksi, parannamme merkittävästi yhden kierroksen ominaisuuksia. Ensinnäkin "diffuusio"-ominaisuus tai "lumivyöry" -indikaattori kasvaa - yksi bitti lähdedataa ja/tai avain vaikuttaa useampaan tuloksen bitteihin. Toiseksi suuremmille substituutiosolmuille voidaan saavuttaa alhaisemmat differentiaaliset ja lineaariset ominaisuudet, mikä vähentää salauksen herkkyyttä samantyyppisille kryptausanalyysille. Tämä pätee erityisesti alennetuille GOST-sykleille ja 8- ja 12-kierrosvaihtoehdoille tällainen vaihe on yksinkertaisesti välttämätön. Tämä kompensoi jonkin verran kestävyyden menetystä, joka johtuu kierrosten määrän vähenemisestä. Tämän tekniikan käyttöä vaikeuttaa se, että sinun on suunniteltava tällaiset "lisätyt" korvaavat solmut itse. Ja myös se, että suurempia solmuja on yleensä huomattavasti vaikeampi suunnitella kuin pienempiä.

Epätyypillinen standardin käyttö.

Tietenkin GOST-salausalgoritmien päätarkoitus on tietojen salaus ja jäljitelmäsuojaus. Niitä löytyy kuitenkin muista sovelluksista, jotka liittyvät luonnollisesti tiedon suojaan. Puhutaanpa niistä lyhyesti:

1. Gamma-tilassa tapahtuvaa salausta varten GOST mahdollistaa kryptografisen gamman luomisen - bittisarjan, jolla on hyvät tilastolliset ominaisuudet ja korkea kryptografinen vahvuus. Lisäksi tätä gammaa käytetään avoimen tiedon muokkaamiseen, mikä johtaa salattuihin tietoihin. Tämä ei kuitenkaan ole ainoa mahdollinen kryptografisen gamman sovellus. Tosiasia on, että sen kehittämisen algoritmi on pseudosa(PRNG), jolla on erinomaiset ominaisuudet. Ei tietenkään ole kovin järkevää käyttää sellaista PRNG:tä, jossa vaaditaan vain generoidun sekvenssin tilastollisten ominaisuuksien saamista, eikä kryptografista vahvuutta tarvita, se ei ole kovin järkevää - näihin tapauksiin on olemassa paljon tehokkaampia generaattoreita. Mutta erilaisille tietoturvaan liittyville sovelluksille tällainen lähde on erittäin hyödyllinen:

• Kuten edellä todettiin, gammaa voidaan käyttää "raaka-aineena" avainten luomiseen. Tätä varten sinun tarvitsee vain saada halutun pituinen gammasegmentti - 32 tavua. Tällä tavalla avaimia voidaan tehdä tarpeen mukaan, eikä niitä tarvitse tallentaa - jos tällaista avainta tarvitaan uudelleen, se on tarpeeksi helppoa luoda uudelleen. Tarvitsee vain muistaa, millä avaimella se alun perin luotiin, mitä synkronointiviestiä käytettiin ja mistä generoidun gamman tavusta avain alkoi. Kaikki tiedot käytettyä avainta lukuun ottamatta eivät ole salaisia. Tällä lähestymistavalla on helppo hallita melko monimutkaista ja haarautunutta avainjärjestelmää käyttämällä vain yhtä "pääavainta".
• Samoin kuin edellisessä, gammaa voidaan käyttää salasanojen luomisen "raaka-aineena". Tässä voi herää kysymys, miksi niitä ylipäätään pitää generoida, eikö ole helpompaa keksiä niitä tarpeen mukaan. Tämän lähestymistavan epäonnistumisen osoittivat selvästi useita tietoverkoissa tapahtuneita tapauksia, joista suurin oli "Morris-madon" aiheuttama Internetin vuorokausivaihtelu marraskuussa 1988. Yksi tapa, jolla haittaohjelma tunkeutui tietokoneeseen, oli salasanan arvaus: ohjelma yritti päästä järjestelmään lajittelemalla peräkkäin useita satoja salasanoja sisäisestä luettelostaan, ja merkittävässä osassa tapauksia se onnistui. Ihmisen fantasia salasanojen keksimisessä osoittautui erittäin huonoksi. Siksi niissä organisaatioissa, joissa turvallisuuteen kiinnitetään asianmukaista huomiota, salasanat generoi ja jakaa käyttäjille turvajärjestelmän ylläpitäjä. Salasanan luominen on hieman monimutkaisempaa kuin avainten luominen, koska tässä tapauksessa "raaka" binäärigamma on muutettava merkkimuotoon, eikä vain "leikattava" paloiksi. Lisäksi yksittäiset arvot on ehkä hylättävä, jotta varmistetaan, että kaikki aakkosten merkit näkyvät yhtä todennäköisesti salasanassa.
• Toinen tapa käyttää kryptografista kirjoa on magneettisen median tietojen taattu poistaminen. Tosiasia on, että vaikka tiedot kirjoitetaan päälle magneettiselle välineelle, aiemmista tiedoista jää jälkiä, jotka voidaan palauttaa asianmukaisella tutkimuksella. Näiden jälkien tuhoamiseksi tällainen päällekirjoitus on suoritettava useita kertoja. Kävi ilmi, että tiedot joutuisivat kirjoittamaan uudelleen mediaan harvemmin, jos tällaisessa menettelyssä käytetään satunnaisia ​​tai näennäissatunnaisia ​​tietoja, jotka jäävät tuntemattomiksi asiantuntijoille, jotka yrittävät palauttaa päällekirjoitetun tiedon. Gammasalauksesta on hyötyä tässä.

2. Salauksen gamman lisäksi myös itse kryptografista muunnosa voidaan käyttää tarpeisiin, jotka eivät liity suoraan salaukseen:

• Tiedämme, että yksi tällaisista GOST-käyttömahdollisuuksista on simuloidun lisäyksen kehittäminen tietoryhmille. Minkä tahansa lohkosalauksen, mukaan lukien GOST, perusteella on kuitenkin melko helppoa rakentaa kaavio yksisuuntaisen hash-funktion laskemiseksi, jota kirjallisuudessa kutsutaan myös MDC:ksi, joka eri lähteissä tarkoittaa muuta tunnistuskoodia / manipulointi (M muutos/ M anipulaatio D etection C ode) tai viestin tiivistelmä (M essee D igest C oodi). Ensimmäinen dekoodaus ilmestyi kirjallisuudessa paljon aikaisemmin, toisen, lyhyemmän, mielestäni ne, jotka eivät muistaneet ensimmäistä :) - se oli vitsi. MDC:tä voidaan käyttää suoraan jäljitelmäsuojausjärjestelmissä jäljitelmän lisäyksen analogina, joka ei kuitenkaan riipu salaisesta avaimesta. Lisäksi MDC:tä käytetään laajasti elektronisissa digitaalisissa allekirjoitusjärjestelmissä (EDS), koska useimmat näistä menetelmistä on suunniteltu siten, että kiinteän kokoinen tietolohko on kätevä allekirjoittaa. Kuten tiedät, käsitellyn standardin GOST 28147-89 perusteella rakennetaan Venäjän federaation standardi yksisuuntaisen hash-funktion laskemiseksi GOST R34.11-94.
• Vähemmän tiedetään, että minkä tahansa lohkosalauksen, mukaan lukien GOST, perusteella voidaan rakentaa täysin toimiva EDS-järjestelmä, jossa on salainen allekirjoitusavain ja avoin varmennusyhdistelmä. Monista syistä tämä järjestelmä ei ole saanut laajaa käytännön leviämistä, mutta joissain tapauksissa sitä voidaan silti pitää erittäin houkuttelevana vaihtoehtona tällä hetkellä maailmassa vallitseville "matemaattisille" EDS-järjestelmille.

Kirjallisuus

Tietojenkäsittelyjärjestelmät. Kryptografinen suojaus. Kryptografinen muunnosalgoritmi GOST 28147-89. Osavaltio. Com. Neuvostoliitto standardien mukaan, M., 1989. ftp://ftp.wtc-ural.ru/pub/ru.crypt/GOST-28147
Shannon Claude. Salaisten järjestelmien matemaattinen teoria. Kokoelmassa "Työteoksia informaatioteoriasta ja kybernetiikasta", M., IL, 1963, s. 333-369. http://www.enlight.ru/crypto/articles/shannon/shann__i.htm
Federal Information Processing Standard (FIPS) 197, Advanced Encryption Standard (AES), Federal Register Voi. 66, nro. 235 / torstai 6. joulukuuta 2001 / Ilmoitukset, s. 63369–63371. http://csrc.nist.gov/encryption/aes/
Feistel Horst. Salaus ja tietoturva. A. Vinokurovin käännös, julkaisija Horst Feistel. Cryptography and Computer Privacy, Scientific American, toukokuu 1973, voi. 228, nro 5, s. 15-23. http://www.enlight.ru/crypto/articles/feistel/feist_i.htm
Schneier Bruce. Sovellettu kryptografia. 2. painos Protokollat, algoritmit ja lähdetekstit C-kielellä., M., "Triumph", 2002 http://www.ssl.stu.neva.ru/psw/crypto/appl_rus/appl_cryp.htm
Menezes Alfred, van Oorschot Paul, Vanstone Scott. Sovellettavan kryptografian käsikirja. http://www.cacr.math.uwaterloo.ca/hac/
Vinokurov Andrey. Miten lohkosalaus on rakennettu? Käsikirjoitus. http://www.enlight.ru/crypto/articles/vinokurov/blcyph_i.htm
Vinokurov Andrey. Salausongelmia sähköisessä iNFUSED BYTES -lehdessä verkossa. http://www.enlight.ru/crypto/articles/ib/ib.htm
Vinokurov Andrey, Primenko Eduard. Raportin teksti "Venäjän federaation ja Yhdysvaltojen salausstandardien ohjelmistojen käyttöönotosta", informatisointikonferenssi, Moskova, MEPhI, 28.-29.1.2001. Julkaistu konferenssijulkaisussa.
Tietotekniikka. Tietojen kryptografinen suojaus. Hash-funktio GOST R34.11-94, Gosstandart RF, M., 1994.

Tämä algoritmi on pakollinen käytettäväksi salausalgoritmina Venäjän federaation valtion organisaatioissa ja useissa kaupallisissa organisaatioissa.

Algoritmin kuvaus

Algoritmin kaavio on esitetty kuvassa. 3.1. Kuten näette, tämän algoritmin järjestelmä on melko yksinkertainen, mikä yksinkertaistaa yksiselitteisesti sen ohjelmisto- tai laitteistototeutusta.

GOST 28147-89 -algoritmi salaa tiedot 64-bittisiksi lohkoiksi, jotka on jaettu kahteen 32-bittiseen alilohkoon (N1 ja N2). Alilohko N1 käsitellään tietyllä tavalla, minkä jälkeen sen arvo lisätään

alilohkoarvolla N2 (lisäys suoritetaan modulo 2), sitten alilohkot vaihdetaan. Tällainen muunnos suoritetaan tietylle määrälle kierroksia: 16 tai 32, riippuen algoritmin toimintatavasta (kuvattu alla). Jokaisella kierroksella suoritetaan seuraavat toiminnot:

1. Näppäinpeitto. /VI-alilohkon sisältö lisätään modulo 2 32 avaimen Kx-osaan.

GOST 28147-89 -algoritmin salausavaimen mitta on 256 bittiä, ja Kx on sen 32-bittinen osa, eli 256-bittinen salausavain esitetään 32-bittisten aliavaimien ketjuna (kuva 3.2):

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

Salausprosessin aikana käytetään yhtä näistä aliavaimista riippuen pyöreästä numerosta ja algoritmin toimintatavasta.

Riisi. 3.1. Algoritmin kaavio GOST 28147-

Riisi. 3.2. GOST 28147-89 -algoritmin salausavain

2. Taulukko vaihto. Avaimen päällekkäisyyden jälkeen /VI-alilohko jaetaan 8 osaan, joissa on 4 bittiä, joiden jokaisen arvo korvataan yksitellen tämän alilohkon osan korvaustaulukon mukaisesti. Taulukkokorvauksia (Substitution box, S-box) käytetään usein nykyaikaisissa salausalgoritmeissa, joten niitä kannattaa harkita tarkemmin.

Taulukon korvaamista käytetään näin: sisäänmenoon syötetään tietyn mittainen (tässä tapauksessa 4-bittinen) datalohko, jonka numeerinen esitys määrää lähtöarvon numeron. Meillä on esimerkiksi seuraavan muotoinen S-laatikko:

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

Tulkoon 4-bittinen lohko "0100" eli arvo on 4. Taulukon mukaan lähdön arvoksi tulee 15, ts. "1111" (0 korvataan 4:llä, 1 korvataan 11:llä, 2:n arvo ei muutu jne.).

Kuten näette, algoritmin kaavio on hyvin yksinkertainen, mikä tarkoittaa, että suurin tiedon salauksen taakka lankeaa korvaaville taulukoille. Valitettavasti algoritmilla on se ominaisuus, että on olemassa "heikkoja" korvaustaulukoita, joiden avulla algoritmi voidaan paljastaa kryptausanalyyttisilla menetelmillä. Heikkoja ovat esimerkiksi taulukko, jossa tulos on yhtä suuri kuin syöte:

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

3. Bittikohtainen syklinen siirto vasemmalle 11 bittiä.

Algoritmitilat

GOST 28147-89 -algoritmilla on 4 toimintatilaa:

□ yksinkertainen vaihtotila;

□ gammatila;

P-pelitila, jossa palaute;

□ jäljitelmien liitteiden valmistustapa.

Nämä tilat poikkeavat jonkin verran yleisesti hyväksytyistä (kuvattu luvussa 1.4), joten niitä kannattaa pohtia tarkemmin.

Näillä tiloilla on erilaiset tarkoitukset, mutta ne käyttävät samaa salausmuunnosta, joka on kuvattu yllä.

Helppo vaihtotila

Yksinkertaisessa korvaustilassa yllä kuvatut 32 kierrosta suoritetaan yksinkertaisesti jokaisen 64-bittisen tietolohkon salaamiseksi. 32-bittisiä aliavaimia käytetään seuraavassa järjestyksessä:

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

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

Salauksen purku yksinkertaisessa korvaustilassa tehdään täsmälleen samalla tavalla, mutta hieman erilaisella aliavaimien käyttöjärjestyksellä:

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

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

Kuten tavallinen ECB-tila, lohkojen erillisestä salauksesta johtuen yksinkertaista korvaustilaa ei suositella todellisten tietojen salaamiseen; sitä tulisi käyttää vain muiden salausavaimien salaamiseen moniavaimen järjestelmissä.

Gamma-tila

Gammatilassa (kuva 3.3) jokainen selkeän tekstin lohko lisätään bitti bitiltä modulo 2 salauksen gammalohkoon, jonka koko on 64 bittiä. Salausgamma on erityinen sekvenssi, joka luodaan käyttämällä yllä kuvattuja muunnoksia seuraavasti:

1. Rekistereihin N1 ja N2 kirjoitetaan niiden alkutäyttö - 64-bittinen arvo, jota kutsutaan "synkronointiviestiksi" (synkronointisanoma on itse asiassa alustusvektorin analogi CBC-, CFB- ja OFB-tiloissa ).

2. /VI- ja N2-rekisterien sisältö (tässä tapauksessa synkronointiviestit) salataan yksinkertaisessa korvaustilassa.

3. N1:n sisältö lisätään modulo (2 32 - 1) vakiolla CI = 2 24 + 2 16 + 2 8 + 4 , lisäyksen tulos kirjoitetaan /VI-rekisteriin.

4. N2:n sisältö lisätään modulo 2 vakiolla C2 = 2 24 + 2 16 + 2 8 +1, summauksen tulos kirjoitetaan rekisteriin N2.

5. /VI- ja N2-rekisterien sisältö tulostetaan 64-bittisenä salauksen gammalohkona (eli tässä tapauksessa /VI ja N2 muodostavat ensimmäisen gammalohkon).

6. Jos tarvitaan seuraava gammalohko (eli salausta tai salauksen purkamista on jatkettava), palaa vaiheeseen 2.

Salauksen purkamista varten generoidaan gamma samalla tavalla, minkä jälkeen XOR-toimintoa sovelletaan jälleen salatekstiin ja gammabitteihin.

Luodakseen saman salausgamman salauksen salauksen purkavalla käyttäjällä on oltava sama avain ja sama synkronointiviestin arvo, joita käytettiin tietojen salaamiseen. Muuten et voi saada alkuperäistä tekstiä salatusta tekstistä.

Useimmissa GOST 28147-89 -algoritmin toteutuksissa synkronointiviesti ei ole salainen elementti, mutta synkronointiviesti voi olla yhtä salainen kuin salausavain. Tässä tapauksessa voidaan katsoa, ​​että algoritmiavaimen tehollinen pituus (256 bittiä) kasvaa synkronointiviestin vielä 64 bitillä, jota voidaan pitää lisäavainelementtinä.

Palaute gamma -tila

Palaute-gammatilassa 2. lohkosta alkaen /VI- ja L/2-rekisterit täytetään ei edellisellä gammalohkolla, vaan edellisen selväkielilohkon salauksen tuloksella (kuva 3.4). Ensimmäinen lohko tässä tilassa luodaan täsmälleen samalla tavalla kuin edellinen.

Riisi. 3.4. Salausgamman luominen gammatilassa palautteen avulla

Imitaattorin generointitila

Huijaus on salauksen tarkistussumma, joka lasketaan salausavaimella ja on suunniteltu tarkistamaan viestien eheys. Sen laskemiseksi on GOST 28147-89 -algoritmin erityinen tila.

Etuliitteen jäljitelmä luodaan seuraavasti:

1. Ensimmäinen 64-bittinen tietolohko, jolle imitaattori lasketaan, kirjoitetaan rekistereihin N1 ja N2 ja salataan pelkistetyssä yksinkertaisessa korvaustilassa, jossa suoritetaan ensimmäiset 16 kierrosta 32:sta.

2. Saatu tulos summataan modulo 2 seuraavan tietolohkon kanssa, jolloin tulos tallennetaan N1:een ja N2:een.

3. M ja N2 salataan jälleen pelkistetyssä vaihtomuodossa ja niin edelleen viimeiseen tietolohkoon asti.

Etuliitteen katsotaan olevan rekisterien N1 ja N2 tuloksena oleva 64-bittinen sisältö tai osa siitä. Useimmiten käytetään 32-bittistä etuliitettä, eli puolet rekisterien sisällöstä. Tämä riittää, koska, kuten mikä tahansa tarkistussumma, jäljitelmäetuliite on tarkoitettu ensisijaisesti suojaamaan vahingossa tapahtuvalta tietojen vääristymiseltä. Tietojen tahallisen muuttamisen estämiseksi käytetään muita salausmenetelmiä - ensisijaisesti sähköistä digitaalista allekirjoitusta (katso kohta 1.1).

Jäljitelmäetuliitettä käytetään seuraavasti:

1. Kun mitä tahansa tietoa salataan, selvätekstijäljitelmä lasketaan ja lähetetään salatekstin mukana.

2. Dekoodauksen jälkeen jäljitelmäetuliite lasketaan uudelleen ja sitä verrataan lähetettyyn.

3. Jos lasketut ja lähetetyt jäljitelmäetuliitteet eivät täsmää, salateksti on vääristynyt lähetyksen aikana tai salauksen purkamisen aikana on käytetty vääriä avaimia.

Jäljitelmäetuliite on erityisen hyödyllinen avaintietojen oikean salauksen tarkistamiseen käytettäessä moniavainjärjestelmiä.

Jäljitelmäetuliite on jonkin verran analogia MAC-sanoman todennuskoodille, joka on laskettu CBC-tilassa; ero on siinä, että etuliitelaskenta ei käytä synkronointiviestiä, kun taas MAC-laskennassa käytetään alustusvektoria.

Algoritmin kryptografinen vahvuus

Vuonna 1994 GOST 28147-89 -algoritmin kuvaus käännettiin englanniksi ja julkaistiin; tämän jälkeen ulkomaisten asiantuntijoiden suorittaman analyysin tulokset alkoivat ilmestyä; Käytännöllisiä hyökkäyksiä ei kuitenkaan löydetty merkittävään aikaan.

□ suuri avaimen pituus - 256 bittiä; yhdessä salaisen synkronointiviestin kanssa tehollinen avaimen pituus kasvaa 320 bittiin;

□ 32 muunnoskierrosta; jo 8 kierroksen jälkeen saavutetaan syötetietojen hajoamisen täysi vaikutus: selvätekstilohkon yhden bitin muuttaminen vaikuttaa kaikkiin salatekstilohkon bitteihin ja päinvastoin, eli on olemassa moninkertainen turvamarginaali.

Harkitse GOST 28147-89 -algoritmin kryptausanalyysin tuloksia.

Korvaustaulukoiden analyysi

Koska standardissa ei anneta korvaustaulukoita, useat teokset (esimerkiksi in) viittaavat siihen, että "pätevä organisaatio" voi laatia sekä "hyviä" että "huonoja" korvaustaulukoita. Kuuluisa asiantuntija Bruce Schneier kuitenkin kutsuu tällaisia ​​oletuksia "huhuiksi". On selvää, että algoritmin kryptografinen vahvuus riippuu pitkälti käytettyjen korvaustaulukoiden ominaisuuksista, vastaavasti on heikkoja korvaustaulukoita (katso esimerkki yllä), joiden käyttö voi yksinkertaistaa algoritmin hyökkäystä. Mahdollisuus käyttää erilaisia ​​korvaustaulukoita näyttää kuitenkin olevan erittäin kannatettava idea, jota tukevat seuraavat kaksi tosiasiaa DES-salausstandardin historiasta (katso lisätietoja osiosta 3.15):

□ DES-algoritmin lineaarista ja differentiaalista kryptausanalyysiä käyttävät hyökkäykset käyttävät korvaustaulukoiden erityispiirteitä; käytettäessä muita taulukoita kryptausanalyysi on aloitettava alusta;

□ DES:ää on yritetty vahvistaa lineaarista ja differentiaalista kryptausanalyysiä vastaan ​​käyttämällä vahvempia korvaustaulukoita; sellaisia ​​taulukoita, jotka ovat todellakin vakaampia, on ehdotettu esimerkiksi s 5 DES -algoritmissa; mutta valitettavasti DES:n korvaaminen s 5 DES:llä oli mahdotonta, koska korvaavat taulukot on määritelty tiukasti standardissa, joten algoritmin toteutukset eivät todennäköisesti tue mahdollisuutta vaihtaa taulukoita muihin.

Useissa teoksissa (esimerkiksi , ja ) päätellään virheellisesti, että GOST 28147-89 -algoritmin salaiset korvaustaulukot voivat olla osa avainta ja lisätä sen tehollista pituutta (mikä ei ole merkittävää, koska algoritmilla on erittäin suuri 256-bittinen avain). Työ kuitenkin osoittaa, että salaiset korvaustaulukot voidaan laskea seuraavalla käytännössä sovellettavalla hyökkäyksellä:

1. Aseta nolla-avain ja etsi "nollavektori", eli arvo z = /(0), missä /() on algoritmin pyöreä funktio. Tämä vaihe kestää noin 2 salausoperaatiota.

2. Nollavektorin avulla lasketaan korvaustaulukoiden arvot, mikä kestää enintään 2 11 operaatiota.

Algoritmien modifikaatiot ja niiden analysointi

Työssä suoritettiin GOST 28147-89 -algoritmin muutosten kryptausanalyysi:

□ GOST-H-algoritmi, jossa aliavaimien käyttöjärjestystä muutetaan alkuperäiseen algoritmiin verrattuna, eli kierroksittain 25:stä 32:een aliavaimia käytetään suorassa järjestyksessä, eli samalla tavalla kuin edellisessä. algoritmin kierrokset ;

□ 20 kierroksen GOST®-algoritmi, joka käyttää XOR:ta modulo 2 32:n sijaan avaimen päällekkäisyyteen.

Analyysin tulosten perusteella pääteltiin, että GOST-H ja GOST© ovat heikompia kuin alkuperäinen GOST 28147-89 -algoritmi, koska molemmilla on heikkojen avainten luokkia. On syytä huomata, että GOST©-kryptausanalyysin kannalta teos toistaa sanasta sanaan GOST 28147-89 -algoritmin kryptausanalyysin osio, joka julkaistiin vuonna 2000 tunnetussa teoksessa (ilman viittausta alkuperäiseen). Tämä asettaa kyseenalaiseksi teoksen tekijöiden ammattitaidon ja sen muut tulokset.

Työssä ehdotetaan erittäin mielenkiintoinen algoritmin muunnos: taulukoiden S \ ... Ss on välttämättä oltava erilaisia; jokaisella algoritmin kierroksella ne on muutettava tietyn lain mukaan. Tämä permutaatio voi olla riippuvainen salausavaimesta tai se voi olla salainen (eli olla osa suurempaa salausavainta kuin alkuperäinen 256-bittinen avain). Molemmat vaihtoehdot lisäävät kirjoittajiensa mukaan merkittävästi algoritmin vastustuskykyä lineaarista ja differentiaalista kryptausanalyysiä vastaan.

Ja työssä esitetään vielä yksi korvaustaulukoihin liittyvä muunnos, jossa analysoidaan yhtä mahdollisista menetelmistä substituutiotaulukoiden laskemiseksi salausavaimen perusteella. Työn kirjoittajat päättelivät, että tällainen riippuvuus heikentää algoritmia, koska se johtaa heikkojen avainten esiintymiseen ja joihinkin algoritmin mahdollisiin haavoittuvuuksiin.

Koko kierroksen algoritmianalyysi

Hyökkäyksiä on myös koko kierroksen GOST 28147-89:ää vastaan ​​ilman muutoksia. Yksi ensimmäisistä avoimista töistä, jossa algoritmin analyysi suoritettiin, hyvin tunnettu työ, on omistettu hyökkäyksille, jotka hyödyntävät useiden tunnettujen salausalgoritmien avainten laajennusprosessin heikkouksia. Erityisesti täyden kierroksen algoritmi GOST 28147-89 voidaan rikkoa käyttämällä differentiaalista kryptausanalyysiä linkitetyissä avaimissa, mutta vain jos käytetään heikkoja korvaustaulukoita. Algoritmin 24 kierroksen versio (josta puuttuu ensimmäiset 8 kierrosta) avataan samalla tavalla kaikille korvaustaulukoille, mutta vahvat korvaustaulukot (esimerkiksi kohdassa ) tekevät tällaisesta hyökkäyksestä ehdottoman epäkäytännöllisen.

Kotimaiset tutkijat A. G. Rostovtsev ja E. B. Makhovenko ehdottivat vuonna 2001 pohjimmiltaan uutta kryptausanalyysimenetelmää (tekijöiden mukaan se on huomattavasti tehokkaampi kuin lineaarinen ja differentiaalinen kryptausanalyysi) muodostamalla tavoitefunktion tunnetusta selkeästä tekstistä, joka vastaa sitä salatekstiä ja haluttua arvoa. avaimesta ja löytää sen ääriarvo, joka vastaa avaimen todellista arvoa. He löysivät myös suuren luokan GOST 28147-89 -algoritmin heikkoja avaimia, joiden avulla voit avata algoritmin käyttämällä vain 4 valittua selkeää tekstiä ja niitä vastaavia salatekstejä, joiden monimutkaisuus on melko pieni. Algoritmin kryptausanalyysiä jatketaan työssä.

Vuonna 2004 korealainen asiantuntijaryhmä ehdotti hyökkäystä, jolla käyttämällä toisiinsa liittyvien avainten differentiaalista kryptausanalyysiä on mahdollista saada 91,7 %:n todennäköisyydellä 12 bittiä salaista avainta. Hyökkäys vaatii 235 valittua selkeää tekstiä ja 236 salaustoimintoa. Kuten näette, tämä hyökkäys on käytännössä hyödytön algoritmin todelliselle avaamiselle.