В настоящий момент наиболее распространенными системами шифрования с открытым ключом являются системы RSA и Эль-Гамаль. Их применение требует больших вычислительных мощностей, а практическая реализация алгоритмов требует решения таких проблем, как быстрое выполнение вычислений с числами, состоящими из сотен десятичных разрядов. Однако RSA и Эль-Гамаль - не единственные алгоритмы шифрования с открытым ключом. Существует целая группа асимметричных криптоалгоритмов, основанных на задаче об укладке ранца. С этой задачей сталкивался каждый, кто хоть раз пытался упаковать много вещей в маленькую емкость. Математически это можно объяснить следующим образом. Пусть задан массив чисел A_n={a₁,a₂...a_n} и число S. Необходимо найти такие элементы массива, чтобы их сумма была равна S. Или, другими словами, сформировать такой двоичный массив K_n, чтобы скалярное произведение A_n на K_n было равно S. При произвольном массиве A_n решение этой задачи очень трудоемко - требуется перебор до 2ⁿ вариантов. Однако, если массив A_n является неубывающим (каждый следующий элемент больше суммы всех предыдущих), то решение (если оно существует) может быть найдено очень легко. Например, можно воспользоваться следующим простейшим кодом на Java:

int [] Matrix = {1, 3, 8, 14, 29, 61, 129, 247};
int [] Vector = new int [8];
int Value = 394;
for (int i=7;i>=0;i-) {
 if (Value >= Matrix[i]) {
 Value-=Matrix[i];
 Vector[i]=1;
 } else {Vector[i]=0;};
}

Первая (но не единственная) система шифрования, основанная на задаче об укладке ранца, была разработана Мэркли и Хеллманом. В качестве закрытого ключа используется неубывающий массив чисел A_n, состоящий из ста и более элементов, число m, большее суммы всех элементов A_n, число w, взаимно простое (не имеющее общих делителей, кроме 1) с m, и число u, такое, что u*w mod m = 1. Открытый ключ B_n вычисляют по формуле b_i = a*w mod m. Эта операция может быть проделана несколько раз (с новыми w и m), что повышает стойкость к взлому, и, кроме того, элементы Bn могут быть переставлены, что также затрудняет взлом. Для шифрования сообщение разбивается на блоки длиной по n бит, и для каждого блока вычисляется скалярное произведение

,

где c_i - биты сообщения. Для дешифрования вычисляется P = S*u mod m, а затем применяется алгоритм разложения по A_n (см. исходный текст).

Покажем весь процесс на примере. Пусть массив A_n = {1, 3, 8, 14, 29, 61, 129, 247}, m=493, w=158, u=415. Следовательно, открытый ключ B_n = {158, 474, 278, 240, 145, 271, 169, 79}. Зашифруем сообщение С = {1,1,0,1,0,0,1,1} - S = 1120. Для дешифрования вычисляем P = 1120*415 mod 493 = 394. Раскладываем P по A_n и получаем исходное сообщение С.

Криптосистема Мэркли-Хеллмана может быть вскрыта двумя способами - полным перебором либо при помощи криптоанализа. В первом случае взломщику необходимо перебирать значения битового блока, шифровать их и сравнивать полученные значения с перехваченным. При использовании массива, состоящего из 128 элементов, взломщик должен проверить до 2¹²⁸ вариантов, что является очень сложной задачей (если не сказать - невозможной), и, кроме того, подобная техника не дает никакой информации о закрытом ключе. Подобрав один 128-битовый блок, взломщик должен будет продолжать подбор для следующих блоков сообщения. Взлом при помощи криптоанализа является более изощренным и позволяет получить информацию о закрытом ключе. Существуют специальные методики, основанные на некоторых особенностях закрытого ключа, позволяющие получить примерные значения чисел u и m по открытому ключу. Для приведенного примера восстановление четырех возможных вариантов закрытого ключа занимает меньше 2 секунд на Pentium 150 MHz. А криптосистема с массивом из 100 элементов, скрытым за 40 итераций, была взломана специалистом Sandia National Labs. Э.Брикеллом за час работы суперкомпьютера Cray-1. Если передаваемая информация стареет за несколько суток, а вероятным взломщиком является не NSA или Sandia, а хакер-самоучка (и у него под столом не стоит пыльный Cray), то криптосистема Мэркли-Хеллмана вполне криптостойка. Кроме того, существуют и другие системы шифрования, которые могут быть отнесены к ранцевым, для которых взлом еще более затруднен.

А.В.БЫЧЕНКОВ,
[email protected]