Составители:
Рубрика:
22
1. Выбирается односторонняя функция, такая, что по x легко нахо-
дится f(x), но по f(x) значение x находится очень трудно. Функция f(x)
объявляется открыто.
2. Находится легкая подзадача определения по f(x) значения x.
3. Значения передаваемой функции f(x) перемешиваются (“взбива-
ются”), так, чтобы для криптоаналитика она выглядела как трудноре-
шаемая, а для легального получателя открывается способ сведения
передаваемых значений функции к легкой подзадаче, что является “ла-
зейкой” для него.
Очень показательными в этом случае являются так называемые
“рюкзачные” криптосистемы, к рассмотрению которых мы и перехо-
дим.
2.2. Рюкзачные системы
Рассмотрим вектор A = (a
1
a
2
a
3
...a
i
... a
n
), где a
i
– различные целые
положительные числа. Пусть, кроме того, задано некоторое положи-
тельное число k. Поставим задачу: выбрать числа a
i
среди элементов
вектора A, такие, чтобы их сумма в точности равнялась k. В этом слу-
чае можно говорить, что k определяет размер рюкзака, а выбранные a
i
– размеры предметов, которые помещаются в рюкзак.
Пусть вектор A = (43 129 215 473 903 302 561 1165 697 1523), а
k = 3231. C помощью перебора можно найти: 3231 = 129 + 473+ 903+ 561+1165.
С другой стороны, если взять вектор-столбец вида (0 1 0 1 1 0 1 1 0 0)
и умножить вектор-строку A на этот вектор-столбец:
0
1
0
1
1
(43129 215 473903302 5611165 6971523) 3231,
0
1
1
0
0
∗=
Страницы
- « первая
- ‹ предыдущая
- …
- 20
- 21
- 22
- 23
- 24
- …
- следующая ›
- последняя »
