Lisp: RSA With Ironclad—The Missing Manual

Ironclad is a cryptography library written entirely in Common Lisp. The project's homepage promises only a rudimentary support for public-key cryptography and explains later that—

Support for RSA encryption and decryption is provided as well, but it is "raw"—the various formatting schemes (e.g. PKCS–1) must be implemented by the user at this time.
The project's TODO list explicitly states that—
RSA, Elgamal, elliptic-curve crypto, and others remain to be added. One issue that has yet to be resolved is how to handle the myriad signature/encryption schemes for RSA.

While the above clarifies why the library's support for public-key cryptography is called rudimentary, it left me wondering which RSA operations can be done with Ironclad in its present form (considering the fact that the last time src/public-key/rsa.lisp was modified was a minor change made more than three years ago).

Skimming over the file discovers that the basics of RSA are there and they can be used for applications that do not have interoperability requirements—for instance, when the intended application implements both parties of a communication channel which is protected with RSA. Moreover, using these basics requires very little effort, which I am going to demonstrate below.

In particular, I was interested in signing messages with RSA, verification of RSA signatures, and generation of RSA keys. To achieve that, I wrote the following source:

 1	(in-package :ironclad)
 3	(defclass rsa-signature ()
 4	    ((s :initarg :s :reader rsa-signature-s)))
 6	(defun make-rsa-signature (s)
 7	  (make-instance 'rsa-signature :s s))
 9	(defmethod sign-message ((key rsa-private-key) message &key (start 0) end)
10	  (make-rsa-signature (encrypt-message key (subseq message start end))))
12	(defmethod verify-signature ((key rsa-public-key)
13				     message
14				     (signature rsa-signature)
15				     &key (start 0) end)
16	  (let ((nonzero (position-if #'plusp message :start start :end end)))
17	    (not (mismatch (subseq message nonzero end)
18			   (encrypt-message key (rsa-signature-s signature))))))
20	(defun make-rsa-key-pair (bits &optional (e 65537) (prng *prng*))
21	  (flet ((find-prime (bits)
22		   (do ((x (generate-prime bits prng) (generate-prime bits prng))
23			(attempts 10 (decf attempts)))
24		       ((= (egcd (1- x) e) 1) x)
25		     (when (zerop attempts) (error "Failed to produce a prime"))))) 
26	    (let* ((bits-p (floor (1+ bits) 2))
27		   (bits-q (- bits bits-p))
28		   (p (find-prime bits-p))
29		   (q (find-prime bits-q))
30		   (n (* p q))
31		   (d (modular-inverse e (* (1- p) (1- q)))))
32	      (values (make-private-key :rsa :n n :d d)
33		      (make-public-key :rsa :n n :e e)))))
35	(eval-when (:compile-toplevel :load-toplevel)
36        (export '(make-rsa-key-pair rsa-signature-s)))

When loaded, this code specialises the generic method SIGN-MESSAGE (on lines 9–10) for the class RSA-PRIVATE-KEY. This specialisation produces instances of a new class, RSA-SIGNATURE (defined on lines 3–4) which holds an unformatted result of exponentiation.

In additon, the program specialises the generic method VERIFY-SIGNATURE (on lines 12–18) for the class RSA-PUBLIC-KEY and for the class RSA-SIGNATURE.

Besides that, there is a new function, MAKE-RSA-KEYPAIR that generates an RSA key which is bits bit long and has e as its public exponent. Finding the first non-zero byte of a specified sub-sequence of the message on line 16 is required because objects of the class RSA-SIGNATURE store the byte representation of a BIGNUM which has no zero-padding on the left while the message may be produced by a hashing algorithm that returns byte arrays of the same length that may have leading zeroes.

The lines 35–36 export the methods MAKE-RSA-KEYPAIR and RSA-SIGNATURE-S to users of the package IRONCLAD. The latter (defined on line 4) is required for extraction of signatures from instances of RSA-SIGNATURE.

This code can be tested with the function TEST-RSA:

 1	(defun test-rsa (digest)
 2	  (multiple-value-bind (private-key public-key) (crypto:make-rsa-key-pair 2048)
 3	    (crypto:verify-signature public-key
 4				     digest
 5				     (crypto:sign-message private-key digest))))
which generates a 2048-bit key and uses it to sign a digest and then immediately verifies the signature. Obviously, this function must always return T.

TEST-RSA can be invoked from the REPL as follows:

CL-USER> (setf crypto:*prng* (crypto:make-prng :fortuna))
CL-USER> (test-rsa (crypto:hex-string-to-byte-array "0102030405060708090a0b0c0d0e0f01020304"))

Caveat emptor! Existing applications and libraries, such as OpenSSL, know absolutely nothing about the format of RSA keys and signatures produced by Ironclad—see the remark of the author of Ironclad regarding formatting schemes which I quoted in the beginning of this article.

Vadim Penzin, October 9th, 2015

I hereby place this article and the accompanying source code into the public domain.
You are welcome to contact me by writing to howto at this domain.
I publish this information in the hope that it will be useful, but without ANY WARRANTY.
You are responsible for any and all consequences that may arise as the result of using this information.