So, Im using java to find the public key of a RSA password. Right now Im unsure what I'm doing and also if it's correct.
I have this information for the public key.
C = 5449089907
n = p*q = 8271344041
q = 181123
p = n/q = 45667
d = 53
phi(n) = (p-1)(q-1) = 8271117252
What complicates things are the BigIntegers, the numbers are way to huge for int and longs, so I have to use the clumsy BigIntegers. As far as I understand I have the following equation to solve.
e*5198987987 - x*8271117252 = 1
I'm trying to use euklidske algorithm to solve it. In Java i think i can use the following method :
I base the code on phi(n) = 8271117252 and d = 53. I then use gcd in a for loop, trying the i numbers from the for loop to gdc on phi(n). If the result is 1, i set e to the iteration number of i. I then use modulus inverse function on e, and phi(n). If, and only if this equals phi(n) I got the answer. (I think, it may be as wrong as it gets).
Anyway, here is the code. Generally any input would be awesome as its driving me a bit nuts.
import java.math.BigInteger;
public class RSADecrypt {
BigInteger p = new BigInteger("53"); // Input privatekey.
BigInteger r = new BigInteger("8271344041");
BigInteger variabel_i;
BigInteger modinv;
BigInteger e;
public RSADecrypt () {
for (BigInteger bi = BigInteger.valueOf(1000000000);
bi.compareTo(BigInteger.ZERO) > 0;
bi = bi.subtract(BigInteger.ONE)) {
if(gcdThing(bi).equals(BigInteger.ONE))
e = bi;
if(modinv(e) == p) {
System.out.println(" I er "+ bi);
}
}
System.out.println("Ikke noe svar for deg!");
}
// Gcd funksjon.
public BigInteger gcdThing(BigInteger i) {
BigInteger b2 = new BigInteger(""+i);
BigInteger gcd = r.gcd(b2);
return gcd;
}
// Modinverse
public BigInteger modinv (BigInteger e2) {
variabel_i = new BigInteger(""+e2);
modinv = r.modInverse(variabel_i);
return modinv;
}
}