2
$\begingroup$

I have a RSA public key in the form of public exponent and modulus as follows:

String exponent = "0000000000000003";
String modulus = "D8016FFDDFBA4B144B0AB13FF01968048B2FC9AA269311D11357DC8CEDCABA232BEC118D3B05AFA2406D27BFB6602B45B80E91D4F446E4A753C251EA6EB8AB8E3F304585DD202D8B04538EB4DD1F87D9A27E1E7B34A304396BBC38EE669E823BD03C1F43698B4B3128F3770C465CE415FD0F965F3170CED1470ED777751DE59D";

And also I have a private CRT key of the corresponding RSA key as follows:

String p = "F401F9E76A0E65D80AA8CF0D526D8D8747E53A3E1223B143AA73F675708ED966AB96965040907CCDF3D5C77904AA0906A6941E3A9C69AEC1F99E73E6EDB07191";
String q = "E29F25EC241F0FEDAD28B8DD1DCBABBD066F4F557467AE6A2CE4ED34F9D93257E2F8C8B6EE1F7A687E386BFEE9C20C3388385E82AFA498237FF801D283216D4D";
String dp = "A2ABFBEF9C09993AB1C5DF5E36F3B3AF85437C29616D20D7C6F7F9A3A05F3B99C7B9B98AD5B5A8894D392FA6031C06046F0D697C6846748151144D449E75A10B";
String dq = "9714C3F2C2BF5FF3C8C5D0936932727E044A34E3A2EFC99C1DEDF378A690CC3A975085CF496A519AFED047FF46815D77B02594571FC31017AAA5568C576B9E33";
String qinv = "075130A6D464E1541E92CCDF21BC4860D4E9E1BEF664CF5900A93774C67A507C13F1FAD2BEC2DCD0BEB4F2535C8175890ABA1BE851D0067B462C4876477E5DA7";

This kind of key was generated for testing purposes.

So I would like to check if it is correct and I have found out that mulitplying of p with q would give different modulus N, resp. N is different only at one half. I used the following calculation:

byte[] bp = hexToByteArray(p);
byte[] bq = hexToByteArray(q);
byte[] bdp = hexToByteArray(dp);
byte[] bdq = hexToByteArray(dq);
byte[] bqinv = hexToByteArray(qinv);

BigInteger pBI = new BigInteger(bp);
BigInteger qBI = new BigInteger(bq);
BigInteger modulusBI = pBI.multiply(qBI);

And the resulting modulus modulusBI has the following value in HEX:

0160502A518CD54E933929557FE02EC03CDB4016A007B2233BFEF8E28362AE649D5CB2860C55B86BCE5EF447C7F4160B89421517A8389DC1DA2BDC30FDE6CCB03F304585DD202D8B04538EB4DD1F87D9A27E1E7B34A304396BBC38EE669E823BD03C1F43698B4B3128F3770C465CE415FD0F965F3170CED1470ED777751DE59D

The value is not same as original modulus N from public key, but one half of it is correct, as you can see:

Computed N :0160502A518CD54E933929557FE02EC03CDB4016A007B2233BFEF8E28362AE649D5CB2860C55B86BCE5EF447C7F4160B89421517A8389DC1DA2BDC30FDE6CCB0 3F304585DD202D8B04538EB4DD1F87D9A27E1E7B34A304396BBC38EE669E823BD03C1F43698B4B3128F3770C465CE415FD0F965F3170CED1470ED777751DE59D
Original N :D8016FFDDFBA4B144B0AB13FF01968048B2FC9AA269311D11357DC8CEDCABA232BEC118D3B05AFA2406D27BFB6602B45B80E91D4F446E4A753C251EA6EB8AB8E 3F304585DD202D8B04538EB4DD1F87D9A27E1E7B34A304396BBC38EE669E823BD03C1F43698B4B3128F3770C465CE415FD0F965F3170CED1470ED777751DE59D

The second half of modulus is correct. Why is that? Am i doing some mistake in multiplying primes p and q?

$\endgroup$

closed as off-topic by yyyyyyy, DrLecter, Maarten Bodewes, Reid, SEJPM Apr 16 '15 at 19:56

  • This question does not appear to be about cryptography within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 6
    $\begingroup$ This is a programming question mostly unrelated to cryptography and should therefore be asked on Stack Overflow. (The numbers are correct, though — that is, $n=pq$ and your code is broken.) $\endgroup$ – yyyyyyy Apr 16 '15 at 10:29
  • 2
    $\begingroup$ Meh, try new BigInteger(1, bp);, same for all other BigInteger calls. $\endgroup$ – Maarten Bodewes Apr 16 '15 at 10:46
  • $\begingroup$ Endianness or sign bits are two common error sources. $\endgroup$ – CodesInChaos Apr 16 '15 at 10:51
1
$\begingroup$

bc on unix:

obase=16

ibase=16

p=F401F9E76A0E65D80AA8CF0D526D8D8747E53A3E1223B143AA73F675708ED966AB96965040907CCDF3D5C77904AA0906A6941E3A9C69AEC1F99E73E6EDB07191

q=E29F25EC241F0FEDAD28B8DD1DCBABBD066F4F557467AE6A2CE4ED34F9D93257E2F8C8B6EE1F7A687E386BFEE9C20C3388385E82AFA498237FF801D283216D4D

n=D8016FFDDFBA4B144B0AB13FF01968048B2FC9AA269311D11357DC8CEDCABA232BEC118D3B05AFA2406D27BFB6602B45B80E91D4F446E4A753C251EA6EB8AB8E3F304585DD202D8B04538EB4DD1F87D9A27E1E7B34A304396BBC38EE669E823BD03C1F43698B4B3128F3770C465CE415FD0F965F3170CED1470ED777751DE59D

p*q-n

0

So, the question is trivial and homework (before posting) was easy to do.

$\endgroup$

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