RSA

rsa.clj contains an implementation of the famous RSA algorithm for public-key cryptography. Lucid explanations can be found at the following sources (sorted in order of increasing depth):

Computerphile video

Scientific American August 1977 - Mathematical Games Column - by Martin Gardner
(Where the RSA algorithm was first introduced to the world.)

Quantum Computing since Democritus - Chapter 8 - by Scott Aaronson
(Look for the section titled "Public-Key Cryptography".)

And then of course there's sections 10.8.2 for the Miller-Rabin test and 15.5.1 for the RSA algorithm in The Nature of Computation itself.

Usage

Let's go through the simple example of en- and decrypting the message "It's all Greek to me.". One of the first steps is to put this string into a form that can be encrypted.

(string-to-bigints "It's all Greek to me." 1)
=> (73N 116N 39N 115N 32N 97N 108N 108N 32N 71N 114N 101N 101N 107N 32N 116N 111N 32N 109N 101N 46N)

The 1 that's passed in as the second argument is the bytesize - the number of bytes each piece of our message should contain. So this operation has just split the input into its constituent bytes and converted each of them to a BigInt. You can check in an ASCII table that the first message - 73 - indeed codes for "I". The reason I'm using BigInts is so that we can also play around with much longer pieces that wouldn't even fit into a long anymore. But integers of other forms will also work almost everywhere.
Then we'll also need some keys.

(make-keys 8 3)
=> {:p 11N, :q 149N, :N 1639N, :e 3}

I picked bitsize to be 8 because that way our public key N - the product of two 8 bit primes - will likely be about 16 bits large. This ensures that N will be larger than any of the 8 bit messages we want to encrypt which is a prerequisite for the whole procedure to work.
The public exponent e = 3 is pretty much arbitrary and as Scott Aaronson points out we could use the 3 all the time and RSA would still be fully secure for all that we know. Next we can encrypt our messages using these keys.

(->> (string-to-bigints "It's all Greek to me." 1)
     (map #(mod-exp % 3 1639)))
=> (574N 568N 315N 1522N 1627N 1389N 960N 960N 1627N 609N 1527N 1009N 1009N 710N 1627N 568N 705N 1627N 219N 1009N 635N)

In order to decrypt the message we need to find the inverse of the public exponent 3 in the group ℤ*_N, which consists of the integers in {1,2,...,N-1} that are relatively prime with N equipped with multiplication mod N.

(invert 3 1480)
=> 987

Here 1480 is the product of p-1 and q-1, also known as the value of Φ(N) - Euler's totient function.
Armed with the inverse let's try to recover the "I" from 574.

(mod-exp 574 987 1639)
=> 73

Lo and behold, the "I" reemerges. Unsurprisingly, decrypting the entire encrypted message produces the original message.

(->> (string-to-bigints "It's all Greek to me." 1)
     (map #(mod-exp % 3 1639))
     (map #(mod-exp % 987 1639))
     (bigints-to-string))
=> "It's all Greek to me."

Finally, let's do all this with much larger keys. This also serves as an opportunity to demonstrate some more convenient means of performing this whole process.

(encrypt-with-new-keys "It's all Greek to me." 256 3)
=>
{:p 36624295014746265099639088700649908391958262331566733922223197576530556458479N,
 :q 105371283202271675588216405013292722389073931816854752709416803336015283840699N,
 :N 3859148962082375392876981504756630778460377560253689167039763552737733113439287573349797833748622365971906314775518120588866401315123488571961218643836821N,
 :e 3,
 :encryption (1237198621754668141601114137498733386308684007111396463942487077692084075765836951167314627874506042862410074740101930089482947317189595602808983255096N)}

(decrypt (encrypt-with-new-keys "It's all Greek to me." 256 3))
=> "It's all Greek to me."