Сейчас на форуме: zds, UniSoft (+5 невидимых)

 eXeL@B —› Программирование —› Небольшой TrueRNG
Посл.ответ Сообщение

Ранг: 369.8 (мудрец), 400thx
Активность: 0.39↘0
Статус: Участник

 Создано: 08 января 2013 09:21
· Личное сообщение · #1

Хочу поделиться крайне простым и маленьким кодом генератора истинно случайных чисел. Это не ГПСЧ, это настоящий недетерминированный ГСЧ. Принцип работы ясен из комментариев к коду.

Code:
  1. unsigned char randomBit()
  2. {
  3.          unsigned __int64 t0 = __rdtsc(); // читаем счетчик тактов процессора
  4.          
  5.          // ждем следующего тика таймера
  6.          //  перед генерацией длинных последовательностей бит не забудьте
  7.          //  вызвать timeBeginPeriod(1) для ускорения системного таймера
  8.          unsigned long t1 = timeGetTime();
  9.          while (t1 == timeGetTime()) Sleep(1);
  10.  
  11.          // определяем сколько тактов процессора прошло за время 1 тика таймера
  12.          // тик таймера минимум 1мс, при частоте процессора 1ггц периоды генераторов
  13.          // отличаются на 6 порядков, при таком различии значение частоты и фазы неизбежно
  14.          // будет плавать даже на генераторах синхронизированных ФАПЧ, что дает нам
  15.          // истинно случайные числа, случайность которых возникает из теплового шума
  16.          t0 = __rdtsc() - t0;
  17.  
  18.          // получаем бит энтропии складывая по модулю 2 все биты результата на тот случай
  19.          // если у каких-нибудь процессоров счетчик тактов увеличивается не на единицу
  20.          while (t0 > 1) t0 = (t0 >> 1) ^ (t0 & 1);
  21.          return t0 & 1;
  22. }


Достоинства: простота, компактность, самая настоящая тру-случайность без движений мышкой, шумов звуковой карты и прочей сложной фигни.
Недостатки: максимальная производительность - 1000 бит в секунду, аппаратная и архитектурная зависимость (только x86/amd64, случайность на виртуалках под вопросом).

З.Ы. В голом виде запрещается использовать в крипто, используйте как один из многих источников энтропии для ГПСЧ.

-----
PGP key <0x1B6A24550F33E44A>

| Сообщение посчитали полезным: Alchemistry, OnLyOnE, plutos, Gideon Vi, Getorix


Ранг: 568.2 (!), 465thx
Активность: 0.55↗0.57
Статус: Участник
оптимист

 Создано: 08 января 2013 12:11
· Личное сообщение · #2

ntldr пишет:
Это не ГПСЧ, это настоящий недетерминированный ГСЧ
Вот вы бедные мучаетесь, свизданули бы уже код с Delphi Randomize и не парились.
ntldr пишет:
случайность на виртуалках под вопросом
как и её роботаспособность зависло на глухо программа с таким кодом.

-----
Чтобы правильно задать вопрос, нужно знать большую часть ответа. Р.Шекли.

Ранг: 590.6 (!), 408thx
Активность: 0.36↘0.18
Статус: Модератор

 Создано: 08 января 2013 12:58
· Личное сообщение · #3

ntldr
Сомневаюсь в True RNG, но это уже и не ПРНГ.
В своем первозданном виде все тесты на случайность проходит?

-----
старый пень

Ранг: 262.5 (наставник), 337thx
Активность: 0.34↘0.25
Статус: Участник

 Создано: 08 января 2013 13:57
· Личное сообщение · #4

ClockMan пишет:
Вот вы бедные мучаетесь, свизданули бы уже код с Delphi Randomize и не парились.
http://www.cracklab.narod.ru/doc/rand.htm




Ранг: 1131.7 (!!!!), 447thx
Активность: 0.67↘0.2
Статус: Участник

 Создано: 08 января 2013 14:00
· Личное сообщение · #5

ClockMan пишет:
Вот вы бедные мучаетесь, свизданули бы уже код с Delphi Randomize и не парились.

закусывать надо.

| Сообщение посчитали полезным: yagello


Ранг: 568.2 (!), 465thx
Активность: 0.55↗0.57
Статус: Участник
оптимист

 Создано: 08 января 2013 14:59
· Личное сообщение · #6

TryAga1n пишет:
http://www.cracklab.narod.ru/doc/rand.htm
Судя по году статьи и то что в Randomize используется GetSystemTime видать старая версия Delphi,в новой идёт получения числа через QueryPerformanceCounter,такчто вы дедушкаTryAga1n устарели.
Gideon Vi пишет:
закусывать надо.
А вам занюхивать.

-----
Чтобы правильно задать вопрос, нужно знать большую часть ответа. Р.Шекли.


Ранг: 568.2 (!), 465thx
Активность: 0.55↗0.57
Статус: Участник
оптимист

 Создано: 08 января 2013 15:30
· Личное сообщение · #7

Code:
  1.          unsigned __int64 t0 = __rdtsc(); // читаем счетчик тактов процессора
  2.          
  3.          // ждем следующего тика таймера
  4.          //  перед генерацией длинных последовательностей бит не забудьте
  5.          //  вызвать timeBeginPeriod(1) для ускорения системного таймера
  6.          unsigned long t1 = timeGetTime();
  7.          while (t1 == timeGetTime()) Sleep(1);
  8.  
  9.          // определяем сколько тактов процессора прошло за время 1 тика таймера
  10.          // тик таймера минимум 1мс, при частоте процессора 1ггц периоды генераторов
  11.          // отличаются на 6 порядков, при таком различии значение частоты и фазы неизбежно
  12.          // будет плавать даже на генераторах синхронизированных ФАПЧ, что дает нам
  13.          // истинно случайные числа, случайность которых возникает из теплового шума
  14.          t0 = __rdtsc() - t0;
  15.  
  16.          // получаем бит энтропии складывая по модулю 2 все биты результата на тот случай
  17.          // если у каких-нибудь процессоров счетчик тактов увеличивается не на единицу
  18.          while (t0 > 1) t0 = (t0 >> 1) ^ (t0 & 1);
  19.          return t0 & 1;


Вашь код большая ошибка...
Вы вызываете в начале
unsigned __int64 t0 = __rdtsc(); потом t0 = __rdtsc() - t0; а вы знаете что значение в вашем коде будут вальвироватся в пределе одного значения(старый трюк на детект отладчика измерения тиков)
ну а дальше timeGetTime(сколько миллисекунд прошло с момента запуска ОС) это вообще упрастит нам задачу а дальше как http://www.cracklab.narod.ru/doc/rand.htm.

-----
Чтобы правильно задать вопрос, нужно знать большую часть ответа. Р.Шекли.


Ранг: 2014.5 (!!!!), 1278thx
Активность: 1.34↘0.25
Статус: Модератор
retired

 Создано: 08 января 2013 15:40
· Личное сообщение · #8

Вообще говоря, не уловил скептицизма.
Во-первых, антиотладка-это замер выполнения чистого кода, который в идеале не переключается. Здесь же явно переключения будут из-за спячки.
Во-вторых, даже если и есть гарантия, что разница будет, скажем, от 1 и 1000, никаких предположений по поводу ксора всех битов ты не сделаешь. Хотя бы ввиду того, что весь большой интервал сводится к 1 биту.
timeGetTime же в самом генераторе практически не участвует, а нужно скорее просто для того, чтобы прождать достаточный промежуток времени, чтобы интервал разницы был побольше.
З.Ы. Что же касается ранда-зная начальное значение и алгоритм ты можешь найти все последующие значения. В данном случае это не применимо (поэтому это и не ГПСЧ), посему аналогию с рандом не совсем понимаю.



Ранг: 590.6 (!), 408thx
Активность: 0.36↘0.18
Статус: Модератор

 Создано: 08 января 2013 16:31
· Личное сообщение · #9

Ну кое-какие предположения сделать все-таки можно.
Например, выделить факторы, влияющие на генратор. Это будут ГЧ и шедулер ОС. Минимизировать влияние второго можно регулируя приоритеты. Для первого труднее - нужно добиться стабильного температурного режима. А возможно и электромагнитного фона.
Опять же, что делать с эмулируемыми средами?
В случае железного тру ГСЧ никакие пляски не помогут.

Низкую скорость можно компенсировать использованием сильной крипты и положительной связью от самого ГСЧ, домешивая время от времени новые данные.

-----
старый пень

Ранг: 488.1 (мудрец), 272thx
Активность: 0.35↘0
Статус: Участник

 Создано: 08 января 2013 19:46
· Личное сообщение · #10

Касательно ГСЧ очень неплохо от майкрософт пресса "Защищенный код" было написано. там и факторы были описаны, которыми можно пользоваться и косяки, на которые обычно наступают

-----
Наша работа во тьме, Мы делаем, что умеем. Мы отдаем, что имеем, Наша работа во тьме....

Ранг: 369.8 (мудрец), 400thx
Активность: 0.39↘0
Статус: Участник

 Создано: 08 января 2013 21:15
· Личное сообщение · #11

Мда. Никто кроме арчера попросту не понял как оно работает. Учите матчасть господа, что такое системный таймер и что такое time stamp counter.
Я объяснять не буду. Топик можно закрывать.

-----
PGP key <0x1B6A24550F33E44A>
 eXeL@B —› Программирование —› Небольшой TrueRNG
Эта тема закрыта. Ответы больше не принимаются.
   Для печати Для печати