Безопасность алгоритмов с открытыми ключами

Так как у криптоаналитика есть доступ к открытому ключу, он всегда может выбрать для шифрования любое сообщение. Это означает, что криптоаналитик при заданном C = E_K Ц P ) может попробовать угадать значение P и легко проверить свою догадку. Это является серьезной проблемой, если количество возможных открытых те к-стов настолько мало, что делает возможным исчерпывающий поиск, но эту проблему легко можно решить, д о-полняя сообщения строкой случайных битов. Это приводит к тому, что идентичным открытым текстам соответ­ствуют различные шифротексты. (Более подробно эта идея описана в разделе 23.15.)

Это особенно важно, если алгоритм с открытым ключом используется для шифрования сеансового ключа. Ева может создать базу данных всех возможных сеансовых ключей, зашифрованных открытым ключом Боба. Конечно, это потребует много времени и памяти, но взлом грубой силой разрешенного к экспорту 40-битового ключа или 56-битового ключа DES потребует намного больше времени и памяти. Как только Ева создаст такую базу данных, она получит ключ Боба и сможет читать его почту.

Алгоритмы с открытыми ключами спроектированы так, чтобы противостоять вскрытиям с выбранным о т-крытым текстом. Их безопасность основана как на трудности получения секретного ключа по открытому, так и на трудности получить открытый текст по шифротексту. Однако большинство алгоритмов с открытым ключом особенно чувствительны к вскрытию с выбранным шифротекстом (см. раздел 1.1).

В системах, в которых операция, обратная шифрованию, используется для цифровой подписи, это вскрытие невозможно предотвратить, если для шифрования и подписей использовать одинаковые ключи.

Следовательно, важно увидеть всю систему целиком, а не только составные части. Хорошие протоколы с от­крытыми ключами спроектированы таким образом, чтобы различные стороны не могли расшифровать прои з-вольные сообщения, генерированные другими сторонами, - хорошим примером являются протоколы доказ а-тельства идентичности (см. раздел 5.2).

19.2 Алгоритмы рюкзака

Первым алгоритмом для обобщенного шифрования с открытым ключом стал алгоритм рюкзака, разраб о-танный Ральфом Мерклом и Мартином Хеллманом [713, 1074]. Он мог быть использован только для шифрова­ния, хотя позднее Ади Шамир адаптировал систему для цифровой подписи [1413]. Безопасность алгоритмов рюкзака опирается на проблему рюкзака, NP-полную проблему. Хотя позже было обнаружено, что этот алго­ритм небезопасен, его стоит изучить, так как он демонстрирует возможность применения NP-полной проблемы

в криптографии с открытыми ключами.

Проблема рюкзака несложна. Дана куча предметов различной массы, можно ли положить некоторые из этих предметов в рюкзак так, чтобы масса рюкзака стала равна определенному значению? Более формально, дан набор значений М_х, М₂,..., М_п и сумма S, вычислить значения й„ такие что

S = b_lM_l+ b₂M₂ +... + b_nM_n

b_t может быть либо нулем, либо единицей. Единица показывает, что предмет кладут в рюкзак, а ноль - что не кладут.

Например, массы предметов могут иметь значения 1, 5, 6, И, 14 и 20. Вы можете упаковать рюкзак так, чтобы его масса стала равна 22, использовав массы 5, 6 и 11. Невозможно упаковать рюкзак так, чтобы его мас­са была равна 24. В общем случае время, необходимое для решения этой проблемы, с ростом количества пре д-метов в куче растет экспоненциально.

В основе алгоритма рюкзака Меркла-Хеллмана лежит идея шифровать сообщение как решение набора пр о-блем рюкзака. Предметы из кучи выбираются с помощью блока открытого текста, по длине равного количеству предметов в куче (биты открытого текста соответствуют значениям Ъ), а шифротекст является полученной сум­мой. Пример шифротекста, зашифрованного с помощью проблемы рюкзака, показан на.