Лекция: Шифрования Меркля-Хеллмана

В данном разделе дается описание криптосистемы Меркля-Хеллмана. Она была опубликована в 1978 году. В 1982 г. Шамир опубликовал эффективный способ ее вскрытия. Ее вскрытие впервые продемонстрировало мощь методов анализа, основанных на геометрии чисел. Положим F2={0,1}

Проблема укладки рюкзака.Пусть – натуральные числа. Рассмотрим две задачи.

Задача 1. Существует ли вектор, где, такой, что

.

Задача 2. Пусть указанный в формулировке задачи 1 вектор существует. Построить эффективный алгоритм его вычисления.

Заметим, что наличие эффективного алгоритма решения задачи 1 для всех натуральных приводит к решению задачи 2. Действительно, тогда и только тогда, когда ответ на вопрос, составляющий задачу 1 при заданных положителен. С другой стороны, эффективный алгоритм решения задачи 2 приводит к эффективному алгоритму решения задачи 1. Пусть — время, которое должен затратить алгоритм решения задачи 2 при заданных натуральных числах. Число можно полагать известным заранее. Таким образом, за время, не превосходящее, алгоритм должен выдать вектор такой, что

.

В этом случае ответ на вопрос задачи 1 положителен. Если алгоритм за время не найдет такой двоичный вектор, то ответ на вопрос задачи 1 отрицателен.

Таким образом, в указанном смысле задачи 1 и 2 эквивалентны по сложности.
В общем случае известны два способа решить задачу 1.

1) Перебирают всевозможные наборы и проверяют равенство. Очевидно, что в среднем надо выполнить O(2n) проверок. Таким образом, этот способ неэффективен.

2) Положим. Строят таблицу, элементами которой являются пар. Упорядочивают элементы таблицы по 1-ой координате. Для каждого вычисляют и проверяют, является ли первой координатой какой-либо пары из таблицы. Если да, то из равенства находят. То есть дает решение задачи. Этот способ требует О( ) операций сравнения чисел, не превосходящих, то есть также является неэффективным. К тому же, здесь требуется занять память, объем которой пропорционален .

Доказано, что задача 1 является NP-полной. То есть полиномиальный алгоритм ее решения позволяет построить полиномиальные алгоритмы решения известных сложных вычислительных задач дискретной математики, таких как выполнимость формул алгебры логики, вычисление клики в графе, заданном матрицей инцидентности, и многих других.

Система открытого шифрования Меркля-Хеллмана.При заданных натуральных числах определяют функцию

равенством .

Эта функция является однонаправленной. Действительно, ее значение очень легко вычислить. С другой стороны, по заданным натуральным числам и значению восстановить вектор в общем случае очень трудно, то есть надо решить задачу 2, которая эквивалентна по сложности NP-полной задаче 1. Однако в частных случаях задача обращения решается легко.

Последовательность натуральных чисел называется супервозрастающей, если

.

Например, последовательность – супервозрастающая. Доказательство следующего утверждения очевидно.

УТВЕРЖДЕНИЕ 1. Пусть – супервозрастающая последовательность,, где. Тогда тогда и только тогда, когда .

Из данного утверждения следует, что для супервозрастающей последовательности вычисление двоичного вектора по значению суммы может быть легко осуществлено. Действительно, пусть нашли. Тогда тогда и только тогда, когда, и так далее.

Криптосистема Меркля-Хеллмана основана на маскировке супервозрастающей последовательности. Пусть – супервозрастающая последовательность. Задаются два натуральных числа и такие, что. Полагают, где .

Шифр с открытым ключом определяют следующим образом. Множество открытых текстов. Если длина сообщения превышает, то оно разбивается на блоки длины. Блок, длина которого не равна, дополняется нулями. Множество блоков шифртекста есть, фактически, подмножество множества, состоящее из, где .

Алгоритм шифрования однозначно задается последовательностью. Это открытый ключ системы Меркля-Хеллмана. Секретным ключом является пара и супервозрастающая последовательность. Шифрование блока открытого текста заключается в вычислении суммы. Знаки двоичного разложения числа составляют соответствующий блоку открытого текста блок шифртекста.

Длина шифртекста в системе Меркля-Хеллмана больше длины открытого текста не более, чем в раз. Для конкретных параметров, предложенных в [1], это число равно приблизительно 2.

Для расшифрования вычисляют так, что, находят, где. По условию

.

Так как, то. Пользуясь сформулированным выше утверждением, легко вычисляют открытый текст .

Рассмотрим пример реализации системы Меркля-Хеллмана. Положим. Зададим супервозрастающую последовательность

и пару взаимно простых чисел где Таким образом мы определили секретный ключ в системе Меркля-Хеллмана. Для определения открытого ключа вычислим

Таким образом, = – открытый ключ в системе Меркля-Хеллмана.

Зашифруем сообщение, вычислив

.

Двоичное разложение числа равно Это есть шифртекст. Для расшифрования надо вычислить и

.

Отсюда по утверждению 1

Плотность последовательности натуральных чисел. Пусть – произвольная последовательность натуральных чисел. Плотностью этой последовательности называют величину

.

Таким образом, каждая конкретная последовательность натуральных чисел, которая является условием задачи 1 или задачи 2, характеризуется своей плотностью. В том числе последовательность в криптосистеме Меркля-Хеллмана.

Заметим, что из свойств супервозрастающей последовательности следует, что и так далее.

Таким образом, при. Так как, то. Имеем. Считают, что с точки зрения величины числа последовательности ведут себя как случайные вычеты по модулю. Поэтому с вероятностью среди них будут присутствовать числа не меньшие. Значит с большой вероятностью выполняется неравенство

при. Для конкретных значений параметров системы, предложенных Мерклем и Хэлманом в [1] выполнено при. Поэтому в этом случае. В разобранном примере

Заметим, что последовательность натуральных чисел не может быть открытым ключом в криптосистеме Меркля-Хеллмана, если ее плотность d. Действительно, неравенство

имеет место тогда и только тогда, когда при всех. Значит,

,

или среди чисел этой последовательности имеются повторения. В том и другом случае найдутся два различных открытых текста, которым соответствует один шифртекст. Это противоречит однозначности расшифрования в системе Меркля-Хеллмана.

Метод Шамира.Метод приводится обычно при следующих ограничениях на параметры криптосистемы Меркля-Хеллмана. При фиксированном и для секретного ключа и имеет место при и. Для конкретных значений параметров, зафиксированных в [1], выполнено и .

Алгоритм вскрытия криптосистемы находит [2] по открытому ключу пару натуральных чисел, таких, что

супервозрастающая последовательность, где

и

.

Доказано, что пару чисел и последовательность можно использовать для расшифрования любого текста, зашифрованного с использованием секретного ключа .

Алгоритм Лагариаса-Одлижко.Алгоритм Лагариаса-Одлижко [3] разработан для решения задачи 2 в случае, когда последовательность натуральных чисел имеет очень маленькую плотность. Пусть для вектора, имеет место

.

Требуется по заданным найти вектор .

Обычно считают, что. Если, то вместо ищут, решая уравнение

.

Изложение алгоритмов Шамира и Лагариаса-Одлижко достаточно сложное в связи с чем мы не приводим их. Для их изложения необходим предварительный раздел, посвященный геометрии чисел.

Литература.

1. Merkle R.C., Hellman M.E., Hidding information and signatures in trapdoor knapsacks, IEEE Transactions on Information Theory, 24 (1978), 525-530.

2. Shamir A. A polynomial – time algorithm for breaking the basic Merkle – Hellman cryptosystem. IEEE Trans. Inform. Theory. – 1984. – 30. – c. 699-704.

3. Odlyzko A.M. Discrete logarithms: The past and the future, preprint. – July 19, 1999.

Глава 46.