Алгоритм поточного шифрования SOLlTAlRE (ПАСЬЯНС) предложен Б. Шнайером в 1999 г. Шифр до безумия красив и я не понимаю, почему на Хабре его еще никто не осветил. Неужели никто не читал «Криптономикон» Стивенсона? Собственно после прочтения книги не могу пройти мимо сего чуда.
Из теории, это поточный шифр с обратной связью по выходу. Из поточности следует, что каждому символу изначальной последовательности будет соответствовать символ зашифрованной. Для тех, кто не знает, к примеру, существуют еще блочные шифры, в них шифрование происходит блоками (несколькими байтами или символами). Далее существует очень много видов сцепления блоков текста и так называемой гаммы (некой случайной секретной последовательности). В данном случае используется обратная связь по выходу, т.е. каждый символ гаммы изменяет состояние гаммы.
Шифрование
Шифрование производится крайне легко. Имеются 2 последовательности:
- DO NOT USE PC
- AD JEN MWD OI
1 — текст, который необходимо зашифровать. 2 — гамма (о ее генерации ниже). Все что необходимо, это перевести текст в цифры и разбить текст по 5 букв (это криптографический этикет). Если букв меньше, то они заполняются неким условным символом, например х.
- 4|15|14|15|20 21|19|5|16|3
- 1|4|10|5|14 13|23|4|15|9
Далее производится сложение. Если получается число большее 26, то из него необходимо вычесть 26. Пример 4+1=5, 20+14=8.
Итоговая последовательность: 5|19|24|20|8 8|16|9|5|12. Переведем в буквы: ESXTH HPIEL
Расшифровка
Расшифровать сообщение тоже очень легко. Генерируется абсолютно такая же гамма и из зашифрованного текста вычитается гамма. Если получается число меньшее нуля, то к нему просто прибавляется 26. Пример 5-1=4, 8-14=20.
- 5|19|24|20|8 8|16|9|5|12
- 1|4|10|5|14 13|23|4|15|9
Итого имеем 4|15|14|15|20 21|19|5|16|3 -> DO NOT USE PC
Генерация гаммы
Именно эта часть алгоритма делает таким интересным этот шифр. Необходима полная колода карт 52 карты + 2 джокера. Карты необходимо пронумеровать, желательно в уме (Вы же не хотите, чтобы АНБ узнало Ваш секрет). От Туза к Королю от 1 до 13 и по мастям порядок следующий Трефы, Бубны, Черви, Пики. Последние 2 номера возьмут джокера, которые необходимо отличать 53-А, младший джокер и 54-Б старший джокер.
Вам необходимо иметь 2 колоды, которые будут абсолютно одинаково перетасованы. Одна колода будет у Вас, другая у Вашего товарища, который будет дешифровать Ваши сообщения.
Для простоты восприятия я сокращу колоды до 28 карт. Допустим изначально они располагались в таком порядке:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
1 шаг. Передвиньте младшего джокера на 1 карту вниз колоды. Если он окажется последним, то поставьте его после 1 карты.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 28 27
2 шаг. Передвиньте старшего джокера на 2 позиции вниз колоды. Если он последний, то поместите его после 2 карты, если предпоследний то после первой картой.
1 28 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
3 шаг. Поменяйте местами 2 крайние части колоды, отделяемые 2 джокерами. В данном случае число 1 пойдет в конец колоды.
28 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 1
4 шаг. Посмотрите на последнее число. Отсчитайте такое количество карт от начала колоды и поместите их перед последней картой. Последнюю карту намеренно оставляют на месте для обратимости алгоритма.
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 1
5 шаг. Посмотрите на 1 число. Отсчитайте такое количество карт после нее и запомните это число. В данном случае это 4. Это и есть первое число ключевой последовательности. Этот шаг не изменяет колоду. Далее шаги с 1 по 5 повторяются n раз. Где n — количество символов в шифруемом тексте.
Локализация
Я подумывал еще и о кириллическом варианте «пасьянса». Все оказалось довольно не трудно. Если исключить букву ё, то в русском языке остается 32 буквы. +2 джокера итого 34 карты. Обычная колода без 6-ок.
Реализация
Суть шифра в его незаметности. Ну сами посудите, что выглядит палевнее: колода карт или шифровальные программы на ноутбуке? Тем не менее, для зашифровки и расшифровки больших текстов необходимо потратить много времени. Я нашел целую кучу реализаций. Но среди них не было знакомого мне PHP. Как раз был очень скучный вечер и родилось небольшое приложение (ссылка внизу). Основа приложения это класс «пасьянс». В нем реализуются некоторые необходимые методы.
- Подготовка сообщения. определение его языковой принадлежности, формирование некоторых констант и обработка строки.
- Подготовка гаммы. Точнее изначальной последовательности, которую задает пользователь. Из нее как раз получается гамма
- Получение посимвольно гаммы. Решение наверняка не самое элегантное (буду рад замечаниям). Использовалось массовое array_slice — array_merge.
- Конвертация строк в числа и обратно.
- Сложение строк и вычитание (шифрование и расшифровка).
Оценка
Подобные алгоритмы можно дешифровать только грубой силой (перебором). Различные аналитические методы к нему практически не применимы. Слабость алгоритма только в его ключе (колоде). Если запечатлят колоду — смогут расшифровать, и то при условии, что Вы полностью следуете алгоритму.
Сам автор предлагает несколько путей.
1. Используйте каждый раз новый ключ. Ключ берите из некой договоренности (колонка бриджа из газет, некие числа из фондовых оценок итд). Главное о них договориться.
2. Немного измените алгоритм получения гаммы. Тогда при изъятии колоды, АНБ все равно ничего не поймет.
Ссылки
Официальная статья автора алгоритма: link
Мое приложение для шифрования и расшифровывания: link
Ссылка на класс PHP: link
Автор: Assorium
