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.