golang中big包源碼閱讀——從RSA算法說起

 ●  1 Golang中RSA加密算法實作

     ●  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}

私鑰結構包含(

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

要求的位數，但是如果後面都是

,那麼

nat

舍棄這些零，如果

precision

不是

Word

長度的整數倍，那麼就要在

mant[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

本文作者：南瓜waniu

本文來自雲栖社群合作夥伴“

Golang語言社群

”，了解相關資訊可以關注“

”。