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 P TOGRAF 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/N W D(a, b)

Przyk lad: N W W (12, 18) = 36 = 12 · 18/N W 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

≡ M g

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 N W 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