Szyfry afiniczne

Pierścień reszt modulo n

Symbolem $ \mathbb{Z}_n $ oznaczamy zbiór $ \{0,1,\dots,n-1\} $ reszt z dzielenia przez $ n $. Dla dowolnych dwóch elementów $ a, b $ zbioru $ \mathbb{Z}_n $ definiujemy działania $ +_n $ (dodawanie modulo n) oraz $ \cdot_n $ (mnożenie modulo n) w następujący sposób

$a +_n b$ – reszta z dzielenia liczby $a + b$ przez $n $

$a \cdot_n b$ – reszta z dzielenia liczby $a \cdot b$ przez $n $

innymi słowy klasyczną sumę $a + b$ oraz iloraz $a \cdot b$ redukujemy modulo $n $.
Przykładowo w zbiorze $ \mathbb{Z}_{12} $ reszt dzielenia przez 12:

$ 5 +_{12} 7 = 0 $, ponieważ $5 + 7 = 12 = 1 \cdot 12 + 0 $

$5 \cdot_{12} 7 = 11$, ponieważ $5\cdot 7 = 35 = 2 \cdot 12 + 11 $

Każde z działań posiada element neutralnie wpływający na jego wynik. Dla działania $ +_n $ jest nim 0, a dla działania $ \cdot_n $ takim elementem jest 1.
Dla każdego $ a \in \mathbb{Z}_n $ symbolem $ -a $ oznaczamy element do niego przeciwny oraz dla każdego $ a \in \mathbb{Z}_n $ takiego, że $ \textrm{NWD}(a,n) = 1 $ symbolem $ a^{-1} $ element do niego odwrotny. Zwróćmy uwagę, że:

$a +_n (-a) = (-a) +_n a = 0 $ oraz $a \cdot_n a^{-1} = a^{-1} \cdot_n a = 1 $

Ponadto:

$ -a = n - a $

Czyli w $ \mathbb{Z}_{12} $

$-5 = 7 $ oraz $-7 = 5$

Zbiór $ \mathbb{Z}_{n} $ z działaniami $ +_n, \cdot_n $ nazywamy pierścieniem reszt modulo n.
Nie każdy element zbioru $ \mathbb{Z}_{n} $ posiada element odwrotny. Istnieje wcześniej wspomniane proste kryterium mówiące nam o tym kiedy element $a$, należący do $ \mathbb{Z}_{n} $ posiada element odwrotny. Mianowicie gdy $ \textrm{NWD}(a,n) = 1 $ wtedy w zbiorze $ \mathbb{Z}_{n} $ istnieje element odwrotny $ a^{-1} $.

Algorytm wyznaczania elementu $ a^{-1} $ w pierścieniu $ \mathbb{Z}_{n} $ wygląda następująco:

Sprawdzamy, czy $ \textrm{NWD}(a,n) = 1 $,
Jeżeli $ \textrm{NWD}(a,n) \ne 1 $ to element odwrotny do elementu $a$ nie istnieje.
Jeżeli $ \textrm{NWD}(a,n) = 1 $ możemy wyznaczyć $ a^{-1} $ korzystając z algorytmu Euklidesa znajdując liczby $c$ oraz $d$ należące do zbioru $ \mathbb{Z}_{n} $ takie, że $$ 1 = c \cdot a + d \cdot n $$ redukując obydwie strony równania modulo $n$ otrzymujemy: $$ 1 = c \cdot_n a \ \ \ \textrm{czyli} \ \ \ a^{-1} = c $$

Przykładowo spróbujmy znaleźć element odwrotny do $5$ i $6$ w pierścieniu $ \mathbb{Z}_{12} $
$ \textrm{NWD} (6, 12) = 6 \ne 1 \ $ nie istnieje $\ 6^{-1} $
$ \textrm{NWD} (5,12) = 1 $ $ 5^{-1} = 5 \ $ ponieważ $1 = 5 \cdot 5 + (-2) \cdot 12 $

Szyfry afiniczne

Zajmijmy się funkcją przekształcającą pierścień $ \mathbb{Z}_{n} $ na samego siebie, która ma postać

$ f(x) = ax +_n b $ gdzie $ a, b \in \mathbb{Z}_n $.

Chcemy, aby dla funkcji $f$ istniało dodatkowo odwzorowanie $g(x) = f^{-1}(x)$, które ma następujące własności:

dowolny element $x$ należący do $ \mathbb{Z}_{n} $ przekształcamy funkcją $f$ w wyniku otrzymując $y = f(x)$,
następnie element $y$ przekształcamy funkcją $g$, i w wyniku jej działania otrzymujemy z powrotem element $x$:
$g(y) = x$. $$ x \xrightarrow{\quad f\quad } y = f(x) \xrightarrow{\quad g \quad} g(y) = x $$

Jeżeli znajdziemy parę takich odwzorowań funkcję $f$ będziemy nazywać funkcją szyfrującą, a funkcję $g$ funkcją deszyfrującą.

Okazuje się, że istnieje proste kryterium, które pozwoli nam odpowiedzieć na pytanie czy dla danej funkcji szyfrującej $$ f(x) = ax +_n b $$ istnieje funkcja deszyfrująca $g(x)$.
Funkcja $f(x) = ax +_n b$ posiada odwzorowanie odwrotne $g(x)$ wtedy i tylko wtedy gdy $\textrm{NWD}(a, n) = 1$. Odwzorowanie $g(x)$ ma następującą postać $$ g(x) = a^{-1} x - a^{-1} b.$$ Funkcje szyfrujące w dowolnym pierścieniu $ \mathbb{Z}_{n} $ wyznaczamy z wykorzystaniem algorytmów Euklidesa.

Sprawdzamy czy funkcja $f(x) = 6x +_{26} 3 $ posiada funkcję odwrotną w pierścieniu $ \mathbb{Z}_{26} $.
$\textrm{NWD}(6, 26) = 2$, co oznacza, że funkcja ta nie posiada funkcji odwrotnej.

Sprawdźmy teraz, czy funkcja $f(x) = 9x +_{26} 3$ posiada funkcję odwrotną w pierścieniu $ \mathbb{Z}_{26} $

$\textrm{NWD}(9,26) = 1 $ stąd $$ 9^{-1} = 3 $$ $$ g(x) = 3x -3 \cdot 3 $$ $$ g(x) = 3x +_{26} (-9) $$ $$ g(x) = 3x +_{26} 17 $$

Zaszyfrujmy tekst INFORMATYKA przy pomocy szyfru afinicznego $f(x) = 9x +_{26} 3 $.

$${\small \begin{array}{|r|c|c|c|c|c|c|c|c|c|c|c|}\hline \textrm{Tekst jawny} & I & N & F & O & R & M & A & T & Y & K & A\\ \hline \textrm{Prezentacja liczbowa} & 8 & 13 & 5 & 14 & 17 & 12 & 0 & 19 & 24 & 10 & 0\\ \hline f(x) = 9x +_{26} 3 & 9\cdot8+3 & 9\cdot13+3 & 9\cdot5+3 & 9\cdot14+3 & 9\cdot17+3 & 9\cdot12+3 & 9\cdot0+3 & 9\cdot19+3 & 9\cdot24+3 & 9\cdot10+3 & 9\cdot0+3\\ \hline \textrm{Prezentacja liczbowa} & 23 & 16 & 22 & 25 & 0 & 7 & 3 & 18 & 11 & 15 & 3\\ \hline \textrm{Szyfrogram} & X & Q & W & Z & A & H & D & S & L & P & D\\ \hline \end{array} } $$ Deszyfrowanie $${\small \begin{array}{|r|c|c|c|c|c|c|c|c|c|c|c|}\hline \textrm{Szyfrogram} & X & Q & W & Z & A & H & D & S & L & P & D\\ \hline \textrm{Prezentacja liczbowa} & 23 & 16 & 22 & 25 & 0 & 7 & 3 & 18 & 11 & 15 & 3\\ \hline g(x) = 3x +_{26} 17 & 3\cdot23+17 & 3\cdot16+17 & 3\cdot22+17 & 3\cdot25+17 & 3\cdot0+17 & 3\cdot7+17 & 3\cdot3+17 & 3\cdot18+17 & 3\cdot11+17 & 3\cdot15+17 & 3\cdot3+17\\ \hline \textrm{Prezentacja liczbowa} & 8 & 13 & 5 & 14 & 17 & 12 & 0 & 19 & 24 & 10 & 0\\ \hline \textrm{Tekst jawny} & I & N & F & O & R & M & A & T & Y & K & A\\ \hline \end{array} } $$

Zaszyfruj

${}$

Odszyfruj

${}$