Notatki z kryptografii  szyfry
Stanisław Klekot
11 kwietnia 2004
1 Konwencje
Konwencje przyjęte dalej w tekście:
funkcję boole owską XOR będę oznaczać symbolem �"
wiadomość niezaszyfrowaną będę nazywać jawnym tekstem, otwartym tekstem, plain text albo
po prostu wiadomością i oznaczać symbolem M
przy szyfrach blokowych długość słowa wejściowego będę oznaczać symbolem w, a ilość rund
algorytmu symbolem r
wiadomość po zaszyfrowaniu będę nazywać kryptogramem i oznaczać symbolem C
klucz użyty do szyfrowania będę oznaczać symbolem K, a jego długość symbolem b
proces szyfrowania wiadomości M przy użyciu klucza K będę oznaczać C = EK(M), proces
odszyfrowywania zaś M = DK(C)
2 Proste algorytmy dla danych dowolnej długości
2.1 One-time pad
Szyfry one-time pad są chyba najprostszą i najszybszą metodą szyfrowania, jeśli ma się klucz.
Najczęściej stosowanym schematem jest C = M �" K (XOR bit po bicie), choć można używać
innych: C = M + K mod n, C = M � K mod n albo jakiejkolwiek innej funkcji 1-1.
W tym algorytmie klucz jest tak długi jak wiadomość, którą ma zaszyfrować. Zapewnia to
bezpieczeństwo doskonałe  dosłownie. Żadne moce przerobowe nie są w stanie złamać szyfru,
bo każda wiadomość (sensowna czy nie) jest równo prawdopodobna, tzn. istnieje dla niej klucz
szyfrujący ją do rozpatrywanego kryptogramu. Bez znajomości klucza nie daje się odszyfrować
wiadomości, jedyną informacją oryginalnego tekstu, która się przedostaje, jest jego długość, a i to
nie jest pewne, bo wiadomość można skompresować albo uzupełnić losowymi danymi.
Wady algorytmu:
1. klucz jest niesamowicie długi
1
2. klucz jest jednorazowy  do każdego szyfrowania trzeba generować nowy (inaczej bezpie-
czeństwo wiadomości jest mocno narażone)
3. łatwo zmienić tekst, jeśli znamy jego format (to jest wada wszystkich algorytmów szyfrują-
cych strumienie danych)
2.2 Szyfry strumieniowe
Szyfry one-time pad są niewygodne, jeśli trzeba przesyłać spore ilości danych, które nie muszą być
idealnie bezpieczne, przede wszystkim z powodu długości klucza użytego do szyfrowania. Można
użyć klucza krótszego i go powtarzać, ale to nie jest bezpieczne. Obecnie używa się generato-
rów ciągów pseudolosowych. Ustawia się taki generator, a wyrzucany strumień bitów XORuje się
z tekstem jawnym. Jest to dość dobra metoda przesyłania dz
więku i obrazu (ogólnie: danych  nie-
dokładnych ), ale nie nadaje się do transmisji np. fragmentów baz danych, gdyż manipulowanie
danymi ustalonego formatu jest proste (patrz: wada 3 w sekcji 2.1)
2.2.1 LFSR
Wez
my początkowy wektor (tablicę bitów) długości n: IV = V0, V1, V2, . . . , Vn i wpiszmy go do
rejestru R o tej samej długości. Wektor ten generuje ciąg (pseudo)losowych bitów b0, b1, b2, . . .:
w k-tym kroku obliczamy Rn+1 używając niektórych bitów spośród R0, R1, . . . , Rn i przesuwamy
cały rejestr o jedno miejsce (R0 �! R1, R1 �! R2, . . . , Rn-1 �! Rn, Rn �! Rn+1). Usunięty bit R0
to jest nasz (pseudo)losowy bit bk.
Ten sposób nosi nazwę linear feedback shift register. Nie jest to najlepszy sposób generowania
losowych bitów. Wystarczy poznać odpowiednio dużo bitów wyjścia (2n), żeby poznać wewnętrzną
strukturę rejestru (tzn. rozpoznać, które bity Rk są używane do generowania Rn+1).
2.2.2 A5
A5 jest algorytmem stosowanym w sieciach GSM. Opiera się na LFSR. Używa trzech rejestrów
o długościach 19, 22 i 23 bitów. Ciągiem wynikowym A5 jest XOR wyjść rejestrów. Nie wszyst-
kie rejestry się przesuwają za każdym razem. Stosowane jest  głosowanie : brany jest środkowy
bit każdego rejestru (odpowiednio 9-ty i dwa 11-te), a przesuwane są te rejestry, które oddały
 większościowy głos, tzn. jeśli wypadło 1, to przesuwają się rejestry z 1 na środkowej pozycji,
w przeciwnym wypadku przesuwają się rejestry z 0.
3 Szyfry blokowe
3.1 Wymagania dla szyfrów blokowych
Szyfry blokowe różnią się dość znacznie od szyfrów strumieniowych. Przede wszystkim operują na
całych blokach danych, nie na pojedynczych bitach. Dodatkowo wszystkie dobre szyfry blokowe
charakteryzują się tzw. efektem lawinowym (zmiana dowolnego bitu klucza lub tekstu jawnego
skutkuje zmianą około połowy losowych bitów kryptogramu). Obie te cechy znacznie utrudniają
modyfikację pojedynczego bitu w bloku  jakakolwiek zmiana rozsypie się po całym tekście po
odszyfrowaniu. Efekt lawinowy zapobiega atakowi przez lokalne przeszukiwanie, bo kryptogramy
2
powstałe przez zaszyfrowanie podobnych wiadomości tym samym kluczem (albo jednej wiadomości
dwoma podobnymi kluczami) różnią się praktycznie losowo, zatem nie można na tej podstawie
ocenić, jak blisko jesteśmy złamania klucza.
3.2 Schemat Feistela
Większość algorytmów blokowych opiera się o schemat Feistela, czasem nazywany siecią Feistela.
Pomysł jest dość prosty. Wiadomość dzielimy na dwie równe części, zwyczajowo nazywane L0 i R0.
Następnie obliczamy wartości L1 i R1:
L1 = R0
R1 = f(K, R0) �" L0
Jak widać, R0 po jednym kroku występuje w takim kryptogramie jawnie, zatem musimy wykonać
co najmniej dwie iteracje.
Odszyfrowanie odbywa się analogicznie:
Rn-1 = Ln
Ln-1 = f(K, Rn-1) �" Rn = f(K, Ln) �" Rn
Schemat ten jest całkiem wygodny, gdyż nie wymaga, aby użyta funkcja f była odwracalna. Nie
zakładamy o niej absolutnie niczego, mogłaby nawet być określona jako f(K, M) a" 0 (choć taka
funkcja nie byłaby zbyt dobrym zabezpieczeniem dla danych). Całe bezpieczeństwo algorytmu jest
oparte o dobrze dobraną funkcję f.
3.3 DES i 3-DES
Algorytm DES jest podręcznikowym zastosowaniem schematu Feistela. Działa na 64-bitowych
blokach, używając 56-bitowego (8 � 7 bitów) klucza, wykonując 16 cykli (podstawień w/g sche-
matu Feistela). Przed pierwszym cyklem tekst jawny jest permutowany (permutacja jest stała).
W samym cyklu połówka danych  32 bity  jest rozszerzana do 48 bitów (tzw. permutacja
rozszerzająca). Wynik jest XORowany z podkluczem danego cyklu, a tak wyliczona wartość jest
dzielona na sześć ośmiobitowych części, z których każda jest przepuszczana przez tzw. S-box .
S-box y to tablice rozmiaru 4 � 16, w których w każdym wierszu występują wszystkie liczby od
0 do 15. Pierwszy i ostatni bit 6-bitowego wejścia kodują numer wiersza, pozostałe kodują nu-
mer kolumny. Połączone wyjścia S-box ów są następnie permutowane (permutacja jest stała). Po
ostatnim cyklu blok szyfrogramu jest przepuszczany przez permutację odwrotną do permutacji
początkowej.
Klucz długości 56 bitów jest dzisiaj stanowczo zbyt krótki. Niestety, znalezienie S-box ów dużych
rozmiarów i równie odpornych na ataki, co oryginalne, jest trudne, zatem bezpośrednie wydłużanie
DESa jest wykluczone. Zamiast tego stosuje się szyfrowanie wielokrotne z użyciem różnych kluczy:


3-DESK ,K2,K3(M) = EK DK EK (M)
1 3 2 1
przy czym K3 często jest taki sam, jak K1  wtedy klucz ma długość 112 bitów, a gdy K2 = K1
albo K2 = K3  mamy szyfrowanie klasycznym DESem (co tłumaczy deszyfrowanie w drugim
kroku).
Dlaczego nie dwukrotne szyfrowanie? Atak known plain-text na podwójny DES nie jest zna-
cząco trudniejszy niż na DES. Szyfrujemy znaną wiadomość wszystkimi (256) kluczami dla DES,
a kryptogram deszyfrujemy wszystkimi kluczami. Wystarczy teraz znalez
ć kryptogram pośredni
3
występujący w obu tablicach. Ta metoda ataku nosi nazwę meet in the middle. Złożoność tego
ataku wynosi zaledwie 2 � 256 szyfrowań + przeszukiwanie dwóch dużych tablic. Nie tego się spo-
dziewaliśmy po dwukrotnym wydłużeniu klucza.
3.4 RC5
Ron Rivest zaproponował zgrabny algorytm szyfrowania. Ilość cykli r, długość szyfrowanego bloku
w i długość klucza b są tu sparametryzowane, co czyni szyfr bardzo elastycznym. Na początku
klucz jest dzielony na podklucze K0, K1, . . . , K2r, K2r+1, a wiadomość na dwie połówki L0 + S0
i R0 + S1, do których są dodane pierwsze dwa podklucze. Pojedyncza runda jest bardzo prosta:

Li = (Li-1 �" Ri-1) j" Ri-1 + K2i

Ri = (Ri-1 �" Li) j" Li + K2i+1
Można to zapisać przy użyciu dwóch rejestrów:

L = (L �" R) j" R + K2i

R = (R �" L) j" L + K2i+1
Symbol j" oznacza operację przesunięcia cyklicznego w lewo. Wszystkie operacje odbywają się
modulo 2w.
3.5 Szyfrowanie długich tekstów
Algorytmy blokowe nie potrafią same z siebie szyfrować tekstów jawnych o innej długości niż
przewidziana dla algorytmu, jednak umiejętnie dzieląc można szyfrować dane także innej długości.
Poniższe sposoby zakładają, że wiadomość składa się z pełnych bloków wejściowych dla szyfru. Tą
własność można uzyskać na przykład uzupełniając wiadomość zerami (padding).
3.5.1 Electronic CodeBook
Najprostszym sposobem jest podzielić wiadomość M na bloki M0, M1, M2, . . . , Mn po w bitów,
po czym zaszyfrować każdy blok niezależnie:
Ci = EK(Mi)
Szyfrując tym sposobem jeden duży plik dostarczamy atakującemu dużo (dokładnie n) krypto-
gramów, co na pewno nie utrudnia złamania klucza. Poza tym, jeśli szyfrujemy tak transmisję,
atakującemu jest łatwo ją zmodyfikować wstawiając fragment wcześniejszy  nie zorientujemy
się, że coś jest nie tak, o ile nie zastosowaliśmy innych metod kontroli spójności danych. Z drugiej
strony, jeśli podczas szyfrowania albo transmisji kryptogramu nastąpi błąd na jednym bicie, stra-
cony jest tylko jeden blok wiadomości, zmiana nie wpływa na pozostałe bloki (choć przez jeden
bit tracimy cały blok tekstu).
3.5.2 Cipher Block Chaining
Możemy uzależnić fragment kryptogramu Ci od wyniku szyfrowania poprzedniej rundy Ci-1.
Sposób jest dość łatwy:
C-1 = IV
Ci = EK(Ci-1 �" Mi)
4
IV jest losowym wektorem początkowym (initial vector). Nie ma większego sensu go szyfrować.
EK(IV ) jest tak losowy, jak sam IV , poza tym C0 trzebaby traktować w szczególny sposób.

Ponadto, jeśli uznać pierwszy blok wiadomości M0 za nieistotny, to IV = EK(M0) dla ciągu
M1, M2, . . . , Mn jest podany jawnym tekstem.
CBC ma kilka ciekawych własności.
1. Wiadomość dwukrotnie szyfrowana tym samym kluczem da różne kryptogramy, atakujący
nie może zatem stwierdzić, czy wysyłana jest dokładnie ta sama wiadomość, co ostatnio.
2. Jeśli podczas szyfrowania uszkodzeniu uległ jeden blok kryptogramu, stracony jest tylko ten
jeden blok: do szyfrowania następnego został użyty ten uszkodzony blok, więc jeśli zostanie
użyty do deszyfrowania, błąd  zniknie .
3. Jeśli i-ty blok kryptogramu uległ uszkodzeniu podczas transmisji, stracony jest w tekście
jawnym blok Mi i uszkodzone bity z bloku Mi+1.
4. Utrata synchronizacji (zgubienie lub znalezienie nadmiarowego bitu) w bloku i powoduje
utratę wszystkich bloków począwszy od i.
3.5.3 Cipher FeedBack
Szyfry blokowe można zamienić na szyfry strumieniowe  sprzęrzone z szyfrowanymi danymi.
Ci = Pi �" EK(Ci-1)
Dzięki tej technice można przesyłać nawet niepełne bloki danych, np. po jednym znaku ASCII
(8-bitowy CFB). Wystarczy utworzyć rejestr R o wielkości w (długość bloku wejściowego algo-
rytmu szyfrującego) i wypełnić go losowym IV . Po przesłaniu porcji danych (naszego ośmiobi-
towego znaku) ustawiamy wysłany kryptogram na początku rejestru przesuwając resztę. Porcję
danych natomiast należy zXORować z tym, co wyjdzie po zaszyfrowaniu rejestru: c = m �" EK(R)
(m  porcja danych do wysłania).
3.5.4 Output FeedBack
Można jeszcze szyfr blokowy zamienić na generator bitów pseudolosowych. Niech losowy R-1 = IV
ma wielkość w. Wtedy
Ri = EK(Ri-1)
Taki generator daje maksymalnie 2(b+w) cykli, co już dla DESa daje 2120 możliwych ciągów
(pseudo)losowych1.
Wynik działania takiego generatora, jak nietrudno się domyślić, jest aplikowany do tekstu jawnego
bit po bicie.
1
tak naprawdę będzie ich mniej, bo DES ma pary kluczy, które można stosować wymiennie, jednak nie zdarzają
się one zbyt często
5
4 Szyfry asymetryczne
4.1 RSA
Generowanie kluczy:
Wybieramy dwie duże (ok. 512 bitów, choć dziś zaleca się cztery do ośmiu razy dłuższe) liczby
pierwsze p i q i obliczamy ich iloczyn n = pq (n jest długości 1024 bity). Liczby p i q muszą być
osobne dla każdego użytkownika algorytmu. Wybieramy losowo e taki, żeby e i (p - 1)(q - 1)
były względnie pierwsze i obliczamy d = e-1 mod (p - 1)(q - 1) (rozszerzony algorytm Euklidesa,
twierdzenie Eulera Fermata). Teraz starannie niszczymy liczby p i q. Kluczem publicznym jest
para (n, e), kluczem prywatnym jest liczba d.
Szyfrowanie wiadomości M:
C = Me mod n
Deszyfrowanie kryptogramu C:
-1 -1 -1
Cd = Ce = (Me)e = Me�e = M (mod n)
Bezpieczeństwo alorytmu opiera się na tzw. problemie faktoryzacji, czyli rozkładu liczby na
czynniki pierwsze. Klucz d jesteśmy w stanie obliczyć, o ile mamy liczbę (p - 1)(q - 1). Ta jest
jednak obliczalna tylko przy pomocy p i q, które zostały zniszczone, a nie da się ich wydobyć
z liczby n, bo nie znamy (do tej pory) żadnego efektywnego algorytmu faktoryzującego liczby.
4.2 Algorytm ElGamala
Generowanie kluczy:
Wybieramy dużą liczbę pierwszą p i liczbę losową g < p2. Liczby p i g mogą być wspólne dla wielu
użytkowników. Losujemy liczbę x < p i obliczamy y = gx mod p. Kluczem publicznym jest trójka
(p, g, y), liczba x jest kluczem prywatnym.
Szyfrowanie wiadomości M:
Wybieramy losowe k, które jest względnie pierwsze z p - 1. Obliczamy r = gk mod p i s =
ykM mod p. Szyfrogramem jest para (r, s).
Deszyfrowanie kryptogramu (r, s):
s ykM (gx)kM
= = = M
rx (gk)x (gx)k
Bezpieczeństwo algorytmu opiera się na trudności obliczania logarytmu dyskretnego. Znając
liczby g, p i y nie możemy policzyć wykładnika potęgi, do której została podniesiona liczba g, żeby
uzyskać y.
2
najrozsądniej jest wybrać generator grupy Z
p
6
5 Podpisy cyfrowe
5.1 Wymagania stawiane podpisowi elektronicznemu
Z punktu widzenia podpisującego, podpis (elektroniczny czy odręczny) musi zaświadczać, że pod-
pisujący podpisał właśnie przedstawiony dokument. Z punktu widzenia przedstawiającego doku-
ment, podpis musi jednoznacznie identyfikować podpisującego. O ile drugi warunek jest trudny do
spełnienia przede wszystkim od strony organizacyjnej (przypisanie kluczy użytkownikom), o tyle
pierwszy warunek jest względnie łatwy, o ile użyje się szyfrów z kluczem publicznym.
5.2 Podpisy RSA
Pomysł podpisów RSA opiera się na fakcie, że żadna z liczb d, e nie jest specjalnie wyróżniona.
Obie mogą równie dobrze służyć do szyfrowania i deszyfrowania. Z uwagi na przeciętną długość
dokumentu, szyfruje się nie same dokumenty, a ich hashe (najczęściej SHA-1). Podpis S pod
dokumentem M zatem wygląda następująco:
S = (SHA-1(M))d mod n
Sprawdzenie jest równie proste:
SHA-1(M ) = Se
Jeśli SHA-1(M ) = SHA-1(M), to podpis jest poprawny.
W tym algorytmie czai się pewne niebezpieczeństwo. Bob chce, żeby Alicja podpisała zrzeczenie
się praw majątkowych na jego korzyść. Układa stosowny dokument M i oblicza z = SHA-1(M).
Wybiera sobie losowe x i daje Alicji do zaszyfrowania jej kluczem prywatnym wartość z � xe. Alicja
w dobrej wierze szyfruje ten losowy ciąg i oddaje Bobowi (z � xe)d = zd � xed = zd � x. Bob może
teraz podzielić to, co dostał od Alicji, przez x i ma podpis Alicji pod M. Wniosek: nie wolno
szyfrować prywatnym kluczem żadnych losowych ciągów nieznanego pochodzenia.
5.3 Podpisy ElGamala
W RSA wykorzystywaliśmy symetrię traktowania obu kluczy. W algorytmie ElGamala klucze
nie mogą być stosowane zamiennie. Mimo to ta sama para kluczy może służyć do podpisywania
wiadomości.
Wybieramy losowo liczbę k względnie pierwszą z p - 1 i obliczamy r = gk mod p. Następnie
obliczamy h = SHA-1(M) oraz s = k-1 (h - xr) mod p - 13. Podpisem jest para (r, s).
Weryfikacja podpisu (r, s):
-1 -1
yrrs = (gx)r(gk)k (h-xr) = gxrgkk (h-xr) = gxr+h-xr = gh (mod p)
Jeśli gh obliczone z podpisu jest równe gSHA-1(M) mod p, to podpis jest poprawny4.
5.4 Standard DSS/DSA
DSS/DSA jest bardzo podobny do podpisów ElGamala. Jego bezpieczeństwo również opiera się
na problemie logarytmu dyskretnego.
3
mamy gwarancję, że istnieje k-1 mod p - 1, bo k jest względnie pierwsze z p - 1
4
Nie do końca. Żeby był poprawny, liczby r i s muszą być mniejsze od p - 1.
7
Czynności przygotowawcze (m.in. generowanie klucza):
Wybieramy liczbę pierwszą p o długości będącej wielokrotnością 64 bitów i zawierającą się między
512 a 1024 bitów. Liczba p - 1 musi dzielić się przez pewną liczbę pierwszą q o długości 160 bitów
p-1
q
(q musimy wyznaczyć). Wybieramy liczbę g = t mod p, gdzie t < p-1 jest dowolną liczbą taką,
żeby g wyszło różne od 1. Wszystkie w/w liczby (p, q i g) mogą być wspólne dla pewnego grona
użytkowników. Losujemy liczbę x < q i obliczamy y = gx. Kluczem prywatnym jest x, kluczem
publicznym jest czwórka (p, q, g, y).
Podpis wiadomości M: Generujemy losowe k < q i obliczamy r = gk mod q oraz s = k-1(SHA-1(M)+
xr) mod q. Podpisem jest para (r, s).
Weryfikacja podpisu (r, s):
u1 = SHA-1(M) � s-1 (mod q)
u2 = r � s-1 (mod q)
1 2
v = ((gu yu ) mod p) mod q
Jeśli v = r, to podpis jest poprawny.
8