Algoritmen defineret af GOST 28147 89-standarden er. Nem udskiftningstilstand

"Mens du lever, skal du ikke dø, se på denne verden.
Mange her har en død sjæl – de er døde indeni.
Men de går og griner uden at vide, at de ikke er der,
Skynd dig ikke med din dødstid," fortalte hun mig.

Aria, "Deroppe"

Introduktion

Introduktion til blokcifre

2.1 Feistel netværk.
2.2 Blok chiffer GOST 28147-89

Teoretisk minimum

3.1 Nøgleoplysninger
3.2 Grundlæggende trin i kryptokonvertering

3.3 Grundlæggende cyklusser:“ 32-Z” , “ 32-P” .

Øve sig

4.1 Implementering af det vigtigste kryptokonverteringstrin
4.2 Forøgelse af algoritmens hastighed
5.
6. Liste over brugt litteratur
7. Anerkendelser

Introduktion.

Dette dokument er mit forsøg på at beskrive en metode til simpelthen at erstatte GOST 28147-89-krypteringsalgoritmen med det enkleste, men ikke desto mindre teknisk kompetente sprog. Læseren vil fortælle sin mening om, hvor godt jeg lykkedes efter at have læst de første seks punkter.

For at mit arbejde kan være mere nyttigt, anbefaler jeg, at du bevæbner dig med forfatternes værker, der er angivet på listen over brugt litteratur. En lommeregner anbefales også, så den har en funktion til at beregne operationen XOR, fordi læsning af artiklen antager, at læseren har til hensigt at studere denne krypteringsalgoritme. Selvom det også er velegnet som en referenceguide, skrev jeg denne artikel specifikt som en træningsartikel.

Introduktion til blokcifre.

Før vi begynder at se på algoritmen, er vi nødt til at gøre os bekendt med historien om oprettelsen af denne slags chiffer. Algoritmen tilhører kategorien af blokcifre, i hvis arkitektur information er opdelt i et endeligt antal blokke, den sidste kan naturligvis ikke være komplet. Krypteringsprocessen foregår præcist over hele blokke, som danner chiffergrammet. Den sidste blok, hvis den er ufuldstændig, suppleres med noget (jeg vil tale om nuancerne i dens færdiggørelse nedenfor) og krypteres på samme måde som komplette blokke. Med ciphergram mener jeg resultatet af krypteringsfunktionen, der virker på en vis mængde data, som brugeren har indsendt til kryptering. Med andre ord er et chiffergram det endelige resultat af kryptering.

Historien om udviklingen af blokcifre er forbundet med de tidlige 70'ere, hvor IBM-virksomheden, der indså behovet for at beskytte information ved overførsel af data over computerkommunikationskanaler, begyndte at implementere sit eget videnskabelige forskningsprogram dedikeret til beskyttelse af information i elektronisk netværk, herunder kryptografi.

En gruppe forskere og udviklere fra IBM, som begyndte at forske i krypteringssystemer med et symmetrisk nøgleskema, blev ledet af Dr. Horst Feistel.

2.1 Feistel netværk

Arkitekturen af den nye krypteringsmetode foreslået af Feistel i klassisk litteratur blev kaldt "Feistel Architecture", men i øjeblikket bruges i russisk og udenlandsk litteratur et mere etableret udtryk - "Feistel netværk" eller Feistel's NetWork. Efterfølgende blev "Lucifer"-chifferet bygget ved hjælp af denne arkitektur - som senere blev offentliggjort og forårsagede en ny bølge af interesse for kryptografi generelt.

Idéen med Feistel-netværksarkitekturen er som følger: input-informationsstrømmen er opdelt i blokke med n bit i størrelse, hvor n er et lige tal. Hver blok er opdelt i to dele - L og R, derefter føres disse dele ind i en iterativ blokchiffer, hvor resultatet af det j-te trin bestemmes af resultatet af det foregående trin j-1! Dette kan illustreres med et eksempel:

Ris. 1

Hvor funktion A er hovedhandlingen af en blokcifre. Det kan være en simpel handling, såsom XOR-operationen, eller den kan have en mere kompleks form og være en sekvens af en række simple handlinger - modulo-addition, venstreforskydning, elementudskiftning osv., tilsammen danner disse simple handlinger såkaldt hovedtrin i kryptokonvertering.

Det skal bemærkes, at nøgleelementerne i funktionens drift er leveringen af nøgleelementer og XOR-operationen, og hvor godt disse operationer er gennemtænkt indikerer den kryptografiske styrke af chifferen som helhed.

For at ideen om Feistel-netværk skal være helt klar, lad os overveje det enkleste tilfælde afbildet i ris. 1, hvor i funktion A – vil operationerne “mod 2” (“xor”) fremkomme, men dette enkleste I en mere alvorlig situation, for eksempel ved at skjule information af national betydning, kan funktion A være mere kompleks (så vidt jeg har set, kan funktion A faktisk være meget kompleks):

Indledende data:

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

Hent krypteringskoden

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

L=0101b, R=1010b

Lad os forklare vores handlinger:

Denne operation er addition mod 2 4. I praksis kommer en sådan operation ned til simpel addition, hvor vi skal tilføje to tal og ignorere indførslen til det 5. ciffer. Da hvis vi sætter eksponenter over cifrene i den binære repræsentation af et tal, vil der være en eksponent fire over det femte ciffer, lad os tage et kig på figuren nedenfor, som viser handlingerne af vores operation:

Ris. 2

Her pegede jeg med en pil på eksponenterne, som du kan se, skulle resultatet have været 10100, men da mod 2 4 operationen ignorerer carry, får vi 0100.

Denne operation kaldes mod 2 i litteraturen og implementeres i assemblersprog af kommandoen XOR. Men dets mere korrekte navn er mod 2 1. Uden denne unikke operation er det næppe muligt at bygge en hurtig, let implementeret krypteringsalgoritme og samtidig få den til at være ret krypto-resistent. Det unikke ved denne operation ligger i, at det er det modsatte af sig selv! For eksempel, hvis tallet A er XORED med tallet B, er resultatet B. I fremtiden er det nok at XOR tallene B og C med hinanden for at få den tidligere værdi af A!

I denne operation fik vi 1010 med tallene 1110 og 0100, for at få 1110 tilbage, er det nok at XOR tallene 0100 og 1010 med hinanden! Du kan læse mere om denne operation i artiklen vedhæftet hjemmesiden. www.wasm.ru, « Grundlæggende guide tilCRC_error detektionsalgoritmer» forfatteren, der Ross N. Williams. I dette arbejde er der en pointe - " 5. Binær aritmetik uden bærer" Det er i denne artikel, at operationen er beskrevet. xor! Jeg udbryder, fordi denne operation i denne artikel er så beskrevet, at læseren ikke kun forstår, hvordan denne operation fungerer, han selv begynder den se, hør og føl!

Denne handling er nødvendig, så de originale værdier kan opnås ved dekryptering af chiffergrammet.

2.2 Blokcifre GOST 28147-89

GOST 28147 – 89-krypteringsalgoritmen tilhører kategorien af blokcifre, der arbejder i henhold til arkitekturen af balancerede Feistel-netværk, hvor to dele af den valgte informationsblok er af samme størrelse. Algoritmen blev udviklet i tarmene i den ottende afdeling af KGB, nu omdannet til FAPSI, og blev etableret som krypteringsstandarden for Den Russiske Føderation tilbage i 1989 under USSR.

For at denne algoritmemetode skal fungere, er det nødvendigt at opdele informationen i blokke med en størrelse på 64 bit. Generer eller indtast følgende nøgleoplysninger i krypteringssystemet: nøgle og substitutionstabel. Valget af nøgle og erstatningstabel ved kryptering bør tages meget alvorligt, pga Dette er grundlaget for sikkerheden af dine oplysninger. For information om, hvilke krav der stilles til nøglen og udskiftningstabellen, se afsnittet "Krav til nøgleoplysninger".

Når vi overvejer metoden, vil vi ikke fokusere på dette, fordi denne artikel, som jeg sagde ovenfor, blev skrevet med det formål at lære læseren, hvordan man krypterer data ved hjælp af metoden til blot at erstatte en given krypteringsalgoritme, men vi vil helt sikkert komme ind på dette problem i slutningen af artiklen.

Teoretisk minimum.

3.1 Nøgleoplysninger

Som jeg sagde ovenfor, deltager følgende aktivt i datakryptering:

3.1.1. En nøgle er en sekvens af otte elementer, hver 32 bit store. Yderligere vil vi betegne det med symbolet K, og de elementer, som det består af, er k1, k2, k3, k4, k5, k6, k7, k8.

3.1.2 Udskiftningstabel – en matrix med otte rækker og seksten kolonner, i det følgende benævnt Hij. Hvert element i skæringspunktet mellem række i og kolonne j optager 4 bit.

Hovedhandlingen i krypteringsprocessen er hovedtrinnet i kryptokonvertering. Dette er intet andet end handlingen med at kryptere data ved hjælp af en bestemt algoritme, kun udviklerne introducerede et meget besværligt navn :).

Før kryptering begynder, er blokken opdelt i to dele L og R, 32 bit hver. De vælger et nøgleelement og fører først derefter disse to dele af blokken, nøgleelementet og erstatningstabellen ind i hovedtrinsfunktionen Resultatet af hovedtrinnet er en iteration af den grundlæggende cyklus, som vil blive diskuteret i den næste afsnit. Hovedtrinet består af følgende:

Tilføjelsesdelen af blokken R summeres med nøgleelementet K mod 2 32. Jeg beskrev en lignende operation ovenfor, her er det samme, kun eksponenten er ikke "4", men "32" - resultatet af denne operation vil blive yderligere betegnet af Smod.
Vi opdeler det tidligere opnåede resultat Smod i fire-bit elementer s7, s6, s5, s4, s3, s2, s1, s0 og føder det til erstatningsfunktionen. Udskiftningen foregår på følgende måde: vælg elementet Smod - s i , start fra begyndelsen med det laveste element, og erstat det med værdien fra erstatningstabellen for i - rækken og kolonnen angivet med værdien af elementet s i . Vi går til s i +1 element og fortsætter på samme måde og fortsætter, indtil vi erstatter værdien af det sidste element Smod - resultatet af denne operation vil blive betegnet som, Ssimple.
I denne operation forskydes værdien af Ssimple cyklisk til venstre med 11 bit, og vi opnår Srol.
Vi vælger den anden del af blok L og tilføjer mod 2 med Srol, som et resultat har vi Sxor.
På dette stadium bliver L-delen af blokken lig med værdien af R-delen, og R-delen initialiseres igen af resultatet af Sxor, og dette er slutningen af hovedtrinsfunktionen!

3.3 Grundlæggende cyklusser: "32-Z", "32-R".

For at kryptere information skal den opdeles i blokke på 64 bit store; naturligvis kan den sidste blok være mindre end 64 bit. Denne kendsgerning er akilleshælen for denne "simpele udskiftningsmetode". Da dets tilføjelse til 64 bit er en meget vigtig opgave i at øge den kryptografiske styrke af chiffergrammet, er dette følsomme sted, hvis det er til stede i rækken af information, og det ikke er (for eksempel en fil på 512 bytes i størrelse !), bør behandles med stort ansvar!

Når du har opdelt informationen i blokke, bør du opdele nøglen i elementer:

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

Selve kryptering består af at bruge såkaldte basiscyklusser. Som igen inkluderer det n'te antal grundlæggende kryptokonverteringstrin.

Grundcyklusser er, hvordan skal jeg sige det, mærket: n – m. Hvor n er antallet af primære kryptokonverteringstrin i basiscyklussen, og m er "typen" af basiscyklussen, dvs. Hvad taler vi om, "Z"-kryptering eller "R"-kryptering af data.

Den grundlæggende krypteringscyklus 32-3 består af 32 hovedkryptotransformationstrin. Funktionen, der implementerer trinhandlingerne, leveres med blok N og nøgleelement K, hvor det første trin sker med k1, det andet over det opnåede resultat med elementet k2 osv. efter følgende skema:

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

Dekrypteringsprocessen for 32-P foregår på lignende måde, men nøgleelementerne leveres i omvendt rækkefø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 sig.

Efter at vi havde stiftet bekendtskab med teorien om, hvordan man krypterer information, var det tid til at se, hvordan kryptering sker i praksis.

Indledende data:

Lad os tage informationsblokken N = 0102030405060708h, her er dele L og R ens:

L = 01020304h, R =05060708h, tag nøglen:

K = ' som 28 zw37 q839 7342ui23 8e2t wqm2 ewp1' (disse er ASCII-koder, for at se den hexadecimale repræsentation kan du åbne denne fil i visningstilstand i Total Commander ved at trykke på " F3"og så nøglen" 3 "). I denne nøgle vil elementværdierne være:

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

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

Lad os også tage følgende erstatningstabel:

Ris. 3

Her er rækkerne nummereret fra 0 til 7, kolonner fra 0 til F.

Advarsel: Al information, inklusive nøglen med erstatningstabellen, tages som et eksempel for at overveje algoritmen!

Ved at bruge "Input Data" er det nødvendigt at opnå resultatet af hovedtrinnet i kryptokonvertering.

Vi vælger delen R = 05060708h og nøgleelementet k1 = 'as28', i hexadecimal form vil nøgleelementet se således ud: 61733238h. Nu udfører vi summeringsoperationen mod 2 32:

Ris. 4

Som du kan se på figuren, havde vi ikke en overførsel til 33 bit markeret med rødt og med eksponenten " 32 " Og hvis vi havde andre værdier for R og nøgleelementet, kunne dette meget vel ske, og så ville vi ignorere det, og i fremtiden ville vi kun bruge de bits, der er markeret med gult.

Jeg udfører denne operation ved hjælp af assembler-kommandoen tilføje:

; eax = R, ebx = 'as28'

Resultatet af denne operation er Smod = 66793940h

Nu er dette den mest vanskelige operation, men hvis du ser nærmere efter, er den ikke længere så skræmmende, som den umiddelbart ser ud. Lad os forestille os Smod i følgende form:

FIGUR IKKE GEMMT

Ris. 5

Jeg forsøgte at visualisere Smod-elementerne i figuren, men jeg vil alligevel forklare:

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

Nu, startende fra det laveste element s0, foretager vi udskiftningen. Husk pointen " 3.2 Grundlæggende trin i kryptokonvertering» i – række, s i – kolonne, se efter værdien i nulrækken og nulkolonnen:

Fig.6

Så den aktuelle værdi af Smod er ikke 6679394 0 h, a 6679394 5 h.

Lad os begynde at erstatte s1, dvs. fire. Brug af første række og fjerde kolonne (s1= 4!). Lad os se på billedet:

Ris. 7

Nu er værdien Smod, ikke 667939 4 5h, 667939 2 5 timer. Jeg antager, at udskiftningsalgoritmen nu er klar for læseren, og jeg kan sige, at efter dette vil det endelige resultat af Ssimple have følgende værdi - 11e10325h.

Jeg vil tale om, hvordan dette lettest kan implementeres i form af assembler-kommandoer senere i næste afsnit, efter jeg har talt om den udvidede tabel.

Vi skal flytte den resulterende Ssimple-værdi 11 bit til venstre.

Ris. 8

Som du kan se, er denne handling ret enkel og implementeres med en assemblersprogkommando - rolle og resultatet af denne operation Srol er 0819288Fh.

Nu er der kun tilbage at XOR delen L af vores informationsblok med værdien Srol. Jeg tager en lommeregner fra w2k sp4 og får Sxor = 091b2b8bh.
Denne handling er endelig, og vi tildeler simpelthen R, værdien af del L, og initialiserer del L med værdien af Sxor.

Endeligt resultat:

L = 091b2b8bh, R = 01020304h

4.2 Forøg algoritmens hastighed

Lad os nu tale om at optimere algoritmen for hastighed. Når man implementerer ethvert projekt, skal man tage højde for, at et program, der arbejder med registre oftere end med hukommelse, virker hurtigst, og her er denne bedømmelse også meget vigtig, fordi over en blok af information er der så mange som 32 krypteringshandlinger!

Da jeg implementerede krypteringsalgoritmen i mit program, gjorde jeg følgende:

Jeg valgte en del af blokken L i eax-registret og R i edx-registret.
esi-registret blev initialiseret med adressen på den udvidede nøgle, mere om det nedenfor.
ebx-registret blev tildelt værdien af adressen på det udvidede erstatningsbord, mere om det nedenfor
Overførte oplysningerne i punkt 1,2, 3 til funktionen af den grundlæggende cyklus 32 - Z eller 32 - R, afhængigt af situationen.

Hvis du ser på forsyningsdiagrammet over nøgleelementerne i afsnit " Grundlæggende cyklusser: "32-Z", "32-R"", så kan vores nøgle til grundcyklus 32 - Z repræsenteres som følger:

K 32-Z =

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

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

De der. fra begyndelsen er der k1, k2, k3, k4, k5, k6, k7, k8 - ‘ as28', 'zw37', 'q839', '7342', 'ui23', '8e2t', 'wqm2', 'ewp1' Denne sekvens gentages tre gange. Så går elementerne i omvendt rækkefølge, dvs.: k8,k7,k6,k5,k4,k3,k2,k1 - 'ewp1', 'wqm2', '8e2t', 'ui23', '7342', 'q839', 'zw37', 'as28'.

Jeg forudarrangerede elementerne i arrayet i den rækkefølge, de skulle føres ind i 32 - Z. Således øgede jeg den nødvendige hukommelse pr. tur, men reddede mig selv fra nogle tænkeprocesser, som jeg ikke havde brug for, og øgede hastigheden af algoritme, for ved at reducere hukommelsesadgangstiden! Her beskrev jeg kun nøglen for 32 - Z, for cyklus 32 - P gjorde jeg det samme, men ved at bruge et andet skema til levering af elementer, som jeg også beskrev i afsnittet " Grundlæggende cyklusser: "32-З", "32-Р"».

Det er tid til at beskrive implementeringen af erstatningsfunktionen, som jeg lovede ovenfor. Jeg kunne ikke beskrive det tidligere, fordi... dette kræver introduktion af et nyt koncept - en udvidet substitutionstabel. Jeg kan ikke forklare dig, hvad det er. I stedet vil jeg vise dig det, og du kan selv formulere, hvad det er - en udvidet substitutionstabel?

Så for at forstå, hvad et udvidet udskiftningsbord er, har vi brug for et udskiftningsbord; for eksempel vil jeg tage den vist i fig. 3.

For eksempel skulle vi erstatte nummeret 66793940h. Jeg vil præsentere det i følgende form:

FIGUR IKKE GEMMT

Ris. 9

Hvis vi nu tager elementerne s1, s0, dvs. lav byte, så vil resultatet af erstatningsfunktionen være lig med 25h! Efter at have læst artiklen af Andrei Vinokurov, som jeg citerede i afsnit " Liste over brugt litteratur", vil du faktisk opdage, at hvis du tager to strenge, kan du få et array, så du hurtigt kan finde erstatningselementer ved hjælp af en assembler-kommando xlat. De siger, at der er en anden hurtigere måde, men Andrei Vinokurov brugte omkring fire år på at undersøge hurtige algoritmer til implementering af GOST! Jeg tror, der er ingen grund til at genopfinde hjulet, når det allerede eksisterer.

Så om arrayet:

Lad os tage de første to linjer, nul og første, og skabe en matrix på 256 bytes. Nu observerer vi en ejendommelighed: hvis vi skal konvertere 00h, så vil resultatet være 75h (vi stoler på fig. 3) - vi sætter denne værdi i arrayet ved offset 00h. Vi tager værdien 01h, resultatet af erstatningsfunktionen 79h, sætter den i arrayet ved offset 01 og så videre indtil 0FFh, hvilket vil give os 0FCh, som vi sætter i arrayet ved offset 0FFh. Så vi fik en udvidet tabel med erstatninger for den første gruppe af rækker: første og nul. Men der er stadig tre grupper: anden side 2, side 3, tredje side 4, side 5, fjerde side 6, side 7. Vi behandler disse tre grupper på samme måde som med den første. Resultatet er en udvidet udskiftningstabel!

Nu kan du implementere en algoritme, der udfører udskiftningen. For at gøre dette tager vi kildekoderne, som Andrey Vinokurov postede på sin side, se " Bibliografi».

lea ebx,extended_table_simple

mov eax,[indsæt nummeret, der skal erstattes]

tilføj ebx,100h ;hop til næste to noder

sub ebx,300h ; så ebx i fremtiden peger på bordet

Nu er der en funktion mere: med de tidligere handlinger erstattede vi ikke kun, men flyttede også tallet 8 bits til venstre! Alt vi skal gøre er at flytte tallet yderligere 3 bit til venstre:

og vi får resultatet af operationen rolle eax,11!

Jeg kan ikke tilføje noget mere vedrørende optimering, det eneste jeg kan understrege er, hvad jeg sagde ovenfor - brug registre oftere end adgang til hukommelse. Jeg tror, at disse ord kun er for begyndere; erfarne mennesker forstår dette udmærket uden mine ord :).

Krav til nøgleoplysninger.

Som det fremgår af artiklen af Andrey Vinokurov, er nøglen valgt i henhold til to kriterier:

— et kriterium for den ligesandsynlige fordeling af bit mellem værdierne 1 og 0. Sædvanligvis bruges Pearson-kriteriet ("chi-kvadrat") som et kriterium for den ligesandsynlige fordeling af bits.

Dette betyder, at nøglen i princippet kan være et hvilket som helst tal. Det vil sige, når den næste bit af nøglen dannes, er sandsynligheden for dens initialisering til en eller nul 50/50!

Bemærk venligst, at nøglen består af otte elementer, hver på 32 bit, så i alt er der 32 * 8 = 256 bit i nøglen og antallet af mulige nøgler er 2.256! Overrasker dette dig ikke? 🙂

- seriekriterium.

Hvis vi ser på vores nøgle, som jeg gav i afsnit " 4.1 Implementering af hovedtrinnet i kryptokonvertering", så vil du bemærke, at følgende notation er sand:

Ris. 10

I én sætning bør værdien af k 1 ikke gentages i k 2 eller i noget andet nøgleelement.

Det vil sige, at nøglen, som vi valgte at betragte som en krypteringsalgoritme, opfylder fuldt ud de to ovenstående kriterier.

Nu om at vælge et erstatningsbord:

Lad os nu tale om, hvordan man vælger den rigtige substitutionstabel. Hovedkravet for at vælge erstatningstabeller er fænomenet "ikke-gentagelse" af elementer, som hver er 4 bit store. Som du allerede har set ovenfor, består hver række i erstatningstabellen af værdierne 0h, 1h, 2h, 3h, ..., 0fh. Så hovedkravet siger, at hver linje indeholder værdierne 0h, 1h, 2h, ..., 0fh og hver sådan værdi i én kopi. For eksempel rækkefølgen:

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

Det opfylder fuldt ud dette krav, men alligevel! Det anbefales ikke at vælge en sådan sekvens som en streng. For hvis du fodrer en værdi til input af en funktion, der er afhængig af en sådan streng, så får du den samme værdi som output! Tror du mig ikke? Tag derefter tallet 332DA43Fh og otte sådanne rækker som en tabel over erstatninger. Udfør udskiftningsoperationen, og jeg kan forsikre dig, at outputtet, du får, er 332DA43Fh! Det vil sige det samme som du har indsendt som input til operationen! Men dette er ikke et tegn på god manerer ved kryptering, og var det? 🙂

Dette var et krav, det næste kriterium siger, at - hver bit af outputblokken skal være statistisk uafhængig af hver bit af inputblokken!

Hvordan ser det nemmere ud? Og her er, hvordan vi for eksempel valgte elementet s0 = 0Fh, 01111b fra ovenstående tal. Sandsynligheden for at vi nu vil erstatte den første bit med en eller nul er 0,5! Sandsynligheden for at erstatte den anden, tredje og fjerde bit, hver bit, betragter vi separat, med enere eller nuller, er også 0,5. Når du vælger s1 = 0Eh, er sandsynligheden for, at vi erstatter nulbit, og dette er "0", med nul eller en for lig med – 0,5! Ifølge dette kriterium er der således ikke noget mønster mellem udskiftningen af nul bits af elementerne s0, s1! Ja, du kan erstatte dem, men du kan også erstatte nuller. 🙂

For at evaluere tabellen i henhold til dette kriterium kan du bygge en tabel med korrelationskoefficienter beregnet ved hjælp af formlen:

— hvis p = 1, så er værdien af bit j ved udgangen lig med værdien af bit i ved input for enhver kombination af bit ved input;

— hvis p = -1, så er værdien af bit j ved udgangen altid den omvendte af inputbit i;

— hvis p = 0, så tager udgangsbitten j med samme sandsynlighed værdierne 0 og 1 for enhver fast værdi af inputbit i.

Lad os tage et enkelt linje eksempel:

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

Lad os opdele det i "komponenter":

Lad os beregne en koefficient ved hjælp af formlen ovenfor. For at gøre det lettere at forstå, hvordan dette gøres, vil jeg forklare mere detaljeret:

— vi tager den 0. bit af det 0. tal (0) ved input og den 0. bit af det 0. tal ved udgangen (1) og udfører operationen 0 XOR 1 = 1.

— vi tager den 0. bit af det 1. tal (1) ved indgangen og den 0. bit af det 1. tal ved udgangen (1) og udfører operationen 1 XOR 1 = 0.

— vi tager den 0. bit af det 2. tal (0) ved indgangen og den 0. bit af det andet tal ved udgangen (0) og udfører operationen 0 XOR 0 = 0.

— vi tager den 0. bit af det 3. tal (1) ved input og den 0. bit af det 3. tal ved udgangen (1) og udfører operationen 1 XOR 1 = 0.

Efter at have udført sekventielle XOR-operationer i denne sekvens, tæller vi antallet af alle ikke-nul-værdier, vi får værdien 6. Derfor P 00 = 1-(6/2 4-1) = 0,25. Så det viste sig, at værdien af bit 0 ved udgangen er lig med værdien af bit 0 ved input i 4 tilfælde ud af 16;

Finale odds tabel:

Tabellen med koefficienter vil være som følger (hvem der ikke er for doven kan genberegne)

	Indgang
Afslut		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

Nå, i denne tabel er tingene endnu værre - bit 1 og 2 i gruppen forbliver uændrede! Kryptanalytikeren har plads til at vende om 🙂 Under hensyntagen til alle disse krav blev der ved simpel brute-force-søgning fundet permutationstabeller svarende til den specificerede teori (til dato - 1276 kombinationer). Her er nogle af 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 brugt litteratur.

Artikel af Andrey Vinokurov:

GOST 28147-89 krypteringsalgoritme, dens brug og implementering

til computere på Intel x86-platformen.

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

Her er kildekoderne til implementering af krypteringsalgoritmen.

Artikel af Horst Feistel:

Kryptografi og computersikkerhed.

(kan findes på samme adresse som forrige artikel)

Ross N. Williams:

En grundlæggende vejledning til CRC-fejldetektionsalgoritmer

Udgivet på hjemmesiden www.wasm.ru.

Anerkendelser

Jeg vil gerne udtrykke min taknemmelighed til alle besøgende på forummet www.wasm.ru. Men jeg vil især gerne takke ChS, som i dag er kendt som SteelRat, han hjalp mig med at forstå ting, som jeg nok aldrig ville have forstået, samt hjælp til at skrive afsnittet: “ Krav til nøgleoplysninger", er hoveddelen af dette afsnit skrevet af ham. Jeg er også den ansatte i KSTU dybt taknemmelig. A.N. Tupolev Anikin Igor Vyacheslavovich og det ville være en synd ikke at nævne Chris Kaspersky for hvad han er og Volodya / wasm.ru for hans instruktioner. Åh, og jeg får det fra ham :). Jeg vil også nævne Sega-Zero / Callipso for at bringe noget matematisk jungle til mit sind.

Det er nok alt, jeg gerne vil fortælle dig.

Jeg ville være taknemmelig for kritik eller spørgsmål relateret til denne artikel eller bare råd. Mine kontaktoplysninger: [e-mail beskyttet], ICQ – 337310594.

Med venlig hilsen, Evil's Interrupt.

P.S.: Jeg forsøgte ikke at overgå nogen med denne artikel. Det er skrevet med den hensigt at gøre det lettere at studere GOST, og hvis du har vanskeligheder, betyder det ikke, at jeg er skyld i dette. Vær fornuftig og vær tålmodig, alt det bedste til dig!

Kort beskrivelse af chifferen

GOST 28147-89 er en sovjetisk og russisk symmetrisk krypteringsstandard introduceret i 1990, også en CIS-standard. Fulde navn - "GOST 28147-89 Informationsbehandlingssystemer. Kryptografisk beskyttelse. Kryptografisk konverteringsalgoritme". Blok chifferalgoritme. Når du bruger gamma-krypteringsmetoden, kan den udføre funktionerne i en strømkrypteringsalgoritme.

GOST 28147-89 er en blokchiffer med en 256-bit nøgle og 32 konverteringscyklusser, der fungerer på 64-bit blokke. Grundlaget for chifferalgoritmen er Feistel Network. Den grundlæggende krypteringstilstand i henhold til GOST 28147-89 er den simple udskiftningstilstand (mere kompleks gamma, gamma med feedback og simulerede indsættelsestilstande er også defineret).

Hvordan algoritmen fungerer

Algoritmen er ikke fundamentalt forskellig fra DES. Den indeholder også krypteringscyklusser (32 af dem) i henhold til Feistel-skemaet (fig. 2.9.).

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

For at generere undernøgler er den originale 256-bit nøgle opdelt i otte 32-bit blokke: k 1 ...k 8 . Tasterne k 9 ...k 24 er en cyklisk gentagelse af tasterne k 1 ...k 8 (nummereret fra mindst signifikante til højeste bit). Tasterne k 25 …k 32 er tasterne k 1 …k 8 i omvendt rækkefølge.

Efter at have gennemført alle 32 runder af algoritmen limes blokke A 33 og B 33 sammen (bemærk at den mest signifikante bit bliver A 33, og den mindst signifikante bit - B 33) - resultatet er resultatet af algoritmen.

Fungere f(EN jeg ,K jeg) beregnes som følger: A i og K i tilføjes modulo 2 32 , derefter opdeles resultatet i otte 4-bit undersekvenser, som hver er input til sin egen substitutionstabel node(i stigende rækkefølge efter bitprioritet), kaldet nedenfor S-blok. Det samlede antal GOST S-blokke er otte, dvs. det samme antal som undersekvenser. Hver S-blok er en permutation af tal fra 0 til 15. Den første 4-bit undersekvens går til indgangen af den første S-boks, den anden - til indgangen af den anden osv. Udgangene fra alle otte S-bokse kombineres til et 32-bit ord, så forskydes hele ordet cyklisk til venstre (mod de mest signifikante bits) med 11 bit. Alle otte S-bokse kan være forskellige. Faktisk kan de være yderligere nøglemateriale, men oftere er de en skemaparameter, der er fælles for en bestemt gruppe af brugere. Standardens tekst angiver, at leveringen af påfyldningserstatningsenheder (S-blokke) udføres på den foreskrevne måde, dvs. algoritme udvikler. Fællesskabet af russiske CIPF-udviklere er blevet enige om de erstatningsknuder, der bruges på internettet.

Dekryptering udføres på samme måde som kryptering, men rækkefølgen af undernøglerne k i er inverteret.

Driftstilstande for GOST 28147-89-algoritmen

GOST 28147-89-algoritmen har fire driftstilstande.

1. Modenem udskiftning accepterer som inputdata, hvis størrelse er et multiplum af 64 bit. Resultatet af kryptering er inputteksten, konverteret i blokke på 64 bit i tilfælde af kryptering med "32-Z" cyklus, og i tilfælde af dekryptering med "32-R" cyklus.

2. Modespil accepterer data af enhver størrelse som input, såvel som en ekstra 64-bit parameter - synkronisere besked. Under drift konverteres synkroniseringsmeddelelsen i "32-Z" cyklussen, resultatet er opdelt i to dele. Den første del er tilføjet modulo 2 32 med en konstant værdi på 1010101 16. Hvis den anden del er lig med 2 32 -1, ændres dens værdi ikke, ellers tilføjes den modulo 2 32 -1 med en konstant værdi på 1010104 16. Værdien opnået ved at kombinere begge transformerede dele, kaldet chiffergamma, går ind i "32-3" cyklussen, dens resultat tilføjes bit for bit modulo 2 med 64-bit blok af inputdata. Hvis sidstnævnte er mindre end 64 bit, så kasseres de ekstra bits af den resulterende værdi. Den resulterende værdi sendes til outputtet. Hvis der stadig er indgående data, gentages handlingen: blokken, der består af 32-bit dele, konverteres i dele, og så videre.

3. Modespil med feedback accepterer også data af enhver størrelse og en synkroniseringsmeddelelse som input. Blokken af inputdata tilføjes bit for bit modulo 2 med resultatet af transformationen i "32-3" cyklussen af synkroniseringsmeddelelsen. Den resulterende værdi sendes til outputtet. Værdien af synkroniseringsmeddelelsen erstattes i tilfælde af kryptering af outputblokken, og i tilfælde af dekryptering - af inputblokken, det vil sige den krypterede. Hvis den sidste blok af indgående data er mindre end 64 bit, så kasseres de ekstra bits af gamma (output af "32-3" cyklus). Hvis der stadig er indgående data, gentages handlingen: fra resultatet af kryptering af den erstattede værdi dannes en chiffergamma osv.

4. Produktionstilstandimitationsindlæg tager som inputdata, der er mindst to hele 64-bit blokke i størrelse og returnerer en 64-bit blok af data kaldet en simuleret insert. Den midlertidige 64-bit værdi sættes til 0, og så længe der er inputdata, tilføjes den bit for bit modulo 2 med resultatet af "16-3" cyklussen, hvis input er en blok af input data. Efter afslutningen af inputdata returneres den midlertidige værdi som resultat.

Krypteringskrypteringsanalyse

GOST 28147-89 chifferen bruger en 256-bit nøgle, og volumen af nøglerummet er 2.256. På ingen af de nuværende almindelige computere kan en nøgle findes på mindre end mange hundrede år. Den russiske standard GOST 28147-89 er designet med en stor margin og er mange størrelsesordener stærkere end den amerikanske DES-standard med dens faktiske nøglestørrelse på 56 bit og et nøglerumvolumen på kun 2 56 .

Der er også angreb på hele GOST 28147-89 uden nogen ændringer. Et af de første offentlige værker til at analysere algoritmen udnytter svagheder i nøgleudvidelsesproceduren for en række velkendte krypteringsalgoritmer. Især hele GOST 28147-89-algoritmen kan brydes ved hjælp af differentiel kryptoanalyse på relaterede nøgler, men kun hvis der bruges svage erstatningstabeller. 24-runders versionen af algoritmen (hvor de første 8 runder mangler) åbnes på lignende måde med eventuelle erstatningstabeller, dog gør stærke erstatningstabeller et sådant angreb fuldstændig upraktisk.

De indenlandske videnskabsmænd A.G. Rostovtsev og E.B. Makhovenko foreslog i 2001 en fundamentalt ny metode til kryptoanalyse ved at danne en objektiv funktion ud fra en kendt klartekst, den tilsvarende chiffertekst og den ønskede nøgleværdi og finde dens ekstremum svarende til nøglens sande værdi. De fandt også en stor klasse af svage nøgler til GOST 28147-89 algoritmen, som gør det muligt at åbne algoritmen ved hjælp af kun 4 udvalgte klartekster og de tilsvarende chiffertekster med en forholdsvis lav kompleksitet.

I 2004 foreslog en gruppe specialister fra Korea et angreb, der ved hjælp af differentiel kryptoanalyse på relaterede nøgler kan opnå en 12-bit hemmelig nøgle med en sandsynlighed på 91,7 %. Angrebet kræver 2 35 udvalgte klartekster og 2 36 krypteringsoperationer. Som du kan se, er dette angreb praktisk talt ubrugeligt til faktisk at bryde algoritmen.

GOST 28147-89 krypteringsalgoritme, dens brug og softwareimplementering til computere på Intel x86-platformen.

Andrey Vinokurov

Beskrivelse af algoritmen.

Vilkår og betegnelser.

En beskrivelse af den russiske føderations krypteringsstandard er indeholdt i et meget interessant dokument med titlen "Kryptografisk konverteringsalgoritme GOST 28147-89". Det faktum, at der i dets navn i stedet for udtrykket "kryptering" optræder et mere generelt begreb " kryptografisk konvertering ”, er slet ikke tilfældigt. Ud over flere tæt beslægtede krypteringsprocedurer beskriver dokumentet en algoritme til generering imitationsindlæg . Sidstnævnte er intet andet end en kryptografisk kontrolkombination, det vil sige en kode genereret ud fra de originale data ved hjælp af en hemmelig nøgle med det formål at efterligningsbeskyttelse , eller beskyttelse af data mod uautoriserede ændringer.

Ved forskellige trin af GOST-algoritmer fortolkes og bruges de data, de opererer på, på forskellige måder. I nogle tilfælde behandles dataelementer som arrays af uafhængige bits, i andre tilfælde som et heltal uden fortegn, i andre som et struktureret komplekst element bestående af flere enklere elementer. For at undgå forvirring er det derfor vigtigt at blive enige om den anvendte notation.

Dataelementer i denne artikel er angivet med store bogstaver med kursiv stil (f.eks. x). Via | x| angiver størrelsen af dataelementet x i stykker. Altså, hvis vi fortolker dataelementet x Som et ikke-negativt heltal kan vi skrive følgende ulighed:.

Hvis et dataelement består af flere mindre elementer, angives dette som følger: x=(x 0 ,x 1 ,…,Xn –1)=x 0 ||x 1 ||…||Xn-1. Processen med at kombinere flere dataelementer til ét kaldes sammenkædning data og er angivet med symbolet "||". Naturligvis skal følgende relation være opfyldt for størrelsen af dataelementer: | x|=|x 0 |+|x 1 |+…+|Xn-1 |. Når komplekse dataelementer og sammenkædningsoperationen specificeres, er de konstituerende dataelementer anført i stigende rækkefølge. Med andre ord, hvis vi fortolker det sammensatte element og alle dets dataelementer som heltal uden fortegn, så kan vi skrive følgende lighed:

I algoritmen kan et dataelement fortolkes som et array af individuelle bits, i hvilket tilfælde bitsene er angivet med samme bogstav som arrayet, men i en version med små bogstaver, 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 .

Således, hvis du bemærkede, er den såkaldte GOST blevet vedtaget. "little-endian" nummerering af cifre, dvs. Inden for multi-bit dataord er individuelle bits og grupper af bit med lavere nummer mindre signifikante. Dette er direkte angivet i paragraf 1.3 i standarden: "Når binære vektorer tilføjes og skiftes cyklisk, anses de mest signifikante bit for at være bits af drev med store tal." Yderligere kræver klausuler i standarden 1.4, 2.1.1 og andre, at man begynder at fylde lagerregistrene på den virtuelle krypteringsenhed med data fra de laveste, dvs. mindre væsentlige kategorier. Nøjagtig den samme nummereringsrækkefølge er vedtaget i Intel x86-mikroprocessorarkitekturen, hvorfor der ikke kræves yderligere permutationer af bits inde i dataord, når du implementerer en chiffer i software på denne arkitektur.

Hvis en operation, der har en logisk betydning, udføres på dataelementer, så antages det, at denne operation udføres på de tilsvarende bits af elementerne. 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 “ ” angiver en vilkårlig binær logisk operation; som regel betyder det operation eksklusiv eller , som også er operationen af summeringsmodul 2:

Logikken i at konstruere en chiffer og strukturen af GOST-nøgleinformation.

Hvis du omhyggeligt studerer den originale GOST 28147-89, vil du bemærke, at den indeholder en beskrivelse af algoritmer på flere niveauer. Helt i toppen er der praktiske algoritmer designet til at kryptere dataarrays og udvikle imitative inserts til dem. Alle er baseret på tre lav-niveau algoritmer, kaldet i GOST teksten cyklusser . Disse grundlæggende algoritmer omtales i denne artikel som grundlæggende cyklusser at skelne dem fra alle andre cyklusser. De har følgende navne og symboler, sidstnævnte er angivet i parentes, og deres betydning vil blive forklaret senere:

krypteringscyklus (32-З);
dekrypteringscyklus (32-P);
produktionscyklus af imiteret indsats (16-Z).

Til gengæld er hver af de grundlæggende cyklusser en multipel gentagelse af en enkelt procedure, der er påkrævet yderligere i dette arbejde det vigtigste trin i kryptokonvertering .

For at forstå GOST skal du således forstå følgende tre ting:

hvad er der sket grundlæggende trin kryptokonverteringer;
hvordan grundlæggende cyklusser dannes ud fra grundlæggende trin;
fra tre grundlæggende cyklusser alle praktiske GOST-algoritmer er lagt sammen.

Før vi går videre til at studere disse spørgsmål, bør vi tale om de vigtigste oplysninger, der bruges af GOST-algoritmer. I overensstemmelse med Kirchhoffs princip, som er opfyldt af alle moderne cifre kendt af den brede offentlighed, er det dens hemmeligholdelse, der sikrer hemmeligholdelsen af den krypterede meddelelse. I GOST består nøgleinformation af to datastrukturer. Udover det faktiske nøgle , der er nødvendige for alle cifre, indeholder den også substitutionstabel . Nedenfor er de vigtigste karakteristika for nøglestrukturerne i GOST.

Det vigtigste trin i kryptokonvertering.

Det grundlæggende kryptokonverteringstrin er i det væsentlige en erklæring, der specificerer konverteringen af en 64-bit datablok. En yderligere parameter for denne operatør er en 32-bit blok, der bruges som et nøgleelement. Hovedtrinsalgoritmediagrammet er vist i figur 1.

Figur 1. Skema over hovedtrinnet i kryptokonvertering af GOST 28147-89-algoritmen.

Nedenfor er forklaringer af hovedtrinsalgoritmen:

Trin 0

N– en konverteret 64-bit datablok, under udførelsen af trinnet dens mindre ( N 1) og senior ( N 2) delene behandles som separate 32-bit heltal uden fortegn. Således kan vi skrive N=(N 1 ,N 2).
x– 32-bit nøgleelement;

Trin 1

Tilføjelse med nøgle. Den nederste halvdel af den konverterede blok tilføjes modulo 2 32 med nøgleelementet brugt på trinnet, resultatet overføres til næste trin;

Trin 2

Blok udskiftning. 32-bit værdien opnået i det foregående trin fortolkes som en matrix af otte 4-bit kodeblokke: S=(S 0 , S 1 , S 2 , S 3 , S 4 , S 5 , S 6 , S 7), og S 0 indeholder de 4 yngste, og S 7 – 4 mest betydningsfulde bits S.

Dernæst erstattes værdien af hver af de otte blokke med en ny, som vælges fra erstatningstabellen som følger: blokværdi S iændringer til S i-te element i rækkefølge (nummerering fra nul) jeg-denne erstatningsknude (dvs. jeg linje i erstatningstabellen, nummerering også fra bunden). Med andre ord, et element fra erstatningstabellen med et rækkenummer svarende til nummeret på den blok, der udskiftes, og et kolonnenummer svarende til værdien af den blok, der erstattes som et 4-bit ikke-negativt heltal, vælges som erstatning for værdien af blokken. Dette gør størrelsen af erstatningstabellen klar: antallet af rækker i den er lig med antallet af 4-bit elementer i en 32-bit datablok, det vil sige otte, og antallet af kolonner er lig med antallet af forskellige værdier af en 4-bit datablok, som er kendt for at være 2 4, seksten.

Trin 3

Roter 11 bits til venstre. Resultatet af det foregående trin forskydes cyklisk med 11 bit mod de mest signifikante bits og overføres til næste trin. I algoritmediagrammet angiver symbolet funktionen af cyklisk at flytte sit argument 11 bit til venstre, dvs. mod de højere rækker.

Trin 4

Bitvis addition: Værdien opnået i trin 3 tilføjes bitvis modulo 2 med den øverste halvdel af blokken, der konverteres.

Trin 5

Skift langs kæden: Den nederste del af den konverterede blok flyttes til stedet for den ældre, og resultatet af det foregående trin placeres på sin plads.

Trin 6

Den resulterende værdi af den konverterede blok returneres som et resultat af udførelse af algoritmen for det primære kryptokonverteringstrin.

Grundlæggende cyklusser af kryptografiske transformationer.

Som nævnt i begyndelsen af denne artikel tilhører GOST klassen af blokcifre, det vil sige, at informationsbehandlingsenheden i den er en datablok. Derfor er det ret logisk at forvente, at det vil definere algoritmer til kryptografiske transformationer, det vil sige til kryptering, dekryptering og "regnskab" for en kontrolkombination af én datablok. Disse algoritmer kaldes grundlæggende cyklusser GOST, som understreger deres grundlæggende betydning for konstruktionen af denne chiffer.

Grundlæggende løkker er bygget af hovedtrin kryptografisk transformation diskuteret i det foregående afsnit. Under hovedtrinnet bruges kun ét 32-bit nøgleelement, mens GOST-nøglen indeholder otte sådanne elementer. Derfor, for at nøglen kan bruges fuldt ud, skal hver af de grundlæggende sløjfer gentagne gange udføre hovedtrinnet med dets forskellige elementer. Samtidig forekommer det ret naturligt, at alle nøgleelementer i hver grundcyklus skal bruges det samme antal gange; af hensyn til chifferstyrken bør dette tal være mere end én.

Alle de antagelser, der blev gjort ovenfor, blot baseret på sund fornuft, viste sig at være korrekte. Grundlæggende loops består af gentagen udførelse hovedtrin bruger forskellige nøgleelementer og adskiller sig kun fra hinanden i antallet af tringentagelser og rækkefølgen, hvori nøgleelementerne bruges. Nedenfor er denne rækkefølge for forskellige cyklusser.

Krypteringscyklus 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. Krypteringscyklusskema 32-З

Dekrypteringscyklus 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. Skema for 32-P dekrypteringscyklussen

Produktionscyklus af imiteret indsats 16-З:

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. Ordning af produktionscyklussen af imiteret indsats 16-Z.

Hver af cyklerne har sin egen alfanumeriske betegnelse svarende til mønsteret " n-X", hvor det første element i betegnelsen ( n), angiver antallet af gentagelser af hovedtrinnet i cyklussen, og det andet betegnelseselement ( x), bogstav, angiver rækkefølgen af kryptering (“Z”) eller dekryptering (“P”) i brugen af nøgleelementer. Denne ordre kræver yderligere forklaring:

Dekrypteringscyklussen skal være den omvendte af krypteringscyklussen, det vil sige, sekventiel anvendelse af disse to cykler til en vilkårlig blok skal i sidste ende give den oprindelige blok, hvilket afspejles i følgende forhold: C 32-Р ( C 32-З ( T))=T, Hvor T– vilkårlig 64-bit datablok, C X ( T) – resultatet af loop-udførelsen x over datablokken T. For at opfylde denne betingelse for algoritmer, der ligner GOST, er det nødvendigt og tilstrækkeligt, at rækkefølgen af brug af nøgleelementer ved de tilsvarende cyklusser er gensidigt omvendt. Det er let at verificere gyldigheden af den skriftlige betingelse for den pågældende sag ved at sammenligne ovenstående sekvenser for cyklus 32-З og 32-Р. En interessant konsekvens følger af ovenstående: egenskaben ved, at en cyklus er invers i forhold til en anden cyklus, er reciprok, det vil sige, at 32-Z-cyklussen er invers i forhold til 32-P-cyklussen. Med andre ord kan kryptering af en blok af data teoretisk udføres ved hjælp af en dekrypteringscyklus, i hvilket tilfælde dekryptering af en blok af data skal udføres af en krypteringscyklus. Af de to gensidigt omvendte cyklusser kan den ene bruges til kryptering, så skal den anden bruges til at dekryptere data, men GOST 28147-89-standarden tildeler roller til cyklusser og giver ikke brugeren ret til at vælge i denne sag .

Cyklussen til fremstilling af en imitativ indsætning er halvt så lang som krypteringscyklusserne, rækkefølgen af at bruge nøgleelementer i den er den samme som i de første 16 trin af krypteringscyklussen, hvilket er let at verificere ved at overveje ovenstående sekvenser, derfor denne rækkefølge i betegnelsen af cyklussen er kodet med det samme bogstav "Z".

Skemaer af grundlæggende cyklusser er vist i figur 2a-c. Hver af dem tager som et argument og returnerer som et resultat en 64-bit blok af data, angivet i diagrammerne N. Symbol Trin( N,x) angiver udførelsen af det vigtigste krypto-transformationstrin for en datablok N ved hjælp af nøgleelement x. Der er endnu en forskel mellem krypterings- og imitative indsættelsesberegningscyklusser, som ikke er nævnt ovenfor: i slutningen af de grundlæggende krypteringscyklusser ombyttes de høje og lave dele af resultatblokken, dette er nødvendigt for deres gensidige reversibilitet.

Grundlæggende krypteringstilstande.

GOST 28147-89 giver følgende tre datakrypteringstilstande:

enkel udskiftning,
spil,
spil med feedback,

og en ekstra tilstand til generering af imiterede skær.

I enhver af disse tilstande behandles data i blokke på 64 bit, hvor arrayet er opdelt og udsat for kryptografisk transformation, hvorfor GOST refererer til blokchiffere. I to gamma-tilstande er det dog muligt at behandle en ufuldstændig blok af data på mindre end 8 bytes, hvilket er essentielt ved kryptering af dataarrays af vilkårlig størrelse, som måske ikke er et multiplum af 8 bytes.

Før du går videre til en diskussion af specifikke kryptografiske transformationsalgoritmer, er det nødvendigt at præcisere notationen, der bruges i diagrammerne i de følgende afsnit:

TÅh, T w – rækker af henholdsvis åbne og krypterede data;

, – jeg- sekventielle 64-bit blokke af henholdsvis åbne og krypterede data: , , den sidste blok kan være ufuldstændig: ;

n– antallet af 64-bit blokke i dataarrayet;

C X - funktion til at konvertere en 64-bit datablok ved hjælp af den grundlæggende cyklus "X" algoritme.

Nu vil vi beskrive de vigtigste krypteringstilstande:

Nem udskiftning.

Kryptering i denne tilstand består af at anvende cyklus 32-З til blokke af åbne data, dekryptering - cyklus 32-Р til blokke af krypterede data. Dette er den enkleste af tilstandene; 64-bit datablokke behandles uafhængigt af hinanden. Skemaer for krypterings- og dekrypteringsalgoritmer i simpel erstatningstilstand er vist i henholdsvis figur 3a og b; de er trivielle og behøver ikke kommentarer.

Tegning. 3a. Datakrypteringsalgoritme i simpel udskiftningstilstand

Tegning. 3b. Datadekrypteringsalgoritme i simpel udskiftningstilstand

Størrelsen af arrayet af åbne eller krypterede data, der er underlagt henholdsvis kryptering eller dekryptering, skal være et multiplum af 64 bit: | T o |=| T w |=64· n , efter at have udført handlingen, ændres størrelsen af det resulterende dataarray ikke.

Den enkle erstatningskrypteringstilstand har følgende funktioner:

Da datablokke er krypteret uafhængigt af hinanden og deres position i dataarrayet, resulterer kryptering af to identiske klartekstblokke i identiske chiffertekstblokke og omvendt. Den noterede egenskab vil give kryptanalytikeren mulighed for at konkludere om identiteten af de originale datablokke, hvis han støder på identiske blokke i det krypterede dataarray, hvilket er uacceptabelt for en seriøs chiffer.
Hvis længden af det krypterede dataarray ikke er et multiplum af 8 bytes eller 64 bit, opstår problemet med, hvordan og hvordan man supplerer den sidste ufuldstændige datablok af arrayet til de fulde 64 bits. Denne opgave er ikke så enkel, som den ser ud ved første øjekast. Indlysende løsninger som "suppler en ufuldstændig blok med nul bit" eller mere generelt "suppler en ufuldstændig blok med en fast kombination af nul og en bit" kan under visse betingelser give kryptanalytikeren mulighed for at bruge brute force metoder til at bestemme indholdet af denne meget ufuldstændige blok, og dette faktum betyder et fald i sikkerhedschiffer. Derudover vil længden af chifferteksten ændre sig og øges til nærmeste heltalsmultipel på 64 bit, hvilket ofte er uønsket.

Ved første øjekast gør ovenstående funktioner det næsten umuligt at bruge den simple udskiftningstilstand, fordi den kun kan bruges til at kryptere dataarrays med en størrelse, der er et multiplum af 64 bit og ikke indeholder gentagne 64-bit blokke. Det ser ud til, at det for enhver reel data er umuligt at garantere opfyldelsen af disse betingelser. Dette er næsten sandt, men der er en meget vigtig undtagelse: husk, at nøglestørrelsen er 32 bytes, og størrelsen på erstatningstabellen er 64 bytes. Derudover vil tilstedeværelsen af gentagne 8-byte blokke i en nøgle eller erstatningstabel indikere deres meget dårlige kvalitet, så en sådan gentagelse kan ikke eksistere i rigtige nøgleelementer. Således fandt vi ud af, at den simple udskiftningstilstand er ganske velegnet til at kryptere nøgleinformation, især da andre tilstande er mindre bekvemme til dette formål, da de kræver et ekstra synkroniseringsdataelement - en synkroniseringsmeddelelse (se næste afsnit). Vores gæt er korrekt; GOST foreskriver brugen af simpel erstatningstilstand udelukkende til kryptering af nøgledata.

Gumming.

Hvordan kan du slippe af med manglerne ved den simple udskiftningstilstand? For at gøre dette er det nødvendigt at gøre det muligt at kryptere blokke med en størrelse på mindre end 64 bit og sikre, at chiffertekstblokken afhænger af dens antal, med andre ord, randomisere krypteringsproces. I GOST opnås dette på to forskellige måder i to krypteringstilstande, hvilket giver spil . Gumming - dette er pålægning (fjernelse) af en kryptografisk skala på åbne (krypterede) data, det vil sige en sekvens af dataelementer genereret ved hjælp af en kryptografisk algoritme for at opnå krypterede (åbne) data. For at anvende gamma under kryptering og fjerne det under dekryptering, skal der anvendes gensidigt inverse binære operationer, for eksempel addition og subtraktion modulo 2 64 for 64-bit datablokke. I GOST bruges til dette formål operationen af bitvis addition modulo 2, da det er det omvendte af sig selv og desuden er det mest simpelt implementeret i hardware. Gamma løser begge nævnte problemer: For det første er alle gamma-elementer forskellige for rigtige krypterede arrays, og derfor vil resultatet af kryptering af selv to identiske blokke i et dataarray være anderledes. For det andet, selvom gamma-elementerne genereres i lige store portioner af 64 bit, kan en del af en sådan blok med en størrelse svarende til størrelsen af den krypterede blok anvendes.

Lad os nu gå direkte til beskrivelsen af gamma-tilstanden. Gamma for denne tilstand opnås som følger: ved hjælp af en eller anden algoritmisk recurrent number sequence generator (RNGN) genereres 64-bit datablokke, som derefter konverteres ved hjælp af 32-3 cyklussen, det vil sige krypteret i den simple udskiftningstilstand, hvilket resulterer i gammablokke. På grund af det faktum, at gamma-applikation og fjernelse udføres ved hjælp af den samme bitvise eksklusive eller operation, er krypterings- og dekrypteringsalgoritmerne i gamma-tilstand identiske, deres generelle skema er vist i figur 4.

Den RGPG, der bruges til at generere skalaen, er en tilbagevendende funktion: – elementer i den tilbagevendende sekvens, f– transformationsfunktion. Derfor opstår spørgsmålet uundgåeligt om dets initialisering, det vil sige om elementet. Faktisk er dette dataelement en algoritmeparameter for gammatilstande; i diagrammerne er det betegnet som S, og kaldes i kryptografi sync send , og i vores GOST – indledende fyldning et af indkoderregistrene. Af visse grunde besluttede udviklerne af GOST ikke at bruge synkroniseringsmeddelelsen direkte til at initialisere RGFC, men resultatet af dens konvertering i henhold til 32-Z-cyklussen: . Sekvensen af elementer, der genereres af RGHR, afhænger helt af dens indledende fyldning, det vil sige, at elementerne i denne sekvens er en funktion af deres antal og den indledende fyldning af RGHR: hvor f i(x)=f(f i –1 (x)), f 0 (x)=x. Under hensyntagen til transformationen ved hjælp af den simple udskiftningsalgoritme tilføjes en afhængighed af nøglen også:

Hvor Г i– jeg- skalaens element, K- nøgle.

Rækkefølgen af gamma-elementer, der skal bruges i gamma-tilstand, er således entydigt bestemt af nøgledataene og synkroniseringsmeddelelsen. For at krypteringsproceduren skal være reversibel, skal den samme synkroniseringsmeddelelse naturligvis bruges i krypterings- og dekrypteringsprocesserne. Af kravet om gammaens unikke karakter, hvis manglende overholdelse fører til et katastrofalt fald i chifferens styrke, følger det, at for at kryptere to forskellige dataarrays på den samme nøgle, er det nødvendigt at sikre brugen af forskellige synkroniseringsmeddelelser. Dette fører til behovet for at lagre eller transmittere synkroniseringsmeddelelsen langs kommunikationskanaler sammen med de krypterede data, selvom det i nogle specielle tilfælde kan forudbestemmes eller beregnes på en særlig måde, hvis kryptering af to arrays med den samme nøgle er udelukket.

Lad os nu se nærmere på den RGPC, der bruges i GOST til at generere gamut-elementer. Først og fremmest skal det bemærkes, at det ikke er nødvendigt at angive nogen statistiske karakteristika for den genererede talrække. RGHR blev designet af udviklerne af GOST baseret på behovet for at opfylde følgende betingelser:

gentagelsesperioden for talsekvensen genereret af RGPC'en bør ikke afvige meget (i procent) fra den maksimalt mulige værdi for en given blokstørrelse på 2 64;
tilstødende værdier produceret af RGPG skal afvige fra hinanden i hver byte, ellers vil kryptanalytikerens opgave blive forenklet;
RGPC'en skulle være ret nem at implementere både i hardware og software på de mest almindelige typer processorer, hvoraf de fleste er kendt for at være 32-bit.

Baseret på de anførte principper designede skaberne af GOST en meget vellykket RGHR, som har følgende egenskaber:

Hvor C 0 =1010101 16 ;

Hvor C 1 =1010104 16 ;

Sænkningen i et tal angiver dets talsystem, så konstanterne, der bruges i dette trin, er skrevet i hexadecimal.

Det andet udtryk har brug for kommentarer, da teksten i GOST indeholder noget andet: , med samme værdi af konstanten C 1 . Men længere nede i standardteksten er der givet en kommentar, at det viser sig under operationen at tage resten modulo 2 32 –1 der forstås ikke på samme måde som i matematik. Forskellen er, at ifølge GOST (2 32 –1) mod(2 32 –1)=(2 32 –1), ikke 0. Dette forenkler faktisk implementeringen af formlen, og det matematisk korrekte udtryk for den er givet ovenfor.

gentagelsesperioden for sekvensen for den nederste del er 2 32, for den ældre del 2 32 -1, for hele sekvensen er perioden 2 32 (2 32 -1), beviset for dette faktum er meget enkelt, få det dig selv. Den første af de to formler er implementeret i en kommando, den anden, på trods af dens tilsyneladende besværlighed, i to kommandoer på alle moderne 32-bit processorer - den første kommando udfører den sædvanlige additionsmodulo 2 32 med lagring af carry bit, og den anden kommando tilføjer carry bit til den resulterende betydning.

Krypteringsalgoritmediagrammet i gammatilstand er vist i figur 4; nedenfor er forklaringer til skemaet:

Figur 4. Algoritme til kryptering (dekryptering) af data i gammatilstand.