I wonder how computers can generate keys,especially RSA, easily and quickly. I've been trying to generate 24-bit keys for 2 hours using Java.
My program is using the random function to generate p and q,then if they aren't prime, the program generates new random numbers. Finally, the program calculates e and d. As you can see, my program uses the standard RSA algorithm,but it takes a lot of time.
I thought that the problem might lie in my algorithm, but not only RSA keys, also generating 100-bit prime numbers takes hours even if I use threads. So how can sites ,using HTTPS such as google, can generate these numbers almost in a millisecond?
There is a class named big integer in Java, and it has the method to generate probably random prime. However, if it's probably prime, some packages can't be decrypted. Not only HTTPS, also some websites can generate 1024-4096 bit keys while I'm struggling to calculate 24-bit keys.
Please explain how it works.
Edit: Here is my code:
private BigInteger minusOne=new BigInteger("-1");
private BigInteger one=new BigInteger("1");
private BigInteger two=new BigInteger("2");
private BigInteger zero=new BigInteger("0");
private void generateKeys(int keySize){
Random r=new Random();
q=BigInteger.probablePrime(keySize,r);
p=BigInteger.probablePrime(keySize, r);
n=p.multiply(q);
phi=(p.add(minusOne)).multiply(q.add(minusOne));
if(p.equals(q)){
generateKeys(keySize);
return;
}
e=calculate_e();
d=calculate_d();
if(d.equals(minusOne)){
generateKeys(keySize);
return;
}
}
private BigInteger calculate_e(){
Random r=new Random();
BigInteger e;
do{
e=new BigInteger(FindBitSize(phi),r);
}while(!BetweenPrime(e,phi));
if(e.compareTo(phi)==-1 && e.compareTo(one)==1){
return e;
}else{
return calculate_e();
}
}
private BigInteger calculate_d(){
BigInteger k=new BigInteger("0");
while(true){
if(k.multiply(e).mod(phi).equals(one)){
return k;
}
k=k.add(one);
}
}
private boolean BetweenPrime(BigInteger b2,BigInteger b1){
BigInteger d=new BigInteger("1");
while(d.compareTo(b1)==-1 && d.compareTo(b2)==-1){
d=d.add(one);
if(b1.mod(d).equals(zero) && b2.mod(d).equals(zero)){
return false;
}
}
return true;
}
However my problem is not about the code. I just don't understand how computers can calculate too big prime numbers in very short time.
There is a reason your implementation is incredibly slow. You've implemented the literal description, but of course there are algorithms that get you to the finish line much faster.
It is usually not necessary to calculate e. There are some common values for that: 3 (0x3), 17 (0x11), 65537 (0x10001). When as few bits of e as possible are set, then the encryption and signature verification will be very fast when efficient modular exponentiation algorithms are used.
You don't have to set it to a static value if you want encryption and decryption to be equally slow. You can compute it as described in Wikipedia using the greatest common divisor (GCD). Good thing BigInteger already provides an implementation for that:
private BigInteger calculate_e(){
Random r = new Random();
BigInteger e;
do{
e = new BigInteger(phi.bitLength(), r);
} while(!e.gcd(phi).equals(one));
if(e.compareTo(phi)==-1 && e.compareTo(one)==1){
return e;
} else {
return calculate_e();
}
}
calculate_d is a very naive implementation and will only work for very small numbers, because you're trying every single number between 1 and phi. The problem is if phi is something like 20 bits long it would take a million iterations. If phi where 30 bits long it would take a billion iterations. That just doesn't scale. The Wikipedia article on RSA suggests to calculate a modular multiplicative inverse e-1 (mod phi). An algorithm that is capable of that is the Extended Euclidean algorithm. Good thing that BigInteger already implements this:
private BigInteger calculate_d(){
return e.modInverse(phi);
}
Note that Random doesn't produce cryptographically secure random numbers. You really need to use SecureRandom to generate p and q. Also, the keySize is actually the size of n, so it should be:
SecureRandom r = new SecureRandom();
q = BigInteger.probablePrime(keySize/2, r);
p = BigInteger.probablePrime(keySize/2, r);