Какие математические алгоритмы используются в электронной подписи
В этой части сделаем небольшое отступление от цифровых подписей в сторону того, без чего непосредственно цифровых подписей, да и защиты информации в привычном понимании, не было бы: шифрования. Ведь первое, что приходит на ум, когда идет речь о защите наших данных — это не дать эти данные нехорошему человеку прочитать. Поэтому, перед тем, как продолжить рассмотрение стандартов PGP и S/MIME, стоит закрасить некоторые остающиеся в знаниях белые пятна, и рассмотреть процесс шифрования немного поподробнее.
Шифры и коды существуют, наверное, с того момента, как человечество научилось записывать свои впечатления об окружающем мире на носителях. Если немного вдуматься, даже обыкновенный алфавит — уже шифр. Ведь когда мы читаем какой-либо текст, в нашей голове каждому нарисованному символу сопоставляется некий звук, сочетание звуков, или даже целое понятие, а в голове соседа, который читать не умеет, этого уже не происходит.
Не зная, какому символу и что сопоставлено, мы никогда не сможем понять, что же именно писавший имел ввиду. К примеру, попробуйте взять и прочитать что-то, написанное на иврите, или на китайском языке. Сами алфавиты этих языков будут являться для вас непреодолимым препятствием, даже если с помощью этих символов написаны понятия вашего родного языка.
Но, тем не менее, простое использование чужого алфавита все же недостаточная мера для защиты ваших данных. Ведь любой алфавит, так или иначе, создавался для удобства пользования им и является неразрывно связанным с языком, которому данный алфавит характерен. А значит, выучив этот язык и некоторый набор базовых понятий на нем (а то и просто воспользовавшись услугами человека, знающего данный язык), нехороший человек может прочитать вашу информацию.
Значит, надо придумать алфавит, который знает только ограниченный круг лиц, и с его помощью записать информацию. Наверняка все читали (или, по крайней мере, слышали) цикл историй про Шерлока Холмса. В этом цикле фигурировал алфавит, составленный из пляшущих человечков (а многие, я думаю, в детстве на его основе составляли свой). Однако, как показывает данная история, наблюдательный человек может разгадать, какой символ и к чему относится. А значит наша информация опять попадет не в те руки.
Что же делать? Придумывать все более и более сложные алфавиты? Но чем более сложный и громоздкий алфавит, тем более неудобно с ним работать, хранить его в тайне. К тому же, насчет тайны есть замечательная поговорка: знают двое – знают все. Ведь самое слабое звено в любом шифре – это человек, который знает, как этот шифр расшифровать.
Вспомним же, что такое функция. Это некоторое соотношение, по которому из одного числа можно получить другое. Зная x и подставляя его в известное нам соотношение y=A*x, мы всегда получим значение y. Но ведь, как правило, верно и обратное: зная y, мы можем получить и x.
Как правило, но далеко не всегда. Для многих зависимостей получить y легко, тогда как x – уже очень трудно, и его получение займет продолжительное время. Вот именно на таких зависимостях и базируется используемое сейчас шифрование.
Но, вернемся к самому шифрованию. Шифрование подразделяют на симметричное, асимметричное и комбинированное. Рассмотрим, в чем суть каждого из них.
Симметричное шифрование, по большому счету, достаточно слабо отличается от старого доброго секретного алфавита. Собственно говоря, отличается оно как раз наличием ключа – некоторой сравнительно маленькой последовательности чисел, которая используется для шифрования и расшифровывания. При этом, каждая из обменивающихся информацией сторон должна этот ключ знать и хранить в секрете. Огромным плюсом такого подхода является скорость шифрования: ключ, по сути, является достаточно простой и короткой инструкцией, какой символ, когда, и на какой надо заменять. И работает данный ключ в обе стороны (то есть с его помощью можно как заменить все символы на новые, так и вернуть все как было), за что такой способ шифрования и получил название симметричного. Столь же огромным минусом является именно то, что обе стороны, между которыми информация пересылается, должны ключ знать. При этом, стоит нехорошему человеку заполучить ключ, как он тут же прочитает наши столь бережно защищаемые данные, а значит проблема передачи ключа принимающей стороне становится в полный рост.
Асимметричное шифрование поступает несколько хитрее. Здесь и у нас, и у нашего получателя есть уже два ключа, которые называют открытый и закрытый. Закрытый ключ мы и получатель храним у себя (заметьте, каждый хранит только свой ключ, а значит, мы уже выходим за пределы той самой поговорки про двоих знающих), а открытый мы и получатель можем спокойно передавать кому угодно – наш закрытый, секретный, по нему восстановить нельзя. Итого, мы используем открытый ключ получателя для шифрования, а получатель, в свою очередь, использует свой закрытый ключ для расшифровывания. Плюс данного подхода очевиден: мы легко можем начать обмениваться секретной информацией с разными получателями, практически ничем (принимая условие, что наш получатель свой закрытый ключ не потерял/отдал и т.п., то есть не передал его в руки нехорошего человека) не рискуем при передаче информации. Но, без огромного минуса не обойтись. И здесь он в следующем: шифрование и расшифровывание в данном случае идут очень, очень, очень медленно, на два-три порядка медленнее, чем аналогичные операции при симметричном шифровании. Кроме того, ресурсов на это шифрование тратится также значительно больше. Да и сами ключи для данных операций существенно длиннее аналогичных для операций симметричного шифрования, так как требуется максимально обезопасить закрытый ключ от подбора по открытому. А значит, большие объемы информации данным способом шифровать просто невыгодно.
Пример использования асимметричного шифрования [Wikipedia]
e — открытый ключ получателя B
d — закрытый ключ получателя B
m — исходная информация отправителя A
c — зашифрованная исходная информация
И снова возникает вопрос: что же делать? А делать нужно следующее: взять, и скомбинировать оба способа. Собственно, так мы и получаем комбинированное шифрование. Наш большой объем данных мы зашифруем по первому способу, а чтобы донести ключ, с помощью которого мы их зашифровали, до получателя, мы сам ключ зашифруем по второму способу. Тогда и получим, что хоть асимметричное шифрование и медленное, но объем зашифрованных данных (то есть ключа, на котором зашифрованы большие данные) будет маленьким, а значит расшифровывание пройдет достаточно быстро, и дальше уже в дело вступит более быстрое симметричное шифрование.
Пример применения комбинированной системы [Wikipedia]
Все эти механизмы нашли свое применение на практике, и оба наших больших лагеря PGP и S/MIME их используют. Как говорилось в первой статье, асимметричное шифрование используется для цифровой подписи (а именно, для шифрования нашего хэша). Отличие данного применения от обычного асимметричного шифрования в том, что для шифрования используется наш закрытый ключ, а для расшифровывания достаточно наличие связанного с ним (то есть, тоже нашего) открытого ключа. Поскольку открытый ключ мы не прячем, наш хэш можем прочитать кто угодно, а не только отдельный получатель, что и требуется для цифровой подписи.
Комбинированное же шифрование применяется в обоих стандартах непосредственно для шифрования отправляемых данных.
Таким образом, начиная пользоваться цифровыми подписями для защиты наших данных от подмены, мы автоматически (для этих двух стандартов) получаем и замечательную возможность защитить наши данные еще и от прочтения, что, согласитесь, весьма удобно.
Теперь, когда мы познакомились с общими принципами работы механизмов, используемых для защиты наших данных, можно наконец перейти к практике и рассмотрению, что же использовать. Но об этом в следующих статьях.
Одно из полезных применений асимметричного шифрования — работа с электронной подписью. Рассказываем, как устроена ЭП изнутри и где она применяется.
Дискретное логарифмирование
Это вторая сложная проблема, на которой основаны цифровые подписи. Для начала хорошо бы усвоить, что такое дискретный логарифм. Для кого-то такое словосочетание может звучать пугающе, но на самом деле это одна из самых простых для понимания вещей в этой статье.
Предположим, дано уравнение 4x = 13 (mod 15) . Задача нахождения x и есть задача дискретного логарифмирования. Почему же она так сложна для вычисления? Попробуй решить это уравнение перебором! Компьютер, ясное дело, будет более успешен, но и задачи дискретного логарифмирования обычно далеко не так просты. Возьмем для примера схему Эль-Гамаля.
Теорминимум
(На картинке изображён Лев Ландау, автор «теорминимума», серии экзаменов по теоретической физике)
Сформируем небольшой словарик терминов, которые нам пригодятся далее:
Открытый текст – данные, подлежащие шифрованию или полученные в результате расшифрования
Шифртекст – данные, полученные в результате применения шифра к открытому тексту
Шифр – совокупность обратимых преобразований, зависящая от некоторого параметра (ключа)
Ключ – параметр шифра, определяющий выбор одного преобразования из совокупности.
Факторизация – процесс разложения числа на простые множители.
НОД – наибольший общий делитель.
Числа a и b называются взаимно простыми, если НОД этих чисел равен 1.
Функция Эйлера φ(n) – функция, равная количеству натуральных чисел, меньших n и взаимно простых с ним.
Хочу отметить, что на данном этапе подразумевается, что вы знакомы с арифметическими операциями по модулю. Если нет, то здесь можно о них почитать.
А что если подменят сам сертификат?
Все сертификаты, которые выдаёт удостоверяющий центр, тоже подписываются электронной подписью. Чтобы проверить подлинность сертификата, можно зайти на официальный сайт удостоверяющего центра и скачать открытый ключ для проверки. Если хеш самого сертификата совпадает с хешем, который мы получили с помощью открытого ключа с сайта — значит, и сам сертификат подлинный.
Выясняем, как и откуда можно получить электронную подпись на примере криптосистемы RSA.
Содержание
Определения и обозначения
Описание криптосистемы RSA
Асимметричные криптографические системы
Шифрование и дешифрование
Электронная подпись документов
Выводы
Будущее неразрывно связано с криптографией. В один прекрасный момент при получении паспорта наши дети будут генерировать электронную подпись и покупать чипсы в ларьке за криптовалюту. Что готовит нам будущее с точки зрения развития криптографии, посмотрим в следующей статье на примере квантовых компьютеров.
Итак, все чаще в кругах, работающих с документами все чаще звучат слова «электронный документ» и, связанное с ним почти неразрывно «электронная цифровая подпись», иначе — ЭЦП.
Данный цикл статей предназначен для того, чтобы раскрыть «тайное знание» о том, что это такое, когда и как это можно и нужно использовать, какие есть плюсы и минусы.
Естественно, статьи пишутся не для специалистов по криптографии, а для тех, кто эту самую криптографию будет использовать, или же только начинает ее изучение, желая стать специалистом, поэтому я старался максимально упростить понимание всего процесса, приводя аналогии и рассматривая примеры.
Зачем нам вообще что-то подписывать? Естественно, чтобы удостоверить, что мы ознакомились с содержимым, согласны (а иногда наоборот, не согласны) с ним. А электронная подпись еще и защищает наше содержимое от подмены.
Итак, начать, естественно, стоит с того, что такое электронная цифровая подпись.
В самом примитивном случае это — результат хэш-функции. Что это такое лучше меня разъяснит википедиа, в нашем же случае главное, что с высокой степенью вероятности ее результат не повторяется для разных исходных данных, а также что результат этой функции мало того, что короче исходных данных, так еще по нему исходную информацию восстановить нельзя. Результат функции называют хэшем, а применение этой функции к данным называют хешированием. Грубо, можно назвать хэш функцию архивированием, в результате чего мы получаем очень маленькую последовательность байт, но восстановить исходные данные из такого «архива» нельзя.
Итак, мы читаем файлик в память, хэшируем прочитанное. И что, уже получаем ЭЦП? Почти. Наш результат с большой натяжкой можно назвать подписью, но, все же, полноценной подписью он не является, потому что:
1. Мы не знаем, кто сделал данную подпись
2. Мы не знаем, когда была сделана подпись
3. Сама подпись не защищена от подмены никак.
4. Ну и да, хэш функций много, какая из них использовалась для создания этого конкретного хэша?
Поэтому применять к хэшу слово «подпись» еще нехорошо, будем называть его дальше просто хэш.
Вы посылаете ваш файл другому человеку, допустим, по почте, будучи уверенными, что он точно получит и прочитает именно то, что вы послали. Он же, в свою очередь, тоже должен хэшировать ваши данные и сравнить свой результат с вашим. Если они совпали — все хорошо. Это значит что данные защищены? Нет.
Ведь хэшировать может кто угодно и когда угодно, и вы никогда не докажете, что он хэшировал не то, что вы послали. То есть, если данные будут перехвачены по дороге злоумышленником, или же тот, кому вы посылаете данные — не очень хороший человек, то данные могут быть спокойно подменены и прохэшированы. А ваш получатель (ну или вы, если получатель — тот самый нехороший человек) никогда не узнает, что он получил не то, что вы отправляли, или сам подменил информацию от вас для дальнейшего использования в своих нехороших целях.
Посему, место для использование чистой хэш функции — транспорт данных в пределах программы или программ, если они умеют общаться между собой. Собственно, с помощью хэш функций вычисляются контрольные суммы. И эти механизмы защищают от случайной подмены данных, но не защищают от специальной.
Но, пойдем дальше. Нам хочется защитить наш результат хеширования от подмены, чтобы каждый встречный не мог утверждать, что это у него правильный результат. Для этого самое очевидное что (помимо мер административного характера)? Правильно, зашифровать. А ведь с помощью шифрования же можно и удостоверить личность того, кто хэшировал данные! И сделать это сравнительно просто, ведь есть ассиметричное шифрование. Да, оно медленное и тяжелое, но ведь нам всего-то и надо — зашифровать маленькую последовательность байт. Плюсы такого действия очевидны — для того, чтобы проверить нашу подпись, надо будет иметь наш открытый ключ, по которому личность зашифровавшего (а значит, и создавшего хэш) можно легко установить.
Суть этого шифрования в следующем: у вас есть закрытый ключ, который вы храните у себя. И есть открытый ключ. Открытый ключ вы можете всем показывать и раздавать, а закрытый — нет. Шифрование происходит с помощью закрытого ключа, а расшифровывание — с помощью открытого.
Приводя аналогию, у вас есть отличный замок и два ключа к нему. Один ключ замок открывает (открытый), второй — закрывает (закрытый). Вы берете коробочку, кладете в нее какую-то вещь и закрываете ее своим замком. Так, как вы хотите, чтобы закрытую вашим замком коробочку открыл ее получатель, то вы открытый, открывающий замок, ключик спокойно отдаете ему. Но вы не хотите, чтобы вашим замком кто-то закрывал коробочку заново, ведь это ваш личный замок, и все знают, что он именно ваш. Поэтому закрывающий ключик вы всегда держите при себе, чтобы кто-нибудь не положил в вашу коробочку мерзкую гадость и не говорил потом, что это вы ее положили и закрыли своим замком.
И все бы хорошо, но тут сразу же возникает проблема, а, на самом деле, даже не одна.
1. Надо как-то передать наш открытый ключ, при этом его должна понять принимающая сторона.
2. Надо как-то связать этот открытый ключ с нами, чтобы нельзя было его присвоить.
3. Мало того, что ключ надо связать с нами, надо еще и понять, какой зашифрованный хэш каким ключом расшифровывать. А если хэш не один, а их, скажем, сто? Хранить отдельный реестр — очень тяжелая задача.
Все это приводит нас к тому, что и закрытый ключ, и наш хэш надо хранить в каких-то форматах, которые нужно стандартизировать, распространить как можно шире и уже тогда использовать, чтобы у отправителя и получателя не возникало «трудностей перевода».
Как водится у людей, к чему-то единому прийти так и не смогли, и образовалось два больших лагеря — формат OpenPGP и формат S/MIME + X.509. Но об этом уже в следующей статье.
Теперь к математике
Асимметричные криптографические системы основаны на так называемых односторонних функциях с секретом. Под односторонней понимается такая функция я 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, а мы переходим к Алисе.
Источники
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. - Учебное пособие
Электронная цифровая подпись сейчас на слуху — многие современные компании потихоньку переходят на электронный документооборот. Да и в повседневной жизни ты наверняка сталкивался с этой штукой. Если в двух словах, суть ЭЦП очень проста: есть удостоверяющий центр, есть генератор ключей, еще немного магии, и вуаля — все документы подписаны. Осталось разобраться, что же за магия позволяет цифровой подписи работать.
ЭЦП на практике
В России, как и во многих развитых странах, электронная подпись имеет официальный юридический статус. У нас этот факт регламентирует закон № 63-ФЗ «Об электронной подписи». Однако он утверждает, что юридической силой обладает далеко не любая электронная подпись, а только соответствующая определенным критериям:
- подпись сгенерирована посредством криптографического преобразования с секретным ключом;
- этот ключ и соответствующий ему открытый ключ выданы квалифицированным удостоверяющим центром;
- по подписи можно достоверно установить ее обладателя.
Подпись также должна быть вычислена средствами, соответствующими требованиям закона. Этим требованиям удовлетворяет отечественный алгоритм шифрования ГОСТ 34.10—2012. Он использует математический аппарат эллиптических кривых, является достаточно стойким и официально используется для разработки криптографических средств, реализующих электронную подпись. Для того чтобы попробовать неквалифицированную подпись — без сертификата удостоверяющего центра, можно воспользоваться известной PGP. Потестировать подпись можно, к примеру, на сайте ReadVerify.
Стоит сказать, что в нашей стране электронная подпись используется чаще, чем можно себе представить. В банках, налоговых, торгово-закупочных операциях, бухгалтерии — во всех этих организациях используется или внедряется ЭЦП. Электронная подпись отважно борется со злом бюрократии, однако до полной победы еще далеко.
За рубежом электронный документооборот процветает еще дольше. Официальный стандарт электронной подписи в США DSS (Digital Signature Standard) также использует эллиптические кривые и основан на описанной выше схеме Эль-Гамаля.
Как оно устроено
Прежде, чем окунуться в необъятный мир математики рассмотреть, как именно устроена RSA, обратимся к тому, как работают
Roadmap
Это пятый урок из цикла «Погружение в крипту». Все уроки цикла в хронологическом порядке:
-
Основы и исторические шифраторы. Как работают (и анализируются) шифры сдвига, замены, Рихарда Зорге, шифр Вернама и шифровальные машины Что это такое, как выполняется распределение ключей и как выбрать криптостойкий ключ Что такое сеть Фейстеля и какими бывают отечественные блочные шифры, используемые в современных протоколах, — ГОСТ 28147—89, «Кузнечик» В чем разница между 3DES, AES, Blowfish, IDEA, Threefish от Брюса Шнайера и как они работают
- Урок 5. Электронная подпись. Виды электронных подписей, как они работают и как их использовать (ты здесь)
- Урок 6. Квантовая криптография. Что это такое, где используется и как помогает в распределении секретных ключей, генерации случайных чисел и электронной подписи
Факторизация больших чисел
Рассмотрим на практике электронную подпись на основе знаменитого алгоритма RSA. Шифрование RSA мы рассматривать не стали — это мейнстрим, и в той же «Википедии» есть его подробное описание.
3. Проверка электронной подписи
RSA, как известно, собирается уходить на пенсию, потому что вычислительные мощности растут не по дням, а по часам. Недалек тот день, когда 1024-битный ключ RSA можно будет подобрать за считаные минуты. Впрочем, о квантовых компьютерах мы поговорим в следующий раз.
В общем, не стоит полагаться на стойкость этой схемы подписи RSA, особенно с такими «криптостойкими» ключами, как в нашем примере.
2. Вычисление электронной подписи
Введение
Наверняка вы сталкивались с таким понятием, как "электронная подпись". Если обратиться к федеральному закону, то можно найти следующее её определение:
«Электронная подпись - информация в электронной форме, которая присоединена к другой информации в электронной форме (подписываемой информации) или иным образом связана с такой информацией и которая используется для определения лица, подписывающего информацию»
Задача ЭП ясна, теперь хотелось бы увидеть и прочувствовать, что именно скрывается за этими двумя словами. Копаясь дальше в гугле, можно найти довольно много различных алгоритмов создания цифровой подписи (DSA, ГОСТ Р 34.10-2012, RSA-PSS и т.д.), разбираться в которых неподготовленному пользователю сложно.
Спасти эту ситуацию и помочь разобраться в том, что есть ЭП, может криптосистема RSA, разработанная Ривестом, Шамиром и Адлеманом в 1978 году. Она не загромождена безумным количеством алгоритмов и основывается на относительно простой математике. В связи с этим можно шаг за шагом прийти от модульной арифметики к алгоритму создания электронной подписи, чему я и хочу посвятить данную статью.
2. Проверка подписи
Даже если не вникать в схему, понятно, что такой алгоритм сложнее. Кроме того, нигде уже не используется простой модуль, его сменили эллиптические кривые. Эллиптическая кривая — это кривая, которая задана кубическим уравнением и имеет невообразимо сложное представление. Задача решения логарифма в группе точек, которые принадлежат эллиптической кривой, вычислительно сложная, и на данный момент не существует таких мощностей, которые решали бы это уравнение за полиномиальное время, если длина секретного ключа составляет 512 бит. Согласно задаче дискретного логарифмирования, невероятно сложно найти на кривой две такие точки, которые связывает операция возведения в некоторую степень.
Что такое электронная подпись
Электронная подпись — это технология, которая помогает подтвердить подлинность электронного документа: договора, справки, выписки или чего-то ещё.
Если упрощённо, работает так:
👉 Есть некий документ, подписанный ЭП
👉 С помощью специальной программы можно проверить подлинность этой подписи и документа
✅ Если программа говорит, что всё окей, то мы можем быть уверены: документ подписал именно тот, кто в нём указан; и с момента подписания в документе ничего не изменилось.
❌ Или программа может сказать, что подпись не совпала. Это значит, что либо документ подписал другой человек, либо после подписания кто-то изменил этот документ (например, дописал ноль в стоимость контракта). Так мы поймём, что этому документу нельзя доверять.
С технической точки зрения ЭП — небольшой файлик, который прилагается к искомому документу. Файлик пересылается вместе с основным документом, его можно передавать по открытым каналам связи, в нём нет ничего секретного.
Электронная подпись нужна, чтобы защищать договоры, выдавать официальные справки, заключать сделки и участвовать в торгах по госзакупкам.
Как работает цифровая подпись
Если ты читал вторую часть нашего цикла, то помнишь, что существуют симметричный и асимметричный подходы к шифрованию. С электронной подписью дела обстоят очень похоже — есть подписи с симметричным механизмом, а есть с асимметричным.
Симметричный механизм подписи малоприменим на практике — никому не хочется генерировать ключи для каждой подписи заново. А как ты помнишь, именно в одинаковых ключах кроется фишка симметричной криптографии.
Схемы электронной подписи так же многообразны, как и способы шифрования. Чтобы схема подписи была стойкой, нужно, чтобы она основывалась на трудновычислимой математической задаче. Есть два типа таких задач: факторизация больших чисел и дискретное логарифмирование.
Основа ЭП — асимметричное шифрование
1. Генерация подписи
Асимметричные криптосистемы
Рассмотрим задачу сохранности содержимого посылки при передаче от отправителя к адресату. Вот картинка с многим полюбившимся Алисой и Бобом:
Цифровая подпись в Bitcoin
Помимо прочего, электронная подпись используется в криптовалютах, в частности — в Bitcoin. У каждого пользователя Bitcoin есть пара из секретного и открытого ключа. Хеш-значение открытого ключа служит основным адресом для передачи монет. Это значение не секретно, и сообщать его можно кому угодно. Но по значению хеша вычислить значение открытого ключа невозможно.
Сама пара ключей будет использована лишь однажды — при передаче прав собственности. На этом жизнь пары ключей заканчивается.
- PUB1 — публичный ключ;
- PRIV1 — секретный ключ;
- HASH1 или HASH(PUB1) — хеш-значение открытого ключа (биткойн-адрес);
- HASH2 или HASH(PUB2) — хеш открытого ключа следующего владельца.
Вот как устроен сам процесс передачи прав собственности на биткойны.
- Владелец монеты открыто сообщает хеш своего публичного ключа HASH(PUB1), это и будет идентифицировать биткойн.
- До момента продажи оба ключа PUB1, PRIV1 продавца остаются в секрете. Известен только HASH(PUB1) и соответствующий ему биткойн.
- Как только появляется покупатель, владелец формирует открытое письмо, в котором указывает адрес биткойна HASH(PUB1) и хеш-значение публичного ключа нового владельца HASH(PUB2). И конечно же, подписывает письмо своим секретным ключом PRIV1, прилагая публичный ключ PUB1.
- После этого пара ключей владельца PUB1 и PRIV1 теряют свою актуальность. Публичным ключом можно проверить само письмо, узнать новый адрес монеты.
О втором собственнике ничего не известно, кроме HASH(PUB2), до тех пор пока он не передаст права третьему владельцу. И эта цепочка может быть бесконечной.
Подписывая передачу прав с использованием ЭЦП, собственник подтверждает не только свою личность, но и свое согласие на проведение сделки. То есть вернуть монетку он уже не может и с этим согласился, подписавшись электронной подписью.
Благодаря HASH(PUB) получается двойная защита. Первая загадка — узнать публичный ключ по его хешу. Вторая загадка — подписаться чужим секретным ключом.
Такая технология построения цепи передачи прав и называется блокчейном. Благодаря этой технологии можно отследить историю владения до самых истоков, но изменить эту историю никак нельзя.
1. Генерация ключей
Причина стойкости RSA кроется в сложности факторизации больших чисел. Другими словами, перебором очень трудно подобрать такие простые числа, которые в произведении дают модуль n. Ключи генерируются одинаково для подписи и для шифрования.
Когда ключи сгенерированы, можно приступить к вычислению электронной подписи.
Как работает: сертификаты
Электронная подпись состоит из двух принципиальных частей:
- Сертификат для удостоверения подписывающего.
- Криптографическая часть для проверки подлинности документа.
Грубо говоря, ЭП должна гарантировать, что документ подписали именно вы и что вы подписали именно этот документ.
В сертификате хранятся данные о владельце подписи:
- кто владелец этой подписи;
- открытый ключ для проверки подписи;
- когда заканчивается срок действия подписи;
- какого уровня документы можно подписывать этой подписью;
- кто выдал сертификат;
- и другие служебные данные.
Но смысл сертификата не в том, что там хранятся эти данные, а в том, кто эти данные туда положил. В России сертификаты и ЭП выдают специальные удостоверяющие центры — это компании, которые гарантируют, что сертификат выдаётся именно тому, кто в этом сертификате указан.
Чтобы получить сертификат, вы приходите лично в эту компанию (удостоверяющий центр), показываете документы, фотографируетесь. Вас заносят в базу удостоверяющего центра и выдают ключи электронной подписи. Так все участники электронного документооборота будут уверены, что все документы, подписанные вашими ключами, подписаны именно вами.
Заключение
Вот мы и прошли все стадии создания электронной подписи, начиная с простой модульной арифметики и заканчивая, собственно, получением подписи. Обладая этими знаниями, вы можете попробовать перевести их на ваш любимый язык программирования и написать свою защищенную аську, например. В том, как именно их применить, вас ограничит только ваше воображение.
Отмечу, что другие существующие алгоритмы создания ЭП основаны на схожих принципах, поэтому надеюсь, что после прочтения этой статьи вам будет проще разобраться в них. "Следующей по сложности" я обозначу криптосистему Эль-Гамаля, но о ней уже не в этом посте.
Спасибо за внимание!
Подпись документов
Рассмотренный алгоритм получения подписи изящен и прост в осознании, однако операция возведения в степень несколько "мешается". Наша текущая задача – подписать объёмный документ. Чтобы сэкономить время, мы не будем подписывать содержимое документа, а прибегнем к помощи хэш-функций (если вы не знаете, что такое хэш-функция, рекомендую почитать википедию). Скажу лишь то, что выходная последовательность хэш-функции имеет небольшую (по сравнению с размером ключей) длину, а также по имеющемуся хэшу нельзя однозначно восстановить исходные данные.
На картинках наглядно показано, в какой момент мы используем хэширование. Создание подписи:
В качестве хэш-функции можно использовать SHA-256, как это сделано, например, в PGP. По теме практического создания электронной подписи с использованием PGP на хабре уже написана статья, поэтому на этом месте имеет смысл поставить точку и перейти к заключению.
Как работает: алгоритмы шифрования
Допустим, вы уже сходили в удостоверяющий центр и получили на флешке сертификат и ключ электронной подписи. Теперь нужно скачать специальный софт, который и будет подписывать ваши документы и проверять чужие на подлинность.
Проблема в том, что ЭП основана на алгоритмах асимметричного шифрования, а их много: разложение на простые множители, дискретное логарифмирование, эллиптические кривые и множество других. Ключ из одного алгоритма не подойдёт для использования в другом, поэтому в России договорились использовать стандарт шифрования ГОСТ Р 34.10-2012, основанный на эллиптических кривых. Все государственные органы работают только с таким алгоритмом и не принимают другие ЭП.
Это значит, что нам нужен специальный софт, в котором уже есть этот алгоритм. Чаще всего используют КриптоПРО, реже — ViPNet CSP. С помощью этих программ можно подписать документы и проверить сертификаты на подлинность.
Принцип работы электронной подписи
Электронная подпись — это асимметричное шифрование наоборот: вы зашифровываете закрытым ключом, а расшифровать может кто угодно с помощью открытого ключа, который доступен всем.
Разберём по шагам:
- В удостоверяющем центре вы получаете сертификат и ключ электронной подписи. Это закрытый ключ, который передавать никому нельзя. Открытый же ключ хранится в самом сертификате, который прикладывается к каждому документу и доступен всем.
- Берёте нужный документ и получаете его криптографический хеш. Хеш — это небольшая строка, которая представляет собой «цифровой отпечаток» файла. У каждого файла с уникальным набором битов будет уникальный хеш, причём он всегда одинаковой длины. Подробнее о хешах мы писали, когда разбирали скандал с паролями Фейсбука.
- Шифруете этот хеш своим закрытым ключом. Полученный результат шифрования добавляете к исходному документу.
- Туда же добавляете сертификат, чтобы все могли проверить и убедиться, что документ подписали вы.
Шифруем, дешифруем.
Здесь за с обозначен шифртекст, который Алиса будет должна передать Бобу. Отметим также, что c ∈ [1, n − 1], как и m. Расшифруем шифртекст, возведя его в степень закрытого ключа Боба d:
А теперь ответим на вопрос, почему m ≡ m′ . Ниже я приведу доказательство данного утверждения, но если оно (доказательство) вам не сильно интересно, то можете его пропустить и просто поверить, что это так.
Здесь нам понадобится теорема Эйлера:
Также полезной будет китайская теорема об остатках:
Ещё раз напишем две ключевые формулы шифрования и расшифрования соответственно:
Если Алиса получила, что m ≡ m′, то подпись считается правильной.
Дочитавших до этого места хочу поздравить с получением первой цифровой подписи "на бумаге"!
Читайте также: