[WikiDyd] [TitleIndex] [WordIndex

Cel zajęć

Zapoznanie się z historycznymi algorytmami kryptograficznych i słabościami związanymi z ich stosowaniem. Zostanie wykorzystany język skryptowy Python umożliwiający szybkie rozwiązanie nawet skomplikowanego problemu.

Wprowadzenie

Analiza algorytmu Cezara, czyli cyklicznego przesunięcie alfabetu. Badanie ROT13, który ma tą zaletę, że dwukrotne wywołanie funkcji szyfrującej jest równoważne odszyfrowaniu. Przykładowa implementacja:

import string
table = string.maketrans("abcdefghijklmnopqrstuvwxyz", "nopqrstuvwxyzabcdefghijklm")
import fileinput
for line in fileinput.input():
        line = line.rstrip()
        print string.translate(line, table)

Głównym narzędziem kryptoanalizy jest statystyka. Kryptogramy historyczne dalekie są od idealnego "białego" szumu. Najprostszą analizą tego rodzaju jest badanie częstotliwości występowania znaków w kryptogramie. Porównując wynik z uśrednionym wzorcem dla danego języka jesteśmy w stanie złamać większość prostych algorytmów historycznych.

Przykład programu dokonującego analizy częstotliwości występowania poszczególnych liter:

import sys, re, string

stat = {}
for line in sys.stdin.readlines():
        line = re.sub(r'\s', '', line)
        for znak in line:
                if znak in stat:
                        stat[znak] += 1
                else:
                        stat[znak] = 0

for znak in stat:
        print "%s <=> %d " % (znak, stat[znak])

Potrzebna wiedza

Przed przystąpieniem do wykonywania ćwiczenia student powinien wiedzą i umiejętnościami w następującej tematyce:

  1. Modyfikowanie przedstawionych programów i pisanie nowych, podobnych.
  2. Teoria algorytmów przesunięcia cyklicznego.
  3. Rozumienie lingwistycznej analizy statystycznej.

Dodatkowe informacje

Hasła dla Google: Cezar, ROT13

Przykładowe zadania

  1. Napisz program szyfrujący algorytmem przesunięcia cyklicznego o wybraną liczbę.
  2. Napisz program deszyfrujący algorytmem przesunięcia cyklicznego.
    • wykorzystując przesunięcie w tył,
    • wykorzystując przesunięcie w przód o dopełnienie do pełnego okresu.
  3. Wielokrotnie wywołując algorytmu przesunięcia cyklicznego w pętli można uzyskać efekt odszyfrowania. Na przykład dla rot13, wystarczy tylko dwa razy. Dla podanej liczby określ teoretycznie ilość wymaganych powtórzeń, a następnie sprawdź to praktycznie.
  4. Za pomocą analizy statystycznej postaraj się odszyfrować tekst zaszyfrowany algorytmem przesunięcia cyklicznego o nieznanym kluczu.
  5. Porównaj rozkłady statystyczne tekstów w trzech różnych językach.

2015-09-23 06:44