[prev in list] [next in list] [prev in thread] [next in thread] 

List:       cryptography
Subject:    Re: ElGamal without exponent reduction?
From:       Bodo_Moeller () public ! uni-hamburg ! de (Bodo Moeller)
Date:       1999-06-24 19:40:16
[Download RAW message or body]

Safuat Hamdy <hamdy@cdc.Informatik.TU-Darmstadt.DE>:

> 	G: generator
> 	a: secret value
> 	A: public value G^a
> 
> and for the signature
> 
> 	k: secret random value
> 	R: G^k
> and
> 	s = a h(m) + k g(R)  mod n		(*)
> 
> where h is a hash-function, n is the group order, and g is a (public)
> mapping from the elements of the group to Z (the integers).  The signature
> is (s, R).
> 
> For the verification, check that
> 	G^s = A^h(m) R^g(R)
> holds.
> 
> Now suppose that the reduction  mod n in (*) is omitted.  Except that the
> size of s would be larger, can anybody see whether this would be harmful?

Each signature provides the attacker with an equation

     s_i  =  a * h_i  +  k_i * g_i

where  s_i, k_i,  and  g_i  are known.  At first sight, the number of
equations  k  will always be less than the number of unknowns
(a, h_1, ..., h_k),  but the attacker can reduce each equation modulo
g_i,  or modulo some factor  f_i  thereof, giving

     s_i  =  a * h_i   mod  f_i,

and thus (if  f_i  can be so chosen as to make  h_i  invertible)

     a  =  s_i / h_i   mod  f_i.

Obtain enough samples, use the Chinese Remainder Theorem, and you
have  a.

[prev in list] [next in list] [prev in thread] [next in thread]