## 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!

Jon HarropDecember 2nd, 2008 - 02:49

Ironically, your F# code is littered with superfluous parentheses.

Great example though. Thanks!

claudioDecember 5th, 2008 - 10:32

Maybe I’ve read too much Scheme in these days and I’ve been infected by its syntax!