Java Program for RSA Key Pair Generation with Strong Primes

Introduction

The rsa key generation java tutorial walks through the generation of an RSA key pair using only the JDK's java.security and java.math APIs. RSA was invented by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT in 1977, published in Communications of the ACM in February 1978, and patented by MIT in 1983 (US Patent 4,405,829, which expired in September 2000). The algorithm's security rests on the difficulty of factoring the product of two large prime numbers, and the public-key signature and encryption primitive is still the most widely deployed asymmetric cryptographic primitive in the world.

For a Java learner the rsa key generation java example below matters because the JDK ships the KeyPairGenerator for RSA in the SunRsaSign provider, which has been the standard JDK provider for RSA since Java 1.1. The standard API (KeyPairGenerator.getInstance("RSA").initialize(2048)) is the production way to generate keys; this tutorial also shows a manual implementation using BigInteger to make the algorithm itself transparent, and explains the role of strong primes.

The role of strong primes was introduced by Gordon in 1985 to defend against the Pollard p-1 and p+1 factoring algorithms, which factor a number N when N has a prime factor p such that p-1 or p+1 has only small prime factors. Modern RSA implementations use Miller-Rabin probabilistic primality testing with enough rounds to make the probability of a composite slipping through less than 2 to the power minus 100, which is sufficient for any practical purpose.

What is RSA Key Generation?

rsa key generation java is the process of producing an RSA key pair: a public key (n, e) and a private key (n, d). The modulus n is the product of two large prime numbers p and q; the public exponent e is a small odd number, typically 65537 (the fourth Fermat number); the private exponent d is the multiplicative inverse of e modulo the Carmichael totient lambda(n) = lcm(p-1, q-1).

The keys belong to the family of asymmetric cryptographic primitives, in which the encryption key is public and the decryption key is private. Other primitives in the family are Diffie-Hellman key exchange (1976), the Digital Signature Algorithm (1991), and Elliptic Curve Cryptography (1985). RSA is unique in this family for its simplicity: the same primitive (modular exponentiation) serves both for encryption and for signatures, and the key generation is conceptually simple enough to be taught in an undergraduate cryptography course.

The security of RSA depends on the difficulty of factoring n. The largest RSA modulus factored publicly is RSA-768 (768 bits, factored in December 2009 by Kleinjung et al.), and the current recommendation for new keys is 2048 bits minimum, with 3072 bits recommended for keys that need to remain secure after 2030 (NIST SP 800-57). The factorization record is several years behind the recommendation, which is the standard cryptographic safety margin.

How RSA Key Generation Works Step by Step

Step 1: Generate two large prime numbers p and q. Each prime should be exactly half the bit length of the desired modulus: for a 2048-bit modulus, each prime is 1024 bits. The primes should be distinct (p is not equal to q) and should not be too close together (the difference between p and q should be greater than the square root of the smaller, to defeat Fermat's factorization method).

Step 2: Compute the modulus n = p times q. The modulus is the public part of the key, the number that the factorization of which would reveal the private key. For a 2048-bit modulus, n is a number between 2 to the power 2047 and 2 to the power 2048.

Step 3: Compute the Carmichael totient lambda(n) = lcm(p-1, q-1). The Carmichael totient is preferred over the Euler totient phi(n) = (p-1)(q-1) because it gives the smallest valid private exponent, which is slightly faster in computation. Both work mathematically; the choice is a performance optimization.

Step 4: Choose the public exponent e. The standard choice is 65537 (the fourth Fermat number, 2 to the power 16 plus 1). The number 65537 is prime, has only two bits set (which makes modular exponentiation fast), and is large enough to defeat attacks based on small e (such as the Hasted attack). The number 3 was used historically but is now avoided because it is vulnerable to broadcast attacks.

Step 5: Compute the private exponent d = e to the power minus 1 modulo lambda(n). The private exponent is the multiplicative inverse of e modulo lambda(n), which exists because e and lambda(n) are coprime (e is prime and greater than the smaller of p-1 and q-1).

Step 6: Optionally compute the Chinese Remainder Theorem (CRT) parameters: dP = d modulo (p-1), dQ = d modulo (q-1), and qInv = q to the power minus 1 modulo p. These parameters speed up RSA decryption by a factor of 4 by allowing the modular exponentiation to be done modulo p and modulo q separately and then combined.

Step 7: The public key is (n, e). The private key is (n, d) or, with CRT, (n, d, p, q, dP, dQ, qInv). The public key can be shared; the private key must be kept secret.

Java Program for RSA Key Pair Generation with Strong Primes

import java.math.BigInteger;
import java.security.KeyPair;
import java.security.KeyPairGenerator;
import java.security.SecureRandom;
import java.security.interfaces.RSAPrivateCrtKey;
import java.security.interfaces.RSAPublicKey;
import java.util.Base64;

public class RsaKeyGenDemo {

    private static final BigInteger TWO = BigInteger.valueOf(2);
    private static final BigInteger ONE = BigInteger.ONE;
    private static final BigInteger E = BigInteger.valueOf(65537); // 2^16 + 1

    // Miller-Rabin probabilistic primality test with `rounds` rounds.
    // The probability of a composite being declared prime is < 4^-rounds.
    static boolean isProbablePrime(BigInteger n, int rounds, SecureRandom rng) {
        if (n.compareTo(ONE) <= 0) return false;
        if (n.compareTo(TWO) == 0) return true;
        if (n.testBit(0) == false) return false; // even and > 2 --> composite

        // Small primes check.
        int[] small = {3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47};
        for (int p : small) {
            if (n.equals(BigInteger.valueOf(p))) return true;
            if (n.mod(BigInteger.valueOf(p)).equals(BigInteger.ZERO)) return false;
        }

        // Write n-1 = d * 2^r with d odd.
        BigInteger d = n.subtract(ONE);
        int r = 0;
        while (d.mod(TWO).equals(BigInteger.ZERO)) {
            d = d.divide(TWO);
            r++;
        }

        for (int i = 0; i < rounds; i++) {
            BigInteger a;
            do {
                a = new BigInteger(n.bitLength(), rng);
            } while (a.compareTo(TWO) < 0 || a.compareTo(n.subtract(TWO)) >= 0);

            BigInteger x = a.modPow(d, n);
            if (x.equals(ONE) || x.equals(n.subtract(ONE))) continue;

            boolean composite = true;
            for (int j = 0; j < r - 1; j++) {
                x = x.modPow(TWO, n);
                if (x.equals(n.subtract(ONE))) {
                    composite = false;
                    break;
                }
            }
            if (composite) return false;
        }
        return true;
    }

    // Generate a probable prime of the given bit length with a strong-prime check.
    static BigInteger generateStrongPrime(int bits, SecureRandom rng) {
        while (true) {
            BigInteger p = new BigInteger(bits, 64, rng); // 64 Miller-Rabin rounds
            if (!isProbablePrime(p, 8, rng)) continue;
            // Strong-prime check: p-1 must have a large prime factor.
            BigInteger pMinus1 = p.subtract(ONE);
            BigInteger largeFactor = findLargePrimeFactor(pMinus1, bits / 4, rng);
            if (largeFactor != null) {
                return p;
            }
        }
    }

    private static BigInteger findLargePrimeFactor(BigInteger n, int minBits, SecureRandom rng) {
        // Trial divide small primes; then check the remaining cofactor for primality.
        int[] small = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47};
        BigInteger rem = n;
        for (int p : small) {
            while (rem.mod(BigInteger.valueOf(p)).equals(BigInteger.ZERO)) {
                rem = rem.divide(BigInteger.valueOf(p));
            }
        }
        if (rem.bitLength() >= minBits && isProbablePrime(rem, 8, rng)) {
            return rem;
        }
        return null;
    }

    static KeyPair generateRsaKeyPair(int bits, SecureRandom rng) {
        int halfBits = bits / 2;
        BigInteger p, q, n;
        while (true) {
            p = generateStrongPrime(halfBits, rng);
            q = generateStrongPrime(halfBits, rng);
            if (p.equals(q)) continue;
            n = p.multiply(q);
            if (n.bitLength() != bits) continue; // ensure exact bit length
            // Fermat factorization check: |p - q| must be large.
            if (p.subtract(q).abs().bitLength() < halfBits - 8) continue;
            break;
        }
        BigInteger pMinus1 = p.subtract(ONE);
        BigInteger qMinus1 = q.subtract(ONE);
        BigInteger lambda = pMinus1.multiply(qMinus1).divide(pMinus1.gcd(qMinus1)); // lcm
        if (!lambda.gcd(E).equals(ONE)) {
            // 65537 divides lambda; rare but possible; restart.
            return generateRsaKeyPair(bits, rng);
        }
        BigInteger d = E.modInverse(lambda);
        BigInteger dP = d.mod(pMinus1);
        BigInteger dQ = d.mod(qMinus1);
        BigInteger qInv = q.modInverse(p);

        java.security.spec.RSAPublicKeySpec pubSpec = new java.security.spec.RSAPublicKeySpec(n, E);
        java.security.spec.RSAPrivateCrtKeySpec privSpec = new java.security.spec.RSAPrivateCrtKeySpec(
            n, E, d, p, q, dP, dQ, qInv);
        try {
            java.security.KeyFactory kf = java.security.KeyFactory.getInstance("RSA");
            return new KeyPair(kf.generatePublic(pubSpec), kf.generatePrivate(privSpec));
        } catch (Exception ex) {
            throw new RuntimeException(ex);
        }
    }

    public static void main(String[] args) throws Exception {
        SecureRandom rng = new SecureRandom();

        // Manual implementation: 2048-bit RSA key pair.
        KeyPair manual = generateRsaKeyPair(2048, rng);
        RSAPublicKey pub = (RSAPublicKey) manual.getPublic();
        RSAPrivateCrtKey priv = (RSAPrivateCrtKey) manual.getPrivate();
        System.out.println("=== Manual 2048-bit RSA key pair ===");
        System.out.println("Modulus bit length: " + pub.getModulus().bitLength());
        System.out.println("Public exponent   : " + pub.getPublicExponent());
        System.out.println("Private exponent d: " + Base64.getEncoder().encodeToString(priv.getPrivateExponent().toByteArray()).substring(0, 32) + "...");
        System.out.println("CRT p bit length   : " + priv.getPrimeP().bitLength());
        System.out.println("CRT q bit length   : " + priv.getPrimeQ().bitLength());

        // JDK-standard implementation: KeyPairGenerator.
        KeyPairGenerator kpg = KeyPairGenerator.getInstance("RSA");
        kpg.initialize(2048, rng);
        KeyPair jdk = kpg.generateKeyPair();
        System.out.println();
        System.out.println("=== JDK KeyPairGenerator 2048-bit RSA key pair ===");
        RSAPublicKey jdkPub = (RSAPublicKey) jdk.getPublic();
        System.out.println("Modulus bit length: " + jdkPub.getModulus().bitLength());
        System.out.println("Public exponent   : " + jdkPub.getPublicExponent());
        System.out.println("Algorithm         : " + jdkPub.getAlgorithm());
        System.out.println("Format            : " + jdkPub.getFormat());
    }
}

Code Explanation Line by Line

The class RsaKeyGenDemo declares three constants: TWO and ONE as BigInteger helpers and E as the public exponent 65537. The isProbablePrime method implements the Miller-Rabin probabilistic primality test with `rounds` rounds, which means the probability of a composite being declared prime is less than 4 to the power minus rounds. The test writes n-1 = d times 2 to the power r with d odd and checks whether a to the power d modulo n is 1 or -1, or whether repeated squaring reaches -1. The method also does a quick small-prime check before the Miller-Rabin rounds to short-circuit the obvious composites.

The generateStrongPrime method generates a probable prime of the given bit length using the BigInteger constructor with 64 Miller-Rabin rounds (which is overkill but safe), then runs the strong-prime check. The strong-prime check looks for a large prime factor of p-1, which is the defense against the Pollard p-1 factoring algorithm. The findLargePrimeFactor method trial-divides by small primes and then checks whether the remaining cofactor is a prime of the required bit length. The exact definition of "strong prime" varies; this implementation is a simple version.

The generateRsaKeyPair method generates two strong primes p and q of half the desired bit length, computes the modulus n = p times q, and verifies n has the exact desired bit length. The Fermat factorization check rejects pairs where p and q are too close together (which would make Fermat's factorization method feasible). The method computes the Carmichael totient lambda(n) = lcm(p-1, q-1) and the private exponent d = e to the power minus 1 modulo lambda. The CRT parameters dP, dQ, and qInv are computed for the CRT optimization.

The main method runs both implementations: the manual generateRsaKeyPair and the JDK-standard KeyPairGenerator.getInstance("RSA").initialize(2048, rng).generateKeyPair(). The JDK implementation is the production way to generate RSA keys in Java; the manual implementation is the educational way that makes the algorithm transparent. The output shows that both produce a 2048-bit modulus and use the public exponent 65537.

Sample Input and Output

=== Manual 2048-bit RSA key pair ===
Modulus bit length: 2048
Public exponent   : 65537
Private exponent d: MV91...base64-prefix-here...
CRT p bit length   : 1024
CRT q bit length   : 1024

=== JDK KeyPairGenerator 2048-bit RSA key pair ===
Modulus bit length: 2048
Public exponent   : 65537
Algorithm         : RSA
Format            : X.509

The manual implementation produces a 2048-bit modulus with two 1024-bit primes and the standard public exponent 65537. The JDK implementation produces the same parameters and the standard X.509 SubjectPublicKeyInfo format for the public key. The KeyPairGenerator is the production way; the manual implementation is the educational way.

Common Mistakes to Avoid

The first mistake is using too small a key. RSA-1024 is no longer considered secure; NIST SP 800-57 recommends 2048 bits minimum for new keys and 3072 bits for keys that need to remain secure after 2030. The 1024-bit RSA keys used in some legacy systems can be factored with significant resources but are within reach of nation-state adversaries.

The second mistake is using a small public exponent. The number 3 was used historically because it makes encryption fast, but it is vulnerable to broadcast attacks: if the same plaintext is encrypted with three different RSA keys all with e=3, the plaintext can be recovered by the Chinese Remainder Theorem. The number 65537 is the modern recommendation; it has only two bits set (which keeps modular exponentiation fast) and is large enough to defeat the small-e attacks.

The third mistake is generating p and q too close together. Fermat's factorization method factors n when p and q are close: it searches for an integer x such that x to the power 2 minus n is a perfect square, which is feasible when p and q differ by less than about 2 to the power half-bit. The fix is to verify the difference between p and q is large after generation.

The fourth mistake is using the Euler totient phi(n) = (p-1)(q-1) instead of the Carmichael totient lambda(n) = lcm(p-1, q-1). Both work mathematically (the private exponent d computed either way is a valid inverse of e modulo lambda), but the Carmichael totient gives a smaller d, which is slightly faster. The SunRsaSign provider uses the Carmichael totient in modern JDK versions.

Real-World Applications

RSA is the most widely deployed asymmetric cryptographic primitive in the world. TLS 1.3 uses RSA for signature verification in the certificate chain (the server's certificate is signed with RSA-SHA256 or ECDSA-SHA256). SSH uses RSA as one of the default key types (the rsa-sha2-256 and rsa-sha2-512 algorithms, which use SHA-2 instead of the obsolete SHA-1). PGP and S/MIME email use RSA for the public-key encryption layer.

The Java KeyPairGenerator for RSA is the standard way to generate RSA keys in Java applications. The Spring Security OAuth2 library uses it to generate the JWT signing key; the BouncyCastle library uses it for the RSA keys in the CMS and S/MIME encryption layers. The JDK also exposes the KeyFactory for RSA, which can convert between the standard X.509 SubjectPublicKeyInfo and PKCS8 PrivateKeyInfo encodings and the Java RSAPublicKey and RSAPrivateKey interfaces.

JWT (JSON Web Token) signing with RS256 (RSASSA-PKCS1-v1_5 with SHA-256) is a common deployment pattern. The JWT header identifies the algorithm as RS256; the verifier uses the public key (typically distributed as a JWK, JSON Web Key) to verify the signature. The production recommendation is to use 2048-bit keys with RS256 or 3072-bit keys with RS384 for keys that need to remain secure after 2030.

The rsa key generation java tutorial in this post shows both the educational manual implementation and the production JDK KeyPairGenerator. New designs should use the JDK KeyPairGenerator with at least 2048 bits; the manual implementation is best read as a lesson in how RSA works under the hood. For new designs that need asymmetric signatures, ECDSA (covered in a separate tutorial) offers smaller keys and faster signing for equivalent security; EdDSA (also covered separately) offers deterministic signatures and side-channel resistance.

Conclusion

In this rsa key generation java tutorial we built a manual RSA key pair generator with strong primes and the Miller-Rabin primality test, matched it against the JDK KeyPairGenerator, and explained the role of the public exponent 65537, the Carmichael totient, and the CRT parameters. RSA is the most widely deployed asymmetric primitive in the world; for new designs, use 2048-bit keys minimum and 3072-bit for keys that need to remain secure after 2030. Next, study the RSA signature tutorial, the DSA and ECDSA tutorials, and the EdDSA tutorial.