Claudio Cherubino's blog Life of a Googler

Implementation of RSA in F#

During my university course I had to learn and use two functional programming languages: Haskell and Scheme. I fell in love with the former but I never managed to do the same with the syntax of Scheme and the incredibly huge number of parenthesis you have to type in order for your code to work!

That's why I decided to steal borrow a short implementation of the RSA algorithm written in Scheme and translate it into F#.

As you may know, RSA is an algorithm used for public-key encryption based on prime numbers and factorization that is widely use on the web to secure e-commerce transactions.

At the end of the following code there is also a working example that can be executed to better understand the steps required to encrypt and decrypt a message (in this case a single number):

#light
// Modulus operator that handles negative numbers correctly
let modulus n m =
  ((n % m) + m) % m

// Greater Common Divisor
let rec gcd a b =
  match b with
  | b when b = 0 -> a
  | b -> gcd b (a % b)

// extended_gcd = (x,y), such that a*x + b*y = gcd(a,b)
let rec extended_gcd a b =
  if (a % b = 0) then
    (0, 1)
  else
    let (x, y) = extended_gcd b (a % b)
    (y, x - y * (a / b))

// modulo_inverse(a,n) = b, such that a*b = 1 [mod n]
let modulo_inverse a n =
  let (x, y) = extended_gcd a n
  modulus x n

// totient(n) = (p - 1)*(q - 1),
// where pq is the prime factorization of n.
let totient p q = (p - 1) * (q - 1)

// square(x) = x^2
let square x = x * x

// modulo-power(base,exp,n) = base^exp [mod n]
let rec modulo_power b exp n =
  if (exp = 0) then
    1
  else
    if (exp % 2 = 1) then
      (((modulo_power b (exp - 1) n) * b) % n)
    else
      ((square (modulo_power b (exp / 2) n)) % n)

// RSA routines.

// A legal public exponent e is between
// 1 and totient(n), and gcd(e,totient(n)) = 1
let is_legal_public_exponent e p q =
  (1 < e) && (e < (totient p q)) && (1 = (gcd e (totient p q)))

// The private exponent is the inverse of the public exponent, mod n.
let private_exponent e p q =
  if (is_legal_public_exponent e p q) then
    modulo_inverse e (totient p q)
  else
    raise (new System.Exception("Not a legal public exponent for that modulus"))

// An encrypted message is c = m^e [mod n]
let encrypt m e n =
  if (m > n) then
    raise (new System.Exception("The modulus is too small to encrypt the message"))
  else
    modulo_power m e n

// A decrypted message is m = c^d [mod n]
let decrypt c d n =
  modulo_power c d n

// RSA example.
let p = 61
let q = 53
let n = p * q
let e = 17
let d = private_exponent e p q
let message = 123
let c = encrypt message e n
let m = decrypt c d n

I think the code presented is self-explainatory and each function is briefly described in the comments, but there is a strange thing that you may have noticed.

The first function I defined is the modulus operator, but F# already has a modulus operator, so why bothering?

Before writing that function I was about to getting crazy, since everything else was already written but the encryption was not working properly. I debugged and tested again and again and eventually I found out that sometimes the result of the native modulo operation was a negative number.

After a short lookup on Wikipedia, I discovered that each programming language implements the modulo operator differently and while in Scheme the result has the same sign as the divisor, in F# the sign of the result is the same as the dividend!