Выполняю…
"Генераторы истинно случайных и псевдослучайных чисел
Генерация истинно случайных (непредсказуемых) чисел - одна из главных проблем возникающих при реализации любой криптосистемы. Огромное количество приложений имеют уязвимости связанные именно с предсказуемостью генерируемых паролей, «salt»-значений, сеансовых ключей, их суррогатов и т.д.
Я постарался сделать генератор для Windows-платформ, который генерирует истинно случайные числа (или очень близкие к ним) без участия человека, основываясь на энтропии шума звуковых карт. Идеи использования оцифрованного звука как источника информационной энтропии уже давно обитали в сети, поэтому я ни в коей мере не претендую на «первооткрывательство». Но с другой стороны, считаю уместным сказать:
эта реализация создана независимо от других в 1998 году (в 1999 генератор был усовершенствован);
основным отличием является использование именно естественного внутреннего шума звуковых карт, а не внешнего источника звука;
Генератор либо генерирует случайные числа, либо указывает причину, по которой это невозможно сделать. Равномерность распределения достигается за счет использования лучших из известных «Dedicated one-way Hash Functions». При соблюдении элементарных условий генерация предсказуемых чисел исключается, для дополнительной гарантии может быть использован простейший внешний генератор белого шума в слышимом диапазоне.
В ноябре 2003, к генератору на основе звукового шума я добавил накопительный генератор, а также обычные «грязные» линейные конгруэнтные генераторы.
Конгруэнтные генераторы Xn+1 = (A∙Xn+ C) mod M построены на базе трех модулей, которые уже давно хорошо себя зарекомендовали:
A = 1664525, предложен M.Lavaux & F.Janssens, период 232;
A = 6364136223846793005, предложен C.Haynes, период 264;
A = 40692, предложен P.L’Ecuyer, период 231-249;
Первый модуль используется для генерации 32-разрядных целых чисел и вещественных одинарной точности. Второй модуль применяется при генерации 64-разрядных целых чисел и вещественных удвоенной точности. Третий модуль повышает статистические показатели младших битов при генерации 80-битных вещественных чисел во внутреннем формате процессоров Intel.
Вещественные числа генерируются в диапазоне 0.0 ≤ x < 1.0, с равномерным распределением. Период третьего генератора составляет 39614076663892894440946139385, при этом возможно использовать полную точность внутрипроцессорного представления вещественных чисел.
Новый накопительный генератор – это отдельная тема. При его разработке я старался сделать генератор, который может работать как превосходный и быстрый генератор псевдослучайных чисел, а при источнике «непредсказуемости», и как мощный генератор криптографически стойких случайных чисел.
Затраты на обслуживание генератора и сбор «исходной случайности» минимальны. Генератор может быть легко применен в embedded системах, а также легко описан на VHDL (реализован аппаратно).
Генератор построен на 32 параллельных регистрах сдвига по неприводимому полиному X64 + X4 + X3 + X (период 264-1), и нелинейной функции обратной связи «сшивающей» генераторы воедино. Псевдокод генератора на языке «C» приведен ниже, операцией «<<<» обозначен циклический сдвиг влево:
- Код: Выделить всё
static struct { unsigned Head, Tail;
unsigned Pool[64];} LyRandom;
void LyRandomPushSalt(unsigned Salt)
LyRandom.Pool[LyRandom.Head++] += Salt;}
unsigned LyRandomGet()
unsigned Value = LyRandom.Pool[LyRandom.Tail] // X1 ^ LyRandom.Pool[LyRandom.Tail + 1] // X64
^ LyRandom.Pool[LyRandom.Tail + 62] // X4
^ LyRandom.Pool[LyRandom.Tail + 61]; // X3
unsigned Salt = 1 // может быть любое ненулевое значение
+ LyRandom.Pool[LyRandom.Tail + 11] <<< 5 // циклические сдвиги
+ LyRandom.Pool[LyRandom.Tail + 23] <<< 7
+ LyRandom.Pool[LyRandom.Tail + 37] <<< 1; Value += Salt; Value += Value < Salt; // циклическое сложение с переносом
LyRandom.Pool[++LyRandom.Tail] = Value;
return Value;
}
void LyRandomInit(unsigned Seed)
LyRandom.Tail = LyRandom.Head = 0;
LyRandomPushSalt(Seed);
for(unsigned i = 0; i < 4096; i++)
LyRandomGet();
}
Генератор показал отличные характеристики, и после всестороннего изучения я думаю предложить его для Linux на замену используемого сейчас.
Важное замечание по поводу криптостойкости: Без «подсаливания» генератора непредсказуемыми (как минимум частично непредсказуемыми) значениями, будут генерироваться лишь псевдослучайные числа. В этом случае криптостойкость этого генератора немного выше чем «классических генераторов» основанных на регистрах сдвига и их комбинациях. Насколько генератор подвержен алгебраической атаке в общем случае пока не известно, нужно исследовать, а мне как всегда некогда
И ещё одно важное «замечание»: Когда я разместил код генератор здесь, один знакомый предложил добавить туда «слона». «Слон» в данном случае - специально внесённая неточность/оплошность/ошибка, преднамеренность и заметность которой не вызывает у специалиста сомнений. Говорят, что «слоны» помогают студентам хоть немного вникать в текст при списывании. А мне позволяют не обращать внимание на критику по-поводу неправильного расположония «мух у слона на заднице» (извиняюсь за грубость). Я вовсе не хочу показаться «крутым математиком», как минимум у меня (увы) нет полноценного образования в этой области, но с другой стороны я просто не желаю выслушивать «критику» от персон не заметивших (или не утрудившихся заметить) даже этого «слона». И на всякий случай, отстутствие «& 63» или «% 64» в индексах при обращении к массиву LyRandom.Pool - это не «слон», это просто упрошение для удобочитаемости.
Удачи !" (с)
http://leo.yuriev.ru/random