Как стать автором
Обновить

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

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


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

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

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

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

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

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

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

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

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