Содержание к диссертации
Введение
Глава 1. Основные понятия и методы 24
1.L Основные определения и понятия 24
1.2.Описание адаптивного критериях 27
1.3. Необходимые сведения из математической статистики и вспомогательные результаты 30
1.4. Адаптивный критерий хи-квадрат. Описание и теоретическое рассмотрение 31
Глава 2. Экспериментальные исследования эффективных генераторов криптографически стойких псевдо случайных последовательностей созданных на основе современных алгоритмов шифрования 35
2.1. Экспериментальные исследования эффективности генераторов псевдослучайных чисел базирующихся на криптографических алгоритмах RC5nRC6 36
2.2. Экспериментальные исследования эффективности генераторов псевдослучайных чисел базирующихся на современных криптографических алгоритмах 55
Глава 3. Экспериментальные исследования статистических свойств зашифрованных текстов на естественных языках и их применение к одной из задач криптографии 80
3.1 Алгоритм различения зашифрованных текстов на естественных языках и случайных последовательностей 81
3.2 Алгоритм различения зашифрованных текстов на естественных языках и случайных последовательностей на длинах выборки от 100 килобайт 92
Заключение 112
Литература 114
Список работ автора по теме диссертации 118
- Необходимые сведения из математической статистики и вспомогательные результаты
- Экспериментальные исследования эффективности генераторов псевдослучайных чисел базирующихся на современных криптографических алгоритмах
- Алгоритм различения зашифрованных текстов на естественных языках и случайных последовательностей
- Алгоритм различения зашифрованных текстов на естественных языках и случайных последовательностей на длинах выборки от 100 килобайт
Введение к работе
Актуальность темы*. Случайные и псевдослучайные числа широко используются в самых различных областях науки и техники. Они очень важны в математическом моделировании, в разработке численных методов, в программировании, криптографии и т. п. И если раньше ученые, нуждающиеся для своей работы в случайных числах, раскладывали карты, бросали кости или вытаскивали шары из урны, которую предварительно "как следует трясли" [10], то сейчас генератор случайных чисел встроен в любой компилятор и процессор компьютера. Например, Intel использует генератор случайных чисел в процессорах со второго полугодия 1999 года [7], Однако, такие генераторы, как правило, недостаточно надежны для криптографических приложений. На создание удовлетворительных псевдослучайных последовательностей с помощью численных методов затрачена масса усилий. В литературе можно найти множество работ по генераторам псевдослучайных чисел, а также различные тесты на случайность (например [4], [11], [35]), Тем не менее, проблема получения псевдослучайных чисел и их тестирования все еще актуальна, особенно для криптографии [31], и поэтому находится в центре внимания многих исследователей [20], [25], [26],
В научно-технической литературе числа, полученные с помощью компьютера, называются псевдослучайными, мы же, в дальнейшем для краткости, в некоторых случаях будем называть их проста случайными или случайными последовательностями. Каждую последовательность случайных чисел, перед использованием, необходимо тщательно проверить. Для приложений и задач, в которых требуются действительно
* Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (колы проектов: 99-01-00586» 03-01-00495) и 1NTAS-00-738 "Эффективное кодирование источников информации и связанные проблемы4.
"качественные" случайные числа, они проверяются специальным набором тестов. Формально генератор псевдослучайных чисел можно считать эффективным, если он проходит все известные статистические тесты. В связи с этим, статистические тесты важны и необходимы, также как и сами генераторы. Более того, генератор случайных чисел может считаться "идеальным1* только до тех пор, пока не появится тест, доказывающий обратное и "время жизни" генератора может на этом остановиться.
Необходимо отметить что, по сравнению с другими задачами, криптографические приложения предъявляют к генераторам случайных последовательностей намного более строгие требования, чем, скажем, вычислительные задачи. "Криптографическая" случайность - это не просто статистическая случайность, хотя и включает ее» Чтобы псевдослучайная последовательность была криптографически стойкой, она должна обладать следующими свойствами: генерируемые последовательности проходят все статистические тесты и их символы должны быть непредсказуемы. В то же время, как и любой криптографический алгоритм, генераторы криптографически стойких случайных последовательностей служат объектами "вскрытия" или "взлома". Поэтому, экспериментальные исследования генераторов криптографически стойких случайных последовательностей, разработка эффективных алгоритмов и методов их тестирования, их устойчивость к "взлому", т. е. проверка качества получаемых последовательностей-важная задача криптографии [10], [23], [31].
Среди задач тестирования последовательностей "на случай* ность" особый интерес представляет задача различения статистическими методами зашифрованных текстов и случайных последовательностей. Разработка эффективных алгоритмов и методов распознавания, или различения зашифрованных текстов хорошо известна
в криптографии (см., например, [10], [16], [34])- Решение этой задачи позволяет определить сам факт передачи по сетям связи (или хранения в информационных базах данных) зашифрованных текстов и, в силу этого, представляет несомненный интерес для разработчиков и исследователей систем защиты информации. Вместе с тем, трудность заключается в том, что современные шифры должны преобразовывать данные в последовательности, неотличимые от случайных настолько, насколько это возможно. Причем это одно из обязательных требований, предъявляемых к современным блоковым шифрам, — неотличимость зашифрованной последовательности от случайной, даже тогда, когда шифруемые данные заведомо не случайны, В частности, если на вход алгоритма шифрования подается текст на естественном языке, то на выходе он должен выглядеть как случайная последовательность. Заметим, что это условие предъявлялось Национальным институтом стандартов и технологии США (NIST) к блоковому шифру при организации конкурса на блоковый шифр 21-го века.
Как известно, для создания и хранения текстовой информации используются различные цифровые форматы (такие как "txt", "tex'\ "html", "doc", rtf\ "pdf1). В связи с этим, возникает вопрос о зависимости результата шифрования текста от формата, в котором он был пред-ставлен. Решение этой задачи представляет несомненный интерес для практической криптографии, разработчиков и исследователей систем защиты информации. Поэтому исследование влияния исходного формата шифруемых данных на возможность их различения в зашифрованном виде от случайных последовательностей важно с практической точки зрения.
Генерация "истинно" случайных чисел - одна из главных проблем возникающих при реализации любой криптосистемы. Огром-
нос количество приложений уязвимо из-за предсказуемости генерируемых чисел. Однако уже более двадцати лег назад было опубликовано множество научной литературы по датчикам случайных чисел (например, [II], [17]). Позднее Дж. Клсйнсн в [12] приходит, однако, к выводу, что "все еще нет высококачественного генератора псевдослучайных чисел11. Одновременно с ним известные специалисты Льюис [5] и Марсалья [21] указывают: "Многие широко распространенные генераторы фактически непригодны1'. Предостережение о распространенности плохих генераторов делает также И.М.Соболь в [6].
Вместе с тем, любое тестирование генераторов крипто графине-ски стойких случайных последовательностей остается частичным. Поэтому Ермаков С. М- и Михайлов Г, А- в [1] отмечают, что кроме специального статистического тестирования 'V. чрезвычайно важна проверка с помощью решения типовых задач, допускающих независимую оценку результатов аналитическими или численными методами. Можно сказать, что представление о надежности псевдослучайных чисел создается в процессе их использования с тщательной проверкой результатов всегда, когда это возможно".
Последние десятилетия характеризуются переходом развитых стран к так называемому информационному обществу, что, в частности, характеризуются широким использованием компьютерных, а точнее, информационных сетей в финансовой сфере, бизнесе, производстве да просто в личной жизни граждан (вспомним только Интернет, в путешествии по которому миллионы "обычных" людей проводят миллиарды часов). Наряду с огромным положительным влиянием на экономику и социальную жизнь, глобальная информатизация общества приводит и к появлению принципиально новых проблем» и угроз, начиная от "невинных" забав с вирусами до атак информационных террористов, потенциальный вред которых вполне сопоставим
с техногенными катастрофами. Поэтому задачи разработки эффективных средств защиты информационных систем приобретают все большую роль и находятся в центре внимания многих исследователей и разработчиков.
Целью данной диссертационной работы является построение и разработка эффективных алгоритмов и комплекса программ для тестирования случайных и псевдослучайных чисел, а также их применение к следующим задачам:
Экспериментальное исследование генераторов криптографически стойких псевдослучайных последовательностей, созданных па основе современных алгоритмов шифрования, а также разработка комплекса программ для их тестирования.
Разработка и исследование эффективных численных методов, и алгоритмов различения зашифрованных текстов на естественных языках от случайных последовательностей,
Экспериментальное исследование влияния формы представления данных на возможность их различения в зашифрованном виде.
Методы исследования. В работе были использованы вычислительные эксперименты на ЭВМ, моделирование, математическая статистика и теория построения эффективных алгоритмов и программ.
Научная нопизпа результатов работы. 13 диссертации получены следующие новые результаты:
1- Проведены экспериментальные исследования нового статистического критерия - "адаптивный критерий ^2", показана целесообразность его применения для статистической проверки случайных последовательностей и даны практические рекомендации по его применению.
2. Предложен эффективный алгоритм статистической проверки
"качества" криптографически стойких псевдослучайных последова
тельностей с помощью разработанного комплекса программ.
Впервые предложен метод различения зашифрованных текстов на естественных языках от случайных последовательностей, позволяющий, с помощью разработанного комплекса программ, различать зашифрованные тексты при сравнительно небольших объемах данных (от 100 килобайт и выше). Отметим, что для популярного статистического критерия % требуется для решения этой задачи в тысячи раз больший объем данных.
Исследовано влияние формата цифровых текстов (txt, rtf, doc, pdf) и их предварительного сжатия па возможность различения в зашифрованном виде на русском, английском и итальянском языках.
Практическая ценность.
Разработаны алгоритмы и программы для тестирования случайных и псевдослучайных последовательностей, эффективность которых существенно выше, чем у ранее известных.
Предложен метод и комплекс программ, позволяющий надежно различать зашифрованные тексты па естественных языках от случайных последовательностей, начиная с длины 100 килобайт.
Исследовано влияние формата цифровых текстов на естественных языках па возможность их различения в зашифрованном виде.
Апробация работы. Основные результаты диссертации докладывались їта между народ пых научных мероприятиях: международная конференция по теории информации ISIT-2003 (Yokohama, Japan» 2003), Китайско-российский форум молодых ученых в Пекине - 2003 г. (Пекин, НаньЦзин, У си, Шан Хай, Китай, 2003), международная конференция Вычислительные технологии и математическое моделирование в науке, технике и образовании ВТММ-2002 (Алматы» Ка-
захстан, 2002), Четвертое международное совещание по электронным публикациям EI-Pub-99 (Новосибирск, 1999), а также на объединенных семинарах института вычислительных технологий СО РАН, кафедры математического моделирования НГУ, кафедры вычислительных технологий НГТУ.
Публикации. По теме диссертации автором опубликованы работы [38] -[43].
На защиту выносятся результаты экспериментальных исследований и совокупность вычислительных алгоритмов тестирования псевдослучайных и случайных чисел, в том числе и предназначенных для различения зашифрованных текстов.
Объем и структура диссертации. Диссертационная работа изложена па 119 страницах и состоит из введения, трех глав и заключения. Иллюстрационный материал включает 10 рисунков. Список литературы состоит из 43 наименований.
СОДЕРЖАНИЕ РАБОТЫ
Во введении обоснована актуальность темы диссертационной работы, сформулированы цель работы и задачи исследований, описываются полученные результаты, дано краткое изложение диссертации по главам.
В первой главе приведены известные результаты и сведения, используемые в дальнейшем. Кратко даются общие сведения по изучаемым в диссертации вопросам, приводится описание адаптивного критерия х используемого в работе.
Критерий хи-квадрат (х2) один из наиболее популярных тестов проверки гипотез, который широко применяется в экономике, биологии, криптографии и многих других областях. Например, критерий хи-квадрат используется для проверки генераторов случайных чисел
и пригодности блоковых шифров для использования их как генераторов случайных чисел (см, [22], [31], [35]).
В таких прикладных программах число категорий (и, следовательно, число степеней свободы % распределения) очень большое и, таким образом, объем выборки должен быть также большим. Значит, в этом случае, вычисления статистики хи-квадрат требуют много времени. Кроме того, часто практически трудно получить такие большие выборки и %2 не может применяться.
Предлагается новый метод, который назван адаптивный критерий хи-квадрат. Показано, что новый критерий применим, когда объем выборки намного меньше, чем это требуется для обычного критерия хи-квадрат.
Остановимся кратко на основной идее метода. Пусть существу
ет гипотеза Щу которая утверждает, что символы из некоторого ал
фавита А = {й]( д2, », at], к > 2, распределены равномерно (т.е.
РІа\)-р(аі)~ — = г(ак)-У^) против альтернативной гипотезы Н]> что
истинное распределение неравномерно. Пусть дана выборка, которая
может быть использована для проверки. Выборка делится на две час
ти, которые называются обучающей и контрольной (проверочной).
Обучающая выборка используется для оценки частоты встречаемости
символов (букв). После этого буквы алфавита^ объединяются в под
множества (классы) Л,,Л2Т...,Л,, j2, таким способом, что во-первых,
в один класс группируются символы с близкими (или равными) час
тотами встречаемости и, во-вторых, s гораздо меньше чем к (скажем,
к — 220» s — 2). Затем, классы {А\, А2г ..., As} рассматриваются как но
вый алфавит и новая гипотеза
Hfl: p{Ai) = \A)\/kltp{A1) = \A2\/ky...p(A1)-\Aa\/k и альтернативная гипотеза,
которая является отрицанием Я0, проверяется па второй (контроль-
ной) части выборки. Очевидно, если //0 истинно, тогда /?в также истинно и, если llj истинно, тогда Н\ истинно. Именно поэтому новый тест может быть использован для проверки первоначальных Н0 иН\. Идея такой схемы довольно проста. Если Н\ истина, тогда есть символы с относительно большими и относительно малыми вероятностями. Вообще говоря, высоковероятные символы будут иметь относительно большие частоты встречаемости и будут накоплены в некоторых классах А-„ тогда как низко вероятные символы будут накоплены в других классах. Именно поэтому, это отличие может быть найдено по проверочной выборке. Важно отметить, что уменьшение числа категорий от к до меньшего sy может существенно увеличить мощность критерия и, поэтому, может существенно уменьшить задаваемый объем выборки. Более точно, показано, что объем выборки, может быть уменьшен в 4к раз, что может быть важно, когда к большое. Мы провели некоторые эксперименты в дополнение к теоретическому исследованию критерия адаптивный х2- А именно, были протестированы зашифрованные тексты на английском, итальянском и русском языках, с целью отличить их от случайных последовательностей. Стоит отмстить, что проблема распознавания зашифрованных текстов на естественных языках имеет некоторый интерес для криптологии (см. [10], [16], [34]). Оказывается, что новый критерий может различать зашифрованные тексты на английском, итальянском и русском языках от случайной двоичной последовательности па выборках значительно меньших, чем это требовалось бы для обычного критерия %2.
Отметим, что обучающиеся методы применялись ко многим статистическим задачам. Например, аппроксимация Маркова и кластерная нейронная сеть используется для того, чтобы делать тсстиро-
вание более эффективным (см, [14], [36]). Кроме того, известно, что стратификация может быть использовано как инструмент в исследовании случайности (см. [19], [37]). В отличии от этих методов, описанный метод предназначен для того, чтобы решить одну специфическую задачу, которая не рассматривалась ранее. А именно, предлагается увеличить мощность критерия хи-квадрат посредством самообучения и группировки, в случае, когда объем выборки относительно мал.
Во второй главе диссертации, состоящей из 2 параграфов, рассматриваются экспериментальные исследования эффективных генераторов криптографически стойких псевдослучайных последовательностей, созданных на базе современных алгоритмов шифрования.
В 1994 году впервые появилось описание алгоритма шифрования RC5, а в 1998 г. - алгоритма RC6. Параграф 2.1 посвящен исследованию криптографических алгоритмов RC5 и RC6 как датчиков случайных чисел. По сравнению с традиционными алгоритмами датчиков псевдослучайных чисел эти криптографические алгоритмы обладают многими достоинствами, одним из которых является очень высокое быстродействие. Авторы алгоритмов рекомендовали их для генерации последовательностей случайных чисел [27], [28]. Однако, на время проведения экспериментальных исследований каких-либо статистических данных по исследованию или применению генераторов псевдослучайных чисел основанных на этих алгоритмах мы не нашли. Таким образом, экспериментальные исследования решали задачу статистического анализа генераторов псевдослучайных чисел, базирующихся на криптографических алгоритмах шифрования RC5, RC6 и разработки рекомендаций по их применению. Для исследований использовался критерий Пирсона х9 являющийся одним из самых распространенных и эффективных тестов [4].
На основании проведенных экспериментальных исследований был сделан вывод о том, что алгоритмы шифрования RC5 и RC6 можно использовать в качестве генераторов псевдослучайных чисел для исследованных длин слов выборки {1, 2, 3, 4, 5, 6, 7» 8, 16, 24, 26} бит. Однако полученные результаты тестирования показали, что для RC5 требуется специальный алгоритм входных данных, при реализации которого значительно улучшаются статистические свойства получаемой последовательности. Временные характеристики алгоритма RC5 уступают характеристикам алгоритма RC6. С помощью RC6 можно получить последовательность случайных чисел значительно большей длины, чем с помощью алгоритма RC5 (период последовательности 212В против 232). Выходная последовательность при одном обращении к алгоритму для RC6 (128 бит) в два раза больше, чем для RC5. Учитывая вышесказанное, мы рекомендовали для получения последовательности случайных чисел в качестве генератора использовать криптографический алгоритм шифрования RC6 (с количеством раундов г = 6 или г = 11). При выборе параметров алгоритма следует помнить, что число раундов влияет на количество "проходов" (операций "перемешивания") и, следовательно, при большой выборке — на общее время счета.
Для реализации алгоритма шифрования RC6 в качестве генератора псевдослучайных чисел на языке Java предлагается RC6Key.class па . Для возможности реализации рассматриваемых криптографических алгоритмоз шифрования на других языках программирования, в конце параграфа дано их полное описание, включая алгоритм расширения ключа.
В параграфе 2.2 рассматриваются исследования криптографических алгоритмов, победителя и финалистов конкурса на блоковый
"шифр 21-го века", проведенного NIST (США) в 1999-2001 г.г., AES, RC6 и MARS с помощью нового статистического метода.
Экспериментальные исследования эффективности генераторов псевдослучайных чисел, проведенные с алгоритмами шифрования RC5 и RC6 {см. параграф 2.1), показали неплохие результаты. Однако эти исследования были ограничены длиной слова (или блока) в 26 бит, что связано с требованиями, для критерия % , на длину проверяемой последовательности и доступными вычислительными ресурсами. Новый статистический критерий - адаптивный критерий %2 позволяет, довольно существенно, снизить ограничения на выбранную длину слова и улучшить качество проверки случайной последовательности. Расчет минимально необходимой длины проверяемой последовательности для адаптивного критерия %2 проводится по формуле (1).
^x где JV — длина проверяемой последовательности в байтах, Ь — длина выбираемого слова в битах, к - коэффициент отношения обучающей выборки от N Например, для традиционного критерия % при тридцати двух битной выборки, необходимая минимальная длина проверяемой последовательности 85899345920 байт, а для адаптивного критерия х2 - 1172308 байт (для к = К)- В данном параграфе представлены результаты экспериментальных исследований датчиков псевдослучайных чисел созданных с помощью криптографических алгоритмов AES, RC6 и MARS. Испытания полученных псевдослучайных последовательностей проводились на длинах слов (букв) b = {8, 16, 24, 32, 40, 48} бит. На первом, подготовительном этапе, с "CDROM-a случайных чисел" ("The Marsaglia Random Number CDROM"), созданного профессором университета Флориды Д. Марсалья (George Marsaglia) [20], были произвольно выбраны сто 128 битных "случайных" ключей. Подготовленный комплекс программ реализации алгоритмов шифрования AES, Mars и RC6 использовался для получения последовательностей случайных чисел необходимых в исследовании. Для каждого создаваемого файла использовался один из последовательно выбираемых подготовленных 128 битных "случайных" ключей и на вход, текущего в данный момент алгоритма шифрования, подавались числам = {0, 1, ..., п}. На выходе алгоритма мы получали файл размерностью 460 мегабайт. Длина файла выбрана пе случайно, поскольку это необходимая минимальная длина проверяемой последовательности, для адаптивного критерия х2» ПРИ выборке слова длинной 48 бит. Таким образом» для исследования было подготовлено 300 файлов или по 100 зашифрованных последовательностей для каждого выбранного алгоритма шифрования. Рассмотрим разработанный алгоритм, который можно представить двумя основными частями: обучения и проверки (контрольной). Обучение, По заданной для испытания длине файла TV байт (6, к и TV являются параметрами программы) определяется» удовлетворяет ли она условию (1). Через заданное N определяем количество слов (здесь» под словом будем понимать битовую последовательность Integer, если 6<32 и Double, если Ь 32) входящих заданную последовательность L = N/(w/8), где w = 64 для выборки Ь>32 и w = 32 для выборки Ъ < 32. Затем, через вычисленное количество слов L находим длину обучающей Le и контрольной Lc частей в словах по формуле. Lt =Lxk Lc=Lx(\-k) Создаются две одномерные таблицы Т и Ys размерностью / вычисляемой с помощью найденных значений Le и Lc по формуле (2)- Величина I будет равна максимально возможному числу букв (здесь и далее в этом параграфе, под буквой будем понимать битовую последовательность равную Ъ битам из алфавита 2 букв), для заданной размерности Ь бит, из наибольшей заданной обучающей или контрольной последовательности» , (2) В ячейки таблицы Т из обучающей части mi={xlix2i...txl\i заданного для проверки файла, последовательно выбираются буквы заданной размерностью выборки b бит. После прохождения mh для оптимизации дальнейшей обработки данных из Г в алгоритме используется сортировка Шелла. По результатам обработки обучающей части подготавливается таблица Кг, которая будет использования в контрольной части. Для этого из таблицы Т последовательно выбирается по одной букве и, если она ранее не встречалось, ее значение заноситься в первую же свободную ячейку Кг. Таким образом, в таблице Кг будут накоплены буквы (буквы в таблице будут располагаться по возрастанию), попавшие в обучающую область mh Проверка. Для контрольной части алгоритма используется вторая половина исходной последовательности n,=\x^ltx^2t..jc^\9 таблица Т и, подготовленная на этапе обучения, таблица Ys. В ячейки таблицы Т из контрольной части п. = {*/4t|,*,Wv*,v}» заданного для проверки файла, последовательно выбираются буквы заданной размерностью выборки b бит. Для оптимизации дальнейшей обработки данных в алгоритме используется сортировка Шелла букв в таблице Т. Дополнительно создаются две таблицы V и Р с размерностью 2 -равной количеству создаваемых новых классов. Из подготовленной таблицы Т последовательно выбираются буквы, полученные из контрольной части исходной последовательности, и сравниваются с буквами, попавшими в обучающую часть. Если в таблице Ys будет найдена буква равная выбранной, увеличивается количество попаданий из контрольной выборки во второй класс К|2] = 1ф]+1* в противном случае, увеличивается счетчик к[і] = к[і] + 1 для первого класса. Подсчитывается общее количество строк (ячеек) с буквами в таблице Ys и полученный результат rtewlndex заносится в таблицу p[l]= newlndex, Первая ячейка таблицы р[\] будет содержать разницу между максимально возможным появлением числа букв для выборки b и реально встретившимися в обучающей части (mi) р[\] = 2*' -р[2]. В завершающей части алгоритма, по результатам выборки из п\ оцениваются частоты попаданий букв (таблица V) для контрольной части и подсчитывается величина $ для двух классов. где Vi количество элементов, попавших в / класс; п — общее количество букв в выборке 1ц {V] V2)', Pi - вероятность попадания в / класс результата испытаний по контрольной части (Л- количество букв, относящихся к "Ґ классу, деленное на 2Ь), с — количество выбранных классов. При большой исходной выборке (№) и малой длине Ъ разность ґ[і] = 2* -^[2] может равняться нулю. Это означает, что в обучающей области встретились все возможные значения букв из области {0, 1, ..., 2Ъ - 1}- В этом случае используется алгоритм с тремя классами (причем алгоритм с тремя классами может быть использован и для первого варианта, когда b большое, а 2* -Г[2]>0). Две таблицы V н Р создаются с размерностью равной 3 - количеству создаваемых новых классов и дополнительная таблица Yb размерностью newlndex. После обучающей части, алгоритм которой не меняется, выполняется дополнительная процедура создания классов-"Dispersion", Находим максимальное Мах и минимальное Min значение вы D = Min + (Мах - Min)/!. (На самом деле алгоритмов определения дисперсии может быть очень много и оптимальные, для каждого распределения, можно найти экспериментальным путем). Из созданной на этапе обучения таблицы Ys последовательно После обработки всей таблицы значений Т по полученным результатам (выборки из /7і) оцениваются частоты попаданий букв (таб- лица V) для контрольной части и подсчитывается величина %2 (З)для трех классов- Где Vt количество элементов, попавших в / класс; п — общее количество букв в выборке щ (У\ + V2 + V2); Pt - вероятность попадания в і класс результата испытаний по контрольной части (Р,-- количество букв, относящихся к "/** классу, деленное на 2А). Наконец, результаты проведенных экспериментальных исследований использования современных алгоритмов шифрования в качестве генераторов криптографически стойких псевдослучайных последовательностей, позволяют сделать вывод, что современные криптографические алгоритмы шифрования AES, Mars и RC6 можно использовать как генераторы псевдослучайных чисел. На основании проведенных экспериментов, заключаем, что мощность нового метода адаптивный критерий существенно выше, чем у традиционного критерия Пирсона %. Новый метод более эффективен во многих приложениях, в частности связанных с криптографией, где Ь велико, а объем доступной выборки ограничен. Третья глава диссертации посвящена задаче построения статистического метода для алгоритма различения зашифрованных текстов на естественных языках и случайных последовательностей, В параграфе 3.1 предлагается и исследуется один из первых результативных вариантов алгоритма» позволяющий достаточно надежно различать зашифрованные тексты на русском, английском и итальянском языках, в формате данных "ixt**7 от случайных последовательностей для длин выборки N^ {512000, 1024000, 2048000} байт. Конструкция предлагаемого алгоритма базируется на двух этапном подходе» Сначала исследуемая последовательность разбивается па (под)слова по 24 бита, что соответствует алфавиту А {ah ..., ак}> где к — 2 л, которая затем делится на две равные части mt = [jcltx2,.„txNfl\ и n, ={xvf2+t*xKt2+2>-xvt\ - обучающую и контрольную. По результатам прохождения всей обучающей выборки mt -{*|.*2»-»*^/г] алфавит из 221 букв разбивается на три класса ((под)алфавита), содержащих буквы с частотами встречаемости, оцененными по обучающей части. Для этого в таблицу Т размерносіью 224 (количество ячеек таблицы равно количеству слов алфавита Л) накапливается счетчик попаданий слова (буквы) из алфавита А, Т\а^{т^\ = 7\а\{т$\ + 1, другими словами, для каждой встреченной буквы в соответствующей ячейке таблицы счетчик увеличивается на единицу. Затем, по данным, накопленным в таблице Т9 определяется максимальное число попаданий Mmax = max(T[a\(mi)]), т.е. счетчик для слова, которое встретилось наибольшее количество раз в обучающей части, с помощью которого вводится новый коэффициент среднего числа попаданий для трех классов ЛГП1еап = А/тах/3. Используя этот коэффициент, проводится группировка (или объединения по классам) букв, с близкой частотой встречаемости, в новые "супербуквьГ {A\t А% Аз}* Па втором этапе используется таблица Т подготовленная на шаге обучения и две новые таблицы Уи Р с размерностью равной количеству созданных новых классов. Подсчитывается общее количество строк (ячеек) в таблице Гдля каждого класса сі = (1, 2, 3} и результат заносится в таблицу P[ct]. Из nt "\x^n^,xKjl^^.xNt}, аналогично этапу обучения, последовательно выбираются слова по К[г[дДя,)]]= іф'[а,(л,)Ц-И» после чего оцениваются частоты попаданий букв (Кс|(/їі)) из алфавита А для контрольной части, подсчитывается статистика %2 для 3 классов и проверяется гипотеза о случайности зашифрованного текстового файла. В параграфе 3.2 предлагается новый алгоритм, позволяющий достаточно надежно различать зашифрованные тексты на русском, английском и итальянском языках, для четырех наиболее известных форматов данных: "txt", "rtf\ "doc", "pdf\ от случайных последовательностей начиная с длины 100 килобайт. Для этого зашифрованный файл, некоторой длины N байт (исходная выборка), разбипается на слова а по 32 бита, что соответствует алфавиту А = {#1, .„,аА}? где А — 232. Полученная последовательность исследуется "на случайность11 по четырем значениям N= {512000, 307200, 204800, 102400} байт. Исходная выборка разбивается, как и в предыдущем варианте, па две части т,=\х19х2^х^п} и п, = К/э+р^/^-*„,} - обучающую и контрольную. Затем подсчитывается частота встречаемости букв из А в обучающей выборке. По результатам обработки обучающей выборки алфавит из 232 букв разбивается па два класса (Ао, А)), содержащих буквы с частотами встречаемости, соответственно, 0 и 1 оцененными по обучающей части. Затем, по контрольной выборке для полученных двух классов, рассматриваемых как отдельные "супербуквы" Ао, и А] проверялась гипотеза против гипотезы Н\7 являющейся отрицанием Н$. (Здесь х - элемент выборки, или в нашем случае, слово длины 32 двоичных знака из проверочной выборки). Это задача проверки гипотезы о параметре биноминального распределения. Она хорошо известна в математической статистике [2], и для ее проверки можно применять не только критерий % , но и другие методы, применимые при малых значениях р[х є А0} (см. [2]). В данной работе мы использовали критерий, базирующийся на непосредственном использовании биноминального распределения [2]. Для его описания мы определим величину Н-4.1/2'2 и обозначим через / количество 32 - битовых слов, а через х количество элементов из контрольной выборки, попавших в множество А\, Пусть а - заданный уровень значимости критерия. Определим Р\ как наибольшее значение Р3 удовлетворяющее неравенству а Рг как наименьшее значение Ру удовлетворяющее неравенству Если к є (/p/j), то гипотеза Щпринимается, в противном случае Щ отвергается. В заключении кратко формулируются основные результаты диссертационной работы и сказано несколько слов о перспективах исследования. В тексте диссертации принята тройная нумерация формул, таблиц и рисунков: первая цифра указывает номер главы, вторая номер параграфа в главе, а последующие - на порядковый номер формулы, таблицы или рисунка. Автор выражает благодарность научному руководителю, доктору технических наук, профессору Борису Яковлевичу Рябко и научному консультанту академику РАН Юрию Ивановичу Шокину за постоянное внимание и помощь в работе. В этой главе приведены известные результаты и сведения, используемые в дальнейшем- Кратко даются общие сведения по изучаемым в диссертации вопросам, приводятся основные определения и понятия, используемые в работе. В практических приложениях наиболее широкое применение нашли три способа генерации псевдослучайных чисел: аппаратный, табличный и алгоритмический [8]. Аппаратный способ предполагает использование специальной злеісгронной приставки — генератора (датчика). В качестве физического эффекта, лежащего в основе таких генераторов, обычно используются шумы в полупроводниковых приборах, реже - явление распадов радиоактивных элементов. Как правило, такие устройства позволяют получать равномерно распределенные на интервале [0, 1] числа. Реализация аппаратного способа не требует никаких специальных вычислительных процедур, однако он не гарантирует качества последовательности непосредственно во время работы, а также возможности повторного получения одинаковых последовательностей чисел. При табличном способе эталонную таблицу псевдослучайных чисел оформляют в виде отдельного файла, который помещают в оперативную или внешнюю память ЭВМ, и обращаются к нему по мере необходимости, но такой способ получения псевдослучайных чисел целесообразно использовать только при небольшом объеме таблицы. Алгоритмический способ основан на формировании псевдослучайных чисел в ЭВМ с помощью специальных алгоритмов и реализующих их программ. Каждое псевдослучайное число вычисляется в случае обращения к соответствующей процедуре. К достоинствам способа относятся: одна проверка качества последовательности, возможность многократного воспроизведения одной и той же последовательности, отсутствие необходимости использования внешних устройств, малый занимаемый объем памяти. Однако то, что запас чисел последовательности ограничен ее периодом и, возможно, большие затраты машинного времени, можно отнести к недостаткам этого способа. Указанные преимущества алгоритмического способа формирования базовой последовательности случайных чисел определяют его наибольшую рациональность по сравнению с двумя другими способами. В настоящей диссертационной работе рассматриваются генераторы псевдослучайной последовательности, основанные на криптографических алгоритмах. Качественный генератор псевдослучайной последовательности, ориентированный на использование в системах защиты информации, должен удовлетворять следующим требованиям: - криптографическая стойкость; - хорошие статистические свойства, псевдослучайная последователь ность по своим статистическим свойствам не должна существенно от личаться от истинно случайной последовательности, более того, ни один статистический тест не обнаруживает в псевдослучайной последо вательности каких-либо закономерностей; - большой период формируемой последовательности; - эффективная аппаратная и программная реализация. Под криптографической стойкостью понимается то, что последовательность должна быть непредсказуемой. Это означает, что никакими вычислительными средствами невозможно предсказать каждый последующий бит, даже при абсолютном знании всех предшествующих битов потока, а также алгоритма или устройства генерирующего данную последовательность с вероятностью, отличающейся от 0.5. В настоящее время неизвестно, существует ли криптографически стойкий генератор. Имеются лишь претенденты на это звание, например, генератор, названный по фамилиям его создателей BBS (Блюма-Блюма-Шуба) [23]. Практически криптостойкость оценивается статистическими методами. Национальный Институт Стандартов и Технологий (НИСТ) США разработал Руководство по проведению статистических испытаний генераторов псевдослучайных последовательностей, ориентированных на использование в задачах криптографической защиты информации [31]. Это Руководство использовали при организации конкурса на блоковый шифр 21-го века [35]. Смысл проведения статистических тестов - выяснить отличается или нет исследуемая последовательность по своим свойствам от свойств последовательности, полученной в результате подбрасывания честной11 монеты, со сторонами, помеченными "О" и "Г\ При этом результаты исходов независимы друг от друга: результат предыдущего не влияет на результат последующего. Вес элементы последовательности генерируются независимо друг от друга," и значение следующего элемента в последовательности не может быть предсказано, независимо от того, сколько элементов уже было произведено. Как принято в литературе, мы такие последовательности будем называть случайными Оценка статистических испытаний основана на проверке гипотезы о случайности исследуемой последовательности нулей и единиц. Таблица 1.1 показывает пошаговый процесс, позволяющий оценить конкретную двоичную последовательность [35], В 1994 году впервые появилось описание алгоритма шифрования RC5, а в 1998 г. — алгоритма RC6. По сравнению с традиционными алгоритмами датчиков псевдослучайных чисел эти криптографические алгоритмы обладают многими достоинствами, одним из которых является очень высокое быстродействие. Авторы алгоритмов рекомендовали их для генерации последовательностей псевдослучайных чисел [28], но на день проведения настоящих экспериментальных исследований каких-либо статистических данных по исследованию или применению генераторов псевдослучайных чисел основанных на этих алгоритмах мы не нашли и, поэтому, решили восполнить этот пробел. Таким образом, целью настоящих экспериментальных исследований является статистический анализ генераторов псевдослучайных чисел, базирующихся на криптографических алгоритмах шифрования RC5, RC6 (описание алгоритмов приведено в конце параграфа) и разработка рекомендаций по их применению. Для своих исследований воспользуемся одним из хорошо известных тестов, который, будучи наиболее полезным, одновременно легко реализуется на вычислительных машинах [4]. Критерий Пирсона д2 ("хи-квадрат"), вероятно, самый распространенный из всех известных статистических критериев [17]. Преимуществом данного критерия является то, что одни и те же табличные значения (таблица -распределения) используются при любом числе п независимых испытаний и любых вероятностях/? Единственной переменной является v = к-1 (число"степеней свободы"), где категория к- число возможных исходов испытаний. На самом деле величина V (статистика $) подчиняется распределению х2 только приближенно, причем приближение тем лучше, чем больше п. С учетом рекомендаций [4] и возможностей доступных вычислительных ресурсов для экспериментальных исследований алгоритма шифрования RC5 мы вводим коэффициент т = 10000, для всех категорий к (при равномерном распределении каждое возможное значение, выбираемого из полученной случайной последовательности слова длиной b бит, должно в среднем встретиться 10000 раз). Число независимых испытаний определяется как п = тк, где к = 2Ь. Необходимая для исследования длина (в байтах) последовательности случайных чисел для каждого выбранного значения Ь, вычисляется по формуле где т - заданный коэффициент; Ъ - длина выбираемого для исследования слова в битах, В нашем случае т = 10000; b = {1, 2, 3, 4, 5» 6, 7S 8, 16} бит; число возможных исходов испытаний равно 2Ь. Для проведения экспериментальных исследований были программно реализованы - алгоритм шифрования RC5 и тест х2, В качестве языка программирования мы выбрали Java- Преимуществом этого языка кодирования является его универсальность и распространенность, что позволяет запускать исполняемый код программы на большинстве системных платформ, без установки дополнительного программного обеспечения. Остановимся подробно на алгоритме проведения экспериментальных исследований. Для получения трех разных непересекающихся последовательностей случайных чисел использовалась программная реализация RC5. Для этого на вход алгоритма шифрования подавались числа : для первой последовательности = {0, 1, ...,w- 1}, для второй Уі = {п, п + 1, ...т 2п- 1}, для третьей суі = {2гс, 2л + 1, .,., Ъп 1}, На выходе программы мы получали три последовательности зашифрованных данных, которые, затем, проверялись на "случайность" с помощью критерия $. Алгоритм шифрования, для одних и тех же входных дан-пых, использовался с разным числом проходов (раундов) кодирования (см, описание алгоритма в конце параграфа). Проведенные многочисленные эксперименты показали, что для алгоритма RC5 при числе раундов г большем, чем двенадцать, качество получаемой последовательности случайных чисел не улучшается. Поэтому, в пашей работе рассматриваются результаты испытаний полученных зашифрованных RC5 данных с 4 раундов по 12 (только после четвертого раунда вывод алгоритма является случайным [35]). Испытания проводились па длинах слов b — {1, 2, 3, 4, 5, 6, 7, 8, 16} бит, которые выбирались последовательно из получаемых выходных последовательностей. Сначала мы исследовали генератор псевдослучайных чисел, базирующийся на криптографическом алгоритме RC5, следуя предложенной в [4] рекомендации» Согласно этой рекомендации алгоритм шифрования RC5-32/8/0 использовался без секретного ключа. На вход подавалось О, 1» 2, ..., /%, чтобы генерировать последовательность случайных чисел, которую можно использовать в рандомизированном вычислении [4]. Однако проведенные многочисленные тесты показали, что при использовании предложенного алгоритма на выходе числа "плохие" (рис.2.ІРІ), Тг е. значения статистики х явно слишком велики (зарегистрировано большое отклонение от равномерного распределения). На (см.рис.2.1.1) результат испытания, для тестируемой длины слова выборки, графически обозначен цифрой равной количеству заданных раундов в алгоритме для каждой проведенной проверки. В связи с большим отклонением от равномерного распределения полученных значений, перед нами встала задача дальнейшего анализа и поиска алгоритма, который позволит использовать RC5 в качестве генератора псевдослучайных чисел. Из (см/габл.2.2.1) видно, что для статистической проверки на случайность с помощью адаптивного критерия %2 необходимая длин-на проверяемой последовательности па много порядков (например, для выборки длинной 32 бита в 73274 раза) меньше чем для стандартного критерия у}. Таким образом, новый критерий, при одних и тех же ограничениях накладываемых доступными вычислительными ресурсами, позволил нам провести экспериментальные исследования последовательностей на случайность для выборки слова длинной до 48 бит. Для новых экспериментальных исследований в качестве генераторов, для получения криптографически стойких псевдослучайных последовательностей, нами использовались современные алгоритмы шифрования AES (Rijndacl), Mars и, уже известный нам шифр, RC6. Программная реализация выбранных алгоритмов проводилась по доступным материалам, представленным на вышеупомянутый конкурс "шифр 21-го века"- В качестве языка программирования, с помощью которого был создан комплекс программ генераторов криптографически стойких случайных чисел, как и предыдущих исследованиях, мы выбрали язык Java. Вкратце напомним алгоритм работы адаптивного критерия Х2[40]. Пусть дана исходная выборка Nh которая разбивается на две части ті и ПІ- обучающую и контрольную. По результатам прохождения всей обучающей выборки алфавит из 2 букв разбивается на К класса ((под)алфавита), содержащих буквы с частотами встречаемости, оцененными по обучающей части. Затем, по контрольной выборке для полученных К классов, рассматриваемых как отдельные "супербуквы", оценивается статистика %2, которая сравнивается с квантилем распределения хи-квадратс К- 1 степенями свободы. Необходимо отметить, что поскольку в наших исследованиях не-пользовался адаптивный критерий % , который обладает свойствами самообучения и группировки, представленіїым в работе вычислениям предшествовали многочисленные эксперименты, направленные на поиск "хороших" длин выборок, количества классов группировки, алгоритмов построения классов и т.п. Результаты этих предварительных вычислений показали, что при использовании различных отношений длин, обучающей и контрольной выборок, полученные численные данные экспериментов (тестирования последовательностей созданных датчиками случайных чисел на базе современных алгоритмов шифрования) настолько незначительно отличаются друг от друга, что не могут повлиять на конечный результат. Следовательно, для экспериментов мы можем использовать наиболее выгодное разбиение исследуемой последовательности, при котором необходимая минимальная длина (вычисленная по формуле (2.2.1)) имеет наименьшее значение. Поэтому в данной работе мы используем алгоритм, при котором обучающая и контрольная выборки равны % (коэффициент к=\С) Остановимся подробно на алгоритме проведения экспериментальных исследований, который состоит из нескольких этапов. На нервом, подготовительном этапе, с "CDROM-a случайных чисел" ("The Marsaglia Random Number CDROM"), созданного профессором университета Флориды Д. Марсалья (George Marsaglia) [20], были произвольно выбраны сто 128 битных "случайных" ключей. Подготовленный комплекс программ реализации алгоритмов шифрования AES, Mars и RC6 (с рекомендованным числом раундов [29]) использовался для создания последовательностей случайных чисел необходимых в исследовании. Для каждого создаваемого файла использовался один из последовательно выбираемых подготовленных заранее 128 битных "случайных" ключей и па вход, текущего в данный момент алгоритма шифрования, подавались числа {0, 1, ..,, п}_ На выходе алгоритма мы получали файл объемом 460 мегабайт. Размер файла выбран не случайно, поскольку это необходимая минимальная длина для выборки слова длинной 48 бит (см,табл,2ЛЛ) для статистической проверки на случайность с помощью адаптивного критерия %2. Таким образом, для исследования было подготовлено 300 файлов или по 100 последовательностей для каждого выбранного алгоритма шифрования. На втором этапе, для проведения экспериментальные исследований эффективности генераторов псевдослучайных чисел базирующихся на криптографических алгоритмах с использованием адаптив-ного критерия х был разработан специальный алгоритм, который мы программно реализовали на языке Java (программа Offsct_Test). Как уже было сказано выше, адаптивный критерий %2 обладает очень гибкими свойствами и поэтому разработанный алгоритм учитывает переменные длины выборок, количества классов группировки, алгоритмы построения классов, что позволяет ограничивать исследования для максимальной длины выборки только доступными в данный момент вычислительными ресурсами, такими как наличие свободного места на жестком диске (проверочный файл для выборки 56 бит требует более 8 гигабайт) и, самое главное, доступный объем оперативной памяти установленной на ЭВМ. Это связано с тем, что для минимизации времени счета, при обработке больших по объему файлов (например, мы используем выборки длинной 460 мегабайт), все вычисления проводятся в оперативной память компьютера, В данной работе представлены результаты исследований проведенных на компьютере с памятью один гигабайт и испытания проводились на длинах слов (букв) Ъ = {8, 16, 24, 32, 40, 48} бит. Рассмотрим более подробно предлагаемый алгоритм, который можно представить двумя основными частями: обучения и проверки (контрольной), и двумя вспомогательными процедурами: создания классов — "Dispersion" и анализа полученных результатов. Обучение. По заданной для испытания длине файла N байт определяется (Ь, к и N являются параметрами программы), удовлетворяет ли она условию неравенства (2-2,1). Если оно не выполняется, на экран монитора выводится сообщение об ошибке и работа алгоритма завершается. В противном случае, через полученное значение N определяем количество слов (здесь и далее в этом параграфе, под словом будем понимать битовую последовательность "Integer" равную 32 битам, если Ь 32 и "Double" равную 64 битам, если й 32) L = Nf(w/S) входящих заданную последовательность, где w - 64 для выборки 6 32 битам и w = 32 для выборки Ь 32 бит. Затем, через вычисленное количество слов L находим длину обучающей Le и контрольной Ьс частей в словах по формуле (2.2.2). Среди всего многообразия задач защиты информации мы выделим одну» рассматриваемую в этой главе - построение эффективных алгоритмов распознавания, или различения, зашифрованных текстов. Эта задача довольно известна в криптографии (см., например, [16], [34]) т.к. ее решение позволяет распознать сам факт передачи по сетям связи (или хранения в информационных базах данных) зашифрованных текстов, что представляет несомненный интерес для разработчиков систем защиты информации. Трудность этой задачи в том, что современные шифры должны преобразовывать данные в последовательности, неотличимые от случайных настолько, насколько это возможно. Точнее, это одно из требований, предъявляемых к современным блоковым шифрам, - неотличимость зашифрованной последовательности от случайной, даже тогда, когда шифруемые данные заведомо не случайны, В частности, как отмечалось, если на вход алгоритма шифрования подается текст на естественном языке, то на выходе он должен выглядеть как случайная последовательность. Заметим, это условие предъявлялось Национальным институтом стандартов и технологии СШЛ — NIST к блоковому шифру при организации конкурса на блоковый шифр 21-го века. Это требование предъявляется в частности и потому, что "неслучайность" зашифрованной последовательности может использоваться для взлома шифров [16], [34]. В данной главе рассматривается задача построения статистического метода для различения зашифрованных текстов на естествен- -ных языках и случайных последовательностей. В параграфе 3.1 предлагается один из первых результативных вариантов алгоритма, хотя проводилось довольно много экспериментов с различными разбиениями зашифрованных данных на (под)слова, с различными длинами (и отношениями) обучающих и контрольных данных, с разными алгоритмами построения классов ("супербукв") и т.п. В параграфе 3.2 предлагается алгоритм, позволяющий достаточно надежно различать зашифрованные тексты на русскомт английском и итальянском языках от случайных последовательностей, начиная с длины 100 килобайт. Отметим, что для решения этой задачи с использованием одного из популярных статистических методов — критерия х потребовало бы объем данных в тысячи раз больший, Пусть дана исходная выборка (зашифрованный файл), которая разбивается на (под)слова а по 24 бита, что соответствует алфавиту А = {а\, ..., а }, где к = 22\ Полученная последовательность проверяется для разных длин выборки N = {512000, 1024000, 2048000} байт. Исходная выборка Ni разбивается на две равные части обучающую и контрольную. По результатам прохождения всей обучающей выборки алфавит из 22i букв разбивается на три класса ((под)алфавита), содержащих буквы с частотами встречаемости, оцененными по обучающей части. Затем, по контрольной выборке для полученных 3 классов, рассматриваемых как отдельные "супербуквы", оценивается величина статистики % , которая сравнивается с 0.001 квантилем распределения хи-квадрат с двумя степенями свободы. Остановимся более подробно на предлагаемом алгоритме, который молено представить двумя основными частями: обучения и проверки (контрольной). Обучение. Для подсчета частоты встречаемости букв из алфавита А = {&), ..., аА} создается основная таблица Г размерностью 224 (количество ячеек таблицы равно количеству слов алфавита А) в которой, на начальном этапе, все ячейки имеют нулевое значение. Из выборки mt ={xitx2,...,x 2\ последовательно выбираются слова Х\ (24 бита) и в таблице Т накапливается счетчик попаданий для каждого слова (буквы) из алфавита А, Т[щ(т{)] = 7{aj(mj)] + 1, другими словами, для каждой встреченной буквы в соответствующей ячейке таблицы (с индексом равным значению #І) счетчик увеличивается на единицу. Длина обучающей области т{ на первом этапе, равна 256000 байт (т.е. //,/2). В результате прохождения всей заданной последовательности т\ формируется таблица с частотами встречаемости букв из обучающей выборки для алфавита А. На втором шаге обучения создается новый алфавит (классы) и подготавливается таблица Т для контрольной части. Для этого по данным, накопленным в таблице, определяется максимальное число попаданий MmaK = max(71#j(tf7j)]), т е. счетчик для слова, которое встретилось наибольшее количество раз в обучающей части. Используя найденное максимальное число попаданий, вводим новый коэффициент среднего числа попаданий для трех классов. Этот коэффициент будет необходим для проведения группировки (или объединения по классам) букв, с близкой частотой встречаемости, в новые "супербуквы" {А\, Л2і Лі}. В зависимости от отношения счетчика попаданий буквы к введенному коэффициенту в таблице Т отмечаются ячейки по признаку отношения к классу. Ячейки, в которые не было не одного попадания на этапе обучения, имеют нулевое значение (класс А\). В ячейки с частой встречаемости 0 Т\а\{т$\ й Л теап заносится 1 (класс А2) В ячейки с частой встречаемости Т[ат{)\ пісші заносится 2 (класс /f3)- По завершению инициализации таблицы переходим к следующей части алгоритма. Для контрольной части алгоритма используется вторая половина исходной последовательности я, = \хы х ,/2 -х } и таблица Г, подготовленная на этапе обучения. Напомним, что длина пх равна длине обучающей последовательности т\. Дополнительно создаются две вспомогательные таблицы V п Р с размерностью равной количеству созданных новых классов.
бранных по обучающей области букв из Yst после чего, вычисляется
дисперсия D необходимая для создания новых классов по формуле,
выбранной после многочисленных экспериментов,
выбираются буквы и помечаются, к какому классу они относятся. Ес
ли значение в ячейки таблицы Ys меньше или равно найденному зна
чению D, в идентичную ячейку таблицы Yb заносится единица, при
знак отношения к первому классу, а счетчик отношения для данного
класса в таблице Р увеличивается на единицу Р[\] — P[l] + 1. Все вы
бранные значения из Yst удовлетворяющие неравенству
D
тичные ячейки таблицы Yb заносится 2 и счетчик для данного класса
в таблице Р увеличивается на единицу Р[2] = Р[2] + 1 для каждого
события). Значения из Ys, для которых неравенство
Ys[i]> D4-{Max-Min)/3 является истиной, помечаются как имеющие от
ношение к третьему классу (в идентичные ячейки Yb заносится 3 и
Р[3] = Р[3] + 1 для каждого случая).
24 бита \xNilw.9xNi) и по содержимому ячейки таблицы 7'[а,(и,)] опре
деляется, к какому классу относится выбранное слово. В таблице V
суммируется количество попаданий в данный классНеобходимые сведения из математической статистики и вспомогательные результаты
Экспериментальные исследования эффективности генераторов псевдослучайных чисел базирующихся на современных криптографических алгоритмах
Алгоритм различения зашифрованных текстов на естественных языках и случайных последовательностей
Алгоритм различения зашифрованных текстов на естественных языках и случайных последовательностей на длинах выборки от 100 килобайт
Похожие диссертации на Разработка и экспериментальные исследования алгоритмов тестирования случайных чисел и их приложения к некоторым задачам криптографии
