Способ генерации случайного числа с использованием компьютера (варианты)

Авторы патента:

G06F7/58 - генераторы случайных или псевдослучайных чисел

Владельцы патента RU 2577201:

Открытое акционерное общество "Информационные технологии и коммуникационные системы" (RU)

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

Область техники, к которой относится изобретение

Предлагаемое изобретение относится к вычислительной технике и, в частности, к способам генерации случайных чисел с использованием компьютера.

Уровень техники

Для решения криптографических задач в компьютерной области требуется источник случайных чисел. В качестве источников случайных чисел могут выступать различного рода аппаратные устройства, программные средства и программно-аппаратные решения.

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

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

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

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

Программно-аппаратные комплексы обычно получают сначала инициализатор аппаратно, а потом уже на его основе программными методами генерируют случайную последовательность. Такое решение бывает дешевле чисто аппаратного, но также не всегда приемлемо для клиентских приложений именно из-за суммарной стоимости. Установка какой-либо дополнительной аппаратной части на мобильные компьютеры может вызывать проблемы. Даже для стационарных компьютеров это не всегда приемлемо, например, из-за возможного нарушения гарантийных условий. Источник случайности здесь - такой же, как и для аппаратных решений.

Ряд программно-аппаратных способов получения случайного числа известен [1, 2, 3].

Так, в качестве источника случайности предлагается использовать время нажатия клавиш, перемещений и щелчков мыши оператором, а также время отклика жестких дисков и принтеров [1]. Источники случайности, связанные с человеком (время нажатия клавиш, величины, связанные с перемещениями и щелчками мыши), могут давать вполне достаточную случайность и в этой связи широко используются. Величины, связанные со временем выполнения операций человеком-оператором и аппаратными устройствами, служат в качестве исходных случайных чисел и затем обрабатываются с использованием специальных программ, на выходе которых формируются случайные числа с требуемыми свойствами.

Однако для серверов, работающих без участия оператора-человека, эти и аналогичные источники недоступны. Обращаться к принтеру всякий раз, когда есть необходимость в случайном числе, тоже не всегда возможно, принтер просто может быть и недоступен в некоторых ситуациях и при некоторых конфигурациях вычислительных систем. Остается время обращения к жесткому диску. Физической основой здесь является то, что внутренний тактовый/опорный генератор жесткого диска независим от системных часов. Это, безусловно, хороший источник. Однако в современных компьютерах жесткого диска может не быть, а в качестве накопителя может использоваться твердотельный накопитель (Solid State Disk). Перечисленные проблемы приводят к недостаткам известного способа.

Мерой случайности является энтропия. Если в качестве источника случайных чисел не использованы специальные устройства, то оценить количество получаемой энтропии на практике, как правило, крайне сложно. Энтропию принято измерять в битах [1].

Если значения выбираются случайно и независимо от результата предыдущего выбора, то для расчета энтропии используется формула (энтропия Шеннона [1, 4, 5]):

где P(X=x) - вероятность появления значения x, а суммирование идет по всем возможным значениям.

Использование последней формулы для неравномерных распределений с большим числом различных значений практически невозможно, поэтому часто используется min-энтропия [4]:

причем минимум берется по всем возможным значениям.

Для любых распределений значение min-энтропии всегда меньше или равно энтропии Шеннона [4].

Известен программно-аппаратный способ получения случайного числа, в котором источниками энтропии являются микроархитектурное состояние процессора, время выполнения последовательности инструкций и неопределенность, вносимая аппаратными прерываниями [2]. Объединение энтропии из разных источников происходит на основе внутрисистемной таблицы, в которой отражается одновременная модификация двух потоков и в которую добавляются величины, связанные с накопленной энтропией, в виде стандартных по размеру целых чисел. Аппаратная часть этого генератора случайных чисел имеет очень сложные состояние и правила его изменения.

Этот способ принят за прототип.

Однако провести оценку величины энтропии в конечном результате и, в частности, доли, внесенной за счет обработки заведомо неслучайных, практически невозможно, что является недостатком известных способов.

Раскрытие изобретения

Техническим результатом является обеспечение способа получения случайного числа с энтропией не меньше заданной величины.

Преимуществом предлагаемого способа является получение случайного числа в компьютере без применения дополнительных аппаратных средств.

Для этого предлагается способ в двух вариантах, позволяющий использовать аппаратные средства компьютера и последующую программную обработку.

Согласно первому варианту, предлагается способ генерации случайных чисел с использованием компьютера, включающего:

• таймер для формирования значений текущего времени, не связанный с генератором тактовой частоты компьютера;

• прикладное программное обеспечение, выполненное с возможностью:

получать из таймера значения текущего времени;

выполнять обработку данных по заранее заданному алгоритму;

выполнять операцию хэширования;

способ, заключающийся в том, что

• задают значение энтропии;

• определяют для данного компьютера количество M элементов последовательности D, которое необходимо обработать для получения значения энтропии не меньше заданного;

• формируют последовательность D, выполняя следующие действия:

вычисляют значение переменной K

K=0;

получают из таймера значение текущего времени ТС;

(А) присваивают значение текущего времени переменной TP

TP=ТС;

задают начальное значение переменной N

N=0;

(В) получают из таймера значение текущего времени ТС;

если ТС=TP, то

вычисляют

N=N+1;

переходят к выполнению этапа В;

запоминают в качестве значения очередного элемента последовательности D значение N

D(K)=N;

вычисляют

K=K+1;

если K<М, то переходят к выполнению этапа А;

• получают случайное число в результате обработки элементов последовательности D.

Переменная K в описанном способе имеет смысл количества накопленных чисел в последовательности D.

Таким образом, в способе по п. 1 в качестве случайной величины используется количество максимально простых программных циклов за время изменения показаний часов реального времени.

Физической основой случайности является принципиальная нестабильность таймера и генератора тактовой частоты, поскольку число программных циклов зависит от числа тактов процессора.

Число программных циклов неизбежно зависит также и от множества других факторах, таких как количество прерываний процессора, обрабатывающего данные других прикладных и системных программ, состояние микропроцессора и т.п. Однако эти факторы можно рассматривать лишь как меру незнания того, что в действительности происходит в компьютере. Для того чтобы свести влияние этих факторов к минимуму, был выбран максимально простой программный цикл. В этом состоит принципиальное отличие от прототипа, где аналогичной ситуации был выбран чрезвычайно сложный вид цикла, включающий создание таблиц и ранее полученных данных и их модификацию, которая происходит в соответствии с новыми данными. Подход прототипа, с одной стороны, позволяет получать значительно более вариативные данные в единицу времени, но физическое обоснование этой вариативности получить весьма затруднительно. В прототипе получают последовательность чисел, сформированную по очень сложному закону, который зависит от буквально всего того, что происходит в компьютере в данный момент, однако вопрос, насколько это воспроизводимо, остается открытым для прототипа. Для предложенного же способа именно в силу простоты цикла вполне можно получить оценку количества энтропии именно из физических соображений.

Важной операцией предложенного способа является определение для данного компьютера количества М элементов последовательности D, которое необходимо обработать для получения значения энтропии не меньше заданного.

Известно, что программно доступный таймер реального времени в современных компьютерах обеспечивает получение значений текущего времени с точностью, как правило, до единиц миллисекунд. При использовании стандартных программ для считывания значений текущего времени из таймера (в составе универсальных языков программирования) реализуется обычно еще меньшая точность. Так, например, в описании стандартной функции GetTickCount() в составе пакета, обеспечивающего работу с универсальным языком программирования С++, компилятор Microsoft Visual Studio 2008, указывается, что обеспечивается точность отсчета времени 10-16 мс [6].

Тактовая частота современных компьютеров составляет единицы гигагерц. Если для определенности принять для тактовой частоты значение 1 ГГц, а для точности отсчета времени значение 10 мс, то за время между ближайшими считываниями значений текущего времени из таймера с помощью стандартной программы пройдет около 10 миллионов тактов.

Число программных циклов, обеспечивающих реализацию способа по первому варианту, будет несколько меньше. Так, например, при использовании компьютера типа PIRIT Codex 2315 i7-870 с тактовой частотой 2,93 ГГц, это число составляет 2-5 млн.

Генераторы частоты всегда нестабильны. Нестабильностью генератора часов реального времени в данном случае можно, очевидно, пренебречь из-за значительно более низкой характерной частоты по сравнению с тактовой частотой компьютера.

В тактовых генераторах компьютеров обычно используют кварцевые резонаторы и умножение частоты.

Так, например, характерное значение стабильности частоты широко распространенной специализированной интегральной микросхемы (чипсета) типа BU2192F составляет 10^-4, типичное значение дрожания (jitter) периода колебаний - около 3·10^-3 (80 пс для частоты 33 МГц), а максимальное - 8·10^-3 (250 пс для частоты 33 МГц) [7]. Реальная тактовая частота получается умножением исходной. Стабильность при этом, очевидно, не возрастает.

Поэтому минимальное оценочное значение нестабильности числа циклов составляет порядка 10^-4, что соответствует случайному изменению числа циклов на несколько сотен за 10 мс, т.е. от измерения к измерению.

Нестабильность в несколько сотен циклов соответствует 6-9 битам энтропии на измерение.

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

Формулу для min-энтропии можно переписать в эквивалентном виде, используя тот факт, что функция

является монотонно убывающей и, следовательно,

для любого множества {z_i}, где z_i>0, а минимум и максимум берутся по всем возможным z_i.

Для min-энтропии исходное выражение (1) можно записать в виде

Тогда, с учетом (2), min-энтропию можно вычислить по формуле

где максимум берется по всем возможным значениям х.

Таким образом, для вычисления min-энтропии, а значит, оценки снизу энтропии, достаточно знать только максимальную вероятность любого наперед заданного определенного события.

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

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

Сформулируем следующую гипотезу: вероятность появления любой выбранной группы из трех подряд идущих значений меньше 2^-20. В качестве критерия проверки этой гипотезы будем рассматривать отсутствие повторяющихся таких групп в серии измерений.

В приложении 1 показано, что при числе измерений 13 млн вероятность ложно принять гипотезу по такому критерию составляет не более 0,0825. Доказательство приведено в предположении независимости группы из идущих подряд трех измерений от других групп из идущих подряд трех измерений.

Для проверки этой оценки была создана прикладная программа в виде утилиты командной строки на языке С++ (программа компилировалась с помощью программы Microsoft Visual Studio 2008), которая принимала в качестве параметров число измерений и имя файла, в который следовало записать результат, и на выходе записывала в файл полученные значения измерений.

Для экспериментальной проверки гипотезы было проведено 5 серий измерений по 13 млн в каждой серии.

Анализ полученных данных показал, что если взять группу из любых подряд идущих трех значений, то такая группа ни в одной полученной последовательности не встречается.

Критерию удовлетворяют все 5 проведенных серий измерений, что уменьшает вероятность ложного принятия гипотезы до 0,0825⁵=0,000004.

Таким образом, гипотезу можно считать практически подтвержденной.

Максимальное значение вероятности 2^-20 для группы из идущих подряд трех чисел (значений) соответствует по формуле (3) min-энтропии в 20 бит для такой группы из идущих подряд трех чисел (значений). Это соответствует минимум 20/3=6,6 битам энтропии на одно число (значение).

Полученное на основе измерений значение min-энтропии является лишь ее оценкой, и важно то, что эта оценка не противоречит оценке на основе физических соображений, которая приведена выше, и дает 6-9 бит энтропии на отсчет.

Предположим, что задано желаемое значение энтропии 200 бит. Тогда необходимо для этого провести не менее 200/6,6≈31 отсчетов, т.е. получить не менее 31 числа (значения).

Выполнив указанные действия предлагаемого способа, можно получить требуемую последовательность из 31-го числа. Если каждое число занимает 32 бита, то всего последовательность занимает 32·31=992 бита и содержит минимум 200 бит энтропии.

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

Наиболее вероятно, полученная последовательность не обладает другими, обычно нужными свойствами (например, независимостью распределения соседних бит, определенным видом распределения и т.д.). Для достижения этих свойств можно обработать эту последовательность каким-либо известным способом, в частности использовать криптографическую хэш-функцию [4].

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

Пусть вероятность коллизии (два значения имеют одинаковое значения хэш-преобразования) для хэш-преобразования равна 2^-N, где N - величина порядка длины хэш-преобразования в битах криптографического качества (например, длина результата составляет 256 бита для хэш функции по ГОСТ Р 34.11-94 [8]), тогда при количестве исходной энтропии на несколько бит меньшего N значимого число коллизий не получается, и, тем самым, сохраняется количество различных значений, а значит, и величина энтропии.

Из приведенных оценок следует, что, используя хэш-преобразование с вероятностью коллизии 2^-N, не следует пытаться получить количество бит энтропии больше чем N минус некоторое небольшое число, даже если эта энтропия и присутствует в исходной последовательности. Несложные математические подсчеты показывают, что если N равно 210, то вполне возможно получить не менее 200 бит энтропии после преобразования последовательности, заведомо содержащей эту энтропию. Для исходной энтропии в 200 бит коллизии уменьшат энтропию примерно на 2^-10 (2^-210/2^-200) ее величины, то есть примерно на одну тысячную бита. Для компенсации этой потери длину исходной последовательности достаточно увеличить, например, на один элемент и собирать 32 отсчета.

Очевидно, что для большей исходной энтропии потери будут большими, но результат будет содержать энтропии не меньше чем, для случая исходной энтропии в 200 бит, т.е. те же самые 200 бит.

На практике можно также проверять, что в ходе реализации способа получено отсчетов не меньше, чем минимальное необходимое количество.

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

Согласно второму варианту способа, предлагается способ генерации случайных чисел с использованием компьютера, включающего:

• прикладное программное обеспечение, выполненное с возможностью:

получать из таймера значения текущего времени;

получать количество тактов, прошедших с момента последнего сброса процессора;

выполнять обработку данных по заранее заданному алгоритму;

выполнять операцию хэширования;

способ, заключающийся в том, что

• задают значение энтропии;

• определяют для данного компьютера количество М элементов последовательности D, которое необходимо обработать для получения значения энтропии не меньше заданного;

• вычисляют значение переменных

K=0,

N=0;

• формируют последовательность D, выполняя следующие действия:

получают из таймера значение текущего времени ТС;

(F) присваивают значение текущего времени переменной TP

TP=ТС;

(G) получают из таймера значение текущего времени ТС;

если ТС=TP, то переходят к выполнению этапа G;

получают количество тактов N, прошедших с момента последнего сброса процессора;

запоминают в качестве значения очередного элемента последовательности D значение числа тактов N, прошедших с момента последнего сброса процессора

D(K)=N;

вычисляют

K=K+1;

если K<М, то переходят к выполнению этапа F;

• получают случайное число в результате обработки элементов последовательности D(M).

Переменная K в описанном способе имеет смысл количества накопленных чисел в последовательности D.

Во втором варианте способа получают число тактов для каждого последовательного изменения показаний часов реального времени. Физическая основа здесь та же самая, влияние на вариативность результатов других факторов ослаблено даже больше. Следует отметить, что такой вариант способа можно реализовать лишь в компьютерах с процессорами, в которых конструктивно предусмотрена возможность получать количество тактов, прошедших с момента последнего сброса процессора. Такая возможность имеется в ряде современных моделей процессоров, например в процессорах Pentium компании Intel (США), где такую возможность обеспечивает использование инструкции RTDSC [9].

Для обработки элементов полученной последовательности во втором варианте способа также может применяться операция хеширования, как и для описанного выше первого варианта способа.

Осуществление изобретения

Для осуществления предложенного способа по п. 1 вначале выбирается компьютер, имеющий таймер для формирования значений текущего времени, не связанный с генератором тактовой частоты компьютера.

Компьютер также должен содержать прикладное программное обеспечение, выполненное с возможностью:

получать из таймера значения текущего времени;

выполнять обработку данных согласно указанным в способе действиям;

выполнять операцию хэширования.

В качестве такого компьютера может использоваться персональный компьютер PIRIT Codex 2315 i7-870 компании ПИРИТ (http://www.pirit.ru) с тактовой частотой 2,93 ГГц, с установленной операционной системой Microsoft Windows 7, 64-битная версия (Version 6.1.7601).

Для получения значений таймера реального времени использовалась стандартная функция GetTickCount() компилятора языка С++ в прикладном пакете Microsoft Visual Studio [6].

В качестве прикладного программного обеспечения, обеспечивающего выполнение операции хэширования криптографического качества, может быть использован бесплатный продукт ОАО "ИнфоТеКС" ViPNet CSP [10].

Прикладные программы, обеспечивающие выполнение обработки данных по алгоритму, реализующему действия предложенного способа, должны быть сформированы заранее. Это способен выполнить специалист по программированию (программист) на основе знания действий предложенного способа.

Перед началом реализации способа

• задают значение энтропии;

• определяют для данного компьютера количество М элементов последовательности D, которое необходимо обработать для получения значения энтропии не меньше заданного.

Затем эти значения вводят в прикладную программу, например, посредством клавиатуры. В качестве конкретных значений можно принять значения из описанного выше примера оценки.

После того, как компьютер с прикладным программным обеспечением подготовлен, запускается прикладная программа.

В результате работы прикладной программы формируется последовательность, которая используется как исходные данные в программе, вычисляющей хэш-преобразование по ГОСТ Р 34.11-94 [8].

Получившееся значение используется как инициализатор программного генератора случайных чисел криптографического качества, на выходе которого формируется случайное число с заданным значением энтропии.

Для осуществления предложенного способа, согласно второму предложенному варианту, вполне подойдет компьютер с характеристиками, указанными выше для первого предложенного варианта, для доступа к счетчику тактов используется команда RTDSC процессора.

Затем выполняются действия, аналогичные указанным выше для первого предложенного варианта.

Приложение 1

Гипотеза: вероятность появления каждого элемента меньше 2^-20.

Критерий: никакой элемент не появляется дважды в серии из m измерений.

Покажем, что в серии независимых измерений длиной m=4333333 вероятность ложно принять гипотезу при выполнении критерия не превышает 0,0825.

Примечание. Здесь рассматривается последовательность длиной 4333333 элементов, а не 13 млн элементов, поскольку в качестве элемента принимается группа из трех последовательных отсчетов.

Предположим, что существует такой элемент , что вероятность его появления . Введем следующие обозначения:

Пусть

q - вероятность не встретить событие в одном испытании;

Р₀ - вероятность того, что не встретится ни разу в последовательности m независимых испытаний;

Р₁ - вероятность того, что встретится ровно один раз в последовательности m независимых испытаний;

Р₂ - вероятность того, что 2 и более раз в последовательности m независимых испытаний;

Q₂ - вероятность того, что не встретится 2 и более раз в последовательности m независимых испытаний. По постановке задачи, Q₂ является вероятностью выполнения критерия.

Из теории вероятностей [11] известно:

значит

Вероятность не встретить в последовательности из m независимых испытаний:

Вероятность встретить ровно один раз в последовательности из m независимых испытаний равна:

Соответственно:

Р₀+Р₁+Р₂=1,

значит

Можно также записать:

Р₂+Q₂=1,

значит

Подставляя в (9) формулы (6)-(8), получаем

Учитывая (4) и (5), получаем из (10):

Оценим величину .

Известно [12], что

Для произвольной константы b>0 можно сделать замену переменой $y = \frac{x}{b}$ . Тогда

Таким образом

Подставляя полученное значение и значение с из (4) в формулу (11), получаем

С ростом вероятности появления υ_a вероятность не встретить повторение этого элемента в последовательности только падает.

Это означает, что при выполнении критерия вероятность ложного принятия гипотезы не превышает 0,0825.

Источники информации

1. Фергюсон Н., Шнайер Б. Практическая криптография. М.: Издательский дом "Вильямс", 2005, 424 с.

2. Seznec A., Sendrier N., "HAVEGE: a user-level software heuristic for generating empirically strong random numbers", ACM Transaction on Modeling and Computer Simulations (TOMACS), Volume 13, Issue 4, October 2003.

3. Stephan , CPU Time Jitter Based Non-Physical True Random Number Generator, статья по адресу http://www.chronox.de/jent/doc/CPU-Jitter-NPTRNG.html.

4. Salil P. Vadhan. Pseudorandomness, 2012 - обзор по адресу

http://people.seas.harvard.edu/~salil/pseudorandomness/pseudorandomness-Aug12.pdf

Randomness Extractors - раздел 6 обзора, стр. 118 по адресу

http://people.seas.harvard.edu/~salil/pseudorandomness/extractors.pdf.

5. Barak В., Shaltiel R., Wigderson A. Computational analogues of entropy. In Sanjeev Arora, Klaus Jansen, Jos′e D.P. Rolim, and Amit Sahai, editors, RANDOMAPPROX 2003, volume 2764 of LNCS, pages 200-215. Springer, 2003.

6. Описание функции GetTickCount - статья по адресу

http://msdn.microsoft.com/en-us/library/ms724408(VS.85).aspx.

7. Clock generator for personal computers - статья по адресу

http://cq-dx.ru/upload/pdf/BU/bu2192f.pdf.

8. ГОСТ P 34.11-94 Информационная технология. Криптографическая защита информации. Функция хэширования.

9. Using the RDTSC Instruction for Performance Monitoring - статья по адресу

http://www.ccsl.carleton.ca/~jamuir/rdtscpml.pdf.

10. Продукт ViPNet CSP - ОАО "ИнфоТеКС" - статья по адресу

http://www.infotecs.ru/products/catalog.php?SECTION_ID=&ELEMENT_ID-2096.

11. Кремер Н.Ш. Теория вероятностей и математическая статистика: Учебник для вузов. М.: ЮНИТИ-ДАНА, 2002, 543 с.

12. Ильин В.А., Позняк Э.Г. Основы математического анализа (в двух частях). М.: Физматлит, 2005.

1. Способ генерации случайных чисел с использованием компьютера, включающего:
• таймер для формирования значений текущего времени, не связанный с генератором тактовой частоты компьютера;
• прикладное программное обеспечение, выполненное с возможностью:
получать из таймера значения текущего времени;
выполнять обработку данных по заранее заданному алгоритму;
выполнять операцию хэширования;
способ, заключающийся в том, что
• задают значение энтропии;
• определяют для данного компьютера количество М элементов последовательности D, которое необходимо обработать для получения значения энтропии не меньше заданного;
• формируют последовательность D(M), выполняя следующие действия:
вычисляют значение переменной K
K=0;
получают из таймера значение текущего времени ТС;
(А) присваивают значение текущего времени переменной TP
TP=ТС;
задают начальное значение переменной N
N=0;
(В) получают из таймера значение текущего времени ТС;
если ТС=TP, то
вычисляют
N=N+1;
переходят к выполнению этапа В;
запоминают в качестве значения очередного элемента последовательности D значение N
D (K)=N;
вычисляют
K=K+1;
если K<М, то переходят к выполнению этапа А;
• получают случайное число в результате обработки элементов последовательности D.

2. Способ по п. 1, в котором обработка элементов последовательности включает выполнение операции хэширования.

3. Способ генерации случайных чисел с использованием компьютера, включающего:
• таймер для формирования значений текущего времени, не связанный с генератором тактовой частоты компьютера;
• прикладное программное обеспечение, выполненное с возможностью:
получать из таймера значения текущего времени;
получать количество тактов, прошедших с момента последнего сброса процессора;
выполнять обработку данных по заранее заданному алгоритму;
выполнять операцию хэширования;
способ, заключающийся в том, что
• задают значение энтропии;
• определяют для данного компьютера количество М элементов последовательности D, которое необходимо обработать для получения значения энтропии не меньше заданного;
• вычисляют значение переменных
K=0,
N=0;
• формируют последовательность D, выполняя следующие действия:
получают из таймера значение текущего времени ТС;
(F) присваивают значение текущего времени переменной TP
TP=ТС;
(G) получают из таймера значение текущего времени ТС;
если ТС=TP, то переходят к выполнению этапа G;
получают количество тактов N, прошедших с момента последнего сброса процессора;
запоминают в качестве значения очередного элемента последовательности D(K) значение числа тактов N, прошедших с момента последнего сброса процессора
D(K)=N;
вычисляют
K=K+1;
если K<М, то переходят к выполнению этапа F;
• получают случайное число в результате обработки элементов последовательности D.

4. Способ по п. 3, в котором обработка элементов последовательности включает выполнение операции хэширования.

Изобретение относится к вычислительной технике, в частности к генераторам псевдослучайных функций (ПСФ), и может быть использовано в цифровых вычислительных устройствах, а также в системах защиты информации.

Генератор псевдослучайных последовательностей // 2557764

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

Способ генерации параллельных потоков псевдослучайных чисел и устройства для его осуществления (2 варианта) // 2556430

Изобретение относится к вычислительной технике и может быть использовано для генерации потоков псевдослучайных чисел (ПСЧ). Техническим результатом является возможность генерации N начальных значений и отсутствие корреляций при их использовании между не менее N потоками ПСЧ.

Генератор случайных чисел // 2554537

Настоящее изобретение относится к генератору случайных чисел для предоставления случайного числа и/или комбинации случайных чисел и/или матрицы случайных чисел. Технический результат заключается в повышении достоверности данных, предоставляемых и отображаемых во время игры.

Генератор нелинейных псевдослучайных последовательностей // 2549524

Изобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных устройствах для формирования кодовых последовательностей. Технический результат заключается в расширении функциональных возможностей за счет расширения класса формируемых последовательностей путем добавления на h-разрядный выход устройства-прототипа модуля, содержащего h/3 нелинейных преобразователей, каждый из которых имеет три двоичных входа и двухбитовый вход, а также блока из h мультиплексоров с двумя входами данных каждый и с общим управляющим входом.

Генератор коррелированных случайных сигналов // 2546580

Изобретение относится к области вычислительной техники и может быть использовано для генерирования широкополосных случайных стационарных сигналов с заданными собственными и взаимными спектральными плотностями мощности.

Способ формирования коррелированных случайных сигналов // 2546579

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

Генератор случайной последовательности // 2542903

Изобретение относится к вычислительной технике и предназначено для генерации случайной последовательности значений из заданного множества значений с требуемыми характеристиками генерируемой последовательности.

Способ и устройство детектирования // 2506631

Предлагаемые способ и устройство относятся к области электронных детекторов, регистрирующих изменения электромагнитного фона окружающей среды. Основная сфера применения - определение эмоционального состояния сознания, развлечения и электронные игры с интерактивным управлением, технические средства для решений в области декоративных и дизайнерских работ, для обустройства интерьеров, устройств освещения и подсветки.

Способ нелинейного трехмерного многораундового преобразования данных dozen // 2503994

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

Способ генерации равномерно распределенных и независимых случайных чисел // 2583729

Изобретение относится к области вычислительной техники и может быть использовано для генерации случайных чисел. Техническим результатом является повышение точности. Способ генерации равномерно распределенных и независимых случайных чисел с нечетным модулем d и множителем z, взаимно простым с d, начинает с произвольно заданного целого числа n, взаимно простого с d, и рекуррентно порождает последовательность целых чисел {r0, r1, r2, …} при помощи отношений конгруэнтности r0≡n mod(d), 0<r0<d, rk≡zrk-1 mod(d), 0<rk<d, k=1, 2, 3, …, и дает на выходе случайные числа {vk:=rk-1/d| k=1, 2, …}, при этом множитель z выбран таким образом, что удовлетворяет условию, что генератор (d,z′) при z′≡zj mod(d) для целого j по меньшей мере в диапазоне 1≤j≤6 проходит спектральный тест второй степени в пределах оценки 1,25, а именно, для любого целого j в диапазоне 1≤j≤6 генератор (d, z′) при z′≡zj mod(d) удовлетворяет условию, что вектор f дуальной решетки, заданный для (d, z′) посредством линейной комбинации f:=m1f1+m2f2 базисных векторов {f1, f2} дуальной решетки, f1:=(d,0), f2:=(-z′,1), с целочисленными коэффициентами {m1,m2} и длиной ||f||:={(dm1-z′m2)2+(m2)2}1/2>0, имеет наименьший ненулевой вектор fmin с длиной amin (2)(z′):=||fmin||>0, удовлетворяя условию ρd (2)(z′):=21/2d1/2/{31/4amin (2)(z′)}<l,25. 6 ил.

Энтропийные пулы для виртуальных машин // 2589348

Изобретение относится к области генерации случайных чисел. Техническим результатом является повышение эффективности генерации случайных чисел для виртуальных машин. В главной операционной системе вычислительного устройства энтропийные данные собираются на основании, по меньшей мере частично, каждого из одного или более компонентов аппаратного обеспечения вычислительного устройства. Энтропийный пул обновляется на основании, по меньшей мере частично, собранных энтропийных данных, и данные из энтропийного пула предоставляются гостевой операционной системе, выполняемой как виртуальная машина вычислительного устройства. Гостевая операционная система сохраняет энтропийный пул гостевой операционной системы, основанный на данных из энтропийного пула, предоставленных главной операционной системой. Гостевая операционная система осуществляет доступ к энтропийному пулу гостевой операционной системы и использует энтропийный пул гостевой операционной системы в качестве основы для генерации значений, включая случайные числа. 5 н. и 21 з.п. ф-лы, 5 ил.

Способ проведения спектральных тестов мультипликативного конгруэнтного генератора случайных чисел // 2589405

Изобретение относится к вычислительной технике и может быть использовано в устройствах, моделирующих случайные процессы. Техническим результатом является получение на компьютерах однородных и независимых случайных чисел. Способ проведения спектральных тестов мультипликативного конгруэнтного генератора (d,z,n) или (d,z), содержащего нечетное целое число d в качестве модуля, а также целое число z, взаимно-простое с d, в качестве множителя, и целое число n, взаимно-простое с d, в качестве начального случайного числа, генерирующего последовательность целых чисел {nk:≡nzk-1 mod(d)| 1≤nk≤d, k=1,2,...} последовательным образом и выдающего на выходе последовательность случайных чисел за счет реализации арифметики {vk:=nk/d| 0≤vk≤1, k=1,2,...}, основан на оценке геометрической формы решетки GL(d,z), в которой занимают свои места L последовательных целых чисел {Qk:=(nk,nk+1,…,nk+L-1)| k=1,2,...}, выданных генератором (d,z,n), посредством вычисления наибольшего расстояния λL(d,z) между параллельными и соседними гиперплоскостями решетки GL(d,z) и оценки ρL′(d,z):=λL(d,z)/ML(d) генератора (d,z) на основе новых контрольных значений ML(d):=L-1/2(L+1)(L-1)/(2L)d(L-1)/L, L≥3, а также принятия решения о прохождении теста (d,z), если условия 1<ρL′(d,z)<RL, 3≤L≤6 выполняются для заданных уровней {RL>1| 3≤L≤6}. 3 ил.

Способ нелинейного трехмерного многораундового преобразования данных rdozen // 2591015

Изобретение относится к защите компьютерной информации. Технический результат - повышение криптостойкости и быстродействия нелинейного преобразования. Способ нелинейного трехмерного многораундового преобразования данных, в котором второй и третий раунды преобразования выполняются аналогично первому: при выполнении преобразований второго и третьего раунда осуществляется деление блока 1 данных S на четыре слоя 4х0, 4x1, 4х2, 4х3 (соответственно Lx0, Lx1, Lx2, Lx3) вдоль оси x; каждый слой Lxk, k=0, 1, 2, 3, представляется в виде квадратного массива байтов 4×4, после чего происходит двумерное стохастическое преобразование 5xk T_Layer каждого слоя Lxk и объединение слоев Lxk в преобразованный блок S; между первым и вторым раундами, а также между вторым и третьим раундами выполняется преобразование 6 перестановки байтов PermBytes; при выполнении преобразования 5xk T_Layer Lxk последовательно выполняются операции замены 9 байтов SubBytes, перемешивания 10 байтов состояния MixState и сложения 11 с раундовым подключом AddRoundSubKey; операция перемешивания 10 байтов состояния MixState выполняется следующим образом: - слой L разбивается на 16 байтов; - суть операции перемешивания байтов состояния - умножение строки байтов состояния на квадратную матрицу 16×16, при этом все операции умножения и сложения элементов строки и матрицы осуществляются в поле GF(28); перемешанные байты объединяются в преобразованный слой L. 5 ил.

Квантовый генератор случайных чисел // 2613027

Изобретение относится к квантовым генераторам случайных чисел и может быть использовано в криптографии. Техническим результатом является повышение качества, степени надежности и скорости генерации. Устройство содержит источник фотонов, однофотонный детектор, измеритель времени, задающий тактовый генератор, дискриминатор, процессор. 3 з.п. ф-лы, 3 ил.

Генератор стохастических ортогональных кодов // 2615322

Изобретение относится к области вычислительной техники и может быть использовано автономно или в комплексе для вычисления ортогонального базиса положительно определенной симметрической матрицы, который может быть использован для передачи информации в системе цифровой радиосвязи с множественным доступом с кодовым разделением каналов (CDMA). Техническим результатом является автоматизация процесса формирования исходных данных и обеспечение формирования систем стохастических ортогональных кодов. Устройство содержит генератор функций Попенко-Турко, позволяющий формировать ортогональные коды, в качестве которых используют ортогональный базис, определяемый собственными значениями и собственными векторами действительной положительно определенной симметрической матрицы, и блок стохастического формирования коэффициентов симметрической матрицы, содержащий микропроцессор, генератор псевдослучайных чисел, блок накопителя, блоки ОЗУ. 14 ил.

Способ потокового генерирования последовательности фигурных чисел, используемой при обучении решению уравнения ферма // 2619527

Изобретение относится к области вычислительной техники и может быть использовано в устройствах для генерирования числовых последовательностей. Техническим результатом является эффективное генерирование последовательности фигурных чисел заданного вида. Способ содержит этапы, на которых для первого операнда выбирают производящую функцию и вычисляют квадрат или куб первого операнда на последовательном умножителе с первым АЛУ, сохраняют промежуточный результат в регистре умножения. Одновременно при помощи второго АЛУ переводят первый операнд в дополнительный код до 2-х и суммируют с промежуточным результатом из регистра умножения. Повторяют действия для второго операнда. Одновременно посредством третьего АЛУ вычисляют частное на последовательном делителе. Записывают фигурное число от первого операнда в запоминающее устройство. Производят действия для второго операнда. Повторяют всю последовательность действий для оставшихся операндов. 2 ил.

Способ и устройство для генерирования истинно случайных чисел и игровая система // 2625048

Группа изобретений относится к области генерирования случайных чисел и может быть использовано в игровых системах. Техническим результатом является создание генератора истинно случайных чисел на основе квантово-оптического процесса. Устройство содержит: источник света, способный генерировать последовательность импульсов в виде одиночных фотонов в световом луче; по меньшей мере два детектора, каждый из которых предназначен для обнаружения одиночных фотонов в световом луче, посредством чего осуществляется предоставление сигналов детекторов; и средства управления, при этом каждый из детекторов для обнаружения одиночных фотонов содержит по меньшей мере одну квантовую точку; и при этом детекторы расположены в эквивалентном поперечном пространственном положении вероятности обнаружения одиночных фотонов в световом луче; и при этом средства управления конфигурированы для управления генерированием последовательности импульсов в виде одиночных фотонов и для регистрации сигналов детекторов для генерирования истинно случайных чисел, при этом источник света для генерирования последовательности импульсов в виде одиночных фотонов основан на структуре квантовых точек. 3 н. и 9 з.п. ф-лы, 5 ил.

Способ получения последовательности случайных двоичных чисел и устройство для его осуществления // 2627132

Изобретение относится к области и предназначено для получения последовательности случайных чисел с заданными статистическими характеристиками. Технический результат - повышение независимости вырабатываемой последовательности случайных чисел от параметров источника шума и получение последовательности случайных чисел с заданными статистическими характеристиками. В способе для получения последовательности случайных двоичных чисел используют источник случайных событий - полупроводниковый шумовой диод. Формируют аналоговый сигнал, характеризующий наступление указанных событий, производят обработку сформированного аналогового сигнала и преобразование его в цифровую форму. Задают интервал времени, в течение которого определяют число знакоперемен (0 и 1). В полученном числе выявляют младший бит и записывают его. Из последовательности указанных младших битов формируют выходную последовательность случайных двоичных чисел. 2 н. и 9 з.п. ф-лы, 1 ил.

Способ генерации случайных двоичных последовательностей с использованием компьютера и действий пользователя // 2628213

Изобретение относится к вычислительной технике. Технический результат заключается в повышении устойчивости генерации случайной двоичной последовательности заданной длины. В качестве источника случайности используют осмысленные целенаправленные действия пользователя, а именно - клики мышью либо клики пальцем в случае сенсорного экрана, по отношению к наблюдаемому внутри рабочей области экрана псевдослучайному процессу, который состоит в последовательной генерации N кругов диаметра d с временными интервалами в доли секунды, и каждый круг начинает прямолинейное движение в различных направлениях из центра рабочей области, отражаясь от границ рабочей области и других кругов, часто меняя направление движения и имитируя в целом хаотичный процесс движения кругов, и после появления в рабочей области последнего круга кликают в произвольной последовательности в площадь каждого из N движущихся кругов, при этом после успешного клика круг переходит в следующее состояние: становится невидимым для пользователя и впоследствии либо продолжает двигаться и соударяться в рабочей области, либо останавливается после h соударений с любыми кругами в рабочей области, h∈{0, 1, 2, 3}, причем вариант состояния невидимого круга определяется независимым от процесса рандомизатором. 2 з.п. ф-лы, 6 ил.