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:

${\displaystyle f(x)=ax+b\ \mod \ m,}$ gdzie

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

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

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

${\displaystyle ax+b\equiv y\mod \ m}$

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

${\displaystyle ax\equiv y-b\mod \ m.}$

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

${\displaystyle ax\equiv y\mod \ m}$

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

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

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

Parametr ${\displaystyle b}$ może być dowolny toteż mamy ${\displaystyle 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:

${\displaystyle d(y)=a^{-1}*(y-b)\mod m,}$

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

Wzór wynika z wyliczeń:

${\displaystyle {\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ć:

${\displaystyle e(x)=7x+5}$

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

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

Szyfrowanie:

${\displaystyle 10*7+5\mod 26=75\mod 26=23}$

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

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

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

Deszyfrowanie:

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

Funkcja deszyfrująca ma postać:

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

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

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

${\displaystyle 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