Обсуждение:Схема Эль-Гамаля

Название

Может все же Алгоритм Эль-Гамаля или Шифр Эль-Гамаля --Insider ⁵¹ 04:34, 11 июля 2007 (UTC)

Алгоритм

Кто-нибудь проверьте алгоритм и доказательство.

Кажется, баг "В схеме Эль-Гамаля необходимо использовать различные значения случайной величины ~k для шифровки различных сообщений ~M и ~M^'. Если использовать одинаковые ~k, то для соответствующих шифротекстов ~(a,b) и ~(a^',b^') выполняется соотношение ~b(b^')^{-1}=M(M^')^{-1}. Из этого выражения можно легко вычислить ~M^', если известно ~M."

С чего вдруг? Даже при одинаковых ключах (н.п (23, 7, 9), 4 и сообщениях 88, 63, мы получаем два шифротекста (21, 5) и (21, 19). Как не трудно догадаться отношение 5/19 ни разу не равно 88/63) 95.161.12.29 20:38, 20 июня 2013 (UTC)

Проверка подписи (не достаточна)

Проверка подписи должна начинаться с проверки условия: 0 < r < p, иначе возможно провести подделку подписи:

• 1. пусть имеется предыдущий подписанный (r,s) документ (его хеш-функция) h(M)
• 2. подделываем подпись документа h(M2)

 2.1. считаем вспомогательный множитель u из условия: u*h(M) = h(M2) mod (p-1)
 2.2. получаем новые s2, r2: 
      s2 = s*u mod (p-1),
      r2 = r*u mod (p-1), и также
      r2 = r mod p,
   из этого находим r2 по Китайской теореме об остатках (в немецкой Вики эта теорема более понятно описана)
      r2 = r*u*p - r*(p-1) mod p*(p-1)

• 3. для полученной подписи (r2, s2) документа h(M2) верно выражение: y^(r2) * r2^(s2) = g^(h(M2)) mod p
• 4. подпись подделана, не выполняется лишь условие 0 < r2 < p, так как при неравных хеш-функциях h(M) и h(M2) значение u не будет равно 1. 134.155.26.208 13:49, 31 января 2009 (UTC) jk

Добавил проверку границ значений. Maxal 15:26, 31 января 2009 (UTC)

вопрос по примеру расшифровки

Вычисляем M по формуле: M = b ( a x ) − 1 mod p = 9 ( 6 8 ) − 1 mod 11 = 5 {\displaystyle M=b(a^{x})^{-1}{\bmod {p}}=9(6^{8})^{-1}\mod {11}=5} {\displaystyle M=b(a^{x})^{-1}{\bmod {p}}=9(6^{8})^{-1}\mod {11}=5}

A^X = 6^8 = 1679616

b*a^x = 15116544

b*(a^x)^-1 = 5,35837E-06; 5,35837E-06 mod 11 = 5,35837E-06

5,35837E-06 <> 5