Односторонняя функция: различия между версиями
[отпатрулированная версия] | [непроверенная версия] |
Содержимое удалено Содержимое добавлено
BsivkoBot (обсуждение | вклад) |
когда?, викификатор |
||
Строка 1:
{{unsolved|информатики|'''''Существуют ли односторонние функции ?'''''}}
'''Односторонняя функция'''
Существование односторонних функций до сих пор не доказано. Их существование докажет, что [[Равенство классов P и NP|классы сложности P и NP не равны]], попутно разрешив ряд вопросов теоретической [[Информатика|информатики]]. Современная{{когда}} [[асимметричная криптография]] основывается на предположении, что односторонние функции всё-таки существуют.
Односторонние функции являются фундаментальными инструментами [[Криптография|криптографии]], персональной идентификации, [[Аутентификация|аутентификации]] и других областей защиты данных. Хотя существование таких функций по-прежнему остаётся недоказанной гипотезой, существует несколько претендентов, выдержавших десятилетия пристального изучения. Многие из них являются неотъемлемой частью большинства [[Телекоммуникации|телекоммуникационных систем]], а также систем [[Электронная коммерция|электронной коммерции]] и [[интернет-банкинг]]а по всему миру.
== Определение ==
Пусть <math> \{0, 1\}^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> ограничено полиномом от длины искомого прообраза{{sfn|Птицын|2002|с=
== Существование ==
Существование односторонних функций не доказано. Если ''f'' является односторонней функцией, то нахождение обратной функции является трудновычислимой (по определению), но легкопроверяемой задачей (путём вычисления ''f'' на ней). Таким образом, из существования односторонней функции следует, что P ≠ NP. Однако, неизвестно, влечёт ли за собой P ≠ NP существование односторонних функций.
Строка 25 ⟶ 24 :
== Использование ==
Говорят, что односторонняя функция сохраняет длину, если битовая длина значения функции равна битовой длине аргумента. Такие функции используются, например, в псевдослучайных генераторах. Если битовая длина значения односторонней функции постоянна при любой длине аргумента, то она называется [[Криптографическая хеш-функция|хеш-функцией]]. Так, хеш-функция используется для хранения паролей или создания [[Электронная цифровая подпись|электронной подписи]]{{sfn|Птицын|2002|с=
Трудность задачи построения криптографических схем из односторонних функций можно пояснить на следующем примере. Пусть <math>f</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>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>. Такие схемы применяются для идентификации «свой/чужой»{{sfn|Схема аутентификации}}.
=== Доказательство выполнения работы ===
{{основная|Proof-of-work}}
Для защиты компьютерных систем от злоупотребления услугами запрашивающей стороне предлагается решить задачу, на поиск решения которой тратится достаточно много времени, а результат легко и быстро проверяется обслуживающей стороной. Примером такой защиты от [[
В системе «[[Биткойн]]» требуется, чтобы получаемая [[хеш-сумма]] была меньше специального параметра. Для поиска нужной хеш-суммы требуется её многократный пересчёт с перебором произвольных значений дополнительного параметра. На поиск одной хеш-суммы все компьютеры системы тратят примерно 10 минут, что регулирует скорость эмиссии новых биткойнов. Для проверки требуется лишь однократное вычисление хеша.
=== Стойкость криптографических схем ===
Существование односторонних функций является необходимым условием для стойкости многих типов криптографических схем. В некоторых случаях этот факт устанавливается достаточно просто. Рассмотрим функцию <math>f</math> такую, что <math>f(r) = K_1</math>. Она вычислима с помощью алгоритма <math>G</math> за полиномиальное время. Покажем, что если <math>f</math> не односторонняя функция, то криптосистема нестойкая. Предположим, что существует полиномиальный вероятностный алгоритм <math>A</math>, который инвертирует <math>f</math> с вероятностью по крайней мере <math>1/p(n)</math> для некоторого полинома <math>p</math>. Здесь <math>n</math>
Из всего сказанного следует, что предположение о существовании односторонних функций является самым слабым криптографическим предположением, которое может оказаться достаточным для доказательства существования стойких криптографических схем различных типов. На выяснение того, является ли это условие и в самом деле достаточным, направлены значительные усилия специалистов.
Строка 51:
=== Умножение и факторизация ===
Функция <math>f</math> принимает на вход два простых числа <math>p</math> и <math>q</math> в двоичном представлении и возвращает их произведение <math>N = f(p, q)</math>. Эта функция может быть вычислена за время порядка [[«O» большое и «o» малое|<math>O</math>]]<math>(n^2)</math>, где <math>n</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> лежит между полиномиальной и экспоненциальной. Поэтому про алгоритмы с такой сложностью говорят, что они требуют суб-экспоненциального времени{{sfn|Смарт|2005|с =
Существует несколько методов [[Факторизация|факторизации]] числа <math>N = p * q</math> с простыми <math>p</math> и <math>q</math>. Некоторые из них:
* ''Пробное деление''
* ''Метод эллиптической кривой'' хорошо работает, если один из простых множителей <math>p</math> не превосходит <math>2^{50}</math>. Его сложность оценивается как <math>L_p(1 / 2, c)</math>.
* ''Квадратичное решето'', вероятно, наиболее быстрый способ разложения чисел, лежащих между <math>10^{80}</math> и <math>10^{100}</math>. Его сложность
* ''Квадратичное решето в числовом поле''. В настоящее время это наиболее успешный метод для чисел, насчитывающих 100 и более десятичных знаков. С его помощью можно разлагать на множители числа до <math>10^{155}</math>, а его сложность оценивается как <math>L_N(1/3,\;(64/9)^{\frac{1}{3}})</math>{{sfn|Смарт|2005|с =
Функция может быть обобщена на диапазон [[Полупростое число|полупростых чисел]]. Заметим, что <math>f</math> не сможет быть односторонней для произвольных <math>p, q > 1</math>, так как их произведение с вероятностью ¾ имеет множитель 2.
Строка 66:
=== Возведение в квадрат и извлечение квадратного корня по модулю ===
Функция <math>f</math> принимает два целых числа: <math>x</math> и <math>N</math>, где <math>N</math>
[[Криптосистема Рабина]] основывается на предположении, что функция Рабина является односторонней.
=== Дискретное экспоненцирование и логарифмирование ===
Функция дискретного экспоненцирования <math>f</math> принимает в качестве аргументов простое число <math>p</math> и целое <math>x</math> в интервале от <math>0</math> до <math>p - 1</math> и возвращает остаток от деления некоторого <math>A^x</math> на <math>p</math>. Эта функция может быть легко вычислена за время [[«O» большое и «o» малое|<math>O</math>]]<math>(n^3)</math>, где <math>n</math>
:: <math>A^x = B</math>
Для некоторых групп <math>G</math> такая задача довольно проста. Например, если <math>G</math>
Для групп, подобных эллиптической кривой, задача дискретного логарифмирования
С задачей дискретного логарифмирования так же связано несколько близких задач. Пусть дана конечная абелева группа <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>.
Можно показать, что задача выбора Диффи-Хеллмана не сложнее задачи Диффи-Хеллмана, а задача Диффи-Хеллмана не сложнее задачи вычисления дискретных логарифмов{{sfn|Смарт|2005|с =
=== Криптографические хеш-функции ===
|