Хэш сумма что это

Хэширование в Blockchain.Что такое хэш сумма.

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

Слово хеш происходит от английского «hash», одно из значений которого трактуется как путаница или мешанина. Собственно, это довольно полно описывает реальное значение этого термина. Часто еще про такой процесс говорят «хеширование», что опять же является производным от английского hashing (рубить, крошить, спутывать и т.п.). Появился этот термин в середине прошлого века среди людей занимающихся обработках массивов данных и Хеш-функция позволяла привести любой массив данных к числу заданной длины. Проще всего хеширование представить как шифр. Берется какой-нибудь текст, шифруется по определенной системе, где на выходе получается билиберда. Эту билиберду можно превратить обратно в текст, если вы знаете, как именно билиберду шифровали. Например, берем цифру 5, шифруем ее, например умножаем на 4, и получаем 20. Если разделить 20 на 4, получим исходную информацию — 5.В данном случае ключем к расшифровке является цифра 4 Буквенные шифры работают сложнее. И чтобы зашифровать текст Можно каждой букве присвоить свой номер, и таким образом зашифровать текст в виде набора чисел. Также можно сдвинуть алфавит на два символа влево и получить трудночитаемый набор букв. Или же записать текст азбукой Морзе и получить последовательность точек и тире. Кстати, азбука Морзе вам ничего не напоминает? Если Морзе кодировал буквы и цифры последовательностью точек и тире, то наши компьютеры кодируют все единицами и нулями. Одно значение (единица или ноль) называется битом. Если присвоить каждой букве латинского алфавита порядковый номер, то для передачи одной буквы понадобиться всего 4 бита. Учитывая пробелы, прописные и заглавные буквы и разные символы, получается 7 бит или один байт с нулем в начале. Так Почему же для передачи и хранения цифровых данных выбрали аналог морзянки, а не что-то вычурное? Потому что компьютеры работают на электричестве. Если по кабелю не течет ток — компьютер регистрирует ноль. Если течет — единицу. Все просто. А при мощности современного интернета, по кабелям можно надежно передавать 100 миллионов бит в секунду и даже больше Но, что будет, если компьютер на мгновение подвиснет и пропустит несколько единичек и нулей? Информация, которую он примет после подвисания, может оказаться нечитаемой. Для расшифровки битов в понятные нам буквы нужен полный и последовательный набор битов, иначе вместо оригинального текста компьютер получит нечитаемый массив из битов.

Что такое хэш сумма.

Давайте еще рассмотрим пример хеширования посложнее.Для этого сначала разберем один вопрос, а именно В чем проблема способа с подсчетом количества бит как мы с вами рассмотрели выше? А проблема в том, что под 77 бит можно подогнать и «Lorem ipsum», и «Здравствуй!» и любые другие одинадцать символов. Простой подсчет количества бит информации не позволяет проверить полученный текст на полное соответствие оригиналу. Совпадение хеш-суммы разных файлов называется коллизией и Плохой алгоритм хеширования дает большое количество коллизий. Наш алгоритм подсчета количества бит — плохой. Значит, хеш-сумму надо считать иначе. Хороший алгоритм в практическом применении не дает коллизий вообще. Это значит, что любому тексту, картинке или файлу можно присвоить уникальный идентификатор (то есть, хеш-сумму), который рассчитывается исходя из самого файла. И желательно, чтобы хеш-сумма была небольшой, и одинакового размера для всех файлов, чтобы уменьшить риск потерять биты самой хеш-суммы во время ее передачи. Алгоритмов много, но нас пока интересует лишь один — SHA-256, который используется в Биткоине и сотнях других криптовалют. Теперь рассмотрим алгоритм SHA-1, ведь так будет проще понять алгоритм SHA-256 SHA-1 придумали в Агенстве Национальной Безопасности США, небезызвестном NSA. Алгоритм предназначался для цифровой подписи документов и проверки их подлинности. Получатель принимал документ и подпись в виде хеш-суммы оригинала. Затем самостоятельно считал хеш-сумму принятого документа и сравнивал ее с полученной подписью. Если хеш-суммы совпадают — значит полученный документ полностью идентичен оригинальному. SHA-1 работает так. Исходный файл разбивается на блоки по 512 бит в каждом. Затем алгоритм определяет четыре ключа, которые не меняются в процессе хеширования, и каждый из ключей весит по 32 бита и необходим для проведения хеширования. Определяются пять случайных переменных, по длине равных ключам. Первый блок преобразуется в 80 32-х битных слов, которые состоят из цифр и первых 6 букв латинского алфавита — A, B, C, D, E и F. 80 слов разбивают на 4 части по 20 слов и каждую часть прогоняют по хитрой формуле с использованием четверых постоянных ключей и пяти переменных. В итоге получают пять слов, каждое состоит из 32 бит. Эти же слова используются как переменные для хеширования следующего блока из 512 бит. Таким образом, хеш-сумма каждого блока напрямую завязана на хеш-сумму предыдущего блока, кроме первого и При хешировании каждого блока используются одинаковые ключи и хеш-сумма предыдущего блока. Таким образом Хеш-сумма любого файла это 5 слов по 32 бита или 160 бит в целом. Теперь об интересном. Зная постоянные ключи, которые использовались для хеширования файла, можно из тех 160 бит восстановить весь документ, просто решая задачу с конца. Это называется «обратным преобразованием». И вообще-то алгоритмы хеширования стараются придумать так, чтобы это самое обратное преобразование было как можно более сложным процессом. В упрощенном виде обратное преобразование выглядит так: Например У нас есть файл (скажем число 4) и ключ (напрмиер число 5). Мы хешируем файл, используя ключ (то есть, умножаем 4 на 5), получаем хеш-сумму — число 20. Если мы знаем хеш-сумму, ключ, по которому хешировали файл, и алгоритм хеширования, то можем просто посчитать формулу в обратном порядке — поделить 20 на 5 и получим наше исходное значение файла А теперь, вопрос?. Действительно ли хеш-сумма по SHA-1 полностью соответствует оригинальному файлу или кажется случайным набором букв и цифр? Что будет, если чуть-чуть изменить исходный файл? Вот, сравните. Отличия — во второй фразе букву P я написал заглавной. Такая вот кардинальная перемена результата при малейшем изменении исходного файла получила название «эффекта лавины» или лавинный эффект. Алгоритм SHA-1 оказался неплохим, но все же уязвимым к коллизиям и обратному преобразованию, хотя восстановление файла по его хешу без знания ключей займет в лучшем случае несколько миллиардов лет. Но Когда на горизонте замаячили квантовые компьютеры, от алгоритма SHA-1 отказались все крупные IT компании, включая Гугл и Яндекс. Да и создатель алгоритма, нацбезопасность США, начала думать над чем-то понадежней. На смену SHA-1 пришел SHA-2. SHA-2 работает по схожему принципу, но использует только один ключ и более хитрые формулы для хеширования. Базовый принцип остался тем же — файл разбивается на блоки, хеш-сумма каждого блока основана на хеш-сумме предыдущего.

Хэширование Bitcoin SHA-256

Криптовалюты Биткоин же работает на алгоритме SHA-256, некой модификации сырого SHA-2. Только на выходе получается не 5 слов, как в первой версии, а целых 8. Восемь 32-х битных слов образуют хеш-сумму размером 256 бит — отсюда и название алгоритма. SHA—256 это классический алгоритм для криптовалют: на нем построена не только основная криптовалюта — Bitcoin, Но и Соответственно в форках bitcoin таких как Bitcoin Cash, Bitcoin Gold, Bitcoin Diamond. используется этот же алгоритм Помимо этих монет, SHA—256 используется также в: * Steemit; * DigiByte; * PeerCoin; * NameCoin; * TeckCoin; * Ocoin; * Zetacoin; * EmerCoin.И многих других Также алгоритм SHA-256 используется как подпрограмма в криптовалюте Litecoin, а основным алгоритмом для майнинга там является Scrypt.Но эти все монеты темы совсем другой рубрики, поэтому просто продолжим говорить о хешировании. Давайте систематизируем кое-что из уже сказанного.В общем процесс хеширования — это череда математических воздействий которым подвергаются данные произвольной длины для преобразования на выходе в битовую строку фиксированной длины. И Каждый из алгоритмов работает по своему, но хорошая хеш-функция должна обладать следующими свойствами

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

Источник

Для чего проверяются хэш-суммы файлов и как это сделать?

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

Что такое целостность файла?

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

Зачем проверять целостность файла?

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

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

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

Как можно проверить целостность файла?

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

Чтобы выполнить проверку по алгоритму MD5, нужно ввести в командную строку следующее:

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

Что такое хэш суммы md5?

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

Как проверить хэш-сумму MD5 с помощью программы Solid Explorer?

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

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

Процесс установки на Android выглядит следующим образом:

Есть ли другие подобные решения

Если требуется быстро проверить целостность файла, но нет доступа к специализированному программному обеспечению, можно открыть вкладку « Свойства » двух сверяемых файлов и провести сравнение величины их размера в байтах. Если величины совпадают, то файл, скорее всего, не подвергался внесению каких-либо изменений.

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

Еще одним способом проверки совпадения хэш-суммы является использование языков веб-программирования для написания специализированного скрипта.

Советы и выводы

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

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

Пожалуйста, оставьте ваши мнения по текущей теме материала. За комментарии, дизлайки, отклики, лайки, подписки огромное вам спасибо!

Источник

Чудеса хеширования

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

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

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

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

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

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

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

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

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

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

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

Вы даже можете провести простой эксперимент: попробуйте при помощи специального сайта произвести преобразование какого-нибудь простого пароля вроде «123456» или «password» из их хеш-значений (созданных алгоритмом MD5) обратно в текст. Вероятность того, что в базе хешей найдутся данные о введенных вами простых паролях, очень высока. В моем случае хеши слов «brain» (8b373710bcf876edd91f281e50ed58ab) и «Brian» (4d236810821e8e83a025f2a83ea31820) успешно распознались, а вот хеш предыдущего абзаца — нет. Отличный пример, как раз для тех, кто все еще использует простые пароли.

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

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

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

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

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

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

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

Источник

Хеш-функция, что это такое?

Приветствую уважаемого читателя!

Сегодня я хотел бы рассказать о том, что из себя представляет хеш-функция, коснуться её основных свойств, привести примеры использования и в общих чертах разобрать современный алгоритм хеширования SHA-3, который был опубликован в качестве Федерального Стандарта Обработки Информации США в 2015 году.

Общие сведения

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

Для идеальной хеш-функции выполняются следующие условия:

а) хеш-функция является детерминированной, то есть одно и то же сообщение приводит к одному и тому же хеш-значению
b) значение хеш-функции быстро вычисляется для любого сообщения
c) невозможно найти сообщение, которое дает заданное хеш-значение
d) невозможно найти два разных сообщения с одинаковым хеш-значением
e) небольшое изменение в сообщении изменяет хеш настолько сильно, что новое и старое значения кажутся некоррелирующими

Давайте сразу рассмотрим пример воздействия хеш-функции SHA3-256.

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

На рисунке ниже видно, что на выходе функции мы имеем 64 цифры шестнадцатеричной системы счисления. Переводя это в двоичную систему, получаем желанные 256 бит.

Любой заинтересованный читатель задаст себе вопрос: «А что будет, если на вход подать данные, бинарный код которых во много раз превосходит 256 бит?»

Надеюсь, теперь нет сомнений в том, что это очень внушительное число!

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

Свойства

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

Pre-image resistance

Имея заданное значение h, должно быть сложно найти любое сообщение m такое, что

Second pre-image resistance

Имея заданное входное значение , должно быть сложно найти другое входное значение такое, что

Collision resistance

Должно быть сложно найти два различных сообщения и таких, что

Такая пара сообщений и называется коллизией хеш-функции

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

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

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

Pre-image resistance. Это свойство называют сопротивлением прообразу. Хеш-функция считается защищенной от нахождения прообраза, если существует очень низкая вероятность того, что злоумышленник найдет сообщение, которое сгенерировало заданный хеш. Это свойство является важным для защиты данных, поскольку хеш сообщения может доказать его подлинность без необходимости раскрытия информации. Далее будет приведён простой пример и вы поймете смысл предыдущего предложения.

Second pre-image resistance. Это свойство называют сопротивлением второму прообразу. Для упрощения можно сказать, что это свойство находится где-то посередине между двумя предыдущими. Атака по нахождению второго прообраза происходит, когда злоумышленник находит определенный вход, который генерирует тот же хеш, что и другой вход, который ему уже известен. Другими словами, злоумышленник, зная, что пытается найти такое, что

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

Неформально все эти свойства означают, что злоумышленник не сможет заменить или изменить входные данные, не меняя их хеша.

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

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

Применение хеш-функций

Рассмотрим несколько достаточно простых примеров применения хеш-функций:

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

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

• Цифровая подпись
Подписываемые документы имеют различный объем, поэтому зачастую в схемах ЭП подпись ставится не на сам документ, а на его хеш. Вычисление хеша позволяет выявить малейшие изменения в документе при проверке подписи. Хеширование не входит в состав алгоритма ЭП, поэтому в схеме может быть применена любая надежная хеш-функция.

Предлагаю также рассмотреть следующий бытовой пример:

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

Теперь давайте поговорим о SHA-3.

Национальный институт стандартов и технологий (NIST) в течение 2007—2012 провёл конкурс на новую криптографическую хеш-функцию, предназначенную для замены SHA-1 и SHA-2.

Организаторами были опубликованы некоторые критерии, на которых основывался выбор финалистов:

Способность противостоять атакам злоумышленников

• Производительность и стоимость

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

• Гибкость и простота дизайна

Гибкость в эффективной работе на самых разных платформах, гибкость в использовании параллелизма или расширений ISA для достижения более высокой производительности

В финальный тур попали всего 5 алгоритмов:

Победителем и новым SHA-3 стал алгоритм Keccak.

Давайте рассмотрим Keccak более подробно.

Keccak

Хеш-функции семейства Keccak построены на основе конструкции криптографической губки, в которой данные сначала «впитываются» в губку, а затем результат Z «отжимается» из губки.

Любая губчатая функция Keccak использует одну из семи перестановок которая обозначается , где

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

В качестве стандарта SHA-3 была выбрана перестановка Keccak-f[1600], для неё количество раундов

Далее будем рассматривать

Давайте сразу введем понятие строки состояния, которая играет важную роль в алгоритме.

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

Соотношение деления зависит от конкретного алгоритма семейства, например, для SHA3-256

В SHA-3 строка состояния S представлена в виде массива слов длины бит, всего бит. В Keccak также могут использоваться слова длины , равные меньшим степеням 2.

Алгоритм получения хеш-функции можно разделить на несколько этапов:

• С помощью функции дополнения исходное сообщение M дополняется до строки P длины кратной r

• Строка P делится на n блоков длины

• «Впитывание»: каждый блок дополняется нулями до строки длиной бит (b = r+c) и суммируется по модулю 2 со строкой состояния , далее результат суммирования подаётся в функцию перестановки и получается новая строка состояния , которая опять суммируется по модулю 2 с блоком и дальше опять подаётся в функцию перестановки . Перед началом работы криптографической губки все элементыравны 0.

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

Все сразу станет понятно, когда вы посмотрите на картинку ниже:

Функция дополнения

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

Функция перестановок

Базовая функция перестановки состоит из раундов по пять шагов:

Шаг

Шаг

Шаг

Шаг

Шаг

Тета, Ро, Пи, Хи, Йота

Далее будем использовать следующие обозначения:

Так как состояние имеет форму массива , то мы можем обозначить каждый бит состояния как

Обозначим результат преобразования состояния функцией перестановки

Также обозначим функцию, которая выполняет следующее соответствие:

— обычная функция трансляции, которая сопоставляет биту бит ,

где — длина слова (64 бит в нашем случае)

Я хочу вкратце описать каждый шаг функции перестановок, не вдаваясь в математические свойства каждого.

Шаг

Эффект отображения можно описать следующим образом: оно добавляет к каждому биту побитовую сумму двух столбцов и

Схематическое представление функции:

Шаг

Отображение направлено на трансляции внутри слов (вдоль оси z).

Проще всего его описать псевдокодом и схематическим рисунком:

Шаг

Шаг представляется псевдокодом и схематическим рисунком:

Шаг

Шаг является единственный нелинейным преобразованием в

Псевдокод и схематическое представление:

Шаг

Отображение состоит из сложения с раундовыми константами и направлено на нарушение симметрии. Без него все раунды были бы эквивалентными, что делало бы его подверженным атакам, использующим симметрию. По мере увеличения раундовые константы добавляют все больше и больше асимметрии.

Ниже приведена таблица раундовых констант для бит

Все шаги можно объединить вместе и тогда мы получим следующее:

Где константы являются циклическими сдвигами и задаются таблицей:

Итоги

В данной статье я постарался объяснить, что такое хеш-функция и зачем она нужна
Также в общих чертах мной был разобран принцип работы алгоритма SHA-3 Keccak, который является последним стандартизированным алгоритмом семейства Secure Hash Algorithm

Надеюсь, все было понятно и интересно

Всем спасибо за внимание!

Источник