● 1.2.1 加密
● 1.2.2 解密
● 1.2.2.1 生成私钥
● 1.2.2.2 解密
● 1.1 RSA加密算法基础
● 1.2 算法优化
● 1.3 多素数
● 1.2 Golang中实现方式
● 2 Golang中Big包
● 2.1.1 Word (
src/math/big/arith.go● 2.1.2 nat (
src/math/big/nat.go● 2.1.3 Int (
src/math/big/int.go● 2.1.4 Rat(
src/math/big/rat.go● 2.1.4 Float(
src/math/big/rat.go● 2.1 类型
1 Golang中RSA加密算法实现
1.1 RSA加密算法基础
RSA加密算法属于非对称加密算法，属于网络的基础安全算法。阮一峰的博文：RSA算法原理(一)和RSA算法原理(二)，非常通俗易懂。在这里简单的归纳总结一下，整个算法分为三个步骤，分别为：生成公钥和密钥；发送方使用公钥生成密文；接收方使用密钥解密。生成公钥和私钥
● 选择两个较大的质数 p 和 q ;● 计算 p 和 q 的乘积 n=p×q ；
● 随机选择整数 e, 保证 1<e<φ(n) 并且 e,φ(n) 互质，其中 φ(n) 为 n 的欧拉函数值；
● 方程 e×d−1=k×φ(n)的一组解：(d,k)；
● 公钥：(n,e)；私钥： (n,d)
公钥加密对于待加密的数值：m, 那么密文: c=memodn。
私钥解密通过(n,d)和密文c，计算得到密文: m=cdmodn。
1.2 算法优化
在解密的算法中，关键点在于计算cd和对于n取模，但是通常情况下，该数是非常大的，因此计算是非常耗时操作。所以对于RSA算法解密的过程有简化的方法。中国剩余定理在*孙子算经*中有下面这么一段话
有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？
换成RSA中就是这样描述：p和q是两个素数，n=p×q, 对于任意(m1,m2),(0≤m21<p,0≤m2<q), 必然存在唯一的整数m,(0≤m<n) 满足 m1=mmodq,m2=mmodp， 所以RSA解密算法中的m=cdmodn, 可以分解为m1=cdmodp,m2=cdmodq, 然后再求得m。对于cdmodp=…=crmodp, 其中r为d除p−1的余数， 即r=dmod(p−1), 令dp=dmod(p−1)，同理dq=dmod(q−1)。同时计算出qinv×q=1modp。在预先计算出结果后，就可快速的解密
● m1=cdpmodp● m2=cdqmodq
● h=(qinv×((m1−m2)modp))modp
● m=m2+h∗q
1.3 多素数
之前讨论的都是两个素数生成加密算法，为了保证n的位数，可以选择超过两个的素数，p,q,r1,r2…,rn，生成公钥和私钥的过程和之前一样，加密和解密的直接算法也是同样的。同样可以使用算法的优化算法。
1.2 Golang中实现方式
在Golang中实现了RSA加密算法：src/crypto/rsa/rsa.go文件中实现了RSA算法。该算法实现上述讨论的内容，但是除此之外，还处理可能出来的问题。如果me的值比n还小，那么c=me，所以根据c很容易的计算出m，因此通常是增加m的值，使之与n接近，PKCS1和OAEP都是很好的方法，在这里不做重点讨论。
1.2.1 加密
公钥的数据结构：
1type PublicKey struct {
2 N *big.Int // modulus
3 E int // public exponent
4}
包含了公钥必须n和e，但是两个是不同的数据类型big.Int和int两种。加密过程也是非常简单
1func encrypt(c *big.Int, pub *PublicKey, m *big.Int) *big.Int {
2 e := big.NewInt(int64(pub.E))
3 c.Exp(m, e, pub.N)
4 return c
5}
其中Exp方法作用c=memodpub.N
1.2.2 解密
私钥的数据结构
1type PrivateKey struct {
2 PublicKey // public part.
3 D *big.Int // private exponent
4 Primes []*big.Int // prime factors of N, has >= 2 elements.
5 // Precomputed contains precomputed values that speed up private
6 // operations, if available.
7 Precomputed PrecomputedValues
8}
embedPrecomputedValues
1type PrecomputedValues struct {
2 Dp, Dq *big.Int // D mod (P-1) (or mod Q-1)
3 Qinv *big.Int // Q^-1 mod P
4 CRTValues []CRTValue
5}
6// 包含了中国余数定理的值
7type CRTValue struct {
8 Exp *big.Int // D mod (prime-1).
9 Coeff *big.Int // R·Coeff ≡ 1 mod Prime.
10 R *big.Int // product of primes prior to this (inc p and q).
11}
DpDqQinvCRTValue1.2.2.1 生成私钥
1func GenerateKey(random io.Reader, bits int) (*PrivateKey, error) {
2 // 生成只有两个2个素数的RSA
3 return GenerateMultiPrimeKey(random, 2, bits)
4}
5func GenerateMultiPrimeKey(random io.Reader, nprimes int, bits int) (*PrivateKey, error){
6 // 设置E的默认值为65537
7 priv := new(PrivateKey)
8 priv.E = 65537
9NextSetOfPrimes:
10 for {
11 // 确定设置还需要的剩余的bit位
12 todo := bits
13 //生成需要需要的bit位的素数
14 for i := 0; i < nprimes; i++ {
15 var err error
16 primes[i], err = rand.Prime(random, todo/(nprimes-i))
17 if err != nil {
18 return nil, err
19 }
20 todo -= primes[i].BitLen()
21 }
22 n := new(big.Int).Set(bigOne)
23 // totient 保存 n 的欧拉函数值
24 totient := new(big.Int).Set(bigOne)
25 pminus1 := new(big.Int)
26 for _, prime := range primes {
27 n.Mul(n, prime)
28 pminus1.Sub(prime, bigOne)
29 totient.Mul(totient, pminus1)
30 }
31 priv.D = new(big.Int)
32 e := big.NewInt(int64(priv.E))
33 // 根据E值计算出D值
34 ok := priv.D.ModInverse(e, totient)
35 //...
36 }
37 // 为解密过程中预先计算
38 priv.Precompute()
39 return priv, nil
40}
在RSA中，公钥中默认为：e=65537，按照所需的素数的个数和生成n的位数生成素数和d，最后进行预先计算操作，以加快解密过程。
1func (priv *PrivateKey) Precompute() {
2 //....
3 priv.Precomputed.Dp = new(big.Int).Sub(priv.Primes[0], bigOne)
4 priv.Precomputed.Dp.Mod(priv.D, priv.Precomputed.Dp)
5
6 priv.Precomputed.Dq = new(big.Int).Sub(priv.Primes[1], bigOne)
7 priv.Precomputed.Dq.Mod(priv.D, priv.Precomputed.Dq)
8
9 priv.Precomputed.Qinv = new(big.Int).ModInverse(priv.Primes[1], priv.Primes[0])
10 //...
11}
PrecomputedDpDqQinv1.2.2.2 解密
1func decrypt(random io.Reader, priv *PrivateKey, c *big.Int) (m *big.Int, err error) {
2 //....
3 if priv.Precomputed.Dp == nil {
4 m = new(big.Int).Exp(c, priv.D, priv.N)
5 } else {
6 // We have the precalculated values needed for the CRT.
7 m = new(big.Int).Exp(c, priv.Precomputed.Dp, priv.Primes[0])
8 m2 := new(big.Int).Exp(c, priv.Precomputed.Dq, priv.Primes[1])
9 m.Sub(m, m2)
10 if m.Sign() < 0 {
11 m.Add(m, priv.Primes[0])
12 }
13 m.Mul(m, priv.Precomputed.Qinv)
14 m.Mod(m, priv.Primes[0])
15 m.Mul(m, priv.Primes[1])
16 m.Add(m, m2)
17 //...
18 }
19 }
20 //...
21 return
22}
如果没有提前计算，那么直接使用公式计算；如果进行已经提前计算值，则按照优化的算法依次计算。
2 Golang中Big包
RSAintint32int64math.bigIntIntRatFloatGoAddSubreceiver2.1 类型
src/math/bigIntFloatRatsrc/math/big/arith.go1type Word uint
WorduintbigWord[]WordWord[]Wordsrc/math/big/nat.go1type nat []Word
nat[]WordnatnatxBWord1<<321<<64uintnatnatnatsrc/math/big/int.go
1type Int struct {
2 neg bool // sign
3 abs nat // absolute value of the integer
4}
Intnegnatint32int64IntIntAndORNOTGCDMODEsrc/math/big/rat.go
1type Rat struct {
2 a, b Int
3}
abIntfloat32float64src/math/big/rat.go
1type Float struct {
2 prec uint32
3 mode RoundingMode
4 acc Accuracy
5 form form
6 neg bool
7 mant nat
8 exp int32
9}
浮点型数据表示方式：
sign×mantissa×2exponent
其中 0.5≤mantissa≤1.0, 而且MinExp≤exponent≤MaxExp。除此之外还包含以下三个变量：
● 精度(precisionmantissa● 取值模式(
modemantissaToNearestEvenToNearestAwayToZero● 准确度(
accuracyBelowExactAboveFloatformFloat
1const (
2 MaxExp = math.MaxInt32 // largest supported exponent
3 MinExp = math.MinInt32 // smallest supported exponent
4 MaxPrec = math.MaxUint32 // largest (theoretically) supported precision; likely memory-limited
5)
mantnatprecision0natprecisionWordmant[0]0x.mant=1mantissa=0.5mantissaexponent
1x form neg mant exp
2----------------------------------------------------------
3±0 zero sign - -
40 < |x| < +Inf finite sign mantissa exponent
5±Inf inf sign - -
Float原文发布时间为：2018-11-25
本文来自云栖社区合作伙伴“Golang语言社区”，了解相关信息可以关注“Golang语言社区”。