Еднопосочни функции
Концепцията за еднопосочна функция е централна за криптографията с публичен ключ. Въпреки че не са директно протоколи, еднопосочните функции са крайъгълният камък на повечето протоколи.
Еднопосочните функции са относително лесни за изчисляване, но са по-трудни за обръщане. Тоест, знаейки x е лесно да се изчисли f(x), но знаейки f(x), не е лесно да се изчисли x. Тук „не е лесно“ означава, че може да отнеме милиони години, за да се изчисли x от f(x), дори ако всички компютри в света се борят с този проблем.
Счупената чиния е добър пример за еднопосочна функция. Лесно е да счупиш чиния на хиляди малки парчета. Не е лесно обаче да сглобите чинията отново от тези парчета.
Звучи хубаво, но неясно и неразбираемо. Няма математически строго доказателство за съществуването на еднопосочни функции и няма реални доказателства за възможността за тяхното конструиране. Въпреки това много функции изглеждат точно като еднопосочни: можем да ги изчислим и досега не знаем лесен начин да ги обърнем. Например, в ограничен квартал е лесно да се изчисли x 2 , но x 1/2 е много по-трудно.
И така, какво е толкова страхотно в еднопосочните функции? Те не могат да се използват директно за криптиране. Съобщение, шифровано с еднопосочна функция, е безполезно - не може да бъде декриптирано. (Упражнение: напишете нещо с малки букви върху чиния, начупете чинията на качествени малки парчета (по-добре е да увиете чинията с парцал, докато правите това - така че парчетата да не летят изпод чука в различни посоки) и след това да ги дадете на приятел. Помолете го да прочете съобщението. Гледайте как ще бъде озадачен от еднопосочната функция.) За криптография с публични ключове имаме нужда от нещо друго.
Еднопосочна функция с капак е специален тип еднопосочна функция с тайна вратичка. Лесно е да се изчисли в едната посока и трудно в обратната. Но ако знаете тайната, можете лесно да изчислите и обратната функция. Тоест, лесно е да се изчисли f(x), дадено x, но е трудно да се изчисли x, дадено f(x). Въпреки това, има малка част от тайната информация, y, която позволява, като се имат предвид f(x) и y, лесно да се изчисли x.
Като добър пример за еднопосочна функция с люк, помислете за часовник. Лесно е да разделите часовник на стотици малки парчета и е трудно тези части да се сглобят обратно в работещ часовник. Но със секретна информация - инструкции за сглобяване - е много по-лесно да се реши този проблем.
Еднопосочни хеш функции
Еднопосочната хеш функция може да има много имена: функция за компресиране, функция за свиване, обобщение, подпис, криптографска контролна сума, проверка на целостта на съобщението (MIC) и код за откриване на манипулация (MDC). Както и да се нарича, тази функция е централна за съвременната криптография. Еднопосочните хеш функции са друга част от основата на много протоколи.
Хеш функциите, отдавна използвани в компютърните науки, са функции, математически или други, които приемат низ с променлива дължина (наречен предобраз) като вход и го преобразуват в низ с фиксирана, обикновено по-малка дължина (наречен хеш стойност). Като проста хеш функция, помислете за функция, която взема предобраз и връща байт, който е XOR на всички входни байтове.
Смисълът на хеш функцията е да се получи характерен признак на предобраза - стойността, по кояторазлични предобрази се анализират при решаването на обратния проблем. Тъй като хеш функцията обикновено е съотношение много към едно, не е възможно да се каже със сигурност, че два низа съвпадат, но те могат да се използват, за да се даде разумна оценка на точността.
Еднопосочната хеш функция е хеш функция, която работи само в една посока: лесно е да се изчисли хеш стойност от предобраз, но е трудно да се създаде предобраз, чиято хеш стойност е равна на дадена стойност. Хеш функциите, споменати по-рано, обикновено не са еднопосочни: даден конкретен байт, не е трудно да се създаде низ от байтове, които XOR дават дадената стойност. Не можете да направите това с еднопосочна хеш функция. Добрата еднопосочна хеш функция е хеш без сблъсъци - трудно е да се създадат две предобраза с еднаква хеш стойност.
Хеш функцията е отворена, няма тайна за нейното изчисляване. Сигурността на еднопосочната хеш функция се крие именно в нейната еднопосочна природа. Изходът няма видима зависимост от входа. Промяната на един бит от предварителното изображение променя средно половината от битовете на хеш стойността. Изчислително невъзможно е да се намери предобраз, който съответства на дадена хеш стойност.
Гледайте на това като на начин да получите характеристиките на файловете. Ако искате да проверите дали някой друг има същия файл като вас, но не искате файлът да ви бъде даден, помолете да ви бъде изпратена хеш стойността. Ако изпратената хеш стойност съвпада с изчислената от вас, тогава е почти сигурно, че файлът на някой друг съвпада с вашия. Това е особено полезно при финансови транзакции, при които не искате да превърнете теглене от $100 в теглене от $1000 някъде онлайн. При нормални обстоятелства можетеизползвайте еднопосочна хеш функция без ключ, така че всеки да може да провери хеш стойността.