

Hi,
I am using the RSA_private_decrypt() function in one of the custom applications, where we expect the premaster to get decrypted faster.
I tried looking at the time consumed by RSA_private_decrypt and loops involved in pseudorandom function to compute key.
It is seen that RSA_private_decrypt is taking almost 64 miliseconds to decrypt the premaster secret.
Did someone observe this? Is there some way I can enhance the performance (like cache some parameters etc.)?
My machine is:
Intel(R) Xeon(R) CPU E5440 @ 2.83GH with Linux2.6.22.

Thanks,
Nilesh
______________________________________________________________________
OpenSSL Project http://www.openssl.orgUser Support Mailing List [hidden email]
Automated List Manager [hidden email]


On 12/21/2012 01:13 PM, Tayade, Nilesh wrote:
> I am using the RSA_private_decrypt() function in one of the custom applications, where we expect the premaster to get decrypted faster.
> I tried looking at the time consumed by RSA_private_decrypt and loops involved in pseudorandom function to compute key.
> It is seen that RSA_private_decrypt is taking almost 64 miliseconds to decrypt the premaster secret.
> Did someone observe this? Is there some way I can enhance the performance (like cache some parameters etc.)?
Asymmetric cryptography tends to be expensive, especially with larger keys.
If the clients are cooperative, you could enable session resumption.
With that, only the first connection from each client would have to
perform the RSA operation, the subsequent TLS handshakes are much quicker.

Florian Weimer / Red Hat Product Security Team
______________________________________________________________________
OpenSSL Project http://www.openssl.orgUser Support Mailing List [hidden email]
Automated List Manager [hidden email]


> Original Message
> From: Florian Weimer [mailto: [hidden email]]
> Sent: Friday, December 21, 2012 5:58 PM
> To: [hidden email]
> Cc: Tayade, Nilesh
> Subject: Re: RSA_private_decrypt function takes longer time.
>
> On 12/21/2012 01:13 PM, Tayade, Nilesh wrote:
>
> > I am using the RSA_private_decrypt() function in one of the custom
> applications, where we expect the premaster to get decrypted faster.
> > I tried looking at the time consumed by RSA_private_decrypt and loops
> involved in pseudorandom function to compute key.
> > It is seen that RSA_private_decrypt is taking almost 64 miliseconds
> to decrypt the premaster secret.
> > Did someone observe this? Is there some way I can enhance the
> performance (like cache some parameters etc.)?
>
> Asymmetric cryptography tends to be expensive, especially with larger
> keys.
>
> If the clients are cooperative, you could enable session resumption.
> With that, only the first connection from each client would have to
> perform the RSA operation, the subsequent TLS handshakes are much
> quicker.
Thanks. Yes, the session resumption is enabled. But my goal is to evaluate the max concurrent sessions which could be handled.
So we are emulating many new SSL sessions being opened with single server.
> 
> Florian Weimer / Red Hat Product Security Team

Thanks,
Nilesh
______________________________________________________________________
OpenSSL Project http://www.openssl.orgUser Support Mailing List [hidden email]
Automated List Manager [hidden email]


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.
> I tried looking at the time consumed by RSA_private_decrypt and loops involved in pseudorandom function to compute key.
> It is seen that RSA_private_decrypt is taking almost 64 miliseconds to decrypt the premaster secret.
> Did someone observe this? Is there some way I can enhance the performance (like cache some parameters etc.)?
>
> My machine is:
> Intel(R) Xeon(R) CPU E5440 @ 2.83GH with Linux2.6.22.
>
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:
 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.
 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 maximumcapacity test load.
Enjoy
Jakob

Jakob Bohm, CIO, Partner, WiseMo A/S. http://www.wisemo.comTransformervej 29, 2730 Herlev, Denmark. Direct +45 31 13 16 10
This public discussion message is nonbinding and may contain errors.
WiseMo  Remote Service Management for PCs, Phones and Embedded
______________________________________________________________________
OpenSSL Project http://www.openssl.orgUser Support Mailing List [hidden email]
Automated List Manager [hidden email]


> Original Message
> From: [hidden email] [mailto:owneropenssl
> [hidden email]] On Behalf Of Jakob Bohm
> Sent: Friday, December 21, 2012 8:23 PM
> To: [hidden email]
> 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.
Thanks for that explanation.
> Some things that can speed up the private key operation without
> compromising security:
>
>  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.
Is the conversion supported by openssl utility (e.g. the way we convert .PEM to PKCS8 format
openssl pkcs8 topk8 in <PEM file> out <PKCS8 format file>)? Does openssl support PEM to CRT conversion?
I did not get any direct command for this conversion.
>
>  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 maximumcapacity test load.
>

Thanks,
Nilesh
>
> 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 nonbinding and may contain errors.
> WiseMo  Remote Service Management for PCs, Phones and Embedded
______________________________________________________________________
OpenSSL Project http://www.openssl.orgUser Support Mailing List [hidden email]
Automated List Manager [hidden email]


On Mon, Dec 24, 2012 at 12:35 AM, Tayade, Nilesh
< [hidden email]> wrote:
>> Original Message
>> From: [hidden email] [mailto:owneropenssl
>> [hidden email]] On Behalf Of Jakob Bohm
>> Sent: Friday, December 21, 2012 8:23 PM
>> To: [hidden email]
>> Subject: Re: RSA_private_decrypt function takes longer time.
>>
>> On 12/21/2012 1:13 PM, Tayade, Nilesh wrote:
>> <SNIP>
>
> Is the conversion supported by openssl utility (e.g. the way we convert .PEM to PKCS8 format
> openssl pkcs8 topk8 in <PEM file> out <PKCS8 format file>)? Does openssl support PEM to CRT conversion?
> I did not get any direct command for this conversion.
I believe you also need inform and outform. For example:
$ openssl genrsa out rsaopenssl.pem 3072
$ openssl pkcs8 nocrypt in rsaopenssl.pem inform PEM topk8
outform DER out rsaopenssl.der
Folks like Jakob or David likely have a one liner. My notes are kind
of old, and this always worked for me.
Here's the syntax for X.509 in case you need it:
$ openssl genrsa out rsaopenssl.pem 3072
$ openssl rsa in rsaopenssl.pem pubout outform DER out rsaopenssl.der
Jeff
______________________________________________________________________
OpenSSL Project http://www.openssl.orgUser Support Mailing List [hidden email]
Automated List Manager [hidden email]


On Mon, Dec 24, 2012 at 1:54 AM, Tayade, Nilesh
< [hidden email]> wrote:
>> Original Message
>> From: [hidden email] [mailto:owneropenssl
>> [hidden email]] On Behalf Of Jeffrey Walton
>> Sent: Monday, December 24, 2012 11:25 AM
>> To: [hidden email]
>> Subject: Re: RSA_private_decrypt function takes longer time.
> [...]
>
>> >> On 12/21/2012 1:13 PM, Tayade, Nilesh wrote:
>> >> <SNIP>
>> >
>> > Is the conversion supported by openssl utility (e.g. the way we
>> convert .PEM to PKCS8 format
>> > openssl pkcs8 topk8 in <PEM file> out <PKCS8 format file>)? Does
>> openssl support PEM to CRT conversion?
>> > I did not get any direct command for this conversion.
>> I believe you also need inform and outform. For example:
>>
>> $ openssl genrsa out rsaopenssl.pem 3072
>> $ openssl pkcs8 nocrypt in rsaopenssl.pem inform PEM topk8
>> outform DER out rsaopenssl.der
>>
>> Folks like Jakob or David likely have a one liner. My notes are kind
>> of old, and this always worked for me.
>>
>> Here's the syntax for X.509 in case you need it:
>>
>> $ openssl genrsa out rsaopenssl.pem 3072
>> $ openssl rsa in rsaopenssl.pem pubout outform DER out rsa
>> openssl.der
>
> Sorry to contact you in person. Just to confirm, do you mean .der format is same as Chinese remainder format of private key?
No problem. Taking it public again ;)
Note sure. The format we use is described in PKCS #1 (IIRC). What you
are referring to  CRT and dP, dQ, pInv, and qInv  are the private
key Representation 2 from Section 3.2 RSA Private Key
(ftp://ftp.rsasecurity.com/pub/pkcs/pkcs1/pkcs1v21.pdf). But I
would not expect it to be available.
Once you have a RSA Private Key, use `dumpasn1` and you will know for
sure. `openssl asn1parse` will also do it, but I use Gutmann's
utility.
If its not representation two, then see "RSA CRT key?",
https://groups.google.com/d/msg/sci.crypt/0ijgmfeBZOM/1h5NC97ZRsJ and
"RSA Converter", http://rsaconverter.sourceforge.net.
Jeff
______________________________________________________________________
OpenSSL Project http://www.openssl.orgUser Support Mailing List [hidden email]
Automated List Manager [hidden email]


> Original Message
> From: [hidden email] [mailto:owneropenssl
> [hidden email]] On Behalf Of Jakob Bohm
> Sent: Friday, December 21, 2012 8:23 PM
> To: [hidden email]
> 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 'donly' key?
>
>  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 maximumcapacity test load.
I would appreciate any link or further pointers on this. I am not so familiar with operations on RSA key.
>
> Enjoy
>
> Jakob
> 

Thanks,
Nilesh
______________________________________________________________________
OpenSSL Project http://www.openssl.orgUser Support Mailing List [hidden email]
Automated List Manager [hidden email]


On Thu, Jan 10, 2013 at 6:13 AM, Tayade, Nilesh
< [hidden email]> wrote:
>> Original Message
>> From: [hidden email] [mailto:owneropenssl
>> [hidden email]] On Behalf Of Jakob Bohm
>> Sent: Friday, December 21, 2012 8:23 PM
>> To: [hidden email]
>> Subject: Re: RSA_private_decrypt function takes longer time.
>>
>> On 12/21/2012 1:13 PM, Tayade, Nilesh wrote:
>> >
>> > I am using the RSA_private_decrypt() function in one of the custom
>> applications, where we expect the premaster to get decrypted faster.
> [...]
>
>> <SNIP>
>
> 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 'donly' key?
The private key is {n, e, d}. The public key is {n, e}.
Jeff
______________________________________________________________________
OpenSSL Project http://www.openssl.orgUser Support Mailing List [hidden email]
Automated List Manager [hidden email]


On 1/10/2013 12:13 PM, Tayade, Nilesh wrote:
>> Original Message
>> From: [hidden email] [mailto:owneropenssl
>> [hidden email]] On Behalf Of Jakob Bohm
>> Sent: Friday, December 21, 2012 8:23 PM
>> To: [hidden email]
>> 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 'donly' 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 "donlycannotgetthe rest" private key. (n, d, e)
is your "donlycanfigureouttherest" private key. (n, d or e, p or
q) is your "enoughtofigureouttherest" private key. (n, d, dQ, dP,
qIn, p, q) is your "allthedetailsalreadythere" 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 maximumcapacity 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 nonzero 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.comTransformervej 29, 2730 Herlev, Denmark. Direct +45 31 13 16 10
This public discussion message is nonbinding and may contain errors.
WiseMo  Remote Service Management for PCs, Phones and Embedded
______________________________________________________________________
OpenSSL Project http://www.openssl.orgUser Support Mailing List [hidden email]
Automated List Manager [hidden email]


> Original Message
> From: [hidden email] [mailto:owneropenssl
> [hidden email]] On Behalf Of Jakob Bohm
> Sent: Thursday, January 10, 2013 6:56 PM
> To: [hidden email]
> Subject: Re: RSA_private_decrypt function takes longer time.
[...]
> > 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 'donly' 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 "donlycannotgetthe rest" private key. (n, d, e)
> is your "donlycanfigureouttherest" private key. (n, d or e, p or
> q) is your "enoughtofigureouttherest" private key. (n, d, dQ, dP,
> qIn, p, q) is your "allthedetailsalreadythere" private key.
>
> So this is good, if you have a safe place to store all those numbers.
Appreciate the explanation. Thanks.
So I feel like I should try some hardware for asymmetric decryption, in order to push the performance.
[...]
> Enjoy
>
> Jakob
> 

Thanks,
Nilesh
______________________________________________________________________
OpenSSL Project http://www.openssl.orgUser Support Mailing List [hidden email]
Automated List Manager [hidden email]


On Thu, Jan 10, 2013 at 9:01 AM, Tayade, Nilesh
< [hidden email]> wrote:
>> Original Message
>> From: [hidden email] [mailto:owneropenssl
>> [hidden email]] On Behalf Of Jakob Bohm
>> Sent: Thursday, January 10, 2013 6:56 PM
>> To: [hidden email]
>> Subject: Re: RSA_private_decrypt function takes longer time.
> [...]
>
>> > 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 'donly' 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 "donlycannotgetthe rest" private key. (n, d, e)
>> is your "donlycanfigureouttherest" private key. (n, d or e, p or
>> q) is your "enoughtofigureouttherest" private key. (n, d, dQ, dP,
>> qIn, p, q) is your "allthedetailsalreadythere" private key.
>>
>> So this is good, if you have a safe place to store all those numbers.
> Appreciate the explanation. Thanks.
> So I feel like I should try some hardware for asymmetric decryption, in order to push the performance.
Performance is overrated. Before anything, the program has to be
correct. It should be secure. And it can be efficient.
If it does not need to be correct, I can make it as fast as you'd
like. We'll start by only allowing eNull and aNull :)
Jeff
______________________________________________________________________
OpenSSL Project http://www.openssl.orgUser Support Mailing List [hidden email]
Automated List Manager [hidden email]


> Original Message
> From: [hidden email] [mailto:owneropenssl
> [hidden email]] On Behalf Of Jeffrey Walton
> Sent: Thursday, January 10, 2013 7:54 PM
> To: [hidden email]
> Subject: Re: RSA_private_decrypt function takes longer time.
>
[...]
> > So I feel like I should try some hardware for asymmetric decryption,
> in order to push the performance.
> Performance is overrated. Before anything, the program has to be
> correct. It should be secure. And it can be efficient.
True. But HSM claims performance, correctness and security.
How about trying any of these PCI based cards?
> If it does not need to be correct, I can make it as fast as you'd
> like. We'll start by only allowing eNull and aNull :)
>
> Jeff

Thanks,
Nilesh
:��I"Ϯ��r�m����(���Z+�K�+����1���x��h���[�z�(���Z+���f�y������f���h��)z{,���


>True. But HSM claims performance, correctness and security.
Jeffrey's point is that you need wholesystem security, not just faster crypto. (And your original note didn't say HSM, but implied just an accelerator card.) For example, how do you make sure that only authentic and authorized software can connect to the HSM?
/r$

Principal Security Engineer
Akamai Technology
Cambridge, MA
:��I"Ϯ��r�m����(���Z+�K�+����1���x��h���[�z�(���Z+���f�y������f���h��)z{,���


On 01/10/2013 04:12 PM, Tayade, Nilesh wrote:
> True. But HSM claims performance, correctness and security.
HSM is an overloaded term, used for accelerators and containers alike.
(Common tamperevident cryptographic modules have very low signing
throughput.)

Florian Weimer / Red Hat Product Security Team
______________________________________________________________________
OpenSSL Project http://www.openssl.orgUser Support Mailing List [hidden email]
Automated List Manager [hidden email]

