Go实现一个在数学问题上的RSA算法

引言

本文撰写于 2019-05-12 22:50:39

RSA加密

RSA的加密过程可以使用一个通式来表达

密文 = 明文E % N

也就是说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的解密同样可以使用一个通式来表达

明文 = 密文D % N

也就是说对密文进行D次方后除以N的余数就是明文,这就是RSA解密过程。知道D和N就能进行解密密文了,所以D和N的组合就是私钥

私钥 = (D,N)

从上述可以看出RSA的加密方式和解密方式是相同的,加密是求“E次方的mod N”;解密是求“D次方的mod N” 此处D是解密(Decryption)的首字母;N是数字(Number)的首字母。

设计原理和过程参考 带你彻底理解RSA算法原理_dbs1215的专栏-CSDN博客_rsa算法

  1. RSA加密密文=明文^E mod N; 公钥=(E,N)
  2. RSA解密明文=密文^D mod N; 私钥=(D,N)
  3. 密钥对: (E,D,N)
  4. N= p * q ;p,q为质数
  5. L=lcm(p-1,q-1);L为p-1、q-1的最小公倍数
  6. E:1 < E < L,gcd(E,L)=1;E,L最大公约数为1(E和L互质)
  7. 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