Почему при атаке методом "грубой силы" по симметричному алгоритму вероятность обнаружения ключа после половины попыток составляет 50%?

Question

В любом криптографическом тексте упоминается, что при атаке методом "грубой силы" по симметричному алгоритму вероятность обнаружения ключа после половины попытки составляет 50%.

например. DES с 56-битным ключом будет иметь 50% шанс найти ключ после первых 2 ⁵⁵ попыток.

Почему при атаке методом «грубой силы» против любого алгоритма симметричного шифрования вероятность обнаружения ключа после половины попыток составляет 50%? Что является математическим доказательством этого?

Answer 1

Если перед вами N коробок, одна из которых содержит приз, то в среднем вам нужно только посмотреть в половину коробок, прежде чем вы найдете его.

(Посмотрите на это с другой стороны: вам было бы невероятно не повезло, если бы было много коробок, и приз был в последней коробке, которую вы пробовали.)

Доказательство: вероятность того, что приз окажется в какой-либо конкретной коробке, составляет 1/N, а приз - в одной и только одной коробке. Если вы посмотрите в половину ящиков (N/2), ваш шанс найти его составляет (1/N) * (N/2), что составляет 1/2 или 50%.

Answer 2

Каждый ключ может как зашифровать, так и расшифровать. Поэтому, если есть 100 возможных ключей, атака грубой силой выглядит следующим образом:

• Первая попытка: 1/100 шанс.
• Вторая попытка: шанс 2/100.
• ...
• Пятидесятая попытка: 50/100 (50%) шанс