Хеширование данных. Алгоритм SHA-1

Министерство образования и науки Российской Федерации
Федеральное государственное автономное образовательное учреждение высшего профессионального образования
«
»
Институт
факультет
Кафедра
Курсовая работа на тему:
Хеширование данных. Алгоритм SHA-1
Курсовая работа
студента курса
Фамилия И. О.
Научный руководитель:
ученая степень,
ученое звание,
Фамилия И. О.
Город
2017
РЕФЕРАТ
ФИО. Курсовая работа «Хеширование данных. Алгоритм SHA-1»:
курсовая работа/ ФИО; Тамбовский государственный университет имени Г.Р.
Державина, Кафедра математического и компьютерного моделирования и
информационных технологий; Науч. рук к.ф.-м.н., доцент, доцент кафедры ИТТ
Лопатин Дмитрий Валерьевич – Тамбов, 2017. 56 – С, 11 -рис, 2 - приложений.
Предметом исследования являются применение хеширования для защиты
информации.
Объектом исследования является алгоритм SHA-1.
Ключевые слова: SHA.
Цель работы: Программная реализация алгоритма SHA-1.
Основные задачи: Описание понятия хеширования, рассмотрение
коллизий и метода их устранения, описание алгоритма SHA-1, программная
реализация алгоритма SHA-1, рассмотрение практического применения
алгоритма SHA-1.
Практическая значимость: практическая значимость курсовой работы
определятся возможностью изучения алгоритма безопасного хеширования,
получения рекомендаций по практическому использованию алгоритма и
рекомендаций по устранению возможностей возникновения коллизий. Данная
работа будет полезна как обычным пользователям, для повышения безопасности
передаваемых данных, так и специалистам по информационной безопасности.
2
СОДЕРЖАНИЕ
ВВЕДЕНИЕ
4
1. Описание предметной области
6
1.1 Описание проблемы
6
1.2 Выбор хеш-функции
9
1.3 Разрешение коллизий
10
1.3.1. Метод открытой адресации
10
1.3.2. Реализация хеш-таблицы (класс Hashtable)
13
1.3.3. Метод цепочек
17
1.3.4. Реализация словаря (класс Dictionary)
18
1.4 Анализ хеширования
19
1.5 Описание задачи
23
1.6 Описание алгоритма SHA-1
23
1.7 Сравнение SHA-1 и MD5
29
1.8 Выводы по главе 2
30
2. Программная реализация алгоритма SHA-1
31
2.1 Описание программы
31
2.2 Тестирование программы
32
2.3 Программная реализация алгоритма на Delphi
33
2.4 Выводы по главе 2
35
3. ТИПОВЫЕ ПРИМЕРЫ ИСПОЛЬЗОВАНИЯ SHA-1
36
3.1 Описание приложений, использующих SHA-1
36
3.2 Выводы по главе 3
38
ЗАКЛЮЧЕНИЕ
39
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
40
Приложение А
44
Приложение Б
48
3
ВВЕДЕНИЕ
Ценность
информации
люди
осознали
очень
давно,
объектом
пристального внимания была переписка сильных мира. В то время и возникла
задача защиты переписки от посторонних глаз. Для этой задачи люди пытались
использовать разные способы, одним из них была тайнопись – составление
сообщения таким образом, чтобы смысл был понятен только посвященным в
тайну. На протяжении долгого времени это искусство служило лишь верхушке
общества, не выходя за пределы посольств, резиденций глав государства. Лишь
несколько десятилетий назад информация приобрела коммерческую ценность,
стала
широко
распространенным
товаром.
Ее
покупают,
продают,
транспортируют, хранят и производят, и, следовательно, воруют и подделывают,
а значит ее необходимо защитить.
Наше
общество
в
большей
степени
становится
информационно
зависимым, успех какого-либо деятельности в большей мере зависит от
обладания определенными сведениями и отсутствия этих сведений у
конкурентов. Чем сильнее проявляется указанный эффект, тем больше
потребность в защите информации и больше потенциальные убытки в сфере
информации.
Постоянное
увеличение
объема
информации
и
широкое
применение компьютерных технологий вызывает рост интереса к криптографии.
В последнее время в сравнении с аппаратными криптосистемами увеличивается
роль программных средств защиты информации, которые не требуют крупных
финансовых затрат. Практически абсолютную защиту данных гарантируют
современные методы шифрования.
Одной из самых ценных вещей в современной жизни является
информация. С появление глобальных компьютерных сетей доступ к
информации не составляет труда. Быстрота и легкость доступа к данным с
помощью компьютерных сетей, таких как Интернет, делает актуальными
следующие угрозы:
- несанкционированный доступ к информации;
4
- несанкционированное изменение информации;
- несанкционированный доступ к сетям и другим сервисам.
Независимо от ценности, информация, хранящаяся на компьютере,
законодательством признается объектом частной собственности. Владелец этой
информации имеет право определять способы обработки и хранения
информации, а также обеспечивать меры, предотвращающие ее хищение,
удаление и искажение.
В настоящее время для защиты информации применяются аппаратные,
программные и программно- аппаратные средства защиты.
Актуальность
и
важность
защиты
информации
обуславливается
следующими факторами:
- современные средства информационной безопасности имеют меньший
темп и развитие, в отличие от современных информационных технологий;
- высокие темпы роста пользователей персональных компьютеров.
С хешированием мы сталкиваемся постоянно: во время работы с браузером
– список веб-страниц, переводчиком – словарь, компилятором – таблица
символов. Хеширование представляет собой разбиение ключей на не
пересекающиеся подмножества, которые обладают определенным свойством
(хеш-функция).
Целью данной курсовой работы является программная реализация
алгоритма хеширования SHA-1.
5
1. Описание предметной области
1.1 Описание проблемы
Пусть
задано
множество
объектов,
характеризуемых
некоторым
уникальным атрибутом, который называется ключом (на множестве ключей
задано отношение порядка). Требуется организовать множество объектов так,
чтобы поиск объекта с заданным ключом потребовал как можно меньше затрат.
Известны способы организации упорядоченных множеств объектов в виде
списков и деревьев. Поиск объекта по заданному значению ключа в списке
требует в среднем N/2 операций, где N – количество объектов в списке. Поиск в
сбалансированном дихотомическом дереве выполняется за log2 N операций, где
N – количество объектов в дереве. В каждом из этих методов продолжительность
поиска зависит от количества объектов в упорядоченном множестве, а
алгоритмы поиска основаны на различных способах организации самих
объектов.
Существуют методы организации упорядоченных множеств объектов, для
которых продолжительность поиска не зависит от количества объектов N. При
этом объекты должны быть организованы в виде таблицы, а для определения
местоположения
каждого
объекта
следует
использовать
ключ.
Задача
представления упорядоченного множества фактически сводится в этом случае к
задаче определения отображения H: K –> A, где K – пространство или множество
ключей, которые могут идентифицировать объекты в таблице с прямым
доступом, A – адресное пространство (множество индексов таблицы), обозначим
его 0,1,2, …, m-1. Отображение множества ключей во множество адресов
называется преобразованием ключа или хешированием (hashing), а функция H,
выполняющая такое преобразование, – хеш-функцией. Графически, хешфункцию можно изобразить, как на рисунке 1.1.
6
Ключ Объекта 1
[0]
[1]
[2]
Хеш-функция
Ключ Объекта n
...
Объект 1
...
Объект n
...
[j]
[k]
[m-2]
[m-1]
Рисунок 1.1 – Графическое представление хеш-функции
Основная трудность преобразования ключей состоит в том, что множество
возможных значений ключей намного больше, чем множество адресов таблицы
(индексов массива). Например, пусть слова, состоящие из 10 букв английского
алфавита, используются для идентификации конкретного человека во множестве
из 1000 человек. При этом имеются 2610 возможных ключей, которые должны
отображаться в 103 возможных индексов. Следовательно, H – преобразование
«многие к одному».
Алгоритмы хеширования состоят из двух компонентов: функции
хеширования, определяющей преобразование пространства ключей в адресное
пространство, и средств разрешений коллизий, устраняющих конфликты,
возникающие вследствие преобразования нескольких ключей в один адрес.
Рассмотрим следующую проблему: если задан набор элементов,
характеризующихся ключом, который определяет отношение порядка, то как
организовать этот набор, чтобы извлечение элемента с заданным ключом
требовало наименьших усилий? Ясно, что в конечном счете доступ к каждому
элементу в памяти компьютера осуществляется указанием его адреса в памяти.
Поэтому вышеуказанная проблема по сути сводится к нахождению подходящего
отображения H ключей (K) в адреса (A):
𝐻: 𝐾 → 𝐴
7
(1.1)
Это отображение можно реализовать с помощью различных алгоритмов
поиска в списках и деревьях на основе разных способов организации данных.
Опишем другой простой и во многих случаях очень эффективный подход.
В этом методе данные организуются с помощью массива. Поэтому H
является отображением, преобразующем ключи в индексы массива, откуда и
происходит название преобразование ключей, нередко используемое для этого
метода. Необходимо
отметить, что здесь не понадобятся процедуры
динамического размещения, массив является одной из фундаментальных,
статических структур. Метод преобразования ключей часто используется в тех
задачах, где с примерно равным эффектом можно применить и деревья.
Фундаментальная трудность при использовании преобразования ключей
заключается в том, что множество возможных значений ключей гораздо больше,
чем множество доступных адресов в памяти (индексов массива). Например,
возьмем имена длиной до 16 букв в качестве ключей, идентифицирующих
отдельных людей во множестве из тысячи человек. Здесь есть 2616 возможных
значений ключей, которые нужно отобразить на 103 возможных индексов.
Очевидно, что функция H отображает несколько значений аргументов в одно
значение индекса. Если задан ключ k, то первый шаг операции поиска состоит в
вычислении соответствующего индекса h = H(k), а второй – очевидно,
обязательный – шаг состоит в проверке того, действительно ли элемент с ключом
k соответствует элементу массива (таблицы) T с индексом h, то есть выполняется
ли равенство T[H(k)].key = k.
Сразу возникают два вопроса:
- Какую функцию H надо взять?
- Что делать, если H не смогла вычислить адрес искомого элемента?
Ответ на второй вопрос состоит в том, чтобы использовать такой метод,
который даст альтернативную позицию, например, индекс h', и если там попрежнему нет искомого элемента, то третий индекс h'', и так далее. Такие
попытки называются – пробы. Ситуацию, когда в вычислительной позиции
8
находится элемент, отличный от искомого, называют коллизией, задача
порождения альтернативных индексов называется разрешением коллизий.
1.2 Выбор хеш-функции
Каждый элемент пространства ключей K является цифровым, алфавитным
или алфавитно-цифровым идентификатором. Хорошая функция преобразования
ключей должна обеспечивать как можно более равномерное распределение
ключей по всему диапазону значений индекса. Других ограничений на
распределение нет, но на самом деле желательно, чтобы оно оказалось
совершенно случайным. Это свойство дало методу название – хеширование. H
называется хеш-функцией. Эта функция должна допускать эффективное
вычисление, то есть состоять из очень небольшого числа основных
арифметических операций.
Допустим, что имеется функция преобразования ORD(k), которая
вычисляет порядковый номер ключа k во множестве всех возможных ключей.
Кроме того, предположим, что индекс массива i принимает значения в диапазоне
целых чисел от 0 до N-1, где N – размер массива. Тогда есть очевидный вариант:
𝐻(𝑘) = 𝑂𝑅𝐷(𝑘) 𝑀𝑂𝐷 𝑁
(1.2)
Такой выбор обеспечивает равномерное распределение ключей по
диапазону индексов и поэтому является основой большинства хеш-функций. Это
выражение очень быстро вычисляется, если N есть степень 2, но именно этого
случая следует избегать, если ключи являются последовательностями букв.
Предположение, что все ключи равно вероятны, в этом случае неверно, и на
самом деле слова, отличающиеся лишь немногими буквами, будут с большей
вероятностью отображаться на одно и то же значение индекса, так что получится
весьма неоднородное распределение. Поэтому особенно рекомендуется в
качестве значения N выбирать простое число. Как следствие придется
использовать полную операцию деления, которую нельзя заменить простым
9
отбрасыванием двоичных цифр, но это не является проблемой на большинстве
современных компьютеров, имеющих встроенную инструкцию деления.
Часто используют хеш-функции, состоящие в применении логических
операций, таких как исключающее «или», к некоторым частям ключа,
представленного как последовательность двоичных цифр. На некоторых
компьютерах эти операции могут выполняться быстрее, чем деление, но иногда
они приводят к удивительно неоднородному распределению ключей по
диапазону индексов.
1.3 Разрешение коллизий
При добавлении элемента в хеш-таблицу коллизия создает основную
проблему всей операции. Без коллизии добавляемый элемент размещается по
индексу, непосредственно вычисленному с помощью хеш-функции. При
наличии коллизии нужный индекс уже занят, поэтому необходимо найти
некоторую другую ячейку для размещения объекта, т.е., вычислить другой
индекс h, который однозначно получается на основе данного ключа. Подобное
корректирующее
действие
называется
разрешением
коллизии
(collision
resolution).
Существует несколько стратегий разрешения коллизии:
- метод открытой адресации;
- метод цепочек.
1.3.1. Метод открытой адресации
Согласно методу открытой адресации, если ключ k отображается в
табличный индекс i, а он уже занят, в таблице просматриваются другие индексы
до тех пор, пока не будет найдено свободное место для объекта, приведшего к
коллизии (G(i) – некоторая функция):
i = i + 1; h = H(k) + G(i);
Для определения функции G(i) можно использовать
10
(1.3)
- линейную проверку (linear probing),
- квадратичную проверку (quadratic probing);
- повторное хеширование (rehashing), называемое также двойным
хешированием (double hashing).
При линейной проверке используется следующая последовательность
индексов в предположении, что таблица круговая:
i, i+1, …, m-1, 0, 1, 2, …, i-1.
Такая последовательность получается, если функция G(i) = i, индексы hi,
используемые для поиска, имеют вид:
h0 = H(k),
hi = (h0 + i) % m, i = 1, …, m-1.
(1.4)
Линейная проверка, хотя и проста в реализации, не является хорошей
стратегией разрешения коллизий, т.к. ведет к кластеризации, при которой вокруг
первичных ключей (ключей, для которых конфликта при занесении в таблицу не
было) возникают все более длинные последовательности занятых подряд
индексов. Например, пусть надо добавить в таблицу Объект 1 с ключом 1234,
Объект 2 с ключом 4674, Объект 3 с ключом 6827, Объект 4 с ключом 3235,
Объект 5 с ключом 7165, размер таблицы m =10, хеш-функция вычисляется по
формуле (1.4). Объект 1 будет размещен в ячейке с индексом 4. Объект 2 также
должен быть размещен в элементе с индексом 4, но этот индекс уже занят,
поэтому Объект 2 занимает следующий свободный элемент
с индексом 5.
Объект 3 добавляется в элемент с индексом 7. Объект 4 должен быть добавлен в
элемент с индексом 5, но этот индекс уже занят, поэтому Объект 4 занимает
следующий свободный элемент с индексом 6. Объект 5 должен быть добавлен в
элемент с индексом 5, но этот индекс уже занят, следующие элементы с
индексами 6 и 7 также заняты, поэтому Объект 5 занимает свободный элемент с
индексом 8.
Коллизии усложняют не только процесс вставки объекта в хеш-таблицу,
но также и процесс поиска объекта по ключу. Например, если необходимо найти
11
информацию об Объекте 5, то по его ключу 7165 вычисляется значение хешфункции, равное 5. Но в элементе с индексом 5 находится Объект 2. Линейный
поиск следует продолжать до тех пор, пока не будет найден объект с заданным
ключом или пустой элемент таблицы. Если в таблице найден пустой элемент, это
означает, что в ней не содержится объект с заданным ключом.
Избежать кластеризации позволяет квадратичная проверка, выполняющая
просмотр индексов таблицы на квадратичном расстоянии (функция G(i) = i2):
h0 = H(k),
hi = (h0 + i ) % m, i = 1, …, m-1.
(1.5)
2
Однако даже квадратичная проверка может привести к кластеризации.
Кроме того, недостаток этой стратегии заключается в том, что при добавлении
объекта можно пропустить свободный элемент. Фактически при квадратичной
проверке используется половина таблицы.
Повторное хеширование работает следующим образом: пусть имеется
набор различных хеш-функций H1, …, Hn и при вставке или извлечении объекта
из хеш-таблицы первоначально используется функция H1. Если это приводит к
коллизии, то производится попытка использования хеш-функции H2 и так далее
до Hn при необходимости. При повторном хешировании очень важно, чтобы
каждый элемент хеш-таблицы просматривался ровно один раз, когда делается m
просмотров, где m – размер таблицы. Это означает, что функции Hi и Hj не
должны выдавать один и тот же индекс таблицы. Такой результат достигается,
если значения, получаемые при вычислении функций Hi и Hj, являются взаимно
простыми числами, что гарантировано, если размер таблицы m – простое число.
Повторное хеширование обеспечивает лучшую технику избежания коллизий,
чем линейная или квадратичная проверка.
Для анализа методов устранения коллизий используется вероятностная
модель, на основе которой получаются формулы для средней длины успешного
и неуспешного поиска. Предполагается, что каждый ключ может быть
отображен в каждый из элементов хеш-таблицы с равной вероятностью 1 / m.
12
Следовательно, существует mN различных вариантов отображения значений
ключей в адресное пространство, где N – количество объектов. Средняя длина
поиска (ALoS – Average Length of Searching) зависит от коэффициента
заполнения таблицы α = N / m, определяемого как отношение занятого и общего
адресного пространства хеш-таблицы. Средняя длина поиска при линейной
проверке вычисляется по формуле (1.6).
1
1 
1 

2  1  
при удачном поиске
ALoSlinear probing 
(1.6)

1
1
1

2
1





2


при неудачном поиске
1.3.2. Реализация хеш-таблицы (класс Hashtable)
.Net Framework Base Class Library имеет реализацию хеш-таблицы в виде
класса System.Collections.Hashtable, предоставляющий коллекцию пар «ключзначение», которые упорядочены по хеш-коду ключа. И значение, и ключ могут
быть любого типа. В этом классе реализованы стандартные операции по работе
с хеш-таблицей, которые описаны в таблице 1.1.
Таблица 1.1 - Методы и свойства класса Hashtable
Сигнатура
public Hashtable(int capacity);
public Hashtable();
public virtual void Add(object key, object
value);
Описание
создает и инициализирует новый экземпляр
класса Hashtable с заданным количеством
элементов. Capacity – минимальное число
элементов, которые должен содержать
экземпляр класса Hashtable
создает и инициализирует новый экземпляр
класса Hashtable с количеством элементов по
умолчанию
добавляет в текущий экземпляр класса
Hashtable элемент с ключом key и значением
value
13
Продолжение таблицы 1.1
public virtual void Clear();
public virtual object Clone();
public virtual bool Contains(object key);
public virtual bool ContainsKey(object key);
public virtual bool ContainsValue(object
value);
public virtual void CopyTo(Array array, int
arrayIndex);
protected virtual int GetHash(object key);
public virtual void Remove(object key);
public virtual int Count { get; }
public virtual ICollection Keys { get; }
ICollection IDictionary.Keys { get; }
public virtual ICollection Values { get; }
ICollection IDictionary.Values { get; }
удаляет все элементы из текущего
экземпляра класса Hashtable
создает объект класса Object, который
является копией текущего экземпляра класса
Hashtable
определяет, содержит ли текущий экземпляр
класса Hashtable заданный ключ key.
Возвращает true, если текущий экземпляр
класса Hashtable содержит заданный ключ
key
определяет, содержит ли текущий экземпляр
класса Hashtable элемент с заданным
ключом key. Возвращает true, если текущий
экземпляр класса Hashtable содержит
элемент с заданным ключом key
определяет, содержит ли текущий экземпляр
класса Hashtable элемент с заданным
значением value. Возвращает true, если
текущий экземпляр класса Hashtable
содержит элемент с заданным значением
value
копирует элементы текущего экземпляра
класса Hashtable в одномерный массив array,
начиная с индекса arrayIndex
генерирует хеш-код для заданного ключа
key текущего экземпляра класса Hashtable
удаляет элемент с заданным ключом key из
текущего экземпляра класса Hashtable
свойство
возвращает
число
пар
ключ/значение, содержащихся в текущем
экземпляре класса Hashtable
свойство возвращает коллекцию ICollection,
содержащую ключи элементов текущего
экземпляра класса Hashtable
свойство реализует поддержку интерфейса
IDictionary, возвращает пары ключ/значение
свойство возвращает коллекцию ICollection,
содержащую значения элементов текущего
экземпляра класса Hashtable
свойство реализует поддержку интерфейса
IDictionary, возвращает пары ключ/значение
С помощью метода Add() добавляются объекты в хеш-таблицу. В качестве
индекса, для извлечения объекта из хеш-таблицы, используется ключ, как и в
случае индексирования массива порядковым значением. Метод ContainsKey()
возвращает логическое значение, указывающее, был ли найден данный ключ в
14
хеш-таблице. Класс Hashtable содержит также свойство Keys, которое
возвращает набор ключей, используемых в хеш-таблице. Это свойство может
использоваться для перечисления элементов в хеш-таблице. Порядок, в котором
добавляются объекты, и порядок ключей в коллекции Keys не обязательно
совпадают. Индекс элемента таблицы, в котором хранится объект, зависит от
хеш значения ключа и стратегии разрешения коллизий.
Рассмотрим функцию хеширования класса Hashtable.
Функция хеширования реализована в методе GetHashCode(), который
определен в классе System.Object. Реализация метода в классе Object возвращает
уникальное целое число, которое не изменяется за время жизни объекта. Т.к.
каждый объект является наследником, прямым или непрямым, класса Object, все
объекты имеют доступ к этому методу. Поэтому объект любого типа может быть
представлен уникальным целым числом.
Функция хеширования класса Hashtable определена следующим образом
(1.7):
H(key) = [ GetHash(key) + 1 + ((( GetHash(key) >> 5) + 1) %
( hashsize – 1 )) ] % hashsize
(1.7)
GetHash(key) – по умолчанию, результат, возвращаемый вывовом
GetHashCode(). GetHash(key) >> 5 вычисляет хеш-код для ключа key и затем
сдвигает результат на 5 разрядов вправо, что эквивалентно выполнению
операции деления на 32. Оператор % выполняет модульную арифметику,
hashsize – общее число элементов хеш-таблицы. Благодаря операции взятия
остатка от деления, H(key) всегда будет целым числом в диапазоне от 0 до
hashsize-1. Т.к. hashsize – общее число элементов хеш-таблицы, результирующее
хеш-значение всегда будет указывать на допустимый индекс таблицы.
Рассмотрим разрешение коллизий в классе Hashtable.
Для разрешения коллизий в классе Hashtable используется повторное
хеширование. Функция H1 определяется по формуле (1.7). Другие хеш-функции
15
отличаются от (1.7) только коэффициентом умножения k. В общем случае хешфункция определяется следующим образом (1.8):
H(key) = [ GetHash(key) + k * ( 1 + ((( GetHash(key) >> 5) + 1) %
( hashsize – 1 ))) ] % hashsize
(1.8)
Рассмотрим коэффициент заполнения и расширение хеш-таблицы.
Класс Hashtable содержит скрытый член класса, называемый LoadFactor,
который задает коэффициент заполнения хеш-таблицы α (значение в диапазоне
от 0.1 до 1.0). Коэффициент заполнения, равный 0.5, означает, что хеш-таблица
может содержать до половины своих элементов незаполненными. Всякий раз,
когда в хеш-таблицу добавляется новое значение, производится проверка, не
приведет ли эта операция к превышению максимального значения коэффициента
заполнения. Если операция добавления объекта приведет к такому увеличению,
хеш-таблица будет расширена согласно следующему алгоритму:
- число элементов хеш-таблицы приблизительно удваивается. Более точно,
число элементов увеличивается от текущего значения в виде простого числа до
следующего простого числа.
- т.к. хеш-значение каждого элемента хеш-таблицы зависит от общего
числа элементов хеш-таблицы, все хеш-значения необходимо повторно
вычислить.
Коэффициент заполнения влияет на ожидаемое количество просмотров
таблицы при возникновении коллизии. Более высокий коэффициент заполнения,
который позволяет иметь относительно плотную хеш-таблицу, требует меньше
памяти, но большего числа просмотров при возникновении коллизии, чем
разреженная хеш-таблица.
Расширение хеш-таблицы является дорогой операцией. Поэтому, если
имеется предварительная оценка количества объектов, которые должны
храниться в хеш-таблице, можно задать начальную емкость хеш-таблицы в
конструкторе (capacity), чтобы избежать нежелательных увеличений ее размера
впоследствии.
16
1.3.3. Метод цепочек
Согласно методу цепочек (chaining), для разрешения коллизий все
множество ключей разбивается на несколько непересекающихся подмножеств,
называемых классами эквивалентности. Два ключа попадают в один и тот же
класс эквивалентности, если хеш-функция преобразует их в один и тот же индекс
таблицы. Каждый класс эквивалентности хранится в виде отдельного списка. В
случае коллизии объект, приводящий к коллизии, добавляется в конец
соответствующего списка. Структура, представляющая хеш-таблицу в виде
связанных списков объектов, называется словарем (Dictionary). Структура
словаря, использующего функцию хеширования, где размер таблицы m = 10,
показана на рисунке 1.2.
10
140
21
32
262
182
63
478
928
569
99
Рисунок 1.2 - Структура словаря
Средняя длина поиска при использовании метода цепочек определяется по
формуле (1.9).
1
ALoSchaining 

2
при удачном поиске
(1.9)

 e
при неудачном поиске
17
1.3.4. Реализация словаря (класс Dictionary)
.Net Framework Base Class Library содержит реализацию хеш-таблицы в
виде класса System.Collections.Generic.Dictionary. Хеш-таблица (Hashtable)
является слабо типизированной структурой данных, т.к. в хеш-таблицу можно
добавлять ключи и значения любого типа. Класс Dictionary имеет сильную
типизацию как для ключей, так и для значений. При создании экземпляра класса
Dictionary необходимо указать типы данных и для ключа, и для значения
следующим образом:
Dictionary<Tkey, TValue> variableName =
new Dictionary<Tkey, TValue> ();
Объект класса Dictionary относится к типу KeyValuePair<(Of<(Tkey,
TValue>)>), представляющему пару из типа ключа и типа значения. В классе
Dictionary реализованы операции по работе с хеш-таблицей, описанные в
таблице 1.2.
Таблица 1.2 - Методы класса Dictionary
Сигнатура
Add
Clear
ContainsKey
ContainsValue
Equals
Finalize
GetEnumerator
Описание
добавляет указанные ключ и значение в
словарь
удаляет все ключи и значения из словаря
Dictionary<(Of <(TKey, TValue>)>)
определяет, содержится ли указанный ключ
в словаре Dictionary<(Of <(TKey, TValue>)>)
определяет,
содержит
ли
коллекция
Dictionary<(Of
<(TKey,
TValue>)>)
указанное значение
определяет, равен ли заданный объект Object
текущему объекту Object (унаследовано от
Object)
позволяет объекту Object попытаться
освободить ресурсы и выполнить другие
операции очистки, перед тем как объект
Object будет утилизирован в процессе
сборки мусора (унаследовано от Object)
возвращает
перечислитель,
осуществляющий
перебор
элементов
словаря Dictionary<(Of <(TKey, TValue>)>)
18
Продолжение таблицы 1.2
GetHashCode
играет
роль
хеш-функции
для
определенного типа (унаследовано от
Object)
возвращает объект Type для текущего
экземпляра (унаследовано от Object)
создает неполную копию текущего объекта
Object (унаследовано от Object)
удаляет значение с указанным ключом из
словаря Dictionary<(Of <(TKey, TValue>)>)
возвращает
объект
String,
который
представляет текущий объект Object
(унаследовано от Object)
получает значение, связанное с указанным
ключом
Свойства
Возвращает
компаратор
IEqualityComparer<(Of <T>)>), используемый для установления равенства ключей
словаря
Возвращает число пар "ключ-значение",
содержащихся в словаре Dictionary<(Of
<(TKey, TValue>)>)
Возвращает или задает значение, связанное
с указанным ключом
Получает коллекцию, содержащую ключи из
словаря Dictionary<(Of <(TKey, TValue>)>)
Получает коллекцию, содержащую значения
в объекте Dictionary<(Of <(TKey, TValue>)>)
GetType
MemberwiseClone
Remove
ToString
TryCetValue
Compare
Count
Item
Keys
Values
Таким образом, хеш-таблица расширяет массив (ArrayList), реализуя
индексирование элементов с помощью произвольного ключа, в отличие от
индексирования порядковым значением. Поиск по уникальному ключу
эффективнее производится в хеш-таблице, чем в массиве, т.к. в хеш-таблице
поиск выполняется за константное время в отличие от линейного поиска в
массиве. Словарь представляет собой безопасную хеш-таблицу с альтернативной
стратегией разрешения коллизий.
1.4 Анализ хеширования
Производительность вставки и поиска в методе хеширования в худшем
случае оставляет желать лучшего. Ведь нельзя исключать, что аргумент поиска
19
таков, что все пробы пройдут в точности по занятым позициям, ни разу не попав
в нужные или свободные. Нужно иметь большое доверие законам теории
вероятностей, чтобы применять технику хеширования. Здесь нужна уверенность
в том, что в среднем число проб мало. Проводимые ниже вероятные аргументы
показывают, что это число очень мало.
Предположим, что все возможные значения ключей равновероятны и что
хеш-функция H распределяет их равномерно по диапазону индексов таблицы.
Допустим, что некоторый ключ вставляется в таблицу размера N, уже
содержащую k элементов. Тогда вероятность попадания в свободную таблицу с
первого раза равно (N-k)/N. Этой же величине равна вероятность p1 того, что
будет достаточно одного сравнения. Вероятность того, что понадобится в
точности еще одна проба, равна вероятности коллизии на первой попытке,
умноженной на вероятность попасть в свободную позицию на второй. В общем
случае получим вероятность pi вставки, требующей в точности i проб:
𝑘
𝑘−1
𝑁
𝑁−1
𝑝𝑖 = ( ) ×
×
𝑘−2
𝑁−2
× … × (𝑁 − 𝑘)/(𝑁 − (𝑖 − 1))
(1.10)
Поэтому среднее число E проб, необходимых для вставки k+1-го ключа,
равно
𝐸𝑘+1 = 𝑆𝑖 : 1 ≤ 𝑖 ≤ 𝑘 + 1: 𝑖 × 𝑝𝑖 = (𝑁 + 1)/(𝑁 − (𝑘 − 1))
(1.11)
Поскольку число проб для вставки элемента совпадает с числом проб для
его поиска, этот результат можно использовать для вычисления среднего числа
E проб, необходимых для доступа к случайному ключу в таблице. Пусть снова
размер таблицы обозначен как N, и пусть m – число ключей в таблице. Тогда
𝑆 :1≤𝑘≤𝑚: 𝐸𝑘
𝐸= 𝑘
𝑚
= (𝑁 + 1) × (𝐻𝑁+1 − 𝐻𝑁−𝑚+1 )
20
(1.12)
где H – гармоническая функция. H можно аппроксимировать как HN =
ln(N)+g, где g – постоянная Эйлера. Далее, если ввести обозначение a для
отношения m/(N+1), то получаем
𝐸=
ln(𝑁+1)−ln(𝑁−𝑚+1)
𝑎
= −ln(1 − 𝑎)/𝑎
(1.13)
Величина a примерно равна отношению занятых и свободных позиций, это
отношение называется коэффициентом заполнения, a = 0 соответствует пустой
таблице, a ≈ 1 – полной. Среднее число E проб для поиска или вставки
случайного ключа дано в таблице 1.3 как функция коэффициента заполнения.
Таблица 1.3 – Среднее число проб E как функция заполнения коэффициента a
a
E
0.1
1.05
0.25
1.15
0.5
1.39
0.75
1.85
0.9
2.56
0.95
3.15
0.99
4.66
Полученные
числа
объясняют
исключительно
высокую
производительность метода преобразования ключей. Даже если таблица
заполнена на 90%, в среднем нужно только 2,56 пробы, чтобы найти искомый
ключ или свободную позицию. Подчеркнем, что это число не зависит от
абсолютного числа ключей, а только от коэффициента заполнения.
Приведенный анализ предполагает, что применяемый метод разрешения
коллизий равномерно рассеивает ключи по оставшимся позициям. Методы,
используемые на практике, дают несколько худшую производительность.
Детальный анализ метода линейных проб дает следующий результат для
среднего числа проб:
21
𝑎
𝐸 = (1 − )/(1 − 𝑎)
(1.14)
2
Некоторые численные значения E(а) приведены в таблице 1.4.
Таблица 1.4 – Среднее число проб для метода линейных проб
а
E
0.1
1.06
0.25
1.17
0.5
1.50
0.75
2.50
0.9
5.50
0.95
10.50
Результаты даже для простейшего способа разрешения коллизий
настолько хороши, что хеширование можно рассматривать как универсальный
метод во всех случаях. Тем более что его производительность превышает все
методы с использованием деревьев, по крайней мере с точки зрения числа
сравнений, необходимых для поиска и вставки. Поэтому рассмотрим некоторые
недостатки хеширования, даже если они очевидны при непредвзятом анализе.
Серьезным недостатком по сравнению с методами с динамическим
размещением являются фиксированный размер таблицы и невозможность
изменять его в соответствии с текущей необходимостью. Поэтому обязательно
нужна хорошая априорная оценка числа обрабатываемых элементов данных,
если
неприемлемы
плохое
использование
памяти
или
низкая
производительность, либо переполнение таблицы. Даже если число элементов
известно точно, - что бывает крайне редко, - стремление к хорошей
производительности заставляет выбирать таблицу немного большего размера,
примерно на 10%.
Второй серьезный недостаток методов «рассеянного хранения» становится
очевидным, если ключи нужно не только вставлять и искать, но и удалять.
Удаление элементов в хеш-таблице – чрезвычайно громоздкая операция, если
только не использовать прямое связывание в отдельной области переполнения.
22
1.5 Описание задачи
В рамках этой курсовой работы напишем программу, которая считает хешзначение сообщения, зашифровывает и расшифровывает это сообщение.
Опишем алгоритм программы и проведем ее тестирование.
1.6 Описание алгоритма SHA-1
На входе алгоритм получает сообщение максимальной длины 264, а на
выходе создается дайджест сообщения длиной в 160 бит.
Алгоритм состоит из шагов, показанных на рисунке 1.3.
Рисунок 1.3 – Логика выполнения SHA-1
На первом шаге добавляются недостающие биты. В сообщение
недостающие биты добавляются так, чтобы длина была кратна 448 по модулю
512:
длина ≡ 448 𝑚𝑜𝑑 512
(2.1)
Добавление осуществляется в любом случае, даже в том, когда сообщение
имеет нужную длину. Количество добавляемых битов находится в диапазоне от
1 до 512.
Сначала добавляется единица, а после нее недостающие нули.
На втором шаге добавляется длина. Блок, состоящий из 64 битов,
добавляется к сообщению. Данный блок представляет собой беззнаковое 64битное целое, которое содержит длину до добавления исходного сообщения.
23
В результате, после выполнения первых двух шагов, получается
сообщение, имеющие длину кратную 512 битам. В расширенном виде сообщение
можно представить, как последовательность блоков Y0, Y1, . . . , YL-1 длиной в 512
бит, таким образом, что расширенное сообщение имеет длину L * 512 бит. В
результате, длина сообщения кратна шестнадцати 32-битным словам.
На третьем шаге происходит инициализация буфера SHA-1. Для хранения
окончательных и промежуточных результатов хеш-функции используется 160битный буфер. Его можно представить, как пять 32-битных регистров: А, В, С,
D
и
Е.
Следующими
шестнадцатеричными
числами
эти
регистры
инициализируются:
- А = 67452301;
- В = ЕFСDАВ89;
- С = 98ВАDCFE;
- D = 10325476;
- Е = С3D2E1F0.
На четвертом шаге происходит обработка сообщения в 16-словных или
512-битных блоках. Модуль, который состоит из 80 циклических обработок,
является основой алгоритма. Он обозначается как Hsha. Согласно рисунку 1.4 все
эти циклические обработки имеют одну и ту же структуру.
24
Рисунок 1.4 – Обработка одного 512-битного блока
На входе каждый цикл получает текущий обрабатываемый 512-битный
блок Yq и ABCDE – 160-битное значение буфера, и содержимое этого буфера
изменяет.
Дополнительная константа Kt используется в каждом цикле. Она
принимает только четыре различных значения:
- 0 <= t <= 19 Kt = 5A827999 (целая часть числа [230 x 21/2]);
- 20 <= t <= 39 Kt = 6ED9EBA1 (целая часть числа [230 x 31/2]);
- 40 <= t <= 59 Kt = 8F1BBCDC (целая часть числа [230 x 51/2]);
- 60 <= t <= 79 Kt = CA62C1D6 (целая часть числа [230 x 101/2]).
25
Для получения SHAq+1 значение SHAq складывается с выходом 80-го
цикла. Сложение по модулю 232 выполняется независимо для каждого из пяти
слов в буфере с каждым из соответствующих слов в SHAq.1
Пятый шаг – выход. Выходом L-ой стадии, после обработки всех 512битных блоков является дайджест сообщения размером 160 бит.
Более детально рассмотрим логику обработки одного 512-битного блока в
каждом из 80 циклов. Согласно рисунку 1.5 каждый цикл можно представить в
следующем виде:
𝐴, 𝐵, 𝐶, 𝐷, 𝐸 (𝐶𝐿𝑆5 (𝐴) + 𝑓𝑡 (𝐵, 𝐶, 𝐷) + 𝐸 + 𝑊𝑡 + 𝐾𝑡 ), 𝐴, 𝐶𝐿𝑆30 (𝐵), 𝐶, 𝐷
(2.2)
Где:
- А, В, С, D, Е - пять слов из буфера;
- t - номер цикла, 0 <= t <= 79;
- ft - элементарная логическая функция;
- СLSs - циклический левый сдвиг 32-битного аргумента на s битов;
- Wt - 32-битное слово, которое получилось из текущего входного 512битного блока;
- Kt - дополнительная константа;
- + - сложение по модулю 232.2
1
Дональд Кнут. Искусство программирования. Том 3. Сортировка и поиск = The Art of Computer Programming,
vol.3. Sorting and Searching. — 2-е издание. — М.: «Вильямс», 2007. — С. 824. — ISBN 0-201-89685-0.
2
Кормен Т., Лейзерсон Ч., Ривест Р., Алгоритмы: построение и анализ, М.: МЦНМО, 2001
26
Рисунок 1.5 – Логика выполнения отдельного цикла
Каждая элементарная функция на входе получает три 32-битных слова и
на выходе создает одно 32-битное слово. Данная функция выполняет набор
логических побитных операций, то есть n-ый бит выхода представляет собой
функцию от n-ых битов трех входов. Эти функции указаны в таблице 2.1.
Таблица 2.1 – Набор логических побитных операций
Номер цикла
Ft(В, С, D)
(0 <= t <= 19)
(B˄C)˅(¬B˄D)
(20 <= t <= 39)
BCD
(40 <= t <= 59)
(В˄С)˅(В˄D)˅(C˄D)
(60 <= t <= 79)
BCD
Но, на практике используются только три различные функции. Для 0 <= t
<= 19 функция условная: if B then C else D. Для 20 <= t <= 39 и 60 <= t <=
27
79 функцией создается бит четности. Для 40 <= t <= 59 функция истинна, если
два или три аргумента являются истинными.
Из очередного 512-битного блока сообщения получаются 32-битные слова
Wt в соответствие с рисунком 1.6.
Рисунок 1.6 – Получение входных значений каждого цикла из очередного блока
Первые 16 значений Wt берутся непосредственно из 16 слов текущего
блока. Оставшиеся значения определяются формулой:
𝑊𝑡 = 𝑊𝑡−16  𝑊𝑡−14  𝑊𝑡−8  𝑊𝑡−3
(2.3)
На первых 16 циклах вход состоит из 32-битного слова данного блока.
Оставшиеся 64 цикла вход состоит из XOR нескольких слов из блока сообщения.
Следующим образом можно суммировать алгоритм SHA-1:
𝑆𝐻𝐴0 = 𝐼𝑉
(2.4)
𝑆𝐻𝐴𝑞+1 ∑ 32 (𝑆𝐻𝐴𝑞 , 𝐴𝐵𝐶𝐷𝐸𝑞 )
(2.5)
𝑆𝐻𝐴 = 𝑆𝐻𝐴𝐿−1
(2.6)
Где:
- IV - начальное значение буфера АВСDЕ;
- АВСDЕq - результат обработки q-того блока сообщения;
- L - число блоков в сообщении, включающие поля длины и добавления;
28
- 32 - сумма по модулю 232, которая выполняется отдельно для каждого
слова буфера;
- SHА - значение дайджеста сообщения.3
1.7 Сравнение SHA-1 и MD5
SHA-1 и MD5 имеют много общего, так как оба алгоритма произошли от
MD4.
Ключевые различия между этими двумя алгоритмами представлены в
таблице 2.2.
Таблица 2.2 – Сравнительная характеристика MD5 и SHА-1
Характеристика
MD5
SHA-1
Длина дайджеста
128 бит
160 бит
Размер блока обработки
512 бит
512 бит
Число итераций
64 (4 цикла по 16 итераций
80
в каждом)
Число элементарных
4
4
64
4
логических функций
Число дополнительных
констант
Произведем сравнение этих алгоритмов в соответствии с целями,
определенными для MD4:
- Безопасность. Наиболее важное и наиболее очевидное различие состоит
в том, что дайджест MD5 короче на 32 бита, чем дайджест SHA-1. SHA-1 более
стойкий алгоритм, если предположить отсутствие в обоих алгоритмах какихлибо структурированных данных, уязвимых для криптоаналитических атак. Если
использовать лобовую атаку, будет труднее создать произвольное сообщение,
которое имеет данный дайджест, если требуется около 2 160 операций, как в
случае алгоритма SHA-1, чем около 2128 операций, в случае алгоритма MD5. При
использовании лобовой атаки, трудно создать два сообщения, которые имеют
3
Шень А, Программирование: теоремы и задачи. М.: МЦНМО, 1995.
29
одинаковый дайджест, в случае алгоритма SHA-1 требуется порядка 280, а в
случае MD5 порядка 264 операций.
- Скорость. Оба алгоритма рассчитаны на 32-битную архитектуру, так как
выполняют сложение по модулю 232. SHA-1 выполняется на 160-битном буфере
и содержит больше шагов (80 вместо 64), а MD5 на 128-битном буфере. Так, MD5
выполняется приблизительно на 25% быстрее, чем SHA-1 на той же аппаратуре.
- Простота и компактность. Оба алгоритма не требуют подстановочных
таблиц и больших программ, просты в реализации и описании. Однако, в SHA-1
используется одношаговая архитектура, а в MD5 архитектура с четырьмя
структурами. В то время как в MD5 для каждого шага структура слов
специфична, а в SHA-1 для всех шагов обработка слов в буфере одинакова.
- Архитектуры little-endian и big-endian: MD5 использует little-endian схему
для интерпретации сообщения как последовательности 32-битных слов, в то
время как SHA-1 задействует схему big-endian. Каких-либо преимуществ в этих
подходах не существует.4
1.8 Выводы по главе 1
Методы и алгоритмы хеширования имеют свои плюсы и минусы. Среди
преимуществ следует отметить скорость и безопасность. Может показаться, что
чем быстрее, тем лучше для пользователей: меньшая нагрузка на сервер, быстрая
регистрация новых пользователей. Но, чем больше скорость хеширования, тем
легче злоумышленнику взломать его. Здесь очень важно подобрать золотую
середину.
Secure Hash Algorithm 1 — алгоритм криптографического хеширования.
SHА-1 реализует хеш-функцию, построенную на идее функции сжатия. MD5 и
SHА-1 по сути, представляют собой улучшенные продолжения MD4.
4
Herbert Hellerman. Digital Computer System Principles. N.Y.: McGraw-Hill, 1967, 424 pp.
30
2. Программная реализация алгоритма SHA-1
2.1 Описание программы
Для написания программы используется среда разработки Microsoft Visual
Studio 2015. Язык программирования C#. Программа считает хеш-значение
сообщения, зашифровывает и расшифровывает это сообщение. Для работы с
алгоритмом подключена библиотека System.Security.Cryptography.
Текст программы приведен в приложении А.
Программа состоит из трех частей: функция Shifr зашифровывает
сообщение и подсчитывает его хеш-сумму, функция Deshifr расшифровывает
сообщение на основе пароля и хеш-суммы. В основной функции передаются
аргументы для Shifr – сообщение и пароль, для Deshifr – хеш-сумма и пароль.
На консоль выводятся хеш-значение и расшифрованное значение.
В функции Shifr также производится проверка на наличие сообщения,
если пустое, то возвращается соответствующая хеш-сумма. Кодируются все
символы в байты:
byte[] initVecB = Encoding.ASCII.GetBytes(initVec);
byte[] solB = Encoding.ASCII.GetBytes(sol);
byte[] ishTextB = Encoding.UTF8.GetBytes(ishText).
Далее создается экземпляр класса PasswordDeriveBytes и переводится в
байты
размер
ключа.
Создается
экземпляр
класса
RijndaelManaged,
инициализируется и задается режим блочного шифра:
RijndaelManaged symmK = new RijndaelManaged();
symmK.Mode = CipherMode.CBC.
Затем
создается
объект-шифратор
для
алгоритма
симметричного
шифрования с заданным ключом. С помощью следующей строки создается
поток с резервным хранилищем – памятью:
using (MemoryStream memStream = new MemoryStream()).
В следующей строке определяется поток, который связывает потоки
данных с криптографическими преобразованиями:
31
using
(CryptoStream
cryptoStream
=
new
CryptoStream(memStream,
encryptor, CryptoStreamMode.Write))
На выходе в строке имеем строковое представление кодировке Base64.5
Функция Deshifr аналогична рассмотренной функции.
2.2 Тестирование программы
В качестве примера зашифруем строку «Привет, мир!», паролем будет
слово «снег». Как видно из рисунка 2.1, программа работает нормально.
Рисунок 3.1 – Результат работы программы
Если в функцию Deshifr передать пароль отличный от пароля при
шифровании, то, как видно из рисунка 2.2, программа завершит свою работу с
ошибкой.
5
Pearson, Peter K. (June 1990), "Fast Hashing of Variable-Length Text Strings", Communications of the ACM.
32
Рисунок 2.2 – Результат работы программы
При отправке пустой строки, программа ничего не выводит, появляется
только пустое консольное приложение, показанное на рисунке 2.3.
Рисунок 2.3 – Результат работы программы
2.3 Программная реализация алгоритма на Delphi
Как видно выше, консольный проект – не очень удобен. Поэтому
рассмотрим программу, написанную в среде Delphi. Код программы приведен в
приложении Б.
При нажатии на кнопку «Open», открывается окно, позволяющее выбрать
текстовый файл. После выбора подсчитывается хеш текста, содержащегося в
файле. На рисунке 2.4 показан результат хеширования строки: «Привет, мир!»
33
Рисунок 2.4 – Окно программы
При нажатии на кнопку «Scan current DIR», считается хеш строки
введенной в окно программы. Например, введем «sha», и в последней строке
получим хеш, окно программы на рисунке 2.5
Рисунок 2.5 – окно программы
Кнопка «Stop» останавливает сканирование, «Save List As» - сохраняет хеш
в текстовый файл, а «Clear» - очищает окно.
С таким интерфейсом работать с программой удобнее, чем с консольным
приложением.
34
2.4 Выводы по главе 2
Программная реализация алгоритма SHA-1 не составляет большого труда.
С использованием встроенных библиотек, написание кода значительно
облегчается. Результат работы – консольное приложение.
35
3. ТИПОВЫЕ ПРИМЕРЫ ИСПОЛЬЗОВАНИЯ SHA-1
3.1 Описание приложений, использующих SHA-1
SHA-1 применяется в для построения кодов аутентификации, в системах
ЭЦП и в системах контроля версий.
Данная
функция
распространенной.
Она
из
всего
семейства
применяется
в
является
SHА
различных
самой
криптографических
приложениях и алгоритмах, которые широко распространены.
В протоколе удаленного рабочего стола Remote Desktop Protocol SHA-1
применяется для достижения целостности сообщений. В протоколе применяется
алгоритм генерации Message Authentication Code, который использует только
SHA-1.
Функция применяется для проверки целостности загружаемых данных в
пиринговом сетевом протоколе для обмена файлами через интернет – BitTorrent.
Хеш сегментов оригинальных файлов перечислены в словаре «info» torrentфайла. После получения сигнала каждая часть сегмента проверяется на
совпадение хеша. При неудачной проверке данные отбрасываются и
запрашиваются повторно.
S/MIME – стандарт для подписи и шифрования с помощью открытого
ключа в электронной почте. В нем, в качестве алгоритма хеширования, также
используется SHA-1.
В программе Mercurial функция применяется для идентификации ревизий.
Mercurial – кроссплатформенная распределенная система управления версиями,
которая разработана для эффективной работы с большими репозиториями кода.
В этой программе SHA-1 хеш представляет собой идентификатор набора
изменений, который состоит из букв «a, b, c, d, e, f» и цифр. Например,
«e1be1898f3747386c41c8a5c5776e87363f6d3d3».
Автоматически,
каждому
набору изменений присваивается подобный идентификатор набора изменений.
Он вычисляется на основе содержимого набора изменений, поэтому
соответствует во всех репозиториях одному и тому же набору изменений.
36
Коллизия, когда будет сгенерирован один и тот же хеш SHA-1 для двух разных
наборов, практически невозможна.
Также, в криптографическом протоколе SSL, подразумевающем более
безопасную связь, в качестве хеш-алгоритма используется SHA-1, который
создает 160-битное хеш-значение.
Git – это распределенная система управления версиями. В программе
вычисляется SHA-1 хеш для каждого объекта в репозитории. Он становится
именем файла, который содержит данный объект в директории git/objects. В
файловых системах, которые не используют деревья для, для оптимизации
работы, именем поддиректории становится первый бит хеша, остальные –
именем файла. Это снизит количество файлов в одной директории. SHA-1
хешами являются все ссылки на объекты, в том числе ссылки на один объект,
который находится в внутри другого объекта. В репозитории есть директория
refs, позволяющая задавать читаемые человеком имена для объектов git. Оба
вида ссылок в командах git – нижележащие SHA-1, и читаемые человеком из refs,
полностью взаимозаменяемые.
В IpSec, наборе протоколов, обеспечивающих защиту данных, которые
передаются по межсетевому протоколу IP, SHA-1 применяется в соединении
«точка-точка» в качестве алгоритма проверки целостности.
В популярной компьютерной программе PGP, которая также является
библиотекой функций, позволяющей выполнять цифровые подписи сообщений
и операции шифрования, в качестве алгоритма хеширования, для создания
электронной цифровой подписи используется SHA-1.
Также, данная функция применяется в SSH – сетевом протоколе
прикладного уровня, которое позволяет производить туннелирование TCPсоединений и удаленное управление операционной системой.
Компания Google отказалась от использования данной функции для
подписания
сертификатов
TLS.
К
тому
же
Яндекс.Почта
перестала
поддерживать устаревшие почтовые программы, которые используют SHA-1.
37
3.2 Выводы по главе 3
Многие компании постепенно отказываются от использования SHA-1. Тем
не менее, данная функция до сих пор используется во многих системах и
приложениях. Она является самой распространенной из всего семейства SHA.
38
ЗАКЛЮЧЕНИЕ
В ближайшее время прогресс в области развития средств вычислительной
техники, программного обеспечения и сетевых технологий даст толчок к
развитию средств обеспечения безопасности, что потребует во многом
пересмотреть
существующую
научную
парадигму
информационной
безопасности. Сегодня, наверное, никто не сможет с уверенностью назвать
точную цифру суммарных потерь от компьютерных преступлений, связанных с
несанкционированных доступом к информации. Это объясняется, прежде всего,
нежеланием пострадавших компаний обнародовать информацию о своих
потерях, а также тем, что не всегда потери от хищения информации можно точно
оценить в денежном эквиваленте.[28]
В наши дни трудно обойтись без хеширования. Оно используется везде,
где необходимо произвести быструю выборку данных. Появляются новые
методы хеширования, модифицируются старые алгоритмы. Однако, на основе
старых, более упрощенных алгоритмов легко понять саму суть хеширования,
программная реализация более простых алгоритмов поможет приобрести
необходимые навыки, для написания полноценных программ для хеширования.
Разумеется, методы и сферы применения хеширования не ограничиваются
тем, что представлено в этой работе. В результате выполнения курсовой работы
была разработана простая программа, реализующая алгоритм SHA-1.
39
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
1. Брюс Шнайер. Прикладная криптография. Протоколы, алгоритмы,
исходные тексты на языке Си. — М.: Триумф, 2002. — ISBN 5-89392-055-4.
2. Вирт Н., Алгоритмы + структуры данных = программы, М.: Мир, 1985.
3. Дональд Кнут. Искусство программирования. Том 3. Сортировка и
поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е
издание. — М.: «Вильямс», 2007. — С. 824. — ISBN 0-201-89685-0.
4. Ершов А.П., Избранные труды., Новосибирск: «Наука», 1994.
5. Керниган Б., Пайк Р., Практика программирования, СПб.: Невский
диалект, 2001.
6. Кормен Т., Лейзерсон Ч., Ривест Р., Алгоритмы: построение и анализ,
М.: МЦНМО, 2001
7. Никлаус Вирт. Алгоритмы и структуры данных. — М.: «Мир», 1989. —
ISBN 5-03-001045-9.
8. Нильс Фергюсон, Брюс Шнайер. Практическая криптография = Practical
Cryptography: Designing and Implementing Secure Cryptographic Systems. — М. :
Диалектика, 2004. — 432 с. — 3000 экз. — ISBN 5-8459-0733-0, ISBN 0-47122357-3.
9. Чмора А., Современная прикладная криптография., М.: Гелиос АРВ,
2001.
10.
Шень А, Программирование: теоремы и задачи. М.: МЦНМО, 1995.
11.
Buchholz W., IBM Systems J., 2 (1963), 86–111
12.
Djamal Belazzougui, Fabiano C. Botelho, Martin Dietzfelbinger (2009).
«Hash, displace, and compress».
13.
Finding Collisions in the Full SHA-1 (англ.). — Статья китайских
исследователей о взломе SHA-1
14.
Fundamenta Math. 46 (1958), 187-189
15.
Herbert Hellerman. Digital Computer System Principles. N.Y.: McGraw-
Hill, 1967, 424 pp.
40
16.
Litwin W., Proc. 6th International Conf. on Very Large Databases (1980),
212-223
17.
Morris R., Scatter Storage Techniques // Communications of the ACM,
1968. V.11, N1. Р.38—44.
18.
NIST Comments on Cryptanalytic Attacks on SHA-1 (англ.). —
Официальный комментарий NIST по поводу атак на SHA-1.
19.
NIST Hash Competition (англ.). — Конкурс на разработку SHA-3.
20.
Niels Ferguson, Bruce Schneier, and Tadayoshi Kohno, Cryptography
Engineering (англ.), John Wiley & Sons, 2010. ISBN 978-0-470-47424-2
21.
Pearson, Peter K. (June 1990), "Fast Hashing of Variable-Length Text
Strings", Communications of the ACM.
22.
Peterson W.W., Addressing for Random-Access Storage // IBM Journal
of Research and Development, 1957. V.1, N2. Р.130—146.
23.
R. Cichelli, Minimal Perfect Hashing Made Simple, Comm. ACM Vol. 23
No. 1, Jan. 1980.
24.
SHA-1 Collision Search Graz (англ.) — Исследовательский проект
технологического университета Граца.
25.
T. Gunji, E. Goto, J. Information Proc., 3 (1980), 1-12
26.
Wolfson, H.J. & Rigoutsos, I (1997). Geometric Hashing: An Overview.
IEEE Computational Science and Engineering.
27.
Брюс
Шнайер
о
взломе
SHA/
https://www.schneier.com/blog/archives/2005/02/cryptanalysis_o.html
28.
Взлом
SHA-1/
https://www.schneier.com/blog/archives/2005/02/sha1_broken.html
29.
Доклад
о
взломе
SHA1/
http://www.infosec.sdu.edu.cn/uploadfile/papers/Finding%20Collisions%20in%20the
%20Full%20SHA-1.pdf
30.
Обзор
SHA-1
от
Консорциума
https://www.w3.org/PICS/DSig/SHA1_1_0.html
41
Всемирной
паутины/
31.
Первый
способ
генерации
коллизий
для
SHA-1/
https://habrahabr.ru/post/322478/
32.
Последствия удачных атак на SHA-1/ https://www.heise.de
33.
Теория хеш-функций/ http://masteroid.ru/content/view/1322/49/
34.
Электронная цифровая подпись/ http://protect.htmlweb.ru/ecp.htm
35.
Finding SHA-1 Characteristics: General Results and Applications/
https://link.springer.com/chapter/10.1007%2F11935230_1.
36.
Miltersen,
Peter
Bro
Universal
Hashing./
http://www.webcitation.org/5hmOaVISI.
37.
RFC 3174/ https://tools.ietf.org/html/rfc3174
38.
Хеширование(TPReport)/http://www.optim.ru/cs/2000/4/bintree_htm/h
ash.asp
39.
Dynamichashing/http://www.cs.sfu.ca/CC/354/zaiane/material/notes/Cha
pter11/node20.html
40.
Hashing
-
Dynamic
Methods/http://www.ecst.csuchico.edu/~melody/courses/csci151_live/Dynamic_hash
_notes.htm
41.
R.
Cichelli,
Minimal
Perfect Hashing Made
Simple/http://planetmath.org/encyclopedia/Hashing.html
42.
Dr. Carlo Pescio
43.
Minimal
Perfect
Hashing/http://www.eptacom.net/pubblicazioni/pub_eng/mphash.html
44.
Хеширование/http://www2.ics.hawaii.edu/~richardy/project/hash/applet
45.
HashingAns /http://www.cs.uic.edu/~i201/HashingAns.pdf
46.
Шифрование
.html
строки
с
помощью
C#
и
SHA-1
/https://upread.ru/art.php?id=42
47.
SHA-!/http://mind-control.wikia.com/wiki/SHA-1
48.
SHA1 and other hash functions online generator /http://www.sha1-
online.com
42
49.
Против кого дружат Google, Mozilla и Microsoft? Или SHA-1 уходит
в прошлое /https://habrahabr.ru/company/first/blog/241603/
50.
Компьютеры
-
SHA-1
-
Описание
алгоритма
/http://www.chinapads.ru/c/s/sha-1_-_opisanie_algoritma
51.
SECURE
HASH
Алгоритмы
/http://solutionmes.wikidot.com/crypto-sha
43
(SHA-1,
SHA-2)
Приложение А
Код программы:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Security.Cryptography;
using System.IO;
namespace sha1
{
class Program
{
public static string Shifr(string ishText, string pass,
string sol = "abcdief", string cryptographicAlgorithm = "SHA1",
int passIter = 2, string initVec = "a8doSuDitOz1hZe#",
int keySize = 256)
{
if (string.IsNullOrEmpty(ishText))
return "";
byte[] initVecB = Encoding.ASCII.GetBytes(initVec);
byte[] solB = Encoding.ASCII.GetBytes(sol);
byte[] ishTextB = Encoding.UTF8.GetBytes(ishText);
PasswordDeriveBytes derivPass = new PasswordDeriveBytes(pass, solB,
cryptographicAlgorithm, passIter);
44
byte[] keyBytes = derivPass.GetBytes(keySize / 8);
RijndaelManaged symmK = new RijndaelManaged();
symmK.Mode = CipherMode.CBC;
byte[] cipherTextBytes = null;
using (ICryptoTransform encryptor = symmK.CreateEncryptor(keyBytes,
initVecB))
{
using (MemoryStream memStream = new MemoryStream())
{
using (CryptoStream cryptoStream = new CryptoStream(memStream,
encryptor, CryptoStreamMode.Write))
{
cryptoStream.Write(ishTextB, 0, ishTextB.Length);
cryptoStream.FlushFinalBlock();
cipherTextBytes = memStream.ToArray();
memStream.Close();
cryptoStream.Close();
}
}
}
symmK.Clear();
return Convert.ToBase64String(cipherTextBytes);
}
public static string DeShifr(string ciphText, string pass,
string sol = "abcdief", string cryptographicAlgorithm = "SHA1",
45
int passIter = 2, string initVec = "a8doSuDitOz1hZe#",
int keySize = 256)
{
if (string.IsNullOrEmpty(ciphText))
return "";
byte[] initVecB = Encoding.ASCII.GetBytes(initVec);
byte[] solB = Encoding.ASCII.GetBytes(sol);
byte[] cipherTextBytes = Convert.FromBase64String(ciphText);
PasswordDeriveBytes derivPass = new PasswordDeriveBytes(pass, solB,
cryptographicAlgorithm, passIter);
byte[] keyBytes = derivPass.GetBytes(keySize / 8);
RijndaelManaged symmK = new RijndaelManaged();
symmK.Mode = CipherMode.CBC;
byte[] plainTextBytes = new byte[cipherTextBytes.Length];
int byteCount = 0;
using (ICryptoTransform decryptor = symmK.CreateDecryptor(keyBytes,
initVecB))
{
using (MemoryStream mSt = new MemoryStream(cipherTextBytes))
{
using (CryptoStream cryptoStream = new CryptoStream(mSt, decryptor,
CryptoStreamMode.Read))
{
byteCount
=
cryptoStream.Read(plainTextBytes,
plainTextBytes.Length);
46
0,
mSt.Close();
cryptoStream.Close();
}
}
}
symmK.Clear();
return Encoding.UTF8.GetString(plainTextBytes, 0, byteCount);
}
static void Main(string[] args)
{
String gg = Shifr("Привет, мир!", "снег");
String gg2 = DeShifr(gg, "снег");
Console.WriteLine(gg);
Console.WriteLine(gg2);
Console.ReadKey();
}
}
}
47
Приложение Б
Код программы:
unit main;
interface
uses
Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, StdCtrls,
Dialogs;
type
TForm1 = class(TForm)
Memo1: TMemo;
Button1: TButton;
Button2: TButton;
Button3: TButton;
Button4: TButton;
CheckBox1: TCheckBox;
CheckBox2: TCheckBox;
CheckBox3: TCheckBox;
BStop: TButton;
SaveDialog1: TSaveDialog;
OpenDialog1: TOpenDialog;
procedure FormCreate(Sender: TObject);
procedure Button1Click(Sender: TObject);
procedure Button2Click(Sender: TObject);
procedure FormResize(Sender: TObject);
procedure Button3Click(Sender: TObject);
procedure Button4Click(Sender: TObject);
procedure BStopClick(Sender: TObject);
private { Private declarations }
public { Public declarations }
48
end;
var
Form1: TForm1;
const
HC0=$67452301;
HC1=$EFCDAB89;
HC2=$98BADCFE;
HC3=$10325476;
HC4=$C3D2E1F0;
K1=$5A827999;
K2=$6ED9EBA1;
K3=$8F1BBCDC;
K4=$CA62C1D6;
var H0,H1,H2,H3,H4:integer; Hout:string;
StopScan:boolean;
implementation
{$R *.DFM}
function rol(const x:integer;const y:byte):integer ;
begin
asm
mov eax,x
mov cl, y
rol eax,cl
mov x, eax
end;
result:=x;
end;
49
procedure INIT;
begin
H0:=HC0;//$67452301;
H1:=HC1;//$EFCDAB89;
H2:=HC2;//$98BADCFE;
H3:=HC3;//$10325476;
H4:=HC4;//$C3D2E1F0;
Hout:='';
end;
function PADDING(s:string;FS:integer):string;
var size,i:integer;
begin
size:=Length(s)*8;
s:=s+char(128);
while (Length(s) mod 64) <>0 do s:=s+#0;
IF ((size) >= 448) then
IF ((size mod 512) >= 448) then
begin
s:=s+#0;
while (Length(s) mod 64) <>0 do s:=s+#0;
end;
i:=Length(s);size:=FS*8;
while size > 0 do
begin
s[i]:=char(byte(size));
size:=size shr 8;
50
i:=i-1;
end;
Result:=s;
end;
Procedure START(const S_IN:string);
var A,B,C,D,E,TEMP:integer; t,i:byte; W:array[0..79] of integer;
begin
t:=1;
for i:=1 to ((Length(S_IN)) div 4) do
begin
W[i1]:=ord(S_IN[t])*256*256*256+ord(S_IN[t+1])*256*256+ord(S_IN[t+2])
*256+ord(S_IN[t+3]);
W[i-1]:=(ord(S_IN[t]) shl 24) +(ord(S_IN[t+1]) shl 16)+(ord(S_IN[t+2]) shl
8)+ord(S_IN[t+3]);
t:=t+4;
end;
For t:=16 to 79 do W[t]:=ROL(W[t-3] XOR W[t-8] XOR W[t-14] XOR W[t16],1);
A:=H0;B:=H1;C:=H2;D:=H3;E:=H4;
{ for t:=0 to 79 do
begin
if (t>=0) AND (t<=19) then TEMP:=ROL(A,5)+((B AND C) OR ((NOT
B) AND D))
+E+K1+W[t];
if (t>=20) AND (t<=39) then TEMP:=ROL(A,5)+(B XOR C XOR D)
+E+K2+W[t];
if (t>=40) AND (t<=59) then TEMP:=ROL(A,5)+((B AND C) OR (B AND
D) OR (C AND D))+E+K3+W[t];
51
if (t>=60) AND (t<=79) then TEMP:=ROL(A,5)+(B XOR C XOR D)
+E+K4+W[t];
E:=D; D:=C; C:=ROL(B,30); B:=A; A:=TEMP;
end;
}
for t:=0 to 19 do
begin
TEMP:=ROL(A,5)+((B AND C) OR ((NOT B) AND D))
+E+K1+W[t];
E:=D; D:=C; C:=ROL(B,30); B:=A; A:=TEMP;
end;
for t:=20 to 39 do
begin
TEMP:=ROL(A,5)+(B XOR C XOR D)
+E+K2+W[t];
E:=D; D:=C; C:=ROL(B,30); B:=A; A:=TEMP;
end;
for t:=40 to 59 do
begin
TEMP:=ROL(A,5)+((B AND C) OR (B AND D) OR (C AND
D))+E+K3+W[t];
E:=D; D:=C; C:=ROL(B,30); B:=A; A:=TEMP;
end;
for t:=60 to 79 do
begin
TEMP:=ROL(A,5)+(B XOR C XOR D)
+E+K4+W[t];
E:=D; D:=C; C:=ROL(B,30); B:=A; A:=TEMP;
end;
H0:=A+H0; H1:=B+H1; H2:=C+H2; H3:=D+H3; H4:=E+H4;
//Form1.memo1.Lines.Add(inttohex(H0,8)+'
'+inttohex(H2,8)+' '+inttohex(H3,8)+' '+inttohex(H4,8));
end;
52
'+inttohex(H1,8)+'
procedure TForm1.FormCreate(Sender: TObject);
begin
WindowState:=wsMaximized;
Form1.Memo1.Clear;
Button2.Enabled:=false ;
Form1.SaveDialog1.Filter := 'Text Files (*.txt)|*.TXT|All Files (*.*)|*.*';
CheckBox1.Checked:=true;
CheckBox2.Checked:=true;
Application.Title:='SHA-1';
Caption:='SHA-1';
end;
procedure Work(Z:string);
var s,s1:string;
i,L,FS:integer;
F:file; n:integer; Buf: array[1..65536] of
char;
begin
Application.ProcessMessages;
IF StopScan then exit;
s:='';
AssignFile(F,Z);
FileMode := FmOpenRead;
Reset(F,1);
FS:=FileSize(F);
INIT;
repeat
BlockRead(F,Buf,sizeOf(Buf),n);
SetLength(s1,n);
For i:=1 to n do s1[i]:=Buf[i];
// s:=s+s1;
53
s:=s1;
L:=length(s1);
IF ((L<65536) and (L>0)) then
begin
s1:= PADDING(s,FS) ;
i:=1;
L:=length(s1);
while i<L do
begin
START(copy(s1,i,64));
i:=i+64;
end;
end;
IF L =65536 then begin
i:=1;
L:=length(s1);
while i<L do
begin
START(copy(s1,i,64));
i:=i+64;
end;
end;
until n=0;
CloseFile(F);
{
INIT;
s:=PADDING(s,FS) ;
L:=length(s);
54
i:=1;
while i<L do
begin
START(copy(s,i,64));
i:=i+64;
end;
}
Hout:=inttohex(H0,8)+'
'+inttohex(H1,8)+'
'+inttohex(H2,8)+'
'+inttohex(H3,8)+' '+inttohex(H4,8);
s1:=Hout;
If (Form1.CheckBox1.Checked AND Form1.CheckBox2.Checked) then
Form1.memo1.Lines.Add(s1+'
'+inttostr(FS)+'
'+ExtractFileName(Z));
If NOT ((Form1.CheckBox1.Checked AND Form1.CheckBox2.Checked))
then
Form1.memo1.Lines.Add(s1);
If (Form1.CheckBox1.Checked AND NOT Form1.CheckBox2.Checked)
then
Form1.memo1.Lines.Add(s1+'
'+inttostr(FS));
If (NOT Form1.CheckBox1.Checked AND Form1.CheckBox2.Checked)
then
Form1.memo1.Lines.Add(s1+'
'+ExtractFileName(Z));
// abc.....opq = 84983E44 1C3BD26E BAAE4AA1 F95129E5 E54670F1
//
abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopqW
=
39958831d7dd0a53e9bfba578cdf45e5ec542e8c
//abc = A9993E36 4706816A BA3E2571 7850C26C 9CD0D89D;
//abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnop = 47B17281
0795699F E739197D 1A1F5960 700242F1
end;
55
procedure TForm1.Button1Click(Sender: TObject);
begin
if Form1.OpenDialog1.Execute then
begin
StopScan:=false;
Work(OpenDialog1.FileName);
Button2.Enabled:=true;
end;
end;
procedure TForm1.FormResize(Sender: TObject);
begin
Memo1.Height:=Height-70;
end;
procedure TForm1.Button3Click(Sender: TObject);
begin
If SaveDialog1.Execute then
begin
If FileExists(SaveDialog1.FileName) then
IF
MessageDlg('File'+#13+SaveDialog1.FileName+#13+'already
exists!'
+#13+#13+'Overwrite (Yes/No) ?',mtWarning, [mbYes, mbNo], 0) =
mrNo then exit;
Memo1.Lines.SaveToFile(SaveDialog1.FileName);
end;
end;
procedure TForm1.Button4Click(Sender: TObject);
56
begin
Form1.Memo1.Clear;
end;
57