How asymmetric key cipher works
This example closely follows the discussion in section 5.5.2 of the book "Discrete analysis" by Romanovsky, I.V. (Spb: Nevsky Dialect; BHV Peterburg (2003), in Russian, ISBN: 5-7940-0114-3). The purpose of this exercise is to demonstrate the mathematical foundations of encryption algorithms that use pairs of asymmetric keys. One key of the pair, the private key, is used by the sender to encrypt a message. The other matching key, the public key, is used by the receiver to restore the plain text. In real world applications the sizes of the keys are chosen so that computational cost of figuring out the private key from the knowledge of the corresponding private key becomes prohibitive.
In order to create a cipher we need to take a large number $n$ such that
$$n = p\cdot q$$
where $p$ and $q$ are primes. The bigger n we choose the stronger the encryption. For encryption we will need to derive integer $e$ and for decryption we will need a corresponding integer $d$. Although $d$ is uniquely determined for any given $e$, in order to calculate it one needs to factorize $n$ into the product of $p$ and $q$. If $n$ is large enough this task becomes very difficult. The numbers that we use for illustration purposes are going to be tiny compared to those used in real key pairs.
Thus let $n=p\cdot q$ and let $$\phi = p\cdot q - p - q + 1$$
In [5]:
import Data.List (sort)
import Data.Char (chr, ord)
In [6]:
p = 997
q = 1097
n = p * q
n
In [7]:
f a b = a * b - a - b + 1
ϕ = f p q
ϕ
Lemma 1 Let $a$ and $n$ be mutually prime. Then $$a^{\phi} = 1 \operatorname{mod} n$$
Proof. Let $\Phi(n)$ be the set of all integers, not greater than $n$ and mutually prime with $n$:
$$\Phi(n)=\left\{k \in \mathbb{N}\left| \; k \in (1:n),\, (k,n) = 1 \right. \right\}$$
In [8]:
qphi x = [k | k <- [1..x], gcd k x == 1]
Note that $\left|\Phi(n)\right|=\phi$
In [9]:
length (qphi n) == ϕ
Now multiplication of members of $\Phi(n)$ by $a$ maps $\Phi(n)$ to itself bijectively. To see this take $b,c\in\Phi(n)$ and notice that if $b\cdot a = c\cdot a$ then $a$ must be divisible by $n$. Thus
$$\prod_{b\in\Phi(n)} b \operatorname{mod} n = \prod_{b\in\Phi(n)} (b\cdot a)\operatorname{mod} n = a^{\phi}\prod_{b\in\Phi(n)} b \operatorname{mod} n$$from which the result follows. $\square$
Consider a numerical example for some small $n$, say $35$
In [10]:
s = qphi 35
s
Let us verify that the statement of the lemma holds for the example where $n=35$. Take $a=11 \in \Phi(n)$. First we see that multiplication by $a \operatorname{mod} n$ is a bijection
In [11]:
s' = map (\x -> x * 11 `mod` 35) s
s'
s == sort s'
Now we check that the statement lemma holds for this example
In [12]:
ψ = f 5 7
all (==1) [x ^ ψ `mod` 35 | x <- qphi 35]
Lemma 2. For each $e$ relatively prime with $\phi$ there exists a unique $d\in (1:\phi)$ such that $e\cdot d = 1 \operatorname{mod} \phi$
Proof. Using the Euclidean algorithm to find the highest common factor of $e$ and $\phi$, which in this case equals $1$, it is possible to compute integer coefficients $d$ and $k$ such that
$$d \cdot e + k \cdot \phi = 1$$This equation is also known as the Bézout's identity and is true for any mutually prime $e$ and $\phi$.
If there exists another number $d'$ satisfying the conditions of the lemma then $d - d'$ must be divisible by $\phi$ which together with the requirement that $d\in (1:\phi)$ implies $d=d'$. $\square$
For the actual calculation of $d$ based on a given $e$ we will use an implementation of the Extended Euclidean algorithm that simultaneously returns the highest common factor and the Bézout's coefficitents
In [13]:
euclidean :: Integer -> Integer -> (Integer, Integer)
euclidean a b
| b == 0 = (1, 0)
| otherwise = (t, s - q * t)
where (q, r) = quotRem a b
(s, t) = euclidean b r
It is clear that in order to derive $e$ knowing $d$ we would have to know the value of $\phi$ and that requires factorizing $n$. Now we choose our encryption key:
In [14]:
e = 397
Then we derive $d$ using the Extended Euclidean procedure:
In [15]:
(d, k) = euclidean e ϕ
(d, k)
Let us check that the results satisfy the Bézout's identity:
In [16]:
d * e + k * ϕ == 1
In order to apply encryption we must represent the data as a sequence of integers. For convenience we define some utility functions to convert strings to and from lists of integers
In [17]:
stringToNum = map (toInteger . ord)
numToString = map (chr . fromInteger)
Now we define the function used to encrypt and decrypt the data:
In [18]:
cipher key bigNumber = map (\x -> x ^ key `mod` bigNumber)
Define encryption and decryption functions using our keys and the chosen big number:
In [19]:
encrypt = (cipher e n) . stringToNum
decrypt = numToString . (cipher d n)
Pick a sample message that emphasizes the perils of symmetric key encryption:
In [20]:
plainTextMessage = concat ["To every man is given a key ",
"that opens the gates of heaven. ",
"The same key opens the gates of hell."]
Now let us encrypt the data and take a look at the result:
In [21]:
encryptedMessage = encrypt plainTextMessage
encryptedMessage
Finally we decrypt the original message:
In [23]:
decrypt encryptedMessage
In [ ]: