Еднопосочна функция
Еднопосочната функцияе математическа функция, която е лесна за изчисляване за всяка входна стойност, но е трудно да се намери аргументът, като се има предвид стойността на функцията. Тук "лесно" и "трудно" трябва да се разбират от гледна точка на теорията на изчислителната сложност. Разликата между сложността на предните и обратните трансформации определя криптографската ефективност на еднопосочната функция. Неинъективността на функцията не е достатъчно условие, за да я наречем еднопосочна. Еднопосочните функции също могат да бъдат наречени трудни за връщане или необратими.
Съществуването на еднопосочни функции все още не е доказано. Тяхното съществуване ще докаже, че класовете на сложност P и NP не са равни, решавайки редица проблеми в теоретичната компютърна наука по пътя. Съвременната асиметрична криптография се основава на предположението, че съществуват еднопосочни функции.
Еднопосочните функции са основни инструменти в криптографията, личната идентификация, удостоверяването и други области на сигурността на данните. Въпреки че съществуването на такива функции все още е недоказана хипотеза, има няколко претенденти, които са издържали десетилетия на проверка. Много от тях са неразделна част от повечето телекомуникационни системи, както и от системите за електронна търговия и интернет банкиране по света.
Съдържание
Съществуването на еднопосочни функции не е доказано. Акоfе еднопосочна функция, тогава намирането на обратната функция е трудно (по дефиниция), но лесно може да се провери (чрез оценяване наfвърху нея). Следователно от съществуването на еднопосочна функция следва, че P ≠ NP. Не е известно обаче дали P ≠ NP предполага съществуването на еднопосочни функции.
Наличието на едностраннофункции ще доведат до съществуването на много други полезни криптографски обекти, включително:
За еднопосочна функция се казва, че запазва дължината, ако битовата дължина на стойността на функцията е равна на битовата дължина на аргумента. Такива функции се използват например в псевдослучайни генератори. Ако битовата дължина на стойността на еднопосочна функция е постоянна за всяка дължина на аргумента, тогава тя се нарича хеш функция. И така, хеш функцията се използва за съхраняване на пароли или създаване на електронен подпис [1] .
Друг пример за използване на еднопосочни функции в криптографски схеми е следната схема за удостоверяване:
Доказателство за работа
За да се защитят компютърните системи от злоупотреба с услуги, искащата страна се иска да разреши проблем, който отнема много време, за да се намери решение, а резултатът се проверява лесно и бързо от обслужващата страна. Пример за такава защита срещу спам е системата Hashcash [3], която изисква частична инверсия на хеш от подателя на имейла.
Системата Bitcoin изисква получената хеш сума да бъде по-малка от специален параметър. За да търсите желаната хеш сума, е необходимо да я преизчислите многократно с изброяване на произволни стойности на допълнителния параметър. Отнема около 10 минути за всички компютри в системата да търсят една хеш сума, която регулира скоростта, с която се издават нови биткойни. Проверката изисква само едно хеш изчисление.
Сила на криптографските схеми
От казаното следва, че предположението за съществуването на еднопосочни функции е най-слабото криптографско предположение, което може да бъде достатъчно, за да докаже съществуването на силни криптографски схеми от различни видове. За уточнениеЗа да се установи дали това условие наистина е достатъчно, са положени значителни усилия от страна на специалистите.
В момента е доказано, че наличието на еднопосочни функции е необходимо и достатъчно условие за съществуването на силни криптосистеми с таен ключ, както и на силни криптографски протоколи от няколко вида, включително протоколи за електронен подпис. От друга страна, има резултат от Impagliazzo и Rudich, който е достатъчно силен аргумент, че определени типове криптографски схеми (включително протоколи за разпределение на ключове от тип Diffie-Hellman) изискват по-силни допускания от предположението за еднопосочна функция [4] .
Няколко претенденти за еднопосочни функции са описани по-долу. В момента не е известно дали те наистина са еднопосочни, но задълбочените изследвания все още не са успели да намерят ефективен обратен алгоритъм за всеки от тях.
Умножение и разлагане на множители
Обърнете внимание, че факторизацията с полиномна сложност е възможна на квантов компютър, използващ алгоритъма на Shor (BQP клас).
Повдигане на квадрат и извличане на квадратен корен по модул
Криптосистемата на Рабин се основава на предположението, че функцията на Рабин е еднопосочна.
Дискретна експозиция и логаритъм
Няколко тясно свързани проблема също са свързани с проблема с дискретния логаритъм. Нека е дадена крайна абелева група ( G , ∗ ):
Може да се покаже, че проблемът за избор на Дифи-Хелман не е по-труден от проблема на Дифи-Хелман, а проблемът на Дифи-Хелман не е по-труден от проблема с дискретния логаритъм [6] .
Криптографски хеш функции
Има много криптографски хеш функции (като SHA-256), които са бързисе изчисляват. Някои от по-простите версии не са преминали през сложен анализ, но най-силните версии продължават да предлагат бързи и практични решения за еднопосочни изчисления. Голяма част от теоретичната подкрепа за тези функции е насочена към осуетяване на някои от предишните успешни атаки.
Други претенденти
Други претенденти за еднопосочни функции се основават на трудността при декодиране на произволни линейни кодове и други проблеми.