Изобретение относится к вычислительной технике, а более конкретно, к устройствам формирования стартового значения для генераторов псевдослучайных чисел при отсутствии аппаратного источника случайных данных, и может использоваться в различных криптографических системах.
Для решения множества задач необходимо формирование случайных чисел. Так случайные числа используются в имитационном моделировании, в формировании паролей, криптографических ключей для различных систем криптографической защиты информации.
Известные генераторы псевдослучайных чисел (ГПСЧ) для формирования псевдослучайной последовательности обычно используют некоторые типы хаотических систем. Сигналы, полученные от этих систем, оцифровываются и представляются в двоичном виде. Полученная двоичная последовательность затем хэшируется для формирования более короткой двоичной последовательности, которая затем используется в качестве стартового значения для ГПСЧ. На основе полученного стартового значения упомянутый генератор формирует псевдослучайные числа, которые затем используются в криптографических системах.
Существующие в настоящее время генераторы псевдослучайных чисел всегда используют источники случайностей. В этом случае экспериментально оценивается энтропия, и последующие измерения проводятся в зависимости от значения оценки.
В частности, известно техническое решение, описанное в патенте США № 5732138 [1], в котором устройство для формирования нового стартового значения использует случайные данные, получаемые от различных хаотических систем. Помимо того, что это устройство имеет низкую производительность, его невозможно использовать в ситуациях, когда источники случайных данных имеют различные скорости генерации энтропии, поскольку устройство не осуществляет классификацию источников по их надежности и скорости. При этом понимается, что к надежным источникам относятся только те источники, которые не могут контролироваться злоумышленником, и данные от которых не могут быть воспроизведены вне системы.
Наиболее близким к заявляемому изобретению в части устройства является устройство формирования стартовых значений для генератора псевдослучайных чисел, описанное в патенте США №5778069 [2]. Это устройство также получает данные от различных видов источников, объединяет данные от различных источников, хэширует полученные данные и на основе полученных данных формирует стартовые значения для ГПСЧ.
Однако и это устройство невозможно использовать в ситуациях, когда указанные источники имеют различные скорости генерации энтропии, т.к. это устройство не осуществляет динамической оценки скоростей источников, что необходимо для определения энтропии. Кроме того, известное устройство [2] не осуществляет классификацию источников по их надежности.
Задача, на решение которой направлено заявляемое изобретение состоит в том, чтобы создать устройство для формирования стартовых значений, обеспечивающее динамическую оценку скоростей источников, классификацию источников на быстрые и медленные, надежные и ненадежные, а также формирующее стартовые значения с учетом скоростных характеристик источников и надежности этих источников.
Технический результат достигается за счет того, что архитектура устройства адаптирована под новый способ формирования стартового значения для генератора псевдослучайных чисел при отсутствии аппаратного источника случайных данных. При этом новый способ заключается в том, что для формирования стартового значения осуществляют следующие операции:
накапливают данные от различных внешних источников, представляющих собой случайные процессы, в блоке памяти;
анализируют полученные данные для определения типа источника: быстрые или медленные, надежные или ненадежные;
для каждого источника по данным, полученным от этого источника, вычисляют текущие оценки энтропии;
осуществляют для каждого источника накопление текущих оценок энтропии путем суммирования этих оценок с последующей записью их в блоке памяти, при этом каждую конкретную ячейку блока памяти используют для записи текущих оценок энтропии только от одного источника данных;
осуществляют сжатие данных, полученных от каждого источника, с применением хэш-функции, с последующей записью результата сжатия в другую ячейку блока памяти, при этом такую ячейку памяти используют для записи сжатых данных только от одного источника данных;
осуществляют смешивание сжатых данных с применением хэш-функции и записывают результат смешивания в другую ячейку блока памяти;
определяют минимальную оценку энтропии для каждого надежного источника на основе полученных текущих оценок энтропии;
осуществляют вычисление приведенной оценки энтропии путем деления минимальной оценки на два и сохраняют последовательность приведенных значений в последовательности ячеек в другой, например второй, области блока памяти;
осуществляют накопление приведенных оценок энтропии для каждого надежного источника путем суммирования этих оценок и записи полученных сумм приведенных оценок в соответствующие ячейки второй области блока памяти, при этом каждую ячейку блока памяти используют для записи суммы приведенной оценки энтропии только от одного источника данных;
для каждого надежного источника данных осуществляют запись сжатых данных в другую ячейку второй области памяти, при этом каждую ячейку блока памяти используют для записи сжатых данных только от одного источника данных;
для каждого надежного источника данных осуществляют запись смешанных данных в соответствующую ячейку второй области блока памяти;
для каждого надежного источника данных определяют набор приведенных оценок энтропии, сохраненных в последовательности ячеек второй области блока памяти:
осуществляют вычисление консервативной оценки энтропии путем деления на два ранее уже приведенные оценки энтропии, сохраненные в соответствующих ячейках второй области блока памяти, которая также сохраняется в соответствующей ячейке другой, например третьей, области блока памяти;
осуществляют накопление консервативных оценок энтропии для каждого надежного источника путем суммирования этих оценок и записи полученных сумм консервативных оценок в последовательности ячеек третьей области блока памяти, при этом каждую ячейку блока памяти используют для записи консервативной оценки энтропии только от одного источника данных;
для каждого надежного источника данных осуществляют запись сжатых данных в соответствующую ячейку третьей области блока памяти, при этом каждую ячейку памяти используют для записи сжатых данных только от одного источника данных;
для каждого надежного источника данных осуществляют запись смешанных данных в соответствующую ячейку третьей области блока памяти;
проверяют выполнение следующих условий:
а) суммы текущих оценок энтропии должны быть равны или превышать число 128 для, по меньшей мере, трех источников, и один из источников должен быть быстрым и надежным или медленным и надежным,
б) суммы приведенных оценок энтропии должны быть равны или превышать число 128 для каждого из источников, при этом все эти источники должны быть быстрыми и надежными или медленными и надежными,
в) суммы консервативных оценок энтропии должны быть равны или превышать число 128 для каждого из источников, при этом все эти источники должны быть быстрыми и надежными или медленными и надежными,
при соблюдении всех указанных условий формируют новое стартовое значение для генератора псевдослучайной последовательности путем дополнительного смешивания уже смешанных данных, сохраненных в соответствующих ячейках первой и второй областей блока памяти, и предыдущего стартового значения генератора псевдослучайной последовательности, при этом формирование осуществляют путем применения итеративного циклического хэширования объединенных данных, извлеченных из ячеек первой, второй областей блока памяти, а также предыдущего стартового значения.
В частном варианте в качестве внешних источников данных используют случайные процессы, происходящие либо в локальной сети типа Ethernet, либо в беспроводной локальной сети (WLAN), при этом данными этих случайных процессов являются значения уровней сигналов в сети WLAN, интервалы между входящими пакетами в сетях, интервалы между пакетами, выходящими из сетей, интервалы между прерываниями, количество прерываний.
В другом частном варианте смешанные данные, сохраненные в соответствующей ячейке третьей области блока памяти, используют при формировании нового стартового значения в момент включения внешнего устройства, входящего в состав, по меньшей мере, одной из сетей.
В другом частном варианте области блока памяти представляют собой сегменты непрерывного адресного пространства массива памяти с произвольным доступом.
Еще в одном частном варианте для определения энтропии регистрируют частоты появления случайного события в источнике данных в течение фиксированного интервала времени и на основе полученных частот осуществляют вычисление текущих оценок энтропии по следующей формуле:
где pi - вероятность, вычисленная на основе частоты появления случайного события в течение фиксированного интервал времени.
Еще в одном частном варианте каждый упомянутый источник относят к одному из следующих типов: быстрый и надежный (FR), медленный и надежный (SR), быстрый и ненадежный (FU), медленный и ненадежный (SU).
Основанное на вышеописанном новом способе устройство формирования стартового значения для генератора псевдослучайных чисел в случае отсутствия аппаратного источника случайных данных содержит средство для анализа источника данных и вычисления текущих оценок энтропии, средство сжатия данных, средство смешивания данных, средство суммирования оценок энтропии, средство накопления данных и формирования оценок энтропии, средство формирования нового стартового значения и средство выдачи стартового значения генератору псевдослучайной последовательности,
при этом средство для анализа источника и вычисления текущих оценок энтропии предназначено для получения данных от различных источников, представляющих собой различные случайные процессы, и определения типа источника на основе полученных данных, а также для вычисления текущих оценок энтропии для каждого источника, при этом источники делятся на типы, общее число которых задается всевозможными комбинациями следующих признаков: быстрый/медленный, надежный/ненадежный;
средство сжатия данных предназначено для сжатия данных, полученных от источников, и выдачи сжатых данных устройству смешивания данных, которое предназначено для смешивания сжатых данных каждого источника;
средство суммирования оценок энтропии предназначено для суммирования полученных текущих оценок энтропии для каждого источника;
средство накопления данных и формирования оценок энтропии содержит два средства вычисления оценок энтропии, два средства суммирования и память, разделенную на три области, каждая из которых состоит из множества ячеек;
первое средство вычисления оценок энтропии предназначено для вычисления приведенных оценок энтропии для каждого источника данных на основе текущих оценок энтропии данного источника, полученных от средства для анализа источников и вычислении текущих оценок энтропии;
первое средство суммирования предназначено для вычисления сумм приведенных оценок энтропии для каждого источника путем суммирования полученных приведенных оценок энтропии данного источника;
второе средство вычисления оценок энтропии предназначено для вычисления консервативных оценок энтропии для каждого надежного источника на основе выбранных промежуточных значений из числа приведенных оценок энтропии, полученных в первом средстве вычисления оценок энтропии;
второе средство суммирования предназначено для вычисления сумм консервативных оценок энтропии для каждого надежного источника путем суммирования консервативных оценок энтропии данного источника, вычисленных вторым средством вычисления оценок энтропии;
блок памяти предназначен для записи результатов сжатия и смешивания, полученных от средств смешивания и сжатия, и оценок энтропии, при этом в ячейки первой области блока памяти записывают результаты смешивания для всех источников, в ячейки второй и третьей областей блока памяти записывают результаты смешивания данных от надежных источников, кроме того, первую область блока памяти используют для записи текущих оценок энтропии, полученных в средстве анализа и вычисления текущих оценок, вторую область блока памяти используют для записи приведенных оценок энтропии, полученных в первом средстве вычисления оценок энтропии, третью область блока памяти используют для записи консервативных оценок энтропии, полученных во втором средстве вычисления оценок энтропии;
средство формирования нового стартового значения предназначено для осуществления проверки выполнения следующих условий:
а) сумма текущих оценок энтропии в первой области блока памяти должна быть равна или превышать число 128 для, по меньшей мере, трех источников, один из источников должен быть быстрым и надежным или медленным и надежным;
б) сумма приведенных оценок энтропии во второй области блока памяти должна быть равна или превышать число 128 для каждого из источников, все источники должны быть быстрыми и надежными или медленными и надежными;
в) сумма приведенных оценок энтропии в третьей области блока памяти должна быть равна или превышать число 128 для каждого из источников, все источники должны быть быстрыми и надежными или медленными и надежными,
при этом при соблюдении всех перечисленных условий указанное устройство формирования нового стартового значения формирует новое стартовое значение для генератора псевдослучайной последовательности путем дополнительного смешивания результатов смешивания, сохраненных в соответствующих ячейках первой и второй областей блока памяти, и предыдущего стартового значения генератора псевдослучайной последовательности, путем применения итеративного циклического хеширования полученных объединенных данных;
средство выдачи стартового значения предназначено для получения нового стартового значения от средства формирования нового стартового значения и передачи полученного нового стартового значения генератору псевдослучайной последовательности.
В частном варианте в качестве внешних источников данных используют случайные процессы, происходящие в локальной сети типа Ethernet, в беспроводной локальной сети (WLAN), при этом данными этих случайных процессов являются значения уровни сигналов в сети WLAN, интервалы между входящими пакетами в сетях, интервалы между пакетами, выходящими из сетей, интервалы между прерываниями, количество прерываний.
В другом частном варианте средство формирования нового стартового значения для формирования нового стартового значения использует смешанные сжатые данные, сохраненные в соответствующих ячейках третьей области блока памяти, в момент включения внешнего устройства, входящего в состав одной из локальных сетей.
Еще в одном частном варианте средство для анализа источника и вычисления текущих оценок энтропии содержит средство регистрации частоты случайного события, предназначенное для регистрации случайных событий источников в течение определенного интервала времени и средство вычисления текущих оценок энтропии, предназначенное для вычисления текущих оценок энтропии на основе частот по следующей формуле:
где pi - вероятность, вычисленная на основе частоты появления случайного события в течение определенного интервала времени.
В другом частном варианте средство анализа для анализа источника и вычисления текущих оценок энтропии вычисляет текущие оценки энтропии на основе частот случайных событий источников, регистрируемых внешним средство регистрации частоты случайного события, при этом вычисление осуществляется по следующей формуле:
где pi - вероятность, вычисленная на основе частоты появления случайного события в течение определенного интервала времени.
Еще в одном частном варианте приведенная оценка энтропии, вычисляемая первым средством вычисления оценок энтропии, равна половине минимума для определенной последовательности текущих оценок энтропии.
В другом частном варианте консервативная оценка энтропии, вычисляемая вторым средством вычисления оценок энтропии, равна половине минимума для определенной последовательности приведенных оценок энтропии.
Еще в одном частном варианте каждый источник относят к одному из следующих типов: быстрый и надежный (FR), медленный и надежный (SR), быстрый и ненадежный (FU), медленный и ненадежный (SU).
Заявленное изобретение иллюстрируется следующими чертежами: фиг.1, на которой представлен алгоритм, т.е. последовательность операций, заявляемого способа; фиг.2, на которой представлена структурная схема заявляемого устройства генерирования стартового значения.
Как показано на фиг.1, в соответствии с заявляемым способом данные 1 от различных источников данных подвергают анализу 2 для определения типа источников.
Источники делятся на следующие виды: быстрые и медленные, надежные и ненадежные. Здесь необходимо отметить, что каждый источник может быть либо быстрым и надежным (FR), либо медленным и надежным (SR), либо быстрым и ненадежным (FU), либо медленным и ненадежным (SU).
К ненадежным источникам относятся процессы, которые можно измерить или получить различными лицами, не имеющими прав доступа внутрь устройства, например хакерами. Так, например, эти лица могут измерить временные интервалы между входящими пакетами или выходящими пакетами.
К надежным источникам относятся источники, формирующие случайные данные, которые не могут быть воспроизведены вне системы. Так, к числу надежных источников относятся случайные процессы, происходящие, например, в принтере.
После завершения анализа 2 на этапе 3 вычисляют текущие оценки энтропии для каждого источника данных на основе частот случайных событий упомянутых источников и заполняют ячейки первой области блока памяти накопленными оценками.
Здесь необходимо отметить, что области блока памяти представляют собой сегменты непрерывного адресного пространства массива памяти с произвольным доступом. Каждую ячейку первой области блока памяти используют для записи упомянутых оценок энтропии только от одного источника.
Кроме того, необходимо учесть, что данные, сохраненные в первой области блока памяти, в дальнейшем используют для обновления стартового значения (затравки) генератора псевдослучайной последовательности чисел (ГПСЧ) с целью снижения риска компрометации, а также в момент включения внешнего устройства, входящего в состав, по меньшей мере, одной из сетей. Так, в качестве такого устройства может выступать, например, принтер или любое другое средство.
Следует отметить, что текущие оценки энтропии для каждого источника данных вычисляют на основе частот случайных событий в источниках.
Текущие оценки энтропии для каждого источника вычисляют по формуле Шеннона:
где рi - вероятность, вычисленная на основе частоты появления случайного события в течение определенного интервал времени.
Важно учитывать, что используемые источники отвечают следующим требованиям 1) являются квазистационарными, т.е. распределение вероятностей случайной переменной остается неизменным в течение длительного промежутка времени или очень медленно изменяется; 2) являются источниками без памяти, т.е. текущее значение случайной переменной не зависит от того, какие значения эта случайная переменная принимала в прошлом; 3) статистически независимы.
На этапе 4 осуществляют выполнение следующих операций:
1. Сжатие данных, полученных от упомянутых источников, с последующей записью.
2. Смешивание полученных сжатых данных, с последующей записью полученных смешанных данных в соответствующую ячейку блока памяти.
Сжатие данных осуществляют с использованием хэш-функции.
Для этой цели применяют хэш-функцию SHA-256. Описание алгоритма хэширования, - вычисления значения хэш-функция для заданного аргумента, - приводится в Федеральном стандарте США FIPS PUB 180-2 [3]. Однако использование SHA-256 не является обязательным. Можно воспользоваться, например, функцией по ГОСТ Р 34.11-94 [4] или аналогичной хэш-функцией.
Для SHA-256 в качестве аргумента выбирают произвольную двоичную последовательность, преимущественно, длиной менее 264 двоичных разрядов. Вычисленное значение представляет собой двоичную последовательность длиной 256 двоичных разрядов. Основу алгоритма хэширования составляет функция сжатия.
Входную двоичную последовательность данных от каждого источника данных разбивают на блоки по 512 двоичных разрядов. Затем функцию сжатия последовательно применяют к каждому из блоков. Следовательно, если длина входной последовательности не превышает 512 двоичных разрядов, то хэширование при помощи SHA-256 сводится к однократному применению функции сжатия. При этом вычислительная трудоемкость хэширования минимальна.
Полученные сжатые значения для каждого источника данных сохраняют в соответствующую ячейку первой области блока памяти, при этом каждую ячейку памяти используют для записи данных только одного источника.
Смешивание всех сжатых данных для каждого источника осуществляют при наличии следующих условий:
(1) приращение сумм оценок энтропии должно быть не менее 32-х;
(2) накопленные в соответствующих ячейках первой области блока памяти данные должны содержать не менее 512-и двоичных разрядов.
При выполнении этих условий смешивание сжатых данных осуществляют следующим образом.
Формируют входную двоичную последовательность данных.
Для этого выполняют конкатенацию (объединение) сжатых данных всех источников данных и предыдущего результата смешивания;
после чего полученную двоичную последовательность длиной 256(n+1) двоичных разрядов, где n - число задействованных источников случайности, разбивают на отдельные блоки по 256 двоичных разрядов.
Далее осуществляют циклическое хэширование при помощи функции SHA-256. Например, для первых трех блоков циклическое хэширование заключается в следующем. Вычисляют значение хэш-функции для конкатенации первого и второго блоков. Результатом хэширования замещают данные первого блока. Вычисляют значение хэш-функции для конкатенации второго и третьего блоков. Результатом хэширования замещают данные второго блока. И так далее, для всех блоков.
На последнем n+1-ом шаге, значение хэш-функции вычисляют для конкатенации (n+1)-го и первого блоков (используют значение первого блока до запуска циклического хэширования), причем результатом хэширования замещают данные исходного (n+1)-го блока. Так выглядит одна итерация циклического хэширования.
Полноценное смешивание обеспечивают за счет многократного применения процедуры циклического хэширования к последовательности блоков, полное обновление которой происходит по завершении очередной итерации. Суммарное число итераций равно n. В итоге последовательность из (n+1)-го блока сжимается до 256 двоичных разрядов однократным применением функции SHA-256.
Полученные смешанные данные сохраняют в соответствующих ячейках первой области блока памяти.
Описанные выше процедуры смешивания и сжатия обеспечивают:
1) приведение отсчетов, полученных от различных источников, к единому унифицированному размеру;
2) смешивание отсчетов как от одного и того же, так и от различных источников случайности. Применение хэш-функции SHA-256 позволяет достичь обеих целей одновременно.
Смешивание при помощи вычислительно-трудоемкой процедуры циклического хэширования выполняют только тогда, когда накоплено достаточное количество энтропии, а именно по условию приращения счетчика энтропии для каждого источника должно быть не менее 32. При смешивании задействованы отсчеты, полученные от различных источников случайности.
Будем исходить из предположения, что в случае применения SHA-256 изменение значения одного двоичного разряда во входной последовательности приводит к изменению значений значительного количества двоичных разрядов результата хэширования (до 256). Тогда в результате двух итераций циклического хэширования изменения произойдут в 512-и двоичных разрядах. Таким образом, после n итераций значения всех выходных разрядов будут зависеть от каждого из значений разрядов входной последовательности.
Известные свойства криптографических хэш-функций гарантируют, что в ходе обработки не произойдет потери энтропии. Таким образом, если предположить, что учтены все возможные источники случайности, то предложенное решение обеспечивает максимальную скорость накапливания энтропийных разрядов при минимальном объеме хранимых данных.
После выполнения этапа 4 осуществляют заполнение второй области блока памяти, т.е. этап 5.
Здесь необходимо отметить, что данные, сохраненные во второй области блока памяти, предназначены для автоматического обновления стартового значения ГПСЧ. Необходимо также отметить, что вторая область блока памяти содержит данные, полученные в результате пессимистического подхода к оценке энтропии источников (оценка умышленно занижается). Такой подход позволяет гарантировать высокий уровень криптостойкости. Например, если данные в первой области блока памяти получены в результате необоснованно завышенных оценок энтропии, то автоматическое обновление с использованием данных второй области блока памяти позволяет компенсировать этот недостаток следующим образом.
Для каждого надежного источника (как быстрого, так и медленного) на основе текущих оценок энтропии этих источников, полученных упомянутым выше способом, вычисляют минимальные оценки энтропии.
Для этого фиксируют серию, например, из восьми промежуточных оценок, вычисленных описанным выше способом по формуле Шеннона. Затем определяют минимальную оценку в серии и осуществляют вычисление приведенной минимальной оценки энтропии. Эта приведенная минимальная оценка равна половине минимальной оценки. Обозначим серию промежуточных оценок fi-7, fi-6,..., fi-1, fi, где i - номер серии. Тогда минимальная оценка текущего значения энтропии заданного источника:
si=min(fi-7, fi-6,..., fi-1, fi)·0,5.
Множитель 0,5 введен для компенсации эффекта взаимного влияния различных источников. Например, входной пакет инициирует прерывания, а также вызывает появление выходного пакета по истечении определенного интервала времени. В ряде случаев такое событие можно предсказать с высокой вероятностью.
Выбор минимальной промежуточной оценки связан с возможным нестационарным поведением источника в случае, если наблюдения производились в течение ограниченного интервала времени, а также с целью снижения риска неадекватной оценки энтропии в результате целенаправленной атаки злоумышленника.
Полученные минимальные оценки энтропии каждого источника записывают в последовательности ячеек второй области блока памяти.
На следующем этапе 6 осуществляют накопление полученных приведенных оценок путем суммирования этих оценок с последующей записью результатов накопления в соответствующие ячейки второй области блока памяти, при этом в каждую ячейку записывают суммы оценок только от одного источника.
Затем на этапе 7 осуществляют запись смешанных сжатых данных, полученных ранее упомянутым способом, в соответствующие ячейки второй области блока памяти. Здесь необходимо отметить, что в эти ячейки записывают смешанные данные только от надежных источников. Запись данных в ячейки второй области блока памяти осуществляют так же, как и запись в ячейки первой области блока памяти, а именно в каждую ячейку второй области блока памяти записывают данные только от одного надежного источника.
На этапе 8 осуществляют заполнение третьей области блока памяти.
Здесь необходимо отметить, что данные третьей области блока памяти используют исключительно для загрузки стартового значения ГПСЧ в момент включения внешнего устройства, входящего в состав упомянутых сетей, например принтер. Данные третьей области блока памяти также формируют на основе пессимистических оценок энтропии надежных источников.
Для каждого надежного источника данных определяют набор приведенных оценок энтропии, сохраненных в последовательности ячеек второй области блока памяти.
На основе полученного набора оценок устройство формирования осуществляют вычисление консервативной оценки энтропии. Это вычисление аналогично ранее упомянутому вычислению приведенной оценки энтропии, т.е. осуществляется деление приведенных оценок энтропии на два.
Так, например, обозначим серию из четырех минимальных оценок энтропии для заданного источника как si-3, si-2, si-1, si, где i - номер серии. Тогда вторая минимальная оценка энтропии:
рi=min(si-3, si-2, si-1, si)·0,5.
Предполагается, что в момент включения третья область памяти гарантированно заполнена, поскольку временной интервал между двумя включениями печатающего устройства (включение-работа-выключение-включение) имеет необходимую продолжительность, достаточную для его заполнения.
Предполагается также, что выборка состоит из набора отсчетов, где под отсчетом понимают двоичную последовательность некоторой длины.
Полученные вычисленные вторые минимальные значения оценок энтропии также сохраняются в третьей области блока памяти.
Далее на этапе 9 осуществляют накопление полученных консервативных оценок для каждого надежного источника данных путем суммирования этих оценок энтропии каждого надежного источника с последующей записью полученных сумм в ячейки третьей области блока памяти, при этом в каждую ячейку записывают суммы от одного источника.
На этапе 10 осуществляют запись смешанных сжатых данных, полученных упомянутым ранее способом, в соответствующие ячейки третьей области блока памяти. Запись этих данных осуществляют так же, как и запись данных в соответствующие ячейки второй области блока памяти, т.е. в каждую ячейку записывают смешанные данные только от одного надежного источника.
Установлено следующее правило распределения значений по трем областям памяти:
FR-источник. Для выборки из пяти отсчетов:
Два отсчета в первую область блока памяти;
Два отсчета во вторую область блока памяти;
Один отсчет в третью область блока памяти.
SR-источник. Для выборки из семи отсчетов:
Четыре отсчета в первую область блока память;
Два отсчета во вторую область блока памяти;
Один отсчет в третью область блока памяти.
FU-источник. Для выборки из пяти отсчетов:
Три отсчета в первую область блока памяти;
Два отсчета во вторую область блока памяти.
SU-источник. Для выборки из семи отсчетов:
Пять отсчетов в первую область блока памяти;
Два отсчета во вторую область блока памяти.
Так, например, если в системе задействовано восемь источников - четыре надежных и четыре ненадежных, то первая и вторая область блока памяти содержат по восемь подобластей каждая. Третья область блока памяти содержит четыре подобласти памяти.
На этапе 11 осуществляют проверку выполнения следующих условий:
а) суммы текущих оценок энтропии должны быть равны или превышать число 128 для, по меньшей мере, трех источников, причем один из упомянутых источников должен быть быстрым и надежным или медленным и надежным,
б) упомянутые суммы приведенных оценок энтропии должны быть равны или превышать число 128 для каждого источника, при этом все источники должны быть быстрыми и надежными или медленными и надежными,
в) упомянутые суммы консервативных оценок энтропии должны быть равны или превышать число 128 для каждого источника, при этом все источники должны быть быстрыми и надежными или медленными и надежными.
В случае соблюдении всех указанных условий формируют новое стартовое значение для генератора псевдослучайной последовательности (этап 12). Для этого осуществляют объединение смешанных сжатых данных, сохраненных в соответствующих ячейках первой и второй областей блока памяти, и предыдущего стартового значения генератора псевдослучайной последовательности с итеративным циклическим хэшированием полученных объединенных данных, извлеченных из упомянутых ячеек первой и второй областей блока памяти, и предыдущего стартового значения.
Здесь необходимо отметить, что при формировании нового стартового значения для ГПСЧ используют данные, сохраненные в третьей области блока памяти, только в момент включения внешнего устройства, например принтера. Эти данные, сохраненные в третьей области блока памяти, объединяют с данными, сохраненными в первой и второй областях блока памяти.
Рассмотрим подробнее этапы объединения данных и хеширования полученных данных.
Как уже отмечалось ранее, в первой и второй областях записаны смешанные сжатые данные соответствующих источников данных. Эти данные имеют по 256 двоичных разрядов. Предыдущее стартовое значение ГПСЧ также имеет 256 двоичных разрядов.
Таким образом, длина двоичной последовательности после конкатенации равна 768.
На втором этапе, аналогично процедуре смешивания, выполняют итеративное циклическое хэширование на основе функции SHA-256.
Для этого на вход хэш-функции подают двоичный блок из 512-и разрядов. Затем результатом хэширования замещают первые 256 двоичных разрядов входного блока. Метод вычисления заключается в последовательном хэшировании данных входной последовательности с фиксированным сдвигом на 256 разрядов.
Обозначим хэш-функцию Н(·), входной блок В;, а два подблока Si1 и Si2, Вi=Si1||Si2. Предположим, что входная последовательность длиной 768 двоичных разрядов состоит из одного блока B1 и одного подблока S21. Тогда в результате применения хэш-функции к блоку B1 получим следующий результат H(B1)||S12||S21. На следующем шаге применим хэш-функцию к блоку S12||S21. Результат равен H(B1)||H(S12||S21)||S21. На заключительном шаге применим хэш-функцию к конкатенации первого и третьего подблоков с результатом H(B1)||H(S12||S21)||H(H(B1)||S21).
Для полноценного обновления необходимо выполнить три итерации. Например, после второй итерации получим следующий результат: H(H(B1)||H(S12||S21))||H(H(S12||S21)||H(H(B1)||S21))||H(H(B1)||S21)||H(H(B1)||H(S12||S21))).
В случае обновления стартового значения при включении печатающего устройства выполняют хэширование блока из 512-и двоичных разрядов.
Полученное новое стартовое значение подают в качестве стартового значения на генератор псевдослучайных чисел, который на основе полученного нового стартового значения формирует новые псевдослучайные числа, которые затем используют в системах защиты, например, для формирования пароля, ключей криптографии и т.п.
Описанный выше способ реализуется следующим устройством генерирования стартового значения для генератора псевдослучайной последовательности.
Структура устройства формирования в деталях показана на фиг.2. Устройство содержит в своем составе: блок 13, представляющий собой средство для анализа вида источника данных и вычисления текущих оценок энтропии, блок 14, представляющий собой средство сжатия данных, блок 15, предназначенный для смешивания данных, блок 16, осуществляющий суммирование оценок энтропии, блок 17, являющийся средством накопления данных и вычисления оценок энтропии, блок 18, представляющий собой средство формирования нового стартового значения, и блок 19, предназначенный для выдачи стартового значения генератору псевдослучайной последовательности. На вход устройства подаются данные от источников данных.
Здесь необходимо отметить, что перечисленные средства могут иметь как аппаратное выполнение, так и программное выполнение, при этом блок 13, в случае его аппаратного выполнения, представляет собой либо процессор, либо любую комбинационную схему, например, на базе элементов И, ИЛИ.
Блок 13 в одном из вариантов может содержать в своем составе средство регистрации частоты случайного события и средство вычисления текущих оценок энтропии. Такое средство регистрации предназначено для регистрации случайных событий упомянутых источников в течение определенного интервала времени, а средство вычисления текущих оценок энтропии предназначено для осуществления вычисления текущих оценок энтропии на основе полученных частот по указанной ранее формуле Шеннона.
Однако могут быть варианты, когда упомянутое средство регистрации частоты событий не входит в состав средства анализа (блок 13) и является внешним по отношению к нему.
Блок 17 содержит в своем составе несколько функциональных элементов (на фиг.2 не показаны), которыми, в данном примере реализации являются два средства вычисления оценок энтропии, два средства суммирования и блок памяти, разделенный на три области, каждая из которых, в свою очередь, разделена на множество ячеек. Количество ячеек областей блока памяти зависит от числа источников.
Устройство работает следующим образом.
На вход блока 13 подают данные от различных источников данных, которые, как указано ранее, представляют собой различные случайные процессы. На основе полученных данных в блоке 13 осуществляют анализ источников, а также вычисляют текущие оценки энтропии для каждого источника заявляемым способом.
Для вычисления текущих оценок в блоке 13 используют данные о частотах, получаемые от средства регистрации частоты случайного события. На основе полученных частот в блоке 13 осуществляют вычисление текущих частот.
Вычисленные текущие оценки энтропии подают на вход блока 16, который на основе полученных текущих оценок энтропии осуществляет суммирование полученных текущих оценок энтропии для каждого источника.
Полученные суммарные оценки с выхода блока 16 поступают на вход блока 17, осуществляющего накопление данных и вычисление оценок энтропии.
Блок 17 работает следующим образом.
Первое средство вычисления оценок энтропии, входящее в состав блока 17, вычисляет приведенные оценки энтропии для каждого источника данных на основе полученных текущих оценок энтропии конкретного источника данных, полученных от блока 13. Вычисление этих оценок подробно описано при раскрытии способа. Полученные оценки передаются первому средству суммирования.
Это средство суммирования вычисляет суммы приведенных оценок энтропии для каждого источника данных путем суммирования полученных приведенных оценок энтропии конкретного источника данных.
Второе средство вычисления оценок энтропии осуществляет выбор промежуточных значений из числа приведенных оценок энтропии для каждого надежного источника, полученных в первом средстве вычисления оценок энтропии, и вычисляет консервативные оценки энтропии для каждого надежного источника данных на основе этих выбранных промежуточных значений. Алгоритм вычисления этих оценок подробно описан ранее при раскрытии способа.
Второе средство суммирования осуществляет суммирование консервативных оценок энтропии для каждого надежного источника данных путем суммирования консервативных оценок энтропии данного источника, вычисленных вторым средством вычисления оценок.
Блок 14, представляющий собой средство сжатия, подключен параллельно блоку 13, и на его вход подаются данные от источника. Получив данные от источников, блок 14 осуществляет сжатие этих данных, как это уже было описано ранее при раскрытии способа. Полученные сжатые данные с выхода блока 14 поступают вход блока 15, являющегося средством смешивания данных. В блоке 15 осуществляется смешивание полученных данных. Процедура смешивания и условия выполнения смешивания подробно описано ранее при раскрытии способа.
Блок памяти (на фиг.2 не показан), входящий в состав блока 17, осуществляет запись смешанных сжатых данных, полученных от средства смешивания, а также запись оценок энтропии, полученных от средства смешивания, а также запись оценок энтропии, полученных от блока 13 и блока 16. В ячейки первой области блока памяти записывают смешанные сжатые данные для всех источников. В ячейки второй и третьей областей блока памяти записывают смешанные сжатые данные от надежных источников.
Запись в памяти осуществляют так же, как это было описано при раскрытии способа, а именно в каждую конкретную ячейку записывают смешанные сжатые данные только от одного источника.
Кроме того, в соответствующие ячейки первой области блока памяти записывают текущие оценки энтропии, полученные в блоке 13. В соответствующую ячейку второй области блока памяти записывают приведенные оценки энтропии, полученные в первом средстве вычисления оценок энтропии. В соответствующую ячейку третьей области блока памяти записывают консервативные оценки энтропии, полученные во втором средстве вычисления оценок энтропии.
Сформированные данные в блоке 17 и блоке 15 подают на вход блока 18, представляющего собой средство формирования нового стартового значения. Этот блок 18 осуществляет проверку выполнения следующих условий:
а) сумма текущих оценок энтропии в первой области блока памяти должна быть равна или превышать число 128 для, по меньшей мере, трех источников, при этом один из источников должен быть быстрым и надежным или медленным и надежным;
б) сумма приведенных оценок энтропии во второй области блока памяти должна быть равна или превышать число 128 для каждого источника, при этом все источники должны быть быстрыми и надежными или медленными и надежными;
в) сумма приведенных оценок энтропии в третьей области блока памяти должна быть равна или превышать 128 для каждого источника, при этом все источники должны быть быстрыми и надежными или медленными и надежными.
В случае соблюдения этих условий блок 18 формирует новое стартовое значение для генератора псевдослучайной последовательности путем объединения смешанных сжатых данных, сохраненных в соответствующих ячейках первой и второй областей блока памяти, и предыдущего стартового значения генератора псевдослучайной последовательности путем итеративного циклического хэширования полученных этих данных и предыдущего стартового значения. Процедура формирования нового стартового значения подробно описана ранее при раскрытии способа.
Сформировав новое стартовое значение, блок 18 подает полученное значение на вход блока 19, представляющего собой средство выдачи стартового значения. Блок 19 передает полученное новое стартовое значение на вход генератора псевдослучайных чисел, который на основе нового стартового значения формирует новые псевдослучайные числа, на основе которых формируются пароли, криптографические ключи и т.п.
| название | год | авторы | номер документа |
|---|---|---|---|
| УСТРОЙСТВО ДЛЯ ГЕНЕРАЦИИ ПСЕВДОСЛУЧАЙНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ ДВОИЧНЫХ ЧИСЕЛ С ИСПОЛЬЗОВАНИЕМ ЭЛЛИПТИЧЕСКИХ КРИВЫХ | 2005 |
|
RU2294559C1 |
| СПОСОБ ГЕНЕРАЦИИ СЛУЧАЙНЫХ ДВОИЧНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ С ИСПОЛЬЗОВАНИЕМ КОМПЬЮТЕРА И ДЕЙСТВИЙ ПОЛЬЗОВАТЕЛЯ | 2016 |
|
RU2628213C1 |
| СПОСОБ ГЕНЕРАЦИИ СЛУЧАЙНОГО ЧИСЛА С ИСПОЛЬЗОВАНИЕМ КОМПЬЮТЕРА (ВАРИАНТЫ) | 2014 |
|
RU2577201C2 |
| Генератор псевдослучайных последовательностей | 2019 |
|
RU2699259C1 |
| УСТРОЙСТВО ОБРАБОТКИ АДРЕСОВ КОММУТАТОРА ЛОКАЛЬНОЙ ВЫЧИСЛИТЕЛЬНОЙ СЕТИ, РАБОТАЮЩЕГО ПО ПРИНЦИПУ ПРОЗРАЧНОГО МОСТА | 2005 |
|
RU2304802C1 |
| ПРЕДСТАВЛЕНИЕ ЦИФРОВЫХ МАТЕРИАЛОВ, ОСНОВАННОЕ НА ИНВАРИАНТНОСТЯХ МАТРИЦ | 2004 |
|
RU2387006C2 |
| КВАНТОВЫЙ ГЕНЕРАТОР СЛУЧАЙНЫХ ЧИСЕЛ | 2015 |
|
RU2613027C1 |
| СПОСОБ БЛОЧНОГО КРИПТОГРАФИЧЕСКОГО ПРЕОБРАЗОВАНИЯ ДВОИЧНОЙ ИНФОРМАЦИИ | 1998 |
|
RU2140713C1 |
| СПОСОБ КРИПТОГРАФИЧЕСКОГО ПРЕОБРАЗОВАНИЯ БЛОКОВ ЦИФРОВЫХ ДАННЫХ | 1997 |
|
RU2140709C1 |
| СПОСОБ ОДНОЗНАЧНОГО ХЭШИРОВАНИЯ НЕОДНОЗНАЧНЫХ БИОМЕТРИЧЕСКИХ ДАННЫХ | 2010 |
|
RU2451409C2 |
Изобретение относится к вычислительной технике и может использоваться в различных криптографических системах. Способ и устройство позволяют формировать стартовые значения, обеспечивающие динамическую оценку скоростей источников, классификацию источников на быстрые и медленные, надежные и ненадежные, а также формировать стартовые значения с учетом скоростных характеристик источников и надежности этих источников. В способе осуществляется вычисление оценок энтропии и запись смешанных сжатых данных в соответствующие ячейки разных областей блока памяти и на основе записанных данных осуществляют формирование нового стартового значения. Устройство формирования стартового значения для генератора псевдослучайной последовательности содержит средство анализа источника данных и вычисления текущих оценок энтропии, средство сжатия данных, средство смешивания данных, средство накопления данных и формирования оценок энтропии, средство формирования нового стартового значения. 2 н. и 8 з.п. ф-лы, 2 ил.
накапливают данные от различных внешних источников, представляющих собой случайные процессы, в блоке памяти;
анализируют полученные данные для определения типа источника: быстрые или медленные, надежные или ненадежные;
для каждого источника вычисляют текущие оценки энтропии по данным, полученным от этого источника;
осуществляют для каждого источника накопление текущих оценок энтропии путем суммирования этих оценок с последующей записью их в блоке памяти, при этом каждую конкретную ячейку блока памяти используют для записи текущих оценок энтропии только от одного источника;
осуществляют сжатие данных, полученных от каждого источника, с применением хэш-функции, с последующей записью результата сжатия в другую ячейку блока памяти, при этом такую ячейку памяти используют для записи сжатых данных только от одного источника;
осуществляют смешивание сжатых данных с применением хэш-функции и записывают результат смешивания в другую ячейку блока памяти;
определяют минимальную оценку энтропии для каждого надежного источника на основе полученных текущих оценок энтропии;
осуществляют вычисление приведенной оценки энтропии путем деления минимальной оценки на два и сохраняют последовательность приведенных значений в последовательности ячеек в другой, например, второй, области блока памяти;
осуществляют накопление приведенных оценок энтропии для каждого надежного источника путем суммирования этих оценок и записи полученных сумм приведенных оценок в соответствующие ячейки второй области блока памяти, при этом каждую ячейку блока памяти используют для записи суммы приведенной оценки энтропии только от одного источника;
для каждого надежного источника данных осуществляют запись сжатых данных в другую ячейку второй области памяти, при этом такую ячейку блока памяти используют для записи сжатых данных только от одного источника;
для каждого надежного источника данных осуществляют запись смешанных данных в соответствующую ячейку второй области блока памяти;
для каждого надежного источника данных определяют набор приведенных оценок энтропии, сохраненных в последовательности ячеек второй области блока памяти,
осуществляют вычисление консервативной оценки энтропии путем деления на два ранее уже приведенных оценок энтропии, сохраненных в соответствующих ячейках второй области блока памяти, которая также сохраняется в соответствующей ячейке другой, например, третьей, области блока памяти;
осуществляют накопление консервативных оценок энтропии для каждого надежного источника путем суммирования этих оценок и записи полученных сумм консервативных оценок в последовательности ячеек третьей области блока памяти, при этом каждую ячейку блока памяти используют для записи консервативной оценки энтропии только от одного источника;
для каждого надежного источника данных осуществляют запись сжатых данных в соответствующую ячейку третьей области блока памяти, при этом каждую ячейку памяти используют для записи сжатых данных только от одного источника;
для каждого надежного источника данных осуществляют запись смешанных данных в соответствующую ячейку третьей области блока памяти;
проверяют выполнение следующих условий:
а) суммы текущих оценок энтропии должны быть равны или превышать число 128 для, по меньшей мере, трех источников, при этом один из источников должен быть быстрым и надежным или медленным и надежным,
б) суммы приведенных оценок энтропии должны быть равны или превышать число 128 для каждого источника, при этом все источники должны быть быстрыми и надежными или медленными и надежными,
в) суммы консервативных оценок энтропии должны быть равны или превышать число 128 для каждого источника, при этом все источники должны быть быстрыми и надежными или медленными и надежными,
при соблюдении всех указанных условий формируют новое стартовое значение для генератора псевдослучайной последовательности путем дополнительного смешивания уже смешанных данных, сохраненных в соответствующих ячейках первой и второй областей блока памяти, и предыдущего стартового значения генератора псевдослучайной последовательности, при этом формирование осуществляют путем применения итеративного циклического хэширования объединенных данных, извлеченных из ячеек первой, второй областей блока памяти, а также предыдущего стартового значения.
где pi - вероятность, вычисленная на основе частоты появления случайного события в течение фиксированного интервала времени.
где pi - вероятность, вычисленная на основе частоты появления случайного события в течение фиксированного интервала времени.
где рi - вероятность, вычисленная на основе частоты появления случайного события в течение фиксированного интервала времени.
| US 5778069 А, 07.07.1998 | |||
| Устройство для контроля генератора случайных чисел | 1989 |
|
SU1674118A1 |
| US 5732138 A, 24.03.1998 | |||
| Магнитометр | 1979 |
|
SU949563A1 |
| EP 1202165 A2, 02.05.2002. | |||
