Wykład 6
Szyfrowanie afiniczne
6.1 Szyfr afiniczny dla monogramów
Założenie: Korzystamy z m literowgo alfabetu, który utożsamiamy ze zbiorem Zm.
W szczególności: alfabet łaciński utożsamiamy ze zbiorem Z26 przypisując literom
następujace wartości:
a 00 h 07 o 14 v 21
b 01 i 08 p 15 w 22
c 02 j 09 q 16 x 23
d 03 k 10 r 17 y 24
e 04 l 11 s 18 z 25
f 05 m 12 t 19
g 06 n 13 u 20
Definicja 6.1. Szyfrem afinicznym (dla monogramów) nazywamy kryptosystem, w któ-
rym
P = C = Zm, K = ZÄ„" × Zm,
m
i dla każdego klucza k = (a, b) " K funkcja szyfrująca zdefiniowana jest wzorem
"x"P Ek(x) = a · x +m b,
m
zaś funkcja deszyfrująca jest określona następująco
"y"C Dk(y) = a · (y +m (m - b)),
m
gdzie a = a-1 mod m.
17
Funkcje Ek i Dk można równoważnie zapisać tak:
"x"P Ek(x) = (ax + b) MOD m oraz "y"C Dk(y) = (a(y - b)) MOD m.
Twierdzenie 6.1. Szyfr afiniczny jest poprawnie określonym systemem kryptograficz-
nym.
Przykład 6.1. Dla alfabetu łacińskiego: m = 26, a więc
P = C = Z26.
Klucz: k = (11, 24).
Tekst jawny: ja.
Ponieważ j = 9 i a = 0, więc
Ek(j) = Ek(9) = (11 · 9 + 24) MOD 26 = 19 = T
oraz
Ek(a) = Ek(0) = (11 · 0 + 24) MOD 26 = 24 = Y.
Tekst tajny: TY.
6.2 Szyfr Hilla
Niech Mn(Zm) będzie zbiorem wszystkich macierzy kwadratowych stopnia n o wyrazach
ze zbioru Zm. W zbiorze tym wprowadzamy działanie mnożenia macierzy modulo m
przyjmujÄ…c dla dowolnych macierzy A, B " Mn(Zm):
A · B = AB MOD m,
m
gdzie po prawej stronie występuje zwykłe działanie mnożenia macierzy, a operacja brania
reszty odnosi się do każdego wyrazu macierzy AB.
Definicja 6.2. MacierzÄ… odwrotnÄ… modulo m do macierzy A " Mn(Zm) nazywamy
takÄ… macierz B " Mn(Zm) (o ile istnieje), że A · B = B · A = In i oznaczmy jÄ…
m m
symbolem A-1 mod m lub, krócej, A.
Fakt: Macierz odwrotna modulo m do macierzy A = [aij] " Mn(Zm) istnieje wtedy i
tylko wtedy, gdy det AĄ"m i wówczas
A-1 mod m = ((det A)-1 mod m) · [Dij MOD m]T ,
m
gdzie Dij oznacza dopełnienie algebraiczne elementu aij macierzy A.
18
Definicja 6.3. Szyfrem Hilla dla n-gramów nazywamy kryptosystem, w którym
P = C = (Zm)n, K = {A " Mn×n(Zm) : det AÄ„"m}
i dla każdego klucza A " K funkcja szyfrująca zdefiniowana jest wzorem
"x"P EA(x) = A · x,
m
zaś funkcja deszyfrująca jest określona następująco
"y"C DA(y) = A · y,
m
gdzie A = A-1 mod m oznacza macierz odwrotnÄ… do A modulo m.
Przykład 6.2. Niech m = 26 (alfabet łaciński). Załóżmy, że kluczem jest macierz
Klucz:
îÅ‚ Å‚Å‚
2 1
ðÅ‚ ûÅ‚
A = .
1 5
Ponieważ det A = 9Ą"26 oraz 9-1 mod 26 = 3, więc
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
5 25 15 23
ûÅ‚ ðÅ‚ ûÅ‚
A-1 mod 26 = 3 ·26 ðÅ‚ = .
25 2 23 6
Tekst jawny: anna, czyli 0 13 13 0.
Dzielimy to słowo na dwa bloki dwuliterowe i szyfrujemy:
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
2 1 0 13
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
EA(a n) = EA(0 13) = ·26 = ,
1 5 13 13
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
2 1 13 0
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
EA(n a) = EA(13 0) = ·26 = .
1 5 0 13
Tekst tajny: 13 13 0 13 czyli NNAN.
6.3 Odwzorowania liniowe i afiniczne modulo m
Definicja 6.4. Niech m, n, p będą liczbami naturalnymi. Funkcję f : (Zm)n (Zm)p
nazywamy odwzorowaniem afinicznym (modulo m), jeżeli istnieje taka macierz wymiaru
n × p o wyrazach z Zm i istnieje taki wektor b " (Zm)p, że
"x"(Z )n f(x) = A · x +m b.
m
m
Jeżeli b = ¸, to odwzorowanie f nazywamy liniowym.
19
Definicja 6.5. Niech m, n " N. Szyfrem afinicznym modulo m dla bloków długości n
(czyli tzw. n-gramów) nazywamy kryptosystem, w którym
" P = C = (Zm)n,
" K = {(A, b) : A " Mn(Zm) '" b " (Zm)n '" det AÄ„"m},
" dla każdego (A, b) " K funkcja szyfrująca E(A, b) jest odwzorowaniem afinicznym
postaci x A · x +m b.
m
Jeżeli K = {A : A " Mn(Zm) '" det AĄ"m} i funkcje szyfrujące są odwzorowaniami
liniowymi o macierzach ze zbioru K , to kryptosystem nazywamy liniowym.
Przykład 6.3. Szyfr Vigenere a z kluczem k = (k1, k2, . . . , kn) dla bloków o długości n
jest szyfrem afinicznym o jednostkowej macierzy szyfrujÄ…cej, tzn. jego funkcjÄ… szyfrujÄ…cÄ…
i deszyfrujÄ…cÄ… sÄ… odwzorowania
"x"(Z )n Ek(x) = x + k MOD m
m
oraz
"x"(Z )n Dk(x) = x - k MOD m.
m
Przykład 6.4. Szyfr Hilla jest szyfrem liniowym.
6.4 Szyfr przestawieniowy
Definicja 6.6. Dla n " N niech Sn oznacza zbiór wszystkich permutacji n-wyrazowych.
Niech m " N i przyjmijmy
" P = C = (Zm)n,
" K = Sn,
" dla każdej permutacji Ą " K funkcja szyfrująca EĄ jest permutacją liter w bloku
długości n:
"x"P EĄ(x1 x2 . . . xn) = xĄ(1) xĄ(2) . . . xĄ(n),
" dla każdej permutacji Ą " K funkcją deszyfrującą DĄ jest funkcja EĄ-1 .
A
atwo sprawdzić, że powyższe warunki określają poprawnie kryptosystem nazywany
szyfrem przestawieniowym dla bloków długości n.
Twierdzenie 6.2. Szyfr przestawieniowy dla bloków długości n jest szyfrem liniowym.
20
6.5 Bezpieczeństwo
Twierdzenie 6.3. Dla wyznaczenia macierzy szyfrującej szyfru Hilla dla bloków długo-
ści n o wyrazach z (Zm)n wystarczy znajomość n tekstów jawnych x1, x2, . . . , xn (wraz
z odpowiadającymi im kryptogramami y1, y2, . . . , yn) takich, że wyznacznik macierzy

X = x1 x2 . . . xn
jest względnie pierwszy z liczbą m.
Twierdzenie 6.4. Dla wyznaczenia klucza (A, b) szyfru afinicznego dla bloków długości
n o wyrazach z (Zm)n wystarczy znajomość n + 1 tekstów jawnych x0, x1, . . . , xn (wraz
z odpowiadającymi im kryptogramami y0, y1, . . . , yn) takich, że wyznacznik macierzy

X = x1 - x0 x2 - x0 . . . xn - x0
jest względnie pierwszy z liczbą m.
Przykład 6.5. Za pomocą szyfru Hilla szyfrujemy bloki dwuliterowe zapisane przy użyciu
dwudziestosześcioliterowego alfabetu utożsamianego z Z26.
Tekst jawny: alfa, czyli 0 11 5 0,
Tekst tajny: BETA, czyli 1 4 19 0.
Oznaczmy macierz szyfrujÄ…cÄ… przez A oraz
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
0 5 1 19
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
X = i Y = .
11 0 4 0
Ponieważ det X = -55Ą"26, więc macierz X jest odwracalna modulo 26:
îÅ‚ Å‚Å‚
0 15
ðÅ‚ ûÅ‚
X-1 mod 26 = .
21 0
Wobec tego
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
1 19 0 15 9 15
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
A = Y ·26 (X-1 mod 26) = ·26 = .
4 0 21 0 0 8
21