Join Log in
Score:1
d186 avatar Crypto

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

sj flag
d186

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?

62
1 + 0
Score:1
fgrieu avatar Crypto
ng flag
fgrieu

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

+ 0
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.