Я не є фахівцем в області теорії чисел. Тому я висловлюю свої думки у вигляді гіпотези, а не суворого докази. Адже Я теж можу помилятися. Для початку розглянемо систему шифрування з відкритим ключем. Передбачається, що якщо зловмисникові про систему з відкритим ключем відомо все, крім вихідного повідомлення A і секретного ключа d, то він або не може обчислити вихідне повідомлення A, або це обчислення вкрай трудомістким. Цього можна добитися, наприклад, якщо процес передачі повідомлення буде описуватися одним рівнянням з двома невідомими. Ідея систем з відкритим ключем шифрування дуже проста, красива і дуже приваблива. Ця простота і насторожує. Згадайте — «простота гірша за крадіжку». Аж надто все просто. Фантастично просто. Ось фантастикою і займемося.

Для початку формалізуємо постановку задачі шифрування з відкритим ключем. Нехай маємо A — початкове повідомлення, a — зашифроване повідомлення, E — функцію шифрування, e — відкритий ключ шифрування, D — функцію дешифрування і d — секретний ключ дешифрування. Опишемо процес передачі повідомлення:

1. a = E ( A, e )

2. A = D ( a, d )

Підставивши в (2) значення a з (1) ми одержуємо такий вираз, що описує процес передачі повідомлення в системі з відкритим ключем:

3. A = D ( E ( A, e ), d )

З допомогою системи з відкритим ключем передача повідомлень можлива тоді і тільки тоді, коли вибрані функції E і D такі, що для деяких значень e та d незалежно від вихідного повідомлення A вираз (3) звертається в тотожність. Введемо функцію G (генератор ключів) таку, що при заздалегідь заданому ключі e з рівняння (4) виходить ключ d, звертає (3) в тотожність для будь-якого значення A.

4. G ( e, d ) = 0

Вирішивши рівняння (4) відносно невідомого ключа і підставивши його значення в (3), отримуємо тотожність. За умовою зловмиснику невідомі тільки A і d, тому функція G йому також відома.

Тепер про фантастику. Кореспондент і зловмисник в системі шифрування з відкритим ключем поставлені в абсолютно однакові умови: для дешифрування повідомлення кожному з них необхідно розв’язати рівняння (4) відносно невідомого ключа. Тільки кореспондент це справляє перед відправкою повідомлення (при генерації пари e і d), а зловмисник — після перехоплення повідомлення (або після опублікування відкритого ключа e). Якщо вирішення цього рівняння вкрай трудомістким, то невідомо, хто швидше його дозволить: кореспондент або зловмисник.

Відразу ж виникає наступне питання: чи має сенс застосовувати систему шифрування з відкритим ключем, якщо її стійкість тисяча років? Адже це означає, що кореспондент зможе отримати працездатну пару e і d тільки через тисячу років після початку надсилання повідомлення. Якщо ж генерація пари e і d була виконана за кілька хвилин, і зловмисник витратить стільки ж часу для отримання секретного ключа дешифрування перехопленого їм зашифрованого повідомлення.

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

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

Алгоритм RSA

Нехай m і e натуральні числа. Функція f, що реалізує схему RSA, влаштована таким чином:

f: x -> xe (mod m)

Для дешифрування повідомлення a = f(x) досить розв’язати порівняння:

xe (mod m)

При деяких умовах на m і e це порівняння має єдине рішення x.

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

Давайте зауважимо одну дивну особливість у наведеному фрагменті тексту: дослідження властивостей функції f, що реалізує схему RSA, виконується в області чисел натурального ряду і заданих над ними операцій. Якщо придивитися уважніше, в правій частині кожного виразу можна бачити (mod m). В принципі, немає нічого поганого в тому, що дослідження операцій за модулем виконується на множині чисел натурального ряду. Лише б всі міркування були коректними, без помилок.

У роботах, присвячених дослідженню RSA, часто можна зустріти приблизно таку фразу: Дано два числа X і Y,… Згадаємо, що всі операції виконуються по модулю m, тобто кожне з цих чисел — залишок від ділення деякого числа натурального ряду на m. Отже, мова йде не про якомусь одному конкретному числі X, а про безліч чисел, яке задається наступним чином: x=A*m+X. Отже, якщо дослідження проводиться в області чисел натурального ряду, ця фраза має звучати так: Дано два набору чисел i*m+X j*m+Y,… Інакше ризикуємо довести, що 2 * 2 = 5.

Відразу ж виникає питання: чи можна користуватися функцією Ейлера? Може виявитися так, що завжди знайдуться такі i та j, що числа натурального ряду i*m+X j*m+Y ( 0

Враховуючи наведене вище опис властивостей системи з відкритим ключем, слід зауважити, що модуль m при використанні алгоритму RSA в системі шифрування з відкритим ключем є складовою частиною функцій E, D, G. Саме тому, рассмотриваются m в контексті системи шифрування з відкритим ключем, що базується на алгоритмі RSA, як щось самостійне не має сенсу. Це ми якраз зараз і побачили.

Для обчислення функції f: x -> xe (mod m) достатньо знати лише числа e і m. Саме вони складають відкритий ключ для шифрування. А ось для обчислення зворотної функції потрібно знати число d, воно і є «секретом», про який йде мова. Здавалося б, нічого не варто, знаючи число m, розкласти його на прості множники, обчислити потім за допомогою відомих правил ф(m) і, нарешті, з допомогою de = 1 (mod ф(m)), (0

Давайте зауважимо у цьому фрагменті тексту ще одну дивну особливість: ф(m) є модулем для операцій у порівнянні de є 1 (mod ф(m)), (0

Спробуйте перетнути наповнений водою басейн з прив’язаними до ніг пудовими гирями. Думаю, що не дивлячись на те, що це було продемонстровано в розділі «слабо» телевізійної передачі «сам собі режисер», ймовірність потонути все-таки вище. Математики теж іноді прив’язують собі «гирі» у вигляді обмежень. Ймовірність зробити помилку в міркуваннях стає значно вище. Але, разом з тим, правильні міркування стають більш вагомими. До речі, з приводу обмежень треба б помітити, що алгоритм RSA базується на операціях по модулю m, тобто в якості остаточного результату береться залишок від ділення на m результату операції з числами натурального ряду. Цікаво, а звідки у ділення ростуть вуха, якщо від його використання спочатку відмовилися?

Згадаймо, що лише практика є критерієм істини та спробуємо виконати віднімання за модулем. Ура! Вийшло! І найцікавіше, що віднімання має єдиний результат. Ось з поділом не все так очевидно. Хоча і для ділення можна показати, що результат ділення так само існує і має єдине значення. Це випливає хоча б з того, що поділ визначено, як операція, зворотна множенню. А при множенні множники і результат визначені.

Що нас чекає

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

Не все так погано

Сам по собі алгоритм RSA насправді володіє хорошою стійкістю. Але при одній умові, що публікувати можна тільки один ключ з трійки: e, d або m. Краще m. А ще краще — не публікувати взагалі.

P. S. В якості прикладу використані фрагменти тексту з книги «Введення в криптографію» (об.ред.В.В.Ященко — М.: МЦНМО, «ЧеРо», 1998).