[e-mail]

Notes, 1/59

Kryptologia i kryptograficzna ochrona informacji

Istota kryptograficznej ochrony informacji

w systemach teleinformatycznych

dr in

ż

. Robert Wicik

Wojskowy Instytut Ł

ą

czno

ś

ci

[e-mail]

[e-mail]

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

[e-mail]

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

[e-mail]

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)

[e-mail]

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

[e-mail]

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

[e-mail]

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

[e-mail]

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

[e-mail]

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

[e-mail]

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@?

[e-mail]

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

[e-mail]

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.

[e-mail]

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

[e-mail]

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

[e-mail]

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

[e-mail]

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)

[e-mail]

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

[e-mail]

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

[e-mail]

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)

[e-mail]

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)

[e-mail]

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

[e-mail]

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

[e-mail]

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

[e-mail]

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

[e-mail]

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

[e-mail]

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)

[e-mail]

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

[e-mail]

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

[e-mail]

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

[e-mail]

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

[e-mail]

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

[e-mail]

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 ->

[e-mail]

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

’

[e-mail]

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

[e-mail]

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)

[e-mail]

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

[e-mail]

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

[e-mail]

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

[e-mail]

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)

[e-mail]

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

[e-mail]

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

[e-mail]

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.

[e-mail]

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)

[e-mail]

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

[e-mail]

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)

[e-mail]

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

[e-mail]

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)

[e-mail]

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

[e-mail]

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]

[e-mail]

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ę

[e-mail]

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

[e-mail]

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

[e-mail]

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.

[e-mail]

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.

[e-mail]

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

[e-mail]

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

[e-mail]

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

[e-mail]

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

[e-mail]

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

[e-mail]

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.