ФЭНДОМ


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

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

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

Методы оптимизации полного перебора Править

Для увеличения скорости подбора ключа используется распараллеливание вычислений. Известно два направления распараллеливания.

  • Во-первых, построение конвейера. Пусть алгоритм соотношения E_k\ (x) = y можно представить в виде цепочки простейших действий (операций):  {O_1\ ,O_2,...,O_N} . Возьмем  N\ процессоров  {A_1\ ,A_2,...,A_N} , зададим их порядок и положим, что  i\ — ый процессор выполняет три одинаковые по времени операции:
    1. приём данных от  (i - 1)\ — го процессора;
    2. выполнение операции  O_i\ ;
    3. передача данных следующему  (i + 1)\ -му процессору.
    Тогда конвейер из  N\ последовательно соединённых, параллельно и синхронно работающих процессоров работает со скоростью  v/3\ , где  v\ — скорость выполнения одной операции одним процессором.
  • Второе направление распараллеливания состоит в том, что множество  K\ всех возможных ключей разбивается на непересекающиеся подмножества  {K_1\, K_2, ... , K_N} . Система из  Q\ машин перебирает ключи так, что  i\ — ая машина осуществляет перебор ключей из множества  K_i\ , i = 1 .. Q . Система прекращает работу, если одна из машин нашла ключ. Самой трудное — это разделение ключевого множества. Но если каждый процессор начнёт вычисление с какого-то произвольного ключа, то время нахождения увеличится, а схема значительно упростится. Среднее число шагов в этом случае составляет  |K|/N\ , где  |K|\ — число элементов во множестве ключей, а  N\ — число процессоров.

Реализация распараллеливания Править

Реализовать распараллеливание можно по-разному.

  • Например, создать вирус для распространения программы-взломщика в глобальной сети. Он должен использовать свободное время процессора для перебора ключей. Рано или поздно один из зараженных компьютеров обнаружит искомый ключ и оповестит об этом злоумышленника.
  • Существуют также более оригинальные идеи распараллеливания вычислений:
    • «Китайская лотерея», создание «криптоаналитических» водорослей и животных.
      1. Китайская лотерея предполагает, что в каждый радиоприемник и телевизор встроена микросхема, запрограммированная на автоматическую проверку различных множеств ключей после получения по эфиру пары открытый текст/шифртекст.
      2. С использованием биотехнологий можно сделать криптоанализ ещё эффективнее. Можно создать существо, состоящее из клеток, умеющих тестировать ключи. Каким-то образом в клетки передаются пары открытый текст/шифртекст. Решения переносятся к органам речи специальными клетками, путешествующими по кровеносной системе существа. В доисторические времена средний динозавр состоял примерно из 1014 клеток (без микробов). Если каждая клетка может выполнять миллион шифрований в секунду, вскрытие 56-битового ключа займёт  7 * 10^{-4} сек, а 64-битового — не более 0,2 сек.
      3. Ещё один способ — создание водорослей, умеющих вскрывать криптографические алгоритмы методом полного перебора. Водоросли могут покрывать большие пространства, что теоретически позволит создать что-то вроде распределённого компьютера с огромным числом процессоров.

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

Полное время раскрытия криптофайла для частного случая (100000 паролей в секунду; 36 символов в алфавите (латинские буквы + цифры)).

ЗнаковКол-во вариантовВремя перебора
136менее секунды
21296менее секунды
346656менее секунды
4167961617 секунд
56046617610 минут, 5 секунд
621767823366 часов, 2 минуты
7783641640969 дней, 2 часа, 16 минут, 26 секунд
82.8211099x101210 месяцев, 23 дня, 52 минуты, 37 секунд
91.0155995x101432 года, 3 месяца, 7 дней, 12 часов, 11 минут
103.6561584x10151161 год, 8 месяцев, 26 дней, 18 часов, 33 минуты, 40 секунд
111.3162170x101741822 года, 7 месяцев, 20 дней, 6 часов, 44 минуты, 22 секунды
124.7383813x10181505614 лет, 11 месяцев, 30 дней, 1 час, 11 минут, 45 секунд

(данные получены посредством программы Hacking Time Analizer)

Таким образом, пароли длиной менее 6 символов, в общем случае, не являются надежными.

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

Примечания Править

cs:Útok hrubou silou

da:Brute force-angreb el:Brute-force attack en:Brute force attack es:Ataque de fuerza bruta fr:Attaque par force brute he:כוח גס id:Serangan brute-force ja:総当たり攻撃 lt:Grubios jėgos ataka nl:Brute force pl:Atak brute force sv:Brute force zh:穷举法

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

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

Также на ФЭНДОМЕ

Случайная вики