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;
最后的 d 就是算出来的 d.
整个过程使用递归的思想可以很好地计算出最后的 d
实现
// @author 我的我的// @date // @desc rsa 算法的简单实现package mainimport ("fmt""math")type (// 64 位 平台 64 位// 整 64 位以上长度的需要自己实现了, 参考 IEEE[triple E]754PublicKey struct {
E int}
PrivateKey struct {
D int}
MiniRSA struct {
PublicKey PublicKey `json:"public_key"`PrivateKey PrivateKey `json:"-"`N int `json:"n"`}
)func main() {var p, q, e, x, y int = 47, 71, 79, 0, 0// 判断 p q 是否为素数if !(isPrime(p) && isPrime(q)) {panic(fmt.Sprintf("isPrime(%d) = %v and isPrime(%d) = %v need isPrime", p, isPrime(p), q, isPrime(q)))
}
N := p * q
setaN := (p - 1) * (q - 1)if gcd(e, setaN) > 1 || N < e {panic("e 要 与 setaN 互质 并且小于 N")
}
extGCD(e, setaN, &x, &y)// 得出公钥和私钥miniRSA := MiniRSA{PrivateKey: PrivateKey{D: x}, PublicKey: PublicKey{E: e}, N: N}
fmt.Printf("miniRSA %#v\n", miniRSA)
plainText := 2020cipherText := enc(plainText, miniRSA.PublicKey.E, miniRSA.N)
fmt.Println("明文:", plainText, "\t密文: ", cipherText, "\t解密:", dec(cipherText, miniRSA.PrivateKey.D, miniRSA.N))
plainText = 233cipherText = enc(plainText, miniRSA.PublicKey.E, miniRSA.N)
fmt.Println("明文:", plainText, "\t密文: ", cipherText, "\t解密:", dec(cipherText, miniRSA.PrivateKey.D, miniRSA.N))
}// 求最大公约数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
}// 拓展的欧几里得算法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
}// 判断素数func isPrime(prime int) bool {// 1 不是素数flag := truefor i := 2; i <= int(math.Sqrt(float64(prime))); i++ {if prime%i == 0 {
fmt.Println(prime, i)
flag = falsebreak}
}return flag
}// 使用公钥加密func enc(plainText int, e, n int) int {return powMod(plainText, e, n)
}// 使用私钥来解密func dec(cipherText int, d, n int) int {return powMod(cipherText, d, n)
}// 快速幂问题func quickPow(a, b int) int {// 不考虑小于零if b == 0 {return 1}
ans := quickPow(a, b/2)
ans *= ansif b%2 == 1 {
ans *= a
}return ans
}// 同余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
}// end 复制代码总结
- RSA 算法的求公钥对和私钥对的整个过程
- RSA 使用公钥加密
- RSA 算法使用私钥解密
- 可以同余定理来避免溢出问题
- 使用快速幂思想来加速加密和解密的过程
有疑问加站长微信联系（非本文作者）
