背景

我們開發(fā)的打印系統(tǒng)需要一套授權(quán)工具，里面用到了rsa加密算法，之前的筆記一直沒整理，最近閑著剛好整理下，方便以后查詢。

rsa原理

RSA加密采用了大質(zhì)數(shù)難以分解的原理來進(jìn)行加密和解密。

兩個隨機的大質(zhì)數(shù)（越大越難以破解）p，q，n=p * q，計算的n就是密鑰的長度。rsa有1024，2048等長度的密鑰
rsa加密有一對密鑰，公鑰和私鑰，公鑰是公開的，用來加密，私鑰用來解密。私鑰簽名，公鑰解簽。

加密解密過程

1. `pow(x, e) % n = y; ` x是明文，y為加密后的密文，x的e次方模n得到y(tǒng)，這就是加密的過程，知道e和n就可以加密了，公鑰是用來加密的所以，公鑰 = （e,n）的組合
2. `pow(y, d) % n = x;` y是密文，x為明文，y的d次方模n得到x，私鑰來解密，所以私鑰 = (d,n)的組合

生成公鑰與私鑰

> 生成密鑰對的過程就是求 n， n的歐拉函數(shù)φ(n)，e, d  

1. 求n
   準(zhǔn)備兩個互質(zhì)數(shù)p，q。這兩個數(shù)不能太小，太小則會容易破解，將p乘以q就是N。如果互質(zhì)數(shù)p和q足夠大，那么根據(jù)目前的計算機技術(shù)和其他工具，至今也沒能從N分解出p和q。換句話說，只要密鑰長度N足夠大（一般1024足矣，也可以是2048，3072，4096...），基本上不可能從公鑰信息推出私鑰信息。
   n = p * q
2. n的歐拉函數(shù)φ(n)
   φ(n) = (p-1)(q-1)
3. 求e
   隨機選擇一個整數(shù)e，滿足條件：1< e < φ(n)，且e與φ(n) 互質(zhì)；實際應(yīng)用中，常常選擇65537
4. 求d
   e對于φ(n)的模反元素d，意思就是找到一個整數(shù)d，可以使得ed被φ(n)除的余數(shù)為1
   即e * d = 1 (mod φ(n)) 等價于 ed - 1 = kφ(n) 實際上就是對ex + φ(n)y = 1 的公式求解，用擴展歐幾里德算法求解
   d 必須滿足 1 < d < φ(n)
   舉個例子
   p = 13 q = 19 n = 13×19 = 247
   l = (p-1) * (q-1) = 216
   取e = 17 ，滿足 1< e < l，且e與l 互質(zhì)
   求d, 17x + 216y = 1
   根據(jù)擴展歐幾里德算法（這個算法沒看過網(wǎng)上炒的例子）算出一組數(shù) (x,y)=(89,-7)，d大于1，即 d=89
   假設(shè)有一個數(shù)m = 101 加密：101的17次方模247=255 解密：255的89次方模247=101。代碼如下：

      package main
      
      import (
        "fmt"
        "math/big"
      )
      
      func main() {
        n := big.NewInt(247)
        e := big.NewInt(17)
        d := big.NewInt(89)
          
        m := big.NewInt(101)
      
        //加密，Exp的第三個參數(shù)如果給上n，可以直接計算出加密后的值，不需要在調(diào)用Mod方法
        var l big.Int
        l.Exp(m, e, nil)
        var x big.Int
        x.Mod(&l, n)
        fmt.Println(x.Int64())
      
        //解密    
        var t big.Int
        t.Exp(big.NewInt(x.Int64()), d, nil)
        var y big.Int
        y.Mod(&t, n)
        fmt.Println(y.Int64(), y.Int64() == m.Int64())
      }

rsa安全嗎？

n和e是公開的，也就是已知公鑰，想要破解只要知道私鑰就行了，那根據(jù)上面的公式，只需要知道d就可以計算出私鑰，e * d = 1 (mod φ(n))，要想得到d 就得計算出φ(n)的值，根據(jù)公式φ(n)=(p-1) * (q-1) 那其實就是求p和q，n=p*q，要求p和q就是對n做因數(shù)分解，那就是說如果n可以被因數(shù)分解，那就能破解密文。而大整數(shù)要做分解是一件很困難的事，這也證明了為什么要選擇2個大整數(shù)作為p和q，越大越難以破解。