Szyfr afiniczny

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Szyfr afinicznyszyfr 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}

Przykład działania[edytuj | edytuj kod]

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ż[edytuj | edytuj kod]