Цифровая подпись
Вернуться на главную страницу astralotchet.ru
Актуальность статьи 10 марта 2004 года.
Аннотация: Рассматриваются основные требования к цифровым подписям, прямая и арбитражная цифровая подпись, стандарты цифровой подписи ГОСТ 34.10 и DSS.
Требования к цифровой подписи
Аутентификация защищает двух участников, которые обмениваются сообщениями, от воздействия некоторой третьей стороны. Однако простая аутентификация не защищает участников друг от друга, тогда как и между ними тоже могут возникать определенные формы споров.
Например, предположим, что Джон посылает Мери аутентифицированное сообщение, и аутентификация осуществляется на основе общего секрета. Рассмотрим возможные недоразумения, которые могут при этом возникнуть:
- Мери может подделать сообщение и утверждать, что оно пришло от Джона. Мери достаточно просто создать сообщение и присоединить аутентификационный код, используя ключ, который разделяют Джон и Мери.
- Джон может отрицать, что он посылал сообщение Мери. Так как Мери может подделать сообщение, у нее нет способа доказать, что Джон действительно посылал его.
В ситуации, когда обе стороны не доверяют друг другу, необходимо нечто большее, чем аутентификация на основе общего секрета. Возможным решением подобной проблемы является использование цифровой подписи. Цифровая подпись должна обладать следующими свойствами:
- Должна быть возможность проверить автора, дату и время создания подписи.
- Должна быть возможность аутентифицировать содержимое во время создания подписи.
- Подпись должна быть проверяема третьей стороной для разрешения споров.
Таким образом, функция цифровой подписи включает функцию аутентификации.
На основании этих свойств можно сформулировать следующие требования к цифровой подписи:
- Подпись должна быть битовым образцом, который зависит от подписываемого сообщения.
- Подпись должна использовать некоторую уникальную информацию отправителя для предотвращения подделки или отказа.
- Создавать цифровую подпись должно быть относительно легко.
- Должно быть вычислительно невозможно подделать цифровую подпись как созданием нового сообщения для существующей цифровой подписи, так и созданием ложной цифровой подписи для некоторого сообщения.
- Цифровая подпись должна быть достаточно компактной и не занимать много памяти.
Сильная хэш-функция, зашифрованная закрытым ключом отправителя, удовлетворяет перечисленным требованиям.
Существует несколько подходов к использованию функции цифровой подписи. Все они могут быть разделены на две категории: прямые и арбитражные.
Прямая и арбитражная цифровые подписи
При использовании прямой цифровой подписи взаимодействуют только сами участники, т.е. отправитель и получатель. Предполагается, что получатель знает открытый ключ отправителя. Цифровая подпись может быть создана шифрованием всего сообщения или его хэш-кодазакрытым ключом отправителя.
Конфиденциальность может быть обеспечена дальнейшим шифрованием всего сообщения вместе с подписью открытым ключом получателя (асимметричное шифрование) или разделяемым секретным ключом (симметричное шифрование). Заметим, что обычно функция подписи выполняется первой, и только после этого выполняется функция конфиденциальности. В случае возникновения спора некая третья сторона должна просмотреть сообщение и его подпись. Если функция подписи выполняется над зашифрованным сообщением, то для разрешения споров придется хранить сообщение как в незашифрованном виде (для практического использования), так и в зашифрованном (для проверки подписи). Либо в этом случае необходимо хранить ключ симметричного шифрования, для того чтобы можно было проверить подпись исходного сообщения. Если цифровая подпись выполняется над незашифрованным сообщением, получатель может хранить только сообщение в незашифрованном виде и соответствующую подпись к нему.
Все прямые схемы, рассматриваемые далее, имеют общее слабое место. Действенность схемы зависит от безопасности закрытого ключа отправителя. Если отправитель впоследствии не захочет признать факт отправки сообщения, он может утверждать, что закрытый ключ был потерян или украден, и в результате кто-то подделал его подпись. Можно применить административное управление, обеспечивающее безопасность закрытых ключей, для того чтобы, по крайней мере, хоть в какой-то степени ослабить эти угрозы. Один из возможных способов состоит в требовании в каждую подпись сообщения включать отметку времени (дату и время) и сообщать о скомпрометированных ключах в специальный центр.
Другая угроза состоит в том, что закрытый ключ может быть действительно украден у Х в момент времени Т. Нарушитель может затем послать сообщение, подписанное подписью Х и помеченное временной меткой, которая меньше или равна Т.
Проблемы, связанные с прямой цифровой подписью, могут быть частично решены с помощью арбитра. Существуют различные схемы с применением арбитражной подписи. В общем виде арбитражная подпись выполняется следующим образом. Каждое подписанное сообщение от отправителя Х к получателю Y первым делом поступает к арбитру А, который проверяет подпись для данного сообщения. После этого сообщение датируется и посылается к Y с указанием того, что оно было проверено арбитром. Присутствие А решает проблему схем прямой цифровой подписи, при которых Х может отказаться от сообщения.
Арбитр играет важную роль в подобного рода схемах, и все участники должны ему доверять.
Рассмотрим некоторые возможные технологии арбитражной цифровой подписи.
Симметричное шифрование, арбитр видит сообщение:
Х -> A: M || EKxa [ IDX || H (M)]
Предполагается, что отправитель Х и арбитр А разделяют секретный ключ KХА и что А и Y разделяют секретный ключ KАY. Х создает сообщение М и вычисляет его хэш-значение Н (М). Затем Х передает сообщение и подпись А. Подпись состоит из идентификатора Х и хэш-значения, все зашифровано с использованием ключа KХА. А дешифрует подпись и проверяет хэш-значение.
A -> Y: ЕКay [ IDX || M ||
EKxa [IDX || H (M)], T ]
Затем А передает сообщение к Y, шифруя его KAY. Сообщение включает IDX, первоначальное сообщение от Х, подпись и отметку времени. Y может дешифровать его для получения сообщения и подписи. Отметка времени информирует Y о том, что данное сообщение не устарело и не является повтором. Y может сохранить М и подпись к нему. В случае спора Y, который утверждает, что получил сообщение М от Х, посылает следующее сообщение к А:
ЕКay [ IDX || M || EKxa [IDX || H (M)] ]
Арбитр использует KAY для получения IDХ, М и подписи, а затем, используя KХА, может дешифровать подпись и проверить хэш-код. Поэтой схеме Y не может прямо проверить подпись Х ; подпись используется исключительно для разрешения споров. Y считает сообщение от Х аутентифицированным, потому что оно прошло через А. В данном сценарии обе стороны должны иметь высокую степень доверия к А:
- Х должен доверять А в том, что тот не будет раскрывать KХА и создавать фальшивые подписи в форме ЕKка [IDX || H (M)].
- Y должен доверять А в том, что он будет посылать ЕKay [ IDX || M || EKxa [IDX || H (M)] ] только в том случае, если хэш-значение является корректным и подпись была создана Х.
- Обе стороны должны доверять А в решении спорных вопросов.
Симметричное шифрование, арбитр не видит сообщение:
Если арбитр не является такой доверенной стороной, то Х должен добиться того, чтобы никто не мог подделать его подпись, а Y должен добиться того, чтобы Х не мог отвергнуть свою подпись.
Предыдущий сценарий также предполагает, что А имеет возможность читать сообщения от Х к Y и что возможно любое подсматривание. Рассмотрим сценарий, который, как и прежде, использует арбитраж, но при этом еще обеспечивает конфиденциальность. В таком случае также предполагается, что Х и Y разделяют секретный ключ KXY.
X -> A: IDX || EKхy [M] ||
EKxa [IDX || H (EKXY [M]) ]
Х передает А свой идентификатор, сообщение, зашифрованное KXY, и подпись. Подпись состоит из идентификатора и хэш-значения зашифрованного сообщения, которые зашифрованы с использованием ключа KХА. А дешифрует подпись и проверяет хэш-значение. В данном случае А работает только с зашифрованной версией сообщения, что предотвращает его чтение.
A -> Y: EKay [ IDX || EKXY[M] ||
EKxa [ IDX || H ( EKXY [M])], T]
А передает Y все, что он получил от Х плюс отметку времени, все шифруя с использованием ключа KAY.
Хотя арбитр и не может прочитать сообщение, он в состоянии предотвратить подделку любого из участников, Х или Y. Остается проблема, как и в первом сценарии, что арбитр может сговориться с отправителем, отрицающим подписанное сообщение, или с получателем, для подделки подписи отправителя.
Шифрование открытым ключом, арбитр не видит сообщение:
Все обсуждаемые проблемы могут быть решены с помощью схемы открытого ключа.
X -> A: IDX || EKRх [ IDX || EKUy [EKRx [M] ] ]
В этом случае Х осуществляет двойное шифрование сообщения М, сначала своим закрытым ключом KRX, а затем открытым ключом Y KUY. Получается подписанная секретная версия сообщения. Теперь это подписанное сообщение вместе с идентификатором Х шифруется KRX и вместе с IDX посылается А. Внутреннее, дважды зашифрованное, сообщение недоступно арбитру (и всем, исключая Y ). Однако Аможет дешифровать внешнюю шифрацию, чтобы убедиться, что сообщение пришло от Х (так как только Х имеет KRX ). Проверка дает гарантию, что пара закрытый/открытый ключ законна, и тем самым верифицирует сообщение.
A -> Y: EKRa [ IDX || EKUy [EKRx [M] ] || T ]
Затем А передает сообщение Y, шифруя его KRA. Сообщение включает IDX, дважды зашифрованное сообщение и отметку времени.
Эта схема имеет ряд преимуществ по сравнению с предыдущими двумя схемами. Во-первых, никакая информация не разделяется участниками до начала соединения, предотвращая договор об обмане. Во-вторых, некорректные данные не могут быть посланы, даже если KRXскомпрометирован, при условии, что не скомпрометирован KRА. В заключение, содержимое сообщения от Х к Y неизвестно ни А, ни кому бы то ни было еще.
Стандарт цифровой подписи DSS
Национальный институт стандартов и технологии США (NIST) разработал федеральный стандарт цифровой подписи DSS. Для создания цифровой подписи используется алгоритм DSA (Digital Signature Algorithm). В качестве хэш-алгоритма стандарт предусматривает использование алгоритма SHA-1 (Secure Hash Algorithm). DSS первоначально был предложен в 1991 году и пересмотрен в 1993 году в ответ на публикации, касающиеся безопасности его схемы.
Подход DSS
DSS использует алгоритм, который разрабатывался для использования только в качестве цифровой подписи. В отличие от RSA, его нельзя использовать для шифрования или обмена ключами. Тем не менее, это технология открытого ключа.
Рассмотрим отличия подхода, используемого в DSS для создания цифровых подписей, от применения таких алгоритмов как RSA.
Создание и проверка подписи с помощью алгоритма RSA
Рис. 10.1. Создание и проверка подписи с помощью алгоритма RSA
Создание и проверка подписи с помощью стандарта DSS
Рис. 10.2. Создание и проверка подписи с помощью стандарта DSS
В подходе RSA подписываемое сообщение подается на вход сильной хэш-функции, которая создает хэш-код фиксированной длины. Для создания подписи этот хэш-код шифруется с использованием закрытого ключа отправителя. Затем сообщение и подпись пересылаются получателю. Получатель вычисляет хэш-код сообщения и проверяет подпись, используя открытый ключ отправителя. Если вычисленный хэш-код равен дешифрованной подписи, то считается, что подпись корректна.
Подход DSS также использует сильную хэш-функцию. Хэш-код является входом функции подписи вместе со случайным числом k, созданным для этой конкретной подписи. Функция подписи также зависит от закрытого ключа отправителя KRa и множества параметров, известных всем участникам. Можно считать, что это множество состоит из глобального открытого ключа KUG. Результатом является подпись, состоящая из двух компонент, обозначенных как s и r.
Для проверки подписи получатель также создает хэш-код полученного сообщения. Этот хэш-код вместе с подписью является входом в функцию верификации. Функция верификации зависит от глобального открытого ключа KUG и от открытого ключа отправителя KUa. Выходом функции верификации является значение, которое должно равняться компоненте r подписи, если подпись корректна. Функция подписи такова, что только отправитель, знающий закрытый ключ, может создать корректную подпись.
Теперь рассмотрим детали алгоритма, используемого в DSS.
Алгоритм цифровой подписи
DSS основан на трудности вычисления дискретных логарифмов и базируется на схеме, первоначально представленной ElGamal и Schnorr.
Общие компоненты группы пользователей
Существует три параметра, которые являются открытыми и могут быть общими для большой группы пользователей.
160-битное простое число q, т.е. 2159 < q < 2160.
Простое число р длиной между 512 и 1024 битами должно быть таким, чтобы q было делителем (р - 1), т.е. 2L-1 < p < 2L, где 512 < L < 1024 и (p-1)/q является целым.
g = h(p-1)/q mod p, где h является целым между 1 и (р-1) и g должно быть больше, чем 1,10.
Зная эти числа, каждый пользователь выбирает закрытый ключ и создает открытый ключ.
Закрытый ключ отправителя
Закрытый ключ х должен быть числом между 1 и (q-1) и должен быть выбран случайно или псевдослучайно.
x - случайное или псевдослучайное целое,
0 < x < q ,
Открытый ключ отправителя
Открытый ключ вычисляется из закрытого ключа как у = gx mod p. Вычислить у по известному х довольно просто. Однако, имея открытый ключ у, вычислительно невозможно определить х, который является дискретным логарифмом у по основанию g.
y = gx mod p
Случайное число, уникальное для каждой подписи.
k - случайное или псевдослучайное целое, 0 < k < q, уникальное для каждого подписывания.
Подписывание
Для создания подписи отправитель вычисляет две величины, r и s, которые являются функцией от компонент открытого ключа (p, q, g), закрытого ключа пользователя (х), хэш-кода сообщения Н (М) и целого k, которое должно быть создано случайно или псевдослучайно и должно быть уникальным при каждом подписывании.
r = (gk mod p) mod q
s = [ k-1 (H (M) + xr) ] mod q
Подпись = (r, s)
Проверка подписи
Получатель выполняет проверку подписи с использованием следующих формул. Он создает величину v, которая является функцией от компонент общего открытого ключа, открытого ключа отправителя и хэш-кода полученного сообщения. Если эта величина равна компоненте r в подписи, то подпись считается действительной.
w = s-1 mod q
u1 = [ H (M) w ] mod q
u2 = r w mod q
v = [ (gu1 yu2) mod p ] mod q
подпись корректна, если v = r
Докажем, что v = r в случае корректной подписи.
Лемма 1. Для любого целого t, если
g = h(p-1)/q mod p
то gt mod p = gt mod q mod p
По теореме Ферма, так как h является взаимнопростым с p, то hp-1 mod p = 1. Следовательно, для любого неотрицательного целого n
gnq mod p = (h(p-1)/q mod p)nq mod p
= h((p-1)/q) nq mod p
= h(p-1)n mod p
= ((h(p-1) mod p)n) mod p
= 1n mod p = 1
Таким образом, для неотрицательных целых n и z мы имеем
gnq+z mod p = (gnq gz) mod p
= ((gnq mod p) (gz mod p )) mod p
= gz mod p
Любое неотрицательное целое t может быть представлено единственным образом как t = nq + z, где n и z являются неотрицательными целыми и 0 < z < q. Таким образом z = t mod q.
Лемма 2. Для неотрицательных чисел a и b: g(a mod q + b mod q) mod p = g(a+b) mod q mod p.
По лемме 1 мы имеем
g(a mod q + b mod q) mod p
= g(a mod q + b mod q) mod q mod p
= g(a + b) mod q mod p
Лемма 3. y(rw) mod q mod p = g(xrw) mod q mod p
По определению y = gx mod p. Тогда:
y(rw) mod q mod p
= (gx mod p)(rw) mod q mod p по правилам
= gx ((rw) mod q) mod p модульной арифметики
= g(x ((rw mod q))) mod q mod p по лемме 1
= g(xrw) mod q mod p
Лемма 4. ((H(M) + xr) w) mod q = k
По определению s = (k-1 (H(M) + xr)) mod q. Кроме того, так как q является простым, любое неотрицательное целое меньшее q имеет мультипликативную инверсию. Т.е. (k k-1) mod q = 1. Тогда:
(ks) mod q = (k((k-1(H(M) + xr)) mod q)) mod q
= (k (k-1(H(M) + xr))) mod q
= ((kk-1) mod q) ((H(M) + xr) mod q) mod q
= (H(M) + xr) mod q
По определению w = s-1 mod q, следовательно, (ws) mod q = 1. Следовательно:
((H(M) + xr) w) mod q
= (((H(M) + xr) mod q) (w mod q)) mod q
= (((ks) mod q) (w mod q)) mod q
= (kws) mod q
= (k mod q) ((ws) mod q)) mod q
= k mod q
Так как 0 < k < q, то k mod q = k.
Теорема. Используя определения для v и r, докажем, что v=r.
v = ((gu1 yu2) mod p) mod q
= ((g(H(M) w) mod q y(rw) mod q) mod p) mod q
= ((g(H(M) w) mod q g(xrw) mod q) mod p) mod q
= ((g(H(M) w) mod q + (xrw) mod q) mod p) mod q
= ((g(H(M) w + xrw) mod q) mod p) mod q
= ((gw (H(M) + xr) mod q) mod p) mod q
= (gk mod p) mod q
= r
Отечественный стандарт цифровой подписи ГОСТ 34.10
В отечественном стандарте ГОСТ 34.10, принятом в 1994 году (сейчас используется ГОСТ 34.10 принятый в 2001 году), используется алгоритм, аналогичный алгоритму, реализованному в стандарте DSS. Оба алгоритма относятся к семейству алгоритмов ElGamal.
В стандарте ГОСТ 34.10 используется хэш-функция ГОСТ 3411, которая создает хэш-код длиной 256 бит. Это во многом обуславливает требования к выбираемым простым числам p и q:
- р должно быть простым числом в диапазоне
2509 < p < 2512 либо 21020 < p < 21024
- q должно быть простым числом в диапазоне
2254 < q < 2256
q также должно быть делителем (р-1).
Аналогично выбирается и параметр g. При этом требуется, чтобы gq (mod p) = 1.
В соответствии с теоремой Ферма это эквивалентно условию в DSS, что g = h(p-1)/q mod p.
Закрытым ключом является произвольное число х
0 < x < q
Открытым ключом является число y
y = gx mod p
Для создания подписи выбирается случайное число k
0 < k < q
Подпись состоит из двух чисел (r, s), вычисляемых по следующим формулам:
r = (gk mod p) mod q s = (k H(M) + xr) mod q
Еще раз обратим внимание на отличия DSS и ГОСТ 34.10.
- Используются разные хэш-функции: в ГОСТ 34.10 применяется отечественный стандарт на хэш-функции ГОСТ 34.11, в DSS используется SHA-1, которые имеют разную длину хэш-кода. Отсюда и разные требования на длину простого числа q: в ГОСТ 34.10 длина q должна быть от 254 бит до 256 бит, а в DSS длина q должна быть от 159 бит до 160 бит.
- По-разному вычисляется компонента s подписи. В ГОСТ 34.10 компонента s вычисляется по формуле
s = (k H(M) + xr) mod q
В DSS компонента s вычисляется по формуле
s = [k-1 (H(M) + xr)] mod q
Последнее отличие приводит к соответствующим отличиям в формулах для проверки подписи.
Получатель вычисляет
w = H(M)-1 mod q u1 = w s mod q u2 = (q-r) w mod q v = [(gu1 yu2) mod p] mod q Подпись корректна, если v = r.
Структура обоих алгоритмов довольно интересна. Заметим, что значение r совсем не зависит от сообщения. Вместо этого r есть функция от k и трех общих компонент открытого ключа. Мультипликативная инверсия k ( mod p ) (в случае DSS ) или само значение k (в случае ГОСТ 34.10) подается в функцию, которая, кроме того, в качестве входа имеет хэш-код сообщения и закрытый ключ пользователя. Эта функциятакова, что получатель может вычислить r, используя входное сообщение, подпись, открытый ключ пользователя и общий открытый ключ.
В силу сложности вычисления дискретных логарифмов нарушитель не может восстановить k из r или х из s.
Другое важное замечание заключается в том, что экспоненциальные вычисления при создании подписи необходимы только для gk mod p. Так как это значение от подписываемого сообщения не зависит, оно может быть вычислено заранее. Пользователь может заранее просчитать некоторое количество значений r и использовать их по мере необходимости для подписи документов. Еще одна задача состоит в определении мультипликативной инверсии k-1 (в случае DSS ). Эти значения также могут быть вычислены заранее.
Подписи, созданные с использованием стандартов ГОСТ 34.10 или DSS, называются рандомизированными, так как для одного и того же сообщения с использованием одного и того же закрытого ключа каждый раз будут создаваться разные подписи (r,s), поскольку каждый раз будет использоваться новое значение k . Подписи, созданные с применением алгоритма RSA, называются детерминированными, так как для одного и того же сообщения с использованием одного и того же закрытого ключа каждый раз будет создаваться одна и та же подпись.
Вернуться на главную страницу astralotchet.ru