Алгоритм электронной цифровой подписи

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

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

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

§ Злоумышленник, укравший закрытый ключ, может подписать любой документ от имени владельца ключа.

§ Злоумышленник может обманом заставить владельца подписать какой-либо документ, например, используя протокол слепой подписи.

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

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

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

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

В настоящее время существуют следующие устройства хранения закрытого ключа:

§ Дискеты

§ Смарт-карты

§ USB-брелоки

§ Таблетки Touch-Memory

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

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

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

1. достоверностью, утверждающей, что пользователь сознательно подписал документ;

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

3. невозможностью повторного использования подписи под одним документом для подписи другого;

4. неизменностью подписанного документа;

5. материальностью подписи, не дающей возможности подписавшему впоследствии отказаться от нее и от документа.

Такими же свойствами должна обладать электронная цифровая подпись, для чего в ее основу положены криптографические методы. Рассмотрим вариант реализации электронной цифровой подписи, построенной на алгоритме RSA (рис. 2.1).

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

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

Рисунок 2.1 – Схема ЭЦП на основе алгоритма RSA

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

Очень популярными являются схемы ЭЦП на основе алгоритма ЭльГемаля, что обусловлено как надлежащей стойкостью алгоритма, так и лучшей по сравнению с RSA скоростью вычислений. В частности, в стандарте национального института стандартов США DSS (Digital Signature Standard) используется алгоритм DSA (Digital Signature Algorithm), который является вариацией алгоритма ЭЦП ЭльГемаля в модификации Шнорра. В алгоритме используются следующие открытые параметры:

· p - простое число в диапазоне от 512 до 1024 бит;

· q -160-битовое простое число, делитель p -1;

· v – любое число, v < p -1, такое, что v ^{(p -1)/ q} mod p > 1;

· g = v ^{(p -1)/ q} mod p;

· y = g^x mod p.

Секретным ключом является любое 160-разрядное число x, x < q.

Алгоритм ЭЦП DSA в графической форме представлен на рис.2.2.

Рисунок 2.2 – Схема алгоритма ЭЦП DSA

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

Для практического применения в криптографии используются эллиптические кривые (ЭК), заданные над полями Галуа. Пусть задано простое число p > 3. Тогда эллиптической кривой E, определенной над простым конечным полем F_p, называется множество пар чисел (x, y), x, y ∈ F_p, которые удовлетворяют тождеству: y² = x³ + ax + b mod p, где a, b ∈ F_p и (4a³ + 27b²) ≠ 0 mod p. Кроме того, к эллиптической кривой добавляется бесконечно удаленная точка I. Таким образом, точки, удовлетворяющие уравнению кривой E, и точка I образуют конечную абелеву группу.

Геометрическое представление эллиптической кривой изображено на рис. 2.3.

Для точек эллиптической кривой определена операция сложения. Для двух точек, принадлежащих кривой E, P (x_p, y_p) и Q (x_p, y_p), точка, являющаяся их суммой, также будет лежать на эллиптической кривой. Координаты точки S = P+Q определяются следующими выражениями:

· k = ((y_q-y_p)/(x_q-x_p)) mod p

· x_s = (k²-x_q-x_p) mod p

· y_s = (k(x_q-x_p)-y_p) mod p

Рисунок 2.3 – График эллиптической кривой

Точку S можно получить графически путем несложных построений. Для этого на графике проводится прямая через точки P и Q, и точка пересечения этой прямой с ЭК зеркально отображается относительно оси OX (см. рис 2.3).

Если точки P и Q совпадают, то мы получаем точку S = 2* Q. Тогда ее координаты определяются иначе:

· k = ((3*x_q²+a)/(2*y_q)) mod p

· x_s = (k²-2x_q) mod p

· y_s = (k(x_q-x_s)-y_p) mod p

Графически удвоение точки можно получить, построив касательную к точке и отразив точку пересечения касательной с эллиптической кривой относительно оси OX (см. точки R и 2 R на рис.2.3). Отсюда очевидно, что можно определить операцию умножения некоторой точки эллиптической кривой на целое число, которая позволяет определить точку Q = k*P (точка P, умноженная на целое число k, обращается в точку Q). Скалярное умножение осуществляется посредством нескольких комбинаций сложения и удвоения точек эллиптической кривой. Например, точка 25* P может быть представлена, как 25* P = 2*(2*(2*(2* P)) + 2*(2*(2* P))) + P. С операцией умножения точки ЭК на целое число напрямую связана идея, надёжность и криптостойкость эллиптической криптографии. Дело в том, что задача ECDLP (Elliptic Curve Discrete Logarithm Problem - задача дискретного логарифма на эллиптической кривой), суть которой заключается в отыскании целого числа k по известным точкам P и Q = k*P, является трудноразрешимой. Помимо уравнения, важным параметром кривой является базисная (генерирующая) точка G, выбираемая для каждой кривой отдельно. Секретным ключом в соответствии с технологией ЭК является большое случайное число k, а сообщаемым открытым ключом - произведение k на базисную точку G.

На криптостойкость алгоритма существенное влияние оказывает правильный выбор как самой кривой (коэффициентов а, b, p), так и базисной точки G.

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

Выбор базисной точки обусловлен тем соображением, чтобы ее порядок был достаточно большим 2254 < q < 2256. Точка P ∈ E называется точкой порядка q, если qP = I.

На эллиптических кривых построен алгоритм проверки ЭЦП ГОСТ Р 34.10 – 2001, являющийся на сегодня стандартом РФ в области ЭЦП. Схема этого алгоритма приведена на рис. 2.4.

Рисунок 2.4 – Схема алгоритма ЭЦП ГОСТ 34.10-2001

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

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