Генератор случайных чисел и поточный шифр

Генератор случайных чисел и поточный шифр

Иллюстрации

Показать все

Реферат

ОБЛАСТЬ ТЕХНИКИ

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

УРОВЕНЬ ТЕХНИКИ

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

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

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

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

Глава книги автора James E Gentle: "Chapter 1. Simulating Random Numbers from the Uniform Distribution", в: "Random Number Generation and Monte Carlos Methods (Second Edition)", 1 января 2005 года (2005-01-01), Springer, New York, XP055082923, ISBN: 978-0-38-700178-4, стр. 1-56, раскрывает несколько решений предшествующего уровня техники. Она описывает в разделе 1.8, стр. 46, что генерирования случайных чисел зачастую могут улучшаться посредством комбинирования более чем одного генератора, и что генераторы, которые комбинируются, могут иметь любой тип. Она также описывает комбинированный генератор, который использует линейный конгруэнтный генератор и два генератора со сдвиговым регистром.

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

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

СУЩНОСТЬ ИЗОБРЕТЕНИЯ

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

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

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

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

Авторы изобретения имеют понимание того, что генерирование последовательности случайных чисел из двух независимых последовательностей не обязательно представляет собой преимущество. Вместо усложнения проблемы, независимость также может помогать взломщику. Фактически, атаки на комбинированные линейные сдвиговые регистры пытаются изолировать потоки друг от друга, с тем, чтобы атаковать их отдельно. Типично это достигается посредством формирования некоторых допущений ("предположений") для одного потока и проверки их достоверности посредством вычисления для другого потока. Например, в статье автора T. Johansson, "Reduced Complexity Correlation Attacks on Two Clock-Controlled Generators", опубликованной в ASIACRYPT, 1998 г.: 342-356, описывается атака на генератор переменной ступенчатой функции. Предлагается ожидать сегмента длины M, содержащего небольшое число единиц, и формировать такое допущение, что только половина нулей исходит из первого линейного сдвигового регистра. Все единицы и оставшиеся нули затем предположительно исходят из второго линейного сдвигового регистра.

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

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

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

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

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

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

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

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

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

Размер модулей связан с безопасностью системы. Коммерчески защищенная система может использовать, в качестве примера, модули длиной 128 битов. Возможны более длинные модули, скажем, длиннее или равные 128, длиннее или равные 256; или короче, скажем, длиннее или равные 64 битам.

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

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

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

Выходная функция может просто копировать внутреннюю последовательность наружу, тем не менее, авторы изобретения обнаружили, что безопасность еще более повышается посредством экранирования части вывода функций от внешнего мира. Например, выход может быть сконфигурирован с возможностью генерировать следующее число в последовательности случайных чисел посредством выбора числа (b) битов из сгенерированного следующего числа во внутренней последовательности, т.е. выбора некоторых, но не всех битов. Например, можно предписывать шаблон, для которого следует извлекать биты, скажем биты, 3, 5, 8, 13, 21, 34, 55, 89 (в этом случае b=8). Обнаружено преимущество того, чтобы связывать значение b с другими частями расчетной схемы, например, функцией комбинирования, как описано ниже. В предпочтительном варианте осуществления выбираются b младших битов.

Обнаружено преимущество того, чтобы включать в функцию комбинирования также этап редукции, типично в качестве последнего этапа в комбинировании. Например, функция комбинирования может содержать операцию по модулю по модулю комбинирования. Комбинация выбирается таким образом, что по меньшей мере один из нескольких модулей, ассоциированных с несколькими функциями, имеет такое свойство, что средство комбинирования минус по меньшей мере один из нескольких модулей представляет собой кратное степени 2, более предпочтительно все модули имеют такую разность, хотя и с различными кратными. Степень двух может выбираться большей, если большее число битов является видимым за пределами электронного устройства. Множитель в кратных числах является небольшим относительно коэффициентов, например, меньшим степени двух. Например, можно извлекать степень двух (2^b) в качестве 2^8 или 2^16, кратное степени 2 затем может извлекаться как меньшее 2^2b, т.е. 2^16 или 2^32, соответственно.

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

Редукция числа выходных битов связывает последовательность случайных чисел с так называемой "проблемой зашумленной полиноминальной интерполяции". Насколько известно, проблема зашумленной полиноминальной интерполяции может активно решаться только с использованием схем на основе решеток при очень значительной трудоемкости вычислений. См., например, статью "Noisy Polynomial Interpolation and Noisy Chinese Remaindering" авторов Daniel Bleichenbacher и Phong Q. Nguyen. К настоящему моменту не предложено генерирование случайных чисел, связанное с проблемой зашумленной полиноминальной интерполяции.

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

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

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

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

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

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

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

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

КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ

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

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

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

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

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

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

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

ПОДРОБНОЕ ОПИСАНИЕ ВАРИАНТОВ ОСУЩЕСТВЛЕНИЯ

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

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

Фиг.1 иллюстрирует на принципиальной блок-схеме электронное устройство 100 генерирования случайных чисел.

Электронное устройство 100 генерирования случайных чисел содержит электронное средство 110 хранения параметров, электронное устройство 120 оценки функций, запоминающее устройство 130 внутренних последовательностей и выход 140. Необязательно, электронное устройство 100 генерирования случайных чисел также содержит устройство 150 тестовых функций.

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

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

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

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

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

Запоминающее устройство 130 последовательностей содержит всю или часть сгенерированной внутренней последовательности случайных чисел. Устройство 100 генерирования случайных чисел сконфигурировано с возможностью сначала генерировать внутреннюю последовательность случайных чисел, из которой извлекается внешняя последовательность случайных чисел для вывода. В более простом варианте осуществления внешняя последовательность может извлекаться аналогично внутренней последовательности, тем не менее, выявлена большая надежность того, чтобы выполнять обработку для внутренней последовательности различных видов перед выводом случайных чисел. По меньшей мере, запоминающее устройство 130 последовательностей в достаточной степени больше для того, чтобы содержать предыдущее значение внутренней последовательности случайных чисел, типично, непосредственно перед этим сгенерированное значение. В случае если функции, сохраненные в средстве 110 хранения параметров и используемые посредством устройства 120 оценки функций, являются многомерными, запоминающее устройство 130 последовательностей является достаточно большим для того, чтобы содержать соответствующее число предыдущих значений. Запоминающее устройство 130 последовательностей используется как в качестве ввода в устройство 120 оценки функций для того, чтобы генерировать следующее значение во внутренних последовательностях, так и в качестве ввода в выход 140 для того, чтобы генерировать следующее внешнее значение. Запоминающее устройство 130 последовательностей обновляется посредством устройства 120 оценки функций, когда генерируется новое значение. В случае если размер запоминающего устройства 130 последовательностей ограничивается, скажем, одним или несколькими значениями, устройство 120 оценки функций должен перезаписывать значение, сгенерированное наибольшее число итераций назад.

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

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

В варианте осуществления, показанном на фиг.1, устройство 120 оценки функций содержит средство оценки функций и средство комбинирования результатов оценки. Средство оценки функций сконфигурировано с возможностью оценивать функцию из нескольких функций, показанных в средстве 110 хранения параметров, и осуществлять редукцию результата по модулю ассоциированным модулем. Оценка повторяется для каждой функции, этого указывается посредством обратной линии 124. Результаты нескольких функций затем комбинируются посредством средства 128 комбинирования результатов оценки. Устройство 120 оценки функций может иметь доступ к некоторому запоминающему устройству, чтобы временно сохранять результаты оценки. В случае если функция комбинирования обеспечивает возможность частичной оценки, это запоминающее устройство может ограничиваться одним значением; в противном случае, это запоминающее устройство должно временно сохранять все из нескольких результатов оценки. В варианте осуществления устройство оценки 120 содержит несколько средств оценки функций, что способствует параллелизации, но что важно, также обеспечивает возможность использования различных типов функций, без серьезного расширения способа, которым представляются функции, т.е. шаблон функции.

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