«ульяновский государственный технический университет» Кафедра «Вычислительная техника»
Скачать 103.19 Kb.
|
| МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «УЛЬЯНОВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ» Кафедра «Вычислительная техника» Отчёт по лабораторной работе №1 «Хеширование паролей. Генераторы случайных чисел» Вариант №9 Выполнил: студент группы ИСТд-41 Корнеев А.В. Проверил: доцент каф. «Вычислительная техника» к.т.н. Мартынов А.И. Ульяновск 2012 г. Задание на лабораторную работу
Описание алгоритма хэшированияЛинейный конгруэнтный генератор псевдо случайных чисел.Генератор использует следующую рекуррентную последовательность  Число a называется мультипликатором, число c инкрементом, а число m - модулем. Инициализация генератора осуществляется тройкой чисел, которая устанавливает начальные значения и параметры генерации. Известно, что генерируемая последовательность будет иметь больший период, если выполняются два условия:
Хэширование с использование линейного конгруэнтного генератораПредложенный в лабораторной метод инициализации генератора был несколько модифицирован следующим образом:
Описанный генератор возвращает случайное число из диапазона 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]); } } Код, описывающий интерфейс приложения оставим за рамками лабораторной работы. |
берется не длина пароля, а 
ое число Каталана, где 
, а 
– длина пароля. Соответственно, число Каталана вычисляется по формуле 
, где 
– биноминальный коэффициент 
или число сочетаний из 
по 
.
, если полученное значение мало, оно дополняется одним из чисел Каталана. Требуется выполнение условия 
. 
число гласных в пароле, 
число согласных в пароле, 
число букв в верхнем регистре, 
число букв в нижнем регистре, 
число цифр, 
число остальных символов. Тогда 
. Инкремент увеличивается на единицу, если получено нечетное значение.Добавить документ в свой блог или на сайт
Похожие:
 | «ульяновский государственный технический университет» Кафедра «Вычислительная техника» Международная научно-практическая конференция «Судейская этика и укрепление доверия к правосудию» и Российско-шведский семинар по... |  | Структурный синтез гетерогенных подсистем обработки информации в... Работа выполнена на кафедре «Вычислительная техника» Федерального государственного бюджетного образовательного учреждения высшего... |
| Факультет авт кафедра «Вычислительная техника» | | Программа разработана в соответствии с: Федеральному Государственному... Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов для направления 230100. 68... |
| Ульяновский государственный технический университет «Программная инженерия» магистерская программа «Методы и средства разработки программных систем» на кафедре «Информационные системы»... | | «ульяновский государственный технический университет» Администрация... Цель: создание педагогических условий для формирования общих компетенций студентов педагогического колледжа |
| Фгбоу впо «Брянский государственный технический университет» Факультет энергетики и электроники Профиль (магистерская программа, специализация): «Промышленная электроника и микропроцессорная техника» | | Пермский Государственный Технический Университет Кафедра государственного... План |
| Учебной дисциплины Фгос) по профессии начального профессионального образования (далее нпо), входящей в состав укрупненной группы профессий 230000 Информатика... | | Рабочая программа учебной дисциплины Основы алгоритмизации и программирования... Фгос нпо, входящей в состав укрупненной группы профессий 230000 Информатика и вычислительная техника, по направлению подготовки 230100... |
| Реферат по дисциплине «Введение в специальность» ... | | Учебно-методический комплекс дисциплины культурология федеральное... «Дальневосточный государственный технический университет (двпи им. В. В. Куйбышева)» в г. Петропавловске-Камчатском |
| Учебно-методический комплекс дисциплины социология федеральное агентство... «Дальневосточный государственный технический университет (двпи им. В. В. Куйбышева)» в г. Петропавловске-Камчатском | | Пермский Государственный Технический Университет Кафедра мкмк курсовая работа Задача о бесконечной ортотропной пластинке с эллиптическим отверстием. Анализ ндс вблизи отверстия |
| Программа учебной ди c циплины основы информационных технологий правительство... Фгос) по профессии начального профессионального образования (далее нпо) входящей в состав укрупненной группы профессий 230000 Информатика... | | Методические указания по выполнению реферата Волгоград Ысшего профессионального образования «волгоградский государственный технический университет» камышинский технологический институт... |
