On 1/10/2013 12:13 PM, Tayade, Nilesh wrote:
-----Original Message-----
From: owner-openssl-us...@openssl.org [mailto:owner-openssl-
us...@openssl.org] On Behalf Of Jakob Bohm
Sent: Friday, December 21, 2012 8:23 PM
To: openssl-users@openssl.org
Subject: Re: RSA_private_decrypt function takes longer time.
On 12/21/2012 1:13 PM, Tayade, Nilesh wrote:
Hi,
I am using the RSA_private_decrypt() function in one of the custom
applications, where we expect the premaster to get decrypted faster.
[...]
The explanation is simple:
The cost of an RSA operation depends on the number of bits in the
exponent used (private or public). Choosing the private or public
exponent can speed up the operation with that exponent, but also
seriously reduces the number of "guesses" needed to figure out what
that chosen exponent is. So it is insecure to do so for the private
key, and the best one can do is to choose an easy exponent for the
public key (typically 0x10001=65537), which makes the public key
operation much faster than the private key operations, but doesn't
slow down the private key operation compared to using a random
number for the public exponent.
So the RSA private key operation (in *any* quality implementation) is
almost always much slower than the public key operation.
Some things that can speed up the private key operation without
compromising security:
Thanks Jakob.
- Make sure your stored private key includes the extra numbers to speed
up the calculation using the Chinese remainder theorem trick (OpenSSL
can work with or without them, but operating with them is faster.
There are mathematical formulas for converting a "d only" private key
to a Chinese remainder private key without having to generate new keys,
so it is a one time configuration task.
Coming back to this. I dumped the PEM key in text format, and it shows n, d,
dQ, dP, qInv, p and q.
Does that mean my private key is not just a 'd-only' key?
That means you have a key with all the extra numbers for "Chinese
Remaineder Theorem" based speedups. (n, e) is your public key.
(n, d) is your "d-only-cannot-get-the rest" private key. (n, d, e)
is your "d-only-can-figure-out-the-rest" private key. (n, d or e, p or
q) is your "enough-to-figure-out-the-rest" private key. (n, d, dQ, dP,
qIn, p, q) is your "all-the-details-already-there" private key.
So this is good, if you have a safe place to store all those numbers.
- To thwart timing attacks on RSA in network protocols, OpenSSL does
some extra "masking operations" before using a private key. You may be
able to coach OpenSSL into setting up a precomputed pool of masking
data structures before the incoming network requests arrive, thus
shaving some time off the response time, especially if the load is a
little uneven, rather than a sustained maximum-capacity test load.
I would appreciate any link or further pointers on this. I am not so familiar
with operations on RSA key.
There is some very deep math involved, which I don't completely
understand myself. But the short version is: Multiplying numbers with a
varying count of non-zero bits and a varying count of multiplications
wanted usually takes a different amount of time depending on those bits
and counts. Those bits and counts are your secret key, so it is very
bad if someone can figure it out by simply measuring how long it takes
to do the key exchange. To prevent that, OpenSSL does some extra
multiplications etc. with unrelated random numbers to make the total
time statistically unrelated to your secret key.
Enjoy
Jakob
--
Jakob Bohm, CIO, Partner, WiseMo A/S. http://www.wisemo.com
Transformervej 29, 2730 Herlev, Denmark. Direct +45 31 13 16 10
This public discussion message is non-binding and may contain errors.
WiseMo - Remote Service Management for PCs, Phones and Embedded
______________________________________________________________________
OpenSSL Project http://www.openssl.org
User Support Mailing List openssl-users@openssl.org
Automated List Manager majord...@openssl.org
