RSA算法

@[TOC]

一、生成公钥和私钥

1、随机生成两个随机素数P，Q
2、将P、Q两个素数相乘得到一个数N，即N=P*Q（需要公开）
3、将P、Q分别减1再相乘得到一个数T，即T=(P-1)*(Q-1)
4、选择一个数E，E满足和T互质且E小于T
5、根据DE mod T = 1计算出密钥D
6、通过以上步骤可以得到N，E，D这3个数字，其中（N、E）作为公钥，（N、D）作为私钥（公钥和私钥可以互换）

二、加密和解密

接受方将生成的公钥（N，E）对外发布
1、用公钥加密
发送方用接受到的公钥（N，E）对密文M加密
密文：M
加密：M^E <font size=3>mod</font> N = C
明文：C
2、用私钥解密
接受方用持有私钥（N，D）对明文C解密
明文：C
解密：C^D <font size=3>mod</font> N = M
密文：M

三、java实现

代码链接

public class RSA {
    private int N;  // 和公钥E一起分发出去
    private int E; // E是公钥，随机选取（必须和T互质）
    private int D; // D是密钥（D和E可以互换）
    public RSA() {
        createKey();
    }
    // 产生密钥
    private void createKey() {
        // 产生两个随机的素数
        int p=61,q=53;
        // 计算N和T
        N = p*q;
        int t = (p-1)*(q-1);
        // 选择E（和T互质就行）
        E = 17;
        // 计算D
        int[] r = new int[2];
        Gcd.extendGcd(E, t, r); // 调用扩充欧几里得算法计算D
        D = r[0];
        // 调整d（d为正数）
        while(D < 0) D +=t;
    }

    /**
     * 利用公钥对密文m加密
     * @param m 必须是整数，且m必须小于N
     * @return c=pow(m,E)%N
     */
    public int encrypt(int m) { // 注意，这里很容易溢出（虽然此算法已经极度简化了）
        BigInteger bm = BigInteger.valueOf(m);
        return bm.pow(E).mod(BigInteger.valueOf(N)).intValue();
    }

    /**
     * 利用密钥对明文c解密
     * @param c
     * @return m1=pow(c, D)%N
     */
    public int decrypt(int c) { // 同样考虑溢出情况
        BigInteger bc = BigInteger.valueOf(c);
        return bc.pow(D).mod(BigInteger.valueOf(N)).intValue();
    }

    public int getPublicKey() {
        return E;
    }

    public void setPublicKey(int E) {
        this.E = E;
    }

    public int getN() {
        return N;
    }

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

    public static void main(String[] args) {
        RSA rsa = new RSA();
        System.out.println("公钥：E="+rsa.getPublicKey()+",N="+rsa.getN()); // 打印公钥
        int m = 65; // 明文
        System.out.println("密文："+m);
        int c = rsa.encrypt(m); // 对明文m加密，得到密文c
        System.out.println("明文："+c);
        int m1 = rsa.decrypt(c); // 对密文c解密，得到明文m1
        System.out.println("解密出来的密文："+m1);
    }
}

参考

阮一峰的博客RSA算法原理
周颖的《程序员的数学思维修炼》