使用 emacslisp 实现 RSA 签名

发布于 2024-11-13 14:00:54 字数 7533 浏览 7 评论 0

Emacs 自带一个很牛逼的，能实现任意精度计算的代数系统，名叫 calc . 我之前有介绍过它 , 现在它已经成为我日常使用的工具之一了。

是的，兄弟,Emacs 可以作代数运算. 而且它和 Emacs 中的其他玩意一样，是可编程的,可以通过 EmacsLisp 对其进行扩展。本文我就要告诉你怎么在 EmacsLisp 中用 calc 来实现 RSA 公钥密码体系

下面是完成的成果：

https://github.com/skeeto/emacs-rsa

当然这只是实现来玩玩的，不是真的想把它应用起来. 而且它的速度实在是太慢了。

Evaluation with calc

由于 Emacs 的整数型是有长度限制的，因此 calc package 就特别的有用。Emacs 并不会先分配一个整形对象然后用一个指针指向它，而是直接在指针中存放整数. 这样做的好处是，它的访问速度更快,但是意味着,Emacs 中的整型能表示的范围要更小一些。

calc 定义了大量的 API, 其中有一个特别好用的函数叫 calc-eval . 它可以接受一个字符串形式的运算式并计算出结果，甚至运算式还能用 $n 来进行参数替换。

(calc-eval "2^16 - 1")
;; => "65535"

(calc-eval "2^$1 - 1" nil 128)
;; => "340282366920938463463374607431768211455"

请注意，该函数返回的结果是字符串，这是 calc 用来表示任意精度数字的一种方式. 而对于传递给它的参数，则既可以是普通的 Elisp 数字也可以是字符串。默认情况下, calc 认为这些数字都是十进制的. 不过你也可以修改它的基，方法是在数字前加上基数和#. 就跟交互式使用 calc 时一样。
举个例子:

(calc-eval "16#deadbeef")
;; => "3735928559"

calc-eval 的第二个参数是可选的，用来修改 calc-eval 的计算方式. 若为 nil,则表示计算运算式并返回结果. 至于其他的值是什么意思，可以去查看 manual 文档。不过在本文中，唯一用到的非 nil 值只有符号 pred ,它表示让 calc-eval 返回时返回一个布尔值。

(calc-eval "$1 < $2" 'pred "4000" "5000")
;; => t

Generating primes

RSA 是建立在大数分解的复杂度基础上的. 要产生 RSA 键值对先需要产生两个质数 p 和 q ,然后用这两个质数进行运算得到两个数学上相关的合成数 (composite numbers)。

calc 提供一个 calc-next-prime 函数来获取大于某个数的下一个质数，该函数使用 probabilistic primarily test — the Fermat Miller-Rabin primality test — 来实现对大数据的高效测试。

It increments the input until it finds a result that passes enough iterations of the primality test.

(calc-eval "nextprime($1)" nil "100000000000000000")
;; => "100000000000000003"

那么要产生一个随机的 n 位的质数，只需要先产生一个 n 位的随机数，然后找出大于它的下一个质数就行了。

;; Generate a 128-bit prime, 10 iterations (0.000084% error rate)
(calc-eval "nextprime(random(2^$1), 10)" nil 128)
"111618319598394878409654851283959105123"

不过 calc 的随机函数是基于 Emacs 的随机函数来实现的，而 Emacs 随机函数的强度不足以被用于加密. 所以在实际实现时，我从 /dev/urandom 来读取 n 个比特作为 n 位的随机数。

(with-temp-buffer
  (set-buffer-multibyte nil)
  (call-process "head" "/dev/urandom" t nil "-c" (format "%d" (/ bits 8)))
  (let ((f (apply-partially #'format "%02x")))
    (concat "16#" (mapconcat f (buffer-string) ""))))

请注意: 一定要使用 /dev/urandom . 原因请参见 no reason to use /dev/random for generating keys

Computing e and d

接下来就是按照 Wikipedia 来写代码了. 产生了质数 p 和 q 后，使用公式 ~n p * q~ 和 ~i (p - 1) * (q - 1)~ 计算出两个相关数。另外，我随意地选择 65,537 来作为指数 e。

至于 rsa--inverse 不过是把 Extended Euclidean 算法按照 Wiki 上的伪代码用 Emacs Lisp + calc 来实现罢了。它本身没有什么好说的，如果你好奇怎么实现的话,直接看仓库中的代码吧。

(defun rsa-generate-keypair (bits)
  "Generate a fresh RSA keypair plist of BITS length."
  (let* ((p (rsa-generate-prime (+ 1 (/ bits 2))))
          (q (rsa-generate-prime (+ 1 (/ bits 2))))
          (n (calc-eval "$1 * $2" nil p q))
          (i (calc-eval "($1 - 1) * ($2 - 1)" nil p q))
          (e (calc-eval "2^16+1"))
          (d (rsa--inverse e i)))
    `(:public  (:n ,n :e ,e) :private (:n ,n :d ,d))))

这里 n 和 e 就是公钥,n 和 d 就是私钥. 下面我们就要开始计算并验证签名了。

Signatures

计算整数 m(m<n) 的签名算式是 s ≡ m^d (mod n) ，为了偷懒，我直接将 Wikipedia 上 right-to-left binary method 的伪代码转换成 Elisp 实现，由于实现方法很简短，我这里把它也列出来了. 注意，震撼力的反斜杠表示整型除法。

(defun rsa--mod-pow (base exponent modulus)
  (let ((result 1))
    (setf base (calc-eval "$1 % $2" nil base modulus))
    (while (calc-eval "$1 > 0" 'pred exponent)
      (when (calc-eval "$1 % 2 == 1" 'pred exponent)
        (setf result (calc-eval "($1 * $2) % $3" nil result base modulus)))
      (setf exponent (calc-eval "$1 \\ 2" nil exponent)
            base (calc-eval "($1 * $1) % $2" nil base modulus)))
    result))

校验签名的过程跟上面是一样的，只不过使用公钥 e 参与运算: m ≡ s^e (mod n) 。

如果签名是正确的，那么 m 会被正确地还原。理论上讲，只有在直到 d 的情况下才能从 m 计算出 s 来。不过，如果 n 的值太小了 , 很容易就能分解出 p 和 q 来，那么 d 也就很容易从公钥中推算出来。所以，一定要注意你选择的 p 和 q 有足够的强度。

现在还剩下一个问题: 一般用户都是对字符串或者文件这类东西作签名的，不太可能对一个整数去做签名。所幸，通过 hash 函数可以将任意长度的数据转换成一段适合签名的整数。Emacs 本身就自带了很多 hash 算法，可以通过 secure-hash 函数来调用. 它可以对字符串和 buffer 进行 hash 运算。

(secure-hash 'sha224 "Hello, world!")
;; => "8552d8b7a7dc5476cb9e25dee69a8091290764b7f2a64fe6e78e9568"

由于结果是一个十六进制数，所以只要在签名加上 16# 就能直接当成 calc 中的整型来用了。下面是实现的签名和验签函数，可以用来对字符串或 buffer 进行签名。

(defun rsa-sign (private-key object)
  (let ((n (plist-get private-key :n))
        (d (plist-get private-key :d))
        (hash (concat "16#" (secure-hash 'sha384 object))))
    ;; truncate hash such that hash < n
    (while (calc-eval "$1 > $2" 'pred hash n)
      (setf hash (calc-eval "$1 \\ 2" nil hash)))
    (rsa--mod-pow hash d n)))

(defun rsa-verify (public-key object sig)
  (let ((n (plist-get public-key :n))
        (e (plist-get public-key :e))
        (hash (concat "16#" (secure-hash 'sha384 object))))
    ;; truncate hash such that hash < n
    (while (calc-eval "$1 > $2" 'pred hash n)
      (setf hash (calc-eval "$1 \\ 2" nil hash)))
    (let* ((result (rsa--mod-pow sig e n)))
      (calc-eval "$1 == $2" 'pred result hash))))

注意到这里面包含了一个对 hash 结果进行阶段的步骤. 这一步实际上会让你的 n 变得很容易被分解！我这里之所以有这么一个步骤是因为本来这也就是写来玩玩的，而且我也不希望太大的 key 造成运算速度太过缓慢。

Putting it all together

下面是一段演示，使用了 128 位的 key.

(setf message "hello, world!")

(setf keypair (rsa-generate-keypair 128))
;; => (:public  (:n "74924929503799951536367992905751084593"
;;               :e "65537")
;;     :private (:n "74924929503799951536367992905751084593"
;;               :d "36491277062297490768595348639394259869"))

(setf sig (rsa-sign (plist-get keypair :private) message))
;; => "31982247477262471348259501761458827454"

(rsa-verify (plist-get keypair :public) message sig)
;; => t

(rsa-verify (plist-get keypair :public) (capitalize message) sig)
;; => nil

其中的每个步骤耗时不超过一秒，不过若使用更长的，足够安全的 key,那么这个实现就太慢了。

比如，在我的笔记本上,产生一个 2048 位的 key 足足花了我半个小时，而使用这个 key 来对消息进行签名又要花费大概一分钟。

这个速度，若想用来对 ELPA package 进行签名恐怕还是太慢了一些。

分享到QQ

分享到微博