СПОСОБ АРИФМЕТИЧЕСКОГО КОДИРОВАНИЯ С ШИФРОВАНИЕМ Российский патент 2016 года по МПК H04L9/08 G06F21/60 

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

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

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

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

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

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

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

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

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

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

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

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

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

Общий принцип использования случайной битовой последовательности для шифрования двоичных информационных последовательностей известен в науке и технике и описан, например, в книге М.А. Иванов "Криптографические методы защиты информации в компьютерных системах и сетях". - М.: КУДИЦ-ОБРАЗ, 2001, стр. 254-256. Совокупность таких способов шифрования двоичных информационных последовательностей известна как способы вероятностного (рандомизированного) шифрования двоичных информационных последовательностей, обеспечивающих повышение защищенности к попыткам нарушителя несанкционированного чтения зашифрованной информации. Данное повышение защищенности обусловлено тем, что изменяющаяся каждый раз случайная битовая последовательность при арифметическом кодировании с зашифрованием существенно повышает непредсказуемость для нарушителя результата кодирования с зашифрованием, включая случай известности для нарушителя кодируемой двоичной информационной последовательности.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Способы предварительного формирования для передающей стороны начальных значений первого и второго регистров кодирования также используют генератор случайных импульсов, генерирующий случайные равновероятные нулевые и единичные импульсы, независимые друг от друга. Случайным образом формируют начальное значение первого регистра кодирования в виде двоичной последовательности длины R битов, равной разрядности устройства, реализующего арифметическое кодирование, и начальное значение второго регистра кодирования в виде двоичной последовательности удвоенной длины 2R битов. Примерный вид начального значения первого регистра кодирования (Нач. знач. 1-го рег. код.) в виде 8-битовой ДП "10011011" и начального значения второго регистра кодирования (Нач. знач. 2-го рег.код.) в виде 16-битовой ДП "01…011110" при R=8 бит показан на фиг. 3(б). Предварительно сформированные для приемной стороны начальные значения первого и второго регистров декодирования полностью совпадают с соответствующими предварительно сформированными начальными значениями первого и второго регистров кодирования. Примерный вид начального значения первого регистра декодирования (Нач. знач. 1-го рег. декод.) в виде 8-битовой ДП "10011011" и начального значения второго регистра декодирования (Нач. знач. 2-го рег. декод.) в виде 16-битовой ДП "01…011110" при R=8 бит показан на фиг. 3(в).

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

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

На передающей стороне от отправителя получают очередную часть двоичной информационной последовательности. Кодирование информационной последовательности начинается с момента поступления первого ее бита и при кодировании первых битов очередной части двоичной информационной последовательности не требуется получения от отправителя целиком очередной части этой последовательности. Примерный вид первых трех очередных частей двоичной информационной последовательности (ИП) в виде двоичной последовательности "0111110110000100010001001" длиной 25 бит показан на фигуре 5(a).

Способы вычисления значения первого и второго счетчиков частоты кодирования в соответствии с предварительно сформированным ключом и двоичной информационной последовательностью заключаются в следующем. Первый счетчик частоты кодирования подсчитывает число кодируемых нулевых символов N₀ в обработанной части ИП. Второй счетчик частоты кодирования подсчитывает число кодируемых единичных символов N₁, в обработанной части ИП. Числа N₀ и N₁ являются неотрицательными ненулевыми целыми числами. При арифметическом кодировании также подсчитывают суммарное число кодируемых нулевых и единичных символов N, равное N=N₀+N₁. В начальном состоянии число кодируемых нулевых и

единичных символов еще не подсчитано, поэтому начиная кодировать первую часть двоичной информационной последовательности значения первого и второго счетчиков частоты кодирования вычисляют, например, в соответствии с ключом. Например, в соответствии с ключом первый и второй счетчики частоты кодирования принимают значения 11 и 2, соответственно. Поэтому суммарное число кодируемых нулевых и единичных символов N принимает начальное значение, равное N=13, как показано в верхней строке начального состояния арифметического кодирования с зашифрованием на фиг. 6 в начальный момент времени t=0. Значение первого счетчика частоты кодирования определяет значение вероятности кодируемых нулевых символов р₀, а значение второго счетчика частоты кодирования определяет значение вероятности кодируемых единичных символов р₁, при этом должно выполняться ограничение вида: р₀+р₁=1 Значение вероятности кодируемых нулевых символов р₀ вычисляют по формуле вида а значение вероятности кодируемых единичных символов р₁ вычисляют по формуле вида

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

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

Например, в начальный момент времени t=0 при значениях первого и второго счетчиков частоты кодирования N₀=11 и N₁=2, соответственно, начальная длина подинтервала единичных символов D₁[0] имеет десятичное значение 38 или "00100110" в двоичном представлении, а начальная длина подинтервала нулевых символов D₀[0] имеет десятичное значение 255-38=217 или "11011001" в двоичном представлении. Подинтервал единичных символов расположен, например, сверху подинтервала нулевых символов, как показано на фиг. 7. Верхнюю границу подинтервала нулевых символов обозначают как значение Q, и данный подинтервал начинается снизу от нижней границы интервала кодирования арифметического кодирования до значения Q исключительно, а подинтервал единичных символов простирается от значения Q включительно до верхней границы интервала кодирования арифметического кодирования исключительно. Значение первого регистра кодирования устанавливают равным значению Q. Например, в момент времени r=0 значение первого регистра кодирования равно десятичному значению 217 или "11011001" в двоичном представлении, как показано на фиг. 6 в первой строке при t=0. Во второй регистр кодирования записывают, например, нижнее L и верхнее Н значения интервала кодирования. Например, в момент времени t=0 во втором регистре кодирования последовательно записаны десятичные значения 0 и 255 или "00000000" и "11111111" в двоичном представлении, как показано на фиг. 6 в первой строке при t=0, а также как показано на фиг. 7 в начальном состоянии (Нач. сост.) арифметического кодирования.

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

Примерный вид арифметического кодирования показанной на фиг. 5(a) двоичной информационной последовательности вида "0111110110000100010001001" длиною 25 двоичных символов с использованием арифметического кодирования в кодированную последовательность вида "110110001110111100101001" представлен на фиг. 6 и на фиг. 7.

При поступлении на вход арифметического кодирования первого кодируемого символа (t=1), являющегося нулевым двоичным символом, значение интервала кодирования первого символа I[1] устанавливают равным начальному значению подинтервала нулевых символов D₀[0], поэтому нижнее значение интервала кодирования первого символа L[l] устанавливают равным начальному нижнему значению интервала кодирования арифметического кодера L[0], записанному во второй регистр кодирования, равному, например, 0, а верхнее значение интервала кодирования первого символа арифметического кодирования H[1] устанавливают равным текущему значению Q, записанному в первый регистр кодирования, равному, например, 217, как показано на фиг. 7. Самый левый бит двоичного представления значения L[1] сравнивают с самым левым битом двоичного представления значения H[1], например, вида "00000000" и "11011001", соответственно, как показано на фиг. 6 при t=1. При их несовпадении переходят к кодированию следующего бита входных данных.

После выполнения кодирования каждого очередного бита входных данных уточняют число закодированных нулевых символов и единичных символов. Так как первый очередной бит является нулевым, то число закодированных нулевых символов увеличивают на единичное значение и оно составляет N₀[1]=12, и число закодированных нулевых и единичных символов становится равным N[1]=N₀[l]+N₁[1]=l3. Пересчитывают текущее значение вероятности кодируемых нулевых символов и текущее значение вероятности кодируемых единичных В соответствии с этим длина подинтервала нулевых символов D₀[1] увеличивается по сравнению с длиной подинтервала единичных символов D₁[1], а параметр Q принимает десятичное значение 186 и двоичное значение "10111010", как показано на фиг. 7 и на фиг. 6, вторая строка сверху.

Если самый левый бит двоичного представления нижнего значения интервала кодирования не совпадает с самым левым битом двоичного представления верхнего значения интервала кодирования, то переходят к кодированию следующего бита. Например, следующий кодируемый бит, второй по счету, двоичной информационной последовательности является единичным двоичным символом, как показано на фиг. 6, третья строка сверху, при t=2. При поступлении на вход арифметического кодирования единичного двоичного символа, значение интервала кодирования арифметического кодирования устанавливают равным значению предыдущего подинтервала единичных символов, поэтому нижнее значение интервала кодирования L[2] устанавливают равным значению Q, а верхнее значение интервала кодирования H[2] устанавливают равным предыдущему верхнему значению интервала кодирования H[1]. Например, как показано на фиг. 7, значение L[2] устанавливают равным 186, а H[2] остается равным предыдущему значению 217. Повторно самый левый бит двоичного представления значения L[2] вида "10111010" сравнивают с самым левым битом двоичного представления значения H[2] вида "11011001" и при их совпадении значение самого левого бита двоичных представлений значений L[2] и H[2] считывают в качестве очередного закодированного бита кодированной последовательности и так далее до окончания двоичной информационной последовательности. Например, при кодировании второго бита данной двоичной информационной последовательности первым закодированным битом кодированной последовательности является совпавший при сравнении единичный двоичный символ, как показано на фиг. 6, третья строка сверху при t=1. Считанный бит удаляют из двоичных представлений значений L[1] и H[1], которые уменьшаются до длины 7 бит вида "0111010" и "1011001", соответственно. Двоичные символы двоичных представлений значений L[1] и H[1] сдвигают справа налево на один разряд и справа к ним в младший разряд дописывают по нулевому двоичному символу. Способы считывания двоичных символов с удалением считанных символов известны и описаны, например, в книге: В. Шило "Популярные цифровые микросхемы". - М., Радио и связь, 1987, 104-123, с использованием регистров сдвига с параллельной и последовательной записью/считыванием двоичных последовательностей. Операции сдвига справа налево на один разряд и дописывания справа нулевого двоичного символа увеличивают значения L[1] и H[1] в 2 раза и называются нормализацией параметров арифметического кодирования. Способы сдвига на один разряд в сторону старших разрядов двоичных последовательностей и записи в освободившийся младший разряд нулевого двоичного символа известны и описаны, например, в книге: В. Шило "Популярные цифровые микросхемы". - М., Радио и связь, 1987, 104-123, с использованием регистров сдвига с параллельной и последовательной записью/считыванием двоичных последовательностей, и по своей сути являются умножением на два десятичных значений нижнего и верхнего значений интервала кодирования.

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

После каждого выполнения нормализации повторно самый левый бит двоичного представления нижнего значения интервала кодирования сравнивают с самым левым битом двоичного представления верхнего значения интервала кодирования. Например, после выполнения нормализации при кодировании второго бита значение L[2] устанавливают равным 116, а H[2] устанавливают равным 178. Повторно самый левый бит двоичного представления значения L[2] вида "01110100" сравнивают с самым левым битом двоичного представления значения H[2] вида "10110010" и при отсутствии совпадения переходят к кодированию следующего, третьего по счету бита двоичной информационной последовательности.

В результате арифметического кодирования первой части двоичной информационной последовательности вида "011110" получена первая часть кодированной последовательности вида "11011000" длиной 8 бит. Очередная часть кодированной последовательности имеет фиксированный размер R бит, например, 8, 16 или 32 бита. Выбор размера очередной части кодированной последовательности определяется разрядностью используемого для реализации способа арифметического кодирования с шифрованием вычислительного устройства. Например, в результате арифметического кодирования первых трех частей двоичной информационной последовательности, показанной на фиг.5(a), получены первые три части кодированной последовательности длиной по 8 бит каждая, показанные на фиг. 5(б).

Способы зашифрования очередной части кодированной последовательности с использованием предварительно сформированных криптографической функции и ключа, а также значений первого и второго регистров кодирования предыдущей части двоичной информационной последовательности заключаются в следующем. В результате арифметического кодирования сформирована очередная часть кодированной последовательности, имеющая фиксированную длину в битах. Например, в результате арифметического кодирования второй части двоичной информационной последовательности вида "11000", показанной на фиг. 5(a), получена вторая часть кодированной последовательности вида "11101111", показанная на фиг. 5(б). Значения первого и второго регистров кодирования предыдущей части двоичной информационной последовательности формируют арифметическим кодированием в начале кодирования предыдущей части ИП. Например, используемые для шифрования второй части КП значения первого и второго регистров кодирования первой части ИП соответствуют начальному состоянию арифметического кодирования в момент времени t=0, показанному на фиг. 6, первая строка. Соответственно, значение первого регистра кодирования первой части ИП равно "11011001", и эквивалентно десятичному значению 217, а значение второго регистра кодирования первой части ИП равно "00000000 11111111", и эквивалентно десятичным значениям 0 и 255. Затем предварительно сформированную двоичную последовательность ключа, например, побитно суммируют по модулю 2 с двоичными последовательностями первого и второго регистров кодирования предыдущей части двоичной информационной последовательности. Для этого первые R бит двоичной последовательности ключа побитно суммируют по модулю 2 с R битами двоичной последовательности первого регистра кодирования предыдущей части двоичной информационной последовательности, затем последующие 2R бит двоичной последовательности ключа побитно суммируют по модулю 2 с 2R битами двоичной последовательности второго регистра кодирования этой части ИП, образуя оперативный ключ для шифрования очередной части КП, по своему предназначению подобный оперативному ключу в ближайшем аналоге (прототипе). Например, оперативный ключ второй части КП показан на фиг.5(e), в виде двоичной последовательности "1001110…0".

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

Аналогичным образом выполняют арифметическое кодирование и зашифрование следующей, третьей части двоичной информационной последовательности и т.д. Третью часть двоичной информационной последовательности вида "0100010001001", показанную на фиг. 5(a), арифметически кодируют в третью часть кодированной последовательности вида "00101001", показанную на фиг. 5(б), которую зашифровывают в третью часть зашифрованной последовательности вида "11001010" длиной 8 бит, показанную на фиг. 5(ж).

Особенностью зашифрования первой части кодированной последовательности является использованием предварительно сформированных криптографической функции и ключа, а также предварительно сформированных начальных значений первого и второго регистров кодирования, примерный вид которых показан на фиг. 3(б). Например, первая часть двоичной информационной последовательности вида "0111110", показанная на фиг. 5(a), арифметически кодируют в первую часть кодированной последовательности вида "11011000", показанную на фиг. 5(б), которую зашифровывают в первую часть зашифрованной последовательности вида "01111101" длиной 8 бит, показанную на фиг. 5(ж).

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

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

Способы вычисления значения первого и второго счетчиков частоты декодирования в соответствии с предварительно сформированным ключом и принятой двоичной информационной последовательностью заключаются в следующем. Первый счетчик частоты декодирования подсчитывает число декодируемых нулевых символов NN₀ в обработанной части принятой ИП. Второй счетчик частоты декодирования подсчитывает число декодируемых единичных символов NN₁,. Числа NN₀ и NN₁ являются неотрицательными ненулевыми целыми числами. При арифметическом декодировании также подсчитывают суммарное число декодируемых нулевых и единичных символов NN, равное NN=NN₀+NN₁. В начальном состоянии число декодируемых нулевых и _{единичных} символов еще не подсчитано, поэтому для первой части принятой двоичной информационной последовательности значения первого и второго счетчиков частоты декодирования вычисляют, например, в соответствии с ключом. Например, в соответствии с ключом первый и второй счетчики частоты декодирования принимают значения 11 и 2, соответственно. Поэтому суммарное число декодируемых нулевых и единичных символов NN принимает начальное значение, равное NN=13, как показано в верхней строке начального состояния арифметического декодирования с расшифрованием на фиг. 10 в начальный момент времени t=0. Значение первого счетчика частоты декодирования определяет значение вероятности декодируемых нулевых символов рр₀, а значение второго счетчика частоты декодирования определяет значение вероятности декодируемых единичных символов рр₁, при этом должно выполняться ограничение вида: pp₀+рр₁=1. Значение вероятности декодируемых нулевых символов рр₀ вычисляют по формуле вида а значение вероятности декодируемых единичных символов рр₁ вычисляют по формуле вида

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

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

Например, в начальный момент времени t=0 при значениях первого и второго счетчиков частоты декодирования NN₀=11 и NN₁=2, соответственно, начальная длина подинтервала единичных символов DD₁[0] имеет десятичное значение 38 или "00100110" в двоичном представлении, а начальная длина подинтервала нулевых символов DD₀[0] имеет десятичное значение 255-38=217 или "11011001" в двоичном представлении. Подинтервал единичных символов расположен, например, сверху подинтервала нулевых символов, как показано на фиг. 11. Верхнюю границу подинтервала нулевых символов декодирования обозначают как значение QQ, и данный подинтервал начинается снизу от нижней границы интервала декодирования арифметического декодирования до значения QQ исключительно, а подинтервал единичных символов декодирования простирается от значения QQ включительно до верхней границы интервала декодирования арифметического декодирования исключительно. Значение первого регистра декодирования устанавливают равным значению QQ. Например, в момент времени t=0 значение первого регистра декодирования равно десятичному значению 217 или "11011001" в двоичном представлении, как показано на фиг. 10 в первой строке при t=0. Во второй регистр декодирования записывают нижнее LL и верхнее НН значения интервала декодирования. Например, в момент времени t=0 во втором регистре декодирования последовательно записаны десятичные значения 0 и 255 или "00000000" и "11111111" в двоичном представлении, как показано на фиг. 10 в первой строке при t=0, а также как показано на фиг. 11 в начальном состоянии (Нач. сост.) арифметического декодирования.

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

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

На приемной стороне получена очередная часть зашифрованной последовательности, имеющая фиксированную длину в битах. Например, принята первая часть зашифрованной последовательности длиной R=8 бит вида "01111101", показанная на фиг. 8(a). Для расшифрования первой части принятой зашифрованной последовательности используют предварительно сформированные начальные значения первого и второго регистров декодирования, например, вида "10011011" и "01…011110", показанные на фиг. 3(в). Предварительно сформированную двоичную последовательность ключа побитно суммируют по модулю 2 с данными двоичными последовательностями начальных значений первого и второго регистров декодирования. Для этого первые R бит двоичной последовательности ключа побитно суммируют по модулю 2 с R битами начального значения двоичной последовательности первого регистра декодирования, затем последующие 2R бит двоичной последовательности ключа побитно суммируют по модулю 2 с 2R битами двоичной последовательности начального значения второго регистра декодирования, образуя оперативный ключ для расшифрования очередной части принятой ЗП, по своему предназначению подобный оперативному ключу в ближайшем аналоге (прототипе). Например, из предварительно сформированного ключа, показанного на фиг. 8(б), сформирован оперативный ключ для расшифрования первой части принятой ЗП в виде двоичной последовательности "1001110…0", показанный на фиг. 8(в). Расшифрование выполняют над очередной частью принятой ЗП длиной R бит, используя алгоритм расшифрования блока данных в режиме обратной связи по шифртексту или в режиме обратной связи по выходу. Результатом расшифрования очередной части принятой ЗП является очередная часть расшифрованной последовательности (РП) длиной R бит. Примерный вид первой части РП показан на фиг. 8(г) в виде двоичной последовательности "11011000" длиной 8 бит.

Перед арифметическим декодированием очередной части расшифрованной последовательности запоминают значения первого и второго регистров декодирования предыдущей части принятой двоичной информационной последовательности, которые используют для расшифрования следующей части, начиная со второй части, принятой зашифрованной последовательности. Значения первого и второго регистров декодирования первой части принятой двоичной информационной последовательности в момент t=0 запоминают для расшифрования второй части принятой зашифрованной последовательности. Например, значения первого и второго регистров декодирования первой части принятой двоичной информационной последовательности имеют вид "11011001" длиной 8 бит и "0000000011111111" длиной 16 бит, соответственно, как показано на фиг. 8(д) и 8(e).

При получении второй части зашифрованной последовательности ее расшифровывают с использованием предварительно сформированных криптографической функции и ключа, а также значений первого и второго регистров декодирования первой части принятой двоичной информационной последовательности. Например, принятую вторую часть ЗП вида "10000110" длиной 8 бит, показанную на фиг. 8(a), расшифровывают во вторую расшифрованной последовательности длиной R бит. Примерный вид второй части РП показан на фиг. 8(г) в виде двоичной последовательности "11101111" длиной 8 бит.

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

На вход арифметического декодирования поступает очередная часть расшифрованной последовательности, например, первая часть РП вида "11011000" длиной 8 бит. Как и ранее описанное арифметическое кодирование, операции арифметического декодирования используют такую же разрядность R выполняемых операций. Поэтому на вход арифметического декодирования считывают входные данные длиной R бит вида "11011000", что соответствует десятичному числу 216. Текущее значение считанной последовательности, указанное на фиг. 11 стрелкой, сравнивают с границами начального значения подинтервала декодирования нулевых символов DD₀[0], находящимися, например, в пределах от 0 до 217 и с границами начального значения подинтервала декодирования единичных символов DD₁[0], находящимися, например, в пределах от 217 до 255. В зависимости от того, в пределах какого подинтервала декодирования символов оказалось текущее значение считанной последовательности, принимают решение о декодировании очередного символа принятой двоичной информационной последовательности. Например, так как текущее значение считанной последовательности оказалось меньше значения QQ, то первый декодированный символ является нулевым и следующие границы интервала декодирования устанавливают соответствующими границам значения подинтервала декодирования нулевых символов DD₀[0]. В результате декодирования первого символа устанавливают нижнее значение интервала декодирования арифметического кодирования LL[l] равным предыдущему значению LL[0], например, LL[0]=0, а верхнее значение интервала декодирования арифметического кодирования НН[1] - равным значению QQ, например, HH[1]=217, как показано на фиг. 10 во второй строке при t=1. После декодирования каждого символа пересчитывают текущее значение вероятности декодируемых нулевых символов и текущее значение вероятности декодируемых нулевых символов, например, после декодирования первого символа, являющегося нулевым, по формуле вида и по формуле вида соответственно.

Устанавливают текущие длины подинтервалов декодирования единичных символов и нулевых символов и устанавливают текущее значение QQ=186 с двоичным представлением вида "10111010", как показано на фиг. 11. Таким образом уточняют значения первого и второго регистров декодирования.

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

После каждого уточнения значений первого и второго регистров декодирования самый левый бит двоичного представления значения LL сравнивают с самым левым битом двоичного представления значения HH, например, при t=1 вида "00000000" и "11011001", соответственно. При их совпадении выполняют нормализацию арифметического декодирования, иначе продолжают декодирование, например, декодируют второй символ первой части принятой двоичной информационной последовательности. На вход арифметического декодирования по прежнему считаны входные данные вида "11011000", что соответствует десятичному числу 216. Текущее значение считанной последовательности, указанное на фиг. 11 стрелкой, сравнивают с границами значения подинтервала декодирования нулевых символов DD₀[1], находящимися, например, в пределах от 0 до 186 и с границами значения подинтервала декодирования единичных символов DD₁[1], находящимися, например, в пределах от 186 до 217. В зависимости от того, в пределах какого подинтервала декодирования символов оказалось текущее значение считанной последовательности, принимают решение о декодировании очередного символа принятой двоичной информационной последовательности. Например, так как текущее значение считанной последовательности оказалось больше значения QQ, то второй декодированный символ является единичным и следующие границы интервала декодирования устанавливают соответствующими границам значения подинтервала декодирования единичных символов DD₁[1]. В результате декодирования второго символа устанавливают нижнее значение интервала декодирования арифметического кодирования LL[2] равным значению QQ, например, LL[1]=186, а верхнее значение интервала декодирования арифметического кодирования НН[2] - равным предыдущему значению HH[1], например, HH[2]=217, как показано на фиг. 10 в третьей строке при t=2. После декодирования каждого символа пересчитывают текущее значение вероятности декодируемого нулевого символа и декодируемого нулевого символа, например, после декодирования второго символа, являющегося единичным, по формуле вида и по формуле вида соответственно. Устанавливают текущие длины подинтервалов декодирования единичных символов и нулевых символов и таким образом уточняют значения первого и второго регистров декодирования.

Самый левый бит двоичного представления значения LL[2] сравнивают с самым левым битом двоичного представления значения HH[2], например, вида "10111010" и "11011001", соответственно. При их совпадении выполняют нормализацию арифметического декодирования: значение самого левого бита двоичных представлений значений LL[2] и НН[2] удаляют и двоичные символы двоичных представлений значений LL[2] и НН[2] сдвигают справа налево на один разряд и справа к ним в младший разряд дописывают по нулевому двоичному символу. Одновременно с этим, значение самого левого бита входных данных удаляют и двоичные символы входных данных сдвигают справа налево на один разряд и справа к ним дописывают следующий двоичный символ РП, например, первый символ второй части РП, являющийся единичным символом, как показано на фиг. 10 в четвертой строке "нормализация" и на фиг. 11. С учетом дописанного двоичного символа, входные данные приобретают двоичное представление "10110001" и десятичное значение 177. Переменная LL[2] принимает десятичное значение 116 и двоичное представление "01110100", а НН[2] - десятичное значение 178 и двоичное представление "10110010". Так как самые левые биты двоичных представлений LL[2] и HH[2] не совпадают, то повторного выполнения нормализации не требуется и выполняют декодирование третьего символа и т.д.

В результате арифметического декодирования первых по очереди двенадцати символов из первой и второй частей РП декодируют первые две части принятой двоичной информационной последовательности, которые по мере декодирования, передают получателю, как показано, например, на фиг. 10 и на фиг. 11. Вид первой части принятой двоичной информационной последовательности "0111110" и второй части принятой двоичной информационной последовательности "11000" показан на фиг. 8(ж). Видно, что на передающей стороне расшифрованные и арифметически декодированные части принятой двоичной информационной последовательности совпадают с соответствующими частями двоичной информационной последовательности, арифметически закодированными и зашифрованными на передающей стороне.

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

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

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

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

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

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

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