Содержание к диссертации
Введение
1. Обзор методов защиты речевой информации 15
1.1. Методы защиты аналоговых речевых сообщений 15
1.2. Методы защиты цифровых сообщений 23
1.2.1. Перестановки 23
1.2.2. Подстановки 24
1.2.3. Гаммирование 25
1.3. Влияние энтропии и избыточности на стойкость шифров 27
1.4. Критерии оценки криптографических алгоритмов 31
1.5. Итеративные блочные шифры 38
1.6. Постановка задачи исследования 43
1.7. Выводы 45
2. Сжатие речевых сигналов на основе оптимизированных дельта-преобразований второго порядка 47
2.1. Об оптимизированных дельта-преобразованиях второго порядка и сжатии информации 47
2.2. Алгоритм двоичного дельта-преобразования со сглаживанием 48
2.3. Использование Д-преобразований для решения задачи компрессии речевых сигналов 52
2.4. Статистические свойства Д-последовательностей и длина сообщений 55
2.5. Инвертирование бита. 60
2.6. Свойства Д-последовательностей и использование 63
криптографических операций для защиты Д-последовательностей 63
2.7. Выводы 68
3. Разработка алгоритма защиты последовательностей с использованием модификации алгоритма Rijndael на основе параметризации (алгоритм А1) 71
3.1. Обоснование выбора алгоритма 71
3.2. Математическая основа алгоритма Rijndael 72
3.3. Описание алгоритма 75
3.4. Разработка схемы управления ключами 81
3.5. Оценка влияния схемы параметризации на стойкость алгоритма 87
3.6. Описание программной модели алгоритма А1 89
3.7. Выводы 91
4. Алгоритм защиты речевых сообщений на основе оптимизированных Д-преобразований второго порядка (алгоритм А2) 93
4.1. Обоснование выбора используемых операций 93
4.2. Описание алгоритма 94
4.3. Обоснование выбора минимальной длины ключа 98
4.4. Оценка стойкости разработанного алгоритма защиты 100
4.5. Описание программной модели алгоритма А2 105
4.6. Выводы 108
5. Исследования характеристик разработанных алгоритмов криптографической защиты речевых сигналов на основе дельта-преобразований второго порядка 110
5.1. Методика и критерии оценки разработанных алгоритмов защиты речевых сигналов 110
5.2. Экспериментальное исследование свойств Д-последовательности 111
5.3. Экспериментальное исследование характеристик генератора УСП 114
5.4. Исследование параметров образующего полинома для преобразования Подстановка Байт и множителя используемого генератора УСП 118
5.5. Оценка быстродействия разработанных алгоритмов по сравнению с существующими блочными шифрами 121
5.6. Выводы 129
Заключение 131
Литература 134
Приложение 1 147
Приложение 2 157
Приложение 3 178
- Методы защиты аналоговых речевых сообщений
- Статистические свойства Д-последовательностей и длина сообщений
- Описание алгоритма
- Оценка быстродействия разработанных алгоритмов по сравнению с существующими блочными шифрами
Методы защиты аналоговых речевых сообщений
Исторически все методы защиты аналоговых речевых сообщений объединяются одним термином скремблирование, под которым понимается перемешивающее преобразование сигнала. Аналоговые сигналы (речевые, биомедицинские, видео- и телевизионные) являются непрерывными и характеризуются своим спектром (эквивалентным сигналу набором синусоидальных составляющих (гармоник)). Поэтому одним из методов скремблирования являются преобразования речевого сигнала в частотной области: инверсия спектра и частотная перестановка. Наибольшее распространение получил метод коммутируемой инверсии по закону ключа, который состоит в использовании циклической инверсии с изменением несущей частоты сигнала и переносом части спектра. Основными недостатками такого метода являются небольшое число возможных несущих частот, в силу чего исходный сигнал может быть быстро восстановлен их перебором и неприемлемо высокая остаточная разборчивость выходного сигнала (субъективная характеристика, связанная с индивидуальными особенностями слухового восприятия человека). Третий способ изменения сигнала в частотной области состоит в делении спектра сигнала на N равных поддиапазонов, которые могут переставляться местами друг с другом и инвертироваться. Поскольку имеется N! возможных перестановок и 2N вариантов инверсий, общее число вариантов преобразования сигнала составит N! 2 . Несмотря на большое количество вариантов перебора, именно небольшое число поддиапазонов является ограничением данного метода, поскольку введение большого числа поддиапазонов связано с практическими трудностями и с искажением сигнала. Кроме того, обычно более 40% энергии сигнала (для речевых сигналов) сосредоточено в первых двух поддиапазонах, соответствующих первой форманте, что существенно ослабляет стойкость метода, поскольку необходимо найти правильные позиции первых двух поддиапазонов и переместить их на нужные места.
Скремблеры с временными перестановками делят аналоговый сигнал на равные промежутки времени, называемые кадрами, каждый из которых делится на фрагменты. Преобразование сигнала осуществляется перестановкой сегментов внутри каждого кадра и перестановкой кадров сообщения. Важным фактором является обоснованный выбор длин кадров и сегментов, т.к. внутри сегмента сигнал не разрушается, то сегменты необходимо выбирать настолько короткими, чтобы в них не содержались целые фрагменты сообщения (единицы слитной речи). С другой стороны, длина сегмента серьезно влияет на качество звучания передаваемого сигнала, что объясняется чисто техническими причинами (чем меньше сегмент, тем ниже качество звучания) [39]. Помимо выбора длин кадров и сегментов важным параметром является сама перестановка, так как одни перестановки лучше других (с точки зрения остаточной разборчивости), и необходим критерий отбора "хороших" перестановок. Для решения проблемы выбора «хороших» перестановок обычно используется экспертная оценка остаточной разборчивости, поскольку формализовать критерий отбора «хороших» перестановок достаточно сложно [33, 39]. Случайная перестановка, которая с формальной точки зрения является достаточно «хорошей» (обеспечивать высокое перемешивание) может иметь высокую разборчивость, что связано со способностями человеческого мозга при прослушивании скремблированного сигнала с парой соседних сегментов і, і+2 восстанавливать пропущенный сегмент і+1.
Наиболее высокую стойкость имеют композиционные скремблеры, принцип построения которых состоит в совместном использовании коммутируемой инверсии, частотного и временного перемешивания в одной системе, однако такие системы также поддаются анализу.
Отдельно стоящим методом защиты аналоговых сигналов является использование аппаратных генераторов шума, когда сигнал с выхода генератора суммируется с защищаемым сигналом, а результат передается по каналу связи. Получатель сообщения должен обладать аналогичным генератором, чтобы восстановить сообщение. Основными недостатками данного метода являются необходимость жесткой синхронизации передающего и приемного генераторов, сложность построения самих генераторов и низкое качество восстановленного сигнала.
Следует отметить, что системы скремблирования поддаются анализу, поскольку они не учитывают информационные характеристики сообщения и в скремблированном сигнале сохраняется избыточность исходного сигнала, что особенно важно для речевых сообщений. Применение методов скремблирования для защиты речевых сигналов в цифровом виде не получило широкого распространения, поскольку используемые для защиты преобразования для цифровых сигналов являются достаточно трудоемкими, для эффективной реализации требуют аппаратной поддержки (сигнальные процессоры), характеризуются высокой остаточной разборчивостью и являются системами временной стойкости.
Указанные выше недостатки систем скремблирования с одной стороны и бурное развитие систем цифровой связи с другой привели к тому, что в настоящее время приоритет в области защиты речевых сообщений переходит к системам защиты дискретных сообщений.
Статистические свойства Д-последовательностей и длина сообщений
С позиций вероятности появления очередного символа ("0" или "1") рассмотрим распределение выходного потока кодера (Д-последовательности). Появление "1" или "0" в очередном бите сжатого потока является случайной величиной, поскольку определяется входным речевым сигналом, представляющим собой нестационарный случайный процесс [4]. Будем считать, что для Д-последовательности р0 « «-, тогда распределение получаемой последовательности дельта-бит (Д-бит) близко к равномерному и, соответственно, Д-последовательность характеризуется безызбыточностью. Оценим статистические свойства Д-последовательностей, исходя из допущения, что появление "О" и "1" равновероятно. Поскольку кванты модуляции принимают значения только из ограниченного множества {-1;+1} (или {0;1} - при практическом использовании алгоритмов компрессии), число символов данного алфавита равно 2. Для Д-последовательности. Можно оценить математическое ожидание величины X (где Х- появление «О» или «1» в очередном кванте модуляции)[26]:
Очевидно, закон распределения величины Xі будет совпадать с распределением X [26]:
Можно показать, что для такого распределения все начальные моменты порядка Л постоянны:
Для центральных моментов к-го порядка можно получить следующие численные оценки:
Энтропия алфавита Д-последовательности, характеризующая минимальное число бит, необходимое для передачи одного символа алфавита, составит: где o(N)- малая величина, характеризующая отклонение от равномерного распределения для сообщения длины N.
Избыточность языка RA для Д-последовательности вычисляется как:
Таким образом, избыточность языка, описывающего кванты модуляции, равна малой величине o(N). Избыточность языка криптограммы является важной характеристикой при проведении криптоанализа и обратно пропорциональна расстоянию единственности априорно неопределенного шифра L: Vl0g2W где К - ключ шифра, \К\ - мощность множества ключей.
Расстояние единственности характеризует число символов криптограммы, теоретически необходимых для однозначной дешифровки при неограниченных ресурсах криптоаналитика. Таким образом, избыточность алфавита и расстояние единственности оказывают влияние не на вычислительную стойкость шифра, а на множественность решений криптограммы. Если объем перехвата меньше расстояния единственности, то результатом дешифрования будет несколько равновероятных решений, для которых сложно сделать вывод, какое из них является истинным.
Для Д-преобразований расстояние единственности будет иметь вид: log, ДО 1оё9ДО RA-log2n o(IV) Применение компрессии сигнала на основе Д-преобразований позволяет увеличить расстояние единственности, поскольку для Д-бит RK является малой величиной, существенно меньшей, чем в случае кодирования информации с многоразрядными отсчетами. Согласно [69], для последовательностей такого языка использование простого алгоритма с небольшим ключом обеспечивает высокую стойкость. Поэтому использование компрессии на основе Д-преобразований, помимо уменьшения объема речевого сигнала, обеспечивает высокую базовую теоретическую стойкость (за счет приближения заданного на алфавите Д-последовательностей шифра к идеальному) и этим обуславливает возможность применения простых алгоритмов защиты.
Использование Д-преобразований для сжатия сигналов имеет существенное преимущество по сравнению с другими методами компрессии. Большинство существующих алгоритмов сжатия информации стремятся достичь минимальной длины выходной последовательности. Минимальная длина последовательности закодированных символов определяется из теоремы К. Шеннона о кодировании источника: минимальное двоичное кодовое слово для кодирования символа с вероятностью появления pt будет занимать log2 pt двоичных разрядов. Для безызбыточных источников, эта величина будет постоянна для всех символов алфавита и уменьшить ее нельзя, поскольку такой источник характеризуется равномерностью распределения. Большинству реальных источников присущи статистические зависимости и вероятности р. распределены неравномерно. Поэтому большинство методов компрессии стремятся достичь минимальной длины кодового слова в среднем по всем символам исходного алфавита, что достигается использованием в качестве базовой стратегии сжатия неравномерности распределения, поэтому для кодирования часто встречающихся символов используются более короткие кодовые слова, чем для редко встречающихся, за счет чего и осуществляется сжатие информации. Однако при этом не устраняются статистические характеристики исходных данных, поскольку для известной таблицы кодов (частот появления символов) при криптоанализе возможно построение модели открытого текста на основе кодовой таблицы. В этом смысле большинство существующих методов компрессии не устраняют частотные характеристики входного потока, а лишь осуществляют сжатие за счет использования переменного числа разрядов для кодирования разных символов алфавита. Сжатие в некоторых разностных алгоритмах (таких, как ДИКМ) достигается за счет меньшего числа разрядов, необходимых для хранения разности между отсчетами.
Отличием рассмотренного алгоритма оптимизированного Д-преобразования от других алгоритмов компрессии информации является стратегия сжатия с фиксированной длиной кодового слова (1 бит) для каждого символа входного потока. Поэтому Д-преобразование достаточно сильно устраняет статистическую избыточность, свойственную данным входного потока. Именно это свойство Д-последовательностей делает возможным, помимо очень большого расстояния единственности, применение простых алгоритмов для эффективной (и, соответственно, более быстродействующей) защиты речевых сообщений. Расстояние единственности характеризует число символов, на основании которых теоретически возможно предсказание допустимой (осмысленной) последовательности символов, описывающих выход источника. Для Д-преобразований эта величина существенно выше, чем для текстовой информации, что говорит о равномерности Д 60 последовательности и сложности построения эффективной модели критерия на открытый текст.
Для выявления статистических зависимостей и подтверждения равномерности распределения последовательностей используется статистическое тестирование. В частности, наиболее распространенным методом является частотный тест Аг-грамм, основанный на подсчете числа к-грамм алфавита для произвольного сообщения. Результаты экспериментальных исследований равномерности распределения Д-последовательности приведены в главе 5.
Описание алгоритма
По аналогии с общепринятой в области криптографической защиты терминологией введем определения основных элементов и понятий предлагаемого алгоритма. Блок - текущий результат преобразования, представляемый в виде линейного массива кадров сигнала. Длина блока составляет М кадров. Кадр -структура данных, содержащая блок начальных условий для одного из рассмотренных вариантов формирования начальных условий (С1 или С2) и последовательность Д-бит. Длина кадра составляет L бит, в которую входит длина блока начальных условий из S бит и длина Д-последовательности из N бит: L = S + N. Состояние - текущий результат преобразования блока. Заполнение состояния производится по порядку следования кадров исходного сигнала. После завершения преобразования выходные кадры получаются из состояния в том же порядке.
Исходя из рассмотрения свойств Д-последовательностей и применимости криптографических операций к ним, можно предложить следующий алгоритм защиты речевых сообщений на основе оптимизированных Д-преобразований.
Раундовое преобразование состоит из четырех различных преобразований, которые с использованием псевдокода можно описать следующим образом:
Раунд_Шифрования (Состояние, Раундовый ключ): Для i=l до М
Инверсия_Бит_Кадра (і, Раундовый ключ); Перестановка_Кадров (Состояние, Раундовый ключ); Для і=1 до М
Гаммирование (і, Раундовый ключ);
Подстановка_Байт_Кадра (і, Раундовый ключ (Модуль Р)); Раундовый ключ = Модификация (Раундовый ключ); Раундовый ключ содержит позиции изменяемых бит для всех кадров блока (вектор {FK}), линейный массив для перестановки кадров (вектор РК), параметры генератора ПСП GK и вектор, задающий подстановку SK.
Каждая из описанных операций реализует обратимое универсальное преобразование, называемое слоем, и раунд таким образом состоит из следующих слоев:
- Линейный слой, обеспечивающий увеличение диффузии входных данных (преобразование Перестановка_Кадров);
- Нелинейный слой, обеспечивающий нелинейность подстановки (Подстановка_Байт_Кадра);
- Слой гаммирования, состоящий из инверсии бит Д-последовательности (Инверсия_Бит_Кадра) и собственно наложения гаммы шифра, выработанной при помощи генератора ПСП.
Инверсия_Бит_Кадра представляет собой гаммирование Д-последовательности /-го кадра с i-u элементом вектора {FK}, \ І М .
Перестановка_Кадров реализует перестановку кадров сигнала внутри блока в соответствии с ключом перестановки РК .
Подстановка_Байт представляет собой нелинейную замену, независимую для каждого байта состояния. Таблицы замен построены на основе композиции двух преобразований:
1. Получение обратного элемента относительно умножения в поле GF(28) по модулю Р, где Р - неприводимый полином степени 8 в поле GF(2 )(т.е. простое число, меньшее 512 и большее 256). При этом нулевой и единичный элементы переходят сами в себя.
2. Применение аффинного преобразования, состоящего в умножении элемента на матрицу с последующим сложением с вектором, над GF(2 )[ 141 ]: S - A-x-vV, где х -мультипликативная инверсия элемента х, А - битовая матрица 8x8, V - константа (более подробно Уо Уі преобразование такого вида рассмотрено в разделе 3). Использование этого преобразования необходимо для устойчивости алгоритма к интерполяционным атакам, базирующимся на алгебраических свойствах конечных полей. В данной реализации по аналогии с разделом 3.3 было выбрано следующее преобразование [141]:
Гаммирование представляет собой наложение гаммы генератора ПСП на весь преобразуемый кадр (начальные условия, служебную информацию и Д-последовательность), что необходимо для повышения стойкости алгоритма. В качестве генератора ПСП предлагается использовать генератор УСП, описанный в 3.4.
Модификация необходима для выработки нового раундового ключа. После завершения обработки блока ключевые элементы кадров FKg циклически сдвигаются влево на cF байт, а ключ РК циклически сдвигается на ср байт вправо, что дает новый ключ для следующего шага алгоритма.
Как было показано в главе 1, необходимыми качествами для практического шифра являются перемешивание (для обеспечения статистической равномерности распределения открытого текста) и рассеивание (для максимального распространения изменений открытого текста в шифртексте), для чего используются криптографические операции перестановки (Р-блоки) и подстановки (S-блоки).
Операция подстановки выполняет роль рассеивателя, а перестановка кадров - перемешивания входных данных [32]. В данном случае, ключевой информацией алгоритма является вектор ключевых параметров Key = {{FK},{PKl{SK\cF,cB). Такая параметризация алгоритма необходима для внесения неопределенности в предлагаемый алгоритм и повышения стойкости.
В разработанном алгоритме для шифрования используется один раунд (состоящий из табличных подстановок, сдвигов и перестановок) небольшой трудоемкости, что позволяет говорить о возможности существенного повышения быстродействия по сравнению с известными алгоритмами, а рассмотренные свойства Д-последовательносгей позволяют говорить о высокой стойкости предлагаемого метода защиты речевой информации.
Оценка быстродействия разработанных алгоритмов по сравнению с существующими блочными шифрами
Важным параметром любого криптографического алгоритма, помимо стойкости, является его быстродействие, поэтому необходимо оценить быстродействие разработанных алгоритмов по сравнению с существующими итеративными блочными шифрами.
Для получения объективной оценки быстродействия необходимо использовать независимые от реализации характеристики алгоритмов шифрования, поскольку оценка быстродействия алгоритма в программной реализации сильно зависит от оптимизации программы и ориентации на работу с определенной архитектурой процессора, операционной системой, длиной блока и т.д. Для сравнительной оценки быстродействия разработанных алгоритмов предлагается использовать методику на основе подсчета количества некоторых элементарных операций, составляющих цикл криптографического преобразования (шифрование 1 блока открытого текста). В результате анализа итеративных блочных шифров (Приложение 2) в качестве элементарных операций для оценки быстродействия предлагается использовать следующие операции:
- гаммирование (XOR) - g;
- сложение - s;
- умножение -т;
- сдвиг - г;
- табличная подстановка (S-блоки алгоритмов) -1.
Состав используемых для оценки элементарных операций определяется наибольшей распространенностью в существующих блочных шифрах. Для битовой перестановки, встречающейся в некоторых шифрах, в качестве приближенной оценки предлагается использовать операцию сдвига по числу битов перестановки. Операции сложения и умножения выполняются по некоторому модулю, совпадающему с длиной разрядной сетки, необходимой для представления данных, которыми оперирует алгоритм: если алгоритм ориентирован на работу с 16-разрядными данными, то сложение и умножение производится по модулю 216, для 32-разрядных - по модулю 232 и т.д.
В качестве прототипов для сравнения были выбраны алгоритмы DES, NewDES, IDEA, BlowFish, ГОСТ и RC5 (Приложение 2), поскольку для этих алгоритмов известны характеристики стойкости и быстродействия и они являются наиболее исследованными симметричными блочными криптографическими алгоритмами.
Оценку быстродействия модификации алгоритма Rijndael на основе параметризации (алгоритм А1) целесообразно проводить с алгоритмом-прототипом Rijndael. Поскольку раунды криптографических преобразований алгоритмов А1 и Rijndael различаются лишь схемой управления ключей (для реализации параметризации А1 используются предвычисления), можно считать, что по временным затратам раунды этих алгоритмов примерно сопоставимы и увеличение быстродействия будет определяться сокращением числа раундов. Как указано в главе 3, для алгоритма А1 для достижения хороших характеристик перемешивания и рассеивания рекомендуется использовать не менее 4 раундов, а минимальное число раундов алгоритма Rijndael составляет 10 [141]. Таким образом, увеличение быстродействия алгоритма А1 по сравнению с Rijndael примерно составляет 2,5 раза.
Раунд алгоритма DES с учетом расширяющей и сжимающей табличных подстановок, сложения с ключом и битовой перестановки можно охарактеризовать как
Для получения сравнительных оценок по быстродействию в единых единицах, в качестве такой характеристики можно использовать число тактов процессора, необходимое для выполнения полного цикла криптографического преобразования. Однако необходимо отметить, что такая оценка является приближенной и не учитывает особенности программной реализации сравниваемых алгоритмов (оптимизации шагов алгоритма, организации структур данных и т.д.). Введенные в качестве элементарных операции характеризуются различной трудоемкостью и, соответственно, разным числом тактов процессора для выполнения в зависимости от типа процессора, размера операндов и их местонахождения. В качестве максимальных характеристик по трудоемкости операций целесообразно использовать следующие характеристики: операции g и s занимают « 1 такт, операция умножения т - от 13 до 42 тактов, операция сдвига г - от 1 до 5 тактов, табличная подстановка t (рассматриваемая как операция mov) - от 1 до 7 тактов (основой для таких характеристик служит время выполнения этих операций для процессора i486).
В соответствие с этим рассмотрим влияние каждой из этих операций на быстродействие рассмотренных шифров (рис. 5.1 - 5.3).
Как можно увидеть из табл. 5.8 и графиков 5.1-5.3, разработанные алгоритмы А1 и А2 благодаря сочетанию используемых операций 128 характеризуются довольно высоким быстродействием по сравнению с существующими аналогами. Согласно рассмотренным оценкам, повышение быстродействия по сравнению с рассмотренными блочными алгоритмами составляет от 2,5 до 5 раз, при этом разработанный алгоритм А2 примерно в 1,5 раза превосходит по быстродействию модифицированный алгоритм А1.
Однако необходимо отметить, что полученная теоретическая оценка является приближенной и не учитывает особенности программной реализации сравниваемых алгоритмов (оптимизации шагов алгоритма, организации структур данных, особенности архитектуры процессора и т.д.).
Для оценки быстродействия программной реализации алгоритмов проводились экспериментальные исследования алгоритмов А1 и А2 по сравнению с оптимизированными реализациями существующих алгоритмов в библиотеке Crypto++[104]. Для тестирования быстродействия алгоритмов использовался компьютер с процессором Celeron 850 под управлением ОС Windows 2000. Результаты исследования приведены в табл. 5.9 (при этом для результатов тестирования можно принять г=4, t=4, m=26).
Как можно увидеть из табл. 5.9, алгоритмы А1 и А2 характеризуются довольно высоким быстродействием. При проведении экспериментальных 129 исследований быстродействия алгоритмов А1 и А2 использовалась неоптимизированная реализация алгоритмов, чем и объясняется более низкое по сравнению с ожидаемым преимущество по сравнению с существующими шифрами. Поэтому, с учетом возможной оптимизации программной реализации алгоритмов А1 и А2, можно говорить о существенном повышении быстродействия разработанных алгоритмов по сравнению с рассмотренными блочными шифрами.
Таким образом, разработанные методы характеризуются достаточно высокими показателями по быстродействию по сравнению с существующими алгоритмами, что позволяет говорить о целесообразности и перспективности их использования для защиты речевой информации.
