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$
    – mikeazo
    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$
    – mikeazo
    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$
    – neel
    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$
    – D.W.
    Mar 6, 2013 at 5:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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