Blokkchiffer
Inndataene for blokkchifferet er en blokk med n biter og en k-bit nøkkel. Ved utgangen, etter påføring av krypteringstransformasjonen, oppnås en n-bit kryptert blokk, og ubetydelige forskjeller i inngangsdataene fører vanligvis til en betydelig endring i resultatet. Blokkchiffer implementeres ved gjentatte ganger å bruke noen grunnleggende transformasjoner på blokker av kildeteksten.Grunnleggende konverteringer:
Feistel Network Transformers
Dette er en transformasjon over vektorer (blokker) som representerer venstre og høyre halvdel av skiftregisteret. DES bruker frem Feistel-transform i kryptering (se figur 1) og omvendt Feistel-transform til dekryptering (se figur 2).
DES krypteringsskjema
Originalteksten er en blokk på 64 biter. Chifferteksten er en blokk på 64 biter.
Krypteringsprosessen består av en innledende permutasjon, 16 krypteringssykluser og en siste permutasjon.
Tenk på et detaljert diagram av DES-algoritmen:
L i R i = 1,2 \ ldots. Venstre og høyre halvdel av en 64-bits blokk L i R i
k i - 48 bits nøkler
f - krypteringsfunksjon
IP - innledende permutasjon
IP -1 er den endelige permutasjonen. 
I følge tabellen er de første 3 bitene av den resulterende IP (T)-blokken etter den første permutasjonen av IP bitene 58, 50, 42 av inngangsblokken T, og dens siste 3 biter er bitene 23, 15, 7 av inngangsblokk. Videre deltar 64-bits IP (T)-blokken i 16-sykluser av Feistel-transformasjonen.
16 sykluser med Feistel-transformasjon:
Del IP (T) i to deler L 0, R 0, hvor L 0, R 0 - henholdsvis 32 mest signifikante biter og 32 minst signifikante biter av blokken T0 IP (T) = L 0 R 0
La T i -1 = L i -1 R i -1 resultat av (i-1) iterasjon, så bestemmes resultatet av den i-te iterasjonen T i = L i R i:
Li = R i - 1 Den venstre halvdelen av Li er lik høyre halvdel av den forrige vektoren Li - 1 R i - 1. Og høyre halvdel av R i er bittilsetningen av Li - 1 og f (R i - 1, k i) modulo 2.
I 16-syklus Feistel-transformasjonen spiller funksjonen f rollen som kryptering. La oss vurdere funksjonen f i detalj.
Argumentene til f er 32-bits vektoren R i - 1, 48-biters nøkkel k i, som er resultatet av å transformere den 56-biters originale chiffernøkkelen k.
For å beregne funksjonen f brukes utvidelsesfunksjonen E, transformasjonen S, bestående av 8 transformasjoner av S-bokser, og permutasjonen P..
Funksjon E utvider 32 bit vektor R i - 1 til 48 bit vektor E (R i - 1) ved å duplisere noen av bitene fra R i - 1 mens rekkefølgen på bitene til vektor E (R i - 1) er vist i tabell 2. 
De tre første bitene av vektoren E (Ri - 1) er bitene 32, 1, 2 av vektoren Ri -1. Tabell 2 viser at bitene 1, 4, 5, 8, 9, 12, 13, 16, 17, 20, 21, 24, 25, 28, 29, 32 er duplisert. De siste 3 bitene av vektor E (Ri - 1) er biter 31, 32, 1 av vektor R i - 1. Blokken E (R i -1) oppnådd etter permutasjonen blir lagt til modulo 2 med tastene k i og deretter representert som åtte påfølgende blokker B 1, B 2, ... B 8.
E (R i - 1) = B 1 B 2 ... B 8
Hver B j er en 6-bits blokk. Videre transformeres hver av blokkene B j til en 4-bits blokk B "j ved å bruke transformasjoner Sj. Transformasjonene Sj bestemmes av tabell 3. Anta at B 3 = 101111 og vi ønsker å finne B" 3. Den første og siste biten av B 3 er binær notasjon av tallet a, 0. Verdien av funksjonen f (R i - 1, ki) (32 bits) oppnås ved permutasjonen P påført 32-bits blokken B "1 B" 2 ... B "8. P er gitt av tabell 4. 
f (R i - 1, k i) = P (B "1 B" 2 ... B "8)
I henhold til tabell 4 er de fire første bitene av den resulterende vektoren etter handlingen av funksjonen f bitene 16, 7, 20, 21 av vektoren B "1 B" 2 ... B "8
Genererer nøkler k i.
Nøklene ki oppnås fra den innledende nøkkelen k (56 biter = 7 byte eller 7 tegn i ASCII) på denne måten. Åtte biter funnet i posisjonene 8, 16, 24, 32, 40, 48, 56, 64 legges til nøkkelen k slik at hver byte inneholder et oddetall av enere. Dette brukes til å oppdage feil ved utveksling og lagring av nøkler. Permuter deretter den utvidede nøkkelen (bortsett fra de ekstra bitene 8, 16, 24, 32, 40, 48, 56, 64). En slik permutasjon er definert som i tabell 5. 
Denne permutasjonen er definert av to blokker C 0 og D 0 på 28 biter hver. De første 3 bitene av C 0 er bitene 57, 49, 41 av den utvidede nøkkelen. Og de tre første bitene av D 0 er bitene 63, 55, 47 av den utvidede nøkkelen. C i, Di i = 1,2,3 ... er hentet fra C i - 1, D i - 1 ved ett eller to venstre sykliske skift i henhold til tabell 6. 
Nøkkelen ki, i = 1, ... 16 består av 48 biter valgt fra bitene til vektoren C i D i (56 bits) i henhold til tabell 7. Den første og andre biten ki er bitene 14, 17 av vektoren C i D i 
Den endelige permutasjonen IP - 1 virker på T 16 og brukes til å gjenopprette posisjon. Det er det motsatte av IP-permutasjon. Den endelige permutasjonen bestemmes av tabell 8. 
DES-bruksmoduser DES kan brukes i fire moduser.
Data Encryption Standard (DES) er en datakrypteringsstandard som ble oppfunnet i USA på 1980-tallet. Blant chifferene regnes han med rette som en "pensjonert", mens han forblir kryptografiens arbeidshest. DES sluttet å være nyttig under forholdene med ultrarask teknologi og store datamengder på grunn av begrensningene på 56 biter per nøkkel og 64 biter for data. Den er imidlertid fortsatt i bruk.
Hva er blokkchiffer?
DES er en blokkchifferalgoritme. I løpet av de siste 20-30 årene har det blitt laget mange blokkchiffer, men å lage et godt chiffer som er sikkert er en ganske vanskelig oppgave. Det er viktig at chifferet har egenskaper som gjør at det kan fungere i mange områder og bransjer.
Blokkchiffer består av flere iterasjoner av å bruke noen chiffer etter tur. Hver iterasjon kalles en runde. Som praksis viser, er selv noen av de primitive algoritmene, når de brukes sekvensielt, i stand til å lage pålitelige chiffer. DES er et eksempel som har vært pålitelig og uforgjengelig i 20 år.
Denne tilnærmingen til utvikling av chiffer letter prosessen og forenkler sikkerhetsanalysen. For eksempel begynner et testangrep på et blokkchiffer med et minimum antall runder og fortsetter metodisk med en økning i antall runder.
Bruker DES
Selv om DES anses som foreldet og ikke oppdatert, kan den brukes for eksempel i form av 3DES, når chifferen brukes tre ganger på rad. Denne tilnærmingen fjerner begrensningen på størrelsen på nøkkelen, men blokken med krypterte data forblir den samme. På en gang var DES et ganske raskt og kryptosterkt chiffer. Nå er ikke dette tilfellet, og 3DES er faktisk tre ganger tregere. Til tross for dette brukes DES fortsatt i en rekke systemer, men bruk i nye prosjekter er forbudt.
DES var den offisielle chifferalgoritmen i USA frem til 1998. I 1997 begynte etableringen av en ny standard kalt System), og selv om kryptoanalyse viser at forsøk på å bryte DES fører til mange systemer med ikke-lineære ligninger, kan ikke analytiske metoder hjelpe til med å løse problemet - dets svake punkt er det lille settet med mulige nøkler. Antallet deres er lik 2 56 og alle alternativer kan telles opp ved hjelp av moderne teknologier på relativt kort tid.
En runde i algoritmen
For klarhet i presentasjonen og beskrivelse av DES-algoritmen bruker vi figur (linjediagram av beregninger) 4.1, som viser strukturen til en runde.
Hvert rektangel i et linjediagram representerer en form for beregning, og en pil som går ut fra det indikerer hvor resultatene av blokken skal overføres. Plusstegnet, sirklet, angir en "eksklusiv eller" operasjon, kjent i programmering som XOR. Operasjonen kalles også "bitvis addisjon" eller "addisjon uten bære". På nettet kan du finne DES-algoritmen i C og studere den for en bedre forståelse.
DES aksepterer en 64-bits tekstblokk. Den går gjennom den innledende permutasjonen i henhold til et visst prinsipp. Ved analyse av algoritmen viste det seg at det er liten mening med denne permutasjonen, siden den ikke gir noen kryptografisk effekt. Tekstblokken er delt inn i 2 like deler: høyre (R) og venstre (L). Deretter byttes og kombineres de krypterte delene, og på slutten av runden oppnås en 64-bits datablokk, kun kryptert.
Generell algoritme
DES-algoritmen inkluderer 16 runder, utført i henhold til skjemaet beskrevet ovenfor. Alle runder er nummerert til i, hvor i = (1; 16). Hver i-te runde fra paret (Li-1, Ri-1) får et nytt par (Li, Ri) ved å bruke Ki-tasten. Hovedtransformasjonene finner sted inne i funksjonen F.
Algoritme for funksjonen F
Som du kan se fra figur 4.1, går R gjennom "Expand"-operasjonen. Denne blokken dupliserer et antall biter fra R og supplerer den med dem, og får en 48-bits verdi. Det resulterende resultatet går gjennom en bitvis tillegg med en 48-bit Ki-nøkkel. Og resultatet av denne operasjonen overføres til blokk S. Blokk S inneholder 8 små substitusjonsmatriser, som velges på en spesiell måte.
Hver matrise mottar 6 biter med informasjon som input og sender ut en 4-bits verdi. Som et resultat mottar blokk S 48-bits data ved inngangen, og ved utgangen representerer den resultatet som en 32-bits verdi.
Denne 32-bits verdien går gjennom en permutasjonsoperasjon til, hvoretter den summeres av xor-operasjonen med L. Til slutt byttes høyre og venstre side og runden avsluttes. Algoritmen gjør som tidligere nevnt 16 slike runder.
Her skal vi ikke overbelaste artikkelen med eksempler som tar mye plass. DES arbeid og eksempler kan sees på nettet.
Feistel-chiffer
DES er basert på Feistel-chifferet. Ideen er ganske elegant. På hver runde legges L-delen til med verdien av F (R, Ki) og L endrer posisjon med R. Nøkkeltrekket til Feistel-algoritmen er at dekryptering og kryptering består av de samme trinnene: L- og R-delene er byttet, og så utføres addisjonsoperasjonen L og F (R, Ki). Dette gjør kryptering og dekrypteringsprosedyrer enkle og greie.
En interessant endring introduseres ofte i Feistel-siffer - avskaffelsen av permutasjonen av L og R i den siste iterasjonen. Dette gjør krypterings- og dekrypteringsalgoritmene helt symmetriske. Den eneste forskjellen er i rekkefølgen som Ki-tastene brukes i. Dette prinsippet viste seg å være ekstremt praktisk for bruk på programvarenivå, siden kryptering og dekryptering utføres ved hjelp av en funksjon. For eksempel en lakonisk implementering av DES-krypteringsalgoritmen i C.
Krypteringsnøkler
DES bruker seksten 48-biters nøkler for å kryptere data. En nøkkel per runde. Hver nøkkel genereres ved å sample 48 biter fra en 56-bits hovednøkkel. Nøkkelgenerering for en gitt runde bestemmes av en mekanisme beskrevet i DES-dokumentasjonen.
Kort fortalt er algoritmen for å hente i-nøkkelen som følger. Bits legges til hovednøkkelen i posisjonene 8, 16, 24, 32, 40, 48, 56, 64. Dette gjøres på en slik måte at hver byte inneholder et oddetall av enere. Overholdelse av regelen hjelper til med å oppdage nøkkelutvekslingsfeil. Deretter, ved bruk av spesielle tabeller, gjennomgår den polstrede nøkkelen permutasjoner og skift, med unntak av bitene som er lagt til. Dermed oppnås den nødvendige nøkkelen.
DES komponenter
Hver komponent i DES-algoritmen løser et spesifikt problem:
- Feistels algoritme forenkler kryptering og dekryptering samtidig som den sikrer at begge halvdelene av teksten blandes.
- Bitvis summering av deler av tekst med nøkler blander de offentlige dataene med nøkkelen og krypterer den.
- S-boks og oppslagstabeller gjør algoritmen ikke-lineær, og øker motstanden mot ulike angrep.
- Utvidelse, S-boks og permutasjoner gir diffusjon av algoritmen - skredeffekten. Med andre ord, hvis minst 1 bit i inngangsdataene til funksjonen F endres, vil dette føre til en endring i mange biter på en gang. Hvis en skredeffekt ikke observeres i chifferen, vil endringer i åpne data føre til tilsvarende endringer i kryptert form, som kan spores og brukes til cracking. I kryptografi er det et kriterium for skredeffekten. Algoritmen tilfredsstiller det hvis, når 1 bit åpne data endres, minst halvparten av de krypterte dataene endres. DES-algoritmen tilfredsstiller den fra runde 4. Bunnlinjen - å endre 1 bit åpne data i DES-chifferet vil endre 29 biter.
Sikkerhetsproblemer i DES
Det åpenbare problemet med DES er å hente krypteringsnøkler fra en offentlig nøkkel. Hva skjer hvis du velger null som nøkkel (alle biter av nøkkelen er lik 0)? Dette vil føre til at utvalget av alle nøkler for kryptering på hver runde vil være det samme, og alle nøkler vil være lik null. Ikke bare vil 16 krypteringer passere med én nøkkel, men på grunn av det faktum at DES-krypterings- og dekrypteringsalgoritmer bare er forskjellige i rekkefølgen nøklene brukes, vil de være nøyaktig like. Hele poenget med kryptering vil gå tapt.
DES har 4 taster, som kalles svake taster, som fører til den beskrevne effekten. DES har 12 halvsvake og 48 pseudo-svake nøkler, som begrenser variasjonen av genererte nøkler i runder. Med andre ord er det en mulighet for at i løpet av kryptering i 16 runder, vil ikke 16 forskjellige nøkler bli brukt, men 8, 4 eller til og med 2.
En mindre åpenbar ulempe med DES er komplementaritetsegenskapen. Det betyr at hvis du bruker klartekstkomplement og nøkkelkomplement for kryptering, ender du opp med en verdi som er komplementet til chifferteksten. Denne latterlige egenskapen kan føre til vellykkede angrep på prosjekter som bruker DES for sikkerhet.
Krypteringsnøkkelproblem
Det er grunnleggende for DES og anses som hovedgrunnen til at denne algoritmen bør forlates. Siden nøkkelstørrelsen i DES er 56 biter, må du se gjennom 2 56 alternativer for å iterere over alle nøklene. Er det så mye?
Hvis du utfører 10 millioner nøkkelkontroller per sekund, vil verifiseringen ta omtrent 2000 år. Algoritmen ser ut til å være ganske robust. Det var slik i forrige århundre, da det å bygge en datamaskin med denne kraften var en nesten umulig oppgave, både fra et teknisk og økonomisk synspunkt.
Hvis du lager en datamaskin med en million sjetonger, vil det ta 20 timer å iterere gjennom hele settet med DES-nøkler. Den første datamaskinen av denne typen for dekryptering ved hjelp av DES-algoritmen dukket opp tilbake i 1998, som taklet oppgaven på 56 timer. Moderne teknologier av nettverk og parallelle prosesser kan redusere denne tiden enda mer.
Krypteringsanalyse og DES
Det kan sies uten å overdrive at DES ga opphav til en anvendt vitenskap kalt "Cryptographic Analysis". Helt fra begynnelsen av utseendet til DES ble det gjort forsøk på å knekke det, vitenskapelig arbeid ble utført for å studere det. Alt dette førte til fødselen av slike områder av matematikk som:
- lineær kryptoanalyse - studiet og identifiseringen av forholdet mellom ren tekst og chiffertekst;
- differensiell kryptoanalyse - studiet og analysen av avhengigheter mellom flere åpne tekster og deres krypterte versjoner;
- kryptanalyse på koblede nøkler - studiet av avhengigheter mellom chiffertekster oppnådd på primærnøkkelen, og nøklene knyttet til primærnøkkelen på noen måte.
DES har motstått 20 år med verdensomspennende kryptoanalyse og angrep, men er fortsatt en sterk chiffer. Men den som søker vil alltid finne...
- Biham og Shamir, forskere fra Israel, viste i 1991 ved hjelp av differensiell kryptoanalyse at DES kan angripes der nøkkelen beregnes, forutsatt at angriperen har 2,47 spesielt matchede par med ren tekst og chiffertekst.
- Den japanske forskeren Mitsuru Matsui viste i 1993 at nøkkelen kan beregnes ved hjelp av lineær kryptoanalyse. For å gjøre dette trenger du bare å vite 2,47 par ren tekst og den tilsvarende krypterte versjonen.
I fremtiden ble disse hackingmetodene litt forbedret, forbedret og forenklet, og en rekke nye hackingmetoder dukket opp. Men de forblir for kompliserte, mot deres bakgrunn ser en fullstendig oppregning av alle nøkkelvarianter ut som det mest passende angrepet på DES.
DES-standarden er utformet for å beskytte mot uautorisert tilgang til sensitiv, men uklassifisert informasjon i amerikanske myndigheter og kommersielle organisasjoner. Algoritmen som ligger til grunn for standarden spredte seg ganske raskt, og allerede i 1980 ble den godkjent av US National Institute of Standards and Technology. Siden den gang har DES blitt en standard, ikke bare i navn, men faktisk. Det finnes programvare og spesialiserte mikrodatamaskiner designet for kryptering og dekryptering av informasjon i dataoverføringsnettverk.
DES er den desidert mest utbredte algoritmen som brukes i systemer for å beskytte kommersiell informasjon. Dessuten blir implementeringen av DES-algoritmen i slike systemer et tegn på god form.
De viktigste fordelene med DES-algoritmen:
· Bare én nøkkel på 56 biter brukes;
· Etter å ha kryptert en melding med én pakke, kan du bruke hvilken som helst annen for å dekryptere;
· Den relative enkelheten til algoritmen gir en høy hastighet på informasjonsbehandlingen;
· Tilstrekkelig høy robusthet av algoritmen.
DES krypterer 64-bits blokker med data ved hjelp av en 56-bits nøkkel. DES-dekryptering er den omvendte operasjonen av kryptering og utføres ved å gjenta krypteringsoperasjonene i omvendt rekkefølge (til tross for den tilsynelatende selvfølgeligheten, gjøres dette ikke alltid. Senere skal vi ta for oss chiffer der kryptering og dekryptering utføres ved hjelp av forskjellige algoritmer).
Krypteringsprosessen består av en innledende bitbytting av en 64-bits blokk, seksten krypteringssykluser og til slutt en omvendt bitbytte (fig. 1).
Det bør bemerkes med en gang at ALLE tabeller gitt i denne artikkelen er STANDARD, og bør derfor inkluderes i implementeringen av algoritmen uendret. Alle permutasjoner og koder i tabellene ble valgt av utviklerne på en slik måte at dekrypteringsprosessen ble så vanskelig som mulig ved å gjette nøkkelen. Strukturen til DES-algoritmen er vist i fig. 2.
Ris. 2.
La neste 8-byte blokk T leses fra filen, som transformeres ved hjelp av IP initial permutasjonsmatrisen (tabell 1) som følger: bit 58 i T blokken blir bit 1, bit 50 – bit 2, etc., som vil resultere i: T (0) = IP (T).
Den resulterende bitsekvensen T (0) er delt inn i to sekvenser på 32 biter hver: L (0) - venstre eller mest signifikante biter, R (0) - høyre eller minst signifikante biter.
Tabell 1: IP Initial Permutation Matrix
58 50 42 34 26 18 10 02
60 52 44 36 28 20 12 04
62 54 46 38 30 22 14 06
64 56 48 40 32 24 16 08
57 49 41 33 25 17 09 01
59 51 43 35 27 19 11 03
61 53 45 37 29 21 13 05
63 55 47 39 31 23 15 07
Deretter utføres kryptering, bestående av 16 iterasjoner. Resultatet av den i-te iterasjonen beskrives med følgende formler:
R (i) = L (i-1) xor f (R (i-1), K (i)),
hvor xor er EXCLUSIVE OR-operasjonen.
Funksjonen f kalles krypteringsfunksjonen. Argumentene er 32-bits sekvensen R (i-1), oppnådd ved (i-1) iterasjonen, og 48-bits nøkkelen K (i), som er resultatet av transformasjon av 64-bits nøkkelen K. I detalj er krypteringsfunksjonen og algoritmen for å oppnå nøkler K(i) beskrevet nedenfor.
Ved den 16. iterasjonen oppnås sekvensene R (16) og L (16) (uten permutasjon), som er sammenkoblet til en 64-bits sekvens R (16) L (16).
Deretter permuteres posisjonene til bitene i denne sekvensen i samsvar med matrisen IP-1 (tabell 2).
Tabell 2: IP -1 omvendt permutasjonsmatrise
40 08 48 16 56 24 64 32
39 07 47 15 55 23 63 31
38 06 46 14 54 22 62 30
37 05 45 13 53 21 61 29
36 04 44 12 52 20 60 28
35 03 43 11 51 19 59 27
34 02 42 10 50 18 58 26
33 01 41 09 49 17 57 25
Matrisene IP -1 og IP er relatert som følger: verdien av det første elementet i IP -1-matrisen er 40, og verdien av det 40. elementet i IP-matrisen er 1, verdien av det 2. element i IP -1-matrisen er 8, og verdien av den åttende elementet i IP-matrisen er lik 2, og så videre.
Datadekrypteringsprosessen er omvendt til krypteringsprosessen. Alle trinn må utføres i omvendt rekkefølge. Dette betyr at de dekrypterte dataene først omorganiseres i henhold til IP-1-matrisen, og deretter utføres de samme handlingene på R (16) L (16) bitsekvensen som i krypteringsprosessen, men i omvendt rekkefølge.
Den iterative dekrypteringsprosessen kan beskrives med følgende formler:
R (i-1) = L (i), i = 1, 2, ..., 16;
L (i-1) = R (i) x eller f (L (i), K (i)), i = 1, 2, ..., 16.
Ved den 16. iterasjonen oppnås sekvensene L (0) og R (0), som er sammenkoblet til en 64-bits sekvens L (0) R (0).
Bitposisjonene til denne sekvensen blir deretter omorganisert i henhold til IP-matrisen. Resultatet av en slik permutasjon er den opprinnelige 64-bits sekvensen.
Vurder nå krypteringsfunksjonen f (R (i-1), K (i)). Det er vist skjematisk i fig. 3.
Ris. 3.
For å beregne verdien av funksjonen f, brukes følgende matrisefunksjoner:
E - utvidelse av en 32-bits sekvens til 48-bit,
S1, S2, ..., S8 - konvertering av en 6-bits blokk til en 4-bits blokk,
P - permutasjon av biter i en 32-bits sekvens.
Utvidelsesfunksjonen E er definert i tabell. 3. I følge denne tabellen er de første 3 bitene av E (R (i-1)) bitene 32, 1 og 2, og de siste er 31, 32 og 1.
Tabell 3: Utvidelsesfunksjon E
32 01 02 03 04 05
04 05 06 07 08 09
08 09 10 11 12 13
12 13 14 15 16 17
16 17 18 19 20 21
20 21 22 23 24 25
24 25 26 27 28 29
28 29 30 31 32 01
Resultatet av funksjonen E (R (i-1)) er en 48-bits sekvens, som er lagt til modulo 2 (operasjon xor) med en 48-bits nøkkel K (i). Resultatet er en 48-bits sekvens, som er delt inn i åtte 6-bits blokker B (1) B (2) B (3) B (4) B (5) B (6) B (7) B (8) . Det er:
E (R (i-1)) xor K (i) = B (1) B (2)... B (8).
Funksjonene S1, S2, ..., S8 bestemmes av tabell. 4.
Tabell 4
Til bord. 4. Krever ytterligere avklaring. La 6-bits blokken B (j) = b1b2b3b4b5b6 angi inngangen til matrisefunksjonen Sj, så indikerer to-bits nummeret b1b6 radnummeret til matrisen, og b2b3b4b5 er kolonnenummeret. Resultatet av Sj (B (j)) er et 4-bits element plassert i skjæringspunktet mellom den angitte raden og kolonnen.
For eksempel, B (1) = 011011. Da er S1 (B (1)) plassert i skjæringspunktet mellom rad 1 og kolonne 13. Kolonne 13 i rad 1 er satt til 5. Så S1 (011011) = 0101.
Ved å bruke valgoperasjonen på hver av 6-bits blokkene B (1), B (2), ..., B (8), får vi en 32-bits sekvens S1 (B (1)) S2 (B (2) )) S3 (B ( 3))... S8 (B (8)).
Til slutt, for å få resultatet av krypteringsfunksjonen, må bitene i denne sekvensen byttes. Til dette brukes permutasjonsfunksjonen P (tabell 5). I inngangssekvensen byttes bitene slik at bit 16 blir bit 1, bit 7 blir bit 2, og så videre.
Tabell 5: Overføringsfunksjon P
Og dermed,
f (R (i-1), K (i)) = P (S1 (B (1)), … S8 (B (8)))
For å fullføre beskrivelsen av datakrypteringsalgoritmen, gjenstår det å gi en algoritme for å oppnå 48-bits nøkler K(i), i = 1 ... 16. Ved hver iterasjon brukes en ny nøkkelverdi K(i), som beregnes ut fra startnøkkelen K. K er en 64-bits blokk med åtte paritetsbiter plassert i posisjonene 8,16,24,32,40,48, 56, 64.
For å fjerne kontrollbitene og permutere resten, brukes funksjonen G for den innledende nøkkelforberedelsen (tabell 6).
Tabell 6
Innledende nøkkelforberedelsesmatrise G
57 49 41 33 25 17 09
01 58 50 42 34 26 18
10 02 59 51 43 35 27
19 11 03 60 52 44 36
63 55 47 39 31 23 15
07 62 54 46 38 30 22
14 06 61 53 45 37 29
21 13 05 28 20 12 04
Transformasjonsresultatet G (K) er delt inn i to 28-bits blokker C (0) og D (0), og C (0) vil bestå av bit 57, 49, ..., 44, 36 av nøkkelen K, og D (0) vil bestå av bits 63, 55, ..., 12, 4 av nøkkelen K. Etter å ha definert C (0) og D (0), C (i) og D (i), i = 1 ... 16, er rekursivt bestemt. For å gjøre dette, bruk et syklisk venstreskift med én eller to biter, avhengig av iterasjonsnummeret, som vist i tabellen. 7.
Tabell 7. Skifttabell for beregning av nøkkel
|
Iterasjonsnummer |
Shift (bit) |
Den resulterende verdien blir igjen "blandet" i samsvar med matrisen H (tabell 8).
Tabell 8: Nøkkel etterbehandlingsmatrise H
14 17 11 24 01 05
03 28 15 06 21 10
23 19 12 04 26 08
16 07 27 20 13 02
41 52 31 37 47 55
30 40 51 45 33 48
44 49 39 56 34 53
46 42 50 36 29 32
Nøkkelen K(i) vil bestå av bitene 14, 17, ..., 29, 32 i sekvensen C(i)D(i). Og dermed:
K (i) = H (C (i) D (i))
Blokkdiagrammet for nøkkelberegningsalgoritmen er vist i fig. 4.
Ris. 4.
Gjenoppretting av originalteksten utføres ved hjelp av denne algoritmen, men først bruker du tasten K (15), deretter K (14), og så videre. Nå skal det være klart for deg hvorfor forfatteren på det sterkeste anbefaler å bruke de gitte matrisene. Hvis du begynner å være selvrettferdig, må du ha mottatt en veldig hemmelig kode, men du kan da ikke avsløre den selv!
Den vanligste og mest kjente symmetriske krypteringsalgoritmen er DES (Datakrypteringsstandard). Algoritmen ble utviklet i 1977, og i 1980 ble den tatt i bruk av NIST (National Institute of Standards and Technology, USA) som standard.
DES er et klassisk to-grenet Feistel-nettverk. Data er kryptert i 64-biters blokker ved hjelp av en 56-bits nøkkel. Algoritmen konverterer 64-bits inngang til 64-bits utgang i flere omganger. Nøkkellengden er 56 bits. Krypteringsprosessen har fire stadier. Det første trinnet er å utføre en innledende permutasjon (IP) av 64-biters kilden (whitening), hvor bitene omorganiseres i henhold til en standardtabell. Neste trinn består av 16 runder med samme funksjon som bruker skift- og substitusjonsoperasjoner. På det tredje trinnet reverseres venstre og høyre halvdel av utgangen fra den siste (16.) iterasjonen. Til slutt, i det fjerde trinnet, omorganiseres IP-1-resultatet oppnådd i det tredje trinnet. Permutasjon IP-1 er invers til den opprinnelige permutasjonen.
Fig. 4. DES-algoritme
Figuren viser måten en 56-bits nøkkel brukes på. Til å begynne med mates nøkkelen til inngangen til permutasjonsfunksjonen. Så, for hver av de 16 rundene, er undernøkkelen Ki en venstre syklisk skift- og permutasjonskombinasjon. Permutasjonsfunksjonen er den samme for hver runde, men K i-undernøklene er forskjellige for hver runde på grunn av den gjentatte forskyvningen av nøkkelbitene.
Den innledende permutasjonen og dens inverse bestemmes av standardtabellen. Hvis M er tilfeldig 64 biter, så er X = IP (M) 64 bit permutert. Hvis vi bruker den inverse permutasjonsfunksjonen Y = IP-1 (X) = IP-1 (IP (M)), får vi den opprinnelige bitsekvensen.
Beskrivelse av runden des
Vurder sekvensen av transformasjoner som brukes i hver runde.
Fig. 5. Illustrasjon av en runde med DES-algoritme
64-biters inngangsblokk går gjennom 16 runder, og ved hver iterasjon oppnås en mellomliggende 64-bits verdi. Venstre og høyre side av hver mellomverdi behandles som separate 32-bits verdier, merket med L og R. Hver iterasjon kan beskrives som følger:
R i = L i -1 F (R i -1, Ki)
Dermed er utgangen til venstre halvdel av Li lik inngangen til høyre halvdel av R i-1. Utgangen til høyre halvdel av R i er resultatet av XORing L i-1 og en funksjon F avhengig av R i-1 og Ki.
La oss vurdere funksjonen F mer detaljert. R i, som mates til inngangen til funksjonen F, er 32 biter lang. Til å begynne med utvides R i til 48 biter ved å bruke en tabell som definerer en permutasjon pluss en 16 bits utvidelse. Utvidelsen skjer på følgende måte. De 32 bitene deles inn i grupper på 4 biter og utvides deretter til 6 biter ved å legge til de ytterste bitene fra to tilstøtende grupper. For eksempel hvis en del av inndatameldingen
Efgh ijkl mnop. ... ...
deretter resulterer utvidelsen i meldingen
Defghi hijklm lmnopq. ... ...
Etter det, for den resulterende 48-bits verdien, utføres en XOR-operasjon med en 48-bits undernøkkel Ki. Deretter mates den resulterende 48-bits verdien til inngangen til substitusjonsfunksjonen, resultatet av denne er en 32-bits verdi.
Substitusjonen består av åtte S-bokser, som hver mottar 6 bits som input og produserer 4 bits ved utgangen. Disse transformasjonene bestemmes av spesielle tabeller. Den første og siste biten av S-boks-inngangen bestemmer radnummeret i tabellen, de midterste 4 bitene bestemmer kolonnenummeret. Skjæringspunktet mellom rad og kolonne definerer 4-bits utdata. For eksempel, hvis inndata er 011011, er radnummeret 01 (rad 1) og kolonnenummeret er 1101 (kolonne 13). Verdien i rad 1 og kolonne 13 er 5, dvs. utgangen er 0101.
Deretter behandles den resulterende 32-bits verdien ved å bruke permutasjonen P, hvis formål er å omorganisere bitene så mye som mulig slik at i neste runde med kryptering, med høy sannsynlighet, vil hver bit bli behandlet av en annen S- eske.
Nøkkelen for en enkelt runde K i består av 48 biter. Nøklene Ki oppnås ved hjelp av følgende algoritme. For 56-bits nøkkelen som brukes som input til algoritmen, utføres først en permutasjon i samsvar med tabellen Permuted Choice 1 (PC-1). Den resulterende 56-bits nøkkelen er delt inn i to 28-biters deler, betegnet henholdsvis C0 og D0. På hver runde blir C i og Di uavhengig syklisk forskjøvet 1 eller 2 biter til venstre, avhengig av rundenummeret. De resulterende verdiene er input til neste runde. De er også en inngang til Permuted Choice 2 (PC-2), som produserer en 48-bits utgang som er inngangen til F (R i-1, Ki).
Dekrypteringsprosessen ligner på krypteringsprosessen. Chifferteksten brukes ved inngangen til algoritmen, men tastene K i brukes i omvendt rekkefølge. Det brukes 16 r i første omgang, 1 r brukes i siste omgang. La utgangen fra den i-te krypteringsrunden være L i || R i. Da vil den tilsvarende inngangen til den (16-i) -te dekrypteringsrunden være R i || L i.
Etter den siste runden av dekrypteringsprosessen, byttes de to halvdelene av utgangen slik at inngangen til den endelige permutasjonen IP-1 er R 16 || L 16. Utdataene fra dette trinnet er ren tekst.
Mer enn 30 år har gått siden DES ble tatt i bruk som amerikansk krypteringsstandard. DES er krypteringsalgoritmen med den rikeste og mest interessante historien.
Historien om opprettelsen av algoritmen
En av de mest kjente kryptologene i verden, Bruce Schneier, beskrev i sin berømte bok "Applied Cryptography" problemene til brukere av informasjonssikkerhetsverktøy på begynnelsen av 70-tallet. XX århundre (selvfølgelig snakker vi om brukere på den andre siden av "jernteppet"):
P det fantes ingen allment akseptert standard for datakryptering, eller bare mye brukte algoritmer for å beskytte informasjon, så det var ikke snakk om kompatibilitet mellom ulike programvare- eller maskinvarekrypteringsverktøy;
Nesten ethvert krypteringsverktøy var en "svart boks" med ganske uklart innhold: hvilken krypteringsalgoritme brukes, hvor kryptografisk sterk den er, om den er riktig implementert, om den er riktig opprettet, lagret, brukte krypteringsnøkler, er det noen udokumenterte funksjoner satt inn av utviklerne i verktøyet osv. – all denne svært viktige informasjonen var ikke tilgjengelig for de aller fleste kjøpere av kryptografiske midler.
Dette problemet er deltatt av US National Bureau of Standards (NBS). Som et resultat, i 1973, ble den første åpne konkurransen for en krypteringsstandard annonsert. NBS var villig til å undersøke kandidatalgoritmer som oppfyller følgende kriterier for å velge en standard:
Algoritmen må være kryptografisk sterk;
Algoritmen må være rask;
Strukturen til algoritmen bør være klar og tydelig;
Styrken på krypteringen bør kun avhenge av nøkkelen, selve algoritmen skal ikke være hemmelig;
Algoritmen bør være lett anvendelig for en rekke formål;
Algoritmen bør enkelt implementeres i maskinvare på den eksisterende elementbasen.
Det ble antatt at interesserte organisasjoner eller spesialister ville sende til NBS detaljerte spesifikasjoner av algoritmene som er tilstrekkelige for implementeringen, det vil si uten noen "hvite flekker". Det ble også antatt at algoritmen ville bli sertifisert av NBS for generell bruk, alle patent- og eksportrestriksjoner ville bli fjernet fra den, som et resultat av at en slik standard måtte løse alle kompatibilitetsproblemene til krypteringsverktøy. I tillegg overtok NBS funksjonene med sertifisering av krypteringsverktøy – det vil si at de «svarte boksene» skulle ha blitt en saga blott.
Faktisk var det bare én kandidatalgoritme: det var Lucifer-krypteringsalgoritmen utviklet av CMM. (se avsnitt 3.31). I to år ble algoritmen forfinet:
Først gjennomførte NBS, sammen med US National Security Agency (NSA, NSA - National Security Agency), en grundig analyse av algoritmen, som resulterte i dens ganske betydelige omarbeiding;
For det andre ble kommentarer og kritikk fra alle interesserte organisasjoner og enkeltpersoner akseptert for vurdering.
Som et resultat av felles aktiviteter av IBM, NBS og NSA i januar 1977 ble DES publisert som en amerikansk standard (den siste versjonen av denne standarden er i dokumentet) for datakrypteringsalgoritmer (bortsett fra høysikkerhetsinformasjon). DES-algoritmen ble patentert av YM, men NBS fikk faktisk en gratis og ubegrenset lisens til å bruke denne algoritmen. Et alternativt, men mindre vanlig navn for algoritmen er DEA (Data Encryption Algorithm).
Hovedkarakteristikker og struktur av algoritmen
DES krypterer informasjon i blokker på 64 biter ved å bruke en 64-bits krypteringsnøkkel som bruker bare 56 biter (nøkkelutvidelsesprosedyren er beskrevet i detalj nedenfor).
Informasjonskryptering utføres som følger (fig. 3.56):
1. Over en 64-bits datablokk utføres en innledende permutasjon i henhold til tabellen. 3.16.
Tabell 3.16
Tabellen tolkes som følger: verdien av inngangsbiten 58 (heretter er alle bitene nummerert fra venstre til høyre, starter fra 1) plasseres i utgangsbiten 1, verdien til den 50. biten - i bit 2 osv. .
2. Resultatet av forrige operasjon er delt inn i 2 underblokker på 32 biter (av
ris. 3,56 merket En 0 og B 0), som det gjøres 16 runder over
følgende transformasjoner:
Som nevnt ovenfor bruker DES kun 56 biter av en 64-bits krypteringsnøkkel. Hver 8. bit blir forkastet og brukes ikke på noen måte i algoritmen, og bruken av de resterende bitene av krypteringsnøkkelen i implementeringene av DES-algoritmen er ikke begrenset av standarden på noen måte. Prosedyren for å trekke ut 56 signifikante biter av en 64-bits nøkkel i fig. 3.59 er betegnet som E. I tillegg til ekstraksjon utfører denne prosedyren også nøkkelbitpermutasjon i henhold til Tabell. 3.19 og 3.20.
Tabell 3.19
Tabell 3.20
Som et resultat av permutasjonen dannes det to 28-bits verdier C og D. Tabell 3.19 definerer utvalget av nøkkelbiter for C, tabell. 3,20 - for D.
Deretter utføres 16 runder med transformasjoner, som hver gir en av nøklene til rundene K t. I hver runde av nøkkelutvidelsesprosedyren utføres følgende handlinger:
1. Gjeldende verdier for C og D forskyves syklisk til venstre med et variabelt antall biter NS. For runde 1, 2, 9 og 16 NS= 1, i de resterende rundene utføres et 2-bits syklisk skift.
2.C og D er sammenkoblet til en 56-bits verdi, som CP-krympende permutasjon brukes på, noe som resulterer i en 48-bits rundnøkkel K (. Den krympende permutasjonen utføres i henhold til tabell 3.21.
Tabell 3.21
Når du dekrypterer data, kan du bruke samme prosedyre for nøkkelutvidelse, men bruke de runde nøklene i omvendt rekkefølge. Det er et annet alternativ: i hver runde av nøkkelutvidelsesprosedyren, i stedet for et syklisk venstreskift, utfør et syklisk høyreskift med n biter, hvor rc '= 0 for den første runden, og' = 1 for runde 2, 9, 16 og n = 2 for de resterende rundene ... En slik nøkkelutvidelsesprosedyre vil umiddelbart gi de runde nøklene som er nødvendige for dekryptering.
Det skal sies at muligheten til å utføre nøkkelutvidelse "on the fly" (spesielt hvis denne muligheten eksisterer både under kryptering og dekryptering) anses som en fordel med krypteringsalgoritmer, siden nøkkelutvidelsen i dette tilfellet kan utføres parallelt med kryptering og ikke kaste bort minne på å lagre nøklene til andre runder enn den nåværende.
