Shamir's ID based signatures

Question

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)
}

Answer 1

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$

Yes, the key generation center can. Rewrite $g^e\equiv i \pmod n$ to $g\equiv i^{e^{-1}} \pmod n$,

then you have a way to compute $g$, since you can compute $e^{-1}$ using the knowledge of $\varphi(n)$ as you know that $e\cdot e^{-1}\equiv 1 \pmod{\varphi(n)}$ using extended Euclidean algorithm.

Another view of Shamirs IBS is to view $d:=e^{-1}$ and thus the master public key of the key generation center is $pk_m=(e,n)$ and the master private key is $sk_m(e,d,n)$. Observe, that this is an RSA key pair.

Now, you can view the key extraction for user with identity $i$ as issuing a textbook RSA signature by the authority holding $sk_m$, i.e., the key generation center computes the signature $g$ as $g\equiv i^d \pmod n$.

However, in contrast to a RSA signature, the signature value $g$ is only given to user $i$ and not made public. More precisely, the value $g$ is the user's secret signing key for Shamirs IBS. Note, that instead of $i$ one should actually use $H(i)$ for a suitable hash function $H:\{0,1\}^*\rightarrow Z_n$ to map the identity to an element to thwart existential forgeries.

Note, that this only concerns the key generation for the user's identities. So far, we have not yet talked about how user $i$ then generates a signature.

An identity based signature issued by user $i$ is essentially a non-interactive honest-verifier proof of knowledge of an $e$'th root modulo $n$, made non interactive using the Fiat-Shamir heuristic (by producing the challenge for the proof as hash of the initial commitment and the message to be signed). There are various other such IBS schemes based on this "generic compiler" which you can find here (in this article you also find a comprehensive description of Shamir's IBS scheme).

Apart from that, there are various other dedicated modern ID based signature schemes, but they all (AFAIK) require pairings on elliptic curve groups and so you may be fine with your choice if you do not have all that functionality available (or do not want to implement it on your own).

Answer 2

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.