Хеширование и передача данных доклад

Обновлено: 04.07.2024

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

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

Что такое хеш (хэш, hash)?

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

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

В предыдущем примере речь шла о применении хэш-алгоритма для слова из 4 букв. Но с тем же успехом можно вставить слово из 1000 букв — все равно после обработки данных на выходе получится значение из 40 символов. Аналогичная ситуация будет и при обработке полного собрания сочинений Льва Толстого.

Криптостойкость функций хеширования

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

Проблемы хэшей

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

Если S = hash (x), то, в идеале, нахождение x должно быть практически невозможным.

Алгоритм MD5 и его подверженность взлому

Атака дня рождения

Если поместить 23 человека в одну комнату, можно дать 50%-ную вероятность того, что у двух человек день рождения будет в один и тот же день. Если же количество людей довести до 70-ти, вероятность совпадения по дню рождения приблизится к 99,9 %. Есть и другая интерпретация: если голубям дать возможность сесть в коробки, при условии, что число коробок меньше числа голубей, окажется, что хотя бы в одной из коробок находится более одного голубя.

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

Когда разговор идет о сопротивлении коллизиям, то алгоритм MD5 действительно очень слаб. Настолько слаб, что даже бытовой Pentium 2,4 ГГц сможет вычислить искусственные хеш-коллизии, затратив на это чуть более нескольких секунд. Всё это в ранние годы стало причиной утечки большого количества предварительных MD5-прообразов.

SHA1, SHA2, SHA3

Что в будущем?

Вне зависимости от того, какие технологии шифрования и криптографические новинки будут использоваться в этом направлении, все сводится к решению одной из двух задач: 1) увеличению сложности внутренних операций хэширования; 2) увеличению длины hash-выхода данных с расчетом на то, что вычислительные мощности атакующих не смогут эффективно вычислять коллизию.

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

Рубрика	Программирование, компьютеры и кибернетика
Вид	курсовая работа
Язык	русский
Дата добавления	13.06.2014
Размер файла	1,2 M

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

1. Хеширование
1.1 Определение хеширования
1.2 История
1.3 Разрешение коллизий
2. Описание задачи и исходных данных
2.1 Постановка задачи
2.2 Описание исходных данных
2.3 Анализ поставленной задачи
3. Описание разработанного Приложения
3.1 Описание программных модулей
3.2 Описание работы методов
3.3 Структура программного продукта
4. Описание интерфейса
Заключение
Список использованных источников
Приложение А Листинг программы

Введение

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

Разрабатываемый программный продукт отлично подойдёт для организаций, которые в своей профессиональной среде сталкиваются с большим количеством информации.

Исходя из задач, актуальностью создаваемой программы является сокращение времени работы, рациональное распределение времени, что позволяет выполнить большой объём работы за более короткие сроки.

хеширование алгоритм справочный информационный программирование

1. Хеширование

1.1 Определение хеширования

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

Существует множество алгоритмов хеширования с различными свойствами (разрядность, вычислительная сложность, криптостойкость и т. п.). Выбор той или иной хеш-функции определяется спецификой решаемой задачи. Простейшими примерами хеш-функций могут служить контрольная сумма или CRC.

1.2 История

Дональд Кнут относит первую систематическую идею хеширования к сотруднику IBM Хансу Петеру Луну, предложившему хеш-кодирование в январе 1953 года.

Первой серьёзной работой, связанной с поиском в больших файлах, была статья Уэсли Питерсона в IBM Journal of Research and Development 1957 года, в которой он определил открытую адресацию, а также указал на ухудшение производительности при удалении. Спустя шесть лет была опубликована работа Вернера Бухгольца, в которой проведено обширное исследование хеш-функций. В течение нескольких последующих лет хеширование широко использовалось, однако не было опубликовано никаких значимых работ.

1.3 Разрешение коллизий

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

Рисунок 1.1 -- Пример коллизии

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

2. Описание задачи и исходных данных

2.1 Постановка задачи

1) чтение из текстового файла информации об объектах класса согласно варианту (таблица 2.1). Количество записей не менее 50. Предусмотреть наличие в файле не корректных записей, которые в процессе работы программы не будут обрабатываться. Использовать регулярные выражения (предусмотреть проверку по возможности всех полей);

2) вывод исходных данных в виде таблицы;

3) визуализация хеш-таблицы или бинарного дерева;

4) поиск информации по заданному ключу или способу обхода;

5) редактирование исходных данных (вставка, удаление, замена) с внесением соответствующих изменений в хеш-таблицу или бинарное дерево поиска. Использовать регулярные выражения;

6) вывод справочной информации о программном продукте и об авторе;

7) демонстрация перегруженных операторов;

8) поиск максимального объекта.

2.2 Описание исходных данных

Исходными данными задачи являются:

1) название предметной области, а точнее название класса и его основные поля указаны в таблице 2.1, которое выбирается согласно варианту выданному преподавателем;

2) текстовый файл с информацией об объектах класса согласно варианту. Количество записей не менее 50. Предусмотреть наличие в файле не корректных записей, которые в процессе работы программы не будут обрабатываться;

3) хеш-таблица с использованием подходящей функции хеширования (алгоритм разрешения конфликтов и ключ указаны в таблице 2.2).

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

Шифрование данных

Шифрование - обратимое преобразование информации в целях сокрытия сведений от несанкционированного круга лиц.

Шифрование происходит на основе алгоритмов, известных передающей и принимающей сторонам. Процесс преобразования открытой информации в закрытый вид называется шифрование . Обратный процесс преобразования закрытой (зашифрованной) информации в открытый вид называется дешифрование .

Взламывание шифра с получением алгоритма шифрования и ключа шифрования (при наличии) называется криптоанализ .

Алгоритм шифрования может использовать ключ шифрования или обходиться без него. Ключи шифрования бывают открытыми и закрытыми .

Шифрование применяется для реализации средств криптографической защиты информации ( СКЗИ ) - средства защиты хранимой информации и средства защиты передаваемой информации.

Узнать подробнее о криптографии можно в ответах Яндекс.Знатоки по вопросу " Что такое криптография? "

Хеширование данных

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

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

Известными алгоритмами хеширования являются MD5, SHA-1 и SHA-2.

Основные принципы хеширования :

при хешировании одинаковых данных получается одинаковое значение хеша (хеш-кода);
разные данные преобразуются в разные хеш-коды (хеш-суммы);
криптостойкость хеш-функции заключается в стойкости к восстановлению хешируемых данных и стойкости к коллизиям преобразования.

Одним из самых простых применений хеширования является хранение паролей (считается более защищённым способом, чем хранение паролей в явном виде).

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

Кодирование данных

Код - это система условных обозначений или сигналов.

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

Самым простым примером кодирования данных является текст. Кодирование может производиться рукописным или машинописным способом на определённом языке речи. Далее можно произвести перекодирование текста документа способом перевода его на другой язык.

Кодированием является написание программы для ЭВМ или перевод программы на другой язык программирования.

Элементами кодируемой информации могут быть:

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

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

Кроме языка речи и программирования известными кодовыми системами являются: азбука Морзе , код Бодо , компьютерная кодировка символов ASCII и Unicodе , шрифты, системы штрих-кодов и др.

Системой кодов можно назвать распространённые устойчивые традиции, обряды, танцевальные системы, принятые в разных народностях.

Дополнительные материалы по теме этой статьи:

24 августа 2019 года.

автор: юрист Демешин Сергей Владимирович.

Участвуйте в обсуждении , пройдите опрос об интересных темах будущих публикаций (ссылка опроса в описании канала, также в описании указаны правила комментирования публикаций).

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

Криптографические хеш-функции — незаменимый и повсеместно распространенный инструмент, используемый для выполнения целого ряда задач, включая аутентификацию, проверку целостности данных, защиту файлов и даже обнаружение зловредного ПО. Существует масса алгоритмов хеширования, отличающихся криптостойкостью, сложностью, разрядностью и другими свойствами. Считается, что идея хеширования принадлежит сотруднику IBM, появилась около 50 лет назад и с тех пор не претерпела принципиальных изменений. Зато в наши дни хеширование обрело массу новых свойств и используется в очень многих областях информационных технологий.

Что такое хеш?

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

Как работает хеш?

Например, мое имя — Brian — после преобразования хеш-функцией SHA-1 (одной из самых распространенных наряду с MD5 и SHA-2) при помощи онлайн-генератора будет выглядеть так: 75c450c3f963befb912ee79f0b63e563652780f0. Как вам скажет, наверное, любой другой Брайан, данное имя нередко пишут с ошибкой, что в итоге превращает его в слово brain (мозг). Это настолько частая опечатка, что однажды я даже получил настоящие водительские права, на которых вместо моего имени красовалось Brain Donohue. Впрочем, это уже другая история. Так вот, если снова воспользоваться алгоритмом SHA-1, то слово Brain трансформируется в строку 97fb724268c2de1e6432d3816239463a6aaf8450. Как видите, результаты значительно отличаются друг от друга, даже несмотря на то, что разница между моим именем и названием органа центральной нервной системы заключается лишь в последовательности написания двух гласных. Более того, если я преобразую тем же алгоритмом собственное имя, но написанное уже со строчной буквы, то результат все равно не будет иметь ничего общего с двумя предыдущими: 760e7dab2836853c63805033e514668301fa9c47.

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

Вот как это выглядит, если изобразить все вышесказанное в виде схемы:

Для чего используется хеш?

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

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

Еще один пример, покруче. Не так давно по тематическим сайтам прокатилась новость о том, что популярный облачный сервис Dropbox заблокировал одного из своих пользователей за распространение контента, защищенного авторскими правами. Герой истории тут же написал об этом в твиттере, запустив волну негодования среди пользователей сервиса, ринувшихся обвинять Dropbox в том, что он якобы позволяет себе просматривать содержимое клиентских аккаунтов, хотя не имеет права этого делать.

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

Как при помощи хеша ловить вирусы?

Криптографические хеш-функции также могут использоваться для защиты от фальсификации передаваемой информации. Иными словами, вы можете удостовериться в том, что файл по пути куда-либо не претерпел никаких изменений, сравнив его хеши, снятые непосредственно до отправки и сразу после получения. Если данные были изменены даже всего на 1 байт, хеш-коды будут отличаться, как мы уже убедились в самом начале статьи. Недостаток такого подхода лишь в том, что криптографическое хеширование требует больше вычислительных мощностей или времени на вычисление, чем алгоритмы с отсутствием криптостойкости. Зато они в разы надежнее.

Кстати, в повседневной жизни мы, сами того не подозревая, иногда пользуемся простейшими хешами. Например, представьте, что вы совершаете переезд и упаковали все вещи по коробкам и ящикам. Погрузив их в грузовик, вы фиксируете количество багажных мест (то есть, по сути, количество коробок) и запоминаете это значение. По окончании выгрузки на новом месте, вместо того чтобы проверять наличие каждой коробки по списку, достаточно будет просто пересчитать их и сравнить получившееся значение с тем, что вы запомнили раньше. Если значения совпали, значит, ни одна коробка не потерялась.

Читайте также: