Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Delphi: Общие вопросы > Random

Автор: SlaUr 12.3.2004, 14:29

Чисто в позновательных целях меня интересует алгоритм работы функии Random .
Например в электронике случайное число можно получить преребирая с высокой частотой числа и при нажатии на кнопку считать из счетчиков число . А как получить случайное число в компьютере для меня загадка.

Автор: x77 12.3.2004, 14:46

функции, подобные рэндому (WriteLn, например) а также всякие константы типа TRUE и пр. определены не в коде, а на уровне компилятора. так что посмотреть их исходники, увы, возможным не представляется. но в общем и целом используется алгоритм перебора от некоего базового числа (число это инициализирует проедура Randomize по значениям системного времени).

Автор: <Spawn> 12.3.2004, 16:34

типичная формула:

Код

Ni = [Ni-1*A + B] mod N

, где A, B, N надлежащим образом выбранные константы, например, A = 1 103 515 245, B = 12 345, C = 32 767.

Автор: RA 12.3.2004, 17:03

Вот тебе статья на эту тему, автор bad_guy

Код

Есть в Delphi две интересные функции: Randomize и Random, а также переменная RandSeed. Надеюсь, что вы знаете об их использовании. Но, наверняка, редко используете переменную RandSeed (dword), а вот с ней то я и захотел разобраться, а также решил поделиться своим опытом с вами. 

Поскольку я всё-таки крэкер, давайте пойдём крэкерским путём - возьмём готовую программу и поглядим как она работает - я взял "Генератор случайных паролей", написанный Цованяном Романом Сейрановичем. Но сначала я посмотрел как же Randomize рандомайзит, на основе чего ? Оказывается, на основе GetSystemTime, которая возвращает текущую дату и точное время (с миллисекундами) но не у нас, а по Гринвичу, для меня это было - на 4 часа меньше, чем на часах. Затем я поглядел алгоритм функции Randomize - он выглядит в Delphi5 следующим образом: 

var St: systemtime;
GetSystemTime(St);
RandSeed := ((St.wHour*$3c + St.wMinute)*$3c + St.wSecond)*$3e8+St.wMilliseconds; 

Как видите, всё очень просто. А сама функция Random уже использует только переменную RandSeed, берёт на основе неё случайное число, а потом меняет RandSeed, причём строго математически, то есть если при каждом запуске программы заносить в RandSeed одинаковую переменную, то набор "случайных" чисел, полученных с помощью Random при том же диапазоне будет такой же. 

Я решил провести небольшой опыт по взлому пароля, сгенерированного с помощью программы "Генератор случайных паролей". Запустил программу, взял длинный не взламываемый перебором пароль и запаковал с этим паролем в ZIP архив какой-то файл. На следующий день я "захотел" взломать этот архив и сделал следующим образом - посмотрел время создания архива и понял, что пароль был сгенерирован где-то в течение 2-3 минут до создания архива, и написал я небольшую программку, которая эмулировала Randomize, но я использовал не GetSystemTime, чтобы заполнить структуру St: Systemtime, а сам заполянял её с шагом одна миллисекунда и начиная от 3 минут до создания архива, не забывая также, что час взят по Гринвичу. Кроме того, я подглядел алгоритм создания пароля в программе "Генератор случайных паролей". То есть, я создал лист паролей. Для каждой миллисекунды я сделал не один пароль, а несколько (я "забыл" длину пароля, но помнил, что она где-то от 4 до 16 символов). То есть у меня получился внушительный лист паролей на почти 30 мегабайт. Затем я взял программку Advanced ZIP Password Recovery и поручил ей мой запароленный архив и дал в помощь свой 30 мегабайтный "словарик", через 3 секунды пароль был найден, надо же... 

Теперь давайте прикинем: если мы не знаем время генерации ключа, но знаем, что некто любит генерировать "трудновзламываемые" пароли с помощью "Генератора случайных паролей", то что мы будем делать ? Теперь посчитаем сколько миллисекунд в сутках 1000*60*60*24 = 86'400'000. Допустим, что пароль длинной от 4 до 20 символов, то есть каждую миллисекунду мы получим по 17 паролей, значит за сутки у нас будет 86400000*17 = 1'468'800'000 - всего то полтора миллиарда паролей. А программка Advanced ZIP Password Recovery перебирает, на моём не слишком крутом компьютере, по 520000 паролей в секунду. Значит любой пароль, сгенерированный в любой день, в любое время с помощью программы "Генератор случайных паролей" будет найден за 1468800000/520000 = 2824 секунды, то есть примерно за 50 минут. Единственной проблемой является, то что Advanced ZIP Password Recovery не поддерживает внешний плагин, который бы "давал" пароли для перебора, поэтому придётся создавать гигабайтные словари паролей, что не очень удобно, но весьма реально. 

Таким образом создавать "Генератор случайных паролей" на основе стандартных функций Delphi весьма глупо. "А как тогда не глупо ?" - спросите вы. Вообще, сейчас серьёзные организации пароли любят генерировать на основе белого шума. Нам же до этого шума далеко - брать нам его негде. А вот пользователя, сидящего за компьютером мы вполне можем использовать, а именно его замечательный человеческий фактор - аналоговую случайную функцию: запустим программу и заметим время, а потом, когда пользователь нажмёт "Генерировать пароль" - заметим время ещё раз - вот и одна случайность, можно также "последить" за траекторией мыши - вот вам вторая случайность. Теперь ещё можно поиcпользовать всякие хитрые функции GetDiskFreeSpace, также можно использовать хэш функции для замедления процесса создания листа паролей, то есть если ваша функция Randomize будет работать хотя бы 100 миллисекунд - уже потребуется 100 суток, чтобы создать весь лист паролей. Но тут ведь ещё одна проблема RandSeed - dword, то есть 32 бита, а это 2^32 = 4294967296. Поделим ка мы его на количество миллисекунд в сутках 4294967296/86'400'000 = 50, то есть потребуется 50*50 = 2500 минут в нашем случае, чтобы найти пароль от любого RandSeed, значит надо брать в качестве RandSeed переменную длинее 32 бит, мне приходит на ум лишь Int64 - вот тогда ваш пароль уже никто не взломает за разумное время. 

Вы скажете: что за фигня - зачем крэкеру это знать ? Может, и не надо, но по-моему уважающему себя крэкеру, а также "продвинутому" программисту полезно знать о вот таком нестандартном подходе к обыденным вещам, понять суть происходящего, познать основы криптоанализа и глубину возможностей крэкерства и недостатков высокоуровневого программирования, а не только снимать аспр, да и то через раз...

Автор: Pakshin A. S. 12.3.2004, 21:16

К слову про Random:
А что, програмёрам лень было включить Randomize в само тело Random'а? А то порой забудешь прописать Randomize и всё летит к чертям собачьим

Автор: x77 12.3.2004, 21:31

Pakshin A. S., нет, не лень. но тогда инициализация счётчика происходила бы при каждом вызове рэндома, что может быть не нужно.

Автор: Seti 14.3.2004, 02:35

x77
Нашел в System.pas код функции Randomize и _RandInit, на который выскакивает отладчик при их вызове.
Поскольку эти функции написаны на ассемблере, без разницы, где изучать их код - в System.pas или в любом отладчике типа SoftIce

Вот пример Random:

PUSH EBX
XOR EBX, EBX
IMUL EDX,[EBX].RandSeed,08088405H
INC EDX
MOV [EBX].RandSeed,EDX
MUL EDX
MOV EAX,EDX
POP EBX

Pakshin A. S.
Инициализацию нельзя вызывать в цикле, иначе случайные числа будут сильно повторяться. (когда-то сам наступил на эти грабли)

Автор: Jey_k 14.3.2004, 17:50

Цитата

типичная формула:

Код

Ni = [Ni-1*A + B] mod N

, где A, B, N надлежащим образом выбранные константы, например, A = 1 103 515 245, B = 12 345, C = 32 767.

Господа могу с уверенностью вам сказать что эта формула, а именно формула конгруэтного отношения случайной величины Гаусса в функции Random не применяется.
Имеет место экспоненциальный закон распределения случайной величины,рассчет ведется в интегральной форме, за начальное значение берется текущий бип системного таймера.

Автор: <Spawn> 14.3.2004, 17:56

Jey_k
Я просто как пример ее привел

Автор: Петрович 16.3.2004, 09:11

Цитата

Не прав, все они (точнее почти все) находятся в модуле SYSTEM, и исходники их есть в поставке. Просто они обычно имеют несколько отличающиеся имена, и реализаваны часто на ASMме

Автор: x77 16.3.2004, 16:20

Петрович, нету их там. открой систем:

Код


unit System; { Predefined constants, types, procedures, }
             { and functions (such as True, Integer, or }
             { Writeln) do not have actual declarations.}
             { Instead they are built into the compiler }
             { and are treated as if they were declared }
             { at the beginning of the System unit.     }