ВУЗ:
Составители:
164
кодирования. Этот алгоритм использует существование определенного
класса исправляющих ошибки кодов, называемых кодами Гоппа (Goppa).
Он предлагал создать код Гоппа и замаскировать его как обычный линейный
код. Существует быстрый алгоритм декодирования кодов Гоппа, но общая
проблема найти слово кода по данному весу в линейном двоичном коде
является NP-полной. Ниже приведен только краткий обзор.
Пусть d
H
(x,y) обозначает расстояние Хэмминга между х и у. Числа п, k
и t служат параметрами системы.
Закрытый ключ состоит из трех частей: G' - это матрица генерации года
Гоппа, исправляющего t ошибок. Р -это матрица перестановок размером п*п.
S - это nonsingular матрица размером k*k.
Открытым ключом служит матрица G размером k*п: G = SG'P.
Открытый текст сообщений представляет собой строку k битов в виде
k-элементного вектора над полем GF(2).
Для шифрования сообщения случайным образом выбирается n-
элементный вектор z над полем GF(2), для которого расстояние Хэмминга
меньше или равно t.
c=mG+z
Для дешифрирования сообщения сначала вычисляется с'= сР
-1
. Затем с
помощью декодирующего алгоритма для кодов Гоппа находится т', для
которого d
H
(m'G,c) меньше или равно t. Наконец вычисляется т = m'S
-1
.
В своей оригинальной работе МакЭлис предложил значения п = 1024, t
= 50 и k = 524. Это минимальные значения, требуемые для безопасности.
Хотя этот алгоритм был одним из первых алгоритмов с открытыми
ключами, и вне появлялось публикаций о его успешном
криптоаналитическом вскрытии, он не получил широкого признания в
криптографическом соообществе. Схема на два-три порядка быстрее, чем
RSA, но у нее есть ряд недостатков. Открытый ключ огромен: 2
19
битов.
Сильно увеличивается объем данных - шифротекст в два раза длиннее
открытого текста. Ни одна из них не достигла успеха для общего случая, хотя
сходство между алгоритмом МакЭлиса и алгоритмом рюкзака немного
волнует.
В 1991 два русских криптографа заявили, что взломали систему
МакЭлиса с некоторыми параметрами. В их статье это утверждение не было
обосновано, и большинство криптографов не приняли во внимание этот
результат.
Другие алгоритмы, основанные на линейных кодах, исправляющих
ошибки
Алгоритм Нидеррейтера (Niederreiter) очень близок к алгоритму
МакЭлиса и считает, что открытый ключ - это случайная матрица проверки
четности кода, исправляющего ошибки. Закрытым ключом служит эф-
фективный алгоритм декодирования этой матрицы.
Другой алгоритм, используемый для идентификации и цифровых
подписей, основан на декодировании синдрома, использующий коды,
Страницы
- « первая
- ‹ предыдущая
- …
- 162
- 163
- 164
- 165
- 166
- …
- следующая ›
- последняя »
