GO实现简单的RSA加密解密

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

/******************
*
*	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)

输入待加密解密数据:1213
素数p=103 q=127; n= p*q=13081; l=2142; e=5; d=857
加密后的结果: 11972
解密后的结果 1213