СПОСОБ ПОТОЧНОГО ШИФРОВАНИЯ ДАННЫХ Российский патент 2011 года по МПК H04L9/00 

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

Известны способы поточного шифрования данных (см., например, Российский стандарт шифрования стандарт СССР ГОСТ 28147-89 [1], Британский алгоритм B-Grypt, Стандарт США DES, Японский алгоритм шифрования данных FEAL [2], стр.48-52, а также патент Российской Федерации на изобретение №2239290 кл. 7 H04L 9/00, Н04К 1/06 [3]).

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

Однако известные способы-аналоги поточного шифрования данных [1, 2] имеют недостаток. Несмотря на то, что шифр, основанный на сложении потока псевдослучайных битов с битами исходного текста по модулю 2, является в общем случае теоретически нераспознаваемым (см. [2], стр.128), сама криптосистема не отличается стойкостью и может быть раскрыта. Если структура регистра сдвига, имеющего n-разрядов известна, то для нахождения начального состояния регистра сдвига надо знать n символов известного открытого текста, которые складываются по модулю 2 с соответствующими n-символами шифртекста. Полученные n-символов псевдослучайной последовательности определяют состояние регистра сдвига на некоторый момент времени. Моделируя работу регистра сдвига в обратном направлении, можно определить его исходное состояние, а следовательно, и ключи, используемые пользователями сети при шифровании-дешифровании информации.

Если структура регистра сдвига, имеющего n-разрядов, является неизвестной, то достаточно 2n-символов известного открытого текста и им соответствующих 2n-символов шифрованного текста, чтобы сравнительно быстро (в течение нескольких секунд работы ЭВМ) определить состояние регистра сдвига и вычислить используемые ключи (см., например, [4] стр.93). А это приводит к снижению стойкости шифра к атакам на основе известных и подобранных исходных текстов.

Наиболее близким по совокупности признаков к заявляемому способу является способ, описанный в [5]. Способ заключается в том, что формируют ключ шифрования в виде двоичного вектора длиною n бит, подают его для начального заполнения регистра сдвига с обратной связью, имеющего n разрядов и вырабатывающего псевдослучайную последовательность максимальной длины, содержащую 2ⁿ-1 двоичных символов, формируют псевдослучайные последовательности символов аддитивной и мультипликативной группы кольца класса вычетов по модулю р=2^k, при этом псевдослучайные последовательности символов аддитивной группы кольца класса вычетов по модулю р формируют в виде двоичных векторов длиною k бит путем снятия информации с k различных разрядов регистра сдвига, а псевдослучайные последовательности символов мультипликативной группы кольца класса вычетов по модулю р=2^k формируют в виде двоичных векторов длиною k бит путем использования символа "1" в нулевом разряде двоичного вектора, а для остальных разрядов двоичного вектора используют символы, снимаемые с k-1 различных разрядов регистра сдвига, делят поток данных на блоки-символы в виде двоичных векторов длиною k бит, поочередно преобразуют блоки-символы в зашифрованное сообщение путем использования операции сложения символов в кольце класса вычетов по модулю р применительно к символам псевдослучайной последовательности аддитивной группы кольца и операции умножения символов в кольце класса вычетов по модулю р применительно к символам псевдослучайной последовательности мультипликативной группы кольца и передают зашифрованные сообщения по линии связи.

Однако способ-прототип имеет недостаток.

Статистический анализ экспериментальных данных, полученных во время работы макета, реализующего данный способ, показывает, что при k=16 время корреляции [6] приближенно равно 4,4 символа. Это означает, что генерируемые символы достаточно долго сохраняют "память" о предыдущих сгенерированных символах [6], то есть существует возможность проследить информационную связь между сгенерированными символами шифрующей последовательности. Кроме того, способ [5] построен на основе псевдослучайной последовательности максимальной длины 2ⁿ-1, то есть передав все 2ⁿ-1 символов шифрующей последовательности, генератор начнет передавать их сначала. Следовательно, при перехвате достаточного количества сгенерированных символов шифрующей последовательности злоумышленник будет обладать достаточными знаниями для осуществления атаки на криптографический алгоритм, например для уменьшения набора ключей при осуществлении атаки полным перебором ключей шифрования. Значит, время вскрытия алгоритма шифрования и получения ключа шифрования может быть уменьшено относительно времени, указанного в [5].

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

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

Указанный технический результат достигается тем, что в известном способе поточного шифрования данных, заключающемся в формировании ключа шифрования в виде двоичного вектора длиною n бит, подаче его для начального заполнения регистра сдвига с обратной связью, имеющего n разрядов и вырабатывающего псевдослучайную последовательность максимальной длины, содержащую 2ⁿ-1 двоичных символов, формировании псевдослучайных последовательностей символов аддитивной и мультипликативной группы кольца класса вычетов по модулю p=2^k, при этом псевдослучайные последовательности символов аддитивной группы кольца класса вычетов по модулю р формируют в виде двоичных векторов длиною k бит путем снятия информации с k различных разрядов регистра сдвига, а псевдослучайные последовательности символов мультипликативной группы кольца класса вычетов по модулю р=2^k формируют в виде двоичных векторов длиною k бит путем использования символа "1" в нулевом разряде двоичного вектора, а для остальных разрядов двоичного вектора используют символы, снимаемые с k-1 различных разрядов регистра сдвига, деления потока данных на блоки-символы в виде двоичных векторов длиною k бит, поочередном преобразовании блоков-символов в зашифрованное сообщение путем использования операции сложения символов в кольце класса вычетов по модулю р применительно к символам псевдослучайной последовательности аддитивной группы кольца и операции умножения символов в кольце класса вычетов по модулю р применительно к символам псевдослучайной последовательности мультипликативной группы кольца и передаче зашифрованного сообщения по линии связи, согласно изобретению дополнительно формируют последовательность символов, представляющую собой детерминированный хаос, в виде двоичных векторов длиною k бит и преобразуют зашифрованные блоки-символы в виде двоичных векторов длиною k бит путем побитного сложения по модулю два с двоичными векторами символов дополнительно сформированной последовательности символов, являющейся детерминированным хаосом.

Эти отличительные признаки по сравнению с прототипом позволяют сделать вывод о соответствии заявляемого технического решения критерию "новизна".

Сущность изобретения заключается в следующем.

Для исключения периодичности из генерируемой шифрующей последовательности складывают не с дополнительно сформированной псевдослучайной последовательностью символов максимальной длины (М-последовательность), как это предлагается в прототипе, а с последовательностью символов, представляющей собой детерминированный хаос [7, с.41-53]. Последовательность символов, представляющая собой детерминированный хаос, является непериодической. По своим свойствам последовательность символов, представляющая собой детерминированный хаос, более случайна, чем последовательность символов, генерируемая стандартными генераторами псевдослучайных последовательностей. Данный факт, например, отмечен в [8, стр.337] для последовательности цифр числа Пи (π), порождаемой нелинейной динамической системой итерированных функций. Следовательно, сложение с последовательностью символов, представляющей собой детерминированный хаос, уменьшает количество информационных связей между символами результирующей генерируемой шифрующей последовательности. В результате проведенного корреляционного анализа данных, полученных экспериментальным путем, установлено, что при k=16 время корреляции [6, стр.6-7] приближенно равно 1 символу, то есть автокорреляционная функция результирующей генерируемой шифрующей последовательности по виду близка к дельта-функции, следовательно, спектральные характеристики результирующей последовательности близки к характеристикам белого шума [6, стр.172-180] - абсолютно непредсказуемого случайного процесса. Для существенного затруднения детектирования последовательности символов, представляющей собой детерминированный хаос, можно использовать ключ шифрования при задании начальных условий ее формирования.

В совокупности признаков заявленного способа используется следующая терминология и обозначения:

секретный ключ (или пароль) представляет из себя комбинацию битов, известную только законному пользователю;

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

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

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

дешифрование - процесс, обратный процедуре шифрования; дешифрование обеспечивает восстановление информации по криптограмме при знании шифр-ключа;

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

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

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

Возможность технической реализации заявленного способа поточного шифрования данных поясняется следующим образом. Формирование последовательности символов, представляющей собой детерминированный хаос, можно осуществлять путем использования нелинейной динамической системы, например генератора Анищенко-Астахова [7, с.83-98] или системы, построенной на основе итерированных алгоритмов с большим числом учитываемых десятичных знаков, например, на основе алгоритма вычисления числа Пи [8, с.336-338].

Предлагаемый способ может быть реализован с помощью ЭВМ или вычислительного устройства.

На фиг.1 представлена структурная схема устройства, где блок 1 - устройство формирования ключа шифрования; блок 2 - регистр сдвига; блок 3 - шифрующее устройство; блок 4 - передающее устройство; блок 5 - генератор последовательности символов, представляющей собой детерминированный хаос;

блок 6 - поразрядный сумматор по модулю 2.

На фиг.2 представлена структурная схема генератора последовательности символов, представляющей собой детерминированный хаос, построенного на основе числа Пи, где блок 7 - блок формирования числа Пи; блок 8 - блок хранения нечетных символов; блок 9 - блок хранения четных символов; блок 10 - сумматор по модулю 16; блок 11 - управляющий блок.

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

z_i=z_2i+z_2i(mod 16).

В блок 7 из блока 1 поступает секретный номер начального символа генерируемой последовательности, представляющей собой детерминированный хаос, s=2. Поток нечетных символов числа Пи (3,1415926535897932384626433832795) из блока 7, начиная со второго, поступает в блок 8:

v=4, 5, 2, 5, 5, 9, 9, 2, 8, 6, 6, 3, 8, 2, 9,

поток четных символов числа Пи - в блок 9

w=1, 9, 6, 3, 8, 7, 3, 3, 4, 2, 4, 3, 3, 7, 5,

после чего в блоке 10 производят суммирование пар символов vi и wi по модулю 16:

z=5, 14, 8, 8, 13, 0, 12, 5, 12, 8, 10, 6, 11, 9, 14,

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

β=2, 10, 8, 15, 9, 3, 15, 9, 0, 1, 5, 11, 1, 2, 10,

поступающим из устройства 3, в соответствии с выбранным криптографическим преобразованием γ=β⊕z в двоичной системе счисления:

β=10, 1010, 1000, 1111, 1001, 11, 1111, 1001,0, 1, 101, 1011, 1, 10, 1010

z=101, 1110, 1000, 1000, 1101, 0, 1100, 101, 1100, 1000, 1010, 110, 1011, 1001, 1110

γ=111, 100,0, 111, 100, 11, 11, 1100, 1100, 1001, 1111, 1101, 1010, 1011, 100

Полученная последовательность:

γ=7, 8, 0, 7, 6, 3, 11, 14, 12, 9, 15, 1, 12, 11, 8

поступает на вход передающего устройства 4.

На приемном конце линии связи осуществляют выделение зашифрованной последовательности β^* в соответствии с установленным криптографическим преобразованием β^*=γ⊕z в двоичной системе счисления:

γ=111, 100,0, 111, 100, 11, 11, 1100, 1100, 1001, 1111, 1101, 1010, 1011, 100

z=101, 1110, 1000, 1000, 1101,0, 1100, 101, 1100, 1000, 1010, 110, 1011, 1001, 1110

β^*=10, 1010, 1000, 1111, 1001, 11, 1111, 1001, 0, 1, 101, 1011,1,10,1010.

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

Реализация предлагаемого способа не вызывает затруднений, так как все блоки и узлы, входящие в устройство, реализующее способ, общеизвестны и широко описаны в технической литературе [7-17]. Генератор последовательности символов, представляющей собой детерминированный хаос, например, может быть реализован в виде генератора Анищенко-Астахова [7, с.83-98] или системы, построенной на основе итерированных алгоритмов с большим числом учитываемых десятичных знаков, например, на основе алгоритма вычисления числа Пи [8, с.336-338], блок формирования числа Пи, например, может быть реализован в виде специализированного устройства на микроконтроллере по принципам и методам, описанным в [8, с.336-338, 9-14], блоки хранения четных и нечетных символов - на базе любого машиночитаемого носителя информации [15, 16], сумматор по модулю 16 и управляющий блок - на базе стандартных цифровых логических микросхем, взаимное соединение блоков и подсоединение к блокам прототипа может быть осуществлено по стандартным схемам подключения устройств [17].

Источники информации

1. Российский стандарт шифрования стандарт СССР. ГОСТ 28147-89 Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования.

2. Мафтик С. Механизмы защиты в сетях ЭВМ. М., 1993 г.

3. Способ поточного шифрования данных. Патент на изобретение №2239290 по заявке №2001135708 от 24.02.2001 г.

4. Тупота В.И. Адаптивные средства защиты информации в вычислительных сетях. - М.: Радио и связь, 2002 г.

5. Способ поточного шифрования данных. Патент на изобретение №2291578 от 10.01.2007.

6. Павлов А.Н. Методы анализа сложных сигналов: Учеб. пособие для студ. физ. фак. / А.Н.Павлов. - Саратов: Научная книга, 2008. - 120 с.: ил.

7. Анищенко B.C. Знакомство с нелинейной динамикой. Лекции Соросовского профессора. Изд. 3-е перераб. и доп., 2008 г.

8. Шредер М. Фракталы, хаос, степенные законы. Миниатюры из бесконечного рая. - Ижевск: НИЦ "Регулярная и хаотическая динамика", 2001, 528 стр.

9. Нечаев И.А. Конструкции на логических элементах цифровых микросхем. - Москва.: Радио и связь, 1992. - 123 с.

10.Белов А.В. Создаем устройства на микроконтроллерах. - СПб.: Наука и техника, 2007. - 304 с.

11. Конструкторско-технологическое проектирование электронной аппаратуры. Учебник для вузов. Серия: Информатика в техническом университете. Под ред. Шахнова В.А. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2003. - 528 с.: ил.

12. Суворова Е., Шейнин Ю. Проектирование цифровых систем на VHDL. Серия "Учебное пособие". - СПб.: БХВ-Петербург, 2003. - 576 с.: ил.

13. Овчинников В.А. Алгоритмизация комбинаторно-оптимизационных задач при проектировании ЭВМ и систем. Серия: Информатика в техническом университете. - М.: Изд-во МГТУ им.Н.Э.Баумана, 2001. -288 с.: ил.

14. Новиков Ю.В. Основы цифровой схемотехники. Базовые элементы и схемы. Методы проектирования. - М.: Мир, 2001. - 379 с.

15. Левин В.И. Носители информации в цифровом веке / Под общ. ред. Д.Г.Красковского. - М.: КомпьютерПресс, 2000. - 256 с.: ил.

16. Гук М. Дисковая подсистема ПК. - СПб.: Питер, 2001. - 336 с.: ил.

17. Пей Ан. Сопряжение ПК с внешними устройствами. - М.: ДМК Пресс, 2003. - 320 с. ил.

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

Способ поточного шифрования данных, заключающийся в формировании ключа шифрования в виде двоичного вектора длиною n бит, подаче его для начального заполнения регистра сдвига с обратной связью, имеющего n разрядов и вырабатывающего псевдослучайную последовательность максимальной длины, содержащую 2ⁿ-1 двоичных символов, формировании псевдослучайных последовательностей символов аддитивной и мультипликативной группы кольца класса вычетов по модулю р=2^k, при этом псевдослучайные последовательности символов аддитивной группы кольца класса вычетов по модулю р формируют в виде двоичных векторов длиною k бит путем снятия информации с k различных разрядов регистра сдвига, а псевдослучайные последовательности символов мультипликативной группы кольца класса вычетов по модулю р=2^k формируют в виде двоичных векторов длиною k бит путем использования символа "1" в нулевом разряде двоичного вектора, а для остальных разрядов двоичного вектора используют символы, снимаемые с k-1 различных разрядов регистра сдвига, деления потока данных на блоки-символы в виде двоичных векторов длиною k бит, поочередном преобразовании блоков-символов в зашифрованное сообщение путем использования операции сложения символов в кольце класса вычетов по модулю р применительно к символам псевдослучайной последовательности аддитивной группы кольца и операции умножения символов в кольце класса вычетов по модулю р применительно к символам псевдослучайной последовательности мультипликативной группы кольца и передаче зашифрованного сообщения по линии связи, отличающийся тем, что дополнительно формируют последовательность символов, представляющую собой детерминированный хаос, в виде двоичных векторов длиною k бит и преобразуют зашифрованные блоки-символы в виде двоичных векторов длиною k бит путем побитного сложения по модулю два с двоичными векторами символов дополнительно сформированной последовательности символов, являющейся детерминированным хаосом.