Идеальный шифр

Юрий Решетов

Определенно в обществе существуют идолы и идолопоклонники. Авторитет какого либо деятеля может быть непререкаемым. Именно в таком положении оказалась криптография, благодаря авторитету Клода Шеннона. В своем докладе "Математическая теория криптографии" от 1 сентября 1945 г. (в данное время рассекречен), он посвятил всего лишь несколько строк матричной системе. Цитирую:

"Матричная система .

Имеется один метод подстановки n-грамм, который заключается в применении к последовательным n-граммам некоторой матрицы, имеющей обратную . Предполагается, что буквы занумерованы от 0 до 25 и рассматриваются как элементы некоторого алгебраического кольца . Если к n-грамме сообщения применить матрицу aij то получится n-грамма криптограммы:

Матрица aij является ключом, и расшифровка выполняется с помощью обратной матрицы . Обратная матрица будет существовать тогда и только тогда , когда определитель |aij| имеет обратный элемент в нашем кольце."

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

Наличие в "криптограмме" ("шифрограмме") положительной избыточности - это вовсе не криптография, а всего лишь шенноновский дебилизм.

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

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

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

Я бы посоветовал янки, заново засекретить доклад Клода Шеннона и более не рассекречивать, дабы не позориться перед остальными этим еще одним лауреатом Нобелевской премии из США, не владевшим математическим аппаратом.

Хорст Фейстель в своей "Криптография и компьютерная безопасность" высказывает мнение, что шифр Вернама (или его еще называют "одноразовым блокнотом") является невскрываемым. Но по причине того, что для практического применения необходимо иметь значительный объем данных для ключа, полагает, что его использование предпочтительно лишь в целях весьма повышенной секретности.

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

Остановимся на этих двух положениях:

Криптографическая система не должна оставлять следов для статистических исследований по Шеннону.
Любой ключ должен быть "подходящим" по Фейстелю.

Если всего эти два условия, то идеальная криптографическая система уже создана. Причем это матричная система. А алгебра матриц, в отличие от статистики, то самое слабое место, которое Клод Шеннон старался обойти краткими оговорками. С какой это стати матрица должна быть ключом, даже если Шеннону так учудилось?

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

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

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

? B ? D E F G ? I J

Начитавшись Шеннона, он предположит, что полная последовательность должна быть:

А B С D E F G H I J

Пусть предполагает! Ведь дуракам, особенно тем, что абсолютно полагаются на авторитетов, закон не писан. Мы же сделаем ключ немного иным, чтобы полная последовательность скрываемая нашим шифром была, например такой:

x B Z D E F G а I J

И все.

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

Программа, которую я создал для идеальной криптографии называется "Панацея". В ее основе линейные уравнения с квадратной матрицей 256x256. Результирующий столбец содержит 247 байт исходного сообщения и 9 байт ключа, на выходе соответственно тоже блоки информации по 247 байт. Естественно, что ключ подойдет любой, а восстановит исходное сообщение только оригинальный. Поэтому никакие брутфорсы тут не помогут: система без ключа неразрешима и детерминированная машина А. Тьюринга не сможет остановиться. Но проблема многих шифров, в т.ч. и Вернама в том, что если потенциальный хакер поимеет возможность ознакомиться и с исходным текстом и с шифрограммой, то ключ будет им вскрыт. Чтобы избежать подобного инцидента, помимо решения линейных уравнений, также применяется и предварительное перемешивание данных по ключу. (Подстановки, которым Шеннон уделил столько времени, в отличие от перемешиваний - здесь мертвому припарки, поскольку система линейных уравнений остается неизменной, а меняются лишь коэффициенты). В результате чего, для выявления ключа хакеру хакеру все же придется перебирать варианты, но его задача из неразрешимой, станет решаемой за конечное время - есть с чем сравнить результат.

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

Принцип действия программы прост. Надо ввести 9 символьный пароль и повторить его ввод. После чего активизируются две кнопки: "Шифровать" и "Дешифровать". После нажатия на любую из них, система спросит имена исходного и шифрованного файлов (всплывающие файловые диалоговые окна) и деактивизирует соответствующую кнопку. После окончания (де)шифрования, кнопка становится опять активной.

Система написана на языке Java и распространяется в открытых исходниках по General Public License. Т.е. каждый желающий может не просто ознакомиться с алгоритмом, но и при желании, даже усовершенствовать его под свои нужды.

Загрузить программное обеспечение криптосистемы "Панацея" можно с сайта FREESOFT.RU . Исходники вложены внутрь архива (*.jar - это zip архивы) Panacea.jar в директории /panacea и имеют расширения *.java (текст лицензии там же).

Запуск программы выполняется из командной строки:

для запуска в графическом режиме:

javaw -jar Panacea.jar

или для запуска в консольном режиме:

java -jar Panacea.jar e sourcefile destfile password

java -jar Panacea.jar d sourcefile destfile password

где:
e - операция шифрования
d - операция дешифрования
sourcefile - исходный файл (для операции дешифрования - шифровка).
destfile - файл назначения (для операции шифрования - шифровка, для дешифрования - результат дешифровки).
password - ключ (пароль) 9 символов.

"Панацея" в версии 1.0 была идеальной для случаев, когда взломщик вообще ничего не знал о том, что зашифровано и тем самым лишался всякой возможности вскрыть криптограмму или получить ключ.
Однако, если взломщику удавалось получить исходный текст и шифрограмму, то ситуация менялась, поскольку появлялся шанс дедуктивно за некоторое число шагов или таких же попыток выявить ключ.
Чтобы лишить хакеров такой возможности, был немного усложнен алгоритм. Чтобы лишить хакера возможности выявить ключ, достаточно было вместо одиночного перемешивания исходного текста перед шифрованием добавить еще одно перемешивание после дешифрования. Взломщик хотя и теряет в этом случае возможность выявления ключа, но может восстановить порядок перемешивания и выявить алгоритм кодирования.
Чтобы лишить его и такой возможности, необходимо и достаточно всего лишь менять схему перемешивания от блока к блоку. Поскольку каждый блок информации будет таким образом уникально перемешан, то хакеру уже не с чем сравнивать (точнее есть с чем, но нет смысла).
Можно было бы еще применить различные методы, столь излюбленные криптоаналитиками, как то: подстановки, сдвиги, дополнительные перемешивания и т.д. Но все эти ухищрения по сути своей всего лишь попытки поменять местами козла, мартышку и косолапого мишку. Хуже того, во многих случаях ухищрения применять вообще не следует, поскольку они частенько привносят избыточность в информацию и позволяют взломщикам выявить более упрощенный алгоритм декодирования или же выявления ключей. Причем, разработчику алгоритма нередко бывает сложно заведомо оценить результаты: запутал он хакера или сам запутался.
Поэтому, решено было проанализировать основные признаки по которым взломщик может распутать схему шифрования. Основная информация для хакеров лежит в двух любых соседних блоках информации и если сравнивать исходные блоки и их шифрограммы, то можно выявить какую нибудь закономерность.
Поскольку это уже ясно, как дважды два, то помимо вышеизложенных ухищрений было решено применить и еще один прием, с помощью которого хакер если что и выяснит, то только то, что ему не нужно.
Чтобы понять принцип, то достаточно представить, что хакер имеет возможность следить, например, за сейфом в котором лежат ценности. Сейф закрывается кодовым ключом, который взломщику заранее неизвестен. Но, поскольку ключ один и тот же, то по результатам слежки, он рано или поздно его выявит. Усложним задачу, а именно введем запрет на замену ключа по тем или иным техническим причинам (единый ключ проще запомнить и проще использовать при многопользовательском доступе). Как выполнить эту задачу, т.е. не меняя одного постоянного ключа, скрыть возможность его выявления. Для этого поставим два сейфа. Первый кодируется с помощью единого ключа. А у второго код все время меняется. Внутрь первого кладется записка с кодом второго. Во первых, хакеру может и не предоставиться возможность следить за первым сейфом. А во вторых, ему нет смысла следить за вторым, т.к. там все время код меняется. Таким образом, если хакер лишен возможности следить за первым сейфом, а только за вторым, то любая попытка выявить код второго сейфа попросту бессмысленна
. Переведем задачу на язык криптографии, если хакер лишен возможности выявить ключ шифрования, но может анализировать шифрограммы и даже иногда и исходные тексты, то такой анализ лишен всякого смысла.
В "Панацее" версии 1.01 применен метод последовательных сейфов. Сначала алгоритм создает первый блок информации и заполняет его случайными числами. Затем случайным образом генерируются 9 чисел - индексов. Индексы записываются в открытом виде в начало шифрограммы. С помощью этих самых индексов, в блоке состоящем из случайных чисел выявляются еще 9 чисел, которые будут следующим ключом. А вот сам блок шифруется ключом пользователя и записывается далее в шифрограмму. Вся остальная информация шифруется уже полученным таким образом ключом.
Если хакеру что и достанется при попытках упростить путь к раскрытию схемы шифрования, то эта схема окажется для каждой шифрограммы уникальной. Все, что ему удастся выявить, так это всего лишь 9 случайных чисел из предыдущего блока.
Может на первый взгляд показаться, что 9 чисел ничего не могут дать хакеру. Но не стоит преуменьшать его возможности. Хотя блок всего один и не с чем сравнивать, но сделаем предположение, что хакер имеет возможность шифровать свою информацию и перехватывать шифрограммы в неограниченном объеме (иногда впечатление кажущейся надежности, настолько притупляет бдительность, что становятся возможными элементарные пренебрежения безопасностью. Многим даже в голову не придет мысль о потенциальном взломе, например, если есть некий канал, по которому информация передается в зашифрованном виде, причем о системе шифрования мало кто догадывается. Многие привыкли судить о других в мерках собственного невежества - мол если мне неведомо, то хакер вообще - дебил.). Предположим, что взломщик всетаки рано или поздно, но найдет какую нибудь лазейку (хотя криптоаналитик о ней может не догадываться, а когда узнает, будет слишком поздно) и выявит схему шифрования первого блока. Если ему это удастся, то можно считать, все секреты скрываемые данной схемой, перестанут быть тайной.
Потому, как схема эта вовсе не случайна. Чтобы лишить хакера и такой потенциальной возможности, в версии 1.01 решено было усложнить схему, добавлением еще одного промежуточного блока случайных чисел и случайного ключа. В этом случае, взломщик, анализируя последнее звено шифрования, будет выявлять предпоследнее. А поскольку схема предпоследнего звена уникальна для каждой шифрограммы, то он ее не сможет выявить в полном объеме - недостаточно разовой информации и по ней не доберется уже до ключевой схемы шифрования первого блока.

Ну, а что же дальше? Как многие наверное заметили, система с закрытым ключом. Переделать ее в систему с ключом открытым невозможно - она станет разрешимой. Но это не проблема. На самом деле можно создать алгоритм секретной передачи ключа.

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

Таким образом происходит обмен. Точнее будет происходить, т.к. готовая версия пока еще незакончена.

09 декабря 2004 г.