CODEWITHSUNDEEP
javamathrsaarithmetic-expressionsmodular-arithmetic
Juanco
Juanco

Reputation: 33

Find number coprime to modulus

I've been doing some research on the RSA encryption system, it's pretty simple to code one using small primes, as there aren't too many possibilities and performance is not a real issue.

Here's how RSA Works:

Knowing this, to encrypt a message we just need to get two random primes, calculate n, e, d, and make our encryption and decryption methods.

This seems pretty easy in theory, now let's turn this into java code:

I first choose two random primes, the bigger the number, the stronger the encryption. So I'll choose p = 1644623 and q = 1644751. According to this page, they are primes.

BigInteger p = new BigInteger("1644623");
BigInteger q = new BigInteger("1644751");

Then, on my init method, I initialize n, e and d:

BigInteger p = new BigInteger("1644623");
BigInteger q = new BigInteger("1644751");

BigInteger n;
BigInteger e;
BigInteger d;

void init() {
    n = p.multiply(q);

    BigInteger pn = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE));

    e = n.subtract(pn);
    while (!mcd(pn, e).equals(BigInteger.ONE)) {
        e = e.add(BigInteger.ONE);
        System.out.println(e);
    }

    d = e.modPow(new BigInteger("-1"), pn);
}

I used BigInteger instead of long, as the values used are extremely big.

In theory, everything works. Practically, pn = 2704992034500, so checking if mcd(pn, e) = 1, and if not adding 1 to e and trying again it's not an option. This program is running since 30 minutes, at an average of 150.000 numbers / second. e = 548151505 and still not found mcd(pn, e) = 1.

Is there any way to find e in a reasonable time?

Upvotes: 2

Views: 2611

Answers (1)

user448810
user448810

Reputation: 17866

Any prime number will be co-prime to the modulus, by definition, so you don't need to search for one, just pick a prime number. Since the encryption key is public, most RSA implementations use something that makes it easy to compute the modular exponentiation: 3 and 65537 = 2 ** 16 + 1 are both prime, and both are commonly used for the encryption key.

Upvotes: 2

Related Questions