[WikiDyd] [TitleIndex] [WordIndex

Cel zajęć

Celem zajęć jest zapoznanie z algorytmami szyfrowania systetrycznego. Zarówno z algorytmami blokowymi jaki i strumieniowymi. Wprowadzanie do tematyki trybów pracy szyfrów blokowych, a także ataków brutalnej siły.

Wprowadzenie

Wprowadzenie do RC4. Algorytm RC4 jest algorytmem szyfrowania strumieniowego. Jego zadaniem jest wygenerowanie strumienia klucza, który następnie jest łączony z tekstem jawnym za pomocą operacji XOR. Poniżej przedstawiony jest pseudokod RC4:

# Inicjalizowanie rejestru:
for i from 0 to 255
    S[i] := i
endfor
j := 0
for i from 0 to 255
    j := (j + S[i] + key[i mod keylength]) mod 256
    swap values of S[i] and S[j]
endfor

# Generowanie strumienia klucza
i := 0
j := 0
while GeneratingOutput:
    i := (i + 1) mod 256
    j := (j + S[i]) mod 256
    swap values of S[i] and S[j]
    K := S[(S[i] + S[j]) mod 256]
    output K
endwhile

Algorytm RC4 jest dostępny także w bibliotece Crypto:

from Crypto.Cipher import ARC4
cipher = ARC4.new("key")
encrypted = cipher.encrypt("Top secret")

Atak brutalnej siły na kryptogram polega na systematycznym przetestowaniu całej przestrzeni możliwych kluczy. Przeprowadzenie ataku wymaga określenia jednoznacznego kryterium zakończenia. Algorytm musi umieć stwierdzić, czy kryptogram został odszyfrowany prawidłowo. Ogólną metodą odróżniania poprawnego odszyfrowania od przypadkowych wyników jest entropia. Tekst naturalny ma entropię znacząco niższą niż przypadkowy wynik odszyfrowania. Znając jednak charakter tekstu jawnego, można zaproponować znacznie prostsze rozwiązania.

Entropia w teorii informacji definiuje następujący wzór entropia.png, gdzie p_i jest prawdopodobieństwem i-tego elementu. Entropię można łatwo wyznaczyć mając histogram tekstu. Trzeba zsumować - p_i log_2 p_i dla wszystkich możliwych elementów histogramu o długości n ( p_i = n_i / n  ).

Potrzebna wiedza

Podstawy programowania w języku Python. Znajomość algorytmów RC4. Zrozumienie znaczenia entropii i metod jej obliczania.

Dodatkowe informacje

Hasła dla Google: RC4, entropy

Przykładowe zadania

  1. Zaimplementuj samodzielnie algorytm generowania klucza algorytmem RC4.
  2. Napisz program szyfrujący przy pomocy XOR i klucza generowanego przez RC4.
  3. Zweryfikuj zgodność swojej implementacji z ARC4 z biblioteki PyCrypto.

  4. Napisz algorytm obliczający entropię.
  5. Porównaj entropie tekstu naturalnego z entropia kryptogramu.
  6. Napisz program przeprowadzający atak brutalnej siły na kryptogram.
  7. Oceń szybkość algorytmu brutalnej-siły. Jaką długość klucza możesz złamać w ciągu 1 minuty?

2015-09-23 06:44