Результат интеллектуальной деятельности: СПОСОБ ГЕНЕРАЦИИ СЛУЧАЙНОГО ЧИСЛА С ИСПОЛЬЗОВАНИЕМ КОМПЬЮТЕРА (ВАРИАНТЫ)

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

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

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

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

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

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

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

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

Подставляя полученное значение и значение с из (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.