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

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


 

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

74120. Порядок хранения и получения информации из базы данных АСКУЭ Энергия+ 17.8 KB
  Для хранения информации в КТС Энергия используется SQLсервер. Хранимая в SQL инф подразделяется на две части: проектные данные содержащие описания состава и названий УСД электр счётчиков ед измерений и др параметры кот пользователь вводит при подготовке проектных Д в программе Редактор проекта . Эти Д формируются программой Ядро и при помощи программы Запись в базу помещаются в SQL. Для хранения и обработки указанной инф исп неск независ баз в SQL: проектная база eng6 используемая программой Редактор проекта для хранения всей...
74121. Структура и состав базового программного обеспечения АСКУЭ Энергия+ 21.72 KB
  Клиентская часть обеспечивает отображение пользователю Д, хранимых в серв части. Содержит разные приложения – потребители инф: разл документы, генераторы отчётов и т.п. С одной серв частью могут работать одна или более кл частей. При доступе к Д только через WEB-сервер на кл компе не требуется установка к-л программ – достаточно наличия WEB-браузера.
74122. SCADA – система TRACE MODE 45.95 KB
  SCD система TRCE MODE. В 2005 г TRCE MODE интегрированная SCD система для разработки АСУ ТП АСКУЭ и систем управления производством получила сертификат соответствия ГОСТ Р выданный ГОССТАНДАРТОМ России. По результатам испытаний в сертификационной лаборатории установлено соответствие интегрированной SCD TRCE MODE требованиям нормативных документов российских и международных стандартов. Это стало важным этапом в процессе повышения качества SCD системы TRCE MODE до уровня лучших мировых аналогов.
74123. Структура системы TRACE MODE 20.57 KB
  Монитор реального времени МРВ. Под управлением МРВ выполняются такие задачи как: запрос данных о состоянии технологического процесса с контроллеров нижнего уровня по любому из встроенных протоколов или через драйвер; передача на нижний уровень команд управления по любому из встроенных протоколов или через драйвер; обмен данными с платами УСО; сохранение данных в архивах; обмен по сети с удаленными МРВ; передача данных по сети на следующий уровень АСУ; обмен с базами данных через ODBC; представление оператору графической информации о...
74124. Автоматизированные информационные системы – общие понятия, структура 17.43 KB
  Автоматизированные информационные системы можно разделить на: Системы информационного обеспечения имеющие самостоятельное целевое назначение и область применения; Автоматизированные системы управления АСУ. Системы информационного обеспечения как правило содержат информационную базу используемую различными потребителями для удовлетворения информационных потребностей при принятии решений. Автоматизированные системы управления человекомашинные системы обеспечивающие автоматический сбор и обработку информации с помощью различных...
74125. Программное обеспечение АСУ ТП. SCADA – системы 18.64 KB
  Программное обеспечение АСУ ТП принято делить на две категории: общее программное обеспечение включающее операционные системы SCDсистемы пакеты программ для программирования контроллеров компиляторы редакторы и т. К этой категории относятся программы для контроллеров реализующие определённые функциональные задачи обработки информации и управления; программы сгенерированные в среде SCDсистемы для визуализации. SCDсистемы супервизорное диспетчерское управление и получение данных это программные продукты которые...
74126. Структура SCADA – систем 18.32 KB
  Специфика каждой конкретной системы управления определяется используемой на каждом уровне программно аппаратной платформой. Датчики поставляют информацию контроллерам которые могут выполнять следующие функции:с бор и обработка информации о параметрах технологического процесса; управление электроприводами и другими исполнительными механизмами; решение задач автоматического логического управления и др...