Homofon substitution

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 19 mars 2022; kontroller kräver 2 redigeringar .

Homofoniskt substitutionschiffer är ett  substitutionschiffer där varje tecken i klartexten ersätts med ett av flera tecken i alfabetchifferet, och antalet ersättningstecken för en bokstav är proportionell mot frekvensen av denna bokstav. Detta gör att du kan dölja den verkliga förekomsten av en given bokstav i chiffertexten [1] .

Historik

Kryptering med metoden homofonisk substitution har varit känd sedan 1400-talet [2] .

Simeone de Crema 1401 använde först homofontabeller för den enhetliga frekvensen av vokaler med hjälp av substitution med flera värden [3] .

Leon Battista Alberti beskrev i sin Treatise on Ciphers , publicerad 1466, ett substitutionschiffer där flera element tilldelas en bokstav [3] .

Traditionella monoalfabetiska substitutionschiffer var fortfarande relevanta på 1600-talet för triviala uppgifter som att kryptera personlig korrespondens för att dölja information från tjänare eller skydda sin dagbok från en fru eller man. Monoalfabetisk substitution ger ett enkelt och snabbt skydd av information från personer okunniga om kryptoanalys . Men för mer allvarliga syften var sådan kryptering inte längre säker, så det blev nödvändigt att leta efter ett chiffer som skulle vara svårare att bryta än ett monoalfabetiskt substitutionschiffer , men som skulle vara lättare att använda än ett polyalfabetiskt substitutionschiffer . Flera varianter av sådana chiffer presenterades, den mest effektiva lösningen på detta problem var ett homofonisk substitutionschiffer, eller homofonisk substitution [1] .

Kryptering

Låt vara  ett tecken i alfabetet som används i klartext. För varje , komponerar vi uppsättningen av symboler , så att för olika symboler och uppsättningarna och inte skär varandra. Vanligtvis är elementen i en mängd siffror. I homofonisk kryptering tas antalet ersättningar för varje tecken i proportion till sannolikheten för att tecknet ska förekomma i klartexten. I kryptering väljs en ersättning för ett klartexttecken antingen slumpmässigt (slumptalsgenerator) eller på ett specifikt sätt (t.ex. i ordning). För att memorera bokstäverna som oftast finns i texter använder de kombinationer av bokstäverna "senovaliter" och "tetrishonda" för ryska respektive engelska. Dessa kombinationer liknar ord och är därför lätta att komma ihåg [4] .

Sannolikheten för utseendet av bokstäver i det ryska alfabetet
Brev Sannolikhet
MEN 0,069
B 0,013
PÅ 0,038
G 0,014
D 0,024
HENNE 0,071
OCH 0,007
W 0,016
Brev Sannolikhet
Och 0,064
Y 0,010
Till 0,029
L 0,039
M 0,027
H 0,057
O 0,094
P 0,026
Brev Sannolikhet
R 0,042
FRÅN 0,046
T 0,054
På 0,023
F 0,003
X 0,008
C 0,005
H 0,012
Brev Sannolikhet
W 0,006
SCH 0,004
Kommersant 0,001
S 0,015
b 0,013
E 0,002
YU 0,005
jag 0,017

(*) (Tabell visar resultaten av en frekvensanalys av litterära och vetenskapliga texter med en total volym på mer än 1 miljon tecken. Under samma förhållanden är sannolikheten för ett "gap" 0,146.)

Eftersom sannolikheten för att stöta på den mest sällsynta bokstaven är ungefär en tusendel, kan kryptering med den homofoniska klartextersättningsmetoden utföras med en chifferersättningstabell, där varje chifferersättning består av 3 siffror och deras totala antal är 1000. I detta fall, för det mest sällsynta elementet, exakt ett tecken [4] .

Ett exempel på en sådan tabell visas nedan.

Nej. MEN B PÅ … E … O P R … E YU jag
ett 012 128 325 … 037 … 064 058 265 … 501 064 106
2 659 556 026 … 700 … 149 073 333 … 248 749 098
… … … … … … … … … … … … …
17 111 061 … 144 … 903 656 476 … 453
… … … … … … … … … …
38 366 804 … … … 123 865 …
… … … … … … … …
69 095 … 010
… … …
71 541 268
… …
94 479

Vissa fält i tabellen är tomma, eftersom antalet ersättningar för varje tecken i källalfabetet är olika. Till exempel kan detta fragment användas för att kryptera ordet "VERA". Varje bokstav i det ursprungliga meddelandet, i det här fallet ett ord, ska ersättas med en av chifferersättningarna i kolumnen för den bokstaven. Om bokstäverna ersätts med sådana chifferersättningar: "B" - , "E" - , "P" - , "A" - , så har det krypterade ordet formen av en numerisk sekvens " " [4] .

Kryptanalys

Homofonisk substitutionskryptering är det enklaste försvaret mot frekvensanalys av kryptoattacker, eftersom en av dess ersättningar väljs slumpmässigt när en bokstav i källtexten krypteras. Med denna krypteringsmetod visas chiffertextelement med lika stor sannolikhet, så den vanliga beräkningen av frekvensen av bokstäver är värdelös för en kryptoanalytiker . Frekvenskrypteringsanalys baserad på att räkna par, trillingar av bokstäver eller ord kommer dock att bli mer framgångsrika. Till exempel är artikeln den vanligaste i engelsk klartext. Dessutom, efter bokstaven q, finns det bara en bokstav - u. Sålunda, när du märker några kombinationer av tecken, kan du dechiffrera en del av texten och sedan, enligt den mottagna informationen, återställa resten [5] [4] .

För närvarande dekrypterar moderna datorer texter krypterade med homofonisk substitution på några sekunder [6] .

Funktioner av chiffer

Det speciella med denna metod är att chifferersättningar inte upprepas. Detta betyder att om bokstaven "Ф" har 3 chifferersättningar, till exempel , och , då chifferersättningarna , och betecknar endast bokstaven "Ф" [7] .

Ett homofoniskt chiffer kan se ut som ett polyalfabetiskt ( polyalfabetiskt ) chiffer, eftersom varje bokstav i alfabetet kan krypteras på många sätt, men i själva verket är ett homofoniskt substitutionschiffer en typ av monoalfabetisk ( monalfabetisk ) chiffer. Den främsta anledningen till att ett homofoniskt chiffer är monoalfabetiskt är att chifferalfabetet inte förändras under hela krypteringsprocessen [7] .

Karakteristika för chiffer

Det homofoniska substitutionschifferet kännetecknas av två parametrar - längden på chiffertexten och komplexiteten , där  är antalet olika tecken i chifferalfabetet som används i denna chiffertext. Uppenbarligen är komplexiteten begränsad . När komplexiteten hos ett chiffer är tillräckligt nära 0, är ​​chiffret ett enkelt substitutionschiffer. Vid ett visst värde blir fördelningen av chifferalfabettecken enhetlig (ca 0,3 för en chiffertext på 200 tecken), men om du fortsätter att öka komplexiteten kan du nå det gränsvärde vid vilket det inte längre är möjligt att entydigt dekryptera texten. Homofoniska substitutioner av högre ordning har samma chiffertext för olika klartexter, därför, i de fall där chiffertextens längd är mindre än unikhetsavståndet , är det omöjligt att förstå vilken version av klartexten som kommer att vara korrekt [8] .

Andra ordningens homofonisk substitution

En andra ordningens homofonisk substitution är en homofonisk substitution så att chiffertexten kan dekrypteras på två sätt. Till exempel kan " " med hjälp av en nyckel (nyckel 1) dekrypteras som "MAMA SOAPED THE RAM", och med hjälp av den andra nyckeln (nyckel 2) som "AMUR WASHED URAL". Båda klartexterna har inte så stor betydelse, men de illustrerar väl att helt olika budskap kan döljas bakom samma chiffertext [9] .

Nyckel 1
M 13, 2
MEN 9, 32, 10
S 19
L 27
R åtta
På 3
Nyckel 2
M 9, 19
MEN 13
S 27
L tio
R 32
På 8.2

Nyckelgenerering och kryptering

För att förstå hur ett sådant chiffer kan erhållas, låt oss skriva våra lika långa klartexter under varandra.

M MEN M MEN M S L MEN R MEN M På
MEN M På R På M S L På R MEN L

Observera nu att om vi läser den resulterande posten inte i rader, utan i kolumner, kommer vi att få 9 olika digram (bokstäverpar): "MA", "AM", "MU", "AP", "YM", " LY", "AL", "RU", "UL". Alla digram utom "MA", "MU" och "AR" upprepas en gång. Fyll sedan matrisen slumpmässigt (6 är antalet bokstäver i vanliga textalfabet; om hela alfabetet används i texten kommer vi att ha en matris eller för det ryska respektive engelska alfabetet) med siffror, till exempel, från 1 till 36 [10] .

MEN L M R På S
MEN 21 tio 9 32 26 34
L 16 6 7 fjorton trettio 27
M 13 arton 23 28 2 5
R fyra femton 36 22 åtta 35
På 25 3 17 29 tjugo 33
S ett 31 19 24 12 elva

Varje rad och varje kolumn mappas till ett av de alfabetiska tecknen i den första respektive andra klartexten. Nu motsvarar varje digram ett visst nummer (vid skärningspunkten mellan motsvarande rader och kolumner), därför kan vi kryptera texterna genom att ersätta digramet med motsvarande nummer. En matris med siffror som motsvarar digram spelar rollen som nyckel i detta fall. För att hålla hela matrisen hemlig är den uppdelad i två matriser: en erhålls genom att sortera elementen i raderna, den andra genom att sortera kolumnerna och transponera . Vid utgången kommer vi att ha två matriser, i var och en av vilka elementen i raderna är sorterade i stigande (fallande), och en matris kan användas för att bara få en klartext. Till exempel tas texter med samma alfabet, eftersom det antas att i det allmänna fallet kommer hela alfabetet att användas för att skapa ett chiffer och att chiffret ska täcka alla möjliga digram [11] .

Nyckel för den första mottagaren
MEN 9 tio 21 26 32 34
L 6 7 fjorton 16 27 trettio
M 2 5 13 arton 23 28
R fyra åtta femton 22 22 36
På 3 17 tjugo 26 29 33
S ett elva 12 19 24 31
Nyckel för den andra mottagaren
MEN ett fyra 13 16 22 25
L 3 6 tio femton arton 31
M 7 9 17 19 23 36
R fjorton 22 24 28 29 32
På 2 åtta 12 tjugo 26 trettio
S 5 elva 27 33 34 35

Homofonisk substitution med minimal redundans

För att förbättra metoden kan den minsta redundansen för chifferalfabetet uppnås. Algoritm

  1. Vi kommer att använda varje nummer endast en gång. Om digramet upprepas, ta ett nytt nummer för det, som kommer att vara större än det maximala tillgängliga i alfabetet. I vårt fall får vi chiffertexten " "
  2. När krypteringen är klar tar du bort alla oanvända element från matrisen
  3. En chifferbokssida med minimal redundans kan erhållas genom att ersätta alla siffror med olika slumptal. Självklart kan vi i det här fallet få chiffertexten " ". Digramnyckeltabellen och nycklar för var och en av mottagarna för en sådan uppsättning meddelanden kommer att reduceras till det minsta möjliga [11] .
MEN L M R På S
MEN åtta 2 4, 10
L 7
M 1, 11 3, 5
R 9
På 12
S 6
Nyckel 1
MEN 2, 4, 8, 10
L 7
M 1, 3, 5, 11
R 9
På 12
S 6
Nyckel 2
MEN 1, 11
L 8, 12
M 2, 6
R 4, 10
På 3, 5, 9
S 7

Om du läser bokstäverna i den ordning som anges av siffrorna som motsvarar varje bokstav får du klartexten. På grund av detta blir användningen av ett sådant chiffer omöjligt, eftersom det räcker för en angripare att ha en nyckel för att få klartexten, utan att ens ha en privat text. Detta gör det meningslöst att minska textredundans. Å andra sidan har den tidigare använda matrisformen av andra ordningens homofoniska substitution ganska god kryptografisk styrka om hela alfabetet används. Två texter kommer att ge ( ) möjliga digram som inte upprepas mycket om inte texten är för stor. Som ett resultat kommer redundansen för krypterade meddelanden att vara låg, medan meddelandet kommer att använda ett stort antal olika tecken, vilket är allvarliga hinder för kryptoanalys [12] .

Anmärkningsvärda exempel

Kryptogrammen för den berömda Zodiac -seriemördaren är krypterade med ett homofoniskt substitutionschiffer. Ett av de två kryptogrammen har ännu inte dechiffrerats [13] .

Balkryptogram anses vara krypterade med ett första ordningens homofoniskt substitutionschiffer, och sannolikheten för att dechiffrera det andra kryptogrammet (det enda av de tre som kunde dechiffreras) på ett sådant sätt att man får en annan meningsfull text är den minsta [ 14] [15] .

Homofonisk substitution i naturen

Den genetiska koden är en homofonisk substitution, där aminosyror spelar rollen som klartextsymboler, och kodon  är trippel av nukleotider  - chiffertextsymboler [16] .

Anteckningar

  1. ↑ 1 2 Singh, 2007 , sid. 70.
  2. ↑ Kahn, 2000 , sid. 7.
  3. ↑ 1 2 Anisimov .
  4. ↑ 1 2 3 4 Singh, 2007 , sid. 71-72.
  5. ↑ Dolgov, 2008 , sid. 33.
  6. ↑ Schneier, 2002 , sid. 35.
  7. ↑ 1 2 Singh, 2007 , sid. 72.
  8. ↑ John C. King & Dennis R. Bahler. An algorithmic solution of sequental homophonic ciphers  (engelska)  = An algorithmic solution of sequental homophonic ciphers // Cryptologia: scientific journal. — Taylor & Francis, 1993. — Vol. 17. - S. 149. - ISSN 0161-1194 . - doi : 10.1080/0161-119391867827 . Arkiverad från originalet den 12 december 2020.
  9. ↑ Hammer, 1988 , sid. 12-13.
  10. ↑ Hammer, 1988 , sid. 13.
  11. ↑ 1 2 Hammer, 1988 , sid. fjorton.
  12. ↑ Hammer, 1988 , sid. 14-15.
  13. ↑ John C. King & Dennis R. Bahler. A framework for the study of homophonic ciphers in classical encryption and genetic systems  (engelska)  = A framework for the study of homophonic ciphers in classical encryption and genetic systems // Cryptologia: Journal. — Taylor & Francis, 1993. — Vol. 17. - P. 46. - ISSN 0161-1194 . - doi : 10.1080/0161-118891862747 . Arkiverad från originalet den 15 februari 2019.
  14. ↑ John C. King & Dennis R. Bahler. A framework for the study of homophonic ciphers in classical encryption and genetic systems  (engelska)  = A framework for the study of homophonic ciphers in classical encryption and genetic systems // Cryptologia: Journal. — Taylor & Francis, 1993. — Vol. 17. - P. 47. - ISSN 0161-1194 . - doi : 10.1080/0161-119391867755 . Arkiverad från originalet den 15 februari 2019.
  15. ↑ Carl Hammer. Andra ordningens homofoniska chiffer  (engelska)  = Andra ordningens homofoniska chiffer // Cryptologia: Journal. - Taylor & Francis, 1988. - Vol. 12. - P. 15-19. — ISSN 0161-1194 . - doi : 10.1080/0161-118891862747 . Arkiverad 8 maj 2020.
  16. ↑ John C. King & Dennis R. Bahler. A framework for the study of homophonic ciphers in classical encryption and genetic systems  (engelska)  = A framework for the study of homophonic ciphers in classical encryption and genetic systems // Cryptologia: Journal. — Taylor & Francis, 1993. — Vol. 17. - S. 48-50. — ISSN 0161-1194 . - doi : 10.1080/0161-119391867755 . Arkiverad från originalet den 15 februari 2019.

Litteratur

Länkar