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

ни один бит не остаётся на прежнем месте

Это уже слабость.

Почему?

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

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

Потому что это ясное, простое для понимания и использования, ограничение алгоритма.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ЧТО???

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

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

Криптостойкость очень низкая, криптостойкость к открытому тексту просто нулевая.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Если точнее, (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!, но я говорил о количестве вариантов, когда лишь один единственный бит остаётся на одном месте.

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

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

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

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

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

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

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

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

Дык в цепочке должны быть разные алгоритмы.

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

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