В настоящий момент наиболее распространенными системами шифрования с открытым ключом являются системы RSA и Эль-Гамаль. Их применение требует больших вычислительных мощностей, а практическая реализация алгоритмов требует решения таких проблем, как быстрое выполнение вычислений с числами, состоящими из сотен десятичных разрядов. Однако RSA и Эль-Гамаль - не единственные алгоритмы шифрования с открытым ключом. Существует целая группа асимметричных криптоалгоритмов, основанных на задаче об укладке ранца. С этой задачей сталкивался каждый, кто хоть раз пытался упаковать много вещей в маленькую емкость. Математически это можно объяснить следующим образом. Пусть задан массив чисел An={a1,a2...an} и число S. Необходимо найти такие элементы массива, чтобы их сумма была равна S. Или, другими словами, сформировать такой двоичный массив Kn, чтобы скалярное произведение An на Kn было равно S. При произвольном массиве An решение этой задачи очень трудоемко - требуется перебор до 2n вариантов. Однако, если массив An является неубывающим (каждый следующий элемент больше суммы всех предыдущих), то решение (если оно существует) может быть найдено очень легко. Например, можно воспользоваться следующим простейшим кодом на 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;};
}
Первая (но не единственная) система шифрования, основанная на задаче об укладке ранца, была разработана Мэркли и Хеллманом. В качестве закрытого ключа используется неубывающий массив чисел An, состоящий из ста и более элементов, число m, большее суммы всех элементов An, число w, взаимно простое (не имеющее общих делителей, кроме 1) с m, и число u, такое, что u*w mod m = 1. Открытый ключ Bn вычисляют по формуле bi = a*w mod m. Эта операция может быть проделана несколько раз (с новыми w и m), что повышает стойкость к взлому, и, кроме того, элементы Bn могут быть переставлены, что также затрудняет взлом. Для шифрования сообщение разбивается на блоки длиной по n бит, и для каждого блока вычисляется скалярное произведение
,
где ci - биты сообщения. Для дешифрования вычисляется P = S*u mod m, а затем применяется алгоритм разложения по An (см. исходный текст).
Покажем весь процесс на примере. Пусть массив An = {1, 3, 8, 14, 29, 61, 129, 247}, m=493, w=158, u=415. Следовательно, открытый ключ Bn = {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 по An и получаем исходное сообщение С.
Криптосистема Мэркли-Хеллмана может быть вскрыта двумя способами - полным перебором либо при помощи криптоанализа. В первом случае взломщику необходимо перебирать значения битового блока, шифровать их и сравнивать полученные значения с перехваченным. При использовании массива, состоящего из 128 элементов, взломщик должен проверить до 2128 вариантов, что является очень сложной задачей (если не сказать - невозможной), и, кроме того, подобная техника не дает никакой информации о закрытом ключе. Подобрав один 128-битовый блок, взломщик должен будет продолжать подбор для следующих блоков сообщения. Взлом при помощи криптоанализа является более изощренным и позволяет получить информацию о закрытом ключе. Существуют специальные методики, основанные на некоторых особенностях закрытого ключа, позволяющие получить примерные значения чисел u и m по открытому ключу. Для приведенного примера восстановление четырех возможных вариантов закрытого ключа занимает меньше 2 секунд на Pentium 150 MHz. А криптосистема с массивом из 100 элементов, скрытым за 40 итераций, была взломана специалистом Sandia National Labs. Э.Брикеллом за час работы суперкомпьютера Cray-1. Если передаваемая информация стареет за несколько суток, а вероятным взломщиком является не NSA или Sandia, а хакер-самоучка (и у него под столом не стоит пыльный Cray), то криптосистема Мэркли-Хеллмана вполне криптостойка. Кроме того, существуют и другие системы шифрования, которые могут быть отнесены к ранцевым, для которых взлом еще более затруднен.
А.В.БЫЧЕНКОВ,
eris-by@mail.ru
Версия для печати
