Программный взлом шифра FreeBitcoins

ПОСЛЕСЛОВИЕ К КОНКУРСУ «РАСШИФРУЙ ТЕКСТ»

(программный взлом конкурсного шифра)
Author: tabi2018

В основе конкурсного «шифра FreeBitcoins» лежит алгоритм Цезаря, принадлежащий к алгоритмам симметричного шифрования, когда для шифрования и расшифровки используется один и тот же ключ.

Шифр назван по имени древнеримского полководца Гая Юлия Цезаря, впервые применившего данный шифр для защиты личных военных сообщений.

Для лучшего понимания деталей конкурсного шифра, имеет смысл напомнить некоторые свойства шифра Цезаря. Тем более, что шифр Цезаря может служить хорошим введением в необычную и непривычную, хотя и несложную модулярную арифметику — язык современной компьютерной криптографии.

1. Взлом шифра Цезаря без математики

Шифр Цезаря можно описать как сдвиг каждого символа слова на одно и то же число позиций вдоль заданного алфавита. Ввиду своей простоты часто при описании шифра Цезаря не используется математика. Приведем пример быстрого взлома шифра Цезаря «ЗРИТУ», созданного на 32-символьном русском алфавите из заглавных букв

путем последовательного формирования следующей таблицы:

Сначала записываем шифртекст ЗРИТУ. Затем каждый символ сдвигаем по алфавиту на одну позицию вверх [ЗРИТУ] — 1 = [ЖПЗСТ] (или вниз: [ЗРИТУ] + 1 = [ИСЙУФ]) и результат записываем над (под) шифром.
Вся процедура повторяется столько раз, пока не получится осмысленное слово. В данном случае на третьем шаге при движении вверх получается правильное слово — «ДНЕПР». Это значит, что ключ шифрования равен трем.

Шифр Цезаря нашел применение в UNIX-системах для несложного шифрования. Для шифра Цезаря в языке web-программирования PHP предусмотрена специальная команда «str_rot13» шифрования английского текста встроенным ключом K = 13. Поскольку в английском алфавите 26 букв, то повторное применение команды к уже созданному шифртексту приведет к его расшифровке.

2. Арифметика часов и формула шифра Цезаря

Для программирования процесса шифрования текста необходимо иметь уравнения шифрования и расшифровки. Шифр Цезаря, ввиду своих простых свойств, является отличным тренажером для математического усвоения азов криптографии, а именно, модулярной (иногда говорят «модульной») арифметики или «арифметики часов» в терминологии для новичков. Рассмотрим задачу. Сейчас 10 часов дня. Который будет час через 100 часов? Решение на основе модулярной арифметики выглядит так: (10+100) mod 24 = 14. Прокомментируем вычисленный ответ задачи: пройдет четверо суток и еще 4 часа, то есть будет 14 часов. Здесь и в дальнейшем запись «a mod b» означает целый остаток от деления числа a на число b и читается запись так: «a модуль b» или «a по модулю b».

Например:
7 mod 7 = 0, т.к. при делении нет остатка;
25 mod 7 = 4, т.к. 25 = 3*7 + 4, где 4 — остаток от целочисленного деления 25 на 7;
−25 mod 7 = 3, т.к. к левой части можно прибавить нулевое значение 4*7 mod 7 = 0.

Замечание: В СИ−подобных языках программирования ( С, С++, C#, PHP, JavaScript) вместо «mod» применяют процент: a % b. В Pascal, Delphi, Matlab используется обозначение «mod».

Запишем формулы шифрования и расшифровки для алгоритма Цезаря. Пусть X — исходный текст, Y — шифртекст, Xc, Yc — коды символов исходного текста и шифртекста соответственно. Воспользуемся алфавитной кодировкой символов текста, когда кодом символа является порядковый номер буквы в алфавите. Назовем число символов N в алфавите длиной или мощностью алфавита.

Формула шифра Цезаря: Yс = (Xс + K) mod N.
Формула расшифровки: Xс = (Yс − K) mod N.

Все числа Xс, Yс, K, N — целые. Формула шифра Цезаря позволяет автоматически вычислять новые коды символов при сдвиге вверх или вниз алфавита, не беспокоясь выйти за его пределы. Смысл применения операции «mod N» состоит в автоматическом зацикливании алфавита, когда сдвиг символов на K позиций выводит за границы алфавита. Величина сдвига K постоянна для всех символов исходного текста и является секретным ключом шифрования. Число ключей для шифра Цезаря равно длине алфавита N.

Пример 1, поясняющий роль загадочного «mod N»: Требуется зашифровать слово «АБВЭЮЯ» с тремя первыми и тремя последними буквами алфавита. Применен 32-символьный алфавит RU(32) без буквы Ё, мощность алфавита N = 32.
Решение:
«АБВЭЮЯ» + Сдвиг_на_3 = ([0, 1, 2, 29, 30, 31] + 3) mod 32 = {Формально вышли из алфавита} = [3, 4, 5, 32, 33, 34] mod 32 = {автоматически вернулись в алфавит благодаря mod 32} = [3, 4, 5, 0, 1, 2] = «ГДЕАБВ».

Пример 2: Расшифровать формульно шифр Цезаря «ЗРИТУ», если ключ равен 3. Формульное шифрование удобно для программирования.
Решение:
Y = «ЗРИТУ» => Yc = [7, 16, 8, 18, 19]; Xc = ([7, 16, 8, 18, 19] − 3) mod 32 = [4, 13, 5, 15, 16] =>»ДНЕПР».

Пример 3: Важное свойство шифра Цезаря. Зашифровать подряд дважды имя ДАНЯ ключом K = 16 на алфавите RU(32).
Решение:
X = «ДАНЯ»; Составляем массив кодов букв: Xc = [4, 0, 13, 31];
Проводим первое шифрование:
Y1c = ([4, 0, 13, 31] + 16) mod 32 = [20, 16, 29, 15] => «ФРЭП»
Проводим повторное шифрование:
Y2с = ([20, 16, 29, 15] +16) mod 32 = [4, 0, 13, 31] => «ДАНЯ».

ВЫВОД: на русском алфавите реализована точная имитация работы команды «str_rot13» языка программирования PHP, а именно, в результате последовательного двукратного шифрования вернулись к исходному тексту. При этом как и в английском алфавите данное свойство проявляется, если секретный ключ равен половине длины алфавита.

3. Арифметика шифра FreeBitcoins

В статьях [1, 2] дано подробное описание «шифра FreeBitcoins» и его криптоанализ [3]. Перед тем как запрограммировать шифр FreeBitcoins, необходимо разобраться в арифметике шифра и построить уравнения шифрования и расшифровки. С точки зрения программирования алфавит представляет собой строку символов

Alf = «АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ»

с кодировкой (индексацией), которая начинается с нуля. Например, на языке JavaScript команды Alf.charAt(0), Alf.charAt(32) вызывают соответственно буквы «А» и «Я» из строки алфавита. Далее условимся, что кодировка букв начинается с нуля, то есть «А» = 0, «Б» = 1, …, «Э» = 31, «Я» = 32.

Напомним основные особенности алгоритма, который был положен в основу Конкурса [1]:
а) исходный текст формировался на русском алфавите с 33 буквами и нормальным порядком их расположения;
б) для шифрования использовался дополнительный алфавит, который был зеркальным к исходному, когда буквы следуют в порядке обратном к нормальному: «Я» = 0, «Ю» = 1, «Э» = 2 , … , «В» = 30, «Б» = 31, «А» = 32.
в) буквы исходного алфавита отображались в буквы зеркального алфавита с выполнением простого свойства: сумма кодов буквы из двух алфавитов одна и та же и не зависит от буквы; например, «Н»+»Нзеркал» = 14 +18 = 32; «Й» +»Йзеркал» = 10 + 22 = 32 и т.д.
г) исходный текст шифровался по алгоритму Цезаря на зеркальном алфавите;
д) ключ шифрования один и тот же для всех букв внутри слова;
е) направление сдвига букв вверх или вниз алфавита выбиралось из условия четности или нечетности длины шифруемого слова.

Конкурсный «шифр FreeBitcoins» построен как модификация шифра Цезаря, что позволяет в несколько шагов получить для него формулы шифрования и расшифровки:

Шаг 1. Перейти к зеркальному алфавиту и изменить кодировку символов. Если Xс — код буквы в алфавите с нормальным порядком от А до Я, тогда в зеркальном алфавите с направлением следования букв от Я до А, код той же буквы равен Xz = 32 — Xс.

Шаг 2. Задать ключ шифрования K равным длине слова шифрования со знаком «+», если число букв в слове нечетное и «-» в противном случае. Например, для 5-буквенного слова «КАКОЙ» ключ равен 5, для 2-буквенного слова «МЫ» с четным числом букв ключ равен -2 или 31, что то же самое в модулярной арифметике, поскольку -2 = 31 (mod 33).

Шаг 3. Построить уравнение «шифра FreeBitcoins», заменив зеркальные коды Xz в формуле шифра Цезаря Yс = (Xz + K) mod N на кодировку с нормальным следованием букв по формуле шага 1. В результате получается уравнение «шифра FreeBitcoins»: Yс = (32 — Xс + K) mod N, где N — мощность применяемого алфавита. В нашем случае N = 33. Уравнение расшифровки получается перестановкой местами Xс и Yс.

Пример. Провести цикл шифрования-расшифровки слова «ЮЛЯ» по «алгоритму FreeBitcoins», применив соответствующие формулы.

Решение:

1. ШИФРОВАНИЕ: Yc = (32 — Xc + K) mod 33.
а) X = «ЮЛЯ» — исходная строка символов.
б) Кодируем буквы с помощью алфавита с нормальным порядком следования букв от А до Я.
Xc = [31, 12, 32];
в) Согласно алгоритму «шифра FreeBitcoins» ключ шифрования K = 3, так как слово состоит из трех букв и число букв нечетное.
г) Подставляем коды в уравнение шифрования:
Yc = (32 — [31, 12, 32] + 3) mod 33 = [4, 23, 3];
После раскодирования получаем шифр исходного имени Y = «ДЦГ».

2. РАСШИФРОВКА: Xc = (32 — Yc + K) mod 33.
а) Y = «ДЦГ» — шифротекст.
б) Массив кодов шифротекста:
Yc = [4, 23, 3];
в) Ключ расшифровки тот же K = 3.
г) Подставляем коды в уравнение шифрования:
Xc = (32 — [4, 23, 3] + 3) mod 33 = [31, 12, 32];
После раскодирования получаем исходное слово X = «ЮЛЯ».

4. Программный взлом конкурсного шифра FreeBitcoins

Для программного взлома применим метод последовательного перебора ключей, называемый также атакой грубой силой (brute force). Этот метод универсален, поскольку изначально нет никакой дополнительной информации о шифре, в частности, что значение ключа совпадает с длиной слова [2]. Число различных ключей для шифра Цезаря, а значит и для конкурсного «шифра FreeBitcoins», равно мощности полного русского алфавита, на котором проводилось шифрование. Если применить перебор ключей от 0 до 32 только к одному слову из фразы, то получим 33 варианта расшифровки и среди них только один осмысленный вариант, совпадающий с исходным текстом. При этом номер варианта расшифровки будет указывать значение ключа. Можно ускорить процесс перебора ключей, применив его не к отдельному слову, а ко всей фразе. В этом случае немного усложняется поиск в полном множестве возможных расшифровок правильных осмысленных тестов для каждого слова поскольку они будут получаться на разных итерациях.

Ниже приведена программа на языке JavaScript для взлома шифра FreeBitcoins на алфавите с 33 заглавными русскими буквами. На вход программы подается вся зашифрованная фраза. Если между словами есть пробелы и знаки препинания, то они автоматически игнорируются как символы, отсутствующие в алфавите. На выходе программы получается фраза, которая для наглядности и лучшей читаемости разбита на слова по шаблону входной фразы.

// ВЗЛОМ ШИФРА КОНКУРСА FreeBitcoins
// шифртекст (1)
Y1 = 'ПЭ ЩДЩХЪ ЦЪЁШБУБ РВ ЭЫВЮЧ';
L1 = [2, 5, 7, 2, 5]; // Массив длин слов
// шифртекст (2)
Y2 = 'ФЦЁФЭЕЧ ХЭ ВЖФЛРФ, ВИЖИЯТФИ ЮФГ';
L2=[7, 2, 6, 8, 3]; // Массив длин слов
VzlomC(Y1,L1); // вызов функции перебора ключей
//------------------------------------------------------------
function VzlomC(Y,Ls){
var Alf = 'АБВГДЕЁЖЗИЙКЛМНОП';
Alf += 'РСТУФХЦЧШЩЪЫЬЭЮЯ';
var Ls; // Массив длин слов
var N=Alf.length; // Длина алфавита
var n=Y.length; // Длина текста
for (var K=0; K<N; K++){
var X=''; // дешифр текст
for (var i=0; i<n; i++){
for(var j=0; j<N;j++){
if(Y.charAt(i) == Alf.charAt(j)) {
Xc=(32-j+K+N) % N;
X += Alf.charAt(Xc); } } }
// --------------------------
// разбивка строки на слова
Ltxt=X.length; sum=Ls[0]; j=0;
X1=''; for(i=0;i<Ltxt;i++){
if(i ==(sum-1))
{X1 +=X[i]+' '; j++; sum +=Ls[j];}
else X1 +=X[i]; }
//--------------------------
writeln("K = "+K+'. '+X1); }
} // конец функции VzlomC(Y,Ls)

Результатом работы программы по взлому первого шифртекста ‘ПЭ ЩДЩХЪ ЦЪЁШБУБ РВ ЭЫВЮЧ’ является печать 33-х перенумерованных строчек, среди которых находим такие строчки:
K = 5. ФЖ КАКОЙ НЙЮЛГРГ УВ ЖИВЁМ
K = 7. ЦИ МВМРЛ ПЛАНЕТЕ ХД ИКДЗО
K = 31. НА ДЩДЗГ ЖГЧЕЬЙЬ МЫ АВЫЯЁ. Здесь значение ключа равно -2, так как -2 mod 33 = 31

Приведенный выше программный код полностью рабочий и адаптирован под «Редактор JS», распространяемый по свободной лицензии GNU. Программный код можно скопировать и запустить в левом окне онлайн редактора JavaScript, нажимая кнопку «Run» или комбинацию клавиш Ctrl-m.

СПИСОК ЛИТЕРАТУРЫ
1. Первоначальная статья: «Конкурс «Расшифруй текст» (Приз $50+)»
https://freebitcoins.com.ua/konkurs-rasshifruj-tekst-priz-50/
2. Заключительная статья: «Шифр FreeBitcoins и результат конкурса»
https://freebitcoins.com.ua/shifr-freebitcoins-i-rezultat-konkursa/
3. Статья победителя Конкурса:
http://bitalk.org/threads/12653/page-3
4. Редактор JavaScript для запуска программного кода
http://math.chapman.edu/~jipsen/js/

Спасибо Тарасу за старания и интересную статью!

Хочешь оставаться в курсе последних новостей из мира криптовалют?
Подписывайся на наш телеграм канал goo.gl/kRs83a
и присоединяйся к нашему телеграм чату goo.gl/MiZFcL

Отправить ответ