Safe RSA variant?

[Nomen Nescio]

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.