Устройство крипто-корректирующего преобразования информации

06 11/08 НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ(71) Заявитель Учреждение образования Белорусский государственный технологический университет(72) Авторы Урбанович Павел Павлович Пацей Наталья Владимировна(73) Патентообладатель Учреждение образования Белорусский государственный технологический университет(57) Устройство крипто-корректирующего преобразования информации, содержащее на передающей стороне источник данных, выходами соединенный со входами первого регистра данных, первый источник ключа, выходами связанный со входами первого регистра ключа, блок помехоустойчивого кодирования, выход которого соединен с первым входом первого сумматора по модулю два, вторым входом подключенного к выходу первого генератора псевдослучайной последовательности, а выходом - к каналу передачи данных,соединенному на приемной стороне с первым входом второго сумматора по модулю два,вторым входом подключенного к выходу второго генератора псевдослучайной последовательности, а выходом соединенного со входом блока помехоустойчивого декодирования,второй источник ключа, выходами подключенный ко входам второго регистра ключа, отличающееся тем, что оно содержит блок сжатия данных, входом соединенный с выходом первого регистра данных, а выходом - со входом блока помехоустойчивого кодирования,блок развертывания, входом соединенный с выходом блока помехоустойчивого декодирования, а выходом - со вторым регистром данных, коммутирующим по выходам приемник данных, вход первого генератора псевдослучайной последовательности соединен с выходом первого регистра ключа, а вход второго генератора псевдослучайной последовательности - с выходом второго регистра ключа. Изобретение относится к криптографическим преобразованиям, сжатию данных и корректирующему кодированию и может быть использовано при хранении данных и в технике связи. Известны способы и устройства шифрования информации в системах связи и обработки информации, которые построены на основе криптографических алгоритмов и корректирующих кодов. Некоторые из этих систем построены на основе добавления к криптографическим преобразованиям схем помехоустойчивого кодирования после 1, 2, 3 либо до них 4 (в 3 используется схема обнаружения ошибок с запросом повторной передачи). Недостатком этих способов, и соответственно устройств, является то, что увеличивается размер закодированных данных и, как результат - замедление работы системы, снижение пропускной способности. Наиболее близким техническим решением к предлагаемому является устройство интегрированного криптографического и кодового преобразования и передачи информации 5, содержащее на передающий стороне источник данных , выходами соединенный со входами блока, реализующего функцию расширениявыходы его соединены со входами кодера , выходы которого соответственно коммутируются с выходами генератора искусственного шума , вследствие чего формируется канальное сообщениена передающей стороне, на приемной стороне устройство содержит канальный декодер, входами соединенный с каналом передачи, а выходами - со входами потребителя данных. В этом устройстве функция расширенияможет быть любой линейной временной зависимой или временной независимой функцией с памятью или без памяти, блоковым кодом или сверточным кодом. Процесс шифрования данных выглядит следующим образом, где- открытый текст,- сообщение, подаваемое на вход канала. В результате конкатенции (последовательного прибавления справа)иполучаем на приемной стороне интегрированный сверточный декодер , и дешифрование выглядит следующим образом, где- получаемое дешифрованное сообщение, а уе,где е, у - сообщение на выходе канала передачи,- аддитивная последовательность шума канала. Так как данная система осуществляет криптографическое преобразование данных, то необходимым условием ее функционирования является существование секретных элементов. В данном случае ключом, который должен держаться в секрете, является функция расширенияили, другими словами, сам алгоритм шифрования. Пример реализации функции , предложенный в 5, легко позволяет производить криптоанализ алгоритма за приемлемое время без знания функции , а при компрометации функции система вовсе не требует анализа и становится тривиальной системой коррекции ошибок, возникающих в канале. Вместе с тем использование корректирующего кода приводит к увеличению длины исходного сообщения, зависящей в общем случае от типа применяемого помехоустой 2 4997 1 чивого кода. Перечисленные особенности известного решения снижают эффективность его использования в системах передачи данных с криптопреобразованиями и помехоустойчивым кодированием. Задачей изобретения является снижение информационной избыточности сообщения и повышение эффективности устройства передачи потока данных с использованием криптографических преобразований и помехоустойчивого кодирования данных. Поставленная задача достигается тем, что в устройство крипто-корректирующего преобразования информации, содержащее на передающей стороне источник данных, выходами соединенный со входами первого регистра данных, первый источник ключа, выходами связанный со входами первого регистра ключа, блок помехоустойчивого кодирования, выход которого соединен с первым входом первого сумматора по модулю два, вторым входом подключенного к выходу первого генератора псевдослучайной последовательности (ПСП), а выходом - к каналу передачи данных, соединенному на приемной стороне с первым входом второго сумматора по модулю два, вторым входом подключенного к выходу второго генератора псевдослучайной последовательности, а выходом соединенного со входом блока помехоустойчивого декодирования, соединенному с регистром данных, устройство содержит также второй источник ключа, выходами подключенный ко входам второго регистра ключа, блок сжатия данных, входом соединенный с выходом первого регистра данных, а выходом - со входом блока помехоустойчивого кодирования, блок развертывания, входом соединенный с блоком помехоустойчивого декодирования, а выходом - со вторым регистром данных, входы первого генератора псевдослучайной последовательности соединены с выходами первого регистра ключа, а выходы второго генератора псевдослучайной последовательности - с выходами второго регистра ключа. Сущность изобретения заключается в том, что вместо блока преобразования данных, осуществляющего линейные преобразования, используется блок сжатия данных, построенный на основе нелинейных операций, и тем самым позволяющим снизить информационную избыточность сообщения. Изобретение поясняется чертежами фиг. 1 - структурная схема устройства крипто-корректирующего преобразования двоичной информации фиг. 2 - структурная схема блока сжатия данных фиг. 3 - структурная схема блока помехоустойчивого кодирования фиг. 4 - структурная схема генератора ПСП фиг. 5 - структурная схема блока помехоустойчивого декодирования фиг. 6 - структурная схема блока развертывания фиг. 7 - пример построения дерева кодирования фиг. 8 - диаграмма состояний декодера Витерби. На фиг. 1 представлена структурная схема устройства крипто-корректирующего преобразования двоичной информации. Устройство (фиг. 1) содержит источник данных 1, выходами 2 подключенный к первому регистру данных 3, выходом 4 подключенный к входу блока 5 сжатия информации,выход которого 6 подключен к входу блока 7 помехоустойчивого кодирования. Устройство также содержит первый сумматор 8 по модулю два, первый вход которого соединен с выходом 9 блока кодирования 7, а второй вход сумматора 8 - с выходом 10 генератора ПСП 11, первый источник ключа 12, выходами 13 соединенный с первым регистром ключа 14, инициализирующим через выходы 15 первый генератор ПСП 11 по заданному алгоритму. Закодированные на передающей стороне данные 16 поступают в каналы связи и,поврежденные (чаще всего) шумом, поступают на первый вход 17 второго сумматора по модулю два 18 на приемной стороне, выходом 19 соединенный с блоком помехоустойчивого декодирования 20, сигнал с выхода 21 которого поступает на вход блока развертыва 3 4997 1 ния 22, выходом 23 соединенного со вторым регистром данных 24, коммутирующим по выходам 25 приемник данных 26. Приемная сторона содержит также второй источник ключа 27, выходами 28 соединенный со вторым регистром ключа 29, инициализирующим по входам 30 второй генератор 31 ПСП, выходом 32 связанный со вторым сумматором по модулю два 18. Блок сжатия данных 5 может функционировать по любому из фундаментальных алгоритмов сжатия данных (арифметические или префиксные коды, коды Хаффмана, Шеннона-Фано, словарные алгоритмы, РСМ и т.д.). В предлагаемой реализации блок сжатия данных 5 построен по схеме на основе кода Хаффмана переменной длины с множественными статичными таблицами (фиг. 2). Ключевая идея кодирования кодами переменной длины Хаффмана состоит в использовании более коротких кодовых слов для наиболее часто встречающихся символов, что позволяет сжимать текст в общем на 30 -706. В частности, он содержитнакапливающих сумматоров символов 33, подсчитывающих частоту встречаемости каждого символа в тексте. Данные с сумматоров 34 поступают в компаратор 35 для определения (формируется на выходе 36) наиболее подходящей кодовой таблицы Хаффмана, заранее построенной и хранимой вблоках 37 кодовых таблиц Хаффмана. Сигнал 36 с компаратора 35, поступающий в блок кодирования 38, активизирует по шине 39 одну из таблиц кодирования 37, которая, в свою очередь, используется блоком кодирования 38 вместе с исходными данными 4. Номер используемой таблицы,необходимый для развертывания (декомпрессии, распознавания), по выходу 40 подается на выход 6 до начала поступления бинарного кода 6. Блок помехоустойчивого кодирования 7 может быть реализован на основе сверточных кодов. На фиг. 3 для примера приведена схема блока 7 на основе сверточного кода (9,6),исправляющего одиночные ошибки с порождающей матрицей, представленной в виде многочленов 7 542. Блок 7 содержит последовательно-параллельный регистр 41 размером 2 бита с выходами 42 и 43, первый 44 и второй 45 регистры сдвига размера 2 бита, три сумматора по модулю два 46, 47, 48 и параллельно-последовательный регистр 49 на 3 бита с входами 50,51 и 52. Принцип функционирования блока 7 известен 7. Параллельно с процессом помехоустойчивого кодирования формируется псевдослучайная последовательность бит генератором 11. Пример построения генератора ПСП 11 показан на фиг. 4. Он строится на основе комбинации двух известных техник формирования ПСП А- схеме Геффе, при которой используются линейные сдвиговые регистры с обратной связью с разными периодами характеристических полиномов и В - алгоритма сотовой системы связи А 5 8. Генератор А состоит из трех линейных регистров сдвига 53,54, 55, трех сумматоров 56, 57 и 58 по модулю 2 соответственно в цепи обратной связи и мультиплексора 59. Выход 60 регистра 55 используется для выбора одного из выходов 61 или 62 двух других регистров 54 и 53. Сдвиговые регистры функционируют на основе характеристических полиномов последовательностей максимальной длины, имеющих вид для 53, 54, 55 соответственно 1 х 2798,1 х 78 х 27, 2192140. Генератор В - также построен на трех линейных регистрах сдвига 63, 64, 65, трех сумматорах 66, 67 и 68 по модулю 2 соответственно в цепи обратной связи, трех элементах НЕ 69, 70, 71 и трех элементах И 72, 73 и 74. Сдвиговые регистры функционируют на основе характеристических полиномов, имеющих вид для 63,64, 65 соответственно 2121621,26816,251122. 4 4997 1 Сдвиговые регистры 53, 54, 55, 63, 64 и 65 инициализируются последовательно ключом из первого регистра ключа 14 (фиг. 1). Выходные сигналы генераторов А -75 и В -76 суммируются в блоке 77 суммирования по модулю, в результате чего формируется результирующий сигнал 10, подаваемый на вход блока 8. На приемной стороне второй генератор 31 ПСП выполнен аналогично генератору 11 на передающей стороне и инициализируется тем же ключом, который поступает из второго источника ключа 27 через второй регистр ключа 29. Блок помехоустойчивого декодирования может быть реализован на основе последовательного или синдромного декодирования, либо по схеме Витерби. Так как в выбранном коде (9,6) длина кодового ограничителя 4, то можно применить полный алгоритм декодирования Витерби с фиксированным временем декодирования 7. Блок 20 помехоустойчивого декодирования (фиг. 5) состоит из последовательно-параллельного регистра 78 размера 3 бита, вычислителя метрики ветвей 79, блока 80 изменения состояния, блока принятия решения 81 и параллельно-последовательного регистра 82 размера 2 бита 7(принцип функционирования блока рассмотрен ниже на конкретном примере). Декодированные данные 21 с исправленными ошибками подаются на вход блока развертывания 22. Блок развертывания 22 (фиг. 6) хранитстатичных таблиц кодирования Хаффмана 83 идентичных таблицам 37 (фиг. 2). Блок 22 состоит также из блока выбора таблицы 84, на который подается сигнал 85 с приемника о номере использованной при кодировании таблицы и непосредственно декодера 86 с поступающим на него бинарным кодом 21 и выходом 23. Отметим, что во всех описанных схемах (фиг. 1-6) сигналы синхронизации не показаны. Если ввести следующие обозначения- исходные данные, К - ключ, - порождающая матрица помехоустойчивого кода,- функция сжатия данных,- функция формирования псевдослучайной последовательности, а- закодированная последовательность данных, то процесс прямого крипто-корректирующего преобразования можно записать такН(К),гдеЕ. Тогда процесс обратного преобразования может быть представлен следующим образом,где, а- канальный шум, - функция помехоустойчивого декодирования, - функция развертывания. Рассмотрим на примере процесс функционирования предлагаемого устройства. Пусть задан ключ размером 256 бит,или в 71 65 67 70 77 75 50 66 44 74 4 45 54 76 77 65 51 58 45 77 45 4 Е 4 4 А 4 В 57 41 5 А 53 4 Е 4 71 74. Передается сообщение ЕХАМРТЕХТ (из источника сообщения 1). В блоках 33 схемы сжатия 5 считается частота каждого символа текста (табл. 1) и в 35 выбирается оптимальная таблица кодирования. Допустим, что выбрана вторая таблица 37,построенная на основе дерева кодирования (фиг. 7), в котором узлы с наименьшей частотой объединяются в новый узел с частотой равной сумме исходных. Кодирование начинается с корня. Если обход идет по правой ветви, то ставится 1, если по левой, то 0. Согласно этому правилу кодирования, исходный текст кодируется 30-ю битами и принимает вид 000100110011110010100110001011. Таким образом, текст сжимается на 52,5 по сравнению с представлением его в двоичном коде(80 бит - ви 830 бит в сжатом виде). На выход 6 блока 5 будет 5 4997 1 передаваться сначала номер используемой таблицы кодирования 40, а затем текст сообщения (в данном случае это 30 бит). Закодированный тест поступает на блок помехоустойчивого кодирования 7. Согласно алгоритму его работы (фиг. 3), получаем закодированный текст с избыточными разрядами (табл. 2), всего 45 бит (для упрощения номер выбранной таблицы не указывается) 000101000101011100110010001011100011001011111. Формирование псевдослучайной последовательности происходит согласно схеме,представленной на фиг. 4. Значения сигналов на выходах 75, 76, 10, 9 и 16 представлены в табл. 3. Предположим, что в процессе передачи данных возникли 3 одиночные ошибки в 6 ом, 15-ом и 36-ом разрядах (ошибочные символы подчеркнуты, а в табл. 3 обозначены ) 111000000110101010001000101110110100001110101. Тогда в приемнике после суммирования входных данных 17 по модулю два с псевдослучайной последовательностью получаем данные 19 (см. табл. 3), которые поступают на блок помехоустойчивого декодирования 20. Декодирование строится по алгоритму Витерби. Решетка декодирования или диаграмма состояний декодера (фиг. 8) построена и функционирует на основе таблицы состояний (табл. 4) и таблицы выходов (табл. 5) помехоустойчивого кодера 7. Декодирование начинается с нулевого состояния (0), по 3-ем битам принятой последовательности 19 - 000 определяется наиболее правдоподобный путь к каждому из возможных узлов (состояний). Переход из 0-ого состояния в 4-ое возможен при входном кадре 101, из 0-ого в 0-ое при 000, из 0-ого в 8-ое при 010 и из 0-ого в 12-ое при 111 (на фиг. 8 обозначены линиями со стрелками). Определяется расстояние между каждым из возможных путей и принятым кадром, которое в дальнейшем будем называть мерой расходимости 7. В первом такте (0) наименьшая мера расходимости, равная нулю, будет при переходе из 0 ого в 0-ое состояние. По табл. 5 определяются выходные биты 00. Во втором такте (1) аналогично выбирается наиболее правдоподобный путь. Это переходы из 0-ого в 8-ое и из 0-ого в 11-ое состояния, что соответствует входным 010 и 111 и выходным 01 и 11 кадрам. Мера расходимости в обоих случаях равна единице. Для разрешения неопределенности необходимо продолжить оба этих пути. На третьем такте (2) при входном кадре 001 наиболее правдоподобными являются переходы из 8-ого во 2-ое состояние (мера расходимости равна нулю), и из 12-ого во 2-ое (мера расходимости также равна нулю). Для устранения неопределенности выбирается путь из 8-ого состояния во 2-ое. Аналогично идет процесс декодирования в оставшихся кадрах. Для разрешения неопределенности в пятом такте (4) все пути с наименьшей мерой расходимости продолжаются до восьмого такта(7), где продолжение двух менее правдоподобных путей не имеет смысла. На фиг. 8 жирной линией обозначен кратчайший путь к следующему узлу решетки декодера (или путь декодирования) двойной пунктирной - пути к узлам решетки, относительно которых существует неопределенность, и тонкой со стрелкой - все возможные пути из текущего узла. После исправления ошибок (фиг. 8) получаем последовательность 00 010 0110 0111 100 101 00 11 00 010 11,которая поступает на блок развертывания 22. Декодирование начинается с вершины(см. фиг. 7) первый бит равен 0, следовательно обход идет по левой ветви и в стек блока 86 заносится второй бит - 0, снова выбирается левая ветвь и достигается лист дерева Е. Аналогично двигаясь по пути 010, достигается символи т.д., пока весь текст не будет восстановлен. После развертывания получаем текст , что соответствует передаваемой последовательности. Таким образом, предлагаемое устройство потокового крипто-корректирующего преобразования информации выполняет те же функции, что и известное. Однако преимущество предлагаемого устройства состоит в увеличении фактической пропускной способности устройства преобразования и в более эффективном использовании каналов связи (или устройств хранения информации). Действительно сжатие исходных данных на 20 100 и более (в приведенном примере исходная последовательность в 80 бит сжимается на 52,5 ) позволяет использовать в данном устройстве помехоустойчивые коды с раз 9 4997 1 личной корректирующей способностью и соответственно увеличивать избыточность сжатых данных для исправления возникающих ошибок практически без увеличения размера исходной последовательности, что невозможно в известном устройстве 5 без увеличения размера передаваемого сообщения. Источники информации 1. Патент США 5574785, МПК 04 9/00, 1996. 2. Патент США 4639548, МПК 04 9/00, 1987. 3. Патент США 5073932, МПК Н 04 К 1/00, Н 04 М 1/00, 1990. 4. Патент США 5504818, МПК 04 9/00, 1996. 5. Патент США 4208739, МПК 04 9/00, 1980. 6. Патент США 5528628, МПК Н 04 В 1/66, Н 04 В 14/04,04 11/02, 1996. 7. Блейхут Р. Теория и практика кодов, контролирующих ошибки. - М. Мир, 1986. С. 480. 8.., -, 1998,//2 . //041101 Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20.