Wykład Kryptografia
Tematy poruszone na wykładach:
- wstęp: szyfrowanie symetryczne: one-time pad,
pojęcia szyfrowania strumieniowego i blokowego, analiza częstości,
szyfrowanie asymetryczne: definicja RSA, zastosowania do realizacji
poufności przekazu oraz podpisu elektronicznego, szyfrowanie hybrydowe,
definicja funkcji hashujących, zastosowania: "elektroniczny notariusz",
MAC, protokoły: ustalanie klucza metodą Diffie-Hellmana, atak
man-in-the-middle na protokół DH, zasada jawności produktów kryptograficznych
i ich ocena
- podstawy algebraiczne: rozszerzony algorytm Euklidesa,
obliczanie odwrotności modulo n , tw. Fermata i Eulera,
Chińskie Twierdzenie o Resztach, zastosowania CRT
do algorytmów potęgowania,
istnienie nietrywialnych pierwiastków z 1 modulo n, obliczanie potęg
modulo n,
- algorytmy faktoryzacji liczb: złożoność metody naiwnej (trial division), metoda rho Pollarda, metoda faktoryzacji Fermata, metoda bazy czynników.
- problem logarytmu dyskretnego: metoda wielkich i małych kroków, algorytm Pohlinga-Hellmana, algorytm oparty na obliczaniu indeksu.
- testy pierwszości: rozkład liczb pierwszych
(funkcja pi(x) i jej
aproksymacja, rozkład liczb pierwszych w klasach kongruencji,
oszacowanie wielkości n-tej liczby pierwszej),
test Fermata (pseudopierwszość, liczby
Carmichaela), test Millera-Rabina (silna pseudopierwszość), derandomizacja testu
Rabina-Millera (rozszerzona hipoteza Riemanna).
- szyfrowanie asymetryczne: RSA: poprawność deszyfrowania,
związek z problemem faktoryzacji, mały publiczny wykładnik - korzyści i niebezpieczeństwa, bezpieczny rozmiar kluczy - nieprzewidywalność postępu
kryptoanalizy, schemat Rabina: szyfrowanie i deszyfrowanie, zalety
(prędkość szyfrowania) i wady (przykład ataku), szyfrowanie ElGamala,
związek z problemami z klasy NP, informacja o algorytmach plecakowych
- podpisy cyfrowe: schematy podpisów with appendix oraz
with message recovery atak na funkcję redundancji
R(M)= M exp(t) , schemat podpisow Rabina: podstawowa wersja, idea
uogólnienia, funkcja redundancji ISO/IEC 9796,
schemat podpisów Fiata-Shamira,
schemat podpisów ElGamala,
atak na ElGamal przy tym samym parametrze k,
atak egzystencjalny przy braku funkcji hashującej, schemat podpisów Schnorra,
metody uwierzytelniania kluczy publicznych: keyrings,
Infrastruktura Klucza
Publicznego, hierarchiczna budowa CA i certyfikacja skrośna, listy CRL,
- autentykacja: protokoły challenge
and response z kryptografia symetryczna i asymetryczną, system haseł
w UNIXie, PIN, listy haseł jednorazowych - schemat Lamporta,
protokoły z wiedzą zerową: pojęcie dowodu interakcyjnego,
dowodu interakcyjnego z wiedzą zerową, protokół Fiata Shamira,
protokół Schnorra,
- ciągi pseudolosowe: generatory fizyczne a pseudolosowe,
przewidywalność i rozróżnialność od generatora losowego, rola testów
statystycznych, generator ANSI X9.17, generator FIPS 186 dla DSA, generatory
LFSR, słabość LFSR, generatory oparte na kilku układach LFSR , A5,
generatory: RSA, BBS
- gospodarka kluczami: przechowywanie kluczy i schematy podziału tajemnic: XOR, schemat Shamira, trasport kluczy: AKEP2, schemat Shamira, MTI,
Kerberos, Clipper i "key ESCROW": budowa LEAF, protokół komunikacji z wykorzystaniem Clippera, atak Blaze'a
- protokoły: SSH, SSL -mechanizmy bezpieczeństwa
- szyfry blokowe: schemat Feistela, mechanizm deszyfrowania,
algorytmy złożone z rund, mechanizm ataku kryptoanalizy różnicowej