Алгоритм и программа генерации ключевой информации

Алгоритм и программа генерации ключевой информации

СОДЕРЖАНИЕ

Список основных сокращений

Введение

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

. ГПСП в системах защиты информации

.1 ГПСП и шифрование мультимедийных данных

.2 ГПСП и хэширование

.3 ГПСП и криптографические протоколы

.4 Вероятностное шифрование и алгоритм Эль-Гамаля

. Принципы построения и классификация ГПСП

.1 Два варианта построения ГПСП

.2 Криптографические ГПСП

.3 Линейные ГПСП

.4 Нелинейные ГПСП

. Конечные поля и ГПСП

.1 Основные понятия теории конечных полей

.2 Стохастические ГПСП

. Описание программы

.1 Основные сведения

.2 Инструкция по работе с программой

Заключение

Библиографический список

Приложение

СПИСОК ОСНОВНЫХ СОКРАЩЕНИЙ

1.      ГПСП - генератор псевдослучайной последовательности.

2.      ПСП - псевдослучайная последовательность.

.        СБИС - сверхбольшая интегральная схема.

4.      LFSR - Linear Feedback Shift Register (регистр сдвига с линейной обратной связью).

5.      RFSR - Random Feedback Shift Register (стохастический генератор псевдослучайной последовательности).

.        БУ - блок умножения.

.        OFB - Output FeedBack (режим обратной связи вывода).

.        БИС - большая интегральная схема.

.        CRC - Cyclic Redundancy Check (алгоритм нахождения циклического избыточного кода).

10.    MDC - Modification Detection Code (код проверки целостности сообщения).

11.    CBC - Cipher Block Chaining (режим сцепления блоков шифротекста).

ВВЕДЕНИЕ

Сфера применения генераторов псевдослучайных последовательностей (ГПСП) чрезвычайно широка. Можно выделить, например, следующие области их использования:

·        космическая связь;

·        коды, обнаруживающие и исправляющие ошибки;

·        встроенное самотестирование сверхбольшой интегральной схемы (СБИС);

·        защита информации и др.

Качественные псевдослучайные последовательности, являясь по своей сути детерминированными, обладают, тем не менее, практически всеми свойствами реализаций истинно случайных процессов и успешно их заменяют, так как случайные последовательности чрезвычайно сложно формировать. Настоящая работа посвящена в первую очередь ГПСП, ориентированным на использование в системах защиты информации от случайных и умышленных деструктивных воздействий. Вначале рассматриваются общие принципы проектирования непредсказуемых ГПСП, требования к таким устройствам, описываются основные строительные блоки, используемые при их создании. Уделяется внимание конгруэнтным генераторам, регистрам сдвига с линейными (LFSR) и нелинейными обратными связями. Далее рассматривается важнейший класс ГПСП, а именно последовательности, формируемые генераторами, функционирующими в конечных полях. И в завершении целиком посвящена теории стохастических ГПСП (RFSR), основными достоинствами которых являются эффективная программная и аппаратная реализация, высокое быстродействие. По этим параметрам RFSR очень незначительно уступают LFSR, при этом в отличие от последних являются нелинейными и обладают всеми свойствами криптографических ГПСП. Приводятся сведения о разработанной программе, предназначенной для генерации ПСП.

ПОСТАНОВКА ЗАДАЧИ

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

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

)        Провести тестирование программы, сравнить свойства полученных последовательностей со свойствами истинно случайных последовательностей.

1.     
ГПСП В СИСТЕМАХ ЗАЩИТЫ ИНФОРМАЦИИ

.1 ГПСП И ШИФРОВАНИЕ МУЛЬТИМЕДИЙНЫХ ДАННЫХ [8]

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

В общем случае процессы зашифрования и расшифрования могут быть описаны следующим образом

Еk: Р → С, Dk: С → Р,

где Еk, Dk, k, Р и C соответственно функции зашифрования и расшифрования, секретный ключ, пространство открытых текстов и пространство шифротекстов. При этом для любого x справедливо

(Ek(x)) = x.

На рис. 1.1, а показана схема абсолютно стойкого шифра. Шифрование информации по этой схеме суть наложение на входную информационную последовательность p ключевой последовательности k. Операция наложения, называемая гаммированием, осуществляется с помощью некоей функции F (в качестве которой очень часто используется операция XOR). Иными словами, для каждого элемента сi зашифрованной последовательности с справедливо

 = F(Pi, ki),

где pi, ki - i-e элементы соответственно исходной информационной последовательности р и ключевой последовательности k, i = (1, m), m - длина последовательностей р, с и k. Расшифрование осуществляется с использованием функции F-1, обратной F:

рi = F-1(ci, ki),

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

•              равенство длин ключа и исходного текста;

•              случайность ключа;

•              однократное использование ключа.

Дополнительные требования, предъявляемые к этой схеме, делают ее слишком дорогой и непрактичной. В результате на практике применяется схема, показанная на рис. 1.1, б, надежность которой определяется качеством используемого генератора ПСП. Функция генератора ПСП состоит в том, чтобы, используя короткий секретный ключ k как зародыш, сформировать длинную псевдослучайную последовательность γ. Каждый элемент рi исходной последовательности р шифруется независимо от других с использованием соответствующего элемента γi ключевой последовательности γ:

= F(pi, γi), pi = F-1(ci, γi).

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

 - (а)

 - (б)

Рис. 1.1. Использование генераторов ПСП при шифровании информации:

а - схема абсолютно стойкого шифра; б - схема гаммирования (синхронное поточное шифрование)

G - генератор ПСП, F- линейная (например, XOR или mod р) или нелинейная функция

Рис. 1.2. Схема гаммирования с обратной связью (самосинхронизирующееся поточное шифрование); FB - функция обратной связи, Q - элементы памяти генератора ПСП

.2 ГПСП И ХЭШИРОВАНИЕ

Важную роль в системах защиты играет хеширование информации, одна из возможных схем которого показана на рис. 1.3. Хеш-функция h(x) принимает на входе массив данных р произвольной длины и формирует на выходе хеш-образ h(p) фиксированной длины. Хеш-преобразование используется:

•              при формировании контрольных кодов, обеспечивающих проверку целостности (CRC-коды) или аутентичности (MDC-коды) информации; проверку правильности хода выполнения программ;

•              при организации парольных систем;

•              при реализации протоколов электронной подписи.

Функция h(x) должна удовлетворять следующим требованиям:

•              результат ее действия должен зависеть не только от всех битов исходного массива данных, но и от их взаимного расположения; иными словами, результат действия h(p) хеш-функции должен быть чувствителен к любым изменениям входной информационной последовательности р;

•              она должна быть вычислительно необратимой, т. е. подобрать массив данных под заданный хеш-образ можно только путем полного перебора по пространству возможных значений р;

•              она не должна иметь коллизий, т. е. задача нахождения для заданной

последовательности р другой последовательности р', р' ≠ р, такой, что h(p') = h(p), должна быть вычислительно неразрешимой.

Рис. 1.3. Хеширование информации:

а - схема формирования хеш-образа массива данных произвольной длины; б - принцип действия хеш-функции

pi - элементы (блоки) исходного массива разрядности n ≤ N, t ≤ N - разрядность хеш-образа h(p), N - разрядность генератора ПСП

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

.3 ГПСП И КРИПТОГРАФИЧЕСКИЕ ПРОТОКОЛЫ

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

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

•              спецификацию форматов пересылаемых сообщений;

•              спецификацию синхронизации действий участников;

•              описание действий при возникновении сбоев.

На рис. 1.4 показана схема симметричной аутентификации (проверки подлинности абонентов А и В) с использованием третьей, доверенной стороны С. Арбитр С использует свой генератор ПСП для формирования сеансовых ключей kAB, с использованием которых происходит взаимодействие абонентов А и В, изначально не доверяющих друг другу. Абонент А использует свой генератор ПСП для формирования случайных запросов хA, используемых в процессе взаимной аутентификации А и В. IDA, IDB - идентификаторы соответственно абонентов А и В; kAC - секретный ключ, разделяемый А и С, kBC - секретный ключ, разделяемый В и C, EAC(p) - результат шифрования сообщения р на ключе kAC, EBC(р) - результат шифрования сообщения р на ключе kBC, ЕAB(p) - результат шифрования сообщения р на ключе kAB.

Рис. 1.4. Схема симметричной аутентификации

.4 ВЕРОЯТНОСТНОЕ ШИФРОВАНИЕ И АЛГОРИТМ ЭЛЬ-ГАМАЛЯ [1, 2]

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

Еk: Р х R → С,

где Еk, k, R, С - соответственно функция зашифрования, секретный ключ, пространство открытых текстов и пространстве шифротекстов. Главная особенность вероятностного шифрования - один и тот же исходный текст, преобразованный на одном и том же ключе, может привести к появлению огромного числа различных шифротекстов.

Схема одного из возможных вариантов вероятностного симметричного блочного шифрования в режиме простой замены показана на рис. 1.5, где на вход функции зашифрования Ek поступает «расширенный» блок рi', полученный в результате конкатенации блока открытого текста pi разрядности п и двоичного набора ri разрядности т с выхода генератора ПСП. В результате зашифрования получается блок ci закрытого текста разрядности n + m. При расшифровании часть ri блока, полученного на выходе функции Dk, просто отбрасывается.

Рис. 1.5. Пример вероятностного шифрования. Ek и Dk - функции шифрования симметричной или асимметричной криптосистемы

Можно выделить следующие достоинства вероятностного шифра:

•              повышается надежность и расширяется область использования режима простой замены;

•              при шифровании используется секретная информация (последовательность r), известная только отправителю информации;

•              появляется принципиальная возможность увеличения времени жизни сеансовых ключей;

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

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

•              отношение длин блока открытого текста рi и соответствующего ему элемента ri вероятностного пространства может выступать в качестве параметра безопасности.

Недостаток у рассматриваемой схемы лишь один - шифротекст всегда длиннее соответствующего ему открытого текста.

Примером вероятностного шифрования является алгоритм Эль Гамаля - асимметричный блочный алгоритм шифрования, в котором могут использоваться блоки любой длины либо меньшей количества значащих цифр ключа (а именно числа p), либо равной количеству значащих цифр, но значение блока должно быть меньше числа p. Длина ключа может быть любой, на сегодняшний день рекомендовано не менее 1024 бит. Алгоритм базируется на проблеме вычисления дискретного логарифма. При шифровании используются подстановки (операция возведения в степень, а также операция умножения по модулю). Шифрование состоит из одного шага. В процедуре зашифрования используется рандомизатор для того, чтобы при зашифровании одинаковые блоки данных были преобразованы в разные блоки шифра. Заметим, что знать рандомизатор для расшифрования не нужно.

Пусть

p - большое простое число,

δ - случайное целое такое, что 1 ≤ δ ≤ p-2,

α, β - такие числа α δ ≡ β(mod p).

Открытый ключ: K0 = (p, α, β). Секретный ключ: Ks = (δ).

Зашифрование: выбирается произвольное r, такое, что 1 ≤ r ≤ p-2.

EK0(x) = (y1, y2), где y1 = αr mod p, а y2 = (x∙βr) mod p.

Расшифрование:

(y1, y2) = ( y2 ∙ (( y1δ mod p)-1 mod p)) mod p.

2.     
ПРИНЦИПЫ ПОСТРОЕНИЯ И КЛАССИФИКАЦИЯ ГПСП

.1 ДВА ВАРИАНТА ПОСТРОЕНИЯ ГПСП

Можно выделить два подхода при использовании в составе генераторов ПСП нелинейных функций: это использование нелинейной функции непосредственно в цепи обратной связи (рис. 2.1, а) и двухступенчатая структура (рис. 2.1, б), в которой задача первой ступени (по сути счетчика) заключается всего лишь в обеспечении максимально большого периода при данной разрядности N используемого регистра Q [8].

а                                    б                                    в

Рис. 2.1. Два варианта построения генератора ПСП:

а - с нелинейной внутренней логикой (режим OFB - Output FeedBack); б - с нелинейной внешней логикой (режим Counter); в - входной и преобразованный вектор ошибок

Q - элементы памяти генератора, FB - линейная или нелинейная функция обратной связи, Fk - нелинейная функция, k - ключ, γi - элемент выходной последовательности, е - входной вектор ошибок, содержащий 1 в разрядах, соответствующих измененным (искаженным) битам, е' - преобразованный (выходной) вектор ошибок.

.2 КРИПТОГРАФИЧЕСКИЕ ГПСП

На рис. 2.2 приведена классификация генераторов ПСП. Роль нелинейной функции Fk может выполнять функция зашифрования Еk одноключевой (классической) или двухключевой криптосистемы, при этом использование криптостойких функций Еk автоматически придает аналогичное свойство и генератору ПСП. Стойкость функций Еk современных криптосистем основывается на недоказуемом предположении о том, что у противника не хватит ресурсов (вычислительных, материальных, временных и т.п.), для того чтобы инвертировать эту функцию при неизвестном k.

Симметричные криптоалгоритмы (криптоалгоритмы с секретным ключом) делятся на три большие группы: поточные, блочные и комбинированные.

Особенности поточного шифрования:

·        каждый элемент исходной информационной последовательности шифруется на своем элементе ключевой последовательности;

·        результат преобразования отдельных элементов зависит от их позиции в исходной последовательности;

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

·        эффективная программная реализация.

Рис. 2.2. Классификация генераторов ПСП

Особенности блочного шифрования:

·        шифрованию подвергаются порции информации фиксированной длины (блоки);

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

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

Недостатки блочного шифрования:

·        одинаковым блокам открытого текста соответствуют одинаковые блоки шифротекста и наоборот;

·        нечувствительность криптосхемы к выпадению или вставке целого числа блоков;

·        существование проблемы последнего блока неполной длины.

В результате на практике чаще всего используется комбинированный подход, при котором шифрование осуществляется либо с использованием операции сцепления блоков (режим CBC), либо с использованием генераторов ПСП по схемам, показанным на рис. 1.1 (режимы OFB и Counter) и рис. 1.2 (режим CFB). При этом в качестве нелинейных функций генераторов ПСП (рис. 2.1) используются функции зашифрования соответствующих блочных криптоалгоритмов.

Особенности шифрования методом гаммирования (поточное или комбинированное шифрование в режимах OFB и Counter):

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

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

Эти не очень приятные особенности отсутствуют при шифровании в режиме гаммирования с обратной связью (поточное или комбинированное шифрование в режиме CFB).

На рис. 2.3 показан генератор ПСП ГОСТ 28147-89, который функционирует в режиме Counter, где ki, i = (1, 32), - раундовые ключи. Разрядность блока данных ГОСТа равна 64 битам, число раундов преобразования равно 32. Функция Ek построена с использованием схемы, которая носит название сбалансированной сети Фейстеля. Схема раундовой функции F показана на рис. 2.4. Ключевая информация ГОСТа - собственно ключ, состоящий из восьми 32-разрядных элементов К0, К1, ..., К7, и таблица замен размерностью 4x16x8 бит, определяющая логику работы восьми 4-разрядных блоков замены (S-блоков). Последовательность использования ключевых элементов при построении функции Ek имеет вид

К0, К1, ..., К7, К0, К1, ..., К7, К0, К1, ..., К7, К7, K6, ..., К0.

Рис. 2.3. Генератор ПСП ГОСТ 28147-89

Таким образом, в состав раунда ГОСТа входят следующие преобразования 32-разрядных двоичных наборов:

·        сложение правой половины R-блока данных с раундовым ключом;

·        разбиение результата на восемь 4-битовых элементов и замена каждого из них по таблице замен;

·        циклический сдвиг результата на 11 разрядов влево;

·        поразрядное сложение по модулю 2 (XOR) результата с левой половиной L блока данных;

·        новое значение элемента L становится равным R, новое значение элемента R становится равным результату предыдущей операции.

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

Рис. 2.4. Раундовая функция ГОСТ 28147-89

На рис. 2.5 показана схема счетчика ГОСТа, который состоит из двух независимых счетчиков со взаимно простыми числами состояний соответственно 232 и 232 - 1. В результате период последовательности на выходе схемы оказывается равным произведению 232(232 - 1). Константы С1 = 01010101h и С2 = 01010104h подобраны таким образом, чтобы каждое следующее состояние счетчика отличалось от предыдущего в каждом байте.

На рис. 2.6 показан генератор ПСП, построенный в соответствии с принятым в 2001 г. американским стандартом AES-128. Разрядность блока данных AES-128 равна 128 битам, число раундов преобразования равно 10. Функция Ek построена с использованием новой архитектуры "Квадрат". Промежуточные результаты преобразований, выполняемых в рамках криптоалгоритма AES-128, называются состояниями. Состояние (рис. 2.7, а) и раундовые ключи шифрования (рис. 2.7, б) можно представить в виде квадратного массива байтов, имеющего 4 строки и 4 столбца. Разрядность исходного секретного ключа, из которого формируются раундовые ключи, равна 128. Свойства шифра иллюстрирует рис. 2.8, из которого видно, что 2 раунда обеспечивают полное рассеивание и перемешивание информации.

Рис. 2.5. Схема счетчика ГОСТ 28147-89

Рис. 2.6. Генератор ПСП стандарта AES-128

Состояние

 - а

Раундовый ключ

 - б

Рис. 2.7. Форматы данных AES-128: а - состояние; б - раундовый ключ

Рис. 2.8. Рассеивание и перемешивание информации в AES-128

В состав раунда AES-128 входят следующие преобразования:

·        побайтовая замена байтов состояния с использованием фиксированной таблицы замен размером 8x256;

·        побайтовый циклический сдвиг строк результата - i-я строка сдвигается на i байтов влево, i = (0, 3);

·        перемешивание столбцов результата;

·        поразрядное сложение по модулю 2 (ХОR) результата с раундовым ключом.

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

Основные особенности AES-128:

·        новая архитектура «Квадрат», обеспечивающая быстрое рассеивание и перемешивание информации, при этом за один раунд преобразованию подвергается весь входной блок;

·        байт-ориентированная структура, удобная для реализация на 8-разрядных МК;

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

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

·        работа по принципу stop-and-go;

·        перемешивание двух ПСП под управлением третьей;

·        многоступенчатая структура;

·        использование S-блоков с изменяющейся в процессе работы таблицей замен;

·        использование блоков пространственного сжатия информации;

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

Одним из лучших поточных шифров является RC4 - шифр с переменным размером ключа, разработанный Р. Ривестом. Криптоалгоритм работает в режиме OFB, т. е. поток ключевой информации не зависит от открытого текста. Используются два 8-разрядных счетчика Q1 и Q2 и 8-разрядный блок замены (S-блок) (рис. 2.9), таблица замен имеет размерность 8 х 256 и является перестановкой (зависящей от ключа) двоичных чисел от 0 до 255.

Рис. 2.9. Схема генератора ПСП RC4

Рассмотрим алгоритм работы 8-разрядного генератора ПСП RC4, точнее, процедуру генерации очередного байта гаммы. Пусть S(i) и γ - содержимое ячейки с адресом i таблицы замен S-блока и очередной байт гаммы.

Один такт работы генератора ПСП RC4:

1)      Такт работы первого счетчика:

1 = (Q1 + 1) mod 28.

2)      Такт работы второго счетчика:

Q2 = (Q2 + S(Q1)) mod 28.

3)      Ячейки таблицы замен S-блока с адресами Q1 и Q2 обмениваются своим содержимым:

(Q1)↔S(Q2).

4)      Вычисление суммы содержимого ячеек таблицы замен S-блока с адресами Q1 и Q2:

Т = (S(Q1) + S(Q2)) mod 28.

5)      Считывание содержимого ячейки таблицы замен S-блока с адресом T:

γ = S(T).

Таблица замен S-блока медленно изменяется при использовании, при этом счетчик Q1 обеспечивает изменение каждого элемента таблицы, a Q2 гарантирует, что элементы таблицы изменяются случайным образом.

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

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

Односторонней функцией называется функция F: X → Y, обладающая двумя свойствами:

·        существует полиномиальный алгоритм вычисления значений F(x);

·        не существует полиномиального алгоритма инвертирования функции F.

До сих пор ни для одной функции, кандидата на звание односторонней, не доказано свойство 2.

Примером кандидата на звание односторонней функции является модульное возведение в степень, т. е. функция F(x) = ωx mod р, где р - большое простое число, ω - примитивный элемент поля GF(p).

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

Односторонняя функция в качестве функции зашифрования неприменима, так как, хотя F(x) - надежно зашифрованное сообщение х, никто, в том числе и законный получатель, не сможет восстановить х. Обойти эту проблему можно с помощью односторонней функции с секретом. Такова, например, функция Fk: X → Y; имеющая обратную Fk-1: Y → X, однако узнать обратную функцию только по Fk без знания секрета k невозможно.

Таким образом, односторонней функцией с секретом к, называется функция Fk: X → Y, зависящая от параметра k и обладающая тремя свойствами:

·        при любом k существует полиномиальный алгоритм вычисления значений Fk(x);

·        при неизвестном k не существует полиномиального алгоритма инвертирования Fk;

·        при известном k существует полиномиального алгоритма инвертирования Fk.

Функцию Fk можно использовать для зашифрования информации, а обратную ей функцию Fk-1 - для расшифрования.

При этом подразумевается, что тот, кто знает, как зашифровывать информацию» вовсе не обязательно должен знать, как расшифровывать. Так же как и в случае с односторонней функцией, вопрос о существовании односторонних функций с секретом открыт. Для практической криптографии найдено несколько функций, кандидатов на звание односторонней функции с секретом. Для них второе свойство не доказано, однако известно, что задача инвертирования эквивалентна некоторой хорошо изученной и давно известной трудной математической задаче. Это означает, что второе требование к односторонней функции с секретом заменяется более слабым условием: при неизвестном k, вероятно, не существует полиномиального алгоритма инвертирования Fk-1.

.3 ЛИНЕЙНЫЕ ГПСП

Важнейшим классом ПСП являются последовательности, формируемые генераторами на основе регистров сдвига с линейными обратными связями - LFSR (Linear Feedback Shift Register) [8]. Используемый при их анализе математический аппарат - теория линейных последовательностных машин и теория конечных полей (полей Галуа). Основными достоинствами этих генераторов являются:

·        простота аппаратной и программной реализации;

·        максимальное быстродействие;

·        хорошие статистические свойства формируемых последовательностей;

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

Наиболее известные примеры использования LFSR и математического аппарата полей Галуа:

·        CRC-коды - идеальное средство контроля целостности информации при случайных искажениях информации;

·        реализация концепции самотестирования БИС и СБИС;

·        поточные шифры А5, PANAMA, SOBER, SNOW и др.;

·        блочный шифр RIJNDAEL, принятый в 2001 г. в качестве стандарта криптографической защиты XXI века - AES.

Исходная информация для построения двоичного LFSR - так называемый образующий многочлен. Степень этого многочлена определяет разрядность регистра сдвига, а ненулевые коэффициенты - характер обратных связей. Так, например, многочлену

Ф(х) = x8 + x7 + x5 + x3 + 1

соответствуют два устройства, показанные на рис. 2.10 и 2.11. В общем случае двоичному образующему многочлену степени N

Ф(х) =  , aN=a0=1, aj∈{0,1}, j=1,(N-1)

соответствуют устройства, показанные на рис. 2.12, a (LFSR1 - схема Фибоначчи) и б (LFSR2 - схема Галуа).

Рис. 2.10. Генератор Фибоначчи (LFSR1), соответствующий

Ф(х) = х8 + х7 + х5 + х3 + 1, и его диаграмма состояний

Рис. 2.11. Генератор Галуа (LFSR2), соответствующий

Ф(х) = х8 + х7 + х5 + х3 + 1, и его диаграмма состояний

Рассмотренные устройства могут использоваться только для генерации битовых ПСП. Если необходима n-разрядная последовательность, можно предложить два варианта действий. В первом случае выбираем образующий многочлен степени N > п (еще лучше N >> n), выбираем схему LFSR1 или LFSR2 и считываем очередной n-разрядный двоичный код с соседних разрядов регистра сдвига каждые п тактов работы LFSR. Во втором случае синтезируем схему устройства, работающего в п раз быстрее исходного LFSR (иначе говоря, выполняющего за один такт своей работы преобразования, которые в исходном LFSR выполняются за п тактов). Этот вариант особенно эффективен в тех случаях, когда образующий многочлен генератора Фибоначчи имеет вид Ф(х) = xN + xi + 1, а i кратно п (рис. 2.13).

Рис. 2.12. Общий вид LFSR, соответствующих

Ф(х) = хN + аN-1хN-1 + ... + аiхi + ... + а2х2 + а1х + 1:

 - схема генератора Фибоначчи; б - схема генератора Галуа.

БУ - блоки умножения на aj ∈ {0,1}; qj(t) ∈ {0,1};

при aj = 1 умножение на aj равносильно наличию связи; при aj = 0 умножение на aj равносильно отсутствию связи

Общий вид генератора двоичных последовательностей, соответствующего уравнению

(t + 1) = Tk Q(t),

где Q(t) и Q(t+1) - состояния регистра генератора ПСП соответственно в моменты времени t и t+1 (до и после прихода синхроимпульса); T - квадратная матрица порядка N вида

,

N - степень образующего многочлена

 - натуральное, показан на рис. 2.14. В частном случае при k = 1, получаем либо схему генератора Фибоначчи (T = T1), либо схему генератора Галуа (T = T2).

Рис. 2.13. Байтовый генератор ПСП:

а - битовый генератор Фибоначчи, соответствующий многочлену Ф(х) = х65 +x32 +1; б - байтовый генератор Фибоначчи, соответствующий Ф(х) = х65 + х32 + 1, qi - состояние i-гo разряда LFSR1, i =

Рис. 2.14. Генератор двоичных последовательностей, соответствующий уравнению Q(t +1) = TkQ(t)

Величина, на которую происходит умножение в каждом блоке умножения (БУ), определяется соответствующим коэффициентом aij сопровождающей матрицы:

Если аij = 0, это эквивалентно отсутствию связи между выходом i-го разряда регистра генератора и входом j-го сумматора по модулю два. Если аij = 1, это эквивалентно наличию связи между выходом i-го разряда регистра генератора и входом j-го сумматора по модулю два.

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

Многочлен Ф(х) степени N называется примитивным, если он не делит нацело ни один многочлен вида xS - 1, где S < 2N - 1. Примитивные многочлены существуют для любого N. Показателем многочлена Ф(х) называется наименьшее натуральное число е, при котором хе - 1 делится на Ф(х) без остатка.

Пусть Ф(х) - примитивный многочлен степени N, тогда справедливо следующее утверждение.

Свойство 1.1. Формируемая последовательность имеет максимальный период S = 2N - 1 тогда и только тогда, когда наибольший общий делитель чисел S и k равен 1 (т. е. S и k взаимно просты).

Следствие. При k = 1 примитивность Ф(х) является необходимым и достаточным условием получения последовательности максимальной длины.

Последовательность максимальной длины принято называть М-последовательностью, а формирующий ее генератор - генератором М-последовательности. Именно генераторы M-последовательностей обычно используются для формирования ПСП.

Каждая матрица V имеет характеристический многочлен φ(х) которым является определитель матрицы V - хЕ, т. е. φ(х) = |V - хЕ|, где Е - единичная матрица. Многочлен Ф(х) определяет только структуру генератора, свойства же последнего зависят именно от φ(х).

Свойство 1.2. Каждая квадратная матрица удовлетворяет своему характеристическому уравнению, т. е. φ(V) = 0.

Свойство 1.3. Характеристический и образующий многочлен генератора связаны следующим соотношением:

φ(х) = Ф(x-1)xN,

т. е. являются взаимно обратными.

Примитивность φ(x) автоматически означает примитивность Ф(х) и наоборот.

Децимацией последовательности {qi(t)} по индексу k называется формирование новой последовательности {q*i(t)}, состоящей из k-х элементов {qi(t)}, т. е. q*i(t) = qi(kt). Если период последовательности, полученной в результате децимации М-последовательности, равен максимальному, децимация называется собственной или нормальной.

Последовательность, снимаемая с выхода i-го триггера генератора, изображенного на рис. 2.14, является децимацией по индексу k последовательности, снимаемой с выхода i-го триггера генераторов, изображенных на рис. 2.12. Если Q - начальное состояние генератора, то последовательности состояний, в которых будут находиться устройства в следующие моменты времени, имеют вид

, QV, QV2, QV3, ...

(для устройства, изображенного на рис. 2.8) и

, QT, QT2, QT3, ...

(для устройств, изображенных на рис. 2.12, где Т = Т1 (а) или Т = Т2 (б)). Учитывая, что V = Tk, можно сделать вывод, что в генераторе, показанном на рис. 2.14, за один такт осуществляются преобразования, которые в генераторах, показанных на рис. 2.12, происходят за k тактов. Таким образом, устройство, показанное на рис. 2.14, в котором содержимое первых k триггеров (при k ≤ N) полностью обновляется в каждом такте, может использоваться для генерации последовательности k-разрядных двоичных кодов, что нельзя сказать про устройства, показанные на рис. 2.12, которые формируют лишь сдвинутые копии одной и той же двоичной последовательности.

.4 НЕЛИНЕЙНЫЕ ГПСП [7]

Генераторы последовательностей длиной pN.

Исключение запрещенного нулевого состояния всех разрядов генератора двоичных М-последовательностей позволяет увеличить период формируемой последовательности и сделать его максимально возможным, равным pN, и повысить ее качество. Например, при р = 2 вероятности появления 0 и 1 становятся равными 1/2. Последовательности длиной 2N называются последовательностями де Брейна (De Bruijn). Рассмотрим схему Фибоначчи. Уравнения работы генератора последовательности длиной 2N имеют вид

.

Рассмотрим формирование последовательности длиной pN по схеме Фибоначчи, p ≠ 2, k = 1. Выберем α*  GF(p), α* ≠ 0. Пусть

Тогда уравнения работы генератора последовательности длиной pN имеют вид

(t+1) = Qj-1(t), j=.

Пусть p = 2n. Рассмотрим формирование последовательности длиной 2nN, k = 1. Выберем α*GF(p), α* ≠ 0. Пусть

Тогда уравнения работы генератора последовательности длиной pnN имеют вид

Qj(t+1)=Qj-1(t), j = .

Рассмотрим формирование последовательности длиной pN, р ≠ 2, в общем случае при произвольном k. Выберем αi*  GF(p), αi* ≠ 0, j = . Пусть

Тогда уравнения работы генератора последовательности длиной pN имеют вид

где aji - коэффициенты матрицы Tk.

Пусть p = 2. Рассмотрим формирование последовательности длиной 2nN при произвольном k. Выберем αi*  GF(p), αi* ≠ 0, j = . Пусть

Тогда уравнения работы генератора последовательности длиной 2nN имеют вид

Генераторы ПСП с предпериодом.

Рассмотрим принципы построения генераторов последовательностей произвольной длины.

Алгоритм построения генератора p-ичной последовательности длины S < pN:

1.      Выбирается примитивный многочлен Ф(х) степени N.

2.      Фиксируется произвольное ненулевое состояние Q0 генератора.

3.      Моделируется t=pN-S тактов работы генератора ПСП и определяется состояние Qt.

4.      Выполняется поразрядная операция XOR над кодами Q1 и Qt. Единичные биты результата определяют номера тех разрядов генератора, сигналы на входах которых необходимо инвертировать, когда генератор находится в состоянии Q0.

5.      Управляемые инверторы реализуются на дополнительных элементах XOR, число которых и место в схеме генератора определяются результатом операции Q1  Qt.

Рассмотрим конечное поле из 2n элементов - GF(2n). Алгоритм построения универсального генератора ПСП следующий.

1.      Строится генератор последовательности длиной 2nN по методике, рассмотренной выше.

2.      Выбирается произвольное состояние генератора

β*1 β*2… β*N, β*i GF(2n), i = .

3.      Тогда уравнения работы универсального генератора имеют вид

где

MSi = (msi(n-1) … msi1msi0), msik  {0, w(t)}, k = ;

4.      Определяются значения периода и предпериода генератора для всех возможных значений (MS1MS2 ... MSN).

3.     
КОНЕЧНЫЕ ПОЛЯ И ГПСП

.1 ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ КОНЕЧНЫХ ПОЛЕЙ

Поле - это множество элементов, обладающее следующими свойствами:

·        в нем определены операции сложения, вычитания, умножения и деления;

·        для любых элементов поля α, β и γ должны выполняться соотношения (свойства ассоциативности, дистрибутивности и коммутативности)

α+β=β+α, αβ = βα, α + (β+γ) = (α + β)+γ,

α(βγ) = (αβ)γ, α(β+γ) = αβ + αγ;

·        в поле должны существовать такие элементы 0, 1, -α и (для α ≠ 0) α-1, что

+ α = α, α + (-α) = 0, 0α = 0,1α = α, α(α-1) = 1;

·        все ненулевые элементы конечного поля могут быть представлены в степени некоторого фиксированного элемента поля ω, называемого примитивным элементом. [8]

Конечное поле содержит конечное число элементов. Поле из L элементов обозначается GF(L) и называется полем Галуа в честь первооткрывателя Эвариста Галуа (1811-1832).

Простейшие поля получаются следующим образом. Пусть р - простое число. Тогда целые числа 0, 1, 2, ... , (р - 1) образуют поле GF(p), при этом операции сложения, вычитания, умножения и деления выполняются по модулю р. Более строго, GF(p) - это поле классов вычетов по модулю р, т. е.

GF(p) = {0, 1, 2, ... , (р - 1)},

где через 0 обозначаются все числа, кратные р, через 1 - все числа, дающие при делении на р остаток 1, и т. д. С учетом этого вместо р - 1 можно писать -1. Утверждение α = β в GF(p) означает, что α - β делится на р или что α сравнимо с β по модулю р, т. е.

α ≡ β(mod р).

Поле, содержащее L = рn элементов, где р - простое число, а n - натуральное, не может быть образовано из совокупности целых чисел по модулю L. Например, во множестве классов вычетов по модулю 4 элемент 2 не имеет обратного, так как 2∙2 = 0. Таким образом, хотя это множество состоит из 4 элементов, оно совсем не похоже на поле GF(L). Чтобы подчеркнуть это различие, обычно вместо GF(4) пишут GF(22).

Элементами поля из рn элементов являются все многочлены степени не более п - 1 с коэффициентами из поля GF(p). Сложение в GF(pn) выполняется по обычным правилам сложения многочленов, при этом операции приведения подобных членов осуществляются по модулю р. Многочлен с коэффициентами из GF(p) (т. е. многочлен над полем GF(p)), не являющийся произведением двух многочленов меньшей степени, называется неприводимым. Примитивный многочлен автоматически является неприводимым. Выберем фиксированный неприводимый многочлен φ(x) степени n. Тогда произведение двух элементов поля получается в результате их перемножения с последующим взятием остатка после деления на φ(х). Таким образом, поле GF(pn) можно представить как поле классов эквивалентности многочленов над GF(p). Два таких многочлена объявляются эквивалентными, если их разность делится на φ(х). Конечные поля порядка рп существуют для всех простых р и всех натуральных n.

3.2 СТОХАСТИЧЕСКИЕ ГПСП [3, 8]

В качестве одного из алгоритмов нелинейного преобразования элементов xi n-разрядной информационной последовательности

такой же длины и качественного генератора псевдослучайных последовательностей (ПСП) с числом состояний 2n можно предложить следующий (рис. 3.1). Для каждого элемента xi (i = ) повторяем нижеприведенную последовательность действий:

·        очередной элемент хi входной последовательности загружаем в память генератора ПСП;

·        выполняем γi тактов работы генератора;

·        состояние генератора после γi тактов работы при начальном состоянии xi объявляем результатом γi преобразования элемента xi.

После преобразования всех элементов исходной последовальности будет получена результирующая последовательность

= y1y2y3 ... yi ... ym

длинной m, для каждого элемента которой справедливо

 = R(xi, γi).

Данное преобразование может эффективно использоваться для решения различных задач, связанных с защитой информации. Впервые оно было предложено С. А. Осмоловским для реализации стохастического кодирования информации [2, 3]. В данной главе рассматривается его применение для построения генераторов ПСП.

Рис. 3.1. Стохастическое преобразование информационной последовательности {хi}

R-Блок.

Схема одного из возможных вариантов построения блока R стохастического преобразования (Random) и его условное графическое обозначение показаны соответственно на рис. 3.2 и 3.3. Ключевая информация R-блока - характер заполнения таблицы

Н = {Н(m)}, m = ,

размерности n  2n, содержащей элементы GF(2n), перемешанные случайным образом, т. е. Н(m)  GF(2n). Результат RH(A, В) преобразования входного n-разрядного двоичного набора А зависит от заполнения таблицы H и параметра преобразования В, задающего смещение в таблице относительно ячейки, содержащей значение А, следующим образом:

(А, В) = H ((mA + В) mod 2n),

где mА - адрес ячейки таблицы H, содержащей код А, т. е. H(mА) = А. Другими словами, результат работы R-блока суть считывание содержимого ячейки таблицы H, циклически смещенной на В позиций в сторону старших адресов относительно ячейки, содержащей код A.

Рис. 3.2. Логика работы R-блока

Рис. 3.3. Условное графическое обозначение R-блока

Для ускорения преобразования в состав R-блока вводится вспомогательный адресный массив= {Addr(j)}

размерности n  2n, причем

Иными словами, ячейка с адресом j в массиве Addr хранит адрес ячейки массива H, содержащей код j.

Заслуживают внимания следующие факты:

·        при Addr = {0, 1, 2, … , (2n-1)}, т. е. при записи в каждую ячейку массива Addr ее собственного адреса, и n = 4 результат преобразования в точности совпадает с результатами работы двух тактов (сложение с 4 битами ключа и замена в соответствующем узле замены) одной секции раундовой функции российского стандарта криптографической защиты, ГОСТ 28147-89;

·        в частном случае при Addr = {0, 1, 2, (2n-1)} и В = 0 получаем классический S-блок (блок замены) с таблицей замен H;

·        при записи в каждую ячейку массивов H и Addr ее собственного адреса получаем классический сумматор по модулю 2n, а значит, с полным на то основанием R-блок может быть назван стохастическим сумматором;

·        по такому же принципу (заменой сумматора по модулю 256 на операцию поразрядного XOR) может быть построен стохастический сумматор в поле GF(28) (стохастический XOR), а также другие элементы (AND, OR, mod р и т. п.) ;

·        требует дополнительного исследования схема стохастического преобразования, показанная на рис. 3.4, где функция F - сумматор по модулю 2 или поразрядный XOR (а возможно и другие операции AND, OR, mod р и т. п.).

Рис. 3.4. Вариант схемы блока стохастического преобразования (RF-блок)

Ключевая информация, необходимая для работы R-блока, - содержимое таблицы H стохастического преобразования. Алгоритм замены ключевой информации, т. е. «перемешивания» или «взбивания» таблиц H, показан на рис. 3.5. Каждая очередная пара байтов

, BYTEi+1

инициализирующей последовательности меняет местами два соответствующих элемента массива H, т. е. выполняется операция

(BYTEi) ↔ H(BYTEi+1), i = 0, 2, 4, ...,

где H(j) - элемент массива H, расположенный в ячейке с адресом j. Алгоритм формирования вспомогательного массива Addr показан на рис. 3.6.

Рис. 3.5. Схема алгоритма «перемешивания» таблицы стохастического преобразования с использованием инициализирующей ПСП BYTE0, BYTE1, BYTE2, ... , BYTEi, BYTEi+1, ...

Рис. З.6. Схема алгоритма формирования адресного массива Addr по известному массиву Н

Существует еще один возможный алгоритм формирования таблицы стохастического преобразования, его схема приведена на рис. 3.7. Для создания таблицы H может быть применен также любой из известных алгоритмов создания таблицы замены, например алгоритм, реализованный в поточном шифре RC4. Учитывая, что циклически сдвинутые таблицы стохастического преобразования эквивалентны, существует 255! различных вариантов заполнения таблицы H.

Рис. 3.7. Схема алгоритма формирования таблицы стохастического преобразования с использованием инициализирующей ПСП BYTE0, BYTE1, BYTE2, ..., BYTEi, ...

случайный последовательность мультимедийный шифрование

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

Стохастические генераторы многоразрядных ПСП на регистрах сдвига - RFSR

Для построения стохастического генератора ПСП (Random Feedback Shift Register - RFSR) предлагается в схемах аддитивного генератора вместо блоков сложения использовать R-блоки (рис. 3.8). Ключевая информация - заполнение таблиц H, определяющих логику работы R-блоков.

Рис. 3.8. Общие схемы стохастических генераторов n-разрядной ПСП (режим OFB) с управляющим входом. Qi - состояние i-го регистра генератора

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

Рассмотрим вариант схемы генератора с одним R-блоком, который может быть представлен в одном из двух идентичных вариантов (рис. 3.9, а - RFSR1 или 3.9, б - RFSR2).

Рис. 3.9. Варианты схемы стохастического генератора RFSR с одним R-блоком (режим OFB)

При соответствующем выборе таблицы стохастического преобразования выходная ПСП по сути - это нелинейная M-последовательность, т. е. последовательность максимальной длины, по своим статистическим свойствам превосходящая классическую M-последовательность с выхода LFSR той же разрядности (рис. 3.10-3.11).

Рис. 3.10. Стохастический генератор при N = 2:

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

На рис. 3.10 и 3.11 показаны примеры генераторов стохастической М-последовательности длиной соответственно 15 и 63.

На рис. 3.12 приведен пример преобразования стохастического генератора, диаграмма состояний которого состоит из трех циклов длиной 22, 25, 16 и одного тривиального цикла, состоящего из состояния 000, переходящего самого в себя, в генератор последовательности длиной 64. Преобразование потребовало включения в состав устройства сумматора и элемента ИЛИ-НЕ, выход которого соединен с входом переноса сумматора. Переходы исходного генератора на рис. 3.12 показаны пунктирной линией.

Рис. 3.11. Стохастический генератор при N = 3:

а - схема генератора и таблица стохастического преобразования; б - диаграмма его переключений

На рис. 3.13 приведена схема генератора ПСП с непрерывно изменяющейся таблицей стохастического преобразования. В каждом такте работы такого RFSR слово (BYTEi+1, BYTEi) с выхода управляющего генератора меняет местами содержимое двух ячеек таблиц Н:

(BYTEi+1) ↔ H(BYTEi).

Рис. 3.12. Стохастический генератор ПСП длиной 64:

а - схема генератора и таблица стохастического преобразования; б - диаграмма его переключений

Рис. 3.13. Схема генератора ПСП с непрерывно изменяющейся таблицей стохастического преобразования

4.     
ОПИСАНИЕ ПРОГРАММЫ

.1 ОСНОВНЫЕ СВЕДЕНИЯ

Общие сведения:

Наименование программы: «Cryptographically Strong Key Algorithm and Analysis (CSKA)» (алгоритм и анализ криптографически стойкой ключевой последовательности) может применяться для генерации ключевой последовательности используя криптографически стойкий алгоритм нелинейного (стохастического) преобразования для решения различных задач, связанных с защитой информации.

Языки программирования: Delphi Enterprise Version 7.0 с использованием стандартных библиотек, а также библиотеки Math.

Программное обеспечение: Windows 98, 2000, XP, Vista, Windows 7.

Функциональное назначение:

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

Описание логической структуры:

Модули.urfsr; {Главный модуль}uGistogramm; {Модуль отображения результата теста построения гистограммы}uRaspredelenie; {Модуль отображения результата теста распределения на плоскости}uMonotonnost; {Модуль отображения результата теста на монотонность}uSeries; {Модуль отображения результата теста проверки серий}uKnyt; {Модуль отображения результата теста Д. Кнута}

Процедуры.Fill; {формирование ключевой последовательности из 16 чисел разрядности 9}GetStirlingNumbers(n_max, m_max: Integer; var StirlingNumbers: TTwoDimArray); {вычисление таблицы значений Стирлинга}Run; {построение блока R стохастического преобразования(Random)}

Кнопки на форме.

procedure bClearClick(Sender: TObject); {очистка формы отображения ключевой последовательности}

procedure bCloseClick(Sender: TObject); {закрытие программы}

procedure bDotClick(Sender: TObject); {процедура тестирования зависимости между элементами исследуемой последовательности}bGistoClick(Sender: TObject); {процедура тестирования равномерности распределения символов в исследуемой последовательности}bKnytClick(Sender: TObject); {процедура тестирования статистических свойств исследуемой последовательности, автор Д. Кнут}bMonotClick(Sender: TObject); {процедура тестирования равномерности распределения символов в исследуемой последовательности на основании участков неубывания и невозрастания}bRunClick(Sender: TObject); {выполнение операции формирования ключевой последовательности по нажатию кнопки на форме}bRunNClick(Sender: TObject); {выполнение операции формирования заданного количества ключевых последовательностей по нажатию кнопки на форме}bSeriesClick(Sender: TObject); {процедура тестирования равномерности распределения символов в исследуемой последовательности на основании появления серий единиц и нулей}

Элементы меню.AboutClick(Sender: TObject); {о программе}

procedure Open1Click(Sender: TObject); {открытие файла сохраненной ключевой последовательности}SaveAsClick(Sender: TObject); {сохранение сформированной ключевой последовательности в файл}SaveClick(Sender: TObject); {сохранение сформированной ключевой последовательности в файл}SaveKeyClick(Sender: TObject); {сохранение кодированной в двойчную систему исчисления сформированной ключевой последовательности в файл}

В качестве алгоритма программы используется генерация ключевой последовательности по формуле , где ma - таблица случайных чисел, сгенерированных с помощью Random, B - константа смещения, заданная пользователем на форме. Далее у пользователя есть возможность провести тестирование создано ключевой последовательности/последовательностей, которые используют анализ либо сформированной последовательности либо в оригинальном виду, либо кодированном в двоичный код.

Используемые технические средства:

Процессор: Intel Pentium II и выше (могут использоваться мобильные устройства). Оперативная память: при работе использует около 6 МБ. Пространство на жестком диске: 600 Кб. Монитор: VGA или выше.

Вызов и загрузка:

Вызов программы осуществляется с жесткого диска или флеш-накопителя путем запуска исполнительного файла «CryptoSKA.exe».

Входные данные:

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

Выходные данные:

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

Интерфейс программы:

На рис 4.1 приведено главное окно для работы с программой.

Рис. 4.1. Главное окно программы «Cryptographically Strong Key Algorithm and Analysis (CryptoSKA)»

4.2    ИНСТРУКЦИЯ ПО РАБОТЕ С ПРОГРАММОЙ

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

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

После запуска программы в поле «Сгенерированная ключевая ПСП» отобразиться ключевая последовательность, которая была сформирована с помощью переменной, заданной в поле «Константа смещения» (по стандарту 3073) автоматически. Для генерации другой последовательности необходимо нажать кнопку «Очистить» для очистки поля результата «Сгенерированная ключевая ПСП», задать параметр смещения «Константа смещения», либо оставить его без изменений и нажать кнопку «Сгенерировать», на открытом текстовом поле отобразится новая сгенерированная ключевая последовательность. Если поле до этого не было очищено, то последовательность будет добавлена в следующую строку после уже находящейся в текстовом поле информации.

При необходимости открыть сформированную ранее тестируемую последовательность, необходимо нажать «Файл» → «Открыть», для сохранения текущей - «Файл» → «Открыть», либо «Файл» → «Открыть как…» в зависимости от необходимости задания имени файла. Для итогового сохранения 77-разрядного ключа в текстовый файл необходимо нажать «Сохранить ключ».

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

Графические тесты.

1)      Тест «Гистограмма распределения элементов».

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

Окно с результатом тестирования приведено на рис. 4.2.

Рис. 4.2. Окно результата работы теста «Гистограмма распределения элементов»

2)      Тест «Распределение на плоскости».

Данный тест предназначен для определения зависимостей между элементами исследуемой последовательности. Построение распределения на плоскости осуществляется следующим образом. На поле размером  (R - разрядность чисел исследуемой последовательности) наносятся точки с координатами (xi; xi+1), где xi - элементы исследуемой последовательности x,  n - длина последовательности. Далее анализируется полученная картина. Если между элементами последовательности отсутствуют зависимости, то точки на поле расположены хаотично. Если на поле присутствуют зависимости, наблюдаются «узоры» - последовательность не является случайной. Для последовательностей большой длины хорошим результатом является абсолютно черное поле.

Окно с результатом тестирования приведено на рис. 4.3.

Рис. 4.3. Окно результата работы теста «Распределение на плоскости»

3)      Тест «Проверка на монотонность».

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

Окно с результатом тестирования приведено на рис. 4.4.

Рис. 4.4. Окно результата работы теста «Проверка на монотонность»

4)      Тест «Проверка серий».

Данный тест позволяет оценить равномерность распределения символов в исследуемой последовательности на основе анализа частоты появления нулей и единиц и серий, состоящих из k-бит. Построение осуществляется следующим образом. Подсчитывается, сколько раз встречаются нули, единицы, серии-двойки (00, 01, 10, 11), серии-тройки (000, 001, 010, 011, 100, 101, 110, 111) в битовом представлении исследуемой последовательности. Полученные результаты представляются в графическом виде. У последовательности, чьи статистические свойства близки к свойствам истинно случайно последовательности, разбросы между числом появлений нулей и единиц, между числом появлений серий пар каждого вида и между числом появления серий-троек каждого вида должны стремиться к нулю. В противном случае последовательность не является случайной.

Окно с результатом тестирования приведено на рис. 4.5.

Рис. 4.5. Окно результата работы теста «Проверка серий»

Оценочные тесты.

1)      Тест Д. Кнута «Проверка несцепленных серий».

Цель теста - исследовать последовательность на случайность, анализируя длины несцепленных серий различной длины. Пусть ε = ε1ε2…εn - двоичная последовательность длины n и m - длина серии. Подсчитывается число появлений всевозможных непересекающихся серий длиной m (лишние биты отбрасываются) и вычисляется статистика:

Полученный результат анализируется при помощи критерия χ2 с числом степеней свободы 2m - 1.

2)      Тест Д. Кнута «Проверка комбинаций».

Данный тест определяет равномерность распределения символов в исследуемой последовательности, анализируя различные комбинации чисел в подпоследовательностях. Пусть ε = ε1ε2…εn - последовательность m-разрядных чисел длины n. Разобьем её на последовательности длинной t каждая (лишние биты отбрасываются). Подсчитывается число подпоследовательностей νi, i = , содержащих i различных чисел, и вычисляется статистика:

 - числа Стирлинга.

Числом Стирлинга из k по r, обозначаемым  или , называется количество неупорядоченных разбиений k-элементного множества на r непустых подмножеств. Явная формула для подсчета чисел Стирлинга следующая:

Полученный результат анализируется при помощи критерия χ2 с числом степеней свободы r - 1.

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

Рис. 4.6. Окно результата работы оценочных тестов

Критические значения  распределения Пирсона [8]

Сравним полученные нами значения  и критические значения  распределения с заданным числом степеней свободы и уровнями значимости 0,01 и 0,05 из таблицы критических значений  распределения Пирсона, где k - степень свободы, α - уровень значимости:

1)      по тесту «Проверка несцепленных серий» для серий из 1 цифры получим 0,96 < 24,99579 < 30,58;

)        по тесту «Проверка несцепленных серий» для серий из 2 цифр получим 4,03 < 24,99579 < 30,58;

)        по тесту «Проверка несцепленных серий» для серий из 3 цифр получим 8,38 < 24,99579 < 30,58;

)        по тесту «Проверка комбинаций» для серий из 1 цифры получим 4,32 < 7,81473 < 11,34487.

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

Текст программы находится в Приложении.

ЗАКЛЮЧЕНИЕ

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

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1.       Воронков Б.Н. Элементы теории чисел и криптозащита: учеб. пособие для вузов / Б. Н. Воронков - Воронеж: Воронежский ГУ, 2008. - 87с.

2.      Воронков Б.Н. Криптографические методы защиты информации: учеб. пособие для вузов / Б. Н. Воронков - Воронеж: Воронежский ГУ, 2008. - 58с.

.        Осмоловский С.А. Стохастические методы передачи данных: учеб. пособие / С. А. Осмоловский - М.: Радио и связь, 1991. - 240с.

4.      ООО «СТОКОС» - Инновационные разработки IT-технологий: [сайт]. - (URL: <http://www.stokos.ru/>) (дата обращения: 24.03.2013).

5.       Пат. 2367007 Российская Федерация, МПК G06F 11/00 H04L 1/20 H03M 13/35. Способ передачи и комплексной защиты информации / Осмоловский С.А. - № 2007132646/09 ; заявл. 30.08.2007 ; опубл. 10.09.2009, Бюл. № 25. - 22с. : ил.

6.      Иванов М.А. Стохастические методы и средства защиты информации в компьютерных системах и сетях: учеб. пособие / М. А. Иванов, А. В. Ковалев, Н. А. Мацук, Д. М. Михайлов, И. В. Чугунков - М.: КУДИЦ-ПРЕСС, 2009. - 512с.

.        Иванов М.А. Теория, применение и оценка качества генераторов псевдослучайных последовательностей: учеб. пособие / М. А. Иванов, И. В. Чугунков - М.: КУДИЦ-ОБРАЗ, 2003. - 240с.

8.      Квантили распределения хи-квадрат: [сайт]. - (URL: <http://ru.wikipedia.org/wiki/Квантили_распределения_хи-квадрат>/) (дата обращения: 04.06.2013).

ПРИЛОЖЕНИЕ

Текст программы «Cryptographically Strong Key Algorithm and Analysis (CSKA)».urfsr; {Главный модуль}, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,, StdCtrls, ExtCtrls, TeeProcs, TeEngine, Chart, Series, Buttons,, CheckLst, ComCtrls, Spin, Math;= array of array of Double;= array [0..15] of integer;= array [0..999999] of integer;= class(TForm): TMenuItem; //описание элементов формы: TButton;: TButton;: TButton;: TButton;: TButton;: TButton;: TButton;: TButton;: TButton;: TOpenDialog;: TSaveDialog;: TMenuItem;: TMenuItem;: TLabel;: TLabel;: TLabel;: TLabel;: TLabel;: TLabel;: TLabel;: TLabel;: TMainMenu;: TMemo;: TMenuItem;: TMenuItem;: TMenuItem;: TMenuItem;: TSpinEdit;: TSpinEdit;: TSpinEdit;AboutClick(Sender: TObject); //процедуры элементов управления с формыbClearClick(Sender: TObject);bCloseClick(Sender: TObject);bDotClick(Sender: TObject);bGistoClick(Sender: TObject);bKnytClick(Sender: TObject);bMonotClick(Sender: TObject);bRunClick(Sender: TObject);bRunNClick(Sender: TObject);bSeriesClick(Sender: TObject);Open1Click(Sender: TObject);SaveAsClick(Sender: TObject);SaveClick(Sender: TObject);SaveKeyClick(Sender: TObject);

{ Private declarations } Run; {построение блока R стохастического преобразования(Random)}

procedure Fill; {формирование ключевой последовательности из 16 чисел}

procedure GetStirlingNumbers(n_max, m_max: integer; var StirlingNumbers: TTwoDimArray); //числа Стирлинга

{ Public declarations };: TForm1;: integer; //параметр размерности тестируемого массива с формы

Z: mas; //массив случайных чисел, формирующий ключевую последовательность

b: mass; //вспомогательный массив-счетчик для проведения тестов

outN: TstringList; //переменная для хранения кодированной последовательности

implementationuGistogramm, uRaspredelenie, uMonotonnost, uSeries, uKnyt;

{$R *.dfm}

procedure TForm1.bRunClick(Sender: TObject); {выполнение операции формирования ключевой последовательности по нажатию кнопки на форме}

begin:= TStringList.Create;;;

procedure TForm1.Fill; {формирование ключевой последовательности из 16 чисел разрядности 9}

var a: string; i, k: integer;

Run;

a := '';

for i := 0 to 15 do //цикл восстановления корректной разрядности (9) в таблице из 16 случайных чисел

begink := length(inttostr(Z[i])) to 8 do:= a + '0';:= a + inttostr(Z[i]);;

outN.Add(copy(a, 1, 77)); //формирование ключевой последовательности из первых 77 чисел

mmo1.Lines.Add(a); //вывод на экран ключевой последовательности из 144 чисел

end;

procedure TForm1.Run; {построение блока R стохастического преобразования(Random)}

var i, c: integer; R: mas;

c := strtoint(sConst.text); //задаваемый пользователем параметр преобразования, задающий смещение для формирования ключевой последовательности

for i := 0 to 15 do //цикл формирования таблицы из 16 случайных чисел

R[i] := Random(536870913); //случайное число из отрезка [0..536870912]

for i := 0 to 15 do //цикл генерации ключевой информации из сформированного массива случайных чисел

begin

Z[i] := (R[Random(16)] + c) mod 536870912; //вычисление модуля случайного числа, смещенного на заранее заданную константу смещения "с"

end;

end;

procedure TForm1.bRunNClick(Sender: TObject); {выполнение операции формирования заданного количества ключевых последовательностей по нажатию кнопки на форме}

var i: integer;:= TStringList.Create; i := 1 to strtoint(sNum.text) do //число необходимых последовательностей считывается с формы

Fill;;TForm1.bCloseClick(Sender: TObject); {закрытие программы};;TForm1.Open1Click(Sender: TObject); {открытие файла сохраненной ключевой последовательности}dOpen doExecute then.Lines.LoadFromFile(filename);.add(filename);:= 'Генератор Псевдослучайных Последовательностей - ' + ExtractFileName(FileName);.filename := filename;;; TForm1.SaveClick(Sender: TObject); {сохранение сформированной ключевой последовательности в файл}

begindOpen.FileName <> '' then.Lines.SaveToFile(dSave.FileName)(Sender);;TForm1.SaveAsClick(Sender: TObject); {сохранение сформированной ключевой последовательности в файл}dSave doexecute then.Lines.SaveToFile(FileName); := 'Генератор Псевдослучайных Последовательностей - ' + ExtractFileName(FileName);

end;

end;

procedure TForm1.SaveKeyClick(Sender: TObject); {сохранение кодированной в двойчную систему исчисления сформированной ключевой последовательности в файл}

begindSave doexecute then.SaveToFile(FileName);;;TForm1.AboutClick(Sender: TObject); {о программе}

MessageDlg('Генератор псевдослучайных последовательностей v 1.00', mtInformation, [mbOK],0);

end;

procedure TForm1.bClearClick(Sender: TObject); {очистка формы отображения ключевой последовательности}

begin

mmo1.Clear;

end;

procedure TForm1.bGistoClick(Sender: TObject); {процедура тестирования равномерности распределения символов в исследуемой последовательности}

var i, j, f, max: integer; a: string;

gType := strtoint(sType.text); //разрядность для считывания из ключевой последовательности

Form2.Show;.Series1.Clear; := 0;

for i := 1 to gType do max := max * 10 + 9; //нахождение максимального значения "max" по заданной разрядности

for i := 0 to max do b[i] := 0; //обнуление массива-счетчика повторений

for i := 0 to mmo1.Lines.Count - 1 do //цикл подсчета повторяющихся значений в ключевой последовательности

begin

a := mmo1.Lines[i]; //считывание из ключевой последовательности построчно

j := 1; //счетчик перемещения по последовательности

while j <= length(a) do //цикл подсчета количества повторяющихся чисел заданной разрядности gType до конца строки

begin

f := strtoint(copy(a, j, gType)); //копируем из последовательности число согласно разрядности

j := j + gType;

inc(b[f]); //счетчик повторений

end;

end;

for i := 0 to max do //вывод на форму гистограммы по найденным значениям

begin.Series1.AddXY(i, b[i]);;

end;

procedure TForm1.bDotClick(Sender: TObject); {процедура тестирования зависимости между элементами исследуемой последовательности}

var i, j, x, y: integer; a: string; sD: real;:= strtoint(sType.text);.Show;.Image1.Canvas.Brush.Color := clWhite; //сбрасываем на белый фон поля для отображения3.Image1.Canvas.FillRect(Rect(0, 0, 909, 909)); //задаём размер на форме для отображения результата

sD := 11; //делитель разрядности 4 для отображения на форме всех найденных значений

if gType = 3 then sD := 1.1 else //подсчет делителя для заданной разрядности

if gType = 2 then sD := 0.1 elsegType = 1 then sD := 0.01 elsegType = 5 then sD := 110.01 elsegType = 6 then sD := 1100.1; := 0;

for i := 0 to mmo1.Lines.Count - 1 do //цикл исследования по всем сформированным ключевым последовательностям

begin

a := mmo1.Lines[i]; //считывание из ключевой последовательности построчно

j := 1; //счетчик перемещения по последовательности

while j < length(a) do //цикл считывания значений требуемой разрядности из ключевой последовательности

begin

j := j + gType;

Form3.Image1.Canvas.Pixels[Round(y / sD), Round(x / sD)] := clBlack; //отображение на форме точек с координатами предыдущего/текущего значения требуемой разрядности из последовательности

y := x;;;; TForm1.bMonotClick(Sender: TObject); {процедура тестирования равномерности распределения символов в исследуемой последовательности на основании участков неубывания и невозрастания}

var i, j, x1, x2, k, m, l: integer; a: string; up1, up2: boolean;:= strtoint(sType.text);.Show;.Series1.Clear;1 := true; //флаги характера неубывания/невозрастания исследуемой последовательности

up2 := true;

l := 1; //начальное значение счетчика количества изменения характера последовательности

k := 0; //задание счетчика неубывания

m := 0; //задание счетчика невозрастания

x2 := 0; //предыдущее число последовательности для сравнения

for i := 0 to mmo1.Lines.Count - 1 do //цикл исследования по всем сформированным ключевым последовательностям

begin

a := mmo1.Lines[i]; //считывание из ключевой последовательности построчно

j := 1; //счетчик перемещения по последовательности

while j < length(a) do //цикл считывания значений требуемой разрядности из ключевой последовательности

begin

x1 := strtoint(copy(a, j, gType)); //копируем из последовательности число согласно разрядности

j := j + gType;

if x1 > x2 then //проверка неубывания/невозрастания предыдущего/текущего значения требуемой разрядности из последовательности

begin(k); //счетчик неубывания:= true;elsex1 < x2 then

inc(m); //счетчик невозрастания

up1 := false;

end else(k);(m);

end;

if up1 <> up2 then //вывод на форму гистограммы, отображающей последовательно периоды неубывания/невозрастания при смене характера

beginnot up1 then4.Series1.SeriesColor := clRed; //невозрастание отображаем красным цветом

Form4.Series1.AddXY(l, k, '', clRed); := 0; //сброс счетчиков неубывания/невозрастания

m := 1;

end else.Series1.SeriesColor := clBlack; //невозрастание отображаем черным цветом.Series1.AddXY(l, m, '', clBlack); := 0; //сброс счетчиков неубывания/невозрастания

k := 1;

end;

inc(l); //счетчик количества изменения характера последовательности

end;:= up1;:= x1;;;

end;

procedure TForm1.bSeriesClick(Sender: TObject); {процедура тестирования равномерности распределения символов в исследуемой последовательности на основании появления серий единиц и нулей}

var i, j, x, e, k, m, l, s2, dType: integer; a, D: string; aD: TstringList;:= strtoint(sType.text); := TStringList.Create; //переменная для хранения кодированной последовательности

aD.Add(''); //формирование начального значения переменной для хранения кодированной последовательности

Form5.Show;.Series1.Clear;2 := 0;

for i := 1 to gType do s2 := s2 * 10 + 9; //нахождение максимального значения "max" по заданной разрядности

for i := 0 to s2 do b[i] := 0; //обнуление массива-счетчика повторений

dType := 13; //разрядность чисел кодированной последовательности, рассчитывается по заданной пользователем разрядности исходной ключевой последовательности

if gType = 3 then dType := 9 elsegType = 2 then dType := 6 elsegType = 1 then dType := 3 elsegType = 5 then dType := 16 elsegType = 6 then dType := 19;:= 1; := 0;

for i := 0 to mmo1.Lines.Count - 1 do //цикл исследования по всем сформированным ключевым последовательностям

begin

a := mmo1.Lines[i]; //считывание из ключевой последовательности построчно

j := 1;

while j <= length(a) do //цикл считывания значений требуемой разрядности из ключевой последовательности

begin

x := strtoint(copy(a, j, gType)); //копируем из последовательности число согласно разрядности

j := j + gType;:= ''; x >= 2 do //перевод из десятеричной системы исчисления в двоичную

begin:= x mod 2;:= x div 2;:= IntToStr(e) + D;; := IntToStr(x) + D; //кодированное двоичное значение

for k := length(D) to dType do D := '0' + D; //восстановление требуемой разрядности для вычисленного двоичного значения

if m <= 9 then //запись в переменную по 9 чисел требуемой разрядности в строке

begin

aD.Strings[l] := aD.Strings[l] + D; //добавление значения в текущую строку

inc(m);

end else

begin

aD.Add(D); //начало записи в новую строку

m := 2; //сброс счетчика значений в строке

inc(l); //счетчик строк

end;

end;

end;

for k := 0 to aD.Count - 1 do //цикл исследования по всем кодированным двоичным последовательностям

for i := 1 to length(aD.Strings[k]) do //считывание из ключевой последовательности построчно

begin(b[strtoint(aD.Strings[k][i])]); //подсчет количества "0" и "1" (i mod 2) = 0 then //подсчет количества требуемых сочетаний "0" и "1"

begincopy(aD.Strings[k], i-1, 2) = '00' then inc(b[2]);copy(aD.Strings[k], i-1, 2) = '01' then inc(b[3]);copy(aD.Strings[k], i-1, 2) = '10' then inc(b[4]);copy(aD.Strings[k], i-1, 2) = '11' then inc(b[5]);;

if (i mod 3) = 0 then //подсчет количества требуемых сочетаний "0" и "1"

begincopy(aD.Strings[k], i-2, 3) = '000' then inc(b[6]);copy(aD.Strings[k], i-2, 3) = '001' then inc(b[7]);copy(aD.Strings[k], i-2, 3) = '010' then inc(b[8]);copy(aD.Strings[k], i-2, 3) = '011' then inc(b[9]);copy(aD.Strings[k], i-2, 3) = '100' then inc(b[10]);copy(aD.Strings[k], i-2, 3) = '101' then inc(b[11]);copy(aD.Strings[k], i-2, 3) = '110' then inc(b[12]);copy(aD.Strings[k], i-2, 3) = '111' then inc(b[13]);;

end;

{вывод на форму гистограммы с посчитанным значением количества искомых комбинаций "0" и "1"}

Form5.Series1.AddXY(0, b[0], '"0"');.Series1.AddXY(1, b[1], '"1"');.Series1.AddXY(2, b[2], '"00"');.Series1.AddXY(3, b[3], '"01"');.Series1.AddXY(4, b[4], '"10"');.Series1.AddXY(5, b[5], '"11"');.Series1.AddXY(6, b[6], '"000"');.Series1.AddXY(7, b[7], '"001"');.Series1.AddXY(8, b[8], '"010"');.Series1.AddXY(9, b[9], '"011"');.Series1.AddXY(10, b[10], '"100"');.Series1.AddXY(11, b[11], '"101"');.Series1.AddXY(12, b[12], '"110"');.Series1.AddXY(13, b[13], '"111"');;

procedure TForm1.bKnytClick(Sender: TObject); {процедура тестирования статистических свойств исследуемой последовательности, автор Д. Кнут}

var, j, x, e, k, m, l, u, s2, dType: integer;, Dv: string; aD: TstringList;, Km: real;: array [0..9] of integer;: array [1..6] of integer;: array [1..6] of real;: TTwoDimArray; //переменная для вычисления числа Стерлинга

begin:= strtoint(sType.text); mmo1.Lines.Strings[0] = '' then Fill; //контроль генерации ключевой последовательности

Form6.Show;.mmo1.Clear; := TStringList.Create; //переменная для хранения кодированной последовательности

aD.Add(''); //формирование начального значения переменной для хранения кодированной последовательности

for i := 1 to 6 do d[i] := 0;i := 1 to 6 do p[i] := 0;2 := 0;

for i := 1 to gType do s2 := s2 * 10 + 9; //нахождение максимального значения "max" по заданной разрядности

for i := 0 to s2 do b[i] := 0; //обнуление массива-счетчика повторений

dType := 13; //разрядность чисел кодированной последовательности, рассчитывается по заданной пользователем разрядности исходной ключевой последовательности

if gType = 3 then dType := 9 else //разрядность чисел кодированной последовательности, рассчитывается по заданной пользователем разрядности исходной ключевой последовательности

if gType = 2 then dType := 6 elsegType = 1 then dType := 3 elsegType = 5 then dType := 16 elsegType = 6 then dType := 19; := 1;

l := 0;

for i := 0 to mmo1.Lines.Count - 1 do //цикл исследования по всем сформированным ключевым последовательностям

begin

a := mmo1.Lines[i]; //считывание из ключевой последовательности построчно

j := 1;

while j <= length(a) do //цикл считывания значений требуемой разрядности из ключевой последовательности

begin

x := strtoint(copy(a, j, gType)); //копируем из последовательности число согласно разрядности

u := 0;

for k := 0 to 9 do c[k] := 0; //обнуление массива подсчета повторения чисел

for k := 0 to gType - 1 do //подсчет количества неповторяющихся значений в числе

inc(c[strtoint(a[j + k])]); k := 0 to 9 do //подсчет количества по неповторяющимся числам

if c[k] <> 0 then inc(u);(d[u]); //вычисление массива числа подпоследовательностей, содержащих различные числа

j := j + gType;:= ''; x >= 2 do //перевод из десятеричной системы исчисления в двоичную

begin:= x mod 2;:= x div 2;:= IntToStr(e) + Dv;; := IntToStr(x) + Dv; //кодированное двоичное значение

for k := length(Dv) to dType do Dv := '0' + Dv; //восстановление требуемой разрядности для вычисленного двоичного значения

if m <= 9 then //запись в переменную по 9 чисел требуемой разрядности в строке

begin

aD.Strings[l] := aD.Strings[l] + Dv; //добавление значения в текущую строку

inc(m);

end else

begin

aD.Add(Dv); //начало записи в новую строку

m := 2; //сброс счетчика значений в строке

inc(l); //счетчик строк

end;

end;

end;

for k := 0 to aD.Count - 1 do //цикл исследования по всем кодированным двоичным последовательностям

for i := 1 to length(aD.Strings[k]) do //считывание из ключевой последовательности построчно

begin(b[strtoint(aD.Strings[k][i])]); //подсчет количества "0" и "1" (i mod 2) = 0 then //подсчет количества требуемых сочетаний "0" и "1"

begincopy(aD.Strings[k], i-1, 2) = '00' then inc(b[2]);copy(aD.Strings[k], i-1, 2) = '01' then inc(b[3]);copy(aD.Strings[k], i-1, 2) = '10' then inc(b[4]);copy(aD.Strings[k], i-1, 2) = '11' then inc(b[5]);;

if (i mod 3) = 0 then //подсчет количества требуемых сочетаний "0" и "1"

begincopy(aD.Strings[k], i-2, 3) = '000' then inc(b[6]);copy(aD.Strings[k], i-2, 3) = '001' then inc(b[7]);copy(aD.Strings[k], i-2, 3) = '010' then inc(b[8]);copy(aD.Strings[k], i-2, 3) = '011' then inc(b[9]);copy(aD.Strings[k], i-2, 3) = '100' then inc(b[10]);copy(aD.Strings[k], i-2, 3) = '101' then inc(b[11]);copy(aD.Strings[k], i-2, 3) = '110' then inc(b[12]);copy(aD.Strings[k], i-2, 3) = '111' then inc(b[13]);;;.mmo1.Lines.Add('Тест Проверка несцепленных серий'); := 0;

for i := 0 to 1 do //подсчет распределения хи-квадрат для серий из 1 цифры

kn := kn + (b[i] - (length(ad.Strings[0]) * aD.Count / 2)) * (b[i]-(length(ad.Strings[0]) * aD.Count / 2));:= kn / (length(ad.Strings[0]) * aD.Count / 2);6.Mmo1.Lines.Add('для серии длиной 1 - ' + floattostr(roundto(kn,-2))); //вывод на форму подсчитанного значения

kn := 0;

for i := 2 to 5 do //подсчет распределения хи-квадрат для серий из 2 цифр

kn := kn + (b[i] - (length(ad.Strings[0]) * aD.Count / 8)) * (b[i] - (length(ad.Strings[0]) * aD.Count / 8));:= kn / (length(ad.Strings[0]) * aD.Count / 8);6.Mmo1.Lines.Add('для серии длиной 2 - ' + floattostr(roundto(kn,-2))); //вывод на форму подсчитанного значения

kn := 0;

for i := 6 to 13 do //подсчет распределения хи-квадрат для серий из 3 цифр

kn := kn + (b[i] - (length(ad.Strings[0]) * aD.Count / 24)) * (b[i] - (length(ad.Strings[0]) * aD.Count / 24));:= kn / (length(ad.Strings[0]) * aD.Count / 24);6.Mmo1.Lines.Add('для серии длиной 3 - ' + floattostr(roundto(kn,-2))); //вывод на форму подсчитанного значения

Form6.mmo1.Lines.Add('анализируется при помощи критерия хи-квадрат с числом степеней свободы, равным ' + floattostr(power(2, gType) - 1));

GetStirlingNumbers(gType,gType,St); //получение таблицы чисел Стирлинга

p[1] := 7; //вычисление множителя pi для нахождения распределения хи-квадрат

for i := 2 to gType do[i] := p[i-1] * (7-i+1);i := 1 to gType do[i] := p[i] * St[gType, i] / power(7, gType); := 0;

for i := 1 to gType do //подсчет распределения хи-квадрат

if d[i] <> 0 then:= Km + (d[i] - length(mmo1.Lines.Strings[0]) * mmo1.Lines.Count * p[i]/ gType) * (d[i] - length(mmo1.Lines.Strings[0]) * mmo1.Lines.Count * p[i]/ gType) / (length(mmo1.Lines.Strings[0]) * mmo1.Lines.Count * p[i]/ gType);6.mmo1.Lines.Add('Тест Проверка комбинаций');

Form6.mmo1.Lines.Add('распределение хи-квадрат = ' + floattostr(roundto(Km,-2))); //вывод на форму подсчитанного значения

Form6.mmo1.Lines.Add('анализируется при помощи критерия хи-квадрат с числом степеней свободы, равным ' + inttostr(gType-1));

end;

procedure TForm1.GetStirlingNumbers(n_max, m_max: Integer; var StirlingNumbers: TTwoDimArray); {вычисление таблицы значений Стирлинга}

var i, j: integer;

begin

SetLength(StirlingNumbers, n_max+1, m_max+1); //Выделение памяти под массив чисел

for i := 0 to n_max do //Заполнение массива S(n,0) = 0[i, 0] := 0;i := 0 to n_max do //Заполнение массива S(n,n) = 1[i, i] := 1;i := 1 to n_max do //Заполнение массива S(n,m) = S(n-1,m-1) + m*S(n-1,m)j := 1 to i-1 do[i, j] := StirlingNumbers[i-1, j-1] + j * StirlingNumbers[i-1, j];;;.