Теория и практика защиты программ
Общие определения
В качестве одного из основных математических объектов в данной работе используются односторонние функции, то есть вычислимые функции, для которых не существует эффективных алгоритмов инвертирования. Необходимо отметить, что односторонняя функция - гипотетический объект, поэтому называть конкретные функции односторонними математически некорректно. Впервые такую гипотетическую конструкцию для конкретного криптографического приложения, - открытого распределения ключей, предложили У.Диффи и М. Хеллман в 1976 г. [DH]. Они показали, что вычисление степеней в мультипликативной группе вычетов над конечным полем является простой задачей с точки зрения состава необходимых вычислений, в то время как извлечение дискретных логарифмов над этим полем – предположительно сложная вычислительная задача.
Неформально говоря, для двух независимых множеств X и Y функция f:X®Y называется односторонней, если для каждого xÎX можно легко вычислить f(x), в то время как почти для всех yÎY вычислительно трудно получить такой xÎX, что f(x)=y, при условии , что такой x
существует.
Все формальные определения односторонних функций в терминах теории сложности вычислений даны в приложении.
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий