Removing 1 modular exponentiation
Mike Perry
mikepery at fscked.org
Mon Feb 19 23:07:47 UTC 2007
Thus spake James Muir (jamuir at scs.carleton.ca):
> Mike Perry wrote:
> >Thus spake Watson Ladd (watsonbladd at gmail.com):
> >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
More information about the tor-talk
mailing list