Эффективные методы построения идеальных криптографических систем защиты информации тема диссертации и автореферата по ВАК РФ 05.12.13, доктор технических наук Фионов, Андрей Николаевич

• Фионов, Андрей Николаевич
• доктор технических наук
• 2005

Оглавление диссертации доктор технических наук Фионов, Андрей Николаевич

Введение.

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

Список литературы диссертационного исследования доктор технических наук Фионов, Андрей Николаевич, 2005 год

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.