Мы все знакомы с понятием подписи. Человек подписывает документ, чтобы показать, что нечто сделано им самим или было им одобрено. Подпись - доказательство получателю, что документ исходит от истинного объекта. Когда клиент подписывает чек, банк должен убедиться, что чек принадлежит клиенту и никому другому. Другими словами, подпись на документе является признаком установления подлинности автора - подлинности документа. Рассмотрим картину, подписанную художником. Подпись на предмете искусства, если она подлинная, означает, что этот предмет, вероятно, подлинный.
Когда Алиса передает сообщение Бобу, Боб должен проверить подлинность передатчика; он должен убедиться, что сообщение исходит от Алисы, а не от Евы. Боб может попросить, чтобы Алиса подписала сообщение с помощью электроники. Другими словами,
В этой лекции мы сначала рассмотрим некоторые проблемы, связанные с цифровыми подписями, а затем перейдем к рассмотрению различных
Рассмотрение начнем с отличия между обычными подписями и цифровыми подписями.
Обычная подпись включена в документ; это - часть документа. Когда мы пишем чек, подпись находится на чеке; это - не отдельный документ. Но когда мы подписываем документ в цифровой форме, мы передаем подпись как отдельный документ. Передатчик передает два документа: сообщение и подпись. Получатель получает оба документа и проверяет, что подпись принадлежит предполагаемому передатчику. Если это доказано, сообщение сохраняется; иначе оно отклоняется.
Второе отличие между двумя типами подписей - метод подтверждения подписи. В случае обычной подписи, когда получатель получает документ, он сравнивает подпись на документе с подписью в архиве. Если они одинаковые, документ подлинный. Получатель должен иметь в архиве копию для сравнения этой подписи. При цифровой подписи - получатель получает сообщение и подпись, но копия подписи не хранится нигде. Получатель должен применить методику проверки комбинации сообщения и подписи, чтобы проверить подлинность.
В случае обычной подписи есть отношения "один ко многим" между подписью и документами. Человек использует ту же самую подпись, чтобы подписать много документов. Для цифровой подписи есть непосредственные отношения между подписью и сообщением. Каждое сообщение имеет свою собственную подпись. Подпись одного сообщения не может использоваться в другом сообщении. Если Боб получает два сообщения, один за другим, от Алисы, он не может использовать подпись первого сообщения, чтобы проверить второе. Каждое сообщение нуждается в новой подписи.
Другая разность между двумя типами подписей - качество, названное резервное копирование. При обычной подписи ее копия на поступившем документе может отличаться от копии, сохраненной в архиве. В цифровой подписи нет такого различия, если нет указателя времени (такого как метка времени) на документе. Например, предположите, что Алиса передает документ, инструктирующий Боба заплатить Еве. Если Ева перехватывает документ и сохраняет подпись, она может воспользоваться этим позже (скопировать подпись), чтобы снова получить деньги от Боба.
Рис. 3.1 показывает процесс цифровой подписи. Передатчик использует
(рис 3.1) Процесс передачи цифровой подписиПотребность в ключах
Обычная подпись походит на частный "ключ", принадлежащий лицу, которое подписывает документ. Подписывающее лицо использует его, чтобы подписать документы; никто другой не имеет эту подпись. Копия подписи находится в архиве подобно открытому ключу; любой может использовать его, чтобы проверить документ, сравнить подпись с первоначальной подписью.
В цифровой подписи подписывающее лицо использует свой секретный ключ - прикладной
Мы можем добавить секретный и открытый ключи к рис. 3.1, чтобы дать законченное понятие цифровой подписи (см. рис. 3.2). Обратите внимание, что когда документ подписан, любой, включая Боба, может проверить это, потому что каждый имеет доступ к открытому ключу Алисы. Алиса не должна использовать свой открытый ключ для того, чтобы подписывать документ, потому что тогда любой сможет подделать ее подпись.
(рис 3.2) Дополнение передачи цифровой подписи ключом Алисы Можем ли мы использовать секретный (симметричный) ключ, чтобы и подписать и проверить подпись? Ответ отрицателен по нескольким причинам.
Первая: ключ засекречивания известен только двум объектам (например, Алисе и Бобу). Так, если Алиса должна подписать другой документ и передать его Тэду, она должна использовать другой ключ засекречивания.
Вторая: как мы увидим, создавая ключ засекречивания для сеанса, в него включают признаки установления подлинности, которые используют цифровую подпись. Мы получим порочный круг.
Третье: Боб может использовать ключ засекречивания, который он использует между собой и Алисой, подписать документ, передать его Тэду и имитировать, что он прибыл от Алисы.
Мы должны понимать различие между секретным и открытым ключами, используемыми в цифровых подписях, и секретным и открытым ключами, которые применяются в
В лекции 10 мы узнали, что криптосистемы с асимметричными ключами очень неэффективны, когда имеют дело с длинными сообщениями. В системе цифровой подписи сообщения обычно длинные, но мы должны использовать асимметрично-ключевые схемы. Решение состоит в том, что подпись
(рис 3.3) Подписание дайджеста Дайджест получается из сообщения на стороне Алисы и проходит процесс подписания, используя секретный ключ Алисы. Алиса затем передает сообщение и подпись Бобу. Как мы увидим позже в этой лекции, есть варианты в процессе подписания, которые зависят от системы. Например, могут быть проведены дополнительные вычисления, прежде чем получается дайджест, или может быть использована другая система засекречивания. В некоторых системах подпись имеет множество значений.
На стороне Боба используется та же самая общедоступная хэш-функция, и сначала из полученного сообщения создается дайджест. Далее вычисляются подпись и дайджест. Процесс подтверждения также проверяет прикладные критерии по результатам вычисления, чтобы определить подлинность подписи. Если подпись подлинна, то сообщение принимается; в противном случае она отклоняется.
Мы обсуждали несколько услуг безопасности в лекции 1, включая конфиденциальность сообщения, установление подлинности сообщения, целостность сообщения и исключение отказа от сообщения.
Безопасность
Целостность сообщения сохраняется, даже если мы подписываем все сообщение, потому что мы не можем получить ту же самую подпись, если сообщение изменено.
Если Алиса подписывает сообщение и затем отрицает это, может ли Боб доказать, что Алиса фактически подписала его? Например, Алиса передает сообщение банку (Боб) и просит перечислить 10000 $ с ее счета на счет Тэда.
Может ли Алиса потом отрицать, что она передала это сообщение? Согласно схеме, которую мы рассматривали до сих пор, Боб мог бы иметь проблему. Боб должен был сохранить подпись в архиве и далее использовать открытый ключ Алисы, чтобы создать первоначальное сообщение, и доказать, что сообщение в архиве и недавно полученное сообщение является одним и тем же. Это невыполнимо, потому что Алиса может изменить за это время свой секретный или открытый ключ. Она может также утверждать, что сообщение в архиве, содержащее подпись, не подлинное.
Одно из решений - третье лицо (доверенное лицо). Люди могут по договоренности иметь сторону, которой они доверяют. В будущих лекциях мы увидим, что сторона, которой доверяют, может решить много других проблем относительно служб безопасности и замены ключей. рис. 3.4 показывает, как сторона, которой доверяют, может препятствовать отрицанию Алисой передачи данного сообщения.
Алиса создает подпись из своего сообщения ( SA ) и передает центру сообщение, которое содержит ее опознавательные признаки, опознавательные признаки Боба, а также подпись. Центр, после проверки правильности открытого ключа Алисы, проверяет с помощью этого ключа Алисы, что сообщение прибыло от Алисы. Затем Центр сохраняет копию сообщения с опознавательными признаками передатчика, опознавательными признаками получателя, а также с меткой времени, в своем архиве. Центр использует свой секретный ключ, чтобы создать из сообщения другую подпись ( ST ). Затем центр передает сообщение, новую подпись, опознавательные признаки Алисы и опознавательные признаки Боба - Бобу. Боб проверяет сообщение, используя общедоступный ключ центра, которому он доверяет.
(рис 3.4) Использование Центра Доверия для исключения отказа от сообщенияЕсли в будущем Алиса отрицает, что она передала сообщение, центр может предъявить копии сохраненного сообщения. Если сообщение Боба - дубликат сообщения, сохраненного в Центре, Алиса проиграет спор. Чтобы обеспечить всему этому конфиденциальность, можно добавить к схеме уровень шифрования/дешифрования, как это будет показано в следующей секции.
(рис 3.5) Дополнение конфиденциальности к схеме цифровой подписи Мы показали асимметрично-ключевое шифрование/дешифрование только для того, чтобы обратить ваше внимание на типы ключей, используемые в каждом конце передачи. Шифрование/дешифрование может также быть сделано симметричным ключом.
Эта секция описывает некоторые атаки цифровых подписей и определяет типы подделки.
Мы рассмотрим три вида атак цифровых подписей:
В
В
В
Если атака успешна, то в результате появляется подделка. Мы можем иметь два типа подделки:
Экзистенциальная подделка
В
В
Несколько
В лекции 10 мы обсуждали, как использовать криптографическую систему RSA для обеспечения секретности. Идея RSA может также применяться для того, чтобы подписать и подтвердить сообщение. В этом случае это называется
(рис 3.6) Общая идея схемы цифровой подписи RSA Подписание и подтверждение сайтов используют ту же самую функцию, но с различными параметрами. Верификатор сравнивает сообщение и вывод функции для сравнения. Если результат истинен, сообщение принято.
Генерация ключей в p и q и вычисляет n = p x q. Алиса вычисляет $$\varphi (n) = (p - 1) (q - 1)$$. Затем она выбирает e, для общедоступного ключа и вычисляет d для частного ключа, такое, что $$e x d = 1 mod \varphi \ (n)$$. Алиса сохраняет d и публично объявляет n и e.
d является частным;. e и. n - общедоступными.Подписание и проверка
Рис 3.7 показывает
(рис 3.7) Схема цифровой подписи RSAПодписание. Алиса на основе сообщения создает подпись, используя частный (секретный) ключ, S = Md mod n, и передает сообщение и подпись Бобу.
Проверка. Боб получает М и S. Он применяет общедоступный ключ Алисы к подписи, чтобы создать копию сообщения М' = Se mod n. Боб сравнивает значение М' со значением М. Если два значения совпадают, Боб принимает сообщение. Чтобы доказать правильность этой процедуры, мы применяем критерии проверки:
$$M' \equiv M(mod \ n) \to S^{e} \equiv M(mod \ n) \to M^{d x e} \equiv M(mod \ n)$$
Последняя конгруэнтность справедлива, потому что $$d x e = 1 mod \ \psi (n)$$ (см. теорему Эйлера в лекции 9).
Пример 3.1
Для безопасности подписи значения p и q должны быть очень большими. Как тривиальный пример, предположим, что Алиса выбирает p = 823 и q = 953 и вычисляет n = 784319. Значение $$\varphi (n)$$ - 782544. Теперь она выбирает e = 313 и вычисляет d = 160009. В этой точке генерация ключей закончена. Теперь вообразим, что Алиса хочет передать сообщение со значением M = 19070 Бобу. Она использует свой частный ключ 160009 для того, чтобы подписать сообщение:
M = 19070 -> S = (19070160009) mod 784319 = 210625 mod 784319
Алиса передает сообщение и подпись Бобу. Боб получает сообщение и подпись. Он вычисляет
$$М' = 210625313 \ mod \ 784319 = 19070 \ mod \ 784319 \ ? \ М \\ М' \equiv \ mod \ n$$Боб принимает сообщение, потому что он проверил подпись Алисы.
Атаки подписи RSA
Есть некоторые атаки, к которым Ева может обратиться для подделки
М, S ) и пробует создать другое сообщение М.', такое, что М' = Se mod n. Эта проблема по сложности решения равна проблеме
(M1, S1) и (M2, S2), которые используют один и тот же секретный ключ. Если М. = M1 x M2 mod n, тогда S. = S1 x S2 mod n. Это просто доказать, потому что мы имеем
S = S1 x S2 mod n =
(M1d x M2d) mod n =
(M1 x M2)d mod n =
Md mod n
Ева может создать М. = M1 x M2 mod n и может создать S. = S1 x S2 mod n ; глупый Боб поверит, что S - подпись Алисы на сообщении М. Эта атака, которая называется иногда мультипликативной атакой,
проводится очень просто. Однако это - М является произведением двух предыдущих сообщений, созданных Алисой, а не Евой; сообщение М. обычно бесполезно.
М1 и М2. С помощью их она позже создает новое сообщение М. = M1 x M2 . Ева может позже утверждать, что Алиса подписала M. Такую атаку называют так же, как и
предыдущую - мультипликативная атака. Это очень серьезная атака М1 и М2, чтобы получить полезный M ).
Подпись RSA на дайджесте сообщения
Как мы обсуждали прежде, подписание
(рис 3.8) Подпись RSА на дайджесте сообщения Алиса, подписывающее лицо, при первом использовании согласует
хэш-функцию, чтобы создать D = h(M). Затем она подписывает дайджест, S = Dd mod n. Сообщение и подпись передают Бобу. Боб, проверяющий, получает сообщение и подпись. Он сначала использует открытый ключ Алисы, чтобы извлечь (файл) дайджест, D' = Se mod n. Затем он применяет хэш-алгоритм для того, чтобы получить сообщение D = h(M).
Боб теперь сравнивает эти два дайджеста, D и D'. Если они являются сравнимыми по модулю n, он принимает сообщение.
Атаки на подписанные дайджесты RSA
Насколько восприимчива
(S, M) и пробует найти другое сообщение М', которое создает тот же самый дайджест, h (M) = h (М'). Как мы узнали в
лекции 1, если М. и М', такие, что h(M) = h(M'). Она соблазняет Алису подписать h(M), чтобы найти S ; теперь Ева имеет пару (М', S), которое прошло подтверждающий тест, но это - подделка. Мы изучали в
лекции 1, что если М, такое, что D = h (M). Как мы узнали в
лекции 1, если хэш-функция устойчива к прообразу, эта атака очень трудно осуществима.(М1,S1) и (М2, S2), которые были созданы с использованием одного и того же секретного ключа. Ева вычисляет S = S1 x S2. Если она сможет найти сообщение М, такое, что h(M) = h(M1) x h(M2), она сможет подделать новое сообщение. Однако нахождение М по данному h (M) - это очень трудный процесс, если
М1,и М2 для нее. Она может создать новую подпись S = S1 x S2. Так как Ева может вычислить h(M) = h(M1) x h(M2), если она может найти сообщение M данному h (M), это новое сообщение - подделка. Однако нахождение М по данному h (M) -очень трудный процесс, если
Криптосистема Эль-Гамаля была обсуждена в лекции 10.
(рис 3.9) Общая идея схемы цифровой подписи Эль-ГамаляВ процессе подписания две функции создают две подписи. На стороне подтверждения обрабатывают выходы двух функций и сравнивают между собой для проверки. Обратите внимание, что одна и та же функция применяется и для подписания, и для проверки, но использует различные входы. Рисунок показывает входы каждой функции. Сообщение - часть входа, для обеспечения функционирования при подписании; оно же - часть входа к функции 1 при подтверждении. Обратите внимание, что вычисления в функциях 1 и 3 проводятся по модулю p, а функции 2 - по модулю p - 1.
Генерация ключей
Процедура генерации ключей здесь точно такая же, как та, которая используется в p, чтобы в поле Z p* проблема e1 - простой элемент в Z p*. Алиса выбирает свой секретный ключ d, чтобы он был меньше, чем p - 1. Она вычисляет e2 = e1d. Открытый ключ Алисы - кортеж (e1, e2, p) ;
секретный ключ Алисы - d.
(e1, e2, p) - открытый ключ Алисы; d -секретный ключ Алисы.Подтверждение и проверка
Рисунок 3.10 показывает
(рис 3.10) Схема цифровой подписи Эль-ГамаляПодписывающаяся Алиса может подписать
r. Обратите внимание, что хотя открытые и секретные ключи могут использоваться неоднократно, Алиса каждый раз нуждается в новом r, когда она подписывает новое сообщение.S1 = er mod p.S2 = (М - d x S1) x r-1 mod (p - 1),где r - мультипликативная инверсия r по модулю p - 1.М, S1 и S2 Бобу.Проверка. Объект, например Боб, получает М, S1 и S2 и может проверить их следующим образом.
0 < S1 < p.0 < S2 < p - 1.V1 = e1M mod p.V2 = e2S1 x e2S2 mod p.V1 является конгруэнтным V2, сообщение принято; иначе оно будет отклонено. Мы можем доказать правильность этого критерия проверки, используя e2 = e1d и S1 = e1r:$$V_{1} \equiv V_{2} (mod \ p) \to e_{1}^{M} \equiv e_{2}^{M} \times S_{1}^{M} mod \ p \equiv (e_{1}^{d1})^{S1} \times (e_{1}^{r})^{S2} (mod \ p) \equiv e_{1}^{dS1+rS2} mod \ p$$
Мы имеем $$e_{1}^{M } \equiv e_{1}^{dS1 + rS2} mod \ p$$
Поскольку e1 - S2, с которого мы начали процесс подписания.
Пример 3.2
Ниже приводится тривиальный пример. Алиса выбрала p = 3119, e1 = 2, d = 127 и вычислила e2 = 2127 mod 3119 = 1702. Она выбрала r равным 307. Она объявила e1, e2 и p ; она сохранила в тайне d. Далее показано, как Алиса может подписать сообщение.
M = 320 S1 = e1r = 2307 = mod3119 S2 = (M - d x S1) x r-1 = (320 - 127 x 2083) x 307-1 = 2105 mod 3118
Алиса передает М, S1 и S2 Бобу. Боб использует открытый ключ, чтобы вычислить, что сообщение подписано Алисой, потому что никто, кроме Алисы, не имеет секретного ключа d.
V1 = e1M = 2320 = 3006 mod 3119 V2 = dS1 x S2S1 = 17022083 x 20832105 = 3006 mod 3119
Поскольку V1 и V2 являются конгруэнтными, Боб принимает сообщение, и он предполагает, что сообщение было подписано Алисой, потому что никто, кроме нее, не имеет секретного ключа Алисы d.
Пример 3.3
Теперь вообразите, что Алиса хочет передать другое сообщение, М = 3000, Тэду. Она выбирает новое r = 107. Алиса передает М., S1 и S2 Тэду. Тэд использует общедоступные ключи, чтобы вычислить V1 и V2.
M = 3000 S1 = e1r = 2107 = 2732mod3119 S2 = (M - d x S1) x r-1 = (3000 - 127 x 2083) x 107-1 = 2526 mod 3118 V1 = e1M = 23000 = 704 mod 3119 V2 = dS1 x S1S2 = 17022732 x 20832526 = 704 mod 3119
Поскольку V1 и V2 являются конгруэнтными, Тэд принимает сообщение; он предполагает, что сообщение подписано Алисой, потому что никто, кроме нее, не имеет секретного ключа Алисы d. Обратите внимание, что сообщение может получить любой человек. Цель состоит не в том, чтобы скрыть сообщение, но в том, чтобы доказать, что его передает Алиса.
Подделка цифровой подписи в схеме Эль-Гамаля
Подделка только ключа. В этом типе подделки Ева имеет доступ только к открытому ключу. Возможны два варианта:
S1 и S2 для этого сообщения. Это - S2 и вычислить S1. Она должна иметь $$d_{1}^{S1} x S_{1}^{S2} \equiv e_{1}^{M} (mod \ p)$$. Другими словами, $$S_{1}^{S2} \equiv e_{1}^{M} d_{1}^{-S1} (mod\ p)$$ или $$S_{2} \equiv log_{S1}(e_{1}^{M} d_{1}^{-S1}) (mod \ p)$$. Это
означает
вычисление S2 и вычислить S1. Это намного труднее, чем выполнить часть aМ, S1 и S2, такие, что подпись первого используется для второго. Если Ева может найти два новых параметра x и y, такие, что М = xS2 mod (p - 1) и S1 = -y S2 mod (p - 1), то она может подделать сообщение, но серьезной выгоды не получит, поскольку это - Подделка при известном сообщении. Если Ева перехватила сообщение М и его две подписи S1 и S2, она может найти другое сообщение М', с той же самой парой подписей S1 и S2. Однако обратите внимание, что это -
Проблема p должно быть очень большим, чтобы сделать трудной проблему Zp*. Рекомендуется длина p по крайней мере 1024 битов. Можно сделать подпись размером 2048 бит. Чтобы уменьшить размер подписи, Шнорр предложил новую схему, основанную на
(рис 3.11) Общая идея схемы цифровой подписи ШнорраВ процессе подписания две функции создают две подписи; в процессе проверки выход одной функции сравнивается с первой подписью для проверки.
рис. 3.11 показывает входы к каждой функции. Важно то, что схема использует два модуля: p и q. Функции 1 и 3 используют p ; функция 2 использует q. Детали входов и функций будут коротко обсуждены далее.
Генерация ключей
Перед подписанием сообщения Алиса должна генерировать ключи и объявить всем общедоступные ключи.
p, которое обычно равно по длине 1024 битам.q должно делиться на (p - 1). Другими словами, (p - 1) = 0 mod q.e1, q -тый
корень которого был бы равен 1 mod p. Чтобы сделать это, Алиса выбирает примитивный элемент в Zp, e0 (см. приложение J) и вычисляет e1 = e0(p-1)/q mod p.d, как свой секретный ключ.e2 = e1d mod p.(e1, e2, p, q), ее секретный ключ - (d).Подписание и проверка
Рисунок 3.12 показывает
(рис 3.12) Схема цифровой подписи ШнорраПодписание
r. Обратите внимание, что открытый и секретный ключи могут использоваться для подписи многих сообщений. Но Алиса должна изменять r каждый раз,
когда она передает новое сообщение. Обратите внимание также на то, что r должен иметь значение между 1 и q.S1 = h(M | e1r mod p) . Сообщение присоединяется (конкатенируется) спереди к значению e1r mod p, затем применяется хэш-функция, чтобы создать дайджест. Обратите внимание, что хэш-функция непосредственно не применяется к сообщению, но вместо этого она получается из последовательного соединения М. и e1r mod p.S2 = r + d x S1 mod q. Обратите внимание, что эта часть - вычисление S2 - делается в арифметике по модулю q.М., S1 и S2.Верификация (проверка) сообщения. Приемник, например Боб, получает М., S1 и S2.
V = h (М | e1S2 e2-S1 mod p).S2 конгруэнтно V по модулю p, сообщение принято; иначе оно отклоняется.Пример 3.4
Вот тривиальный пример. Предположим, что мы выбираем q = 103 и p = 2267. Обратите внимание на то, что p = 22 x q + 1. Мы выбираем e0 = 2, которое является элементом в Z2267*. Тогда (p - 1) / q = 22, так что мы имеем e1 = 222 mod 2267 = 354.
Мы выбираем d = 30, тогда e2 = 35430 mod 2267 = 1206. Секретный ключ Алисы -теперь - (d), ее общедоступный ключ - (e1,e2,p,q).
Алиса хочет передать сообщение М. Она выбирает r = 11 и вычисляет er = 35411 = 630 mod 2267. Предположим, что сообщение - 1000, и конкатенация (последовательное соединение) означает 1000630. Также предположим, что хэширование этого значения дает дайджест h (1000630) = 200. Это означает S1 = 200. Алиса вычисляет S2 = r + d x S1 mod q = 11 + 1026 200 mod 103 = 11 + 24 = 35. Алиса передает сообщение М =1000, S1 = 200 и S2 = 35. Проверку оставляем как упражнение.
Подделка по
Похоже, что все атаки на S1 = h (М. | e1r(mod p)). Это означает, что хэш-функция применяется к комбинации сообщение и e1r, в которой r является секретным.
(рис 3.13) Общая идея схемы DSSВ процессе подписания две функции создают две подписи; в процессе проверки выход одной функции сравнивается с первой подписью для проверки. Это подобно p и q. Функции 1 и 3 используют оба модуля p и q, функция 2 - только q. Детали входов и функций коротко рассматриваются ниже.
Генерация ключей
Перед подписанием сообщения к любому объекту Алиса должна генерировать ключи и объявить общедоступные ключи.
p. между 512 и 1024 битами. Число битов в p должно быть кратно числу 64.q с таким условием, чтобы оно делилось на (p - 1).<Zp*, x > и <Zq* ,x > ; вторая - подгруппа первой.e1, такое, чтобы оно было q -тым корнем 1 по модулю p (e1p = 1 mod p). Она поступает так: выбирает элемент в Zp, e0, и вычисляет e1 = e0(p-1)/q mod p.d как секретный ключ и вычисляет e2 = e1d(e1, e2, p, q), ее секретный ключ - (d).Подписание и проверка
Рисунок 3.14 показывает схему DSS.
(рис 3.14) Схема DSSПодписание. Ниже показаны шаги подписания сообщения.
(1 <= r <= q). Обратите внимание, что хотя открытые и секретные ключи могут быть выбраны один раз и использоваться для того, чтобы подписать много сообщений, Алиса должна выбирать каждый раз новый r, когда она должна подписать новое сообщение.S1 = (e1 mod p) mod q. Обратите внимание: значение первой подписи не зависит от М (сообщения).h (M).S2 = (h(M) + dS1)r-1mod q. Обратите внимание, что вычисление S2 делается по модулю q.M, S1 и S2 Бобу.Проверка (верификация). Для проверки сообщения обычно применяются следующие шаги, когда получены М, S1 и S2.
S1 0 < S1 < q.S2 0 < S2 < q.М, применяя V = [(e1h(M)/S2 e2S1/S2) mod p] mod q.S конгруэнтен V, сообщение принимается; иначе - отклоняется.Пример 3.5
Алиса выбирает q = 101 и p = 8081. Алиса выбирает e0 = 3 и вычисляет e1 = e0(p-1)/q mod p = 6968. Алиса выбирает d = 61 в качестве секретного ключа и вычисляет e2 = e1d mod p = 2038. Теперь Алиса может передать сообщение Бобу. Предположим, что h (M) = 5000, и Алиса выбирает r = 61:
h(M) = 5000 r =61 S1 = (e1r mod p) mod q = 54 S2 = (h(M) + dS1)r-1 mod q = 40 S2-1 = 48 mod 101 V = [(69685000 x 48 x 203854 x 48 x 203854 x 48)mod 8081]mod 101 = 54
Поскольку Sj и V являются подходящими, Боб принимает сообщение.
Сравнение DSS и RSА
Вычисление DSS-подписи быстрее, чем вычисление подписей RSА, при использовании того же самого p.
Сравнение DSS и схемы Эль-Гамаля
DSS-подпись - меньше, чем подписи в q меньше, чем p.
Наша последняя схема -
В процессе подписания две функции и экстрактор (извлекающее устройство) создают две подписи; в процессе проверки (верификации) обрабатывают выход одной функции (после прохождения через экстрактор) и сравнивают ее с первой подписью для проверки. Функции f1 и f3 фактически создают точки на кривой. Первая создает новую точку для секретного ключа подписывающего лица. Вторая - новую точку из двух общедоступных ключей подписывающего лица. Каждый экстрактор извлекает первые координаты соответствующей точки в модульной арифметике. Детали входов и функций коротко обсуждаются далее.
(рис 3.15) Общая идея схемы DSSГенерация ключей
Генерация ключей осуществляется следующими шагами:
Ep (a,b)p.q, чтобы использовать для вычисления.d, целое число.e1(.,....)e2 (..,....) = d x e1 (......), другую точку на кривой.(a, b, p, q, e1, e2), ее секретный ключ - d.Подписание и проверка (верификация)
Рис. 3.16 показывает
(рис 3.16) Схема EDSSПодписание. Процесс подписания состоит главным образом из выбора секретного случайного числа, создания третьей точки на кривой, вычисления двух подписей и передачи сообщения и подписей.
r, между 1 и q - 1.P (U, v) = r x e1 (......).P (u, v), чтобы вычислить первую подпись S1 . Это означает S1 = u mod q.r и S1, чтобы вычислить вторую подпись S2 = (h (M) + d x S1) r-1 mod q,М, S1 и S2.Проверка (верификация).Процесс проверки состоит главным образом из восстановления третьей точки и подтверждения, что первая координата эквивалентна S1 по модулю q. Обратите внимание, что третья точка была создана подписывающим лицом, использующим секретное случайное число r. Верификатор не имеет этого значения. Ему нужно создать третью точку из S1 , и S2.
М, S1 и S2 для создания двух промежуточных результатов A и B:A = h(M)S2-1 mod q
B = S2-1S1 mod q
Затем Боб восстанавливает третью точку T(x,y) = A x e1( ... , ...) + B x e2( ... , ...)
T(x,y), чтобы проверить сообщение. Если x = S1 mod q, подпись принимается, иначе - отклоняется.В этой секции кратко обсуждаются варианты и приложения для цифровых подписей.
Ниже проводится краткое обсуждение некоторых вариантов и дополнений к главному понятию цифровых подписей. Для более четкого понимания читатель может посмотреть специальную литературу.
Подпись с указанием времени
Иногда подписанный документ должен иметь указание времени, чтобы препятствовать действиям противника. Это названо
Например, Алиса подписывает запрос своему банку (условно Бобу), выдать некоторую сумму денег Еве. Документ может быть перехвачен Евой, если на этом документе нет никакого указания времени.
Включение фактической даты и времени на документах может создать проблемы - несинхронизированные часы, отсутствие универсального времени. Одно решение состоит в том, чтобы использовать nonce (number only once - Nonce) - одноразовое случайное число, которое может быть использовано только однажды. Когда приемник получает документ с
Слепые подписи
Иногда мы имеем документ, который хотим подписать, не раскрывая содержание документа подписывающему лицу. Например, ученый хочет сообщить Бобу, что он, возможно, открыл очень важную теорию, которую необходимо подписать у обычного нотариуса. Он просит Алису передать это, не разрешая ей узнать содержание теории. Для этой цели Дэвид Чом (David Caum) разработал некоторые патентованные
Слепая подпись, основанная на схеме RSА. Опишем кратко b, и вычисляет слепое сообщение B = М. x be mod n, в котором e является открытым ключом Алисы и n - определенным модулем в схеме цифровой подписи RSА. Обратите внимание, что b иногда называется "маскирующим коэффициентом", который Боб передает Алисе.
Алиса подписывает маскированное сообщение, используя Sblind = Bd mod n, где d является секретным ключом Алисы. Обратите внимание, что Sb - подпись на слепой (маскированной) версии сообщения.
Боб просто использует мультипликативную инверсию его случайного числа b, чтобы отделить слепое сообщение от подписи. Подпись - S = Sb b-1 mod n. Мы можем доказать, что S - подпись на первоначальном сообщении, как это определено в
S - подпись, если Боб передал первоначальное сообщение, которое будет подписано Алисой.
Предотвращение мошенничества. При слепой подписи появляется опасность, что Боб, может дать Алисе подписать слепое сообщение, которое может навредить ей. Например, сообщение Боба могло быть документом, утверждающим, что Алиса передаст Бобу все свое имущество после ее смерти. Есть по крайней мере три способа предотвратить такой ущерб.
В дальнейшем в этой книге обсуждаются несколько приложений криптографии для сетевой безопасности. Большинство этих приложений непосредственно или косвенно требует использования открытых ключей. Чтобы использовать открытый ключ, человек должен доказать, что он законно владеет этим ключом. По этой причине была разработана идея сертификации и свидетельств сертификации (CA) (См. лекцию 4 и лекцию 5). Свидетельства (CA), чтобы быть признанными, должны быть подписаны. Цифровые подписи используются, чтобы обеспечить такое доказательство. Когда Алиса должна применить открытый ключ Боба, она пользуется свидетельством. Сертифицированные CA используют общедоступный ключ с секретным ключом и проверяемой подписью Алисы. Само свидетельство содержит общедоступный ключ Боба.
Сегодняшние протоколы, которое используют услуги CA, - это IPSec (лекция 8), SSL/TLS ( лекция 7) и S/MIME ( лекция 6). Протокол PGP поддерживает свидетельства, но они могут быть заменены соглашениями между людьми в сообществе.
Для более детального изучения положений, обсужденных в этой лекции, мы рекомендуем нижеследующие книги и сайты. Пункты, указанные в скобках, показаны в списке ссылок в конце книги.
[Sti06], [TW06] и [PHS03] подробно рассматривают цифровые подписи.
Нижеследующие сайты дают больше информации о темах, обсужденных в этой лекции.
p = 809, q = 751, и d = 23, вычислите общедоступный ключ e.Затем
M1 = 100. Получите подпись S1.М2 = 50. Получите подпись S2.М = M1 x М2 = 5000, то S = S1 x S2.p = 881 и d = 700, найдите значения e1 и e2. Выберите r = 17. Найдите значение S1 и S2, если М = 400.q = 83, p = 997 и d = 23, найдите значения для e1 и e2. Выберите r = 11. Если М
= 400 и h (400) = 100, найдите значение S1., S2 и V. Равно ли $$S_{1} \equiv V (mod \ p)$$?q = 59, p = 709 и d = 14, найдите значения для e1 и e2. Выберите r = 13. Найдите значение S1 и S2, если h (M) = 100. Проверьте подпись.S и размером n.S1 и S2 в зависимости от размера p.S1 и S2 в зависимости от размера p и q.S1 и S2 в зависимости от размера p и q.S2 = 0, то две подписи должны быть повторно вычислены, используя новый r. Какова причина этого?r, используемое подписывающим лицом? Возможно ли это в принципе? Объясните ваш ответ отдельно для схем Эль-Гамаля-Шнорра, DSS.n? Объясните ваш ответ отдельно для каждого протокола: Эль-Гамаля, Шнорра или DSS.p и q являются маленькими. Используйте p = 19 и q = 3.p мало. Используйте p = 19.p и q являются маленькими. Используйте p =29 и q = 7.p и q являются маленькими. Используйте p =29 и q = 7.r, может ли она подделать сообщение? Объясните.r, может ли она подделать сообщение? Объясните.r, может ли она подделать сообщение? Объясните.p, q, e1 и r в S1 и S2 в S2 делается по модулю p, а вычисление S2 делается по модулю p - 1.S1 делается по модулю p, а вычисление S2 делается по модулю q.S1 делается по модулю p и модулю q, а вычисление S2 делается только по модулю q.Мы все знакомы с понятием подписи. Человек подписывает документ, чтобы показать, что нечто сделано им самим или было им одобрено. Подпись - доказательство получателю, что документ исходит от истинного объекта. Когда клиент подписывает чек, банк должен убедиться, что чек принадлежит клиенту и никому другому. Другими словами, подпись на документе является признаком установления подлинности автора - подлинности документа. Рассмотрим картину, подписанную художником. Подпись на предмете искусства, если она подлинная, означает, что этот предмет, вероятно, подлинный.
Когда Алиса передает сообщение Бобу, Боб должен проверить подлинность передатчика; он должен убедиться, что сообщение исходит от Алисы, а не от Евы. Боб может попросить, чтобы Алиса подписала сообщение с помощью электроники. Другими словами,
В этой лекции мы сначала рассмотрим некоторые проблемы, связанные с цифровыми подписями, а затем перейдем к рассмотрению различных
Рассмотрение начнем с отличия между обычными подписями и цифровыми подписями.
Обычная подпись включена в документ; это - часть документа. Когда мы пишем чек, подпись находится на чеке; это - не отдельный документ. Но когда мы подписываем документ в цифровой форме, мы передаем подпись как отдельный документ. Передатчик передает два документа: сообщение и подпись. Получатель получает оба документа и проверяет, что подпись принадлежит предполагаемому передатчику. Если это доказано, сообщение сохраняется; иначе оно отклоняется.
Второе отличие между двумя типами подписей - метод подтверждения подписи. В случае обычной подписи, когда получатель получает документ, он сравнивает подпись на документе с подписью в архиве. Если они одинаковые, документ подлинный. Получатель должен иметь в архиве копию для сравнения этой подписи. При цифровой подписи - получатель получает сообщение и подпись, но копия подписи не хранится нигде. Получатель должен применить методику проверки комбинации сообщения и подписи, чтобы проверить подлинность.
В случае обычной подписи есть отношения "один ко многим" между подписью и документами. Человек использует ту же самую подпись, чтобы подписать много документов. Для цифровой подписи есть непосредственные отношения между подписью и сообщением. Каждое сообщение имеет свою собственную подпись. Подпись одного сообщения не может использоваться в другом сообщении. Если Боб получает два сообщения, один за другим, от Алисы, он не может использовать подпись первого сообщения, чтобы проверить второе. Каждое сообщение нуждается в новой подписи.
Другая разность между двумя типами подписей - качество, названное резервное копирование. При обычной подписи ее копия на поступившем документе может отличаться от копии, сохраненной в архиве. В цифровой подписи нет такого различия, если нет указателя времени (такого как метка времени) на документе. Например, предположите, что Алиса передает документ, инструктирующий Боба заплатить Еве. Если Ева перехватывает документ и сохраняет подпись, она может воспользоваться этим позже (скопировать подпись), чтобы снова получить деньги от Боба.
Рис. 3.1 показывает процесс цифровой подписи. Передатчик использует
(рис 3.1) Процесс передачи цифровой подписиПотребность в ключах
Обычная подпись походит на частный "ключ", принадлежащий лицу, которое подписывает документ. Подписывающее лицо использует его, чтобы подписать документы; никто другой не имеет эту подпись. Копия подписи находится в архиве подобно открытому ключу; любой может использовать его, чтобы проверить документ, сравнить подпись с первоначальной подписью.
В цифровой подписи подписывающее лицо использует свой секретный ключ - прикладной
Мы можем добавить секретный и открытый ключи к рис. 3.1, чтобы дать законченное понятие цифровой подписи (см. рис. 3.2). Обратите внимание, что когда документ подписан, любой, включая Боба, может проверить это, потому что каждый имеет доступ к открытому ключу Алисы. Алиса не должна использовать свой открытый ключ для того, чтобы подписывать документ, потому что тогда любой сможет подделать ее подпись.
(рис 3.2) Дополнение передачи цифровой подписи ключом Алисы Можем ли мы использовать секретный (симметричный) ключ, чтобы и подписать и проверить подпись? Ответ отрицателен по нескольким причинам.
Первая: ключ засекречивания известен только двум объектам (например, Алисе и Бобу). Так, если Алиса должна подписать другой документ и передать его Тэду, она должна использовать другой ключ засекречивания.
Вторая: как мы увидим, создавая ключ засекречивания для сеанса, в него включают признаки установления подлинности, которые используют цифровую подпись. Мы получим порочный круг.
Третье: Боб может использовать ключ засекречивания, который он использует между собой и Алисой, подписать документ, передать его Тэду и имитировать, что он прибыл от Алисы.
Мы должны понимать различие между секретным и открытым ключами, используемыми в цифровых подписях, и секретным и открытым ключами, которые применяются в
В лекции 10 мы узнали, что криптосистемы с асимметричными ключами очень неэффективны, когда имеют дело с длинными сообщениями. В системе цифровой подписи сообщения обычно длинные, но мы должны использовать асимметрично-ключевые схемы. Решение состоит в том, что подпись
(рис 3.3) Подписание дайджеста Дайджест получается из сообщения на стороне Алисы и проходит процесс подписания, используя секретный ключ Алисы. Алиса затем передает сообщение и подпись Бобу. Как мы увидим позже в этой лекции, есть варианты в процессе подписания, которые зависят от системы. Например, могут быть проведены дополнительные вычисления, прежде чем получается дайджест, или может быть использована другая система засекречивания. В некоторых системах подпись имеет множество значений.
На стороне Боба используется та же самая общедоступная хэш-функция, и сначала из полученного сообщения создается дайджест. Далее вычисляются подпись и дайджест. Процесс подтверждения также проверяет прикладные критерии по результатам вычисления, чтобы определить подлинность подписи. Если подпись подлинна, то сообщение принимается; в противном случае она отклоняется.
Мы обсуждали несколько услуг безопасности в лекции 1, включая конфиденциальность сообщения, установление подлинности сообщения, целостность сообщения и исключение отказа от сообщения.
Безопасность
Целостность сообщения сохраняется, даже если мы подписываем все сообщение, потому что мы не можем получить ту же самую подпись, если сообщение изменено.
Если Алиса подписывает сообщение и затем отрицает это, может ли Боб доказать, что Алиса фактически подписала его? Например, Алиса передает сообщение банку (Боб) и просит перечислить 10000 $ с ее счета на счет Тэда.
Может ли Алиса потом отрицать, что она передала это сообщение? Согласно схеме, которую мы рассматривали до сих пор, Боб мог бы иметь проблему. Боб должен был сохранить подпись в архиве и далее использовать открытый ключ Алисы, чтобы создать первоначальное сообщение, и доказать, что сообщение в архиве и недавно полученное сообщение является одним и тем же. Это невыполнимо, потому что Алиса может изменить за это время свой секретный или открытый ключ. Она может также утверждать, что сообщение в архиве, содержащее подпись, не подлинное.
Одно из решений - третье лицо (доверенное лицо). Люди могут по договоренности иметь сторону, которой они доверяют. В будущих лекциях мы увидим, что сторона, которой доверяют, может решить много других проблем относительно служб безопасности и замены ключей. рис. 3.4 показывает, как сторона, которой доверяют, может препятствовать отрицанию Алисой передачи данного сообщения.
Алиса создает подпись из своего сообщения ( SA ) и передает центру сообщение, которое содержит ее опознавательные признаки, опознавательные признаки Боба, а также подпись. Центр, после проверки правильности открытого ключа Алисы, проверяет с помощью этого ключа Алисы, что сообщение прибыло от Алисы. Затем Центр сохраняет копию сообщения с опознавательными признаками передатчика, опознавательными признаками получателя, а также с меткой времени, в своем архиве. Центр использует свой секретный ключ, чтобы создать из сообщения другую подпись ( ST ). Затем центр передает сообщение, новую подпись, опознавательные признаки Алисы и опознавательные признаки Боба - Бобу. Боб проверяет сообщение, используя общедоступный ключ центра, которому он доверяет.
(рис 3.4) Использование Центра Доверия для исключения отказа от сообщенияЕсли в будущем Алиса отрицает, что она передала сообщение, центр может предъявить копии сохраненного сообщения. Если сообщение Боба - дубликат сообщения, сохраненного в Центре, Алиса проиграет спор. Чтобы обеспечить всему этому конфиденциальность, можно добавить к схеме уровень шифрования/дешифрования, как это будет показано в следующей секции.
(рис 3.5) Дополнение конфиденциальности к схеме цифровой подписи Мы показали асимметрично-ключевое шифрование/дешифрование только для того, чтобы обратить ваше внимание на типы ключей, используемые в каждом конце передачи. Шифрование/дешифрование может также быть сделано симметричным ключом.
Эта секция описывает некоторые атаки цифровых подписей и определяет типы подделки.
Мы рассмотрим три вида атак цифровых подписей:
В
В
В
Если атака успешна, то в результате появляется подделка. Мы можем иметь два типа подделки:
Экзистенциальная подделка
В
В
Несколько
В лекции 10 мы обсуждали, как использовать криптографическую систему RSA для обеспечения секретности. Идея RSA может также применяться для того, чтобы подписать и подтвердить сообщение. В этом случае это называется
(рис 3.6) Общая идея схемы цифровой подписи RSA Подписание и подтверждение сайтов используют ту же самую функцию, но с различными параметрами. Верификатор сравнивает сообщение и вывод функции для сравнения. Если результат истинен, сообщение принято.
Генерация ключей в p и q и вычисляет n = p x q. Алиса вычисляет $$\varphi (n) = (p - 1) (q - 1)$$. Затем она выбирает e, для общедоступного ключа и вычисляет d для частного ключа, такое, что $$e x d = 1 mod \varphi \ (n)$$. Алиса сохраняет d и публично объявляет n и e.
d является частным;. e и. n - общедоступными.Подписание и проверка
Рис 3.7 показывает
(рис 3.7) Схема цифровой подписи RSAПодписание. Алиса на основе сообщения создает подпись, используя частный (секретный) ключ, S = Md mod n, и передает сообщение и подпись Бобу.
Проверка. Боб получает М и S. Он применяет общедоступный ключ Алисы к подписи, чтобы создать копию сообщения М' = Se mod n. Боб сравнивает значение М' со значением М. Если два значения совпадают, Боб принимает сообщение. Чтобы доказать правильность этой процедуры, мы применяем критерии проверки:
$$M' \equiv M(mod \ n) \to S^{e} \equiv M(mod \ n) \to M^{d x e} \equiv M(mod \ n)$$
Последняя конгруэнтность справедлива, потому что $$d x e = 1 mod \ \psi (n)$$ (см. теорему Эйлера в лекции 9).
Пример 3.1
Для безопасности подписи значения p и q должны быть очень большими. Как тривиальный пример, предположим, что Алиса выбирает p = 823 и q = 953 и вычисляет n = 784319. Значение $$\varphi (n)$$ - 782544. Теперь она выбирает e = 313 и вычисляет d = 160009. В этой точке генерация ключей закончена. Теперь вообразим, что Алиса хочет передать сообщение со значением M = 19070 Бобу. Она использует свой частный ключ 160009 для того, чтобы подписать сообщение:
M = 19070 -> S = (19070160009) mod 784319 = 210625 mod 784319
Алиса передает сообщение и подпись Бобу. Боб получает сообщение и подпись. Он вычисляет
$$М' = 210625313 \ mod \ 784319 = 19070 \ mod \ 784319 \ ? \ М \\ М' \equiv \ mod \ n$$Боб принимает сообщение, потому что он проверил подпись Алисы.
Атаки подписи RSA
Есть некоторые атаки, к которым Ева может обратиться для подделки
М, S ) и пробует создать другое сообщение М.', такое, что М' = Se mod n. Эта проблема по сложности решения равна проблеме
(M1, S1) и (M2, S2), которые используют один и тот же секретный ключ. Если М. = M1 x M2 mod n, тогда S. = S1 x S2 mod n. Это просто доказать, потому что мы имеем
S = S1 x S2 mod n =
(M1d x M2d) mod n =
(M1 x M2)d mod n =
Md mod n
Ева может создать М. = M1 x M2 mod n и может создать S. = S1 x S2 mod n ; глупый Боб поверит, что S - подпись Алисы на сообщении М. Эта атака, которая называется иногда мультипликативной атакой,
проводится очень просто. Однако это - М является произведением двух предыдущих сообщений, созданных Алисой, а не Евой; сообщение М. обычно бесполезно.
М1 и М2. С помощью их она позже создает новое сообщение М. = M1 x M2 . Ева может позже утверждать, что Алиса подписала M. Такую атаку называют так же, как и
предыдущую - мультипликативная атака. Это очень серьезная атака М1 и М2, чтобы получить полезный M ).
Подпись RSA на дайджесте сообщения
Как мы обсуждали прежде, подписание
(рис 3.8) Подпись RSА на дайджесте сообщения Алиса, подписывающее лицо, при первом использовании согласует
хэш-функцию, чтобы создать D = h(M). Затем она подписывает дайджест, S = Dd mod n. Сообщение и подпись передают Бобу. Боб, проверяющий, получает сообщение и подпись. Он сначала использует открытый ключ Алисы, чтобы извлечь (файл) дайджест, D' = Se mod n. Затем он применяет хэш-алгоритм для того, чтобы получить сообщение D = h(M).
Боб теперь сравнивает эти два дайджеста, D и D'. Если они являются сравнимыми по модулю n, он принимает сообщение.
Атаки на подписанные дайджесты RSA
Насколько восприимчива
(S, M) и пробует найти другое сообщение М', которое создает тот же самый дайджест, h (M) = h (М'). Как мы узнали в
лекции 1, если М. и М', такие, что h(M) = h(M'). Она соблазняет Алису подписать h(M), чтобы найти S ; теперь Ева имеет пару (М', S), которое прошло подтверждающий тест, но это - подделка. Мы изучали в
лекции 1, что если М, такое, что D = h (M). Как мы узнали в
лекции 1, если хэш-функция устойчива к прообразу, эта атака очень трудно осуществима.(М1,S1) и (М2, S2), которые были созданы с использованием одного и того же секретного ключа. Ева вычисляет S = S1 x S2. Если она сможет найти сообщение М, такое, что h(M) = h(M1) x h(M2), она сможет подделать новое сообщение. Однако нахождение М по данному h (M) - это очень трудный процесс, если
М1,и М2 для нее. Она может создать новую подпись S = S1 x S2. Так как Ева может вычислить h(M) = h(M1) x h(M2), если она может найти сообщение M данному h (M), это новое сообщение - подделка. Однако нахождение М по данному h (M) -очень трудный процесс, если
Криптосистема Эль-Гамаля была обсуждена в лекции 10.
(рис 3.9) Общая идея схемы цифровой подписи Эль-ГамаляВ процессе подписания две функции создают две подписи. На стороне подтверждения обрабатывают выходы двух функций и сравнивают между собой для проверки. Обратите внимание, что одна и та же функция применяется и для подписания, и для проверки, но использует различные входы. Рисунок показывает входы каждой функции. Сообщение - часть входа, для обеспечения функционирования при подписании; оно же - часть входа к функции 1 при подтверждении. Обратите внимание, что вычисления в функциях 1 и 3 проводятся по модулю p, а функции 2 - по модулю p - 1.
Генерация ключей
Процедура генерации ключей здесь точно такая же, как та, которая используется в p, чтобы в поле Z p* проблема e1 - простой элемент в Z p*. Алиса выбирает свой секретный ключ d, чтобы он был меньше, чем p - 1. Она вычисляет e2 = e1d. Открытый ключ Алисы - кортеж (e1, e2, p) ;
секретный ключ Алисы - d.
(e1, e2, p) - открытый ключ Алисы; d -секретный ключ Алисы.Подтверждение и проверка
Рисунок 3.10 показывает
(рис 3.10) Схема цифровой подписи Эль-ГамаляПодписывающаяся Алиса может подписать
r. Обратите внимание, что хотя открытые и секретные ключи могут использоваться неоднократно, Алиса каждый раз нуждается в новом r, когда она подписывает новое сообщение.S1 = er mod p.S2 = (М - d x S1) x r-1 mod (p - 1),где r - мультипликативная инверсия r по модулю p - 1.М, S1 и S2 Бобу.Проверка. Объект, например Боб, получает М, S1 и S2 и может проверить их следующим образом.
0 < S1 < p.0 < S2 < p - 1.V1 = e1M mod p.V2 = e2S1 x e2S2 mod p.V1 является конгруэнтным V2, сообщение принято; иначе оно будет отклонено. Мы можем доказать правильность этого критерия проверки, используя e2 = e1d и S1 = e1r:$$V_{1} \equiv V_{2} (mod \ p) \to e_{1}^{M} \equiv e_{2}^{M} \times S_{1}^{M} mod \ p \equiv (e_{1}^{d1})^{S1} \times (e_{1}^{r})^{S2} (mod \ p) \equiv e_{1}^{dS1+rS2} mod \ p$$
Мы имеем $$e_{1}^{M } \equiv e_{1}^{dS1 + rS2} mod \ p$$
Поскольку e1 - S2, с которого мы начали процесс подписания.
Пример 3.2
Ниже приводится тривиальный пример. Алиса выбрала p = 3119, e1 = 2, d = 127 и вычислила e2 = 2127 mod 3119 = 1702. Она выбрала r равным 307. Она объявила e1, e2 и p ; она сохранила в тайне d. Далее показано, как Алиса может подписать сообщение.
M = 320 S1 = e1r = 2307 = mod3119 S2 = (M - d x S1) x r-1 = (320 - 127 x 2083) x 307-1 = 2105 mod 3118
Алиса передает М, S1 и S2 Бобу. Боб использует открытый ключ, чтобы вычислить, что сообщение подписано Алисой, потому что никто, кроме Алисы, не имеет секретного ключа d.
V1 = e1M = 2320 = 3006 mod 3119 V2 = dS1 x S2S1 = 17022083 x 20832105 = 3006 mod 3119
Поскольку V1 и V2 являются конгруэнтными, Боб принимает сообщение, и он предполагает, что сообщение было подписано Алисой, потому что никто, кроме нее, не имеет секретного ключа Алисы d.
Пример 3.3
Теперь вообразите, что Алиса хочет передать другое сообщение, М = 3000, Тэду. Она выбирает новое r = 107. Алиса передает М., S1 и S2 Тэду. Тэд использует общедоступные ключи, чтобы вычислить V1 и V2.
M = 3000 S1 = e1r = 2107 = 2732mod3119 S2 = (M - d x S1) x r-1 = (3000 - 127 x 2083) x 107-1 = 2526 mod 3118 V1 = e1M = 23000 = 704 mod 3119 V2 = dS1 x S1S2 = 17022732 x 20832526 = 704 mod 3119
Поскольку V1 и V2 являются конгруэнтными, Тэд принимает сообщение; он предполагает, что сообщение подписано Алисой, потому что никто, кроме нее, не имеет секретного ключа Алисы d. Обратите внимание, что сообщение может получить любой человек. Цель состоит не в том, чтобы скрыть сообщение, но в том, чтобы доказать, что его передает Алиса.
Подделка цифровой подписи в схеме Эль-Гамаля
Подделка только ключа. В этом типе подделки Ева имеет доступ только к открытому ключу. Возможны два варианта:
S1 и S2 для этого сообщения. Это - S2 и вычислить S1. Она должна иметь $$d_{1}^{S1} x S_{1}^{S2} \equiv e_{1}^{M} (mod \ p)$$. Другими словами, $$S_{1}^{S2} \equiv e_{1}^{M} d_{1}^{-S1} (mod\ p)$$ или $$S_{2} \equiv log_{S1}(e_{1}^{M} d_{1}^{-S1}) (mod \ p)$$. Это
означает
вычисление S2 и вычислить S1. Это намного труднее, чем выполнить часть aМ, S1 и S2, такие, что подпись первого используется для второго. Если Ева может найти два новых параметра x и y, такие, что М = xS2 mod (p - 1) и S1 = -y S2 mod (p - 1), то она может подделать сообщение, но серьезной выгоды не получит, поскольку это - Подделка при известном сообщении. Если Ева перехватила сообщение М и его две подписи S1 и S2, она может найти другое сообщение М', с той же самой парой подписей S1 и S2. Однако обратите внимание, что это -
Проблема p должно быть очень большим, чтобы сделать трудной проблему Zp*. Рекомендуется длина p по крайней мере 1024 битов. Можно сделать подпись размером 2048 бит. Чтобы уменьшить размер подписи, Шнорр предложил новую схему, основанную на
(рис 3.11) Общая идея схемы цифровой подписи ШнорраВ процессе подписания две функции создают две подписи; в процессе проверки выход одной функции сравнивается с первой подписью для проверки.
рис. 3.11 показывает входы к каждой функции. Важно то, что схема использует два модуля: p и q. Функции 1 и 3 используют p ; функция 2 использует q. Детали входов и функций будут коротко обсуждены далее.
Генерация ключей
Перед подписанием сообщения Алиса должна генерировать ключи и объявить всем общедоступные ключи.
p, которое обычно равно по длине 1024 битам.q должно делиться на (p - 1). Другими словами, (p - 1) = 0 mod q.e1, q -тый
корень которого был бы равен 1 mod p. Чтобы сделать это, Алиса выбирает примитивный элемент в Zp, e0 (см. приложение J) и вычисляет e1 = e0(p-1)/q mod p.d, как свой секретный ключ.e2 = e1d mod p.(e1, e2, p, q), ее секретный ключ - (d).Подписание и проверка
Рисунок 3.12 показывает
(рис 3.12) Схема цифровой подписи ШнорраПодписание
r. Обратите внимание, что открытый и секретный ключи могут использоваться для подписи многих сообщений. Но Алиса должна изменять r каждый раз,
когда она передает новое сообщение. Обратите внимание также на то, что r должен иметь значение между 1 и q.S1 = h(M | e1r mod p) . Сообщение присоединяется (конкатенируется) спереди к значению e1r mod p, затем применяется хэш-функция, чтобы создать дайджест. Обратите внимание, что хэш-функция непосредственно не применяется к сообщению, но вместо этого она получается из последовательного соединения М. и e1r mod p.S2 = r + d x S1 mod q. Обратите внимание, что эта часть - вычисление S2 - делается в арифметике по модулю q.М., S1 и S2.Верификация (проверка) сообщения. Приемник, например Боб, получает М., S1 и S2.
V = h (М | e1S2 e2-S1 mod p).S2 конгруэнтно V по модулю p, сообщение принято; иначе оно отклоняется.Пример 3.4
Вот тривиальный пример. Предположим, что мы выбираем q = 103 и p = 2267. Обратите внимание на то, что p = 22 x q + 1. Мы выбираем e0 = 2, которое является элементом в Z2267*. Тогда (p - 1) / q = 22, так что мы имеем e1 = 222 mod 2267 = 354.
Мы выбираем d = 30, тогда e2 = 35430 mod 2267 = 1206. Секретный ключ Алисы -теперь - (d), ее общедоступный ключ - (e1,e2,p,q).
Алиса хочет передать сообщение М. Она выбирает r = 11 и вычисляет er = 35411 = 630 mod 2267. Предположим, что сообщение - 1000, и конкатенация (последовательное соединение) означает 1000630. Также предположим, что хэширование этого значения дает дайджест h (1000630) = 200. Это означает S1 = 200. Алиса вычисляет S2 = r + d x S1 mod q = 11 + 1026 200 mod 103 = 11 + 24 = 35. Алиса передает сообщение М =1000, S1 = 200 и S2 = 35. Проверку оставляем как упражнение.
Подделка по
Похоже, что все атаки на S1 = h (М. | e1r(mod p)). Это означает, что хэш-функция применяется к комбинации сообщение и e1r, в которой r является секретным.
(рис 3.13) Общая идея схемы DSSВ процессе подписания две функции создают две подписи; в процессе проверки выход одной функции сравнивается с первой подписью для проверки. Это подобно p и q. Функции 1 и 3 используют оба модуля p и q, функция 2 - только q. Детали входов и функций коротко рассматриваются ниже.
Генерация ключей
Перед подписанием сообщения к любому объекту Алиса должна генерировать ключи и объявить общедоступные ключи.
p. между 512 и 1024 битами. Число битов в p должно быть кратно числу 64.q с таким условием, чтобы оно делилось на (p - 1).<Zp*, x > и <Zq* ,x > ; вторая - подгруппа первой.e1, такое, чтобы оно было q -тым корнем 1 по модулю p (e1p = 1 mod p). Она поступает так: выбирает элемент в Zp, e0, и вычисляет e1 = e0(p-1)/q mod p.d как секретный ключ и вычисляет e2 = e1d(e1, e2, p, q), ее секретный ключ - (d).Подписание и проверка
Рисунок 3.14 показывает схему DSS.
(рис 3.14) Схема DSSПодписание. Ниже показаны шаги подписания сообщения.
(1 <= r <= q). Обратите внимание, что хотя открытые и секретные ключи могут быть выбраны один раз и использоваться для того, чтобы подписать много сообщений, Алиса должна выбирать каждый раз новый r, когда она должна подписать новое сообщение.S1 = (e1 mod p) mod q. Обратите внимание: значение первой подписи не зависит от М (сообщения).h (M).S2 = (h(M) + dS1)r-1mod q. Обратите внимание, что вычисление S2 делается по модулю q.M, S1 и S2 Бобу.Проверка (верификация). Для проверки сообщения обычно применяются следующие шаги, когда получены М, S1 и S2.
S1 0 < S1 < q.S2 0 < S2 < q.М, применяя V = [(e1h(M)/S2 e2S1/S2) mod p] mod q.S конгруэнтен V, сообщение принимается; иначе - отклоняется.Пример 3.5
Алиса выбирает q = 101 и p = 8081. Алиса выбирает e0 = 3 и вычисляет e1 = e0(p-1)/q mod p = 6968. Алиса выбирает d = 61 в качестве секретного ключа и вычисляет e2 = e1d mod p = 2038. Теперь Алиса может передать сообщение Бобу. Предположим, что h (M) = 5000, и Алиса выбирает r = 61:
h(M) = 5000 r =61 S1 = (e1r mod p) mod q = 54 S2 = (h(M) + dS1)r-1 mod q = 40 S2-1 = 48 mod 101 V = [(69685000 x 48 x 203854 x 48 x 203854 x 48)mod 8081]mod 101 = 54
Поскольку Sj и V являются подходящими, Боб принимает сообщение.
Сравнение DSS и RSА
Вычисление DSS-подписи быстрее, чем вычисление подписей RSА, при использовании того же самого p.
Сравнение DSS и схемы Эль-Гамаля
DSS-подпись - меньше, чем подписи в q меньше, чем p.
Наша последняя схема -
В процессе подписания две функции и экстрактор (извлекающее устройство) создают две подписи; в процессе проверки (верификации) обрабатывают выход одной функции (после прохождения через экстрактор) и сравнивают ее с первой подписью для проверки. Функции f1 и f3 фактически создают точки на кривой. Первая создает новую точку для секретного ключа подписывающего лица. Вторая - новую точку из двух общедоступных ключей подписывающего лица. Каждый экстрактор извлекает первые координаты соответствующей точки в модульной арифметике. Детали входов и функций коротко обсуждаются далее.
(рис 3.15) Общая идея схемы DSSГенерация ключей
Генерация ключей осуществляется следующими шагами:
Ep (a,b)p.q, чтобы использовать для вычисления.d, целое число.e1(.,....)e2 (..,....) = d x e1 (......), другую точку на кривой.(a, b, p, q, e1, e2), ее секретный ключ - d.Подписание и проверка (верификация)
Рис. 3.16 показывает
(рис 3.16) Схема EDSSПодписание. Процесс подписания состоит главным образом из выбора секретного случайного числа, создания третьей точки на кривой, вычисления двух подписей и передачи сообщения и подписей.
r, между 1 и q - 1.P (U, v) = r x e1 (......).P (u, v), чтобы вычислить первую подпись S1 . Это означает S1 = u mod q.r и S1, чтобы вычислить вторую подпись S2 = (h (M) + d x S1) r-1 mod q,М, S1 и S2.Проверка (верификация).Процесс проверки состоит главным образом из восстановления третьей точки и подтверждения, что первая координата эквивалентна S1 по модулю q. Обратите внимание, что третья точка была создана подписывающим лицом, использующим секретное случайное число r. Верификатор не имеет этого значения. Ему нужно создать третью точку из S1 , и S2.
М, S1 и S2 для создания двух промежуточных результатов A и B:A = h(M)S2-1 mod q
B = S2-1S1 mod q
Затем Боб восстанавливает третью точку T(x,y) = A x e1( ... , ...) + B x e2( ... , ...)
T(x,y), чтобы проверить сообщение. Если x = S1 mod q, подпись принимается, иначе - отклоняется.В этой секции кратко обсуждаются варианты и приложения для цифровых подписей.
Ниже проводится краткое обсуждение некоторых вариантов и дополнений к главному понятию цифровых подписей. Для более четкого понимания читатель может посмотреть специальную литературу.
Подпись с указанием времени
Иногда подписанный документ должен иметь указание времени, чтобы препятствовать действиям противника. Это названо
Например, Алиса подписывает запрос своему банку (условно Бобу), выдать некоторую сумму денег Еве. Документ может быть перехвачен Евой, если на этом документе нет никакого указания времени.
Включение фактической даты и времени на документах может создать проблемы - несинхронизированные часы, отсутствие универсального времени. Одно решение состоит в том, чтобы использовать nonce (number only once - Nonce) - одноразовое случайное число, которое может быть использовано только однажды. Когда приемник получает документ с
Слепые подписи
Иногда мы имеем документ, который хотим подписать, не раскрывая содержание документа подписывающему лицу. Например, ученый хочет сообщить Бобу, что он, возможно, открыл очень важную теорию, которую необходимо подписать у обычного нотариуса. Он просит Алису передать это, не разрешая ей узнать содержание теории. Для этой цели Дэвид Чом (David Caum) разработал некоторые патентованные
Слепая подпись, основанная на схеме RSА. Опишем кратко b, и вычисляет слепое сообщение B = М. x be mod n, в котором e является открытым ключом Алисы и n - определенным модулем в схеме цифровой подписи RSА. Обратите внимание, что b иногда называется "маскирующим коэффициентом", который Боб передает Алисе.
Алиса подписывает маскированное сообщение, используя Sblind = Bd mod n, где d является секретным ключом Алисы. Обратите внимание, что Sb - подпись на слепой (маскированной) версии сообщения.
Боб просто использует мультипликативную инверсию его случайного числа b, чтобы отделить слепое сообщение от подписи. Подпись - S = Sb b-1 mod n. Мы можем доказать, что S - подпись на первоначальном сообщении, как это определено в
S - подпись, если Боб передал первоначальное сообщение, которое будет подписано Алисой.
Предотвращение мошенничества. При слепой подписи появляется опасность, что Боб, может дать Алисе подписать слепое сообщение, которое может навредить ей. Например, сообщение Боба могло быть документом, утверждающим, что Алиса передаст Бобу все свое имущество после ее смерти. Есть по крайней мере три способа предотвратить такой ущерб.
В дальнейшем в этой книге обсуждаются несколько приложений криптографии для сетевой безопасности. Большинство этих приложений непосредственно или косвенно требует использования открытых ключей. Чтобы использовать открытый ключ, человек должен доказать, что он законно владеет этим ключом. По этой причине была разработана идея сертификации и свидетельств сертификации (CA) (См. лекцию 4 и лекцию 5). Свидетельства (CA), чтобы быть признанными, должны быть подписаны. Цифровые подписи используются, чтобы обеспечить такое доказательство. Когда Алиса должна применить открытый ключ Боба, она пользуется свидетельством. Сертифицированные CA используют общедоступный ключ с секретным ключом и проверяемой подписью Алисы. Само свидетельство содержит общедоступный ключ Боба.
Сегодняшние протоколы, которое используют услуги CA, - это IPSec (лекция 8), SSL/TLS ( лекция 7) и S/MIME ( лекция 6). Протокол PGP поддерживает свидетельства, но они могут быть заменены соглашениями между людьми в сообществе.
Для более детального изучения положений, обсужденных в этой лекции, мы рекомендуем нижеследующие книги и сайты. Пункты, указанные в скобках, показаны в списке ссылок в конце книги.
[Sti06], [TW06] и [PHS03] подробно рассматривают цифровые подписи.
Нижеследующие сайты дают больше информации о темах, обсужденных в этой лекции.
p = 809, q = 751, и d = 23, вычислите общедоступный ключ e.Затем
M1 = 100. Получите подпись S1.М2 = 50. Получите подпись S2.М = M1 x М2 = 5000, то S = S1 x S2.p = 881 и d = 700, найдите значения e1 и e2. Выберите r = 17. Найдите значение S1 и S2, если М = 400.q = 83, p = 997 и d = 23, найдите значения для e1 и e2. Выберите r = 11. Если М
= 400 и h (400) = 100, найдите значение S1., S2 и V. Равно ли $$S_{1} \equiv V (mod \ p)$$?q = 59, p = 709 и d = 14, найдите значения для e1 и e2. Выберите r = 13. Найдите значение S1 и S2, если h (M) = 100. Проверьте подпись.S и размером n.S1 и S2 в зависимости от размера p.S1 и S2 в зависимости от размера p и q.S1 и S2 в зависимости от размера p и q.S2 = 0, то две подписи должны быть повторно вычислены, используя новый r. Какова причина этого?r, используемое подписывающим лицом? Возможно ли это в принципе? Объясните ваш ответ отдельно для схем Эль-Гамаля-Шнорра, DSS.n? Объясните ваш ответ отдельно для каждого протокола: Эль-Гамаля, Шнорра или DSS.p и q являются маленькими. Используйте p = 19 и q = 3.p мало. Используйте p = 19.p и q являются маленькими. Используйте p =29 и q = 7.p и q являются маленькими. Используйте p =29 и q = 7.r, может ли она подделать сообщение? Объясните.r, может ли она подделать сообщение? Объясните.r, может ли она подделать сообщение? Объясните.p, q, e1 и r в S1 и S2 в S2 делается по модулю p, а вычисление S2 делается по модулю p - 1.S1 делается по модулю p, а вычисление S2 делается по модулю q.S1 делается по модулю p и модулю q, а вычисление S2 делается только по модулю q.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.