Spis rzeczy

1 Pierwszy rzut oka na kryptogra

,

e

4

1.0.1 Szyfrowanie danych

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

4

1.0.2 Podstawowe zastosowania technik szyfrowania

:

:

:

:

:

:

:

:

:

5

1.0.3 Historia kryptograi

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

8

1.0.4 Kontrowersje zwi

,

azane ze stosowaniem kryptograi

:

:

:

:

:

:

9

1.0.5 Korzystanie z produkt ow kryptogracznych

:

:

:

:

:

:

:

:

:

:

10

2 Podstawowe techniki szyfrowania

12

2.0.6 Podstawienie

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

12

2.0.7 XOR i one-time pad

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

13

2.0.8 S-boksy

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

15

3 Algorytmy symetryczne

18

3.1 DES { Data Encryption Standard

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

18

3.1.1 Szyfrowanie DES-em

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

19

3.1.2 Deszyfrowanie DES-em

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

21

3.2 Trzykrotny DES

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

21

3.3 Szyfrowanie tekst ow dowolnej dlugo sci

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

21

3.3.1 Elektroniczna ksi

,

a_zka kodowa

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

22

3.3.2 Cipher Block Chaining

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

23

3.3.3 Cypher Feedback

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

23

3.4 IDEA

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

24

3.4.1 Szyfrowanie poprzez algorytm IDEA

:

:

:

:

:

:

:

:

:

:

:

:

:

:

25

3.4.2 Generowanie podkluczy dla algorytmu IDEA

:

:

:

:

:

:

:

:

:

25

3.4.3 Deszyfrowanie przez IDEA

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

25

4 Algorytmy niesymetryczne

29

4.0.4 Teoria zlo_zono sci obliczeniowej a kryptograa

:

:

:

:

:

:

:

:

:

29

4.0.5 Szyfry plecakowe

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

30

4.1 RSA

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

32

4.1.1 Opis algorytmu RSA

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

33

4.1.2 Testy pierwszo sci

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

35

4.1.3 Aspekty bezpiecze nstwa RSA

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

37

4.1.4 Trudne bity kryptogram ow RSA

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

39

4.2 Algorytm ElGamala

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

41

5 Funkcje jednokierunkowe

43

5.0.1 Kandydaci na funkcje jednokierunkowe

:

:

:

:

:

:

:

:

:

:

:

:

:

44

5.0.2 Hard-core bit

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

45

i

SPIS

RZECZY

ii

6 Jednokierunkowe funkcje hashuj

,

ace

46

6.0.3 Wlasno sci i zastosowania funkcji hashuj

,

acych

:

:

:

:

:

:

:

:

:

46

6.0.4 Ataki przeciw funkcjom hashuj

,

acym

:

:

:

:

:

:

:

:

:

:

:

:

:

:

47

6.1 Techniki o dowodliwych wlasno sciach

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

49

6.1.1 Hashowanie przy pomocy dyskretnego logarytmu

:

:

:

:

:

:

:

49

6.1.2 Rozszerzenie na teksty dowolnej dlugo sci

:

:

:

:

:

:

:

:

:

:

:

:

50

6.2 Praktyczne algorytmy hashuj

,

ace

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

51

6.2.1 MD5

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

51

6.2.2 Hashowanie dowolnie dlugich tekst ow

:

:

:

:

:

:

:

:

:

:

:

:

:

52

7 Ci

,

agi pseudolosowe

55

7.0.3 Wlasno sci ci

,

ag ow pseudolosowych

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

55

7.0.4 Generatory ci

,

ag ow pseudolosowych

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

57

7.0.5 Pseudolosowo s c generatora BBS

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

59

7.1 Zastosowania ci

,

ag ow pseudolosowych

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

59

7.1.1 Szyfrowanie strumieniowe

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

59

7.1.2 Szyfrowanie probabilistyczne

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

60

8 Podpisy cyfrowe

61

8.0.3 Podpisy cyfrowe ElGamala

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

62

8.0.4 DSA

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

63

8.0.5 Slepe podpisy

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

64

8.0.6 Kanal podprogowy

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

65

8.0.7 Podpisy niezaprzeczalne

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

66

9 Uwierzytelnianie

69

9.0.8 Protok ol challenge and response

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

69

9.0.9 Dowody interakcyjne

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

70

9.0.10 Dowody z wiedz

,

a zerow

,

a

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

71

9.0.11 Protok ol Fiege-Fiata-Shamira

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

73

9.0.12 Protok ol Schnorra

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

74

9.0.13 Protok ol Guillou-Quisquartera

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

75

9.0.14 Podpisy cyfrowe poprzez uwierzytelnianie

:

:

:

:

:

:

:

:

:

:

:

76

10 Administracja kluczami

77

10.1 Praktyka gospodarki kluczami

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

77

10.1.1 Urz

,

adzenie kryptograczne

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

77

10.1.2 Generowanie kluczy

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

78

10.1.3 Hierarchia kluczy

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

79

10.1.4 Przechowywanie kluczy

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

79

10.2 Protokoly uzgadniania kluczy

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

80

10.2.1 Uzgadnianie kluczy poprzez szyfrowanie symetryczne

:

:

:

:

:

81

10.2.2 Uzgadnianie klucza przez szyfrowanie asymetryczne

:

:

:

:

:

82

10.2.3 Protok ol Die-Hellmana i jego pochodne

:

:

:

:

:

:

:

:

:

:

:

82

11 Protokoly kryptogra
czne

85

11.0.4 Atak man in the middle

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

85

11.0.5 Dzielenie tajemnic

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

87

11.0.6 Zobowi

,

azanie bitowe

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

88

11.0.7 Pieni

,

adze cyfrowe

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

90

11.0.8 Elektroniczne wybory

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

93

SPIS

RZECZY

iii

12 Kryptoanaliza

95

12.0.9 Kryptoanaliza r o_znicowa

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

96

12.0.10Kryptoanaliza liniowa

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

99

12.0.11R o_znicowa kryptoanaliza bl

,

ed ow

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

100

13 Wybrane implementacje

102

13.0.12Smart cards

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

102

13.0.13Krzywe eliptyczne

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

103

13.0.14Kerberos

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

103

13.0.15Zabezpieczanie komunikacji telefonicznej

:

:

:

:

:

:

:

:

:

:

:

:

106

13.0.16PGP { Pretty Good Privacy

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

107

13.0.17Zabezpieczanie poczty elektronicznej { PEM

:

:

:

:

:

:

:

:

:

108

13.0.18Bezpiecze nstwo w WWW

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

109

13.0.19Protokoly obrotu nansowego

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

109

A Wybrane aspekty teorii liczb

112

B Teoria algorytmow

116

Przedmowa

Do niedawna kryptograa byla obiektem zainteresowania w wi

,

ekszym stopniu slu_zb

wywiadowczych i wojska ni_z przedmiot ow gospodarczych i prywatnych os ob. Post

,

ep

w dziedzinie elektroniki a zwlaszcza gwaltowny rozw oj sieci komputerowych sytuacj

,

e

t

,

e zmienily w radykalny spos ob.

Dawniej, gdy prywatny u_zytkownik dysponowal jedynie komputerem PC nie

wl

,

aczonym do sieci, ochrona danych byla stosunkowo prosta i zapewniona przez

zyczny dost

,

ep do komputera. Na tej samej zasadzie chronione byly dane przecho-

wywane w postaci elektronicznej przez male rmy, dzialy rm, organizacje politycz-

ne. Nie skomplikowaneprotokoly kryptograczne, ale klucz do pomieszczenia z kom-

puterem, czy koperta, w kt orej przesylana byla dyskietka, stanowily ochron

,

e przed

niepowolanym dost

,

epem. Oczywi scie zdarzaly si

,

e kradzie_ze dyskietek, komputer ow,

wlamania do siedzib partii politycznych

:

:

:

. Wi

,

ekszo s c u_zytkownik ow nie czulo

jednak potrzeby skuteczniejszej ochrony swych danych.

Sytuacja zacz

,

ela si

,

e radykalnie zmienia c z chwil

,

a gwaltownego wzrostu sieci

komputerowych. Dotyczylo to nie tylko sieci obejmuj

,

acych szereg dzial ow pojedyn-

czych rm, ale i sieci globalne, takie jak Internet (w tym zwlaszcza World Wide

Web). Zapewnienie bezpiecze nstwa w tych sieciach stalo si

,

e jednym z pierwszo-

planowych zada n decyduj

,

acych o ich dalszym rozwoju. Nowe techniki telekomu-

nikacyjne, takie jak telefonia kom orkowa, telewizja cyfrowa, telebanking, itp., nie

moglyby znale z c swego miejsca w codziennej praktyce, gdyby nie stosowanie technik

kryptogracznych dla ochrony dost

,

epu.

Najpierw rewolucja obj

,

ela komunikacj

,

e w srodowisku naukowym. Pojawienie

si

,

e poczty elektronicznej umo_zliwilo blyskawiczne kontaktowanie sie naukowc ow z

najdalszych kraj ow. Pozwolilo to na olbrzymi wzrost wydajno sci w wielu dziedzi-

nach bada n. Mo_znaby si

,

e spodziewa c, _ze konkurencja i ostra walka o przodownictwo

doprowadzi w srodowisku naukowym do wielu nadu_zy c poczty elektronicznej. Tym

bardziej, _ze nie jest trudne na przyklad przesla c list w ten spos ob, by nadawca po

nagl owku m ogl by c przekonany, _ze pochodzi on od innej osoby. Mo_zliwe jest r ownie_z

przechwytywanie korespondencji przeznaczonej do innych adresat ow. Zjawiska te

jednak stanowily dotychczas w calym srodowisku naukowymbardzo w

,

aski margines.

Powodem zapewne bylo to, i_z komunikowaly si

,

e osoby, kt ore i tak obdarzaly si

,

e

pelnym zaufaniem. Tak wi

,

ec metody, kt ore pozwalalyby na zabezpieczenie przed

odczytem, modykacj

,

a czy te_z preparowaniem list ow elektronicznych przez osoby

trzecie nie byly stosowane.

Te czasy min

,

ely. Wraz z pojawieniem si

,

e World Wide Web Internet stal si

,

e

atrakcyjny dla "szaregou_zytkownika\. WInternecie pojawilysi

,

e interesuj

,

ace zasoby

informacyjne, dzi

,

eki czemu ilo s c u_zytkownik ow zacz

,

ela rosn

,

a c gwaltownie. Co

wi

,

ecej, Internet coraz cz

,

e sciej jest u_zywany nie jako narz

,

edzie zabawy czy rozwijania

zainteresowa n, ale do cel ow komercyjnych. Ju_z dzi s bilety lotnicze kupuj

,

e przez

Internet, literatur

,

e naukow

,

a wybieram przez World Wide Web, a zamiast kupowa c

gazet

,

e z lokalnymi ogloszeniami si

,

egam do jej elektronicznego odpowiednika. W

takiej sytuacji b

,

edzie coraz wi

,

ecej os ob: hardware tanieje, software staje si

,

e coraz

latwiejszy do obslugi przez laika, w wielu krajach pol

,

aczenia telefoniczne wskutek

1

SPIS

RZECZY

2

konkurencji na rynku telekomunikacyjnym staj

,

a si

,

e ta nsze i wy_zszej jako sci. Coraz

latwiejsze b

,

edzie zatem stanie si

,

e kolejnym u_zytkownikiem Internetu. Za par

,

e lat

b

,

edziemy mie c zapewne do czynienia z sytuacj

,

a, gdy Internet b

,

edzie najwi

,

ekszym

supermarketem, najobszerniejsz

,

a gazet

,

a, najwi

,

ekszym Hyde Parkiem,

:

:

:

{przynaj-

mniej w krajach, gdzie uslugi telekomunikacyjne b

,

ed

,

a wystarczaj

,

aco tanie.

Jak ka_zdy wynalazek, rozw oj globalnych sieci komputerowych przynosi korzy sci,

ale i niebezpiecze nstwa. Wiele dyskutuje si

,

e na przyklad na temat mo_zliwo sci

wykorzystywania Internetu przez organizacje przest

,

epcze. Sytuacja przypomina

nieco spory po wynalezieniu samochodu. Nie spos ob cz

,

e sciowo nie przyzna c racji

przeciwnikom automobili maj

,

ac przed oczyma tragiczne statystki o tysi

,

acach ludzi

zabitych na drogach. Nie cofn

,

elo to jednak motoryzacji, tak jak nie do odwr ocenia

jest ju_z rozw oj globalnej sieci komputerowej na swiecie.

Poniewa_z poprzez Internet komunikowa c si

,

e b

,

ed

,

a nie dobrzy i ufaj

,

acy sobie

znajomi, lecz cz

,

esto anonimowi czy wrodzy sobie u_zytkownicy, mijaj

,

a czasy, gdy

niezbyt wiele my slano o bezpiecze nstwie danych i komunikacji. Z jednej strony

podl

,

aczenie do sieci komputerowych stanowi c b

,

edzie warunek wst

,

epny istnienia

rm (tak jak posiadanie telefonu, faxu, czy skrzynki pocztowej), z drugiej strony

podl

,

aczenie to stanowi o mo_zliwo sci wlama n, dewastacji danych i innych dziala n o

charakterze przest

,

epczym.

Oczywi scie u_zytkownicy sieci komputerowych b

,

ed

,

a sie broni c przed niepowo-

lanym dost

,

epem do danych czy manipulacjami dokonywanymi na nich. Pierwsz

,

a

lini

,

a obrony b

,

ed

,

a oczywi scie systemy operacyjne zarz

,

adzaj

,

ace prac

,

a komputer ow i

wykonywaniem zlece n na rzecz u_zytkownik ow. W wielu miejscach ruchu w sieciach

komputerowych (kt ore uzyskaly ju_z modn

,

a nazw

,

e

infostr

ad

) "sprawdzane b

,

ed

,

a

bilety\, a "pasa_zerowie na gap

,

e\ b

,

ed

,

a usuwani z ruchu. R ownocze snie zadaniem

systemu operacyjnego b

,

edzie przestrzeganie, czy u_zytkownicy dokonuj

,

a jedynie do-

zwolonych operacji.

Wskutek zlo_zono sci stawianych zada n systemy operacyjne b

,

ed

,

a stawa c si

,

e coraz

bardziej skomplikowane. Tym samymcoraz trudniej b

,

edzie ich tw orcom przewidzie c

wszystkie mo_zliwo sci, tak aby uniemo_zliwi comini

,

ecie zabezpiecze n zainstalowanych

poprzez system operacyjny. Dotychczasowe doniesienia z tego pola walki s

,

a raczej

pesymistyczne dla system ow operacyjnych. Stoj

,

a one w obliczu mia_zd_z

,

acej przewagi

wlamywaczy zwanych hackerami. Hackerzy nie s

,

a, jakby si

,

e chcialo wierzy c, jedynie

grup

,

a nastoletnich maniak ow komputerowych (czy lagodniej m owi

,

ac, milo snik ow

technik komputerowych). Jest to grupa o olbrzymim potencjale intelektualnym,

nierzadko doskonalym zapleczu sprz

,

etowym i nansowym.

Ostatni

,

a szans

,

a na zagwarantowanie bezpiecze nstwa danych jest kryptograa.

Nie mo_ze ona usun

,

a c wszelkich niebezpiecze nstw (jak na przyklad zniszczenie da-

nych przez wlamywacza komputerowego), ale w wielu sytuacjach skutecznie pomaga

(na przyklad uniemo_zliwia odczyt danych przez niepowolan

,

a osob

,

e). W odr o_znieniu

do innych metod kryptograa dostarcza metod wzgl

,

ednie bezpiecznych. Tak bez-

piecznych, _ze liniami telekomunikacyjnymi dokonuje si

,

e co chwila przelew ow nie-

wyobra_zalnych dla szarego czlowieka sum. I nikt si

,

e nie martwi, _ze kto s wl

,

aczy si

,

e

na lini

,

e i t

,

a drog

,

a powi

,

ekszy stan swego konta o ile s milion ow dolar ow (z kt orymi

odleci natychmiast na wyspy poludniowego Pacyku do kraju, z kt orym zapomniano

zawrze c umow

,

e o ekstardycji przest

,

epc ow).

Miroslaw Kutylowski

Wst

,

ep

Niniejsza ksi

,

a_zka ma za zadanie w bardzo zwi

,

ezly spos ob przedstawi c podstawowe

metody kryptograczne. Wiele interesuj

,

acych technik kryptogracznych zostalo w

niej pomini

,

etych. Nacisk polo_zony zostal na te aspekty, kt ore maj

,

a b

,

ad z mie c mog

,

a

praktyczne zastosowanie. Wskutek tego wiele teoretycznie ciekawych zagadnie n

swiadomie nie poruszamy w tej ksi

,

a_zce. Z drugiej strony, naszym zamyslem bylo, na

tyle na ile to jest mo_zliwe w tak kr otkiej pozycji, umo_zliwi cczytelnikowi zrozumienie

matematycznych mechanizm ow tkwi

,

acych w kryptograi. Tym ksi

,

a_zka ta r o_zni si

,

e

na przyklad od dost

,

epnej na polskim rynku pozycji Bruce'a Schneiera 6], maj

,

acej

bardziej charakter encyklopedii ni_z podr

,

ecznika.

Niniejsza ksi

,

a_zka przeznaczona jest dla student ow informatyki i pokrewnych

dziedzin. Mo_ze by c wykorzystana jako podr

,

ecznik do semestralnego wykladu z kry-

ptograi, jak r ownie_z jako material do samodzielnego studiowania. Do zrozumie-

nia niekt orych cz

,

e sci ksi

,

a_zki niezb

,

edna jest znajomo s c pewnych fakt ow z algebry.

Czytelnik nieobeznany z tymi zagadnieniami mo_ze znale z c brakuj

,

ace informacje w

Dodatku A. Niekiedy konieczna jest znajomo s c standardowych fakt ow z podstaw

informatyki wykladanych na pierwszych latach studi ow informatycznych. Cz

,

e s c

tych poj

,

e c skr otowo przedstawiamy w Dodatku B.

Niniejsza ksi

,

a_zka oparta jest na cz

,

e sci skryptu do wykladu Miroslawa Kutylow-

skiego. Wyklad ten odbyl si

,

e na Wydziale Matematyki i Informatyki Uniwersytetu

Paderborn w semestrze zimowym 1995 roku. Wspomniany skrypt obejmuje pr ocz

kryptograi zagadnienia kod ow samokoryguj

,

acych bl

,

edy i kompresji danych. Jest

on dost

,

epny poprzez World Wide Web pod adresem

http://www.uni-paderborn.de/fachbereich/AG/agmadh/WWW/german/LehreKuty/ikk95/skript.ps.gz

Lista zauwa_zonych bl

,

ed ow, uzupelnienia, itp. znajduj

,

a si

,

e w World Wide Web

pod adresem

http://www.uni-paderborn.de/fachbereich/AG/agmadh/WWW/german/LehreKuty/kryptograa/

Pragniemy podzi

,

ekowa c licznym studentom za udzielon

,

a pomoc. W szczeg olno-

sci wymieni c chcieliby smy Guido Haeselera, kt orego notatki do wykladu w Latex-u

byly podstaw

,

a pierwszej wersji skryptu (i szeregu rysunk ow zawartych w ksi

,

a_zce).

Cz

,

e s c rysunk ow zostala wykonana przez Franka Beste i Ew

,

e Kutylowsk

,

a.

3

Rozdzia

l

1

Pierwszy

rzut

ok

a

na

kryptogra

,

e

1.0.1 Szyfrowanie danych

Najwa_zniejsze pole zainteresowa
n kryptograi (ale obecnie ju_z nie jedyne) to szyf-

rowanie dokument
ow. Z orginalnego dokumentu (mo_ze to by
c tekst, zakodowany

cyfrowo obraz, zakodowany cyfrowo d
zwi

,

ek,

:

:

:

) zwanego

tekstem jawnym

mo_zna

stworzy
c jego zaszyfrowan

,

a wersj

,

e zwan

,

a

kryptogramem

. Do zaszyfrowania i de-

szyfrowania niezb

,

edny jest dodatkowo

klucz

lub klucze. Ze wzgl

,

edu na wlasno
sci

kluczy rozr
o_zniamy nast

,

epuj

,

ace metody szyfrowania:

Algorytmy symetryczne:

klucz do szyfrowania i deszyfrowania s

,

a identyczne

(lub latwo wyprowadzalne jeden z drugiego).

tekst jawny

zaszyfrowany tekst (kryptogram)

6

6

?

?

-



szyfrowanie kluczem

K

deszyfrowanie kluczem

K

Rysunek 1.1: Symetryczna metoda szyfrowania

Algorytmy asymetryczne:

(zwane tak_ze algorytmami z

kluczem jawnym

lub

kluczem publicznym

) klucze do szyfrowania i deszyfrowania s

,

a r
o_zne prak-

tycznie nie powinno by
c mo_zliwe wyprowadzenie z jednego z nich pasuj

,

acego

drugiego klucza umo_zliwiaj

,

acego operacj

,

e odwrotn

,

a.

Jako podstawow

,

a zasad

,

e nale_zy przyj

,

a
c, _ze deszyfrowanie przy pomocy niewla
s-

ciwego klucza nie powinno praktycznie dostarcza
c

_zadnych

informacji o tek
scie

jawnym.

W ramach kryptograi rozwa_zamy r
ownie_z metody

lamania szyfrow

, lub ina-

czej

kryptoanalizy

. Chodzi o to by, na przyklad, na podstawie kryptogramu

znale
z
c odpowiadaj

,

acy mu tekst jawny lub zastosowany do szyfrowania klucz.

4

R

OZDZIA

L

1.

PIER

WSZY

RZUT

OKA

NA

KR

YPTOGRAFI

,

E

5

1.0.2 Podstawowe zastosowania technik szyfrowania

Ochrona danych przed niepowolanym odczytem

Realizacja tego celu nast

,

epuje poprzez szyfrowanie danych przy pomocy algorytm
ow

symetrycznych.

Pola zastosowan:

Zapis danych na nosnikach (dyski itp.) nie gwarantuj

,

acych ochrony przed odczy-

tem przez niepowolane osoby

: Dane te s

,

a zapisywane jedynie w postaci krypto-

gramu tylko posiadacz odpowiedniego klucza mo_ze z kryptogramu odtworzy
c

orginalny tekst.

Zabezpieczenie komunikacji przeprowadzanej liniami nara_zonami na podsluch

: na

przyklad tego rodzaju zabezpieczenie niezb

,

edne jest w przypadku elektro-

nicznego dokonywania operacji gieldowych { podsluch dokonywanych zam
o-

wie
n dostarczalby informacji pozwalaj

,

acy na efektywn

,

a spekulacj

,

e gieldow

,

a.

Jeszcze wi

,

eksze niebezpiecze
nstwa wi

,

aza
c si

,

e mog

,

a z mo_zliwo
sciami zmian w

przesylanych informacjach, na przyklad w wypadku elektronicznego obrotu

pieni

,

edzy pomi

,

edzy bankami. Szyfrowanie nie eliminuje zycznej mo_zliwo
sci

zakl
ocenia komunikacji b

,

ad
z dokonywania w niej zmian. Jednak zmiany do-

konywane bez znajomo
sci odpowiedniego klucza powoduj

,

a powstawanie chao-

tycznych tekst
ow po odszyfrowaniu przez prawowitego odbiorc

,

e u_zywaj

,

acego

prawidlowego klucza. W ten spos
ob pr
oba oszustwa zostaje wykryta.

Uwierzytelnianie dokumentow

Uwierzytelnianie dokument
ow mo_ze nast

,

api
c przy pomocy algorytm
ow asymetry-

cznych. Alice publikuje (na przyklad na swej stronie w World Wide Web) jeden z

dwu pasuj

,

acych do siebie kluczy, mianowicie ten slu_z

,

acy do deszyfrowania (dlatego

klucz ten nazywamy

kluczem jawnym

lub

kluczem publicznym

). Drugi z pary

kluczy jest przez Alice pilnie strze_zony i nie jest podawany do niczyjej wiadomo
sci.

Klucz ten nazywamy

kluczem prywatnym

. Uwierzytelnianie dokument
ow przez

Alice odbywa si

,

e poprzez szyfrowanie ich przy pomocy jej prywatnego klucza (patrz

rys. 1.2). Jest to mo_zliwe poniewa_z:

Ka_zdy mo_ze przy pomocy publicznego klucza Alice odzyska
c orginalny tekst.
Je
sli kryptogram nie byl wygenerowany przy pomocy prywatnego klucza Alice,

to deszyfrowanie przy pomocy klucza Alice daje w wyniku tekst b

,

ed

,

acy chao-

tycznym ci

,

agiem znak
ow bez _zadnego
sladu sensu. Gwarantuje to, _ze jedynie

posiadacz prywatnego klucza Alice mo_ze t

,

a drog

,

a uwierzytelnia
c dokumenty

w imieniu Alice.
Na tej samej zasadzie pomylenie klucza publicznego w trakcie deszyfrowania

r
ownie_z daje w wyniku tekst b

,

ed

,

acy chaotycznym ci

,

agiem znak
ow. Dzi

,

eki

temu nie jest mo_zliwe przypisanie tekstu niewla
sciwemu autorowi.

Ochrona prywatnosci elektronicznej korespondencji

Asymetryczne algorytmy szyfrowania mo_zna u_zy
c r
ownie_z dla ochrony elektronicz-

nej korespondencji. Przesylanie korespondencji elektronicznej l

,

aczy si

,

e bowiem z

wieloma niebezpiecze
nstwami. Kto
s maj

,

acy kontrol

,

e nad w

,

ezlem Internetu, przez

kt
ory przesylany jest list, mo_ze list ten zniszczy
c, zmodykowa
c, albo wreszcie

przekaza
c go komu
s innemu. Aby zapobiec przynajmniej dw
om ostatnim mo_z-

liwo
sciom mo_zna u_zy
c scenariusza opisanego poni_zej. Przed niszczeniem list
ow

kryptograa nie jest nas w stanie uchroni
c.

R

OZDZIA

L

1.

PIER

WSZY

RZUT

OKA

NA

KR

YPTOGRAFI

,

E

6

'

&

$

%

'

&

$

%

Alice

Bob

tekst orginalny

kryptogram

tekst orginalny

?

deszyfrowanie

kluczem

publicznym

K

0

szyfrowanie

kluczem

prywatnym

K

-

Rysunek 1.2: Uwierzytelnianie przez szyfrowanie

Zal
o_zmy, i_z Alice chce bezpiecznie otrzymywa
c korespondencj

,

e. W tym celu

Alice musi dysponowa
c par

,

a pasuj

,

acych kluczy dla asymetrycznego algorytmu szy-

fruj

,

acego. Klucz do

szyfr

owania

zostaje przez Alice opublikowany, na przyklad po-

przez World Wide Web. Gdy Bob pragnie wysla
c list do Alice, wtedy wykonywane

s

,

a nast

,

epuj

,

ace kroki (patrz rys. 1.3):

Bob zaopatruje si

,

e w klucz

K

, publiczny klucz Alice.

Bob szyfruje tekst swego listu do Alice przy pomocy klucza

K

.

Bob wysyla zaszyfrowany list poczt

,

a elektroniczn

,

a do Alice (w zale_zno
sci od

stosowanego systemu, konieczna mo_ze by
c konwersja z pliku zawieraj

,

acego

kryptogram z postaci binarnej na tekstow

,

a, by unikn

,

a
c zmian wprowadzanych

przez program pocztowy).
Alice deszyfruje otrzymany list przy pomocy swego prywatnego klucza i otrzy-

muje w ten spos
ob orginalny list.

Powy_zszy protok
ol gwarantuje, _ze tylko Alice jest w stanie odkodowa
c prze-

znaczone do niej listy. Tak wi

,

ec przechwycenie korespondencji przez osoby trzecie

przestaje by
c niebezpieczne. R
ownie_z pr
oby wprowadzania zmian w zaszyfrowanym

li
scie (nawet na
slepo) jest skazana na niepowodzenie { wszystkie rozs

,

adne algo-

rytmy szyfruj

,

ace maj

,

a wlasno
s
c, _ze zmiana cho
cby jednego bitu w kryptogramie

powoduje olbrzymie zmiany w tek
scie po deszyfrowaniu, wskutek czego tekst ten

ma posta
c przypadkowego ci

,

agu znak
ow.

Oczywi
scie bezpiecze
nstwo korespondencji mi

,

edzy Alice i Bobem mo_zna zagwa-

rantowa
c poprzez stosowanie szyfrowania algorytmem symetrycznym z kluczem

znanym jedynie Alice i Bobowi. Zalet

,

a protokolu z u_zyciem asymetrycznego al-

gorytmu jest to, _ze Alice i Bob nie musz

,

a uzgadnia
c stosowanych kluczy, oraz

_ze Alice mo_ze ograniczy
c si

,

e do posiadania jednej pary kluczy dla korespondencji

prowadzonej z du_z

,

a ilo
sci

,

a os
ob. Protok
ol nadaje si

,

e wi

,

ec dobrze dla korespondencji

pomi

,

edzy osobami sporadycznie kontaktuj

,

acymi si

,

e oraz gdy Alice otrzymuje listy

od du_zej ilo
sci os
ob.

Elektroniczny notariusz

Do notariusza zglaszamy si

,

e w dw
och wa_znych sytuacjach:

R

OZDZIA

L

1.

PIER

WSZY

RZUT

OKA

NA

KR

YPTOGRAFI

,

E

7

'

&

$

%

'

&

$

%

List 1

List 2

-

-

szyfrowanie

szyfrowanie
kluczem

publicznym

K

kluczem

publicznym

K

Bob

Mike

Kryptogram 1

Kryptogram 2

List 1

List 2

'

&

$

%

J

J

J

^

deszyfrowanie
kluczem

K

0

S

S

w

prywatnym

K

0

Alice, posiadaczka

K

0

Rysunek 1.3: Ochrona korespondencji przy u_zyciu asymetrycznych algorytm
ow

szyfruj

,

acych

1. Je
sli chcemy urz

,

edowo potwierdzi
c istnienie jakiego
s dokumentu. W tym

wypadku mo_zemy dodatkowo pragn

,

a
c by proces potwierdzania nie ujawnial

tre
sci dokumentu (bo mo_ze by
c to na przyklad opis nowej, warto
sciowej tech-

nologii).

2. Je
sli chcemy zagwarantowa
c by w dokumencie (na przyklad umowie handlo-

wej) nie byly dokonywane p
o
zniej jakiekolwiek zmiany przez nieuczciwego

partnera.

W obu przypadkach wystarcza sporz

,

adzenie dla wspomnianego dokumentu czego
s

w rodzaju odcisk
ow palc
ow { kr
otkiego ci

,

agu symboli, kt
ory

pr

aktycznie

jest dla

ka_zdego tekstu inny. Takie "odciski palc
ow\ mo_zna na przyklad opublikowa
c jako

ogloszenie w codziennej prasie. Zdobywamy w ten spos
ob dow
od istnienia doku-

mentu. Aby dow
od ten byl niezaprzeczalny musimy zagwarantowa
c kilka wlasno
sci.

Do sporz

,

adzania "odcisk
ow palc
ow\ u_zywamy tak zwanych

jednokierunkowych

funkcji hashuj

,

acych

. M
owimy, _ze

H

jest jednokierunkow

,

a funkcj

,

a hashuj

,

ac

,

a o

ile spelnione s

,

a nast

,

epuj

,

ace warunki:

Dla ka_zdego

X

latwo jest obliczy
c

H

(

X

).

H

(

X

) ma ustalon

,

a dlugo
s
c dla wszystkich tekst
ow

X

(w ten spos
ob dlugo
s
c

H

(

X

) nie zdradza _zadnych informacji o tek
scie

X

).

Dla zadanego

Y

znalezienie

X

takiego, _ze

H

(

X

) =

Y

, jest praktycznie niemo-

_zliwe. Dotyczy to w szczeg
olno
sci systematycznego przeszukiwania wszystkich

mo_zliwych tekst
ow. Tak wi

,

ec ci

,

agi

H

(

X

) musz

,

a by
c wystarczaj

,

aco dlugie,

by takie systematyczne przeszukiwanie bylo praktycznie beznadziejne. Je
sli

warto
sci funkcji hashuj

,

acej skladaj

,

a si

,

e z 128 bit
ow to mamy do dyspozycji

2

128

mo_zliwych warto
sci. Jest to praktycznie niesko
nczona ilo
s
c (dla por
ow-

nania calkowity okres od pocz

,

atku do ko
nca Wszech
swiata bywa szacowany

wedlug niekt
orych teorii na 2

61

sekund!).

W rzeczywisto
sci nakladane s

,

a jeszcze bardziej rygorystyczne warunki na wlasno
sci

jednokierunkowych funkcji hashuj

,

acych (patrz Rozdzial 6).

R

OZDZIA

L

1.

PIER

WSZY

RZUT

OKA

NA

KR

YPTOGRAFI

,

E

8

W celu "notarialnego\ potwierdzenia posiadania dokumentu

X

nale_zy obliczy
c

warto
s
c

H

(

X

) i opublikowa
c j

,

a lub umie
sci
c u notariusza (rol

,

e notariusza mo_ze

przej

,

a
c odpowiedni specjalnie zabezpieczony program sieciowy). P
o
zniej, gdy pra-

gniemy udowodni
c posiadanie dokumentu

X

, przedstawiamy

X

i wskazujemy na

miejsce, gdzie podali
smywcze
sniej warto
s
c

H

(

X

). Sprawdzenie polega na obliczeniu

warto
sci

H

(

X

) dla podanego tekstu

X

i por
ownaniu jej z warto
sci

,

a opublikowan

,

a

wcze
sniej lub zlo_zon

,

a u notariusza.

W celu zagwarantowania, i_z tekst

X

(na przyklad umowa) nie ulegnie mody-

kacjom, r
ownie_z obliczamy warto
s
c

H

(

X

). Warto
s
c t

,

e mo_zemy nast

,

epnie dol

,

aczy
c

do dokumentu (na przyklad dla wykrycia przypadkowych bl

,

ed
ow powstalych w

trakcie transmisji danych) lub opublikowa
c, czy zlo_zy
c u notariusza (dla ochrony

przed post

,

epowaniem nieuczciwego partnera umowy).

Zauwa_zmy, _ze opisana metoda moglaby na przyklad pozwala
c na proste spraw-

dzanie autentyczno
sci program
ow komputerowych. Jeden z trudniejszych do wy-

krycia atak
ow na system komputerowy jest wprowadzanie tzw. koni troja
nskich {

program
ow zachowuj

,

acych si

,

e z punktu widzenia u_zytkownika w spos
ob dokladnie

taki sam jak programy orginalne, jednak wykonuj

,

ace pewne dodatkowe funkcje (na

przyklad samopowielanie w przypadku wirus
ow, czy przekazywanie informacji na

zewn

,

atrz w wypadku szpiegostwa gospodarczego). O ile jednak producent programu

X

zamie
sci warto
s
c

H

(

X

) na przyklad w World Wide Web, wtedy osoba posiadaj

,

aca

program

X

mo_ze w ka_zdym momencie obliczy
c warto
s
c funkcji

H

dla posiadanego

programu i por
owna
c j

,

a z warto
sci

,

a

H

(

X

) dost

,

epn

,

a publicznie. Zauwa_zmy, _ze

metoda ta pozwala na wykrycie zmian dokonywanych w programie przez

jakie-

kolwiek

wirusy, te znane jak i nieznane lub nienapisane jeszcze. Istotn

,

a cech

,

a tej

metody jest to, _ze producent nie musi upublicznia
c programu

X

, a mimo wszystko

pelna werykacja orginalno
sci jest mo_zliwa. Tym samym producent ma szanse

sprzeda_zy dalszych kopii programu

X

.

O ile wybierzemy funkcj

,

e hashuj

,

ac

,

a generuj

,

ac

,

a kr
otkie ci

,

agi liter, wtedy telefo-

nicznie mo_zna sprawdzi
c orginalno
s
cdokument
ow przeslanych elektronicznie (osoby

znaj

,

ace si

,

e po glosie mog

,

a sprawdzi
c czy warto
sci funkcji hashuj

,

acej dla wyslanego

i otrzymanego dokumentu s

,

a takie same). T

,

a drog

,

a mo_zna na przyklad drog

,

a

telefoniczn

,

a sprawdzi
c orginalno
s
c kluczy publicznych generowanych przez system

PGP.

|||||||||||||||||||||||||||||||||||

Przyklady, jakie przedstawili
smy powy_zej to tylko niekt
ore z dzisiejszych per-

spektyw zastosowania kryptograi. Ju_z po tych przykladach wida
c jednak, _ze pole

zastosowa
n kryptograi wykracza daleko poza klasyczne szyfrowanie danych (na

przyklad do cel
ow militarnych). Niekt
ore inne zastosowania b

,

ed

,

a przedstawione w

dalszej cz

,

e
sci tej ksi

,

a_zki. Poza tym Czytelnik mo_ze odwola
c si

,

e do bogatej literatury

fachowej dotycz

,

acej kryptograi.

1.0.3 Historia kryptograi

Ju_z w staro_zytno
sci stosowane byly pewne metody szyfrowania wiadomo
sci o cha-

rakterze strategicznym. Ciekawe jest, _ze stopie
n wyranowania tych metod byl

znacz

,

aco ni_zszy od stanu wiedzy matematycznej w ka_zdej wla
sciwie epoce. Sto-

sowane metody byly dawniej zazwyczaj do
s
c prymitywne i pozwalaly na zlamanie

szyfr
ow dostatecznie zdeterminowanemu przeciwnikowi. Sytuacja ulegla zmianie

ju_z w pierwszej polowie dwudziestego wieku. Zbudowano wtedy szereg system
ow

szyfrowania przy pomocy urz

,

adze
n mechanicznych wykorzystywanych powszechnie

podczas II Wojny
Swiatowej. Cz

,

e
s
c z tych system
ow zostala skutecznie zlamana

(na przyklad niemiecki system Enigma). Prawdziw

,

a rewolucj

,

e pod wzgl

,

edem pro-

jektowania system
ow szyfruj

,

acych przyni
osl rozw
oj elektroniki daj

,

acy olbrzymie

mo_zliwo
sci operacji obliczeniowych niskim kosztem.

R

OZDZIA

L

1.

PIER

WSZY

RZUT

OKA

NA

KR

YPTOGRAFI

,

E

9

Rozw
oj kryptograi od swych pocz

,

atk
ow byl bardzo silnie zwi

,

azany z celami

wojskowymi. W zwi

,

azku z tym wszelkie prace z dziedziny kryptograi mialy cha-

rakter tajny i ich rezultaty nie byly publikowane lub wykorzystywane w sektorze

cywilnym do lat siedemdziesi

,

atych. Naukowcy prowadz

,

acy badania w kryptogra-

i znajdowali si

,

e pod
scisl

,

a kontrol

,

a organ
ow bezpiecze
nstwa. Publikowanie prac

nast

,

epowalo sporadycznie i niekiedy jedynie poprzez niedopatrzenie organ
ow kon-

trolnych.

Prawdziwy przelom pod wzgl

,

edem rozwoju kryptograi nast

,

apil w latach sie-

demdziesi

,

atych wraz z odkryciem asymetrycznych algorytm
ow szyfruj

,

acych. Ol-

brzymie zainteresowanie w
srodowiskach naukowych spowodowalo lawinowy wzrost

ilo
sci prowadzonych bada
n, ju_z poza kontrol

,

a aparat
ow bezpiecze
nstwa poszcze-

g
olnych pa
nstw. Wymiana informacji jaka ma miejsce od tego czasu pozwolila na

ogromny rozw
oj wiedzy w tej dziedzinie.

W wielu krajach stosowanie metod kryptogracznych jest nadal zabronione lub

ograniczone. W wielu krajach, sk

,

adinn

,

ad demokratycznych, gdzie obywatele ciesz

,

a

si

,

e du_zym zakresem wolno
sci, podejmowane s

,

a pr
oby ustanowienia kontroli pa
nstwa

nad stosowaniem metod kryptogracznych. W szczeg
olno
sci dotyczy to przyklad

Wsp
olnoty Europejskiej i USA (forsowanie u_zywania Clippera, tj. ukladu elektro-

nicznego slu_z

,

acego do szyfrowania, jednak pozwalaj

,

acego na lamanie kryptogram
ow

przez slu_zby bezpiecze
nstwa). Doprowadzilo to te_z do tak spektakularnych krok
ow

jak zakaz u_zywania technik kryptogracznych do cel
ow prywatnych w Rosji.

Ograniczaniu mo_zliwo
sci stosowania metod kryptogracznych sprzeciwiaj

,

a si

,

e

bardzo gwaltownie
srodowiska buzinessu. Wskazuj

,

a na niezb

,

edno
s
c jej stosowania

w gospodarce w niereglamentowany spos
ob. W obecnej chwili wydaje si

,

e, _ze jednym

z niezb

,

ednych warunk
ow rozwoju gospodarczego pa
nstwa jest rozbudowa globalnej

sieci komputerowej pelni

,

acej funkcj

,

e infrastruktury informacyjnej gospodarki. Po-

niewa_z w sieciach tego typu nie da si

,

e raczej zagwarantowa
c bezpiecze
nstwa przed

wlamaniamikomputerowymi,dane musz

,

a by
c zabezpieczane w inny spos
ob. Jedyna

droga do realizacji tego celu wiedzie poprzez wykorzystanie technik kryptogra-

cznych. Podnoszone s

,

a argumenty, i_z wprowadzenie ogranicze
n stosowania kry-

ptograi nieuchronie powoduje spadek atrakcyjno
sci danego kraju dla inwestycji

gospodarczych.

1.0.4 Kontrowersje zwi

,

azane ze stosowaniem kryptograi

Kryptograa w obecnym stadium rozwoju potra zagwarantowa
c ochron

,

e danych

przed dost

,

epem niepowolanych os
ob. Jest to mo_zliwe nawet wtedy, gdy wla
sciciel

danych za takowe uwa_za organy
scigania. Dopuszczenie stosowania tych metod

uniemo_zliwiazatem skutecznie dokonywanie "rewizji\ policyjnychwsystemachkom-

puterowych. Umo_zliwia to dokonywanie elektronicznego przetwarzania danych w

ramach dzialalno
sci przest

,

epczej bez niebezpiecze
nstwa dostarczenia organom
sci-

gania materialu dowodowego w wypadku ich przechwycenia. Pozwala to r
ownie_z

na korzystanie z powszechnie dost

,

epnych sieci takich jak Internet do dzialalno
sci

przest

,

epczej. Z mo_zliwo
sci tych korzystaj

,

a zapewne ju_z teraz organizacje dzialaj

,

ace

na kraw

,

edzi prawa, lub te_z wbrew prawu.

W obliczu powy_zszych zagro_ze
n w wielu pa
nstwach organy bezpiecze
nstwa (cza-

sami demokratycznie wybrane, czasami b

,

ed

,

ace aparatem politycznej represji) stara-

j

,

a si

,

e zabroni
c b

,

ad
z ograniczy
c stosowanie metod kryptogracznych. Druga z tych

opcji polega na dopuszczeniu jedynie takich metod, kt
ore mog

,

a zosta
c zlamane

przez organy bezpiecze
nstwa (wskutek slabo
sci tych metod, konieczno
sci przekazy-

wania u_zywanych kluczy organom bezpiecze
nstwa, b

,

ad
z dzi

,

eki wbudowanym do

algorytm
ow "tylnym drzwiom\ pozwalaj

,

acym na deszyfrowanie bez znajomo
sci

kluczy).

R

OZDZIA

L

1.

PIER

WSZY

RZUT

OKA

NA

KR

YPTOGRAFI

,

E

10

Przeciwnicy stosowania ogranicze
n w stosowaniu kryptograi wskazuj

,

a, i_z
sro-

dowiska przest

,

epcze bylyby i tak w stanie korzysta
c z technik kryptogracznych

bez mo_zliwo
sci udowodnienia im tego poprzez organy
scigania. Problem polega

na tym, i_z kryptogramy maj

,

a charakter losowych ci

,

ag
ow znak
ow i s

,

a od nich

nieodr
o_znialne. Z drugiej strony losowy charakter maj

,

a szumy zawarte w ka_zdym

kodowanym cyfrowo obrazie czy d
zwi

,

eku. Tym samym przest

,

epca dzialaj

,

acy w

ramach zorganizowanych grup mo_ze ukry
c przekazywan

,

a wiadomo
s
c na przyklad w

zdj

,

eciu Tatr umieszczonym na swej stronie WWW, czy te_z na dysku CD specjalnie w

tym celu spreparowanym. Co wi

,

ecej, z niekt
orych form kryptograi nie jeste
smy w

stanie ju_z zrezygnowa
c, cho
cby w obrocie bankowym. Poniewa_z wiele metod u_zywa

jako niezb

,

ednych parametr
ow losowych ci

,

ag
ow znak
ow, przest

,

epca mo_ze zamiast

nich u_zywa
c kryptogram
ow z przest

,

epczymi informacjami. Zn
ow, nie wzbudzi to

_zadnych podejrze
n, a wiadomo
sci tak przekazywane b

,

ed

,

a odr
o_znialne od naprawd

,

e

losowych ci

,

ag
ow jedynie dla posiadaczy tajnego klucza (przyklad takiej sytuacji

opisujemy dokladniej w Rozdziale 8.0.6).

Reasumuj

,

ac, wydaje si

,

e i_z postulowane ograniczenia s

,

a w stanie by
c skuteczne

jedynie w odniesieniu do os
ob czy organizacji nie paraj

,

acych si

,

e dzialalno
sci

,

a prze-

st

,

epcz

,

a. Spowodowaloby to zatem skutek odwrotny do zamierzonego { stawialoby

organizacje przest

,

epcze w uprzywilejowanej pozycji wobec reszty spolecze
nstwa,

kt
ora nie bylaby w stanie broni
c swych danych wobec dziala
n kryminalnych.

1.0.5 Korzystanie z produktow kryptogracznych

Upublicznienie kryptograi pozwala na bardziej wiarygodn

,

a werykacj

,

e oferowa-

nych program
ow i sprz

,

etu kryptogracznego. Nie mo_zna bowiem w tym wzgl

,

edzie

polega
c na reklamie samych rm. Wadliwo
s
coferowanego produktu nie jest widocz-

na bowiem golym okiem, a cz

,

esto bez nieslychanie kosztownego badania produktu

nie jest si

,

e r
ownie_z w stanie o tym przekona
c.

Sformulowa
cmo_zna nast

,

epuj

,

ace zasady dotycz

,

ace praktycznego stosowania pro-

dukt
ow kryptogracznych w sytuacjach, gdy rzeczywi
scie bezpiecze
nstwo ma klu-

czowe znaczenie:

Jako wzgl

,

ednie bezpieczne mog

,

a by
c uznane jedynie programy czy te_z spe-

cjalny hardware oferowany poprzez znane rmy o niezaprzeczalnej reputacji.

Najlepiej, gdy produkty te posiadaj

,

a certykaty odpowiednich pa
nstwowych

urz

,

ed
ow kontrolnych (jak na przyklad NIST w USA).

Programy i urz

,

adzenia kryptograczne powinny realizowa
c powszechnie zna-

ne, popularne i przetestowane rozwi

,

azania. Proces testowania powinien mie
c

nast

,

epuj

,

acy przebieg:

1.

Propozycja metody, wraz z jej szczegolowym opisem musi byc podana do

wiadomosci publicznej.

Bezpiecze
nstwo metody nie mo_ze opiera
c si

,

e na

utajnieniu jej sposobu dzialania. Wiadomo, _ze i tak pewna grupa os
ob

uzyska do takich informacji dost

,

ep (cho
cby pracownicy rmy oferuj

,

acej

produkt). Grupa ta mo_ze nast

,

epnie wykorzystywa
c je na szkod

,

e u_zyt-

kownika produktu.

2.

Propozycja musi wzbudzic powszechne zainteresowanie srodowiska nauko-

wego i businessu i musz

,

a byc prowadzone nad ni

,

a intensywne badania.

3.

Jesli po dlu_zszym czasie nie ma znacz

,

acych post

,

epow prowadz

,

acych do

zlamania metody

a teoretyczne badania zdaj

,

a si

,

e potwierdza
c jej bez-

piecze
nstwo (na przyklad poprzez redukcj

,

e znanych trudnych zagadnie
n

obliczeniowych do zagadnienia zlamania proponowanego szyfru),

wtedy

metod

,

e t

,

e mo_zna uznac za wzgl

,

ednie bezpieczn

,

a i dopuscic do u_zytku

.

R

OZDZIA

L

1.

PIER

WSZY

RZUT

OKA

NA

KR

YPTOGRAFI

,

E

11

Je
sli jakikolwiek z powy_zszych warunk
ow nie jest spelniony, algorytm nie

mo_zna uzna
c za bezpieczny.
Niezb

,

edne jest ci

,

agle
sledzenie rozwoju stanu wiedzy kryptogracznej. Post

,

e-

py w tej dziedzinie mog

,

a spowodowa
c mo_zliwo
s
clamania algorytm
ow dawniej

uznawanych za bezpieczne. (Tego typu sytuacja nast

,

apila na przyklad w

odniesieniu do dlugo
sci kluczy dla systemu RSA wskutek post

,

ep
ow w zakresie

algorytm
ow rozkladaj

,

acych liczby na czynniki pierwsze.)

Czasami jako
s
c oferty software'u i hardware'u kryptogracznego jest powi

,

azana

z czynnikami politycznymi, takimi jak ograniczenia eksportowe. Na przyklad tak

zwane "wersje mi

,

edzynarodowe\ program
ow rm ameryka
nskich maj

,

ace dostarczy
c

prywatnemu u_zytkownikowi narz

,

edzia kryptograczne gwarantuj

,

a jedynie bardzo

niski poziom bezpiecze
nstwa. Poziom ten jest tak niski, _ze programy te nie wyma-

gaj

,

a zezwole
n eksportowych w bardzo restrykcyjnym ustawodawstwie USA.

Rozdzia

l

2

P

o

dsta

w

o

w

e

tec

hniki

szyfro

w

ania

W niniejszym rozdziale przedstawiamy kilka klasycznych technik szyfrowania. Tech-

niki te bywaj

,

a skladnikami wielu bardziej zaawansowanych algorytmow, dlatego

poswi

,

ecimy im chwil

,

e uwagi.

2.0.6 Podstawienie

Niech : 

!

 b

,

edzie permutacj

,

a, zas  zbiorem u_zywanych liter. Tekst jawny

a

1

a

2

:

:

:

a

n

(gdzie

a

i

2

) jest szyfrowany jako (

a

1

) (

a

2

)

:

:

:

(

a

n

). Kryptogram

b

1

:

:

:

b

n

odszyfrowywany jest jako

;

1

(

b

1

)

:

:

:

;

1

(

b

n

).

Przyklad: szyfry Cesara

Litery alfabetu mo_zna uto_zsamiac z liczbami. W

systemie Cesara u_zywanych jest 26 liter odpowiadaj

,

acych liczbom od 0 do 25.

(

i

) :=

i

+ 3 mod 26 dla

i

2

f

0



:

:

:



25

g

.

Analiza cz

,

estotliwosci

Slabosci

,

a szyfrow opartych na podstawieniach jest to, _ze mog

,

a one byc zlamane

poprzez analiz

,

e cz

,

estotliwosci wyst

,

epowania poszczegolnych liter alfabetu. Litery

alfabetu nie wyst

,

epuj

,

a bowiem z jednakow

,

a cz

,

estotliwosci

,

a { analiza tych cz

,

e-

stotliwosci w zaszyfrowanych tekstach pozwala na zgadni

,

ecie niektorych wartosci

permutacji . Dla przykladu przyjrzyjmy si

,

e przeci

,

etnej cz

,

estotliwosci wyst

,

epo-

wania liter w tekstach w j

,

ezyku angielskim (wedlug 1]):

E - 12.31 % L - 4.03 % B - 1.62 %

T - 9.59 % D - 3.65 % G - 1.61 %

A - 8.05 % C - 3.20 % V - 0.93 %

O - 7.94 % U - 3.10 % K - 0.52 %

N - 7.19 % P - 2.29 % Q - 0.20 %

I - 7.18 % F - 2.28 % X - 0.20 %

S - 6.59 % M - 2.25 % J - 0.10 %

R - 6.03 % W - 2.03 % Z - 0.09 %

H - 5.14 % Y - 1.88 %

Kryptoanaliza polega na sporz

,

adzeniu tabeli cz

,

estotliwosci wyst

,

epowania liter

w zaszyfrowanym tekscie i porownania go z powy_zsz

,

a tabel

,

a. Na tej podstawie

mo_zna na przyklad zlokalizowac prawdopodobne wartosci dla (

E

), (

T

), (

A

). Po

przyj

,

eciu hipotetycznych wartosci dla tych liter szukamy w kryptogramie sekwencji

12

R

OZDZIA

L

2.

PODST

A

W

O

WE

TECHNIKI

SZYFR

O

W

ANIA

13

liter odpowiadaj

,

acych typowym slowom takim jak na przyklad "the\. Pozwala

to na zwerykowanie hipotezy i przyj

,

ecie prawidlowych wartosci dla E, T, A. Po

ustaleniu tych wartosci mo_zemy pokusic si

,

e o odgadni

,

ecie (

H

) - tak by utworzyc

odpowiednio du_zo kryptogramow dla "the\. Post

,

epowanie to kontynuujemy dyspo-

nuj

,

ac coraz to wi

,

ekszymi porcjami tekstu jawnego.

Sposobem na utrudnienie analizy cz

,

estotliwosci jest szyfrowanie poprzez podsta-

wienie nie pojedynczych liter, ale blokow liter okreslonej dlugosci (tj. : 

k

!



k

).

Mamy wtedy bowiem do czynienia z mniejszymi dysproporcjami w zakresie sredniej

cz

,

estotliwosci wyst

,

epowania poszczegolnych konguracji liter w bloku w szczegol-

nosci poszczegolne prawdopodobienstwa s

,

a stosunkowo malymi liczbami. Utrudnia

to odgadni

,

ecie wartosci podstawienia . W szczegolnosci kryptoanaliza wymaga

du_zo dlu_zszych kryptogramow, aby moc skorzystac z jakichkolwiek statystycznych

prawidlowosci.

Przykladem systemu, w ktorym koduje si

,

e bloki dlugosci 2 jest system Fairplay'a

przedstawiony na rys. 2.1. Jest to prosty system, w ktorym wszelkie operacje szy-

frowania i deszyfrowania mog

,

a byc z latwosci

,

a dokonane r

,

ecznie. System oczywiscie

gwarantuje tylko bardzo niewielki zakres bezpieczenstwa i mo_ze byc traktowany jako

dygresja w stron

,

e metod historycznych (stosowanych w trakcie I Wojny Swiatowej).

Szyfrowaniu podlegaj

,

a pary liter, przy czym u_zywamy 25 liter (25 du_zych liter

alfabetu angielskiego, jedna z liter, mianowicie J, jest w tekstach zast

,

apiona przez

I). Do szyfrowania i deszyfrowania u_zywamy jest kwadrat 5



5, w ktory wpisujemy

kolejne litery wyst

,

epuj

,

ace w hasle (na rys. 2.1 haslem jest "POSZLA MALPA

DO PIWNICY\), przy czym pomijamy powtarzaj

,

ace si

,

e litery. Gdy po wpisaniu

tych liter zostaly jeszcze wolne miejsca w kwadracie, to umieszczamy tam jeszcze

niewpisane litery w kolejnosci alfabetycznej. W ten sposob wypelniamy kwadrat

25 literami. Szyfrowanie przebiega nast

,

epuj

,

aco. Zalo_zmy dla przykladu, _ze chcemy

zaszyfrowac par

,

e OH wedlug klucza z rys. 2.1. Litery O oraz H wyznaczaj

,

a pro-

stok

,

at



w kwadracie do szyfrowania, w ktorego pozostalych rogach znajduj

,

a si

,

e S

i G. Regula szyfrowania mowi, _ze OH zast

,

epujemy wlasnie tymi literami, tj. SG.

Gdy para liter jak

,

a zamierzamy zaszyfrowac le_zy w jednej kolumnie lub jednym

wierszu (i wobec tego nie deniuje prostok

,

ata), to litery te zast

,

epujemy par

,

a liter

le_z

,

ac

,

a na prawo od nich, na przyklad SY zast

,

epujemy przez ZB, zas WE przez AN

(litery le_z

,

ace w pierwszej kolumnie z prawej strony zast

,

epujemy literami z ostatniej

kolumny).

Ogolnie rzecz bior

,

ac podstawienie nie oparte o dlugie bloki lub o prostych

zasadach generowania permutacji z klucza mo_ze byc podatne na analiz

,

e cz

,

estotliwo-

sci. Z tego wzgl

,

edu podstawienie nale_zy traktowac raczej jako technik

,

e pomocnicz

,

a

do wykorzystania jako element pomocniczy bardziej zlo_zonych metod.

2.0.7 XOR i one-time pad

Operacja

X

OR

(

eXclusive OR

) jest zdeniowana jak nast

,

epuje:

0

X

OR

0 = 1

X

OR

1 = 0



1

X

OR

0 = 0

X

OR

1 = 1.

Szyfrowanie przy pomocy XOR:

zalo_zmy, _ze tekst jawny jest ci

,

agiem bit-

ow

a

1



:

:

:



a

n

, zas klucz ci

,

agiem bitow

k

1



:

:

:



k

n

. Wtedy kryptogramem jest ci

,

ag

c

1



:

:

:



c

n

, gdzie

c

i

:=

a

i

X

OR

k

i

dla

i

= 1



:

:

:



n

. Deszyfrowanie oparte jest na

trzech latwych do sprawdzenia rownosciach:

x

X

OR

x

= 0



x

X

OR

0 =

x

x

X

OR

(

y

X

OR

z

) = (

x

X

OR

y

)

X

OR

z

)

:

St

,

ad

c

i

X

OR

k

i

= (

a

i

X

OR

k

i

)

X

OR

k

i

=

a

i

X

OR

(

k

i

X

OR

k

i

) =

a

i

X

OR

0 =

a

i

:

R

OZDZIA

L

2.

PODST

A

W

O

WE

TECHNIKI

SZYFR

O

W

ANIA

14



R T U V X

F G H K Q

N C Y B E

A M D I W

P O S Z L

(KR) = FV, (OW) = LM,

(AI) = MW, (WE) = AN

(SZ) = ZL

OH - rogi prostok

,

ata



 OH

zast

,

epowany jest poprzez litery

znajduj

,

ace si

,

e w pozostalych rogach

prostok

,

ata



 tj. przez SG

szyfrowanie:

szyfrowanie tekstu jawnego KR

j

OW

j

A I

j

WE

j

SZ

R T U V X

F G H K Q

N C Y B E

A M D I W

P O S Z L

pozostale litery

w kolejnosci alfabetycznej

haslo:

"POSZLA MALPA DO PIWNICY\

klucz: kwadrat 5



5 zawiera wszystkie litery z waj

,

atkiem J,

ktore w tekscie jawnym zast

,

epujemy poprzez I

Rysunek 2.1: System Playfair'a

Szyfrowanie przy pomocy

X

OR

ma wielorakie zastosowania. Jednym z nich jest

one-time pad

.

One-time pad

Jest to metoda szyfrowania, w ktorej u_zywany jest losowo wy-

brany klucz

k

1



:

:

:



k

n

. Samo szyfrowanie odbywa si

,

e przy pomocy

X

OR

. Istotne

jest, by do ka_zdego szyfrowania u_zywac

innego, wygenerowanego niezale_znie

klucza

. Zasadzie tej metoda zawdzi

,

ecza sw

,

a nazw

,

e.

Nast

,

epuj

,

ace wlasnosci s

,

a kluczowe dla metody one-time pad:



Kryptogram jest tak_ze ci

,

agiem losowym

n

bitow, tzn. ma ten sam rozklad

prawdopodobienstwa co ci

,

agi bitow wygenerowane przez rzucanie monet

,

a

(wyrzucenie reszki powoduje dopisanie 1, wyrzucenie orla { dopisanie 0).



Bez znajomosci klucza

_zadna

informacja dotycz

,

aca tekstu jawnego nie mo_ze

byc wydedukowana z kryptogramu (bez wzgl

,

edu na zastosowane moce obli-

czeniowe itp.). Wlasnosc ta bywa nazywana bezpieczenstwem doskonalym.

Dla udowodnienia pierwszej wlasnosci zauwa_zmy, _ze jesli

k

i

=

a

i

, to

c

i

= 0, oraz

_ze

c

i

= 1 w przeciwnym wypadku. Zatem prawdopodobienstwo, _ze

c

i

= 0 jest rowne

1

2

niezale_znie od wartosci

a

i

. Zatem

i

-ty bit kryptogramu jest losowy. Poniewa_z

bity

k

i

s

,

a losowane niezale_znie od siebie, wi

,

ec i bity kryptogramu s

,

a niezale_zne, tak

jak w przypadku ci

,

agow jakie otrzymujemy rzucaj

,

ac monet

,

a.

Niech

c

1

:

:

:

c

n

b

,

edzie dowolnym ci

,

agiem bitow. Dla udowodnienia drugiej wlas-

nosci zauwa_zmy, _ze dla ka_zdego tekstu jawnego

d

1

:

:

:

d

n

istnieje dokladnie jeden

R

OZDZIA

L

2.

PODST

A

W

O

WE

TECHNIKI

SZYFR

O

W

ANIA

15

klucz

k

1

:

:

:

k

n

taki, _ze poprzez szyfrowanie otrzymujemy kryptogram

c

1

:

:

:

c

n

. Istot-

nie, dla

i

= 1



:

:

:



n

spelniona musi byc rownosc

c

i

=

d

i

X

OR

k

i

, sk

,

ad

k

i

=

d

i

X

OR

c

i

.

Poniewa_z kryptogram

c

1

:

:

:

c

n

odpowiada ka_zdemu mo_zliwemu tekstowi jawnemu

z takim samym prawdopodobienstwem, nic nie mo_zna wywnioskowac o ksztalcie

tekstu jawnego bez znajomosci klucza.

Zastosowania one-time pad:

jedn

,

a dziedzin

,

a zastosowan jest szyfrowanie sto-

sunkowo krotkich, ale bardzo wa_znych informacji, jak rozkazy wojskowe o strate-

gicznym znaczeniu (na przyklad o wystrzeleniu rakiet j

,

adrowych). U_zywanie w

tej sytuacji szyfrow mo_zliwych do zlamania (chocby olbrzymim nakladem obliczen)

niesie niebezpieczenstwo, _ze faktycznie szyfry zostan

,

a zlamane.

Problemy ze stosowaniem one-time pad:

zasady u_zywania one-time pad

mowi

,

a, _ze klucz



musi byc zawczasu uzgodniony przez osoby komunikuj

,

ace si

,

e



musi byc wybrany naprawd

,

e losowo (co technicznie nie jest latwe,

patrz rozdzial 7)



musi byc przechowywany w bezpieczny sposob



musi byc co najmniej tak dlugi jak szyfrowany tekst.

Ka_zdy z powy_zszych warunkow stwarza niedogodnosci dla u_zytkownikow i zaw

,

e_za

pole praktycznych zastosowan one-time pad.

Niebezpieczenstwo u_zycia wielokrotnie tego samego klucza:

Zalo_zmy, _ze

szyfrujemy dlugi tekst

a

0

a

1

:

:

:

przy pomocy klucza dlugosci

n

. Poniewa_z brakuje

nam bitow klucza, u_zywamy nast

,

epuj

,

acej formuly:

c

i

=

a

i

X

OR

k

i

mod

n

:

Inaczej mowi

,

ac, bloki dlugosci

n

szyfrujemy ka_zdorazowo przy pomocy tego samego

klucza

k

0

:

:

:

k

n;

1

. Zauwa_zmy, _ze wtedy

c

j

X

OR

c

n

+

j

= (

a

j

X

OR

k

j

)

X

OR

(

a

n

+

j

X

OR

k

j

) =

a

j

X

OR

a

n

+

j

:

Zatem z latwosci

,

a mo_zna bez znajomosci klucza na podstawie samego kryptogramu

obliczyc

a

j

X

OR

a

n

+

j

!

Zlamanie tak skonstruowanego kryptogramu mo_ze si

,

e odbywac wedlug nast

,

e-

puj

,

acego scenariusza. Z du_zym prawdopodobienstwem ka_zdy tekst zawiera dlugie

ci

,

agi spacji. Zakladaj

,

ac, _ze

a

j

jest spacj

,

a mo_zna obliczyc

a

j

+

n

. Czyni

,

ac tak dla

ka_zdego

j

otrzymujemy pewien tekst. Szukamy w nim zrozumialych fragmentow.

W miejscach, gdzie

n

pozycji do tylu w tekscie jawnym wyst

,

epuje blok spacji

otrzymamy w ten sposob fragmenty tekstu jawnego. Jesli potramy je rozpoznac,

to dysponujemy bitami

a

i

,

c

i

dla odpowiednich

i

. St

,

ad wyliczamy

k

i

mod

n

=

a

i

X

OR

c

i

. Znalezione wartosci klucza u_zywamy nast

,

epnie dla calego kryptogramu w

celu odszyfrowania innych fragmentow tekstu jawnego. Prac

,

e mo_zna kontynuowac

probuj

,

ac zgadn

,

ac kolejne wartosci

k

i

na granicy odszyfrowanych regionow spraw-

dzaj

,

ac czy prowadzi to do sensownego uzupelnienia odgadni

,

etych fragmentow tekstu

jawnego.

2.0.8 S-boksy

S-boksy s

,

a nadzwyczaj istotnymi skladnikami algorytmu DES (

D

ata

E

ncryption

S

tandard) najwa_zniejszego w praktyce algorytmu szyfruj

,

acego w momencie powsta-

wania tej ksi

,

a_zki. Ka_zdy S-boks jest zdeniowany poprzez macierz rozmiaru 4



16

zawieraj

,

ac

,

a liczby z przedzialu od 0 do 15 (patrz rys. 2.2).

R

OZDZIA

L

2.

PODST

A

W

O

WE

TECHNIKI

SZYFR

O

W

ANIA

16

15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13

4 1 14 8 13 6 2 11 15 12 9 7 9 10 5 0

0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8

14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7

argument= 111010, wynik= 10

10

= 1010

2

wiersz 2, kolumna 13

-

6

Rysunek 2.2: Szyfrowanie przy pomocy S-boksow (rysunek przedstawia S-boks o

nazwie S1)

Sposob dzialania S-boksow.

S-boks deniuje funkcj

,

e, ktorej argumentami s

,

a

ci

,

agi zlo_zone z 6 bitow, a wartosciami ci

,

agi zlo_zone z 4 bitow. Obliczenie wartosci

dla argumentu

x

ma nast

,

epuj

,

acy przebieg:



pierwszy i ostatni bit argumentu

x

tworz

,

a liczb

,

e w systemie dwojkowym wy-

znaczaj

,

ac

,

a numer wiersza (wiersze numerujemy od 0 do 3),



pozostale 4 bity

x

wyznaczaj

,

a numer kolumny (kolumny numerujemy od 0 do

15),



na przeci

,

eciu wyznaczonych kolumny i wiersza znajduje si

,

e pojedynczy ele-

ment, liczba ta jest szukan

,

a wartosci

,

a funkcji.

Wybor liczb znajduj

,

acych si

,

e w S-boksie ma fundamentalne znaczenie dla jakosci

szyfrowania. Wybor S-boksow stosowanych w praktyce nie byl do konca procesem

jawnym, znanych jest jednak kilka regul, ktore wzi

,

eto pod uwag

,

e. Nie jest znana

_zadna prosta i elegancka analiza matematyczna, ktora prowadzilaby do wyboru

takich a nie innych S-boksow. W praktyce stosowane s

,

a S-boksy o nazwach S1, S2,

:

:

:

, S8.

Efekt lawinowy:

Jedn

,

a z podstawowych zasad szyfrowania jest to, by zmiana

pojedynczego bitu w tekscie jawnym powodowala zmian

,

e wielu bitow w kryptogra-

mie. W idealnej sytuacji powinno to powodowac zmian

,

e mniej wi

,

ecej tylu bitow,

ile bysmy zmienili w wypadku ich ustawienia wedlug rzutow monet

,

a. Tym samym

podobne teksty jawne nie maj

,

a podobnych kryptogramow! Wlasnosc ta utrudnia

w znacz

,

acy sposob kryptoanaliz

,

e. W tej sytuacji mowimy o

efekcie lawinowym

,

dla podkreslenia, _ze zmiana pojedynczego bitu w tekscie jawnym powoduje lawin

,

e

zmian w kryptogramie.

Przy pomocy S-boksow mo_za zrealizowac efekt lawinowy. O ile S-boks stosujemy

do bitow (

x

y 

z



u

v 

w

) to zmiana

x

lub

w

powoduje zmian

,

e numeru wiersza. Rzut

oka na S-boks z rys. 2.2 pozwala stwierdzic, _ze wiersze nie s

,

a do siebie podobne.

Dlatego nie ma _zadnego powodu, by po zmianie

x

lub

w

wynik przypominal w

jakikolwiek sposob stary wynik. Podobne zjawisko odnosi si

,

e do kolumn, gdy_z

kolumny S-boksu rownie_z nie s

,

a podobne.

Gdy S-boksy s

,

a u_zywane wielokrotnie, wtedy efekt lawinowy ulega spot

,

egowaniu

i sposob w jaki zmiana pojedynczego bitu wplywa na zmian

,

e koncowego wyniku jest

coraz bardziej skomplikowany.

Kryteria wyboru S-boksow:

Poni_zej omawiamy niektore wa_zne wlasnosci, ja-

kie powinny byc spelnione przez dobre S-boksy. Ka_zda z nich zostala sformulowana

na zasadzie

\jesli wlasnosc nie jest spelniona, to kryptoanaliza mo_ze byc ulatwiona\

.

R

OZDZIA

L

2.

PODST

A

W

O

WE

TECHNIKI

SZYFR

O

W

ANIA

17



Ka_zdy wiersz S-boksu zawiera wszystkie liczby calkowite od

0

do

15

.

Wlasnosc ta zapewnia, _ze sama znajomosc wiersza nie daje _zadnej informacji

o wartosci koncowej.



Funkcja obliczana przez S-boks nie jest funkcj

,

a aniczn

,

a,

tzn. _zaden bit wyniku nie da si

,

e przedstawic jako

c

0

+

P

6

i

=1

c

i



x

i

, gdzie

x

i

oznacza

i

-ty bit argumentu, zas operacje arytmetyczne wykonywane s

,

a

modulo 2. Gdyby bity wyniku byly wyra_zalne za pomoc

,

a funkcji anicznych,

to kryptoanaliza bylaby powa_znie ulatwiona. Istotnie, po pierwsze skladanie

S-boksow nie mialoby sensu { dalej poruszalibysmy si

,

e w obr

,

ebie funkcji

anicznych, bo zlo_zenie funkcji anicznych jest funkcj

,

a aniczn

,

a. Po drugie,

kryptoanaliza ograniczalaby si

,

e do rozwi

,

azywania ukladow rownan liniowych,

co nie jest trudnym zadaniem.



Zmiana jednego bitu argumentu zmienia co najmniej dwa bity wyniku.

Wlasnosc ta ma zapewnic efekt lawinowy w przypadku wielokrotnego zasto-

sowania S-boksow.



Dla ka_zdego argumentu

x

wartosci obliczane przez S-boks dla argumentow

x

oraz

x

X

OR

001100

ro_zni

,

a si

,

e co najmniej na dwoch pozycjach.



Dla ka_zdego argumentu

x

oraz

e

f

2

f

0



1

g

wartosci obliczane przez S-boks dla

x

oraz

x

X

OR

11

ef

00

ro_zni

,

a si

,

e co najmniej na dwoch pozycjach.



Jesli ustalimy wartosc jednego bitu argumentu oraz jedn

,

a pozycj

,

e wyniku, to dla

okolo polowy ustawien pozostalych bitow argumentu na wybranej pozycji wyniku

otrzymamy

0

.

Wlasnoscta gwarantuje, _ze nawet gdy znamy wartosc jednego bitu argumentu,

to na dowolnej pozycji wyniku otrzymujemy 1 w przybli_zeniu z takimi cz

,

esto-

sciami jak w wypadku losowania bitow przy pomocy rzutow monet

,

a.

Bardzo wskazany jest rownie_z taki wybor wartosci w tablicy S-boksu, by jak najbar-

dziej utrudnione byly znane techniki kryptoanalizy, takie jak kryptoanaliza ro_zni-

cowa i liniowa (patrz rozdz. 12).

Rozdzia

l

3

Algorytmy symetryczne

3.1

DES

{

Data

Encryption

Standard

Zanim przejdziemy do technicznego opisu algorytmu DES, sformu
lujmy kilka ogol-

nych uwag na jego temat:

DES jest symetrycznym algorytmem szyfruj

,

acym, ten sam klucz jest u_zywany

do szyfrowania i deszyfrowania.
Szczego
lowy opis algorytmu DES zosta
l celowo opublikowany. Chodzi
lo o

przekonanie potencjalnych u_zytkownikow, _ze bezpieczenstwo metody nie tkwi

w tajnosci jej budowy, ale w konstrukcji odpornej na kryptoanaliz

,

e. Bowiem

ka_zda metoda, ktorej szczego
ly nie zosta
ly ujawnione, mo_ze zawierac w sobie

tzw.

tylne drzwi

, czyli miejsce w algorytmie, ktore mo_ze byc wykorzystane

przez przeciwnika znaj

,

acego szczego
ly algorytmu na zdobycie informacji nie-

dost

,

epnych w zwyk
lym trybie (na przyk
lad dotycz

,

ace u_zywanych kluczy).

DES jest znacz

,

aco szybszy, gdy jest zaimplementowany jako hardware a nie

jako software. Algorytm zosta
l celowo tak zaprojektowany, aby zniecz

,

ecic do

u_zywania implementacji software'owych uwa_zanych za bardziej podatne na

atak (
latwiej jest si

,

e w
lamac do systemu i niepostrze_zenie wymienic software,

ni_z dokonac zycznego w
lamania by wymienic hardware). Uk
lady realizuj

,

ace

DES s

,

a bardzo szybkie (na przyk
lad 1 GB/sek.) dla porownania dobry soft-

ware na PC mo_ze miec pr

,

edkosc tysi

,

ace razy ni_zsz

,

a.

DES szyfruje bloki z
lo_zone z 64 bitow, co daje 8 liter ASCII, ka_zda zao-

patrzona w bit parzystosci. Klucze sk
ladaj

,

a si

,

e rownie_z z 64 bitow, przy

czym 8 bitow jest bitami parzystosci. Tak wi

,

ec w istocie w trakcie wyboru

klucza mo_zna okreslic jedynie 56 bitow, reszta jest generowana automatycznie.

Post

,

ep w dziedzinie technologii i zwi

,

azane z tym obni_zenie kosztow kry-

ptoanalizy wyzwoli
ly dyskusje, czy d
lugosc kluczy DES-a nie jest za ma
la.

Koszty znalezienia klucza na podstawie dostatecznej ilosci par tekst jawny{

kryptogram zaszyfrowany tym kluczem bywaj

,

a szacowane jedynie na miliony

dolarow USA.
DES zosta
l w USA uznany za standard dla celow niemilitarnych. Zosta
l

wst

,

epnie zaprojektowany w osrodku badawczym IBM w Yorktown Heights,

a nast

,

epnie zmody kowany przez NSA (National Security Agency), rz

,

adowy

organ w USA zajmuj

,

acy si

,

e problemami bezpieczenstwa narodowego. Wywo-

la
lo to wiele podejrzen, _ze NSA zna

tylne drzwi

umo_zliwiaj

,

acej
lamanieszyfrow

generowanych przy pomocy DES-a. Poniewa_z DES sta
l si

,

e w mi

,

edzyczasie

18

R

OZDZIA

L

3.

ALGOR

YTMY

SYMETR

YCZNE

19

standardem w zastosowaniach komercyjnych na ca
lym swiecie, dawa
loby to

USA olbrzymie korzyscie w zakresie militarnym i gospodarczym.
W odniesieniu do DES-a nie zosta
ly opublikowane _zadne prace daj

,

ace tej

metodzie solidne podstawy matematyczne. Jednak_ze ponad 20 lat badan

akademickich potwierdzaj

,

a, _ze konstrukcja DES-a jest bardzo wyra nowana.

Jakkolwiek w zakresie kryptoanalizy DES-a osi

,

agni

,

eto du_ze post

,

epy, nie za-

grozi
ly one znacz

,

aco stosowaniu tej metody w praktyce. Z drugiej strony

uproszczone wersje DES-a mog

,

a byc z
lamane znacz

,

aco mniejszym kosztem.

Interesuj

,

ace jest, _ze proby ulepszen DES-a dotychczas nie doprowadzi
ly do

znacz

,

acych post

,

epow i DES nie doczeka
l si

,

e nowej, lepszej wersji.

3.1.1 Szyfrowanie DES-em

Szyfrowanie i deszyfrowanie przy pomocy DES-a sk
lada si

,

e z 16

rund

. W trakcie

ka_zdej rundy dokonywane s

,

a te same obliczenia, ale na wynikach obliczen z poprzed-

niej rundy i specjalnym podkluczu generowanym z 64-bitowego klucza. Dodatkowo,

przed pierwsz

,

a rund

,

a i po ostatniej rundzie bity s

,

a permutowane w ustalony sposob.

Generowanie podkluczy

W celu uzyskania podkluczy u_zywanych podczas poszczegolnych rund usuwamy

najpierw 8 bitow parzystosci zawartych w kluczu. Nast

,

epnie z pozosta
lych 56 bitow

tworzonych jest 16 podkluczy, ka_zdy sk
ladaj

,

acy si

,

e z 48 bitow. Tak utworzony

i

-

ty klucz oznaczac b

,

edziemy przez

K

i

b

,

edzie on u_zywany w trakcie

i

-tej rundy.

Ka_zdy podklucz sk
lada si

,

e ze z gory okreslonych bitow orginalnego klucza { dla

ka_zdego podklucza s

,

a to inne bity i ustawione w innej kolejnosci. Sposob tworzenia

podkluczy jest jawny i zosta
l opublikowany wraz z opisem DES-a. Maj

,

ac na uwadze

koszty hardware'u wybrano taki sposob wybierania bitow podkluczy, jaki
latwo

daj

,

e si

,

e zrealizowac hardware'owo. Interesuj

,

ace jest, i_z znane metody kryptoana-

lizy DES-a w najbardziej istotnym momencie nie wykorzystuj

,

a zale_znosci mi

,

edzy

wartosciami bitow podkluczy.

Permutacja pocz

,

atkowa i koncowa

Na pocz

,

atku bity tekstu jawnego s

,

a permutowane. Nie ma to _zadnego celu kry-

ptogra cznego. Zauwa_zmy jednak, _ze permutacja ta mo_ze byc z
latwosci

,

a zaim-

plementowana hardware'owo. Po prostu poszczegolne bity doprowadzone s

,

a za

pomoc

,

a drutow (dok
ladniej po
l

,

aczen w uk
ladzie VLSI) na odpowiednie miejsca.

Czas obliczen permutacji odpowiada tu jedynie czasowi w jakim informacje dotr

,

a

po drutach na miejsca przeznaczenia. W przeciwienstwie do tego implementacja

software'owa wymaga d
lugich obliczen: ka_zdy bit oddzielnie musi byc przekopio-

wany na miejsce przeznaczenia.

Pod koniec szyfrowania uzyskane bity s

,

a permutowane permutacj

,

a odwrotn

,

a do

pocz

,

atkowej. Permutacja ta jest nazywana

permutacj

,

a koncow

,

a

.

Runda DES-a

Dane wejsciowe rundy

i

+1 sk
ladaj

,

a si

,

e z dwu ci

,

agow 32-bitowych:

L

i

(pierwszych

32 bitow b

,

ed

,

acych wynikiem rundy

i

) oraz

R

i

(pozosta
le 32 bity uzyskane w rundzie

i

). Zachodz

,

a nast

,

epuj

,

ace zwi

,

azki:

L

i+1

=

R

i

R

i+1

=

L

i

X

OR

f

(

R

i

K

i+1

)

(3.1)

R

OZDZIA

L

3.

ALGOR

YTMY

SYMETR

YCZNE

20

gdzie

f

jest funkcj

,

a, ktora posiada zasadnicze znaczenie dla szyfrowania. Obliczenie

wartosci funkcji

f

jest przedstawione na rys. 3.2 i dokonuje si

,

e w nast

,

epuj

,

acy sposob:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

numery bitow na wejsciu

numery bitow na wyjsciu

...

po
l

,

aczenia realizuj

,

ace

permutacj

,

e z

rozszerzeniem

@

@

@

@

@

@

;

;

;

;

;

;

(

(

(

(

(

(

(

(

(

(

(

(

(

(

(

(

(

(

(

(

(

(

(

(

32

1 2 3 4

5 6 7 8

9 10 11

Rysunek 3.1: Permutacja z rozszerzeniem

1. Poprzez tzw.

permutacj

,

e z rozszerzeniem

otrzymuje si

,

e ci

,

ag z
lo_zony z 48

bitow z 32 bitow

R

i

(32 bity

R

i

s

,

a kopiowane na 48 pozycji, niektore z nich

dwukrotnie, patrz rys. 3.1).

2. Na otrzymanych 48 bitach jest dokonywana operacja XOR z odpowiadaj

,

acymi

im bitami podklucza

K

i+1

.

3. Otrzymane 48 bitow dzielone jest na 8 grup po 6 bitow. Ka_zda grupa pod-

dawana jest dzia
laniu S-boksu. (S-Boks u_zywany przez

i

-t

,

a grup

,

e nazywany

jest Si.)

4. Otrzymane 32 bity s

,

a na koniec permutowane.

f

(

R

i

K

i+1

)

?





permutacja

?





S

1





S

2





S

3





S

4





S

5





S

6





S

7





S

8

H

H

H

H

j

Q

Q

Q

s

S

S

w

B

B

N























+

/

?

?

?

?

?

?

?

?





XOR

?

K

i+1

H

H

H

H

H

H

j



















permut. z rozszerz.

?

R

i

?

Rysunek 3.2: Funkcja

f

DES-a

R

OZDZIA

L

3.

ALGOR

YTMY

SYMETR

YCZNE

21

3.1.2 Deszyfrowanie DES-em

Nale_za
loby oczekiwac, _ze aby deszyfrowac kryptogram nale_zy ca
le obliczenie sk
la-

daj

,

ace si

,

e na szyfrowanie odtworzyc od konca do pocz

,

atku. Ale dla S-boksow nie

jest to mo_zliwe! Jednemu wynikowi otrzymanemu przez S-boks odpowiada wiele

mo_zliwych argumentow. Pomaga tu jednak nast

,

epuj

,

acy wybieg: z rownosci (3.1)

wynika, i_z:

R

i;1

=

L

i

L

i;1

=

R

i

X

OR

f

(

R

i;1

K

i

) =

R

i

X

OR

f

(

L

i

K

i

)

Jesli wi

,

ec znamy

L

i

,

R

i

oraz podklucz

K

i

, to na podstawie powy_zszych rownosci

mo_zemy obliczyc

L

i;1

i

R

i;1

. Tak wi

,

ec nie musimywcale obliczacfunkcji odwrotnej

do funkcji obliczanych przez S-boksy.

Latwo widac, _ze podczas deszyfrowania dokonywane s

,

a te same operacje co

podczas szyfrowania (tylko podklucze wyst

,

epuj

,

a w odwrotnej kolejnosci). Z tego

wzgl

,

edu ten sam hardware mo_ze byc u_zyty do szyfrowania i deszyfrowania.

Zauwa_zylismy, _ze wzory (3.1) stwarzaj

,

a dogodne mo_zliwoscideszyfrowania. Inte-

resuj

,

ace jest, _ze szyfrowanie wed
lug schematu danego tymi wzorami zdaje si

,

e miec

solidne podstawy teoretyczne (por. 4]). Jest to jeden z argumentow przemawiaj

,

a-

cych na korzysc DES-a.

3.2

T

rzykrotn

y

DES

Wielkosc klucza u_zywanego przez algorytm DES wydaje si

,

e byc niewystarczaj

,

aca.

Z tego wzgl

,

edu podj

,

eto szereg prob mody kacji DES-a, tak aby w istotny sposob

wykorzystywac d
lu_zsze klucze. Wiele tych prob skonczy
lo si

,

e niepowodzeniem.

Okazywa
lo si

,

e bowiem, i_z koszty zwi

,

azane ze z
lamaniem kryptogramow utworzo-

nych przy pomocy tych metod s

,

a porownywalne z kosztami z
lamania kryptogramow

utworzonych przy pomocy DES-a (przynajmniej przy u_zyciu znanych metod
la-

mania szyfrow). Bardziej skomplikowana budowa algorytmu i d
lu_zsze klucze nie

oferowa
ly wi

,

ec wi

,

ekszego bezpieczenstwa.

Metod

,

a niekiedy stosowan

,

a w praktyce jest

trzykrotny DES

. U_zywamy w nim

dwoch kluczy

S

1

,

S

2

, ka_zdy b

,

ed

,

acy zwyk
lym kluczem DES-a. Szyfrowanie tekstu

jawnego ma nast

,

epuj

,

acy przebieg:

1. tekst jawny szyfrowany jest kluczem

S

1

,

2. wynik kroku 1 jest deszyfrowany kluczem

S

2

,

3. wynik kroku 2 jest powtornie szyfrowany kluczem

S

1

.

Aby z kryptogramu otrzymac z powrotem tekst jawny wystarczy oczywiscie wyko-

nac nast

,

epuj

,

ace kroki:

1. kryptogram deszyfrowany jest kluczem

S

1

,

2. wynik kroku 1 jest szyfrowany kluczem

S

2

,

3. wynik kroku 2 jest powtornie deszyfrowany kluczem

S

1

.

3.3

Szyfro

w

anie

tekst

ow

do

w

olnej

d

lugo



sci

DES szyfruje tylko bardzo krotkie teksty (8 liter ASCII!). Aby DES uczynic

u_zytecznym trzeba znalezc sposob na szyfrowanie tekstow dowolnej d
lugosci. Po-

ni_zej przedstawiamy trzy takie ogolne metody rozszerzaj

,

ace szyfrowanie tekstow

ustalonej d
lugosci, powiedzmy

k

, na teksty dowolnej d
lugosci.

R

OZDZIA

L

3.

ALGOR

YTMY

SYMETR

YCZNE

22

3.3.1 Elektroniczna ksi

,

a_zka kodowa

Elektroniczna ksi

,

a_zka kodowa

(inaczej

ECB

, czyli

Electronic Codebook

) funkcjo-

nuje jak nast

,

epuje (patrz rys. 3.3): tekst jawny dzielony jest na bloki d
lugosci

k

.

Ka_zdy z tych blokow jest oddzielnie szyfrowany przy pomocy tego samego klucza.

kryptogram

tekst jawny

blok 1

blok 2

blok 3

DES

DES

DES

-

-

-

K

K

K

?

?

?

?

?

?











 

Rysunek 3.3: Schemat trybu ECB

Tryb ECB ma t

,

a zalet

,

e, _ze uszkodzenie lub utrata pojedynczych blokow nie

ma wp
lywu na mo_zliwosc deszyfrowania pozosta
lych cz

,

esci kryptogramu. Z drugiej

strony mo_zliwy jest atak nie wymagaj

,

acy z
lamania szyfru. Przesledzimy to na

nast

,

epuj

,

acym przyk
ladzie:

Przyklad ataku na ECB:

Za
lo_zmy, _ze komunikacja pomi

,

edzy dwoma bankami

odbywa si

,

e w trybie ECB. W ten sposob szyfrowane s

,

a przelewy mi

,

edzy kontami

obu bankow. Za
lo_zmy, _ze specy kacja kont, na jakie nale_zy dokonac przelewow ma

nast

,

epuj

,

ac

,

a postac:

przelew =

kon-

to

odbior- ca

wartosc przelewu

kryptogram = blok 1 blok 2 blok 3 blok 4 blok 5 blok 6

Przest

,

epca Mallet, ktory jest w stanie mody kowac tresc kryptogramow nap
ly-

waj

,

acych do banku, mo_ze przeprowadzic nast

,

epuj

,

acy atak:

1. Mallet dokonuje 17 przelewow na swe konto, zawsze t

,

e sam

,

a kwot

,

e pieni

,

edzy.

Nast

,

epnie identy kuje w przesy
lanych kryptogramach taki kryptogram konta,

na ktory dokonano dok
ladnie 17 przelewow i w dodatku na t

,

e sam

,

a kwot

,

e.

Mallet mo_ze w tym momencie za
lo_zyc, _ze chodzi tu o jego konto. W ten sposob

poznaje kryptogram numeru swego konta mimo, i_z nie zna klucza u_zytego do

szyfrowania.

2. Mallet zamienia w pewnej ilosci przep
lywaj

,

acych kryptogramow kod numeru

konta, wstawiaj

,

ac na to miejsce kryptogram numeru swego konta. Dzi

,

eki temu

bank dopisuje do konta Malleta kwoty przeznaczone pierwotnie dla innych

osob.

3. Mallet sprawdza stan swego konta i dokonuje przelewu na swe konto w kraju,

z ktorym nie podpisano umowy o ekstradycji. Nast

,

epnie udaje si

,

e sladem

pieni

,

edzy zanim ktos si

,

e zorientuje.

Aby unikn

,

ac sytuacji opisanej powy_zej trzeba u_zyc bezpieczniejszego trybu szy-

frowania. Dwa takie tryby opisujemy poni_zej.

Jako ciekawostk

,

e dodajmy, _ze mimo wskazanych powy_zej zagro_zen instytucje

nansowe cz

,

esto lekkomyslnie u_zywaj

,

a trybu ECB do transmisji wa_znych danych.

R

OZDZIA

L

3.

ALGOR

YTMY

SYMETR

YCZNE

23

3.3.2 Cipher Block Chaining

Cipher Block Chaining

(CBC) jest metod

,

a, dzi

,

eki ktorej ten sam blok tekstu

jawnego jest szyfrowany w ro_znych miejscach w ro_zny sposob. Osi

,

agane jest to

w nast

,

epuj

,

acy sposob. Rozwa_zmy algorytm szyfruj

,

acy bloki d
lugosci

k

. Niech

E

K

(

X

) oznacza kryptogram uzyskany z tekstu jawnego

X

przy pomocy klucza

K

. Jesli tekst jawny sk
lada si

,

e z blokow

P

1

P

2

P

3

:

:

:

d
lugosci

k

, to kryptogram

uzyskany przy pomocy klucza

K

sk
lada si

,

e blokow

C

1

C

2

C

3

:

:

:

(rownie_z d
lugosci

k

) zde niowanych nast

,

epuj

,

aco:

C

1

=

E

K

(

P

1

X

OR

I

)

C

i

=

E

K

(

P

i

X

OR

C

i;1

)

:

Ci

,

ag

I

wyst

,

epuj

,

acy w powy_zszym wzorze jest generowany losowo i przesy
lany w

sposob niezaszyfrowany. Zauwa_zmy, _ze kryptogramy poszczegolnych blokow s

,

a ze

sob

,

a powi

,

azane: dla otrzymania

C

i

wykorzystujemy

C

i;1

, a nie tylko

P

i

. Poniewa_z

C

i

zale_zy od

C

i;1

, a

C

i+1

od

C

i

, wi

,

ec posrednio

C

i+1

zale_zy od

C

i;1

. Zale_znosci

tego typu przenosz

,

a si

,

e dalej i ostatecznie ka_zdy blok

C

j

jest zale_zny od wszystkich

blokow

C

1

:

:

:

C

j

;1

, a co za tym idzie rownie_z od

I

P

1

P

2

:

:

:

P

j

;1

.

Deszyfrowywanie tak uzyskanych kryptogramow jest stosunkowo proste (poni_zej

D

oznacza funkcj

,

e deszyfruj

,

ac

,

a dla blokow d
lugosci

k

):

P

1

=

D

K

(

C

1

)

X

OR

I

P

i

=

D

K

(

C

i

)

X

OR

C

i;1

:

(3.2)

Odnotujmy kilka w
lasnosci szyfrowania w trybie CBC:

Zaleta: takie same bloki z regu
ly s

,

a reprezentowane z regu
ly poprzez bloki

ro_znej postaci w kryptogramie. Co wi

,

ecej, ten sam tekst jawny jest szyfrowany

w inny sposob, o ile wybierzemy inny ci

,

ag pocz

,

atkowy

I

.

Wada: nie mo_zna _zadnego bloku

C

i

usun

,

ac z kryptogramu. Stwarza to

k
lopoty, o ile pragn

,

elibysmy przy pomocy CBC szyfrowac zawartosc baz da-

nych. Podobne problemy napotykamyprzy probie wprowadzenia dodatkowego

bloku w srodku tekstu jawnego: od tego miejsca ca
ly kryptogram musi byc

utworzony na nowo.
Wada: podzia
l na bloki musi byc odporny na zak
locenia (dodatkowy bit lub

utrata pojedynczego bitu prowadz

,

a do desynchronizacji szyfrowania i deszy-

frowania).
Zaleta: przek
lamania wewn

,

atrz jednego bloku (bez zmiany ilosci bitow) pro-

wadz

,

a do przek
laman po deszyfrowaniu, ale jedynie w bloku, w ktorym na-

st

,

api
lo przek
lamanie i bloku nast

,

epuj

,

acym po nim. W
lasnosc ta wynika

bezposrednio z wzoru (3.2).

3.3.3 Cypher Feedback

CFB

, czyli

cypher feedback

, jest drugim bezpiecznym trybem szyfrowania d
lugich

tekstow. W odro_znieniu do CBC szyfrowane s

,

a nie ca
le bloki, ale fragmenty z
lo_zone

z 8 bitow, czyli w praktyce 1 litera. Tryb ten mo_ze byc u_zyty na przyk
lad dla

zabezpieczenia komunikacji pomi

,

edzy klawiatur

,

a i serwerem. Oczywiste jest, _ze

w tej sytuacji niezb

,

edne jest natychmiastowe przesy
lanie pojedynczych znakow

bez czekania na zgromadzenie bloku 8 znakow, jak to mia
lo miejsce w przypadku

korzystania z trybu CBC. Mo_zliwe jest rownie_z przesy
lanie t

,

a metod

,

a na przyk
lad

pojedynczych bitow.

R

OZDZIA

L

3.

ALGOR

YTMY

SYMETR

YCZNE

24

Schemat dzia
lania CFB przedstawiony jest na rys. 3.4, przy czym wykorzystano

DES jako metod

,

e szyfrowania pojedynczych blokow. Jednym z zasadniczych sk
lad-

nikow CFB jest rejestr przesuwaj

,

acy. Na pocz

,

atku zawiera on losowo wygenerowany

ci

,

ag, ktory jest przesy
lany w niezaszyfrowanej postaci. W trakcie ka_zdego taktu

pracy CFB przy u_zyciu klucza

K

wykonywane s

,

a nast

,

epuj

,

ace operacje:

1. Zawartosc rejestru przesuwaj

,

acego jest szyfrowana przy pomocy klucza

K

.

2. Z wytworzonego kryptogramu pobieranych jest pierwszych 8 bitow, bity te

s
lu_z

,

a do operacji

X

OR

z 8 bitami koduj

,

acymi nast

,

epn

,

a liter

,

e

P

podawan

,

a

na wejsciu. W wyniku otrzymujemy ci

,

ag osmiu bitow

Z

.

3. Ci

,

ag

Z

tworzy kolejnych 8 bitow wyniku. Ponadto w rejestrze przesuwaj

,

acym

wykonujemy przesuni

,

ecie o 8 pozycji. Jest to przesuni

,

ecie niecykliczne { 8

bitow z lewej strony ulega usuni

,

eciu. Z kolei na osmiu zwolnionych pozycjach

zapisywany jest ci

,

ag

Z

.

P

?

nast

,

epna litera

-





X

OR

-

?

wyjscie

?

8 bitow

Z

?

kryptogram

rejestr przesuwaj

,

acy

?

?

-

DES





klucz

K

Rysunek 3.4: Schemat trybu CFB

3.4

IDEA

Wiele prob podejmowanych by
lo nad zaprojektowaniem algorytmu, ktory zast

,

api
lby

DES. Jedn

,

a z przyczyn by
lo przekonanie, _ze wielkosc kluczy DES-a jest za ma
la.

Inn

,

a wa_zn

,

a przyczyn

,

a by
ly regulacje prawne w USA uznaj

,

ace DES za produkt o

znaczeniu militarnym i u_zywanie go poza granicami USA bez stosownych licencji

za czyn przest

,

epczy. Poniewa_z utrudnia to stosowanie kryptogra i w kontaktach z

partnerami z USA i spoza USA, istnieje potrzeba znalezienia algorytmu, ktorego

stosowanie nie prowadzi
loby do koniktow z amerykanskimi organami bezpieczen-

stwa. Cele te przyswieca
ly powstaniu algorytmu (

I

nternational

D

ata

E

ncryption

S

tandard), wskrocie

IDEA

.

Wlasnosci IDEA:

IDEA jest algorytmem, z ktorego mo_zna korzystac bezp
latnie do celow nie-

komercyjnych. Algorytm jest opatentowany w Europie.

R

OZDZIA

L

3.

ALGOR

YTMY

SYMETR

YCZNE

25

IDEA jest algorytmem nowym, wprowadzonym w latach dziewi

,

ecdziesi

,

atych.

Algorytm spotka
l si

,

e z du_zym zainteresowaniem, w tym rownie_z jesli chodzi

o proby jego kryptoanalizy. Wobec stosunkowo krotkiego okresu od momentu

jego opublikowania nale_zy z ostro_znosci

,

a podchodzic do jego bezpieczenstwa.

IDEA wchodzi jako jeden z komponentow w sk
lad PGP, popularnego pakietu

kryptogra cznego (patrz rozdz. 13.0.16).
Klucze u_zywane przez IDEA s

,

a z
lo_zone z 128 bitow. W praktyce oznacza

to, _ze poszukiwanie pasuj

,

acego klucza do pary kryptogram{tekst jawny po-

przez wyprobowywanie wszystkich kluczy po kolei jest niewykonalne. Mimo

wielkosci kluczy programy szyfruj

,

ace i deszyfruj

,

ace wed
lug algorytmu IDEA

nie s

,

a wolniejsze ni_z programy realizuj

,

ace DES.

3.4.1 Szyfrowanie poprzez algorytm IDEA

Szyfrowanie sk
lada si

,

e z 8 rund. Pojedyncz

,

a rund

,

e schematycznie przedstawia

rys. 3.5. Oprocz tego po ostatniej rundzie dokonywane jest przekszta
lcenie

koncowe (patrz rys. 3.8). Jego znaczenie stanie si

,

e jasne, gdy omawiacb

,

edzie-

my deszyfrowanie.
Ka_zda runda przeprowadza rozmaite operacje na 16-bitowych blokach. Trzy

operacje s

,

a u_zywane:

{

X

OR

dokonywany na poszczegolnych bitach,

{

dodawanie modulo 2

16

(oznaczane dalej symbolem +),

{

mno_zenie modulo (2

16

+ 1) (oznaczane dalej symbolem

).

Klucz zawiera 128 bitow. Z niego generowanych jest szereg podkluczy. W

trakcie rundy

i

u_zywanych jest szesc podkluczy

Z

(i)

1

:

:

:

Z

(i)

6

.

W odro_znieniu do kluczy, tekst jawny zawiera 64 bitow.

Przebieg rundy algorytmu IDEA zosta
l przedstawiony na rys. 3.5. Dane wejsciowe

dla rundy

i

sk
ladaj

,

a si

,

e z 4 blokow po 16 bitow oznaczonych

X

1

:

:

:

X

4

. Rezultat

sk
lada si

,

e z blokow 16-bitowych oznaczonych

Y

1

:

:

:

Y

4

.

3.4.2 Generowanie podkluczy dla algorytmu IDEA

Szyfrowanie przy pomocy algorytmu IDEA wymaga 6

8+4 podkluczy (8 jest ilosci

,

a

rund, ka_zda z rund wykorzystuje 6 podkluczy, dodatkowo przekszta
lcenie koncowe

u_zywa 4 kluczy). Podklucze s

,

a generowane w nast

,

epuj

,

acy sposob:

1. Klucz jest dzielony na bloki 16-bitowe. Daje to pierwszych 8 podkluczy (6

podkluczy dla pierwszej rundy, 2 dla drugiej rundy).

2. Na kluczu wykonuje si

,

e przesuni

,

ecie cykliczne o 25 pozycji. Wynik jest na

nowo dzielony na bloki d
lugosci 16. Daje to nast

,

epnych 8 podkluczy (4

brakuj

,

ace podklucze dla drugiej rundy, 4 dla trzeciej rundy).

3. Operacje z punktu 2 powtarzamy a_z wygenerujemy wszystkie potrzebne pod-

klucze.

3.4.3 Deszyfrowanie przez IDEA

Tak jak w przypadku DES-a potrzebna jest jakas sprytna metoda, albowiem bez-

posrednio wyliczyc dane wejsciowe dla rundy na podstawie danych wyjsciowych dla

rundy by
loby trudno (porownaj rys. 3.5).

R

OZDZIA

L

3.

ALGOR

YTMY

SYMETR

YCZNE

26

X

1

: 16 bitow

X

2

: 16 bitow

X

3

: 16 bitow

X

4

: 16 bitow

?

?

?

?

j

j

+

j

+

j

Z

(i)

4

-

Z

(i)

3

-

Z

(i)

2

-

Z

(i)

1

-

?

?

j

X

j

X

?

?

-

(

(

(

(

(

(

(

(

(

h

h

h

h

h

h

h

h

h

r

r

r

r

h

h

?

(

(

?

j

-

j

+

Z

(i)

5

-

j

+

j

Z

(i)

6

?

?

j

X

?

-

r

j

X

j

X

?

-

r

j

X

?

h

h

h

h

h

h

h

h

h

?

(

(

(

(

(

(

(

(

(

?

?

Y

1

: 16 bitow

Y

2

: 16 bitow

Y

3

: 16 bitow

Y

4

: 16 bitow

...

...

...

...

j

mno_zenie

j

+ dodawanie

j

X

X

OR

Z

1

(

i

)

Z

2

(

i

)

:::

- podklucze rundy

i

Rysunek 3.5: Runda

i

algorytmu IDEA

Idea deszyfrowania dla jednej rundy:

Wprowadzmy nast

,

epuj

,

ace oznaczenia

(patrz rys. 3.6):

A

=

X

1

Z

(i)

1

B

=

X

2

+

Z

(i)

2

C

=

X

3

+

Z

(i)

3

D

=

X

4

Z

(i)

4

:

Niech

E

=

B

X

OR

Y

3

F

=

C

X

OR

Y

2

(porownaj rys. 3.6).
Latwo zauwa_zyc korzystaj

,

ac z rys. 3.6, _ze

Y

3

X

OR

Y

4

= (

B

X

OR

E

)

X

OR

(

E

X

OR

D

) =

B

X

OR

D :

Zatem mo_zemy obliczyc wartosc

B

X

OR

D

. Podobnie mo_zna obliczyc

A

X

OR

C

.

Zauwa_zmy, _ze

B

X

OR

D

i

A

X

OR

C

s

,

a wynikami otrzymywanymi przez dwa w

,

ez
ly

obliczaj

,

ace

X

OR

w srodkowej cz

,

esci uk
ladu przedstawionego na rys. 3.6. Tak wi

,

ec

znaj

,

ac klucze

Z

(i)

5

i

Z

(i)

6

mo_zna obliczyc

E

i

F

. Przy ich pomocy otrzymujemy:

A

=

Y

1

X

OR

F

B

=

Y

3

X

OR

E

C

=

Y

2

X

OR

F

D

=

Y

4

X

OR

E

:

Znaj

,

ac

A

B

C

D

i podklucze

Z

(i)

1

:

:

:

Z

(i)

4

mo_zna na koniec wyliczyc

X

1

:

:

:

X

4

.

W opisany powy_zej sposob znaj

,

ac podklucze wyprowadzilismy dane wejsciowe

rundy z jej wyniku. W celu przeprowadzenia deszyfrowania czynimy to dla wszyst-

kich rund, poczynaj

,

ac od ostatniej.

R

OZDZIA

L

3.

ALGOR

YTMY

SYMETR

YCZNE

27

X

1

X

2

X

3

X

4

?

?

?

?

j

j

+

j

+

j

Z

(i)

4

-

Z

(i)

3

-

Z

(i)

2

-

Z

(i)

1

-

?

?

j

X

j

X

?

?

-

(

(

(

(

(

(

(

(

(

h

h

h

h

h

h

h

h

h

r

r

r

r

h

h

?

(

(

?

j

l

k

-

j

+

l

k

Z

(i)

5

-

j

+

j

Z

(i)

6

?

?

j

X

?

-

r

j

X

j

X

?

-

r

j

X

?

h

h

h

h

h

h

h

h

h

?

(

(

(

(

(

(

(

(

(

?

?

Y

1

Y

2

Y

3

Y

4

...

...

...

...

B

E

F

C

D

A

A

X

OR

C

B

X

OR

D

Rysunek 3.6: Metoda deszyfrowania dla algorytmu IDEA

Realizacja deszyfrowania:

Powy_zej zauwa_zylismy jak deszyfrowac w przypadku

algorytmu IDEA. Jesli wykonywane operacje przedstawimy schematycznie (patrz

rys. 3.7), to zauwa_zamy uderzaj

,

ace podobienstwo do operacji wykonywanych pod-

czas rundy szyfrowania. Jedyna ro_znica polega na tym, _ze arytmetyczne operacje

wykonywane przy u_zyciu 4 podkluczy s

,

a wykonywane nie na pocz

,

atku, ale na koncu

rundy deszyfrowania. Dzi

,

eki temu ten sam uk
lad elektroniczny mo_ze byc u_zyty w

celu szyfrowania i deszyfrowania. Jedynie logiczny podzia
l na rundy jest nieco inny:

najpierw przeprowadzamy operacj

,

e pocz

,

atkow

,

a, odpowiadaj

,

ac

,

a operacji koncowej

szyfrowania, a nast

,

epnie wykonujemy 8 rund, ka_zda z nich zaczynaj

,

aca si

,

e od

operacji

X

OR

.

Podklucze u_zywane podczas deszyfrowania odpowiadaj

,

a podkluczom szyfrowa-

nia wylistowanym w innej kolejnosci. Ponadto by otrzymac podklucze deszyfrowa-

nia musimy cz

,

esc podkluczy odwrocic (te u_zywane do mno_zenia) lub zanegowac (te

u_zywane do dodawania).

R

OZDZIA

L

3.

ALGOR

YTMY

SYMETR

YCZNE

28

Y

1

Y

3

Y

2

Y

4

?

?

?

?

?

?

?

?

j

j

+

j

+

j

Z

(i)

4

;1

-

;Z

(i)

3

-

;Z

(i)

2

-

Z

(i)

1

;1

-

?

?

j

X

j

X

?

?

-

(

(

(

(

(

(

(

(

(

h

h

h

h

h

h

h

h

h

r

r

r

r

h

h

?

(

(

?

j

-

j

+

Z

(i)

5

;1

-

j

+

j

;Z

(i)

6

?

?

j

X

?

-

r

j

X

j

X

?

-

r

j

X

?

h

h

h

h

h

h

h

h

h

?

(

(

(

(

(

(

(

(

(

?

?

X

1

X

3

X

2

X

4

Rysunek 3.7: Schemat deszyfrowania w algorytmie IDEA

16 bitow

16 bitow

16 bitow

16 bitow

16 bitow

16 bitow

?

?

?

?

j

.

j

+

j

j

+

.

Z

(9)

4

-

Z

(9)

3

-

Z

(9)

2

-

Z

(9)

1

-

Z

Z

~





=













9

X

X

X

X

X

X

z

kryptogram

Rysunek 3.8: Przekszta
lcenie koncowe w algorytmie IDEA

Spis rzeczy

1 Pierwszy rzut oka na kryptogra

,

e

4

1.0.1 Szyfrowanie danych

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

4

1.0.2 Podstawowe zastosowania technik szyfrowania

:

:

:

:

:

:

:

:

:

5

1.0.3 Historia kryptograi

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

8

1.0.4 Kontrowersje zwi

,

azane ze stosowaniem kryptograi

:

:

:

:

:

:

9

1.0.5 Korzystanie z produkt ow kryptogracznych

:

:

:

:

:

:

:

:

:

:

10

2 Podstawowe techniki szyfrowania

12

2.0.6 Podstawienie

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

12

2.0.7 XOR i one-time pad

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

13

2.0.8 S-boksy

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

15

3 Algorytmy symetryczne

18

3.1 DES { Data Encryption Standard

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

18

3.1.1 Szyfrowanie DES-em

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

19

3.1.2 Deszyfrowanie DES-em

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

21

3.2 Trzykrotny DES

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

21

3.3 Szyfrowanie tekst ow dowolnej dlugo sci

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

21

3.3.1 Elektroniczna ksi

,

a_zka kodowa

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

22

3.3.2 Cipher Block Chaining

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

23

3.3.3 Cypher Feedback

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

23

3.4 IDEA

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

24

3.4.1 Szyfrowanie poprzez algorytm IDEA

:

:

:

:

:

:

:

:

:

:

:

:

:

:

25

3.4.2 Generowanie podkluczy dla algorytmu IDEA

:

:

:

:

:

:

:

:

:

25

3.4.3 Deszyfrowanie przez IDEA

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

25

4 Algorytmy niesymetryczne

29

4.0.4 Teoria zlo_zono sci obliczeniowej a kryptograa

:

:

:

:

:

:

:

:

:

29

4.0.5 Szyfry plecakowe

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

30

4.1 RSA

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

32

4.1.1 Opis algorytmu RSA

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

33

4.1.2 Testy pierwszo sci

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

35

4.1.3 Aspekty bezpiecze nstwa RSA

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

37

4.1.4 Trudne bity kryptogram ow RSA

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

39

4.2 Algorytm ElGamala

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

41

5 Funkcje jednokierunkowe

43

5.0.1 Kandydaci na funkcje jednokierunkowe

:

:

:

:

:

:

:

:

:

:

:

:

:

44

5.0.2 Hard-core bit

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

45

i

SPIS

RZECZY

ii

6 Jednokierunkowe funkcje hashuj

,

ace

46

6.0.3 Wlasno sci i zastosowania funkcji hashuj

,

acych

:

:

:

:

:

:

:

:

:

46

6.0.4 Ataki przeciw funkcjom hashuj

,

acym

:

:

:

:

:

:

:

:

:

:

:

:

:

:

47

6.1 Techniki o dowodliwych wlasno sciach

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

49

6.1.1 Hashowanie przy pomocy dyskretnego logarytmu

:

:

:

:

:

:

:

49

6.1.2 Rozszerzenie na teksty dowolnej dlugo sci

:

:

:

:

:

:

:

:

:

:

:

:

50

6.2 Praktyczne algorytmy hashuj

,

ace

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

51

6.2.1 MD5

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

51

6.2.2 Hashowanie dowolnie dlugich tekst ow

:

:

:

:

:

:

:

:

:

:

:

:

:

52

7 Ci

,

agi pseudolosowe

55

7.0.3 Wlasno sci ci

,

ag ow pseudolosowych

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

55

7.0.4 Generatory ci

,

ag ow pseudolosowych

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

57

7.0.5 Pseudolosowo s c generatora BBS

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

59

7.1 Zastosowania ci

,

ag ow pseudolosowych

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

59

7.1.1 Szyfrowanie strumieniowe

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

59

7.1.2 Szyfrowanie probabilistyczne

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

60

8 Podpisy cyfrowe

61

8.0.3 Podpisy cyfrowe ElGamala

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

62

8.0.4 DSA

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

63

8.0.5 Slepe podpisy

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

64

8.0.6 Kanal podprogowy

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

65

8.0.7 Podpisy niezaprzeczalne

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

66

9 Uwierzytelnianie

69

9.0.8 Protok ol challenge and response

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

69

9.0.9 Dowody interakcyjne

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

70

9.0.10 Dowody z wiedz

,

a zerow

,

a

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

71

9.0.11 Protok ol Fiege-Fiata-Shamira

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

73

9.0.12 Protok ol Schnorra

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

74

9.0.13 Protok ol Guillou-Quisquartera

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

75

9.0.14 Podpisy cyfrowe poprzez uwierzytelnianie

:

:

:

:

:

:

:

:

:

:

:

76

10 Administracja kluczami

77

10.1 Praktyka gospodarki kluczami

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

77

10.1.1 Urz

,

adzenie kryptograczne

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

77

10.1.2 Generowanie kluczy

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

78

10.1.3 Hierarchia kluczy

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

79

10.1.4 Przechowywanie kluczy

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

79

10.2 Protokoly uzgadniania kluczy

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

80

10.2.1 Uzgadnianie kluczy poprzez szyfrowanie symetryczne

:

:

:

:

:

81

10.2.2 Uzgadnianie klucza przez szyfrowanie asymetryczne

:

:

:

:

:

82

10.2.3 Protok ol Die-Hellmana i jego pochodne

:

:

:

:

:

:

:

:

:

:

:

82

11 Protokoly kryptogra
czne

85

11.0.4 Atak man in the middle

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

85

11.0.5 Dzielenie tajemnic

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

87

11.0.6 Zobowi

,

azanie bitowe

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

88

11.0.7 Pieni

,

adze cyfrowe

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

90

11.0.8 Elektroniczne wybory

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

93

SPIS

RZECZY

iii

12 Kryptoanaliza

95

12.0.9 Kryptoanaliza r o_znicowa

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

96

12.0.10Kryptoanaliza liniowa

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

99

12.0.11R o_znicowa kryptoanaliza bl

,

ed ow

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

100

13 Wybrane implementacje

102

13.0.12Smart cards

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

102

13.0.13Krzywe eliptyczne

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

103

13.0.14Kerberos

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

103

13.0.15Zabezpieczanie komunikacji telefonicznej

:

:

:

:

:

:

:

:

:

:

:

:

106

13.0.16PGP { Pretty Good Privacy

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

107

13.0.17Zabezpieczanie poczty elektronicznej { PEM

:

:

:

:

:

:

:

:

:

108

13.0.18Bezpiecze nstwo w WWW

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

109

13.0.19Protokoly obrotu nansowego

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

109

A Wybrane aspekty teorii liczb

112

B Teoria algorytmow

116

Przedmowa

Do niedawna kryptograa byla obiektem zainteresowania w wi

,

ekszym stopniu slu_zb

wywiadowczych i wojska ni_z przedmiot ow gospodarczych i prywatnych os ob. Post

,

ep

w dziedzinie elektroniki a zwlaszcza gwaltowny rozw oj sieci komputerowych sytuacj

,

e

t

,

e zmienily w radykalny spos ob.

Dawniej, gdy prywatny u_zytkownik dysponowal jedynie komputerem PC nie

wl

,

aczonym do sieci, ochrona danych byla stosunkowo prosta i zapewniona przez

zyczny dost

,

ep do komputera. Na tej samej zasadzie chronione byly dane przecho-

wywane w postaci elektronicznej przez male rmy, dzialy rm, organizacje politycz-

ne. Nie skomplikowaneprotokoly kryptograczne, ale klucz do pomieszczenia z kom-

puterem, czy koperta, w kt orej przesylana byla dyskietka, stanowily ochron

,

e przed

niepowolanym dost

,

epem. Oczywi scie zdarzaly si

,

e kradzie_ze dyskietek, komputer ow,

wlamania do siedzib partii politycznych

:

:

:

. Wi

,

ekszo s c u_zytkownik ow nie czulo

jednak potrzeby skuteczniejszej ochrony swych danych.

Sytuacja zacz

,

ela si

,

e radykalnie zmienia c z chwil

,

a gwaltownego wzrostu sieci

komputerowych. Dotyczylo to nie tylko sieci obejmuj

,

acych szereg dzial ow pojedyn-

czych rm, ale i sieci globalne, takie jak Internet (w tym zwlaszcza World Wide

Web). Zapewnienie bezpiecze nstwa w tych sieciach stalo si

,

e jednym z pierwszo-

planowych zada n decyduj

,

acych o ich dalszym rozwoju. Nowe techniki telekomu-

nikacyjne, takie jak telefonia kom orkowa, telewizja cyfrowa, telebanking, itp., nie

moglyby znale z c swego miejsca w codziennej praktyce, gdyby nie stosowanie technik

kryptogracznych dla ochrony dost

,

epu.

Najpierw rewolucja obj

,

ela komunikacj

,

e w srodowisku naukowym. Pojawienie

si

,

e poczty elektronicznej umo_zliwilo blyskawiczne kontaktowanie sie naukowc ow z

najdalszych kraj ow. Pozwolilo to na olbrzymi wzrost wydajno sci w wielu dziedzi-

nach bada n. Mo_znaby si

,

e spodziewa c, _ze konkurencja i ostra walka o przodownictwo

doprowadzi w srodowisku naukowym do wielu nadu_zy c poczty elektronicznej. Tym

bardziej, _ze nie jest trudne na przyklad przesla c list w ten spos ob, by nadawca po

nagl owku m ogl by c przekonany, _ze pochodzi on od innej osoby. Mo_zliwe jest r ownie_z

przechwytywanie korespondencji przeznaczonej do innych adresat ow. Zjawiska te

jednak stanowily dotychczas w calym srodowisku naukowymbardzo w

,

aski margines.

Powodem zapewne bylo to, i_z komunikowaly si

,

e osoby, kt ore i tak obdarzaly si

,

e

pelnym zaufaniem. Tak wi

,

ec metody, kt ore pozwalalyby na zabezpieczenie przed

odczytem, modykacj

,

a czy te_z preparowaniem list ow elektronicznych przez osoby

trzecie nie byly stosowane.

Te czasy min

,

ely. Wraz z pojawieniem si

,

e World Wide Web Internet stal si

,

e

atrakcyjny dla "szaregou_zytkownika\. WInternecie pojawilysi

,

e interesuj

,

ace zasoby

informacyjne, dzi

,

eki czemu ilo s c u_zytkownik ow zacz

,

ela rosn

,

a c gwaltownie. Co

wi

,

ecej, Internet coraz cz

,

e sciej jest u_zywany nie jako narz

,

edzie zabawy czy rozwijania

zainteresowa n, ale do cel ow komercyjnych. Ju_z dzi s bilety lotnicze kupuj

,

e przez

Internet, literatur

,

e naukow

,

a wybieram przez World Wide Web, a zamiast kupowa c

gazet

,

e z lokalnymi ogloszeniami si

,

egam do jej elektronicznego odpowiednika. W

takiej sytuacji b

,

edzie coraz wi

,

ecej os ob: hardware tanieje, software staje si

,

e coraz

latwiejszy do obslugi przez laika, w wielu krajach pol

,

aczenia telefoniczne wskutek

1

SPIS

RZECZY

2

konkurencji na rynku telekomunikacyjnym staj

,

a si

,

e ta nsze i wy_zszej jako sci. Coraz

latwiejsze b

,

edzie zatem stanie si

,

e kolejnym u_zytkownikiem Internetu. Za par

,

e lat

b

,

edziemy mie c zapewne do czynienia z sytuacj

,

a, gdy Internet b

,

edzie najwi

,

ekszym

supermarketem, najobszerniejsz

,

a gazet

,

a, najwi

,

ekszym Hyde Parkiem,

:

:

:

{przynaj-

mniej w krajach, gdzie uslugi telekomunikacyjne b

,

ed

,

a wystarczaj

,

aco tanie.

Jak ka_zdy wynalazek, rozw oj globalnych sieci komputerowych przynosi korzy sci,

ale i niebezpiecze nstwa. Wiele dyskutuje si

,

e na przyklad na temat mo_zliwo sci

wykorzystywania Internetu przez organizacje przest

,

epcze. Sytuacja przypomina

nieco spory po wynalezieniu samochodu. Nie spos ob cz

,

e sciowo nie przyzna c racji

przeciwnikom automobili maj

,

ac przed oczyma tragiczne statystki o tysi

,

acach ludzi

zabitych na drogach. Nie cofn

,

elo to jednak motoryzacji, tak jak nie do odwr ocenia

jest ju_z rozw oj globalnej sieci komputerowej na swiecie.

Poniewa_z poprzez Internet komunikowa c si

,

e b

,

ed

,

a nie dobrzy i ufaj

,

acy sobie

znajomi, lecz cz

,

esto anonimowi czy wrodzy sobie u_zytkownicy, mijaj

,

a czasy, gdy

niezbyt wiele my slano o bezpiecze nstwie danych i komunikacji. Z jednej strony

podl

,

aczenie do sieci komputerowych stanowi c b

,

edzie warunek wst

,

epny istnienia

rm (tak jak posiadanie telefonu, faxu, czy skrzynki pocztowej), z drugiej strony

podl

,

aczenie to stanowi o mo_zliwo sci wlama n, dewastacji danych i innych dziala n o

charakterze przest

,

epczym.

Oczywi scie u_zytkownicy sieci komputerowych b

,

ed

,

a sie broni c przed niepowo-

lanym dost

,

epem do danych czy manipulacjami dokonywanymi na nich. Pierwsz

,

a

lini

,

a obrony b

,

ed

,

a oczywi scie systemy operacyjne zarz

,

adzaj

,

ace prac

,

a komputer ow i

wykonywaniem zlece n na rzecz u_zytkownik ow. W wielu miejscach ruchu w sieciach

komputerowych (kt ore uzyskaly ju_z modn

,

a nazw

,

e

infostr

ad

) "sprawdzane b

,

ed

,

a

bilety\, a "pasa_zerowie na gap

,

e\ b

,

ed

,

a usuwani z ruchu. R ownocze snie zadaniem

systemu operacyjnego b

,

edzie przestrzeganie, czy u_zytkownicy dokonuj

,

a jedynie do-

zwolonych operacji.

Wskutek zlo_zono sci stawianych zada n systemy operacyjne b

,

ed

,

a stawa c si

,

e coraz

bardziej skomplikowane. Tym samymcoraz trudniej b

,

edzie ich tw orcom przewidzie c

wszystkie mo_zliwo sci, tak aby uniemo_zliwi comini

,

ecie zabezpiecze n zainstalowanych

poprzez system operacyjny. Dotychczasowe doniesienia z tego pola walki s

,

a raczej

pesymistyczne dla system ow operacyjnych. Stoj

,

a one w obliczu mia_zd_z

,

acej przewagi

wlamywaczy zwanych hackerami. Hackerzy nie s

,

a, jakby si

,

e chcialo wierzy c, jedynie

grup

,

a nastoletnich maniak ow komputerowych (czy lagodniej m owi

,

ac, milo snik ow

technik komputerowych). Jest to grupa o olbrzymim potencjale intelektualnym,

nierzadko doskonalym zapleczu sprz

,

etowym i nansowym.

Ostatni

,

a szans

,

a na zagwarantowanie bezpiecze nstwa danych jest kryptograa.

Nie mo_ze ona usun

,

a c wszelkich niebezpiecze nstw (jak na przyklad zniszczenie da-

nych przez wlamywacza komputerowego), ale w wielu sytuacjach skutecznie pomaga

(na przyklad uniemo_zliwia odczyt danych przez niepowolan

,

a osob

,

e). W odr o_znieniu

do innych metod kryptograa dostarcza metod wzgl

,

ednie bezpiecznych. Tak bez-

piecznych, _ze liniami telekomunikacyjnymi dokonuje si

,

e co chwila przelew ow nie-

wyobra_zalnych dla szarego czlowieka sum. I nikt si

,

e nie martwi, _ze kto s wl

,

aczy si

,

e

na lini

,

e i t

,

a drog

,

a powi

,

ekszy stan swego konta o ile s milion ow dolar ow (z kt orymi

odleci natychmiast na wyspy poludniowego Pacyku do kraju, z kt orym zapomniano

zawrze c umow

,

e o ekstardycji przest

,

epc ow).

Miroslaw Kutylowski

Wst

,

ep

Niniejsza ksi

,

a_zka ma za zadanie w bardzo zwi

,

ezly spos ob przedstawi c podstawowe

metody kryptograczne. Wiele interesuj

,

acych technik kryptogracznych zostalo w

niej pomini

,

etych. Nacisk polo_zony zostal na te aspekty, kt ore maj

,

a b

,

ad z mie c mog

,

a

praktyczne zastosowanie. Wskutek tego wiele teoretycznie ciekawych zagadnie n

swiadomie nie poruszamy w tej ksi

,

a_zce. Z drugiej strony, naszym zamyslem bylo, na

tyle na ile to jest mo_zliwe w tak kr otkiej pozycji, umo_zliwi cczytelnikowi zrozumienie

matematycznych mechanizm ow tkwi

,

acych w kryptograi. Tym ksi

,

a_zka ta r o_zni si

,

e

na przyklad od dost

,

epnej na polskim rynku pozycji Bruce'a Schneiera 6], maj

,

acej

bardziej charakter encyklopedii ni_z podr

,

ecznika.

Niniejsza ksi

,

a_zka przeznaczona jest dla student ow informatyki i pokrewnych

dziedzin. Mo_ze by c wykorzystana jako podr

,

ecznik do semestralnego wykladu z kry-

ptograi, jak r ownie_z jako material do samodzielnego studiowania. Do zrozumie-

nia niekt orych cz

,

e sci ksi

,

a_zki niezb

,

edna jest znajomo s c pewnych fakt ow z algebry.

Czytelnik nieobeznany z tymi zagadnieniami mo_ze znale z c brakuj

,

ace informacje w

Dodatku A. Niekiedy konieczna jest znajomo s c standardowych fakt ow z podstaw

informatyki wykladanych na pierwszych latach studi ow informatycznych. Cz

,

e s c

tych poj

,

e c skr otowo przedstawiamy w Dodatku B.

Niniejsza ksi

,

a_zka oparta jest na cz

,

e sci skryptu do wykladu Miroslawa Kutylow-

skiego. Wyklad ten odbyl si

,

e na Wydziale Matematyki i Informatyki Uniwersytetu

Paderborn w semestrze zimowym 1995 roku. Wspomniany skrypt obejmuje pr ocz

kryptograi zagadnienia kod ow samokoryguj

,

acych bl

,

edy i kompresji danych. Jest

on dost

,

epny poprzez World Wide Web pod adresem

http://www.uni-paderborn.de/fachbereich/AG/agmadh/WWW/german/LehreKuty/ikk95/skript.ps.gz

Lista zauwa_zonych bl

,

ed ow, uzupelnienia, itp. znajduj

,

a si

,

e w World Wide Web

pod adresem

http://www.uni-paderborn.de/fachbereich/AG/agmadh/WWW/german/LehreKuty/kryptograa/

Pragniemy podzi

,

ekowa c licznym studentom za udzielon

,

a pomoc. W szczeg olno-

sci wymieni c chcieliby smy Guido Haeselera, kt orego notatki do wykladu w Latex-u

byly podstaw

,

a pierwszej wersji skryptu (i szeregu rysunk ow zawartych w ksi

,

a_zce).

Cz

,

e s c rysunk ow zostala wykonana przez Franka Beste i Ew

,

e Kutylowsk

,

a.

3