Homofonní substituce

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 19. března 2022; kontroly vyžadují 2 úpravy .

Homofonní substituční šifra je substituční šifra , ve které je každý znak otevřeného textu nahrazen jedním z několika znaků abecední šifry a počet náhradních znaků pro jedno písmeno je úměrný četnosti tohoto písmene. To umožňuje skrýt skutečnou frekvenci výskytu daného písmene v šifrovém textu [1] .

Historie

Šifrování metodou homofonní substituce je známé již od 15. století [2] .

Simeone de Crema v roce 1401 poprvé použil homofonní tabulky pro jednotnou frekvenci samohlásek pomocí vícehodnotové substituce [3] .

Leon Battista Alberti ve svém Pojednání o šifrách , publikovaném v roce 1466, popsal substituční šifru, ve které je několik prvků přiřazeno jednomu písmenu [3] .

Tradiční monoalfabetické substituční šifry byly v 17. století stále relevantní pro triviální úkoly, jako je šifrování osobní korespondence za účelem skrytí informací před služebnictvem nebo ochrana deníku před manželkou nebo manželem. Monoalfabetická substituce vytváří jednoduchou a rychlou ochranu informací před lidmi neznalými kryptoanalýzy . Pro vážnější účely však takové šifrování již nebylo bezpečné, a tak bylo nutné hledat šifru, kterou by bylo obtížnější prolomit než monoalfabetická substituční šifra , ale která by byla snáze použitelná než polyalfabetická substituční šifra . Bylo předloženo několik variant takových šifer, nejúčinnějším řešením tohoto problému byla homofonní substituční šifra, neboli homofonní substituce [1] .

Šifrování

Dovolit být znak abecedy, který se používá v otevřeném textu. Pro každý sestavíme sadu symbolů tak, aby se pro různé symboly a sady a neprotínaly. Prvky množiny jsou obvykle čísla. V homofonním šifrování se počet substitucí pro každý znak bere v poměru k pravděpodobnosti, že se tento znak objeví v otevřeném textu. V šifrování se náhrada za znak otevřeného textu volí buď náhodně (generátor náhodných čísel), nebo specifickým způsobem (např. v pořadí). K zapamatování písmen, která se v textech nejčastěji vyskytují, používají kombinace písmen „senovaliter“ a „tetrishonda“ pro ruštinu a angličtinu, resp. Tyto kombinace jsou podobné slovům, a proto jsou snadno zapamatovatelné [4] . $i$ $i$ $M_{i}$ $i$ $j$ $M_{i}$ $M_{j}$ $M_{i}$

Pravděpodobnost výskytu písmen ruské abecedy

Dopis	Pravděpodobnost
ALE	0,069
B	0,013
V	0,038
G	0,014
D	0,024
JEJÍ	0,071
A	0,007
Z	0,016

Dopis	Pravděpodobnost
A	0,064
Y	0,010
Na	0,029
L	0,039
M	0,027
H	0,057
Ó	0,094
P	0,026

Dopis	Pravděpodobnost
R	0,042
Z	0,046
T	0,054
V	0,023
F	0,003
X	0,008
C	0,005
H	0,012

Dopis	Pravděpodobnost
W	0,006
SCH	0,004
Kommersant	0,001
S	0,015
b	0,013
E	0,002
YU	0,005
já	0,017

(*) (Tabulka ukazuje výsledky frekvenční analýzy literárních a vědeckých textů o celkovém objemu více než 1 milion znaků. Za stejných podmínek je pravděpodobnost „mezery“ 0,146.)

Vzhledem k tomu, že pravděpodobnost setkání s nejvzácnějším písmenem je přibližně tisícina, lze šifrování pomocí metody homofonní substituce otevřeného textu provést pomocí substituční tabulky šifry, kde každá substituce šifry se skládá ze 3 číslic a jejich celkový počet je 1000. V tomto případě pro nejvzácnější prvek, přesně jeden znak [ 4] .

Příklad takové tabulky je uveden níže.

Ne.	ALE	B	V	…	E	…	Ó	P	R	…	E	YU	já
jeden	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

Některá pole v tabulce jsou prázdná, protože počet nahrazení každého znaku zdrojové abecedy je jiný. Tento fragment lze například použít k zašifrování slova „VERA“. Každé písmeno původní zprávy, v tomto případě slovo, by mělo být nahrazeno jednou z náhrad šifry ve sloupci pro dané písmeno. Pokud jsou písmena nahrazena takovými substitucemi šifry: "B" - , "E" - , "P" - , "A" - , pak má zašifrované slovo tvar číselné sekvence " " [4] . $325$ $700$ $865$ $095$ $325$ $700$ $865$ $095$

Kryptoanalýza

Homofonní substituční šifrování je nejjednodušší obranou proti kryptografickým útokům s frekvenční analýzou, protože při šifrování písmene zdrojového textu je náhodně vybrána jedna z jeho substitucí. Při tomto způsobu šifrování se prvky šifrového textu objevují se stejnou pravděpodobností, takže běžný výpočet četnosti písmen je pro kryptoanalytika k ničemu . Úspěšnější však bude frekvenční kryptoanalýza založená na počítání dvojic, trojic písmen nebo slov. Například článek the je nejběžnější v anglickém prostém textu. Také za písmenem q je pouze jedno písmeno - u. Když si tedy všimnete některých kombinací znaků, můžete dešifrovat část textu a poté, podle obdržených informací, obnovit zbytek [5] [4] .

V současné době moderní počítače dešifrují texty zašifrované homofonní substitucí během několika sekund [6] .

Vlastnosti šifry

Zvláštností této metody je, že se záměny šifry neopakují. To znamená, že pokud písmeno "Ф" má 3 substituce šifry, například , a , pak substituce šifry , a označují pouze písmeno "Ф" [7] . $100$ $477$ $906$ $100$ $477$ $906$

Homofonní šifra může vypadat jako polyalfabetická ( polyalfabetická ) šifra, protože každé písmeno abecedy může být zašifrováno mnoha způsoby, ale ve skutečnosti je homofonní substituční šifra typem monoalfabetické ( monoalfabetické ) šifry. Hlavním důvodem, proč je homofonní šifra monoalfabetická, je to, že šifrová abeceda se během procesu šifrování nemění [7] .

Charakteristika šifry

Homofonní substituční šifra je charakterizována dvěma parametry - délkou šifrového textu a složitostí , kde je počet různých znaků šifrové abecedy použitých v tomto šifrovém textu. Složitost je samozřejmě omezená . Když je složitost šifry dostatečně blízká 0, je šifra jednoduchou substituční šifrou. Při určité hodnotě se rozložení znaků šifrové abecedy sjednotí (asi 0,3 pro šifrovaný text o 200 znacích), ale pokud budete pokračovat ve zvyšování složitosti, můžete dosáhnout hraniční hodnoty, při které již není možné jednoznačně dešifrovat text. Homofonní substituce vyšších řádů mají stejný šifrový text pro různé otevřené texty, proto v případech, kdy je délka šifrového textu menší než vzdálenost jedinečnosti , není možné pochopit, která verze otevřeného textu bude správná [8] . $N$ $M=N/L$ $L$ $0\leqslant M\leqslant 1$ $M$

Homofonní substituce druhého řádu

Homofonní substituce druhého řádu je homofonní substituce taková, že šifrový text lze dešifrovat dvěma způsoby. Například " " pomocí jednoho klíče (klíč 1) lze dešifrovat jako "MAMA SOAPED THE FRAME" a pomocí druhého klíče (klíč 2) jako "AMUR WASHED URAL". Oba otevřené texty nemají velký význam, ale dobře ilustrují, že za stejným šifrovým textem se mohou skrývat zcela odlišné zprávy [9] . $13$ $9$ $2$ $32$ $2$ $19$ $27$ $deset$ $osm$ $32$ $13$ $3$

Klíč 1

M	13, 2
ALE	9, 32, 10
S	19
L	27
R	osm
V	3

Klíč 2

M	9, 19
ALE	13
S	27
L	deset
R	32
V	8.2

Generování klíčů a šifrování

Abychom pochopili, jak lze takovou šifru získat, zapišme si pod sebe stejně dlouhé otevřené texty.

M	ALE	M	ALE	M	S	L	ALE	R	ALE	M	V
ALE	M	V	R	V	M	S	L	V	R	ALE	L

Nyní si všimněte, že pokud budeme číst výsledný záznam nikoli v řádcích, ale ve sloupcích, dostaneme 9 různých digramů (dvojic písmen): "MA", "AM", "MU", "AP", "YM", " LY" , "AL", "RU", "UL". Všechny digramy kromě "MA", "MU" a "AR" se jednou opakují. Dále náhodně vyplňte matici (6 je počet písmen v abecedě prostého textu; pokud je v textu použita celá abeceda, budeme mít matici nebo pro ruskou a anglickou abecedu) čísly, například, od 1 do 36 [10] . $6\cdot 6$ $33\cdot 33$ $26\cdot 26$

	ALE	L	M	R	V	S
ALE	21	deset	9	32	26	34
L	16	6	7	čtrnáct	třicet	27
M	13	osmnáct	23	28	2	5
R	čtyři	patnáct	36	22	osm	35
V	25	3	17	29	dvacet	33
S	jeden	31	19	24	12	jedenáct

Každý řádek a každý sloupec je mapován na jeden z abecedních znaků prvního a druhého otevřeného textu. Nyní každý diagram odpovídá určitému číslu (v průsečíku odpovídajících řádků a sloupců), takže nahrazením diagramu odpovídajícím číslem můžeme zašifrovat texty. Matice s čísly odpovídajícími diagramům hraje v tomto případě roli klíče. Aby byla úplná matice utajena, je rozdělena na dvě matice: jedna se získá seřazením prvků řádků, druhá setříděním sloupců a transponováním . Na výstupu budeme mít dvě matice, v každé z nich jsou prvky v řádcích seřazeny vzestupně (sestupně) a jednu matici lze použít k získání pouze jednoho otevřeného textu. Například se berou texty se stejnými abecedami, protože se předpokládá, že v obecném případě bude k vytvoření šifry použita celá abeceda a že šifra by měla pokrývat všechny možné digramy [11] .

Klíč pro prvního příjemce

ALE	9	deset	21	26	32	34
L	6	7	čtrnáct	16	27	třicet
M	2	5	13	osmnáct	23	28
R	čtyři	osm	patnáct	22	22	36
V	3	17	dvacet	26	29	33
S	jeden	jedenáct	12	19	24	31

Klíč pro druhého příjemce

ALE	jeden	čtyři	13	16	22	25
L	3	6	deset	patnáct	osmnáct	31
M	7	9	17	19	23	36
R	čtrnáct	22	24	28	29	32
V	2	osm	12	dvacet	26	třicet
S	5	jedenáct	27	33	34	35

Homofonní substituce s minimální redundancí

Pro zlepšení metody lze dosáhnout minimální redundance šifrové abecedy. Algoritmus

Každé číslo použijeme pouze jednou. Pokud se diagram opakuje, vezměte pro něj nové číslo, které bude větší než maximum dostupné v abecedě. V našem případě dostaneme šifrový text " " $13$ $9$ $2$ $32$ $37$ $19$ $27$ $deset$ $osm$ $38$ $39$ $3$
Po dokončení šifrování odstraňte z matice všechny nepoužívané prvky
Stránku šifrové knihy s minimální redundancí lze získat nahrazením všech čísel různými náhodnými čísly. Je zřejmé, že v tomto případě můžeme získat šifrový text " ". Tabulka klíčů diagramu a klíče pro každého z příjemců pro takovou sadu zpráv budou omezeny na možné minimum [11] . $jeden$ $2$ $3$ $čtyři$ $5$ $6$ $7$ $osm$ $9$ $deset$ $jedenáct$ $12$

	ALE	L	M	R	V	S
ALE		osm	2	4, 10
L						7
M	1, 11				3, 5
R					9
V		12
S			6

Klíč 1

ALE	2, 4, 8, 10
L	7
M	1, 3, 5, 11
R	9
V	12
S	6

Klíč 2

ALE	1, 11
L	8, 12
M	2, 6
R	4, 10
V	3, 5, 9
S	7

Přečtete-li písmena v pořadí označeném čísly odpovídajícími každému písmenu, získáte prostý text. Z tohoto důvodu je použití takové šifry nemožné, protože k získání prostého textu bude stačit útočníkovi mít klíč, aniž by měl soukromý text. Díky tomu je zbytečné snižovat redundanci textu. Na druhé straně dříve používaná maticová forma homofonní substituce druhého řádu má poměrně dobrou kryptografickou sílu, pokud je použita plná abeceda. Dva texty poskytnou ( ) možné diagramy, které se nebudou příliš opakovat, pokud není text příliš velký. V důsledku toho bude redundance šifrovaných zpráv nízká, zatímco zpráva bude používat velké množství různých znaků, což jsou vážné překážky pro kryptoanalýzu [12] . $33\cdot 33=1089$ $26\cdot 26=676$

Pozoruhodné příklady

Kryptogramy slavného sériového vraha Zodiac jsou zašifrovány homofonní substituční šifrou. Jeden ze dvou kryptogramů se zatím nepodařilo rozluštit [13] .

Baleovy kryptogramy se považují za zašifrované homofonní substituční šifrou prvního řádu a pravděpodobnost rozluštění druhého kryptogramu (jediného ze tří, který bylo možné rozluštit) tak, aby se získal další smysluplný text, je nejmenší [ 14] [15] .

Homofonní substituce v přírodě

Genetický kód je homofonní substituce, ve které aminokyseliny hrají roli symbolů otevřeného textu a kodony jsou trojice nukleotidů - symboly šifrového textu [16] .

Poznámky

↑ 1 2 Singh, 2007 , str. 70.
↑ Kahn, 2000 , str. 7.
↑ 1 2 Anisimov .
↑ 1 2 3 4 Singh, 2007 , str. 71-72.
↑ Dolgov, 2008 , str. 33.
↑ Schneier, 2002 , str. 35.
↑ 1 2 Singh, 2007 , str. 72.
↑ John C. King a Dennis R. Bahler. Algoritmické řešení sekvenčních homofonních šifer (anglicky) = Algoritmické řešení sekvenčních homofonních šifer // Cryptologia: vědecký časopis. — Taylor & Francis, 1993. — Sv. 17. - S. 149. - ISSN 0161-1194 . - doi : 10.1080/0161-119391867827 . Archivováno z originálu 12. prosince 2020.
↑ Kladivo, 1988 , s. 12-13.
↑ Kladivo, 1988 , s. 13.
↑ 1 2 Hammer, 1988 , str. čtrnáct.
↑ Kladivo, 1988 , s. 14-15.
↑ John C. King a Dennis R. Bahler. Rámec pro studium homofonních šifer v klasických šifrovacích a genetických systémech (anglicky) = Rámec pro studium homofonních šifer v klasických šifrovacích a genetických systémech // Cryptologia: Journal. — Taylor & Francis, 1993. — Sv. 17. - S. 46. - ISSN 0161-1194 . - doi : 10.1080/0161-118891862747 . Archivováno z originálu 15. února 2019.
↑ John C. King a Dennis R. Bahler. Rámec pro studium homofonních šifer v klasických šifrovacích a genetických systémech (anglicky) = Rámec pro studium homofonních šifer v klasických šifrovacích a genetických systémech // Cryptologia: Journal. — Taylor & Francis, 1993. — Sv. 17. - S. 47. - ISSN 0161-1194 . - doi : 10.1080/0161-119391867755 . Archivováno z originálu 15. února 2019.
↑ Carl Hammer. Homofonické šifry druhého řádu (anglicky) = Homofonické šifry druhého řádu // Cryptologia: Journal. - Taylor & Francis, 1988. - Sv. 12. - S. 15-19. — ISSN 0161-1194 . - doi : 10.1080/0161-118891862747 . Archivováno 8. května 2020.
↑ John C. King a Dennis R. Bahler. Rámec pro studium homofonních šifer v klasických šifrovacích a genetických systémech (anglicky) = Rámec pro studium homofonních šifer v klasických šifrovacích a genetických systémech // Cryptologia: Journal. — Taylor & Francis, 1993. — Sv. 17. - S. 48-50. — ISSN 0161-1194 . - doi : 10.1080/0161-119391867755 . Archivováno z originálu 15. února 2019.

Literatura

Simon Singh. Kapitola 2. Neprolomitelná šifra // Kniha šifer. Tajná historie šifer a jejich dešifrování = The Code Book od Simona Singha / z angličtiny přeložil A. Galygin. - M .: AST , 2007. - T. 2. - S. 69-74. - 4000 výtisků. — ISBN 978-5-17-038477-8 .
Pazizin S. V., Malyuk A. A., Prigozhin N. S. Kapitola 3. Kryptografické metody informační bezpečnosti // Úvod do informační bezpečnosti v automatizovaných systémech. - M . : Horká linka - Telecom, 2001. - S. 52. - 148 s. - 3000 výtisků. — ISBN 5-93517-062-0 .
Dolgov V. A., Anisimov V. V. Kapitola 5. Substituční šifry // Kryptografické metody informační bezpečnosti . - Chabarovsk: Nakladatelství DVGUPS, 2008. - S. 32-33. — 155 str. - 30 kopií. (nedostupný odkaz)
Arto Salomaa. Chapter 1. Classical Cryptography // Public Key Cryptography = Public-Key Cryptography / Edited by A. E. Andreev and A. A. Bolotov. - M. : Mir, 1995. - S. 35. - 318 s. — ISBN 5-03-001991-X .
Schneier Bruce. Kapitola 1. Základní pojmy // Aplikovaná kryptografie. Protokoly, algoritmy, zdrojový kód v jazyce C = Aplikovaná kryptografie. Protokoly, algoritmy a zdrojový kód v C / z angličtiny přeložil A. Galygin. - M .: Triumph, 2002. - 816 s. - 3000 výtisků. - ISBN 5-89392-055-4 . Archivováno 8. října 2013 na Wayback Machine
David Kahn. Codebreakers / Z angličtiny přeložil A. Klyuchevsky. - M .: Tsentrpoligraf, 2000. - ISBN 5-227-00678-4 . (nedostupný odkaz)
Carl Hammer. Homofonické šifry druhého řádu (anglicky) = Homofonické šifry druhého řádu // Cryptologia: Scientific journal. - Taylor & Francis, 1988. - Sv. 12. - S. 11-20. — ISSN 0161-1194 . - doi : 10.1080/0161-118891862747 .
John C. King a Dennis R. Bahler. Alhoritmické řešení sekvenčních homofonních šifer (anglicky) = Alhoritmické řešení sekvenčních homofonních šifer // Cryptologia: Scientific journal. — Taylor & Francis, 1993. — Sv. 17. - S. 148-165. — ISSN 0161-1194 . - doi : 10.1080/0161-119391867827 .
John C. King a Dennis R. Bahler. Rámec pro studium homofonních šifer v klasickém šifrování a genetických systémech (anglicky) = Rámec pro studium homofonních šifer v klasických šifrovacích a genetických systémech // Cryptologia: Scientific journal. — Taylor & Francis, 1993. — Sv. 17. - S. 45-54. — ISSN 0161-1194 . - doi : 10.1080/0161-119391867755 .

Odkazy

Anisimov VV Substituční šifry . Kryptografické metody ochrany informací . Staženo: 4. prosince 2012. (neurčitý)