Homofoninen substituutio

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 19. maaliskuuta 2022 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Homofoninen korvaussalaus on korvaussalaus , jossa jokainen selkeän tekstin merkki korvataan yhdellä aakkossalauksen useista merkeistä, ja yhden kirjaimen korvaavien merkkien määrä on verrannollinen tämän kirjaimen esiintymistiheyteen. Tämän avulla voit piilottaa tietyn kirjaimen todellisen esiintymistiheyden salatekstissä [1] .

Historia

Salaus homofonisella substituutiolla on tunnettu 1400-luvulta lähtien [2] .

Simeone de Crema käytti vuonna 1401 ensimmäisen kerran homofonitaulukoita vokaalien yhtenäiseen taajuuteen moniarvoisen substituution avulla [3] .

Leon Battista Alberti kuvaili vuonna 1466 julkaistussa traktaatissaan salakirjoituksia korvaussalauksen, jossa yhdelle kirjaimelle on määritetty useita elementtejä [3] .

Perinteiset yksiaakkosiset korvaussalaukset olivat merkityksellisiä vielä 1600-luvulla triviaaleissa tehtävissä, kuten henkilökohtaisen kirjeenvaihdon salaamisessa tietojen piilottamiseksi palvelijoilta tai päiväkirjan suojelemiseksi vaimolta tai aviomieheltä. Monoaakkosinen substituutio tuottaa yksinkertaisen ja nopean tiedon suojauksen ihmisiltä, jotka eivät osaa kryptaanalyysiä . Vakavampiin tarkoituksiin tällainen salaus ei kuitenkaan ollut enää turvallinen, joten tuli välttämättömäksi etsiä salausta, joka olisi vaikeampi rikkoa kuin yksiaakkosinen korvaussalaus , mutta jota olisi helpompi käyttää kuin moniaakkosista korvaussalausta . Tällaisista salakirjoista esiteltiin useita muunnelmia, tehokkain ratkaisu tähän ongelmaan oli homofoninen substituutiosalaus tai homofoninen substituutio [1] .

Salaus

Antaa olla selkeässä tekstissä käytetyn aakkoston merkki. Jokaiselle , muodostamme joukon symboleja niin, että eri symbolit ja joukot ja eivät leikkaa. Tyypillisesti joukon alkiot ovat numeroita. Homofonisessa salauksessa kunkin merkin vaihtojen määrä otetaan suhteessa todennäköisyyteen, että kyseinen merkki esiintyy selväkielisessä tekstissä. Salauksessa selkätekstin merkki valitaan joko satunnaisesti (satunnaislukugeneraattori) tai tietyllä tavalla (esim. järjestyksessä). Tekstistä useimmin esiintyvien kirjainten muistamiseksi he käyttävät kirjainten "senovaliter" ja "tetrishonda" yhdistelmiä venäjäksi ja englanniksi. Nämä yhdistelmät ovat samankaltaisia kuin sanoja, ja siksi ne on helppo muistaa [4] . $i$ $i$ $Mi}$ $i$ $j$ $Mi}$ $M_{j}$ $Mi}$

Venäjän aakkosten kirjainten ilmestymisen todennäköisyys

Kirje	Todennäköisyys
MUTTA	0,069
B	0,013
AT	0,038
G	0,014
D	0,024
HÄNEN	0,071
JA	0,007
W	0,016

Kirje	Todennäköisyys
Ja	0,064
Y	0,010
Vastaanottaja	0,029
L	0,039
M	0,027
H	0,057
O	0,094
P	0,026

Kirje	Todennäköisyys
R	0,042
FROM	0,046
T	0,054
klo	0,023
F	0,003
X	0,008
C	0,005
H	0,012

Kirje	Todennäköisyys
W	0,006
SCH	0,004
Kommersant	0,001
S	0,015
b	0,013
E	0,002
YU	0,005
minä	0,017

(*) (Taulukko näyttää yli miljoonan merkin kokonaismäärän kirjallisten ja tieteellisten tekstien taajuusanalyysin tulokset. Samoissa olosuhteissa "aukon" todennäköisyys on 0,146.)

Koska harvinaisimman kirjaimen kohtaamisen todennäköisyys on noin tuhannesosa, salaus homofonisella selvätekstikorvausmenetelmällä voidaan suorittaa käyttämällä salauksen korvaustaulukkoa, jossa kukin salauksen korvaus koostuu 3 numerosta ja niiden kokonaismäärä on 1000. Tässä tapauksessa harvinaisin elementti, tasan yksi merkki [4] .

Alla on esimerkki tällaisesta taulukosta.

Ei.	MUTTA	B	AT	…	E	…	O	P	R	…	E	YU	minä
yksi	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

Jotkut taulukon kentät ovat tyhjiä, koska lähdeaakkoston kunkin merkin korvausten määrä on erilainen. Tätä fragmenttia voidaan käyttää esimerkiksi sanan "VERA" salaamiseen. Jokainen alkuperäisen viestin kirjain, tässä tapauksessa sana, tulee korvata jollakin kyseisen kirjaimen sarakkeen salauskorvauksista. Jos kirjaimet korvataan sellaisilla salauskorvauksilla: "B" - , "E" - , "P" - , "A" - , niin salatulla sanalla on numerosarja " " [4] . $325$ $700$ $865$ $095$ $325$ $700$ $865$ $095$

Cryptanalysis

Homofoninen korvaussalaus on yksinkertaisin suojaus taajuusanalyysin salaushyökkäyksiä vastaan, koska yksi sen korvauksista valitaan satunnaisesti salattaessa lähdetekstin kirjainta. Tällä salausmenetelmällä salatekstielementit ilmestyvät yhtä suurella todennäköisyydellä, joten tavallinen kirjainten tiheyden laskenta on hyödytöntä kryptaanalyytikolle . Parien, kirjainten kolmoiskappaleiden tai sanojen laskemiseen perustuva taajuuden kryptausanalyysi onnistuu kuitenkin paremmin. Esimerkiksi artikkeli a on yleisin englanninkielisessä pelkässä tekstissä. Lisäksi q-kirjaimen jälkeen on vain yksi kirjain - u. Näin ollen, kun huomaat joitakin merkkiyhdistelmiä, voit tulkita osan tekstistä ja palauttaa loput saatujen tietojen mukaan [5] [4] .

Nykyaikaiset tietokoneet purkavat homofonisella korvauksella salattujen tekstien salauksen muutamassa sekunnissa [6] .

Salauksen ominaisuudet

Tämän menetelmän erikoisuus on, että salauksen vaihtoa ei toisteta. Tämä tarkoittaa, että jos kirjaimella "Ф" on 3 salauskorvausta, esimerkiksi , ja , niin salauskorvaukset , ja merkitsevät vain kirjainta "Ф" [7] . $100$ $477$ $906$ $100$ $477$ $906$

Homofoninen salaus voi näyttää moniaakkoiselta ( moniaakkoselta ) salaukselta, koska aakkosten jokainen kirjain voidaan salata monin tavoin, mutta itse asiassa homofoninen korvaussalaus on eräänlainen yksiaakkosinen ( monaakkosellinen ) salaus. Pääsyy siihen, miksi homofoninen salaus on yksiaakkosinen, on se, että salauksen aakkoset eivät muutu salausprosessin aikana [7] .

Salauksen ominaisuudet

Homofoniselle korvaussalaukselle on tunnusomaista kaksi parametria - salatekstin pituus ja monimutkaisuus , jossa on tässä salatekstissä käytettyjen salakirjoitusaakkosten eri merkkien lukumäärä. Ilmeisesti monimutkaisuus on rajallinen . Kun salauksen monimutkaisuus on tarpeeksi lähellä nollaa, salaus on yksinkertainen korvaussalaus. Tietyllä arvolla salaaakkosten merkkien jakautuminen muuttuu tasaiseksi (noin 0,3 200 merkin salatekstiä varten), mutta jos jatkat monimutkaisuuden lisäämistä, voit saavuttaa raja-arvon, jossa salauksen purkaminen ei ole enää mahdollista yksiselitteisesti teksti. Korkeamman asteen homofonisilla substituutioilla on sama salateksti erilaisille selväkielisille teksteille, joten tapauksissa, joissa salatekstin pituus on pienempi kuin ainutlaatuisuusetäisyys , on mahdotonta ymmärtää, mikä selkeän tekstin versio on oikea [8] . $N$ $M = N/L$ $L$ $0\leqslant M\leqslant 1$ $M$

Toisen asteen homofoninen substituutio

Toisen asteen homofoninen substituutio on homofoninen substituutio siten, että salateksti voidaan purkaa kahdella tavalla. Esimerkiksi " " yhden avaimen (avain 1) avulla voidaan purkaa nimellä "MAMA SOAPED THE FRAME" ja toisen avaimen (avain 2) avulla "AMUR WASHED URAL". Molemmilla selkoteksteillä ei ole paljoa merkitystä, mutta ne havainnollistavat hyvin, että saman salatekstin taakse voidaan piilottaa täysin erilaisia viestejä [9] . $13$ $9$ $2$ $32$ $2$ $19$ $27$ $kymmenen$ $kahdeksan$ $32$ $13$ $3$

Avain 1

M	13, 2
MUTTA	9, 32, 10
S	19
L	27
R	kahdeksan
klo	3

Avain 2

M	9, 19
MUTTA	13
S	27
L	kymmenen
R	32
klo	8.2

Avainten luonti ja salaus

Ymmärtääksemme, kuinka tällainen salaus voidaan saada, kirjoitetaan samanpituiset selkotekstimme toistensa alle.

M	MUTTA	M	MUTTA	M	S	L	MUTTA	R	MUTTA	M	klo
MUTTA	M	klo	R	klo	M	S	L	klo	R	MUTTA	L

Huomaa nyt, että jos luemme tuloksena olevaa tietuetta ei riveissä, vaan sarakkeissa, saamme 9 erilaista digrammia (kirjainparia): "MA", "AM", "MU", "AP", "YM", " LY" , "AL", "RU", "UL". Kaikki digrammit paitsi "MA", "MU" ja "AR" toistetaan kerran. Täytä seuraavaksi satunnaisesti matriisi (6 on pelkkien aakkosten kirjainten lukumäärä; jos tekstissä käytetään koko aakkostoa, meillä on matriisi tai venäjän ja englannin aakkosille) esimerkiksi numeroilla, 1 - 36 [10] . $6\cdot 6$ $33\cdot 33$ $26\cdot 26$

	MUTTA	L	M	R	klo	S
MUTTA	21	kymmenen	9	32	26	34
L	16	6	7	neljätoista	kolmekymmentä	27
M	13	kahdeksantoista	23	28	2	5
R	neljä	viisitoista	36	22	kahdeksan	35
klo	25	3	17	29	kaksikymmentä	33
S	yksi	31	19	24	12	yksitoista

Jokainen rivi ja jokainen sarake on yhdistetty johonkin ensimmäisen ja toisen selväkielisen tekstin aakkosmerkkeistä. Nyt jokainen kaava vastaa tiettyä numeroa (vastaavien rivien ja sarakkeiden leikkauskohdassa), joten korvaamalla kaava vastaavalla numerolla voimme salata tekstit. Digrammeja vastaavien numeroiden matriisi toimii avaimena tässä tapauksessa. Jotta koko matriisi pysyisi salassa, se on jaettu kahteen matriisiin: toinen saadaan lajittelemalla rivien elementit, toinen lajittelemalla sarakkeet ja transponoimalla . Tuloksena on kaksi matriisia, joissa kummassakin rivien elementit on järjestetty nousevaan (laskevaan) järjestykseen ja yhdellä matriisilla voidaan saada vain yksi selväteksti. Esimerkiksi tekstit, joissa on samat aakkoset, otetaan, koska oletetaan, että yleisessä tapauksessa koko aakkosto käytetään salauksen luomiseen ja että salauksen tulee kattaa kaikki mahdolliset digrammit [11] .

Ensimmäisen vastaanottajan avain

MUTTA	9	kymmenen	21	26	32	34
L	6	7	neljätoista	16	27	kolmekymmentä
M	2	5	13	kahdeksantoista	23	28
R	neljä	kahdeksan	viisitoista	22	22	36
klo	3	17	kaksikymmentä	26	29	33
S	yksi	yksitoista	12	19	24	31

Avain toiselle vastaanottajalle

MUTTA	yksi	neljä	13	16	22	25
L	3	6	kymmenen	viisitoista	kahdeksantoista	31
M	7	9	17	19	23	36
R	neljätoista	22	24	28	29	32
klo	2	kahdeksan	12	kaksikymmentä	26	kolmekymmentä
S	5	yksitoista	27	33	34	35

Homofoninen korvaus minimaalisella redundanssilla

Menetelmän parantamiseksi voidaan saavuttaa salausaakkosten minimiredundanssi . Algoritmi

Käytämme kutakin numeroa vain kerran. Jos kaava toistetaan, ota sille uusi numero, joka on suurempi kuin aakkosissa käytettävissä oleva enimmäismäärä. Meidän tapauksessamme saamme salatekstin " " $13$ $9$ $2$ $32$ $37$ $19$ $27$ $kymmenen$ $kahdeksan$ $38$ $39$ $3$
Kun salaus on valmis, poista kaikki käyttämättömät elementit matriisista
Salauskirjasivu, jolla on minimaalinen redundanssi, voidaan saada korvaamalla kaikki numerot erilaisilla satunnaisluvuilla. Ilmeisesti tässä tapauksessa voimme saada salatekstin " ". Suunnitelma-avaintaulukko ja kunkin vastaanottajan avaimet tällaiselle viestijoukolle pienennetään mahdollisimman pieneksi [11] . $yksi$ $2$ $3$ $neljä$ $5$ $6$ $7$ $kahdeksan$ $9$ $kymmenen$ $yksitoista$ $12$

	MUTTA	L	M	R	klo	S
MUTTA		kahdeksan	2	4, 10
L						7
M	1, 11				3, 5
R					9
klo		12
S			6

Avain 1

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

Avain 2

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

Jos luet kirjaimet kutakin kirjainta vastaavien numeroiden osoittamassa järjestyksessä, saat selkeän tekstin. Tämän vuoksi tällaisen salauksen käyttö tulee mahdottomaksi, koska pelkän tekstin saamiseksi hyökkääjällä riittää avain, vaikka hänellä ei olisi edes yksityistä tekstiä. Tämä tekee tekstin redundanssin vähentämisestä turhaa. Toisaalta aiemmin käytetyllä toisen asteen homofonisen substituution matriisimuodolla on melko hyvä kryptografinen vahvuus, jos käytetään täyttä aakkostoa. Kaksi tekstiä antaa ( ) mahdollisia digrammeja, jotka eivät toistu paljon, ellei teksti ole liian suuri. Tämän seurauksena salattujen viestien redundanssi on alhainen, kun taas viestissä käytetään paljon erilaisia merkkejä, jotka ovat vakavia esteitä kryptausanalyysille [12] . $33\cdot 33=1089$ $26\cdot 26=676$

Merkittäviä esimerkkejä

Kuuluisan Zodiac -sarjamurhaajan kryptogrammit on salattu homofonisella korvaussalauksella. Toista kahdesta kryptogrammista ei ole vielä purettu [13] .

Paalin kryptogrammit katsotaan salatuiksi ensimmäisen asteen homofonisella korvaussalauksella, ja todennäköisyys purkaa toinen kryptogrammi (ainoa kolmesta, joka voidaan purkaa) siten, että saadaan toinen mielekäs teksti, on pienin [ 14] [15] .

Homofoninen substituutio luonnossa

Geneettinen koodi on homofoninen substituutio, jossa aminohapoilla on selkeän tekstin symbolien rooli ja kodonit ovat nukleotidien kolminkertaisia salatekstimerkkejä [16] .

Muistiinpanot

↑ 1 2 Singh, 2007 , s. 70.
↑ Kahn, 2000 , s. 7.
↑ 1 2 Anisimov .
↑ 1 2 3 4 Singh, 2007 , s. 71-72.
↑ Dolgov, 2008 , s. 33.
↑ Schneier, 2002 , s. 35.
↑ 1 2 Singh, 2007 , s. 72.
↑ John C. King & Dennis R. Bahler. An Algorithmic Solution of Sequental homophonic ciphers (englanti) = An Algorithmic Solution of Sequental homophonic ciphers // Cryptologia: science Journal. - Taylor & Francis, 1993. - Voi. 17. - s. 149. - ISSN 0161-1194 . - doi : 10.1080/0161-119391867827 . Arkistoitu alkuperäisestä 12.12.2020.
↑ Hammer, 1988 , s. 12-13.
↑ Hammer, 1988 , s. 13.
↑ 1 2 Hammer, 1988 , s. neljätoista.
↑ Hammer, 1988 , s. 14-15.
↑ John C. King & Dennis R. Bahler. A framework for the study of homofonic ciphers in classical encryption and genetic systems (englanti) = A framework for the study of homophonic ciphers in classical encryption and genetic systems // Cryptologia: Journal. - Taylor & Francis, 1993. - Voi. 17. - s. 46. - ISSN 0161-1194 . - doi : 10.1080/0161-118891862747 . Arkistoitu alkuperäisestä 15. helmikuuta 2019.
↑ John C. King & Dennis R. Bahler. A framework for the study of homofonic ciphers in classical encryption and genetic systems (englanti) = A framework for the study of homophonic ciphers in classical encryption and genetic systems // Cryptologia: Journal. - Taylor & Francis, 1993. - Voi. 17. - s. 47. - ISSN 0161-1194 . - doi : 10.1080/0161-119391867755 . Arkistoitu alkuperäisestä 15. helmikuuta 2019.
↑ Carl Hammer. Second order homophonic ciphers (englanniksi) = Second order homophonic ciphers // Cryptologia: Journal. - Taylor & Francis, 1988. - Voi. 12. - s. 15-19. — ISSN 0161-1194 . - doi : 10.1080/0161-118891862747 . Arkistoitu 8. toukokuuta 2020.
↑ John C. King & Dennis R. Bahler. A framework for the study of homofonic ciphers in classical encryption and genetic systems (englanti) = A framework for the study of homophonic ciphers in classical encryption and genetic systems // Cryptologia: Journal. - Taylor & Francis, 1993. - Voi. 17. - s. 48-50. — ISSN 0161-1194 . - doi : 10.1080/0161-119391867755 . Arkistoitu alkuperäisestä 15. helmikuuta 2019.

Kirjallisuus

Simon Singh. Luku 2. Murtamaton salaus // Salauskirja. Salausten salainen historia ja niiden salauksen purku = Simon Singhin koodikirja / englannista kääntänyt A. Galygin. - M .: AST , 2007. - T. 2. - S. 69-74. - 4000 kappaletta. — ISBN 978-5-17-038477-8 .
Pazizin S. V., Malyuk A. A., Prigozhin N. S. Luku 3. Tietoturvan kryptografiset menetelmät // Johdatus tietoturvaan automatisoiduissa järjestelmissä. - M . : Hot line - Telecom, 2001. - S. 52. - 148 s. - 3000 kappaletta. — ISBN 5-93517-062-0 .
Dolgov V. A., Anisimov V. V. Luku 5. Korvaussalaukset // Tietoturvan kryptografiset menetelmät . - Habarovsk: DVGUPS Publishing House, 2008. - S. 32-33. - 155 s. - 30 kappaletta. (linkki ei saatavilla)
Arto Salomaa. Luku 1. Klassinen kryptografia // Julkisen avaimen kryptografia = Public-Key Cryptography / Toimittaneet A. E. Andreev ja A. A. Bolotov. - M .: Mir, 1995. - S. 35. - 318 s. — ISBN 5-03-001991-X .
Schneier Bruce. Luku 1. Peruskäsitteet // Sovellettu kryptografia. Protokollat, algoritmit, lähdekoodi C-kielellä = Applied Cryptography. Protokollat, algoritmit ja lähdekoodi C-kielellä / kääntänyt englannista A. Galygin. - M . : Triumph, 2002. - 816 s. - 3000 kappaletta. - ISBN 5-89392-055-4 . Arkistoitu 8. lokakuuta 2013 Wayback Machinessa
David Kahn. Codebreakers / Englannista kääntänyt A. Klyuchevsky. - M . : Tsentrpoligraf, 2000. - ISBN 5-227-00678-4 . (linkki ei saatavilla)
Carl Hammer. Second order homophonic ciphers (englanniksi) = Second order homophonic ciphers // Cryptologia: Scientific Journal. - Taylor & Francis, 1988. - Voi. 12. - s. 11-20. — ISSN 0161-1194 . - doi : 10.1080/0161-118891862747 .
John C. King & Dennis R. Bahler. An alhoritmic solution of sequental homophonic ciphers (englanti) = An alhoritmic solution of sequental homophonic ciphers // Cryptologia: Scientific Journal. - Taylor & Francis, 1993. - Voi. 17. - s. 148-165. — ISSN 0161-1194 . - doi : 10.1080/0161-119391867827 .
John C. King & Dennis R. Bahler. A framework for the study of homophonic ciphers in classical encryption and genetic systems (englanti) = A framework for the study of homophonic ciphers in classical encryption and genetic systems // Cryptologia: Scientific Journal. - Taylor & Francis, 1993. - Voi. 17. - s. 45-54. — ISSN 0161-1194 . - doi : 10.1080/0161-119391867755 .

Linkit

Anisimov VV Korvaussalaukset . Tietojen suojauksen kryptografiset menetelmät . Haettu: 4. joulukuuta 2012. (määrätön)