r.wicik@wil.waw.pl
Notes, 1/59
Kryptologia i kryptograficzna ochrona informacji
Istota kryptograficznej ochrony informacji
w systemach teleinformatycznych
dr in
Ŝ
. Robert Wicik
Wojskowy Instytut Ł
ą
czno
ś
ci
r.wicik@wil.waw.pl
rwicik@op.pl
Plan
1.
Literatura
2.
Wprowadzenie – sieci teleinformatyczne – zagro enia i ochrona
3.
Podstawowe poj cia kryptograficznej ochrony informacji
4.
Rodzaje systemów kryptograficznych
5.
Usługi kryptograficznej ochrony informacji
6.
Techniki kryptograficznej ochrony informacji
7.
Szyfry blokowe
8.
Funkcje skrótu i techniki uwierzytelniania
9.
Szyfry strumieniowe
10.
Szyfry z kluczem publicznym
11.
Podpisy cyfrowe
12.
Protokoły
13.
Krzywe eliptyczne
14.
Kryteria bezpiecze stwa dla szyfrów
r.wicik@wil.waw.pl
Notes, 2/59
1. Literatura
•
C. E. Shannon – Communication Theory of Secrecy Systems, Bell System
Technical Journal, vol. 28(4), 1949
•
W. Diffie, M. Hellman, New Directions In Cryptography, IEEE
Transactions on Information Theory 22, 1976
•
D. E. Robling Denning - Kryptografia i ochrona danych, WNT, Warszawa,
1993
•
J. Stokłosa - Kryptograficzne metody ochrony danych, WPP, Pozna , 1992
•
A. Menezes, P. Oorschot, S. Vanston - Handbook of applied cryptography,
CRC Press, 1997
•
B. Schneier - Kryptografia dla praktyków, WNT, Warszawa, 1995
•
J. Pieprzyk, T. Hardjono, J. Sebbery - Fundamentals of Computer Security,
Springer Ferlag, 2003
•
N. Koblitz - Wykład z teorii liczb i kryptografii, WNT, Warszawa, 1995
•
J. Gawinecki, J. Szmidt - Zastosowanie ciał sko
ń
czonych i krzywych
eliptycznych w kryptografii, WAT, Warszawa, 1999
•
J. Szmidt, M. Misztal - Wst
ę
p do kryptologii, WSISiZ, Warszawa, 2001
•
RSA Laboratories - Frequently Asked Questions about Today’s
Cryptography, Ver. 4.1, 2000
•
K. Liderman - Podr
ę
cznik administratora bezpiecze
ń
stwa
teleinformatycznego, MIKOM, Warszawa, 2003
•
PN-ISO/IEC 17799 - Technika informatyczna. Praktyczne zasady
zarz
ą
dzania bezpiecze
ń
stwem informacji, PKN, 2003
•
Normy z serii ISO 27000 - dot. systemów zarz
ą
dzania bezpiecze
ń
stwem
informacji
•
ITSEC – Information Technology Evaluation Criteria, Document COM(90)
314, v. 1.2. Commission of the European Communities, 1991
•
CC – Common Criteria, ISO/IEC 15408, 2005
r.wicik@wil.waw.pl
Notes, 3/59
2.a. Wprowadzenie – systemy teleinformatyczne
Informacja – obiekt abstrakcyjny, który po zakodowaniu w postać danych moŜe
być przechowywany, przesyłany, przetwarzany
Informacje wraŜliwe – informacje, które mogą być wykorzystane przeciwko
interesom danego podmiotu poprzez ich ujawnienie,
zmodyfikowanie, brak dostępu
Informacje niejawne – informacje stanowiące tajemnicę państwową i słuŜbową
(wg Ustawy o ochronie informacji niejawnych)
Dane osobowe – dane osobowe wg Ustawy o ochronie danych osobowych
System teleinformatyczny – system słuŜący do wytwarzania, przechowywania,
przetwarzania i przesyłania informacji
Systemy teleinformatyczne:
1.
Sieci informatyczne
•
stanowiska komputerowe
•
sieci wymiany danych (lokalne i rozległe)
2.
Indywidualne kanały telekomunikacyjne
•
transmisja danych (w ramach sieci komputerowych, pomiędzy
terminalami abonenckimi)
•
łączność telefoniczna (analogowa i cyfrowa)
•
łączność telefaksowa
3.
Grupowe trakty telekomunikacyjne
•
międzycentralowe (między łącznicami)
•
międzywęzłowe (między węzłami pakietowymi)
r.wicik@wil.waw.pl
Notes, 4/59
2.b. Wprowadzenie – bezpieczeństwo teleinformatyczne
Bezpieczeństwo teleinformatyczne – poziom uzasadnionego zaufania, Ŝe nie
zostaną poniesione potencjalne straty wynikłe z niepoŜądanego ujawnienia,
modyfikacji lub braku dostępu do informacji przechowywanej lub przesyłanej
za pomocą systemów teleinformatycznych. (K. Liderman)
Podstawowe atrybuty bezpieczeństwa informacji
•
poufność (tajność) – poziom ochrony jakiej ma podlegać informacja (np.
poprzez określenie klauzul tajności dla informacji klasyfikowanych:
ZastrzeŜone, Poufne, Tajne, Ściśle Tajne), zapewnienie dostępu do
informacji tylko osobom upowaŜnionym
•
integralność – zdolność do stwierdzenia, Ŝe informacja jest poprawna, nie
podlegała nieuprawnionej modyfikacji
•
dostępność – zapewnienie, Ŝe podmioty upowaŜnione mają dostęp do
informacji, kiedy to jest potrzebne
r.wicik@wil.waw.pl
Notes, 5/59
2.c. Wprowadzenie - zagroŜenia
ZagroŜenia w sieciach informatycznych
1.
Podsłuch
•
zdobycie informacji przechowywanych na stanowisku komputerowym
•
zdobycie informacji przesyłanych w sieci
•
poznanie protokołów wymiany danych i protokołów kryptograficznych
2.
Nieuprawniony dostęp do zasobów sieci
3.
Nieuprawnione działania legalnego uŜytkownika
4.
Wirusy, konie trojańskie
•
nieuprawnione aplikacje działające destrukcyjnie na system
•
nieuprawnione aplikacje wspomagające penetrację systemu
5.
Maskarada
•
fałszywe źródła i ujścia informacji
6.
Generowanie sztucznego ruchu
•
uniemoŜliwianie lub utrudnianie dostępu do zasobów
7.
Powtórzenia
•
powtórne nadanie podsłuchanej wcześniej informacji w celu uzyskania
uprawnień lub wprowadzenia w błąd odbiorcy
8.
Ataki na integralność
•
danych
•
systemów informatycznych
9.
Zaprzeczenie
•
nadania informacji
•
odbioru informacji
•
treści informacji
r.wicik@wil.waw.pl
Notes, 6/59
2.d. Wprowadzenie - zagroŜenia
ZagroŜenia w kanałach indywidualnych
1.
Podsłuch
•
zdobycie informacji przesyłanych w kanałach indywidualnych
•
poznanie protokołów transmisyjnych i kryptograficznych umoŜliwiających
wykonanie ataku aktywnego na kanał lub sieć łączności
2.
Modyfikacja lub opóźnianie przesyłanych informacji
•
dezorganizowanie pracy uŜytkowników sieci łączności
3.
Powtórzenia
•
wprowadzanie w błąd odbiorcy poprzez nadanie podsłuchanej wcześniej
informacji
4.
Nieuprawnione działania legalnego uŜytkownika
5.
Dostęp do terminala nieuprawnionego uŜytkownika
ZagroŜenia w traktach grupowych
1.
Podsłuch
•
zdobycie informacji przesyłanych w kanałach indywidualnych
•
zdobycie informacji sygnalizacji i zarządzania umoŜliwiające wykonanie
ataku aktywnego na system łączności
2.
Analiza potoku ruchu
•
lokalizacja waŜnych stanowisk i obiektów
3.
Modyfikacja lub opóźnianie przesyłanych informacji oraz maskarada
•
zakłócanie pracy systemu łączności
•
fałszywe źródła i ujścia informacji
r.wicik@wil.waw.pl
Notes, 7/59
2.e. Wprowadzenie - ochrona
Ochrona informacji
•
przed ujawnieniem
•
przed nieautoryzowaną modyfikacją lub zniszczeniem
•
zapewnienie dostępu
Środki bezpieczeństwa
1.
Prawne
•
ustawy
•
kodeks karny
2.
Administracyjno-organizacyjne
•
osoby odpowiedzialne za bezpieczeństwo
•
normy, przepisy i regulaminy postępowania
•
uprawnienia
•
szkolenia
3.
Fizyczne
•
kraty, zamki, strefy bezpieczeństwa
•
sejfy
•
kabiny ekranujące
•
systemy alarmowe i ppoŜ.
4.
Techniczne
•
ochrona dostępu (hasła, uprawnienia)
•
ochrona przed złośliwy oprogramowaniem (antywirusowa)
•
k r y p t o g r a f i c z n e m e t o d y o c h r o n y i n f o r m a c j i
r.wicik@wil.waw.pl
Notes, 8/59
2.f. Wprowadzenie – historia kryptografii
Kryptografia
Kryptoanaliza
klasyczne
szyfry ręczne
szyfry
maszynowe
elektroniczne
(programowe i
sprzętowe)
implementacje
szyfrów
1919
1926
1949
1976
1977
1978
1994
1995
2000
szyfr Cezara
szyfry podstawieniowe,
przestawieniowe,
polialfabetyczne,
wędrującego klucza
maszyny rotorowe
Enigma
szyfr Vernama z
kluczem jednorazowym
Shannon –
Communication Theory
of Secrecy Systems
Diffie, Hellman – New
Directions in
Cryptography
DES – Data Encryption
Standard
RSA – szyfr z kluczem
publicznym
DSS – Digital Signature
Standard
Utah Digital Signature
Law
AES – Advanced
Encryption Standard
1854
1863
1890
1933
1945
1982
1990
1993
2000
złamanie szyfru
polialfabetycznego
(Vigenere’a)
złamanie szyfru
wędrującego klucza
złamanie szyfru Enigmy
złamanie szyfru
purpurowego
złamanie szyfru
plecakowego
kryptoanaliza róŜnicowa
kryptoanaliza liniowa
faktoryzacja 512-
bitowej liczby
modularnej RSA
r.wicik@wil.waw.pl
Notes, 9/59
2.g. Wprowadzenie – szyfry historyczne
Szyfr Cezara
Szyfr przesuwający z kluczem 3.
Szyfrowanie: c= E(p) = (p+3) mod n.
Deszyfrowanie: p= D(p) = (c-3) mod n
Gdzie n - ilość liter w alfabecie, dla łaciny początkowo 21 liter, obecnie 26.
A B C D E F G H I K L M N O P Q R S T V X
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Tekst otwarty: ALEA IACTA EST (ko
ś
ci zostały rzucone)
Kryptogram mod 21: DOHD MDFAD HXA
Kryptogram mod 26: DOHD LDFWD HVW
Szyfr Rot13
Rot13 działa jak szyfr Cezara na alfabecie łacińskim modulo 26 z kluczem 13.
Szyfrowanie i deszyfrowanie to ta sam funkcja: p=Rot13[c=Rot13(p)]
Tekst otwarty: Komu bije dzwon
Tekst po zakodowaniu rot13: Xbzh ovwr qmjba
Szyfr Rot47
Rot47 działa jak szyfr Cezara na znakach o kodach od 33 do 126 z tablicy kodów
ASCII modulo 94 z kluczem 47.
Szyfrowanie i deszyfrowanie to ta sam funkcja: p=Rot47[c=Rot47(p)]
Tekst otwarty: Komu bije dzwon
Tekst po zakodowaniu rot47: z@>F 3:;6 5KH@?
r.wicik@wil.waw.pl
Notes, 10/59
2.h. Wprowadzenie – szyfry historyczne
Szyfr polialfabetyczny (Vigenere’a)
Szyfr podstawieniowy z ustalanym kluczem lub autokluczem. Kolejne znaki były
sumowane ze znakami klucza mod długość alfabetu. Odpowiada szyfrowaniu
kolejnych znaków szyfrem cezara o róŜnych przesunięciach dla kolejnych
znaków. Do szyfrowania pomocna jest tablica permutacji alfabetu. Litery
kryptogramu są znajdowane na przecięciu kolumny i wiersza wyznaczonych
przez litery tekstu otwartego i klucza. Wyznaczanie klucza odwrotnego do
deszyfrowania: K
*
i
= [26 – K
i
] mod 26. Autoklucz tworzony jest z tekstu jawnego
poprzez dodanie litery na początku.
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
B C D E F G H I J K L M N O P Q R S T U V W X Y Z A
C D E F G H I J K L M N O P Q R S T U V W X Y Z A B
D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
E F G H I J K L M N O P Q R S T U V W X Y Z A B C D
F G H I J K L M N O P Q R S T U V W X Y Z A B C D E
G H I J K L M N O P Q R S T U V W X Y Z A B C D E F
H I J K L M N O P Q R S T U V W X Y Z A B C D E F G
I J K L M N O P Q R S T U V W X Y Z A B C D E F G H
J K L M N O P Q R S T U V W X Y Z A B C D E F G H I
K L M N O P Q R S T U V W X Y Z A B C D E F G H I J
L M N O P Q R S T U V W X Y Z A B C D E F G H I J K
M N O P Q R S T U V W X Y Z A B C D E F G H I J K L
N O P Q R S T U V W X Y Z A B C D E F G H I J K L M
O P Q R S T U V W X Y Z A B C D E F G H I J K L M N
P Q R S T U V W X Y Z A B C D E F G H I J K L M N O
Q 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
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 Q
S T U V W X Y Z A B C D E F G H I J K L M N O P Q R
T U V W X Y Z A B C D E F G H I J K L M N O P Q R S
U V W X Y Z A B C D E F G H I J K L M N O P Q R S T
V W X Y Z A B C D E F G H I J K L M N O P Q R S T U
W X Y Z A B C D E F G H I J K L M N O P Q R S T U V
X Y Z A B C D E F G H I J K L M N O P Q R S T U V W
Y Z A B C D E F G H I J K L M N O P Q R S T U V W X
Z A B C D E F G H I J K L M N O P Q R S T U V W X Y
Tekst otwarty: Komu bije dzwon
Klucz: kluc zklu czklu
Kryptogram: Uzgw asuy fygzh
r.wicik@wil.waw.pl
Notes, 11/59
2.i. Wprowadzenie – szyfrowanie
Enigma
Niemiecka maszyna szyfrująca będąca w sprzętową
implementacją szyfru polialfabetycznego o róŜnych
permutacjach tekstu dla kolejnych szyfrowanych liter,
co pozwalało zatrzeć w kryptogramach statystyki
tekstu jawnego. Wykorzystywana od lat 20 XX w.
Wynalazcą był Hugo Koch, który sprzedał patent
Arturowi Scherbiusowi. Enigmę w 1932 r. złamali
Polacy: M. Rejewski, J. RóŜycki i H. Zygalski. Dzięki
temu wiele tajnych niemieckich tekstów było znane
Aliantom w czasie II wojny światowej. Na bazie
Enigmy budowano maszyny szyfrujące do lat 70.
Szyfry produktowe, podstawieniowo-przestawieniowe
Szyfry zbudowane z prostych operacji przestawieniowych i podstawieniowych
realizujących mieszanie informacji odkrytej z kluczem w celu uzyskania
kryptogramu i zatarcia statystyk tekstu otwartego (np. DES, AES). Podwaliny
podane przez Shannona i stosowane do czasów współczesnych w szyfrach
blokowych.
Szyfry z kluczem publicznym
Szyfry zbudowane w oparciu o funkcje jednokierunkowe, gdzie obliczeniowo
trudno jest odtworzyć klucz tajny na podstawie klucza publicznego (np. RSA,
DH, DSA). Na tej podstawie budowane są współczesne szyfry z kluczem
publicznym, podpisy cyfrowe oraz schematy uzgadniania klucza.
r.wicik@wil.waw.pl
Notes, 12/59
3.a Podstawowe pojęcia kryptograficznej ochrony informacji
Kryptologia – nauka obejmująca kryptografię i kryptoanalizę
Kryptografia – dziedzina wiedzy i badań zajmująca się metodami utajnionego
zapisywania wiadomości
Kryptoanaliza - dziedzina wiedzy i badań zajmująca się metodami łamania
szyfrów
Szyfrowanie – proces tworzenia tekstu zaszyfrowanego (kryptogramu) z tekstu
źródłowego (wiadomości jawnych, odkrytych) odbywający się
według algorytmu szyfrowania (szyfru)
System kryptograficzny
•
zbiór kluczy K
oraz dla kaŜdego k
∈
∈
∈
∈
K
•
zbiór wiadomości jawnych M
k
•
zbiór wiadomości zaszyfrowanych C
k
•
funkcja szyfrująca E
k
: M
k
C
k
•
funkcja deszyfrująca D
k
: C
k
M
k
taka,
Ŝe D
k
(E
k
(m))=m dla kaŜdego m
∈
∈
∈
∈
M
k
r.wicik@wil.waw.pl
Notes, 13/59
4.a Rodzaje systemów kryptograficznych
Systemy z kluczem prywatnym
•
systemy symetryczne
prywatne (tajne) klucze słuŜą do szyfrowania i deszyfrowania
informacji
•
klucz musi być dystrybuowany kanałem chronionym
•
klucz musi być chroniony w czasie uŜytkowania
•
stosowane są szyfry blokowe i strumieniowe
c=E
k
(m)
szyfrowanie
m=D
k
(c)
deszyfrowanie
m
m
c
kanał odkryty
źródło kluczy
k
k
k
kanał chroniony
r.wicik@wil.waw.pl
Notes, 14/59
4.b Rodzaje systemów kryptograficznych
Systemy z kluczem publicznym
•
systemy asymetryczne
do szyfrowania informacji słuŜy klucz publiczny (jawny)
do deszyfrowania informacji słuŜy klucz prywatny (tajny)
•
klucz publiczny nie jest chroniony w czasie dystrybucji i uŜytkowania
•
klucz prywatny jest generowany w miejscu uŜytkowania (lub
dystrybuowany kanałem chronionym)
•
klucz prywatny wymaga ochrony w czasie uŜytkowania
•
stosowane są szyfry asymetryczne oparte o problemy trudne obliczeniowo
(trudno jest znaleźć klucz prywatny d na podstawie publicznego e –
funkcja jednokierunkowa e=f
j
(d) )
c=E
e
(m)
szyfrowanie
m=D
d
(c)
deszyfrowanie
m
m
c
kanał odkryty
źródło kluczy
e=f
j
(d)
d
e
kanał odkryty
r.wicik@wil.waw.pl
Notes, 15/59
4.c Rodzaje systemów kryptograficznych
System bezwarunkowo bezpieczny
•
entropia wiadomości szyfrowanych H(M)
≤≤≤≤
H(K) entropii kluczy
•
praktycznie występuje w systemie szyfrowym z kluczami – ciągami
losowymi jednokrotnego wykorzystania (szyfr Vernama, „one-time pad”)
System warunkowo (obliczeniowo) bezpieczny
•
entropia wiadomości szyfrowanych H(M) > H(K) entropii kluczy
•
występuje w systemach utajniania informacji opartych o szyfry blokowe,
strumieniowe lub asymetryczne – z kluczami o ustalonej długości
•
bezpieczeństwo szyfrów warunkowo bezpiecznych określa się poprzez
złoŜoność obliczeniową najlepszego ataku na szyfr w stosunku do
potencjalnych moŜliwości obliczeniowych kryptoanalityka w czasie
waŜności utajnianej informacji
•
szyfr uznaje się za warunkowo bezpieczny, gdy najlepsze ataki na szyfr
posiadają złoŜoność obliczeniową zbliŜoną do złoŜoności ataków
brutalnych, a ataki brutalne są praktycznie nie moŜliwe do
przeprowadzenia
ZłoŜoność ataków brutalnych (dla szyfrów blokowych)
•
czasowa złoŜoność obliczeniowa ataku w celu znalezienia klucza – średnio
2
|k|-1
operacji, gdzie |k| – długość klucza (bezpiecznie gdy |k| > 100 bitów)
•
pamięciowa złoŜoność obliczeniowa ataku w celu zdefiniowania
przekształcenia szyfrowego dla danego klucza – 2
|d|
par bloków danych
tekstów jawnych i odpowiadających im kryptogramów, gdzie |d| - długość
szyfrowanego bloku danych (bezpiecznie, gdy |d| > 100 bitów)
r.wicik@wil.waw.pl
Notes, 16/59
5. Usługi kryptograficznej ochrony informacji
1.
Poufność – zabezpieczenie przed ujawnieniem treści informacji
2.
Integralność – umoŜliwia weryfikację poprawności informacji
3.
Uwierzytelnienie – umoŜliwia weryfikację autentyczności (poprawności,
pochodzenia, toŜsamości)
•
informacji
•
podmiotów (nadawców, odbiorców, uŜytkowników)
•
kluczy
4.
Niezaprzeczalność – uwierzytelnienie oparte o podpis cyfrowy
•
nadawcy informacji
•
treści informacji
•
odbiorcy informacji
5.
Generacja, zarządzanie, dystrybucja i uzgadnianie kluczy
•
w systemach symetrycznych
•
w systemach asymetrycznych
6.
Certyfikacja – uwierzytelnienie przez zaufany urząd
•
kluczy
•
podmiotów
•
aplikacji
r.wicik@wil.waw.pl
Notes, 17/59
6. Techniki kryptograficznej ochrony informacji
1.
Szyfry
•
szyfry symetryczne (blokowe, strumieniowe)
•
szyfry asymetryczne (z kluczem publicznym)
2.
Funkcje skrótu
•
funkcje skrótu
•
szyfrowane sumy kontrolne
3.
Funkcje, kody i protokoły uwierzytelniające
•
danych (funkcja skrótu z kluczem, szyfrowanie z sumą kontrolną)
•
podmiotów (hasła dostępu i funkcje skrótu, protokoły uwierzytelniające,
podpis cyfrowy, zaufana trzecia strona)
•
kluczy (certyfikaty kluczy, zaufane urzędy)
4.
Podpis cyfrowy
•
treści i nadawcy (podpis cyfrowy skrótu informacji)
•
odbiorcy (podpis cyfrowy, zaufana trzecia strona)
5.
Techniki i protokoły generacji, zarządzania, dystrybucji i uzgadniania kluczy
•
dla systemów symetrycznych
•
dla systemów z kluczem publicznym
r.wicik@wil.waw.pl
Notes, 18/59
7.a. Szyfry blokowe
Szyfr blokowy – jest to schemat szyfrowania, w którym jedno wykonanie
algorytmu szyfrowania powoduje zaszyfrowanie fragmentu tekstu jawnego o
ustalonej długości zwanego blokiem
Blok tekstu jawnego
Blok kryptogramu
Algorytm
szyfrowania
Klucz
Podstawowe parametry
1.
Długość bloku: 64, 128 bitów (8, 16 znaków)
2.
Długość klucza (pierwotnego): 40
÷÷÷÷
256 bitów (5
÷÷÷÷
32 znaki)
r.wicik@wil.waw.pl
Notes, 19/59
7.b. Szyfry blokowe
Typy konstrukcji
1.
Szyfr produktowy – mocny szyfr zbudowany z prostych operacji (np.
podstawiania i przestawiania bitów informacji) zapewniających mieszanie
(tekstu jawnego z kluczem) i rozpraszanie (tekstu jawnego w celu zatarcia
jego statystyk w kryptogramie)
2.
Podstawieniowo-przestawieniowy – zbudowany z kolejnych warstw
podstawieniowych realizowanych przez S-boksy (skrzynki podstawieniowe) i
przestawieniowych realizowanych przez permutacje (przestawiania bitów)
3.
Iteracyjne – na bloku tekstu jawnego wykonywane są kolejno po sobie
identyczne rundy działające w oparciu o róŜne podklucze wytworzone z
klucza pierwotnego
4.
Typu Feistel – szyfr iteracyjny z rundą działającą na połówkach (ćwiartkach)
szyfrowanego bloku; identyczny algorytm szyfrowania i deszyfrowania
(odwrotnie są podawane podklucze)
r.wicik@wil.waw.pl
Notes, 20/59
7.c. Szyfry blokowe – struktura podstawieniowo-przestawieniowa
S
11
S
12
S
13
S
21
S
22
S
23
S
31
S
32
S
33
Blok informacji jawnej
Blok informacji zaszyfrowanej
←
←
←
←
warstwa podstawieniowa: S-boksy
←
←
←
←
warstwa podstawieniowa: S-boksy
←
←
←
←
warstwa podstawieniowa: S-boksy
←
←
←
←
warstwa przestawieniowa: permutacja
←
←
←
←
warstwa przestawieniowa: permutacja
UzaleŜnianie struktury od klucza
•
mieszanie klucza z informacją między warstwami przestawieniową i
podstawieniową
•
wybór S-boksów przez klucz
r.wicik@wil.waw.pl
Notes, 21/59
7.d. Szyfry blokowe – struktura typu Feistel
R
0
f
L
0
Blok informacji jawnej
k
1
f
k
2
k
r
Blok informacji zaszyfrowanej
runda 1
kolejne rundy
R
1
L
1
L
r-1
R
r-1
f
R
r
L
r
runda r
Runda rozszerzonej struktury typu Feistel
C
i-1
C
i
f
D
i-1
k
i
D
i
B
i
A
i
B
i-1
A
i-1
r.wicik@wil.waw.pl
Notes, 22/59
7.e. Szyfry blokowe – tryby pracy
1. ECB (Electronic Code Book) – elektroniczna ksiąŜka kodowa
P
1
P
2
C
1
C
2
E
k
E
k
Bloki tekstu jawnego ->
Bloki kryptogramów ->
Szyfrowanie ->
P
3
C
3
E
k
C
1
C
2
P
1
P
2
D
k
D
k
Bloki tekstu jawnego ->
Bloki kryptogramów ->
Deszyfrowanie ->
C
3
P
3
D
k
Własności
•
dostęp do pojedynczych bloków (przydatne w bazach danych)
•
moŜliwość zmian pojedynczych bloków kryptogramów (takŜe przez
przeciwnika)
•
nie powiela błędów na kolejne bloki
r.wicik@wil.waw.pl
Notes, 23/59
7.f. Szyfry blokowe – tryby pracy
2. CBC (Cipher Block Chaining) – łańcuchowanie bloków zaszyfrowanych
IV
P
1
C
0
C
1
E
k
E
k
Bloki tekstu jawnego ->
Bloki kryptogramów ->
Szyfrowanie ->
P
2
C
2
E
k
C
0
C
1
IV
P
1
D
k
D
k
Bloki tekstu jawnego ->
Bloki kryptogramów ->
Deszyfrowanie ->
C
2
P
2
D
k
Własności
•
randomizer powodujący ulosowienie kryptogramów
•
utrudniona zmiana pojedynczych bloków kryptogramów
•
błąd w tekście jawnym powielany na wszystkie kolejne bloki
•
błąd w kryptogramie powielany na jeden następny blok
r.wicik@wil.waw.pl
Notes, 24/59
7.g. Szyfry blokowe – tryby pracy
3. CFB (Cipher Feedback Mode) – sprzęŜenie zwrotne kryptogramów
IV
O
E
k
r
r
n
n
IV
O
E
k
r
r
n
n
r
r
P
P
C
Szyfrowanie
Deszyfrowanie
Własności
•
szyfrowanie w trybie strumieniowym – w jednostkach mniejszych niŜ
blok, np. znak, bit
•
szyfrowanie i deszyfrowanie wg algorytmu szyfrowania
•
szyfr samosynchronizujący się
•
błąd w tekście jawnym powielany na resztę kryptogramu
•
błąd w kryptogramie powielany do wysunięcia rejestru
r.wicik@wil.waw.pl
Notes, 25/59
7.h. Szyfry blokowe – tryby pracy
4. OFB (Output Feedback Mode) – sprzęŜenie zwrotne bloków wyjściowych
IV
O
E
k
n
r
n
n
IV
O
E
k
n
r
n
n
r
r
P
P
C
Szyfrowanie
Deszyfrowanie
Własności
•
szyfrowanie w trybie strumieniowym – w jednostkach mniejszych niŜ
blok, np. znak, bit
•
szyfrowanie i deszyfrowanie wg algorytmu szyfrowania
•
szyfr wymaga synchronizacji
•
błędy nie powielają się
•
rejestr IV moŜe być licznikiem (moŜliwość deszyfrowania pojedynczych
znaków)
r.wicik@wil.waw.pl
Notes, 26/59
7.i. Szyfry blokowe
Najgroźniejsze ataki kryptoanalityczne
1.
Kryptoanaliza liniowa (93r.)
•
polega na znajdowaniu liniowych aproksymacji szyfru – efektywnych,
zbliŜonych do liniowych zaleŜności między:
bitami klucza
bitami tekstu jawnego
bitami kryptogramu
•
wysoce efektywne aproksymacje szyfru oraz odpowiednia ilość par
tekstów jawnych i kryptogramów pozwala odtworzyć bity klucza
•
ochrona poprzez:
wysoce nieliniowe elementy szyfru
długi blok szyfrowany i długi klucz
2.
Kryptoanaliza róŜnicowa (90r.)
•
polega na znajdowaniu wysoce prawdopodobnych charakterystyk
róŜnicowych szyfru – zaleŜności między róŜnicami zachodzącymi między:
bitami tekstu jawnego
bitami kryptogramu
•
wysoce prawdopodobne charakterystyki róŜnicowe szyfru, odpowiednie
profile róŜnicowe nieliniowych elementów oraz odpowiednia ilość par
tekstów jawnych i kryptogramów pozwala odtworzyć bity klucza
•
ochrona poprzez:
wysoce nieliniowe elementy szyfru o dobrym profilu róŜnicowym
długi blok szyfrowany i długi klucz
r.wicik@wil.waw.pl
Notes, 27/59
8.a. Funkcje skrótu i techniki uwierzytelniania
Własności funkcji skrótu
1.
Funkcja oblicza
•
na podstawie wiadomości m dowolnej długości
•
skrót h=H(m) określonej długości (128, 160, 256 … 512 bitów)
2.
Funkcja jednokierunkowa
•
łatwo jest obliczyć skrót h na podstawie wiadomości m
•
trudno jest obliczyć wiadomość m na podstawie skrótu h
3.
Funkcja bez kolizji
•
mając wiadomość m trudno jest znaleźć inną wiadomość m’ taką, Ŝe
H(m)=H(m’)
m
i
IV
h
H
Blok wiadomo
ś
ci ->
Skrót ->
<- Skracanie
Warto
ść
inicjuj
ą
ca ->
Zastosowanie funkcji skrótu
1.
Do weryfikacji integralności danych
2.
Do weryfikacji haseł dostępu
3.
Do budowy kodów uwierzytelniających
4.
W schematach podpisu cyfrowego
r.wicik@wil.waw.pl
Notes, 28/59
8.b. Funkcje skrótu i techniki uwierzytelniania
Obliczanie skrótu
•
wiadomość jest dzielona na bloki o długości odpowiedniej dla danej
funkcji skrótu (256, 512 bitów)
•
ostatni fragment wiadomości jest dopełniany do pełnego bloku
•
kolejne pośrednie skróty h
i
są podawane jako wartości IV w następnych
etapach skracania
•
skrót z ostatniego etapu skracania jest skrótem za całą wiadomość
m
1
IV
h
H
Bloki wiadomo
ś
ci ->
Skrót ->
Skracanie ->
m
2
m
n
|| d
H
H
h
1
h
2
Weryfikacja integralności
1.
nadawca wiadomości oblicza dla niej skrót h
2.
skrót h jest wysyłany do odbiorcy razem z wiadomością
3.
odbiorca oblicza skrót h’ dla odebranej wiadomości
4.
odbiorca sprawdza, czy h = h’ – jeśli tak - integralność wiadomości nie
została naruszona
r.wicik@wil.waw.pl
Notes, 29/59
8.c. Funkcje skrótu i techniki uwierzytelniania
Schemat uwierzytelniania (bez poufności wiadomości)
•
nadawca wiadomości oblicza dla wiadomości m znacznik
uwierzytelniający t z wykorzystaniem klucza e
•
wiadomość jest wysyłana do odbiorcy ze znacznikiem uwierzytelniającym
•
odbiorca wiadomości oblicza dla wiadomości m znacznik
uwierzytelniający t’ z wykorzystaniem klucza e
•
odbiorca weryfikuje autentyczność (nadawcy, wiadomości) porównując
znaczniki uwierzytelniające: odebrany t i obliczony t’
obliczanie znacznika
uwierzytelniającego
t=A
e
(m)
m
m
m, t
kanał odkryty
źródło
kluczy
e
kanał chroniony
obliczanie znacznika
uwierzytelniającego
t’=A
e
(m)
weryfikacja czy t=t’
jeŜeli t=t’
Sposoby realizacji kodów uwierzytelniających
•
szyfrowanie wiadomości z dołączoną jej sumą kontrolną lub skrótem
•
funkcja skrótu z kluczem – klucz podawany jako wartość inicjująca IV
lub jako pierwszy skracany blok
•
kody uwierzytelniające (MAC) na bazie funkcji skrótu
r.wicik@wil.waw.pl
Notes, 30/59
8.d. Funkcje skrótu i techniki uwierzytelniania
Uwierzytelnienie z wykorzystaniem funkcji skrótu z kluczem
•
funkcja skrótu z kluczem jako wartość inicjująca
m
1
k
t
H
Bloki wiadomo
ś
ci ->
Znacznik uwierzytelniaj
ą
cy ->
Skracanie ->
m
2
m
n
|| d
H
H
h
1
h
2
•
funkcja skrótu z kluczem jako pierwszy blok wiadomości
k
IV
t
H
Bloki wiadomo
ś
ci ->
Znacznik uwierzytelniaj
ą
cy ->
Skracanie ->
m
1
m
n
|| d
H
H
h
1
h
2
r.wicik@wil.waw.pl
Notes, 31/59
8.e. Funkcje skrótu i techniki uwierzytelniania
Kody uwierzytelniające na bazie funkcji skrótu
1.
NMAC (Nested Message Authentication Code)
•
opiera się na funkcji skrótu z podwójnym kluczem zastępującym wartości
inicjujące IV
•
uŜyta funkcja skrótu wymaga modyfikacji (IV)
m
1
k
1
t
H
Bloki wiadomo
ś
ci ->
Obliczenie znacznika ->
Skracanie ->
m
2
m
n
|| d
H
H
h
1
h
2
k
2
H
h
n
Znacznik uwierzytelniaj
ą
cy ->
r.wicik@wil.waw.pl
Notes, 32/59
8.f. Funkcje skrótu i techniki uwierzytelniania
Kody uwierzytelniające na bazie funkcji skrótu
2.
HMAC (Hash based Message Authentication Code)
•
opiera się na funkcji skrótu z podwójnym kluczem dołączanym na
początek wiadomości
•
nie wymaga modyfikacji uŜytej funkcji skrótu
k
1
IV
t
H
Bloki wiadomo
ś
ci ->
Obliczenie znacznika ->
Skracanie ->
m
1
m
n
|| d
H
H
h
1
h
2
k
2
H
h
n
Znacznik uwierzytelniaj
ą
cy ->
H
IV
h
1
’
r.wicik@wil.waw.pl
Notes, 33/59
8.g. Funkcje skrótu i techniki uwierzytelniania
Podstawowe ataki na funkcje skrótu
1.
Atak metodą dnia urodzin
•
atak ma na celu znalezienie kolizji – dwóch róŜnych wiadomości, dla
których funkcja daje te same skróty
•
wykorzystuje fakt, Ŝe wystarcza juŜ 23 osoby, aby prawdopodobieństwo
tego, Ŝe dwie z nich mają ten sam dzień urodzin było wyŜsze niŜ 0.5
•
złoŜoność obliczeniowa ataku
≈≈≈≈
2
n/2
, gdzie n długość bloku skrótu
•
ochrona:
długi blok skrótu – powyŜej 128 bitów
2.
Atak ze spotkaniem w środku
•
atak ma na celu znalezienie fałszywej wiadomości, dla danego skrótu
•
polega na dopasowywaniu wiadomości tak, aby prowadząc skracanie od
początku i końca, w środku uzyskać identyczne skróty pośrednie
•
złoŜoność obliczeniowa ataku
≈≈≈≈
2
n/2
, gdzie n długość bloku skrótu
•
ochrona:
długi blok skrótu – powyŜej 128 bitów
stosowanie nieodwracalnych przekształceń do skracania
r.wicik@wil.waw.pl
Notes, 34/59
9.a. Szyfry strumieniowe
Szyfr strumieniowy – rodzaj algorytmu szyfrowania, który w danej chwili
utajnia pojedynczy znak lub bit, wykorzystując przekształcenie szyfrujące
zmieniające się w czasie
Własności szyfrów strumieniowych
•
utajnianie informacji w postaci sekwencji pojedynczych znaków lub bitów
•
nie powielają błędów (synchroniczne)
•
wymagają synchronizacji (synchroniczne) warunków początkowych pracy
i chwili startu
•
wymagają resynchronizacji w przypadku poślizgów (zgubienia lub
dodania znaków lub bitów w sekwencji kryptogramów)
•
przewaŜnie łatwe i szybkie w implementacjach sprzętowych, trudne i
wolniejsze w implementacjach programowych
•
nie są odporne na ataki aktywne w postaci wtrąceń, powieleń lub usunięć
znaków lub bitów kryptogramów (resynchronizacja powodująca przerwy
w łączności)
•
nie są odporne na ataki aktywne w postaci zmian w kryptogramach
(wymagane są dodatkowe mechanizmy zapewniające integralność i
uwierzytelnienie)
r.wicik@wil.waw.pl
Notes, 35/59
9.b. Szyfry strumieniowe
Przykładowa realizacja szyfru strumieniowego
•
szyfrowanie (deszyfrowanie) odbywa się przez sumowanie sekwencji
znaków lub bitów informacji otwartej m
i
(zaszyfrowanej c
i
) z sekwencją
znaków lub bitów sekwencji szyfrującej z
i
pochodzącej z generatora
•
generator sekwencji szyfrującej zbudowany w oparciu o rejestry liniowe ze
sprzęŜeniem zwrotnym lub z wykorzystaniem szyfru blokowego
pracującego w trybie OFB (Output Feedback Mode)
•
generatory wymagają synchronizacji w celu wypracowania identycznych
kluczy sesji (warunków początkowych pracy generatorów) i chwili startu
generatorów
Klucz
Warunki Pocz
ą
tkowe
Sekwencja informacji
otwartej
Sekwencja informacji
zaszyfrowanej
Generator
Sekwencji
Szyfrującej
z
i
m
i
c
i
Generator
Sekwencji
Szyfrującej
z
i
Sekwencja informacji
otwartej
m
i
Klucz
Warunki Pocz
ą
tkowe
Dane do synchronizacji
generatorów
r.wicik@wil.waw.pl
Notes, 36/59
9.c. Szyfry strumieniowe
Rejestr liniowy ze sprzęŜeniem zwrotnym (ang. LFSR – Linear Feedback Shift
Register) – rejestr przesuwny (sekwencja D komórek stanu), który w danej
chwili czasu (takcie zegara):
•
oddaje zawartość komórki stanu nr 1 jako element sekwencji wyjściowej
•
przesuwa zawartości kolejnych komórek stanu do komórek o numerze o 1
niŜszym
•
wyznacza nową zawartość komórki stanu nr D jako sumę (funkcja
liniowa) zawartości wybranych komórek z poprzedniego stanu
•
wybór komórek poprzedniego stanu odbywa się na podstawie zawartości
komórek rejestru sprzęŜeń
x
0
=1
s
+
s
1
s
2
r
D-1
s
D-1
r
2
s
D
r
1
x
D-1
x
2
x
1
x
D
r
D
r
0
z
i
Rejestr
sprz
ęŜ
e
ń
->
Rejestr
stanu ->
Sekwencja
wyj
ś
ciowa ->
Takty zegara
•
r
D
x
D
+ r
D-1
x
D-1
+ . . . + r
2
x
2
+ r
1
x
1
+ 1 – wielomian sprzęŜeń rejestru
•
[s
D
, s
D-1
, . . . , s
2
, s
1
] – stan początkowy rejestru (przynajmniej jedna
wartość s
i
∈
∈
∈
∈
[1..D]
powinna być róŜna od zera)
•
s
+
= (r
D
s
1
+ r
D-1
s
2
+ . . . + r
2
s
D-1
+ r
1
s
D
) mod 2 – wartość sprzęŜenia
r.wicik@wil.waw.pl
Notes, 37/59
9.d. Szyfry strumieniowe
Własności generatorów sekwencji szyfrującej opartych o rejestry liniowe ze
sprzęŜeniem zwrotnym
•
okres sekwencji wyjściowej – ilość róŜnych stanów wyjściowych z generatora
(następne stany będą powtórzeniami juŜ występujących wcześniej)
w przypadku pojedynczego rejestru o długości D z nie redukowalnym
(maksymalnym, pierwotnym) wielomianem sprzęŜeń – okres wynosi 2
D
-1,
w przypadku pojedynczego rejestru o długości D z redukowalnym
wielomianem sprzęŜeń – okres wynosi 2
N
-1, gdzie N jest długością
wielomianu dzielącego wielomian o długości D
w przypadku generatorów zbudowanych z wielu rejestrów – wynikowy
okres jest funkcją okresów poszczególnych rejestrów (np. iloczyn)
•
złoŜoność liniowa sekwencji wyjściowej – długość najkrótszego rejestru, który
generuje tą sekwencję
w przypadku pojedynczego rejestru o długości D – złoŜoność liniowa
wynosi D
w przypadku generatorów zbudowanych z wielu rejestrów oraz
ewentualnie z nieliniowej funkcji łączącej – wynikowa złoŜoność liniowa
jest funkcją złoŜoności poszczególnych rejestrów i rzędu nieliniowości
funkcji łączącej
•
własności statystyczne sekwencji wyjściowej
w przypadku poprawnie zbudowanych generatorów – bardzo dobre
r.wicik@wil.waw.pl
Notes, 38/59
9.e. Szyfry strumieniowe – przykłady generatorów
Generatory z nieliniową funkcją filtrującą
•
funkcja filtrująca łączy wiele wyjść z jednego rejestru
L F S R
sekwencja szyfruj
ą
ca
z
i
nieliniowa funkcja filtrująca
Generatory z nieliniową funkcją kombinacyjną
•
funkcja kombinacyjna łączy wyjścia z wielu rejestrów
L F S R A
sekwencja szyfruj
ą
ca
z
i
L F S R B
L F S R N
•
•
•
nieliniowa
funkcja
kombinacyjna
a
i
b
i
n
i
Cel stosowania nieliniowych funkcji łączących
•
podniesienie złoŜoności liniowej generatora
•
podniesienie
odporności
generatora
na
ataki
kryptoanalityczne
(skierowane przeciw rejestrom)
r.wicik@wil.waw.pl
Notes, 39/59
9.f. Szyfry strumieniowe – przykłady generatorów
Generatory z nieliniową funkcją kombinacyjną
1.
Generator Geffe
•
długości rejestrów A, B i C – parami względnie pierwsze
•
funkcja kombinacyjna – f(a
i
, b
i
, c
i
) = a
i
⋅⋅⋅⋅
b
i
+ c
i
⋅⋅⋅⋅
b
i
•
okres = (2
A
-1)
⋅⋅⋅⋅
(2
B
-1)
⋅⋅⋅⋅
(2
C
-1)
złoŜoność liniowa = AC + CB + B
L F S R A
sekwencja szyfruj
ą
ca
z
i
L F S R B
L F S R C
a
i
b
i
c
i
f
2.
Generator sumacyjny
•
długości rejestrów A, B ... N – parami względnie pierwsze
•
funkcja kombinacyjna – suma z bitem pamięci w postaci przeniesienia
•
okres = (2
A
-1)
⋅⋅⋅⋅
(2
B
-1)
⋅⋅⋅⋅
...
⋅⋅⋅⋅
(2
N
-1) złoŜoność liniowa
≈≈≈≈
(2
A
-1)
⋅⋅⋅⋅
(2
B
-1)
⋅⋅⋅⋅
...
⋅⋅⋅⋅
(2
N
-1)
L F S R A
sekwencja szyfruj
ą
ca
z
i
L F S R B
L F S R N
•
•
•
ΣΣΣΣ
a
i
b
i
n
i
przeniesienie
r.wicik@wil.waw.pl
Notes, 40/59
9.g. Szyfry strumieniowe – przykłady generatorów
Generatory z kontrolowanym taktowaniem
1.
Generator Günthera
•
długości rejestrów B, C – względnie pierwsze, A daje sekwencję de
Bruijna o okresie 2
A
•
okres = 2
A
⋅⋅⋅⋅
(2
B
-1)
⋅⋅⋅⋅
(2
C
-1)
złoŜoność liniowa > (B+C)
⋅⋅⋅⋅
(2
A
-1)
L F S R A
sekwencja szyfruj
ą
ca
z
i
L F S R B
L F S R C
a
i
b
i
c
i
takty
zegara
2.
Generator skrócony
•
długości rejestrów A i B – względnie pierwsze
•
okres – 2
A-1
⋅⋅⋅⋅
(2
B
-1)
złoŜoność liniowa > B
⋅⋅⋅⋅
2
A-2
sekwencja szyfruj
ą
ca
z
i
L F S R A
L F S R B
a
i
b
i
takty
zegara
a
i
= 1 -> oddaj b
i
a
i
= 0 -> odrzu
ć
b
i
r.wicik@wil.waw.pl
Notes, 41/59
9.h. Szyfry strumieniowe – GSM A5
Szyfr strumieniowy A5 – jest uŜywany do utajniania informacji przesyłanej
drogą radiową pomiędzy telefonami komórkowymi a stacjami bazowymi.
Generator sekwencji szyfrującej algorytmu A5:
•
3 rejestry liniowe z pierwotnymi wielomianami sprzęŜeń (LFSR) o
długościach 19, 22 i 23,
•
wszystkie rejestry taktowane nierównomiernie za pośrednictwem funkcji
parametryzowanej przez sekwencje ze wszystkich rejestrów,
•
wyjściem generatora jest suma XOR wyjść z poszczególnych rejestrów.
L F S R B
sekwencja szyfruj
ą
ca
L F S R A
L F S R C
clock
control
Klucze
•
klucz sesji algorytmu A5: 64 bity + 22 bity numeru ramki,
•
klucz sesji jest wytwarzany z wykorzystaniem algorytmu A8, na którego
wejście podawany 128-bitowy klucz master i 128-bitowa liczba losowa,
•
uwierzytelnienie uŜytkownika realizowane jest z wykorzystaniem
algorytmu A3.
r.wicik@wil.waw.pl
Notes, 42/59
9.i. Szyfry strumieniowe
Podstawowe ataki kryptoanalityczne na generatory zbudowane z rejestrów
1.
Algorytm Berlekampa-Masseya
•
wyznacza złoŜoność liniową sekwencji binarnej
•
jeśli sekwencja jest dwa razy dłuŜsza od złoŜoności – wyznacza unikalny
rejestr (wielomian sprzęŜeń), który wygenerował tą sekwencję
•
ochrona:
nie podawać wyjść z rejestrów wprost na wyjście generatora
2.
Ataki korelacyjne (Siegenthaler, Meier-Staffelbach)
•
odtwarzają wypełnienie początkowe rejestrów w generatorach z
nieliniową funkcją kombinacyjną
•
wykorzystują korelacje pomiędzy wejściami a wyjściem funkcji łączącej
czyli pomiędzy sekwencją wyjściową z generatora a sekwencjami
wyjściowymi z rejestrów
•
ochrona:
dobór funkcji łączących o wysokim rządzie odporności korelacyjnej
stosowanie funkcji łączących z pamięcią
unikanie rzadkich wielomianów sprzęŜeń rejestrów
zmienianie wielomianów sprzęŜeń rejestrów (jako klucze relacji)
zmienianie wypełnień początkowych rejestrów (jako klucze sesji)
r.wicik@wil.waw.pl
Notes, 43/59
10.a. Szyfry z kluczem publicznym
Szyfr z kluczem publicznym – jest to asymetryczny, dwukluczowy szyfr o
własnościach:
•
klucz publiczny (jawny) słuŜy do szyfrowania
•
klucz prywatny (tajny) do deszyfrowania informacji
•
obliczeniowo jest niemoŜliwe (trudne):
odzyskanie klucza prywatnego z klucza publicznego lub z innych
elementów algorytmu szyfrowania
odzyskanie informacji jawnej z kryptogramu bez znajomości klucza
prywatnego
Szyfry z kluczem publicznym opierają się na zapadkowych funkcjach
jednokierunkowych
Zapadkowa funkcja jednokierunkowa – jest to funkcja o własnościach:
•
obliczeniowo łatwo jest znaleźć wartość tej funkcji na podstawie argumentów
•
obliczeniowo niemoŜliwe (trudne) jest znalezienie wartości funkcji odwrotnej
bez znajomości tajnego klucza
Funkcje jednokierunkowe – Problemy trudne obliczeniowo
•
mnoŜenie liczb całkowitych – rozkład na czynniki pierwsze
•
funkcja potęgowa – pierwiastkowanie dyskretne (modularne)
•
funkcja wykładnicza – logarytmowanie dyskretne (modularne)
•
sumowanie podzbioru liczb – znajdowanie podzbioru liczb tworzących sumę
w problemie plecakowym
r.wicik@wil.waw.pl
Notes, 44/59
10.b Szyfr asymetryczny z kluczami prywatnymi
Szyfr wykładniczy (Pohlinga-Hellmana)
•
szyfrowanie:
c = m
e
mod p
•
deszyfrowanie:
m = c
d
mod p
•
liczba modularna:
p – liczba pierwsza
wtedy dla kaŜdego m<p
NWD(m, p) = 1
i wiadomości dają się poprawnie deszyfrować
•
klucz szyfrujący:
[e, p]
•
klucz deszyfrujący:
[d, p]
e
⋅⋅⋅⋅
d mod
ϕϕϕϕ
(p) = 1
ϕϕϕϕ
(p) = p-1
klucz szyfrujący nie nadaje się do opublikowania, gdyŜ łatwo jest znaleźć d
na podstawie e – d = e
-1
( mod
ϕϕϕϕ
(p) )
bezpieczeństwo szyfru (klucza e dla ataku ze znanym tekstem jawnym)
opiera się trudności obliczenia logarytmu dyskretnego e = log
m
c (mod p)
r.wicik@wil.waw.pl
Notes, 45/59
10.c. Szyfry z kluczem publicznym
Szyfr RSA (Rivest Shamir Adleman)
•
szyfrowanie:
c = m
e
mod n
•
deszyfrowanie:
m = c
d
mod n
•
liczba modularna:
n = p
⋅⋅⋅⋅
q – iloczyn liczb pierwszych
•
klucz szyfrujący:
[e, n]
NWD(e, s)=1
s =
ϕϕϕϕ
(n) = (p-1)
⋅⋅⋅⋅
(q-1)
•
klucz deszyfrujący:
[d, n]
e
⋅⋅⋅⋅
d
≡≡≡≡
1 (mod s)
e = d
-1
(mod s)
klucz szyfrujący nadaje się do opublikowania, gdyŜ trudno jest znaleźć d na
podstawie e – brak
ϕϕϕϕ
(n)
bezpieczeństwo szyfru (wiadomości m) opiera się na trudności obliczenia
pierwiastka
e
√√√√
c (mod n) – złoŜoność zbliŜona do złoŜoności rozkładu n na
czynniki pierwsze p i q
bezpieczeństwo szyfru (klucza d) opiera się na trudności obliczenia rozkładu
liczby n na czynniki pierwsze p i q – złoŜoność zbliŜona do złoŜoności
obliczania logarytmu dyskretnego
zalecana długość liczby n – powyŜej 512 bitów (1024 bity i więcej)
Szyfr plecakowy (Merklego-Hellmana, Rivesta-Chora)
•
szyfrowanie:
c =
ΣΣΣΣ
i=1..n
(k
i
m
i
)
•
deszyfrowanie:
algorytm znajdowania m
i
mając [c, a
i
, a
i
-> k
i
]
•
klucz szyfrujący:
liczby k
i
powstałe w wyniku przekształcenia a
i
•
klucz deszyfrujący:
liczby a
i
i funkcja przekształcająca a
i
-> k
i
klucz k
i
nadaje się do opublikowania w wyniku zachowania w tajemnicy
funkcji a
i
-> k
i
bezpieczeństwo szyfru (wiadomości m
i
) opiera(ło) się na trudności znalezienia
podzbioru liczb k
i
tworzących sumę c
r.wicik@wil.waw.pl
Notes, 46/59
10.d. Szyfry z kluczem publicznym
Szyfr Rabina
•
szyfrowanie:
c = m
2
mod n
•
deszyfrowanie:
algorytm znajdowania
2
√√√√
c (mod n) mając dane p i q
•
klucz szyfrujący:
n = p
⋅⋅⋅⋅
q – iloczyn liczb pierwszych
•
klucz deszyfrujący: [p, q]
klucz szyfrujący nadaje się do opublikowania, gdyŜ trudno jest znaleźć p i q
na podstawie n
bezpieczeństwo szyfru (wiadomości m) opiera się na trudności obliczenia
pierwiastka
2
√√√√
c (mod n) bez znajomości p i q
bezpieczeństwo szyfru (klucza [p, q]) opiera się na trudności obliczenia
rozkładu liczby n na czynniki pierwsze p i q
Szyfr ElGamala
•
szyfrowanie:
wylosuj 0 < k < (p-1)
c = (
γγγγ
,
δδδδ
)
γγγγ
=
αααα
k
mod p
δδδδ
= m
⋅⋅⋅⋅
(
αααα
a
)
k
mod p
•
deszyfrowanie:
m = (
γγγγ
-a
)
⋅⋅⋅⋅δδδδ
mod p
•
klucz szyfrujący:
[p,
αααα
,
αααα
a
] p – liczba pierwsza,
αααα
- generator grupy Z
p
*
•
klucz deszyfrujący: a
klucz szyfrujący nadaje się do opublikowania, gdyŜ trudno jest znaleźć a na
podstawie
αααα
a
bezpieczeństwo szyfru (wiadomości m) opiera się trudności rozwiązania
problemu ekwiwalentnego do problemu Diffie-Hellmana (znalezienia
αααα
ak
mając dane:
αααα
, p,
αααα
a
,
αααα
k
wszystko mod p)
bezpieczeństwo szyfru (klucza a) opiera się na trudności obliczania
logarytmu dyskretnego a = log
α
αα
α
(
αααα
a
) (mod p)
r.wicik@wil.waw.pl
Notes, 47/59
11.a. Podpisy cyfrowe
Podpis cyfrowy – znacznik uwierzytelniający dołączany do wiadomości o
następujących własnościach:
•
zaleŜny od tajnego klucza znanego tylko podpisującemu
•
zaleŜny od podpisywanej wiadomości
•
trudny do podrobienia bez znajomości tajnego klucza
•
weryfikowalny z wykorzystaniem jawnego klucza
m’=E
e
(s)
weryfikacja
s=D
d
(m)
podpisywanie
OK jeśli
m = m’
m, s
kanał odkryty
źródło
kluczy
d
e=f
j
(d)
kanał odkryty
m
Wykorzystanie podpisu cyfrowego
•
integralność i uwierzytelnienie
•
niezaprzeczalność
•
certyfikacja kluczy
r.wicik@wil.waw.pl
Notes, 48/59
11.b. Podpisy cyfrowe
Podpis bazujący na RSA
•
podpisywanie:
µµµµ
= H(m)
s =
µµµµ
d
mod n
•
weryfikacja:
µµµµ
’ = H(m)
µµµµ
” = s
e
mod n
OK, jeśli
µµµµ
’ =
µµµµ
”
•
klucz podpisu:
[d, n]
•
klucz weryfikacji:
[e, n]
DSA (Digital Signature Algorithm)
•
podpisywanie:
µµµµ
= H(m)
wylosuj 0 < k < q
r = (
αααα
k
mod p) mod q
s = k
-1
⋅⋅⋅⋅
(
µµµµ
+ar) mod q
•
weryfikacja:
µµµµ
’ = H(m)
u
1
=
µµµµ
’
⋅⋅⋅⋅
s
-1
mod q
u
2
= r
⋅⋅⋅⋅
s
-1
mod q
v = (
αααα
u1
⋅⋅⋅⋅
y
u2
mod p) mod q
OK jeśli
v = r
•
klucz podpisu:
[p, q,
αααα
, a]
•
klucz weryfikacji:
[p, q,
αααα
, y]
r.wicik@wil.waw.pl
Notes, 49/59
12.a. Protokoły kryptograficzne
Protokół – szereg kroków, obejmujących dwa lub więcej podmiotów,
podejmowanych w celu realizacji określonego zadania
Protokół kryptograficzny – protokół wykonywany z wykorzystaniem technik
kryptograficznych lub na potrzeby tych technik
Własności protokołów
•
protokół powinien być kompletny – po kaŜdym kroku powinny być
zdefiniowane kroki dla wszystkich moŜliwych sytuacji bez moŜliwości
nieporozumień
•
podmioty wykonujące protokół muszą go znać i dokładnie wykonywać
wszystkie kroki
Zastosowanie protokołów kryptograficznych
•
dystrybucja kluczy
•
uzgadnianie kluczy
•
weryfikacja autentyczności
•
usługi niezaprzeczalności
•
sterowanie dostępem
Rodzaje protokołów kryptograficznych
•
oparte o techniki symetryczne
•
oparte o techniki asymetryczne
•
wspomagane przez zaufaną trzecią stronę
r.wicik@wil.waw.pl
Notes, 50/59
12.b. Protokoły kryptograficzne
Protokół uwierzytelnienia i ustalania klucza sesji oparty o szyfr blokowy
Uczestnicy protokołu: podmioty A i B otrzymują:
•
tajny klucz uwierzytelnienia k
1.
A
•
losuje liczbę
µµµµ
A
•
wysyła do B kryptogram c
1
= E
k
(
µµµµ
A
)
2.
B
•
deszyfruje
µµµµ
A
’ = D
k
(c
1
)
•
losuje liczbę
µµµµ
B
•
wysyła do A kryptogram c
2
= E
k
(
µµµµ
A
’,
µµµµ
B
)
3.
A
•
deszyfruje [
µµµµ
A
”,
µµµµ
B
’] = D
k
(c
2
)
•
weryfikuje, czy
µµµµ
A
=
µµµµ
A
” i jeśli tak, to
•
losuje klucz sesji e
•
wysyła do B kryptogram c
3
= E
k
(
µµµµ
B
’,
µµµµ
A
, e)
4.
B
•
deszyfruje [
µµµµ
A
”,
µµµµ
B
”, e’] = D
k
(c
3
)
•
weryfikuje, czy
µµµµ
B
=
µµµµ
B
” i jeśli tak, to
•
zachowuje klucz sesji e’ jako zgodny z e
Bezpieczeństwo protokołu opiera się na tajemnicy klucza i mocy algorytmu
szyfrowania E
k
, D
k
r.wicik@wil.waw.pl
Notes, 51/59
12.c. Protokoły kryptograficzne
Protokół Diffiego-Hellmana – uzgadniania klucza
Uczestnicy protokołu: podmioty A i B ustalają jawnie:
•
dwie liczby całkowite n i g, n – liczba pierwsza, g < n
1.
A
•
losuje liczbę x
•
oblicza X = g
x
mod n
•
wysyła do B liczbę X
2.
B
•
losuje liczbę y
•
oblicza Y = g
y
mod n
•
wysyła do A liczbę Y
3.
A
•
oblicza k = Y
x
mod n
4.
B
•
oblicza k
’
= X
y
mod n
Bezpieczeństwo protokołu opiera się na trudności obliczeniowej logarytmów
dyskretnych x = log
g
X (mod n) i y = log
g
Y (mod n) niezbędnych do
znalezienia k = g
xy
mod n
r.wicik@wil.waw.pl
Notes, 52/59
13.a. Krzywe Eliptyczne
Krzywe eliptyczne – systemy kryptograficzne z kluczem publicznym oparte na
problemie logarytmu dyskretnego na krzywych eliptycznych (N. Koblitz ‘85r. i
V. Miller ‘87r.), np.:
•
schemat podpisu ECDSA,
•
protokół kryptograficzny ECDH.
Krzywa eliptyczna nad ciałem GF(p) - zbiór par (x,y) elementów tego ciała
(punktów) oraz punkt O (w nieskończoności), spełniających równanie w GF(p):
b
ax
x
y
+
+
=
3
2
,
0
27
4
2
3
≠
+
=
∆
b
a
,
GF(p)
b
a,
∈
.
Krzywa eliptyczna nad ciałem GF(2
n
) - zbiór par (x,y) elementów tego ciała
(punktów) oraz punkt O (w nieskończoności), spełniających równanie w GF(2
n
):
b
ax
x
xy
y
+
+
=
+
2
3
2
,
0
≠
b
,
)
GF(2
b
a,
n
∈
.
Działania w grupie punktów na krzywej: dodawanie punktów, odejmowanie
punktów, mnoŜenie punktu przez liczbę, wyznaczanie punktu przeciwnego do
danego punktu.
Silne kryptograficznie krzywe eliptyczne – krzywa E nad ciałem GF(p
n
)
powinna spełniać podstawowe warunki:
1.
n jest liczbą pierwszą (ewentualnie rozkładalną na dwa czynniki pierwsze);
2.
rząd krzywej (liczba punktów na krzywej) jest #E=kr, gdzie r>2
160
jest liczbą
pierwszą oraz liczby r i p są względnie pierwsze, natomiast k jest małą liczbą
naturalną;
3.
problemu logarytmu dyskretnego na krzywej eliptycznej nie redukuje się do
problemu logarytmu w ciałach skończonych.
r.wicik@wil.waw.pl
Notes, 53/59
13.b. Krzywe Eliptyczne
Podpis ECDSA
•
Klucz prywatny:
o
d – losowa liczba naturalna z przedziału [1..n-1];
•
Klucz publiczny zbiór parametrów (E, P, n, Q), gdzie:
o
E – silna kryptograficznie krzywa eliptyczna,
o
P – punkt na krzywej E rzędu n, tzn. nP=O,
o
Q – punkt na krzywej Q=dP.
Generacja podpisu
•
Wylosuj liczbę naturalną k z przedziału [1...n-1],
•
Oblicz kP=(x
1
,y
1
) oraz r=x
1
mod n, gdzie x
1
jest liczbą całkowitą, r
≠≠≠≠
0,
•
Oblicz k
-1
mod n,
•
Oblicz s=k
-1
(h(M)+dr) mod n, gdzie h() - funkcja skrótu, s
≠≠≠≠
0,
•
Podpisem cyfrowym wiadomości M jest para liczb całkowitych (r,s).
Weryfikacja podpisu
•
Oblicz w=s
-1
mod n oraz wartość funkcji skrótu h(M) wiadomości M.
•
Oblicz u
1
= h(M)w mod n oraz u
2
= rw mod n.
•
Oblicz punkt na krzywej u
1
P + u
2
Q = (x
0
,y
0
) oraz v = x
0
mod n
•
Zaakceptuj podpis wtedy i tylko wtedy, gdy v=r.
r.wicik@wil.waw.pl
Notes, 54/59
14.a. Kryteria bezpieczeństwa dla szyfrów
Wymagania bezpieczeństwa dla algorytmów wg NESSIE
(NESSIE - New European Schemes for Signature, Integrity and Encryption)
1.
Szyfry blokowe
High - długość klucza min. 256 bitów, długość bloku min. 128 bitów
Normal - długość klucza min. 128 bitów, długość bloku min. 128 bitów
Normal-Legacy - długość klucza min. 128 bitów, długość bloku min. 64
bitów
2.
Szyfry strumieniowe
High - długość klucza min. 256 bitów, pamięć wewnętrzna min. 256 bitów
Normal - długość klucza min. 128 bitów, pamięć wewnętrzna min. 128
bitów
3.
Kody uwierzytelniające (MAC)
Powinny dawać kody o max. długości odpowiadającej długości klucza
High - długość klucza min. 256 bitów
Normal - długość klucza min. 128 bitów
4.
Funkcje skrótu odporne na kolizje
High - długość skrótu (wyjścia) min. 512 bitów
Normal - długość skrótu (wyjścia) min. 256 bitów
r.wicik@wil.waw.pl
Notes, 55/59
14.b. Kryteria bezpieczeństwa dla szyfrów
Wymagania bezpieczeństwa dla algorytmów wg NESSIE
(NESSIE - New European Schemes for Signature, Integrity and Encryption)
5.
Jednokierunkowe funkcje skrótu
High - długość skrótu (wyjścia) min. 256 bitów
Normal - długość skrótu (wyjścia) min. 128 bitów
6.
Asymetryczne schematy szyfrowania
Minimalna złoŜoność obliczeniowa ataku rzędu 2
80
szyfrowań 3DES
7.
Asymetryczne schematy podpisu cyfrowego
Minimalna złoŜoność obliczeniowa ataku rzędu 2
80
szyfrowań 3DES
8.
Asymetryczne schematy identyfikacji
Minimalna złoŜoność obliczeniowa ataku rzędu 2
80
szyfrowań 3DES
Prawdopodobieństwo podszycia się powinno być niŜsze niŜ 2
-32
r.wicik@wil.waw.pl
Notes, 56/59
14.c. Kryteria bezpieczeństwa dla szyfrów
Wybór systemu kryptograficznej ochrony informacji jest zaleŜny od takich
parametrów, jak:
1.
Okres waŜności informacji
Przewidywany czas, przez który informacja powinna być skutecznie
chroniona przed atakami
2.
Margines bezpieczeństwa
Akceptowalny poziom pewności, Ŝe ataki będą niewykonalne w czasie
waŜności informacji, co w głównej mierze zaleŜy od:
o
toŜsamości atakującego
o
złoŜoności obliczeniowej ataku
o
moŜliwości finansowych atakującego
3.
ZłoŜoność kryptoanalizy
Efektywność ataków w czasie waŜności informacji - najlepszy atak na
system powinien co najmniej tak złoŜony, jak ataki brutalne (pełny
przegląd, atak metodą dnia urodzin, itp.)
Odporność na ataki powinna być oceniana w środowisku, w którym
będzie uŜywany system
System kryptograficzny powinien zapewniać bezpieczeństwo
przez czas waŜności chronionej informacji
z Ŝądanym przez uŜytkownika marginesem bezpieczeństwa
przy przewidywanych moŜliwościach finansowych i obliczeniowych
atakującego
przy przewidywanych złoŜonościach ataków w zadanym środowisku
Ź
ródło: Price Water House Coopers CCE Quarterly Journal – Issue 1 2000
r.wicik@wil.waw.pl
Notes, 57/59
14.d. Kryteria bezpieczeństwa dla szyfrów
Ź
ródło: Price Water House Coopers CCE Quarterly Journal – Issue 1 2000
Arjen Lenstra, Eric Verheul - Selecting Cryptographic Key Sizes, PKC’2000
r.wicik@wil.waw.pl
Notes, 58/59
14.e. Kryteria bezpieczeństwa dla szyfrów
Zalecane długości kluczy – szyfry symetryczne
Wysoki poziom bezpieczeństwa na 20-30 lat – 112-128 bitów
Dla długoterminowego zabezpieczania – 256 bitów
Zalecane długości kluczy – szyfry asymetryczne
Dane publikowane przez ECRYPT
r.wicik@wil.waw.pl
Notes, 59/59
14.f. Kryteria bezpieczeństwa dla szyfrów
Zalecane do uŜytku długości kluczy – szyfry asymetryczne
Zalecane przez ECRYPT długo
ś
ci kluczy do u
Ŝ
ytku
Zalecenia NIST - dla bezpiecze
ń
stwa informacji ponad 10lat – 112/2048 bitów
Zalecenia NESSIE - dla bezpiecze
ń
stwa informacji ponad 5-10lat – 80/1536 bitów
Zalecenia RSA Labs.