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

| improve this answer | |
$\endgroup$

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