Применение хеш-функции в создании электронной цифровой подписи
Трубникова, Е. А. Применение хеш-функции в создании электронной цифровой подписи / Е. А. Трубникова, В. П. Батунина. — Текст : непосредственный // Юный ученый. — 2020. — № 7 (37). — С. 19-22. — URL: https://moluch.ru/young/archive/37/2117/ (дата обращения: 01.10.2023).
При обмене электронными документами по каналам связи возникает проблема аутентификации как автора документа, так и самого документа. Это означает, что получатель должен быть уверен, во-первых, в истинности автора, а во-вторых, в отсутствии изменений в самом документе. В обычных бумажных документах эти проблемы решаются за счет того, что содержание документа и рукописная подпись автора жестко связаны физическим носителем данных (бумагой). В электронных документах на машинных носителях такой связи нет.
Целью аутентификации электронных документов является их защита от возможных видов вредоносных действий:
– активный перехват — злоумышленник, подключившись к каналу связи, перехватывает файлы документов и меняет их на другие,
направляет документ абоненту
от имени абонента
утверждает, что не направлял документ абоненту
, хотя в действительности посылал;
меняет полученный или формирует новый документ, после чего утверждает, что получил его от абонента
повторяет от своего имени ранее переданный документ, который абонент
Один из самых простых способов аутентификации (подписи) электронных документов — использование шифрования. При этом отправитель
шифрует документ своим секретным ключом и отправляет получателю
дешифрует документ с помощью открытого ключа отправителя
. Если это ему удается, то документ считается истинным. Если получатель
не сможет дешифровать документ, то документ подлинным не считается. Такой способ имеет чрезвычайно серьезный недостаток, связанный с тем, что он неэффективен для подписания документов значительного объема.
Именно поэтому для аутентификации электронных документов, передаваемых по телекоммуникационным каналам связи, используется специально создаваемая электронная цифровая подпись (ЭЦП). Функционально ЭЦП аналогична обычной рукописной подписи и обладает следующими свойствами:
– показывает, что подписанный документ получен от лица, поставившего свою подпись;
– не дает возможности лицу, поставившему свою подпись, отказаться от подписанного документа;
– является неотъемлемой частью данного документа и не может быть использована для подписания другого документа;
– гарантирует целостность подписанного документа.
Электронная цифровая подпись представляет собой относительно небольшое количество дополнительных цифровых данных, которые передаются вместе с подписанным текстом. Применение ЭЦП имеет вид следующего криптографического протокола:
1) для документа
, который должен быть подписан, отправитель
вычисляет значение односторонней хэш-функции
шифрует своим личным секретным ключом и получает число, которое считается подписью документа;
3) зашифрованное хэш-значение вместе с документом
сначала сам вычисляет хэш-значение
полученного документа, далее дешифрует полученное хеш-значения с использованием открытого ключа отправителя
, после чего сравнивает оба значения.
Если два полученных хэш-значения совпадают, то подпись отправителя
считается верной, а сам документ
Участники криптографического протокола ЭЦП должны предварительно договориться об использовании определенной криптографической системы, а также хэш-функции.
Среди большого количества различных асимметричных криптосистем самой популярной является криптосистема RSA, разработанная в 1977 г. и получившая свое название в честь Рона Ривеста (Rivest), Ади Шамира (Shamir) и Леонарда Эйдельмана (Adleman). Алгоритм RSA используется в банковских компьютерных сетях, особенно для работы с удаленными клиентами (Обслуживание кредитных карточек). Надежность алгоритма основывается на трудности факторизации (разложения на множители) больших чисел и трудности вычисления дискретных алгоритмов (нахождения
Алгоритм RSA состоит из трех частей: генерации ключей, шифрования и дешифрования. Генерируют
— открытый ключ и
— секретный ключ. Открытый ключ публикуется и доступен каждому желающему прислать владельцу ключа сообщение, которое зашифровано указанным алгоритмом. Зашифрованное сообщение невозможно прочитать с помощью открытого ключа, и только владелец закрытого ключа имеет возможность расшифровать принятое сообщение.
, которая используется в протоколе ЭЦП, предназначена для того, чтобы сжать подписываемый документ
произвольной длины к двоичному хэш-значению
фиксированной длины (несколько десятков бит). Благодаря этому подписывается не один длинный документ, а его краткое хэш-значение, при этом длина подписи становится фиксированной.
Основные свойства хэш-функции:
зависит от всего документа
чрезвычайно сложным способом, благодаря чему по значению
невозможно восстановить документ
чувствительно к любым, даже незначительным, изменениям в документе
(вставки, удаления, перестановки и т. п.);
является необратимой, то есть подбор некоторого фиктивного документа
‘ с тем же самым хеш-значением
является задачей практически нерешаемой;
4) вероятность того, что хеш-значения двух разных документов совпадут, чрезвычайно мала.
Подавляющее большинство используемых хэш-функций имеют вид
и работают по следующему принципу: они образуют одно хэш-значение длиной
бит из двух входных значений, каждое из которых тоже имеет длину n бит. Для применения такой хэш-функции документ
должен быть предварительно представлен в двоичной форме и разбит на отдельные блоки
Содержание указанных входных значений хэш-функции следующее:
1) первое входное значение представляет собой очередной блок документа
2) второе входное значение представляет собой хэш-значение
всех предыдущих блоков документа.
При исчислении хэш-значение для первого блока
документа используется некоторое начальное хэш-значение
, которое можно выбрать случайным или фиксированным (например,
— в простейшем случае). При этом хэш-значение, вычисленное при использовании последнего блока документа, считается хеш-значением всего документа
Правило образования одного хэш-значения из двух входных зависит от типа хэш-функции. В простейшем случае здесь может использоваться сложение по модулю 2, т. е.
Покажем реализацию алгоритма создания и передачи ЭЦП на примере. Для создания иллюстративного примера мы будем использовать небольшие числа в десятичной форме записи. Найдем хеш-образ фамилии Трубникова, используя хеш-функцию
— произведение двух простых чисел, и алгоритм шифрования RSA.
Возьмем два простых числа
выбираем случайным образом, пусть оно равно 12. Слово «ТРУБНИКОВА» представим в виде последовательности чисел (20, 18, 21, 2, 15, 10, 12, 16, 3, 1) по номерам букв в русском алфавите. Тогда имеем
, получим хеш-образ сообщения «ТРУБНИКОВА»:
В итоге получаем хеш-образ сообщения «ТРУБНИКОВА», равный 9, который будем использовать для вычисления электронной цифровой подписи по схеме RSA.
Сгенерируем открытый и секретный ключи для алгоритма шифрования RSA. Оставим ранее выбранные простые двузначные числа
, тогда функция Эйлера
выбираем из условий
взаимно просто с
не имеют общих делителей.
выбираем из условий
Последнее условие означает, что число
должно делиться на 352 без остатка.
Таким образом, для определения
нужно подобрать такое число
Таким образом мы сгенерировали
— открытый ключ и
Электронная цифровая подпись сообщения, состоящего из Фамилии, вычисляется по правилу
Как видим, хеш-образ сообщения совпадает с найденным значением H, следовательно, подпись признается подлинной.
Таким образом мы построили демонстрационный пример создания электронной цифровой подписи с использованием хеш-функции
и алгоритма шифрования RSA. Все вычисления были выполнены в электронных таблицах Excel, в частности, с использованием формулы =ОСТАТ(
- Айерлэнд К. Классическое введение в современную теорию чисел / К. Айерлэнд, М. Роузен. — Пер. с англ. — М.: Мир, 1987. — 416 с.
- Алферов А. П. Основы криптографии / А. П. Алферов, А. Ю. Зубов, А. С. Кузьмин, А. В. Черемушкин. М.: Гелиос АРВ, 2002. — 480 с.
Похожие статьи
Исследование криптосистем с открытым ключом на основе.
В криптосистеме с открытым ключом для шифрования и расшифрования используются различные ключи.
RSA — криптографический алгоритм с открытым ключом
Это позволит нападающему читать все сообщения, зашифрованные открытым ключом и подделывать.
Создание ключей, шифрование и дешифрование сообщений.
Применить закрытый ключ для дешифрования сообщения: . Рассмотрим пример создания ключей шифрования и дешифрования в
Статья посвящена реализации алгоритма шифрования на открытом ключе RSA. LabVIEW (англ. RSA (аббревиатура от фамилий Rivest.
Пост-квантовый алгоритм электронно—цифровой подписи на.
Алгоритмы электронно—цифровой подписи являются одним из важнейших инструментов криптографии и обеспечивают целостность электронного документа, аутентификацию и неотказуемость автора документа. Электронно—цифровая подпись в настоящее время.
Алгоритмы шифрования данных | Статья в журнале.
Алгоритмы асимметричного шифрования используют два ключа шифрования: открытый для зашифровывания информация и секретный для ее дешифрования, причем открытый ключ достаточно просто вычисляется из секретного, а вычислить секретный ключ из открытого.
Реализация алгоритма шифрования RSA на языке.
Статья посвящена реализации алгоритма шифрования на открытом ключе RSA. LabVIEW (англ. Laboratory Virtual Instrumentation Engineering Workbench) — это среда разработки и платформа для выполнения программ.
Анализ алгоритма RSA. Некоторые распространённые.
Атака на подпись RSA в схеме с нотариусом. Пусть — открытый ключ нотариуса.
Сторона шифрует сообщения с применением очередного открытого ключа каждого пользователя.
Основные термины (генерируются автоматически): открытым ключом, шифрования rsa.
Способ хранения закрытого ключа криптосистемы цифровой.
Электронная цифровая подпись (ЭЦП) — реквизит электронного документа, полученный в результате криптографического преобразования информации с использованием закрытого ключа подписи и позволяющий установить отсутствие искажения информации в электронном.
Шифрование и криптоанализ | Статья в журнале «Молодой. »
Основные термины (генерируются автоматически): открытым ключом, шифрования rsa, секретной экспоненты, секретную экспоненту, открытый ключ
Алгоритмы шифрования данных | Статья в журнале. Алгоритмы асимметричного шифрования используют два ключа.
Теория чисел в криптографии | Статья в журнале.
RSA, число, простое число, тест, выбор показателей, случайный сеансовый ключ, случайный образ, секретный показатель, простой перебор
Статья посвящена реализации алгоритма шифрования на открытом ключе RSA. Некоторые аспекты криптографического взлома и.
Электронная цифровая подпись для чайников: с чем ее есть, и как не подавиться. Часть 1
Итак, все чаще в кругах, работающих с документами все чаще звучат слова «электронный документ» и, связанное с ним почти неразрывно «электронная цифровая подпись», иначе — ЭЦП.
Данный цикл статей предназначен для того, чтобы раскрыть «тайное знание» о том, что это такое, когда и как это можно и нужно использовать, какие есть плюсы и минусы.
Естественно, статьи пишутся не для специалистов по криптографии, а для тех, кто эту самую криптографию будет использовать, или же только начинает ее изучение, желая стать специалистом, поэтому я старался максимально упростить понимание всего процесса, приводя аналогии и рассматривая примеры.
Зачем нам вообще что-то подписывать? Естественно, чтобы удостоверить, что мы ознакомились с содержимым, согласны (а иногда наоборот, не согласны) с ним. А электронная подпись еще и защищает наше содержимое от подмены.
Итак, начать, естественно, стоит с того, что такое электронная цифровая подпись.
В самом примитивном случае это — результат хэш-функции. Что это такое лучше меня разъяснит википедиа, в нашем же случае главное, что с высокой степенью вероятности ее результат не повторяется для разных исходных данных, а также что результат этой функции мало того, что короче исходных данных, так еще по нему исходную информацию восстановить нельзя. Результат функции называют хэшем, а применение этой функции к данным называют хешированием. Грубо, можно назвать хэш функцию архивированием, в результате чего мы получаем очень маленькую последовательность байт, но восстановить исходные данные из такого «архива» нельзя.
Итак, мы читаем файлик в память, хэшируем прочитанное. И что, уже получаем ЭЦП? Почти. Наш результат с большой натяжкой можно назвать подписью, но, все же, полноценной подписью он не является, потому что:
1. Мы не знаем, кто сделал данную подпись
2. Мы не знаем, когда была сделана подпись
3. Сама подпись не защищена от подмены никак.
4. Ну и да, хэш функций много, какая из них использовалась для создания этого конкретного хэша?
Поэтому применять к хэшу слово «подпись» еще нехорошо, будем называть его дальше просто хэш.
Вы посылаете ваш файл другому человеку, допустим, по почте, будучи уверенными, что он точно получит и прочитает именно то, что вы послали. Он же, в свою очередь, тоже должен хэшировать ваши данные и сравнить свой результат с вашим. Если они совпали — все хорошо. Это значит что данные защищены? Нет.
Ведь хэшировать может кто угодно и когда угодно, и вы никогда не докажете, что он хэшировал не то, что вы послали. То есть, если данные будут перехвачены по дороге злоумышленником, или же тот, кому вы посылаете данные — не очень хороший человек, то данные могут быть спокойно подменены и прохэшированы. А ваш получатель (ну или вы, если получатель — тот самый нехороший человек) никогда не узнает, что он получил не то, что вы отправляли, или сам подменил информацию от вас для дальнейшего использования в своих нехороших целях.
Посему, место для использование чистой хэш функции — транспорт данных в пределах программы или программ, если они умеют общаться между собой. Собственно, с помощью хэш функций вычисляются контрольные суммы. И эти механизмы защищают от случайной подмены данных, но не защищают от специальной.
Но, пойдем дальше. Нам хочется защитить наш результат хеширования от подмены, чтобы каждый встречный не мог утверждать, что это у него правильный результат. Для этого самое очевидное что (помимо мер административного характера)? Правильно, зашифровать. А ведь с помощью шифрования же можно и удостоверить личность того, кто хэшировал данные! И сделать это сравнительно просто, ведь есть ассиметричное шифрование. Да, оно медленное и тяжелое, но ведь нам всего-то и надо — зашифровать маленькую последовательность байт. Плюсы такого действия очевидны — для того, чтобы проверить нашу подпись, надо будет иметь наш открытый ключ, по которому личность зашифровавшего (а значит, и создавшего хэш) можно легко установить.
Суть этого шифрования в следующем: у вас есть закрытый ключ, который вы храните у себя. И есть открытый ключ. Открытый ключ вы можете всем показывать и раздавать, а закрытый — нет. Шифрование происходит с помощью закрытого ключа, а расшифровывание — с помощью открытого.
Приводя аналогию, у вас есть отличный замок и два ключа к нему. Один ключ замок открывает (открытый), второй — закрывает (закрытый). Вы берете коробочку, кладете в нее какую-то вещь и закрываете ее своим замком. Так, как вы хотите, чтобы закрытую вашим замком коробочку открыл ее получатель, то вы открытый, открывающий замок, ключик спокойно отдаете ему. Но вы не хотите, чтобы вашим замком кто-то закрывал коробочку заново, ведь это ваш личный замок, и все знают, что он именно ваш. Поэтому закрывающий ключик вы всегда держите при себе, чтобы кто-нибудь не положил в вашу коробочку мерзкую гадость и не говорил потом, что это вы ее положили и закрыли своим замком.
И все бы хорошо, но тут сразу же возникает проблема, а, на самом деле, даже не одна.
1. Надо как-то передать наш открытый ключ, при этом его должна понять принимающая сторона.
2. Надо как-то связать этот открытый ключ с нами, чтобы нельзя было его присвоить.
3. Мало того, что ключ надо связать с нами, надо еще и понять, какой зашифрованный хэш каким ключом расшифровывать. А если хэш не один, а их, скажем, сто? Хранить отдельный реестр — очень тяжелая задача.
Все это приводит нас к тому, что и закрытый ключ, и наш хэш надо хранить в каких-то форматах, которые нужно стандартизировать, распространить как можно шире и уже тогда использовать, чтобы у отправителя и получателя не возникало «трудностей перевода».
Как водится у людей, к чему-то единому прийти так и не смогли, и образовалось два больших лагеря — формат OpenPGP и формат S/MIME + X.509. Но об этом уже в следующей статье.
Хэш-функции и электронная подпись
Определение 9.1 Хэш-функции — это функции, предназначенные для «сжатия» произвольного сообщения, записанного, как правило, в двоичном алфавите, в некоторую битовую последовательность фиксированной длины, называемую сверткой.
Хэш-функции применяются для тестирования логических устройств, для быстрого поиска и проверки целостности записей в базах данных.
В криптографии хэш-функции применяются для решения следующих задач:
- построения систем контроля целостности данных при их передаче или хранении,
- аутентификация источника данных.
При решении первой задачи для каждого набора данных вычисляется значение хеш-функции (называемое кодом аутентификации сообщения или имитовставкой), которое передается или хранится вместе с самими данными. При получении данных пользователь вычисляет значение свертки и сравнивает его с имеющимся контрольным значением. Несовпадение говорит о том, что данные были изменены. При решении второй задачи, аутентификации источника данных, мы имеем дело с не доверяющими друг другу сторонами. В связи с этим подход, при котором обе стороны обладают одним и тем же секретным ключом, уже не применим. В такой ситуации применяют схемы цифровой подписи, позволяющие осуществить аутентификацию источника данных. Как правило, при этом сообщение, прежде чем быть подписано личной подписью, основанной на секретном ключе пользователя, «сжимается» с помощью хеш-функции, выполняющей функцию кода обнаружения ошибок.
Определение 9.2 Обозначим через множество, элементы которого будем называть сообщениями,
— натуральное число. Хеш-функцией называется всякая легко вычислимая функция
двух переменных, где
и
— двоичные векторы длины
и
соответственно, и
— длина свертки. Для получения значения
сообщение
сначала разбивается на блоки длины
(при этом если длина сообщения не кратна
, то последний блок неким специальным образом дополняется до полного), а затем к полученным блокам
применяют следующую последовательную процедуру вычисления свертки:
— некоторый фиксированный начальный вектор . Если функция
зависит от ключа, то этот вектор можно положить равным нулевому вектору. Если же функция
не зависит от ключа, то для исключения возможности перебора коротких сообщений (при попытках обращения хеш-функции) этот вектор можно составить из фрагментов указывающих на дату, время, номер сообщения и т.п.
При таком подходе свойства хеш-функции полностью определяются свойствами одношаговой сжимающей функции
.
9.2 Электронная подпись
9.2.1 Общие положения
Появление криптографии с открытым ключом позволило решать задачи, которые ранее считались неразрешимыми. К таким задачам относится использование цифрового аналога собственноручной подписи абонента — электронной цифровой подписи (ЭЦП).
Цифровая подпись (ЭЦП) для сообщения является числом, зависящим от самого сообщения и от секретного ключа, известного только подписывающему. Важное требование: подпись должна допускать проверку без знания секретного ключа. При возникновении спорной ситуации, связанной с отказом от факта подписи либо с возможной подделкой подписи, третья сторона должна иметь возможность разрешить спор.
Задачи, которые решает подпись:
- Осуществить аутентификацию источника сообщения,
- Установить целостность сообщения,
- Обеспечить невозможность отказа от факта подписи конкретного сообщения.
Для реализации схемы ЭЦП необходимы два алгоритма: алгоритм генерации подписи и алгоритм проверки. Надежность схемы ЭЦП определяется сложностью следующих задач:
- Подделки подписи, то есть нахождения правильного значения подписи для заданного документа,
- Создания подписанного сообщения, то есть нахождения хотя бы одного сообщения с правильным значением подписи,
- Подмены подписи, то есть нахождения двух различных сообщений с одинаковым значением подписи.
Заметим, что между ЭЦП и собственноручной подписью имеются различия, хотя они и служат для решения одинаковых задач. Так, ЭЦП зависит от подписываемого текста, различна для разных тестов. Кроме того, ЭЦП требует дополнительных механизмов, реализующих алгоритмы ее вычисления и проверки. Наконец, принципиальной сложностью, возникающей при использовании ЭЦП, является необходимость создания инфраструктуры открытых ключей. Эта инфраструктура состоит из центров сертификации открытых ключей и обеспечивает возможность своевременного подтверждения достоверности открытой информации, необходимой для проверки ЭЦП, что необходимо для предотвращения подделки подписи.
Некоторые наиболее употребительные схемы ЭЦП
В настоящее время имеется большое количество различных схем ЭЦП, обеспечивающих тот или иной уровень стойкости. Существующие схемы можно классифицировать таким образом:
- Схемы на основе систем шифрования с открытыми ключами,
- Схемы со специально разработанными алгоритмами вычисления и проверки подписи,
- Схемы на основе симметричных систем шифрования. Рассмотрим некоторые схемы.
9.2.2 Схема Эль-Гамаля
Безопасность схемы основана на трудности вычисления дискретных логарифмов в конечном поле. Для генерации пары ключей выбирается простое число и два случайных числа,
и
, оба меньше
. Затем вычисляется
. При этом
и
можно сделать общими для группы пользователей. Секретным ключом является
. Чтобы подписать сообщение
, сначала выбирается случайное число
, взаимно простое с
. Затем вычисляются подпись
по формулам:
. Оно должно храниться в секрете и уничтожаться сразу после вычисления подписи, так как знание
и значения подписи позволяет легко вычислить секретный ключ
. И тогда подпись будет полностью скомпрометирована. Кроме того,
должно быть действительно случайным и не должно повторяться для различных подписей, полученных на одном секретном ключе. Если злоумышление сможет получить два сообщения, подписанные с помощью одного и того же значения
, то он сможет раскрыть
, даже не зная значение
.
Схема Эль-Гамаля послужила образцом для построения большого семейства во многом сходных по своим свойствам схем подписи.
Пример 9.1 Выберем и
, а секретный ключ
.
,
и
. Чтобы подписать
, сначала выберем случайное число
, убеждаемся, что
. Вычисляем: