实现公钥私钥体系的不对称加密

我们之前介绍的不对称加密算法，如果从最终密钥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类型来进行。

閱讀更多 陸滿庭 的文章

關鍵字: 私钥 加密 通信