ГЕНЕРАТОР СЛУЧАЙНЫХ ЧИСЕЛ Российский патент 2008 года по МПК G06F7/58 

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

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

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

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

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

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

Известно много технических решений по реализации генераторов случайных чисел RU 2138074 С1, 20.09.1999, RU 2163027 C1, 10.02.2001, RU 2080651 C1, 27.05.1997, SU 1425785 A1, 23.09.1988, SU 1716510 A1, 29.02.1992, SU 1774334 A1, 07.11.1992, GB 2100485 A, 22.12.1982, EP 0498534 A1, 12.08.1992.

Из известных технических решений наиболее близким к заявляемому является генератор случайных чисел (SU 1571582, кл. G06F 7/58, 1990), содержащий оптически связанные оптический квантовый генератор и мозаичный фотоприемник, выход каждого из N элементов которого подключен к входу соответствующей схемы сравнения.

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

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

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

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

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

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

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

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

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

Без ограничения общности можно считать, что любой генератор случайных чисел построен по следующей схеме: к выходам источника случайных событий a₁,..., a_n применяется криптографическое преобразование, в результате чего получается последовательность случайных чисел b₁,..., b_m, причем ее длина не обязательно должна равняться длине исходной последовательности. На чертеже представлена обобщенная схема генератора случайных чисел.

Генератор случайных чисел содержит источник элементарных частиц слабой интенсивности 1, приемник частиц, содержащий детектор частиц 2 и накопитель числа событий 3, аналого-цифровой преобразователь 4, схему, выравнивающую статистические характеристики получаемого потока данных 5, а также генератор 6.

Пусть последовательности a₁,..., a_n и b₁,..., b_m являются реализациями случайных величин ξ и η, Н(ξ) и H(η) - оценки их энтропии, тогда используемый нормализатор должен обрабатывать исходный поток таким образом, чтобы H(η)≤Н(ξ).

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

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

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

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