Wstep do kryptografii [version 9 Feb 2013 ed.] [PDF]

Zitiervorschau

WST†P DO KRYPTOGRAFII Grzegorz Szkibiel Jesie« 2012/13

Spis tre±ci 1 Kryptograa a steganograa

5

1.1

Steganograa

. . . . . . . . . . . . . . . . . . . . . . . . . . .

6

1.2

Szyfry przestawieniowe . . . . . . . . . . . . . . . . . . . . . .

8

1.3

Systemy kryptograczne

9

. . . . . . . . . . . . . . . . . . . . .

2 Klasyczne metody szyfrowania

12

2.1

Szyfry cykliczne . . . . . . . . . . . . . . . . . . . . . . . . . .

12

2.2

Monoalfabetyczny szyfr Beauforta . . . . . . . . . . . . . . . .

13

2.3

Kody aniczne jednowymiarowe . . . . . . . . . . . . . . . . .

14

2.4

Permutacje alfabetu

. . . . . . . . . . . . . . . . . . . . . . .

15

2.5

Analiza cz¦sto±ci wyst¦powania liter . . . . . . . . . . . . . . .

16

2.6

Homofony i nulle

. . . . . . . . . . . . . . . . . . . . . . . . .

17

2.7

Jednostki dwuliterowe czyli digramy . . . . . . . . . . . . . . .

18

2.8

Szyfr Playfaira

. . . . . . . . . . . . . . . . . . . . . . . . . .

20

2.9

Podwójny szyfr Playfaira . . . . . . . . . . . . . . . . . . . . .

21

2.10 szyfr Delastelle'a

. . . . . . . . . . . . . . . . . . . . . . . . .

22

2.11 Jednostki wieloliterowe . . . . . . . . . . . . . . . . . . . . . .

23

2.12 Szyfry polialfabetyczne . . . . . . . . . . . . . . . . . . . . . .

23

2.13 Ša«cuch szyfrów i DES . . . . . . . . . . . . . . . . . . . . . .

28

3 Maszyny szyfruj¡ce

32

3.1

Zasada dziaªania

. . . . . . . . . . . . . . . . . . . . . . . . .

32

3.2

Jak zªamano szyfr ENIGMY . . . . . . . . . . . . . . . . . . .

36

4 Macierze szyfruj¡ce

41 N

4.1

Algebra liniowa modulo

. . . . . . . . . . . . . . . . . . . .

41

4.2

Szyfry Hill'a . . . . . . . . . . . . . . . . . . . . . . . . . . . .

44

4.3

Aniczne przeksztaªcenia szyfruj¡ce . . . . . . . . . . . . . . .

48

2

5 Pakowanie plecaka

50

5.1

Postawienie problemu . . . . . . . . . . . . . . . . . . . . . . .

50

5.2

Szybko rosn¡ce ci¡gi

. . . . . . . . . . . . . . . . . . . . . . .

51

oparty na problemie pakowania plecaka . . . . . . . . . . . . .

53

5.3

Kryptosystem

6 Systemy z publicznym kluczem

56

6.1

Numeryczna funkcja jednokierunkowa . . . . . . . . . . . . . .

57

6.2

Funkcje skrótu

. . . . . . . . . . . . . . . . . . . . . . . . . .

58

6.3

poufno±¢ i autentyczno±¢. . . . . . . . . . . . . . . . . . . . . .

58

6.4

Wymiana kluczy

60

6.5

2-1 funkcje jednokierunkowe

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7 System RSA

60

62

7.1

Rozkªad liczb na czynniki

. . . . . . . . . . . . . . . . . . . .

62

7.2

Liczby wybrane losowo . . . . . . . . . . . . . . . . . . . . . .

63

7.3

Zasada dziaªania systemu RSA

. . . . . . . . . . . . . . . . .

64

7.4

Wpadka systemowa wspólny moduª . . . . . . . . . . . . . . .

65

7.5

Wpadka systemowa niski wykªadnik . . . . . . . . . . . . . . .

65

8 Teorio-liczbowe podstawy RSA

67

8.1

Systemy pozycyjne

. . . . . . . . . . . . . . . . . . . . . . . .

67

8.2

Iterowane podnoszenie do kwadratu . . . . . . . . . . . . . . .

69

8.3

Twierdzenie Eulera i Maªe Twierdzenie Fermata . . . . . . . . . . . . . . . . . . . .

69

8.4

liczby pseudo-pierwsze

71

8.5

Chi«skie twierdzenie o resztach

8.6

Kongruencje stopnia 2

8.7

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

74

. . . . . . . . . . . . . . . . . . . . . .

77

Gra w orªa i reszk¦ przez telefon . . . . . . . . . . . . . . . . .

80

9 Zastosowania arytmetyki modulo m do rozkªadu liczb

83

9.1

Wzory skróconego mno»enia . . . . . . . . . . . . . . . . . . .

9.2

Metoda

. . . . . . . . . . . . . . . . .

85

9.3

Metoda faktoryzacji Fermata . . . . . . . . . . . . . . . . . . .

87

9.4

Bazy rozkªadu . . . . . . . . . . . . . . . . . . . . . . . . . . .

88

ρ

rozkªadu na czynniki

3

83

10 Logarytm dyskretny

92

10.1 Poj¦cie logarytm dyskretny

. . . . . . . . . . . . . . . . . . .

92

10.2 System DiegoHellmana uzgadniania klucza

. . . . . . . . . . . . . . . . . . . . . . . .

10.3 System kryptograczny Masseya-Omury

93

. . . . . . . . . . . .

95

10.4 System ElGamala . . . . . . . . . . . . . . . . . . . . . . . . .

96

11 Protokoªy o zerowej wiedzy i przekazy nierozró»nialne 11.1 Kolorowanie mapy 11.2 Logarytm dyskretny

97

. . . . . . . . . . . . . . . . . . . . . . . .

97

. . . . . . . . . . . . . . . . . . . . . . .

99

11.3 Przekazy nierozró»nialne . . . . . . . . . . . . . . . . . . . . . 100 11.4 Dowód faktoryzacji . . . . . . . . . . . . . . . . . . . . . . . . 102

4

Rozdziaª 1 Kryptograa a steganograa Kryptograa jako dyscyplina matematyczna zajmuj¡ca si¦ metodami przesyªania wiadomo±ci w zakamuowanej formie tak, aby tylko adresat mógª odczyta¢ wiadomo±¢, rozwin¦ªa si¦ w drugiej poªowie dwudziestego wieku chocia» byªa ona stosowana znacznie wcze±niej. Do czasów drugiej wojny ±wiatowej szyfrów oczywi±cie u»ywano, jednak aparat matematyczny nie byª stosowany do ich tworzenia.

Prawdziwa bomba wybuchªa, kiedy u»ywane od

lat dwudziestych maszyny mechaniczne zostaªy zast¡pione przez komputery o du»ej mocy obliczeniowej. Wówczas okazaªo si¦, »e praktycznie ka»dy szyfr wynaleziony do tego czasu mo»e by¢ zªamany w stosunkowo krótkim czasie. Zaistniaªa potrzeba systemu szyfruj¡cego, który nie tylko chroniªby tajemnice wojskowe, ale przede wszystkim informacje bankowe ukryte w ogólnie dost¦pnej sieci komputerowej. Wiadomo przy tym, »e tego rodzaju system b¦dzie ,,atakowany od samego pocz¡tku. Z drugiej strony, na pocz¡tku lat siedemdziesi¡tych ujawniono w ko«cu, kto zªamaª tajemnic¦ niemieckiej ENIGMY. To zmusiªo wielu matematyków i informatyków do gª¦bszego zainteresowania si¦ ,,now¡ dziedzin¡ nauki, która stanowi najszersz¡ drog¦ od matematyki do informatyki. Kryptograa jednak»e jest nauk¡ si¦gajac¡ jeszcze czasów staro»ytnych.

W trakcie wy-

kªadu prze±ledzimy histori¦ tej nauki oraz wejdziemy w nowoczesne metody szyfrowania.

5

1.1

Steganograa

Jest wiele terminów okre±laj¡cych, z pozoru mogªoby si¦ wydawa¢, t¦ sam¡ rzecz: kryptograa, kryptologia, kodowanie, steganograa, szyfrowanie itd. Jednak»e dla osób dogª¦bnie studiuj¡cych temat, ró»nice mi¦dzy tymi poj¦ciami staj¡ si¦ wyra¹ne. Steganograa, na przykªad zajmuje si¦ kamuowaniem tekstu w dosªownym tego sªowa znaczeniu. Zakamuowanie (zakrycie) i odkrycie tekstu nie wymagaj¡ skomplikowanych algorytmów, tylko pewnej zasady logicznej, szablonu, b¡d¹ odczynników chemicznych.

Opiszemy tu

najpopularniejsze metody steganografów. Jedn¡ z metod jest u»ywanie w tek±cie dwóch charakterów pisania poszczególnych liter.

Litery napisane inaczej utworz¡ ukryty tekst.

Innym

sposobem jest robienie maªej przerwy tu» przed liter¡, któr¡ chcieliby±my »eby adresat przeczytaª. Zamiast pisa¢ dªugi i nic nie znacz¡cy tekst mo»na wykorzysta¢ tekst ju» napisany (np. gazet¦ lub ksi¡»k¦) i zaznaczy¢ potrzebne litery tak, aby nikt niepowoªany nie domy±liª si¦, ze co± jest zaznaczone:

to

S

jest mi znów potrzebne. Kochany Tato czwartek. Ryby w tym jeziorze s¡ wyj¡tkowo nieu-

dwadzie±cia zªotych

przy±lij mi je w chwytne.

S t o dwadzie±cia zªotych j e s t mi znów potrze bne. Kochan y Ta t o przy±lij mi je w c zwartek.

R yby w tym jez iorze s¡ wyj¡ tkowo

ni euchwytne. Inn¡ metod¡ jest wskazanie ci¡gu liczb pokazuj¡cych pozycj¦ danej litery b¡d¹ w alfabecie, b¡d¹ te» w jakiej± ksi¡»ce. Na przykªad posªuguj¡c si¦ ksi¡»k¡ Neal'a Koblitza ,,Wykªad z teorii liczb i kryptograi mo»emy zaszyfrowa¢ sªowo ,,mama ci¡giem liczb 21 26 31 2. Ci¡g ten rozszyfrowujemy licz¡c litery od okre±lonego miejsca w ksi¡»ce. W naszym przypadku jest to pocz¡tek tekstu ,,Wst¦pu. By wskaza¢ po»¡dany ci¡g liczb mo»emy posªu»y¢ si¦ cho¢by pudeªkiem domina przesªanym w paczce. Aby ukry¢ wiadomo±¢ mo»na te» si¦ posªu»y¢ rebusem, lub te» labiryntem z literami w korytarzach. Prawidªowe przej±cie takiego labiryntu ujawni nam ukryty tekst. Podobnie, wiadomo±¢ mo»emy schowa¢ w obrazek z dziwnymi detalami, który staje si¦ czytelny, gdy w odpowiedniej od niego odlegªo±ci mrugniemy oczami i zobaczymy trójwymiarowy rysunek. Obraz, jako taki, te» mo»e posªu»y¢ steganografowi do ukrycia wiadomo±ci. Na przykªad pewne detale (¹d¹bªa traw lub tym podobne) mog¡ ukªada¢ si¦ w kod Morse'a. Ciekaw¡ grup¡ metod steganogracznych jest zamiana ukrywanej wiado-

6

mo±ci w ªatwo, ale na pewno ¹le zrozumian¡ wiadomo±¢ brzmi¡c¡ caªkiem nieszkodliwie. Mo»na rozró»ni¢ tu dwie kategorie: maskowanie i zasªanianie. Maskowanie wymaga najpierw zgody obu stron co do przekazywanego kodu. Cz¦sto stosuj¡ to bryd»y±ci, którzy trzymaj¡c odpowiednio papierosa lub robi¡c szereg niewinnych czynno±ci, w istocie przekazuj¡ sobie informacje. Mistrzami w przekazywaniu zamaskowanych informacji s¡ te» wi¦¹niowie, którzy tworz¡ swój swoisty »argon. niektóre sªowa w tym »argonie to dziura, paka  wi¦zienie; ±nieg, cukier  kokaina; obczyszczenie  kradzie» itp. W czasie drugiej wojny ±wiatowej, Amerykanie zatrudnili radiooperatorów, którzy rozmawiali w swoim ojczystym j¦zyku  Nawaho. Japo«czycy nie mogli przechwyci¢ i zidentykowa¢ »adnej z wysyªanych wiadomo±ci. Bardzo dobry (jak na tamte czasy) niemiecki szyfr ENIGMA zostaª, jak wiadomo, zªamany. Mówi¡c o maskowaniu, trudno jest tu nie wspomnie¢ o audycjach radia BBC w 1944 roku, gdzie w±ród tzw, prywatnych wiadomo±ci zapodziaªo si¦ hasªo ,,dªugie struny jesiennych skrzypiec, a jaki± czas pó¹niej ,,rani¡ me serce monotonnym brzmieniem. Oznaczaªo to dokªadn¡ dat¦ i miejsce inwazji na Francj¦.

Niemiecka Abwehra Admiraªa Canarisa rozszyfrowaªa

dokªadnie t¦ wiadomo±¢, która dotarªa do wszystkich niemieckich jednostek z wyj¡tkiem stacjonuj¡cej w Normandii VII armii. Do dzi± nie wyja±niono w peªni, dlaczego armia ta nie zostaªa ostrze»ona. Wspomnie¢ mo»emy tak»e o audycjach Polskiego Radia, nadaj¡cych sªynne ,,Uwaga, uwaga, nadchodzi, KO-MA 27.

Tak»e Japo«czycy, »eby przekaza¢ swoim statkom wia-

domo±¢ o wojnie z USA u»yli sªów ,,higaszi no kaze ame (wschodni wiatr, deszcz). Sªowa te zostaªy wplecione w prognoz¦ pogody i powtórzone dwukrotnie. Z maskowaniem sªów za pomoc¡ zjawisk meteorologicznych trzeba jednak mocno uwa»a¢, o czym przekonaªa si¦ Miss Holly Golightly w lmie ,,‘niadanie u Tianiego. Przekazana przez ni¡ ,,wiadomo±¢ o pogodzie, która brzmiaªa ,,±nieg w Nowym Orleanie byªa mocno podejrzana i stró»owie prawa skojarzyli to sobie z handlem kokain¡. Zasada zasªaniania tekstu najcz¦±ciej jest typu ,,czytaj okre±lonym znaku.

nt¡

liter¦ po

Mo»e to by¢ spacja, pocz¡tek nowej linii tekstu lub

samogªoska. Zasªanianie stosowali powszechnie »oªnierze, którzy chcieli przekaza¢ miejsce swego pobytu rodzinie, ale nie mogli tego zrobi¢ w ocjalny sposób.

Dla jednego z nich nie sko«czyªo si¦ to dobrze, poniewa» rodzice

w li±cie powrotnym spytali go: ,,Gdzie jest to Nutsi? Nie mo»emy znale¹¢ tego w »adnym atlasie!.

Równie» Kornel Makuszy«ski w ksi¡»ce ,,Szatan

z siódmej klasy u»yª ten rodzaj zasªaniania. Bohater ksi¡»ki tak sprytnie

7

napisaª list, »e jego przyjaciele bez wi¦kszego trudu rozszyfrowali wiadomo±¢, któr¡ chciaª przekaza¢:

Serdecznie ukochany panie profesorze! Trzeba byªo takiego jak ja wariata, aby nie znaj¡c okolicy ruszy¢ na dalek¡ w¦drówk¦. Takim jednak szcz¦±cie sprzyja. Ziemie okoliczne s¡ bardzo pi¦kne, lecz Ejgoªa pi¦kniejsza. ›al mi jedynie, »e pana tu ze mn¡ nie ma. Caªy jestem i zdrów. Znalazªem miªe towarzystwo i dlatego nie wiem dobrze, kiedy wreszcie powróc¦ do Ejgoªy. B¡d¹cie jednak»e o mnie spokojni, cho¢bym nawet dªugo nie powracaª. Ogromnie mi t¦skno za panem, panie profesorze, za pani¡ Mari¡ i pann¡ Wandeczk¡. ‘ciskam wszystkich i ª¡cz¦ ukªony dla caªego domu. Wdzi¦czny Ada±. Inny sposób zasªaniania wymaga szablonu, którym zasªania si¦ napisany tekst. W okienkach szablonu odczytujemy nasz¡ ukryt¡ wiadomo±¢. Metoda ta wymaga jednak doskonaªego wyczucia miejsca  umiej¦tno±ci dopasowania tekstu tak, aby odpowiedni wyraz znalazª si¦ w wyznaczonym szablonem miejscu.

1.2

Szyfry przestawieniowe

Szyfry przestawieniowe (lub anagramowe) s¡ tak»e rodzajami steganogramów, mimo »e okre±la si¦ je mianem ,,szyfry. Dokªadnie, »eby zaszyfrowa¢ pewien tekst, przestawiamy jego litery wedªug okre±lonej zasady.

Przyto-

czymy tu dwa przykªady szyfrów przestawieniowych.

Szyfr pªotowy.

Ukªadamy litery tekstu ,,wzdªó» pªotu, tj.

wzdªó»

ªamanej zªo»onej ze sko±nych odcinków. Wysoko±¢ pªotu jest okre±lona liczb¡ liter przypadaj¡c¡ na jeden odcinek ªamanej. Nast¦pnie tekst zaszyfrowany odczytujemy wierszami. Na przykªad, chc¡c zaszyfrowa¢ tekst

‘MIERCI

pªotem o wysoko±ci 3, zapisujemy

I

G N

Y S

R

‘

N

A I

M

E I

8

C I

INSYGNIA

ig±rnynamecsiii.

i przepisujemy

Generalnie, przy szyfrowaniu obowi¡zuje

zasada, »e w tek±cie zaszyfrowanym nie ma znaków interpunkcyjnych ani spacji.

Mo»e to prowadzi¢ do nieporozumie«, ale zasada ta utrudnia te»

ewentualne ªamanie szyfru.

Przy pªocie wysoko±ci 5, zaszyfrowany tekst

kªsókipr¡ew»i, to KSI›E PӊKRWI. Szyfr kwadratowy. Tekst, który chcemy zaszyfrowa¢ wpisujemy w kwadrat (lub kilka takich samych kwadratów) wierszami, a jako szyfr odczytujemy kolumnami, i to wedªug pewnej permutacji. kwadratu

4×4

(12)(34)

z permutacj¡

Na przykªad, u»yjemy

i zaszyfrujemy tekst

KOMNATA TA-

JEMNIC. Poniewa» tekst ten ma mniej ni» 16 liter, na jego ko«cu dopisujemy dowolne litery (tzw. nulle) i wpisujemy tekst w kwadrat

K O M N A T A T A J E M N I C X Odczytuj¡c kolumy wg kolejno±ci

mxmaec.

2 − 1 − 4 − 3,

otrzymujemy

otjikaannt-

Istotn¡ wskazówk¡ identykuj¡c¡ szyfr kwadratowy jest fakt, »e

liczba liter w tek±cie zaszyfrowanym jest wielokrotno±ci¡ kwadratu liczby naturalnej

n.

Sama liczba

aeim«lkifzinocyofz

n

oznacza dªugo±¢ boku kwadratu.

Np.

tekst

ma 18 liter, co mo»e oznacza¢, »e zostaª u»yty szyfr kwa-

dratowy z kwadratem o boku 3, a do zaszyfrowania u»yto dwóch kwadratów.

1.3

Systemy kryptograczne

Podstawowym elementem, który odró»nia steganogra¦ od kryptograi jest

system kryptograczny.

Jest to poj¦cie które w przypadku metod kryptogra-

cznych mo»na w miar¦ ªatwo zdeniowa¢. Na pocz¡tek zdeniujmy kilka podstawowych elementów. Aby jednak wiadomo±¢ mogªa by¢ wysªana, najpierw trzeba j¡ w jaki± sposób napisa¢. W tym celu u»ywamy alfabetu, który deniujemy jako dowolny zbiór sko«czony. Liczb¦ elementów zbioru cza¢ przez

|A|, #A

lub

A.

A (alfabetu) b¦dziemy ozna-

Do zapisywania wiadomo±ci b¦dziemy u»ywa¢

alfabetu ªaci«skiego

A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z,

9

który uto»samimy z liczbami 0, 1, 2,

...,

25. B¦dziemy te» rozwa»a¢ inne

alfabety, którym w podobny sposób odpowiada¢ b¦d¡ liczby ze zbioru wszystkich liczb caªkowitych nieujemnych i mniejszych od

q.

Zq

Zbiór ten ma

t¦ zalet¦, »e jego elementy mo»na dodawa¢, odejmowa¢ i mno»y¢ zgodnie z zasadami arytmetyki modulo

q.

Litery alfabetu mo»na ukªada¢ w bloki liter. Blok dwuliterowy nazywamy digramem, trzyliterowy trigramem i, ogólnie, blok

nliterowy

nazywamy n An zbiór

gramem. Litery i bloki liter ukªadaj¡ si¦ w tekst. Oznaczmy przez wszystkich

ngramów

z alfabetu

A.

Tekstem nazywamy dowolny element

zbioru

A∗ =

[

An .

n≥0 Generalnie, szyfrujemy tylko wiadomo±ci, które co± oznaczaj¡, wi¦c nie mog¡ to by¢ przypadkowe ci¡gi liter. Koniecznym zatem jest zdeniowanie ∗ poj¦cia j¦zyka. J¦zykiem nazywamy dowolny podzbiór zbioru A . Zaªó»my wi¦c, »e mamy wybrany konkretny j¦zyk oraz pewien tekst w tym j¦zyku. Tekst ów nazywamy jawnym lub otwartym. Alfabet

jawnym.

jest on napisany tak»e nazywamy

A, w którym

Aby przesªa¢ tekst, szyfrujemy

go. Mo»emy w tym celu u»y¢ jednego alfabetu szyfrowego

B

(szyfry monoal-

fabetyczne), lub te» wielu alfabetów szyfrowych (szyfry polialfabetyczne). W tym drugim przypadku, u»ywa si¦ raczej wielu kopii tego samego alfabetu. Zawsze jednak potrzebne nam jest przeksztaªcenie szyfruj¡ce, czyli funkcja ró»nowarto±ciowa jawnym, to

E(m)

E okre±lona w A∗ o warto±ciach w B∗.

Je±li

m jest tekstem

nazywamy kryptotekstem, lub szyfrem.

W dalszej cz¦±ci wykªadu b¦dziemy u»ywa¢ synonimów wymienionych wy»ej poj¦¢, które oznacza¢ b¦d¡ to samo, je±li nie zostanie podana inna denicja. Na przykªad, sªowo ,,tekst b¦dziemy stosowa¢ zamiennie ze sªowem ,,wiadomo±¢. Istnieje wiele mo»liwo±ci zdeniowania przeksztaªcenia jest zada¢ bijekcj¦ mentów co

A,

e : A → B.

Poniewa»

B

E.

Najpro±ciej

ma wówczas tyle samo ele-

A = B . Przeksztaªcenie e generuje E m = l1 l2 . . . lq jest wiadomo±ci¡, to E(m) = podobny sposób generujemy E z funkcji ró»nowarto-

wi¦c przyjmujemy, »e

w nastepuj¡cy sposób.

Je»eli

e(l1 )e(l2 ) . . . e(lq ). W n m ±ciowej e : A → B .

W tym wypadku, liczba liter w szyfrowanej wiado-

mo±ci musi by¢ podzielna przez

n.

Je±li tak nie jest, nale»y dopisa¢ do tej

wiadomo±ci odpowiedni¡ ilo±¢ liter. Zdeniujemy teraz poj¦cie kryptosystemu. Kryptosystemem nazywamy

10

rodzin¦ przeksztaªce« szyfruj¡cych

{Ek : k ∈ K}, gdzie K

jest pewnym zbio-

rem (sko«czonym lub nie) zwanym przestrzeni¡ kluczy. Dowolny element

k

przestrzeni kluczy nazywamy kluczem.

k odwzorowanie Ek jest ró»nowarto±ciowe, istnieje Dk , które nazywamy deszyfrowaniem. Je±li m jest dla dowolnego klucza k ,

Skoro dla dowolnego odwzorowanie odwrotne wiadomo±ci¡ jawn¡, to

Dk (Ek (m)) = m. Nie musi jednak zachodzi¢

Ek (Dk (m)) = m.

11

Rozdziaª 2 Klasyczne metody szyfrowania Korzenie kryptograi si¦gaj¡ czasów staro»ytnego Rzymu. Tam wªa±nie powstaª i byª u»ywany pierwszy system kryptograczny. zwanego te» klasycznych.

szyfrem Cezara

lub

cyklicznym

Od tego systemu,

zaczniemy nasz przegl¡d metod

Nast¦pnie rozwa»ymy budow¦ innych, bardziej skomplikowa-

nych systemów, które byªy u»ywane w historii lub te» byªy stworzone do innych celów ni» ochrona tajemnic.

2.1

Szyfry cykliczne

Zostaªy wynalezione, a na pewno u»ywane przez Juliusza Cezara. Maj¡ one bardzo ªatwy klucz, ale jednocze±nie s¡ ªatwe do zªamania. Oznaczmy przez jest

N.

p

jednostk¦ tekstu jawnego i zaªó»my »e tych jednostek

Wtedy funkcja szyfruj¡ca

Ek

jest okre±lona wzorem

Ek (p) = p + k(mod N ). Kluczem jest tu liczba Je±li

k

k,

a przestrze« kluczy pokrywa si¦ z alfabetem

ZN .

jest równe 3, to aby zaszyfrowa¢ sªowo TAK, przeksztaªcamy je w

ci¡g 19 0 12, nast¦pnie dodajemy do ka»dej z tych liczb 3 modulo 26 otrzymuj¡c 24 3 15 i z powrotem przeksztaªcamy liczby na litery by otrzyma¢

wdn.

Przeksztaªcenie szyfruj¡ce okre±lone powy»ej nazywamy przesuni¦ciem.

Wygodnie jest tutaj napisa¢ alfabet, a pod nim liczby odpowiadaj¡ce poszczególnym literom. A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 12

W celu odszyfrowania wiadomo±ci

tgyfz kqyz, zaszyfrowanej kluczem 6,

zamieniamy j¡ najpierw w ci¡g liczb 19 6 24 5 25 10 16 24 25. Tym razem, pd ka»dej z liczb odejmujemy 6 (modulo 26) i otrzymujemy 13 0 18 25 19 4 10 18 19.

W nast¦pnym kroku patrzymy jakie litery s¡ na pozycjach z

ostatniego ci¡gu i otrzymujemy wiadomo±¢ jawn¡ NASZ TEKST. Jest ogólnie przyj¦te, »e tekst zaszyfrowany podajemy w blokach pi¦cio literowych. Uªatwia to przekazywanie tekstu i zmniejsza ryzyko pomyªki przy wysyªaniu i deszyfrowaniu. Zajmiemy si¦ teraz ªamaniem szyfrów cyklicznych. Je±li wiemy na pewno, »e mamy do czynienia z szyfrem cyklicznym i znamy ilo±¢ liter w alfabecie, czyli

N,

ka»d¡ z

ªamanie polega na znalezieniu liczby

N

k.

Za

k

wystarczy podstawi¢

mo»liwo±ci i sprawdza¢ po kolei sens otrzymanych w ten sposób

wiadomo±ci. Na przykªad, przypu±¢my, »e chcemy zªama¢ szyfr Wiemy przy tym, »e

N = 26.

Sprawdzamy po kolei wszystkie mo»liwe klucze.

Zauwa»amy przy tym, »e odejmowanie liczby dodawanie liczby

xolfd vhcdp nrzd.

26−k modulo 26.

k modulo 26 jest tym samym, co

Dodajemy wi¦c do liczb odpowiadaj¡cych

literom szyfru, tj. 23 14 11 5 3 21 7 2 3 15 13 17 25 3, kolejno

2, . . . , k = 25.

kilka pierwszych liter. Przy Podobnie dla

k = 1, k =

Cz¦sto, aby wyeliminowa¢ przypadek wystarczy wypróbowa¢

k = 2.

k = 1 mamy pocz¡tek YPM, co jest nieczytalne.

Tym razem mamy ZQ. Szcz¦±cie u±miecha si¦ do nas

dosy¢ pó¹no, bo dopiero dla

k = 23.

Otrzymujemy wówczas ci¡g 20 11 8

2 0 18 4 25 0 12 10 14 22 0, co daje fraz¦ ULICA SEZAMKOWA. Ten sposób ªamania szyfrów nazywa si¦

przestrzeni kluczy.

metod¡ brutalnej siªy,

lub

wyczerpania

Juliusz Cezar u»ywaª klucza 3, ale i tak dowódcy legionów raczej domy±lali si¦ tre±ci przysªanych wiadomo±ci ni» je odszyfrowywali. Jego nast¦pca, Oktawian August u»ywaª klucza 2, nast¦pnie 1, a potem w ogóle zrezygnowaª z szyfrowania wiadomo±ci.

2.2

Monoalfabetyczny szyfr Beauforta

W zasadzie szyfr ten, wynaleziony przez G. Sestri w 1710 roku, jest cz¦±ci¡ bardziej skomplikowanej techniki szyfrowania. Tutaj przedstawimy tylko podstawowy krok tej techniki, który mo»e istnie¢ jako samodzielny system szyfruj¡cy. Podobnie jak w przypadku szyfrów Cezara, przestrzeni¡ kluczy jest

13

ZN ,

ale przeksztaªcenie szyfruj¡ce jest dane wzorem

Ek (p) = −p + k(mod N ). Zauwa»my, »e przeksztaªcenie deszyfruj¡ce ma tak¡ sam¡ posta¢. Zatem szyfrowanie i deszyfrowanie odbywa si¦ za pomoc¡ tego samego przeksztaªcenia. Zauwa»my te», »e w przeciwie«stwie do kryptosystemu Cezara, gdzie identyczno±ci¡, w kryptosystemie Beauforta, »adnego

Ek

E0

byªo

nie jest identyczno±ci¡ dla

k.

Ze wzgl¦du na maª¡ liczb¦ kluczy, równie» i ten szyfr mo»na ªama¢ przez wyczerpanie przestrzeni kluczy. Podamy jeszcze alfabet jawny i szyfrowy dla klucza 3. Zauwa»my, »e kolejno±¢ liter w alfabecie szyfrowym jest odwrócona. A B C D E F G H I J K L M N O P Q R S T U V W X Y Z D C B A Z Y X W V U T S R Q P O N M L K J I H G F E

2.3

Kody aniczne jednowymiarowe

Je»eli zamiast jednej liczby jeste±my w stanie zapami¦ta¢ dwie, to mo»emy stosowa¢ nieco bardziej skomplikowany kod aniczny, gdzie przeksztaªcenie szyfruj¡ce ma posta¢

E(p) = ap + b (mod N ).

Naszym kluczem jest tu pa-

ra (a, b). ›eby rozszyfrowa¢ wiadomo±¢ u»ywamy innego klucza. Dokªadnie, D(c) = a0 c + b0 ( mod N ), gdzie a0 jest liczb¡ odwrotn¡ do a modulo N , a b0 = −a0 b w ZN . Musimy tu uwa»a¢, czy NWD(a, N ) jest równy 1, gdy» w przeciwnym wypadku nasz szyfr nie b¦dzie jednoznaczny. Kiedy a = 1, kod aniczny staje si¦ kodem cyklicznym. Gdy b = 0, kod aniczny nazywamy szyfrem liniowym.

W przypadku alfabetu 26-literowego, przestrze« kluczy

12 · 26)

elementów. Nie jest to du»a liczba z kyptoanalitycznego

ma 312 (=

punktu widzenia, ale rozwa»enie takiej liczby przypadków mo»e stworzy¢ pewne trudno±ci.

Zademostrujemy metod¦, która ogranicza istotnie liczb¦

rozwa»anych przypadków.

2.1 Przykªad.

szyfrze tym najcz¦stsz¡ liter¡

g

vqtmx ozdtg hgjqm aqhcx bgkgt ag. W jest g, a nast¦pn¡ jest q. Podejrzewamy, »e a (pozycja 0), natomiast q (pozycja 16), to e

Zªamiemy szyfr

(pozycja 6) to zaszyfrowane

(pozycja 4). Mamy wi¦c

6a0 +b0 ≡0( mod 26) 16a0 +b0 ≡4( mod 26) 14

Odejmuj¡c obie kongruencje stronami otrzymujemy 0 0 st¡d natychmiast a = 3. Chwil¦ potem mamy b =

10a0 ≡ 4 (mod 26), a 8 i mamy klucz deszy-

fruj¡cy. Zastosowanie tego klucza daje nam tekst jawny

do zªamania.

2.4

Ten szyfr nadaje si¦

Permutacje alfabetu

Znacznie trudniejsze od szyfrów cyklicznych oraz anicznych s¡ szyfry, w których ka»da litera alfabetu jawnego jest zast¡piona liter¡ alfabetu szyfrowego bez stosowania okre±lonego algorytmu arytmetycznego.

Zatem przestrze«

kluczy jest równa zbiorowi wszystkich permutacji alfabetu. W celu uªatwienia zapami¦tania przeksztaªcenia szyfruj¡cego stosujemy tu innego rodzaju klucz. Jest to sªowo, którego litery zast¦puj¡ pocz¡tkowe litery alfabetu jawnego.

Dalsze litery dopisujemy tak jak wyst¦puj¡ one w alfabecie jawnym

przy czym pomijamy ju» wykorzystane znaki.

Na przykªad stosuj¡c klucz

,,szyfrowanie dostajemy nast¦puj¡ce przeksztaªcenie szyfruj¡ce:

a b c d e f

g h i j k l m n o p q r s t u v w x y z

S Z Y F R O W A N I E B C D G H J K L M P Q T U V X

Opisany powy»ej kryptosystem nazywamy permutacyjnym. Jego odmian¡ jest stosowany w pierwszych maszynach szyfruj¡cych kryptosystem transpozycyjny, tj. taki, którego przestrze« kluczy jest równa zbiorowi wszystkich permutacji, które mo»na zapisa¢ w postaci iloczynu rozª¡cznych transpozycji. Przykªadem tu jest nast¦puj¡ce przeksztaªcenie szyfruj¡ce:

a b c d e f

g h i j k

l m n o p q r s t u v w x y z

Z C B F R D W K N J H M L I O P T E Y Q X V G U S A

Poniewa» szyfry tego rodzaju byªy zaprogramowane w maszynach jako metody standardowe, nikt nie musiaª pami¦ta¢ klucza. Zalet¡ szyfrów transpozycyjnych jest fakt, »e klucze szyfruj¡cy i rozszyfrowuj¡cy s¡ identyczne. Zatem ta sama maszyna sªu»yªa zarówno do szyfrowania jak i do rozszyfrowywania wiadomo±ci.

15

2.5

Analiza cz¦sto±ci wyst¦powania liter

Ta metoda ªamania szyfrów opiera si¦ na prawach rachunku prawdopodobie«stwa. Wiadomo, »e pewne litery wyst¦puj¡ w tek±cie cz¦±ciej ni» inne. Oto alfabet angielski poukªadany wedªug cz¦sto±ci wyst¦powania liter: E  12.5%, T, A, O, I, N  9.2-7%, S, R  6%, L, D 4%, C, U, M, F, P, G, W, Y, B  3-1.5%, V, K, X, J, Q, Z  1-0.1%, Je»eli wi¦c przechwycimy wiadomo±¢ na tyle dªug¡ (lub na tyle du»o wiadomo±ci), aby wyeliminowa¢ przypadkowo±¢, mo»emy przypuszcza¢, »e najcz¦±ciej powtarzaj¡ca si¦ litera to zakodowane E, T, A, O, I lub N. Je»eli mamy do czynienia z kodem cyklicznym, nasze sprawdzanie mo»liwo±ci dla

b

ogranicza si¦ do sze±ciu przypadków. Okazuje si¦, »e na podstawie badania entropii j¦zyka, czyli ilo±ci informacji zawartej w jednym symbolu zaszyfrowanego tekstu, mo»na zªama¢ ka»dy szyfr, który szyfruje tekst angielski maj¡cy wi¦cej ni» 25 liter. Oczywi±cie metoda ta nie dziaªa, je±li przechwytywane wiadomo±ci s¡ krótkie (maj¡ mniej ni» 25 liter) i klucz cz¦sto si¦ zmienia. je±li przechwycimy tylko

xolfd vhcdpnrzd.

Na przykªad,

jak w rozwa»anym wy»ej szyfrze

cyklicznym, to nie wida¢ tu, która litera pojawia si¦ najcz¦±ciej. Z drugiej strony jednak, jak si¦ okazuje, klucze s¡ bardzo niech¦tnie zmieniane. Rz¡d Stanów Zjednoczonych nie zdecydowaª si¦ na zmian¦ kluczy nawet po tym, jak wszystkie zgin¦ªy w tajemniczej kradzie»y w Zagrzebiu na pocz¡tku drugiej wojny ±wiatowej. Kiedy ju» wiemy, które litery pojawiaj¡ si¦ najcz¦±ciej, zwracamy uwag¦ na powtarzaj¡ce si¦ pary.

Na przykªad EA jest najcz¦±ciej pojawiaj¡cym

si¦ digramem samogªosek. Dosy¢ cz¦sty jest te» digram IO. Natomiast OI, IA, AI, OA i AO s¡ ju» znacznie rzadsze. Digram AE nie pojawia si¦ prawie nigdy. Ogólnie, dziesi¦¢ najcz¦stszych digramów w j¦zyku angielskim, to TH, HE, AN, IN, ER, RE, ON, ES, TI oraz AT. Dla przykªadu spróbujmy rozszyfrowa¢ nast¦puj¡cy tekst

wktqr lwktq fqatr yggrg ltqut

ziqzd rziqz kqveq fsnzg ksnqv

xlzwt olzgg kkgzl ziglt qozof

lsoet fgxko qktqe vigso utqlz

rvozi liofu ethzq cto tk

qfqbo sqkut wstql xzeit

Aby uªatwi¢ nieco ªamanie, przypu±¢my »e wiemy ju», i» najcz¦±ciej pojawiaj¡c¡ si¦ w tek±cie jawnym liter¡ nie jest

16

e.

Z analizy cz¦sto±ci wynika, »e najcz¦stszymi literami w zaszyfrowanym tek±cie s¡

q, t, z, g, k, l, o, i i f.

q t z g k l o i f

Tworzymy teraz tak zwan¡ tabel¦ kontaktów:

q

t

z g k

l

o i

f

0

0

2

0

3

2

1

0

1

6

0

0

0

2

2

1

0

1

2

1

0

2

0

1

2

4

0

0

0

2

2

0

1

0

0

2

1

3

0

1

1

0

1

0

0

1

2

3

0

0

0

0

1

0

0

0

2

0

0

3

0

0

3

3

1

0

1

0

0

1

0

0

2

0

0

1

0

0

0

1

0

Podaje ona jak cz¦sto w zaszyfrowanym tek±cie wyst¦puj¡ digramy zªo»one z najcz¦±ciej wyst¦puj¡cych liter. Na przykªad digram (szukamy w tabeli miejsca, gdzie krzy»uje si¦ wiersz Wiemy, »e

q

k

kq

wyst¦puje 3 razy

z kolumn¡

q.

nie jest zaszyfrowanym E. Zgadujemy zatem, »e to

powiada E. Poniewa» mamy 6 par

tq,

a

t

ma by¢ E, wi¦c

q

t

od-

odpowiada

zapewne A. Trzeci¡ liter¡ z kolei jest Z. Poniewa» T jest jeszcze ,,wolne, przyporz¡dkujmy

z → T.

Poniewa»

nie pojawia, przypuszczamy, »e

zi

i → H.

pojawia si¦ 4 razy, a

iz

w ogóle si¦

Na koniec zauwa»amy jeszcze, »e

pojawia si¦ dwa razy. Dobrze jest wi¦c postawi¢, »e

g

gg

to O. Podstawiamy

teraz odgadni¦te litery do naszego kryptogramu i odgadujemy reszt¦ liter na zasadzie ,,co pasuje.

Tekstem jawnym jest wi¦c:

BREAD THAT MUST

BE SLICED WITH AN AX IS A BREAD THAT IS TOO NOURISHING LARGE NAKED CARROTS ARE ACCEPTABLE AS FOOD ONLY TO THOSE WHO LIVE IN HUTCHES EAGERLY AWAITING EASTER.

2.6

Homofony i nulle

kiedy przekonano si¦, »e analiza cz¦sto±ci wyst¦powania liter jest pot¦»n¡ broni¡, zacz¦to si¦ zastanawia¢, jak utrudni¢ t¦ analiz¦. Nasuwaj¡ si¦ tutaj dwie dosy¢ oczywiste metody. Jedn¡ z nich jest ,,dokªadanie liter, a drug¡ zmniejszanie ilo±ci najcz¦±ciej powtarzaj¡cych si¦ znaków.

17

Prowadzi to do

dwóch denicji.

Nullem nazywamy jednostk¦ tekstu zaszyfrowanego, któ-

rej nie odpowiada »adna jednostka tekstu jawnego. Oczywi±cie, nasze przeksztaªcenie szyfruj¡ce musi by¢ w dalszym ci¡gu wzajemnie jednoznaczne. Zatem, w praktyce, do alfabetu jawnego dorzucamy ,,znak pusty, któremu odpowiada pewien znak w alfabecie zaszyfrowanym. Na przykªad

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z s z y f r o w a n i e 3 c d g h j k 4 m p q

W powy»szym szyfrze, wyst¦puj¡ dwa nulle:

b i l.

t

∅ ∅0

u v x b l

Wtajemniczeni wiedz¡, »e

po otrzymaniu zaszyfrowanej wiadomo±ci, nale»y te dwa znaki zignorowa¢. Na przykªad zaszyfrowane wiadomo±ci

esmsbhp13m1s

oraz

e1sbmsh1pb3ms

oznaczaj¡ to samo, a mianowicie wiadomo±¢ KATAPULTA. Druga denicja jest nast¦puj¡ca: homofonem nazywamy jednostk¦ tekstu jawnego, której odpowiada wi¦cej ni» jedna jednostka tekstu zaszyfrowanego. I tym razem mamy problemy z wieloznaczno±ci¡ funkcji szyfruj¡cej. Problem ten pokonujemy powtarzaj¡c elementy w alfabecie jawnym. A oto przykªad

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A A T s z y f r o w a n i e 3 c d g h j k 4 m p q

t

u v x b 5 l

Trzy homofony powy»szego alfabetu to A, A i T. Dzi¦ki nim wiadomo±¢ KATAPULTA mo»emy zaszyfrowa¢ tak, »e »adna litera alfabetu zaszyfrowanego nie powtarza si¦:

esm5hp31b.

Przy ukªadaniu przeksztaªcenia szyfruj¡cego mo»emy stosowa¢ zarówno nulle jak i homofony. Šamanie szyfru jest wtedy jeszcze bardziej utrudnione. Oprócz tych dwóch utrudnie« stosowane s¡ te» i inne bardziej skomplikowane. Niektóre z nich opiszemy poni»ej.

2.7

Jednostki dwuliterowe czyli digramy

Digramy jako alfabet po raz pierwszy zastosowaª niejaki Giovanni Battista Porta w 1563 roku. Alfabet taki skªadaª si¦ z czterystu digramów i do ka»dego z nich Porta z niebywaª¡ inwencj¡ dobraª pewien szczególny znak. Ogólnie, stosuj¡c digramy jako jednostki tekstu jawnego, mamy alfabet 2 zªo»ony z N liter. Jego symbole zast¦pujemy b¡d¹ pojedynczymi znakami,

18

Rysunek 2.1: Tablica Porty

jak to zrobiª Porta, b¡d¹ te» (innymi) digramami.

Nasze przeksztaªcenie

szyfruj¡ce przedstawiamy w postaci tabeli, jak na przykªad w tabeli Porty. Dokªadnie, je±li 2 cja E∗k : A →

A jest alfabetem, to przeksztaªceniem bazowym jest bijekA2 . W szczególno±ci liczba liter w tek±cie jawnym m musi

by¢ parzysta. Przestrzeni¡ kluczy jest tu oczywi±cie zbiór wszystkich permu2 ∗ tacji zbioru A . Przeksztaªcenie szyfruj¡ce Ek jest generowane przez Ek w naturalny sposób, tj. Je±li

m = m1 m2 . . . mp ,

gdzie

mi

s¡ digramami, to

Ek (m) = Ek∗ (m2 )Ek∗ (m2 ) . . . Ek∗ (mp ). Powy»sze przeksztaªcenie nazywamy

2-dzielnym.

Aby zªama¢ kod digramowy mo»emy stosowa¢ analiz¦ cz¦sto±ci wyst¦powania jednostek dwuliterowych. Aby metoda ta si¦ powiodªa, przechwycony tekst musi by¢ bardzo dªugi. Je»eli dla tekstu o jednostkach jednoliterowych potrzebowali±my N znaków, aby ªamanie si¦ powiodªo, to teraz potrzebujemy 2 okoªo N znaków. Dla j¦zyka angielskiego jest to ju» ponad 525 liter.

19

Gªówn¡ przeszkod¡ przy stosowaniu szyfrów dwudzielnych jest brak efektywnego algorytmu szyfruj¡cego i deszyfruj¡cego. Próby uproszczenia ogólnej zasady doprowadziªy do powstania szyfrów opartych na kwadracie oraz na macierzach. Szyfry oparte na kwadracie omówimy w nast¦pnych trzech podrozdziaªach.

2.8

Szyfr Playfaira

Problem zapami¦tania du»ej ilo±ci znaków doprowadziª w 1854 roku niejakiego Charlesa Wheatstone'a do wynalezienia prostej metody zast¦powania jednego bloku liter drugim. Litery alfabetu umieszczone s¡ w kwadracie

5×5,

a blok liter tekstu jawnego tworzy w tym kwadracie przek¡tn¡ prostok¡ta. Blok dwuliterowy odczytany z drugiej przek¡tnej jest odpowiadaj¡cym blokiem kryptotekstu. Je±li litery znajduj¡ si¦ w tym samym wierszu lub w tej samej kolumnie, szyfrowanie jest nieco trudniejsze. Ogólnie po krótkiej praktyce, ªatwo jest posªugiwa¢ si¦ opisanym szyfrem. Szyfr ten nazwany szyfrem Playfaira, byª stosowany przez Anglików, prawdopodobnie, od czasów Wojny Krymskiej (1854), poprzez Wojny Burskie (1880 do 1902) a» do ko«ca pierwszej wojny ±wiatowej. Wiadomo jednak, »e od poªowy 1915 roku, Niemcy nie mieli problemów z jego zªamaniem. Szyfr ten u»ywa digramów jako jednostek tekstu. Kluczem jest macierz

5×5

zawieraj¡ca 25 liter (bez j). Do jej uªo»enia u»yjemy sªowa kluczowego

,,szyfrowanie.

s o e h q Digram

xy = kij kmn ,

gdzie

z w b k t

x 6= y

y f a n c d l m u v

r i g p x

oraz

i, j , m, n ∈ {1, 2, 3, 4, 5}

je±li

i 6= m i=m i 6= m

szyfrujemy

jako

  kin kmj ki,j+1 ki,n+1   ki+1,j km+1,j

je±li je±li

oraz oraz oraz

j= 6 n; j= 6 n; j = n.

(Dodanie 1 do wska¹nika 5 daje tu wynik 1.) Je»eli lamy, tzn. wtykamy pomi¦dzy

xiy

liter¦

20

q,

x = y,

digram rozdzie-

która jest ró»na od

x

i od

y.

Przeksztaªcenie deszyfruj¡ce w pierwszym przypadku, tj. gdy deszyfrowane litery znajduj¡ si¦ w innych wierszach oraz kolumnach, pokrywa si¦ z szyfruj¡cym.

W pozostaªych przypadkach pozycje liter digramu przesu-

wamy w lewo lub w gór¦ stosuj¡c zasad¦ cykliczno±ci. zaszyfrowanym tek±cie nie mo»e si¦ tra¢ digram postaci

Zauwa»my, »e w

xx.

Šamanie szyfru Playfaira i pozostaªych dwóch szyfrów opartych na kwadracie, polega na analizie statystycznej powi¡za« liter kryptotekstu i na tej podstawie odtworzeniu kwadratu.

2.9

Podwójny szyfr Playfaira

Aby unikn¡¢ niewygody zwi¡zanej z digramami zªo»onymi z takich samych liter, w latach trzydziestych XX wieku, na potrzeby faszystowskiej organizacji SD stworzono system oparty na dwóch kwadratach. Tym razem zrezygnowano z litery

y,

która byªa zast¦powana przez

tak»e zostaªo zmodykowane, tzn.

i.

Przeksztaªcenie szyfruj¡ce

zostaª dodany dodatkowy krok.

Krok

podstawowy algorytmu szyfruj¡cego niewiele ró»niª si¦ od przeksztaªcenia Playfaira. Dokªadnie, wykorzystano dwa kwadraty:

d k v c q

o a r g u

p s f i w

e l t n h b j m x z

s i r t b f l m u v

c d g o w

h n j p x

e a k . q z

(2.1)

Pierwszej litery digramu szukamy w pierwszym kwadracie, a drugiej w drugim. W rezultacie mamy tylko dwa przypadki. Je±li

lij lmn

jest digramem,

lij jest w pierwszym kwadracie, a lmn w drugim, i, j , m, n ∈ {1, 2, 3, 4, 5}, to bijekcja zbioru digramów wyglada nast¦puj¡co. ( lmj lin je±li i 6= m, E ∗ (lij lmn ) = li,j+1 lm,n+1 je±li i = m

przy czym

i znów, pierwsza litera jest w pierwszym kwadracie, a druga w drugim oraz dodanie 1 rozumiemy jako przesuni¦cie cykliczne w kwadracie. Jak ju» wspomnieli±my, algorytm szyfrowania skªadaª si¦ z dwóch kroków. W pierwszym tekst jawny dzielony byª na póª lub na bloki 17-literowe w przypadku, gdy wiadomo±¢ zawieraªa wi¦cej ni» 34 litery.

21

Bloki te byªy

umieszczane jeden nad drugim, a digramy do szyfrowania zbierano pionowo. Na przykªad, aby zaszyfrowa¢ tekst

ZBIERAMY SIE W PIATEK

dzielimy

go na poªowy i odpowiednio umieszczamy:

Z B I E R A M Y S I E W P I A T E K

ZI, BE, IW, EP, RI, AA, MT, YE, SK. Stosuj¡c kwadraty z (2.1) otrzymujemy digramy lv, lk, wo, jh, of, sr, nm, pq oraz fa, które po prostu ª¡czymy w tekst otrzymuj¡c szyfr: lvlkw ojhof srnmp qfa. Digramy do przeksztaªcenia to

Przy deszyfrowaniu, post¦pujemy w odwrotnej kolejno±ci. Zauwa»amy, »e przeksztaªcenie deszyfruj¡ce digramy jest takie samo jak szyfruj¡ce w pierwszym przypadku, tj. kiedy litery znajduj¡ si¦ w wierszach o innych numerach.

2.10

szyfr Delastelle'a

Kwadrat zaproponowany przez felixa Delastelle'a w 1902 roku jest typowym przykªadem szyfru transpozycyjnego (przeksztaªcenie szyfruj¡ce jest równe deszyfruj¡cemu) i eliminuje wszelkie niedogodno±ci zwi¡zane ze stosowaniem ró»nych przypadków. W kwadracie Delastelle'a nie ma litery pujemy przez

v.

s o b j q

z a c k t

y f n i d g l m u v

w, któr¡ zast¦-

r e h p x

Bazowe przeksztaªcenie szyfruj¡ce polega na zamianie wspóªrz¦dnych:

(lij lmn ) = lim ljn .

Dla przykªadu zaszyfrujemy fraz¦

E∗

SZYFR FRANCUSKI.

Pod ka»d¡ liter¡ piszemy pionowo jej wspóªrz¦dne w kwadracie, i znajdujemy litery o wspóªrz¦dnych zapisanych poziomo.

S Z 1 1s 1 2z

Y F 1 1s 3 4g

R F 1 1s 5 4v

Otrzymany kryptogram to

R A 1 2z 5 2t

szsgs vztnc qbki. 22

N C 2 3n 3 2c

U S 5 1q 3 1b

K I 4 2k 2 4i

2.11

Jednostki wieloliterowe

Aby jeszcze bardziej utrudni¢ ªamanie tekstu mo»emy zastosowa¢ trigramy, czyli jednostki trzyliterowe. Pojawia si¦ tu jednak problem odpowiedniego zapisania przeksztaªcenia szyfruj¡cego  tabelka musi by¢ trzywymiarowa. Tym gorszy jest ten problem im dªu»sze s¡ jednostki tekstu. Specjalne sze±ciany szyfruj¡ce na wzór kwadratów Playfaira byªy proponowane przez Luigi Gioppi di Tuerkheim w 1897 roku oraz przez Williama Friedmana w latach dwudziestych XX wieku. Zdecydowanie ch¦tniej przyj¦to popularne podczas I Wojny ‘wiatowej ksi¡»ki kodowe, gdzie szyfrowano od razu caªe wyrazy a nawet zdania. Jednostkami tekstu jawnego s¡ tu cz¦sto powtarzaj¡ce si¦ sekwencje liter. W dalszej perspektywie oznacza to tworzenie swego rodzaju ,,sªowników zwanych ksi¡»kami kodowymi. I tu pojawia si¦ kolejny problem. Nikt nie jest w stanie pami¦ta¢ caªej tre±ci takiej ksi¡»ki. Zatem musi ona zawsze by¢ pod r¦k¡ zarówno koduj¡cego jak i dekoduj¡cego.

Stwarza to

du»e pole manewru dla szpiegów i nie tylko. W sierpniu 1914 roku niemiecki kr¡»ownik Magdeburg próbowaª uciec od rosyjskiego pancernika i sztuka ta mu si¦ nie udaªa. Co gorsza, statek zamiast zaton¡¢, osiadª na mieli¹nie i w zwi¡zku z tym wszystkie ksi¡»ki kodowe niemieckiej marynarki zamiast zaton¡¢, traªy w r¦ce Rosjan, którzy po przestudiowaniu ich ,,podali dalej. W rezultacie ksi¡»ki dostaªy si¦ w r¦ce niejakiego Winstona Churchilla, który wiedziaª jak je wykorzysta¢.

2.12

Szyfry polialfabetyczne

Blaise de Vigenére w wydanej w 1586 roku ksi¡»ce

Traicté des Chifres

opi-

saª kilka ró»nych metod szyfrowania. Ostatecznie jego nazwiskiem nazwano szyfr, który opisany byª wcze±niej przez biskupa J.H. von Trittenheim'a. Idea szyfrów tego typu polega na u»yciu kilku metod szyfruj¡cych nast¦puj¡cych po sobie.

Na przykªad, rozwa»my ci¡g kluczy

k0 , k1 , . . . , kr−1

do szyfrów

Cezara. Przeksztaªcenie szyfruj¡ce deniujemy w nast¦puj¡cy sposób.

Ek0 k1 ...kr−1 (m0 m1 . . . mn ) = (m0 + k0 )(m1 + k1 ) . . . (mn + kn mod r ), przy czy dodawanie wykonujemy modulo liczba liter w alfabecie. Stosuj¡c uto»samienie liter alfabetu z liczbami modulo 26 mo»emy uto»sami¢ ci¡g kluczy i sªowo. Na przykªad zaszyfrujmy

BETYCZNA stosuj¡c klucz anulka.

FUNKCJA POLIALFA-

W tym celu uªó»my tabel¦ przesuni¦¢:

23

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z a b c d e f g h i j k l m n o p q r

s

n o p q r s t u v w x y z a b c d e

f g h i

u v w x y z a b c d e f

g h i

t u v w x y z j

j k l m n o p q

k l m r s

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

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

a b c d e f g h i j k l m n o p q r

s

i

t

j k

g h i

j

t u v w x y z

Pierwszy wiersz powy»szej tabeli to alfabet, a ka»dy nast¦pny wiersz, to alfabet pisany pocz¡wszy od odpowiedniej litery sªowaklucza. Nast¦pnie nasz tekst dzielimy na bloki dªugo±ci sªowa ,,anulka i szyfrujemy pierwsz¡ liter¦ ka»dego bloku wedªug pierwszego szyfru, drug¡ wedªug drugiego itd.

F U N K C J a n u l k a f h h v m j

A P O L I A a n u l k a a c i w s a

L F A B E T a n u l k a l s u m o t

Y C Z N A a n u l k y p t y k

Otrzymali±my zatem kryptogram

fhhvm jaciw salsu motyp tyk.

Deszyfro-

wanie odbywa si¦ na podobnej zasadzie, tj.

Dk0 k1 ...kr−1 (m0 m1 . . . mn ) = (m0 − k0 )(m1 − k1 ) . . . (mn − kn mod r ), gdzie odejmowanie jest wykonywane modulo liczba liter w alfabecie.

Aby

uªatwi¢ szyfrowanie i odszyfrowywanie, J.H. von Trittenheim zaproponowaª poni»sz¡ tabel¦ przesuni¦¢ alfabetu. Nazywa si¦ ona

tabula recta.

24

tablic¡ Tryteniusza

lub

a b c d e

f

b c d e

f

g h

g h

c d e

f

d e

f

g h

e

f

g h

f

g h

g h

g h

i

j

k

i

j

k

l m n o p q r

l m n o p q r

l m n o p q r

i

j

k

i

j

k

l m n o p q r

i

j

k

l m n o p q r

l m n o p q r

i

j

k

i

j

k

l m n o p q r

l m n o p q r

h

i

j

k

i

j

k

l m n o p q r

j

k

l m n o p q r

k

l m n o p q r

l m n o p q r

s

s

s

s

s

s

s

s

s

s

s

t u v w x y z

t u v w x y z a

t u v w x y z a b

t u v w x y z a b c

t u v w x y z a b c d

t u v w x y z a b c d e

t u v w x y z a b c d e

t u v w x y z a b c d e

t u v w x y z a b c d e

t u v w x y z a b c d e

t u v w x y z a b c d e

t u v w x y z a b c d e

m n o p q r

s

n o p q r

s

t u v w x y z a b c d e

o p q r

s

t u v w x y z a b c d e

p q r

s

t u v w x y z a b c d e

q r

s

t u v w x y z a b c d e

r

s

t u v w x y z a b c d e

t u v w x y z a b c d e

s

t u v w x y z a b c d e

u v w x y z a b c d e

f

g h

v w x y z a b c d e

f

w x y z a b c d e

f

g h

x y z a b c d e

f

g h

y z a b c d e

f

g h

z a b c d e

g h

f

s

i

f

g h

f

f

f

f

g h

f

f

g

g h

g h

g h

i

i

j

i

j

k

i

j

k

l

l m

g h

f g h

f g h

i

j

k

g h i

j

k

l m n

k

l m n o

g h i

g h

f

f

f

f

i

j

j k

l m n o p

i

j k l m n o p q k l m n o p q r

g h

i

j

i

j

k

l m n o p q r

l m n o p q r

i

j

k

i

j

k

l m n o p q r

i

j

k

l m n o p q r

i

j

k

l m n o p q r

j

k

l m n o p q r

s

s

s

s

s

s

t

t u

t u v

t u v w

t u v w x

t u v w x y

Šamanie szyfrów Vigenére'a polega na dopasowaniu odpowiedniego alfabetu do pozycji danej litery. Gªównym problemem jest tutaj jednak znalezienie okresu

r.

I to jest zapewne gªówna przyczyna, dla której szyfr Viginére'a

byª ,,nieªamalny przez prawie trzysta lat! Dopiero w 1863 roku, ocer ar-

1

mii pruskiej, F. W. Kasiski wynalazª metod¦ wypadkowej przypadkowo±ci , której nie opiszemy z uwagi na zbyt skomplikowany aparat statystyczny. Wykorzystuj¡c ci¡g kluczy

k0 k1 · · · kr−1

do monoalfabetycznych szyfrów

Beauforta tworzymy szyfr Beauforta, w którym przeksztaªcenia szyfruj¡ce i deszyfruj¡ce pokrywaj¡ si¦.

Ek0 k1 ...kr−1 (m0 m1 . . . mn ) = (−m0 + k0 )(−m1 + k1 ) . . . (−mn + kn mod r ), 1 ang.

the incidence of coincidences

25

Dodawanie i odejmowanie, odbywa si¦ na zasadach arytmetyki modularnej z moduªem, którym jest liczba liter w alfabecie. Stosuj¡c uto»samienie liter alfabetu z liczbami modulo 26 mo»emy uto»sami¢ ci¡g kluczy i pewien wyraz  hasªo. Dla przykªadu zaszyfrujmy

CJA POLIALFABETYCZNA

stosuj¡c klucz

anulka.

FUNK-

W tym celu uªó»my

tabel¦ alfabetów szyfruj¡cych: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z a z y x w v u t

s r q p o n m l k j i h g f

n m l k j

f e d c b a z y x w v u t s

u t l

i h g

s r q p o n m l k j

k j

k j

i h g f

i

h g f e d c b a z

e

d c b

r

q p o

y x w v

e d c b a z y x w v u t s r q p o n m

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

a z y x w v u t

s r q p o n m l k j i h g f

Nast¦pnie nasz tekst dzielimy na bloki dªugo±ci sªowa

e

d c b

anulka

i szyfru-

jemy pierwsz¡ liter¦ ka»dego bloku wedªug pierwszego szyfru, drug¡ wedªug drugiego itd.

F U N K C J a n u l k a v t h b i r

A P O L I A a n u l k a a y g a c a

L F A B E T a n u l k a p i u k g h

Y C Z N A a n u l k c l v y k

Otrzymali±my zatem kryptogram

vthbi rayga capiu kghcl vyk.

Podobnie jak

dla szyfru Vigenére'a i w tym przypadku mo»emy utworzy¢ odpowiedni¡ tabel¦ przesuni¦¢ alfabetu. Uogólnieniem dwóch powy»szych systemów jest

Vigenére'a. kluczy

wariant aniczny szyfru

Do konstrukcji przeksztaªcenia szyfruj¡cego u»ywamy tu ci¡gu

(n0 , k0 ), (n1 , k1 ) . . . , (nr−1 , kr−1 )

do szyfrów anicznych. Sama kon-

strukcja odbywa si¦ na podobnej zasadzie jak w poprzednich przypadkach:

E(m0 m1 . . . mp ) = (n0 m0 + k0 )(n1 m1 + k1 ) . . . (np mod r mp + kp mod r ). Wedªug F. Bauera, oryginalny szyfr Vigenére'a skªadaª si¦ z serii przesuni¦tych alfabetów ustawionych bez okre±lonych reguª arytmetycznych:

26

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z s z y f z y f

r o w a n i e b c d g h

j

k

l m p q

l m p q t

t

u v x

r o w a n i e b c d g h

j

k

y f r o w a n i e b c d g h j

k

l m p q t u v x s z

f

l m p q t u v x

r o w a n i

r o w a n i

e b c d g h

e b c d g h j

o w a n i e b c d g h j k

Generalnie, je±li mamy ci¡g rowany przez ten ci¡g

j k k

u v x s s z y

l m p q t u v x

s

z y f

l m p q t u v x s

z

y f r

E0 , E1 , . . . , Er−1

szyfr polialfabetyczny

bijekcji alfabetu, to gene-

jest dany przez przeksztaªcenie

E(m0 m1 . . . mp ) = E0 (m0 )E1 (m1 ) . . . Ep mod r (mp ), m = m0 m1 . . . mp jest wiadomo±ci¡ jawn¡. Dla przykªadu, szyfr szyfr oryginalny w powy»szym systemie, to lssnq muogk ubusc.

gdzie

frazy

W latach czterdziestych XX wieku C.E. Shannon stworzyª teori¦ entropii, która zajmuje si¦ badaniem informacji zawartej w tek±cie.

Mi¦dzy innymi

zdeniowaª on zasad¦

bezwarunkowego bezpiecze«stwa,

liwego do zªamania.

Szyfr polialfabetyczny jest takim, je±li speªnione s¡

czyli szyfru niemo»-

nast¦puj¡ce warunki

•

Klucz u»yty do szyfrowania wiadomo±ci jest dªu»szy lub równy szyfrowanej wiadomo±ci.

•

Klucz musi by¢ wygenerowany w sposób caªkowicie losowy (nie mo»e istnie¢ sposób na odtworzenie klucza na podstawie znajomo±ci dziaªania generatorów liczb pseudolosowych).

•

Klucz nie mo»e by¢ u»yty do zaszyfrowania wi¦cej ni» jednej wiadomo±ci.

Opublikowany w 1917 roku szyfr G.S. Vernama speªnia te warunki. Kryptosystem ten jest u»ywany do dzi± w poª¡czeniu

gor¡cej linii

mi¦dzy Waszyng-

tonem a Moskw¡. Idea tego szyfru polega na tym, »e klucz jest generowany pseudoprzypadkowo i ten sam generator strumienia pseudoprzypadkowego zamontowany jest na obu ko«cach linii przesyªowej. Klucz szyfruj¡cy i deszyfruj¡cy jest ten sam. Wiadomo±¢ jest najpierw kodowana na strumie« zer i jedynek a nast¦pnie dodawany jest do niej modulo dwa pseudoprzypadkowy strumie« klucza. Dekodowanie odbywa si¦ w oparciu o t¦ sam¡ zasad¦.

27

Zdecydowanie nie jest bezwarunkowo bezpieczny system

autoklucz, gdzie

sama szyfrowana wiadomo±¢ jest kluczem (drugi warunek nie jest speªniony). System autoklucza polega na zastosowaniu pewnego systemu, gdzie litery alfabetu mo»na uto»sami¢ z kluczem. W ten sposób pami¦tamy jeden klucz (starter), wedªug którego szyfrujemy pierwsz¡ liter¦ tekstu. Druga litera jest szyfrowana wg klucza, którym jest pierwsza litera itd. gdzie starterem jest

k,

Dla szyfru Cezara,

mamy

E(m0 m1 m2 . . . mp ) = (m0 + k)(m1 + m0 )(m2 + m1 ) . . . (mp + mp−1 ).

2.13

Ša«cuch szyfrów i DES

Do±¢ istotn¡ wad¡ schematu opisanego w poprzednim paragrae, jest fakt, »e ten sam tekst szyfruje si¦ tak samo, je±li u»yty jest ten sam klucz. Chodzi o to, »e potencjalny intruz wcale nie musi zna¢ tekstu jawnego, by wymusi¢ na odbiorcy szyfru okre±lone dziaªanie  wystarczy, »e prze±le mu przechwycony wcze±niej (zaszyfrowany) tekst. Poniewa» intruz wie jaka reakcja byªa wcze±niej, podejrzewa, »e taka sama b¦dzie i tym razem. Jednym ze sposobów omini¦cia tej niedogodno±ci jest zastosowanie

Ša«cuch szyfrów 1 .

Pomysª jest

nast¦puj¡cy: Dzielimy tekst jawny (zakodowany w strumie« bitów) na bloki bitów. Potrzebny jest inicjuj¡cy wektor zero-jedynkowy

C0

o

n

Mi

po

n

bitach oraz

klucz K tej samej dªugo±ci. Pierwszy blok tekstu jawnego szyfrujemy jako C1 = M1 ⊕ C0 ⊕ K , drugi jako C2 = M2 ⊕ C1 ⊕ K , i tak dalej. Ogólnie, Cj = Mj ⊕ Cj−1 ⊕ K . W celu rozszyfrowania, dzielimy tekst zaszyfrowany na n-bitowe kawaªki Ci i otrzymujemy kolejno M1 = C1 ⊕ C0 ⊕ K , nast¦pnie, M2 = C2 ⊕ C1 ⊕ K itd. Je±li który± z Ci jest bª¦dny, to otrzymujemy bª¡d w co najwy»ej dwóch kawaªkach tekstu jawnego, mianowicie Mi oraz Mi+1 . Wektor C0 musi by¢ przesªany innym kanaªem ni» wiadomo±¢ jawna i klucz. Przy odpowiednio du»ym n istnieje bardzo maªa szansa, »e wiadomo±¢, klucz i wektor inicjuj¡cy powtórz¡ si¦.

1

Ša«cuch szyfrów jest wykorzystany w systemie DES , który byª u»ywany od 1977 roku do ko«ca lat osiemdzisi¡tych. W 1974 roku, National Bureau of Standards zobowiazaªo rmy ameryka«skie do napisania programu szyfruj¡cego, który b¦dzie standardem w kodowaniu wiadomo±ci rz¡dowych. Miaª on

1 ang.

1 Data

cipherblock chaining Encryption Standard

28

zastapi¢ niewygodne w u»yciu ksi¡»ki kodowe. Odpowiedzi¡ rmy IBM byª system LUCIFER, który po uproszczeniu i modykacji staª si¦ standardem. Program szyfruj¡cy zostaª rozpowszechniony w postaci ko±ci, któr¡ ka»dy zainteresowany mógª wmontowa¢ w swój komputer. Rozszyfrowywanie polegaªo na u»yciu tej samej ko±ci. Opiszemy teraz zasad¦ dziaªania algorytmu DES. Wej±ciowe 64 bity s¡ najpierw pomieszane przez pocz¡tkow¡ permutacj¦ tworz¡ wektor

L0 ,

a nast¦pne 32 tworz¡

R0 .

IP .

Pierwsze 32 bity

Po szesnastu rundach manipu-

lacji, wektory lewy i prawy ª¡cz¡ si¦ w caªo±¢ i przechodz¡ przez permutacj¦ IP −1 generuj¡c ostateczn¡ wersj¦ szyfru. Podczas 16 rund szyfrowania tworz¡ si¦ kolejno wektory oraz

R1 , R2 , . . . , R16 .

Dla

1 ≤ i ≤ 16,

Ki

f (Ri−1 , Ki )

mamy

Ri = Li−1 ⊕ f (Ri−1 , Ki ),

Li = Ri−1 , gdzie

L1 , L2 , . . . , L16

jest wektorem dwójkowym o 32 wspóªrz¦dnych, a wektory

s¡ 48-bitowymi wektorami generowanymi przez klucz

K

wedªug proce-

dury, któr¡ opiszemy pó¹niej. Dekodowanie odbywa si¦ w odwrotn¡ stron¦, tj. najpierw zaszyfrowany −1 tekst jest poddawany permutacji IP , tworz¡ si¦ L16 i R16 , a nast¦pnie obliczane s¡ kolejno

R15 = L16 , L15 = R16 ⊕ f (R15 , K16 ) . . . , R0 = L1 , L0 = R1 ⊕ f (R0 , K1 ). Poª¡czony wektor

L0 R0

jest poddany permutacji

IP

i powstaje ci¡g 64 bitów

wiadomo±ci jawnej. Warto±ci¡ funkcji

f

jest 32-bitowy ci¡g. Procedura jego powstawania wy-

Ki ma 48 bitów, a Ri−1 - 32 bity. rozszerzy¢ Ri−1 do 48 bitów. Rozszerzenie

gl¡da nast¦puj¡co. Jak ju» wspominali±my, Aby te wektory doda¢, musimy

Ri−1

odbywa si¦ wedªug Tabeli selekcji bitów. Powstaªy 48-bitowy strumie«

jest podzielony na 8 wektorow 6-bitowych, które s¡ przepuszczone przez

S -boksów, rozwa»my wektor sze±ciobitowy a1 a2 a3 a4 a5 a6 , na przykªad 010011, który traa na S4 . Bity a1 a6 to numer wiersza (i), a a2 a3 a4 a5 to numer kolumny (j ) zapiboksy (Tabela

S -boksów).

S-

Aby przybli»y¢ metod¦ dziaªania

sane w ukªadzie dwójkowym. Strumie« wyj±ciowy (w ukªadzie dziesi¦tnym) jest na pozycji i w

S4

(i, j) S -boksa.

znajduje si¦ na pozycji

wyj±ciowym jest

012 = 1 oraz 10012 = 9 7 = 01112 . Zatem strumieniem

W naszym przypadku,

(1, 9)

liczba

0111. 29

32

1

2

3

4

5

4

5

6

7

8

9

8

9

10

11

12

13

12

13

14

15

16

17

16

17

18

19

20

21

20

21

22

23

24

25

24

25

26

27

28

29

28

29

30

31

32

1

Rysunek 2.2: Tabela selekcji bitów

Po wyj±ciu z

S -boksów,

strumienie 4-bitowe ª¡cz¡ si¦ tworz¡c 32-bitowy

wektor, który dodatkowo przechodzi przez permutacj¦ Klucz

K

P.

ma 64 bity podzielone na 8-bitowe cz¦±ci, z których ka»da ma

7 efektywnych bitów, a ósmy bit sprawdza parzysto±¢.

Dokªadnie, jest on

ustalony tak, by w caªej ósemce liczba jedynek byªa parzysta. W przypadku, gdyby wyst¡piª bª¡d w transmisji klucza, zostaje on wykryty z dokªadnym wskazaniem ósemki, w której wyst¡piª. Z 64 bitów klucza, po sprawdzeniu poprawno±ci, 8 bitów sprawdzaj¡cych jest odrzuconych, a pozostaªe 56 bitów przechodzi przez permutacj¦ pocz¡tkow¡

P C1.

Spermutowany strumie« 56

bitów jest podzielony na póª. Pierwsze 28 bitów tworzy wektor

C0 ,

a nast¦-

pne D0 . Wektory C1 i D1 powstaj¡ przez (cykliczne) przesuni¦cie zawarto±ci C0 , odpowiednio, D0 o LS1 = 1 pozycji w lewo. Ogólnie, Ci oraz Di powstaj¡ przez przesuni¦cie zawarto±ci, odpowiednio, Ci−1 , Di−1 o LSi pozycji w lewo. Wektory Ci oraz Di s¡ nast¦pnie ª¡czone i po przej±ciu selekcji P C2 tworz¡ 48-bitowy strumie« Ki . Gªówne zarzuty wobec DES, to, po pierwsze, zbyt krótki klucz, co powoduje, »e mo»e on by¢ znaleziony w miar¦ szybko metod¡ sprawdzenia wszyst56 kich 2 mo»liwo±ci. Po drugie, nie wiadomo, jakie kryteria kierowaªy konstruktorami

S -boksów.

Testy statystyczne pokazuj¡, »e liczby w

S -boksach

nie s¡ przypadkowe. Niewykluczone, »e kryje si¦ tu pewna furtka pozwalaj¡ca ªatwo rozszyfrowa¢ zakodowan¡ wiadomo±¢. Mimo swoich wad DES byª do±¢ dªugo u»ywany, a» w ko«cu ust¡piª on miejsca kryptosystemom o kluczu publicznym. Rozpowszechnienie szybkich, ªatwo programowalnych komputerów doprowadziªo do sytuacji, w której ko±¢ szyfruj¡ca okazaªa si¦ zb¦dna:

Po co montowa¢ do komputera dodatkowe

urz¡dzenie, je±li mo»na napoisa¢ program, który powoduje takie samo dziaªanie, a jeszcze dodatkowo mo»na go w ka»dej chwili ulepszy¢.

30

kolumna 0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

0

14

4

13

1

2

15

11

8

3

10

6

12

5

9

0

7

1

0

15

7

4

14

2

13

1

10

6

12

11

9

5

3

8

wiersz

S1

S2

S3

S4

S5

S6

S7

S8

2

4

1

14

8

13

6

2

11

15

12

9

7

3

10

5

0

3

15

12

8

2

4

9

1

7

5

11

3

14

10

0

6

13

0

15

1

8

14

6

11

3

4

9

7

2

13

12

0

5

10

1

3

13

4

7

1

2

8

14

12

0

1

10

6

9

11

5

2

0

14

7

11

10

4

13

1

5

8

12

6

9

3

2

15

3

13

8

10

1

3

15

4

2

11

6

7

12

0

5

14

9

0

10

0

9

14

6

3

15

5

1

13

12

7

11

4

2

8

1

13

7

0

9

3

4

6

10

2

8

5

14

12

11

15

1

2

13

6

4

9

8

15

3

0

11

1

2

12

5

10

14

7

3

1

10

13

0

6

9

8

7

4

15

14

3

11

5

2

12

0

7

13

14

3

0

6

9

10

1

2

8

5

11

12

4

15

1

13

8

11

5

6

15

0

3

4

7

2

12

1

10

14

9

2

10

6

9

0

12

11

7

13

15

1

3

14

5

2

8

4

3

3

15

0

6

10

1

13

8

9

4

5

11

12

7

2

14

0

2

12

4

1

7

10

11

6

8

5

3

15

13

0

14

9

1

14

11

2

12

4

7

13

1

5

0

15

10

3

9

8

6

2

4

2

1

11

10

13

7

8

15

9

12

5

6

3

0

14

3

11

8

12

7

1

14

2

13

6

15

0

9

10

4

5

3

0

12

1

10

15

9

2

6

8

0

13

3

4

14

7

5

11

1

10

15

4

2

7

12

9

5

6

1

13

14

0

11

3

8

2

9

14

15

5

2

8

12

3

7

0

4

10

1

13

11

6

3

4

3

2

12

9

5

15

10

11

14

1

7

6

0

8

13

0

4

11

2

14

15

0

8

13

3

12

9

7

5

10

6

1

1

13

0

11

7

4

9

1

10

14

3

5

12

2

15

8

6

2

1

4

11

13

12

3

7

14

10

15

6

8

0

5

9

2

3

6

11

13

8

1

4

10

7

9

5

0

15

14

2

3

12

0

13

2

8

4

6

15

11

1

10

9

3

14

5

0

12

7

1

1

15

13

8

10

3

7

4

12

5

6

11

0

14

9

2

2

7

11

4

1

9

12

14

2

0

6

10

13

15

3

5

8

3

2

1

14

7

4

10

8

13

15

12

9

0

3

5

6

11

Rysunek 2.3: Tabela

31

S -boksów

Rozdziaª 3 Maszyny szyfruj¡ce Kod maszyn szyfruj¡cych jest klasycznym transpozycyjnym szyfrem polialfabetycznym.

Ze wzgl¦du jednak na wag¦, jak¡ odegraª on w historii, po-

±wi¦camy mu osobny rozdziaª.

3.1

Zasada dziaªania

Pomysª skonstruowania maszyny szyfruj¡cej powstaª zapewne wraz z ide¡ zwykªej maszyny do pisania  wystarczy inaczej poª¡czy¢ klawiatur¦ z czcionkami, a zamiast tekstu pisanego na klawiaturze, na papierze pojawi si¦ szyfr. Aby nie u»ywa¢ dwóch maszyn (jednej do szyfrowania, drugiej do rozszyfrowywania), powszechnie u»ywa si¦ w maszynach szyfrów transpozycyjnych. Na rysunku 3.1. szyny do pisania.

przedstawiony jest uproszczony schemat zwykªej ma-

Je±li wci±niemy klawisz ,,O, na papierze pojawi si¦ li-

tera ,,O. Zmienimy teraz sposób zadrutowania, czyli przebieg szarych linii (rysunek 3.2). Tym razem po wci±ni¦ciu klawisza ,,O, na papierze pojawi si¦ litera ,,I. A je±li wci±niemy po kolei czyli

wisk.

S O W A, napiszemy szyfr sªowa ,,sowa,

Nast¦pnym krokiem jest skonstruowanie kilku pasków z szarymi liniami, które deniuj¡ szyfr oraz zaprojektowanie maszyny w ten sposób, by paski te mo»na byªo w dowolnym momencie wymienia¢. St¡d ju» tylko krok do zast¡pienia paska walcem  wystarczy umie±ci¢ styki na obwodzie. Walec (rotor) mo»e si¦ obraca¢ i w ten sposób zmienia¢ metod¦ szyfrowania (rysunek 3.3). Naci±ni¦cie klawisza oznacza obrót walca o jeden styk. Zatem, po naci±ni¦ciu ,,S pojawia si¦ ,,W (jak dot¡d), ale walec si¦ obraca i po naci±ni¦ciu

32

Rysunek 3.1: Maszyna do pisania

,,O mamy ju» ,,E. W ostateczno±ci zaszyfrowane sªowo

SOWA, to oeke.

Nast¦pne ulepszenia, to doªo»enie kolejnych walców oraz reektora, który wykorzystuje walce podwójnie (sygnaª idzie z klawiatury, szyfrowany jest przez walce, a nast¦pnie odbijany przez reektor i ponownie szyfrowany przez wszystkie walce. Stosowano te» kilka innych metod, jak np. ruchome bolce, które powoduj¡, »e walce obracaj¡ si¦ o wi¦cej ni» jeden styk. U»ywana przez Amerykanów maszyna szyfruj¡ca

Hagelin

skonstruowana

przez B. Hagelina posiada a» 6 rotorów z odpowiednio, 26, 25, 23, 21, 19 i 17 bolcami. Ka»dy z tych bolców mo»e by¢ w pozycji pasywnej lub aktywnej. Po zaszyfrowaniu litery, wszystkie walce obracaj¡ si¦ o jedn¡ pozycj¦ w zale»no±ci od pozycji bolców. Po zaszyfrowaniu 25-literowego tekstu, drugi walec (i tylko on) jest w oryginalej pozycji.

Poniewa» liczby bolców na poszcze-

gólnych rotorach s¡ kopierwsze, system Hagelin mo»na porówna¢ do szyfru Vigenere'a z okresem równym

26 · 25 · 23 · 21 · 19 · 17 = 101 405 850.

Elekro-mechaniczna ENIGMA, u»ywana przez Niemców i Japo«czyków, zostaªa wynaleziona w 1923 roku przez A. Scherbius'a. W pierwszej wersji byªy to trzy rotory oraz reektor. W 1941 oraz 1943 roku doªo»ono po jednym walcu.

Naci±ni¦cie klawisza ,,A powoduje szyfrowanie litery wg schematu

z rysunku 3.4, tj.

po wyj±ciu z klawwiatury (2), sygnaª przechodzi przez

przeka¹nik (3), styki (4), trzy walce szyfruj¡ce (5), reektor (6) i ponownie przez walce i styki. Otrzymujemy liter¦ ,,S. Teraz mamy jeszcze dodatkow¡ pªyt¦ przeª¡czników (8), która zamienia nasze ,,S na ,,D. Ostatecznie zapala si¦ »arówka (9) z liter¡ ,,D. Po caªej tej procedurze, pierwszy walec (tylko)

33

Rysunek 3.2: Maszyna do szyfrowania

Rysunek 3.3: Maszyna do szyfrowania z obracanym walcem

obracaª si¦ o jedn¡ pozycj¦. Po ,,wstukaniu 26-literowego tekstu, pierwszy walec wracaª do pierwotnego ustawienia, a drugi obracaª si¦ o jedn¡ pozycj¦. Najsªabsz¡ stron¡ ENIGMY i gªównym powodem zªamania szyfru byª sposób przesyªania identykatorów, czyli ustawie« poszczególnych walców. Odpowiednie rotory oraz poª¡czenia wtyczek byªy przekazywane w odpowiednich arkuszach ustawie«. Aby zacz¡¢ szyfrowanie, nale»aªo ustawi¢ poªo»enie pocz¡tkowe rotorów (pierwszy identykator - ABC). Nast¦pnie zakodowa¢ dowolny trigram (np.

AAA), co dawaªo drugi identykator (JME).

Po ustawieniu rotorów na AAA (nasz przykªadowy trigram) mo»na kodowa¢ wiadomo±¢, np. ENIGMAKODJEDEN. Zaszyfrowany tekst do wysªania to

abc jme bikrn hozyp wjls. 34

Rysunek 3.4: Schemat ENIGMY

35

Aby rozszyfrowa¢ wiadomo±¢

abc jme bikrn hozyp wjls ustawiamy ro-

tory na ABC (pierwszy identykator), wstukujemy JME (drugi identykator), co daje wiadomo±¢ AAA. Ustawiamy rotory na AAA i wstukujemy dalsz¡ cz¦±¢ tekstu.

3.2

Jak zªamano szyfr ENIGMY

Tajemnica kodu ENIGMY zostaªa zªamana w 1932 roku przez Polskie Biuro Szyfrów kierowane przez Maksymiliana Ci¦»kiego. Pod jego kierunkiem pracowaªo trzech matematyków: Marian Rejewski, Jerzy Ró»ycki oraz Henryk Zygalski. Dane techniczne oraz sposoby szyfrowania zostaªy najpierw przekazywane od jesieni 1931 roku wywiadowi francuzkiemu przez szpiega Hansa Thilo Schmidta. Pod koniec 1932 roku major Gustav Bertrand (pseudonim ,,Bolek) przesªaª te dane do Polskiego Biura Szyfrów. Teraz przyszªa kolej na rozszyfrowanie. Co zauwa»ono od razu, to dwa trigramy, które poprzedzaªy ka»dy tekst podawany w blokach pi¦cioliterowych. Marian Rejewski zaªo»yª, »e jest to identykator, który skªada si¦ z dwóch identycznych trigramów zaszyfrowanych na dwa ró»ne sposoby. Niech

P 1 , P2 , P3 , P 4 , P5 , P6

oznaczaj¡ permu-

tacje alfabetu, którymi zaszyfrowana jest odpowiednia litera identykatora.

i ∈ {1, 2, 3}, to z tego, »e Pi a = x oraz Pi+3 a = y wynika −1 natychmiast, »e Pi+3 Pi x = y . Jednak»e ENIGMA stosowaªa szyfry trans−1 pozycyjne, wi¦c Pi = Pi . St¡d mamy Pi+3 Pi x = y . Przyjrzyjmy si¦ tablicy

Wówczas, je±li

identykatorów (rysunek 3.5). W permutacji

•

z 1.

•

z 35.

•

z 2. i 4.

•

z 30. i 53.

a

P4 P 1

mamy

przechodzi na siebie;

s

przechodzi na siebie;

b

przechodzi na

r

c

przechodzi na

i odwrotnie;

w

i odwrotnie.

Post¦pujemy podobnie dalej i ostatecznie otrzymujemy

P4 P1 = (a)(s)(bc)(rw)(dvpf kxgzyo)(eijmunqlht). 36

1

AUQ

AMN

23

NXD

QTU

45

TMN

EBY

2

BNH

CHL

24

NXD

QTU

46

TMN

EBY

3

BCT

CGJ

25

NLU

QFZ

47

TAA

EXB

4

CIK

BZT

26

OBU

DLZ

48

USE

NWH

5

DDB

VDV

27

PVJ

FEG

49

VII

PZK

6

EJP

IPS

28

QGA

LYB

50

VII

PZK

7

FBR

KLE

29

QGA

LYB

51

VQZ

PVR

8

GPB

ZSV

30

RJL

WPX

52

VQZ

PVR

9

HNO

THD

31

RJL

WPX

53

WTM

RAO

10

HNO

THD

32

RJL

WPX

54

WTM

RAO

11

HXV

TTI

33

RJL

WPX

55

WTM

RAO

12

IKG

JKF

34

RFC

WQQ

56

WKI

RKK

13

IKG

JKF

35

SYX

SCW

57

XRS

GNM

14

IND

JHU

36

SYX

SCW

58

XRS

GNM

15

JWF

MIC

37

SYX

SCW

59

XOI

GUK

16

JWF

MIC

38

SYX

SCW

60

XYW

GCP

17

KHB

XJV

39

SYX

SCW

61

YPC

OSQ

18

KHB

XJV

40

SJM

SPO

62

YPC

OSQ

19

LDR

HDE

41

SJM

SPO

63

ZZY

YRA

20

LDR

HDE

42

SJM

SPO

64

ZEF

YOC

21

MAW

UXP

43

SUG

SMF

65

ZSJ

YWG

22

MAW

UXP

44

SUG

SMF

Rysunek 3.5: Tablica identykatorów ENIGMY.

Podobnie znajdujemy zªo»enia

P5 P2

oraz

P6 P 3 .

P5 P2 = (d)(k)(axt)(cgy)(blf qveoum)(hjpswizrn), P6 P3 = (abviktjgf cqny)(duzrehlxwpsmo).

Cykle dªugo±ci jeden (,,samiczki wg »argonu Polskiego Biura Szyfrów) s¡ najªatwiejsze: je±li P4 P1 = α, to oznacza to, »e musi istnie¢ β takie, »e P4 β = α oraz P1 α = β . Zatem zarówno P1 jak i P4 zawieraj¡ transpozycj¦ (as). Podobnie, P2 oraz P5 maj¡ w swoim rozkªadzie (dk). Co do pozostaªych cykli, to potrzebne nam jest pewne twierdzenie z teorii permutacji.

37

3.1.Twierdzenie.

Zaªó»my, »e permutacja

P

zawiera 2-cykle

(x1 y1 )(x2 y2 ) . . . (xk yk ) a permutacja

Q

zawiera 2-cykle

(y1 x2 )(y2 x3 ) . . . (yk x1 ). Wówczas zªo»enie

QP

zawiera

Zatem, je±li 10cykle w

k -cykle (x1 x2 . . . xk )

P 4 P1

oraz

(yk yk−1 . . . y1 ).

,,zgrywaj¡ si¦ w fazie, to wystarczy pod

pierwszym podpisa¢ drugi w odwrotnej kolejno±ci i wszystkie transpozycje oraz

P4

P1

mamy w zasi¦gu r¦ki. Problem jednak jest w znalezieniu fazy tak dla

2- jak i dla 10-cykli. W tym celu trzeba sprawdzi¢ 20 (=

2 · 10)

przypadków.

Co gorsza, przypadki te s¡ niezale»ne od przypadków rozwa»anych dla pozostaªych permutacji. W efekcie pozostaje do rozwa»enia

2 · 10 · 3 · 9 · 13 = 7020

przypadków. Marian Rejewski skorzystaª tu ze znanego stereotypu dotycz¡cego Niemców: lubi¡ oni porz¡dek. Poza tym, maªo kto potra wybra¢ na klawiaturze typowo przypadkowy ukªad, zwªaszcza gdy musi to robi¢ po raz setny w ci¡gu

aaa, bbb aaa, poniewa» P4 oraz P1 P2 a = y , P5 a = c, wi¦c P2 zawiera cykl

dnia. W zwi¡zku z tym, cz¦st¡ praktyk¡ byª wybór identykatora lub

sss.

Zaªó»my wi¦c, »e identykatory 35-39, to

(as). Wynika st¡d, »e (ay), natomiast P5 , transpozycj¦ ac. Zapiszmy odpowiednio 3-cykle zªo»enia P5 P2 : a x t y g c

zawieraj¡ cykl

Otrzymujemy transpozycje

(gt)

(ca) b¦d¡ce permutacji P3 i P6 . oraz

(ay), (xg) oraz (tc) wchodz¡ce w skªad P2 i (yx), P5 . Chwil¦ pó¹niej otrzymujemy caªy rozkªad

cz¦±ci¡

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

P3 = (ax)(bl)(vh)(ie)(kr)(tz)(ju)(gd)(f o)(cm)(qs)(np)(yw) P6 = (xb)(lv)(hi)(ek)(rt)(zj)(ug)(df )(oc)(mq)(sn)(py)(wa). 38

oraz

Id¡c tym tropem, widzimy, »e pierwsza i trzecia litera tekstu jawnego identykatora 1, to

s.

Zatem litera ±rodkowa, to pewnie te»

s.

Mamy zatem

rozkªady

P2 = (dk)(ay)(xg)(tc)(su)(wo)(ie)(zv)(rq)(nf )(hl)(jb)(pm), P5 = (dk)(yx)(gt)(ca)(uw)(oi)(ez)(vr)(qn)(f h)(lj)(bp)(ms). Zostaj¡ nam ju» tylko

P1

i

P4 .

Patrzymy na identykatory 53-55 (na przy-

c. Zac. Otrzymujemy st¡d cykle (cw) oraz (wb) i (rc) jako cz¦±¢ permutacji P5 . Na

kªad) i zauwa»amy, »e ich druga i trzecia litera tekstów jawnych, to pewne wi¦c pierwsza litera, to tak»e

(br),

które s¡ cz¦±ci¡

P1

oraz cykle

koniec rozwa»amy identykatory 49 i 50, których tekst jawny, to prawdopodobnie,

eee

i otrzymujemy ostatecznie

P1 = (as)(cw)(br)(ev)(id)(jo)(my)(uz)(ng)(qx)(lk)(hf )(tp), P4 = (as)(wb)(rc)(vi)(dj)(om)(yu)(zn)(gq)(xl)(kh)(f t)(pe). Caªa tabela jawnych tekstów identykatorów przedstawiona jest poni»ej. Je±li we¹miemy jeszcze pod uwag¦ ukªad klawiszy na klawiaturze ENIGMY (tak»e poni»ej) oraz kolejno±¢ liter w alfabecie, to w tabeli jawnych tekstów identykatorów nie znajdziemy nic oryginalnego. 1

sss

12

ddd

2 3 4

23

ggg

rfv

13

rtz

14

wer

34

ddd

24

ggg

dfg

25

ghj

15

ooo

26

jjj

37

Pocz¡wszy od roku 1933

bnm

45

ppp

56

cde

35

aaa

46

ppp

57

qqq

36

aaa

47

pyx

58

qqq

aaa

48

zui

59

qwe

5

ikl

16

ooo

27

tzu

38

aaa

49

eee

60

qay

6

vbn

17

lll

28

xxx

39

aaa

50

eee

61

mmm

7

hjk

18

lll

29

xxx

40

abc

51

ert

62

mmm

8

nml

19

kkk

30

bbb

41

abc

52

ert

63

uvw

9

f

20

kkk

31

bbb

42

abc

53

ccc

64

uio

10

f

21

yyy

32

bbb

43

asd

54

ccc

65

uuu

11

fgv

22

yyy

33

bbb

44

asd

55

ccc

Rysunek 3.6: Jawne teksty identykatorów ENIGMY. identykatory, w których byªy 3 takie same litery zostaªy zakazane. Byªo ju» jednak za pó¹no, poniewa» Polacy znali ju» dobrze ENIGM†. Zªe zwyczaje zreszt¡ i tak pozostaªy i zawsze mo»na si¦ byªo dopatrzy¢ pewnej reguªy w ukªadzie liter identykatora.

39

Q

W A

P

E S

Y

R D

X

T F

C

Z G

V

U H

B

I J

N

O K

M

L

Rysunek 3.7: Klawiatura ENIGMY.

Odszyfrowanie tabeli identykatorów byªo najwa»niejsz¡ cz¦±ci¡ ªamania szyfru, ale nie ko«cz¡c¡. Teraz w oparciu o otrzymane permutacje nale»aªo odpowiednio dobra¢ rotory, zaprogramowa¢ maszyn¦ oraz skorzysta¢ z niej odczytuj¡c tekst. Od 1936 roku, szyfr nale»aªo ªama¢ codziennie, poniewa» obowi¡zkowa byªa codzienna zmiana rotorów i innych ustawie«.

Ka»de z

ustawie« byªo jednak dokªadnie obejrzane przez pracowników Polskiego Biura Szyfrów i w zasadzie ka»da przechwycona wiadomo±¢ byªa rozszyfrowana.

40

Rozdziaª 4 Macierze szyfruj¡ce System kryptograczny, który rozwa»ymy w tym rozdziale zostaª zaproponowany przez Lester'a Hill'a w 1929 roku.

System ten, jak za chwil¦ zo-

baczymy staª si¦ przeªomem w kryptograi, poniewa» jest to historycznie pierwszy system, który szyfruje wieloliterowe jednostki tekstu i nie wymaga przy tym skomplikowanego klucza. Podstawow¡ ide¡ jest tu algebra liniowa, a wªa±ciwie teoria moduªów nad

4.1

ZN .

Algebra liniowa modulo N

Przypuszczamy, »e dany jest

26-literowy

(lub, ogólnie,

N -literowy)

w którym uto»samiamy litery i liczby tak, jak dotychczas. tekstu wybieramy

n-gramy,

czyli bloki

n

alfabet,

Jako jednostki

literowe. Poniewa» uogólnienie jest

proste, wi¦c ograniczymy si¦ do przypadków, gdy

n=2

lub

n = 3.

Ka»dy

digram przedstawiamy jako wektor   o dwóch wspóªrz¦dnych. Dokªadnie, blok liter

xy

przedstawiamy jako

  14 wektor . 13 rz¦dnych, xyz ,

x y

. Na przykªad, digramowi ON odpowiada

Podobnie uto»samiamy trigramy i wektory o trzech wspóªto

x y z


T

itd.

Jak wiadomo, ka»demu wektorowi zaczepionemu w prostok¡tnym ukªadzie wspóªrz¦dnych odpowiada punkt ko«ca tego wektora. Zatem mo»emy n tu wprowadzi¢ prostok¡tny ukªad wspóªrz¦dnych, tyle »e nie b¦dzie to R , n n ale Z26 lub ogólnie ZN . Ka»demu n-gramowi odpowiada wi¦c punkt na (sko«czonej) pªaszczy¹nie anicznej.

41

Teraz, gdy przedstawili±my ju» nasze

n-gramy

jako wektory b¡d¹ punkty

na pªaszczy¹nie anicznej, mo»emy wykorzysta¢ przeksztaªcenia ró»nowarto±ciowe pªaszczyzny jako funkcje szyfruj¡ce.

W szczególno±ci mo»emy tu

wykorzysta¢ wiadomo±ci z algebry liniowej i anicznej. Przypomnijmy wi¦c, »e dowolne przeksztaªcenie liniowe (homomorzm) macierzow¡, czyli tak¡ macierz równe

AX .

caj¡c przez obrazów.

Macierz

f

A

f

ma swoj¡ reprezentacj¦

  1 0

X mamy f (X) n = 2) przeksztaª-

»e dla dowolnego wektora

otrzymujemy (w przypadku, gdy

generatory

Je±li

A,

f

oraz

  0 1

a nast¦pnie ukªadaj¡c macierz z

jest ró»nowarto±ciowe (jest monomorzmem), to odwzo-

rowanie odwrotne do

f

Podamy teraz prosty algorytm na obliczenie macierzy odwrotnej Jest to znany algorytm

A. do A.

jest reprezentowane przez macierz odwrotn¡ do

eliminacji Gaussa.

Jest on te» podstaw¡ kryptoana-

lizy systemów opartych na macierzach. W celu obliczenia macierzy odwrotnej do

A,

ukªadamy najpierw macierz

(A|I),

gdzie

I

jest macierz¡ jednostkow¡.

Nast¦pnie stosujemy elementarne przeksztaªcenia wierszy: 1. pomno»enie wiersza przez liczb¦ odwracaln¡ modulo

N,

2. zamiana dwóch wierszy, 3. dodanie do jednego wiersza kombinacji liniowej pozostaªych,

A tak aby dosta¢ macierz jednostkow¡ I . Oczywi±cie, w tym samym (A|I). Gdy ju» to osi¡gniemy, macierz¡ po prawej stronie I b¦dzie macierz odwrotna do A. Opisany algoMacierz

czasie jest przeksztaªcana druga cz¦±¢ macierzy

rytm mo»na te» stosowa¢ dla macierzy nieodwracalnej. Wtedy nie b¦dziemy jednak w stanie doprowadzi¢ lewej strony do postaci macierzy jednostkowej.

 Dla przykªadu, obliczymy macierz odwrotn¡ do czynniki s¡ z



9 15 19 2

 , gdzie wspóª-

Z26 .

9 15 | 1 0 19 2 | 0 1





1 19 | 3 0 19 2 | 0 1



mno»ymy pierwszy −1 wiersz przez 3 = 9



1 19 | 3 0 0 5 | 21 1



19 razy odejmujemy

formujemy macierz

(A|I)

pierwszy wiersz od drugiego

42



 1 19 | 3 0 0 1 | 25 21   1 0 | 22 17 0 1 | 25 21

Zatem

−1

A

 =

22 17 25 21

mno»ymy drugi −1 wiersz przez 5

= 21

19 razy odejmujemy drugi wiersz od pierwszego

 . Zastosujemy teraz eliminacj¦ Gaussa, aby znale¹¢



macierz odwrotn¡ do

 2 4 5 B =  1 3 23. 15 24 13 

2 1 15  1 2 15  1 0 0  1 0 0  1 0 0  1 0 0  1 0 0  1 0 0

Otrzymujemy

 4 5 | 1 0 0 3 23 | 0 1 0 24 13 | 0 0 1  3 23 | 0 1 0 4 5 | 1 0 0 24 13 | 0 0 1  3 23 | 0 1 0 24 11 | 1 24 0 5 6 | 0 11 1  3 23 | 0 1 0 5 6 | 0 11 1 24 11 | 1 24 0  3 23 | 0 1 0 1 22 | 0 23 21 24 11 | 1 24 0  0 9 | 0 10 15 1 22 | 0 23 21 0 3 | 1 18 16  0 9 | 0 10 15 1 22 | 0 23 21 0 1 | 9 6 14  0 0 | 23 8 19 1 0 | 10 21 25 . 0 1 | 9 6 14 43



Ostatecznie mamy

B −1

 23 8 19 = 10 21 25. 9 6 14

By nie robi¢ nic ,,na darmo warto jest wiedzie¢, kiedy dana macierz jest odwracalna. Mówi o tym nast¦puj¡ce twierdzenie.

4.2.Twierdzenie. Dla dowolnej macierzy A o wspóªczynnikach w ZN

nast¦-

puj¡ce warunki s¡ równowa»ne: (i) NWD(det A, (ii)

A

ma macierz odwrotn¡;

(iii) je±li

(iv)

A

N ) = 1;

xiy

nie s¡ jednocze±nie równe zeru, to

    x 0 A 6= ; y 0

okre±la odwzorowanie wzajemnie jednoznaczne.

4.2



Szyfry Hill'a

Przedstawimy tu dokªadnie metod¦ szyfrowania, deszyfrowania oraz kryptoanalizy systemu Hill'a dla macierzy

Szyfrowanie

2 × 2.

wygl¡da nast¦puj¡co:

1. Wybieramy macierz

A o wspóªczynnikach caªkowitych odwracaln¡ mo-

dulo 26. 2. Grupujemy tekst jawny w digramy. Je±li liczba liter w tek±cie nie jest podzielna przez

2,

dodajemy na ko«cu tekstu cokolwiek.

3. Ka»dy utworzony wektor macierz

A

i wektory

Ap

  x p = y

tekstu jawnego mno»ymy przez

ustawiamy po kolei w tekst zaszyfrowany.

4.3.Przykªad. Macierz¡ szyfruj¡c¡ jest WAMY.

44



1 2 0 3

 . Zaszyfrujemy tekst UKRY-

Grupujemy najpierw nasz tekst w jednostki dwuliterowe i otrzymujemy pi¦¢ wektorów

  20 , 10

  17 , 24

  22 , 0

  12 . 24

(4.1)

Po pomno»eniu tych wektorów przez nasz¡ macierz szyfruj¡c¡ otrzymujemy

  14 , 4

  13 , 20

  22 , 0

  8 20

co po podstawieniu odpowiedników literowych daje kryptotekst

oenuwaiu.

Poniewa» w opisanej powy»ej metodzie szyfrowania wykorzystali±my digramy jako jednostki tekstu, powy»sza metoda szyfrowania nazywa si¦ 2

n-literowe nszyfr Hill'a.

szyfrem Hill'a. Je±li nasz tekst podzielimy na jednostki frowania u»yjemy macierzy

Uwagi.

z

Z26 .

n × n,

to otrzymamy

i do szy-

A wcale nie musi mie¢ wspóªczynników

1) Nasza macierz szyfruj¡ca

Wystarczy, »e po otrzymaniu wektorów zaszyfrowanego tekstu we¹-

miemy ich wspóªczynniki modulo 26. Macierz

A musi jednak by¢ odwracalna

modulo 26. 2) Zamiast mno»y¢ ka»dy wektor z (4.1) przez macierz

A

mo»emy od razu

pomno»y¢ A przez macierz

  20 17 22 12 10 24 0 24 ,,zªo»on¡ z tych wektorów. Otrzymana macierz b¦dzie macierz¡, której kolumnami s¡ wektory tekstu zaszyfrowanego.

Deszyfrowanie.

›eby rozszyfrowa¢ szyfr Hill'a, u»ywamy macierzy od-

wrotnej do macierzy szyfruj¡cej. Dokªadnie, je±li tekstu zaszyfrowanego, to

A−1 c

  c1 c= c2

jest digramem

jest odpowiadaj¡cym mu digramem tekstu

jawnego.

4.4.Przykªad.

Rozkodujemy 2szyfr Hilla

qilyfsnnpajguw

pomoc¡ macierzy

 A=

 9 15 . 19 2 45

zaszyfrowany za

Stosuj¡c opisany w 4.1 algorytm na znalezienie macierzy odwrotnej do

A

znajdujemy

−1

A Nast¦pnie mno»¡c

 =

 22 17 . 25 21

A−1 przez macierz digramów zaszyfrowanego tekstu otrzy-

mujemy

     22 17 16 11 5 13 15 9 20 20 0 0 13 18 14 8 = , 25 21 8 24 18 13 0 6 22 22 25 9 0 11 13 0 co daje nam tekst UWAZAJ NA SLONIA.

Šamanie.

Okazuje si¦, »e gdy znajdziemy

n

odpowiadaj¡cych sobie

gramów, to b¦dziemy te» w stanie znale¹¢ i macierz deszyfruj¡c¡.

n

By to

zrobi¢ mo»na wykorzysta¢ podobny do opisanego w 4.1 algorytm znajdywania macierzy odwrotnej. Opiszemy go, trzymaj¡c si¦ naszej dotychczasowej zasady, dla digramów. Dokªadnie, je±li mamy wektory tekstu jawnego   T p1 oraz c1 | pT1 , p2 oraz odpowiadaj¡ce im wektory c1 i c2 , to tworzymy macierz T c2 | pT2 której wierszami s¡ wspóªrz¦dne wektorów tekstu zaszyfrowanego, po których nast¦puj¡ wspóªrz¦dne odpowiadaj¡cych im wektorów tekstu jawnego. Nast¦pnie przeksztaªcamy otrzyman¡ macierz stosuj¡c elementarne operacje na wierszach tak, aby po lewej stronie otrzyma¢ macierz jednostkow¡.

To co

pojawi si¦ po prawej stronie jest transponowan¡ macierz¡ deszyfruj¡c¡.

4.5.Przykªad. Rozszyfrujemy wiadomo±¢ hmrzsewcrnwfnncc wiedz¡c, »e zaczyna si¦ ona od sªowa DEAR. Wiemy, »e wektorom tekstu zaszyfrowanego

  7 12

i

  17 25

odpowiadaj¡

    3 0 wektory oraz . Zastosujemy teraz opisany algorytm do znalezienia 4 17 −1 macierzy deszyfruj¡cej A .    T  7 12 | 3 4 c1 | pT1 tworzymy macierz , 17 25 | 0 17 cT2 | pT2   1 24 | 19 8 mno»ymy pierwszy −1 17 25 | 0 17 wiersz przez 15 = 7 ,   1 24 | 19 8 9 razy dodajemy 0 7 | 15 11 pierwszy wiersz do drugiego, 46



Zatem

 1 24 | 19 8 0 1 | 17 9   1 0 | 0 1 0 1 | 17 9   1 17 −1 A = . Aby 0 9

mno»ymy drugi −1 wiersz przez 7

= 15,

2 razy dodajemy drugi wiersz do pierwszego.

otrzyma¢ tekst jawny, mno»ymy otrzyman¡

macierz deszyfruj¡c¡ przez macierz zªo»on¡ z digramów tekstu zaszyfrowanego. Otrzymujemy



 7 17 18 22 17 22 13 2 12 25 4 2 13 5 13 2   3 0 8 4 4 3 0 10 = , 4 17 10 18 13 19 13 18 1 17 0 9



co nam daje tekst DEAR IKE SEND TANKS. Aby metoda ªamania szyfru podana w powy»szym przykªadzie zadziaªaªa, macierz zªo»ona z digramów tekstu zaszyfrowanego (lewa strona macierzy wyj±ciowej) musi by¢ macierz¡ odwracaln¡. Je±li tak nie jest, nasz algorytm si¦ w pewnym momencie urywa i po lewej stronie nie mo»emy otrzyma¢ macierzy jednostkowej.

Co wtedy mo»na zrobi¢?

Mo»emy szuka¢ innych

odpowiadaj¡cych sobie digramów.

Je±li takiej mo»liwo±ci nie ma, staramy −1 si¦ uzyska¢ jak najwi¦cej informacji na temat macierzy A i rozwa»y¢ kilka mo»liwo±ci.

4.6.Przykªad.

Przypu±¢my, »e przechwycili±my wiadomo±¢ wkncchssjh i

wiemy, »e pierwszym sªowem jest GIVE. Nasz¡ macierz¡ wyj±ciow¡ jest

 W =

 22 10 | 6 8 . 13 2 | 21 4

Nie mo»emy wykona¢ ju» pierwszego kroku algorytmu, poniewa» ani 22 ani 13 nie s¡ odwracalne modulo 26. Dlatego musimy zrezygnowa¢ ze zwykªej −1 drogi. By zebra¢ troch¦ informacji na temat A stosujemy nasz algorytm modulo 13, czyli najpierw redukujemy wyrazy

W

modulo 13,   a nast¦pnie

znajdujemy macierz deszyfruj¡c¡ modulo 13. Jest ni¡

−1

A

  2 4 = + 13A1 , 3 2 47

2 4 3 2

. Zatem

gdzie macierz

A1

jest macierz¡ zªo»on¡ z zer i jedynek (16 mo»liwo±ci). −1 Wiemy jednak, »e macierz A jest odwracalna, wi¦c jej wyznacznik musi

by¢ liczb¡ nieparzyst¡. To wyklucza 10 mo»liwo±ci. Nast¦pnie wykorzystujemy informacj¦, »e

    22 13 6 21 = , A 10 2 8 4     1 1 1 0 co nam pozostawia dwie mo»liwo±ci: oraz . 1 1 1 1 −1

Pierwsza macierz

daje nam wiadomo±¢ GIVE GHEMHP, co odrzucamy jako nieczyteln¡. Druga macierz daje nam wiadomo±¢ GIVE THEM UP, co prawdopodobnie jest tekstem jawnym. W naszych przykªadach wykorzystali±my tylko macierze

2×2 i przy ªama-

niu szyfrów zakªadali±my, »e nasz przeciwnik u»ywaª takich wªa±nie macierzy i alfabetu dwudziestosze±cioliterowego. Je»eli u»yte s¡ macierze wy»szych rozmiarów, ªamanie szyfrów staje si¦ trudniejsze, ale sama procedura ªamania jest identyczna. Zauwa»my, »e zbyt du»e rozmiary macierzy szyfruj¡cej te» nie s¡ wskazane, poniewa» pocz¡tek tekstu zaszyfrowanego staje si¦ wtedy szyfrem permutacyjnym, który mo»na zªama¢ stosuj¡c analiz¦ cz¦sto±ci wyst¦powania liter.

4.3

Aniczne przeksztaªcenia szyfruj¡ce

Ogólniejsz¡ form¡ szyfrowania wektora digramu (ngramu) jest pomno»enie go najpierw przez pewn¡ macierz Zatem, je±li przez

c

A,

a nast¦pnie dodanie staªego wektora

oznaczymy jednostk¦ tekstu zaszyfrowanego, a przez

jednostk¦ tekstu jawnego, to c = −1 0 wtedy posta¢ p = A c − b , gdzie

b. p

Ap + b. Przeksztaªcenie deszyfruj¡ce ma b0 = A−1 b. Zauwa»my, »e macierz A musi

by¢ macierz¡ odwracaln¡. ›eby zªama¢ szyfr aniczny, wystarczy zna¢ trzy odpowiadaj¡ce sobie digramy. Zaªó»my, »e digramom digramy

p1 , p2 i p3

c1 , c2 i c3

tekstu zaszyfrowanego odpowiadaj¡

tekstu jawnego. Mamy wtedy

p1 = A−1 c1 + b0 p2 = A−1 c2 + b0 p3 = A−1 c3 + b0 . 48

(4.2)

Odejmuj¡c trzecie równanie od pierwszego i drugiego. Otrzymujemy ukªad równa«

(p1 − p3 ) = A−1 (c1 − c3 ) (p2 − p3 ) = A−1 (c2 − c3 ). Teraz traktujemy

p1 − p3

oraz

p2 − p3

jako digramy tekstu jawnego, a

c1 − c3

i

c2 − c3 jako digramy kryptogramu i stosuj¡c algorytm opisany w 4.2 znajdu−1 jemy A . Kiedy ju» znamy t¦ macierz, z dowolnego równania ukªadu (4.2) 0 obliczamy b .

49

Rozdziaª 5 Pakowanie plecaka 5.1

Postawienie problemu

Jak zauwa»yli±my, szyfry oparte na rachunku macierzowym nie s¡ przera»aj¡co trudne do zªamania. Zdecydowanie trudniejszy jest kryptosystem oparty na nast¦puj¡cym problemie pakowania plecaka: Zaªó»my, »e musimy zabra¢ ze sob¡ na wycieczk¦ w góry wiele ,,potrzebnych przedmiotów. Jednak»e do dyspozycji mamy jedynie plecak o ograniczonej pojemno±ci

S.

Przedmioty maj¡ obj¦to±ci

zsumowaniu daj¡ obj¦to±¢ wi¦ksz¡ od gnowa¢.

S.

a1 , a2 , . . . , an ,

które po

Musimy zatem z czego± zrezy-

Jedynym kryterium jest tu tylko to, by plecak byª zapakowany

optymalnie, tj. bierzemy tylko te przedmioty, których obj¦to±ci daj¡ sum¦

S.

Co zatem wªo»y¢ do plecaka?

5.1 Przykªad. Wówczas mamy

(a1 , a2 , a3 , a4 , a5 ) = (2, 7, 8, 11, 12) oraz niech S = 21. a1 + a3 + a5 = S oraz a1 + a2 + a5 = S . Zatem zabieramy

Niech

ze sob¡ przedmioty pierwszy, trzeci i pi¡ty, lub pierwszy, drugi i szósty. Powy»szy problem mo»na sformuªowa¢ nast¦puj¡co: Dla danych liczb naturalnych

x2 , . . . , xn

a1 , a2 , . . . , an

oraz

S,

znale¹¢ taki ci¡g

x1 ,

zªo»ony z zer i jedynek, »eby zachodziªa równo±¢

a1 x1 + a2 x2 + · · · + an xn = S. Rozwa»aj¡c ci¡g z przykªadu 5.1 dostajemy dwa rozwi¡zania:

x1 = x3 = x5 = 1, x2 = x4 = 0

oraz

50

x1 = x2 = x5 = 1, x3 = x4 = 0.

(5.1)

x1 , x2 , . . . , xn ,

Aby znale¹¢ ci¡g kona¢ co najwy»ej

dla którego (5.1) zachodzi musimy wy-

n

dodawa«, jednak »eby rozwi¡za¢ problem pakowania 2n mo»liwo±ci. n Oznacza to, »e rozwi¡zanie powy»szego problemu zajmuje O(2 ) czasu. Naj-

plecaka metod¡ prób i bª¦dów, musimy sprawdzi¢ wszystkie n

szybszy znany algorytm dziaªa w czasie O(2 2 ). Je±li n = 100, to komputer 20 wykonuj¡cy 2 (procesor 1MHz) operacji na sekund¦ potrzebuje na rozwi¡30 zanie problemu pakowania plecaka czas rz¦du 2 , czyli okoªo miliard sekund albo ponad 30 lat! Pewne warto±ci liczb

a1 , a2 , . . . , an

zdecydowanie przy±pieszaj¡ rozwi¡-

zanie problemu pakowania plecaka. Na przykªad, je±li s¡ to pot¦gi dwójki, to rozwi¡zanie sprowadza si¦ do znalezienia rozwini¦cia liczby

S

w systemie

dwójkowym. Rozwini¦cie to znajdujemy w czasie logarytmicznym stosuj¡c tzw. ,,chciwy algorytm, który opiszemy poni»ej.

5.2

Szybko rosn¡ce ci¡gi

Ci¡g liczb naturalnych

a1 , a2 , . . . , an

j−1 X

ai < aj

nazywamy szybko rosn¡cym, je±li

dla

j ∈ {2, 3, . . . , n}.

i=1 Przykªadem szybko rosn¡cego ci¡gu jest 2, 3, 7, 14, 27. Niech

S = 37.

Wówczas ,,chciwy algorytm dziaªa nast¦puj¡co: Zawsze bierzemy najwi¦k-

x5 = 1, ale x4 = 0 poniewa» 27 + 14 > 37. x3 = 1 gdy» 27 + 7 < 37. Podobnie, x2 = 1 oraz x1 = 0. Ogólnie, je±li mamy szybko rosn¡cy ci¡g a1 , a2 , . . . , an , to wyznaczamy xn , xn−1 , . . . , x1 korzystaj¡c ze wzorów ( 1, je±li S ≥ an xn = 0, je±li S < an szy przedmiot jaki si¦ mie±ci.

Tak wi¦c

oraz

xj dla

( 1, = 0,

je±li je±li

P S − ni=j+1 xi ai ≥ aj P S − ni=j+1 xi ai < aj

j ∈ n − 1, n − 2, . . . , 1. Problem pakowania plecaka dla ci¡gów szybko rosn¡cych mo»e by¢ wi¦c

rozwi¡zany bardzo szybko. Poni»szy system kryptograczny MerklegoHell-

51

mana, który do roku 1982 byª uwa»any za najlepszy system o tzw. kluczu publicznym opiera si¦ na ,,zamianie problemu trudnego na problem ªatwy. Zaªó»my, »e nych.

Niech

m

a1 , a2 , . . . , an

jest szybko rosn¡cym ci¡giem liczb natural-

b¦dzie liczb¡ naturaln¡ wi¦ksz¡ od

2an . We¹my dowoln¡ m i utwórzmy ci¡g b1 ,

w wzgl¦dnie pierwsz¡ z b2 , . . . , bn bior¡c wa1 , wa2 , . . . , wan modulo m. Je»eli b1 , b2 , . . . , bn nie jest ci¡giem szybko rosn¡cym, to »eby rozwi¡za¢ Pn problem pakowania plecaka i=1 xi bi = S , nie mo»emy u»y¢ chciwego algo−1 rytmu. Jednak»e, je±li znamy w , to mo»emy rozwi¡za¢ problem pakowania liczb¦ caªkowit¡ nieujemn¡

plecaka

n X

xi ai = S0 ,

(5.2)

i=1 gdzie

S0 ≡ Sw−1 (mod m).

Kiedy mamy ju» rozwi¡zany problem (5.2), to

wiemy, »e

−1

w S=

n X

−1

w x i bi ≡

i=1

n X

xi ai

(mod m).

i=1

Powy»sz¡ procedur¦ opiszemy na przykªadzie.

5.2 Przykªad.

Rozwa»my szybko rosn¡cy ci¡g

(a1 , a2 , a3 , a4 , a5 ) = (3, 5, 9, 20, 44), Zauwa»my, »e

w−1 = 4.

Wówczas

m = 89

oraz

w = 67.

(b1 , b2 , b3 , b4 , b5 ) = (23, 68, 69, 5, 11).

›eby

rozwi¡za¢ problem pakowania plecaka

23x1 + 68x2 + 69x3 + 5x4 + 11x5 = 84, mno»ymy obie strony powy»szego równania przez 4 i redukujemy modulo 89 otrzymuj¡c

3x1 + 5x2 + 9x3 + 20x4 + 44x5 = 69. Teraz rozwi¡zujemy ªatwo powy»szy problem pakowania plecaka otrzymuj¡c

x1 = x3 = 0; x2 = x4 = x5 = 1. rozwi¡zanie 68 + 5 + 11 = 84. 52

Zatem nasz pierwotny problem ma

5.3

Kryptosystem oparty na problemie pakowania plecaka

System kryptograczny oparty na problemie pakowania plecaka dziaªa na-

a1 , a2 , . . . , an , liczb¦ m > 2an w wzgl¦dnie pierwsz¡ z m. Nast¦pnie obliczamy wyrazy ci¡gu . . . , bn , który jest kluczem szyfruj¡cym. W celu zaszyfrowania wia-

st¦puj¡co. Wybieramy szybko rosn¡cy ci¡g oraz liczb¦

b 1 , b2 ,

domo±ci, zamieniamy j¡ najpierw na ci¡g bitów, zgodnie z poni»sz¡ tabelk¡. Nast¦pnie otrzymany ci¡g zer i jedynek dzielimy na bloki dªugo±ci n. Dla Pn ka»dego bloku x1 , x2 , . . . , xn , obliczamy sum¦ i=1 xi bi i otrzymany ci¡g sum wysyªamy jako tekst zaszyfrowany, lub w omówiony wcze±niej z adresatem sposób, zamieniamy liczby na bloki liter i nast¦pnie wysyªamy.

litera

odpowiednik

litera

odpowiednik

A

00000

N

01101

B

00001

O

01110

C

00010

P

01111

D

00011

Q

10000

E

00100

R

10001

F

00101

S

10010

G

00110

T

10011

H

00111

U

10100

I

01000

V

10101

J

01001

W

10110

K

01010

X

10111

L

01011

Y

11000

M

01100

Z

11001

Dla przykªadu zaszyfrujemy wiadomo±¢ REPLY IMMEDIATELY u»ywaj¡c ci¡gu

C = (2002, 3337, 2503, 2170, 503, 172, 3347, 855).

Najpierw zamie-

niamy litery na bity i otrzymany ci¡g dzielimy na bloki 8-bitowe. Jak zwykle, ostatni blok uzupeªniamy dowolnie, aby tak jak pozostaªe miaª 8 bitów. 10001001

00011110

10111100

00100001

10001100

00100000

11010000

00001001

10010001

01111000

53

W kolejnym kroku obliczamy odpowiednie sumy wyrazów ci¡gu

C

otrzy-

muj¡c kryptogram

(3360, 3192, 7350, 3358, 2677, 7509, 1358, 5027, 8513). Na przykªad dodajemy 2002, 503 i 855 »eby otrzyma¢ 3360.

(5.3)

Je±li chcemy

otrzyma¢ kryptogram zapisany alfabetycznie, mo»emy zamieni¢ liczby z systemu dziesi¦tnego na pozycyjny o podstawie 26. Wtedy cyframi s¡ pozycje liter, wi¦c zamiast liczb dziesi¦tnych mamy bloki liter. Zauwa»my, »e suma 3 wszystkich elementów ci¡gu C , to 14889 i jest to liczba mniejsza od 26 . Mo»emy wi¦c ka»d¡ liczb¦ kryptogramu (5.3) zast¡pi¢ blokiem trzech liter. Na 2 przykªad, 7350 = 10 · 26 + 22 · 26 + 18, wi¦c zast¦pujemy j¡ blokiem KWS. Ostatecznie otrzymujemy EZGJEE KWSEZE DYZDSH LCVCAG HLJMPL. Zauwa»my teraz, »e klucz szyfruj¡cy mo»e by¢ podany do publicznej wiadomo±ci:

Mamy tekst jawny oraz kryptogram wªa±nie otrzymany, ale czy

jeste±my w stanie odczyta¢ inny kryptogram, np. NCZKQL KENNCO LWMKEN lub w postaci numerycznej,

(8865, 7187, 6877, 8854, 8020, 6877),

(5.4)

zaszyfrowany tym samym kluczem? W sumie, to nawet nie wiemy od razu, ile liter jest w tek±cie jawnym. Powy»sza idea prowadzi do powstania sieci korespondentów. Ka»dy u»ytkownik sieci ma swój prywatny klucz rozszyfrowuj¡cy, a klucze szyfruj¡ce mog¡ by¢ umieszczone w swoistej ,,ksi¡»ce telefonicznej, która jest dostarczona ka»demu u»ytkownikowi sieci. Ide¦ t¦ omówimy w nast¦pnym rozdziale, a teraz poka»emy jak mo»na ªatwo rozszyfrowa¢ szyfr (5.4). Do rozszyfrowania potrzebujemy oryginalnego ci¡gu szybko rosn¡cego, jakim jest

(2, 11, 14, 29, 58, 119, 241, 480), liczby

m = 3837

oraz

w−1 = 23.

Znajdujemy kolejno:

8865 · 23 ≡ 534 7187 · 23 ≡ 310 6877 · 23 ≡ 854 8854 · 23 ≡ 281 8020 · 23 ≡ 284 54

(mod (mod (mod (mod (mod

3837) 3837) 3837) 3837) 3837),

a nast¦pnie

534 = 0 · 2 + 1 · 11 + 1 · 14 + 1 · 29 + 0 · 58 + 0 · 119 + 0 · 241 + 1 · 480 310 = 0 · 2 + 1 · 11 + 0 · 14 + 0 · 29 + 1 · 58 + 0 · 119 + 1 · 241 + 0 · 480 854 = 0 · 2 + 0 · 11 + 1 · 14 + 0 · 29 + 0 · 58 + 1 · 119 + 1 · 241 + 1 · 480 281 = 0 · 2 + 1 · 11 + 0 · 14 + 1 · 29 + 0 · 58 + 0 · 119 + 1 · 241 + 0 · 480 284 = 0 · 2 + 0 · 11 + 1 · 14 + 1 · 29 + 0 · 58 + 0 · 119 + 1 · 241 + 0 · 480. Zatem wiadomo±¢ (5.4) w wersji binarnej, to

01110 00101 00101 00010 01110 10100 10001 10010 00100 111, co daje wiadomo±¢ jawn¡ OFF COURSE. Trzy ostatnie bity zostaªy dodane przy szyfrowaniu, aby dopeªni¢ blok. Zauwa»my, »e je»eli dªugo±¢ ci¡gu jest równa 5, to opisany szyfr jest bardziej skomplikowan¡ wersj¡ klasycznego szyfru permutacyjnego - litera alfabetu jest zast¡piona liczb¡ w sposób wzajemnie jednoznaczny.

W opi-

sanym przykªadzie liczb¡, lub blokiem trzech liter zast¦pujemy osiem bitów tekstu jawnego, co jest niepeªnym digramem. W ten sposób istotnie zmieniamy dotychczas poznane reguªy szyfrowania, gdzie dªugo±¢ szyfrowanego bloku liter byªa zawsze liczb¡ naturaln¡. W roku 1983 Shamir opublikowaª prac¦, która zdyskwalikowaªa system kryptograczny oparty na problemie pakowania plecaka jako system bezpieczny.

Otó» okazaªo si¦, »e szyfr ten mo»na zªama¢ w czasie wielo-

mianowym.

Po roku 1983 starano si¦ utrudni¢ szyfr, ale poniewa» ka»da

próba ko«czyªa si¦ szybko podobn¡ publikacj¡, szyfry oparte na problemie pakowania plecaka nie maj¡ dzi± du»ego powodzenia, mimo »e niektóre z nich w dalszym ci¡gu s¡ nie zªamane.

55

Rozdziaª 6 Systemy z publicznym kluczem Jak ju» zauwa»yli±my przy okazji omawiania systemu kryptogracznego opartego o problem pakowania plecaka, istniej¡ szyfry, których klucz szyfruj¡cy jest a» tak ró»ny od klucza rozszyfrowuj¡cego, »e ten pierwszy mo»na bez obawy poda¢ do publicznej wiadomo±ci. Tego rodzaju kryptosystem nazywamy szyfrem o kluczu publicznym.

Przy okazji takiego systemu mo»emy

mówi¢ o tworzeniu pewnej sieci u»ytkowników, z których ka»dy ma swój (jawny) klucz szyfruj¡cy oraz (tajny) rozszyfrowuj¡cy.

Gdyby±my chcieli

utworzy¢ tego rodzaju sie¢ maj¡c do dyspozycji jedynie szyfry klasyczne, to ka»dy z u»ytkowników musiaªby pami¦ta¢ klucze szyfruj¡ce wszystkich u»ytkowników oraz klucz rozszyfrowuj¡cy wiadomo±¢ od ka»dego u»ytkownika. Je»eli tych u»ytkowników byªoby

2(n − 1)

n,

to ka»dy z nich miaªby do zapami¦tania

kluczy, a w caªej sieci byªoby

2n(n − 1)

kluczy. Co gorsza, u»yt-

kownicy musieliby mie¢ do siebie peªne zaufanie, poniewa» ka»dy z kluczy szyfruj¡cych jest te» kluczem rozszyfrowuj¡cym. System kryptograczny z kluczem publicznym zdecydowanie ogranicza liczb¦ kluczy.

Dokªadnie, liczba kluczy dla caªej sieci, to tylko

n.

Ka»dy

z u»ytkowników pami¦ta wi¦c tylko jeden klucz  swój rozszyfrowuj¡cy, natomiast klucze szyfruj¡ce podane s¡ w swego rodzaju ksi¡»ce telefonicznej. Znajomo±¢ tych kluczy nie jest równoznaczna z dost¦pem do ka»dej wiadomo±ci, jaka si¦ pojawia w sieci. Systemy kryptograczne, w których znajomo±¢ klucza szyfruj¡cego oznacza praktycznie znajomo±¢ klucza rozszyfruj¡cego nazywamy systemami symetrycznymi. Pozostaªe systemy, czyli systemy o kluczu publicznym nazywamy systemami asymetrycznymi lub niesymetrycznymi.

56

6.1

Numeryczna funkcja jednokierunkowa

Aby zbudowa¢ omawiany wy»ej kryptosystem oraz sie¢ jego u»ytkowników, potrzebne nam b¦dzie poj¦cie funkcji jednokierunkowej.

Poj¦ciem funkcja

okre±la¢ tu b¦dziemy raczej schemat lub algorytm szyfrowania ni» funkcj¦ w ±cisªym znaczeniu.

W ka»dym razie jest to funkcja ªatwa do obliczenia w

jednym kierunku, ale bardzo trudna do obliczenia w kierunku przeciwnym. Czyli, znaj¡c argument bez trudu obliczamy warto±¢ funkcji, ale znajomo±¢ warto±ci funkcji nie pozwala nam obliczy¢ argumentu, dla którego ta warto±¢ jest przyjmowana. Na przykªad, aby obliczy¢ iloczyn dwóch liczb 500cyfrowych, nowoczesne komputery potrzebuj¡ kilku mikrosekund. Jednak»e, aby rozªo»y¢ na czynniki liczb¦ 1000 cyfrow¡, te same komputery potrzebuj¡ wieków. Idea funkcji jednokierunkowej pojawiªa si¦ w 1974, jednak wydaje si¦ »e jest ona nieco starsza.

W 1968 roku, kiedy rodziª si¦ system operacyjny

UNIX, potrzebny byª solidny system zabezpieczania informacji. Rozwi¡zano to w ten sposób, »e kiedy u»ytkownik po raz pierwszy wprowadza hasªo lub je zmienia, jest ono zaszyfrowane, a gdy hasªo to jest wprowadzane ponownie, system szyfruje je i porównuje z wcze±niej zaszyfrowan¡ wersj¡. Pierwszy szczegóªowy opis funkcji jednokierunkowej opublikowaª G. Purf : Fp → Fp , gdzie p = 264 − 59,

dy w 1974 roku. Opisana wtedy funkcja, to a funkcja jest okre±lona wzorem 24 +17

f (x) = x2 gdzie wspóªczynniki

ai

24 +3

+ a1 x 2

+ a2 x 3 + a3 x 2 + a4 x + a5 ,

byªy pewnymi liczbami 19cyfrowymi.

Zauwa»my, »e obliczenie funkcji odwrotnej do powy»szej nie jest niemo»liwe, tylko po prostu zajmuje du»o czasu.

Do tej pory nie przedstawiono

funkcji ,,czysto jednokierunkowej, tj. takiej, która po upªywie jakiego± czasu nie przestaªa by¢ jednokierunkow¡. Nie udowodniono nawet, »e taka funkcja istnieje lub te», »e nie isnieje. Ciekawy przykªad funkcji jednokierunkowej przedstawiª A. Salomaa tak»e w 1974 roku.

Jego pomysª polegaª na wykorzystaniu ksi¡»ki telefonicznej.

Numer telefonu oznaczaª pierwsz¡ liter¦ nazwiska abonenta. Bardzo ªatwo jest zakodowa¢ dan¡ liter¦ je±li mamy do dyspozycji spis telefonów. Jednak trudno jest przeszuka¢ caª¡ ksi¡»k¦ telefoniczn¡, aby odnale¹¢, na jak¡ liter¦ zaczyna si¦ nazwisko wªa±ciciela numeru telefonicznego. Przykªadowy szyfr,

57

to

914538761 914628841 914526316 914330826 914692564 914539302 914540189 Jak wida¢ z tego przykªadu, szyfr jest do±¢ dªugi. St¡d idea

6.2

funkcji skrótu.

Funkcje skrótu

Inaczej s¡ nazywane funkcjami haszuj¡cymi. szyfru.

Stosuje si¦ je do skrócenia 12 Chodzi o to, »e kryptogram jest zwykle dªugi (ok. 10 bitów w

przypadku podpisu elektronicznego).

Funkcja skrótu przeprowadza go na

znacznie krótszy tekst (np. do 1000 bitów). Jest to mo»liwe, poniewa» nie 12 wszystkie liczby 10 -bitowe s¡ wykorzystane przez dany system kryptograczny. Mo»liwe jest zatem utworzenie bijekcji.

6.3

poufno±¢ i autentyczno±¢.

Problem poufno±ci i autentyczno±ci pojawiª si¦ wrazem z systemami kryptogracznymi o kluczu publicznym. Poufno±¢ jest to wymóg polegaj¡cy na tym, aby przesyªana wiadomo±¢ mogªa by¢ odszyfrowana tylko przez adresata.

Autentyczno±¢ jest to wymóg, aby adresat miaª pewno±¢, »e osoba,

której podpis widnieje pod wiadomo±ci¡ jest nadawc¡.

Brak poufno±ci i autentyczno±ci.

Je±li mamy do czynienia z sieci¡ u»yt-

kowników, którzy posªuguj¡ si¦ klasycznym systemem szyfrowania, to ka»dy z nich zna klucz szyfruj¡cy (a zatem i rozszyfrowuj¡cy) ka»dego innego u»ytkownika sieci. Zatem nie mo»e tu by¢ mowy ani o poufno±ci ani o autentyczno±ci wysyªanych wiadomo±ci.

Poufno±¢ zachowana, ale brak autentyczno±ci.

Zaªó»my, »e Piotrek i

Agnieszka s¡ u»ytkownikami pewnej sieci. Wówczas oboje maj¡ swoje klucze publiczne opublikowane w informatorze dla u»ytkowników. Je±li Agnieszka chce wysªa¢ do Piotrka wiadomo±¢

m,

szyfruje j¡ najpierw kluczem publicz−1 nym Piotrka (powiedzmy FP ). Klucz rozszyfrowuj¡cy FP ma Piotrek i tylko on jest w stanie roszyfrowa¢ szyfr

FP (m).

Jednak»e Izka, mo»e podszy¢ si¦ 0 pod Agnieszk¦ i wysªa¢ do Piotrka swoj¡ wªasn¡ wiadomo±¢ m . Szyfruje 0 j¡ identycznie jak Agnieszka, tj. oblicza FP (m ). Oczywi±cie, Izka nawet je±li przechwyci kryptogram Agnieszki, nie jest w stanie go rozszyfrowa¢, ale Piotrek nigdy nie jest pewien, od kogo otrzymaª wiadomo±¢.

58

Mamy wi¦c

tu do czynienia z przypadkiem, kiedy kryptogram jest poufny (tzn.

tylko

adresat mo»e go rozszyfrowa¢), ale nie jest autentyczny (tzn. adresat nie wie na pewno, czy osoba podpisana jest nadawc¡).

Autentyczno±¢ zachowana, ale brak poufno±ci.

Rozwa»my spraw¦ za-

pªaty za zakupy za pomoc¡ karty kredytowej. Sama wiadomo±¢ (kwota transakcji, wykaz zakupionych towarów itp.) nie jest tu wa»na, wi¦c mo»e by¢ tekstem jewnym, ale z którego konta pójdzie przelew jest rzecz¡ do±¢ istotn¡. Obecnie, autentyczno±¢ karty jest sprawdzana przez porównanie podpisów klienta na karcie i zªo»onego w obecno±ci sprzedawcy lub za pomoc¡ czterocyfrowego numeru identykacyjnego (PINu). Czasami, je±li bank stwierdzi, »e klient, który zwykle nie wydawaª du»o, nagle zaczyna ,,szasta¢ pieni¦dzmi, odpowiedni urz¦dnik dzwoni do niego i zadaje mnóstwo pyta«, które maj¡ stwierdzi¢ autentyczno±¢.

Skªadania podpisu, wstukiwania PINu oraz roz-

mowy z urz¦dnikiem bankowym daªoby si¦ unikn¡¢ gdyby istniaªa w±ród wszystkich posiadaczy kart pewna sie¢ pozwalaj¡ca na wysªanie przy ka»dym u»yciu karty kredytowej swojego podpisu stwierdzaj¡cego autentyczno±¢. Tego rodzaju podpis jest u»ywany w tak zwanym ,,immobilizerze samochodowym. kluczyk.

Podpis jest elektronicznie zapisany w chipie wtopionym w

Tylko tym kluczykiem mo»na uruchomi¢ dany samochód.

Je»eli

kto± usiªuje wªo»y¢ do stacyjki inny klucz, odpowiedni chip zamontowany w stacyjce wykrywa niezgodno±¢ i uruchamia szereg czynno±ci, tj.

odcina

pr¡d od stacyjki oraz paliwo od silnika. Oczywi±cie, je±li niepo»¡dana osoba posi¡dzie wªa±ciwy kluczyk, nie b¦dzie miaªa ona trudno±ci z uruchomieniem samochodu.

Poufno±¢ i autentyczno±¢ zachowana. grupuje inwestorów i maklerów.

Wyobra¹my sobie sie¢, która

Inwestorzy obawiaj¡ si¦, »e ich maklerzy

mog¡ kupowa¢ akcje przyznaj¡c si¦ do ich zakupu dopiero gdy ich ceny rosn¡ (wtedy bior¡ prowizje), a je±li spadaj¡, twierdzi¢, »e dostali wyra¹ne polecenie zakupu akcji (na dowód pokazuj¡ zaszyfrowany tekst z poleceniem od inwestora.

Maklerzy natomiast, boj¡ si¦, »e je±li zakupi¡ walory tra-

c¡ce na warto±ci, »aden inwestor nie przyzna si¦ do wysªania kryptogramu z poleceniem zakupu. Potrzeba tu wi¦c zachowania zarówno poufno±ci jak i autentyczno±ci. Jest to zachowane, je±li wiadomo±¢ jest najpierw zaszyfrowana kluczem prywatnym nadawcy, a nast¦pnie kluczem publicznym odbiorcy.

59

6.4

Wymiana kluczy

Systemy z kluczem publicznym s¡ jeszcze mªode i istniej¡ spore problemy z zastosowaniem ich w praktyce.

Przede wszystkim, s¡ one znacznie wol-

niejsze od systemów klasycznych, tj.

liczba jednostek tekstu przesyªanych

w ci¡gu sekundy jest istotnie mniejsza dla systemów z kluczem publicznym. Jest to gªówny powód, dla którego systemy te nie zostaªy wprowadzone do powszechnago u»ytku. Jednak»e daj¡ one bardzo dobr¡ sposobno±¢ do przesyªania (tajnych) kluczy systemów klasycznych.

Klucze mo»na wymienia¢

wi¦c cz¦sto bez korzystania z pomocy kurierów. Wi¦ksze obj¦to±ciowo informacje wysyªane s¡ ju» z wykorzystaniem metod klasycznych.

6.5

2-1 funkcje jednokierunkowe

W poprzednich podrozdziaªach omawiali±my pewne funkcje jednokierunkowe, które ze wzgl¦du na zastosowanie musiaªy by¢ wzajemnie jednoznaczne lub przynajmniej ró»nowarto±ciowe.

Okazuje si¦, »e funkcje, które przyjmuj¡ 2 jedn¡ warto±¢ dla dwóch argumentów (podobnie jak x ) maj¡ równie ciekawe zastosowanie. Poka»emy, »e za ich pomoc¡ mo»na zagra¢ w orªa i reszk¦ przez telefon. Idea tej zabawy jest prosta i mo»na j¡ wytªumaczy¢ natychmiast. Przypu±¢my, »e Alicja oraz Stefan chc¡ rozstrzygn¡¢, do kogo ma nale»e¢ samochód. W tym celu mog¡ oni rzuci¢ monet¡ i zda¢ si¦ na los. Jednak»e dzieli ich pewna odlegªo±¢ przez co mog¡ si¦ porozumiewa¢ wyª¡cznie przez telefon.

Maj¡ te» do dyspozycji pewn¡ funkcj¦

muje dla dwóch argumentów

x1

oraz

x2 .

f,

która warto±¢

y

przyj-

Zakªadamy tutaj, »e znaj¡c pewien

argument, bez trudu mo»na obliczy¢ warto±¢ funkcji odpowiadaj¡c¡ temu argumentowi, jednak je±li znamy jak¡± warto±¢, nie mo»emy obliczy¢ bez dodatkowych informacji ani jednego argumentu, który odpowiada tej warto±ci. Zakªadamy, »e Stefan nie zna tych dodatkowych informacji, natomiast Alicja zna. Ich gra wygl¡da nast¦puj¡co: 1. Stefan wybiera losowo argument wysyªa Alicji (argument 2. Alicja po otrzymaniu

y

x

x

i oblicza warto±¢

y = f (x),

któr¡

pozostawia w tajemnicy).

i znaj¡c dodatkowe informacje, oblicza

x1

oraz

x2 . Rzut monet¡ polega teraz na losowym wybraniu jednego argumentu x1 lub x2 . Ten argument (zaªó»my, »e jest to x1 ) wysyªa ona Stefanowi. 60

3. Je±li

x = x1

Stefan przegrywa, i nie mo»e si¦ z tego wykr¦ci¢, poniewa»

je±li powie Alicji, »e wygraª, to ona za»¡da od niego drugiego elementu.

x 6= x1 , x = x2 .

4. Je»eli

wygrywa Stefan i na dowód wygranej przesyªa Alicji

Zauwa»my, »e dodatkowo, Alicja nie mo»e si¦ tu wykr¦ci¢ od wygranej. Natomiast Stefan, je±li koniecznie chce przegra¢, zaªatwia to bez problemu. Okazuje si¦, »e jest mo»liwe omini¦cie i tego mankamentu, ale odpowiedni rezultat (znany dobrze w pewnych kr¦gach) nie zostaª do tej pory opublikowany. W dalszej cz¦±ci wykªadu poznamy teorio-liczbowe i algebraiczne podstawy przytoczonych koncepcji kryptogracznych.

61

Rozdziaª 7 System RSA Przy poszukiwaniu funkcji jednokierunkowej

f,

któr¡ chcemy zastosowa¢ w

systemie o kluczu publicznym, chcemy u»y¢ pomysªu wzgl¦dnie prostego do −1 zastosowania. Z drugiej strony chcemy mie¢ pewno±¢, »e znalezienie f nie b¦dzie ªatwe.

Potrzebujemy wi¦c silnych dowodów empirycznych, których

mo»e dostarczy¢ nam historia poszukiwa« takiej funkcji.

7.1

Rozkªad liczb na czynniki

System RSA (Rivest  Shamir  Adleman), który tu przedstawimy, oparty jest na problemie znalezienia rozkªadu liczby zªo»onej na czynniki pierwsze. Funkcj¡ jednokierunkow¡ jest tu funkcja okre±lona w zbiorze par liczb pierwszych o warto±ciach w zbiorze liczb naturalnych. Na przykªad, pomno»enie dwóch dwu-cyfrowych liczb pierwszych, powiedzmy 23 i 47 nie powinno sprawi¢ nam wi¦kszego problemu. Natomiast pytanie o rozkªad liczby 2047 (wiemy, »e jest ona iloczynem dwóch dwu-cyfrowych liczb pierwszych) jest trudne. Przypomnijmy, »e

funkcj¡ Eulera ϕ(n) nazywamy moc zbioru liczb dodat-

n = pq , gdzie p oraz q s¡ ϕ(n) = n+1−p−q jest równowa»na znajomo±ci liczb p i q . Istotnie, je±li znamy n, p oraz q , bez problemu mo»emy obliczy¢ n + 1 − p − q . Je»eli natomiast znamy n oraz ϕ(n), to znamy te» n = pq oraz n + 1 − ϕ(n) = p + q i »eby obliczy¢ p oraz q , rozwi¡zujemy w miar¦ prosty ukªad równa« stopnia drugiego. W przypadku systemu RSA, kluczem jawnym jest (n, e), gdzie n jest ilo-

nich wzgl¦dnie pierwszych z

n.

Zauwa»my, »e je±li

liczbami pierwszymi, to znajomo±¢ warto±ci funkcji Eulera

62

e jest liczb¡ wzgl¦dnie pierwsz¡ z ϕ(n). Kluczem tajnym jest natomiast (n, d), gdzie d jest liczb¡ odwrotn¡ do e modulo ϕ(n). Znajomo±¢ rozkªadu liczby n oraz liczba ϕ(n) nie s¡ potrzebne do

czynem dwóch liczb pierwszych, a

szyfrowania ani do deszyfrowania, wi¦c lepiej o nich zapomnie¢. Najpopularniejsz¡ metod¡ ªamania RSA jest wªa±nie znajdywanie rozkªadu liczby

7.2

n.

Liczby wybrane losowo

Nast¦pnym krokiem jest tu wygenerowanie klucza. losowe liczby pierwsze

p

oraz

q

Potrzebna do tego s¡

i liczba losowa spomi¦dzy 1 i

φ(pq).

Gdy

mówimy o liczbie losowej, mamy na my±li liczb¦ wybran¡ przez pewien generator liczb losowych b¡d¹ pseudolosowych. Tym generatorem jest maszyna, która generuje ci¡g liczb tak, aby nikt nie mógª przewidzie¢ jaka jest nast¦pna liczba w ci¡gu, ani sam generator nie byª w stanie powtórzy¢ wygenerowanego wcze±niej ci¡gu.

Nie zale»y nam tutaj, aby wykorzysta¢ najwi¦ksze

znane liczby pierwsze, poniewa» te s¡ szybko znalezione przez postronnego intruza. Aby otrzyma¢ losow¡ liczb¦ pierwsz¡, najpierw generujemy liczb¦

m

(im wi¦ksz¡ tym lepiej). Je±li oka»e si¦ ona liczb¡ parzyst¡ zast¡pimy j¡

m + 1. Nast¦pnie zastosujemy odpowiednie testy pierwszo±ci, aby zobaczy¢, czy m jest pierwsza. Je±li nie, zast¦pujemy j¡ przez m + 2, m + 4 itd., przez

a» znajdziemy w ko«cu liczb¦ pierwsz¡. Poniewa» prawdopodobie«stwo zna-

m wynosi 1/ ln m, ln m liczb tramy na

lezienia liczby pierwszej w pobli»u losowo wybranej liczby mo»emy si¦ spodziewa¢, »e po przetestowaniu okoªo liczb¦ pierwsz¡. pierwsza z

Podobnie szukamy liczby losowej

e,

która jest wzgl¦dnie

φ(n).

Wspomniane testy pierwszo±ci opieraj¡ si¦ najcz¦±ciej na

dzeniu Fermata

oraz na

liczbach pseudopierwszych.

7.1 Twierdzenie. (Maªe Twierdzenie oraz a - p, to ap−1 ≡ 1 (mod p).

Fermata)

Maªym Twier-

Je±li p jest liczb¡ pierwsz¡

Liczb¡ pseudopierwsz¡ o podstawie a nazywamy tak¡ liczb¦ zªo»on¡ n, an−1 ≡ 1 (mod n). W przeciwie«stwie do liczb pierwszych, liczby

dla której

pseudopierwsze s¡ znacznie trudniejsze do znalezienia.

Najmniejsz¡ liczb¡

pseudopierwsz¡ o podstawie 2 jest 341, a o podstawie 3, 91.

63

7.3

Zasada dziaªania systemu RSA p oraz q , oraz liczb¦ losow¡ e, ϕ(pq). Niech n = pq , e < φ(n) (mo»na wzi¡¢ d = e−1 (mod ϕ(n)). Kluczem szyfruj¡cym jest

Ka»dy u»ytkownik wybiera dwie liczby pierwsze która jest wzgl¦dnie pierwsza z

liczb¦ e modulo φ(n)) oraz KE = (n, e). Mo»na go poda¢ do publicznej wiadomo±ci. Natomiast kluczem rozszyfrowuj¡cym jest KD = (n, d). Ten klucz lepiej jest zachowa¢ w tajemnicy tak jak liczby p, q oraz ϕ(n). Przeksztaªceniem szyfruj¡cym jest e funkcja f : Zn → Zn okre±lona wzorem f (P ) ≡ P (mod n). Przeksztaª−1 ceniem deszyfruj¡cym jest funkcja f odwrotna do f i okre±lona wzorem −1 d f (C) ≡ C (mod n). Pozostaje jeszcze wyja±ni¢, jakie jednostki tekstu b¦dziemy u»ywa¢. Chodzi tu przede wszystkim o to, aby ka»dy u»ytkownik systemu u»ywaª tych samych jednostek.

Zaªó»my wi¦c, »e teksty jawne i zaszyfrowane b¦d¡ za-

pisane za pomoc¡ tego samego alfabetu licz¡cego N symboli. Wybieramy k l liczby k i l tak, aby N < n < N . Jako jednostki tekstu jawnego we¹miemy bloki po

k

liter, które b¦dziemy traktowali jako liczby

o podstawie

N.

k cyfrowe

w systemie

Podobnie, jednostkami zaszyfrowanymi b¦d¡ bloki po

l

liter.

Zatem ka»dy blok tekstu zaszyfrowanego ma przypisan¡ warto±¢ liczbow¡ l mi¦dzy 0 i N − 1.

7.2 Przykªad.

Przyjmiemy

N = 26, k = 3

i

l = 4.

Zatem jednostki

tekstu jawnego s¡ trigramami, a jednostki tekstu zaszyfrowanego  tetragramami.

Chcemy przesªa¢ wiadomo±¢ TAK do u»ytkownika

klucz szyfruj¡cy

A,

który ma

(46927, 39423).

W tym celu szukamy najpierw odpowied2 nika liczbowego sªowa TAK. Jest to 19 · 26 + 0 · 26 + 10 = 12854. Na39423 st¦pnie obliczamy 12854 mod 46927 otrzymuj¡c w wyniku 14251 = 3 2 0 · 26 + 21 · 26 + 2 · 26 + 3, a to daje nam kryptotekst Tym samym kluczem zaszyfrowano inny tekst uzyskuj¡c kryptogram

avbc. bc.

Czy jeste± w

stanie odtworzy¢ tekst jawny? Adresat ma swój klucz rozszyfrowuj¡cy (46927, 26767), który pozwala mu 26767 obliczy¢ 14251 mod 46927 = 12854, a to mu daje sªowo TAK. U»ytkownik systemu RSA z powy»szego przykªadu wygenerowaª swoje klucze u»ywaj¡c liczb pierwszych 281 i 167. Oczywi±cie u»yli±my tutaj bardziej ,,wyobra»alne liczby ni» to si¦ zwykle stosuje. Normalnie, liczby k i l s¡ k tak dobrane, aby N miaªo nie mniej ni» 200 cyfr dziesi¦tnych. ›eby podnie±¢ du»¡ liczb¦ do du»ej pot¦gi stosujemy algorytm iterowanego podnoszenia do 3 kwadratu. Zajmuje on, O(log n) operacji na bitach.

64

7.4

Wpadka systemowa wspólny moduª

Przypu±¢my, »e dwóch u»ytkowników u»ywa tego samego moduªu maj¡ oni klucze (publiczne) postaci

(n, e1 )

oraz

(n, e2 ).

n,

tzn.

Je±li ta sama wia-

domo±¢ jest wysªana do obu u»ytkowników, to mo»na j¡ rozszyfrowa¢ bez znajomo±ci klucza rozszyfruj¡cego pod warunkiem, »e e1 oraz e2 s¡ wzgl¦de e nie pierwsze. Dokªadnie, je±li znamy m 1 modn oraz m 2 modn oraz zachodzi NWD

(e1 , e2 ) = 1,

to istniej¡ liczby caªkowite

x, y

takie, »e

e1 x + e2 y = 1.

Zatem

(me1 )x (me2 )y = me1 x+e2 y modn = m. Dla przykªadu przypu±¢my, »e

n = 5038301, e1 = 787, e2 = 6785.

jawny dzielimy tu na trigramy, które przechodz¡ w 5gramy.

Tekst

Zaªó»my, »e

przechwycili±my teksty HOTIT oraz EOXNS. U»ywaj¡c algorytmu Euklidesa dostajemy

888e1 − 103e2 = 1.

przechwycone 5gramy odpowiadaj¡ liczbom

3457967 oraz 2089872. Obliczamy zatem

3457967888 · 2089872−103 mod 5038301 = 4458054 · 999321 mod 5038301 = 11502, a to daje wiadomo±¢ jawn¡

7.5

Wpadka systemowa niski wykªadnik

Zaªó»my, »e

k

u»ytkowników posiada w kluczu ten sam wykªadnik, który

jest mniejszy od gdzie

rak.

e < k.

k,

tj.

ich klucze publiczne to

Przypu±¢my, »e do wszystkich

k

(n1 , e), n2 , e), . . . , (nk , e),

u»ytkowników zostaªa wysªana

ta sama wiadomo±¢ m. Zatem do itego u»ytkownika dociera wiadomo±¢ yi = me mod ni . Poniewa» m < ni oraz e < k , wi¦c me < n1 n2 . . . nk . U»ywaj¡c chi«skiego twierdzenia o resztach rozwi¡zujemy ukªad kongruencji

Y ≡ yi

(mod ni )

gdzie

1 ≤ i ≤ k.

Na podstawie tego» twierdzenia istnieje dokªadnie jedno rozwi¡zanie modulo

n1 n2 . . . nk

takiego ukªadu kongruencji je±li liczby n1 , n2 , . . . , nk s¡ wzgl¦dnie e pierwsze. W tym wypadku mamy m = Y i »eby obliczy¢ m wystarczy wzi¡¢ zwykªy pierwiastek stopnia

e

z

Y. 65

Rozwa»my dla przykªadu

e=3

oraz

n1 = 2881, n2 = 2867, n3 = 3127.

Szyfrujemy tu digramy tekstu, a tekst zaszyfrowany skªada si¦ z trigramów. Przypu±¢my, »e przechwycili±my wiadomo±ci BZG, BGX oraz CDZ wysªane do naszych trzech u»ytkowników.

Wiadomo±ciom tym odpowiadaj¡ liczby

1332, 855 oraz 1455. Wiemy te», »e wszystkie trzy kryptogramy to jest ta sama wiadomo±¢ jawna.

U»ywaj¡c chi«skiego twierdzenia o resztach, ro-

zwi¡zujemy ukªad kongruencji

Y ≡ 1332

(mod 2881) Y ≡ 855

otrzymuj¡c

Y = m3 = 211708736.

(mod 2867) Y ≡ 1455

(mod 3127)

Pierwiastek sze±cienny z tej ostatniej

liczby wynosi 596, czyli tekstem jawnym jest

66

wy.

Rozdziaª 8 Teorio-liczbowe podstawy RSA 8.1

Systemy pozycyjne

Stosowany powszechnie system zapisu liczb nazywamy systemem pozycyjnym, poniewa» znaczenie cyfry zale»y od pozycji, na której si¦ owa cyfra znajduje. Poza tym, nasz system liczenia nazywamy dziesi¦tnym, poniewa» mamy dokªadnie 10 cyfr. Liczba cyfr w systemie pozycyjnym zale»y od podstawy.

Dokªadnie, dowoln¡ liczb¦ caªkowit¡ nieujemn¡

podstawie

b≥2

n

zapisujemy przy

w postaci

(dk−1 dk−2 . . . d1 d0 )b ,

(8.1)

dk−1 , dk−2 , . . . , d1 , d0 s¡ liczbami caªkowitymi nieujemnymi wi¦kszymi od b − 1 nazywanymi cyframi. Zapis (8.1) oznacza, »e gdzie

oraz nie-

n = dk−1 bk−1 + · · · + d1 b + d0 . Je»eli

n

jest liczb¡ ujemn¡ to wyra»enie po prawej stronie równo±ci (8.2)

zacz¦liby±my od znaku liczb¡

(8.2)

k -cyfrow¡

−.

Je»eli

dk−1

n jest b = 10 to

nie jest zerem, to mówimy, »e

w systemie pozycyjnym o podstawie

b.

Je»eli

nawiasy w (8.1) opuszczamy, gdy» wtedy mamy do czynienia ze zwykªym dziesi¦tnym systemem pozycyjnym. Podobnie opu±cimy nawiasy gdy wybór podstawy jasno wynika z kontekstu. liczby

n

przy podstawie

Je»eli

b > 10,

Zapis (8.2) nazywamy rozwini¦ciem

b.

to pisownia niektórych cyfr jest uci¡»liwa (wymaga do-

datkowych nawiasów) lub niejasna:

(101)b 67

mo»na rozumie¢ na dwa sposoby.

Dlatego dla oznaczenia cyfr 10, 11, 12,

...

u»ywamy liter:

A, B , C , . . .

Oczy-

wi±cie mo»na u»ywa¢ liter lub innych znaków dla oznaczenia wszystkich cyfr. Na przykªad dla podstawy 26, która jest u»ywana w kryptograi, cyframi s¡ po prostu litery alfabetu ªaci«skiego. Cz¦sto zdarza si¦, »e trzeba przej±¢ od jednej podstawy systemu pozycyjnego do drugiej.

Zwykle jest to przej±cie do podstawy 10 lub od pod-

stawy 10. Przechodzenie do podstawy 10 polega na obliczeniu wyra»enia po prawej stronie (8.2). Gorzej jest przej±¢ od podstawy 10 do innej podstawy. Najbardziej naturalnym sposobem jest sekwencyjne dzielenie z reszt¡, które zademonstrujemy na przykªadzie.

8.1 Przykªad.

Zapiszemy liczb¦ 346 w systemie trójkowym, czyli przy pod-

346 = 115·3+1. 346 = 38 · 32 + 1 · 3 + 1.

stawie 3. Dzielimy 346 na 3 otrzymuj¡c 115, reszta 1. Zatem Teraz dzielimy 115 na 3 otrzymuj¡c 38, reszta 1. St¡d Kontynuuj¡c ten proces otrzymamy

346 = 35 + 34 + 2 · 32 + 31 + 1, czyli

346 = (110211)3 . b1 6= 10 do podstawy b2 6= 10, to mo»na

Je»eli przechodzimy od podstawy

tu przechodzi¢ po±rednio przez podstaw¦ 10. Czasem jednak bardziej efek-

b1

tywne jest zapisanie

i cyfr w systemie o podstawie

pogrupowanie. Je»eli dodatkowo

b1

jest pot¦g¡

b2 ,

b2

oraz odpowiednie

to sposób ten jest bardzo

szybki.

Przykªady 8.2.

(548)16 w systemie dwójkowym. 2 1 · 2 + 1, 4 = 1 · 22 oraz 8 = 1 · 23 , mamy Zapiszemy

Poniewa»

16 = 24 , 5 =

(548)16 = 5 · 162 + 4 · 16 + 8 = 1 · 210 + 1 · 28 + 1 · 26 + 1 · 23 = (10101001000)2 .

8.3.

Zapiszemy n = (212021)3 w systemie o podstawie 9. Grupujemy cyfry 2 po 2 (bo 9 = 3 ) zaczynaj¡c od prawej strony: 21, 20, 21. (Je±li ,,nie starcza cyfr na ostatni¡ grup¦, dodajemy z przodu odpowiedni¡ liczb¦ zer. Poniewa»

(21)3 = 2 · 3 + 1 = 7,

a

(20)3 = 2 · 3 = 6,

wi¦c

n = (767)9 .

Dziaªania arytmetyczne na liczbach w systemie o podstawie bez anga»owania w to podstawy 10.

b wykonujemy

Dodawanie, odejmowanie i mno»enie

pisemne przeprowadzamy tak jak dotychczas, przy czym przy ,,po»yczaniu bierzemy nie 10 lecz

b. 68

Tak»e uªamki mo»na rozwija¢ przy dowolnej podstawie. Maj¡ one (sko«czon¡ lub niesko«czon¡ posta¢

(dk−1 dk−2 . . . d1 d0 , d−1 d−2 . . . )b .

Warto tu za-

uwa»y¢, »e przy zmianie podstawy, mog¡ te» zmieni¢ si¦ uªamki okresowe. Na przykªad

8.2

0, 33333 · · · = (0, 1)3 ,

a

0, 5 = (0, 11111 . . . )3 .

Iterowane podnoszenie do kwadratu

Podnoszenie du»ych liczb do pot¦g o jeszcze wi¦kszych wykªadnikach nie jest obliczeniowo trudne, ale gromadzenie du»ych liczb zabiera du»o pami¦ci. W przypadku zastosowa« w systemach kryptogracznych, mamy zawsze do czynienia z dziaªaniami w sko«czonych strukturach algebraicznych. To znacznie zmniejsza rz¡d liczb, którymi operujemy. Dla przykªadu obliczymy poteg¦ 348171 ( mod 1019). W tym celu zapisujemy 7 +25 +23 +2+1

348171 = 3482  = 



2 !2  2 2  2
2 3482 · 348 · 348  · 348 · 348.

Nasze pot¦gowanie sprowadza si¦ zatem do podnoszenia do kwadratu lub mno»enia przez 348, przy czym za ka»dym razem wynik redukujemy modulo 1019. Po wykonaniu oblicze« otrzymujemy 127.

8.3

Twierdzenie Eulera i Maªe Twierdzenie Fermata

Twierdzenia te mog¡ znacznie uªatwi¢ pot¦gowanie liczb w arytmetyce modularnej. Uzasadniaj¡ te», dlaczego zaszyfrowany za pomoc¡ RSA szyfr mo»na te» rozszyfrowa¢.

8.4 Twierdzenie.

(Eulera) Je»eli NWD(a,

m) = 1,

to

aϕ(m) ≡ 1 (mod m).

Twierdzenie to mo»e by¢ udowodnione za pomoc¡ elementarnych metod, my jednak u»yjemy tu nieco ,,ci¦»szej broni, a mianowicie znanego z teorii grup faktu, »e dowolny element grupy podniesiony do pot¦gi, której wykªadnikiem jest rz¡d grupy daje element neutralny.

69

Dowód. ϕ(m)

W grupie elementów odwracalnych pier±cienia

elementów. Jest to wi¦c grupa sko«czona rz¦du

jej element podniesiony do pot¦gi

ϕ(m)

Zm mamy dokªadnie ϕ(m). Zatem dowolny

daje element neutralny, czyli 1.

Šatwym wnioskiem z twierdzenia Eulera jest nast¦puj¡ce twierdzenie.

8.5 Twierdzenie. oraz

p - a,

(Maªe twierdzenie Fermata) Je»eli

ap−1 ≡ 1 (mod p). bp ≡ b (mod p).

to

kongruencja

p

jest liczb¡ pierwsz¡

Dla dowolnej liczby caªkowitej

b

zachodzi



Nieco trudniejszy jest dowód poni»szego wniosku.

8.6 Wniosek. Je±li p - a i n ≡ m (mod p − 1), to an ≡ am (mod p). Dowód. sa¢

c

Przypu±¢my, »e

n = m + c(p − 1) dla ap−1

razy kongruencj¦

p − 1|n − m, wi¦c mo»emy napipewnej liczby naturalnej c. Mno»ymy przez siebie ≡ 1 (mod p) aby otrzyma¢ ac(p−1) ≡ 1 (mod p).

n > m.

Poniewa»

›eby otrzyma¢ tez¦ wystarczy pomno»y¢ stronami ostatni¡ kongruencj¦ przez m m oczywiste przystawanie a ≡ a (mod p). Podobnie uzasadniamy nast¦pny wniosek.

8.7 Wniosek. Je»eli liczby a oraz m s¡ wzgl¦dnie pierwsze oraz zachodzi kongruencja r ≡ s (mod ϕ(m)), to ar ≡ as (mod m).  Podamy teraz dwa przykªady zastosowa« powy»szych wniosków.

Przykªady. 8.7. Znajdziemy ostatni¡ cyfr¦ liczby 2100000000000 Wykªadnik 100000000000

2

w systemie o podstawie 7.

100000000000 daje reszt¦ 4 przy dzieleniu przez 7 − 1 = 6. ≡ 24 (mod 7). Poniewa» 24 = 16, a 16 ≡ 2 (mod 7),

St¡d wi¦c

szukan¡ ostatni¡ cyfr¡ jest 2.

8.8.

Znajdziemy ostatni¡ cyfr¦

ϕ(16) = 7,

a

1234 ≡ 2 (mod

31234

w ukªadzie szestnastkowym. Mamy tu 7). Zatem 31234 ≡ 9 (mod 16) i ostatni¡ cyfr¡

jest 9. Okazuje si¦, »e najni»sza pot¦ga sza ni»

ϕ(m).

a w Twierdzeniu Eulera jest cz¦sto mniej-

Wynika to z faktu, »e rz¡d grupy nie jest, ogólnie rzecz bior¡c,

rz¦dem elementu, ani nawet wykªadnikiem grupy. Na przykªad ϕ(105) = 48, 12 ale dla a wzgl¦dnie pierwszych ze 105 mamy a ≡ 1 (mod 105). Poni»sze twierdzenie pokazuje jak ulepszy¢ pot¦g¦

70

a.

8.8 Twierdzenie. Przypu±¢my, »e m = pα1 1 pα2 2 . . . pαk k , gdzie wszystkie pi s¡ ró»ne i pαi i ||m. Niech n = NWW(ϕ (pα1 1 ) , ϕ (pα2 2 ) , . . . , ϕ (pαk k )). Wtedy mamy an ≡ 1 (mod m) dla ka»dego a wzgl¦dnie pierwszego z m. Dowód.

αi

aϕ(pi

Z twierdzenia Eulera wynika

)

≡ 1 (mod pαi i )

dla ka»dego i ∈ {1, 2, . . . , k}. Mno»¡c t¦ kongruencj¦ stronami przez siebie n/pαi i razy αi n otrzymujemy a ≡ 1 (mod pi ) dla ka»dego i. St¡d bezpo±rednio wynika, »e αi n n dla dowolnego i mamy pi |a − 1. Zatem i m|a − 1, a to nam daje tez¦. Wracaj¡c do uwagi przed powy»szym twierdzeniem, zauwa»my, »e

105 =

3 · 5 · 7 i 12 = NWW(ϕ(3), ϕ(5), ϕ(7)) = NWW(2, 4, 6).

8.9 Przykªad.

21000000 modulo 77. Mamy tu 77 = 7·11, ϕ(7) = 6, ϕ(11) = 10, NWW(6, 10) = 30. St¡d 230 ≡ 1 (mod 77). Nast¦pnie mamy 1000000 = 30 · 33333 + 10, wi¦c 21000000 ≡ 210 ≡ 23 (mod 77).

8.4

Obliczymy

liczby pseudo-pierwsze

Potrzebne s¡ du»e liczb pierwsze i to takie, których generalnie nikt nie zna. Pojawia si¦ zatem potrzeba szybkich algorytmów szukaj¡cych liczb pierwszych lub testuj¡cych liczby na pierwszo±¢.

Wi¦kszo±¢, a w zasadzie pra-

wie wszystkie takie algorytmy s¡ algorytmami probabilistycznymi, w których prawdopodobie«stwo, »e otrzymamy liczb¦ pierwsz¡ nie jest równe 1. Mo»e si¦ wi¦c zdarzy¢, »e otrzymana liczba jest zªo»ona. Warunki równowa»ne pierwszo±ci liczby, jak np. które mówi, »e liczba

−1 (mod n),

n

Twierdzenie Wilsona,

jest pierwsza wtedy i tylko wtedy, gdy

n jest liczb¡ (n−1)! (nawet

nie s¡ dobrym kryterium  ªatwiej sprawdzi¢ czy

pierwsz¡ dziel¡c j¡ przez kolejne liczby nieparzyste ni» oblicza¢ modulo

(n − 1)! ≡

n).

Dobrym testem pierwszo±ci jest Maªe Twierdzenie Fermata (8.5).

Pro-

blem w tym, i» nie jest to warunek równowa»ny pierwszo±ci. Na przykªad, 2340 ≡ 1 (mod 341), chocia» 341 nie jest liczb¡ pierwsz¡. Nasze rozwa»ania oprzemy jednak na tym twierdzeniu, badaj¡c które liczby zªo»one speªniaj¡ tez¦ Maªego Twierdzenia Fermata. Liczb¦ zªo»on¡

n

pseudopierwsz¡ ), je±li

nazywamy

pseudopierwsz¡ przy podstawie a

an−1 ≡ 1

(mod n). 71

(lub

a-

(8.3)

Zauwa»my, »e je»eli NWD(a, n−1 to warunek 8.3 jest równowa»ny kongruencji a ≡ 1 (mod n). Piszemy wówczas w skrócie:

n jest psp(a).

Zauwa»my, »e liczba 341 jest 2-pseudopierwsza.

n) = 1,

Jak pokazaª Sarrus w

1819 roku, jest to najmniejsza liczba pseudopierwsza przy podstawie 2. Kolejne odkrywane liczby psp(2) byªy nieparzyste. Dopiero w 1950, D.H. Lehmer odkryª pierwsz¡ parzyst¡ liczb¦ 2-pseudopierwsz¡. Najmniejsz¡ liczb¡ 3-pseudopierwsz¡ jest natomiast 91. Okazuje si¦, ze liczb pseudopierwszych (o dowolnej podstawie) jest niesko«czenie wiele, ale s¡ one rozmieszczone do±¢ »zadko". Na przykªad mamy tylko 5597 liczb psp(2) mniejszych od miliarda. Tymczasem liczb pierwszych

n mniejsza od miliarda speªnia warunek 8.3 dla a = 2, to prawdopodobie«stwo, »e n jest pierwsza jest wi¦ksze od 0, 9999. Liczba, która jest psp(2) nie musi by¢ w tym przedziale jest ponad 50 milionów. Zatem, je»eli pewna liczba

jednocze±nie psp(3). Okazuje si¦, »e liczb mniejszych od miliarda, które s¡ pseudopierwsze jednocze±nie przy podstawie 2, 3 i 5 jest tylko 685. Mo»na wi¦c zrobi¢ caªkiem por¦czn¡ tablic¦ tych liczb, która pozwoli nam odrzuca¢ liczby zªo»one speªniaj¡ce tez¦ Maªego Twierdzenia Fermata. Wydaje si¦ wi¦c, »e bior¡c odpowiednio du»o pocz¡tkowych liczb pierwszych jako podstawy dojdziemy w ko«cu do sytuacji, w której nie znajdziemy liczb pseudopierwszych mniejszych od okre±lonej liczby. Jak odkryª w 1912 roku R.D. Carmichael, jest to sytuacja niemo»liwa. Liczb¦ zªo»on¡ wamy

liczb¡ Carmichaela,

pierwszej z

n.

je±li

n

jest psp(a) dla ka»dej liczby

a

n

nazy-

wzgl¦dnie

Jak pokazaª w roku 1992 A. Granville, liczb Carmichaela jest

niesko«czenie wiele. Podamy przykªad jednej z nich.

8.10 Przykªad.

Mamy

561 = 3 · 11 · 17.

Niech

a

b¦dzie liczb¡ wzgl¦dnie

pierwsz¡ z 561. Korzystaj¡c z Maªego Twierdzenia Fermata, otrzymujemy:

a2 ≡ 1 (mod 3) a10 ≡ 1 (mod 11) a16 ≡ 1 (mod 17)

a560 ≡ (a2 )280 ≡ 1 a560 ≡ (a10 )56 ≡ 1 a560 ≡ (a16 )35 ≡ 1

⇒ ⇒ ⇒

Dalej, z chi«skiego twierdzenia o resztach, dostajemy

(mod 3) (mod 11) (mod 17).

a560 ≡ 1 (mod 561),

co oznacza, »e 561 jest liczb¡ Carmichaela. Do±¢ du»y post¦p w skuteczno±ci testów opartych na liczbach pseudopierwszych daje nast¦puj¡ca obserwacja. Je±li liczba p jest pierwsza, to kon2 gruencja x ≡ 1 (mod p) ma dokªadnie 2 rozwi¡zania: 1 i −1 (twierdzenie 2 Lagrange'a). Z tego samego twierdzenia wynika, »e je»eli x ≡ 1 (mod n)

72

ma wi¦cej ni» dwa rozwi¡zania, to testowania liczby

n

n musi by¢ liczb¡ zªo»on¡.

na pierwszo±¢ sprowadza si¦ do szukania nietrywialnych

pierwiastków stopnia 2 z jedynki modulo ste

Zatem problem

n.

Z oczywistych wzgl¦dów, b¦dziemy dalej rozwa»a¢ tylko liczby nieparzyn. Skoro n jest nieparzysta, to n − 1 mo»na zapisa¢ w postaci 2r s, gdzie s

r > 0. pseudopierwsza przy podstawie a. jest liczb¡ nieparzyst¡ oraz

Przypu±¢my, »e liczba n jest pierwsza lub n−1 Wówczas a ≡ 1 (mod n). Rozwa»amy

po kolei liczby

x1 = a2s mod n,

x0 = as mod n,

...

rs

x r = a2

mod n.

Zauwa»my, »e aby obliczy¢ warto±ci wszystkich wyrazów ci¡gu

X = (x0 , x1 , . . . , xr ), wystarczy obliczy¢ redukowa¢ modulo

x0 , a nast¦pnie podnosi¢ j¡ sukcesywnie do n otrzymuj¡c kolejne wyrazy. Zauwa»my, »e

kwadratu i mamy tu 3

mo»liwo±ci: 1. istnieje

0 < t ≤ r,

takie »e

xt = 1

2. istnieje

0 < t ≤ r,

takie »e

xt = 1, xt−1 6= ±1,

3.

oraz

xt−1 = −1,

x0 = 1.

Oczywi±cie, je±li

xt = 1,

to dla

i>t

mamy

xi = 1.

Zatem je±li w pewnym

X pojawi si¦ 1, to wszystkie nast¦pne wyrazy te» n−1 s¡ równe 1. Poniewa» xr = a , wi¦c xr = 1. Je±li speªniony jest warunek 2, 2 to oznacza to, »e kongruencja x ≡ 1 (mod n) ma wi¦cej ni» dwa pierwiastki (bo 1, −1 oraz xt−1 ), czyli n na pewno nie jest liczb¡ pierwsz¡. Pozostaªe momencie konstrukcji ci¡gu

przypadki daj¡ nast¦puj¡c¡ denicj¦.

n jest nieparzyst¡ psp(a). Mówimy, »e n jest liczb¡ silnie pseudopierwsz¡, przy podstawie a lub spsp(a), je»eli as ≡ 1 (mod n) lub 2t s istnieje 0 < t < r , takie »e a ≡ −1 (mod n), gdzie n − 1 = 2r s, s jest liczb¡ nieparzyst¡ oraz r > 0. W terminologii ci¡gu X mamy, »e n jest spsp(a), je±li jest speªniony Przypu±¢my, »e

warunek 1 lub 3.

8.11 Przykªad. 2

2 · 85

Rozwa»my najmniejsz¡ psp(2), czyli 341.

Mamy

340 =

x0 = 32, x1 =1. Oznacza to, »e 341 nie jest spsp(2). Co wi¦x0 jest nietrywialnym pierwiastkiem kwadratowym z 1 modulo 341, wi¦c mo»emy znale¹¢ rozkªad 341 obliczaj¡c NWD(32 − 1, 341) = 31 oraz NWD(32 + 1, 341) = 11. oraz

cej, poniewa»

73

8.12 Przykªad.

n = 561.

Jest to liczba Carmichaela, czyli jest ona 4 pseudopierwsza przy ka»dej podstawie. Mamy 560 = 2 · 35 i niech a = 2. Wówczas

x0 = 263, x1 = 166, x2 = 67, x3 = 1.

8.13 Przykªad. jest

We¹my

Zatem 561 nie jest spsp(2).

Najmniejsz¡ liczb¡ silnie pseudopierwsz¡ przy podstawie 2

2047 = 23 · 89. Poka»emy, »e jest to istotnie liczba silnie pseudopierwsza. 2046 = 2 · 1023 oraz x0 = 1.

Mamy

Wszystkich liczb psp(2) mniejszych od dziesi¦ciu miliardów jest 14884, ale liczb spsp(2) jest ju» tylko 3291. Najmniejsz¡ liczb¡ b¦d¡c¡ jednocze±nie spsp(2) oraz spsp(3) jest

1373653 = 829 · 1657.

Nie ma liczby mniejszej

od dziesi¦ciu miliardów, która by byªa jednocze±nie spsp(a) dla

13.

2 ≤ a ≤

Mimo to liczb silnie pseudopierwszych przy dowolnej podstawie jest

niesko«czenie wiele, co udowodnili C. Pomerance, J.L. Selfridge i S.S. Wagsta w 1980 roku.

8.5

Chi«skie twierdzenie o resztach

Twierdzenie, które tu przedstawimy zostaªo odkryte i wykorzystywane w ±redniowiecznych Chinach. Przyczyn¡ tego odkrycia byªy trudno±ci z mno»eniem i dodawaniem du»ych liczb  ªatwiej jest nauczy¢ si¦ na pami¦¢ kilku kombinacji, ni» wykonywa¢ dziaªania arytmetyczne w pami¦ci.

A dokªad-

nie, kiedy dowódca chciaª zliczy¢ swoje wojsko, kazaª ustawi¢ si¦ »oªnierzom w dwu-szeregu, nast¦pnie w trzy-szeregu, potem w pi¦cio-szeregu itd. Liczba ,,niesparowanych »oªnierzy w ka»dym z tych ustawie« (czyli reszty z dzielenia ogólnej liczby »oªnierzy przez 2, 3, 5, . . . )

dawaªy liczb¦ wszystkich

»oªnierzy. ›eby skonkretyzowa¢ nasze my±lenie, rozwa»my nast¦puj¡cy przykªad.

8.14 Przykªad.

Po ustawieniu caªego wojska w 3-, 5- i 7-szeregu dosta-

li±my, odpowiednio 2, 1 oraz 6 niesparowanych »oªnierzy. Jaka jest liczebno±¢ oddziaªu, je»eli wiadomo, »e »oªnierzy jest mniej ni» 100? Formalizuj¡c zadanie, niech lenia

x

x b¦dzie liczb¡ »oªnierzy.

Zatem reszty z dzie-

przez 3, 5 oraz 7, to 2, 1 i 6. St¡d

x≡2 x≡1 x≡6

(mod 3) (mod 5) (mod 7) 74

(8.4) (8.5) (8.6)

Powy»szy system trzech kongruencji rozwi¡»emy korzystaj¡c z dowodu nast¦pnego twierdzenia.

8.15 Twierdzenie (Chi«skie twierdzenie o resztach). Przypu±¢my, »e m1 , m2 , . . . , mr s¡ parami wzgl¦dnie pierwsze. Wówczas ukªad kongruencji x ≡ a1 x ≡ a2

.. .

(mod m1 ) (mod m2 ) (8.7)

x ≡ ar

(mod mr )

ma jednoznaczne rozwi¡zanie modulo m1 m2 . . . mr . Dowód. xi =

Wprowad¹my nast¦puj¡ce oznaczenia: M = m1 m2 −1 Mi mod mi dla 1 ≤ i ≤ r. Rozwa»my teraz liczb¦

. . . mr , Mi =

M , mi

x = a1 M1 x1 + a2 M2 x2 + · · · + ar Mr xr . j 6= i zachodzi Mj ≡ 0 (mod xi ), wi¦c x ≡ ai Mi xi (mod mi ) dla ka»dego i. Ale Mi xi ≡ 1 (mod mi ), wi¦c x ≡ ai (mod mi ) dla 1 ≤ i ≤ r . Pozostaje jeszcze udowodni¢ jednoznaczno±¢. Niech x1 oraz x2 b¦d¡ dwoma rozwi¡zaniami ukªadu (8.7). Zatem x1 ≡ x2 (mod mi ) dla 1 ≤ i ≤ r . St¡d mi | x1 − x2 , a poniewa» m1 , m2 , . . . mr s¡ wzgl¦dnie pierwsze, wi¦c M | x1 − x2 . Zatem dwa rozwi¡zania (8.7) ró»ni¡ si¦ o wielokrotno±¢ M i ukªad ten ma jednoznaczne modulo M rozwi¡zanie. Poniewa» dla

W odró»nieniu od dowodów wielu innych podobnych twierdze«, dowód chi«skiego twierdzenia o resztach daje wzór na rozwi¡zanie ukªadu kongruencji.

8.16 Przykªad.

Rozwa»my ukªad kongruencji z przykªadu 8.14. Stosuj¡c

oznaczenia dowodu twierdzenia 8.15, mamy

M = 105

i

mi

ai

Mi

xi

1

3

2

35

2

2

5

1

21

1

3

7

6

15

1

75

oraz

St¡d

x ≡ 2 · 35 · 2 + 1 · 21 · 1 + 6 · 15 · 1 ≡ 140 + 21 + 90 ≡ 251 ≡ 41

(mod (mod (mod (mod

105) 105) 105) 105).

Zaªo»enie o kopierwszo±ci moduªów jest do±¢ istotnym ograniczeniem. Na przykªad, ukªadu kongruencji

x≡3 x≡7

(mod 8) (mod 12)

(8.8)

nie mo»na rozwi¡za¢ stosuj¡c twierdzenia 8.15, poniewa» 8 oraz 12 nie s¡ wzgl¦dnie pierwsze. Nie oznacza to jednak, »e ukªad ten nie ma rozwi¡zania. Rozwi¡»emy go w nast¦pnym przykªadzie.

8.17 Przykªad.

Aby rozwi¡za¢ ukªad kongruencji 8.8 zapiszmy najpierw

12 = 4 · 3 i rozbijmy drug¡ kongruencj¦ ukªadu na dwie kongruencje x ≡ 7 (mod 4) i x ≡ 7 (mod 3). Mamy zatem ukªad trzech kongruencji x≡3 x≡3 x≡1

(mod 8) (mod 4) (mod 3).

(8.9)

Ale rozwi¡zanie pierwszej kongruencji ukªadu (8.9) speªnia te» drug¡ kongruencj¦, wi¦c druga kongruencja jest niepotrzebna. Otrzymujemy wi¦c równowa»ny (8.8) ukªad kongruencji

x≡3 x≡1

(mod 8) (mod 3).

Ostatni ukªad rozwi¡zujemy stosuj¡c chi«skie twierdzenie o resztach (8.15), otrzymuj¡c

x ≡ 19 (mod 24).

76

8.6

Kongruencje stopnia 2

Rozwa»my nast¦puj¡cy przykªad

8.18 Przykªad.

Chcemy znale¹¢ wszystkie liczby n, których ostatnie trzy 2 cyfry s¡ takie same jak w n . Od razu zauwa»amy, »e takimi liczbami s¡ 0 oraz 1.

Po chwili zauwa»amy te», »e 1000, 1001 i wszystkie liczby ko«-

cz¡ce si¦ na 000 lub 001 maj¡ wymagan¡ wªasno±¢.

Dochodzimy wi¦c do

kongruencji

n ≡ n2

(mod 1000),

(8.10)

której rozwi¡zanie da nam wszystkie szukane liczby. Jest to kongruencja 2 drugiego stopnia (f (n) = n − n ). Jej rozwi¡zaniami (modulo 1000) s¡ 0, 1, 376, 625. Gdyby w przykªadzie 8.18 moduª byª maªy, to kongruencj¦ (8.10) rozwi¡zaliby±my podstawiaj¡c za od

m.

n

wszystkie nieujemne liczby caªkowite mniejsze

Metoda ta nie pracuje, je±li

m

jest du»¡ liczb¡.

W rozdziale tym

poka»emy, »e kongruencje o moduªach zªo»onych mo»na zredukowa¢ do kongruencji o moduªach pierwszych.

To pozwoli nam rozwi¡za¢ niektóre kon-

gruencje. Nie b¦dziemy tu wprowadza¢ skomplikowanej teorii pozwalaj¡cej nam rozwi¡za¢ ka»d¡ kongruencj¦.

Pierwiastkiem modulo m wielomianu f (x) o wspóªczynnikach caªkowitych

f (r) ≡ 0 (mod m). Je±li r jest pierwiastkiem 0 0 wielomianu f (x) modulo m oraz r ≡ r (mod m), to f (r) ≡ f (r ) (mod m), 0 czyli r te» jest pierwiastkiem wielomianu f (x) modulo m. Nasze rozwa»ania na temat pierwiastków b¦dziemy ogranicza¢ do Zm i mówi¡c ,,rozwi¡zanie mamy na my±li rozwi¡zanie modulo m. nazywamy tak¡ liczb¦

r,

»e

Przykªady. 8.19.

podstawiaj¡c za

8.20.

x2 + 2

Wielomian

x

Wielomian

nie ma pierwiastków modulo 7.

Sprawdzamy to

kolejne liczby 0, 1, 2, 3, 4, 5, 6.

x2 − 2

ma w

Zauwa»my, »e wielomian

Z7

f (x)

dokªadnie dwa pierwiastki: 3 i 4. z przykªadu 8.18 byª stopnia drugiego i

miaª dokªadnie 4 pierwiastki modulo 1000.

Jak wiadomo, w ciaªach licz-

bowych, wielomian nie mo»e mie¢ wi¦cej pierwiastków ni» jego stopie«. W szczególno±ci, wielomian stopnia 2 nie mo»e mie¢ trzech pierwiastków.

77

8.21.

Wielomian

x2 − 1

ma w

Z12

cztery pierwiastki: 1, 5, 7 oraz 11.

m na moduªy b¦m = pα1 1 pα2 2 . . . pαk k , to αi kongruencja f (x) ≡ 0 (mod m) implikuje k kongruencji f (x) ≡ 0 (mod pi ), gdzie 1 ≤ i ≤ k . Odwrotna implikacja tak»e zachodzi, poniewa» pot¦gi Rozwa»ymy teraz metod¦ redukcji moduªu zªo»onego

d¡ce pot¦gami liczb pierwszych z rozkªadu

m.

Je±li

ró»nych liczb pierwszych s¡ kopierwsze.

8.22 Przykªad. Rozwa»my kongruencj¦ x2 ≡ 1 (mod 105).

Poniewa» 105 = 3 · 5 · 7, wi¦c nasza kongruencja jest równowa»na ukªadowi trzech kongruencji

x2 ≡ 1 x2 ≡ 1 x2 ≡ 1

(mod 3) (mod 5) (mod 7).

Ka»d¡ z powy»szych kongruencji rozwi¡zujemy podstawiaj¡c kolejne liczby i otrzymujemy w trzech przypadkach po dwa rozwi¡zania: 1 i 2 modulo 3, 1 i 4 modulo 5 oraz 1 i 6 modulo 7.

Dowolna kombinacja tych rozwi¡za«

daje rozwi¡zanie modulo 105. Oznaczmy przez r pierwiastek wielomianu x2 − 1 modulo 105. r jest jednym z rozwi¡za« o±miu poni»szych ukªadów kongruencji.

r ≡ 1 (mod 3) r ≡ 1 (mod 5) r ≡ 1 (mod 7),

r ≡ 2 (mod 3) r ≡ 1 (mod 5) r ≡ 1 (mod 7),

r ≡ 2 (mod 3) r ≡ 4 (mod 5) r ≡ 1 (mod 7), r ≡ 2 (mod 3) r ≡ 1 (mod 5) r ≡ 6 (mod 7),

r≡1 r≡4 r≡6

r ≡ 1 (mod 3) r ≡ 4 (mod 5) r ≡ 1 (mod 7),

r ≡ 1 (mod 3) r ≡ 1 (mod 5) r ≡ 6 (mod 7), (mod 3) (mod 5) (mod 7),

r≡2 r≡4 r≡6

(mod 3) (mod 5) (mod 7).

Rozwi¡zaniami (modulo 105) tych ukªadów kongruencji s¡, kolejno, 1, 71, 64, 29, 76, 41, 34 i 104.

78

Wracaj¡c do przykªadu 8.18, kongruencja 8.10 jest równowa»na ukªadowi kongruencji

n ≡ n2 n ≡ n2

(mod 23 ) (mod 53 ).

(8.11)

Pierwsz¡ kongruencj¦ z (8.11) mo»emy jeszcze rozwi¡za¢ podstawiaj¡c kolejne liczby od 0 do 7. Przy drugiej kongruencji metoda ta zawodzi ze wzgl¦du na zbyt wiele liczb. Zastosujemy wi¦c inn¡ metod¦. Poniewa» kongruencj¦ n ≡ n2 (mod 5) speªniaj¡ dwie liczby (modulo 5) 0 oraz 1, wi¦c kongruencj¦

n ≡ n2

(mod 52 )

(8.12)

0 + 5k1 oraz 1 + 5l1 . Podstawiamy te liczby do (8.12) 5k1 ≡ 0 (mod 52 ) oraz 5l1 ≡ 10l1 (mod 52 ). St¡d kongruencje k1 ≡ 0 (mod 5) i l1 ≡ 2l1 (mod 5), które daj¡ k1 = 0 oraz l1 = 0. Mamy

speªniaj¡ liczby postaci otrzymuj¡c

zatem 2 rozwi¡zania modulo 25: 0 oraz 1. Rozwi¡zaniami modulo 125 drugiej 2 2 kongruencji z (8.12) s¡ liczby postaci 5 k2 oraz 1 + 5 l2 . Wykonuj¡c podobne obliczenia jak powy»ej dostajemy dwa rozwi¡zania: 0 i 1.

Aby rozwi¡za¢

zadanie postawione w przykªadzie 8.18, wystarczy rozwi¡za¢ cztery ukªady kongruencji

(mod 23 ) (mod 53 ),

r ≡ e1 r ≡ e2 gdzie za

e1

oraz

e2

podstawiamy 0 lub 1. Cztery szukane rozwi¡zania to 0,

1, 376 i 625.

8.23 Przykªad.

Rozwi¡»emy kongruencj¦

x2 + 4x + 2 ≡ 0

(mod 49).

(8.13)

f (x) = x2 +4x+2 oraz 49 = 72 . Zaczynamy wi¦c od kongruencji x + 4x + 2 ≡ 0 (mod 7), dla której znajdujemy rozwi¡zanie podstawiaj¡c po kolei wszystkie liczby od 0 do 6. Znajdujemy dwa pierwiastki x1 = 1 oraz x2 = 2. Zatem pierwiastki kongruencji (8.13), to 1 + 7k oraz 2 + 7l . Mamy tutaj 2

Podstawiajac je do (8.13) otrzymujemy

42k ≡ −7

(mod 49)

oraz

7l ≡ −14

(mod 49),

co redukuje si¦ do

6k ≡ −1

(mod 7)

i ostatecznie daje rozwi¡zania

oraz

x1 = 8

oraz

79

l ≡ −2 x2 = 37.

(mod 7)

8.24 Przykªad.

Rozwi¡»emy kongruencj¦

x2 + x + 7 ≡ 0

(mod 9).

(8.14)

x2 + x + 7 ≡ 0 (mod 3) jest x0 = 1. Ale zapisuj¡c x = 1 + 3k i podstawiaj¡c do (8.14), otrzymujemy 0 ≡ 0 (mod 9), wi¦c x1 = 1 + 3 · 0 = 1, x2 = 1 + 3 · 1 = 4 oraz x3 = 1 + 3 · 2 = 7 s¡ Jedynym pierwiastkiem kongruencji

pierwiastkami (8.14).

8.25 Przykªad.

Poszukamy pierwiastków kwadratowych z 1 modulo 16. f (x) = x2 − 1. Modulo 8, ma on 4 pierwiastki:

Rozwa»ymy wi¦c wielomian

x01 = 1, x02 = 3, x03 = 5 i x04 = 7. Dalej szukamy ki , gdzie xi = x0i + 8ki f (xi ) ≡ 0 (mod 16) dla i ∈ {1, 2, 3, 4}. Otrzymujemy sprzeczno±¢ dla k2 i k3 oraz 0 ≡ 0 (mod 16) dla k1 i k2 . Zatem pierwiastkami kwadratowymi oraz

z jedynki modulo 16 s¡ 1, 9, 7 i 15. Zako«czymy ten podrozdziaª jeszcze jednym przykªadem, który ma du»e znaczenie w kryptograi.

8.26 Przykªad.

p i q s¡ ró»nymi liczbami pierwszymi oraz x ≡ 1 (mod n) ma dokªadnie 4 rozwi¡zania, 2 2 poniewa» ka»da z kongruencji x ≡ 1 (mod p) oraz x ≡ 1 (mod q) ma dokªadnie dwa rozwi¡zania. Rozwi¡zania ±1 nazywamy trywialnymi. Je±li x jest nietrywialnym rozwi¡zaniem, to NWD(x − 1, n) oraz NWD(x + 1, n) s¡ 2 liczbami p i q . Zatem je±li znamy nietrywialne rozwi¡zanie kongruencji x ≡ 1 (mod n), to znamy te» rozkªad liczby n. Odwrotnie, je±li znamy rozkªad 2 liczby n, czyli p oraz q , to rozwi¡zania kongruencji x ≡ 1 (mod n) mo»emy

n = pq .

Przypu±¢my, »e 2

Wówczas kongruencja

otrzyma¢ korzystaj¡c z chi«skiego twierdzenia o resztach dla czterech ukªadów kongruencji:

x ≡ e1 dla

x ≡ e2

(mod p),

(mod q)

e1 , e2 ∈ {0, 1}.

8.7

Gra w orªa i reszk¦ przez telefon

Wykorzystamy tu stosunkowo maªe liczby, »eby caªy czas kontrolowa¢ przebieg gry. Niech wi¦c

n = 341 = 11 · 31.

Powró¢my do Alicji i Stefana, którzy

si¦ ju» pojawili na tym wykªadzie. Liczby 11 oraz 31 s¡ znane Alicji, a Stefan zna tylko ich iloczyn, tj. 341.

80

2 1. Stefan wybiera losowo liczb¦ 0 < x ≤ 340 i oblicza warto±¢ x . Zaªó»my, 2 »e x = 134, wi¦c x = 224. Alicja otrzymuje tylko liczb¦ 224.

y = 224 oraz wiedz¡c, »e 341 = 11 · 31, oblicza 2 cztery pierwiastki równania x = 224 modulo 341. Robi to w nast¦pu2 j¡cy sposób. Poniewa» x ≡ 224 (mod 341), wi¦c

2. Alicja po otrzymaniu

x2 ≡ 224 ≡ 4 x2 ≡ 224 ≡ 7

(mod 11) (mod 31)

st¡d mamy jedn¡ z czterech mo»liwo±ci

x ≡ ± 2 (mod 11) x ≡ ± 10 (mod 31) Stosuj¡c oznaczenia z dowodu chi«skiego twierdzenia o resztach roz-

a1 = 2, m1 = 11, a2 = 10, m2 = 31, M = 341. Obliczamy teraz M1 = 31 oraz M2 = 11. Stosuj¡c algorytm Euklidesa lub w inny sposób obliczamy N1 = 6 i N2 = 17. wi¡zujemy powy»szy ukªad nast¦puj¡co:

Teraz ju» bez trudu otrzymujemy

x = 2 · 31 · 6 + 10 · 11 · 17 = 2242, co modulo 341 daje 196. Alicja mo»e t¦ liczb¦ potraktowa¢ jako swoj¡ szcz¦±liw¡ i wysªa¢ j¡ Stefanowi, lub te» obliczy¢ trzy pozostaªe liczby rozwi¡zuj¡c nast¦puj¡ce ukªady kongruencji

x ≡ −2 (mod 11); x ≡ 2 (mod 11); x ≡ −2 x ≡ 10 (mod 31); x ≡ −10 (mod 31); x ≡ −10 Wówczas do dyspozycji b¦dzie miaªa liczby i

−134,

196

oraz

134

(mod 11); (mod 31). (tak»e

−196

ale to si¦ nie liczy) i b¦dzie w prawdziwej rozterce decyduj¡c,

czy ma wysªa¢ 3. Je±li wysªaªa

x2 = 196,

x1 = 134

czy te»

x1 = 134.

Stefan ma pecha, poniewa» nie zna on liczby

196, której Alicja natychmiast za»¡da. 4. Je»eli jednak Alicja wysªaªa

x2 = 196,

wygrywa Stefan i na dowód

wygranej przesyªa Alicji liczb¦ 134. Zauwa»my, »e mo»emy tu zastosowa¢ ka»d¡ liczb¦ dwóch liczb pierwszych

p i q,

n, która jest iloczynem

przy czym je±li gramy faktycznie o samochód

81

to liczby te musz¡ by¢ na tyle du»e i tak dobrane, »eby nie mo»na byªo zbyt szybko znale¹¢ rozkªadu liczby

n.

Liczby

p = 11

oraz

q = 31

z powy»-

szego przykªadu mog¡ co najwy»ej sªu»y¢ do gry o rozbite lusterko boczne. Zauwa»my te», »e w punkcie 4, Stefan mo»e udowodni¢ swoj¡ wygran¡ znajduj¡c bez problemu rozkªad liczby

n,

poniewa» NWD(x1

od 1, czyli stanowi nietrywialny dzielnik liczby

82

n.

− x2 , n)

jest wi¦kszy

Rozdziaª 9 Zastosowania arytmetyki modulo m do rozkªadu liczb Najpopularniejsz¡ metod¡ ªamania szyfru RSA jest próba znalezienia klucza deszyfruj¡cego. Jest to równowa»ne znalezieniu rozkªadu liczby niki.

n

na czyn-

Zaproponujemy tu kilka metod opartych o Twierdzenie Eulera oraz

Maªe Twierdzenie Fermata.

9.1

Wzory skróconego mno»enia

Zaczniemy od nast¦puj¡cego prostego wniosku, który znamy z tzw. ,,wzorów skróconego mno»enia

9.1 Twierdzenie. Dla dowolnej liczby caªkowitej b i dowolnej liczby naturalnej n liczba bn − 1 jest podzielna przez b − 1. Iloraz jest równy bn−1 + bn−2 + · · · + b2 + b + 1.

Dowód.

Korzystamy ze znanej to»samo±ci

bn − 1 = (b − 1)(bn−1 + bn−2 + · · · + b2 + b + 1). Zamieniaj¡c

b

na

bm

otrzymujemy natychmiast nast¦puj¡cy wniosek.

9.2 Wniosek. Dla ka»dej liczby caªkowitej b i dowolnych liczb naturalnych n i m zachodzi równo±¢ bmn − 1 = (bm − 1)(bm(n−1) + bm(n−2) + · · · + b2m + bm + 1). 83

Jako przykªad zastosowania powy»szego wniosku zobaczmy, »e

235 − 1

dzieli si¦ przez 31 oraz przez 127. Ciekawszym spostrze»eniem jest tu fakt, n »e je±li 2 − 1 jest liczb¡ pierwsz¡, to n jest tak»e liczb¡ pierwsz¡. Liczby p zªo»one Mersenne'a (tzn. liczby postaci 2 − 1, gdzie p jest liczb¡ pierwsz¡) s¡ kontrprzykªadem na to, »e twierdzenie odwrotne nie zachodzi.

9.3 Twierdzenie. Niech liczba b b¦dzie wzgl¦dnie pierwsza z liczb¡ m i niech a i c b¦d¡ liczbami naturalnymi. Je±li ba ≡ 1 (mod m), b c ≡ 1 (mod m) oraz d = NWD(a, c), to bd ≡ 1 (mod m). Dowód.

d = ua+vc, gdzie u i v s¡ liczbami caªkowitymi. Poniewa» u, v jest dodatnia, a druga ujemna lub au równa 0. Zaªó»my, »e u > 0, v ≤ 0. Mamy b ≡ 1 (mod m) oraz bc(−v) ≡ 1 c(−v) −1 (mod m). Z drugiej kongruencji wynika, »e (b ) ≡ 1 (mod m). Mno»¡c au+vc stronami pierwsz¡ kongruencj¦ oraz t¦ ostatni¡, otrzymujemy b ≡ 1 (mod m), co dowodzi tez¦. aic

Zapiszmy

s¡ dodatnie, wi¦c jedna z liczb

9.4 Twierdzenie. Je±li p jest dzielnikiem pierwszym liczby bn − 1, to (i) dla pewnego dzielnika d < n liczby n mamy p | bd − 1, lub (ii) p ≡ 1 (mod n). Je±li p > 2 oraz liczba n jest nieparzysta, to wówczas w przypadku (ii) mamy p ≡ 1 (mod 2n). Dowód.

p | bn − 1, wi¦c p nie jest dzielnikiem b. Zatem w my±l p−1 maªego twierdzenia Fermata b ≡ 1 (mod p). Z poprzedniego twierdzenia d otrzymujemy b ≡ 1 (mod p), gdzie d = NWD(n, p − 1). Je»eli d < n, to p | bd − 1, czyli zachodzi (i). Je±li d = n, to d | p − 1, wi¦c mamy (ii). Je»eli p i n s¡ obie nieparzyste i n | p − 1, to tak»e 2 | p − 1 i p ≡ 1 (mod 2n). Poniewa»

Przykªady.

Je±li chcemy rozªo»y¢ na czynniki jak¡kolwiek liczb¦

dzamy po kolei czy liczby pierwsze mniejsze od

n

√ n

n to sprawn. Je±li

s¡ dzielnikami

jest du»a pojawiaj¡ si¦ tu przynajmniej dwa problemy. Po pierwsze liczb

pierwszych robi si¦ du»o, a po drugie rozpoznawanie liczb pierwszych powy»ej 100 staje si¦ kªopotliwe i cz¦sto wymaga iterowania algorytmu. Powy»sze twierdzenie znacznie zaw¦»a ilo±¢ dzielników pierwszych liczby

9.5. √

n.

2047 = 211 − 1 oraz p | 2047, to p ≡ 1 (mod 22)

Rozªó»my na czynniki liczb¦ 2047. Zauwa»my, »e

2047 < 46. Z twierdzenia 9.4 wynika, »e je±li gdy» p i 11 s¡ nieparzyste a jedynym wªa±ciwym dzielnikiem jedenastu jest 1.

Zatem je±li jaka± liczba pierwsza mniejsza od 46 dzieli 2047 to musi to by¢ 23. Po podzieleniu przekonujemy si¦, »e

2047 = 23 · 89. 84

9.6.

12 Rozªó»my na czynniki liczb¦ 3 − 1 = 531440. Z wniosku 9.2 wynika 1 2 3 4 6 natychmiast, »e 3 − 1, 3 − 1, 3 − 1, 3 − 1 oraz 3 − 1 dziel¡ 531440. Zatem 4 4 nasza liczba na pewno dzieli si¦ przez 2 , 5, (dzielniki 3 − 1), 13 (dzielnik 33 − 1) i 7 (dzielnik 33 + 1, bo 36 − 1 = (33 − 1)(33 + 1)). Po podzieleniu 4 otrzymujemy 531440 = 2 · 5 · 7 · 13 · 73. Poniewa» 73 jest liczb¡ pierwsz¡ otrzymali±my nasz rozkªad.

9.7.

34359738367 = 235 − 1. Po pierw5 7 sze, mamy natychmiast dzielniki pierwsze 2 − 1 = 31 i 2 − 1 = 127. Po podzieleniu otrzymujemy 34359738367 = 31 · 127 · 8727391. Liczba 8727391 Rozªó»my na czynniki pierwsze liczb¦

jest jednak zbyt du»a aby orzec, czy jest to liczba pierwsza, czy nie. Pierwiastek z tej liczby jest mniejszy od 2955, wi¦c w dalszym ci¡gu mamy wiele kªopotliwych dzielników pierwszych do sprawdzenia. Z Twierdzenia 9.4 wynika jednak, »e mamy do sprawdzenia tylko liczby pierwsze spo±ród 36, 71, 106, 141, i tak dalej a» do 2955. Od razu odrzucamy 36, a skoro 71 jest liczb¡ pierwsz¡, dzielimy i otrzymujemy

8727391 = 71 · 122921.

Pierwiastek z tej

ostatniej liczby wynosi ,,ju» tylko 351. Z naszego ci¡gu mo»liwych dzielników pierwszych wyszukujemy liczby 211 i 281 mniejsze od 351 i sprawdzamy, »e nie s¡ one dzielnikami 122921. Zatem 122921 jest liczb¡ pierwsz¡ i naszym

34359738367 = 31 · 71 · 127 · 122921.

rozkªadem na czynniki jest

Twierdzenie 9.4 oraz powy»sze przykªady pokazuj¡ dlaczego wszystkie ,,rekordowe liczby pierwsze s¡ liczbami Mersenne'a.

Przestaje te» dziwi¢

fakt, »e pod koniec lat siedemdziesi¡tych XX wieku rekord najwi¦kszej liczby 21701 pierwszej 2 − 1 nale»aª do uczniów liceum.

9.2

Metoda ρ rozkªadu na czynniki

Metoda rozkªadu liczby zªo»onej na czynniki, któr¡ teraz zaprezentujemy zostaªa przedstawiona przez J.M. Pollarda. Nazywana jest ona równie» metod¡ Monte Carlo. Mo»emy stosowa¢ j¡ do ka»dej liczby naturalnej i przy odpowiednim doborze parametrów jest ona szybsza ni» dzielenie przez kolejne liczby pierwsze mniejsze od

√

n. ρ

Pierwszy krok w metodzie

polega na wyborze ªatwo obliczalnej funk-

cji przeksztaªcaj¡cej zbiór

Zn

próbujemy wielomianów.

W drugim kroku wybieramy pewn¡ pocz¡tkow¡

warto±¢

x0 ,

w siebie.

Jak zwykle, w pierwszej kolejno±ci

a nast¦pnie obliczamy kolejne iteracje funkcji

x1 = f (x0 ),

x2 = f (x1 ), 85

x3 = f (x2 ),

f: ...

Po otrzymaniu pewnej liczby pocz¡tkowych wyrazów tak zdeniowanego ci¡gu, rozwa»amy ró»nice wyrazów tego ci¡gu w nadziei, »e pewna z tych ró»nic, powiedzmy

xi − xj ,

nie jest wzgl¦dnie pierwsza z

acja nast¡pi, to wówczas NWD(xi

− xj , n)

n.

Je±li taka sytu-

jest jednym z dzielników

n.

Powy»szy algorytm zilustrujemy na w miar¦ prostym przykªadzie. Niech 2 wi¦c n = 15857, f (x) = x + 1, x0 = 2. Obliczamy kolejne warto±ci xj otrzymuj¡c

x0 = 2, x1 = 5, x2 = 26, x3 = 677, x4 = 14334, x5 = 4408, x6 = 5640, x7 = 459, x8 = 4541. x0 od wszystkich pozostaªych i zauwa»amy, »e za ka»dym razem wychodzi i» liczby xj −x0 oraz 15857 s¡ wzgl¦dnie pierwsze. Nast¦pnie, poniewa» x0 − x1 ju» badali±my, wi¦c rozwa»amy ró»nice xj − x1 dla j > 1, a potem xj − x2 dla j > 2 itd. W ko«cu mamy NWD(x7 − x6 , 15857) = NWD(−5181, 15857) = 157. Zatem 15857 = 157 · 101. Je»eli chodzi o wielomian, który u»ywamy, to jest to, Nast¦pnie badamy kolejne ró»nice, tj. najpierw odejmujemy

niestety, kwestia wyczucia. Opisany algorytm mo»na nieco ulepszy¢, a mianowicie dla ka»dego indeksu

k

wystarczy obliczy¢ tylko jeden NWD. Aby opisa¢ to ulepszenie,

zauwa»my najpierw, »e je±li pewne indeksy

xk0 ≡ xj0 (mod r)

k0

j0 n,

speªniaj¡ kongruencj¦

r liczby to kongruencja ta jest k > k0 , j > j0 takich, »e k − j = k0 − j0 .

dla pewnego dzielnika

speªniona dla wszystkich indeksów

i

Wynika to z nast¦puj¡cej wªasno±ci kongruencji: je»eli a dokªadnie, je±li

xj0 +1 (mod r),

y ≡ z (mod m),

to

f (y) ≡ f (z) (mod m),

xk0 ≡ xj0 (mod r), to równie» xk0 +1 = f (xk0 ) ≡ f (xj0 ) = xk0 +2 ≡ xj0 +2 (mod r) itd.

wi¦c i

Opiszemy wi¦c wspomnian¡ modykacj¦. W dalszym ci¡gu obliczamy koxk . Zaªó»my, »e k jest liczb¡ (h+1)bitow¡, tj. 2h ≤ k < 2h+1 . h Za j we¹my 2 − 1, czyli najwi¦ksz¡ liczb¦ hbitow¡. Porównujemy wtedy

lejne warto±ci

xk

z

xj .

Tak zmodykowany algorytm pozwala nam tylko raz obliczy¢ war-

to±¢ NWD(xk

− xj , n)

dla ka»dego

k.

W powy»szym przykªadzie

ograniczamy si¦ wi¦c do nast¦puj¡cych oblicze«:

x1 − x0 = 3, x2 − x1 = 21, x3 − x1 = 672,

(3, 15857) = 1 NWD(21, 15857) = 1 NWD(672, 15857) = 1 NWD

86

n = 157857

x4 − x3 x5 − x3 x6 − x3 x7 − x3 x8 − x7

= 3657, = 3731, = 4963, = −218, = 4082,

(3657, NWD(3731, NWD(4963, NWD(−218, NWD(4082, NWD

15857) = 1 15857) = 1 15857) = 1 15857) = 1 15857) = 157.

i w tym momencie algorytm staje si¦ szybszy od metody dziele« przez kolejne liczby pierwsze.

9.3

Metoda faktoryzacji Fermata

Opisane dotychczas metody rozkªadu du»ych liczb na czynniki dziaªaªy b¡d¹ z pewnym prawdopodobie«stwem, b¡d¹ te» tylko dla bardzo szczególnych liczb.

Okazuje si¦ jednak, »e jak dot¡d, nie znaleziono skutecznej metody

rozkªadu, która zawsze zadziaªa i nie wymaga m¦cz¡cych oblicze«. Omówimy teraz metod¦, która dziaªa skutecznie dla liczb, których dzielniki s¡ zbyt blisko siebie. Opiera si¦ ona na nast¦puj¡cym twierdzeniu.

9.8 Twierdzenie. Niech n b¦dzie dodatni¡ liczb¡ nieparzyst¡. Istnieje wówczas wzajemnie jednoznaczna odpowiednio±¢ pomi¦dzy rozkªadami (a, b) liczby n = ab i zapisami (t, s) liczby n = t2 − s2 . Dowód. Wystarczy sprawdzi¢, »e nast¦puj¡ce odwzorowania s¡ wzajemnie jednoznaczne.

 (a, b) 7→

a+b a−b , 2 2

 ;

(t, s) 7→ (t + s, t − s).

W naszych dalszych rozwa»aniach b¦dziemy stosowa¢ oznaczenia przyj¦te w twierdzeniu 9.16 oraz zakªada¢, »e liczba

n

jest nieparzysta.

n = ab oraz a, b s¡ blisko √ siebie, to s = (a − b)/2 jest . Szukaj¡c zatem rozkªadu t niewiele ró»ni si¦ od n√ (a, b) liczby n próbujemy kolejnych warto±ci t od [ n]+1 a» znajdziemy tak¡ 2 2 liczb¦ t, »e t − n jest peªnym kwadratem. Jest to nasza liczba s . Zauwa»my, »e je»eli

maª¡ liczb¡, czyli liczba

9.9 Przykªad. Rozªó»my √ 

n = 200819. W tym celu obli2 czy liczby 449 − 200819 = 782,

na czynniki liczb¦

200819 + 1 = 449 i sprawdzamy, 450 − 200819 = 1681 itd. s¡ kwadratami. 2 kwadratem, ale 1681 = 41 . Zatem

czamy 2

Okazuje si¦, »e 782 nie jest

200819 = 4502 − 412 = 491 · 409. 87

Oczywi±cie, cz¦sto si¦ zdarza, »e opisana powy»ej metoda nie przynosi rezultatu. Istnieje pewne ulepszenie, h i które hteraz iopiszemy. Mianowicie, mo»emy spróbowa¢ warto±ci

liczby

√

kn + 1,

√

kn + 2

2

itd. dla

t − s = kn, czyli rozkªad liczby kn. NWD(t + s, n) > 1, czyli poznamy nietrywialny

razem otrzymamy liczb¡, to

2

t=

k ∈ N.

Je±li

k

Tym

jest maª¡

dzielnik wªa±ciwy

n.

9.10 Przykªad.

Rozªó»my na czynniki liczb¦ 141467. Sprawdzaj¡c

t = 377,

378, . . . dochodzimy do wniosku, »e do niczego nie dojdziemy. Próbujemy zatem k = 3 i sprawdzamy liczby 652, 653, 654 oraz 655. Otrzymujemy 6552 − 141467 = 682 . Nast¦pnie obliczamy NWD(655 + 68, 141467) = 241 i otrzymujemy rozkªad

141467 = 241 · 587. Poka»emy, »e je±li metoda Fermata nie przyniosªa po»¡danego skutku i chcemy zastosowa¢ opisane ulepszenie, to nie warto bra¢ tu pod uwag¦ k = 2. Istotnie, je±li t2 − s2 = 2n, to jedna z liczb t + s, t − s musi by¢

t i s s¡ parzyste b¡d¹ obie s¡ nieparzyste. Zatem i t − s jest parzysta. Wynika st¡d, »e 4|2n, czyli n jest liczb¡ parzyst¡. Jest to sprzeczno±¢, poniewa» rozwa»amy tu tylko liczby n nieparzyste. Mo»na parzysta. Zatem obie liczby

pokaza¢ (dowód wymaga znajomo±ci pewnych nie wprowadzonych tu poj¦¢), »e równie»

9.4

k=4

jest ,,zª¡ liczb¡.

Bazy rozkªadu

Metoda baz rozkªadu jest ulepszeniem metody Fermata opisanej w poprzed2 2 nim podrozdziale. Opiera si¦ ona na nast¦puj¡cej obserwacji. Je»eli t ≡ s (mod n), ale t 6≡ ±s (mod n), to n|t2 − s2 ale n - t − s ani t + s. Zatem

(t − s, n) > 1

NWD

lub NWD(t

4633. Zauwa»my, »e

4633 = 41 · 113.

+ s, n) > 1. Dla przykªadu rozwa»my liczb¦ 4633|772 − 362 . Mamy NWD(77 − 36, 4633) = 41, wi¦c

Istotnym problemem jest tu znalezienie 77 i 36.

Wprowadzimy teraz kilka poj¦¢. Bezwzgl¦dnie najmniejsz¡ reszt¡ z dzie-

n ∈ Z nazywamy liczb¦ caªkowit¡ r tak¡, »e a ≡ r (mod n) oraz je±li a ≡ s (mod n), to |r| ≤ |s|. Baz¡ rozkªadu nazywamy zbiór B = {−1, p1 , p2 , . . . , ph−1 }, gdzie pi s¡ ró»nymi liczbami pierwszymi. Liczba b jest B liczb¡, je»eli bezwzgl¦dnie najmniejsza reszta z 2 dzielenia b przez n rozkªada si¦ na iloczyn liczb nale»¡cych do zbioru B . lenia liczby caªkowitej

a

przez

88

Powró¢my do przykªadu liczby

B liczbami,

czas 67, 68 i 69 s¡

n = 4633.

Niech

B = {−1, 2, 3}.

Wów-

poniewa»

672 ≡ −144 (mod 4633 ), −144 = −1 · 24 · 32 ; 682 ≡ −9 (mod 4633 ), −9 = −1 · 32 ; 692 ≡ 128 (mod 4633 ), 128 = 27 . Zh2

oznacza hwymiarow¡ przestrze« wektorow¡ nad ciaªem Z2 . Dla ka»dej liczby n i danej bazy rozkªadu B zawieraj¡cej h liczb, ka»dej B liczbie b przypisujemy wektor ε ∈ Zh2 w nast¦puj¡cy sposób. Niech teraz

Q αi b2 mod n = h−1 i=0 pi niech εi = αi mod 2. Wówczas ε = (ε0 , ε1 , . . . , εh−1 ). Je»eli

= 4633, B = {−1, 2, 3}) B liczbie 67 odpowiada wektor (1, 0, 0), B liczbie 68 odpowiada tak»e (1, 0, 0), a B liczbie 69 odpowiada wektor (0, 1, 0). Przypu±¢my, »e mamy dany pewien zbiór B liczb bj takich, »e odpowiadajace im wektory εj = (ε0j , ε1j , . . . , εh−1,j ) sumuj¡ si¦ do zera. Oznaczmy 2 przez aj bezwzgl¦dnie najmniejsz¡ reszt¦ z dzielenia bj przez n i zapiszmy W naszym przykªadzie (n

aj =

h−1 Y

α

pi ij .

i=0 Poniewa»

εj

sumuj¡ si¦ do zera,

jest kwadratem. Oznaczmy

c=

Y

γi =

ajPjest kwadratem. Zatem 1 j αij . Niech teraz 2

pγi i mod n,

b=

i Wówczas mamy Szukamy wtedy

Y

iloczyn liczb

aj

bj mod n.

j

b2 ≡ c2 (mod n). Je»eli nowego zbioru B liczb.

mamy pecha, to

b ≡ ±c (mod n).

Sprawdzimy, czy mieli±my pecha w naszym przykªadzie, gdzie n = 4633, B = {−1, 2, 3}. Poniewa» (1, 0, 0) + (1, 0, 0) = (0, 0, 0), wi¦c mo»emy przyj¡¢ b1 = 67 oraz b2 = 68. Wówczas a1 = −1 · 24 · 32 oraz a2 = −1 · 32 . Po 4 4 2 2 pomno»eniu otrzymujemy a1 a2 = 2 · 3 , c = 2 · 3 mod 4633 = 36 oraz b = 67 · 68 mod 4633 = −77. Poniewa» −77 6≡ ±36 (mod 4)633, wi¦c mamy szcz¦±cie!

89

n jest liczb¡ 2 zªo»on¡, która rozkªada si¦ na iloczyn r czynników pierwszych, to liczba b r 2 ma 2 ≥ 4 pierwiastków. Zatem losowy pierwiastek z b jest równy ±b z 1 2 . Zatem w k próbach mamy przynajmniej prawdopodobie«stwem r ≤ 2 2 1 jedn¡ ,,dobr¡ par¦ (b, c) z prawdopodobie«stwem wi¦kszym ni» 1 − k . 2 W dalszym ci¡gu nie wiemy, jak wybra¢ odpowiedni¡ baz¦ rozkªadu B oraz zbiór B liczb bj . Zwykle stosuje si¦ tu dwa sposoby. Zastanówmy si¦ teraz, jak cz¦sto mo»emy mie¢ pecha. Skoro

B bierzemy −1 oraz h−1 pocz¡tkowych liczb pierwszych. Nast¦pnie zbieramy ,,na »ywioª du»o B liczb maj¡c nadziej¦, »e w ko«cu nam

1. Za

si¦ poszcz¦±ci.

2. Najpierw zbieramy dzieleniu przez Nast¦pnie za

bj

byªy

B

n

bj

tak, aby

b2j

miaªo maª¡ bezwzgl¦dn¡ reszt¦ przy

(na przykªad rozwa»amy liczby bliskie

h√

kn

i

, itd.).

bierzemy dokªadnie to co potrzeba, aby zbiór wszystkie

B liczbami.

Stosuj¡c 1, wzi¦li±my w naszym przykªadzie B = {−1, 2, 3} oraz za B  2 liczby wzi¦lismy 67, 68, 69. (68 = 4624). Spróbujmy si¦ uprze¢, »e 68, 69 2 oraz 96 maj¡ by¢ B -liczbami (96 ≈ 2 · 4633). Poniewa» 96 = −50 mod 4633,

B przyjmujemy zbiór {−1, 2, 3, 5}. Mamy −9 = −1 · 32 ε1 = (1, 0, 0, 0) 128 = 27 ε2 = (0, 1, 0, 0) −50 = −1 · 2 · 52 ε2 = (1, 1, 0, 0). 4 Dalej, b = 68 · 69 · 96 mod 4633 = 1031 oraz c = 2 · 3 · 5 mod 4633 = 240. Obliczamy teraz NWD(1031 − 240, 4633) otrzymuj¡c 113. Zatem wi¦c za

4633 = 113 · 41. Na zako«czenie podamy jeszcze jeden przykªad.

9.11 Przykªad.

√

kn i jednoSzukamy liczb bj w pobli»u 2 cze±nie nie chcemy, »eby w rozkªadzie bj mod n byªy liczby pierwsze wi¦ksze od 13. Rezultat przedstawimy w poni»szej tabelce. Niech

n = 1829.

90

bj

−1

42

1

43

2

Mo»emy wi¦c za

bj

5

1

85

1

11

13 1

1 2

74

7

1 2

61

86

3

1 1 1

4

1

1

wzi¡¢ 43 i 86 lub 42, 43, 61 oraz 85.

W pierwszym 3 oraz 2 · 5 = 40. W

43 · 86 mod 1829 = 40 42 · 43 · 61 · 85 mod 1829 = 1459, 2 · 3 · 5 · 7 · 13 mod 1829 = 901 i NWD(1459 + 901, 1829) = 59. Zatem 1829 = 59 · 31.

przypadku mamy pecha, poniewa»

drugim przypadku nie jest juz tak ¹le, poniewa»

91

Rozdziaª 10 Logarytm dyskretny 10.1

Poj¦cie logarytm dyskretny

System RSA jest oparty na tym, »e pomno»enie przez siebie dwóch liczb jest istotnie ªatwiejsze ni» rozkªad liczby na czynniki.

Podobn¡ wªasno±¢

,,jednokierunkowo±ci ma te» podnoszenie liczby do pot¦gi w (du»ym) ciele x sko«czonym. Zauwa»my, »e w R, obliczenie b nie jest istotnie ªatwiejsze od obliczenia logb x i to z dowoln¡ dokªadno±ci¡. Nie jest to jednak prawd¡ dla ciaª sko«czonych. Zaªó»my, »e mamy ustalon¡ liczb¦

b

nale»¡c¡ do grupy multyplikatywnej x pewnego ciaªa sko«czonego Fq . Je±li chcemy obliczy¢ b , stosujemy wypróbowan¡ metod¦ iterowanego podnoszenia do kwadratu, która dziaªa w miar¦ szybko. Je±li jednak wiemy tylko, »e ªatwo znale¹¢ taki wykªadnik

x,

y

»eby

jest pewn¡ pot¦g¡ elementu b, nie jest bx = y . Potrzebujemy zatem funkcji

okre±lonej na ciele sko«czonym i odwrotnej do pot¦gowania.

Tak¡ funkcj¦

nazywamy logarymem dyskretnym. Dokªadnie, logarytmem dyskretnym, o ∗ x podstawie b ∈ Fq z elementu y nazywamy tak¡ liczb¦ caªkowit¡ x, »e b = y .

Przykªady. 10.1.

We¹my

q = 19.

Wtedy liczba 2 jest generatorem grupy

F∗19 .

Logaryt-

mem dyskretnym o podstawie 2 z 7 jest 6.

10.2.

W grupie

10.3.

Rozwa»ymy ciaªo

F∗9 rozwa»my element α, który jest pierwiastkiem wielomianu x − x − 1. Logarytmem dyskretnym o podstawie α z −1 jest 4. 2

multyplikatywnej

F16129 , tutaj 16129 = 1272 . Niech generatorem grupy b¦dzie g = a + 2, przy czym a jest pierwiastkiem drugiego 92

stopnia z

2a + 2,

−1 = 126.

Wówczas logarytmem dyskretnym z 87 jest 12032, a z

12000.

Zwró¢my uwag¦ na to, »e logarytm dyskretny ma warto±ci w

Z,

czyli nie

tam gdzie argumenty. Dokªadnie jest to funkcja z grupy multyplikatywnej ciaªa sko«czonego do pier±cienia liczb caªkowitych. Podobnie jak i dla rozkªadu liczb na czynniki pierwsze, istniej¡ algorytmy pozwalaj¡ce stosunkowo szybko obliczy¢ logarytm dyskretny dla pewnych, szczególnych liczb oraz ciaª. Nie b¦dziemy si¦ jednak zajmowa¢ tymi algorytmami, poniewa» ich dokªadne wytªumaczenie wymaga znajomo±ci problemów zwi¡zanych z teori¡ ciaª sko«czonych, której tutaj nie przedstawimy. W zamian omówimy kilka systemów opartych na logarytmie dyskretnym.

10.2

System DiegoHellmana uzgadniania klucza

Jak ju» wspomnieli±my, systemy z publicznym kluczem s¡ wci¡» zbyt wolne, aby za ich pomoc¡ przesyªa¢ dªugie wiadomo±ci. Z drugiej strony, je±li wiadomo±¢ jest odpowiednio krótka, nie mo»na zªama¢ szyfru stosuj¡c analiz¦ cz¦sto±ci wyst¦powania liter. Dlatego systemów z publicznym kluczem cz¦sto u»ywa si¦ do uzgadniania kluczy systemów klasycznych. Opiszemy tu system wymiany kluczy oparty o logarytm dyskretny. Zaªó»my, »e do szyfrowania chcemy u»ywa¢ pewnego klucza

k.

Liczb¦

k

wybieramy losowo z pewnego przedziaªu pocz¡tkowego liczb naturalnych. Zauwa»my, »e wybranie liczby z takiego przedziaªu jest równowa»ne wybraniu losowego elementu pewnego du»ego ciaªa sko«czonego uto»samiamy z liczbami naturalnymi z przedziaªu Aby uto»sami¢ elementy

Fpf

Fpf

odpowiada

elementy

z liczbami caªkowitymi, wybieramy najpierw

baz¦ tego ciaªa (jako przestrzeni wektorowej) nad mentowi ciaªa

Fpf , którego [0, pf − 1].

f elementowy

Zp .

Wtedy ka»demu ele-

ci¡g elementów

reprezentuje liczb¦ zapisan¡ w systemie o podstawie

p.

Zp .

Ci¡g ten

Oczywi±cie, nie jest

to jedyny sposób uto»samienia pewnego przedziaªu liczb naturalnych z elementami ciaªa sko«czonego. Metoda DiegoHellmana dziaªa nast¦puj¡co. Potrzebujemy tu du»ego Fq oraz generatora g grupy F∗q . Liczb¦ q i element g podajemy do publicznej wiadomo±ci. Przypu±¢my, »e dwoje u»ytkowników, Maja ciaªa sko«czonego

i Gucio, chce uzgodni¢ klucz. Kluczem tym b¦dzie pewien element

93

Fq .

Aby

rozpocz¡¢ negocjacje, Maja wybiera dla siebie liczb¦ M , a Gucio liczb¦ G. M G Pot¦gi g oraz g oboje podaj¡ do publicznej wiadomo±ci. Wspólnym tajMG G nym kluczem, którego b¦d¡ u»ywa¢ jest g . Oczywi±cie, je±li znamy g M MG oraz M albo g oraz G, to bez problemów obliczamy g . Nie jest to M G jednak ªatwe, je±li znamy tylko g i g . Oczywi±cie, opisany system mo»emy stosowa¢ tylko wtedy, je±li prawdziwe jest nast¦puj¡ce zaªo»enie

Zaªo»enie DiegoHellmana. znane s¡ tylko

g

a

oraz

g

b

Zadanie obliczenia

g ab

nie jest ªatwe je±li

.

Powy»sze zaªo»enie jest tak samo silne jak zaªo»enie, »e logarytm dyskretny w grupie nie mo»e by¢ ªatwo obliczony. Dokªadnie, je±li znamy prosty a b sposób obliczania logarytmu dyskretnego, to znaj¡c g i g , bez problemu obab liczymy a oraz b, a wi¦c i g . Znanym problemem jest wynikanie odwrotne, ab a b tj. czy je±li obliczenie g znaj¡c g i g jest ªatwe, to tak»e obliczenie logarytmu dyskretnego jest ªatwe. Jest to wci¡» otwarty problem. Dziaªanie opisanego systemu wymiany kluczy opiszemy na podstawie ªatwego przeksztaªcenia szyfruj¡cego oraz maªego ciaªa sko«czonego.

10.4 Przykªad.

Przypu±¢my, »e naszym przeksztaªceniem szyfruj¡cym jest

przesuni¦cie, a wi¦c kluczem jest tu liczba

k,

któr¡ dodajemy modulo 26 do

ka»dej litery tekstu jawnego. Kluczem rozszyfrowuj¡cym jest tu wi¦c liczba

−k (mod 26). Sam klucz wybieramy bior¡c reszt¦ z dzielenia uzgodnionej liczby przez 26. Niech g (generator F53 ) b¦dzie równy 3. Zaªó»my, »e Maja 29 wybraªa liczb¦ losow¡ M = 29, wi¦c jej kluczem publicznym jest 3 = 26. G Kluczem publicznym Gucia jest 3 = 12. Zatem uzgodnionym kluczem 29 szyfruj¡cym jest p = 12 = 21. Sprawd¹my teraz, czy jest to rzeczywi±cie uzgodniony klucz, tj. czy Gucio otrzymaª t¦ sam¡ liczb¦. Wybran¡ liczb¡ Gucia byªo G = 47. Maja ma klucz 26 (= 329 ). Zatem Gucio otrzymaª klucz szyfruj¡cy p = 2647 = 21.

publiczny

10.5 Przykªad.

Zaªó»my, »e umawiamy si¦ na dwuliterowe hasªo do szy-

fru permutacyjnego i wykorzystujemy ciaªo typlikatywnej

g = a + 2,

gdzie

a

F16129

z generatorem grupy mul-

−1. HI , a

jest pierwiastkiem kwadratowym z

Oboje Przypu±¢my, »e Gucio zaczyna negocjacje od (tajnego) hasªa

T K . Oboje zamieniaj¡ swoje hasªa na liczby. S¡ to, odpowiednio, G = 190 = 7 · 26 + 8 oraz M = 504 = 19 ∗ 26 + 10. Gucio i Maja upublicz190 niaj¡ elementy (a + 2) = 7a + 94 oraz, odpowiednio, (a + 2)504 = 68a + 40. Maja, aby uzyska¢ hasªo, podnosi 7a + 94 do pot¦gi 504 otrzymuj¡c 21a + 24. Uzgodnionym hasªem jest wi¦c V Y . Maja od

94

10.3

System kryptograczny Masseya-Omury

Aby u»ywa¢ tego systemu, wszyscy u»ytkownicy musz¡ zdecydowa¢ si¦ u»ywa¢ ustalonego, powszechnie znanego ciaªa sko«czonego nik wybiera (w tajemnicy przed innymi) liczb¦ losow¡ jest wzgl¦dnie pierwsza z do

e

modulo

q − 1.

q − 1.

Nast¦pnie ka»dy oblicza liczb¦ odwrotn¡

Obie liczby

e

oraz

Tola chce wysªa¢ do Lolka wiadomo±¢ elementem ciaªa

Fq ,

Fq . Ka»dy u»ytkow0 ≤ e ≤ q − 1, która

d

P,

stanowi¡ klucz prywatny.

Je»eli

najpierw uto»samia j¡ z pewnym P eT . Lolek

a nast¦pnie wysyªa do Lolka wiadomo±¢

nie próbuje nawet odszyfrowywa¢ wiadomo±ci, tylko stosuj¡c swój klucz prye e watny oblicza P T L i tak otrzymany element odsyªa do Toli, która z kolei e e d e e d oblicza P T L T = P L i odsyªa to Do Lolka, który po obliczeniu P L L = P bez trudu odczytuje wiadomo±¢.

10.6 Przykªad. kluczem jest

Ponownie rozwa»ymy ciaªo

(779, 6563).

F16129 .

Zaªó»my, »e naszym

Otrzymali±my od Toli wiadomo±¢

(32a + 66, 16a + 112, 12a + 112, 48a + 66, 69a + 116, 66a + 0). Ka»dy z elemetów podnosimy do pot¦gi o wykªadniku 779, otrzymujemy

(75a + 48, 118a + 93, 118a + 78, 28a + 81, 71a + 79, 38a + 0) i odsyªamy to do Toli. Chwil¦ pó¹niej, Tola przysyªa nam ci¡g

(75a + 95, 30a + 40, 38a + 122, 38a + 83, 67a + 62, 100a + 0). Tym razem, podnosz¡c do pot¦gi 6563, otrzymujemy

(9a + 4, 18a + 19, 8a + 12, 15a + 17, 4a + 25, 10a + 0) i odczytujemy wiadomo±¢ (kolejne liczby, to pozycje liter alfabetu):

imprezka.

jest

Zauwa»my, »e wa»nym jest, aby u»ytkownik, który odczytaª wiele informacji nie byª w stanie znale¹¢ eT nawet je±li dotarªo do niego du»o wiadoP eT . Gdyby bowiem Lolek rozwi¡zaª problem logarytmu dyskretnego,

mo±ci

to szybko obliczyªby

eT

a wi¦c i

dT ,

a to oznaczaªoby, »e byªby w stanie nie

tylko odczyta¢ ka»d¡ wiadomo±¢, jak¡ wysyªa Tola (niezale»nie od tego, do kogo jest ona skierowana), ale równie» mógªby bez trudu ,,podszy¢ si¦ pod Tol¦.

95

Zwró¢my te» uwag¦ i na to, »e system Maseya-Omury wymaga stosowania dobrej metody potwierdzania to»samo±ci, poniewa» adresat, otrzymuj¡c e najpierw P , nie wie, czyim kluczem e jest ta wiadomo±¢ zaszyfrowana. Tak wi¦c Lolek mo»e otrzyma¢ wiadomo±¢ od Justysi b¦d¡c przekonanym, »e jest e e to wiadomo±¢ od Toli. Z drugiej strony, tak»e Tola po otrzymaniu P T L musi by¢ pewna, »e odpowied¹ przyszªa od Lolka a nie od innego u»ytkownika systemu.

10.4

System ElGamala

Tutaj równie» potrzebne jest ustalone ciaªo sko«czone Fq (odpowiednio du»e) ∗ oraz pewien element g ∈ Fq . Podobnie jak powy»ej, tekstem zaszyfrowanym b¡d¹ jego jednostkami s¡ elementy Fq . Ka»dy uzytkownik wybiera losowo liczb¦ caªkowit¡

0 < a < q − 1,

która jest jego tajnym kluczem rozszyfrowua j¡cym. jawnym kluczem szyfruj¡cym jest g . Zaªó»my, »e chcemy wysªa¢ do u»ytkownika

A wiadomo±¢ P .

W tym celu k a k wybieramy losow¡ liczb¦ naturaln¡ k i wysyªamy par¦ elementów (g , P g A ). aA k aA Oczywi±cie jeste±my w stanie obliczy¢ g znaj¡c tylko g , poniewa» wystarczy t¦ liczb¦ podnie±¢ do pot¦gi k . Adresat A chc¡c odczyta¢ wiadomo±¢, k a k podnosi najpierw g do pot¦gi aA , a nast¦pnie dzieli P g A przez otrzyman¡ liczb¦ uzyskuj¡c wiadomo±¢ P . Je±li adresat preferuje mno»enie, to zamiast k podnosi¢ g do pot¦gi aA , podnosi t¦ liczb¦ do pot¦gi q − 1 − aA a nast¦pnie a k mno»y wynik oraz P g A otrzymuj¡c P . Kto±, kto potra rozwi¡za¢ problem logarytmu dyskretnego w Fq bez a trudu rozszyfruje ka»d¡ wiadomo±¢, poniewa» znaj¡c g oraz g jest on w stanie znale¹¢ klucz rozszyfrowuj¡cy

a.

Je»eli zaªo»enie DiegoHellmana ak nie zachodzi, to tak»e mo»na zªama¢ szyfr ElGamala znajduj¡c g znaj¡c k a tylko g (przesyªane) oraz g (publiczne).

96

Rozdziaª 11 Protokoªy o zerowej wiedzy i przekazy nierozró»nialne Poj¦cie zerowej wiedzy pojawiªo si¦ w kryptograi na pocz¡tku lat osiemdziesi¡tych.

Zostaªo ono sprowokowane rozwojem rynku nansowego, a w

szczególno±ci poª¡czeniem rynku usªug bankowych z rynkiem usªug telekomunikacyjnych. Dokªadnie, wyobra¹my sobie sytuacj¦, gdy klient znajduj¡cy si¦ na Karaibach chce dokona¢ operacji w banku, który jest w Szwajcarii. W tym celu u»ywa linii telefonicznej i zleca t¡ drog¡ wykonanie operacji. Problemem jest potwierdzenie to»samo±ci zleceniodawcy.

Oczywi±cie mo»e on

poda¢ jakie± hasªo, które go zidentykuje. Tylko, »e hasªo to zna¢ b¦dzie od tej pory urz¦dnik bankowy oraz kilka innych osób, które w danej chwili przysªuchuj¡ si¦ rozmowie. Zleceniodawca chciaªby wi¦c nie tyle poda¢ hasªo co u d o w o d n i ¢ fakt, »e to hasªo zna. Po przeprowadzeniu takiego dowodu, urz¦dnik bankowy powinien by¢ pewien to»samo±ci zleceniodawcy, ale jego wiedza na temat tajnego hasªa powinna by¢ taka sama jak przed rozmow¡. Jak konkretnie przeprowadzi¢ dowód o zerowej wiedzy wytªumaczymy w oparciu o dwa poni»sze przykªady.

11.1

Kolorowanie mapy

Jest udowodnione, »e ka»d¡ map¦ na pªaszczy¹nie mo»na pokolorowa¢ u»ywaj¡c czterech kolorów. Niektóre mapy mo»na pokolorowa¢ u»ywaj¡c tylko trzech kolorów. Przypu±¢my, »e Urszuli udaªo si¦ pokolorowa¢ pewn¡ dosy¢ skomplikowan¡ map¦ trzema kolorami  czerwonym, niebieskim i zielonym.

97

Chce ona przekona¢ Stefana, »e istotnie potra ona pokolorowa¢ dan¡ map¦, ale jednocze±nie nie chce pokazywa¢ mapy. Aby przeprowadzi¢ dowód o zerowej wiedzy musimy przeªo»y¢ map¦ na j¦zyk matematyczny, a dokªadnie na j¦zyk teorii grafów. Grafem nazywamy par¦ zbiorów zbiory dwuelementowe

{u, v}

(V, E), gdzie elementami zbioru E s¡ u, v ∈ V . Elementy zbioru V na-

przy czym

zywamy wierzchoªkami i interpretujemy je geometrycznie jako punkty, a elementy zbioru

E

nazywamy kraw¦dziami i interpretujemy jako odcinki.

c, n, z , je±li istnieje tylko {u, v} ∈ E .

Mówimy, »e graf jest pokolorowany kolorami

f : V → {c, n, z}

taka, »e

f (u) 6= f (v)

je»eli

funkcja

Map¦ uto»samiamy z grafem w ten sposób, »e zbiór pa«stw staje si¦ zbiorem

V,

a do zbioru

E

nale»¡ te i tylko te pary pa«stw, które maj¡

wspóln¡ granic¦. Tak wi¦c zakªadamy, »e Urszula pokolorowaªa pewien graf i b¦dzie teraz udowadnia¢ Stefanowi, »e dokonaªa tego w sposób prawidªowy. Wyobra¹my sobie wierzchoªki tego grafu jako maªe, biaªe kuleczki, a kraw¦dzie jako pr¦ty. W ±rodku kuleczek znajduj¡ si¦ trzy lampki: czerwona, niebieska i zielona. Urszula posiada dwa urz¡dzenia:

A,

które uaktywnia lampk¦ o wybranym kolorze w ka»dym z wierzchoªku;

B,

które po naci±ni¦ciu przycisku wybiera losow¡ permutacj¦ trzech kolorów i zmienia kolor aktywnej lampki w ka»dym wierzchoªku zgodnie z t¡ permutacj¡. Zaªó»my, »e lampki wewn¡trz wierzchoªków zapalaj¡ si¦ je±li kto± chwyci

za pr¦t ª¡cz¡cy te dwa wierzchoªki. Urszula konstruuje 3kolorowanie grafu i za pomoc¡ urz¡dzania A uaktywnia lampki w ka»dym z wierzchoªków. A oto procedura, któr¡ wykonuje Stefan:

1. Stefan mo»e chwyci¢ za jeden pr¦t i zapali¢ lampki na jego ko«cach. Je±li graf jest pokolorowany prawidªowo, wierzchoªki rozbªyskuj¡ róo»nymi kolorami. 2. Urszula naciska przycisk urz¡dzenia B i permutuje kolory. 3. Kroki 1. i 2. s¡ powtarzane tak dªugo, a» Stefan nie przekona si¦, »e graf jest pokolorowany prawidªowo.

98

Zauwa»my, »e je±li graf nie jest pokolorowany prawidªowo, to w pewnym momencie Stefan chwyci za pr¦t, którego wierzchoªki zapal¡ si¦ tym samym kolorem. Po drugie, z uwagi na ci¡gªe permutowanie kolorów, Stefan nie jest w stanie odtworzy¢ pokolorowania grafu.

Istotnie, gdyby Urszula znaªaby

Stefana na tyle, »e byªaby w stanie przwidzie¢, który pr¦t on chwyci, nie musiaªaby w ogóle kolorowa¢ grafu, tylko po prostu zadbaªaby o to, by na ko«cach pr¦ta, który zamierza chwyci¢ Stefan aktywne byªy lampki ró»nych kolorów.

11.2

Logarytm dyskretny

Przyjmiemy tu, »e mamy dane pewne ciaªo sko«czone Fq oraz generator g ∗ jego grupy multyplikatywnej. Niech y ∈ Fq . Przypu±¢my, »e Urszula znalax zªa rozwi¡zanie równania g = y , czyli logarytm dyskretny o podstawnie g z elementu

y.

Chce ona teraz przekona¢ Stefana, i» faktycznie zna ona loga-

rytm dyskretny, ale nie chce podawa¢ warto±ci liczbowej i Stefan znaj¡ ciaªo sko«czone

Fq

x.

Oboje, Urszula

oraz rz¡d jego grupy multyplikatywnej.

Oto ci¡g kroków, które wykonuj¡ w celu przeprowadzenia dowodu o zerowej wiedzy:

Krok 1.

Urszula generuje losow¡ liczb¦ dodatni¡ b = ge.

e < q−1

i wysyªa Stefa-

nowi element

Krok 2.

Stefan decyduje, któr¡ z poni»szych czynno±ci ma wykona¢ (mo»e

wykona¢ dokªadnie jedn¡ z nich):

Krok 2a.

Stefan prosi Urszul¦ o ujawnienie e. Jej prawdomówno±¢ g e i porównuj¡c to z otrzyman¡ liczb¡ b.

sprawdza obliczaj¡c

Krok 2b. przez

Stefan prosi Urszul¦ o wskazanie reszty

r

q − 1.

(a próbuje ona to

Je±li Urszula faktycznie zna

x

z dzielenia

x+e

udowodni¢), to znalezienie tej reszty nie powinno jej przysporzy¢ r problemu. Stefan sprawdza prawdomówno±¢ Urszuli obliczaj¡c g x e x+e r i przyrównuj¡c to do yb. Zauwa»my, »e yb = g g = g =g .

Krok 3.

Kroki 1. oraz 2. s¡ powtarzane tak dªugo, a» Stefan jest caªkowicie

przekonany, »e Urszula zna

x.

Zauwa»my najpierw, »e Stefan nie mo»e domaga¢ si¦ od Urszuli obu informacji z podpunktów 2

a. oraz 2b. Gdyby poznaª on jednocze±nie e oraz r, 99

to poznaªby te»

x = r − e.

Nast¦pnie zauwa»my, »e znajomo±¢

x

nie jest

a. Jednak»e mo»e on zdecy-

Urszuli potrzebna je»eli Stefan decyduje si¦ na 2

b.,

dowa¢ si¦ na krok 2

x

jest potrzebna. Po co wi¦c jest ge w kroku potrzebny krok 2 ? Gdyby go nie byªo, Urszula mogªaby wysªa¢ y 1., a w kroku 2 po prostu e. Krok 2 zapobiega takiej mo»liwo±ci.

b.

a.

a tu ju» znajomo±¢

a.

W powy»szym dowodzie istotnie wyst¦puje zerowa wiedza. Je±li bowiem kto± nie zna liczby

x,

ale jest w stanie przewidzie¢ post¦powanie Stefana,

tzn. wie, co on wybierze w nast¦pnym kroku, to bez trudu mo»e go oszuka¢.

a.

Mianowicie, je±li wiadomo, »e Stefan zdecyduje si¦ na 2 , to nale»y mu e przesªa¢ g w kroku 1. oraz e w kroku 2 Je»eli natomiast wiemy, »e Stefan ge zdecyduje si¦ na 2 , to wysyªamy mu w kroku 1. oraz e w kroku 2 y

a.

b.

11.1 Przykªad.

Ponownie wykorzystamy

b.

F16129

z generatorem

g = a + 2,

2

a + 1 = 0. Urszula udowodni Stefanowi, »e zna warto±¢ x logarytmu y = 96a + 106. W tym celu generuje e i wysyªa g e = 111a + 120. Je±li Stefan poprosi o e, Urszula wy±le mu 41 i Stefan sprawdzi, »e (a + 2)41 = 111a + 120. Urszula ponownie generuje e i tym razem wysyªa 82a + 62. Przypu±¢my, »e Stefan poprosi tym razem o reszt¦ z dzielenia x + e przez 16128. Wtedy Urszula wysyªa mu liczb¦ 15276, a Stefan sprawdza, 15276 czy (a + 2) = (82a + 62)(96a + 106). Czynno±ci te powtarzaj¡ a» Stefan uzna, »e Urszula istotnie zna warto±¢ x gdzie

dyskretnego z

11.3

Przekazy nierozró»nialne

Powy»ej przedstawione dowody byªy dowodami interaktywnymi, tzn. podczas uzasadniania Urszula oraz Stefan kontaktowali si¦ ze sob¡. Kanaª przekazów nierozró»nialnych sªu»y do konstruowania nieinteraktywnych dowodów o zerowej wiedzy. Przebiega on zatem w jedn¡ stron¦  w kierunku sprawdzaj¡cego. Dopuszczamy tu jednak mo»liwo±¢, »e pewne informacje mog¡ by¢ przesªane w drug¡ stron¦, ale ju» nie kanaªem tylko ,,publicznie. Dokªadnie, kanaª przekazów nierozró»nialnych umo»liwia Urszuli przekazanie Stefanowi dwóch pakietów zaszyfrowanych informacji przy czym speªnione musz¡ by¢ nast¦puj¡ce warunki: 1. Stefan mo»e rozszyfrowa¢ dokªadnie jeden z przesªanych dwóch pakietów. 2. Urszula nie wie, który z pakietów zostanie rozszyfrowany.

100

3. Stefan oraz Urszula s¡ pewni, »e warunki 1) oraz 2) s¡ speªnione. Opiszmy przykªad kanaªu przekazów nierozró»nialnych oparty na problemie logarytmu dyskretnego. Potrzebne nam b¦dzie (du»e) ciaªo sko«czone Fq oraz ustalony element b ∈ F∗q taki, »e je±li znamy bx oraz by , to trudno xy jest obliczy¢ b (czyli speªnione jest zaªo»enie DiegoHellmana). Dalej, n potrzebne nam b¦dzie przeksztaªcenie ψ : Fq → F2 . Przy czym warto±ci zarówno przeksztaªcenia

ψ

jak i przeksztaªcenia odwrotnego mog¡ by¢ obli-

czone w ªatwy sposób. Zaªó»my, »e wszystkie ci¡gi n-bitowe maj¡ce na ko«cu f 0 nale»¡ do przeciwdziedziny ψ . Je±li q = p oraz elementy Fq uto»samimy z liczbami caªkowitymi zapisanymi w systemie o podstawie

p,

to

ψ

mo»e od-

wzorowywa¢ te elementy przypisuj¡c im ci¡g bitów wyst¦puj¡cych w zapisie dwójkowym odpowiadaj¡cych liczb. Przypu±¢my, »e jednostkami tekstu s¡ ci¡gi Potrzebny nam jeszcze b¦dzie ustalony element

nbitów, tzn. elementy Fn2 . C ∈ F∗q taki, »e nikt nie zna

jego logarytmu dyskretnego. Kanaª przekazów nierozró»nialnych dziaªa w nast¦puj¡cy sposób. Stefan

0 < x < q − 1 oraz 1 ∈ {1, 2}. Nast¦pnie tworzy (β1 , β2 ), gdzie βi = bx oraz β3−i = bCx . Dopuszczamy tu

wybiera losowo liczby swój klucz publiczny

mo»liwo±¢ utworzenia serii tego rodzaju kluczy publicznych. B¦d¡ one znane Urszuli (tak jak i wszystkim innym). Zauwa»my, »e Stefan nie zna logarytmu dyskretnego liczby

β3−i

poniewa» nikt nie zna logarytmu dyskretnego liczby

C. Urszula wybiera teraz teksty kietom.

m1

m2 , które przypisuje dwóm pay1 , y2 ∈ {0, 1, . . . , q − 1} i wysyªa

oraz

Wybiera ona te» liczby losowe

Stefanowi dwa pakiety:

by1 , α1 = m1 + ψ(β1y1 ) βiyi = (bx )yi , a yi wyznaczy¢ ψ(βi ), a co Poniewa»

oraz

by2 , α2 = m2 + ψ(β2y2 ).

Stefan zna zarówno

by1

oraz

x,

wi¦c mo»e on ªatwo yi za tym idzie, tak»e wyznaczy¢ mi = αi + ψ(βi ).

Odczytanie wiadomo±ci m3−i jest jednak niemo»liwe, poniewa» znajomo±¢ y3−i by3−i oraz C nie jest wystarczaj¡ca do znalezienia β3−i (zaªo»enie Diego Hellmana). Tak wi¦c Stefan mo»e odczyta¢ dokªadnie jedn¡ z przesªanych wiadomo±ci. Urszula mo»e bez trudu sprawdzi¢, »e

β1 β2 = C , wi¦c β1 oraz β2 .

zna¢ logarytmów dyskretnych z obu elementów

interesie le»y posiadanie jak najwi¦cej informacji.

Stefan nie mo»e Jednak»e w jego

Urszula mo»e wi¦c by¢

pewna, »e Stefan zna logarytm dyskretny dokªadnie jednej z liczb

101

β1 , β2 .

Nie

ma jednak sposobu na to, by zdecydowa¢ jednoznacznie z którego elementu zna Stefan logarytm dyskretny. Tak wi¦c warunki 2) oraz 3) denicji kanaªu przekazów nierozró»nialnych s¡ speªnione.

11.4

Dowód faktoryzacji

Opiszemy procedur¦ nieiteraktywnego dowodu o zerowej wiedzy, za pomoc¡ którego Urszula przekona stefana, »e zna ona rozkªad na czynniki liczby caªkowitej

n.

Wykorzystamy tu fakt, »e znajomo±¢ faktoryzacji liczby

n jest równz

nowa»na umiej¦tno±ci znajdywania pierwiastków kwadratowych modulo

n na iloczyn liczb pierwszych p oraz q i mamy rozwi¡za¢ kongruencj¦ y ≡ x2 (mod n), to rozwi¡zujemy 2 2 dwie kongruencje y ≡ x (mod p) oraz y ≡ x (mod q) a nast¦pnie stosujemy

dowolnej liczby. Istotnie, je±li znamy rozkªad

chi«skie twierdzenie o resztach dostaj¡c cztery pierwiastki wyj±ciowej kon2 gruencji. Je±li natomiast potramy rozwi¡za¢ kongruencj¦ y ≡ x (mod n), 2 2 czyli znale¹¢ ±x1 oraz ±x2 , takie, »e x1 ≡ x2 (mod n), to znajdziemy te» nietrywialny dzielnik liczby n, który jest równy NWD(x1 + x2 , n). Opiszemy teraz procedur¦ dowodu o zerowej wiedzy. Zakªadamy tutaj, »e nad wszystkim czuwa niezale»ny arbiter okre±lany mianem Centrum, który dostarcza te» pewnych informacji zarówno dla Urszuli jak i dla Stefana. 1. Centrum generuje losow¡ liczb¦ y = x2 mod n.

x i wysyªa do Urszuli i do Stefana liczb¦

2. Urszula oblicza cztery pierwiastki kwadratowe

±x1

oraz

±x2

z liczby

y.

Jeden z nich nazywa x0 . Nast¦pnie wybiera losow¡ liczb¦ r i ozna2 cza s = r mod n. Potem kªadzie m1 = r mod n oraz m2 = x0 r

mod n.

Ostatecznie Urszula wysyªa Stefanowi za pomoc¡ kanaªu prze-

kazów nierozró»nialnych wiadomo±ci przekazuje mu

m1

oraz

m2 ,

a drog¡ publiczn¡

s.

3. Stefan jest w stanie odczyta¢ tylko jedn¡ wiadomo±¢. Sprawdza, czy jej kwadrat przystaje modulo

n

do

s,

czy do

ys.

4. Czynno±ci 1.3. s¡ powtarzane dopóty, dopóki nie sko«cz¡ si¦ wszystkie klucze publiczne

(β1 , β2 )

Stefana u»ywane do aktywacji kanaªu przeka-

Je±li byªo T kluczy, to Stefan jest pewny z −T prawdopodobie«stwem 1 − 2 , »e Urszula zna rozkªad liczby n na

zów nierozró»nialnych. czynniki.

102

Przeprowad¹my teraz zwykª¡ dyskusj¦ na temat, czy powy»szy protokóª jest istotnie dowodem o zerowej wiedzy.

Zastanówmy si¦ najpierw, w jaki

sposób Urszula mogªaby oszuka¢ Stefana. Wiadomo±¢ wiastka z

y,

ale wiadomo±¢

m2

zawiera pierwiastek z

m1 nie zawiera piery i nie mo»na nic na

to poradzi¢. Jedyn¡ szans¡ uszustwa byªoby wi¦c tutaj przesyªanie dwóch identycznych wiadomo±ci

m1 .

Szybko jednak Stefan nabraªby podejrze«, po-

niewa» za ka»dym razem przy sprawdzaniu otrzymywaªby

s, a taki (β1 , β2 )

przydarza si¦ tylko wówczas, gdy przy generowaniu klucza losow¡

i

ukªad liczb¡

jest zawsze 1. Czy Stefan odtworzyªby wszystkie pierwiastki kwa-

y ? Tak¡ mo»liwo±¢ daje mu tylko wiadomo±¢ m2 . Poniewa» jednak liczba r nie jest mu znana, wi¦c nie mo»e on obliczy¢ x0 znaj¡c tylko x0 r mod n oraz r2 mod n. Tak wi¦c Stefan nie jest w stanie znale¹¢ nawet 2 jednego pierwiastka kongruencji y ≡ x (mod n).

dratowe z

103