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

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

Model szyfrowania

konwencjonalnego

• Szyfrator tworzy tekst zaszyfrowany Y=E

(X)

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

przekształcenie X=D

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

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

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

)

lub inaczej w zbiorze {0,1}

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

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

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

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

0 , j

1 , j

2 , j

3 , j

0 , j

1 , j

2 , j

3 , j

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

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

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

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

K J

K P

Szyfrowanie asymetryczne -

uwierzytelnienie

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

K J

K P

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

(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

mod n

M = C

mod n =

)

mod n =

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

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



(n)+1

= m

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

 m mod n

RSA i twierdzenie Eulera

• Z twierdzenia Eulera wynika, że m



(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

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

mod n

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

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

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

5 1 2 b i tó w

5 1 2 b i t ó w

L - 1

5 1 2 b i t ó w

. . .

M D 5

5 1 2

M D 5

5 1 2

M D 5

5 1 2

M D 5

5 1 2

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

oraz bufor ABCD (MD

)

• 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 ] )

1 2 8

M D

A B C D

3 2

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

A B C D

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

A B C D

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

5 1 2

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

(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

Plan wykładu

• 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

Document Outline

Slide 1
Slide 2
Slide 3
Slide 4
Slide 5
Slide 6
Slide 7
Slide 8
Slide 9
Slide 10
Slide 11
Slide 12
Slide 13
Slide 14
Slide 15
Slide 16
Slide 17
Slide 18
Slide 19
Slide 20
Slide 21
Slide 22
Slide 23
Slide 24
Slide 25
Slide 26
Slide 27
Slide 28
Slide 29
Slide 30
Slide 31
Slide 32
Slide 33
Slide 34
Slide 35
Slide 36
Slide 37
Slide 38
Slide 39
Slide 40
Slide 41
Slide 42
Slide 43
Slide 44
Slide 45
Slide 46
Slide 47
Slide 48
Slide 49
Slide 50
Slide 51
Slide 52
Slide 53
Slide 54
Slide 55
Slide 56
Slide 57
Slide 58
Slide 59
Slide 60
Slide 61
Slide 62
Slide 63
Slide 64
Slide 65
Slide 66
Slide 67
Slide 68
Slide 69
Slide 70
Slide 71
Slide 72
Slide 73
Slide 74
Slide 75
Slide 76
Slide 77
Slide 78