О переборе паролей

[Trotil]

Пусть мощность множества возможных паролей - N (например, для 32 бит оно будет равно 2^32)

Задача - угадать пароль перебором возможных комбинаций.

Способ 1: последовательно перебирать все варианты: 0, 1, 2, .. N-1.
Способ 2: Случайно генерировать число y<N и опробовать его в качестве пароля.

Найти матожидание числа опробований до нахождения верного пароля (задача не сложная, поэтому ответы приводить пока не буду - пишите в комменты) - М1 и M2.

Интересней другое. M2 является верхней средней оценкой. И никакие хитрые способы не заставят повысить эту оценку. Она не зависит от того, сколько раз в год вы меняете пароль. Даже если вы будете менять его каждый день - алгоритм все равно наткнется на ваш пароль в среднем за M2 шагов.

@темы: Головоломки и занимательные задачи

Comments

[Dieter Zerium]

А разве среднее число опробований не будет равно для обоих способов (т.е., вообще говоря, всё равно, как перебирать, единственное, что неподходящие пароли второй раз пробовать не надо)?
вот безо всяких формул M1=N / 2, как мне кажется...

[Trotil]

Ну M1 = N/2 - это очевидно )))
M2 посчитать чуть сложнее, но тоже вполне по силам по стандартному теорверу )

единственное, что недоходящие пароли второй раз пробовать не надо)?

Во втором случае нет такого условия. Это как раз отличает первый случай от второго.

После того, как найдут M2 я поясню, в чем преимущества второго способа над первым (хотя M1<M2)

[Дилетант]

Trotil
Во втором для узнавания пароля на k-шагу вероятность равна (k от 1 до N я считаю, а не от нуля):
(N-1)^(k-1)/N^k?

[Trotil]

k от 1 до N

Только не до N а до бесконечности... И чему она равна, эта сумма?

[Дилетант]

Trotil
тьфу! До N я имела в виду количество вариантов.
*А что это за шифровка у тебя в дневнике?

[Trotil]

Да, и еще одна ошибка - это у вас сумма p(i)... Она будет равна 1, естественно. А матожидание - это немного другое.

[Дилетант]

Trotil я не помню формулы убывающей геом прогрессии )
Сейчас посмотрю )))

[Trotil]

Тьфу на меня - это не ошибка )))

узнавания пароля на k-шагу вероятность

Да, это верно. Меня смутил промежуток (я подумал, сумму там написали)

Прошу извинить.

[Дилетант]

Блин, но там же еще на k надо умножать!

[Дилетант]

Поговорили ))))

[Trotil]

тьфу! До N я имела в виду количество вариантов.

Да-да-да... Я уже понял, что понял не так )))

*А что это за шифровка у тебя в дневнике?

Я тестировал одну возможность... Кстати, ты там коммент можешь оставить, в этой шифровке?

[Дилетант]

Trotil нет, не могу ))) иначе бы я там спросила )))
А что такое пппппппп???

[Trotil]

хде? ))))

(считай, что ты ниче не видела ))))))

нет, не могу ))) иначе бы я там спросила )))

Вот именно такую возможность я и тестировал Как видишь - довольно успешно! )


Матожидание будешь считать? ))))

[Дилетант]

Формула такая:
M=Σ k(N-1)^(k-1)/N^k
k от 1 до ∞
???

[Trotil]

Да

[Дилетант]

Trotil
А есть какая-нибудь формула про скалярное произведение векторов, один из которых арифметическая прогрессия, а другой геометрическая?

Я же ни одной формулы для рядов не помню (((((

[Trotil]

Не знаю, если честно ))))

Не будем лишать удовольствия пока тех, кто возьмется подсчитать эту сумму?

[Дилетант]

Trotil я ухожу скоро ((((
так что желающих ждет масса удовольствия )))
до вечера я (по крайней мере) ответ не выложу )))
Думаю, ты тоже )))

[Trotil]

До вечера тогда. Пока-пока

[Amicus Plato]

Trotil
Получилось N!!!!!
Ыыы!!!
Только скажи, что неправильно!!!!

[Trotil]

Правильно получилось

[Amicus Plato]

Trotil
То-то ж! ))))
Получилась бесконечная сумма бесконечных сумм ))))
И она свернулась!
Давненько не чувствовала так остро, что жизнь удалась ))))
А дальше-то что?

[Trotil]

А дальше-то что?

А дальше вот что: числа N/2 и N отличаются всего в два раза.

Пусть все это дело опробуют несколько процессоров (T процессоров). Ключевое пространство разбивается на T секторов, каждый процессор работает независимо в своем секторе. Матожидание будет равно N/2T.

И второй случай: каждый из этих процессоров работает независимо. Более того, в один момент времени может быть сгенерированна одна и таже операция. И, несмотря на то, что нет никаких ограничений, матожидание будет равно N/T.

И опять разница всего лишь в два раза.

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

Очень многие троянские программы работают именно по принципу 2.

[Дилетант]

Trotil
да-а...

ФАНТАСТИКА!

суровая вещь теория вероятностей...

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