Shamir's ID based signatures I am currently implementing Shamir's ID based signature algorithm as proposed in Adi Shamir, Identity-Based Cryptosystems and Signature Schemes. Advances in Cryptology: Proceedings of CRYPTO 84, Lecture Notes in Computer Science, 7:47--53, 1984.

However I am stuck with generating the private key for a certain identity. The paper states that "the only difference between users is the value of i, and the secret key which corresponds to i is the unique number g such that

$g^e = i (\mod n)$.

This g can easily be computed by the key generation center, but if the RSA scheme is secure, no one else can extract e-th roots mod n." Where:


$g$ is the private key belonging to $i$.
$i$ is the ID for which the private key is to be generated.
$n$ is the product of two large primes $p, q$. 
$e$ is a large prime which is relatively prime to $\phi(n)$


However, I am lacking the number theoretic background knowledge to derive the formula for the private key, given the knowledge of $p$, $q$, $\phi(n)$. I guess I have to apply Fermat's little theorem somehow. Please give me a hint for a solution.

PS: A question for the ID based crypto pros - do you recommend any more modern approaches? Shamir's paper the to be most suitable for my purpose and should be secure given a suitable bitlength is chosen.



Addendum: So concluding from DrLecter's answers, I have tried to map the needed functionality reusing as much as possible from an existing RSA implementation (RSA functionality denoted by *).


pk_i = (e, n) => public key of id i (i = m denotes master key)
sk_i = (d, n) => private key of id i (i = m denotes master key)
sig_mi = (s, t) => signature of message m signed by i
hash'(x) => hash function making full use of Z_n
hash''(x) => hash function with bitlength l such that 2^-l sufficiently small (e.g. SHA256)


Pseudocode:

//Generate private key sk_i for identity i
sk_i getPrivateKey(i, sk_m) {
    return sk_i(decrypt*(hash'(i), sk_m), sk_m.n) //hash' making use of full range of Z_n
}

//Receive public key pk_i for identity i
pk_i getPublicKey(i, pk_m) {
    return pk_i(hash'(i), pk_m.n) //hash' making use of full range of Z_n
}

//Sign a message with private key sk_i
sig_mi sign(message, sk_i) {
    r = rnd()
    t = r^e (mod sk_i.n)
    s = sk_i.d * r^hash''(t, message) (mod sk_i.n) //sk_i.d = g as generated by function getPublicKey
    return sig_mi(s,t)
}

//Verify a message with signature sig_mi
boolean verify(message, sig_mi, pk_m) {
    return (sig_mi.s^pk_m.e (mod n) == hash'(i)^pk_m.e * t^hash''(t, message) (mod n)) //hash'' with bitlength l such that 2^-l is sufficiently small (e.h. SHA256)
}
Compute $d$ such that $ed\equiv 1\bmod{\varphi(n)}$ using extended euclidean algorithm. Then compute $g = i^d\bmod{n}$.

This is basically RSA decryption.