RU2595953C1 - Method for arithmetic encoding with encryption - Google Patents
Method for arithmetic encoding with encryption Download PDFInfo
- Publication number
- RU2595953C1 RU2595953C1 RU2015132451/08A RU2015132451A RU2595953C1 RU 2595953 C1 RU2595953 C1 RU 2595953C1 RU 2015132451/08 A RU2015132451/08 A RU 2015132451/08A RU 2015132451 A RU2015132451 A RU 2015132451A RU 2595953 C1 RU2595953 C1 RU 2595953C1
- Authority
- RU
- Russia
- Prior art keywords
- sequence
- values
- decoding
- coding
- registers
- Prior art date
Links
- 238000000034 method Methods 0.000 title claims abstract description 62
- 230000006870 function Effects 0.000 claims description 26
- 238000012546 transfer Methods 0.000 claims description 2
- 230000005540 biological transmission Effects 0.000 abstract description 10
- 238000005516 engineering process Methods 0.000 abstract description 3
- 239000000126 substance Substances 0.000 abstract 1
- 238000007906 compression Methods 0.000 description 18
- 230000006835 compression Effects 0.000 description 18
- 230000015572 biosynthetic process Effects 0.000 description 7
- 238000010606 normalization Methods 0.000 description 6
- 230000008859 change Effects 0.000 description 5
- 238000013144 data compression Methods 0.000 description 5
- 238000010586 diagram Methods 0.000 description 5
- 238000004891 communication Methods 0.000 description 4
- 230000008569 process Effects 0.000 description 4
- 230000009466 transformation Effects 0.000 description 4
- 238000013478 data encryption standard Methods 0.000 description 3
- 238000006243 chemical reaction Methods 0.000 description 2
- 239000013256 coordination polymer Substances 0.000 description 2
- 230000007423 decrease Effects 0.000 description 2
- 238000012545 processing Methods 0.000 description 2
- 238000012443 analytical study Methods 0.000 description 1
- 230000010365 information processing Effects 0.000 description 1
- 230000008054 signal transmission Effects 0.000 description 1
- 238000000844 transformation Methods 0.000 description 1
- 238000012795 verification Methods 0.000 description 1
Images
Landscapes
- Compression, Expansion, Code Conversion, And Decoders (AREA)
Abstract
Description
Изобретение относится к области электросвязи и информационных технологий, а именно к технике криптографической защиты избыточной двоичной информации при обмене данными по общедоступным каналам передачи, в которых нарушитель может осуществлять действия по несанкционированному чтению информации.The invention relates to the field of telecommunications and information technology, in particular to the technique of cryptographic protection of excess binary information when exchanging data via publicly available transmission channels in which the intruder can carry out actions for unauthorized reading of information.
Заявленное изобретение может быть использовано для обеспечения конфиденциальности сжимаемой избыточной двоичной информации, передаваемой в современных информационно-телекоммуникационных системах.The claimed invention can be used to ensure the confidentiality of compressible redundant binary information transmitted in modern information and telecommunication systems.
Известны способы шифрования двоичной информации, описанные, например, в государственном стандарте 28147-89. Системы обработки информации. Зашита криптографическая. Алгоритм криптографического преобразования. - М.: Госстандарт СССР. 1989, стр. 9-14. В данных способах у отправителя двоичную последовательность (ДП) разделяют у отправителя на последовательные блоки длиной n бит, где обычно n=64. По криптографической функции с использованием заранее сформированного для отправителя и получателя секретного ключа (СК) последовательно из каждого блока ДП с учетом предыдущего зашифрованного блока формируют зашифрованный текущий блок до тех пор, пока поступают блоки ДП. Зашифрованные текущие блоки передают по каналу связи получателю. Принятые получателем зашифрованные текущие блоки по криптографической функции с использованием СК последовательно расшифровывают с учетом предыдущего зашифрованного принятого блока до тех пор, пока поступают зашифрованные блоки.Known methods for encrypting binary information, described, for example, in state standard 28147-89. Information processing systems. Cryptographic protection. Cryptographic conversion algorithm. - M.: Gosstandart of the USSR. 1989, pp. 9-14. In these methods, the sender's binary sequence (DP) is divided at the sender into consecutive blocks of length n bits, where usually n = 64. According to the cryptographic function using a secret key (SC) preformed for the sender and recipient, the encrypted current block is formed sequentially from each block of the DP, taking into account the previous encrypted block, until the DP blocks arrive. The encrypted current blocks are transmitted over the communication channel to the recipient. The encrypted current blocks received by the recipient according to the cryptographic function using the SC are sequentially decrypted taking into account the previous encrypted received block until the encrypted blocks arrive.
Недостатками указанных аналогов являются:The disadvantages of these analogues are:
- неэффективное использование пропускной способности каналов передачи, вызванное невозможностью использования избыточности двоичной информации после ее шифрования;- inefficient use of bandwidth transmission channels caused by the inability to use redundancy of binary information after its encryption;
- использование нарушителем неудаленной избыточности двоичной информации облегчает ему несанкционированное чтение зашифрованной информации.- the use by the intruder of the remote redundancy of binary information facilitates unauthorized reading of encrypted information.
Известен также способ арифметического кодирования с шифрованием по патенту РФ 2226041 МПК H04L 9/08 (2006.01) от 01.11.2001. Данный способ заключается в том, что на передающей стороне исходная информация искажается с помощью ключевой последовательности, а на приемной стороне искаженная информация восстанавливается с помощью ключевой последовательности с посимвольной обработкой, отличающийся тем, что входные двоичные данные разбивают на блоки фиксированной длины и кодируют поочередно, подвергая их преобразованию методом арифметического кодирования с криптографическими функциями F1, F2 иThere is also known a method of arithmetic coding with encryption according to the patent of the Russian Federation 2226041 IPC
F3, зависящими от указанной ключевой последовательности, в качестве криптографического преобразования F2 и F3 выбирают псевдослучайные функции, на каждом шаге кодирования вводят данные для арифметического кодирования посимвольно и кодируют их с использованием таблицы символов, реализующих преобразование F2 и таблицы интервалов вероятности появления символов, реализующих преобразование F3, на каждом шаге кодирования обновляют таблицу символов путем извлечения из нее N ее первых значений, разбивают их на пары, переставляют местами извлеченные символы в таблице символов, а также на каждом шаге кодирования из таблицы интервалов вероятности появления каждого символа извлекают N ее первых значений, разбивают их на пары, затем выполняют обмен интервалами вероятности появления в указанной таблице, после чего преобразованные входные данные передают в блок выходных данных.F 3 , depending on the indicated key sequence, pseudo-random functions are selected as the cryptographic transformation F 2 and F 3 , at each coding step, data for arithmetic coding is entered character-by-character and encoded using a symbol table that implements F 2 transformation and a table of intervals of probability of occurrence of symbols that implement the F 3 transformation, at each coding step, the symbol table is updated by extracting N of its first values from it, breaking them into pairs, rearranging the places The marked characters in the symbol table, as well as at each coding step, extract N first values from the table of probability intervals for the appearance of each symbol, divide them into pairs, then exchange intervals of probability of occurrence in the specified table, after which the converted input data is transferred to the output data block .
В этом патенте на каждом шаге арифметического кодирования с шифрованием входные двоичные данные разбивают на блоки фиксированной длины, которые представляют собой недвоичные символы, таблицу интервалов вероятности появления различных символов криптографически изменяют с использованием криптографических преобразований по ключу, что существенно изменяет истинные интервалы вероятности появления этих символов и приводит к невозможности существенного сжатия избыточных входных данных при их арифметическом кодировании с шифрованием. Недостатками этого аналога является ограничение входных данных только последовательностями, состоящими из недвоичных символов, а также сравнительно малая степень удаления избыточности шифруемой информации, что приводит к неэффективному использованию пропускной способности каналов передачи зашифрованной информации.In this patent, at each step of the arithmetic coding with encryption, the input binary data is divided into blocks of fixed length, which are non-binary characters, the table of the intervals of the probability of occurrence of various symbols is cryptographically changed using cryptographic transformations by key, which significantly changes the true intervals of the probability of occurrence of these symbols and It leads to the impossibility of significant compression of redundant input data during their arithmetic encoding with encryption. The disadvantages of this analogue are the limitation of the input data only to sequences consisting of non-binary characters, as well as the relatively small degree of removal of redundancy of encrypted information, which leads to inefficient use of the bandwidth of the transmission channels of encrypted information.
Наиболее близким по своей технической сущности к заявленному способу арифметического кодирования с шифрованием является способ арифметического кодирования с шифрованием по патенту США 7664267 МПК H04L 9/00 (2006.01) от 30.06.2005. Способ-прототип арифметического кодирования с шифрованием заключается в предварительном формировании для передающей и приемной сторон главного ключа, на передающей стороне от отправителя получают очередную часть двоичной информационной последовательности, генерируют случайную битовую последовательность, формируют оперативный ключ из главного ключа и случайной битовой последовательности, вычисляют значения первого и второго счетчиков частоты кодирования в соответствии с предварительно сформированным главным ключом, оперативным ключом и двоичной информационной последовательностью, если значение первого счетчика частоты кодирования больше значения второго счетчика частоты кодирования, то меняют местами эти значения, устанавливают значения первого и второго регистров кодирования в соответствии со значениями первого и второго счетчиков частоты кодирования, выполняют арифметическое кодирование очередной части информационной последовательности, уточняют значения первого и второго регистров кодирования, формируют очередную часть зашифрованной последовательности из очередной части закодированной последовательности, передают очередную часть зашифрованной последовательности на приемную сторону и выполняют перечисленные действия до тех пор, пока поступают очередные части двоичной информационной последовательности, на приемной стороне получают очередную часть зашифрованной последовательности, арифметически декодируют случайную битовую последовательность из первой части принятой двоичной информационной последовательности, вычисляют значения первого и второго счетчиков частоты декодирования в соответствии с предварительно сформированным главным ключом, декодированной случайной битовой последовательностью и принятой двоичной информационной последовательностью, если значение первого счетчика частоты декодирования больше значения второго счетчика частоты декодирования, то меняют местами эти значения, устанавливают значения первого и второго регистров декодирования в соответствии со значениями первого и второго счетчиков частоты декодирования, выполняют арифметическое декодирование очередной части принятой зашифрованной последовательности, уточняют значения первого и второго регистров декодирования, формируют очередную часть принятой двоичной информационной последовательности из очередной части декодированной последовательности, передают получателю очередную часть принятой двоичной информационной последовательности и выполняют перечисленные действия на приемной стороне до тех пор, пока поступают очередные части зашифрованной последовательности.The closest in technical essence to the claimed method of arithmetic coding with encryption is the method of arithmetic coding with encryption according to US patent 7664267 IPC
Способ-прототип арифметического кодирования с шифрованием обеспечивает высокую защищенность к попыткам нарушителя несанкционированного чтения зашифрованной информации. Общая схема способа-прототипа арифметического кодирования с шифрованием представлена на фиг. 1. На передающей стороне выполняют арифметическое кодирование с зашифрованием двоичной информационной последовательности (ИП), а на приемной стороне - арифметическое декодирование с ее расшифрованием. На передающей стороне очередные части двоичной информационной последовательности поступают на вход кодера с зашифрованием 1. В процессе арифметического кодирования очередных частей двоичной информационной последовательности последовательно уточняют значения первого и второго счетчиков частоты кодирования, составляющие модель кодирования, реализуемой блоком модели кодирования 2. Чем ближе значения первого и второго счетчиков частоты кодирования к действительной вероятности появления нулевых символов и единичных символов, соответственно, сжимаемой избыточной информационной последовательности, тем выше коэффициент сжатия арифметического кодирования этой информационной последовательности.The prototype method of arithmetic coding with encryption provides high security for attempts by an intruder to unauthorized reading of encrypted information. The general scheme of the prototype arithmetic coding with encryption is shown in FIG. 1. On the transmitting side, arithmetic coding is performed with encryption of the binary information sequence (IP), and on the receiving side, arithmetic decoding with its decryption is performed. On the transmitting side, the next parts of the binary information sequence are sent to the input of the encoder with
Особенностью способа-прототипа арифметического кодирования с шифрованием является генерирование случайной битовой последовательности с использованием генератора случайных чисел 3 (ГСЧ), которая вместе с главным ключом используют для криптографического изменения модели кодирования, непредсказуемого для нарушителя, пытающегося при перехвате в канале передачи 4 зашифрованной последовательности (ЗП) вычислить из нее двоичную информационную последовательность без знания конфиденциального ключа.A feature of the prototype arithmetic coding with encryption is the generation of a random bit sequence using a random number generator 3 (RNG), which, together with the master key, is used to cryptographically change the encoding model that is unpredictable for an intruder trying to intercept an encrypted sequence in the transmission channel 4 (GP ) calculate from it a binary information sequence without knowing the confidential key.
На приемной стороне очередные части принятой зашифрованной последовательности поступают на вход декодера с расшифрованием 6. Сгенерированная отправителем случайная битовая последовательность в составе зашифрованной последовательности передается получателю, который выделяет ее в декодере случайной последовательности 7 и вместе с главным ключом используют для криптографического изменения модели декодирования, идентичного криптографическому изменению модели кодирования. Модель декодирования реализуется блоком модели декодирования 8.On the receiving side, the next parts of the received encrypted sequence are input to the decoder with
Общий принцип использования случайной битовой последовательности для шифрования двоичных информационных последовательностей известен в науке и технике и описан, например, в книге М.А. Иванов "Криптографические методы защиты информации в компьютерных системах и сетях". - М.: КУДИЦ-ОБРАЗ, 2001, стр. 254-256. Совокупность таких способов шифрования двоичных информационных последовательностей известна как способы вероятностного (рандомизированного) шифрования двоичных информационных последовательностей, обеспечивающих повышение защищенности к попыткам нарушителя несанкционированного чтения зашифрованной информации. Данное повышение защищенности обусловлено тем, что изменяющаяся каждый раз случайная битовая последовательность при арифметическом кодировании с зашифрованием существенно повышает непредсказуемость для нарушителя результата кодирования с зашифрованием, включая случай известности для нарушителя кодируемой двоичной информационной последовательности.The general principle of using a random bit sequence for encrypting binary information sequences is known in science and technology and is described, for example, in M.A. Ivanov "Cryptographic methods of information security in computer systems and networks." - M.: KUDITS-IMAGE, 2001, p. 254-256. The combination of such methods for encrypting binary information sequences is known as probabilistic (randomized) encryption methods for binary information sequences, which provide increased security for attempts by an unauthorized person to read encrypted information. This increase in security is due to the fact that a random bit sequence that changes every time during arithmetic encoding with encryption significantly increases the unpredictability for the intruder of the encrypted encoding result, including the case of fame for the intruder of the encoded binary information sequence.
Однако в данном способе-прототипе арифметического кодирования с шифрованием необходимость передачи случайной битовой последовательности по каналу передачи, а также криптографическое изменение модели кодирования в соответствии со случайной битовой последовательностью, несогласованной со статистическими характеристиками сжимаемой избыточной информационной последовательности, приводит к существенному снижению коэффициента сжатия арифметического кодирования двоичной информационной последовательности. В частности, авторы способа-прототипа указывают на этот недостаток, описывая в реферате, что предлагаемый ими способ может обеспечить сжатие кодируемых с шифрованием двоичных информационных последовательностей не более чем в 2 раза. В противоположность этому известно, что арифметическое кодирование достаточно длинных избыточных двоичных информационных последовательностей способно обеспечить удаление из них избыточности вплоть до значения их энтропии и достичь значений коэффициента сжатия вплоть до десятков раз, как описано, например, в книге Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин "Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео". - М.: ДИАЛОГ-МИФИ, 2002, стр. 35-49.However, in this prototype method of arithmetic coding with encryption, the need to transmit a random bit sequence over the transmission channel, as well as a cryptographic change in the coding model in accordance with a random bit sequence that is inconsistent with the statistical characteristics of the compressed redundant information sequence, leads to a significant decrease in the compression coefficient of binary arithmetic coding informational sequence. In particular, the authors of the prototype method indicate this drawback, describing in the abstract that their proposed method can provide compression of binary information sequences encoded with encryption no more than 2 times. In contrast to this, it is known that arithmetic coding of sufficiently long redundant binary information sequences can ensure the removal of redundancy from them up to the value of their entropy and achieve values of compression coefficient up to tens of times, as described, for example, in the book by D. Vatolin, A. Ratushnyak, M. Smirnov, V. Yukin "Data compression methods. Device archivers, image and video compression." - M.: DIALOGUE-MEPhI, 2002, p. 35-49.
Таким образом, недостатком ближайшего аналога (прототипа) является сравнительно малая степень удаления избыточности зашифрованной информации, что приводит к неэффективному использованию пропускной способности каналов передачи зашифрованной информации.Thus, the disadvantage of the closest analogue (prototype) is the relatively small degree of removal of redundancy of encrypted information, which leads to inefficient use of bandwidth transmission channels of encrypted information.
Техническим результатом заявляемого решения является арифметическое кодирование с шифрованием избыточной двоичной информационной последовательности с повышением степени удаления избыточности зашифрованной информации.The technical result of the proposed solution is arithmetic coding with encryption of the redundant binary information sequence with an increase in the degree of removal of redundancy of encrypted information.
Указанный технический результат в заявляемом способе арифметического кодирования с шифрованием достигается тем, что в известном способе арифметического кодирования с шифрованием, заключающимся в том, что предварительно для передающей и приемной сторон формируют ключ, на передающей стороне от отправителя получают очередную часть двоичной информационной последовательности, вычисляют значения первого и второго счетчиков частоты кодирования в соответствии с предварительно сформированным ключом и двоичной информационной последовательностью, устанавливают значения первого и второго регистров кодирования в соответствии со значениями первого и второго счетчиков частоты кодирования, выполняют арифметическое кодирование очередной части двоичной информационной последовательности, уточняют значения первого и второго регистров кодирования, передают очередную часть зашифрованной последовательности на приемную сторону и выполняют перечисленные действия до тех пор, пока поступают очередные части двоичной информационной последовательности, на приемной стороне получают очередную часть зашифрованной последовательности, вычисляют значения первого и второго счетчиков частоты декодирования в соответствии с предварительно сформированным ключом и принятой двоичной информационной последовательностью, устанавливают значения первого и второго регистров декодирования в соответствии со значениями первого и второго счетчиков частоты декодирования, выполняют арифметическое декодирование очередной части последовательности, уточняют значения первого и второго регистров декодирования, передают получателю очередную часть принятой двоичной информационной последовательности и выполняют перечисленные действия на приемной стороне до тех пор, пока поступают очередные части зашифрованной последовательности, дополнительно для передающей и приемной сторон предварительно формируют криптографическую функцию. На передающей стороне после уточнения значений первого и второго регистров кодирования зашифровывают очередную часть кодированной последовательности с использованием предварительно сформированных криптографической функции и ключа, а также значений первого и второго регистров кодирования предыдущей части двоичной информационной последовательности, причем зашифровывают первую часть кодированной последовательности с использованием предварительно сформированных криптографической функции и ключа, а также предварительно сформированных начальных значений первого и второго регистров кодирования. На приемной стороне после вычисления значений первого и второго счетчиков частоты декодирования расшифровывают очередную часть принятой зашифрованной последовательности с использованием предварительно сформированных криптографической функции и ключа, а также значений первого и второго регистров декодирования предыдущей части принятой двоичной информационной последовательности, выполняют арифметическое декодирование очередной части расшифрованной последовательности, причем расшифровывают первую часть принятой зашифрованной последовательности с использованием предварительно сформированных криптографической функции и ключа, а также предварительно сформированных начальных значений первого и второго регистров декодирования.The specified technical result in the inventive method of arithmetic coding with encryption is achieved by the fact that in the known method of arithmetic coding with encryption, which means that a key is formed for the transmitting and receiving sides first, the next part of the binary information sequence is received from the sender, the values are calculated the first and second coding frequency counters in accordance with a pre-formed key and a binary information sequence In fact, set the values of the first and second coding registers in accordance with the values of the first and second coding frequency counters, perform arithmetic coding of the next part of the binary information sequence, specify the values of the first and second coding registers, transfer the next part of the encrypted sequence to the receiving side and perform the above steps until as long as the next parts of the binary information sequence arrive, on the receiving side we get the next part of the encrypted sequence is calculated, the values of the first and second decoding frequency counters are calculated in accordance with the previously generated key and the received binary information sequence, the values of the first and second decoding registers are set in accordance with the values of the first and second decoding frequency counters, arithmetic decoding of the next part of the sequence , specify the values of the first and second decoding registers, transmit receive lu another part of the received binary information sequence and perform these actions on the reception side as long as the received encrypted portion of the next sequence, further for transmitting and receiving parties preformed cryptographic function. On the transmitting side, after specifying the values of the first and second encoding registers, the next part of the encoded sequence is encrypted using the pre-generated cryptographic function and key, as well as the values of the first and second encoding registers of the previous part of the binary information sequence, and the first part of the encoded sequence is encrypted using the pre-generated cryptographic function and key, as well as preformed OF DATA initial values of the first and second encoding registers. On the receiving side, after calculating the values of the first and second counters of the decoding frequency, the next part of the received encrypted sequence is decrypted using the pre-generated cryptographic function and key, as well as the values of the first and second decoding registers of the previous part of the received binary information sequence, arithmetic decoding of the next part of the decrypted sequence is performed, and decrypt the first part of the accepted encrypted sequences using pre-formed cryptographic functions and keys, as well as pre-formed initial values of the first and second decoding registers.
В предлагаемой совокупности действий при арифметическом кодировании с шифрованием на передающей стороне сначала выполняют собственно арифметическое кодирование в соответствии со значениями первого и второго счетчиков частоты кодирования, которые адаптируются под действительные значения вероятности появления нулевых символов и единичных символов, соответственно, сжимаемой избыточной двоичной информационной последовательности, при этом значения первого и второго счетчиков частоты кодирования не искажаются случайной битовой последовательностью, несогласованной со статистическими характеристиками сжимаемой избыточной информационной последовательности. Благодаря этому коэффициент сжатия избыточной двоичной информационной последовательности обеспечивается существенно выше, чем при арифметическом кодировании с шифрованием при криптографическом изменении значений первого и второго счетчиков частоты кодирования в соответствии со случайной битовой последовательностью, как предлагается в ближайшем аналоге (прототипе). В процессе арифметического кодирования в соответствии со значениями первого и второго счетчиков частоты кодирования устанавливают значения первого и второго регистров кодирования, которые уточняются по результатам арифметического кодирования каждой очередной части двоичной информационной последовательности.In the proposed set of actions for arithmetic coding with encryption on the transmitting side, the arithmetic coding is first performed in accordance with the values of the first and second counters of the coding frequency, which adapt to the actual values of the probability of occurrence of zero characters and single characters, respectively, of a compressed redundant binary information sequence, when the values of the first and second counters of the coding frequency are not distorted by a random bit consistency inconsistent with the statistical characteristics of a compressible excess information sequence. Due to this, the compression ratio of the excess binary information sequence is provided significantly higher than with arithmetic coding with encryption during cryptographic changes in the values of the first and second coding frequency counters in accordance with a random bit sequence, as proposed in the closest analogue (prototype). In the process of arithmetic coding, in accordance with the values of the first and second counters of the coding frequency, the values of the first and second coding registers are set, which are refined by the results of arithmetic coding of each subsequent part of the binary information sequence.
Затем выполняют шифрование кодированной последовательности с использованием предварительно сформированных криптографической функции и ключа, причем для повышения степени непредсказуемости шифрования для нарушителя при зашифровании очередной части кодированной последовательности используют переменные значения первого и второго регистров кодирования. Чем выше коэффициент сжатия избыточной двоичной информационной последовательности, тем ближе статистические характеристики значений первого и второго регистров кодирования к характеристикам случайной битовой последовательности, используемой в ближайшем аналоге (прототипе). В предлагаемом способе изменяющиеся во времени значения первого и второго регистров кодирования используют для повышения защищенности зашифрованной информационной последовательности образом, эквивалентным использованию случайной битовой последовательности в ближайшем аналоге (прототипе), но эти значения не надо передавать по каналу передачи, так как при использовании одного и того же конфиденциального ключа в процессе арифметического декодирования на приемной стороне формируют значения первого и второго регистров декодирования, идентичные значениям первого и второго регистров кодирования на передающей стороне.Then, the encrypted sequence is encrypted using the pre-formed cryptographic function and key, and to increase the degree of encryption unpredictability for the intruder, when encrypting the next part of the encoded sequence, variable values of the first and second encoding registers are used. The higher the compression ratio of the excess binary information sequence, the closer the statistical characteristics of the values of the first and second coding registers to the characteristics of the random bit sequence used in the closest analogue (prototype). In the proposed method, the time-varying values of the first and second coding registers are used to increase the security of the encrypted information sequence in a manner equivalent to using a random bit sequence in the closest analogue (prototype), but these values do not need to be transmitted over the transmission channel, since when using the same the confidential key in the process of arithmetic decoding on the receiving side form the values of the first and second decoding registers, identical to the values of the first and second coding registers on the transmitting side.
Поэтому указанная новая совокупность действий позволяет при выполнении арифметического кодирования с шифрованием избыточной двоичной информационной последовательности повысить степень удаления избыточности зашифрованной информации.Therefore, this new set of actions allows, when performing arithmetic coding with encryption of the redundant binary information sequence, to increase the degree of redundancy of the encrypted information.
Заявленный способ поясняется чертежами, на которых показаны:The claimed method is illustrated by drawings, which show:
- на фиг. 1 - общая схема арифметического кодирования с зашифрованием и арифметического декодирования с расшифрованием в ближайшем аналоге (прототипе);- in FIG. 1 is a general diagram of arithmetic coding with encryption and arithmetic decoding with decryption in the closest analogue (prototype);
- на фиг. 2 - общая схема арифметического кодирования с зашифрованием и арифметического декодирования с расшифрованием в предлагаемом способе;- in FIG. 2 - a General scheme of arithmetic coding with encryption and arithmetic decoding with decryption in the proposed method;
- на фиг. 3 - рисунки, поясняющие предварительное формирование ключа и криптографической функции;- in FIG. 3 - figures explaining the preliminary formation of the key and cryptographic function;
- на фиг. 4 - алгоритм арифметического кодирования с зашифрованием;- in FIG. 4 - arithmetic coding algorithm with encryption;
- на фиг. 5 - временные диаграммы арифметического кодирования с зашифрованием;- in FIG. 5 - time diagrams of arithmetic coding with encryption;
- на фиг. 6 - таблица состояний арифметического кодирования первых трех очередных частей двоичной информационной последовательности;- in FIG. 6 is a state table of arithmetic coding of the first three successive parts of a binary information sequence;
- на фиг. 7 - временные диаграммы арифметического кодирования первой части двоичной информационной последовательности;- in FIG. 7 is a timing diagram of arithmetic coding of the first part of a binary information sequence;
- на фиг. 8 - временные диаграммы арифметического декодирования с расшифрованием;- in FIG. 8 - time diagrams of arithmetic decoding with decryption;
- на фиг. 9 - алгоритм арифметического декодирования с расшифрованием;- in FIG. 9 - arithmetic decoding algorithm with decryption;
- на фиг. 10 - таблица состояний арифметического декодирования первых двух частей принятой двоичной информационной последовательности;- in FIG. 10 is a state table of arithmetic decoding of the first two parts of the received binary information sequence;
- на фиг. 11 - временные диаграммы арифметического декодирования первых двух частей принятой двоичной информационной последовательности;- in FIG. 11 is a timing diagram of arithmetic decoding of the first two parts of a received binary information sequence;
- на фиг. 12 - значения длины и коэффициента сжатия арифметически кодированных с шифрованием избыточных двоичных информационных последовательностей для способа-прототипа и заявленного способа.- in FIG. 12 - values of the length and compression ratio of arithmetically encoded with encryption of excess binary information sequences for the prototype method and the claimed method.
Реализация заявленного способа представлена на примере системы арифметического кодирования с шифрованием, обеспечивающей на передающей стороне арифметическое кодирование с зашифрованием двоичной информационной последовательности, а на приемной стороне - ее арифметическое декодирование с расшифрованием. На передающей стороне по мере арифметического кодирования очередных частей информационной последовательности уточняют значения первого и второго счетчиков частоты кодирования, составляющие модель кодирования, а также выполняют криптографическое изменение модели кодирования с использованием конфиденциального ключа. Значения первого и второго счетчиков частоты кодирования с выхода блока модели кодирования 2 поступают на вход арифметического кодера 1, в котором в соответствии с этими значениями и текущими состояниями регистров кодирования очередную часть двоичной информационной последовательности сжимают в очередную часть кодированной последовательности. Затем очередную часть кодированной последовательности зашифровывают в блоке зашифрования 4 в соответствии с значением ключа и значениями первого и второго регистров кодирования предыдущей части двоичной информационной последовательности, запомненными в блоке памяти регистров кодирования 3.The implementation of the claimed method is presented on the example of an arithmetic coding system with encryption, which provides arithmetic coding with encryption of the binary information sequence on the transmitting side, and its arithmetic decoding with decryption on the receiving side. On the transmitting side, as the arithmetic coding of the next parts of the information sequence, the values of the first and second coding frequency counters that make up the coding model are clarified, and a cryptographic change of the coding model is performed using a confidential key. The values of the first and second coding frequency counters from the output of the
С выхода блока зашифрования 4 очередную часть зашифрованной последовательности передают на приемную сторону по незащищенному каналу передачи 5. К каналу передачи может подключаться нарушитель, который с использованием блока перехвата зашифрованной последовательности 6 пытается осуществить несанкционированное чтение информационной последовательности.From the output of the
Принятая на приемной стороне очередная часть зашифрованной последовательности поступает на вход блока расшифрования 7, где ее расшифровывают в соответствии со значением ключа и значениями первого и второго регистров декодирования предыдущей части двоичной информационной последовательности, запомненными в блоке памяти регистров декодирования 8. Очередную часть расшифрованной последовательности арифметически декодируют в декодере 10 с учетом значений первого и второго счетчиков частоты декодирования, составляющих модель декодирования, формирующейся в блоке модели декодирования 9. В процессе кодирования и декодирования значения первого и второго счетчиков частоты кодирования и значения первого и второго счетчиков частоты декодирования при обработке каждой очередной части информационной последовательности синхронно изменяют с использованием конфиденциального ключа.The next part of the encrypted sequence received on the receiving side is fed to the input of the
На передающей стороне по мере арифметического кодирования очередных частей информационной последовательности уточняют значения первого и второго счетчиков частоты кодирования, составляющих модель кодирования, а также выполняют криптографическое изменение модели кодирования с использованием конфиденциального ключа. В процессе арифметического кодирования с зашифрованием и арифметического декодирования с расшифрованием также синхронно меняются значения первого и второго регистров кодирования и соответствующие значения первого и второго регистров декодирования.On the transmitting side, as the arithmetic coding of the next parts of the information sequence, the values of the first and second coding frequency counters constituting the coding model are clarified, and a cryptographic change of the coding model is performed using a confidential key. In the process of arithmetic encoding with encryption and arithmetic decoding with decryption, the values of the first and second encoding registers and the corresponding values of the first and second decoding registers are also synchronously changed.
В способе арифметического кодирования с шифрованием реализуется следующая последовательность действий.In the method of arithmetic coding with encryption, the following sequence of actions is implemented.
Предварительное формирование для передающей и приемной сторон ключа заключается в следующем. Ключ в виде двоичной последовательности (ДП) формируют с использованием генератора случайных импульсов, генерирующего случайные равновероятные нулевые и единичные импульсы, независимые друг от друга. Способы формирования случайным выбором символов двоичной последовательности ключа известны и описаны, например, в книге: Д. Кнут "Искусство программирования на ЭВМ". - М.: Мир, 1977, т. 2, стр. 22. Длина ДП ключа в битах должна быть не менее 256 бит, что описано, например, в ГОСТ 28147-89. Данный ключ является конфиденциальным и известен только на передающей и приемной стороне. Примерный вид ключа показан на фиг.3(a). Единичные значения битов на фигурах показаны в виде заштрихованных импульсов, нулевые значения битов - в виде незаштрихованных импульсов.Preliminary formation for the transmitting and receiving sides of the key is as follows. The key in the form of a binary sequence (DP) is formed using a random pulse generator that generates random equally probable zero and single pulses, independent of each other. Methods of randomly generating binary key sequence characters are known and described, for example, in the book: D. Knut, "The Art of Computer Programming." - M .: Mir, 1977, t. 2, p. 22. The length of the key in bits should be at least 256 bits, which is described, for example, in GOST 28147-89. This key is confidential and is known only on the transmitting and receiving side. An exemplary key view is shown in FIG. 3 (a). Single bit values in the figures are shown in the form of shaded pulses, zero bit values in the form of unshaded pulses.
Способы предварительного формирования для передающей стороны начальных значений первого и второго регистров кодирования также используют генератор случайных импульсов, генерирующий случайные равновероятные нулевые и единичные импульсы, независимые друг от друга. Случайным образом формируют начальное значение первого регистра кодирования в виде двоичной последовательности длины R битов, равной разрядности устройства, реализующего арифметическое кодирование, и начальное значение второго регистра кодирования в виде двоичной последовательности удвоенной длины 2R битов. Примерный вид начального значения первого регистра кодирования (Нач. знач. 1-го рег. код.) в виде 8-битовой ДП "10011011" и начального значения второго регистра кодирования (Нач. знач. 2-го рег.код.) в виде 16-битовой ДП "01…011110" при R=8 бит показан на фиг. 3(б). Предварительно сформированные для приемной стороны начальные значения первого и второго регистров декодирования полностью совпадают с соответствующими предварительно сформированными начальными значениями первого и второго регистров кодирования. Примерный вид начального значения первого регистра декодирования (Нач. знач. 1-го рег. декод.) в виде 8-битовой ДП "10011011" и начального значения второго регистра декодирования (Нач. знач. 2-го рег. декод.) в виде 16-битовой ДП "01…011110" при R=8 бит показан на фиг. 3(в).Methods of preliminary formation for the transmitting side of the initial values of the first and second coding registers also use a random pulse generator that generates random equally probable zero and unit pulses independent of each other. Randomly form the initial value of the first coding register in the form of a binary sequence of length R bits equal to the bit depth of the device that implements arithmetic coding, and the initial value of the second coding register in the form of a binary sequence of doubled length 2R bits. An approximate form of the initial value of the first coding register (Start value of the 1st reg code) in the form of an 8-bit DP "10011011" and the initial value of the second coding register (Start value of the 2nd reg code) in the form The 16-bit DP "01 ... 011110" with R = 8 bits is shown in FIG. 3 (b). The initial values of the first and second decoding registers pre-formed for the receiving side completely coincide with the corresponding pre-formed initial values of the first and second encoding registers. An approximate form of the initial value of the first decoding register (Start value of the 1st reg. Deco.) In the form of an 8-bit DP "10011011" and the initial value of the second decoding register (Start value of the 2nd reg. Deco.) In the form The 16-bit DP "01 ... 011110" with R = 8 bits is shown in FIG. 3 (c).
Способы предварительного формирования для передающей и приемной сторон криптографической функции известны и описаны, например, в книге М.Д. Смид, Д.К. Бранстед "Стандарт шифрования данных: Прошлое и будущее". ТИИЭР, 1988, - т. 76, №5, стр. 49. Они заключаются в формировании криптографической функции, используя алгоритм шифрования данных DES в режиме обратной связи по шифртексту или в режиме обратной связи по выходу. При этом шифрование выполняют над очередной частью кодированной последовательности (КП) длиной R бит. Примерный вид очередной части кодированной последовательности (Очер. часть КП) показан на фиг. 3(г). В результате использования предварительно сформированных криптографической функции, ключа и первого и второго регистров кодирования предыдущей части двоичной информационной последовательности формируют очередную часть зашифрованной последовательности (ЗП). Данные способы обеспечивают формирование каждого битового значения очередной части зашифрованной последовательности в зависимости от каждого битового значения очередной части зашифрованной, от каждого бита ключа и от каждого бита первого и второго регистров кодирования предыдущей части двоичной информационной последовательности. Примерный вид очередной части зашифрованной последовательности (Очер. часть ЗП) длиной R бит показан на фиг. 3(д).Methods of preliminary formation of a cryptographic function for the transmitting and receiving sides are known and described, for example, in the book of M.D. Smid, D.K. Branstead "Data Encryption Standard: Past and Future." TIIER, 1988, v. 76, No. 5, p. 49. They consist in the formation of a cryptographic function using the DES data encryption algorithm in ciphertext feedback mode or in output feedback mode. In this case, encryption is performed on the next part of the encoded sequence (KP) of length R bits. An exemplary view of the next part of the encoded sequence (Part. Part of the CP) is shown in FIG. 3 (g). As a result of using the pre-formed cryptographic function, the key, and the first and second coding registers of the previous part of the binary information sequence, the next part of the encrypted sequence (GP) is formed. These methods provide the formation of each bit value of the next part of the encrypted sequence, depending on each bit value of the next part of the encrypted, from each bit of the key and from each bit of the first and second encoding registers of the previous part of the binary information sequence. An exemplary view of the next part of the encrypted sequence (Outline. Part of the RFP) of length R bits is shown in FIG. 3 (d).
Алгоритм арифметического кодирования с шифрованием представлен на фигуре 4.The arithmetic encoding algorithm with encryption is presented in figure 4.
На передающей стороне от отправителя получают очередную часть двоичной информационной последовательности. Кодирование информационной последовательности начинается с момента поступления первого ее бита и при кодировании первых битов очередной части двоичной информационной последовательности не требуется получения от отправителя целиком очередной части этой последовательности. Примерный вид первых трех очередных частей двоичной информационной последовательности (ИП) в виде двоичной последовательности "0111110110000100010001001" длиной 25 бит показан на фигуре 5(a).On the transmitting side, the next part of the binary information sequence is received from the sender. The encoding of an information sequence begins from the moment its first bit arrives, and when encoding the first bits of the next part of the binary information sequence, it is not required to receive the entire next part of this sequence from the sender. An exemplary view of the first three successive parts of a binary information sequence (IP) in the form of a binary sequence "0111110110000100010001001" with a length of 25 bits is shown in figure 5 (a).
Способы вычисления значения первого и второго счетчиков частоты кодирования в соответствии с предварительно сформированным ключом и двоичной информационной последовательностью заключаются в следующем. Первый счетчик частоты кодирования подсчитывает число кодируемых нулевых символов N0 в обработанной части ИП. Второй счетчик частоты кодирования подсчитывает число кодируемых единичных символов N1, в обработанной части ИП. Числа N0 и N1 являются неотрицательными ненулевыми целыми числами. При арифметическом кодировании также подсчитывают суммарное число кодируемых нулевых и единичных символов N, равное N=N0+N1. В начальном состоянии число кодируемых нулевых иThe methods for calculating the values of the first and second coding frequency counters in accordance with a pre-formed key and a binary information sequence are as follows. The first counter of the encoding frequency counts the number of encoded zero characters N 0 in the processed part of the IP. The second counter of the encoding frequency counts the number of encoded unit characters N 1 in the processed part of the IP. Numbers N 0 and N 1 are non-negative non-zero integers. In arithmetic coding, the total number of encoded zero and unit symbols N equal to N = N 0 + N 1 is also calculated. In the initial state, the number of encoded zeros and
единичных символов еще не подсчитано, поэтому начиная кодировать первую часть двоичной информационной последовательности значения первого и второго счетчиков частоты кодирования вычисляют, например, в соответствии с ключом. Например, в соответствии с ключом первый и второй счетчики частоты кодирования принимают значения 11 и 2, соответственно. Поэтому суммарное число кодируемых нулевых и единичных символов N принимает начальное значение, равное N=13, как показано в верхней строке начального состояния арифметического кодирования с зашифрованием на фиг. 6 в начальный момент времени t=0. Значение первого счетчика частоты кодирования определяет значение вероятности кодируемых нулевых символов р0, а значение второго счетчика частоты кодирования определяет значение вероятности кодируемых единичных символов р1, при этом должно выполняться ограничение вида: р0+р1=1 Значение вероятности кодируемых нулевых символов р0 вычисляют по формуле вида
Способы установки значений первого и второго регистров кодирования в соответствии со значениями первого и второго счетчиков частоты кодирования известны и описаны, например, в книге Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин "Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео". - М., ДИАЛОГ-МИФИ, 2002, стр. 124-130. Значения первого и второго регистров кодирования устанавливают следующим образом. Сначала определяют нижнее L и верхнее Я значения интервала кодирования арифметического кодирования. В начале арифметического кодирования начальное нижнее значение интервала кодирования устанавливают, например, в минимальное значение, а начальное верхнее значения интервала кодирования - в максимальное значение. Например, при разрядности R=8 бит, начальное нижнее значение интервала кодирования арифметического кодирования L[0] устанавливают в минимальное значение, равное нулевому значению в десятичном представлении или "00000000" в двоичном представлении, где старшие двоичные символы записывают слева, а начальное верхнее значение интервала кодирования арифметического кодирования H[0] устанавливают в максимальное значение, равное 255 в десятичном представлении или "11111111" в двоичном представлении.Methods for setting the values of the first and second coding registers in accordance with the values of the first and second counters of the coding frequency are known and described, for example, in the book “Data compression methods. Archiver device, compression, by D. Vatolin, A. Ratushnyak, M. Smirnov, V. Yukin images and videos. " - M., DIALOGUE-MEPhI, 2002, pp. 124-130. The values of the first and second coding registers are set as follows. First, the lower L and upper I values of the coding interval of the arithmetic coding are determined. At the beginning of the arithmetic coding, the initial lower value of the encoding interval is set, for example, to the minimum value, and the initial upper value of the encoding interval is set to the maximum value. For example, with a bit length of R = 8 bits, the initial lower value of the coding interval for arithmetic coding L [0] is set to the minimum value equal to zero in decimal or "00000000" in binary representation, where the most significant binary characters are written to the left, and the initial upper value the coding interval of the arithmetic coding H [0] is set to a maximum value of 255 in decimal or "11111111" in binary representation.
Значение интервала кодирования арифметического кодирования I, равное I=H-L, разделяют на значения подинтервала нулевых символов D0 и подинтервала единичных символов D1, длины которых прямо пропорциональны значениям первого и второго счетчиков частоты кодирования или, что удобнее для кодирования, значениям вероятностей кодируемых нулевых символов р0 и единичных символов p1, соответственно. Длину подинтервала единичных символов D1, определяют по формуле вида D1=I×p1, а длину подинтервала нулевых символов D0 определяют по формуле вида D0=I-D1.The value of the coding interval of arithmetic coding I, equal to I = HL, is divided into values of the sub-interval of zero characters D 0 and the sub-interval of single characters D 1 , the lengths of which are directly proportional to the values of the first and second counters of the coding frequency or, which is more convenient for coding, to the probability values of the coded zero characters p 0 and single characters p 1 , respectively. The length of the sub-interval of single characters D 1 is determined by the formula of the form D 1 = I × p 1 , and the length of the sub-interval of zero characters D 0 is determined by the formula of the form D 0 = ID 1 .
Например, в начальный момент времени t=0 при значениях первого и второго счетчиков частоты кодирования N0=11 и N1=2, соответственно, начальная длина подинтервала единичных символов D1[0] имеет десятичное значение 38 или "00100110" в двоичном представлении, а начальная длина подинтервала нулевых символов D0[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 в начальном состоянии (Нач. сост.) арифметического кодирования.For example, at the initial moment of time t = 0 for the values of the first and second counters of the coding frequency N 0 = 11 and N 1 = 2, respectively, the initial length of the sub-interval of unit characters D 1 [0] has the
Способы кодирования очередной части двоичной информационной последовательности с использованием арифметического кодирования в кодированную последовательность известны и описаны, например, в книге Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин "Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео". - М., ДИАЛОГ-МИФИ, 2002, стр. 35-43. Они заключаются в последовательном кодировании очередных двоичных символов информационной последовательности в соответствии с текущими значениями интервала кодирования арифметического кодирования и текущими значениями вероятностей кодируемых нулевых символов и единичных символов с последовательным формированием очередной части кодированной последовательности.Methods of encoding the next part of a binary information sequence using arithmetic encoding into an encoded sequence are known and described, for example, in the book by D. Vatolin, A. Ratushnyak, M. Smirnov, V. Yukin "Data compression methods. Archiver device, image and video compression" . - M., DIALOGUE-MEPhI, 2002, pp. 35-43. They consist in sequential coding of the next binary characters of the information sequence in accordance with the current values of the coding interval of the arithmetic coding and the current values of the probabilities of the encoded zero characters and single characters with the sequential formation of the next part of the coded sequence.
Примерный вид арифметического кодирования показанной на фиг. 5(a) двоичной информационной последовательности вида "0111110110000100010001001" длиною 25 двоичных символов с использованием арифметического кодирования в кодированную последовательность вида "110110001110111100101001" представлен на фиг. 6 и на фиг. 7.An exemplary arithmetic coding shown in FIG. 5 (a) of a binary information sequence of the form “0111110110000100010001001” with a length of 25 binary symbols using arithmetic coding into an encoded sequence of the form “110110001110111100101001" is shown in FIG. 6 and in FIG. 7.
При поступлении на вход арифметического кодирования первого кодируемого символа (t=1), являющегося нулевым двоичным символом, значение интервала кодирования первого символа I[1] устанавливают равным начальному значению подинтервала нулевых символов D0[0], поэтому нижнее значение интервала кодирования первого символа L[l] устанавливают равным начальному нижнему значению интервала кодирования арифметического кодера L[0], записанному во второй регистр кодирования, равному, например, 0, а верхнее значение интервала кодирования первого символа арифметического кодирования H[1] устанавливают равным текущему значению Q, записанному в первый регистр кодирования, равному, например, 217, как показано на фиг. 7. Самый левый бит двоичного представления значения L[1] сравнивают с самым левым битом двоичного представления значения H[1], например, вида "00000000" и "11011001", соответственно, как показано на фиг. 6 при t=1. При их несовпадении переходят к кодированию следующего бита входных данных.When the first encoded character (t = 1), which is a binary binary character, arrives at the input of arithmetic coding, the value of the encoding interval of the first character I [1] is set equal to the initial value of the sub-interval of zero characters D 0 [0], therefore, the lower value of the encoding interval of the first character L [l] is set equal to the initial lower value of the encoding interval of the arithmetic encoder L [0] recorded in the second encoding register, for example, 0, and the upper value of the encoding interval of the first character arithmetic coding H [1] is set equal to the current value of Q recorded in the first coding register, equal to, for example, 217, as shown in FIG. 7. The leftmost bit of the binary representation of the value L [1] is compared with the leftmost bit of the binary representation of the value H [1], for example, of the form "00000000" and "11011001", respectively, as shown in FIG. 6 at t = 1. If they do not match, they proceed to encoding the next bit of the input data.
После выполнения кодирования каждого очередного бита входных данных уточняют число закодированных нулевых символов и единичных символов. Так как первый очередной бит является нулевым, то число закодированных нулевых символов увеличивают на единичное значение и оно составляет N0[1]=12, и число закодированных нулевых и единичных символов становится равным N[1]=N0[l]+N1[1]=l3. Пересчитывают текущее значение вероятности кодируемых нулевых символов
Если самый левый бит двоичного представления нижнего значения интервала кодирования не совпадает с самым левым битом двоичного представления верхнего значения интервала кодирования, то переходят к кодированию следующего бита. Например, следующий кодируемый бит, второй по счету, двоичной информационной последовательности является единичным двоичным символом, как показано на фиг. 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, с использованием регистров сдвига с параллельной и последовательной записью/считыванием двоичных последовательностей, и по своей сути являются умножением на два десятичных значений нижнего и верхнего значений интервала кодирования.If the leftmost bit of the binary representation of the lower value of the encoding interval does not coincide with the leftmost bit of the binary representation of the upper value of the encoding interval, then the next bit is encoded. For example, the next encoded bit of the second binary information sequence is a single binary symbol, as shown in FIG. 6, the third row from above, at t = 2. When a single binary character is input to the arithmetic coding, the value of the coding interval of the arithmetic coding is set equal to the value of the previous sub-interval of single characters, therefore, the lower value of the coding interval L [2] is set equal to the value Q, and the upper value of the coding interval H [2] is set equal to the previous upper value of the encoding interval H [1]. For example, as shown in FIG. 7, the value of L [2] is set to 186, and H [2] remains the same as the
Таким образом, при кодировании каждого очередного двоичного символа информационной последовательности уточняют значения первого и второго регистров кодирования.Thus, when encoding each successive binary symbol of the information sequence, the values of the first and second encoding registers are specified.
После каждого выполнения нормализации повторно самый левый бит двоичного представления нижнего значения интервала кодирования сравнивают с самым левым битом двоичного представления верхнего значения интервала кодирования. Например, после выполнения нормализации при кодировании второго бита значение L[2] устанавливают равным 116, а H[2] устанавливают равным 178. Повторно самый левый бит двоичного представления значения L[2] вида "01110100" сравнивают с самым левым битом двоичного представления значения H[2] вида "10110010" и при отсутствии совпадения переходят к кодированию следующего, третьего по счету бита двоичной информационной последовательности.After each normalization run, the leftmost bit of the binary representation of the lower value of the encoding interval is compared again with the leftmost bit of the binary representation of the upper value of the encoding interval. For example, after normalization is performed, when encoding the second bit, the value of L [2] is set to 116, and H [2] is set to 178. Again, the leftmost bit of the binary representation of the value L [2] of the form “01110100” is compared with the leftmost bit of the binary representation of the value H [2] of the form "10110010" and if there is no match, they proceed to the encoding of the next third bit of the binary information sequence.
В результате арифметического кодирования первой части двоичной информационной последовательности вида "011110" получена первая часть кодированной последовательности вида "11011000" длиной 8 бит. Очередная часть кодированной последовательности имеет фиксированный размер R бит, например, 8, 16 или 32 бита. Выбор размера очередной части кодированной последовательности определяется разрядностью используемого для реализации способа арифметического кодирования с шифрованием вычислительного устройства. Например, в результате арифметического кодирования первых трех частей двоичной информационной последовательности, показанной на фиг.5(a), получены первые три части кодированной последовательности длиной по 8 бит каждая, показанные на фиг. 5(б).As a result of arithmetic coding of the first part of the binary information sequence of the form "011110", the first part of the encoded sequence of the form "11011000" with a length of 8 bits is obtained. The next part of the encoded sequence has a fixed size R bits, for example, 8, 16 or 32 bits. The choice of the size of the next part of the encoded sequence is determined by the bit depth used to implement the method of arithmetic coding with encryption of the computing device. For example, as a result of arithmetic coding of the first three parts of the binary information sequence shown in FIG. 5 (a), the first three parts of the encoded sequence of 8 bits each, shown in FIG. 5 B).
Способы зашифрования очередной части кодированной последовательности с использованием предварительно сформированных криптографической функции и ключа, а также значений первого и второго регистров кодирования предыдущей части двоичной информационной последовательности заключаются в следующем. В результате арифметического кодирования сформирована очередная часть кодированной последовательности, имеющая фиксированную длину в битах. Например, в результате арифметического кодирования второй части двоичной информационной последовательности вида "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".Methods of encrypting the next part of the encoded sequence using pre-generated cryptographic functions and keys, as well as the values of the first and second encoding registers of the previous part of the binary information sequence are as follows. As a result of arithmetic coding, the next part of the encoded sequence having a fixed bit length is formed. For example, as a result of arithmetic coding of the second part of the binary information sequence of the form “11000” shown in FIG. 5 (a), the second part of the encoded sequence of the form “11101111” shown in FIG. 5 B). The values of the first and second coding registers of the previous part of the binary information sequence are formed by arithmetic coding at the beginning of the coding of the previous part of the IP. For example, the values of the first and second coding registers of the first part of the IP used to encrypt the second part of the CP correspond to the initial state of arithmetic coding at time t = 0, shown in FIG. 6, the first line. Accordingly, the value of the first coding register of the first part of the IP is “11011001”, and is equivalent to the
Собственно шифрование очередной части кодированной последовательности с использованием предварительно сформированных криптографической функции и оперативного ключа шифрования этой части КП описано, например, в книге М.Д. Смид, Д.К. Бранстед "Стандарт шифрования данных: Прошлое и будущее". ТИИЭР, 1988, - т. 76, №5, стр. 49. Оно заключаются в использовании ранее описанной предварительно сформированной криптографической функции, реализующей алгоритм шифрования блока данных в режиме обратной связи по шифртексту или в режиме обратной связи по выходу. При этом шифрование выполняют над очередной частью кодированной последовательности длиной R бит. Результатом шифрования очередной части кодированной последовательности является очередная часть зашифрованной последовательности (ЗП) длиной R бит.Примерный вид второй части ЗП показан на фиг. 5(ж) в виде двоичной последовательности "10000110" длиной 8 бит.The actual encryption of the next part of the encoded sequence using the previously generated cryptographic function and the operational encryption key of this part of the KP is described, for example, in the book of M.D. Smid, D.K. Branstead "Data Encryption Standard: Past and Future." TIIER, 1988, v. 76, No. 5, p. 49. It consists in using the previously described pre-generated cryptographic function that implements the encryption algorithm of the data block in feedback mode using ciphertext or in output feedback mode. In this case, encryption is performed on the next part of the encoded sequence of length R bits. The result of encrypting the next part of the encoded sequence is the next part of the encrypted sequence (RFP) of length R bits. An example view of the second part of the RFP is shown in FIG. 5 (g) in the form of a binary sequence "10000110" with a length of 8 bits.
Аналогичным образом выполняют арифметическое кодирование и зашифрование следующей, третьей части двоичной информационной последовательности и т.д. Третью часть двоичной информационной последовательности вида "0100010001001", показанную на фиг. 5(a), арифметически кодируют в третью часть кодированной последовательности вида "00101001", показанную на фиг. 5(б), которую зашифровывают в третью часть зашифрованной последовательности вида "11001010" длиной 8 бит, показанную на фиг. 5(ж).In the same way, arithmetic encoding and encryption of the next, third part of the binary information sequence, etc. The third part of the binary information sequence of the type “0100010001001” shown in FIG. 5 (a) are arithmetically encoded into the third part of the encoded sequence of the form “00101001” shown in FIG. 5 (b), which is encrypted in the third part of the encrypted sequence of the form “11001010” with a length of 8 bits, shown in FIG. 5 (g).
Особенностью зашифрования первой части кодированной последовательности является использованием предварительно сформированных криптографической функции и ключа, а также предварительно сформированных начальных значений первого и второго регистров кодирования, примерный вид которых показан на фиг. 3(б). Например, первая часть двоичной информационной последовательности вида "0111110", показанная на фиг. 5(a), арифметически кодируют в первую часть кодированной последовательности вида "11011000", показанную на фиг. 5(б), которую зашифровывают в первую часть зашифрованной последовательности вида "01111101" длиной 8 бит, показанную на фиг. 5(ж).A feature of encrypting the first part of the encoded sequence is the use of pre-generated cryptographic functions and keys, as well as pre-formed initial values of the first and second encoding registers, an exemplary view of which is shown in FIG. 3 (b). For example, the first part of the binary information sequence of the form “0111110” shown in FIG. 5 (a) are arithmetically encoded into the first part of an encoded sequence of the form “11011000” shown in FIG. 5 (b), which is encrypted in the first part of an encrypted sequence of the form “01111101” with a length of 8 bits, shown in FIG. 5 (g).
Способы передачи на приемную сторону очередной части зашифрованной последовательности известны и описаны, например, в книге А.Г. Зюко, Д.Д. Кловский, М.В. Назаров, Л.М. Финк "Теория передачи сигналов". - М: Радио и связь, 1986, стр. 11. Примерный вид первых трех частей принятой зашифрованной последовательности (Прин. ЗП) показан на фиг. 8(a).Methods of transmitting to the receiving side the next part of the encrypted sequence are known and described, for example, in the book of A.G. Zyuko, D.D. Klovsky, M.V. Nazarov, L.M. Fink "Theory of signal transmission." - M: Radio and Communications, 1986, p. 11. An exemplary view of the first three parts of a received encrypted sequence (Pr. GP) is shown in FIG. 8 (a).
Алгоритм арифметического декодирования с расшифрованием представлен на фиг. 9.The decoding arithmetic decoding algorithm is shown in FIG. 9.
Способы вычисления значения первого и второго счетчиков частоты декодирования в соответствии с предварительно сформированным ключом и принятой двоичной информационной последовательностью заключаются в следующем. Первый счетчик частоты декодирования подсчитывает число декодируемых нулевых символов NN0 в обработанной части принятой ИП. Второй счетчик частоты декодирования подсчитывает число декодируемых единичных символов NN1,. Числа NN0 и NN1 являются неотрицательными ненулевыми целыми числами. При арифметическом декодировании также подсчитывают суммарное число декодируемых нулевых и единичных символов NN, равное NN=NN0+NN1. В начальном состоянии число декодируемых нулевых и единичных символов еще не подсчитано, поэтому для первой части принятой двоичной информационной последовательности значения первого и второго счетчиков частоты декодирования вычисляют, например, в соответствии с ключом. Например, в соответствии с ключом первый и второй счетчики частоты декодирования принимают значения 11 и 2, соответственно. Поэтому суммарное число декодируемых нулевых и единичных символов NN принимает начальное значение, равное NN=13, как показано в верхней строке начального состояния арифметического декодирования с расшифрованием на фиг. 10 в начальный момент времени t=0. Значение первого счетчика частоты декодирования определяет значение вероятности декодируемых нулевых символов рр0, а значение второго счетчика частоты декодирования определяет значение вероятности декодируемых единичных символов рр1, при этом должно выполняться ограничение вида: pp0+рр1=1. Значение вероятности декодируемых нулевых символов рр0 вычисляют по формуле вида
Способы установки значений первого и второго регистров декодирования в соответствии со значениями первого и второго счетчиков частоты декодирования известны и описаны, например, в книге Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин "Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео". - М., ДИАЛОГ-МИФИ, 2002, стр. 124-130. Значения первого и второго регистров декодирования устанавливают следующим образом. Сначала определяют нижнее LL и верхнее НН значения интервала декодирования. В начале арифметического декодирования начальное нижнее значение интервала декодирования устанавливают, например, в минимальное значение, а начальное верхнее значения интервала декодирования - в максимальное значение. Например, при разрядности R=8 бит, начальное нижнее значение интервала декодирования арифметического декодирования LL[0] устанавливают в минимальное значение, равное нулевому значению в десятичном представлении или "00000000" в двоичном представлении, где старшие двоичные символы записывают слева, а начальное верхнее значение интервала декодирования арифметического кодирования HH[0] устанавливают в максимальное значение, равное 255 в десятичном представлении или "11111111 "в двоичном представлении.Methods of setting the values of the first and second decoding registers in accordance with the values of the first and second counters of the decoding frequency are known and described, for example, in the book D. Data compression methods. Archiver device, compression, by D. Vatolin, A. Ratushnyak, M. Smirnov, V. Yukin images and videos. " - M., DIALOGUE-MEPhI, 2002, pp. 124-130. The values of the first and second decoding registers are set as follows. First, the lower LL and upper HH decoding interval values are determined. At the beginning of arithmetic decoding, the initial lower value of the decoding interval is set, for example, to the minimum value, and the initial upper value of the decoding interval is set to the maximum value. For example, with a bit size of R = 8 bits, the initial lower value of the arithmetic decoding decoding interval LL [0] is set to the minimum value equal to zero in decimal or "00000000" in binary representation, where the most significant binary characters are written to the left, and the initial upper value the decoding interval of the arithmetic coding HH [0] is set to a maximum value of 255 in decimal representation or "11111111" in binary representation.
Значение интервала декодирования арифметического декодирования II, равное II=HH-LL, разделяют на значения подинтервала нулевых символов DD0 и подинтервала единичных символов DD1, длины которых прямо пропорциональны значениям первого и второго счетчиков частоты декодирования или, что удобнее для декодирования, значениям вероятностей декодируемых нулевых символов рр0 и единичных символов рр1, соответственно. Длину подинтервала единичных символов DD1, определяют по формуле вида DD1=II×рр1, а длину подинтервала нулевых символов DD0 определяют по формуле вида DD0=II-DD1.The value of the decoding interval of arithmetic decoding II, equal to II = HH-LL, is divided into values of the sub-interval of zero characters DD 0 and the sub-interval of single characters DD 1 , the lengths of which are directly proportional to the values of the first and second counters of the decoding frequency or, more convenient for decoding, to the probabilities of the decoded zero characters pp 0 and single characters pp 1 , respectively. The length of the sub-interval of single characters DD 1 is determined by the formula of the form DD 1 = II × pp 1 , and the length of the sub-interval of zero characters DD 0 is determined by the formula of the form DD 0 = II-DD 1 .
Например, в начальный момент времени t=0 при значениях первого и второго счетчиков частоты декодирования NN0=11 и NN1=2, соответственно, начальная длина подинтервала единичных символов DD1[0] имеет десятичное значение 38 или "00100110" в двоичном представлении, а начальная длина подинтервала нулевых символов DD0[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 в начальном состоянии (Нач. сост.) арифметического декодирования.For example, at the initial moment of time t = 0 for the values of the first and second decoding frequency counters NN 0 = 11 and NN 1 = 2, respectively, the initial length of the subinterval of unit characters DD 1 [0] has a decimal value of 38 or "00100110" in binary representation , and the initial length of the sub-interval of null characters DD 0 [0] has a decimal value of 255-38 = 217 or "11011001" in binary representation. The sub-interval of single characters is located, for example, on top of the sub-interval of zero characters, as shown in FIG. 11. The upper boundary of the sub-interval of null decoding symbols is designated as the QQ value, and this sub-interval starts from the bottom of the lower boundary of the arithmetic decoding decoding interval to the QQ value exclusively, and the sub-interval of single decoding symbols extends from the QQ value inclusive to the upper limit of the arithmetic decoding decoding interval exclusively. The value of the first decoding register is set equal to the QQ value. For example, at time t = 0, the value of the first decoding register is equal to the
Таким образом, начальные состояния первого и второго регистров декодирования идентичны начальным состояниям первого и второго регистров кодирования, равно как начальные значения первого и второго счетчиков частоты декодирования идентичны начальным значениям первого и второго счетчиков частоты кодирования.Thus, the initial states of the first and second decoding registers are identical to the initial states of the first and second encoding registers, as well as the initial values of the first and second decoding frequency counters are identical to the initial values of the first and second encoding frequency counters.
Способы расшифрования очередной части принятой зашифрованной последовательности с использованием предварительно сформированных криптографической функции и ключа, а также значений первого и второго регистров декодирования предыдущей части принятой двоичной информационной последовательности аналогичны ранее описанным способам зашифрования очередной части кодированной последовательности с использованием предварительно сформированных криптографической функции и ключа, а также значений первого и второго регистров кодирования предыдущей части двоичной информационной последовательности и заключаются в следующем.The methods for decrypting the next part of the received encrypted sequence using the previously generated cryptographic function and key, as well as the values of the first and second decoding registers of the previous part of the received binary information sequence, are similar to the previously described methods of encrypting the next part of the encoded sequence using the pre-generated cryptographic function and key, as well as values of the first and second coding registers pr of the previous part of the binary information sequence and are as follows.
На приемной стороне получена очередная часть зашифрованной последовательности, имеющая фиксированную длину в битах. Например, принята первая часть зашифрованной последовательности длиной 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 бит.On the receiving side, the next part of the encrypted sequence having a fixed bit length is received. For example, the first part of the encrypted sequence of length R = 8 bits of the form “01111101” shown in FIG. 8 (a). To decrypt the first part of the received encrypted sequence, preformed initial values of the first and second decoding registers are used, for example, of the form “10011011” and “01 ... 011110” shown in FIG. 3 (c). A preformed binary key sequence is bitwise added modulo 2 with the given binary sequences of the initial values of the first and second decoding registers. To do this, the first R bits of the binary sequence of the key are bitwise modulo 2 summed with R bits of the initial value of the binary sequence of the first decoding register, then the next 2R bits of the binary key sequence are bitwise summed modulo 2 with 2R bits of the binary sequence of the initial sequence of the second decoding register, forming an operational key to decrypt the next part of the adopted RFP, which in its purpose is similar to the operational key in the closest analogue (prototype). For example, from the preformed key shown in FIG. 8 (b), an operational key is generated for decrypting the first part of the received RFP in the form of a binary sequence “1001110 ... 0”, shown in FIG. 8 (c). Decryption is performed on the next part of the received RFP with a length of R bits, using the decryption algorithm of the data block in ciphertext feedback mode or in output feedback mode. The result of decoding the next part of the received RFP is the next part of the decrypted sequence (RP) of length R bits. An exemplary view of the first part of the RP is shown in FIG. 8 (g) in the form of a binary sequence "11011000" with a length of 8 bits.
Перед арифметическим декодированием очередной части расшифрованной последовательности запоминают значения первого и второго регистров декодирования предыдущей части принятой двоичной информационной последовательности, которые используют для расшифрования следующей части, начиная со второй части, принятой зашифрованной последовательности. Значения первого и второго регистров декодирования первой части принятой двоичной информационной последовательности в момент t=0 запоминают для расшифрования второй части принятой зашифрованной последовательности. Например, значения первого и второго регистров декодирования первой части принятой двоичной информационной последовательности имеют вид "11011001" длиной 8 бит и "0000000011111111" длиной 16 бит, соответственно, как показано на фиг. 8(д) и 8(e).Before arithmetic decoding of the next part of the decrypted sequence, the values of the first and second decoding registers of the previous part of the received binary information sequence are stored, which are used to decrypt the next part, starting from the second part, the received encrypted sequence. The values of the first and second decoding registers of the first part of the received binary information sequence at the time t = 0 are stored to decrypt the second part of the received encrypted sequence. For example, the values of the first and second decoding registers of the first part of the received binary information sequence are “11011001” with a length of 8 bits and “0000000011111111” with a length of 16 bits, respectively, as shown in FIG. 8 (e) and 8 (e).
При получении второй части зашифрованной последовательности ее расшифровывают с использованием предварительно сформированных криптографической функции и ключа, а также значений первого и второго регистров декодирования первой части принятой двоичной информационной последовательности. Например, принятую вторую часть ЗП вида "10000110" длиной 8 бит, показанную на фиг. 8(a), расшифровывают во вторую расшифрованной последовательности длиной R бит. Примерный вид второй части РП показан на фиг. 8(г) в виде двоичной последовательности "11101111" длиной 8 бит.Upon receipt of the second part of the encrypted sequence, it is decrypted using the previously generated cryptographic function and key, as well as the values of the first and second decoding registers of the first part of the received binary information sequence. For example, the adopted second part of the RFP of the form "10000110" with a length of 8 bits, shown in FIG. 8 (a) is decrypted into a second decrypted sequence of length R bits. An exemplary view of the second part of the RP is shown in FIG. 8 (g) in the form of a binary sequence "11101111" with a length of 8 bits.
Способы арифметического декодирования очередной части расшифрованной последовательности известны и описаны, например, в книге Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин "Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео". - М., ДИАЛОГ-МИФИ, 2002, стр. 35-43. Они заключаются в последовательном декодировании с использованием арифметического декодирования очередной части расшифрованной последовательности в соответствии с текущими значениями интервала декодирования арифметического декодирования и текущими значениями вероятности декодируемых нулевых символов и единичных символов. Начальное состояние (Нач. сост.) арифметического декодирования представлено на фиг. 10 и на фиг. 11 при t=0.The methods of arithmetic decoding of the next part of the decrypted sequence are known and described, for example, in the book by D. Vatolin, A. Ratushnyak, M. Smirnov, V. Yukin, "Data compression methods. Archiver device, image and video compression." - M., DIALOGUE-MEPhI, 2002, pp. 35-43. They consist in sequential decoding using arithmetic decoding of the next part of the decrypted sequence in accordance with the current values of the decoding interval of the arithmetic decoding and the current values of the probability of decoded zero characters and single characters. The initial state (Start) of arithmetic decoding is shown in FIG. 10 and in FIG. 11 at t = 0.
На вход арифметического декодирования поступает очередная часть расшифрованной последовательности, например, первая часть РП вида "11011000" длиной 8 бит. Как и ранее описанное арифметическое кодирование, операции арифметического декодирования используют такую же разрядность R выполняемых операций. Поэтому на вход арифметического декодирования считывают входные данные длиной R бит вида "11011000", что соответствует десятичному числу 216. Текущее значение считанной последовательности, указанное на фиг. 11 стрелкой, сравнивают с границами начального значения подинтервала декодирования нулевых символов DD0[0], находящимися, например, в пределах от 0 до 217 и с границами начального значения подинтервала декодирования единичных символов DD1[0], находящимися, например, в пределах от 217 до 255. В зависимости от того, в пределах какого подинтервала декодирования символов оказалось текущее значение считанной последовательности, принимают решение о декодировании очередного символа принятой двоичной информационной последовательности. Например, так как текущее значение считанной последовательности оказалось меньше значения QQ, то первый декодированный символ является нулевым и следующие границы интервала декодирования устанавливают соответствующими границам значения подинтервала декодирования нулевых символов DD0[0]. В результате декодирования первого символа устанавливают нижнее значение интервала декодирования арифметического кодирования LL[l] равным предыдущему значению LL[0], например, LL[0]=0, а верхнее значение интервала декодирования арифметического кодирования НН[1] - равным значению QQ, например, HH[1]=217, как показано на фиг. 10 во второй строке при t=1. После декодирования каждого символа пересчитывают текущее значение вероятности декодируемых нулевых символов и текущее значение вероятности декодируемых нулевых символов, например, после декодирования первого символа, являющегося нулевым, по формуле вида
Устанавливают текущие длины подинтервалов декодирования единичных символов и нулевых символов и устанавливают текущее значение QQ=186 с двоичным представлением вида "10111010", как показано на фиг. 11. Таким образом уточняют значения первого и второго регистров декодирования.Set the current lengths of the decoding intervals of single characters and zero characters, and set the current value QQ = 186 with a binary representation of the form “10111010”, as shown in FIG. 11. Thus, the values of the first and second decoding registers are specified.
Декодированный нулевой символ считывают с выхода арифметического декодирования в качестве первого символа первой части принятой двоичной информационной последовательности.The decoded null character is read from the arithmetic decoding output as the first character of the first part of the received binary information sequence.
После каждого уточнения значений первого и второго регистров декодирования самый левый бит двоичного представления значения LL сравнивают с самым левым битом двоичного представления значения HH, например, при t=1 вида "00000000" и "11011001", соответственно. При их совпадении выполняют нормализацию арифметического декодирования, иначе продолжают декодирование, например, декодируют второй символ первой части принятой двоичной информационной последовательности. На вход арифметического декодирования по прежнему считаны входные данные вида "11011000", что соответствует десятичному числу 216. Текущее значение считанной последовательности, указанное на фиг. 11 стрелкой, сравнивают с границами значения подинтервала декодирования нулевых символов DD0[1], находящимися, например, в пределах от 0 до 186 и с границами значения подинтервала декодирования единичных символов DD1[1], находящимися, например, в пределах от 186 до 217. В зависимости от того, в пределах какого подинтервала декодирования символов оказалось текущее значение считанной последовательности, принимают решение о декодировании очередного символа принятой двоичной информационной последовательности. Например, так как текущее значение считанной последовательности оказалось больше значения QQ, то второй декодированный символ является единичным и следующие границы интервала декодирования устанавливают соответствующими границам значения подинтервала декодирования единичных символов DD1[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] не совпадают, то повторного выполнения нормализации не требуется и выполняют декодирование третьего символа и т.д.The leftmost bit of the binary representation of the LL [2] value is compared with the leftmost bit of the binary representation of the HH value [2], for example, of the form “10111010” and “11011001”, respectively. If they coincide, the arithmetic decoding is normalized: the value of the leftmost bit of the binary representations of the LL [2] and LV [2] values is deleted and the binary symbols of the binary representations of the LL [2] and LV [2] values are shifted from right to left by one digit and from right to them in the least significant order, add a binary binary character. At the same time, the value of the leftmost bit of the input data is deleted and the binary characters of the input data are shifted from right to left by one bit, and the next binary RP symbol is added to them, for example, the first symbol of the second part of the RP, which is a single symbol, as shown in FIG. 10 in the fourth row “normalization” and in FIG. 11. Given the added binary character, the input data acquires the binary representation "10110001" and the
В результате арифметического декодирования первых по очереди двенадцати символов из первой и второй частей РП декодируют первые две части принятой двоичной информационной последовательности, которые по мере декодирования, передают получателю, как показано, например, на фиг. 10 и на фиг. 11. Вид первой части принятой двоичной информационной последовательности "0111110" и второй части принятой двоичной информационной последовательности "11000" показан на фиг. 8(ж). Видно, что на передающей стороне расшифрованные и арифметически декодированные части принятой двоичной информационной последовательности совпадают с соответствующими частями двоичной информационной последовательности, арифметически закодированными и зашифрованными на передающей стороне.As a result of arithmetic decoding of the first twelve characters in turn from the first and second parts of the RP, the first two parts of the received binary information sequence are decoded, which, as they are decoded, are transmitted to the receiver, as shown, for example, in FIG. 10 and in FIG. 11. A view of the first part of the received binary information sequence "0111110" and the second part of the received binary information sequence "11000" is shown in FIG. 8 (g). It can be seen that on the transmitting side, the decrypted and arithmetically decoded parts of the received binary information sequence coincide with the corresponding parts of the binary information sequence arithmetically encoded and encrypted on the transmitting side.
Проверка теоретических предпосылок заявленного способа арифметического кодирования с шифрованием проверялась путем его аналитических исследований.Verification of the theoretical premises of the claimed method of arithmetic coding with encryption was verified by its analytical studies.
Было выполнено арифметическое кодирование с шифрованием одной и той же двоичной информационной последовательности длиной 49766400 байт с использованием способа-прототипа и предлагаемого способа, результаты показаны на фиг. 12. При разрядности R битов устройства, реализующего арифметическое кодирование, равной 8, 16 и 32 битов, при использовании способа-прототипа достигается коэффициент сжатия от 1,18 до 1,42 раз, а при использовании предлагаемого способа величина коэффициента сжатия повышается в диапазоне значений от 3,78 до 4,19 раз. Также исследовалось, насколько предлагаемый способ арифметического кодирования теряет в коэффициенте сжатия при реализации шифрования по сравнению с этим же арифметическим кодированием без шифрования. При арифметическом кодировании без шифрования достигается коэффициент сжатия от 4,02 до 4,32 раз, то есть при реализации шифрования уменьшение коэффициента сжатия составляет не более 0,13…0,24 раз.Arithmetic coding was performed with encryption of the same
Таким образом, в заявленном способе арифметического кодирования с шифрованием для избыточной двоичной информационной последовательности обеспечивается повышение степени удаления избыточности зашифрованной информации.Thus, in the inventive method of arithmetic coding with encryption for redundant binary information sequence provides an increase in the degree of removal of redundancy of encrypted information.
Claims (3)
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| RU2015132451/08A RU2595953C1 (en) | 2015-08-04 | 2015-08-04 | Method for arithmetic encoding with encryption |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| RU2015132451/08A RU2595953C1 (en) | 2015-08-04 | 2015-08-04 | Method for arithmetic encoding with encryption |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| RU2595953C1 true RU2595953C1 (en) | 2016-08-27 |
Family
ID=56891976
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| RU2015132451/08A RU2595953C1 (en) | 2015-08-04 | 2015-08-04 | Method for arithmetic encoding with encryption |
Country Status (1)
| Country | Link |
|---|---|
| RU (1) | RU2595953C1 (en) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| RU2737917C1 (en) * | 2016-12-27 | 2020-12-04 | Хелдер Сильвестре Паива ФИГУЕИРА | Ambiguity increase |
Citations (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6046744A (en) * | 1996-01-11 | 2000-04-04 | Microsoft Corporation | Selective refinement of progressive meshes |
| RU2226041C2 (en) * | 2001-11-01 | 2004-03-20 | Государственное предприятие конструкторское бюро "СПЕЦВУЗАВТОМАТИКА" | Method for binary data cryptographic conversion |
| US7664267B2 (en) * | 2000-11-29 | 2010-02-16 | Agere Systems Inc. | Bit based arithmetic coding using variable size key cipher |
| US8369568B2 (en) * | 2006-04-26 | 2013-02-05 | The Board Of Regents Of The University Of Texas System | Methods and systems for digital image security |
| US8411859B2 (en) * | 2005-07-05 | 2013-04-02 | Stmicroelectronics S.A. | Non-deterministic number generation |
| US9054870B2 (en) * | 2012-10-22 | 2015-06-09 | Donatello Apelusion Gassi | Information security based on eigendecomposition |
-
2015
- 2015-08-04 RU RU2015132451/08A patent/RU2595953C1/en not_active IP Right Cessation
Patent Citations (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6046744A (en) * | 1996-01-11 | 2000-04-04 | Microsoft Corporation | Selective refinement of progressive meshes |
| US7664267B2 (en) * | 2000-11-29 | 2010-02-16 | Agere Systems Inc. | Bit based arithmetic coding using variable size key cipher |
| RU2226041C2 (en) * | 2001-11-01 | 2004-03-20 | Государственное предприятие конструкторское бюро "СПЕЦВУЗАВТОМАТИКА" | Method for binary data cryptographic conversion |
| US8411859B2 (en) * | 2005-07-05 | 2013-04-02 | Stmicroelectronics S.A. | Non-deterministic number generation |
| US8369568B2 (en) * | 2006-04-26 | 2013-02-05 | The Board Of Regents Of The University Of Texas System | Methods and systems for digital image security |
| US9054870B2 (en) * | 2012-10-22 | 2015-06-09 | Donatello Apelusion Gassi | Information security based on eigendecomposition |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| RU2737917C1 (en) * | 2016-12-27 | 2020-12-04 | Хелдер Сильвестре Паива ФИГУЕИРА | Ambiguity increase |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN111492615B (en) | Cryptographic device with updatable sharing matrix | |
| CN111492616B (en) | Configurable devices for lattice-based cryptography | |
| US4351982A (en) | RSA Public-key data encryption system having large random prime number generating microprocessor or the like | |
| KR100657062B1 (en) | Information encryption method and apparatus for realizing this method | |
| EP1834438B1 (en) | Cryptography related to keys | |
| KR101267109B1 (en) | Cryptographic primitives, error coding, and pseudo-random number improvement methods using quasigroups | |
| CN116032474B (en) | A computer network security protection system based on big data | |
| US20070028088A1 (en) | Polymorphic encryption method and system | |
| US7190791B2 (en) | Method of encryption using multi-key process to create a variable-length key | |
| JPS5873257A (en) | Encoding device | |
| CN109450635B (en) | Transmitter deniable encryption method based on fault-tolerant learning problem | |
| CN115276989A (en) | Serialized data encryption method based on direction scrambling | |
| RU2459276C1 (en) | Method for coding of m message represented as multidigit binary number | |
| CN115333777B (en) | Data encryption method, system, device and storage medium | |
| CN109344627B (en) | A Novel Shannon Perfect Secrecy Method | |
| RU2595953C1 (en) | Method for arithmetic encoding with encryption | |
| CN115834060A (en) | Cryptology-based electronic official document secure import and export method and system | |
| CN115843360B (en) | Symmetric encryption and decryption method based on exponential complexity | |
| RU2205516C1 (en) | Procedure of continuous coding of discrete information | |
| Chen et al. | An improved image encryption algorithm based on chaos | |
| RU2656713C1 (en) | Method for arithmetic encoding with encryption | |
| CN117314427A (en) | Efficient hidden communication method and communication system based on blockchain remarks | |
| US11038668B2 (en) | Transposition encryption alphabet method (TEAM) | |
| CN109409106B (en) | A Shannon Perfect Secrecy Method for a Novel Infinite Alphabet | |
| CN118827004B (en) | An encryption method based on edge IoT agent |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| MM4A | The patent is invalid due to non-payment of fees |
Effective date: 20200805 |