Интернет магазин китайских планшетных компьютеров

Компьютеры - McEliece

криптосистема с открытыми ключами на основе теории алгебраического кодирования, разработанная в 1978 году Робертом Мак-Элисом. Этот алгоритм использует существование определённого класса исправляющих ошибки кодов, называемых кодами Гоппа. Он предлагал создать код Гоппа и замаскировать его как обычный линейный код. Существует быстрый алгоритм декодирования кодов Гоппа, но общая проблема найти слово кода по данному весу в линейном двоичном коде является NP-полной.

Описание алгоритма

Пусть d_H обозначает расстояние Хэмминга между y и x. Числа n, k и t служат параметрами системы. Закрытый ключ состоит из трёх частей: G' — это матрица генерации кода Гоппа, исправляющего t ошибок; P — это матрица перестановок размером n * n; S — это несингулярная матрица размером k * k. Открытым ключом служит матрица G размером k * n: G = SG'P. Открытый текст сообщений представляет собой строку k битов в виде k-элементного вектора над полем GF.

Для шифрования сообщения случайным образом выбирается n-элементный вектор z над полем GF, для которого расстояние Хэмминга меньше или равно t.

C = mG + z.

Для дешифрования сообщения сначала вычисляется c' = cP . Затем с помощью декодирующего алгоритма для кодов Гоппа находится m', для которого d_H меньше или равно t. Наконец вычисляется m = m'S .

В своей оригинальной работе МакЭлис предложил значения n = 1024, t = 50 и k = 524, Это минимальные значения, требуемые для безопасности. Хотя этот алгоритм был одним из первых алгоритмов с открытыми ключами, и не появилось публикаций о его успешном криптоаналитическом вскрытии, он не получил широкого признания в криптографичесом сообществе. Схема на два-три порядка быстрее чем RSA, но у неё есть ряд недостатков. Открытый ключ огромен: 2 битов. Сильно увеличивается объём данных — шифротекст в два раза длиннее открытого текста.