Хеш-функции в криптографии

Хеширование – Криптография

Хеширование (иногда «хэширование», англ.

 hashing) — преобразование по детерминированному алгоритму входного массива данных произвольной длины в выходную битовую строку фиксированной длины.

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

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

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

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

История

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

В 1956 году Арнольд Думи (англ. Arnold Dumey) в своей работе «Computers and automation» первым представил концепцию хеширования таковой, какой её знает большинство программистов сейчас. Думи рассматривал хеширование, как решение «Проблемы словаря», а также предложил использовать в качестве хеш-адреса остаток деления на простое число.[1]

Первой серьёзной работой, связанной с поиском в больших файлах, была статья Уэсли Питерсона (англ. W.

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

В 1967 году хеширование в современном значении упомянуто в книге Херберта Хеллермана «Принципы цифровых вычислительных систем». В 1968 году Роберт Моррис (англ.

 Robert Morris) опубликовал в Communications of the ACM большой обзор по хешированию, эта работа считается ключевой публикацией, вводящей понятие о хешировании в научный оборот и закрепившей ранее применявшийся только в жаргоне специалистов термин «хеш».

До начала 1990-х годов в русскоязычной литературе в качестве эквивалента термину «хеширование» благодаря работам Андрея Ершова использовалось слово «расстановка», а для коллизий использовался термин “конфликт” (Ершов использовал «расстановку» с 1956 года, в русскоязычном издании книги Вирта «Алгоритмы и структуры данных» 1989 года также используется термин «расстановка»). Предлагалось также назвать метод русским словом «окрошка». Однако ни один из этих вариантов не прижился, и в русскоязычной литературе используется преимущественно термин «хеширование».[3]

Виды хеш-функций

Хорошая хеш-функция должна удовлетворять двум свойствам:

1. Быстро вычисляться;
2. Минимизировать количество коллизий

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

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

Казалось бы значения хеш-кодов должны равномерно распределиться между «000» и «999», но для реальных данных такой метод подходит лишь в том случае, если ключи не имеют большого количества нулей слева или справа.[3]

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

Хеш-функции, основанные на делении

Первый метод заключается в том, что мы используем в качестве хеша остаток от деления на , где  – это количество всех возможных хешей:

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

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

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

При правильном выборе  такой способ гарантирует отсутствие коллизий между почти одинаковыми ключами.[3]

Мультипликативная схема хеширования

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

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

Среди преимуществ этих двух методов стоит отметь, что они выгодно используют то, что реальные ключи неслучайны, например в том случае если ключи представляют собой арифметическую прогрессию (допустим последовательность имён «ИМЯ1», «ИМЯ2», «ИМЯ3»). Мультипликативный метод отобразит арифметическую прогрессию в приближенно арифметическую прогрессию различных хеш-значений, что уменьшает количество коллизий по сравнению со случайной ситуацией.[3]

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

Хеширование строк переменной длины

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

Хеширование Пирсона (англ. Pearson hashing) — алгоритм, предложенный Питером Пирсоном (англ.

 Peter Pearson) для процессоров с 8-битными регистрами, задачей которого является быстрое вычисление хеш-кода для строки произвольной длины.

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

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

h := 0for each c in W loop index := h xor c h := T[index]end loopreturn h

Среди преимуществ алгоритма следует отметить:

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

В качестве альтернативного способа хеширования ключей,  состоящих из  символов (), можно предложить вычисление

Идеальное хеширование

Идеальной хеш-функцией (англ. Perfect hash function) называется такая функция, которая отображает каждый ключ из набора  в множество целых чисел без коллизий. В математических терминах это инъективное отображение.

Описание

1. Функция  называется идеальной хеш-функцией для , если она инъективна на ;
2. Функция  называется минимальной идеальной хеш-функцией для , если она является ИХФ и ;
3. Для целого , функция  называется -идеальной хеш-функцией (k-PHF) для  если для каждого  имеем .

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

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

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

Универсальное хеширование

Универсальным хешированием (англ.

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

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

Хэш функция в криптографии [описание+примеры]

Технология блокчейн признана одним из самых инновационных открытий последних лет. Она оказала огромное влияние на формирование мира и её влияние только растет.

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

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

Что такое криптографические хеш-функции?

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

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

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

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

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

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

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

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

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

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

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

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

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

Как работают криптографические хеш-функции

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

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

Как используют показатели мегахеша майнеры

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

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

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

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

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

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

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

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

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

Хешрейт отражается в фиксированных показателях:

• Хеш в секунду H/s;
• Килохеш в секунду KH/s;
• Мегахеш в секунду MH/s;
• Гигахэш в секунду GH/s;
• Терахэш в секунду TH/s;
• Петахэш в секунду PH/s.

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

Мегахэш — это фактически отражение того, сколько различных хешей вычислительная техника может сгенерировать за одну секунду, например, 1000 мегахешей.

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

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

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

Выводы

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

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

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

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

Источник: https://prostocoin.com/blog/hash

Понимание криптографических хешей – ключ к познанию блокчейна | Криптовалюта.Tech

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

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

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

Очень краткая история цифровых денег

Биткоин – новый подход к предыдущим экспериментам с цифровыми деньгами. В 1990-х это была горячая, но спекулятивная тема. Даже Алан Гринспен в своей речи в 1996 г. сказал:

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

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

В числе их экспериментов, существовавших до Биткоина, были Hashcash Адама Бэка, BitGold Ника Сабо, B-Money Вэй Дая и RPOW Хэла Финни.

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

Что такое криптографические хеш-функции?

Криптографическая хеш-функция берёт данные и, по сути, переводит их в строку букв и цифр. Вы когда-нибудь пользовались URL-сокращалками типа Bitly или TinyURL? Это нечто похожее.

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

Это может быть что-то очень короткое (например, слово «пёс») или почти бесконечно длинное (например, весь текст «Повести о двух городах»), и на выходе вы получите уникальную строку установленной длины.

Итак, данные вводятся в хеш-функцию, функция выполняется и получается строка букв и цифр (можете попробовать самостоятельно здесь). Эта строка называется хешем. В блокчейне Биткоина хеши состоят из 256 бит или 64 символов.

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

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

И каждый раз, когда вы вводите одни и те же данные, вы получите не только один и тот же хеш, но уникальный и отличный от любого другого хеша.

Пример

Хеш фразы:

df0a199c7fef0a53d9a4144bc9122441b94510c13faf424ca26b65aa5035048f

Тогда как хеш слова «пёс»:

cd6357efdd966de8c0cb2f876cc89ec74ce35f0968e11743987084bd428944

Как работают криптографические хеш-функции

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

Использовавшаяся выше хеш-функция – SHA-256, хеш-функция, применяемая в Биткоине, – работает на основе безумно сложной формулы, связанной с отражением света от эллипсов. Вам не стоит слишком из-за этого переживать.

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

Как хеш-функции применяются в блокчейне

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

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

Так как блокчейну удаётся обновляться, оставаясь децентрализованным? Он использует криптографическую вероятностную хеш-игру, называемую «доказательство выполнения работы» (Proof of Work).

Криптография обеспечивает консенсус

Чтобы продолжать функционировать, блокчейн должен создавать новые блоки. Так как блокчейны – это децентрализованные системы, новые блоки должны создаваться не единственным аутентифицирующим субъектом, а сетью в целом. Чтобы решить, каким будет новый блок, сеть должна достичь консенсуса.

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

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

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

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

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

Компьютеры, в каком-то смысле, работают совместно, так как каждый предложенный хеш не может быть предложен снова. Компьютер, первым отгадавший правильное число, выигрывает право на создание следующего блока и получает 12,5 биткоина, что сейчас равно примерно $50 000.

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

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

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

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

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

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

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

10-минутное решение

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

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

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

Ещё меньше вероятность получить любую обезьяну.

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

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

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

Так как же протокол Биткоина гарантирует, что игра на отгадывание будет становиться достаточно сложной, чтобы даже чрезвычайно мощным майнинговым компьютерам на отгадывание требовалось примерно 10 минут? Вспомните пример с обезьяной.

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

В частности, игра усложняется посредством требования наличия у правильного хеша в начале определённого количества нулей.

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

Это сложно понять, но в основе лежит математический закон, говорящий, что достаточно квадратного корня N рандомных событий, чтобы вероятность их совпадения составляла 50%.

Та же самая математика поддерживает парадокс дней рождения – если в комнате всего 23 человека, существует 50% вероятность, что у двух из них день рождения в один и тот же день.

Должен заметить, что я лишь (с трудом) понимаю, как работает блокчейн Биткоина.

Другие блокчейны могут использовать криптографию совершенно иначе, чем я здесь описал. Например, я не знаю, использует ли ту же систему доказательство доли владения (proof of stake) – как утверждается, более эффективное усовершенствование доказательства выполнения работы.

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

Источник: https://cryptocurrency.tech/ponimanie-kriptograficheskih-heshej-klyuch-k-poznaniyu-blokchejna/

Криптографическая хеш-функция

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

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

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

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

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

Применение криптографических хеш-функций в создании электронной подписи

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

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

•         повышение криптостойкости;
•         снижение сложности процесса;
•         обеспечение совместимости.

Применение криптографических хеш-функций при аутентификации парольной фразы

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

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

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

Наиболее распространенные криптографические хеш-функции

На данный момент применяются следующие криптографические хеш-функции:

• MD5 – один из самых распространённых алгоритмов, являющийся криптографической хеш-функцией, размер которой составляет 128 бит. В ближайшее время готовится обновление версии, так как она уже не соответствует высоким стандартам криптоустойчивости.
• ГОСТ Р 34.11-94 – отечественная криптографическая хеш-функция, генерирующая дайджест длиной 256 бит.
• ГОСТ Р 34.11-2012 – обновлённая версия, отличающаяся высокой стойкостью к попыткам взлома и стабильностью в работе. Объем выдаваемого хеша может быть как 512, так и 256 бит. Как правило, применяется в системе государственного документооборота, создавая электронные подписи.
• SHA-1 – криптографическая хеш-функция, преобразующая информацию в строку, длина которой равняется 160 битам. Не обладает достаточным уровнем криптоустойчивости.
• SHA-2 – криптографическая хеш-функция, созданная на основе алгоритмов SHA: 224; 256; 384; 512; 512/256; 512/224. Несмотря на высокую стойкость к взлому, данный алгоритм используется крайне редко. Причина – неудачный результат одного из криптоанализов, во время которого было выявлено критическое количество коллизий (повторений хеша). Разработчики намерены создать новую криптографическую хеш-функцию SHA-3, которая будет основана на алгоритме Keccak.

Уровень сложности

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

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

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

Будьте в курсе всех важных событий United Traders — подписывайтесь на наш телеграм-канал

Источник: https://utmagazine.ru/posts/21195-kriptograficheskaya-hesh-funkciya

Универсальное хеширование

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

В хеш-таблицах

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

1. Метод цепочек (метод прямого связывания)

2. Метод открытой адресации

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

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

Криптографическая соль

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

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

Данный метод, кпримеру, используется для храненияпаролей в UNIX-подобныхоперационных системах.

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

Криптографические хеш-функции

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

• Необратимость: для заданного значения хеш-функции m должно быть вычислительно неосуществимо найти блок данных , для которого .
• Стойкость к коллизиям первого рода: для заданного сообщения M должно быть вычислительно неосуществимо подобрать другое сообщение N, для которого .
• Стойкость к коллизиям второго рода: должно быть вычислительно неосуществимо подобрать пару сообщений , имеющих одинаковый хеш.

Данные требованияне являются независимыми:

• Обратимая функция нестойка к коллизиям первого и второго рода.
• Функция, нестойкая к коллизиям первого рода, нестойка к коллизиям второго рода; обратное неверно.

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

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

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

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

Источник: https://StudFiles.net/preview/5877716/page:3/

Корпоративные информационные системы

http://ru.wikipedia.org/wiki/Целостность_информации 

Целостности данных – при котором отсутствует любое ее изменение либо изменение осуществляется только преднамеренно субъектами, имеющими на него право.

Методы контроля целостности данных:

1. Полная копия данных 

Полная копия данных

Создаются полные копии данных и потом сверяются. 

Преимущества:

• простота реализации
• полный контроль данных (до бита)

Недостатки:

• большой объем
• копии можно подменить
• копиями можно воспользоваться (например: если данные – пароль)

Рис. Контроль целостности с помощью полной копии данных

Применение:

1. контроль целостности файлов 

Контрольная сумма

http://ru.wikipedia.org/wiki/Контрольная_сумма

Контрольная сумма – значение, рассчитанное по входным данным с помощью определённого алгоритма.

Преимущества:

• высокая скорость вычисления
• малый размер
• стандартный размер

Недостатки:

• можно подменить
• для одного значения существует множество исходных данных
• можно подобрать исходные данные к значению за приемлемое время (например: получить пароль)

Рис. Контроль целостности с помощью контрольной суммы

Примеры контрольных сумм: CRC8, CRC16, CRC32

Пример вычисления:

исходный текст: Контроль целостности данных

crc32 (длина 32 бита)

b4feb5a5

Применение:

1. контроль целостности файлов
2. контроль передаваемых данных по каналам связи
3. контроль целостности при считывании данных (например: c HDD)

Хеш

http://ru.wikipedia.org/wiki/Хеширование

Хеш (хэш, криптографический хеш) – значение, рассчитанное по входным данным с помощью криптографического алгоритма.

Преимущества:

• малый размер
• стандартный размер
• нельзя подобрать исходные данные к значению за приемлемое время (например: получить пароль)

Недостатки:

• низкая скорость вычисления (сопоставима с шифрованием)
• можно подменить
• для одного значения существует множество исходных данных

Рис. Основная задача хеш функций

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

ГОСТ Р 34.11-94

http://ru.wikipedia.org/wiki/ГОСТ_Р_34.11-94

Входное сообщение M разделяется на блоки mn,mn ? 1,mn ? 2,…,m1 по 256 бит. В случае если размер последнего блока mn меньше 256 бит, то к нему приписываются слева нули для достижения заданной длины блока.

Каждый блок сообщения подаётся на шаговую функцию для вычисления промежуточного значения хеш-функции Hout=f(Hin, mi)  где Hout, Hin, mi — блоки длины 256 бит.

Рис. Вычисление хеш по ГОСТ Р 34.11-94 (сравните с CBC)

h — значение хеш-функции сообщения M

Len(M) – длина сообщения

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

Пример вычисления:

исходный текст: Контроль целостности данных

md2 (длина 128 бит)

md4 (длина 128 бит)

md5 (длина 128 бит)

sha1 (длина 160 бит)

sha224 (длина 224 бит)

sha256 (длина 256 бит)

sha384 (длина 384 бит)

sha512 (длина 512 бит)

ГОСТ Р 34.11-94 (длина 256 бит)

7e347a5f3a3d8c6837d7accbed3e0b1e

e37e491b9b4ea133df9964b25d7c7cd9

8ab8a5cf989e220ff8d39be415b903d5

63cdc45bd8a857007d0be8c435e1e547653482d3

670c98e5b7ce7bd2c7e98b6ed448e0a6f3247e3fdeb678dde61bce

1a97bcc0cf6722a8aac7b73d12700c0022778904790ce9eee7656f12d95dc2

b87b59cad0db141378d8ff04e46d00dd137113391d2a7009d640dd018680c459 310bdfef6b3258aeaa4b8146105698

3f7b9d8b241d764026fe2b0f72ad62d65fd1c5d77a18784108a69e8ad172c2 e6583989439aea658a2111525897d43af0f6c50cf299b360c21b3e02e8706f4e

d38e4f1bc5d03601486f4aca83fed00c82e1a36fdac27806cce4b9464af1e9f9

Применение:

1. контроль целостности файлов
2. контроль передаваемых данных по каналам связи
3. контроль целостности при считывании данных (например: c HDD)
4. хеши паролей
5. аутентификация (CRAM-MD5, DIGEST-MD5 и т.д.)

Имитовставка (MAC, message authentication code — код аутентичности сообщения)

 http://ru.wikipedia.org/wiki/Имитовставка

Имитовставка –  значение, рассчитанное по входным данным с помощью криптографического алгоритма с использованием секретного элемента (ключа), известного только отправителю и получателю.

Преимущества:

• малый размер
• стандартный размер
• нельзя подобрать исходные данные к значению за приемлемое время (например: получить пароль)
• нельзя подменить без секретного элемента (ключа)

Недостатки:

• низкая скорость вычисления (сопоставима с шифрованием)
• для одного значения существует множество исходных данных
• секретный ключ известен как минимум двоим

 Вычисляют имитовставку шифрованием данных блочным алгоритмом в режимах CBC. Имитовставкой является последний шифрованный блок.

Рис. Вычисление имитовставки

Имитовставка по ГОСТ 28147-89

Длина имитовставки от 1 до 32 бит.

Открытый текст TO разбивается на блоки длиной 64 бита. Последний блок в случае необходимости дополняется нулями.

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

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

ЭЦП

http://ru.wikipedia.org/wiki/ЭЦП

Электронная цифровая подпись – зашифрованное значение вычисленного хеша по входным данным.

Преимущества:

• малый размер
• стандартный размер
• нельзя подобрать исходные данные к значению за приемлемое время (например: получить пароль)
• нельзя подменить без секретного элемента (ключа)
• секретный ключ известен одному

Недостатки:

• низкая скорость вычисления (сопоставима с шифрованием)
• для одного значения существует множество исходных данных

Рис. Создание и проверка ЭЦП

Алгоритм:

1. вычисляется хеш
2. шифруется хеш

Применение:

1. контроль целостности файлов
2. контроль передаваемых данных по каналам связи
3. аутентификации источника данных (кто создал подпись)

f

Источник: https://moodle.kstu.ru/mod/page/view.php?id=9359