Криптография - статьи




О современной криптографии - часть 6


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

Ввиду того, что задача определения ключа может быть представлена как задача решения некоторой системы нелинейных уравнений в конечном поле, для криптографии представляют значительный интерес методы решения систем того или иного вида и оценки их сложности. С примерами криптографических исследований можно познакомиться по многочисленным работам, связанным с изучением свойств преобразования DES, которые опубликованы в последние 20 лет в Procedings of Crypto, Procedings of Eurocrypt, Journal of Cryptology.

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

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

За последние годы получил значительное развитие раздел теоретической криптографии, занимающийся изучением вопросов существования тех или иных криптографических объектов с доказуемыми (при некоторых дополнительных предположениях) оценками стойкости. В круг интересов этого раздела криптографии входят вопросы построения и обоснования свойств таких криптографических понятий как "односторонняя функция", псевдослучайный генератор, криптографический протокол (cryptographic protocol), в частности, протокол доказательства с нулевым разглашением (zero-knowledge proof protocol) и т. п. Эти понятия изучаются с точки зрения абстрактных позиций сложности вычислений.




Содержание  Назад  Вперед