How to create a RSA private key from raw data?

[Chris]

I'm having a bit of trouble creating and using RSA keys from raw data.

I have the public exponent(e), public modulus(n), and private modulus(d).

Encryption seems to work (don't know for sure):

RSA* rsa = RSA_new();
rsa->e = BN_bin2bn(pubexp, pubexp_len, rsa->e);
rsa->n = BN_bin2bn(pubmod, pubmod_len, rsa->n);
result = RSA_public_encrypt(data_len, data, out, rsa,
RSA_PKCS1_PADDING);

No errors at least.

Decryption seg faults without e and is incorrect with e:

RSA* rsa = RSA_new();
rsa->e = BN_bin2bn(pubexp, pubexp_len, rsa->e);
rsa->n = BN_bin2bn(pubmod, pubmod_len, rsa->n);
rsa->d = BN_bin2bn(prvmod, prvmod_len, rsa->d);
result = RSA_private_decrypt(data_len, data, out, rsa,
RSA_PKCS1_PADDING);

Seems strange to seg fault, doesn't it know something is missing/incorrect?
Does RSA_new not initialize the structure to a clean state? Wouldn't an
error be appropriate here?

I assume it's missing some information about the private key. I couldn't
find an "RSA key from raw data" type function though the docs say don't
manipulate the internals directly (but give no alternative). The docs says
p, q, dmp1, dmq1, and iqmp are unnecessary, correct?

Thanks for any pointers.

[Chris]

<snip>
Seems strange to seg fault, doesn't it know something is
missing/incorrect? Does RSA_new not initialize the structure to a clean
state? Wouldn't an error be appropriate here?

OK, I worked this out. It was the public exponent requirement that was
throwing me off.

After tracing this I see it's some call to BLINDING_HELPER() (rsa_eay.c line
466 of ossl 0.9.7i) that needs the public exponent and is causing the seg
fault. AFAIK the rest of the algorithm does not need the public exponent...
Not too big a deal to keep that in there but seems unnecessary. Hmmm.

Is the public exponent really necessary for decryption? It has been a while
since I looked at the RSA algorithm.

[Dr. Stephen Henson]

Post by Chris

<snip>
Seems strange to seg fault, doesn't it know something is
missing/incorrect? Does RSA_new not initialize the structure to a clean
state? Wouldn't an error be appropriate here?

OK, I worked this out. It was the public exponent requirement that was
throwing me off.
After tracing this I see it's some call to BLINDING_HELPER() (rsa_eay.c line
466 of ossl 0.9.7i) that needs the public exponent and is causing the seg
fault. AFAIK the rest of the algorithm does not need the public exponent...
Not too big a deal to keep that in there but seems unnecessary. Hmmm.
Is the public exponent really necessary for decryption? It has been a while
since I looked at the RSA algorithm.

There are security issues associated with RSA private key operations which are
handled by OpenSSL trying the reverse operation using a public key which
requires the public exponent.

While this is particularly the case when all CRT components are present there
are some lesser ones when just the private exponent is used.

In any case it is a good idea to use or recalculate the CRT components because
RSA is much quicker when they are present.

Steve.
--
Dr Stephen N. Henson. Email, S/MIME and PGP keys: see homepage
OpenSSL project core developer and freelance consultant.
Funding needed! Details on homepage.
Homepage: http://www.drh-consultancy.demon.co.uk
______________________________________________________________________
OpenSSL Project http://www.openssl.org
User Support Mailing List openssl-users-MCmKBN63+***@public.gmane.org
Automated List Manager majordomo-MCmKBN63+***@public.gmane.org

[Chris]

Post by Dr. Stephen Henson
There are security issues associated with RSA private key operations which are
handled by OpenSSL trying the reverse operation using a public key which
requires the public exponent.
While this is particularly the case when all CRT components are present there
are some lesser ones when just the private exponent is used.
In any case it is a good idea to use or recalculate the CRT components because
RSA is much quicker when they are present.

Thanks. I knew the blinding was in there but I was not sure how it was
implemented.

In my tests I found using the CRT components speed it up about 3x. With my
application being a desktop app, full blown RSA operations are relatively
few and far between so the simplicity of managing just the private exponent
is a worthwhile trade-off. Considering even a lowly 266 Mhz laptop can
still do more than twelve 1024-bit operations per second, that is plenty
fast.

Thanks again.

[Dr. Stephen Henson]

Post by Chris

Post by Dr. Stephen Henson
There are security issues associated with RSA private key operations which are
handled by OpenSSL trying the reverse operation using a public key which
requires the public exponent.
While this is particularly the case when all CRT components are present there
are some lesser ones when just the private exponent is used.
In any case it is a good idea to use or recalculate the CRT components because
RSA is much quicker when they are present.

Thanks. I knew the blinding was in there but I was not sure how it was
implemented.

Actually cwitthat isn't blinding I was referring to. It is protection against a
well known attack where if an RSA private key operation calculation fails and
the invalid data is visible (for example an invalid signature) the private key
can be leaked. For CRT a single error is sufficient.

Steve.
--
Dr Stephen N. Henson. Email, S/MIME and PGP keys: see homepage
OpenSSL project core developer and freelance consultant.
Funding needed! Details on homepage.
Homepage: http://www.drh-consultancy.demon.co.uk
______________________________________________________________________
OpenSSL Project http://www.openssl.org
User Support Mailing List openssl-users-MCmKBN63+***@public.gmane.org
Automated List Manager majordomo-MCmKBN63+***@public.gmane.org

[Kyle Hamilton]

(please forgive me for the messiness of this email.)

* Dr. Henson: When OpenSSL encrypts the private key, does it encrypt
the public key and exponent as well, or just the private part of the
key? if it encrypts the pubkey and exp as well, is this to verify the
proper private key when it's loaded?

Chris, the short answer is: no, RSA decryption does not require the
public exponent. However, there's a couple of caveats that apply with
OpenSSL due to design decisions.

Also: nothing should ever cause a SEGV, so this is a bug. (Security
against DoS depends on always checking your parameters, no matter what
you think the source is going to be. ;) )

e and n are the public key, d is the private key, and the primes that
generated them should be discarded.

(more detail:

choose 2 primes that are not equal to each other but are of equal
length to each other, p and q. Let n = (p*q).
Compute the totient of p*q (that is, ((p-1)*(q-1))), and randomly
generate a key e such that 1 < e < (p-1)(q-1) AND e is relatively
prime to that totient.

Compute decryption key d such that
e*d = 1 (mod ((p-1)*(q-1))

e and n make up the public key.
d makes up the private key.)

Encryption occurs on blocks of size < n, and I'm going to assume just
a single block here (cuz it's easier):

ciphertext = exp(message,e) % n;
message = exp(ciphertext,d) % n;

Theoretically, there should be no need for e during decryption.

However, in OpenSSL the assumption has been made that the public key
can always be extracted from the private key file, since the keys that
it generates are stored such.

* reference material provided by Applied Cryptography 2nd Edition,
Schneier 1996 and http://en.wikipedia.org/wiki/RSA

-Kyle H

<snip>
Seems strange to seg fault, doesn't it know something is

missing/incorrect? Does RSA_new not initialize the structure to a clean
state? Wouldn't an error be appropriate here?
OK, I worked this out. It was the public exponent requirement that was
throwing me off.
After tracing this I see it's some call to BLINDING_HELPER() (rsa_eay.c
line 466 of ossl 0.9.7i) that needs the public exponent and is causing the
seg fault. AFAIK the rest of the algorithm does not need the public
exponent... Not too big a deal to keep that in there but seems unnecessary.
Hmmm.
Is the public exponent really necessary for decryption? It has been a
while since I looked at the RSA algorithm.

______________________________________________________________________
OpenSSL Project http://www.openssl.org
User Support Mailing List openssl-users-MCmKBN63+***@public.gmane.org
Automated List Manager majordomo-MCmKBN63+***@public.gmane.org

[Dr. Stephen Henson]

Post by Kyle Hamilton
* Dr. Henson: When OpenSSL encrypts the private key, does it encrypt
the public key and exponent as well, or just the private part of the
key? if it encrypts the pubkey and exp as well, is this to verify the
proper private key when it's loaded?

It encrypts a PKCS#1 RSAPrivateKeyInfo structure in all the existing encrypted
private key formats. That includes all components including n,e.

Post by Kyle Hamilton
Chris, the short answer is: no, RSA decryption does not require the
public exponent. However, there's a couple of caveats that apply with
OpenSSL due to design decisions.

One of those design decisions is protection against error either due to a
hardware glitch or some obscure boundary case bug in the bignum code.

If such an error occurred and a bad private key operation data was output in
some cases it would leak data which could be used to reconstruct the private
key.

Steve.
--
Dr Stephen N. Henson. Email, S/MIME and PGP keys: see homepage
OpenSSL project core developer and freelance consultant.
Funding needed! Details on homepage.
Homepage: http://www.drh-consultancy.demon.co.uk
______________________________________________________________________
OpenSSL Project http://www.openssl.org
User Support Mailing List openssl-users-MCmKBN63+***@public.gmane.org
Automated List Manager majordomo-MCmKBN63+***@public.gmane.org

[Kyle Hamilton]

Which version of PKCS#1 does OpenSSL use? v1 had a problem in its
(lack of) padding that would allow private key leakage, at least
according to Wikipedia:

In 1998, Daniel Bleichenbacher described the first practical adaptive
chosen ciphertext attack, against RSA-encrypted messages using the
PKCS #1 v1 padding scheme (a padding scheme randomizes and adds
structure to an RSA-encrypted message, so it is possible to determine
whether a decrypted message is valid.) Due to flaws with the PKCS #1
scheme, Bleichenbacher was able to mount a practical attack against
RSA implementations of the Secure Socket Layer protocol, and to
recover session keys. As a result of this work, cryptographers now
recommend the use of provably secure padding schemes such as Optimal
Asymmetric Encryption Padding, and RSA Laboratories has released new
versions of PKCS #1 that are not vulnerable to these attacks.

(Wikipedia article RSA, heading 4.5 (Adaptive Chosen Ciphertext
Attacks), accessed 2006Feb23)

-Kyle H

Post by Dr. Stephen Henson

Post by Kyle Hamilton
* Dr. Henson: When OpenSSL encrypts the private key, does it encrypt
the public key and exponent as well, or just the private part of the
key? if it encrypts the pubkey and exp as well, is this to verify the
proper private key when it's loaded?

It encrypts a PKCS#1 RSAPrivateKeyInfo structure in all the existing encrypted
private key formats. That includes all components including n,e.

Post by Kyle Hamilton
Chris, the short answer is: no, RSA decryption does not require the
public exponent. However, there's a couple of caveats that apply with
OpenSSL due to design decisions.

One of those design decisions is protection against error either due to a
hardware glitch or some obscure boundary case bug in the bignum code.
If such an error occurred and a bad private key operation data was output in
some cases it would leak data which could be used to reconstruct the private
key.
Steve.
--
Dr Stephen N. Henson. Email, S/MIME and PGP keys: see homepage
OpenSSL project core developer and freelance consultant.
Funding needed! Details on homepage.
Homepage: http://www.drh-consultancy.demon.co.uk
______________________________________________________________________
OpenSSL Project http://www.openssl.org

______________________________________________________________________
OpenSSL Project http://www.openssl.org
User Support Mailing List openssl-users-MCmKBN63+***@public.gmane.org
Automated List Manager majordomo-MCmKBN63+***@public.gmane.org

[Dr. Stephen Henson]

Post by Kyle Hamilton
Which version of PKCS#1 does OpenSSL use? v1 had a problem in its
(lack of) padding that would allow private key leakage, at least
In 1998, Daniel Bleichenbacher described the first practical adaptive
chosen ciphertext attack, against RSA-encrypted messages using the
PKCS #1 v1 padding scheme (a padding scheme randomizes and adds
structure to an RSA-encrypted message, so it is possible to determine
whether a decrypted message is valid.) Due to flaws with the PKCS #1
scheme, Bleichenbacher was able to mount a practical attack against
RSA implementations of the Secure Socket Layer protocol, and to
recover session keys. As a result of this work, cryptographers now
recommend the use of provably secure padding schemes such as Optimal
Asymmetric Encryption Padding, and RSA Laboratories has released new
versions of PKCS #1 that are not vulnerable to these attacks.
(Wikipedia article RSA, heading 4.5 (Adaptive Chosen Ciphertext
Attacks), accessed 2006Feb23)

OpenSSL can use several PKCS#1 schemes.

The actual type referred to in that attack is RSAES-PKCS1-V1_5 and the attack
wont reveal the RSA private key in use rather individual session keys under
certain specific circumstances.

SSL/TLS uses that scheme in all its RSA key exchange ciphersuites so it
couldn't just be changed to OAEP. Instead various countermeasures have been
implemented in OpenSSL and other SSL/TLS libraries against that attack.

Steve.
--
Dr Stephen N. Henson. Email, S/MIME and PGP keys: see homepage
OpenSSL project core developer and freelance consultant.
Funding needed! Details on homepage.
Homepage: http://www.drh-consultancy.demon.co.uk
______________________________________________________________________
OpenSSL Project http://www.openssl.org
User Support Mailing List openssl-users-MCmKBN63+***@public.gmane.org
Automated List Manager majordomo-MCmKBN63+***@public.gmane.org