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) обратное преобразование эффективно вычисляемо.

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


 

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

562. Социальная политика в современных условиях 88 KB
  Цели, задачи и объекты социальной политики в Российской Федерации. Базовая система предпосылок концепции социальной политики. Социальная напряженность в обществе и ее зависимость от социальной политики государства. Социальное управление как средство реализации социальной политики.
563. Деятельность международных финансово-кредитных организаций 85.68 KB
  Европейский банк реконструкции и развития. Многостороннее агентство по гарантированию инвестиций. Международная ассоциация развития. Проблемы экономического роста, налогообложения, задолженности. Международный валютный фонд и всемирный банк.
564. Налоги и налогообложение 87.17 KB
  Налог по существу – отчуждение части созданного продукта в пользу государства, что вызвано объективной необходимостью создания материальной базы для содержания государства и выполнения возложенных на него функций.
565. Сбытовая политика фирмы 83 KB
  Понятия сбыта и товароведения. Подбор товаров для реализации и формирование оптимальных с транспортной точки зрения партий. Оформление сопроводительных документов (товарно-транспортные накладные, спецификации, сертификаты, упаковочные листы и т.п.), отгрузка и контроль за движением груза. Каналы распределения и их виды.
566. Устройство кузова пассажирского вагона 66 KB
  Конструкция кузова пассажирского вагона существенно отличается от кузова грузового вагона. Боковые продольные балки. Пакеты теплоизоляции. Монтаж котла отопления, калориферов, бака для воды и вентиляционного агрегата.
567. Планирование конкурентной цены и рационального объема продаж нового товара 279.5 KB
  Определение исходной цены и объема продаж нового товара. Оценка уровня конкурентоспособного товара по технико-эксплуатационным параметрам. Экспертная оценка предпочтительности товаров по параметрам. Определение диапазона конкурентной цены. Установление окончательной цены и объема продаж. Анализ воздействия ключевых факторов на прибыль.
568. Финансовое планирование и финансовый контроль на предприятиях 86 KB
  Финансовое планирование – это разновидность управленческой деятельности, направленной на определение необходимого объёма финансовых ресурсов, их оптимальное распределение и использование с целью обеспечения финансовой устойчивости хозяйствующего субъекта. Значение и задачи финансового планирования на предприятии.
569. Построение приложений локальных баз данных средствами СУБД Microsoft Access 74.5 KB
  Формирование письма исполнителю (указание выполнить дело, запрос о причинах задержки сроков исполнения). Разработка телефонного справочника. Автоматизация составления расписания. Вывод списка продуктов и сметы для данного блюда на N персон.
570. Исследование и настройка узлов магнитофона 75 KB
  Изучить строение магнитофона и дать оценку его функционированию. Проверка магнитофона произошла успешно, были выявлены неточности и недостатки в работе, но в общем можно сказать, что данный магнитофон пригоден для работы, и может использоваться в домашних условиях.