I’ve just finished reading Cryptography Decrypted by H.X.Mel and Doris Baker. I’ve read a few texts on the the subject before, but this was certainly the most accessible book on the subject that I have ever read. It covered some of the history of code making and code breaking, and then moved on to symmetric and asymmetric cryptography followed by an introduction to IPSec and SSL. It explained the basic concepts well with many examples, pushing some of the details in the appendixes of the book.

One of the appendixes covered the math behind public key cryptography, and since I’d never tried implementing any of this stuff before, I thought I should see how hard it was to implement (in a very inefficient manner). My current favourite language for rapidly prototyping code on .NET is F#. The type checking together with the REPL (read-eval-print loop) make it easy to write code while exploring the problem space. In the end I spent about one hour getting some of the basic algorithms together.

This is a copy of the F# session:

First we define a function for checking if a number is prime, by testing for divisibility by all numbers up to the square root of the number under test. We use the bigint type, a type containing unbounded integer values. This is separate from the integer type and requires us to put I after the numeric forms to avoid type errors.

> #light

– let isPrime (n : bigint) =

– let lim = Math.BigInt.FromInt64(int64(sqrt(float(n))))

– let rec sieve m =

– m > lim or (n % m <> 0I && sieve (m+1I))

– sieve 2I;;

– let isPrime (n : bigint) =

– let lim = Math.BigInt.FromInt64(int64(sqrt(float(n))))

– let rec sieve m =

– m > lim or (n % m <> 0I && sieve (m+1I))

– sieve 2I;;

val isPrime : bigint -> bool

We can run a few quick tests on the function.

> isPrime 2I;;

val it : bool = true

> isPrime 3I;;

val it : bool = true

> isPrime 4I;;

val it : bool = false

> isPrime 5I;;

val it : bool = true

val it : bool = true

> isPrime 3I;;

val it : bool = true

> isPrime 4I;;

val it : bool = false

> isPrime 5I;;

val it : bool = true

We’ll need a list of small primes later for filtering, so we can quickly generate them using a sequence expression.

> let smallPrimesSequence = seq { 2I .. 100I} |> Seq.filter isPrime;;

val smallPrimesSequence : seq<bigint>

> for i in smallPrimesSequence do

– printfn "%A" i;;

2I

3I

…… lots of lines missed out

– printfn "%A" i;;

2I

3I

…… lots of lines missed out

97I

val it : unit = ()

> let smallprimes = Seq.to_list smallPrimesSequence ;;

val it : unit = ()

> let smallprimes = Seq.to_list smallPrimesSequence ;;

val smallprimes : bigint list

We define a function for raising one number to an integer power, and test it on a sequence that we recognise.

> let power n m =

– let rec accumulatedPower acc left raised =

– if left = 0I

– then acc

– else

– let acc’ = if left % 2I = 1I then acc * raised else acc

– accumulatedPower acc’ (left / 2I) (raised * raised)

– accumulatedPower 1I m n;;

– let rec accumulatedPower acc left raised =

– if left = 0I

– then acc

– else

– let acc’ = if left % 2I = 1I then acc * raised else acc

– accumulatedPower acc’ (left / 2I) (raised * raised)

– accumulatedPower 1I m n;;

val power : Math.BigInt -> bigint -> bigint

> for i in 1I .. 12I do

– printfn "%A" (power 2I i);;

2I

4I

8I

16I

32I

64I

128I

256I

512I

1024I

2048I

4096I

val it : unit = ()

> for i in 1I .. 12I do

– printfn "%A" (power 2I i);;

2I

4I

8I

16I

32I

64I

128I

256I

512I

1024I

2048I

4096I

val it : unit = ()

A good way to spot non-primes is to see if a number passes the Fermat test. For a prime p, and a number m less than p, it is a theorem of Fermat that m ^ (p-1) mod p = 1. We’ll apply the Fermat test with the value m as 2,3,5,7. If the number passes this and isn’t divisible by any of the number on our list of primes, we know there is a very good chance of it being prime.

> let possiblePrimeViaFermat (p : bigint) m =

– (power m p) % p = m;;

– (power m p) % p = m;;

val possiblePrimeViaFermat : bigint -> Math.BigInt -> bool

> possiblePrimeViaFermat 127I 3I;;

val it : bool = true

> possiblePrimeViaFermat 105I 3I;;

val it : bool = false

> let testForPrimality (n : bigint) =

– let rec filterUsingSmallPrimes candidates =

– match candidates with

– | [] -> true

– | h::t -> (n % h <> 0I && filterUsingSmallPrimes t)

– let fermatTest = possiblePrimeViaFermat n

– filterUsingSmallPrimes smallprimes

– && fermatTest 2I && fermatTest 3I

– && fermatTest 4I && fermatTest 5I;;

val it : bool = true

> possiblePrimeViaFermat 105I 3I;;

val it : bool = false

> let testForPrimality (n : bigint) =

– let rec filterUsingSmallPrimes candidates =

– match candidates with

– | [] -> true

– | h::t -> (n % h <> 0I && filterUsingSmallPrimes t)

– let fermatTest = possiblePrimeViaFermat n

– filterUsingSmallPrimes smallprimes

– && fermatTest 2I && fermatTest 3I

– && fermatTest 4I && fermatTest 5I;;

val testForPrimality : bigint -> bool

> testForPrimality 220I;;

val it : bool = false

val it : bool = false

Given a starting value that we’ll suppose has been generated randomly, we need to find the next prime.

> let rec nextPrime (n : bigint) =

– if testForPrimality n

– then n

– else nextPrime (n+1I);;

– if testForPrimality n

– then n

– else nextPrime (n+1I);;

val nextPrime : bigint -> bigint

> nextPrime 101I;;

val it : bigint = 101I

val it : bigint = 101I

Given two numbers, a modulus value n and a potential exponent in the public key algorithm, m, we need to determine if n and m are co-prime and we need to determine the multiplicative inverse of m in the group for that modulus. A modified version of Euclid’s algorithm allows us to calculate both values at the same time.

> let rec hcf (n : bigint) m =

– let rec hcf’ a b c d =

– if b = 0I

– then (a, if c < 0I then c + n * (1I + (-c / n)) else c)

– else

– let multiple = a / b

– hcf’ b (a – b * multiple) d (c – d * multiple)

– if n < m then failwith "invalid parameters" else hcf’ n m n 1I;;

– let rec hcf’ a b c d =

– if b = 0I

– then (a, if c < 0I then c + n * (1I + (-c / n)) else c)

– else

– let multiple = a / b

– hcf’ b (a – b * multiple) d (c – d * multiple)

– if n < m then failwith "invalid parameters" else hcf’ n m n 1I;;

val hcf : bigint -> bigint -> bigint * Math.BigInt

> hcf 7I 5I ;;

val it : bigint * Math.BigInt = (1I, 3I)

> hcf 8I 4I;;

val it : bigint * Math.BigInt = (4I, 1I)

val it : bigint * Math.BigInt = (1I, 3I)

> hcf 8I 4I;;

val it : bigint * Math.BigInt = (4I, 1I)

The first return value shows that 7 and 5 are co-prime, and that 3 * 5 = 1 mod 7. The second example shows that 8 and 4 are not co-prime.

Given two primes, p and q, we need to find e and d where e * d = 1 mod (p-1)(q-1) and e is co-prime to (p-1)(q-1). Algorithms usually start out with e=3 and only use another value if it doesn’t meet the criteria.

> let getExponents p q =

– let decrementedPrimeProduct = (p – 1I)*(q – 1I)

– let rec testExponent e =

– let (h, d) = hcf decrementedPrimeProduct e

– if h = 1I then (e,d) else testExponent (e+1I)

– testExponent 3I;;

– let decrementedPrimeProduct = (p – 1I)*(q – 1I)

– let rec testExponent e =

– let (h, d) = hcf decrementedPrimeProduct e

– if h = 1I then (e,d) else testExponent (e+1I)

– testExponent 3I;;

val getExponents : bigint -> Math.BigInt -> bigint * Math.BigInt

> getExponents 5I 11I;;

val it : bigint * Math.BigInt = (3I, 27I)

val it : bigint * Math.BigInt = (3I, 27I)

Lastly, we can define a function that takes the two primes and returns the modulus and the exponents for encrypting and decrypting.

> let getPublicPrivateKeys p q =

– let n = p * q

– let (e,d) = getExponents p q

– (n,e,d);;

– let n = p * q

– let (e,d) = getExponents p q

– (n,e,d);;

val getPublicPrivateKeys :

bigint -> Math.BigInt -> Math.BigInt * bigint * Math.BigInt

bigint -> Math.BigInt -> Math.BigInt * bigint * Math.BigInt

For the example in the book, they take primes 5 and 11 and get exponent 3 for encrypting and 27 for decrypting.

> getPublicPrivateKeys 5I 11I;;

val it : Math.BigInt * bigint * Math.BigInt = (55I, 3I, 27I)

val it : Math.BigInt * bigint * Math.BigInt = (55I, 3I, 27I)

We can define a test function for passing a message through the encoding process:

> let test keyData message =

– match keyData with

– | (modulus, e, d) ->

– let encoded = (power message e) % modulus

– let decoded = (power encoded d) % modulus

– (message, encoded, decoded);;

– match keyData with

– | (modulus, e, d) ->

– let encoded = (power message e) % modulus

– let decoded = (power encoded d) % modulus

– (message, encoded, decoded);;

val test :

Math.BigInt * bigint * bigint -> Math.BigInt ->

Math.BigInt * Math.BigInt * Math.BigInt

Math.BigInt * bigint * bigint -> Math.BigInt ->

Math.BigInt * Math.BigInt * Math.BigInt

> let myTest = test (getPublicPrivateKeys (nextPrime 170I) (nextPrime 300I));;

val myTest : (Math.BigInt -> Math.BigInt * Math.BigInt * Math.BigInt)

> myTest 29292I;;

val it : Math.BigInt * Math.BigInt * Math.BigInt = (29292I, 2290I, 29292I)

val it : Math.BigInt * Math.BigInt * Math.BigInt = (29292I, 2290I, 29292I)

All in all, this was quite a fun experience. The algorithms are easy to write in F# without having to add a lot of fluff to get things to run, and it is easy to execute the functions from the command line to test out the code and explore the problem space.

Advertisements