6. Криптоаналіз алгоритмів з відкритим ключем

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

У цій моделі Єва перехоплює відкритий ключ   , Посланий Бобом Алісі. Потім створює пару ключів   і   , "Маскується" під Боба, посилаючи Алісі відкритий ключ   , Який, як думає Аліса, відкритий ключ, посланий їй Бобом. Єва перехоплює зашифровані повідомлення від Аліси до Боба, розшифровує їх за допомогою секретного ключа   , Заново зашифровує відкритим ключем   Боба і відправляє повідомлення Бобу. Таким чином, ніхто з учасників не здогадується, що є третя особа, яка може як просто перехопити повідомлення   , Так і підмінити його на хибне повідомлення   . Це підкреслює необхідність аутентифікації відкритих ключів. Для цього зазвичай використовують сертифікати. Розподілене управління ключами в PGP вирішує проблему за допомогою поручителів. 

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

Більшість криптосистем з відкритим ключем засновані на проблемі факторизації великих чисел. Приміром, RSA використовує в якості відкритого ключа n добуток двох великих чисел. Складність злому такого алгоритму полягає в труднощі розкладання числа n на множники. Але це завдання вирішити реально. І з кожним роком процес розкладання стає все швидше. Нижче наведені дані розкладання на множники за допомогою алгоритму "Квадратичне решето".

Рік	Число десяткових розрядів  в розкладеному числі	У скільки разів складніше розкласти  на множники 512-бітове число
1983	71	> 20 млн
1985	80	> 2 млн
1988	90	250 тис.
1989	100	30 тис.
1993	120	500
1994	129	100

Також задачу розкладання потенційно можна вирішити за допомогою Алгоритму Шора при використанні досить потужного квантового комп'ютера.

Для багатьох методів несиметричного шифрування криптостійкість, отримана в результаті криптоаналізу, істотно відрізняється від величин, які заявляються розроблювачами алгоритмів на підставі теоретичних оцінок. Тому в багатьох країнах питання застосування алгоритмів шифрування даних знаходиться в полі законодавчого регулювання. Зокрема, в Росії до використання в державних і комерційних організаціях дозволені тільки ті програмні засоби шифрування даних, які пройшли державну сертифікацію в адміністративних органах, зокрема, в ФСБ, ФСТЕК.