En substitutionskryptering er en krypteringsmetode , hvor elementer af den originale almindelige tekst erstattes med krypteringstekst i henhold til en eller anden regel. Tekstelementer kan være enkelttegn (den mest almindelige store og små bogstaver), bogstavpar, tredobbelte bogstaver, en kombination af disse tilfælde og så videre. I klassisk kryptografi er der fire typer substitutionsciffer [1] :
Som et alternativ til substitutionscifre kan man overveje permutationscifre . I dem er tekstens elementer omarrangeret i en anden rækkefølge end originalen, og selve elementerne forbliver uændrede. I modsætning hertil ændrer tekstens elementer i substitutionscifre ikke deres rækkefølge, men ændrer sig selv.
Brugen af substitutionscifre har sin oprindelse i Mesopotamien . For at skjule oplysninger om opskriften på fremstilling af glasur til keramik, erstattede forfatteren nogle af ordene med tal og kileskriftstegn . Den romerske kejser Gaius Julius Cæsar flyttede, da han skrev hemmelige beskeder, hvert bogstav i alfabetet med 3 positioner. Denne type substitutionsciffer blev senere opkaldt efter ham, Cæsar-chifferet . En anden ikke mindre berømt chiffer fra antikken , Atbash , blev brugt i Bibelen til at skabe skjulte budskaber. Hvert bogstav i ordet blev erstattet af dets spejlbillede i alfabetet [2] [3] .
En af de første krypteringsenheder anses for at være Aeneas lineal , når man bruger hvilken en lang tråd blev trådt gennem en spalte og derefter gennem huller lavet i linealen. Bogstaver svarende til dem var placeret ved siden af hullerne. Der blev bundet en knude på tråden på det sted, hvor den gik gennem hullet. Således blev teksten i beskeden erstattet af en række af afstande mellem knuderne. Denne enhed blev opfundet af den antikke græske kommandant Aeneas Tacticus i det 4. århundrede f.Kr. e. [4] [5]
Med brugen af frekvensanalyse til at bryde monoalfabetiske cifre i det 9. århundrede , blev det nødvendigt at ændre hyppigheden af forekomsten af tegn i almindelig tekst. Til dette formål begyndte man at bruge en monosonisk substitutionschiffer , hvis essens var sammenligningen af flere erstatningstegn med et bogstav i forhold til hyppigheden af dette brevs udseende i forskellige tekster. Antipave Clementius VII's sekretær Gabriel de Lavinda i det 15. århundrede var den første til at bruge homofoner for at sikre nogenlunde samme vokalfrekvens. Efter 65 år beskriver Leon Battista Alberti en-lyds substitutionscifferet i detaljer i sin bog Treatise on Ciphers . Hovedproblemet med spredningen af homofonisk substitution var behovet for at bruge et udvidet alfabet til at kryptere meddelelser. [6] [7] [8] [9]
Denne mangel blev fjernet med polyalfabetiske cifre , hvoraf den første blev beskrevet af den tyske munk Johann Trithemius . Ifølge metoden beskrevet i hans afhandling "Udskrivning" blev det næste bogstav erstattet af et tegn fra dets eget chifferalfabet, mens hvert næste alfabet blev hentet fra det forrige ved at skifte med et bogstav. Den polyalfabetiske ciffer beskrevet af Blaise de Vigenère i 1585 opnåede særlig popularitet . Et vilkårligt ord blev brugt som nøgle til chifferen. Sættet af chifferalfabeter, der svarer til et givet ord, blev bestemt ud fra Vigenère-tabellen. [ti]
I 1854 udgav den engelske fysiker Charles Wheatstone et polygram -chiffer , senere opkaldt efter Lord Lyon Playfair. Denne chiffer erstatter bogstavpar (bigram) med enkelte tegn, hvilket markant øger dens kryptografiske modstand mod frekvensanalyse. [elleve]
Med fremkomsten af computere faldt polyalfabetiske og polygramcifre i baggrunden, og de blev erstattet af nye, mere sikre blokcifre . [12]
I simple substitutionscifre udføres substitution på kun ét enkelt tegn. For en visuel demonstration af en simpel substitutionscifre er det nok at skrive det samme alfabet under et givet alfabet , men i en anden rækkefølge eller for eksempel med en offset. Alfabetet skrevet på denne måde kaldes substitutionsalfabetet.
Et simpelt substitutionsciffer, der bruges til det hebraiske alfabet , og hvorfra det har sit navn. Kryptering sker ved at erstatte det første bogstav i alfabetet med det sidste, det andet med det næstsidste ( alef (første bogstav) erstattes af tav (sidste), bet (andet) erstattes af shin (næstsidste); fra disse kombinationer chifferen har fået sit navn). [13] Atbash-ciffer for det engelske alfabet:
Kilde alfabet: | ABCDEFGHIJKLMNOPQRSTU VWXYZ |
Erstatningsalfabet: | ZYXWVUTSRQPONMLKJIHGF EDCBA |
Cæsar-chifferet er en af de ældste cifre. Under kryptering erstattes hvert bogstav af et andet, som er adskilt fra det i alfabetet med et fast antal positioner. Chifferen er opkaldt efter den romerske kejser Gaius Julius Cæsar , som brugte den til hemmelig korrespondance. En naturlig udvikling af Cæsar-cifferet var Vigenère-cifferet . Kryptering ved hjælp af en nøgle :
Kilde alfabet: | ABCDEFGHIJKLMNOPQRSTU VWXYZ |
Erstatningsalfabet: | EFGHIJKLMNOPQRSTUVWXY ZABCD |
Et moderne eksempel på en Cæsar-chiffer er ROT13 . Det skifter hvert tegn i det engelske alfabet med 13 positioner. Brugt i internetfora , som et middel til at skjule spoilere , hovedpunkter, puslespilsløsninger og stødende materiale fra tilfældig visning. [fjorten]
Kryptering ved hjælp af et kodeordEn chiffer, der bruger et kodeord, er en af de nemmeste at implementere og dekryptere. Tanken er, at der vælges et kodeord , som skrives foran, derefter skrives resten af bogstaverne i alfabetet ud i deres rækkefølge. Kryptér ved hjælp af kodeordet WORD.
Kilde alfabet: | ABCDEFGHIJKLMNOPQRSTU VWXYZ |
Erstatningsalfabet: | WORDABCEFGHIJKLMNPQST UVXYZ |
Som vi kan se, når vi bruger et kort kodeord, får vi en meget, meget enkel erstatning. Vi kan bruge et ord med gentagne bogstaver som et kodeord, men kun hvis vi fjerner de ekstra bogstaver fra kodeordet, ellers vil dette føre til dekrypteringsuklarhed, det vil sige, at det samme bogstav i chifferteksten svarer til to forskellige bogstaver i det originale alfabet. [femten]
Traditionelt er chiffertekst skrevet i blokke (et andet navn for "grupper") på 5 tegn uden hensyntagen til tegnsætning og mellemrum. Dette hjælper med at undgå fejl, når du sender en krypteret besked og giver dig mulighed for at skjule ordgrænser i den originale tekst. Blokken indeholder 6 tegn, da det før var praktisk at sende dem via telegraf .
Den største ulempe ved denne krypteringsmetode er , at de sidste bogstaver i alfabetet (som har lave frekvensanalysekoefficienter ) har en tendens til at blive ved enden. En mere sikker måde at bygge et erstatningsalfabet på er at lave en kolonneflytning (kolonneflytning) i alfabetet ved hjælp af et nøgleord, men dette gøres ikke ofte.
Selvom antallet af mulige nøgler er meget stort (26! = 288,4 ), kan denne form for chiffer let brydes. Forudsat at meddelelsen er af tilstrækkelig længde (se nedenfor), kan kryptanalytikeren gætte betydningen af nogle af de mest almindelige bogstaver baseret på en analyse af frekvensfordelingen af tegn i chifferteksten. Dette giver dig mulighed for at danne separate ord, som kan bruges på forhånd for at opnå en mere komplet løsning senere (se frekvensanalyse). I henhold til det engelske sprogs unikke afstand , skulle 27,6 bogstaver fra chifferteksten være nok til at bryde den simple substitutionsciffer. I praksis er omkring 50 tegn normalt nok til at bryde, selvom nogle chiffertekster kan brydes med færre tegn, hvis der findes ikke-standardstrukturer. Men med en ensartet fordeling af tegn i teksten kan det være nødvendigt med meget længere chiffertekster for at knække.
Et tidligt forsøg på at øge kompleksiteten af frekvensanalysen af chiffertekster var at maskere de faktiske frekvenser af almindelige teksttegn ved hjælp af homofoni. I disse cifre svarer bogstaverne i det originale alfabet til mere end ét tegn fra erstatningsalfabetet. Normalt får de højest hyppige kildeteksttegn flere ækvivalenter end de sjældnere tegn. Således bliver fordelingen af frekvenser mere ensartet, hvilket i høj grad komplicerer frekvensanalyse [17] .
Da udskiftningsalfabetet krævede mere end 26 tegn, har der været behov for udvidede alfabeter. En af de enkleste løsninger er at erstatte alfabetet med tal . En anden metode består af simple ændringer af et eksisterende alfabet: store bogstaver , små bogstaver , omvendte tegn osv. Mere kunstneriske, men ikke nødvendigvis mere pålidelige, ville være homofoniske cifre, der bruger fuldstændigt opfundne (fiktive) alfabeter (såsom chifferen i en bog E. Poe's "Gold Bug" eller " The Voynich Manuscript ". Disse cifre er dog ikke eksempler på homofonisk substitution).
Et ciffer udstedt af en middelalderlig embedsmand, som er en lille bog med store homofoniske substitutionstabeller. Chifferen var oprindelig begrænset til navnene på datidens vigtige personer, derfor fulgte chifferens navn; i senere udgaver blev denne chiffer suppleret med en lang række almindelige ord og stednavne. På grundlag af denne "nomenclator" blev Rossignols Store Cipher kompileret, brugt af kong Ludvig XIV af Frankrig . Efter at denne chiffer var ophørt med at blive brugt, blev de franske arkiver lukket i flere hundrede år.
"Nomenclatorer" var standarden for diplomatisk korrespondance, spionmeddelelser og var hovedmidlet til anti -politisk sammensværgelse fra begyndelsen af det 15. århundrede til slutningen af det 18. århundrede. Selvom regeringens kryptoanalytikere systematisk knækkede "nomenklatatorerne" i midten af det sekstende århundrede. Den sædvanlige vej ud af denne situation var at øge mængden af borde. Men i slutningen af det attende århundrede, da systemet begyndte at gå ud af brug, havde nogle "nomenklatorer" op til 50.000 tegn. Men ikke alle "nomenklatorer" var brudt.
Great Cipher of RossignolAntoine Rossignol og hans søn Bonaventure Rossignol opfandt den store chiffer , som brugte 587 forskellige numre. [18] Chifferen var så stærk, at ingen i mange århundreder kunne bryde den, indtil den blev gjort af den franske hærofficer, kryptograf Etienne Bazery i 1893, ved at bruge eksemplet med et brev fra krigsministeren Louvois til kong Ludvig XIV . . Han indså, at hvert tal ikke kodede ét bogstav, men en hel stavelse . Baseri antog, at sekvensen 124-22-125-46-345 kodede ordet "les ennemis" (fjender), og ud fra denne information var han i stand til at tyde hele teksten.
BogchifferEn bogciffer er en ciffer, hvor nøglen er en bog eller et lille stykke tekst . Hovedkravet vil være, at begge korrespondenter ikke blot har samme bog, men også samme oplag og udgave. Traditionelt fungerer bogcifre ved at erstatte ord i den originale tekst med placeringen af de samme ord i bogen. Dette vil virke, indtil der stødes på et ord, der ikke er i bogen, på hvilket tidspunkt meddelelsen ikke kan kodes. [19] En alternativ tilgang, der omgår dette problem, er at erstatte individuelle tegn i stedet for ord. Denne metode har dog en bivirkning: chifferteksten bliver meget stor (normalt bruges 4 til 6 cifre til at kryptere hvert tegn eller stavelse).
En yderligere fortsættelse af simple substitutionscifre er polyalfabetiske cifre. Abu Al-Kindi viste i sine værker, at almindelige monoalfabetiske cifre er ret nemme at frekvense kryptering og var den første til at foreslå brugen af polyalfabetiske cifre. I Europa blev sådanne cifre først beskrevet i 1467 af den italienske arkitekt Leon Battista Alberti . I det 16. århundrede præsenterede den tyske abbed Johann Trithemius i sin bog Shorthand et polyalfabetisk krypteringsskema i form af en tabel. En mere kompleks version ved hjælp af blandede alfabeter blev beskrevet i 1563 af Giambattista della Porta i hans bog De Furtivis Literarum Notis (latin: "Om individuelle bogstavers skjulte betydning"). Essensen af polyalfabetiske ciphers ligger i den gentagne anvendelse af forskellige simple substitutions ciphers til et vist antal bogstaver i den krypterede tekst. Det vil sige, at en af de simple substitutionscifre anvendes på hvert bogstav separat.
Vigenère-chifferet består af en sekvens af flere Cæsar-cifre med forskellige skiftværdier. Til kryptering kan en tabel med alfabeter kaldet tabula recta eller Vigenères firkant (tabel) bruges. Med hensyn til det latinske alfabet består Vigenère-tabellen af linjer på hver 26 tegn, hvor hver næste linje er forskudt med flere positioner. Der er således 26 forskellige Cæsar-cifre i tabellen. På forskellige stadier af kodningen bruger Vigenère-chifferet forskellige alfabeter fra denne tabel. Hvert trin af kryptering bruger forskellige alfabeter, valgt afhængigt af nøgleordets karakter. [20] Hvis nøgleordet for eksempel er 'CAT', så krypteres det første bogstav i klarteksten med alfabetet 'C', det andet 'A', det tredje 'T', det fjerde igen 'C' og snart.
EngangsnotesblokDenne type substitutionscifre er ret specifik. Det blev opfundet i slutningen af Første Verdenskrig af Gilbert Vernam . Claude Shannon beviste matematisk sin absolutte kryptografiske styrke i sit papir fra 1945. For at oprette en chiffertekst XOR-behandles klarteksten med en tast (kaldet engangsblok eller chifferblok). I dette tilfælde er brugen af en engangsblok i de fleste tilfælde upraktisk, da det kræves, at nøglen har samme størrelse som klarteksten. Det kræver også, at nøglen er helt tilfældig, kun bruges én gang og holdes hemmelig for alle undtagen modtager og afsender. I denne henseende er den kommercielle brug af Vernam-chifferet ikke så almindelig som offentlige nøgleordninger, og den bruges hovedsageligt til transmission af meddelelser af særlig betydning af offentlige myndigheder. [21]
I polygram substitutionscifre erstattes almindelige bogstaver ikke ét ad gangen, men i grupper. Den første fordel ved denne metode er, at frekvensfordelingen af grupper af bogstaver er meget mere ensartet end individuelle tegn. For det andet kræver produktiv frekvensanalyse en større størrelse af chifferteksten, da antallet af forskellige grupper af bogstaver er meget større end blot alfabetet.
Playfair-krypteringen er en manuel symmetrisk krypteringsteknik, der var banebrydende for brugen af bigram-substitution . Opfundet i 1854 af Charles Wheatstone , men opkaldt efter Lord Lyon Playfair, som introducerede denne chiffer i de britiske regeringstjenester. Chifferen sørger for kryptering af tegnpar (bigram) i stedet for enkelte tegn, som i substitutionskrypteringen og i mere komplekse Vigenère-chiffersystemer. [22] [23] Playfair-chifferet bruger en 5x5 matrix (for det latinske alfabet, for det kyrilliske alfabet er det nødvendigt at øge størrelsen af matrixen til 4x8), hvis celler er fyldt med et blandet alfabet (på engelsk tekster, er tegnet "Q" normalt udeladt for at reducere alfabetet, i andre versioner er "I" og "J" kombineret til én celle). Udskiftningen udføres derefter ved at repræsentere bigrammerne som to hjørner af et rektangel. De to andre hjørner i diagrammet bruges til kryptering (se hovedartiklen for flere detaljer). Playfair-cifferet blev brugt taktisk af det britiske militær i Anden Boerkrig og Første Verdenskrig og af australierne og tyskerne under Anden Verdenskrig . Grunden til at bruge Playfair-chifferet var, at det er ret hurtigt at bruge og ikke kræver noget specielt udstyr.
Hill CipherHill-chifferet, opfundet i 1929 af Lester S. Hill, er et polygram-ciffer, der kan bruge store grupper ved hjælp af lineær algebra . Hvert bogstav tildeles først et nummer. For det latinske alfabet bruges ofte det enkleste skema: A = 0, B =1, ..., Z=25. Blokken med n bogstaver behandles som en n-dimensionel vektor og ganges med en n × n matrix modulo 26. Matricens komponenter er nøglen og skal være tilfældige, forudsat at matrixen skal være inverterbar for at dekrypteringen kan foretages operation for at være mulig. [24] Hill-chifferet er sårbart over for klartekstangreb, fordi det bruger lineære operationer. Derfor skal nogle ikke-lineære operationer tilføjes for at øge den kryptografiske styrke. Kombinationen af lineære operationer, som i Hill-chifferet, og ikke-lineære trin førte til oprettelsen af et permutation-permutation-netværk (såsom Feistel-netværket ). Derfor kan moderne blokcifre fra et vist synspunkt betragtes som en type polygramcifre. [25]
Den berømte amerikanske kryptograf Bruce Schneier identificerer fire 4 hovedmetoder til kryptoanalyse: [26]
Lad os beskrive den kryptografiske styrke af substitutionscifre med hensyn til disse metoder.
Monoalfabetiske cifre brydes let ved hjælp af metoder til frekvensanalyse [6] .
Krypteringsanalyse af monosoniske substitutionscifre udføres ved at tælle hyppigheden af forekomsten af par og tripler af tegn [27] .
For at dekryptere polyalfabetiske cifre bruges Kasiski-metoden [28] .
Hill's polygram - chiffer kan brydes ved at beregne frekvenserne af tegnsekvenser [29] .
Givet en klartekst af tilstrækkelig længde er det trivielt at bryde monoalfabetiske og monolyd-cifre [30] .
For hurtigt at bryde polyalfabetiske cifre skal længden af klarteksten overstige nøglens længde [31] .
Alle substitutionscifre er sårbare over for angreb med valgt almindelig tekst undtagen engangspuden [32] .
Standard Hill-chifferet , der er sammensat af n lineære ligninger, kan brydes i den valgte klartekst ved at opsnappe n² par af meddelelses- og chifferteksttegn af en kryptoanalytiker. [25]
En af de første krypteringsenheder blev opfundet i det 15. århundrede og erstattede Cæsar-cifferet . Dens forfatter var den italienske arkitekt Leon Battista Alberti , som ydede et væsentligt bidrag til udviklingen af substitutionscifre. Denne enhed bestod af to kobberskiver af forskellig størrelse, fastgjort med en nål. Et alfabet blev påført langs kanterne af hver disk. Begge diske kunne rotere uafhængigt af hinanden og dermed matche bogstaverne i klartekst og chiffertekst. Alberti-skiven blev meget brugt i fem århundreder, herunder under den amerikanske borgerkrig [33] .
I begyndelsen af det 20. århundrede, efter radioens opfindelse, blev det nødvendigt at udvikle krypteringsmaskiner til militær og kommerciel brug. Som grundlag for disse enheder blev der brugt polyalfabetiske substitutionscifre, såvel som princippet om driften af krypteringsdisken [34] .
For at opnå et krypteret signal blev der brugt en hul skive med kontakter på begge sider. Teksten opnået som et resultat af kryptering afhang af kommuteringen af disken og dens vinkelposition. Denne type krypteringsenheder blev efterfølgende kaldt roterende maskiner [34] [35] .
Roterende maskiner blev brugt af forskellige lande under Anden Verdenskrig . De mest berømte af dem var: den amerikanske bil SIGABA , den tyske ENIGMA , den engelske TYPEX og den japanske PURPLE. [36]
Roterende krypteringssystemer havde to typer nøgler. Lodning mellem rotorens kontakter indstiller en permanent nøgle. For at erstatte permanente nøgler var det nødvendigt at opgradere alle frigivne krypteringsmaskiner af denne model, hvilket er svært at implementere i praksis. Variable nøgler skiftede ofte hver dag og blev bestemt af et sæt rotorer og deres udgangsposition. [37]
På trods af forskydningen af substitutionscifre med blokcifre, bruges engangspuder stadig på statsniveau i vores tid. De bruges til at levere tophemmelige kommunikationskanaler. Ifølge rygter var telefonlinjen mellem lederne af USSR og USA krypteret ved hjælp af en engangsblok og eksisterer muligvis stadig. Engangsnotesblokke bruges af spioner fra forskellige stater til at skjule særlig vigtig information. Sådanne meddelelser kan ikke dekrypteres i mangel af en nøgle skrevet i en notesbog, uanset computerens computerkraft. [38] [12]