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

Definicja 6.1.

Szyfrem afinicznym (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 zdefiniowana jest wzorem

∀

x∈P

E

k

(x) = a ·

m

x

+

m

b,

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

∀

y∈C

D

k

(y) = a ·

m

(y +

m

(m − b)),

gdzie a = a

−

1

mod m.

17

Funkcje E

k

i D

k

można równoważnie zapisać tak:

∀

x∈P

E

k

(x) = (ax + b) MOD m

oraz

∀

y∈C

D

k

(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

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

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

18

Definicja 6.3.

Szyfrem Hilla dla n-gramó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 zdefiniowana jest wzorem

∀

x∈P

E

A

(x) = A ·

m

x,

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

∀

y∈C

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:

A

=





2 1

1 5





.

Ponieważ det A = 9⊥26 oraz 9

−

1

mod 26 = 3, więc

A

−

1

mod 26 = 3 ·

26





5 25

25

2





=





15 23

23

6





.

Tekst jawny:

anna, czyli 0 13 13 0.

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

E

A

(a n) = E

A

(0 13) =





2

1

1

5





·

26





0

13





=





13

13





,

E

A

(n a) = E

A

(13 0) =





2

1

1

5





·

26





13

0





=





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 : (Z

m

)

n

→ (Z

m

)

p

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

n

× p o wyrazach z Z

m

i istnieje taki wektor b ∈ (Z

m

)

p

, że

∀

x∈

(Z

m

)

n

f

(x) = A ·

m

x

+

m

b.

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

= (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 afinicznym

postaci x 7→ 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 afinicznym o jednostkowej macierzy szyfrującej, tzn. jego funkcją szyfrującą

i deszyfrującą są odwzorowania

∀

x∈

(Z

m

)

n

E

k

(x) = x + k MOD m

oraz

∀

x∈

(Z

m

)

n

D

k

(x) = x − k MOD m.

Przykład 6.4. Szyfr Hilla jest szyfrem liniowym.

6.4

Szyfr przestawieniowy

Definicja 6.6.

Dla n ∈ N niech S

n

oznacza zbiór wszystkich permutacji n-wyrazowych.

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:

∀

x∈P

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.

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 (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

=

h

x

1

x

2

. . .

x

n

i

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 (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

=

h

x

1

− x

0

x

2

− x

0

. . .

x

n

− x

0

i

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

X

=





0

5

11 0





i

Y

=





1

19

4

0





.

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

X

−

1

mod 26 =





0 15

21

0





.

Wobec tego

A

= Y ·

26

(X

−

1

mod 26) =





1 19

4

0





·

26





0

15

21

0





=





9 15

0

8





.

21