Перегляд вихідного коду сторінки Одностороння функція

У [[інформатика|інформатиці]], односторонньою функцію є [[функція (математика)|функція]], яку [[легко обчислити]] на кожному вході, але [[важко обчислити|важко знайти]] прообраз елемента [[Область значень|області значень]] функції. Тут «легко» і «складно» слід розуміти з точки зору [[Теорія складності обчислень|теорії складності]], зокрема теорії проблеми поліноміального часу. Те, що функція не є [[бієкція|бієкцією]] не є достатнім, щоб функція була односторонньою.

Існування таких односторонніх функцій досі є відкритою проблемою. З їхнього існування випливає твердження, що [[клас складності|класи складності]] [[Рівність класів P і NP|P та NP не рівні]].
Сучасна [[асиметрична криптографія]] ґрунтується на припущенні, що односторонні функції все-таки існують.

У прикладному контексті, терміни «легко» і «складно», як правило, інтерпретуються як «досить дешево для легітимних користувачів» і «занадто витратно для будь-яких несанкціонованих агентів». Односторонні функції, в цьому сенсі, є основними інструментами криптографії, [[ідентифікація особистості|ідентифікації особистості]], [[аутентифікація|аутентифікації]], та інших складових [[Послуга безпеки (телекомунікації)|безпеки даних]]. Хоча наявність таких функцій також є відкритою проблемою, є кілька кандидатів, які витримали десятиліття пильного розгляду. Деякі з них є необхідними елементами телекомунікаційних систем і, систем [[Електронна комерція|електронної комерції]] і [[Інтернет-банкінг]]у по всьому світу.

== Теоретичне визначення ==
Функція ''f'': {0, 1}<sup>n</sup> → {0, 1}<sup>*</sup> є '''односторонньою''', якщо ''f'' може бути обчислена алгоритмом поліноміальної складності, але для кожного довільного, поліноміальної складності, алгоритму ''A'' виконується:

: <math>Pr[ f( A( f(x) ) ) = f(x) ] < \frac{1}{p(n)}</math>

для будь-якого позитивного многочлену ''р''(''n'') і достатньо великих ''n'', вважаючи, що ''x'' обирається за [[рівномірний розподіл|рівномірним розподілом]] з {0, 1} <sup>''n''</sup> та випадковості ''A''.

Відзначимо що, за цим визначенням має бути «складною» для обернення у середньостатистичному випадку, а не в найгіршому, на відміну від теорії складності, де під складним зазвичай розуміють складне у найгіршому випадку.

Відзначимо знову, що просто зробити функцію не бієкцією не робить її односторонньою функції. У цьому контексті, обернення функції означає визначення хоч якогось одного прообразу заданого значення, що не вимагає існування [[обернена функція|оберненої функції]]. Наприклад, ''f''(''x'') = ''x''<sup>2</sup> не є оборотньою (наприклад, ''f''(2) = ''f''(-2) = 4), але також не є односторонньою, бо для будь-якого значення можна обчислити один з елементів його прообразу за поліноміальний час, взявши його квадратний корінь.

== Пов'язані поняття ==
'''Одностороння перестановка'''&nbsp;— одностороння функція, яка є [[перестановка|перестановкою]]. Односторонні перестановки є важливим [[криптографічний примітив|криптографічним примітивом]], і не відомо, чи їхнє існування випливає з існування односторонніх функцій.

[[Колізія хеш-функції|Хеш-функція без колізій]] f є односторонньою функцією, яка також стійка до колізій, тобто жоден довільний поліноміальночасовий алгоритм не може знайти колізію&nbsp;— значення ''x'', ''y'', що ''f''(''x'') = ''f''(''y'')&nbsp;— з '''не''' незначною ймовірністю.

=== Одностороння функція з секретом ===
'''Одностороння функція з секретом''' ({{lang-en|trapdoor function}}) — це [[одностороння функція]] <math>f(x): D \rightarrow R</math>, яку [[легко обчислити]] для будь-якого <math>x \in D</math>, але [[майже для всіх]] значень <math>y \in R</math> [[важко обчислити]] значення <math>x</math> таке що <math>y = f(x)</math>. Однак якщо існує секрет k, то знаючи його легко обчислити x <math>\forall y \in R</math>{{sfn|Гулак|Мухачов|Хорошко|Яремчук|2011|p=111}}. Односторонні функції широко використовуються в [[криптографія|криптографії]].

Односторонні функції набули поширеності в криптографії в середині 1970-х з оприлюдненням Діффі, Геллманом і Мерклом [[Асиметричні алгоритми шифрування|асиметричних алгоритмів шифрування]]. Діффі і Геллман запропонували кілька варіантів побудови таких функцій{{sfn|Гулак|Мухачов|Хорошко|Яремчук|2011|p=111}}, дуже швидко виявилось, що знайти односторонню функцію важче ніж видавалось на перший погляд, бо перші функції не були ас

Прикладом такої функції може слугувати одностороння функція RSA. Через наявність секрету, що дозволяє легко обчислити першовзір більшість цифрових підписів покладаються саме на RSA функцію.

== Теоретичні наслідки односторонніх функцій ==
Якщо ''f'' є односторонньою функцією, то обернення ''f'' буде задачею, вихід якого важко обчислити (за означенням), але легко перевірити (шляхом обчислення ''f'' від нього). Таким чином, з існування односторонньої функції випливає, що P ≠ NP. Однак, невідомо, чи з P ≠ NP випливає існування односторонніх функцій.

З існування односторонньої функції випливає існування багатьох інших корисних концепцій, у тому числі:

* [[Генератор псевдовипадкових чисел|Псевдовипадкових генераторів]];
* сімей [[Псевдовипадкова функція|Псевдовипадкових функції]];
* Бітова [[схема зобов'язання]];
* Приватний ключ шифрування схем, безпечний проти адаптивної атаки з вибором шифрованого тексту;
* [[MAC підпис]];
* [[Схема цифрового підпису]] (безпечна проти адаптивної атаки з вибором повідомлень).

== Кандидати на звання односторонньої функції ==
Є численна кількість кандидатів на звання односторонньої функції (станом на квітень 2009 року). Ясно, що невідомо, чи є ці функції дійсно односторонніми, але значні дослідження досі не змогли створити ефективний алгоритм обернення для хоч однієї з них.

=== Множення і факторизація ===
Функція ''f'' приймає на вхід два прості числа ''p'' і ''q'' в двійковому вигляді і повертає їхній добуток. Ця функція може бути обчислена за час ''O''(''n''<sup>2</sup>), де ''n'' є сумарною довжиною (кількістю цифр) аргументів. Обернення цієї функція вимагає [[факторизація|факторизацію]] заданого цілого числа''N''. Найкращі алгоритми факторизації, відомі для цієї задачі, працюють час <math>2^{O({(\log N)^{1/3} (\log \log N})^{2/3})}</math>, який є всього-лише [[псевдо-поліноміальний час|псевдо-поліноміальний]] у <math>\log N</math>, число бітів, необхідних для подання''N''.

Ця функція може бути узагальнена покладанням ''p'' і ''q'' у підходящому наборі [[Напівпросте число|напівпростих]] чисел. Відзначимо, що ''f'' не одностороння для довільних ''p, q''&gt;1, так як добуток буде мати 2 як дільник з імовірністю 3/4.

=== Модульне піднесення у квадрат і знаходження квадратного кореня ===
Функція ''f'' приймає два натуральних числа ''x'' і ''N'', де ''N''&nbsp;— добуток двох простих ''p'' і''q''. На виході&nbsp;— остача від ділення ''x''<sup>2</sup> на ''N''. Знаходження оберненої функції вимагає обчислення квадратного кореня за модулем ''N'', тобто ''x'', якщо відомо y і ''x''<sup>2</sup> mod ''N'' = ''y''. Можна показати, що останнє завдання таке ж складне, як і розкладання N на множники.

[[Криптосистема Рабіна]] ґрунтується на припущенні, що функція Рабіна (тобто, ця) є односторонньою.

=== Дискретне експоненціювання і логарифмування ===
<!-- За цим описом, це не одностороння функція, а [[люк-функція]]. Що це дає? -->
Функція ''f'' приймає просте число ''p'' і ціле ''x'' між 0 і ''p''−1; і повертає залишок частини 2<sup>''x''</sup> поділеного на ''p''. Ця функція [[Дискретне експоненціювання|дискретного експоненціювання]] може бути легко обчислена за час ''O''(''n''<sup>3</sup>), де ''n''&nbsp;— кількість біт у ''p''. Обернення цієї функції вимагає обчислення [[дискретний логарифм|дискретного логарифма]] за модулем ''p''; якщо дано просте ''p'' і ціле ''y'' між 0 і ''p''−1;, знаходимо таке ''x'', що 2<sup>''x''</sup> = ''y''. Станом на 2009, немає опублікованих алгоритмів цієї задачі, які працюють за поліноміальний час. Схема [[Схема Ель-Гамаля|ElGamal]] заснована на цій функції.

=== Криптографічні хеш-функції ===
Є ряд [[криптографічна хеш-функція|криптографічних хеш-функцій]], які швидко обчислюються (наприклад, [[SHA-256|SHA 256]]). Деякі простіші версії не проходили складний аналіз, але найсильніші версії продовжують пропонувати швидкі, практичні рішення для розрахунку в один бік. Більшу частину теоретичної підтримки складають методи зриву деяких раніше успішних атак.

=== Інші претенденти ===
Інші претенденти в односторонні функції ґрунтуються на складності декодування випадкових [[Лінійний код|лінійних кодів]] та інших завданнях.

== Універсальна одностороння функція ==
Існує явна функція, яка є односторонньою, [[Тоді й лише тоді|тоді і тільки тоді]], коли односторонні функції існують. Так як ця функція була першою знайденою комбінаторно повною односторонньою функцією буде показано, вона відома як «універсальна одностороння функція». Задача визначення існування односторонніх функцій, таким чином, зводиться до задачі доведення того, що дана функція є односторонньою.

== Зноски ==
<references />

== Література ==
* {{cite book |last1=Гулак |first1=Г. М |last2=Мухачов |first2=В. А. |last3=Хорошко |first3=В. О. |last4=Яремчук |first4=Ю. Є. |title=Основи криптографічного захисту інформації |date=2011 |publisher=ВНТУ |location=Вінниця |isbn=978-966-641-430-7|ref=harv}}

== Посилання ==
*{{citation|first1=W.|last1=Diffie|author1-link=Whitfield Diffie|first2=M.|last2=Hellman|author2-link=Martin Hellman|title=New directions in cryptography|journal=[[IEEE Transactions on Information Theory]]|volume=22|issue=6|pages=644–654|year=1976|doi=10.1109/TIT.1976.1055638|url=http://www-ee.stanford.edu/~hellman/publications/24.pdf|citeseerx=10.1.1.37.9720}}

{{Math-stub}}{{Crypto-stub}}
{{ВП-портали|Програмування|Математика}}

[[Категорія:Криптографія]]
[[Категорія:Криптографічні примітиви]]
[[Категорія:Нерозв'язані проблеми інформатики]]