Генератори випадкових чисел

Міністерство  освіти і науки України, молоді та спорту України

Національний  університет “Львівська політехніка”

Інститут комп’ютерних наук та інформаційних технологій

Кафедра програмного  забезпечення

 

 

 

 

 

Звіт

Про виконання лабораторної роботи №1

з предмету безпека програм та даних

 

 

 

 

 

 

 

 

 

Виконала:

ст. гр. ПІ-41

Цимбалюк Т.М.

 

Прийняв:

ст. викл. каф. ПЗ

Сенів М. М.

 

 

Львів - 2012

Тема: Генератори випадкових чисел.

Мета: Запрограмувати лінійний генератор випадкових чисел.

 

Теоретичні відомості

Сучасна інформатика широко використовує випадкові числа в різних програмах – від методу Монте-Карло до криптографії. Ряд алгоритмів захисту мережі, заснованих на засобах криптографії, передбачає використання випадкових чисел. Ці застосування висувають дві вимоги до послідовності випадкових чисел: випадковість і непередбачуваність.

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

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

Генератор псевдовипадкових чисел – алгоритм, що генерує  послідовність чисел, елементи якої незалежні один від одного і підлягають заданому розподілу.

Найбільш популярним алгоритмом для генерування псевдовипадкових чисел є алгоритм, запропонований Лемером, який називається методом  лінійного порівняння. Цей алгоритм має чотири наступних параметри.

m	модуль порівняння	m > 0
a	Множник	0 ≤ a < m
c	Приріст	0 ≤ c < m
X0	початкове число	0 ≤ X0 < m

Послідовність псевдовипадкових чисел {X₀} отримують за допомогою ітерацій наступного співвідношення:

.

При цьому якщо m, a, c та X₀ є цілими, то буде отримано послідовність цілих чисел з діапазону 0 ≤ Xn < m. Вибір значень для a, c та m є дуже важливим з точки зору створення хорошого генератора псевдовипадкових чисел. Бажано, щоб m було дуже великим та простим, щоб потенційно могли генеруватись дуже довгі серії різних псевдовипадкових чисел. Загальним правилом тут є вибір значення m, близького до максимально допустимого для даного комп'ютера додатного цілого числа.

Пропонується  три критерії, за якими можна оцінити  якість будь-якого генератора псевдовипадкових чисел.

1) Функція генерації повинна бути функцією повного періоду, тобто функція повинна породити усі числа від 0 до m перед тим, як числа почнуть повторюватись.

2) Створена послідовність повинна вести себе як випадкова. Насправді ця послідовність не буде випадковою, оскільки генерується детермінованим алгоритмом, але існує багато статистичних тестів, які можна використовувати для того, щоб оцінити ступінь випадковості поведінки послідовності.

3) Функція генерації повинна ефективно реалізовуватись в рамках 32-бітної арифметики.

Перевагою алгоритму  лінійного порівняння є те, що якщо вибрати адекватні множник та модуль порівняння, то створювана послідовність  чисел виявляється статистично  невідрізнимою від послідовності  чисел, що вибираються випадково (але незворотно) з множини чисел 1, 2, …, m-1. Однак в самому алгоритмі немає нічого випадкового взагалі, крім вибору початкового значення X0. Якщо це значення вибране, інші числа послідовності визначаються ним однозначно. Це виявляється дуже важливим з точки зору криптоаналізу.

Якщо противник  знає, що використовується алгоритм лінійного  порівняння і якщо до того ж йому відомі параметри алгоритму (наприклад, a = 75, c = 0, m = 2^31-1), то, відкривши усього одно число, противник може отримати всі наступні. Але якщо навіть опонент знає тільки те, що вибрано алгоритм лінійного порівняння, знання невеликої частини послідовності вже достатньо для того, щоб визначити усі параметри алгоритму.

Завдання

 

Запрограмувати лінійний генератор випадкових чисел.

Параметри генератора такі:

1. Х0 = 37
2. M = 2^31- 3
3. C = 46368
4. A = 2^15

Код програми

 

using System;

using System.Text.RegularExpressions;

using System.Windows.Forms;

 

using System.IO;

 

namespace Gen

{

  

    public partial class Form1 : Form

    {

        public class LinGenerator

        {

            private static UInt64 _x;

            private static UInt64 _a;

            private static UInt64 _m;

            private static UInt64 _c;

 

            static LinGenerator()

            {

                _x = Convert.ToUInt64(DateTime.Now.Millisecond);

                _a = 3;

                _m = 10;

                _c = 10;

            }

 

            public static UInt64 GetNextNumber()

            {

                _x = (_a * _x + _c) % _m;

                return _x;

            }

 

            public static void SetArguments(UInt64 sX, UInt64 sA, UInt64 sC, UInt64 sM)

            {

                _x = sX;

                _m = sM;

                _a = sA;

                _c = sC;

            }           

        }

 

        public Form1()

        {

            InitializeComponent();

        }

 

        private UInt64 countM;

        private UInt64 countA;

 

        private bool CheckLabels()

        {

            const string pattern = "\\d";

 

            const string patternText2 = "(\\d)\\^(\\d)";

 

            char[] split = {'^'};

            string[] text = label5.Text.Split(split);

            if (text.Length == 2)

            {

                split[0] = '-';

                string[] textRest = text[1].Split(split);

 

                var rx = new Regex(pattern);

                if (rx.Match(label8.Text).Success && rx.Match(label9.Text).Success &&

                    (new Regex(patternText2)).Match(label6.Text).Success &&

                    ((new Regex(pattern)).Match(text[0]).Success &&

                     (new Regex(pattern)).Match(textRest[0]).Success &&

                     (new Regex(pattern)).Match(textRest[0]).Success &&

                     textRest.Length == 2))

                {

                    try

                    {

                        countM = Convert.ToUInt64(Math.Pow(Convert.ToDouble(text[0]), Convert.ToDouble(textRest[0])))

                                 - Convert.ToUInt64(textRest[1]);

                        char[] split2 = {'^'};

                        string[] a = label6.Text.Split(split2);

                        countA = Convert.ToUInt64(Math.Pow(Convert.ToDouble(a[0]), Convert.ToDouble(a[1])));

                        UInt64 temp = Convert.ToUInt64(label9.Text);

                        temp = Convert.ToUInt64(label8.Text);

                       

                      return true;

                    }

                    catch(Exception e)

                    {

                        MessageBox.Show("Введено дуже великі числа");

                        return false;

                    }

                  

                }

                else

                {

                    MessageBox.Show("Введено не коректні дані");

                    return false;

                }

            }

            else

            {

                MessageBox.Show("Введено не коректні дані");

                return false;

            }

        }

 

        private void button1_Click(object sender, EventArgs e)

        {

            if (CheckLabels() && (new Regex("\\d")).Match(textBox5.Text).Success)

            {

                richTextBox1.Clear();

                LinGenerator.SetArguments(Convert.ToUInt64(label9.Text), countA,

                                        Convert.ToUInt64(label8.Text), countM);

               

                FileStream file = new FileStream("gen.txt", FileMode.Create);

                StreamWriter stream = new StreamWriter(file);

                stream.WriteLine("Послідовність випадкових чисел:");

 

                for (UInt64 i = 0; i < Convert.ToUInt64(textBox5.Text); i++)

                {

                    UInt64 nextNumber = LinGenerator.GetNextNumber();

                    richTextBox1.Text += nextNumber.ToString() + "   ";

                    stream.Write(nextNumber.ToString() + "; ");

                }

                stream.Close();

            }

    }

 

        private void Form1_Load(object sender, EventArgs e)

        {

            label5.Text = "2^31-3";

            label6.Text = "2^15";

            label8.Text = "46368";

            label9.Text = "37";

            textBox5.Text = "";

        }

 

        private void button2_Click(object sender, EventArgs e)

        {

            System.Diagnostics.Process.Start("gen.txt");

        }

 

        private void button3_Click(object sender, EventArgs e)

        {

           

            if(CheckLabels())

            {

                LinGenerator.SetArguments(Convert.ToUInt64(label9.Text), countA,

                                        Convert.ToUInt64(label8.Text), countM);

                UInt64 startNumber = LinGenerator.GetNextNumber();

                bool finish = true;

 

                for (UInt64 i = 0; i < countM; i++)

                {

                    UInt64 nextNumber = LinGenerator.GetNextNumber();

                    if (nextNumber == startNumber)

                    {

                        MessageBox.Show("Період: " + (i + 1));

                        finish = false;

                        break;

                    }

                }

                if (finish)

                    MessageBox.Show("Період: " + countM);

            }

        }

}

Результат виконання

Рис. 1.

 

 

Висновок

    На цій лабораторній я запрограмувала лінійний генератор випадкових чисел. Розглядаючи задані параметри, можна стверджувати, що вони є оптимальними, оскільки період генерації є великим – 9042036 елементів. Отже це не дозволить зловмиснику легко встановити закономірність.