非对称算法（RSA篇）

概述

RSA加密算法是一种非对称加密算法，在RSA算法中，加密密钥（即公开密钥）PK是公开信息，而解密密钥（即秘密密钥）SK是需要保密的。加密算法E和解密算法D也都是公开的。对极大整数做因数分解的难度决定了RSA算法的可靠性。

加密原理

一、生成公钥和私钥

1. 随机生成两个素数P、Q。
2. 将P、Q两个素数相乘得到一个数N。
3. 计算N的欧拉函数M，M=(P-1)*(Q-1)。
4. 选择一个整数E使其与M互质。
5. 给定一个整数D，使得(E*D)%M=1。
6. 得到N、E、D三个数，其中（N、E）作为公钥，（N、D）作为私钥（公钥和私钥可以互换）。

   二、生成密文

   使用公钥（N、E）对data进行加密。
   加密过程：这里的E相当于公钥

data^E mod N = [data]

三、密文解密

使用私钥（N、D）对密文进行解密。
解密过程：这里的D相当于密钥

[data]^D mod N = data

欧拉定理

注：欧拉函数f(n)表示在小于或等于n的正整数中，有多少个与n互质的数

代码实现

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);
    }
}

代码实现（python）

def isPrime(number):
    import math
    i = 2
    sqrtnum = (int)(math.sqrt(number))
    for i in range(2, sqrtnum + 1):
        if number % i == 0:
            return False
        i = i + 1
    return True

def is_ET_Prime(ee, tt):
    while tt != 0:
        a = ee
        ee = tt
        tt = a % tt
    if ee == 1:
        return True
    else:
        return False
def get_publickey(k, t):
    d = 0
    while ((d * k) % t != 1):
        d += 1
    return d
def encryption(plain, d, n):
    re = (plain ** d) % n

    return re

if __name__ == "__main__":
    print
    "~" * 70
    Flag = False
    while True:
        p = int(input("please input a prime p:"))
        q = int(input("please input a prime q:"))

        if (isPrime(p) and isPrime(q)):
            break
        else:
            print
            "p or q is not prime!"
            continue
    print
    "p=", p, "q=", q
    n = q * p
    t = (q - 1) * (p - 1)
    print("n=", n, "t=", t)
    print("~" * 70)
    Flag == False
    while Flag == False:
        e = int(input("please input a private key:"))
        Flag = is_ET_Prime(e, t)
        if Flag == False:
            print("e is not prime with the t!")
    print("the private key e=", e)
    d = get_publickey(e, t)
    print("the public key d=", d)
    plain = int(ord(input("please input the plain you want to entrypted:")))
    encry = encryption(plain, d, n)
    print("plain", plain, "is encrypted as", encry)
    #print(encry)
    plain1 = encryption(encry, e, n)
    print("encrypt", encry, "is decrypted as", plain1)