Utasítások
Készítsd el az affin rejtjel implementációját, amely egy ősi, a Közel-Keleten kialakult titkosítási rendszer.
Az affin rejtjel a monoalfabetikus helyettesítő rejtjelek egyik fajtája.
Minden karaktert leképezünk a numerikus megfelelőjére, egy matematikai függvénnyel titkosítjuk, majd átalakítjuk az új numerikus értékének megfelelő betűvé.
Bár minden monoalfabetikus rejtjel gyenge, az affin rejtjel sokkal erősebb, mint az Atbash rejtjel, mert jóval több kulcsa van.
Titkosítás
A titkosítási függvény a következő:
E(x) = (ai + b) mod m
Ahol:
-
i a betű indexe 0-tól az ábécé hossza mínusz 1-ig.
-
m az ábécé hossza.
A latin ábécé esetén m értéke 26.
-
a és b egész számok, amelyek a titkosítási kulcsot alkotják.
Az a és m értékének relatív prímnek (vagy kölcsönösen prímnek) kell lennie ahhoz, hogy az automatikus visszafejtés sikerüljön, azaz hogy az 1 legyen az egyetlen közös osztójuk (további információt a Wikipédia relatív prím egészekről szóló cikkében találsz).
Ha a nem relatív prím m-hez, a programodnak jeleznie kell, hogy ez hiba.
Ellenkező esetben a megadott kulccsal kell titkosítania vagy visszafejtenie.
A feladat szempontjából a számjegyek érvényes bemenetnek számítanak, de nem titkosítjuk őket.
A szóközök és az írásjelek kimaradnak.
A rejtjelezett szöveget rögzített hosszúságú, szóközzel elválasztott csoportokban írjuk ki, a hagyományos csoportméret 5 betű.
Így nehezebb a szóhatárok alapján kitalálni a titkosított szöveget.
Visszafejtés
A visszafejtési függvény a következő:
D(y) = (a^-1)(y - b) mod m
Ahol:
-
y egy titkosított betű numerikus értéke, azaz y = E(x)
- fontos megjegyezni, hogy
a^-1 az a mod m moduláris multiplikatív inverze (MMI)
- a moduláris multiplikatív inverz csak akkor létezik, ha
a és m relatív prím.
Az a MMI-je az az x, amelyre igaz, hogy ax m-mel való osztásának maradéka 1:
ax mod m = 1
Ha többet szeretnél megtudni arról, hogyan találhatod meg a moduláris multiplikatív inverzet, és hogy mit is jelent, a kapcsolódó Wikipédia-cikkben olvashatsz róla.
Általános példák
- A
"test" titkosítása "ybty"-t adja az a = 5, b = 7 kulccsal
- A
"ybty" visszafejtése "test"-et adja az a = 5, b = 7 kulccsal
- A
"ybty" visszafejtése "lqul"-t adja a hibás a = 11, b = 7 kulccsal
- A
"kqlfd jzvgy tpaet icdhm rtwly kqlon ubstx" visszafejtése "thequickbrownfoxjumpsoverthelazydog"-ot adja az a = 19, b = 13 kulccsal
- A
"test" titkosítása az a = 18, b = 13 kulccsal hiba, mert a 18 és a 26 nem relatív prím
Példa a moduláris multiplikatív inverz (MMI) megtalálására
Az MMI megkeresése a = 15 esetén:
(15 * x) mod 26 = 1-
(15 * 7) mod 26 = 1, azaz 105 mod 26 = 1
- A
7 a 15 mod 26 MMI-je
