golang 实现 RSA 的加密解密

本文摘自网络，作者，侵删。

RSA 介绍

RSA 由 Ron Rivest, Adi Shamir 和 Lennard Adleman 三位大佬在 1977 年提出的算法。

RSA 加密算法是一种非对称机密算法, 对极大整数做因数分解的难度决定了RSA算法的可靠性。

公钥与私钥的产生

选取两个大的质数： p 和 q
计算 n = p * q
计算小于 n 并且与 n 互质的整数的个数, 使用欧拉公式可以计算ο(n)=(p−1)∗(q−1)
随机选择加密的私钥 e, 使 1 < e < ο(n), 并且 e 与 ο(n) 互质
使用欧几里得算法计算解密私钥 d, 使 ed = 1 (mod(ο(n)))
公钥对 {e,n} PK(需要公开出去的); 私钥对 {e,n} 为 SK(切不可泄露)

RSA 如何加密

密文 = 明文emod n通过公式, 可以知道 RSA 的密文是通过明文的 e 次方再对 n 进行取模得到的。这个加密过程只用到乘法和除法运算。公钥对 = {e, n}

RSA 如何解密

明文 = 密文d mod n 原理是: 密文的 d 次方，然后对 n 取模得到明文。私钥对 = {d,n}

素数

素数指在大于 1 自然数中，除了 1 和该数本身外，无法被其他自然数整除的数。(1 不是素数)

func isPrime(prime int) bool {
    flag := truefor i := 2; i <= int(math.Sqrt(float64(prime))); i++ {if prime%i == 0 {
            flag = falsebreak}
    }return flag
}复制代码

最大公因数

指的是能够整除多个整数的最大正整数

func gcd(a, b int) int {if a == 0 || b == 0 {return 0}// 直到 a == b 为止for a != b {if a > b {
            a -= b
        } else {
            b -= a
        }
    }return a
}复制代码

扩展欧几里得算法

裴蜀定理: 给定二个整数 a、b, 必存在整数 x、y 使得 ax + by = gcd(a,b), 其中 gcd(a,b) 结果为 a 和 b 的最大公约数。

func extGCD( a , b int , x , y * int ) int {if b == 0 {
        *x = 1*y = 0return a
    }
    d := extGCD(b, a%b, x, y)
    *x, *y = *y, *x-a/b*(*y)return d
}复制代码

同余

同余是数论上一种等价关系。当两个整数除以一个正整数，若得相同的余数，则二整数同余。

举个???? ：

3 % 4 ≡ 5 % 4

快速幂同模

func powMod(a, n, m int) int {// 不考虑小于零if n == 0 {return 1}
    
    x := powMod(a, n/2, m)
    ans := x * x % mif n%2 == 1 {
        ans = ans * a % m
    }return ans
}复制代码

两个数互质

if gcd(a,b ) == 1 {
  fmt.Println("a b 互质")
}复制代码

例子

例子: 令 p = 47, q = 71, 求用到的 RSA 算法加密用到的公钥和私钥

p 与 q 都是较大的质数

计算过程：

计算 n = p * q = 47 * 71 = 3337;
计算小于 n 并且与 n 互质的个数 ο(n)=(p−1)∗(q−1) ; ο(n)=46∗70 = 3220;
随机选择 e = 79 (e需要满足 1 < e < n,并且 e 与 ο(n) 互质);
则私钥 d 满足: 79 * d mod 3220 = 1;

由于 e 与 n 互质, 所以满足 79 * d - k * 3220 = 1

使用辗转相除法计算 d;

a. 式子(4) 可以表示为 79 * d - 3220 * k = 1 (其中 k 为正整数);

b. 将 3220 对 79 取模得到余数 60 代替 3220，则变成 79 * d - 60 *k = 1;

c. 同理，将 79 对 60 取模得到余数 19 代替 79，则变成 19 * d - 60 *k = 1;

d. 同理，将 60 对 19 取模得到余数 3 代替 60, 则变成 19 * d - 3 * k = 1;

e. 同理，将 19 对 3 取模得到余数 1 代替 19, 则变成 1 * d - 3 * k =1;

当 d 的系数变成了 1 的时候, (d - 3 * k = 1)

令 k = 0, 代入式子 (e) 中, 得到 d =1;

将 d = 1 代入式子(d) 中，得到 k = 6;

将 k = 6 代入式子(c) 中，得到 d = 19;

将 d = 19 代入式子(b) 中，得到 k =25;

将 k =25 代入式子(a) 中，得到 d = 1019;