Homofon szubsztitúció

A homofon helyettesítő rejtjel egy olyan  helyettesítő rejtjel , amelyben a nyílt szöveg minden karakterét az ábécé titkosításának több karaktere közül egyel helyettesítik , és az egy betűhöz tartozó helyettesítő karakterek száma arányos ennek a betűnek a gyakoriságával. Ez lehetővé teszi egy adott betű valós előfordulási gyakoriságának elrejtését a titkosított szövegben [1] .

Történelem

A homofon szubsztitúciós módszerrel történő titkosítás a 15. század óta ismert [2] .

Simeone de Crema 1401-ben használt először homofon táblázatokat a magánhangzók egységes gyakoriságára többértékű helyettesítés segítségével [3] .

Leon Battista Alberti 1466- ban megjelent Treatise on Ciphers -ben egy helyettesítő titkosítást írt le, amelyben egy betűhöz több elem van hozzárendelve [3] .

A hagyományos monoalfabetikus helyettesítési titkosítások még a 17. században is relevánsak voltak az olyan triviális feladatoknál, mint a személyes levelezés titkosítása, hogy elrejtse az információkat a szolgák elől, vagy a napló védelme a feleség vagy férj elől. A monoalfabetikus helyettesítés egyszerű és gyors információvédelmet biztosít a kriptoanalízisben nem tudó emberektől . Komolyabb célokra azonban az ilyen titkosítás már nem volt biztonságos, ezért szükségessé vált egy olyan rejtjel keresése, amelyet nehezebb lenne feltörni, mint egy monoalfabetikus helyettesítő rejtjel , de amely könnyebben használható, mint egy többalfabetikus helyettesítő rejtjel . Az ilyen rejtjeleknek több változatát is bemutatták, erre a problémára a leghatékonyabb megoldás a homofon szubsztitúciós rejtjel, vagy a homofon szubsztitúció volt [1] .

Titkosítás

Legyen  az egyszerű szövegben használt ábécé karaktere. Mindegyikhez összeállítjuk a szimbólumkészletet úgy, hogy a különböző szimbólumok és a halmazok ne metsszék egymást. Általában egy halmaz elemei számok. A homofon titkosításnál az egyes karakterek helyettesítésének számát a karakter szövegben való megjelenésének valószínűségével arányosan veszik. A titkosítás során egy egyszerű szöveges karakter helyettesítését véletlenszerűen (véletlenszám-generátor) vagy meghatározott módon (pl. sorrendben) választják ki. A szövegekben leggyakrabban előforduló betűk memorizálásához a "senovaliter" és a "tetrishonda" betűk kombinációit használják az orosz és az angol nyelven. Ezek a kombinációk hasonlóak a szavakhoz, ezért könnyen megjegyezhetők [4] .

(*) (A táblázat az 1 millió karaktert meghaladó összmennyiségű irodalmi és tudományos szövegek gyakorisági elemzésének eredményeit mutatja. Ugyanezen feltételek mellett a „rés” valószínűsége 0,146.)

Mivel a legritkább betűvel való találkozás valószínűsége hozzávetőleg egy ezrelék, a homofon egyszerű szöveg helyettesítési módszerrel történő titkosítás egy rejtjelhelyettesítési táblázat segítségével is végrehajtható, ahol minden rejtjelhelyettesítés 3 számjegyből áll, és ezek teljes száma 1000. Ebben az esetben a a legritkább elem, pontosan egy karakter [4] .

Az alábbiakban egy ilyen táblázat látható.

A táblázat egyes mezői üresek, mivel a forrásábécé egyes karaktereinél eltérő a helyettesítések száma. Például ez a töredék használható a "VERA" szó titkosításához. Az eredeti üzenet minden betűjét, ebben az esetben egy szót, az adott betű oszlopában található titkosítási helyettesítések valamelyikével kell helyettesíteni. Ha a betűket ilyen titkosítási helyettesítések helyettesítik: "B" - , "E" - , "P" - , "A" - , akkor a titkosított szó " " számsorozat alakja [4] .

Kriptanalízis

A homofon szubsztitúciós titkosítás a legegyszerűbb védekezés a frekvenciaelemző kriptográfiai támadások ellen, mivel a forrásszöveg betűinek titkosításakor véletlenszerűen választják ki valamelyik helyettesítését. Ezzel a titkosítási módszerrel a rejtjelezett szövegelemek egyenlő valószínűséggel jelennek meg, így a betűk gyakoriságának szokásos számítása haszontalan egy kriptoanalitikus számára . A párok, betűhármasok vagy szavak számlálásán alapuló gyakorisági kriptográfiai elemzés azonban sikeresebb lesz. Például a cikk a leggyakoribb angol egyszerű szövegben. Ezenkívül a q betű után csak egy betű van - u. Így néhány karakterkombinációt észlelve megfejtheti a szöveg egy részét, majd a kapott információk alapján visszaállíthatja a többit [5] [4] .

Jelenleg a modern számítógépek pillanatok alatt visszafejtik a homofón szubsztitúcióval titkosított szövegeket [6] .

A titkosítás jellemzői

Ennek a módszernek az a sajátossága, hogy a rejtjelcserék nem ismétlődnek meg. Ez azt jelenti, hogy ha a "Ф" betűnek 3 rejtjel helyettesítése van, például , és , akkor a rejtjel helyettesítések , és csak a "Ф" betűt jelölik [7] .

A homofonikus rejtjel többalfabetikus ( polialfabetikus ) rejtjelnek tűnhet , mivel az ábécé minden betűje többféleképpen titkosítható, valójában azonban a homofon helyettesítő titkosítás egy monoalfabetikus ( monoalfabetikus ) rejtjel. A fő ok, amiért a homofonikus titkosítás monoalfabetikus, az az, hogy a titkosítási ábécé nem változik a titkosítási folyamat során [7] .

A titkosítás jellemzői

A homofon helyettesítő titkosítást két paraméter jellemzi - a rejtjelezett szöveg hossza és a bonyolultság , ahol  a rejtjelezett ábécé ebben a rejtjelezett szövegben használt különböző karaktereinek száma. Nyilvánvaló, hogy a komplexitás korlátozott . Ha egy rejtjel összetettsége elég közel van a 0-hoz, a rejtjel egy egyszerű helyettesítő rejtjel. Egy bizonyos értéknél a titkosítási ábécé karaktereinek eloszlása ​​egyenletessé válik (kb. 0,3 200 karakteres rejtjelezett szöveg esetén), azonban ha tovább növeli a bonyolultságot, elérheti azt a határértéket, amelynél már nem lehet egyértelműen visszafejteni. a szöveg. A magasabb rendű homofon helyettesítések ugyanazzal a rejtjelezett szöveggel rendelkeznek a különböző nyílt szövegekhez, ezért olyan esetekben, amikor a rejtjelezett szöveg hossza kisebb, mint az egyediség távolsága , lehetetlen megérteni, hogy a nyílt szöveg melyik változata lesz helyes [8] .

Másodrendű homofon szubsztitúció

A másodrendű homofon szubsztitúció olyan homofon helyettesítés, amelynél a rejtjelezett szöveg kétféleképpen dekódolható. Például a " " egy kulccsal (1. kulcs) dekódolható "MAMA SZAPPANÍTOTT A KERETET", a második kulcs (2. kulcs) segítségével pedig "AMUR WASHED URAL"-ként. Mindkét nyílt szöveg nem hordoz sok jelentést, de jól szemlélteti, hogy egyazon titkosított szöveg mögött teljesen különböző üzenetek rejtőzhetnek [9] .

Kulcsgenerálás és titkosítás

Annak érdekében, hogy megértsük, hogyan lehet ilyen titkosítást megszerezni, írjuk egymás alá az egyenlő hosszúságú nyílt szövegeinket.

Most vegye figyelembe, hogy ha a kapott rekordot nem sorokban, hanem oszlopokban olvassuk, 9 különböző digramot (betűpárt) kapunk: "MA", "AM", "MU", "AP", "YM", " LY" , "AL", "RU", "UL". Az „MA”, „MU” és „AR” kivételével minden digram egyszer ismétlődik. Ezután véletlenszerűen töltsük ki a mátrixot (6 az egyszerű szöveges ábécék betűinek száma; ha a teljes ábécét használjuk a szövegben, akkor lesz egy mátrixunk, vagy az orosz és az angol ábécére) például számokkal, 1-től 36-ig [10] .

Minden sor és minden oszlop az első és a második egyszerű szöveg valamelyik alfabetikus karakteréhez van hozzárendelve. Most minden digram egy bizonyos számnak felel meg (a megfelelő sorok és oszlopok metszéspontjában), ezért a digramot a megfelelő számra cserélve titkosíthatjuk a szövegeket. A digramoknak megfelelő számokat tartalmazó mátrix ebben az esetben kulcs szerepét tölti be. A teljes mátrix titokban tartása érdekében két mátrixra van osztva: az egyiket a sorok elemeinek rendezésével, a másikat az oszlopok rendezésével és transzponálásával kapjuk . A kimeneten két mátrixunk lesz, amelyek mindegyikében a sorok elemei növekvő (csökkenő) sorrendben vannak, és egy mátrix segítségével csak egy egyszerű szöveget kaphatunk. Például azonos ábécéjú szövegeket veszünk, mivel feltételezzük, hogy általános esetben a teljes ábécét használják fel egy titkosítás létrehozására, és a rejtjelnek le kell fednie az összes lehetséges digramot [11] .

Homofonikus helyettesítés minimális redundanciával

A módszer fejlesztése érdekében a titkosító ábécé minimális redundanciája érhető el. Algoritmus

1. Minden számot csak egyszer használunk. Ha a digram megismétlődik, vegyen egy új számot, amely nagyobb lesz, mint az ábécében elérhető maximális szám. A mi esetünkben a " " titkosított szöveget kapjuk
2. A titkosítás befejezése után távolítson el minden nem használt elemet a mátrixból
3. Minimális redundanciájú rejtjelkönyv oldalt kaphatunk, ha minden számot különböző véletlenszámokra cserélünk. Nyilvánvaló, hogy ebben az esetben megkaphatjuk a " " titkosított szöveget. A digramkulcs-tábla és az egyes címzettek kulcsai egy ilyen üzenetkészlethez a lehető legkisebbre csökkennek [11] .

Ha a betűket az egyes betűknek megfelelő számok által jelzett sorrendben olvassa el, megkapja az egyszerű szöveget. Emiatt egy ilyen rejtjel használata lehetetlenné válik, mivel a sima szöveg megszerzéséhez elegendő, ha a támadónak van kulcsa, anélkül, hogy privát szövege lenne. Ez értelmetlenné teszi a szövegredundancia csökkentését. Másrészt a másodrendű homofon szubsztitúció korábban használt mátrixformája meglehetősen jó kriptográfiai erősséggel rendelkezik, ha a teljes ábécét használjuk. Két szöveg ( ) olyan lehetséges digramokat ad, amelyek nem ismétlődnek sokat, hacsak a szöveg nem túl nagy. Ennek eredményeként a titkosított üzenetek redundanciája alacsony lesz, miközben az üzenet nagyszámú különböző karaktert használ majd, ami komoly akadályokat jelent a kriptoanalízis számára [12] .

Figyelemre méltó példák

A híres Zodiac sorozatgyilkos kriptogramjait homofonikus helyettesítő titkosítással titkosítják. A két kriptogram közül az egyiket még nem sikerült megfejteni [13] .

A bála kriptogramokat elsőrendű homofon helyettesítő rejtjellel titkosítottnak tekintik, és a legkisebb annak a valószínűsége, hogy a második kriptogramot ( a három közül az egyetlen, amely megfejthető) úgy fejtsék meg, hogy egy másik értelmes szöveget kapjanak. 14] [15] .

Homofon szubsztitúció a természetben

A genetikai kód egy homofon szubsztitúció, melyben az aminosavak a plaintext szimbólumok szerepét töltik be, a kodonok  pedig a nukleotidok  hármasa - titkosított szöveg szimbólumok [16] .

Jegyzetek

1. ↑ 1 2 Singh, 2007 , p. 70.
2. ↑ Kahn, 2000 , p. 7.
3. ↑ 1 2 Anisimov .
4. ↑ 1 2 3 4 Singh, 2007 , p. 71-72.
5. ↑ Dolgov, 2008 , p. 33.
6. ↑ Schneier, 2002 , p. 35.
7. ↑ 1 2 Singh, 2007 , p. 72.
8. ↑ John C. King és Dennis R. Bahler. An algorithmic Solution of sequental homophonic ciphers  (angol)  = An algorithmic Solution of sequental homophonic ciphers // Cryptologia: tudományos folyóirat. – Taylor & Francis, 1993. – 20. évf. 17. - P. 149. - ISSN 0161-1194 . - doi : 10.1080/0161-119391867827 . Az eredetiből archiválva : 2020. december 12.
9. ↑ Hammer, 1988 , p. 12-13.
10. ↑ Hammer, 1988 , p. 13.
11. ↑ 1 2 Hammer, 1988 , p. tizennégy.
12. ↑ Hammer, 1988 , p. 14-15.
13. ↑ John C. King és Dennis R. Bahler. A framework for the study of homophonic ciphers in classical encryption and genetic systems  (angol)  = A framework for the study of homophonic ciphers in classical encryption and genetic systems // Cryptologia: Journal. – Taylor & Francis, 1993. – 20. évf. 17. - P. 46. - ISSN 0161-1194 . - doi : 10.1080/0161-118891862747 . Archiválva az eredetiből 2019. február 15-én.
14. ↑ John C. King és Dennis R. Bahler. A framework for the study of homophonic ciphers in classical encryption and genetic systems  (angol)  = A framework for the study of homophonic ciphers in classical encryption and genetic systems // Cryptologia: Journal. – Taylor & Francis, 1993. – 20. évf. 17. - P. 47. - ISSN 0161-1194 . - doi : 10.1080/0161-119391867755 . Archiválva az eredetiből 2019. február 15-én.
15. ↑ Carl Hammer. Second order homophonic ciphers  (angolul)  = Second order homophonic ciphers // Cryptologia: Journal. - Taylor és Francis, 1988. - 1. évf. 12. - P. 15-19. — ISSN 0161-1194 . - doi : 10.1080/0161-118891862747 . Archiválva : 2020. május 8.
16. ↑ John C. King és Dennis R. Bahler. A framework for the study of homophonic ciphers in classical encryption and genetic systems  (angol)  = A framework for the study of homophonic ciphers in classical encryption and genetic systems // Cryptologia: Journal. – Taylor & Francis, 1993. – 20. évf. 17. - P. 48-50. — ISSN 0161-1194 . - doi : 10.1080/0161-119391867755 . Archiválva az eredetiből 2019. február 15-én.

Irodalom

• Simon Singh. 2. fejezet: Feltörhetetlen rejtjel // Rejtjelek könyve. A rejtjelek titkos története és dekódolásuk = The Code Book by Simon Singh / angolból fordította A. Galygin. - M .: AST , 2007. - T. 2. - S. 69-74. - 4000 példány.  — ISBN 978-5-17-038477-8 .
• Pazizin S. V., Malyuk A. A., Prigozhin N. S. 3. fejezet. Az információbiztonság kriptográfiai módszerei // Bevezetés az automatizált rendszerek információbiztonságába. - M . : Forró vonal - Telecom, 2001. - S. 52. - 148 p. - 3000 példányban.  — ISBN 5-93517-062-0 .
• Dolgov V. A., Anisimov V. V. 5. fejezet. Helyettesítő titkosítások // Az információbiztonság kriptográfiai módszerei . - Habarovszk: DVGUPS Kiadó, 2008. - S. 32-33. — 155 p. - 30 példány.  (nem elérhető link)
• Arto Salomaa. 1. fejezet Klasszikus kriptográfia // Public Key Cryptography = Public-Key Cryptography / Szerkesztette A. E. Andreev és A. A. Bolotov. - M . : Mir, 1995. - S. 35. - 318 p. — ISBN 5-03-001991-X .
• Schneier Bruce. 1. fejezet Alapfogalmak // Alkalmazott kriptográfia. Protokollok, algoritmusok, forráskód C nyelven = Applied Cryptography. Protokollok, algoritmusok és forráskód C nyelven / angolból fordította A. Galygin. - M . : Triumph, 2002. - 816 p. - 3000 példányban.  - ISBN 5-89392-055-4 . Archiválva : 2013. október 8. a Wayback Machine -nél
• David Kahn. Kódtörők / Angolból fordította A. Klyuchevsky. - M . : Tsentrpoligraf, 2000. - ISBN 5-227-00678-4 .  (nem elérhető link)
• Carl Hammer. Second order homophonic ciphers  (angolul)  = Second order homophonic ciphers // Cryptologia: Scientific Journal. - Taylor és Francis, 1988. - 1. évf. 12. - P. 11-20. — ISSN 0161-1194 . - doi : 10.1080/0161-118891862747 .
• John C. King és Dennis R. Bahler. An alhoritmic solution of sequental homophonic ciphers  (angol)  = An alhoritmic solution of sequental homophonic ciphers // Cryptologia: Scientific Journal. – Taylor & Francis, 1993. – 20. évf. 17. - P. 148-165. — ISSN 0161-1194 . - doi : 10.1080/0161-119391867827 .
• John C. King és Dennis R. Bahler. A framework for the study of homophonic ciphers in classical encryption and genetic systems  (angol)  = A framework for the study of homophonic ciphers in classical encryption and genetic systems // Cryptologia: Scientific Journal. – Taylor & Francis, 1993. – 20. évf. 17. - P. 45-54. — ISSN 0161-1194 . - doi : 10.1080/0161-119391867755 .

Linkek

• Anisimov VV Helyettesítő titkosítások . Az információvédelem kriptográfiai módszerei . Letöltve: 2012. december 4. (határozatlan)