LINUX.ORG.RU
ФорумTalks

Перестановочный шифр

 ,


0

2

Хочу обсудить криптостойкость перестановочного шифра, в котором переставляются отдельные биты. Предположим, что данные делятся на блоки достаточно большой длины, скажем 256 бит (для сравнения в DES блоки перестановок 64 бита) и все биты переставляются в соответствии с некой таблицей, которая и будет ключём шифрования. При этом ключ обязан соответствовать двум требованиям:

1. ни один бит не остаётся на прежнем месте
2. длины переходов неодинаковые, например простые сдвиги запрещены

В идеале такой ключ будет генерироваться аппаратно на основе физически случайных процессов и программной проверки соответствия требованиям.

Интересно послушать мнение разбирающихся в криптографии и в криптоанализе людей о криптостойкости такого алгоритма. Например, на сколько этот алгоритм стоек к криптоанализу по известному отрывку исходного сообщения?

Бонусный вопрос. На сколько возрастёт крипкостойкость такого алгоритма если помимо перестановок ещё и вставлять дополнительный случайный мусор, до перестановок? То есть увеличивать размер блока (а значит и ключа), скажем на четверть, за счёт добавления мусорных битов в заранее заданное и нескрываемое место исходного блока, например в конец, в начало или после каждого четвёртого бита полезной информации. Думаю, что куда именно вставлять мусор не важно, ведь он всё равно перемешается неизвестным для атакующего способом. Очевидным воздействием добавления случайного мусора будет так же случайное изменение соотношения нулевых и единичных битов между исходным и зашифрованным сообщениями. Без такого мусора количества нулевых и единчных битов сохранятся, что наверняка не есть хорошо с точки зрения криптоанализа.

★★★★★

По поводу мусора, сейчас применяют алгоритмы с лавинным эффектом. Изменение одного бита исходного сообщения приводит к изменению двух и более битов получаемого сообщения.

foxy_ant ()
Ответ на: комментарий от foxy_ant

У таких алгоритмов наверняка есть свои криптографические слабости. В рамках данной темы меня интересует лишь описанный мной алгоритм.

bbk123 ★★★★★ ()
Ответ на: комментарий от Miguel

Как его можно практически использовать для криптоанализа? У каждого из 256-и бит в блоке есть до 256 вариантов перемещения. То, что мы исключили один из них (перемещение на нулевую длину) никак не ослабляет наш алгоритм. Наоборот, это исключает вероятную возможность того, что таких нулевых перемещений будет слишком много и результат шифрования будет слишком близок к исходному сообщению, что облегчит его полное или частичное понимание до расшифровки.

bbk123 ★★★★★ ()
Ответ на: комментарий от bbk123

То, что мы исключили один из них (перемещение на нулевую длину) никак не ослабляет наш алгоритм.

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

В «Энигме» что-то в этом роде было, и Блетчли-парк, естественно, воспользовался.

Miguel ★★★★★ ()
Последнее исправление: Miguel (всего исправлений: 1)
Ответ на: комментарий от Miguel

Если никак не ограничивать варианты перестановок, то общее число таких вариантов будет n!, где n - количество переставляемых элементов, в нашем случае 256. 256! - это невероятно большое число, даже половина которого тоже невероятно большая. К тому же, как ты пришёл к выводу о «больше половине» исключений? По-моему их будет достаточно мало, в процентном соотношении. Всего лишь 256 вариантов, где хотя бы один бит остаётся на своём месте. По сравнению с 256! (256 * 255 * 254 * ... * 2) это капля в море, даже меньше. Для примера гораздо меньшее чисто 100! приблизительно равно 9.332621544 * 10^157 что очень много.

bbk123 ★★★★★ ()
Ответ на: комментарий от bbk123

Всего лишь 256 вариантов, где хотя бы один бит остаётся на своём месте.

Хотя нет, это количество вариантов, когда лишь один бит остаётся на своём месте. Хорошо, мне лень считать, пусть всего будет половина, хотя на самом деле гораздо меньше. Всё равно, даже половина от 256! - это очень много.

bbk123 ★★★★★ ()

Ну, начнём с того, что распределение бит будет соответствовать распределению бит в оригинальном сообщении. То есть, просто глядя на соотношение нулей и единиц можно будет судить об исходном тексте, например, сжат он, а, может, это Юникод или ASCII текст на английском.

Про «ничто не перестанавливаетсяв себя», как справедливо замечено, это сокращает число вариантов. Я рекомендую прочитать про криптоанализ Энигмы, где буквы тоже в себя никогда не заменялись. Там, конечно, другая проблема, но как иллюстрация годится. Неперестановка в себя выглядит, как раскрытие двух бит сообщения.

ivlad ★★★★★ ()
Ответ на: комментарий от bbk123

К тому же, как ты пришёл к выводу о «больше половине» исключений?

Если точнее, (1-1/e): https://en.wikipedia.org/wiki/Derangement

хотя на самом деле гораздо меньше

На самом деле, больше.

Хотя нет, это количество вариантов, когда лишь один бит остаётся на своём месте.

ЧТО???

Одних только вариантов, где ПЕРВЫЙ бит остаётся на своём месте, уже 255!, то есть 1/256 от общего количества.

Miguel ★★★★★ ()
Последнее исправление: Miguel (всего исправлений: 1)
Ответ на: комментарий от ivlad

Угу, а если использовать один и тот же ключ для каждого блока из 8 символов… в общем, раскроют такой код очень быстро, можно даже без компьютера обойтись, если хоть примерно представлять, чего можно ожидать в сообщении.

Miguel ★★★★★ ()
Ответ на: комментарий от gremlin_the_red

Вообще, все подстановочные шифры (а это именно такой) ломаются простым статистическим анализом.

gremlin_the_red ★★★ ()

Я мало что понимаю в криптографии, но…

Предположим, что данные делятся на блоки достаточно большой длины, скажем 256 бит (для сравнения в DES блоки перестановок 64 бита) и все биты переставляются в соответствии с некой таблицей, которая и будет ключём шифрования.

Если таблица перестановок будет одинаковой для всех блоков и можно насобирать много таких зашифрованных блоков, то:

  • Можно будет легко находить одинаковые блоки.
  • Можно будет находить биты, меняющиеся чаще или реже. Биты, неким образом связанные друг с другом. Например, если в передаваемых данных есть фиксированный «magic number», то его будет легко найти, хоть и в «размазанном» по блоку виде. То есть можно примерно угадать структуру исходных данных, включая длины отдельных «полей».
  • С учётом предыдущего пункта, при наличии отрывка плейнтекста можно попробовать понять из чего этот отрывок состоит (если мы говорим про некие структурированные данные) и где он мог встречаться в известных блоках. И попробовать угадать часть таблицы перестановок.
  • Если это шифрование используется в клиент-серверном взаимодействии, и есть возможность наснифать и запросы к серверу и ответы от него, то можно попробовать их скореллировать друг с другом. И попробовать угадать логику работы протокола.

В общем, Do Not Roll Your Own Crypto!

im-0 ()
Ответ на: комментарий от ivlad

Ну, начнём с того, что распределение бит будет соответствовать распределению бит в оригинальном сообщении. То есть, просто глядя на соотношение нулей и единиц можно будет судить об исходном тексте, например, сжат он, а, может, это Юникод или ASCII текст на английском.

Врядли, но как раз для этого я хочу добавлять мусорные биты.

Про «ничто не перестанавливаетсяв себя», как справедливо замечено, это сокращает число вариантов. Я рекомендую прочитать про криптоанализ Энигмы, где буквы тоже в себя никогда не заменялись. Там, конечно, другая проблема, но как иллюстрация годится. Неперестановка в себя выглядит, как раскрытие двух бит сообщения.

Сокращение копеечное, а про раскрытие двух бит я вообще не понял. Что за биты и как они раскрываются?

Конкретно сколько вариантов останется если исключить неперестановки любых битов. Всего всех перестановок 256!. Количество возможных нулевых перестановок 255!. Разница 256! - 255! = (256 * 255!) - 255! = 255 * 255! то есть всё равно over до хрена.

Энигма не занималась перестановками битов в блоке, она вообще занималась не перестановками, а заменами букв. Изъян Энигмы заключался в запрете на замену буквы саму на себя. Именно это позволяло взломать её код по открытому куску текста, который немцы постоянно передавали в начале или в конце своих сообщений.

bbk123 ★★★★★ ()
  1. ни один бит не остаётся на прежнем месте

Именно так взломали enigma. Она тоже (физически) не могла кодировать символ самим собой. Что стало фатальным недостатком и позволило относительно быстрый взлом.

  1. длины переходов неодинаковые, например простые сдвиги запрещены

А это уже незначительные детали.

Дальше не читал.

beastie ★★★★★ ()
Последнее исправление: beastie (всего исправлений: 1)
Ответ на: комментарий от Miguel

Если точнее, (1-1/e): https://en.wikipedia.org/wiki/Derangement

Не очень понял откуда эта формула и что она вычисляет, но за статью о беспорядках спасибо.

На самом деле, больше.

Выше я показал, что останется 255 * 255! вариантов, что гораздо больше половины от всех 256! перестановок. И эта половина равна 0.5 * 256! = 0.5 * 256 * 255! = 128 * 255!

Хотя нет, это количество вариантов, когда лишь один бит остаётся на своём месте.

ЧТО???

Одних только вариантов, где ПЕРВЫЙ бит остаётся на своём месте, уже 255!, то есть 1/256 от общего количества.

Количество вариантов где хотя бы один бит остаётся на своём месте действительно равно 255!, но я говорил о количестве вариантов, когда лишь один единственный бит остаётся на одном месте.

bbk123 ★★★★★ ()
Ответ на: комментарий от bbk123

Количество возможных нулевых перестановок 255!

Нет. Это — количество перестановок, в которых ПЕРВЫЙ бит остаётся на месте. Есть и другие. Посмотри в википедию по ссылке.

Miguel ★★★★★ ()
Ответ на: комментарий от bbk123

Количество вариантов где хотя бы один бит остаётся на своём месте действительно равно 255!

Нет, не равно. Оно приблизительно равно 256!/e.

но я говорил о количестве вариантов, когда лишь один единственный бит остаётся на одном месте.

Таких всё равно овердохрена. Количество перестановок, где первый бит — единственный, остающийся на месте, будет — в соответствии с той статьёй — примерно равно 255!/e.

Miguel ★★★★★ ()
Последнее исправление: Miguel (всего исправлений: 1)

Настоящий взрыв мозга криптоаналитика даёт только цепочка шифров. Причём, пофиг, что в этой цепочке, всеми досмотренный стандарт или наколенное поделие

TooPar ()
Ответ на: комментарий от TooPar

Применение подобного перестановочного шифра (без дурацких ограничений) дважды вряд ли будет сильно лучше однократного.

Miguel ★★★★★ ()
Ответ на: комментарий от bbk123

Врядли, но как раз для этого я хочу добавлять мусорные биты.

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

torvn77 ★★★★★ ()
Последнее исправление: torvn77 (всего исправлений: 1)
Закрыто добавление комментариев для недавно зарегистрированных пользователей (со score < 50)