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

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

Большинство из практически используемых в настоящее время криптосистем обладают лишь вычислительной стойкостью. Это означает, например, что шифры могут в принципе быть взломаны путем полного перебора ключей. Но что более важно отметить, пока никому не удалось найти каких-либо строгих доказательств того, что для тех или иных вычислительно стойких систем не существует более эффективных алгоритмов взлома, чем перебор ключей. Более того, история криптоанализа свидетельствует о том, что для многих систем, казавшихся надежными, со временем такие более эффективные алгоритмы взлома находятся, а некоторые системы в результате оказываются настолько нестойкими, что выходят из практического использования. Основная проблема здесь состоит в том, что при отсутствии математически строгих доказательств стойкости никто не может быть уверен, что противник уже сегодня не располагает эффективными методами, направленными против используемых криптосистем. Если говорить о перспективах применения вычислительно стойких систем, то следует также отметить, что большую угрозу для таких систем представляют квантовые компьютеры. Сегодня квантовые компьютеры изучаются в основном на уровне математических моделей, хотя имеются сведения о первых практических реализациях с ограниченными вычислительными возможностями (скажем, реализующие 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−586 «Построение эффективных алгоритмов для кодирования и прогнозирования источников информации и нумерации комбинаторных объектов», 99−07−90 438 «Разработка параллельных средств анализа и организации функционирования суперВС с массовым параллелизмом, моделей и методов распараллеливания прикладных задач», 00−01−672 «Разработка доказуемо стойких криптографических алгоритмов, основанных на эффективных методах кодирования источников информации», 03−01−495 «Разработка универсальных кодов асимптотически минимальной сложности» ;

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