Главная
страница 1
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

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



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

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

Лабораторная работа №1 по дисциплине

«Информационная безопасность и защита информации»



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

Вариант 6: Генератор Парка-Миллера

Выполнил:

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

Ильин А.Г.

Проверил:

доцент кафедры ВТ

Мартынов А.И.

Ульяновск

2012 г.

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




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

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

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

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



Описание используемых алгоритмов

Хэширование


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

      1. Приведение к виду , то есть в конец строки добавляется ноль. Это позволяет получать хороший (сильно отличающийся) хэш даже для строки из одного символа.

  1. Получение зерна по формуле

,
где — искомое зерно для ГСЧ;
— ASCII-код i-го символа строки;
— ближайшее к размеру алфавита простое число (в данной лабораторной работе — 257).

  1. Получение хэша по следующей формуле:

,
где — искомый хэш;
— i-й символ хэша;

— i-е случайное число из ГСПЧ;

() — преобразование к шестнадцатеричному виду;

mod — остаток от деления;



— получение ASCII-кода i-го символа исходной строки;

Генератор Парка-Миллера


Самая простая последовательность, которую можно предложить для реализации генератора равномерного распределения:

Константы были предложены Park и Miller:

a=75=16807 (MINSTD), m=231-1=2147483647 (число Мерсена)

Использование этих констант позволяет получить последовательность с очень большим (в рамках решаемой задачи) периодом.


Листинг программы


#!/usr/bin/env python

# -*- coding: utf-8 -*-

def PM_hash(pwd, length=32):

'''


Генерирует хеш-строку, используя ГПСЧ Парка-Миллера.

Исходная строка не может быть пустой.

Длина по умолчанию - 32 символа.

'''


if not len(pwd):

print("String may not be empty")

return 0

def Park_Miller(seed):

'''

Создаёт ГСПЧ Парка-Миллера.



Зерно представляет собой число и генерируется

на основе исходной строки

'''

last = seed



while 1:

last = (16807 * last % 2147483647)

yield last % 65535

print("\nString is: {0}\n").format(pwd)

pwd += '0' # Хороший хэш и для одного символа

'''


Генерация зерна для передачи в ГСПЧ:

Сумма произведений кода очередного символа на

ближайшее к размеру алфавита простое число

в степени, равной индексу очередного символа

'''

seed = 0


print('Generating seed...')

for i in xrange(len(pwd)):

seed += ord(pwd[i]) * (257 ** i)

print('Seed generated: {0}\n').format(seed)

'''

Из объекта hat теперь можно по одному вытаскивать случайные числа



'''

hat = Park_Miller(seed)

result = ''

'''


Для большей связи с исходным текстом (и уменьшению вероятности коллизии)

гаммируем исходный текст полученными числами. Для каждого символа исходного

текста определяем ASCII-код, суммируем со случайным числом, сжимаем до 15

вариантов, преобразуем в hex и добавляем к хешу.

Повторяем до получания необходимой длины

'''


print('Generating hash...')

for i in xrange(length):

result += hex((ord(pwd[i % len(pwd)]) + hat.next()) % 15)[2:-1]

return result

# print PM_hash(' ')

print u'''Лабораторная работа №1.

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

Выполнил: студент группы ИСТд-41 Ильин А.Г.

Вариант: №6 (генератор Парка-Миллера)

Дата выполнения: 5 октября 2012

'''

while 1:


print(u"Введите желаемую строку для получения хэша." +

u" Для завершения введите пустую строку.")

string = raw_input()

if not string:



break

print("Hash generated: {0}\n").format(PM_hash(string))



Выводы


Генератор Парка-Миллера является частным случаем линейного конгруэнтного ГПСЧ. Особенностью линейного конгруэнтного метода является то, что полученная последовательность статистически неотличима от случайной последовательности натуральных чисел, если её параметры правильно подобраны.

Однако, все элементы этой последовательности в данном случае однозначно определяются параметром – зерном. Если криптоаналитик знает об использовании линейного конгруэнтного метода с известными параметрами, то известной становится вся последовательность чисел. Даже если криптоаналитик знает только лишь об использовании линейного конгруэнтного метода, то информация о небольшой части последовательности достаточна для выявления параметров метода и всех последующих элементов последовательности. Поэтому, хотя линейный конгруэнтный метод порождает статистически хорошую псевдослучайную последовательность чисел, он не является криптографически стойким.


Смотрите также:
Лабораторная работа №1 по дисциплине «Информационная безопасность и защита информации» Хеширование паролей. Генераторы случайных чисел
43.45kb.
1 стр.
Лабораторная работа 1 Анализ и генерация случайных чисел Задание
319.84kb.
1 стр.
Генераторы псевдослучайных чисел и их применимость для расчетов монте-карло
44.25kb.
1 стр.
Лабораторная работа №1 по курсу "Информационная безопасность" Лабораторная работа №1
118.45kb.
1 стр.
С. 59-63. Генераторы случайных событий: необходима осторожность
63.53kb.
1 стр.
Рандомизированные алгоритмы. Аппаратные и программные генераторы случайных чисел. Линейные конгруэнтные гсч
33.99kb.
1 стр.
Генераторы случайных чисел
23.81kb.
1 стр.
Рассказ: Генератор случайных чисел 2007 г. Генератор случайных чисел Помолись со мной. Иди ты
123.49kb.
1 стр.
Формирование выборки случайных чисел, распределенных по заданному закону распределения
151.21kb.
1 стр.
Программа дисциплины "информационная безопасность и защита информации" Рекомендуется Министерством образования РФ для направления подготовки
167.34kb.
1 стр.
Лабораторная работа по дисциплине «Защита информации»: Криптографический шифр на основе биграмм
70.08kb.
1 стр.
Генераторы псевдослучайных чисел, оптимизированные для определенной микропроцессорной архитектуры
11.66kb.
1 стр.