| Subject: | Invalid private keys being produced |
During interoperability tests with Crypt::DSA::GMP, I found my simple key validation routine regularly failing for the CryptX produced keys.
FIPS 186-2: "4. DSA parameters" page 8:
x = a randomly or pseudorandomly generated integer with 0 < x < q
FIPS 186-4: "4. DSA parameters" page 15:
x = the private key that must remain secret; x is a randomly or pseudorandomly generated integer, such that 0 < x < q, i.e., x is in the range [1, q-1].
src/ltc/pk/dsa/dsa_make_key.c produces random x values of the same bit size as q (looping if x == 0), but that allows x to be >= q.
Example:
perl -MCrypt::PK::DSA -MMath::BigInt -E 'my $dsa1 = Crypt::PK::DSA->new(); do { $dsa1->generate_key(20, 128); my $pkhash = $dsa1->key2hash; die "$pkhash->{x} >= $pkhash->{q}" if Math::BigInt->from_hex($pkhash->{x}) >= Math::BigInt->from_hex($pkhash->{q}); } for 1..100'
It looks like k in the signing function is also being generated with the bit size of q rather than mod q.
This has been in libtomcrypt for some time I guess. I'm not sure if that project is still being worked on -- the last release was in 2007. I'm not certain that either the x or k ranges present a cryptographic flaw, but it's definitely wrong according to the specifications.