Методы теории помехоустойчивого кодирования в некоторых задачах защиты информации тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат технических наук Чмора, Андрей Львович

• Чмора, Андрей Львович
• кандидат технических наук
• 2012

Оглавление диссертации кандидат технических наук Чмора, Андрей Львович

Содержание

Введение

Глава I. Маскировка ключа с помощью биометрии

1.1. Биометрия и криптографические ключи

1.2. Модель маскировки ключа с помощью биометрии

1.3. Статистические свойства радужной оболочки

1.4. Кодовая конструкция

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

1.6. Метод «биометрической вуали»

1.7. Сценарий практического применения

1.8. Выводы

Глава II. Метод шарад

II. 1. Сетевая DoS-атака

11.2. Технология САРТСНА

11.3. Вычислительные шарады

11.4. Шарады и DoS-атака

11.5. Недостатки метода шарад

Глава III. Кодовые шарады

III. 1. Кодовая конструкция

111.2. Выбор кода

111.3. Итеративный метод

111.4. Выводы

Заключение

Литература

Приложение А. Основные понятия теории кодирования

А.1. Геометрическая интерпретация кода

А. 2. Проверочная, порождающая матрицы и их свойства

А.З. Коды Рида—Соломона

А.4. Коды Боуза—Чоудхури—Хоквингема

А.5. Число проверочных матриц кода РС

А.6. Обобщенные коды РС

А.7. Обобщенные коды БЧХ

А.8. Декодирование линейного кода

Приложение Б. Некоторые разделы криптографии

Б.1. Криптографические хэш-функции

Б.2. Блочные шифры

Приложение В. Парадокс дней рождения

Введение диссертации (часть автореферата) на тему «Методы теории помехоустойчивого кодирования в некоторых задачах защиты информации»

Введение

Актуальность работы. В ближайшие десятилетия следует ожидать появления действующего прототипа квантового компьютера. В 1997 году П. В. Шор1 (P. W. Shor) продемонстрировал существование эффективных квантовых методов решения сложных вычислительных задач, определяющих криптостойкость известных алгоритмов цифровой подписи и асимметричного шифрования. В первую очередь к ним относятся широко применяемые на практике алгоритмы RSA, DSA, KCDSA, EC-DSA, ЕС-KCDSA, EC-GDSA (ISO/IEC 14888-3, ISO/IEC 14888-2 и IEEE Р1363), а также ГОСТ Р 34.10-2001. Другой известный результат3 К.-П. Шнорра (С.-P. Schnorr) и М. Якобссона (М. Jakobsson) указывает на то, что криптостойкость перечисленных алгоритмов определяется вычислительной трудоемкостью решения задач целочисленной факторизации и дискретного логарифмирования.

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

Аппарат теории кодирования широко применяется для построения протоколов идентификации и цифровой подписи. Следует отметить протокол Ж.Штерна4 (J.Stern), а также схему цифровой подписи на случайных ко-

1 Shor P. W. Polynomial-time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum

Computer // SIAM J. of Сотр. 1997- no. 26. Pp. 1484-1509.

2 Schnorr C. -P., Jakobsson M. Security of Discrete Log Cryptosystems in the Random Oracle and Generic

Model //In The Mathematics of Public-Key Cryptography. The Fields Institute. 1999.

3 Barg A. Complexity Issues in Coding Theory // Handbook of coding theory. Ed. by V. S. Pless, W. C. Huffman, R. Brualdi. Amsterdam, Holland: Elsevier Science, 1998.

4 Stern J. A New Identification Scheme Based on Syndrome Decoding // Advances in

дах5 Г. А. Кабатянского, Е. А. Крука и Б. Дж. М. Смитса (В. J. М. Smeets).

Широко известны криптосистемы Р. МакЭлиса (R. МсЕНесе) и Г. Нидер-райтера (Н. Niederreiter) на основе кодов Гоппы6 и обобщенных кодов Рида-Соломона7. В работе В. М. Сидельникова и С. О. Шестакова предложена эффективная атака на криптосистему на основе обобщенных кодов Рида—Соломона8. В. М. Сидельников разработал вариант криптосистемы на кодах Рида—Маллера9. Подробное исследование этой криптосистемы завершилось доказательством ее уязвимости10. В 1991 году Э. М. Габидулин, А. В. Парамонов, О. В. Третьяков предложили криптосистему, основанную на кодах, исправляющих ошибки в ранговой метрике11.

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

Cryptology-CRYPTO'93. Lect. Notes in Сотр. Sci. Springer-Verlag. 1993. Vol. 773. Pp. 13-21.

5 KabatianskiiG., KroukE., Smeets B.J.M. A Digital Signature Scheme Based on Random Error-

Correcting Codes // Lect. Notes in Сотр. Sci. Springer-Verlag. 1997. Vol. 1355. Pp. 161-167.

6 McEliece R. A Public-key Cryptosystem Based on Algebraic Coding Theory // Deep Space Network

Progress Report / DSN PR 42-44. 1978. - Apr 15. Pp. 114-116.

7 Niederreiter H. Knapsack-type Cryptosystems and Algebraic Coding Theory // Prob. of Control and

Inform. Theory. 1986. Vol. 15, no. 5. Pp. 159-166.

8 Sidelnikov V. M., Shestakov S. 0. On Insecurity of Cryptosystems Based on Generalized Reed-Solomon

Codes // Disc. Math, and App. 1992. Vol. 2, no. 4. Pp. 439-444.

9 Sidelnikov V. M. A Public-key Cryptosystem based on Binary Reed-Muller Codes // Disc. Math, and

App. 1994. Vol. 4, no. 3. Pp. 439-444.

10 Minder L., Shokrollahi A. Cryptanalysis of the Sidelnikov Cryptosystem // Advances in Cryptology-EUROCRYPT'07 / Ed. by M. Naor. Vol. 4515 of Lect. Notes in Сотр. Sci. Springer-Verlag, 2007. Pp. 347-360.

11 Gabidulin E.M., Paramonov A.V., Tretjakov О. V. Ideals Over a Non-Commutative Ring and Their Application in Cryptology // Advances in Cryptology-EUROCRYPT'91 / Ed. by D.W. Davies. Vol. 547 of Lect. Notes in Сотр. Sci. Springer-Verlag, 1991. Pp. 482-489.

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

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

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

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

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

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

щего адекватный уровень криптостойкости, представляется перспективной и актуальной.

DoS12-aTaKH отличаются от других известных атак. Задача DoS-атаки — создание искусственной ситуации, в которой добросовестному потребителю будет отказано в предоставлении соответствующих услуг.

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

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

12 Denial of Service.

13 Brainard J., Juels A. Client Puzzles: A Cryptographic Countermeasure Against Connection Depletion Attacks // Proc. of the ISOC Network and Distr. Sys. Sec. Sym. 1999. Pp. 151-165.

14 Distributed Denial of Service.

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

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

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

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

2. Разработать метод маскировки криптографического ключа с помощью биометрии и обосновать его криптостойкость.

3. Разработать конструкции шарад на основе кодов, исправляющих ошибки.

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

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

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

• предложена практическая реализация модели маскировки ключа с помощью биометрии с привлечением аппарата теории помехоустойчивого кодирования, — так называемый метод «биометрической вуали», и приведен пример кодовой конструкции;

• выполнен анализ криптостойкости метода «биометрической вуали»;

• выполнен анализ метода шарад и обозначены недостатки известных конструкций;

• введен класс шарад на основе кодов, исправляющих ошибки (кодовые шарады);

• сконструирована итеративная кодовая шарада и выполнен анализ ее устойчивости;

• предложена компактная и устойчивая итеративная кодовая шарада, обладающая широким диапазоном трудоемкости и допускающая плавную настройку.

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

Актуальность разработки эффективных методов противодействия ОБоЗ-атакам невозможно переоценить, с развитием сетевых технологий, а также с

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

Научные положения, выносимые на защиту. На защиту выносятся следующие основные результаты и положения:

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

• метод «биометрической вуали», гарантирующий адекватный уровень практической криптостойкости: при параноидальном подходе трудоемкость раскрытия эталона методом силовой атаки не менее 289 двоичных операций;

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

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

• итеративная кодовая шарада, которая не поддается распараллеливанию;

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

Апробация работы. На представленные в первой главе результаты по-

лучен патент Российской Федерации, а также патенты Республики Корея и США [1-3]. Кроме этого, материалы диссертационной работы были использованы при подготовке курса лекций по теме «Криптографические методы защиты информации в компьютерных системах и сетях» по направлению 011674 факультета РТК Московского физико-технического института кафедры «Проблемы передачи и обработки информации», прочитанных в период с 2008 по 2011 гг. Следует также отметить, что результаты, представленные ранее в патентах [1-3] и позднее в публикации [4], были впоследствии воспроизведены группой специалистов Компьютерной лаборатории (Computer Laboratory) Кембриджского университета под руководством известного эксперта в области защиты информации, профессора Р. Андерсона (R. Anderson), и опубликованы в техническом отчете UCAM-CL-TR-640 в июле 2005 г., а затем и в статье15 2006 г. Однако, приоритет принадлежит российским авторами, как авторам первой патентной заявки по данной тематике, зарегистрированной в мае 2004 г. Таким образом, можно заключить, что результаты, изложенные в первой главе настоящей диссертации, с успехом прошли международную апробацию.

Публикации. В ходе подготовки диссертации соискателем опубликованы 14 печатных работ [1-14], включая патенты Российской Федерации, США и Республики Корея. Конкретно по теме диссертации опубликованы 5 печатных работ [1-4, 7], из них 2 опубликованы в реферируемых изданиях, включенных в Перечень ВАК [4, 7].

Личный вклад автора. Содержание диссертации и основные положения, выносимые на защиту, отражают персональный вклад автора в опубликованные работы. Подготовка заявок по патентам [1-3] проводилась совместно с соавтором, причем вклад диссертанта не менее 50%. Все представленные

15 Нао F., Anderson R., Daugman J. G. Combining Crypto with Biometrics Effectively // IEEE Trans, on Comp. 2006. Vol. 55, no. 9. Pp. 1081-1088.

в диссертации результаты получены лично автором.

Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения, библиографии и приложения. Общий объем работы составляет 115 страниц. Диссертация содержит 2 рисунка и одну таблицу по объему не превышающих одну страницу. Список литературы состоит из 101 наименования на 13 страницах.

Заключение диссертации по теме «Теоретические основы информатики», Чмора, Андрей Львович

III.4. Выводы

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

Заключение

Сформулируем основные результаты диссертационного исследования.

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

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

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

4. Приведен пример кодовой конструкции, а именно, двоичный код БЧХ с п = 2048, размерности к ^ 398, исправляющий двоичные ошибки веса t ^ 150.

5. Разработанный метод «биометрической вуали» удовлетворяет модели и гарантирует адекватный уровень практической криптостойкости. В рамках метода приводится описание процедур представления и выделения криптографического ключа.

6. Выполнен анализ криптостойкости метода «биометрической вуали». Оценивалась трудоемкость силовой атаки с целью получения эталона Т для некоторого S при Т ф S. Из свойств биометрии радужной оболочки следует, что энтропия полученного образа, так же как эталона, не превышает 249 двоичных разрядов. Поскольку Н ^ 0.333, то можно ввести ограничение сверху на вес вектора ошибки, положив £ = 83. Показано, что в диапазоне 10 < £ ^ 83 с помощью перебора ошибок веса Ь можно проверить не более 9% от общего числа претендентов на Т.

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

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

9. Поскольку тривиальные кодовые шарады допускают возможность распараллеливания, введен класс шарад на основе итеративной кодовой конструкции (итеративная кодовая шарада).

10. Выполнен анализ итеративной кодовой шарады на устойчивость. Показано, что не смотря на устойчивость, такие шарады не оптимальны с точки зрения объема памяти и накладных расходов при передаче.

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

Список литературы диссертационного исследования кандидат технических наук Чмора, Андрей Львович, 2012 год

Литература

1. Чмора A. JL, Уривский А. В. Биометрическая система аутентификации / Федеральная Служба по Интеллектуальной Собственности, Патентам и Товарным Знакам. Патент на изобретение, 2004. — Май 12. № 2316120. URL: http://wwwl.fips.ru/fips_servl/fips_servlet?DB= RUPAT&rn=5142&DocNumber=2316120&TypeFile=html (дата обращения: 02.03.2011).

2. Chmora A., Ourivski A. Method and Apparatus for Generating Cryptographic Key Using Biométrie Data / Republic of Korea Patent Office. Republic of Korea Patent, 2005. - Mar 26. No. 10-2005-0025211.

3. Chmora A., Ourivski A. Method and Apparatus for Generating Cryptographic Key Using Biométrie Data / United States Patent and Trademark Office. United States Patent, 2010.-Sep 21. No. 7,802,105. URL: http://patft.uspto.gov (дата обращения: 02.03.2011).

4. Чмора A. JI. Маскировка ключа с помощью биометрии // Проблемы Передачи Информации. 2011. Т. 47, № 2. С. 131-146.

5. Чмора Андрей. Современная прикладная криптография. Москва: Ге-лиос, 2002. 256 с. ISBN: 5-85438-046-3.

6. Error Control, Cryptology, and Speech Compression // Workshop on Information Protection / Ed. by A. Chmora, S. B. Wicker. Lecture Notes in Computer Science. Moscow, Russia: Springer-Verlag, 1994.— Dec 6-9.

7. Чмора A. JI. Кодовые шарады // Информационно-управляющие системы. 2010. № 6. С. 47-53.

8. Chmora A., Ourivski A. Method and System for Distributed Certificate Management in Ad-hoc Networks / United States Patent and Trademark Office. United States Patent, 2008.-Jun 3. No. 7,382,762. URL:http: //patft.uspto.gov (дата обращения: 02.03.2011).

9. Chmora A., Urivskiy A. Method of Managing a Key of User for Broadcast Encryption / United States Patent and Trademark Office. United States Patent, 2010.-Aug 10. No. 7,774,598. URL: http://patft.uspto.gov (дата обращения: 02.03.2011).

10. Urivskiy A., Chmora A., Bogachov A. et al. Method for Making Seed Value Used in Pseudo Random Number Generator and Device Thereof / United States Patent and Trademark Office. United States Patent, 2010. —Aug 10. No. 7,773,748. URL: http://patft.uspto.gov (дата обращения: 02.03.2011).

11. Chmora A., Ourivski A. Light-weight Key Distribution Scheme in Wireless Network / United States Patent and Trademark Office. United States Patent, 2010.-Jun 15. No. 7,738,663. URL: http://patft.uspto.gov (дата обращения: 02.03.2011).

12. Чмора A. JI., Уривский А. В., Ким В. Схема предварительного распределения ключей для кластерных сетей и способ ее функционирования / Федеральная Служба по Интеллектуальной Собственности, Патентам и Товарным Знакам. Патент на изобретение, 2008. — Июль 27. № 2330382. URL: http://wwwl.fips.ru/fips_servl/fips_servlet?DB= RUPAT&rn=5142&DocNumber=2330382&TypeFile=html (дата обращения: 02.03.2011).

13. Чмора А. Л., Уривский А. В., Захаров С. В. и др. Способ и устройство формирования стартового значения для генератора псевдослучайных

чисел / Федеральная Служба по Интеллектуальной Собственности, Патентам и Товарным Знакам. Патент на изобретение, 2007.— Январь 20. № 2292074. URL: http: //wwwl .f ips. ru/f ips_servl/f ips_servlet?DB= RUPAT&rn=5142&DocNumber=2292074&TypeFile=html (дата обращения: 02.03.2011).

14. Уривский А. В., Чмора A. JI. Система распределения ключей и способ ее функционирования / Федеральная Служба по Интеллектуальной Собственности, Патентам и Товарным Знакам. Патент на изобретение, 2008. — Июль 20. № 2329605. URL: http: //wwwl .f ips .ru/f ips_servl/ fips_servlet?DB=RUPAT&rn=5142&DocNumber=2329605&TypeFile=html (дата обращения: 02.03.2011).

15. Anderson R. Security Engineering. A Guide to Building Dependable Distributed Systems. 2nd edition. Wiley, 2008. 1080 pp. ISBN: 978-0-470-06852-6.

16. Monrose F., Reiter M. K., Wetzel R. Password Hardening Based on Keystroke Dynamics // Proceedings of 6th ACM Conference on Computer and Communication Security (CCCS). Singapore: 1999. Pp. 73-82.

17. Monrose F., Reiter M. K., Wetzel R. Cryptographic Key Generation from Voice // Proceedings of IEEE Symposium on Security and Privacy. Oakland, CA, US: 2001. Pp. 202-213.

18. Hao F., Chan C. W. Private Key Generation from On-Line Handwritten Signatures // Information Management к Computer Security. 2002. Vol. 10, no. 2. Pp. 159-164.

19. Soutar C., Roberge D., Stoianov A. et al. Biometric Encryption™ using image processing // Proceedings of SPIE. Vol. 3314. 1998. Pp. 178-188.

20. Soutar С., Roberge D., Stoianov A. et al. Biometrie Encryption™ - Enrollment and Verification Procedures // Proceedings of SPIE. Vol. 3386. 1998. Pp. 24-35.

21. Soutar C., Roberge D., Stoianov A. et al. Biometrie Encryption™ // Ed. by R. К. Nichols. ICSA Guide to Cryptography. McGraw-Hill Companies, 1999. 28 pp. ISBN: 0079137598. URL: http://www.comp. hkbu.edu.hk/~ycfeng/project/Biometric_Encryption.pdf(дата обращения: 02.03.2011).

22. Clancy Т. С., Kiyavash N., Lin D. J. Secure Smart Card-Based Fingerprint Authentication // ACM SIGMM Workshop Biometrics Methods and Application (WBMA). Berkeley, CA, US: 2003.-Nov 2-8. Pp. 45-52.

23. Jules A., Sudan M. A Fuzzy Vault Scheme // Designs, Codes and Cryptography. 2006. Vol. 38, no. 2. Pp. 237-257.

24. Goh A., Ngo D. C. L. Computation of Cryptographic Keys from Face Biometrics // Lecture Notes in Computer Science. 2003. Vol. 2828. Pp. 1-13.

25. МакВильямс Ф. Д., Слоэн H. Дж. Теория кодов, исправляющих ошибки. Москва: Связь, 1979. 744 с.

26. Berlekamp Е. R., McEliece R. J., van Tilborg H. С. A. On the Inherent Intractability of Certain Coding Problems // IEEE Transactions on Information Theory. 1978. Vol. IT-24, no. 3. Pp. 384-386.

27. Vardy A. On the Inherent Intractability of Certain Coding Problems // IEEE Transactions on Information Theory. 1997. Vol. IT-43, no. 6. Pp. 1757-1766.

28. Vardy A. Algorithmic Complexity in Coding Theory and the Minimum Dis-

tance Problem // Proceedings of the 29 Annual ACM Symposium on Theory of Computing Table. El Paso, Texas, US: 1997. Pp. 92-109.

29. Dumer I., Micciancio D., Sudan M. Hardness of Approximating the Minimum Distance of a Linear Code // IEEE Transactions on Information Theory. 2003. Vol. IT-49, no. 1. Pp. 22-37.

30. Guruswami V., Vardy A. Maximum-Likelihood Decoding of Reed-Solomon Codes is NP-hard // IEEE Transactions on Information Theory. 2005. Vol. IT—51, no. 7. Pp. 2249-2256.

31. Guruswami V., Sudan M. Improved Decoding of Reed-Solomon Codes and Algebraic Geometry Codes // IEEE Transactions on Information Theory. 1999. Vol. IT—45, no. 6. Pp. 1757-1767.

32. Daugman J. G. The Importance of Being Random: Statistical Principles of Iris Recognition // Pattern Recognition. 2003. Vol. 36. Pp. 279-291.

33. Daugman J. G. How Iris Recognition Works // IEEE Transactions on Circuits and Systems for Video Technology. 2004. Vol. 14, no. 1. Pp. 21-30.

34. Daugman J. G. Complete Discrete 2D Gabor Transforms by Neural Networks for Image Analysis and Compression // IEEE Transactions on Acoustics, Speech, and Signal Processing. Vol. 36. 1988. Pp. 1169-1179.

35. Daugman J. G. Probing the Uniqueness and Randomness of IrisCodes: Results From 200 Billion Iris Pair Comparisons // Proceedings of IEEE. Vol. 94. 2006. Pp. 1927-1935.

36. Barg A., Krouk E., van Tilborg H. C. A. On the Complexity of Minimum Distance Decoding of Long Linear Codes // IEEE Transactions on Information Theory. 1999. Vol. IT-45, no. 5. Pp. 1392-1405.

37. Lenstra А. К., Verheul E. Selecting Cryptographic Key Sizes // Journal of Cryptology. 2001. Vol. 14, no. 4. Pp. 255-293.

38. Lenstra A. K. Key Lengths // Ed. by H. Bidgoli. 1st edition. The Handbook of Information Security. Wiley, 2005.

39. Yearly Report on Algorithms and Key Sizes // European Network of Excellence in Cryptology II, ECRYPT II / Ed. by N. Smart; D.SPA.13, Rev. 1.0, ICT-2007-216676. Katholieke Universiteit Leuven (KUL), 2010. URL: http : //www. ecrypt. eu. org/document s/D. SPA. 13. pdf (дата обращения: 02.03.2011).

40. Barker E., Barker W., Burr W. et al. Recommendation for Key Management / National Institute of Standards and Technology. Special Publication 800-57, Part 1, 2007.-Mar. URL: http://csrc.nist. gov/publications/nistpubs/800-57/sp800-57-Partl-revised2_ Mar08-2007.pdf (дата обращения: 02.03.2011).

41. Hao F., Anderson R., Daugman J. G. Combining Crypto with Biometrics Effectively // IEEE Transactions on Computers. 2006. Vol. 55, no. 9. Pp. 1081-1088.

42. Blaze M., Diffie W., Rivest R. L. et al. Minimal Key Lengths for Symmetric Ciphers to Provide Adequate Commercial Security // Report by an Ad Hoc Group of Cryptographers and Computer Scientists / Business Software Alliance. 1996.

43. Bertoni G., Breveglieri L., Fragneto P. et al. Efficient Software Implementation of AES on 32-bit Platforms // Lecture Notes in Computer Science. 2003. Vol. 2523. Pp. 129-142.

44. Ekert A., Jozsa R. Quantum Computation and Shor's Factoring Algorithm // Reviews of Modern Physics. 1997. Vol. 68, no. 3. Pp. 733-753.

45. Shor P. W. Polynomial-time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer // SIAM Journal of Computing. 1997. no. 26. Pp. 1484-1509.

46. Vandersypen L. M. K., Steffen M., Breyta G. et al. Experimental Realization of Shor's Quantum Factoring Algorithm Using Nuclear Magnetic Resonance // Nature. 2001. no. 414. Pp. 883-887.

47. Beauregard S. Circuit for Shor's Algorithm Using 2n+3 Qubits // Quantum Information and Computation. 2003. no. 3. Pp. 175-185.

48. Hanneke D., Home J. P., Jost J. D. et al. Realization of a Programmable Two-qubit Quantum Processor // Journal of Cryptology. 2009. no. 6. Pp. 13-16.

49. Naraine R. Massive DDOS Attack Hit DNS Root Servers. 2002.-Oct 23. URL: http://siliconvalley.internet.com/news/article.php/ 1486981 (дата обращения: 03.03.2011).

50. Wagner J. SCO Hit By Another DDoS Attack. 2003.-Dec 10. URL:http: //www.internetnews.com/dev-news/article.php/3287781 (дата обращения: 03.03.2011).

51. Schuba С. L., Krsul I. V., Kuhn M. G. et al. Analysis of a Denial of Service Attack on TCP // Proceedings of IEEE Symposium on Security and Privacy. IEEE Computer Society Press, 1997. — May. Pp. 208-223. URL: http: //citeseerx. ist. psu. edu/viewdoc/download? doi=10.1.1.85.6727&rep=repl&type=pdf (дата обращения: 03.03.2011).

52. von Ahn L., Blum M., Hopper N. J., Langford J. CAPTCHA: Using hard AI problems for security // Eurocrypt'03 / Ed. by E. Biham. Lecture Notes in Computer Science. Springer-Verlag, 2003. Pp. 294-311.

53. Dwork C., Naor M. Pricing Via Processing or Combatting Junk Mail // Proceedings of Crypto 92. 1992.

54. Brainard J., Juels A. Client Puzzles: A Cryptographic Countermeasure Against Connection Depletion Attacks // Proceedings of the 1999 ISOC Network and Distributed System Security. 1999. Pp. 151-165.

55. Aura T., Nikander P., Leiwo J. DoS-resistant Authentication with Client Puzzles // 8th International Workshop on Security Protocols. Lecture Notes in Computer Science. Springer-Verlag, 2000. Pp. 170-181.

56. Dean D., Stubblefield A. Using client puzzles to protect TLS // 10th USENIX Security Symposium. 2001. Pp. 1-8.

57. Wang X., Reiter M. K. Defending Against Denial-of-Service Attacks with Puzzle Auctions // IEEE Symposium on Security and Privacy. Washington, DC: 2003. Pp. 78-92.

58. Price G. A General Attack Model on Hash-Based Client Puzzles // 9th IMA Conference on Cryptography and Coding. Vol. 2898. Cirencester, UK: 2003. Pp. 319-331.

59. Waters B., Juels A., Halderman A., Felten E. New Client Puzzle Outsourcing Techniques for DoS Resistance // ACM CCS. 2004. Pp. 246-256.

60. Wang X., Reiter M. K. Mitigating Bandwidth-Exhaustion Attacks Using Congestion Puzzles // 11th ACM Conference on Computer and Communications Security. Washington, DC: 2004. Pp. 257-267.

61. Feng W. The Case for TCP/IP Puzzles // ACM SIGCOMM Future Directions in Network Architecture (FDNA '03). Karlsruhe, Germany: 2003.

62. Feng W., Kaiser E., Luu A. The Design and Implementation of Network Puzzles // IEEE INFOCOM '05. Vol. 4. Miami, FL: 2005. Pp. 2372-2382.

63. Parno В., Wendlandt D., Shi E. et al. Portcullis: Protecting Connection Setup from Denial-of-Capability Attacks // ACM SIGCOMM '07. Vol. 4. Kyoto, Japan: 2007. Pp. 289-300.

64. Rivest R. L., Shamir A., Wagner D. Time-lock puzzles and timed-release crypto//Technical Report MIT/LCS/TR-684. MIT, 1996. URL:http: //people.csail.mit.edu/rivest/RivestShamirWagner-timelock.pdf (дата обращения: 03.03.2011).

65. Ma M. Mitigating Denial of Service Attacks with Password Puzzles // International Conference on Information Technology: Coding and Computing (ITCC '05). Vol. 2. Las Vegas: 2005. Pp. 621-626.

66. Groza В., Petrica D. On Chained Cryptographic Puzzles // 3rd Romanian-Hungarian Joint Symposium on Applied Computational Intelligence (SACI '06). Timisoara, Romania: 2006.

67. Tritilanunt S., Boyd C., Foo E., Gonzalez J. M. Toward Non-Parallelizable Client Puzzles // 6h International Conference on Cryptology and Network Security. Vol. 4856. Singapore: 2007. Pp. 247-264.

68. Cormen T. H., Leiserson С. E., Rivest R. L., Stein C. Introduction to Algorithms. 2nd edition. McGraw-Hill, 2001. 984 pp. ISBN: 0-262-03293-7.

69. Coster M. J., Joux A., Lamacchia B. A. et al. Improved Low-Density Subset Sum Algorithms // Computational Complexity. 1992. Vol. 2, no. 2.

70. Lenstra A. K., Lenstra H. W., Lovâsz L. Factoring Polynomials with Rational Coefficients // Mathematische Annalen. 1982. Vol. 261, no. 4. Pp. 515-534.

71. Abliz M., Znati T. A Guided Tour Puzzle for Denial of Service Prevention // Annual Computer Security Applications Conference. 2009. Pp. 279-288.

72. Abadi M., Burrows M., Manasse M., Wobber T. Moderately Hard, Memory-Bound Functions // 10th Annual Network and Distributed System Security Symposium (NDSS '03). San Diego, CA: 2003. Pp. 25-39.

73. Dwork C., Goldberg A., Naor M. On Memory-Bound Functions for Fighting Spam // CRYPTO '03. Vol. 2729 of Lecture Notes in Computer Science. Santa Barbara, CA: 2003. Pp. 426-444.

74. Merkle R. C. Secure Communications Over Insecure Channels // Communications of the ACM. 1978.-Apr. Vol. 21, no. 4. Pp. 294^299.

75. Menezes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography. CRC-Press.

76. ISO/IEC 18032 // Information technology-Security techniques-Prime number generation. 2002.

77. Schnorr C. P., Jakobsson M. Security of Discrete Log Cryptosystems in the Random Oracle + Generic Model // Proceedings of Conference on The Mathematics of Public-Key Cryptography. Toronto, Canada: The Fields Institute, 1999.

78. Shoup V. Lower Bounds for Discrete Logarithms and Related Problems // Advances in Cryptology-EUROCRYPT'97. Vol. 1233 of Lecture Notes in Computer Science. Springer-Verlag, 1997. Pp. 256-266.

79. Nechaev V. Complexity of a Determinate Algorithm for the Discrete Logarithm Problem // Mathematical Notes. 1994. no. 55. Pp. 165-172.

80. Adkins D., Lakshminarayanan K., Perrig A., Stoica I. Taming IP packet flooding attacks // HotNets-II. ACM Press, 2003. Pp. 170-181.

81. Nielsen M., Chuang I. Quantum Computation and Quantum Information. 1st edition. Cambridge University Press, 2000. 675 pp. ISBN: 0521635039.

82. Barg A. Complexity Issues in Coding Theory // Handbook of coding theory, Ed. by V. S. Pless, W. C. Huffman, R. Brualdi. Amsterdam, Holland: Elsevier Science, 1998. URL: http://www.eccc.uni-trier.de/report/1997/ 046/ (дата обращения: 03.03.2011).

83. Riek R. Observations on the Application of Error-Correcting Codes to Public Key Encryption // Proceedings of the IEEE International Carnahan Conference on Security Technology, Crime Countermeasures. 1990. Pp. 15-18.

84. Rivest R. L., Shamir A., Adleman L. M. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems // Communications of the ACM. 1978. no. 21. Pp. 120-126.

85. Johansson T., Kabatianskii G., Smeets B. On the Relation Between A-Codes and Codes Correcting Independent Errors // Advances in Cryptology-EU-ROCRYPT'93. Vol. 765 of Lecture Notes in Computer Science. Springer-Verlag, 1993. Pp. 1-11.

86. van Tilborg H. C. A. Authentication Codes: An Area where Coding and Cryptology Meet // Proceedings of 5th IMA Conference on Cryptography and Coding / Ed. by C. Boyd. Institute of Mathematics & Its Applications (IMA), 1995. Pp. 169-183.

87. A. Bruen М. F., D. Wehlau. Method for the Construction of Hash Functions Based on Sylvester Matrices, Balanced Incomplete Block Designs and Error-Correcting Codes / United States Patent and Trademark Office. United States Patent Application, 2002.-Sep. No. 20,030,053,622. URL: http://www.freepatentsonline.com/y2003/0053622.html (дата обращения: 03.03.2011).

88. Weng L. Hashing System Utilizing Error Correction Coding Techniques / United States Patent and Trademark Office. United States Patent, 2003.— Mar. No. 7,085,988. URL: http://www.freepatentsonline.com/ 7085988.html (дата обращения: 03.03.2011).

89. Brown D. R. L., Campagna M. J., Struik M. Collision-resistant Elliptic Curve Hash Functions / United States Patent and Trademark Office. United States Patent Application, 2009.-Oct. No. 20,100,111,296. URL: http://www.freepatentsonline.com/y2010/0111296.html (дата обращения: 03.03.2011).

90. ISO/IEC 10118-3 // Information technology-Security techniques-Hash-functions-Part 3: Dedicated hash-functions. 2002.

91. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. Москва: Мир, 1976. 593 с.

92. Евсеев Г. С. О сложности декодирования линейных кодов // Проблемы Передачи Информации. 1983. Т. 19, № 1.

93. Крук Е. А. Границы для сложности декодирования линейных кодов // Проблемы Передачи Информации. 1983. Т. 25, № 3. С. 103-109.

94. Rivest R. L. The MD4 Message-Digest Algorithm // Request for Comments 1320. Internet Engineering Task Force, 1990. —Apr.

95. Rivest R. L. The MD5 Message-Digest Algorithm // Request for Comments 1321. Internet Engineering Task Force, 1992, —Apr.

96. Secure Hash Standard // Information Processing Standards Publication 180-3. Federal Information Processing Standards Publications, 2008.— Oct 17.

97. ГОСТ P 34.11-1994 // Информационная технология. Криптографическая защита информации. Функция хэширования. Издательство стандартов, 1994.

98. Integrity Primitives for Secure Information Systems: Final Report of RACE Integrity Primitives Evaluation RIPE-RACE 1040 // Ed. by A. Bosselaers, В. Preneel. New York: Springer-Verlag, 1995. Vol. 1007 of Lecture Notes in Computer Science.

99. Dobbertin H., Bosselaers A., Preneel B. RIPEMD-160: A Strengthened Version of RIPEMD // Fast Software Encryption, Third International Workshop / Ed. by D. Gollmann. Vol. 1039 of Lecture Notes in Computer Science. Springer-Verlag, 1996. Pp. 71-82.

100. ISO/IEC 18033-3 // Information technology-Security techniques-Encryption algorithms-Part 3: Block ciphers. 2004.

101. Bellare M., Kilian J., Rogaway P. The Security of the Cipher Block Chaining Message Authentication Code // Journal of Computer and System Sciences. 2000. Vol. 61, no. 3. Pp. 362-399.

Приложение А Основные понятия теории кодирования

В приложении приводятся только те сведения, которые необходимы для изложения результатов глав I и III диссертационного исследования. Для изучения теории помехоустойчивого кодирования следует обратиться к книгам [25, 91]. Настоящее приложение содержит материалы из упомянутых книг в переработанном и сокращенном виде.

Для дальнейших рассуждений понадобится ввести понятие конечного поля ^ = рто, где р — простое число, т — положительное целое, содержащее д элементов. Для линейного пространства размерности п над воспользуемся обозначением = {х = (ггх,..., хп)\х^ Е ¥д}.

Определим метрику Хэмминга над пространством следующим образом. Пусть задана пара векторов х, у Е тогда расстояние с£(х, у) между этими двумя векторами равно числу координат, в которых они различаются. Пусть, например, х, у Е F|. Тогда для векторов х = (4,1,2,3) и у = (1,1,4, 3) из четырехмерного пространства над Рб = {0,1, 2,3,4}, расстояние с/(х, у) = 2, так как эти вектора различаются только в первой и третьей координатах. В классических трудах по теории кодирования линейное пространство ¥™ с метрикой Хэмминга называют пространством Хэмминга. Кроме расстояния (¿(х, у), введем также функцию которая задает вес вектора х, равный числу его ненулевых координат. Для функций «¿(х, у) и \лЛ:(х) выполняются следующие соотношения: с£(х, у) = \л/1:(х — у), (¿(0,х) = \л/1:(х).

Назовем кодом произвольное подмножество С пространства F™. Тогда кодовое расстояние д(С) определяется как ¿{С) = ттх]уес;х/ус!(х,у), или как минимальное расстояние между двумя различными векторами из С.

Для представления полученных в диссертационном исследовании резуль-

татов достаточно рассмотреть только такие коды, которые представляют собой линейные подпространства пространства Для линейных кодов будем использовать обозначение [п, к, с1]ч, где п — длина кода, к — размерность и с/ — его кодовое расстояние, Очевидно, что д — с£(С). Величину г — п — к называют избыточностью кода, а отношение Я = к/п— скоростью кода.

Отметим, что кодовое расстояние линейного кода равно минимальному весу ненулевого вектора из С.

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

В результате одиночной ошибки происходит трансформация отдельного символа вектора х £ или, по-другому, замена одного символа на другой. Причем новый символ, возникший на месте исходного, также принадлежит Ед. Тогда, если в векторе х произошло t ошибок, то трансформации подверглись £ различных символов вектора. В пространстве Хэмминга£-кратная ошибка переводит кодовый вектор х в вектор х', отстоящий от х на расстояние t, что, в свою очередь, означает ¿(х, х') = Ь.

А.1. Геометрическая интерпретация кода

Для метрики Хэмминга возможна следующая геометрическая интерпретация. Если произошло не более £ ошибок, то искаженный кодовый вектор х' находится в шаре радиуса £ с центром в точке х £ С. Если все шары радиуса £ имеют центры в точках кода С, то из геометрических соображений следует, что код способен исправить любые £ или менее ошибок. Очевидно, что такое исправление, или декодирование, заключается в поиске шара с центром х, в котором располагается вектор х'. Следовательно, если (1{С) ^ 2Ь + 1, то код позволяет исправлять все ошибки веса ^

Пусть имеется информационный вектор р = ... ,рк), ръ € ¥д. Задача заключается в передаче р от отправителя к получателю по каналу с шумом. Для этого вычисляют вектор х = /(р), х Е С, где /(•)—функция кодирования, и передают х по каналу с шумом вместо р. Соответственно, на выходе канала с шумом получают х' и если число ошибок не превосходит то р = /_1(х'), где /_1(') — функция декодирования.

Важная задача теории помехоустойчивого кодирования заключается в построении кода длины п и расстоянием (1 с максимальным числом кодовых векторов. Для линейного кода это означает построение кода максимальной размерности к.

А.2. Проверочная, порождающая матрицы и их свойства

Пусть заданы х, у € такие, что х = (хъ ..., хп), у = (т/ь ..., уп) и х^у^ Е ¥д. Тогда скалярное произведение (х, у) определяется как

п ¿=1

где сложение и умножение выполняется в полеЕд.

Линейный код над ¥д может быть задан двумя различными способами. Через базис подпространства С, или через базис подпространства двойственного, или дуального, к С. Тогда дуальный код Сх над ¥д состоит из всех векторов х Е Е™, таких, что (х, у) = 0 для всех у Е С. Если предположить, что базис кода С задается набором векторов уь ..., уто тогда базис дуального кода С± состоит из всех векторов XI,... таких, что (х£,у5) = О для всех в — 1,... ,к и £ = 1,... ,п — к.

Матрица В, строки которой состоят из базисных векторов х^ кода С"1, называется проверочной матрицей кода С, а матрица А, строками которой

являются базисные вектора ys кода С, называется проверочной матрицей кода С1-. Соответственно коду С принадлежат все вектора у G F^, для которых выполнено

Вут = О,

или же все вектора у £ F™, которые имеют вид

y = pA,p£Fj.

Отметим, что столбец ут состоит из п g-ичных символов. Матрицы В и А по определению взаимно ортогональны: А ■ Вт = О, В • Ат — 0.

Утверждение 1. Кодовое расстояние кода С равно <i, если

i. Произвольный набор из d — 1 столбцов матрицы В является линейно-независимым.

ii. В матрице В найдется набор из d линейно-зависимых столбцов.

Таким образом, из Утверждения 1 следует, что для построения кода С с расстоянием d необходимо построить матрицу В, у которой произвольный набор из d —1 столбцов является линейно-независимым.

Известно, что Утверждение 1 выполняется для матрицы вида

В = =

/

«1 а°2 . .. а0 п

OL\ OL 2 ■ ■ ап

а\ а\ . .. а2 ^п

\

V

а

d-2 d-2 Ü-O

o¿

.d-2

/

,d> 2,

(A.l)

где п ^ ц — 1 и = {«1,012,.. ■ ~ различные ненулевые элементы поля ¥д. Произвольный набор из d—l столбцов такой матрицы является линейно-

независимым, что следует из свойств определителя Вандермонда

А0 ... Ph

fil ■ ■ ■ fin

А2 ft2 ■.. Л2-1

od-2 od-2 od-2

Pi P2 ' ' ' Pd-1

который отличен от 0 для f3j ф fa при j ф г.

Несложно расширить множество 03 через добавление к нему элементов О G Fq и оо. Далее будем полагать, что матрица из А.1 определена для расширенного множества Кроме этого, столбец с номером а является j-ш столбцом, если а = aj. Аналогично для вектора х = (ха1,ха2,..., хап) G Fq.

А.З. Коды Рида—Соломона

Коды Рида—Соломона (код PC) задаются с помощью проверочной матрицы А.1 и различных множеств 03. С точки зрения блоковой длины различают три типа кодов Рида—Соломона с п = q — 1, g, g + 1. Рассмотрим эти типы в контексте множества 03.

Тип I. п = q — 1. Множество 03 состоит из всех ненулевых элементов поля F

Я.'

Тип II. п = q. Множество 05 состоит из всех элементов поля Fq. Для aj = 0 столбец (а^, aj,..., матрицы В имеет вид (1,0,..., 0)т.

Тип III. п = q + 1, d > 3. Множество 03 состоит из всех элементов поля Fq и элемента оо. Причем, для b G Fq и b ф 0, boo = оо, Ъ/оо = 0 и т.д. Для а^ = оо столбец (а®, а^-,..., а^~2)Т матрицы В имеет вид (0,0,..., If по определению. Так /(оо) = 0 для многочлена

,/3 G {«1, а2,

/М = Е£о ПРИ /М < й - 2- Если /М < а - 2> то /(оо) =

Коды Рида—Соломона являются также д-значными МДР-кодами [25] и имеют параметры [п, п — й + 1,<^]д. Последнее означает, что эти коды имеют максимальную размерность п — 1 при заданных пи с1. Отметим, что коды типа I используются для построения циклических кодов Боуза—Чоудхури— Хоквингема (далее кодов БЧХ).

А.4. Коды Боуза—Чоудхури—Хоквингема

Предположим, что задано подполе ¥г, г = поля ¥д, д = рт, тогда 5|т. Рассмотрим г-значный подкод кода РС, п = д — 1, состоящий из всех векторов кода РС, координаты которых принадлежать полю Такой код называют кодом Боуза—Чоудхури—Хоквингема (код БЧХ). В дальнейшем для кодов БЧХ будем использовать обозначение ВСНг(п,с1). Код имеет параметры [д — 1, ксГ]г, где в! > с/, к' ^ д — 1 — (с1 — 1 — ) Отметим, что размерность кода РС вычисляется над полем ¥д, а размерность ВСНг(п, с1) — над его подпол ем ¥г.

А.5. Число проверочных матриц кода РС

Для заданной невырожденной матрицы % размерности с? — 1 х с/ — 1 матрицы В и %В определяют один и тот же код РС. Причем матрицы В и %В различны, если И ф где £ —единичная матрица. Следовательно, число различных проверочных матриц, которые определяют один и тот же код РС, равно числу Л^-1 невырожденных квадратных матриц Н размера й— 1 х с1- 1. И число таких матриц

= (/-1 - IX/-1 -д)... (дл~1 - дй~2).

94

А.6. Обобщенные коды PC

Добавим к полю F^ элемент оо и рассмотрим результирующее поле ¥q =

¥„ U оо. Имеем проверочную матрицу вида

/

С

71«? Ъ®2 ■ 7псхп

7i 72СК2 • ■ • InOin

ha\ 72«! • ■ • InOtl

\

\Ъ(*1 2 72^2 2 • • • 7пО& 2)

, d > 3, п = q + 1,

(А.2)

где aj G ¥q и aj -ф щ при j ф г, jj <Е Fg \ {0}. Для aj = со столбец

(7ja°j-• ■ • > ljaf2)Т матрицы С имеет вид (0, 0,..., 7¿)т, j —

Обобщенный код длины п = q + 1 имеет кодовое расстояние d и размерность n — d + 1.

Если задана диагональная матрица D = diag(7i, 72,..., %), а также проверочная матрица В кода Рида—Соломона типа III, то проверочная матрица обобщенного кода может быть представлена как произведение С = В ■ D.

1,..., п.

А.Т. Обобщенные коды БЧХ

Обобщенному коду ВСНг{п, д) принадлежат все вектора кода ВСНг(п, й!), координаты которых принадлежат подполю поля ¥д.

Такой код можно задать с помощью проверочной матрицы над полем Если к — размерность кода ВСНг{п,д) над то размер проверочной матрицы будет п — к х п. Такая матрица может иметь вид А.2. В общем случае методы определения размерности к кодов ВСНг(п, с?) в настоящее время не известны.

А.8. Декодирование линейного кода

Известны три типа декодирования кода С. Задан вектор х' £ полученный на выходе канала с шумом.

1. Корреляционное декодирование. По предъявленному вектору х' находят одно или несколько кодовых словх € С, ближайших в метрике Хэммин-га к х'. Трудоемкость корреляционного декодирования нетривиальных кодов возрастает как экспоненциальная функция от их длины [92, 93]. Иными словами, трудоемкость декодирования сравнима с трудоемкостью силовой атакой — метода проб и ошибок с исчерпывающим перебором вариантов. Доказано, что задача корреляционного декодирования относится к классу NP-тpyдныx [82].

2. Декодирование в пределах кодового расстояния. Известно, что произвольный линейный код С над ¥ч с параметрами [п, к, с1}д, д, ^ Г^/2], допускает декодирование в пределах его кодового расстояния, сложность которого не превышает 0(тт(щк, п ("))> гДе £ = . Здесь — число кодовых слов кода С и 0(щк) — число операций, необходимых для перебора всех кодовых слов и сравнения каждого из них с х'. Число точек в шаре с центром в х равно ОХ*? — ^У • Тогда для перебора всех точек шара с целью нахождения среди них кодового вектора х потребуется выполнить не более О(п^=0 (")) операций сравнения. Для большинства распространенных на практике кодов известны алгоритмы декодирования, сложность которых возрастает как полином небольшой степени от п. Например, для декодирования обобщенного кода Рида—Соломона потребуется не более 0(п3) операций в F

3. Декодирование за пределами кодового расстояния. По вектору х' 6

отстоящему в метрике Хэмминга не слишком далеко от некоторого кодового слова х £ С, находят одно или несколько кодовых слов х Е С, находящихся на расстоянии ^ Iот х', где £ > \((1—1)/2]. Например, для кодов Рида—Соломона известен алгоритм Гурусвами—Судана с полиномиальной трудоемкостью декодирования [31]. Однако трудоемкость быстро возрастает с увеличением разности Д = £ — \(с1 — 1)/2]. Существует верхняя граница числа ошибок для которой декодирование невозможно. В частности, для алгоритма Гурусвами—Судана такая гра-

Приложение Б Некоторые разделы криптографии

В приложении приводятся сведения из тех разделов криптографии и криптоанализа, которые необходимы для понимания результатов глав I и III диссертационного исследования.

Б.1. Криптографические хэш-функции

Криптографические хэш-функции широко используются в составе различных криптографических механизмов. Таких, например, как процедура вычисления/проверки цифровой подписи и кода аутентичности сообщения. Подчеркнем, что для задач диссертационного исследования важны именно криптографические хэш-функции. В дальнейшем под хэш-функцией будем подразумевать функцию, которая удовлетворяет ряду требований, вытекающих из специфики криптографических задач. В полном объеме теория хэш-функций изложена в книгах [5, 75]. Настоящее приложение содержит материалы главы 9 из книги [75] в переработанном и сокращенном виде.

Различают два типа хэш-функций: безключевые и ключевые. Для первых будем использовать обозначение /г(-), а для вторых — h(-, •). Очевидно, что различие между безключевой и ключевой функциями состоит в наличии дополнительного аргумента для последней. Как следует из названия, в качестве такого аргумента выступает секретный ключ. Задачи диссертационного исследования позволяют ограничится функциями вида h(-).

Рассмотрим отображение вида/л : {0,1}* —{0,1}л. Пусть отображение реализуется с помощью функции /г(-). Тогда на вход h(-) подается двоичная последовательность х, произвольной, но конечной разрядности, а в резуль-

тате вычислений возвращается значение у = к(х) — двоичная последовательность фиксированной разрядности Л. Далее по тексту такую функцию будем называть Л-разрядной. Значение хэш-функции иногда называют «цифровым отпечатком пальца»1 или «дайджестом».

Функция Н(-) обладает следующими свойствами.

Сжатие. Отображает входную последовательность х, произвольной, но конечной разрядности 7, в двоичную последовательность у фиксированной разрядности Л, Л ^ 7.

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

В дальнейшем будем придерживаться сложившейся терминологии: для обозначения аргумента х и значения у функции /г(-) воспользуемся названиями прообраз и образ соответственно.

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

Пусть задана функция /г(-), а также пара прообразов х, х' и образов у, у'. Тогда упомянутая функция возможно обладает следующими дополнительными свойствами.

С трудноразрешимым прообразом. Означает трудноразрешимость задачи нахождения произвольного прообраза для любого образа из наперед заданного множества. По-другому, нахождение произвольного прообраза х' для заданного образа у = Н(х), такого, что Н{х') = у, при условии, что ни один прообраз образа у, в том числе и ж, не известен.

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

1 Данный термин не имеет прямого отношения к биометрии.

соответствует тот же образ, что и для известного прообраза. По-другому, для заданного прообраза х найти произвольный прообраз х' ф х, такой, что Н(х) = К{х').

С трудноразрешимыми коллизиями. Означает трудноразрешимость задачи нахождения двух различных прообразов х и х\ которые соответствуют одному и тому же образу. По-другому, таких прообразов, что и{х) = Н(х'), при условии отсутствия ограничений на выбор х и х'.

Поясним смысл описанных выше свойств. Рассмотрим схему цифровой подписи, в которой подписью заверяется не исходная последовательность х, а образ у — Н(х). Тогда функция /г(-) должна гарантировать трудноразрешимость нахождения второго прообраза, в противном случае злоумышленник способен выполнить подлог— найти такой прообраз х' ф х, что Н(х) = к(х'). Если злоумышленник способен навязывать последовательности, которые заверяются цифровой подписью, то его задача упрощается и вместо нахождения некоторого второго прообраза х' фиксированного прообраза х, ему достаточно найти произвольную пару (х,х), для которой существует коллизия, а именно, Н(х) = Н{х). Тогда функция /г(-) должна также гарантировать трудноразрешимость нахождения коллизий.

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

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

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

Атака I. Для заданного образа у найти прообраз х, такой, что у = И(х),

или для заданной пары (х, Ь(х)) найти второй прообраз х', такой, что к(х') = К(х).

Атака II. Найти пару прообразов х и х', х ^ х' таких, что Н{х') = Н{х).

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

Здесь «||» используется для обозначения конкатенации двоичных последовательностей. Тогда Н(-) — (Л + 1)-разрядная хэш-функция с трудноразрешимыми коллизиями, но трудноразрешимость прообраза для такой функции не гарантируется. Рассмотренный пример имеет вырожденный характер, но наглядно демонстрирует, что факт трудноразрешимости коллизий не означает трудноразрешимости прообраза для конкретного образа. Тем не менее, для большинства используемых на практике хэш-функций с трудноразрешимыми коллизиями предположение о трудноразрешимости прообраза следует считать вполне обоснованным.

Для нахождения прообраза или второго прообраза Л-разрядной хэш-функции методом силовой атаки достаточно опробовать не более 2Л претендентов. Если выбор прообраза ничем не ограничен, то для нахождения различныхх и х' таких, что Н(х) = Н(х'), достаточно опробовать не более 2А/2 претендентов. Оценка трудоемкости опирается на факт теории вероятностей, известный как «парадокс дней рождения». Поясним это на примере задачи о размещении.

Н(х)

1\\х, если х имеет разрядность Л О || д(х), в противном случае.

Предположим имеется q шаров. Пронумеруем их от 1 до q. Имеется также корзина с N ячейками, где N ^ q. Суть испытания заключается в последовательном помещении шаров в корзину в соответствии с присвоенными номерами, начиная с первого. В результате такого помещения шар может попасть в любую из N ячеек с равной вероятностью. Коллизия возникает тогда, когда в конкретную ячейку попадает не менее двух шаров. Оценим вероятность коллизии C(N,q). В Приложении В доказано, что

для 1 < q < у/2N. Тогда C(N, q) « 1 для q « у/2N.

Покажем как этот факт может быть использован для отыскания коллизий хэш-функции. С этой целью будем трактовать каждый образ как отдельную ячейку. При бросании «шара» Х{ в корзину он может попасть в ячейку i/i, где г/i = h(xi). Тогда факт коллизии, или попадание в конкретную ячейку двух шаров, означает, что два различных прообраза Х{ и Xj соответствуют одному образу при условии функции h(-). Оценим вероятность этого события как функцию q. Обозначим через Prob{у/) вероятность того, что «шар» попадает в ячейку yj, а именно, вероятность того, что h(xj) = yj, Xj er F^. Предположим, что известна обратная функция для прообраза h~l{Vj) = ixj G F2 : h(*j) = Vj}, т0ГДа

Probfe) = ЦМ

Предположим, что — множество образов и N = Тогда, исходя из предположения Prob(yi) — Prob(i/2) = • • • = РгоЬ(улг), можно заключить, что

\h-\yi)\ = \h-\y2)\ = ... = \h-\yN)\. (Б.1)

Функции, для которых выполняется Б.1, называются регулярными. Если h(-) относится к классу регулярных, то вероятность коллизии оценивается как

С (И, д),ив результате проверки д « у/Ш= у/ЩЩ претендентов коллизия может быть найдена с близкой к единице вероятностью. Если к(-) не относится к классу регулярных, то коллизия может быть найдена за меньшее количество опробований.

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

Ниже приводится описание «атаки квадратного корня». Напомним, что расстояние в метрике Хэмминга с£(х, у), а также вес Хэмминга \лЛ:(х), определены в Приложении А. Тогда для х, у 6

фс,у )<п/сг, (Б.2)

где 2 < а < п для всех о | п. Ограничение Б.2 означает, что в д-ичных последовательностях х и у различаются не менее половины всех координат.

Вход. Исходная и целевая двоичные последовательности хх, Х2 £ А-раз-рядная односторонняя хэш-функция 1г(-).

1. I = 2Л//2, % := 0.

2. г := г + 1.

3. Выбирает с^, такое, что <¿(0^X1) ^ п/а.

4. Сохраняет в памяти запись вида {1г(оц), ац}.

5. Если г < то к 2.

6- з ■= Э + 1-

7. Выбирает такое, что х2) ^ п/а.

?

8. Проверяет Ь(^) = для каждого о^, г = Вероятность совпадения не ниже 2~Л/2.

9. Если /г<(Д/) = то на Выход.

10. Если у < то к 6.

Выход. Двоичные последовательности х'х, х'2 <Е ¿(х'^хх) ^ п/а, (¿(х^хг) ^ п/а такие, что /¿(х^) = /¿(х2). Тогда цифровая подпись для х'х может быть использована для х2.

Для экономии памяти поступим следующим образом. Введем модифицирующую функцию такую, что р(хьу) = х'х и ¿(хьхУ < п/ст, х^хх € ^ для заданного Л-разрядного образа у. Причем значение каждого разряда у используется в качестве признака, который управляет изменением значения соответствующего разряда прообраза хх. Например, если й-ый разряд у равен 1, то значение I-го разряда хх меняется на противоположный. Если хх фиксировано, то функция <?(•, •) отображает значение хэш-функции в аргумент. Тогда логично воспользоваться обозначением дХ1(у) = х^. Предположим также, что функция дХ1(-) инъективна и различные х'х соответствуют различным у. Воспользуемся признаком четности веса Хэмминга для разграничения пространства образов на две приблизительно одинаковые части. Определим автоморфную функцию отображения г(-) следующим образом.

, ч I НЗхЛу)), если мЛ(у) четное г(у) = <

I ^(дХ2(у)), если wt(у) нечетное.

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

с вероятностью 0.5. Тогда без потери общности можно предположить, что %Х1Ы) = %х2(У)) и Х1 = х2 = 9*2(.у') Для различных Хх и х2.

Следовательно, Ь(х'1) = /г,(х'2).

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

Таблица Б.1. Криптостойкость А-разрядных хэш-функций

Хэш-функция Свойства Объем перебора Тип атаки

Односторонняя Трудноразр. прообраза Трудноразр. 2-го прообраза 2Л 2Л Нахождение прообраза Нахождение 2-го прообраза

С трудноразр. коллизиями Трудноразр. коллизии 2А/2 Нахождение коллизии

В прикладных задачах часто применяют следующие хэш-функции [94—

99].

Б.2. Блочные шифры

Задачи диссертационного исследования позволяют ограничится рассмотрением симметричных шифрсистем на основе блочных шифров. Симметричными называются такие шифрсистемы, в которых один и тоже секретный ключ используется как для зашифрования, так и для расшифрования. Для изучения теории симметричных шифрсистем следует обратиться к книгам [5, 75]. Настоящий раздел содержит материалы главы 7 из книги [75] в переработанном и сокращенном виде.

Блочный шифр есть функция, отображающая п-разрядный двоичный блок открытого текста в п-разрядный двоичный блок шифртекста. Число п будем называть длиной блока (блочной длиной). Упомянутая функция параметризуется /с-разрядным ключом К, который принимает значения из

подмножества /С (ключевое пространство) множества всех /с-разрядных двоичных векторов Предполагается, что ключ случаен. Длины блоков открытого текста Р и шифртекста С совпадают. Далее по тексту под п-разрядным блоком будем подразумевать последовательность из п двоичных разрядов.

Функция обратима и при фиксированном ключе есть суть биективное отображение для п-разрядных блоков открытого текста и шифртекста. Такую функцию можно также интерпретировать как перестановку. Причем каждый ключ отвечает за свою перестановку. Совокупное число ключей равно |/С|, тогда эффективный размер ключа равен |/С| при условии, что /С = Ук- Если ключи равновероятны и каждый задает свое биективное отображение, то энтропия ключевого пространства также равна \К\.

Определение. Тогда п-разрядный блочный шифр есть функция вида Е : Уп х /С —>• Уп, такая, что для каждого ключа К £ К. существует обратимое прямое отображение Ек(Р), или функция зашифрования для К, из Уп в Уп. По построению существует обратное отображение Б к {С) или функция расшифрования для К. Тогда С = Ек(Р) означает, что блок шифртекста С получен в результате зашифрования блока открытого текста Р с помощью ключа К и Р = Дк(С).

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

Согласно Определению Б.2 блочный шифр реализует всевозможные подстановки. Тогда для представления ключа такого п-разрядного случайного блочного шифра потребуется к^2(2п!) « (п — 1.44)2П разрядов, что приблизительно в 2п раз больше числа разрядов в блоке открытого текста/шифртекста. Отметим, что с практической точки зрения, такой подход представляется необоснованным.

Определение. Назовем случайным шифрующим отображением функцию Е, которая отображает блок открытого текста из Уп в блок шифртекста из Ут, т > п, при условии существования некоторого множества случайных чисел 71 = 14, а именно, Е : Уп х /С х 71 Ут. Тогда для каждого ключа К Е /С и Я Е 71 функция зашифрования Е§(Р) отображает Р ЕУп в Ут. По построению существует обратная функция расшифрования (С), которая отображает С ЕУт в Уп.

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

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

1. Злоумышленник имеет доступ к данным, которые передаются по открытому каналу связи.

2. Злоумышленнику известны функции зашифрования и расшифрования, но ключ недоступен.

Известны следующие разновидности атак на блочные шифры.

1. На основе шифртекста. Злоумышленник не располагает никакой дополнительной информацией кроме шифртекста.

2. На основе открытого текста. Злоумышленник располагает достаточных количеством пар открытый текст/шифртекст.

3. На основе выборочного открытого текста, Злоумышленник может выбирать открытый текст и получать соответствующий шифртекст. Адаптивный вариант атаки заключается в выборе текущего открытого текста в зависимости от того, какие пары открытый текст/шифртекст были выбраны ранее.

Отметим, что криптостойкость по отношению к атаке на основе выборочного открытого текста гарантирует также криптостойкость по отношению к атакам на основе открытого текста и шифртекста.

Кроме перечисленных выше, возможны также атаки на основе выборочного шифртекста и на основе связанных ключей. Предполагается, что для осуществления атаки на основе выборочного шифртекста злоумышленник должен располагать достаточным количеством пар открытый текст/шифр-текст для некоторого количества шифртекстов по выбору. А для осуществления атаки на основе связанных ключей злоумышленник должен иметь возможность зашифровывать открытые тексты как на ключе, который должен быть раскрыт, так и на вспомогательных ключах. При этом все ключи связаны некоторой функциональной зависимостью. На практике это означает, что долговременный ключ записан в энергонезависимую память специализированного устройства, работа с которым возможна только в режиме «черного ящика». Устройство имеет два входа и один выход, назначение которых меняется в зависимости от исполняемой операции: зашифрования или расшифрования. На один из входов всегда подается ключ. Если на ключевой вход такого устройства ничего не подается, то зашифрование/расшифрование выполняется на долговременном ключе, который считывается из памяти устройства. Если ключевой вход активизирован, то устройство игнорирует долговременный ключ и выполняет зашифрование/расшифрование на введенном ключе.

Трудоемкость наилучшей из известных атак — основной критерий оцен-

ки криптостойкости блочного шифра. При оценке трудоемкости принимают во внимание следующие аспекты.

1. Объем данных. Необходимое число п-разрядных блоков.

2. Объем памяти. Необходимый объем памяти для хранения блоков/вспомогательных данных.

3. Трудоемкость обработки. Число операций, необходимое для обработки блоков или однократного заполнения выделенной памяти.

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

Криптостойкость зависит также от длины блока п. Если п мало, то возможна атака с использованием специализированного словаря открытых текстов или словарная атака. Такой словарь может быть организован как набор пар открытый текст/шифртекст для фиксированного ключа. Чем больше пар, тем больше объем памяти и выше вероятность определения шифртек-ста. Полный словарь состоит из 2п пар открытый текст/шифртекст и имеет меньший объем, если открытый текст избыточен. Кроме этого, если словарь состоит из 2П//2 таких пар, и около 2П/2 блоков шифртекста получено из открытого канала, то в соответствии с «парадоксом дней рождения» (см. Приложение В), какой-то из полученных шифртекстов будет обнаружен в словаре с вероятностью близкой к единице.

Блочный шифр гарантирует совершенную секретность, если обеспечивается статистическая независимость открытого текста и шифртекста.

Следующие критерии используются для оценки блочных шифров на практике.

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

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

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

4. Размер блока. Влияет как на криптостойкость, — чем больше, тем выше криптостойкость, — так и сложность реализации, — чем больше, тем дороже реализация. Кроме этого, способен влиять на производительность. Например, если разрядность исходного сообщения не кратна разрядности отдельного блока открытого текста и необходимо выполнить «набивку»2.

2 Заполнить свободные позиции случайными символами.

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

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

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

Для п-разрядного блочного шифра с ^-разрядным ключом и некоторым количеством (["(& +4)/п~|) известных пар открытый текст/шифртекст, таких, что зашифрование выполнялось с помощью фиксированного ключа К, неизвестный ключ К может быть раскрыт методом силовой атаки или перебором всевозможных претендентов из /С в среднем за 2/с~1 опробований. С этой целью для каждого претендента выполняют расшифрование С. Если в результате получен открытый текст Р ф Р, то ключ отбраковывается. Число ложных ключей, которые дают отображение С в Р, зависит от относительного размера кип. Неопределенность устраняется дополнительной проверкой претендента с помощью пары (Р\С'). Как правило, для раскрытия К достаточно проверить |/С|/2 претендентов.

Определим двойное зашифрование как преобразование вида

Е(х) = ЕК2(ЕК1(Х)),

где через Ек обозначен блочный шифр Е с ключом К.

При двойном зашифровании силовая атака предполагает опробование 22к различных /с-разрядных ключей. Атака, известная под название «встреча посередине», позволяет сократить объем перебора до 2к опробований за счет 2к дополнительных ячеек памяти. Пусть задана пара (Р, С), вычисляем Мг — Е{(Р) для 2к различных ключей К\ = г и сохраняем проиндексированные пары (М{, г) в долговременной памяти. Расшифровываем С с применением 2к ключей К2 = ] и для каждой пары {М^, где М= И ¿(С), проверяем выполнение равенства М) = М{ для каждого М{ из ранее сформированной таблицы. Поскольку Е^Р) = М = ^(С), то факт неравенства позволяет отбраковывать претендентов (г, ]). Также как и в случае однократного зашифрования, существует некоторое количество ложных ключей. Неопределенность устраняется дополнительной проверкой претендентов с помощью вспомогательной пары (Р;, С').

Можно сократить объем памяти угадыванием фиксированных э разрядов для каждого из ключей К\ и К2, 0 ^ 5 ^ к. Тогда в каждой таблице будет по 2к~в записей (угаданные разряды позволяют исключить 2е записей), но для опробования всевозможных претендентов потребуется проверить 2Э • 2е пар. Соответственно понадобится память для хранения 2 • 2к~в записей, а объем перебора возрастет до 22в • 2к~8 = 2к+в опробований.

На практике применяют блочные шифры из [100].

Приложение В Парадокс дней рождения

Оценки вероятности коллизии необходимы для понимания методов, представленных в разделе Б.1. Краткое, но ясное изложение таких оценок содержится в приложении к публикации [101].

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

Утверждение 2. Обозначим через С (А/", д) вероятность как минимум одной коллизии при случайном размещении д ^ 1 шаров в корзине с N ^ д ячейками. Тогда

Кроме этого

. С(7У,д) ^ 1 - , (В.2)

и для 1 < д ^ л/т

(В.З)

Следующее неравенство используется в доказательстве Утверждения 2.

Утверждение 3. Для произвольного вещественного числах € [0,1] справедливо неравенство

— • х < 1 — е~хх ^ х. 113

Доказательство Утверждения 2. Обозначим чере С{ событие, когда при помещении шара с номером г в корзину возникает коллизия. Тогда РгоЬ[С^] не превышает (г — Когда шар с номером г помещают в корзину, то имеется

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

С( = РгоЬ[С1 УС2У... УСЧ]

< РгоЬрх] + РгоЬ[С2] + ... + РгоЬ[Су

0 1

<--1---ь ... + -—

^ N N N

= д(д- 1) 2АГ '

Получим оценку нижней границы. Для этого обозначим через ^ противоположное событие, когда при помещении шара с номером % в корзину коллизия не возникает. Очевидно, что если при помещении % шаров в корзину коллизии не возникает, то все эти шары должны попасть в различные ячейки. Поэтому вероятность такого события при помещении {г + 1)-го шара равна в точности {И - г)/И. То есть,

N — I г

РгоЬ[А+1|Д] = — = 1 - -.

Заметим также, что РгоЬ^х] = 1. Вероятность не возникновения коллизии в конце испытания можно вычислить следующим образом

1 = РгоЬ[Д,

= Probf.Dgl.Dg_i] • РгоЬр9_1

7-1

П РгоЬ[А+1| А]

г=1

ЙН)- <в-4>

г=1

Заметим, что г/Ы ^ 1. Воспользуемся неравенством 1 — х ^ е х для каждого члена произведения В.4. Тогда произведение В.4 ограничено сверху как <7-1

Д = е-^-2/Ы-...-{я-1)/Ы = ед(д-1)/2Н_

г=1

Объединим результаты и получим следующее неравенство

которое совпадает с оценкой В.2 из Утверждения 2.

Докажем состоятельность оценки В.З. Известно, чтод(д —1)/2N ^ 1, так как д

Следовательно, можно воспользоваться неравенством 1-е х ^ (1 — е~~1)х для получения следующей оценки

Доказательство завершается вычислением константы 0.5(1 — 1/е) « 0.3. □