1
$\begingroup$

Below is my implementation of the RSA algorithm. Actually I'm choosing the private key (d) instead of public key (e) and computing the public key.It is working fine but

I want to know if this is a safe implementation? and also Is any part in the code could lead to factorization of the modulus (n), thereby breaking the key?

As I did some work on it, I think the way I'm calculating (e and d) that could leads to factorization of the modulus(n) but I'm not sure. I read some research work on vulnerable class of exponents in RSA and from there I got public exponent satisfying an equation:

eX - NY = (ap + bq)Z with q>a>0, b=[ap/q]

Using the continued fraction algorithm and the Elliptic Curve Method of factorization, we can show that such exponents yield the factorization of the RSA modulus.

So question is that IS any part in code could lead to factorization of the modulus(n), thereby breaking the key? If yes then which part?

import java.math.*; import java.security.*; import java.util.*; public class RSAKeyGenerator { public static int KEY_SIZE = 2048; public static void main(String [] args) { try { //select size of each prime factor whose product will be atleast the given keysize. int factor_size = KEY_SIZE/2; Random rnd = new SecureRandom(); BigInteger p = BigInteger.probablePrime(factor_size, rnd); BigInteger q = BigInteger.probablePrime(factor_size, rnd); //compute N = p * q BigInteger N = p.multiply(q); //compute euler phi = (p-1) * (q-1) BigInteger phi = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE)); //select d size int d_size = KEY_SIZE / 5; //compute d BigInteger d = BigInteger.probablePrime(d_size, rnd); //make sure d is a coprime to euler phi. while (phi.gcd(d).compareTo(BigInteger.ONE) > 0) { //select another d d = BigInteger.probablePrime(d_size, rnd); } // compute e = d^-1 mod phi BigInteger e = d.modInverse(phi); BigInteger plaintext = BigInteger.probablePrime(d_size, rnd); BigInteger ciphertext = plaintext.modPow(e, N); BigInteger decryptedvalue = ciphertext.modPow(d, N); if(decryptedvalue.compareTo(plaintext) == 0) { System.out.println("decrypted values matches original plain text. these are proper RSA keys"); } else { System.out.println("something wrong... decrypted value does not match. try again!"); return; } catch (Throwable th) { }

}

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ This site is not for code review. For that, I'd suggest CodeReview.SE. That said, the crypto expertise here will probably be of more help. So instead of simply pasting your code here, rewrite it into mathematical equations. That would be more on-topic here. $\endgroup$ Commented Mar 5, 2013 at 17:00
  • $\begingroup$ Your method of choosing $d$ and then computing $e$ is nonstandard and probably could lead to breaks. At the very least, it is inefficient. Often we simply fix $e=65567$, make sure it is coprime to $\varphi(n)$, then compute $d$. $\endgroup$ Commented Mar 5, 2013 at 17:02

1 Answer 1

Reset to default
5
$\begingroup$

No, this is not a safe implementation; from the modulus and the public exponent, it would be possible to factor the modulus.

The reason is that you pick the private exponent to be small; one-fifth the size as the modulus. It's known that knowledge of a public exponent corresponding to that is sufficient to factor.

The obvious question is "why are you picking the private exponent?". Instead, why don't you pick the public exponent (65537 is a popular choice), and derive the private exponent from that.

Improve this answer
$\endgroup$
2
  • $\begingroup$ It is right that picking public exponent 65537 is popular choice, but above code compute public exponent of 2045 bit. isn't it good enough. $\endgroup$ Commented Mar 6, 2013 at 4:34
  • 3
    $\begingroup$ @kumaravi, no, it is not good enough. I recommend you read poncho's answer again, particularly the part beginning "The reason is..." $\endgroup$ Commented Mar 6, 2013 at 5:16

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.