Cryptography - RSA cryptanalysis : same message sent to different ppl with same low public
I have a set of three crypted messages (C1,C2,C3) (plus their modulus N1,N2,N3) from the same original message and I know the public exponent is 3, so I should be able to decrypt the original, shouldn't I?
So, if I understood well, I have to apply the Chinese remainder theorem and compute C'=M3 mod (N1*N2*N3). Plus N1*N2*N3 should be superior to M3, thus C'=M^3. Then a cube root of C' should give me the original message.
Problem is I know it can't be the original message because I have some rules to translate the decimal digits into letters and it should give me something readable, but I have nothing like that...
So the code
Chinese Remainder theorem :
public BigInteger CRT (BigInteger N1, BigInteger N2, BigInteger N3, BigInteger C1, BigInteger C2, BigInteger C3){
M = (N1.multiply(N2)).multiply(N3);
M1 = M.divide(N1);
M2 = M.divide(N2);
M3 = M.divide(N3);
Y1 = M1.modInverse(N1);
Y2 = M2.modInverse(N2);
Y3 = M3.modInverse(N3);
C = (((C1.multiply(M1)).multiply(Y1)).add((C2.multiply(M2)).multiply(Y2))).add((C3.multiply(M3)).multiply(Y3));
return C;
}
Newton Method to get the cube root on BigIntegers :
public BigInteger CubeRoot (BigInteger B,int iter){
BigInteger[] cubique =new BigInteger[2];
cubique[0] = B.divide(THREE);
for (int i=0;i<iter;i++){
cubique[1] = ((cubique[0].multiply(TWO)).add(B.divide(cubique[0].pow(2)))).divide(THREE);
cubique[0] = cubique[1];
}
return cubique[0];
}
I then enter N1,N2,N3,C1,C2,C3 in my main method and use the CRT with it, then the CubeRoot method.
I'm beginning to think my teacher messed up something (cause I have good CubeRoot (tried with google, same number), and the CRT doesn't seem bad o me..
Oh well...
[2425 byte] By [
Hydexa] at [2007-11-26 23:32:06]
# 2
Ah, yes.
What I have :
N1=1267682768173705772121204466014351966420991747124296692738781
N2=594784728187929558157361061797280079304217376578704859396287
N3=671800525673311414176121424420561070006706636143564347159839
c1=73027778005252405544593327041436348569691170420622495551015
c2=305913617156006386034555579973415711489743094002030933386086
c3=414716605522784806237606817798193202630805281585499491403345
Some rules to read the decrypted message :
01:a;02:b...,26:z ; 27 : [space]; 28 : [-]; 29 : ! ; 30 : , ; 31 : '
So a 04310103 would be read d'ac (means something in ly own language)
The assignement : 3 users B1,B2,B3 using respectively public keys (3,N1), (3,N2), (3,N3) receive the same message m. So I have 3 different samples of the same message crypted differently but with the same p ublic exponent (3) : C1,C2,C3.
Goal : Decrypt m.
Hydexa at 2007-7-10 14:44:26 >
# 12
The confusion is due partly to the fact that the word mod is sort of overloaded here. In math, a mod n is any of the infinite sequence of integers ..., a-2n, a -n, a, a+n, a+2n, ..., i.e. a +k*n, where k is any integer. Note that exactly one value in this sequence, call it 'r', satisfies, 0<= r < n. Now in computing, when we speak of a mod n, we usually mean this one value 'r'. This is what the BigInteger mod methods give you. The final twist is that in computational number theory, of which this is a simple example, both definitions come into play.
What the theory says is that when I do my CRT calculation I get a some C such that C = M3 + k*(N1*N2*N3). That is almost but not quite what I want for the cryptanalytic result. If instead I choose to use the magic smallest value 'r' from above, I still get an equation r = M3 + l*(N1*N2*N3), but now the facts 1) 0<= r< (N1*N2*N3), and 2) 0<=M3 < (N1*N2*N3) tell me that 'l' must equal 0, or r=M3.
When you computed C in your java CRT method, the intermediate result grows much larger than N1*N2*N3.
