Небольшой TrueRNG v2.0

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

Посл.ответ	Сообщение
ntldr Ранг: 369.8 (мудрец), 400thx Активность: 0.39↘0 Статус: Участник	Создано: 29 января 2013 21:09 · Личное сообщение · #1 Продолжение топика https://ssl.exelab.ru/f/action=vthread&forum=6&topic=20695 Вторая версия алгоритма в которой решены почти все существующие проблемы. Проходит статтесты на виртуалках (кроме детерминированных эмуляторов вроде Bochs), проходит корреляционные тесты при одновременном запуске множества копий, работает надежно на всем доступном мне железе (в том числе на процессорах в которых TSC увеличивается кратно). Минусы - скорость генерации снижена, генерация может завершиться ошибкой. Code: static void waitNextTick() { unsigned long t1 = timeGetTime(); do { Sleep(1); } while (t1 == timeGetTime()); } static unsigned char extractBit(unsigned long t) { unsigned short t0 = t & 0xFFFF; unsigned short t1 = (t >> 16) & 0xFFFF; unsigned long delta=0x9e3779b9, sum = 0; for (int i = 0; i < 64; i++) { sum += delta; t0 += (t1<<4) ^ (t1 + (sum & 0xFFFF)) ^ (t1>>5); t1 += (t0<<4) ^ (t0 + (sum & 0xFFFF)) ^ (t0>>5); } return t0 & 1; } unsigned char randomBit() { for (int i = 0; i < 128; i++) { unsigned __int64 t0 = __rdtsc(); waitNextTick(); unsigned __int64 t1 = __rdtsc() - t0; waitNextTick(); unsigned __int64 t2 = __rdtsc() - t0 - t1; // отбрасываем тайминги больше 0xFFFFFFFF как заведомо неправдоподобные if (t1 > 0xFFFFFFFF \|\| t2 > 0xFFFFFFFF) continue; // отбрасываем слишком похожие тайминги (отсеиваются очень редкие совпадения) if (_abs64(t1 - t2) < 64) continue; // извлекаем из двух таймингов по одному биту используя псевдослучайный экстрактор unsigned char bit0 = extractBit(t1 & 0xFFFFFFFF); unsigned char bit1 = extractBit(t2 & 0xFFFFFFFF); // используем экстрактор фон Неймана // для устнанения значительных статистических отклонений на виртуалках if (bit0 ^ bit1) return bit0; } // если генерация не удалась за 128 попыток, мы находимся в полностью детерминистичном эмуляторе // либо счетчик тактов процессора полностью непригоден для данного алгоритма __debugbreak(); } З.Ы. перед генерацией не забываем вызвать timeBeginPeriod(1), иначе всё будет совсем медленно. ----- PGP key <0x1B6A24550F33E44A> \| Сообщение посчитали полезным: 4kusNick, plutos, kioresk, Getorix, Gideon Vi

DrGolova Ранг: 199.6 (ветеран), 12thx Активность: 0.1↘0 Статус: Участник www.uinc.ru	Создано: 30 января 2013 05:23 · Личное сообщение · #2 Йа дебил - объясните мне, зачем это нужно? Производные XorShift'а по определению не криптостойкие генераторы, сколько бы туда не вмешивались rdtsc Или это попытка детектирования виртуалок/гипервизоров? Тогда д0вай консольку, печатающую результат - проверим.
ntldr Ранг: 369.8 (мудрец), 400thx Активность: 0.39↘0 Статус: Участник	Создано: 30 января 2013 06:31 · Личное сообщение · #3 DrGolova пишет: Йа дебил - объясните мне, зачем это нужно? Просто для интереса. Попытка сделать как можно более простой "чистый" ГСЧ не требующий ввода внешних данных. Для практических задач малопригодно, ибо там рулят криптостойкие ГПСЧ с подмешиванием энтропии из многих источников. DrGolova пишет: Производные XorShift'а по определению не криптостойкие генераторы, сколько бы туда не вмешивались rdtsc Так суть в том, что это ГСЧ а не ГПСЧ. Следующий генерируемый бит никак не зависит от предыдущих (у ГСЧ нет состояния). Вся магия функции extractBit нужна лишь для свертки 32 бит в 1 при неизвестном (и предположительно неслучайном) распределении исходных данных. Энтропию этот алгоритм берет из джиттера между системным таймером и тактовой частотой процессора (этот эффект есть как на железе так и в виртуалках, за одним единственным исключением - Bochs). ----- PGP key <0x1B6A24550F33E44A> \| Сообщение посчитали полезным: Jupiter

Для печати