БРУТФОРС

Полный перебор (или метод «грубой силы» от англ. brute force) — метод решения задачи путем перебора всех возможных вариантов. Сложность полного перебора зависит от размерности пространства всех возможных решений задачи.

Любая задача из класса NP может быть решена полным перебором. При этом, несмотря на то, ЧОЧО проверка каждого конкретного возможного решения в классе NP может быть осуществлена за полиномиальное время, в зависимости от количества всех возможных решений полный перебор может потребовать экспоненциального времени работы.

В криптографии на сложности полного перебора основывается оценка криптостойкости шифров. В частности, шифр считается криптостойким, если не существует метода «взлома» существенно более быстрого чем полный перебор всех ключей.

Пример продолжительности подбора

Полное время раскрытия криптофайла для частного случая (100000 паролей в секунду; 36 символов в алфавите (латинские буквы + цифры)).Знаков Кол-во вариантов Время перебора
1 36 менее секунды
2 1296 менее секунды
3 46656 менее секунды
4 1679616 17 секунд
5 60466176 10 минут, 5 секунд
6 2176782336 6 часов, 2 минуты
7 78364164096 9 дней, 2 часа, 16 минут, 26 секунд
8 2.8211099×1012 10 месяцев, 23 дня, 52 минуты, 37 секунд
9 1.0155995×1014 32 года, 3 месяца, 7 дней, 12 часов, 11 минут
10 3.6561584×1015 1161 год, 8 месяцев, 26 дней, 18 часов, 33 минуты, 40 секунд
11 1.3162170×1017 41822 года, 7 месяцев, 20 дней, 6 часов, 44 минуты, 22 секунды
12 4.7383813×1018 1505614 лет, 11 месяцев, 30 дней, 1 час, 11 минут, 45 секунд

При переборе с использованием технолигии nVidia CUDA на GeForce 9800GT скорость перебора достигает 2 000 000 000 паролей в секунду.