Генерация ключей
Генерация ключей в схеме цифровой подписи RSА точно такая же, как и генерация ключей в криптографической системе RSА (см.
“B. Стандарты и организации по стандартизации”
). Алиса выбирает два простых числа p и q и вычисляет n = p x q. Алиса вычисляет e, для общедоступного ключа и вычисляет d для частного ключа, такое, что d и публично объявляет n и e.
В схеме цифровой подписи RSA. dявляется частным;. eи. n- общедоступными.
Подписание и проверка
Рис 3.7 показывает схему цифровой подписи RSA.
Подписание. Алиса на основе сообщения создает подпись, используя частный (секретный) ключ, S = Md mod n, и передает сообщение и подпись Бобу.
Проверка. Боб получает М и S. Он применяет общедоступный ключ Алисы к подписи, чтобы создать копию сообщения М’ = Se mod n. Боб сравнивает значение М’ со значением М.
Последняя конгруэнтность справедлива, потому что
“A. ASCII”
).
Пример 3.1
Для безопасности подписи значения p и q должны быть очень большими. Как тривиальный пример, предположим, что Алиса выбирает p = 823 и q = 953 и вычисляет n = 784319. Значение 782544. Теперь она выбирает e = 313 и вычисляет d = 160009. В этой точке генерация ключей закончена. Теперь вообразим, что Алиса хочет передать сообщение со значением M = 19070 Бобу. Она использует свой частный ключ 160009 для того, чтобы подписать сообщение:
Алиса передает сообщение и подпись Бобу. Боб получает сообщение и подпись. Он вычисляет
Боб принимает сообщение, потому что он проверил подпись Алисы.
Атаки подписи RSA
Есть некоторые атаки, к которым Ева может обратиться для подделки схемы цифровой подписи RSА Алисы.
Атака только на ключ. Ева имеет доступ только к открытому ключу Алисы, перехватывает пару ( М, S ) и пробует создать другое сообщение М.’, такое, что М’ = Se mod n.
Эта проблема по сложности решения равна проблеме дискретного логарифма, которую мы рассмотрели в
“A. ASCII”
. Это – экзистенциальная подделка и обычно бесполезна для Евы.
Атака при известном сообщении. Здесь Ева использует мультипликативное свойство RSА. Предположим, что Ева перехватила две пары подписи сообщения – (M1, S1) и (M2, S2), которые используют один и тот же секретный ключ.
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 – подпись Алисы на сообщении М.
Эта атака, которая называется иногда мультипликативной атакой,
проводится очень просто. Однако это – экзистенциальная подделка так, как сообщение, М является произведением двух предыдущих сообщений, созданных Алисой, а не Евой; сообщение М. обычно бесполезно.
Атака по выбранному сообщению. Эта атака также использует мультипликативное свойство RSA. Ева может так или иначе попросить, чтобы Алиса подписала два законных сообщения М1 и М2.
С помощью их она позже создает новое сообщение М. = M1 x M2. Ева может позже утверждать, что Алиса подписала M. Такую атаку называют так же, как и
предыдущую – мультипликативная атака.
Это очень серьезная атака схемы цифровой подписи RSA, потому что это – селективная подделка. (Ева может перемножать М1 и М2, чтобы получить полезный M ).
Подпись RSA на дайджесте сообщения
Как мы обсуждали прежде, подписание дайджеста сообщения и использование сильного алгоритма хэширования имеет несколько преимуществ. В случае RSA процессы подписания и проверки можно сделать намного быстрее, потому что схема цифровой подписи RSА – не что иное, как шифрование с секретным ключом и дешифрование с открытым ключом.
Алиса, подписывающее лицо, при первом использовании согласует
хэш-функцию, чтобы создать дайджест сообщенияD = h(M). Затем она подписывает дайджест, S = Dd mod n.
Сообщение и подпись передают Бобу. Боб, проверяющий, получает сообщение и подпись. Он сначала использует открытый ключ Алисы, чтобы извлечь (файл) дайджест, D’ = Se mod n. Затем он применяет хэш-алгоритм для того, чтобы получить сообщение D = h(M).
Боб теперь сравнивает эти два дайджеста, D и D’. Если они являются сравнимыми по модулю n, он принимает сообщение.
Атаки на подписанные дайджесты RSA
Насколько восприимчива схема цифровой подписи RSA к нападению, когда дайджест уже подписан?
Атака только на ключ. Мы можем иметь три случая этой атаки.
- Ева перехватывает пару (S, M) и пробует найти другое сообщение М’, которое создает тот же самый дайджест, h (M) = h (М’). Как мы узнали в
“Целостность сообщения и установление подлинности сообщения”
, если алгоритм хэшированияобладает устойчивостью ко второму прообразу,
эта атака очень трудна. - Ева находит два сообщения, М. и М’, такие, что h(M) = h(M’). Она соблазняет Алису подписать h(M), чтобы найти S ; теперь Ева имеет пару (М’, S), которое прошло подтверждающий тест, но это – подделка. Мы изучали в
“Целостность сообщения и установление подлинности сообщения”
, что если алгоритм хэшированияустойчив к коллизиям, эта атака очень трудна. - Ева случайным подбором может найти дайджест сообщения D, который может соответствовать случайной подписи S. Она тогда находит сообщение М, такое, что D = h (M). Как мы узнали в
“Целостность сообщения и установление подлинности сообщения”
, если хэш-функция устойчива к прообразу, эта атака очень трудно осуществима.
Атака при известном сообщении. Предположим, что Ева имеет две пары подписи сообщения – (М1,S1) и (М2, S2), которые были созданы с использованием одного и того же секретного ключа.
Ева вычисляет S = S1 x S2. Если она сможет найти сообщение М, такое, что h(M) = h(M1) x h(M2), она сможет подделать новое сообщение.
Атаки по выбранному сообщению. Ева может попросить, чтобы Алиса подписала два законных сообщения – М1,и М2 для нее. Она может создать новую подпись S = S1 x S2.
Так как Ева может вычислить h(M) = h(M1) x h(M2), если она может найти сообщение M данному h (M), это новое сообщение – подделка. Однако нахождение М по данному h (M) -очень трудный процесс, если алгоритм хэшированияустойчив к прообразу.
Когда дайджест подписан непосредственно вместо сообщения, восприимчивость. схемы цифровой подписи RSAзависят от свойств алгоритма хэширования.
Математические понятия
Преимущество подхода на основе эллиптических кривых в сравнении с задачей факторизации числа, используемой в RSA, или задачей целочисленного логарифмирования, применяемой в алгоритме Диффи-Хеллмана и в DSS, заключается в том, что в данном случае обеспечивается эквивалентная защита при меньшей длине ключа.
В общем случае уравнение эллиптической кривой Е имеет вид:
y2 axy by = x3 cx2 dx e
В качестве примера рассмотрим эллиптическую кривую Е, уравнение которой имеет вид:
На этой кривой лежат только четыре точки, координаты которых являются целыми числами. Это точки
А (0, 0), В (1, -1), С (1, 0) и D (0, -1)
Для определения операции сложения для точек на эллиптической кривой сделаем следующие предположения:
Введем следующие правила сложения точек на эллиптической кривой:
Следовательно,
Если прямая является касательной к кривой в какой-либо из точек P или Q, то в этом случае следует положить S = P или S = Q соответственно.
Введенная таким образом операция сложения подчиняется всем обычным правилам сложения, в частности коммутативному и ассоциативному законам. Умножение точки Рэллиптической кривой на положительное число k определяется как сумма k точек Р.
В криптографии с использованием эллиптических кривых все значения вычисляются по модулю р, где р является простым числом. Элементами данной эллиптической кривой являются пары неотрицательных целых чисел, которые меньше р и удовлетворяют частному виду эллиптической кривой:
Такую кривую будем обозначать Ep (a,b). При этом числа а и b должны быть меньше р и должны удовлетворять условию эллиптической кривой вычисляется следующим образом.
- Для каждого такого значения х, что 0 <= х <= р, вычисляется x3 ax b (mod p).
- Для каждого из полученных на предыдущем шаге значений выясняется, имеет ли это значение квадратный корень по модулю р. Если нет, то в Ep (a,b) нет точек с этим значением х. Если корень существует, имеется два значения y, соответствующих операции извлечения квадратного корня (исключением является случай, когда единственным значением оказывается y = 0 ). Эти значения (x,y) и будут точками Ep (a,b).
Множество точек Ep (a,b) обладает следующими свойствами:
- Р 0 = Р
- Если Р = (x,y), то Р (x,-y) = 0. Точка (x,-y) является отрицательным значением точки Р и обозначается -Р. Заметим, что (x,-y) лежит на эллиптической кривой и принадлежит Ep (a,b).
- Если Р = (x1,y1) и Q = (x2,y2), где , то P Q = (x3,y3) определяется по следующим формулам:
где
Число P = (x1, y1) и Q = (x2, y2). При P = Q секущая превращается в касательную, чем и объясняется наличие двух формул для вычисления
Задача, которую должен решить в этом случае атакующий, есть своего рода задача “дискретного логарифмирования на эллиптической кривой”, и формулируется она следующим образом. Даны точки P и Q на эллиптической кривой Ep (a,b). Необходимо найти коэффициент k < p такой, что
P = k x Q
Относительно легко вычислить P по данным k и Q, но довольно трудно вычислить k, зная P и Q.
Рассмотрим три способа использования эллиптических кривых в криптографии.
Стандарт цифровой подписи (dss)
Стандарт цифровой подписи (DSS – Digital Signature Standard) был принят национальным Институтом Стандартов и Технологии (NIST) в 1994 г. NIST издал DSS как FIPS-186 (FEDERAL INFORMATION PROCESSING STANDARD 186).
DSS применяет алгоритм цифровой подписи (DSA), основанный на схеме Эль-Гамаля, с использованием некоторых идей из схемы Шнорра. DSS критиковался со времени его издания.
В процессе подписания две функции создают две подписи; в процессе проверки выход одной функции сравнивается с первой подписью для проверки. Это подобно схеме Шнорра, но входы различны. Другое отличие: эта схема использует дайджест сообщения (не само сообщение) как часть входов к функциям 1 и 3.
Интересно то, что схема применяет два общедоступных модуля: p и q. Функции 1 и 3 используют оба модуля p и q, функция 2 – только q. Детали входов и функций коротко рассматриваются ниже.
Генерация ключей
Перед подписанием сообщения к любому объекту Алиса должна генерировать ключи и объявить общедоступные ключи.
- Алиса выбирает простое число длиной p. между 512 и 1024 битами. Число битов в p должно быть кратно числу 64.
- Алиса выбирает простое число на 160 битов 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.
Подписание. Ниже показаны шаги подписания сообщения.
- Алиса выбирает случайное число (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:
Поскольку Sj и V являются подходящими, Боб принимает сообщение.
Сравнение DSS и RSА
Вычисление DSS-подписи быстрее, чем вычисление подписей RSА, при использовании того же самого p.
Сравнение DSS и схемы Эль-Гамаля
DSS-подпись – меньше, чем подписи в схеме Эль-Гамаля, потому что q меньше, чем p.
Схема цифровой подписи шнорра
Проблема схемы цифровой подписи Эль-Гамаля – в том, что p должно быть очень большим, чтобы сделать трудной проблему дискретного логарифмаZp*.
Рекомендуется длина p по крайней мере 1024 битов. Можно сделать подпись размером 2048 бит. Чтобы уменьшить размер подписи, Шнорр предложил новую схему, основанную на схеме Эль-Гамаля , но с уменьшенным размером подписи.
рис. 3.11 дает общую идею схемы цифровой подписи Шнорра.
В процессе подписания две функции создают две подписи; в процессе проверки выход одной функции сравнивается с первой подписью для проверки.
рис. 3.11 показывает входы к каждой функции. Важно то, что схема использует два модуля: p и q.
Генерация ключей
Перед подписанием сообщения Алиса должна генерировать ключи и объявить всем общедоступные ключи.
- Алиса выбирает простое число p, которое обычно равно по длине 1024 битам.
- Алиса выбирает другое простое число q, которое имеет тот же самый размер, что и дайджест, созданный функцией криптографического хэширования (в настоящее время 160 битов, но это может измениться в будущем). Простое число q должно делиться на (p – 1). Другими словами, (p – 1) = 0 mod q.
- Алиса выбирает e1, q -тый
корень которого был бы равен 1 mod p. Чтобы сделать это, Алиса выбирает примитивный элемент в Zp, e0(см.
“G. Список неприводимых и примитивных полиномов”
) и вычисляет e1 = e0(p-1)/q mod p. - Алиса выбирает целое число, d, как свой секретный ключ.
- Алиса вычисляет e2 = e1d mod p.
- Общедоступный ключ Алисы – (e1, e2, p, q), ее секретный ключ – (d).
В схеме цифровой подписи Шнорраобщедоступный ключ Алисы – (e1, e2, p, q) ; ее секретный ключ – (d).
Подписание и проверка
Рисунок 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*.
Мы выбираем 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.
Подделка по схеме подписи Шнорра
Похоже, что все атаки на схему Эль-Гамаля могут быть применены к схеме Шнорра. Однако схема Шнорра находится в лучшем положении, потому что S1 = h (М.
Схема цифровой подписи эллиптической кривой
Наша последняя схема – схема цифровой подписи эллиптической кривой(ECDSS – Elliptic Curve Digital Signature Scheme), которая основана на применении эллиптических кривых, – их мы обсуждали в
“B.
В процессе подписания две функции и экстрактор (извлекающее устройство) создают две подписи; в процессе проверки (верификации) обрабатывают выход одной функции (после прохождения через экстрактор) и сравнивают ее с первой подписью для проверки. Функции f1 и f3 фактически создают точки на кривой.
Первая создает новую точку для секретного ключа подписывающего лица. Вторая – новую точку из двух общедоступных ключей подписывающего лица. Каждый экстрактор извлекает первые координаты соответствующей точки в модульной арифметике. Детали входов и функций коротко обсуждаются далее.
Генерация ключей
Генерация ключей осуществляется следующими шагами:
- Алиса выбирает эллиптическую кривуюEp (a,b) с
простым числом p. - Алиса выбирает другое простое число q, чтобы использовать для вычисления.
- Алиса выбирает секретный ключ d, целое число.
- Алиса выбирает точку на кривой e1(.,….)
- Алиса вычисляет e2 (..,….) = d x e1 (……), другую точку на кривой.
- Общедоступный ключ Алисы – (a, b, p, q, e1, e2), ее секретный ключ – d.
Подписание и проверка (верификация)
Рис. 3.16 показывает схему цифровой подписи эллиптической кривой.
Подписание. Процесс подписания состоит главным образом из выбора секретного случайного числа, создания третьей точки на кривой, вычисления двух подписей и передачи сообщения и подписей.
- Алиса выбирает секретное случайное число, 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 для создания двух промежуточных результатов 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, подпись принимается, иначе – отклоняется.
Схема цифровой подписи эль-гамаля
Криптосистема Эль-Гамаля была обсуждена в
“B. Стандарты и организации по стандартизации”
. Схема цифровой подписи Эль-Гамаля использует те же самые ключи, но алгоритм различен.
рис. 3.9 дает общую идею схемы цифровой подписи Эль-Гамаля.
В процессе подписания две функции создают две подписи. На стороне подтверждения обрабатывают выходы двух функций и сравнивают между собой для проверки. Обратите внимание, что одна и та же функция применяется и для подписания, и для проверки, но использует различные входы.
Рисунок показывает входы каждой функции. Сообщение – часть входа, для обеспечения функционирования при подписании; оно же – часть входа к функции 1 при подтверждении. Обратите внимание, что вычисления в функциях 1 и 3 проводятся по модулю p, а функции 2 – по модулю p – 1.
Генерация ключей
Процедура генерации ключей здесь точно такая же, как та, которая используется в криптографической системе. Выберем достаточно большое простое число p, чтобы в поле Z p* проблема дискретного логарифма была достаточно трудной.
Пусть e1 – простой элемент в Z p*. Алиса выбирает свой секретный ключ d, чтобы он был меньше, чем p – 1. Она вычисляет e2 = e1d.
Всхеме цифровой подписи Эль-Гамаля(e1, e2, p)- открытый ключ Алисы; d-секретный ключ Алисы.
Подтверждение и проверка
Рисунок 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:
Мы имеем
Поскольку e1 – первообразный корень, может быть доказано, что вышеупомянутое сравнение справедливо тогда и только тогда, когда , и результат сравнения есть тот же самый S2, с которого мы начали процесс подписания.
Пример 3.2
Ниже приводится тривиальный пример. Алиса выбрала p = 3119, e1 = 2, d = 127 и вычислила e2 = 2127 mod 3119 = 1702.
Она выбрала r равным 307. Она объявила e1, e2 и p ; она сохранила в тайне d. Далее показано, как Алиса может подписать сообщение.
Алиса передает М, S1 и S2 Бобу. Боб использует открытый ключ, чтобы вычислить, что сообщение подписано Алисой, потому что никто, кроме Алисы, не имеет секретного ключа d.
Поскольку V1 и V2 являются конгруэнтными, Боб принимает сообщение, и он предполагает, что сообщение было подписано Алисой, потому что никто, кроме нее, не имеет секретного ключа Алисы d.
Пример 3.3
Теперь вообразите, что Алиса хочет передать другое сообщение, М = 3000, Тэду. Она выбирает новое r = 107. Алиса передает М., S1 и S2 Тэду.
Поскольку V1 и V2 являются конгруэнтными, Тэд принимает сообщение; он предполагает, что сообщение подписано Алисой, потому что никто, кроме нее, не имеет секретного ключа Алисы d.
Подделка цифровой подписи в схеме Эль-Гамаля
Схема цифровой подписи Эль-Гамаля уязвима к экзистенциальной подделке, но селективную подделку на этой схеме сделать очень трудно.
Подделка только ключа. В этом типе подделки Ева имеет доступ только к открытому ключу. Возможны два варианта:
- Ева имеет заранее заданное сообщение М. Она должна подделать подпись Алисы на этом сообщении. Ева должна найти две правильных подписи S1 и S2 для этого сообщения. Это – селективная подделка.
- Ева может методом случайного подбора найти три значения, М, S1 и S2, такие, что подпись первого используется для второго. Если Ева может найти два новых параметра x и y, такие, что М = xS2 mod (p – 1) и S1 = -y S2 mod (p – 1), то она может подделать сообщение, но серьезной выгоды не получит, поскольку это – экзистенциальная подделка.
Подделка при известном сообщении. Если Ева перехватила сообщение М и его две подписи S1 и S2, она может найти другое сообщение М’, с той же самой парой подписей S1 и S2. Однако обратите внимание, что это – экзистенциальная подделка, которая не помогает Еве.
Упражнения
- Используя схему RSA, при p = 809, q = 751, и d = 23, вычислите общедоступный ключ e.
Затем
- Используя схему Эль-Гамаля при 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. Равно ли ? - Используя схему DSS, при q = 59, p = 709 и d = 14, найдите значения для e1 и e2. Выберите r = 13. Найдите значение S1 и S2, если h (M) = 100. Проверьте подпись.
- Сделайте следующее:
- NIST-спецификация требует для DSS следующее: если значение S2 = 0, то две подписи должны быть повторно вычислены, используя новый r. Какова причина этого?
- Что случится, если Ева найдет значение r, используемое подписывающим лицом? Возможно ли это в принципе? Объясните ваш ответ отдельно для схем Эль-Гамаля-Шнорра, DSS.
- Что случится, если Алиса подпишет два сообщения, используя одно и то же значение n? Объясните ваш ответ отдельно для каждого протокола: Эль-Гамаля, Шнорра или DSS.
- Покажите пример уязвимости схемы RSA к селективной подделке, когда значения p и q являются маленькими. Используйте p = 19 и q = 3.
- Покажите пример уязвимости схемы Эль-Гамаля к селективной подделке, когда значение p мало. Используйте p = 19.
- Покажите пример уязвимости схемы Шнорра к селективной подделке, когда значения p и q являются маленькими. Используйте p =29 и q = 7.
- Покажите пример уязвимости DSS к селективной подделке, когда значения p и q являются маленькими. Используйте p =29 и q = 7.
- В схеме Эль-Гамаля, если Ева может найти значение r, может ли она подделать сообщение? Объясните.
- В схеме Шнорра, если Ева может найти значение r, может ли она подделать сообщение? Объясните.
- В DSS-схеме, если Ева может найти значение r, может ли она подделать сообщение? Объясните.
- Предположим, что значения p, q, e1 и r в схеме Шнорра – те же самые, что и соответствующие значения в DSS-схеме. Сравните значения S1 и S2 в схеме Шнорра с соответствующими значениями в DSS-схеме.
- Объясните, почему в схеме Эль-Гамаля вычисление S2 делается по модулю p, а вычисление S2 делается по модулю p – 1.
- Объясните, почему в схеме Шнорра вычисление S1 делается по модулю p, а вычисление S2 делается по модулю q.
- Объясните, почему в схеме DSS вычисление S1 делается по модулю p и модулю q, а вычисление S2 делается только по модулю q.
- В схеме Шнорра докажите правильность процесса проверки.
- В DSS-схеме докажите правильность процесса проверки.
- В схеме цифровой подписи эллиптической кривой докажите правильность процесса проверки.
- Напишите два алгоритма для схемы RSА: один для процесса подписания и один для процесса проверки.
- Напишите два алгоритма для схемы Эль-Гамаля: один для процесса подписания и один для процесса проверки.
- Напишите два алгоритма для схемы Шнорра: один для процесса подписания и один для процесса проверки.
- Напишите два алгоритма для DSS-схемы: один для процесса подписания и один для процесса проверки.
- Напишите два алгоритма для схемы эллиптической кривой: один для процесса подписания и один для процесса проверки.