Результат интеллектуальной деятельности: СПОСОБ АРИФМЕТИЧЕСКОГО КОДИРОВАНИЯ С ШИФРОВАНИЕМ

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

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

Известны способы шифрования двоичной информации, описанные, например, в государственном стандарте 28147-89. Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования. - М.: Госстандарт СССР. 1989, стр. 9-14. В данных способах у отправителя двоичную последовательность (ДП) разделяют у отправителя на последовательные блоки длиной n бит, где обычно n=64. По криптографической функции с использованием заранее сформированного для отправителя и получателя секретного ключа (СК) последовательно из каждого блока ДП с учетом предыдущего зашифрованного блока формируют зашифрованный текущий блок до тех пор, пока поступают блоки ДП. Зашифрованные текущие блоки передают по каналу связи получателю. Принятые получателем зашифрованные текущие блоки по криптографической функции с использованием СК последовательно расшифровывают с учетом предыдущего зашифрованного принятого блока до тех пор, пока поступают зашифрованные блоки.

Недостатками указанных аналогов являются:

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

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

Известен также способ арифметического кодирования с шифрованием по патенту РФ 2226041 МПК Н04L 9/08 (2006.01) от 01.11.2001. Данный способ заключается в том, что на передающей стороне исходная информация искажается с помощью ключевой последовательности, а на приемной стороне искаженная информация восстанавливается с помощью ключевой последовательности с посимвольной обработкой, отличающийся тем, что входные двоичные данные разбивают на блоки фиксированной длины и кодируют поочередно, подвергая их преобразованию методом арифметического кодирования с криптографическими функциями F₁, F₂ и F₃, зависящими от указанной ключевой последовательности, в качестве криптографического преобразования F₂ и F₃ выбирают псевдослучайные функции, на каждом шаге кодирования вводят данные для арифметического кодирования посимвольно и кодируют их с использованием таблицы символов, реализующих преобразование F₂ и таблицы интервалов вероятности появления символов, реализующих преобразование F₃, на каждом шаге кодирования обновляют таблицу символов путем извлечения из нее N ее первых значений, разбивают их на пары, переставляют местами извлеченные символы в таблице символов, а также на каждом шаге кодирования из таблицы интервалов вероятности появления каждого символа извлекают N ее первых значений, разбивают их на пары, затем выполняют обмен интервалами вероятности появления в указанной таблице, после чего преобразованные входные данные передают в блок выходных данных.

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

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

Наиболее близким по своей технической сущности к заявленному способу арифметического кодирования с шифрованием является способ арифметического кодирования с шифрованием по патенту США 7664267 МПК Н04L 9/00 (2006.01) от 30.06.2005. Способ - прототип арифметического кодирования с шифрованием заключается в предварительном формировании для передающей и приемной сторон основного ключа, на передающей стороне от отправителя получают очередную часть двоичной информационной последовательности (ИП), генерируют случайную битовую последовательность, вычисляют очередную часть оперативного ключа из основного ключа и случайной битовой последовательности, вычисляют значения первого и второго счетчиков частоты кодирования в соответствии с предварительно сформированным основным ключом, очередной частью оперативного ключа и очередной частью двоичной информационной последовательности, если значение первого счетчика частоты кодирования больше значения второго счетчика частоты кодирования, то меняют местами эти значения, устанавливают значения первого и второго регистров кодирования в соответствии со значениями первого и второго счетчиков частоты кодирования, выполняют арифметическое кодирование очередной части информационной последовательности в очередную часть закодированной последовательности, уточняют значения первого и второго регистров кодирования, формируют очередную часть зашифрованной последовательности из очередной части закодированной последовательности, передают очередную часть зашифрованной последовательности на приемную сторону и выполняют перечисленные действия до тех пор, пока поступают очередные части двоичной информационной последовательности, на приемной стороне получают очередную часть зашифрованной последовательности, арифметически декодируют случайную битовую последовательность из первой части принятой двоичной информационной последовательности, вычисляют значения первого и второго счетчиков частоты декодирования в соответствии с предварительно сформированным основным ключом, декодированной случайной битовой последовательностью и принятой двоичной информационной последовательностью, если значение первого счетчика частоты декодирования больше значения второго счетчика частоты декодирования, то меняют местами эти значения, устанавливают значения первого и второго регистров декодирования в соответствии со значениями первого и второго счетчиков частоты декодирования, выполняют арифметическое декодирование очередной части принятой зашифрованной последовательности, уточняют значения первого и второго регистров декодирования, формируют очередную часть принятой двоичной информационной последовательности из очередной части декодированной последовательности, передают получателю очередную часть принятой двоичной информационной последовательности и выполняют перечисленные действия на приемной стороне до тех пор, пока поступают очередные части зашифрованной последовательности.

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

Однако в данном способе-прототипе арифметического кодирования с шифрованием выполнение криптографического изменения модели кодирования в соответствии со случайной битовой последовательностью, несогласованной со статистическими характеристиками сжимаемой избыточной информационной последовательности, приводит к существенному снижению коэффициента сжатия арифметического кодирования ИП. В частности, авторы способа-прототипа указывают на этот недостаток, описывая в реферате, что предлагаемый ими способ может обеспечить сжатие кодируемых с шифрованием ИП не более чем в 2 раза. В противоположность этому известно, что арифметическое кодирование достаточно длинных избыточных ИП способно обеспечить удаление из них избыточности вплоть до значения их энтропии и достичь значений коэффициента сжатия вплоть до десятков раз, как описано, например, в книге Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин "Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео". - М.: ДИАЛОГ-МИФИ, 2002, стр. 35-49.

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

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

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

На передающей стороне вычисляют значения первого и второго счетчиков частоты кодирования в соответствии с двоичной информационной последовательностью, после чего из основного ключа по криптографической функции вычисляют очередную часть оперативного ключа, по которой устанавливают длину очередной части двоичной информационной последовательности и очередную размерность алфавита кодирования, причем вычисляют очередную часть оперативного ключа в виде десятичного числа n, где n≥1, по которой устанавливают длину n бит очередной части двоичной информационной последовательности и очередную размерность алфавита кодирования равной 2ⁿ.

От отправителя получают очередную часть двоичной информационной последовательности установленной длины, устанавливают значения первого и второго регистров кодирования в соответствии со значениями первого и второго счетчиков частоты кодирования, очередной частью двоичной информационной последовательности и очередной размерностью алфавита кодирования, на приемной стороне вычисляют значения первого и второго счетчиков частоты декодирования в соответствии с принятой двоичной информационной последовательностью, после чего из основного ключа по криптографической функции вычисляют очередную часть оперативного ключа, по которой устанавливают длину очередной части принятой двоичной информационной последовательности и очередную размерность алфавита декодирования, причем вычисляют очередную часть оперативного ключа в виде десятичного числа n, по которой устанавливают длину n бит очередной части принятой двоичной информационной последовательности и очередную размерность алфавита декодирования равной 2ⁿ. Устанавливают значения первого и второго регистров декодирования в соответствии со значениями первого и второго счетчиков частоты декодирования, очередной размерностью алфавита декодирования и очередной частью принятой зашифрованной последовательности, выполняют арифметическое декодирование очередной части принятой зашифрованной последовательности в очередную часть принятой двоичной информационной последовательности.

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

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

Заявленный способ поясняется чертежами, на которых показаны:

- на фиг. 1 - общая схема арифметического кодирования с зашифрованием и арифметического декодирования с расшифрованием в предлагаемом способе;

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

- на фиг. 3 - алгоритм арифметического кодирования с зашифрованием;

- на фиг. 4 - временные диаграммы арифметического кодирования с зашифрованием;

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

- на фиг. 6 - временные диаграммы арифметического декодирования с расшифрованием;

- на фиг. 7 - алгоритм арифметического декодирования с расшифрованием;

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

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

Реализация заявленного способа представлена на примере системы арифметического кодирования с шифрованием, показанной на фиг. 1, обеспечивающей на передающей стороне арифметическое кодирование с зашифрованием двоичной информационной последовательности, а на приемной стороне - ее арифметическое декодирование с расшифрованием. На передающей стороне в формирователе оперативного ключа 1 по криптографической функции из основного ключа вычисляют очередную часть оперативного ключа в виде числа n и устанавливают очередную размерность алфавита кодирования равной 2ⁿ. Считыватель очередной части ИП 2 считывает очередную часть ИП длиной n бит. В первом счетчике частоты кодирования 3 и втором счетчике частоты кодирования 4 в соответствии с уже обработанными частями ИП вычисляют значение первого счетчика частоты кодирования, подсчитывающего частоту закодированных нулевых символов, и значение второго счетчика частоты кодирования, подсчитывающего частоту закодированных единичных символов, соответственно. В первом регистре кодирования 5 и втором регистре кодирования 6 устанавливают значения первого и второго регистров кодирования в соответствии со значениями первого и второго счетчиков частоты кодирования, очередной частью двоичной информационной последовательности и очередной размерностью алфавита кодирования. В арифметическом кодере 7 в соответствии со значениями первого и второго регистров кодирования выполняют арифметическое кодирование очередной части ИП. В формирователе очередной части ШП 8 формируют очередную часть зашифрованной последовательности из очередной части закодированной последовательности, которую по каналу передачи 9 передают на приемную сторону.

На приемной стороне в формирователе оперативного ключа 10 по криптографической функции из основного ключа вычисляют очередную часть оперативного ключа в виде числа n и устанавливают очередную размерность алфавита декодирования равной 2ⁿ . В считывателе очередной части принятой зашифрованной последовательности (ПШП) 11 считывают очередную часть принятой ШП. В первом счетчике частоты декодирования 12 и втором счетчике частоты декодирования 13 в соответствии с уже обработанными частями принятой ИП вычисляют значение первого счетчика частоты декодирования, подсчитывающего частоту декодированных нулевых символов, и значение второго счетчика частоты декодирования, подсчитывающего частоту декодированных единичных символов, соответственно. В первом регистре декодирования 14 и втором регистре декодирования 15 устанавливают значения первого и второго регистров декодирования в соответствии со значениями первого и второго счетчиков частоты декодирования, очередной размерностью алфавита декодирования и очередной частью принятой ШП. В арифметическом декодере 16 в соответствии со значениями первого и второго регистров декодирования выполняют арифметическое декодирование очередной части принятой ШП в очередную часть принятой ИП, которую передают получателю.

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

Предварительное формирование для передающей и приемной сторон основного ключа заключается в следующем. Основной ключ в виде двоичной последовательности (ДП) формируют с использованием генератора случайных импульсов, генерирующего случайные равновероятные нулевые и единичные импульсы, независимые друг от друга. Способы формирования символов двоичной последовательности ключа их случайным выбором известны и описаны, например, в книге: Д. Кнут "Искусство программирования на ЭВМ". - М.: Мир, 1977, т. 2, стр. 22. Длина ДП основного ключа в битах должна быть не менее 256 бит, что описано, например, в ГОСТ 28147-89. Данный ключ является конфиденциальным и известен только на передающей и приемной стороне. Примерный вид ДП основного ключа показан на фиг. 2(a). Единичные значения битов на фигурах показаны в виде заштрихованных импульсов, нулевые значения битов - в виде незаштрихованных импульсов.

Способы предварительного формирования для передающей и приемной сторон криптографической функции известны и описаны, например, в книге М.Д. Смид, Д.К. Бранстед "Стандарт шифрования данных: Прошлое и будущее". ТИИЭР, 1988, - т. 76, №5, стр. 49. Они заключаются в формировании криптографической функции, используя алгоритм шифрования данных DES в режиме обратной связи по шифртексту или в режиме обратной связи по выходу. При этом шифрование выполняют над предыдущим криптографическим блоком, длина которого при использовании, например, алгоритма шифрования данных DES, равна 64 бита. Для формирования первого криптографического блока используют нулевой криптографический блок, вид которого общеизвестен и он является неконфиденциальным. Например, нулевой криптографический блок показан на фиг. 2(б) в виде двоичной последовательности "0000…0000". При использовании предварительного сформированной криптографической функции из нулевого криптографического блока с использованием основного ключа формируют первый криптографический блок, из первого криптографического блока с использованием основного ключа формируют второй криптографических блок и т.д., как показано на фиг.2(б).

Алгоритм арифметического кодирования с шифрованием представлен на фигуре 3.

Способы вычисления значений первого и второго счетчиков частоты кодирования в соответствии с двоичной информационной последовательностью известны и описаны, например, в книге Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин "Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео". - М.: ДИАЛОГ-МИФИ, 2002, стр. 124-130. Для этого первый счетчик частоты кодирования подсчитывает число кодируемых нулевых символов N₀ в обработанной части ИП, а второй счетчик частоты кодирования подсчитывает число кодируемых единичных символов N_l в обработанной части ИП. Числа N₀ и N₁ являются неотрицательными ненулевыми целыми числами. Также подсчитывают суммарное число кодируемых нулевых и единичных символов N, равное N=N₀+N₁. Значение частоты кодируемых нулевых символов р₀ вычисляют по формуле вида , а значение частоты кодируемых единичных символов р₁ вычисляют по формуле вида .

В начальном состоянии число кодируемых нулевых и единичных символов еще не подсчитано, поэтому в начальном состоянии устанавливают число кодируемых нулевых символов N₀=1 и число кодируемых единичных символов N_r=1. Соответственно, в начальный момент времени t=0 частота кодируемых нулевых символов равна и частота кодируемых единичных символов равна . После арифметического кодирования нулевых и единичных символов уточняют значения первого и второго счетчиков частоты кодирования.

Способы вычисления из основного ключа по криптографической функции очередной части оперативного ключа, по которой устанавливают длину очередной части двоичной информационной последовательности и очередную размерность алфавита кодирования, заключаются в следующем. Очередную часть оперативного ключа вычисляют по предварительно сформированной криптографической функции с использованием предварительно сформированного основного ключа. Для этого зашифровывают предыдущий криптографический блок, применяя, например, алгоритм шифрования данных DES в режиме обратной связи по шифртексту или в режиме обратной связи по выходу с использованием в качестве ключа шифрования предварительно сформированный основной ключ. Для формирования первого криптографического блока используют нулевой криптографический блок, вид которого общеизвестен. Например, вид нулевого криптографического блока показан на фиг. 4(a). При использовании предварительного сформированной криптографической функции и основного ключа из нулевого криптографического блока формируют первый криптографический блок вида, например, "10111…1011", как показано на фиг. 4(a). Из сформированного очередного криптографического блока выделяют очередную часть двоичной последовательности (ДП), например, фиксированной длины в четыре бита из начала очередного криптографического блока, как показано на фиг. 4(б). Из очередной части ДП вычисляют очередную часть оперативного ключа (ОК) в виде десятичного числа n, где n≥1, для этого подсчитывают число единичных символов данной двоичной последовательности. Например, из первого криптографического блока вида "10111…1011" выделяют первую часть двоичной последовательности вида "1011", в которой имеется 3 единичных символа, соответственно, первая часть оперативного ключа имеет десятичное значение n=3. Из второго криптографического блока вида "10011…1110" выделяют вторую часть двоичной последовательности вида "1001", в которой имеется 2 единичных символа, соответственно, вторая часть оперативного ключа имеет десятичное значение n=2 и т.д., как показано на фиг. 4(в).

Устанавливают очередную размерность алфавита кодирования, равную 2ⁿ. Очередная размерность алфавита кодирования может принимать значения 2, 4, 8,... Например, при длине первой части ИП n=3 бит первая размерность алфавита кодирования равна 8, при n=2 бит вторая размерность алфавита кодирования равна 4, при n=1 бит пятая размерность алфавита кодирования равна 2 и т.д.

По значению очередной части оперативного ключа устанавливают длину n бит очередной части двоичной информационной последовательности. От отправителя получают очередную часть ИП установленной длины. Например, первая часть ИП имеет длину n=3 бита и вид "000", вторая часть ИП имеет длину n=2 бита и вид "01", пятая часть ИП имеет длину n=1 бит и вид "0", как показано на фиг. 4(г). Очередная часть ИП длиною n бит имеет общий вид a_n, a_n-l,…,a_i,…,a₂, а₁, где очередные биты а_i, i=1,2,…..., n, принимают нулевое или единичное значение, первым по времени появления является бит a₁ и т.д.

Устанавливают значения первого и второго регистров кодирования в соответствии со значениями первого и второго счетчиков частоты кодирования, очередной частью двоичной информационной последовательности и очередной размерностью алфавита кодирования следующим образом. Сначала, как описано, например, в книге Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин "Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео". - М.: ДИАЛОГ-МИФИ, 2002, стр. 124-130, определяют нижнее L значение интервала кодирования и верхнее Я значение интервала кодирования арифметического кодирования. В начале арифметического кодирования начальное нижнее значение интервала кодирования устанавливают, например, в минимальное значение, а начальное верхнее значения интервала кодирования - в максимальное значение. Например, при разрядности арифметического кодирования 8 бит, начальное нижнее значение интервала кодирования арифметического кодирования L[0] устанавливают в минимальное значение, равное нулевому значению в десятичном представлении или "0000 0000" в двоичном представлении, где старшие двоичные символы записывают слева, а начальное верхнее значение интервала кодирования арифметического кодирования Н[0] устанавливают в максимальное значение, равное 255 в десятичном представлении или "1111 1111" в двоичном представлении.

Интервал кодирования арифметического кодирования I, равный I=Н-L, разделяют на значения подинтервала нулевых символов D₀ и подинтервала единичных символов D₁ длины которых прямо пропорциональны значениям первого и второго счетчиков частоты кодирования или, что эквивалентно, значениям вероятностей кодируемых нулевых символов р₀ и единичных символов р₁, соответственно. Длину подинтервала нулевых символов D₀ определяют по формуле вида D₀=I×р₀, а длину подинтервала единичных символов D₁ определяют по формуле вида D₁=I-D₀.

Например, в начальный момент времени t=0 при значениях первого и второго счетчиков частоты кодирования N₀=1 и N_t=1, соответственно, начальная длина подинтервала нулевых символов D₀[0] имеет десятичное значение 127 или "01111111" в двоичном представлении, а начальная длина подинтервала единичных символов D₁[0] имеет десятичное значение 255-127=128 или "10000000" в двоичном представлении. Подинтервал единичных символов расположен, например, сверху подинтервала нулевых символов. Верхнюю границу подинтервала нулевых символов обозначают как значение Q, и данный подинтервал начинается снизу от нижней границы интервала кодирования арифметического кодирования до значения Q исключительно, а подинтервал единичных символов простирается от значения Q включительно до верхней границы интервала кодирования арифметического кодирования исключительно. Например, в начальный момент времени t=0 значение Q равно десятичному значению 127 или "01111111" в двоичном представлении.

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

Если длина очередной части двоичной информационной последовательности равна n=1, то интервал кодирования разделяют на значения подинтервала нулевых символов D₀ и подинтервала единичных символов D₁ один раз, если n=2, то разделение в соответствии с очередной частью двоичной информационной последовательности выполняют итеративно 2 раза и т.д. Например, первая часть ИП имеет длину n=3 бит и вид "000". Сначала интервал кодирования (в данный момент начальный интервал кодирования) от 0 до 255 разделяют на подинтервал нулевых символов от нижней границы интервала кодирования L=0 до значения Q=127 исключительно, а подинтервал единичных символов простирается от значения Q=127 включительно до верхней границы интервала кодирования арифметического кодирования Н=255, исключительно. Далее при n>1 в зависимости от первого бита а₁ очередной части ИП выбирают текущий интервал кодирования: если первый бит а₁ очередной части ИП имеет нулевое значение, то текущий интервал кодирования становится равным текущему подинтервалу нулевых символов, если первый бит а₁ очередной части ИП имеет единичное значение, то текущий интервал кодирования становится равным текущему подинтервалу единичных символов. Текущий интервал кодирования I повторно разделяют на текущий подинтервал нулевых символов длиною D₀=I×р₀, и текущий подинтервал единичных символов длиною D₁=I-D₀ и т.д.

Например, для первой части ИП вида "000" в зависимости от первого бита а₁=0 текущий интервал кодирования становится равным текущему подинтервалу нулевых символов, в пределах от L=0 до значения Q=127. Затем текущий интервал кодирования I разделяют на текущий подинтервал нулевых символов D₀ длиною D₀=64 и подинтервал единичных символов D₁ длиною D₁=63. Текущее значение Q стало равным Q=64. В зависимости от второго бита а₂=0 первой части ИП текущий интервал кодирования становится равным текущему подинтервалу нулевых символов, в пределах от L=0 до значения Q=64.

В соответствии с очередной частью двоичной информационной последовательности и очередной размерностью алфавита кодирования 2ⁿ, где n=3, в третий раз текущий интервал кодирования I разделяют на текущий подинтервал нулевых символов D₀ длиною D₀=I×р₀=64×1/2=32 и текущий подинтервал единичных символов D₁ длиною D₁=I-D₀=64-32=32. Текущее значение Q стало равным Q=32 или "0010 0000" в двоичном представлении, текущее значение нижней границы интервала кодирования L=0 и текущее значение верхней границы интервала кодирования Н=64 или "0100 0000" в двоичном представлении, как показано во второй строке фиг. 5, обозначенной Формирование модели для первой части ИП (Форм, модели для 1-ой части ИП).

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

Выполняют арифметическое кодирование очередной части двоичной информационной последовательности в очередную часть закодированной последовательности следующим образом. Оно заключается в кодировании очередной части двоичной информационной последовательности в соответствии с текущими значениями первого и второго регистров кодирования в зависимости от значения последнего, n-го символа очередной части ИП.

Если символ а_n очередной части ИП является нулевым двоичным символом, текущее значение интервала кодирования I устанавливают равным текущему значению подинтервала нулевых символов D₀, и текущее нижнее значение интервала кодирования L устанавливают равным текущему нижнему значению интервала кодирования, записанному в первый регистр кодирования, а текущее верхнее значение интервала кодирования Н устанавливают равным текущему значению Q, записанному во второй регистр кодирования. А при поступлении на вход арифметического кодирования очередной части двоичной информационной последовательности, символ а_n которой является единичным двоичным символом, текущее значение интервала кодирования I устанавливают равным текущему значению подинтервала единичных символов D₁, и текущее нижнее значение интервала кодирования L устанавливают равным текущему значению Q, записанному во второй регистр кодирования, а текущее верхнее значение интервала кодирования H устанавливают равным текущему верхнему значению интервала кодирования, записанному в первый регистр кодирования.

Например, при поступлении на вход арифметического кодирования первой части двоичной информационной последовательности, символ а_n которой (третий по счету) является нулевым двоичным символом, текущее значение интервала кодирования I устанавливают равным текущему значению подинтервала нулевых символов D₀, и текущее нижнее значение интервала кодирования L устанавливают равным текущему нижнему значению интервала кодирования L=0, а текущее верхнее значение интервала кодирования H устанавливают равным текущему значению Q=32, как показано в третьей строке фиг. 5 в момент времени t=1 при кодировании первой части двоичной информационной последовательности (t=1: код. 1-ой части ИП).

Способы уточнения значений первого и второго регистров кодирования арифметического кодирования известны и описаны, например, в книге Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин "Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео". - М.: ДИАЛОГ-МИФИ, 2002, стр. 35-43. Они заключаются в сравнении левого (самого старшего по времени записи в регистр) бита двоичного представления текущего нижнего значения интервала кодирования L, записанного в первый регистр кодирования, с левым (самым старшим по времени записи в регистр) бита двоичного представления текущего верхнего значения интервала кодирования H, записанного во второй регистр кодирования, и при их совпадении значение левого бита двоичных представлений текущих значений L и H считывают в качестве очередного закодированного бита кодированной последовательности и т.д.

Например, как показано на фиг. 5 в третьей строке, после кодирования первой части двоичной информационной последовательности двоичное представление текущего нижнего значения интервала кодирования L равно "0000 0000", а двоичное представление текущего верхнего значения интервала кодирования Я равно "0010 0000". Выявлено совпадение самого левого бита этих двоичных представлений и самый левый бит двоичных представлений значений L и H считывают в качестве очередного закодированного бита кодированной последовательности (Зак. сим.), как показано в правом столбце на фиг. 5. Считанный бит удаляют из двоичных представлений, которые уменьшаются до длины 7 бит вида "000 0000" для L и "010 0000" для H, соответственно. Двоичные символы двоичных представлений значений L и H сдвигают справа налево на один разряд и справа к ним в младший разряд дописывают по нулевому двоичному символу. Способы считывания двоичных символов с удалением считанных символов известны и описаны, например, в книге: В. Шило "Популярные цифровые микросхемы". - М.: Радио и связь, 1987, 104-123, с использованием регистров сдвига с параллельной и последовательной записью/считыванием двоичных последовательностей. Операции сдвига справа налево на один разряд и дописывания справа нулевого двоичного символа увеличивают значения L и Н в 2 раза и называются нормализацией параметров арифметического кодирования. Способы сдвига на один разряд в сторону старших разрядов двоичных последовательностей и записи в освободившийся младший разряд нулевого двоичного символа известны и описаны, например, в книге: В. Шило "Популярные цифровые микросхемы". – М.: Радио и связь, 1987, 104-123, с использованием регистров сдвига с параллельной и последовательной записью/считыванием двоичных последовательностей, и по своей сути являются умножением на два десятичных значений нижнего и верхнего значений интервала кодирования. В результате значение L осталось равным числу 0 с двоичным представлением вида "0000 0000", а десятичное значение Н устанавливают равным 64 с двоичным представлением вида "0100 0000", как показано на фиг. 5 в четвертой строке.

После выполнения очередной нормализации повторно самый левый бит двоичного представления значения L сравнивают с самым левым битом двоичного представления значения Н и при их совпадении значение самого левого бита двоичных представлений значений L и Н считывают в качестве очередного закодированного бита кодированной последовательности и так далее до окончания двоичной информационной последовательности. В результате уточнения значений первого и второго регистров кодирования после арифметического кодирования первой части ИП вида "000" получена первая часть закодированной последовательности (КП) вида "00" длиной 2 бит, показанная на фиг. 4(г).

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

Далее уточняют число закодированных нулевых символов и единичных символов. После кодирования первой части двоичной информационной последовательности, состоящей из трех нулевых символов, число закодированных нулевых символов увеличивают на 3 и оно составляет N₀=4, и число закодированных нулевых и единичных символов становится равным N=N₀+N₁=5. Пересчитывают текущее значение вероятности кодируемых нулевых символов и текущее значение вероятности кодируемых единичных и т.д.

Примерный вид арифметического кодирования с зашифрованием первых семи очередных частей двоичной информационной последовательности вида "000 01 001 00 0 010 01" длиною 16 двоичных символов, показанных на фиг. 4(г), в первые семь очередных частей закодированной последовательности представлен на фиг. 4(д) и на фиг. 5. В результате арифметического кодирования некоторые очередные части закодированной последовательности могут оказаться пустыми, как например, пятая и шестая части КП.

Формируют очередные части зашифрованной последовательности из очередных частей закодированной последовательности следующим образом. Из очередных частей закодированной последовательности последовательно считывают фиксированное число m≥2 двоичных символов в очередные части зашифрованной последовательности (ШП). Например, при длине m=4 очередных частей ШП семь первых частей КП, показанных на фиг. 4(д), формируют первые неполные четыре части ШП, показанные на фиг. 4(e), последняя часть ШП оказалась неполной.

Способы передачи на приемную сторону очередной части зашифрованной последовательности известны и описаны, например, в книге А.Г. Зюко, Д.Д. Кловский, М.В. Назаров, Л.М. Финк. Теория передачи сигналов. – М.: Радио и связь, 1986, стр. 11. Примерный вид первых четырех частей принятой зашифрованной последовательности (Пр. ШП) показан на фиг. 6(a).

Алгоритм арифметического декодирования с расшифрованием представлен на фиг. 7.

Способы вычисления значения первого и второго счетчиков частоты декодирования в соответствии с принятой двоичной информационной последовательностью известны и описаны, например, в книге Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. - М.: ДИАЛОГ-МИФИ, 2002, стр. 124-130. Первый счетчик частоты декодирования подсчитывает число декодируемых нулевых символов NN₀ в обработанной части принятой ИП. Второй счетчик частоты декодирования подсчитывает число декодируемых единичных символов NN₁. Числа NN₀ и NN₁ являются ненулевыми целыми числами. При арифметическом декодировании также подсчитывают суммарное число декодируемых нулевых и единичных символов NN, равное NN=NN₀+NN₁.

Значение частоты декодируемых нулевых символов рр₀ вычисляют по формуле вида , а значение частоты декодируемых единичных символов рр₁ вычисляют по формуле вида . В начальном состоянии число декодируемых нулевых и единичных символов еще не подсчитано, поэтому в начальном состоянии устанавливают число декодируемых нулевых символов NN₀=1 и число декодируемых единичных символов NN₁=1. Соответственно, в начальный момент времени t=0 частота декодируемых нулевых символов равна и частота декодируемых единичных символов равна . После арифметического декодирования нулевых и единичных символов уточняют значения первого и второго счетчиков частоты декодирования.

Способы вычисления на приемной стороне из основного ключа по криптографической функции очередной части оперативного ключа, по которой устанавливают длину очередной части принятой двоичной информационной последовательности и очередную размерность алфавита декодирования, идентичны ранее описанным способам вычисления из основного ключа по криптографической функции очередной части оперативного ключа, по которой устанавливают длину очередной части двоичной информационной последовательности и очередную размерность алфавита кодирования. Поэтому на приемной стороне вычисляют идентичные с передающей стороной очередные части оперативного ключа, например, как показано на фиг.6(б), по которым устанавливают длину очередных частей принятой двоичной информационной последовательности и очередную размерность алфавита декодирования. Например, при установленной длине первой части принятой ИП n=3 бит первая размерность алфавита декодирования равна 8, при установленной длине второй части принятой ИП n=2 бит вторая размерность алфавита кодирования равна 4 и т.д.

Устанавливают значения первого и второго регистров декодирования в соответствии со значениями первого и второго счетчиков частоты декодирования, очередной размерностью алфавита декодирования и очередной частью принятой зашифрованной последовательности следующим образом. Сначала, как описано, например, в книге Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. - М.: ДИАЛОГ-МИФИ, 2002, стр. 124-130, определяют нижнее L значение интервала декодирования и верхнее Н значение интервала декодирования арифметического декодирования. В начале арифметического декодирования начальное нижнее значение интервала декодирования устанавливают, например, в минимальное значение, а начальное верхнее значения интервала декодирования - в максимальное значение. Например, при разрядности арифметического декодирования R=8 бит, начальное нижнее значение интервала декодирования арифметического декодирования LL[0] устанавливают в минимальное значение, равное нулевому значению в десятичном представлении или "0000 0000" в двоичном представлении, где старшие двоичные символы записывают слева, а начальное верхнее значение интервала декодирования арифметического декодирования НН[0] устанавливают в максимальное значение, равное 255 в десятичном представлении или "1111 1111" в двоичном представлении.

Интервал декодирования арифметического декодирования II, равный II=НН-LL, разделяют на подинтервал декодирования нулевых символов DD₀ и подинтервала декодирования единичных символов DD₁, длины которых прямо пропорциональны значениям первого и второго счетчиков частоты декодирования или, что эквивалентно, значениям вероятностей декодируемых нулевых символов рр₀ и единичных символов рр₁, соответственно. Длину подинтервала нулевых символов DD₀ определяют по формуле вида DD₀=II×рр₀, а длину подинтервала единичных символов DD₁ определяют по формуле вида DD₁=II-DD₀.

Например, в начальный момент времени декодирования tt=0 при значениях первого и второго счетчиков частоты декодирования NN₀=1 и NN₁=1, соответственно, начальная длина подинтервала нулевых символов DD₀[0] имеет десятичное значение 127 или "0111 1111" в двоичном представлении, а начальная длина подинтервала единичных символов DD₁[0] имеет десятичное значение 255-127=128 или "1000 0000" в двоичном представлении. Подинтервал единичных символов расположен, например, сверху подинтервала нулевых символов. Верхнюю границу подинтервала нулевых символов обозначают как значение QQ, и данный подинтервал начинается снизу от нижней границы интервала кодирования арифметического декодирования до значения QQ исключительно, а подинтервал единичных символов простирается от значения QQ включительно до верхней границы интервала декодирования исключительно.

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

В начальном состоянии декодирования из очередных частей принятой зашифрованной последовательности считывают число бит, соответствующее разрядности значения интервала декодирования арифметического декодирования. Например, при разрядности R=8 бит считывают 8 бит, и в момент времени декодирования tt=0 из первых двух частей принятой ШП считывают последовательность вида "0001 0111", что соответствует десятичному числу 22, как показано в строке начального состояния арифметического декодирования (нач. сост.) при tt=0 на фиг. 8.

В соответствии с очередной длиной n бит очередной части принятой ИП и размерностью алфавита декодирования устанавливают значения первого и второго регистров декодирования путем разделения n раз текущего интервала декодирования на текущие подинтервал декодирования нулевых символов и подинтервал декодирования единичных символов, причем выбираемый подинтервал декодирования должен включать текущее значение считанной последовательности. Например, при установленной длине первой части принятой ИП n=3 бит и первой размерности алфавита декодирования, равной 8, три раза выполняют разделение текущего интервала декодирования. Сначала текущий интервал декодирования (в данный момент начальный интервал декодирования) от 0 до 255 разделяют на подинтервал декодирования нулевых символов от LL=0 до QQ=127, а подинтервал декодирования единичных символов от QQ=127 до НН=255. Текущее значение считанной последовательности 22 принадлежит подинтервалу декодирования нулевых символов, поэтому при первом разделении текущий интервал декодирования становится равным подинтервалу декодирования нулевых символов. Выбор подинтервала декодирования нулевых символов при первом разделении текущего интервала декодирования означает, что первый символ очередной части принятой двоичной информационной последовательности является нулевым символом, иначе выбор подинтервала декодирования единичных символов при первом разделении текущего интервала декодирования означает, что первый символ очередной части принятой двоичной информационной последовательности является единичным символом. Затем при втором разделении текущий интервал декодирования разделяют на подинтервал декодирования нулевых символов от LL=0 до QQ=64 и на подинтервал декодирования единичных символов от QQ=64 до НН=127. Текущее значение считанной последовательности 22 снова принадлежит подинтервалу декодирования нулевых символов, поэтому текущий интервал декодирования выбирают от LL=0 до НН=64. Выбор подинтервала декодирования нулевых символов при втором разделении текущего интервала декодирования означает, что второй символ очередной части принятой двоичной информационной последовательности является нулевым символом. В третий раз текущий интервал декодирования разделяют на подинтервал декодирования нулевых символов от LL=0 до QQ=32 и на подинтервал декодирования единичных символов от QQ=32 до НН=64, как показано во второй строке фиг. 8, обозначенной "Формирование модели для первой части принятой ИП" (Форм, модели для 1-ой части пр. ИП). Соответственно, в первый регистр декодирования RR₁ записывают значение LL=0 и значение QQ=32, а во второй регистр декодирования RR₂ записывают значение НН=64.

Выполняют арифметическое декодирование очередной части принятой двоичной информационной последовательности следующим образом. Оно заключается в декодировании очередной части принятой ИП в соответствии с текущими значениями первого и второго регистров декодирования в зависимости от текущего значения считанной последовательности. Текущий интервал декодирования становится равным тому текущему подинтервалу декодирования, который включает текущее значение считанной последовательности. Например, при декодировании первой части принятой ИП текущий подинтервал декодирования нулевых символов от LL=0 до QQ=32 включает текущее значение считанной последовательности 22. Выбор текущего подинтервала декодирования нулевых символов означает декодирование последнего символа данной части принятой ИП как нулевого символа, иначе выбор текущего подинтервала декодирования единичных символов означает декодирование последнего символа данной части принятой ИП как единичного символа. Поэтому с учетом ранее установленных первого и второго символов первая часть принятой ИП принимает вид "000", как показано на фиг. 6(в). В результате декодирования первой части принятой ИП текущий интервал декодирования выбран от LL=0 до НН=32, как показано на фиг. 8 в третьей строке "tt=1: Декодирование 1-ой части принятой ИП" (Дек. 1-ой части пр. ИП).

Способы уточнения значений первого и второго регистров декодирования арифметического декодирования идентичны ранее описанным способам уточнения значений первого и второго регистров кодирования арифметического кодирования. Они заключаются в сравнении левого (самого старшего по времени записи в регистр) бита двоичного представления текущего нижнего значения интервала декодирования LL, записанного в первый регистр декодирования, с левым (самым старшим по времени записи в регистр) бита двоичного представления текущего верхнего значения интервала декодирования НН, записанного во второй регистр декодирования, и при их совпадении выполняют нормализацию арифметического декодирования: значение самого левого бита двоичных представлений значений LL и НН удаляют и двоичные символы двоичных представлений значений LL и НН сдвигают справа налево на один разряд и справа к ним в младший разряд дописывают по нулевому двоичному символу. Одновременно с этим, значение самого левого бита считанной последовательности удаляют и двоичные символы входных данных сдвигают справа налево на один разряд и справа к ним дописывают следующий двоичный символ очередной части принятой зашифрованной последовательности. Например, после арифметического декодирования первой части принятой ИП переменная LL принимает десятичное значение 0 и двоичное представление "0000 0000", а НН - десятичное значение 32 и двоичное представление "0010 0000". В результате нормализации переменная LL принимает десятичное значение 0 и двоичное представление "0000 0000", а НН - десятичное значение 64 и двоичное представление "0100 0000", а входные данные с учетом следующего двоичного символа (девятого по счету согласно фиг. 6(a) очередной (по счету третьей) части принятой ШП, являющегося единичным символом, принимают десятичное значение 45 и двоичное представление "0010 1101", как показано на фиг. 8 в четвертой строке "нормализация". Так как левый бит двоичного представления LL снова совпадает с левым бита двоичного представления НН, то нормализацию выполняют повторно, как показано на фиг. 8 в пятой строке "нормализация". После второй нормализации левые биты двоичных представлений LL и НН не совпадают, что означает завершение уточнения значений первого и второго регистров декодирования арифметического декодирования.

После арифметического декодирования очередной части принятой ИП ее передают получателю и уточняют число декодируемых нулевых символов NN₀ и число декодируемых единичных символов NN₁ в обработанной части принятой ИП. Например, в результате декодирования первой части принятой ИП число декодируемых нулевых символов приняло значение NN₀=4, а число декодируемых единичных символов NN₁ осталось прежним. Соответственно, уточняют значение частоты декодируемых нулевых символов рр₀=4/5 и значение частоты декодируемых единичных символов рр₁=\15, как показано в третьей строке на фиг. 8.

В результате арифметического декодирования с использованием основного ключа на приемной стороне, из первых четырех частей принятой ШП декодированы полностью первые три части принятой ИП, как показано на фиг. 6(в). Видно, что при декодировании со знанием основного ключа очередные части принятой ИП соответствуют очередным частям ИП.

Если на приемной стороне неизвестен основной ключ, то невозможно правильно декодировать принятую ИП. Например, на фиг. 9 показан процесс декодирования этих же четырех частей принятой ШП в условиях, когда длина очередных частей принятой двоичной информационной последовательности принимаются равной n=1 и очередная размерность алфавита декодирования принимается равной 2. В результате декодирования принятая ИП имеет вид "0000 0000 0011". Первые четыре символа принятой ИП совпали с символами ИП, а далее символы принятой ИП совпадают с символами ИП с вероятностью случайного угадывания.

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

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

Было выполнено арифметическое кодирование с шифрованием одной и той же избыточной двоичной информационной последовательности длиной 49766400 байт с использованием способа-прототипа и предлагаемого способа. При разрядности R битов устройства, реализующего арифметическое кодирование, равной 8, 16 и 32 битов, при использовании способа-прототипа достигается коэффициент сжатия от 1,18 до 1,42 раз, а при использовании предлагаемого способа величина коэффициента сжатия повышается в диапазоне значений от 3,78 до 4,19 раз, соответственно, во столько же раз уменьшается скорость передачи зашифрованной информации.

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