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 ${\rm 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 ${\rm 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{align} \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{align}$