Safuat Hamdy <[EMAIL PROTECTED]>:
> 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.
