Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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)
}
share|improve this question
2  
I'd suggest removing your PS and asking that as a new question. –  mikeazo Jan 29 at 17:49
    
@Kwijibo: I think my comment may have been not clear enough. I also edited my answer to make that more clear. The public key for identity $i$ would be $H(i)$ and the private key $g$ for identity $i$ can be computed using getPrivateKey. However, note that issuing and verifying a signature with Shamir's IBE has nothing to do with RSA signature generation/verification. However, you can use the functionality provided by RSA to implement it. –  DrLecter Jan 30 at 11:42
    
Thanks for your comments. I edited my post to reflect your answer. So far this should be correct? Regarding verification and generation, I will have a sharp look at the paper, again. –  Kwyjibo Jan 30 at 11:56
    
@Kwyjibo so far thats ok (although $H$ should take the full range of $Z_n$). But that's the most straightforward part of the scheme ;) –  DrLecter Jan 30 at 14:08
    
Another try, implementing sign and verify as described in the paper. –  Kwyjibo Jan 30 at 16:35

2 Answers 2

up vote 0 down vote accepted

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

share|improve this answer
    
So you are claiming that an arbitrary RSA implementation can be "onverted" into an IBS scheme by setting $d = e^{-1}$, which I could simply extract with Java's mod inverse function. –  Kwyjibo Jan 30 at 8:43
    
Yes, if you have an RSA implementation, then you have all methods you need to implement Shamirs IBE. –  DrLecter Jan 30 at 8:47
    
What is Shamirs IBE? $\:$ (The OP's question is about identity-based signatures.) $\hspace{1.7 in}$ –  Ricky Demer Jan 31 at 10:24
    
@Ricky Demer that's a typo. Should be IBS –  DrLecter Jan 31 at 10:24

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.