Поняття про однобічні функції і функції з лазівками.

Такі криптосистеми називаються асиметричними або системами з відкритими ключами.

Задачі криптології, що привели до асиметричних шифрів.

Основні принципи асиметричної криптографії

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

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

Обидві ці задачі, без використання захищеного каналу зв'язку, удалося вирішити в рамках моделі криптосистему з «відкритим» ключем, запропонованої В.Диффи і М.Хеллманом у 1976 році.

Відмінність моделі системи секретного зв'язку В.Диффи і М.Хеллмана від моделі К.Шеннона в тім, що вона є асиметричною у тому сенсі, що користувачі стосовно секретного параметра нерівноправні. Повністю ключ відомий тільки одержувачу повідомлення і являє собою пару де подключ (т.зв. відкритий ключ) служить ключем зашифрування, а подключ служить для расшифрования, при цьому тільки є секретним параметром (т.зв. секретний, особистий, приватний ключ).

Ключ відомий тільки одержувачу повідомлень, які відправники повинні шифрувати, використовуючи ключ .

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

Строго кажучи, не доведено, що однобічні функції існують. Однак визнано, що деякі перетворення мають властивості, близьки до властивостей однобічних функцій.

Функція , при великих значеннях і , поводиться як однобічна. Реалізовати зворотню функцію (дискретний логарифм) обчислювально неможливо. Аналогічні властивості має степенева функція виду , де .

Для обернення цієї функції досить розв’язати задачу факторизації - розкладання числа на співмножники. Задача факторизації натурального числа і задача дискретного логарифмування є алгоритмічними проблемами теорії чисел.

Абонент, що бажає передати ключ для симетричної криптосистеми, перешифровує його ключем одержувача (вважається, що асиметрична система створена заздалегідь і відкритий ключ опублікований). Однобічна функція гарантує безпеку, тому що розшифрувати повідомлення можна тільки знаючи ключ , а його знає лише потрібний абонент. Загальновідомо, що даний механізм проте не є безпечним. На практиці виявилося необхідним вводити в глобальному масштабі систему т.зв. центрів сертифікації відкритих ключів. Центр сертифікації відіграє роль довіреної особи, яка підтверджує, що повідомлення, зашифроване даним відкритим ключем, зможе розшифрувати саме той абонент, для якого це повідомлення призначалося.