Re: Safe RSA variant?
Jason Holt writes: Trent generates primes p,q. He publishes n=pq and some random value g. Trent calculates a and a' such that aa' = 1 % (p-1)(q-1) and a' is prime. He sends Alice a' and g^a%n. a' is her secret exponent and g^a%n her public value. Another way to think of g^a is as the a'-th root of g, since (g^a)^a' = g mod n. If we instead use k instead of a', then Alice gets k and the kth root of g. Bob can establish a shared secret with Alice if Alice got a' from Trent. He picks a random r and sends her g^ar%n. She raises it to a' to compute the shared secret g^r%n. In my notion, she publishes her kth root of g, Bob raises it to the rth power, and Alice then raises it to the kth power to recover g^r. So the important questions are: * Given g^a%n and a', can Alice derive (p-1)(q-1)? If so, she'd be able to take over Trent's job. No, given g and the kth root of g, she clearly can't find phi(n), because every RSA signature supplies such a pair. * Given g^k%n and k' for lots of different k, can we derive (p-1)(q-1) or otherwise imitate Trent's ability to give out (g^k%n, k') pairs? I think this is OK too. See the Strong RSA Assumption, for example at http://www.zurich.ibm.com/security/ace/sig.pdf. Basically this says that you can't find kth roots mod an RSA modulus without knowing the factors. You might want to ask this on sci.crypt, they are pretty good with pure math questions like this one.
Safe RSA variant?
Well, I got such a good response from my last technical question that I'll try again :) If it's actually secure, it'll go really well with my credential system. Trent generates primes p,q. He publishes n=pq and some random value g. Trent calculates a and a' such that aa' = 1 % (p-1)(q-1) and a' is prime. He sends Alice a' and g^a%n. a' is her secret exponent and g^a%n her public value. Bob can establish a shared secret with Alice if Alice got a' from Trent. He picks a random r and sends her g^ar%n. She raises it to a' to compute the shared secret g^r%n. So the important questions are: * Given g^a%n and a', can Alice derive (p-1)(q-1)? If so, she'd be able to take over Trent's job. * Given g^k%n and k' for lots of different k, can we derive (p-1)(q-1) or otherwise imitate Trent's ability to give out (g^k%n, k') pairs? So IOW the goal is for Bob to be able to send Alice a message iff she knows a secret from Trent. And if Alice's secret is compromised, only messages sent to (or possibly from) Alice become vulnerable. A friend of mine pointed out that Alice can trivially compute another working pair of keys from her own: g^-a and -a'. And if the a' keys weren't prime, Alice and Bob could factor them and generate other keypairs. Both of those seem manageable, though. The common modulus attack in which you use g^k and g^k' to get information on g (which is public in this case) by calculating rk+sk'=1 caused me problems in earlier equations I tried, but doesn't seem to help the attacker here. -J
