Блог программистов

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

   Для начала надо разобраться с общим принципом работы ГПСЧ. У любого ГПСЧ есть некоторое значение (переменная), которое текущее значение которой и является случайным значением, назовём эту переменную RandSeed, его также принято называть инициализатором ГПСЧ (по крайнем мере я его так называю, вы называйте, как хотите смысл не меняется). При вызове функции Randomize() происходит присваивание переменной RandSeed некоторого значения, которое извлекается от системного таймера или другого источника, значение которого трудно предсказать. В разных языках программирования всё по разному, в некоторых надо самому передать функции Randomize инициализирующее значение (например, функция srand() в С++). Но суть везде одинакова, переменной RandSeed присваивается некоторое начальное значение.
   При вызове функции Random происходят некоторые операции со значением RandSeed, операции могут быть любыми, всё зависит от реализации ГПСЧ, важно то, что вычисления всегда одни и те же, отсюда и предсказуемость ГПСЧ. Новое значение RandSeed будет являться результатом выполнения функции Random. В некоторых языках надо самому подгонять полученное значение в нужный диапазон в некоторых, функция Random сама подгонит результат в нужный диапазон. Но почти всегда это будет остаток от деления, полученного случайного значения на диапазон.
   Теперь ближе к делу, попробуем написать свой собственный ГПСЧ. Воспользуемся алгоритмом, который предлагает нам компания Intel, он очень прост.

int Random()
{
  RandSeed = (214013* RandSeed +2531011); 
 
  return (RandSeed >>16)&0x7FFF;
}

Эта функция возвращает случайное 16-битное значение. Но слишком теоретизировать не будем, сразу напишем функцию-ГПСЧ. Функцию-ГПСЧ будем писать на ассемблере, тестировать всё будем на Delphi.
   Алгоритм, предложенный Intel, на ассемблере будет выглядеть так:

@@random16:
        imul eax, [RandSeed], 214013
        add eax, 2531011
        mov [RandSeed], eax
        shr eax, 16
        ret

   Вышуказанная функция генерирует случайное 16-битное значение. Получение случайного 32-битного значения будет выглядеть так:

@@random32:
        call @@random16
        push eax
        call @@random16
        shl eax, 16
        or eax, [esp]
        add esp, 4
        ret

   Функция на встроенном ассемблере на Delphi будет выглядеть следующим образом.

	
function MyRandom():DWORD;
asm
        jmp @@AdvRandom

@@random32:
        call @@random16
        push eax
        call @@random16
        shl eax, 16
        or eax, [esp]
        add esp, 4
        ret

@@random16:
        imul eax, [RandSeed], 214013
        add eax, 2531011
        mov [RandSeed], eax
        shr eax, 16
        ret

@@AdvRandom:
        call @@random32
        ret
end;

   Если нам нужно случайное значение от 0 до 100, то достаточно просто разделить полученное значение разделить на 100, остаток от деления и будет необходимым случайным значением. Теперь необходимо протестировать всю эту красоту.

	
procedure TForm1.TestRandom(RandFunc: TRandFunc; InitVal:DWORD);
var
  i, j, v :integer;
  counts:array[0..255] of Integer;
  str:string;
  avg:double;
begin

  MyRandomize(InitVal);
  avg:=0;
  for i:=1 to 1000000 do
   avg:=avg+ (RandFunc() mod 100);
  avg:=avg/1000000;
  lblAVG_Val.Caption:='Среднее значение '+FloatToStr(avg);

  for i:=0 to 255 do
   counts:=0;

  MyRandomize(InitVal);
  for i:=1 to 100000 do
   begin
    v:=RandFunc() mod 256;
    inc(counts[v]);
    Canvas.Pixels[counts[v], v+ 50]:=clBlack;
   end;

  MyRandomize(InitVal);
  //ShowMessage(inttostr(InitVal));
  for i:=1 to 10000 do
   Canvas.Pixels[RandFunc() mod 200, 320+(RandFunc() mod 200)]:=clBlack;

  mmoVals.Clear;
  for i:=1 to 100 do
   begin
    MyRandomize(InitVal);
    str:=inttostr(RandFunc() mod 100);
    for j:=2 to 24 do RandFunc();
    str:=str+' '+ IntToStr(RandFunc() mod 100);
    for j:=26 to 99 do RandFunc();
    str:=str+' '+ IntToStr(RandFunc() mod 100);
    mmoVals.Lines.add(str);
   end;
end;

Вышеуказанная функция производит тестирование функции-ГПСЧ, которая передаётся ей через параметр RandFunc. Сначала происходит получение миллиона случайных значений, получение среднего и вывод в Label. Потом происходит вычисление частоты вхождения чисел от 0 до 255 после ста тысяч вызовов функции (ГПСЧ предварительно инициализируется). По полученным значениям формируется что-то вроде мини-гистограммы (перед тестом ГПСЧ предварительно инициализируется). Если функция-ГПСЧ нормальная, то на гистограмме не должно быть преобладающего диапазона. Потом происходит что-то вроде «закрашивания» квадрата размером 200х200 пикселей (перед тестом ГПСЧ предварительно инициализируется), при использовании нормальной функции-ГПСЧ в этом квадрате не должно быть больших незакрашенных участков. Последний тест, это тест на предсказуемость, происходит инциализация ГПСЧ, потом функция вызывается 100 раз и в memo выводится значения первого, двадцать пятого и сотого вызова функции-ГПСЧ. Тест на предсказуемость производится 100 раз.
   Теперь чтобы протестировать достаточно одной строчки
TestRandom(MyRandom, strtoint(edtInitVal.Text));

   Результаты теста для инициализатора равного 456, приведены на скриншоте.

   Первые три теста прошли удачно, функция даёт хороший разброс. Но вот последний тест на предсказуемость полностью провален. Первое, двадцать пятое и сотое значение всегда одно и тоже, меняем значение инциализатора, поток меняется, но значения, тем не менее, одни и те же. Что это значит? Это значит, что для каждого инициализатора можно сопоставить выходной поток, т.е. по большому счёту и функция не нужна достаточно держать базу данных, согласно которой можно будет сопоставить выходной поток по инициализирующему значению. Инициализирующее значение может принимать значения от 0 до 2^32-1, значит всевозможных выходных потоков может быть всего 2^32. В такой ситуации можно имея первые 10-12 значений функции сопоставить их инициализатору и полностью предугадать весь выходной поток. Такой порядок вещей неприемлем для алгоритмов шифрования, так как их результаты становятся предсказуемыми
   Как решить эту проблему? Главная проблема состоит в том, что функции Random производит всегда одни и те же действия. Решением проблемы будет некоторая непредсказуемая операция со значением RandSeed. Я предлагаю использовать команду RDTSC. Команда RDTSC получает количество тактов процессора после его включения или перезагрузки, результат выполнения команды RDTSC сохраняется в регистрах EDX:EAX. Чтобы снизить предсказуемость функцию-ГПСЧ, надо обновлять значение RandSeed перед каждым вычислением случайного значения, например вот так
RandSeed := RandSeed xor (RDTSC.EDX xor RDTSC.EAX);
   На ассемблере это будет выглядеть следующим образом

	
function MyAdvancedRandom():DWORD;
asm
…...
@@AdvRandom:
        push edx
        rdtsc
        xor eax, edx
        pop edx
        xor [RandSeed], eax
        call @@random32
        ret
end;

   Теперь необходимо протестировать эту функцию, результат теста на скриншоте:

   Теперь все тесты пройдены успешно. Разброс хороший, предсказуемость почти нулевая.
   С помощью инструкции RDTSC мы добились почти полной непредсказуемости ГПСЧ, тем не менее, возможны ситуации, когда значения RDTSC станут предсказуемыми. Например, в операционной системе реального времени, когда текущий поток ничем не прерывается, то при использовании в цикле с большим количеством итераций функции-ГПСЧ, её значения станут предсказуемыми, так как результат команды RDTSC станет предсказуемым (потому что счётчик тактов всегда будет меняться на одинаковое значение). Но Windows и Linux как известно это не системы реального времени, поэтому можно смело использовать предложенный мною ГПСЧ на этих системах. При использовании вышеуказанной функции-ГПСЧ на многопроцессорных системах, результаты выполнения функции становятся ещё более непредсказуемыми, так как на разных процессорах (ядрах) счётчик тактов независимый.

Скачать программу пример и исходники (Delphi)

Fast Random Number Generator on the Intel® Pentium® 4 Processor