Хэш функции на асимметрике
Отделено из темы про Keccak
|
||||||||||||||||||||||||||
|
||||||||||||||||||||||||||
Нормы пользования. Некоторые права на материалы сайта защищены по условиям лицензии CreativeCommons. Движок
openSpace 0.8.25a и дизайн сайта © 2006-2007 Vlad "SATtva" Miller.
|
||||||||||||||||||||||||||
комментариев: 9796 документов: 488 редакций: 5664
Большой список причин. Затрудняюсь грамотно изложить их все. Навскидку, да надо учитывать алгебраические свойства, но необязательно только для композиций функций (опять же, вы под этим, скорее всего понимаете явно что-то своё, нацеленное на ваши попытки решений). Например, RSA строго не сводится к проблеме факторизации (но это очень глубокий уровень, его в приземлённой теоретической криптографии даже не рассматривают), а криптосистема Рабина — сводится строго. Во-вторых, есть всякие, пусть и неэффективные, но методы поиска решений трудной задачи и не так тривиально их можно учесть. В третьих — любой различитель от RO, каким-бы безобидным он не был, затрудняет доказательство сложности. Проще доказать, что функция неразличима от RO, а затем, что конструкция на основе RO стойкая.
Разумеется, из случайного оракула можно построить тривиально взламываемую конструкцию. Нужно доказать минимум две вещи:
2. Конструкция стойкая, если выполняется п.1. При этом п.2. доказывается отдельно от п.1.
Видимо, недостатки аналогов линейных конгруэнтных генераторов таким путём не исправить, т.к. не соблюдается п.2.
Вход и выход блочного шифра всегда будут биективными, какой бы ключ не подавали. Иначе бы нельзя ничего расшифровать обратно, это бы вообще не было бы блочным шифром. Ключ лишь задаёт внутреннее состояние раундовых функций. Оно эффективно равно размеру блока. Поэтому ключ выбирают обычно равным, но можно и большим, в теоретическом пределе стойкость от этого не повысится, но для практики это м.б. удобнее.
Нет. Не про это. А про то, что получится не просто идеальный шифр, а образующий квазигруппу по отношению к ключу и открытому тексту, что весьма нетривиально. Если сопоставить упорядоченное множество всех ключей от {0x00…0} до {0xFF…F}, упорядоченному таким же образом множеству всех блоков открытых текстов, то результат можно будет вписать в матрицу всех возможных блоков шифртекстов, каждый столбец и каждая строка которой будут перестановками, причём каждый шифртекст будет лишь единожды встречаться в каждой строке и в каждом столбце. Такие структуры на основе симметрики создавать пытались, также как и делать на их основе асимметричное шифрование и всякие нетривиальные протоколы. Вот только обеспечить не только создание, но и стойкость самой такой структуры оказалось весьма нетривиальной задачей. Может это и станет когда-нибудь прорывом в криптографии, но пока это очень далеко от мэйнстрима.
Таким, что DH выполняется в массе алгебраических структур, включая и полугруппы, и квазигруппы, и объекты тропической алгебры, правда какие там определённые условия конкретно для квазигрупп и прочей экзотики, надо каждый раз смотреть индивидуально. Были авторы, которые пытались раздуть сеть Файстеля из симметричных преобразований хитрого вида до квазигруппы приемлемого порядка и на этой основе сконструировать асимметрику. Нельзя сказать, что это принципиально невозможно, но пока выглядит слишком ненадёжно и фантастически.