Kryptografia — wyk lad dla IV roku

Kryptografia

Wyk lad z podstaw klasycznej

kryptografii z elementami

kryptografii kwantowej

dla student´

ow IV roku

Serdecznie

witam!

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

0

Kryptografia — wyk lad dla IV roku

Literatura

• M. Kuty lowski i W. B. Strothmann Kryptografia: Teoria

i praktyka zabezpieczania system´

ow komputerowych, Wyd.

READ ME, Warszawa, 1999, drugie wydanie dost

,

epne w

ksi

,

egarniach

• B. Schneier Kryptografia dla praktyk´ow, WNT, Warszawa,

2002, wydanie drugie

• R. Wobst, Kryptologia. Budowa i lamanie zabezpiecze´n,

RM, Warszawa, 2002

• A. J. Menezes, P. C. van Oorschot, S. A. Vanstone

Handbook of Applied Cryptography, CRC Press, 1997, New
York, dost

,

epna w Internecie

• S. J. Lomonaco A quick glance at quantum cryptography,

LANL quant-ph archive, quant-ph/9811056, 1998

• S. J. Lomonaco A talk on quantum cryptography or how

Alice outwits Eve, LANL quantum-ph archive, quant-
ph/0102016, 2001

• N. Gisin, G. Ribordy, W. Titel, H. Zbinden Quantum

cryptography, LANL quant-ph archive, quant-ph/0101098,
2001

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

1

Kryptografia — wyk lad dla IV roku

Terminologia

•

Kryptografia

— dziedzina wiedzy zajmuj

,

aca si

,

e zabez-

pieczaniem informacji (szyfrowanie)

•

Kryptoanaliza

— lamanie szyfr´ow

•

Kryptologia

— dzia l matematyki, kt´ory zajmuje si

,

e

podstawami metod kryptograficznych (kryptografia +
kryptoanaliza)

•

G l´

owne postacie

?

Alicja

— nadawca informacji

?

Bolek

— odbiorca informacji

?

Ewa

— pods luchuj

,

aca kana l przesy lowy i usi-

luj

,

aca przechwyci´

c informacj

,

e przeznaczon

,

a dla

Bolka

Ewa

⇑

Alicja

=

⇒

Bolek

Szyfrowanie i deszyfrowanie

tekst jawny

M

szyfrowanie

=

⇒

E

K

(M ) = C

kryptogram

C

deszyfrowanie

=

⇒

D

K

(C) = M

tekst jawny

M

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

2

Kryptografia — wyk lad dla IV roku

Algorytmy

•

symetryczne

— klucz do szyfrowania i deszyfrowania

jest ten sam (

klucz tajny

) — DES, IDEA

•

asymetryczne

— klucze do szyfrowania i deszyfrowa-

nia s

,

a r´o˙zne (

klucz jawny albo publiczny

— RSA,

ElGamal)

Przyk lad kryptogramu

• tekst jawny

Wyk lad z podstaw klasycznej kryptografii z elementami kryptografii kwantowej

• kryptogram (GnuPG)

hQEOA+npwcy1l0+VEAP+IrpTozmtpWBINXV5koW5sBC86EAelZTrEXrzUHohenPo

ohzkgIoBH17Rvu46hZUsHjeHyH74RI1Lv0klHbtBOLiCLvZfdtBWFFtzr4j4kDt7

n7kGMrJCxwOKuZIVCdMrRS9jvcBgFydYIeq/jkA3VvPGU4nT3AEyqiZ+xkrPRvsE

AJ59+4YDc1sbccJdu6nyRMJ2rcYH+SoS+BDgUmkopkG2KCjnQHArUWGq9N1v3ULH

dRfKwl4kgOK2EQGTFaQxjGXqyK41MS5noOZhZ8nHgJ4N9vE/TH/CaTiWgLQyXoKt

4J4xOJ5wx6rjNIK5MRl37XxWr3D8xDwWBGtKFGLllcV/0ogBymNlqBWZB6qi/xZo

cLdPWR94WmIvpkxWsR5HZhU06K6D7l/KgSarosSDwpOtT6c/21epCZvuvrfnq8pm

lpTXqVuHVsZNGCp599pJCkgLTxdQDyV0xjD8feVEtX2pfHxdWMORMdEG2QGfWSCa

z0hvf2t7B+7lFQsK+TPi3+YQMaoXK+XmAyPz =vRaX

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

3

Kryptografia — wyk lad dla IV roku

Podstawowe zastosowania

• ochrona danych

? dane na dyskach

? przesy lanie danych poprzez linie nara˙zone na pods luch

• uwierzytelnianie dokument´ow i os´ob
• ochrona prywatno´sci korespondencji elektronicznej
• elektroniczny notariusz
• podpis cyfrowy
• pieni

,

adze cyfrowe

• wybory elektroniczne

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

4

Kryptografia — wyk lad dla IV roku

Jak to dzia la: algorytm symetryczny

1. Alicja i Bolek uzgadniaj

,

a algorytm i klucz jakich b

,

ed

,

a

u˙zywa´c

2. Alicja szyfruje tekst u˙zywaj

,

ac uzgodnionego algorytmu i

klucza otrzymuj

,

ac kryptogram

3. Alicja przesy la kryptogram do Bolka

4. Bolek deszyfruje kryptogram u˙zywaj

,

ac tego samego

algorytmu i klucza otrzymuj

,

ac tekst jawny

•

Problemy:

? klucz musi by´c przekazywany w spos´ob tajny

? je´sli Ewa wejdzie w posiadanie klucza to mo˙ze deszy-

szyfrowa´c wszystko, a nawet podszy´c si

,

e pod Alicj

,

e

? je´sli ka˙zda para korespondent´ow w sieci dysponuje

w lasnym kluczem to liczba kluczy szybko ro´snie dla
kogo´s kto utrzymuje kontakt z wieloma osobami

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

5

Kryptografia — wyk lad dla IV roku

Jak to dzia la: algorytm asymetryczny

1. Alicja i Bolek uzgadniaj

,

a kryptosystem z kluczem pu-

blicznym, kt´orego b

,

ed

,

a u˙zywa´c

2. Bolek przesy la Alicji sw´oj klucz publiczny

3. Alicja szyfruje wiadomo´s´c kluczem publicznym Bolka i

przesy la kryptogram do Bolka

4. Bolek deszyfruje kryptogram u˙zywaj

,

ac swojego klucza

prywatnego

lub

u˙zytkownicy sieci uzgadniaj

,

a kryptosystem i przesy laj

,

a

swoje klucze publiczne do bazy na znanym serwerze i wtedy
protok´o l wygl

,

ada jeszcze pro´sciej

1. Alicja i Bolek pobieraj

,

a klucze publiczne z serwera

2. Alicja szyfruje wiadomo´s´c kluczem publicznym Bolka i

wysy la kryptogram do Bolka

3. Bolek deszyfruje wiadomo´s´c Alicji u˙zywaj

,

ac w lasnego

klucza prywatnego

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

6

Kryptografia — wyk lad dla IV roku

Kryptosystem hybrydowy

1. Bolek wysy la do Alicji sw´oj klucz publiczny

2. Alicja generuje losowy klucz K dla obecnej sesji, szyfruje

go kluczem publicznym Bolka i wysy la kryptogram klucza
E

B

(K) do Bolka

3. Bolek deszyfruje kryptogram klucza u˙zywaj

,

ac swojego

klucza prywatnego, D

B

(E

B

(K))=K, otrzymuj

,

ac klucz K

dla obecnej sesji

4. oboje u˙zywaj

,

a klucza K i symetrycznego algorytmu do

szyfrowania i deszyfrowania informacji przesy lanych w
czasie tej sesji

•

Uwagi:

? algorytmy symetryczne s

,

a szybsze ni˙z algorytmy

asymetryczne, co ma znaczenie przy przesy laniu du˙zej
ilo´sci danych

? je´sli Ewa zdob

,

edzie klucz K, to mo˙ze go u˙zy´c do

deszyfrowania jedynie aktualnej sesji, potem ju˙z jest
bezu˙zyteczny

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

7

Kryptografia — wyk lad dla IV roku

Podpis cyfrowy: kryptosystem z kluczem

publicznym

1. Alicja szyfruje dokument u˙zywaj

,

ac swojego klucza

prywatnego, podpisuj

,

ac w ten spos´ob dokument

2. Alicja przesy la tak podpisany dokument do Bolka

3. Bolek deszyfruje dokument u˙zywaj

,

ac klucza publicznego

Alicji, weryfikuj

,

ac w ten spos´ob podpis Alicji

•

Uwagi:

? podpis jest prawdziwy; Bolek weryfikuje go deszyfruj

,

ac

kryptogram kluczem publicznym Alicji

? podpis nie mo˙ze by´c sfa lszowany; tylko Alicja zna jej

klucz prywatny

? podpis nie mo˙ze by´c przeniesiony do innego dokumentu

? podpisany dokument nie mo˙ze by´c zmieniony; zmie-

niony dokument nie da si

,

e rozszyfrowa´c kluczem

publicznym Alicji

? podpis jest niezaprzeczalny;

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

8

Kryptografia — wyk lad dla IV roku

Jednokierunkowe funkcje hashuj

,

ace (skr´

otu)

• dla ka˙zdego X latwo jest obliczy´c H(X)
• H(X) ma tak

,

a sam

,

a d lugo´s´c dla wszystkich tekst´ow X

• dla zadanego Y znalezienie takiego X, ˙ze H(X) = Y jest

praktycznie niemo˙zliwe

• dla zadanego X trudno znale´z´c X

0

takie, ˙ze H(X) =

H(X

0

)

Elektroniczny notariusz

• dla danego dokumentu X obliczamy warto´s´c H(X) i

publikujemy lub deponujemy u notariusza warto´s´c H(X)

• chc

,

ac udowodni´c prawdziwo´s´c dokumentu X przedsta-

wiamy dokument, obliczamy H(X) i por´ownujemy z
opublikowan

,

a wcze´sniej warto´sci

,

a

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

9

Kryptografia — wyk lad dla IV roku

Szyfr Cezara

• szyfr podstawieniowy monoalfabetyczny

ABCDEFGH I J KLMNOPR S T UVWXYZ
DEFGH I J KLMNO P R S TUVWXY Z ABC

tekst jawny=

⇒KRYP T OGRAF I A

kryptogram=

⇒

NUBTW S J UD I LD

Szyfr Vigen`

ere’a

A B C D E F G H I J K L M N

O

P R S T U V W X Y Z

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

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

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

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

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

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

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

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

M

N O P R S T U V W X Y Z A B

C

D E F G H I J K L

N O P R S T

U

V W X Y Z A B C D E F G H I J K L M

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

P R S T U V W X Y Z A B C D E F G H

I

J K L M N O

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

S

T U V W X Y Z A B

C

D E F G H

I

J K L M N O P R

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

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

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

G

H I J K L M N O P R S T U V

W

X

Z A B C D

E

F G H I J K L M N O

P

R S T U V W X Y

klucz =

⇒

S Z Y MPAN S S ZYM

tekst =

⇒KR Y PTOGRAF I A

krypt.=

⇒

CPWC I OU I SEGM

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

10

Kryptografia — wyk lad dla IV roku

Operacja xor i one-time pad — szyfr

Vernama

0

⊕ 0 = 0

0

⊕ 1 = 1

1

⊕ 0 = 1

1

⊕ 1 = 0

• tekst jawny jest ci

,

agiem bit´ow M=m

1

, m

2

, . . . , m

n

• wybieramy losowy ci

,

ag bit´ow K=k

1

, k

2

, . . . , k

n

, kt´ory

stanowi klucz

• szyfrowanie polega na wykonaniu operacji xor bit po

bicie;

otrzymujemy w ten spos´

ob losowy ci

,

ag bit´

ow stanowi

,

acych

kryptogram C=c

1

, c

2

, . . . , c

n

, gdzie c

i

= m

i

⊕ k

i

• operacja ta jest odwracalna;

poniewa˙z a

⊕a = 0 i a⊕b⊕b = a, zatem c

i

⊕k

i

= (m

i

⊕k

i

)

⊕k

i

=

m

i

• kryptogram jest losowym ci

,

agiem n bit´ow

Je´sli k

i

= m

i

to c

i

= 0, w przeciwnym wypadku c

i

= 1;

prawdopodobie´

nstwo, ˙ze c

i

= 0 jest r´

owne

1
2

niezale˙znie od

warto´sci m

i

, zatem i-ty bit kryptogramu jest losowy

• szyfr ten jest nie do z lamania —

bezpiecze´

nstwo do-

skona le

— nie mo˙zna uzyska´c ˙zadnej informacji o tek´scie

jawnym bez znajomo´sci klucza

Poniewa˙z c

i

= m

i

⊕ k

i

implikuje k

i

= m

i

⊕ c

i

, a kryptogram

c

1

, c

2

, . . . , c

n

odpowiada ka˙zdemu mo˙zliwemu tekstowi jawnemu

z takim samym prawdopodobie´

nstwem, to na podstawie samego

kryptogramu nie wiemy nic o tek´scie jawnym

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

11

Kryptografia — wyk lad dla IV roku

•

Problemy:

? klucz musi by´c wcze´sniej uzgodniony przez Alicj

,

e i

Bolka

? klucz musi by´c wybrany naprawd

,

e losowo, co nie jest

latwe

? klucz musi by´c przechowywany w bezpieczny spos´ob

? klucz musi by´c co najmniej tak d lugi jak szyfrowany

tekst

•

Przyk lad:

tekst jawny =

⇒

S

Z

Y

F

R

binarnie

=

⇒ 01010011 01011010 01011001 01000110 01010010

klucz

=

⇒

01110010 01010101 11011100 10110011 00101011

kryptogram =

⇒

00100001 00001111 10000101 11110101 01111001

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

12

Kryptografia — wyk lad dla IV roku

DES — Data Encryption Standard

• w 1981 r. przyj

,

ety w USA jako standard do cel´ow

cywilnych

• algorytm symetryczny
• szczeg´o ly algorytmu zosta ly opublikowane (podejrzenia o

tylne drzwi)

• szyfruje bloki 64 bitowe (8 liter ASCII z bitem parzysto´sci)
• klucze s

,

a efektywnie 56 bitowe (64 bity minus 8 bit´ow

parzysto´sci); obecnie uwa˙za si

,

e, ˙ze taka d lugo´s´c klucza jest

zbyt ma la

Etapy DES

• wej´scie — 64 bitowy blok
• permutacja pocz

,

atkowa

• blok zostaje podzielony na lew

,

a i praw

,

a po low

,

e po 32 bity

ka˙zda

• 16 rund identycznych operacji opisanych funkcj

,

a f , w

czasie kt´orych dane prawej po lowy s

,

a przekszta lcane z

u˙zyciem klucza

? w czasie ka˙zdej rundy bity klucza s

,

a przesuwane, a

nast

,

epnie 48 bitowy podklucz jest wybierany z 56

bitowego klucza

? prawa cz

,

e´s´c danych jest rozszerzana do 48 bit´ow za

pomoc

,

a permutacji rozszerzaj

,

acej a nast

,

epnie podlega

operacji xor z 48 bitami podklucza

? wynik wysy lany jest do 8 S-boks´ow, kt´ore produkuj

,

a

nowe 32 bity

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

13

Kryptografia — wyk lad dla IV roku

? otrzymane 32 bity s

,

a permutowane w P-boksie

• wynik tych 4 operacji stanowi

,

acych funkcj

,

e f podlega

operacji xor z lew

,

a po low

,

a i staje si

,

e now

,

a praw

,

a po low

,

a

• stara prawa po lowa staje si

,

e now

,

a lew

,

a po low

,

a, i tak 16

razy

• permutacja ko´ncowa
• kryptogram

Je´sli L

i

i R

i

s

,

a lew

,

a i praw

,

a po low

,

a dla i-tej rundy, K

i

jest

podkluczem dla tej rundy, to tej rundy mamy

L

i

=

R

i

−1

R

i

=

L

i

−1

⊕ f(R

i

−1

, K

i

)

• deszyfrowanie DES-em polega na przeprowadzeniu tych

samych operacji co dla szyfrowania tylko podklucze
wyst

,

epuj

,

a w odwrotnej kolejno´sci

Poniewa˙z

R

i

−1

=

L

i

L

i

−1

=

R

i

⊕ f(R

i

−1

, K

i

) = R

i

⊕ f(L

i

, K

i

)

to znaj

,

ac L

i

, R

i

oraz K

i

mo˙zemy obliczy´c L

i

−1

i R

i

−1

.

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

14

Kryptografia — wyk lad dla IV roku

PSfrag replacements

L

0

R

0

L

1

R

1

L

15

R

15

L

16

R

16

K

1

K

2

K

15

K

16

f

f

f

64

64

64

64

32

32

32

32

32

48

permutacja pocz

,

atkowa

permutacja ko´

ncowa

tekst jawny

kryptogram

Rysunek 1: Schemat dzia lania DES

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

15

Kryptografia — wyk lad dla IV roku

PSfrag replacements

L

i

−1

R

i

−1

L

i

R

i

klucz

klucz

K

i

permutacja

S-boksy (S

1

, S

2

, . . . , S

8

)

permutacja rozszerzaj

,

aca

permutacja zw

,

e˙zaj

,

aca

32

32

32

32

32

48

48

28

28

28

28

rotacja

rotacja

Rysunek 2: Jedna runda DES

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

16

Kryptografia — wyk lad dla IV roku

Elementy DES

• permutacje pocz

,

atkowa i ko´

ncowa nie maj

,

a znaczenia

kryptograficznego (u latwiaj

,

a operowanie danymi w baj-

tach)

IP 58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4

62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8
57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3
61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7

IP

−1

40 8 48 16 56 24 64 32 39 7 47 15 55 23 63 31
38 6 46 14 54 22 62 30 37 5 45 13 53 21 61 29
36 4 44 12 52 20 60 28 35 3 43 11 51 19 59 27
34 2 42 10 50 18 58 26 33 1 41 9 49 17 57 25

Tablica 1: Permutacja pocz

,

atkowa IP i ko´

ncowa IP

−1

(tablice

te czytamy od lewej do prawej, od g´

ory w d´

o l odczytuj

,

ac kolejne

bity wyniku, a numery umieszczone na kolejnych pozycjach tabeli

oznaczaj

,

a numer bitu na wej´sciu, np. bit 58 wej´scia jest pierwszym

bitem wyj´scia, itd.)

• generowanie podkluczy

? z 64 bitowego losowego klucza otrzymuje si

,

e 56 bitowy

ignoruj

,

ac co ´osmy bit i dokonuj

,

ac permutacji KP

KP 57 49 41 33 25 17 9 1 58 50 42 34 26 18

10 2 59 51 43 35 27 19 11 3 60 52 44 36
63 55 47 39 31 23 15 7 62 54 46 38 30 22
14 6 61 53 45 37 29 21 13 5 28 20 12 4

Tablica 2: Permutacja klucza

? 56 bitowy klucz dzieli si

,

e na dwie po lowy po 28 bit´ow

? po lowy s

,

a przesuwane cyklicznie w lewo o 1 lub 2 bity

w zale˙zno´sci od rundy wg regu ly

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

17

Kryptografia — wyk lad dla IV roku

runda

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

przesuni

,

ecie 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1

Tablica 3: Przesuni

,

ecia po l´owek klucza

? permutacja z kompresj

,

a CP (permutowany wyb´or) daje

48 bit´ow podklucza

CP 14 17 11 24 1 5 3 28 15 6 21 10

23 19 12 4 26 8 16 7 27 20 13 2
41 52 31 37 47 55 30 40 51 45 33 48
44 49 39 56 34 53 46 42 50 36 29 32

Tablica 4: Permutacja zw

,

e˙zaj

,

aca

• permutacja z rozszerzeniem rozszerza 32 bity R

i

do 48

bit´ow

EP 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

Tablica 5: Permutacja z rozszerzeniem

• S-boksy

? wynik operacji xor na rozszerzonym R

i

i K

i

dzielony

jest na 8 cz

,

e´sci po 6 bit´ow, z kt´orych ka˙zda przechodzi

do oddzielnego S-boksu (S

1

, . . . , S

8

)

? 6 bit´ow wchodz

,

acych do S-boksu przekszta lcanych

jest w 4 bity wyj´sciowe w specjalny spos´ob pierwszy i
ostatni bit 6 bit´ow wej´sciowych daje liczb

,

e dwubitow

,

a

od 0–3 oznaczaj

,

ac

,

a wiersz S-boksu, za´s bity 2–5 daj

,

a

liczb

,

e 4-bitow

,

a od 0–15, kt´ora odpowiada kolumnie

tabeli.

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

18

Kryptografia — wyk lad dla IV roku

S

1

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

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

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

S

2

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

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

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

S

3

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

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

S

4

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

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

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

S

5

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

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

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

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

S

6

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

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

S

7

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

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

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

S

8

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

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

Tablica 6: S-boksy

Np. dla 110011 na wej´sciu, 1 i 6 bit daj

,

a 11

2

= 3

10

,

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

19

Kryptografia — wyk lad dla IV roku

za´s bity 2–4 daj

,

a 1001

2

= 9

10

, na przeci

,

eciu wiersza

3 i kolumny 9 S

1

mamy liczb

,

e 11

10

= 0111

2

(wiersze

i kolumny liczymy od zera). W wyniku otrzymujemy
0111.

• wyniki z 8 S-boks´ow s

,

a l

,

aczone w 32 bitow

,

a liczb

,

e

• na tych 32 bitach dokonuje si

,

e permutacji wg Tablicy 7

oraz operacji xor z 32 bitami lewej po lowy otrzymuj

,

ac

now

,

a praw

,

a po low

,

e, kt´ora przekazywana jest do nast

,

epnej

rundy

16 7 20 21 29 12 28 17 1 15 23 26 5 18 31 10

2 8 24 14 32 27 3 9 19 13 30 6 22 11 4 25

Tablica 7: Pertmutacja (P -boks)

Trzykrotny DES

Rozszerzenie algorytmu DES, w kt´orym stosuje si

,

e dwa klucze

K

1

i K

2

•

Szyfrowanie

1. wiadomo´s´c szyfrowana jest kluczem K

1

2. wynik kroku 1. deszyfrowany jest kluczem K

2

3. wynik kroku 2. jest ponownie szyfrowany kluczem K

1

•

Deszyfrowanie

1. kryptogram deszyfrowany jest kluczem K

1

2. wynik kroku 1. szyfrowany jest kluczem K

2

3. wynik kroku 2. jest powt´ornie deszyfrowany kluczem

K

1

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

20

Kryptografia — wyk lad dla IV roku

Tryby szyfrowania: szyfrowanie blokowe

•

ECB — Electronic Codebook

(Elektroniczna ksi

,

a˙zka

kodowa)
Tekst jawny dzielony jest na bloki o d lugo´sci 64 bity i
ka˙zdy blok jest oddzielnie szyfrowany tym samym kluczem

? zaleta — utrata lub uszkodzenie pojedynczych blok´ow

nie ma wp lywu na mo˙zliwo´s´c deszyfrowania pozosta-
lych; nadaje si

,

e do szyfrowania baz danych

? wada — mo˙zliwa jest modyfikacja kryptogramu bez

znajomo´sci klucza

•

CBC — Cipher Block Chaining

(Wi

,

azanie blok´ow)

Szyfrowanie kolejnego bloku zale˙zy od wyniku szyfrowania
poprzedniego bloku; taki sam blok tekstu jawnego jest w
r´o˙znych miejscach szyfrowany inaczej — kolejny blok tek-
stu jawnego jest poddawany operacji xor z kryptogramem
poprzedniego bloku.

Matematycznie wygl

,

ada to nast

,

epuj

,

aco:

C

1

=

E

K

(M

1

⊕ I)

C

i

=

E

K

(M

i

⊕ C

i

−1

)

M

1

=

D

K

(C

1

⊕ I)

M

i

=

D

K

(C

i

)

⊕ C

i

−1

gdzie M

i

jest i-tym blokiem wiadomo´sci, C

i

i-tym blokiem

kryptogramu, za´s I jest losowym ci

,

agiem bit´

ow, kt´

ory jest

przesy lany bez szyfrowania

? zalety — takie same bloki tekstu jawnego maj

,

a r´o˙zne

kryptogramy; zmiana bitu (przek lamanie) wewn

,

atrz

jednego bloku prowadzi do zmiany tekstu po deszyfro-
waniu tylko w danym bloku i nast

,

epnym

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

21

Kryptografia — wyk lad dla IV roku

? wady — nie mo˙zna usun

,

a´c ˙zadnego bloku z kryp-

togramu; nie nadaje si

,

e do szyfrowania baz danych;

nieodporny na zak l´ocenia (dodatkowy bit lub utrata
jednego bitu psuj

,

a dalszy przekaz)

•

CFB — Cipher Feedback

(Szyfrowanie ze sprz

,

e˙zeniem

zwrotnym)
Szyfrowaniu podlegaj

,

a jednostki mniejsze ni˙z blok (64

bity), np. jeden znak ASCII (1 bajt = 8 bit´ow). Schemat
dzia lania przedstawiony jest na Rys. 3. Tryb wa˙zny w
zastosowaniach sieciowych, np. komunikacja pomi

,

edzy

klawiatur

,

a i serwerem. Istotnym elementem CFB jest

rejestr przesuwaj

,

acy.

• Dzia lanie CFB

1. na pocz

,

atku rejestr przesuwaj

,

acy zawiera losowy ci

,

ag

64 bit´ow

2. zawarto´s´c rejestru przesuwaj

,

acego jest szyfrowana za

pomoc

,

a klucza K np. algorytmem DES

3. 8 pierwszych bit´ow kryptogramu jest dodawane mo-

dulo 2 z 8 bitami reprezentuj

,

acymi liter

,

e wiadomo´sci

(M

i

) daj

,

ac kryptogram C

i

przesy lany do odbiorcy

4. C

i

jednocze´snie przesy lane jest do rejestru przesu-

waj

,

acego zajmuj

,

ac ostatnie 8 bit´ow i przesuwaj

,

ac

pozosta le bity o 8 pozycji w lewo; przesuni

,

ecie to

nie jest cykliczne, tzn. pierwszych 8 bit´ow jest
usuwanych

5. przy deszyfrowaniu rola wej´scia i wyj´scia zostaje

zamieniona

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

22

Kryptografia — wyk lad dla IV roku

PSfrag replacements

8

8

8

8

8

8

8

64

64

64

64

C

i

C

i

M

i

M

i

K

K

Kryptogram

Kryptogram

Szyfrowanie (DES)

Szyfrowanie (DES)

Rejestr przesuwaj

,

acy

Rejestr przesuwaj

,

acy

(a) Szyfrowanie

(b) Deszyfrowanie

Rysunek 3: Schemat dzia lania CFB

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

23

Kryptografia — wyk lad dla IV roku

IDEA — International Data Encryption

Algorithm

• IDEA jest algorytmem blokowym wprowadzonym w latach

90-tych

• IDEA u˙zywa kluczy 128 bitowych
• IDEA jest u˙zywana w pakiecie PGP
• IDEA jest algorytmem opatentowanym; mo˙zna go u˙zywa´c

bezp latnie do cel´ow niekomercyjnych

• IDEA dzia la na blokach 64 bitowych i wykorzystuje 3

r´o˙zne operacje: xor (

⊕), dodawanie modulo 2

16

(

) oraz

mno˙zenie modulo 2

16

+1 (

); schemat dzia lania algorytmu

przedstawiony jest na Rys. 4

Szyfrowanie

• 64 bitowy blok jest dzielony na 4 bloki po 16 bit´ow:

X

1

, X

2

, X

3

, X

4

, kt´ore stanowi

,

a dane wej´sciowe dla pierw-

szej rundy algorytmu

• algorytm sk lada si

,

e z 8 rund

• w ka˙zdej rundzie wykonywane s

,

a wymienione wy˙zej 3

typy operacji na 16 bitowych blokach z 16 bitowymi
podkluczami (ka˙zda runda wymaga 6 podkluczy)

• w wyniku otrzymuje si

,

e 4 bloki po 16 bit´ow: Y

1

, Y

2

, Y

3

, Y

4

• pomi

,

edzy rundami blok 2 i 3 s

,

a zamieniane

• algorytm ko´nczy przekszta lcenie ko´ncowe, kt´ore wymaga

4 podkluczy

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

24

Kryptografia — wyk lad dla IV roku

































PSfrag replacements

X

1

X

2

X

3

X

4

Y

1

Y

2

Y

3

Y

4

K

(1)

1

K

(1)

2

K

(1)

3

K

(1)

4

K

(1)

5

K

(1)

6

K

(9)

1

K

(9)

2

K

(9)

3

K

(9)

4

Kolejne 7 rund

Transformacja ko´

ncowa

Pierwsza runda

Rysunek

4:

Schemat dzia lania algorytmu IDEA:

⊕ — operacja xor,

— dodawanie modulo 2

16

,

 — mno˙zenie modulo 2

16

+ 1,

K

(r)

i

— i-ty podklucz dla r-tej rundy

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

25

Kryptografia — wyk lad dla IV roku

Generowanie podkluczy

• IDEA u˙zywa klucza 128 bitowego i wymaga 8×6+4=52

podklucze

1. 128 bitowy klucz jest dzielony na bloki 16 bitowe, co

daje 8 podkluczy

2. na kluczu wykonuje si

,

e przesuni

,

ecie cykliczne o 25

pozycji i znowu dzieli na bloki 16 bitowe, co daje
kolejne 8 podkluczy

3. operacj

,

e z punktu 2 powtarza si

,

e tak d lugo a˙z wygene-

ruje si

,

e wszystkie podklucze

Deszyfrowanie

• Deszyfrowanie algorytmem IDEA przebiega wg sche-

matu przedstawionego na Rys. 4, w kt´orym zamiast
X

1

, X

2

, X

3

, X

4

na wej´sciu podaje si

,

e bloki Y

1

, Y

2

, Y

3

, Y

4

kryptogramu oraz klucz K (ten sam co przy szyfrowaniu)

• z klucza K generuje si

,

e podklucze K

(r)

i

• generuje si

,

e podklucze deszyfruj

,

ace K

0(r)

i

wg schematu

przedstawionego w Tablicy 8

Runda

K

0(r)

1

K

0(r)

2

K

0(r)

3

K

0(r)

4

K

0(r)

5

K

0(r)

6

r = 1



K

(10

−r)

1



−1

−K

(10

−r)

2

−K

(10

−r)

3



K

(10

−r)

4



−1

K

(9

−r)

5

K

(9

−r)

6

2

≤ r ≤ 8



K

(10

−r)

1



−1

−K

(10

−r)

3

−K

(10

−r)

2



K

(10

−r)

4



−1

K

(9

−r)

5

K

(9

−r)

6

r = 9



K

(10

−r)

1



−1

−K

(10

−r)

2

−K

(10

−r)

3



K

(10

−r)

4



−1

—

—

Tablica 8: Tworzenie podkluczy deszyfruj

,

acych K

0(r)

i

na pod-

stawie podkluczy szyfruj

,

acych K

(r)

i

w algorytmie IDEA (dla

K

i

= 0 przyjmuje si

,

e (K

i

)

−1

= 0; 2

16

≡ −1 mod 2

16

+ 1)

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

26

Kryptografia — wyk lad dla IV roku

AES — Advanced Encryption Standard —

Rijndael

• Nowy standard przyj

,

ety w 2001 r. w USA

• algorytm blokowy, kt´ory zaprojektowali Joan Daemen i

Vincent Rijmen

• zar´owno d lugo´s´c bloku jak i klucza mo˙ze by´c wybrana

jako 128, 192 lub 256 bit´ow

• Rijndael jest og´olnie dost

,

epny

• liczba rund zale˙zy od d lugo´sci bloku
• w ka˙zdej rundzie wykonywane s

,

a 4 operacje (macierzowe):

podstawienie w S-boksie, przesuni

,

ecie wierszy, mieszanie

kolumn i xor z podkluczem

• podklucze s

,

a generowane algorytmem, kt´ory zale˙zy od

rundy

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

27

Kryptografia — wyk lad dla IV roku

Algorytmy asymetryczne — RSA

• Witfield Diffie i Martin Hellman — idea kryptografii z

kluczem publicznym, rok 1976

•

RSA

— Ron

R

ivest, Adi

S

hamir i Leonard

A

dleman, rok

1978

• bezpiecze´nstwo algorytmu RSA opiera si

,

e na trudno´sci

obliczeniowej zwi

,

azanej z rozk ladem du˙zych liczb na

czynniki (faktoryzacja)

Wybierzmy dwie du˙ze liczby pierwsze p i q i obliczmy ich
iloczyn (iloczyn latwo obliczy´c)

n

=

pq,

nast

,

epnie wybierzmy losowo liczb

,

e e < n wzgl

,

ednie pierwsz

,

a

z liczb

,

a (p

− 1)(q − 1). Liczba e b

,

edzie kluczem szyfruj

,

acym.

Teraz znajd´zmy liczb

,

e d tak

,

a, ˙ze

ed

≡ 1 (mod (p − 1)(q − 1)),

lub inaczej

d

≡ e

−1

(mod

(p

− 1)(q − 1)).

Liczby d i n s

,

a tak˙ze wzgl

,

ednie pierwsze. Do obliczenia d mo˙zna

u˙zy´c rozszerzonego algorytmu Euklidesa. Liczba d jest kluczem

deszyfruj

,

acym. Liczby

{e, n} stanowi

,

a klucz publiczny, kt´

ory

ujawniamy, za´s liczby

{d, n} stanowi

,

a klucz prywatny, kt´

ory

powinien by´c ´sci´sle chroniony (liczba d)

•

Szyfrowanie

Wiadomo´s´c dzielimy na bloki m

i

mniejsze ni˙z n, kt´ore

szyfrujemy u˙zywaj

,

ac formu ly

c

i

≡ m

e

i

(mod

n)

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

28

Kryptografia — wyk lad dla IV roku

•

Deszyfrowanie

Tekst jawny z kryptogramu otrzymujemy obliczaj

,

ac

m

i

≡ c

d

i

(mod

n)

•

Uzasadnienie

Poniewa˙z ed

≡ 1 (mod (p − 1)(q − 1)), to istnieje liczba

ca lkowita k taka, ˙ze ed = 1 + k(p

− 1)(q − 1). Z ma lego

twierdzenia Fermata, dla N W D(m, p) = 1, mamy

m

p

−1

≡ 1 (mod p)

podnosz

,

ac obie strony tej kongruencji do pot

,

egi k(q

− 1) oraz

mno˙z

,

ac przez m otrzymujemy

m

1+k(p

−1)(q−1)

≡ m (mod p)

Kongruencja ta jest tak˙ze prawdziwa dla N W D(m, p) = p,
poniewa˙z wtedy obie strony przystaj

,

a do 0

(mod

p). Zatem,

zawsze mamy

m

ed

≡ m (mod p).

Podobnie,

m

ed

≡ m (mod q),

a poniewa˙z p i q s

,

a r´

o˙znymi liczbami pierwszymi, to z chi´

nskiego

twierdzenia o resztach otrzymujemy

m

ed

≡ m (mod n)

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

29

Kryptografia — wyk lad dla IV roku

•

Przyk lad (trywialny):
Znajdowanie klucza:

p

=

1123

q = 1237

n

=

pq =

1389151

φ =

(p

− 1)(q − 1) = 1386792

e =

834781

d

≡ e

−1

(mod

φ) =

1087477

Szyfrowanie:

m

=

983415

c

≡ m

e

(mod

n)

983415

834781

(mod

1389151

) =

190489

Deszyfrowanie:

m

≡ c

d

(mod

n)

190489

1087477

(mod

1389151

) = 983415

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

30

Kryptografia — wyk lad dla IV roku

Troch

,

e matematyki

•

Podzielno´

s´

c liczb

? Dla danych liczb ca lkowitych a i b m´

owimy, ˙ze liczba b jest

podzielna przez a lub, ˙ze liczba a dzieli liczb

,

e b, je˙zeli istnieje

taka liczba ca lkowita d, ˙ze b = ad. Liczb

,

e a nazywamy

dzielnikiem liczby b, a fakt ten zapisujemy a

|b.

? Ka˙zda liczba b > 1 ma co najmniej dwa dzielniki dodatnie:

1 i b.

? Dzielnikiem nietrywialnym liczby b nazywamy dzielnik

dodatni r´

o˙zny od 1 i b.

? Liczba pierwsza to liczba wi

,

eksza od 1 nie maj

,

aca innych

dzielnik´

ow dodatnich ni˙z 1 i ona sama.

? Liczba maj

,

aca co najmniej jeden nietrywialny dzielnik jest

liczb

,

a z lo˙zon

,

a.

•

Twierdzenie o rozk ladzie na czynniki pierwsze

Ka˙zda liczba naturalna n mo˙ze by´c przedstawiona jedno-
znacznie (z dok ladno´sci

,

a do kolejno´sci czynnik´ow) jako

iloczyn liczb pierwszych.

Zwykle taki rozk lad zapisujemy jako iloczyn odpowiednich

pot

,

eg r´

o˙znych liczb pierwszych, np. 6600 = 2

3

· 3 · 5

2

· 11.

•

W lasno´

sci relacji podzielno´

sci

1. Je´sli a

|b i c jest dowoln

,

a liczb

,

a ca lkowit

,

a, to a

|bc.

2. Je´sli a

|b i b|c, to a|c

3. Je´sli a

|b i a|c, to a|b ± c

4. Je´sli liczba pierwsza p dzieli ab, to p

|a lub p|b

5. Je´sli m

|a i n|a oraz m i n nie maj

,

a wsp´

olnych dzielnik´

ow

wi

,

ekszych od 1, to mn

|a

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

31

Kryptografia — wyk lad dla IV roku

•

Najwi

,

ekszy wsp´

olny dzielnik — N W D(a, b)

Najwi

,

ekszy wsp´

olny dzielnik, N W D(a, b), dla danych dw´

och

liczb ca lkowitych (nie b

,

ed

,

acych jednocze´snie zerami), to

najwi

,

eksza liczba ca lkowita d b

,

ed

,

aca dzielnikiem zar´

owno a,

jak i b.

Przyk lad: N W D(12, 18) = 6

•

Najmniejsza wsp´

olna wielokrotno´

s´

c — N W W (a, b)

Najmniejsza wsp´

olna wielokrotno´s´c, N W W (a, b), to najmniej-

sza dodatnia liczba ca lkowita, kt´

or

,

a dziel

,

a a i b

.

N W W (a, b) = a

· b/NW D(a, b)

Przyk lad: N W W (12, 18) = 36 = 12

· 18/NW D(12, 18)

•

Liczby wzgl

,

ednie pierwsze

Liczby a i b s

,

a wzgl

,

ednie pierwsze je˙zeli N W D(a, b) = 1,

tzn. liczby a i b nie maj

,

a wsp´olnego dzielnika wi

,

ekszego

od 1.

N W D(841, 160) = 1 zatem liczby 841 i 160 s

,

a wzgl

,

ednie

pierwsze (patrz ni˙zej)

•

Algorytm Euklidesa

Algorytm Euklidesa pozwala znale´z´c N W D(a, b) w czasie
wielomianowym (dla a > b, O(ln

2

(a)))

Dla a > b, dzielimy a przez b otrzymuj

,

ac iloraz q

1

i reszt

,

e

r

1

, tzn. a = q

1

b + r

1

, w nast

,

epnym kroku b gra rol

,

e a, za´s

r

1

gra rol

,

e b: b = q

2

r

1

+ r

2

. Post

,

epowanie to kontynuujemy

dziel

,

ac kolejne reszty, r

i

−2

= q

i

r

i

−1

+ r

i

, a˙z do momentu kiedy

otrzymamy reszt

,

e, kt´

ora dzieli poprzedni

,

a reszt

,

e. Ostatnia

niezerowa reszta jest N W D(a, b).

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

32

Kryptografia — wyk lad dla IV roku

Obliczmy N W D(841, 160)

841

=

5

· 160 + 41

160

=

3

· 41 + 37

41

=

1

· 37 + 4

37

=

9

· 4 + 1

4

=

4

· 1 + 0

Poniewa˙z N W D(841, 160) = 1, to liczby 841 i 160 s

,

a wzgl

,

ednie

pierwsze.

•

Twierdzenie

Najwi

,

ekszy wsp´olny dzielnik dw´och liczb mo˙ze by´c przed-

stawiony w postaci kombinacji liniowej tych liczb ze
wsp´o lczynnikami ca lkowitymi: N W D(a, b) = xa + yb,
przy czym liczby x i y mo˙zna znale´z´c w czasie O(ln

2

(a)).

W poprzednim przyk ladzie N W D(841, 160) = 1. Korzystaj

,

ac

z ci

,

agu r´

owno´sci w algorytmie Euklidesa (id

,

ac w przeciwn

,

a

stron

,

e) otrzymujemy

1

=

37

− 9 · 4

=

37

− 9(41 − 1 · 37) = 10 · 37 − 9 · 41

=

10(160

− 3 · 41) − 9 · 41 = 10 · 160 − 39 · 41

=

10

· 160 − 39 · (841 − 5 · 160)

=

−39 · 841 + 205 · 160

Zatem x =

−39 i y = 205.

•

Rozszerzony algorytm Euklidesa

Rozszerzony algorytm Euklidesa znajduje zar´

owno najwi

,

ekszy

wsp´

olny dzielnik N W D(a, b) liczb a i b jak i liczby x i y b

,

ed

,

ace

wsp´

o lczynnikami kombinacji liniowej N W D(a, b) = xa + yb.

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

33

Kryptografia — wyk lad dla IV roku

q

r

a

b

x

x

2

x

1

y

y

2

y

1

— — 841 160

—

1

0

—

0

1

5

41 160 41

1

0

1

-5

1

-5

3

37 41

37

-3

1

-3

16

-5

16

1

4

37

4

4

-3

4

-21 16 -21

9

1

4

1

-39 4 -39 205 -21 205

Na ka˙zdyn etapie mamy r = x

· 841 + y · 160. Z ostatniego

wiersza odczytujemy:

N W D(841, 160) = 1 =

−39 · 841 + 205 · 160

Przyporz

,

adkowania w algorytmie s

,

a nast

,

epuj

,

ace:

q =

ba/bc,

r

← a − qb,

x

← x

2

− qx

1

,

y

← y

2

− qy

1

a

← b,

b

← r,

x

2

← x

1

,

x

1

← x,

y

2

← y

1

,

y

1

← y

•

Kongruencje

Dla danych trzech liczb ca lkowitych a, b i m m´owimy,

˙ze liczba a przystaje do liczby b modulo m i piszemy

a

≡ b (mod m), gdy r´o˙znica a − b jest podzielna przez

m. Liczb

,

e m nazywamy modu lem kongruencji.

W lasno´

sci

1. a

≡ a (mod m)

2. a

≡ b (mod m) wtedy i tylko wtedy, gdy b ≡

a

(mod

m)

3. Je´sli a

≡ b (mod m) oraz b ≡ c (mod m), to

a

≡ c (mod m)

4. Je´sli a

≡ b (mod m) i c ≡ d (mod m), to

a

± c ≡ b ± d (mod m) oraz ac ≡ bd (mod m)

Kongruencje wzgl

,

edem tego samego modu lu mo˙zna

dodawa´c, odejmowa´c i mno˙zy´c stronami.

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

34

Kryptografia — wyk lad dla IV roku

5. Je´sli a

≡ b (mod m), to a ≡ b (mod d) dla

ka˙zdego dzielnika d

|m

6. Je´sli a

≡ b (mod m), a ≡ b (mod n), oraz m i n

s

,

a wzgl

,

ednie pierwsze, to a

≡ b (mod mn)

7. Dla ustalonej liczby m, ka˙zda liczba przystaje modulo

m do jednej liczby zawartej pomi

,

edzy 0 i m

− 1.

Przyk lady:

27

≡ 7 (mod 5)

bo

27

− 7 = 4 · 5

27

≡ 2 (mod 5)

bo

27

− 2 = 5 · 5

−8 ≡ −7 (mod 5)

bo

−8 − 7 = −3 · 5

•

Twierdzenie

Liczbami a, dla kt´orych istnieje liczba b taka, ˙ze
ab

≡ 1 (mod m), s

,

a dok ladnie te liczby a, dla kt´o-

rych N W D(a, m) = 1. Taka liczba odwrotna b = a

−1

mo˙ze by´c znaleziona w czasie O(ln

2

(m)).

Poniewa˙z N W D(841, 160) = 1 (patrz poprzedni przyk lad), to

istnieje liczba 160

−1

(mod

841). Liczb

,

e t

,

e mo˙zna obliczy´c

za pomoc

,

a rozszerzonego algorytmu Euklidesa. Poniewa˙z

1 =

−39 · 841 + 205 · 160, to 205 · 160 ≡ 1 (mod 841), a wi

,

ec

160

−1

(mod

841) = 205.

•

Ma le twierdzenie Fermata

Niech p b

,

edzie liczb

,

a pierwsz

,

a. Wtedy ka˙zda liczba a spe l-

nia kongruencj

,

e ap

≡ a (mod p) i ka˙zda liczba a niepo-

dzielna przez p spe lnia kongruencj

,

e a

p

−1

≡ 1 (mod p).

Liczba 1231 jest liczb

,

a pierwsz

,

a i N W D(1231, 5871) = 1, wi

,

ec

5871

1230

≡

1

(mod

1231)

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

35

Kryptografia — wyk lad dla IV roku

•

Chi´

nskie twierdzenie o resztach

Je´sli liczby m

1

, m

2

, . . . , m

k

s

,

a parami wzgl

,

ednie pierw-

sze, tzn. N W D(m

i

, m

j

) = 1 dla i

6= j, wtedy uk lad

kongruencji

x

≡ a

1

(mod

m

1

)

x

≡ a

2

(mod

m

2

)

. . .

. . .

x

≡ a

k

(mod

m

k

)

ma wsp´olne rozwi

,

azanie modulo m = m

1

m

2

. . . m

k

.

Przyk lad:

x

≡ 1 (mod 11)

x

≡ 2 (mod 12)

x

≡ 3 (mod 13)

Niech M

i

= m/m

i

b

,

edzie iloczynem wszystkich modu l´

ow

z wyj

,

atkiem i-tego. Wtedy N W D(m

i

, M

i

) = 1, a wi

,

ec

istnieje taka liczba N

i

, ˙ze M

i

N

i

≡ 1 (mod m

i

), wtedy

wsp´

olnym rozwi

,

azaniem modulo m jest x =

P

i

a

i

M

i

N

i

. Dla

ka˙zdego i wszystkie sk ladniki sumy poza i-tym s

,

a podzielne

przez m

i

, gdy˙z m

i

|M

j

dla j

6= i zatem dla ka˙zdego i mamy

x

≡ a

i

M

i

N

i

≡ a

i

(mod

m

i

). W naszym przyk ladzie mamy:

a

1

= 1, a

2

= 2, a

3

= 3, m

1

= 11, m

2

= 12, m

3

= 13,

m = 1716, M

1

= 156, M

2

= 143, M

3

= 132. Aby znale´z´c

wsp´

olne rozwi

,

azanie tego uk ladu kongruencji nale˙zy znale´z´c

liczby N

i

b

,

ed

,

ace odwrotno´sciami liczb M

i

modulo m

i

. W

tym celu mo˙zemy u˙zy´c algorytmu Euklidesa. W wyniku

otrzymujemy liczby: N

1

= 6, N

2

= 11 i N

3

= 7. Zatem

wsp´

olnym rozwi

,

azaniem jest x

≡ 6 · 156 + 2 · 11 · 143 + 3 · 7 ·

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

36

Kryptografia — wyk lad dla IV roku

132

(mod

1716)

≡ 1706 (mod 1716). W tym przyk ladzie

wida´c, ˙ze liczba

−10 daje takie reszty zatem x = −10 + 1716.

•

Funkcja Eulera

Dla n

≥ 1, niech φ(n) b

,

edzie liczb

,

a tych nieujemnych

liczb b mniejszych od n, kt´ore s

,

a wzgl

,

ednie pierwsze z n.

Funkcja φ(n) nazywa si

,

e funkcj

,

a Eulera.

Funkcja Eulera φ jest

”

multiplikatywna”, tzn. φ(mn) =

φ(m)φ(n), je´sli tylko N W D(m, n) = 1.

•

Twierdzenie Eulera

Je´sli N W D(a, m) = 1, to a

φ(m)

≡ 1 (mod m).

Wniosek

Je´sli N W D(a, m) = 1 i je´sli n

0

jest reszt

,

a z dzielenia n

przez φ(m), to a

n

≡ a

n

0

(mod

m)

•

Pot

,

egowanie modulo metod

,

a iterowanego podno-

szenia do kwadratu

Podstawowym dzia laniem w kryptografii jest obliczanie
a

n

(mod

m), gdzie m i n s

,

a bardzo du˙zymi liczbami.

Zauwa˙zmy, ˙ze rozwini

,

ecie dw´ojkowe liczby n ma posta´c

n =

k

−1

X

i=0

n

i

2

i

= n

0

+ 2n

1

+ 4n

2

+

· · · + 2

k

−1

n

k

−1

,
gdzie n

i

∈ {0, 1} s

,

a cyframi rozwini

,

ecia dw´ojkowego.

Zatem

a

n

=

k

−1

Y

i=0

a

n

i

2

i

=



a

2

0



n

0



a

2

1



n

1

. . .



a

2

k

−1



n

k

−1

Za l´o˙zmy, ˙ze a < m oraz przyjmijmy, ˙ze przez b b

,

edziemy

oznaczali cz

,

e´sciowe iloczyny. Na pocz

,

atku b = 1. Je˙zeli

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

37

Kryptografia — wyk lad dla IV roku

n

0

= 1 to zast

,

epujemy b przez a, w przeciwnym przypadku

nadal b = 1. Nast

,

epnie liczymy a

1

≡ a

2

(mod

m). Je´sli

n

1

= 1, to mno˙zymy b przez a

1

i redukujemy modulo

m, za´s je´sli n

1

= 0 nie zmieniamy b. Nast

,

epnie liczymy

a

2

≡ a

2

1

(mod

m). Znowu, je´sli n

2

= 1, to mno˙zymy

b przez a

2

; w przeciwnym przypadku nie zmieniamy b.

Post

,

epuj

,

ac dalej w ten spos´ob, w j-tym kroku mamy

obliczon

,

a pot

,

eg

,

e a

j

≡ a

2j

(mod

m). Je´sli n

j

= 1 to

w l

,

aczamy a

j

do iloczynu b, je´sli n

j

= 0 to b si

,

e nie zmienia.

Po k

− 1 krokach otrzymamy b ≡ a

n

(mod

m).

Przyk lad:

Obliczmy 7

698

(mod

1234) = 287

i

0 1

2

3

4

5

6

7

8

9

n

i

0 1

0

1

1

1

0

1

0

1

a

i

7 49 1167 787 1135 1163 105 1153 391 1099

b

1 49

49

309 259

121 121

71

71

287

•

Czy wystarczy liczb pierwszych?
Twierdzenie

Niech π(x) oznacza liczb

,

e liczb pierwszych

≤ x. Wtedy

lim

x

→∞

π(x)

x/ ln x

=

1

Dla x

≥ 17

π(x)

>

x

ln x

Dla przyk ladu, dla x = 10

10

, π(x) = 455052511, natomiast

bx/ ln xc = 434294481.

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

38

Kryptografia — wyk lad dla IV roku

•

Testy pierwszo´

sci

Istniej

,

a probabilistyczne testy pierwszo´sci liczb, kt´ore

pozwalaj

,

a z du˙zym prawdopodobie´

nstwem w sko´

nczonym

czasie da´c odpowied´z czy dana liczba jest pierwsza.

Test Fermata

Testujemy czy liczba n jest pierwsza. Wybieramy losowo
liczb

,

e a < n

− 1, obliczamy r = a

n

−1

(mod

n), je´sli

r

6= 1 to n jest liczb

,

a z lo˙zon

,

a. Test przeprowadzamy

t-krotnie, t

≥ 1. Je´sli wszystkie testy wypadn

,

a pomy´slnie,

tzn. r = 1, to liczb

,

e uznajemy za pierwsz

,

a, cho´c mo˙ze tak

nie by´c.

Test Millera-Rabina

Testujemy czy liczba n jest pierwsza. Piszemy n

− 1 = 2

s

r,

gdzie r jest nieparzyste. Wybieramy losowo liczb

,

e a,

2

≤ a ≤ n − 2. Obliczamy y = a

r

(mod

n). Je´sli

y = 1 lub y = n

− 1 to n jest z lo˙zona. Obliczamy

a

2

, a

4

, . . . , (a

2

)

j

tak d lugo a˙z a

2j

≡ 1 (mod n) lub

j = s. Je´sli wszystkie (a

2

)

j

≡ 1 (mod n) to uznajemy,

˙ze liczba n jest pierwsza.

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

39

Kryptografia — wyk lad dla IV roku

Algorytm ElGamala

U podstaw dzia lania algorytmu ElGamala le˙zy matema-
tyczny problem logarytmu dyskretnego. Niech p b

,

edzie liczb

,

a

pierwsz

,

a, przez

Z

p

oznaczamy zbi´or liczb

{0, 1, . . . , p − 1} i

niech g b

,

edzie generatorem

Z

p

, tzn. takim elementem, ˙ze dla

ka˙zdej liczby 0 < a < p istnieje takie i, ˙ze a

≡ g

i

(mod

p)

(wszystkie elementy z wyj

,

atkiem zerowego mog

,

a by´c wyge-

nerowane z g).

Problem logarytmu dyskretnego polega na znalezieniu dla
danej liczby 0 < b < p takiej liczby a, ˙ze g

a

≡ b (mod p)

.

Przyk lad:

We´zmy

Z

19

, czyli zbi´

or liczb

{0, 1, . . . , 18} oraz g = 2. Niech

b = 2

a

(mod

19), mamy wtedy

a 0 1 2 3 4

5 6 7 8 9 10 11 12 13 14 15 16 17 18

b 1 2 4 8 16 13 7 14 9 18 17 15 11 3

6 12 5 10 1

•

Wyb´

or klucza

Wybieramy odpowiednio du˙z

,

a liczb

,

e pierwsz

,

a p, tak

,

a, ˙ze

obliczenie logarytmu dyskretnego jest praktycznie niewy-
konalne, wybieramy liczb

,

e ca lkowit

,

a 0 < a < p

− 1 oraz

liczb

,

e g, nast

,

epnie obliczamy b

≡ g

a

(mod

p). Liczby

{b, g, p} stanowi

,

a klucz publiczny, za´s liczby

{a, g, p} klucz

prywatny.

•

Szyfrowanie

Aby zaszyfrowa´c wiadomo´s´c M wybieramy losowo liczb

,

e

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

40

Kryptografia — wyk lad dla IV roku

k wzgl

,

ednie pierwsz

,

a z p

− 1, a nast

,

epnie obliczamy

c

1

≡ g

k

(mod

p)

c

2

≡ M b

k

(mod

p)

Para liczb c

1

i c

2

tworzy kryptogram, kt´ory jest dwukrot-

nie d lu˙zszy od tekstu jawnego.

•

Deszyfrowanie

M

= c

2

(c

a

1

)

−1

(mod

p)

•

Uzasadnienie

c

2

(c

a

1

)

−1

≡ M b

k

(g

ka

)

−1

≡ Mg

ka

(g

ka

)

−1

≡ M (mod p)

•

Prosty przyk lad
Znajdowanie klucza

Niech

p = 229

i

g = 6

, wybieramy

a = 70

, wtedy

b

≡

6

70

(mod

229) = 97

, zatem klucz publiczny stanowi

,

a liczby

{

97, 6, 229

}, za´s klucz prywatny stanowi

,

a liczby

{

70

, 6, 229

}

Szyfrowanie

Niech wiadomo´s´c M = 130, wybieramy

k = 127

takie, ˙ze

N W D(127, 228) = 1 (liczby tej nie ujawniamy)

c

1

≡

6

127

(mod

229

) =

155

c

2

≡ 130 ·

97

127

(mod

229

) =

169

Deszyfrowanie

M

=

169

· (

155

70

)

−1

(mod

229

)

≡

169

· 36 (mod

229

) = 130

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

41

Kryptografia — wyk lad dla IV roku

Jednokierunkowe funkcje hashuj

,

ace (skr´

otu)

• dla ka˙zdego X latwo jest obliczy´c H(X)
• H(X) ma tak

,

a sam

,

a d lugo´s´c dla wszystkich tekst´ow X

• dla zadanego Y znalezienie takiego X, ˙ze H(X) = Y jest

praktycznie niemo˙zliwe; funkcja

jednokierunkowa

• dla danego X trudno znale´z´c X

0

takie, ˙ze H(X) = H(X

0

);

funkcja

s labo bezkonfliktowa

• nie jest praktycznie mo˙zliwe znalezienie X i X

0

takich, ˙ze

X

6= X

0

oraz H(X) = H(X

0

); funkcja

silnie bezkonflik-

towa

Typowe zastosowania

• Przechowywanie hase l w komputerach
• Ochrona integralno´sci danych

Algorytm MD5 (Message Digest)

Algorytm, zaprojektowany przez Rivesta, jest modyfikacj

,

a

wcze´sniejszego algorytmu MD4. Wiadomo´s´c dowolnej d lu-
go´sci jest przekszta lcona w jej 128 bitowy

”

odcisk palca”

(sum

,

e kontroln

,

a, skr´ot wiadomo´sci). Zasadnicza procedura

algorytmu dzia la na blokach 512 bitowych przekszta lcaj

,

ac je

w 128 bitowe skr´oty.

Etapy MD5

•

Krok 1

Wiadomo´s´c dowolnej d lugo´sci jest uzupe lniana w taki

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

42

Kryptografia — wyk lad dla IV roku

spos´ob, ˙ze na ko´

ncu dodawany jest bit

”

1” i odpowiednia

ilo´s´c zer, tak aby ostatni blok mia l d lugo´s´c 448 bit´ow.

•

Krok 2

Do ostatniego bloku dodawana jest 64 bitowa liczba
reprezentuj

,

aca d lugo´s´c wiadomo´sci (w bitach) i w ten

spos´ob przygotowana wiadomo´s´c ma d lugo´s´c b

,

ed

,

ac

,

a

ca lkowit

,

a wielokrotno´sci

,

a 512 bit´ow. Tym samym wia-

domo´s´c jest wielokrotno´sci

,

a 16 s l´ow 32-bitowych. Niech

M

0

, M

1

, . . . M

N

−1

oznaczaj

,

a kolejne s lowa wiadomo´sci,

gdzie N jest jest wielokrotno´sci

,

a 16.

•

Krok 3

Algorytm operuje na 32-bitowych zmiennych a, b, c, d,
kt´orych warto´sci pocz

,

atkowe A, B, C, D w zapisie szest-

nastkowym s

,

a nast

,

epuj

,

ace:

A =0x67452301
B =0xefcdab89
C =0x98badcfe
D =0x10325476

•

Krok 4

G l´owna p

,

etla algorytmu sk lada si

,

e z 4 rund, w ka˙zdej

rundzie 16 razy wykonywane s

,

a operacje na 32 bitowych

s lowach. Operacje te zdefiniowane s

,

a przez 4 funkcje

F (X, Y, Z) = (X

∧ Y ) ∨ (¬X) ∧ Z)

G(X, Y, Z) = (X

∧ Z) ∨ Y ∧ (¬X)

H(X, Y, Z) = X

⊕ Y ⊕ Z

I(X, Y, Z) = Y

⊕ (X ∨ (¬Z))

gdzie

⊕ oznacza operacj

,

e xor,

∧ operacj

,

e and,

∨ operacj

,

e

or, za´s

¬ operacj

,

e not.

0

⊕ 0 = 0

0

∧ 0 = 0

0

∨ 0 = 0

¬0 = 1

0

⊕ 1 = 1

0

∧ 1 = 0

0

∨ 1 = 1

¬1 = 0

1

⊕ 0 = 1

1

∧ 0 = 0

1

∨ 0 = 1

1

⊕ 1 = 0

1

∧ 1 = 1

1

∨ 1 = 1

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

43

Kryptografia — wyk lad dla IV roku

Niech X

j

= M

i

∗16+j

oznacza j-te s lowo w i-tym bloku

wiadomo´sci M (j = 0, . . . , 15, i = 0, . . . , N/16

− 1),

←- s niech oznacza cykliczne przesuni

,

ecie w lewo o s

bit´ow oraz zdefiniujmy liczby T

k

(k = 1, . . . , 64) tak, ˙ze

T

k

=

b2

32

·| sin k|c, gdzie k jest w radianach. Mamy wtedy:

?

Runda 1

Niech [abcd j s k] oznacza operacj

,

e

a = b + ((a + F (b, c, d) + X

j

+ T

k

)

←- s),

wtedy 16 operacji tej rundy to:

[abcd

0 7 1] [dabc 1 12 2] [cdab 2 17 3] [bcda 3 22 4]

[abcd

4 7 5] [dabc 5 12 6] [cdab 6 17 7] [bcda 7 22 8]

[abcd

8 7 9] [dabc 9 12 10] [cdab 10 17 11] [bcda 11 22 12]

[abcd 12 7 13] [dabc 13 12 14] [cdab 14 17 15] [bcda 15 22 16]

?

Runda 2

Niech [abcd j s k] oznacza operacj

,

e

a = b + ((a + G(b, c, d) + X

j

+ T

k

)

←- s),

wtedy 16 operacji tej rundy to:

[abcd

1 5 17] [dabc 6 9 18] [cdab 11 14 19] [bcda 0 20 20]

[abcd

5 5 21] [dabc 10 9 22] [cdab 15 14 23] [bcda 4 20 24]

[abcd

9 5 25] [dabc 14 9 26] [cdab 3 14 27] [bcda 8 20 28]

[abcd 13 5 29] [dabc 2 9 30] [cdab 7 14 31] [bcda 12 20 32]

?

Runda 3

Niech [abcd j s k] oznacza operacj

,

e

a = b + ((a + H(b, c, d) + X

j

+ T

k

)

←- s),

wtedy 16 operacji tej rundy to:

[abcd

5 4 33] [dabc 8 11 34] [cdab 11 16 35] [bcda 14 23 36]

[abcd

1 4 37] [dabc 4 11 38] [cdab 7 16 39] [bcda 10 23 40]

[abcd 13 4 41] [dabc 0 11 42] [cdab 3 16 43] [bcda 6 23 44]
[abcd

9 4 45] [dabc 12 11 46] [cdab 15 16 47] [bcda 2 23 48]

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

44

Kryptografia — wyk lad dla IV roku

?

Runda 4

Niech [abcd j s k] oznacza operacj

,

e

a = b + ((a + I(b, c, d) + X

j

+ T

k

)

←- s),

wtedy 16 operacji tej rundy to:

[abcd

0 6 49] [dabc 7 10 50] [cdab 14 15 51] [bcda 5 21 52]

[abcd 12 6 53] [dabc 3 10 54] [cdab 10 15 55] [bcda 1 21 56]
[abcd

8 6 57] [dabc 15 10 58] [cdab 6 15 59] [bcda 13 21 60]

[abcd

4 6 61] [dabc 11 10 62] [cdab 2 15 63] [bcda 9 21 64]

? Po tych 4 rundach warto´sci a, b, c, d s

,

a dodawane do

warto´sci A, B, C, D i algorytm przechodzi do nast

,

ep-

nego bloku M .

PSfrag replacements

Runda 1

Runda 2

Runda 3

Runda 4

Blok wiadomo´sci M (512 bit´ow)

F

G

H

I

A

A

B

B

C

C

D

D

Rysunek 5:

G l´

owna p

,

etla algorytmu MD5

•

Krok 5

Po przej´sciu wszystkich 512-bitowych blok´ow wiadomo´sci
M algorytm l

,

aczy rejestry a, b, c, d daj

,

ac 128 bitow

,

a liczb

,

e

b

,

ed

,

ac

,

a warto´sci

,

a funkcji hashuj

,

acej.

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

45

Kryptografia — wyk lad dla IV roku

SHA (Secure Hash Algorithm)

Algorytm opracowany przez NIST przy udziale NSA opu-
blikowany w 1993. Nowsza wersja SHA-1 opublikowana w
1995 r. Idea tego algorytmu oparta jest na MD4 i MD5.
Warto´s´c funkcji hashuj

,

acej to liczba 160 bitowa i w zwi

,

azku

z tym algorytm wymaga 5 rejestr´ow zamiast 4. U˙zywa te˙z
w nieco inny spos´ob nieliniowych funkcji transformuj

,

acych,

dokonuje dodatkowych operacji na poszczeg´olnych s lowach
wiadomo´sci, w ka˙zdej rundzie wykonuje 20 operacji zamiast
16. Zasada dzia lania jest jednak bardzo podobna do MD5.
Og´olnie uwa˙za si

,

e, ˙ze jest bezpieczniejszy ni˙z MD5 ze wzgl

,

edu

na

”

d lu˙zsz

,

a” warto´s´c funkcji hashuj

,

acej i pewne ulepszenia

samego algorytmu.

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

46

Kryptografia — wyk lad dla IV roku

Szyfrowanie strumieniowe i generatory

ci

,

ag´

ow pseudolosowych

•

Synchroniczne szyfrowanie strumieniowe

Ci

,

ag bit´ow klucza generowany jest niezale˙znie od szyfro-

wanej wiadomo´sci i kryptogramu.

? Musi by´c zachowana synchronizacja pomi

,

edzy nadawc

,

a

i odbiorc

,

a.

? Zmiana bitu kryptogramu (przek lamanie) nie wp lywa

na mo˙zliwo´s´c deszyfrowania pozosta lych bit´ow.

? Dodanie lub usuni

,

ecie bitu powoduje utrat

,

e synchroni-

zacji.

? Istnieje mo˙zliwo´s´c zmiany wybranych bit´ow kryp-

togramu, a co za tym idzie zmiany deszyfrowanej
wiadomo´sci.

PSfrag replacements

GK

GK

K

K

k

i

k

i

m

i

m

i

c

i

c

i

(a) Szyfrowanie

(b) Deszyfrowanie

Rysunek 6:

Model synchronicznego szyfrowania strumieniowego

z dodawaniem modulo 2 (

⊕), GK jest generatorem ci

,

agu bit´

ow

klucza, za´s K jest kluczem inicjalizuj

,

acym generator

Tekst jawny szyfrowany jest bit po bicie (one-time pad).

Losowo generowane bity k

1

, k

2

, . . . , k

i

stanowi

,

a bity klucza,

kt´

ore s

,

a dodawane modulo 2 (operacja xor) do bit´

ow wia-

domo´sci m

1

, m

2

, . . . , m

i

w spos´

ob ci

,

ag ly daj

,

ac kolejne bity

kryptogramu c

1

, c

2

, . . . , c

i

, gdzie c

i

= m

i

⊕ k

i

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

47

Kryptografia — wyk lad dla IV roku

•

Samosynchronizuj

,

ace (asynchroniczne) szyfrowa-

nie strumieniowe

? CFB (Cipher Feedback) z blokiem jednobitowym

? Utrata lub dodanie bitu w kryptogramie powoduje

utrat

,

e tylko kawa lka wiadomo´sci — samosynchroniza-

cja.

? Ograniczona propagacja b l

,

ed´ow.

? Zmiana bitu kryptogramu powoduje, ˙ze kilka innych

bit´ow b

,

edzie deszyfrowanych b l

,

ednie — latwiej wykry´c

tak

,

a zmian

,

e.

? Jednak na skutek samosynchronizacji wykrycie zmian

w kryptogramie jest trudniejsze (je´sli zmiany dotycz

,

a

tylko cz

,

e´sci kryptogramu, to dalsza cz

,

e´s´c jest deszyfro-

wana poprawnie).

PSfrag replacements

b

1

b

1

b

n

−2

b

n

−2

b

n

−1

b

n

−1

b

n

b

n

G

G

K

K

k

i

k

i

m

i

m

i

c

i

c

i

(a) Szyfrowanie

(b) Deszyfrowanie

. . . . . .

. . . . . .

Rejestr przesuwaj

,

acy

Rejestr przesuwaj

,

acy

Generowane bity

Rysunek 7:

Model samosynchronizuj

,

acego szyfrowania strumie-

niowego

•

Generatory ci

,

ag´

ow pseudolosowych

Do generowania klucza potrzebny jest generator losowego
ci

,

agu bit´ow. Generowanie prawdziwie losowego ci

,

agu

jest trudne, wi

,

ec zwykle stosuje si

,

e ci

,

agi pseudolosowe.

Ci

,

agi pseudolosowe to ci

,

agi, kt´ore spe lniaj

,

a statystyczne

w lasno´sci ci

,

ag´ow losowych, ale generowane s

,

a w spos´ob

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

48

Kryptografia — wyk lad dla IV roku

deterministyczny: generator startuj

,

acy z takiego samego

stanu pocz

,

atkowego generuje taki sam ci

,

ag bit´ow. Z

tego wzgl

,

edu ci

,

agi pseudolosowe u˙zywane w kryptografii

musz

,

a spe lnia´c warunki znacznie ostrzejsze ni˙z np. ci

,

agi

pseudolosowe u˙zywane w symulacjach.

•

LFSR — Linear Feedback Shift Register

(Rejestr

przesuwaj

,

acy z liniowym sprz

,

e˙zeniem zwrotnym)

PSfrag replacements

b

1

b

2

b

3

b

4

b

5

b

6

b

7

b

n

−3

b

n

−2

b

n

−1

b

n

. . . . . .

Rejestr przesuwaj

,

acy

Generowane bity

Rysunek 8:

Generowanie ci

,

agu bit´

ow za pomoc

,

a LFSR

? LFSR posiada rejestr przesuwaj

,

acy o d lugo´sci n bit´ow,

kt´ory na pocz

,

atku zawiera losowe bity.

? Niekt´ore bity rejestru s

,

a poddawane operacji xor (

⊕)

i wynik zast

,

epuje najstarszy bit rejestru, jednocze´snie

pozosta le bity przesuwane s

,

a o jedn

,

a pozycj

,

e w prawo i

najm lodszy bit staje si

,

e kolejnym bitem generowanego

ci

,

agu.

Przyk lad:

We´zmy rejestr 4-bitowy, kt´

orego pierwszy i czwarty bit s

,

a

poddawane operacji xor i niech pocz

,

atkowo rejestr zawiera

same jedynki. Wtedy otrzymujemy nast

,

epuj

,

ace stany rejestru:

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

49

Kryptografia — wyk lad dla IV roku

1 1 1 1
0 1 1 1
1 0 1 1
0 1 0 1
1 0 1 0
1 1 0 1
0 1 1 0
0 0 1 1
1 0 0 1
0 1 0 0
0 0 1 0
0 0 0 1
1 0 0 0
1 1 0 0
1 1 1 0

Generowany ci

,

ag to najm lodsze (prawe) bity kolejnych stan´

ow

rejestru, czyli:

1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 . . .

Poniewa˙z n-bitowy rejestr mo˙ze znale´z´c si

,

e w jednym z 2

n

− 1

stan´

ow, wi

,

ec teoretycznie mo˙ze on generowa´c ci

,

ag o d lugo´sci

2

n

− 1 bit´ow. Potem ci

,

ag si

,

e powtarza. (Wykluczamy ci

,

ag

samych zer, kt´

ory daje nieko´

ncz

,

acy si

,

e ci

,

ag zer)

• LFSR ma s lab

,

a warto´s´c kryptograficzn

,

a gdy˙z znajomo´s´c

2n kolejnych bit´ow ci

,

agu pozwala na znalezienie warto´sci

generowanych od tego miejsca.

• LFSR dzia la jednak bardzo szybko, zw laszcza je´sli jest

to uk lad hardware’owy, i st

,

ad jest on bardzo atrakcyjny

w praktycznych zastosowaniach. Mo˙zna konstruowa´c
bardziej skomplikowane uk lady zawieraj

,

ace kilka LFSR

i nieliniow

,

a funkcj

,

e f przekszta lcaj

,

ac

,

a bity generowane

przez poszczeg´olne LFSR.

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

50

Kryptografia — wyk lad dla IV roku

Generowany ciag

PSfrag replacements

LFSR 1

LFSR 2

LFSR n

f

Generowane bity

Rysunek 9:

Uk lad z lo˙zony z wielu LFSR

Przyk lad: Generator Geffe

PSfrag replacements

LFSR 1

LFSR 2

LFSR n

f (x

1

, x

2

, x

3

)

x

1

x

2

x

3

¬ x

2

∧ x

3

x

1

∧ x

2

Rysunek 10:

Generator Geffe: f (x

1

, x

2

, x

3

) = (x

1

∧ x

2

)

⊕ (¬ x

2

∧ x

3

)

? Generator Geffe ma s labe w lasno´sci kryptograficzne ze

wzgl

,

edu na korelacje pomi

,

edzy generowanymi bitami i

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

51

Kryptografia — wyk lad dla IV roku

bitami LFSR 1 lub LFSR 2

Niech y(t) = f (x

1

(t), x

2

(t), x

3

(t)), wtedy

P (y(t) = x

1

(t)) = P (x

2

(t) = 1) + P (x

2

(t) = 0)

· P (x

3

(t) =

x

1

(t)) =

1
2

+

1
2

·

1
2

=

3
4

, i podobnie dla x

3

(t).

•

Generatory sterowane zegarem
Generator o zmiennym kroku

(alternating step gene-

rator)

PSfrag replacements

LFSR 1

LFSR 2

LFSR 3

Zegar

Generowane bity

Rysunek 11:

Generator o zmiennym kroku

? LFSR 1 jest przesuwany w ka˙zdym takcie zegara.

? Je´sli na wyj´sciu LFSR 1 jest 1 to LFSR 2 jest przesu-

wany; LFSR 3 nie jest przesuwany (poprzedni bit jest
powtarzany).

? Je´sli na wyj´sciu LFSR 1 jest 0 to LFSR 3 jest przesu-

wany; LFSR 2 nie jest przesuwany (poprzedni bit jest
powtarzany).

? Wyj´sciowe bity LFSR 2 i LFSR 3 s

,

a dodawane modulo

2 (

⊕) daj

,

ac kolejny bit generowanego ci

,

agu.

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

52

Kryptografia — wyk lad dla IV roku

Shrinking generator

PSfrag replacements

LFSR 1

LFSR 2

LFSR 3

Zegar

a

i

b

i

wy´slij b

i

je˙zeli a

i

= 1

opu´s´c b

i

je˙zeli a

i

= 0

Rysunek 12:

Shrinking generator

•

Generatory, kt´

orych bezpiecze´

nstwo oparte jest na

trudno´

sciach obliczeniowych

Generator Blum-Micali

W generatorze tym wykorzystuje si

,

e trudno´s´c w obliczaniu

logarytmu dyskretnego. Wybieramy dwie liczby pierwsze
a i p oraz liczb

,

e x

0

(zarodek), a nast

,

epnie obliczamy

x

i+1

= a

x

i

mod

p

dla

i = 1, 2, 3, . . .

Pseudolosowy ci

,

ag bit´ow tworzymy w nast

,

epuj

,

acy spos´ob:

k

i

=







1

je˙zeli x

i

< (p

− 1)/2

0

w przeciwnym przypadku

Generator RSA

Generator oparty na trudno´sci z faktoryzacj

,

a liczb.

Wybieramy dwie liczby pierwsze p i q (N = pq) oraz liczb

,

e

e wzgl

,

ednie pierwsz

,

a z (p

− 1)(q − 1). Wybieramy losow

,

a

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

53

Kryptografia — wyk lad dla IV roku

liczb

,

e (zarodek) x

0

mniejsz

,

a od N , a nast

,

epnie obliczamy

x

i+1

=

x

e

i

(mod

N )

generowanym bitem jest najm lodszy bit x

i

Generator Blum-Blum-Shub — BBS

Znajdujemy dwie du˙ze liczby pierwsze p i q, takie, ˙ze
p

≡ 3 (mod 4) oraz q ≡ 3 (mod 4); N = pq.

Wybieramy losow

,

a liczb

,

e x wzgl

,

ednie pierwsz

,

a z N , a

nast

,

epnie obliczamy

x

0

=

x

2

(mod

N )

x

0

stanowi zarodek dla generatora. Teraz liczymy

x

i+1

= x

2

i

(mod

N )

Generowanym bitem k

i

jest najm lodszy bit x

i+1

.

•

Generator RC 4

Generator RC 4 zosta l opracowany przez Rona Rivesta
w 1987 r. Przez kilka lat by l to algorytm tajny. W
1994 r. kto´s w Internecie opublikowa l program realizuj

,

acy

ten algorytm. Od tego czasu algorytm nie stanowi
tajemnicy. Algorytm ten pracuje w trybie

OFB (Output

Feedback)

. Ci

,

ag generowany przez RC 4 jest losowym

ci

,

agiem bajt´ow.

? Algorytm u˙zywa dw´och wska´znik´ow i, j przyjmuj

,

a-

cych warto´sci 0, 1, 2, . . . , 255 oraz S-boksu z warto-

´sciami S

0

, S

1

, . . . , S

255

, kt´ore tworz

,

a permutacj

,

e liczb

0, 1, . . . , 255.

? Inicjalizacja: Na pocz

,

atku i = j = 0, S

l

= l dla

l = 0, 1, . . . , 255, kolejna 256-bajtowa tablica wy-
pe lniana jest bajtami klucza, przy czym klucz jest

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

54

Kryptografia — wyk lad dla IV roku

u˙zywany wielokrotnie, a˙z do wype lnienia ca lej tablicy
K

0

, K

1

, . . . , K

255

. Nast

,

epnie wykonujemy:

for i = 0 to 255:
j = (j + S

i

+ K

i

)

(mod

256)

zamie´

n S

i

z S

j

? Generowanie kolejnego bajtu:

i = i + 1

(mod

256)

j = j + S

i

(mod

256)

zamie´

n S

i

z S

j

l = S

i

+ S

j

(mod

256)

K = S

l

? Otrzymany bajt K jest dodawany modulo 2 (xor)

z kolejnym bajtem wiadomo´sci daj

,

ac kolejny bajt

kryptogramu (przy deszyfrowaniu role tekstu jawnego i
kryptogramu si

,

e zamieniaj

,

a).

Algorytm RC 4 jest u˙zywany w wielu programach komer-
cyjnych.

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

55

Kryptografia — wyk lad dla IV roku

Podpis cyfrowy

Przypomnijmy:

System kryptograficzny z kluczem publicznym mo˙ze by´c
wykorzystany do podpisywania dokument´ow cyfrowych.

1. Alicja szyfruje dokument u˙zywaj

,

ac swojego klucza

prywatnego, podpisuj

,

ac w ten spos´ob dokument

2. Alicja przesy la tak podpisany dokument do Bolka

3. Bolek deszyfruje dokument u˙zywaj

,

ac klucza publicznego

Alicji, weryfikuj

,

ac w ten spos´ob podpis Alicji

•

Uwagi:

? podpis jest prawdziwy; Bolek weryfikuje go deszyfruj

,

ac

kryptogram kluczem publicznym Alicji

? podpis nie mo˙ze by´c sfa lszowany; tylko Alicja zna jej

klucz prywatny

? podpis nie mo˙ze by´c przeniesiony do innego dokumentu
? podpisany dokument nie mo˙ze by´c zmieniony; zmie-

niony dokument nie da si

,

e rozszyfrowa´c kluczem

publicznym Alicji

? podpis jest niezaprzeczalny;
? wad

,

a tego sposobu podpisywania dokument´ow jest

jednak to, ˙ze podpis jest conajmniej tak d lugi jak sam
dokument

Podpis z wykorzystaniem jednokierunkowej funkcji
hashuj

,

acej

1. Alicja u˙zywa funkcji hashuj

,

acej do dokumentu, kt´ory ma

podpisa´c, otrzymuj

,

ac skr´ot (

”

odcisk palca”) dokumentu

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

56

Kryptografia — wyk lad dla IV roku

2. Alicja podpisuje skr´ot dokumentu szyfruj

,

ac go swoim

kluczem prywatnym

3. Alicja przesy la Bolkowi dokument i podpisany skr´ot

4. Bolek u˙zywa tej samej funkcji hashuj

,

acej do otrzymania

skr´otu dokumentu, a nast

,

epnie deszyfruje podpisany

skr´ot u˙zywaj

,

ac klucza publicznego Alicji; je´sli zdeszy-

frowany skr´ot zgadza si

,

e z otrzymanym przez niego to

podpis jest prawdziwy

? podpis jest znacznie kr´otszy od dokumentu
? mo˙zna sprawdzi´c istnienie podpisu bez ogl

,

adania

samego dokumentu

Schemat ElGamala podpisu cyfrowego

•

Generowanie kluczy

? Alicja wybiera du˙z

,

a liczb

,

e pierwsz

,

a p oraz liczb

,

e

g

∈ Z

p

(generator grupy multiplikatywnej

Z

∗

p

)

? Alicja wybiera liczb

,

e losow

,

a 0 < a < p

− 1 oraz

oblicza b

≡ g

a

(mod

p)

? Kluczem publicznym Alicji s

,

a liczby

{b, g, p} za´s

kluczem prywatnym liczby

{a, g, p}

•

Podpisywanie

? Alicja wybiera liczb

,

e losow

,

a k (tajn

,

a), tak

,

a, ˙ze

0 < k < p

− 1 oraz NW D(k, p − 1) = 1

? Alicja oblicza

r = g

k

(mod

p),

k

−1

(mod

p),

s = k

−1

[H(M )

− ar] (mod p − 1).

? Podpisem Alicji dla wiadomo´sci M jest para liczb

{r, s}

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

57

Kryptografia — wyk lad dla IV roku

•

Weryfikacja

? Bolek aby stwierdzi´c prawdziwo´s´c podpisu Alicji

pobiera klucz publiczny Alicji

{b, g, p}

? Bolek sprawdza czy 0 < r < p, je´sli nie, podpis nie

jest prawdziwy

? Bolek oblicza

x

1

= b

r

r

s

(mod p),

x

2

= g

H(M )

(mod

p).

? Bolek akceptuje podpis je´sli x

1

= x

2

•

Uzasadnienie

Poniewa˙z s

≡ k

−1

[H(M )

− ar]

(mod

p

− 1), to mno˙z

,

ac

stronami przez k mamy ks

≡ H(M) − ar (mod p − 1) i

po przekszta lceniu H(M )

≡ ar + ks (mod p − 1), a co

za tym idzie g

H(M )

≡ g

ar+ks

≡ (g

a

)

r

r

s

≡ b

r

r

s

(mod

p).

Tak wi

,

ec x

1

= x

2

.

DSA — Digital Signature Algorithm

Algorytm podpisu cyfrowego zatwierdzony w 1994 r. przez
NIST jako standard podpisu cyfrowego w USA (Digital
Signature Standard — DSS). Wykorzystuje funkcj

,

e hashuj

,

ac

,

a

SHA-1.

•

Generacja klucza

? Alicja wybiera liczb

,

e pierwsz

,

a q o d lugo´sci 160 bit´ow

? Alicja wybiera liczb

,

e pierwsz

,

a p o d lugo´sci 512

≤ l ≤

1024, przy czym 64

|l, tak

,

a, ˙ze q

|p − 1

? Alicja wybiera element g

∈ Z

p

i oblicza

b = g

(p

−1)/q

(mod

p);

je´sli b = 1 to wybiera inne g.

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

58

Kryptografia — wyk lad dla IV roku

? Alicja wybiera liczb

,

e losow

,

a a, 0 < a < q, i oblicza

c = b

a

(mod

p)

? Kluczem publicznym Alicji jest zbi´or liczb

{b, c, p, q}

•

Podpisywanie

? Alicja wybiera tajn

,

a liczb

,

a losow

,

a k, 0 < k < q,

? Alicja oblicza

r = (b

k

(mod

p))

(mod

q),

k

−1

(mod

q),

s = k

−1

[H(M ) + ar]

(mod q).

? Podpisem Alicji dla wiadomo´sci M jest para liczb

{r, s}

•

Weryfikacja

? Bolek pobiera klucz publiczny Alicji

{b, c, p, q}

? Bolek sprawdza czy 0 < r < q i 0 < s < q, je´sli nie, to

podpis jest fa lszywy

? Bolek oblicza

H(M ) i w = s

−1

(mod

q),

u

1

= w H(M )

(mod

q),

u

2

= rw

(mod q),

v = (b

u

1

c

u

2

(mod

p))

(mod

q).

? Bolek uznaje podpis za prawdziwy je´sli v = r.

•

Uzasadnienie

Je´sli

{r, s} jest prawdziwym podpisem Alicji dla wiadomo´sci

M , to H(M )

≡ −ar+ks (mod q). Mno˙z

,

ac stronami przez w

i przekszta lcaj

,

ac otrzymujemy w H(M ) + arw

≡ k (mod q),

co jest r´

ownowa˙zne u

1

+ au

2

≡ k (mod q). Podnosz

,

ac b do

pot

,

egi lewej i prawej strony tej kongruencji otrzymujemy

(b

u

1

+au

2

(mod

p))

(mod

q)

≡ (b

k

(mod

p))

(mod

q)

i dalej mamy

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

59

Kryptografia — wyk lad dla IV roku

(b

u

1

c

u

2

(mod

p))

(mod

q)

≡ (b

k

(mod

p))

(mod

q),

a to oznacza v = r.

´

Slepe podpisy cyfrowe

Zasadniczym za lo˙zeniem protoko l´ow podpis´ow cyfrowych
jest, ˙ze podpisuj

,

acy dokument wie co podpisuje. Nie na-

le˙zy podpisywa´c dokument´ow wygl

,

adaj

,

acych na losowy ci

,

ag

bit´ow.

Od powy˙zszej zasady s

,

a jednak odst

,

epstwa. Przypu-

´s´cmy, ˙ze Bolek jest notariuszem, za´s Alicja chce aby Bolek

potwierdzi l notarialnie istnienie dokumentu, ale nie chce aby
ten dokument obejrza l. Mamy wtedy do czynienia z tzw.

´slepym podpisem. Wyobra´zmy sobie, ˙ze Alicja wk lada list

do koperty l

,

acznie z kalk

,

a, a potem prosi Bolka o z lo˙zenie

podpisu na zaklejonej kopercie. Po otwarciu koperty na li´scie
b

,

edzie kopia podpisu Bolka. Cyfrowo ´slepy podpis mo˙zna

zrealizowa´c korzystaj

,

ac np. z algorytmu RSA.

•

´

Slepy podpis z u˙zyciem RSA

? Alicja pobiera klucz publiczny Bolka

{e, n}

? Alicja wybiera liczb

,

e losow

,

a k, 0 < k < n,

? Alicja oblicza z = M k

e

(mod

n) i przesy la z do

Bolka

? Bolek oblicza z

d

= (M k

e

)

d

(mod

n) u˙zywaj

,

ac

swojego klucza prywatnego

{d, n} i wynik przesy la

Alicji

? Alicja oblicza s = z

d

/k

(mod

n).

Poniewa˙z

z

d

≡ (M k

e

)

d

≡ M

d

k

(mod

n), wi

,

ec z

d

/k =

M

d

k/k

≡ M

d

(mod

n), czyli s = M

d

(mod

n)

jest podpisem Bolka na wiadomo´sci M .

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

60

Kryptografia — wyk lad dla IV roku

Niezaprzeczalne podpisy cyfrowe

Podpis niezaprzeczalny nie mo˙ze by´c sprawdzony bez zgody
osoby podpisuj

,

acej. Podpisuj

,

acy nie mo˙ze si

,

e wyprze´c

swojego podpisu, ale mo˙ze tak˙ze dowie´s´c, ˙ze podpis jest
fa lszywy (je´sli jest).

•

Niezaprzeczalny podpis oparty na logarytmach
dyskretnych

Przypu´s´cmy, ˙ze stron

,

a podpisuj

,

ac

,

a dokument jest Alicja.

?

Generacja klucza

Alicja posiada klucz prywatny

{a, g, p} oraz klucz

publiczny

{b, g, p} wygenerowany jak w algorytmie

ElGamala.

?

Podpisywanie

Alicja oblicza z = M

a

(mod

p) i to jest jej podpis

dla dokumentu M

?

Weryfikacja

1. Bolek wybiera dwie liczby losowe r i s mniejsze od p,

oblicza w = z

r

b

s

(mod

p) i przesy la Alicji

2. Alicja oblicza

t = a

−1

(mod

p

− 1)

v = w

t

(mod

p)

i przesy la Bolkowi v

3. Bolek sprawdza czy v = M

r

g

s

(mod

p)

?

Uzasadnienie

Zauwa˙zmy, ˙ze v = w

t

= z

rt

b

st

= (z

t

)

r

(b

t

)

s

= (M

at

)

r

(g

at

)

s

=

M

r

g

s

(mod

p)

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

61

Kryptografia — wyk lad dla IV roku

Uwierzytelnianie

Kluczow

,

a spraw

,

a dla bezpiecze´

nstwa system´ow kompute-

rowych jest zapewnienie dost

,

epu do systemu i zasob´ow

tylko osobom do tego uprawnionym. W systemie musi wi

,

ec

by´c wbudowany mechanizm sprawdzania, czy u˙zytkownik
podaj

,

acy si

,

e za Alicj

,

e, naprawd

,

e ni

,

a jest. Do tego celu

s lu˙zy mechanizm uwierzytelniania lub identyfikacji (tutaj nie
rozr´o˙zniamy tych poj

,

e´c, chocia˙z czasem si

,

e je rozr´o˙znia).

•

Has la

Najcz

,

e´sciej stosowany system identyfikacji to system hase l.

Alicja chc

,

ac wej´s´c do sytemu podaje tajne has lo znane

tylko jej i systemowi.

?

Has la w systemie Unix

szyfrowane s

,

a programem

crypt

, kt´ory stanowi pewn

,

a modyfikacj

,

e DES. U˙zyt-

kownik wybiera o´smioliterowe has lo. Z ka˙zdego bajtu
reprezentuj

,

acego liter

,

e has la wybieranych jest 7 bit´ow,

kt´ore w rezultacie tworz

,

a 56 bitowy klucz. Klucz

ten s lu˙zy do szyfrowania 64 bitowego bloku znanego
tekstu (zwykle same zera). Wynik podlega kolejnemu
szyfrowaniu, i tak 25 razy. Dodatkowo u˙zywa si

,

e 12

bit´ow (

”

salt”) generowanych przez zegar systemowy w

momencie tworzenia has la. Bity te s

,

a wykorzystane

w permutacji rozszerzaj

,

acej DES. Wynik szyfrowania

(64 bity) plus

”

salt” (12 bit´ow) jest

”

przepakowany” i

zapisywany w postaci 11 znak´ow ASCII. Has lo prze-
chowywane jest w postaci 13 znak´ow ASCII, kt´ore
zawieraj

,

a dwa znaki

”

salt” oraz 11 znak´ow zaszyfrowa-

nego has la. Dodanie 12 bit´ow

”

salt” powoduje, ˙ze liczba

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

62

Kryptografia — wyk lad dla IV roku

mo˙zliwo´sci dla wybranego has la zwi

,

eksza si

,

e 2

12

= 4096

razy.

? W nowszych systemach stosuje si

,

e bezpieczniejsze

sposoby szyfrowania hase l, np. algorytm MD5

•

PIN — Personal Identification Number

Odmian

,

a has la jest tak˙ze PIN u˙zywany w przypadku

kart kredytowych, bankowych, czy tzw. token´ow. Jest
to zwykle liczba czterocyfrowa (czasem o´smiocyfrowa),
kt´ora ma zabezpiecza´c przed u˙zyciem karty przez osoby
niepowo lane, np. z lodzieja.

•

Protok´

o l challenge-response

Idea tego sposobu identyfikacji polega na odpowiedzi Alicji
na wyzwanie przes lane przez Bolka, kt´ora przekona Bolka,

˙ze ma do czynienie rzeczywi´scie z Alicj

,

a.

?

Protok´

o l challenge-response z tajnym kluczem

1. Alicja i Bolek dysponuj

,

a takim samym tajnym

kluczem K (algorytm symetryczny) oraz um´owili si

,

e

jakiej funkcji hashuj

,

acej H b

,

ed

,

a u˙zywa´c.

2. Alicja komunikuje si

,

e z Bolkiem przedstawiaj

,

ac si

,

e

jako Alicja

3. Bolek generuje liczb

,

e losow

,

a r

B

i wysy la j

,

a Alicji

4. Alicja oblicza H(K, r

B

) i przesy la wynik Bolkowi

5. Bolek tak˙ze oblicza H(K, r

B

) i je´sli wynik zgadza

si

,

e z wynikiem przys lanym przez Alicj

,

e to to˙zsamo´s´c

Alicji zostaje potwierdzona

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

63

Kryptografia — wyk lad dla IV roku

?

Protok´

o l challenge-response z kluczem publicz-

nym

1. Alicja komunikuje si

,

e z Bolkiem przedstawiaj

,

ac si

,

e

jako Alicja

2. Bolek generuje liczb

,

e losow

,

a r

B

i wysy la j

,

a Alicji

3. Alicja szyfruje liczb

,

e r

B

u˙zywaj

,

ac swojego klucza

prywatnego i kryptogram wysy la do Bolka

4. Bolek deszyfruje kryptogram otrzymany od Alicji

u˙zywaj

,

ac jej klucza publicznego i je´sli w wyniku

otrzyma r

B

to to˙zsamo´s´c Alicji jest potwierdzona

•

Dowody z wiedz

,

a zerow

,

a



















































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































W

D

Rysunek 13: Jaskinia

? Alicja chce przekona´c Bolka, ˙ze zna pewien sekret, ale

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

64

Kryptografia — wyk lad dla IV roku

nie chce zdradzi´c samego sekretu. Alicja twierdzi, ˙ze
potrafi otworzy´c drzwi zamykaj

,

ace przej´scie w jaskini.

? Bolek stoi przy wej´sciu do jaskini

? Alicja wchodzi do jaskini i idzie albo w lewo albo w

prawo dochodz

,

ac do drzwi zamykaj

,

acych przej´scie

? Bolek dochodzi do rozwidlenia korytarza, rzuca monet

,

a

i w zale˙zno´sci od wyniku rzutu krzyczy, nakazuj

,

ac Alicji

wyj´s´c albo z lewego korytarza albo z prawego

? Alicja wykonuje polecenie Bolka, otwieraj

,

ac drzwi je´sli

to konieczne

? Do´swiadczenie takie powtarzaj

,

a n-krotnie. Je´sli n jest

dostatecznie du˙ze, to prawdopodobie´

nstwo tego, ˙ze

Alicja wykona polecenie Bolka nie potrafi

,

ac otworzy´c

drzwi jest znikomo ma le (1/2

n

).

•

Dow´

od o wiedzy zerowej dla logarytmu dyskret-

nego

Alicja chce przekona´c Bolka, ˙ze zna warto´s´c logarytmu
dyskretnego bez zdradzanie tej warto´sci. Czyli chce
udowodni´c, ˙ze zna liczb

,

e x, kt´ora spe lnia zale˙zno´s´c

a

x

= b

(mod

p), gdzie p jest du˙z

,

a liczb

,

a pierwsz

,

a.

Oboje znaj

,

a p, a, b, natomiast Bolek nie zna x.

? Alicja generuje t liczb losowych r

1

, r

2

, . . . , r

t

mniejszych

od p

− 1

? Alicja oblicza h

i

≡ a

r

i

(mod

p) i przesy la je Bolkowi

? Alicja i Bolek wsp´olnie rzucaj

,

a t razy monet

,

a generuj

,

ac

w ten spos´ob t bit´ow b

1

, b

2

, . . . , b

t

? Dla wszystkich bit´ow Alicja oblicza i przesy la Bolkowi

nast

,

epuj

,

ace liczby

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

65

Kryptografia — wyk lad dla IV roku

r

i

je´sli b

i

= 0

s

i

= r

i

− r

j

je´sli b

i

= 1

gdzie j jest najwi

,

eksz

,

a warto´sci

,

a, dla kt´orej b

j

= 1

? Dla wszystkich bit´ow t Bolek sprawdza czy

a

r

i

≡ h

i

(mod

p)

dla b

i

= 0

a

s

i

≡ h

i

h

−1

j

(mod

p)

dla b

i

= 1

? Dla ka˙zdego i, dla kt´orego b

i

= 1, Alicja oblicza i

wysy la Bolkowi
z

i

= (x

− r

i

)

(mod

p

− 1)

? Bolek sprawdza czy a

z

i

≡ bh

−1

i

(mod

p)

•

Protok´

o l Fiata-Shamira

Bezpiecze´

nstwo tego protoko lu opiera si

,

e na trudno´sci

obliczeniowej pierwiastk´ow kwadratowych modulo n,
gdzie n jest iloczynem dw´och liczb pierwszych. Protok´o l
ten wymaga udzia lu strony trzeciej, zaufanego arbitra —
Trusted Authority (TA)

? TA wybiera dwie liczby pierwsze p i q, oblicza ich

iloczyn n = pq

? Alicja wybiera losow

,

a liczb

,

e wzgl

,

ednie pierwsz

,

a z n,

oblicza liczb

,

e v = s

2

(mod

n) i rejestruje u TA v

jako sw´oj klucz publiczny

? TA udost

,

epnia liczby n i v jako identyfikatory to˙zsa-

mo´sci Alicji

? Alicja wybiera losowo liczb

,

e r wzgl

,

ednie pierwsz

,

a z n,

oblicza x = r

2

(mod

n) i wysy la x Bolkowi

? Bolek wysy la Alicji losowy bit b

? Alicja wysy la Bolkowi

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

66

Kryptografia — wyk lad dla IV roku

r

je´sli b = 0

y = r

· s (mod n)

je´sli b = 1

? Bolek sprawdza czy

x = r

2

(mod

n)

je´sli b = 0

y

2

= x

· v (mod n)

je´sli b = 1

Pierwsza r´owno´s´c dowodzi, ˙ze Alicja zna pierwiastek
kwadratowy z x, druga natomiast dowodzi, ˙ze Ali-
cja zna s. Protok´o l ten powtarza si

,

e t razy, wtedy

prawdopodobie´

nstwo oszustwa przez Alicj

,

e wynosi

1/2

t

.

•

Protok´

o l Schnorra

Protok´o l ten opiera si

,

e na problemie logarytmu dyskret-

nego. Protok´o l wykorzystuje certyfikaty wydawane przez
TA. W etapie wst

,

epnym nale˙zy wybra´c liczb

,

e pierwsz

,

a p

oraz drug

,

a liczb

,

e pierwsz

,

a q tak

,

a, ˙ze q

|p − 1. Liczby te

powinny by´c dostatecznie du˙ze (np. p d lugo´sci 1024 bity
a q > 160 bit´ow. Wybieramy tak˙ze liczb

,

e b = g

(p

−1)/q

,

gdzie g jest generatorem

Z

p

. Ka˙zda ze stron otrzymuje

liczby

{p, q, b} oraz klucz publiczny pozwalaj

,

acy weryfi-

kowa´c podpisy TA. Ponadto nale˙zy wybra´c parametr t
(t

≥ 40, 2

t

< q), kt´ory okre´sla poziom bezpiecze´

nstwa.

? TA ustala to˙zsamo´s´c Alicji w konwencjonalny spos´ob i

przydziela jej identyfikator I

A

? Alicja wybiera losowo tajn

,

a liczb

,

e a oraz oblicza

v = b

a

(mod

p) i rejestruje v u TA

? TA generuje podpis cyfrowy S(I

A

, v) oraz wydaje Alicji

certyfikat C = (I

A

, v, S(I

A

, v)) wi

,

a˙z

,

acy I

A

z v

? Alicja wybiera liczb

,

e losow

,

a r < q i oblicza

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

67

Kryptografia — wyk lad dla IV roku

x = b

r

(mod

p)

? Alicja przesy la Bolkowi certyfikat C oraz liczb

,

e x

? Bolek sprawdza klucz publiczny Alicji sprawdzaj

,

ac

podpis TA na certyfikacie

? Bolek wybiera losowo liczb

,

e k (1

≤ k ≤ 2

t

) i wysy la j

,

a

Alicji (challenge)

? Alicja sprawdza 1

≤ k ≤ 2

t

i wysy la Bolkowi

y = ak + r

(mod

q) (response)

? Bolek oblicza z = b

y

v

k

(mod

p) i je´sli z = x uznaje,

˙ze to˙zsamo´s´c Alicji jest potwierdzona.

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

68

Kryptografia — wyk lad dla IV roku

Zarz

,

adzanie kluczami

•

Wytwarzanie kluczy

Do wytwarzania kluczy najlepiej nadaj

,

a si

,

e generatory

ci

,

ag´ow losowych.

Przyk lad: standard ANSI X9.17
E

K

(X) oznacza szyfrowanie 3-DES kluczem K wielko´sci

X. Niech V

0

b

,

edzie tajn

,

a liczb

,

a 64 bitow

,

a, a T znacznikiem

czasu, wtedy klucz losowy R

i

generuje si

,

e w nast

,

epuj

,

acy

spos´ob:
R

i

= E

K

(E

K

(T

i

)

⊕ V

i

)

V

i+1

= E

K

(E

K

(T

i

)

⊕ R

i

)

•

Przesy lanie kluczy

Je´sli Alicja i Bolek zamierzaj

,

a pos lugiwa´c si

,

e symetrycz-

nym algorytmem kryptograficznym, to potrzebuj

,

a tego

samego klucza. Alicja mo˙ze wygenerowa´c taki klucz u˙zy-
waj

,

ac generatora ci

,

ag´ow losowych, ale pozostaje problem

jak w bezpieczny spos´ob przekaza´c ten klucz Bolkowi.

•

Przechowywanie kluczy

Najbezpieczniejszym sposobem przechowywania klucza
jest zapami

,

etanie go przez Alicj

,

e. Niestety spos´ob ten

ma t

,

e wad

,

e, ˙ze Alicja mo˙ze zapomnie´c taki klucz. Klucze

mog

,

a by´c przechowywane w pami

,

eci ROM. Klucz taki

mo˙ze by´c rozdzielony na po lowy, z kt´orych jedna jest
przechowywana w terminalu a druga w pami

,

eci ROM.

W wielu sytuacjach istnieje konieczno´s´c przechowywania
kopii zapasowych klucza. Do tego celu wykorzystuje si

,

e

np. karty inteligentne. Klucze na og´o l maj

,

a struktur

,

e

hierarchiczn

,

a

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

69

Kryptografia — wyk lad dla IV roku

?

master keys

klucze znajduj

,

ace si

,

e najwy˙zej w hierarchii, takie klu-

cze nigdy nie s

,

a zmieniane. Taki klucz jest zwykle

tylko zapami

,

etywany przez u˙zytkownika lub zapisany w

urz

,

adzeniu kryptograficznym. Mo˙ze on by´c cz

,

e´sciowo

zapisany na kartach inteligentnych a cz

,

e´sciowo zapa-

mi

,

etywany przez u˙zytkownika. Master key s lu˙zy do

zabezpieczania innych kluczy.

?

klucze do szyfrowania kluczy

(keys-encrypting keys)

klucze wykorzystywane w protoko lach do uzgadniania
(przesy lania) kluczy.

?

klucze do szyfrowania danych

(data keys)

s

,

a to zwykle klucze o kr´otkim czasie wa˙zno´sci (np.

klucze sesyjne) s lu˙z

,

ace do szyfrowania danych

Uzgadnianie kluczy

•

Algorytm Diffiego-Hellmana

? Alicja i Bolek uzgadniaj

,

a dwie liczby: du˙z

,

a liczb

,

e

pierwsz

,

a p oraz liczb

,

e g, kt´ora jest generatorem

Z

p

? Alicja wybiera losowo du˙z

,

a liczb

,

e ca lkowit

,

a a < p

− 1 i

przesy la Bolkowi x = g

a

(mod

p)

? Bolek wybiera losowo du˙z

,

a liczb

,

e ca lkowit

,

a b < p

− 1 i

wysy la Alicji y = g

b

(mod

p)

? Alicja oblicza K = y

a

(mod

p)

? Bolek oblicza K = x

b

(mod

p)

Uzasadnienie:

K = y

a

= (g

b

)

a

= g

ab

(mod

p)

K = x

b

= (g

a

)

b

= g

ab

(mod

p)

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

70

Kryptografia — wyk lad dla IV roku

•

Algorytm ElGamala

? Bolek wybiera liczb

,

e pierwsz

,

a p oraz generator g w

Z

p

, a nast

,

epnie wybiera losowo liczb

,

e 0 < b < p

− 1,

oblicza g

b

(mod

p) oraz og lasza sw´oj klucz publiczny

{p, g, g

b

}

? Alicja pobiera klucz publiczny Bolka, wybiera losowo

liczb

,

e 0 < a < p

− 1 i wysy la Bolkowi

g

a

(mod

p)

obliczaj

,

ac jednocze´snie klucz K = (g

b

)

a

(mod p)

? Bolek oblicza ten sam klucz K = (g

a

)

b

(mod

p)

•

Station-to Station protocol (STS)

W tym protokole przyjmuje si

,

e, ˙ze Alicja ma certyfikat

klucza publicznego Bolka i na odwr´ot Bolek ma certyfikat
klucza publicznego Alicji. Niech E oznacza symetryczny
algorytm szyfruj

,

acy, S

A

(M ) oznacza podpis Alicji pod

wiadomo´sci

,

a M : S

A

(M ) = (H(M ))

d

A

(mod

n

A

) (RSA

na warto´sci funkcji hashuj

,

acej). Ka˙zda ze stron wybiera

odpowiedni

,

a liczb

,

e pierwsz

,

a p oraz generator g w

Z

p

.

Ka˙zda ze stron wybiera klucze RSA do podpisu.

? Alicja wybiera losowo liczb

,

e a i wysy la Bolkowi

g

a

(mod

p)

? Bolek wybiera losowo liczb

,

e b i oblicza klucz K =

(g

a

)

b

(mod

p)

? Bolek podpisuje konkatenacj

,

e g

b

, g

a

, szyfruje podpis

kluczem K i wysy la Alicji
g

b

(mod

p) oraz E

K

(S

B

(g

b

, g

a

))

? Alicja oblicza klucz K = (g

b

)

a

(mod

p), deszyfruje

otrzymane dane oraz u˙zywa klucza publicznego Bolka

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

71

Kryptografia — wyk lad dla IV roku

do sprawdzenia podpisu pod warto´sci

,

a funkcji hashu-

j

,

acej z konkatenacji obu eksponens´ow. Je´sli warto´s´c

funkcji hashuj

,

acej zgadza si

,

e z otrzyman

,

a przez ni

,

a

warto´sci

,

a, Alicja akceptuje klucz K i wysy la Bolkowi

E

K

(S

A

(g

a

, g

b

))

? Bolek deszyfruje otrzyman

,

a wiadomo´s´c, weryfikuje

podpis Alicji i je´sli wynik jest pozytywny, akceptuje
klucz K

•

Uzgadnianie klucza z szyfrowaniem

Zak ladamy, ˙ze Alicja i Bolek (u˙zytkownik i komputer)
znaj

,

a has lo P .

? Alicja generuje losowo par

,

e kluczy (publiczny i pry-

watny), szyfruje klucz publiczny K

0

u˙zywaj

,

ac algo-

rytmu symetrycznego wykorzystuj

,

acego has lo P jako

klucz i wysy la do Bolka
Alicja, E

P

(K

0

)

? Bolek deszyfruje wiadomo´s´c otrzyman

,

a od Alicji

otrzymuj

,

ac klucz K

0

, nast

,

epnie generuje klucz sesyjny

K, szyfruje ten klucz kluczem publicznym K

0

oraz

kluczem P i wysy la Alicji
E

P

(E

K

0

(K))

? Alicja deszyfruje wiadomo´s´c otrzyman

,

a od Bolka

uzyskuj

,

ac klucz K. Nast

,

epnie generuje ci

,

ag losowy r

A

,

szyfruje go kluczem K i wysy la do Bolka
E

K

(r

A

)

? Bolek deszyfruje wiadomo´s´c otrzyman

,

a od Alicji

otrzymuj

,

ac ci

,

ag r

A

, generuje w lasny ci

,

ag losowy r

B

,

szyfruje obydwa ci

,

agi kluczem K i wysy la Alicji

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

72

Kryptografia — wyk lad dla IV roku

E

K

(r

A

, r

B

)

? Alicja deszyfruje wiadomo´s´c uzyskuj

,

ac r

A

i r

B

. Je´sli

r

A

jest prawid lowe, szyfruje r

B

i wysy la do Bolka

E

K

(r

B

)

? Bolek deszyfruje wiadomo´s´c i je´sli r

B

jest prawid lowe

klucz K zostaje zaakceptowany jako klucz sesyjny.

Istniej

,

a r´o˙zne implementacje tego protoko lu, z wykorzy-

staniem algorytmu RSA czy ElGamala. Protok´o l ten
wzmacnia bezpiecze´

nstwo przy uzgadnianiu klucza sesyj-

nego.

•

ssh

secure shell

Protok´o l umo˙zliwiaj

,

acy bezpieczne logowanie si

,

e do

komputer´ow w sieci stworzony przez Tatu Yl¨onena,
kt´ory skutecznie zapobiega takim metodom ataku jak IP
Spoofing i DNS Spoofing, czy te˙z pods luchiwaniu hase l lub
transmitowanych danych. Obecnie rozwijana jest wersja
OpenSSH, na licencji GNU.

? przy instalacji programu generowana jest para klu-

czy algorytmu asymetrycznego przynale˙zna danemu
komputerowi — klucz publiczny komputera — host key

? przy uruchomieniu demona sshd generowana jest

nast

,

epna para kluczy — server keys. Publiczny jest

dost

,

epny do czytania, a prywatny jest przechowywany

w pami

,

eci komputera (nie jest zapisywany na dysku).

Co godzin

,

e para tych kluczy jest zmieniana.

? ka˙zdy u˙zytkownik generuje kolejn

,

a par

,

e kluczy (ssh-

keygen), kt´ore s lu˙z

,

a do uwierzytelniania u˙zytkownika.

Klucz prywatny jest szyfrowany.

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

73

Kryptografia — wyk lad dla IV roku

? Kiedy Alicja pr´obuje zalogowa´c si

,

e na komputer Bolka,

to komputer ten wysy la jej swoje dwa klucze publiczne
host key i server key. Komputer Alicji sprawdza czy
host key zgadza si

,

e z kluczem zapisanym w lokalnym

pliku known-hosts.

? Je´sli wszystko si

,

e zgadza to Alicja generuje losowy klucz

sesji i szyfruje go po kolei obydwoma kluczami publicz-
nymi komputera Bolka i tak uzyskany kryptogram
przesy la do Bolka.

? Bolek potrzebuje dw´och kluczy prywatnych do odszy-

frowania klucza sesyjnego

? Bolek przesy la Alicji liczb

,

e losow

,

a r

B

zaszyfrowan

,

a

kluczem publicznym Alicji.

? Alicja deszyfruje otrzymany kryptogram i odsy la

Bolkowi H(r

B

) udowadniaj

,

ac mu swoj

,

a to˙zsamo´s´c.

W ten spos´ob zostaje ustanowiony bezpieczny kana l
komunikacyjny.

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

74

Kryptografia — wyk lad dla IV roku

Kryptoanaliza

•

Podstawowe rodzaje ataku

? Atak typu

ciphertext-only

— znane s

,

a tylko krypto-

gramy — chcemy znale´z´c klucz lub tekst jawny

? Atak typu

known plaintext

— znane s

,

a pewne pary

kryptogram-tekst jawny — szukamy klucza

? Atak typu

chosen plaintext

— znane s

,

a kryptogramy

dla dowolnie wybranego tekstu jawnego

? Atak typu

chosen ciphertext

— atakuj

,

acy ma mo˙zliwo´s´c

uzyskania tekstu jawnego dla dowolnie wybranego
tekstu tajnego

? Atak typu

adaptive chosen plaintext

— atakuj

,

acy ma

mo˙zliwo´s´c wielokrotnego szyfrowania tekstu jawnego,
kt´ory jest modyfikowany w zale˙zno´sci od uzyskanych
wcze´sniej wynik´ow

•

Kryptoanaliza r´

o˙znicowa

Eli Biham i Adi Shamir w 1990 r. znale´zli metod

,

e ataku

na DES przy wybranym tek´scie jawnym, kt´ora okaza la
si

,

e bardziej efektywna ni˙z przeszukiwanie wszystkich

mo˙zliwo´sci (atak brutalny). W kryptoanalizie r´o˙znicowej
por´ownuje si

,

e pary kryptogram´ow, kt´ore powsta ly w

wyniku zaszyfrowania par tekst´ow jawnych o ustalonych
r´o˙znicach. Przypu´s´cmy, ˙ze mamy dwa bloki o r´ownej
d lugo´sci X i X

0

i wprowadzimy r´o˙znic

,

e obu blok´ow ∆X =

X

⊕X

0

(operacja dodawania modulo dwa odpowiadaj

,

acych

sobie bit´ow obu blok´ow — operacja xor — w wyniku

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

75

Kryptografia — wyk lad dla IV roku

dostajemy jedynki na tych miejscach gdzie ci

,

agi bit´ow

si

,

e r´o˙zni

,

a). Rozwa˙zmy par

,

e wej´sciow

,

a X i X

0

tekst´ow

jawnych i uwzgl

,

edniaj

,

ac fakt, ˙ze operacje liniowe nie

zmieniaj

,

a r´o˙znicy ∆X, co dotyczy tak˙ze operacji xor z

kluczem K

i

, kt´ora daje:

Y = X

⊕ K

i

, Y

0

= X

0

⊕ K

i

,

∆Y = (X

⊕ K

i

)

⊕ (X

0

⊕ K

i

) = X

⊕ X

0

= ∆X ,

a wi

,

ec przed wej´sciem do S-boksa r´o˙znice si

,

e zachowuj

,

a

i nie zale˙z

,

a od warto´sci klucza. Nieliniowym elementem

DES’a s

,

a S-boksy i r´o˙znica ∆Y zostanie przez S-boks na

og´o l zmieniona. Je´sli wynikiem dzia lania S-boksu b

,

edzie

Z = S(Y ), to r´o˙znica ∆Z = S(Y )

⊕ S(Y

0

) b

,

edzie zale˙za la

od klucza K

i

i okazuje si

,

e, ˙ze tylko niekt´ore warto´sci dla

∆Z s

,

a mo˙zliwe, a to oznacza, ˙ze mo˙zliwe jest uzyskanie

informacji o kluczu K

i

. W tablicy 9 podane s

,

a liczby

mo˙zliwych ∆Z dla danej r´o˙znicy ∆X (r´o˙znice ∆X i ∆Z
podane s

,

a uk ladzie szestnastkowym o czym przypomina

wska´znik x). Liczba znajduj

,

aca si

,

e w tablicy podzielona

przez 64 okre´sla prawdopodobie´

nstwo wyst

,

apienia danej

r´o˙znicy ∆Z. W tabeli znajdujemy wiele zer, a to oznacza,

˙ze takie r´o˙znice nie mog

,

a wyst

,

api´c. Prawdopodobie´

nstwa

wyst

,

apienia poszczeg´olnych r´o˙znic znacznie si

,

e r´o˙zni

,

a i

ten fakt jest wykorzystywany w kryptoanalizie r´o˙znicowej.
Np. dla ∆X = 1

x

istniej

,

a tylko cztery pary kt´ore daj

,

a

r´o˙znic

,

e ∆Z = F

x

. Takie pary mo˙zna wcze´sniej wyznaczy´c

i w tym przypadku s

,

a to pary:

{1E

x

, 1F

x

}, {1F

x

, 1E

x

}, {2A

x

, 2B

x

}, {2B

x

, 2A

x

}.

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

76

Kryptografia — wyk lad dla IV roku

∆X

∆Z

0

x

1

x

2

x

3

x

4

x

5

x

6

x

7

x

8

x

9

x

A

x

B

x

C

x

D

x

E

x

F

x

0

x

64 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

1

x

0 0 0 6 0 2 4 4 0 10 12 4 10 6 2 4

2

x

0 0 0 8 0 4 4 4 0 6 8 6 12 6 4 2

3

x

14 4 2 2 10 6 4 2 6 4 4 0 2 2 2 0

4

x

0 0 0 6 0 10 10 6 0 4 6 4 2 8 6 2

5

x

4 8 6 2 2 4 4 2 0 4 4 0 12 2 4 6

6

x

0 4 2 4 8 2 6 2 8 4 4 2 4 2 0 12

7

x

2 4 10 4 0 4 8 4 2 4 8 2 2 2 4 4

8

x

0 0 0 12 0 8 8 4 0 6 2 8 8 2 2 4

9

x

10 2 4 0 2 4 6 0 2 2 8 0 10 0 2 12

A

x

0 8 6 2 2 8 6 0 6 4 6 0 4 0 2 10

B

x

2 4 0 10 2 2 4 0 2 6 2 6 6 4 2 12

C

x

0 0 0 8 0 6 6 0 0 6 6 4 6 6 14 2

D

x

6 6 4 8 4 8 2 6 0 6 4 6 0 2 0 2

E

x

0 4 8 8 6 6 4 0 6 6 4 0 0 4 0 8

F

x

2 0 2 4 4 6 4 2 4 8 2 2 2 6 8 8

10

x

0 0 0 0 0 0 2 14 0 6 6 12 4 6 8 6

11

x

6 8 2 4 6 4 8 6 4 0 6 6 0 4 0 0

12

x

0 8 4 2 6 6 4 6 6 4 2 6 6 0 4 0

13

x

2 4 4 6 2 0 4 6 2 0 6 8 4 6 4 6

14

x

0 8 8 0 10 0 4 2 8 2 2 4 4 8 4 0

15

x

0 4 6 4 2 2 4 10 6 2 0 10 0 4 6 4

16

x

0 8 10 8 0 2 2 6 10 2 0 2 0 6 2 6

17

x

4 4 6 0 10 6 0 2 4 4 4 6 6 6 2 0

18

x

0 6 6 0 8 4 2 2 2 4 6 8 6 6 2 2

19

x

2 6 2 4 0 8 4 6 10 4 0 4 2 8 4 0

1A

x

0 6 4 0 4 6 6 6 6 2 2 0 4 4 6 8

1B

x

4 4 2 4 10 6 6 4 6 2 2 4 2 2 4 2

1C

x

0 10 10 6 6 0 0 12 6 4 0 0 2 4 4 0

1D

x

4 2 4 0 8 0 0 2 10 0 2 6 6 6 14 0

1E

x

0 2 6 0 14 2 0 0 6 4 10 8 2 2 6 2

1F

x

2 4 10 6 2 2 2 8 6 8 0 0 0 4 6 4

Tablica 9: Tablica rozk ladu r´o˙znic w S-boksie S

1

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

77

Kryptografia — wyk lad dla IV roku

∆X

∆Z

0

x

1

x

2

x

3

x

4

x

5

x

6

x

7

x

8

x

9

x

A

x

B

x

C

x

D

x

E

x

F

x

20

x

0 0 0 10 0 12 8 2 0 6 4 4 4 2 0 12

21

x

0 4 2 4 4 8 10 0 4 4 10 0 4 0 2 8

22

x

10 4 6 2 2 8 2 2 2 2 6 0 4 0 4 10

23

x

0 4 4 8 0 2 6 0 6 6 2 10 2 4 0 10

24

x

12 0 0 2 2 2 2 0 14 14 2 0 2 6 2 4

25

x

6 4 4 12 4 4 4 10 2 2 2 0 4 2 2 2

26

x

0 0 4 10 10 10 2 4 0 4 6 4 4 4 2 0

27

x

10 4 2 0 2 4 2 0 4 8 0 4 8 8 4 4

28

x

12 2 2 8 2 6 12 0 0 2 6 0 4 0 6 2

29

x

4 2 2 10 0 2 4 0 0 14 10 2 4 6 0 4

2A

x

4 2 4 6 0 2 8 2 2 14 2 6 2 6 2 2

2B

x

12 2 2 2 4 6 6 2 0 2 6 2 6 0 8 4

2C

x

4 2 2 4 0 2 10 4 2 2 4 8 8 4 2 6

2D

x

6 2 6 2 8 4 4 4 2 4 6 0 8 2 0 6

2E

x

6 6 2 2 0 2 4 6 4 0 6 2 12 2 6 4

2F

x

2 2 2 2 2 6 8 8 2 4 4 6 8 2 4 2

30

x

0 4 6 0 12 6 2 2 8 2 4 4 6 2 2 4

31

x

4 8 2 10 2 2 2 2 6 0 0 2 2 4 10 8

32

x

4 2 6 4 4 2 2 4 6 6 4 8 2 2 8 0

33

x

4 4 6 2 10 8 4 2 4 0 2 2 4 6 2 4

34

x

0 8 16 6 2 0 0 12 6 0 0 0 0 8 0 6

35

x

2 2 4 0 8 0 0 0 14 4 6 8 0 2 14 0

36

x

2 6 2 2 8 0 2 2 4 2 6 8 6 4 10 0

37

x

2 2 12 4 2 4 4 10 4 4 2 6 0 2 2 4

38

x

0 6 2 2 2 0 2 2 4 6 4 4 4 6 10 10

39

x

6 2 2 4 12 6 4 8 4 0 2 4 2 4 4 0

3A

x

6 4 6 4 6 8 0 6 2 2 6 2 2 6 4 0

3B

x

2 6 4 0 0 2 4 6 4 6 8 6 4 4 6 2

3C

x

0 10 4 0 12 0 4 2 6 0 4 12 4 4 2 0

3D

x

0 8 6 2 2 6 0 8 4 4 0 4 0 12 4 4

3E

x

4 8 2 2 2 4 4 14 4 2 0 2 0 8 4 4

3F

x

4 8 4 2 4 0 2 4 4 2 4 8 8 6 2 2

Tablica 9: Tablica rozk ladu r´o˙znic w S-boksie S

1

c.d.

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

78

Kryptografia — wyk lad dla IV roku

Znajomo´s´c takich par oraz prawdopodobie´

nstw ich wy-

st

,

apienia pozwala przy wykorzystaniu ataku typu chosen

plaintext uzyska´c informacj

,

e o bitach klucza. Mo˙zna w ten

spos´ob znacznie ograniczy´c przestrze´

n mo˙zliwych kluczy.

Prawdopodobnie tw´orcy DES’a zdawali sobie spraw

,

e z

mo˙zliwo´sci kryptoanalizy r´o˙znicowej, chocia˙z pojawi la si

,

e

ona p´o´zniej ni˙z sam DES. Liczba rund DES’a zosta la wy-
brana w taki spos´ob, ˙ze nawet korzystanie z kryptoanalizy
r´o˙znicowej wymaga du˙zych nak lad´ow (mocy obliczenio-
wych) dla z lamania szyfru.

•

Kryptoanaliza liniowa

Inn

,

a metod

,

a kryptoanalizy jest kryptoanaliza liniowa

zaproponowana przez Mitsuru Matsui w 1993 r. Idea
kryptoanalizy liniowej polega na opisie dzia lania urz

,

adze-

nia szyfruj

,

acego poprzez aproksymacj

,

e liniow

,

a. Mimo, ˙ze

S-boksy DES’a s

,

a elementami nieliniowymi, to mog

,

a by´c

one aproksymowane formu lami liniowymi. Oznacza to,

˙ze zale˙zno´sci liniowe aproksymuj

,

ace dzia lanie S-boksu s

,

a

spe lnione z prawdopodobie´

nstwem r´o˙znym ni˙z 1/2. Je´sli

np. wiemy, ˙ze pomi

,

edzy bitami klucza k

i

, tekstu jawnego

m

i

oraz kryptogramu c

i

zachodz

,

a z z prawdopodobie´

n-

stwem 90% zale˙zno´sci
m

15

⊕ k

2

⊕ m

7

⊕ k

6

= c

2

⊕ m

5

⊕ c

7

m

8

⊕ k

2

⊕ k

6

= c

5

⊕ c

6

,

to znaj

,

ac m

i

i c

i

mo˙zemy z takim samym prawdopo-

dobie´

nstwem wyznaczy´c k

2

⊕ k

6

. Oczywi´scie tego typu

zale˙zno´sci nale˙zy najpierw znale´z´c.

Dla DES’a przy ataku typu known plaintext kryptoanaliza
liniowa wymaga ´srednio 2

43

par tekst jawny-kryptogram

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

79

Kryptografia — wyk lad dla IV roku

do znalezienia klucza. Matsui w 1994 r. potrzebowa l 50
dni aby na 12 komputerach HP 9735 obliczy´c klucz DES’a!

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

80

Kryptografia — wyk lad dla IV roku

Algorytmy kwantowe

•

Bit kwantowy — kubit (qubit)

Klasyczny bit mo˙ze przyjmowa´c dwie warto´sci

{0, 1}.

Uk lad kwantowy, kt´ory ma dwa mo˙zliwe stany

{|0i, |1i}

mo˙ze si

,

e znajdowa´c w ka˙zdym z nich, ale tak˙ze w stanie

b

,

ed

,

acym syperpozycj

,

a stan´ow bazowych

|Ψi = a|0i + b|1i

i taki stan nazywamy

kubitem

. Oznacza to, ˙ze z prawdo-

podobie´

nstwem p

0

=

|a|

2

uk lad znajduje si

,

e w stanie

|0i i

z prawdopodobie´

nstwem p

1

=

|b|

2

w stanie

|1i, oczywi´scie

p

0

+ p

1

= 1. Stan uk ladu kwantowego mo˙zemy przedstawi´c

jako wektor na sferze Blocha

PSfrag replacements

|0i

|1i

|Ψi

Rysunek 14: Kubit na sferze Blocha

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

81

Kryptografia — wyk lad dla IV roku

•

Twierdzenie o nieklonowaniu

Nie istnieje transformacja unitarna U taka, ˙ze

U

|Ψi|0i = |Ψi|Ψi

dla dowolnego

|Ψi.

Dow´od:
Przypu´s´cmy, ˙ze istnieje U takie, ˙ze

U

|Ψi|0i = |Ψi|Ψi

U

|Φi|0i = |Φi|Φi

dla dowolnych

|Ψi i |Φi. Transformacja U reprezentowa la

by maszyn

,

e klonuj

,

ac

,

a, gdyby taka istnia la. Z unitarno´sci

U wynika jednak, ˙ze

hΨ|h0|U

†

U

|Φi|0i = hΨ|ΦihΨ|Φi

hΨ|Φih0|0i = hΨ|ΦihΨ|Φi

co nie jest prawdziwe dla dowolnych

|Ψi i |Φi, natomiast

mo˙ze zachodzi´c dla stan´ow ortogonalnych

hΨ|Φi = {0, 1}.

Stany ortogonalne (klasyczne bity) mog

,

a by´c kopiowane,

natomiast dowolne stany kwantowe nie.

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

82

Kryptografia — wyk lad dla IV roku

•

Bramki logiczne

PSfrag replacements

klasyczne

kwantowe

x

x

a

|0i + b|1i

a

|0i + b|1i

a

|1i + b|0i

a

|0i − b|1i

|1i

1

√

2

(

|0i + |1i)

S

R

Rysunek 15: Jednobitowe bramki logiczne

PSfrag replacements klasyczne

kwantowe

x

x

x

x

y

y

y

x

∧ y

x

⊕ y

x

⊕ y

CNOT

Rysunek 16: Dwubitowe bramki logiczne

W bazie stan´ow

{|0i, |1i}, mamy

|0i ≡





1

0



 ,

|1i ≡





0

1





Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

83

Kryptografia — wyk lad dla IV roku

Wtedy operacje na stanach kwantowych maj

,

a reprezenta-

cj

,

e macierzow

,

a, i tak na przyk lad

U

NOT

=





0

1

1

0





U

NOT

|0i =





0

1

1

0









1

0



 =





0

1



 ≡ |1i

Operacja przesuni

,

ecia fazy, kt´ora nie zmienia stanu

|0i za´s

stan

|1i zmienia na −|1i, ma posta´c

U

S

=





1

0

0

−1





Operacja Hadamarda, czasem nazywana pierwiastkiem
kwadratowym z NOT (

√

NOT), ma posta´c

H

=

1

√

2





1

1

1

−1





Istnieje niesko´

nczenie wiele bramek kwantowych genero-

wanych przez rotacje o k

,

at θ

U

R

(θ)

=





cos θ

− sin θ

sin θ

cos θ





oraz przesuni

,

ecia faz

U

P

(ϕ

1

, ϕ

2

)

=





e

iϕ

1

0

0

e

iϕ

2





Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

84

Kryptografia — wyk lad dla IV roku

Operacja CNOT (kontrolowane NOT) na dw´och kubitach
ma posta´c

U

CN

=















1

0

0

0

0

1

0

0

0

0

0

1

0

0

1

0















•

Problem Deutscha

Przypu´s´cmy, ˙ze mamy kwantow

,

a czarn

,

a skrzynk

,

e oblicza-

j

,

ac

,

a funkcj

,

e f (x), tzn. wykonuj

,

ac

,

a transformacj

,

e unitarn

,

a

na dw´och kubitach przedstawion

,

a poni˙zej

|xi

?

|f(x)i

f :

{0, 1} → {0, 1}

U

f

:

|xi|yi → |xi|y ⊕ f(x)i

Pytanie:

czy po jednym przebiegu kwantowego komputera mo˙zemy

stwierdzi´c, ˙ze f (0) = f (1)?

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

85

Kryptografia — wyk lad dla IV roku

We´zmy nast

,

epuj

,

acy

kwantowy obw´od

|0i

H

H

Pomiar

|1i

H

U

f

gdzie H jest kwantow

,

a bramk

,

a Hadamarda.

Dzia lanie obwodu

H :

|0i →

1

√

2

(

|0i + |1i)

|1i →

1

√

2

(

|0i − |1i)

|0i|1i →

1
2

(

|0i + |1i)(|0i − |1i)

→

1
2



(

−1)

f (0)

|0i + (−1)

f (1)

|1i



(

|0i − |1i)

→

1
2

 

(

−1)

f (0)

+ (

−1)

f (1)



|0i

+



(

−1)

f (0)

− (−1)

f (1)



|1i



1

√

2

(

|0i − |1i)

|mi =







|0i dla f(0) = f(1)
|1i dla f(0) 6= f(1)

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

86

Kryptografia — wyk lad dla IV roku

•

Kwantowy paralelizm

Przypu´s´cmy, ˙ze mamy funkcj

,

e dzia laj

,

ac

,

a na N bit´ow o

2

N

mo˙zliwych warto´sciach. Aby obliczy´c tablic

,

e funkcji

f (x) musieliby´smy policzy´c warto´s´c funkcji 2

N

razy (dla

N = 100

∼ 10

30

)! Na komputerze kwantowym dzia laj

,

acym

zgodnie z

U

f

:

|xi|0i → |xi|f(x)i

mo˙zemy wybra´c stan pocz

,

atkowy (kwantowy rejestr) w

postaci

|ψ

0

i =



1

√

2

(

|0i + |1i)



N

=

1

2

N/2

2

N

−1

X

x=0

|xi

i obliczaj

,

ac f (x) tylko raz otrzymujemy stan

|ψi =

1

2

N/2

2

N

−1

X

x=0

|xi|f(x)i

Na przyk lad, dla N = 2

|ψ

0

i =

1
2

(

|00i + |01i + |10i + |11i)

|00i → |0i
|01i → |1i
|10i → |2i
|11i → |3i

|ψ

0

i =

1
2

(

|0i + |1i + |2i + |3i)

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

87

Kryptografia — wyk lad dla IV roku

Algorytm Shora

•

Etap 1

Przygotowujemy rejestr A komputera
kwantowego w superpozycji wszyst-
kich mo˙zliwych stan´ow

•

Etap 2

Liczba, kt´or

,

a chcemy sfaktoryzowa´c

jest N , N = 15 Wybieramy liczb

,

e lo-

sow

,

a X, 1 < X < N

−1, X = 2. Wyko-

nujemy operacj

,

e B = (X

A

mod

N )

np. dla X = 2 mamy wyniki przedsta-
wione w tabelce

•

Etap 3

Obliczamy P = X

f /2

− 1; f = 4 i

sprawdzamy czy P jest dzielnikiem N
w naszym przypadku
P = 2

4/2

− 1 = 3,

P = 2

4/2

+ 1 = 5;

Hurra !!!

15/3 = 5
15/5 = 3

Rejestr A

Rejestr B

0

1

1

2

2

4

3

8

4

1

5

2

6

4

7

8

8

1

9

2

10

4

11

8

12

1

13

2

14

4

15

8

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

88

Kryptografia — wyk lad dla IV roku

Kwantowa transformata Fouriera

QF T :

|xi →

1
q

q

−1

X

y=0

e

2πixy/q

|yi

gdzie q = 2

N

•

Okres funkcji

Przygotowujemy stan

|ψ

0

i =

1

√

q

q

−1

X

x=0

|xi|f(x)i

Mierzymy drugi rejestr dostaj

,

ac

|f(x

0

)

i, co powoduje, ˙ze

pierwszy rejestr staje si

,

e superpozycj

,

a wszystkich stan´ow,

kt´ore daj

,

a warto´s´c f (x

0

) (funkcja jest okresowa z okresem

r)

1

√

a

a

−1

X

j=0

|x

0

+ jr

i , a − 1 <

q
r

< a + 1

Stosujemy QTF

1

√

qa

q

−1

X

y=0

e

2πix

0

y

a

−1

X

j=0

e

2πijry/q

|yi

Prob(y) =

a

q













1
a

a

−1

X

j=0

e

2πijry/q













2

Je´sli q/r jest ca lkowite (q/r = a), to

Prob(y) =

1
a













1
a

a

−1

X

j=0

e

2πijy/q













2

=







1
r

y = a

∗ integer

0

otherwise

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

89

Kryptografia — wyk lad dla IV roku

Kryptografia kwantowa

•

Protok´

o l BB84

(Bennett, Brassard, 1984)

Wybierzmy dwie ortonormalne bazy dla pomiaru polary-
zacji fotonu:

?

Baza prosta

(+)

Tworz

,

a j

,

a dwa stany o polaryzacji poziomej oraz

pionowej

{|→i, |↑i}

?

Baza uko´

sna

(

×)

Tworz

,

a j

,

a dwa stany o polaryzacji 45

◦

oraz polaryzacji

135

◦

{|%i, |-i}

? Zachodz

,

a nast

,

epuj

,

ace relacje

|%i =

1

√

2

(

|→i+ |↑i)

|-i = −

1

√

2

(

|→i− |↑i)

|→i =

1

√

2

(

|%i− |-i)

|↑i =

1

√

2

(

|%i+ |-i)

Wynika z nich, ˙ze pomiar polaryzacji fotonu “uko´snego”
w bazie prostej daje z prawdopodobie´

nstwem 1/2 stan

|→i lub |↑i, co oznacza, ˙ze pomiar taki nie daje ˙zad-
nych informacji o polaryzacji fotonu. To samo mo˙zemy
powiedzie´c o pomiarze fotonu “prostego” w bazie uko-

´snej. Polaryzacja prosta i polaryzacja uko´sna to dwie

wielko´sci fizyczne, kt´ore zgodnie z prawami mechaniki

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

90

Kryptografia — wyk lad dla IV roku

kwantowej

nie s

,

a wsp´

o lmierzalne

. Obowi

,

azuje tutaj

zasada nieoznaczono´

sci Heisenberga

.

?

Alfabety kwantowe

Maj

,

ac dwie bazy mo˙zemy stworzy´c dwa kwantowe

alfabety przypisuj

,

ac dw´om ortogonalnym stanom bazy

warto´sci binarne 0 i 1.

|→i ≡ 0

|↑i ≡ 1

|%i ≡ 0
|-i ≡ 1

?

Etapy BB84

1. Alicja wybiera losowo jedn

,

a z dw´och baz i jedn

,

a

z dw´och ortogonalnych polaryzacji w wybranej ba-
zie, co oznacza wyb´or jednej z czterech mo˙zliwych
polaryzacji i wysy la do Bolka foton o takiej polary-
zacji. Zgodnie z przyj

,

etymi alfabetami oznacza to

odpowiadaj

,

acy wybranym polaryzacjom ci

,

ag bit´ow.

2. Bolek losowo wybiera baz

,

e prost

,

a lub uko´sn

,

a i

wykonuje pomiar polaryzacji fotonu, kt´ory otrzyma l
od Alicji

3. Bolek notuje wyniki pomiar´ow zachowuj

,

ac je w

tajemnicy

4. Bolek publicznie informuje Alicj

,

e jakiej bazy u˙zywa l,

za´s Alicja informuje go czy by la to baza w la´sciwa czy
nie.

5. Alicja i Bolek przechowuj

,

a wyniki, dla kt´orych

Bolek u˙zy l w la´sciwej bazy. Przypisuj

,

ac tym wynikom

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

91

Kryptografia — wyk lad dla IV roku

warto´sci binarne 0 i 1 zgodnie z przyj

,

etymi alfabetami

oboje otrzymuj

,

a taki sam ci

,

ag zer i jedynek (losowy),

kt´ory mo˙ze s lu˙zy´c jako klucz kryptograficzny.

Przyk lad:

Alicja

+

×

+

×

×

+

×

×

×

+

+

+

×

↑

%

→

%

-

→

-

-

%

↑

↑

↑

%

1

0

0

0

1

0

1

1

0

1

1

1

0

Bolek

+

+

×

+

×

×

×

+

×

+

+

×

×

↑

→

%

↑

-

%

-

→

%

↑

↑

-

%

1

0

0

1

1

0

1

0

0

1

1

1

0

A/B

√

√

√

√

√

√

√

klucz

1

1

1

0

1

1

0

Por´ownuj

,

ac bity wys lane przez Alicj

,

e z bitami za-

rejestrowanymi przez Bolka mo˙zemy podzieli´c bity
zarejestrowane przez Bolka na trzy kategorie: bity
pewne (´srednio 50 %) — te dla kt´orych Bolek wybra l
prawid low

,

a baz

,

e i kt´ore mog

,

a by´c traktowane jako

klucz kryptograficzny; bity prawid lowe pomimo z lego
wyboru bazy (´srednio 25 %); bity nieprawid lowe (´sred-
nio 25 %). Prawdopodobie´

nstwo wyboru jednej z dw´och

mo˙zliwych baz wynosi 1/2, prawdopodobie´

nstwo zare-

jestrowania prawid lowej polaryzacji przy prawid lowym
wyborze bazy wynosi 1, prawdopodobie´

nstwo pomiaru

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

92

Kryptografia — wyk lad dla IV roku

prawid lowej polaryzacji przy nieprawid lowo wybranej
bazie wynosi 1/2, zatem prawdopodobie´

nstwo tego, ˙ze

zarejestrowany bit b

,

edzie prawid lowy (taki sam jak bit

wys lany) jest r´owne

1
2

· 1 +

1
2

·

1
2

=

3
4

. Prawdopodobie´

n-

stwo zarejestrowania bitu nieprawid lowego (b l

,

ednego)

wynosi wi

,

ec 1

−

3
4

=

1
4

.

Alicja

+

×

+

×

×

+

×

×

×

+

+

+

×

↑

%

→

%

-

→

-

-

%

↑

↑

↑

%

1

0

0

0

1

0

1

1

0

1

1

1

0

Bolek

+

+

×

+

×

×

×

+

×

+

+

×

×

↑

→

%

↑

-

%

-

→

%

↑

↑

-

%

1

0

0

1

1

0

1

0

0

1

1

1

0

pewne

1

1

1

0

1

1

0

dobre

0

0

0

1

z le

1

0

Je´sli Ewa pods luchuje stosuj

,

ac strategi

,

e tzw. nieprze-

´zroczystego pods luchu, to wybiera losowo baz

,

e prost

,

a

lub uko´sn

,

a, dokonuje pomiaru polaryzacji w tej bazie i

nast

,

epnie przesy la do Bolka foton o takiej polaryzacji

jak

,

a zmierzy la. Dokonywane przez Ew

,

e pomiary musz

,

a

wprowadzi´c b l

,

edy, kt´ore Alicja i Bolek mog

,

a wykry´c

przy uzgadnianiu klucza. W podanym ni˙zej przyk ladzie
ostatni bit zosta l zmieniony. ´

Srednio 25 % bit´ow klucza

zostanie zmienionych. Takie b l

,

edy Alicja i Bolek mog

,

a

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

93

Kryptografia — wyk lad dla IV roku

wykry´c wybieraj

,

ac losowo pewn

,

a liczb

,

e bit´ow klucza i

por´ownuj

,

ac publicznym kana lem ich warto´sci. Te bity

oczywi´scie nast

,

epnie si

,

e wyrzuca. Je´sli liczba b l

,

ed´ow

przekracza za lo˙zony poziom to uznaje si

,

e, ˙ze kana l

by l pods luchiwany i procedur

,

e uzgadniania klucza

rozpoczyna si

,

e od nowa.

Mechanika kwantowa nie dopuszcza mo˙zliwo´sci pasyw-
nego pods luchu. Bezpiecze´

nstwo kwantowego systemu

kryptograficznego gwarantowane jest przez prawa fizyki!

Alicja

+

×

+

×

×

+

×

×

×

+

+

+

×

↑

%

→

%

-

→

-

-

%

↑

↑

↑

%

1

0

0

0

1

0

1

1

0

1

1

1

0

Ewa

+

+

+

×

+

×

+

×

+

+

+

×

+

↑

→

→

%

→

%

↑

-

↑

↑

↑

-

→

1

0

0

0

0

0

1

1

1

1

1

1

0

Bolek

+

+

×

+

×

×

×

+

×

+

+

×

×

↑

→

%

↑

-

%

-

→

%

↑

↑

-

-

1

0

0

1

1

0

1

0

0

1

1

1

1

klucz

1

1

1

0

1

1

1

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

94

Kryptografia — wyk lad dla IV roku

•

Protok´

o l B92

(Bennett, 1992)

W 1992 r. Charles Bennett zaproponowa l protok´o l wy-
miany klucza oparty na dw´och nieortogonalnych stanach
kwantowych. Niech takimi stanami b

,

ed

,

a

{|→i, |%i}. Bo-

lek wykonuje pomiary polaryzacji w stanach ortogonalnych
do

{|→i, |%i}, tzn. w stanach {|↑i, |-i}.

?

Alfabet kwantowy

Alicja przygotowuje fotony o polaryzacji horyzontalnej
|→i lub polaryzacji 45 % |%i przypisuj

,

ac im warto´sci

binarne

|→i ≡ 0
|%i ≡ 1

?

Etapy B92

1. Alicja wybiera losowo jedn

,

a z dw´och polaryzacji

{|→i, |%i} i przesy la do Bolka foton o takiej pola-
ryzacji. Powtarzaj

,

ac t

,

e procedur

,

e, Alicja wysy la do

Bolka losowy ci

,

ag zer i jedynek.

2. Bolek losowo wybiera jeden ze stan´ow

{|↑i, |-i} i

mierzy polaryzacj

,

e w takim stanie. Je´sli wybra l po-

laryzacj

,

e ortogonaln

,

a do polaryzacji wybranej przez

Alicj

,

e, to nie zarejestruje fotonu. W przeciwnym

razie z prawdopodobie´

nstwem 1/2 zarejestruje foton.

Je´sli zarejestrowa l foton o polaryzacji

|↑i to przypi-

suje mu warto´s´c binarn

,

a 1, za´s fotonowi o polaryzacji

|-i przypisuje warto´s´c binarn

,

a 0.

3. Bolek przekazuje Alicji publicznym kana lem infor-

macj

,

e dla kt´orych foton´ow uzyska l wynik pozytywny

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

95

Kryptografia — wyk lad dla IV roku

(T), czyli zarejestrowa l foton, ale nie zdradza jak

,

a

polaryzacj

,

e zmierzy l.

4. Alicja i Bolek przechowuj

,

a ci

,

ag bit´ow, dla kt´orych

Bolek zarejestrowa l foton. Ci

,

ag ten stanowi klucz

kryptograficzny.

Przyk lad:

Alicja

%

→

→

→

%

→

%

%

→

%

%

%

→

1

0

0

0

1

0

1

1

0

1

1

1

0

Bolek

-

-

↑

-

↑

↑

↑

-

↑

-

-

↑

↑

N

T

N

T

T

N

N

N

N

N

N

T

N

0

0

1

1

A/B

√

√

√

√

klucz

0

0

1

1

Podobnie jak w przypadku protoko lu BB84 obecno´s´c
Ewy spowoduje b l

,

edy w kluczu, kt´ore Alicja i Bolek

mog

,

a wykry´c.

Kryptografia kwantowa szybko si

,

e rozwija. Tutaj przedsta-

wi lem tylko najprostsze protoko ly. Istniej

,

a inne protoko ly

kwantowe uzgadniania klucza, np. protok´o l zaproponowany
prze Ekerta w 1991 r oparty na zjawisku EPR. Do kodowania
mo˙zna u˙zywa´c np. fazy fotonu, a nie polaryzacji.

Kryptografia kwantowa jest ju˙z faktem!

.

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

96

Kryptografia — wyk lad dla IV roku

Grupa prof. Gisina w Genewie przeprowadzi la udane eks-
perymenty z kwantow

,

a dystrybucj

,

a klucza na odleg lo´sci 67

km, u˙zywaj

,

ac komercyjnych ´swiat lowod´ow. Trwaj

,

a inten-

sywne prace nad kwantow

,

a dystrybucj

,

a klucza w otwartej

przestrzeni.

Mechanika kwantowa, kt´ora z jednej strony mo˙ze spowo-
dowa´c, ˙ze klasyczne algorytmy kryptograficzne stan

,

a si

,

e

bezu˙zyteczne, z drugiej strony daje mo˙zliwo´s´c wykorzystania
jej praw do bezpiecznego przekazywania klucza kryptogra-
ficznego.

Ryszard Tana´

s, http://zon8.physd.amu.edu.pl/˜tanas

97