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

[Andy]

Есть RAR архив, пароль к нему увы забыт... Необходимо все-таки архив распаковать, но использовать стандатные программы "ломалки" не представляется возможным, так как не учитывая конкретные особенности пароля ломать надо будет 100 лет :)
Информация о пароле следующая:

• Пароль представлен числовой строкой (только цифры)
• Колличество цифр 13-14 (для определенности возьмем 14 - т.е. длина пароля 14 символов, все из которых цифры)
• Начинается с "1"
• Имеются сочетания "95" и "400"
• Точно имеются цифры "2" и "6"
• никакие цифры не располагаются подряд более, чем по 2 штуки

Если настроить программу Advanced RAR Password Recovery на грубый перебор и использование только цифр, то ждать придется несколько сотен лет (все-таки 14 символов, блин).
Что требуется. Мне нужно оценить с учетом вышеперечисленных факторов на сколько сократится множество значений пароля. Т.е. имеет ли мне смысл пытаться написать свой распаковщик, займет ли с учетом этих особенностей разархивация приемлемое время несколько месяцев. Если математики тут есть - это дело не трудно прикинуть? Пока только это...

[DeeJayC]

Есть RAR архив, пароль к нему увы забыт... Необходимо все-таки архив распаковать, но использовать стандатные программы "ломалки" не представляется возможным, так как не учитывая конкретные особенности пароля ломать надо будет 100 лет
Информация о пароле следующая:

• Пароль представлен числовой строкой (только цифры)
• Колличество цифр 13-14 (для определенности возьмем 14 - т.е. длина пароля 14 символов, все из которых цифры)
• Начинается с "1"

Уже 13

• Имеются сочетания "95" и "400"
• Точно имеются цифры "2" и "6"
• никакие цифры не располагаются подряд более, чем по 2 штуки

Поскольку только цифры - то время сокращается раз этак в 5
( отбросим всякие буквы и символы типа +- ), если case-insensitive,
то в 3...

[AiK]

Дык символов или всё же цифр? Если мне мой склероз не изменяет, то в десятичной системе измерений ты можешь записать
при помощи 10 цифр в 14-ти позициях 10^14 различных чисел. Т.е. при переборе хотя бы 1млн паролей в секунду тебе понадобится "всего" три года и пару месяцев.
Если цифр 13 (начинается с 1) - уже нужно будет примерно 3.5 месяца.

[AiK]

Имеются сочетания "95" и "400"

Точно имеются цифры "2" и "6"

Это очень ценное утверждение. Только вот точно не помню я комбинаторики. Совсем.
Переставновки там, сочетания... Если очень грубо, то то, что ты знаешь 7 цифр из 14-ти,
но не знаешь на каких они местах даёт тебе выигрыш в два раза... Хотя это просто не серъёзное
утверждение - надо справочник смотреть.

[Andy]

утверждение - надо справочник смотреть.

Да, это точно.

Вобщем поговорил я с человеком, чей архив надо разархивировать и уточнил еще некоторые детали.

Примерный пароль: "1?95?6??400?2??"
Знаки вопроса - неизвестные символы, позиции известных символов неизвестны . Точно известно, что комбинация "95" расположена перед "400". После комбинации "400" есть как минимум еще два символа-цифры.

Я пробовал его (архив) поковырять программой Advanced Archive Password Recovery от ЭлкомСофта, задал пространство символов - и тем не менее скорость перебора на моем компе 900паролей/сек. При компрессии использовался WinRAR 2.90, а начиная с этой версии, как я узнал существенно усложнен алгоритм шифрования, поэтому так медленно.
А теперь предположим, что я напишу распаковщик на ассемблере (пока еще не знаю как, нужно формат RAR'a найти (может кто знает где?) ), оптимизирую код под комп, который будет подбирать пароли - я так думаю больше 5000p/s не получу. Поэтому чтобы время зря не терять нужно посчитать все это дело...

[DeeJayC]

Лады.. Поехали. Имеем 35 символов. (A-Z, 0-9). В первом случае -33 (не может быть 1 и 9)
Во втором случае - опять 33 ( не может быть 5 и 6 )
В третьем и четвёртом 34, при этом не повторяются - 34 комбинации, т.е не учитывается диагональ
В пятом - опять 33 и два последних - опять 34, 34 ( потому как в последнем случае ничего нет)

Имеем

33 * 33 * 34 * 33 * 33 * 34 * 34 = 46611438984

[Eugie]

Имеем 35 символов. (A-Z, 0-9).

Откуда ж 35? Ведь одно из условий (цитата)

Пароль представлен числовой строкой (только цифры)

На самом деле вырисовывается такая калькуляция: из 13 цифр (первую 1 отбросим) известны 7, из которых 5 в виде фрагментов "95" и "400" (самая ценная информация!), причем "95" идет раньше "400". Остальные условия игнорируем, т.к.формализовать их сложно, а перебор они сильно не ограничивают.

Тогда пароль можно записать в виде *95*400*, где * означает разные варианты наборов цифр суммарной длины 8 знаков.

Число вариантов пароля можно оценить так: (число всевозможных 8-знаковых чисел)*(количество разбиений ('разрезов') 8-знаковой последовательности на 3 части). Первое, очевидно, равно 10^8. Второе равно сумме 1+2+..+9=45. Итого имеем 4.5*10^9 вариантов - на порядок меньше, чем у DeeJayC - Желающие могут улучшить оценку, учитывая доп.условия.

---
Ох, нелегкая это работа - из болота тащить бегемота! (с) К.Чуковский

[DeeJayC]

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

И вот ещё... 1?95 - не 1995 ли часом? Не год создания архива?

[Eugie]

Угу, а 400 - время

[Andy]

И вот ещё... 1?95 - не 1995 ли часом? Не год создания архива

Нет, архив создан примерно 2 года назад, только вышедшим тогда WinRar 2.90. Там навернутый алгоритм шифрования из-за чего подбираются комбинации довольно медленно.
Я пробовал оценить число вариантов подбором "в лоб", т.е. прогу написал которая все пароли по очереди перебирает и подсчитывает подходящие - прога работала долго, до ее окончания работы я ждать не стал. Было очевидно, что паролей вобщем дофига...
И тем не менее. Я написал программу для подбора на ассемблере, причем для распаковки использую стандартную библиотеку unrar.dll (на http://www.rarsoft.com взял) - так вот скорость при переборе числового пароля ~100000 паролей/сек. Этого всё равно мало, т.к. по окончательному заключению длина пароля все-таки 14-15 символов (а не 13-14), хотя все предыдущие условия остались верны. Числовой пароль из 11 символов программа подбирает быстро, а вот для подбора 14 (без учета первой "1") уже нужно искать мощный компьютер.
Сейчас одна вобщем проблема - избавиться от стандартной unrar.dll, так как именно она сейчас в моей программе "самое слабое звено". Только расхакивать её и извлекать из нее процедуры времени нет (да и сложновато это все-таки)...