Система Мак–Элиса на основе линейного кода, исправляющего заданное число ошибок

⇐ ПредыдущаяСтр 3 из 7Следующая ⇒

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

Общими параметрами в системе Мак-Элиса являются натуральные числа k, n, t. Для получения открытого и соответствущего ему секретного ключа абонентом A проводятся следующие действия.

1. Берется порождающая матрица G=G_k_´_n двоичного (n,k)-линейного кода, исправляющего t ошибок, для которого известен эффективный алгоритм декодирования.

2. Выбирается случайная двоичная невырожденная матрица S=S_k_´_k.

3. Выбирается случайная подстановочная матрица P=P_n_´_n.

4. Вычисляется произведение матриц G₁=S×G×P.

Открытым ключом является пара (G₁,t), а секретным – тройка (S,G,P)

Для зашифрования сообщения m, предназначенного для абонента A, абонент B выполняет следующие действия:

1) представляет сообщение m в виде двоичного вектора длины k;

2) выбирает случайный двоичный вектор ошибок Z длины n, содержащий £t единиц;

3) вычисляет вектор C=m×G₁+Z и направляет его (в качестве шифрованного текста) абоненту A.

Для расшифрования полученного шифртекста абонентом A выполняются следующие действия.

1. Вычисляется вектор C₁=C×P^-1.

2. Получает вектор m₁, применяя к вектору C₁ алгоритм декодирования кода с порождающей матрицей G.

3. Вычисляет вектор исходного сообщения m=m₁×S^-1.

Корректность приведенного алгоритма расшифрования вытекает из следующих соотношений

C₁=C×P^-1=(m×G₁+Z)×P^-1=(m×S×G×P+Z)×P^-1=(m×S)×G+Z×P^-1.

А так как вектор Z×P^-1 имеет не более t единиц, алгоритм декодирует вектор С₁ в m₁=m×S .

В качестве кода в системе Мак-Элиса можно использовать, например, код Гоппы. Известно, что для любого неприводимого многочлена g(x) степени t над полем GF(2^m) существует бинарный код (код Гоппы) длины n=2^m и размерности k³n-mt, исправляющий до t ошибок, для которого имеется эффективный алгоритм декодирования. В настоящее время не известны эффективные алгоритмы дешифрования системы Мак-Элиса, использующей код Гоппы при правильном выборе параметров системы.

Однако рекомендуемые параметры такой системы (n=1024, t=38, k³644) приводят к значительному увеличению открытого ключа системы (около 2¹⁹ бит) и увеличению длины сообщения при шифровании ( примерно в полтора раза). По этой причине данная система не имеет широкого распространения.

СИСТЕМЫ ЭЛЕКТРОННОЙ ПОДПИСИ

Система электронной подписи на основе криптосистем RSA

Пусть абонент A поместил в открытом справочнике для зашифрования по системе RSA поступающих в его адрес сообщений числа (n, e), а число d является секретной частью ключа.

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

Для этого абонент A вместе с сообщением m ÎZ_n направляет

абоненту B также и величину s=m^d (mod n), которая собственно и является подписью абонента A под собщением “m”.

Для проверки правильности подписи абонент B, получив пару (m, s), проверяет на истинность равенство

s^e= m (mod n).

Если данное равенство выполняется, то принимается решение о том, что сообщение “m” действительно исходит от абонента A.

Следует отметить, что само сообщение “m” не скрывается, а всего лишь подтверждается (проверяется) то, что данное сообщение действительно исходит от абонента A.

Схема электронной подписи Рабина

Абонент A генерирует два больших простых числа p и q, p¹q. Пусть n= pq. Далее абонент A выбирает случайным образом целое число bÎZ_n, (b,n) = 1 и помещает пару (n,b) в открытый справочник. Числа же p и q он хранит у себя в секрете.

Пусть также R - некоторое фиксированное множество, h - хэш-функция, отображающая Z_n´R в Z_n. Хэш-функция h также является общеизвестной.

Подписью сообщения mÎZ_n объявляется пара (r,x), rÎR, xÎZ_n такая, что справедливо равенство

x(x + b) º h(m,r) (mod n).

Абонент A для подписи сообщения mÎZ_n выбирает случайным образом rÎR и вычисляет h(m,r). Далее находятся решения x₁, x₂ соответственно сравнений вида

x(x + b) º h(m, r) (mod p)

x(x + b) º h(m, r) (mod q).

Пара (x₁, x₂) с помощью китайской теоремы об остатках позволяет найти решение x сравнения вида

x(x + b) º h(m, r) (mod n),

то есть получить подпись (r,x) для сообщения “m”.

Если при выбранном значении rÎR решения (x₁, x₂) указанных выше сравнений не существует, то выбирается другое значение r'ÎR и процедура повторяется. Среднее число попыток для получения подписи (при определенных теоретико-вероятностных предположениях о поведении хэш-функции при случайном выборе ее аргументов) составляет 4.

Попытка же найти подпись для сообщения “m” без знания p и q приводит к необходимости решения сравнения

x(x + b) = c (mod n),

что является трудной задачей, сравнимой по сложности (как считается) с задачей разложения числа n.

Дата добавления: 2019-02-12; просмотров: 255; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 1 234 5 6 7 Следующая ⇒

Мы поможем в написании ваших работ!