nullprogram.com/blog/2015/10/30/
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
under-documented calc-eval function. It evaluates an expression
string with format-like argument substitutions ($n).
(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
radix and #. This is the same as in the user interface of calc. For
example:
(calc-eval "16#deadbeef")
;; => "3735928559"
The second argument (optional) to calc-eval adjusts its behavior.
Given 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
Generating primes
RSA is founded on the difficulty of factoring large composites with
large factors. Generating an RSA keypair starts with generating two
prime numbers, p and 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"
Unfortunately calc’s random function is based on Emacs’ random
function, which is entirely unsuitable for cryptography. In the real
implementation I read n bits from /dev/urandom to generate an n-bit
number.
(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) ""))))
(Note: /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 p and 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 e.
The function 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
curious.
(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 n and e and the private key is n and d. From
here we can compute and verify cryptographic signatures.
Signatures
To compute signature s of an integer m (where 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
e: m ≡ s^e (mod n). If the signature is valid, m will be
recovered. In theory, only someone who knows d can feasibly compute
s from m. If n is small enough to factor, revealing
p and q, then 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 secure-hash. It
hashes strings and buffers.
(secure-hash 'sha224 "Hello, world!")
;; => "8552d8b7a7dc5476cb9e25dee69a8091290764b7f2a64fe6e78e9568"
Since the result is hexadecimal, just prefix 16# to turn it into a
calc integer.
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
your 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.