Rozdzia

l

2

P

o

dsta

w

o

w

e

tec

hniki

szyfro

w

ania

W niniejszym rozdziale przedstawiamy kilka klasycznych technik szyfrowania. Tech-

niki te bywaj

,

a skladnikami wielu bardziej zaawansowanych algorytmow, dlatego

poswi

,

ecimy im chwil

,

e uwagi.

2.0.6 Podstawienie

Niech

: 

!

 b

,

edzie permutacj

,

a, zas  zbiorem u_zywanych liter. Tekst jawny

a

1

a

2

:

:

:

a

n

(gdzie

a

i

2

) jest szyfrowany jako

(

a

1

)

(

a

2

)

:

:

:

(

a

n

). Kryptogram

b

1

:

:

:

b

n

odszyfrowywany jest jako

;

1

(

b

1

)

:

:

:

;

1

(

b

n

).

Przyk
lad: szyfry Cesara

Litery alfabetu mo_zna uto_zsamiac z liczbami. W

systemie Cesara u_zywanych jest 26 liter odpowiadaj

,

acych liczbom od 0 do 25.

(

i

) :=

i

+ 3 mod 26 dla

i

2

f

0



:

:

:



25

g

.

Analiza cz

,

estotliwosci

Slabosci

,

a szyfrow opartych na podstawieniach jest to, _ze mog

,

a one byc zlamane

poprzez analiz

,

e cz

,

estotliwosci wyst

,

epowania poszczegolnych liter alfabetu. Litery

alfabetu nie wyst

,

epuj

,

a bowiem z jednakow

,

a cz

,

estotliwosci

,

a { analiza tych cz

,

e-

stotliwosci w zaszyfrowanych tekstach pozwala na zgadni

,

ecie niektorych wartosci

permutacji

. Dla przykladu przyjrzyjmy si

,

e przeci

,

etnej cz

,

estotliwosci wyst

,

epo-

wania liter w tekstach w j

,

ezyku angielskim (wedlug 1]):

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

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

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

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

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

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

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

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

H - 5.14 % Y - 1.88 %

Kryptoanaliza polega na sporz

,

adzeniu tabeli cz

,

estotliwosci wyst

,

epowania liter

w zaszyfrowanym tekscie i porownania go z powy_zsz

,

a tabel

,

a. Na tej podstawie

mo_zna na przyklad zlokalizowac prawdopodobne wartosci dla

(

E

),

(

T

),

(

A

). Po

przyj

,

eciu hipotetycznych wartosci dla tych liter szukamy w kryptogramie sekwencji

12

R

OZDZIA

L

2.

PODST

A

W

O

WE

TECHNIKI

SZYFR

O

W

ANIA

13

liter odpowiadaj

,

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

to na zwerykowanie hipotezy i przyj

,

ecie prawidlowych wartosci dla E, T, A. Po

ustaleniu tych wartosci mo_zemy pokusic si

,

e o odgadni

,

ecie

(

H

) - tak by utworzyc

odpowiednio du_zo kryptogramow dla "the\. Post

,

epowanie to kontynuujemy dyspo-

nuj

,

ac coraz to wi

,

ekszymi porcjami tekstu jawnego.

Sposobem na utrudnienie analizy cz

,

estotliwosci jest szyfrowanie poprzez podsta-

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

: 

k

!



k

).

Mamy wtedy bowiem do czynienia z mniejszymi dysproporcjami w zakresie sredniej

cz

,

estotliwosci wyst

,

epowania poszczegolnych konguracji liter w bloku w szczegol-

nosci poszczegolne prawdopodobienstwa s

,

a stosunkowo malymi liczbami. Utrudnia

to odgadni

,

ecie wartosci podstawienia

. W szczegolnosci kryptoanaliza wymaga

du_zo dlu_zszych kryptogramow, aby moc skorzystac z jakichkolwiek statystycznych

prawidlowosci.

Przykladem systemu, w ktorym koduje si

,

e bloki dlugosci 2 jest system Fairplay'a

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

frowania i deszyfrowania mog

,

a byc z latwosci

,

a dokonane r

,

ecznie. System oczywiscie

gwarantuje tylko bardzo niewielki zakres bezpieczenstwa i mo_ze byc traktowany jako

dygresja w stron

,

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

Szyfrowaniu podlegaj

,

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

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

,

apiona przez

I). Do szyfrowania i deszyfrowania u_zywamy jest kwadrat 5



5, w ktory wpisujemy

kolejne litery wyst

,

epuj

,

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

DO PIWNICY\), przy czym pomijamy powtarzaj

,

ace si

,

e litery. Gdy po wpisaniu

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

niewpisane litery w kolejnosci alfabetycznej. W ten sposob wypelniamy kwadrat

25 literami. Szyfrowanie przebiega nast

,

epuj

,

aco. Zalo_zmy dla przykladu, _ze chcemy

zaszyfrowac par

,

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

,

a pro-

stok

,

at



w kwadracie do szyfrowania, w ktorego pozostalych rogach znajduj

,

a si

,

e S

i G. Regula szyfrowania mowi, _ze OH zast

,

epujemy wlasnie tymi literami, tj. SG.

Gdy para liter jak

,

a zamierzamy zaszyfrowac le_zy w jednej kolumnie lub jednym

wierszu (i wobec tego nie deniuje prostok

,

ata), to litery te zast

,

epujemy par

,

a liter

le_z

,

ac

,

a na prawo od nich, na przyklad SY zast

,

epujemy przez ZB, zas WE przez AN

(litery le_z

,

ace w pierwszej kolumnie z prawej strony zast

,

epujemy literami z ostatniej

kolumny).

Ogolnie rzecz bior

,

ac podstawienie nie oparte o dlugie bloki lub o prostych

zasadach generowania permutacji z klucza mo_ze byc podatne na analiz

,

e cz

,

estotliwo-

sci. Z tego wzgl

,

edu podstawienie nale_zy traktowac raczej jako technik

,

e pomocnicz

,

a

do wykorzystania jako element pomocniczy bardziej zlo_zonych metod.

2.0.7 XOR i one-time pad

Operacja

X

OR

(

eXclusive OR

) jest zdeniowana jak nast

,

epuje:

0

X

OR

0 = 1

X

OR

1 = 0



1

X

OR

0 = 0

X

OR

1 = 1.

Szyfrowanie przy pomocy XOR:

zalo_zmy, _ze tekst jawny jest ci

,

agiem bit-

ow

a

1



:

:

:



a

n

, zas klucz ci

,

agiem bitow

k

1



:

:

:



k

n

. Wtedy kryptogramem jest ci

,

ag

c

1



:

:

:



c

n

, gdzie

c

i

:=

a

i

X

OR

k

i

dla

i

= 1



:

:

:



n

. Deszyfrowanie oparte jest na

trzech latwych do sprawdzenia rownosciach:

x

X

OR

x

= 0



x

X

OR

0 =

x

x

X

OR

(

y

X

OR

z

) = (

x

X

OR

y

)

X

OR

z

)

:

St

,

ad

c

i

X

OR

k

i

= (

a

i

X

OR

k

i

)

X

OR

k

i

=

a

i

X

OR

(

k

i

X

OR

k

i

) =

a

i

X

OR

0 =

a

i

:

R

OZDZIA

L

2.

PODST

A

W

O

WE

TECHNIKI

SZYFR

O

W

ANIA

14



R T U V X

F G H K Q

N C Y B E

A M D I W

P O S Z L

(KR) = FV,

(OW) = LM,

(AI) = MW,

(WE) = AN

(SZ) = ZL

OH - rogi prostok

,

ata



 OH

zast

,

epowany jest poprzez litery

znajduj

,

ace si

,

e w pozostalych rogach

prostok

,

ata



 tj. przez SG

szyfrowanie:

szyfrowanie tekstu jawnego KR

j

OW

j

A I

j

WE

j

SZ

R T U V X

F G H K Q

N C Y B E

A M D I W

P O S Z L

pozostale litery

w kolejnosci alfabetycznej

haslo:

"POSZLA MALPA DO PIWNICY\

klucz: kwadrat 5



5 zawiera wszystkie litery z waj

,

atkiem J,

ktore w tekscie jawnym zast

,

epujemy poprzez I

Rysunek 2.1: System Playfair'a

Szyfrowanie przy pomocy

X

OR

ma wielorakie zastosowania. Jednym z nich jest

one-time pad

.

One-time pad

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

brany klucz

k

1



:

:

:



k

n

. Samo szyfrowanie odbywa si

,

e przy pomocy

X

OR

. Istotne

jest, by do ka_zdego szyfrowania u_zywac

innego, wygenerowanego niezale_znie

klucza

. Zasadzie tej metoda zawdzi

,

ecza sw

,

a nazw

,

e.

Nast

,

epuj

,

ace wlasnosci s

,

a kluczowe dla metody one-time pad:



Kryptogram jest tak_ze ci

,

agiem losowym

n

bitow, tzn. ma ten sam rozklad

prawdopodobienstwa co ci

,

agi bitow wygenerowane przez rzucanie monet

,

a

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



Bez znajomosci klucza

_zadna

informacja dotycz

,

aca tekstu jawnego nie mo_ze

byc wydedukowana z kryptogramu (bez wzgl

,

edu na zastosowane moce obli-

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

Dla udowodnienia pierwszej wlasnosci zauwa_zmy, _ze jesli

k

i

=

a

i

, to

c

i

= 0, oraz

_ze

c

i

= 1 w przeciwnym wypadku. Zatem prawdopodobienstwo, _ze

c

i

= 0 jest rowne

1

2

niezale_znie od wartosci

a

i

. Zatem

i

-ty bit kryptogramu jest losowy. Poniewa_z

bity

k

i

s

,

a losowane niezale_znie od siebie, wi

,

ec i bity kryptogramu s

,

a niezale_zne, tak

jak w przypadku ci

,

agow jakie otrzymujemy rzucaj

,

ac monet

,

a.

Niech

c

1

:

:

:

c

n

b

,

edzie dowolnym ci

,

agiem bitow. Dla udowodnienia drugiej wlas-

nosci zauwa_zmy, _ze dla ka_zdego tekstu jawnego

d

1

:

:

:

d

n

istnieje dokladnie jeden

R

OZDZIA

L

2.

PODST

A

W

O

WE

TECHNIKI

SZYFR

O

W

ANIA

15

klucz

k

1

:

:

:

k

n

taki, _ze poprzez szyfrowanie otrzymujemy kryptogram

c

1

:

:

:

c

n

. Istot-

nie, dla

i

= 1



:

:

:



n

spelniona musi byc rownosc

c

i

=

d

i

X

OR

k

i

, sk

,

ad

k

i

=

d

i

X

OR

c

i

.

Poniewa_z kryptogram

c

1

:

:

:

c

n

odpowiada ka_zdemu mo_zliwemu tekstowi jawnemu

z takim samym prawdopodobienstwem, nic nie mo_zna wywnioskowac o ksztalcie

tekstu jawnego bez znajomosci klucza.

Zastosowania one-time pad:

jedn

,

a dziedzin

,

a zastosowan jest szyfrowanie sto-

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

gicznym znaczeniu (na przyklad o wystrzeleniu rakiet j

,

adrowych). U_zywanie w

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

niesie niebezpieczenstwo, _ze faktycznie szyfry zostan

,

a zlamane.

Problemy ze stosowaniem one-time pad:

zasady u_zywania one-time pad

mowi

,

a, _ze klucz



musi byc zawczasu uzgodniony przez osoby komunikuj

,

ace si

,

e



musi byc wybrany naprawd

,

e losowo (co technicznie nie jest latwe,

patrz rozdzial 7)



musi byc przechowywany w bezpieczny sposob



musi byc co najmniej tak dlugi jak szyfrowany tekst.

Ka_zdy z powy_zszych warunkow stwarza niedogodnosci dla u_zytkownikow i zaw

,

e_za

pole praktycznych zastosowan one-time pad.

Niebezpieczenstwo u_zycia wielokrotnie tego samego klucza:

Zalo_zmy, _ze

szyfrujemy dlugi tekst

a

0

a

1

:

:

:

przy pomocy klucza dlugosci

n

. Poniewa_z brakuje

nam bitow klucza, u_zywamy nast

,

epuj

,

acej formuly:

c

i

=

a

i

X

OR

k

i

mod

n

:

Inaczej mowi

,

ac, bloki dlugosci

n

szyfrujemy ka_zdorazowo przy pomocy tego samego

klucza

k

0

:

:

:

k

n;

1

. Zauwa_zmy, _ze wtedy

c

j

X

OR

c

n

+

j

= (

a

j

X

OR

k

j

)

X

OR

(

a

n

+

j

X

OR

k

j

) =

a

j

X

OR

a

n

+

j

:

Zatem z latwosci

,

a mo_zna bez znajomosci klucza na podstawie samego kryptogramu

obliczyc

a

j

X

OR

a

n

+

j

!

Zlamanie tak skonstruowanego kryptogramu mo_ze si

,

e odbywac wedlug nast

,

e-

puj

,

acego scenariusza. Z du_zym prawdopodobienstwem ka_zdy tekst zawiera dlugie

ci

,

agi spacji. Zakladaj

,

ac, _ze

a

j

jest spacj

,

a mo_zna obliczyc

a

j

+

n

. Czyni

,

ac tak dla

ka_zdego

j

otrzymujemy pewien tekst. Szukamy w nim zrozumialych fragmentow.

W miejscach, gdzie

n

pozycji do tylu w tekscie jawnym wyst

,

epuje blok spacji

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

to dysponujemy bitami

a

i

,

c

i

dla odpowiednich

i

. St

,

ad wyliczamy

k

i

mod

n

=

a

i

X

OR

c

i

. Znalezione wartosci klucza u_zywamy nast

,

epnie dla calego kryptogramu w

celu odszyfrowania innych fragmentow tekstu jawnego. Prac

,

e mo_zna kontynuowac

probuj

,

ac zgadn

,

ac kolejne wartosci

k

i

na granicy odszyfrowanych regionow spraw-

dzaj

,

ac czy prowadzi to do sensownego uzupelnienia odgadni

,

etych fragmentow tekstu

jawnego.

2.0.8 S-boksy

S-boksy s

,

a nadzwyczaj istotnymi skladnikami algorytmu DES (

D

ata

E

ncryption

S

tandard) najwa_zniejszego w praktyce algorytmu szyfruj

,

acego w momencie powsta-

wania tej ksi

,

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



16

zawieraj

,

ac

,

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

R

OZDZIA

L

2.

PODST

A

W

O

WE

TECHNIKI

SZYFR

O

W

ANIA

16

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

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

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

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

argument= 111010, wynik= 10

10

= 1010

2

wiersz 2, kolumna 13

-

6

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

nazwie S1)

Sposob dzia
lania S-boksow.

S-boks deniuje funkcj

,

e, ktorej argumentami s

,

a

ci

,

agi zlo_zone z 6 bitow, a wartosciami ci

,

agi zlo_zone z 4 bitow. Obliczenie wartosci

dla argumentu

x

ma nast

,

epuj

,

acy przebieg:



pierwszy i ostatni bit argumentu

x

tworz

,

a liczb

,

e w systemie dwojkowym wy-

znaczaj

,

ac

,

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



pozostale 4 bity

x

wyznaczaj

,

a numer kolumny (kolumny numerujemy od 0 do

15),



na przeci

,

eciu wyznaczonych kolumny i wiersza znajduje si

,

e pojedynczy ele-

ment, liczba ta jest szukan

,

a wartosci

,

a funkcji.

Wybor liczb znajduj

,

acych si

,

e w S-boksie ma fundamentalne znaczenie dla jakosci

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

jawnym, znanych jest jednak kilka regul, ktore wzi

,

eto pod uwag

,

e. Nie jest znana

_zadna prosta i elegancka analiza matematyczna, ktora prowadzilaby do wyboru

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

,

a S-boksy o nazwach S1, S2,

:

:

:

, S8.

Efekt lawinowy:

Jedn

,

a z podstawowych zasad szyfrowania jest to, by zmiana

pojedynczego bitu w tekscie jawnym powodowala zmian

,

e wielu bitow w kryptogra-

mie. W idealnej sytuacji powinno to powodowac zmian

,

e mniej wi

,

ecej tylu bitow,

ile bysmy zmienili w wypadku ich ustawienia wedlug rzutow monet

,

a. Tym samym

podobne teksty jawne nie maj

,

a podobnych kryptogramow!Wlasnosc ta utrudnia

w znacz

,

acy sposob kryptoanaliz

,

e. W tej sytuacji mowimy o

efekcie lawinowym

,

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

,

e

zmian w kryptogramie.

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

do bitow (

x

y 

z



u

v 

w

) to zmiana

x

lub

w

powoduje zmian

,

e numeru wiersza. Rzut

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

,

a do siebie podobne.

Dlatego nie ma _zadnego powodu, by po zmianie

x

lub

w

wynik przypominal w

jakikolwiek sposob stary wynik. Podobne zjawisko odnosi si

,

e do kolumn, gdy_z

kolumny S-boksu rownie_z nie s

,

a podobne.

Gdy S-boksy s

,

a u_zywane wielokrotnie, wtedy efekt lawinowy ulega spot

,

egowaniu

i sposob w jaki zmiana pojedynczego bitu wplywa na zmian

,

e koncowego wyniku jest

coraz bardziej skomplikowany.

Kryteria wyboru S-boksow:

Poni_zej omawiamy niektore wa_zne wlasnosci, ja-

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

na zasadzie

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

.

R

OZDZIA

L

2.

PODST

A

W

O

WE

TECHNIKI

SZYFR

O

W

ANIA

17



Ka_zdy wiersz S-boksu zawiera wszystkie liczby calkowite od

0

do

15

.

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

o wartosci koncowej.



Funkcja obliczana przez S-boks nie jest funkcj

,

a aniczn

,

a,

tzn. _zaden bit wyniku nie da si

,

e przedstawic jako

c

0

+

P

6

i

=1

c

i



x

i

, gdzie

x

i

oznacza

i

-ty bit argumentu, zas operacje arytmetyczne wykonywane s

,

a

modulo 2. Gdyby bity wyniku byly wyra_zalne za pomoc

,

a funkcji anicznych,

to kryptoanaliza bylaby powa_znie ulatwiona. Istotnie, po pierwsze skladanie

S-boksow nie mialoby sensu { dalej poruszalibysmy si

,

e w obr

,

ebie funkcji

anicznych, bo zlo_zenie funkcji anicznych jest funkcj

,

a aniczn

,

a. Po drugie,

kryptoanaliza ograniczalaby si

,

e do rozwi

,

azywania ukladow rownan liniowych,

co nie jest trudnym zadaniem.



Zmiana jednego bitu argumentu zmienia co najmniej dwa bity wyniku.

Wlasnosc ta ma zapewnic efekt lawinowy w przypadku wielokrotnego zasto-

sowania S-boksow.



Dla ka_zdego argumentu

x

wartosci obliczane przez S-boks dla argumentow

x

oraz

x

X

OR

001100

ro_zni

,

a si

,

e co najmniej na dwoch pozycjach.



Dla ka_zdego argumentu

x

oraz

e

f

2

f

0



1

g

wartosci obliczane przez S-boks dla

x

oraz

x

X

OR

11

ef

00

ro_zni

,

a si

,

e co najmniej na dwoch pozycjach.



Jesli ustalimy wartosc jednego bitu argumentu oraz jedn

,

a pozycj

,

e wyniku, to dla

okolo polowy ustawien pozostalych bitow argumentu na wybranej pozycji wyniku

otrzymamy

0

.

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

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

,

esto-

sciami jak w wypadku losowania bitow przy pomocy rzutow monet

,

a.

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

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

cowa i liniowa (patrz rozdz. 12).