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