_gcry_mpi_gcd calculation wrong

[Stephan Mueller]

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