Public & Private Key
Pink
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?
Tom St Denis
typically in RSA keygen one chooses a public exponent [say e=65537]
then finds primes such that the euler totient doesn't divide it. The
private exponent is then generated as the inverse of e modulo the
totient. From the private key [sans e] you can figure out e, but
given only the product and e you can't figure out d [so far the only
known approach for d > N^0.29 is factoring N].
Tom
Thomas Pornin
> 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
Harold Johanssen
> 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.
Thomas Pornin
> 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
unruh
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.
>
>
>
>
Giuliano Bertoletti
Hello,
In general the only requirement for an assymmetric cryptosystem is that
the private key cannot be derived from the public key. The opposite
might or might not be true depending on the PK system, but in general is
not important.
For example in RSA the opposite is true because private and public
exponents are equivalent in the sense that what one does is undone by
the other.
Then for convenience we choose small (and therefore easily guessable)
exponents we elect to be public but that's only to speed up encryption
and verification (two public operations).
Also, along with the private exponent you need also public data (i.e.
the modulus) to perform any meaningful operation (like signature and
decyption), so the idea is that public is public, private is private +
public. If you include all the public stuff in the private, you've the
advantage that you keep data in only one place and your system is
perfectly functional; at most you might have to ask a CA for resigning
your public key.
Finally there exist PK systems like HFE where the public key has to be
derived from the private.
Cheers,
Giulio.
Pink ha scritto: