javaencryptionrsakey-generator

How to generate keys for RSA in Java


I got this code to encrypt/decrypt some String via RSA. This project is used to understand the encryption and is build only for learning purposes. Until now I always used a fixed key to use my application but now I want to build a method which generates a valid key based on the entered bitsize.

This is my current class:

import java.math.BigInteger;
import java.util.Random;

public class RSAWorker {

    public static BigInteger gcdExtended(BigInteger a, BigInteger b) {
        BigInteger a_cur = BigInteger.ONE;
        BigInteger b_cur = BigInteger.ZERO;
        BigInteger a_next = BigInteger.ZERO;
        BigInteger b_next = BigInteger.ONE;
        BigInteger q;
        BigInteger r;

        do {
            q = a.divide(b);
            r = a.subtract(q.multiply(b));
            BigInteger tmpA = a_next;
            BigInteger tmpB = b_next;
            a_next = a_cur.subtract(q.multiply(a_next));
            b_next = b_cur.subtract(q.multiply(b_next));
            a_cur = tmpA;
            b_cur = tmpB;
            a = b;
            b = r;
        } while (r.intValue() > 0);

        return a_cur;
    }

    public static char separator = '_';
    private BigInteger e = BigInteger.ZERO;
    private BigInteger d = BigInteger.ZERO;
    private BigInteger n = BigInteger.ZERO;

    private ProgressInformant progressSupervisor;

    private void inform(long index, long max) {
        if (progressSupervisor != null) {
            progressSupervisor.prograssAt(Math.round((float) index / max * 100));
        }
    }

    public void generateKeys(int bitSize) {
       e = 65537;
       d = 1873890542004290369;
       n = 11495756297295397069;
    }

    public BigInteger encode(BigInteger c) {
        return c.modPow(e, n);
    }

    public BigInteger decode(BigInteger c) {
        return c.modPow(d, n);
    }

    public String encode(String str) {
        StringBuilder result = new StringBuilder();

        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            result.append(encode(BigInteger.valueOf(c)));
            result.append(separator);
            inform(i + 1, str.length());

            if (Thread.interrupted()) {
                return null;
            }
        }

        return result.toString();
    }

    public String decode(String str) {
        StringBuilder result = new StringBuilder();

        String[] tokens = str.split(separator+"+");

        for (int i = 0; i < tokens.length; i++) {
            String s = tokens[i];
            result.append((char) decode(new BigInteger(s)).intValue());
            inform(i + 1, tokens.length);

            if (Thread.interrupted()) {
                return null;
            }
        }

        return result.toString();
    }

    public ProgressInformant getProgressSupervisor() {
        return progressSupervisor;
    }

    public void setProgressSupervisor(ProgressInformant progressSupervisor) {
        this.progressSupervisor = progressSupervisor;
    }

    public BigInteger getE() {
        return e;
    }

    public void setE(BigInteger e) {
        this.e = e;
    }

    public BigInteger getD() {
        return d;
    }

    public void setD(BigInteger d) {
        this.d = d;
    }

    public BigInteger getN() {
        return n;
    }

    public void setN(BigInteger n) {
        this.n = n;
    }
}

Solution

  • Have a look at this wikipedia artcle: RSA Key Generation

    It shows you step by step how to generate a valid key.

    public void generateKeys(int bitSize) {
        Random rnd = new Random();
        //1
        BigInteger p = BigInteger.probablePrime(bitSize, rnd);
        BigInteger q = BigInteger.probablePrime(bitSize, rnd);
    
        //2
        n = p.multiply(q);
    
        //3
        BigInteger euler = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE));
    
        //4
        BigInteger x = BigInteger.valueOf(65537);
    
        do {
            if (euler.gcd(x).equals(BigInteger.ONE)) {
                e = x;
                //5
                d = gcdExtended(e, euler);
                if (d.signum() == 1) {
                    break;
                }
            }
            x = x.add(BigInteger.ONE);
        } while (true);
    }
    
    1. Choose two distinct prime numbers p and q (via probablePrime)
    2. Compute n = pq
    3. Euler totient function (http://en.wikipedia.org/wiki/Euler%27s_totient_function)
    4. Choose e (as public key exponent)
    5. Determine d, via your already existing gcdExtended method (extended Euclidian algorithm)