Почему в атаке грубой силы на симметричный алгоритм есть 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%) шанс