Основы криптографии Учебное пособие - Алферов А.П.
ISBN 5-85438-025-0
Скачать (прямая ссылка):
Несложно проверить, что такое определение корректно, то есть что выполняется равенство DkiEk{M)) = M при любых к є К и M є X .
Введение в правило зашифрования рандомизатора г делает шифр Эль-Гамаля шифром многозначной замены (см. гл. 5). В связи со случайным характером выбора параметра г подобную схему шифрования называют еще схемой вероятностного шифрования. Для нее открытый текст и ключ не определяют шифртекст однозначно.
319
І лава 11
Для выработки открытого и секретного ключей каждый из абонентов системы осуществляет следующие операции:
1) выбирает большое простое число р и некоторый порождающий элемент а группы Tj*р;
2) случайно выбирает целое число я, 1<я</?-2,и вычисляет (3 = ога (mod р);
3) публикует открытый ключ (р,а,/?), оставляя в секрете число а.
Следует отметить, что в приведенной системе необходимо использовать различные значения рандомизатора г для зашифрования различных открытых текстов Af и AT. В самом деле, в противном случае соответствующие шифртек-
сты (С],С2) и (С],С2) оказываются связанными соотношением C2-(C2)"1 =Af-(Aft)"1 и Aff может быть легко вычислен, если известен Af.
Как уже отмечалось, стойкость системы Эль-Гамаля определяется сложностью решения задачи дискретного логарифмирования BZ*rB настоящее время эта задача практически нереализуема для значений р , содержащих не менее 150 десятичных знаков. Рекомендуется также, чтобы число р — 1 содержало большой простой делитель.
Система Эль-Гамаля может быть обобщена для применения в любой конечной циклической группе G. Криптографическая стойкость такой обобщенной схемы определяется сложностью задачи логарифмирования в группе G . При этом групповая операция в G должна быть легко реализуемой. В качестве G чаще всего выбираются следующие три группы:
1) мультипликативная группа Z*p целых чисел по модулю простого числа р\
320
Системы с открытыми ключами
2) мультипликативная группа GF (2т)* конечного поля
GF(Im) характеристики 2;
3) группа точек эллиптической кривой над конечным полем.
Вероятностный характер шифрования можно отнести к достоинствам системы Эль-Гамаля, так как схемы вероятностного шифрования обладают, как правило, большей стойкостью по сравнению со схемами с детерминированным процессом шифрования. Недостатком системы является удвоение длины открытого текста при шифровании.
§ 11.3. Шифрсистема Мак-Элиса
Идея, лежащая в основе данной системы, состоит в выборе корректирующего кода, исправляющего определенное число ошибок, для которого существует эффективный алгоритм декодирования. С помощью секретного ключа этот код “маскируется” под общий линейный код, для которого, как известно, задача декодирования не имеет эффективного решения.
В системе Мак-Элиса параметрами системы, общими для всех абонентов, являются целые числа k, п и t. Для получения открытого и соответствующего секретного ключа каждому из абонентов системы следует осуществить следующую последовательность действий:
1) выбрать порождающую матрицу G = Gkxrt двоичного (я, к) -линейного кода, исправляющего / ошибок, для которого известен эффективный алгоритм декодирования;
2) случайно выбрать двоичную невырожденную матрицу
S — Skxk;
3) случайно выбрать подстановочную матрицу P = Pnxn;
4) вычислить произведение матриц G1 =SGP.
321
І лава 11
Открытым ключом является пара (Gx, t), секретным — тройка (Sf5G5P).
Для того чтобы зашифровать сообщение M, предназначенное для абонента А, абоненту В следует выполнить следующие действия:
1) представить M в виде двоичного вектора длины к ;
2) выбрать случайный бинарный вектор ошибок Z длины Yi, содержащий не более t единиц;
3) вычислить бинарный вектор С = M Ga + Z и направить его абоненту А.
Получив сообщение С, абонент А вычисляет вектор C1 =C-P"1, с помощью которого, используя алгоритм декодирования кода с порождающей матрицей G, получает далее векторы MxwM = Mx •S~].
Чтобы убедиться в корректности приведенного алгоритма расшифрования, достаточно заметить, что
C1 =С-Р~Х =(М-Ga+Z)-P~x = = (М -S -G- P+ Z)- Р~х = = (М-S)-G + Z-P~\
где Z • P1 — вектор, содержащий не более t единиц. Поэто-му алгоритм декодирования кода с порождающей матрицей G декодирует С в Mx =MS.
В качестве кода, исправляющего ошибки в системе Мак-Элиса, можно использовать код Гоппы (см., например, [Пит64]). Известно, что для любого неприводимого полинома
g{x) степени t над полем GF(Tn) существует бинарный
код Гоппы длины Yi = 2т и размерности к> Yi- YYit, исправляющий до t ошибок включительно, для которого имеется
322
Системы с открытыми ключами
эффективный алгоритм декодирования. В настоящее время не известны эффективные алгоритмы дешифрования системы Мак-Элиса, использующей код Гоппы, при правильном выборе параметров системы.
Вместе с тем рекомендуемые параметры для этой системы [Men97 ] — w = 1024, / = 38, А: >644 — приводят к
тому, что открытый ключ имеет размер около 219 бит, а длина сообщения увеличивается при шифровании примерно в 1,6 раза, в связи с чем данная система не получила широкого распространения.
