автореферат диссертации по радиотехнике и связи, 05.12.13, диссертация на тему:Эффективные методы построения идеальных криптографических систем защиты информации

Фионов Андрей Николаевич

ЭФФЕКТИВНЫЕ МЕТОДЫ ПОСТРОЕНИЯ ИДЕАЛЬНЫХ КРИПТОГРАФИЧЕСКИХ СИСТЕМ ЗАЩИТЫ ИНФОРМАЦИИ

Специальность 05.12.13 — Системы, сети и устройства

телекоммуникаций

АВТОРЕФЕРАТ

диссертации на соискание ученой степени доктора технических наук

Новосибирск-2005

На правах рукописи

УДК 621.391

Фионов Андрей Николаевич

ЭФФЕКТИВНЫЕ МЕТОДЫ ПОСТРОЕНИЯ ИДЕАЛЬНЫХ КРИПТОГРАФИЧЕСКИХ СИСТЕМ ЗАЩИТЫ ИНФОРМАЦИИ

Специальность 05.12.13 — Системы, сети и устройства

телекоммуникаций

АВТОРЕФЕРАТ

диссертации на соискание ученой степени доктора технических наук

Новосибирск-2005

&4ЧУП2

Работа выполнена в Государственном образовательном учреждении высшего профессионального образования «Сибирский государственный университет телекоммуникаций и информатики» (ГОУ ВПО «СибГУТИ»)

Научный консультант: доктор технических наук, профессор

Рябко Борис Яковлевич

Официальные оппоненты: доктор технических наук, профессор

Губарев Василий Васильевич

доктор физико-математических наук, профессор Дьячков Аркадий Георгиевич

доктор технических наук, профессор Елепов Борис Степанович

Ведущее предприятие: Московский физико-технический институт

(государственный университет)

Защита состоится 'И.'^-О0'?- в Ю00 часов на заседании диссертационного совета Д219.005.01 при ГОУ ВПО «СибГУТИ» по адресу: 630102, г. Новосибирск, ул. Кирова, 86.

С диссертацией можно ознакомиться в библиотеке «СибГУТИ».

Автореферат разослан 1 0 • Ъ 00

Ученый секретарь диссертационного соверг к.т.н., профессор

НАЦИОНАЛЬНАЯ БИБЛИОТЕКА

ОЭ КХруТУ^ ^

Крук Б И.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность проблемы Одной из важных областей исследований в системах, сетях и устройствах телекоммуникаций является исследование и разработка новых методов защиты информации и обеспечение информационной безопасности этих систем, сетей и устройств. В свою очередь, защита информации в значительной степени базируется на использовании криптографических методов, связанных с шифрованием данных. Наибольшее практическое применение для шифрования информации в настоящее время находят симметричные системы, построенные на основе блоковых или потоковых шифров с секретным ключом. В этих системах абоненты взаимодействуют по открытым каналам связи, доступным некоторому противнику. Каждая пара абонентов имеет общий секретный ключ, который используется для шифрования передаваемых данных Предполагается, что секретные ключи передаются по закрытому (или защищенному) каналу, имеющему значительно меньшую пропускную способность по сравнению с открытым каналом. В зависимости от использованных методов построения эти системы можно разделить на два больших класса: вычислительно стойкие системы и безусловно стойкие системы. Разница между этими классами проявляется при рассмотрении атаки по шифротексту, когда криптоаналитик (противник) имеет перехваченный шифротекгт (криптограмму) и пытается восстановить сообщение и использованный секретный ключ.

Большинство из практически используемых в настоящее время криптосистем обладают лишь вычислительной стойкостью. Это означает, например, что шифры могут в принципе быть взломаны путем полного перебора ключей Но что более важно отметить, пока никому не удалось найти каких-либо строгих доказательств того, что для тех или иных вычислительно стойких систем не существует более эффективных алгоритмов взлома, чем перебор ключей. Более того, история криптоанализа свидетельствует о том, что для многих систем, казавшихся надежными, со временем такие более эффективные алгоритмы взлома находятся, а некоторые системы в результате оказываются настолько нестойкими, что выходят из практического использования Основная проблема здесь состоит в том, что при отсутствии математически строгих доказательств стойкости никто не может быть уверен, что противник уже сегодня не располагает эффективными методами, направленными против используемых криптосистем. Если говорить о перспективах применения вычислительно стойких систем, то следует также отметить, что большую угрозу

для таких систем представляют квантовые компьютеры Сегодня квантовые компьютеры изучаются в основном на уровне математических моделей, хотя имеются сведения о первых практических реализациях с ограниченными вычислительными возможностями (скажем, реализующие 7-битовые квантовые алгоритмы). В многочисленных работах по квантовым компьютерам показано, что с их помощью многие криптоаналитические задачи, практически нерешаемые в традиционных вычислительных системах, могут быть быстро решены. Таким образом, если сегодня вычислительно стойкие системы в целом удовлетворительно решают возлагаемые на них задачи по защите информации, то ситуация может резко измениться в ближайшем будущем, если квантовые компьютеры станут реальностью или будут открыты новые эффективные методы криптоанализа.

В противоположность вычислительно стойким системам, безусловно стойкие системы гарантируют невозможность вскрытия шифров (при соблюдении некоторых условий, связанных с их корректным применением), независимо от вычислительных возможностей криптоаналитика. Это свойство делает весьма актуальной задачу эффективных методов построения таких систем. Основы теории стойкости криптосистем были заложены К. Шенноном. Отметим здесь три основные понятия, которые он ввел: совершенная криптосистема, расстояние единственности шифра и идеальная криптосистема Формальные определения этих понятий будут даны в соответствующих главах, а здесь ограничимся их неформальным рассмотрением, которое позволит судить о стоящих перед нами задачах. Совершенная криптосистема предполагает, что независимо от объема перехваченного шифротекста противник не получает никакой информации о сообщении. Примером совершенной системы является шифр Вернама В этом шифре длина секретного ключа равна длине сообщения и ключ используется только один раз Можно сказать, что шифр Вернама применим в системах, где пропускная способность открытого и закрытого каналов одинакова. Однако, на практике, как указывалось выше, пропускная способность закрытого канала часто много меньше пропускной способности открытого канала. В таких случаях секретные ключи намного короче передаваемых сообщений и существует некоторая «критическая» длина шифротекста, названная расстоянием единственности шифра, при которой криптоаналитик может определить ключ почти однозначно. Шеннон показал, что расстояние единственности пропорционально длине ключа и обратно пропорционально избыточности сообщения. Ключ может обновляться (или по

рождаться) с некоторой скоростью, определяемой пропускной способностью закрытого канала. Если ключ обновляется быстрее, чем достигается расстояние единственности, то криптоаналитик не может получить единственного решения криптограммы, те не может вскрыть шифр. Такую систему Шеннон назвал идеальной Если избыточность сообщения удается сделать равной нулю, то расстояние единственности становится бесконечным и мы получаем строго идеальную криптосистему В строго идеальной криптосистеме криптоаналитик всегда получает множество допустимых решений криптограммы соответствующее множеству возможных ключей. Подчеркнем, что в случае когда расстояние единственности больше длины сообщения или криптосистема строго идеальна, шифр оказывается невскрываемым.

Основным способом построения невскрываемых шифров при использовании коротких ключей является кодирование сообщений перед шифрованием. Можно выделить два основных подхода к такому кодированию. Первый заключается в применении традиционного сжатия данных для уменьшения избыточности сообщения и, следовательно, увеличения расстояния единственности шифра. Особенностью этого подхода является то, что он может быть распространен на большое множество моделей источников информации. При этом следует иметь в виду, что в методах кодирования избыточность традиционно определяется как разность между средней длиной кодового слова и энтропией на символ источника (мы называем эту разность избыточностью по входу). Однако для оценки расстояния единственности шифра необходима другая величина, определяемая для двоичного кода как величина отклонения средней энтропии одного кодового символа от единицы (т.е. ее максимально возможного значения). Мы называем эту величину избыточностью по выходу. Как правило, применяемые методы сжатия должны быть характеризованы не эвристическими или экспериментальными, а теоретически доказанными показателями избыточности, чтобы гарантировать определенную величину расстояния единственности. Естественная постановка задачи разработки алгоритмов сжатия сводится к минимизации сложности кодера и декодера при достижении заданной произвольно малой избыточности на символ сообщения.

Второй основной подход состоит в построении специальных кодов или, точнее, преобразований сообщений перед шифрованием. В рамках этого подхода может ставиться задача достижения бесконечного расстояния единственности шифра или, другими словами, построения строго идеальных криптоси-

стем. Получаемые коды не обязательно должны «сжимать» сообщение как раз наоборот, такие коды часто могут быть построены при условии «растяжения» сообщения методами рандомизации. Реализация этого подхода, предлагаемая в настоящей работе, основана на методах нумерационного и омо-фонного кодирования Получаемый код состоит из нескольких отделимых компонент, одна из которых неотличима от последовательности случайных и независимых символов. Именно эта компонента кода подлежит шифрованию, в то время как другие компоненты могут передаваться в открытом виде. Говоря неформально, в отличие от схемы со сжатием данных, здесь шифруется не весь код, а отдельные его части, имеющие наибольшую «степень случайности» Данный подход более эффективен, чем первый, с точки зрения свойств получаемой криптосистемы Однако специальные методы кодирования могут быть не столь эффективны с вычислительной точки зрения при сложных моделях источников.

Решение задач построения безусловно стойких криптосистем в рамках двух указанных основных подходов тесно связано со многими задачами в других разделах криптографии, теории кодирования источников и теории информации в целом Так, например, эффективные конструкции, разработанные для методов сжатия данных, с успехом применяются при построении специальных кодов на основе нумерационного и омофонного кодирования. В свою очередь, омофонное и нумерационное кодирование тесно связано с задачей генерации случайных величин и выделения случайности. Необходимость проверки качества получаемых кодов требует рассмотрения задач статистического тестирования случайных последовательностей. Вообще, решение основной поставленной задачи (построение идеальных систем) привело к необходимости или сделало возможным решение многих смежных задач, что и отражено в представленной работе.

Проблемы криптографии привлекают внимание многих исследователей. Начало научного изучения предмета было положено в работах К. Шеннона (Shannon, С.) в конце 40-х годов XX века, но наиболее активные (открытые) исследования начались в 70-х годах после выхода в свет работ У. Диффи (Diffie, W.), Р. Меркля (Mercle. R.) и М. Хеллмана (Hellman, М.), а также JI. Адлемана (Adleman, L.), Т. Эль-Гамаля (ElGamal, Т.), Р. Ривеста (Rivest, R.), А. Шамира (Shamir, А.) и многих других. Значительный вклад в развитие современной криптографии внесли (открытые) работы Э М. Габи-дулина, Б.Я. Рябко, В М. Сидельникова и целого ряда других отечественных

ученых Вопросы безусловной стойкости криптосистем были впервые рассмотрены К Шенноном и затем, спустя несколько десятилетий, изучались в работах Р. Альсведе (Ahlswede, R.), Дж.Л. Месси (Massey, J.L.), Б.Я. Рябко, Ю."М. Штарькова и др. Омофонными кодами занимались такие исследователи как К. Гюнтер (Günther, Ch.), К. Гирман (Gehrmann, Ch.), Дж.Л. Месси, В Пенцхорн (Penzhorn, W.), B.K. да Рока (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.), Дж. Месси, М.С. Пинскер и многих других. Многочисленные работы посвящены методам универсального, нумерационного и адаптивного кодирования. Основные результаты в этой области принадлежат как отечественным исследователям В.Ф. Бабкину, P.E. Кричевскому, Б.Я. Рябко, В.К Трофимову, Б.М. Фитиигофу, Ю.М. Штарькову, так и зарубежным исследователям Я. Зи-ву (Ziv, J.), Т. Коверу (Cover, Т.), Дж. Лэнгдону (Langdon, G.), А. Лемпелу (Lempel, А.), А. Моффату (Moffat, А ), Й. Риссанену (Rissanen, J ), П. Элай-есу и др.

В качестве основного критерия, по которому можно сравнивать различные методы построения теоретически стойких систем и связанных с ними алгоритмов, может выступать сложность реализации, рассматриваемая как функция некоторого целевого параметра. Для идеальных систем целевым параметром может служить расстояние единственности шифра или тесно связанная с ним избыточность кода. Для строго идеальных систем это может быть размер обрабатываемого блока или сообщения. Для методов выделения случайности и генерации случайных величин — количество расходуемых символов входной последовательности. Сложность измеряется количеством элементарных битовых операций, которые необходимо выполнять для достижения заданного значения целевого параметра (для краткости эта величина иногда называется временем работы или трудоемкостью алгоритма), и объемом памяти в битах, который требуется для выполнения алгоритма. Для

удобства сравнения трудоемкостей они, как правило, приводятся в расчете на один входной (или выходной) символ.

Следует отметить, что до появления работ профессора Б.Я. Рябко и автора настоящей диссертации известные конструкции строго идеальных криптосистем обладали экспоненциальной трудоемкостью (по длине сообщения), что делало их неприменимыми на практике. Оставались также проблемы сложности методов в области омофонного, нумерационного, адаптивного кодирования и в других смежных областях, ограничивающие их практическое применение, в частности, построение идеальных криптосистем

Цель работы состоит в следующем'

1. Построение идеальных криптосистем на основе универсальных и адаптивных методов сжатия данных, обладающих на порядок более низкой сложностью, чем ранее известные, при обеспечении заданной произвольно низкой скорости порождения ключа.

2. Построение строго идеальных криптосистем на основе специальных методов преобразования сообщений, обладающих неэкспоненциальной трудоемкостью.

3. Разработка методов статистического тестирования для экспериментальной проверки качества полученных криптосистем, имеющих мощность существенно большую, чем ранее известные тесты.

Объектом исследований в предлагаемой работе являются криптосистемы, обладающие безусловной стойкостью. Предмет исследований состоит в поиске методов реализации безусловно стойких систем, на порядок более эффективных, чем ранее известные.

Состояние проблемы Известные конструкции строго идеальных криптосистем обладают экспоненциальной по длине сообщения трудоемкостью и, следовательно, практически не реализуемы В то же время известно множество методов кодирования, из которых необходимо особо выделить омо-фонные и адаптивные коды, пригодных для построения идеальных систем за счет снижения расстояния единственности Сложность предложенных другими авторами омофонных кодов, рассматриваемая как функция избыточности и числа используемых при кодировании случайных символов, растет экспоненциально, что затрудняет практическое применение этих кодов Эффективных адаптивных кодов известно достаточно много, однако и здесь имеется

резерв для снижения сложности при достижении заданной произвольно малой избыточности, прежде всего, за счет уменьшения порядка трудоемкости обработки больших алфавитов источников, а также за счет экономии памяти кодера и декодера при реализации адаптивных моделей. Кроме того, многие адаптивные коды характеризованы лишь эвристическими или экспериментальными оценками, в то время как для криптографических применений требуются строго доказанные теоретические оценки Остановимся также на характеристике ряда задач, являющихся вспомогательными с точки зрения достижения поставленных целей. Известный метод Элайеса для выделения случайности обладал экспоненциальной сложностью, однако Рябко и Мачи-кина предложили эффективную реализацию этого метода для двоичных алфавитов источника. Наилучший метод генерации произвольно распределенных случайных величин (интервальный алгоритм Хана и Хоши) требует линейного роста памяти и примерно квадратичного роста времени при увеличении длины получаемой последовательности случайных величин. Такими же характеристиками сложности обладает построенный на базе интервального алгоритма метод преобразования распределений случайных величин. Известные статистические тесты, например, рекомендованные для практического использования в системах защиты информации Национальным институтом стандартов и технологий США, для обнаружения отклонений от случайности в «почти» случайных последовательностях, получаемых на выходах низкоизбыточных кодеров, часто требуют объемов выборки значительно превосходящих ресурсы памяти компьютеров, что делает эти тесты неприменимыми.

Задачи исследования Для достижения указанных целей с учетом изложенного состояния проблемы в рамках диссертационной работы решаются следующие задачи.

1. Определение влияния различных типов избыточности на стойкость криптосистем, включающих сжатие и рандомизацию сообщений.

2. Получение аналитической верхней оценки избыточности арифметического кода, как основного метода низкоизбыточного кодирования.

3. Построение алгоритма для выполнения операций с кумулятивными вероятностями в арифметическом кодере и декодере за менее чем линейное время при возрастающем размере алфавита источника и разработка структуры данных и алгоритма, позволяющих существенно снизить

объем памяти кодера и декодера, требуемый для оценивания статистики источника с заданной точностью

4. Разработка алгоритмов омофонного кодирования, характеризуемых линейной или меньшей сложностью и быстро адаптирующихся к меняющейся статистике источника.

5. Построение алгоритма нумерации сочетаний при произвольных алфавитах источника с линейно возрастающей сложностью при увеличении длины входной последовательности.

6. Построение методов генерации случайных величин, характеризуемых линейным или меньшим ростом сложности при минимизации количества расходуемых случайных бит и создание на их основе эффективных методов вероятностного выбора омофонов для омофонных кодеров.

7. Построение асимптотически оптимального метода преобразования распределений случайных величин, имеющего не более чем линейную сложность.

8. Разработка конструкций строго идеальных криптосистем неэкспоненциальной трудоемкости для источников с неизвестной статистикой.

9. Построение алгоритмов статистического тестирования случайных последовательностей, требующих существенно меньших объемов выборки, чем ранее известные и разработка эффективных схем применения статистических тестов к криптоанализу блоковых шифров.

Методы исследования В процессе исследований были использованы основные положения и методы теории информации, теории кодирования дискретных источников, теории сложности, теории вероятностей и эксперименты на ЭВМ.

Научная новизна результатов работы:

1. Получено соотношение между избыточностью по входу и избыточностью по выходу в криптосистеме, включающей сжатие и рандомизацию сообщений, что позволяет точно оценивать расстояние единственности для построения идеальных систем.

2. Получена аналитическая верхняя оценка избыточности арифметического кодирования, на основании которой предложен оптимальный выбор параметров кодера в адаптивной схеме со скользящим окном.

3. Построен алгоритм для выполнения операций с кумулятивными вероятностями в арифметическом кодере и декодере, требующий логарифмического времени при возрастающем размере алфавита источника и разработаны структура данных и алгоритм, позволяющие экспоненциально снизить объем памяти кодера и декодера, требуемый для оценивания статистики источника с заданной точностью.

4. Разработаны два алгоритма омофоняого кодирования, названные «арифметическое кодирование с разделением интервала» (АКРИ) и «арифметическое кодирование с фиктивным символом» (АКФС), характеризуемые логарифмически растущим объемом памяти и почти логарифмически растущим временем, не требующие дополнительных вычислений при изменении статистики источника. При компьютерной реализации метод АКФС работает в несколько раз быстрее, но имеет большее значение избыточности по входу.

5. Построен алгоритм нумерации сочетаний для произвольного конечного алфавита источника, характеризуемый почти линейно возрастающей памятью и ло1 арифмически-полиномиальным ростом времени при увеличении длины входной последовательности.

6. Построены два метода генерации случайных величин, базирующиеся на АКРИ и АКФС декодерах, характеризуемые логарифмическим ростом объема памяти и почти логарифмическим ростом времени вычислений при минимизации количества расходуемых случайных бит. На их основе построены методы вероятностного выбора омофонов для омофонных кодеров, сводящие расходование случайных символов до минимально заданного уровня без увеличения сложности кодеров. Кроме того, предложены быстрые методы выбора омофонов при отсутствии ограничений на количество расходуемых случайных бит, требующие в среднем лишь нескольких машинных операций для осуществления выбора.

7. Построен асимптотически оптимальный метод преобразования распределений случайных величин, имеющий логарифмическую сложность.

8. Разработаны и исследованы две базовые конструкции строго идеальных криптосистем линейной трудоемкости для источников с неизвестной статистикой Первая конструкция базируется на нумерации сочетаний. вторая - на универсальном омофонном коде.

9. Построены алгоритмы статистического тестирования случайных последовательностей, превосходящие по мощности лучшие 16 тестов, рекомендованных Национальным институтом стандартов и технологий США в 2001 году. На основе разработанных статистических тестов предложена градиентная статистическая атака на блоковые шифры.

Практическая ценность полученных результатов:

1. Разработанные методы омофонного и адаптивного кодирования позволяют строить идеальные криптосистемы, имеющие существенно меньшую сложность, чем ранее известные.

2. Предложенные конструкции строго идеальных криптосистем могут быть легко реализованы на практике для большого класса источников информации.

3. Предложенные методы кодирования сообщений, примененные к произвольным источникам информации, позволяют существенно повысить надежность существующих шифров.

4. Полученные методы выделения случайности и генерации случайных величин позволяют на порядок повысить вычислительную эффективность использующих их систем при минимизации расходования входных случайных символов.

5. Разработанные конструкции кодов могут с успехом применяться в задачах сжатия информации для повышения эффективности систем сжатия.

6. Предложенные методы статистического тестирования, как наиболее мощные на сегодняшний день, могут использоваться для верификации и сертификации случайных последовательностей, получаемых в криптографии.

Реализация и внедрение результатов работы Основные результаты получены в рамках следующих государственных и международных программ:

• проекты, финансируемые Российским фондом фундаментальных исследований:

- № 99-01-00586 "Построение эффективных алгоритмов для кодирования и прогнозирования источников информации и нумерации комбинаторных объектов",

- № 99-07-90438 "Разработка параллельных средств анализа и организации функционирования суперВС с массовым параллелизмом, моделей и методов распараллеливания прикладных задач",

- № 00-01-00672 "Разработка доказуемо стойких криптографических алгоритмов, основанных на эффективных методах кодирования источников информации",

- № 03-01-00495 "Разработка универсальных кодов асимптотически минимальной сложности";

• международный проект INTAS-00-738 "Efficient source coding and related problems";

в рамках Программы фундаментальных и прикладных исследований вузов связи Российской Федерации "Фундаментальные аспекты новых информационных и ресурсосберегающих технологий"

• НИР "Построение эффективных методов сжатия данных и их применение для разработки доказуемо нсвскрываемых криптографических систем" (1999-2000),

• НИР "Временная оптимизация доказуемо стойких систем защиты информации" (2001);

а также в рамках работ по проекту "Разработка эффективных методов сжатия больших объемов информации для применения в Интернете и других компьютерных сетях'" (2002-2004), финансируемому Фондом фундаментальных исследований СибГУТИ.

Результаты диссертации используются в учебном процессе при чтении курсов "Основы криптографии'', "Структуры и алгоритмы обработки данных", "Теория вычислительных процессов и систем", а также при выполнении дипломных проектов в СибГУТИ.

Апробация работы Основные результаты докладывались и обсуждались на следующих российских и международных конференциях'

• Международный семинар '"Перспективы развития современных средств и систем телекоммуникаций" (Новосибирск, 2000).

• Международная научно-техническая конференция "Информатика и проблемы телекоммуникаций" (Новосибирск, 2001).

• Workshop on Computer Science and Information Technologies CSIT 2001 (Ufa, Russia, 2001)

• Международный семинар "Перспективы развития современных средств и систем телекоммуникаций" (Санкт-Петербург, -30 июня - 4 июля, 2002).

• 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 монография, подготовлено 8 отчетов о НИР.

Личный вклад Автору диссертации полностью принадлежат конструкции омофонных кодеров на основе арифметического кодирования с разделением интервала и с фиктивным символом, схема универсального омофонного

кодирования и базирующаяся на ней строго идеальная криптосистема, алгоритмы генерации и преобразования распределений случайных величин на базе омофонных декодеров В работах, связанных с нумерационным кодированием (выделение случайности, конструкция строго идеальной системы) вклад автора состоит в обобщении быстрого алгоритма нумерации сочетаний на произвольный конечный алфавит источника, разработка доказательств основных теорем. В других совместных работах личный вклад автора составляет не менее 50%.

Основные положения, выносимые на защиту

I. Для решения задачи построения идеальных криптосистем и повышения практической стойкости шифров за счет уменьшения расстояния единственности предложена конструкция кода на порядок более эффективная как по времени, так и по объему памяти, чем ранее известные; аналитически определены все необходимые параметры, гарантирующие в конечном счете достижение любого заданного значения расстояния единственности шифра.

2 Для решения задачи построения идеальных и строго идеальных систем разработан класс методов омофонного кодирования, экспоненциально более эффективных, чем ранее известные, обеспечивающих полную рандомизацию сообщений при заданном произвольно низком их растяжении (избыточности по входу)

3. Для омофонных кодеров разработаны асимптотически оптимальные методы генерации произвольно распределенных случайных величин на порядок менее трудоемкие, чем ранее известные, и представляющие самостоятельный интерес для решения задач генерации и преобразования распределений случайных величин.

4. Для решения задач выделения случайности (улучшения физических генераторов случайных чисел) и построения строго идеальных систем построен алгоритм быстрой нумерации сочетаний в произвольном конечном алфавите источника, сложность которого на порядок меньше, чем у ранее известных методов.

5 Известный со времен Шеннона подход к построению строго идеальных криптосистем требовал экспоненциального по длине сообщения роста

трудоемкости и поэтому был не реализуем На основе нумерации сочетаний для источника без памяти с неизвестной статистикой построена строю идеальная криптосистема менее чем квадратичной трудоемкости, которая может быть практически реализована.

6 Омофонные коды обеспечивают полную рандомизацию сообщений, что необходимо для построения идеальных криптосистем, но, как считалось ранее, применимы только при известной статистике источника Автором диссертационной работы показано, как применить омофонный код к сообщениям источника с неизвестной статистикой. В результате построена идеальная криптосистема с почти линейной трудоемкостью.

7. Для решения задачи верификации разработанных методов, применяемых к реальным источникам информации, предложены методы статистического тестирования значительно более мощные, чем ранее известные. Предложена схема применения этих методов для анализа блоковых шифров

Структура и объем работы Диссертация состоит из введения, пяти глав, заключения, списка литературы и приложения. Диссертация содержит 241 страницу машинописного текста. Список литературы включает 108 наименований.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

В первой главе вводятся основные понятия, связанные с криптосистемами с секретным ключом, рассматриваются основные виды атак на криптосистему, излагаются и иллюстрируются основные понятия теории секретных систем Шеннона (совершенная система, расстояние единственности шифра), вводится схема системы с предварительным кодированием информации; вводится понятие избыточности по входу и выходу кодера, выводится соотноше-

)

ние между этими избыточностями; рассматривается схема адаптивного арифметического кодирования, описываются и исследуются подходы к уменьшению времени кодирования и декодирования при работе с большими алфавитами и к уменьшению объема памяти кодера и декодера, использующейся для оценивания статистики источника; выводится оценка избыточности арифметического кода.

Рассматривается задача передачи секретных сообщений от некоторого отправителя А к получателю В по открытому каналу связи при наличии противника Е. Чтобы скрыть содержание сообщений от Е, А шифрует их перед передачей, а В расшифровывает после приема. В настоящее время для шифрования данных в подобного рода системах используются блоковые и потоковые шифры, являющиеся представителями класса так называемых симметричных схем шифрования или шифров с секретным ключом. Мы для определенности будем предполагать использование в конструируемых системах блоковых шифров. В рассматриваемой системе А и В могут договаг риваться об используемом секретном ключе по специальному «закрытому» каналу, недоступному для прослушивания противником. Как правило, закрытый какал имеет намного меньшую пропускную способность, чем открытый канал. Обычно при анализе криптосистем рассматриваются три основных вида атак: атака по шифротексту, атака по известному тексту и атака по выбранному тексту. Система называется вычислительно стойкой, если для ее вскрытия (нахождения секретного ключа) требуется такое количество вычислений, которое не может быть реализовано на практике. Система называется безусловно стойкой, если она не может быть вскрыта в принципе (при атаке по шифротексту).

К. Шеннон ввел в рассмотрение три вида безусловно стойких систем: совершенные, идеальные и строго идеальные. Система называется совершенной, если апостериорная вероятность любого сообщения при известном шиф-ротексте равна априорной вероятности этого сообщения. Шеннон показал, что система совершенна тогда и только тогда, когда шифротекст статистически не зависит от сообщения. Примером совершенной системы служит шифр Вернама. В этом шифре длина ключа равна длине сообщения и ключ используется только один раз. Если длина ключа меньше длины сообщения, то существует некоторый (средний) объем шифротекста п*, называемый расстоянием единственности шифра, при перехвате которого сообщение, а значит и ключ, могут быть однозначно определены. Обозначим через хп = Х\Х2. ■ - хп сообщение на входе шифратора, а через уп = у\у2 • • ■ уп — сообщение на его выходе, те. шифротекст. полученный при использовании ключа К. Обозначим через Н(хп), Н(уп) и Н{К) соответственно энтропии сообщения, шифротекста и ключа. Пусть сообщение порождается стационарным эрго-дическим источником в алфавите А = {ах, а2, ■ ,адг} и предельная энтропия источника равна Л бит на букву, Л = Итп^<Х1Н(х")/п. Тогда величина

р = log N — h называется избыточностью сообщения (на символ источника) Шеннон показал, что для расстояния единственности справедливо неравен-

Р

Если скорость порождения ключа Н(К)/п превосходит избыточность на символ сообщения р, то расстояние единственности п* всегда будет больше длины шифротекста п. Такую систему Шеннон назвал идеальной. Если избыточность р = 0, то п* = оо (при любой энтропии ключа Н{К) > 0) и мы получаем строго идеальную систему.

Важным приемом для повышения расстояния единственности является предварительное кодирование (сжатие и рандомизация) данных, призванное максимально уменьшить избыточность р. Обычно кодер работает на основании некоторой модели источника, которая может быть статической, универсальной или адаптивной Иными словами, кодер предполагает, что источник принадлежит некоторому классу (например, является марковским второго порядка и т.п.). Избыточность адаптивного кода, обозначаемая через г, определяется как разность между средней длиной кодового слова и энтропией источника. Избыточность шифруемого сообщения р может быть названа выходной избыточностью по отношению к кодеру (или избыточностью по выходу). Если при кодировании используется рандомизация, то вводится еще один показатель — среднее количество случайных бит, добавляемых на каждый символ источника. Эту величину мы обозначаем через е (expansion).

Мы показываем (теорема 1.4), что в схеме без рандомизации входная и выходная избыточности связаны равенством

г

Р= Н(и) + г

где Н(и) — энтропия на символ источника. Это позволяет сделать интересный вывод. Если энтропия Н(и) велика, то р ведет себя почти так же, как г при г —* 0, и сложность кодера, рассматриваемая как функция р, растет так же, как если она рассматривается как функция г. Другими словами, эффективный метод сжатия данных также эффективен и для криптографических применений Но если энтропия источника мала, то уменьшение г не влияет на р до того момента, когда г становится меньше Н(и). Как следствие, чтобы обеспечить заданное малое значение р в криптосистеме, может понадобиться очень сложный кодер. В этом случае полезным приемом оказывается рандомизация сообщений. Мы показываем (теорема 1 о), что в схеме, включающей

рандомизацию,

г

Р~ Н{и) + г + е '

Теперь р может быть сделано произвольно малым путем выбора достаточно большого е, и нам не нужен сложный кодер, даже если энтропия источника мала.

Далее рассматривается задача снижения сложности адаптивного кодирования при достижении заданной произвольно малой избыточности г. Мы используем арифметический кодер как имеющий наименьшую сложность при г —► 0 и адаптивную схему со скользящим окном. Мы отдаем предпочтение этой схеме, потому что она, во-первых, позволяет достаточно точно оценивать статистику источника, во-вторых, легко адаптируется к изменяющейся статистике, и, наконец, при надлежащем выборе размера окна позволяет исключить операции деления в арифметическом кодировании, что заметно увеличивает скорость работы кодера и декодера. Мы предлагаем два направления снижения сложности схемы.

Первое связано с тем, что адаптивная модель обеспечивают получение некоторых оценок вероятностей р(аг) появления каждой буквы а, из алфавита источника А = {ai, a2,..., ад-}. Арифметическое кодирование, однако, требует задания кумулятивных вероятностей Q{al) = J2J<tр{а3). Так как оценки вероятностей изменяются после кодирования каждого нового символа, кумулятивные вероятности необходимо постоянно пересчитывать. Такой пересчет требует O(N) операций на каждый символ источника. В настоящей работе предлагается алгоритм, вычисляющий кумулятивные вероятности за время О (log N), что экспоненциально меньше. Основная идея этого алгоритма заключается в том, что в памяти кодера и декодера хранятся не только оценки вероятностей отдельных символов p{ai), р(аг), p(a-j), ..., но и суммы пар [p(tti) +р(а2)], [р(аз) +р(а4)], - ■ •. суммы четверок и т.д. В результате при изменении некоторой оценки p(at) требуется пересчитать не более log N хранящихся в памяти элементов. С другой стороны, вычисление кумулятивной вероятности требует не более log N сложений. Например, Q(a%) вычисляется с помощью двух сложений

Q(a s) = [P(ai) +Ж«2) +р(аз) +РЫ] + [р(а5) + р(а6)] +р(а7).

Метод аналогичной сложности предлагается также для поиска символа в кумулятивном распределении при декодировании

Второе направление снижения сложности схемы связано с недостатком схемы со скользящим окном — необходимостью хранить окно в памяти кодера и декодера. При достижении малой избыточности память отводимая под окно, становится доминирующей компонентой сложности кодера и декодера и составляет 0((Nlog N)/r) бит (г —> 0) Чтобы устранить указанный недостаток мы используем особый вид скользящего окна, названный "мнимым скользящим окном" (концепция мнимого скользящего окна была предложена в работах Б.Я. Рябко). Этот подход позволяет сохранить все свойства скользящего окна и, в то же время, избавить кодер и декодер от хранения в памяти самого окна. Основная идея состоит в том что при сдвиге окна после кодирования очередного символа из него удаляется не самый старый, а случайно выбранный символ. Распределение вероятностей для выбора удаляемого символа соответствует распределению символов в реальном окне и определяется на основании значений счетчиков частоты встречаемости символов Такой подход позволяет не хранить само окно в памяти кодера и декодера, но, в то же время, достаточно точно оценивать статистику источника. Предложен быстрый алгоритм генерации необходимой случайной величины, характеризующийся логарифмической зависимостью времени выполнения от размера алфавита.

Для точной оценки расстояния единственности получена оценка избыточности арифметического кода (теорема 1.13)

тс < N(t + loge)2~(t-2) + 2/L,

где N — размер алфавита, т - количество бит в представлении вероятностей, t — битовый размер регистров кодера, L — длина кодируемого блока или сообщения. На основании этой оценки даны рекомендации по оптимальному выбору параметров кодера в адаптивной схеме и получена оценка избыточности адаптивного кода (теорема 1.6)

N-1 N+1 г < log е --- -I--—.

И) +1 w + N

где w — размер окна (реального или мнимого), w + N = 2Т.

Оценки избыточности позволили сделать выводы о сложности предложенных методов. Показано, что сложность экспоненциально ниже, чем у ранее известных адаптивных схем.

Также в первой главе рассмотрено обобщение предложенных методов на случай марковских источников произвольного порядка.

Во второй главе вводится понятие омофонного кода, приводится обзор известных методов; описывается и исследуется новый метод арифметического кодирования с разделением интервала (АКРИ); описывается и исследуется новый метод арифметического кодирования с фиктивным символом (АКФС).

Омофонное кодирование представляет собой вид рандомизации сообщений, в котором буква источника заменяется специальными символами (омофонами), выбираемыми случайным образом так, чтобы сделать кодовую последовательность неотличимой от последовательности равновероятных и независимых нулей и единиц Таким образом, омофонное кодирование достигает избыточности текста на входе шифратора р = 0 и. поэтому, позволяет получать безусловно стойкие шифры

Рассмотрим пример побуквенного омофонного кода, предложенного Гюн-тером Пусть источник порождает символы из алфавита А = {а, Ь} с вероятностями Р(а) = 3/4, Р(Ь) = 1/4. Кодирование производится по следующему правилу: а —> 0 с вероятностью 2/3, а —» 10 с вероятностью 1/3. b —11. Мы видим, что символ а может кодироваться двумя кодовыми словами (омофонами). Чтобы осуществить выбор омофона, необходимо сгенерировать случайную величину с распределением вероятностей (2/3. 1/3). При кодировании сообщения источника этим методом получаемая кодовая последовательность неотличима от последовательности равновероятных и независимых нулей и единиц, т.е. имеет избыточность р = 0.

Если в знаменателе вероятностей символов стоит не степень двух, то целесообразно использовать другой метод, предложенный да Рокой. Пусть, например, р(а) = 3/5, р(Ъ) — 2/5. Будем выбирать с вероятностью 3/8 фиктивный символ Д и с вероятностью 5/8 символ источника. После этого р(а) = (3/5)(5/8) = 3/8, р{Ъ) = (2/5)(5/8) = 2/8 и р(А) = 3/8, т.е. в знаменателе вероятностей получается степень двух. Далее можем использовать метод Гюнтера: а —> 00 с вероятностью 2/3, а —> 110 с вероятностью 1/3; Ь —► 01; А —» 10 с вероятностью 2/3, Д —> 111 с вероятностью 1/3. Если был выбран фиктивный символ, то мы вновь возвращаемся к кодированию символа источника. При декодировании фиктивные символы отбрасываются

Основными характеристиками методов омофонного кодирования являются избыточность по входу е, определяемая как разность между средней длиной кодового слова и энтропией источника, и количество случайных бит, необходимых для осуществления вероятностных выборов при кодировании, г] Заметим, что величина е показывает насколько в среднем увеличилась

энтропия источника в пересчете на один символ, поэтому иногда называется «растяжением» сообщения Представленные выше методы являются оптимальными при побуквенном кодировании и характеризуются значениями е < 2, т] = 2е<4 бит на символ. Во многих случаях, особенно для источников с низкой энтропией, избыточность по входу 2 бита на символ сообщения может оказаться слишком высокой. Классическим путем уменьшения этого показателя является кодирование блоков символов. Однако традиционные методы блокового кодирования оказываются практически нереализуемыми из-за экспоненциального роста объема кодовой таблицы при увеличении размера блока. Другим недостатком побуквенных методов является их плохая адаптация к меняющимся вероятностям символов, что, как показано в четвертой главе, важно для универсального омофонного кодирования, применяемого к источникам с неизвестной статистикой.

В настоящей работе предлагаются два метода омофонного кодирования, для которых объем памяти и время кодирования и декодирования растут как 0(logl/e) и О (log 1 /е log log 1/е log log log 1/e) соответственно при e —> 0. Более того, для большого диапазона значений избыточности регистры кодера и декодера не выходят за пределы машинного слова и, поэтому, трудоемкость остается константной (т.е. требустся фиксированное число машинных операций для кодирования и декодирования символа). При использовании описываемых в третьей главе методов генерации случайных величин значение г] может варьироваться от т] « 2 + е до rj и 2е без увеличения порядка сложности кодеров. Наконец, предложенные методы хорошо адаптируются к изменяющейся статистике источника, т.к могут использовать быстрый алгоритм вычисления кумулятивных вероятностей, описанный в первой главе.

Первый метод назван «арифметическое кодирование с разделением интервала» (АКРИ). Он отличается от обычного арифметического кодирования особой техникой обработки интервалов с нецелыми (дробными) границами, гарантирующей нулевую избыточность результирующей кодовой последовательности. Пусть, например, при кодировании очередного символа сообщения получился интервал с дробными границами [4.4, 10.7). Обычное арифметическое кодирование преобразует его к целочисленному интервалу [4, 10) путем отсечения дробных частей, что приводит к появлению избыточности, которая оценивалась в первой главе Алгоритм АКРИ действует по-другому. Он рассматривает три омофонных подынтервала V — [5, 10). = [4.4, 5) и V+ — [10, 10.7). Условие полной рандомизации будет выполнено, если мы

выберем для дальнейшего кодирования только один из этих подынтервалов с вероятностью, пропорциональной его длине Очевидно, что выбор подынтервала V позволяет нам остаться в рамках целых чисел. Если же выбираются подынтервалы У+ или V~, то необходимо масштабировать единичный интервал, включающий в себя или V, и повторить процесс разделения. Например, при длине регистров кодера Ь = А бита, если на первой стадии выбран = [4.4, 5), то масштабируем интервал [4, 5), т.е. фактически увеличиваем его в 24 = 16 раз так. что он переходит в полный интервал [0, 16). При этом V- переходит в интервал [6.4, 16) (его левая граница вычисляется путем умножения числа 0.4 на 16) Полученный интервал представляется в виде двух подынтервалов V = [7, 16) и V' = [6.4, 7). Опять выбирается один из них с вероятностями пропорциональными их длине и т.д., пока выбор не остановится на подынтервале с целочисленными границами Дальнейшие действия не отличаются от действий обычного арифметического кодера.

Показано (теорема 2.2), что алгоритм АКРИ позволяет кодировать сообщения с избыточностью по входу

е < 8т2~* + З/Ь,

где N — размер алфавита источника, Ь — битовая длина регистров кодера, Ь — длина сообщения.

Второй метод назван «арифметическое кодирование с фиктивным символом» (АКФС). Идея АКФС может быть проиллюстрирована на следующем примере. Пусть источник порождает буквы из алфавита А — {а. Ь} с вероятностями р(а) = 3/5, р(Ь) — 2/5 и пусть размер текущего интервала в арифметическом кодере составляет 7 единиц. Мы должны распределить буквы источника на этом интервале в соответствии с их вероятностями. Однако, «правильные» доли букв составляют 4.2 единицы для а и 2.8 единицы для Ь, т.е. не являются целыми числами. Обычный арифметический кодер, за счет отсечения дробных частей, отвел бы 4 единицы для буквы а и 3 единицы для буквы Ь, внося, тем самым, избыточность в код. Алгоритм АКФС предлагает осуществлять безызбыточное кодирование за счет преобразования входного распределения вероятностей Будем выбирать фиктивный символ Д с вероятностью 2/7 и символ источника — с вероятностью 5/7. В результате мы получим распределение р(а) = 3/7, р(Ь) = 2/7 и р(А) = 2/7. Теперь эти три символа хорошо распределяются на интервале в 7 единиц, что приводит к генерации безызбыточного арифметического кода с совершенными стати-

стическими свойствами (нули и единицы равновероятны и независимы). Разумеется, если был выбран Д. то мы еще раз возвращаемся к кодированию символа источника.

Показано (теорема 2 5), что алгоритм АКФС позволяет кодировать сообщения с избыточностью по входу

г-т-2 . 2*~т~2

где I — битовая длина регистров арифметического кодера, т < £ — 3 — битовая длина знаменателя вероятностей символов, Ь — длина сообщения.

При фиксированной длине регистров кодера алгоритм АКФС, как правило, дает большее растяжение сообщения, чем алгоритм АКРИ. Однако, особенности построения алгоритма АКФС делают его в несколько раз более быстрым при компьютерной реализации

В третьей главе дается постановка задачи выделения случайности, кратко описываются известные методы; ставится задача эффективной нумерации множеств, рассматриваются и анализируются основные подходы к ее решению, описывается и исследуется быстрый алгоритм нумерации сочетаний в произвольном алфавите источника; ставится задача генерации произвольно распределенных случайных величин, приводится краткий обзор известных методов, рассматриваются быстрые алгоритмы для предложенных АКРИ и АКФС омофонных кодеров, предлагается и анализируется идея построения генераторов на базе омофонных декодеров, рассматривается реализация этой идеи применительно к разработанным АКРИ и АКФС кодерам; ставится задача преобразования распределений случайных величин, предлагается и изучается асимптотически оптимальный алгоритм такого преобразования.

Вначале рассматривается задача преобразования последовательностей независимых нулей и единиц, вероятности порождения которых, возможно, не равны, в последовательности равновероятных и независимых нулей и единиц, Фон Нейман предложил следующий метод: исходная последовательность разбивается на блоки (слова) длины 2, которые кодируются по следующему правилу:

00 -+ Л, 01 0, 10 1, 11 Л,

где Л обозначает пустое слово. Этот метод решает поставленную задачу, тк. вероятности блоков 01 и 10 равны и сами блоки независимы. Однако, часть входных символов (блоки 00 и 11) теряется Элайес обобщил метод фон Неймана на произвольные длины блоков и ввел показатель эффективности —

величину г]п, определяемую как отношение среднего значения длины получаемого кодового слова к длине блока п Он показал, что верхней границей для величины г]п является энтропия источника Метод Элайеса основан на нумерации сочетаний из п нулей и единиц Предложенный им метод нумерации, однако, имел экспоненциальную по длине блока сложность. В работах Б Я. Рябко и Е.П. Мачикиной предложен метод неэкспоненциальной сложности.

Мы обобщаем рассмотренную задачу, полагая, что на вход поступает последовательность независимых случайных величин, принимающих значения в конечном множестве произвольного размера с неизвестными вероятностями На основе этой входной информации необходимо получить последовательность равновероятных и независимых нулей и единиц. Для решения поставленной задачи разработан быстрый алгоритм нумерации сочетаний символов, выбираемых из произвольного конечного алфавита. Важно отметить, что разработанный алгоритм используется не только для решения задачи выделения случайности, но и для построения строго идеальных криптосистем (глава 4). В связи с этим разработан также эффективный обратный алгоритм Сденумерации), который по заданному номеру находит соответствующее сочетание символов. Показано (теорема 3.2), что для разработанных алгоритмов нумерации и денумерации сочетаний из п символов трудоемкость (в пересчете на один символ) составляет nloglogn) битовых операций, а объем памяти 0(7гк^п) бит.

Другая важная задача, решаемая в третьей главе, называется задачей генерации случайных чисел (величин) и состоит в преобразовании входной последовательности равновероятных и независимых бит в произвольно распределенные случайные величины. Кнут и Яо предложили метод решения задачи на основе деревьев. Например, генерация случайной величины, принимающей значение г>1 с вероятностью 2/3 и с вероятностью 1/3 производится с помощью следующего дерева:

Дерево просматривается, начиная с корня, в соответствии со значениями входных бит. Если переход осуществляется в черный кружок, то случайная

Г

величина принимает соответствующее значение; если переход происходит в белый кружок, то проход по дереву необходимо повторить с использованием новых входных бит Легко видеть, что вероятность выбора У\ в два раза превышает вероятность выбора и2. Это означает, что вероятности выбора р(у 1) = 2/3 и р(г'г) = 1/3, что и требовалось.

Кнут и Яо показали, что их метод оптимален для генерации одной случайной величины £ и требует в среднем #(£) -+- 2 входных бита. Среднее превышение количества потребляемых бит над энтропией случайной величины мы называем потерей генератора и обозначаем через е.

Мы предлагаем быстрый метод генерации двоичных и троичных случайных величин, который может быть использован в схемах омофонных кодеров АКРИ и АКФС, представленных в главе 2, если входные биты дешевы и их не нужно экономить. Этот метод близок к алгоритму Кнута и Яо, но основан на интервальном принципе и не требует построения деревьев. При использовании этого метода в составе АКРИ и АКФС кодеров потеря генератора е < е + 2 бит, где е — избыточность по входу кодера.

Во многих схемах, в частности, в омофонном кодировании сообщений, требуется генерация последовательности случайных величин. В этом случае алгоритм Кнута и Яо сохраняет оптимальность по количеству расходуемых входных бит, только если вся последовательность представляется как одно большое число, составленное из элементов последовательности как из цифр, что требует экспоненциального роста дерева при увеличении длины последовательности. В литературе описаны асимптотически оптимальные методы, которые справляются с этой трудностью путем реализации последовательной процедуры, напоминающей арифметическое декодирование. Так, наиболее эффективный из известных интервальный алгоритм Хана и Хоши требует лишь линейного роста объема памяти при увеличении длины последовательности. Однако, этот метод предполагает использование операций типа умножения с линейно возрастающей длиной чисел, что приводит к почти квадратичному (в пересчете на один символ входной последовательности) росту времени вычислений

Для построения класса более быстрых методов генерации случайных чисел мы предлагаем подход, основанный на омофонном декодировании Для объяснения сути предлагаемого подхода заметим, что в результате омофон-ного кодирования сообщение х\х^х^..., х £ А, преобразуется в кодовую последовательность С1С2С3..., с £ {0,1}, символы которой равновероятны и

независимы При декодировании последовательность С1С2С3... поступает на вход декодера, который также знает распределение вероятностей источника. На основании этих данных декодер восстанавливает исходное сообщение Х1Х2Х3.... Заметим теперь, что если вместо С1С2С3... на вход декодера поступает просто последовательность равновероятных и независимых бит г^гз... и некоторое распределение вероятностей, то он выдаст последовательность случайных чисел у\угуъ ■ ■ ■, подчиняющихся этому распределению. Причем, потеря генератора е совпадает с избыточностью по входу е соответствующего омофонного кодера.

С учетом полученных во второй главе оценок избыточности предложенных омофонных кодеров и ее связи со сложностью методов мы получаем следующий результат (теорема 3.6): использование АКРИ-декодирования или АКФС-декодирования позволяет генерировать случайные величины с количеством расходуемых входных бит произвольно близким к энтропии целевого распределения вероятностей, т.е. с произвольно малой потерей е, при следующих оценках объема памяти 5 и времени Т:

Таким образом, сложность предложенных генераторов экспоненциально ниже, чем у ранее известных.

Мы также показываем, что использование этих эффективных генераторов в составе омофонных кодеров позволяет осуществлять вероятностный выбор омофонов со средним количеством расходуемых случайных бит т} < 2е без увеличения порядка сложности алгоритмов. Такая конструкция актуальна, если требуется максимально экономить случайные символы, используемые при омофонном кодировании

Наконец, последняя задача, которая логически вытекает из рассмотренных методов, это построение эффективного алгоритма преобразования распределений случайных величин. Пусть некоторая случайная переменная X принимает значения из множества {1,2,..., М} с известными вероятностями и пусть дана последовательность значений этой случайной переменной Хт = Х\Х2 ■ • -хт. Требуется построить последовательность случайных чисел У" = У\У2---Уп, которые представляют собой значения случайной переменной У, подчиняющейся некоторому целевому распределению над алфавитом {1,2, ...Л/'} Обозначим через Н{Х) и Я(У) энтропии X и У. Показателем эффективности алгоритма решения этой задачи является сред-

/11 1 Т = 0 \\og- ^ - ^ 1о§ 1о§ -

1), —а (»

нее число переменных X требуемых для получения одной переменной Y, lim^oo Е(т)/п. Нижней границей для этого показателя служит отношение энтропий H(Y)/H(X) Наилучший из известных методов, интервальный алгоритм Хана и Хоши, позволяет достичь указанной нижней границы при п —> оо, и, как указывалось выше, требует линейного роста объема памяти и почти квадратичного роста времени вычислений.

Мы предлагаем следующую схему для решения поставленной задачи. Пусть АКРИ или АКФС кодер получает на вход последовательность Хт и работает на основе распределения для X Последовательность с выхода кодера подается на вход декодера, который, однако, работает на основе распределения для Y. То есть отличие от обычной схемы состоит в том, что кодер и декодер используют разные алфавиты и разные распределения вероятностей. Причем, нет необходимости получать промежуточную кодовую последоваг-тельность C\Ci.. .q в явном виде, т.к. кодер и декодер могут соответственно производить и потреблять последовательно бит за битом Для работы кодера, естественно, нужен дополнительный источник случайных символов. Мы заменяем этот дополнительный источник вспомогательным генератором случайных бит и ответвляем малую часть входной последовательности на вход этого генератора. Понятно, что этот вспомогательный генератор не может базироваться на омофонном кодировании. Но мы можем ожидать, что даже относительно более сложный генератор существенно не увеличит общую сложность схемы, тк количество случайных бит, которые он должен генерировать, может быть сделано произвольно малым. В качестве такого генератора мы используем разработанный метод извлечения случайности на основе быстрой нумерации сочетаний. Эта конструкция приводит к следующему результату (теорема 3.8): эффективность схемы преобразования распределений

Е{т) H(Y) lim -i-i = + б,

n-юо П n[X)

причем потеря e может быть сделана сколь угодно малой при росте объема памяти S и времени Т, определяемом оценками (1).

В четвертой главе вводится понятие строго идеальной криптосистемы; описывается и исследуется конструкция строго идеальной системы на основе нумерации сочетаний; описывается и исследуется конструкция строго идеальной системы на основе универсального омофонного кодирования.

Пусть сообщение х\хг-- - xt шифруется при помощи секретного ключа к = k\k<2... ,ks, в результате чего получается зашифрованное сообщение у —

У\У2 ■ У1 Обозначим через Н(х 1X2 ■. • х{) энтропию сообщения, через Н(у) и Н(к) — соответственно энтропии шифротекста и ключа. Тогда Н(х\Х2 ■ ■ ■ у) представляет неопределенность сообщения, а Н(к\у) — неопределенность ключа при условии, что известен шифротекст у. Шифр называется строго идеальным. если

Н{хгх2 ■ ■ ■ х^у) = Н(к\у) = тт{Я(1!а;2... Н{к)}.

Нас интересует случай, когда Н(х 1X2 ■ ■. х^ > Н(к). Неформально, строгая идеальность шифра означает, что количество решений криптограммы равно количеству различных ключей и все решения равновероятны

Мы рассматриваем источник без памяти, который порождает символы в алфавите А = {а\, а?,.. ■, а у} с неизвестными вероятностями. Требуется построить строго идеальную систему для сообщений этого источника. Первая предлагаемая конструкция базируется на нумерационном коде. Опишем основную идею ее построения.

Будем последовательно разбивать сообщение источника на блоки символов длины п. Обозначим один из таких блоков через х и опишем преобразования, выполняемые над каждым блоком. Вначале подсчитаем количество букв а\, а2, ..., адг в блоке х. Пусть, скажем, имеется пг букв а\. п2 букв а,2, ., пдг букв ац- Определим и(х) как слово длины + 1)] бит,

кодирующее последовательность счетчиков пг.

Теперь рассмотрим множество Б всех последовательностей, соответствующих слову и(х). В этом множестве

151 _ ( п =

элементов. Несмотря на то, что нам не известны вероятности последовательностей из множества 5, мы можем сказать точно, что все они равны между собой (в силу независимости выбора отдельных букв сообщения). Зададим на множестве 5 лексикографический порядок Вычислим номер данного конкретного блока х внутри упорядоченного множества 5 с помощью быстрого алгоритма нумерации сочетаний (глава 3). Обозначим этот номер через и>(£). Разобьем множество 5 на непересекающиеся подмножества 5о, £1, .. ■, с числами элементов, равными различным степеням двойки (например, если |5| = 21, то получаем три подмножества с числами элементов 16, 4 и 1).' По ш{х) определим, какому подмножеству принадлежит х (обозначим номер

такого подмножества через v(x)), и найдем номер х внутри данного подмножества (обозначим этот номер через w(x)) Замечательно то, что w{x) — это последовательность равновероятных и независимых нулей и единиц. Действительно, w(x) — это номер одной из равновероятных последовательностей букв в подмножестве из 2Ь элементов (для некоторого b). Номера всех таких последовательностей — это всевозможные последовательности из Ь двоичных цифр. Но если все последовательности из Ь двоичных цифр равновероятны, то отдельные символы равновероятны и независимы.

Обрабатывая описанным образом последовательные блоки, мы представляем сообщение в виде u(xi)v(xi)w(xi)u(x2)v(x2)w(x2)....

Теперь перейдем к описанию процесса шифрования преобразованного сообщения. Слова и{-) и v(-) мы оставляем в открытом виде. Шифруются только слова w{-). В качестве шифра можно, например, использовать побитовое сложение по модулю 2 с периодически продолженным ключом. Для описания этого шифра удобно занумеровать символы слов w(-) подряд и обозначить их через W1W2W3 .... Тогда шифрование проводится по формуле гг — адгфкг шоа я. В результате применения описанного метода мы зашифровали сообщение следующим образом:

XiX2...Xt —► у = u{xi)v{xi)z{xi)u(x2)v(x2)z{x2)... . (2)

По построению алгоритма ясно, что из правой части (2) можно восстановить сообщение, если знать к.

В работе приводится доказательство того, что полученный шифр строго идеален и исследуются его основные свойства. Показано (теорема 4.3), что для предложенного шифра с длиной блока п время шифрования и дешифрования, отнесенное на один символ, растет как 0(log3nloglogr?), а размер памяти шифратора и дешифратора растет как O(nlogn) при увеличении п. Эта сложность экспоненциально ниже, чем у ранее известных методов, что открывает дорогу к практическому использованию разработанного метода. Показано также (утверждение 4 2 и теорема 4.4), что "почти вся" информация сообщения содержится в шифруемых компонентах кода.

Другая конструкция строго идеальной системы базируется на универсальном омофонном коде. Пусть дан тот же источник с неизвестной статистикой. Будем так же разбивать сообщение источника на блоки символов длины п, подсчитывать количество индивидуальных букв в блоке и формировать слово и{х), кодирующее последовательность счетчиков букв. Однако, вместо

вычисления номера сочетаний мы будем строить омофонный код для последовательности символов блока на основании их достоверных (faithful) вероятностей. Чтобы показать, как вычисляются эти вероятности, рассмотрим пример блока х ~ ЪсЪаса в алфавите А = {а, Ь, с}. Покажем распределения вероятностей для каждого символа сообщения:

па = 2, щ = 2, пс — 2;

х! : р(а) = 2/6, р(Ъ) = 2/6, р(с) - 2/6;

х2 : р(а) = 2/5, р(Ь) = 1/5, р(с) = 2/5;

хз : Р(а) = 2/4, р(Ь) = 1/4, р(с) = 1/4;

х4: р(а) = 2/3, р(Ь) = О, р(с) = 1/3;

х5: р(а) = 1/2, р(Ь)=0, р(с) = 1/2;

х6 : р(а) = 1, р(Ь) = 0, р(с) = 0.

Знаменатель вероятностей показывает, сколько всего символов осталось, начиная с текущего, а числитель — сколько осталось данных букв. Ясно, что эти распределения легко вычисляются. Отметим, что алгоритм нумерации сочетаний, построенный в третьей главе, фактически использует такие же распределения для символов. Поэтому омофонный код, кодирующий символы блока на основании указанных достоверных вероятностей, можно назвать «рандомизированной нумерацией». Преимущество омофонного кода состоит в том, что он вычисляется гораздо быстрее. Обозначим построенный омофонный код через ит(х). Тогда все сообщение представляется в виде u(xi)u>r(xx)u(x2)u>r(x2).... Как и ранее, слова и(хг) остаются в открытом виде, а слова шг(хг) шифруются путем сложения с периодически продолженным ключом. Омофонный код гарантирует, что последовательность слов шг(хг) состоит из равновероятных и независимых нулей и единиц, что обеспечивает строгую идеальность шифра.

Предложенные во второй главе алгоритмы АКРИ и АКФС могут с успехом использоваться для кодирования сообщений по описанной схеме. В этом случае время шифрования и дешифрования, отнесенное на один символ, растет как О (log п log log n log log log n), размер памяти шифратора растет как 0(п), а дешифратора — как О (log п) при п —> оо. Более того, если величина log п остается в пределах машинного слова, то время, затрачиваемое на один символ, остается постоянным с ростом п. Другие основные свойства схемы практически совпадают со свойствами, описанными для первой конструкции строго идеальной системы.

В пятой главе ставится задача статистического тестирования случайных последовательностей, предлагаются новые методы, приводятся данные экспериментального сравнения предложенных методов с лучшими известными тестами; описывается схема применения предложенных тестов к анализу блоковых шифров, приводятся данные экспериментальных исследований

Случайные и псевдослучайные числа находят самое широкое применение в криптографических системах, что, в частности, демонстрировалось в предыдущих главах. Это делает актуальной задачу построения эффективных статистических тестов, предназначенных для выявления возможных отклонений от случайности. Так, Национальный институт стандартов и технологий США (№8Т) недавно провел исследование известных статистических тестов для проверки случайных и псевдослучайных чисел В ходе этого исследования были выделены 16 методов, которые МБТ рекомендует для применения в криптографии.

В настоящей работе показано, что методы универсального и адаптивного кодирования, служившие в предыдущих главах основой для построения теоретически стойких криптосистем, могут быть использованы для решения задачи тестирования последовательностей случайных чисел. Таким образом продемонстрирована взаимосвязь между получением случайности и проверкой на случайность. Приведены данные экспериментов, показывающие, что новые статистические тесты, построенные на базе универсальных и адаптивных кодов, превосходят по мощности все 16 методов, рекомендованных ШБТ.

В качестве одного из приложений новых тестов рассмотрена задача статистического криптоанализа блоковых шифров, демонстрирующая еще одну взаимосвязь между разными разделами криптографии Показано, что процесс работы блоковых шифров может быть представлен в виде последовательности простых шагов, постепенно увеличивающих степень «случайности» данных. На основе этого феномена построена градиентная статистическая атака на шифр. В качестве объекта экспериментального исследования предложенной атаки был взят шифр 11С5 Приведены экспериментальные данные, показывающие, что зашифрованная последовательность довольно надежно отличается от случайной до восьмого раунда и статистические тесты способны различать правильный и неправильные подключи на основе анализа «случайности» декодированной последовательности.

В заключении делаются основные выводы по диссертационной работе В приложении приводятся основные блоковые шифры, используемые в

качестве шифраторов и дешифраторов в предлагаемых идеальных и строго идеальных криптосистемах- ГОСТ 28147-89, 11С6 и 11упс1ас1 (АЕБ).

ОСНОВНЫЕ ЗАКЛЮЧЕНИЯ И ВЫВОДЫ

1 Для решения задачи построения идеальных криптосистем и повышения практической стойкости шифров за счет уменьшения расстояния единственности предложена конструкция кода на порядок более эффективная как по времени, так и по объему памяти, чем ранее известные: сложность кодирования и декодирования при больших размерах алфавита источника N снижена с уровня O(NlogN) до уровня О (log2 N) битовых операций; объем памяти кодера и декодера снижен с 0(1/г) до О (log (1 /г)) бит при избыточности г —» 0. Получена аналитическая верхняя оценка избыточности арифметического кодирования

rc < (N + 1)(т + loge) •

где N — размер алфавита источника, т — максимальная длина чисел, представляющих вероятности символов источника, t — длина регистров арифметического кодера. Показано, что в адаптивной схеме со скользящим окном при определенном выборе параметров кодера избыточность удовлетворяет неравенству

N+1

Г° < w + N'

где w — размер окна.

2. Для решения задачи построения идеальных и строго идеальных криптосистем предложено два эффективных метода омофонного кодировав ния, названных арифметическое кодирование с разделением интервала (АКРИ) и арифметическое кодирование с фиктивными символами (АКФС), более эффективных, чем ранее известные, обеспечивающих полную рандомизацию сообщений при заданном произвольно низком их растяжении (избыточности по входу) е. Оба метода позволяют также получать произвольно низкие значения количества расходуемых случайных бит г] и характеризуются следующими оценками объема памяти

РОС НАЦИОНАЛЬНАЯ БИБЛИОТЕКА I С. Петербург ) Ч 09 МО акт ,

33 . *

S и времени Т-

S = 0(log(l/e)),

Т = 0(log(l/е) log log(l/е) log log log(l/e)), г) < 2e, e —» 0.

3. Для омофонных кодеров разработаны асимптотически оптимальные методы генерации произвольно распределенных случайных величин, достигающие произвольно малой потери (е) входных случайных символов при логарифмическом росте объема памяти и почти логарифмическом росте времени (в расчете на одну получаемую случайную переменную), что на порядок меньше, чем для лучших известных методов. Показано, что можно достичь потребления случайных бит на уровне 2е бит на символ источника без увеличения порядка сложности кодеров. Предложена схема преобразования распределения X в распределение Y, имеющая эффективность

E(m) H(Y) lim - + 6,

n—00 п Н{Х)

где Е(т)/п есть среднее число выходных переменных, получаемых из одной входной, причем потеря е может быть сделана сколь угодно малой при объеме памяти S и времени Т

S = О (log(l/e)), Т = 0 (log(l/e)loglog(l/e)logloglog(l/e)), что экспоненциально меньше, чем у известных ранее методов.

4. Для решения задач выделения случайности (улучшения физических генераторов случайных чисел) и построения строго идеальных систем построен алгоритм быстрой нумерации сочетаний в произвольном конечном алфавите источника, который требует объема памяти O(nlogn) бит при трудоемкости кодирования и декодирования 0(log3nloglogn) битовых операций (в пересчете на один символ источника), что на порядок меньше, чем у ранее известных методов.

5. Известный со времен Шеннона подход к построению строго идеальных криптосистем требовал экспоненциального по длине сообщения роста трудоемкости и поэтому был не реализуем. На основе нумерации сочетаний для источника без памяти с неизвестной статистикой построена строго идеальная криптосистема неэкспоненциальной трудоемкости.

Для предложенного метода с длиной блока п время шифрования и дешифрования, отнесенное на один символ, растет как 0(log3nloglogn), а размер памяти шифратора и дешифратора растет как 0(п log п) при увеличении п

6 Омофонные коды обеспечивают полную рандомизацию сообщений, что необходимо для построения идеальных криптосистем, но, как считалось ранее, применимы только при известной статистике источника. Предложен метод построения идеальной криптосистемы на основе универсального омофонного кодирования Для предложенного метода с длиной блока п время шифрования и дешифрования, отнесенное на один символ, растет как О (log п log log п log log log n), а размеры памяти шифратора и дешифратора растут соответственно как 0(п) и O(logn) при п —* ос. Более того, показано, что в достаточно широком диапазоне значений основных параметров время, затрачиваемое на один символ, остается постоянным

7. Для решения задачи верификации разработанных методов, применяемых к реальным источникам информации, предложены методы статистического тестирования значительно более мощные, чем ранее известные. Предложена схема применения этих методов для анализа блоковых шифров. Приведенные экспериментальные данные подтверждают основные предположения о статистических свойствах шифров и о возможности реализации градиентной статистической атаки. Показана способность статистических тестов различать правильный и неправильные подключи на основе анализа «случайности» декодированной последовательности.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

Монография

Рябко Б. Я., Фионов А. Н. Основы современной криптографии для специалистов в информационных технологиях - М.: Научный мир, 2004. -173 с.

Статьи и доклады на конференциях

1. Ryabko В. Y., Fionov А. N. A fast and efficient homophomc coding algorithm // Algorithms and Computation - Berlin: Springer. 1996. - P 427-438 (Lecture Notes m Computer Science; V. 1178).

2. Фионов A.H. Быстрый метод полной рандомизации сообщений // Рос- • сийская научно-техн. конф "Информатика и проблемы телекоммуникаций". - Новосибирск, 1996. - Т 1. - С 70.

3. Фионов А. Н. Эффективный метод рандомизации сообщений на основе арифметического кодирования // Дискретный анализ и исследование операций. - 1997. - Т. 4, № 2 - С. 51-74.

4 Рябко Б. Я., Федотов А. М., Фионов А. Н. Надежные системы защиты электронных публикаций, базирующиеся на эффективном омо-фонном кодировании // Вычислительные технологии. - 1997 - Т. 2, № 3. - С. 68-72.

•5 Фионов А. Н. Эффективная рандомизация сообщений на основе арифметического кодирования // Международная научно-техн конф. "Информатика и проблемы телекоммуникаций". - Новосибирск, 1997. - С. 157-158.

6. Ryabko В. Ya., Fionov А. N. Homophonic coding with logarithmic memory size // Algorithms and Computation. - Berlin: Springer, 1997. P. 253-262 (Lecture Notes in Computer Science; V 1350).

7. Рябко Б. Я., Фионов А. Н. Быстрый метод полной рандомизации сообщений // Проблемы передачи информации - 1997. - Т. 33, № 3. -С. 3-14.

8. Ryabko В., Fionov A. Decreasing redundancy of homophonic coding // 1997 IEEE International Symposium on Information Theory (ISIT 1997) -Ulm, Germany, July 1997. - P. 94.

9. Рябко Б. Я., Федотов А. М., Фионов А. Н. Современные средства криптографической защиты информации в сетях передачи данных // Международная конф "Современные информационные технологии". -Новосибирск, 1998. - С. 42-44.

10. Рябко Б. Я., Фионов А. Н., Федотов А. М. Конфиденциальность взаимодействий в открытых информационных сетях // Международный семинар "Перспективы развития современных средств и систем телекоммуникаций". - Новосибирск. 1998 - С. 38-42.

11. Fionov А. N. Computationally efficient randomization of messages // Международная Сибирская конф. по исслед. операций. - Новосибирск, 1998. - С. 159.

12. Ryabko В. Ya., Fionov А. N. Efficient algorithm of adaptive arithmetic coding // Международная Сибирская конф по исслед операций. - Новосибирск, 1998. - С. 151.

13. Fionov А. N. Using homophonic decoding for random number generation // Международный семинар "Распределенная обработка информации". - Новосибирск, 1998. - С. 63-67.

14. Ryabko В., Fionov A. Fast homophonic coding with logarithmic memory size // 1998 IEEE International Symposium on Information Theory (ISIT 1998). - Cambridge, MA, USA, August 1998. - P. 52.

15. Ryabko В., Fionov A. Efficient homophonic coding //IEEE Transactions on Information Theory. - 1999. - V. 45, N. 6. - P. 2083-2091

16. Рябко Б. Я., Фионов А. Н. Эффективный метод адаптивного арифметического кодирования для источников с большими алфавитами // Проблемы передачи информации. - 1999 - Т. 35, № 4. - С 1-14

17. Ryabko В., Fionov A. Fast and space-efficient adaptive arithmetic coding // Cryptography and Coding - Berlin: Springer, 1999. - P. 270-279 (Lecture Notes in Computer Science; V. 1746).

18. Фионов A. H. Составные коды для криптосистем // Международный семинар "Перспективы развития современных средств и систем телекоммуникаций". - Новосибирск, 2000. - С. 74-79.

19. Fionov A. Random number generation via homophonic coding // 2000 IEEE International Symposium on Information Theory (ISIT 2000). - Sorrento, Italy, June 25-30, 2000. - P. 354.

20. Фионов А.Н. Стойкий потоковый шифр на базе рандомизированных кодов // Международная научно-техн конф "Информатика и проблемы телекоммуникаций". - Новосибирск, 2001 - С. 40-41

21. Fionov A. Universal homophonic coding / / 2001 IEEE International Symposium on Information Theory (ISIT 2001). - Washington, DC, USA, June 24-29, 2001. - P 116

22 Ryabko В., Fionov A. Efficient algorithm for strongly ideal cipher // Workshop on Computer Science and Information Technologies (CSIT 2001). - Ufa, Russia, 2001

23. Ryabko В., Fionov A. Adaptive arithmetic coding for changing statistics: randomization vs space // 2002 IEEE International Symposium on Information Theory (ISIT 2002) - Lausanne. Switzerland. June 24 - June 29, 2002. - P. 116.

24. Фионов A. H. Построение омофонных кодов при неизвестной статистике источника сообщений / / Международный семинар "Перспективы развития современных средств и систем телекоммуникаций'' - Санкт-Петербург, 30 июня - 4 июля, 2002 - С 83-86.

25. Ryabko В., Fionov A. Efficient algorithm for stiongly ideal cipher // 2nd IMA Conference on Mathematics in Communication - Lancaster University, UK, 16-18 December 2002.

26. Рябко Б. Я., Фионов А. Н. Перспективы применения криптографических систем // Электросвязь - 2003 - № 8. - С. 28-31.

27. Fionov A. Arithmetic homophonic coding with dummy symbols //' 2004 IEEE International Symposium on Information Theory (ISIT 2004). - Chicago, Illinois, USA, June 27 - July 2, 2004 - P. 129.

28. Ryabko B. Ya., Fionov A. N., Monarev V. A., Shokin Yu. I.

Using information theory approach to randomness testing // 2nd Russian-German Advanced Research Workshop on Computational Science and High Performance Computing. - Stuttgart, Germany, March 14 - 16, 2005 -http: / /www .hlrs.de.

Андрей Николаевич Фионов

ЭФФЕКТИВНЫЕ МЕТОДЫ ПОСТРОЕНИЯ ИДЕАЛЬНЫХ КРИПТОГРАФИЧЕСКИХ СИСТЕМ ЗАЩИТЫ ИНФОРМАЦИИ

Автореферат

Подписано в печать 13.09.2005, формат бумаги 60x84/16, отпечатано на ризографе, шрифт №10, изд. л. 2,0, заказ № 76, тираж 100. СибГУТИ 630102, Новосибирск, ул. Кирова, 86

»

I

I

I

s

»18852

РНБ Русский фонд

2006-4 15503

Введение.

1. Методы эффективного кодирования для повышения расстояния единственности шифров.

1.1. Введение.

1.2. Теория систем с совершенной секретностью.

1.3. Соотношение избыточностей по входу и выходу

1.4. Основные подходы к потроению метода эффективного кодирования

1.4.1. Быстрое кодирование с использованием скользящего окна

1.4.2. Использование мнимого скользящего окна для уменьшения объема памяти кодера и декодера.

1.4.3. Кодирование марковских источников

1.4.4. Избыточность арифметического кодирования.

Выводы.

2. Омофонное кодирование.

2.1. Обзор побуквенных омофонных кодов.

2.2. Арифметическое кодирование с разделением интервала.

2.2.1. Основная идея метода.

2.2.2. Описание алгоритма кодирования.

2.2.3. Свойства метода.

2.3. Арифметическое кодирование с фиктивным символом.

2.3.1. Описание алгоритма.

2.3.2. Оценка избыточности по входу. щ 2.3.3. Потребление внешних случайных бит.

2.3.4. Вычислительная сложность метода

Выводы.

3. Выделение случайности и генерация случайных величин

3.1. Задачи, возникающие при использовании физических генераторов случайных чисел

3.2. Эффективная нумерация множеств

3.2.1. Постановка задачи.

• 3.2.2. Нумерация сочетаний.

3.2.3. Быстрый алгоритм нумерации сочетаний.

3.3. Эффективная генерация произвольно распределенных случай® ных величин

3.3.1. Постановка задачи.

3.3.2. Быстрая генерация случайных величин для омофонных кодеров

3.3.3. Генерация случайных величин на основе омофонного декодирования щ 3.3.4. Уменьшение числа случайных бит, используемых в омофонном кодировании.

3.3.5. Эффективное преобразование вероятностностных распределений

Выводы.

4. Строго идеальные криптосистемы.

4.1. Основные определения и постановка задачи.

4.2. Конструкция идеальной криптосистемы на базе нумерационного кода.

4.2.1. Основная идея и свойства метода. а 4.2.2. Описание общего алгоритма и его свойства.

4.3. Построение строго идеальной системы на базе универсального омофонного кода.

4.3.1. Введение.

4.3.2. Основная идея.

4.3.3. Общая конструкция строго идеальной системы.

Выводы.

5. Статистические тесты и атака на блоковые шифры.

5.1. Тесты для проверки генераторов случайных и псевдослучайных чисел.

5.1.1. Тест «Стопка книг»

5.1.2. Порядковый тест.

5.1.3. Экспериментальные исследования.

5.2. Статистическая атака на блоковые шифры.

Выводы.

Основные заключения и выводы.

Актуальность проблемы Одной из важных областей исследований в системах, сетях и устройствах телекоммуникаций является исследование и разработка новых методов защиты информации и обеспечение информационной безопасности этих систем, сетей и устройств. В свою очередь, защита информации в значительной степени базируется на использовании криптографических методов, связанных с шифрованием данных. Наибольшее практическое применение для шифрования информации в настоящее время находят симметричные системы, построенные на основе блоковых или потоковых шифров с секретным ключом. В этих системах абоненты взаимодействуют по открытым каналам связи, доступным некоторому противнику. Каждая пара абонентов имеет общий секретный ключ, который используется для шифрования передаваемых данных. Предполагается, что секретные ключи передаются по закрытому (или защищенному) каналу, имеющему значительно меньшую пропускную способность по сравнению с открытым каналом. В зависимости от использованных методов построения эти системы можно разделить на два больших класса: вычислительно стойкие системы и безусловно стойкие системы. Разница между этими классами проявляется при рассмотрении атаки по шифротексту, когда криптоаналитик (противник) имеет перехваченный шифротекст (криптограмму) и пытается восстановить сообщение и использованный секретный ключ.

Большинство из практически используемых в настоящее время криптосистем обладают лишь вычислительной стойкостью. Это означает, например, что шифры могут в принципе быть взломаны путем полного перебора ключей. Но что более важно отметить, пока никому не удалось найти каких-либо строгих доказательств того, что для тех или иных вычислительно стойких систем не существует более эффективных алгоритмов взлома, чем перебор ключей. Более того, история криптоанализа свидетельствует о том, что для многих систем, казавшихся надежными, со временем такие более эффективные алгоритмы взлома находятся, а некоторые системы в результате оказываются настолько нестойкими, что выходят из практического использования. Основная проблема здесь состоит в том, что при отсутствии математически строгих доказательств стойкости никто не может быть уверен, что противник уже сегодня не располагает эффективными методами, направленными против используемых криптосистем. Если говорить о перспективах применения вычислительно стойких систем, то следует также отметить, что большую угрозу для таких систем представляют квантовые компьютеры. Сегодня квантовые компьютеры изучаются в основном на уровне математических моделей, хотя имеются сведения о первых практических реализациях с ограниченными вычислительными возможностями (скажем, реализующие 7-битовые квантовые алгоритмы). В многочисленных работах по квантовым компьютерам показано, что с их помощью многие криптоаналитические задачи, практически нерешаемые в традиционных вычислительных системах, могут быть быстро решены. Таким образом, если сегодня вычислительно стойкие системы в целом удовлетворительно решают возлагаемые на них задачи по защите информации, то ситуация может резко измениться в ближайшем будущем, если квантовые компьютеры станут реальностью или будут открыты новые эффективные методы криптоанализа.

В противоположность вычислительно стойким системам, безусловно стойкие системы гарантируют невозможность вскрытия шифров (при соблюдении некоторых условий, связанных с их корректным применением), независимо от вычислительных возможностей криптоаналитика. Это свойство делает весьма актуальной задачу эффективных методов построения таких систем. Основы теории стойкости криптосистем были заложены в работе К. Шеннона [20]. Отметим здесь три основные понятия, введенные Шенноном: совершенная криптосистема, расстояние единственности шифра и идеальная криптосистема. Формальные определения этих понятий будут даны в соответствующих главах, а здесь ограничимся их неформальным рассмотрением, которое позволит судить о стоящих перед нами задачах. Совершенная криптосистема предполагает, что независимо от объема перехваченного шифротекста противник не получает никакой информации о сообщении. Примером совершенной системы является шифр Вернама. В этом шифре длина секретного ключа равна длине сообщения и ключ используется только один раз. Можно сказать, что шифр Вернама применим в системах, где пропускная способность открытого и закрытого каналов одинакова. Однако, на практике, как указывалось выше, пропускная способность закрытого канала часто много меньше пропускной способности открытого канала. В таких случаях секретные ключи намного короче передаваемых сообщений и существует некоторая «критическая» длина шифротекста, названная расстоянием единственности шифра, при которой криптоаналитик может определить ключ почти однозначно. Шеннон показал, что расстояние единственности пропорционально длине ключа и обратно пропорционально избыточности сообщения. Ключ может обновляться (или порождаться) с некоторой скоростью, определяемой пропускной способностью закрытого канала. Если ключ обновляется быстрее, чем достигается расстояние единственности, то криптоаналитик не может получить единственного решения криптограммы, т.е. не может вскрыть шифр. Такую систему Шеннон назвал идеальной. Если избыточность сообщения удается сделать равной нулю, то расстояние единственности становится бесконечным и мы получаем строго идеальную криптосистему. В строго идеальной криптосистеме криптоаналитик всегда получает множество допустимых решений криптограммы соответствующее множеству возможных ключей. Подчеркнем, что в случае когда расстояние единственности больше длины сообщения или криптосистема строго идеальна, шифр оказывается невскрываемым.

Основным способом построения невскрываемых шифров при использовании коротких ключей является кодирование сообщений перед шифрованием. Можно выделить два основных подхода к такому кодированию. Первый заключается в применении традиционного сжатия данных для уменьшения избыточности сообщения и, следовательно, увеличения расстояния единственности шифра. Особенностью этого подхода является то, что он может быть распространен на большое множество моделей источников информации. При этом следует иметь в виду, что в методах кодирования избыточность традиционно определяется как разность между средней длиной кодового слова и энтропией на символ источника (мы называем эту разность избыточностью по входу). Однако для оценки расстояния единственности шифра необходима другая величина, определяемая для двоичного кода как величина отклонения средней энтропии одного кодового символа от единицы (т.е. ее максимально возможного значения). Мы называем эту величину избыточностью по выходу. Как правило, применяемые методы сжатия должны быть характеризованы не эвристическими или экспериментальными, а теоретически доказанными показателями избыточности, чтобы гарантировать определенную величину расстояния единственности. Естественная постановка задачи разработки алгоритмов сжатия сводится к минимизации сложности кодера и декодера при достижении заданной произвольно малой избыточности на символ сообщения.

Второй основной подход состоит в построении специальных кодов или, точнее, преобразований сообщений перед шифрованием. В рамках этого подхода может ставиться задача достижения бесконечного расстояния единственности шифра или, другими словами, построения строго идеальных криптосистем. Получаемые коды не обязательно должны «сжимать» сообщение, как раз наоборот, такие коды часто могут быть построены при условии «растяжения» сообщения методами рандомизации. Реализация этого подхода, предлагаемая в настоящей работе, основана на методах нумерационного и омофонного кодирования. Получаемый код состоит из нескольких отделимых компонент, одна из которых неотличима от последовательности случайных и независимых символов. Именно эта компонента кода подлежит шифрованию, в то время как другие компоненты могут передаваться в открытом виде. Говоря неформально, в отличие от схемы со сжатием данных, здесь шифруется не весь код, а отдельные его части, имеющие наибольшую «степень случайности». Данный подход более эффективен, чем первый, с точки зрения свойств получаемой криптосистемы. Однако специальные методы кодирования могут быть не столь эффективны с вычислительной точки зрения при сложных моделях источников.

Решение задач построения безусловно стойких криптосистем в рамках двух указанных основных подходов тесно связано со многими задачами в других разделах криптографии, теории кодирования источников и теории информации в целом. Так, например, эффективные конструкции, разработанные для методов сжатия данных, с успехом применяются при построении специальных кодов на основе нумерационного и омофонного кодирования. В свою очередь, омофонное и нумерационное кодирование тесно связано с задачей генерации случайных величин и выделения случайности. Необходимость проверки качества получаемых кодов требует рассмотрения задач статистического тестирования случайных последовательностей. Вообще, решение основной поставленной задачи (построение идеальных систем) привело к необходимости или сделало возможным решение многих смежных задач, что и отражено в представленной работе.

Проблемы криптографии привлекают внимание многих исследователей. Начало научного изучения предмета было положено в работах К. Шеннона (Shannon, С.) в конце 40-х годов XX века, но наиболее активные (открытые) исследования начались в 70-х годах после выхода в свет работ У. Диффи (Diffie, W.), Р. Меркля (Mercle, R.) и М. Хеллмана (Hellman, М.), а также J1. Адлемана (Adleman, L.), Т. Эль-Гамаля (ElGamal, Т.), Р. Ривеста

Rivest, R.), А. Шамира (Shamir, А.) и многих других. Значительный вклад в развитие современной криптографии внесли (открытые) работы Э.М. Габи-дулина, Б.Я. Рябко, В.М. Сидельникова и целого ряда других отечественных ученых. Вопросы безусловной стойкости криптосистем были впервые рассмотрены К. Шенноном и затем, спустя несколько десятилетий, изучались в работах Р. Альсведе (Ahlswede, R.), Дж.Л. Месси (Massey, J.L.), Б.Я. Рябко, Ю.М. Штарькова и др. Омофонными кодами занимались такие исследователи как К. Гюнтер (Gunther, 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.), П. Элайесу и др.

В качестве основного критерия, по которому можно сравнивать различные методы построения теоретически стойких систем и связанных с ними алгоритмов, может выступать сложность реализации, рассматриваемая как функция некоторого целевого параметра. Для идеальных систем целевым параметром может служить расстояние единственности шифра или тесно связанная с ним избыточность кода. Для строго идеальных систем это может быть размер обрабатываемого блока или сообщения. Для методов выделения случайности и генерации случайных величин — количество расходуемых символов входной последовательности. Сложность измеряется количеством битовых операций, которые необходимо выполнять для достижения заданного значения целевого параметра (для краткости эта величина иногда называется временем работы или трудоемкостью алгоритма), и объемом памяти в битах, который требуется для выполнения алгоритма. Для удобства сравнения трудоемкостей они, как правило, приводятся в расчете на один символ.

Следует отметить, что до появления работ професора Б.Я. Рябко и автора настоящей диссертации известные конструкции строго идеальных криптосистем обладали экспоненциальной трудоемкостью (по длине сообщения), что делало их неприменимыми на практике. Оставались также проблемы сложности методов в области омофонного, нумерационного, адаптивного кодирования и в других смежных областях, ограничивающие их практическое применение, в частности, построение идеальных криптосистем.

Цель работы состоит в следующем:

1. Построение идеальных криптосистем на основе универсальных и адаптивных методов сжатия данных, обладающих на порядок более низкой сложностью, чем ранее известные, при обеспечении заданной произвольно низкой скорости порождения ключа.

2. Построение строго идеальных криптосистем на основе специальных методов преобразования сообщений, обладающих неэкспоненциальной трудоемкостью.

3. Разработка методов статистического тестирования для экспериментальной проверки качества полученных криптосистем, имеющих мощность существенно большую, чем ранее известные тесты.

Объектом исследований в предлагаемой работе являются криптосистемы, обладающие безусловной стойкостью. Предмет исследований состоит в поиске методов реализации безусловно стойких систем, на порядок более эффективных, чем ранее известные.

Состояние проблемы Известные конструкции строго идеальных криптосистем обладают экспоненциальной по длине сообщения трудоемкостью и, следовательно, практически не реализуемы. В то же время известно множество методов кодирования, из которых необходимо особо выделить омо-фонные и адаптивные коды, пригодных для построения идеальных систем за счет снижения расстояния единственности. Сложность предложенных другими авторами омофонных кодов, рассматриваемая как функция избыточности и числа используемых при кодировании случайных символов, растет экспоненциально, что затрудняет практическое применение этих кодов. Эффективных адаптивных кодов известно достаточно много, однако и здесь имеется резерв для снижения сложности при достижении заданной произвольно малой избыточности, прежде всего, за счет уменьшения порядка трудоемкости обработки больших алфавитов источников, а также за счет экономии памяти кодера и декодера при реализации адаптивных моделей. Кроме того, многие адаптивные коды характеризованы лишь эвристическими или экспериментальными оценками, в то время как для криптографических применений требуются строго доказанные теоретические оценки. Остановимся также на характеристике ряда задач, являющихся вспомогательными с точки зрения достижения поставленных целей. Известный метод Элайеса для выделения случайности обладал экспоненциальной сложностью, однако Рябко и Мачи-кина предложили эффективную реализацию этого метода для двоичных алфавитов источника. Наилучший метод генерации произвольно распределенных случайных величин (интервальный алгоритм Хана и Хоши) требует линейного роста памяти и примерно квадратичного роста времени при увеличении длины получаемой последовательности случайных величин. Такими же характеристиками сложности обладает построенный на базе интервального алгоритма метод преобразования распределений случайных величин. Известные статистические тесты, например, рекомендованные для практического использования в системах защиты информации Национальным институтом стандартов и технологий США, для обнаружения отклонений от случайности в «почти» случайных последовательностях, получаемых на выходах низкоизбыточных кодеров, часто требуют объемов выборки значительно превосходящих ресурсы памяти компьютеров, что делает эти тесты неприменимыми.

Задачи исследования Для достижения указанных целей с учетом изложенного состояния проблемы в рамках диссертационной работы решаются следующие задачи.

1. Определение влияния различных типов избыточности на стойкость криптосистем, включающих сжатие и рандомизацию сообщений.

2. Получение аналитической верхней оценки избыточности арифметического кода, как основного метода низкоизбыточного кодирования.

3. Построение алгоритма для выполнения операций с кумулятивными вероятностями в арифметическом кодере и декодере за менее чем линейное время при возрастающем размере алфавита источника и разработка структуры данных и алгоритма, позволяющих существенно снизить объем памяти кодера и декодера, требуемый для оценивания статистики источника с заданной точностью.

4. Разработка алгоритмов омофонного кодирования, характеризуемых линейной или меньшей сложностью и быстро адаптирующихся к меняющейся статистике источника.

5. Построение алгоритма нумерации сочетаний при произвольных алфавитах источника с линейно возрастающей сложностью при увеличении длины входной последовательности.

6. Построение методов генерации случайных величин, характеризуемых линейным или меньшим ростом сложности при минимизации количества расходуемых случайных бит и создание на их основе эффективных методов вероятностного выбора омофонов для омофонных кодеров.

7. Построение асимптотически оптимального метода преобразования распределений случайных величин, имеющего не более чем линейную сложность.

8. Разработка конструкций строго идеальных криптосистем неэкспоненциальной трудоемкости для источников с неизвестной статистикой.

9. Построение алгоритмов статистического тестирования случайных последовательностей, требующих существенно меньших объемов выборки, чем ранее известные и разработка эффективных схем применения статистических тестов к криптоанализу блоковых шифров.

Методы исследования В процессе исследований были использованы основные положения и методы теории информации, теории кодирования дискретных источников, теории сложности, теории вероятностей и эксперименты на ЭВМ.

Научная новизна результатов работы:

1. Получено соотношение между избыточностью по входу и избыточностью по выходу в криптосистеме, включающей сжатие и рандомизацию сообщений, что позволяет точно оценивать расстояние единственности для построения идеальных систем.

2. Получена аналитическая верхняя оценка избыточности арифметического кодирования, на основании которой предложен оптимальный выбор параметров кодера в адаптивной схеме со скользящим окном.

3. Построен алгоритм для выполнения операций с кумулятивными вероятностями в арифметическом кодере и декодере, требующий логарифмического времени при возрастающем размере алфавита источника и разработаны структура данных и алгоритм, позволяющие экспоненциально снизить объем памяти кодера и декодера, требуемый для оценивания статистики источника с заданной точностью.

4. Разработаны два алгоритма омофонного кодирования, названные «арифметическое кодирование с разделением интервала» (АКРИ) и «арифметическое кодирование с фиктивным символом» (АКФС), характеризуемые логарифмически растущим объемом памяти и почти логарифмически растущим временем, не требующие дополнительных вычислений при изменении статистики источника. При компьютерной реализации метод АКФС работает в несколько раз быстрее, но имеет большее значение избыточности по входу.

5. Построен алгоритм нумерации сочетаний для произвольного конечного алфавита источника, характеризуемый почти линейно возрастающей памятью и логарифмически-полиномиальным ростом времени при увеличении длины входной последовательности.

6. Построены два метода генерации случайных величин, базирующиеся на АКРИ и АКФС декодерах, характеризуемые логарифмическим ростом объема памяти и почти логарифмическим ростом времени вычислений при минимизации количества расходуемых случайных бит. На их основе построены методы вероятностного выбора омофонов для омофонных кодеров, сводящие расходование случайных символов до минимально заданного уровня без увеличения сложности кодеров. Кроме того, предложены быстрые методы выбора омофонов при отсутствии ограничений на количество расходуемых случайных бит, требующие в среднем лишь нескольких машинных операций для осуществления выбора.

7. Построен асимптотически оптимальный метод преобразования распределений случайных величин, имеющий логарифмическую сложность.

8. Разработаны и исследованы две базовые конструкции строго идеальных криптосистем линейной трудоемкости для источников с неизвестной статистикой. Первая конструкция базируется на нумерации сочетаний, вторая — на универсальном омофонном коде.

9. Построены алгоритмы статистического тестирования случайных последовательностей, превосходящие по мощности лучшие 16 тестов, рекомендованных Национальным институтом стандартов и технологий США в 2001 году. На основе разработанных статистических тестов предложена градиентная статистическая атака на блоковые шифры.

Практическая ценность полученных результатов:

1. Разработанные методы омофонного и адаптивного кодирования позволяют строить идеальные криптосистемы, имеющие существенно меньшую сложность, чем ранее известные.

2. Предложенные конструкции строго идеальных криптосистем могут быть легко реализованы на практике для большого класса источников информации.

3. Предложенные методы кодирования сообщений, примененные к произвольным источникам информации, позволяют существенно повысить надежность существующих шифров.

4. Полученные методы выделения случайности и генерации случайных величин позволяют на порядок повысить вычислительную эффективность использующих их систем при минимизации расходования входных случайных символов.

5. Разработанные конструкции кодов могут с успехом применяться в задачах сжатия информации для повышения эффективности систем сжатия.

6. Предложенные методы статистического тестирования, как наиболее мощные на сегодняшний день, могут использоваться для верификации и сертификации случайных последовательностей, получаемых в криптографии.

Реализация и внедрение результатов работы Основные результаты получены в рамках следующих государственных и международных программ:

• проекты, финансируемые Российским фондом фундаментальных исследований: 99-01-00586 "Построение эффективных алгоритмов для кодирования и прогнозирования источников информации и нумерации комбинаторных объектов", 99-07-90438 "Разработка параллельных средств анализа и организации функционирования суперВС с массовым параллелизмом, моделей и методов распараллеливания прикладных задач", 00-01-00672 "Разработка доказуемо стойких криптографических алгоритмов, основанных на эффективных методах кодирования источников информации", 03-01-00495 "Разработка универсальных кодов асимптотически минимальной сложности";

• международный проект INTAS-00-738 "Efficient source coding and related problems"; в рамках Программы фундаментальных и прикладных исследований вузов связи Российской Федерации "Фундаментальные аспекты новых информационных и ресурсосберегающих технологий"

• НИР "Построение эффективных методов сжатия данных и их применение для разработки доказуемо невскрываемых криптографических систем" (1999-2000),

• НИР "Временная оптимизация доказуемо стойких систем защиты информации" (2001); а также в рамках работ по проекту "Разработка эффективных методов сжатия больших объемов информации для применения в Интернете и других компьютерных сетях" (2002-2004), финансируемому Фондом фундаментальных исследований СибГУТИ.

Результаты диссертации используются в учебном процессе при чтении курсов "Основы криптографии", "Структуры и алгоритмы обработки данных", "Теория вычислительных процессов и систем", а также при выполнении дипломных проектов в СибГУТИ.

Апробация работы Основные результаты докладывались и обсуждались на следующих российских и международных конференциях:

• Международный семинар "Перспективы развития современных средств и систем телекоммуникаций" (Новосибирск, 2000).

• Международная научно-техническая конференция "Информатика и проблемы телекоммуникаций" (Новосибирск, 2001).

• Workshop on Computer Science and Information Technologies CSIT 2001 (Ufa, Russia, 2001).

• Международный семинар "Перспективы развития современных средств и систем телекоммуникаций" (Санкт-Петербург, 30 июня - 4 июля, 2002).

• 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%.

Основные положения, выносимые на защиту

1. Для решения задачи построения идеальных криптосистем и повышения практической стойкости шифров за счет уменьшения расстояния единственности предложена конструкция кода на порядок более эффективная как по времени, так и по объему памяти, чем ранее известные; аналитически определены все необходимые параметры, гарантирующие в конечном счете достижение любого заданного значения расстояния единственности шифра.

2. Для решения задачи построения идеальных и строго идеальных систем разработан класс методов омофонного кодирования, экспоненциально более эффективных, чем ранее известные, обеспечивающих полную рандомизацию сообщений при заданном произвольно низком их растяжении (избыточности по входу).

3. Для омофонных кодеров разработаны асимптотически оптимальные методы генерации произвольно распределенных случайных величин на порядок менее трудоемкие, чем ранее известные, и представляющие самостоятельный интерес для решения задач генерации и преобразования распределений случайных величин.

4. Для решения задач выделения случайности (улучшения физических генераторов случайных чисел) и построения строго идеальных систем построен алгоритм быстрой нумерации сочетаний в произвольном конечном алфавите источника, сложность которого на порядок меньше, чем у ранее известных методов.

5. Известный со времен Шеннона подход к построению строго идеальных криптосистем требовал экспоненциального по длине сообщения роста трудоемкости и поэтому был не реализуем. На основе нумерации сочетаний для источника без памяти с неизвестной статистикой построена строго идеальная криптосистема менее чем квадратичной трудоемкости, которая может быть практически реализована.

6. Омофонные коды обеспечивают полную рандомизацию сообщений, что необходимо для построения идеальных криптосистем, но, как считалось ранее, применимы только при известной статистике источника. Автором диссертационной работы показано, как применить омофонный код к сообщениям источника с неизвестной статистикой. В результате построена идеальная криптосистема с почти линейной трудоемкостью.

7. Для решения задачи верификации разработанных методов, применяемых к реальным источникам информации, предложены методы статистического тестирования значительно более мощные, чем ранее известные. Предложена схема применения этих методов для анализа блоковых шифров.

Структура и объем работы Диссертация состоит из введения, пяти глав, заключения, списка литературы и приложения. Диссертация содержит 241 страниц машинописного текста. Список литературы включает 108 наименований.

ОСНОВНЫЕ ЗАКЛЮЧЕНИЯ И ВЫВОДЫ

1. Для решения задачи построения идеальных криптосистем и повышения практической стойкости шифров за счет уменьшения расстояния единственности предложена конструкция кода на порядок более эффективная как по времени, так и по объему памяти, чем ранее известные: сложность кодирования и декодирования при больших размерах алфавита источника N снижена с уровня O(NlogN) до уровня 0(\og2 N) битовых операций; объем памяти кодера и декодера снижен с 0(1/г) до 0(log(l/r)) бит при избыточности г 0. Получена аналитическая верхняя оценка избыточности арифметического кодирования rc < (N + 1)(т + log е) • где N — размер алфавита источника, т — максимальная длина чисел, представляющих вероятности символов источника, t — длина регистров арифметического кодера. Показано, что в адаптивной схеме со скользящим окном при определенном выборе параметров кодера избыточность удовлетворяет неравенству

N + 1 w + N где w — размер окна.

2. Для решения задачи построения идеальных и строго идеальных криптосистем предложено два эффективных метода омофонного кодирования, названных арифметическое кодирование с разделением интервала (АКРИ) и арифметическое кодирование с фиктивными символами (АКФС), более эффективных, чем ранее известные, обеспечивающих полную рандомизацию сообщений при заданном произвольно низком их растяжении (избыточности по входу) е. Оба метода позволяют также получать произвольно низкие значения количества расходуемых случайных бит rj и характеризуются следующими оценками объема памяти S и времени Т:

S = 0(log(l/e)),

Т = 0(log(l/e) log log(l/e) log log log(l/e)),

77 < 2e, e 0.

3. Для омофонных кодеров разработаны асимптотически оптимальные методы генерации произвольно распределенных случайных величин, достигающие произвольно малой потери (е) входных случайных символов при логарифмическом росте объема памяти и почти логарифмическом росте времени (в расчете на одну получаемую случайную переменную), что на порядок меньше, чем для лучших известных методов. Показано, что можно достичь потребления случайных бит на уровне 2е бит на символ источника без увеличения порядка сложности кодеров. Предложена схема преобразования распределения X в распределение У, имеющая эффективность

Нт = ^Q- + 6, п-* 00 п где Е(тп)/п есть среднее число выходных переменных, получаемых из одной входной, причем потеря е может быть сделана сколь угодно малой при объеме памяти S и времени Т

S=0 (log(l/e)), Т = О (log(l/e) loglog(l/e) logloglog(l/e)), что экспоненциально меньше, чем у известных ранее методов.

4. Для решения задач выделения случайности (улучшения физических генераторов случайных чисел) и построения строго идеальных систем построен алгоритм быстрой нумерации сочетаний в произвольном конечном алфавите источника, который требует объема памяти 0(n log п) бит при трудоемкости кодирования и декодирования О (log3 п log log п) битовых операций (в пересчете на один символ источника), что на порядок меньше, чем у ранее известных методов.

5. Известный со времен Шеннона подход к построению строго идеальных криптосистем требовал экспоненциального по длине сообщения роста трудоемкости и поэтому был не реализуем. На основе нумерации сочетаний для источника без памяти с неизвестной статистикой построена строго идеальная криптосистема неэкспоненциальной трудоемкости. Для предложенного метода с длиной блока п время шифрования и дешифрования, отнесенное на один символ, растет как 0(log3 n log log п), а размер памяти шифратора и дешифратора растет как 0(п log п) при увеличении п.

6. Омофонные коды обеспечивают полную рандомизацию сообщений, что необходимо для построения идеальных криптосистем, но, как считалось ранее, применимы только при известной статистике источника. Предложен метод построения идеальной криптосистемы на основе универсального омофонного кодирования. Для предложенного метода с длиной блока п время шифрования и дешифрования, отнесенное на один символ, растет как О (log п log log п log log log n), а размеры памяти шифратора и дешифратора растут соответственно как О(п) и O(logn) при п —» оо. Более того, показано, что в достаточно широком диапазоне значений основных параметров время, затрачиваемое на один символ, остается постоянным.

7. Для решения задачи верификации разработанных методов, применяемых к реальным источникам информации, предложены методы статистического тестирования значительно более мощные, чем ранее известные. Предложена схема применения этих методов для анализа блоковых шифров. Приведенные экспериментальные данные подтверждают основные предположения о статистических свойствах шифров и о возможности реализации градиентной статистической атаки. Показана способность статистических тестов различать правильный и неправильные подключи на основе анализа «случайности» декодированной последовательности.

1. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. - 383 с.

2. Бабкин В. Ф. Метод универсального кодирования независимых сообщений неэкспоненциальной трудоемкости // Проблемы передачи информации. 1971. - Т. 7, № 4. - С. 13-21.

3. Введение в криптографию / Под общ. ред. В. В. Ященко. М.: МЦНМО: «ЧеРо», 2000. - 287 с.

4. Галлагер Р. Теория информации и надежная связь. М.: Советское радио, 1974. - 425 с.

5. ГОСТ 28147-89. Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования данных.

6. Кнут Д. Искусство программирования для ЭВМ. В 3-х томах. Т. 2. Получисленные алгоритмы. М.: Мир, 1977. - 724 с.

7. Кричевский Р. Е. Оптимальное кодирование источника на основе наблюдений // Проблемы передачи информации. 1975. - Т. 11, № 4. - С. 37-42.

8. Кричевский Р. Е. Сжатие и поиск информации. М.: Радио и связь, 1989.

9. Рябко Б. Я. Сжатие данных с помощью стопки книг // Проблемы передачи информации. 1980. - Т. 16, № 4. - С. 16-21.

10. Рябко Б. Я. Быстрый алгоритм адаптивного кодирования // Проблемы передачи информации. 1990. - Т. 26, № 4. - С. 24-37.

11. Рябко Б. Я. Эффективный метод кодирования источников информации, использующий алгоритм быстрого умножения // Проблемы передачи информации. 1995. - Т. 31, № 1. - С. 3-12.

12. Рябко Б. Я. Сжатие данных с помощью "мнимого скользящего окна" // Проблемы передачи информации. 1996. - Т. 32, № 2. - С. 22-30.

13. Рябко Б. Я. Быстрая нумерация комбинаторных объектов // Дискретная математика. 1998. - Т. 10, № 2. - С. 101-119.

14. Рябко Б. Я. Просто реализуемая идеальная криптографическая система // Проблемы передачи информации. 2000. - Т. 36, № 1. - С. 90-104.

15. Рябко Б. Я., Пестунов А. И. «Стопка книг» как новый статистический тест для случайных чисел // Проблемы передачи информации. -2004. Т. 40, № 1. - С. 73-78.

16. Рябко Б. Я., Стогниенко В. С., Шокин Ю. И. Адаптивный критерий хи-квадрат для различения близких гипотез при большом числе классов и его применение к некоторым задачам криптографии // Проблемы передачи информации. 2003. - Т. 30, № 2. - С. 53-62.

17. Трофимов В. К. Избыточность универсального кодирования произвольных марковских источников // Проблемы передачи информации. -1974. Т. 10, № 4. - С. 16-24. .

18. Феллер В. Введение в теорию вероятностей и ее приложения. В 2-х томах. М.: Мир, 1984. - Т 1. - 527 с.

19. Фитингоф Б. М. Оптимальное кодирование при неизвестной и меняющейся статистике сообщений // Проблемы передачи информации. 1966. -Т. 2, №2.-С. 3-11.

20. Шеннон К. Работы по теории информации и кибернетике. М.: ИЛ, 1963. - С. 333-369 (Теория связи в секретных системах).

21. Штарьков Ю. М. Универсальное последовательное кодирование отдельных сообщений // Проблемы передачи информации. 1987. - Т. 23, № 3. - С. 3-17.

22. Штарьков Ю. М. Некоторые теоретико-информационные задачи защиты дискретных данных // Проблемы передачи информации. 1994. -Т. 30, № 2. - С. 49-60.

23. Abrahams J. Generation of discrete distributions from biased coins // IEEE Transactions on Information Theory. 1996. - V. 42, № 5. - P. 1541-1546.

24. Ahlswede R. Remarks on Shannon's secrecy systems // Problems of Control and Information Theory. 1982. - V. 11, № 4. - P. 301-318.

25. Bell Т. C., Cleary J. G., Witten I. H. Text compression. Englewood Cliffs, NJ: Prentice Hall, Inc. - 1990.

26. Bentley J. L., Sleator D. D., Tarjan R. E. Wei V. K. A locally adaptive data compression scheme // Communications of the ACM. 1986. - V. 29, № 4. - P. 320-330.

27. Cleary J. G., Witten I. H. Data compression using adaptive coding and partial string matching // IEEE Transactions on Communications. 1984. -V. 32, №4. - P. 396-402.

28. Cleary J. G., Witten I. H. A comparison of enumerative and adaptive codes // IEEE TYansactions on Information Theory. 1984. - V. 30, №2. -P. 306-315.

29. Cover Т. M. Enumerative source encoding // IEEE Transactions on Information Theory. 1973. - V. 19, № 1. - P. 73-77.

30. Daemen J., Rijmen V. The Rijndael Block Cipher, см. http://csrc.nist.gov/encryption/aes/rijndael/.

31. Elias P. Minimax optimal universal codeword sets // Transactions of the IEEE. 1983. - V. 29, № 4. - P. 491-502.

32. Elias P. Interval and recency rank source encoding: two on-line adaptive variable-length schemes // TYansactions of the IEEE. 1987. - V. 33M. - P. 3-10.

33. FIPS 197. Advanced encryption standard, см. http://csrc.nist.gov/publications/.

34. Fitingof В., Waksman Z. Fuzed trees and some new approaches to source coding // IEEE TYansactions on Information Theory. 1988. V. 34, № 3. -P. 417-424.

35. Gehrmann Ch. An adaptive homophonic algorithm // 1993 IEEE Internationsl Symposium on Information Theory (ISIT 1993). San Antonio, 1993. - P. 280.

36. Gehrmann Ch. Remarks on theoretical treatments of secrecy systems // 7th Joint Swedish-Russian International Workshop on Information Theory. -St. Petersburg, June 1995. P. 84-88.

37. Goldwasser S., Bellare M. Lecture notes on cryptography, http://www-cse.ucsd.edu/users/mihir/crypto-lecnotes.html

38. Guazzo М. A general minimum-redundancy source-coding algorithm // IEEE Transactions on Information Theory. 1980. - V. 26, №1. - P. 1525.

39. Gunther Ch. G. A universal algorithm for homophonic coding // Advances in Cryptology Eurocrypt-88. Heidelberg and New York: Springer-Verlag, 1988. - P. 405-414 (Lecture Notes in Computer Science; V. 330).

40. Han T. S., Hoshi M. Interval algorithm for random number generation // IEEE Transactions on Information Theory. 1997. - V. 43, № 2. - P. 599-611.

41. Jelinek F. Probabilistic information theory. New York: McGraw-Hill, 1968. - P. 476-489.

42. Jendal H. N., Kuhn Y. J. В., Massey J. L. An information-theoretic treatment of homophonic substitution // Advances in Cryptology Eurocrypt-89. Berlin: Springer-Verlag, 1990. - P. 382-394 (Lecture Notes in Computer Science; V. 434).

43. Knuth D. E., Yao A. C. The complexity of nonuniform random number generation // Algorithms and Complexity: New Directions and Results, J. F. Traub Ed. New York: Academic Press, 1976. - P. 357-248.

44. Krichevsky R. Universal Compression and Retrieval. Dordrecht: Kluwer Academic Publishers, 1994.

45. Krichevsky R. E., Trofimov V. K. The performance of universal encoding // IEEE Transactions on Information Theory. 1981. - V. 27, № 2. - P. 199207.

46. Langdon G. G., Rissanen J. A simple general binary source code // IEEE Transactions on Information Theory. 1982. - V. 28, № 9. - P. 800-803.

47. Langdon G. G. An introduction to arithmetic coding // IBM J. Res. Dev. 1984. - V. 28, № 2. - P. 135-149.

48. Massey J. L. An introduction to contemporary cryptology // Proceedings of the IEEE. 1988. - V. 76. - P. 533-549.

49. Massey J. L. Some applications of source coding in cryptography // European Transactions on Telecommunications. 1994. - V. 5. - P. 421-429.

50. Menezes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography. CRC Press, 1996. - 661 p. http://www.cacr.math.uwaterloo.ca/hac/.

51. Moffat A. A note on the PPM data compression algorithm. Res. Rep. 88/7, Dep. Comput. Sci. Univ. of Melbourne. Australia, 1988.

52. Moffat A., Turpin A. Efficient construction of minimum-redundancy codes for large alphabets // IEEE Transactions on Information Theory. 1998. -V. 44, №4. - P. 1650-1657.

53. Moffat A., Neal R. M., Witten I. H. Arithmetic coding revisited // ACM Transactions on Information Systems. 1998. - V. 16, № 3. - P. 256-294.

54. Nisan N., Ta-Shma A. Extracting randomness: a survey and new constructions // Journal of Computing and System Science. 1999. V. 58, № 1. - P. 148-173.

55. Nisan N., Zuckerman D. Randomness is linear in space // Journal of Computing and System Science. 1996. - V. 52, № 1. - P. 43-52.

56. Rissanen J. J. Generalized Kraft inequality and arithmetic coding // IBM J. Res. Dev. 1976. - V. 20. - P. 198-203.

57. Rissanen J. J., Langdon G. G. Arithmetic coding // IBM J. Res. Dev. -1979. V. 23, №. - P. 149-162.

58. Rissanen J., Langdon G. G. Universal modeling and coding // IEEE

59. Transactions on Information Theory. 1981. - V. 27, № 1. - P. 12-23.

60. Roche J. R. Efficient generation of random variables from biased coins // 1991 IEEE International Symposium on Information Theory (ISIT 1991). -P. 169.

61. Rubin F. Arithmetic stream coding using fixed precision registers // IEEE Transactions on Information Theory. 1979. - V. 2, №6. - P. 672-675.

62. Rukhin A. et al. A statistical test suite for random and pseudorandom number generators for cryptographic applications // NIST Special Publication 800-22 (rev. May,15,2001). http://csrc.nist.gov/rng/SP800-22b.pdf.

63. Ryabko В. Y. Fast and effective coding of information sources // IEEE Transactions on Information Theory. 1994. - V. 40, № 1. - P. 96-99.

64. Ryabko B. The simple ideal cipher system // 2000 IEEE International Symposium on Information Theory (ISIT 2000). Sorrento, Italy, June 2000. - P. 240.

65. Ryabko В., Matchikina E. Fast and efficient construction of an unbiased random sequence // IEEE Transactions on Information Theory. 2000. - V. 46, N 3. - P. 1090-1093.

66. Ryabko B. Ya., Monarev V. A. Using information theory approach to randomness testing // Journal of Statistical Planning and Inference. 2005.

67. Ryabko В., Rissanen J. Fast adaptive arithmetic code for large alphabet sources with asymmetrical distributions // IEEE Communications Letters. -2003.-V. 7, № l.-P. 33-35.

68. Schneier B. Self-study course in block cipher cryptanalysis // Cryptologia. 2000. - V. 24, N. 1. - P. 18-34. http://www.counterpane.com/self-study.html.

69. Shannon C. Communication theory of secrecy systems // Bell System Technical Journal. 1949. - V. 28, № 4. - P. 656-715.

70. Simmons G. J. Cryptology // Encyclopaedia Britannica. ed. 16. Chicago, IL: Encyclopaedia Britannica Inc. - 1986. - P. 913-924.

71. Shtarkov Y. М., Babkin V. F. Combinatorial encoding for discrete stationary sources // 1973 IEEE International Symposium on Information Theory. Budapest, 1973. - P. 249-257.

72. Willems F. M. J., Shtarkov Y. M., Tjalkens T. J. The context-tree weighting method: Basic properties // IEEE Transactions on Information Theory. 1995. - V. 41, №3. - P. 653-664.

73. Witten I. H., Neal R., Cleary J. G. Arithmetic coding for data compression // Communications of the ACM. 1987. - V. 30, №6. - P. 520-540.

74. Ziv J., Lempel A. A universal algorithm for sequential data compression // IEEE Transactions on Information Theory. 1977. - V. 23, № 3. - P. 337-343.

75. Ziv J., Lempel A. Compression of individual sequences via variable-rate coding // IEEE Transactions on Information Theory. 1978. - V. 24, № 5. -P. 530-536.

76. Работы автора, в которых изложены основные результаты диссертации1. Монографии

77. Рябко Б. Я., Фионов А. Н. Основы современной криптографии для специалистов в информационных технологиях. М.: Научный мир, 2004.- 173 с.

78. Статьи и доклады на конференциях

79. Ryabko В. Y., Fionov А. N. A fast and efficient homophonic coding algorithm // Algorithms and Computation. Berlin: Springer, 1996. - P. 427-438 (Lecture Notes in Computer Science; V. 1178).

80. Фионов A.H. Быстрый метод полной рандомизации сообщений // Российская научно-техн. конф. "Информатика и проблемы телекоммуникаций". Новосибирск, 1996. - Т. 1. - С. 70.

81. Фионов А. Н. Эффективный метод рандомизации сообщений на основе арифметического кодирования // Дискретный анализ и исследование операций. 1997. - Т. 4, № 2. - С. 51-74.

82. Рябко Б. Я., Федотов А. М., Фионов А. Н. Надежные системы защиты электронных публикаций, базирующиеся на эффективном омо-фонном кодировании // Вычислительные технологии. 1997. - Т. 2, № 3.- С. 68-72.

83. Фионов А. Н. Эффективная рандомизация сообщений на основе арифметического кодирования // Международная научно-техн. конф. "Информатика и проблемы телекоммуникаций". Новосибирск, 1997. - С. 157-158.

84. Ryabko В. Ya., Fionov А. N. Homophonic coding with logarithmic memory size // Algorithms and Computation. Berlin: Springer, 1997. P. 253-262 (Lecture Notes in Computer Science; V. 1350).

85. Рябко Б. Я., Фионов А. Н. Быстрый метод полной рандомизации сообщений // Проблемы передачи информации. 1997. - Т. 33, № 3. - С. 3-14.

86. Ryabko В., Fionov A. Decreasing redundancy of homophonic coding // 1997 IEEE International Symposium on Information Theory (ISIT 1997). -Ulm, Germany, July 1997. P. 94.

87. Рябко Б. Я., Федотов А. М., Фионов А. Н. Современные средства криптографической защиты информации в сетях передачи данных // Международная конф. "Современные информационные технологии". -Новосибирск, 1998. С. 42-44.

88. Рябко Б. Я., Фионов А. Н., Федотов А. М. Конфиденциальность взаимодействий в открытых информационных сетях // Международный семинар "Перспективы развития современных средств и систем телекоммуникаций". Новосибирск, 1998. - С. 38-42.

89. Fionov А. N. Computationally efficient randomization of messages // Международная Сибирская конф. по исслед. операций. Новосибирск, 1998. - С. 159.

90. Ryabko В. Ya., Fionov А. N. Efficient algorithm of adaptive arithmetic coding // Международная Сибирская конф. по исслед. операций. Новосибирск, 1998. - С. 151.

91. Fionov А. N. Using homophonic decoding for random number generation // Международный семинар "Распределенная обработка информации". -Новосибирск, 1998. С. 63-67.

92. Ryabko В., Fionov A. Fast homophonic coding with logarithmic memory size // 1998 IEEE International Symposium on Information Theory (ISIT 1998). Cambridge, MA, USA, August 1998. - P. 52.

93. Ryabko В., Fionov A. Efficient homophonic coding // IEEE Transactions on Information Theory. 1999. - V. 45, N. 6. - P. 2083-2091.

94. Рябко Б. Я., Фионов А. Н. Эффективный метод адаптивного арифметического кодирования для источников с большими алфавитами // Проблемы передачи информации. 1999. - Т. 35, № 4. - С. 1-14.

95. Ryabko В., Fionov A. Fast and space-efficient adaptive arithmetic coding // Cryptography and Coding. Berlin: Springer, 1999. - P. 270-279 (Lecture Notes in Computer Science; V. 1746).

96. Фионов A. H. Составные коды для криптосистем // Международный семинар "Перспективы развития современных средств и систем телекоммуникаций". Новосибирск, 2000. - С. 74-79.

97. Fionov A. Random number generation via homophonic coding // 2000 IEEE International Symposium on Information Theory (ISIT 2000). Sorrento, Italy, June 25-30, 2000. - P. 354.

98. Фионов A.H. Стойкий потоковый шифр на базе рандомизированных кодов // Международная научно-техн. конф. "Информатика и проблемы телекоммуникаций". Новосибирск, 2001. - С. 40-41.

99. Fionov A. Universal homophonic coding // 2001 IEEE International Symposium on Information Theory (ISIT 2001). Washington, DC, USA, June 24-29, 2001. - P. 116.

100. Ryabko В., Fionov A. Efficient algorithm for strongly ideal cipher // Workshop on Computer Science and Information Technologies (CSIT 2001). Ufa, Russia, 2001.

101. Ryabko В., Fionov A. Adaptive arithmetic coding for changing statistics: randomization vs space // 2002 IEEE International Symposium on Information Theory (ISIT 2002). Lausanne, Switzerland, June 24 - June 29, 2002. - P. 116.

102. Фионов A. H. Построение омофонных кодов при неизвестной статистике источника сообщений // Международный семинар "Перспективы развития современных средств и систем телекоммуникаций". Санкт-Петербург, 30 июня - 4 июля, 2002. - С. 83-86.

103. Ryabko В., Fionov A. Efficient algorithm for strongly ideal cipher // 2nd IMA Conference on Mathematics in Communication. Lancaster University, UK, 16-18 December 2002.

104. Рябко Б. Я., Фионов А. Н. Перспективы применения криптографических систем // Электросвязь. 2003. - № 8. - С. 28-31.

105. Fionov A. Arithmetic homophonic coding with dummy symbols // 2004 IEEE International Symposium on Information Theory (ISIT 2004). -Chicago, Illinois, USA, June 27 July 2, 2004. - P. 129.

106. Ryabko B. Ya., Fionov A. N., Monarev V. A., Shokin Yu. I.

107. Using information theory approach to randomness testing // 2nd Russian-German Advanced Research Workshop on Computational Science and High Performance Computing. Stuttgart, Germany, March 14 - 16, 2005. -http://www.hlrs.de.