Kryptografia-wyklad_06.pdf

Wykład 6

Szyfrowanie aniczne

6.1 Szyfr aniczny dla monogramów

Założenie: Korzystamy z m literowgo alfabetu, który utożsamiamy ze zbiorem Z m .

W szczególności: alfabet łaciński utożsamiamy ze zbiorem

Z 26 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

Denicja 6.1. Szyfrem anicznym (dla monogramów) nazywamy kryptosystem, w któ

rym

P = C = Z m , K = Z m × Z m ,

i dla każdego klucza k = (a, b) ∈ K funkcja szyfrująca zdeniowana jest wzorem

∀ x2P E k (x) = a m x + m b,

zaś funkcja deszyfrująca jest określona następująco

∀ y2C D k (y) = a m (y + m (m − b)),

gdzie a = a −1

mod m.

Funkcje E k i D k można równoważnie zapisać tak:

∀ x2P E k (x) = (ax + b) MOD m oraz ∀ y2C D k (y) = (a(y − b)) MOD m.

Twierdzenie 6.1. Szyfr aniczny jest poprawnie określonym systemem kryptogracz

nym.

Przykład 6.1. Dla alfabetu łacińskiego: m = 26, a więc

P = C = Z 26 .

Klucz: k = (11, 24).

Tekst jawny: ja.

Ponieważ j = 9 i a = 0, więc

E k (j) = E k (9) = (11 9 + 24) MOD 26 = 19 = T

oraz

E k (a) = E k (0) = (11 0 + 24) MOD 26 = 24 = Y.

Tekst tajny: TY.

6.2 Szyfr Hilla

Niech M n (Z m ) będzie zbiorem wszystkich macierzy kwadratowych stopnia n o wyrazach

ze zbioru Z m . W zbiorze tym wprowadzamy działanie mnożenia macierzy modulo m

przyjmując dla dowolnych macierzy A, B ∈ M n (Z m ):

A m B = AB MOD 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.

Denicja 6.2. Macierzą odwrotną modulo m do macierzy A ∈

M n (Z m ) nazywamy

taką macierz B ∈

M n (Z m ) (o ile istnieje), że A m B = B m A =

I n i oznaczmy ją

symbolem A −1

mod m lub, krócej, A.

Fakt: Macierz odwrotna modulo m do macierzy A = [a ij ] ∈

M n (Z m ) istnieje wtedy i

tylko wtedy, gdy det A⊥m i wówczas

A −1

mod m = ((det A) −1

mod m) m [D ij MOD m] T

gdzie D ij oznacza dopełnienie algebraiczne elementu a ij macierzy A.

Denicja 6.3. Szyfrem Hilla dla ngramów nazywamy kryptosystem, w którym

P = C = (Z m ) n , K = {A ∈ M n×n (Z m ) : det A⊥m}

i dla każdego klucza A ∈ K funkcja szyfrująca zdeniowana jest wzorem

∀ x2P E A (x) = A m x,

zaś funkcja deszyfrująca jest określona następująco

∀ y2C D A (y) = A m y,

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

1 5

A =

Ponieważ det A = 9⊥26 oraz 9 −1

mod 26 = 3, więc

5 25

15 23

A −1

mod 26 = 3 26

Tekst jawny: anna, czyli 0 13 13 0.

Dzielimy to słowo na dwa bloki dwuliterowe i szyfrujemy:

2 1

1 5

E A (a n) = E A (0 13) =

2 1

1 5

E A (n a) = E A (13 0) =

Tekst tajny: 13 13 0 13 czyli NNAN.

6.3 Odwzorowania liniowe i aniczne modulo m

Denicja 6.4. Niech m, n, p będą liczbami naturalnymi. Funkcję f : (Z m ) n → (Z m ) p

nazywamy odwzorowaniem anicznym (modulo m), jeżeli istnieje taka macierz wymiaru

n × p o wyrazach z Z m i istnieje taki wektor b ∈ (Z m ) p , że

∀ x2(Z m ) n f (x) = A m x + m b.

Jeżeli b = , to odwzorowanie f nazywamy liniowym.

Denicja 6.5. Niech m, n ∈ N. Szyfrem anicznym modulo m dla bloków długości n

(czyli tzw. ngramów) nazywamy kryptosystem, w którym

• P = C = (Z m ) n ,

• K = {(A, b) : A ∈ M n (Z m ) ∧ b ∈ (Z m ) n

∧ det A⊥m},

• dla każdego (A, b) ∈ K funkcja szyfrująca E (A, b) jest odwzorowaniem anicznym

postaci x → A m x + m b.

Jeżeli K = {A : A ∈ M n (Z m ) ∧ 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 = (k 1 , k 2 , . . . , k n ) dla bloków o długości n

jest szyfrem anicznym o jednostkowej macierzy szyfrującej, tzn. jego funkcją szyfrującą

i deszyfrującą są odwzorowania

∀ x2(Z m ) n E k (x) = x + k MOD m

oraz

∀ x2(Z m ) n D k (x) = x − k MOD m.

Przykład 6.4. Szyfr Hilla jest szyfrem liniowym.

6.4 Szyfr przestawieniowy

Denicja 6.6. Dla n ∈ N niech S n oznacza zbiór wszystkich permutacji nwyrazowych.

Niech m ∈ N i przyjmijmy

• P = C = (Z m ) n ,

• K = S n ,

• dla każdej permutacji ∈ K funkcja szyfrująca E jest permutacją liter w bloku

długości n:

∀ x2P E (x 1 x 2 . . . x n ) = x (1) x (2) . . . x (n) ,

• dla każdej permutacji ∈ K funkcją deszyfrującą D jest funkcja E −1 .

Ł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.

6.5 Bezpieczeństwo

Twierdzenie 6.3. Dla wyznaczenia macierzy szyfrującej szyfru Hilla dla bloków długo

ści n o wyrazach z (Z m ) n wystarczy znajomość n tekstów jawnych x 1 , x 2 , . . . , x n (wraz

z odpowiadającymi im kryptogramami y 1 , y 2 , . . . , y n ) takich, że wyznacznik macierzy

X =

x 1

x 2

. . . x n

jest względnie pierwszy z liczbą m.

Twierdzenie 6.4. Dla wyznaczenia klucza (A, b) szyfru anicznego dla bloków długości

n o wyrazach z (Z m ) n wystarczy znajomość n + 1 tekstów jawnych x 0 , x 1 , . . . , x n (wraz

z odpowiadającymi im kryptogramami y 0 , y 1 , . . . , y n ) takich, że wyznacznik macierzy

X =

x 1 − x 0

x 2 − x 0

. . . x n − x 0

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 Z 26 .

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

11 0

1 19

X =

Y =

Ponieważ det X = −55⊥26, więc macierz X jest odwracalna modulo 26:

0 15

X −1

mod 26 =

Wobec tego

1 19

0 15

9 15

A = Y 26 (X −1

mod 26) =

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: