Метод грубой силы


Метод грубой силы

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

Любая задача из класса 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. Ещё один способ — создание водорослей, умеющих вскрывать криптографические алгоритмы методом полного перебора. Водоросли могут покрывать большие пространства, что теоретически позволит создать что-то вроде распределённого компьютера с огромным числом процессоров.

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

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

Знаков Кол-во вариантов Время перебора
1 36 менее секунды
2 1296 менее секунды
3 46 656 менее секунды
4 1 679 616 17 секунд
5 60 466 176 10 минут, 5 секунд
6 2 176 782 336 6 часов, 2 минуты
7 78 364 164 096 9 дней, 2 часа, 16 минут, 26 секунд
8 2,821 109 9x1012 10 месяцев, 23 дня, 52 минуты, 37 секунд
9 1,015 599 5x1014 32 года, 3 месяца, 7 дней, 12 часов, 11 минут
10 3,656 158 4x1015 1161 год, 8 месяцев, 26 дней, 18 часов, 33 минуты, 40 секунд
11 1,316 217 0x1017 41 822 года, 7 месяцев, 20 дней, 6 часов, 44 минуты, 22 секунды
12 4,738 381 3x1018 1 505 614 лет, 11 месяцев, 30 дней, 1 час, 11 минут, 45 секунд

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

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

При переборе с использованием технологии nVidia

См. также


Wikimedia Foundation. 2010.

Смотреть что такое "Метод грубой силы" в других словарях:

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

  • Метод пузырька — Сортировка простыми обменами, сортировка пузырьком (англ. bubble sort)  простой алгоритм сортировки. Для понимания и реализации этот алгоритм  простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: O(n²). Алгоритм… …   Википедия

  • Полный перебор — У этого термина существуют и другие значения, см. Перебор. Полный перебор (или метод «грубой силы», англ. brute force)  метод решения математических задач. Относится к классу методов поиска решения исчерпыванием всевозможных… …   Википедия

  • Криптограммы Бейла — Обложка первого издания брошюры «Документы Бейла…» Криптограммы Бейла  три зашифрованных сообщения, как то полагается, несущих в себе информацию о местонахождении клада из золота, серебра и драгоценных камней, зарытого якобы на терр …   Википедия

  • Snefru — Snefru  это криптографическая однонаправленная хеш функция, предложенная Ральфом Мерклом. (Само название Snefru, продолжая традиции блочных шифров Khufu и Khafre, также разработанных Ральфом Мерклом, представляет собой имя египетского… …   Википедия

  • Атака на блочный шифр — попытка взлома (дешифрования) данных, зашифрованных блочным шифром. К блочным шифрам применимы все основные типы атак, однако существуют некоторые, специфичные лишь для блочных шифров, атаки. Содержание 1 Типы атак 1.1 Общие …   Википедия

  • Нейрокриптография — Нейрокриптография  раздел криптографии, изучающий применение стохастических алгоритмов, в частности, нейронных сетей, для шифрования и криптоанализа. Содержание 1 Определение 2 Применение …   Википедия

  • Задача коммивояжёра — Оптимальный маршрут коммивояжёра через 15 крупнейших городов Германии. Указанный маршрут является самым коротким из всех возможных 43 589 145 600. Задача коммивояжёра (англ. Travelling salesman problem, TSP) (коммивояжёр …   Википедия

  • N-Hash — Криптографическая хеш функция Название N Hash Создан 1990 Опубликован 1990 Размер хеша 128 бит Число раундов 12 или 15 Тип хеш функция N Hash  криптографическая …   Википедия

  • Задача о коммивояжере — Задача коммивояжёра (коммивояжёр  бродячий торговец) является одной из самых известных задач комбинаторной оптимизации. Задача заключается в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с… …   Википедия

Книги



Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.