Z Ćwiczenia 29.03.2008, Zajęcia, II semestr 2008, Wstęp do kryptologii


Zaczniemy na dzisiejszych ćwiczeniach od arytmetyki modularnej i na poczateku nieco teorii. Na poczatek dzielenie z resztą. Przyjmijmy pewne oznaczenia: 0x01 graphic
(moduł), oraz a calkowite. Podzielić liczbę a przez n to znaczy dokonać takiego przedstawienia, że 0x01 graphic
, gdzie q (liczba wyznaczająca ile n się mieści w a) i r (reszta z dzielenia) są całkowite oraz 0x01 graphic
, gdzie 0x01 graphic
. Inaczej takie dzielenie można zapisac jako

r = a mod n. Jeśli mamy dwie liczby calkowite a i b, to wówczas:

0x01 graphic

Teraz jakie mamy własności relacji 0x01 graphic
przystawania mod n. Są trzy:

1. 0x01 graphic
- zwrotność

2. 0x01 graphic
- symetria

3. 0x01 graphic
- przechodniość

Relacja spełniająca te wszystkie własności nazywana jest relacją równoważności. I można tu dokonać takiej operacji abstrakcji, że tworzymy klasy relacji równoważności dzieląc zbiór Z przez tą relacje równoważności co zapisujemy: 0x01 graphic
. I ten zbiór 0x01 graphic
to są te wszystkie możliwe wartości tej reszty. I teraz w tym zbiorze 0x01 graphic
jeżeli określimy działanie dodawania 0x01 graphic
i przyjmiemy 0x01 graphic
, to 0x01 graphic
. Grupę (0x01 graphic
,0x01 graphic
) nazwiemy grupa abelową, jeśli działanie dodawania modularnego w tym zbiorze spełnia nastepujące cztery własności:

1. 0x01 graphic
- łączność

2. 0x01 graphic
, gdzie 0 to element neutralny

3. 0x01 graphic
, gdzie - a = n - a będzie elmentem przeciwnym

4. 0x01 graphic
- przemienność

Jeśli czwarty warunek nie będzie spełniony, a inne tak, to jest to zwykła grupa. Jeśli którykolwiek z pierwszych trzech warunków nie będize spełniony, to nie będize to grupa.

I teraz przejdźmy do przykładów kodowania słów w oparciu o tą właśnie arytmetykę modularną. Będziemy uzywali szyfrów przesuwających. Na początek zajmiemy się grupą 0x01 graphic
, gdzie 0x01 graphic
i n = 26. Oznacza to, że kodując jakis tekst bedziemy mieli do czynienia z alfabetem 26 znakowym, gdzie każdemu znakowi przypisana będzie okreslona pozycja. Plus oznacza, że kodując będziemy dokonywali pewnego przesunięcia pozycji w prawo. Zobaczmy najpierw, jak będzie wyglądał nasz alfabet składających się z n liter, gdzie każdej przypisana jest odpowiednia pozycja z zakresu od 0 do 26. Będzie to klasyczny alfabet literowy:

a b c d e f g h i j k l m n o p q r s t u v w x y z

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

I nasz klucz niech wynosi k = 7 co będzie oznaczać, że będziemy przesuwac w prawo każdą literke tekstu jawnego o 7. Będziemy zatem na każdej pozycji literki z tekst jawnego dokonywać takiej operacji: 0x01 graphic
. A zatem niech naszym tekstem jawnym, który będizemy szyfrowali będzie tekst obecnosc obowiazkowa. Zobaczmy, jakie pozycje będą przypisane każdej z tych liter słowa według alfabetu:

o b e c n o s c | o b o w i a z k o w a

14 1 4 2 13 14 18 2 | 14 1 14 22 8 0 25 10 14 22 0

No i teraz zakodujmy stosując działanie 0x01 graphic
:

v i l j u v z j | v i v d p h g r v d h

21 8 11 9 20 21 25 9 21 8 21 9 15 7 6 17 21 3 7

Teraz w jaki sposób rozszyfrować podany tekst. Zamiast odejmować 7, czyli przesyuwać w lewo, można to zrobić prościej. Wystarczy skorzystać z działania 0x01 graphic
. Zatem należy do tych pozycji co dodaliśmy dodać 19 i podzielić modularnie przez 26. Jeśli otrzymaliśmy znów tekst jawny, to wszystko w porzadku, natomiast jeśli tekst otrzymany nie zgadza się z tekstem jawnym to znaczy, ze pomylilismy się najprawdopodobniej w obliczeniach.

Przejdźmy teraz do zagadnienia związanego z mnożeniem modularnym. Będziemy operowali grupą 0x01 graphic
i dla tej grupy przyjmując a i b calkowite musza być spełnione takie własności, że 0x01 graphic
. I wykonamy trzy takie tabelki działań dla określonych zbiorów: 0x01 graphic
. Zbiór oznaczony gwiazdką oznaczać będzie zbiór z odjęciem jednego elementu - 0. W tabeli wymnożymy wszystkie elementy w nawiasie stosując wszystkie możliwe kombinacje i dzieląc każda z nich modulo n. A zatem:

1

2

3

4

1

1

2

3

4

2

2

4

1

3

3

3

1

4

2

4

4

3

2

1

1

2

3

4

5

1

1

2

3

4

5

2

2

4

0

2

4

3

3

0

3

0

3

4

4

2

0

4

2

5

5

4

3

2

1

Dla pierwszej tabeli stosujemy modulo 5, a dla drugiej - modulo 6. Jeśli a jest różne od 0 i b jest różne od 0, oraz a razy b jest równe 0 mod n to takie liczby nazywamy dzielnikami zera. Widzimy w pierwszym przypadku, że nie ma takich dzielników, zaś w drugim przypadku mamy cztery takie przypadki. No i jeszcze istnieje element odwrotny. W pierwszym przypadku są dwa takie przypadki, bo 1 razy 1 mod 5 = 1, oraz 4 razy 4 mod 5 = 1. W drugim też 2 - 1 razy 1 mod 6 = 1, oraz 5 razy 5 mod 6 = 1. Dla odwrotności musi być spełniony warynek, że a i b sa równe, oraz wynikiem działania na tych liczbach musi być zawsze 1.

Teraz takie zadanie domowe. Wszelkie zadania domowe mają zostać wykonane w osobnym zeszycie 32 - kartkowym i są obowiązkowe. Należy zbadać (0x01 graphic
), oraz 0x01 graphic
) modularnie - wykonac tabelę, sprawdzić dzielniki i elementy neutralne. Podobnie dla (0x01 graphic
), oraz 0x01 graphic
).

Teraz z kolei zajmiemy się szyfrem afinicznym będącym uogólnieniem szyfru przesuwającego, gdzie klucz k bedzie miał postać k = (a, b), gdzie 0x01 graphic
, oraz 0x01 graphic
. Zaszyfrowanie nie stanowi problemu, natomiast problem pojawia się przy deszyfracji. Wówczas przyjmujemy, że 0x01 graphic
, oraz:

0x01 graphic
, gdzie 0x01 graphic
.

I ostatnie zadanie domowe będzie polegało na zaszyfrowaniu jakiegoś teksu jawnego tą metodą i zdeszyfrowaniu zakodowanego tekstu przyjmując, że a będzie różne od 1, a b różne od 0.



Wyszukiwarka

Podobne podstrony:
DES, Zajęcia, II semestr 2008, Wstęp do kryptologii
Rozp. Ministra Zdrowia z dn. 29.03.2007 r., Polibuda, II semestr, Techologia oczyszczania wód i ście
Z Ćwiczenia 15.03.2008, Zajęcia, II semestr 2008, Analiza matematyczna
Z Ćwiczenia 01.03.2008, Zajęcia, II semestr 2008, Analiza matematyczna
Z Wykład 29.03.2008, Zajęcia, II semestr 2008, Matematyka dyskretna i logika
Z Wykład 15.03.2008, Zajęcia, II semestr 2008, Analiza matematyczna
Z Ćwiczenia 20.04.2008, Zajęcia, II semestr 2008, Teoria informacji i kodowania
PSYCHOLOGIA – ćwiczenia 02.03.2008, WSKFIT 2007-2012, II semestr, psychologia
Z Ćwiczenia 26.04.2008, Zajęcia, II semestr 2008, Analiza matematyczna
Z Wykład 01.03.2008, Zajęcia, II semestr 2008, Rachunek prawdopodobieństwa
Z Ćwiczenia 19.04.2008, Zajęcia, II semestr 2008, Algorytmy i struktury danych
Z Wykład 16.03.2008, Zajęcia, II semestr 2008, Techniki Internetowe
Z Ćwiczenia 05.04.2008, Zajęcia, II semestr 2008, Analiza matematyczna
Z Ćwiczenia 06.04.2008, Zajęcia, II semestr 2008, Matematyka dyskretna i logika
Z Ćwiczenia 01.06.2008, Zajęcia, II semestr 2008, Rachunek prawdopodobieństwa

więcej podobnych podstron