«Mens du lever, ikke dø, se på denne verden.
Mange her har en død sjel – de er døde innvendig.
Men de går og ler, uten å vite at de ikke er der,
Ikke skynd deg med dødstiden din, sa hun til meg.

Aria, "Der oppe"

1. Introduksjon

1. Introduksjon til blokkchiffere

2.1 Feistel nettverk.
2.2 Blokkchiffer GOST 28147-89

1. Teoretisk minimum

3.1 Nøkkelinformasjon
3.2 Grunnleggende trinn i kryptokonvertering

3.3 Grunnleggende sykluser:“ 32-Z” , “ 32-P” .

1. Øve på

4.1 Implementering av hovedkryptokonverteringstrinnet
4.2 Øke hastigheten på algoritmen
5.
6. Liste over brukt litteratur
7. Anerkjennelser

Introduksjon.

Dette dokumentet er mitt forsøk på å beskrive en metode for ganske enkelt å erstatte GOST 28147-89-krypteringsalgoritmen med det enkleste, men likevel teknisk kompetente språket. Leseren vil si sin mening om hvor godt jeg lyktes etter å ha lest de seks første punktene.

For at arbeidet mitt skal være mer nyttig, anbefaler jeg å bevæpne deg med verkene til forfatterne som er angitt i listen over brukt litteratur. En kalkulator anbefales også slik at den har en funksjon for å beregne operasjonen XOR, fordi lesing av artikkelen antar at leseren har til hensikt å studere denne krypteringsalgoritmen. Selv om den også egner seg som referanseguide, skrev jeg denne artikkelen spesifikt som en opplæringsartikkel.

Introduksjon til blokkchiffer.

Før vi begynner å se på algoritmen, må vi gjøre oss kjent med historien om opprettelsen av denne typen chiffer. Algoritmen tilhører kategorien blokkchiffer, i arkitekturen hvis informasjon er delt inn i et begrenset antall blokker, den siste kan naturligvis ikke være komplett. Krypteringsprosessen skjer nøyaktig over hele blokker, som danner chiffergrammet. Den siste blokken, hvis den er ufullstendig, er supplert med noe (jeg vil snakke om nyansene ved fullføringen nedenfor) og krypteres på samme måte som komplette blokker. Med chiffergram mener jeg resultatet av at krypteringsfunksjonen virker på en viss mengde data som brukeren sendte inn for kryptering. Med andre ord er et chiffergram det endelige resultatet av kryptering.

Historien om utviklingen av blokkchiffer er assosiert med tidlig på 70-tallet, da IBM-selskapet, som innså behovet for å beskytte informasjon ved overføring av data over datakommunikasjonskanaler, begynte å implementere sitt eget vitenskapelige forskningsprogram viet til beskyttelse av informasjon i elektronisk nettverk, inkludert kryptografi.

En gruppe forskere og utviklere fra IBM, som begynte å forske på krypteringssystemer med et symmetrisk nøkkelskjema, ble ledet av Dr. Horst Feistel.

2.1 Feistel-nettverk

Arkitekturen til den nye krypteringsmetoden foreslått av Feistel i klassisk litteratur ble kalt "Feistel Architecture", men for øyeblikket i russisk og utenlandsk litteratur brukes et mer etablert begrep - "Feistel-nettverk" eller Feistel's NetWork. Deretter ble "Lucifer"-chifferet bygget ved å bruke denne arkitekturen - som senere ble publisert og forårsaket en ny bølge av interesse for kryptografi generelt.

Ideen til Feistel-nettverksarkitekturen er som følger: inndatastrømmen er delt inn i blokker med n bits i størrelse, der n er et partall. Hver blokk er delt inn i to deler - L og R, deretter mates disse delene inn i et iterativt blokkchiffer, der resultatet av det j-te trinnet bestemmes av resultatet av forrige trinn j-1! Dette kan illustreres med et eksempel:

Ris. 1

Hvor funksjon A er hovedhandlingen til et blokkchiffer. Det kan være en enkel handling, for eksempel XOR-operasjonen, eller den kan ha en mer kompleks form og være en sekvens av en rekke enkle handlinger - modulo-addisjon, venstreforskyvning, elementerstatning osv., sammen danner disse enkle handlingene såkalte hovedtrinn i kryptokonvertering.

Det skal bemerkes at nøkkelelementene i funksjonens drift er tilførselen av nøkkelelementer og XOR-operasjonen, og hvor godt disse operasjonene er gjennomtenkt indikerer den kryptografiske styrken til chifferen som helhet.

For at ideen om Feistel-nettverk skal være helt klar, la oss vurdere den enkleste saken som er avbildet i ris. 1, hvor i funksjon A – vil operasjonene “mod 2” (“xor”) vises, men dette enkleste tilfelle, i en mer alvorlig situasjon, for eksempel ved å skjule informasjon av nasjonal betydning, kan funksjon A være mer kompleks (så vidt jeg har sett, kan funksjon A faktisk være veldig kompleks):

Opprinnelige data:

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

Få krypteringskoden

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

L=0101b, R=1010b

La oss forklare handlingene våre:

1. Denne operasjonen er tilleggsmod 2 4. I praksis kommer en slik operasjon ned til enkel addisjon, hvor vi må legge til to tall og ignorere bære inn i det femte sifferet. Siden, hvis vi setter eksponenter over sifrene i den binære representasjonen av et tall, vil det være en eksponent fire over det femte sifferet, la oss ta en titt på figuren nedenfor, som viser handlingene til operasjonen vår:

Ris. 2

Her pekte jeg med en pil til eksponentene, som du ser burde resultatet vært 10100, men siden mod 2 4-operasjonen ignorerer carryen får vi 0100.

1. Denne operasjonen kalles mod 2 i litteraturen, og implementeres på assemblerspråk av kommandoen XOR. Men det mer korrekte navnet er mod 2 1. Uten denne unike operasjonen er det neppe mulig å bygge en rask, lett implementert krypteringsalgoritme og samtidig ha den ganske kryptobestandig. Det unike med denne operasjonen ligger i det faktum at det er det motsatte av seg selv! For eksempel, hvis tallet A er XORED med tallet B, er resultatet B. I fremtiden er det nok å XOR tallene B og C med hverandre for å få den forrige verdien av A!

I denne operasjonen fikk vi 1010 med tallene 1110 og 0100, for å få 1110 tilbake, er det nok å XOR tallene 0100 og 1010 med hverandre! Du kan lese mer om denne operasjonen i artikkelen vedlagt nettstedet. www.wasm.ru, « Grunnleggende veiledning tilCRC_error deteksjonsalgoritmer» forfatteren som Ross N. Williams. I dette arbeidet er det et poeng - " 5. Binær aritmetikk uten bærer" Det er i denne artikkelen operasjonen er beskrevet. xor! Jeg utbryter fordi i denne artikkelen er denne operasjonen så beskrevet at leseren ikke bare forstår hvordan denne operasjonen fungerer, han begynner den til og med se, hør og føl!

1. Denne handlingen er nødvendig slik at de opprinnelige verdiene kan oppnås ved dekryptering av chiffergrammet.

2.2 Blokkchiffer GOST 28147-89

GOST 28147 – 89-krypteringsalgoritmen tilhører kategorien blokkchiffer som fungerer i henhold til arkitekturen til balanserte Feistel-nettverk, der to deler av den valgte informasjonsblokken er like store. Algoritmen ble utviklet i innvollene til den åttende avdelingen av KGB, nå omgjort til FAPSI, og ble etablert som krypteringsstandarden til den russiske føderasjonen tilbake i 1989 under USSR.

For at denne algoritmemetoden skal fungere, er det nødvendig å dele informasjonen inn i blokker på 64 bits i størrelse. Generer eller skriv inn i krypteringssystemet følgende nøkkelinformasjon: nøkkel og erstatningstabell. Valg av nøkkel og erstatningstabell ved kryptering bør tas svært alvorlig, fordi Dette er grunnlaget for sikkerheten til informasjonen din. For informasjon om hvilke krav som stilles til nøkkelen og erstatningstabellen, se avsnittet "Krav til nøkkelinformasjon".

Når vi vurderer metoden vil vi ikke fokusere på dette, fordi denne artikkelen, som jeg sa ovenfor, ble skrevet med mål om å lære leseren hvordan man krypterer data ved å bruke metoden for å ganske enkelt erstatte en gitt krypteringsalgoritme, men vi vil definitivt berøre dette problemet på slutten av artikkelen.

Teoretisk minimum.

3.1 Nøkkelinformasjon

Som jeg sa ovenfor, deltar følgende aktivt i datakryptering:

3.1.1. En nøkkel er en sekvens av åtte elementer, hver 32 biter i størrelse. Videre vil vi betegne den med symbolet K, og elementene den består av er k1, k2, k3, k4, k5, k6, k7, k8.

3.1.2 Erstatningstabell – en matrise med åtte rader og seksten kolonner, heretter kalt Hij. Hvert element i skjæringspunktet mellom rad i og kolonne j opptar 4 biter.

Hovedhandlingen i krypteringsprosessen er hovedtrinnet i kryptokonvertering. Dette er ikke noe mer enn handlingen med å kryptere data ved hjelp av en viss algoritme, bare utviklerne introduserte et veldig tungvint navn :).

Før kryptering begynner, deles blokken i to deler L og R, 32 bit hver. De velger et nøkkelelement og mater først deretter disse to delene av blokken, nøkkelelementet og erstatningstabellen inn i hovedtrinnsfunksjonen Resultatet av hovedtrinnet er én iterasjon av grunnsyklusen, som vil bli diskutert i neste avsnitt. Hovedtrinnet består av følgende:

1. Addisjonsdelen av blokken R summeres med nøkkelelementet K mod 2 32. Jeg beskrev en lignende operasjon ovenfor, her er det samme, bare eksponenten er ikke "4", men "32" - resultatet av denne operasjonen vil bli ytterligere betegnet av Smod.
2. Vi deler det tidligere oppnådde resultatet Smod i fire-bits elementer s7, s6, s5, s4, s3, s2, s1, s0 og mater det inn i erstatningsfunksjonen. Erstatningen skjer som følger: velg elementet Smod - s i , start fra begynnelsen med det laveste elementet, og erstatt det med verdien fra erstatningstabellen for i - raden og kolonnen angitt med verdien til elementet s i . Vi går til s i +1 element og fortsetter på samme måte og fortsetter til vi erstatter verdien av det siste elementet Smod - resultatet av denne operasjonen vil bli betegnet som, Ssimple.
3. I denne operasjonen forskyves verdien av Ssimple syklisk til venstre med 11 biter og vi får Srol.
4. Vi velger den andre delen av blokk L og legger til mod 2 med Srol, som et resultat har vi Sxor.
5. På dette stadiet blir L-delen av blokken lik verdien av R-delen, og R-delen initialiseres i sin tur av resultatet av Sxor og dette er slutten på hovedtrinnsfunksjonen!

3.3 Grunnleggende sykluser: "32-Z", "32-R".

For å kryptere informasjon, må den deles inn i blokker med 64 bits størrelse, naturlig nok kan den siste blokken være mindre enn 64 biter. Dette faktum er akilleshælen til denne "enkle erstatningsmetoden". Siden tillegget til 64 biter er en svært viktig oppgave for å øke den kryptografiske styrken til chiffergrammet, vil dette sensitive stedet, hvis det er tilstede i utvalget av informasjon, og det ikke er det (for eksempel en fil på 512 byte i størrelse !), bør behandles med stort omsorgsansvar!

Etter at du har delt informasjonen i blokker, bør du dele nøkkelen i elementer:

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

Selve kryptering består av å bruke såkalte basissykluser. Som igjen inkluderer det n-te antallet grunnleggende kryptokonverteringstrinn.

Grunnsykluser er, hvordan skal jeg si det, merket: n – m. Hvor n er antall hovedkryptokonverteringstrinn i basissyklusen, og m er "typen" til basissyklusen, dvs. Hva snakker vi om, "Z"-kryptering eller "R"-kryptering av data.

Den grunnleggende krypteringssyklusen 32-3 består av 32 hovedtrinn for kryptotransformasjon. Funksjonen som implementerer trinnhandlingene leveres med blokk N og nøkkelelement K, hvor det første trinnet skjer med k1, det andre over det oppnådde resultatet med element k2, osv. etter følgende skjema:

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

Dekrypteringsprosessen for 32-P skjer på lignende måte, men nøkkelelementene leveres i omvendt rekkefølge:

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

Øve på.

Etter at vi ble kjent med teorien om hvordan man krypterer informasjon, var det på tide å se hvordan kryptering skjer i praksis.

Opprinnelige data:

La oss ta informasjonsblokken N = 0102030405060708h, her er deler L og R like:

L = 01020304h, R =05060708h, ta nøkkelen:

K = ' as28 zw37 q839 7342ui23 8e2t wqm2 ewp1' (disse er ASCII-koder, for å se den heksadesimale representasjonen kan du åpne denne filen i visningsmodus i Total Commander ved å trykke på " F3"og deretter nøkkelen" 3 "). I denne nøkkelen vil elementverdiene være:

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

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

La oss også ta følgende erstatningstabell:

Ris. 3

Her er radene nummerert fra 0 til 7, kolonner fra 0 til F.

Advarsel: All informasjon, inkludert nøkkelen med erstatningstabellen, er tatt som eksempel for å vurdere algoritmen!

Ved å bruke "Input Data" er det nødvendig å oppnå resultatet av hovedtrinnet med kryptokonvertering.

1. Vi velger delen R = 05060708h og nøkkelelementet k1 = 'as28', i heksadesimal form vil nøkkelelementet se slik ut: 61733238h. Nå utfører vi summeringsoperasjonen mod 2 32:

Ris. 4

Som du kan se i figuren, hadde vi ikke en overføring til 33 biter merket med rødt og med eksponenten " 32 " Og hvis vi hadde andre verdier for R og nøkkelelementet, kunne dette godt skje, og da ville vi ignorert det, og i fremtiden ville vi bare bruke bitene merket med gult.

Jeg utfører denne operasjonen ved å bruke assembler-kommandoen Legg til:

; eax = R, ebx = 'as28'

Resultatet av denne operasjonen er Smod = 66793940h

1. Nå er dette den mest vanskelige operasjonen, men hvis du ser nærmere etter, er den ikke lenger så skummel som den ser ut til å begynne med. La oss forestille oss Smod i følgende form:

FIGUR IKKE LAGRET

Ris. 5

Jeg prøvde å visualisere Smod-elementene i figuren, men jeg skal forklare likevel:

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

Nå, med utgangspunkt i det laveste elementet s0, gjør vi erstatningen. Husker poenget " 3.2 Grunnleggende trinn for kryptokonvertering» i – rad, s i – kolonne, se etter verdien i nullraden og nullkolonnen:

Fig.6

Så den nåværende verdien av Smod er ikke 6679394 0 h, a 6679394 5 h.

La oss begynne å erstatte s1, dvs. fire. Bruke første rad og fjerde kolonne (s1= 4!). La oss se på bildet:

Ris. 7

Nå er verdien Smod, ikke 667939 4 5h, 667939 2 5t. Jeg antar at erstatningsalgoritmen nå er tydelig for leseren, og jeg kan si at etter dette vil det endelige resultatet av Ssimple ha følgende verdi - 11e10325h.

Jeg vil snakke om hvordan dette lettest kan implementeres i form av assembler-kommandoer senere i neste avsnitt, etter at jeg har snakket om den utvidede tabellen.

1. Vi må flytte den resulterende Ssimple-verdien 11 biter til venstre.

Ris. 8

Som du kan se, er denne handlingen ganske enkel, og implementeres med en assembly-språkkommando - rolle og resultatet av denne operasjonen Srol er 0819288Fh.

1. Nå gjenstår det bare å XOR delen L av informasjonsblokken vår med verdien Srol. Jeg tar en kalkulator fra w2k sp4 og får Sxor = 091b2b8bh.
2. Denne handlingen er endelig, og vi tildeler, renser R, verdien av del L, og initialiserer del L med verdien av Sxor.

Endelig resultat:

L = 091b2b8bh, R = 01020304h

4.2 Øk hastigheten på algoritmen

La oss nå snakke om å optimalisere algoritmen for hastighet. Når du implementerer ethvert prosjekt, må du ta i betraktning at et program som fungerer med registre oftere enn med minne, fungerer raskest, og her er denne dommen også veldig viktig, fordi over en blokk med informasjon er det så mange som 32 krypteringshandlinger!

Da jeg implementerte krypteringsalgoritmen i programmet mitt, gjorde jeg følgende:

1. Jeg valgte en del av blokken L inn i eax-registeret, og R inn i edx-registeret.
2. esi-registeret ble initialisert med adressen til den utvidede nøkkelen, mer om det nedenfor.
3. ebx-registeret ble tildelt verdien til adressen til det utvidede erstatningsbordet, mer om det nedenfor
4. Overførte informasjonen til punktene 1,2, 3 til funksjonen til grunnsyklusen 32 - Z eller 32 - R, avhengig av situasjonen.

Hvis du ser på forsyningsdiagrammet for nøkkelelementene i avsnitt " Grunnleggende sykluser: "32-Z", "32-R"", så kan nøkkelen vår for grunnsyklusen 32 - Z representeres som følger:

K 32-Z =

'as28','zw37','q839','7342','ui23','8e2t','wqm2','ewp1',

'as28','zw37','q839','7342','ui23','8e2t','wqm2','ewp1',

'ewp1','wqm2','8e2t','ui23','7342','q839','zw37','as28'

De. fra begynnelsen er det k1, k2, k3, k4, k5, k6, k7, k8 - ‘ as28', 'zw37', 'q839', '7342', 'ui23', '8e2t', 'wqm2', 'ewp1' Denne sekvensen gjentas tre ganger. Da går elementene i omvendt rekkefølge, dvs.: k8,k7,k6,k5,k4,k3,k2,k1 - 'ewp1', 'wqm2', '8e2t', 'ui23', '7342', 'q839', 'zw37', 'as28'.

Jeg forhåndsarrangerte elementene i arrayet i den rekkefølgen de skulle mates inn i 32 - Z. Dermed økte jeg minnet som kreves per tur, men reddet meg fra noen tenkeprosesser som jeg ikke trengte, og økte hastigheten på algoritme, for ved å redusere minnetilgangstid! Her beskrev jeg bare nøkkelen for 32 - Z, for syklus 32 - P gjorde jeg det samme, men ved å bruke et annet opplegg for å levere elementer, som jeg også beskrev i avsnitt " Grunnleggende sykluser: "32-З", "32-Р"».

Det er på tide å beskrive implementeringen av erstatningsfunksjonen, som jeg lovet ovenfor. Jeg kunne ikke beskrive det tidligere, fordi... dette krever innføring av et nytt konsept - en utvidet substitusjonstabell. Jeg kan ikke forklare deg hva det er. I stedet skal jeg vise deg det, og du kan selv formulere hva det er – en utvidet erstatningstabell?

Så for å forstå hva et utvidet erstatningsbord er, trenger vi et erstatningsbord; for eksempel tar jeg det som er vist i fig. 3.

For eksempel måtte vi erstatte nummeret 66793940h. Jeg vil presentere den i følgende form:

FIGUR IKKE LAGRET

Ris. 9

Hvis vi nå tar elementene s1, s0, dvs. lav byte, vil resultatet av erstatningsfunksjonen være lik 25h! Etter å ha lest artikkelen av Andrei Vinokurov, som jeg siterte i avsnitt " Liste over brukt litteratur", vil du faktisk finne at hvis du tar to strenger kan du få en array, som lar deg raskt finne erstatningselementer ved å bruke en assembler-kommando xlat. De sier det er en annen raskere måte, men Andrei Vinokurov brukte omtrent fire år på å undersøke raske algoritmer for implementering av GOST! Jeg tror det ikke er nødvendig å finne opp hjulet på nytt når det allerede eksisterer.

Så om matrisen:

La oss ta de to første linjene, null og første, og lage en matrise på 256 byte. Nå observerer vi en særegenhet: hvis vi trenger å konvertere 00h, vil resultatet være 75h (vi stoler på fig. 3) - vi setter denne verdien i matrisen ved offset 00h. Vi tar verdien 01h, resultatet av erstatningsfunksjonen 79h, legger den i matrisen ved offset 01 og så videre til 0FFh, som vil gi oss 0FCh, som vi legger inn i matrisen ved offset 0FFh. Så vi fikk en utvidet tabell med erstatninger for den første gruppen av rader: første og null. Men det er fortsatt tre grupper: andre side 2, side 3, tredje side 4, side 5, fjerde side 6, side 7. Vi behandler disse tre gruppene på samme måte som med den første. Resultatet er en utvidet erstatningstabell!

Nå kan du implementere en algoritme som vil utføre erstatningen. For å gjøre dette tar vi kildekodene som Andrey Vinokurov la ut på siden sin, se " Bibliografi».

lea ebx,extended_table_simple

mov eax,[sett nummeret som skal erstattes]

legg til ebx,100h ;hopp til neste to noder

sub ebx,300h ; slik at ebx i fremtiden vil peke på tabellen

Nå er det en funksjon til: med de forrige handlingene erstattet vi ikke bare, men flyttet også tallet 8 biter til venstre! Alt vi trenger å gjøre er å flytte tallet ytterligere 3 biter til venstre:

og vi får resultatet av operasjonen rolle eax,11!

Jeg kan ikke legge til noe mer angående optimalisering, det eneste jeg kan understreke er det jeg sa ovenfor - bruk registre oftere enn å få tilgang til minne. Jeg tror disse ordene bare er for nybegynnere; erfarne mennesker forstår dette utmerket uten mine ord :).

Krav til nøkkelinformasjon.

Som nevnt i artikkelen av Andrey Vinokurov, er nøkkelen valgt i henhold til to kriterier:

— et kriterium for den likesannsynlige fordelingen av biter mellom verdiene 1 og 0. Vanligvis brukes Pearson-kriteriet («chi-square») som et kriterium for den likesannsynlige fordelingen av biter.

Dette betyr at nøkkelen i prinsippet kan være et hvilket som helst tall. Det vil si at når neste bit av nøkkelen dannes, er sannsynligheten for initialisering til én eller null 50/50!

Vær oppmerksom på at nøkkelen består av åtte elementer, hver på 32 biter, så totalt er det 32 ​​* 8 = 256 biter i nøkkelen og antall mulige nøkler er 2.256! Forundrer ikke dette deg? 🙂

- seriekriterium.

Hvis vi ser på nøkkelen vår, som jeg ga i avsnitt " 4.1 Implementering av hovedtrinnet i kryptokonvertering", så vil du legge merke til at følgende notasjon er sann:

Ris. 10

I en setning skal verdien av k 1 ikke gjentas i k 2 eller i noe annet nøkkelelement.

Det vil si at nøkkelen som vi valgte å betrakte som en krypteringsalgoritme oppfyller de to kriteriene ovenfor.

Nå om å velge et erstatningsbord:

La oss nå snakke om hvordan du velger riktig erstatningstabell. Hovedkravet for å velge erstatningstabeller er fenomenet "ikke-repetisjon" av elementer, som hver er 4 bits store. Som du allerede har sett ovenfor, består hver rad i erstatningstabellen av verdiene 0h, 1h, 2h, 3h, ..., 0fh. Så hovedkravet sier at hver linje inneholder verdiene 0h, 1h, 2h, ..., 0fh og hver slik verdi i en kopi. For eksempel sekvensen:

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

Den oppfyller fullt ut dette kravet, men likevel! Det anbefales ikke å velge en slik sekvens som en streng. For hvis du mater en verdi til inngangen til en funksjon som er avhengig av en slik streng, vil du få samme verdi som utgangen! Tro meg ikke? Ta så tallet 332DA43Fh og åtte slike rader som en tabell over erstatninger. Utfør utskiftingsoperasjonen, og jeg forsikrer deg, utgangen du vil få er 332DA43Fh! Altså det samme som du sendte inn som innspill til operasjonen! Men dette er ikke et tegn på god oppførsel ved kryptering, og var det det? 🙂

Dette var ett krav, det neste kriteriet sier at - hver bit av utgangsblokken må være statistisk uavhengig av hver bit av inngangsblokken!

Hvordan ser dette enklere ut? Og her er hvordan vi for eksempel valgte elementet s0 = 0Fh, 01111b fra tallet ovenfor. Sannsynligheten for at vi nå erstatter den første biten med en eller null er 0,5! Sannsynligheten for å erstatte den andre, tredje og fjerde biten, hver bit, vurderer vi separat, med enere eller nuller er også 0,5. Når du velger s1 = 0Eh, er sannsynligheten for at vi erstatter nullbiten, og dette er "0", med null eller en for lik – 0,5! I henhold til dette kriteriet er det altså ikke noe mønster mellom utskifting av nullbiter av elementene s0, s1! Ja, du kan erstatte enere, men du kan også erstatte nuller. 🙂

For å evaluere tabellen i henhold til dette kriteriet, kan du bygge en tabell med korrelasjonskoeffisienter beregnet ved hjelp av formelen:

— hvis p = 1, så er verdien av bit j ved utgangen lik verdien av bit i ved inngangen for en hvilken som helst kombinasjon av biter ved inngangen;

— hvis p = -1, så er verdien av bit j ved utgangen alltid invers av inngangsbit i;

— hvis p = 0, tar utgangsbiten j med lik sannsynlighet verdiene 0 og 1 for en hvilken som helst fast verdi av inngangsbiten i.

La oss ta et enkelt linje eksempel:

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

La oss dele det ned i "komponenter":

La oss beregne en koeffisient ved å bruke formelen gitt ovenfor. For å gjøre det lettere å forstå hvordan dette gjøres, vil jeg forklare mer detaljert:

— vi tar den 0. biten av det 0. tallet (0) ved inngangen og den 0. biten av det 0. tallet ved utgangen (1) og utfører operasjonen 0 XOR 1 = 1.

— vi tar den 0. biten av det første tallet (1) ved inngangen og den 0. biten av det første tallet ved utgangen (1) og utfører operasjonen 1 XOR 1 = 0.

— vi tar den 0. biten av det andre tallet (0) ved inngangen og den 0. biten av det andre tallet ved utgangen (0) og utfører operasjonen 0 XOR 0 = 0.

— vi tar den 0. biten av det tredje tallet (1) ved inngangen og den 0. biten av det tredje tallet ved utgangen (1) og utfører operasjonen 1 XOR 1 = 0.

Etter å ha utført sekvensielle XOR-operasjoner i denne sekvensen, teller vi antallet av alle verdier som ikke er null, vi får verdien 6. Derfor P 00 = 1-(6/2 4-1) = 0,25. Så det viste seg at verdien av bit 0 ved utgangen er lik verdien av bit 0 ved inngangen i 4 tilfeller av 16;

Finaletabell med odds:

Tabellen med koeffisienter vil være som følger (hvem som ikke er for lat kan beregne på nytt)

	Inngang
Exit		0	1	2	3
	0	-0,25	0,00	0,00	0,00
	1	0,00	1,00	0,00	0,00
	2	0,00	0,00	1,00	0,00
	3	0,00	0,00	0,00	-0,50

Vel, i denne tabellen er ting enda verre - bit 1 og 2 i gruppen forblir uendret! Kryptanalytikeren har plass til å snu 🙂 Ved å ta hensyn til alle disse kravene, ved enkelt brute-force-søk, ble permutasjonstabeller som tilsvarer den angitte teorien funnet (til dags dato - 1276 kombinasjoner). Her er noen av dem:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Liste over brukt litteratur.

1. Artikkel av Andrey Vinokurov:

GOST 28147-89 krypteringsalgoritme, dens bruk og implementering

for datamaskiner på Intel x86-plattformen.

(finnes på: http://www.enlight.ru/crypto/frame.htm).

Her er kildekodene for implementering av krypteringsalgoritmen.

1. Artikkel av Horst Feistel:

Kryptografi og datasikkerhet.

(finnes på samme adresse som forrige artikkel)

1. Ross N. Williams:

En grunnleggende veiledning til CRC-feildeteksjonsalgoritmer

Lagt ut på nettsiden www.wasm.ru.

Anerkjennelser

Jeg vil gjerne uttrykke min takknemlighet til alle besøkende på forumet www.wasm.ru. Men jeg vil spesielt takke ChS, som for tiden er kjent som SteelRat, han hjalp meg å forstå ting som jeg sannsynligvis aldri ville ha forstått, samt hjelp til å skrive avsnittet: " Krav til nøkkelinformasjon", ble hoveddelen av dette avsnittet skrevet av ham. Jeg er også dypt takknemlig overfor den ansatte i KSTU. A.N. Tupolev Anikin Igor Vyacheslavovich og det ville være synd å ikke nevne Chris Kaspersky for hva han er og Volodya / wasm.ru for hans instruksjoner. Å, og jeg får det fra ham :). Jeg vil også nevne Sega-Zero / Callipso for å bringe litt matematisk jungel inn i tankene mine.

Det er nok alt jeg vil fortelle deg.

Jeg vil være takknemlig for kritikk eller spørsmål knyttet til denne artikkelen eller bare råd. Mine kontaktdetaljer: [e-postbeskyttet], ICQ – 337310594.

Med vennlig hilsen, Evil's Interrupt.

P.S.: Jeg prøvde ikke å overgå noen med denne artikkelen. Den ble skrevet med den hensikt å gjøre det lettere å studere GOST, og hvis du har vanskeligheter, betyr ikke dette at jeg har skylden for dette. Vær rimelig og vær tålmodig, alt godt til deg!

Kort beskrivelse av chifferen

GOST 28147-89 er en sovjetisk og russisk symmetrisk krypteringsstandard introdusert i 1990, også en CIS-standard. Fullt navn - "GOST 28147-89 Informasjonsbehandlingssystemer. Kryptografisk beskyttelse. Kryptografisk konverteringsalgoritme." Blokkchifferalgoritme. Når du bruker gamma-krypteringsmetoden, kan den utføre funksjonene til en strømchifferalgoritme.

GOST 28147-89 er et blokkchiffer med en 256-bits nøkkel og 32 konverteringssykluser, som opererer på 64-biters blokker. Grunnlaget for chifferalgoritmen er Feistel Network. Den grunnleggende krypteringsmodusen i henhold til GOST 28147-89 er den enkle erstatningsmodusen (mer kompleks gamma, gamma med tilbakemelding og simulerte innsettingsmoduser er også definert).

Hvordan algoritmen fungerer

Algoritmen er ikke fundamentalt forskjellig fra DES. Den inneholder også krypteringssykluser (32 av dem) i henhold til Feistel-skjemaet (fig. 2.9.).

Ris. 2.9. Krypteringsrunder av GOST 28147-89-algoritmen.

For å generere undernøkler er den originale 256-bits nøkkelen delt inn i åtte 32-biters blokker: k 1 ...k 8 . Tastene k 9 ...k 24 er en syklisk repetisjon av tastene k 1 ...k 8 (nummerert fra minst signifikante til høyeste biter). Tastene k 25 …k 32 er tastene k 1 …k 8 i omvendt rekkefølge.

Etter å ha fullført alle 32 runder av algoritmen limes blokkene A 33 og B 33 sammen (merk at den mest signifikante biten blir A 33, og den minst signifikante biten - B 33) - resultatet er resultatet av algoritmen.

Funksjon f(EN Jeg ,K Jeg) beregnes som følger: A i og K i legges til modulo 2 32 , deretter deles resultatet inn i åtte 4-bits undersekvenser, som hver er inndata til sine egne substitusjonstabellnode(i stigende rekkefølge etter bitprioritet), kalt nedenfor S-blokk. Det totale antallet GOST S-blokker er åtte, det vil si det samme antallet som undersekvenser. Hver S-blokk er en permutasjon av tall fra 0 til 15. Den første 4-bits undersekvensen går til inngangen til den første S-boksen, den andre - til inngangen til den andre osv. Utgangene til alle åtte S-boksene kombineres til et 32-bits ord, så forskyves hele ordet syklisk til venstre (mot de mest signifikante bitene) med 11 biter. Alle de åtte S-boksene kan være forskjellige. Faktisk kan de være ekstra nøkkelmateriale, men oftere er de en skjemaparameter som er felles for en bestemt gruppe brukere. Teksten til standarden indikerer at levering av fyllingserstatningsenheter (S-blokker) utføres på foreskrevet måte, d.v.s. algoritmeutvikler. Fellesskapet til russiske CIPF-utviklere har blitt enige om erstatningsnodene som brukes på Internett.

Dekryptering utføres på samme måte som kryptering, men rekkefølgen på undernøklene k i inverteres.

Driftsmoduser for GOST 28147-89-algoritmen

GOST 28147-89-algoritmen har fire driftsmoduser.

1. Modusenkel utskifting godtar som inngangsdata hvis størrelse er et multiplum av 64 biter. Resultatet av kryptering er inndatateksten, konvertert i blokker på 64 biter i tilfelle av kryptering med "32-Z" syklus, og i tilfelle av dekryptering med "32-R" syklus.

2. Modusgambling godtar data av alle størrelser som input, samt en ekstra 64-bits parameter - synkronisere melding. Under drift konverteres synkroniseringsmeldingen i "32-Z" -syklusen, resultatet er delt inn i to deler. Den første delen er lagt til modulo 2 32 med en konstant verdi på 1010101 16. Hvis den andre delen er lik 2 32 -1, endres ikke verdien, ellers legges den til modulo 2 32 -1 med en konstant verdi på 1010104 16. Verdien oppnådd ved å kombinere begge transformerte deler, kalt chiffergamma, går inn i "32-3" syklusen, resultatet blir lagt til bit for bit modulo 2 med 64-bits blokken med inngangsdata. Hvis sistnevnte er mindre enn 64 biter, blir de ekstra bitene av den resulterende verdien forkastet. Den resulterende verdien sendes til utgangen. Hvis det fortsatt er innkommende data, gjentas handlingen: blokken som består av 32-biters deler, konverteres i deler, og så videre.

3. Modusspilling med tilbakemeldinger godtar også data av alle størrelser og en synkroniseringsmelding som input. Blokken med inngangsdata legges til bit for bit modulo 2 med resultatet av transformasjonen i "32-3" syklusen til synkroniseringsmeldingen. Den resulterende verdien sendes til utgangen. Verdien av synkroniseringsmeldingen erstattes i tilfelle kryptering av utgangsblokken, og i tilfelle dekryptering - av inngangsblokken, det vil si den krypterte. Hvis den siste blokken med innkommende data er mindre enn 64 biter, forkastes de ekstra bitene i gamma (utgang fra "32-3" syklusen). Hvis det fortsatt er innkommende data, gjentas handlingen: fra resultatet av kryptering av den erstattede verdien dannes et chiffergamma, etc.

4. Produksjonsmodusimitasjonsinnlegg tar som inngangsdata som er minst to hele 64-bits blokker i størrelse og returnerer en 64-bits blokk med data kalt en simulert innsetting. Den midlertidige 64-bits verdien settes til 0, så, så lenge det er inngangsdata, blir den lagt til bit for bit modulo 2 med resultatet av "16-3" syklusen, hvis inngang er en blokk med input data. Etter slutten av inndataene, returneres den midlertidige verdien som resultat.

Chifferkryptanalyse

GOST 28147-89-chifferet bruker en 256-bits nøkkel og volumet på nøkkelrommet er 2256. På ingen av de eksisterende datamaskinene for generell bruk kan en nøkkel finnes på mindre enn mange hundre år. Den russiske standarden GOST 28147-89 ble designet med stor margin og er mange størrelsesordener sterkere enn den amerikanske DES-standarden med sin faktiske nøkkelstørrelse på 56 biter og et nøkkelromvolum på kun 2 56 .

Det er også angrep på full-round GOST 28147-89 uten noen modifikasjoner. Et av de første offentlige verkene som analyserte algoritmen utnytter svakheter i nøkkelutvidelsesprosedyren til en rekke kjente krypteringsalgoritmer. Spesielt kan hele GOST 28147-89-algoritmen brytes ved hjelp av differensiell kryptoanalyse på relaterte nøkler, men bare hvis svake erstatningstabeller brukes. 24-runders versjonen av algoritmen (hvor de første 8 rundene mangler) åpnes på lignende måte med eventuelle erstatningstabeller, men sterke erstatningstabeller gjør et slikt angrep helt upraktisk.

Innenriksforskerne A.G. Rostovtsev og E.B. Makhovenko foreslo i 2001 en fundamentalt ny metode for kryptoanalyse ved å danne en objektiv funksjon fra en kjent klartekst, den tilsvarende chifferteksten og den ønskede nøkkelverdien og finne dens ekstremum som tilsvarer nøkkelens sanne verdi. De fant også en stor klasse med svake nøkler til GOST 28147-89-algoritmen, som gjør det mulig å åpne algoritmen ved å bruke bare 4 utvalgte klartekster og de tilsvarende chiffertekstene med en ganske lav kompleksitet.

I 2004 foreslo en gruppe spesialister fra Korea et angrep som ved hjelp av differensiell kryptoanalyse på relaterte nøkler kan få en 12-bits hemmelig nøkkel med en sannsynlighet på 91,7 %. Angrepet krever 2 35 utvalgte klartekster og 2 36 krypteringsoperasjoner. Som du kan se, er dette angrepet praktisk talt ubrukelig for å faktisk bryte algoritmen.

Erstatningstabellen er et langsiktig nøkkelelement, det vil si at den er gyldig i en mye lengre periode enn en enkelt nøkkel. Det antas at det er felles for alle krypteringsnoder innenfor samme kryptografiske beskyttelsessystem. Kvaliteten på chifferen avhenger av kvaliteten på denne tabellen. Med en "sterk" substitusjonstabell faller ikke styrken til chifferen under en viss akseptabel grense selv om den er kompromittert. Omvendt kan bruk av en "svak" tabell redusere styrken til chifferen til en uakseptabel lav grense. Ingen informasjon om kvaliteten på erstatningsbordet har blitt publisert i den åpne pressen i Russland, men eksistensen av "svake" tabeller er hevet over tvil - et eksempel er en "triviell" erstatningstabell, der hver verdi erstattes av seg selv. En rekke arbeider konkluderer feilaktig med at de hemmelige substitusjonstabellene til GOST 28147-89-algoritmen kan være en del av nøkkelen og øke dens effektive lengde (noe som ikke er signifikant, siden algoritmen har en veldig stor 256-bits nøkkel).

GOST 28147-89 krypteringsalgoritme, dens bruk og programvareimplementering for datamaskiner på Intel x86-plattformen.

Andrey Vinokurov

Beskrivelse av algoritmen.

Vilkår og betegnelser.

En beskrivelse av den russiske føderasjonens krypteringsstandard er inneholdt i et veldig interessant dokument med tittelen "Kryptografisk konverteringsalgoritme GOST 28147-89". Det faktum at det i navnet i stedet for begrepet "kryptering" vises et mer generelt konsept " kryptografisk konvertering ”, er slett ikke tilfeldig. I tillegg til flere nært beslektede krypteringsprosedyrer, beskriver dokumentet én algoritme for generering imitasjonsinnlegg . Sistnevnte er ikke annet enn en kryptografisk kontrollkombinasjon, det vil si en kode generert fra de originale dataene ved å bruke en hemmelig nøkkel for å imitasjonsbeskyttelse , eller beskytte data mot uautoriserte endringer.

Ved forskjellige trinn av GOST-algoritmer blir dataene de opererer på tolket og brukt på forskjellige måter. I noen tilfeller behandles dataelementer som matriser av uavhengige biter, i andre tilfeller som et heltall uten fortegn, i andre som et strukturert komplekst element som består av flere enklere elementer. Derfor, for å unngå forvirring, er det viktig å bli enige om notasjonen som brukes.

Dataelementer i denne artikkelen er utpekt med store bokstaver med kursiv stil (f.eks. X). Via | X| angir størrelsen på dataelementet X i biter. Altså, hvis vi tolker dataelementet X Som et ikke-negativt heltall kan vi skrive følgende ulikhet:.

Hvis et dataelement består av flere mindre elementer, er dette faktum indikert som følger: X=(X 0 ,X 1 ,…,Xn –1)=X 0 ||X 1 ||…||Xn-1 . Prosessen med å kombinere flere dataelementer til ett kalles sammenkobling data og er indikert med symbolet "||". Naturligvis må følgende relasjon være oppfylt for størrelsen på dataelementer: | X|=|X 0 |+|X 1 |+…+|Xn-1 |. Når du spesifiserer komplekse dataelementer og sammenkoblingsoperasjonen, er de konstituerende dataelementene oppført i stigende prioritetsrekkefølge. Med andre ord, hvis vi tolker det sammensatte elementet og alle dets dataelementer som heltall uten fortegn, kan vi skrive følgende likhet:

I algoritmen kan et dataelement tolkes som en rekke individuelle biter, i hvilket tilfelle bitene er angitt med samme bokstav som matrisen, men i en versjon med liten bokstav, som vist i følgende eksempel:

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

Derfor, hvis du la merke til, har den såkalte GOST blitt tatt i bruk. "little-endian" nummerering av sifre, dvs. Innenfor multi-bit dataord er individuelle biter og grupper av biter med lavere nummer mindre betydningsfulle. Dette er direkte uttalt i paragraf 1.3 i standarden: "Når du legger til og syklisk skifter binære vektorer, anses de mest signifikante bitene for å være bitene til stasjoner med store tall." Videre krever klausuler i standarden 1.4, 2.1.1 og andre å begynne å fylle lagringsregistrene til den virtuelle krypteringsenheten med data fra de laveste, dvs. mindre viktige kategorier. Nøyaktig den samme nummereringsrekkefølgen er tatt i bruk i Intel x86-mikroprosessorarkitekturen, og det er grunnen til at når du implementerer et chiffer i programvare på denne arkitekturen, er det ikke nødvendig med ytterligere permutasjoner av biter i dataord.

Hvis en operasjon som har en logisk betydning utføres på dataelementer, antas det at denne operasjonen utføres på de tilsvarende bitene til elementene. Med andre ord EN B=(en 0 b 0 ,en 1 b 1 ,…,en n –1 b n–1), hvor n=|EN|=|B|, og symbolet “ ” angir en vilkårlig binær logisk operasjon; som regel betyr dette operasjon eksklusiv eller , som også er operasjonen til summering modulo 2:

Logikken i å konstruere et chiffer og strukturen til GOST-nøkkelinformasjon.

Hvis du nøye studerer den originale GOST 28147–89, vil du legge merke til at den inneholder en beskrivelse av algoritmer på flere nivåer. Helt på toppen er det praktiske algoritmer designet for å kryptere datamatriser og utvikle imitative inserts for dem. Alle er basert på tre lavnivåalgoritmer, kalt i GOST-teksten sykluser . Disse grunnleggende algoritmene omtales i denne artikkelen som grunnleggende sykluser for å skille dem fra alle andre sykluser. De har følgende navn og symboler, sistnevnte er gitt i parentes og deres betydning vil bli forklart senere:

• krypteringssyklus (32-З);
• dekrypteringssyklus (32-P);
• produksjonssyklus av imitasjonsinnsats (16-Z).

På sin side er hver av de grunnleggende syklusene en gjentakelse av én enkelt prosedyre, noe som kreves ytterligere i dette arbeidet. hovedtrinnet i kryptokonvertering .

Derfor, for å forstå GOST, må du forstå følgende tre ting:

• hva har skjedd grunnleggende trinn kryptokonverteringer;
• hvordan grunnleggende sykluser dannes fra grunnleggende trinn;
• fra tre grunnleggende sykluser alle praktiske GOST-algoritmer er lagt sammen.

Før vi går videre til å studere disse problemene, bør vi snakke om nøkkelinformasjonen som brukes av GOST-algoritmer. I samsvar med Kirchhoffs prinsipp, som tilfredsstilles av alle moderne chiffer kjent for allmennheten, er det dens hemmelighold som sikrer hemmeligholdet til den krypterte meldingen. I GOST består nøkkelinformasjon av to datastrukturer. Foruten det faktiske nøkkel , nødvendig for alle chiffer, inneholder den også erstatningstabell . Nedenfor er hovedkarakteristikkene til nøkkelstrukturene til GOST.

Hovedtrinnet i kryptokonvertering.

Det grunnleggende kryptokonverteringstrinnet er i hovedsak en uttalelse som spesifiserer konverteringen av en 64-biters blokk med data. En ekstra parameter for denne operatøren er en 32-bits blokk, som brukes som et nøkkelelement. Algoritmediagrammet for hovedtrinn er vist i figur 1.

Figur 1. Skjema for hovedtrinnet for kryptokonvertering av GOST 28147-89-algoritmen.

Nedenfor er forklaringer av hovedtrinnsalgoritmen:

Trinn 0

• N– en konvertert 64-bits datablokk, under utførelsen av trinnet er det mindre ( N 1) og senior ( N 2) delene behandles som separate 32-biters heltall uten fortegn. Dermed kan vi skrive N=(N 1 ,N 2).
• X– 32-bits nøkkelelement;

Trinn 1

Tillegg med nøkkel. Den nedre halvdelen av den konverterte blokken legges til modulo 2 32 med nøkkelelementet brukt på trinnet, resultatet overføres til neste trinn;

Steg 2

Utskifting av blokker. 32-bits verdien oppnådd i forrige trinn tolkes som en matrise med åtte 4-bits kodeblokker: S=(S 0 , S 1 , S 2 , S 3 , S 4 , S 5 , S 6 , S 7), og S 0 inneholder de 4 yngste, og S 7 – 4 mest betydningsfulle biter S.

Deretter erstattes verdien av hver av de åtte blokkene med en ny, som velges fra erstatningstabellen som følger: blokkverdi S i endringer til S i-te element i rekkefølge (nummerering fra null) Jeg-den erstatningsnoden (dvs. Jeg linje i erstatningstabellen, nummerering også fra bunnen av). Med andre ord, et element fra erstatningstabellen med et radnummer lik nummeret på blokken som erstattes og et kolonnenummer lik verdien av blokken som erstattes som et 4-bits ikke-negativt heltall, velges som erstatning for verdien av blokken. Dette gjør størrelsen på erstatningstabellen tydelig: antall rader i den er lik antall 4-bits elementer i en 32-bits datablokk, det vil si åtte, og antall kolonner er lik antall forskjellige verdier av en 4-bits datablokk, som er kjent for å være 2 4, seksten.

Trinn 3

Roter 11 biter til venstre. Resultatet av det forrige trinnet forskyves syklisk med 11 biter mot de mest signifikante bitene og overføres til neste trinn. I algoritmediagrammet indikerer symbolet funksjonen til å syklisk skifte argumentet 11 biter til venstre, dvs. mot de høyere gradene.

Trinn 4

Bitvis addisjon: Verdien oppnådd i trinn 3 legges til bitvis modulo 2 med den øvre halvdelen av blokken som konverteres.

Trinn 5

Skift langs kjeden: den nedre delen av den konverterte blokken flyttes til stedet for den eldre, og resultatet av forrige trinn plasseres på sin plass.

Trinn 6

Den resulterende verdien av den konverterte blokken returneres som et resultat av å utføre algoritmen for hovedtrinnet i kryptokonvertering.

Grunnleggende sykluser av kryptografiske transformasjoner.

Som nevnt i begynnelsen av denne artikkelen, tilhører GOST klassen blokkchiffer, det vil si at enheten for informasjonsbehandling i den er en datablokk. Derfor er det ganske logisk å forvente at den vil definere algoritmer for kryptografiske transformasjoner, det vil si for kryptering, dekryptering og "regnskap" for en kontrollkombinasjon av én datablokk. Disse algoritmene kalles grunnleggende sykluser GOST, som understreker deres grunnleggende betydning for konstruksjonen av dette chifferet.

Grunnløkker er bygget av hovedtrinn kryptografisk transformasjon diskutert i forrige avsnitt. Under hovedtrinnet brukes kun ett 32-bits nøkkelelement, mens GOST-nøkkelen inneholder åtte slike elementer. Derfor, for at nøkkelen skal brukes fullt ut, må hver av de grunnleggende løkkene gjentatte ganger utføre hovedtrinnet med de forskjellige elementene. Samtidig virker det ganske naturlig at alle nøkkelelementer i hver grunnsyklus skal brukes like mange ganger; av hensyn til chifferstyrken bør dette tallet være mer enn ett.

Alle antakelsene ovenfor, bare basert på sunn fornuft, viste seg å være korrekte. Grunnløkker består av gjentatt utførelse hovedtrinn bruker forskjellige nøkkelelementer og skiller seg fra hverandre kun i antall trinnrepetisjoner og rekkefølgen nøkkelelementene brukes i. Nedenfor er denne rekkefølgen for ulike sykluser.

Krypteringssyklus 32-Z:

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 .

Figur 2a. Krypteringssyklusskjema 32-З

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

Figur 2b. Opplegg for 32-P dekrypteringssyklusen

Produksjonssyklus av imitasjonsinnsats 16-Z:

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 .

Figur 2c. Opplegg av produksjonssyklusen av imitasjonsinnsats 16-Z.

Hver av syklusene har sin egen alfanumeriske betegnelse som tilsvarer mønsteret " n-X", hvor det første elementet i betegnelsen ( n), spesifiserer antall repetisjoner av hovedtrinnet i syklusen, og det andre betegnelseselementet ( X), bokstav, spesifiserer rekkefølgen for kryptering (“Z”) eller dekryptering (“P”) ved bruk av nøkkelelementer. Denne bestillingen trenger ytterligere forklaring:

Dekrypteringssyklusen må være den inverse av krypteringssyklusen, det vil si at sekvensiell applikasjon av disse to syklusene til en vilkårlig blokk må til slutt gi den opprinnelige blokken, noe som gjenspeiles i følgende forhold: C 32-Р ( C 32-З ( T))=T, Hvor T– vilkårlig 64-biters datablokk, C X ( T) – resultatet av løkkekjøringen X over datablokken T. For å oppfylle denne betingelsen for algoritmer som ligner på GOST, er det nødvendig og tilstrekkelig at rekkefølgen for bruk av nøkkelelementer av de tilsvarende syklusene er gjensidig invers. Det er lett å verifisere gyldigheten av den skriftlige betingelsen for saken under vurdering ved å sammenligne sekvensene ovenfor for syklusene 32-З og 32-Р. En interessant konsekvens følger av det ovenstående: egenskapen til at en syklus er invers til en annen syklus er resiprok, det vil si at 32-Z-syklusen er invers til 32-P-syklusen. Med andre ord, kryptering av en blokk med data kan teoretisk utføres ved bruk av en dekrypteringssyklus, i hvilket tilfelle dekryptering av en blokk med data må utføres av en krypteringssyklus. Av de to gjensidig inverse syklusene, kan en av dem brukes til kryptering, deretter må den andre brukes til å dekryptere data, men GOST 28147-89-standarden tildeler roller til sykluser og gir ikke brukeren rett til å velge i denne saken .

Syklusen for å produsere en imitativ innsetting er halvparten så lang som krypteringssyklusene, rekkefølgen for bruk av nøkkelelementer i den er den samme som i de første 16 trinnene i krypteringssyklusen, som er lett å verifisere ved å vurdere sekvensene ovenfor, derfor denne rekkefølgen i betegnelsen på syklusen er kodet med samme bokstav "Z".

Skjemaer av grunnleggende sykluser er vist i figurene 2a-c. Hver av dem tar som et argument og returnerer som et resultat en 64-bits blokk med data, angitt i diagrammene N. Symbol trinn( N,X) betegner utførelsen av hfor en datablokk N ved hjelp av nøkkelelement X. Det er enda en forskjell mellom krypterings- og imitativ innsettingsberegningssyklus, ikke nevnt ovenfor: på slutten av de grunnleggende krypteringssyklusene byttes de høye og lave delene av resultatblokken, dette er nødvendig for deres gjensidige reversibilitet.

Grunnleggende krypteringsmoduser.

GOST 28147-89 gir følgende tre datakrypteringsmoduser:

• enkel utskifting,
• spilling,
• spilling med tilbakemeldinger,

og en ekstra modus for å generere imitasjonsinnsatser.

I noen av disse modusene blir data behandlet i blokker på 64 biter, som matrisen er delt inn i og utsatt for kryptografisk transformasjon, og det er grunnen til at GOST refererer til blokkchiffer. I to gamma-moduser er det imidlertid mulig å behandle en ufullstendig blokk med data som er mindre enn 8 byte i størrelse, noe som er avgjørende når du krypterer datamatriser av vilkårlig størrelse, som kanskje ikke er et multiplum av 8 byte.

Før du går videre til en diskusjon av spesifikke kryptografiske transformasjonsalgoritmer, er det nødvendig å avklare notasjonen som brukes i diagrammene i de følgende avsnittene:

TÅ, T w - rekker av henholdsvis åpne og krypterte data;

, – Jeg- Sekvensielle 64-biters blokker med henholdsvis åpne og krypterte data: , , kan den siste blokken være ufullstendig: ;

n– antall 64-bits blokker i datamatrisen;

C X - funksjon for å konvertere en 64-bits datablokk ved å bruke den grunnleggende syklusen "X" algoritmen.

Nå vil vi beskrive de viktigste krypteringsmodusene:

Enkel utskifting.

Kryptering i denne modusen består av å bruke syklus 32-З til blokker med åpne data, dekryptering - syklus 32-Р til blokker med krypterte data. Dette er den enkleste av modusene; 64-biters datablokker behandles uavhengig av hverandre. Skjemaer med krypterings- og dekrypteringsalgoritmer i enkel erstatningsmodus er vist i henholdsvis figur 3a og b; de er trivielle og trenger ikke kommentarer.

Tegning. 3a. Datakrypteringsalgoritme i enkel erstatningsmodus

Tegning. 3b. Datadekrypteringsalgoritme i enkel erstatningsmodus

Størrelsen på utvalget av åpne eller krypterte data, underlagt henholdsvis kryptering eller dekryptering, må være et multiplum av 64 biter: | T o |=| T w |=64· n , etter å ha utført operasjonen, endres ikke størrelsen på den resulterende datamatrisen.

Den enkle erstatningskrypteringsmodusen har følgende funksjoner:

• Siden datablokker er kryptert uavhengig av hverandre og deres posisjon i datamatrisen, resulterer kryptering av to identiske klartekstblokker i identiske chiffertekstblokker og omvendt. Den bemerkede egenskapen vil tillate kryptoanalytikeren å gjøre en konklusjon om identiteten til de originale datablokkene hvis han møter identiske blokker i den krypterte datamatrisen, noe som er uakseptabelt for en seriøs chiffer.
• Hvis lengden på den krypterte datamatrisen ikke er et multiplum av 8 byte eller 64 biter, oppstår problemet med hvordan og hvordan man skal supplere den siste ufullstendige datablokken til matrisen til hele 64 biter. Denne oppgaven er ikke så enkel som den ser ut ved første øyekast. Åpenbare løsninger som "supplere en ufullstendig blokk med null biter" eller mer generelt "supplere en ufullstendig blokk med en fast kombinasjon av null og en bit" kan under visse forhold gi kryptoanalytikeren muligheten til å bruke brute force metoder for å bestemme innholdet i denne svært ufullstendige blokken, og dette faktum betyr en reduksjon i sikkerhetschiffer. I tillegg vil lengden på chifferteksten endres, og øke til nærmeste heltallsmultippel på 64 biter, noe som ofte er uønsket.

Ved første øyekast gjør funksjonene ovenfor det nesten umulig å bruke den enkle erstatningsmodusen, fordi den kun kan brukes til å kryptere datamatriser med en størrelse som er et multiplum av 64 biter og ikke inneholder repeterende 64-biters blokker. Det ser ut til at det for noen reelle data er umulig å garantere oppfyllelsen av disse betingelsene. Dette er nesten sant, men det er ett veldig viktig unntak: husk at nøkkelstørrelsen er 32 byte, og størrelsen på erstatningstabellen er 64 byte. I tillegg vil tilstedeværelsen av gjentatte 8-byte blokker i en nøkkel eller erstatningstabell indikere deres svært dårlige kvalitet, så slik repetisjon kan ikke eksistere i ekte nøkkelelementer. Dermed fant vi ut at den enkle erstatningsmodusen er ganske egnet for å kryptere nøkkelinformasjon, spesielt siden andre moduser er mindre praktiske for dette formålet, siden de krever tilstedeværelsen av et ekstra synkroniseringsdataelement - en synkroniseringsmelding (se neste avsnitt) . Vår gjetning er riktig; GOST foreskriver bruk av enkel erstatningsmodus utelukkende for kryptering av nøkkeldata.

Gumming.

Hvordan kan du bli kvitt manglene ved den enkle erstatningsmodusen? For å gjøre dette er det nødvendig å gjøre det mulig å kryptere blokker med en størrelse på mindre enn 64 biter og sikre at chiffertekstblokken avhenger av nummeret, med andre ord, randomisere krypteringsprosess. I GOST oppnås dette på to forskjellige måter i to krypteringsmoduser, noe som gir gambling . Gumming - dette er pålegging (fjerning) av en kryptografisk skala på åpne (krypterte) data, det vil si en sekvens av dataelementer generert ved hjelp av en kryptografisk algoritme for å oppnå krypterte (åpne) data. For å bruke gamma under kryptering og fjerne det under dekryptering, må gjensidig inverse binære operasjoner brukes, for eksempel addisjon og subtraksjon modulo 2 64 for 64-bits datablokker. I GOST, for dette formålet, brukes operasjonen av bitvis addisjon modulo 2, siden det er det motsatte av seg selv og dessuten er enklest implementert i maskinvare. Gamma løser begge de nevnte problemene: For det første er alle gamma-elementer forskjellige for ekte krypterte arrays, og derfor vil resultatet av kryptering av to identiske blokker i en datamatrise være forskjellig. For det andre, selv om gamma-elementene genereres i like deler av 64 biter, kan en del av en slik blokk med en størrelse lik størrelsen på den krypterte blokken brukes.

La oss nå gå direkte til beskrivelsen av gammamodusen. Gamma for denne modusen oppnås som følger: ved hjelp av en algoritmisk gjentakende tallsekvensgenerator (RNGN) genereres 64-bits datablokker, som deretter konverteres ved hjelp av 32-3 syklusen, det vil si kryptert i den enkle erstatningsmodus, noe som resulterer i gammablokker. På grunn av det faktum at gammaapplikasjon og fjerning utføres med samme bitvise eksklusive eller operasjon, er krypterings- og dekrypteringsalgoritmene i gammamodus identiske, deres generelle skjema er vist i figur 4.

RGPG-en som brukes til å generere skalaen er en tilbakevendende funksjon: – elementer i den tilbakevendende sekvensen, f– transformasjonsfunksjon. Følgelig oppstår spørsmålet uunngåelig om dets initialisering, det vil si om elementet. Faktisk er dette dataelementet en algoritmeparameter for gammamoduser; i diagrammene er det betegnet som S, og kalles i kryptografi synkronisere send , og i vår GOST – innledende fylling ett av koderregistrene. Av visse grunner bestemte utviklerne av GOST seg for å ikke bruke synkroniseringsmeldingen direkte for å initialisere RGFC, men resultatet av konverteringen i henhold til 32-Z-syklusen: . Sekvensen av elementer generert av RGHR avhenger helt av dens første fylling, det vil si at elementene i denne sekvensen er en funksjon av antallet og den første fyllingen av RGHR: hvor f i(X)=f(f i –1 (X)), f 0 (X)=X. Tatt i betraktning transformasjonen ved hjelp av den enkle erstatningsalgoritmen, legges det også til en avhengighet av nøkkelen:

Hvor Г i– Jeg-te element av skalaen, K- nøkkel.

Således er sekvensen av gamma-elementer som skal brukes i gamma-modus unikt bestemt av nøkkeldataene og synkroniseringsmeldingen. Naturligvis, for at krypteringsprosedyren skal være reversibel, må den samme synkroniseringsmeldingen brukes i krypterings- og dekrypteringsprosessene. Fra kravet om unikhet til gamma, manglende overholdelse som fører til en katastrofal reduksjon i chifferets styrke, følger det at for å kryptere to forskjellige datamatriser på samme nøkkel, er det nødvendig å sikre bruk av forskjellige synkroniseringsmeldinger. Dette fører til behovet for å lagre eller overføre synkroniseringsmeldingen langs kommunikasjonskanaler sammen med de krypterte dataene, selv om det i noen spesielle tilfeller kan forhåndsbestemmes eller beregnes på en spesiell måte hvis kryptering av to arrays med samme nøkkel er utelukket.

La oss nå se nærmere på RGPC-en som brukes i GOST for å generere gamut-elementer. Først av alt bør det bemerkes at det ikke er nødvendig å gi noen statistiske egenskaper for den genererte tallsekvensen. RGHR ble designet av utviklerne av GOST basert på behovet for å oppfylle følgende betingelser:

• repetisjonsperioden for tallsekvensen generert av RGPC bør ikke avvike mye (i prosentvis) fra den maksimalt mulige verdien for en gitt blokkstørrelse på 2 64;
• tilstøtende verdier produsert av RGPG må avvike fra hverandre i hver byte, ellers vil kryptanalytikerens oppgave bli forenklet;
• RGPC-en skal være ganske enkel å implementere både i maskinvare og programvare på de vanligste typene prosessorer, hvorav de fleste er kjent for å være 32-bit.

Basert på de listede prinsippene designet skaperne av GOST en meget vellykket RGHR, som har følgende egenskaper:

Hvor C 0 =1010101 16 ;

Hvor C 1 =1010104 16 ;

Det nedskrevne i et tall indikerer tallsystemet, så konstantene som brukes i dette trinnet er skrevet i heksadesimal.

Det andre uttrykket trenger kommentarer, siden teksten til GOST inneholder noe annet: , med samme verdi av konstanten C 1 . Men videre i standardteksten er det gitt en kommentar om at det viser seg at under operasjonen av å ta resten modulo 2 32 –1 der er ikke forstått på samme måte som i matematikk. Forskjellen er at ifølge GOST (2 32 –1) mod(2 32 –1)=(2 32 –1), ikke 0. Dette forenkler faktisk implementeringen av formelen, og det matematisk korrekte uttrykket for den er gitt ovenfor.

• repetisjonsperioden for sekvensen for den nedre delen er 2 32, for den eldre delen 2 32 –1, for hele sekvensen er perioden 2 32 (2 32 –1), beviset på dette faktum er veldig enkelt, få det deg selv. Den første av de to formlene er implementert i én kommando, den andre, til tross for dens tilsynelatende tungvinthet, i to kommandoer på alle moderne 32-bits prosessorer - den første kommandoen utfører den vanlige addisjonsmodulen 2 32 med lagring av bærebiten, og den andre kommandoen legger bærebiten til den resulterende betydningen.

Krypteringsalgoritmediagrammet i gammamodus er vist i figur 4; nedenfor er forklaringer for skjemaet:

Figur 4. Algoritme for kryptering (dekryptering) av data i gammamodus.

Trinn 0

Definerer inngangsdata for hovedkryptokonverteringstrinnet:

• T o(w) – en rekke åpne (krypterte) data av vilkårlig størrelse, utsatt for en kryptering (dekryptering) prosedyre; under prosedyren konverteres matrisen i 64-bits deler;
• S – synkronisere melding , et 64-bits dataelement som kreves for å initialisere gammageneratoren;

Trinn 1

Den første transformasjonen av synkroniseringsmeldingen, utført for å "randomisere" den, det vil si for å eliminere de statistiske mønstrene som er tilstede i den, blir resultatet brukt som den første fyllingen av RGPC;

Steg 2

Ett trinn i RGPC-operasjonen, implementering av den tilbakevendende algoritmen. I løpet av dette trinnet, den eldste ( S 1) og junior ( S 0) deler av datasekvensen genereres uavhengig av hverandre;

Trinn 3

Gumming. Det neste 64-bits elementet generert av RGPC blir utsatt for en krypteringsprosedyre ved bruk av syklus 32-3, resultatet brukes som et gammaelement for å kryptere (dekryptere) neste blokk med åpne (krypterte) data av samme størrelse.

Trinn 4

Resultatet av algoritmen er en kryptert (dekryptert) datamatrise.

Følgende er funksjonene til gamma som krypteringsmodus:

1. Identiske blokker i en åpen datamatrise vil gi forskjellige chiffertekstblokker når de krypteres, noe som vil gjøre det mulig å skjule fakta om deres identitet.
2. Siden gammaoverlegg utføres bitvis, kan kryptering av en delvis blokk med data enkelt oppnås ved å kryptere bitene til den delvise blokken ved å bruke de tilsvarende bitene i gammablokken. For å kryptere en ufullstendig blokk på 1 bit, i henhold til standarden, bør den minst signifikante biten fra gammablokken brukes.
3. Synkroniseringsmeldingen som brukes til kryptering må på en eller annen måte overføres for bruk i dekryptering. Dette kan oppnås på følgende måter:

• lagre eller overføre en synkroniseringsmelding sammen med en kryptert datamatrise, noe som vil føre til en økning i størrelsen på datamatrisen når kryptert med størrelsen på synkroniseringsmeldingen, det vil si med 8 byte;
• bruke en forhåndsbestemt verdi av synkroniseringsmeldingen eller generere den synkront av kilden og mottakeren i henhold til en viss lov, i dette tilfellet er det ingen endring i størrelsen på den overførte eller lagrede datamatrisen;

Begge metodene utfyller hverandre, og i de sjeldne tilfellene der den første, mest vanlige, ikke fungerer, kan den andre, mer eksotiske, brukes. Den andre metoden har mye mindre anvendelse, siden det er mulig å lage en synkroniseringsmelding forutbestemt bare hvis ikke mer enn én datamatrise er kryptert på et gitt sett med nøkkelinformasjon, noe som ikke skjer veldig ofte. Det er heller ikke alltid mulig å generere en synkroniseringsmelding synkront ved kilden og mottakeren av en datamatrise, siden det krever en streng kobling til noe i systemet. En tilsynelatende god idé å bruke nummeret på den overførte meldingen som en synkroniseringsmelding i et system for overføring av krypterte meldinger er derfor ikke egnet, siden meldingen kan gå tapt og ikke nå mottakeren, i så fall krypteringssystemene til kilden og mottakeren vil bli desynkronisert. Derfor, i det aktuelle tilfellet, er det ikke noe alternativ til å sende synkroniseringsmeldingen sammen med den krypterte meldingen.

På den annen side kan det motsatte eksempelet gis. La oss si at datakryptering brukes til å beskytte informasjon på disken, og den er implementert på et lavt nivå; for å sikre uavhengig tilgang, krypteres dataene etter sektor. I dette tilfellet er det umulig å lagre synkroniseringsmeldingen sammen med de krypterte dataene, siden sektorstørrelsen ikke kan endres, men den kan beregnes som en funksjon av diskens lesehodenummer, spor (sylinder) og sektornummer på sporet. I dette tilfellet er synkroniseringsmeldingen knyttet til posisjonen til sektoren på disken, som neppe endres uten å formatere disken på nytt, det vil si uten å ødelegge dataene på den.

Gamma-modusen har en annen interessant funksjon. I denne modusen krypteres bitene i datamatrisen uavhengig av hverandre. Dermed avhenger hver bit av chifferteksten av den tilsvarende biten i klarteksten og selvfølgelig sekvensnummeret til biten i matrisen: . Dette innebærer at endring av en chiffertekstbit til den motsatte verdien vil resultere i en lignende endring til den motsatte verdien av en klartekstbit:

der angir invertert i forhold til t bitverdi().

Denne egenskapen gir en angriper muligheten til, ved å påvirke chiffertekstbitene, å gjøre forutsigbare og til og med målrettede endringer i den tilsvarende klarteksten som er oppnådd etter dekryptering, uten å ha den hemmelige nøkkelen. Dette illustrerer det velkjente faktum innen kryptologi som hemmelighold og autentisitet er forskjellige egenskaper kryptografiske systemer . Med andre ord, egenskapene til et kryptosystem for å gi beskyttelse mot uautorisert tilgang til innholdet i en melding og mot uautoriserte endringer i en melding er uavhengige og kan bare overlappe i visse tilfeller. Dette betyr at det finnes kryptografiske algoritmer som gir et visst hemmelighold av krypterte data og som samtidig ikke beskytter mot endringer på noen måte, og omvendt, sikrer dataenes autentisitet og på ingen måte begrenser muligheten til å sette seg inn i dem. Av denne grunn bør den betraktede egenskapen til gammamodusen ikke betraktes som dens ulempe.

Gamma med tilbakemelding.

Denne modusen er veldig lik gamma-modusen og skiller seg fra den bare i måten gamma-elementene genereres på - det neste gamma-elementet genereres som et resultat av 32-3 syklustransformasjonen av forrige blokk med krypterte data, og for å kryptere den første blokken i datamatrisen, genereres gammaelementet som et resultat av den sammeklusen. Dette oppnår blokkkjeding – hver chiffertekstblokk i denne modusen avhenger av de tilsvarende og alle tidligere klartekstblokkene. Derfor kalles denne modusen noen ganger spilling med sammenlåsende blokker . Det at blokker er koblet sammen har ingen innvirkning på chifferets styrke.

Diagrammet over krypterings- og dekrypteringsalgoritmene i gammamodus med tilbakemelding er vist i figur 5 og trenger på grunn av sin enkelhet ingen kommentarer.

Figur 5. Algoritme for kryptering (dekryptering) av data i gammamodus med tilbakemelding.

Gammakryptering med lukket sløyfe har de samme funksjonene som vanlig gammakryptering, bortsett fra effekten av krypteringstekstkorrupsjon på den tilsvarende klarteksten. For sammenligning, la oss skrive ned blokkdekrypteringsfunksjonene for begge nevnte moduser:

Gumming;

Gamma med tilbakemelding;

Hvis endringer i visse biter av chifferteksten i vanlig gammamodus bare påvirker de tilsvarende bitene i renteksten, er bildet noe mer komplisert i tilbakemeldingsgammamodusen. Som man kan se fra den tilsvarende ligningen, ved dekryptering av en datablokk i gammamodus med lukket sløyfe, avhenger den åpne datablokken av de tilsvarende og tidligere krypterte datablokkene. Derfor, hvis du introduserer forvrengninger i en kryptert blokk, vil to blokker med åpne data etter dekryptering bli forvrengt - den tilsvarende og den som følger den, og forvrengningene i det første tilfellet vil være av samme art som i gammamodus , og i det andre tilfellet - som i den enkle erstatningen. Med andre ord, i den tilsvarende blokken med åpne data vil de samme bitene bli ødelagt som i blokken med krypterte data, og i neste blokk med åpne data er alle biter uavhengige av hverandre med sannsynlighet 1 / 2 vil endre sine verdier.

Utvikling av en simulert innsats for datamatrisen.

I tidligere seksjoner diskuterte vi virkningen av korrupsjon av krypterte data på de tilsvarende vanlige dataene. Vi har slått fast at ved dekryptering i den enkle erstatningsmodusen, viser den korresponderende blokken med åpne data seg å være forvrengt på en uforutsigbar måte, og ved dekryptering av en blokk i gammamodus er endringene forutsigbare. I gammamodus med lukket sløyfe blir to blokker forvrengt, en på en forutsigbar måte og den andre på en uforutsigbar måte. Betyr dette at fra synspunktet om beskyttelse mot pålegging av falske data, er gammamodusen dårlig, og de enkle erstatnings- og tilbakemeldingsgammamodusene er gode? - Ikke i noe tilfelle. Når du analyserer denne situasjonen, er det nødvendig å ta i betraktning at uforutsigbare endringer i en dekryptert datablokk bare kan oppdages hvis de samme dataene er redundante, og jo større redundansgraden er, desto mer sannsynlig er det å oppdage forvrengning. Svært stor redundans oppstår for eksempel for tekster på naturlige og kunstige språk, i dette tilfellet oppdages forvrengning nesten uunngåelig. Men i andre tilfeller, for eksempel når komprimerte digitaliserte lydbilder blir forvrengt, vil vi rett og slett få et annet bilde som øret vårt kan oppfatte. Forvrengningen i dette tilfellet vil forbli uoppdaget, med mindre det selvfølgelig er a priori informasjon om lydens natur. Konklusjonen her er denne: siden evnen til noen krypteringsmoduser til å oppdage forvrengninger introdusert i krypterte data i betydelig grad er avhengig av tilstedeværelsen og graden av redundans til de krypterte dataene, er denne evnen ikke en iboende egenskap til de tilsvarende modusene og kan ikke betraktes som deres fordel.

For å løse problemet med å oppdage forvrengninger i en kryptert datamatrise med en gitt sannsynlighet, sørger GOST for en ekstra modus for kryptografisk transformasjon - utviklingen av imitativ innsetting. Imitasjonsinnlegg er en kontrollkombinasjon som er avhengig av åpne data og hemmelig nøkkelinformasjon. Hensikten med å bruke imitativ innsetting er å oppdage alle tilfeldige eller tilsiktede endringer i informasjonsarrayen. Problemet beskrevet i forrige avsnitt kan løses med hell ved å legge til imitative innlegg til de krypterte dataene. For en potensiell angriper er følgende to oppgaver nesten umulige å løse hvis han ikke har nøkkelen:

• beregning av imitativ innsetting for et gitt åpent utvalg av informasjon;
• valg av åpne data for et gitt simuleringsinnlegg;

Diagrammet av algoritmen for å utvikle en simulert innsats er vist i figur 6.

Figur 6. Algoritme for å utvikle en simulert innsats for en datamatrise.

En del av blokken mottatt ved utgangen tas som en simulert innsetting, vanligvis dens 32 minst signifikante biter. Når man velger størrelsen på et falskt innlegg, må man ta hensyn til at sannsynligheten for å lykkes med å pålegge falske data er lik 2 –| Jeg | per seleksjonsforsøk, hvis angriperen ikke har en mer effektiv seleksjonsmetode til rådighet enn enkel gjetting. Når du bruker et 32-bits simulert innlegg, er denne sannsynligheten lik

Diskusjon av GOST kryptografiske algoritmer.

Kryptografisk styrke til GOST.

Når du velger en kryptografisk algoritme for bruk i en bestemt utvikling, er en av de avgjørende faktorene dens styrke, det vil si motstand mot motstanders forsøk på å avsløre den. Spørsmålet om styrken til et chiffer, ved nærmere undersøkelse, kommer ned til to sammenhengende spørsmål:

• Er det mulig å knekke denne chifferen i det hele tatt?
• i så fall, hvor vanskelig er det i praksis;

Chiffer som ikke kan brytes i det hele tatt kalles absolutt eller teoretisk sterke. Eksistensen av slike chiffer er bevist av Shannons teorem, men prisen på denne styrken er behovet for å bruke en nøkkel for å kryptere hver melding som ikke er mindre i størrelse enn selve meldingen. I alle tilfeller, med unntak av en rekke spesielle, er denne prisen overdreven, så i praksis brukes hovedsakelig chiffer som ikke er helt sikre. Dermed kan de vanligste krypteringsskjemaene brytes på en begrenset tid, eller mer presist, i et begrenset antall trinn, som hver er en operasjon på tall. For dem er det viktigste konseptet praktisk utholdenhet, som uttrykker den praktiske vanskeligheten med å oppdage deres. Et kvantitativt mål på denne vanskeligheten kan være antall elementære aritmetiske og logiske operasjoner som må utføres for å åpne chifferen, det vil si for å bestemme den tilsvarende klarteksten for en gitt chiffertekst med en sannsynlighet som ikke er mindre enn en gitt verdi. Samtidig, i tillegg til den dekrypterte datamatrisen, kan kryptoanalytikeren ha blokker med åpne data og tilsvarende krypterte data, eller til og med muligheten til å skaffe tilsvarende krypterte data for alle åpne data han velger – avhengig av de oppførte og mange andre uspesifiserte dataene. forhold, skilles det ut separate typer kryptoanalyse.

Alle moderne kryptosystemer er bygget på Kirchhoff-prinsippet, det vil si at hemmeligholdet til krypterte meldinger bestemmes av hemmeligholdet til nøkkelen. Dette betyr at selv om krypteringsalgoritmen i seg selv er kjent for kryptoanalytikeren, er han likevel ikke i stand til å dekryptere meldingen hvis han ikke har riktig nøkkel. Et chiffer anses som godt utformet hvis det ikke er noen måte å bryte det mer effektivt enn med brute force over hele nøkkelrommet, dvs. over alle mulige nøkkelverdier. GOST tilsvarer sannsynligvis dette prinsippet - i løpet av årene med intensiv forskning har ikke en eneste effektiv metode for kryptoanalyse blitt foreslått. Når det gjelder styrke, er den mange størrelsesordener overlegen den tidligere amerikanske krypteringsstandarden, DES.

GOST bruker en 256-bits nøkkel og volumet på nøkkelrommet er 2256. Ingen av de elektroniske enhetene som for øyeblikket eksisterer eller forventes å bli implementert i nær fremtid, kan brukes til å hente en nøkkel på kortere tid enn mange hundre år. Denne verdien har blitt de facto nøkkelstørrelsesstandarden for symmetriske kryptografiske algoritmer i disse dager, og den nye amerikanske krypteringsstandarden støtter den også. Den tidligere amerikanske standarden, DES, med sin reelle nøkkelstørrelse på 56 biter og volumet av nøkkelrom på bare 2 56 er ikke lenger tilstrekkelig stabil i lys av mulighetene til moderne dataverktøy. Dette ble demonstrert på slutten av 90-tallet av flere vellykkede brute force-forsøk på å bryte DES. I tillegg var DES mottakelig for spesielle kryptoanalyseteknikker som differensial og lineær. I denne forbindelse kan DES være av forskningsmessig eller vitenskapelig interesse snarere enn praktisk interesse. I 1998 ble dens kryptografiske svakhet offisielt anerkjent - US National Institute of Standards anbefalte bruk av trippel DES-kryptering. Og på slutten av 2001 ble en ny amerikansk krypteringsstandard, AES, offisielt godkjent, bygget på forskjellige prinsipper og fri fra forgjengerens mangler.

Merknader om GOST-arkitektur.

Det er velkjent at den innenlandske krypteringsstandarden er en representant for en hel familie av chiffer bygget på de samme prinsippene. Dens mest kjente "slektning" er den tidligere amerikanske krypteringsstandarden, DES-algoritmen. Alle disse chiffer, som GOST, inneholder tre-nivå algoritmer. I kjernen er det alltid et visst "grunnleggende trinn", på grunnlag av hvilke "grunnsykluser" bygges på en lignende måte, og på grunnlag av disse bygges praktiske prosedyrer for kryptering og utvikling av imitative innlegg. Dermed ligger spesifisiteten til hver av chifferene i denne familien nettopp i hovedtrinnet, eller snarere til og med i sin del. Selv om arkitekturen til klassiske blokkchiffer, som GOST refererer til, ligger langt utenfor rammen av denne artikkelen, er det fortsatt verdt å si noen ord om det.

Algoritmene for "hovedtrinnene for kryptotransformasjon" for chiffer som GOST er bygget på en identisk måte, og denne arkitekturen kalles balansert Feistel-nettverk (balansert Feistel-nettverk) etter navnet på personen som først foreslo det. Datakonverteringsplan på én syklus, eller, som det vanligvis kalles, rund , er vist i figur 7.

Figur 7. Innhold i hovedtrinnet i kryptotransformasjon for blokkchiffer som ligner på GOST.

En blokk med jevn størrelse leveres til inngangen til hovedtrinnet, hvis øvre og nedre halvdeler behandles separat fra hverandre. Under konverteringen plasseres den nedre halvdelen av blokken i stedet for den eldre halvdelen, og den eldre halvdelen, kombinert ved hjelp av den bitvise operasjonen eksklusiv eller ” med resultatet av å beregne en bestemt funksjon, i stedet for den yngste. Denne funksjonen tar som argument den lave halvdelen av blokken og nøkkelinformasjonselementet ( X), er innholdsdelen av chifferen og kalles krypteringsfunksjon . Av ulike grunner viste det seg å være fordelaktig å dele den krypterte blokken i to like store deler: | N 1 |=|N 2 | – dette faktum reflekteres av ordet "balansert" i arkitekturens navn. Kryptering av ubalanserte nettverk brukes imidlertid også fra tid til annen, men ikke like ofte som balanserte. I tillegg krever hensynet til chifferstyrken at størrelsen på nøkkelelementet ikke skal være mindre enn størrelsen på halve blokken: i GOST er alle tre størrelsene lik 32 biter .

Hvis vi bruker det ovenstående på diagrammet over hovedtrinnet til GOST-algoritmen, vil det bli åpenbart at blokkene 1,2,3 av algoritmen (se fig. 1) bestemmer beregningen av krypteringsfunksjonen, og blokkene 4 og 5 spesifiser dannelsen av utgangsblokken til hovedtrinnet basert på innholdet i inngangsblokken og krypteringsfunksjonsverdiene. Flere detaljer om arkitekturen til moderne blokkchiffer med hemmelig nøkkel finner du i klassiske verk, eller, i tilpasset form, i mine verk.

I forrige seksjon sammenlignet vi allerede DES og GOST når det gjelder holdbarhet, nå vil vi sammenligne dem når det gjelder funksjonelt innhold og enkel implementering. I GOST-krypteringssykluser gjentas hovedtrinnet 32 ​​ganger, for DES er denne verdien 16. Selve GOST-krypteringsfunksjonen er imidlertid mye enklere enn den lignende DES-funksjonen, som inneholder mange uregelmessige bitpermutasjoner. Disse operasjonene er ekstremt ineffektive på moderne ikke-spesialiserte prosessorer. GOST inneholder ikke slike operasjoner, så det er mye mer praktisk for programvareimplementering.

Ingen av DES-implementeringene for Intel x86-plattformen som er vurdert av forfatteren når halvparten av ytelsen til GOST-implementeringen som er foreslått i denne artikkelen, til tross for den to ganger kortere syklusen. Alt det ovennevnte indikerer at utviklerne av GOST tok hensyn til både de positive og negative aspektene ved DES, og også mer realistisk vurderte nåværende og fremtidige evner til kryptoanalyse. Det er imidlertid ikke lenger relevant å ta DES som grunnlag når man sammenligner ytelsen til chifferimplementeringer. Den nye amerikanske krypteringsstandarden gjør det mye bedre med effektivitet - med samme nøkkelstørrelse som GOST (256 biter), fungerer AES omtrent 14 % raskere - dette er sammenlignet med antall "elementære operasjoner". I tillegg kan GOST praktisk talt ikke parallelliseres, mens AES har mye flere muligheter i denne forbindelse. På noen arkitekturer kan denne fordelen med AES være mindre, på andre kan den være større. Så på en Intel Pentium-prosessor når den 28%. Detaljer finner du i.

Krav til kvaliteten på nøkkelinformasjon og nøkkelkilder.

Ikke alle nøkler og erstatningstabeller gir maksimal chifferstyrke. Hver krypteringsalgoritme har sine egne kriterier for å evaluere nøkkelinformasjon. For DES-algoritmen er det derfor kjent at det er såkalte " svake nøkler ", når den brukes, er ikke forbindelsen mellom åpne og krypterte data maskert tilstrekkelig, og chifferen brytes relativt lett.

Hvis et omfattende svar på spørsmålet om kvalitetskriteriene til GOST-nøkler og erstatningstabeller kan fås hvor som helst i det hele tatt, kan det bare være fra utviklerne av algoritmen. De relevante dataene ble ikke publisert i åpen presse. Imidlertid, i henhold til den etablerte prosedyren, for å kryptere klassifisert informasjon, må nøkkeldata mottatt fra en autorisert organisasjon brukes. Indirekte kan dette indikere tilstedeværelsen av metoder for kontroll av nøkkeldata for lus. Hvis tilstedeværelsen av svake nøkler i GOST er et diskutabelt problem, er tilstedeværelsen av svake erstatningsenheter hevet over tvil. Åpenbart er den "trivielle" erstatningstabellen, ifølge hvilken enhver verdi erstattes av seg selv, så svak at når du bruker den, kan chifferen enkelt knekkes, uansett hva nøkkelen er.

Som nevnt ovenfor er ikke kriterier for vurdering av nøkkelinformasjon tilgjengelig, men det kan likevel gjøres noen generelle vurderinger rundt dem.

Nøkkel

Nøkkelen må være en rekke statistisk uavhengige biter som tar på seg verdiene 0 og 1 med lik sannsynlighet. Det kan ikke utelukkes helt at enkelte spesifikke nøkkelverdier kan vise seg å være "svake", dvs. chiffer gir kanskje ikke det spesifiserte styrkenivået hvis det brukes. Imidlertid er antagelig andelen av slike verdier i den totale massen av alle mulige nøkler ubetydelig liten. I det minste har intensiv forskning på chifferen ennå ikke avslørt en eneste slik nøkkel for noen av de kjente (dvs. foreslått av FAPSI) substitusjonstabeller. Derfor vil nøkler generert ved hjelp av en virkelig tilfeldig tallsensor være av høy kvalitet med en sannsynlighet som skiller seg fra enhet med en ubetydelig liten mengde. Hvis nøklene genereres ved hjelp av en pseudo-tilfeldig tallgenerator, må generatoren som brukes gi de statistiske egenskapene ovenfor, og i tillegg ha høy kryptografisk styrke - ikke mindre enn GOST selv. Med andre ord, oppgaven med å bestemme de manglende elementene i sekvensen av elementer generert av generatoren bør ikke være enklere enn oppgaven med å bryte chifferen. I tillegg kan ulike statistiske kriterier brukes for å avvise nøkler med dårlige statistiske egenskaper. I praksis er to kriterier vanligvis tilstrekkelig: for å kontrollere den likesannsynlige fordelingen av nøkkelbiter mellom verdier 0 og 1, brukes vanligvis Pearson-testen (chi square), og for å sjekke uavhengigheten til nøkkelbiter, brukes kjøretesten . Du kan lese om de nevnte kriteriene i lærebøker eller oppslagsverk om matematisk statistikk.

Den beste tilnærmingen for å generere nøkler ville være å bruke maskinvare-mellomtonesensorer, men dette er ikke alltid akseptabelt av økonomiske årsaker. Når du genererer et lite utvalg nøkkelinformasjon, er "elektronisk rulett"-metoden et rimelig alternativ til å bruke en slik sensor, som er mye brukt i praksis, når den neste genererte delen av tilfeldige biter avhenger av tidspunktet operatøren trykker på en bestemt tast på datamaskinens tastatur. I denne ordningen er kilden til tilfeldige data databrukeren, eller mer presist, tidskarakteristikkene til reaksjonen hans. I dette tilfellet kan bare noen få biter med tilfeldig data genereres per tastetrykk, så den totale hastigheten for å generere nøkkelinformasjon er lav - opptil flere biter per sekund. Denne tilnærmingen er åpenbart ikke egnet for å skaffe store nøkler.

I tilfelle det er nødvendig å generere et stort utvalg av nøkkelinformasjon, er bruken av ulike programvaresensorer for pseudo-tilfeldige tall mulig og svært utbredt. Siden en slik sensor krever høye nivåer av kryptografisk styrke, er det naturlig å bruke gammageneratoren til selve chifferen som den - vi "skjærer" ganske enkelt gammaen generert av chifferen i "biter" av den nødvendige størrelsen, for GOST - 32 bytes. For denne tilnærmingen trenger vi selvfølgelig en "hovednøkkel", som vi kan få tak i ved hjelp av den elektroniske rulettmetoden beskrevet ovenfor, og med dens hjelp, ved å bruke et chiffer i gammageneratormodus, får vi en rekke nøkkelinformasjon av størrelsen vi trenger. Så disse to metodene for å generere nøkler - "manuell" og "algoritmisk" - fungerer i tandem og utfyller hverandre. Nøkkelgenereringsordninger i "lavbudsjetts" informasjonskryptografiske beskyttelsessystemer er nesten alltid bygget på dette prinsippet.

Substitusjonstabell

Erstatningstabellen er et langsiktig nøkkelelement, det vil si at den er gyldig i en mye lengre periode enn en enkelt nøkkel. Det antas at det er felles for alle krypteringsnoder innenfor samme kryptografiske beskyttelsessystem. Selv om konfidensialiteten til erstatningstabellen brytes, forblir styrken til chifferen ekstremt høy og synker ikke under den tillatte grensen. Derfor er det ikke noe spesielt behov for å holde bordet hemmelig, og i de fleste kommersielle applikasjoner av GOST gjøres dette. På den annen side er erstatningstabellen et kritisk element for å sikre styrken til hele chifferen. Å velge feil tabell kan føre til at chifferen lett blir brutt av kjente kryptoanalyseteknikker. Kriteriene for å utvikle erstatningsenheter er en nøye bevoktet hemmelighet og FAPSI vil neppe dele den med publikum i nær overskuelig fremtid. Til syvende og sist krever det en enorm mengde arbeid å fortelle om en gitt erstatningstabell er god eller dårlig – mange tusen arbeids- og maskintimer. Når den er valgt og brukt, må en tabell erstattes hvis og bare hvis chifferen som bruker den, viste seg å være sårbar for en eller annen type kryptoanalyse. Derfor vil det beste valget for den gjennomsnittlige chifferbrukeren være å ta en av flere tabeller som har blitt offentlige. For eksempel fra standarden for hash-funksjonen, også kjent som "sentralbank"-funksjonen; informasjon om disse tabellene kan finnes i den åpne pressen og til og med på Internett, hvis du ser godt nok etter.

For de som ikke er vant til å ta den enkle ruten, nedenfor er et generelt opplegg for å få tabeller av høy kvalitet:

1. Ved å bruke en eller annen teknikk utvikler du et sett med åtte erstatningsenheter med garanterte ikke-linearitetsegenskaper. Det er flere slike teknikker, en av dem er bruken av såkalte bøyde funksjoner.
2. Du sjekker oppfyllelsen av de enkleste "kvalitetskriteriene" - for eksempel de som er publisert for DES-erstatningsnoder. Her er noen mer generelle betraktninger i denne forbindelse: Hver substitusjonsnode kan beskrives med fire logiske funksjoner fra fire logiske argumenter. Hvis disse funksjonene er skrevet inn minimal form(dvs. med minst mulig uttrykkslengde) vil ikke være kompleks nok, en slik erstatningsnode blir avvist. I tillegg må de enkelte funksjonene innenfor hele substitusjonstabellen være tilstrekkelig forskjellige fra hverandre. På dette stadiet er mange åpenbart lavkvalitetstabeller eliminert.
3. For et chiffer med tabeller etter eget valg, bygg forskjellige runde modeller som tilsvarer forskjellige typer kryptoanalyse og mål de tilsvarende "profil"-karakteristikkene. Så, for lineær kryptoanalyse, bygg en lineær statistisk analog av krypteringsrunden og beregn "profil" -karakteristikken - en indikator på ikke-linearitet. Hvis det ikke er tilstrekkelig, avvises erstatningsbordet.
4. Til slutt, ved å bruke resultatene fra forrige avsnitt, utsetter du chifferen med tabellen du har valgt for intensiv forskning - et forsøk på kryptoanalyse ved bruk av alle kjente metoder. Dette stadiet er det vanskeligste og mest tidkrevende. Men hvis det er laget med høy kvalitet, kan det med stor sannsynlighet sies at chifferen med tabellene du har valgt ikke vil bli knekt av bare dødelige, og det er mulig, vil være for tøft for intelligensen tjenester.

Du kan imidlertid gjøre det mye enklere. Saken er at jo flere runder det er i et chiffer, jo mindre innflytelse har styrkeegenskapene til en runde på styrken til hele chifferen. GOST har hele 32 runder – flere enn i nesten alle chiffer med tilsvarende arkitektur. Derfor er det for de fleste innenlandske og kommersielle applikasjoner tilstrekkelig å skaffe substitusjonsnoder som uavhengige tilfeldige permutasjoner av tall fra 0 til 15. Dette kan praktisk talt implementeres, for eksempel ved å stokke en kortstokk med seksten kort, som hver er tildelt en av verdiene for det angitte området.

Når det gjelder substitusjonstabellen, bør et annet interessant faktum bemerkes. For reversibiliteten til krypteringssyklusene "32-З" og "32-Р" er det ikke nødvendig at erstatningsnodene er permutasjoner av tall fra 0 til 15. Alt fungerer selv om erstatningsnoden har dupliserte elementer, og erstatningen bestemt av en slik node , er irreversibel, men i dette tilfellet er styrken til chifferen redusert. Hvorfor dette er nøyaktig slik, diskuteres ikke i denne artikkelen, men det er ikke vanskelig å bekrefte selve faktum. For å gjøre dette er det nok å først prøve å kryptere og deretter dekryptere en blokk med data ved å bruke en slik "ufullstendig" erstatningstabell, hvis noder inneholder dupliserte verdier.

Variasjoner over temaet GOST

Svært ofte, for bruk i et kryptografisk databeskyttelsessystem, kreves det en algoritme med en raskere implementeringshastighet enn GOST, og så høy kryptografisk styrke er ikke nødvendig. Et typisk eksempel på slike oppgaver er ulike typer elektroniske aksjehandelssystemer som administrerer handelsøkter i sanntid. Her er krypteringsalgoritmene som brukes for å gjøre det umulig å dekryptere driftsdataene til systemet under økten (data om innsendte bestillinger, avsluttede transaksjoner, etc.), etter utløpet er disse dataene som regel ikke lenger ubrukelig for angripere. Det kreves med andre ord garantert holdbarhet på bare noen få timer – dette er den typiske varigheten av en handelsøkt. Det er klart at å bruke en fullverdig GOST i denne situasjonen ville være å skyte spurver med en kanon.

Hva skal jeg gjøre i dette og lignende tilfeller for å øke krypteringshastigheten? Svaret ligger på overflaten - bruk en modifikasjon av chifferen med færre hovedtrinn (runder) i grunnsyklusene. De gangene vi reduserer antall krypteringsrunder, øker ytelsen like mye. Denne endringen kan oppnås på to måter - ved å redusere lengden på nøkkelen og redusere antall "gjennomgangssykluser" av nøkkelen. Husk at antallet grunnleggende trinn i grunnleggende krypteringssykluser er N=n·m, Hvor n– antall 32-biters elementer i nøkkelen, m– antall sykluser med bruk av nøkkelelementer, i standarden n=8, m=4. Du kan redusere hvilket som helst av disse tallene, men det enkleste alternativet er å redusere lengden på nøkkelen uten å påvirke måten den brukes på.

Det er klart at prisen for å fremskynde arbeidet vil være en nedgang i chifferets styrke. Den største vanskeligheten er at det er ganske vanskelig å mer eller mindre nøyaktig anslå størrelsen på denne reduksjonen. Åpenbart er den eneste mulige måten å gjøre dette på å gjennomføre en fullskala studie av chiffervarianter med reduserte kryptografiske konverteringssykluser. Det er klart at for det første krever dette bruk av klassifisert informasjon, som bare eies av utviklerne av GOST, og for det andre er det veldig arbeidskrevende. Derfor vil vi nå prøve å gi en veldig, veldig grov vurdering, kun basert på generelle mønstre.

Når det gjelder motstanden til chifferen mot sprekking med "omfattende" metoder, det vil si mot et "brute force"-angrep, er alt mer eller mindre klart her: en nøkkel på 64 bit er et sted på grensen til å være tilgjengelig for denne typen av angrep, er et chiffer med en nøkkel på 96 biter eller høyere (husk at nøkkelen må inneholde et heltall på 32-bits elementer) ganske motstandsdyktig mot det. Faktisk, for flere år siden ble den forrige amerikanske krypteringsstandarden, DES, gjentatte ganger hacket av brute force-metoder - først ble den hacket av et datanettverk organisert på grunnlag av det globale Internett, og deretter av et spesialisert nettverk, dvs. en datamaskin designet spesielt for dette formålet. La oss anta at standardversjonen av GOST, når den implementeres i programvare på moderne prosessorer, fungerer fire ganger raskere enn DES. Da vil den 8-runde "reduserte GOST" fungere 16 ganger raskere enn DES. La oss også anta at i tiden etter DES-hacket, har dataytelsen firedoblet seg i henhold til Moores lov. Som et resultat får vi at det nå er 64 ganger raskere å sjekke en 64-bits nøkkel for "redusert GOST" med åtte sykluser enn å sjekke en DES-nøkkel om gangen. Dermed er fordelen med denne versjonen av GOST fremfor DES når det gjelder kompleksiteten til et brute-force angrep redusert fra 2 64–56 = 2 8 = 256 til 256 / 64 = 4 ganger. Enig, dette er en veldig illusorisk forskjell, nesten ingenting.

Det er mye vanskeligere å vurdere motstanden til svekkede GOST-modifikasjoner mot "intensive" metoder for kryptoanalyse. Et generelt mønster kan imidlertid spores også her. Faktum er at "profil"-egenskapene til mange av de kraftigste typene kryptoanalyse i dag avhenger eksponentielt av antall krypteringsrunder. Så for lineær kryptoanalyse (LCA) vil dette være en linearitetskarakteristikk L :

Hvor C og er konstanter, R er antall runder. Et lignende forhold eksisterer for differensiell kryptoanalyse. I sin "fysiske betydning" er alle egenskaper av denne typen sannsynligheter. Vanligvis er mengden innledende data som kreves for kryptoanalyse og dens kompleksitet omvendt proporsjonal med slike egenskaper. Det følger at disse arbeidsintensitetsindikatorene vokser eksponentielt med antall grunnleggende krypteringstrinn. Derfor, når antall runder reduseres flere ganger, vil kompleksiteten til de mest kjente analysetypene endre seg som, veldig tilnærmet og grovt, roten til denne kraften fra den opprinnelige mengden. Dette er et veldig stort fall i holdbarhet.

På den annen side ble GOST designet med stor sikkerhetsmargin og er i dag motstandsdyktig mot alle kjente typer kryptoanalyse, inkludert differensial og lineær. I forhold til LCA betyr dette at for dens vellykkede implementering kreves det flere "åpne blokk-krypterte blokker"-par enn "eksisterer i naturen", det vil si mer enn 2 64 . Når det tas i betraktning det ovennevnte, betyr dette at for en vellykket LCA av en 16-runders GOST, vil det være nødvendig med minst blokker eller 2 35 byte eller 32 GB data, og for en 8-runder, minst blokker eller 2 19 byte eller 0,5 MB.

Konklusjonene fra alt det ovennevnte er gitt i tabellen nedenfor, som oppsummerer egenskapene til de reduserte versjonene av GOST.

Antall runder	Nøkkelstørrelse, biter	Ytelsesindeks	Sannsynlige egenskaper ved chifferen (veldig grovt anslag)
24	192	1,33	Motstandsdyktig mot de fleste kjente typer CA, eller på grensen til motstand. Den praktiske implementeringen av CA er umulig på grunn av høye krav til innledende data og arbeidsintensitet.
16	128	2	Teoretisk sett er det ustabilt for noen typer kryptoanalyse, men deres praktiske implementering er i de fleste tilfeller vanskelig på grunn av høye krav til kildedata og arbeidsintensitet.
12	95	2,67	Den er ikke motstandsdyktig mot noen kjente typer kryptoanalyse, men er egnet for å sikre hemmelighold av små mengder data (opptil titalls eller hundrevis av kilobyte) i en kort periode.
8	64	4	Den er ikke motstandsdyktig mot noen kjente typer kryptoanalyse, men er egnet for å sikre hemmelighold av små datamengder (opptil titalls kilobyte) i en kort periode.

De to siste alternativene, med 12 og 8 runder, er i stand til å gi svært, veldig begrenset tidsbeskyttelse. Bruken deres er kun berettiget i oppgaver der det kun kreves kortvarig hemmelighold av de beskyttede dataene, i størrelsesorden flere timer. Et mulig bruksområde for disse svake chiffervariantene er å blokkere UDP-trafikk fra elektroniske børshandelssystemer. I dette tilfellet blir hver datapakke (datagram, den midterste "D" fra forkortelsen UDP) kryptert med en separat 64-bits nøkkel, og selve nøkkelen krypteres med en sesjonsnøkkel (en nøkkel hvis omfang er én kommunikasjonsøkt mellom to datamaskiner) og overføres sammen med data.

Før jeg avslutter med de reduserte versjonene av GOST, vil jeg si at alle de ovennevnte hensyn er svært spekulative. Standarden gir holdbarhet for kun én variant med 32 runder. Og ingen kan gi deg garantier for at motstanden til reduserte versjoner av chifferen mot sprekker vil endre seg på den måten som er angitt ovenfor. Hvis du likevel bestemmer deg for å bruke dem i utviklingen din, husk at du har tråkket på svært ustø underlag, som når som helst kan skli ut under føttene dine. Siden krypteringshastighet er et kritisk problem for deg, bør du kanskje vurdere å bruke en raskere chiffer eller en kraftigere datamaskin? En annen vurdering av hvorfor dette er verdt å gjøre, er at svekkede versjoner av GOST vil være mest følsomme for kvaliteten på erstatningsenhetene som brukes.

Problemet som vurderes har også en bakside. Hva om krypteringshastigheten ikke er kritisk, men styrkekravene er veldig strenge? Motstanden til GOST kan økes på to måter - la oss kalle dem "omfattende" og "intensive". Den første av dem er ikke mer enn en enkel økning i antall krypteringsrunder. Det er ikke helt klart for meg hvorfor dette faktisk kan være nødvendig, siden den innenlandske standarden allerede gir den nødvendige holdbarheten uten dette. Men hvis du lider av paranoia mer enn det nødvendige nivået (og alle "informasjonsforsvarere" er ganske enkelt forpliktet til å lide av det, dette er en betingelse for profesjonell egnethet, det eneste spørsmålet er alvorlighetsgraden av saken:), vil dette hjelpe du roer deg litt ned. Hvis du ikke er sikker på dette KGB-chifferet eller erstatningstabellen du bruker, kan du bare doble, firedoble osv. antall runder – velg multiplisitet basert på alvorlighetsgraden av saken din. Denne tilnærmingen lar deg virkelig øke styrken til chifferen - hvis tidligere krypteringsanalyse rett og slett var umulig, er det nå umulig i kvadrat!

Et mer vanskelig og interessant spørsmål er om det er mulig å øke styrken til chifferen uten å endre antall og struktur på hovedkrypteringstrinnene. Overraskende nok er svaret på dette positivt, selv om vi igjen tråkker på spekulasjonenes vaklende grunn. Faktum er at i GOST, ved hovedkonverteringstrinnet, er det ment å erstatte 4 x 4 biter, men i praksis (vi vil snakke om dette senere) utfører alle programvareimplementeringer erstatningsbyte for byte, dvs. 8 x 8 bits - dette gjøres av effektivitetshensyn. Hvis vi umiddelbart designer en slik erstatning som en 8-bits, vil vi forbedre ytelsen til en runde betydelig. For det første vil "diffusjons"-karakteristikken eller "skred"-indikatoren øke - en bit av kildedataene og/eller nøkkelen vil påvirke et større antall biter av resultatet. For det andre, for større erstatningsnoder, kan lavere differensial- og lineære egenskaper oppnås, og dermed redusere chifferens mottakelighet for lignende typer kryptoanalyse. Dette gjelder spesielt for reduserte GOST-sykluser, og for alternativer med 8 og 12 runder er et slikt trinn ganske enkelt nødvendig. Dette vil noe kompensere for tapet av holdbarhet i dem fra reduksjonen i antall runder. Det som gjør det vanskelig å bruke denne teknikken er at du må designe slike "forstørrede" erstatningsenheter selv. Og også det faktum at større enheter generelt er mye vanskeligere å konstruere enn mindre.

Ikke-standard bruk av standarden.

Selvfølgelig er hovedformålet med GOST kryptografiske algoritmer kryptering og databeskyttelse. Imidlertid kan de også finne andre applikasjoner relatert, naturlig nok, til informasjonssikkerhet. La oss kort snakke om dem:

1. For kryptering i gamma-modus sørger GOST for utvikling av en kryptografisk gamma - en sekvens av biter med gode statistiske egenskaper og høy kryptografisk styrke. Denne gammaen brukes deretter til å endre åpne data, noe som resulterer i krypterte data. Dette er imidlertid ikke den eneste mulige anvendelsen av kryptografisk gamma. Faktum er at algoritmen for genereringen er en pseudo-tilfeldig tallsekvensgenerator (PRNG) med utmerkede egenskaper. Å bruke en slik PRNG der bare de statistiske egenskapene til den genererte sekvensen kreves, men kryptografisk styrke ikke er nødvendig, er selvfølgelig ikke veldig rimelig - for disse tilfellene er det mye mer effektive generatorer. Men for ulike applikasjoner relatert til informasjonssikkerhet, vil en slik kilde være veldig nyttig:

• Som nevnt ovenfor kan gamma brukes som et "råmateriale" for å generere nøkler. For å gjøre dette trenger du bare å få et gammasegment med ønsket lengde - 32 byte. På denne måten kan nøkler lages etter behov og de trenger ikke lagres – hvis en slik nøkkel trengs igjen, vil det være ganske enkelt å generere den igjen. Du trenger bare å huske hvilken nøkkel den opprinnelig ble generert på, hvilken synkroniseringsmelding som ble brukt, og hvilken byte av den genererte gammaen nøkkelen begynte med. All informasjon unntatt nøkkelen som brukes er uklassifisert. Denne tilnærmingen vil gjøre det enkelt å kontrollere et ganske komplekst og forgrenet nøkkelsystem ved å bruke bare én "hovednøkkel".
• I likhet med den forrige kan gamma brukes som det første "råmaterialet" for å generere passord. Her kan spørsmålet oppstå: hvorfor er det nødvendig å generere dem i det hele tatt? Er det ikke lettere å bare finne dem opp etter behov? Feilen i denne tilnærmingen ble tydelig demonstrert av en rekke hendelser i datanettverk, hvorav den største var den daglige lammelsen av Internett i november 1988 forårsaket av Morris-ormen. En av måtene et ondsinnet program penetrerte en datamaskin på var ved å gjette passord: Programmet prøvde å komme inn i systemet ved å prøve passord i rekkefølge fra den interne listen på flere hundre, og i en betydelig andel av tilfellene lyktes det. Den menneskelige fantasien for å finne opp passord viste seg å være svært dårlig. Det er grunnen til at i de organisasjonene der sikkerheten er viet behørig oppmerksomhet, genereres passord og distribueres til brukere av systemsikkerhetsadministratoren. Å generere passord er litt mer komplisert enn å generere nøkler, siden i dette tilfellet må den "rå" binære gammaen konverteres til symbolsk form, og ikke bare "kuttes" i biter. I tillegg kan det hende at individuelle verdier må forkastes for å sikre at det er like sannsynlig at alle alfabetiske tegn vises i passordet.
• En annen måte å bruke kryptografisk gamma på er garantert sletting av data på magnetiske medier. Faktum er at selv når informasjon omskrives på et magnetisk medium, forblir spor av tidligere data, som kan gjenopprettes ved passende undersøkelse. For å ødelegge disse sporene, må slik overskriving utføres flere ganger. Det viste seg at det ville være nødvendig å omskrive informasjon til media færre ganger hvis en slik prosedyre brukte tilfeldige eller pseudo-tilfeldige data som ville forbli ukjente for eksperter som prøver å gjenopprette den slettede informasjonen. Gamma-chifferet vil komme godt med her.

2. Ikke bare den kryptografiske gammaen, men også selve kryptotransformasjonen kan brukes til behov som ikke er direkte relatert til kryptering:

• Vi vet at et av disse alternativene for å bruke GOST er utviklingen av simulerte innsatser for datamatriser. På grunnlag av et hvilket som helst blokkchiffer, inkludert GOST, er det imidlertid ganske enkelt å konstruere et skjema for å beregne en enveis hashfunksjon, også kalt i litteraturen MDC, som i forskjellige kilder står for endre deteksjonskode / manipulasjon (M modifikasjon/ M animasjon D eteksjon C ode) eller meldingssammendrag (M essay D fordøye C ode). Den første dekodingen dukket opp i litteraturen mye tidligere, den andre, kortere, tror jeg, ble oppfunnet av de som ikke var i stand til å huske den første :), - det var en spøk. MDC kan brukes direkte i imitasjonsbeskyttelsessystemer som en analog til imitasjonsinnsetting, som imidlertid ikke er avhengig av den hemmelige nøkkelen. I tillegg er MDC mye brukt i elektronisk digital signatur (EDS), fordi de fleste av slike ordninger er utformet på en slik måte at det er praktisk å signere en datablokk med fast størrelse. Som du vet, på grunnlag av den diskuterte GOST 28147-89-standarden, ble den russiske føderasjonens standard for beregning av enveis-hash-funksjonen GOST R34.11-94 bygget.
• Det er mindre kjent at på grunnlag av et hvilket som helst blokkchiffer, inkludert GOST, kan det bygges et fullt funksjonelt digitalt signaturskjema, med en hemmelig signaturnøkkel og en åpen verifiseringskombinasjon. Av en rekke årsaker har denne ordningen ikke fått bred praktisk distribusjon, men i noen tilfeller kan den fortsatt betraktes som et svært attraktivt alternativ til de "matematiske" digitale signaturordningene som for tiden dominerer i verden.

Litteratur

Informasjonsbehandlingssystemer. Kryptografisk beskyttelse. Kryptografisk transformasjonsalgoritme GOST 28147-89. Stat Com. USSR i henhold til standarder, M., 1989. ftp://ftp.wtc-ural.ru/pub/ru.crypt/GOST-28147
Shannon Claude. Matematisk teori om hemmelige systemer. I samlingen «Works on information theory and kybernetics», M., IL, 1963, s. 333-369. http://www.enlight.ru/crypto/articles/shannon/shann__i.htm
Kunngjøring av godkjenning av Federal Information Processing Standard (FIPS) 197, Advanced Encryption Standard (AES), Federal Register Vol. 66, nr. 235 / torsdag 6. desember 2001 / Notices, s. 63369–63371. http://csrc.nist.gov/encryption/aes/
Feistel Horst. Kryptografi og datasikkerhet. Oversettelse av A. Vinokurov ifølge publikasjonen Horst Feistel. Cryptography and Computer Privacy, Scientific American, mai 1973, vol. 228, nr. 5, s. 15-23. http://www.enlight.ru/crypto/articles/feistel/feist_i.htm
Schneier Bruce. Anvendt kryptografi. 2. utg. Protokoller, algoritmer og kildetekster på C-språk., M., "Triumph", 2002 http://www.ssl.stu.neva.ru/psw/crypto/appl_rus/appl_cryp.htm
Menezes Alfred, van Oorschot Paul, Vanstone Scott. Håndbok for anvendt kryptografi. ttp://www.cacr.math.uwaterloo.ca/hac/
Vinokurov Andrey. Hvordan fungerer et blokkchiffer? Manuskript. http://www.enlight.ru/crypto/articles/vinokurov/blcyph_i.htm
Vinokurov Andrey. Problemer med kryptografi for det elektroniske tidsskriftet inNFUSED BYTES online. http://www.enlight.ru/crypto/articles/ib/ib.htm
Vinokurov Andrey, Primenko Eduard. Tekst til rapporten "Om programvareimplementering av krypteringsstandarder i den russiske føderasjonen og USA," konferanse om informatisering, Moskva, MEPhI, 28.-29. januar 2001. Publisert i konferansehandlinger.
Informasjonsteknologi. Kryptografisk informasjonsbeskyttelse. Hash-funksjon GOST R34.11-94, State Standard of the Russian Federation, M., 1994.

Algoritme GOST 28147-89

GOST 28147-89 er en sovjetisk og russisk symmetrisk krypteringsstandard introdusert i 1990, også en CIS-standard. Fullt navn - "GOST 28147-89 Informasjonsbehandlingssystemer. Kryptografisk beskyttelse. Kryptografisk konverteringsalgoritme."

Ris. 4.

Blokkchifferalgoritme. Når du bruker gamma-krypteringsmetoden, kan den utføre funksjonene til en strømchifferalgoritme. GOST 28147-89 -- blokkchiffer med en 256-bits nøkkel og 32 konverteringssykluser, som opererer på 64-biters blokker. Grunnlaget for chifferalgoritmen er Feistel-nettverket. Det er fire driftsmoduser i henhold til GOST 28147-89: enkel utskifting, gambling, gambling med tilbakemelding ogsmodus.

Fordelene med algoritmen: nytteløsheten til et kraftangrep, effektiviteten av implementeringen og følgelig høy ytelse på moderne datamaskiner, tilstedeværelsen av beskyttelse mot pålegging av falske data (generering av imitativ innsetting) og den samme krypteringssyklusen i alle fire GOST-algoritmer, en større nøkkel sammenlignet med DESX-algoritmen.

Ulemper med algoritmen: Hovedproblemene til GOST er relatert til standardens ufullstendighet når det gjelder generering av nøkler og erstatningstabeller. Det antas at GOST har "svake" nøkler og erstatningstabeller, men standarden beskriver ikke kriteriene for å velge og eliminere "svake". Standarden spesifiserer heller ikke en algoritme for å generere en substitusjonstabell (S-bokser). På den ene siden kan dette være ekstra hemmelig informasjon (i tillegg til nøkkelen), og på den annen side reiser det en rekke problemer: det er umulig å bestemme den kryptografiske styrken til algoritmen uten å kjenne substitusjonstabellen på forhånd ; implementeringer av algoritmen fra forskjellige produsenter kan bruke forskjellige erstatningstabeller og kan være inkompatible med hverandre; muligheten for bevisst levering av svake erstatningstabeller av lisensmyndighetene i den russiske føderasjonen.

Fordeler med IDEA fremfor analoger

I programvareimplementering på Intel486SX er dobbelt så rask som DES IDEA, som er en betydelig økning i hastighet; IDEAs nøkkellengde er 128 biter, mot 56 biter for DES, som er en god forbedring mot brute-force-nøkler. Sannsynligheten for å bruke svake taster er svært liten og utgjør 1/2 64 . IDEA er raskere enn GOST 28147-89-algoritmen (i programvareimplementering på Intel486SX). Bruk av IDEA i parallelle krypteringsmoduser på Pentium III- og Pentium MMX-prosessorer gjør det mulig å oppnå høye hastigheter. Sammenlignet med AES-finalistene er 4-veis IDEA bare litt tregere enn RC6 og Rijndael på Pentium II, men raskere enn Twofish og MARS. På Pentium III er 4-veis IDEA enda raskere enn RC6 og Rijndael. En annen fordel er at den er godt studert og motstandsdyktig mot velkjente kryptoanalyseverktøy.

1 Blokkdiagram av den kryptografiske transformasjonsalgoritmen 1

2 Enkel utskiftingsmodus 4

3 Gamma-modus 8

4 Gamma-modus med tilbakemelding 11

5 Si14

Vedlegg 1 Begreper brukt i denne standarden og deres definisjoner 16

Vedlegg 2 Verdier av konstanter C1, C2 18

Vedlegg 3 Opplegg for programvareimplementering av den kryptografiske algoritmen

transformasjoner. 19

Vedlegg 4 Regler for summering modulo 2 32 og modulo (2 32 -I) 25

STATENS STANDARD

USSR UNION

INFORMASJONSBEHANDLINGSSYSTEMER. KRYPTOGRAFISK SIKKERHET

Kryptografisk konverteringsalgoritme

Dato for introduksjon 07/01/90

Denne standarden etablerer en enhetlig kryptografisk transformasjonsalgoritme for informasjonsbehandlingssystemer i nettverk av elektroniske datamaskiner (datamaskiner), individuelle datasystemer og datamaskiner, som definerer reglene for datakryptering og utvikling av imitasjoner.

Den kryptografiske transformasjonsalgoritmen er utformet for maskinvare- eller programvareimplementering, tilfredsstiller kryptografiske krav og pålegger i sin kapasitet ikke begrensninger på graden av hemmelighold av den beskyttede informasjonen.

Standarden er obligatorisk for organisasjoner, virksomheter og institusjoner som bruker kryptografisk beskyttelse av data lagret og overført i datanettverk, i separate datasystemer eller i datamaskiner.

Begrepene som brukes i denne standarden og deres definisjoner er gitt i vedlegg 1.

I. BLOKKDIAGRAM FOR DEN KRYPTOGRAFISKE TRANSFORMASJONSALGORITIMEN

1.1. Blokkdiagrammet for den kryptografiske transformasjonsalgoritmen (kryptoskjemaet) inneholder (se figur 1):

Offisiell publikasjon ★

en 256-bits nøkkellagringsenhet (KSD), bestående av åtte 32-bits stasjoner (X0, Xt. X2, A3 L4, X$, X6, Xu); fire 32-bits stasjoner (/V (, N 2, Nj, /V 4);

Reproduksjon er forbudt

© Standards Publishing House, 1989 © IPK Standards Publishing House, 1996

to 32-bits stasjoner L/$,) med permanente fyllinger C 2, C\\ registrert i dem

to 32-bits modulo 2 32 addere (SM|, SL/3);

32-bit adder av bitvis summering modulo 2 (SL/2);

32-bit modulo adderer (2 32 - 1) (SL/ 4);

modulo 2(SL/5) adderer, det er ingen begrensning på kapasiteten til SL/$ addereren;

substitusjonsblokk (A);

syklisk skiftregister elleve trinn mot det mest signifikante sifferet (R).

1.2. Substitusjonsblokken A" består av åtte substitusjonsnoder A'j,

A 2, A“z, K 4, A5, A7, A 8 med 64-bits minne hver. Post

En 32-bit vektor brukt på en substitusjonsblokk deles inn i åtte sekvensielle 4-bit vektorer, som hver blir konvertert til en 4-bit vektor av den tilsvarende substitusjonsnoden, som er en tabell med seksten rader som inneholder fire utfyllingsbiter per rad . Inngangsvektoren bestemmer adressen til en rad i tabellen, fyllingen av denne raden er utgangsvektoren. 4-bits utgangsvektorene blir deretter sammenkoblet sekvensielt til en 32-bits vektor.

1.3. Når du legger til og syklisk skifter binære vektorer, anses de mest signifikante bitene for å være bitene til lagringsenhetene med store tall.

1.4. Når du skriver nøkkelen (I", W 2 ..., W q e (0,1), d = N256, i

RCU-verdien W\ legges inn i det i-te sifferet til frekvensomformeren Xq, verdien W 2 legges inn i det andre sifferet til frekvensomformeren L#, ..., verdien W^ 2 legges inn i det 32. sifferet til stasjonen Xq; verdien W33 legges inn i det første sifferet til stasjonen X\ y, verdien legges inn i det andre sifferet til stasjonen X\ y..., verdien W M legges inn i det 32. sifferet til stasjonen X\\ den verdien W 6 5 legges inn i det første sifferet til stasjonen X 2 osv., verdien 1U 2 5b legges inn i den 32. biten til Xy-stasjonen.

1.5. Ved omskrivning av informasjon omskrives innholdet i p-te-sifferet til en stasjon (adder) til p-te-sifferet til en annen stasjon (adder).

1.6. Verdiene for konstante fyllinger Cj, C 2 (konstanter) for lagringsenheter /V 6, /V5 er gitt i vedlegg 2.

1.7. Nøklene som bestemmer fyllingen av KZU og tabeller i substitusjonsblokken K er hemmelige elementer og leveres på foreskrevet måte.

Å fylle tabellene i substitusjonsblokken K er et langsiktig nøkkelelement felles for datanettverket.

Organiseringen av ulike typer kommunikasjon oppnås ved å bygge et hensiktsmessig nøkkelsystem. I dette tilfellet kan muligheten for å generere nøkler (fylle KZU) i en enkel erstatningsmodus og kryptere dem i en enkel erstatningsmodus samtidig som det gir imitasjonsbeskyttelse for overføring over kommunikasjonskanaler eller lagring i datamaskinens minne, brukes.

1.8. Kryptoordningen sørger for fire typer arbeid: kryptering (dekryptering) av data i enkel erstatningsmodus; kryptering (dekryptering) av data i gammamodus;

kryptering (dekryptering) av data i gammamodus med tilbakemelding;

simuleringsinnleggsgenereringsmodus.

Opplegg for programvareimplementering av den kryptografiske transformasjonsalgoritmen er gitt i vedlegg 3.

2. ENKEL ENDRINGSMODUS

2.1. Kryptering av klare data ved hjelp av enkel erstatningsmodus

2.1.1. Kryptoskjemaet som implementerer krypteringsalgoritmen i enkel erstatningsmodus skal ha formen vist i figur 2.

Åpne data som skal krypteres er delt inn i blokker på 64 bit hver. Inndata for hvilken som helst blokk T () = (D|(0), ^(O), ..., d 3 1(0), i 32 (0), £|(0), b 2 (0) y. ..., Z> 32 (0)) av binær informasjon i stasjonene N\ og N 2 utføres slik at verdien D|(0) legges inn i den 1. biten av N|, verdien a 2 (0) er lagt inn i 2. bit / Vj, etc., er verdien i 32 (0) lagt inn i 32. siffer iVj; verdi />|(0) angis

1. siffer L/ 2, verdien b 2 (0) legges inn i 2. siffer N 2 osv., verdien >> 32 (0) legges inn i 32. siffer N 2. Som et resultat oppnås tilstanden (i 32 (0), i 3 |(0), ... og 2 (0) y<7|(0)) накопителя yVj и состояние (/>32 (0), b 2 1(0), ... , />|(0)) lagerenhet N 2.

2.1.2. 256 biter av nøkkelen legges inn i RCU. Innholdet i åtte 32-bits stasjoner Aq, X\ t ..., Xj har formen:

^0 = (^32^3.....

*1 =(^64^63, . ^34^33)

*7 = (^56> ^255. ... , I/ 226, ^ 225)

2.1.3. Krypteringsalgoritmen for en 64-biters blokk med vanlig data i enkel erstatningsmodus består av 32 sykluser.

I den første syklusen summeres den innledende fyllingen av lageret modulo 2 32 i adderen CM\ med fyllingen av lageret Xq, mens fyllingen av lageret Nj opprettholdes.

Resultatet av summeringen konverteres i substitusjonsblokken K og den resulterende vektoren sendes til inngangen til registeret /?, hvor den syklisk forskyves med elleve trinn mot de mest signifikante bitene. Resultatet av skiftet summeres bit for bit modulo 2 i adderen CM 2 med 32-bits fylling av stasjonen yV 2 . Resultatet oppnådd i CM 2 skrives i N\%, med den gamle fyllingen N| omskrevet til N 2. Den første syklusen avsluttes.

Etterfølgende sykluser utføres på samme måte, med

I 2. syklus leses fyllingen X\ fra RCU, i 3. syklus fra RCU

fyllingen X2 leses, etc., i den 8. syklusen leses fyllingen Xj fra RCU. I sykluser fra 9 til 16, så vel som i sykluser fra 17 til 24, leses fyllinger fra RCU i samme rekkefølge:

I de siste åtte syklusene fra den 25. til den 32. er rekkefølgen for lesing av RCD-fyllingene reversert:

helvete, helvete, helvete.

Ved kryptering i 32 sykluser utføres derfor følgende rekkefølge for valg av lagringsfyll:

helvete, ^2,^),^4>^5,^6"^7, helvete, ^2,^3"^4,^5,-^6,^7, helvete, helvete, helvete, helvete, helvete ,helvete,helvete,helvete.

I 32. syklus legges resultatet fra addereren SL/ 2 inn i stasjonen CU 2, og den gamle fyllingen lagres i stasjonen N\.

Mottatt etter den 32. syklusen med kryptering for å fylle N| og N2 er den krypterte datablokken som tilsvarer den vanlige datablokken.

2.1 4 Krypteringsligninger i enkel erstatningsmodus har formen:

J*Cr> "(

I b(/) = a(/~ I)

ved y = 1-24;

G"

\bO) - a O - O at / 8* 25 -g 31; a(32) = a(31)

A (32) = (d (31) ffl X 0)KRG> b (31)

hvor d(0) = (a 32 (0), «з|(0), ... , Д|(0)) er den første utfyllingen av N\ før den første krypteringssyklusen;

6(0) = (632(0), 63j(0), ... , 6j(0)) - innledende fylling /U 2 før den første krypteringssyklusen;

a(j) = (032(7), 0з|(/) e... , 0|(/)) - fylling av kontrollenheten, etter den y-te krypteringssyklusen;

b(j) = (6× 2 (/), 63j(/"), ... , 6|(/)) - fylling /V 2 etter den ytte krypteringssyklusen, y = 032.

Tegnet φ betyr den bitvise summeringen av 32-bit vektorer modulo 2.

Tegnet Ш betyr summeringen av 32-bit vektorer modulo 2 32. Reglene for summering modulo 2 32 er gitt i vedlegg 4;

/? - operasjonen av et syklisk skifte på elleve trinn mot de høyeste sifrene, dvs.

^(g 32"O|>g 30>g 29>g 28>g 27>g 26"g 25>g 24>g 23'G 22"G 2b G 20>"g 2* g |)~

= (g 21" g 20> - "g 2* g 1 * G 32>G31 *GzO" g 29* g 28*, 27e"26e/"25>, 24>G23", 22)*

2.1.5. 64-bits blokken med krypterte data Tsh sendes ut fra stasjonene L^, VU 2 i følgende rekkefølge: fra 1., 2., ..., 32. bit av stasjon L7|, deretter fra 1., 2., ... , 32. bit lagring W 2, dvs.

t w - (a,<32),0 2 (32),0 32 (32), 6,(32), 6 2 <32),6 32 <32».

De resterende blokkene med åpne data i enkel erstatningsmodus er kryptert på samme måte.

2.2. Dekryptering av krypterte data ved hjelp av enkel erstatningsmodus

2.2.1. Kryptoskjemaet som implementerer dekrypteringsalgoritmen i enkel erstatningsmodus har samme form (se Chsrt.2) som for kryptering. 256 biter av samme nøkkel som brukes til kryptering legges inn i RCU. De krypterte dataene som skal dekrypteres er delt inn i blokker på 64 bit hver. Skriv inn en hvilken som helst blokk

T w - (0,(32),o 2 (32), ..., 0 32 (32), 6,(32), 6 2 (32), ..., 6 32 (32))

inn i akkumulatorer L', og N 2 produseres slik at verdien dj(32) legges inn i 1. siffer /V, verdien o 2 (32) legges inn i 2. siffer /V osv., verdien a 32 (32) legges inn i det 32. sifferet /V,; verdien 6,(32) legges inn i 1. siffer i N2 osv., verdien 6 32 (32) legges inn i 32. siffer i N2.

2.2.2. Dekryptering utføres i henhold til samme algoritme som kryptering av åpne data, med den forskjellen at fyllingene til stasjonene Xq, X\y..., Xj leses fra RCU i dekrypteringssykluser i følgende rekkefølge:

helvete, helvete 3, helvete, helvete, helvete, helvete, helvete, helvete 0,

helvete 6, helvete 4, helvete 2, helvete, helvete, helvete, helvete 2, helvete.

2.2.3. Dekrypteringsligningene ser slik ut:

G d (32 - /) = (d (32 - / + 1) SHLG,.,) *LF6(32 - / + 1) b (32 - /) = d (32 - / + 1) at, / = 1+8;

I o(32- /) = (a(32-/M)SHDG (32 _ /)(tod8))KLFL(32./M) |6(32-/) = d (32 - / + 1)

ved /= 9 + 31;

b(0) = (a (1) ШДГо) ОФй(1)

2.2.4. W- og N2-stasjonene oppnådd etter 32 driftssykluser utgjør en blokk med åpne data.

Da = (fli(O), a 2 (0), ... , Az 2 (0)" 6, (0), 6 2 (0), ... , 6 32 (0)), tilsvarende blokk med krypterte data, mens verdien o,(0) til blokk 7® tilsvarer innholdet i 1. bit yV, tilsvarer verdien 02(0)

S. 8 GOST 28147-89

tilsvarer innholdet i 2. bit N\, etc., verdien Dz2(0) tilsvarer innholdet i 32. bit N\; verdien 6j(0) tilsvarer innholdet i 1. bit; verdien ^(0) tilsvarer innholdet i 2. bit N2 osv., verdien £зг(0) tilsvarer innholdet i 32. bit N2 -

De resterende blokkene med krypterte data dekrypteres på samme måte.

2.3. Krypteringsalgoritmen i modusen for enkel utskifting av 64-bits blokken G 0 er betegnet med A y, dvs.

A (T 0) = A (a (0), b (0)) = (a (32), b (32)) = T w.

2.4. Den enkle erstatningsmodusen kan kun brukes til å kryptere (dekryptere) data i tilfellene gitt i klausul 1.7.

3. SPILLEMODUS

3.1. Kryptering av åpne data i gammamodus

3.1.1. Kryptoskjemaet som implementerer krypteringsalgoritmen i gamma-modus har formen vist i figur 3.

Åpne data, delt inn i 64-bits blokker T\)\ 7), 2) ..., 7)) m “, 1 7[) M), krypteres i gammamodus ved bitvis summering modulo 2 i adderen SL/ 5 med chiffer gamma Гш, som produseres i blokker på 64 biter, dvs.

G _/L1) R2) Lm-1) LM)\

"ill V 1 w e * w * » " Sh » " * * * " 111 /»

hvor M er bestemt av volumet av krypterte data.

Tjj) - Yth 64-bit block, /“ antall binære sifre i blokk 7J) M) kan være mindre enn 64, mens den delen av chifferspekteret som ikke brukes til kryptering fra blokk Г\^] forkastes.

3.1.2. 256 biter av nøkkelen legges inn i RCU. En 64-bits binær sekvens (synkroniseringsmelding) S = (5*1, S 2, ..., 5^4) introduseres i stasjonene iVj, N 2, som er den første fyllingen av disse stasjonene for den påfølgende generasjonen av M-blokker av chiffer gamma. Synkroniseringsmeldingen legges inn i jV| og L^slik at verdien 5[ legges inn i 1. siffer i VU), verdien S 2 legges inn i 2. siffer N\ osv., verdien ^skrives inn i 32. siffer 7V|; verdien S33 legges inn i 1. siffer N2, verdien 4S34 legges inn i 2. siffer N2 osv., verdien legges inn i 32. siffer N2.

3.1.3. Den første fyllingen av stasjoner /Vj og N 2 (synkroniseringsmelding.5) er kryptert i enkel erstatningsmodus iht.