Kryptografia symetryczna

Prowadzący

Bartłomiej Surma
Śmiało piszcie na mojego maila w razie jakichkolwiek pytań / uwag. (bartlomiej.surma(at)grinvest.pl)

Opis

Kryptografia zajmuje się zabezpieczaniem informacji tak, żeby niepowołane osoby nie mogły się do nich dostać.
Za każdym razem, kiedy logujesz się do komputera, czy korzystasz z szyfrowanego połączenia internetowego (np. podczas logowania się na facebooka, kożystania z gmaila, czy korzystania z internetowego banku) używasz różnych algorytmów kryptograficznych (a właściwie, robi to za ciebie urządenie).

Posługiwanie się narzędziami kryptograficznymi nie jest trudne, jednak bardzo łatwo jest popełnić jakiś błąd, który sprawi, że zupełnie nie uzyska się zabezpieczenia.

Na tych warsztatach mamy poznać i zrozumieć podstawowe narzędzia kryptograficzne, a także (co nawet ważniejsze) nauczyć się, jak wykorzystywać je w sposób zapewniający bezpieczeństwo (budować na ich podstawie bardziej skomplikowane systemy).
Nauczymy się stwierdzać i udowadniać, dlaczego pewne konstrukcje są bezpieczne, a inne nie.

Program zajęć

1.Szyfry strumieniowe

• sposób działania, definicja bezpiecznego szyfru, One Time Pad - szyfr nie do złamania
• generatory liczb pseudolosowych, LFSR, co to znaczy, że algorytm jest nie do złamalny
• przykłady złych implementacji: MS-PPTP, WEP

2. Szyfry blokowe

• idea
• funkcje pseudolosowe, permutacje pseudolosowe
• Data Encryption Standard - działanie, analiza, następcy - bezpieczniejsze szyfry
• abstrakcyjny model szyfrów blokowych
• ataki na szyfr, jak się przed nimi bronić

3. Upewnianie się, że wiadomość pochodzi od nadawcy, czyli integralność danych

Wymagania

Czym jest funkcja, co to jest dodawanie modulo, czy po prostu modulo, co to jest XOR bitowy, jakie ma własności.
Podstawy rachunku prawdopodobieństwa: co to są zmienne losowe, jak ich używać.

Właściwie całą tę wiedzę sprawdzać będą zadania kwalifikacyjne, jeśli będziecie mieli z nimi problemy, dajcie znać.

Zadania kwalifikacyjne

1. Jak wygląda jednostajny rozkład prawdopodobieństwa dla {0,1}\(^3\) - trzybitowego ciągu znaków? (Ciągu złożonego z trzech znaków należących do {0,1})

2. Mamy generator dwubitowych słów, taki, że n-te słowo z generatora
\(x_{n} = x_{n-1} +_{\mod4} 1\) lub \(x_n = x_{n-1} -_{\mod4} 1\), każdy z prawdopodobieństwem \(\frac{1}{2}\)
wiemy, że \(x_o = 10\). (jest to zapis w systemie binarnym, nie będę już później tego zaznaczał)
Przedstaw rozkłady prawdopodobieństw dla zerowego, pierwszego i drugiego słowa tego generatora.

3. Niech \(r_1, r_2\) będą jednostajnymi zmiennymi losowymi na \(\{0,1\}^2\).
Zdefiniuj zmienną losową \(X = r_1 + r_2\).
Ile wynosi Pr[X = 11] ?

4. Niech X będzie zmienną losową na \(\{0,1\}^n\), niech Y będzie niezależną, jednostajną zmienną losową na \(\{0,1\}^n\). Udowodnij, że Z := X⊕Y jest jednostajną zmienną losową.

5. Mamy grę w której jest n graczy (ponumerowanych od 0 do n-1), każdy zapisuje na kartce wybraną (losowo) liczbę od 1 do n, liczby są dodawane, a ich wynik modulo n oznacza zwycięzcę. Czy każdy z graczy ma równe szanse na wygraną?

6. Mamy grę w której gracz ma za zadanie odgadnąć kartę (od 9 do A). Jedyny ruch jaki może wykonać, to pokazać zbiór kart wyroczni i zapytać jej, czy szukana karta znajduje się wśród nich. (Wyrocznie zawsze odpowiada zgodnie z prawdą.) W dowolnym momencie może wskazać szukaną kartę i wygrywa, jeśli wskazał właściwą, przegrywa, jeśli fałszywą. Ile zapytań musi zrobić gracz, żeby na pewno wygrać? Ile średnio zapytań potrzebuje, żeby wygrać?