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

Question

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

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

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

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

вопрос Последующие меры вдохновленный ответы и комментарии:

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

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

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

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

Answer 1

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

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

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

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

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

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

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

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

Answer 2

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

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

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

Answer 3

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

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