Оценить число комбинаций пароля (математика)

Eugie · 26 фев 2004, 22:16

Andy, так не надо перебирать ВСЕ варианты. Генерируй и проверяй только пароли вида 1*95*400*. Я же выше дал оценку числа вариантов (для 13-значных). Для 14-значных это будет 5.5*10^10 вариантов. Если скорость перебора 10^5 пар./сек, то времени уйдет 5.5*10^5 сек = 152 часа.

27 фев 2004, 01:15

Да, такой вот архив... Без даты...

Andy · 08 мар 2004, 18:55

Работа продолжается. Программа оптимизирована практически полностью, но осталось два "слабых звена".
1. Стандартный распаковщик.
2. функция преобразования из __int64 (asm - QWORD) в строку. Использование внешних функций типа _i64toa() или wsprintf порядком тормозят скорость. Поэтому предлагаю на обсуждение новую проблему - алгоритм быстрого преобразования из 64-битного числа в строку (строка десятичная). Лучше, конечно на ассемблере или на С++. Я видел пример на подобную тему, но там преобразование в "десятичную" строку производилось делением на 10 в цикле. Т.е. это очень медленный алгоритм, так как на каждую комбинацию пароля будет приходиться как минимум 12-16 операций деления на 10. У кого-нибудь есть на этот счет идеи?

chur · 09 мар 2004, 13:49

Можно попробовать такой алгоритм (код на Perl, но думаю всё понятно).

Код: Выделить всё

my $bignum = 0xfedcba9876543210; # int64
my $res; # здесь будет результат (строка)
my @digits = ('0', '1', '2', '3', '4', '5', '6', '7', '8', '9'); # массив символов
my @lg10   = (10000000000000000000,  # массив порядков
              1000000000000000000,
              100000000000000000,
              10000000000000000,
              1000000000000000,
              100000000000000,
              10000000000000,
              1000000000000,
              100000000000,
              10000000000,
              1000000000,
              100000000,
              10000000,
              1000000,
              100000,
              10000,
              1000,
              100,
              10);

for(my $i=0; $i<=$#lg10; $i++) {  # прим. конструкция $#lg10 возвращает индекс последнего элемента массива @lg10 
  my $dig=0;
  # пока число больше текущего порядка
  while ($bignum >= $lg10[$i]) {
    # вычитаем этот порядок из него
    $bignum -= $lg10[$i];
    # и, соответственно, все учитываем
    $dig++;
  }
  # сколько насчитали, столько и пишем. 
  # Т.к. начинаем с самого большого порядка, то первые нули не учитываем 
  $res .= $digits[$dig] if $res || $dig;
}
$res .= $digits[$bignum];

print $res;

Eugie · 09 мар 2004, 23:59

Andy,
По-моему, игра не стоит свеч. Ну какой % составит отношение (время_на_itoa/время_на_итерацию_в_целом)? - Наверняка небольшой. Соответственно, и выигрыш от возможной оптимизации будет невелик. Да и вряд ли можно существенно оптимизировать itoa по сравнению со стандартной. Мой личный опыт состоит в том, что очень_часто стандартные реализации весьма неплохо оптимизированы - ведь их не идиоты пишут

Andy · 10 мар 2004, 00:29

По-моему, игра не стоит свеч. Ну какой % составит отношение (время_на_itoa/время_на_итерацию_в_целом)?

Кстати, совсем не так. _i64toa вызывается при каждой итерации. Т.е. вызывается 10^14 раз. Работает она (_i64toa) довольно медленно, так как:

Функция расположена в другой DLL - вызов процедуры в другом потоке крайне медленная штука для таких случаев. Я же собираюсь сделать эту функцию макросом, следовательно +15% производительности.
Далее, эта функция написана для перевода числа в различные системы исчисления (10-ичная, 16-ричная и т.д.) - это дело тоже не надо, следовательно еще +5%.
Плюс можно ее под оптимизировать немного и получить в сумме до 40% выигрыша. Функции конечно пишут не идиоты, но ведь они не рассчитаны при разработке на экстремальную производительность.

К тому же я все равно на ассемблере это дело пишу, не охота завязываться на внешние необязательные DLL.

chur, сейчас буду смотреть, спасибо... Если я все правильно понял - хорошая идея и никакого деления

Eugie · 10 мар 2004, 17:59

i64toa вызывается при каждой итерации. Т.е. вызывается 10^14 раз.

Andy, честно говоря не понял, зачем перебирать все пароли, если известен шаблон. И зачем вообще нужно конвертировать _int64 в строку, разве не проще сразу генерировать подходящие пароли в строковом виде? Тогда и конверсия не понадобится

Теперь о варианте с конверсией. Я имел в виду, что время, уходящее на вызов _i64toa, может быть существенно меньшим, чем время на проверку пароля (в рамках одной итерации). Если так, то общий выигрыш от оптимизации _i64toa будет невелик. Конечно, если уходящее на конверсию время сравнимо или больше времени на проверку пароля, то оптимизировать _i64toa надо. Но я бы сначала-таки проверил

Насчет предложенного chur'ом алгоритма. Идея понятна: вместо медленных делений воспользоваться быстрыми вычитаниями. Насколько я помню, вычитание примерно на порядок быстрее деления. С другой стороны, для N-значного числа нужно N-1 делений, а вот кол-во вычитаний в алгоритме chur'а равно сумме всех десятичных цифр в числе, т.е. в среднем ~ 4.5*N. В общем, где-то вдвое быстрее получается, чем для стандартного алгоритма.

Andy · 10 мар 2004, 18:46

зачем перебирать все пароли, если известен шаблон

В принципе да, но ведь не известны позиции известных цифр в шаблоне. Т.е. я делал так: перебирал по очереди все пароли, преобразовывал каждый в строку и проверял, содержит ли эта строка "400", "95" ну и все такое. Ну если содержит, то попытка распаковки. Выяснилось, что просто перебрать все значения 14-15-значного пароля уже довольно долго, из-за этого - оптимизации до упора

разве не проще сразу генерировать подходящие пароли в строковом виде

А это хорошая мысль!! Должно быть быстрее! Уже проверяю

Mobys · 12 мар 2004, 18:26

Окончательные данные задачи:
Пароль только цифры 0-9 – 10 комбинаций.
Длина пароля [как было уточнено] 15, но так же известно, что пароль начинается с «1», причем «95» не соприкасается с «1». Имеются сочетания цифр «95» и «400», причем таким образом, что «95» стоит в пароле раньше «400» и они не соприкасаются. Так же известно, что после цифры «400» как минимум два знака.

Значит, общую маску пароля можно представить следующим образом:
1?95??????400??
Задача сводится к нахождению пароля в 9 цифр [между 1 и 95, между 95 и 400, и после 400], следовательно, перебор равен 10^9.
Осталось рассчитать количество комбинаций, при которых «95» и «400» спокойно перемещаются в пространстве [между 1? и последними двумя цифрами]:
формулой for i:=6 downto 1 do sum:=sum+i;
короче операции сводятся к 21 перестановке внутри (21 маска для решения проблемы):
1? 95??????400 ??
1? 95?????400? ??
1? 95????400?? ??
1? 95???400??? ??
1? 95??400???? ??
1? 95?400????? ??
1? ?95?????400 ??
1? ?95????400? ??
1? ?95???400?? ??
1? ?95??400??? ??
1? ?95?400???? ??
1? ??95????400 ??
1? ??95???400? ??
1? ??95??400?? ??
1? ??95?400??? ??
1? ???95???400 ??
1? ???95??400? ??
1? ???95?400?? ??
1? ????95??400 ??
1? ????95?400? ??
1? ?????95?400 ??

Таким образом общее решение задачи сводится к 21 задаче подбора пароля из 9 неизвестных цифр.
А это 21*10^9 = 2,1*10^10 [при учете, что пароль в 15 символов].
Теперь можно спокойно подсчитать затраченное время [из расчета подбора 900 паролей в секунду]:
2.1*exp(10*ln(10)) / 900 = 23333333 секунды или 388889 минуты или 6481.5 часа или всего-навсего 270 дней с хвостиком.
Ну а если оптимизируешь подбор пароля под скорость 5000 pps, то статистика становится более приятной ;-) всего лишь 48 с хвостиком дней ;-)
You say: так вот скорость при переборе числового пароля ~100000 паролей/сек - то всего лишь 58.3 часа ;-)

А тот факт, что точно имеются цифры "2" и "6" . . . я думаю можно опустить, хотя на самом деле при правильном анализе может получиться приблизительно 50-100 задач [комбинаций нахождения цифр в пароле по выбранным условиям] по подбору пароля в 7 цифр.
Хотя может быть я что-то напутал, зато выглядит очень даже правдоподобно ;-)

Mobys.

Mobys · 13 мар 2004, 13:30

После окончательного анализа есть интересный вывод – присутствие цифр «2» и «6» существенно уменьшит количество комбинаций!
Рассмотрим на примере 1–й маски - 1?95??????400??:
Количество комбинаций перемещения «2» и «6» равно 8:
1295??????400?6
1295??????4006?
1295?????6400??
1295????6?400??
1295???6??400??
1295??6???400??
1295?6????400??
12956?????400??
Так как масок у нас 21 то общее число сводится к 21*8=168 комбинациям по нахождению пароля в 7 цифр:
168*10^7=1.68*10^9
А это в 12.5 раз меньше предыдущих вычислений.
Так что при скорости 100000 pps потребуется всего-навсего: 4,6 часа ;-)

Mobys.