Шифрсистема Мак-Элиса.

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

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

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

2) Случайно выбрать двоичную невырожденную матрицу S = Sk´k.

3) Случайно выбрать подстановочную матрицу P = Pn´n.

4) Вычислить произведение матриц G1 = S · G · P.

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

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

1) Представить M в виде двоичного вектора длины k.

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

3) Вычислить бинарный вектор C = M · GA + Z и направить его абоненту A.

Получив сообщение C, абонент A вычисляет вектор C1 = C · P-1, с помощью которого, используя алгоритм декодирования кода с порождающей матрицей G, получает далее векторы M1 и M = M1 · S-1.

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

Рекомендуемые параметры этой системы - n = 1024, t = 38, k > 644 – приводят к тому, что открытый ключ имеет размер около 219 бит, а длина сообщения увеличивается при шифровании примерно в 1,6 раза, в связи с чем данная система не получила широкого распространения.

 

Контрольные вопросы

1. Почему операции для криптографических преобразований должны обладать свойством замкнутости?

2. Приведите случаи, при которых функция Эйлера легко вычислима.

3. В чем различие между кольцом вычетов по модулю натурального числа и простым конечным полем?

4. Для чего используется расширенный (обобщенный) алгоритм Евклида?

5. Для решения какого вида систем сравнений используется китайская теорема об остатках?

6. В чем различие между символами Лежандра и Якоби?

7. Назовите два способа извлечения квадратных корней в простом конечном поле?

8. Может ли в криптосистеме RSA шифрующая экспонента быть четной?

9. Какие требования к модулю P предъявляются в криптосистеме Эль-Гамаля?

10. Сколько вариантов расшифрования сообщения в криптосистеме Рабина?

 









Дата добавления: 2016-02-13; просмотров: 1478;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

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

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.006 сек.