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

Лабораторная работа №1

Тема: «Принципы построения и свойства генераторов псевдослучайных последовательностей»

 

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

 

Задание к работе:

1. Написать программу для генератора псевдослучайной последовательности и сгенерировать последовательность равную периоду генератора. Записать полученную последовательность в файл.

Генератор «стоп-пошел» Beth-Piper

Используемые  LFSR (32,7,5,3,2,1,0), (12,6,4,1,0), (28,3,0)

2. Написать программу для тестирования заданного   генератора по пяти основным тестам.

 

 

 

 

 

Ход работы:

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

using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Linq;

using System.Text;

using System.Windows.Forms;

using System.IO;

 

namespace LR1__LFSR

{

    public partial class Form1 : Form

    {

        private static UInt32 LFSR1, LFSR2, LFSR3;

 

        public Form1()

        {

            InitializeComponent();

        }

 

        private UInt32 RandomizeLFSR (int size)

        {

            UInt32 LFSR = 0;

            Random rand = new Random();

            for (int i = 0; i < size; i++)

                LFSR |= (uint)(rand.Next(2)<<i);

            return LFSR;

        }

 

        private UInt32 LFSR_1()

        {

            LFSR1 = ((((LFSR1 >> 31) ^ (LFSR1 >> 6) ^ (LFSR1 >> 4) ^ (LFSR1 >> 2) ^ (LFSR1 >> 1) ^ LFSR1) & 1) << 31) | (LFSR1 >> 1);

            return LFSR1 &1;

        }

 

        private UInt32 LFSR_2()

        {

            LFSR2 = ((((LFSR2 >> 11) ^ (LFSR1 >> 5) ^ (LFSR1 >> 3) ^ LFSR1) & 1) << 11) | (LFSR1 >> 1);

            return LFSR2 &1;

        }

        private UInt32 LFSR_3()

        {

            LFSR3 = ((((LFSR3 >> 27) ^ (LFSR1 >> 2) ) & 1) << 27) | (LFSR1 >> 1);

            return LFSR3 &1;

        }

        private void button1_Click(object sender, EventArgs e)

        {

            SaveFileDialog dialog = new SaveFileDialog();

            dialog.Filter = "Файл со случайными велечинами: (*.txt)|*txt";

            if (dialog.ShowDialog() == DialogResult.OK)

            {

                textBox1.Text = dialog.FileName + ".txt";

                button2.Enabled = true;

            }        }

        private void button2_Click(object sender, EventArgs e)

        {

            richTextBox1.Clear();

           

            StreamWriter stream = new StreamWriter(textBox1.Text);

            LFSR1 = RandomizeLFSR(32);

            LFSR2 = RandomizeLFSR(12);

            LFSR3 = RandomizeLFSR(28);

            UInt32 Lmin = LFSR2;

            UInt32 Resultat = 0;

           

            for (int i = 1; i < (int)numericUpDown1.Value; i++)

            {

 

                if ((1 & LFSR1) == 1)

                {

                    Resultat = (LFSR2 ^ LFSR3)&1;

                    Lmin = LFSR2;

                    stream.Write(Resultat.ToString());

                   

                }

                else

                {

                    Resultat = (Lmin ^ LFSR3)&1;

                 

                    stream.Write(Resultat.ToString());

                }

                LFSR_1();

                LFSR_2();

                LFSR_3();

            }

            stream.Close();

            MessageBox.Show("файл создан", "cообщение");

        }

 

    }

}

 

 

Разработаем тестовую программу

using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Linq;

using System.Text;

using System.Windows.Forms;

using System.IO;

 

namespace LR1_test

{

    public partial class Form1 : Form

    {

        private static string text;

       

        public Form1()

        {

            InitializeComponent();

        }

 

        private void Form1_Load(object sender, EventArgs e)

        {

 

        }

 

        private void button1_Click(object sender, EventArgs e)

        {

            OpenFileDialog dial = new OpenFileDialog();

            if (dial.ShowDialog() != DialogResult.OK)

                return;

            StreamReader reader = new StreamReader(dial.FileName);

            text = reader.ReadToEnd();

            reader.Close();

            richTextBox1.Clear();

            richTextBox1.Text += "Частотный тест: " + TestChastotnii() + "\n";

            richTextBox1.Text += "Тест на серии: " + TestNaSerii() + "\n";

            richTextBox1.Text += "Обобщенный тест: " + TestObshii() + "\n";

            richTextBox1.Text += "Тест на последовательность: " + TestNaPosled() + "\n";

            richTextBox1.Text += "Автокорреляционный тест: " +TestAvtokor(8) + "\n";

 

        }

 

        private double TestChastotnii()

        {

            int n0 = 0, n1 = 0, n = text.Length;

            for (int i = 0; i < n; i++)

                if (text[i] == '1') n1++;

                else if (text[i] == '0') n0++;

            return Math.Abs((double)Math.Pow(n0 - n1, 2) / n);

                   

        }

 

        private double TestNaSerii()

        {

            int n = text.Length, n1 = 0, n0 = 0, n00 = 0, n01 = 0, n10 = 0, n11 = 0;

            for (int i = 0; i < n; i++)

                if (text[i] == '1') n1++;

                else if (text[i] == '0') n0++;

            for (int i = 0; i < n - 1; i++)

            {

                if ((text[i] == '0') && (text[i + 1] == '0')) n00++;

                if ((text[i] == '0') && (text[i + 1] == '1')) n01++;

                if ((text[i] == '1') && (text[i + 1] == '0')) n10++;

                if ((text[i] == '1') && (text[i + 1] == '1')) n01++;

 

            }

            return Math.Abs((4.0 / (n - 1)) * (n00 * n00 + n01 * n01 + n10 * n10 + n11 * n11) - ((2.0 / n) * (n0 * n0 + n1 * n1)) + 1);

 

        }

        private double TestObshii()

        {

            const int m = 3;

            int n = text.Length, k = n / m, Sum = 0;

            int len = (int)Math.Pow(2, m);

            int[] N = new int[len];

            for (int i = 0; i < len; N[i++] = 0) ;

            for (int i = 0; i < k - 2; i++)

            {

                if ((text[i] == '0') && (text[i + 1] == '0') && (text[i + 2] == '0')) N[0]++;

                if ((text[i] == '0') && (text[i + 1] == '0') && (text[i + 2] == '1')) N[1]++;

                if ((text[i] == '0') && (text[i + 1] == '1') && (text[i + 2] == '0')) N[2]++;

                if ((text[i] == '0') && (text[i + 1] == '1') && (text[i + 2] == '1')) N[3]++;

                if ((text[i] == '1') && (text[i + 1] == '0') && (text[i + 2] == '0')) N[4]++;

                if ((text[i] == '1') && (text[i + 1] == '0') && (text[i + 2] == '1')) N[5]++;

                if ((text[i] == '1') && (text[i + 1] == '1') && (text[i + 2] == '0')) N[6]++;

                if ((text[i] == '1') && (text[i + 1] == '1') && (text[i + 2] == '1')) N[7]++;

 

 

            }

            for (int i = 0; i < len; Sum += (int)Math.Pow(N[i++], 2)) ;

            return Math.Abs((Math.Pow(2, m) / k) * Sum - k);

        }

 

        private double TestNaPosled()

        {

            const int k = 3;

            int n = text.Length;

            double[] e = new double[k];

            int[] B = new int[k];

            int[] G = new int[k];

            for (int i = 1; i <= k; B[i - 1] = G[i - 1] = 0, i++)

                e[i - 1] = (n - i + 3) / Math.Pow(2, (i + 2));

            for (int i = 0; i < n - 4; i++)

            {

                if ((text[i] == '1') && (text[i + 1] == '0') && (text[i + 2] == '1')) B[0]++;

                if ((text[i] == '0') && (text[i + 1] == '1') && (text[i + 2] == '0')) G[0]++;

                if ((text[i] == '1') && (text[i + 1] == '0') && (text[i+2]=='0') && (text[i+3]=='1')) B[1]++;

                if ((text[i] == '0') && (text[i + 1] == '1') && (text[i + 2] == '1') && (text[i + 3] == '0')) G[1]++;

                if ((text[i] == '1') && (text[i + 1] == '0') && (text[i + 2] == '0') && (text[i + 3] == '0')&& (text[i+4]=='1')) B[2]++;

                if ((text[i] == '0') && (text[i + 1] == '1') && (text[i + 2] == '1') && (text[i + 3] == '1')&& (text[i+4]=='0')) G[2]++;

 

 

 

            }

            double tmp1 = 0.0, tmp2 = 0.0;

            for (int i = 0; i < k; i++)

            {

            tmp1+=(Math.Pow((B[i]-e[i]),2))/e[i];

            tmp2+=(Math.Pow((G[i]-e[i]),2))/e[i];

            }

            return Math.Abs(tmp1+tmp2);

        }

 

        private double TestAvtokor(int d)

        {

            int n = text.Length, A = 0;

            if (d > (n / 2) | d < 1)

                return 0.0;

            for (int i = 0; i < n - d; A += (text[i] ^ text[i + d]), i++) ;

            return Math.Abs(2 * (A - ((n - d) / 2)) / Math.Sqrt(n - d));

 

        }

    }

}

 

В результате выполнения первой программы  получим последовательность в 100 бит:

000010001000010000100100010000101001000101001001010010000100010101000001001001010010010000010000001

Получим результат:

1. Частотный тест: 20,4545454545455
2. Тест на серии: 21,5454545454545
3. Обобщенный тест: 23,969696969697
4. Тест на последовательность: 28,4652567756776
5. Автокорреляционный тест: 2,93519754282137

 

Для уровня значимости пороговые величины для , , , и равны 3.8415, 5.9915, 14.0671, 9.4877 и 1.96, соответственно. Как видно заданная последовательность не прошла тест.