[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
Re: Removing 1 modular exponentiation
Thus spake James Muir (jamuir@xxxxxxxxxxxxxxx):
> Mike Perry wrote:
> >Thus spake Watson Ladd (watsonbladd@xxxxxxxxx):
> >Well, one immediate problem is that b/k has to be an integer.. So b=rk
> >for some random r and b is thus not completely random.. To clarify the
> >effects of this, you should rewrite your protocol as follows from
> >Round 2 on:
>
> that's not really a problem. all computations are done in the group
> ZZ_p. 1/k really means the inverse of k modulo the order of g in ZZ_p.
> So b/k does not have to be an integer.
My abstract algebra is a bit rusty, but isn't finding this value as
hard as the DLP?
Problem is: (g^X)^k = g for some given k. Find X equivalent to 1/k.
Rewrite as (g^k)^X = g
Seems like you need to take the Discrete Log of both sides to get your
X=1/k value. This is hard.
Perhaps you are thinking that g^(b/k)=g^b*g^(1/k). But it doesn't, it
is (g^b)^(1/k).
If I'm wrong, please enlighten.
--
Mike Perry
Mad Computer Scientist
fscked.org evil labs