13  Cryptography

Exercise 13.1 - Vigenère cipher

The Vigenère cipher consists in choosing a key formed by a secret word (in capital letters) and to transform it into a vector whose elements are the positions of these letters in the alphabet. For example, “ASECRET” corresponds to (0, 18, 4, 2, 17, 4, 19). To encode a text (in capital letters, without spaces or punctuation) with the “ASECRET” key, you just have to shift the first letter by 0, the second by 18, the third by 4, and so on, and repeat in a loop. The details, especially the historical ones, are available on Wikipedia.

a. Write a function to_int(s) that transforms a character into its place in the alphabet and write the inverse function to_chr(i).

b. Write a function crypt(text, key) that encrypts text with the secret word key.

c. Write a function to decipher a text by knowing the key.

Exercise 13.2 - Breaking the Vigenère cipher !

Charles Babbage was the first to break the Vigenère cipher. The idea is that three consecutive letters appearing several times in the cipher text are likely to be the result of encrypting the same letters of the message with the same letters of the key. This is even more likely with a group of four letters. Thus, the spacing between two same groups of cipher letters is a multiple of the key length. For example, if the repetition of one group is spaced 28 letters apart, then the repetition of another is spaced 91 letters apart, the greatest common divisor (GCD) of 28 and 91 is 7. So, it is likely that the key has 7 letters. Then knowing the size of the key, it is enough to base on the fact that the letter “E” is the most common in English. For this strategy to have a chance of success, the size of the text must be large enough.

a. Write a function to calculate the GCD between two numbers. Write another function to calculate the GCD between a list of numbers.

b. Visit the Project Gutenberg website (https://www.gutenberg.org/), choose your favorite English text and download it in “Plain Text” format. Write a function that converts the text to uppercase and strips it of all punctuation and other special characters.

import unicodedata, re
def convert_upper(text):
    # convert to upper case
    text = text.upper()
    # convert accents
    text = unicodedata.normalize('NFKD', text)
    # delete special characters
    regex = re.compile('[^a-zA-Z]')
    text = regex.sub('', text)
    return text

c. Keep about of few thousand characters in the middle of the chosen text and encrypt it with a key. Then, write a function to determine the length of the key by looking at identical strings of three or more characters in the encrypted message.

d. Write a function to decrypt an encrypted message by returning the key. Try to decrypt the text of your favorite author with this function.

Exercise 13.3 - Generating prime numbers

Most current encryption algorithms are based on the use of large prime numbers. The goal is to write a function to generate prime numbers. The first step is to generate a large random number, i.e., having a certain number of bits. Then, a primality test allows to decide if this number is prime or not. If \(\pi(n)\) denotes the number of primes less than or equal to \(n\), then asymptotically \(\pi(n) \approx \frac{n}{\ln n}\). For a number less than \(n\) drawn at random, the probability that it is prime is about \(1/\ln(n)\). For example, to generate a prime number of 1 024 bits (the minimum guaranteeing reasonable security at the moment), i.e., of the order of \(2^{1024}\), one must try \(\ln(2^{1024}) \approx 710\) random numbers before finding one that is prime. Since all even numbers are clearly not prime, it is enough to test an average of \(355\).

a. Write a program to generate an odd random number of \(k\) bits, i.e., between \(2^{k-1}\) and \(2^{k}\).

The simplest way to determine whether a number \(n\) is prime is to try to divide it by all the integers \(1 < d < n\). There are two reasons for not testing all \(d\) between 2 and \(n-1\). The first is that it is unnecessary to try even \(d\) greater than 2. The second is that there is no point in testing numbers larger than \(\sqrt{n}\).

b. Write an algorithm isprime(n) to determine if a number is prime or not.

c. Write a function generate(k,primality) to generate a random prime of k bits with the primality test. Test with the primality test isprime. Is it reasonable to expect to generate a prime number of 1 024 bits with this algorithm?

Exercise 13.4 - Generating pseudoprime numbers

The previous algorithm for generating primes being unusable for generating large primes, another approach, probabilistic, is advocated. A probabilistic primality test decides that a number is prime if it is prime with a very high probability. Such a number is called pseudoprime. Thus, a probabilistic test can be wrong and assume that a number is prime when in fact it is not.

The simplest primality test is based on Fermat’s little theorem: if \(n\) is prime, then \(a^{n-1}=1 \pmod n\) for all \(1 \leq a \leq n-1\). So, if we find an \(a\) such that \(a^{n-1}\neq1 \pmod n\), then \(n\) is not prime. Fermat’s primality test tests \(N\) values of \(a\) chosen at random and if \(a^{n-1}=1 \pmod n\) for these \(N\) values, then it declares that \(n\) is probably prime. Carmichael numbers are not prime, but satisfy \(a^{n-1}=1 \pmod n\) for all \(a\) prime with \(n\). The prime Carmichael numbers are 561, 1 105, and 1 729. If \(n\) is not a Carmichael number, then the probability that Fermat’s test is wrong is \(2^{-N}\). Choosing, for example, \(N=128\), we get a probability of being wrong of less than \(3\times 10^{-39}\).

a. Write a function implementing Fermat’s primality test. Use this test to generate random pseudoprimes.

b. ! Improve the speed of the previous algorithm by first testing whether \(n\) is divisible by primes less than 1 000 before applying Fermat’s test.

Fermat’s primality test allows to generate large pseudoprime numbers with a good probability of being right. The main problem comes from the existence of Carmichael numbers which are excluded from this probability. The Miller-Rabin primality test avoids this problem.

c. !! Understand and implement the Miller-Rabin primality test explained in detail on Wikipedia.

Exercise 13.5 - RSA encryption

The RSA algorithm, from the initials of Ronald Rivest, Adi Shamir, and Leonard Adleman who invented it in 1983, is one of the most widely used asymmetric cryptographic algorithms still in use today. Asymmetric encryption allows an encrypted message to be transmitted to Alice without having to first transmit a secret key to Bob who encrypts the message. The creation by Alice of a public key is enough for Bob to encrypt the message and for Alice to decrypt it with his private key. There are three main steps in the RSA algorithm:

Creation of the keys. Alice wanting to receive a secret message chooses two very large prime numbers \(p\) and \(q\) which she keeps secret. She then computes \(n=pq\) and the Euler’s totient function \(\varphi(n)=(p-1)(q-1)\) which counts the number of integers between 1 and \(n\) which are prime with \(n\). Then, she chooses an encryption exponent \(e\) that is prime with \(\varphi(n)\). The public key of Alice is given by the pair \((n,e)\). Finally, Alice computes the decryption exponent \(d\) which is the inverse of \(e\) modulo \(\varphi(n)\), i.e., such that \(ed = 1 \pmod{\varphi(n)}\). The private key of Alice is \((p,q,d)\).

Encryption of the message. To encrypt her message, Bob first transforms it into an integer \(M < n\). The encrypted message is then given by:

\[ C = M^e \pmod n \,. \]

Decryption of the message. The encrypted message \(C\) is then transmitted to Alice. To decrypt it, Alice calculates:

\[ M = C^d \pmod n \,, \]

which is again the original message.

a. Show mathematically that the decoded message corresponds to the original message.

b. Given \(e\) and \(\varphi(n)\), write a function bezout(e, phi) to determine \(d\) such that \(ed = 1 \pmod{\varphi(n)}\).

c. Write an algorithm generate_keys(length) that generates prime numbers \(p\) and \(q\) such that \(n\) has length bits, then determines \(\varphi(n)\), \(e\), and \(d\), and finally returns the public key \((n,e)\) and the private key \((p,q,d)\).

d.

By choosing to encode each character on 8 bits, a string of length \(\ell\) is written as a list \((a_0,a_1,\dots, a_\ell)\) with each \(0 \leq a_i \leq 255\). This list can be converted into an integer \(k\) in the following way:

\[ k = \sum_{i=0}^\ell a_i 256^i \,. \]

Write a function toint and a function tostr allowing respectively to convert a string into this integer and vice versa.

e. Write a function to encrypt a text with a public key and another to decrypt it with the private key. To do this, we must make sure that the text is convertible to an integer less than \(n\), otherwise we must split it into blocks and encrypt them separately.

Exercise 13.6 - Breaking RSA encryption !!!

Here is a public key:

(68117338482399392463470612359918949867243158421743691127857737867721430816193,
 8574804889772039379584963728913511545285333461429022558358093567068308193213)

and a message encrypted with this public key:

[58596475619506534790513764457287009750782774091650513492129616474442548981218, 63104441776088042791326380939334783287587514668094966738945085681279666911085, 28554071027878428355220078106239724269975910095918920153395621402277475101298, 59741501338113334375364443871445379652906086792175677977732561102242895663472, 58112750329964299619137149248787612030029527546642617307333293076280314987312, 35797889480880131361419044106285382024227752245483928531935179265371527989598, 40720672564903953103257522703989328334587437415699233514026965026895256621366]

a. Decrypt the previous message!