W tym ćwiczeniu mamy podany ciąg znaków zaszyfrowany poprzez wykonanie operacji XOR na każdym ze znaków z bajtem o nieznanej wartości (to bajt, w związku z tym wiemy, że jest to wartość z przedziału 0-255). Naszym zadaniem jest odszyfrowanie tej wiadomości.
Autorzy podpowiadają nam, że najłatwiej jest XORować podaną wiadomość ze wszystkimi wartościami od 0 do 255 i wybrać tą która najlepiej pasuje. Oczywiście komputer nie potrafi tak łatwo wyłapać tą wartość, która dla człowieka będzie miała najwięcej sensu. Potrzebujemy metryki pozwalającej naszemu skryptowi obliczyć „sensowność” otrzymanej wiadomości. Pisząc „sensowność” mam na myśli, prawdopodobieństwo, że jakiś człowiek mógł napisać taką wiadomość.
W celu napisania algorytmu do oceniania wiadomości, potrzebujemy częstotliwości z jaką poszczególne znaki ASCII występują w tekstach napisanych w języku angielskim. Ja w pierwszym podejściu próbowałem użyć wartości dostępnych na Wikipedii (https://en.wikipedia.org/wiki/Letter_frequency). Mój algorytm działał, ale nie do końca tak dobrze jak tego oczekiwałem. Otrzymywana przeze mnie odpowiedź miała najlepszy wynik, ale nie była najlepsza i musiałem przeglądać wszystkie wiadomości od najlepszej do najgorszej aby wybrać tą właściwą. Problemem było to, że statystyki z Wikipedii dotyczyły jedynie liter z alfabetu i nie uwzględniały białych znaków takich jak np. spacja, przejść do nowej linii czy cyfr. W związku z tym zacząłem szukać lepszej statystyki. W pewnym momencie miałem pomysł, aby stworzyć projekt w którym przeprowadzę stosowne obliczenia (na końcu wpisu podam gdyby ktoś szukał pomysłu na miniprojekt). W końcu trafiłem na stronę http://www.fitaly.com/board/domper3/posts/136.html i znalazłem dokładnie to czego potrzebowałem i mogłem zacząć kodować (https://gitlab.com/akoltys/cryptopals).
def get_string_score(input_string):
score = 0
for input_char in input_string:
input_char = chr(input_char)
if input_char in CHARS_FREQ:
score += CHARS_FREQ[input_char]
return score
def find_best_key(input_string):
scores = {}
for x in range (0, 256):
xored_input = hex_string_xor_key(input_string, [x])
scores[x] = get_string_score(xored_input)
if (scores[x] > 0):
print(x, scores[x],''.join([chr(x) for x in xored_input]))
secret_key = max(scores, key=scores.get)
secret_msg = hex_string_xor_key(input_string, [secret_key])
decoded_msg = ''.join([chr(x) for x in secret_msg])
if scores[secret_key] > 0:
print('Secret Key: ', secret_key, ' Score: ', scores[secret_key], '>>>', decoded_msg)
return scores[secret_key], decoded_msgFunkcja find_best_key przyjmuje jako argument wiadomość, którą chcemy rozszyfrować. Wiadomość XORowana jest z wszystkimi wartościami od 0 do 255 i obliczany jest wynik otrzymanej zdekodowanej wiadomości. W tym celu używana jest funkcja get_string_score, która jako argument przyjmuje wiadomość do ocenienia. Funkcja sprawdza wszystkie znaki z podanego ciągu i sumuje ich wartość punktową zapisaną w zmiennej CHARS_FREQ. Zmienna CHARS_FREQ jest słownikiem w którym kluczem jest wartość ASCII a wartości to procentowa częstotliwość występowania danego znaku w tekstach napisanych w języku angielskim.
Po obliczeniu wyników dla wszystkich kombinacji, wybieramy tą która osiągnęła najlepszy wynik.
POMYSŁ NA MINIPROJEKT
Tak jak wcześniej wspomniałem, zamiast szukać gotowej statystyki, można samemu taką sporządzić. Na stronie https://www.gutenberg.org/ dostępnych jest bardzo dużo książek które można legalnie i za darmo pobrać w różnych formatach. Projekt polega na pobraniu np. 10 najpopularniejszych książek w języku angielskim i na ich podstawie zrobić statystykę.
PS. Jak ktoś bardzo chce, to da się podciągnąć nasz algorytm pod uczenie maszynowe albo jak kto woli Machine Learning – zbieranie statystyk występowania poszczególnych znaków jest procesem uczenia algorytmu.