обзор схем электронной цифровой подписи
Массовое использование компьютерных сетей и электронных коммуникаций значительно расширяют возможности для обмена информацией между пользователями. Все больше организаций пользуются электронной почтой для ускорения прохождения информации внутри компании и для внешних контактов, больше людей пользуются услугами интернет-магазинов. Словом, электронные документы (ЭД) если не вытесняют бумажные, то, по крайней мере, являются им достойной альтернативой. Но, как и у любой медали, у повальной информатизации есть обратная сторона. Дело в том, что у электронного документа есть качественное отличие от бумажного - копирование, изменение и удаление не представляют никакой сложности. Поэтому основные проблемы, встающие перед пользователями информационных систем заключаются в нарушении:
- конфиденциальности - ознакомлении с документом лиц, не имеющим на это права;
- целостности - модификация (изменение) документа лицом, не имеющим на это права;
- авторства - возможность создать электронный документ от имени другого лица или подделки его атрибутов, например, времени создания.
Еще совсем недавно основной аспект защиты документооборота заключался в сохранении конфиденциальности (секретности) предаваемых сообщений. И как отправитель, так и получатель секретных сообщений были заинтересованы в сохранении тайны и целостности переданного сообщения. В этих условиях достижение конфиденциальности, целостности и проверка авторства решались с применением средств традиционной (симметричной) криптографии. Считается, что использование надежных шифров и сохранение в тайне ключевой информации обеспечивает надежную защиту информации от прочтения противником. Действительно, не зная секретного ключа очень трудно прочитать перехваченное сообщение, если используется стойкий шифр. А для защиты от случайных или преднамеренных искажений применялись так называемые имитовставки. Имитовставка зависит от секретного ключа и всего массива данных весьма сложным образом, поэтому подделать ее, не зная ключа, невозможно. Так как секретный ключ известен только двум (или некоторой группе) корреспондентов, то получение сообщения, защищенного имитовставкой, выработанной на данном ключе, подтверждает принадлежность автора сообщения к этой группе.
электронная цифровая подпись
Механизм электронной цифровой подписи (ЭЦП) возник как побочный эффект криптографии с открытым ключом. Поэтому характерное для систем с открытым ключом разделение ключа на 2 части - секретную и несекретную - позволяет реализовать возможность проверки подлинности без возможности подписать другой документ.
Итак, цифровая подпись - это конечная цифровая последовательность, зависящая от самого сообщения или документа и от секретного ключа, известного только подписывающему субъекту, предназначенная для установления авторства. Так как цифровая подпись строится на базе криптосистемы с открытым ключом, то необходимо иметь пару ключей - секретный и открытый. Секретный ключ используется для формирования цифровой подписи, поэтому его нужно хранить в тайне. А открытый ключ используется для проверки соответствия подписи документу, поэтому он должен быть опубликован, например, в общедоступном каталоге.
Предположим, что абонент A уже сформировал свою пару секретного и открытого ключей и на их основе построил функции DKA(x) и EKA(x). Причем для любого x должно выполнятся равенство EKA(DKA(x)) = x. Функцию DKA(x) будем называть функцией подписи сообщения x, а функцию EKA(x) - функцией проверки подписи для сообщения x. В дальнейшем будем отождествлять функции DKA(x) и EKA(x) с секретным и открытым ключами пользователя A соответственно. Надо заметить, что функции DKA(x) и EKA(x) связаны (так как связаны секретный и открытый ключи), однако по опубликованной функции EKA(x) вычислительно невозможно восстановить функцию DKA(x).
Рассмотрим схему взаимодействия отправителя (A) и получателя (B), которая позволяет B проверить подлинность передаваемого сообщения.
1. A создает сообщение x, которое он собирается подписать и вычисляет подпись DKA(x).
2. A передает B пару (x,DKA(x)).
3. B проверяет равенство EKA(DKA(x)) = x. В случае совпадения обоих величин B принимает решение о подлинности сообщения x, в противном случае B принимает решение считать сообщение x искаженным.
Рассмотренный протокол взаимодействия имеет следующий недостаток: так как функция EKA(x) - опубликована, то злоумышленник C может для любого z вычислить EKA(z) и предать в канал связи пару (EKA(z),z). Несложно видеть, что в этом случае z, будет подписью для EKA(z). Для предотвращения такой возможности пользователи должны подписывать не сами сообщения, а их хэши, то есть значения хэш-функции от сообщения.
Напомним определение хэш-функции. Функция h:X -> M называется хэш-функцией, если выполнены следующие условия:
1. Постоянство размера - для входного массива данных любого размера результатом должен быть блок данных фиксированного размера.
2. Функция h(x) легко вычислима.
3. Функцию h(x) трудно инвертировать, то есть почти для всех m из M трудно найти x из X такой, что h(x) = m.
4. Для данного x сложно найти x' неравный x такой, что h(x) = h(x').
5. Сложно найти пару (x, x') из X2 такую, что x неравен x' и h(x) = h(x').
Где M - множество векторов фиксированной длины, а X - вектора произвольной длины. Пара (x, x') из X2 такая, что x неравно x' и h(x) = h(x') называется коллизией хэш-функции h.
Помимо устранения рассмотренной выше возможности создания подписи без знания секретного ключа, использование хэш-функции решает еще одну проблему: дело в том, что функции EKA(x) и DKA(x) оперируют с блоками данных фиксированного размера, а размер сообщения может превышать этот размер. Без использования хэш-функции подписывать сообщение x пришлось бы следующим образом:
x = (x1,..,xk) \to ( (x1,DKA(x1)),.., (xk,DKA(xk))),
где x1,..,xk - векторы фиксированной длины, совпадающей с длиной входа функций EKA(x) и DKA(x). Подобная подпись обладает следующими недостатками:
- для больших документов слишком сильно загружается процессор, так как придется много раз вычислять функцию DKA(xi);
- злоумышленник может набрать достаточно большой набор пар (xi, DKA(xi)) и сам формировать сообщения из фрагментов.
Модифицированный протокол выглядит таким образом:
1. A создает сообщение x, которое он собирается подписать и вычисляет его хэш h(x), после чего подписывает DKA(h(x)).
2. A передает B пару (x,DKA(h(x))).
3. B проверяет равенство EKA(DKA(h(x))) = h(x). В случае совпадения обоих величин B принимает решение о подлинности сообщения x, в противном случае B принимает решение считать сообщение x искаженным.
В этом протоколе возможность подделки подписи может быть основана на нахождении коллизии хэш-функции, то есть по известному значению h(x) найти x' такой, что h(x) = h(x'). Для предотвращения этой возможности нельзя использовать непроверенные функции. Как правило, стойкие к коллизиям хэш- функции описаны в государственном стандарте. В Российской Федерации этот стандарт носит название ГОСТ Р 34.11-94, в США - описывается документами FIPS 180-1 и FIPS 180-2, а в Евросоюзе рекомендуется использование стандарта Whirlpool.
Российский стандарт хэширования был принят в 1994 году и с тех пор не изменялся, размер хэш-блока для него составляет 256 бит. В США изначально действовал стандарт SHS (Secure Hash Standard), где размер хэш-блока был равен 160 бит. Однако в 2002 году стандарт был пересмотрен: прежний остался действовать и получил обозначение SHA-1, но к нему были добавлены три новых алгоритма, вырабатывающие хэш-блоки размером 256, 384 и 512 бит, названные SHA-256/384/512 соответственно.
механизм сертификатов
Однако рассмотренные выше протоколы не учитывают один факт: а как пользователю B убедиться, что открытый ключ EKA принадлежит отправителю A? Рассмотрим подробнее проблему доверия пользователя B открытому ключу отправителя A. При использовании цифровой подписи A и B нужно защищать только свои личные секретные ключи. А открытые ключи им нужно использовать совместно. Хранить их в секрете нет необходимости, нужна лишь возможность идентифицировать открытый ключ другой стороны. Поэтому для применения цифровой подписи критическое значение имеет доверие к соответствию между известным субъектом и его открытым ключом. B может доверять открытому ключу A, если A передал ему ключ безопасным способом. Но безопасность передачи обеспечивается только защищенными средствами связи. Более вероятно, что B получил открытый ключ A с помощью незащищенного средства связи (например, из общего каталога), поэтому нужен механизм, который может обеспечить B уверенность в том, что имеющийся у него открытый ключ действительно принадлежит A, а не кому-либо другому.
Один их таких механизмов основан на сертификатах (certificate), выдаваемых центром сертификации (certification authority). Сертификаты обеспечивают механизм надежной связи между открытым ключом и субъектом, которому принадлежит соответствующий личный ключ. Сертификат - это цифровой документ, который содержит открытый ключ субъекта (subject public key) и подписан электронной цифровой подписью его издателя (issuer). Сертификат также содержит сведения о владельце открытого ключа, например, информацию, которая его дополнительно идентифицирует. Таким образом, выдавая сертификат, издатель удостоверяет подлинность связи между открытым ключом субъекта и информацией, его идентифицирующей. В настоящее время наиболее часто используются сертификаты на основе стандарта Международного союза телекоммуникаций ITU-T X.509 версии 3 и рекомендаций IETF (Internet Engineering Task Force) RFC 2459. Например, формат сертификата X.509 принят в протоколах S/MIME, IP Security, а также SSL/TLS и SET. Кроме того, это базовая технология, используемая в инфраструктуре открытых ключей операционной системы Windows 2000. Однако это не единственный вид сертификатов. Например, система защиты сообщений электронной почты PGP (Pretty Good Privacy) использует свою специфическую форму сертификатов.
Центр сертификации (ЦС) --- это служба, которая выдает сертификаты.
Центр сертификации является гарантом связи между открытым ключом субъекта и содержащейся в сертификате информацией по идентификации этого субъекта. Различные ЦС устанавливают и гарантируют эту связь различными способами, поэтому прежде чем доверять сертификатам того или иного ЦС, следует ознакомиться с его политикой и регламентом.
подтверждение доверия
Когда B получает подписанное сообщение, у него возникает важный вопрос: можно ли этой подписи доверять? Иными словами, действительно ли эта подпись принадлежит отправителю сообщения? B может проверить целостность подписи с помощью известного ему открытого ключа отправителя и криптографических алгоритмов. Однако при этом B должен быть уверен в том, что использованный им для проверки открытый ключ действительно принадлежит тому субъекту, именем которого подписано сообщение. Если у B нет прямого доказательства, что открытый ключ принадлежит A, то ему надо получить хотя бы достаточно веское подтверждение этого. Если B сможет найти сертификат открытого ключа A, выданный тем центром сертификации, которому он доверяет, то он получит убедительное подтверждение того, что открытый ключ A действительно принадлежит A. Итак, у B появится веское основание полагать, что открытый ключ принадлежит именно A, если он найдет сертификат, который:
- имеет действительную с криптографической точки зрения подпись его издателя;
- подтверждает связь между именем A и открытым ключом A;
- выдан центром сертификации, которому B доверяет.
Если B найдет такой сертификат открытого ключа A, то он сможет проверить подлинность этого сертификата с помощью открытого ключа центра сертификации. Однако теперь у B возникает следующий вопрос: как убедиться в том, что этот открытый ключ действительно принадлежит данному центру сертификации? B нужно найти сертификат, удостоверяющий подлинность этого центра сертификации. Таким образом в процессе проверки сертификата B продвигается по цепочке сертификатов (certification path). В конце цепочки сертификатов, ведущей от сертификата открытого ключа A через ряд центров сертификации, находится сертификат, выданный тем ЦС, которому B полностью доверяет. Такой сертификат называется доверенным корневым сертификатом (trusted root certificate), поскольку он образует в иерархии связей «открытые ключи – личность» корень (самый верхний узел), который B считает надежным. Если B явно решит доверять этому доверенному корневому сертификату, то он неявно будет доверять всем сертификатам, выданным доверенным корневым сертификатом и всеми сертифицированными им ЦС. Набор доверенных корневых сертификатов, которым B доверяет явно - это единственная информация, которую B должен получить надежным способом. На этом наборе сертификатов базируется его система доверия и обоснование надежности инфраструктуры открытых ключей.
схемы электронной цифровой подписи
Аппарат электронной цифровой подписи позволяет решать задачи проверки целостности и их авторства (без возможности отречения), разумеется, если используются стойкие алгоритмы формирования ЭЦП, надежные криптографические протоколы и сохранен в тайне секретный ключ. Поэтому для того, чтобы документы, подписанные ЭЦП, имели юридическую силу, развитые государства принимают стандарты на алгоритмы ЭЦП, кроме того, существует ряд коммерческих алгоритмов, которые хоть в среднем и слабее национальных, однако достаточно надежны для коммерческого уровня при разумном выборе длины ключей. Ниже будут описаны 9 алгоритмов формирования цифровой подписи:
- ГОСТ Р34.10-01;
- ECDSA;
- ESIGN;
- RSA-PSS;
- схема Шнорра;
- ElGamal;
- электронная цифровая подпись СТБ 1176.2-99;
- схема Диффи-Лампорта;
- вероятностная схема подписи Рабина.
ГГОСТ Р34.10-01 и ECDSA - стандарты в России и США соответственно, а алгоритмы ESIGN, RSA-PSS - претенденты в конкурсе проекта NESSIE (Евросоюз).
схема цифровой подписи ГОСТ Р 34.10-01
В основу безопасности российского стандарта электронной цифровой подписи ГОСТ Р 34.10-2001 и его американского аналога ECDSS положена задача дискретного логарифмирования на эллиптической кривой. Эллиптическая кривая E(Fp) в форме Вейерштрасса задается уравнением
y2 = f(x) (mod p),
где кубический многочлен f(x) не имеет кратных корней в поле Fp.
В основу протокола электронной цифровой подписи ГОСТ Р 34.10-2001 положен протокол Эль-Гамаля. Этот протокол обладает вычислимыми морфизмами, позволяющими на основании одного подписанного сообщения создавать произвольное число формально правильных пар сообщение-подпись, поэтому подпись вычисляется для значения хэш-функции от сообщения. Пусть m - подписываемое сообщение, h - хэш-функция по ГОСТ Р 34.11-94, {E(Fp), Q, P} - открытый ключ, число l, - секретный ключ, при этом P = lQ. Для формирования подписи выполняются следующие действия:
- вычисляется хэш-функция e = h(m) ( mod r ), причем e не равно 0;
- вырабатывается случайный показатель k, 0 < k < r, и вычисляется точка R = (xR, yR) = kQ, причем xR не равно 0 (mod r);
- вычисляется часть подписи
s = (lxR + ke) (mod r),
причем s неравно 0.
Подписанное сообщение представляет собой тройку (m, xR (mod r), s). Для проверки подписи выполняются следующие действия:
- проверяются условия 0 < xR (mod r) < r и 0 < s < r;
- вычисляется e = h(m) (mod r) и если e = 0, то считается e = 1;
- вычисляется точка R' = (se-1 (mod r))Q - (xRe -1 (mod r))Q;
- проверяется сравнение xR' = xR (mod r).
Если сравнение выполняется, то подпись верна.
Для обеспечения высокой сложности задачи дискретного логарифмирования на эллиптической кривой необходимо выполнение следующих условий, предусмотренных ГОСТ Р 34.10-2001:
- p - простое число длины 256 бит;
- многочлен f(x) не имеет кратных корней (дискриминант многочлена f отличен от нуля);
- многочлен f(x) не должен задаваться неполным уравнением;
- число точек |E(Fp)| имеет простой делитель r длины от 254 до 256 бит;
- порядок группы E(Fp) |E(Fp)| неравен p;
- pk неравно 1 (mod r) для k = 1,... , 30.
Безопасность протокола подписи непосредственно зависит от сложности обращения хэш-функции и сложности вычисления коллизий хэш-функции, так как в первом случае можно вычислить сообщение для имеющейся подписи, а во втором — заготовить пару сообщений с одинаковыми значениями e, подписать одно из них, а потом заменить одно сообщение другим.
схема электронной цифровой подписи ECDSA
Пусть p>2 простое число. Эллиптическая кривая E задается уравнением
y 2 = x3+ax+b (mod p ) (*)
над конечным простым полем. Предположим, что группа E(Fp) содержит подгруппу простого порядка q, которая порождается точкой G из группы E(Fq). Перейдем к рассмотрению протокола электронной цифровой подписи. Известными считаются эллиптическая кривая (*), в том числе простое число p и точка G из группы E(Fp). Секретным ключем является s (mod q), а открытым - точка W=sG из E(Fp).
Пусть вычет m (mod q) - хэш-значение подписываемого сообщения. Чтобы получить подпись для m, необходимо выполнить следующие шаги.
1. Выбирать случайный вычет u(mod q) ( и хранить его в секрете), где 0<u<q. Вычислить точку V = uG =(xV,yV), где представитель класса вычетов xV выбирается из фиксированного интервала 0 < xV < p.
2. Вычислить c=xV (mod q) . Если c=0(mod q) , то перейти к шагу 1. В противном случае вычислить d=u-1 (m+sc)(mod q).Если d=0 (mod q) , то перейти к шагу 1. В противном случае пара чисел (c,d), где 0<c,d<q есть подпись для m.
Чтобы проверить подпись под сообщением m (хэш-значением сообщения) необходимо выполнить следующие шаги.
1. Вычислить h=d-1 (mod q) и вычеты h1 =hm (mod q), h2 = hc (mod q).
2. Вычислить точку P=h1G+h2W =(xP,yP), 0 <= xP <p.
3. Если c=xP (mod q), то подпись принимается, в противном случае - отвергается.
Несложно заметить, что эта схема, как и новый ГОСТ, является переложением стандарта DSA на эллиптические кривые. В одной из работ высказано предположение о том, что этот переход связан с большими успехами специальных служб России и США в решении задач дискретного логарифмирования.
слабость цифровой подписи ECDSA
Есть мнение, что новый стандарт небезопасен, так как позволяет имитировать подмену подписи. По его мнению, недостаток ECDSA в том, что этот стандарт позволяет рядовому пользователю выбрать свои секретный и открытый ключи так, что подписи для двух известных заранее сообщений совпадут. А это открывает простор для различных махинаций с использованием ЭЦП. Возможность имитации подделки основывается на том, что x-координаты противоположных точек эллиптических кривых совпадают. Если qG=0, то (q-1)G = -G, следовательно справедливы равенства:
c1 = xG = c2 = x(q-1)G = c,
где 0 - бесконечно удаленная точка эллиптической кривой (нейтральный элемент относительно операции +). Положим случайные вычеты q1 и q2 равными 1 и (q-1). Отметим также, что (q-1)-1 = (q-1) (mod q).
Подберем две одинаковые подписи для сообщений m1 и m2. Уравнения подписи имеют вид:
d1 = u1 -1 (m1 + sc) (mod q) = (m1 + sc) (mod q)
d2 = u2 -1 (m2 + sc) (mod q) = (q-1)(m2 + sc) (mod q)
Нам нужно, чтобы выполнялось равенство d1 = d2. Получим уравнение:
m1+sc = (q-1)(m2 +sc) (mod q)
Отсюда легко находится s:
2cs = (q-1)(m1 + m2) (mod q)
Так как q - простое число, то это уравнение однозначно разрешимо относительно s. Таким образом, мы получили две одинаковые подписи для двух заранее выбранных сообщений.
ESIGN --- это схема подписи, предложенная Okamoto и Shiraishi в 1985 году. Она использует вычисления в кольце вычетов со специальным типом модуля. Главное преимущество схемы ESIGN --- это ее скорость. В сравнении с системами, основанными на схеме RSA или схеме Эль-Гамаля, ESIGN отличается в несколько раз более высоким быстродействием процессов подписи документа и проверки подписи.
Пусть N = p2 q - 3k-разрядное целое, где p и q - два простых числа примерно одинаковой длины. Секретную часть ключа составляют два k-битных простых числа p и q, а открытую часть ключа - пара (N,e), где e - целое число больше четырех. Схема Esign использует (k-1)-битную хэш-функцию H, для вычисления хэш-значения от подписываемого сообщения. Подпись для сообщения M вычисляется следующим образом:
1. Сообщение M сначала хэшируется, то есть вычисляется H(M). Мы обозначим за y 3k-разрядное целое число, соответствующее битовой строке 0||H(M)||02k, где 02k - последовательность из 2k нулей.
2. Число r случайно выбирается из Z p q * (обратимые элементы кольца Z p q).
3. Вычисляются значения:
4.
z = x - r e (mod N).
w0 = ? z/pq ? + 1.
w1 = w0 pq - z.
Если w1 > 22k-1, тогда снова выполняется шаг 2.
u = w0 (e re-1)-1 (mod p).
s = r + u*p*q.
5. Подписью M будет s.
Для проверки правильности подписи сообщения M проверяющий просто сравнивает k старших разрядов se (mod N) с 0||H(M) и на основании этого сравнения делает вывод о принятии (если битовые последовательности совпадают) или отклонении (если битовые последовательности не совпадают) подписи. Истинность алгоритм проверки подписи следует из
se = (r + u*p*q)e (mod N) = re + e*r e-1*u*p* q ( mod N) = (y-z) + w0*p*q ( mod N) = y + w1 (mod N).
Так как w1 < 2 2k-1 и N - в точности 3k-разрядное целое число, то k старших разрядов (se (mod N) ) те же, что и у y, то есть 0||H(M). Стойкость схемы Esign основывается на разновидности проблемы RSA, на извлечении корня e-й степени в кольце вычетов. Точнее, вычислении приближенного значения корня, что считается сложной задачей. Формально задача извлечения приближенного корня (AER Approximate e-th Root problem ) описывается следующим образом: даны модуль N = p2*q, экспонента e>3 и y - обратимый элемент кольца вычетов ZN, найти x - обратимый элемент кольца вычетов ZN такой, что y <= xe <= y + 22k-1. Известно, что факторизация N дает эффективное решение данной задачи.
Предположение AER заключается в том, что проблема AER является трудноразрешимой.
Важно отметить, что в первоначальном варианте схемы допускался выбор экспоненты e равной 2 или 3, что упрощало вычисление подписи и ее проверку. Однако в этом случае имеются алгоритмы криптоанализа данной схемы, разработанные E. F. Brickell, J. M. DeLaurentis и A. M. Odlyzko. В их работе cказано, что случайные числа r должны выбираться независимо, случайно и равновероятно из Zp*q*. В частности, использование линейного конгруэнтного генератора для задания r с опубликованными параметрами приводит к компроментации секретного ключа.
схема цифровой подписи RSA PSS-ES
Ниже будет рассмотрена вероятностная схема цифровой подписи на основе PSS-R (Probabilistic Signature Scheme with message recovery, вероятностная схема цифровой подписи с восстановлением сообщения в процессе проверки подписи). В этой схеме рекомендуется (но не навязывается) использование криптосистемы RSA, что и отражено в ее названии. Ее основное достоинство заключается в том, что можно использовать один и тот же ключевой набор для шифрования с открытым ключом и для цифровой подписи. То есть, если абонент A, посылая сообщение абоненту B, шифрует это сообщение с помощью открытого ключа B - пары (N,e). Абонент B дешифрует зашифрованное сообщение с помощью соответствующего секретного ключа - (N,d). Для того чтобы подписать сообщение M, пользователь B использует тот же секретный ключ (N,d). Как обычно, любой желающий может проверить эту подпись, используя открытый ключ B (N,e).
Опишем саму схему PSS-ES. Параметрами схемы являются целые числа k, k1, k0 и две хэш-функции:
H:{0,1}k-k 1 --> {0,1} k 1
и
G:{0,1} k 1 --> {0,1}k-k 1
Схема набивки, используемая в этой системе, описывается следующим образом:
?(M,k) = w||s
Схема шифрования и цифровой подписи PSS-ES основана на PSS-R и k-разрядной однонаправленной функции с ловушкой f. Как PSS-R схема подписи PSS-ES восстанавливает сообщение в процессе проверки подписи. Поэтому можно подписывать только сообщения фиксированной длины - (k - k0 - k1) бит. Для подписи сообщения M произвольной длины необходимо использовать хэш-функцию.
схема цифровой подписи Клауса Шнорра(Schnorr)
Стойкость схемы Шнорра основывается на трудной задаче вычисления дискретных логарифмов. Для генерации пары ключей сначала выбираются два простых числа p и q так, чтобы q было сомножителем p-1. Затем выбирается a, не равное 1, такое что aq = 1 ( mod p). Все эти числа могут быть свободно опубликованы и использоваться группой пользователей. Для генерации конкретной пары ключей выбирается случайное число, меньшее q. Оно служит закрытым ключом, s. Затем вычисляется открытый ключ v = a-s (mod p). Для подписи сообщений используется хэш-функция H(M).
Предварительные вычисления. Пользователь A выбирает случайное число r, меньшее q, и вычисляет x = ar (mod p).
Подпись сообщения M. Для того, чтобы подписать сообщение M пользователю A необходимо выполнить следующие действия:
1. Объединить M и x и хэшировать результат: e = H(M,x).
2. Вычислить y = (r + se) (mod q). Подписью являются значения e и y, их нужно выслать получателю B.
Проверка подписи для сообщения M. Получатель B вычисляет x' = ay ve (mod p). Затем он проверяет, что хэш-значение для объединения M и x' равно e. e = H(M,x') Если это так, то он считает подпись верной. В своей работе Шнорр приводит следующие свойства своего алгоритма:
1. Большая часть вычислений, нужных для генерации подписи и независящих от подписываемого сообщения, может быть выполнена на стадии предварительных вычислений. Следовательно, эти вычисления могут быть выполнены во время простоя и не влияют на скорость вычисления подписи. 2. При одинаковом уровне безопасности длина подписей для Schnorr короче, чем для RSA. Например, при 140-битовом q длина подписей равна всего лишь 212 битам, меньше половины длины подписей RSA. Подписи Schnorr также намного короче подписей ElGamal.
схема цифровой подписи ElGamal
Для генерации ключевой пары выбираются большое простое число р и примитивный элемент g мультипликативной группы поля GF(p). Выбирается случайное число х такое, что x<p-1. Открытым ключом является y = gx ( mod p), секретным ключем является x.
Подпись сообщения M. Для того, чтобы подписать сообщение M пользователю A необходимо выполнить следующие действия:
1. Выбрать случайно и равновероятно число k из группы обратимых элементов кольца Z p-1 *. То есть НОД(k,p-1) = 1.
2. Вычислить a = gk (mod q).
3. Вычислить b = (M-xa)k-1 (mod p-1).
4. Подписью для сообщения M является пара (a,b).
Проверка подписи для сообщения M. Для проверки подписи (a,b) для сообщения M получатель B проверяет выполнение равенства gM = ya ab (mod p). Надо заметить, что для ускорения процесса подписи вычисления на шагах 1 и 2 можно проводить заранее, вычислять значения k-1 тоже. Как и в других похожих схемах подписи значение k должно оставаться в секрете и выбираться cлучайно.
электронная цифровая подпись СТБ 1176.2-99
Введенный в 1999г. стандарт Республики Беларусь СТБ 1176.2 "Информационная технология. Защита информации. Процедуры выработки и проверки электронной цифровой подписи " базируется на схеме ЭЦП Шнорра.
Параметры. При выработке и проверке подписи используются l-битовое простое число p и r-битовое простое число q, q | (p-1). Допустимые значения указаны в таблице 1. Применяется определяемая СТБ 1176.1 функция хеширования h, параметр L которой устанавливается равным (r-1).
Таблица 1. Допустимые значения параметров r и l.
Часть преобразований стандарта выполняется в группе G, определяемой множеством Bp = {1,2, ...,p-1 } и операцией *
u * v = uvR-1 ( mod p),
где R = 2l+2. Использование операции * вместо обычного умножения по модулю p упрощает применение алгоритма Монтгомери. Далее, u(m) - m-я степень числа u из Bp как элемента G. В стандарте приведены алгоритмы генерации чисел p,q и элемента a из Bp, имеющего порядок q в группе G. Числа p, q, a являются долговременными параметрами СТБ 1176.2-99, едиными для группы пользователей.
Входные данные. Всякое сообщение M, подпись к которому вырабатывается или проверяется, задается последовательностью байтов. Если t- n-разрядное число по основанию 28 = 256, то есть
t = t0 (256)0+..+tn-1 (256)n-1
причем 0 <= ti <256, tn-1 не равно 0, то t||M --- сообщение, полученное вставкой байтов t0, t1,..,tn-1 в начало M.
Выработка подписи. При выработке подписи S к сообщению M используется личный ключ x, 0<x<q. Выполняются следующие шаги.
1. Выработать случайное секретное число k, 1<k<q.
2. t = a(k).
3. U = h(t||M). Если U=0, то вернуться к шагу 1.
4. V = (k-xU). Если V=0, то вернуться к шагу 1.
5. S = U2r+V.
Проверка подписи. При проверке подписи S к сообщению M используется открытый ключ y = a(X). Алгоритм проверки подписи состоит из следующих шагов.
1. V = S ( mod 2r).
2. U = (S-V)/2r.
3. Проверить условия 0<U<2r-1, 0<V<q. Если хотя бы одно из условий
нарушается, то подпись признается недействительной и выполнение
алгоритма завершается.
4. t = a(V) * y(U).
5. W = h(t||M).
6. Если W неравно U, то подпись признается недействительной. Если W=U, то принимаются решения о том, что:
а) подпись S была создана с помощью личного ключа x, связанного с открытым ключем y;
б)подпись S и сообщение M не были изменены с момента их создания.
схема Диффи-Лампорта
Для аутентификации пользователя можно применять произвольную симметрическую схему. Пусть отправитель сообщения A хочет подписать n-битовое бинарное сообщение m=m1.. mn из V2n.
Он выбирает 2n ключей некоторой криптосистемы, которые хранятся в секрете. Обозначим их так: a1,..,an;b1,..,bn.
Если E - алгоритм шифрования, то A генерирует 4n параметров проверки { (Xi,Yi,Ui,Vi): 1<= i <= n}, где Xi и Yi - величины, подаваемые на вход E и связанные соотношениями
Ui = E(Xi,ai)
Vi = E(Yi,bi)
1 <= i < n
Параметры проверки заранее посылаются получателю B и третьему доверенному лицу.
Чтобы подписать n-битовое сообщение m=(m1,..,mn), пользователь A применяет следующую процедуру: его подпись будет цепочкой S = S1 ..Sn, где для каждого i
Si = ai, если mi =0
Si = bi, если mi =1
Пользователь B проверяет подпись следующим образом: для каждого i (0 <= i <= n) он использует бит mi и ключ Si, чтобы проверить:
если mi = 0, то E(Xi,Si) = Ui
если mi = 1, то E(Yi,Si) = Vi
Пользователь B принимает подписанное сообщение за истинное только в том случае, если при процедуре проверки эти равенства выполнены для каждого L.
Эта система проста в использовании, но у нее есть, по крайней мере, два очевидных недостатка. Во-первых, необходима предварительная передача параметров проверки. Во-вторых, что более важно, подпись сильно увеличивает длину сообщения. Если в криптосистеме используются ключи длиной, скажем, 64 бита, то длина подписанного сообщения увеличится в 64 раза.
вероятностная схема подписи Рабина
В 1978 г. Рабин предложил следующий способ подписи. Пусть E - функция шифрования некоторой криптосистемы, (ki, 1 <= i <= 2r) -
последовательность случайно выбранных ключей, которые отправитель A держит в секрете. Пользователь B получает список параметров проверки (Xi,Ui) (1 <= i <= 2r), где
E(Xi,ki) = Ui (1 <= i <= 2r)
Эти параметры хранятся в доступном для всех месте.
Предположим, что A хочет подписать сообщение m. Его подписью будет цепочка S = S1S2..S2r, для каждого i (1<=i<=2r) Si =E(m,ki). B делает следующее. Сначала он выбирает случайным образом r ключей, которые A должен ему предъявить: ki1 , ki2 ,..,kir. При получении этих ключей от A он проверяет:
E(m,ki1) = Si1
E(Xi1,ki1) = Ui1
и далее для всех индексов i2, i3 ,.., ir . Он считает действительной подпись от A только в том случае, когда выдерживаются все проверки. Безопасность получателя зависит от его уверенности в том, что только отправитель, знающий секретный ключ, может послать так подписанное сообщение. Что касается A, то предположим, что он отказывается от сообщения, которое по утверждению B он подписал. Тогда протокол для A следующий: он должен предъявить судье свои секретные ключи k1,k2,..,k2r, и в присутствии обеих сторон делается 2r проверок:
E(m,ki)=Si, E(Xi,ki)=Ui
Рассмотрим, что это означает в трех возможных случаях.
1. Корректными являются менее r проверок. Тогда B не должен был принимать подписанное сообщение.
2. Выдерживается точно r проверок, то есть при формировании ключей B выбрал именно это подмножество из r ключей. Вероятность, что он угадает это подмножество, равна pr = (C2r r)-1, для r=18, pr примерно равно 10-10.
3. Выдерживается r+1 и более проверок: отказ абонента A не принимается.
заключение
Криптография уверенно входит в повседневную жизнь, каждый пользователь компьютера неявно пользуется различными крипографическими алгоритмами. Это и установка защищенного соединения по протоколам SSL/TLS, и автоматическая проверка цифровой подписи программ или драйверов, и постянный рост использования электронных документов для проведения финансовых операций. Аппарат ЭЦП, возникший как развитие идей криптографии с открытым ключем, начинает играть всю большую роль в системе электронных коммуникаций.
Большое значение аппарата электронных цифровых подписей в современном мире отражается принятием национальных (ГОСТ, СТБ, ECDSA, ESIGN) и коммерческих (RSA) стандартов цифровой подписи. Рассмотренные выше стандарты определяют технические аспекты применения цифровых подписей. Однако возникают вопросы юридического характера:
- Как придать документам, существующим только в электронном виде, тот же правовой статус, котрый имеется у бумажных документов?
- Как обеспечить защищенный, надежный и юридически законный метод подписи электронных документов, который исключит необходимость создавать и подписывать бумажные документы, тем самым поощряя и облегчая электронную коммерцию?
Эти два вопроса носят скорее юридический характер, поэтому в настоящее время в большинстве развитых стран приняты нормативные акты, регулирующие взаимоотношения субъектов, использующих ЭЦП. Но ЭЦП - это не только инструмент для ведения электонного документооборота, но и новый интересный криптографический примитив, поэтому много математиков занимаются исследованиями в области схем цифровой подписи/идентификации.
По материалам реферата слушателя 4 курса ИКСИ, научный руководитель – Сергей Кунегин
- конфиденциальности - ознакомлении с документом лиц, не имеющим на это права;
- целостности - модификация (изменение) документа лицом, не имеющим на это права;
- авторства - возможность создать электронный документ от имени другого лица или подделки его атрибутов, например, времени создания.
Еще совсем недавно основной аспект защиты документооборота заключался в сохранении конфиденциальности (секретности) предаваемых сообщений. И как отправитель, так и получатель секретных сообщений были заинтересованы в сохранении тайны и целостности переданного сообщения. В этих условиях достижение конфиденциальности, целостности и проверка авторства решались с применением средств традиционной (симметричной) криптографии. Считается, что использование надежных шифров и сохранение в тайне ключевой информации обеспечивает надежную защиту информации от прочтения противником. Действительно, не зная секретного ключа очень трудно прочитать перехваченное сообщение, если используется стойкий шифр. А для защиты от случайных или преднамеренных искажений применялись так называемые имитовставки. Имитовставка зависит от секретного ключа и всего массива данных весьма сложным образом, поэтому подделать ее, не зная ключа, невозможно. Так как секретный ключ известен только двум (или некоторой группе) корреспондентов, то получение сообщения, защищенного имитовставкой, выработанной на данном ключе, подтверждает принадлежность автора сообщения к этой группе.
электронная цифровая подпись
Механизм электронной цифровой подписи (ЭЦП) возник как побочный эффект криптографии с открытым ключом. Поэтому характерное для систем с открытым ключом разделение ключа на 2 части - секретную и несекретную - позволяет реализовать возможность проверки подлинности без возможности подписать другой документ.
Итак, цифровая подпись - это конечная цифровая последовательность, зависящая от самого сообщения или документа и от секретного ключа, известного только подписывающему субъекту, предназначенная для установления авторства. Так как цифровая подпись строится на базе криптосистемы с открытым ключом, то необходимо иметь пару ключей - секретный и открытый. Секретный ключ используется для формирования цифровой подписи, поэтому его нужно хранить в тайне. А открытый ключ используется для проверки соответствия подписи документу, поэтому он должен быть опубликован, например, в общедоступном каталоге.
Предположим, что абонент A уже сформировал свою пару секретного и открытого ключей и на их основе построил функции DKA(x) и EKA(x). Причем для любого x должно выполнятся равенство EKA(DKA(x)) = x. Функцию DKA(x) будем называть функцией подписи сообщения x, а функцию EKA(x) - функцией проверки подписи для сообщения x. В дальнейшем будем отождествлять функции DKA(x) и EKA(x) с секретным и открытым ключами пользователя A соответственно. Надо заметить, что функции DKA(x) и EKA(x) связаны (так как связаны секретный и открытый ключи), однако по опубликованной функции EKA(x) вычислительно невозможно восстановить функцию DKA(x).
Рассмотрим схему взаимодействия отправителя (A) и получателя (B), которая позволяет B проверить подлинность передаваемого сообщения.
1. A создает сообщение x, которое он собирается подписать и вычисляет подпись DKA(x).
2. A передает B пару (x,DKA(x)).
3. B проверяет равенство EKA(DKA(x)) = x. В случае совпадения обоих величин B принимает решение о подлинности сообщения x, в противном случае B принимает решение считать сообщение x искаженным.
Рассмотренный протокол взаимодействия имеет следующий недостаток: так как функция EKA(x) - опубликована, то злоумышленник C может для любого z вычислить EKA(z) и предать в канал связи пару (EKA(z),z). Несложно видеть, что в этом случае z, будет подписью для EKA(z). Для предотвращения такой возможности пользователи должны подписывать не сами сообщения, а их хэши, то есть значения хэш-функции от сообщения.
Напомним определение хэш-функции. Функция h:X -> M называется хэш-функцией, если выполнены следующие условия:
1. Постоянство размера - для входного массива данных любого размера результатом должен быть блок данных фиксированного размера.
2. Функция h(x) легко вычислима.
3. Функцию h(x) трудно инвертировать, то есть почти для всех m из M трудно найти x из X такой, что h(x) = m.
4. Для данного x сложно найти x' неравный x такой, что h(x) = h(x').
5. Сложно найти пару (x, x') из X2 такую, что x неравен x' и h(x) = h(x').
Где M - множество векторов фиксированной длины, а X - вектора произвольной длины. Пара (x, x') из X2 такая, что x неравно x' и h(x) = h(x') называется коллизией хэш-функции h.
Помимо устранения рассмотренной выше возможности создания подписи без знания секретного ключа, использование хэш-функции решает еще одну проблему: дело в том, что функции EKA(x) и DKA(x) оперируют с блоками данных фиксированного размера, а размер сообщения может превышать этот размер. Без использования хэш-функции подписывать сообщение x пришлось бы следующим образом:
x = (x1,..,xk) \to ( (x1,DKA(x1)),.., (xk,DKA(xk))),
где x1,..,xk - векторы фиксированной длины, совпадающей с длиной входа функций EKA(x) и DKA(x). Подобная подпись обладает следующими недостатками:
- для больших документов слишком сильно загружается процессор, так как придется много раз вычислять функцию DKA(xi);
- злоумышленник может набрать достаточно большой набор пар (xi, DKA(xi)) и сам формировать сообщения из фрагментов.
Модифицированный протокол выглядит таким образом:
1. A создает сообщение x, которое он собирается подписать и вычисляет его хэш h(x), после чего подписывает DKA(h(x)).
2. A передает B пару (x,DKA(h(x))).
3. B проверяет равенство EKA(DKA(h(x))) = h(x). В случае совпадения обоих величин B принимает решение о подлинности сообщения x, в противном случае B принимает решение считать сообщение x искаженным.
В этом протоколе возможность подделки подписи может быть основана на нахождении коллизии хэш-функции, то есть по известному значению h(x) найти x' такой, что h(x) = h(x'). Для предотвращения этой возможности нельзя использовать непроверенные функции. Как правило, стойкие к коллизиям хэш- функции описаны в государственном стандарте. В Российской Федерации этот стандарт носит название ГОСТ Р 34.11-94, в США - описывается документами FIPS 180-1 и FIPS 180-2, а в Евросоюзе рекомендуется использование стандарта Whirlpool.
Российский стандарт хэширования был принят в 1994 году и с тех пор не изменялся, размер хэш-блока для него составляет 256 бит. В США изначально действовал стандарт SHS (Secure Hash Standard), где размер хэш-блока был равен 160 бит. Однако в 2002 году стандарт был пересмотрен: прежний остался действовать и получил обозначение SHA-1, но к нему были добавлены три новых алгоритма, вырабатывающие хэш-блоки размером 256, 384 и 512 бит, названные SHA-256/384/512 соответственно.
механизм сертификатов
Однако рассмотренные выше протоколы не учитывают один факт: а как пользователю B убедиться, что открытый ключ EKA принадлежит отправителю A? Рассмотрим подробнее проблему доверия пользователя B открытому ключу отправителя A. При использовании цифровой подписи A и B нужно защищать только свои личные секретные ключи. А открытые ключи им нужно использовать совместно. Хранить их в секрете нет необходимости, нужна лишь возможность идентифицировать открытый ключ другой стороны. Поэтому для применения цифровой подписи критическое значение имеет доверие к соответствию между известным субъектом и его открытым ключом. B может доверять открытому ключу A, если A передал ему ключ безопасным способом. Но безопасность передачи обеспечивается только защищенными средствами связи. Более вероятно, что B получил открытый ключ A с помощью незащищенного средства связи (например, из общего каталога), поэтому нужен механизм, который может обеспечить B уверенность в том, что имеющийся у него открытый ключ действительно принадлежит A, а не кому-либо другому.
Один их таких механизмов основан на сертификатах (certificate), выдаваемых центром сертификации (certification authority). Сертификаты обеспечивают механизм надежной связи между открытым ключом и субъектом, которому принадлежит соответствующий личный ключ. Сертификат - это цифровой документ, который содержит открытый ключ субъекта (subject public key) и подписан электронной цифровой подписью его издателя (issuer). Сертификат также содержит сведения о владельце открытого ключа, например, информацию, которая его дополнительно идентифицирует. Таким образом, выдавая сертификат, издатель удостоверяет подлинность связи между открытым ключом субъекта и информацией, его идентифицирующей. В настоящее время наиболее часто используются сертификаты на основе стандарта Международного союза телекоммуникаций ITU-T X.509 версии 3 и рекомендаций IETF (Internet Engineering Task Force) RFC 2459. Например, формат сертификата X.509 принят в протоколах S/MIME, IP Security, а также SSL/TLS и SET. Кроме того, это базовая технология, используемая в инфраструктуре открытых ключей операционной системы Windows 2000. Однако это не единственный вид сертификатов. Например, система защиты сообщений электронной почты PGP (Pretty Good Privacy) использует свою специфическую форму сертификатов.
Центр сертификации (ЦС) --- это служба, которая выдает сертификаты.
Центр сертификации является гарантом связи между открытым ключом субъекта и содержащейся в сертификате информацией по идентификации этого субъекта. Различные ЦС устанавливают и гарантируют эту связь различными способами, поэтому прежде чем доверять сертификатам того или иного ЦС, следует ознакомиться с его политикой и регламентом.
подтверждение доверия
Когда B получает подписанное сообщение, у него возникает важный вопрос: можно ли этой подписи доверять? Иными словами, действительно ли эта подпись принадлежит отправителю сообщения? B может проверить целостность подписи с помощью известного ему открытого ключа отправителя и криптографических алгоритмов. Однако при этом B должен быть уверен в том, что использованный им для проверки открытый ключ действительно принадлежит тому субъекту, именем которого подписано сообщение. Если у B нет прямого доказательства, что открытый ключ принадлежит A, то ему надо получить хотя бы достаточно веское подтверждение этого. Если B сможет найти сертификат открытого ключа A, выданный тем центром сертификации, которому он доверяет, то он получит убедительное подтверждение того, что открытый ключ A действительно принадлежит A. Итак, у B появится веское основание полагать, что открытый ключ принадлежит именно A, если он найдет сертификат, который:
- имеет действительную с криптографической точки зрения подпись его издателя;
- подтверждает связь между именем A и открытым ключом A;
- выдан центром сертификации, которому B доверяет.
Если B найдет такой сертификат открытого ключа A, то он сможет проверить подлинность этого сертификата с помощью открытого ключа центра сертификации. Однако теперь у B возникает следующий вопрос: как убедиться в том, что этот открытый ключ действительно принадлежит данному центру сертификации? B нужно найти сертификат, удостоверяющий подлинность этого центра сертификации. Таким образом в процессе проверки сертификата B продвигается по цепочке сертификатов (certification path). В конце цепочки сертификатов, ведущей от сертификата открытого ключа A через ряд центров сертификации, находится сертификат, выданный тем ЦС, которому B полностью доверяет. Такой сертификат называется доверенным корневым сертификатом (trusted root certificate), поскольку он образует в иерархии связей «открытые ключи – личность» корень (самый верхний узел), который B считает надежным. Если B явно решит доверять этому доверенному корневому сертификату, то он неявно будет доверять всем сертификатам, выданным доверенным корневым сертификатом и всеми сертифицированными им ЦС. Набор доверенных корневых сертификатов, которым B доверяет явно - это единственная информация, которую B должен получить надежным способом. На этом наборе сертификатов базируется его система доверия и обоснование надежности инфраструктуры открытых ключей.
схемы электронной цифровой подписи
Аппарат электронной цифровой подписи позволяет решать задачи проверки целостности и их авторства (без возможности отречения), разумеется, если используются стойкие алгоритмы формирования ЭЦП, надежные криптографические протоколы и сохранен в тайне секретный ключ. Поэтому для того, чтобы документы, подписанные ЭЦП, имели юридическую силу, развитые государства принимают стандарты на алгоритмы ЭЦП, кроме того, существует ряд коммерческих алгоритмов, которые хоть в среднем и слабее национальных, однако достаточно надежны для коммерческого уровня при разумном выборе длины ключей. Ниже будут описаны 9 алгоритмов формирования цифровой подписи:
- ГОСТ Р34.10-01;
- ECDSA;
- ESIGN;
- RSA-PSS;
- схема Шнорра;
- ElGamal;
- электронная цифровая подпись СТБ 1176.2-99;
- схема Диффи-Лампорта;
- вероятностная схема подписи Рабина.
ГГОСТ Р34.10-01 и ECDSA - стандарты в России и США соответственно, а алгоритмы ESIGN, RSA-PSS - претенденты в конкурсе проекта NESSIE (Евросоюз).
схема цифровой подписи ГОСТ Р 34.10-01
В основу безопасности российского стандарта электронной цифровой подписи ГОСТ Р 34.10-2001 и его американского аналога ECDSS положена задача дискретного логарифмирования на эллиптической кривой. Эллиптическая кривая E(Fp) в форме Вейерштрасса задается уравнением
y2 = f(x) (mod p),
где кубический многочлен f(x) не имеет кратных корней в поле Fp.
В основу протокола электронной цифровой подписи ГОСТ Р 34.10-2001 положен протокол Эль-Гамаля. Этот протокол обладает вычислимыми морфизмами, позволяющими на основании одного подписанного сообщения создавать произвольное число формально правильных пар сообщение-подпись, поэтому подпись вычисляется для значения хэш-функции от сообщения. Пусть m - подписываемое сообщение, h - хэш-функция по ГОСТ Р 34.11-94, {E(Fp), Q, P} - открытый ключ, число l, - секретный ключ, при этом P = lQ. Для формирования подписи выполняются следующие действия:
- вычисляется хэш-функция e = h(m) ( mod r ), причем e не равно 0;
- вырабатывается случайный показатель k, 0 < k < r, и вычисляется точка R = (xR, yR) = kQ, причем xR не равно 0 (mod r);
- вычисляется часть подписи
s = (lxR + ke) (mod r),
причем s неравно 0.
Подписанное сообщение представляет собой тройку (m, xR (mod r), s). Для проверки подписи выполняются следующие действия:
- проверяются условия 0 < xR (mod r) < r и 0 < s < r;
- вычисляется e = h(m) (mod r) и если e = 0, то считается e = 1;
- вычисляется точка R' = (se-1 (mod r))Q - (xRe -1 (mod r))Q;
- проверяется сравнение xR' = xR (mod r).
Если сравнение выполняется, то подпись верна.
Для обеспечения высокой сложности задачи дискретного логарифмирования на эллиптической кривой необходимо выполнение следующих условий, предусмотренных ГОСТ Р 34.10-2001:
- p - простое число длины 256 бит;
- многочлен f(x) не имеет кратных корней (дискриминант многочлена f отличен от нуля);
- многочлен f(x) не должен задаваться неполным уравнением;
- число точек |E(Fp)| имеет простой делитель r длины от 254 до 256 бит;
- порядок группы E(Fp) |E(Fp)| неравен p;
- pk неравно 1 (mod r) для k = 1,... , 30.
Безопасность протокола подписи непосредственно зависит от сложности обращения хэш-функции и сложности вычисления коллизий хэш-функции, так как в первом случае можно вычислить сообщение для имеющейся подписи, а во втором — заготовить пару сообщений с одинаковыми значениями e, подписать одно из них, а потом заменить одно сообщение другим.
схема электронной цифровой подписи ECDSA
Пусть p>2 простое число. Эллиптическая кривая E задается уравнением
y 2 = x3+ax+b (mod p ) (*)
над конечным простым полем. Предположим, что группа E(Fp) содержит подгруппу простого порядка q, которая порождается точкой G из группы E(Fq). Перейдем к рассмотрению протокола электронной цифровой подписи. Известными считаются эллиптическая кривая (*), в том числе простое число p и точка G из группы E(Fp). Секретным ключем является s (mod q), а открытым - точка W=sG из E(Fp).
Пусть вычет m (mod q) - хэш-значение подписываемого сообщения. Чтобы получить подпись для m, необходимо выполнить следующие шаги.
1. Выбирать случайный вычет u(mod q) ( и хранить его в секрете), где 0<u<q. Вычислить точку V = uG =(xV,yV), где представитель класса вычетов xV выбирается из фиксированного интервала 0 < xV < p.
2. Вычислить c=xV (mod q) . Если c=0(mod q) , то перейти к шагу 1. В противном случае вычислить d=u-1 (m+sc)(mod q).Если d=0 (mod q) , то перейти к шагу 1. В противном случае пара чисел (c,d), где 0<c,d<q есть подпись для m.
Чтобы проверить подпись под сообщением m (хэш-значением сообщения) необходимо выполнить следующие шаги.
1. Вычислить h=d-1 (mod q) и вычеты h1 =hm (mod q), h2 = hc (mod q).
2. Вычислить точку P=h1G+h2W =(xP,yP), 0 <= xP <p.
3. Если c=xP (mod q), то подпись принимается, в противном случае - отвергается.
Несложно заметить, что эта схема, как и новый ГОСТ, является переложением стандарта DSA на эллиптические кривые. В одной из работ высказано предположение о том, что этот переход связан с большими успехами специальных служб России и США в решении задач дискретного логарифмирования.
слабость цифровой подписи ECDSA
Есть мнение, что новый стандарт небезопасен, так как позволяет имитировать подмену подписи. По его мнению, недостаток ECDSA в том, что этот стандарт позволяет рядовому пользователю выбрать свои секретный и открытый ключи так, что подписи для двух известных заранее сообщений совпадут. А это открывает простор для различных махинаций с использованием ЭЦП. Возможность имитации подделки основывается на том, что x-координаты противоположных точек эллиптических кривых совпадают. Если qG=0, то (q-1)G = -G, следовательно справедливы равенства:
c1 = xG = c2 = x(q-1)G = c,
где 0 - бесконечно удаленная точка эллиптической кривой (нейтральный элемент относительно операции +). Положим случайные вычеты q1 и q2 равными 1 и (q-1). Отметим также, что (q-1)-1 = (q-1) (mod q).
Подберем две одинаковые подписи для сообщений m1 и m2. Уравнения подписи имеют вид:
d1 = u1 -1 (m1 + sc) (mod q) = (m1 + sc) (mod q)
d2 = u2 -1 (m2 + sc) (mod q) = (q-1)(m2 + sc) (mod q)
Нам нужно, чтобы выполнялось равенство d1 = d2. Получим уравнение:
m1+sc = (q-1)(m2 +sc) (mod q)
Отсюда легко находится s:
2cs = (q-1)(m1 + m2) (mod q)
Так как q - простое число, то это уравнение однозначно разрешимо относительно s. Таким образом, мы получили две одинаковые подписи для двух заранее выбранных сообщений.
ESIGN --- это схема подписи, предложенная Okamoto и Shiraishi в 1985 году. Она использует вычисления в кольце вычетов со специальным типом модуля. Главное преимущество схемы ESIGN --- это ее скорость. В сравнении с системами, основанными на схеме RSA или схеме Эль-Гамаля, ESIGN отличается в несколько раз более высоким быстродействием процессов подписи документа и проверки подписи.
Пусть N = p2 q - 3k-разрядное целое, где p и q - два простых числа примерно одинаковой длины. Секретную часть ключа составляют два k-битных простых числа p и q, а открытую часть ключа - пара (N,e), где e - целое число больше четырех. Схема Esign использует (k-1)-битную хэш-функцию H, для вычисления хэш-значения от подписываемого сообщения. Подпись для сообщения M вычисляется следующим образом:
1. Сообщение M сначала хэшируется, то есть вычисляется H(M). Мы обозначим за y 3k-разрядное целое число, соответствующее битовой строке 0||H(M)||02k, где 02k - последовательность из 2k нулей.
2. Число r случайно выбирается из Z p q * (обратимые элементы кольца Z p q).
3. Вычисляются значения:
4.
z = x - r e (mod N).
w0 = ? z/pq ? + 1.
w1 = w0 pq - z.
Если w1 > 22k-1, тогда снова выполняется шаг 2.
u = w0 (e re-1)-1 (mod p).
s = r + u*p*q.
5. Подписью M будет s.
Для проверки правильности подписи сообщения M проверяющий просто сравнивает k старших разрядов se (mod N) с 0||H(M) и на основании этого сравнения делает вывод о принятии (если битовые последовательности совпадают) или отклонении (если битовые последовательности не совпадают) подписи. Истинность алгоритм проверки подписи следует из
se = (r + u*p*q)e (mod N) = re + e*r e-1*u*p* q ( mod N) = (y-z) + w0*p*q ( mod N) = y + w1 (mod N).
Так как w1 < 2 2k-1 и N - в точности 3k-разрядное целое число, то k старших разрядов (se (mod N) ) те же, что и у y, то есть 0||H(M). Стойкость схемы Esign основывается на разновидности проблемы RSA, на извлечении корня e-й степени в кольце вычетов. Точнее, вычислении приближенного значения корня, что считается сложной задачей. Формально задача извлечения приближенного корня (AER Approximate e-th Root problem ) описывается следующим образом: даны модуль N = p2*q, экспонента e>3 и y - обратимый элемент кольца вычетов ZN, найти x - обратимый элемент кольца вычетов ZN такой, что y <= xe <= y + 22k-1. Известно, что факторизация N дает эффективное решение данной задачи.
Предположение AER заключается в том, что проблема AER является трудноразрешимой.
Важно отметить, что в первоначальном варианте схемы допускался выбор экспоненты e равной 2 или 3, что упрощало вычисление подписи и ее проверку. Однако в этом случае имеются алгоритмы криптоанализа данной схемы, разработанные E. F. Brickell, J. M. DeLaurentis и A. M. Odlyzko. В их работе cказано, что случайные числа r должны выбираться независимо, случайно и равновероятно из Zp*q*. В частности, использование линейного конгруэнтного генератора для задания r с опубликованными параметрами приводит к компроментации секретного ключа.
схема цифровой подписи RSA PSS-ES
Ниже будет рассмотрена вероятностная схема цифровой подписи на основе PSS-R (Probabilistic Signature Scheme with message recovery, вероятностная схема цифровой подписи с восстановлением сообщения в процессе проверки подписи). В этой схеме рекомендуется (но не навязывается) использование криптосистемы RSA, что и отражено в ее названии. Ее основное достоинство заключается в том, что можно использовать один и тот же ключевой набор для шифрования с открытым ключом и для цифровой подписи. То есть, если абонент A, посылая сообщение абоненту B, шифрует это сообщение с помощью открытого ключа B - пары (N,e). Абонент B дешифрует зашифрованное сообщение с помощью соответствующего секретного ключа - (N,d). Для того чтобы подписать сообщение M, пользователь B использует тот же секретный ключ (N,d). Как обычно, любой желающий может проверить эту подпись, используя открытый ключ B (N,e).
Опишем саму схему PSS-ES. Параметрами схемы являются целые числа k, k1, k0 и две хэш-функции:
H:{0,1}k-k 1 --> {0,1} k 1
и
G:{0,1} k 1 --> {0,1}k-k 1
Схема набивки, используемая в этой системе, описывается следующим образом:
?(M,k) = w||s
Схема шифрования и цифровой подписи PSS-ES основана на PSS-R и k-разрядной однонаправленной функции с ловушкой f. Как PSS-R схема подписи PSS-ES восстанавливает сообщение в процессе проверки подписи. Поэтому можно подписывать только сообщения фиксированной длины - (k - k0 - k1) бит. Для подписи сообщения M произвольной длины необходимо использовать хэш-функцию.
схема цифровой подписи Клауса Шнорра(Schnorr)
Стойкость схемы Шнорра основывается на трудной задаче вычисления дискретных логарифмов. Для генерации пары ключей сначала выбираются два простых числа p и q так, чтобы q было сомножителем p-1. Затем выбирается a, не равное 1, такое что aq = 1 ( mod p). Все эти числа могут быть свободно опубликованы и использоваться группой пользователей. Для генерации конкретной пары ключей выбирается случайное число, меньшее q. Оно служит закрытым ключом, s. Затем вычисляется открытый ключ v = a-s (mod p). Для подписи сообщений используется хэш-функция H(M).
Предварительные вычисления. Пользователь A выбирает случайное число r, меньшее q, и вычисляет x = ar (mod p).
Подпись сообщения M. Для того, чтобы подписать сообщение M пользователю A необходимо выполнить следующие действия:
1. Объединить M и x и хэшировать результат: e = H(M,x).
2. Вычислить y = (r + se) (mod q). Подписью являются значения e и y, их нужно выслать получателю B.
Проверка подписи для сообщения M. Получатель B вычисляет x' = ay ve (mod p). Затем он проверяет, что хэш-значение для объединения M и x' равно e. e = H(M,x') Если это так, то он считает подпись верной. В своей работе Шнорр приводит следующие свойства своего алгоритма:
1. Большая часть вычислений, нужных для генерации подписи и независящих от подписываемого сообщения, может быть выполнена на стадии предварительных вычислений. Следовательно, эти вычисления могут быть выполнены во время простоя и не влияют на скорость вычисления подписи. 2. При одинаковом уровне безопасности длина подписей для Schnorr короче, чем для RSA. Например, при 140-битовом q длина подписей равна всего лишь 212 битам, меньше половины длины подписей RSA. Подписи Schnorr также намного короче подписей ElGamal.
схема цифровой подписи ElGamal
Для генерации ключевой пары выбираются большое простое число р и примитивный элемент g мультипликативной группы поля GF(p). Выбирается случайное число х такое, что x<p-1. Открытым ключом является y = gx ( mod p), секретным ключем является x.
Подпись сообщения M. Для того, чтобы подписать сообщение M пользователю A необходимо выполнить следующие действия:
1. Выбрать случайно и равновероятно число k из группы обратимых элементов кольца Z p-1 *. То есть НОД(k,p-1) = 1.
2. Вычислить a = gk (mod q).
3. Вычислить b = (M-xa)k-1 (mod p-1).
4. Подписью для сообщения M является пара (a,b).
Проверка подписи для сообщения M. Для проверки подписи (a,b) для сообщения M получатель B проверяет выполнение равенства gM = ya ab (mod p). Надо заметить, что для ускорения процесса подписи вычисления на шагах 1 и 2 можно проводить заранее, вычислять значения k-1 тоже. Как и в других похожих схемах подписи значение k должно оставаться в секрете и выбираться cлучайно.
электронная цифровая подпись СТБ 1176.2-99
Введенный в 1999г. стандарт Республики Беларусь СТБ 1176.2 "Информационная технология. Защита информации. Процедуры выработки и проверки электронной цифровой подписи " базируется на схеме ЭЦП Шнорра.
Параметры. При выработке и проверке подписи используются l-битовое простое число p и r-битовое простое число q, q | (p-1). Допустимые значения указаны в таблице 1. Применяется определяемая СТБ 1176.1 функция хеширования h, параметр L которой устанавливается равным (r-1).
Таблица 1. Допустимые значения параметров r и l.
| Уровень стойкости | r | l |
| 1 | 143 | 638 |
| 2 | 154 | 766 |
| 3 | 175 | 1022 |
| 4 | 182 | 1118 |
| 5 | 195 | 1310 |
| 6 | 208 | 1534 |
| 7 | 222 | 1790 |
| 8 | 235 | 2046 |
| 9 | 249 | 2334 |
| 10 | 257 | 2462 |
Часть преобразований стандарта выполняется в группе G, определяемой множеством Bp = {1,2, ...,p-1 } и операцией *
u * v = uvR-1 ( mod p),
где R = 2l+2. Использование операции * вместо обычного умножения по модулю p упрощает применение алгоритма Монтгомери. Далее, u(m) - m-я степень числа u из Bp как элемента G. В стандарте приведены алгоритмы генерации чисел p,q и элемента a из Bp, имеющего порядок q в группе G. Числа p, q, a являются долговременными параметрами СТБ 1176.2-99, едиными для группы пользователей.
Входные данные. Всякое сообщение M, подпись к которому вырабатывается или проверяется, задается последовательностью байтов. Если t- n-разрядное число по основанию 28 = 256, то есть
t = t0 (256)0+..+tn-1 (256)n-1
причем 0 <= ti <256, tn-1 не равно 0, то t||M --- сообщение, полученное вставкой байтов t0, t1,..,tn-1 в начало M.
Выработка подписи. При выработке подписи S к сообщению M используется личный ключ x, 0<x<q. Выполняются следующие шаги.
1. Выработать случайное секретное число k, 1<k<q.
2. t = a(k).
3. U = h(t||M). Если U=0, то вернуться к шагу 1.
4. V = (k-xU). Если V=0, то вернуться к шагу 1.
5. S = U2r+V.
Проверка подписи. При проверке подписи S к сообщению M используется открытый ключ y = a(X). Алгоритм проверки подписи состоит из следующих шагов.
1. V = S ( mod 2r).
2. U = (S-V)/2r.
3. Проверить условия 0<U<2r-1, 0<V<q. Если хотя бы одно из условий
нарушается, то подпись признается недействительной и выполнение
алгоритма завершается.
4. t = a(V) * y(U).
5. W = h(t||M).
6. Если W неравно U, то подпись признается недействительной. Если W=U, то принимаются решения о том, что:
а) подпись S была создана с помощью личного ключа x, связанного с открытым ключем y;
б)подпись S и сообщение M не были изменены с момента их создания.
схема Диффи-Лампорта
Для аутентификации пользователя можно применять произвольную симметрическую схему. Пусть отправитель сообщения A хочет подписать n-битовое бинарное сообщение m=m1.. mn из V2n.
Он выбирает 2n ключей некоторой криптосистемы, которые хранятся в секрете. Обозначим их так: a1,..,an;b1,..,bn.
Если E - алгоритм шифрования, то A генерирует 4n параметров проверки { (Xi,Yi,Ui,Vi): 1<= i <= n}, где Xi и Yi - величины, подаваемые на вход E и связанные соотношениями
Ui = E(Xi,ai)
Vi = E(Yi,bi)
1 <= i < n
Параметры проверки заранее посылаются получателю B и третьему доверенному лицу.
Чтобы подписать n-битовое сообщение m=(m1,..,mn), пользователь A применяет следующую процедуру: его подпись будет цепочкой S = S1 ..Sn, где для каждого i
Si = ai, если mi =0
Si = bi, если mi =1
Пользователь B проверяет подпись следующим образом: для каждого i (0 <= i <= n) он использует бит mi и ключ Si, чтобы проверить:
если mi = 0, то E(Xi,Si) = Ui
если mi = 1, то E(Yi,Si) = Vi
Пользователь B принимает подписанное сообщение за истинное только в том случае, если при процедуре проверки эти равенства выполнены для каждого L.
Эта система проста в использовании, но у нее есть, по крайней мере, два очевидных недостатка. Во-первых, необходима предварительная передача параметров проверки. Во-вторых, что более важно, подпись сильно увеличивает длину сообщения. Если в криптосистеме используются ключи длиной, скажем, 64 бита, то длина подписанного сообщения увеличится в 64 раза.
вероятностная схема подписи Рабина
В 1978 г. Рабин предложил следующий способ подписи. Пусть E - функция шифрования некоторой криптосистемы, (ki, 1 <= i <= 2r) -
последовательность случайно выбранных ключей, которые отправитель A держит в секрете. Пользователь B получает список параметров проверки (Xi,Ui) (1 <= i <= 2r), где
E(Xi,ki) = Ui (1 <= i <= 2r)
Эти параметры хранятся в доступном для всех месте.
Предположим, что A хочет подписать сообщение m. Его подписью будет цепочка S = S1S2..S2r, для каждого i (1<=i<=2r) Si =E(m,ki). B делает следующее. Сначала он выбирает случайным образом r ключей, которые A должен ему предъявить: ki1 , ki2 ,..,kir. При получении этих ключей от A он проверяет:
E(m,ki1) = Si1
E(Xi1,ki1) = Ui1
и далее для всех индексов i2, i3 ,.., ir . Он считает действительной подпись от A только в том случае, когда выдерживаются все проверки. Безопасность получателя зависит от его уверенности в том, что только отправитель, знающий секретный ключ, может послать так подписанное сообщение. Что касается A, то предположим, что он отказывается от сообщения, которое по утверждению B он подписал. Тогда протокол для A следующий: он должен предъявить судье свои секретные ключи k1,k2,..,k2r, и в присутствии обеих сторон делается 2r проверок:
E(m,ki)=Si, E(Xi,ki)=Ui
Рассмотрим, что это означает в трех возможных случаях.
1. Корректными являются менее r проверок. Тогда B не должен был принимать подписанное сообщение.
2. Выдерживается точно r проверок, то есть при формировании ключей B выбрал именно это подмножество из r ключей. Вероятность, что он угадает это подмножество, равна pr = (C2r r)-1, для r=18, pr примерно равно 10-10.
3. Выдерживается r+1 и более проверок: отказ абонента A не принимается.
заключение
Криптография уверенно входит в повседневную жизнь, каждый пользователь компьютера неявно пользуется различными крипографическими алгоритмами. Это и установка защищенного соединения по протоколам SSL/TLS, и автоматическая проверка цифровой подписи программ или драйверов, и постянный рост использования электронных документов для проведения финансовых операций. Аппарат ЭЦП, возникший как развитие идей криптографии с открытым ключем, начинает играть всю большую роль в системе электронных коммуникаций.
Большое значение аппарата электронных цифровых подписей в современном мире отражается принятием национальных (ГОСТ, СТБ, ECDSA, ESIGN) и коммерческих (RSA) стандартов цифровой подписи. Рассмотренные выше стандарты определяют технические аспекты применения цифровых подписей. Однако возникают вопросы юридического характера:
- Как придать документам, существующим только в электронном виде, тот же правовой статус, котрый имеется у бумажных документов?
- Как обеспечить защищенный, надежный и юридически законный метод подписи электронных документов, который исключит необходимость создавать и подписывать бумажные документы, тем самым поощряя и облегчая электронную коммерцию?
Эти два вопроса носят скорее юридический характер, поэтому в настоящее время в большинстве развитых стран приняты нормативные акты, регулирующие взаимоотношения субъектов, использующих ЭЦП. Но ЭЦП - это не только инструмент для ведения электонного документооборота, но и новый интересный криптографический примитив, поэтому много математиков занимаются исследованиями в области схем цифровой подписи/идентификации.
По материалам реферата слушателя 4 курса ИКСИ, научный руководитель – Сергей Кунегин
Сетевые решения. Статья была опубликована в номере 12 за 2005 год в рубрике технологии
