Algorytmy i Struktury Danych

Kryptografia

Wykład: Krzysztof Loryś

Ćwiczenia: Krzysztof Loryś, Grzegorz Stachowiak

Informacje dla grupy ćwiczeniowej KLo

Spis treści wykładu

· Wykład 1 (17.02): one-time pad, bezpieczeństwo doskonałe, problem logarytmu dyskretnego, protokół (DH) Diffiego-Hellmana wymiany kluczy (bezpieczeństwo, efektywność), założenie DHA

· Wykład 2 (24.02): atak man-in-the middle, RSA, przykłady zastosowań kryptosystemów z kluczem publicznym, typy ataków na kryptosystemy, kryptoanaliza prostych szyfrów symetrycznych (szyfr przesunięciowy, szyfr afiniczny, szyfr podstawieniowy, szyfr Vigenere’a)

· Wykład 3 (3.03): szyfry strumieniowe, LFSR (okresowość, zastosowanie do one-time pad, kryptoanaliza: atak ze znanym tekstem jawnym), Szyfry produktowe, Schemat Feistela, Lucyfer, DES, ataki na DES (przeszukiwanie przestrzeni kluczy, atak „z tradeoffem pamięć-czas”), potrójny DES

· Wykład 4 (17.03): Testy pierwszości. Podstawowy test pierwszości. Reszty i niereszty kwadratowe. Symbole Legendre’a i Jacoby’ego. Prawo wzajemności dla symbolu Jacoby’ego. Test Solovay’a-Strassena. Test Rabina-Millera.

· Wykład 5 (24.03): Ataki na RSA

· Wykład 6 (31.03): Algorytmy faktoryzacji. Metoda p-1. Metoda bazy czynników. Kryptosystem Rabina. Kryptosysytem ElGamala. Kryptosystem plecakowy.

· Wykład 7(14.04): Podpisy cyfrowe. Schemat RSA. Schemat ElGamala. DSS.

· Pozostałe wykłady:

o Podpisy: niezaprzeczalne, jednorazowe, niepodrabialne, ślepe.

o Funkcje skrótu (bezkonfliktowość, atak urodzinowy, funkcja Chauma-van Heijsta-Pfitzmann, rozszerzanie funkcji skrótu, MD4(informacyjnie)).

o Uzgadnianie klucza (schemat Blooma, schemat Diffiego-Hellmana i jego modyfikacje, Kerberos)

o Schematy uwierzytelniania (schemat Schnorra, schemat Okamoto, schemat Quillou-Quisquatera, schemat Fiata-Shamira)

o Schematy wspołużytkowania (konstrukcje oparte na sieci monotonicznej, schemat Shamira)

o Dowody z wiedzą zerową

o Kanał podprogowy. Zobowiązanie bitowe. Pieniądze cyfrowe (prosty protokół). Wybory elektroniczne (informacyjnie bez konkretnego protokołu)

Listy zadań

· Lista nr 1

· Lista nr 3. Pliki pomocnicze:

o Tryby szyfrowania

o Schemat DES

o DES - szczegóły

· Lista nr 4.

· Lista nr 5.

· Lista nr 6.

· Lista nr 7.

· Lista nr 8.

· Lista nr 9.

· Lista nr 10.

Komunikaty:

· Przypominam grupie KLO o składaniu deklaracji. Zadeklarowanie zadania oznacza, że deklarujący nie tylko umie je rozwiązać, ale także umie zaprezentować rozwiązanie.

· Rozwiązania niektórych zadań z listy nr 4 można znaleźć w książce N.Koblitza „Wykłady z kryptografii i teori liczb”. Zachęcam do lektury.

· UWAGA. Dziekan ogłosił, że najbliższy czwartek (24.03) jest wolny od zajęć. Jak się możecie domyśleć, spowoduje to spore komplikacje (np. synchronizacja ćwiczeń z wykładem). W dalszej perspektywie są inne wolne czwartki (Juvenalia, Boże Ciało). Mam w związku z tym pytanie: kto jest za przeprowadzeniem wykładu w najbliższy czwartek, a kto nie może lub nie chce przyjść? Stanie się według Waszej woli.

o Jeśli wykładu nie będzie, sporządzę odpowiednią listę zadań obejmującą nieco nowego materiału (to nie jest takie złe rozwiązanie, jak może się początkowo wydawać)

o Jeśli wykład odbędzie się, oferuję konsultacje dla tych którzy nie mogli być

· Ćwiczenia w dniu 18.05 nie odbędą się L

· Egzamin:

o Pierwszy termin odbędzie się 17.06. pocz. godz 9-ta.

o Drugi termin – do ustalenia. Proponuję 23-ci (w trakcie egzaminu z AiSD). Niewielką liczbę osób mogę przeegzaminować ustnie.

· Po wpisy ocen z egzaminu i ćwiczeń można zgłaszać się do mnie w ii. To będzie szybsze niż czekanie na umieszczenie listy w Internecie. Będę w Instytucie 30.06 i 1.07 w godzinach wczesnego popołudnia.