Note 1:
This article is executable code. You can copy and paste this article in a file with extension .lhs (say crypto.lhs), load it in a haskell interpreter and run the examples! You can get started by installing the haskell platform on Windows, Linux or Mac. You can learn Haskell by reading the excellent tutorial called Learn you a haskell by Miran Lipovaca. It is also available as a book from "no starch press".
Note 2:
All lines starting with > are interpreted by the haskell interpreter. All such lines are shown enclosed inside a box in this article.
Note 3:
Code shown in magenta color is code that you can type at the interpreter prompt after loading this article.
Professor Knuth is world famous for his "The Art of Computer Programming" series of books, where he uses a hypothetical assembly level language called MIX to describe the algorithm. The reader cannot make use of a PC in understanding the algorithm by loading it and trying it out with some sample data. You have some algorithm books that use C or Java. But because these language don’t provide a high degree of abstraction, the essence of the algorithm is lost in the scaffolding, in my opinion.
Haskell would be the better choice instead of assembly or C or Java. Not only can you describe the algorithm with a high level of abstraction, you can also load the file into a haskell interpreter and run it. Okasaki has described several algorithms succinctly using a functional language.
There are several advantages of using haskell:
Literate style:
In literate style of programming, documentation (or comments) is given more importance and is therefore the default, and the interpreter or compiler will ignore it. It is for human consumption. In other words, you don’t need comment markers like /* or // or #; however, you need to mark code to inform the compiler to process it. In haskell, you mark the code by prefixing the line with a >. This means that you can put this whole blog article in a file with suffix .lhs (say crypto.lhs), load and run it in haskell interpreter. Try it.
Lazy Evaluation:
In additional to being a functional language, another advantage of haskell is that evaluation is lazy. For example in the code below, oddNumbers refers to all the odd numbers. Because haskell uses lazy evaluation, nothing is computed unless it is needed.
> oddNumbers = [1,3..]
However, if you type oddNumbers in the interpreter, you will get an endless supply of odd numbers. If you want the first 20, you can say
> odd20 = take 20 oddNumbers
When you type
odd20
you will get [1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39].
Type inferencing:
The code is not cluttered with types for variables and functions. At the same time, unlike ruby or python or perl or javascript, haskell is a statically typed language — due to the magic of type inferencing, you can ask the interpreter for the type.
For e.g., if you type
:t odd20
at the interpreter prompt, you will get odd20 :: [Integer]
That is, oddNumbers is a list of Integers.
How about the type of a function? Type
:t filter
and you will get filter :: (a -> Bool) -> [a] -> [a]
That is, filter is a function that takes a function as its first argument, a list as the second argument [^1] and returns a list. The first argument (a -> Bool) is any function that takes an arbitrary type a and returns True or False. What filter does is take as one by one from the second argument, feed it to the (a -> Bool) function; if the result is true then the a is included in the resultant list; if not the a is not included, that is filtered out.
[^1]: in haskell, all functions can be treated as having a single argument
For e.g. if you type
filter (> 20) odd20
you will get [21,23,25,27,29,31,33,35,37,39]
As mentioned earlier, the first argument to filter is a function. You can define your own function like this (\x -> …). For e.g. if we wanted to get numbers from odd20 that are more than 20 but less than 30, you can type
filter (\x -> (x > 20) && (x < 30)) odd20
and you will get [21,23,25,27,29]
No limitation of word size
You don’t need to worry about overflow. For e.g. you can type
aa = 11111111111111111111111111111111111111111111111111111111111111111111
With these formalities over, let us start Public key cryptography example.
Here’s a brief overview of Public key cryptography. You can skip this section if you know about this.
public key cryptography uses 2 keys. If one key is used to encrypt the data the other key is required to decrypt it and vice versa. One of the keys is called the public key — you give this to anyone who wants to send an encrypted message to you — and the other is called the private key, which as the name says only you know. If someone wants to send you a encrypted message which only you can decrypt, the sender will encrypt it using your public key. This message can only be decrypted by your private key — if you keep the key secret only you can decrypt the message. However, when you want to digitally sign a message (typically you sign the hash of the message), you will encrypt the message (or the hash) with your private key. The message can be decrypted by everyone who has your public key. But given that only you could have encrypted it, the recipients know that the message could only have come from you and that it has not been tampered with. Non-repudiation is achieved: that is, you cannot say that you didn’t send the message. Of course you can always claim that someone stole your laptop and got your private key which you didn’t protect with a good passphrase. To prevent replay of your message at a later time, the message can have a message number and timestamp.
Public key cryptography employs large prime numbers. Typically, you take a huge odd number not ending in 5 and run some primality tests (like Rabin-Miller or AKS) which will tell if it is a prime number with a high degree of certainty.
For our purposes, let us use the Sieve of Eratosthenes to get random numbers.
Let us start with all odd numbers starting with 3, represented by [3,5..]. The first number in the list — 3 in this case — is always prime. Store the first number (3) and remove it and all multiples of it from the list. Now run the algorithm again on the remaining items on the list. This can be expressed succinctly in haskell as
> sieve = sieveget [3,5..]
> where sieveget (x:xs) = x : sieveget (filter (\y -> y rem x /= 0) xs)
sieveget function is given [3,5..] which is a list of all odd numbers starting from 3. (x:xs) disassembles the list into the first item x and the rest of the list xs. The : function prepends an item to a list. For e.g. if you type
10 : [12, 40]
you will get [10,12,40]
The first item x in the list to sieveget is prime and so we keep it and run the sieveget function on the filtered list. We start with xs which is all but the first item and then we filter out all numbers that are a multiple of x. That is, if the remainder is not zero we keep it
Now we want the first 100 odd prime numbers, you can type
take 100 sieve
you will get
[3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,
71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,
149,151,157,163,167,173,179,181,191,193,197,199,211,223,
227,229,233,239,241,251,257,263,269,271,277,281,283,293,
307,311,313,317,331,337,347,349,353,359,367,373,379,383,
389,397,401,409,419,421,431,433,439,443,449,457,461,463,
467,479,487,491,499,503,509,521,523,541,547]
Now, when you take 2 huge prime numbers p and q (several hundred digits long) and multiply them, it is computationally infeasible to get the factors p and q given the product n. This in-feasibility forms the basis for the security of public key cryptography. We will use smaller primes initially.
Let us take 2 prime numbers p=419, q=467 and multiply them to get n=231689
> p = 443 > q = 523 > n = p * q > phi = (p -1 ) * (q - 1)
phi is 230724. Pick a number e less than phi, which is relatively prime w.r.t phi. That is, pick e such that gcd(phi, e) is 1. gcd is the greatest common divisor. gcd is a built-in function in haskell. We can pick e by taking the list of numbers from 3 to phi, represented by [3..phi], feed the numbers in the list one by one into a function that checks if it is relatively prime w.r.t phi and if not drop it. We provide the function (\x -> …) and use the builtin haskell function dropWhile. After dropWhile is done, the first number in the list is e and so we use head to extract it. Code is shown below.
> getRelPrim phi = head $ dropWhile (\x -> gcd phi x /= 1) [3..phi] > e = getRelPrim phi
So, we have phi = 230724, e = 5 and gcd(phi, e) is 1.
We can use the extended euclid algo to compute x and d such that
phi x + e d = 1
That is, 230724 x + 5 d = 1
or
e d = 1 – phi x
e d = 1 mod phi
d is called the inverse of e as e d is 1 (modulo phi).
(e, n) is the public key and (d, n) is the private key.
Encryption and Digital Signature:
To encrypt a message m (value > 0 and < n) using your public key, you raise it to power e (modulo n). To decrypt, you raise the encrypted message to power d (modulo n) and you will get the message m back.
For digital signatures, you will raise the message m to the power d and the recipient will raise it to the power e (all operations modulo n).
That is m^ed (mod n) = m. Also m^de (mod n) = m. This result derives from Fermat’s little theorem that says that if ‘p’ is prime and does not divide ‘a’ then a^(p-1) = 1 mod p.
The myegcd function computes extended gcd and myegcdprint prints the equation. We will describe these functions later.
> (_,_,d) = myegcd phi e
The myegcd function returns a 3-tuple and we are only interested in the 3rd item d and so we use (_,_,d) where _ represents don’t care.
If you type
myegcdprint phi e
you will get "230724 -1 + 5 46145 = 1"
You can verify that this is true.
So, d is 46145.
The inverse of e (currently 5) is d (currently 46145) when using modulo phi arithmetic.
As e d = 1 mod phi, we have 5 46145 = 1 mod 230724.
We have public key (e, n) = (5, 231689) and private key (d, n) = (46145, 231689).
Encryption example:
You encrypt the message by raising it to the power e (modulo n) and decrypt by raising the encrypted value to the power d, modulo n.
Say the message that we want to encrypt is 223344. Note the message should be less than n which in this case is 231689
> m = 223344 > encryptedData = expm m e n > decryptedData = expm encryptedData d n
Now, if you type
m == decryptedData
you will get True
Digital Signature example:
You sign a message m by raising it to the power d (modulo n) and verify it by raising it to the power e, modulo n. Typically, for signatures, you sign the hash of the message.
> signedData = expm m d n > verify = expm signedData e n
Now, if you type
m == verify
you will get True
We used extended euclid algo to get d, the inverse of e. I have written the haskell function to compute this.
You can lookup Extended euclid algo on the net. As we recursively compute the GCD of (phi and e), at each step, we compute two values x and d so that the phi x + e d is equal to the intermediate result. When the algo terminates, phi x + e d will equal the gcd. In this case, the gcd will be 1 as phi and e are relatively prime.
> myegcd a b | a < b = myegcd b a
> | otherwise = myegcdint a 1 0 b 0 1
> where
> myegcdint a x1 y1 b x2 y2
> | a == 1 || b == 0 = (a,x1,y1)
> | otherwise = myegcdint b x2 y2 (a-q*b) (x1-q*x2) (y1-q*y2)
> where q = a div b
The myegcdprint function will print the extended euclid equation in human readable form.
> myegcdprint a b = show a ++ " * " ++ show x ++ " + " ++ show b ++ " * " ++ show y ++ " = " ++ show g > where (g, x, y) = myegcd a b
Fast exponentiation
We saw that encryption and decryption involve exponentiation where numbers are raised to huge powers. The fast way of doing exponentiation is square and multiply. The idea is that if you want to compute x^16, instead of computing x x x…., we compute it as
x^8^2 which is x^4^2^2 which is x^2^2^2^2. That is, compute x squared, take square of that, take square of that, take square of that. As we are doing modulo n arithmetic, at every computation the result will be less than n.
Compute x power y mod n
> expm :: Integer -> Integer -> Integer -> Integer > expm x y n | y == 0 = 1 > | even y = squareMod (expm x (ydiv2) n) > | otherwise = (x * expm x (y - 1) n)modn > where squareMod x = (x * x)modn
I had mentioned that (e,n) is the public key and (d, n) is the private key, where n is th product of 2 large prime numbers p and q.
Let’s take an actual example of using keys generated by the ssh-keygen program. The keys generated are public key (e2, n2) and private key (d2, n2). It is computationally infeasible to compute the factors of n2.
> e2 = 35 > n2 = 24599401746186544753585961989720697860704715921318395940811762321215824807557621697773907059796278097849505445501910724127399058460980693293203072038002590801395199249852129071785672432585203410476016181097544362116141296152084962539836378639714910932045653550299284024139643780887744160517654443042858165440470729203910671971108375907799483531295095884757318712743604139662876557480089185990901673609791265534652918892119685256352928215530103500864655881906626489900075970231161622248096171641166493196571900381773587416989060932497512209232086471223469521552685754200399412399363427090919531299307639414716933116679 > d2 = 23896561696295500617769220218585820778970295466423584628217140540609658384484546792123224000944955866482376718487570417723759085362095530627682984265488231064212479271284925384020367505939911884462415718780471666055680116262025392181555339250008770619701492020290733052021368244290951470217150030384490789284723446352612874100855163720916693652323338592824320761571069766455515173265488168772631721275227008702052324471708016271923750701117083641222829878315994730013466394834385556567998059103378941822186911574514956042021813821291695649765910911868786507227896870707132539618458226575245639015267416267484415584011
Let’s encrypt the same message m = 223344.
> encryptedData2 = expm m e2 n2
If you type
encryptedData2
in the interpreter console you will get a huge number
16371940091952870870086641812654237642504965017693
59496018555325696511812776190362956365134904583170
98213327230928068269952348286568103082758511794183
25837307448454601341922223332549197824
Now let us decrypt it using the private key
> decryptedData2 = expm encryptedData2 d2 n2
You will get back the input. You can check by typing
input2 == decryptedData2
Note that the computations hardly take any time though we are taking numbers to very high power. This is because numbers don’t get very big due to modulo arithmetic and because of smart exponentiation.
Try these examples and enter the fascinating world of haskell and cryptography.