Википедия

Односторонняя функция: различия между версиями

Интерактивная навигация по истории
[отпатрулированная версия][непроверенная версия]
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
Добавил информации из книжек.
Строка 1:
{{unsolved|информатики|'''''Существуют ли односторонние функции ?'''''}}
 
'''Односторонняя функция''' ({{lang-en|one-way function, OWF}}) это функция, которая легко вычисляется для любого входного значения, но трудно найти аргумент по заданному значению функции. Здесь «легко» и «трудно» должны пониматься с точки зрения [[Теория сложности вычислений|теории сложности вычислений]]. Разрыв между сложностью прямого и обратного преобразований определяет криптографическую эффективность односторонней функции. [[Инъекция (математика)|Неинъективность функции]] не является достаточным условием для того, чтобы называть её односторонней. Односторонние функции могут называться также трудно обратимыми или необратимыми.
 
Существование односторонних функций до сих пор не доказано. Их существование докажет, что [[Равенство классов P и NP|классы сложности P и NP не равны]], попутно разрешив ряд вопросов теоретической [[Информатика|информатики]]. Современная [[асимметричная криптография]] основывается на предположении, что односторонние функции все-таки существуют.
Строка 8:
 
== Определение ==
ФункцияПусть ''f'':<math> \{0, 1\}^n<sup/math>* — множество всех двоичных строк длины n. Функция </supmath>f: →\{0, 1\}^* \rightarrow \{0, 1\}<sup>^*</supmath> является '''односторонней функцией''', если она [[Теория сложности вычислений|эффективно]] вычисляется за полиномиальное время на детерминированной [[Машина Тьюринга|машине Тьюринга]], но не существует полиномиальной [[Вероятностная машина Тьюринга|вероятностной машины Тьюринга]], которая обращает эту функцию с более чем экспоненциально малой вероятностью. То есть для любой вероятностной полиномиальной машины <math>M</math>, для любого полинома <math>p(n)</math> и достаточно большого <math>n \in \mathbb{N}</math> выполняется:
 
:: <math>Pr[M(f(m)) \in f^{-1}(m)] < 1/p(n)</math>
 
где строка <math>m</math> выбирается случайным образом на множестве <math>\{0, 1\}^n</math> в соответствии с равномерным законом распределения. Время работы машины <math>M</math> ограничено полиномом от длины искомого прообраза.
 
== Существование ==
Строка 21 ⟶ 25 :
* [[Электронная цифровая подпись]].
 
== Использование ==
== Односторонние функции в криптографических схемах ==▼
Говорят, что односторонняя функция сохраняет длину, если битовая длина значения функции равна битовой длине аргумента. Такие функции используются, например, в псевдослучайных генераторах. Если битовая длина значения односторонней функции постоянна при любой длине аргумента, то она называется [[Криптографическая хеш-функция| хеш-функцией]]. Так, хеш-функция используется для хранения паролей или создания [[Электронная цифровая подпись|электронной подписи]].
Существование односторонних функций является необходимым условием для стойкости многих типов криптографических схем. В некоторых случаях этот факт устанавливается достаточно просто. Рассмотрим функцию ''f'' такую, что ''f(r) = K<sub>1</sub>''. Она вычислима с помощью алгоритма ''G'' за полиномиальное время. Покажем, что если ''f'' не односторонняя функция, то криптосистема нестойкая. Предположим, что существует полиномиальный вероятностный алгоритм ''A'', который инвертирует ''f'' с вероятностью по крайней мере ''1/p(n)'' для некоторого полинома ''p''. Здесь ''n'' — длина ключа <math>K_1</math>. Атакующий может подать на вход алгоритму ''A'' ключ <math>K_1</math> и получить с указанной вероятностью некоторое значение <math>r'</math> из прообраза. Далее злоумышленник подает <math>r'</math> на вход алгоритма ''G'' и получает пару ключей <math>(K_1, K'_2)</math>. Хотя <math>K'_2</math> не обязательно совпадает с <math>K_2</math>, тем не менее, по определению криптосистемы <math>D_{K_2'}(E_{K_1}(m)) = m</math> для любого открытого текста ''m''. Поскольку <math>K'_2</math> найден с вероятностью по крайней мере ''1/p(n)'', которая в криптографии не считается пренебрежимо малой, криптосистема нестойкая.▼
 
Из всего сказанного следует, что предположение о существовании односторонних функций является самым слабым криптографическим предположением, которое может оказаться достаточным для доказательства существования стойких криптографических схем различных типов. На выяснение того, является ли это условие и в самом деле достаточным, направлены значительные усилия специалистов. Трудность задачи построения криптографических схем из односторонних функций можно пояснить на следующем примере. Пусть ''<math>f'' </math> — односторонняя функция и нам требуется построить ''криптосистему с секретным ключом''. В такой криптосистеме имеется только один ключ  — секретный, который известен и отправителю, и получателю шифрованного сообщения. Алгоритмы шифрования <math>E_K</math> и дешифрования <math>D_K</math> оба зависят от этого секретного ключа <math>K</math> и таковы, что <math>D_K(E_K(m)) = m</math> для любого открытого текста ''<math>m''</math>. Ясно, что если криптограмму ''<math>d''</math> сообщения ''<math>m''</math> вычислять как <math>d=f(m)</math>, то противник, перехвативший ''<math>d''</math>, может вычислить ''<math>m''</math> лишь с пренебрежимо малой вероятностью. Но во-первых, непонятно, каким образом сможет восстановить сообщение ''<math>m''</math> из криптограммы законный получатель? Во-вторых, из того, что функция ''<math>f''</math> односторонняя следует лишь, что противник не может вычислить все сообщение целиком. А это  — весьма низкий уровень стойкости. Желательно, чтобы противник, знающий криптограмму ''<math>d''</math>, не мог вычислить ни одного бита открытого текста.
 
Для решения первой проблемы были придуманы [[Односторонняя функция с потайным входом|односторонние функции с потайным входом]]. Это специальный тип односторонней функции для которой легко вычислить <math>f(m)</math> по заданному <math>m</math>, трудно по известному <math>f(m)</math> вычислить <math>m</math>. Однако существует некоторая дополнительная секретная информация <math>y</math>, позволяющая при знании <math>f(m)</math> и <math>y</math> легко вычислить <math>m</math>.
На настоящий момент доказано, что существование односторонних функций является необходимым и достаточным условием для существования стойких криптосистем с секретным ключом, а также стойких криптографических протоколов нескольких типов, включая протоколы электронной подписи.
 
 
Еще одним примером использования односторонних функций в криптографических схемах является следующая схема аутентификации:
 
Абонент <math>A</math> вырабатывает следующую последовательность сообщений: <math>m_0, m_1=f(m_0), m_2=f(m_1)</math> и т. д. <math>m_{100}=f(m_{99})</math>, где <math>f(m)</math> — односторонняя функция. Затем <math>m_{100}</math> передается по секретному каналу (или при встрече) абоненту <math>B</math>. Когда <math>A</math> необходимо подтвердить свою личность, он передаёт <math>B</math> по открытому каналу сообщение <math>m_{99}</math>. <math>B</math> проверяет: <math>f(m_{99}) =? m_{100}</math>. В следующий раз <math>A</math> передаст <math>m_{98}</math>, и <math>B</math> проверит: <math>f(m_{98}) =? m_{99}</math> и т. д. Перехват сообщений на i-ом этапе в открытом канале ничего не даст злоумышленнику, так как он не сможет получить соответствующее значение <math>m_{i-1}</math>, чтобы в следующий раз идентифицировать себя как абонента <math>A</math>. Такие схемы применяются для идентифкации «свой/чужой».
 
▲=== Односторонние функции вСтойкость криптографических схемахсхем ===
▲Существование односторонних функций является необходимым условием для стойкости многих типов криптографических схем. В некоторых случаях этот факт устанавливается достаточно просто. Рассмотрим функцию ''<math>f''</math> такую, что ''<math>f(r) = K<sub>1K_1</submath>''. Она вычислима с помощью алгоритма ''<math>G''</math> за полиномиальное время. Покажем, что если ''<math>f''</math> не односторонняя функция, то криптосистема нестойкая. Предположим, что существует полиномиальный вероятностный алгоритм ''<math>A''</math>, который инвертирует ''<math>f''</math> с вероятностью по крайней мере ''<math>1/p(n)''</math> для некоторого полинома ''<math>p''</math>. Здесь ''<math>n'' </math> — длина ключа <math>K_1</math>. Атакующий может подать на вход алгоритму ''<math>A''</math> ключ <math>K_1</math> и получить с указанной вероятностью некоторое значение <math>r'</math> из прообраза. Далее злоумышленник подает <math>r'</math> на вход алгоритма ''<math>G''</math> и получает пару ключей <math>(K_1, K'_2)</math>. Хотя <math>K'_2</math> не обязательно совпадает с <math>K_2</math>, тем не менее, по определению криптосистемы <math>D_{K_2'}(E_{K_1}(m)) = m</math> для любого открытого текста ''<math>m''</math>. Поскольку <math>K'_2</math> найден с вероятностью по крайней мере ''<math>1/p(n)''</math>, которая в криптографии не считается пренебрежимо малой, криптосистема нестойкая.
 
Из всего сказанного следует, что предположение о существовании односторонних функций является самым слабым криптографическим предположением, которое может оказаться достаточным для доказательства существования стойких криптографических схем различных типов. На выяснение того, является ли это условие и в самом деле достаточным, направлены значительные усилия специалистов.
 
На настоящий момент доказано, что существование односторонних функций является необходимым и достаточным условием для существования стойких криптосистем с секретным ключом, а также стойких криптографических протоколов нескольких типов, включая протоколы электронной подписи, а также стойких криптографических протоколов нескольких типов, включая протоколы электронной подписи. С другой стороны, имеется результат Импальяццо и Рудиха, который является достаточно сильным аргументом в пользу того, что для некоторых типов криптографических схем (включая протоколы распределения ключей типа Диффи-Хеллмана) требуются более сильные предположения, чем предположение о существовании односторонних функций<ref name="limits"></ref>.
 
== Кандидаты в односторонние функции ==
Строка 32 ⟶ 48 :
 
=== Умножение и факторизация ===
Функция ''<math>f''</math> принимает на вход два простых числа ''<math>p''</math> и ''<math>q''</math> в двоичном представлении и возвращает их произведение. Эта функция может быть вычислена за время порядка [[«O» большое и «o» малое|''<math>O''</math>]](''n''<supmath>(n^2)</supmath>), где ''<math>n'' </math> — общая длина (количество двоичных чисел) входных данных. Построение обратной функции требует нахождения множителей заданного целого числа ''<math>N''</math>. ЛучшийОпределение известныймножителей алгоритмявляется [[факторизация|разложенияочень натрудоёмкой множители]]вычислительной выполняетсяоперацией. заДля времяоценки <math>2^{O({(\logсложности N)^{1/3}алгоритма, (\logраскладывающего \logцелое число <math>N})^{2/3})}</math> ина являетсяпростые [[Псевдополиномиальныймножители, алгоритм|псевдополиномиальным]].часто используют функцию:
:: <math>L_N(\alpha, \beta) = exp((\beta + o(1)(\ln N)^\alpha(\ln \ln N)^{1 - \alpha}))</math>
Если алгоритм имеет сложность <math>O(L_N(0, \beta))</math>, то ему требуется полиномиальное время на работу (размер задачи на входе, число бит числа, <math>\ln N</math>). При сложности <math>O(L_N(1, \beta))</math> ему потребуется уже экспоненциальное время. Таким образом скорость роста функции <math>L_N(\alpha, \beta)</math> при <math>0 < \alpha < 1</math> лежит между полиномиальной и экспоненциальной. Поэтому про алгоритмы с такой сложностью говорят, что они требуют суб-экспоненциального времени.
 
Существует несколько методов [[Факторизация|факторизации]] числа <math>N = p * q</math> с простыми <math>p</math> и <math>q</math>. Некоторые из них:
Функция может быть обобщена на диапазон [[Полупростое число|полупростых чисел]]. Заметим, что ''f'' не сможет быть односторонней для произвольных ''p'', ''q'' > 1, так как их произведение с вероятностью ¾ имеет множитель 2.▼
* ''Пробное деление'' — в этом алгоритме для всех простых чисел <math>p</math>, не превосходящих <math>\sqrt{N}</math>, проверяется условие <math>N / p \in \mathbb Z</math>. Такой алгоритм близок к полному перебору и имеет экспоненциальную сложность <math>O(L_N(1, 1))</math>.
* ''Метод эллиптической кривой'' хорошо работает, если один из простых множителей <math>p</math> не превосходит <math>2^{50}</math>. Его сложность оценивается как <math>L_p(1 / 2, c)</math>.
* ''Квадратичное решето'', вероятно, наиболее быстрый способ разложения чисел, лежащих между <math>10^{80}</math> и <math>10^{100}</math>. Его сложность — <math>L_p(1 / 2, 1)</math>.
* ''Квадратичное решето в числовом поле''. В настоящее время это наиболее успешный метод для чисел, насчитывающих 100 и более десятичных знаков. С его помощью можно разлагать на множители числа до <math>10^{155}</math>, а его сложность оценивается как <math>L_N(1/3,\;(64/9)^{\frac{1}{3}})</math>.
 
▲Функция может быть обобщена на диапазон [[Полупростое число|полупростых чисел]]. Заметим, что ''<math>f''</math> не сможет быть односторонней для произвольных ''<math>p'', ''q'' > 1</math>, так как их произведение с вероятностью ¾ имеет множитель 2.
 
Заметим, что факторизация с полиномиальной сложностью возможна на [[Квантовый компьютер|квантовом компьютере]] с помощью [[Алгоритм Шора|алгоритма Шора]] ([[класс BQP]]).
 
=== Возведение в квадрат и извлечение квадратного корня по модулю ===
Функция ''<math>f''</math> принимает два целых числа: ''<math>x''</math> и ''<math>N''</math>, где ''<math>N'' </math> — произведение двух простых ''<math>p''</math> и ''<math>q''</math>. На выходе  — остаток от деления ''x''<supmath>x^2</supmath> на <math>N</math>. Нахождение обратной функции требует вычисления квадратного корня по модулю <math>N</math>, то есть нахождения <math>x</math> если известно <math>y</math> и ''x''то, что <supmath>x^2</sup> mod\bmod ''N'' = ''y''</math>. Можно показать, что последняя задача вычислительно так же сложна, как и разложение <math>N</math> на множители.
 
[[Криптосистема Рабина]] основывается на предположении, что функция Рабина является односторонней.
 
=== Дискретное экспоненцирование и логарифмирование ===
Функция дискретного экспоненцирования ''<math>f''</math> принимает в качестве аргументов простое число ''<math>p''</math> и целое ''<math>x''</math> в интервале от ''<math>0''</math> до ''p−1''<math>p - 1</math> и возвращает остаток от деления некоторого <math>2A^x</math> на ''<math>p''</math>. Эта функция может быть легко вычислена за время [[«O» большое и «o» малое|''<math>O''</math>]](''n''<supmath>(n^3)</supmath>), где ''<math>n'' </math> — количество битов в ''<math>p''</math>. Обращение этой функции требует вычисления [[дискретный логарифм|дискретного логарифма]] по модулю ''<math>p''</math>. ТоПусть есть<math>(G, по*)</math> заданному- простомуконечная ''p''абелева игруппа, целомунапример ''y''мультипликативная междугруппа ''0''конечного иполя ''p−1''или требуетсяэллиптическая найтикривая такоенад ''x'',конечным чтополем. Проблема вычисления дискретных логарифмов состоит в определении целого числа <math>2^x</math>, modкоторое ''p''при =данных ''y''.<math>A, [[СхемаB</math> Эль-Гамаля]]удовлетворяет основывается на этой функции.соотношению:
::<math>A^x = B</math>
Для некоторых групп <math>G</math> такая задача довольно проста. Например, если <math>G</math> - группа целых чисел по модулю <math>N</math> по сложению. Для других групп, однако, эта задача более сложная. Например, в мультипликативной группе конечного поля, наилучший из известных алгоритмов, решающий проблему дискретного логарифмирования, - это метод [[Общий метод решета числового поля|квадратичного решета в числовом поле]]. Сложность вычисления дискретных логарифмов в этом случае оценивается как <math>L_N(1/3, c)</math>. [[Схема Эль-Гамаля]] основывается на этой проблеме.
 
Для групп, подобных эллиптической кривой, задача дискретного логарифмирования еще более трудна. Наилучший из доступных на сегодняшний день методов, вычисляющих дискретные логарифмы над общей эллиптической кривой над полем <math>\mathbb F_q</math>, называется [[Ρ-метод Полларда дискретного логарифмирования|ρ-метод Полларда]]. Его сложность <math>O(L_N(1, 1/2))</math>. Это экспоненциальный алгоритм, поэтому криптосистемы, основанные на эллиптической кривой, как правило, работают с малым ключом, около 160 бит. В то время как системы, отталкивающиеся от разложения на множители или вычисления дискретных логарифмов в конечных полях, используют ключи в 1024 бита.
 
С проблемой дискретного логарифмирования так же связано несколько близких задач. Пусть дана конечная абелева группа <math>(G, *)</math>:
*''Задача Диффи-Хеллмана'', которая состоит в следующем: даны элементы <math>A \in G, B = A^x, C = A^y</math>. Требуется вычислить <math>D = A^{xy}</math>.
*''Проблема выбора Диффи-Хеллмана''. Дано: <math>A \in G, B = A^x, C = A^y, D = A^z</math>. Требуется определить, является ли <math>z</math> произведением <math>x</math> и <math>y</math>.
Можно показать что проблема выбора Диффи-Хеллмана не сложнее задачи Диффи-Хеллмана, а задача Диффи-Хеллмана не сложнее задачи вычисления дискретных логарифмов.
 
=== Криптографические хэш-функции ===
Строка 53 ⟶ 88 :
* [[Криптографическая хеш-функция]]
* [[Односторонняя функция с потайным входом]]
 
== Примечания ==
<references>
<ref name="limits">{{книга|автор = Russell Impagliazzo, Steven Rudich|заглавие = Private Information Retrieval Does Not Imply One-way Permutations|ссылка = http://www.csie.ntu.edu.tw/~lyuu/theses/thesis_r88067.pdf}}</ref>
</references>
 
== Ссылки ==
Строка 60 ⟶ 100 :
* {{cite book|author = [[Christos Papadimitriou]] | year = 1993 | title = Computational Complexity | publisher = Addison Wesley | edition = 1st edition | isbn = 0-201-53082-1 |chapter=Section 12.1: One-way functions |pages=279—298}}
* {{книга |заглавие=Введение в криптографию |ответственный=Под ред. В. В. Ященко |часть=[http://nature.web.ru/db/msg.html?mid=1157083&uri=node14.html Глава 2.3. Односторонние функции] |ссылка=http://nature.web.ru/db/msg.html?mid=1157083&uri=book.html}}
* {{книга |заглавие= Приложение теории детерминированного хаоса в криптографии |ответственный= Птицын Н |часть= Глава 2.5.2 Односторонняя функция |ссылка= http://www.reid.ru/books/%D0%A2%D0%B5%D1%85%D0%BD%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F%20%D0%B8%20%D1%81%D0%BF%D0%B5%D1%86%D0%B8%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F/spec.lit/spechran/136-140/spec139/Pticin%20N.%20Prilozhenie%20teorii%20determinirovannogo%20haosa%20v%20kriptografii.%20(2002).pdf|ref = Птицын}}
 
* {{книга |заглавие=Криптография |ответственный=Смарт Н|часть=Глава 7.2 Односторонние функции |ссылка=https://ru.scribd.com/doc/38151420/%D0%A1%D0%BC%D0%B0%D1%80%D1%82-%D0%9A%D1%80%D0%B8%D0%BF%D1%82%D0%BE%D0%B3%D1%80%D0%B0%D1%84%D0%B8%D1%8F-2005|isbn=5-94836-043-1}}
* {{cite web |url= http://netcode.ru/cpp/?artID=4010|title= Глава 4.1 Односторонние функции |accessdate=2014-10-09 |lang=рус.}}
[[Категория:Криптография]]
[[Категория:Нерешённые проблемы информатики]]
Источник — https://ru.wikipedia.org/wiki/Односторонняя_функция