Protokoły kryptograficzne

Prowadzący

Robert Obryk <moc.liamg|kyrbor#moc.liamg|kyrbor>

Opis

Na warsztatach będziemy się zajmować protokołami kryptograficznymi służącymi do czegoś więcej niż po prostu prywatnego przesłania danych. Dowiemy się na przykład, jak sprawiedliwie “rzucać monetą” przez telefon czy też jak udowodnić komuś, że coś wiemy nic mu o tym nie mówiąc. Na koniec zaimplementujemy jakiś większy protokół: pewnie protokół do tasowania talii kart w dwie osoby.

Program zajęć

Warsztaty składać się będą z dwu części: teoretycznej i praktycznej. Na tej pierwszej będziemy poznawać (często przez, mam nadzieję, wymyślanie) protokoły i dowodzić ich własności. Na drugiej będziemy implementować

Wymagania

Należy znać podstawy teorii liczb:

  • wiedzieć, że modulo można czasami dzielić;
  • wiedzieć, czym jest reszta kwadratowa i znać jej proste własności;
  • znać twierdzenie Eulera;
  • warto wiedzieć, że każda liczba pierwsza p ma takie g, że $\{1, g \mod p, g^2 \mod p, \ldots, g^{p-2} \mod p\}$ zawiera wszystkie liczby z $\{1, \ldots, p-1\}$

Przydadzą się intuicje na temat wielomianowości algorytmów.

Z powodu częsci praktycznej należy umieć programować. Jeśli ktoś chce pisać w innym języku niż C/C++/Java/Python/Haskell, proszę o maila. Jeśli ktoś podejrzewa, że nie spełnia wymagań, a chciałby w warsztatach uczestniczyć, też proszę o maila.

Zadania kwalifikacyjne

1. Napisz w języku w którym będziesz chciał pisać funkcję liczącą odwrotność modulo (możesz użyć np. rozszerzonego algorytmu Euklidesa).

2. Weźmy pewną liczbę pierwszą p.Otrzymujemy od kogoś liczbę całkowitą wylosowaną z $\{0, 1, \ldots, p-1\}$ z nieznanego nam rozkładu prawdopodobieństa. Losujemy sami liczbę z $\{0, 1, \ldots, p-1\}$ w taki sposób, że prawdopodobieństwo wylosowania każdej liczby jest takie samo. Co można powiedzieć o rozkładzie prawdopodobieństwa iloczynu tych dwu liczb modulo n?

3. Rozważmy następującą sytuację: na serwerze działa program, który przyjmuje po sieci komendy. Aby uniemożliwić niepowołane wywołanie komendy postanowiono, że do serwera będą przesyłane komendy zaszyfrowane kluczem, który jest znany tylko serwerowi i uprawnionym użytkownikom. Serwer deszyfruje otrzymaną wiadomość i, jeśli mu się udało oraz wynik jest jedną z komend, wykonuje uzyskaną komendę. Dla uproszczenia zakładamy, że serwenie wysyła żadnych wiadomości. Wskaż, w jaki sposób przeciwnik będący w stanie podłuchiwać komunikaty wysyłane do serwera może wykonać którąś komendę nie łamiąc szyfru? W jakich sytuacjach jest to rozwiązanie jest bezpieczne (czyli kiedy jeśli przeciwnik nie umie złamać szyfru to też nie jest w stanie spowodować wykonania komendy)? Spróbuj znaleźć metodę uniknięcia tego problemu.

Dodatkowe informacje

O ile nie zaznaczono inaczej, treść tej strony objęta jest licencją Creative Commons Attribution-ShareAlike 3.0 License