Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
Однако задача о рюкзаке с быстрорастущим набором несравненно проще. А именно, просмотрим (упорядоченный по убыванию) список Vi, начиная с наибольшего, до тех пор, пока не найдем первый элемент, который не превосходит V. Соответствующее значение г мы включим в наше множество / (т.е. положим S{ = 1), заменим V на V — v{ и продолжим простмотр списка Vi по убыванию, пока опять не найдем элемент, не превосходящий эту разность. Продолжая действовать таким способом, мы, очевидно, построим подмножество элементов Vi, в сумме равных V, или же исчерпаем все элементы U;, не доведя разность V — Y^i^i Vi до нуля, что будет в случае, когда задача не имеет решения. Теперь мы запишем алгоритм решения в более формальном виде, удобном для преобразования в компьютерную программу.
Следующий алгоритм (полиномиальной сложности) решает задачу о рюкзаке при заданном быстрорастущем наборе {i>j} и целом V.
1. Положим W равным VaJ равным к.
2. Начиная с и последовательно уменьшая j, полагаем все Sj = 0 до тех пор, пока не придем к первому такому значению і (обозначаем его через Z0), что и,-0 ^ W. Положим ?,0 = 1.
3. Заменим W на W — vio, положим j = го и, если W > 0, то переходим к шагу 2.
4. Если W = 0, то цель достигнута. Если W > 0 и все оставшиеся V1 больше W, то ясно, что решения п = (єк-і •¦¦?0)2 нашей задачи не существует. Заметим, что решение, если оно есть, единственно.
Пример 2. Пусть Vi те же, что в примере 1, а V = 24. Тогда, проходя пятерку {2,3,7,15,31} справа налево, мы видим, что ?4 = О, ?3 = 1 (в этот момент мы заменяем 24 на 24 - 15 = 9), ?2 = 1 (в этот момент мы заменяем 9 на 9 — 7 = 2), е\ = 0, ?о = 1. Таким образом, п = (0UOl)2 = 13.
Теперь мы опишем, как построить рюкзачную криптосистему (называемую также системой Меркля-Хеллмана). Сначала предположим, что элементы открытого текста имеют в качестве своих числовых эквивалентов А;-разрядные двоичные числа Р. Например, если мы имеем дело с отдельными буквами 26-буквенного алфавита, то каждой букве естественным образом ставится в соответствие свое пятиразрядное двоичное число от 0 = (0000O)2 до 25 = (HOOl)2.
Далее каждый пользователь выбирает быстрорастущий набор
§ 4. ЗАДАЧА О РЮКЗАКЕ
125
{vq, ..., Vk-\}; Целое число тп, большее v0 + ¦•• + v^-i, и взаимно простое с т целое число а, 0 < а < т. Это делается с помощью случайной процедуры. Например, мы можем выбрать произвольно
Последовательность ИЗ к + 1 ПОЛОЖИТеЛЬНЫХ ЦеЛЫХ ЧИСеЛ Zq,..., Zk, МеНЬШИХ Некоторого ПОДХОДЯЩеГО предела, ПОЛОЖИТЬ TJ0 = Zq, Vi = Z1 + V{_i + Vi_2 + ¦ ¦¦ + V0 ДЛЯ І = 1, . . . , к - 1 И ГП = Zk + Y2i = 0 vi-
Затем мы можем выбрать случайно положительное а0 < то и выбрать а как наименьшее целое, большее или равное а0, которое взаимно просто с то. После этого вычисляются b = a (modm) (т.е. b является наименьшим положительным целым, удовлетворяющим условию ab = 1 (mod то)) и fc-элементный набор {wi}, определяемый равенствами Wi = avi (mod то) (т.е. Wi является наименьшим положительным вычетом avi по модулю то). Пользователь держит числа Vi, то, а и b в секрете, а набор {Wi} делает общеизвестным. Таким образом, ключом шифрования K^ является набор {w0,.. ., wk-i}, а ключом дешифрования Kd — пара (Ь,т) (которая вместе с ключом шифрования позволяет определить набор {г>0,..., vk-\})-
Желающий передать сообщение P = (Sk-i, ¦ ¦ ¦,?\,?о) пользователю с ключом ШИфрОВаНИЯ {Wi} ВЫЧИСЛяеТ С = f(P) = YlIi = q ?iWi и
передает это целое число.
Чтобы прочитать это сообщение, пользователь сначала находит наименьший положительный вычет V числа ЬС по модулю то. Так как ЬС = Yl?i^wi = Yl?ivi (m°d то) (поскольку bwi = bavi = г>; (mod то)), то V = Yl?ivi- (Здесь мы воспользовались тем фактом, что каждое из условий V < то и 2~l?ivi ^ Yl vi < т превращает сравнение по модулю то в равенство.) Теперь можно воспользоваться приведенным выше алгоритмом для задачи о рюкзаке с быстрорастущим набором и найти единственное решение [ек-г ¦ ¦ •?0)2 = P задачи о подмножестве {г>,} с суммой, равной V. Так мы восстанавливаем сообщение Р.
Заметим, что злоумышленнику, знающему только набор [wi], придется решать задачу о рюкзаке С = Yl EiWi уже не с быстрорастущим набором, поскольку свойство быстрого роста {г>;} разрушается умножением на а и приведением по модулю то. Поэтому приведенный выше алгоритм уже нельзя использовать, и возникающая перед злоумышленником задача кажется значительно более сложной. Мы вернемся к этому позднее.
Пример 3. Предположим, что элементами открытого текста являются буквы 26-буквенного алфавита, которым, как и выше, отвечают двоичные числа от 0 = (0000O)2 до 25 = (HOOl)2, а наш секретный ключ дешифрования — это быстрорастущий набор из примера 1. Выберем то = 61, а = 17. Тогда b = 18 и ключ шифрования — это
126
ГЛ. IV. ОТКРЫТЫЙ КЛЮЧ
набор (34, 51, 58, 11, 39). Чтобы послать сообщение «WHY», наш корреспондент должен вычислить «VF»= (10110)2 >-> 51 + 58 + 39 = 148, «Н»= (0011I)2 ь-» 34 + 51 + 58 = 143, «У»= (HOOO)2 ¦-> 11 + 39 = 50. Чтобы прочитать сообщение 148, 143, 50, мы сначала умножаем эти числа на 18 и приводим результаты по модулю 61; получаем 41, 12, 46. Далее, взяв поочередно V = 41, V = 12 и V = 46 и проведя такие же рассуждения, как в примере 2, мы восстановим сообщение (1011O)2, (00Hl)2, (HOOO)2.
