Теория и практика защиты программ

         

Общие определения


В качестве одного из основных математических объектов в данной работе используются односторонние функции, то есть вычислимые функции, для которых не существует эффективных алгоритмов инвертирования. Необходимо отметить, что односторонняя функция - гипотетический объект, поэтому называть конкретные функции односторонними математически некорректно. Впервые такую гипотетическую конструкцию для конкретного криптографического приложения, - открытого распределения ключей, предложили У.Диффи и М. Хеллман в 1976 г. [DH]. Они показали, что вычисление степеней в мультипликативной группе вычетов над конечным полем является простой задачей с точки зрения состава необходимых вычислений, в то время как извлечение дискретных логарифмов над этим полем – предположительно сложная вычислительная задача.

Неформально говоря, для двух независимых множеств X и Y функция f:X®Y называется односторонней, если для каждого xÎX можно легко вычислить f(x), в то время как почти для всех yÎY вычислительно трудно получить такой xÎX, что f(x)=y, при условии , что такой x

существует.

Все формальные определения односторонних функций в терминах теории сложности вычислений даны в приложении.




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