ГЕНЕРАТОР СЛУЧАЙНЫХ ЧИСЕЛ И ПОТОЧНЫЙ ШИФР

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

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

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

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

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

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

Первый пример. Внешняя последовательность случайных чисел может задаваться как последовательность: так что каждый элемент соответствует b битам другого элемента внутренней последовательности, например, , сгенерированной из оценки по двум полиномам конечного поля (f и g), и результат, комбинированный посредством сложения целых чисел, обозначается следующим образом: . В этой системе обозначений, обозначает редукцию по модулю q. Следует отметить, что может превышать p или q, поскольку он генерируется в качестве сложения целых чисел, значение может быть непосредственно использовано для последующих y-значений вследствие модульных операций. Генератор случайных чисел может использовать значение x₀ в качестве начального числа для того, чтобы создавать различные последовательности, скажем, случайного значения.

Другие варианты осуществления включают в себя следующее:

1. Последовательность также может составляться следующим образом:

с использованием случайных чисел и в качестве начального числа.

2. Использование многомерных полиномов, например, с двумя переменными, например:

с использованием случайных чисел и в качестве начального числа.

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

4. Последовательность также может составляться посредством использования в качестве ввода преобразование предыдущего значения . Например, может быть версией со сдвигом в x битов или преобразовываться таким образом, что i-й бит перемещается в j-й бит в .

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

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

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

Ниже приводится еще один способ выбора параметров, который является особенно преимущественным, поскольку он соответствует конкретной сложной математической проблеме.

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

Число b может выбираться большим, скажем, 8, 16, 32. Число полиномов может быть большим, скажем, трех. Размер комбинирующего модуля может быть меньшим, скажем, 32, 64, 80 битов или большим, скажем, 196 или 256 либо между этими значениями.

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

1. Выбор случайных небольших случайных чисел

2. Задание модулей

3. Тестирование того, являются или нет взаимно простыми, если нет, переход к этапу 1.

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

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

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

Это и другие варианты осуществления протестированы с использованием комплекта тестов на случайность, указываемого в специальном издании NIST 800-22 "A Statistical Test Suite for Random and Pseudorandom number generators for Cryptographic Applications". Обнаружено, что случайные свойства в последовательностях случайных чисел, сгенерированных таким способом, являются вполне достаточными для криптографического использования.

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

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

На этапе 310 получаются несколько функций, и, для каждой функции из нескольких функций, ассоциированный модуль, причем не все модули равны. На этапе 320 генерируются начальные значения внутренней последовательности случайных чисел. Например, они могут быть зашумленными значениями, полученными из некоторого другого источника. В этом случае сформированная последовательность должна быть непрогнозируемой; до сих пор начальная последовательность была непрогнозируемой. Альтернативно это могут быть определенные значения, скажем, все 0; в этом случае последовательность должна быть воспроизводимой. Для взломщика, который не знает начальные значения, например, поскольку они хранятся в секрете от него, последовательность должна быть неотличимой от истинной случайной последовательности. По меньшей мере, любая различимость не должна быть достаточной для того, чтобы прогнозировать будущие значения последовательности. На этапе 330 генерируется следующее число во внутренней последовательности случайных чисел. Это осуществляется способом, предоставленным на этапах 332-338. На этапе 332 получается ранее сгенерированное число во внутренней последовательности случайных чисел. Если последовательность помечается, как , причем теперь генерируемое следующее число составляет (более высокие индексы соответствуют позднее сгенерированным значениям), то используемое число может составлять , оно также может составлять другое значение. Следует отметить, что на этой блок-схеме последовательности операций способа одно и то же предыдущее значение используется для всех функций. Это предпочтительная ситуация, поскольку она гарантирует зависимость между функциями. На этапе 334 функция оценивается для ранее полученного сгенерированного значения внутренней последовательности () по модулю модулем, ассоциированным с функцией оценки. В случае если функции представляют собой полиномы или комбинации S-блоков, после которых, возможно, идет линейная функция или полином, такие вычисления возможны на устройствах с низкими ресурсами. Такие функции также могут кодироваться естественным способом, скажем, в запоминающем устройстве 110. На этапе 336 определяется, остаются или нет функции для оценки, и если да, последовательность операций возвращается к этапу 334, чтобы оценивать следующую функцию из нескольких функций. На этапе 338 несколько результатов оценки комбинируются посредством применения функции комбинирования. Для множества функций, в частности, сложения и XOR и т.п., этап 338 может быть интегрирован на этапе 336. На этапе 340 следующее число генерируется в последовательности случайных чисел из сгенерированного следующего числа во внутренней последовательности.

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

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

Фиг.2 иллюстрирует использование случайной последовательности в поточном шифре.

Чертеж показывает устройство 210 генерирования параметров. Устройство 210 генерирования параметров сконфигурировано с возможностью извлекать криптографический ключ в качестве ввода и формировать параметры для использования в электронном устройстве 100 генерирования случайных чисел. Следует отметить, что некоторые параметры могут быть фиксированными, некоторые могут генерироваться. Типично, число полиномов, число выходных битов и степени полиномов должны быть определены заранее на основе оценки модели угроз. В этом варианте осуществления устройство 210 генерирования параметров генерирует по меньшей мере одно из нескольких модулей или нескольких функций. Предпочтительно устройство 210 генерирования параметров генерирует как несколько модулей, так и несколько функций. Устройство 210 генерирования параметров может генерировать или не генерировать сами функции. Предпочтительно, чтобы устройство 210 генерирования параметров генерировало функции. Например, устройство 210 генерирования параметров может генерировать последовательность коэффициентов для использования в качестве коэффициентов полинома. Устройство 200 поточного шифрования дополнительно содержит устройство 240 комбинирования для комбинирования последовательности случайных чисел. Кроме того, устройство 200 поточного шифрования сконфигурировано с возможностью получать поток данных, скажем, из ввода либо из средства хранения, либо из генерирования, и сконфигурировано с возможностью дополнительно обрабатывать выходной поток. Поток данных может представлять поток простых данных, и при этом выходной поток является соответствующим потоком зашифрованных данных. Поток данных также может представлять поток зашифрованных данных, и при этом выходной поток представляет поток простых данных. Выходной поток получается из входного потока посредством комбинирования второго с последовательностью (потоком) случайных чисел, извлекаемой из электронного устройства 100 генерирования случайных чисел.

При работе устройство 210 генерирования параметров принимает криптографический ключ, скажем, 128-битовый или 256-битовый ключ, который является секретом для взломщика. Возможно, устройство 210 генерирования параметров также принимает одноразовый номер или другие данные. С помощью принимаемых данных устройство 210 генерирования параметров конфигурирует электронное устройство 100 генерирования случайных чисел, т.е. конфигурирует средство 110 хранения параметров. В этот момент электронное устройство 100 генерирования случайных чисел сконфигурировано с возможностью формировать последовательность случайных чисел. После того как устройство 200 поточного шифрования начинает прием входного потока 220, входной поток комбинируется с последовательностью случайных чисел. Это может осуществляться множеством способов, например, как фактически известно в области техники поточных шифров. В частности, устройство 240 комбинирования может представлять собой XOR-устройство. Таким образом, формируется выходной поток. Выходной поток может быть сохранен либо дополнительно обработан или передан и т.д.

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

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

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

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

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

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

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

Расширение ключей может выполняться посредством их хэширования, скажем, вместе со счетчиком, если требуются несколько блоков. Sha-1 и Sha-256 являются подходящими вариантами.

Поточные шифры являются применимыми в продуктах и услугах, которые требуют защиты связи, в частности, на ограниченных по ресурсам устройствах. Пример такой ограниченной по ресурсам системы представляет собой управление освещением. Эта система проиллюстрирована на фиг.5. Фиг.5 показывает контроллер 510 электрического освещения и электронный осветительный прибор 520. Контроллер 510 освещения может отслеживать и/или управлять осветительным прибором 520. Осветительный прибор 520 может представлять собой, скажем комбинацию лампы/светодиодного формирователя сигналов управления. Контроллер 510 освещения и осветительный прибор 520 сконфигурированы с возможностью двусторонней связи. Тем не менее, если требуется только мониторинг или только управление, также может использоваться односторонняя связь. Контроллер 510 освещения и осветительный прибор 520 совместно используют общий секретный ключ K. Как контроллер 510 освещения, так и осветительный прибор 520 содержат такое устройство, как устройство 200 поточного шифрования или устройство 400 поточного шифрования. С использованием разделенного секрета и, возможно, одноразового номера, которой они обменялись (возможно, в простом формате) ранее, как контроллер 510 освещения, так и осветительный прибор 520 конфигурируют электронное устройство 100 генерирования случайных чисел. Если контроллер 510 освещения отправляет сообщение в осветительный прибор 520, скажем, для управления им, оно шифруется в качестве поточного шифра. Когда сообщение принимается в осветительном приборе 520, сообщение может быть дешифровано с использованием аналогичной сгенерированной последовательности случайных чисел. Связь из осветительного прибора 520 в контроллер 510 освещения осуществляется наоборот.

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

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

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

Список ссылок с номерами на фиг.1, 2, 4 и 5

100 - электронное устройство генерирования случайных чисел для генерирования последовательности случайных чисел

110 - электронное средство хранения параметров

120 - электронное устройство оценки функций

122 - средство оценки функций

124 - тракт управления

128 - средство комбинирования результатов оценки

130 - запоминающее устройство внутренних последовательностей

140 - выход

150 - устройство тестовых функций

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

210 - устройство генерирования параметров

220 - поток данных

230 - выходной поток

240 - устройство комбинирования

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

500 - электронная система управления освещением

510 - контроллер электрического освещения

520 - электронный осветительный прибор