Podstawy kryptografii

Plan wykładu

• Wstęp
• Rodzaje systemów kryptograficznych
• Historia kryptografii
• Szyfrowanie symetryczne
• Algorytm AES
• Szyfrowanie asymetryczne
• Algorytm RSA
• Algorytmy haszujące
• Algorytm MD5
• Podsumowanie

Plan wykładu

• Wstęp

• Rodzaje systemów kryptograficznych
• Historia kryptografii
• Szyfrowanie symetryczne
• Algorytm AES
• Szyfrowanie asymetryczne
• Algorytm RSA
• Algorytmy haszujące
• Algorytm MD5
• Podsumowanie

Wstęp

• Podstawowym sposobem zabezpieczania

informacji przesyłanych w sieci komputerowej jest

kryptografia

• Kryptografia zajmuje się zapisywaniem tekstu w

sposób utajniony. Szyfrowanie to zamiana tekstu

jawnego na kryptogram. Deszyfrowaniem

nazywamy operację odwrotną

• Kryptoanaliza zajmuje się zagadnieniami

związanymi z łamaniem szyfru, czyli próbą

znalezienia klucza szyfru lub odczytaniu tekstu

jawnego na podstawie kryptogramu, bez

znajomości klucza

• Systemy kryptograficzne opisują sposób

realizacji usług w sieci teleinformatycznej przy

użyciu technik kryptograficznych

Motywacja rozwoju

kryptografii

• Wzrost potrzeb związanych z bezpieczeństwem z

powodu rozwoju sieci komputerowych

• Potrzeba realizacji elektronicznych transakcji,

operacji finansowych z zapewnieniem
uwierzytelnienia, podpisu cyfrowego,
niezaprzeczalności, itd.

• Trudna realizacja podanych usług

bezpieczeństwa bez stosowania technik
kryptograficznych

Plan wykładu

• Wstęp

• Rodzaje systemów kryptograficznych

• Historia kryptografii
• Szyfrowanie symetryczne
• Algorytm AES
• Szyfrowanie asymetryczne
• Algorytm RSA
• Algorytmy haszujące
• Algorytm MD5
• Podsumowanie

Rodzaje systemów

kryptograficznych

Według metody przekształcenia tekstu jawnego w

tekst zaszyfrowany:

• Podstawienie zakłada, że każdy element tekstu

jawnego (bit, znak, litera) jest odwzorowywany na
inny element

• Transpozycja zakłada przestawienie kolejności

elementów tekstu jawnego. Podstawowy wymogi
to brak straty informacji i odwracalność każdej
operacji. Większość systemów, zwanych
systemami produktowymi (ang. product systems)
przewiduje wiele etapów podstawiania i
transponowania

Rodzaje systemów

kryptograficznych

Według liczby używanych kluczy:
• Szyfrowanie z jednym kluczem

(konwencjonalne, symetryczne, z tajnym
kluczem), np. AES, DES

• Szyfrowanie z dwoma kluczami (asymetryczne,

z kluczem jawnym), np. RSA

Rodzaje systemów

kryptograficznych

Według sposobu przetwarzania tekstu jawnego:
• Szyfr blokowy przetwarza po kolei każdy blok

tekstu wejściowego, produkując jeden blok
wyjściowy na każdy blok wejściowy

• Szyfr strumieniowy przetwarza elementy

wejściowe w sposób ciągły, produkując
jednocześnie materiał wyjściowy

Bezpieczeństwo systemów

kryptograficznych

• Schemat szyfrujący jest bezwarunkowo

bezpieczny, jeżeli generowany tekst
zaszyfrowany nie zawiera wystarczająco dużo
informacji, by jednoznacznie określić
odpowiadający mu tekst jawny, niezależnie od
ilości dostępnego tekstu zaszyfrowanego

• Schemat szyfrujący jest obliczeniowo

bezpieczny, jeżeli koszt złamania szyfru
przewyższa wartość informacji zaszyfrowanej
oraz/lub czas potrzebny do złamania szyfru
przekracza użyteczny „czas życia” informacji

Plan wykładu

• Wstęp
• Rodzaje systemów kryptograficznych

• Historia kryptografii

• Szyfrowanie symetryczne
• Algorytm AES
• Szyfrowanie asymetryczne
• Algorytm RSA
• Algorytmy haszujące
• Algorytm MD5
• Podsumowanie

Historia (1)

• W VII w p.n.e w Grecji stosowano do szyfrowania

scytale

• Tekst pisany był na nawiniętym na patyk pasku

skórzanym

• Po rozwinięciu tekst widoczny na pasku był

trudny do odszyfrowania

• Odszyfrowanie wymaga ponownego

nawinięcia na patyk

• Na przykład tekst „Proszę o pomoc”

Pros

zęop

omoc

• Po odczytaniu na pasku wygląda „pzoręmooospc”

Historia (2)

• Szyfr Cezara polegający na przesunięciu liter

tekstu o 3 używany przez Juliusz Cezara do
komunikacji z wojskami

• Dzięki stosowaniu tego szyfru Juliusz Cezar podbił

całą Galię z wyjątkiem pewnej małej wioski ;-)

Historia (3)

• Polacy w czasie wojny polsko-bolszewickiej (1919-

1920) potrafili odszyfrować depesze wroga, co
ułatwiało działania wojenne (więcej na
serwisy.gazeta.pl/df/1,34467,2856516.html)

Historia (4)

• Enigma – maszyna szyfrująca

używana przez wojska
niemieckie od lat 20 XX wieku
do czasów drugiej wojny
światowej. W 1932 roku
Enigma została złamana przez
polskich matematyków: Marian
Rejewski, Jerzy Różycki i
Henryk Zygalski)

Plan wykładu

• Wstęp
• Rodzaje systemów kryptograficznych
• Historia kryptografii

• Szyfrowanie symetryczne

• Algorytm AES
• Szyfrowanie asymetryczne
• Algorytm RSA
• Algorytmy haszujące
• Algorytm MD5
• Podsumowanie

Uproszczony model

szyfrowania konwencjonalnego

Ź r ó d ł o

k o m u n i k a t u

A l g o r y t m

s z y f r u j ą c y

T e k s t j a w n y

T e k s t j a w n y

A l g o r y t m

d e s z y f r u j ą c y

K a n a ł i n f o r m a c y j n y

T e k s t z a s z y f r o w a n y

W s p ó l n y k l u c z

M i e j s c e

p r z e z n a c z e n i a

A

B

Model szyfrowania

konwencjonalnego

• Szyfrator tworzy tekst zaszyfrowany Y=E

K

(X)

• Odbiorca posiadający klucz może odwrócić

przekształcenie X=D

K

(Y)

• Przeciwnik śledzący Y, ale pozbawiony dostępu do X

i K, próbuje odgadnąć hipotetyczny tekst jawny X` i

hipotetyczny klucz K`. Zakładamy, że zna on

algorytm szyfrujący E i deszyfrujący D

Ź r ó d ł o

k o m u n i k a t u

S z y f r a t o r

Ź r ó d ł o

k l u c z a

B e z p i e c z n y k a n a ł

D e s z y f r a t o r

M i e j s c e

p r z e z n a c z e n i a

K r y p t o a n a l i t y k

X `

K `

X

Y

X

K

Techniki szyfrowania

• Steganografia służy do ukrycia faktu istnienia

komunikatu, np. zaznaczanie liter, atrament

sympatyczny

• Techniki podstawiania polega na zastępowaniu

elementów (bitów) tekstu jawnego innymi

elementami (bitami)

• Techniki transpozycyjne polegają na

permutacji liter (przestawieniu) tekstu jawnego

Steganografia (1)

• Herodot w "Dziejach" opisuje następujący tajny

przekaz informacji

• Despota Hiastus przetrzymywany przez króla

perskiego Dariusza postanawia przesłać
informację do swego zięcia Arystogorasa z
Miletu, tak aby mogła się ona przedostać mimo
pilnujących go strażników

• Aby tego dokonać na wygolonej głowie swego

niewolnika tatuuje przesłanie

• Kiedy niewolnikowi odrosły włosy posyła go z

oficjalnym, mało istotnym listem

Steganografia (2)

• Stosowanie

atramentu
sympatycznego

• Nakłuwanie szpilką

liter tekstu (książki)

• Sformułowanie

komunikatu, aby
sekwencja kolejnych
liter, sylab bądź
wyrazów tworzyła
ukrytą wiadomość

Steganografia w informatyce

• W komputerowym zapisie obrazu (zdjęcie jpg,

film mpg) lub dźwięku (mp3) pewne bity można
zmienić bez wpływu na jakość obrazu (dźwięku)

• Na tych bitach przesyłane są tajne informacje,

które można odczytać wiedząc gdzie zostały
ukryte

Techniki podstawiania

• Technika podstawienia polega na zastępowaniu

elementów (liter, bitów) tekstu jawnego innymi
elementami (b literami, bitami) według
ustalonego schematu

• Przykładowe algorytmy: szyfr Cezara, Szyfr

Playfair, szyfr Vigenere’a

Szyfr Cezara (1)

• Szyfr Cezara polega na zastąpieniu każdej litery

alfabetu literą znajdującą się o trzy pozycje dalej

C=E(p)=(p+3) mod (26)

• C to litera tekstu zaszyfrowanego odpowiadająca

literze tekstu jawnego o indeksie p

• Przesunięcie może mieć wielkość dowolną, więc

ogólna postać algorytmu wygląda następująco:

C=E(p)=(p+k) mod (26), 0<k<26

• Algorytm deszyfrujący ma postać:

p=D(C)=(C-k) mod (26)

Szyfr Cezara (2)

• Przykład dla szyfru Cezara (przesunięcie o 3 znaki)
• Klucz

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

• Szyfrowanie
tekst jawny : szyfr juliusza cezara
tekst zaszyfrowany: VCBIU MXOLXVCD FHCDUD

• Dla szyfru Cezara łatwo można przeprowadzić

kryptoanalizę metodą brutalną polegającą na
wypróbowaniu 25 możliwych kluczy k

Szyfry jednoalfabetowe

• Dla szyfrów jednoalfabetowych możemy

zastosować jako szyfr dowolną permutację 26
znaków alfabetu

• Oznacza to 26!=4*10

26

możliwych kluczy, czyli

można wykluczyć próby rozszyfrowania metodą
brutalną

• Jednak, jeśli kryptoanalityk zna tekst

zaszyfrowany i jego charakter (język tekstu
jawnego), może on wykorzystać regularności
zawarte w języku

Szyfry jednoalfabetowe -

kryptoanaliza

• Dla każdego języka można określić względną

częstość występowania liter (film „Motyl i
skafander”)

• Poniższa tabela prezentuje procentową częstość

względną występowania poszczególnych liter w
tekście angielskim

Techniki transpozycyjne (1)

• Techniki transpozycyjne polegają na permutacji

liter tekstu jawnego

• Najprostszym takim szyfrem jest tzw. technika

płotu, polegająca na tym, że tekst jawny zapisuje

się jako ciąg kolumn, a odczytuje jako ciąg

wierszy

• Na przykład dla płotu o wysokości 2
tekst jawny : szyfrtranspozycyjny
syrrnpzcjy
zftasoyyn
tekst zaszyfrowany: syrrnpzcjyzftasoyyn

Techniki transpozycyjne (2)

• Bardziej skomplikowany system polega na zapisaniu

komunikatu w prostokącie, a następnie odczytanie ze

zmianą kolejności kolumn

Klucz : 3 1 4 2 7 6 5
tekst jawny : b a r d z i e
j s k o m p l
i k o w a n y
s y s t e m p
o l e g a n a
tekst zaszyfrowany:

ASKYLDOWTGBJISORKOSEELYPAIPNMNZMAEA

• Szyfr transpozycyjny można uczynić znaczenie

bezpieczniejszym poprzez stosowanie kilku etapów

transpozycji, co utrudnia znacznie rekonstrukcję

klucza

Konfuzja i dyfuzja

Shannon, twórca teorii informacji przedstawił w

1949 roku dwie główne zasady szyfrowania:

• Konfuzja oznacza rozmycie zależności pomiędzy

tekstami jawnymi a ich zaszyfrowanymi wersjami

• Dyfuzja oznacza rozłożenie zawartych w tekście

jawnym informacji w całym tekście
zaszyfrowanym

Proste szyfry podstawieniowe (szyfr Cezera, szyfr

Vigenere’a) zapewniają tylko konfuzję, gdyż każda
litera jest szyfrowana oddzielnie

Efekt lawinowy

• Efektem lawinowym określamy intensywniejszy

niż dla dyfuzji rozmazanie tekstu jawnego w

tekście zaszyfrowanym

• Jest spotykany dla szyfrowania blokowego
• Każdy bit zaszyfrowanego tekstu zależy od

wszystkich bitów tekstu jawnego w danym bloku

• Dla zmiany pojedynczego bitu tekstu jawnego lub

klucza, każdy bit tekstu zaszyfrowanego powinien

zmienić swoją wartość z prawdopodobieństwem

równym dokładnie 50%

• Kryptoanaliza różnicowa wykorzystuje nawet

niewielkie odstępstwo od tej zasady

Algorytmy produktowe

• Większość współczesnych algorytmów blokowych

to algorytmy produktowe – po kolei
wykonywane są proste, stosunkowo mało
bezpieczne kroki szyfrujące zwane rundami
(iteracjami)

• Dzięki stosowaniu wielu rund bezpieczeństwo

algorytmu znacząco rośnie

Plan wykładu

• Wstęp
• Rodzaje systemów kryptograficznych
• Historia kryptografii
• Szyfrowanie symetryczne

• Algorytm AES

• Szyfrowanie asymetryczne
• Algorytm RSA
• Algorytmy haszujące
• Algorytm MD5
• Podsumowanie

Konkurs AES

• W 1997 roku agencja NIST (ang. National Institute

of Standards and Technology) rozpisała konkurs na
nowy standard szyfrowania, który miał otrzymać
nazwę AES (ang. Advanced Encryption Standard)

• Wybrany algorytm, Rijndael opracowany został

przez naukowców belgijskich dr Joan Daemen oraz
dr Vincent Rijmen

• Rijndael jest blokowym algorytmem szyfrowania z

kluczem symetrycznym pozwalającym na
wykorzystanie klucza szyfrującego o długości 128,
192 i 256 bitów

Dlaczego wygrał Rijndeal

• Znakomita kombinacja gwarantowanego

poziomu bezpieczeństwa, wydajności,
efektywności i łatwości implementacji

• Rijndael charakteryzuje się bardzo dobrą

wydajnością zarówno przy implementacji
sprzętowej, jak i programowej uwzględniającej
różne środowiska i systemy operacyjne

• Testy wykazały, że nie wymaga dużo pamięci

operacyjnej, co sprawia, że można go stosować w
wielu niedostępnych dla innych algorytmów
miejscach

Rijndael w pigułce (1)

• Algorytm blokowy (128, 192 lub 256 bitowe bloki

danych)

• Szyfrowanie jest symetryczne, zatwierdzono klucze

o długościach 128, 192 i 256 bitów

• Proces szyfrowania podlega iteracjom, przy czym

rozróżnia się: rundę wstępną, pewną ilość rund

standardowych (ich ilość zależy od długości klucza i

wynosi odpowiednio 10, 12 lub 14), z których każda

posiada 4 transformacje, rundę końcową

• Został zatwierdzony jako następca algorytmu DES
• Rijndael nie jest chroniony żadnymi zastrzeżeniami

patentowymi, więc nie wymaga opłat licencyjnych

Rijndael w pigułce (2)

• Spełnia 3 główne założenia postawione przez

twórców algorytmu: odporność na wszystkie

znane ataki, szybkość pracy i zwartość kodu na

różnych platformach, łatwość implementacji

• Aktualny stan wiedzy w zakresie kryptoanalizy

nie pozwala na skuteczny atak na wiadomości

szyfrowane tym algorytmem

• Atak brutalny, czyli sprawdzenie wszystkich

możliwych kluczy szyfrujących jest praktycznie

niewykonalny ze względu na długość klucza

• Jest łatwy do implementacji sprzętowej

(większość rodzajów procesorów, smartcard) i

programowej (wiele popularnych języków

programowania)

Szczegóły algorytmu Rijndael

(1)

• Podstawowe pojęcia służące do opisu algorytmu

to "Stan" i "runda"

• Runda (ang. round) to odpowiednik

standardowego etapu obliczeń mającym jako
parametr tzw. Klucz Rundy (ang. Round Key)

• Z reguły runda jest superpozycją, co najmniej 2

bijekcji tzw. podstawienia i permutacji, w
Rijndaelu tych przekształceń jest więcej

Szczegóły algorytmu Rijndael

(2)

• Przekształcenia składające się na każdą rundę

operują na pewnej macierzy prostokątnej

stanowiącej wynik pośredni kolejnych obliczeń

podczas realizacji algorytmu i nazywanej Stanem

(ang. State)

• Jest to macierz o współczynnikach w ciele GF(2

8

)

lub inaczej w zbiorze {0,1}

8

czyli macierz, której

współczynniki to bajty

• Macierz bajtowa Stanu ma 4 wiersze i Nb

kolumn (Nb to długość bloku podzieloną przez 32),

Nb=4, 6 lub 8

• Klucz szyfrujący jest również reprezentowany jako

macierz o 4 wierszach

Szczegóły algorytmu Rijndael

(3)

• Liczbę kolumn tego klucza oznaczamy przez Nk
• Liczba Nk jest równa długości klucza podzielonej przez

32; Nk=4, 6 lub 8

• Długość klucza i bloku, czyli Nk i Nb możemy zmieniać

niezależnie

• Liczba rund Nr stosowana w algorytmie zależy od Nb i

Nk

Nb

Nk

Nr

Nb

Nk

Nr

Nb

Nk

Nr

4

4

10

4

6

12

4

8

14

6

4

12

6

6

12

6

8

14

8

4

14

8

6

14

8

8

14

Ogólny opis algorytmu

R u n d a 1

R u n d a 2

R u n d a 1 0

1 2 8 - b i t o w y t e k s t j a w n y

1 2 8 - b i t o w y t e k s t z a s z y f r o w a n y

K l u c z

r u n d y 1

G e n e r a to r

k l u c z y r u n d

1 2 8 - b i t o w y k l u c z

T e k s t j a w n y w 1 2

T t w w

e n

k j y 1

s a 2

K l u c z

r u n d y 2

K l u c z

r u n d y 1 0

$ * a x

- \ & ^

{ : C g

u S . !

$ * a x - \ & ^ { : C g u S . !

M a c i e r z

S t a n u

B y te S u b

S h i f t R o w

M i x C o l u m n

A d d R o u n d K e y

Opis jednej rundy algorytmu

• Przekształcenie rundy jest bijekcją będąca

superpozycją 4 bijekcji składowych

• Runda składa się z następujących czterech

przekształceń operujących na macierzy Stanu

– przekształcenia ByteSub
– przekształcenia ShiftRow
– przekształcenia MixColumn
– dodawania klucza rundy

• Ostatnia runda nie zawiera przekształcenia

MixColumn

Przekształcenie ByteSub

• Przy transformacji ByteSub operuje się na

poszczególnych elementach macierzy Stanu,
które są pojedynczymi bajtami

• Każdy bajt przechodzi transformację, którą ze

względów historycznych nazwano S-Boxem i jest
wpisywany w to samo miejsce

• W fazie tej wykonuje się jedynie operacje na

bajtach, a zatem jest to łatwe nawet w
procesorach 8-bitowych

S - B o x

b b b b
b b b b
b b b b
b b b b

0 , 0

0 , 1

0 , 2

0 , 3

1 , 0

1 , 1

1 , 2

1 , 3

2 , 0

2 , 1

2 , 2

2 , 3

3 , 0

3 , 1

3 , 2

3 , 3

a

0 , 0

a a a

a a a a
a a a a
a a a a

0 , 1

0 , 2

0 , 3

1 , 0

1 , 1

1 , 2

1 , 3

2 , 0

2 , 1

2 , 2

2 , 3

3 , 0

3 , 1

3 , 2

3 , 3

a

i , j

b

i , j

Przekształcenie ShiftRow

• Ta transformacja przesuwa cyklicznie kolejne

wiersze macierzy o odpowiednią liczbę pozycji

• Wartości przesunięcia zależą od wielkości bloku

i klucza - dla naszych danych pierwszego wiersza

się nie przesuwa, drugi przesuwa się o 1 kolumnę,

trzeci o 2 kolumny, a czwarty o 3 kolumny

• Ponieważ takie przesunięcie sprowadza się

jedynie do zmiany uporządkowania danych w

pamięci, jest ono łatwe w realizacji dla każdego

procesorów.

a b c d

e f g h

i j k l

m n o p

a b c d

f g h e

k l i j

p m n o

b r a k p r z e s u n i ę c i a

p r z e s u n ię c ie o 1 b a j t

p r z e s u n ię c i e o 2 b a j t y

p r z e s u n ię c ie o 3 b a j t y

Przekształcenie MixColumn

• Transformacja MixColumn miesza wartości

zawarte w jednej kolumnie w dość skomplikowany
sposób, zmieniając jednocześnie ich wartości

• Dzięki zastosowaniu specjalnych struktur

algebraicznych taka operacja może zostać
wykonana dość sprawnie na 8-bitowym
procesorze lub wykorzystując pełną moc
procesora 32-bitowego

c x( )

b b b b
b b b b
b b b b
b b b b

0 , 0

0 , 1

0 , 2

0 , 3

1 , 0

1 , 1

1 , 2

1 , 3

2 , 0

2 , 1

2 , 2

2 , 3

3 , 0

3 , 1

3 , 2

3 , 3

a a a a
a a a a
a a a a
a a a a

0 , 0

0 , 1

0 , 2

0 , 3

1 , 0

1 , 1

1 , 2

1 , 3

2 , 0

2 , 1

2 , 2

2 , 3

3 , 0

3 , 1

3 , 2

3 , 3

a

0 , j

a

1 , j

a

2 , j

a

3 , j

b

0 , j

b

1 , j

b

2 , j

b

3 , j

o

Dodawanie klucza rundy

• Dla każdej rundy generowany jest z klucza

pierwotnego specjalny klucz rundy, który zostaje
w tej transformacji połączony z macierzą danych
za pomocą operacji XOR

• Poszczególne komórki (bajty) klucza są

XORowane z odpowiednimi komórkami (bajtami)
macierzy Stanu

Bezpieczeństwo Rijndael (1)

• Operacje MixColumn i ShiftRow zapewniają silną

dyfuzję (zamiana jednego bitu stanu wpływa na

wszystkie bity stanu w małej liczbie rund)

• Operacje ByteSub i dodawanie klucza rundy

zapewniają silną konfuzję (zgubienie zależności –

na podstawie rezultatu jednej rundy nie można

wywnioskować macierzy stanu na początku rundy)

• Aby przeprowadzić kryptoanalizę różnicową, między

poszczególnymi rundami muszą istnieć

przewidywalne różnice. Udowodniono, że

odpowiednie prawdopodobieństwa wykorzystywane

przy kryptoanalizie DES-a w przypadku Rijndaela nie

są wystarczające do przeprowadzenia skutecznego

ataku

Bezpieczeństwo Rijndael (2)

• Udowodniono, że zależności danych pomiędzy

rundami dla Rijndaela są tak małe, iż
kryptoanaliza liniowa jest całkowicie
nieskuteczna

• Istnieją ataki (np. Square, XSL), które są zdolne

do złamania algorytmu Rijndaela ale dla liczby
rund znacznie mniejszej niż określone w
standardzie

Plan wykładu

• Wstęp
• Rodzaje systemów kryptograficznych
• Historia kryptografii
• Szyfrowanie symetryczne
• Algorytm AES

• Szyfrowanie asymetryczne

• Algorytm RSA
• Algorytmy haszujące
• Algorytm MD5
• Podsumowanie

Szyfrowanie asymetryczne

• Algorytmy asymetryczne z kluczem jawnym

opierają się na funkcjach matematycznych, a nie
na podstawianiu i permutacji

• Szyfrowanie jest asymetryczne, wykorzystuje

dwa klucze: publiczny (ogólnie dostępny) i
prywatny

Ź r ó d ł o

k o m u n i k a t u

A l g o r y t m

s z y f r u j ą c y

T e k s t j a w n y

T e k s t j a w n y

A l g o r y t m

d e s z y f r u j ą c y

K a n a ł i n f o r m a c y j n y

T e k s t z a s z y f r o w a n y

M i e j s c e

p r z e z n a c z e n i a

A

B

K l u c z

j a w n y B

K l u c z

p r y w a tn y B

Szyfrowanie asymetryczne -

poufność

B

Ź r ó d ł o

k o m u n i k a t u

S z y f r o w a n i e

Ź r ó d ł o p a r y

k l u c z y

D e s z y f r o w a n i e

M i e j s c e

p r z e z n a c z e n i a

K r y p to a n a l i ty k

X `

K P `

b

X

Y

X

K J

b

K P

b

A

Szyfrowanie asymetryczne -

uwierzytelnienie

B

A

Ź r ó d ł o

k o m u n i k a t u

S z y f r o w a n i e

Ź r ó d ł o p a r y

k l u c z y

D e s z y f r o w a n i e

M i e j s c e

p r z e z n a c z e n i a

K r y p to a n a l i ty k

K P `

a

X

Y

X

K J

a

K P

a

Funkcja jednokierunkowa

• Stworzenie praktycznego systemu szyfrowania

asymetrycznego z kluczem jawnym wymaga
zastosowania funkcji jednokierunkowej z
bocznym wejściem (ang. trapdoor one-way function)

• Funkcja jednokierunkowa to taka, która

przekształca swoją dziedzinę na przedział w taki
sposób, że każda wartość funkcji ma tylko jedną
odwrotność, z tym że obliczenie funkcji jest łatwe
(czas wielomianowy), a obliczenie odwrotności
niewykonalne (wysiłek obliczeniowy rośnie szybciej niż
wielomianowo):

• Y=f(X) - łatwe
• X=f

-1

(Y) - niewykonalne

Funkcja jednokierunkowa z

bocznym wejściem

• Obliczenie funkcji jednokierunkowej z bocznym

wejściem jest łatwe w jednym kierunku, a
niewykonalne w drugim, chyba że są znane
pewne dodatkowe informacje, które umożliwiają
obliczenie odwrotności w czasie wielomianowym

• Y=f

k

(X) - łatwe przy znajomości k i X

• X=f

k-1

(Y) - łatwe przy znajomości k i Y

• X=f

k-1

(Y) - niewykonalne, gdy znamy Y, a nie

znamy k

Kryptoanaliza algorytmów

asymetrycznych

• Atak metodą brutalną (sprawdzenie wszystkich

kombinacji klucza)

• Atak na podstawie klucza jawnego – próba

wyliczenia klucza prywatnego na podstawie
klucza jawnego

• Atak prawdopodobnego komunikatu –

wszystkie możliwe komunikaty są szyfrowane
kluczem jawnym i porównywane z tekstem
zaszyfrowanym

Plan wykładu

• Wstęp
• Rodzaje systemów kryptograficznych
• Historia kryptografii
• Szyfrowanie symetryczne
• Algorytm AES
• Szyfrowanie asymetryczne

• Algorytm RSA

• Algorytmy haszujące
• Algorytm MD5
• Podsumowanie

Algorytm RSA (1)

• Algorytm RSA został opublikowany w 1978 roku

przez Rona Rivesta, Adi Shamira i Lena
Adlemana

• Algorytm RSA to szyfr blokowy, w którym tekst

jawny i tekst zaszyfrowany są liczbami
całkowitymi od 0 do n-1 dla pewnego n

• Tekst jawny jest szyfrowany blokami, z których

każdy ma wartość binarną mniejszą niż n

Algorytm RSA (2)

• Szyfrowanie i deszyfrowanie bloku tekstu jawnego

M i zaszyfrowanego C mają następującą formę:

C = M

e

mod n

M = C

d

mod n =

(M

e

)

d

mod n =

M

ed

mod n

• Zarówno odbiorca i nadawca muszą znać wartość n
• Klucz jawny to KJ={e,n}, a klucz prywatny to

KP={d,n}

• Jak wyznaczyć liczby n, e, d aby M = M

ed

mod n

oraz podany schemat był bezpieczny?

Funkcja Eulera

• Leonhard Euler – szwajcarski

matematyk i fizyk żyjący w XVIII
wieku

• Funkcja Eulera, zapisywana jako



(n) oznacza liczbę dodatnich

liczb całkowitych mniejszych od
n i jednocześnie względnie
pierwszych względem n

• Dla każdej liczby pierwszej p

zachodzi



(p) = p – 1

Twierdzenie Eulera

Teza: Dla każdego a i n względnie pierwszych to n

dzieli bez reszty liczbę (a



(n)

– 1), czyli a



(n)

 1

mod n

• Z twierdzenia Eulera wynika, że dla dwóch liczb

pierwszych p i q i dwóch liczb całkowitych takich,
że n = pq oraz 0<m<n i dowolnej liczby k,
zachodzi następująca zależność

m

k



(n)+1

= m

k(p – 1)(q – 1)+1

 m mod n

RSA i twierdzenie Eulera

• Z twierdzenia Eulera wynika, że m

k



(n)+1

 m mod

n dla n=pq, p i q to liczby pierwsze

• Aby osiągnąć następującą zależność potrzebną w

algorytmie RSA

M = M

ed

mod n

• musimy podstawić ed = k



(n)+1

Generowanie kluczy w RSA

1. Wybierz dwie liczby pierwsze p, q
2. Oblicz n=pxq
3. Wybierz liczbę całkowitą d taką, że

nwd(d,



(n))=1 oraz 1<d<



(n)

4. Oblicz e  d

-1

mod



(n)

5. Klucz jawny KJ={e,n} i klucz prywatny

KP={d,n}

Szyfrowanie i deszyfrowanie

w RSA

Szyfrowanie
• Tekst jawny: M<n
• Tekst zaszyfrowany: C = M

e

mod n

Deszyfrowanie
• Tekst zaszyfrowany: C
• Tekst jawny: M = C

d

mod n

Łamanie RSA

• Metoda brutalna – odpowiednia długość klucza

zapewnia bezpieczeństwo

• Ponieważ znane jest {n,e} to rozkładając n na

czynniki pierwsze p i q można obliczyć



(n) i d.

Odpowiednie duże liczby pierwsze zapewniają
bezpieczeństwo. Dlatego duże liczby pierwsze są
nieustannie poszukiwane i następne chronione

• Określić



(n) bezpośrednio

• Określić d bezpośrednio bez znajomości



(n)

Porównanie RSA i AES

Cecha

AES

RSA

Szybkość

działania

+

–

Bezpieczeństwo

+

+

Zastosowania

Poufność

(szyfrowanie

danych)

Uwierzytelnianie

, dystrybucja

kluczy,

podpis cyfrowy

Plan wykładu

• Wstęp
• Rodzaje systemów kryptograficznych
• Historia kryptografii
• Szyfrowanie symetryczne
• Algorytm AES
• Szyfrowanie asymetryczne
• Algorytm RSA

• Algorytmy haszujące

• Algorytm MD5
• Podsumowanie

Algorytmy haszujące

• Funkcja haszująca z danych M o zmiennym

rozmiarze wylicza pewien wynik H(M) o stałym
rozmiarze, zwany też wyciągiem lub skrótem
komunikatu

• Wynik haszowania jest funkcją wszystkich bitów

komunikatu i zapewnia wykrywanie błędów,
uwierzytelnianie

• Haszowanie jest używane w większości systemów

kryptograficznych stosowanych w sieciach
komputerowych, np. PGP, podpis elektroniczny,
TLS (SSL)

• Przykładowe algorytmy haszujące to MD5, SHA

Wymagania dla funkcji

haszującej

• H można zastosować do dowolnej wielkości bloku

danych

• H tworzy dane wyjściowe o ustalonej długości
• H(x) jest łatwo obliczyć dla każdego x, co ułatwia

implementację sprzętową i programową

• Dla każdego kodu m znalezienie takiego x, że

H(x)=m nie jest wykonywalne na drodze obliczeń

• Dla każdego danego bloku x, znalezienie takiego

y różnego od x, dla którego H(y)=H(x) nie jest
wykonywalne na drodze obliczeń

• Znalezienie pary (x,y), że H(y)=H(x) nie jest

wykonywalne na drodze obliczeń

Kryptoanaliza algorytmów

haszujących

• Podstawowy atak na funkcje haszującą może

polegać na próbie stworzenia komunikatu,
który daje taki sam skrót jak przechwycony
komunikat

• Poza tym można próbować zmodyfikować tekst

w taki sposób, aby skrót się nie zmienił

Plan wykładu

• Wstęp
• Rodzaje systemów kryptograficznych
• Historia kryptografii
• Szyfrowanie symetryczne
• Algorytm AES
• Szyfrowanie asymetryczne
• Algorytm RSA
• Algorytmy haszujące

• Algorytm MD5

• Podsumowanie

Algorytm MD5

• Algorytm MD5 (ang. Message Digest) został stworzony

przez Rona Rivesta i opublikowany jako RFC1321

• Algorytm z wejściowego komunikatu o dowolnej

długości generuje 128-bitowy wyciąg

• Dane wejściowe przetwarzane są w 512 bitowych

blokach

• Przykład działania
• MD5("Ala ma kota") =

91162629d258a876ee994e9233b2ad87

• MD5("Ala ma koty") =

6a645004f620c691731b5a292c25d37f

Generowanie wyciągu w MD5

(1)

• Dodawanie bitów dopełniających
• Dodanie długości komunikatu
• Inicjalizacja 128-bitowego bufora MD
• Przetwarzanie komunikatu w blokach 512-

bitowych

• Otrzymanie wyniku

Generowanie wyciągu w MD5

(2)

K o m u n i k a t

K b i t ó w

L

x 5 1 2 b i t ó w = N x 3 2 b i ty

D o p e ł n i e n i e

( 1 - 5 1 2 ) b i tó w

D ł u g o ś ć

k o m u n i k a t u

( K m o d 2 )

6 4

1 0 0 .. . 0

Y

0

Y

1

5 1 2 b i tó w

5 1 2 b i t ó w

Y

q

5 1 2 b i t ó w

Y

L - 1

5 1 2 b i t ó w

. . .

. . .

H

M D 5

5 1 2

H

M D 5

5 1 2

H

M D 5

5 1 2

H

M D 5

5 1 2

1 2 8

1 2 8

1 2 8

1 2 8

A B C D

1 2 8 b i t o w y w y c i ą g

Przetwarzanie komunikatu w

512-bitowych blokach

• Wszystkie 4 etapy mają

podobną strukturę, lecz

każdy korzysta z innej

elementarnej funkcji

logicznej oznaczanej w

specyfikacji jako F, B, H, I

• W każdym etapie jest

przetwarzany aktualny blok

Y

q

oraz bufor ABCD (MD

q

)

• Dodatkowo w każdym

etapie korzysta się z

kolejnych części tablicy

T[1,...,64] skonstruowanej

na podstawie funkcji sinus

f ( A B C D ,Y , T [ 1 , .. . ,1 6 ] )

F

q

1 2 8

M D

q

A B C D

A B C D

3 2

f ( A B C D , Y ,T [ 1 7 , .. . ,3 2 ] )

G

q

A B C D

f ( A B C D , Y ,T [ 3 3 , .. . ,4 8 ] )

H

q

A B C D

f ( A B C D , Y ,T [ 4 9 , .. . ,6 4 ] )

I

q

5 1 2

Y

q

+

m o d 2

3 2

+

m o d 2

3 2

+

m o d 2

3 2

+

m o d 2

3 2

1 2 8

M D

q + 1

Elementarna operacja MD5

• Każdy z kroków wykonywanych 64

razy dla każdego bloku ma postać

AB+CLS

s

(A+g(B,C,D)+X[k]+T[i])

• Przez g oznaczamy jedną z funkcji

elementarnych F, G, H, I

• X[k] oznacza k-te 32 bitowe słowo

w przetwarzanym 512-bitowym

bloku

• T[i] oznacza i-te 32 bitowe słowo

w tablicy stałych

• Wszystkie dodawania są

realizowane modulo 2

32

Plan wykładu

• Wstęp
• Rodzaje systemów kryptograficznych
• Historia kryptografii
• Szyfrowanie symetryczne
• Algorytm AES
• Szyfrowanie asymetryczne
• Algorytm RSA
• Algorytmy haszujące
• Algorytm MD5

• Podsumowanie

Podsumowanie

• Algorytm symetryczne stosują wiele różnych

sposobów dla zapewnianie silnej konfuzji i dyfuzji

• Algorytmy asymetryczne i haszujące umożliwiają

efektywną realizację szeregu funkcji bezpieczeństwa
(np. uwierzytelnianie, podpis cyfrowy, integralność)

• Bezpieczeństwo kryptograficzne algorytmów zależy

od konstrukcji algorytmu i długości klucza

• Ważnym aspektem jest ochrona praw patentowych,

która może ograniczać możliwość stosowania
danego algorytmu

Kolejny wykład

Bezpieczeństwo sieci

komputerowych