Проверка криптографической подписи хеша
Итак, все чаще в кругах, работающих с документами все чаще звучат слова «электронный документ» и, связанное с ним почти неразрывно «электронная цифровая подпись», иначе — ЭЦП.
Данный цикл статей предназначен для того, чтобы раскрыть «тайное знание» о том, что это такое, когда и как это можно и нужно использовать, какие есть плюсы и минусы.
Естественно, статьи пишутся не для специалистов по криптографии, а для тех, кто эту самую криптографию будет использовать, или же только начинает ее изучение, желая стать специалистом, поэтому я старался максимально упростить понимание всего процесса, приводя аналогии и рассматривая примеры.
Зачем нам вообще что-то подписывать? Естественно, чтобы удостоверить, что мы ознакомились с содержимым, согласны (а иногда наоборот, не согласны) с ним. А электронная подпись еще и защищает наше содержимое от подмены.
Итак, начать, естественно, стоит с того, что такое электронная цифровая подпись.
В самом примитивном случае это — результат хэш-функции. Что это такое лучше меня разъяснит википедиа, в нашем же случае главное, что с высокой степенью вероятности ее результат не повторяется для разных исходных данных, а также что результат этой функции мало того, что короче исходных данных, так еще по нему исходную информацию восстановить нельзя. Результат функции называют хэшем, а применение этой функции к данным называют хешированием. Грубо, можно назвать хэш функцию архивированием, в результате чего мы получаем очень маленькую последовательность байт, но восстановить исходные данные из такого «архива» нельзя.
Итак, мы читаем файлик в память, хэшируем прочитанное. И что, уже получаем ЭЦП? Почти. Наш результат с большой натяжкой можно назвать подписью, но, все же, полноценной подписью он не является, потому что:
1. Мы не знаем, кто сделал данную подпись
2. Мы не знаем, когда была сделана подпись
3. Сама подпись не защищена от подмены никак.
4. Ну и да, хэш функций много, какая из них использовалась для создания этого конкретного хэша?
Поэтому применять к хэшу слово «подпись» еще нехорошо, будем называть его дальше просто хэш.
Вы посылаете ваш файл другому человеку, допустим, по почте, будучи уверенными, что он точно получит и прочитает именно то, что вы послали. Он же, в свою очередь, тоже должен хэшировать ваши данные и сравнить свой результат с вашим. Если они совпали — все хорошо. Это значит что данные защищены? Нет.
Ведь хэшировать может кто угодно и когда угодно, и вы никогда не докажете, что он хэшировал не то, что вы послали. То есть, если данные будут перехвачены по дороге злоумышленником, или же тот, кому вы посылаете данные — не очень хороший человек, то данные могут быть спокойно подменены и прохэшированы. А ваш получатель (ну или вы, если получатель — тот самый нехороший человек) никогда не узнает, что он получил не то, что вы отправляли, или сам подменил информацию от вас для дальнейшего использования в своих нехороших целях.
Посему, место для использование чистой хэш функции — транспорт данных в пределах программы или программ, если они умеют общаться между собой. Собственно, с помощью хэш функций вычисляются контрольные суммы. И эти механизмы защищают от случайной подмены данных, но не защищают от специальной.
Но, пойдем дальше. Нам хочется защитить наш результат хеширования от подмены, чтобы каждый встречный не мог утверждать, что это у него правильный результат. Для этого самое очевидное что (помимо мер административного характера)? Правильно, зашифровать. А ведь с помощью шифрования же можно и удостоверить личность того, кто хэшировал данные! И сделать это сравнительно просто, ведь есть ассиметричное шифрование. Да, оно медленное и тяжелое, но ведь нам всего-то и надо — зашифровать маленькую последовательность байт. Плюсы такого действия очевидны — для того, чтобы проверить нашу подпись, надо будет иметь наш открытый ключ, по которому личность зашифровавшего (а значит, и создавшего хэш) можно легко установить.
Суть этого шифрования в следующем: у вас есть закрытый ключ, который вы храните у себя. И есть открытый ключ. Открытый ключ вы можете всем показывать и раздавать, а закрытый — нет. Шифрование происходит с помощью закрытого ключа, а расшифровывание — с помощью открытого.
Приводя аналогию, у вас есть отличный замок и два ключа к нему. Один ключ замок открывает (открытый), второй — закрывает (закрытый). Вы берете коробочку, кладете в нее какую-то вещь и закрываете ее своим замком. Так, как вы хотите, чтобы закрытую вашим замком коробочку открыл ее получатель, то вы открытый, открывающий замок, ключик спокойно отдаете ему. Но вы не хотите, чтобы вашим замком кто-то закрывал коробочку заново, ведь это ваш личный замок, и все знают, что он именно ваш. Поэтому закрывающий ключик вы всегда держите при себе, чтобы кто-нибудь не положил в вашу коробочку мерзкую гадость и не говорил потом, что это вы ее положили и закрыли своим замком.
И все бы хорошо, но тут сразу же возникает проблема, а, на самом деле, даже не одна.
1. Надо как-то передать наш открытый ключ, при этом его должна понять принимающая сторона.
2. Надо как-то связать этот открытый ключ с нами, чтобы нельзя было его присвоить.
3. Мало того, что ключ надо связать с нами, надо еще и понять, какой зашифрованный хэш каким ключом расшифровывать. А если хэш не один, а их, скажем, сто? Хранить отдельный реестр — очень тяжелая задача.
Все это приводит нас к тому, что и закрытый ключ, и наш хэш надо хранить в каких-то форматах, которые нужно стандартизировать, распространить как можно шире и уже тогда использовать, чтобы у отправителя и получателя не возникало «трудностей перевода».
Как водится у людей, к чему-то единому прийти так и не смогли, и образовалось два больших лагеря — формат OpenPGP и формат S/MIME + X.509. Но об этом уже в следующей статье.
Симметричные и асимметричные шифры
Сначала дадим краткое определение криптографических функций шифрования и дешифрования.
К функциям 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 вызвать для массива нулевой длины.
Цифровая подпись
Заключение
Создание и верификация цифровой подписи в CryptoAPI через сертификат открытого ключа
Сегодня все технологии передачи защищенных данных в Internet – обмен ключами, работа с сертификатами, алгоритмы шифрования - должны соответствовать стандарту PEM (Privacy-Enhanced Mail). Протокол X.509, который описывает структуру сертификата, является составной частью PEM.
Version |
Serial Number |
Algorithm Identifier:Algorithm Parameters |
Issuer |
Period of Validity:Not Before Date Not After Date |
Subject |
Subject’s Public KeyAlgorithmParametersPublic Key |
Signature |
Установим этот сертификат. Двойным щелчком по файлу evgeny.cer запускаем certificate import wizard. Выбираем для установки персональное хранилище (personal) и заканчиваем установку, нажав кнопку Finish.
Данная цифровая подпись преобразована в hex-вид, поэтому при верификации ее нужно преобразовать обратно в текстовый формат.
Алгоритм верификации состоит из вызова следующих функций:
- CertOpenStore - открываем хранилище сертификатов.
- CertFindCertificateInStore – находим нужный сертификат.
- CRYPT_VERIFY_MESSAGE_PARA – заполняем структуру для верификации
- CryptVerifyDetachedMessageSignature – проверяем подпись.
Результат должен быть следующим:
Верификация цифровой подписи без дополнительной информации
А теперь, предположим, вы получили цифровую подпись без дополнительной информации в hex представлении. Ее длина 256 байт или 128 байт в текстовом виде.
Вы также получили и сертификат с открытым ключом. Используя только функции для работы с сертификатами, вы не сможете верифицировать такую подпись. Для верификации этой подписи нужно перейти к функциям CryptoAPI нижнего уровня, которые работают с CSP (cryptographic service provider). Все криптографические операции в операционной системе выполняются независимыми друг от друга модулями, известными как криптографические сервис провайдеры (CSP). В поставку Windows 2000 входят несколько CSP:
- Gemplus GemSAFE Card CSP v1.0
- Microsoft Base Cryptographic Provider v1.0
- Microsoft Base DSS and Diffie-Hellman Cryptographic Provider
- Microsoft Base DSS Cryptographic Provider
- Microsoft DH SChannel Cryptographic Provider
- Microsoft Enhanced Cryptographic Provider v1.0
- Microsoft Enhanced DSS and Diffie-Hellman Cryptographic Provider
- Microsoft RSA SChannel Cryptographic Provider
- Microsoft Strong Cryptographic Provider
- Schlumberger Cryptographic Service Provider
Процесс верификации заключается в вызове следующих функций:
Результат должен быть следующим:
После верификации двух цифровых подписей рассмотрим алгоритм их создания.
Мы должны получить цифровую подпись, приведённую в начале статьи.
- CertOpenStore - открывает хранилище сертификатов.
- CertFindCertificateInStore – находит нужный сертификат.
- CRYPT_SIGN_MESSAGE_PARA – заполнение структуры для создания подписи
- CryptSignMessage – создаем подпись.
Результат должен быть следующим:
Cоздание обычной цифровой подписи
Теперь создадим обычную подпись, используя наш сертификат (файл evgeny.pfx), размером 256 байт в hex-представлении. Как и в случае верификации такой подписи, воспользуемся функцией CryptAcquireCertificatePrivateKey. Она обеспечит переход от сертификата к соответствующему дескриптору CSP. Используя дескриптор, нам осталось получить подпись.
Ниже представлена последовательность действий.
CertOpenStore - открывает хранилище сертификатов.
CertFindCertificateInStore – находит нужный сертификат.
CryptAcquireCertificatePrivateKey –получает дескриптор CSP провайдера соответствующего нашему сертификату.
CryptCreateHash – создает хэш
CryptSignHash – шифрует созданный хэш
Результат должен быть следующим:
Выясняем, как и откуда можно получить электронную подпись на примере криптосистемы RSA.
Содержание
Определения и обозначения
Описание криптосистемы RSA
Асимметричные криптографические системы
Шифрование и дешифрование
Электронная подпись документов
Заключение
Вот мы и прошли все стадии создания электронной подписи, начиная с простой модульной арифметики и заканчивая, собственно, получением подписи. Обладая этими знаниями, вы можете попробовать перевести их на ваш любимый язык программирования и написать свою защищенную аську, например. В том, как именно их применить, вас ограничит только ваше воображение.
Отмечу, что другие существующие алгоритмы создания ЭП основаны на схожих принципах, поэтому надеюсь, что после прочтения этой статьи вам будет проще разобраться в них. "Следующей по сложности" я обозначу криптосистему Эль-Гамаля, но о ней уже не в этом посте.
Спасибо за внимание!
Как оно устроено
Прежде, чем окунуться в необъятный мир математики рассмотреть, как именно устроена RSA, обратимся к тому, как работают
Подпись документов
Рассмотренный алгоритм получения подписи изящен и прост в осознании, однако операция возведения в степень несколько "мешается". Наша текущая задача – подписать объёмный документ. Чтобы сэкономить время, мы не будем подписывать содержимое документа, а прибегнем к помощи хэш-функций (если вы не знаете, что такое хэш-функция, рекомендую почитать википедию). Скажу лишь то, что выходная последовательность хэш-функции имеет небольшую (по сравнению с размером ключей) длину, а также по имеющемуся хэшу нельзя однозначно восстановить исходные данные.
На картинках наглядно показано, в какой момент мы используем хэширование. Создание подписи:
В качестве хэш-функции можно использовать SHA-256, как это сделано, например, в PGP. По теме практического создания электронной подписи с использованием PGP на хабре уже написана статья, поэтому на этом месте имеет смысл поставить точку и перейти к заключению.
Асимметричные криптосистемы
Рассмотрим задачу сохранности содержимого посылки при передаче от отправителя к адресату. Вот картинка с многим полюбившимся Алисой и Бобом:
Общие сведения
Криптографическая хеш-функция - это математический алгоритм, который отображает данные произвольного размера в битовый массив фиксированного размера.
Для идеальной хеш-функции выполняются следующие условия:
Давайте сразу рассмотрим пример воздействия хеш-функции SHA3-256.
Число 256 в названии алгоритма означает, что на выходе мы получим строку фиксированной длины 256 бит независимо от того, какие данные поступят на вход.
На рисунке ниже видно, что на выходе функции мы имеем 64 цифры шестнадцатеричной системы счисления. Переводя это в двоичную систему, получаем желанные 256 бит.
Любой заинтересованный читатель задаст себе вопрос: "А что будет, если на вход подать данные, бинарный код которых во много раз превосходит 256 бит?"
Ответ таков: на выходе получим все те же 256 бит!
Дело в том, что 256 бит - это соответствий, то есть различных входов имеют свой уникальный хеш.
Чтобы прикинуть, насколько велико это значение, запишем его следующим образом:
Надеюсь, теперь нет сомнений в том, что это очень внушительное число!
Поэтому ничего не мешает нам сопоставлять длинному входному массиву данных массив фиксированной длины.
Итоги
В данной статье я постарался объяснить, что такое хеш-функция и зачем она нужна
Также в общих чертах мной был разобран принцип работы алгоритма SHA-3 Keccak, который является последним стандартизированным алгоритмом семейства Secure Hash Algorithm
Шифруем, дешифруем.
Здесь за с обозначен шифртекст, который Алиса будет должна передать Бобу. Отметим также, что c ∈ [1, n − 1], как и m. Расшифруем шифртекст, возведя его в степень закрытого ключа Боба d:
А теперь ответим на вопрос, почему m ≡ m′ . Ниже я приведу доказательство данного утверждения, но если оно (доказательство) вам не сильно интересно, то можете его пропустить и просто поверить, что это так.
Здесь нам понадобится теорема Эйлера:
Также полезной будет китайская теорема об остатках:
Ещё раз напишем две ключевые формулы шифрования и расшифрования соответственно:
Если Алиса получила, что m ≡ m′, то подпись считается правильной.
Дочитавших до этого места хочу поздравить с получением первой цифровой подписи "на бумаге"!
Применение хеш-функций
Рассмотрим несколько достаточно простых примеров применения хеш-функций:
• Верификация пароля
Проверка пароля обычно использует криптографические хеши. Хранение всех паролей пользователей в виде открытого текста может привести к массовому нарушению безопасности, если файл паролей будет скомпрометирован. Одним из способов уменьшения этой опасности является хранение в базе данных не самих паролей, а их хешей. При выполнении хеширования исходные пароли не могут быть восстановлены из сохраненных хеш-значений, поэтому если вы забыли свой пароль вам предложат сбросить его и придумать новый.
• Цифровая подпись
Подписываемые документы имеют различный объем, поэтому зачастую в схемах ЭП подпись ставится не на сам документ, а на его хеш. Вычисление хеша позволяет выявить малейшие изменения в документе при проверке подписи. Хеширование не входит в состав алгоритма ЭП, поэтому в схеме может быть применена любая надежная хеш-функция.
Предлагаю также рассмотреть следующий бытовой пример:
Алиса ставит перед Бобом сложную математическую задачу и утверждает, что она ее решила. Боб хотел бы попробовать решить задачу сам, но все же хотел бы быть уверенным, что Алиса не блефует. Поэтому Алиса записывает свое решение, вычисляет его хеш и сообщает Бобу (сохраняя решение в секрете). Затем, когда Боб сам придумает решение, Алиса может доказать, что она получила решение раньше Боба. Для этого ей нужно попросить Боба хешировать его решение и проверить, соответствует ли оно хеш-значению, которое она предоставила ему раньше.
Теперь давайте поговорим о SHA-3.
Национальный институт стандартов и технологий (NIST) в течение 2007—2012 провёл конкурс на новую криптографическую хеш-функцию, предназначенную для замены SHA-1 и SHA-2.
Организаторами были опубликованы некоторые критерии, на которых основывался выбор финалистов:
Способность противостоять атакам злоумышленников
• Производительность и стоимость
Вычислительная эффективность алгоритма и требования к оперативной памяти для программных реализаций, а также количество элементов для аппаратных реализаций
• Гибкость и простота дизайна
Гибкость в эффективной работе на самых разных платформах, гибкость в использовании параллелизма или расширений ISA для достижения более высокой производительности
В финальный тур попали всего 5 алгоритмов:
Победителем и новым SHA-3 стал алгоритм Keccak.
Давайте рассмотрим Keccak более подробно.
Свойства
Криптографическая хеш-функция должна уметь противостоять всем известным типам криптоаналитических атак.
В теоретической криптографии уровень безопасности хеш-функции определяется с использованием следующих свойств:
Pre-image resistance
Second pre-image resistance
Имея заданное входное значение , должно быть сложно найти другое входное значение такое, что
Collision resistance
Давайте чуть более подробно поговорим о каждом из перечисленных свойств.
Несмотря на то, что хеш-функций без коллизий не существует, некоторые из них достаточно надежны и считаются устойчивыми к коллизиям.
Second pre-image resistance. Это свойство называют сопротивлением второму прообразу. Для упрощения можно сказать, что это свойство находится где-то посередине между двумя предыдущими. Атака по нахождению второго прообраза происходит, когда злоумышленник находит определенный вход, который генерирует тот же хеш, что и другой вход, который ему уже известен. Другими словами, злоумышленник, зная, что пытается найти такое, что
Отсюда становится ясно, что атака по нахождению второго прообраза включает в себя поиск коллизии. Поэтому любая хеш-функция, устойчивая к коллизиям, также устойчива к атакам по поиску второго прообраза.
Неформально все эти свойства означают, что злоумышленник не сможет заменить или изменить входные данные, не меняя их хеша.
В частности, хеш-функция должна вести себя как можно более похоже на случайную функцию, оставаясь при этом детерминированной и эффективно вычислимой.
Функция перестановок
Базовая функция перестановки состоит из раундов по пять шагов:
Тета, Ро, Пи, Хи, Йота
Далее будем использовать следующие обозначения:
Так как состояние имеет форму массива , то мы можем обозначить каждый бит состояния как
Обозначим результат преобразования состояния функцией перестановки
Также обозначим функцию, которая выполняет следующее соответствие:
- обычная функция трансляции, которая сопоставляет биту бит ,
где - длина слова (64 бит в нашем случае)
Я хочу вкратце описать каждый шаг функции перестановок, не вдаваясь в математические свойства каждого.
Шаг
Эффект отображения можно описать следующим образом: оно добавляет к каждому биту побитовую сумму двух столбцов и
Схематическое представление функции:
Шаг
Отображение направлено на трансляции внутри слов (вдоль оси z).
Проще всего его описать псевдокодом и схематическим рисунком:
Шаг
Шаг представляется псевдокодом и схематическим рисунком:
Шаг
Шаг является единственный нелинейным преобразованием в
Псевдокод и схематическое представление:
Шаг
Отображение состоит из сложения с раундовыми константами и направлено на нарушение симметрии. Без него все раунды были бы эквивалентными, что делало бы его подверженным атакам, использующим симметрию. По мере увеличения раундовые константы добавляют все больше и больше асимметрии.
Ниже приведена таблица раундовых констант для бит
Все шаги можно объединить вместе и тогда мы получим следующее:
Где константы являются циклическими сдвигами и задаются таблицей:
Теорминимум
(На картинке изображён Лев Ландау, автор «теорминимума», серии экзаменов по теоретической физике)
Сформируем небольшой словарик терминов, которые нам пригодятся далее:
Открытый текст – данные, подлежащие шифрованию или полученные в результате расшифрования
Шифртекст – данные, полученные в результате применения шифра к открытому тексту
Шифр – совокупность обратимых преобразований, зависящая от некоторого параметра (ключа)
Ключ – параметр шифра, определяющий выбор одного преобразования из совокупности.
Факторизация – процесс разложения числа на простые множители.
НОД – наибольший общий делитель.
Числа a и b называются взаимно простыми, если НОД этих чисел равен 1.
Функция Эйлера φ(n) – функция, равная количеству натуральных чисел, меньших n и взаимно простых с ним.
Хочу отметить, что на данном этапе подразумевается, что вы знакомы с арифметическими операциями по модулю. Если нет, то здесь можно о них почитать.
Введение
Наверняка вы сталкивались с таким понятием, как "электронная подпись". Если обратиться к федеральному закону, то можно найти следующее её определение:
«Электронная подпись - информация в электронной форме, которая присоединена к другой информации в электронной форме (подписываемой информации) или иным образом связана с такой информацией и которая используется для определения лица, подписывающего информацию»
Задача ЭП ясна, теперь хотелось бы увидеть и прочувствовать, что именно скрывается за этими двумя словами. Копаясь дальше в гугле, можно найти довольно много различных алгоритмов создания цифровой подписи (DSA, ГОСТ Р 34.10-2012, RSA-PSS и т.д.), разбираться в которых неподготовленному пользователю сложно.
Спасти эту ситуацию и помочь разобраться в том, что есть ЭП, может криптосистема RSA, разработанная Ривестом, Шамиром и Адлеманом в 1978 году. Она не загромождена безумным количеством алгоритмов и основывается на относительно простой математике. В связи с этим можно шаг за шагом прийти от модульной арифметики к алгоритму создания электронной подписи, чему я и хочу посвятить данную статью.
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.
• «Отжимание»: пока длина результата меньше чем , где - количество бит в выходном массиве хеш-функции, первых бит строки состояния добавляется к результату . После каждой такой операции к строке состояния применяется функция перестановок и данные продолжают «отжиматься» дальше, пока не будет достигнуто значение длины выходных данных .
Все сразу станет понятно, когда вы посмотрите на картинку ниже:
Функция дополнения
Источники
Handbook of Applied Cryptography by A. Menezes, P. van Oorschot and S. Vanstone
Криптографические методы защиты информации: учеб. пособие / С. М. Владимиров, Э. М. Габидулин, А. И. Колыбельников, А. С. Кшевецкий; под ред. А. В. Уривского. – М.: МФТИ, 2016
Маховенко Е. Б. Теоретико-числовые методы в криптографии — М.: Гелиос АРВ, 2006.
NIST Special Publication 800-57 Part 3 Revision 1
Молдовян Н.А. Теоретический минимум и алгоритмы цифровой подписи. – СПб.: БХВ-Петербург, 2010. - Учебное пособие
Сегодня я хотел бы рассказать о том, что из себя представляет хеш-функция, коснуться её основных свойств, привести примеры использования и в общих чертах разобрать современный алгоритм хеширования SHA-3, который был опубликован в качестве Федерального Стандарта Обработки Информации США в 2015 году.
Теперь к математике
Асимметричные криптографические системы основаны на так называемых односторонних функциях с секретом. Под односторонней понимается такая функция я y=f(x), которая легко вычисляется при имеющемся x, но аргумент x при заданном значении функции вычислить сложно. Аналогично, односторонней функцией с секретом называется функция y=f(x, k), которая легко вычисляется при заданном x, причём при заданном секрете k аргумент x по заданному y восстановить просто, а при неизвестном k – сложно.
Подобным свойством обладает операция возведения числа в степень по модулю:
Что есть что разобрались, теперь перейдём к конкретике, а именно – генерации ключей Боба. Давайте выберем число n такое, что:
где p и q – некоторые разные простые числа. Для такого n функция Эйлера имеет вид:
Такой выбор n обусловлен следующим. Как вы могли заметить ранее, закрытый ключ d можно получить, зная открытый e. Зная числа p и q, вычислить функцию Эйлера не является вычислительно сложной задачей, ровно как и нахождение обратного элемента по модулю. Однако в открытом ключе указано именно число n. Таким образом, чтобы вычислить значение функции Эйлера от n (а затем получить закрытый ключ), необходимо решить задачу факторизации, которая является вычислительно сложной задачей для больших n (в современных системах, основанных на RSA, n имеет длину 2048 бит).
Возвращаемся к генерации ключей. Выберем целое число e:
Для него вычислим число d:
Для отыскания числа, обратного по модулю, можно воспользоваться алгоритмом Евклида.
Мы завершили с этапом генерации ключей. Теперь Боб публикует свой открытый ключ (e, n), прячет закрытый d, а мы переходим к Алисе.
Читайте также: