Előadás № 8 a helyettesítés fogalma
Cél: megfontolni a helyettesítés fogalmát, az azonos helyettesítést,
magyarázza el, hogyan történik a szubsztitúciók sokszorosítása, megtaláljuk a fordított szubsztitúciót,
felsorolja a helyettesítések termékének tulajdonságait,
vegye figyelembe az inversion, a paritás-páratlan permutációk fogalmát
megmutatja, hogyan használják a permutációkat a kriptográfiában
Valami egyik barátomtól kaptam egy táviratot. Ez a telegram furcsa volt. Ezt mondja: "yazhirponchors mej".
Tud "olvasni" ezt a szöveget? Foma egy pillanatra elgondolkodva megértette a telegram titkát. Meghívást kapott. Úgy döntött, hogy ugyanabban a szellemben reagál. Összeállította a válaszüzeneteket, és ugyanúgy titkosította. Az eredmény két sorból állt:
- Szombaton jövök, hogy találkozzak.
A titkosítás vége után Thomas minden levelezését egy barátjával akarta, hogy csak titkosított szövegeket vezessen, és időnként megváltoztatta a titkosítás módját. Ezért lelkesen vette fel a titkosítás módját.
Úgy döntött, hogy felváltja a forrás szövegének betűit azokkal a pozíciók számával, amelyeket ezek a betűk elfoglalnak. Itt van egy lista a Thomas által fogadott számokról egy barát távirata számára:
Aztán észrevette, hogy a titkosított szöveg az eredeti szövegtől csak a bécék megváltozott sorrendjében különbözik. A betűk sorrendje megváltozik, könnyen látható ugyanazon pozíciószámok segítségével. Például egy másik barát telegramának titkosított szövegét most egy lista jelenítheti meg:
A két lista összehasonlítása a szöveg titkosításának kulcsa:
.
A karakterbevitel a következőképpen olvasható: "1 megy 18-ra". Ehelyett egy másik bejegyzést használnak.
A nyilak iránya határozza meg a szöveg titkosításának sorrendjét. Például a titkosított szöveg első pozíciójában lévő betűnek a 18. helyet kell elfoglalnia a rejtjeles szövegben.
Ha a nyilak iránya megfordul, akkor ugyanaz a kétsoros tábla határozza meg a szöveg dekódolásának sorrendjét. Például a 18. pozícióban lévő rejtjeles szövegnek a dekódolt szöveg első pozícióját kell elfoglalnia.
Végül, ha az első sor mindig a forrásszöveghez van társítva, akkor nem szükséges a nyilak használata. (A forráskód titkosítása titkosított szöveg, illetve titkosításkor történő visszafejtés esetén).
Miután mindezt megértette, Foma gyorsan leírta a kulcsát a távirata második titkosításához:
Csak egy bizonyos értelemben kell tájékoztatnia barátjának ezt a kulcsot, és garantálja a levelezés titkosságát!
Ha megérted Thomas elképzeléseit, itt a kedvenc titkosított szöveged:
A kulcs titkosítva van:
Próbáld meg elolvasni ezt a mondást!
A titkosítás kulcsa:
- Bízz, de ellenőrizd!
Valószínűleg már tudod, hogy ilyen típusú titkosítási kulcsokkal találkozhatsz. Mindegyikük kétsoros tábla lehet:
.
Itt a felső sorban minden természetes szám 1-től n-ig növekvő sorrendben. Az alsó sort a felső sorban lévő számok permutációjával kapjuk meg. Az egész tábla egészét az n sorrendű permutációnak nevezik.
Tekintsük a készletet, ahol minden egyes elemet csak egyszer mutatnak be. Ezután a készlet egy-egy mappáját önmagára az n fokú permutációnak nevezik.
Az n-edik teljesítmény halmazát jelölik.
A kapcsolat bináris, ezért szokásos helyettesíteni egy kétsoros mátrixot, amelynek első sorában az előképeket írják, és a második - képükben:
Ha prototípus (érvek) vannak elhelyezve növekvő sorrendben (a belépési helyettesítése az ilyen úgynevezett kanonikus. Ha nem érvek vannak írva emelkedő sorrendben, majd átrendezve az oszlopok (ebben az esetben maga a helyettesítés nem változott, de csak sorrendjét megváltoztatjuk megfelelések kiejtés) lehet a felső sorban rendezett formához vezet:
Ha lehetséges, a kanonikus rekordot használjuk. Ilyen rekordot tapasztaltunk, amikor n elemek permutációját regisztráltuk. Felhívjuk a figyelmet arra, hogy a permutáció előképe tetszőleges véges készlet, és a helyettesítés előképe szükséges.
Azt találjuk, a számos különböző lehetséges permutációinak mértékben n. Mivel minden egyes kanonikus egyenértékű helyettesítéseket megfelelő permutáció, permutációinak számát n-ed-fokú egyenlő permutációinak számát az n elem, m. E. A készlet áll az elemek.
Térjünk vissza Thomashoz. A kulcs helyettesítésével
titkosította az egyik szóból álló üzenetet, és elküldte egy barátnak. A titkosítatlan üzenet, amely újra titkosítva van, de egy másik kulccsal
Megfejteni ezt az üzenetet. , "Bor"
A dekódolási folyamat sokkal gyorsabban hajtható végre, ha tudod, hogyan történik egy algebrai művelet kicseréléseken. Ezt a műveletet helyettesítések sokszorosításának nevezik. (Ha akarod, másképp nevezheted el, mert semmi köze a szokásos számok sokszorosításához).
Nézzünk egy példát arra, hogyan működik. Szorozzuk meg azokat a permutációkat, amelyekkel az üzenet Thomashez titkosítva:
A szorzási eljárás egymást követő helyettesítésre szorul.
Az első helyettesítés (A): 1 → 5;
a második helyettesítésben (B). 5 → 1;
Ennek eredményeképpen: 1 → 1.
Hasonlóképpen a "2 → 2" és a "2 → 3" -ból következik: "2 → 3". Három további típusú érv elvégzésével termékcserét kapunk
Az AV kódolással történő helyettesítésével egyszerűen "Thomas" üzenetet dekódolhatunk "egy lépésben". Ugyanakkor önmagát is irányíthatja (VA = "pump")
Ha érdekel, akkor jöhet a saját helyettesítési üzenet titkosításaival, és tarthatja a titkos levelezést barátaival.
Az üzenetek megfejtése során ismerkedett meg az algebrai műveletekkel az új objektumok helyettesítésével. Ha bármelyikőtök nem csak a titkosítást érdekli, hanem az Ön helyettesítésével, akkor jobban megismerheti őket, ha elvégzi a következő feladatokat.
CÍMKÉZÉS 1. Találjon helyettesítő művet:
CÍMKÉZÉS 2. Keresse meg a fenti A és B helyettesítések BA értékét. A BA helyettesítés kódolásként dekódolja újra a "snoas" üzenetet. Hasonlítsa össze az eredményt az előző átirat eredményével. Ezt követően elmondhatja, hogy a helyettesítések szorzata a kommutativitás tulajdonsággal rendelkezik-e.
Tegyük fel, hogy két permutációt adunk meg, és