М27. Число ложных ответов при дешифровании des-алгоритма методом "встречного поиска "

При зашифровании текста на 2⁵⁶ различных ключах мы получим 2⁵⁶ различных шифрованных текстов. Поскольку общее количество различных 64-разрядных двоичных векторов равно 2⁶⁴, то в списке шифрованных текстов окажется примерно лишь каждый 256-й вектор (256=2⁸). То же самое будет справедливо при расшифровании текста на 2⁵⁶ различных ключах. Если теперь сравнить оба списка, то вероятность того, что какой-либо вектор из списка зашифрования будет содержаться также и в списке расшифрования, составляет 1 шанс из 256.

Всего в списке зашифрования 2⁵⁶ векторов, и из них примерно каждый 256-й должен встретиться в списке расшифрования. Таким образом, всего таких совпадений должно быть 2⁴⁸. Все эти ответы, кроме одного, будут ложными, и для нахождения истинного решения понадобится проводить еще одну или несколько проверок.