Rozdzia

l

3

Algorytmy symetryczne

3.1

DES

{

Data

Encryption

Standard

Zanim przejdziemy do technicznego opisu algorytmu DES, sformulujmy kilka ogol-

nych uwag na jego temat:

DES jest symetrycznym algorytmem szyfruj

,

acym, ten sam klucz jest u_zywany

do szyfrowania i deszyfrowania.

Szczegolowy opis algorytmu DES zostal celowo opublikowany. Chodzilo o

przekonanie potencjalnych u_zytkownikow, _ze bezpieczenstwo metody nie tkwi

w tajnosci jej budowy, ale w konstrukcji odpornej na kryptoanaliz

,

e. Bowiem

ka_zda metoda, ktorej szczegoly nie zostaly ujawnione, mo_ze zawierac w sobie

tzw.

tylne drzwi

, czyli miejsce w algorytmie, ktore mo_ze byc wykorzystane

przez przeciwnika znaj

,

acego szczegoly algorytmu na zdobycie informacji nie-

dost

,

epnych w zwyklym trybie (na przyklad dotycz

,

ace u_zywanych kluczy).

DES jest znacz

,

aco szybszy, gdy jest zaimplementowany jako hardware a nie

jako software. Algorytm zostal celowo tak zaprojektowany, aby zniecz

,

ecic do

u_zywania implementacji software'owych uwa_zanych za bardziej podatne na

atak (latwiej jest si

,

e wlamac do systemu i niepostrze_zenie wymienic software,

ni_z dokonac zycznego wlamania by wymienic hardware). Uklady realizuj

,

ace

DES s

,

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

ware na PC mo_ze miec pr

,

edkosc tysi

,

ace razy ni_zsz

,

a.

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

patrzona w bit parzystosci. Klucze skladaj

,

a si

,

e rownie_z z 64 bitow, przy

czym 8 bitow jest bitami parzystosci. Tak wi

,

ec w istocie w trakcie wyboru

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

Post

,

ep w dziedzinie technologii i zwi

,

azane z tym obni_zenie kosztow kry-

ptoanalizy wyzwolily dyskusje, czy dlugosc kluczy DES-a nie jest za mala.

Koszty znalezienia klucza na podstawie dostatecznej ilosci par tekst jawny{

kryptogram zaszyfrowany tym kluczem bywaj

,

a szacowane jedynie na miliony

dolarow USA.

DES zostal w USA uznany za standard dla celow niemilitarnych. Zostal

wst

,

epnie zaprojektowany w osrodku badawczym IBM w Yorktown Heights,

a nast

,

epnie zmodykowany przez NSA (National Security Agency), rz

,

adowy

organ w USA zajmuj

,

acy si

,

e problemami bezpieczenstwa narodowego. Wywo-

lalo to wiele podejrzen, _ze NSA zna

tylne drzwi

umo_zliwiaj

,

acejlamanieszyfrow

generowanych przy pomocy DES-a. Poniewa_z DES stal si

,

e w mi

,

edzyczasie

18

R

OZDZIA

L

3.

ALGOR

YTMY

SYMETR

YCZNE

19

standardem w zastosowaniach komercyjnych na calym swiecie, dawaloby to

USA olbrzymie korzyscie w zakresie militarnym i gospodarczym.

W odniesieniu do DES-a nie zostaly opublikowane _zadne prace daj

,

ace tej

metodzie solidne podstawy matematyczne. Jednak_ze ponad 20 lat badan

akademickich potwierdzaj

,

a, _ze konstrukcja DES-a jest bardzo wyranowana.

Jakkolwiek w zakresie kryptoanalizy DES-a osi

,

agni

,

eto du_ze post

,

epy, nie za-

grozily one znacz

,

aco stosowaniu tej metody w praktyce. Z drugiej strony

uproszczone wersje DES-a mog

,

a byc zlamane znacz

,

aco mniejszym kosztem.

Interesuj

,

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

znacz

,

acych post

,

epow i DES nie doczekal si

,

e nowej, lepszej wersji.

3.1.1 Szyfrowanie DES-em

Szyfrowanie i deszyfrowanie przy pomocy DES-a sklada si

,

e z 16

rund

. W trakcie

ka_zdej rundy dokonywane s

,

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

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

przed pierwsz

,

a rund

,

a i po ostatniej rundzie bity s

,

a permutowane w ustalony sposob.

Generowanie podkluczy

W celu uzyskania podkluczy u_zywanych podczas poszczegolnych rund usuwamy

najpierw 8 bitow parzystosci zawartych w kluczu. Nast

,

epnie z pozostalych 56 bitow

tworzonych jest 16 podkluczy, ka_zdy skladaj

,

acy si

,

e z 48 bitow. Tak utworzony

i

-

ty klucz oznaczac b

,

edziemy przez

K

i

 b

,

edzie on u_zywany w trakcie

i

-tej rundy.

Ka_zdy podklucz sklada si

,

e ze z gory okreslonych bitow orginalnego klucza { dla

ka_zdego podklucza s

,

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

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

,

ac na uwadze

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

daj

,

e si

,

e zrealizowac hardware'owo. Interesuj

,

ace jest, i_z znane metody kryptoana-

lizy DES-a w najbardziej istotnym momencie nie wykorzystuj

,

a zale_znosci mi

,

edzy

wartosciami bitow podkluczy.

Permutacja pocz

,

atkowa i ko
ncowa

Na pocz

,

atku bity tekstu jawnego s

,

a permutowane. Nie ma to _zadnego celu kry-

ptogracznego. Zauwa_zmy jednak, _ze permutacja ta mo_ze byc z latwosci

,

a zaim-

plementowana hardware'owo. Po prostu poszczegolne bity doprowadzone s

,

a za

pomoc

,

a drutow (dokladniej pol

,

aczen w ukladzie VLSI) na odpowiednie miejsca.

Czas obliczen permutacji odpowiada tu jedynie czasowi w jakim informacje dotr

,

a

po drutach na miejsca przeznaczenia. W przeciwienstwie do tego implementacja

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

wany na miejsce przeznaczenia.

Pod koniec szyfrowania uzyskane bity s

,

a permutowane permutacj

,

a odwrotn

,

a do

pocz

,

atkowej. Permutacja ta jest nazywana

permutacj

,

a ko
ncow

,

a

.

Runda DES-a

Dane wejsciowe rundy

i

+1 skladaj

,

a si

,

e z dwu ci

,

agow 32-bitowych:

L

i

(pierwszych

32 bitow b

,

ed

,

acych wynikiem rundy

i

) oraz

R

i

(pozostale 32 bity uzyskane w rundzie

i

). Zachodz

,

a nast

,

epuj

,

ace zwi

,

azki:

L

i+1

=

R

i

R

i+1

=

L

i

X

OR

f

(

R

i

K

i+1

)

(3.1)

R

OZDZIA

L

3.

ALGOR

YTMY

SYMETR

YCZNE

20

gdzie

f

jest funkcj

,

a, ktora posiada zasadnicze znaczenie dla szyfrowania. Obliczenie

wartosci funkcji

f

jest przedstawione na rys. 3.2 i dokonuje si

,

e w nast

,

epuj

,

acy sposob:

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

numery bitow na wejsciu

numery bitow na wyjsciu

...

pol

,

aczenia realizuj

,

ace

permutacj

,

e z

rozszerzeniem

@

@

@

@

@

@

;

;

;

;

;

;

(

(

(

(

(

(

(

(

(

(

(

(

(

(

(

(

(

(

(

(

(

(

(

(

32

1 2 3 4

5 6 7 8

9 10 11

Rysunek 3.1: Permutacja z rozszerzeniem

1. Poprzez tzw.

permutacj

,

e z rozszerzeniem

otrzymuje si

,

e ci

,

ag zlo_zony z 48

bitow z 32 bitow

R

i

(32 bity

R

i

s

,

a kopiowane na 48 pozycji, niektore z nich

dwukrotnie, patrz rys. 3.1).

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

,

acymi

im bitami podklucza

K

i+1

.

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

dawana jest dzialaniu S-boksu. (S-Boks u_zywany przez

i

-t

,

a grup

,

e nazywany

jest Si.)

4. Otrzymane 32 bity s

,

a na koniec permutowane.

f

(

R

i

K

i+1

)

?







permutacja

?







S

1







S

2







S

3







S

4







S

5







S

6







S

7







S

8

H

H

H

H

j

Q

Q

Q

s

S

S

w

B

B

N

















+





/

?

?

?

?

?

?

?

?







XOR

?

K

i+1

H

H

H

H

H

H

j





















permut. z rozszerz.

?

R

i

?

Rysunek 3.2: Funkcja

f

DES-a

R

OZDZIA

L

3.

ALGOR

YTMY

SYMETR

YCZNE

21

3.1.2 Deszyfrowanie DES-em

Nale_zaloby oczekiwac, _ze aby deszyfrowac kryptogram nale_zy cale obliczenie skla-

daj

,

ace si

,

e na szyfrowanie odtworzyc od konca do pocz

,

atku. Ale dla S-boksow nie

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

mo_zliwych argumentow. Pomaga tu jednak nast

,

epuj

,

acy wybieg: z rownosci (3.1)

wynika, i_z:

R

i;1

=

L

i

L

i;1

=

R

i

X

OR

f

(

R

i;1

K

i

) =

R

i

X

OR

f

(

L

i

K

i

)

Jesli wi

,

ec znamy

L

i

,

R

i

oraz podklucz

K

i

, to na podstawie powy_zszych rownosci

mo_zemy obliczyc

L

i;1

i

R

i;1

. Tak wi

,

ec nie musimywcale obliczacfunkcji odwrotnej

do funkcji obliczanych przez S-boksy.

Latwo widac, _ze podczas deszyfrowania dokonywane s

,

a te same operacje co

podczas szyfrowania (tylko podklucze wyst

,

epuj

,

a w odwrotnej kolejnosci). Z tego

wzgl

,

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

Zauwa_zylismy, _ze wzory (3.1) stwarzaj

,

a dogodne mo_zliwoscideszyfrowania. Inte-

resuj

,

ace jest, _ze szyfrowanie wedlug schematu danego tymi wzorami zdaje si

,

e miec

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

,

a-

cych na korzysc DES-a.

3.2

T

rzykrotn

y

DES

Wielkosc klucza u_zywanego przez algorytm DES wydaje si

,

e byc niewystarczaj

,

aca.

Z tego wzgl

,

edu podj

,

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

wykorzystywac dlu_zsze klucze. Wiele tych prob skonczylo si

,

e niepowodzeniem.

Okazywalo si

,

e bowiem, i_z koszty zwi

,

azane ze zlamaniem kryptogramow utworzo-

nych przy pomocy tych metod s

,

a porownywalne z kosztami zlamania kryptogramow

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

mania szyfrow). Bardziej skomplikowana budowa algorytmu i dlu_zsze klucze nie

oferowaly wi

,

ec wi

,

ekszego bezpieczenstwa.

Metod

,

a niekiedy stosowan

,

a w praktyce jest

trzykrotny DES

. U_zywamy w nim

dwoch kluczy

S

1

,

S

2

, ka_zdy b

,

ed

,

acy zwyklym kluczem DES-a. Szyfrowanie tekstu

jawnego ma nast

,

epuj

,

acy przebieg:

1. tekst jawny szyfrowany jest kluczem

S

1

,

2. wynik kroku 1 jest deszyfrowany kluczem

S

2

,

3. wynik kroku 2 jest powtornie szyfrowany kluczem

S

1

.

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

nac nast

,

epuj

,

ace kroki:

1. kryptogram deszyfrowany jest kluczem

S

1

,

2. wynik kroku 1 jest szyfrowany kluczem

S

2

,

3. wynik kroku 2 jest powtornie deszyfrowany kluczem

S

1

.

3.3

Szyfro

w

anie

tekst

ow

do

w

olnej

d

lugo



sci

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

u_zytecznym trzeba znalezc sposob na szyfrowanie tekstow dowolnej dlugosci. Po-

ni_zej przedstawiamy trzy takie ogolne metody rozszerzaj

,

ace szyfrowanie tekstow

ustalonej dlugosci, powiedzmy

k

, na teksty dowolnej dlugosci.

R

OZDZIA

L

3.

ALGOR

YTMY

SYMETR

YCZNE

22

3.3.1 Elektroniczna ksi

,

a_zka kodowa

Elektroniczna ksi

,

a_zka kodowa

(inaczej

ECB

, czyli

Electronic Codebook

) funkcjo-

nuje jak nast

,

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

k

.

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

kryptogram

tekst jawny

blok 1

blok 2

blok 3

DES

DES

DES

-

-

-

K

K

K

?

?

?

?

?

?











 

Rysunek 3.3: Schemat trybu ECB

Tryb ECB ma t

,

a zalet

,

e, _ze uszkodzenie lub utrata pojedynczych blokow nie

ma wplywu na mo_zliwosc deszyfrowania pozostalych cz

,

esci kryptogramu. Z drugiej

strony mo_zliwy jest atak nie wymagaj

,

acy zlamania szyfru. Przesledzimy to na

nast

,

epuj

,

acym przykladzie:

Przyklad ataku na ECB:

Zalo_zmy, _ze komunikacja pomi

,

edzy dwoma bankami

odbywa si

,

e w trybie ECB. W ten sposob szyfrowane s

,

a przelewy mi

,

edzy kontami

obu bankow. Zalo_zmy, _ze specykacja kont, na jakie nale_zy dokonac przelewow ma

nast

,

epuj

,

ac

,

a postac:

przelew =

kon-

to

odbior- ca

wartosc przelewu

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

Przest

,

epca Mallet, ktory jest w stanie modykowac tresc kryptogramow naply-

waj

,

acych do banku, mo_ze przeprowadzic nast

,

epuj

,

acy atak:

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

,

e sam

,

a kwot

,

e pieni

,

edzy.

Nast

,

epnie identykuje w przesylanych kryptogramach taki kryptogram konta,

na ktory dokonano dokladnie 17 przelewow i w dodatku na t

,

e sam

,

a kwot

,

e.

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

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

szyfrowania.

2. Mallet zamienia w pewnej ilosci przeplywaj

,

acych kryptogramow kod numeru

konta, wstawiaj

,

ac na to miejsce kryptogram numeru swego konta. Dzi

,

eki temu

bank dopisuje do konta Malleta kwoty przeznaczone pierwotnie dla innych

osob.

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

z ktorym nie podpisano umowy o ekstradycji. Nast

,

epnie udaje si

,

e sladem

pieni

,

edzy zanim ktos si

,

e zorientuje.

Aby unikn

,

ac sytuacji opisanej powy_zej trzeba u_zyc bezpieczniejszego trybu szy-

frowania. Dwa takie tryby opisujemy poni_zej.

Jako ciekawostk

,

e dodajmy, _ze mimo wskazanych powy_zej zagro_zen instytucje

nansowe cz

,

esto lekkomyslnie u_zywaj

,

a trybu ECB do transmisji wa_znych danych.

R

OZDZIA

L

3.

ALGOR

YTMY

SYMETR

YCZNE

23

3.3.2 Cipher Block Chaining

Cipher Block Chaining

(CBC) jest metod

,

a, dzi

,

eki ktorej ten sam blok tekstu

jawnego jest szyfrowany w ro_znych miejscach w ro_zny sposob. Osi

,

agane jest to

w nast

,

epuj

,

acy sposob. Rozwa_zmy algorytm szyfruj

,

acy bloki dlugosci

k

. Niech

E

K

(

X

) oznacza kryptogram uzyskany z tekstu jawnego

X

przy pomocy klucza

K

. Jesli tekst jawny sklada si

,

e z blokow

P

1

P

2

P

3

:

:

:

dlugosci

k

, to kryptogram

uzyskany przy pomocy klucza

K

sklada si

,

e blokow

C

1

C

2

C

3

:

:

:

(rownie_z dlugosci

k

) zdeniowanych nast

,

epuj

,

aco:

C

1

=

E

K

(

P

1

X

OR

I

)

C

i

=

E

K

(

P

i

X

OR

C

i;1

)

:

Ci

,

ag

I

wyst

,

epuj

,

acy w powy_zszym wzorze jest generowany losowo i przesylany w

sposob niezaszyfrowany. Zauwa_zmy, _ze kryptogramy poszczegolnych blokow s

,

a ze

sob

,

a powi

,

azane: dla otrzymania

C

i

wykorzystujemy

C

i;1

, a nie tylko

P

i

. Poniewa_z

C

i

zale_zy od

C

i;1

, a

C

i+1

od

C

i

, wi

,

ec posrednio

C

i+1

zale_zy od

C

i;1

. Zale_znosci

tego typu przenosz

,

a si

,

e dalej i ostatecznie ka_zdy blok

C

j

jest zale_zny od wszystkich

blokow

C

1

:

:

:

C

j

;1

, a co za tym idzie rownie_z od

I

P

1

P

2

:

:

:

P

j

;1

.

Deszyfrowywanie tak uzyskanych kryptogramow jest stosunkowo proste (poni_zej

D

oznacza funkcj

,

e deszyfruj

,

ac

,

a dla blokow dlugosci

k

):

P

1

=

D

K

(

C

1

)

X

OR

I

P

i

=

D

K

(

C

i

)

X

OR

C

i;1

:

(3.2)

Odnotujmy kilka wlasnosci szyfrowania w trybie CBC:

Zaleta: takie same bloki z reguly s

,

a reprezentowane z reguly poprzez bloki

ro_znej postaci w kryptogramie. Co wi

,

ecej, ten sam tekst jawny jest szyfrowany

w inny sposob, o ile wybierzemy inny ci

,

ag pocz

,

atkowy

I

.

Wada: nie mo_zna _zadnego bloku

C

i

usun

,

ac z kryptogramu. Stwarza to

klopoty, o ile pragn

,

elibysmy przy pomocy CBC szyfrowac zawartosc baz da-

nych. Podobne problemy napotykamyprzy probie wprowadzenia dodatkowego

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

utworzony na nowo.

Wada: podzial na bloki musi byc odporny na zaklocenia (dodatkowy bit lub

utrata pojedynczego bitu prowadz

,

a do desynchronizacji szyfrowania i deszy-

frowania).

Zaleta: przeklamania wewn

,

atrz jednego bloku (bez zmiany ilosci bitow) pro-

wadz

,

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

st

,

apilo przeklamanie i bloku nast

,

epuj

,

acym po nim. Wlasnosc ta wynika

bezposrednio z wzoru (3.2).

3.3.3 Cypher Feedback

CFB

, czyli

cypher feedback

, jest drugim bezpiecznym trybem szyfrowania dlugich

tekstow. W odro_znieniu do CBC szyfrowane s

,

a nie cale bloki, ale fragmenty zlo_zone

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

zabezpieczenia komunikacji pomi

,

edzy klawiatur

,

a i serwerem. Oczywiste jest, _ze

w tej sytuacji niezb

,

edne jest natychmiastowe przesylanie pojedynczych znakow

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

korzystania z trybu CBC. Mo_zliwe jest rownie_z przesylanie t

,

a metod

,

a na przyklad

pojedynczych bitow.

R

OZDZIA

L

3.

ALGOR

YTMY

SYMETR

YCZNE

24

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

DES jako metod

,

e szyfrowania pojedynczych blokow. Jednym z zasadniczych sklad-

nikow CFB jest rejestr przesuwaj

,

acy. Na pocz

,

atku zawiera on losowo wygenerowany

ci

,

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

pracy CFB przy u_zyciu klucza

K

wykonywane s

,

a nast

,

epuj

,

ace operacje:

1. Zawartosc rejestru przesuwaj

,

acego jest szyfrowana przy pomocy klucza

K

.

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

slu_z

,

a do operacji

X

OR

z 8 bitami koduj

,

acymi nast

,

epn

,

a liter

,

e

P

podawan

,

a

na wejsciu. W wyniku otrzymujemy ci

,

ag osmiu bitow

Z

.

3. Ci

,

ag

Z

tworzy kolejnych 8 bitow wyniku. Ponadto w rejestrze przesuwaj

,

acym

wykonujemy przesuni

,

ecie o 8 pozycji. Jest to przesuni

,

ecie niecykliczne { 8

bitow z lewej strony ulega usuni

,

eciu. Z kolei na osmiu zwolnionych pozycjach

zapisywany jest ci

,

ag

Z

.

P

?

nast

,

epna litera

-





X

OR

-

?

wyjscie

?

8 bitow

Z

?

kryptogram

rejestr przesuwaj

,

acy

?

?

-

DES



klucz

K



Rysunek 3.4: Schemat trybu CFB

3.4

IDEA

Wiele prob podejmowanych bylo nad zaprojektowaniem algorytmu, ktory zast

,

apilby

DES. Jedn

,

a z przyczyn bylo przekonanie, _ze wielkosc kluczy DES-a jest za mala.

Inn

,

a wa_zn

,

a przyczyn

,

a byly regulacje prawne w USA uznaj

,

ace DES za produkt o

znaczeniu militarnym i u_zywanie go poza granicami USA bez stosownych licencji

za czyn przest

,

epczy. Poniewa_z utrudnia to stosowanie kryptograi w kontaktach z

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

stosowanie nie prowadziloby do koniktow z amerykanskimi organami bezpieczen-

stwa. Cele te przyswiecaly powstaniu algorytmu (

I

nternational

D

ata

E

ncryption

S

tandard), wskrocie

IDEA

.

Wlasno
sci IDEA:

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

komercyjnych. Algorytm jest opatentowany w Europie.

R

OZDZIA

L

3.

ALGOR

YTMY

SYMETR

YCZNE

25

IDEA jest algorytmem nowym, wprowadzonym w latach dziewi

,

ecdziesi

,

atych.

Algorytm spotkal si

,

e z du_zym zainteresowaniem, w tym rownie_z jesli chodzi

o proby jego kryptoanalizy. Wobec stosunkowo krotkiego okresu od momentu

jego opublikowania nale_zy z ostro_znosci

,

a podchodzic do jego bezpieczenstwa.

IDEA wchodzi jako jeden z komponentow w sklad PGP, popularnego pakietu

kryptogracznego (patrz rozdz. 13.0.16).

Klucze u_zywane przez IDEA s

,

a zlo_zone z 128 bitow. W praktyce oznacza

to, _ze poszukiwanie pasuj

,

acego klucza do pary kryptogram{tekst jawny po-

przez wyprobowywanie wszystkich kluczy po kolei jest niewykonalne. Mimo

wielkosci kluczy programy szyfruj

,

ace i deszyfruj

,

ace wedlug algorytmu IDEA

nie s

,

a wolniejsze ni_z programy realizuj

,

ace DES.

3.4.1 Szyfrowanie poprzez algorytm IDEA

Szyfrowanie sklada si

,

e z 8 rund. Pojedyncz

,

a rund

,

e schematycznie przedstawia

rys. 3.5. Oprocz tego po ostatniej rundzie dokonywane jest przeksztalcenie

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

,

e jasne, gdy omawiacb

,

edzie-

my deszyfrowanie.

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

operacje s

,

a u_zywane:

{

X

OR

dokonywany na poszczegolnych bitach,

{

dodawanie modulo 2

16

(oznaczane dalej symbolem +),

{

mno_zenie modulo (2

16

+ 1) (oznaczane dalej symbolem



).

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

trakcie rundy

i

u_zywanych jest szesc podkluczy

Z

(i)

1

:

:

:

Z

(i)

6

.

W odro_znieniu do kluczy, tekst jawny zawiera 64 bitow.

Przebieg rundy algorytmu IDEA zostal przedstawiony na rys. 3.5. Dane wejsciowe

dla rundy

i

skladaj

,

a si

,

e z 4 blokow po 16 bitow oznaczonych

X

1

:

:

:

X

4

. Rezultat

sklada si

,

e z blokow 16-bitowych oznaczonych

Y

1

:

:

:

Y

4

.

3.4.2 Generowanie podkluczy dla algorytmu IDEA

Szyfrowanie przy pomocy algorytmu IDEA wymaga 6



8+4 podkluczy (8 jest ilosci

,

a

rund, ka_zda z rund wykorzystuje 6 podkluczy, dodatkowo przeksztalcenie koncowe

u_zywa 4 kluczy). Podklucze s

,

a generowane w nast

,

epuj

,

acy sposob:

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

podkluczy dla pierwszej rundy, 2 dla drugiej rundy).

2. Na kluczu wykonuje si

,

e przesuni

,

ecie cykliczne o 25 pozycji. Wynik jest na

nowo dzielony na bloki dlugosci 16. Daje to nast

,

epnych 8 podkluczy (4

brakuj

,

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

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

klucze.

3.4.3 Deszyfrowanie przez IDEA

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

posrednio wyliczyc dane wejsciowe dla rundy na podstawie danych wyjsciowych dla

rundy byloby trudno (porownaj rys. 3.5).

R

OZDZIA

L

3.

ALGOR

YTMY

SYMETR

YCZNE

26

X

1

: 16 bitow

X

2

: 16 bitow

X

3

: 16 bitow

X

4

: 16 bitow

?

?

?

?

j



j

+

j

+

j



Z

(i)

4

-

Z

(i)

3

-

Z

(i)

2

-

Z

(i)

1

-

?

?

j

X

j

X

?

?

-

(

(

(

(

(

(

(

(

(

h

h

h

h

h

h

h

h

h



r

r

r

r

h

h

?

(

(

?

j



-

j

+

Z

(i)

5

-

j

+



j



Z

(i)

6



?

?

j

X

?

-



r

j

X

j

X

?



-

r

j

X

?

h

h

h

h

h

h

h

h

h

?

(

(

(

(

(

(

(

(

(

?

?

Y

1

: 16 bitow

Y

2

: 16 bitow

Y

3

: 16 bitow

Y

4

: 16 bitow

...

...

...

...

j



mno_zenie

j

+ dodawanie

j

X

X

OR

Z

1

(

i

)

Z

2

(

i

)

:::

- podklucze rundy

i

Rysunek 3.5: Runda

i

algorytmu IDEA

Idea deszyfrowania dla jednej rundy:

Wprowadzmy nast

,

epuj

,

ace oznaczenia

(patrz rys. 3.6):

A

=

X

1



Z

(i)

1

B

=

X

2

+

Z

(i)

2

C

=

X

3

+

Z

(i)

3

D

=

X

4



Z

(i)

4

:

Niech

E

=

B

X

OR

Y

3

F

=

C

X

OR

Y

2

(porownaj rys. 3.6). Latwo zauwa_zyc korzystaj

,

ac z rys. 3.6, _ze

Y

3

X

OR

Y

4

= (

B

X

OR

E

)

X

OR

(

E

X

OR

D

) =

B

X

OR

D :

Zatem mo_zemy obliczyc wartosc

B

X

OR

D

. Podobnie mo_zna obliczyc

A

X

OR

C

.

Zauwa_zmy, _ze

B

X

OR

D

i

A

X

OR

C

s

,

a wynikami otrzymywanymi przez dwa w

,

ezly

obliczaj

,

ace

X

OR

w srodkowej cz

,

esci ukladu przedstawionego na rys. 3.6. Tak wi

,

ec

znaj

,

ac klucze

Z

(i)

5

i

Z

(i)

6

mo_zna obliczyc

E

i

F

. Przy ich pomocy otrzymujemy:

A

=

Y

1

X

OR

F 

B

=

Y

3

X

OR

E

C

=

Y

2

X

OR

F 

D

=

Y

4

X

OR

E

:

Znaj

,

ac

A

B

C 

D

i podklucze

Z

(i)

1

:

:

:

Z

(i)

4

mo_zna na koniec wyliczyc

X

1

:

:

:

X

4

.

W opisany powy_zej sposob znaj

,

ac podklucze wyprowadzilismy dane wejsciowe

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

kich rund, poczynaj

,

ac od ostatniej.

R

OZDZIA

L

3.

ALGOR

YTMY

SYMETR

YCZNE

27

X

1

X

2

X

3

X

4

?

?

?

?

j



j

+

j

+

j



Z

(i)

4

-

Z

(i)

3

-

Z

(i)

2

-

Z

(i)

1

-

?

?

j

X

j

X

?

?

-

(

(

(

(

(

(

(

(

(

h

h

h

h

h

h

h

h

h



r

r

r

r

h

h

?

(

(

?

j



l

k

-

j

+

l

k

Z

(i)

5

-

j

+



j



Z

(i)

6



?

?

j

X

?

-



r

j

X

j

X

?



-

r

j

X

?

h

h

h

h

h

h

h

h

h

?

(

(

(

(

(

(

(

(

(

?

?

Y

1

Y

2

Y

3

Y

4

...

...

...

...

B

E

F

C

D

A

A

X

OR

C

B

X

OR

D

Rysunek 3.6: Metoda deszyfrowania dla algorytmu IDEA

Realizacja deszyfrowania:

Powy_zej zauwa_zylismy jak deszyfrowac w przypadku

algorytmu IDEA. Jesli wykonywane operacje przedstawimy schematycznie (patrz

rys. 3.7), to zauwa_zamy uderzaj

,

ace podobienstwo do operacji wykonywanych pod-

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

wykonywane przy u_zyciu 4 podkluczy s

,

a wykonywane nie na pocz

,

atku, ale na koncu

rundy deszyfrowania. Dzi

,

eki temu ten sam uklad elektroniczny mo_ze byc u_zyty w

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

najpierw przeprowadzamy operacj

,

e pocz

,

atkow

,

a, odpowiadaj

,

ac

,

a operacji koncowej

szyfrowania, a nast

,

epnie wykonujemy 8 rund, ka_zda z nich zaczynaj

,

aca si

,

e od

operacji

X

OR

.

Podklucze u_zywane podczas deszyfrowania odpowiadaj

,

a podkluczom szyfrowa-

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

nia musimy cz

,

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

u_zywane do dodawania).

R

OZDZIA

L

3.

ALGOR

YTMY

SYMETR

YCZNE

28

Y

1

Y

3

Y

2

Y

4

?

?

?

?

?

?

?

?

j



j

+

j

+

j



Z

(i)

4

;1

-

;Z

(i)

3

-

;Z

(i)

2

-

Z

(i)

1

;1

-

?

?

j

X

j

X

?

?

-

(

(

(

(

(

(

(

(

(

h

h

h

h

h

h

h

h

h



r

r

r

r

h

h

?

(

(

?

j



-

j

+

Z

(i)

5

;1

-

j

+



j



;Z

(i)

6



?

?

j

X

?

-



r

j

X

j

X

?



-

r

j

X

?

h

h

h

h

h

h

h

h

h

?

(

(

(

(

(

(

(

(

(

?

?

X

1

X

3

X

2

X

4

Rysunek 3.7: Schemat deszyfrowania w algorytmie IDEA

16 bitow

16 bitow

16 bitow

16 bitow

16 bitow

16 bitow

?

?

?

?

j

.

j

+

j

j

+

.

Z

(9)

4

-

Z

(9)

3

-

Z

(9)

2

-

Z

(9)

1

-

Z

Z

~





=













9

X

X

X

X

X

X

z

kryptogram

Rysunek 3.8: Przeksztalcenie koncowe w algorytmie IDEA