Научная литература
booksshare.net -> Добавить материал -> Математика -> Коблиц Н. -> "Курс теории чисел и криптографии" -> 61

Курс теории чисел и криптографии - Коблиц Н.

Коблиц Н. Курс теории чисел и криптографии — Москва: Научное изд-во ТВП, 2001. — 254 c.
Скачать (прямая ссылка): theory-chisel-kriptographii.djvu
Предыдущая << 1 .. 55 56 57 58 59 60 < 61 > 62 63 64 65 66 67 .. 125 >> Следующая


Конечно, использование однобуквенных элементов открытого текста со столь малым к = 5 не обеспечивает надежной защиты. Пример 3 призван лишь проиллюстрировать механизм системы.

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

Однако в этих рассуждениях крылась ошибка. Порождаемые такими системами задачи о рюкзаке С = Y ?iwi, хотя и не соответствуют быстрорастущим наборам, но имеют весьма специфический тип, а именно, получаются из задач с быстрорастущим набором простым преобразованием: умножением всех величин на а и приведением по модулю то. В 1982 году Шамир нашел полиномиальный по к алгоритм решения задач о рюкзаке такого типа. Поэтому исходная криптосистема Меркля-Хеллмана не может считаться надежной криптосистемой с открытым ключом.

Одним из способов защиты от алгоритма !Памира может быть некоторое усложнение рюкзачной системы последовательностью преобразований вида X ь-> ах (mod то). Например, можно просто применить два преобразования с параметрами (01,Tn1) и (а2,т2) соответственно. Мы сначала заменяем нашу быстрорастущую последовательность {г>,} на {wj}, где Wi — наименьший положительный вычет UyV1 (mod 77Z1), а затем получаем третью последовательность {и,}, взяв наименьшие положительные вычеты Uj = a2Wi (mod т2). Здесь мы выбираем 77I1, т2 и O1, O2 случайно так, чтобы они удовлетворяли условиям 77I1 > Vi, т2 > Um1 и НОД (O1Jm1) = НОД (а2,т2) = 1. Тогда открытым ключом будет набор величин «,-, а шифрующей функцией — функция С = /(F) = Х)*=о?іиь где P = (ек-\ ¦•¦?0)2- При дешифровании шифртекста используется ключ Kp = (6!,TO1JO25Tn2) (где bi = O1 1 (mod TTi1) и b2 = а21 (mod то2)). Сначала вычисляется наименьший положительный вычет Ь2С по модулю тп2, затем результат домножается на Ьг и приводится по модулю To1. Так как b2C = "Y1EiWi (mod JJi2) и JJi2 > ктп\ > Ywii То результат приведе-

§ 4. ЗАДАЧА О РЮКЗАКЕ

127

ния Ъ2С по модулю 7ТІ2 совпадает с YJe^UJj. Потом, когда мы берем biY^,?iwi (mod Tn1), получаем ?;^, откуда можно определить єІ5 используя приведенный выше алгоритм для задачи о рюкзаке с быстрорастущим набором.

В настоящее время еще не найден полиномиальный алгоритм решения итерированной задачи о рюкзаке (т. е. криптосистемы с открытым ключом, описанной в предыдущем абзаце). Однако Брикелю с соавторами удалось обобщить алгоритм Шамира и показать, что к итерированной рюкзачной криптосистеме применимы эффективные методы криптоанализа. Во всяком случае, после достижения Шамира большинство экспертов потеряло доверие к стойкости криптосистем с открытым ключом данного типа.

Одна до сих пор не вскрытая рюкзачная система. Теперь опишем метод передачи сообщений, основанный на однонаправленной функции рюкзачного типа, который использует многочлены над конечным полем. Эту криптосистему предложили Чор и Райвест; мы изложим слегка упрощенный (и менее эффективный) вариант их конструкции.

Опять предположим, что Алиса хочет принимать сообщения в форме наборов из к битов ?o,...,?fc_i. (Число к Алиса выбирает так, чтобы выполнялись указанные ниже условия.) Как и раньше, ее открытым ключом является последовательность натуральных чисел Vq, ..., W/c-i, построенная описываемым ниже способом. Но теперь Боб должен посылать ей не только целое число с = ^EjVj, но и сумму разрядов с' = ^2 Ej.

Алиса строит последовательность Vj следующим образом. Выбор всех параметров, которые упоминаются в этом абзаце, можно делать секретным образом, так как Бобу для посылки сообщения необходим лишь итоговый набор г>0,..., . Сначала Алиса выбирает такую степень простого q = , что q — 1 не имеет больших простых делителей (в этом случае возможно практическое вычисление логарифмов в группе F,, см. §3), причем как р, так и / имеют умеренные значения (например, записываются двумя или тремя десятичными разрядами). Так, в работе Чора и Райвеста 1988 г. рассматривалась величина q = 19724. Далее Алиса выбирает нормированный неразложимый многочлен F(X) Є Fp[A'] степени /, так что F9 может рассматриваться как Fp[X]/F[X). Она выбирает также образующий элемент g в F* и целое число z. Алиса производит выбор F, g и z каким-нибудь случайным образом.

Пусть t Є Fq = Fp[X]/F(X) обозначает класс вычетов, содержащий X. Алиса выбирает в качестве к любое целое число, меньшее р и

128

ГЛ. IV. ОТКРЫТЫЙ КЛЮЧ

/ одновременно. Для j = О,..., к — 1 она вычисляет такие неотрицательные целые bj < q — 1, что дЬ' — t + j (согласно предположению, Алиса может легко вычислять дискретные логарифмы в F9). Наконец, Алиса выбирает случайно перестановку 7Г элементов множества {О,..., к — 1} и полагает Vj равным наименьшему неотрицательному вычету 6„•(J) + z по модулю q — 1. Она объявляет (г>0,.. . , i>fc_i) своим открытым ключом.

Расшифрование происходит следующим образом. Получив от Боба с и с', Алиса сначала вычисляет элемент д° z° , который единственным образом представляется в виде многочлена G(X) Є FP[X] степени ниже /. Но она знает, что этот элемент равен также \~Ідє'Ьіг(з) = Д(і + 7г(І))?', что соответствует многочлену Yi(X A-ir(j)Y' ¦ Поскольку многочлены G(A") и Yl(X +Tt(J)Y' имеют степень ниже / и представляют собой один и тот же элемент по модулю F(X), должно выполняться равенство
Предыдущая << 1 .. 55 56 57 58 59 60 < 61 > 62 63 64 65 66 67 .. 125 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed