Mike Perry wrote: > Thus spake Mike Perry (mikepery@xxxxxxxxxx): > >> Thus spake James Muir (jamuir@xxxxxxxxxxxxxxx): >> >>>> 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.
Attachment:
signature.asc
Description: OpenPGP digital signature