Криптосистемы Меркля-Хеллмана и Хора-Ривеста
Криптосистемы Меркля-Хеллмана и Хора-Ривеста основаны на использовании односторонней функции, известной под названием "задача укладки рюкзака.
Пусть имеется n объектов, так что можно составить n-компонентный вектор f, так что i-й компонент f
представляет собой место, занимаемое i-м объектом. Имеется рюкзак общим объемом K.
Теперь задачу укладки рюкзака может быть сформулирована следующим образом: нам даны f и K, и требуется найти битовый вектор x, такой что fx=K. Доказано, что не существует эффективного алгоритма вычисления x по f
и K в общем случае. Таким образом, мы можем использовать вектор f
для шифрования n-битового сообщения x путем вычисления произведения K = fx.
Важно отметить, что выбор f является критическим. Например, предположим, что f выбирается в виде супервозрастающей последовательности. В этой ситуации для любого i
В этом случае при данных f и К
вычислить x очень просто. Мы проверим, является ли K
большим, чем последний элемент f, и если да, то мы делаем последний элемент x равным 1, вычитаем это значение из K и рекурсивно решаем меньшую проблему. Этот метод работает, поскольку когда K
больше последнего элемента f, даже если мы выберем x=(1 1 1 … 1 0), то произведение fx все равно будет слишком маленьким, благодаря тому, что последовательность супервозрастающая. Таким образом, мы должны выбирать 1 в последней позиции x.
Ясно, что выбор f очень важен – в зависимости от f мы можем получить, а можем и не получить одностороннюю функцию. Однако, именно существование этого простого случая позволяет нам создать функцию-ловушку, которую мы можем использовать для построения криптосистемы с открытым ключом.
Пользователь A получает свой открытый ключ следующим образом:
1. Выбирает супервозрастающую последовательность f' примерно из 100 элементов;
2. Выбирает случайное целое m, большее суммы элементов f';
3. Выбирает другое случайное целое w, взаимно простое с m.
4. Теперь вычисляется f'' умножением каждого компонента f'
на w по модулю m;
f'' = f'w
(mod m)
5. И наконец, проводится случайная перестановка P элементов f''
для получения открытого ключа f.
Теперь А раскрывает ключ f и держит в секрете f', m, w и P.
Когда пользователь B хочет послать А сообщение (битовый вектор) x, он вычисляет S = fx и посылает это вычисленное S. Если данная система является стойкой, тогда для внешнего наблюдателя С вычисление x по S и публичному ключу f будет эквивалентно решению задачи рюкзака в общем случае. Допустим, что предположение о стойкости верно. В этом случае, хотя С не может расшифровать сообщение, А может это сделать, применяя секретные значения, которые она использовала при вычислении f.
Пользователь А может вычислить S’=f'x, так что она сможет решить задачу рюкзака в случае супервозрастающей последовательности. Вычисление S’ производится следующим образом.
Таким образом, A просто умножает S на мультипликативное обратное w по модулю m, а затем решает задачу рюкзака в случае супервозрастающей последовательности f’, и теперь она сможет прочитать сообщение.
При получении ключа мы начинаем с супервозрастающей последовательности и затем скрываем имеющуюся в ней структуру. Другими словами, построенная последовательность выглядит так, что в ней нет никакой структуры. Но система может быть сделана еще более стойкой (или, по крайней мере, так будет казаться) путем повторения этого процесса скрытия структуры. Если мы выберем другие m и w, тогда мы сможем построить новый открытый ключ, который не может быть построен с использованием единственной пары (m,
w). Мы можем повторять это снова и снова, и система выглядит все более и более стойкой с каждой итерацией.
В 1982 г Эди Шамир открыл атаку на криптосистему, использующую одну итерацию. Это оказалось началом падения систем, основанных на задаче рюкзака.
Допустим, что перестановка не применяется, так что f'' = f. Тогда для любого i
fi є f'iw mod m
По определению модульной конгруэнтности должен существовать вектор k, такой что для любого i
ufi – mki = f'i
где u – это мультипликативное обратное к w по модулю m (напомним, что мы выбирали m и w взаимно простыми, так что это обратное существует). После этого в результате деления получаем:
Поскольку m очень велико, выражение справа будет очень маленьким, поэтому покомпонентное частное k
и f близко к u/m. Подставляя вместо i 1 и вычитая из первоначального уравнения, получим:
Поскольку обе величины справа положительны и вычитаемое очень мало, мы можем записать:
Также заметим, что поскольку f'
супервозрастающая, каждый элемент должен быть меньше половины следующего, поэтому для любого i имеем:
f'i
< m Ч 2i–n
Далее мы можем записать:
После несложных преобразований получаем:
|ki
Ч f1 – k1 Ч fi| < f1 Ч 2i–n
Оказывается, что поскольку f открыт, всего лишь несколько этих неравенств (три или четыре) однозначно определяют k. Эти неравенства относятся к области целочисленного программирования, поэтому k
можно быстро найти, например, с помощью алгоритма Ленстры. А если мы знаем k, то мы можем легко раскрыть систему.
Допустим, что мы выполним перестановку f до опубликования, т.е. P не является идентичной. Поскольку нам нужны только первые 3 или 4 элемента k, мы можем просто перебрать все варианты, количество которых определяется третьей или четвертой степенью размерности k.
В дальнейшем были разработаны методы вскрытия систем, использующих несколько итераций, и в настоящее время любая система, использующая модульное умножение для скрытия легко разрешимой задачи рюкзака, может быть эффективно раскрыта. Однако, рассмотренный метод не является единственным способом применения задачи рюкзака в криптографии.
В 1986 г. Бен-Цион Хор предложил криптосистему, на сегодняшний день единственную, не использующую модульное умножение для скрытия простой задачи укладки рюкзака. Это также единственная система, основанная на задаче укладки рюкзака, которая не раскрыта.
Во-первых, отметим, что любая супервозрастающая последо вательность должна расти экспоненциально, поскольку минимальная супервозрастающая последовательность – это степени двойки. Во-вторых, отметим, что причина, по которой используются супервозрастающие последовательности заключается в том, что любая h-элементная сумма из нее уникальна.
Другими словами, если мы представим нашу последовательность в виде вектора f, функция скалярного произведения f на битовый вектор x будет однозначна и поэтому может быть обращена. Но оказывается возможным построить последовательность, растущую только полиномиально, но сохраняющую свойство единственности h-элементных сумм. Конструкция такой последовательности была опубликована в 1962 г.
Пусть GF(p) – поле целых чисел по модулю простого числа p, и GF(ph) – расширение степени h основного поля. Также пусть 1 – вектор, все элементы которого равны 1.
С формальной точки зрения мы строим последовательность длины p, такую что для любого i от 0 до p – 1
1 Ј ai Ј ph – 1
и для каждых различных x, y, таких что x*1 = y*1 = h, x*a
и y*a также должны быть различны. Мы можем представлять векторы x
и y как битовые (т.е. содержащие только 0 и 1).
Далее построение проводится довольно просто. Во-первых, выберем t – алгебраический элемент степени h над GF(p), т.е. минимальный многочлен с коэффициентами из GF(p), корнем которого является t, имеет степень h. Далее выберем g – мультипликативный генератор (примитивный элемент) поля GF(ph), т.е. для каждого элемента x из GF(ph) (кроме нуля) существует некоторое i, такое, что g в степени i
будет равно x.
Теперь рассмотрим аддитивный сдвиг GF(p), т.е. множество
t + GF(p) = {t + i
| 0 Ј i Ј p – 1 } М GF(ph)
Пусть каждый элемент вектора a будет логарифмом по основанию g соответствующего элемента из t+GF(p):
ai
= logg(t+i)
Мы должны проверить, что a, определенная подобным образом, удовлетворяет заданным свойствам. Определенно, каждый элемент в a
будет лежать в заданном диапазоне, поскольку g порождает GF(p,h). Теперь пусть у нас есть различные x и y, такие что x*1 = y*1 = h, но x*a = y*a. Тогда, возводя g
в степень x*a и y*a, получим:
Поэтому мы также можем записать
и далее
Теперь заметим, что произведение в обеих частях неравенства представляет собой приведенный многочлен от t степени h. Иными словами, если бы мы вычислили оба этих произведения и заменили значение t
формальным параметром, например, z, тогда старшим членом на каждой стороне был бы x в степени h с коэффициентом 1. Мы знаем, что если мы подставим значение t вместо z, то значения этих двух полиномов будут равны. Поэтому вычтем один из другого, старшие члены сократятся, и если мы подставим t, то получим 0. Мы получили полином степени h–1, корнем которого является t. Но это противоречит тому, что мы выбрали t алгебраическим элементом степени h. Таким образом, доказательство закончено и построение корректно.
Хор разработал метод использования данного построения в качестве основы криптосистемы. Кратко он заключается в следующем. Мы выбираем p
и h достаточно маленькими, чтобы мы могли вычислять дискретные логарифмы в GF(ph). Хор рекомендует p около 200, а h
около 25. Затем мы выбираем t и g как указано выше. Для каждого из них будет много вариантов, и мы можем просто произвести случайный выбор (В действительности, будет так много пар <t,g>, что очень большое количество пользователей могут использовать одинаковые p и h, и вероятность того, что два пользователя выберут одинаковые ключи, будет пренебрежимо мала.). Затем мы следуем конструкции Боуза-Чоула. Мы вычисляем логарифмы по основанию g от t+i для каждого i, это даст нам
a. Наконец, мы выбираем случайную перестановку a, которая и будет нашим ключом. Мы публикуем результат перестановки a вместе с p
и h. Величины t, g и использованная перестановка остаются в секрете.
Чтобы послать сообщение A, B просто берет свое сообщение и вычисляет S = x*a. В действительности, это не так уж и просто, поскольку сообщение должно быть длиной p бит и должно быть x*1 = h, но Хор представил довольно прямолинейный метод преобразования неограниченной битовой строки в несколько блоков, каждый из которых имеет требуемую форму. А получает S. Он возводит g в степень S и выражает результат в виде полинома от t степени h с коэффициентами из GF(p). Далее он вычисляет h корней этого полинома, затем применяет обратную подстановку и получает индексы элементов в x, содержащих единицы.
Интересно отметить, что если кто-либо откроет эффективный метод вычисления дискретных логарифмов, то такой алгоритм не только не поможет вскрыть эту систему, но и облегчит генерацию ключей, так как при этом мы должны вычислять дискретные логарифмы.
До настоящего времени не было опубликовано ни одного эффективного метода вскрытия этой системы при знании только открытого ключа.
