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

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

Модули.

unit urfsr; {Главный модуль}

unit uGistogramm; {Модуль отображения результата теста построения гистограммы}

unit uRaspredelenie; {Модуль отображения результата теста распределения на плоскости}

unit uMonotonnost; {Модуль отображения результата теста на монотонность}

unit uSeries; {Модуль отображения результата теста проверки серий}

unit uKnyt; {Модуль отображения результата теста Д. Кнута}

Процедуры.

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

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

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

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

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

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

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

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

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

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

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

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

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

Элементы меню.

procedure AboutClick(Sender: TObject); {о программе}

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

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

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

procedure 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. Окно результата работы оценочных тестов

б k	0,01	0,025	0,05	0,95	0,975	0,99
1	6,63490	5,02389	3,84146	0,00393	0,00098	0,00016
2	9,21034	7,37776	5,99146	0,10259	0,05064	0,02010
3	11,34487	9,34840	7,81473	0,35185	0,21580	0,11483
4	13,2767	11,14329	9,48773	0,71072	0,48442	0,29711
5	15,08627	12,8325	11,0705	1,14548	0,83121	0,55430
6	16,81189	14,44938	12,59159	1,63538	1,23734	0,87209
7	18,47531	16,01276	14,06714	2,16735	1,68987	1,23904
8	20,09024	17,53455	15,50731	2,73264	2,17973	1,64650
9	21,66599	19,02277	16,91898	3,32511	2,70039	2,08790
10	23,20925	20,48318	18,30704	3,94030	3,24697	2,55821
11	24,72497	21,92005	19,67514	4,57481	3,81575	3,05348
12	26,21697	23,33666	21,02607	5,22603	4,40379	3,57057
13	27,68825	24,7356	22,36203	5,89186	5,00875	4,10692
14	29,14124	26,11895	23,68479	6,57063	5,62873	4,66043
15	30,57791	27,48839	24,99579	7,26094	6,26214	5,22935

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

3. Осмоловский С.А. Стохастические методы передачи данных: учеб. пособие / С. А. Осмоловский - М.: Радио и связь, 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с.

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

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

ПРИЛОЖЕНИЕ

Текст программы «Cryptographically Strong Key Algorithm and Analysis (CSKA)».

unit urfsr; {Главный модуль}

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, ExtCtrls, TeeProcs, TeEngine, Chart, Series, Buttons,

Menus, CheckLst, ComCtrls, Spin, Math;

type

TTwoDimArray = array of array of Double;

mas = array [0..15] of integer;

mass = array [0..999999] of integer;

TForm1 = class(TForm)

About: TMenuItem; //описание элементов формы

bClear: TButton;

bClose: TButton;

bDot: TButton;

bGisto: TButton;

bKnyt: TButton;

bMonot: TButton;

bRun: TButton;

bRunN: TButton;

bSeries: TButton;

dOpen: TOpenDialog;

dSave: TSaveDialog;

Exit1: TMenuItem;

File1: TMenuItem;

Label1: TLabel;

Label2: TLabel;

Label3: TLabel;

Label4: TLabel;

Label5: TLabel;

Label6: TLabel;

Label7: TLabel;

Label8: TLabel;

mMenu: TMainMenu;

mmo1: TMemo;

Open1: TMenuItem;

Save: TMenuItem;

SaveAs: TMenuItem;

SaveKey: TMenuItem;

sConst: TSpinEdit;

sNum: TSpinEdit;

sType: TSpinEdit;

procedure AboutClick(Sender: TObject); //процедуры элементов управления с формы

procedure bClearClick(Sender: TObject);

procedure bCloseClick(Sender: TObject);

procedure bDotClick(Sender: TObject);

procedure bGistoClick(Sender: TObject);

procedure bKnytClick(Sender: TObject);

procedure bMonotClick(Sender: TObject);

procedure bRunClick(Sender: TObject);

procedure bRunNClick(Sender: TObject);

procedure bSeriesClick(Sender: TObject);

procedure Open1Click(Sender: TObject);

procedure SaveAsClick(Sender: TObject);

procedure SaveClick(Sender: TObject);

procedure SaveKeyClick(Sender: TObject);

private

{ Private declarations }

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

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

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

public

{ Public declarations }

end;

var

Form1: TForm1;

gType: integer; //параметр размерности тестируемого массива с формы

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

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

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

implementation

uses uGistogramm, uRaspredelenie, uMonotonnost, uSeries, uKnyt;

{$R *.dfm}

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

begin

outN := TStringList.Create;

Fill;

end;

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

var a: string; i, k: integer;

begin

Run;

a := '';

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

begin

for k := length(inttostr(Z[i])) to 8 do

a := a + '0';

a := a + inttostr(Z[i]);

end;

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

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

end;

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

var i, c: integer; R: mas;

begin

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;

begin

outN := TStringList.Create;

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

Fill;

end;

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

begin

Close;

end;

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

begin

with dOpen do

if Execute then

begin

mmo1.Lines.LoadFromFile(filename);

historylist.add(filename);

Caption := 'Генератор Псевдослучайных Последовательностей - ' + ExtractFileName(FileName);

dSave.filename := filename;

end;

end;

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

begin

if dOpen.FileName <> '' then

mmo1.Lines.SaveToFile(dSave.FileName)

else

SaveAsClick(Sender);

end;

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

begin

with dSave do

if execute then

begin

mmo1.Lines.SaveToFile(FileName);

Caption := 'Генератор Псевдослучайных Последовательностей - ' + ExtractFileName(FileName);

end;

end;

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

begin

with dSave do

if execute then

begin

outN.SaveToFile(FileName);

end;

end;

procedure TForm1.AboutClick(Sender: TObject); {о программе}

begin

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;

begin

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

Form2.Show;

Form2.Series1.Clear;

max := 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

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

end;

end;

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

var i, j, x, y: integer; a: string; sD: real;

begin

gType := strtoint(sType.text);

Form3.Show;

Form3.Image1.Canvas.Brush.Color := clWhite; //сбрасываем на белый фон поля для отображения

Form3.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 else

if gType = 1 then sD := 0.01 else

if gType = 5 then sD := 110.01 else

if gType = 6 then sD := 1100.1;

y := 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;

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

y := x;

end;

end;

end;

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

var i, j, x1, x2, k, m, l: integer; a: string; up1, up2: boolean;

begin

gType := strtoint(sType.text);

Form4.Show;

Form4.Series1.Clear;

up1 := 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

inc(k); //счетчик неубывания

up1 := true;

end else

if x1 < x2 then

begin

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

up1 := false;

end else

begin

inc(k);

inc(m);

end;

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

begin

if not up1 then

begin

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

Form4.Series1.AddXY(l, k, '', clRed);

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

m := 1;

end else

begin

Form4.Series1.SeriesColor := clBlack; //невозрастание отображаем черным цветом

Form4.Series1.AddXY(l, m, '', clBlack);

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

k := 1;

end;

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

end;

up2 := up1;

x2 := x1;

end;

end;

end;

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

var i, j, x, e, k, m, l, s2, dType: integer; a, D: string; aD: TstringList;

begin

gType := strtoint(sType.text);

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

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

Form5.Show;

Form5.Series1.Clear;

s2 := 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 else

if gType = 1 then dType := 3 else

if gType = 5 then dType := 16 else

if gType = 6 then dType := 19;

m := 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)); //копируем из последовательности число согласно разрядности

j := j + gType;

D := '';

while x >= 2 do //перевод из десятеричной системы исчисления в двоичную

begin

e := x mod 2;

x := x div 2;

D := IntToStr(e) + D;

end;

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

inc(b[strtoint(aD.Strings[k][i])]); //подсчет количества "0" и "1"

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

begin

if copy(aD.Strings[k], i-1, 2) = '00' then inc(b[2]);

if copy(aD.Strings[k], i-1, 2) = '01' then inc(b[3]);

if copy(aD.Strings[k], i-1, 2) = '10' then inc(b[4]);

if copy(aD.Strings[k], i-1, 2) = '11' then inc(b[5]);

end;

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

begin

if copy(aD.Strings[k], i-2, 3) = '000' then inc(b[6]);

if copy(aD.Strings[k], i-2, 3) = '001' then inc(b[7]);

if copy(aD.Strings[k], i-2, 3) = '010' then inc(b[8]);

if copy(aD.Strings[k], i-2, 3) = '011' then inc(b[9]);

if copy(aD.Strings[k], i-2, 3) = '100' then inc(b[10]);

if copy(aD.Strings[k], i-2, 3) = '101' then inc(b[11]);

if copy(aD.Strings[k], i-2, 3) = '110' then inc(b[12]);

if copy(aD.Strings[k], i-2, 3) = '111' then inc(b[13]);

end;

end;

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

Form5.Series1.AddXY(0, b[0], '"0"');

Form5.Series1.AddXY(1, b[1], '"1"');

Form5.Series1.AddXY(2, b[2], '"00"');

Form5.Series1.AddXY(3, b[3], '"01"');

Form5.Series1.AddXY(4, b[4], '"10"');

Form5.Series1.AddXY(5, b[5], '"11"');

Form5.Series1.AddXY(6, b[6], '"000"');

Form5.Series1.AddXY(7, b[7], '"001"');

Form5.Series1.AddXY(8, b[8], '"010"');

Form5.Series1.AddXY(9, b[9], '"011"');

Form5.Series1.AddXY(10, b[10], '"100"');

Form5.Series1.AddXY(11, b[11], '"101"');

Form5.Series1.AddXY(12, b[12], '"110"');

Form5.Series1.AddXY(13, b[13], '"111"');

end;

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

var

i, j, x, e, k, m, l, u, s2, dType: integer;

a, Dv: string; aD: TstringList;

kn, Km: real;

c: array [0..9] of integer;

d: array [1..6] of integer;

p: array [1..6] of real;

St: TTwoDimArray; //переменная для вычисления числа Стерлинга

begin

gType := strtoint(sType.text);

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

Form6.Show;

Form6.mmo1.Clear;

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

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

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

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

s2 := 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 else

if gType = 1 then dType := 3 else

if gType = 5 then dType := 16 else

if gType = 6 then dType := 19;

m := 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])]);

for k := 0 to 9 do //подсчет количества по неповторяющимся числам

if c[k] <> 0 then inc(u);

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

j := j + gType;

Dv := '';

while x >= 2 do //перевод из десятеричной системы исчисления в двоичную

begin

e := x mod 2;

x := x div 2;

Dv := IntToStr(e) + Dv;

end;

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

inc(b[strtoint(aD.Strings[k][i])]); //подсчет количества "0" и "1"

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

begin

if copy(aD.Strings[k], i-1, 2) = '00' then inc(b[2]);

if copy(aD.Strings[k], i-1, 2) = '01' then inc(b[3]);

if copy(aD.Strings[k], i-1, 2) = '10' then inc(b[4]);

if copy(aD.Strings[k], i-1, 2) = '11' then inc(b[5]);

end;

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

begin

if copy(aD.Strings[k], i-2, 3) = '000' then inc(b[6]);

if copy(aD.Strings[k], i-2, 3) = '001' then inc(b[7]);

if copy(aD.Strings[k], i-2, 3) = '010' then inc(b[8]);

if copy(aD.Strings[k], i-2, 3) = '011' then inc(b[9]);

if copy(aD.Strings[k], i-2, 3) = '100' then inc(b[10]);

if copy(aD.Strings[k], i-2, 3) = '101' then inc(b[11]);

if copy(aD.Strings[k], i-2, 3) = '110' then inc(b[12]);

if copy(aD.Strings[k], i-2, 3) = '111' then inc(b[13]);

end;

end;

Form6.mmo1.Lines.Add('Тест Проверка несцепленных серий');

kn := 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 := kn / (length(ad.Strings[0]) * aD.Count / 2);

Form6.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 := kn / (length(ad.Strings[0]) * aD.Count / 8);

Form6.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 := kn / (length(ad.Strings[0]) * aD.Count / 24);

Form6.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

p[i] := p[i-1] * (7-i+1);

for i := 1 to gType do

p[i] := p[i] * St[gType, i] / power(7, gType);

Km := 0;

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

if d[i] <> 0 then

Km := 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);

Form6.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

StirlingNumbers[i, 0] := 0;

for i := 0 to n_max do //Заполнение массива S(n,n) = 1

StirlingNumbers[i, i] := 1;

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

for j := 1 to i-1 do

StirlingNumbers[i, j] := StirlingNumbers[i-1, j-1] + j * StirlingNumbers[i-1, j];

end;

initialization

randomize;

end.

Размещено на Allbest.ru