Насколько устойчивы к коллизиям алгоритмы шифрования?

Question

Насколько сложно заданному зашифрованному тексту, сгенерированному данным (симметричным или асимметричным) алгоритмом шифрования, работающему с парой открытый текст / ключ, найти другую пару открытого текста / ключа, которая дает один и тот же зашифрованный текст?

И насколько трудно найти две пары открытого текста / ключа, ведущие к одному и тому же шифротексту?

Что привело к этому вопросу, это другой вопрос, который может оказаться не связанным с вышеуказанными вопросами:

Если у вас есть зашифрованный текст и ключ, и вы хотите расшифровать его, используя некоторую процедуру дешифрования, эта процедура обычно сообщает вам, был ли ключ правильным. Но откуда оно это знает? Ищет ли он какой-то шаблон в результате открытого текста, который указывает, что расшифровка прошла успешно? Существуют ли другие ключевые результаты в каком-то другом тексте, который содержит шаблон и также сообщается как «действительный» программой?

Дополнительный вопрос , вдохновленный ответами и комментариями:

Если разрешенные пары открытого текста / ключа ограничены следующими (или обоими) способами:

1) Открытый текст начинается с KCV (значения проверки ключа) ключа.

2) Открытый текст начинается со значения хеш-функции некоторой комбинации открытого текста / ключа

Сделало бы это невозможным обнаружение столкновения? Даже ясно, что такой открытый текст / ключ существует =

Answer 1

Ответ на ваш вопрос в том виде, в каком вы его сформулировали, заключается в том, что нет никакого сопротивления столкновению, чем когда-либо.

Симметричный регистр Предположим, вы получили обычный текстовый PT, длина которого кратна длине блока базового блочного шифра.Вы генерируете случайный IV и шифруете простой текст, используя ключ K, режим CBC и без заполнения.

Создание простого текста PT 'и ключа K', который выдает одинаковый зашифрованный текст CT, очень просто.Просто выберите K 'наугад, расшифруйте CT, используя клавиши K' и IV, и вы получите коллизионный PT '.

Это становится немного сложнее, если вы также используете заполнение, но это все еще возможно.Если вы используете заполнение PKCS # 5/7, просто продолжайте генерировать ключи, пока не найдете такой, что последний октет вашего расшифрованного текста PT 'будет 0x01.Это займет в среднем 128 попыток.

Чтобы сделать такое обнаружение коллизий недопустимым, вы должны использовать код аутентификации сообщения (MAC).

Асимметричный случай Нечто подобное применимов RSA шифрование с открытым ключом.Если вы не используете заполнение (что явно не рекомендуется и, возможно, даже не поддерживается большинством криптографических библиотек) и используете открытый ключ (N, E) для шифрования PT в CT, просто сгенерируйте вторую пару ключей (N ', E', D'), так что N '> N, тогда PT' = CT ^ D '(мод N) будет шифроваться в CT в (N', E ').

Если вы используете PKCS # 1Заполнение v1.5 для вашего шифрования RSA, наиболее значимый октет после операции с закрытым ключом RSA должен быть 0x02, что будет с вероятностью приблизительно один из 256. Кроме того, первый октет со значением 0x00 должен произойти не раньше, чем прииндекс 9, что произойдет с большой вероятностью (примерно 0,97).Следовательно, в среднем вам придется сгенерировать в среднем около 264 случайных пар ключей RSA одинакового размера, прежде чем вы нажмете одну, что для простого текста могло бы привести к тому же зашифрованному тексту.

Если вы используетеОднако при заполнении RSA-OAEP дешифрование секретного ключа гарантированно завершится неудачей, если только текст шифра не был сгенерирован с использованием соответствующего открытого ключа.

Answer 2

Если вы шифруете некоторый открытый текст (длина n ), то существует 2 ⁿ уникальных строк ввода, и каждая из них должна привести к уникальному зашифрованному тексту(иначе это не было бы обратимо).Следовательно, все возможные строки длиной n являются действительными шифротекстами.Но это верно для всех ключей.Следовательно, для любого данного зашифрованного текста существует 2 ^k способов его получения, каждый с различным ключом длины k .

Следовательно, чтобы ответить на ваш первый вопрос: очень просто!Просто выберите произвольный ключ и «расшифруйте» зашифрованный текст.Вы получите открытый текст, который соответствует ключу.

Я не уверен, что вы подразумеваете под «процедура обычно говорит вам, был ли ключ правильным».

Answer 3

Один простой способ проверить действительность ключа - добавить известную часть в открытый текст перед шифрованием. Если расшифровка не воспроизводит это, это не правильный ключ.

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