28563

Однонаправленные функции, построение однонаправленных функций с секретами

Доклад

Информатика, кибернетика и программирование

Обозначим через QF сложность вычисления значения Fx для произвольного xX через QF1 сложность вычисления по произвольному yY значения x такого что Fx=y сложность вычисления понимается в стандартном смысле теории сложности. Сложность вычисления F такова что алгоритм ее вычисления реализуем на современной технике и выдает ответ за приемлемое время 2. Сложность вычисления F1 такова что алгоритм ее вычисления либо не реализуем на современной технике либо не дает ответ за приемлемое время. Что считать приемлемым...

Русский

2013-08-20

14.43 KB

5 чел.

41. Однонаправленные функции, построение однонаправленных функций с секретами.

В основе идей, изложенных в статье Уитфилда Диффи и Мартина Хеллмана  лежало понятие однонаправленной функции.

   Пусть X, Y - произвольные равномощные множества, F -  биективная  функция, отображающая X в Y. Обозначим через Q(F) - сложность вычисления значения F(x) для произвольного xX, через Q(F-1) - сложность вычисления по произвольному yY значения x, такого, что F(x)=y (сложность вычисления понимается в стандартном смысле теории сложности).

    В данных терминах будем говорить, что функция F является однонаправленной, если Q(F-1) много больше Q(F). Как видно, данное определение не является достаточно строгим. Под термином «много больше» можно подразумевать весьма разные понятия, например то, что вычисление F имеет полиномиальную сложность, а F-1- экспоненциальную.

Для того, чтобы под понятием однонаправленная функция понимался вполне конкретный класс объектов считают, что под термином «много больше», понимается следующее:

1.   Сложность вычисления F такова, что алгоритм ее вычисления реализуем на современной технике и выдает ответ  за приемлемое время

2.   Сложность вычисления F-1 такова, что алгоритм ее вычисления либо не реализуем на современной технике, либо не дает ответ за приемлемое время.

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

На момент опубликования статьи авторы не имели конкретной системы ЭЦП и по этой причине их система ОРК повисла в воздухе, так как в ней не решался вопрос аутентификации отправителя сообщения. Такое решение появилось значительно позднее  - в 1984 году. Пока же авторы предложили еще одну абстрактную схему с использованием так называемых однонаправленных функций с секретом (trapdoor one-way function). Строгое определения однонаправленной функции с секретом дать весьма затруднительно.

Попробуем сформулировать его следующим образом.

    Однонаправленной функцией с секретом S называется  биективная функция F отображающая произвольное множество X в множество Y, зависящая от параметров T1,...,TL  и обладающая следующим свойствами: 

1.     Существует некоторая функция S, зависящая от параметров T1,...,TL 

2.   По виду функции F значение функции S для конкретных параметров T1,...,TL  не восстанавливается 

3.   Сложность вычисления значения F-1(y)  yY при знании значения S(T1,...,TL) не превосходит сложности вычисления прямого преобразования  F 

4.   Сложность вычисления преобразования F-1 без знания значения S(T1,...,TL) много больше сложности вычисления прямого преобразования F. 

     Иными словами, без знания дополнительной информации о функции F она является однонаправленной, при наличии некоторой дополнительной информации (которую нельзя получить по функции F) обратное преобразование эффективно вычисляемо.

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


 

А также другие работы, которые могут Вас заинтересовать

80226. Социальный статус 41.5 KB
  Социальная мобильность В системе стратификации индивиды или группы могут перемещаться с одного уровня слоя на другой. Этот процесс называется социальной мобильностью. Социальное неравенство предполагает различия в распределении благ и ответственности а социальная стратификация – структурированную систему неравенства социальная мобильность проявляется в движении индивидов или групп от одного социального статуса к другому. Вертикальная мобильность – изменение положения индивида которое вызывает повышение или понижение его социального...
80227. Технология создания видеофильма. Линейный и нелинейный монтаж 60 KB
  Снимаемый или съемочный кадр несколько длиннее того который будет виден на экране после монтажа фильма этот кадр называют монтажным. План составляется после тщательного ознакомления со всем снятым материалом и определения основной концепции монтажа фильма отсюдато название: план монтажа фильма. она является лишь элементом упорядочивающим готовый но еще сырой материал раньше всего в процессе монтажа фильма. Длинным может быть рабочий материал для просмотра или хранения в архиве а фильм должен быть кратким лаконичным лемким по...
80228. Аудио форматы на DVD 405.5 KB
  Аудио мир захвачен CD благодаря их высокой практичности и низкой цене а видео переходит от VHS кассет на DVD. Но музыкальная индустрия и DVD Forum предпочитают универсальный формат они желают продавать наши любимые альбомы на DVD так и появился формат DVD аудио. С технической точки зрения DVD имеет больший объем чем CD.
80229. Современные форматы видео 988.5 KB
  Аналоговый видеосигнал включает в себя несколько различных компонентов, объединенных в единое целое. Такой составной видеосигнал малопригоден для оцифровки. Предварительно его следует разделить на так называемые базовые компоненты. Обычно компоненты представляют собой три различных сигнала, соответствующие определенной модели представления цветового пространства
80230. Алгоритм сжатия видео. Основные особенности MPEG 160 KB
  Сначала все цветовое пространство кадра преобразуется из RGB в YCbCr. Необходимость этого преобразования заключается в том, что глаз более чувствителен к яркости цвета, чем к его оттенку. Y - это величина яркости цвета, а Cb и Cr - цветовые величины, определяющие оттенок и насыщение цвета (они определяют количество синей и красной составляющих в цвете).
80231. СРЕДСТВА МУЛЬТИМЕДИА 94.5 KB
  Мультимедиа это интерактивные системы обеспечивающие работу с неподвижными изображениями и движущимся видео анимированной компьютерной графикой и текстом речью и высококачественным звуком. Появление систем мультимедиа безусловно производит революционные изменения в таких областях как образование компьютерный тренинг во многих сферах профессиональной деятельности науки искусства в компьютерных играх и т. Появление систем мультимедиа подготовлено как с требованиями практики так и с развитием теории.
80232. Системи мультимедіа 543.5 KB
  Цифровий відеозапис забезпечує помітно кращу якість кадру, чіткіше зображення і кращу передачу кольорів. Більш того, цифрову копію відеофільму не відрізниш від оригіналу, що робить редагування і обробку зображення, навіть на рівні любителя, значно простіше, а якість - вищим в порівнянні з аналоговою відеотехнологією.
80233. Планування в організації 13.07 MB
  Планування в організації. Сутність планування як функції управління Щоб спільні зусилля співробітників організації були успішними вони повинні знати що від них очікується. Для цього необхідно: сформулювати цілі до яких прагне організація; визначити шляхи досягнення встановлених цілей; на підставі цього поставити задачі перед підрозділами організації та конкретними виконавцями. Планування – процес визначення цілей організації та прийняття рішень щодо шляхів їх досягнення.
80234. Командні ролі 42 KB
  Командні ролі описують типову схему конструктивної поведінки людини в команді. Не слід плутати командні ролі з типом особи, під яким розуміють переважний спосіб взаємодії з навколишнім світом або спрямованість психологічної енергії. Командна роль, яку людина переймає на себе часто залежить від складу і стану команди