實現公鑰私鑰體系的不對稱加密

我們之前介紹的不對稱加密算法，如果從最終密鑰Kenc和Kdec相同這個角度來看，還不是徹底的不對稱加密算法。另外，該算法還需要A和B各自保留的一段私有數據a與b參與運算。因此如果另一個通信方C想要加入進來，在不獲得a或b的情況下是不可能的。

而現在在加密領域較為流行的公私鑰加密體系較好地解決了上述問題，該體系的主要算法可以描述如下：

• 假設A準備與很多人進行加密通信；
• A生成一對密鑰，分別稱為“公鑰”和“私鑰”；
• A將公鑰公開，發送給所有需要與A通信的人；
• 需要向A發送數據的人，在發送之前將數據用公鑰進行加密之後再發送；
• A接收到加密的密文後，用私鑰進行解密即可正確還原出原文；
• 同樣，A用私鑰加密後的密文，其他人用公鑰也可以正確解密。

可以看出，公私鑰體系的加密算法只有一個公開的公鑰和一個私有的私鑰，並且加解密時分別就是用這兩個密鑰作為最終密鑰，是真正的不對稱加密算法，而且比之前算法的步驟大大簡化。下面代碼中演示了一個在Go語言中實現的經典公私鑰加密算法，這個算法利用大質數的不相關性實現公私鑰對的生成，由於我們重點不是講解算法，所以有關該算法的數學意義將不進行討論，有興趣的可以自行查閱相關文獻。

<code>package main
 
import (
  "bytes"
  "crypto/rand"
  "encoding/gob"
  "math/big"
  mathRand "math/rand"
  "time"
  t "tools"
)
 
// getRandomPrime 用於獲取一個隨機的質數
func getRandomPrime() *big.Int {
  for {
       tmpN, errT := rand.Prime(rand.Reader, 10)
 
       if errT != nil {
             // 有錯誤發生則繼續循環，直至正確生成一個質數為止
             continue
       }
 
       return tmpN
  }
}
 
// calKeys 用於生成一組公鑰、私鑰
func calKeys() (pubKey *big.Int, privateKey *big.Int, modTotal *big.Int) {
 
  // 令 p 為一個隨機的質數
  p := getRandomPrime()
 
  // 令 q 為一個不等於 p 的隨機質數
  var q *big.Int
  for {
       q = getRandomPrime()
 
       if q.Cmp(p) != 0 {
             break
       }
  } 

 
  t.Printfln("p: %v, q: %v", p, q)
 
  // 令 n 為 p 和 q 的乘積（公倍數）
  n := new(big.Int).Mul(p, q)
 
  t.Printfln("n（模數）: %v", n)
 
  // bigOneT 相當於一個常數 1，是 *big.Int 類型的
  bigOneT := big.NewInt(1)
 
  // 令 m = (p - 1) * (q - 1)
  m := new(big.Int).Mul(new(big.Int).Sub(p, bigOneT), new(big.Int).Sub(q, bigOneT))
 
  t.Printfln("m: %v", m)
 
  // 從3開始循環選擇一個符合條件的公鑰 e
  e := big.NewInt(3)
 
  for {
       // 每次不符合條件時，e = e + 1；
       // 實際上，e = e + 2 會更快，因為偶數更可能會有公約數
       e.Add(e, bigOneT)
 
       // 獲取 e 與 (p - 1) 的最大公約數
       diff1 := new(big.Int).GCD(nil, nil, e, new(big.Int).Sub(p, bigOneT))
 
       // 獲取 e 與 (q - 1) 的最大公約數
       diff2 := new(big.Int).GCD(nil, nil, e, new(big.Int).Sub(q, bigOneT))
 
       // 獲取 e 與 m 的最大公約數
       diff3 := new(big.Int).GCD(nil, nil, e, m)
 
       // 選擇合適的 e 的條件是，e 與 (p - 1)、(q - 1)、m 必須都分別互為質數
       // 也就是最大公約數為 1
       if diff1.Cmp(bigOneT) == 0 && diff2.Cmp(bigOneT) == 0 && diff3.Cmp(bigOneT) == 0 {
             break 

       }
  }
 
  t.Printfln("e（公鑰）: %v", e)
 
  // 計算私鑰
  d := new(big.Int).ModInverse(e, m)
 
  t.Printfln("d（私鑰）: %v", d)
 
  return e, d, n
 
}
 
func main() {
 
  // 初始化隨機數種子
  mathRand.Seed(time.Now().Unix())
 
  // 獲取公鑰（pubKeyT）、私鑰（privateKeyT）和共用的模數（modTotalT）
  // modTotalT 可以公開
  // 也可以將pubKeyT和modTotalT合起來看做公鑰
  // 將privateKeyT和modTotalT合起來看做私鑰
  pubKeyT, privateKeyT, modTotalT := calKeys()
 
  // 未加密的文本
  originalText := "我們都很nice。"
 
  t.Printfln("原文：%#v", originalText)
 
  // 下面開始加密的過程
 
  // 用於存放密文的大整數切片
  cypherSliceT := make([]big.Int, 0)
 
  // 注意用 range 遍歷 string 時，其中的 v 都是 rune 類型
  for _, v := range originalText {
       // 每個 Unicode 字符將作為數值用公鑰和模數進行加密 

       cypherSliceT = append(cypherSliceT, *new(big.Int).Exp(big.NewInt(int64(v)), pubKeyT, modTotalT))
  }
 
  var cypherBufT bytes.Buffer
 
  // 用gob包將密文大整數切片轉換為字節切片以便傳輸或保存
  gob.NewEncoder(&cypherBufT).Encode(cypherSliceT)
 
  cypherBytesT := cypherBufT.Bytes()
 
  t.Printfln("密文數據：%#v", cypherBytesT)
 
  // 下面開始解密的過程
 
  // 獲得加密後的密文字節切片
  decryptBufT := bytes.NewBuffer(cypherBytesT)
 
  var decryptSliceT []big.Int
 
  // 用gob包將密文字節切片轉換為對應的密文大整數切片
  gob.NewDecoder(decryptBufT).Decode(&decryptSliceT)
 
  // 為了演示，將分別用私鑰和公鑰來解密
  // decryptRunes1T用於存放用私鑰解密的結果
  // decryptRunes2T用於存放用公鑰解密的結果
  decryptRunes1T := make([]rune, 0)
  decryptRunes2T := make([]rune, 0)
 
  // 循環對每個大整數進行解密
  for _, v := range decryptSliceT {
       // 注意解密後的大整數要轉換回 rune 格式才符合要求
       decryptRunes1T = append(decryptRunes1T, rune((*(new(big.Int))).Exp(&v, privateKeyT, modTotalT).Int64()))
       decryptRunes2T = append(decryptRunes2T, rune((*(new(big.Int))).Exp(&v, pubKeyT, modTotalT).Int64()))
  }
 
  decryptText1T := string(decryptRunes1T) 

  t.Printfln("用私鑰解密後還原的文本：%#v", decryptText1T)
 
  decryptText2T := string(decryptRunes2T)
  t.Printfln("用公鑰解密後還原的文本：%#v", decryptText2T)
 
}/<code>

代碼 14‑5 crypto2/crypto2.go

先看看代碼 14‑5的多次運行結果：

<code>C:\\goprjs\\src\\test3>go run test3.go
p: 911, q: 809
n（模數）: 736999
m: 735280
e（公鑰）: 9
d（私鑰）: 408489
原文："我們都很nice。"
密文數據：[]byte{0xd, 0xff, 0x83, 0x2, 0x1, 0x2, 0xff, 0x84, 0x0, 0x1, 0xff, 0x82, 0x0, 0x0, 0xf, 0xff, 0x81, 0x5, 0x1, 0x1, 0x3, 0x49, 0x6e, 0x74, 0x1, 0xff, 0x82, 0x0, 0x0, 0x0, 0x30, 0xff, 0x84, 0x0, 0x9, 0x4, 0x2, 0x5, 0x7d, 0xc1, 0x4,
0x2, 0x6, 0x7b, 0xeb, 0x4, 0x2, 0x5, 0x36, 0x2b, 0x4, 0x2, 0x1, 0xd9, 0xf6, 0x4, 0x2, 0xb, 0x1a, 0x81, 0x3, 0x2, 0x66, 0x43, 0x4, 0x2, 0x3, 0x7f, 0x5f, 0x4, 0x2, 0x4, 0x5c, 0x80, 0x4, 0x2, 0x6, 0x2, 0xe}
用私鑰解密後還原的文本："我們都很nice。"
用公鑰解密後還原的文本："\\U00057324\\U0003aa62\\U0005f3d0\\U000a2f3a\\U00088985홖\\U000420f8\\U0001a4a7\\U0006a2bb"
 
C:\\goprjs\\src\\test3>go run test3.go
p: 937, q: 809
n（模數）: 758033
m: 756288
e（公鑰）: 5
d（私鑰）: 453773
原文："我們都很nice。"
密文數據：[]byte{0xd, 0xff, 0x83, 0x2, 0x1, 0x2, 0xff, 0x84, 0x0, 0x1, 0xff, 0x82, 0x0, 0x0, 0xf, 0xff, 0x81, 0x5, 0x1, 0x1, 0x3, 0x49, 0x6e, 0x74, 0x1, 0xff, 0x82, 0x0, 0x0, 0x0, 0x31, 0xff, 0x84, 0x0, 0x9, 0x4, 0x2, 0x6, 0xf7, 0xe6, 0x4,
0x2, 0x6, 0xa6, 0x46, 0x4, 0x2, 0x3, 0x73, 0xf6, 0x4, 0x2, 0x7, 0x76, 0x3b, 0x4, 0x2, 0xa, 0x83, 0x13, 0x4, 0x2, 0x8, 0xba, 0x85, 0x4, 0x2, 0x5, 0xbe, 0xc2, 0x4, 0x2, 0xb, 0x27, 0x6d, 0x4, 0x2, 0x6, 0xdb, 0x5a}
用私鑰解密後還原的文本："我們都很nice。" 

用公鑰解密後還原的文本："\\U000ab98a\\U00015852\\U0008af0c\\U0006c2a7\\U0001f26f\\U0009ee7c"
 
C:\\goprjs\\src\\test3>go run test3.go
p: 911, q: 907
n（模數）: 826277
m: 824460
e（公鑰）: 11
d（私鑰）: 74951
原文："我們都很nice。"
密文數據：[]byte{0xd, 0xff, 0x83, 0x2, 0x1, 0x2, 0xff, 0x84, 0x0, 0x1, 0xff, 0x82, 0x0, 0x0, 0xf, 0xff, 0x81, 0x5, 0x1, 0x1, 0x3, 0x49, 0x6e, 0x74, 0x1, 0xff, 0x82, 0x0, 0x0, 0x0, 0x31, 0xff, 0x84, 0x0, 0x9, 0x4, 0x2, 0x2, 0x9c, 0x0, 0x4, 0x2, 0x2, 0x71, 0x1e, 0x4, 0x2, 0xb, 0xde, 0x42, 0x4, 0x2, 0xa, 0xb6, 0xe4, 0x4,
0x2, 0xa, 0xe3, 0x86, 0x4, 0x2, 0x9, 0x72, 0x10, 0x4, 0x2, 0xa, 0xc6, 0xab, 0x4, 0x2, 0x2, 0xcd, 0x41, 0x4, 0x2, 0x6, 0x78, 0xc5}
用私鑰解密後還原的文本："我們都很nice。"
用公鑰解密後還原的文本："\\U0008bb1f\\U000992b0\\U00060c54\\U000c615b\\U000a0f37\\U000b8b29\\U000bc9cd\\U000812ec\\U000c2517"/<code>

可以看出：每次生成的公鑰、私鑰和模數都不一樣；但每次用公鑰加密數據後，如果用私鑰進行解密總是可以正確地還原原文，而用公鑰則無法正確解密（結果總是亂碼）。這說明這個公私鑰加密算法是設計成功的。

對於代碼 14‑5，其中已經有詳盡的註釋，請一定參看，另外我們再補充說明幾點：

• 首先，再次聲明算法的數學意義和數學計算過程我們將略過不解釋；
• p、q、n、m都是生成公鑰私鑰對的時候所需的中間過程參數，其中的n還將被用於作為最後加密和解密算法的模數；
• 用於生成質數的函數getRandomPrime中，使用了rand.Prime函數來產生隨機質數，該函數第二個參數是生成質數的最大二進制位數，它限制了可能得到的質數的上限範圍，位數越多隨機質數的最大值就越大，但生成時間也越長。真正的公私鑰算法中，使用的質數一般越大越好，本代碼因僅用作示例，所以只用了10個二進制位來生成質數；
• 由於本算法中涉及較大的冪運算，因此使用了可以表示大數字的math.big庫，從而一些計算過程也只能表示的比較複雜；
• 公鑰e理論上可以從符合條件的所有值中任意選擇，但一般習慣從3開始向上挑選；
• 公鑰e和模數n都可以公開，私鑰d則不應公開；
• 本例中使用該算法對一個字符串中的所有Unicode字符逐一用公鑰進行加密；解密過程中則反向解密；由於用range遍歷字符串時得到的是一個一個rune類型的數據，所以加解密時要分別做rune到big.Int的類型轉換和其反向轉換。也可以用索引遍歷字符串的每個字節，來使加密解密針對byte類型來進行。

閱讀更多 陸滿庭 的文章

關鍵字: 私鑰 加密 通信