информатика

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

Например, имя Brian — после преобразования хеш-функцией SHA-1 будет выглядеть так: 75c450c3f963befb912ee79f0b63e563652780f0.

Если снова воспользоваться алгоритмом SHA-1, то слово Brain(мозг) трансформируется в строку 97fb724268c2de1e6432d3816239463a6aaf8450.

Как видите, результаты значительно отличаются друг от друга, даже несмотря на то, что разница между моим именем и названием органа центральной нервной системы заключается лишь в последовательности написания двух гласных. Более того, если преобразовать тем же алгоритмом имя, но написанное уже со строчной буквы, то результат все равно не будет иметь ничего общего с двумя предыдущими: 760e7dab2836853c63805033e514668301fa9c47.

Общее у них все же есть: каждая строка имеет длину ровно 40 символов.

Казалось бы, ничего удивительного, ведь все введенные слова также имели одинаковую длину — 5 букв. Однако, если захешировать весь предыдущий абзац целиком, то все равно получится последовательность, состоящая ровно из 40 символов: c5e7346089419bb4ab47aaa61ef3755d122826e2. То есть 1128 символов, включая пробелы, были ужаты до строки той же длины, что и пятибуквенное слово. То же самое произойдет даже с полным собранием сочинений Уильяма Шекспира: на выходе вы получите строку из 40 букв и цифр. При всем этом не может существовать двух разных массивов данных, которые преобразовывались бы в одинаковый хеш.

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

Требования, которым хеш в базе должен удовлетворять:

 - стойкость к атакам перебора (прямой перебор и перебор по словарю);

 - невозможность поиска одинаковых паролей разных пользователей по хешам.

Для выполнения первого требования нужно использовать стойкие хеш-функции.

Для выполнения второго — к паролю перед хешированием добавляется случайная строка (соль). Таким образом, у двух пользователей с паролем «123456» будут разные соли «соль1» и «соль2», а соответственно и хеш-функции от «123456соль1» и «123456соль2» в базе тоже будут разные.

И соль и сам хеш хранятся в базе данных. То есть получив доступ к СУБД, злоумышленник получает и значения хешей и соли.

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

Задание:

1.      Хешировать свой пароль на сайте: http://www.hashemall.com/

2.      Использовать взломщик паролей на сайте: https://crackstation.net/

3.      Разобрать понятия имитовставка и аппаратное хэширование паролей.

Метод деления. Исходными данными являются – некоторый целый ключ key и размер таблицы m. Результатом данной функции является остаток от деления этого ключа на размер таблицы. Общий вид функции:

int h(int key, int m) {

return key % m; // Значения

}

Для m = 10 хеш-функция возвращает младшую цифру ключа.

Аддитивный метод, в котором ключом является символьная строка. В хеш-функции строка преобразуется в целое суммированием всех символов и возвращается остаток от деления на m (обычно размер таблицы m = 256).

int h(char *key, int m) {

int s = 0;

while(*key)

s += *key++;

return s % m;

}

Коллизии возникают в строках, состоящих из одинакового набора символов, например, abc и cab.

Метод середины квадрата, в котором ключ возводится в квадрат (умножается сам на себя) и в качестве индекса используются несколько средних цифр полученного значения.

Например, ключом является целое 32-битное число, а хеш-функция возвращает средние 10 бит его квадрата:

int h(int key) {

key *= key;

key >>= 11; // Отбрасываем 11 младших бит

return key % 1024; // Возвращаем 10 младших бит

}

В мультипликативном методе дополнительно используется случайное действительное число r из интервала [0,1), тогда дробная часть произведения r*key будет находиться в интервале [0,1]. Если это произведение умножить на размер таблицы m, то целая часть полученного произведения даст значение в диапазоне от 0 до m–1.

int h(int key, int m) {

double r = key * rnd();

r = r – (int)r; // Выделили дробную часть

return r * m;

}

ЭЦП — это реквизит электронного документа. Это последовательность битов, вычисленная уникально для каждого конкретного сообщения. Подпись может быть вычислена как с применением секретного ключа, так и без него. Без секретного ключа подпись представляет собой просто код, который может доказать, что документ не был изменен. С использованием секретного ключа подпись докажет целостность сообщения, позволит убедиться в его подлинности и аутентифицировать источник.

Скачано с www.znanio.ru