Реализация подстановочного шифра и некоторый статистический анализ
Мотивация
Вы здесь, потому что беспокоитесь о том, что весь ваш трафик отслеживается и анализируется правительством? Вы находитесь в нужном месте! Здесь вы научитесь как шифровать свой текст, так и читать чей-то секретный чат, который был зашифрован подстановочным шифром.
Плохо то, что в конце концов вы будете уверены, что все ваши чаты в WhatsApp можно легко декодировать (конечно, это неправда, Facebook решил не использовать шифр замены для WhatsApp около 40 лет назад).
Мы реализуем шифр подстановки на Python, а затем попробуем взломать код, используя статистику.
Замещающий шифр
Википедия говорит:
В криптографии подстановочный шифр - это метод шифрования, при котором единицы открытого текста заменяются зашифрованным текстом в соответствии с фиксированной системой; единицы могут быть отдельными буквами (наиболее распространенными), парами букв, тройками букв, смесями вышеперечисленного и так далее. Получатель расшифровывает текст, выполняя обратную замену.
Другими словами, все буквы «A» заменяются на «B», а все буквы «B» заменяются чем-то другим. Просто смешиваем все буквы. И человек, который получает зашифрованный текст, знает, как смешиваются буквы.
Давайте посмотрим на пример.
У вас есть этот текст:
On a dark desert highway Cool wind in my hair Warm smell of colitas Rising up through the air Up ahead in the distance I saw a shimmering light My head grew heavy and my sight grew dim I had to stop for the night There she stood in the doorway I heard the mission bell And I was thinkin' to myself 'This could be heaven or this could be hell Then she lit up a candle And she showed me the way There were voices down the corridor I thought I heard them say
И давайте заменим эти буквы:
abcdefghijklmnopqrstuvwxyz
этим:
fcpevqkzgmtrayonujdlwhbxsi
Итак, вместо «a» мы пишем «f», вместо «b» мы пишем «c» и так далее.
Тогда мы получаем этот зашифрованный текст:
oy f efjt evdvjl zgkzbfs poor bgye gy as zfgj bfja davrr oq porglfd jgdgyk wn lzjowkz lzv fgj wn fzvfe gy lzv egdlfypv g dfb f dzgaavjgyk rgkzl as zvfe kjvb zvfhs fye as dgkzl kjvb ega g zfe lo dlon qoj lzv ygkzl lzvjv dzv dlooe gy lzv eoojbfs g zvfje lzv agddgoy cvrr fye g bfd lzgytgy' lo asdvrq 'lzgd powre cv zvfhvy oj lzgd powre cv zvrr lzvy dzv rgl wn f pfyerv fye dzv dzobve av lzv bfs lzvjv bvjv hogpvd eoby lzv pojjgeoj g lzowkzl g zvfje lzva dfs
Для простоты все буквы теперь строчные. Конечно, это не требование.
Реализация на Python
Реализация на Python проста: мы смотрим на каждую букву, и если буква в алфавите, то заменяем ее на ключ:
alphabet = "abcdefghijklmnopqrstuvwxyz" key = "fcpevqkzgmtrayonujdlwhbxsi" text = "On a dark desert highway Cool wind in my hair" result = "" for letter in text: if letter.lower() in alphabet: result += key[alphabet.find(letter.lower())] else: result += letter print(result)
Ага. Мы сделали. Но это Python, так почему бы не упростить его?
alphabet = "abcdefghijklmnopqrstuvwxyz" key = "fcpevqkzgmtrayonujdlwhbxsi" text = "On a dark desert highway Cool wind in my hair" print("".join([key[alphabet.find(a)] if a in alphabet else a for a in text.lower() ]))
Реализация на JavaScript
Реализация в JavaScript включает некоторую структуру HTML и прочее, поэтому она немного длиннее, хотя идея та же:
Проанализируйте это :)
Итак, почему Facebook решил не шифровать все чаты подстановочным шифром? Неужели просто взломать код?
Как бы вы к этому подошли?
Брутфорс займет некоторое время, и нетривиально проверить, декодирован ли текст, вам нужно проверить каждое слово и сравнить его с некоторым словарём. Другая проблема в том, что некоторые слова могут быть названиями, например, «Калифорния», и вы их не найдете.
Поскольку мы шифруем букву за буквой, есть смысл расшифровать ее таким же образом. Подсчитываем количество букв в «нормальном тексте» и выясняем, какие буквы встречаются чаще. Скажем, если буква «е» встречается чаще всего, мы находим самую частую букву в нашем зашифрованном тексте и заменяем ее на «е». Скорее всего, мы будем правы.
Ok. Как считать? Я взял слова знаменитой «Богемской рапсодии» Queen и сосчитал буквы:
import matplotlib.pyplot as plt alphabet = "abcdefghijklmnopqrstuvwxyz" plt.bar(list(alphabet), [corpus.lower().count(letter) for letter in alphabet])
Здесь переменная corpus содержит текст полностью. В итоге получаем вот такую диаграмму:
А вот частота букв в нашем зашифрованном тексте:
Итак, отсюда мы можем предположить, что буква «е», скорее всего, зашифрована буквой «v», а буква «о» - буквой «z».
Разберем оба графика:
import pandas as pd df = pd.DataFrame({ "letter": list(alphabet), "count": [corpus.lower().count(letter) for letter in alphabet] }) df = df.sort_values("count") plt.bar(df["letter"], df["count"])
Вот для корпуса («Богемская рапсодия»):
А вот и зашифрованный текст:
Тогда получаем следующий ключ:
gpnkvqayftioedzcxbjlshwmru
против оригинального ключа:
fcpevqkzgmtrayonujdlwhbxsi
А сейчас это, конечно, неточно :( Но мы отгадали по крайней мере пару букв. Это может быть отправной точкой для угадывания остальных.
Итак, нам не удалось взломать этот код. И я был слишком наивен, чтобы придерживаться такого подхода. Итак, я быстро поискал алгоритм в Интернете и обнаружил, что он намного сложнее.
Что вам нужно сделать, так это собрать статистику биграмм, квадрамм и т. Д. Итак, мы должны выучить что-то вроде «за буквой A часто следует буква T». А для этого нужен корпус побольше. Может в следующий раз.
Иногда мы терпим неудачу, да :) Надеюсь, вам все еще понравилось это путешествие.