Математические основы защиты информации. Ишмухаметов Ш.Т - 69 стр.

Методы, основанные на задаче дискретного логарифмирования                     70

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


4.3. Односторонние функции. Хеш-функции
Односторонняя (однонаправленная) функция (one way function) - это
отображение X       →    Y , где X       и Y        - произвольные множества,
удовлетворяющее следующим условиям:

  1. Для каждого x из области определения функции f легко вычислить
     f (x). Понятие "легко"обычно означает, что существует алгоритм,
     вычисляющий функцию f (x) за полиномиальное время от длины
     аргумента x.

  2. Задача   нахождения      прообраза         x     для   произвольного     y,
     принадлежащего       области      значений       функции    f,     является
     вычислительно      сложной     задачей.    Последнее   означает,   что   не
     существует алгоритма, вычисляющего существенно быстрее, чем
     алгоритм полного перебора.

      Пример 1. Задача вычисления простых множителей натурального
числа n (факторизация N) является односторонней функций – самый
быстрый известный алгоритм факторизации – метод решета числового поля
имеет субэкспоненциальную верхнюю оценку времени своей работы. На
вычислительной сложности решения этой задачи построен один из самых
известных асимметричных методов криптографии - метод RSA.