Implementing toy RSA in Ruby, on a dare
Problem statement
So today, I’m publishing my “toy RSA in 5 minutes in Ruby”, along with a backstory.
Backstory
I have a longstanding dispute with a friend of mine (Skurt) about the way things are taught at our Alma mater. One of his claims is that they don’t teach you enough practical knowledge to be useful^{1}.
Anyway, the other day Skurt wanted to implement a toy RSA cryptosystem (end to end). And since he’s doing it rather poorly (so far), I got nerd sniped into doing it too^{2}. Because obviously it won’t take more than 5 minutes.
Solution
The RSA (cryptosystem) wiki
page is somewhat useful in getting to the solution^{3}. The one thing they (and
others) somewhat gloss over is the computation of d
, the private exponent.
So, yeah. Toy RSA is simpleish. We have two primes, p
and q
, whose product
makes up public modulo n
.
Then we have a public exponent e
(chosen ~arbitrarily, but with a constraint
that it has to be coprime with
ϕ(n)
^{4}).
Result of which is the public key tuple: (n, e)
.
And then we have the clincher, private exponent d
, which is multiplicative
inverse of e
(modulo ϕ(n)
(or λ(n)
, depending on your inclination)).
The way wikipedia talks about d
is funny:
This means: solve for d the equation
de ≡ 1 (mod λ(n))
; d can be computed efficiently by using the extended Euclidean algorithm, […]
And I don’t mean ha ha funny. What I mean is that most of the first page search engine hits on RSA I looked at basically gloss over the specific – even if rather simple – computation.
Anyway, armed with d
(which you get from e
and z
using
extended euclidean algorithm),
you also have the full private key tuple: (n, d)
, or maybe (n, d, p, q)
if you want to be fancy down the line.
Rubying that up is easy:
#!/usr/bin/env ruby
# Warning: this will blow up beyond very small numbers;
# see better version below.
require 'prime'
p = 17 # prime 1
q = 13 # prime 2
e = 5 # public exponent
m = 23 # message
raise "p not prime" unless p.prime?
raise "q not prime" unless q.prime?
n = p * q
z = (p1).lcm(q1) # we go with λ(n) here; roll with it.
raise "e < 2" if e < 2
raise "e >= z" unless e < z
raise "e and z not coprime" unless e.gcd(z) == 1
# https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Modular_integers
def inverse(a, n)
t, newt, r, newr = 0, 1, n, a
until newr.zero?
q = r / newr
t, newt = newt, t  q * newt
r, newr = newr, r  q * newr
end
raise "#{a} not invertible" if r > 1
t += n if t < 0
t
end
d = inverse(e, z)
raise "m < 2" if m < 2 # these make zero sense, IMO
raise "m >= n" unless m < n
c = m**e % n
mm = c**d % n
raise "m != mm" unless m == mm
puts "Public key: (#{n}, #{e})"
puts "Private key: (#{n}, #{d})"
puts "Message #{m} encrypts to: #{c}"
puts "Message #{c} decrypts to: #{mm}"
And the output is as expected:
Public key: (221, 5)
Private key: (221, 29)
Message 23 encrypts to: 160
Message 160 decrypts to: 23
Actual use
First off – don’t. Seriously, do not use naked toy RSA for anything. The OAEP exists for a reason.
But, this is for fun. So, let’s foolishly proceed with a gleam in our eye.
Let’s say we want to encrypt short texts using our toy RSA^{5}. Let’s say up to 10 bytes, so we need at least 81bit RSA modulus to be safe.
Easy:
# Fear my awesome prime picking powers, lowly human.
$ nextprime.rb 8887776665554
8887776665563
$ nextprime.rb 9998887776665
9998887776739
$ ruby e 'p (8887776665554*9998887776739).bit_length'
87
But we hit a snag with the code I posted above:
$ ruby toyrsa.rb
toyrsa.rb:21: warning: in a**b, b may be too big
Traceback (most recent call last):
toyrsa.rb:29:in `<main>': m != mm (RuntimeError)
That’s because Ruby’s exponentiation is rather naïve.
So we need a better modexp
to make even our 87bit RSA to work.
And while we could use OpenSSL for that^{6}, let’s do it the hard way –
by monkeypatching in Integer.modexp
that uses the
squaring approach to modular exponentiation^{7}:
#!/usr/bin/env ruby
require 'prime'
p = 8887776665563
q = 9998887776739
e = 65537
m_raw = ARGV.first  "hoi, world"
m = m_raw.bytes.inject(0){m,x m<<8x} # network order FTW
raise "p not prime" unless p.prime?
raise "q not prime" unless q.prime?
n = p * q
z = (p1).lcm(q1) # we go with λ(n) here; roll with it.
raise "e < 2" if e < 2
raise "e >= z" unless e < z
raise "e and z not coprime" unless e.gcd(z) == 1
# multiplicative inverse of a (mod n) via extended euclidean algo
def inverse(a, n)
t, newt, r, newr = 0, 1, n, a
until newr.zero?
q = r / newr
t, newt = newt, t  q * newt
r, newr = newr, r  q * newr
end
raise "#{a} not invertible" if r > 1
t += n if t < 0
t
end
d = inverse(e, z)
raise "m < 2" if m < 2 # these make zero sense, IMO
raise "m >= n" unless m < n
class Integer
# self**e % n, by running powers of two
def modexp(e, n)
s = 1 # running result
x = self.to_i # initially: x**1
until e.zero? # until no bits left
s = (s * x) % n if e.odd? # * current power if lsb set
e >>= 1 # drop one bit
x = (x*x) % n # get next power mod n
end
s
end
end
c = m.modexp(e, n)
mm = c.modexp(d, n)
raise "m != mm" unless m == mm
puts "Public key: (#{n}, #{e})"
puts "Private key: (#{n}, #{d})"
puts "Message #{m} encrypts to: #{c}"
puts "Message #{c} decrypts to: #{mm}"
class Integer
def to_text
out = []
c = self
until c.zero?
out << (c&0xff)
c >>= 8
end
# nonprintable chars and '"' are encoded as \x<hexcode>, as per usual
out.reverse.map { x
((32..126).to_a[34]).include?(x) ? x.chr : "\\x%02x" % x
}.join
end
end
puts "Original message as text: \"#{m.to_text}\""
puts "Encrypted message as text: \"#{c.to_text}\""
puts "Decrypted message as text: \"#{mm.to_text}\""
Which ends up outputting:
$ ruby toyrsa.rb
Public key: (88867881463683987813739057, 65537)
Private key: (88867881463683987813739057, 14605202251118597539744223)
Message 493181281278595163122788 encrypts to: 16245416456256413048157205
Message 16245416456256413048157205 decrypts to: 493181281278595163122788
Original message as text: "hoi, world"
Encrypted message as text: "\x0dp\x19\xcam\xf3\xf2s\xda\xb4\x15"
Decrypted message as text: "hoi, world"
$ ruby a.rb "foo"
Public key: (88867881463683987813739057, 65537)
Private key: (88867881463683987813739057, 14605202251118597539744223)
Message 6713199 encrypts to: 36834036670485844285978001
Message 36834036670485844285978001 decrypts to: 6713199
Original message as text: "foo"
Encrypted message as text: "\x1ew\xe9!\x04\xac\xa0\x22\xe7\xf5\x91"
Decrypted message as text: "foo"
Closing words
There you have it, a toy RSA cryptosystem in Ruby. As you can see, the dry theory is miles away from the implementation – for multiple reasons.
And this barely scratched what would be required for a robust productionready implementation. For that one, please peruse OpenSSL or similar battle tested library^{8}.
And in case you’re wondering… no, it did not take 5 minutes. I’m neither superhuman nor a 100x programmer. It took somewhat longer (not sure about exact timing), and it took even longer still to put it into a blogpresentable form^{9}.

To which my counterargument always is that independent “homework” is where theory and practical knowledge meet. Go figure, eh? ↩

Last time I implemented RSA – poorly – was when I was young and naïve, needing a way to sign software updates. So armed with Schneier’s red book, I took a stab at it. Don’t get me wrong, it worked marvelously in the MSDOS app where I used it… but man, give me openssl any day of the week instead. ↩

And if you don’t know RSA by heart, it’s a good read. The original RSA paper is probably better for an end to end example, but hey, either works. ↩

Technically either Euler’s totient function: ϕ or, better (smaller), Carmichael’s totient function: λ. ↩

I mean, the original RSA paper explains exactly this scenario, but you’re too cool for that, and that paper’s not in Ruby, yes? ;) ↩

c = m.to_bn.mod_exp(e, n).to_i
↩ 
See Modular exponentiation for an indepth explainer. But essentially you can compute it by just iteratively generating increasing powers of two of the original number and multiplying some of these powers together. That way you never stray beyond simple multiplication (mod
n
). ↩ 
And if you’re not hell bent on RSA, how about you do yourself a favor and use libsodium? You can thank me later. ↩

And let’s not forget the
d = e**(z  1) % z
culdesac which I thought is going to work as a consequence of Lagrange’s theorem… but doesn’t (not always, anyway). I might suck at group theory? ↩