Public & Private Key
in [Cryptography]
|
Prev: Workshop “Medical Imaging Systems” within EUROMEDIA 2010 – Announce & Call for Papers
Next: Diffie Hellman Question
From: Pink on 17 Dec 2009 09:34 Since the private key cannot be derived from the public key in a PKI, I always assumed that the reverse was also true. However, looking at the way openssl rsautl command line generates a keypair - seems to be a 2 step process. 1st step is a private key & the second step is generation of the public key from the private key, looks like my assumption may not be true or is that the first step in the openssl command line generates both & the second step just extracts the public key from the public-private key pair?
From: Thomas Pornin on 17 Dec 2009 10:25 According to Pink <pink(a)nvald.com>: > Since the private key cannot be derived from the public key in a PKI, I > always assumed that the reverse was also true. Well, you assumed wrong. More precisely, asymmetric cryptosystems can be conceived where the public key cannot be derived from the private key, but this is not a very useful property in practical usages and is not actively sought after. We want the private key to be unguessable from the public key precisely so that the public key can be made "public". We then assume that "everybody" knows the public key (that's what "public" means) which kind of voids any notion of making the public key unguessable. To have the public key unguessable from the private key, then it cannot be "public"; you would have two private keys, mathematically related to each other but distinct and not guessable from each other. Right now I do not see what use such a thing could have. > However, looking at the way openssl rsautl command line generates a > keypair - seems to be a 2 step process. 1st step is a private key & > the second step is generation of the public key from the private key, > looks like my assumption may not be true or is that the first step in > the openssl command line generates both & the second step just > extracts the public key from the public-private key pair? In RSA as defined by PKCS#1, the private key contains a number of fields, namely: n public modulus e public exponent d private exponent p first factor of n q second factor of n dp d reduced modulo p-1 dq d reduced modulo q-1 iq inverse of q modulo p n = p*q, d must be intertible modulo p-1 and q-1, e is a value which is inverse of d modulo p-1 and modulo q-1. e can be, and usually is, a very small value (e.g. e = 3), which considerably speeds up operations with the public key (asymmetric encryption, signature verification). The values of p, q, dp, dq and iq are not strictly necessary for private key operations (asymmetric decryption, signature generation) but they allow the use of CRT (aka "Chinese Remainder Theorem"), which then again speeds up such operations (by a factor of 4). Knowledge of e is not mathematically necessary for private key operations either, but it is handy to implement masking, which is a technique used for private key operations to prevent side-channel leakage of information about the private key (the private key is private, thus we do not want an external entity to be able to learn some information about it by accuractely timing the signature generation process; masking helps for that, and it uses the value of e). The public key is then the pair (n,e), i.e. a subset of the private key. The key generation step produces the complete private key, from which the public key is trivially extracted. Now it is possible to imagine a "kind of RSA" where the private key is (n,d) and the public key is (n,e). Provided that nobody knows the factors p and q, and that both e and d are "big" (about the same size as n), and that we ignore issues related to side-channel leakage, then we get a system where neither key can be guessed from the other. Of course, for this to make sense, both keys must be private (as I pointed out above, there is little point in making a public value unguessable). Of course, the key generation process must have, at some point, both keys and the other fields (including the p and q factors of n), so that the generation process looks like: 1. generate p and q, then n, e and d; 2. give (n,d) to one party and (n,e) to another; 3. forget about p and q. This can be done with specialized hardware, or through some advanced cryptographic techniques. Besides, such a kind-of-RSA would be slower since we would lack the optimization opportunities detailed above (e must be big to avoid being guessable, and CRT cannot be applied since nobody knows p and q). --Thomas Pornin
From: Harold Johanssen on 17 Dec 2009 11:02 On Thu, 17 Dec 2009 15:25:20 +0000, Thomas Pornin wrote: > In RSA as defined by PKCS#1, the private key contains a number of > fields, namely: > > n public modulus > e public exponent > d private exponent > p first factor of n > q second factor of n > dp d reduced modulo p-1 > dq d reduced modulo q-1 > iq inverse of q modulo p > > n = p*q, d must be intertible modulo p-1 and q-1, e is a value which is > inverse of d modulo p-1 and modulo q-1. e can be, and usually is, a very > small value (e.g. e = 3), which considerably speeds up operations with > the public key (asymmetric encryption, signature verification). The > values of p, q, dp, dq and iq are not strictly necessary for private key > operations (asymmetric decryption, signature generation) but they allow > the use of CRT (aka "Chinese Remainder Theorem"), which then again > speeds up such operations (by a factor of 4). Why did they include dp, dq and iq in the PKCS#1 document? After all, they are trivially derived from p, q and d.
From: Thomas Pornin on 17 Dec 2009 11:19 According to Harold Johanssen <noemail(a)please.net>: > Why did they include dp, dq and iq in the PKCS#1 document? After > all, they are trivially derived from p, q and d. That's not "trivial" when you are implementing it on some low-powered memory-starved embedded architecture. Plain RSA operations need neither modular reduction or modular inversion; these operations are not completely cheap in terms of code footprint and CPU time, when compared to a raw modular exponentiation. Now you are free to implement your own RSA key storage format; omitting dp, dq and iq can be thought of a kind of data compression system. --Thomas Pornin
From: unruh on 17 Dec 2009 13:08
On 2009-12-17, Pink <pink(a)nvald.com> wrote: > Since the private key cannot be derived from the public key in a PKI, I > always assumed that the reverse was also true. > However, looking at the way openssl rsautl command line generates a > keypair - seems to be a 2 step process. > 1st step is a private key & the second step is generation of the public key > from the private key, looks like my assumption may not be true or is that > the first step in the openssl command line generates both & the > second step just extracts the public key from the public-private key pair? Yes, your assumption is bad. the public key is easily derivable from the private-- or the crypto would be useless since thepublic key could not be generated without centuries of effort. The key is that the private key includes more info than the public. For example in RSA the private key includes the factors which makes it trivial to find the public key and the private exponent. > > > > |