Информация для шпиона: Шифрование информации

Информация для шпиона: Шифрование информации

Хэш-функция

Преобразование массива входных данных произвольной длины в (выходную) битовую строку установленной длины, выполняемое определённым алгоритмом.

Для чего это нужно? К примеру у вас есть два набора данных, а вам необходимо быстро сравнить их на равенство, то хэш-функция может сделать это за вас, если у двух наборов данных хэши разные, то они гарантировано разные, а в случае равенства хэшей — данные скорее всего одинаковы.

Чаще всего хэш-функции используются для проверки уникальности пароля, файла, строки и тд. К примеру, скачивая файл из интернета, мы часто видим рядом с ним строку вида b10a8db164e0754105b7a99be72e3fe5 — это и есть хэш, прогнав этот файл через алгоритм MD5 вы получите такую строку, и, если хэши равны, можно с большой вероятностью утверждать что этот файл действительно подлинный.

Например: файлы записей итогового собеседования по русскому языку в 9 классе передовались вместе с хэшами для контроля подлинности

MD5

MD5 — один из серии алгоритмов по построению дайджеста сообщения, разработанный профессором Рональдом Л. Ривестом из Массачусетского технологического института. Был разработан в 1991 году как более надёжный вариант предыдущего алгоритма MD4.

Алгоритм состоит из пяти шагов:

1)Append Padding Bits (Выравнивание потока)
В исходную строку дописывают единичный байт 0х80, а затем дописывают нулевые биты, до тех пор, пока длина сообщения не будет сравнима с 448 по модулю 512. То есть дописываем нули до тех пор, пока длина нового сообщения не будет равна [длина] = (512*N+448),
где N — любое натуральное число, такое, что это выражение будет наиболее близко к длине блока.
2)Append Length (Добавление длины сообщения)
Далее в сообщение дописывается 64-битное представление длины исходного сообщения.
3)Initialize MD Buffer (Инициализация буфера)
На этом шаге инициализируется буффер
word A: 01 23 45 67
word B: 89 ab cd ef
word C: fe dc ba 98
word D: 76 54 32 10
Как можно заметить буффер состоит из четырех констант, предназначенный для сбора хэша.
4)Process Message in 16-Word Blocks (Вычисление в цикле)
На четвертом шаге в первую очередь определяется 4 вспомогательные логические функции, которые преобразуют входные 32-битные слова, в, как ни странно, в 32-битные выходные.
F(X,Y,Z) = XY v not(X) Z
G(X,Y,Z) = XZ v Y not(Z)
H(X,Y,Z) = X xor Y xor Z
I(X,Y,Z) = Y xor (X v not(Z))
Также на этом шаге реализуется так называемый «белый шум» — усиление алгоритма, состоящее 64 элементного массива, содержащего псевдослучайные числа, зависимые от синуса числа i:
T[i]=4,294,967,296*abs(sin(i))
Далее начинается «магия». Копируем каждый 16-битный блок в массив X[16] и производим манипуляции:
AA = A
BB = B
CC = C
DD = D
Затем происходят «чудесные» преобразования-раунды, которых всего будет 4. Каждый раунд состоит из 16 элементарных преобразований, которые в общем виде можно представить в виде [abcd k s i], которое, в свою очередь, можно представить как A = B + ((A + F(B,C,D) + X[k] + T[i]) <<< s), где
A, B, C, D — регистры
F(B,C,D) — одна из логических функций
X[k] — k-тый элемент 16-битного блока.
T[i] — i-тый элемент таблицы «белого шума»
<<< s — операция циклического сдвига на s позиций влево.
Приводить все раунды не имеет смысла, все их можно посмотреть тут
Ну и в конце суммируем результаты вычислений:
A = A + AA
B = B + BB
C = C + CC
D = D + DD
5) Output
Выводя побайтово буффер ABCD начиная с A и заканчивая D получим наш хэш.

Надежность

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

Также у MD5, как у любой хэш-функции, существует такое понятие как коллизии — это получение одинаковых хэшей для разных исходных строк. В 1996 году Ганс Доббертин нашёл псевдоколлизии в MD5, используя определённый инициализирующий буффер (ABCD). Также в 2004 году китайские исследователи Ван Сяоюнь, Фен Дэнгуо, Лай Сюэцзя и Юй Хунбо объявили об обнаруженной ими уязвимости в алгоритме, позволяющей за небольшое время (1 час на кластере IBM p690) находить коллизии. Однако в 2006 году чешский исследователь Властимил Клима опубликовал алгоритм, позволяющий находить коллизии на обычном компьютере с любым начальным вектором (A,B,C,D) при помощи метода, названного им «туннелирование».

Заключение

Надо признать, что MD5-хэши стали неотъемлемой частью нашей жизни. Они вездесущи. Их используют в качестве алгоритмов для хэширования паролей как в программном обеспечении, так и на веб-ресурсах. Они не зависят ни от платформы, ни от ОС, на которых исполняются. Векторы атак также довольно широки: от банкоматов до цифровых подписей, от авторизации клиент-сервер и до целостности передаваемых по сети файлов. Являясь быстрыми и менее криптостойкими, 128-битные алгоритмы хэширования принесут еще немало бед.

Подготовил: Вишняков Стас, 7 класс

Похожие статьи

Комментарии:

Leave a reply

Your email address will not be published. Required fields are marked *

три × три =

Этот сайт использует Akismet для борьбы со спамом. Узнайте как обрабатываются ваши данные комментариев.

Информационная поддержка

Яндекс.Метрика

Рейтинг@Mail.ru