СТРУКТУРА ПОТОЧНОГО ШИФРА С ЦИКЛИЧЕСКИМ ПЕРЕМЕЩЕНИЕМ БУФЕРОВ Российский патент 2010 года по МПК H04L9/18 H04L9/22 

Область техники

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

Предшествующий уровень техники

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

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

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

Поточные шифры вызывают больший интерес в настоящее время, потому что сформированный ими поток (известный также как "ключевой поток") достигает высокой степени защиты, сравнимой с шифром Вернама (известным также как шифр "one-time pad"). Обычно шифр Вернама формирует ключевой поток такой же длины, как шифруемое текстовое сообщение. Ключевой поток шифра Вернама считается совершенно случайным, что обеспечивает очень высокие уровни защиты, однако ему свойственны непроизводительные затраты памяти, что может быть нежелательным для некоторых применений.

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

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

Сущность изобретения

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

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

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

Краткое описание чертежей

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

Фиг.1 - примерная система поточного шифра,

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

фиг.3 - примеры образования пар циклически перемещающихся блоков памяти,

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

фиг.5 - примерный наикратчайший "простой" циклический граф, соответствующий циклически перемещающимся блокам памяти,

фиг.6 - иллюстрация способа усиления правила вывода Н путем рекурсивного циклического перемещения блоков памяти,

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

Подробное описание изобретения

В представленном ниже описании предполагается, что читатель знаком с методами криптографии. Для основного введения в криптографию читателю предлагается ознакомиться с работой A.Menezes, P.van Oorschot, S.Vanstone "Handbook of Applied Cryptography" (Справочник по прикладной криптографии), пятое издание (август 2001г.), опубликованной издательством CRC Press.

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

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

Общее представление поточного шифра

На фиг.1 показана примерная система 100 поточного шифра. Система 100 содержит генератор 102 ключевого потока, который использует ключ (k) 104 для генерации ключевого потока (z _i). Выходная функция применяется (106) для объединения созданного ключевого потока (z _i) и сообщения (m _i) 108, чтобы получить шифрованный текст (110). Сформированный ключевой поток (z _i) изменяется во времени и может создаваться случайным образом из исходного малого ключевого потока (например, начального числа), из начального числа и предыдущего шифрованного текста или т.п. Выходная функция (106) может применяться к отдельным знакам (или двоичным числам) сообщения (m _i) по одному каждый раз.

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

1. Правило для инициализации внутреннего состояния Ω шифра (например, с помощью такого ключа как 104 на фиг.1 и/или случайных значений).

2. E:Ω→Ω, механизм для развертывания или обновления состояния Ω (например, генератором 102 ключевого потока).

3. H:Ω→{0,1}ⁿ, правило вывода для формирования n-битных выводов (например, ключевого потока (z _i), сформированного элементом 102 на фиг.1).

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

В одном варианте относительно простые обновления (описанные ниже в разделе "Правила обновления") объединяются с эффективными правилами вывода (например, как описано ниже со ссылкой на фиг.2). Например, при заданном сценарии с правилом быстрого обновления Е и простым правилом вывода Н развертывающееся правило Е становится хорошим после продолжительного периода, при этом существует некоторое характеристическое время Т, при котором после Т применений правила состояние Е^Т(Ω_I) имеет мало сходства с Ω_i, если вообще его имеет. Такой метод может усилить многие известные конструкции поточного шифра, или же его можно использовать для создания широкого спектра новых шифров посредством объединения двух или более процессов, имеющих указанное свойство. Предполагается, что такие реализации будут также эффективны в программных средствах.

Память или буферы с циклически перемещающимся содержанием

На фиг.2 проиллюстрирован примерный способ 200 усиления правила вывода Н с помощью (циркулирующих или циклически перемещающихся) блоков памяти. В одном варианте способ 200 улучшает ключевой поток, сформированный генератором ключевого потока (таким как 102 на фиг.1). Элемент (например, отдельные знаки или двоичные числа), сформированный правилом вывода Н, сохраняется (202). Можно использовать различные виды устройств или сред для сохранения элемента, например, регистр, кэш или другие виды памяти (такие как описанные в связи с вычислительной средой на фиг.7). Сохраненные данные могут находиться в одном и том же или в разных устройствах.

Функция p образования пар (которая описана ниже в этом же разделе) дает результат спаривания (204) на основании значений, сохраненных по меньшей мере в двух соответствующих блоках памяти (таких как А и С, показанных на фиг.3 и 4). В одном варианте функция образования пар может принимать более двух входных значений. Индекс (например, использованный для индексации блоков памяти и/или функции образования пар) обновляется (206), например, на 1. Если заданный порог (Т) не достигнут (208), например, как определено при сравнении обновленного индекса с пороговой величиной, способ 200 возвращается к этапу 202 для сохранения следующего элемента, сформированного правилом вывода Н.

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

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

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

1. C[i] ← элемент, созданный правилом вывода Н (202).

2. Обеспечить p(A[n _i ];C[I]) (204).

3. i ← i +1 (206).

4. если i=Т (208), то А ← В, В ← С (210), i←0 (212).

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

Для определения функции р образования пар может быть определена таблица (i,n _i ) констант n _i для i∈{0,T}. Сначала можно определить неориентированный граф G с вершинами, обозначенными a ₀ ,…,a _{T_1} и c ₀ ,…,c _{T_1} (фиг.4). Затем добавляются края (a _i ,a _i+1 ) и (c _i ,c _i+1 ) для 0≤i≤T-1 и (a_ni,c_i) для 0≤i≤T. Пары (n _i ,i) таковы, что граф G имеет относительно большой обхват (где обхват - это длина кратчайшего цикла в G). Предполагается, что вместо функции образования пар или в дополнение к ней можно использовать многоаргументные функции. Кроме того, эта функция может принимать более двух аргументов (например, по одному из каждого буфера).

Функция образования пар

В отношении функции образования пар p:{0,1} ⁿ x{0,1} ⁿ →{0,1} ⁿ для каждого х функция y→p(x,y) является однозначной. Аналогично, для каждого у функция x→p(x,y) также дает взаимно однозначное соответствие. В одном варианте эта функция является эффективной для вычислений и не симметричной на ее входах. Некоторые примерные выборы для функции образования пар:

A: p(x,y)=x ⊕ S[y], где S - фиксированная таблица перестановок.

B: p(x,y)=x ⊕ (ay+b), где a и b - две константы, причем а нечетная. Эта операция может быть эффективно реализована с использованием SSE (потокового SIMD-расширения, где SIMD означает "один поток команд - несколько потоков данных"), имеющегося в некоторых современных процессорах (например, которые описаны ниже со ссылкой на процессор 704 на фиг.7).

С: p(x,y)=γ,δ выбирается как почти универсальная хэш-функция путем итерации следующих правил:

где x ^L и x ^R соответственно означают левую и правую половины х, при произвольно выбранных а,b.

Граф G схематически отражает отношения, которые известны противнику: (a _i ,a _i+1 ) и (c _i ,c _i+1 ) связываются через обновления внутреннего состояния, и (a _n ,c _i ) - аргументы функции образования пар.

Так как функция образования пар представляет собой взаимно однозначное соответствие обоих ее аргументов, знание ее точного значения не даст утечки информации о любом из аргументов. Если при составлении функции не произошло никакого сокращения, то одно из наилучших отношений, которые можно извлечь, будет иметь по меньшей мере k входных значений (обхват графа). Действительно, для любого из m<k входных значений z ₀ = пара (x ₀ ,y ₀ ), z ₁ = пара (x₁,y₁), z _m = пара (x _m ,y _m ), может быть много входных пар (x ₀ ,y ₀ ),…,(x _m ,y _m ), которые приведут к этим выходным значениям.

В одном варианте таблица n _i создается автономно и поэтому может выбираться так, чтобы получить максимальный обхват графа. Эвристически, установка n _i =c*i mod Т, где c - взаимно простое, приращиваемое к Т, дает требуемые результаты, как будет обсуждаться ниже. В одном варианте такие методы дают результаты без потерь в том смысле, что выходной результат имеет такой же размер, как входное значение при однозначном соответствии байтов.

Параметры: размер буфера, свойства графа

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

При рассмотрении графов, определенных как n _i =c*i, где с - взаимно простое, приращиваемое к Т, можно относительно легко провести исчерпывающий поиск возможных приращений. В следующей таблице 1 представлены примерные приращения, при которых максимально увеличиваются обхват и минимальный "простой" цикл (для n=8, 16, 32, 128). В таблице 1 приведены только те с, которые меньше n/2.

Таблица 1

Свойства графа G

Длина буфера Приращение Обхват Мин. простой цикл Т=8 С=3 6 4 16 3,5,7 6 6 32 7,9 8 10 64 19,27 8 12 128 15,17,47,49 8 18

Дополнительные буферы

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

Вместе с переменной задержкой можно использовать буфер задержки D, который инициализируется случайными величинами. В одном варианте используется функция обновления задержка+S[задержка], где S - случайная перестановка за один цикл. Как показано на фиг.6, для случая сдвига блоков памяти влево можно итерировать следующие этапы.

1. C[i] ← элемент, созданный правилом вывода Н (602).

2. Обеспечить часть функции образования пар p(A[n _i ]; C[I] (например, левой половины) и D[задержка] (604).

3. Вставить остальную часть функции образования пар (например, правую половину) в положение задержка буфера D (D[задержка]) (606).

4. Обновить значение задержка и установить i←i+1 (608).

5. Если i = Т (610), то A←В,В←С (612), i←0(614).

Конечно, подобные операции можно итерировать и для случая сдвига блоков памяти вправо (например, на этапе 2 обеспечить правую половину, на этапе 3 вставить левую половину и на этапе 5 сдвинуть блоки памяти вправо). Кроме того, последнюю операцию можно эффективно реализовать в одном варианте путем циклического перемещения указателей к трем буферам. Более того, как описано со ссылкой на фиг.2, можно инициализировать блоки памяти А и В (например, случайными значениями или значениями, созданными выходной функцией Н) перед выполнением этапов способа 600.

Соответственно элемент (такой как отдельные знаки или двоичные числа), созданный правилом вывода Н, сохраняется (602). Как описано со ссылкой на фиг.2, можно использовать различные виды запоминающих устройств или сред для сохранения элемента, такие как буфер, регистр, кэш или другие виды памяти. Затем обеспечиваются часть результата функции p образования пар и значение задержки (D[задержка]) (604) (например, значения, сохраненные, по меньшей мере, в двух таких соответствующих блоках памяти как показанные на фиг.3 и 4). Остальная часть функции образования пар вводится в буфер задержки (индексированная задержкой, например, D[задержка] ) (606). Индекс, использованный для индексации блоков памяти и функции образования пар, и индекс для буфера задержки (задержка) обновляются (608).

Если заданный порог не достигнут (610), например, как определено при сравнении обновленного индекса с пороговой величиной, способ 600 возвращается к этапу 602, на котором сохраняется следующий элемент, созданный правилом вывода Н. В противном случае при достижении порога (как определено в 610) блоки памяти циклически перемещаются (например, путем сдвига сохраненных значений влево или вправо) (612). Затем инициализируется индекс (например, на 0) (614), и способ возобновляется на этапе 602, на котором сохраняется следующий элемент, созданный правилом вывода Н. Способ 600 можно выполнять до тех пор, пока не будет сформирован ключевой поток заданной длины.

Правила обновления

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

Ниже описано несколько примерных правил обновления, включая правила, основанные на случайных блужданиях, Т-функциях, линейных регистрах сдвига с обратной связью (ЛРСОС) и словесных поточных шифрах, таких как предполагаемый RC4 (алгоритм шифрования с ключом переменного размера, известный как Ron's Code 4, созданный Роном Ривестом из алгоритма RSA (метод шифрования открытым ключом RSA (Ривеста-Шамира-Адлемана)).

Случайные блуждания по графам-расширителям

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

В одном варианте основные графы предположительно являются ориентированными. Следующие блуждания обычно считаются блужданиями по графам Кейли (Cayley). Обычно граф Кейли на G с генераторами s[1],…,s[n] имеет элементы группы G в качестве узлов и ребра формы (x,x°s[i]).

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

Далее приводится несколько примерных графов, которые можно эффективно реализовать:

Аддитивное блуждание. x:=x+s[i]. Здесь s - таблица случайных элементов в аддитивной группе по модулю 2 ⁿ.

Мультипликативное блуждание. x:=x•s[I]mod2 ⁿ. Здесь s - таблица случайных элементов в мультипликативной группе по модулю 2 ⁿ.

Блуждание Габбера-Галила (Gabber-Galil). Этот граф имеет правило обновления Е, которое можно реализовать со сдвигом и сложением. Поскольку это неориентированные графы, они являются расширителями.

Блуждание Рамануяна (Ramanujan). Эти графы были созданы ЛФС (Любоцки-Филипс-Сарнак (Lubotzky, Phillips, Sarnak)). Они могут быть относительно более сложными для эффективной реализации. Также было доказано, что они являются хорошими расширителями и имеют большой обхват (т.е. логарифмический в размере графа) как неориентированные графы. В одной реализации эти графы используются в качестве ориентированных графов.

Блуждание с перестановками. Графом является S _n, и правило обновления Е переставляет два случайных положения. Известно, что такое блуждание обеспечивает быстрое смешивание. Оно может использоваться в качестве модели для предполагаемого RC4.

Случайные блуждания с динамическими генераторами. Они представляют правило обновления Е для генераторов графа Кейли.

Итерированные Т-функции для обновления состояния

Класс обратимых отображений {0,1} ⁿ →{0,1} ⁿ (называемых Т-функциями) позволяет вводить нелинейность с помощью элементарных операций с регистрами (например, ∧, ∨, ⊕, *, -, , x→-x, □, <<). В одном варианте Т-функции используются для обеспечения функции обновления, частично для относительно более быстрых программных решений.

Примером такой функции является f(x)=x+(x ² ∨ 5) mod 2 ⁿ, для которой последовательность x _i+1 =f(x _i ) будет охватывать всю область в одном цикле. В одном варианте для каждой итерации требуется всего три цикла. Выбор n=64 и выдача верхней половины x_i (т.е. H(x _i )=MSB ₃₂ (x _i )) может дать в результате псевдослучайную последовательность, которая удовлетворяет статистический тестовый набор для кандидатов УСИ (усовершенствованных служб шифрования, AES) с уровнем значимости а = 0,01. Самый лучший известный криптоанализ зависит от использования структуры итерированного вывода и обычно занимает время 2 ^cn, где с - константа. Следовательно, эта структура важна для подтверждения свойств этих функций, и небольшое изменение конструкции может нарушить это свойство. Эти функции позволяют выбирать некоторые параметры произвольно с учетом определенных ограничений. Предполагается, что описанные варианты реализации устойчивы к таким атакам при минимальных непроизводительных затратах и увеличивают длину основного ключа для поточного шифра.

Правила ЛРСОС для обновления состояния и объединение таких генераторов

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

Можно использовать различные конфигурации ЛРСОС, в которых различными способами комбинируются выходные значения, например, генераторы сжатия, тактовые генераторы, генераторы, основанные на алгоритме М (или алгоритме Макларена-Марсалья (MacLaren-Marsaglia)) и/или алгоритме В (или приеме Бейса-Дурама (Bays-Durham)) и т.п. Более подробную информацию относительно ЛРСОС и других основ криптографии можно найти в работе A.Menezes, P.Van Oorschot, S. Vanstone "Handbook of Applied Cryptography" (Справочник по прикладной криптографии), пятое издание (август 2001г.), опубликованной издательством CRC Press.

Словесные поточные шифры на основе S ₂₅₆

Словесные поточные шифры обычно работают на байтовом уровне, например, с использованием компактного представления элемента S₂₅₆ в виде таблицы из 256 элементов. При современном уровне техники расширение до может потребовать использования таблицы неосуществимого размера. В качестве альтернативы табличный код σ∈S₂₅₆ можно расширить в словесную матрицу посредством расширения каждой записи в таблице путем прибавления 24 случайных бит, так что модуль таблицы 256 все еще будет σ. Затем записи в таблице обновляются при сохранении младших байтов с использованием функции f _a,b =ax+b, где сами элементы a,b обновляются с помощью случайных блужданий по и

Аппаратная реализация

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

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

Системная шина 708 представляет одну или более из любых нескольких видов шинных структур, включающих в себя шину памяти или контроллер памяти, периферийную шину, ускоренный графический порт и процессор, или локальную шину с использованием любой из множества шинных архитектур. Например, такие архитектуры могут включать в себя шину промышленной стандартной архитектуры (ISA), шину микроканальной архитектуры (MCA), шину расширенной промышленной стандартной архитектуры (EISA), шину Ассоциации по стандартам видеооборудования (VESA), локальную шину и шину межсоединения периферийных компонентов (PCI), также известную как шина расширения.

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

Системная память 706 содержит машиночитаемую запоминающую среду в форме энергозависимой памяти, такой как оперативное запоминающее устройство (ОЗУ) 710, и/или энергонезависимое запоминающее устройство, такое как постоянное запоминающее устройство (ПЗУ) 712. Базовая система ввода/вывода (BIOS) 714, содержащая базовые стандартные программы, которые способствуют переносу информации между элементами в компьютере 702, например, во время запуска, хранится в ПЗУ 712. ПЗУ 712 обычно содержит данные и/или программные модули, к которым возможен непосредственный доступ и/или с которыми оперирует в настоящий момент процессорный блок 704.

Компьютер 702 может также содержать и другие съемные/несъемные, энергозависимые/энергонезависимые запоминающие среды. Например, на фиг.7 показан накопитель 716 на жестких дисках для считывания и записи на несъемные, энергонезависимые запоминающие среды (не показаны), накопитель 718 на магнитных дисках для считывания и записи на съемные энергонезависимые магнитные диски 720 (например, "флоппи-диски"), и накопитель 722 на оптических дисках для считывания и записи на съемные энергонезависимые оптические диски 724, такие как CD-ROM, DVD-ROM или другие оптические запоминающие среды. Накопитель 716 на жестких дисках, накопитель 718 на магнитных дисках и накопитель 722 на оптических дисках подключены к системной шине 708 через один или более интерфейсов 726 для запоминающих сред. Альтернативно, накопитель 716 на жестких дисках, накопитель 718 на магнитных дисках и накопитель 722 на оптических дисках могут быть подсоединены к системной шине 708 через один или более интерфейсов (не показаны).

Накопители на дисках и связанные с ними машиночитаемые носители обеспечивают энергонезависимое хранение машиночитаемых команд, структур данных, программных модулей и других данных для компьютера 702. Хотя в данном примере показан накопитель 716 на жестких дисках, накопитель 718 на магнитных дисках и накопитель 722 на оптических дисках, понятно, что для реализации примерной вычислительной системы и среды можно также использовать другие типы машиночитаемых запоминающих сред, которые могут хранить данные, доступные для компьютера, например, магнитные кассеты или другие магнитные запоминающие устройства, карты флэш-памяти, CD-ROM, цифровые универсальные диски (DVD) или другие оптические запоминающие средства, оперативные запоминающие устройства (ОЗУ), постоянные запоминающие устройства (ПЗУ), электрически стираемые программируемые постоянные запоминающие устройства (ЭСППЗУ) и т.п.

На жестком диске 716, магнитном диске 718, оптическом диске 722, в ПЗУ 712 и/или ОЗУ 710 можно хранить любое количество программных модулей, включая, например, операционную систему 726, одну или более прикладных программ 728, другие программные модули 730 и программные данные 732. Каждый компонент из группы, включающей в себя операционную систему 726, одну или более прикладных программ 728, другие программные модули 730 и программные данные 732 (или их комбинацию), может реализовать полностью или частично резидентные компоненты, которые поддерживают распределенную файловую систему.

Пользователь может вводить команды и информацию в компьютер 702 через устройства ввода, такие как клавиатура 734 и указательное устройство (например, мышь). Другие устройства ввода 738 (не показаны) могут включать в себя микрофон, джойстик, игровую приставку, спутниковую тарелку, последовательный порт, сканер и/или т.п. Эти и другие устройства ввода подсоединены к процессорному блоку 704 через интерфейсы ввода/вывода 740, которые подсоединены к системной шине 708, но могут быть соединены другими интерфейсными и шинными структурами, такими как параллельный порт, игровой порт или универсальная последовательная шина (USB).

Монитор 742 или другое устройство отображения можно также подключить к системной шине 708 через интерфейс, такой как видеоадаптер 744. В дополнение к монитору 742 другие внешние периферийные устройства могут включать в себя такие компоненты как динамики (не показаны) и принтер 746, которые могут быть подключены к компьютеру 702 через интерфейсы ввода/вывода 740.

Компьютер 702 может работать в сетевой среде с использованием логических соединений с одним или более компьютерами, такими как удаленное вычислительное устройство 748. Например, удаленное вычислительное устройство 748 может быть персональным компьютером, портативным компьютером, сервером, маршрутизатором, сетевым компьютером, одноранговым устройством или другим обычным сетевым узлом, игровым пультом и т.п. Удаленное вычислительное устройство 748 показано в виде портативного компьютера, который может включать в себя множество или все элементы и признаки, описанные в отношении компьютера 702.

Логические соединения между компьютером 702 и удаленным компьютером 748 изображены в виде локальной вычислительной сети (ЛВС) 750 и глобальной вычислительной сети (ГВС) 752. Такие сетевые среды обычно используются в учреждениях, на предприятиях, интранет и Интернет.

При реализации в сетевой среде ЛВС компьютер 702 подключен к локальной сети 750 через сетевой интерфейс или адаптер 754. При реализации в среде ГВС компьютер 702 обычно содержит модем 756 или другое средство для установления связи через глобальную сеть 752. Модем 756, который может быть встроенным в компьютер 702 или внешним, можно подключить к системной шине 708 через интерфейсы ввода/вывода 740, или другие соответствующие механизмы. Понятно, что проиллюстрированные сетевые соединения являются примерными, и что можно использовать также другие средства установления линий связи между компьютерами 702 и 748.

В такой сетевой среде, как показана с вычислительной средой 700, программные модули, изображенные с компьютером 702, или их части могут храниться в удаленном запоминающем устройстве. Например, удаленные прикладные программы 758 находятся в запоминающем устройстве удаленного компьютера 748. В целях иллюстрации прикладные программы и другие выполняемые программные компоненты, такие как операционная система, проиллюстрированы в виде отдельных блоков, хотя понятно, что такие программы и компоненты могут находиться в разное время в разных компонентах памяти в вычислительном устройстве 702 и исполняться процессором данных компьютера.

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

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

"Компьютерная запоминающая среда" включает в себя энергозависимые и энергонезависимые, съемные и несъемные запоминающие среды, реализованные с помощью любого метода или технологии, для хранения такой информации как машиночитаемые команды, структуры данных, программные модули или другие данные. Компьютерная запоминающая среда включает в себя, без ограничения перечисленным, ОЗУ, ПЗУ, ЭСППЗУ, флэш-память или другую технологию памяти, CD-ROM, цифровые универсальные диски (DVD) или другие оптические запоминающие среды, магнитные кассеты, магнитную ленту, магнитные диски или другие магнитные запоминающие устройства, или любые другие запоминающие среды, которые можно использовать для хранения требуемой информации и к которым возможен доступ компьютера.

"Коммуникационная среда" обычно включает в себя машиночитаемые команды, структуры данных, программные модули или другие данные в модулированном сигнале данных, таком как несущая волна или другой транспортный механизм. Коммуникационная среда также включает в себя любую среду для доставки информации. Термин "модулированный сигнал данных" означает сигнал, одна или несколько характеристик которого установлены или изменяются таким образом, чтобы закодировать информацию в сигнале. Например, без ограничения указанным, коммуникационная среда включает в себя проводную среду, такую как проводная сеть или прямое проводное соединение, и беспроводную среду, например, акустическую, радиочастотную (РЧ), инфракрасную (ИК), беспроводную среду Wireless Fidelity (например, стандарт беспроводной сетевой связи IEEE 802.11b, или Wi-Fi), сотовую среду, беспроводную среду Bluetooth, а также другие беспроводные среды. Комбинации перечисленных выше сред также подпадают под объем понятия машиночитаемой среды.

Заключение

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

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

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

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

3. Способ по п.1, в котором первый, второй и третий блоки памяти реализованы в одном запоминающем устройстве.

4. Способ по п.1, в котором результаты фунции образования пар сохраняют в таблице.

5. Способ по п.1, в котором только первый и третий блоки памяти активны в любой данный момент времени.

6. Способ по п.1, в котором первый и третий блоки памяти инициализируют случайными величинами.

7. Способ по п.1, который применяют рекурсивно.

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

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

10. Способ по п.1, в котором дополнительно усиливают функцию образования пар посредством применения четвертого блока памяти.

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

12. Способ по п.11, в котором секретная перестановка медленно видоизменяется.

13. Способ по п.10, в котором четвертый блок памяти инициализируют случайными величинами.

14. Способ по п.10, в котором четвертый блок памяти инициализируют случайными величинами и переменной задержкой.

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