Written on 

Implementing toy RSA in Ruby, on a dare

fun programming quickie ruby

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 useful1.

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 too2. Because obviously it won’t take more than 5 minutes.

Solution

The RSA (cryptosystem) wiki page is somewhat useful in getting to the solution3. The one thing they (and others) somewhat gloss over is the computation of d, the private exponent.

So, yeah. Toy RSA is simple-ish. 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 = (p-1).lcm(q-1) # 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 RSA5. Let’s say up to 10 bytes, so we need at least 81-bit 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 87-bit RSA to work.

And while we could use OpenSSL for that6, let’s do it the hard way – by monkeypatching in Integer.modexp that uses the squaring approach to modular exponentiation7:

#!/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<<8|x} # network order FTW

raise "p not prime" unless p.prime?
raise "q not prime" unless q.prime?

n = p * q
z = (p-1).lcm(q-1) # 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
    # non-printable 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 production-ready implementation. For that one, please peruse OpenSSL or similar battle tested library8.

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 blog-presentable form9.

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

  2. 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 MS-DOS app where I used it… but man, give me openssl any day of the week instead. ↩

  3. 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. ↩

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

  5. 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? ;) ↩

  6. c = m.to_bn.mod_exp(e, n).to_i ↩

  7. See Modular exponentiation for an in-depth 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). ↩

  8. And if you’re not hell bent on RSA, how about you do yourself a favor and use libsodium? You can thank me later. ↩

  9. And let’s not forget the d = e**(z - 1) % z cul-de-sac 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? ↩