Реализация подстановочного шифра и некоторый статистический анализ

Мотивация

Вы здесь, потому что беспокоитесь о том, что весь ваш трафик отслеживается и анализируется правительством? Вы находитесь в нужном месте! Здесь вы научитесь как шифровать свой текст, так и читать чей-то секретный чат, который был зашифрован подстановочным шифром.

Плохо то, что в конце концов вы будете уверены, что все ваши чаты в 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». А для этого нужен корпус побольше. Может в следующий раз.

Иногда мы терпим неудачу, да :) Надеюсь, вам все еще понравилось это путешествие.