RSA Signatures in Emacs Lisp
Emacs comes with a wonderful arbitrary-precision computer algebra system called calc. I’ve discussed it previously and continue to use it on a daily basis. That’s right, people, Emacs can do calculus. Like everything Emacs, it’s programmable and extensible from Emacs Lisp. In this article, I’m going to implement the RSA public-key cryptosystem in Emacs Lisp using calc.
If you want to dive right in first, here’s the repository:
This is only a toy implementation and not really intended for serious cryptographic work. It’s also far too slow when using keys of reasonable length.
Evaluation with calc
The calc package is particularly useful when considering Emacs’ limited integer type. Emacs uses a tagged integer scheme where integers are embedded within pointers. It’s a lot faster than the alternative (individually-allocated integer objects), but it means they’re always a few bits short of the platform’s native integer type.
calc has a large API, but the user-friendly porcelain for it is the
calc-eval function. It evaluates an expression
string with format-like argument substitutions (
(calc-eval "2^16 - 1") ;; => "65535" (calc-eval "2^$1 - 1" nil 128) ;; => "340282366920938463463374607431768211455"
Notice it returns strings, which is one of the ways calc represents
arbitrary precision numbers. For arguments, it accepts regular Elisp
numbers and strings just like this function returns. The implicit
radix is 10. To explicitly set the radix, prefix the number with the
#. This is the same as in the user interface of calc. For
(calc-eval "16#deadbeef") ;; => "3735928559"
The second argument (optional) to
calc-eval adjusts its behavior.
nil, it simply evaluates the string and returns the result.
The manual documents the different options, but the only other
relevant option for RSA is the symbol
pred, which asks it to return
a boolean “predicate” result.
(calc-eval "$1 < $2" 'pred "4000" "5000") ;; => t
RSA is founded on the difficulty of factoring large composites with
large factors. Generating an RSA keypair starts with generating two
q, and using these primes to compute two
mathematically related composite numbers.
calc has a function
calc-next-prime for finding the next prime
number following any arbitrary number. It uses a probabilistic
primarily test — the
Fermat Miller-Rabin primality test
— to efficiently test large integers. It increments the input until
it finds a result that passes enough iterations of the primality test.
(calc-eval "nextprime($1)" nil "100000000000000000") ;; => "100000000000000003"
So to generate a random n-bit prime, first generate a random n-bit number and then increment it until a prime number is found.
;; Generate a 128-bit prime, 10 iterations (0.000084% error rate) (calc-eval "nextprime(random(2^$1), 10)" nil 128) "111618319598394878409654851283959105123"
random function is based on Emacs’
function, which is entirely unsuitable for cryptography. In the real
implementation I read n bits from
/dev/urandom to generate an n-bit
(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 is the right choice. There’s no reason to use
/dev/random for generating keys.)
Computing e and d
From here the code just follows along from the Wikipedia article.
After generating the primes
q, two composites are computed,
n = p * q and
i = (p - 1) * (q - 1). Lacking any reason to do
otherwise, I chose 65,537 for the public exponent
rsa--inverse is just a straight Emacs Lisp + calc
implementation of the extended Euclidean algorithm from the Wikipedia
article pseudocode, computing
d ≡ e^-1 (mod i). It’s not much
use sharing it here, so take a look at the repository if you’re
(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))))
The public key is
e and the private key is
here we can compute and verify cryptographic signatures.
To compute signature
s of an integer
m < n), compute
s ≡ m^d (mod n). I chose the right-to-left binary method, again
straight from the Wikipedia pseudocode (lazy!). I’ll share this
one since it’s short. The backslash denotes integer division.
(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))
Verifying the signature is the same process, but with the public key’s
m ≡ s^e (mod n). If the signature is valid,
m will be
recovered. In theory, only someone who knows
d can feasibly compute
n is small enough to factor, revealing
d can be feasibly recomputed from the public key.
So mind your Ps and Qs.
So that leaves one problem: generally users want to sign strings and
files and such, not integers. A hash function is used to reduce an
arbitrary quantity of data into an integer suitable for signing. Emacs
comes with a bunch of them, accessible through
hashes strings and buffers.
(secure-hash 'sha224 "Hello, world!") ;; => "8552d8b7a7dc5476cb9e25dee69a8091290764b7f2a64fe6e78e9568"
Since the result is hexadecimal, just prefix
16# to turn it into a
Here’s the signature and verification functions. Any string or buffer can be signed.
(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))))
Note the hash truncation step. If this is actually necessary, then
n is very easy to factor! It’s in there since this is just a
toy and I want it to work with small keys.
Putting it all together
Here’s the whole thing in action with an extremely small, 128-bit 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
Each of these operations took less than a second. For larger, secure-length keys, this implementation is painfully slow. For example, generating a 2048-bit key takes my laptop about half an hour, and computing a signature with that key (any size message) takes about a minute. That’s probably a little too slow for, say, signing ELPA packages.