Common Lisp 实现的 RSA 非对称加密玩具库

之前看过李永乐老师的讲课，感觉 RSA 加密的核心算法挺简单的，就想自己实现看看。感兴趣的请移步B站观看。

开始写代码以后发现，RSA 的核心算法确实不是难点，大概5，6句话就能讲清楚，难点反而是在于加密与解密算法的周边。比如：密钥生成，信息分段加密，以及解密后的重新组装，等等。

被这些周边问题卡住以后，捏着鼻子用某度找了一圈，不客气地说，所找到的基本都是垃圾，搜索结果中靠前的都是些不懂装懂的垃圾博客。

作为非专业人士，我斗胆把实现过程写出来，如果没有误导他人，还能给不小心点进来的某人一点帮助，也算是做了件好事。

核心算法

1. 先准备两个素数 p 和 q，为了防御别人破解，请选择两个比较大的素数，比如 83 和 97 [笑]

2. 将 p 和 q 相乘，得到 n。要注意啰，这里的得到的 n 会成为密钥的一部分，将会参与加密与解密运算。

3. 通过 (p-1) * (q-1) 得到一个数，这个就是所谓的欧拉函数，这里记作 φ(n)

4. 选一个数作为公钥指数 e，一般都选择 65537

5. 通过选定的公钥指数 e 和 φ(n) 计算得出私钥指数 d。d必须满足条件 e * d % φ(n) = 1。

这里总过5步，难点在最后一步 d 的计算。稍后再详细讲。

得到 e, d, 和 n 之后，把 e 和 n 放在一起，叫做公钥，用于加密；把 d和n放在一起，叫做私钥，用于解密。

加密和解密的计算过程完全一致，不同的只是传递的参数不同。

设 m 为明文，通过乘方模运算就得到密文 c:

m ^ e % n => c

反过来

c ^ d % n => m

可以看到，算法全一样，完全可以实现为单个函数，区别只在于你传递给它的是公钥还是私钥。

所以，下面就是所谓的核心算法的实现：

(defun euler (p q)
  (* (- p 1) (- q 1)))

(defstruct rsa-key
  name bits type n exponent)

(defun gen-keys (name &optional (bits 2048))
  (let* ((p  (make-prime (floor bits 2)))
         (q  (make-prime (floor bits 2)))
         (n  (* p q))
         (e  #x10001)
         (m  (euler p q))
         (d  (modinv e m)))
    (values (make-rsa-key :name name
                          :bits bits
                          :type :public
                          :n n
                          :exponent e)
            (make-rsa-key :name name
                          :bits bits
                          :type :private
                          :n n
                          :exponent d))))

;; 这里是入口，加密解密都靠它，区别只在于传递给它的参数 密文 or 明文 | 公钥 or 私钥
(defun enc/dec-number (n key)
  (expmod n (rsa-key-exponent key) (rsa-key-n key)))

这段代码并不能运行，因为还差一些东西。很明显，make-prime 和 modinv还没有实现。

难点一：大素数生成

凭直觉，你可以从2开始往后枚举：2,3,5,7,9,11,13... 再往后呢？

写一个嵌套循环来试除？对不起,这种蠢办法的复杂度是指数级的，就是你家有超算，也会很快就算不动了。

就如同大数的质因数分解是个难题一样，大数的素性检测同样也是难题。好在目前存在一些非确定性的基于概率的检测算法，可以将复杂度优化到对数级。这就是成功的路径。

看过 《SICP》人应该知道还记得，SICP 上面提到过一种叫做米勒拉宾测试的算法。如果认真做作业的话，很可能已经实现过了。所以，这不是问题。几年前我就已经用 Scheme 写过了，现在不过是用 Lisp 再写一次。

(defun check-nontrivial-sqrt (n m)
  (let ((x (mod (square n) m)))
    (if (and (= x 1)
             (not (= n 1))
             (not (= n (- m 1))))
        0
        x)))

(defun exp-mod (base exp m)
  (cond ((= exp 0) 1)
        ((evenp exp)
         (check-nontrivial-sqrt (exp-mod base (/ exp 2) m) m))
        (t (mod (* base (exp-mod base (- exp 1) m)) m))))

(defun miller-rabin-test (n base)
  (= (exp-mod base (- n 1) n) 1))

(defun make-random-list (n count)
  (if (= count 0)
      nil
      (cons (+ 1 (random (- n 1)))
            (make-random-list n (- count 1)))))

(defun test-queue (n test-list)
  (or (null test-list)
      (and (miller-rabin-test n (car test-list))
           (test-queue n (cdr test-list)))))

(defun primep (n)
  (or (= n 2)
      (and (> n 1)
           (oddp n)
           (test-queue n (make-random-list n 20)))))

test-queue 并非必要的，在测试中遇到非素数时，有极高的概率在很少的几次迭代中发现真相，从而不需要跑完指定的迭代次数。不过我就想写成这样，因为上面的代码足以在几毫秒内判断一个天文数字大小的整数是不是素数。

为了方便 RSA 相关函数调用，还需要几个辅助函数：

(defun next-prime (n)
  (labels ((iter (n)
             (if (primep n)
                 n
                 (iter (+ n 2)))))
    (if (oddp n)
        (iter n)
        (iter (+ n 1)))))

(eval-when (:load-toplevel)
  (setf *random-state* (make-random-state t)))

(defun make-prime (&optional (bits 1024))
  (let ((hex-bits (floor bits 4))  ;; 1 hex digit is equal to 4 binary digits
        (hex-string (make-array 0 :element-type 'base-char :fill-pointer 0 :adjustable t))
        (*print-base* 16))  ;; 这就是让教授们掩鼻的动态变量的神奇用法之一，你可以伪造一个全局变量来欺骗某个函数
    (with-output-to-string (s hex-string)
      (let (;; 确保最高的两位设置为 1
            (first-digit (logior (random 16) #b1100)))
        (format s "~A" first-digit)
        (dotimes (i (- hex-bits 1))
          (format s "~A" (random 16)))))
    (let ((n (parse-integer hex-string :radix 16)))
      (next-prime n))))

调用的入口是make-prime，默认生成 1024 位的随机素数。如果一次生成一个比较大的随机数，再以该数为起点寻找素数的话可以更快，但是随机数的位数无法控制。因此，这里的算法是迭代 bits / 4 次，每次迭代生成一位随机的 16 进制数，刚好对应 4 位二进制数。因为生成密钥对不是经常运行的任务，所以这个代价是可以接受的。就算是极度优化的 OpenSSL,在生成足够长的密钥对时也是需要等待的。

难点二，计算私钥指数 d

d必须满足的条件是 e * d % φ(n) = 1

这个的算法是现成的，网上代码满天飞，难点在于抄对。

下面就是我从 Python 翻译过来的实现：

(defun egcd (a b)
  (if (= a 0)
      (values b 0 1)
      (multiple-value-bind (g y x)
          (egcd (mod b a) a)
        (values g (- x (* (floor b a) y)) y))))

(defun modinv (a m)
  (multiple-value-bind (g x y)
      (egcd a m)
    (declare (ignore y))
    (unless (= g 1)
      ;;(error "modular inverse does not exists")
      0)
    (mod x m)))

不是难点 expmod

这个不是难点，是从 SICP 上直接抄下来的。

(defun expmod (base exp m)
  (cond ((= exp 0) 1)
        ((evenp exp)
         (mod (square (expmod base (/ exp 2) m)) m))
        (t (mod (* base (expmod base (- exp 1) m)) m))))

前面的素数判断的代码中的 exp-mod 函数仅仅是在它的基础上多加了一个check-nontrivial-sqrt判断。因为我不确定加了这个判断对最终的结果正确性会不会有影响，所以还是把原始版本给抄了上来。

作为演示性的实现，到此就已经完整了。至少把 demo 跑起来是没问题的。接下来如果要赋予它实用性的话，还要处理一些棘手的问题。比如，如何将待加密的数据切成片，分别加密后再组装在一起。至于解密方，又要如何从一些二进制位中正确地将加密单元切出来，分别解密，再组装成原始的文件。目前我还在和一些 BUG 搏斗，代码就不放出来了。