НОУ ИНТУИТ | Лекция | Хэш-функции и электронная подпись

Генерация ключей

Генерация ключей в схеме цифровой подписи RSА точно такая же, как и генерация ключей в криптографической системе RSА (см.

«B. Стандарты и организации по стандартизации»
). Алиса выбирает два простых числа p и q и вычисляет n = p x q. Алиса вычисляет varphi  (n) = (p - 1) (q - 1)e, для общедоступного ключа и вычисляет d для частного ключа, такое, что e x d = 1 mod varphi   (n)d и публично объявляет n и e.

В схеме цифровой подписи RSA. dявляется частным;. eи. n- общедоступными.

Подписание и проверка

Рис 3.7 показывает схему цифровой подписи RSA.

Подписание. Алиса на основе сообщения создает подпись, используя частный (секретный) ключ, S = Md mod n, и передает сообщение и подпись Бобу.

Проверка. Боб получает М и S. Он применяет общедоступный ключ Алисы к подписи, чтобы создать копию сообщения М’ = Se mod n. Боб сравнивает значение М’ со значением М.

Последняя конгруэнтность справедлива, потому что d x e = 1 mod  psi (n)
«A. ASCII»
).

Пример 3.1

Для безопасности подписи значения p и q должны быть очень большими. Как тривиальный пример, предположим, что Алиса выбирает p = 823 и q = 953 и вычисляет n = 784319. Значение varphi  (n)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 к нападению, когда дайджест уже подписан?

Атака только на ключ. Мы можем иметь три случая этой атаки.

  1. Ева перехватывает пару (S, M) и пробует найти другое сообщение М’, которое создает тот же самый дайджест, h (M) = h (М’). Как мы узнали в

    «Целостность сообщения и установление подлинности сообщения»
    , если алгоритм хэшированияобладает устойчивостью ко второму прообразу,
    эта атака очень трудна.
  2. Ева находит два сообщения, М. и М’, такие, что h(M) = h(M’). Она соблазняет Алису подписать h(M), чтобы найти S ; теперь Ева имеет пару (М’, S), которое прошло подтверждающий тест, но это — подделка. Мы изучали в

    «Целостность сообщения и установление подлинности сообщения»
    , что если алгоритм хэшированияустойчив к коллизиям, эта атака очень трудна.
  3. Ева случайным подбором может найти дайджест сообщения 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зависят от свойств алгоритма хэширования.

Упражнения

  1. Используя схему RSA, при p = 809, q = 751, и d = 23, вычислите общедоступный ключ e.

    Затем

  2. Используя схему Эль-Гамаля при p = 881 и d = 700, найдите значения e1 и e2. Выберите r = 17. Найдите значение S1 и S2, если М = 400.
  3. Используя схему Шнорра, при q = 83, p = 997 и d = 23, найдите значения для e1 и e2. Выберите r = 11. Если М
    = 400
    и h (400) = 100, найдите значение S1., S2 и V. Равно ли S_{1} equiv  V (mod  p)?
  4. Используя схему DSS, при q = 59, p = 709 и d = 14, найдите значения для e1 и e2. Выберите r = 13. Найдите значение S1 и S2, если h (M) = 100. Проверьте подпись.
  5. Сделайте следующее:
  6. NIST-спецификация требует для DSS следующее: если значение S2 = 0, то две подписи должны быть повторно вычислены, используя новый r. Какова причина этого?
  7. Что случится, если Ева найдет значение r, используемое подписывающим лицом? Возможно ли это в принципе? Объясните ваш ответ отдельно для схем Эль-Гамаля-Шнорра, DSS.
  8. Что случится, если Алиса подпишет два сообщения, используя одно и то же значение n? Объясните ваш ответ отдельно для каждого протокола: Эль-Гамаля, Шнорра или DSS.
  9. Покажите пример уязвимости схемы RSA к селективной подделке, когда значения p и q являются маленькими. Используйте p = 19 и q = 3.
  10. Покажите пример уязвимости схемы Эль-Гамаля к селективной подделке, когда значение p мало. Используйте p = 19.
  11. Покажите пример уязвимости схемы Шнорра к селективной подделке, когда значения p и q являются маленькими. Используйте p =29 и q = 7.
  12. Покажите пример уязвимости DSS к селективной подделке, когда значения p и q являются маленькими. Используйте p =29 и q = 7.
  13. В схеме Эль-Гамаля, если Ева может найти значение r, может ли она подделать сообщение? Объясните.
  14. В схеме Шнорра, если Ева может найти значение r, может ли она подделать сообщение? Объясните.
  15. В DSS-схеме, если Ева может найти значение r, может ли она подделать сообщение? Объясните.
  16. Предположим, что значения p, q, e1 и r в схеме Шнорра — те же самые, что и соответствующие значения в DSS-схеме. Сравните значения S1 и S2 в схеме Шнорра с соответствующими значениями в DSS-схеме.
  17. Объясните, почему в схеме Эль-Гамаля вычисление S2 делается по модулю p, а вычисление S2 делается по модулю p — 1.
  18. Объясните, почему в схеме Шнорра вычисление S1 делается по модулю p, а вычисление S2 делается по модулю q.
  19. Объясните, почему в схеме DSS вычисление S1 делается по модулю p и модулю q, а вычисление S2 делается только по модулю q.
  20. В схеме Шнорра докажите правильность процесса проверки.
  21. В DSS-схеме докажите правильность процесса проверки.
  22. В схеме цифровой подписи эллиптической кривой докажите правильность процесса проверки.
  23. Напишите два алгоритма для схемы RSА: один для процесса подписания и один для процесса проверки.
  24. Напишите два алгоритма для схемы Эль-Гамаля: один для процесса подписания и один для процесса проверки.
  25. Напишите два алгоритма для схемы Шнорра: один для процесса подписания и один для процесса проверки.
  26. Напишите два алгоритма для DSS-схемы: один для процесса подписания и один для процесса проверки.
  27. Напишите два алгоритма для схемы эллиптической кривой: один для процесса подписания и один для процесса проверки.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Adblock
detector