_gcry_mpi_gcd calculation wrong
Stephan Mueller
smueller at chronox.de
Fri Feb 15 09:40:00 CET 2019
Hi,
I am trying to check whether the following P and Q values lead to a proper RSA
key or not (i.e. I want to check whether P and Q would be the right candidates
for an RSA key).
e = a6db5b
p =
bdb4a50991c2d6cf2aeaef86068a026f1a45463697c23f7567c0cbfc5da5bc7b0b70d6e44da33df2e6bca8152292a3c6b776ea2e9f6528ea5d3e74afc19ee271ca940c2bcde6f18bf20c068bb973387d681b12d3689606825987d7bfc241cea0741a1be3a253f83e1654062db92b85287be8b385488a0eae13a4fe497d4fe751d588d0839086d1b935bf70bf715c34f87ed54cba51300aaaf53bdea5288726c7527a028dc2acf8962826a99ede37fad7b7310a77afb2bb8d9306350dc758930f
q =
c23121afc2530f01528bdf680d6d718f4719792d6137ef4500ea7bf993209c6d324999d668359953c71f8b320ea02af9d4b0f5199c2fef7ccda71f507cafd83d02183fd1575815d41eca6a2cec39104e9209ccbe0800a8c277077a27e726d73c2a0b6834313d0dc7a749c036d1edaafb48dd2a80ec191446b8958ba5e42d2b6424203ea26dc60e6c8397e605398c1e7da441c0ab142a29601bda839e8d69fe037115a2c712910a56beb9b19b938215cecf4e339f05b76059041568016fe64851
I convert the input data into the following SEXP:
(genkey(rsa(nbits 4:3072)(test-parms(e 8:10935131)(p %b)(q %b))))
Where %b is replaced with P and Q respectively during gcry_sexp_build.
This is followed by a gcry_pk_genkey.
libgcrypt generates and error during gcry_pk_genkey indicating that the values
are not prime.
After debugging the issue, I found that for the P value, _gcry_mpi_gcd
indicates that the common divisor for P-1 and E is not 1 (in fact, it
calculates the common divisor to be 7).
I.e. the following lines fail in generate_fips:
if (mpi_gcd (g, p1, e))
...
else if (testparms)
goto err;
The issue now is that the NIST reference implementation I use to verify the
results say that P and Q are prime and that the RSA key should be generated.
Also OpenSSL accepts the P and Q values and generates the RSA key using
RSA_generate_key_ex where the RSA struct contains P and Q already.
Ciao
Stephan
More information about the Gcrypt-devel
mailing list