getting wrong rsa private exponent (d) for this particular test vector from nist cavp

Question

In 186-2rsatestvectors.zip/SigVerRSA.rsp

n = bb5784794f27bfab90a19bcc20bb10ac3d1d432d90651dace6235e34560abd733a0c3b693ea3802707c0e22e81603a6e2b82812a0027ece2d974a5a5190df89d636f7ab200849065fe412fe85e41aceb0d68b10cdd07e42ea16184c974f58c10c560aa444f64b41e932ab25355648b510b1feedca780cfb68f11ac9fc98ab15b

p = bda227ead8dc178121176abe07d036b3615a14e2badf195deba2082bf086c5eef4d40dc3ae3b57827359e90564fe4bf6cee0483506ad1be3586615711dbbccd7
q = fce80dce2ba920d88a530c9410d0a4e0358a3a11052e58dd73b0b179ef8f56fe3b5a2d117a7554948421c7b53beae378b2004d3f1314b2e64d4f23a49e1acb1d

SHAAlg = SHA1
e = 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010001
d = 557263ea3e97b71ce5f14811b126114335f6b852ba66dc43a58e212406d08c3b579107b2078f645ea8f32956a3ccc3a9c72f958116241fb01215d98d7561817061f6fc6001f423712f815f1caf325bf92405da8670c8ac1b931813402de1411c3e2b0c576a94378b5ccf540f95d62400b9610e83190fb2b8dbf13e838b9f86ed
Msg = 5e0a7afe6509821cac8d2cc01c6d419e671fb1fa902c33bdade12cc8ec47d288d45691cbcd66aed2e3e62aa7c750e9b1165c1385de75bbff5f69be920e64eedce01f707dc455632a7177c2fd63a08c0f20cb2249c044f077ac5c4f9ea661aa900acde0bd53beea4ce0a6be6bf94473e30dd3a5ef3d811b4e1f22a797bb264ecd
S = 0e93c8f719f00609fdbbe09f3b3e49f7a98288d9f87f18af893c15d47a6d418b8973ea90d382b5f8139990bb50b2264a34c483f4795ed4635c73221348d58a81978c72e9c1386cff9ff6d68747152940aed8c7a6bf28ac564100ab02bf326200a1a3f3f0f3777b825b507482d3c6ca629895e6d65ebb86d0a9bb96f82cb8849f
Result = P

I am getting d as

b31e2626e62b96f2ae4215f7c1839999548559e982996b1a189fd03e31d5eaf4f4972566a6e124722cd39a6de47ce0e0dcf0d616163816217ed02c6001e87dbe36699edc7ff3cf7758ecbb67d202c4a4df480b92ff45e515341f78d1f850f8ae08c4440efdee3b8f2aa6d4dbf013d1f17e80bb375fef332f509f7848927993a1

which i confirmed with https://www.mobilefish.com/services/rsa_key_generation/rsa_key_generation.php

snippet of the code

if (!((p1 = BN_new()) && BN_sub(p1, A, BN_value_one()))) goto out;
if (!((q1 = BN_new()) && BN_sub(q1, A, BN_value_one()))) goto out;
if (!(n = BN_new())) goto out;
if (!BN_mul(n, p, q, c)) goto out;
if (!(phi = BN_new())) goto out;
if (!BN_mul(phi, p1, q1, c)) goto out;
if (!(d = BN_new())) goto out;
if (!BN_mod_inverse(d, e, phi, c)) goto out;

How can I get correct d? Why is signature verification passes for this nist test vector?

Answer 1

You are computing $d:=e^{-1}\bmod\varphi(n)$, with $\varphi$ Euler's totient, and $\varphi(n)=(p-1)(q-1)$.

But you want to compute $d:=e^{-1}\bmod\lambda(n)$, with $\lambda$ the Carmichael function, and $\lambda(n)=\operatorname{lcm}(p-1,q-1)=(p-1)(q-1)/\gcd(p-1,q-1)$.

Both methods yield $d$ that's a private exponent matching a given $(n,e)$. Only the second method always yields the smallest such positive $d$. The first method is that of the original RSA article, the second method is prescribed by FIPS 186-5 (and earlier since -2) and thus NIST's CAVP. Both methods are compatible with PKCS#1, which allows any $d$ with $e\,d\equiv1\pmod{\lambda(n)}$ and $0<d<n$.