Szyfr afiniczny

Szyfr afiniczny – szyfr należący do grupy monoalfabetycznych szyfrów podstawieniowych.

Rodzina szyfrów monoalfabetycznych posiada jedną bardzo ważną cechę, a mianowicie jednej literze alfabetu jawnego odpowiada dokładnie jedna litera alfabetu tajnego. Funkcja szyfrująca wygląda następująco:

$f(x)=ax+bmodm,$ gdzie

$x$ to szyfrowana litera, $(a,b)$ jest kluczem, a $m$ to liczba liter w alfabecie (zwykle korzystamy z $m=26$ bo tyle liter ma język angielski)

Łatwo zauważyć, że jeśli $a=1,$ to mamy do czynienia ze zwykłym przesunięciem.

Szyfr afiniczny ma sens tylko wtedy, gdy funkcja afiniczna $f$ jest różnowartościowa, tzn. gdy dla dowolnego y należącego do zbioru klas reszt ${\mathbb{Z}}_m$ równanie

$ax+b\equiv ymodm$

ma co najwyżej jedno rozwiązanie ze względu na zmienną $x.$ Zapiszmy nasze równanie w sposób następujący:

$ax\equiv y-bmodm.$

Zauważmy, że gdy wartości $y$ przebiegają cały zbiór ${\mathbb{Z}}_m,$ to i wartości $y-b$ się wyczerpują, czyli wystarczy jeśli zbadamy rozwiązywalność równań

$ax\equiv ymodm$

dla $y\in {\mathbb{Z}}_m.$ Równanie to ma dokładnie jedno rozwiązanie dla każdego $y\in {\mathbb{Z}}_m$ wtedy i tylko wtedy, gdy $\mathrm{N}\mathrm{W}\mathrm{D}(a,m)=1$ (gdzie NWD oznacza największy wspólny dzielnik dwóch liczb).

Na przykład gdy $m=26=2\cdot 13$ to wartości $a$ należące do ${\mathbb{Z}}_{26}$ dla których $\mathrm{N}\mathrm{W}\mathrm{D}(a,26)=1$ są następujące:

1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25.

Parametr $b$ może być dowolny toteż mamy $12\cdot 26=312$ możliwych kluczy. Jest to bardzo mała liczba kluczy, która nie daje odpowiedniego bezpieczeństwa, toteż szyfr ten nie jest w zasadzie stosowany.

Funkcja deszyfrująca dla tego szyfru wygląda tak:

$d(y)=a^{-1}*(y-b)modm,$

gdzie $a^{-1}$ jest odwrotnością $a$ w pierścieniu ${\mathbb{Z}}_{26}.$

Wzór wynika z wyliczeń:

$\begin{array}{cc}\text{D}(\text{E}(x))& =a^{-1}(\text{E}(x)-b)modm\\ & =a^{-1}(((ax+b)modm)-b)modm\\ & =a^{-1}(ax+b-b)modm\\ & =a^{-1}axmodm\\ & =xmodm.\end{array}$

Przykład działania

Przyjmując, że K = (7, 5) należy zaszyfrować i odszyfrować słowo KOT.

Dla uproszenia korzystamy z mod 26 (alfabet angielski ma 26 znaków). Funkcja szyfrująca ma postać:

$e(x)=7x+5$

Zmieniamy litery wyrazu „kot” na wartości liczbowe:

K = 10; O = 14; T = 19;

Szyfrowanie:

$10*7+5mod26=75mod26=23$

$14*7+5mod26=103mod26=25$

$19*7+5mod26=138mod26=8$

Tekst zaszyfrowany odpowiada ciągowi 23, 25, 8, czyli: XZI.

Deszyfrowanie:

$7^{-1}mod26=15$

Funkcja deszyfrująca ma postać:

$d(y)=15*(y-5)mod26$

$15*(23-5)mod26=270mod26=10$

$15*(25-5)mod26=300mod26=14$

$15*(8-5)mod26=45mod26=19$

Ciąg liczb 10, 14, 19 odpowiada naszemu wyjściowemu KOT.

Zobacz też

• szyfr Cezara
• szyfr polialfabetyczny
• szyfr Vigenère’a