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

Щоб вирішити цю проблему, можна шифрувати за допомогою іншого вектора. З цією метою вибирають:*

число ;

У цьому випадку немає жодних підстав стверджувати, що нова послідовність аi' буде суперзростаючою. Далі отриману послідовність за певним правилом перестав-ляють і отриманий таким способом результат подають як публічний ключ. Приватним ключем будуть вектор (a1 ..., аn), числа М і W, а також використана перестановка.

Шифрування й дешифрування. Для простоти приймемо, що перестановку не ви-користовують. Біти і1,...,in шифрують стандартним способом за допомогою послідовності, що є явним ключем. Обчислена криптограма дорівнює числу

Дешифрування можливе після такого перетворення криптограми. Нехай у = i1 a1’+ ... + іп а'п - криптограма, яку розглядаємо. Оскільки числа W і М є взаємно простими, то за допомогою алгоритму Евкліда отримуємо число W (mod M). Обчис-люємо W-1y(mod M):

.

Для криптофами W-1y(modM) і суперзростаючого вектора а1 ..., an знаходимо явний текст i1,...,in„ на підставі таких міркувань.

Нехай є криптограмою. Зазначимо, що іn = 1 тоді і тільки тоді, коли k= > аn оскільки Тоді біт in можна легко обчислити. Знайшовши in, отримуємо к' = к – іn аn і суперзростаючий вектор (a1 ...,an-1). Криптограма к' відповідає цьому вектору та явному тексту i1,…,in-1. Аналогічно, як і раніше, тепер можемо знайти in-1. Повторюємо ці дії доти, доки не отримаємо всі біти ij.

Як уже зазначено, описаний алгоритм не можна застосовувати на практиці, бо знайдено метод дешифрування за прийнятний час без знання таємного ключа. Це не означає, що знайдено алгоритм, який за прийнятний час розв'язує NР-повну задачу про вкладання рюкзака.

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

Додамо, що існує алгоритм шифрування (Хор-Райвест), який ґрунтується на проблемі заповнення рюкзака, та досі не розкритий.

Криптосистема RSA

Система шифрування з відкритим ключем RSA запропонована 1977 р. Назва сис-теми утворена з початкових букв прізвищ її авторів (R.Rivest, A.Shamir і L.Adleman).

Ця система є криптосистемою, стійкість якої ґрунтується на складності розв'язу-вання задачі розкладу числа на прості співмножники.

Система RSA потребує для реалізації значну кількість арифметичних операцій. Тому швидкість шифрування й дешифрування для неї є значно нижчою (приблизно у : 000 разів), ніж для симетричного шифру DES.

Специфічні застосування RSA. Нехай ключ К1 є приватним, а ключ К2 - пуб-лічним ключем деякої особи А. Завдяки виконанню умови

DK1(EK2(x)) = EK1(DK2(x)) = х ту саму пару ключів К1, К2 можна використати з різною метою.

Шифрування кореспонденції. Нехай особа В хоче надіслати лист М особі А. З цією метою В обчислює Ек2(М) і надсилає результат А. Особа А отримує ЕК1(М) й обчислює DK1(Ek2(M)) = М. Не знаючи ключа К1, практично неможливо дешифрувати Еk2(М). А тому лише особа А може прочитати призначений їй лист від особи В.

Підтвердження. Нехай особа А хоче розіслати повідомлення Т, підтверджуючи водночас, що є його автором. Для цього А шифрує Т як ЕК1{Т). Кожен адресат дешифрує повідомлення за допомогою публічного ключа К2 як Dk2 (Ek1 (T)) = Т.

Алгоритм RSA

Нехай маємо певну систему з великою кількістю користувачів, і кожен з них може надіслати таємне повідомлення до іншого. Одиницями явного тексту є цілі числа з вибраного користувачем діапазону. Повідомлення може складатися з блоків літер абет-ки, наприклад, української. Кожна літера відображена своїм номером у абетці (нагаду-ємо, що нумерацію літер починають з нуля). Водночас зазначимо, що повідомлення не обов'язково повинно бути текстом. Це може бути будь-яка інформація: звуковий сиг-нал, зображення (світлина чи фільм), база даних тощо. На практиці одиниці явного тексту мають приблизно від 200 до 600 десяткових знаків.

Кожен користувач діє так.

Вибір ключа. Випадково вибирає два великі прості числа р і q та обчислює їхній добуток п = pq. Випадково вибирає число e таке, що e < ф(п) - (р - 1)(q - 1), де ф(п) - значення функції Ейлера для п. Число є повинно бути того самого порядку, що й число п і, крім того, числа e та ф(п) повинні бути взаємно простими: НСД (e, ф(п)) = 1. Інакше кажучи, е є Z* ф(n). За допомогою алгоритму Евкліда обчислює число d, що задовольняє умову

ed l(mod ф(п)).

У цьому разі, пара е, п є утвореним публічним ключем, а число d - утвореним приватним ключем в алгоритмі RSA.

Шифрування. Шифрувати можна числа з проміжку 0 < т < п. Шифрування поля-гає в обчисленні значень:

Е(т) = тe mod n.

Тоді для блока явного тексту т отримуємо криптограму сЕ(т).

Дешифрування полягає в обчисленні значень

D(c) = cd mod n.

Приклад 3.14. Нехай p = 59 і q = 71. Тоді n = 4189 і ф(п) = 4060. Вибираємо число е= 1229. Обчислюємо за допомогою алгоритму Евкліда НСД( 1229, 4060) = 1. Одночасно обчислюємо значення d= 1229-1 mod 4060 = 849. Згенеровано ключі: 1229, 4189 - публічний, 849 - приватний.

Що робить користувач В, коли хоче, наприклад, надіслати абоненту