ECDSA_do_verify()

[Kirk81 ()]

Hello,
I'm trying to benchmark the ECDSA with a 160 prime key and the SHA-1 function: I pass a string of characters to the SHA-1 and then I pass the digest to the ECDSA_do_sign and the ECDSA_so_verify function.

For this purpose I've modified a code that was posted previously. The code is the following and it's for MSV 2005. ecdsa.c

With a Intel Pentium M processor 1500MHz, I can "hash and sign" (with the above configuration) in 2.6 [ms] and I'm able to verify it in 0.02 [ms].

BUT...Is it possible that the verify function is so fast? Am I doing any mistake or is it a bug?

Plz note that the CPUTicks function works only with an IA-32. In any case u can use the other function that i included for timing.

Thanks in advance

[Mounir IDRASSI-3]

Hi,

What you are seeing is the side-effect of OpenSSL initialization
internals during the first time you access a cryptographic function that
uses random numbers (like ECDSA).
If, in your code, you do two signature in a raw before doing the
verification, you will notice that the first signature is always slower
that the second one and the second signature takes almost the same time
as the verification.

If you want to remove this side-effect, add the following two lines at
beginning of your program before doing any cryptographic operation :

    BIGNUM *dummy = BN_new();
    BN_rand(dummy, 256, 1, 1);

After adding these lines, you will see the magic! (the timings will
become more reasonable)

FYI, the side-effect has to do with the entropy collection of the
OpenSSL random generator. During the first cryptographic operation, most
of the time is consumed by the function RAND_poll.

Cheers,
--
Mounir IDRASSI
IDRIX
http://www.idrix.fr

Kirk81 wrote:

> Hello,
> I'm trying to benchmark the ECDSA with a 160 prime key and the SHA-1
> function: I pass a string of characters to the SHA-1 and then I pass the
> digest to the ECDSA_do_sign and the ECDSA_so_verify function.
>
> For the purposed I've modified a code that was posted previously. The code
> is the following and it's for MSV 2005.
> http://www.nabble.com/file/p26074867/ecdsa.c ecdsa.c
>
> With a Intel Pentium M processor 1500MHz, I can "hash and sign" (with the
> above configuration) in 2.6 [ms] and I'm able to verify it in 0.02 [ms].
>
> BUT...Is it possible that the verify function is so fast? Am I doing any
> mistake or is it a bug?
>
> Thanks in advance
>  

______________________________________________________________________
OpenSSL Project                                 http://www.openssl.org
Development Mailing List                       openssl-dev@...
Automated List Manager                           majordomo@...

[Mounir IDRASSI]

Hi,

What you are seeing is the side-effect of OpenSSL initialization
internals during the first time you access a cryptographic function that
uses random numbers (like ECDSA).
If, in your code, you do two signature in a raw before doing the
verification, you will notice that the first signature is always slower
that the second one and the second signature takes almost the same time
as the verification.

If you want to remove this side-effect, add the following two lines at
beginning of your program before doing any cryptographic operation :

    BIGNUM *dummy = BN_new();
    BN_rand(dummy, 256, 1, 1);

After adding these lines, you will see the magic! (the timings will
become more reasonable)

FYI, the side-effect has to do with the entropy collection of the
OpenSSL random generator. During the first cryptographic operation, most
of the time is consumed by the function RAND_poll.

Cheers,
--
Mounir IDRASSI
IDRIX
http://www.idrix.fr

Kirk81 wrote:

> Hello,
> I'm trying to benchmark the ECDSA with a 160 prime key and the SHA-1
> function: I pass a string of characters to the SHA-1 and then I pass the
> digest to the ECDSA_do_sign and the ECDSA_so_verify function.
>
> For the purposed I've modified a code that was posted previously. The code
> is the following and it's for MSV 2005.
> http://www.nabble.com/file/p26074867/ecdsa.c ecdsa.c
>
> With a Intel Pentium M processor 1500MHz, I can "hash and sign" (with the
> above configuration) in 2.6 [ms] and I'm able to verify it in 0.02 [ms].
>
> BUT...Is it possible that the verify function is so fast? Am I doing any
> mistake or is it a bug?
>
> Thanks in advance
>  

______________________________________________________________________
OpenSSL Project                                 http://www.openssl.org
Development Mailing List                       openssl-dev@...
Automated List Manager                           majordomo@...

[David Jacobson-3]

Kirk81 wrote:

> Hello,
> I'm trying to benchmark the ECDSA with a 160 prime key and the SHA-1
> function: I pass a string of characters to the SHA-1 and then I pass the
> digest to the ECDSA_do_sign and the ECDSA_so_verify function.
>
> For the purposed I've modified a code that was posted previously. The code
> is the following and it's for MSV 2005.
> http://www.nabble.com/file/p26074867/ecdsa.c ecdsa.c
>
> With a Intel Pentium M processor 1500MHz, I can "hash and sign" (with the
> above configuration) in 2.6 [ms] and I'm able to verify it in 0.02 [ms].
>
> BUT...Is it possible that the verify function is so fast? Am I doing any
> mistake or is it a bug?
>
> Thanks in advance

It doesn't sound possible.  In fact, ECDSA verify has two point
multiplications vs. one for ECDSA sign.  So it should be slower.  But
here is a technique that will help resolve the issue.  Change one byte
of the message, and try to verify.  If it verifies successfully, you
know it is not working.

   -- David Jacobson
______________________________________________________________________
OpenSSL Project                                 http://www.openssl.org
Development Mailing List                       openssl-dev@...
Automated List Manager                           majordomo@...

[Kirk81]

Hello,

I put the two lines but it doesn't work , at all: in fact, it works worth! :-/

Have u tried to do it before suggest it to me? What result did u get?

Thanks

Mounir IDRASSI wrote:

Hi,

What you are seeing is the side-effect of OpenSSL initialization
internals during the first time you access a cryptographic function that
uses random numbers (like ECDSA).
If, in your code, you do two signature in a raw before doing the
verification, you will notice that the first signature is always slower
that the second one and the second signature takes almost the same time
as the verification.

If you want to remove this side-effect, add the following two lines at
beginning of your program before doing any cryptographic operation :

    BIGNUM *dummy = BN_new();
    BN_rand(dummy, 256, 1, 1);

After adding these lines, you will see the magic! (the timings will
become more reasonable)

FYI, the side-effect has to do with the entropy collection of the
OpenSSL random generator. During the first cryptographic operation, most
of the time is consumed by the function RAND_poll.

Cheers,
--
Mounir IDRASSI
IDRIX
http://www.idrix.fr

[Kirk81]

The ECDSA_do function seems working: the verification process failed when I changed a bit in the string of the verify process.

Yep, the verify process should be slower.

David Jacobson-3 wrote:

It doesn't sound possible.  In fact, ECDSA verify has two point
multiplications vs. one for ECDSA sign.  So it should be slower.  But
here is a technique that will help resolve the issue.  Change one byte
of the message, and try to verify.  If it verifies successfully, you
know it is not working.

   -- David Jacobson
______________________________________________________________________
OpenSSL Project                                 http://www.openssl.org
Development Mailing List                       [e-mail]
Automated List Manager                           [e-mail]

[Mounir IDRASSI]

Hi,

Of course I tested it before writing the email!! The output I get from
your program is below. Moreover, I used a professional profiling tool to
analyse the time consumption and to verify that it is coming from the
first call of the first signing operation, and specifically from RAND_poll.
How could the initialization of a BIGNUM and computing a random value
for it be worse??
Also, in your code, MSVC 2008 complains that there is an overflow in the
integral constant line 79 : you have to replace 134774L by 134774LL to
avoid this.

More generally, if you need more accurate timing values, I advise you to
compute the mean of several measurements : for example, in your code,
you can perform a loop of 1000 iteration containing the call to SHA1 and
ECDSA_do_sign and then divide the elapsed time by 1000 (the same thing
for the verification). Thus, you will remove the side effect of the
first signature call and you will get more significant values.

Have tried modifying your code to do two signatures in a raw, one after
another, and output the timing of each one?

And here is the output of your program after introducing the dummy
BIGNUM random initialization (on a Pentium M processor 1700 MHz) :

C:\>ecdsatest.exe

 --> WinTimeHigh: 0
 --> WinTimeLow: 0 [ns]
 --> CPU-Ticks.High = 0
 --> CPU-Ticks.Low = 18832
(sig->r, sig->s):
(9134279177818445EE242B823B088E70CDB05AB9,6BA4942A96BA5B1D798F859FB331F557D5170E1F)

 sign returned 1
(sig->r, sig->s):
(9134279177818445EE242B823B088E70CDB05AB9,6BA4942A96BA5B1D798F859FB331F557D5170E1F)
i2d_ECDSA_SIG returned 0062E2B8, length 47
d2i_ECDSA_SIG returned 0062E2E8

 --> WinTimeHigh: 0
 --> WinTimeLow: 0 [ns]
 --> CPU-Ticks.High = 0
 --> CPU-Ticks.Low = 22368
verify returned 1

And just in case, I have put the MSVC 2008 build binary against OpenSSL
09.8k on the following link : http://www.idrix.fr/test/ecdsatest.zip

Cheers,
--
Mounir IDRASSI
IDRIX
http://www.idrix.fr

Kirk81 wrote:

> Hello,
>
> I put the two lines but it doesn't work , at all: in fact, it works worth!
> :-/
>
> Have u tried to do it before suggest it to me? What result did u get?
>
> Thanks
>
>
>
>
> Mounir IDRASSI wrote:
>  
>> Hi,
>>
>> What you are seeing is the side-effect of OpenSSL initialization
>> internals during the first time you access a cryptographic function that
>> uses random numbers (like ECDSA).
>> If, in your code, you do two signature in a raw before doing the
>> verification, you will notice that the first signature is always slower
>> that the second one and the second signature takes almost the same time
>> as the verification.
>>
>> If you want to remove this side-effect, add the following two lines at
>> beginning of your program before doing any cryptographic operation :
>>
>>     BIGNUM *dummy = BN_new();
>>     BN_rand(dummy, 256, 1, 1);
>>
>> After adding these lines, you will see the magic! (the timings will
>> become more reasonable)
>>
>> FYI, the side-effect has to do with the entropy collection of the
>> OpenSSL random generator. During the first cryptographic operation, most
>> of the time is consumed by the function RAND_poll.
>>
>> Cheers,
>> --
>> Mounir IDRASSI
>> IDRIX
>> http://www.idrix.fr
>>
>>    
>
>  

______________________________________________________________________
OpenSSL Project                                 http://www.openssl.org
Development Mailing List                       openssl-dev@...
Automated List Manager                           majordomo@...

[Kirk81]

yep, thanks!!

you were right! I had a shock about the performance: I didn't aspect it soo fast!! That was my doubt.
Here my MSVC 2008 build binary against 'openssl-1.0.0-stable-SNAP-20091028'.
ECDSA.exe

Thanks for the hint about the loop of measurements: it was in program in the following version.

And thank you very much about the overflow: I didn't notice that.

Seem you're quite familiary with openSSL and crypography so I'd like to ask a if u ever de-coupling the functions of openSSL's project? I would like to isolate the ECDSA (and the corresponding functions) from openSSL and remove all the rest.  Is it possible?

Kirk

Mounir IDRASSI wrote:

Hi,

Of course I tested it before writing the email!! The output I get from
your program is below. Moreover, I used a professional profiling tool to
analyse the time consumption and to verify that it is coming from the
first call of the first signing operation, and specifically from RAND_poll.
How could the initialization of a BIGNUM and computing a random value
for it be worse??
Also, in your code, MSVC 2008 complains that there is an overflow in the
integral constant line 79 : you have to replace 134774L by 134774LL to
avoid this.

More generally, if you need more accurate timing values, I advise you to
compute the mean of several measurements : for example, in your code,
you can perform a loop of 1000 iteration containing the call to SHA1 and
ECDSA_do_sign and then divide the elapsed time by 1000 (the same thing
for the verification). Thus, you will remove the side effect of the
first signature call and you will get more significant values.

Have tried modifying your code to do two signatures in a raw, one after
another, and output the timing of each one?

And here is the output of your program after introducing the dummy
BIGNUM random initialization (on a Pentium M processor 1700 MHz) :

C:\>ecdsatest.exe

 --> WinTimeHigh: 0
 --> WinTimeLow: 0 [ns]
 --> CPU-Ticks.High = 0
 --> CPU-Ticks.Low = 18832
(sig->r, sig->s):
(9134279177818445EE242B823B088E70CDB05AB9,6BA4942A96BA5B1D798F859FB331F557D5170E1F)

 sign returned 1
(sig->r, sig->s):
(9134279177818445EE242B823B088E70CDB05AB9,6BA4942A96BA5B1D798F859FB331F557D5170E1F)
i2d_ECDSA_SIG returned 0062E2B8, length 47
d2i_ECDSA_SIG returned 0062E2E8

 --> WinTimeHigh: 0
 --> WinTimeLow: 0 [ns]
 --> CPU-Ticks.High = 0
 --> CPU-Ticks.Low = 22368
verify returned 1

And just in case, I have put the MSVC 2008 build binary against OpenSSL
09.8k on the following link : http://www.idrix.fr/test/ecdsatest.zip

Cheers,
--
Mounir IDRASSI
IDRIX
http://www.idrix.fr

Kirk81 wrote:
> Hello,
>
> I put the two lines but it doesn't work , at all: in fact, it works worth!
> :-/
>
> Have u tried to do it before suggest it to me? What result did u get?
>
> Thanks
>
>
>
>
> Mounir IDRASSI wrote:
>  
>> Hi,
>>
>> What you are seeing is the side-effect of OpenSSL initialization
>> internals during the first time you access a cryptographic function that
>> uses random numbers (like ECDSA).
>> If, in your code, you do two signature in a raw before doing the
>> verification, you will notice that the first signature is always slower
>> that the second one and the second signature takes almost the same time
>> as the verification.
>>
>> If you want to remove this side-effect, add the following two lines at
>> beginning of your program before doing any cryptographic operation :
>>
>>     BIGNUM *dummy = BN_new();
>>     BN_rand(dummy, 256, 1, 1);
>>
>> After adding these lines, you will see the magic! (the timings will
>> become more reasonable)
>>
>> FYI, the side-effect has to do with the entropy collection of the
>> OpenSSL random generator. During the first cryptographic operation, most
>> of the time is consumed by the function RAND_poll.
>>
>> Cheers,
>> --
>> Mounir IDRASSI
>> IDRIX
>> http://www.idrix.fr
>>
>>    
>
>  

______________________________________________________________________
OpenSSL Project                                 http://www.openssl.org
Development Mailing List                       [e-mail]
Automated List Manager                           [e-mail]

[Kirk81]

Sorry guys, I found some mistakes in my code.

This is about the benchmark of the function: previously when I print out the values of the numbers of CPUticks and 'WinTime', I'm considering the sign (or the verify) operation for a loop of 100 repeated times.
 
So finally, with an IA-32 Pentium M processor 1500MHz, the functions are in order of microseconds [ms]:

- signature : 1.3 ms

- verify: 1.46 ms

That's more plausible!!

Here u can find the 'right' version of the ECDSA:

ecdsa.c

I hope now it's everything's fine. Thanks and sorry again! :-)

Kirk

[Michael Sierchio]

Kirk81 wrote:
> Sorry guys, I found some mistakes in my code.

Not just in your code

> So finally, with an IA-32 Pentium M processor 1500MHz, the functions are in
> order of microseconds [ms]:

ms denotes milliseconds.  us denotes microseconds, unless you
can express it as μs, which is obviously preferred.

______________________________________________________________________
OpenSSL Project                                 http://www.openssl.org
Development Mailing List                       openssl-dev@...
Automated List Manager                           majordomo@...

[Kirk81]

u r right. I think one things and i wrote another :-/  

I'm in the order on milliseconds [ms].

Michael Sierchio wrote:

Kirk81 wrote:
> Sorry guys, I found some mistakes in my code.

Not just in your code

> So finally, with an IA-32 Pentium M processor 1500MHz, the functions are in
> order of microseconds [ms]:

ms denotes milliseconds.  us denotes microseconds, unless you
can express it as μs, which is obviously preferred.

______________________________________________________________________
OpenSSL Project                                 http://www.openssl.org
Development Mailing List                       [e-mail]
Automated List Manager                           [e-mail]

[Peter Waltenberg]

FYI.

OpenSSL 0.9.8e 23 Feb 2007 built on: Fri Oct 16 14:31:12 EST 2009 platform:
linu
x-x86_64 compiler: gcc -fPIC -DOPENSSL_PIC -DOPENSSL_THREADS -D_REENTRANT
-DDSO_
DLFCN -DHAVE_DLFCN_H -m64 -DL_ENDIAN -DTERMIO -O3 -Wall -DMD32_REG_T=int
-DOPENS
SL_BN_ASM_MONT -DSHA1_ASM -DSHA256_ASM -DSHA512_ASM -DOPENSSL_IA32_SSE2
-DMD5_AS
M -DAES_ASM OPENSSLDIR:
"/usr/local/ssl":----------------------------,Linux2.6.30.8-64.f
c11.x86,#1 SMP Fri Sep 25 04,x86_64,Thu Oct 29 07:18:35 2009

Threaded speed test, 1 threads
Signature tests (Speeds in signs/s - verifies/s)
Mode/Size       ,S2048    ,V2048
RSA-SHA1        ,124.90   ,4282.19
ECDSA tests (Speeds in signs/s - verifies/s) SHA1 hash
EC type,        Sign     ,Verify
P-192           ,1074.25  ,890.77
P-224           ,977.67   ,852.78
P-256           ,865.94   ,742.80
P-384           ,364.07   ,307.44
P-521           ,187.18   ,158.93
K-163           ,838.20   ,424.63
K-283           ,279.43   ,140.47
K-409           ,133.47   ,66.99
K-571           ,62.69    ,31.42
B-163           ,785.80   ,400.80
B-283           ,253.92   ,127.59
B-409           ,120.89   ,60.56



Peter

______________________________________________________________________
OpenSSL Project                                 http://www.openssl.org
Development Mailing List                       openssl-dev@...
Automated List Manager                           majordomo@...

[Mounir IDRASSI]

Hi,

I have already thought about it but never done it because I found it to
be too tedious, especially concerning the build system and the heavy
macro usage, combined with a lack of motivation!
However, I believe it is possible to isolate ECDSA and it should take a
week at most for an experienced OpenSSL developer to come up with a
clean library subset.

Cheers,
--
Mounir IDRASSI
IDRIX
http://www.idrix.fr

Kirk81 wrote:

> yep, thanks!!
>
> you were right! I had a shock about the performance: I didn't aspect it soo
> fast!! That was my doubt.
> Here my MSVC 2008 build binary against 'openssl-1.0.0-stable-SNAP-20091028'.
> http://www.nabble.com/file/p26093729/ECDSA.exe ECDSA.exe
>
> Thanks for the hint about the loop of measurements: it was in program in the
> following version.
>
> And thank you very much about the overflow: I didn't notice that.
>
> Seem you're quite familiary with openSSL and crypography so I'd like to ask
> a if u ever de-coupling the functions of openSSL's project? I would like to
> isolate the ECDSA (and the corresponding functions) from openSSL and remove
> all the rest.  Is it possible?
>
> Kirk
>
>
>
> Mounir IDRASSI wrote:
>  
>> Hi,
>>
>> Of course I tested it before writing the email!! The output I get from
>> your program is below. Moreover, I used a professional profiling tool to
>> analyse the time consumption and to verify that it is coming from the
>> first call of the first signing operation, and specifically from
>> RAND_poll.
>> How could the initialization of a BIGNUM and computing a random value
>> for it be worse??
>> Also, in your code, MSVC 2008 complains that there is an overflow in the
>> integral constant line 79 : you have to replace 134774L by 134774LL to
>> avoid this.
>>
>> More generally, if you need more accurate timing values, I advise you to
>> compute the mean of several measurements : for example, in your code,
>> you can perform a loop of 1000 iteration containing the call to SHA1 and
>> ECDSA_do_sign and then divide the elapsed time by 1000 (the same thing
>> for the verification). Thus, you will remove the side effect of the
>> first signature call and you will get more significant values.
>>
>> Have tried modifying your code to do two signatures in a raw, one after
>> another, and output the timing of each one?
>>
>> And here is the output of your program after introducing the dummy
>> BIGNUM random initialization (on a Pentium M processor 1700 MHz) :
>>
>> C:\>ecdsatest.exe
>>
>>  --> WinTimeHigh: 0
>>  --> WinTimeLow: 0 [ns]
>>  --> CPU-Ticks.High = 0
>>  --> CPU-Ticks.Low = 18832
>> (sig->r, sig->s):
>> (9134279177818445EE242B823B088E70CDB05AB9,6BA4942A96BA5B1D798F859FB331F557D5170E1F)
>>
>>  sign returned 1
>> (sig->r, sig->s):
>> (9134279177818445EE242B823B088E70CDB05AB9,6BA4942A96BA5B1D798F859FB331F557D5170E1F)
>> i2d_ECDSA_SIG returned 0062E2B8, length 47
>> d2i_ECDSA_SIG returned 0062E2E8
>>
>>  --> WinTimeHigh: 0
>>  --> WinTimeLow: 0 [ns]
>>  --> CPU-Ticks.High = 0
>>  --> CPU-Ticks.Low = 22368
>> verify returned 1
>>
>> And just in case, I have put the MSVC 2008 build binary against OpenSSL
>> 09.8k on the following link : http://www.idrix.fr/test/ecdsatest.zip
>>
>> Cheers,
>> --
>> Mounir IDRASSI
>> IDRIX
>> http://www.idrix.fr
>>
>> Kirk81 wrote:
>>    
>>> Hello,
>>>
>>> I put the two lines but it doesn't work , at all: in fact, it works
>>> worth!
>>> :-/
>>>
>>> Have u tried to do it before suggest it to me? What result did u get?
>>>
>>> Thanks
>>>
>>>
>>>
>>>
>>> Mounir IDRASSI wrote:
>>>  
>>>      
>>>> Hi,
>>>>
>>>> What you are seeing is the side-effect of OpenSSL initialization
>>>> internals during the first time you access a cryptographic function that
>>>> uses random numbers (like ECDSA).
>>>> If, in your code, you do two signature in a raw before doing the
>>>> verification, you will notice that the first signature is always slower
>>>> that the second one and the second signature takes almost the same time
>>>> as the verification.
>>>>
>>>> If you want to remove this side-effect, add the following two lines at
>>>> beginning of your program before doing any cryptographic operation :
>>>>
>>>>     BIGNUM *dummy = BN_new();
>>>>     BN_rand(dummy, 256, 1, 1);
>>>>
>>>> After adding these lines, you will see the magic! (the timings will
>>>> become more reasonable)
>>>>
>>>> FYI, the side-effect has to do with the entropy collection of the
>>>> OpenSSL random generator. During the first cryptographic operation, most
>>>> of the time is consumed by the function RAND_poll.
>>>>
>>>> Cheers,
>>>> --
>>>> Mounir IDRASSI
>>>> IDRIX
>>>> http://www.idrix.fr
>>>>
>>>>    
>>>>        
>>>  
>>>      
>> ______________________________________________________________________
>> OpenSSL Project                                 http://www.openssl.org
>> Development Mailing List                       openssl-dev@...
>> Automated List Manager                           majordomo@...
>>
>>
>>    
>
>  

______________________________________________________________________
OpenSSL Project                                 http://www.openssl.org
Development Mailing List                       openssl-dev@...
Automated List Manager                           majordomo@...