1
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.