Ім'я файлу: ПК_Лаб1_КБ47_Кононцев.docx
Розширення: docx
Розмір: 93кб.
Дата: 27.11.2022
скачати

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»

ІКТА

Кафедра БІТ




З В І Т

до лабораторної роботи №1

з курсу: «Прикладна криптографія»

на тему:

«Генерація псевдовипадкових чисел»

Виконав:

ст. гр. КБ-47

Кононцев М.О.

Прийняв:

к.т.н.

Войтусік С.С.

Львів 2022

Мета роботи

Ознайомитись з методами генерації псевдовипадкових чисел за допомогою програми NIST STS.

Теоретична частина

Існує два основних типи генераторів, що використовуються для отримання випадкових послідовностей: генератори випадкових чисел та генератори псевдовипадкових чисел. Для криптографічних додатків обидва ці типи генераторів виробляють потік нулів та одиниць, який може бути розділити на підпотоки або блоки випадкових чисел.

Випадкова послідовність бітів може бути інтерпретована як результат підкидання неупередженої "чесної" монети зі сторонами, позначеними "0" і "1", причому кожне підкидання має ймовірність рівно ½ того, що буде отримано "0" або "1". Крім того, підкидання монети не залежать одне від одного: результат будь-якого попереднього підкидання монети не впливає на наступні підкидання монети. Таким чином, незміщена "чесна" монета є ідеальним генератором випадкового бітового потоку, оскільки значення "0" і "1" будуть розподілені випадковим чином (а [0,1] - рівномірно). Всі елементи послідовності генеруються незалежно один від одного, і значення наступного елемента в послідовності неможливо передбачити, незалежно від того, скільки елементів вже було вироблено.

Очевидно, що використання незміщених монет в криптографічних цілях є недоцільним. Тим не менш, гіпотетичний вихід такого ідеалізованого генератора істинної випадкової послідовності служить еталоном для оцінки генераторів випадкових і псевдовипадкових чисел.

Випадкові та псевдовипадкові числа, що генеруються для криптографічних застосувань, повинні бути непередбачуваними. У випадку ГПСЧ, якщо початкове число невідоме, наступне вихідне число в послідовності повинно бути непередбачуваним, незважаючи на будь-які знання про попередні випадкові числа в послідовності. Ця властивість відома як пряма непередбачуваність. Також не повинно бути можливим визначити початкове число, знаючи будь-які згенеровані значення (тобто, необхідна також зворотна непередбачуваність). Не повинно бути очевидним жодного зв'язку між початковим значенням та будь-яким значенням, що генерується з цього початкового значення; кожен елемент послідовності повинен виглядати як результат незалежної випадкової події, ймовірність якої дорівнює 1/2. Для забезпечення непередбачуваності в майбутньому необхідно ретельно підходити до отримання вихідних даних. Значення, отримані за допомогою ГПСЧ, є повністю передбачуваними, якщо відомі вихідні дані та алгоритм генерації. Оскільки в багатьох випадках алгоритм генерації є загальнодоступним, вихідні дані повинні зберігатися в таємниці і не повинні виводитися з псевдовипадкової послідовності, яку він генерує. Крім того, сама вихідна величина повинна бути непередбачуваною.

Хід роботи

Запустимо програму, згенерувавши 15 послідовностей на 1 280 000 бітів за допомогою методу лінійної конгруенції.



Рис. 1. Інтерфейс консольного застосунку

------------------------------------------------------------------------------

RESULTS FOR THE UNIFORMITY OF P-VALUES AND THE PROPORTION OF PASSING SEQUENCES

------------------------------------------------------------------------------

generator is

------------------------------------------------------------------------------

C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 P-VALUE PROPORTION STATISTICAL TEST

------------------------------------------------------------------------------

1 1 1 1 4 2 1 1 2 1 0.275709 15/15 Frequency

2 2 0 1 1 3 1 2 2 1 0.437274 15/15 BlockFrequency

2 0 3 2 1 2 2 1 1 1 0.437274 15/15 CumulativeSums

1 1 2 2 1 0 4 0 3 1 0.048716 15/15 CumulativeSums

2 1 1 1 2 1 0 1 2 4 0.162606 15/15 Runs

3 0 3 0 3 2 1 1 1 1 0.090936 15/15 LongestRun

0 1 2 2 1 4 1 0 2 2 0.090936 15/15 Rank

1 4 3 1 0 2 1 2 0 1 0.048716 15/15 FFT

2 1 1 1 2 1 1 3 3 0 0.275709 14/15 NonOverlappingTemplate

0 3 1 2 1 4 0 1 0 3 0.012650 15/15 NonOverlappingTemplate

1 2 1 2 3 1 1 3 0 1 0.275709 15/15 NonOverlappingTemplate

4 0 0 0 1 2 0 2 3 3 0.006196 15/15 NonOverlappingTemplate

1 0 5 2 1 3 2 0 1 0 0.002971 15/15 NonOverlappingTemplate

0 0 2 3 0 3 3 2 1 1 0.048716 15/15 NonOverlappingTemplate

2 1 2 1 0 2 2 3 1 1 0.437274 15/15 NonOverlappingTemplate

3 0 2 1 0 2 3 2 1 1 0.162606 15/15 NonOverlappingTemplate

2 0 2 2 1 2 1 3 0 2 0.275709 15/15 NonOverlappingTemplate

2 1 4 1 0 1 0 2 2 2 0.090936 15/15 NonOverlappingTemplate

2 0 1 3 3 1 3 0 1 1 0.090936 15/15 NonOverlappingTemplate

0 1 1 4 4 1 1 0 1 2 0.012650 15/15 NonOverlappingTemplate

2 2 0 2 2 1 0 3 1 2 0.275709 15/15 NonOverlappingTemplate

3 2 1 3 1 0 1 3 0 1 0.090936 15/15 NonOverlappingTemplate

1 2 6 1 1 0 0 2 1 1 0.000648 15/15 NonOverlappingTemplate

2 1 2 1 2 2 1 4 0 0 0.090936 14/15 NonOverlappingTemplate

5 1 0 2 1 0 2 3 1 0 0.002971 15/15 NonOverlappingTemplate

2 2 0 1 1 0 1 2 4 2 0.090936 15/15 NonOverlappingTemplate

1 3 1 1 1 5 1 0 1 1 0.012650 15/15 NonOverlappingTemplate

1 2 2 2 2 2 0 1 2 1 0.637119 15/15 NonOverlappingTemplate

2 3 2 0 1 0 1 4 2 0 0.025193 14/15 NonOverlappingTemplate

4 2 3 1 1 2 1 0 1 0 0.048716 15/15 NonOverlappingTemplate

2 2 2 1 1 3 2 2 0 0 0.275709 15/15 NonOverlappingTemplate

1 1 3 2 0 4 0 1 3 0 0.012650 15/15 NonOverlappingTemplate

1 4 1 2 0 2 1 2 1 1 0.162606 15/15 NonOverlappingTemplate

1 3 1 1 6 0 0 1 2 0 0.000134 15/15 NonOverlappingTemplate

3 2 1 3 1 2 3 0 0 0 0.048716 15/15 NonOverlappingTemplate

2 2 3 1 0 1 2 1 2 1 0.437274 15/15 NonOverlappingTemplate

1 2 2 0 1 1 2 2 1 3 0.437274 15/15 NonOverlappingTemplate

1 1 2 1 2 2 1 1 2 2 0.834308 14/15 NonOverlappingTemplate

0 1 5 5 1 0 1 2 0 0 0.000026 * 15/15 NonOverlappingTemplate

0 1 5 3 1 0 2 1 1 1 0.006196 15/15 NonOverlappingTemplate

1 2 0 0 0 3 6 0 2 1 0.000060 * 15/15 NonOverlappingTemplate

0 0 1 0 6 2 0 0 3 3 0.000012 * 15/15 NonOverlappingTemplate

2 1 3 1 1 1 2 2 0 2 0.437274 15/15 NonOverlappingTemplate

3 1 2 4 1 0 1 1 1 1 0.090936 15/15 NonOverlappingTemplate

1 1 0 2 2 2 2 2 1 2 0.637119 15/15 NonOverlappingTemplate

2 3 1 3 1 2 2 1 0 0 0.162606 14/15 NonOverlappingTemplate

3 0 0 0 1 2 1 3 4 1 0.012650 14/15 NonOverlappingTemplate

3 2 1 1 2 3 1 0 1 1 0.275709 14/15 NonOverlappingTemplate

2 2 0 3 0 1 4 0 0 3 0.006196 15/15 NonOverlappingTemplate

2 3 2 1 1 1 1 2 1 1 0.637119 15/15 NonOverlappingTemplate

1 2 0 0 0 2 2 4 2 2 0.048716 15/15 NonOverlappingTemplate

1 1 0 2 0 1 4 2 2 2 0.090936 15/15 NonOverlappingTemplate

3 0 1 2 1 1 2 2 1 2 0.437274 15/15 NonOverlappingTemplate

1 2 1 0 3 2 1 2 2 1 0.437274 15/15 NonOverlappingTemplate

2 2 1 3 0 2 1 1 2 1 0.437274 15/15 NonOverlappingTemplate

1 2 1 3 2 1 0 1 4 0 0.048716 15/15 NonOverlappingTemplate

0 2 2 1 4 1 4 0 1 0 0.006196 15/15 NonOverlappingTemplate

2 0 0 0 4 1 2 2 3 1 0.025193 15/15 NonOverlappingTemplate

3 1 1 1 2 1 0 2 2 2 0.437274 14/15 NonOverlappingTemplate

2 1 0 0 0 5 0 4 1 2 0.000296 15/15 NonOverlappingTemplate

2 2 4 2 2 1 0 0 1 1 0.090936 14/15 NonOverlappingTemplate

3 2 2 2 1 1 1 2 1 0 0.437274 15/15 NonOverlappingTemplate

1 4 3 0 0 1 2 1 1 2 0.048716 15/15 NonOverlappingTemplate

1 1 0 0 2 3 2 2 0 4 0.025193 15/15 NonOverlappingTemplate

1 2 0 1 2 1 2 1 1 4 0.162606 15/15 NonOverlappingTemplate

1 1 1 4 1 3 0 0 0 4 0.002971 15/15 NonOverlappingTemplate

2 0 1 1 3 1 2 1 3 1 0.275709 15/15 NonOverlappingTemplate

1 0 2 3 1 1 1 3 2 1 0.275709 14/15 NonOverlappingTemplate

1 0 1 5 0 2 1 2 2 1 0.012650 15/15 NonOverlappingTemplate

3 0 0 1 3 3 1 3 1 0 0.025193 15/15 NonOverlappingTemplate

2 3 3 2 0 0 2 0 1 2 0.090936 15/15 NonOverlappingTemplate

0 3 2 0 4 0 2 1 1 2 0.025193 15/15 NonOverlappingTemplate

3 0 2 4 1 1 1 0 0 3 0.012650 15/15 NonOverlappingTemplate

4 4 0 1 0 1 3 0 1 1 0.002971 15/15 NonOverlappingTemplate

1 0 3 3 1 3 1 1 1 1 0.162606 14/15 NonOverlappingTemplate

2 0 1 0 3 0 3 1 4 1 0.012650 15/15 NonOverlappingTemplate

0 0 2 4 0 1 3 3 1 1 0.012650 15/15 NonOverlappingTemplate

3 1 1 0 0 1 1 1 3 4 0.025193 14/15 NonOverlappingTemplate

1 0 1 1 2 2 2 1 3 2 0.437274 15/15 NonOverlappingTemplate

4 0 1 2 3 0 2 1 1 1 0.048716 13/15 NonOverlappingTemplate

1 1 0 2 0 2 2 2 2 3 0.275709 15/15 NonOverlappingTemplate

4 1 1 1 3 3 0 1 0 1 0.025193 14/15 NonOverlappingTemplate

2 1 1 1 2 1 1 3 3 0 0.275709 14/15 NonOverlappingTemplate

3 1 1 1 1 2 1 3 0 2 0.275709 15/15 NonOverlappingTemplate

0 1 1 4 3 0 1 0 1 4 0.002971 15/15 NonOverlappingTemplate

1 1 1 1 2 2 1 4 1 1 0.275709 15/15 NonOverlappingTemplate

1 2 0 2 2 1 0 4 0 3 0.025193 15/15 NonOverlappingTemplate

1 1 2 1 1 0 2 2 4 1 0.162606 15/15 NonOverlappingTemplate

0 2 1 1 2 2 3 1 2 1 0.437274 15/15 NonOverlappingTemplate

2 3 2 1 1 0 2 1 1 2 0.437274 15/15 NonOverlappingTemplate

4 1 0 1 2 2 1 2 2 0 0.090936 14/15 NonOverlappingTemplate

2 1 1 0 1 3 2 1 3 1 0.275709 15/15 NonOverlappingTemplate

3 1 1 1 1 1 4 2 1 0 0.090936 15/15 NonOverlappingTemplate

1 1 1 2 1 0 2 4 1 2 0.162606 15/15 NonOverlappingTemplate

1 0 0 0 3 1 1 4 2 3 0.012650 14/15 NonOverlappingTemplate

3 1 3 1 0 2 4 0 1 0 0.012650 15/15 NonOverlappingTemplate

0 2 3 0 1 1 3 2 1 2 0.162606 15/15 NonOverlappingTemplate

3 2 1 2 2 3 0 1 1 0 0.162606 13/15 NonOverlappingTemplate

1 1 2 2 1 2 1 0 1 4 0.162606 15/15 NonOverlappingTemplate

3 1 2 3 1 2 0 2 1 0 0.162606 15/15 NonOverlappingTemplate

2 0 0 3 2 1 1 2 1 3 0.162606 15/15 NonOverlappingTemplate

0 1 2 3 2 1 1 1 2 2 0.437274 15/15 NonOverlappingTemplate

3 0 0 1 1 2 2 3 2 1 0.162606 15/15 NonOverlappingTemplate

2 0 3 0 1 1 3 2 1 2 0.162606 15/15 NonOverlappingTemplate

2 0 1 1 3 2 3 1 1 1 0.275709 15/15 NonOverlappingTemplate

2 2 0 1 1 2 0 2 3 2 0.275709 15/15 NonOverlappingTemplate

0 0 4 2 3 2 3 1 0 0 0.006196 15/15 NonOverlappingTemplate

2 2 3 1 3 0 0 2 0 2 0.090936 15/15 NonOverlappingTemplate

2 0 2 1 0 2 2 0 3 3 0.090936 15/15 NonOverlappingTemplate

1 2 0 2 1 4 3 0 0 2 0.025193 15/15 NonOverlappingTemplate

2 2 2 2 0 2 0 1 1 3 0.275709 15/15 NonOverlappingTemplate

0 1 1 0 3 2 3 2 2 1 0.162606 15/15 NonOverlappingTemplate

0 1 2 1 1 3 2 1 2 2 0.437274 15/15 NonOverlappingTemplate

1 3 0 1 2 1 2 0 1 4 0.048716 15/15 NonOverlappingTemplate

1 2 1 1 1 1 3 1 2 2 0.637119 15/15 NonOverlappingTemplate

4 0 2 1 1 2 1 2 0 2 0.090936 14/15 NonOverlappingTemplate

0 3 0 1 0 3 1 0 6 1 0.000026 * 15/15 NonOverlappingTemplate

1 2 2 0 2 0 2 1 2 3 0.275709 15/15 NonOverlappingTemplate

2 2 1 2 0 3 0 0 2 3 0.090936 15/15 NonOverlappingTemplate

2 2 0 1 0 2 1 0 5 2 0.006196 15/15 NonOverlappingTemplate

2 2 2 2 2 0 0 5 0 0 0.002971 15/15 NonOverlappingTemplate

2 2 1 0 2 2 1 2 2 1 0.637119 15/15 NonOverlappingTemplate

3 3 2 1 0 1 1 1 1 2 0.275709 14/15 NonOverlappingTemplate

2 2 0 2 1 3 2 0 3 0 0.090936 15/15 NonOverlappingTemplate

0 2 1 4 3 3 1 0 0 1 0.012650 15/15 NonOverlappingTemplate

2 0 1 0 1 1 2 2 1 5 0.012650 14/15 NonOverlappingTemplate

3 0 0 0 2 3 1 2 3 1 0.048716 15/15 NonOverlappingTemplate

2 2 1 1 1 3 2 0 1 2 0.437274 15/15 NonOverlappingTemplate

2 3 1 0 1 2 0 4 1 1 0.048716 14/15 NonOverlappingTemplate

4 1 0 2 1 0 1 1 2 3 0.048716 15/15 NonOverlappingTemplate

3 3 0 4 0 1 1 0 2 1 0.012650 14/15 NonOverlappingTemplate

1 3 0 0 1 0 2 4 1 3 0.012650 15/15 NonOverlappingTemplate

2 2 3 0 1 1 1 1 3 1 0.275709 15/15 NonOverlappingTemplate

1 2 1 1 0 3 2 1 2 2 0.437274 15/15 NonOverlappingTemplate

1 0 2 1 2 2 3 3 1 0 0.162606 15/15 NonOverlappingTemplate

4 0 0 1 1 3 2 0 1 3 0.012650 15/15 NonOverlappingTemplate

4 2 0 3 0 3 1 0 2 0 0.006196 15/15 NonOverlappingTemplate

5 1 1 0 2 2 1 1 2 0 0.012650 14/15 NonOverlappingTemplate

1 2 2 2 2 0 2 0 3 1 0.275709 15/15 NonOverlappingTemplate

1 1 3 2 0 2 3 2 0 1 0.162606 15/15 NonOverlappingTemplate

2 1 4 1 0 1 2 2 2 0 0.090936 15/15 NonOverlappingTemplate

3 2 1 1 2 1 2 0 0 3 0.162606 13/15 NonOverlappingTemplate

3 1 1 1 2 2 2 1 0 2 0.437274 15/15 NonOverlappingTemplate

0 3 2 1 1 2 1 1 3 1 0.275709 15/15 NonOverlappingTemplate

1 3 1 4 3 0 1 1 0 1 0.025193 15/15 NonOverlappingTemplate

1 1 2 2 2 2 1 3 1 0 0.437274 15/15 NonOverlappingTemplate

2 2 2 0 1 2 1 2 0 3 0.275709 15/15 NonOverlappingTemplate

2 2 3 0 0 3 2 1 1 1 0.162606 15/15 NonOverlappingTemplate

1 2 5 0 1 2 1 0 1 2 0.012650 15/15 NonOverlappingTemplate

2 0 2 2 1 3 0 1 1 3 0.162606 15/15 NonOverlappingTemplate

2 0 1 3 2 2 1 2 1 1 0.437274 15/15 NonOverlappingTemplate

1 2 1 2 1 0 2 5 1 0 0.012650 15/15 NonOverlappingTemplate

3 0 0 2 1 3 1 2 1 2 0.162606 15/15 NonOverlappingTemplate

3 1 1 1 0 3 1 3 2 0 0.090936 15/15 NonOverlappingTemplate

2 2 1 3 2 1 1 0 2 1 0.437274 15/15 NonOverlappingTemplate

4 1 1 1 3 3 0 1 0 1 0.025193 14/15 NonOverlappingTemplate

1 3 0 2 1 2 0 2 3 1 0.162606 15/15 OverlappingTemplate

1 2 0 2 0 2 2 2 1 3 0.275709 14/15 Universal

3 2 2 1 2 0 2 0 1 2 0.275709 14/15 ApproximateEntropy

0 1 1 2 2 1 1 0 1 2 0.834308 11/11 RandomExcursions

0 3 1 3 0 0 0 1 3 0 0.048716 11/11 RandomExcursions

0 1 2 1 2 1 1 2 0 1 0.834308 11/11 RandomExcursions

1 1 1 0 0 2 2 1 3 0 0.437274 11/11 RandomExcursions

4 1 1 2 1 0 0 0 2 0 0.090936 10/11 RandomExcursions

2 1 1 0 0 2 1 0 2 2 0.637119 10/11 RandomExcursions

5 1 0 1 1 2 0 1 0 0 0.012650 10/11 RandomExcursions

3 1 1 1 1 1 1 0 2 0 0.637119 11/11 RandomExcursions

0 1 2 4 1 0 1 0 1 1 0.162606 11/11 RandomExcursionsVariant

0 2 4 2 0 0 0 2 1 0 0.048716 11/11 RandomExcursionsVariant

0 2 3 1 1 0 2 1 0 1 0.437274 11/11 RandomExcursionsVariant

0 3 2 1 1 0 2 1 0 1 0.437274 11/11 RandomExcursionsVariant

0 2 4 0 1 1 1 1 0 1 0.162606 11/11 RandomExcursionsVariant

0 4 1 0 2 0 1 3 0 0 0.025193 11/11 RandomExcursionsVariant

0 1 3 2 0 0 2 2 1 0 0.275709 11/11 RandomExcursionsVariant

0 1 0 1 4 1 2 1 1 0 0.162606 11/11 RandomExcursionsVariant

1 0 1 1 2 3 1 2 0 0 0.437274 11/11 RandomExcursionsVariant

2 2 1 0 0 3 0 3 0 0 0.090936 10/11 RandomExcursionsVariant

2 2 1 0 0 3 1 1 0 1 0.437274 10/11 RandomExcursionsVariant

3 0 0 1 2 2 2 1 0 0 0.275709 10/11 RandomExcursionsVariant

3 1 1 1 1 0 2 0 2 0 0.437274 10/11 RandomExcursionsVariant

3 1 0 3 1 1 0 2 0 0 0.162606 10/11 RandomExcursionsVariant

3 1 1 0 2 0 1 1 1 1 0.637119 10/11 RandomExcursionsVariant

1 2 1 1 1 0 0 2 3 0 0.437274 10/11 RandomExcursionsVariant

2 0 1 1 0 2 2 1 2 0 0.637119 11/11 RandomExcursionsVariant

2 0 1 2 1 1 1 0 2 1 0.834308 10/11 RandomExcursionsVariant

2 0 4 1 3 0 1 1 1 2 0.048716 15/15 Serial

3 0 0 0 1 2 3 2 3 1 0.048716 15/15 Serial

4 0 1 0 1 0 3 4 0 2 0.001399 14/15 LinearComplexity

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

The minimum pass rate for each statistical test with the exception of the

random excursion (variant) test is approximately = 13 for a

sample size = 15 binary sequences.

The minimum pass rate for the random excursion (variant) test

is approximately = 9 for a sample size = 11 binary sequences.

For further guidelines construct a probability table using the MAPLE program

provided in the addendum section of the documentation.

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Висновок

В ході даної лабораторної роботи б я ознайомився з різними методами генерації псевдовипадкових чисел. Згенерував та протестував генерацію псевдовипадкових послідовностей методом лінійної конгруенції за допомогою програми NIST STS.
скачати

© Усі права захищені
написати до нас