Проверка криптографической подписи хеша

Обновлено: 06.07.2024

Симметричные и асимметричные шифры

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

К функциям E(.) и D(.) предъявляются следующие требования:

Надежность шифра определяется именно по его соответствию вышеперечисленным требованиям, при этом считается, что алгоритмы вычисления E(.) и D(.) известны всем (есть еще вариант так называемой Security by obscurity, т.е. защиты из-за неизвестности алгоритма, но он при оценке стойкости шифров не рассматривается).

Если K1=K2, то шифр называется симметричным, в противном случае – асимметричным. Примеры известных симметричных шифров – DES, IDEA, Blowfish, ГОСТ, асимметричных – RSA, ECC.

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

Алгоритм RSA

Для генерации ключевой пары выбираются два больших (по современным требованиям надежности не менее 512 бит) простых числа (некоторые популярные алгоритмы их генерации рассмотрены в [1]) p и q . Затем вычисляется их произведение n = p * q и выбирается случайное число e , так что e взаимно просто с ( p -1)*( q -1). Также вычисляется число d , такое, что d * e =1 mod ( p -1)*( q -1) (эта операция делается с помощью расширенного алгоритма Евклида, см. [1]). Это означает, что

Шифрование осуществляется следующим способом:

c =m^ e mod n (возведение m в степень e по модулю n ),

а дешифрование производится так:

Гарантию того, что получится верный результат, дает малая теорема Ферма. Для любого a меньше, либо равного n:

a^ phi(n) =1 mod n , где phi(n) – число целых положительных чисел меньших n и взаимно простых с ним. Для n = p * q , phi(n)= ( p -1)*( q -1) и

(m^ e )^ d mod n = m^(1+k* phi(n) ) mod n=m.

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

Задача нахождения такого u (отличного от m), чтобы H(u)=h, должна являться трудной при неизвестном m.

Задача нахождения такого u, что H(u)=H(m) является трудной при известном m.

Цифровая подпись

Обмен ключами

Работа с CryptoAPI

Криптопровайдеры, инициализация и деинициализация

Любой сеанс работы с CryptoAPI начинается с инициализации (получения контекста). Инициализация выполняется при помощи функции CryptAcquireContext . В качестве параметров эта функция принимает имя контейнера ключей, имя криптопровайдера, тип провайдера и флаги, определяющие тип и действия с контейнером ключей и режим работы криптопровайдера:

Криптопровайдер – это сущность (обычно библиотека), реализующая определенный набор криптографических алгоритмов и обеспечивающая работу с ними. Существует около семи стандартных провайдеров, предустановленных в системе. Нам для примеров понадобятся два из них – Microsoft Base Cryptographic Provider (MS_DEF_PROV) и Microsoft Enhanced Cryptographic Provider (MS_ENHANCED_PROV) .

ПРИМЕЧАНИЕ

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

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

ПРИМЕЧАНИЕ

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

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

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

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

Следующий пример демонстрирует инициализацию CryptoAPI для последующего вычисления хеша MD5:

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

Генерация ключей и обмен ключами

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

Первый и четвертый параметры говорят сами за себя. Вторым параметром передается идентификатор алгоритма шифрования, для которого генерируется ключ (например, CALG_3DES ). При генерации ключевых пар RSA для шифрования и подписи используются специальные значения AT_KEYEXCHANGE и AT_SIGNATURE . Третий параметр задает различные опции ключа, которые зависят от алгоритма и провайдера. Например, старшие 16 битов этого параметра могут задавать размер ключа для алгоритма RSA. Подробное описание всех флагов можно найти в MSDN. Здесь я упомяну только один флаг - CRYPT_EXPORTABLE, который позволяет экспортировать закрытые ключи RSA из контейнера (по умолчанию это запрещено). Для других ключей этот параметр смысла не имеет – открытые ключи являются свободно экспортируемыми, а сессионные ключи вообще не хранятся внутри контейнера, так что их обязательно нужно экспортировать.

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

Обмен ключами в CryptoAPI реализуется с помощью функций CryptExportKey и CryptImportKey , имеющих следующие прототипы:

В качестве ключей экспорта/импорта могут использоваться либо ключевая пара RSA (с типом AT_KEYEXCHANGE), либо симметричный сеансовый ключ. Параметр dwBlobType зависит от того, какой ключ экспортируется (импортируется), и задает тип структуры, в которую помещается экспортируемый ключ. Для открытого ключа это PUBLICKEYBLOB, и ключ экспорта/импорта при этом лишен смысла и должен быть нулем. Для закрытого ключа это PRIVATEKEYBLOB , и в качестве ключа экспорта может использоваться сеансовый ключ. Для сеансового ключа это обычно SIMPLEBLOB (бывает еще OPAQUEKEYBLOB и SYMMETRICWRAPKEYBLOB , но мы их рассматривать не будем), а экспортируется он, как правило, на открытом ключе получателя.

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

После окончания работы с ключом, его нужно уничтожить вызовом CryptDestroyKey .

ПРИМЕЧАНИЕ

При этом закрытый ключ сохраняется в контейнере (если, конечно, не использовался режим CRYPT_VERIFYCONTEXT), а сессионные ключи уничтожаются совсем.

В качестве примера рассмотрим создание и экспорт пары ключей для шифрования RSA и симметричного ключа 3DES:

Рабочие примеры генерации и импорта/экспорта ключей приведены в демонстрационных проектах rsakg и encfile.

Симметричные шифры DES и 3DES

Это одни из немногих симметричных шифров, предоставляемых стандартными криптопровайдерами CryptoAPI. Поскольку DES и 3DES – это практически один и тот же алгоритм (3DES – это DES, применяемый 3 раза подряд), то мы ограничимся примером использования алгоритма 3DES.

ПРИМЕЧАНИЕ

Однако заметим, что для использования алгоритма 3DES требуется Enhanced провайдер, а для DES вполне достаточно Base. Впрочем, DES уже не является стойким по современным меркам алгоритмом, поэтому использовать его стоит лишь там, где надежность шифрования не очень критична.

Алгоритм 3DES использует разные ключи DES для каждой из своих итераций. Поэтому размер его ключа равен тройному размеру ключа DES, т.е. 192 (64*3) бита. Реально размер ключа 3DES – 168 (56*3) бит, т.к. в DES один байт ключа является контрольным для основных семи. Шифрование и дешифрование выполняются с помощью функций:

Параметр hHash позволяет параллельно с шифрованием/дешифрованием проводить хеширование данных для последующей электронной подписи или ее проверки. Флаг Final определяет, является ли шифруемый блок данных последним. Он необходим, поскольку данные можно шифровать по кускам, но для последнего блока всегда выполняется определенная деинициализация алгоритма (освобождаются внутренние структуры), и многие алгоритмы производят добавление (и проверку корректности при дешифровании) заполнителя (padding) после основных данных. Параметры pbData и pdwDataLen задают адрес буфера и размер шифруемых данных. Для не последнего блока данных ( Final =FALSE) размер данных должен быть всегда кратен размеру шифруемого алгоритмом блока (для 3DES и DES этот размер равен 64 битам). Для последнего блока допускается нарушение этого условия.

ПРИМЕЧАНИЕ

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

Последний параметр функции CryptEncrypt – dwBufLen может показаться странным. Зачем нам размер буфера, если мы и так знаем размер входных данных? Однако на самом деле он необходим. Как я уже упомянул, многие алгоритмы добавляют заполнитель в последний блок после основных данных. В этом случае размер зашифрованных данных может оказаться больше, чем размер исходных данных. И результат может попросту не вместиться в буфер! Поэтому стоит заранее указать размер буфера, превышающий максимальный размер помещаемых в него открытых данных. Для DES и 3DES максимально возможный довесок составляет 64 бита, т.е. 8 байт (это я установил опытным путем).

В качестве примера шифрования приведу выдержку из демонстрационного проекта encfile:

Асимметричный шифр RSA

Начиная с Windows 2000 расширенный (Enhanced) криптопровайдер поддерживает прямое шифрование данных по алгоритму RSA. Максимальный размер данных, которые можно зашифровать за один вызов CryptEncrypt , равен размеру ключа минус 11 байт. Дело в том, что при шифровании добавляется обязательный заполнитель (padding), который впоследствии проверяется при дешифрации. Соответственно, использование шифра RSA может быть целесообразно только при небольших объемах шифруемых данных (например, при обмене ключами) из-за существенного увеличения объема шифрованного текста и относительно медленной работе алгоритма RSA по сравнению с блочными шифрами.

Хеши MD5 и SHA

Хеш создается вызовом функции CryptCreateHash , принимающей на входе контекст криптопровайдера, идентификатор алгоритма ( CALG_MD5 или CALG_SHA) и хендл ключа (для хешей с ключем типа MAC и HMAC). После этого хеш можно вычислять как явно, используя функцию CryptHashData , так и неявно, передавая хэндл хеша в функцию CryptEncrypt . Использование CryptEncrypt обсуждалось в разделе про DES, поэтому остановимся на функции CryptHashData . Ее вызов может выглядеть следующим образом:

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

Размер хеша MD5 равен 128 бит или 16 байтов. Для SHA это 160 бит или 20 байтов. После получения значения хеш использовать уже нельзя. Его нужно разрушить вызовом CryptDestroyHash . Проверка хеша производится точно также, как и его создание – нужно вычислить хеш и сверить полученное значение с сохраненным:

Алгоритмы цифровой подписи RSA и DSS

Позволяют установить корректность данных (точнее, их хеша) и принадлежность подписи владельцу закрытого ключа. Функции CryptoAPI позволяют подписывать только хеши, но не сами данные. Хеш предварительно должен быть вычислен (см. предыдущую главу), а затем подписан с помощью функции CryptSignHash на закрытом ключе для подписи (AT_KEYEXCHANGE) находящейся в контейнере криптопровайдера! Проверка подписи осуществляется на открытом ключе, который нужно предварительно импортировать:

Практический пример применения подписи можно увидеть в демонстрационном проекте encfile. Вычисление/проверка подписи RSA и DSS выполняется одинаково, однако для работы с подписью DSS нужно использовать Microsoft DSS Cryptographic Provider ( MS_DEF_DSS_PROV ,тип PROV_DSS ). Кроме того, подпись DSS работает только с алгоритмом хеширования SHA.

Симметричные шифры DES, 3DES, Rijndael

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

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

На вторые возможные грабли я наступил в коде дешифрования. Размер расшифрованных данных для не финального блока может быть меньше размера шифротекста. Ни с чем подобным в CryptoAPI я не сталкивался.

Асимметричные шифры и цифровая подпись: RSA и DSA

Заявленные в классах RSACryptoServiceProvider и DSACryptoServiceProvider методы SignHash не работают. Вообще! При попытке передать в них хеш, сформированный с помощью MD5CryptoServiceProvider или SHA1CryptoServiceProvider , всегда вываливается исключение.

Поэтому приходится использовать классы RSAPKCS1SignatureFormatter и DSASignatureFormatter .

ПРЕДУПРЕЖДЕНИЕ

Не верьте этому! При попытке подсунуть блок данных длиной в 117 байт при длине ключа 1024 бита вы получите исключение. У меня получилось, что максимальный размер блока данных при таком размере ключа равен 87 байтам, т.е. на 30 байт меньше заявленного.

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

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

Метод Decrypt , обратный методу Encrypt , не может расшифровать зашифрованный блок данных, если его первоначальный размер был больше 86 байтов (для 1024-битных ключей). Т.е. вы можете зашифровать блок из 87 байтов, но потом вы не сможете его расшифровать.

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

Обмен симметричными ключами

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

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

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

Цифровая подпись

Заключение

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

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

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

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

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

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

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

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

Ответ таков: на выходе получим все те же 256 бит!
Дело в том, что 256 бит - это соответствий, то есть различных входов имеют свой уникальный хеш.
Чтобы прикинуть, насколько велико это значение, запишем его следующим образом:

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

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

Свойства

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

Pre-image resistance

Second pre-image resistance

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

Collision 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Шаг

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

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

Шаг

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

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

Шаг

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

Шаг

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

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

Шаг

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

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

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

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

Итоги

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

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

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

построения систем контроля целостности данных при их передаче или хранении,
аутентификация источника данных.

$\begin H_0=v, \\ \\ H_i= f(M_i, H_), i=1,\dots,N, \\ \\ h(M)=H_N. \\ \end$

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

9.2 Электронная подпись

9.2.1 Общие положения

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

Задачи, которые решает подпись:

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

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

Некоторые наиболее употребительные схемы ЭЦП

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

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

9.2.2 Схема Эль-Гамаля

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

$r=g^<k> (\mod p) \qquad \text\qquad s = (M-xr)\cdot k^ (\mod (p-1)).$

Для проверки подписи нужно убедиться, что

$<y> ^ \cdot ^ Схема Эль-Гамаля послужила образцом для построения большого семейства во многом сходных по своим свойствам схем подписи. Пример 9.1 Выберем и , а секретный ключ . <img class=$
- число, обратное по модулю , " />
существует, так как и - взаимно просты.

Используемые на практике алгоритмы хеширования достаточно сложны, поэтому будем использовать учебные алгоритмы формирования хеш-значения . Схему учебных алгоритмов хэширования предложила Васильева И.Н. [1].

Первый учебный алгоритм хеширования

$p=79,\qquad g=15,\qquad x=34,\qquad k=17.$

$\begin<equation*> \begin h_1=(h_0+n_1)^2 (\mod 79) =36, \\ h_2=(h_1+n_2)^2 (\mod 79) =31, \\ h_3=(h_2+n_3)^2 (\mod 79) =26 \\ h_4 = (h_3+n_4)^2 (\mod p)$
. Для рассматриваемого примера получили:

- отрицательное, следует взять его по модулю .

$s=23 \cdot 5 (\mod 79-1)=37.$

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

(\mod p)" />
, а затем их произведение по модулю .

$\begin<equation*> \begin y^ (\mod p)= 38\cdot 27 <img class=$

(\mod p)" />
, значение было получено ранее.

$g^ В примере (\mod p)$
, если равенство выполняется - подпись подлинная, то есть она была вычислена правильно.

В примере получили , равенство выполняется, значит, подпись сгенерирована правильно.

Второй учебный алгоритм хеширования

Начальное значение принимается равным числу десятичных разрядов в .

$h_i =(M_i+ 2\cdot h_<i-1> +1)^ (\mod p-1),\ i=1,\dots,n.$

(\mod p)" />
, а затем их произведение по модулю :

$\begin<equation*> \begin y^ (\mod p)= 35\cdot 15 (\mod 58) = 24;\\ h_2 = (5 + 2\cdot 24 + 1)^2 (\mod 58) = 16;\\ h_3 = (6 + 2\cdot 16 + 1)^2 (\mod 58) = 13;\\ h_4 = (9 + 2\cdot 13 + 1)^2 (\mod 58) = 20;\\ h = h_4 + 1 = 21; \end$

$g^ В примере (\mod p)$
, если равенство выполняется - подпись подлинная, в противном случае - фальшивая.

$53\neq 6$

В нашем примере . Равенство не выполняется, значит, подпись фальшивая.

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

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

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

Функционально цифровая подпись аналогична обычной рукописной подписи и обладает ее основными достоинствами:

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

Электронная цифровая подпись представляет собой относительно небольшое количество дополнительной цифровой информации, передаваемой вместе с подписываемым текстом.

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

Система ЭЦП включает две основные процедуры:

процедуру формирования цифровой подписи;
процедуру проверки цифровой подписи.

Процедура формирования цифровой подписи

Рис. 1. Схема формирования электронной цифровой подписи.

Процедура проверки цифровой подписи

Рис. 3. Схема проверки электронной цифровой подписи

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

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

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

Рис. 4. USB-токен Рутокен ЭЦП 2.0.

дату подписи;
срок окончания действия ключа данной подписи;
информацию о лице, подписавшем файл (Ф.И.О., должность, краткое наименование фирмы);
идентификатор подписавшего (имя открытого ключа);
собственно цифровую подпись.

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

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

прочитать из файла, в котором содержится открытый ключ К_А, идентификационную информацию об абоненте А;
сгенерировать собственную пару ключей k_n и K_n, записав в них идентификационную информацию абонента A;
подменить хранящийся у абонента B открытый ключ К_А своим открытым ключом K_n, но содержащим идентификационную информацию абонента A.

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

Рис. 5. Защита открытых ключей с помощью удостоверяющего центра.

Сегодня существует большое количество алгоритмов ЭЦП.

Описание алгоритма.

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

Рис. 6. Иллюстрация работы DSA.

Генерация ключей DSA.

Отправитель и получатель электронного документа используют при вычислениях большие целые числа:

g и p – простые числа длиной L битов каждое (512 <=L <=1024);

q –простое число длиной 160 бит (делитель числа (p – 1)). Числа g, p, q являются открытыми и могут быть общими для всех пользователей сети.

Отправитель выбирает случайное целое число x, 1 < x < q. Число x является секретным ключом отправителя для формирования электронной цифровой подписи.

Затем отправитель вычисляет значение

Число y является открытым ключом для проверки подписи отправителя. Число y передается всем получателям документов.

Генерация подписи DSA. Этот алгоритм предусматривает использование односторонней функции хэширования h(・). В первых редакциях стандарта определен алгоритм безопасного хэширования SHA-1.

Проверка подписи DSA.

Для того чтобы проверить подпись (r, s) на М участника A, участник B делает следующие шаги:

1. Получает подлинную копию открытого ключа y участника А.

4. Используя открытый ключ y, вычисляет значение
v = ((g u 1 y u 2 )mod p) mod q.

5. Признает подпись (r, s) под документом M подлинной, если v = r.

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

ГОСТ Р 34.10-2012 (полное название: «ГОСТ Р 34.10-2012. Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи») — российский стандарт, описывающий алгоритмы формирования и проверки электронной цифровой подписи. Принят и введён в действие Приказом Федерального агентства по техническому регулированию и метрологии от 7 августа 2012 года № 215-ст вместо ГОСТ Р 34.10-2001. До ГОСТ Р 34.10-2001 действовал стандарт ГОСТ Р 34.10-94.

Цифровая подпись позволяет:

Данный алгоритм разработан главным управлением безопасности связи Федерального агентства правительственной связи и информации при Президенте Российской Федерации при участии Всероссийского научно-исследовательского института стандартизации. Разрабатывался взамен ГОСТ Р 34.10-94 для обеспечения большей стойкости алгоритма.

ГОСТ Р 34.10-2012 и ГОСТ Р 34.10-2001 основаны на эллиптических кривых. Стойкость этих алгоритмов основывается на сложности вычисления дискретного логарифма в группе точек эллиптической кривой, а также на стойкости хэш-функции. Для ГОСТ Р 34.10-2012 используется хэш-функция по ГОСТ Р 34.11-2012. Для ГОСТ Р 34.10-2001 — ГОСТ Р 34.11-94.

Эллиптическая кривые описываются уравнением вида

Каноническая форма (форма Вейерштрасса):

где a и b — вещественные числа.

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

Рис. 7. Различные формы эллиптических кривых (b=1, a изменяется от 2 до -3).

Механизм цифровой подписи определяется посредством реализации двух основных процессов

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

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

Необходимо прочесть документ ГОСТ Р 34.10-2012 во время занятий по самоподготовке.

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

Простая электронная подпись, или ПЭП

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

Где используется?

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

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

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

правила, по которым подписанта определяют по его простой электронной подписи.

обязанность пользователя соблюдать конфиденциальность закрытой части ключа ПЭП (например, пароля в паре “логин-пароль” или СМС-кода, присланного на телефон).

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

Неквалифицированная электронная подпись, или НЭП

Усиленная неквалифицированная электронная подпись (далее — НЭП) создается с помощью программ криптошифрования с использованием закрытого ключа электронной подписи. НЭП идентифицирует личность владельца, а также позволяет проверить, вносили ли в файл изменения после его отправки.

Человек получает в удостоверяющем центре два ключа электронной подписи: закрытый и открытый. Закрытый ключ хранится на специальном ключевом носителе с пин-кодом или в компьютере пользователя.

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

Соответствие открытого ключа владельцу закрытого ключа прописывается в сертификате электронной подписи, который также выдается удостоверяющим центром. Требования к структуре неквалифицированного сертификата не установлены в федеральном законе № 63-ФЗ “Об электронной подписи”. При использовании НЭП сертификат можно не создавать.

Где используется?

НЭП необходима, чтобы участвовать в электронных госзакупках по 44-ФЗ в качестве поставщика на шести федеральных электронных торговых площадках госзакупок. Этот же вид подписи можно использовать для внутреннего и внешнего ЭДО, если стороны предварительно договорились об этом.

Участникам ЭДО нужно соблюдать дополнительные условия, чтобы электронные документы, заверенные НЭП, считались равнозначными бумажным с собственноручной подписью. Сторонам нужно обязательно заключить между собой соглашение о правилах использования НЭП и взаимном признании ее юридической силы.

Квалифицированная электронная подпись, или КЭП

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

Обязательно имеет квалифицированный сертификат в бумажном или электронном виде, структура которого определена приказом ФСБ России № 795 от 27.12.2011.

Программное обеспечение для работы с КЭП сертифицировано ФСБ России.

Выдавать КЭП может только удостоверяющий центр, который аккредитован Минкомсвязи России.

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

КЭП — это подпись, которая придает документам юридическую силу без дополнительных условий. Если организации ведут ЭДО, подписывая документы КЭП, их юридическая сила признается автоматически согласно федеральному закону № 63-ФЗ “Об электронной подписи”.

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