Обсуждение:Схема Эль-Гамаля
Название[править код]
Может все же Алгоритм Эль-Гамаля или Шифр Эль-Гамаля --Insider 51 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