| Kommunikationsteori i hemmelige systemer | |
|---|---|
| Kommunikationsteori om hemmeligholdelsessystemer | |
| Forfatter | Claude Shannon |
| Genre | Forskningsartikel |
| Originalsprog | engelsk |
| Original udgivet | 1949 |
| Forlægger | Bell System Teknisk Journal |
| sider | 59 |
| Tekst på et tredjepartswebsted | |
Communication Theory of Secrecy Systems er en artikel af den amerikanske matematiker og ingeniør Claude Shannon , publiceret i Bell System Technical Journal i 1949 .
I den blev de grundlæggende begreber i teorien om kryptografi defineret for første gang [1] , den perfekte kryptografiske styrke af Vernam-chifferet blev bevist , konceptet om unikhedsafstanden blev defineret , problemet med sprogredundans blev overvejet, og ideen om at skabe chiffer baseret på flere erstatnings- og permutationscyklusser blev foreslået . Det menes, at det var med fremkomsten af denne artikel, at kryptografi, som tidligere blev betragtet som en kunst, begyndte at udvikle sig som en videnskab [2] [3] [4] .
Fra begyndelsen af 1940'erne arbejdede Claude Shannon for US National Defense Research Committee.. Hos Bell Labs , et forskningscenter inden for blandt andet telekommunikation og elektroniske systemer, forskede han inden for informationsteori og kryptografi , især spørgsmål om offentlig kommunikationssikkerhed [5] [6] .
Den 1. september 1945 , som et resultat af hans udvikling, blev en hemmelig rapport " A Mathematical Theory of Cryptography " udgivet . Blandt dem, som den var rettet til, var Lloyd Espenshid, Harold Stephen Black, Frederick Britton Llewellyn, Harry Nyquist , Ralph Hartley , John Robinson Pierce , Hendrik Wade Bode, Walter Shewhart og Sergei Aleksandrovich Shchelkunov [7] [8] .
Tre år senere udkom Shannons værk A Mathematical Theory of Communication , som anses for grundlæggende i informationsteorien [5] . I oktober 1949 publicerede Bell System Technical Journal en artikel om kryptografi af Claude Shannon, Communication Theory of Secrecy Systems . Sidstnævnte, såvel som tidligere i "Mathematical Theory of Communication", omfattede en væsentlig del af de konceptuelle udviklinger, der tidligere blev præsenteret i den hemmelige rapport "Mathematical Theory of Cryptography". I begge artikler blev der udviklet et matematisk apparat til de tilsvarende systemer [5] [7] .
Bell Labs arbejdede på hemmelige systemer. Jeg arbejdede med kommunikationssystemer og blev også udpeget til nogle af de udvalg, der studerede krypteringsteknikken. Arbejdet med begge matematiske teorier - kommunikation og kryptografi - har foregået samtidigt siden 1941. Man kan ikke sige, at den ene blev afsluttet før den anden - begge var så tætte, at de ikke kunne adskilles.Claude Shannon [9] [5]
Oversættelsen af artiklen "Theory of Communication in Secret Systems" til russisk blev lavet af professor Vladlen Fedorovich Pisarenko og placeret i samlingen af oversættelser af Claude Shannons artikler "Works on Information Theory and Cybernetics", udgivet på initiativ af Andrei Nikolaevich Kolmogorov i 1963 [10] .
Claude Shannons artikel "Communication Theory in Secret Systems" er opdelt i tre hoveddele: "The Mathematical Structure of Secret Systems", "Theoretical Secrecy" og "Practical Secrecy".
I artiklens første del introduceres en formel definition af et kryptosystem ( symmetrisk kryptosystem ), bestående af en meddelelseskilde, en nøglekilde, ciphers, en meddelelse, en nøgle, et kryptogram og en modstander cipher. Der defineres en krypteringsfunktion, der afhænger af den originale besked og nøgle, en dekrypteringsproces for modtageren af beskeden, som består i at beregne den kortlægning, der er det omvendte af kryptering, og en dekrypteringsproces for modstanderen - et forsøg på at bestemme original meddelelse, kun kender kryptogrammet og a priori sandsynligheder for forskellige nøgler og meddelelser [4] [ 11] [12] [13] .
Forfatteren foreslog også en repræsentation af kryptosystemet i form af en todelt graf , i hvis toppunkter er mulige meddelelser og mulige kryptogrammer, og hver krypteringsnøgle er forbundet med et sæt kanter, der forbinder hver mulig meddelelse med dets tilsvarende kryptogram [14 ] [15] .
Der gives en matematisk beskrivelse af tidligere kendte cifre. Den simple substitutionsciffer , Vigenère cipher , digram , trigram og n-gram substitution , Playfair cipher , autokey cipher og fraktional cipher betragtes [16] [2] .
De vigtigste kriterier for evaluering af kryptosystemers egenskaber (styrke) i artiklen er: størrelsen (længden) af nøglen, kompleksiteten af krypterings- og dekrypteringsoperationer, muligheden eller umuligheden af at dekryptere meddelelsen af modstanderen på en enkelt måde, graden af indflydelse af fejl under kryptering og transmission på den modtagne meddelelse og graden af stigning i meddelelsens størrelse som følge af kryptering [17] . I slutningen af artiklen blev det bemærket, at i tilfælde af kryptering af en meddelelse, der er sammensat i et naturligt sprog, er det umuligt at forbedre den samlede vurdering af kryptosystemet ved at forbedre det i alle de anførte parametre samtidigt [18] .
Strukturen af algebraen af hemmelige systemer (chifferalgebra) med to hovedoperationer til at kombinere cifre foreslås: vægtet sum (tilføje cifre med vægte i form af cifferudvælgelsessandsynligheder) og produkt (successiv anvendelse). Nye cifre foreslås opnået ved at kombinere en vægtet sum og et produkt af forskellige cifre [13] .
Anden del af artiklen definerer begrebet perfekt sikkerhed for et kryptosystem , et system hvor den oprindelige besked og kryptogrammet er statistisk uafhængige [3] [4] .
Den perfekte sikkerhed ved Vernam-chifferet ( engangs-chifferblok ) [4] er blevet bevist . Upålideligheden af nogle cifre er vist på eksemplet med Cæsar-chifferet , hvor hyppigheden af forekomst af tegn, der svarer til tegnene i den oprindelige meddelelse, ikke afhænger af nøglen [6] .
Når man overvejer en tilfældig chiffer, blev begrebet unikhedsafstand introduceret - det mindste antal kryptogramsymboler, hvormed nøglen kan bestemmes entydigt [3] [19] . Problemet med sprogredundans bemærkes også , som består i, at redundans, som er et sæt af betingelser pålagt meddelelsens tegn, giver yderligere muligheder for at dekryptere kryptogrammet af fjenden [5] [20] .
Konceptet med et ideelt sikkert kryptosystem, som har en uendelig unikhedsafstand, introduceres. Et særligt (mere strengt) tilfælde af sådanne systemer er fuldstændig hemmelige systemer. Deres karakteristiske træk er, at det ideelle kryptosystem bevarer usikkerhed selv med en vellykket dekrypteringsoperation af modstanderen [19] .
I artiklens tredje del er kryptosystemets ydeevne defineret som en funktion, der afhænger af antallet af kendte symboler i kryptogrammet og er lig med den gennemsnitlige mængde arbejde, der er brugt på at finde krypteringsnøglen [3] . Denne funktion har nogle ligheder med begrebet beregningsmæssig kompleksitet af en algoritme [21] .
Muligheden for at dechifrere chifferen ved hjælp af en statistisk analyse af forekomsten af chiffertekstsymboler og metoden for sandsynlige ord overvejes. Ifølge teorien beskrevet i artiklen kan modstanderen i dekrypteringsprocessen bruge nogle statistiske egenskaber ved sproget. Det er vist, at f.eks. hvis sproget i den oprindelige besked er kendt, er det for nogle cifre muligt at åbne en tekst bestående af flere dusin tegn. Som et eksempel på de mest almindelige ord/sætninger i det engelske sprog citerede forfatteren konstruktionerne “ the ”, “ and ”, “ that ” og stavelsen “ -tion ”, og som en kombination af symboler “ qu ”, som er direkte relateret til spørgsmålet om sproglig redundans , der behandles i anden del af artiklen [5] [20] .
Det blev foreslået at bruge flere lag (cyklusser) af substitutioner og permutationer, som efterfølgende blev brugt i konstruktionen af blokcifre . I det originale papir kaldte Shannon disse metoder for " forvirring " (sammenfiltring, svarende til substitution) og " diffusion " (spredning, svarende til permutation) [4] .
I bogen " Code Breakers " af David Kahn blev den opfattelse udtrykt, at mens artiklen " Matematical Theory of Communication " fungerede som begyndelsen på udviklingen af informationsteori , betragtede artiklen "Theory of Communication in Secret Systems" den videnskabelige essens. af kryptografi . Forfatterens store bidrag bemærkes ved at påpege sproglig redundans som grundlaget for kryptoanalyse, og at det var Shannon, der først introducerede de grundlæggende principper for dekryptering. En anden vigtig idé i Shannons artikel i Kahns bog er introduktionen af unikhedsafstanden [9] .
Whitfield Diffie og Martin Hellman i artiklen "New Directions in Cryptography" (eng. New Directions in Cryptography ) udtalte, at Shannon i "The Theory of Communication in Secret Systems" beviste den perfekte hemmeligholdelse af en engangs chifferblok , men dens brug er en praktisk talt urealiserbar opgave til de fleste anvendte formål [22] . Det er blevet hævdet, at denne artikel af Diffie og Hellman førte til et gennembrud inden for kryptografi, fordi det blev vist, at parterne kunne opnå en delt hemmelig nøgle ved hjælp af en ubeskyttet kommunikationskanal, hvilket ikke var tilfældet i den kryptografi, der er beskrevet i Shannons papir . 4] .
Bruce Schneier , i Applied Cryptography, bemærkede, at indtil 1967 var litteraturen om kryptografi tom, med en sjælden undtagelse, som er artiklen "Communication Theory in Secret Systems" [19] .
Handbook of Applied Cryptography bemærkede, at artiklen er en af de bedste grundlæggende artikler om informationssikkerhed og er især bemærkelsesværdig, at den kombinerer den praktiske og teoretiske side af spørgsmålet, introducerer de grundlæggende ideer om redundans og entydighedsafstand [23] .
" Encyclopedia of Cryptography and Security " angiver virkningen af ideen foreslået i dette papir på brugen af flere cyklusser, bestående af udskiftning og permutation, på skabelsen af blokcifre og SP-nettet . Også af særlig betydning er Shannons model af et kryptosystem og Vernam-chifferets perfekte hemmeligholdelsessætning . Derudover er en af de mest citerede maksimer inden for kryptografi antagelsen fra første del af artiklen: " Fjenden kender det system, der bliver brugt" [4] .