» Генератор псевдослучайных чисел. Повышаем криптостойкость Assembler. Borland Delphi. . Блог программистов


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




20111 Авг

Генератор псевдослучайных чисел. Повышаем криптостойкость

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

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

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

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

Комментарии

  1. Ноябрь 20th, 2011 | 14:58

    Неплохо получилось 😉 .

  2. Январь 13th, 2012 | 21:55

    Неплохая статья. А вообще не новая, просто автор воплотил её на наглядном примере и для широкой аудитории. Инструкция rdtsc используется почти всех криптографических алгоритмах в целях достижения необходимого уровня энтропии.

  3. K10
    Январь 13th, 2012 | 22:41

    push edx
    rdtsc
    xor eax, edx
    pop edx

    зачем push edx / pop edx ?

  4. Январь 14th, 2012 | 18:15

    push edx / pop edx, тут конечно не нужен. Автор наверно хотел полностью сохранять контекст вызвавшего кода, наверно чисто ради эстестического удовлетворения

  5. rpy3uH
    Январь 14th, 2012 | 20:09

    да, push edx / pop edx исключительно для эстетики

  6. Март 29th, 2012 | 15:50

    Также по использованию генератора случайных чисел есть хорошая статья на сайте http://delphi-info.ru. Также у вас добавление комментариев на сайте плохо работает — открывает пустую страницу. Исправьте, пожалуйста

  7. Апрель 20th, 2013 | 15:56

    Спасибо автору за статью 😯

  8. Араз
    Ноябрь 30th, 2013 | 16:28

    Генератора случайных чисел по сути не существует, ибо любой генератор основан на алгоритме (будь он сложный, будь простой-всё это некий алгоритм подбора), если бы даже существовал настоящий генератор случайности, то он нарушал бы законы вселенной-детерминантность вселенной. Только сущность(сущность человека, обладая способностью свободы воли и осознанностью) способна обойти детерминантность и воссоздать полную непредсказуемость случайных чисел.

  9. Вячеслав
    Декабрь 25th, 2013 | 09:04

    «Только сущность(сущность человека, обладая способностью свободы воли и осознанностью) способна обойти детерминантность и воссоздать полную непредсказуемость случайных чисел.»

    В языках программирования многое можно назвать сущностями, хотя они не обладают свободой воли и осозноннастью, а зависят от среды исполнения и многих других факторов.
    В некотором смысле вы правы поскольку эти сущьности создает человек и они зависят от человека.
    Но объект класса в нашем конкретном случае будет сущьностью, которая сможет в некоторой степени воссоздать непредсказуемость. Но другой вопрос — будет ли полная непредсказуемость полезной, в случае когда в конечном итоге нам нужна будет предсказуемость(дешифратор), по которой можно будет воссоздать данные?

  10. Neyro
    Январь 3rd, 2014 | 16:41

    гуманитарий : 75% _ Из : 100 % _ СамЯ _ и На остаток % _ Могу Да И Доказать _ с Вероятностью : 75 % кАКИЕ ЦИФРЫ _ и чИСЛАМИ _ псевдослучайны _ САМ Не хочу ! ПОКА Заниматься расчётами ( МОЯ СПЕЦИАЛИЗАЦИЯ _ вероятности _ При … ) _ ! Но от _ » ДОСТОЙНОГО : Математика _ Не отказался _ Бы _ : НУЖНО Уметь _ ( ОПЕРИРОВАТЬ Огромными число ~ ЦИФРАМИ _ В Уме _ ) Уклоном _ На : Геометра _ От Себя _ ( когда просто Отдыхаю _ ((( АйКЬЮ : 98 ))) ) : алгоритм _ Неслучайных : ЧИСЕЛ _ Цифрами _ » ИНТЕРЕСУЕТ » _ что Возможно Выразить При таких _ РАСЧЁТАХ _ И В : парсеках .

  11. Февраль 4th, 2014 | 22:15

    “Только сущность(сущность человека, обладая способностью свободы воли и осознанностью) способна обойти детерминантность и воссоздать полную непредсказуемость случайных чисел.”

    Это не совсем так.

    http://ru.wikipedia.org/wiki/Аппаратный_генератор_случайных_чисел

  12. Февраль 4th, 2014 | 22:23

    >то он нарушал бы законы вселенной-детерминантность вселенной

    И вообще — с каких пор наша вселенная детерминирована? 🙂

  13. Октябрь 1st, 2014 | 07:27

    Все это относительно товарищи! 😉

  14. Октябрь 6th, 2014 | 15:22

    Да статья не новая, но описано подробно +

  15. tolltoll
    Октябрь 16th, 2014 | 10:33

    Подскажите как установить диапазон от 0 до 51 вкл.

  16. Имяя
    Февраль 25th, 2015 | 16:15

    Гуманитарии, ухаха.
    Конечно мир гуманитариев детерминирован.
    Монетку подбросил, мляяя а оно во как, гуманитарий держит удар, ну это мы чет не посчитали.
    Вселенная такая вот детерминированная существует мильён лет и тут херак человеки и ещё сто питсот видов которые постоянно эволюционируют, и сразуже же гуманитариям понятно, детерминированная, пути гасподни не исповидимы!
    Погода тоже у нас детерминированная, правда пока предсказать не могём, ну видно есть непознанные законы детерминированья.

    Тут учёный построил коллайдер, ловит всякие нетроны протоны, и всякий раз както оно поразному. Проводит стопитсот опытов видит есть неопределенность.