0,0
рейтинг
28 февраля 2012 в 00:11

Разработка → Крипто-шифр «пасьянс»

Алгоритм поточного шифрования SOLlTAlRE (ПАСЬЯНС) предложен Б. Шнайером в 1999 г. Шифр до безумия красив и я не понимаю, почему на Хабре его еще никто не осветил. Неужели никто не читал «Криптономикон» Стивенсона? Собственно после прочтения книги не могу пройти мимо сего чуда.

Из теории, это поточный шифр с обратной связью по выходу. Из поточности следует, что каждому символу изначальной последовательности будет соответствовать символ зашифрованной. Для тех, кто не знает, к примеру, существуют еще блочные шифры, в них шифрование происходит блоками (несколькими байтами или символами). Далее существует очень много видов сцепления блоков текста и так называемой гаммы (некой случайной секретной последовательности). В данном случае используется обратная связь по выходу, т.е. каждый символ гаммы изменяет состояние гаммы.



Шифрование


Шифрование производится крайне легко. Имеются 2 последовательности:
  1. DO NOT USE PC
  2. AD JEN MWD OI

1 — текст, который необходимо зашифровать. 2 — гамма (о ее генерации ниже). Все что необходимо, это перевести текст в цифры и разбить текст по 5 букв (это криптографический этикет). Если букв меньше, то они заполняются неким условным символом, например х.
  1. 4|15|14|15|20 21|19|5|16|3
  2. 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.
  1. 5|19|24|20|8 8|16|9|5|12
  2. 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
карма
37,0
рейтинг 0,0
Пользователь
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (38)

  • 0
    Я может невнимательно прочитал, но где используется обратная связь по выходу?
    • 0
      Цитата оригинального текста автора.
      Solitaire is an output-feedback mode stream cipher.


      Насколько я могу судить, обратная связь по выходу затрагивает только изменение гаммы, непосредственно после генерации каждого символа ключевой последовательности. У меня это отражено во фразе:
      Далее шаги с 1 по 5 повторяются n раз.
      • +1
        Все, вспомнил, что такое обратная связь по выходу. :)
        А зачем на пятерки символов бить? В этом есть какой-то смысл?
        • 0
          Довольно трудный вопрос, но автор пишет, что таков этикет =)
          • –1
            Традиция, если посмотреть в оригинал.
        • +7
          Телеграфу так удобнее.
      • 0
        Если посмотреть, то алгоритм генерации гаммы — генератор псевдо-случайной последовательности, инициализируемый начальным состоянием (состоянием колоды в начале). После этого генератор работает в автономном режиме генерации гаммы, которая складывается по модулю с входным потоком.
        Тогда получается, что данную схему можно рассматривать и как просто поточный шифр, и как поточный шифр с обратной связью по выходу (внутреннее состояние генератора — состояние колоды — и есть та самая обратная связь).
  • +18
    Где безумная красота?
    или у меня просто нет чувства прекрасного?..
    • +1
      Эх, абстрагируйтесь от компьютерных будней, переставьте себе средневековье во дворе и погони за колодой карт, которую все боятся перетасовать)

      Или как во время войны высылают подарочек в виде колоды карт, и никто даже не может предположить, что это инструмент тайного шпионажа.

      По-моему красиво.
  • +5
    > Подобные алгоритмы можно дешифровать только грубой силой (перебором). Различные аналитические методы к нему практически не применимы.
    И есть доказательство? Или это вам так кажется?
  • –2
    Приведите оценки временных затрат на криптоанализ для современных видеокарт.
    • +3
      Каждое сообщение, содержащее «Доброго времени суток, уважаемый...» — это утечка 29-32 символов гаммы.
      Где анализ устойчивости алгоритма к дешифровке?
    • +1
      Вопросом анализа алгоритма на криптоустойчивость я пока не задавался, думаю это отдельная статья. Пока у меня был всего лишь один вечер, на разбор и составление приложения.
      Если говорить о грубой силе, то придется перебрать 54! (что-то около 10^70) перестановок колоды карт и это при условии, что генерация гаммы происходит именно по этим 5 шагам.
      Если каждый раз генерировать новую гамму, то попытка аналитики тоже может потонуть.

      Здесь нужно действовать как-то по другому… Буду думать.
    • –1
      Это же очень похоже на шифр Вижинера, а он довольно легко взламывается на обычном компьютере при большом количестве шифротекста. В своё время писал программку для взлома целыми тремя способами — замечательно вскрывался текст длинной от 500 символов (в некоторых случаях от 50).
      • +1
        Ну я бы не стал их сравнивать. Слабость шифра Вижинера в его ключе, точнее в повторении ключа. Да и использование стандартного алфавита это же вообще самоубийство. Его взламывали вручную, не говоря уже о машинном взломе… Хотя я возьму на заметку и попробую в недалеком будущем написать маленькую программку для взлома этого шифра.
      • +1
        Здесь генерируется ключевая последовательность с куда большим периодом чем длина исходного ключа. И Виженера вы не взломаете если длина ключа будет равна длине сообщения.
      • +2
        В шифре Виженера гамма периодическая (причём с малым периодом), а здесь, похоже, что нет. Так что сравнивать их нельзя.
        • 0
          Здесь тоже периодическая, она же полностью зависит от состояния колоды, а состояний конечное число (хоть и очень много).
          • 0
            Это само собой. Имелась в виду периодичность на протяжении сообщения. А так, наверное, все генераторы гамм периодические. Истинно случайные числа, к сожалению, получать только вычислениями мы не умеем.
  • 0
    Выбором для русского языка 34 карт вместо 54 автор понизил стойкость ключа с 241 бит до 128 бит ;(
    Пу негодуе
    • 0
      Можете предложить альтернативу? Я не видел колоды из 66 карт.
      • 0
        Вариант просто оставить те же 52+2 карты, но использовать арифметику по модулю 32 при складывании (вычитании) текста с шифтопотоком тут не подходит — он не трансформирует алфавит в алфавит с равнораспределенной вероятностью. Т.е. буква «А» при сложении с равнораспределенным случайным числом от 1 до 52 по модулю 32 ляжет в распределение [«Б»… «Б»+20] с вероятностью в 2 раза больше чем в [«Б»+21… «Б»+30, «А»] (у нас нет карты с номером 0), а это прямая предпосылка для частотного анализа.

        Оставить модуль 52 для сложения возможности нет — алфавита не хватит.

        Как вариант — сделать какое-то взаимооднозначное преобразование текста из 32-х символьного алфавита в 26-ти символьный, применить оригинальный шифр, и при необходимости применить ещё раз взаимооднозначное преобразование обратно в 32-х символьный алфавит (уже другое, т.к. первое в обратном направлении в общем случае работать не будет). Придумать такое кодирование не составляет проблемы — пытливый читать может попробовать решить эту задачу в качестве упражнения )
        • +1
          Не знаю, на мой взгляд тогда этот шифр становится уже менее ручным, если преобразовывать как минимум в латиницу и обратно.
          Одного понять не могу, зачем было так подробно описывать итак понятное, про не соотносимость числа 52 и 32, кэп?
        • 0
          Арифметическое кодирование.
      • –1
        Большие и маленькие буквы, не?
    • 0
      Обидно, конечно, но «Пасьянс» вряд ли создавался для секретов, которые требуют слишком уж высокой стойкости. Для его целей — хватит, наверное. Или это существенное снижение?
      • 0
        Ну, у этого шифра и так не много достоинств, его реальная стойкость гораздо ниже, например, возможная невысокая величина периода для части ключей, очевидные неравномерности в распределении символов в шифропотоке (так, вероятность в нем встретить последовательность 1,1,1 вовсе не равна 1/52**3)…

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

        ЗЫ. У меня там ошибочка — 54! это около 237 бит, один десятичный знак пропустил )
        • –1
          Ради интереса займу себя задачкой, насколько «пасьянс» сглаживает частоту встречаемости символов.
          Насчет периодов Вы явно поторопились. Я генерировал длинные последовательности гаммы и никакого периода не обнаружил.
          • 0
            Увы, криптоскойкость на глаз не проверяется — Вы не обнаружите коротких периодов даже у тех алгоритмов у которых они точно есть (точнее, бывают). Тут математика нужна, а не игры с генерацией.
  • –4
    Спасибо, за то, что не написали внизу статьи под какой лицензией исходники…
    • –2
      В исходниках написано. Или кто-то планирует их тут же скидывать на торренты без открытия файла?
      • –4
        рукалицо
  • –2
    Существует куча настоящих шифров, описание и анализ которых хоть кому-то в современном мире могут пригодиться. Переключитесь лучше на них.
  • +1
    Разве использование программы для данного шифра не нивелирует всю его красоту? )
  • –2
    К сожалению, последовательность состояний колоды даже близко не проходит через все 54! Я пробовал экспериментировать на маленьких колодах, так циклы получались совсем короткими. И в том виде, как шифр описан в «Криптономиконе», он не является обратимым, у них там какая-то проблема когда джокер оказывается верхней или нижней картой (подробностей уже не помню, но исправить легко).
    Основная проблема этого шифра в том виде, как его предполагалось применять — он совершенно неустойчив к мелким сбоям. Достаточно один раз на шаге 4 сбиться в подсчете карт (или неправильно проинтерпретировать значение карты), и продолжение сообщения окажется информационным мусором. Шпиону во время WWII было бы очень непросто пользоваться подобным генератором.
    • +1
      Это проблемы всех шифров. И если вам интересно, возьмите любой учебник по истории криптографии. То, чем «шпионы» пользовались в военное время вас немало удивит. Карты это еще цветочки.

      Помимо самого процесса шифровки-дешифровки, основная проблема всего мероприятия — это все как-то потом передать. И так как ценность информации ограничена во времени, то все надо делать как можно быстрее.
      Быстро зашифровать, быстро передать и использовать те инструменты криптографии, на взлом которых уйдет времени больше, чем будет жить зашифрованная информация. Карты неплохой выбор.
      • 0
        Не совсем. У этого шифра проблема в том, что исходное состояние ключа (колоды, переданной под столом) при дешифровке меняется необратимо. Конечно, если код брать из колонки «бридж» этой проблемы нет, но если колоду передали физически? Придется на всякий случай переписать последовательность карт — а это уже некрасиво.
        • +1
          Можно предварительно договориться о начальном состоянии ключа в зависимости от времени суток, фазы луны и времени года. Пики-трефы-бубны-черви, 6789 вперед колоды и прочее. Это не проблема. Шифры низкой стойкости одноразовые, как правило.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.