Klasyczna kryptologia wstęP. Proste kryptosystemy



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

Szyfr Vigenere’a

W szyfrach podstawieniowych każda litera tekstu jawnego zamieniana jest na tylko jedną literę szyfrogramu. Kryptosytemy o tej własności nazywane są monoalfabetycznymi. Przedstawimy teraz szyfr Vigenere’a (dyplomata francuski Blaise de Vigenere żył w latach 1523-1596), w którym poszczególne litery tekstu jawnego mogą być przekształcone na różne litery alfabetu szyfrogramu. Określony przez niego kryptosystem należy do kategorii polialfabetycznych. Niech będzie ustaloną liczbą naturalną. Przyjmujemy



.

Dla klucza definiujemy przekształcenie szyfrujące



i przekształcenie deszyfrujące



gdzie działania arytmetyczne wykonujemy modulo 26.



Widzimy, że przy pomocy m-literowego klucza k szyfrujemy ciąg m liter tekstu jawnego i każda litera może być zaszyfrowana na m różnych liter szyfrogramu; z tego względu szyfr Vigenere’a należy do kategorii szyfrów polialfabetycznych.
Liczba możliwych kluczy w szyfrze Vigenere’a jest bardzo duża, równa jest . Dla przestrzeń klucza jest większa niż . Sprawdzenie takiej ilości kluczy jest zadaniem dla komputera, jednak istnieją metody kyptoanalizy, które umożliwiają złamanie szyfru Vigenere’a w czasie szybszym niż przeszukiwanie całej przestrzeni klucza.

Przykład



Tekst jawny

tenkr yptos ystem nieje stbez piecz ny



Szyfrogram

LDLPI QORTJ QRRJD FHCOV KSZJQ HHCHQ FX

Jeśli w szyfrze Vigenere’a długość użytego klucza równa jest długości tekstu jawnego to nazywamy go szyfrem z kluczem bieżącym. Jeśli dodatkowo klucz ten jest losowym ciągiem liter lub bitów oraz klucz jest użyty tylko jeden raz to jest to szyfr z kluczem jednokrotnym (one time pad). Szyfry te będą oddzielnie omawiane wraz z generatorami ciągów losowych.

Szyfr Hilla

W kryptosystemach opisanych powyżej szyfrowane są pojedyncze litery tekstu jawnego. W szyfsze Hilla wprowadzonym w 1929 roku szyfrowane są jednocześnie bloki m-literowe.

Niech m będzie liczbą naturalną, następnie

Metoda szyfrowania polega na wykorzystaniu m przekształceń liniowych m liter alfabetu tekstu jawnego; wtedy bloki m-literowe traktowane są jako jednostki tekstu jawnego.



Na przykład dla m=2 niech będzie elementem odpowiadającym elementem określonym wzorami

gdzie równości rozumiane są modulo 26. Powyższe wzory można zapisać w postaci macierzowej:



.

Kluczem przekształcenia szyfrującego jest macierz K o wymiarach 2  2. Natomiast kluczem deszyfrującym jest macierz odwrotna do macierzy K obliczona modulo 26:



.

Warunkiem istnienia macierzy odwrotnej jest to, aby wyznacznik macierzy K był liczbą względnie pierwszą z modułem 26. Zaszyfrujemy tekst jawny luty. Digramom lu i ty odpowiadają pary liczb (11,20) i (19,24). Po obliczeniach znajdujemy odpowiadające elementy szyfrogramu: (3,4) i (11,22) tzn. digramy: ZU i VI.



Dla dowolnego m kluczem w szyfrze Hilla jest odwracalna modulo 26 macierz K o wymiarach . Warunkiem odwracalności tej macierzy jest to, aby jej wyznacznik był liczbą względnie pierwszą z modułem 26. Jeśli i są odpowiednio jednostkami tekstu jawnego i szyfrogramu to przekształcenia szyfrujące i deszyfrujące w konwencji mnożenia macierzy mają postać:

dokładniej dla przekształcenia szyfrującego uwzględniając elementy klucza:



.

W tym miejscu wskażemy tylko, że istnieją metody kryptoanalizy szyfru Hilla.


Szyfr przestawieniowy

W omawianych wyżej szyfrach podstawieniowych poszczególne litery tekstu jawnego lub grupy literowe były zastępowane, przy ustalonym kluczu, przez określone litery lub grupy literowe szyfrogramu. W szyfrach przestawieniowych zwanych także szyframi permutacyjnymi elementy tekstu jawnego nie zmieniają się, natomiast zmienia się ich kolejność w tekście jawnym dając w efekcie odpowiedni szyfrogram. Powyższa różnica między szyframi podstawieniowymi i przestawieniowymi została wskazana dokładnie przez Giovami Porta w 1563 roku. Do opisu szyfrów przestawieniowych wygodniej jest używać liter tekstu jawnego a nie ich odpowiedników liczbowych.

Niech będzie ustaloną liczbą naturalną. Wtedy

gdzie jest alfabetem tekstu jawnego (np. 26-elementowym zbiorem liter), zaś przestrzeń klucza K składa się ze wszystkich permutacji zbioru {1,2,...,m}. Dla ustalonego klucza k będącego permutacją przekształcenie szyfrujące ma postać:



a przekształcenie deszyfrujące:



gdzie jest permutacją odwrotną do.


Przykład

Niech m = 6 i permutacja ma postać:



1

2

3

4

5

6

3

5

1

6

4

2

Szyfrując wiadomość:

Jestbr zydkap ogoda

otrzymujemy szyfrogram:

sbJrte dazpky oaoxdg

W celu uzyskania 3 grup 6-literowych dodajemy na końcu tekstu jawnego x.

Przedstawimy dwa przykłady praktycznego tworzenia szyfrów przestawieniowych. Dany jest tekst jawny kryptografia. Słowo to wpisujemy wierszami do macierzy


o wymiarach 4 3.

1

2

3

K

R

Y

P

T

O

G

R

A

F

I

A

Następnie odczytujemy wpisany tekst kolumnami w kolejności kolumn (2 1 3) otrzymując szyfrogram:

RTRIKPGFYOAA.

Możemy stosować różne odmiany tej metody:



  1. Odczytywanie z tablicy nie musi odbywać się kolumnami.

  2. Można korzystać z różnych figur geometrycznych.

  3. Można wykorzystywać siatki w danej figurze, a tekst jawny wpisuje się w określone miejsca figury, a całkowite wypełnienie siatki uzyskuje się przez obroty figury.

Przedstawimy wykorzystanie sposobu trzeciego. Kwadrat o wymiarach dzielimy na cztery kwadraty o wymiarach , których pola numerujemy ustaloną permutacją liczb 1,2,...,9.

1

2

3

7

4

1

4

5

6

8

5

2

7

8

9

9

6

3

3

6

9

9

8

7

2

5

8

6

5

4

1

4

7

3

2

1

Wycinamy teraz w sposób przypadkowy z tych czterech kwadratów 9 pól jednostkowych o numerach od 1 do 9. Otrzymujemy przykładowo następujący szablon:


1

2

3

7

4

1

4

5

6

8

5

2

7

8

9

9

6

3

3

6

9

9

8

7

2

5

8

6

5

4

1

4

7

3

2

1

w którym zakreślone pola oznaczają wycięte miejsca. Tekst jawny wpisujemy teraz wierszami w otwory szablonu, następnie obracamy szablon o 900 i wpisujemy dalej. Obracając szablon jeszcze dwukrotnie wypełniamy całą tablicę. Jeśli wymiary mniejszego kwadratu są możemy w ten sposób wpisać tekst o długości znaków. Kluczem tego szyfru jest szablon.



Szyfry przestawieniowe są szczególnym przypadkiem szyfrów Hilla. Niech będzie ustaloną permutacją zbioru . Definiujemy tzw. macierz permutacyjną o wymiarach następującymi wzorami:

Macierz ta zawiera w każdym wierszu i każdej kolumnie dokładnie jedną jedynkę. Permutacji odwrotnej odpowiada macierz odwrotna:



Macierz jest kluczem w odpowiadającym szyfrze Hilla. Dla podanego wyżej przykładu szyfru przedstawieniowego z m = 6 i podaną permutacją odpowiadająca macierz permutacyjna ma postać:



Natomiast macierz odwrotna określająca przekształcenie deszyfrujące ma postać:







1   2   3   4   5   6   7   8   9


©operacji.org 2017
wyślij wiadomość

    Strona główna