如何使用Java手写实现一个RSA加密算法

8到16位RSA实现

RSA这种算法非常可靠，密钥越长，它就越难破解。

• 第一步，随机选择两个不相等的质数p和q。
• 第二步，计算p和q的乘积n。
• 第三步，计算n的欧拉函数φ(n)。
• 第四步，随机选择一个整数e，条件是1< e < φ(n)，且e与φ(n) 互质。
• 第五步，计算e对于φ(n)的模反元素d。
• 第六步，将n和e封装成公钥，n和d封装成私钥。

实现效果

代码

密钥的父类：

public class Key {
    private int n;

    public int getN() {
        return n;
    }

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

私钥：

public class PrivateKey extends Key {
    private int d;

    public int getD() {
        return d;
    }

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

    PrivateKey(int n, int d) {
        setN(n);
        this.d = d;
    }
}

公钥：

public class PublicKey extends Key {
    private int e;

    public int getE() {
        return e;
    }

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

    PublicKey(int n, int e) {
        setN(n);
        this.e = e;

    }
}

密钥对：

public class KeyPair {

    private PrivateKey privateKey;
    private PublicKey publicKey;

    public KeyPair(PublicKey publicKey, PrivateKey privateKey) {
        this.publicKey = publicKey;
        this.privateKey = privateKey;
    }

    public PrivateKey getPrivateKey() {
        return privateKey;
    }


    public PublicKey getPublicKey() {
        return publicKey;
    }

}

密钥生成器：

public class KeyGenerator {

    private int keyLength;
    private final int DEFAULT_KEY_LENGTH = 8;

    public KeyGenerator() {
        keyLength = DEFAULT_KEY_LENGTH;
    }

    public KeyGenerator(int keyLength) {
        this.keyLength = keyLength;
    }

    public PublicKey generatePublicKey(int n, int e) {
        return new PublicKey(n, e);
    }

    public PrivateKey generatePrivateKey(int n, int d) {
        return new PrivateKey(n, d);
    }

    public KeyPair generateKeys() {
        int maxN = (1 << keyLength) - 1;
        int minN = 1 << keyLength - 1;

        //p, q两个质数
        int p, q, n;

        //利用二分法，求合适的素数索引最大值
        int pivot;
        int start = 0;
        int end = PrimeTable.primes.length;
        do {
            //防止直接加和平均溢出
            pivot = start + (end - start) >> 1;
            if (PrimeTable.primes[pivot] > maxN) {
                end = pivot - 1;
            } else if (PrimeTable.primes[pivot] < maxN) {
                start = pivot + 1;
            }else {
                break;
            }
        } while (PrimeTable.primes[pivot + 1] > maxN);

        //利用循环，从合适的素数中，挑选两个乘积在maxN和minN之内的数
        do {
            p = PrimeTable.primes[(int) (Math.random() * (pivot - 1))];
            q = PrimeTable.primes[(int) (Math.random() * (pivot - 1))];
            n = p * q;
        } while (n > maxN || n < minN);

        int phiN = (p - 1) * (q - 1);
        int e;

        do {
            e = (int) (1 + Math.random() * (phiN - 1));
        } while (e == 1 || !coprime(e, phiN));

        int y = 0;
        while ((++y * phiN + 1) % e != 0) {}
        int d = (y * phiN + 1) / e;

        PrivateKey prik = generatePrivateKey(n, d);
        PublicKey pubk = generatePublicKey(n, e);
        return new KeyPair(pubk, prik);
    }

    /**
     * 判断两个数是否互质
     * 用大数除以小数，如果除得的余数与其中较小数互质
     * 则原来两个数是互质数。
     * 如：317和52，317÷52＝6……5，因余数5与52互质，则317和52是互质数。
     * @param smallNumber 小的数
     * @param largeNumber 大的数
     * @return 如果是质数返回true，否则返回false
     */
    public boolean coprime(int smallNumber, int largeNumber) {
        while (largeNumber % smallNumber > 0) {
            int temp = smallNumber;
            smallNumber = largeNumber % smallNumber;
            largeNumber = temp;
        }
        return smallNumber == 1;
    }
}

RSA的实现：

public class Rsa {

    public static List<Long> encrypt(PublicKey publicKey, String plainText) {
        char[] chars = plainText.toCharArray();
        List<Long> list = new ArrayList<>();
        for (char ch : chars) {
            int e = publicKey.getE();
            int n = publicKey.getN();

            long qw = (int)ch;
            long c = quickMod(qw, e, n);
            //此方法无效，需另辟蹊径，目前解决方案：int换成long
            /*if (c <= 0) {
                //杜绝出现负数
                c = (c + n) % n;
                System.out.println("出现了负数，ch is " + ch + ", e is " + e + ", n is " + n);
            }*/
            list.add(c);
        }
        return list;
    }

    public static String decrypt(PrivateKey privateKey, List<Long> cipher) {
        int d = privateKey.getD();
        int n = privateKey.getN();
        StringBuilder sb = new StringBuilder();
        for (long cipherUnit : cipher) {
            long m = quickMod(cipherUnit, d, n);
            sb.append((char) m);
        }
        return sb.toString();
    }

    /**
     * 快速模运算
     * m^e % n （^是次方的意思）
     * @param m 底数
     * @param e 次方
     * @param n 模
     * @return 余数
     */
    public static long quickMod(long m, long e, long n) {
        long res = 1;
        m = m % n;
        while (e > 0) {
            if (e % 2 == 1) {
                res = (res * m) % n;
            }
            m = (m * m) % n;
            e = e >> 1;
        }
        return res;
    }

}

试运行：

public class Main {

    public static void main(String[] args) {
        KeyGenerator generator = new KeyGenerator(16);
        KeyPair keyPair = generator.generateKeys();
        PublicKey publicKey = keyPair.getPublicKey();
        PrivateKey privateKey = keyPair.getPrivateKey();

        String plainText = "Hello RSA";

        System.out.println("plain text is: " + plainText);

        List<Long> cipher = Rsa.encrypt(publicKey, plainText);

        System.out.println("cipher is: " + cipher);

        String decrypt = Rsa.decrypt(privateKey, cipher);
        System.out.println("decrypt result is: " + decrypt);

    }
}

Junit Test：

public class RsaTest {

    private KeyPair keys = new KeyGenerator(16).generateKeys();
    private LinkedHashSet<String> stringSet = new LinkedHashSet<>();

    @Before
    public void setUp() {
        stringSet.add("Hello");
        stringSet.add("hello");
        stringSet.add("what are you doing");
        stringSet.add("hi!");
        stringSet.add("1234");
        stringSet.add("!@#$%^&*()_+");
        stringSet.add("hey");
        stringSet.add("我是中文");
        stringSet.add("(【pic】`・ω・【pic】)");
    }

    @Test
    public void testDecrypt1() {
        for (String str : stringSet) {
            System.out.println(str);
            assertTrue(str.equals(
                    Rsa.decrypt(keys.getPrivateKey(), Rsa.encrypt(keys.getPublicKey(), str))));
        }
    }

    @Test
    public void testEncrypt1() {
        System.out.println(
                Rsa.encrypt(keys.getPublicKey(), "hello")
        );
    }

    @Test
    public void testQuickMod() {
        assertEquals(1, Rsa.quickMod(2, 4, 3));
        assertEquals(3, Rsa.quickMod(3, 3, 6));
        System.out.println(Rsa.quickMod('A', 28107, 48367));
    }

}

代码下载

点击下载RsaImpl.rar