Klasyczna kryptologia wstęP. Proste kryptosystemy



Pobieranie 0,69 Mb.
Strona2/9
Data14.02.2018
Rozmiar0,69 Mb.
1   2   3   4   5   6   7   8   9

Arytmetyka modularna. Szyfr przesuwający



Przed opisem szyfru przesuwającego (shift cipher) dokonamy przeglądu podstawowych faktów z arytmetyki modularnej. Niech a i b będą liczbami całkowitymi zaś m liczbą naturalną. Piszemy wtedy , co czytamy a przystaje do b modulo m, jeśli m dzieli a-b. Liczbę m nazywamy modułem kongruencji . Jeśli podzielimy odpowiednio a i b przez m to otrzymamy



gdzie reszty z dzielenia spełniają warunek: . Nietrudno jest zauważyć, że wtedy i tylko wtedy gdy . Będziemy pisać dla oznaczenia reszty z dzielenia a przez m . Mamy wtedy, że wtedy i tylko wtedy gdy . Zastępując a przez , mówimy, że liczba całkowita a została zredukowana modulo m.

Opiszemy teraz arytmetykę modulo m. Oznaczmy przez Zm zbiór liczb całkowitych z określonymi działaniami dodawania + i mnożenia  w ten sposób, że wyniki rzeczywistych działań są redukowane modulo m.



Na przykład 1113  15(mod16), stąd 1113 = 15 w Z16. Powyższe działania w Zm mają podstawowe własności działań arytmetycznych:

  1. Dodawanie jest zamknięte: dla Zm , Zm.

  2. Dodawanie jest przemienne: .

  3. Dodawanie jest łączne: .

  4. Zero jest elementem neutralnym względem dodawania:

dla

  1. Elementem przeciwnym (odwrotnym) do jest : .

  2. Mnożenie jest zamknięte: dla .

  3. Mnożenie jest przemienne: .

  4. Mnożenie jest łączne: .

9. 1 jest elementem neutralnym względem mnożenia:

dla

10. Dodawanie i mnożenie są działaniami rozdzielnymi:

dla .

Zbiór Zm z dodawaniem tworzy strukturę algebraiczną zwaną grupą abelową (przemienną), natomiast Zm z działaniami dodawania i mnożenia jest pierścieniem.

Opiszemy teraz szyfr przesuwający. Odwołując się do ogólnej definicji kryptosystemu przyjmujemy



.

Dla klucza definiujemy



Wzięliśmy , ponieważ w języku angielskim jest 26 liter.

W celu szyfrowania tekstu zapisanego z użyciem alfabetu angielskiego numerujemy wpierw kolejne litery przez liczby 0,1,...,25:


A

B

C

D

E

F

G

H

I

J

K

L

M

0

1

2

3

4

5

6

7

8

9

10

11

12




N

0

P

Q

R

S

T

U

V

W

X

Y

Z

13

14

15

16

17

18

19

20

21

22

23

24

25.

Szyfrowanie polega na zastąpieniu danej litery przez literę leżącą k pozycji dalej w alfabecie traktowanym jako cykl zamknięty. Deszyfrowanie jest procesem odwrotnym. Dla k = 3 szyfr ten był oryginalnie używany przez Juliusza Cezara (żył w latach 100-40 p.n.e.).

Przykład

Weźmy szyfr przesuwający z i tekst jawny

spotk aniej utror ano.

Numerując kolejne litery otrzymujemy ciąg liczb:



18

15

14

19

10

0

13

8

4

9

20

19

17

14

17

0

13

14





Do każdej liczby dodajemy 11 dokonując ewentualnie redukcji modulo 26, w wyniku otrzymujemy ciąg liczb:

3

0

25

4

21

11

24

19

15

20

5

4

2

25

2

11

24

25





Zamieniamy teraz liczby na odpowiadające litery otrzymując szyfrogram:

DAZEV LYTPU FECZC LYZ.

W podawanych przykładach tekst jawny będziemy zapisywali przy pomocy liter małych, a szyfrogram przy pomocy liter dużych, pomijamy spacje i dzielimy ewentualnie oba teksty na grupy pięcioliterowe. Przy deszyfrowaniu wykonujemy proces odwrotny: po zamianie liter na liczby odejmujemy 11 modulo 26 i otrzymanym liczbom przyporządkowujemy litery otrzymując w efekcie tekst jawny.

Kryptosystem, który może mieć praktyczne zastosowanie musi spełniać pewne warunki, które sformułujemy wstępnie w następujący sposób:



  1. Funkcje szyfrująca i deszyfrująca muszą być łatwe i szybkie w obliczaniu.

  2. Kryptosystem musi być bezpieczny: przeciwnik (Oskar) znając algorytm szyfrujący i kryptogram y nie jest w stanie znaleźć klucza k czy też tekstu jawnego x. Określenie klucza k jest co najmniej tak trudne jak znalezienie tekstu jawnego.

Warunek 2 bezpieczeństwa kryptosystemu jest sformułowany w bardzo ogólny sposób. Opisany wyżej kryptosystem oparty na przesunięciu liter w alfabecie o stałą liczbę miejsc nie jest bezpieczny. Do jego złamania możemy kolejno sprawdzać wartości klucza k aż otrzymamy sensowny tekst jawny; średnio należy wykonać 26/2 = 13 prób. Opisana metoda kryptoanalizy nazywa się przeszukiwaniem przestrzeni klucza, stąd warunkiem koniecznym (ale nie dostatecznym) bezpieczeństwa kryptosystemu jest to, aby przestrzeń klucza była możliwie duża, co uniemożliwi jej przeszukanie w realnym czasie.



1   2   3   4   5   6   7   8   9


©operacji.org 2017
wyślij wiadomość

    Strona główna