Хабрахабр

[Из песочницы] 25 видов «Цезаря» и английские слова

Каждый из них по-своему хорош. В мире криптографии есть много простых способов зашифровать сообщение. Об одном из них и пойдёт речь.

Ылчу Щзкгув

Или в переводе с «Шифра Цезаря» на русский — Шифр Цезаря.

cesar

Классический шифр Цезаря двигает буквы на три шага вперёд. — В чём его суть?
— Он кодирует сообщение, смещая каждую букву на N пунктов. Простыми словами — было «абв», стало «где».

Что с пробелами?
С ними всё в порядке. — А как же буквы в конце алфавита? То есть, буквы «эюя» обратяться в «абв». Если смещая букву шифр выходит за рамки алфавита — он начинает отсчёт сначала. А пробелы остаются пробелами.

N может отличаться от тройки. — Разве N обязательно должно равняться трём?
Совсем нет. Допускаются любые N в промежутке [1: M-1], где M — количество букв в алфавите.

Но меня привлекла не его «надёжность», а кое-что другое. Такой шифр легко расшифровать, если знать о его существовании.

Одним летним днём мне захотелось узнать:

  • А что если я зашифрую слово с помощью «Цезаря», а на выходе получу существующее слово?
  • Сколько таких слов «перевёртышей» есть?
  • И будет ли закономерность, если менять N?

Ответы на эти вопросы я начал искать в те же минуты.

Из концертов Михаила Задорнова и личного опыта я понял две вещи: Отступление.

  1. Американцы не обижаются на речи русских комиков.
  2. Русский язык силён и могуч. И слов в нём немеряно много.

К тому же, когда-то давно была инфа, что англоязычные ребята смогли собрать полный словарь английских слов. Поэтому я решил взять за основу английскую мову. Что побудило меня найти такой Датасет.

Автор обещал 479K английских слов в удобных форматах. Первая строка вялого гугления навела меня на этот репозиторий. Мне приглянулся файл json, в котором все слова были уложены в удобном виде для загрузки в словарь Python.

«Но это не беда, ведь для показательного примера вполне хватит», подумал я. После первого вскрытия оказалось, что слов там поменьше — 370 101 штука.

words = json.load(open('words_dictionary.json', 'r'))
len(words.keys())
>> 370101

Решил сделать его в виде списка самым удобным для меня методом. Для начала нужно создать алфавит. Также нужно было запомнить количество букв в алфавите:

abc = list('abcdefghijklmnopqrstuvwxyz')
abc_len = len(abc)

Вот что получилось: Сначала было интересно сделать функцию перевода слова в зашифрованное.

# слово в цезарь-слово
def cesar(word, abc, abc_len, step=3): word_list = list(word) result = [] for w in word_list: i = abc.index(w) i = (i+step) % abc_len wn = abc[i] result.append(wn) result = ''.join(result) return result

Но наткнулся на проблему. Решил сделать большой цикл по всем словам и начать их переводить одно за другим. Оказалось, что некоторые слова содержали знак «-», что было удивительно и естественно одновременно.

После чего удалил оба, ведь на результате это почти не скажется. Недолго думая, я подсчитал количество таких слов и оказалось, что их — всего два. На помощь мне родилась эта функция:

# удаляет символ «-» и возвращает исправленный словарь
def rem(words): words_list = list(words.keys()) words = for word in words_list: if '-' in word: words_list.remove(word) else: words[word] = 1 return words

Словарь имел вид:

{'a': 1, 'aa': 1, 'aaa': 1, 'aah': 1, ... }

Для этого написал функцию: Поэтому я принял решение не мудрить и заменить единички на закодированные слова.

# конвертирует словарь {'word': 1} в {'word': 'cesar-word'}
def cesar_all(words, abc, abc_len, step=3): result = words for w in result: result[w] = cesar(w, abc, abc_len, step=step) return result

Вот он: И, конечно, нужен был большой цикл, который пройдёт по всем словам, найдёт слова-перевёртыши и сохранит результат.

# проходит по словам и сохраняет результат
def check_all(words_cesar, min_len=0): words_keys = words_cesar.keys() words_result = {} for word in words_keys: if words_cesar[word] in words_keys: if len(word) >= min_len: words_result[word] = words_cesar[word] return words_result

Он будет нужен в будущем. Вы могли заметить, что в параметрах функции стоит «min_len=0». Таких как: «аа», «aah» и подобные сочетания. Ибо особенностью этого Датасета был «странный» набор слов. Именно они дали первый результат — 660 слов-перевёртышей.

Поэтому пришлось поставить ограничение в пять минимум пять символов, чтобы слова были приятны глазу и похожи на существующие.

words_result = check_all(words_cesar, min_len=5)
words_result
>> {'abime': 'delph', 'biabo': 'elder', 'bifer': 'elihu', 'cobra': 'freud', 'colob': 'frore', 'oxime': 'ralph', 'pelta': 'showd', 'primero': 'sulphur', 'teloi': 'whorl', 'xerox': 'ahura'}

Моё любимое сочетание:
primero [Первый] → sulphur [Сера]. Да, десять слов-перевёртышей нашлись благодаря алгоритму. Большинство других пар Google-переводчик не распознаёт.

Но впереди остались вопросы типа: «А что же с другими N?» На этом этапе я частично погасил жажду познания.

И с помощью данной функции я нашёл ответ:

# цикл для всех N
def loop_all(words, abc, abc_len, min_len=5): result = {} for istep in range(1, abc_len): words_rem = rem(words) words_cesar = cesar_all(words_rem, abc, abc_len, step=istep) words_result = check_all(words_cesar, min_len=min_len) result[istep] = words_result print('DONE: {}'.format(istep)) return result

Осталось только посмотреть результаты. Цикл закончил работу за 10–15 секунд. А вот финальная функция, которая покажет нам итог: Но, как я считаю — всё интереснее, когда есть график.

# цветовой график
def img_plot(result): lengths = [] for k in result.keys(): l = len(result[k].keys()) lengths.append(l) lengths = np.reshape(lengths, (5,5)) display(lengths) plt.figure(figsize=(20,10)) plt.imshow(lengths, interpolation='sinc') plt.colorbar() plt.show() >> array([[ 12, 5, 10, 41, 4], [116, 23, 18, 20, 29], [ 18, 15, 56, 15, 18], [ 29, 20, 18, 23, 116], [ 4, 41, 10, 5, 12]])

img_plot

Некоторые N дают намного бОльше слов, чем другие. — А что если я зашифрую слово с помощью «Цезаря», а на выходе получу существующее слово?
— Такое возможно, даже очень.

В моём случае при N=3, минимальной длиной слова в 0 и в 5 — количество слов: 660 и 10 соответственно. — Сколько таких слов «перевёртышей» есть?
— Зависит от N, минимальной длины и, конечно, от Датасета.

Из графика (или тепловой карты) можно заметить, что цвета симметричны. — И будет ли закономерность, если менять N?
— Как видно, да! А ответ на вопрос «Почему так?» оставлю читателю. И значения в матрице результатов говорят об этом.

  • Не совсем корректный Датасет. Многие слова неочевидны. Хотя, так может быть. Это же «все» слова английского языка.
  • Код всегда можно улучшить.
  • «Шифр Цезаря» — частный случай «Афинного шифра», где формула:

$НоваяБуква = A * ПрошлаяБуква + B $

Кстати, у него больше нюансов, а значит — больше интересного. Для «Шифра Цезаря» А = 1.

Мой рабочий файл с результатом и списком слов-перевёртышей лежит в этом репозитории

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть