Państwowa Wyższa Szkoła Zawodowa W Elblągu, Instytut Informatyki Stosowanej

Laboratorium Teoretycznych Podstaw Informatyki

str. 1

Państwowa Wyższa Szkoła Zawodowa W Elblągu

Instytut Informatyki Stosowanej

Sprawozdanie z

Laboratorium Ochrona Informacji

Grupa dziekańska:
PBDiOU
Grupa laboratoryjna:

Data oddania: 2010-03-13

Skład grupy:
1.Anna Pajewska
2.Sławek Własak
3.Zbyszek Macijewicz

Ocena:

KRYPTOGRAFIA

nauka o przekazywaniu informacji w sposób zabezpieczony przed niepowołanym dostępem. Kryptologię dzieli się
na:

* kryptografię (z gr. gráfo "pisać"), czyli naukę o układaniu systemów kryptograficznych,

* kryptoanalizę (gr. kryptós oraz – rozluźnić), czyli naukę o ich łamaniu.

Współcześnie kryptologia jest uznawana za gałąź zarówno matematyki, jak i informatyki; ponadto jest blisko
związana z teorią informacji, inżynierią oraz bezpieczeństwem komputerowym. Kryptologia ma szerokie
zastosowanie w społeczeństwach rozwiniętych technicznie; wykorzystuje się ją np. w rozwiązaniach
zapewniających bezpieczeństwo kart bankomatowych, haseł komputerowych i handlu elektronicznego.

Duża część teoretycznych prac w dziedzinie kryptografii dotyczy algorytmicznych podstaw kryptografii –
algorytmów mających podstawowe, użyteczne w kryptografii właściwości – i ich związków z innymi problemami
kryptograficznymi. Przykładowo: funkcja jednokierunkowa to funkcja, której wartości łatwo obliczyć, trudno
natomiast znaleźć wartości funkcji do niej odwrotnej.

Rozkład na czynniki lub faktoryzacja – proces, w którym dla danego obiektu znajduje się obiekty, takie że ich
iloczyn jest jemu równy, przez co są one w pewnym sensie od niego prostsze.

Faktoryzacja liczby całkowitej x, to znalezienie takich liczb całkowitych y

1

, y

2

, ..., y

n

, że ich iloczyn jest równy

danej liczbie: x = y_{1}y_{2}\cdots y_{n}, przy czym żadne z y

i

nie może być równe 1 lub x (tzw. faktoryzacja

trywialna).

Do algorytmicznych podstaw kryptografii zalicza się wszystkie algorytmy służące do szyfrowania. Jednym z takich
algorytmów jest RSA.

RSA - jeden z pierwszych i obecnie jeden z najpopularniejszych asymetrycznych algorytmów kryptograficznych,
zaprojektowany w 1977 przez Rona Rivesta, Adi Shamira oraz Leonarda Adlemana. Pierwszy, który można
stosować zarówno do szyfrowania jak i do podpisów cyfrowych. Bezpieczeństwo szyfrowania opiera się na
trudności faktoryzacji dużych liczb pierwszych. Jego nazwa pochodzi od pierwszych liter nazwisk jego twórców.

Państwowa Wyższa Szkoła Zawodowa W Elblągu, Instytut Informatyki Stosowanej

Laboratorium Teoretycznych Podstaw Informatyki

str. 2

Próby złamania

Pierwszą udaną faktoryzację RSA zakończono 2 grudnia 1999 roku w ramach konkursu The RSA Factoring
Challenge. Dotychczas największym kluczem RSA jaki rozłożono na czynniki pierwsze jest klucz 768-bitowy.
Liczby pierwsze zostały znalezione 12 grudnia 2009 a informacje o przeprowadzonej faktoryzacji opublikowano 7
stycznia 2010 roku. Wykorzystano do tego klaster komputerów; czas zużyty na obliczenia był o 2 rzędy wielkości
krótszy od prognozowanego. Potencjalnym zagrożeniem dla RSA jest skonstruowanie komputera kwantowego.

Generowanie klucza

W celu wygenerowania klucza prywatnego i publicznego wybieramy dwie duże liczby pierwsze p i q (najlepiej w
taki sposób, aby obie były tej samej długości - maksymalizuje to bezpieczeństwo klucza) oraz losowy klucz
szyfrujący e, taki, że e jak i (p-1)(q-1) są liczbami względnie pierwszymi. Klucz deszyfrujący d możemy obliczyć
stosując wzór:

d = e^{-1} \mod (p-1)(q-1).

Następnie obliczamy iloczyn wcześniej wybranych liczb pierwszych n = pq a liczby p oraz q utajniamy w taki
sposób, aby nikt nie wiedział, że zostały stworzone do wygenerowania kluczy. Od teraz liczba d jest kluczem
prywatnym, natomiast liczby e i n kluczami publicznymi.

Szyfrowanie i deszyfrowanie

Zanim zaszyfrujemy wiadomość dzielimy ją na bloki mi długości nie większej niż n a następnie każdy z bloków
szyfrujemy według wzoru:

c_{i} = m_{i}^e \mod n

Zaszyfrowana wiadomość będzie się składać z kolejnych bloków ci. Tak stworzony szyfrogram przekształcamy na
tekst jawny odszyfrowując kolejne blok ci według wzoru:

m_{i} = c_{i}^d \mod n.

Możliwe jest także zaszyfrowanie wiadomości za pomocą klucza tajnego d a następnie jej odszyfrowanie za pomocą
klucza publicznego e. To właśnie ta własność sprawia, że RSA może zostać wykorzystany do cyfrowego
podpisywania dokumentów.

Algorytm szyfrowania/deszyfrowania:

• tekst tajny oblicza się z zależności S=J

e

mod n (jest to sposób na szyfrowanie)

• tekst jawny oblicza się z zależności J=S

k

mod n (jest to sposób na odszyfrowanie)

Zadanie

Użyj RSA do zaszyfrowania i później odszyfrowania tekstu „Ochrona informacji”. Pokaż analitycznie (na papierze)
wszystkie kroki szyfrowania/deszyfrowania dla wszystkich liter powyższego tekstu.

Państwowa Wyższa Szkoła Zawodowa W Elblągu, Instytut Informatyki Stosowanej

Laboratorium Teoretycznych Podstaw Informatyki

str. 3

Dopisujemy kody ASCII do każdej litery

O – 79 c– 99 h – 104 r – 114 o – 111 n – 110 a – 97 I – 73 n – 110 f – 102 o – 111 r – 114 m – 109 a – 97 c – 99 j –
106 i – 105

Wybieramy dwie liczby pierwsze (bez reszty dzielą się przez 1 i samą siebie), dla uproszczenia obliczeń są to małe
liczby, np p=11 i q=17.

Teraz obliczamy iloczyn n=pq

n=11*17=187

Do zaszyfrowania wiadomosci potrzebujemy jeszcze jednej liczby do klucza szyfrującego e, np 7

Korzystając ze wzoru S=J

e

mod n szyfrujemy kolejne litery

O = 79

7

mod 187 =((79

4

mod 187) * (79

3

mod 187)) mod 187

Stąd: ((38950081 mod 187)*( 493039 mod 187)) mod 187 = (38*107) mod 187 = 4066 mod 187 = 139

O = 139

I dalej:

c = 99

7

mod 187 =((99

4

mod 187) * (99

3

mod 187)) mod 187= (132*143) mod 187 = 176

h = 104

7

mod 187 =((104

4

mod 187) * (104

3

mod 187)) mod 187= (152*59) mod 187 = 179

r = 114

7

mod 187 =((114

4

mod 187) * (114

3

mod 187)) mod 187 = (47*130) mod 187 = 126

o = 111

7

mod 187 =((111

4

mod 187) * (111

3

mod 187)) mod 187 = (67*100) mod 187 = 155

n = 110

7

mod 187 =((110

4

mod 187) * (110

3

mod 187)) mod 187= (33*121) mod 187 = 66

a = 97

7

mod 187 =((97

4

mod 187) * (97

3

mod 187)) mod 187=(115*113) mod 187 = 92

I = 73

7

mod 187 =((73

4

mod 187) * (73

3

mod 187)) mod 187= (47*57) mod 187 = 61

n = 110

7

mod 187 =((110

4

mod 187) * (110

3

mod 187)) mod 187= (33*121) mod 187 = 66

f = 102

7

mod 187 =((102

4

mod 187) * (102

3

mod 187)) mod 187 = (136*170) mod 187 = 119

o = 111

7

mod 187 =((111

4

mod 187) * (111

3

mod 187)) mod 187 = (67*100) mod 187 = 155

r = 114

7

mod 187 =((114

4

mod 187) * (114

3

mod 187)) mod 187 = (47*130) mod 187 = 126

m = 109

7

mod 187 =((109

4

mod 187) * (109

3

mod 187)) mod 187= (175*54) mod 187 = 100

a = 97

7

mod 187 =((97

4

mod 187) * (97

3

mod 187)) mod 187=(115*113) mod 187 = 92

c = 99

7

mod 187 =((99

4

mod 187) * (99

3

mod 187)) mod 187= ( 132*143) mod 187 = 176

j = 106

7

mod 187 =((106

4

mod 187) * (106

3

mod 187)) mod 187 = (69*13) mod 187 = 149

i = 105

7

mod 187 =((105

4

mod 187) * (105

3

mod 187)) mod 187= (64*95) mod 187 = 96

Państwowa Wyższa Szkoła Zawodowa W Elblągu, Instytut Informatyki Stosowanej

Laboratorium Teoretycznych Podstaw Informatyki

str. 4

Aby odwrócić działanie funkcji szyfrującej (czyli odszyfrować wiadomość) należy znać klucz prywatny, obliczamy
go ze wzoru k*e=1 mod(p-1)(q-1) czyli 7*k= 10*16+1 =161

k=161/7 = 23

Następnie używamy klucza prywatnego do deszyfrowania wiadomości przy użyciu J=S

k

mod n.

O = 139

23

mod 187 = 79

c = 176

23

mod 187 =99

h = 179

23

mod 187 =104

r = 126

23

mod 187 =114

o = 155

23

mod 187 =111

n = 66

23

mod 187 =110

a = 92

23

mod 187 =97

I = 61

23

mod 187 =73

n = 66

23

mod 187 =110

f = 119

23

mod 187 =102

o = 155

23

mod 187 =111

r = 126

23

mod 187 =114

m = 100

23

mod 187 =109

a = 92

23

mod 187 =97

c = 176

23

mod 187 =99

j = 149

23

mod 187 =106

i = 96

23

mod 187 =105

Znając tylko klucz publiczny nie obliczymy klucza prywatnego ponieważ do wyliczenia tego klucza potrzebne są
ilorazy z których składa się klucz publiczny.