[1201] in cryptography@c2.net mail archive
Re: DSA reference code?
daemon@ATHENA.MIT.EDU (Eric Young)
Thu Jul 10 22:37:08 1997
Date: Fri, 11 Jul 1997 11:58:36 +1000 (EST)
From: Eric Young <eay@cryptsoft.com>
To: Rodney Thayer <rodney@sabletech.com>
cc: cryptography@c2.net
In-Reply-To: <3.0.1.32.19970710093051.007da100@pop3.pn.com>
On Thu, 10 Jul 1997, Rodney Thayer wrote:
> I would like to know what DSA (that's the proper term, right? Not DSS)
> reference implementations are out there. In participating in the IETF PKIX
> discussions on this I'm trying to measure the gap between theory and
> practice. I did some fishing around and I find only one 'C' DSA
> implementation, "Cryptolib" from AT&T (which is sitting on some site in
> Italy). I suspect Schneier's disk set has DSA, too, but I haven't bought a
> copy of that (yet.)
>
> I am just trying to set up some reference code, to do timings and survey
> whether people have implemented 'precomputation' and see how hard it is in
> practice to do encryption, as suggested in Schneier's book. BSAFE seems to
> not give enough control through the API to do encryption, and I don't know
> if they do the precomputation [presumably one might determine that by
> checking the source.]
I can comment on DSA in SSLeay.
In theory I can do the pre-computation but I don't do it in my SSLv3
You have to do the calculation some time, and it cannot be re-used.
For a smart card, where you operate in parallel and have secure storage to
hold the values it makes alot of sense.
Wei Dia is doing some pre-calculations, but of a different type, I have not
looked into what he is doing yet. I think he is doing a long termp space/time
tradeoff with his a^b%m implementation.
Times I have for a few boxes,
Pentium 2 266mhz Win95
sign verify
rsa 512 bits 0.0062s 0.0008s
rsa 1024 bits 0.0287s 0.0009s
rsa 2048 bits 0.1785s 0.0059s
rsa 4096 bits 1.1300s 0.0205s
sign verify
dsa 512 bits 0.0055s 0.0100s
dsa 1024 bits 0.0154s 0.0299s
dsa 2048 bits 0.0502s 0.0996s
Alpha 400mhz (I've added another decimal since but have not run the new
version on this box yet)
rsa 512 bits 0.003s 0.000
rsa 1024 bits 0.013s 0.000
rsa 2048 bits 0.081s 0.003
rsa 4096 bits 0.577s 0.011
dsa 512 bits 0.003s 0.005
dsa 1024 bits 0.007s 0.014
dsa 2048 bits 0.025s 0.050
and the more standard type box a pentium 100 NT
rsa 512 bits 0.022s 0.003
rsa 1024 bits 0.112s 0.003
rsa 2048 bits 0.726s 0.026
rsa 4096 bits 5.268s 0.095
dsa 512 bits 0.021s 0.039
dsa 1024 bits 0.063s 0.127
dsa 2048 bits 0.224s 0.451
The lowest level interface is
int DSA_sign_setup( DSA *dsa,BN_CTX *ctx_in,BIGNUM **kinvp,BIGNUM **rp);
int DSA_sign(int type,unsigned char *dgst,int dlen,
unsigned char *sig, unsigned int *siglen, DSA *dsa);
int DSA_verify(int type,unsigned char *dgst,int dgst_len,
unsigned char *sigbuf, int siglen, DSA *dsa);
The DSA_sign_setup is rather ugly, and does not need to be called.
It calculates the dsa->kinv and dsa->r values.
I don't tend to use this in the library since it is not thread safe (assuming
the DSA key is shared between threads).
So to use pre-calculation, do lots of
DSA_sign_setup(dsa,bn_ctx,&kinv,&r);
calls saving the kinv and r pairs.
Then when it comes to signing,
dsa->kinv=kinv;
dsa->r=r;
DSA_sign(....)
eric
