Removing 1 modular exponentiation
Watson Ladd
watsonbladd at gmail.com
Tue Feb 20 02:08:27 UTC 2007
Mike Perry wrote:
> Thus spake Mike Perry (mikepery at fscked.org):
>
>> Thus spake James Muir (jamuir at scs.carleton.ca):
>>
>>>> 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.
>>> Since we are working modulo p and we know that g is a generator of ZZ_p
>>> its order is p-1. So, to find X above you just need to solve:
>>>
>>> k*X == 1 (mod p-1)
>>>
>>> This can be done efficiently using the extended Euclidean Algorithm
>>> (provided that gcd(k,p-1)=1).
>> Doh! You're right. The kittens are saved! (For now)
>
> Oh wait, heh, this is an extra modular exponentiation hidden in the
> f^(b/k) step then. The kittens have been put in jeopardy for nothing! ;)
>
But f^(b/k) requires 1 exponentiation and 1 multiplication. So this does
save some work. The issue is that it is insecure.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 249 bytes
Desc: OpenPGP digital signature
URL: <http://lists.torproject.org/pipermail/tor-talk/attachments/20070219/ef1f9ff2/attachment.pgp>
More information about the tor-talk
mailing list