Описание алгоритма хэширования



Скачать 103.19 Kb.
Дата24.04.2016
Размер103.19 Kb.
ТипОтчет
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

федеральное государственное бюджетное образовательное учреждение высшего профессионального образования



«УЛЬЯНОВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

Кафедра «Вычислительная техника»



Отчёт по лабораторной работе №1

«Хеширование паролей. Генераторы случайных чисел»

Вариант №9
Выполнил:

студент группы ИСТд-41

Корнеев А.В.

Проверил:

доцент каф. «Вычислительная техника»

к.т.н. Мартынов А.И.
Ульяновск

2012 г.
Задание на лабораторную работу



  1. Изучить алгоритмы хеширования паролей;

  2. Изучить известные алгоритмы работы генераторов случайных чисел;

  3. Реализовать свой упрощенный вариант алгоритма хеширования пароля согласно варианту;

  4. Реализовать свой алгоритм генератора случайных чисел согласно варианту;

  5. Проанализировать выходную последовательность, выдаваемую генератором при различных параметрах.



Описание алгоритма хэширования

Линейный конгруэнтный генератор псевдо случайных чисел.


Генератор использует следующую рекуррентную последовательность

Число a называется мультипликатором, число c инкрементом, а число m - модулем.

Инициализация генератора осуществляется тройкой чисел, которая устанавливает начальные значения и параметры генерации. Известно, что генерируемая последовательность будет иметь больший период, если выполняются два условия:


  1. A mod 4 = 1

  2. C - нечетное



Хэширование с использование линейного конгруэнтного генератора


Предложенный в лабораторной метод инициализации генератора был несколько модифицирован следующим образом:

  1. В качестве начального значения берется не длина пароля, а ое число Каталана, где , а – длина пароля. Соответственно, число Каталана вычисляется по формуле , где – биноминальный коэффициент или число сочетаний из по .

  2. Мультипликатор вычисляется по формуле , если полученное значение мало, оно дополняется одним из чисел Каталана. Требуется выполнение условия .

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

Описанный генератор возвращает случайное число из диапазона 0-4294967296, иначе говоря – 32 случайных бита. Сгенерируем последовательность из 10 чисел. Но, всю последовательность чисел легко восстановить, зная лишь 3 смежных числа. Поэтому генерируемый хэш будет вида , где – шестнадцатеричное представление ого числа полученной последовательности.

Таким образом, мы имеет отражения множества паролей (произвольной длины) в множество шестнадцатеричных чисел. Отразим это следующей функциональной зависимостью , где - образ исходного пароля в множестве . Заметим, что указанные преобразования являются однозначными, но не обратимыми, иначе: не существует обратного оператора . Исходное множество бесконечно. Множество хэшей конечно и его мощность равна , что достаточно велико. При незначительном изменении пароля (замены одного символа на смежный, перестановка двух соседних символов, изменения регистра одной буквы) описанный метод дает значительно различающиеся символы. Иначе говоря, при небольшом расстояние между их образами в множестве будет значительно.

Анализ выдаваемой последовательности осуществляется непосредственно в приложении: расчёт статистических показателей (математическое ожидание, дисперсия, среднеквадратичное отклонение) для разных длин последовательностей и построение графика распределения случайных чисел.

Описание исходного кода программы


Есть интерфейс IRandomGenerator, который описывает базовые методы для генератора псевдослучайных чисел.

interface IRandomGenerator

{

uint Next();



}

Класс LinearCongruentialGenerator реализует указанный интерфейс и хранит состояние генератора, которое однозначно определяется вектором из 4 элементов . Помимо этого класс также содержит сведения о стандартных параметрах, используемых в языке C для генерации последовательности псевдослучайных чисел.



public class LinearCongruentialGenerator : IRandomGenerator

{

public const uint DEFAULT_A = 1664525;



public const uint DEFAULT_C = 1013904223;

public const uint DEFAULT_M = uint.MaxValue;

private uint current = 1;
public uint A { get; set; }

public uint C { get; set; }

public uint M { get; set; }

public uint Current { set { current = value; } }


public uint Next()

{

return current = (A * current + C) % M;



}

}
Подобный подход на разделение интерфейса и реализации используется и для хэш-функции.

interface IHashFunction

{

string getHash(string str);



}

class SimpleHash : IHashFuction

{

public const uint SEQUENCE_SIZE = 10;



public IRandomGenerator Random { set; private get; }
public string getHash(string str)

{

initialGenerator(str);



string result = "";

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

{

var randomValue = Random.Next();



string next = randomValue.ToString("X");

if ((i & 1) == 0) {

result += next;

}

else {



result = next + result;

}

}



return result;

}
private void initialGenerator(string str)

{

var rnd = Random as LinearCongruentialGenerator;



if (rnd == null) return;

rnd.A = Utils.getMultipleParam(str);

rnd.Current = Utils.getStartValue(str.Length);

rnd.C = Utils.getAddictiveParam(str);

rnd.M = LinearCongruentialGenerator.DEFAULT_M;

}

}



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

Статический класс Utils содержит реализацию вспомогательных математических функций, используемых для инициализации генератора. Алгоритмы были подробно рассмотрены выше, поэтому приведем лишь исходный код этого класса.

static class Utils

{

public const int MAX_PASSWORD_LENGTH = 20;



private static uint[] fact = new uint[MAX_PASSWORD_LENGTH + 1];
static Utils()

{

fact[0] = 1;



for (uint i = 1; i < fact.Length; ++i)

{

fact[i] = i * fact[i - 1];



}

}
public static uint getAddictiveParam(string str)

{

int countVowels = 0;



int countConsonants = 0;

int countLower = 0;

int countUpper = 0;

int countOthers = 0;

int countDigit = 0;

uint sumAscii = 0;

char[] vowels = { 'e', 'y', 'u', 'i', 'o', 'a', 'й', 'у', 'е', 'ы', 'а', 'о', 'э', 'я', 'и', 'ю' };

foreach (char c in str) {

if (Char.IsLetter(c)) {

if (Char.IsLower(c)) {

++countLower;

}

else {



++countUpper;

}

if (vowels.Contains(c)) {



++countVowels;

}

else {



++countConsonants;

}

}



else if (Char.IsDigit(c)) {

++countDigit;

}

++countOthers;



sumAscii += c;

}

int n = str.Length;



uint result = sumAscii + binomialCoefficient(countConsonants, n) + binomialCoefficient(countDigit, n)

+ binomialCoefficient(countLower, n) + binomialCoefficient(countOthers, n)

+ binomialCoefficient(countUpper, n) + binomialCoefficient(countVowels, n);

return result + (1 - result & 1);

}
public static uint getMultipleParam(string str)

{

uint result = 0;



for (int i = 1; i < str.Length; ++i) {

result += (uint)Math.Pow(str[i] - str[i - 1], 2);

}

if (result < ushort.MaxValue) {



result += catalan((int)(result + str.Length) % (MAX_PASSWORD_LENGTH/2 + 1));

}

return result + (5 - (result % 4));



}
public static uint getStartValue(int length)

{

int abs = Math.Abs(MAX_PASSWORD_LENGTH/2 - length);



return length > 10 ? catalan(Math.Max(MAX_PASSWORD_LENGTH / 2 - length, abs))

: catalan(Math.Max(length, abs));

}
public static uint catalan(int n)

{

return binomialCoefficient(n, 2 * n);



}
public static uint binomialCoefficient(int k, int n)

{

return fact[n] / (fact[k] * fact[n - k]);



}

}

Код, описывающий интерфейс приложения оставим за рамками лабораторной работы.

Поделитесь с Вашими друзьями:


База данных защищена авторским правом ©psihdocs.ru 2017
обратиться к администрации

    Главная страница