Способ генерации гаммы, используемый при поточном шифровании
METHOD FOR GAMMA GENERATION, USED IN STREAM ENCRYPTION

Настоящее изобретение относится, к криптографии, в частности к
вычислению гаммы при поточном шифровании.
С широким распространением цифровой связи возрастает потребность в защите соответствующих каналов связи. Например, современные технологии позволяют пользователям осуществлять дистанционный доступ к банковским счетам, медицинским данным и другой конфиденциальной и секретной информации.
В настоящее время в симметричном шифровании широко используются два вида шифров – блочный и поточный. Блочный шифр оперирует с большим блоком данных. Поточный шифр, с другой стороны, оперирует  с относительно малыми элементами текста (такими как биты, байты). Поточные шифры могут работать гораздо быстрее, чем блочные шифры.
i
i
i
i
Алгоритмы поточного шифрования, в отличие от блочного шифрования выполняют преобразование информации  в текущий момент времени i, поступающей от источника сообщений X , по одному биту путём сложения  Xпо модулю два  со значением k,  вырабатываемым генератором гаммы, и  также имеющим значение один бит. Генератор гаммы как на стороне отправителя сообщения, так и на стороне получателя сообщения вырабатывает одинаковую последовательность нулей и единиц- гамму k. Поточный шифр устраняет необходимость разбивать исходное сообщение (открытый текст) на  блоки одинаковой длины по 64 бит или по 128 бит,как это делается в алгоритмах блочного шифрования, таких как DES или AES.Следовательно, поточный шифр может работать в реальном времени и при передаче  сообщения, представленного в виде последовательности  цифр в двоичном коде, то есть в виде нулей и единиц,каждая цифра может шифроваться и передаваться мгновенно.
1
2
n
При использовании  гаммирования, ключом является последовательность чисел-гамма, то есть  последовательность битов k, k,..., k с которой производится сложение открытого текста.
i
В настоящее время для выработки гаммы применяются: линейный конгруэнтный генератор псевдослучайных чисел, метод Фибоначчи с запаздыванием, генератор псевдослучайных чисел на основе алгоритма BBS, отдельные режимы работы алгоритма DES,алгоритм RC4,или аналогичные шифры, которые вырабатывают  последовательность чисел k.
n
n
Способ поточного шифрования с использованием алгоритма RC4 (Рябко Б.Я., Фионов А.Н., Криптография в информационном мире, стр.201-203,-М.: Горячая линия-Телеком, 2018г, -300с.ил)  является ближайшим к данному изобретению.RC4 относится к  классу алгоритмов, определяемых размером его блока или слова – параметром n[1]. Внутреннее состояние RC4 состоит из последовательности чисел размером 2 слов, при  n=4 количество чисел  данной последовательности равено-16 и может быть записано в десятичной форме - 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 и двух счетчиков  - i-й и j-й счётчики, оба при n=4 являются 4-битовыми. Все вычисления проводятся по модулю 2,  то есть при n=4-это означает, что вычисления будут проводиться по модулю 16.
-
таблица
S-бокс)
таблица
4
n
n
В RC4последовательность чисел используется как  замен (, и обозначается как S и при n=4 массив Sбудет состоять из 2=16 элементов, как отмечено выше, то есть из чисел 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15. В каждый момент времени  S содержит все возможные n-битовые (в нашем случае 4-битовые) числа  от 0 до 15 в перемешанном виде. Конкретная перестановка значений в таблице определяется ключом К, который представляет – произвольный набор чисел. Если длина ключа меньше чем 2 , а в данном случае меньше чем 16, то ключ повторяется несколько раз, пока количество цифр в ключе не будет равно 2.После того как все числа будут перемешаны  закончится этап №1, а на втором этапе производится выборка псевдослучайного слова (числа).
значение
№2
i
Для этого счетчикам i и j присваивается начальное  ноль. Затем для получения каждого нового значения z выполняются следующие действия (этап  ):
i = (i + 1) mod 16;
i
j = (j + S) mod 16;
i
j
поменять местами S и S;
i
j
t = (S + S) mod 16;
i
t
z = S.
i
i
i
i
i
Значение z  вычисляется в десятичной форме записи, то есть как одно из чисел в диапазоне от 0 до 15.Для получения гаммы, то есть k, вычисляемые на каждом шаге последовательности чисел zзаписываем в двоичном виде и суммируются побитно по модулю два с открытым текстом x. В результате получается зашифрованное значениеy.
При использовании в известном способе поточного шифрования алгоритма RC4, которое происходит в два этапа, нет возможности оперативно менять гамму, так как надо менять ключ-матрицу К, кроме того для перемешивания матрицы состояния необходимо использовать два счетчика (i и j) на первом этапе, и использовать программу выборки чисел на втором этапе.
Задачей на которую направлено данное изобретение, является  улучшение качества шифрования, за счёт вычисления новой вспомогательной матрицы – ключа KQ (или выборки её из библиотеки) в каждом новом цикле шифрования.
Техническим результатом изобретения является сокращение временных затрат на шифрование исходного (открытого) текста и улучшение качества шифрования за счёт  вычисления новой вспомогательной матрицы – ключа KQ (или выборки её из библиотеки) в каждом новом цикле шифрования.
Кроме того, данный способ позволяет менять вспомогательную матрицу – ключ  KQ с помощью матричных вычислений и таким образом,  улучшается качество шифрования.
Для достижения названного технического результата в предлагаемом способе генерации гаммы, используемом при поточном шифровании:
создают матрицу состояния SQ;
производят вычисление вспомогательной матрицы-ключа  KQ, значение матрицы-ключа  KQ можно вычислять заранее и хранить в библиотеке, как на стороне получателя, так и на стороне  отправителя информации;
производят  вычисление результирующей матрицы состояний SQL путем выполнения арифметических действий с матрицами SQ  и KQ;
используют счетчик  элементов результирующей матрицы состояний SQL, для  организации нового цикла вычислений путём вычисления новой матрицы KQ или использования матрицыKQ из библиотеки;
формируют последовательность Ki, путем перевода чисел результирующей матрицы состояний SQL из десятичной системы счисления в двоичную.
n
Вычисление результирующей матрицы SQL осуществляют путем сложения матрицы состояний SQ и матрицы-ключа KQ по модулю 2.
n
Вычисление результирующей матрицы SQL осуществляют путем сложения матрицы состояний SQ и транспонированной матрицы-ключа KQ по модулю 2.
n
Вычисление результирующей матрицы SQL осуществляют путем перемножения матрицы состояний SQ на матрицу-ключ KQ, по модулю 2.
n
n
Вычисление результирующей матрицы SQL осуществляют  путём сложения матрицы состояний SQ с матрицей-ключом KQ, умноженной на постоянное число  1 <µ <2 -1, по модулю 2.
ij
В предлагаемом способе генерации гаммы, состоящем из циклов - в каждом цикле  используют матричный подход к построению как матрицы состояния SQ (аналог матрицы S), так и вспомогательной матрицы КQ, которая является аналогом ключа К  в  RC4 и вычисляется результирующая матрица SQL в результате  матричных преобразований над матрицами SQ и KQ. Элементы результирующей матрицы SQL формируют последовательность Ki, путем перевода чисел результирующей матрицы состояний SQL из десятичной системы счисления в двоичную.
В матричном подходе определяющим параметром является размер матрицы N, который может быть выражен через n, внутреннее состояние  и  определяется квадратной  матрицей SQ размером N*N, где
2
n
n\2
N = 2 или  N= 2, (1)
то есть при n=4 N=4, при n=8 N=16, при n=10 N=32 и т.д.
Квадратная матрица SQ, используется как таблица замен S (S-бокс) в  RC4. В начальный момент времени матрица SQ также как и таблица замен S содержит все возможные n-битовые числа, записанные  либо по порядку, либо в перемешенном виде, то есть записанные в соответствии с заранее согласованной (между отправителем и получателем) последовательности.
Матричный алгоритм состоит из двух этапов. На первом, подготовительном этапе производится инициализация матрицы состояния SQ и вычисление вспомогательной матрицы КQ, которая является аналогом ключа К в RC4, по формуле
n
КQ=  L*Mmod2, (2),
n
где L - матрица порядка N*1, а M порядка 1*N, причём числа входящие в данные матрицы выбираются произвольным образом из чисел, входящих в  матрицу состояния SQ, а элементы вспомогательной матрицы КQ вычисляются  по модулю 2.
n
n
n
На втором, основном этапе вычисляется по модулю 2 матрица SQL по формуле SQL = (SQ +KQ)mod2илиSQL =(SQ *KQ)mod2(3)
и производится выборка чисел, которыми будут являться элементы данной матрицы SQL, то есть SQLij - это числа, переведённые из десятичной системы счисления в двоичную систему счисления, и будут  числами ki.
Матрицы SQL, SQ и KQ  имеют одинаковый порядок, и представляют собой квадратные матрицы размера N*N.
4
n
4
Рассмотрим принцип работы матричного подхода при n=4. В этом случае количество всех чисел, входящих в массив S или в матрицу состояния SQ будет равно 2= 16, а сами числа будут находиться в диапазоне от 0 до 15. Тогда N, вычисляемое по формуле (1) будет равно 4 и матрица SQ может быть представлена, в матричном виде как квадратная матрица размером N*N = 4*4. В дальнейшем для упрощения понятия принципа работы матричного подхода в матрицу состояния SQ запишем числа от 0 до 15 по порядку, хотя их порядок может быть изменён - по согласованию, между отправителем и получателем информации. Так как n=4 то все вычисления будут производиться по модулю 2 = 2 =16.
С учётом этого на первом этапе вычислений матрица состояния SQ может быть представлена, в следующем виде:
Так как вспомогательная  матрица КQ вычисляется по формуле (2), то есть:
n
КQ=  L*Mmod2,
то заметим, что вычисление значений матрицы КQ производится с применением двух матриц- L (N*1) и М(1*N), и числа, входящие в данные матрицы, могут выбираться произвольным образом из чисел, входящих в  матрицу состояния SQ, как было указано ранее. Для простоты и наглядности вычислений примем, что матрица М равна транспонированной матрице L, а в качестве произвольных чисел выберем значения 1,2,3,4.
Тогда вспомогательная матрица КQ вычисляется по модулю 16 следующим образом
Значение результирующей матрицы SQL вычисляется в соответствии с уравнением (3) - суммируя матрицы SQ и КQ по модулю 16,получим
Выборка чисел, для применения в поточном шифровании в качестве гаммы, может быть произведена любым способом, как по порядку (первая строка, вторая и т.д.), так и начиная с последнего элемента данной таблицы к первому, а после этого производится перевод перевода выбранных чисел из десятичной в двоичную систему счисления.
Данный матричный подход даёт возможность применения различных вариантов для дальнейших вычислений результирующей матрицы SQL и её составляющих,  таких как матрица  состояния SQ,  и вспомогательная матрица КQ.
Например, можно получить новое значение результирующей матрицы SQL как результат произведения матриц SQ и КQ, то есть
*
SQL = SQКQ, (4),
учитывая, что все вычисления производятся по модулю  16 , как в рассмотренном выше примере.
Применительно к вспомогательной матрице КQ для получения новых значений также возможны следующие варианты:
во-первых, возможно преобразовать вспомогательную матрицу КQ с помощью выбора  новых чисел(произвольных) в матрицах L, M или например, можно выбрать в качестве матрицы L- i-ый столбец матрицы состояния SQ, а в качестве матрицы М- j-ую строку матрицы SQ;
во-вторых, сдвинув «старые» элементы матриц L, М на определённое число позиций (одинаковое или разное выбранное по заранее согласованному алгоритму) и получить в результате их перемножения новое значение вспомогательной матрицы КQ;
n
n
в-третьих, можно ввести новый элемент – число µ, где  µ - скалярная величина, находящаяся в диапазоне 1 < µ ≤ 2-1 и умножить вспомогательную матрицу КQ, полученную на предыдущем этапе вычислений на µ- в результате чего все элементы вспомогательной матрицы KQ будут умножены на данный коэффициент и после применения к ним операции вычисления по  модулю 2, в результате будет получено новое значение вспомогательной матрицы КQ на новом этапе вычислений;
в-четвёртых, для вычисления результирующей матрицы SQL можно использовать транспонированное значение вспомогательной матрицы KQ.
ij
i
После этих преобразований, учитывая полученное обновлённое значение вспомогательной матрицы КQ, можно вычислить  новое значение результирующей матрицы SQL, элементы которой, то есть числа SQL в двоичной форме записи могут быть использованы как числа k .Предлагаемый матричный подход может использоваться для получения последовательности псевдослучайных чисел(гамма)  в поточном  шифровании.
Предлагаемый способ поясняется чертежами, на которых показаны:
Фиг.1 – Схема работы поточного шифра
i
Фиг.2 - Блок-схема операций способа генерации гаммы – k.
Способ  состоит из циклов и осуществляется следующим образом.
n
n
n
n
ij
00,
01
n-1 n-1
ij
i
i
i.
Цикл работы состоит из нескольких этапов. На первом этапе производится инициализация матрицы состояния SQ (блок №1), то есть запись чисел в данную матрицу (блок №1), например от 0 до 15, если n=4 или от 0 до 255, если n=8, или от 0 до 1023 если n=10 и т.д.  Так как матричный подход даёт возможность построения матрицы ключа различными способами по модулю 2 (например, перемножением i-ого столбца на j-ую строку или умножением полученного результата на константу 1<µ<2-1, транспонированием полученного результата или выборки из библиотек и т.д.), то на втором этапе происходит выбор варианта построения вспомогательной матрицы ключа KQ (блок №2). На третьем этапе происходит вычисление вспомогательной матрицы ключа KQ (блок №3) для выбранного варианта. На данном этапе также возможно использование  вспомогательной матрицы KQ из библиотеки, содержащей заранее вычисленные значения данной матрицы. Результат этого  этапа поступает, на первый вход блока № 4, на второй вход которого поступают  элементы матрицы состояний SQ и на выходе блока № 4 получается результирующая матрица SQL. Элементы результирующей  матрицы, то есть числа SQL , где ( i, j = 0….2-1), выбранные, например, по порядку то есть sqlsql…sqlпоступают на вход блоков № 5 и № 6. Блок № 5 является счётчиком и после подсчёта количества чисел матрицы SQL, где ( i, j = 0….2-1) начинает новый цикл шифрования путём  вычисления новой вспомогательной матрицы KQ или взятия её из библиотеки матриц KQ, в блоке № 6 данные числа переводятся из десятичной системы счисления в двоичную и формируют последовательность K (гамму), которая складывается с открытым текстом X и образует зашифрованный текст Y
n
осле того как будут выбраны все числа результирующей матрицы SQL, по команде от счётчика (блок № 5), можно будет  изменить вспомогательную матрицу KQ, например, умножить полученный результат - вспомогательную матрицу KQ на константу 1<µ<2-1или транспонировать её и сложить с матрицей состояния SQ, или перемножить матрицы SQL и KQ, и кроме того можно использовать заранее вычисленные значения вспомогательной матрицы ключа KQ, находящиеся в библиотеке, а после этого повторить весь цикл заново.
С учетом того, что перемешивание чисел в результирующей матрице SQL производится за счёт матричных преобразований, нет необходимости в использовании i-го и j-го счётчиков и в применении специальной программы выборки чисел, а оперативное изменение вспомогательной матрицы ключа KQ, затруднит дешифрование текста для противника.