GO实现简单的RSA加密解密

xuthus5 · · 4420 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。
## 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 ```

有疑问加站长微信联系(非本文作者))

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:701969077

4420 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传