Составители:
Рубрика:
25
Затем легальный получатель сообщения также легко находит преоб-
разование вектора X:
39⋅25 ≡ 13 mod 37; 29⋅25 ≡ 22 mod 37; 14⋅25 ≡17 mod 37. Теперь
получатель имеет вектор X’= (13 22 17) и ему остается вычислить ис-
ходный вектор A , зная вектор B и u:
3⋅25 ≡ 1 mod 37; 6⋅25 ≡ 2 mod 37; 12⋅25 ≡ 4 mod 37; 24⋅25 ≡ 8 mod 37;
11⋅25 ≡ 16 mod 37. Исходный вектор A = (1 2 4 8 16) является сверхрас-
тущим, поэтому по вектору A и X’ легко дешифруется переданное со-
общение:
101
010
110
100
011
2.4. Плотные рюкзаки
Задача о рюкзаке, лежащая в основе базисного варианта систем с
открытым распределением ключей, имеет низкую плотность, в том смыс-
ле, что компоненты рюкзачного вектора располагаются в отрезке от 1
до n очень редко. Плотность рюкзака определяется следующим обра-
зом:
()
2
A.
log max A
n
d
=
Так, для сверхрастущего вектора A = (1 2 4 8 16 32 64) d(A) = 7/6.
Увеличить плотность рюкзачного вектора можно с использованием
полей Галуа GF(p
h
), где p – простое; h – целое.
Конечное поле F(p
h
) содержит p
h
элементов. Основное поле F(p) ,
которое является подполем поля F(p
h
), содержит p элемента (0, 1, 2, 3, ...,
p–1) и 2 операции: ⊕ mod p и ⊕ mod p.
Элемент α называется алгебраическим степени h над полем F(p),
если и только если α удовлетворяет в F(p) уравнению: P(x) = 0, где P(x)
– многочлен степени h, но не удовлетворяет никакому уравнению с
многочленом меньшей степени. Это влечет неприводимость многочле-
Страницы
- « первая
- ‹ предыдущая
- …
- 23
- 24
- 25
- 26
- 27
- …
- следующая ›
- последняя »
