ВУЗ:
Составители:
149
разрешенного к экспорту 40-битового ключа или 56-битового ключа DES
потребует намного больше времени и памяти. Как только Ева создаст такую
базу данных, она получит ключ Боба и сможет читать его почту.
Алгоритмы с открытыми ключами спроектированы так, чтобы
противостоять вскрытиям с выбранным открытым текстом. Их безопасность
основана как на трудности получения секретного ключа по открытому, так и
на трудности получить открытый текст по шифротексту. Однако
большинство алгоритмов с открытым ключом особенно чувствительны к
вскрытию с выбранным шифротекстом.
В системах, в которых операция, обратная шифрованию, используется
для цифровой подписи, это вскрытие невозможно предотвратить, если для
шифрования и подписей использовать одинаковые ключи.
Следовательно, важно увидеть всю систему целиком, а не только
составные части. Хорошие протоколы с открытыми ключами
спроектированы таким образом, чтобы различные стороны не могли
расшифровать произвольные сообщения, генерированные другими
сторонами, - хорошим примером являются протоколы доказательства
идентичности.
2.7.1. Алгоритмы рюкзака
Первым алгоритмом для обобщенного шифрования с открытым
ключом стал алгоритм рюкзака, разработанный Ральфом Мерклом и
Мартином Хеллманом. Он мог быть использован только для шифрования,
хотя позднее Ади Шамир адаптировал систему для цифровой подписи.
Безопасность алгоритмов рюкзака опирается на проблему рюкзака, NP-
полную проблему. Хотя позже было обнаружено, что этот алгоритм
небезопасен, его стоит изучить, так как он демонстрирует возможность
применения NP-полной проблемы в криптографии с открытыми ключами.
Проблема рюкзака несложна. Дана куча предметов различной массы,
можно ли положить некоторые из этих предметов в рюкзак так, чтобы масса
рюкзака стала равна определенному значению? Более формально, дан набор
значений M
1
, М
2
,. . ., М
n
и сумма S, вычислить значения b
i
, такие что
S = b
1
М
1
+ b
2
М
2
+...+ b
п
М
п
b
i
может быть либо нулем, либо единицей. Единица показывает, что
предмет кладут в рюкзак, а ноль - что не кладут.
Например, массы предметов могут иметь значения 1, 5, 6, 11, 14 и 20.
Вы можете упаковать рюкзак так, чтобы его масса стала равна 22,
использовав массы 5, 6 и 11. Невозможно упаковать рюкзак так, чтобы его
масса была равна 24. В общем случае время, необходимое для решения этой
проблемы, с ростом количества предметов в куче растет экспоненциально.
В основе алгоритма рюкзака Меркла-Хеллмана лежит идея шифровать
сообщение как решение набора проблем рюкзака. Предметы из кучи
выбираются с помощью блока открытого текста, по длине равного
количеству предметов в куче (биты открытого текста соответствуют
Страницы
- « первая
- ‹ предыдущая
- …
- 147
- 148
- 149
- 150
- 151
- …
- следующая ›
- последняя »
