golang中big包源码阅读——从RSA算法说起

李海彬

发布于 2018-12-19 10:55:36

1.2K0

发布于 2018-12-19 10:55:36

文章被收录于专栏：Golang语言社区

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=me mod n。

私钥解密通过(n,d)和密文c，计算得到密文: m=cd mod n。

1.2 算法优化

在解密的算法中，关键点在于计算cd和对于n取模，但是通常情况下，该数是非常大的，因此计算是非常耗时操作。所以对于RSA算法解密的过程有简化的方法。中国剩余定理在*孙子算经*中有下面这么一段话

有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？

换成RSA中就是这样描述：p和q是两个素数，n=p×q, 对于任意(m1,m2),(0≤m21<p,0≤m2<q), 必然存在唯一的整数m,(0≤m<n) 满足 m1=m mod q,m2=m mod p，所以RSA解密算法中的m=cd mod n, 可以分解为m1=cd mod p,m2=cd mod q, 然后再求得m。对于cd modp=…=cr mod p, 其中r为d除p−1的余数，即r=dmod(p−1), 令dp=d mod (p−1)，同理dq=d mod(q−1)。同时计算出qinv×q=1 mod p。在预先计算出结果后，就可快速的解密

m1=cdp mod p
m2=cdq mod q
h=(qinv×((m1−m2) mod p)) mod p
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=me mod pub.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}

私钥结构包含(embed)了公钥的结构，也可以知道使用了多素数的计算的方式，并使用PrecomputedValues结构保存加速解密计算的值，具体信息如下：

 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}

其中Dp,Dq和Qinv是之前算法描述的预先计算的值，而CRTValue切片包含了使用中国余数定理所需要的值。

1.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}

对于两个素数的提前计算比较直观，对私钥中的Precomputed中的Dp,Dq和Qinv分别计算。

1.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包

由于RSA算法在实现过程中需要很大（位数很多）的数据，所以没有使用int、int32、int64等数据类型，而是使用math.big包中提供的Int类型。除了Int类型，还定义了Rat,Float等相关类型，由于Go不支持操作符重载，所以基本上运算使用Add, Sub等形式定义的，在类型方法中，返回值通常也是receiver，所以在使用过程中，不需要定义一些变量保存结果，直接使用链式调用即可。

2.1 类型

在src/math/big中，实现了整数Int，浮点数Float和有理数Rat三种使用到的数据类型。除此之外还有一些辅助类型和针对大数处理的函数。

2.1.1 Word (`src/math/big/arith.go`)

1type Word uint

Word类型是uint的别名，它代表了在big包中基本操作单元，其中包含了一些列基本的算术计算函数，除了Word之间的加减乘除计算；定义了[]Word和Word之间的加减乘除计算；定义了[]Word之间的加和减计算。

2.1.2 nat (`src/math/big/nat.go`)

1type nat []Word

nat是[]Word的别名，和整数表示形式一样，nat中每一个元素表示一位数字位，所以对于任意nat表示的任意数值x，都有：x=x[n−1]×Bn−1+x[n−2]×Bn−2+…+x[1]×B+x[0]

其中B为Word表示值的基，通常为1<<32或者1<<64，取决于uint的类型是32位还是64位。除此之外，nat表示的值在最终的结果中，是不包含前面的零。定义了nat之间的加、减、乘、除等操作，还定义了区间内的连乘、平方根、取模；也提供了nat池，达到重复使用的目的。

2.1.3 Int (`src/math/big/int.go`)

1type Int struct {
2    neg bool // sign
3    abs nat  // absolute value of the integer
4}

Int类型定义包含了一个布尔型值neg，表示该值是正数还是负数；一个nat类型，表示该整数的绝对值。除了定义常规的整数之间运算，还定义了诸如int32,int64等和Int之间互相转换；字符串和Int类型相互转换；And,OR,NOT等运算；最大公约数GCD,取模MODE和素数等相关的计算方法。

2.1.4 Rat(`src/math/big/rat.go`)

1type Rat struct {
2    a, b Int
3}

有理数ab中的分子分母a和b为Int类型，提供了常规的算术运算；还有有float32, float64等相关转换操作。

2.1.4 Float(`src/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。除此之外还包含以下三个变量：

精度(precision): 表示mantissa比特位表示值的最大值；
取值模式(mode): 表示将浮点值转换为mantissa表示时候取值模式，一般有ToNearestEven, ToNearestAway,ToZero等等；
准确度(accuracy):表示取舍值与真正值之间的差值，取值有三种：Below,Exact和Above。

在Float类型中的form内部使用，用来表示该浮点值是零值，无穷值还是有穷值。Float定义的精度限制范围：

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)

与 IEEE-754 定义的浮点型方式稍微有点不同：mant是一个非零的有限值，nat切片通常保存precision要求的位数，但是如果后面都是0,那么nat舍弃这些零，如果precision不是Word长度的整数倍，那么就要在mant[0]后面补上0; 如果x.mant=1，也就是mantissa=0.5，将会做一些标准化，将mantissa进行左移操作，exponent部分会右移操作。统一的形式为

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，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自 Golang语言社区微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度