Главная » 2014»Сентябрь»30 » Скачать Построение высокоскоростных квантовых генераторов случайных чисел для систем защиты информации. Архангельская, Анна Васильевна бесплатно
06:38
Скачать Построение высокоскоростных квантовых генераторов случайных чисел для систем защиты информации. Архангельская, Анна Васильевна бесплатно
Построение высокоскоростных квантовых генераторов случайных чисел для систем защиты информации
Диссертация
Автор: Архангельская, Анна Васильевна
Название: Построение высокоскоростных квантовых генераторов случайных чисел для систем защиты информации
Справка: Архангельская, Анна Васильевна. Построение высокоскоростных квантовых генераторов случайных чисел для систем защиты информации : диссертация кандидата технических наук : 05.13.19 / Архангельская Анна Васильевна; [Место защиты: С.-Петерб. политехн. ун-т] Москва, 2008 182 c. : 61 08-5/287
Объем: 182 стр.
Информация: Москва, 2008
Содержание:
Обозначения и сокращения
Введение
1 Основные характеристики и методы построения ГСЧ
11 Выбор корректной терминологии
12 Классификация ГПСЧ и ГСЧ
13 Анализ современных ГПСЧ и ГСЧ
14 Выводы
2 Структура ИСС и ГСЧ, основанных на квантовых событиях
21 Анализ методов построения ГСЧ
22 Описание макета ГСЧ
23 Блок генерации случайных чисел
24 Применение схемы с затвором генератора
25 Обоснование случайности используемого физического процесса
26 Выводы
3 Методы и методика статистического тестирования ГСЧ
31 Тестирование двоичныхпоследовательностей
32 Критерии принятия решения о прохождении теста
33 Методика тестирования ГСЧ с использованием пакета NIST STS
34 Методика тестирования недвоичных последовательностей
35 Выводы
4 Исследование свойств ИСС и ГСЧ, основанного на измерениях интенсивности квантовых событий
41 Относительные частоты и совместные распределения случайных величин
42 Энтропия и независимость отсчетов ИСС
43 Исследование с использованием методики тестирования недвоичных последовательностей
44 Выводы
5 Применение разработанного высокоскоростного квантового ГСЧ в средствах защиты информации
51 Рекомендации по применению квантового ГСЧ
52 Применение совершенно стойких шифров
53 Одноразовая ЭЦП
54 Аутентификация типа «запрос-ответ»
55 Усовершенствование ключевых расписаний
56 Выводы
Введение:
Случайность пронизывает все уголки реального мира. С развитием науки стало понятно, что случайность - это не просто следствие недостаточности детерминистских знаний человека, но принципиальное свойство окружающего мира. Турбулентное движение жидкостей или газов, радиоактивный распад, тепловые шумы, пролет фотона через поляризационный фильтр - лишь некоторые примеры случайных явлений.
Главным неформальным признаком случайности является непредсказуемость, хотя степень непредсказуемости часто зависит от имеющейся информации и от уровня знаний. Это свойство позволяет говорить о случайности в идеальных детерминированных объектах, например, последовательности простых чисел, знаках десятичных разложений иррациональных чисел, поведении динамических систем.
Первые исследования случайных явлений были связаны с азартными играми, лотереями, страховым делом. Азартные игры и лотереи можно рассматривать и как исторически первые примеры практической реализации и применения генераторов случайных чисел (ГСЧ), т.е. устройств, которые порождают непредсказуемые последовательности объектов, например, символов или чисел при бросании монет или игральных кубиков, наборов игральных карт, номеров шаров при извлечении их из барабана.
Область применения ГСЧ существенно расширилась в середине XX века вследствие бурного развития двух научных направлений: вычислительных методов, в первую очередь, статистического моделирования, и криптографии. Возможность реализации ГСЧ для указанных применений была обеспечена, с одной стороны, развитием теории вероятностей и математической статистики, а с другой - становлением радиоэлектроники и созданием ЭВМ, позволивших быстро проводить сложные вычисления.
Возможность использования ГСЧ для численного вычисления интегралов, решения дифференциальных уравнений с частными производными и других математических задач, как правило, обосновывается законом больших чисел или центральной предельной теоремой. Но, например, методы построения рандомизированных алгоритмов решения комбинаторных и оптимизационных задач используют и другие результаты теории вероятностей.
Теория вероятностей стала одной из математических основ криптологии после того, как Клод Шеннон в работе «Теория связи в секретных системах» [1] доказал теорему о возможности построения совершенного шифра. Конструктивная часть этой теоремы в качестве примера совершенного шифра предлагала процедуру познакового сложения открытого текста и ключа, образованного независимыми равномерно распределенными знаками того же алфавита (шифр Вернама . или одноразового блокнота). Доказательство этой теоремы поставило перед создателями криптографических систем следующую основную задачу - приближение свойств ключевых последовательностей и шифрованного текста к свойствам последовательностей равномерно распределенных независимых случайных величин, т.е. по существу, построение генераторов псевдослучайных чисел (ГПСЧ), выходы которых трудно отличимы от действительно случайных чисел.
При построении ГПСЧ используются детерминированные алгоритмы, а математической моделью ГПСЧ являются автономные конечные автоматы, в которых случайным образом выбирается начальное состояние.
Критерий близости псевдослучайной последовательности к действительно случайной последовательности зависит от области применения псевдослучайных чисел. Например, в методе Монте-Карло обычно используются только закон больших чисел и центральная предельная теорема, и в таких ситуациях, как правило, некоррелированность псевдослучайных чисел является достаточной [2 — 5]. Однако для моделирования с использованием параллельного метода Монте-Карло требуются случайные числа, удовлетворяющие более строгим критериям [3-7], также как и для вычисления числа к с использованием теоремы Эрнесто Чезаро (Ernesto Cesaro) [8, 9], связывающей НОД двух случайно выбранных целых чисел и число тс. Это и привело к разработке ряда так называемых физических тестов на случайность, основанных на стандартных вычислительных приложениях, таких как моделирование методом Монте-Карло или моделирование с использованием случайных блужданий [2, 10].
Использование случайных переменных может заменить сложные для обоснования математические предположения [11]. Наиболее известными примерами являются тест на простоту Соло-вэй (Solovay) - Штрассен (Strassen), использующий метод Монте-Карло и детерминированный тест на простоту Гари Миллера (Gary Miller), основанный на расширенной гипотезе Римана [12].
При применении случайных чисел в указанных приложениях даже в случае использования неудовлетворительного ГПСЧ можно повторить вычисления с другим генератором и сравнить полученные результаты. В то же время в криптографии с помощью ГПСЧ строится защита' важной информации от злоумышленника, и исправить последствия применения некачественного генератора, как правило, невозможно. В криптографических приложениях формируются наиболее жесткие критерии близости последовательностей к случайным, т.к. качество генератора напрямую связано со стойкостью криптографических алгоритмов. Этими факторам обуславливается то, что в настоящее время многие криптографические приложения зачастую используют ГСЧ, а не ГПСЧ.
В то же время криптографические приложения предъявляют все более высокие требования к быстродействию ГСЧ. Так в некоторых системах шифрованной связи случайным образом генерируются не только ключи абонентов, но и разовые ключи сообщений, шифрующие, последовательности или гамма [13]. Во многих криптографических протоколах используются случайные числа[14 - 16], например, в протоколах аутентификации «запрос-ответ» случайные числа служат для противодействия атакам типа «повтор». Случайные числа применяются и для обеспечения безопасного вероятностного шифрования [17]. Можно представить себе, сколько требуется ключевой информации для банковской системы, обрабатывающей в моменты пиковой нагрузки десятки, и даже сотни тысяч транзакций в секунду. Алгоритмы цифровой подписи, помимо секретного ключа подписывающего, требуют генерации случайного значения, используемого в качестве разового секретного ключа, также случайные числа применяются и в других криптографических конструкциях [18 - 23].
Случайность и криптография тесно взаимосвязаны, ведь основная цель криптографических систем состоит в том; чтобы преобразовать неслучайные осмысленные открытые тексты в кажущуюся случайной беспорядочную последовательность символов. Это свойство криптосистем может быть использовано и для генерации псевдослучайных последовательностей.
Другой аспект взаимосвязи между свойствами случайных последовательностей и криптографией еще более интересен. Даже самые лучшие криптосистемы, были бы бесполезны, если криптоаналитик мог бы угадывать используемый в них ключ. Это замечание, очевидно, относится как к симметричным, так и: к асимметричным криптосистемам. По всей видимости, не существует лучшего способа предотвращения подобных атак, чем выбор ключа действительно случайным образом.
Однако многие практические реализации криптографических средств не имеют надежных источников действительно случайных значений, таких как шум электрических цепей или время между пролетом частиц в счетчике Гейгера [24]. И именно отсутствие случайности в так называемых телеграфных ключах как раз и было главной причиной вскрытия немецкой шифровальной машины Энигмы (Enigma) [25 - 27]. Зачастую вместо генерации случайного числа для выработки заменителей требуемых параметров, - случайных величин, используется математическое преобразование (ГПСЧ). В некоторых случаях на вход ГПСЧ подаются случайные значения от различных источников с низкой энтропией, а генератор, в свою очередь, выдает последовательности, практически неотличимые от действительно случайных.
Доказано, что любая алгоритмическая реализация теоретически идеализированного представления о случайности будет несовершенной [28], т.е. истинно случайная последовательность не может быть вычислена и, следовательно, она должна быть непериодической бесконечной последовательностью. Следует отметить, что многие реализации ГПСЧ не являются стойкими к криптографическому анализу. Кроме того, одни только статистические свойства вырабатываемых чисел не свидетельствуют о стойкости генератора к криптографическим атакам, а являются лишь предпосылкой для этого. В результате именно используемый ГПСЧ (или ГСЧ) часто оказывается причиной уязвимости многих реальных систем криптографической защиты информации [29 - 31], а вопросами их построения и исследования занимаются такие отечественные и зарубежные ученые, как А. Зубков, А. Щербаков, Д. Кнут, Б. Шнайер, Д. Келси, А. Шамир, М. Наор, О. Рейнголд, Н. Ферпосон.
Быстродействие большинства выпускаемых серийно генераторов ограничено используемыми физическими процессами и обычно не превышает 100 Кбит/с. Однако в августе 2004 года швейцарская компания ID Quantique выпустила ГСЧ, основанный на квантовых эффектах, а именно на прохождении или отклонении фотона при попадании на полупрозрачное зеркало [32]. Хотя его скорость равняется 4 Мбит/с, это также не удовлетворяет современным потребностям. Более того, из-за отсутствия подробного описания задача оценки его характеристик представляется неразрешимой. По этим причинам является актуальной разработка отечественного высокоскоростного криптографически стойкого ГСЧ. Решению данной проблемы и посвящено настоящее исследование.
Целью диссертационной работы является повышение стойкости механизмов защиты информации за счет разработки и использования метода построения высокоскоростного ГСЧ, основанного на квантовом процессе. Для увеличения скорости выработки случайных чисел предлагается использовать новый класс источников случайных событий (ИСС), выходные последовательности которых являются небинарными. Такие ИСС могут быть основаны на квантовых процессах, возникающих, например, при излучении фотонов источником света слабой интенсивности и их регистрации.
В соответствии с поставленной целью в диссертационной работе решаются следующие задачи:
• Анализ существующих методов построения ГСЧ.
• Обоснование использования небинарных последовательностей для построения высокоскоростных ГСЧ.
• Выбор физического процесса, характеризующегося недвоичной величиной, который может быть использован для генерации случайных чисел, и разработка основанного на нем ИСС;
• Разработка модели ГСЧ, основанных на квантовых событиях, использующих в качестве ИСС световой поток слабой интенсивности, измеряемой фотоэлектронным умножителем (ФЭУ).
• Исследование существующих методов статистического тестирования ГСЧ и разработка методики тестирования небинарных последовательностей.
• Разработка ГСЧ, соответствующего предложенной модели, анализ его характеристик и выработка рекомендаций по его практическому применению.
Основными методами исследований, используемыми в работе, являются методы комбинаторики, теории вероятностей, математической статистики, теории информации и криптологии.
Работа состоит из введения, 5 глав, заключения, списка литературы и 11 приложений.
В первой главе приводится обзор современных ГСЧ, исследуются и уточняются методы и пути решения поставленной научной'задачи. В работе проанализирован ряд известных ГСЧ, среди которых генераторы, описанные в стандарте ANSI Х9.17 и в американском стандарте на цифровую подпись DSS, и ГСЧ, основанные на квантовых процессах. На основании сравнения рассмотренных ГСЧ по таким показателям, как быстродействие, физический процесс, лежащий в основе ИСС, и энтропия случайной величины, соответствующей выходному значению генератора, сделан вывод о перспективности построения ГСЧ, основанных на квантовых событиях.
Вторая глава посвящена исследованию методов построения ГСЧ, анализу требований, предъявляемых к ним, разработке структуры ИСС и обоснованию выбора физического процесса, положенного в его основу. В работе доказана целесообразность использования в блоке генерации схемы, позволяющей управлять изменениями состояния, так называемого затвора генератора, обеспечивающего стойкость ГСЧ к компрометации его состояния, оценены некоторые ее параметры. Также обоснована случайность используемого квантового процесса как с позиций квантовой физики, так и при помощи описания его вероятностной схемы.
В третьей главе рассматриваются задачи разработки методики исследования ГСЧ и построения статистических тестов, применимых к недвоичным последовательностям. Предложена методика тестирования недвоичных последовательностей, позволяющая исследовать ИСС разработанного типа, которая направлена на проверку наиболее важного показателя качества ГСЧ - непредсказуемости получаемых значений и решает задачу обобщения методов статистического тестирования последовательностей на случай более сложных распределений, отличных от равномерного.
В четвёртой главе рассматриваются вопросы, связанные с получением и анализом таких характеристик разработанного ГСЧ, как независимость случайных величин, соответствующих различным отсчетам ИСС, их коэффициентов корреляции и энтропии отсчета. Проведенная экспериментальная проверка предложенных принципов построения высокоскоростных ГСЧ подтверждает обоснованную в работе независимость элементов выходных последовательностей разработанного ИСС, что позволяет использовать его при построении высокоскоростных ГСЧ, применяющихся в средствах защиты информации.
В пятой главе описываются особенности практического применения предложенного класса ГСЧ для решения прикладных задач, формулируются требования к основным компонентам ГСЧ. Показано, что повышение быстродействия ГСЧ приводит к повышению стойкости реализации механизмов защиты информации на примере одноразовой электронной цифровой подписи (ЭЦП), схемы аутентификации «запрос-ответ» с использованием симметричного алгоритма шифрования и протокола односторонней аутентификации с использованием случайных чисел. Обосновано, что применение разработанного высокоскоростного ГСЧ позволяет увеличить стойкость дискового шифрования и реализации некоторых алгоритмов шифрования за счет увеличения длины ключ и незначительной модификации ключевого расписания.
Заключение содержит основные выводы и результаты, полученные в диссертационной работе.
В ходе исследований был получен ряд результатов, характеризующихся научной новизной:
• Предложен и обоснован подход к построению высокоскоростных ГСЧ на основе физических процессов, характеризующихся небинарной величиной. В качестве указанного процесса предлагается использовать излучение и регистрацию фотонов.
• Предложена структура ИСС, основанного на выбранном физическом процессе, состоящего из источника элементарных частиц слабой интенсивности, приемника частиц, имеющего квантовую природу и позволяющего получать мгновенную аналоговую характеристику квантовых явлений, и аналого-цифрового преобразователя (АЦП).
• Разработана модель ГСЧ на основе предлагаемого ИСС, рассматривающая процесс как с позиций квантовой физики, так и при помощи описание его вероятностной схемы.
• Разработана методика статистического тестирования недвоичных последовательностей, позволяющая исследовать свойства предложенного ИСС, основанная на проверке гипотезы независимости случайных величин, соответствующих отсчетам измерителя интенсивности квантовых событий, и методе отбеливания фон Неймана.
• Реализован опытный образец ГСЧ, оценены его основные характеристики, в частности скорость, которая на два порядка превышает показатели современных генераторов.
• Составлены и обоснованы рекомендации по выбору параметров ИСС и ГСЧ, основанных на квантовых событиях, включающие в себя требования к используемому источнику элементарных частиц, ФЭУ и АЦП.
Новизна диссертационной работы подтверждена выполненным патентным поиском, в результате которого выявлен ряд изобретений, наиболее близких к разработанному ГСЧ [33 - 35].
Однако предлагаемый ГСЧ имеет существенные отличия от известных аналогов, самые значимые из которых заключаются в том, что для выработки очередного случайного числа оценивается количественная характеристика групповых квантовых событий. По тематике работы подана заявка на изобретение № 2007123264 от 21.06.2007.
Практическую ценность представляют:
• Методика тестирования выходных последовательностей ИСС и ГСЧ, позволяющая исследовать недвоичные последовательности, и ее программная реализация.
• Действующий макет ГСЧ, основанный на небинарном ИСС, позволяющий осуществлять генерацию статистически независимых последовательностей с высокой скоростью.
• Рекомендации по практическому применению разработанного класса ГСЧ и выбору их параметров.
Результаты работы представляют практическую ценность для обеспечения различных аспектов безопасности информации, в первую очередь, конфиденциальности и целостности, позволяют усовершенствовать системы распределения ключей, протоколы аутентификации и схемы ЭЦП.
На защиту выносятся следующие основные результаты работы: }
• Подход к построению высокоскоростных ГСЧ, основанный на применении небинарных последовательностей.
• Структура ИСС, содержащего источник элементарных частиц слабой интенсивности и приемник частиц, позволяющий получать мгновенную аналоговую характеристику квантовых явлений, пропорциональную количеству зарегистрированных частиц.
• Модель высокоскоростного ГСЧ, основанного на разработанном ИСС, выходы которого являются недвоичными величинами.
• Методика статистического тестирования недвоичных последовательностей, позволяющая исследовать свойства ИСС, основанных на процессах, характеризующихся многозначными величинами, например, интенсивностью физического процесса.
• Рекомендации по выбору параметров ИСС и ГСЧ, основанных на квантовых событиях.
Основные результаты исследований используются в ЗАО «Голлард» при проектировании защищенных систем обработки информации. Результаты диссертационной работы внедрены в учебный процесс на факультете «Информационная безопасность» Московского инженерно-физического института (государственного университета).
Результаты работы докладывались на Российской научно-технической конференции «Методы и технические средства обеспечения безопасности информации» (С.-Петербург, 2004
2007 гг.), на Всероссийской научно-практической конференции «Проблемы информационной безопасности государства, общества и личности» (Томск, 2005 г.), Международной научно-практической конференции «Информационная безопасность» (Таганрог, 2005 г.), Всероссийской научной конференции «Проблемы информационной безопасности в системе высшей школы» (Москва, 2005 - 2007 гг.), Международной конференции «Комплексная защита информации» (Суздаль, 2006 г.), Сибирской научной школе-семинаре с международным участием «Компьютерная безопасность и криптография» - SIBECRYPT'06 (Шушенское, 2006 г.) и SIBECRYPT07 (Горно-Алтайск, 2007 г.).
Работа поддержана грантом Министерства образования и науки РФ в рамках ведомственной научной программы «Развитие научного потенциала высшей школы» (2005 г.). По тематике работы подана заявка на изобретение № 2007123264 от 21.06.2007.
По теме диссертации опубликовано 17 печатных работ, в том числе 6 научных статей, из них 5 в изданиях, включенных в Перечень ведущих рецензируемых научных журналов, и 11 тезисов докладов.
