Лабораторная работа №1.
Тема работы: “Хеширование паролей. Генераторы случайных чисел”
Задание:
1. Изучить алгоритмы хеширования паролей.
2. Изучить известные алгоритмы работы генераторов случайных чисел.
3. Реализовать свой упрощенный вариант алгоритма хеширования пароля согласно варианту (по Таблице 1)
4. Реализовать свой алгоритм генератора случайных чисел согласно варианту.
5. Проанализировать выходную последовательность, выдаваемую генератором при различных параметрах.
Дополнительные требования к лабораторной работе:
Паролем может быть любая последовательность символов (русских и английских, цифр, знаков препинания и т. д.). Схема хеширования пароля также берется из лабораторной работы №1 Текст программы оформляется прилично (удобочитаемо, с описанием ВСЕХ функций, переменных и критических мест). В процессе работы программа ОБЯЗАТЕЛЬНО выдает информацию о состоянии процесса генерации. Интерфейс программы может быть произвольным, но удобным и понятным (разрешается использование библиотек VCL) Среда разработки и язык программирования могут быть произвольными.Требования для сдачи лабораторной работы:
Демонстрация работы реализованной вами системы. Авторство Теория (ориентирование по алгоритму и теоретическим аспектам) Оформление и представление письменного отчета по лабораторной работе, который содержит:1. Титульный лист
2. Задание на лабораторную работу
3. Описание используемых алгоритмов шифрования
4. Листинг программы
5. Выводы
Варианты заданий
Таблица 1.
№ варианта | Тип генератора | Диапазон значений |
Конгруэнтный генератор | 0-255 | |
Генератор Парка-Миллера | 0-65535 | |
Генератор Геффа | 0- | |
Аддитивный генератор | 0-255 | |
Конгруэнтный генератор | 0- | |
Генератор Парка-Миллера | 0-65535 | |
Генератор Геффа | 0-255 | |
Аддитивный генератор | 0-65535 | |
Конгруэнтный генератор | 0- | |
Генератор Парка-Миллера | 0- | |
Генератор Геффа | 0-255 | |
Аддитивный генератор | 0-255 | |
Конгруэнтный генератор | 0-255 | |
Генератор Парка-Миллера | 0-65535 | |
Генератор Геффа | 0-255 | |
Аддитивный генератор | 0- | |
Конгруэнтный генератор | 0- | |
Генератор Парка-Миллера | 0-255 | |
Генератор Геффа | 0-255 | |
Аддитивный генератор | 0-65535 | |
Конгруэнтный генератор | 0- | |
Генератор Парка-Миллера | 0- | |
Генератор Геффа | 0-255 | |
Аддитивный генератор | 0-255 | |
Конгруэнтный генератор | 0-65535 | |
Генератор Парка-Миллера | 0-255 | |
Генератор Геффа | 0-65535 | |
Аддитивный генератор | 0-255 | |
Конгруэнтный генератор | 0-65535 | |
Генератор Парка-Миллера | 0-255 |
Теоретический материал
1. Методы хеширования паролей
Хеширование - это преобразование, получающее из данных произвольной длины некое значение (свертку) фиксированной длины.
Рассмотрим самый простой пример хеширования пароля для конгруэнтного генератора, реализуемого формулой:
I(n+1)=(a*I(n)+c)(mod m)
Инициализация генератора осуществляется тройкой чисел, которая устанавливает начальные значения и параметры генерации. Известно, что генерируемая последовательность будет иметь больший период, если выполняются два условия:
A mod 4 = 1 C - нечетноеДля того чтобы установить привязку текстового пароля к начальным параметрам инициализации необходимо разработать алгоритм хеширования этого пароля. При этом должны выполняться несколько условий:
· полученное значение хеш-функции должно однозначно описывать текстовый пароль, причем изменение хотя бы одного символа в пароле должно вызывать существенное изменение значения хеш-функции.
· результат хеширования должен удовлетворять условиям, позволяющим получить максимальный период генерации случайных чисел.
Предложим следующий вариант:
I0 – длина пароля
A – сумма ASCII кодов пароля, вычисляемая по формуле: 
, где n = I0-1
C – сумма ASCII кодов гласных букв пароля.
Например, если пароль pass = “qwerty”, то
I0 = 6
A = 44
C = 222
Эта тройка чисел описывает текстовый пароль, но не удовлетворяет условиям успешной генерации чисел, поэтому увеличим C на единицу, то есть C =223 , а A также увеличим на 1, чтобы выполнялось условие A mod 4 = 1.
2. Обзор используемых генераторов псевдослучайных чисел
Конгруэнтный генератор
Подобные генераторы используют рекуррентную последовательность
I(n+1)=(a*I(n)+c)(mod m)
Число a называется мультипликатором, число c инкрементом, а число m - модулем.
Генератор Парка-Миллера
Самая простая последовательность, которую можно предложить для реализации генератора равномерного распределения:
I(j+1)=a*I(j)(mod m)
при соответствующем выборе констант. Константы были предложены Park и Miller:
a=75=16807, m=231-1=
Генератор Геффа
В этом генераторе потока ключей используются три LFSR, объединённые нелинейным образом.
LFSR – это Сдвиговый регистр с обратной связью состоит из двух частей: сдвигового регистра и функции обратной связи. Сдвиговый регистр представляет собой последовательность битов. Когда нужно извлечь бит, все биты сдвигового регистра сдвигаются вправо на 1 позицию. Новый крайний левый бит является значением функции обратной связи от остальных битов регистра. Периодом сдвигового регистра называется длина получаемой последовательности до начала её повторения.
В генераторе Геффа два LFSR являются входами мультиплексора, а третий LFSR управляет выходом мультиплексора.
Если a1,a2,a3-выходы трёх LFSR, выход генератора Геффа можно описать так: b=(a1 and a2) or (not a1 and a3).Если длины LFSR равны n1,n2,n3,то линейная сложность генератора равна (n1+1)n2+n1n3.Этот генератор слаб и не может устоять против корреляционного вскрытия. В 75 процентах времени выход генератора равен LFSR-2. Поэтому, если известны отводные последовательности обратной связи, можно догадаться о начальном значении LFSR-2 и сгенерировать выходную последовательность этого регистра. Можно подсчитать, сколько раз выход LFSR совпадает с выходом генератора.
Аддитивный генератор
Аддитивные генераторы очень эффективны, так как их результатом являются слова, а не случайные биты. Сами по себе они не безопасны, но могут использоваться в качестве составных блоков для безопасных генераторов.
Начальное состояние генератора представляет из собой массив n - битовых слов:
X(1),X(2),....,X(m).
Это первоначальное состояние и является ключом. i-e слово генератора
X(i)=(X(i-a)+X(i-b)+X(i-c)+...+X(i-m)) mod 2^n.
При правильном выборе a, b,c,...,m период этого генератора не меньше 2^(n-1).
