Materiały do ćwiczeń z kryptografii

(do tego wykładu)

Semestr letni 2006/2007

21.02 Wprowadzenie
  1. Parę słów o tym co to jest kryptografia. Dyskuja o tym że nie istnieją idealne zabezpieczenia, a szyfrowanie jest kompromisem pomiędzy kosztem zabezpieczenia a kosztem dostania się do chronionych danych.
  2. Stosowane proste sposoby szyfrowania: rot13, szyfry permutacyjne i przestawieniowe.
  3. Łamanie szyfrów przez analizę częstotliwości.
  4. Idealna tajność: szyfr jednorazowy. Pokazanie że niezależnie od rozkładu wiadomości, idealna losowość klucza gwarantuje idealną losowość szyfrogramów.
  5. Ataki kryptologiczne:
28.02 Szyfry symetryczne
  1. Czego dowiaduje się przeciwnik, jeśli użyjemy tego samego klucza szyfru jednorazowego do zakodowania wiadomości M1 i M2? Jakie to ma znaczenie dla wiadomości będących np. tekstem albo obrazem?
  2. Pokazać że złożenie dwóch (niezależnych) systemów idealnie tajnych daje system idealnie tajny.
  3. LFSR to efektywna metoda generowania pseudolosowych ciągów, używanych do szyfrowania min. w kartach chipowych i tokenach. W przypadku używania pojedynczego LFSR, ile potrzeba bitów do odtworzenia całego generowanego przez niego ciągu (w praktyce używa się kombinacji kilku generatorów)?
  4. Szyfr Hilla polega na traktowaniu liter alfabetu jako elementów grupy Z26 i mnożeniu każdego bloku d liter przez wybraną (odwracalną) macierz d * d. Pokazać że taki szyfr można złamać za pomocą ataku z wybranym tekstem jawnym i określić jak długi tekst jest potrzebny do odtworzenia klucza.
  5. System nazywamy parami bezpiecznym, jeśli dla dowolnej pary wiadomości M1 i M2, prawdopodobieństwo że M1 zostanie zaszyfrowane jako C jest takie samo jak że M2 zostanie zaszyfrowane jako C. Pokazać że ta własność jest równoważna idealnej tajności.
07.03 DES
  1. Opis działania DES.
  2. Jakie są znane ataki na DES. Krótkie wprowadzenie do kryptoanalizy.
  3. Używanie "Podwójnego DES" nie jest przydatne ze względu na atak pamięciowy. Pokazać jak wygląda zależność użytej pamięci do liczby potrzebnych operacji w tym ataku. W praktyce używa się potrójnego DES. Pokazać jakie są koszty analogicznego ataku w tym przypadku.
  4. Omówienie modeli używania szyfrów blokowych.
14.03 Szyfry asymetryczne: RSA
  1. Opis działania RSA.
  2. Własności funkcji fi.
  3. Pokazać że znajdowanie wartości funkcji fi jest równie trudne jak faktoryzacja.
  4. Pokazać że dla klucza publicznego RSA równego (n,3) znajomość szyfrogramów C(M) oraz C(M+1) pozwala odtworzyć wiadomość M.
  5. Pokazać że jeśli wiadomość M została zaszyfrowana RSA za pomocą klucza (n,e) oraz za pomocą nieprawidłowego klucza (n,e'), gdzie e' różni się od e na jednym bicie, to przeciwnik znając te dwa szyfrogramy jest w stanie odtworzyć M bez pomocy klucza prywatnego.
21.03 Inne szyfry asymetryczne
  1. Opis działania ElGamal.
  2. Opis działania protokołu Diffie-Hellmana.
  3. Opis działania szyfru Rabina.
  4. Szyfry oparte o krzywe eliptyczne.
  5. Szyfry oparte na problemie plecakowym: Merkle-Hellman.
4.04 Kryptografia kwantowa
  1. Wprowadzenie: co to jest kubit i jak ma działać hipotetyczny komputer kwantowy.
  2. Przy pomocy kubitów można robić uzyskiwać różne nieintuicyjne efekty. Przykładem jest kwantowa teleportacja.
  3. Zbudowanie komputera kwantowego pozwoliłoby łamać szyfry RSA, ElGamal, Diffie-Hellmana i ogólnie wszystkie szyfry teorioliczbowe. Przykładem jak to działa jest kwantowy algorytm faktoryzacji.
  4. Komputera kwantowego póki co nikt nie zbudował, ale operowanie na pojedynczych kubitach jest łatwe w realizacji. To wystarczy do stworzenia idealnie bezpiecznego protokołu wymiany klucza, np. Protokołu BB84.
  5. Urządzenia korzystające z kryptografii kwantowej można już kupić w sklepach: MagiQ Technologies (warto obejrzeć prezentację).
18.04 Funkcje jednokierunkowe
  1. Pokazać że jeśli g i h są różnymi pierwiastkami modulo liczba pierwsza p, to umiejętność szybkiego rozwiązywania logarytmu dyskretnego przy podstawie g (czyli dla dowolnej liczby 0 < x < p możemy łatwo znaleźć y takie że gy=x (mod p)), daje też możliwość szybkiego rozwiązywania logarytmu dyskretnego przy podstawie h.
  2. Funckja zaniedbywalna to funkcja f : R+ -> R+ malejąca tak szybko, że dla dowolnej liczby naturalnej c istnieje argument począwszy od którego jest już mniejsza od n-c. Jeśli f(x) i g(x) są zaniedbywalne, to czy zaniedbywalne są:
    • f(x)+g(x)
    • f(x)g(x)
    • f(g(x))?
  3. Funkcja (silnie) jednokierunkowa to funkcja f:{0,1}*->{0,1}* spełniająca warunki:
    4. * f jest obliczalna w wielomianowym czasie
    * dla dowolnego wielomianowego algorytmu probabilistycznego, prawdopodobieństwo że mając daną wartość y algorytm ten znajdzie x takie że f(x)=y, jest funkcją zaniedbywalną (od sumy długości x i y).
  4. Czy złożenie funkcji jednokierunkowych może (musi) być funkcją jednokierunkową?
  5. Czy dla dowolnej funkcji jednokierunkowej f, funkcja g=f(x) xor x jest jednokierunkowa? (xor wykonujemy bit po bicie, pozostawiając fragment dłuższego argumentu nietknięty)
  6. Predykat hard-core dla funkcji jednokierunkowej f, to boolowska funkcja b : {0,1}k->{0,1} taka, że odgadnięcie b(x) na podstawie f(x) jest trudne. Formalnie, żaden wielomianowy algorytm probabilistyczny nie odgaduje go z prawdopodobieństwem większym od 1/2 o nie-zaniedbywalną funkcję k.
  7. Uniwersalny predykat hard-core, to funkcja b(x) taka, że dla dowolnej funkcji jednokierunkowej jest on jej predykatem hard-core. Pokazać że nie istnieje coś takiego.
25.04 Funkcje jednokierunkowe i generatory pseudolosowe
  1. Pokazać że istnienie funkcji słabo jednokierunkowych implikuje istnienie funkcji silnie jednokierunkowych.
  2. Pokazać że istnienie funkcji jednokierunkowych implikuje że P=/=NP, a nawet że BPP=/=NP.
  3. Zdefiniujmy następujący język:
    L={n#k: n ma nietrywialny dzielnik d < k }
    • pokazać że L należy do NP i do co-NP
    • pokazać że jeśli L jest NP-zupełny, to NP=co-NP
    • pokazać że jeśli L należy do klasy BPP, to faktoryzacja jest problemem łatwo rozwiązywalnym
    • wywnioskować że jeśli L nie należy do BPP, to (NP ^ co-NP)\BPP jest niepusty (zauważyć że jest to silniejszy wynik niż P=/=NP).
  4. Generator pseudolosowy to deterministyczny algorytm wielomianowy wyliczający funkcję G:{0,1}k->{0,1}l taką że l > k, oraz żaden wielomianowy algorytm nie jest w stanie odróżnić wyniku działania generatora od ciągu losowego. Formalnie:
    Dla dowolnego wielomianowego algorytmu probabilistycznego A, jeśli weźmiemy losowy ciąg y o długości l, i losowy ciąg x o długości k, to |Pr[A(G(x))=1]-Pr[A(y)=1]| jest zaniedbywalną funkcją k.
  5. Czy dla dowolnych generatorów pseudolosowych G1 i G2 wynik operacji G1 xor G2 jest generatorem pseudolosowym?
  6. Pokazać, że istnienie generatorów pseudolosowych implikuje istnienie funkcji jednokierunkowych.
9.05 Podpisy cyfrowe
  1. Co to jest Podpis cyfrowy.
  2. Ataki kryptologiczne na podpis cyfrowy:
    • Atak bezpośredni - jedynie przy wykorzystaniu klucza
    • Atak ze znanymi podpisami - dysponując kolekcją jakichś wiadomości i podpisów wygenerowanych przez właściciela klucza
    • Atak z wybranymi podpisami - dysponując kolekcją wybranych przez siebie wiadomości, podpisanych przez właściciela klucza (innych niż podpisywane w czasie ataku)
  3. Sposoby złamania podpisu:
    • Złamanie egzystencjalne - wygenerowanie jakiegoś poprawnego podpisu (potencjalnie do bezsensownej wiadomości)
    • Złamanie selektywne - wygenerowanie podpisu do jednej z wybranych przez siebie wiadomości
    • Złamanie uniwersalne - wygenerowanie podpisu do każdej wybranej wiadomości
    • Złamanie totalne - poznanie klucza prywatnego podpisującego
  4. Pokazać że podpis oparty o RSA można
    a) Złamać egzystencjalnie przy pomocy ataku bezpośredniego
    b) Złamać uniwersalnie za pomocą ataku z wybranymi podpisami
  5. Opis działania DSA. Pokazać że ten system można złamać egzystencjalnie za pomocą ataku bezpośredniego.