ВУЗ:
Составители:
152
011000 соответствует 93 + 81 = 174
110101 соответствует 62 + 93 + 88 + 37 = 280
101110 соответствует 62 + 81 + 88 + 102 = 333
Шифротекстом будет последовательность 174,280,333
Дешифрирование
Законный получатель данного сообщения знает закрытый ключ:
оригинальную сверхвозрастающую поcледовательность, а также значения п и
т, использованные для превращения ее в нормальную последовательность
рюкзака. Для дешифрирования сообщения получатель должен сначала
определить n
-1
, такое что n(n
-1
)
≡
l (mod т). Каждое значение щифротекста
умножается на п
-1
mod m, а затем разделяется с помощью закрытого ключа,
чтобы получить значения открытого текста.
В нашем примере сверхвозрастающая последовательность -
{2,3,6,13,27,52}, т равно 105, а и - 31. Шифротекстом служит 174,280,333. В
этом случае п
-1
равно 61, поэтому значения шифротекста должны быть
умножены на 61 mod 105.
174*61 mod 105 = 9 = 3 + 6, что соответствует 011000
280*61 mod 105 = 70 = 2 + 3 + 13 + 52, что соответствует 110101
333*61 mod 105 = 48 = 2 + 6 + 13 + 27, что соответствует 101110
Расшифрованным открытым текстом является 011000 110101 101110.
Практические реализации
Для последовательности из шести элементов нетрудно решить задачу
рюкзака, даже если последовательность не является сверхвозрастающей.
Реальные рюкзаки должны содержать не менее 250 элементов. Длина
каждого члена сверхвозрастающей последовательности должна быть где-то
между 200 и 400 битами, а длина модуля должна быть от 100 до 200 битов.
Для получения этих значений практические реализации используют
генераторы случайной последовательности.
Вскрывать подобные рюкзаки при помощи грубой силы бесполезно.
Если компьютер может проверять миллион вариантов в секунду, проверка
всех возможных вариантов рюкзака потребует свыше 10
4б
лет. Даже миллион
машин, работающих параллельно, не успеет решить эту задачу до
превращения солнца в сверхновую звезду.
Безопасность метода рюкзака
Взломали криптосистему, основанную на проблеме рюкзака, не
миллион машин, а пара криптографов. Сначала был раскрыт единственный
бит открытого текста. Затем Шамир показал, что в определенных обстоя-
тельствах рюкзак может быть взломан. Были и другие достижения - но никто
не мог взломать систему Мартина-Хеллмана в общем случае. Наконец
Шамир и Циппел (Zippel), обнаружили слабые места в преобразовании, что
позволило им восстановить сверхвозрастающую последовательность рюкзака
Страницы
- « первая
- ‹ предыдущая
- …
- 150
- 151
- 152
- 153
- 154
- …
- следующая ›
- последняя »
