СПОСОБ АУТЕНТИФИКАЦИИ ЭЛЕКТРОННОГО ИЗОБРАЖЕНИЯ
AUTHENTICATION OF ELECTRONIC IMAGE

Изобретение относится к области электросвязи и информационных технологий, а именно к технике защиты подлинности электронных изображений (ЭИ), сжимаемых алгоритмами сжатия ЭИ, такими как JPEG2000, Н.264 и т.п., передаваемых отправителем получателю по общедоступным каналам передачи, в которых нарушитель может осуществлять действия по навязыванию получателю неподлинных ЭИ.
Заявленный способ может быть использован для обеспечения подлинности ЭИ, передаваемых в современных информационно-телекоммуникационных системах.
Известны способы аутентификации ЭИ на основе вычисления отправителем и проверки получателем имитовставки двоичной последовательности (ДП) этого изображения. Эти способы относятся к криптографическим способам контроля подлинности ЭИ и описаны, например, в государственном стандарте 28147-89. Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования. - М.: Госстандарт СССР. 1989, стр. 9-14. В данных способах ЭИ сжимают в соответствии с алгоритмом JPEG2000, предписанным международным стандартом ISO/IES 15444. Двоичную последовательность сжатого электронного изображения JPEG разделяют у отправителя на последовательные блоки длиной n бит, где обычно n=64. По криптографической функции формирования имитовставки с использованием заранее сформированной для отправителя и получателя двоичной последовательности (ДП) секретного ключа (СК) последовательно от каждого блока с учетом предыдущего зашифрованного блока формируют зашифрованный текущий блок до тех пор, пока поступает ДП ЭИ. Из последнего зашифрованного блока выделяют ДП имитовставки ЭИ длиной l<n бит. Затем ДП ЭИ и ДП имитовставки передают по каналу связи или записывают на электронные носители, например CD или DVD диски. Принятое получателем ЭИ проверяют, для чего заново разделяют его ДП на последовательные принятые блоки длиной n бит, по криптографической функции формирования имитовставки с использованием ДПСК последовательно от каждого принятого блока с учетом предыдущего зашифрованного принятого блока формируют очередной зашифрованный принятый блок до тех пор, пока поступает ДП принятого ЭИ. Из последнего зашифрованного принятого блока выделяют длиной l<n бит ДП имитовставки принятого ЭИ и при полном совпадении заново сформированной и принятой имитовставок принятое ЭИ считают подлинным.
Недостатками указанных аналогов являются:
- невозможность проверки подлинности части аутентифицированного с использованием имитовставки ЭИ;
- уменьшение пропускной способности каналов передачи или необходимость использования запоминающих устройств большой емкости из-за включения и последующей передачи по каналу связи имитовставки электронного изображения.
1
2
1
2
Известны также способы аутентификации ЭИ на основе вычисления и встраивания цифровых водяных знаков (ЦВЗ) в электронное изображение. Эти способы относятся к стеганографическим способам контроля подлинности ЭИ и описаны, например, в способе аутентификации ЭИ по патенту США 7313696 МПК H04L 9/00 (2006.01) от 25.12.07. Данный способ аутентификации ЭИ заключается в предварительном формировании для отправителя и получателя ДП СК, криптографической функции хэширования и криптографической функции шифрования. У отправителя разделяют ЭИ на М≥2 блоков каждый размером n×n пикселов, где n≥2 и n≥2, над каждым m-ым, где m=1,2,…,М, блоком ЭИ выполняют вейвлет преобразование, полученные в результате преобразования вейвлет коэффициенты квантуют и преобразуют в ДП вейвлет коэффициентов m-го блока ЭИ, которые преобразуют в N≥2 УДП вейвлет коэффициентов m-го блока ЭИ. Из K, где K=N-1, УДП ВК m-го блока ЭИ вычисляют его хэширующую последовательность с помощью предварительно сформированной криптографической функции хэширования. Затем из хэширующей последовательности m-го блока ЭИ вычисляют его ДП цифрового водяного знака с помощью предварительно сформированных криптографической функции шифрования и ДП СК. Аутентифицируют m-й блок ЭИ, для чего встраивают ДП ЦВЗ m-го блока ЭИ в N-ую УДП ВК этого блока ЭИ заменой N-ой УДП ВК этого блока ЭИ на его ДП ЦВЗ.
Полученные УДП ВК с встроенной ДП ЦВЗ m-го блока ЭИ кодируют с использованием арифметического кодирования в кодированные последовательности этого блока, включающие маркеры, причем действия по аутентификации у отправителя блоков ЭИ повторяют до завершения их поступления.
Передают аутентифицированное ЭИ получателю, где проверяют подлинность принятого получателем ЭИ, для чего разделяют ДП принятого получателем ЭИ на двоичные последовательности его принятых блоков, которые разделяют на кодированные последовательности m-го принятого блока ЭИ, декодируют их и выделяют N УДП ВК m-го принятого блока ЭИ. Выделяют из N-ой УДП ВК m-го принятого блока ЭИ ДП ЦВЗ m-го принятого блока ЭИ и запоминают ее.
Из К УДП ВК m-го принятого блока ЭИ вычисляют его хэширующую последовательность с помощью предварительно сформированной криптографической функции хэширования. Затем из хэширующей последовательности m-го принятого блока ЭИ вычисляют его ДП ЦВЗ с помощью предварительно сформированных криптографической функции шифрования и ДП СК и сравнивают ее с ранее выделенной и запомненной ДП ЦВЗ m-го принятого блока ЭИ. При их совпадении m-ый принятый блок ЭИ считают подлинным. Повторяют действия по проверке подлинности принятых блоков ЭИ до завершения их приема. Принятое ЭИ считают подлинным, если подлинными оказываются М принятых блоков ЭИ.
Недостатком указанных аналогов является относительно низкая устойчивость аутентифицированного ЭИ к воздействию ошибок канала передачи. Это обусловлено тем, что при искажении ошибками канала передачи любого бита ДП m-го принятого аутентифицированного БЭИ в этой двоичной последовательности происходит размножение ошибок из-за использовании функции хэширования для ее вычисления и в итоге этот БЭИ считают неподлинным.
1
2
1
2
Наиболее близким по своей технической сущности к заявленному способу аутентификации ЭИ является способ аутентификации ЭИ, описанный в международном стандарте защиты ЭИ: Документ ISO/IEC FCD15444-8: Information technology - JPEG2000 image coding system. Part 8. Secure JPEG2000. Женева, 2004, стр. 66-89. Способ - прототип аутентификации ЭИ заключается в предварительном формировании для отправителя и получателя ДП СК и криптографической функции хэширования. У отправителя над ЭИ выполняют вейвлет преобразование, полученные в результате преобразования вейвлет коэффициенты квантуют и разделяют на N≥2 кодовых блоков квантованных вейвлет коэффициентов каждый размером n×n коэффициентов, где n≥2 и n≥2, квантованные вейвлет коэффициенты n-го, где n=1,2,…,N, кодового блока квантованных вейвлет коэффициентов преобразуют в двоичные последовательности квантованных вейвлет коэффициентов n-го кодового блока, которые преобразуют в L≥2 упорядоченные двоичные последовательности (УДП) квантованных вейвлет коэффициентов n-го кодового блока, из первых K, где 1≤K≤L, УДП квантованных вейвлет коэффициентов n-го кодового блока с использованием предварительно сформированных криптографической функции хэширования и ДП СК вычисляют ДП цифрового водяного знака (ЦВЗ) n-го кодового блока, которую встраивают в последние Т, где K≤Т≤L, УДП квантованных вейвлет коэффициентов этого же блока, номера которых определяют предварительно сформированной ДП СК, УДП квантованных вейвлет коэффициентов n-го кодового блока, включая УДП вейвлет коэффициентов с встроенной ДП ЦВЗ n-го кодового блока, кодируют с использованием арифметического кодирования в кодированные последовательности этого блока, по окончании арифметического кодирования каждой очередной УДП квантованных вейвлет коэффициентов n-го кодового блока в ДП кодированного ЭИ записывают разделительный маркер УДП, а после кодирования L УДП квантованных вейвлет коэффициентов n-го кодового блока в ДП кодированного ЭИ записывают разделительный маркер кодового блока, причем действия по аутентификации у отправителя кодовых блоков повторяют до завершения их поступления.
Передают кодированное ЭИ получателю, где проверяют подлинность принятого получателем ЭИ, для чего разделяют ДП принятого получателем ЭИ на двоичные последовательности его принятых блоков, декодируют кодированные последовательности n-го принятого кодового блока с использованием арифметического декодирования и выделяют L УДП квантованных вейвлет коэффициентов n-го принятого кодового блока, из последних Г УДП квантованных вейвлет коэффициентов n-го принятого кодового блока, номера которых определяют предварительно сформированной ДП СК, выделяют ДП ЦВЗ n-го принятого кодового блока, которую запоминают, из первых К УДП квантованных вейвлет коэффициентов n-го принятого кодового блока с использованием предварительно сформированных криптографической функции хэширования и ДП СК вычисляют ДП ЦВЗ n-го принятого кодового блока, которую побитно сравнивают с запомненной выделенной ДП ЦВЗ этого блока, при их совпадении n-ый принятый кодовый блок считают подлинным, повторяют действия по проверке подлинности принятых кодовых блоков до завершения их приема, принятое ЭИ считают подлинным, если подлинными оказываются N принятых кодовых блоков.
Способ - прототип аутентификации ЭИ обеспечивает контроль подлинности ЭИ, сжимаемого с использованием алгоритмов сжатия, таких как JPEG2000 и т.п.
необн
-b
-32
-9
Недостатком ближайшего аналога (прототипа) является сравнительно небольшая защищенность от подмены нарушителем подлинного аутентифицированного ЭИ на неподлинное ЭИ. Данный недостаток обусловлен тем, что при аутентификации в каждый n-ый кодовый блок кодированного ЭИ встраивается двоичная последовательность ЦВЗ длиной b бит. Численно защищенность от подмены нарушителем подлинного аутентифицированного ЭИ на неподлинное ЭИ на каждый кодовый блок оценивается вероятностью необнаруживаемой подмены, вычисляемой по формуле Р≈2, как описано, например, в ГОСТ 28147-89 "Алгоритмы криптографической защиты данных". Длину двоичной последовательности ЦВЗ, как правило, выбирают равной b=32 бита, что обеспечивает вероятность необнаруживаемой подмены 2≈10. При необходимости повышения защищенности от подмены нарушителем подлинного аутентифицированного ЭИ на неподлинное ЭИ снижение вероятности необнаруживаемой подмены достигается только путем увеличения длины двоичной последовательность ЦВЗ, что вызывает увеличение длины аутентифицированного ЭИ и требует при его передаче увеличения скорости передачи по каналам передачи или при хранении использования запоминающих устройств большей емкости.
Техническим результатом заявляемого способа является повышение защищенности от подмены нарушителем подлинного аутентифицированного ЭИ на неподлинное ЭИ.
1
2
1
2
Указанный технический результат в заявляемом способе аутентификации ЭИ достигается тем, что в известном способе аутентификации ЭИ, заключающемся в предварительном формировании для отправителя и получателя двоичной последовательности секретного ключа, у отправителя над ЭИ выполняют вейвлет преобразование, полученные в результате преобразования вейвлет коэффициенты квантуют и разделяют на N≥2 кодовых блоков квантованных вейвлет коэффициентов каждый размером n×n коэффициентов, где n≥2 и n≥2, квантованные вейвлет коэффициенты n-го, где n=1,2,…,N, кодового блока квантованных вейвлет коэффициентов преобразуют в двоичные последовательности квантованных вейвлет коэффициентов n-го кодового блока, которые преобразуют в L≥2 упорядоченных двоичных последовательностей квантованных вейвлет коэффициентов n-го кодового блока, упорядоченные двоичные последовательности квантованных вейвлет коэффициентов n-го кодового блока кодируют с использованием арифметического кодирования в кодированные последовательности этого блока, по окончании арифметического кодирования очередной УДП квантованных вейвлет коэффициентов n-го кодового блока в ДП кодированного ЭИ записывают разделительный маркер УДП, а после кодирования L УДП квантованных вейвлет коэффициентов n-го кодового блока в ДП кодированного ЭИ записывают разделительный маркер кодового блока, причем действия по аутентификации у отправителя кодовых блоков повторяют до завершения их поступления, передают кодированное ЭИ получателю, где проверяют подлинность принятого получателем ЭИ, для чего разделяют ДП принятого получателем ЭИ на двоичные последовательности его принятых блоков с использованием разделительного маркера каждого кодового блока, декодируют кодированные последовательности n-го принятого кодового блока с использованием арифметического декодирования в L упорядоченных двоичных последовательностей квантованных вейвлет коэффициентов n-го принятого кодового блока, повторяют действия по проверке подлинности принятых кодовых блоков до завершения их приема, принятое ЭИ считают подлинным, если подлинными оказываются N принятых кодовых блоков, дополнительно у отправителя перед кодированием очередной УДП квантованных вейвлет коэффициентов n-го кодового блока с использованием арифметического кодирования изменяют разрядность представления интервала арифметического кодирования в соответствии с предварительно сформированной ДП СК и номером n-го кодового блока, разделительный маркер УДП выбирают случайным образом в подинтервале кодирования последнего двоичного символа данной УДП.
1
2
У получателя перед декодированием очередной кодированной последовательности n-го принятого кодового блока с использованием арифметического декодирования изменяют разрядность представления интервала арифметического декодирования в соответствии с предварительно сформированной ДП СК и номером n-го принятого кодового блока, n-ый принятый кодовый блок считают подлинным, если декодировано L×n×n его битов.
Указанная новая совокупность действий за счет изменения разрядности представления интервала арифметического кодирования в соответствии с предварительно сформированной ДП СК и номером n-го кодового блока, у отправителя перед кодированием очередной УДП квантованных вейвлет коэффициентов n-го кодового блока с использованием арифметического кодирования вносит для нарушителя дополнительную неопределенность о длине кодированной последовательности, которая должна быть сформирована в результате арифметического кодирования очередной УДП квантованных вейвлет коэффициентов n-го кодового блока при использовании неизвестного для нарушителя секретного ключа. Тем самым нарушитель без знания ключа не может сформировать из неподлинного электронного изображения кодированное электронное изображение, которое будет признано получателем подлинным. Поэтому указанная новая совокупность действий позволяет повысить защищенность от подмены нарушителем подлинного аутентифицированного ЭИ на неподлинное ЭИ.
Заявленный способ поясняется чертежами, на которых показаны:
- на фиг. 1 - общая схема аутентификации ЭИ;
- на фиг. 2 - рисунки, поясняющие предварительное формирование ДП СК;
- на фиг. 3 - алгоритм формирования аутентифицированного ЭИ;
- на фиг. 4 - временные диаграммы формирования аутентифицированного n-го кодового блока;
- на фиг. 5 - временные диаграммы кодирования УДП КВК n-го кодового блока с использованием арифметического кодирования в кодированные последовательности этого блока при установке разрядности представления интервала арифметического кодирования в соответствии с предварительно сформированной ДП СК;
- на фиг. 6 - таблица состояний арифметического кодирования УДП КВК n-го кодового блока в кодированные последовательности этого блока при установке разрядности представления интервала арифметического кодирования в соответствии с предварительно сформированной ДП СК;
- на фиг. 7 - временные диаграммы проверки подлинности n-го принятого кодового блока;
- на фиг. 8 - алгоритм проверки подлинности принятого ЭИ;
- на фиг. 9 - временные диаграммы декодирования кодированных последовательностей n-го принятого кодового блока с использованием арифметического декодирования при установке разрядности представления интервала арифметического кодирования в соответствии с предварительно сформированной ДП СК;
- на фиг. 10 - таблица состояний арифметического декодирования кодированных последовательностей n-го принятого кодового блока с использованием арифметического декодирования при установке разрядности представления интервала арифметического кодирования в соответствии с предварительно сформированной ДП СК;
- на фиг. 11 - временные диаграммы декодирования кодированных последовательностей n-го принятого кодового блока с использованием арифметического декодирования без установки разрядности представления интервала арифметического кодирования в соответствии с предварительно сформированной ДП СК;
- на фиг. 12 - значения вероятности необнаруживаемой подмены электронного изображения на кодовый блок для способа-прототипа и заявленного способа аутентификации ЭИ.
Реализация заявленного способа представлена на примере системы аутентификации ЭИ, включающей блок формирования кодированного ЭИ 1 и блок проверки принятого ЭИ 2, которые взаимодействуют через канал передачи 4 (фиг. 1). У отправителя на первый и второй входы блока формирования кодированного ЭИ 1 принимают ЭИ и ДП СК соответственно. С выхода блока формирования кодированного ЭИ 1 кодированное с обеспечением аутентификации ЭИ передают по каналу передачи 4 получателю. Также в канале передачи 4 нарушителем с использованием блока перехвата и навязывания неподлинного ЭИ 3 может осуществляться перехват переданного отправителем кодированного с обеспечением аутентификации ЭИ. Нарушитель пытается модифицировать перехваченное ЭИ в выгодное ему неподлинное ЭИ, которое нарушитель передает получателю по каналу передачи 4. У получателя проверку подлинности принятого ЭИ осуществляют в блоке проверки принятого ЭИ 2 с использованием ДП СК. Результат проверки подлинности принятого ЭИ считывают с выходов блока проверки принятого ЭИ 2 "подлинное ЭИ " и "неподлинное ЭИ ", соответственно.
В способе аутентификации ЭИ реализуется следующая последовательность действий.
Предварительное формирование для отправителя и получателя ДП СК заключается в следующем. Данную последовательность формируют с использованием генератора случайных импульсов, генерирующего случайные равновероятные нулевые и единичные импульсы, независимых друг от друга. Способы формирования случайным выбором символов ДП СК известны и описаны, например, в книге: Д. Кнут "Искусство программирования на ЭВМ". - М.: Мир, 1977, т. 2, стр. 22. Длина ДП СК в битах должна быть не менее 256 бит, что описано, например, в ГОСТ 28147-89. Примерный вид ДП СК показан на фигуре 2. Единичные значения битов на фигурах показаны в виде заштрихованных импульсов, нулевые значения битов - в виде незаштрихованных импульсов.
1
2
1
2
Алгоритм формирования аутентифицированного ЭИ представлен на фигуре 3. Аутентифицируемое ЭИ представлено матрицей пикселей электронного изображения размером w×w пикселов, где w≥2 и w≥2. Примерный вид значений яркости пикселей (ЯП) ЭИ, поочередно считанных слева направо строка за строкой сверху вниз, представлен на фигуре 4(a).
Известные способы выполнения над ЭИ вейвлет преобразования описаны, например, в книге S. Lyu, Н. Farid "Steganalysis Using Higher-Order Image Statistics", IEEE Transactions on Information Security and Forensics, vol. 1, pp. 111-119, 2006. Над ЭИ выполняют k - уровневое, где k=1,2,3,…K, а 1≤K≤10, вейвлет преобразование с формированием матрицы коэффициентов вейвлет преобразования ЭИ такого же размера, как и размер исходного ЭИ в пикселях. Матрица коэффициентов вейвлет преобразования ЭИ состоит из матриц горизонтальных, вертикальных, высокочастотных и низкочастотных коэффициентов вейвлет преобразования ЭИ. На фиг. 4(б) показан пример значений низкочастотных коэффициентов (низ. коэф.), вертикальных коэффициентов (вер. коэф.), высокочастотных коэффициентов (выс. коэф.) и горизонтальных коэффициентов (гор. коэф.) первого уровня вейвлет преобразования ЭИ. Видно, что вейвлет коэффициенты ЭИ принимают как положительные, так и отрицательные значения и могут быть нецелочисленными.
Способы квантования полученных в результате преобразования значений ВК ЭИ известны и описаны, например, в книге Я. Ричардсон "Видеокодирование. Н.264 и MPEG-4 - стандарты нового поколения". - М.: Техносфера, 2005, стр. 78-80. Значения ВК ЭИ квантуют путем их округления до ближайшего целого значения. Примерный вид квантованных вейвлет коэффициентов (КВК) ЭИ показан на фигуре 4(в).
1
2
1
2
1
2
Способы разделения квантованных вейвлет коэффициентов на N≥2 кодовых блоков каждый размером n×n коэффициентов, где n≥2 и n≥2, известны и описаны, например, в книге Я. Ричардсон "Видеокодирование. Н.264 и MPEG-4 - стандарты нового поколения". - М., Техносфера, 2005, стр. 38-40. Из матрицы квантованных вейвлет коэффициентов ЭИ, начиная, например, с ее левого верхнего угла, выделяют матрицу коэффициентов размера n строк и n столбцов, которая образует n-ый, где n=1,2,…,N, кодовый блок, в данном случае первый кодовый блок. Затем справа или снизу от выделенной матрицы коэффициентов выделяют следующую матрицу коэффициентов такого же размера, которая образует следующий кодовый блок и так пока из матрицы квантованных вейвлет коэффициентов ЭИ не выделены все коэффициенты. Размер кодовых блоков выбирают, например, порядка 16×16, 32×32 коэффициентов и т.д., что определяется числом формируемых вейвлет коэффициентов кодового блока. Примерный вид квантованных вейвлет коэффициентов n-го кодового блока представлен на фигуре 4(г).
1
2
1
2
Способы преобразования квантованные вейвлет коэффициенты n-го кодового блока в их ДП известны и описаны, например, в книге: ISO/IES 15444-1. Information technology - JPEG2000 image coding system. Женева. 2001, стр. 219-222. КВК n-го кодового блока по фиксированному правилу кодирования преобразовывают в ДП КВК этого блока. Оно заключается в преобразовании целочисленного значения каждого КВК n-го кодового блока в двоичную последовательность, в которой каждый последующий бит отличается по информационной значимости в 2 раза, а старший двоичный символ этой двоичной последовательности кодирует знак квантованного вейвлет коэффициента. Положительное значение квантованного вейвлет коэффициента кодируют, например, единичным двоичным символом, а отрицательное значение - нулевым двоичным символом. Например, значение первого КВК n-го кодового блока, равное -8=-(8+0+0+0), преобразовывают в первую ДП КВК этого блока вида 01000, а значение второго КВК этого блока, равное +273=256+16+1, преобразовывают во вторую ДП КВК этого блока вида 1110010001, а значение последнего n×n-го КВК этого блока, равное +241=128+64+32+16+1, преобразовывают в n×n-ю ДП КВК этого блока вида 111110001. Примерный вид ДП КВК n-го кодового блока показан на фигуре 4(д).
L-1
Способы преобразования двоичных последовательностей КВК n-го кодового блока в L≥2 упорядоченных двоичных последовательностей КВК этого блока известны и описаны, например, в книге В. Воробьев, В. Грибунин "Теория и практика вейвлет-преобразования". - СПб., ВУС, 1999, стр. 159-161. Они заключаются в последовательной записи первых битов всех двоичных последовательностей КВК n-го кодового блока в первую упорядоченную двоичную последовательность КВК этого блока, последовательной записи вторых битов всех двоичных последовательностей КВК n-го кодового блока во вторую УПД КВК этого блока и т.д. Упорядоченность двоичных последовательностей КВК n-го кодового блока заключается в выбранном порядке последовательной записи битов двоичных последовательностей КВК n-го кодового блока ЭИ в УДП КВК этого блока. Число L выбирают как наименьшее целое число, обеспечивающее соотношение вида: значение 2 должно быть не меньше абсолютной величины наибольшего значения квантованных вейвлет коэффициентов n-го кодового блока с учетом знака. Примерный вид УДП КВК n-го кодового блока показан на фиг. 4(e). Например, первая УДП КВК первого кодового блока имеет вид 0111…1.
Способы изменения разрядности представления интервала арифметического кодирования в соответствии с предварительно сформированной ДП СК и номером n-го кодового блока перед кодированием каждой очередной УДП квантованных вейвлет коэффициентов n-го кодового блока с использованием арифметического кодирования заключаются в следующем. Из предварительно сформированной ДП СК считывают очередную двоичную подпоследовательность секретного ключа длиною k бит. Перед кодированием первой УДП квантованных вейвлет коэффициентов n-го кодового блока считывают первую двоичную подпоследовательность секретного ключа, перед кодированием второй УДП квантованных вейвлет коэффициентов этого кодового блока считывают вторую двоичную подпоследовательность секретного ключа и так далее.
r
r
Считанную двоичную подпоследовательность преобразуют в десятичное число, считая, например, ее левый символ наиболее значимым. Например, при k=6 бит десятичное представление считанной двоичной подпоследовательности принадлежит интервалу значений от 0 до 63. Десятичный номер n-го кодового блока преобразуют в его двоичную последовательность. Считанную двоичную подпоследовательность СК и двоичную последовательность номера n-го кодового блока суммируют, начиная с одноименных младших двоичных битов, по модулю 2. Способы суммирования двух двоичных последовательностей известны и описаны, например, в книге: А. Сикарев, О. Лебедев "Микроэлектронные устройства формирования и обработки сложных сигналов". - М.: Радио и связь, 1983, стр. 107-108 на основе сумматоров по модулю 2. Устанавливают разрядность r представления интервала арифметического кодирования перед кодированием очередной УДП квантованных вейвлет коэффициентов n-го кодового блока с использованием арифметического кодирования, например, равной сумме десятичного представления суммированной двоичной последовательности и фиксированного числа w>0. Фиксированное число w исключает возможность установки недопустимо малой разрядности представления интервала арифметического кодирования, пусть, например, фиксированное число равно w=3. Например, считанная первая двоичная подпоследовательность имеет вид "001000", как показано на фиг. 2, а ее десятичное представление равно 8. При w=3 разрядность r представления интервала арифметического кодирования перед кодированием первой УДП квантованных вейвлет коэффициентов n-го кодового блока с использованием арифметического кодирования равна r=11. Разрядность r определяет диапазон возможных значений интервала кодирования арифметического кодирования в пределах от 0 до 2-1. При установленной таким образом разрядности r устанавливают начальное нижнее значение интервала кодирования в минимальное значение, равное, например, нулю, и начальное верхнее значение интервала кодирования в максимальное значение, равное, например, 2-1. Например, при r=11 начальное нижнее значение интервала кодирования арифметического кодирования L[0] устанавливают в минимальное значение, равное нулевому значению в десятичном представлении или 00000000000 в двоичном представлении длиной 11 символов, где старшие двоичные символы записывают слева, а начальное верхнее значение интервала кодирования арифметического кодирования Н[0] устанавливают в максимальное значение, равное 2047 в десятичном представлении или 11111111111 в двоичном представлении. Пример начального состояния (Нач. сост.) интервала кодирования арифметического кодирования представлен на фиг. 5.
0
1
0
1
0
1
0
1
0
1
0
1
0
1
1
0
<mrow><msub><mi>p</mi><mn>0</mn></msub><mrow><mo>[</mo><mn>0</mn><mo>]</mo></mrow><mo>=</mo><mfrac><mrow><msub><mi>N</mi><mn>0</mn></msub><mrow><mo>[</mo><mn>0</mn><mo>]</mo></mrow></mrow><mrow><mi>N</mi><mrow><mo>[</mo><mn>0</mn><mo>]</mo></mrow></mrow></mfrac></mrow>
<mrow><msub><mi>p</mi><mn>1</mn></msub><mrow><mo>[</mo><mn>0</mn><mo>]</mo></mrow><mo>=</mo><mfrac><mrow><msub><mi>N</mi><mn>1</mn></msub><mrow><mo>[</mo><mn>0</mn><mo>]</mo></mrow></mrow><mrow><mi>N</mi><mrow><mo>[</mo><mn>0</mn><mo>]</mo></mrow></mrow></mfrac></mrow>
Для установки начального состояния (Нач. сост.) интервала кодирования арифметического кодирования также устанавливают начальное значение вероятности кодируемых нулевых символов р[0] и начального значения вероятности кодируемых единичных символов р[0]. При установке начального значения вероятности кодируемых нулевых символов р[0] и начального значения вероятности кодируемых нулевых символов p[0] в выбранные значения должно выполняться ограничение вида: p[0]+р[0]=1. Начальное значение вероятности кодируемых нулевых символов р[0] вычисляют по формуле вида
, начальное значение вероятности кодируемых единичных символов p[0] вычисляют по формуле вида
, где N[0] - начальное число закодированных нулевых символов, N[0] - начальное число закодированных единичных символов, а N[0] - начальное число закодированных нулевых и единичных символов, равное N[0]=N[0]+N[0]. В известных способах, описанных, например, в книге Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин "Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео". - М.: ДИАЛОГ-МИФИ, 2002, стр. 124-130, устанавливают начальное число закодированных нулевых символов равным N[0]=l, а начальное число закодированных единичных символов - равным N[0]=1, то есть начальные значения вероятности кодируемых единичных и нулевых символов устанавливают равными: p[0]=р[0].
0
1
0
1
1
1
1
0
0
1
1
0
Начальное значение интервала кодирования арифметического кодера I[0], равное I[0]=Н[0]-L[0], разделяют на начальные значения подинтервала нулевых символов D[0] и подинтервала единичных символов D[0], длины которых прямо пропорциональны начальным значениям вероятностей кодируемых нулевых символов р[0] и единичных символов р[0] соответственно. Начальную длину подинтервала единичных символов D[0] определяют по формуле вида D[0]=I[0]×р[0], а начальную длину подинтервала нулевых символов D[0] определяют по формуле вида D[0]=I[0]-D[0]. Например, начальная длина подинтервала единичных символов D[0] имеет десятичное значение 1024 или 10000000000 в двоичном представлении, а начальная длина подинтервала нулевых символов D[0] имеет десятичное значение 1023 или 01111111111 в двоичном представлении. Подинтервал единичных символов расположен сверху подинтервала нулевых символов, как показано, например, на фиг. 5. Верхнюю границу подинтервала нулевых символов обозначают как значение Q, и данный подинтервал начинается снизу от нижней границы интервала кодирования арифметического кодирования до значения Q исключительно, а подинтервал единичных символов простирается от значения Q включительно до верхней границы интервала кодирования арифметического кодирования исключительно. Например, начальное значение Q имеет десятичное значение 1023, как показано на фиг. 6 в первой строке при t=0.
Способы кодирования каждой очередной, с первой до L-ой, УДП КВК n-го кодового блока с использованием арифметического кодирования в кодированные последовательности n-го кодового блока известны и описаны, например, в книге Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин "Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео". - М., ДИАЛОГ-МИФИ, 2002, стр. 35-43. Они заключаются в последовательном кодировании очередных двоичных символов УДП КВК n-го кодового блока в соответствии с текущими значениями интервала кодирования арифметического кодирования и текущими значениями вероятностей кодируемых нулевых символов и единичных символов с последовательным формированием кодированных последовательностей n-го кодового блока.
Примерный вид кодирования показанной на фиг. 4(e) первой УДП КВК n-го кодового блока в виде двоичной последовательности "011111" длиною 6 двоичных символов с использованием арифметического кодирования в кодированные последовательности n-го кодового блока при установке разрядности представления интервала арифметического кодирования в соответствии с предварительно сформированной ДП СК представлен на фиг. 5.
0
При поступлении на вход арифметического кодирования первого кодируемого символа, являющегося нулевым двоичным символом, значение интервала кодирования первого символа I[1] устанавливают равным начальному значению подинтервала нулевых символов D[0], поэтому нижнее значение интервала кодирования первого символа L[1] устанавливают равным начальному нижнему значению интервала кодирования арифметического кодера L[0], равному, например, нулю, а верхнее значение интервала кодирования первого символа арифметического кодирования Н[1] устанавливают равным текущему значению Q, равному, например, 1023, как показано на фиг. 6 при t=1. Самый левый бит двоичного представления значения L[1] сравнивают с самым левым битом двоичного представления значения Н[1], например, вида 000…0 и 0111…1 соответственно. При их совпадении значение самого левого бита двоичных представлений значений L[1] и H[1] считывают в качестве закодированного бита кодированной последовательности n-го кодового блока. Например, при кодировании УДП КВК n-го кодового блока в виде двоичной последовательности "0111111" первым закодированным битом кодированной последовательности этого блока является совпавший при сравнении нулевой двоичный символ, как показано на фиг. 6, вторая строка сверху при t=1. Считанный бит удаляют из двоичных представлений значений L[1] и Н[1], которые уменьшаются до длины 10 бит вида 00…0 и 11…1 соответственно. Двоичные символы двоичных представлений значений L[1] и H[1] сдвигают справа налево на один разряд и справа к ним дописывают по нулевому двоичному символу. Способы считывания двоичных символов с удалением считанных символов известны и описаны, например, в книге: В. Шило "Популярные цифровые микросхемы". - М., Радио и связь, 1987, 104-123, с использованием регистров сдвига с параллельной и последовательной записью/считыванием двоичных последовательностей. Операции сдвига справа налево на один разряд и дописывания справа нулевого двоичного символа увеличивают значения L[1] и H[1] в 2 раза и называются нормализацией параметров арифметического кодирования. Способы сдвига на один разряд в сторону старших разрядов двоичных последовательностей и записи в освободившийся младший разряд нулевого двоичного символа известны и описаны, например, в книге: В. Шило "Популярные цифровые микросхемы". - М.: Радио и связь, 1987, 104-123, с использованием регистров сдвига с параллельной и последовательной записью/считыванием двоичных последовательностей, и по своей сути являются умножением на два десятичных значений нижнего и верхнего значений интервала кодирования.
В результате нормализации нижнее значение интервала кодирования первого символа приняло значение 0, а верхнее значение интервала кодирования приняло двоичное значение 111…10 или десятичное значение 2046, как показано на фиг. 6.
После каждого выполнения нормализации повторно самый левый бит двоичного представления нижнего значения интервала кодирования сравнивают с самым левым битом двоичного представления верхнего значения интервала кодирования. При их совпадении значение самого левого бита этих двоичных представлений считывают в качестве следующего закодированного бита кодированной последовательности n-го кодового блока. Например, после выполнения описанной нормализации между собой сравнивают самые левые биты двоичных представлений вида 000…0 и 111…10 и при их несовпадении переходят к кодированию следующего бита УДП КВК n-го кодового блока и так далее до окончания кодируемых битов УДП КВК этого блока.
0
0
1
0
1
<mrow><msub><mi>p</mi><mn>0</mn></msub><mo stretchy="false">[</mo><mn>1</mn><mo stretchy="false">]</mo><mo>=</mo><mfrac><mrow><msub><mi>N</mi><mn>0</mn></msub><mo stretchy="false">[</mo><mn>1</mn><mo stretchy="false">]</mo></mrow><mrow><mi>N</mi><mo stretchy="false">[</mo><mn>1</mn><mo stretchy="false">]</mo></mrow></mfrac><mo>=</mo><mfrac><mn>2</mn><mn>3</mn></mfrac></mrow>
<mrow><msub><mi>p</mi><mn>1</mn></msub><mo stretchy="false">[</mo><mn>1</mn><mo stretchy="false">]</mo><mo>=</mo><mfrac><mrow><msub><mi>N</mi><mn>1</mn></msub><mo stretchy="false">[</mo><mn>1</mn><mo stretchy="false">]</mo></mrow><mrow><mi>N</mi><mo stretchy="false">[</mo><mn>1</mn><mo stretchy="false">]</mo></mrow></mfrac><mo>=</mo><mfrac><mn>1</mn><mn>3</mn></mfrac></mrow>
После выполнения кодирования каждого очередного бита УДП КВК n-го кодового блока уточняют число закодированных нулевых символов и единичных символов. Так как первый кодированный бит является нулевым, то число закодированных нулевых символов увеличивают на единичное значение и оно составляет N[1]=2, и число закодированных нулевых и единичных символов становится равным N[1]=N[l]+N[l]=3. Пересчитывают текущее значение вероятности кодируемых нулевых символов
и текущее значение вероятности кодируемых единичных
. В соответствии с этим длина подинтервала нулевых символов D[1] становится в 2 раза больше длины подинтервала единичных символов D[1], а параметр Q принимает значение 1364, как показано на фиг. 5 и на фиг. 6, третья строка сверху.
Например, второй бит УДП КВК n-го кодового блока является единичным двоичным символом, как показано на фиг. 6, при t=2. При поступлении на вход арифметического кодирования единичного двоичного символа значение интервала кодирования арифметического кодирования устанавливают равным значению предыдущего подинтервала единичных символов, поэтому нижнее значение интервала кодирования L[2] устанавливают равным значению Q, а верхнее значение интервала кодирования H[2] устанавливают равным предыдущему верхнему значению интервала кодирования Н[1]. Например, как показано на фиг. 5, значение L[2] устанавливают равным 1364, а Н[2] остается равным предыдущему значению 2046. Повторно самый левый бит двоичного представления значения L[2] сравнивают с самым левым битом двоичного представления значения Н[2] и при их совпадении значение самого левого бита двоичных представлений значений L[2] и Н[2] считывают в качестве очередного закодированного бита кодированной последовательности n-го кодового блока и так далее до окончания УДП КВК n-го кодового блока. Например, результатом кодирования первой УДП КВК n-го кодового блока в виде двоичной последовательности "011111" является двоичная последовательность вида "01111".
После кодирования последнего двоичного символа очередной упорядоченной двоичной последовательности КВК n-го кодового блока разделительный маркер УДП выбирают случайным образом в интервале кодирования последнего двоичного символа данной УДП. С использованием генератора случайных чисел генерируют случайное значение, находящееся в пределах интервала кодирования последнего двоичного символа данной УДП. Способы формирования случайных значений известны и описаны, например, в книге: Д. Кнут "Искусство программирования на ЭВМ". - М.: Мир, 1977, т. 2, стр. 22. Например, после кодирования последнего, шестого по счету, двоичного символа данной УДП и выполнения нормализации интервал кодирования находится в пределах от 458 до 2016. Случайным образом в данном интервале кодирования выбирают разделительный маркер УДП с десятичным значением 475 или двоичным значением "001 1101 1011", как показано на фиг. 6, предпоследняя строка.
Способы записи разделительного маркера УДП по окончании арифметического кодирования УДП КВК n-го кодового блока в ДП сжатого ЭИ известны и описаны, например, в книге: В. Шило "Популярные цифровые микросхемы". - М.: Радио и связь, 1987, 104-123, с использованием регистров сдвига с параллельной и последовательной записью/считыванием двоичных последовательностей.
Если в n-ом кодовом блоке не все L УДП квантованных вейвлет коэффициентов закодированы, то выполняют кодирование очередной УДП КВК n-го кодового блока, при этом перед ее кодированием изменяют разрядность представления интервала арифметического кодирования в соответствии с предварительно сформированной ДП СК. Например, для кодирования второй УДП КВК этого кодового блока из предварительно сформированной ДП СК считывают вторую двоичную подпоследовательность секретного ключа вида "100100", как показано на фиг. 2, и т.д.
Примерный вид кодирования первой УДП КВК n-го кодового блока в виде двоичной последовательности "011111" длиною 6 двоичных символов с использованием арифметического кодирования в кодированные последовательности n-го кодового блока при установке разрядности представления интервала арифметического кодирования в соответствии с предварительно сформированной ДП СК представлен на фиг. 5, а последовательные состояния арифметического кодирования показаны на фиг. 6.
Способы записи разделительного маркера кодового блока по окончании арифметического кодирования всех УДП КВК n-го кодового блока в ДП сжатого ЭИ известны и описаны, например, в книге: В. Шило "Популярные цифровые микросхемы". - М.: Радио и связь, 1987, 104-123, с использованием регистров сдвига с параллельной и последовательной записью/считыванием двоичных последовательностей. Разделительный маркер кодового блока предназначен для обеспечения возможности разделения ДП принятого получателем ЭИ на двоичные последовательности его принятых кодовых блоков. Разделительный маркер кодового блока является уникальной двоичной последовательностью априори известного для отправителя и получателя вида. Примерный вид разделительного маркера кодового блока в виде уникальной двоичной последовательности вида 0101…01 показан на фиг. 4(ж).
Примерный вид кодированных последовательностей (КП) с первой по L-ой УДП КВК n-го кодового блока показан на фиг. 4(ж).
Примерный вид двоичной последовательности кодированного (кодир.) ЭИ, состоящей из двоичных последовательностей с первого до N-го кодовых блоков, показан на фиг. 4(з).
Способы передачи получателю кодированного ЭИ известны и описаны, например, в книге А.Г. Зюко, Д.Д. Кловский, М.В. Назаров, Л.М. Финк "Теория передачи сигналов". - М.: Радио и связь, 1986, стр. 11. Примерный вид двоичной последовательности принятого получателем ЭИ показан на фиг. 7(a).
Алгоритм проверки подлинности n-го принятого кодового блока представлен на фиг. 8.
Способы разделения ДП принятого получателем ЭИ на кодированные последовательности принятых кодовых блоков известны и описаны, например, в книге: А. Сикарев, О. Лебедев "Микроэлектронные устройства формирования и обработки сложных сигналов". - М., Радио и связь, 1983, стр. 72-80. Они заключаются в разделении ДП принятого получателем ЭИ на кодированные последовательности его принятых кодовых блоков с использованием разделительного маркера кодового блока известного получателю вида, указывающего границы каждого принятого блока. Примерный вид КП n-го принятого кодового блока представлен на фигуре 7(б).
Способы изменения разрядности представления интервала арифметического декодирования в соответствии с предварительно сформированной ДП СК и номером n-го принятого блока ЭИ перед декодированием каждой очередной кодированной последовательности n-го принятого кодового блока с использованием арифметического декодирования, в точности соответствуют ранее описанным способам изменения разрядности представления интервала арифметического кодирования в соответствии с предварительно сформированной ДП СК и номером n-го блока ЭИ перед кодированием каждой очередной УДП квантованных вейвлет коэффициентов n-го кодового блока с использованием арифметического кодирования.
r
При установленной разрядности r представления интервала арифметического декодирования в соответствии с предварительно сформированной ДП СК и номером n-го принятого блока ЭИ устанавливают начальное нижнее значение интервала декодирования в минимальное значение, равное нулю, и начальное верхнее значение интервала декодирования в максимальное значение, равное 2-1. Например, при r=11 начальное нижнее значение интервала декодирования арифметического декодирования LL[0] устанавливают в минимальное значение, равное нулевому значению в десятичном представлении или 00000000000 в двоичном представлении длиной 11 символов, где старшие двоичные символы записывают слева, а начальное верхнее значение интервала декодирования арифметического декодирования НН[0] устанавливают в максимальное значение, равное 2047 в десятичном представлении или 11111111111 в двоичном представлении. Начальное состояние арифметического декодирования представлено на фиг. 9.
0
1
0
1
1
1
1
0
0
1
0
1
0
1
<mrow><mi>p</mi><msub><mi>p</mi><mn>1</mn></msub><mo stretchy="false">[</mo><mn>0</mn><mo stretchy="false">]</mo><mo>=</mo><mfrac><mrow><mi>N</mi><msub><mi>N</mi><mn>1</mn></msub><mo stretchy="false">[</mo><mn>0</mn><mo stretchy="false">]</mo></mrow><mrow><mi>N</mi><mi>N</mi><mo stretchy="false">[</mo><mn>0</mn><mo stretchy="false">]</mo></mrow></mfrac><mo>=</mo><mfrac><mn>1</mn><mn>2</mn></mfrac></mrow>
<mrow><mi>p</mi><msub><mi>p</mi><mn>0</mn></msub><mo stretchy="false">[</mo><mn>0</mn><mo stretchy="false">]</mo><mo>=</mo><mfrac><mrow><mi>N</mi><msub><mi>N</mi><mn>0</mn></msub><mo stretchy="false">[</mo><mn>0</mn><mo stretchy="false">]</mo></mrow><mrow><mi>N</mi><mi>N</mi><mo stretchy="false">[</mo><mn>0</mn><mo stretchy="false">]</mo></mrow></mfrac><mo>=</mo><mfrac><mn>1</mn><mn>2</mn></mfrac></mrow>
Начальное значение интервала декодирования арифметического декодера II[0], равное II[0]=HH[0]-LL[0], где LL[0] - начальное нижнее значение интервала декодирования арифметического декодера, а HH[0] - начальное верхнее значение интервала декодирования арифметического декодера, разделяют на начальные значения подинтервала декодирования нулевых символов DD[0] и подинтервала декодирования единичных символов DD[0], длины которых прямо пропорциональны начальным значениям вероятности декодируемых нулевого символа рр[0] и единичного символа рр[0] соответственно. Начальную длину подинтервала декодирования единичных символов DD[0] определяют по формуле вида DD[0]=II[0]×рр[0], а начальную длину подинтервала декодирования нулевых символов DD[0] определяют по формуле вида DD[0]=II[0]-DD[0]. Например, как показано на фиг. 10 при t=0, установлены начальные значения LL[0]=16384 и НН[0]=32768. На фиг. 10 показана таблица состояний арифметического декодирования кодированных последовательностей n-го принятого кодового блока с использованием арифметического декодирования при установке разрядности представления интервала арифметического кодирования в соответствии с предварительно сформированной ДП СК. Например, начальное число декодированных нулевых символов равно NN[0]=1, а начальное число декодированных единичных символов - NN[0]=1, соответственно начальное число декодированных нулевых и единичных символов равно NN[0]=NN[0]+NN[0]=1+1=2. Соответственно начальное значение вероятности декодируемых единичных символов равно
и начальное значение вероятности декодируемых нулевых символов равно
. Верхнее значение подинтервала декодирования нулевых символов обозначают как значение QQ, и данный подинтервал начинается снизу от нижнего значения интервала декодирования до значения QQ исключительно, а подинтервал декодирования единичных символов простирается от значения QQ включительно до верхнего значения интервала декодирования исключительно. Начальное значение QQ имеет десятичное значение 1023, как показано на фиг. 10 при t=0.
0
1
Для сравнения начальное состояние арифметического декодирования без установки разрядности представления интервала арифметического кодирования в соответствии с предварительно сформированной ДП СК представлено на фиг. 11. Нарушитель в силу незнания ДП СК отличным от получателя образом устанавливает начальное состояние арифметического декодирования, выбирая свое значение разрядности представления интервала арифметического кодирования, например, r=16. При r=16 нарушитель устанавливает начальные границы интервала декодирования вида LL[0]=0 и HH[0]=65535, начальные значения вероятности декодируемых нулевого символа рр[0]=1/2 и единичного символа рр[0]=1/2, как показано на фиг. 11.
Способы декодирования кодированных последовательностей n-го Пр. кодового блока с использованием арифметического декодирования известны и описаны, например, в книге Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин "Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео". - М., ДИАЛОГ-МИФИ, 2002, стр. 35-43. Они заключаются в последовательном декодировании с использованием арифметического декодирования кодированных последовательностей n-го Пр. кодового блока в соответствии с текущими значениями интервала декодирования арифметического декодера и текущими значениями вероятности декодируемых нулевого символа и единичного символа.
0
1
0
На вход арифметического декодирования с установленным значением разрядности представления интервала арифметического декодирования в соответствии с предварительно сформированной ДП СК поступают кодированные последовательности n-го Пр. кодового блока, например КП первой УДП КВК вида 0111 1001 1101 1011 длиной 16 двоичных символов, сформированной арифметическим кодированием с установленным значением разрядности представления интервала арифметического кодирования в соответствии с предварительно сформированной ДП СК. В соответствии с установленным значением разрядности на вход арифметического декодирования считывают входные данные из первых 11 бит данной кодированной последовательности вида 0111 1001 110, что соответствует десятичному числу 974. Текущее значение считанной кодированной последовательности, указанное на фиг. 9 стрелкой, сравнивают с границами начального значения подинтервала декодирования нулевых символов DD[0], находящимися, например, в пределах от 0 до 1023 и с границами начального значения подинтервала декодирования единичных символов DD[0], находящимися, например, в пределах от 1023 до 2046. В зависимости от того, в пределах какого подинтервала декодирования символов оказалось текущее значение считанной кодированной последовательности, принимается решение о декодировании очередного символа упорядоченной двоичной последовательности КВК n-го принятого кодового блока. Например, так как текущее значение считанной кодированной последовательности оказалось меньше значения QQ, то первый декодированный символ является нулевым и следующие границы интервала декодирования устанавливают соответствующими границам начального значения подинтервала декодирования нулевых символов DD[0].
Для декодирования следующего символа устанавливают нижнее значение интервала декодирования арифметического кодирования LL[1] равным предыдущему значению LL[0], например, LL[0]=0, а верхнее значение интервала декодирования арифметического кодирования НН[1] равным значению QQ, например QQ=1023, как показано на фиг. 10 при t=1. Самый левый бит двоичного представления значения LL[1] сравнивают с самым левым битом двоичного представления значения НН[1], например, вида 000…0 и 0111…1 соответственно. При их совпадении выполняют нормализацию арифметического декодирования: значение самого левого бита двоичных представлений значений LL[l] и НН[1] удаляют и двоичные символы двоичных представлений значений LL[l] и НН[1] сдвигают справа налево на один разряд и справа к ним дописывают по нулевому двоичному символу. Одновременно с этим значение самого левого бита входных данных удаляют и двоичные символы входных данных сдвигают справа налево на один разряд и справа к ним дописывают следующий двоичный символ декодируемой последовательности, например единичный символ, двенадцатый по счету в КП первой УДП КВК. Как, например, показано на фиг. 10 в третьей строке сверху "нормализация", входные данные приобретают двоичное представление 111 1001 1101 и десятичное значение 1949. Переменная LL[1] принимает значение 0 и двоичное представление 000…0, а НН[1] - десятичное значение 2046 и двоичное представление 11…10.
После каждого выполнения нормализации повторно самый левый бит двоичного представления значения LL сравнивают с самым левым битом двоичного представления значения НН, и при совпадении выполняют повторную нормализацию арифметического декодирования аналогичным образом. При их совпадении переходят к декодированию следующего символа.
<mrow><mi>p</mi><msub><mi>p</mi><mn>0</mn></msub><mo stretchy="false">[</mo><mn>1</mn><mo stretchy="false">]</mo><mo>=</mo><mfrac><mrow><mi>N</mi><msub><mi>N</mi><mn>0</mn></msub><mo stretchy="false">[</mo><mn>1</mn><mo stretchy="false">]</mo></mrow><mrow><mi>N</mi><mi>N</mi><mo stretchy="false">[</mo><mn>1</mn><mo stretchy="false">]</mo></mrow></mfrac><mo>=</mo><mfrac><mn>2</mn><mn>3</mn></mfrac></mrow>
<mrow><mi>p</mi><msub><mi>p</mi><mn>1</mn></msub><mo stretchy="false">[</mo><mn>1</mn><mo stretchy="false">]</mo><mo>=</mo><mfrac><mrow><mi>N</mi><msub><mi>N</mi><mn>1</mn></msub><mo stretchy="false">[</mo><mn>1</mn><mo stretchy="false">]</mo></mrow><mrow><mi>N</mi><mi>N</mi><mo stretchy="false">[</mo><mn>1</mn><mo stretchy="false">]</mo></mrow></mfrac><mo>=</mo><mfrac><mn>1</mn><mn>3</mn></mfrac></mrow>
После декодирования каждого символа пересчитывают текущее значение вероятности декодируемого нулевого символа и текущее значение вероятности декодируемого нулевого символа, например, после декодирования первого символа, являющегося нулевым, по формуле вида
и по формуле вида
соответственно. Устанавливают текущие длины подинтервалов декодирования единичных символов и нулевых символов и устанавливают текущее значение QQ=1364 с двоичным представлением вида 101 0101 0100, как показано на фиг. 10 в третьей строке сверху "нормализация".
Для декодирования следующего символа, второго по счету, текущее десятичное значение входных данных сравнивают с границами текущего значения подинтервала декодирования нулевых символов и подинтервала декодирования единичных символов. Текущее десятичное значение 1949 входных данных оказалось в пределах подинтервала декодирования единичных символов, поэтому очередной, второй по счету, декодированный символ является единичным, как показано на фиг. 10 в четвертой строке сверху при t=2.
Для декодирования следующего символа устанавливают нижнее значение интервала декодирования LL[2] равным QQ, например QQ=1364, а верхнее значение интервала декодирования НН[2] равным предыдущему значению LL[1]. Самый левый бит двоичного представления значения LL[2] сравнивают с самым левым битом двоичного представления значения НН[2] и при их совпадении выполняют нормализацию арифметического декодирования и т.д.
1
2
После декодирования очередных n×n битов декодирование кодированной последовательности очередной УДП КВК m-го Пр. блока ЭИ заканчивают и выполняют декодирование следующей кодированной последовательности этого принятого кодового блока с использованием арифметического декодирования, перед чем изменяют разрядность представления интервала арифметического декодирования в соответствии с предварительно сформированной ДП СК, для чего из предварительно сформированной ДП СК считывают следующую двоичную подпоследовательность секретного ключа длиною k бит и т.д.
1
2
Если из двоичной последовательности n-го Пр. блока ЭИ декодировано L×n×n битов, то n-ый принятый кодовый блок считают подлинным, иначе его считают неподлинным. Принятое ЭИ считают подлинным, если подлинными оказываются все N принятых кодовых блоков.
1
2
Способы подсчета длины в битах декодированной последовательности известны и описаны, например, в книге А. Сикарев, О. Лебедев "Микроэлектронные устройства формирования и обработки сложных сигналов". - М.: Радио и связь, 1983, стр. 125-131, на основе использования двоичных счетчиков. Способы сравнения подсчитанной длины со значением L×n×n известны и описаны, например, в книге А. Сикарев, О. Лебедев. "Микроэлектронные устройства формирования и обработки сложных сигналов". - М.: Радио и связь, 1983, стр. 178-183. Они заключаются в побитном сравнении двоичных представлений сравниваемых значений с использованием цифровых компараторов, формирующих управляющий сигнал при несовпадении в любом сравниваемом двоичном разряде попарно сравниваемых значений.
1
2
1
2
Пример выполнения арифметического декодирования с установленным значением разрядности представления интервала арифметического декодирования не в соответствии с секретным ключом показан на фиг. 11. При выборе разрядности представления интервала арифметического кодирования, например, r=16, невозможно обеспечить условие проверки подлинности принятых кодовых блоков. Например, в результате арифметического декодирования с несоответствующим образом установленным значением разрядности представления интервала арифметического декодирования первой кодированной последовательности n-го Пр. кодового блока вида 0111 1001 1101 1011 арифметический декодер не может однозначно декодировать входную последовательность, им декодировано более 5 битов, что не равно установленному в данном примере значению n×n битов, равному 5. Это означает, что в результате из двоичной последовательности n-го Пр. блока ЭИ не будет декодировано L×n×n битов, то n-ый принятый кодовый блок считают неподлинным, и в целом принятое ЭИ будет признано неподлинным.
Проверка теоретических предпосылок заявленного способа аутентификации ЭИ проверялась путем его аналитических исследований.
необн
необн
-b
-32
-9
-k
L
Защищенность от подмены нарушителем подлинного аутентифицированного ЭИ на неподлинное ЭИ оценивается вероятностью необнаруживаемой подмены электронного изображения на кодовый блок. Вероятность необнаруживаемой подмены электронного изображения на кодовый блок для способа прототипа вычисляют по формуле Р≈2, где длину b аутентификатора, как правило, выбирают равной b=32 бита, что обеспечивает вероятность необнаруживаемой подмены 2≈10. В заявленном способе вероятность необнаруживаемой подмены электронного изображения на кодовый блок вычисляют по формуле Р≈(2). Параметр k определяет число различных вариантов разрядности представления интервала арифметического кодирования, например, при k=6 возможны 64 варианта разрядности представления интервала арифметического кодирования для каждой упорядоченной двоичной последовательности, выбираемые независимо друг от друга.
-17
-27
В таблице на фиг. 12 представлены значения вероятности необнаруживаемой подмены электронного изображения на кодовый блок при числе вариантов разрядности представления интервала арифметического кодирования 64 и 256 и при числе L упорядоченных двоичных последовательностей КВК в каждом кодовом блоке электронного изображения, равном L-9 и L=11. Данные значения L являются типичными при сжатии электронных изображений алгоритмом сжатия JPEG2000. В заявленном способе вероятность необнаруживаемой подмены электронного изображения на кодовый блок обеспечивается не более 5·10-3,2·10, что существенно меньше соответствующего показателя защищенности для способа-прототипа.
Таким образом, в заявленном способе аутентификации ЭИ достигается повышение защищенности от подмены нарушителем подлинного аутентифицированного ЭИ на неподлинное ЭИ.
Проведенные исследования подтверждают, что при использовании предлагаемого способа аутентификации ЭИ обеспечивается повышение защищенности от подмены нарушителем подлинного аутентифицированного ЭИ на неподлинное ЭИ.