Welome to the Internet, here's your private key
Greg Rose
ggr at qualcomm.com
Mon Feb 4 22:17:24 EST 2002
At 04:24 PM 2/4/2002 -0800, Bill Frantz wrote:
>At 2:09 PM -0800 2/4/02, lynn.wheeler at firstdata.com wrote:
> >1) A typical message would have a 20-byte nonce random number, which
> >computed to a 20-byte SHA1 and then encrypted with RSA resulting in 20-byte
> >signature (basic message plus 40-byte infrastructure overhead, signature
> >plus nonce).
I think an RSA signature can be no smaller than the key modulus, so an RSA
sig with a 1024-bit key is going to be 128 bytes plus some overhead, no
matter what. I think you (Lynn) meant DSA here. Or maybe you did mean RSA,
given that you then go on to DSA... I don't know.
>On the other hand, building a good source of random numbers into the card
>doesn't strike me as being that difficult. (Although running a FIPS-140
>test every time a signature is generated (card is powered up), might be a
>performance problem.)
This forced me to instrument my FIPS-140 code to measure it. It takes 1.42
ms to run a test on a Sun Ultra at 250MHz (I know, this is an ancient
machine). It's all integer arithmetic, on short integers at that, except
for the chi-square poker test, which (currently) does some floating point
but could easily be recoded to do scaled, 32-bit integer (16 x 16 -> 32 bit
multiplies, 16 of them, would be the bottleneck). Anyway, on a 0.5 MHz
smarcard, it's probably fair to assume this would take 0.5 seconds or so
(my C code is meant for clarity, not speed). This is probably less than the
time required for an RSA or DSA signature (taking into account the
precomputation) without hardware acceleration.
The scariest thing, though... at first I put in an unkeyed RC4 generator
for the self-test data, but accidentally ran the FIPS test on a straight
counter output... and it passed (even version 1)! I'd always assumed that
something in the regularity of a counter would trigger it. Running through
the buffer, XORing consecutive bytes, makes it fail quite handily, but
might also have the undesirable effect of hiding a bias in the data, if
there was one. I'm thinking of suggesting to NIST that a stronger test
would be to run the test on the raw data, and then on the data after XORing
consecutive bytes... if it's really random stuff it should pass both, and
in the meantime this would catch all sorts of failures. Any comments?
Anyway, if anyone wants it, the new fips140.c (with self-test and timing
loop support, but no other changes) is on my web page.
Greg.
Greg Rose INTERNET: ggr at qualcomm.com
Qualcomm Australia VOICE: +61-2-9817 4188 FAX: +61-2-9817 5199
Level 3, 230 Victoria Road, http://people.qualcomm.com/ggr/
Gladesville NSW 2111 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com
More information about the cryptography
mailing list