Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Генератори псевдовипадкових послідовностей на базі регістрів зсуву з лінійним зворотнім звязком
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2013
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Алгоритмічні основи криптології
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
кафедра БІТ
Звіт
до лабораторної роботи № 5
з дисципліни "Алгоритмічні основи криптології"
по темі : "Генератори псевдовипадкових послідовностей на базі регістрів зсуву з лінійним зворотнім звязком"
Варіант 1
Львів – 2013
Мета роботи - вивчити основні методи реалізації генераторів псевдовипадкових послідовностей та ознайомитись з методами аналізу з використанням статистичних тестів та навчитися розробляти програмне забеспечення для реалізації перерахованих алгоритмів на компютері.
1. ЗАВДАННЯ
1) Ввести в комп'ютер програми згідно з отриманим завданням.
2) Відлагодити програми. При необхідності скоригувати блок-схеми алгоритмів та програми у відповідності з виявленими логічними та синтаксичними помилками.
3) Остаточні версії блок-схем, програм та отримані результати занести у звіт з лабораторної роботи.
№ варіанту
Функція зворотного звязку
Тип регістру
Тести
1
(8, 4, 3, 2, 0)
Фібоначчі
Частотний і послідовний
3. Список ідентифікаторів констант, змінних, процедур і функцій, використаних у блок-схемах алгоритмів і програм, та їх пояснення
Main() - головна фунція
Console.ReadLine() - функція зчитує з клавіатури текст
Console.Write() - функція виводить на екран текст
Console.WriteLine() - функція виводить на екран тексторий ряд
Array.Copy() - функція копіює значення елементів з одного масиву в інший
SizeOfMatrix() - функція у котрій вводимо кількість розрядів
Generator() - конструктор оголошує змінні для роботи генератора
ChosePolinoms() - функція у котрій вибираємо тип поліномів
OneDiagonals() - функція, котра створює матрицю в котрій перший рядок - поліном, решта рядків заповнені по діагоналі 1
ShowMatrix() - функція виводить на екран матрицю
SetDegree() - функція у котрій вводимо степінь матриці
MatrixToDegree() - функція підносить матрицю до вказаного степеня
Generation() - функція котра реалізує процес генерації псевдовипадкових чисел
Eq() - функція перевіряє чи обидва масиви рівні
ShowResult() - функція виводить результат, на даному такті двійкову послідовність, переводить її в 10-ву, і виводить
ForCoordinates() - функція заповнює файл координатами для графічного тесту
Testin() - конструктор керує виконанням статистичних тестів
Testing1() - функція, частотний тест
Testing2() - функція, частотний тест в підпослідовностях
Testing3() - функція, тест дирок
bsize - змінна цілого типу, кількість розрядів
fv - об'єкт, з доступом до класу Generator
polynomsType - змінна цілого типу, тип поліномів
m_step - змінна цілого типу, степінь матриці
m_size - змінна цілого типу, розмір матриці
a - двовимірний масив цілого типу, початкова матриця
b - двовимірний масив цілого типу, копія а
generator - двовимірний масив цілого типу, піднесена до степеня кінцева матриця
ran - одновимірний масив цілого типу, 2-ва послідовність псевдовипадкове число
gen - одновимірний масив цілого типу, копія ran
test - одновимірний масив цілого типу, частина послідовності для тестування
i_test - змінна цілого типу, індекс test
coor - масив дійсного типу, координати для виконання графічного тесту
icoor - змінна цілого типу, індекс coor
per - масив цілого типу, для перевірки періодичності
f_ind_per - змінна цілого типу, перше зафіксоване повторювання
ok_per - змінна логічного типу, індикатор періодичності
l_ind_per - змінна цілого типу, останній зафіксоване повторювання
sw - об'єкт, файл 2-вої послідовності п/в чисел
coord - об'єкт, файл з координатами для графічного тесту
t - об'єкт, файл з інформацією про періодичність
polyn - текстовий рядок, інформацію про поліном
matr_r - текстовий рядок, інформація про степінь матриці
4. Текст програми
Generator.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
class Generator
{
byte polynomsType;
byte m_step;
byte m_size;
// For Matrix
int[,] a;
int[,] b;
int[,] generator;
// For Generation
int[] ran;
int[] gen;
// For Test
public int[] test;
int i_test;
// For Coordinat x y
double[] coor;
int icoor;
// For Check period
int[] per;
int f_ind_per;
bool ok_per = false;
int l_ind_per;
// Files
static public StreamWriter sw;
static public StreamWriter coord;
static public StreamWriter t;
//For File Names
public string polyn = String.Empty;
public string matr_r = "_r";
public Generator(byte size)
{
a = new int[size, size];
b = new int[size, size];
generator = new int[size, size];
ran = new int[size];
gen = new int[size];
per = new int[size];
//For test
test = new int[size * 1000];
i_test = 0;
coor = new double[1000];
icoor = 0;
m_size = size;
ChosePolinoms();
OneDiagonals();
Console.WriteLine(" \n\t Початкова матриця : \n ");
ShowMatrix();
}
public void OneDiagonals()
{
// Нульові значення
for (int i = 0; i < m_size; i++)
for (int j = 0; j < m_size; j++)
{
if (a[i, j] == 1) break;
else if (i == j + 1) a[i, j] = 1; // По діагоналям = 1
else a[i, j] = 0;
}
}
public void ChosePolinoms()
{
Console.Write("Введiть тип полiномiв : ");
polynomsType = Convert.ToByte(Console.ReadLine());
switch (polynomsType)
{
case 1:
a[0, 44] = 1;
a[0, 3] = 1;
a[0, 2] = 1;
a[0, 0] = 1;
Console.WriteLine("x45 + x4 + x3 + x1");
polyn = "x45-x4-x3-x_";
break;
default :
break;
}
}
public void SetDegree()
{
Console.Write(" \n\t Введiть степiнь матрицi: ");
m_step = Convert.ToByte(Console.ReadLine());
matr_r += Convert.ToString(m_step);
sw = new StreamWriter(polyn + "gen" + matr_r + ".txt");
coord = new StreamWriter(polyn + "coor" + matr_r + ".txt");
t = new StreamWriter(polyn + "per" + matr_r + ".txt");
Console.WriteLine();
}
public void MatrixToDegree()
{
int sum;
if (m_step == 1)
{
Array.Copy(a, generator, a.Length);
return;
}
Array.Copy(a,b,a.Length);
for (int s = 1; s < m_step; s++)
{
for (int i = 0; i < m_size; i++)
{
for (int j = 0; j < m_size; j++)
{
sum = 0;
for (int m = 0; m < m_size; m++)
sum += b[m, j] * a[i, m];
if ((sum % 2) == 0)
sum = 0;
else
sum = 1;
generator[i, j] = sum;
}
}
Array.Copy(generator, a, generator.Length);
}
Console.WriteLine("Матриця пiднесена до " + m_step + " степеня ");
}
public void ShowMatrix()
{
for (int i = 0; i < m_size; i++)
{
for (int j = 0; j < m_size; j++)
{
Console.Write(a[i, j] + " ");
}
Console.WriteLine();
}
}
public void Generation()
{
int sum;
int T = 0;
ran[0] = 1;
for (int i = 1; i < m_size; i++)
ran[i] = 0;
Array.Copy(ran,test,ran.Length);
Array.Copy(ran, per, ran.Length);
i_test += ran.Length;
ShowResult();
for (int takt = 0; takt < 1000; takt++)
{
for (int i = 0; i < m_size; i++)
{
sum = 0;
for (int j = 0; j < m_size; j++)
{
sum += generator[i, j] * ran[j];
}
if ((sum % 2) == 0)
sum = 0;
else
sum = 1;
gen[i] = sum;
}
for (int i = 0; i < m_size; i++)
{
if (i_test >= test.Length)
{
i_test = 0;
Test.Testin(test, polyn, matr_r);
}
test[i_test] = gen[i];
i_test++;
}
Array.Copy(gen, ran, gen.Length);
ShowResult();
if (Eq(per,ran) && ok_per == false)
{
f_ind_per = takt;
ok_per = true;
}
if (Eq(per, ran))
l_ind_per = takt;
}
T = ((l_ind_per + 1) / (f_ind_per + 1));
Console.WriteLine("Полiном : {0}, степенi : {1}", polyn, matr_r);
Console.WriteLine("Перiод : [{0}, {1}] = {2}", f_ind_per, l_ind_per, T);
t.WriteLine("T[{0}, {1}] = {2}", f_ind_per, l_ind_per, T);
t.Close();
}
bool Eq(int[] a, int[] b)
{
int ab_size = a.Length;
int c = 0;
for (int ind = 0; ind < ab_size; ind++)
if (a[ind] == b[ind])
c++;
if (c == ab_size)
return true;
else return false;
}
void ShowResult()
{
double result = 0;
for (int i = 0; i < m_size; i++)
{
Console.Write(ran[i]);
sw.Write(ran[i]);
}
Console.Write(" = ");
for (int i = 0, t = m_size - 1; i < m_size; i++, t--)
{
result += (ran[i] * Math.Pow(2, t));
}
if (icoor < coor.Length)
{
coor[icoor] = result;
icoor++;
}
Console.WriteLine(result);
sw.WriteLine();
}
public void ForCoordinates()
{
for (int i = 0; i < coor.Length - 1; i++)
coord.WriteLine(coor[i] + " " + coor[i + 1]);
}
}
class Program
{
public static byte bsize;
static void SizeOfMatrix()
{
Console.WriteLine("========== Полiноми : ");
Console.WriteLine("1) x45 + x4 + x3 + x1 Для 45-розрядного генератора Галуа");
Console.Write("Введiть кiлькiсть розрядiв - ");
bsize = Convert.ToByte(Console.ReadLine());
}
static void Main()
{
SizeOfMatrix();
Generator fv = new Generator(bsize);
fv.SetDegree();
fv.MatrixToDegree();
fv.ShowMatrix();
Console.WriteLine("\n Генерацiя псевдовипадкових чисел \n");
fv.Generation();
fv.ForCoordinates();
Generator.coord.Close();
Generator.sw.Close();
Test.sTest.Close();
Console.ReadLine();
}
}
Tests.cs
using System;
using Gamma;
using System.IO;
class Test
{
/*
Testing1 Частотний (монобiтний) тест
Testing2 Частотний тест в пiдпослiдовностях
Testing3 Тест дирок
*/
static public StreamWriter sTest;
static public void Testin(int[] a, string polyn, string matr_r)
{
sTest = new StreamWriter(polyn + "test" + matr_r + ".txt");
Testing1(a);
Testing2(a);
Testing3(a);
sTest.Close();
}
// Частотний (монобiтний) тест
static void Testing1(int[] b)
{
int one = 0;
int zero = 0;
double sobs = 0;
double pvalue = 0;
int sn = 0;
for (int i = 0; i < b.Length; i++)
{
if (b[i] == 1)
one++;
else
zero++;
}
sn = one - zero;
sobs = Math.Abs(sn) / Math.Sqrt(b.Length);
pvalue = normaldistr.erfc(sobs / Math.Sqrt(2));
if (pvalue > 0.01)
{
Console.WriteLine("пройдений Частотний (монобiтний) тест p-value = {0}", pvalue);
sTest.Write("1");
}
else
{
Console.WriteLine("не пройдений Частотний (монобiтний) тест p-value = {0}", pvalue);
sTest.Write("0");
}
}
// Частотний тест в пiдпослiдовностях
static void Testing2(int[] b)
{
double one = 0;
double xobs = 0;
double pvalue;
int M = (int)(0.05*b.Length);
double N = (b.Length / M);
double[] p = new double[(int)N];
int[,] a = new int[(int)N, M];
for (int i = 0; i < N; i++)
{
one = 0;
for (int j = 0; j < M; j++)
{
a[i, j] = b[M * i + j];
if (a[i, j] == 1)
one++;
}
p[i] = one / M;
xobs += Math.Pow(p[i]-0.5,2);
}
xobs = 4 * N * xobs;
pvalue = igammaf.igamc(N/2,xobs/2);
if (pvalue > 0.01)
{
Console.WriteLine("пройдений Частотний тест в пiдпослiдовностях p-value = {0}", pvalue);
sTest.Write("1");
}
else
{
Console.WriteLine("не пройдений Частотний тест в пiдпослiдовностях p-value = {0}", pvalue);
sTest.Write("0");
}
}
// Тест дирок
static void Testing3(int[] b)
{
int one = 0;
double n = b.Length;
double p, tau;
double pvalue;
int rk = 0;
int vobs = 0;
for (int i = 0; i < b.Length; i++)
{
if (b[i] == 1)
one++;
}
p = one / n;
tau = 2 / Math.Sqrt(n);
if (Math.Abs(p - 0.5) >= tau)
{
Console.WriteLine("не пройдений Тест \"дирок\"");
sTest.Write("0");
return;
}
for (int k = 1; k < n - 1; k++)
{
if (b[k] == b[k - 1])
rk = 1;
if (b[k] == b[k + 1])
rk = 0;
vobs += rk;
}
vobs++;
pvalue = normaldistr.erfc(
Math.Abs(vobs-2*n*p*(1-p))/(2*Math.Sqrt(2*n)*p*(1-p))
);
if (pvalue > 0.01)
{
Console.WriteLine("пройдений Тест \"дирок\" p-value = {0}", pvalue);
sTest.Write("1");
}
else
{
Console.WriteLine("не пройдений Тест \"дирок\" p-value = {0}", pvalue);
sTest.Write("0");
}
}
}
5. Результати роботи програм
31.05.2014 15:05-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора