Алгоритми з відкритим ключем

Процес передачі ключа завжди був слабкою ланкою майже у всіх системах шифрування. Незалежно від того, наскільки міцною була сама криптосистема, якщо порушник міг украсти ключ, система ставала марною. До 1976 р. всі криптологи виходили з передумови, що ключ дешифрування ідентичний ключу шифрування. У той же час ключі повинні були мати всі користувачі системи. Таким чином, здавалося, що ця проблема непереборна: ключі повинні бути захищені від крадіжки й у той же час їх потрібно поширювати серед користувачів, тому їх не можна просто зберігати у банківському сейфі.

У 1976 р. два дослідники зі Стэнфордського університету, Діффі (Diffie) і Хеллман (Hellman), запропонували радикально нову криптосистему, в якій ключ шифрування й ключ дешифрування були різними, крім того, ключ дешифрування не можна було одержати із ключа шифрування.

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

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

Найбільш відомим алгоритмом шифрування з відкритим ключем є алгоритм RSA,розроблений групою дослідників Массачусетського технологічного інституту. Він названий за початковими літерами прізвищ трьох розробників: RSA (Rivest, Shamir, Adleman). В основі цього методу лежать деякі принципи теорії чисел. Надійність методу ґрунтується на складності знаходження множників великих чисел.

Рівест (Rivest) з колегами стверджує, що розкладання на множники числа з 200 десяткових цифр вимагатиме 4 млрд. років комп'ютерного часу, а числа з 500 цифр — 10²⁵ років. В обох випадках передбачається найкращий відомий алгоритм і комп'ютер, що виконує одну інструкцію за 1 мкс.