Содержание к диссертации
Введение
1. Методы эффективного кодирования для повышения рассто яния единственности шифров 23
1.1. Введение 23
1.2. Теория систем с совершенной секретностью 29
1.3. Соотношение избыточностей по входу и выходу . 40
1.4. Основные подходы к потроєнню метода эффективного кодирования 44
1.4.1. Быстрое кодирование с использованием скользящего окна 47
1.4.2. Использование мнимого скользящего окна для уменьшения объема памяти кодера и декодера 56
1.4.3. Кодирование марковских источников 61
1.4.4. Избыточность арифметического кодирования 62
Выводы 68
2. Омофонное кодирование 70
2.1. Обзор побуквенных омофонных кодов 70
2.2. Арифметическое кодирование с разделением интервала 76
2.2.1. Основная идея метода 77
2.2.2. Описание алгоритма кодирования 81
2.2.3. Свойства метода 91
2.3. Арифметическое кодирование с фиктивным символом 96
2.3.1. Описание алгоритма 98
2.3.2. Оценка избыточности по входу 100
Оглавление З
2.3.3. Потребление внешних случайных бит 103
2.3.4. Вычислительная сложность метода 104
Выводы 105
3. Выделение случайности и генерация случайных величин 107
3.1. Задачи, возникающие при использовании физических генераторов случайных чисел 108
3.2. Эффективная нумерация множеств 113
3.2.1. Постановка задачи 113
3.2.2. Нумерация сочетаний 119
3.2.3. Быстрый алгоритм нумерации сочетаний 126
3.3. Эффективная генерация произвольно распределенных случайных величин 136
3.3.1. Постановка задачи 136
3.3.2. Быстрая генерация случайных величин для омофонных кодеров 138
3.3.3. Генерация случайных величин на основе омофонного декодирования 142
3.3.4. Уменьшение числа случайных бит, используемых в омо-фонном кодировании 144
3.3.5. Эффективное преобразование вероятностностных распределений 146
Выводы 151
4. Строго идеальные криптосистемы 154
4.1. Основные определения и постановка задачи 154
4.2. Конструкция идеальной криптосистемы на базе нумерационного кода 156
4.2.1. Основная идея и свойства метода 156
4.2.2. Описание общего алгоритма и его свойства 163
Оглавление 4
4.3. Построение строго идеальной системы на базе универсального омофонного кода 170
4.3.1. Введение 170
4.3.2. Основная идея 173
4.3.3. Общая конструкция строго идеальной системы 178
Выводы 180
5. Статистические тесты и атака на блоковые шифры 181
5.1. Тесты для проверки генераторов случайных и псевдослучайных чисел 182
5.1.1. Тест «Стопка книг» 183
5.1.2. Порядковый тест 186
5.1.3. Экспериментальные исследования 187
5.2. Статистическая атака на блоковые шифры 190
Выводы 204
Основные заключения и выводы 205
Список литературы
- Соотношение избыточностей по входу и выходу
- Арифметическое кодирование с разделением интервала
- Эффективная генерация произвольно распределенных случайных величин
- Конструкция идеальной криптосистемы на базе нумерационного кода
Введение к работе
Актуальность проблемы Одной из важных областей исследований в системах, сетях и устройствах телекоммуникаций является исследование и разработка новых методов защиты информации и обеспечение информационной безопасности этих систем, сетей и устройств. В свою очередь, защита информации в значительной степени базируется на использовании криптографических методов, связанных с шифрованием данных. Наибольшее практическое применение для шифрования информации в настоящее время находят симметричные системы, построенные на основе блоковых или потоковых шифров с секретным ключом. В этих системах абоненты взаимодействуют по открытым каналам связи, доступным некоторому противнику. Каждая пара абонентов имеет общий секретный ключ, который используется для шифрования передаваемых данных. Предполагается, что секретные ключи передаются по закрытому (или защищенному) каналу, имеющему значительно меньшую пропускную способность по сравнению с открытым каналом. В зависимости от использованных методов построения эти системы можно разделить на два больших класса: вычислительно стойкие системы и безусловно стойкие системы. Разница между этими классами проявляется при рассмотрении атаки по шифротексту, когда криптоаналитик (противник) имеет перехваченный шифротекст (криптограмму) и пытается восстановить сообщение и использованный секретный ключ.
Большинство из практически используемых в настоящее время криптосистем обладают лишь вычислительной стойкостью. Это означает, например, что шифры могут в принципе быть взломаны путем полного перебора ключей. Но что более важно отметить, пока никому не удалось найти каких-либо строгих доказательств того, что для тех или иных вычислительно стойких си-
Введение 6
стем не существует более эффективных алгоритмов взлома, чем перебор ключей. Более того, история криптоанализа свидетельствует о том, что для многих систем, казавшихся надежными, со временем такие более эффективные алгоритмы взлома находятся, а некоторые системы в результате оказываются настолько нестойкими, что выходят из практического использования. Основная проблема здесь состоит в том, что при отсутствии математически строгих доказательств стойкости никто не может быть уверен, что противник уже сегодня не располагает эффективными методами, направленными против используемых криптосистем. Если говорить о перспективах применения вычислительно стойких систем, то следует также отметить, что большую угрозу для таких систем представляют квантовые компьютеры. Сегодня квантовые компьютеры изучаются в основном на уровне математических моделей, хотя имеются сведения о первых практических реализациях с ограниченными вычислительными возможностями (скажем, реализующие 7-битовые квантовые алгоритмы). В многочисленных работах по квантовым компьютерам показано, что с их помощью многие криптоаналитические задачи, практически нерешаемые в традиционных вычислительных системах, могут быть быстро решены. Таким образом, если сегодня вычислительно стойкие системы в целом удовлетворительно решают возлагаемые на них задачи по защите информации, то ситуация может резко измениться в ближайшем будущем, если квантовые компьютеры станут реальностью или будут открыты новые эффективные методы криптоанализа.
В противоположность вычислительно стойким системам, безусловно стойкие системы гарантируют невозможность вскрытия шифров (при соблюдении некоторых условий, связанных с их корректным применением), независимо от вычислительных возможностей криптоаналитика. Это свойство делает весьма актуальной задачу эффективных методов построения таких систем. Основы теории стойкости криптосистем были заложены в работе К. Шеннона [20]. Отметим здесь три основные понятия, введенные Шенноном: совершен-
Введение 7
ная криптосистема, расстояние единственности шифра и идеальная криптосистема. Формальные определения этих понятий будут даны в соответствующих главах, а здесь ограничимся их неформальным рассмотрением, которое позволит судить о стоящих перед нами задачах. Совершенная криптосистема предполагает, что независимо от объема перехваченного шифротекста противник не получает никакой информации о сообщении. Примером совершенной системы является шифр Вернама. В этом шифре длина секретного ключа равна длине сообщения и ключ используется только один раз. Можно сказать, что шифр Вернама применим в системах, где пропускная способность открытого и закрытого каналов одинакова. Однако, на практике, как указывалось выше, пропускная способность закрытого канала часто много меньше пропускной способности открытого канала. В таких случаях секретные ключи намного короче передаваемых сообщений и существует некоторая «критическая» длина шифротекста, названная расстоянием единственности шифра, при которой криптоаналитик может определить ключ почти однозначно. Шеннон показал, что расстояние единственности пропорционально длине ключа и обратно пропорционально избыточности сообщения. Ключ может обновляться (или порождаться) с некоторой скоростью, определяемой пропускной способностью закрытого канала. Если ключ обновляется быстрее, чем достигается расстояние единственности, то криптоаналитик не может получить единственного решения криптограммы, т.е. не может вскрыть шифр. Такую систему Шеннон назвал идеальной. Если избыточность сообщения удается сделать равной нулю, то расстояние единственности становится бесконечным и мы получаем строго идеальную криптосистему. В строго идеальной криптосистеме криптоаналитик всегда получает множество допустимых решений криптограммы соответствующее множеству возможных ключей. Подчеркнем, что в случае когда расстояние единственности больше длины сообщения или криптосистема строго идеальна, шифр оказывается невскрываемым.
Введение 8
Основным способом построения невскрываемых шифров при использовании коротких ключей является кодирование сообщений перед шифрованием. Можно выделить два основных подхода к такому кодированию. Первый заключается в применении традиционного сжатия данных для уменьшения избыточности сообщения и, следовательно, увеличения расстояния единственности шифра. Особенностью этого подхода является то, что он может быть распространен на большое множество моделей источников информации. При этом следует иметь в виду, что в методах кодирования избыточность традиционно определяется как разность между средней длиной кодового слова и энтропией на символ источника (мы называем эту разность избыточностью по входу). Однако для оценки расстояния единственности шифра необходима другая величина, определяемая для двоичного кода как величина отклонения средней энтропии одного кодового символа от единицы (т.е. ее максимально возможного значения). Мы называем эту величину избыточностью по выходу. Как правило, применяемые методы сжатия должны быть характеризованы не эвристическими или экспериментальными, а теоретически доказанными показателями избыточности, чтобы гарантировать определенную величину расстояния единственности. Естественная постановка задачи разработки алгоритмов сжатия сводится к минимизации сложности кодера и декодера при достижении заданной произвольно малой избыточности на символ сообщения.
Второй основной подход состоит в построении специальных кодов или, точнее, преобразований сообщений перед шифрованием. В рамках этого подхода может ставиться задача достижения бесконечного расстояния единственности шифра или, другими словами, построения строго идеальных криптосистем. Получаемые коды не обязательно должны «сжимать» сообщение, как раз наоборот, такие коды часто могут быть построены при условии «растяжения» сообщения методами рандомизации. Реализация этого подхода, предлагаемая в настоящей работе, основана на методах нумерационного и омо-
Введение 9
фонного кодирования. Получаемый код состоит из нескольких отделимых компонент, одна из которых неотличима от последовательности случайных и независимых символов. Именно эта компонента кода подлежит шифрованию, в то время как другие компоненты могут передаваться в открытом виде. Говоря неформально, в отличие от схемы со сжатием данных, здесь шифруется не весь код, а отдельные его части, имеющие наибольшую «степень случайности». Данный подход более эффективен, чем первый, с точки зрения свойств получаемой криптосистемы. Однако специальные методы кодирования могут быть не столь эффективны с вычислительной точки зрения при сложных моделях источников.
Решение задач построения безусловно стойких криптосистем в рамках двух указанных основных подходов тесно связано со многими задачами в других разделах криптографии, теории кодирования источников и теории информации в целом. Так, например, эффективные конструкции, разработанные для методов сжатия данных, с успехом применяются при построении специальных кодов на основе нумерационного и омофонного кодирования. В свою очередь, омофонное и нумерационное кодирование тесно связано с задачей генерации случайных величин и выделения случайности. Необходимость проверки качества получаемых кодов требует рассмотрения задач статистического тестирования случайных последовательностей. Вообще, решение основной поставленной задачи (построение идеальных систем) привело к необходимости или сделало возможным решение многих смежных задач, что и отражено в представленной работе.
Проблемы криптографии привлекают внимание многих исследователей. Начало научного изучения предмета было положено в работах К. Шеннона (Shannon, С.) в конце 40-х годов XX века, но наиболее активные (открытые) исследования начались в 70-х годах после выхода в свет работ У. Диффи (Dime, W.), Р. Меркля (Mercle, R.) и М. Хеллмана (Hellman, М.), а также Л. Адлемана (Adleman, L.), Т. Эль-Гамаля (ElGamal, Т.), Р. Ривеста
Введение
(Rivest, R.), А. Шамира (Shamir, А.) и многих других. Значительный вклад в развитие современной криптографии внесли (открытые) работы Э.М. Габи-дулина, Б.Я. Рябко, В.М. Сидельникова и целого ряда других отечественных ученых. Вопросы безусловной стойкости криптосистем были впервые рассмотрены К. Шенноном и затем, спустя несколько десятилетий, изучались в работах Р. Альсведе (Ahlswede, R.), Дж.Л. Месси (Massey, J.L.), Б.Я. Рябко, Ю.М. Штарькова и др. Омофонными кодами занимались такие исследователи как К. Гюнтер (Giinther, Ch.), К. Гирман (Gehrmann, Ch.), Дж.Л. Месси, В. Пенцхорн (Penzhorn, W.), В.К. да Рока (da Rocha, V.C.), Б.Я. Рябко и др. Задача извлечения случайности и генерации случайных величин изучалась в многочисленных работах, среди которых отметим работы Дж. Абрахаме (Abrahams, J.), П. Элайеса (Elias, Р.), Д. Кнута и А. Яо (Knuth, D., Yao, А.), Н. Нисана и Д. Цуккермана (Nisan, N., Zuckerman, D.), Ж.Р. Роше (Roche, J.R.), Б.Я. Рябко и Е.П. Мачикиной, Т.С. Хана и М. Хоши (Han, T.S., Hoshi, М.). Подходы, применяемые для решения поставленных задач, связаны с общей теорией кодирования, изучаемой в работах таких авторов как Э. Бер-лекэмп (Berlekamp, Е.), Э.М. Габидулин, Р. Галлагер (Gallager, R.), А.Г. Дьячков, К.Ш. Зигангиров, Д. Костелло (Costello, D.), Дж. Месси, М.С. Пинскер и многих других. Многочисленные работы посвящены методам универсального, нумерационного и адаптивного кодирования источников. Основные результаты в этой области принадлежат как отечественным исследователям В.Ф. Бабкину, Р.Е. Кричевскому, Б.Я. Рябко, В.К. Трофимову, Б.М. Фитин-гофу, Ю.М. Штарькову, так и зарубежным исследователям Я. Зиву (Ziv, J.), Т. Коверу (Cover, Т.), Дж. Лэнгдону (Langdon, G.), А. Лемпелу (Lempel, А.), А. Моффату (Moffat, А.), Й. Риссанену (Rissanen, J.), П. Элайесу и др.
В качестве основного критерия, по которому можно сравнивать различные методы построения теоретически стойких систем и связанных с ними алгоритмов, может выступать сложность реализации, рассматриваемая как функция некоторого целевого параметра. Для идеальных систем целевым па-
Введение 11
раметром может служить расстояние единственности шифра или тесно связанная с ним избыточность кода. Для строго идеальных систем это может быть размер обрабатываемого блока или сообщения. Для методов выделения случайности и генерации случайных величин — количество расходуемых символов входной последовательности. Сложность измеряется количеством битовых операций, которые необходимо выполнять для достижения заданного значения целевого параметра (для краткости эта величина иногда называется временем работы или трудоемкостью алгоритма), и объемом памяти в битах, который требуется для выполнения алгоритма. Для удобства сравнения трудоемкостей они, как правило, приводятся в расчете на один символ.
Следует отметить, что до появления работ професора Б.Я. Рябко и автора настоящей диссертации известные конструкции строго идеальных криптосистем обладали экспоненциальной трудоемкостью (по длине сообщения), что делало их неприменимыми на практике. Оставались также проблемы сложности методов в области омофонного, нумерационного, адаптивного кодирования и в других смежных областях, ограничивающие их практическое применение, в частности, построение идеальных криптосистем.
Цель работы состоит в следующем:
Построение идеальных криптосистем на основе универсальных и адаптивных методов сжатия данных, обладающих на порядок более низкой сложностью, чем ранее известные, при обеспечении заданной произвольно низкой скорости порождения ключа.
Построение строго идеальных криптосистем на основе специальных методов преобразования сообщений, обладающих неэкспоненциальной трудоемкостью.
Разработка методов статистического тестирования для экспериментальной проверки качества полученных криптосистем, имеющих мощность существенно большую, чем ранее известные тесты.
Введение 12
Объектом исследований в предлагаемой работе являются криптосистемы, обладающие безусловной стойкостью. Предмет исследований состоит в поиске методов реализации безусловно стойких систем, на порядок более эффективных, чем ранее известные.
Состояние проблемы Известные конструкции строго идеальных криптосистем обладают экспоненциальной по длине сообщения трудоемкостью и, следовательно, практически не реализуемы. В то же время известно множество методов кодирования, из которых необходимо особо выделить омо-фонные и адаптивные коды, пригодных для построения идеальных систем за счет снижения расстояния единственности. Сложность предложенных другими авторами омофонных кодов, рассматриваемая как функция избыточности и числа используемых при кодировании случайных символов, растет экспоненциально, что затрудняет практическое применение этих кодов. Эффективных адаптивных кодов известно достаточно много, однако и здесь имеется резерв для снижения сложности при достижении заданной произвольно малой избыточности, прежде всего, за счет уменьшения порядка трудоемкости обработки больших алфавитов источников, а также за счет экономии памяти кодера и декодера при реализации адаптивных моделей. Кроме того, многие адаптивные коды характеризованы лишь эвристическими или экспериментальными оценками, в то время как для криптографических применений требуются строго доказанные теоретические оценки. Остановимся также на характеристике ряда задач, являющихся вспомогательными с точки зрения достижения поставленных целей. Известный метод Элайеса для выделения случайности обладал экспоненциальной сложностью, однако Рябко и Мачи-кина предложили эффективную реализацию этого метода для двоичных алфавитов источника. Наилучший метод генерации произвольно распределенных случайных величин (интервальный алгоритм Хана и Хоши) требует линейного роста памяти и примерно квадратичного роста времени при увеличении длины получаемой последовательности случайных величин. Такими же
Введение 13
характеристиками сложности обладает построенный на базе интервального алгоритма метод преобразования распределений случайных величин. Известные статистические тесты, например, рекомендованные для практического использования в системах защиты информации Национальным институтом стандартов и технологий США, для обнаружения отклонений от случайности в «почти» случайных последовательностях, получаемых на выходах низкоизбыточных кодеров, часто требуют объемов выборки значительно превосходящих ресурсы памяти компьютеров, что делает эти тесты неприменимыми. Задачи исследования Для достижения указанных целей с учетом изложенного состояния проблемы в рамках диссертационной работы решаются следующие задачи.
Определение влияния различных типов избыточности на стойкость криптосистем, включающих сжатие и рандомизацию сообщений.
Получение аналитической верхней оценки избыточности арифметического кода, как основного метода низкоизбыточного кодирования.
Построение алгоритма для выполнения операций с кумулятивными вероятностями в арифметическом кодере и декодере за менее чем линейное время при возрастающем размере алфавита источника и разработка структуры данных и алгоритма, позволяющих существенно снизить объем памяти кодера и декодера, требуемый для оценивания статистики источника с заданной точностью.
Разработка алгоритмов омофонного кодирования, характеризуемых линейной или меньшей сложностью и быстро адаптирующихся к меняющейся статистике источника.
Построение алгоритма нумерации сочетаний при произвольных алфавитах источника с линейно возрастающей сложностью при увеличении длины входной последовательности.
Введение 14
Построение методов генерации случайных величин, характеризуемых линейным или меньшим ростом сложности при минимизации количества расходуемых случайных бит и создание на их основе эффективных методов вероятностного выбора омофонов для омофонных кодеров.
Построение асимптотически оптимального метода преобразования распределений случайных величин, имеющего не более чем линейную сложность.
Разработка конструкций строго идеальных криптосистем неэкспоненциальной трудоемкости для источников с неизвестной статистикой.
Построение алгоритмов статистического тестирования случайных последовательностей, требующих существенно меньших объемов выборки, чем ранее известные и разработка эффективных схем применения статистических тестов к криптоанализу блоковых шифров.
Методы исследования В процессе исследований были использованы основные положения и методы теории информации, теории кодирования дискретных источников, теории сложности, теории вероятностей и эксперименты на ЭВМ.
Научная новизна результатов работы:
Получено соотношение между избыточностью по входу и избыточностью по выходу в криптосистеме, включающей сжатие и рандомизацию сообщений, что позволяет точно оценивать расстояние единственности для построения идеальных систем.
Получена аналитическая верхняя оценка избыточности арифметического кодирования, на основании которой предложен оптимальный выбор параметров кодера в адаптивной схеме со скользящим окном.
Введение 15
Построен алгоритм для выполнения операций с кумулятивными вероятностями в арифметическом кодере и декодере, требующий логарифмического времени при возрастающем размере алфавита источника и разработаны структура данных и алгоритм, позволяющие экспоненциально снизить объем памяти кодера и декодера, требуемый для оценивания статистики источника с заданной точностью.
Разработаны два алгоритма омофонного кодирования, названные «арифметическое кодирование с разделением интервала» (АКРИ) и «арифметическое кодирование с фиктивным символом» (АКФС), характеризуемые логарифмически растущим объемом памяти и почти логарифмически растущим временем, не требующие дополнительных вычислений при изменении статистики источника. При компьютерной реализации метод АКФС работает в несколько раз быстрее, но имеет большее значение избыточности по входу.
Построен алгоритм нумерации сочетаний для произвольного конечного алфавита источника, характеризуемый почти линейно возрастающей памятью и логарифмически-полиномиальным ростом времени при увеличении длины входной последовательности.
Построены два метода генерации случайных величин, базирующиеся на АКРИ и АКФС декодерах, характеризуемые логарифмическим ростом объема памяти и почти логарифмическим ростом времени вычислений при минимизации количества расходуемых случайных бит. На их основе построены методы вероятностного выбора омофонов для омофонных кодеров, сводящие расходование случайных символов до минимально заданного уровня без увеличения сложности кодеров. Кроме того, предложены быстрые методы выбора омофонов при отсутствии ограничений на количество расходуемых случайных бит, требующие в среднем лишь нескольких машинных операций для осуществления выбора.
Введение 16
Построен асимптотически оптимальный метод преобразования распределений случайных величин, имеющий логарифмическую сложность.
Разработаны и исследованы две базовые конструкции строго идеальных криптосистем линейной трудоемкости для источников с неизвестной статистикой. Первая конструкция базируется на нумерации сочетаний, вторая — на универсальном омофонном коде.
Построены алгоритмы статистического тестирования случайных последовательностей, превосходящие по мощности лучшие 16 тестов, рекомендованных Национальным институтом стандартов и технологий США в 2001 году. На основе разработанных статистических тестов предложена градиентная статистическая атака на блоковые шифры.
Практическая ценность полученных результатов:
Разработанные методы омофонного и адаптивного кодирования позволяют строить идеальные криптосистемы, имеющие существенно меньшую сложность, чем ранее известные.
Предложенные конструкции строго идеальных криптосистем могут быть легко реализованы на практике для большого класса источников информации.
Предложенные методы кодирования сообщений, примененные к произвольным источникам информации, позволяют существенно повысить надежность существующих шифров.
Полученные методы выделения случайности и генерации случайных величин позволяют на порядок повысить вычислительную эффективность использующих их систем при минимизации расходования входных случайных символов.
Введение 17
Разработанные конструкции кодов могут с успехом применяться в задачах сжатия информации для повышения эффективности систем сжатия.
Предложенные методы статистического тестирования, как наиболее мощные на сегодняшний день, могут использоваться для верификации и сертификации случайных последовательностей, получаемых в криптографии.
Реализация и внедрение результатов работы Основные результаты получены в рамках следующих государственных и международных программ:
проекты, финансируемые Российским фондом фундаментальных иссле
дований:
- № 99-01-00586 "Построение эффективных алгоритмов для кодиро
вания и прогнозирования источников информации и нумерации
комбинаторных объектов",
№ 99-07-90438 "Разработка параллельных средств анализа и организации функционирования суперВС с массовым параллелизмом, моделей и методов распараллеливания прикладных задач",
№ 00-01-00672 "Разработка доказуемо стойких криптографических алгоритмов, основанных на эффективных методах кодирования источников информации",
- № 03-01-00495 "Разработка универсальных кодов асимптотически
минимальной сложности";
международный проект INTAS-00-738 "Efficient source coding and related
problems";
Введение . 18
в рамках Программы фундаментальных и прикладных исследований вузов связи Российской Федерации "Фундаментальные аспекты новых информационных и ресурсосберегающих технологий"
НИР "Построение эффективных методов сжатия данных и их применение для разработки доказуемо невскрываемых криптографических систем" (1999-2000),
НИР "Временная оптимизация доказуемо стойких систем защиты информации" (2001);
а также в рамках работ по проекту "Разработка эффективных методов сжатия больших объемов информации для применения в Интернете и других компьютерных сетях" (2002-2004), финансируемому Фондом фундаментальных исследований СибГУТИ.
Результаты диссертации используются в учебном процессе при чтении курсов "Основы криптографии", "Структуры и алгоритмы обработки данных", "Теория вычислительных процессов и систем", а также при выполнении дипломных проектов в СибГУТИ.
Апробация работы Основные результаты докладывались и обсуждались на следующих российских и международных конференциях:
Международный семинар "Перспективы развития современных средств и систем телекоммуникаций" (Новосибирск, 2000).
Международная научно-техническая конференция "Информатика и проблемы телекоммуникаций" (Новосибирск, 2001).
Workshop on Computer Science and Information Technologies CSIT 2001 (Ufa, Russia, 2001).
Международный семинар "Перспективы развития современных средств и систем телекоммуникаций" (Санкт-Петербург, 30 июня - 4 июля, 2002).
Введение 19
2000 IEEE International Symposium on Information Theory (ISIT 2000) (Sorrento, Italy, June 25-30, 2000).
ISIT 2001 (Washington, DC, USA, June 24-29, 2001).
ISIT 2002 (Lausanne, Switzerland, June 24 - June 29, 2002).
2nd IMA Conference on Mathematics in Communication (Lancaster University, UK, 16-18 December 2002).
ISIT 2004 (Chicago, Illinois, USA, June 27 - July 2, 2004).
2nd Russian-German Advanced Research Workshop on Computational Science and High Performance Computing (Stuttgart, Germany, March 14 -16, 2005).
Публикации По теме диссертации опубликовано 29 печатных работ, в том числе 1 монография, 9 статей в журналах и сборниках; подготовлено 8 отчетов о НИР.
Личный вклад Автору диссертации полностью принадлежат конструкции омофонных кодеров на основе арифметичекого кодирования с разделением интервала и с фиктивным символом, схема универсального омофонного кодирования и базирующаяся на ней строго идеальная криптосистема, алгоритмы генерации и преобразования распределений случайных величин на базе омофонных декодеров. В работах, связанных с нумерационным кодированием (выделение случайности, конструкция строго идеальной системы) вклад автора состоит в обобщении быстрого алгоритма нумерации сочетаний на произвольный конечный алфавит источника, разработка доказательств основных теорем. В других совместных работах личный вклад автора составляет не менее 50%.
Введение
Основные положения, выносимые на защиту
Для решения задачи построения идеальных криптосистем и повышения практической стойкости шифров за счет уменьшения расстояния единственности предложена конструкция кода на порядок более эффективная как по времени, так и по объему памяти, чем ранее известные; аналитически определены все необходимые параметры, гарантирующие в конечном счете достижение любого заданного значения расстояния единственности шифра.
Для решения задачи построения идеальных и строго идеальных систем разработан класс методов омофонного кодирования, экспоненциально более эффективных, чем ранее известные, обеспечивающих полную рандомизацию сообщений при заданном произвольно низком их растяжении (избыточности по входу).
Для омофонных кодеров разработаны асимптотически оптимальные методы генерации произвольно распределенных случайных величин на порядок менее трудоемкие, чем ранее известные, и представляющие самостоятельный интерес для решения задач генерации и преобразования распределений случайных величин.
Для решения задач выделения случайности (улучшения физических генераторов случайных чисел) и построения строго идеальных систем построен алгоритм быстрой нумерации сочетаний в произвольном конечном алфавите источника, сложность которого на порядок меньше, чем у ранее известных методов.
Известный со времен Шеннона подход к построению строго идеальных криптосистем требовал экспоненциального по длине сообщения роста трудоемкости и поэтому был не реализуем. На основе нумерации сочетаний для источника без памяти с неизвестной статистикой построена
Введение 21
строго идеальная криптосистема менее чем квадратичной трудоемкости, которая может быть практически реализована.
Омофонные коды обеспечивают полную рандомизацию сообщений, что необходимо для построения идеальных криптосистем, но, как считалось ранее, применимы только при известной статистике источника. Автором диссертационной работы показано, как применить омофонный код к сообщениям источника с неизвестной статистикой. В результате построена идеальная криптосистема с почти линейной трудоемкостью.
Для решения задачи верификации разработанных методов, применяемых к реальным источникам информации, предложены методы статистического тестирования значительно более мощные, чем ранее известные. Предложена схема применения этих методов для анализа блоковых шифров.
Структура и объем работы Диссертация состоит из введения, пяти глав, заключения, списка литературы и приложения. Диссертация содержит 241 страниц машинописного текста. Список литературы включает 108 наименований.
В первой главе вводятся основные понятия, связанные с криптосистемами с секретным ключом, рассматриваются основные виды атак на криптосистему, излагаются и иллюстрируются основные понятия теории секретных систем Шеннона (совершенная система, расстояние единственности шифра), вводится система с предварительным кодированием информации; вводится понятие избыточности по входу и выходу кодера, выводится соотношение между этими избыточностями; рассматривается схема адаптивного арифметического кодирования, описываются и исследуются подходы к уменьшению времени кодирования и декодирования при работе с большими алфавитами и к уменьшению объема памяти, использующейся для оценивания статистики источника; выводится оценка избыточности арифметического кода.
Введение 22
Во второй главе вводится понятие омофонного кода, приводится обзор известных методов; описывается и исследуется новый метод арифметического кодирования с разделением интервала (АКРИ); описывается и исследуется новый метод арифметического кодирования с фиктивным символом (АКФС).
В третьей главе дается постановка задачи выделения случайности, кратко описываются известные методы; ставится задача эффективной нумерации множеств, рассматриваются и анализируются основные подходы к ее решению, описывается и исследуется быстрый алгоритм нумерации сочетаний в произвольном алфавите источника; ставится задача генерации произвольно распределенных случайных величин, приводится краткий обзор известных методов, рассматриваются быстрые алгоритмы для предложенных АКРИ и АКФС омофонных кодеров, предлагается и анализируется идея построения генераторов на базе омофонных декодеров, рассматривается реализация этой идеи применительно к разработанным АКРИ и АКФС кодерам; ставится задача преобразования распределений случайных величин, предлагается и изучается асимптотически оптимальный алгоритм такого преобразования.
В четвертой главе вводится понятие строго идеальной криптосистемы; описывается и исследуется конструкция строго идеальной системы на основе нумерации сочетаний; описывается и исследуется конструкция строго идеальной системы на основе универсального омофонного кодирования.
В пятой главе ставится задача статистического тестирования случайных последовательностей; предлагаются новые методы, приводятся данные экспериментального стравнения предложенных методов с лучшими известными тестами; описывается схема применения предложенных тестов к анализу блоковых шифров, приводятся данные экспериментальных исследований.
В заключении делаются основные выводы по диссертационной работе.
В приложении приводятся основные блоковые шифры, используемые в качестве шифраторов и дешифроторов в предлагаемых идеальных и строго идеальных криптосистемах.
Соотношение избыточностей по входу и выходу
В данном разделе находится соотношение между между входной и выходной избыточностью, которое позволяет судить как о параметрах секретности, так и о параметрах сложности криптосистемы.
Мы показываем, что в схеме без рандомизации входная и выходная избыточности связаны равенством г Р= H{u) + r где H(u) — энтропия на символ источника. Это позволяет сделать интересный вывод. Если энтропия Н(и) велика, то р ведет себя почти так же, как г при г — 0, и сложность кодера, рассматриваемая как функция р, растет так же, как если она рассматривается как функция г. Другими словами, эффективный метод сжатия данных также эффективен и для криптографических применений. Но если энтропия источника мала, то уменьшение г не влияет на р до того момента, когда г становится меньше H(u). Как следствие, чтобы обеспечить заданное малое значение р в криптосистеме, может понадобиться очень сложный кодер. И здесь помогает рандомизация.
Мы показываем, что в схеме, включающей рандомизацию, г Р= H(u) + r + e где е (expansion) — это параметр метода рандомизации, определяющий среднее число случайных бит, которые добавляются к кодовому слову символа источника. Кодовая избыточность г возникает вследствие замены неизвестных вероятностей символов их оценками, даваемыми адаптивной моделью источника. Теперь р сожет быть сделано произвольно малым путем выбора достаточно большого е, и нам не нужен сложный кодер, даже если энтропия источника мала.
Рассмотрим стационарный эргодический источник, порождающий буквы в некотором конечном алфавите А. Сообщение источника и1 = щіі2...щ, где все щ Є А, имеет энтропию Н(ие). Энтропия на букву источника H(u) = lim H(ue)/. — oo
Кодер преобразует сообщение ие в кодовую последовательность хп = х\Хч... хп, где все ХІ Є {0,1}. Длина кода п — это случайная величина, которая может рассматриваться как функция от конкретного сообщения и1 Є А1, п = п(ие). Средняя длина кодовой последовательности иеєАе Средняя длина кодового слова df Е(п) = lim Ei{n)/L l—юо
Мы полагаем, что действительные вероятности источника, например, Р(г/), не известны, и кодер полагается на некоторые оценки этих вероятностей. Избыточность кодера на символ определяется как г = Е{п)-Н{и). (1.8)
Сложность метода кодирования (декодирования) измеряется в терминах времени и объема памяти. Сложность по времени Т выражается числом битовых операций, которые необходимо выполнять при кодировании (декодировании) одного символа источника. Сложность по памяти S — это объем памяти кодера (декодера) в битах. Чтобы можно было судить об эффективности различных методов, естественно рассматривать показатели сложности как функции от кодовой избыточности г.
В теории информации хорошо известно, что если избыточность кода г = О, то кодовая последовательность не отличима от последовательности равновероятных и независимых бит, т.е. распределена равномерно и для каждого кодового бита х мы имеем Рт(х = 0) = Pr(rc = 1) = 1/2. Энтропия бита кода Н{х) = 1, т.е. достигает максимума, и энтропия кодовой последовательности хп составляет п бит.
Если г 0, то кодовая последовательность получается не равномерно распределенной: нули и единицы зависимы и/или имеют разные вероятности. Энтропия кодовой последовательности Н(хп) п.
Поэтому естественно определить выходную избыточность кодера для п-битовой кодовой последовательности как рп = п-Н(хп). Выходная избыточность на один бит р = lim рп/п = 1 - lim Н(хп)/п = 1 - Н(х), (1.9) П—+00 П—»00 где Н(х) = lim oo H{xn)Jn — энтропия на символ (на бит) кодовой последовательности (так называемая предельная энтропия). Т.к. в криптосистеме кодовая последовательность — это входное сообщение для шифратора, выходная избыточность — это целевой параметр метода кодирования.
Задача построения кодов для криптографии теперь переформулируется следующим образом: для произвольного заданного значение р 1 необходимо найти метод кодирования со строго доказанным уровнем выходной избыточности р р . Если несколько методов удовлетворяют этому условию, то естественно сравнить их по сложности, рассматриваемой как функция р. Для решения задачи необходимо установить взаимосвязь между риг.
Арифметическое кодирование с разделением интервала
Итак, при посимвольном омофонном кодировании для каждого символа сообщения выбирается соответствующий ему интервал и производится омофонное кодирование этого интервала. Основная идея арифметического кодирования заключается в том, что кодирование интервала на каждом шаге не производится. Вместо этого на интервале, соответствующем первому символу сообщения, рассматривается новое распределение символов алфавита источника, в котором выбирается интервал, соответствующий второму символу сообщения и т.д. Иными словами, каждый последующий символ сообщения сужает текущий интервал до интервала, соответствующего этому символу. В результате получается интервал, соответствующий всему сообщению. Для рандомизации сообщения необходимо произвести омофонное кодирование этого заключительного интервала.
На пути реализации описанной идеи возникает следующая трудность: раз рядность чисел, представляющих границы интервала, а следовательно и точ ность вычислений, возрастает при увеличении длины сообщения. Например, для представления интервалов для символов с вероятностями (2.1) достаточ но разделить отрезок на 16 частей, что соответствует представлению границ интервалов в виде 4-значных двоичных чисел. Для представления интервалов для двухбуквенных сообщений отрезок нужно будет разделить уже на 162 = 256 частей, что соответствует представлению границ интервалов в виде 8-значных двоичных чисел. При арифметическом кодировании постоянная точность вычислений сохраняется за счет масштабирования и округления интервалов (точнее, отсечения дробной части у границ интервала, см. Алгоритм 1.2). В случае сжатия данных округление интервала лишь увеличивает избыточность кода, но при решении задачи рандомизации оно не допустимо, т.к. результирующая кодовая последовательность не будет состоять из равновероятных и независимых нулей и единиц. Вместо округления границ интервала мы делим интервал на части (или подынтервалы) и выбираем одну из частей с вероятностью, пропорциональной ее длине. Это соответствует представлению кодируемого символа омофонами.
В качестве примера рассмотрим кодирование сообщения abc. Для представления границ интервала будем использовать 4-значные двоичные числа, записываемые для удобства в десятичной системе счисления (как будет показано далее, точность представления границ интервала зависит от минимальной вероятности символа и заданной избыточности). Обозначим через \а\ длину интервала для символа а, через \ab\ — суммарную длину интервалов для символов а и Ь.
Получив первый символ сообщения, выбираем интервал [0, 7), соответствующий букве а. Заключительный интервал для сообщения abc будет находиться внутри интервала [0, 7), а интервал [0, 7) целиком лежит в левой половине полного интервала. Поэтому первый бит кода заключительного интервала будет равен нулю. Передадим ноль на выход кодера и исключим из рассмотрения правую половину полного интервала. Увеличим масштаб оставшейся (левой) половины вдвое. При этом интервал [0, 7) перейдет в интервал [0, 14). Описанный процесс, в ходе которого был получен кодовый бит, назовем С-масштабированием.
Найдем распределение букв алфавита источника на интервале [0, 14). Для этого вычислим \a\ = dP(a), \ab\ = d(P(a) + P(b)), где d есть длина интервала. Для следующего символа сообщения выберем интервал [б, ll), соответствующий букве Ъ. Так как границы интервала не являются целыми числами, разделим интервал на три части с длинами 7/8, 4 и 3/8 и произведем вероятностный выбор одной из них. Допустим, выбрана средняя часть длиной 4, т.е. интервал [7, 11). Попытаемся его масштабировать. Интервал [7, 11) не принадлежит какой-либо одной половине полного интервала, поэтому его С-масштабирование не возможно. Однако он целиком лежит во второй и третьей четвертях полного интервала. Это означает, что следующие два кодовых бита могут быть либо 01, либо 10. Важно, что второй бит является обратным по отношению к первому. Введем переменную S и запишем = 1, чтобы запомнить, что после очередного кодового бита (когда он определится), нужно будет вставить один обратный бит. Увеличим вдвое масштаб второй и третьей четверти. При этом интервал [7, 11) перейдет в интервал [6, 14), а середина полного интервала останется на месте. Описанный процесс, в ходе которого формируется значение 5, назовем 5-масштабированием.
Эффективная генерация произвольно распределенных случайных величин
Задача генерации случайных величин хорошо известна. Традиционной областью ее приложения было моделирование, но сегодня эта задача также актуальна для кодирования источников (например, в схеме мнимого скользящего окна, глава 1) и особенно для омофонного кодирования (глава 2). Базовая постановка задачи сводится к выработке случайного числа, которое подчиняется некоторому заданному распределению вероятностей на основе последовательности, сгенерированной известным случайным процессом, например путем подбрасываний монеты. Использование понятия монеты общепринято в области алгоритмов генерации случайных величин, хотя совершенно ясно, что в реальных системах используются другие источники случайных символов. Монета называется правильной (несмещенной) если при ее подбрасывании получается последовательность равновероятных и независимых чисел О и 1, р(0) = р(1) = 1/2. Монета называется смещенной, если р(0) ф р(1). -Агарная (или М-сторонняя) монета может принимать М различных значений из {1,2,... ,М} и может быть смещенной или несмещенной. Обычно полагается, что подбрасывания монеты независимы и распределены одинаково. Основное естественное требование к решению задачи заключается в минимизации (в среднем) числа подбрасываний для генерации одной случайной величины при наименьших возможных вычислительных затратах.
Кнут и Яо [б] предложили метод для генерации случайных чисел с заданным распределением вероятностей путем подбрасываний правильной монеты. В их методе подбрасывания монеты прослеживаются по некоторому дереву разбора, каждый путь от корня к листу в котором ассоциирован с некоторой вероятностью из заданного распределения. Они предложили конструкцию дерева, котороая минимизирует среднее число подбрасываний монеты и установили, что Н + 2 есть нижняя граница для среднего числа подбрасываний, где Н — это энтропия Шеннона для заданного распределения. Метод Кнута и Яо был нами фактически проиллюстрирован на стр. 2.1.
В следующем подразделе мы опишем метод генерации двоичных и троичных случайных величин близкий по духу к алгоритму Кнута и Яо, но не требующий построения деревьев и поэтому более быстрый при компьютерной реализации. Этот метод может быть использован в схемах омофонных кодеров АКРИ и АКФС, представленных в главе 2, если подбрасывания монеты реализуются дешево и их не нужно экономить.
Некоторые исследователи, например, Абрахаме [23], Роше [64], Хан и Хо-ши [40], предложили обобщение задачи генерации случайных чисел на случай использования в качестве входа смещенных М-арных монет, что позволяет генерировать одно неравномерное распределение из другого. Но что, как нам кажется, более важно, в [64], [40] акцент был сделан на генерирование последовательности случайных чисел, а не одного числа. В этом случае алгоритм Кнута и Яо сохраняет оптимальность по количеству подбрасываний только если вся последовательность представляется как одно большое число, составленное из элементов последовательности как из цифр, что требует экспоненциального роста дерева при увеличении длины последовательности. Методы из [64], [40] справляются с этой трудностью путем реализации последовательной процедуры, напоминающей арифметическое декодирование. Так, алгоритм Хана и Хоши [40] требует лишь линейного роста объема памяти при увеличении длины последовательности. Однако, этот метод предполагает использование операций типа умножения с линейно возрастающей длиной чисел, что приводит к почти квадратичному (в пересчете на один символ входной последовательности) росту времени вычислений.
Для построения класса более быстрых методов генерации случайных чисел мы предлагаем подход, основанный на омофонном кодировании. Техника омофонного кодирования была подробно рассмотрена во второй главе, где, в частности, были описаны два эффективных метода, названные АКРИ и АКФС. Мы показываем, что при использовании этих методов генерация случайных величин требует лишь логарифмического роста объема памяти и примерно логарифмического роста времени вычислений при приближении к нижней границе для количества подбрасываний монеты. Мы также описываем применение этого подхода к реализации омофонных кодеров в ситуации, когда нужно максимально экономить подбрасывания монет при реализации выбора омофонов.
Конструкция идеальной криптосистемы на базе нумерационного кода
В этом разделе мы рассмотрим конструкцию идеальной системы, впервые предложенную в [14], ограничившись описанием только основной идеи применительно к случаю, когда сообщение порождается двоичным источником без памяти с неизвестной статистикой, иными словами, делается последовательно и независимо случайный выбор буквы из алфавита А = {0,1,0,2}, причем вероятности выбора букв неизвестны. В следующем разделе будет представлен общий алгоритм.
Пусть источник порождает сообщения 1 2 ... xt, t — со, и имеется ключ фиксированной длины k = кікч .. .ks, s 1. (Как мы упомянули выше, предполагается также, что энтропия источника на букву отлична от нуля, так как в противном случае вообще нет необходимости в передаче сообщений.) Будем последовательно разбивать сообщение источника на блоки символов длины п, где п 1 — параметр метода. Обозначим один из таких блоков через х. Опишем преобразования, выполняемые над каждым таким п-буквенным блоком.
Вначале определим количество букв а\ и ач в блоке х. Пусть, скажем, имеется 72i букв а\ и тії = п — щ букв «2 Определим u{x) как слово длины [log(n+ 1)] бит, кодирующее Пі.
Теперь рассмотрим множество S всех последовательностей, состоящих из пі букв а\ и тії букв ач- В этом множестве \riij п\\(п — щ)\ элементов. Несмотря на то, что нам не известны вероятности последовательностей из множества S, одно мы можем сказать точно — все они равны между собой (в силу независимости выбора отдельных букв сообщения). Зададим на множестве S некоторый порядок, например, расположим сообщения в порядке возрастания соответствующих им двоичных чисел (считая, что а\ = О, ач — 1). Вычислим номер данного конкретного блока х внутри упорядоченного множества S с помощью алгоритма нумерации сочетаний (глава 3). Обозначим этот номер через ш{х).
Разобьем множество S на непересекающиеся подмножества SQ , S\, ..., Su с числами элементов, равными различным степеням двойки (например, если IS"! = 21, то получаем три подмножества с числами элементов 16, 4 и 1). По и{х) определим, какому подмножеству принадлежит х (обозначим номер такого подмножества через v(x)), и найдем номер х внутри данного подмножества (обозначим этот номер через w(x)).
Посмотрим внимательно на номер сообщения внутри подмножества, w(x). Замечательно то, что w(x) — это полностью случайная последовательность нулей и единиц (т.е. такая, где символы независимы, а вероятности нуля и единицы равны). Действительно, w{x) — это номер одной из равновероятных последовательностей букв в подмножестве из 2Ь элементов (для некоторого 6). Номера всех таких последовательностей — это всевозможные последовательности из b двоичных цифр. Но если все последовательности из b двоичных цифр равновероятны, то отдельные символы равновероятны и независимы.
Итак, обрабатывая описанным образом последовательные блоки сообщения, мы представляем сообщение в виде u{xi)v{xi)w{xi)u{x2)v{x2)w{x2)... .
Теперь перейдем к описанию процесса шифрования преобразованного сообщения. На первый взгляд это может показаться странным, но слова и(-) и v(-) вообще не шифруются! Шифруются только слова w(-) с использованием секретного ключа к. В качестве шифра можно, например, использовать побитовое сложение по модулю 2 с периодически продолженным ключом. Для описания этого шифра удобно занумеровать символы слов w(-) подряд и обозначить их через W1W2W3 .... Тогда шифрование проводится по формуле Z{ == І і й? fci mod s
В результате применения описанного метода мы зашифровали сообщение следующим образом: хгх2...xt — у = u(x1)v(x1)z(x1)u(x2)v(x2)z(x2).... (4.4)
По построению алгоритма ясно, что из правой части (4.4) можно восстановить сообщение, если знать к. Вначале нужно дешифровать символы слов го(-), используя формулу Wi = Z{ ф k{ mod si (4 "j а затем из слов u( )v(-)w(-) восстанавливаются последовательные блоки сообщения. Пример 4.2. Пусть требуется зашифровать сообщение агаг іагагагаїагагаї с трехбитовым ключом k = 011. Разобьем сообщение на два блока по пять символов, n = 5.
