How to create a RSA private key from raw data?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|

How to create a RSA private key from raw data?

Chris-35
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.

Reply | Threaded
Open this post in threaded view
|

Re: How to create a RSA private key from raw data?

Chris-35
On 2/22/06, Chris <[hidden email]> wrote:
Decryption seg faults without e and is incorrect with e:
<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.

Reply | Threaded
Open this post in threaded view
|

Re: How to create a RSA private key from raw data?

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

On 2/22/06, Chris <[hidden email]> wrote:

> On 2/22/06, Chris <[hidden email]> wrote:
> > Decryption seg faults without e and is incorrect with e:
> > <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                    [hidden email]
Automated List Manager                           [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: How to create a RSA private key from raw data?

Dr. Stephen Henson
In reply to this post by Chris-35
On Wed, Feb 22, 2006, Chris wrote:

> On 2/22/06, Chris <[hidden email]> wrote:
> >
> > Decryption seg faults without e and is incorrect with e:
> > <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                    [hidden email]
Automated List Manager                           [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: How to create a RSA private key from raw data?

Chris-35
On 2/23/06, Dr. Stephen Henson <[hidden email] > wrote:
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.
Reply | Threaded
Open this post in threaded view
|

Re: How to create a RSA private key from raw data?

Dr. Stephen Henson
On Thu, Feb 23, 2006, Chris wrote:

> On 2/23/06, Dr. Stephen Henson <[hidden email]> wrote:
> >
> > 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                    [hidden email]
Automated List Manager                           [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: How to create a RSA private key from raw data?

Dr. Stephen Henson
In reply to this post by Kyle Hamilton
On Wed, Feb 22, 2006, Kyle Hamilton wrote:

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

> 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                    [hidden email]
Automated List Manager                           [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: How to create a RSA private key from raw data?

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

On 2/23/06, Dr. Stephen Henson <[hidden email]> wrote:

> On Wed, Feb 22, 2006, Kyle Hamilton wrote:
>
> >
> > * 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.
>
> > 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                    [hidden email]
> Automated List Manager                           [hidden email]
>
______________________________________________________________________
OpenSSL Project                                 http://www.openssl.org
User Support Mailing List                    [hidden email]
Automated List Manager                           [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: How to create a RSA private key from raw data?

Dr. Stephen Henson
On Thu, Feb 23, 2006, Kyle Hamilton wrote:

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

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                    [hidden email]
Automated List Manager                           [hidden email]