Kryptografia wyklad dla IV roku
Kryptografia
Wyklad z podstaw klasycznej
kryptografii z elementami
kryptografii kwantowej
dla studentów IV roku
Serdecznie
witam!
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 0
Kryptografia wyklad dla IV roku
Literatura
" M. Kutylowski i W. B. Strothmann Kryptografia: Teoria
i praktyka zabezpieczania systemów komputerowych, Wyd.
READ ME, Warszawa, 1999, drugie wydanie dostepne w
ksiegarniach
" B. Schneier Kryptografia dla praktyków, WNT, Warszawa,
2002, wydanie drugie
" R. Wobst, Kryptologia. Budowa i lamanie zabezpieczeń,
RM, Warszawa, 2002
" A. J. Menezes, P. C. van Oorschot, S. A. Vanstone
Handbook of Applied Cryptography, CRC Press, 1997, New
York, dostepna 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ś, http://zon8.physd.amu.edu.pl/tanas 1
Kryptografia wyklad dla IV roku
Terminologia
" Kryptografia dziedzina wiedzy zajmujaca sie zabez-
pieczaniem informacji (szyfrowanie)
" Kryptoanaliza lamanie szyfrów
" Kryptologia dzial matematyki, który zajmuje sie
podstawami metod kryptograficznych (kryptografia +
kryptoanaliza)
" Glówne postacie
Alicja nadawca informacji
Bolek odbiorca informacji
Ewa podsluchujaca kanal przesylowy i usi-
lujaca przechwycić informacje przeznaczona dla
Bolka
Ewa
Ń!
Alicja =! Bolek
Szyfrowanie i deszyfrowanie
szyfrowanie
deszyfrowanie
tekst jawny kryptogram tekst jawny
=!
=!
M C M
EK(M) = C
DK(C) = M
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 2
Kryptografia wyklad dla IV roku
Algorytmy
" symetryczne klucz do szyfrowania i deszyfrowania
jest ten sam (klucz tajny) DES, IDEA
" asymetryczne klucze do szyfrowania i deszyfrowa-
nia sa różne (klucz jawny albo publiczny RSA,
ElGamal)
Przyklad kryptogramu
" tekst jawny
Wyklad 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ś, http://zon8.physd.amu.edu.pl/tanas 3
Kryptografia wyklad dla IV roku
Podstawowe zastosowania
" ochrona danych
dane na dyskach
przesylanie danych poprzez linie narażone na podsluch
" uwierzytelnianie dokumentów i osób
" ochrona prywatności korespondencji elektronicznej
" elektroniczny notariusz
" podpis cyfrowy
" pieniadze cyfrowe
" wybory elektroniczne
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 4
Kryptografia wyklad dla IV roku
Jak to dziala: algorytm symetryczny
1. Alicja i Bolek uzgadniaja algorytm i klucz jakich beda
używać
2. Alicja szyfruje tekst używajac uzgodnionego algorytmu i
klucza otrzymujac kryptogram
3. Alicja przesyla kryptogram do Bolka
4. Bolek deszyfruje kryptogram używajac tego samego
algorytmu i klucza otrzymujac tekst jawny
" Problemy:
klucz musi być przekazywany w sposób tajny
jeśli Ewa wejdzie w posiadanie klucza to może deszy-
szyfrować wszystko, a nawet podszyć sie pod Alicje
jeśli każda para korespondentów w sieci dysponuje
wlasnym kluczem to liczba kluczy szybko rośnie dla
kogoś kto utrzymuje kontakt z wieloma osobami
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 5
Kryptografia wyklad dla IV roku
Jak to dziala: algorytm asymetryczny
1. Alicja i Bolek uzgadniaja kryptosystem z kluczem pu-
blicznym, którego beda używać
2. Bolek przesyla Alicji swój klucz publiczny
3. Alicja szyfruje wiadomość kluczem publicznym Bolka i
przesyla kryptogram do Bolka
4. Bolek deszyfruje kryptogram używajac swojego klucza
prywatnego
lub użytkownicy sieci uzgadniaja kryptosystem i przesylaja
swoje klucze publiczne do bazy na znanym serwerze i wtedy
protokól wyglada jeszcze prościej
1. Alicja i Bolek pobieraja klucze publiczne z serwera
2. Alicja szyfruje wiadomość kluczem publicznym Bolka i
wysyla kryptogram do Bolka
3. Bolek deszyfruje wiadomość Alicji używajac wlasnego
klucza prywatnego
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 6
Kryptografia wyklad dla IV roku
Kryptosystem hybrydowy
1. Bolek wysyla do Alicji swój klucz publiczny
2. Alicja generuje losowy klucz K dla obecnej sesji, szyfruje
go kluczem publicznym Bolka i wysyla kryptogram klucza
EB(K) do Bolka
3. Bolek deszyfruje kryptogram klucza używajac swojego
klucza prywatnego, DB(EB(K))=K, otrzymujac klucz K
dla obecnej sesji
4. oboje używaja klucza K i symetrycznego algorytmu do
szyfrowania i deszyfrowania informacji przesylanych w
czasie tej sesji
" Uwagi:
algorytmy symetryczne sa szybsze niż algorytmy
asymetryczne, co ma znaczenie przy przesylaniu dużej
ilości danych
jeśli Ewa zdobedzie klucz K, to może go użyć do
deszyfrowania jedynie aktualnej sesji, potem już jest
bezużyteczny
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 7
Kryptografia wyklad dla IV roku
Podpis cyfrowy: kryptosystem z kluczem
publicznym
1. Alicja szyfruje dokument używajac swojego klucza
prywatnego, podpisujac w ten sposób dokument
2. Alicja przesyla tak podpisany dokument do Bolka
3. Bolek deszyfruje dokument używajac klucza publicznego
Alicji, weryfikujac w ten sposób podpis Alicji
" Uwagi:
podpis jest prawdziwy; Bolek weryfikuje go deszyfrujac
kryptogram kluczem publicznym Alicji
podpis nie może być sfalszowany; tylko Alicja zna jej
klucz prywatny
podpis nie może być przeniesiony do innego dokumentu
podpisany dokument nie może być zmieniony; zmie-
niony dokument nie da sie rozszyfrować kluczem
publicznym Alicji
podpis jest niezaprzeczalny;
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 8
Kryptografia wyklad dla IV roku
Jednokierunkowe funkcje hashujace (skrótu)
" dla każdego X latwo jest obliczyć H(X)
" H(X) ma taka sama dlugość dla wszystkich tekstów X
" dla zadanego Y znalezienie takiego X, że H(X) = Y jest
praktycznie niemożliwe
" dla zadanego X trudno znalezć X takie, że H(X) =
H(X )
Elektroniczny notariusz
" dla danego dokumentu X obliczamy wartość H(X) i
publikujemy lub deponujemy u notariusza wartość H(X)
" chcac udowodnić prawdziwość dokumentu X przedsta-
wiamy dokument, obliczamy H(X) i porównujemy z
opublikowana wcześniej wartościa
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 9
Kryptografia wyklad dla IV roku
Szyfr Cezara
" szyfr podstawieniowy monoalfabetyczny
ABCDEFGH I J KLMNOPRS T UVWXYZ
DEFGH I J KLMNOP RSTUVWXY Z ABC
tekst jawny=!KRYP T OGRAF I A
kryptogram=!NUBTWS J UD I LD
Szyfr VigenŁre 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 MPANS S ZYM
tekst =!KR Y PTOGRAF I A
krypt.=!CPWC I OU I SEGM
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 10
Kryptografia wyklad 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 ciagiem bitów M=m1, m2, . . . , mn
" wybieramy losowy ciag bitów K=k1, k2, . . . , kn, który
stanowi klucz
" szyfrowanie polega na wykonaniu operacji xor bit po
bicie;
otrzymujemy w ten sposób losowy ciag bitów stanowiacych
kryptogram C=c1, c2, . . . , cn, gdzie ci = mi " ki
" operacja ta jest odwracalna;
ponieważ a"a = 0 i a"b"b = a, zatem ci"ki = (mi"ki)"ki =
mi
" kryptogram jest losowym ciagiem n bitów
Jeśli ki = mi to ci = 0, w przeciwnym wypadku ci = 1;
1
prawdopodobieństwo, że ci = 0 jest równe niezależnie od
2
wartości mi, zatem i-ty bit kryptogramu jest losowy
" szyfr ten jest nie do zlamania bezpieczeństwo do-
skonale nie można uzyskać żadnej informacji o tekście
jawnym bez znajomości klucza
Ponieważ ci = mi " ki implikuje ki = mi " ci, a kryptogram
c1, c2, . . . , cn odpowiada każdemu możliwemu tekstowi jawnemu
z takim samym prawdopodobieństwem, to na podstawie samego
kryptogramu nie wiemy nic o tekście jawnym
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 11
Kryptografia wyklad dla IV roku
" Problemy:
klucz musi być wcześniej uzgodniony przez Alicje i
Bolka
klucz musi być wybrany naprawde losowo, co nie jest
latwe
klucz musi być przechowywany w bezpieczny sposób
klucz musi być co najmniej tak dlugi jak szyfrowany
tekst
" Przyklad:
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ś, http://zon8.physd.amu.edu.pl/tanas 12
Kryptografia wyklad dla IV roku
DES Data Encryption Standard
" w 1981 r. przyjety w USA jako standard do celów
cywilnych
" algorytm symetryczny
" szczególy algorytmu zostaly opublikowane (podejrzenia o
tylne drzwi)
" szyfruje bloki 64 bitowe (8 liter ASCII z bitem parzystości)
" klucze sa efektywnie 56 bitowe (64 bity minus 8 bitów
parzystości); obecnie uważa sie, że taka dlugość klucza jest
zbyt mala
Etapy DES
" wejście 64 bitowy blok
" permutacja poczatkowa
" blok zostaje podzielony na lewa i prawa polowe po 32 bity
każda
" 16 rund identycznych operacji opisanych funkcja f, w
czasie których dane prawej polowy sa przeksztalcane z
użyciem klucza
w czasie każdej rundy bity klucza sa przesuwane, a
nastepnie 48 bitowy podklucz jest wybierany z 56
bitowego klucza
prawa cześć danych jest rozszerzana do 48 bitów za
pomoca permutacji rozszerzajacej a nastepnie podlega
operacji xor z 48 bitami podklucza
wynik wysylany jest do 8 S-boksów, które produkuja
nowe 32 bity
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 13
Kryptografia wyklad dla IV roku
otrzymane 32 bity sa permutowane w P-boksie
" wynik tych 4 operacji stanowiacych funkcje f podlega
operacji xor z lewa polowa i staje sie nowa prawa polowa
" stara prawa polowa staje sie nowa lewa polowa, i tak 16
razy
" permutacja końcowa
" kryptogram
Jeśli Li i Ri sa lewa i prawa polowa dla i-tej rundy, Ki jest
podkluczem dla tej rundy, to tej rundy mamy
Li = Ri-1
Ri = Li-1 " f(Ri-1, Ki)
" deszyfrowanie DES-em polega na przeprowadzeniu tych
samych operacji co dla szyfrowania tylko podklucze
wystepuja w odwrotnej kolejności
Ponieważ
Ri-1 = Li
Li-1 = Ri " f(Ri-1, Ki) = Ri " f(Li, Ki)
to znajac Li, Ri oraz Ki możemy obliczyć Li-1 i Ri-1.
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 14
Kryptografia wyklad dla IV roku
tekst jawny
64
permutacja poczatkowa
64
L0 R0
48
32
K1 32
32
f
L1 R1
K2
PSfrag replacements
f
L15 R15
K16
f
K15
32
32
R16 L16
64
permutacja końcowa
64
kryptogram
Rysunek 1: Schemat dzialania DES
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 15
Kryptografia wyklad dla IV roku
Li-1 Ri-1 klucz
rotacja rotacja
32 32
28
28
permutacja rozszerzajaca permutacja zweżajaca
48
Ki
48
S-boksy (S1, S2, . . . , S8)
PSfrag replacements
32
permutacja
32
32
28 28
Li Ri klucz
Rysunek 2: Jedna runda DES
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 16
Kryptografia wyklad dla IV roku
Elementy DES
" permutacje poczatkowa i końcowa nie maja znaczenia
kryptograficznego (ulatwiaja 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 poczatkowa IP i końcowa IP-1 (tablice
te czytamy od lewej do prawej, od góry w dól odczytujac kolejne
bity wyniku, a numery umieszczone na kolejnych pozycjach tabeli
oznaczaja numer bitu na wejściu, np. bit 58 wejścia jest pierwszym
bitem wyjścia, itd.)
" generowanie podkluczy
z 64 bitowego losowego klucza otrzymuje sie 56 bitowy
ignorujac co ósmy bit i dokonujac 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 sie na dwie polowy po 28 bitów
polowy sa przesuwane cyklicznie w lewo o 1 lub 2 bity
w zależności od rundy wg reguly
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 17
Kryptografia wyklad dla IV roku
runda 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
przesuniecie 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1
Tablica 3: Przesuniecia polówek klucza
permutacja z kompresja CP (permutowany wybór) daje
48 bitów 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 zweżajaca
" permutacja z rozszerzeniem rozszerza 32 bity Ri do 48
bitów
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 Ri i Ki dzielony
jest na 8 cześci po 6 bitów, z których każda przechodzi
do oddzielnego S-boksu (S1, . . . , S8)
6 bitów wchodzacych do S-boksu przeksztalcanych
jest w 4 bity wyjściowe w specjalny sposób pierwszy i
ostatni bit 6 bitów wejściowych daje liczbe dwubitowa
od 0 3 oznaczajaca wiersz S-boksu, zaś bity 2 5 daja
liczbe 4-bitowa od 0 15, która odpowiada kolumnie
tabeli.
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 18
Kryptografia wyklad dla IV roku
S1 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
S2 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
S3 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
S4 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
S5 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
S6 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
S7 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
S8 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ściu, 1 i 6 bit daja 112 = 310,
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 19
Kryptografia wyklad dla IV roku
zaś bity 2 4 daja 10012 = 910, na przecieciu wiersza
3 i kolumny 9 S1 mamy liczbe 1110 = 01112 (wiersze
i kolumny liczymy od zera). W wyniku otrzymujemy
0111.
" wyniki z 8 S-boksów sa laczone w 32 bitowa liczbe
" na tych 32 bitach dokonuje sie permutacji wg Tablicy 7
oraz operacji xor z 32 bitami lewej polowy otrzymujac
nowa prawa polowe, która przekazywana jest do nastepnej
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órym stosuje sie dwa klucze
K1 i K2
" Szyfrowanie
1. wiadomość szyfrowana jest kluczem K1
2. wynik kroku 1. deszyfrowany jest kluczem K2
3. wynik kroku 2. jest ponownie szyfrowany kluczem K1
" Deszyfrowanie
1. kryptogram deszyfrowany jest kluczem K1
2. wynik kroku 1. szyfrowany jest kluczem K2
3. wynik kroku 2. jest powtórnie deszyfrowany kluczem
K1
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 20
Kryptografia wyklad dla IV roku
Tryby szyfrowania: szyfrowanie blokowe
" ECB Electronic Codebook (Elektroniczna ksia żka
kodowa)
Tekst jawny dzielony jest na bloki o dlugości 64 bity i
każdy blok jest oddzielnie szyfrowany tym samym kluczem
zaleta utrata lub uszkodzenie pojedynczych bloków
nie ma wplywu na możliwość deszyfrowania pozosta-
lych; nadaje sie do szyfrowania baz danych
wada możliwa jest modyfikacja kryptogramu bez
znajomości klucza
" CBC Cipher Block Chaining (Wiazanie bloków)
Szyfrowanie kolejnego bloku zależy od wyniku szyfrowania
poprzedniego bloku; taki sam blok tekstu jawnego jest w
różnych miejscach szyfrowany inaczej kolejny blok tek-
stu jawnego jest poddawany operacji xor z kryptogramem
poprzedniego bloku.
Matematycznie wyglada to nastepujaco:
C1 = EK(M1 " I)
Ci = EK(Mi " Ci-1)
M1 = DK(C1 " I)
Mi = DK(Ci) " Ci-1
gdzie Mi jest i-tym blokiem wiadomości, Ci i-tym blokiem
kryptogramu, zaś I jest losowym ciagiem bitów, który jest
przesylany bez szyfrowania
zalety takie same bloki tekstu jawnego maja różne
kryptogramy; zmiana bitu (przeklamanie) wewnatrz
jednego bloku prowadzi do zmiany tekstu po deszyfro-
waniu tylko w danym bloku i nastepnym
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 21
Kryptografia wyklad dla IV roku
wady nie można usuna ć żadnego bloku z kryp-
togramu; nie nadaje sie do szyfrowania baz danych;
nieodporny na zaklócenia (dodatkowy bit lub utrata
jednego bitu psuja dalszy przekaz)
" CFB Cipher Feedback (Szyfrowanie ze sprzeżeniem
zwrotnym)
Szyfrowaniu podlegaja jednostki mniejsze niż blok (64
bity), np. jeden znak ASCII (1 bajt = 8 bitów). Schemat
dzialania przedstawiony jest na Rys. 3. Tryb ważny w
zastosowaniach sieciowych, np. komunikacja pomiedzy
klawiatura i serwerem. Istotnym elementem CFB jest
rejestr przesuwajacy.
" Dzialanie CFB
1. na poczatku rejestr przesuwajacy zawiera losowy ciag
64 bitów
2. zawartość rejestru przesuwajacego jest szyfrowana za
pomoca klucza K np. algorytmem DES
3. 8 pierwszych bitów kryptogramu jest dodawane mo-
dulo 2 z 8 bitami reprezentujacymi litere wiadomości
(Mi) dajac kryptogram Ci przesylany do odbiorcy
4. Ci jednocześnie przesylane jest do rejestru przesu-
wajacego zajmujac ostatnie 8 bitów i przesuwajac
pozostale bity o 8 pozycji w lewo; przesuniecie to
nie jest cykliczne, tzn. pierwszych 8 bitów jest
usuwanych
5. przy deszyfrowaniu rola wejścia i wyjścia zostaje
zamieniona
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 22
Kryptografia wyklad dla IV roku
Rejestr przesuwajacy
64
K
Szyfrowanie (DES)
64
Kryptogram
8
8 8 8
Mi Ci
(a) Szyfrowanie
Rejestr przesuwajacy
64
Szyfrowanie (DES)
K
PSfrag replacements
64
Kryptogram
8
8 8
Mi Ci
(b) Deszyfrowanie
Rysunek 3: Schemat dzialania CFB
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 23
Kryptografia wyklad dla IV roku
IDEA International Data Encryption
Algorithm
" IDEA jest algorytmem blokowym wprowadzonym w latach
90-tych
" IDEA używa kluczy 128 bitowych
" IDEA jest używana w pakiecie PGP
" IDEA jest algorytmem opatentowanym; można go używać
bezplatnie do celów niekomercyjnych
" IDEA dziala na blokach 64 bitowych i wykorzystuje 3
różne operacje: xor ("), dodawanie modulo 216 ( ) oraz
mnożenie modulo 216 +1 ( ); schemat dzialania algorytmu
przedstawiony jest na Rys. 4
Szyfrowanie
" 64 bitowy blok jest dzielony na 4 bloki po 16 bitów:
X1, X2, X3, X4, które stanowia dane wejściowe dla pierw-
szej rundy algorytmu
" algorytm sklada sie z 8 rund
" w każdej rundzie wykonywane sa wymienione wyżej 3
typy operacji na 16 bitowych blokach z 16 bitowymi
podkluczami (każda runda wymaga 6 podkluczy)
" w wyniku otrzymuje sie 4 bloki po 16 bitów: Y1, Y2, Y3, Y4
" pomiedzy rundami blok 2 i 3 sa zamieniane
" algorytm kończy przeksztalcenie końcowe, które wymaga
4 podkluczy
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 24
Kryptografia wyklad dla IV roku
X1 X2 X3 X4
(1) (1) (1)
(1)
K1 K2 K3
K4
(1)
K5
(1)
K6
PSfrag replacements
Pierwsza runda
Kolejne 7 rund
Transformacja końcowa
(9)
(9) (9) (9)
K1
K2 K3 K4
Y1 Y2 Y3 Y4
Rysunek 4: Schemat dzialania algorytmu IDEA:
" operacja xor, dodawanie modulo 216,
mnożenie modulo 216 + 1,
(r)
Ki i-ty podklucz dla r-tej rundy
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 25
Kryptografia wyklad dla IV roku
Generowanie podkluczy
" IDEA używa klucza 128 bitowego i wymaga 86+4=52
podklucze
1. 128 bitowy klucz jest dzielony na bloki 16 bitowe, co
daje 8 podkluczy
2. na kluczu wykonuje sie przesuniecie cykliczne o 25
pozycji i znowu dzieli na bloki 16 bitowe, co daje
kolejne 8 podkluczy
3. operacje z punktu 2 powtarza sie tak dlugo aż wygene-
ruje sie wszystkie podklucze
Deszyfrowanie
" Deszyfrowanie algorytmem IDEA przebiega wg sche-
matu przedstawionego na Rys. 4, w którym zamiast
X1, X2, X3, X4 na wejściu podaje sie bloki Y1, Y2, Y3, Y4
kryptogramu oraz klucz K (ten sam co przy szyfrowaniu)
(r)
" z klucza K generuje sie podklucze Ki
" generuje sie podklucze deszyfrujace K (r) wg schematu
i
przedstawionego w Tablicy 8
Runda K (r) K (r) K (r) K (r) K (r) K (r)
1 2 3 4 5 6
-1 -1
(10-r) (10-r) (10-r) (10-r) (9-r) (9-r)
r = 1 K1 -K2 -K3 K4 K5 K6
-1 -1
(10-r) (10-r) (10-r) (10-r) (9-r) (9-r)
2d" r d" 8 K1 -K3 -K2 K4 K5 K6
-1 -1
(10-r) (10-r) (10-r) (10-r)
r = 9 K1 -K2 -K3 K4
Tablica 8: Tworzenie podkluczy deszyfrujacych K (r) na pod-
i
(r)
stawie podkluczy szyfrujacych Ki w algorytmie IDEA (dla
Ki = 0 przyjmuje sie (Ki)-1 = 0; 216 a" -1 mod 216 + 1)
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 26
Kryptografia wyklad dla IV roku
AES Advanced Encryption Standard
Rijndael
" Nowy standard przyjety w 2001 r. w USA
" algorytm blokowy, który zaprojektowali Joan Daemen i
Vincent Rijmen
" zarówno dlugość bloku jak i klucza może być wybrana
jako 128, 192 lub 256 bitów
" Rijndael jest ogólnie dostepny
" liczba rund zależy od dlugości bloku
" w każdej rundzie wykonywane sa 4 operacje (macierzowe):
podstawienie w S-boksie, przesuniecie wierszy, mieszanie
kolumn i xor z podkluczem
" podklucze sa generowane algorytmem, który zależy od
rundy
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 27
Kryptografia wyklad dla IV roku
Algorytmy asymetryczne RSA
" Witfield Diffie i Martin Hellman idea kryptografii z
kluczem publicznym, rok 1976
" RSA Ron Rivest, Adi Shamir i Leonard Adleman, rok
1978
" bezpieczeństwo algorytmu RSA opiera sie na trudności
obliczeniowej zwiazanej z rozkladem dużych liczb na
czynniki (faktoryzacja)
Wybierzmy dwie duże liczby pierwsze p i q i obliczmy ich
iloczyn (iloczyn latwo obliczyć)
n = pq,
nastepnie wybierzmy losowo liczbe e < n wzglednie pierwsza
z liczba (p - 1)(q - 1). Liczba e bedzie kluczem szyfrujacym.
Teraz znajdzmy liczbe d taka, że
ed a" 1 (mod (p - 1)(q - 1)),
lub inaczej
d a" e-1 (mod (p - 1)(q - 1)).
Liczby d i n sa także wzglednie pierwsze. Do obliczenia d można
użyć rozszerzonego algorytmu Euklidesa. Liczba d jest kluczem
deszyfrujacym. Liczby {e, n} stanowia klucz publiczny, który
ujawniamy, zaś liczby {d, n} stanowia klucz prywatny, który
powinien być ściśle chroniony (liczba d)
" Szyfrowanie
Wiadomość dzielimy na bloki mi mniejsze niż n, które
szyfrujemy używajac formuly
ci a" me (mod n)
i
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 28
Kryptografia wyklad dla IV roku
" Deszyfrowanie
Tekst jawny z kryptogramu otrzymujemy obliczajac
mi a" cd (mod n)
i
" Uzasadnienie
Ponieważ ed a" 1 (mod (p - 1)(q - 1)), to istnieje liczba
calkowita k taka, że ed = 1 + k(p - 1)(q - 1). Z malego
twierdzenia Fermata, dla NW D(m, p) = 1, mamy
mp-1 a" 1 (mod p)
podnoszac obie strony tej kongruencji do potegi k(q - 1) oraz
mnożac przez m otrzymujemy
m1+k(p-1)(q-1) a" m (mod p)
Kongruencja ta jest także prawdziwa dla NW D(m, p) = p,
ponieważ wtedy obie strony przystaja do 0 (mod p). Zatem,
zawsze mamy
med a" m (mod p).
Podobnie,
med a" m (mod q),
a ponieważ p i q sa różnymi liczbami pierwszymi, to z chińskiego
twierdzenia o resztach otrzymujemy
med a" m (mod n)
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 29
Kryptografia wyklad dla IV roku
" Przyklad (trywialny):
Znajdowanie klucza:
p = 1123 q = 1237
n = pq = 1389151
Ć = (p - 1)(q - 1) = 1386792
e = 834781
d a" e-1 (mod Ć) = 1087477
Szyfrowanie:
m = 983415
c a" me (mod n)
983415834781 (mod 1389151) = 190489
Deszyfrowanie:
m a" cd (mod n)
1904891087477 (mod 1389151) = 983415
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 30
Kryptografia wyklad dla IV roku
Troche matematyki
" Podzielność liczb
Dla danych liczb calkowitych a i b mówimy, że liczba b jest
podzielna przez a lub, że liczba a dzieli liczbe b, jeżeli istnieje
taka liczba calkowita d, że b = ad. Liczbe a nazywamy
dzielnikiem liczby b, a fakt ten zapisujemy a|b.
Każda liczba b > 1 ma co najmniej dwa dzielniki dodatnie:
1 i b.
Dzielnikiem nietrywialnym liczby b nazywamy dzielnik
dodatni różny od 1 i b.
Liczba pierwsza to liczba wieksza od 1 nie majaca innych
dzielników dodatnich niż 1 i ona sama.
Liczba majaca co najmniej jeden nietrywialny dzielnik jest
liczba zlożona.
" Twierdzenie o rozkladzie na czynniki pierwsze
Każda liczba naturalna n może być przedstawiona jedno-
znacznie (z dokladnościa do kolejności czynników) jako
iloczyn liczb pierwszych.
Zwykle taki rozklad zapisujemy jako iloczyn odpowiednich
poteg różnych liczb pierwszych, np. 6600 = 23 3 52 11.
" Wlasności relacji podzielności
1. Jeśli a|b i c jest dowolna liczba calkowita, to a|bc.
2. Jeśli a|b i b|c, to a|c
3. Jeśli a|b i a|c, to a|b ą c
4. Jeśli liczba pierwsza p dzieli ab, to p|a lub p|b
5. Jeśli m|a i n|a oraz m i n nie maja wspólnych dzielników
wiekszych od 1, to mn|a
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 31
Kryptografia wyklad dla IV roku
" Najwiekszy wspólny dzielnik NW D(a, b)
Najwiekszy wspólny dzielnik, NW D(a, b), dla danych dwóch
liczb calkowitych (nie bedacych jednocześnie zerami), to
najwieksza liczba calkowita d bedaca dzielnikiem zarówno a,
jak i b.
Przyklad: NW D(12, 18) = 6
" Najmniejsza wspólna wielokrotność NW W (a, b)
Najmniejsza wspólna wielokrotność, NW W (a, b), to najmniej-
sza dodatnia liczba calkowita, która dziela a i b.
NW W (a, b) = a b/NW D(a, b)
Przyklad: NW W (12, 18) = 36 = 12 18/NW D(12, 18)
" Liczby wzglednie pierwsze
Liczby a i b sa wzglednie pierwsze jeżeli NW D(a, b) = 1,
tzn. liczby a i b nie maja wspólnego dzielnika wiekszego
od 1.
NW D(841, 160) = 1 zatem liczby 841 i 160 sa wzglednie
pierwsze (patrz niżej)
" Algorytm Euklidesa
Algorytm Euklidesa pozwala znalezć NW D(a, b) w czasie
wielomianowym (dla a > b, O(ln2(a)))
Dla a > b, dzielimy a przez b otrzymujac iloraz q1 i reszte
r1, tzn. a = q1b + r1, w nastepnym kroku b gra role a, zaś
r1 gra role b: b = q2r1 + r2. Postepowanie to kontynuujemy
dzielac kolejne reszty, ri-2 = qiri-1 + ri, aż do momentu kiedy
otrzymamy reszte, która dzieli poprzednia reszte. Ostatnia
niezerowa reszta jest NW D(a, b).
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 32
Kryptografia wyklad dla IV roku
Obliczmy NW D(841, 160)
841 = 5 160 + 41
160 = 3 41 + 37
41 = 1 37 + 4
37 = 9 4 + 1
4 = 4 1 + 0
Ponieważ NW D(841, 160) = 1, to liczby 841 i 160 sa wzglednie
pierwsze.
" Twierdzenie
Najwiekszy wspólny dzielnik dwóch liczb może być przed-
stawiony w postaci kombinacji liniowej tych liczb ze
wspólczynnikami calkowitymi: NW D(a, b) = xa + yb,
przy czym liczby x i y można znalezć w czasie O(ln2(a)).
W poprzednim przykladzie NW D(841, 160) = 1. Korzystajac
z ciagu równości w algorytmie Euklidesa (idac w przeciwna
strone) 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ówno najwiekszy
wspólny dzielnik NW D(a, b) liczb a i b jak i liczby x i y bedace
wspólczynnikami kombinacji liniowej NW D(a, b) = xa + yb.
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 33
Kryptografia wyklad dla IV roku
q r a b x x2 x1 y y2 y1
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żdyn etapie mamy r = x 841 + y 160. Z ostatniego
wiersza odczytujemy:
NW D(841, 160) = 1 = -39 841 + 205 160
Przyporzadkowania w algorytmie sa nastepujace:
q = a/b , r ! a - qb, x ! x2 - qx1, y ! y2 - qy1
a ! b, b ! r, x2 ! x1, x1 ! x, y2 ! y1, y1 ! y
" Kongruencje
Dla danych trzech liczb calkowitych a, b i m mówimy,
że liczba a przystaje do liczby b modulo m i piszemy
a a" b (mod m), gdy różnica a - b jest podzielna przez
m. Liczbe m nazywamy modulem kongruencji.
Wlasności
1. a a" a (mod m)
2. a a" b (mod m) wtedy i tylko wtedy, gdy b a"
a (mod m)
3. Jeśli a a" b (mod m) oraz b a" c (mod m), to
a a" c (mod m)
4. Jeśli a a" b (mod m) i c a" d (mod m), to
a ą c a" b ą d (mod m) oraz ac a" bd (mod m)
Kongruencje wzgledem tego samego modulu można
dodawać, odejmować i mnożyć stronami.
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 34
Kryptografia wyklad dla IV roku
5. Jeśli a a" b (mod m), to a a" b (mod d) dla
każdego dzielnika d|m
6. Jeśli a a" b (mod m), a a" b (mod n), oraz m i n
sa wzglednie pierwsze, to a a" b (mod mn)
7. Dla ustalonej liczby m, każda liczba przystaje modulo
m do jednej liczby zawartej pomiedzy 0 i m - 1.
Przyklady:
27 a" 7 (mod 5) bo 27 - 7 = 4 5
27 a" 2 (mod 5) bo 27 - 2 = 5 5
-8 a" -7 (mod 5) bo -8 - 7 = -3 5
" Twierdzenie
Liczbami a, dla których istnieje liczba b taka, że
ab a" 1 (mod m), sa dokladnie te liczby a, dla któ-
rych NW D(a, m) = 1. Taka liczba odwrotna b = a-1
może być znaleziona w czasie O(ln2(m)).
Ponieważ NW D(841, 160) = 1 (patrz poprzedni przyklad), to
istnieje liczba 160-1 (mod 841). Liczbe te można obliczyć
za pomoca rozszerzonego algorytmu Euklidesa. Ponieważ
1 = -39 841 + 205 160, to 205 160 a" 1 (mod 841), a wiec
160-1 (mod 841) = 205.
" Male twierdzenie Fermata
Niech p bedzie liczba pierwsza. Wtedy każda liczba a spel-
nia kongruencje ap a" a (mod p) i każda liczba a niepo-
dzielna przez p spelnia kongruencje ap-1 a" 1 (mod p).
Liczba 1231 jest liczba pierwsza i NW D(1231, 5871) = 1, wiec
58711230 a" 1 (mod 1231)
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 35
Kryptografia wyklad dla IV roku
" Chińskie twierdzenie o resztach
Jeśli liczby m1, m2, . . . , mk sa parami wzglednie pierw-
sze, tzn. NW D(mi, mj) = 1 dla i = j, wtedy uklad
kongruencji
x a" a1 (mod m1)
x a" a2 (mod m2)
. . . . . .
x a" ak (mod mk)
ma wspólne rozwiazanie modulo m = m1m2 . . . mk.
Przyklad:
x a" 1 (mod 11)
x a" 2 (mod 12)
x a" 3 (mod 13)
Niech Mi = m/mi bedzie iloczynem wszystkich modulów
z wyjatkiem i-tego. Wtedy NW D(mi, Mi) = 1, a wiec
istnieje taka liczba Ni, że MiNi a" 1 (mod mi), wtedy
wspólnym rozwiazaniem modulo m jest x = aiMiNi. Dla
i
każdego i wszystkie skladniki sumy poza i-tym sa podzielne
przez mi, gdyż mi|Mj dla j = i zatem dla każdego i mamy
x a" aiMiNi a" ai (mod mi). W naszym przykladzie mamy:
a1 = 1, a2 = 2, a3 = 3, m1 = 11, m2 = 12, m3 = 13,
m = 1716, M1 = 156, M2 = 143, M3 = 132. Aby znalezć
wspólne rozwiazanie tego ukladu kongruencji należy znalezć
liczby Ni bedace odwrotnościami liczb Mi modulo mi. W
tym celu możemy użyć algorytmu Euklidesa. W wyniku
otrzymujemy liczby: N1 = 6, N2 = 11 i N3 = 7. Zatem
wspólnym rozwiazaniem jest x a" 6 156 + 2 11 143 + 3 7
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 36
Kryptografia wyklad dla IV roku
132 (mod 1716) a" 1706 (mod 1716). W tym przykladzie
widać, że liczba -10 daje takie reszty zatem x = -10 + 1716.
" Funkcja Eulera
Dla n e" 1, niech Ć(n) bedzie liczba tych nieujemnych
liczb b mniejszych od n, które sa wzglednie pierwsze z n.
Funkcja Ć(n) nazywa sie funkcja Eulera.
Funkcja Eulera Ć jest
multiplikatywna , tzn. Ć(mn) =
Ć(m)Ć(n), jeśli tylko NW D(m, n) = 1.
" Twierdzenie Eulera
Jeśli NW D(a, m) = 1, to aĆ(m) a" 1 (mod m).
Wniosek
Jeśli NW D(a, m) = 1 i jeśli n jest reszta z dzielenia n
przez Ć(m), to an a" an (mod m)
" Potegowanie modulo metoda iterowanego podno-
szenia do kwadratu
Podstawowym dzialaniem w kryptografii jest obliczanie
an (mod m), gdzie m i n sa bardzo dużymi liczbami.
Zauważmy, że rozwiniecie dwójkowe liczby n ma postać
k-1
n = ni2i = n0 + 2n1 + 4n2 + + 2k-1nk-1
i=0
,
gdzie ni " {0, 1} sa cyframi rozwiniecia dwójkowego.
Zatem
k-1
n0 1 n1 nk-1
i 0 k-1
an = ani2 = a2 a2 . . . a2
i=0
Zalóżmy, że a < m oraz przyjmijmy, że przez b bedziemy
oznaczali cześciowe iloczyny. Na poczatku b = 1. Jeżeli
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 37
Kryptografia wyklad dla IV roku
n0 = 1 to zastepujemy b przez a, w przeciwnym przypadku
nadal b = 1. Nastepnie liczymy a1 a" a2 (mod m). Jeśli
n1 = 1, to mnożymy b przez a1 i redukujemy modulo
m, zaś jeśli n1 = 0 nie zmieniamy b. Nastepnie liczymy
a2 a" a2 (mod m). Znowu, jeśli n2 = 1, to mnożymy
1
b przez a2; w przeciwnym przypadku nie zmieniamy b.
Postepujac dalej w ten sposób, w j-tym kroku mamy
obliczona potege aj a" a2j (mod m). Jeśli nj = 1 to
wlaczamy aj do iloczynu b, jeśli nj = 0 to b sie nie zmienia.
Po k - 1 krokach otrzymamy b a" an (mod m).
Przyklad:
Obliczmy 7698 (mod 1234) = 287
i 0 1 2 3 4 5 6 7 8 9
ni 0 1 0 1 1 1 0 1 0 1
ai 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 liczbe liczb pierwszych d" x. Wtedy
Ą(x)
lim = 1
x "
x/ ln x
Dla x e" 17
x
Ą(x) >
ln x
Dla przykladu, dla x = 1010, Ą(x) = 455052511, natomiast
x/ ln x = 434294481.
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 38
Kryptografia wyklad dla IV roku
" Testy pierwszości
Istnieja probabilistyczne testy pierwszości liczb, które
pozwalaja z dużym prawdopodobieństwem w skończonym
czasie dać odpowiedz czy dana liczba jest pierwsza.
Test Fermata
Testujemy czy liczba n jest pierwsza. Wybieramy losowo
liczbe a < n - 1, obliczamy r = an-1 (mod n), jeśli
r = 1 to n jest liczba zlożona. Test przeprowadzamy
t-krotnie, t e" 1. Jeśli wszystkie testy wypadna pomyślnie,
tzn. r = 1, to liczbe uznajemy za pierwsza, choć może tak
nie być.
Test Millera-Rabina
Testujemy czy liczba n jest pierwsza. Piszemy n-1 = 2sr,
gdzie r jest nieparzyste. Wybieramy losowo liczbe a,
2 d" a d" n - 2. Obliczamy y = ar (mod n). Jeśli
y = 1 lub y = n - 1 to n jest zlożona. Obliczamy
a2, a4, . . . , (a2)j tak dlugo aż a2j a" 1 (mod n) lub
j = s. Jeśli wszystkie (a2)j a" 1 (mod n) to uznajemy,
że liczba n jest pierwsza.
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 39
Kryptografia wyklad dla IV roku
Algorytm ElGamala
U podstaw dzialania algorytmu ElGamala leży matema-
tyczny problem logarytmu dyskretnego. Niech p bedzie liczba
pierwsza, przez Zp oznaczamy zbiór liczb {0, 1, . . . , p - 1} i
niech g bedzie generatorem Zp, tzn. takim elementem, że dla
każdej liczby 0 < a < p istnieje takie i, że a a" gi (mod p)
(wszystkie elementy z wyjatkiem zerowego moga być wyge-
nerowane z g).
Problem logarytmu dyskretnego polega na znalezieniu dla
danej liczby 0 < b < p takiej liczby a, że ga a" b (mod p).
Przyklad:
Wezmy Z19, czyli zbiór liczb {0, 1, . . . , 18} oraz g = 2. Niech
b = 2a (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ór klucza
Wybieramy odpowiednio duża liczbe pierwsza p, taka, że
obliczenie logarytmu dyskretnego jest praktycznie niewy-
konalne, wybieramy liczbe calkowita 0 < a < p - 1 oraz
liczbe g, nastepnie obliczamy b a" ga (mod p). Liczby
{b, g, p} stanowia klucz publiczny, zaś liczby {a, g, p} klucz
prywatny.
" Szyfrowanie
Aby zaszyfrować wiadomość M wybieramy losowo liczbe
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 40
Kryptografia wyklad dla IV roku
k wzglednie pierwsza z p - 1, a nastepnie obliczamy
c1 a" gk (mod p)
c2 a" M bk (mod p)
Para liczb c1 i c2 tworzy kryptogram, który jest dwukrot-
nie dluższy od tekstu jawnego.
" Deszyfrowanie
M = c2(ca)-1 (mod p)
1
" Uzasadnienie
c2(ca)-1 a" M bk(gka)-1 a" Mgka(gka)-1 a" M (mod p)
1
" Prosty przyklad
Znajdowanie klucza
Niech p = 229 i g = 6, wybieramy a = 70, wtedy b a"
670 (mod 229) = 97, zatem klucz publiczny stanowia liczby
{97, 6, 229}, zaś klucz prywatny stanowia liczby {70, 6, 229}
Szyfrowanie
Niech wiadomość M = 130, wybieramy k = 127 takie, że
NW D(127, 228) = 1 (liczby tej nie ujawniamy)
c1 a" 6127 (mod 229) = 155
c2 a" 130 97127 (mod 229) = 169
Deszyfrowanie
M = 169 (15570)-1 (mod 229) a" 169 36 (mod 229) = 130
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 41
Kryptografia wyklad dla IV roku
Jednokierunkowe funkcje hashujace (skrótu)
" dla każdego X latwo jest obliczyć H(X)
" H(X) ma taka sama dlugość dla wszystkich tekstów X
" dla zadanego Y znalezienie takiego X, że H(X) = Y jest
praktycznie niemożliwe; funkcja jednokierunkowa
" dla danego X trudno znalezć X takie, że H(X) = H(X );
funkcja slabo bezkonfliktowa
" nie jest praktycznie możliwe znalezienie X i X takich, że
X = X oraz H(X) = H(X ); funkcja silnie bezkonflik-
towa
Typowe zastosowania
" Przechowywanie hasel w komputerach
" Ochrona integralności danych
Algorytm MD5 (Message Digest)
Algorytm, zaprojektowany przez Rivesta, jest modyfikacja
wcześniejszego algorytmu MD4. Wiadomość dowolnej dlu-
gości jest przeksztalcona w jej 128 bitowy
odcisk palca
(sume kontrolna, skrót wiadomości). Zasadnicza procedura
algorytmu dziala na blokach 512 bitowych przeksztalcajac je
w 128 bitowe skróty.
Etapy MD5
" Krok 1
Wiadomość dowolnej dlugości jest uzupelniana w taki
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 42
Kryptografia wyklad dla IV roku
sposób, że na końcu dodawany jest bit i odpowiednia
1
ilość zer, tak aby ostatni blok mial dlugość 448 bitów.
" Krok 2
Do ostatniego bloku dodawana jest 64 bitowa liczba
reprezentujaca dlugość wiadomości (w bitach) i w ten
sposób przygotowana wiadomość ma dlugość bedaca
calkowita wielokrotnościa 512 bitów. Tym samym wia-
domość jest wielokrotnościa 16 slów 32-bitowych. Niech
M0, M1, . . . MN-1 oznaczaja kolejne slowa wiadomości,
gdzie N jest jest wielokrotnościa 16.
" Krok 3
Algorytm operuje na 32-bitowych zmiennych a, b, c, d,
których wartości poczatkowe A, B, C, D w zapisie szest-
nastkowym sa nastepujace:
A =0x67452301
B =0xefcdab89
C =0x98badcfe
D =0x10325476
" Krok 4
Glówna petla algorytmu sklada sie z 4 rund, w każdej
rundzie 16 razy wykonywane sa operacje na 32 bitowych
slowach. Operacje te zdefiniowane sa 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 operacje xor, '" operacje and, (" operacje
or, zaś Ź operacje 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ś, http://zon8.physd.amu.edu.pl/tanas 43
Kryptografia wyklad dla IV roku
Niech Xj = Mi"16+j oznacza j-te slowo w i-tym bloku
wiadomości M (j = 0, . . . , 15, i = 0, . . . , N/16 - 1),
! s niech oznacza cykliczne przesuniecie w lewo o s
bitów oraz zdefiniujmy liczby Tk (k = 1, . . . , 64) tak, że
Tk = 232 | sin k| , gdzie k jest w radianach. Mamy wtedy:
Runda 1
Niech [abcd j s k] oznacza operacje
a = b + ((a + F (b, c, d) + Xj + Tk) ! 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 operacje
a = b + ((a + G(b, c, d) + Xj + Tk) ! 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 operacje
a = b + ((a + H(b, c, d) + Xj + Tk) ! 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ś, http://zon8.physd.amu.edu.pl/tanas 44
Kryptografia wyklad dla IV roku
Runda 4
Niech [abcd j s k] oznacza operacje
a = b + ((a + I(b, c, d) + Xj + Tk) ! 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ści a, b, c, d sa dodawane do
wartości A, B, C, D i algorytm przechodzi do nastep-
nego bloku M.
Blok wiadomości M (512 bitów)
PSfrag replacementsA
A
Runda 1 Runda 2 Runda 3
Runda 4
B B
C
C
F H I
G
D D
Rysunek 5: Glówna petla algorytmu MD5
" Krok 5
Po przejściu wszystkich 512-bitowych bloków wiadomości
M algorytm laczy rejestry a, b, c, d dajac 128 bitowa liczbe
bedaca wartościa funkcji hashujacej.
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 45
Kryptografia wyklad 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ść funkcji hashujacej to liczba 160 bitowa i w zwiazku
z tym algorytm wymaga 5 rejestrów zamiast 4. Używa też
w nieco inny sposób nieliniowych funkcji transformujacych,
dokonuje dodatkowych operacji na poszczególnych slowach
wiadomości, w każdej rundzie wykonuje 20 operacji zamiast
16. Zasada dzialania jest jednak bardzo podobna do MD5.
Ogólnie uważa sie, że jest bezpieczniejszy niż MD5 ze wzgledu
na
dluższa wartość funkcji hashujacej i pewne ulepszenia
samego algorytmu.
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 46
Kryptografia wyklad dla IV roku
Szyfrowanie strumieniowe i generatory
ciagów pseudolosowych
" Synchroniczne szyfrowanie strumieniowe
Ciag bitów klucza generowany jest niezależnie od szyfro-
wanej wiadomości i kryptogramu.
Musi być zachowana synchronizacja pomiedzy nadawca
i odbiorca.
Zmiana bitu kryptogramu (przeklamanie) nie wplywa
na możliwość deszyfrowania pozostalych bitów.
Dodanie lub usuniecie bitu powoduje utrate synchroni-
zacji.
Istnieje możliwość zmiany wybranych bitów kryp-
togramu, a co za tym idzie zmiany deszyfrowanej
wiadomości.
PSfrag replacements
mi ci
ci mi
ki
K ki K
GK
GK
(a) Szyfrowanie (b) Deszyfrowanie
Rysunek 6: Model synchronicznego szyfrowania strumieniowego
z dodawaniem modulo 2 ("), GK jest generatorem ciagu bitów
klucza, zaś K jest kluczem inicjalizujacym generator
Tekst jawny szyfrowany jest bit po bicie (one-time pad).
Losowo generowane bity k1, k2, . . . , ki stanowia bity klucza,
które sa dodawane modulo 2 (operacja xor) do bitów wia-
domości m1, m2, . . . , mi w sposób ciagly dajac kolejne bity
kryptogramu c1, c2, . . . , ci, gdzie ci = mi " ki
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 47
Kryptografia wyklad dla IV roku
" Samosynchronizujace (asynchroniczne) szyfrowa-
nie strumieniowe
CFB (Cipher Feedback) z blokiem jednobitowym
Utrata lub dodanie bitu w kryptogramie powoduje
utrate tylko kawalka wiadomości samosynchroniza-
cja.
Ograniczona propagacja bledów.
Zmiana bitu kryptogramu powoduje, że kilka innych
bitów bedzie deszyfrowanych blednie latwiej wykryć
taka zmiane.
Jednak na skutek samosynchronizacji wykrycie zmian
w kryptogramie jest trudniejsze (jeśli zmiany dotycza
tylko cześci kryptogramu, to dalsza cześć jest deszyfro-
wana poprawnie).
PSfrag replacements
Rejestr przesuwajacy Rejestr przesuwajacy
bn bn-1 bn-2 . . . . . . b1 bn bn-1 bn-2 . . . . . . b1
mi
ci
ci mi
ki K ki
K
G G
Generowane bity
(a) Szyfrowanie (b) Deszyfrowanie
Rysunek 7: Model samosynchronizujacego szyfrowania strumie-
niowego
" Generatory ciagów pseudolosowych
Do generowania klucza potrzebny jest generator losowego
ciagu bitów. Generowanie prawdziwie losowego ciagu
jest trudne, wiec zwykle stosuje sie ciagi pseudolosowe.
Ciagi pseudolosowe to ciagi, które spelniaja statystyczne
wlasności ciagów losowych, ale generowane sa w sposób
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 48
Kryptografia wyklad dla IV roku
deterministyczny: generator startujacy z takiego samego
stanu poczatkowego generuje taki sam ciag bitów. Z
tego wzgledu ciagi pseudolosowe używane w kryptografii
musza spelniać warunki znacznie ostrzejsze niż np. ciagi
pseudolosowe używane w symulacjach.
" LFSR Linear Feedback Shift Register (Rejestr
PSfrag replacements
przesuwajacy z liniowym sprzeżeniem zwrotnym)
Rejestr przesuwajacy
Generowane bity
bn bn-1 bn-2 bn-3 . . . . . . b7 b6 b5 b4 b3 b2 b1
Rysunek 8: Generowanie ciagu bitów za pomoca LFSR
LFSR posiada rejestr przesuwajacy o dlugości n bitów,
który na poczatku zawiera losowe bity.
Niektóre bity rejestru sa poddawane operacji xor (")
i wynik zastepuje najstarszy bit rejestru, jednocześnie
pozostale bity przesuwane sa o jedna pozycje w prawo i
najmlodszy bit staje sie kolejnym bitem generowanego
ciagu.
Przyklad:
Wezmy rejestr 4-bitowy, którego pierwszy i czwarty bit sa
poddawane operacji xor i niech poczatkowo rejestr zawiera
same jedynki. Wtedy otrzymujemy nastepujace stany rejestru:
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 49
Kryptografia wyklad 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 ciag to najmlodsze (prawe) bity kolejnych stanów
rejestru, czyli:
1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 . . .
Ponieważ n-bitowy rejestr może znalezć sie w jednym z 2n - 1
stanów, wiec teoretycznie może on generować ciag o dlugości
2n - 1 bitów. Potem ciag sie powtarza. (Wykluczamy ciag
samych zer, który daje niekończacy sie ciag zer)
" LFSR ma slaba wartość kryptograficzna gdyż znajomość
2n kolejnych bitów ciagu pozwala na znalezienie wartości
generowanych od tego miejsca.
" LFSR dziala jednak bardzo szybko, zwlaszcza jeśli jest
to uklad hardware owy, i stad jest on bardzo atrakcyjny
w praktycznych zastosowaniach. Można konstruować
bardziej skomplikowane uklady zawierajace kilka LFSR
i nieliniowa funkcje f przeksztalcajaca bity generowane
przez poszczególne LFSR.
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 50
Kryptografia wyklad dla IV roku
LFSR 1
LFSR 2
Generowany ciag
f
PSfrag replacements
LFSR n
Generowane bity
Rysunek 9: Uklad zlożony z wielu LFSR
Przyklad: Generator Geffe
x1
x1 '" x2
LFSR 1
PSfrag replacements
x2
f(x1, x2, x3)
LFSR 2
Ź x2 '" x3
x3
LFSR n
Rysunek 10: Generator Geffe: f(x1, x2, x3) = (x1 '" x2) " (Ź x2 '" x3)
Generator Geffe ma slabe wlasności kryptograficzne ze
wzgledu na korelacje pomiedzy generowanymi bitami i
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 51
Kryptografia wyklad dla IV roku
bitami LFSR 1 lub LFSR 2
Niech y(t) = f(x1(t), x2(t), x3(t)), wtedy
P (y(t) = x1(t)) = P (x2(t) = 1) + P (x2(t) = 0) P (x3(t) =
1 1 1 3
x1(t)) = + = , i podobnie dla x3(t).
2 2 2 4
" Generatory sterowane zegarem
Generator o zmiennym kroku (alternating step gene-
rator)
LFSR 2
Zegar Generowane bity
LFSR 1
PSfrag replacements
LFSR 3
Rysunek 11: Generator o zmiennym kroku
LFSR 1 jest przesuwany w każdym takcie zegara.
Jeśli na wyjściu LFSR 1 jest 1 to LFSR 2 jest przesu-
wany; LFSR 3 nie jest przesuwany (poprzedni bit jest
powtarzany).
Jeśli na wyjściu LFSR 1 jest 0 to LFSR 3 jest przesu-
wany; LFSR 2 nie jest przesuwany (poprzedni bit jest
powtarzany).
Wyjściowe bity LFSR 2 i LFSR 3 sa dodawane modulo
2 (") dajac kolejny bit generowanego ciagu.
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 52
Kryptografia wyklad dla IV roku
Shrinking generator
ai
LFSR 1
PSfrag replacements
Zegar
LFSR 3
wyślij bi jeżeli ai = 1
bi
LFSR 2
opuść bi jeżeli ai = 0
Rysunek 12: Shrinking generator
" Generatory, których bezpieczeństwo oparte jest na
trudnościach obliczeniowych
Generator Blum-Micali
W generatorze tym wykorzystuje sie trudność w obliczaniu
logarytmu dyskretnego. Wybieramy dwie liczby pierwsze
a i p oraz liczbe x0 (zarodek), a nastepnie obliczamy
xi+1 = axi mod p dla i = 1, 2, 3, . . .
Pseudolosowy ciag bitów tworzymy w nastepujacy sposób:
ńł
ł
1 jeżeli xi < (p - 1)/2
ki =
ół
0 w przeciwnym przypadku
Generator RSA
Generator oparty na trudności z faktoryzacja liczb.
Wybieramy dwie liczby pierwsze p i q (N = pq) oraz liczbe
e wzglednie pierwsza z (p - 1)(q - 1). Wybieramy losowa
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 53
Kryptografia wyklad dla IV roku
liczbe (zarodek) x0 mniejsza od N, a nastepnie obliczamy
xi+1 = xe (mod N)
i
generowanym bitem jest najmlodszy bit xi
Generator Blum-Blum-Shub BBS
Znajdujemy dwie duże liczby pierwsze p i q, takie, że
p a" 3 (mod 4) oraz q a" 3 (mod 4); N = pq.
Wybieramy losowa liczbe x wzglednie pierwsza z N, a
nastepnie obliczamy
x0 = x2 (mod N)
x0 stanowi zarodek dla generatora. Teraz liczymy
xi+1 = x2 (mod N)
i
Generowanym bitem ki jest najmlodszy bit xi+1.
" Generator RC 4
Generator RC 4 zostal opracowany przez Rona Rivesta
w 1987 r. Przez kilka lat byl to algorytm tajny. W
1994 r. ktoś w Internecie opublikowal program realizujacy
ten algorytm. Od tego czasu algorytm nie stanowi
tajemnicy. Algorytm ten pracuje w trybie OFB (Output
Feedback). Ciag generowany przez RC 4 jest losowym
ciagiem bajtów.
Algorytm używa dwóch wskazników i, j przyjmuja-
cych wartości 0, 1, 2, . . . , 255 oraz S-boksu z warto-
ściami S0, S1, . . . , S255, które tworza permutacje liczb
0, 1, . . . , 255.
Inicjalizacja: Na poczatku i = j = 0, Sl = l dla
l = 0, 1, . . . , 255, kolejna 256-bajtowa tablica wy-
pelniana jest bajtami klucza, przy czym klucz jest
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 54
Kryptografia wyklad dla IV roku
używany wielokrotnie, aż do wypelnienia calej tablicy
K0, K1, . . . , K255. Nastepnie wykonujemy:
for i = 0 to 255:
j = (j + Si + Ki) (mod 256)
zamień Si z Sj
Generowanie kolejnego bajtu:
i = i + 1 (mod 256)
j = j + Si (mod 256)
zamień Si z Sj
l = Si + Sj (mod 256)
K = Sl
Otrzymany bajt K jest dodawany modulo 2 (xor)
z kolejnym bajtem wiadomości dajac kolejny bajt
kryptogramu (przy deszyfrowaniu role tekstu jawnego i
kryptogramu sie zamieniaja).
Algorytm RC 4 jest używany w wielu programach komer-
cyjnych.
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 55
Kryptografia wyklad dla IV roku
Podpis cyfrowy
Przypomnijmy:
System kryptograficzny z kluczem publicznym może być
wykorzystany do podpisywania dokumentów cyfrowych.
1. Alicja szyfruje dokument używajac swojego klucza
prywatnego, podpisujac w ten sposób dokument
2. Alicja przesyla tak podpisany dokument do Bolka
3. Bolek deszyfruje dokument używajac klucza publicznego
Alicji, weryfikujac w ten sposób podpis Alicji
" Uwagi:
podpis jest prawdziwy; Bolek weryfikuje go deszyfrujac
kryptogram kluczem publicznym Alicji
podpis nie może być sfalszowany; tylko Alicja zna jej
klucz prywatny
podpis nie może być przeniesiony do innego dokumentu
podpisany dokument nie może być zmieniony; zmie-
niony dokument nie da sie rozszyfrować kluczem
publicznym Alicji
podpis jest niezaprzeczalny;
wada tego sposobu podpisywania dokumentów jest
jednak to, że podpis jest conajmniej tak dlugi jak sam
dokument
Podpis z wykorzystaniem jednokierunkowej funkcji
hashujacej
1. Alicja używa funkcji hashujacej do dokumentu, który ma
podpisać, otrzymujac skrót ( odcisk palca ) dokumentu
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 56
Kryptografia wyklad dla IV roku
2. Alicja podpisuje skrót dokumentu szyfrujac go swoim
kluczem prywatnym
3. Alicja przesyla Bolkowi dokument i podpisany skrót
4. Bolek używa tej samej funkcji hashujacej do otrzymania
skrótu dokumentu, a nastepnie deszyfruje podpisany
skrót używajac klucza publicznego Alicji; jeśli zdeszy-
frowany skrót zgadza sie z otrzymanym przez niego to
podpis jest prawdziwy
podpis jest znacznie krótszy od dokumentu
można sprawdzić istnienie podpisu bez ogladania
samego dokumentu
Schemat ElGamala podpisu cyfrowego
" Generowanie kluczy
Alicja wybiera duża liczbe pierwsza p oraz liczbe
g " Zp (generator grupy multiplikatywnej Z")
p
Alicja wybiera liczbe losowa 0 < a < p - 1 oraz
oblicza b a" ga (mod p)
Kluczem publicznym Alicji sa liczby {b, g, p} zaś
kluczem prywatnym liczby {a, g, p}
" Podpisywanie
Alicja wybiera liczbe losowa k (tajna), taka, że
0 < k < p - 1 oraz NW D(k, p - 1) = 1
Alicja oblicza
r = gk (mod p),
k-1 (mod p),
s = k-1 [H(M) - ar] (mod p - 1).
Podpisem Alicji dla wiadomości M jest para liczb
{r, s}
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 57
Kryptografia wyklad dla IV roku
" Weryfikacja
Bolek aby stwierdzić prawdziwość podpisu Alicji
pobiera klucz publiczny Alicji {b, g, p}
Bolek sprawdza czy 0 < r < p, jeśli nie, podpis nie
jest prawdziwy
Bolek oblicza
x1 = brrs (mod p),
x2 = gH(M) (mod p).
Bolek akceptuje podpis jeśli x1 = x2
" Uzasadnienie
Ponieważ s a" k-1 [H(M) - ar] (mod p - 1), to mnożac
stronami przez k mamy ks a" H(M) - ar (mod p - 1) i
po przeksztalceniu H(M) a" ar + ks (mod p - 1), a co
za tym idzie gH(M) a" gar+ks a" (ga)rrs a" brrs (mod p).
Tak wiec x1 = x2.
DSA Digital Signature Algorithm
Algorytm podpisu cyfrowego zatwierdzony w 1994 r. przez
NIST jako standard podpisu cyfrowego w USA (Digital
Signature Standard DSS). Wykorzystuje funkcje hashujaca
SHA-1.
" Generacja klucza
Alicja wybiera liczbe pierwsza q o dlugości 160 bitów
Alicja wybiera liczbe pierwsza p o dlugości 512 d" l d"
1024, przy czym 64|l, taka, że q|p - 1
Alicja wybiera element g " Zp i oblicza
b = g(p-1)/q (mod p);
jeśli b = 1 to wybiera inne g.
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 58
Kryptografia wyklad dla IV roku
Alicja wybiera liczbe losowa a, 0 < a < q, i oblicza
c = ba (mod p)
Kluczem publicznym Alicji jest zbiór liczb {b, c, p, q}
" Podpisywanie
Alicja wybiera tajna liczba losowa k, 0 < k < q,
Alicja oblicza
r = (bk (mod p)) (mod q),
k-1 (mod q),
s = k-1 [H(M) + ar] (mod q).
Podpisem Alicji dla wiadomości 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śli nie, to
podpis jest falszywy
Bolek oblicza
H(M) i w = s-1 (mod q),
u1 = w H(M) (mod q),
u2 = rw (mod q),
v = (bu1cu2 (mod p)) (mod q).
Bolek uznaje podpis za prawdziwy jeśli v = r.
" Uzasadnienie
Jeśli {r, s} jest prawdziwym podpisem Alicji dla wiadomości
M, to H(M) a" -ar+ks (mod q). Mnożac stronami przez w
i przeksztalcajac otrzymujemy w H(M) + arw a" k (mod q),
co jest równoważne u1 + au2 a" k (mod q). Podnoszac b do
potegi lewej i prawej strony tej kongruencji otrzymujemy
(bu1+au2 (mod p)) (mod q) a" (bk (mod p)) (mod q)
i dalej mamy
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 59
Kryptografia wyklad dla IV roku
(bu1cu2 (mod p)) (mod q) a" (bk (mod p)) (mod q),
a to oznacza v = r.
Ślepe podpisy cyfrowe
Zasadniczym zalożeniem protokolów podpisów cyfrowych
jest, że podpisujacy dokument wie co podpisuje. Nie na-
leży podpisywać dokumentów wygladajacych na losowy ciag
bitów. Od powyższej zasady sa jednak odstepstwa. Przypu-
śćmy, że Bolek jest notariuszem, zaś Alicja chce aby Bolek
potwierdzil notarialnie istnienie dokumentu, ale nie chce aby
ten dokument obejrzal. Mamy wtedy do czynienia z tzw.
ślepym podpisem. Wyobrazmy sobie, że Alicja wklada list
do koperty lacznie z kalka, a potem prosi Bolka o zlożenie
podpisu na zaklejonej kopercie. Po otwarciu koperty na liście
bedzie kopia podpisu Bolka. Cyfrowo ślepy podpis można
zrealizować korzystajac np. z algorytmu RSA.
" Ślepy podpis z użyciem RSA
Alicja pobiera klucz publiczny Bolka {e, n}
Alicja wybiera liczbe losowa k, 0 < k < n,
Alicja oblicza z = M ke (mod n) i przesyla z do
Bolka
Bolek oblicza zd = (M ke)d (mod n) używajac
swojego klucza prywatnego {d, n} i wynik przesyla
Alicji
Alicja oblicza s = zd/k (mod n). Ponieważ
zd a" (M ke)d a" Mdk (mod n), wiec zd/k =
Mdk/k a" Md (mod n), czyli s = Md (mod n)
jest podpisem Bolka na wiadomości M.
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 60
Kryptografia wyklad dla IV roku
Niezaprzeczalne podpisy cyfrowe
Podpis niezaprzeczalny nie może być sprawdzony bez zgody
osoby podpisujacej. Podpisujacy nie może sie wyprzeć
swojego podpisu, ale może także dowieść, że podpis jest
falszywy (jeśli jest).
" Niezaprzeczalny podpis oparty na logarytmach
dyskretnych
Przypuśćmy, że strona podpisujaca 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 = Ma (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 = zrbs (mod p) i przesyla Alicji
2. Alicja oblicza
t = a-1 (mod p - 1)
v = wt (mod p)
i przesyla Bolkowi v
3. Bolek sprawdza czy v = Mrgs (mod p)
Uzasadnienie
Zauważmy, że v = wt = zrtbst = (zt)r(bt)s = (Mat)r(gat)s =
Mrgs (mod p)
Ryszard Tanaś, http://zon8.physd.amu.edu.pl/tanas 61
Wyszukiwarka
Podobne podstrony:
Kryptografia z Elementami Kryptografii Kwantowej Tanas p51Chip Potomkowie Enigmy Kryptografia KwantowaWykład 3 Podstawy mechaniki kwantowejMATERIALY WYKLADOWE Podstawy budownictwa 09 KONSTRUKCJA I ELEMENTY BUDYNKUWykład 1 podstawy chemii nieorganicznejWyklad PodstawyElektrotechnikiFinanse Przedsiębiorstwa Wykład 2 Podstawy Zarządzania Finansami Przedsiębiorstwa03 Wykład 3 Podstawowe rozkłady zmiennych losowychidB24WYKŁAD Układy wzmacniaczy operacyjnych z elementami nieliniowymiwykłady z podstaw programowaniaKonspekt wykładów z Podstaw automatyki wykład 5wykład 1 Podstawy Logistyki1Komunikowanie o zdrowiu wykład1a podstawowe pojęciawięcej podobnych podstron