Введение в криптографию
[an error occurred while processing this directive]

Новые направления


В 1983 году в книге ``Коды и математика'' М.Н.Аршинова и Л.Е.Садовского (библиотечка ``Квант'') было написано: ``Приемов тайнописи - великое множество, и, скорее всего, это та область, где уже нет нужды придумывать что-нибудь существенно новое.'' Однако это было очередное большое заблуждение относительно криптографии. Еще в 1976 году была опубликована работа молодых американских математиков У.Диффи и М.Э.Хеллмана ``Новые направления в криптографии''1), которая не только существенно изменила криптографию, но и привела к появлению и бурному развитию новых направлений в математике. Центральным понятием ``новой криптографии'' является понятие односторонней функции (подробнее об этом см. главу ).

, обладающая двумя свойствами:

а) существует полиномиальный алгоритм вычисления значений ;

б) не существует полиномиального алгоритма инвертирования функции (т.е. решения уравнения относительно , точное определение см. на стр. ).

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

Еще одним новым понятием является понятие функции с секретом. Иногда еще употребляется термин функция с ловушкой. Функцией с секретом называется функция

, зависящая от параметра и обладающая тремя свойствами:

а) существует полиномиальный алгоритм вычисления значения для любых и ;

б) не существует полиномиального алгоритма инвертирования при неизвестном ;

в) существует полиномиальный алгоритм инвертирования при известном .

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




- Начало -  - Назад -  - Вперед -


[an error occurred while processing this directive]