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+b\ \mod \ m,$ 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 y\mod \ m$

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-b\mod \ m.$

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 y\mod \ m$

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 {NWD} (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 {NWD} (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)\mod m,$

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

Wzór wynika z wyliczeń:

${\begin{aligned}{\mbox{D}}({\mbox{E}}(x))&=a^{-1}({\mbox{E}}(x)-b)\mod {m}\\&=a^{-1}(((ax+b)\mod {m})-b)\mod {m}\\&=a^{-1}(ax+b-b)\mod {m}\\&=a^{-1}ax\mod {m}\\&=x\mod {m}.\end{aligned}}$

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+5\mod 26=75\mod 26=23$

$14*7+5\mod 26=103\mod 26=25$

$19*7+5\mod 26=138\mod 26=8$

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

Deszyfrowanie:

$7^{-1}\mod 26=15$

Funkcja deszyfrująca ma postać:

$d(y)=15*(y-5)\mod 26$

$15*(23-5)\mod 26=270\mod 26=10$

$15*(25-5)\mod 26=300\mod 26=14$

$15*(8-5)\mod 26=45\mod 26=19$

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

Zobacz też

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