## RSA加密
RSA的加密过程可以使用一个通式来表达
> 密文=明文EmodN
也就是说RSA加密是对明文的E次方后除以N后求余数的过程。就这么简单?对,就是这么简单。
从通式可知,只要知道E和N任何人都可以进行RSA加密了,所以说E、N是RSA加密的密钥,也就是说E和N的组合就是公钥,我们用(E,N)来表示公钥
>公钥=(E,N)
不过E和N不并不是随便什么数都可以的,它们都是经过严格的数学计算得出的,关于E和N拥有什么样的要求及其特性后面会讲到。顺便啰嗦一句E是加密(Encryption)的首字母,N是数字(Number)的首字母
## RSA解密
RSA的解密同样可以使用一个通式来表达
> 明文=密文DmodN
也就是说对密文进行D次方后除以N的余数就是明文,这就是RSA解密过程。知道D和N就能进行解密密文了,所以D和N的组合就是私钥
> 私钥=(D,N)
从上述可以看出RSA的加密方式和解密方式是相同的,加密是求“E次方的mod N”;解密是求“D次方的mod N”
此处D是解密(Decryption)的首字母;N是数字(Number)的首字母。
设计原理和过程参考 [https://blog.csdn.net/dbs1215/article/details/48953589](https://blog.csdn.net/dbs1215/article/details/48953589)
```go
/******************
*
* RSA加密:密文=明文^E mod N 公钥=(E,N)
* RSA解密:明文=密文^D mod N 私钥=(D,N)
* 密钥对:(E,D,N)
* N= p * q ;p,q为质数
* L=lcm(p-1,q-1) ;L为p-1、q-1的最小公倍数
* E:1 < E < L,gcd(E,L)=1;E,L最大公约数为1(E和L互质)
* D:1 < D < L,E*D mod L = 1
*
*******************/
package main
import (
"crypto/rand"
"fmt"
"math/big"
)
//生成小素数
func GetPrime() *big.Int {
prime,err := rand.Prime(rand.Reader,7)
if err != nil {
fmt.Println("素数生成出错:",err)
return nil
}
return prime
}
//最大公约数
func GCD(p,q *big.Int) *big.Int {
var t = big.NewInt(0)
return t.GCD(big.NewInt(1),big.NewInt(1),p,q)
}
//生成e E和φ(n)互为质数
func RandExponent(l *big.Int) *big.Int{
var t = big.NewInt(2)
var gcd *big.Int
for t.Cmp(l) <= 0 {
gcd = GCD(t,l)
if gcd.Cmp(big.NewInt(1)) == 0 {
return t
}
t = big.NewInt(0).Add(t,big.NewInt(1))
}
return nil
}
//求摸余一
func ModOne(l,e *big.Int) *big.Int {
var t = big.NewInt(2)
var result,mul *big.Int
for t.Cmp(l) < 0 {
mul = big.NewInt(0).Mul(e,t)
result = big.NewInt(0).Mod(mul,l)
if result.Cmp(big.NewInt(1)) == 0 {
return t
}
t = big.NewInt(0).Add(t,big.NewInt(1))
}
return nil
}
func main() {
//===============输入待加密解密数据=================
var mm string
fmt.Printf("输入待加密解密数据:")
_, _ = fmt.Scanf("%s", &mm)
//---------------生成密钥对--------------
//1.准备两个小素数 且不能相等
var p = GetPrime()
//var p = big.NewInt(17)
var q = GetPrime()
for p.Int64() == q.Int64() {
q = GetPrime()
}
//var q = big.NewInt(19)
//2.求N = p * q
var n = big.NewInt(0).Mul(p,q)
//3.求L = φ(n) = (p-1) * (q-1)
//3.1得到最大公约数
var gcd = GCD(big.NewInt(0).Add(p,big.NewInt(-1)),big.NewInt(0).Add(q,big.NewInt(-1)))
//3.2得到 (p-1) * (q-1)
var f = big.NewInt(0).Mul(big.NewInt(0).Add(p,big.NewInt(-1)),big.NewInt(0).Add(q,big.NewInt(-1)))
//3.3得到最小公倍数
var l = big.NewInt(0).Div(f,gcd)
//3.求E:E是一个比1大比L小的数,E和L的最大公约数为1
var e = RandExponent(l)
//4.求D:由数E计算出来的。D、E和L之间必须满足 1 < D < L ;; E*D mod L = 1
var d = ModOne(l,e)
fmt.Printf("素数p=%d q=%d; n= p*q=%d; l=%d; e=%d; d=%d\n",p,q,n,l,e,d)
//-------------开始加密------------------
//1.准备待加密数据 mm
//2.content = mm^e mod n 加密
//2.1 将待加密内容二进制化
var content,_ = big.NewInt(0).SetString(mm,0)
//2.2 计算 调用exp函数:将z = (content^y mod n) 并返回z
var z big.Int
z.Exp(content,e,n)
//2.3 输出密文的字符串
fmt.Println("加密后的结果:",z.String())
//-------------开始解密------------------
//3.1 s = z^d mod n 将待解密的数据二进制化
var scontent = big.NewInt(0).SetInt64(z.Int64())
//3.2 计算 调用exp函数:将s = (scontent^d mod n) 并返回s
var s big.Int
s.Exp(scontent,d,n)
fmt.Println("解密后的结果",s.String())
}
```
## 测试
int64类型在运算较大的数据时会溢出,导致部分数据无法被正确的输出,遂只计算最高4为数(阈值3326),我们任然可以才采取其他的措施来处理整型溢出问题,比如拼接字符串,将需要加密的字符切割,分别加密后解密。亦或者构造更加完美的两个大素数。通过调整素数生成函数GetPrime的语句的第二个参数 “6” 可生成更高位数的大素数`prime,err := rand.Prime(rand.Reader,X)`
```shell
输入待加密解密数据:1213
素数p=103 q=127; n= p*q=13081; l=2142; e=5; d=857
加密后的结果: 11972
解密后的结果 1213
```
有疑问加站长微信联系(非本文作者))