Рассмотренная криптосистема является семантически стойкой и неделимой. В частности, неделимость обеспечивается тем, что значение g" подается на вход функции хэширования. Если этого не сделать, то возможна атака, подобная описанной в п. 3.3.2 на шифр Эль-Гамаля. Дело в том, что в некоторых группах (включая Zp ) значения g"" и g" неоднозначно определяют значение g". Т.е. могут суш,ествовать и Фи, такие что g"" = g"". Пусть / = (р - 1)/2. Тогда = -\. Если нам дано зашифрованное сооб-ш,ение ЕМ = g" II епсМ II tag, то мы сможем вычислить новый шифртекст, ЕМ = g" епсМ tag, который с большой вероятностью будет соответствовать тому же самому открытому тексту. Пусть = g-i. В этом случае = /"-g" = giy = /4-1)", и это равно g"" тогда и только тогда, когда v - четное, т.е. в половине всех случаев. Таким образом, с вероятностью 1/2 вычисленный шифртекст будет являться результатом зашифрования того же самого исходного текста.

Секретный ключ получателя

Вычисление секретного значения

Общее секретное значение

шифртекст

mac Key

tag II-»

епсКеу

SYM.dec

MAC.ver

открытый текст

1 - OK О-BAD

Рис. 3.3. Процесс расшифрования и аутентификации. Эффективность предложенной схемы по суш,еству та же, что и у шифра Эль-Гамаля, т.е. для зашифрования требуются две операции возведения в степень, а для расшифрования - одна.

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

3.3.3. Криптосистема Ривеста-Шамира-Адлемапа

Система Ривеста-Шамира-Адлемана (Rivest, Shamir, Adleman - RSA) представляет собой криптосистему, стойкость которой основана на сложности решения задачи разложения числа на простые сомножители. Кратко алгоритм можно описать сле-дуюш,им образом:

Пользователь А выбирает пару различных простых чисел и , вычисляет «д = PkQk и выбирает число d, такое что НОД(й?А, Ф(«а)) 1, где ф(«) - функция Эйлера (количество чисел, меньших п и взаимно простых с п. Если п =pq, где р и q -простые числа, то ф(«) (р - \){q - \)). Затем он вычисляет величину вА, такую, что Jaa = 1 (mod Ф(«а)), и размеш,ает в об-ш,едоступной справочной таблице пару (ед, «а), являюш,уюся открытым ключом пользователя А.

Теперь пользователь В, желая передать сообш,ение пользователю А, представляет исходный текст

X = (хо, Хи х„-х), X g Z„ , о < / < «,

по основанию «д:

N = co+ci «д+..

Пользователь В зашифровывает текст при передаче его пользователю А, применяя к коэффициентам с, отображение Е :

ЕеА,«А - С->cA(mod«A),

получая зашифрованное сообш,ение N. В силу выбора чисел d и бд, отображение Е является взаимно однозначным, и обратным к нему будет отображение

ЕА,«А - с->/а (modИд)

Пользователь А производит расшифрование полученного со-обш,енияМ, применяя df,nf •

Для того чтобы найти отображение Е , обратное по отношению к , требуется знание множителей «д = РкЧк-

Время выполнения наилучших из известных алгоритмов разложения при п > Ю"* на сегодняшний день выходит за пределы современных технологичесьсих возможностей.

Суш,ествует вариант криптосистемы RSA, в которой вместо функции Эйлера используется функция Кармайкла X, где Х{п) -наименьшее целое t, такое что для любого целого х, взаимно простого с п, выполняется х = \ mod п. Если п выбирается так, как описано выше, то Х{п) = ШУЩр -1,-1)

3.3.4. Криптосистемы Меркля-Хеллмапа и Хора-Ривеста

Криптосистемы Меркля-Хеллмана и Хора-Ривеста основаны на использовании односторонней функции, известной под названием "задача укладки рюкзака.

Пусть имеется п объектов, так что можно составить п-компонентный вектор f, так что /-й компонент f представляет собой место, занимаемое i-м объектом. Имеется рюкзак обш,им объемом К.

Теперь задачу укладки рюкзака может быть сформулирована следуюш,им образом: нам даны f и К, и требуется найти битовый вектор X, такой что fx=K. Доказано, что не суш,ествует эффективного алгоритма вычисления х по f и К в обш,ем случае. Таким образом, мы можем использовать вектор f для шифрования «-битового сообш,ения х путем вычисления произведения K=fx.

Важно отметить, что выбор f является критическим. Например, предположим, что f выбирается в виде супервозрастаюш,ей последовательности. В этой ситуации для любого /

г-1 7=1

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

элемента f, даже если мы выберем х=(1 1 1 ... 1 0), то произведение fx все равно будет слишком маленьким, благодаря тому, что последовательность супервозрастаюш,ая. Таким образом, мы должны выбирать 1 в последней позиции х.

Ясно, что выбор f очень важен - в зависимости от f мы можем получить, а можем и не получить одностороннюю функцию. Однако, именно суш,ествование этого простого случая позволяет нам создать функцию-ловушку, которую мы можем использовать для построения криптосистемы с открытым ключом.

Пользователь А получает свой открытый ключ следуюш,им образом:

1. Выбирает супервозрастаюш,ую последовательность f примерно из 100 элементов;

2. Выбирает случайное целое т, большее суммы элементов f;

3. Выбирает другое случайное целое w, взаимно простое с т.

4. Теперь вычисляется f умножением каждого компонента f на w по модулю т;

f = f W (mod т)

5. И наконец, проводится случайная перестановка Р элементов f для получения открытого ключа f

Теперь А раскрывает ключ f и держит в секрете f, /и, w и Р.

Когда пользователь В хочет послать А сообш,ение (битовый вектор) X, он вычисляет 5 = fx и посылает это вычисленное S. Если данная система является стойкой, тогда для внешнего наблюдателя С вычисление х по и публичному ключу f будет эквивалентно решению задачи рюкзака в обш,ем случае. Допустим, что предположение о стойкости верно. В этом случае, хотя С не может расшифровать сообш,ение, А может это сделать, применяя секретные значения, которые она использовала при вычислении f.

Пользователь А может вычислить 5"=fx, так что она сможет решить задачу рюкзака в случае супервозрастаюш,ей последовательности. Вычисление S производится следуюш,им образом.

S- ,. - jmodm - w modm-

= w~, j modm w~Smodm i

Таким образом, A просто умножает S на мультипликативное обратное w по модулю т, а затем решает задачу рюкзака в случае супервозрастаюш,ей последовательности f, и теперь она сможет прочитать сообш,ение.

При получении ключа мы начинаем с супервозрастаюш,ей последовательности и затем скрываем имеюш,уюся в ней структуру. Другими словами, построенная последовательность выглядит так, что в ней нет никакой структуры. Но система может быть сделана еш,е более стойкой (или, по крайней мере, так будет казаться) путем повторения этого процесса скрытия структуры. Если мы выберем другие mnw, тогда мы сможем построить новый открытый ключ, который не может быть построен с использованием единственной пары (т, w). Мы можем повторять это снова и снова, и система выглядит все более и более стойкой с каждой итерацией.

В 1982 г Эди Шамир открыл атаку на криптосистему, ис-пользуюш,ую одну итерацию. Это оказалось началом падения систем, основанных на задаче рюкзака.

Допустим, что перестановка не применяется, так что f = f. Тогда для любого /

f; = fiw mod т

По определению модульной конгруэнтности должен суш,ест-вовать вектор к, такой что для любого /

Mf/-/wk/ = f,

где и - это мультипликативное обратное к w по модулю т (напомним, что мы выбирали т nw взаимно простыми, так что это обратное суш,ествует). После этого в результате деления получаем:

т fj fjm

Поскольку т очень велико, выражение справа будет очень маленьким, поэтому покомпонентное частное к и f близко к и/т. Подставляя вместо / 1 и вычитая из первоначального уравнения, получим:

к, к,

mfj mil

Поскольку обе величины справа положительны и вычитаемое очень мало, мы можем записать:

Также заметим, что поскольку f супервозрастаюш,ая, каждый элемент должен быть меньше половины следуюш,его, поэтому для любого / имеем:

f,<w2-« Далее мы можем записать:

После несложных преобразований получаем: krfi-ki-f,<fi-2-«

Оказывается, что поскольку f открыт, всего лишь несколько этих неравенств (три или четыре) однозначно определяют к. Эти неравенства относятся к области целочисленного программирования, поэтому к можно быстро найти, например, с помо-ш,ью алгоритма Ленстры. А если мы знаем к, то мы можем легко раскрыть систему.

Допустим, что мы выполним перестановку f до опубликования, т.е. Р не является идентичной. Поскольку нам нужны только первые 3 или 4 элемента к, мы можем просто перебрать все варианты, количество которых определяется третьей или четвертой степенью размерности к.

В дальнейшем были разработаны методы вскрытия систем, используюш,их несколько итераций, и в настояш,ее время любая система, используюш,ая модульное умножение для скрытия лег-