This is not a book about cryptography, it is rather a book that helps the reader face a course focused on cryptography, so we will not explain the general theory of cryptography. However, after having seen some mathematical background in the previous sections, it is possible to define rigorously a few cryptographic systems in an easy way. We believe these systems can motivate you to start a deeper subject of cryptography on your own.
In this section we will see:
the Diffie-Helman key-exchange
the Rivest-Shamir-Adleman encryption/decryption system
the classical El Gamal encryption/decryption system
a classical stream cipher
The cryptographic problem solved by the Diffie-Helman key-exchange (DH) has been a long-standing problem in all cryptographic operations since the dawn of time.
Whenever two peers agreed on a system to encrypt their messages, sooner or later they needed to find a way to change it,
in order to prevent the enemy from understanding it. The most efficient way to do so is to design a cryptosystem whose exact working depends on a short string, called a cryptographic key. Since the key is short (only 16 bytes even in modern times), it can be communicated easily.
We will see an example of such a system in Section \ref{stream}.
Unfortunately, if there are thousands of users of the systems (as for example the units of an army moving into enemy territories) and the communication channel can be heard by the enemy (radio communication being the main example in history), it becomes very complex to send millions of keys in a secure way.
The DH system allows two peers (Alice and Bob) to agree on a key (or any other short secret), even when communicating over an insecure channel that can be heard by the enemy. Alice and Bob agree on a prime \(p\) and a primitive element \(g\) of \(\mathbb{Z}_{p}\).
This is public information, so for example \(p\) and \(g\) could be told on the air by the General to all units in his command and it does not matter if the
enemy hears these.
The system works as follows:
Alice chooses secretly a positive integer \(a\) less than \(p\) and she does not share it with anyone,
Bob chooses secretly a positive integer \(b\) less than \(p\) and he does not share it with anyone,
Alice computes the exponentiation \(g^{a}\) in \(\mathbb{Z}_{p}\) and she sends the result to Bob (the enemy may intercept it)
Bob computes the exponentiation \(g^{b}\) in \(\mathbb{Z}_{p}\) and he sends the result to Alice (the enemy may intercept it)
Alice has received \(g^{b}\) and so she can compute another exponentiation \((g^{b})^{a}\) in \(\mathbb{Z}_{p}\), the results being \(g^{(ab)}\), that she keeps secret and does not share with anyone,
Bob has received \(g^{a}\) and so he can compute another exponentiation \((g^{a})^{b}\) in \(\mathbb{Z}_{p}\), the results being \(g^{(ab)}\), that he keeps secret and does not share with anyone,
now Alice and Bob have the same value, \(g^{ab}\), and they start using it as a key.
Thanks to the research in finite fields developed in the last \(30\) years, we observe that, even if the enemies simultaneously collect \(p\), \(g\), \(g^{a}\) and \(g^{b}\), then they have a negligible probability to reconstruct \(g^{ab}\) and so the key remains hidden from them.
The system we have described is still used today a lot, especially on the Internet. We complete this subsection with some observations on the DH protocol as it used nowadays:
the prime number \(p\) is huge, at least \(p>2^{2048}\),
the prime number \(p\) has to be chosen with some specific algebraic properties, for example the factorization of \(p-1\) in prime numbers should contain one huge prime,
there are some primes that have been standardized and are used by many applications, as for instance those proposed by the National Institute of Standards in the U.S.
The key-exchange is only one of the numerous problems that cryptographers face in modern times.
Another interesting problem is the so-called public-key encryption, as follows:
Alice wants to send Bob a secret, but now they are far apart and they can communicate only in an insecure way (e.g., by standard email);
unfortunately, they did not agree beforehand on a system that uses cryptographic keys and so the DH protocol is useless.
A solution to this problem is the RSA algorithm, summarized below:
Bob chooses secretly two distinct prime numbers, \(p\) and \(q\), and perform their multiplication \(N=pq\);
Bob chooses secretly a positive integer \(d\) smaller than \(N\) and coprime with \(\phi(N)=(p-1)(q-1)\);
Bob computes the inverse \(e\) of \(d\) modulo \(\phi(N)\);
Bob sends to Alice both \(N\) and \(e\) (the enemies may intercept them);
Alice has received \(N\) and \(e\); she has a message \(m\) to send to Bob and so she compute the exponentiation \(m^{e}\) in \(\mathbb{Z}_{N}\), the results being the ciphertext \(c\);
Alice sends \(c\) to Bob (the enemies may intercept it);
Bob has received \(c\) and so he can compute another exponentiation \(c^{d}\) in \(\mathbb{Z}_{p}\), the results being \(m\) thanks to Theorem ??.
Thanks to the research in number theory developed so far, even if the enemies simultaneously collect \(N\), \(e\) and \(c\), then they have a negligible probability to reconstruct \(m\) and so the message remains hidden from them.
The system we have described is still used today, especially for electronic payments. We complete this subsection with some observations on the RSA protocol as it used nowadays:
the prime numbers \(p\) and \(q\) are huge, at least \(p,q>2^{1024}\),
the prime numbers \(p,q\) has to be chosen with care, for example their difference \(|p-q|\) must exceed both their square roots,
the private exponent \(d\) must be large, at least \({}^{4}\sqrt{N}\),
the public exponent \(e\) should be at least \(e\geq 65537\).
We now describe another cryptographic algorithm that provides public-key encryption:
Bob chooses a prime \(p\) and a primitive element \(g\) of \(\mathbb{Z}_{p}\).
Bob chooses secretly a positive integer \(x\) smaller than \(p-1\).
Bob computes the exponentiation: \(h=g^{x}\) in \(\mathbb{Z}_{p}\).
Bob sends \(p\), \(g\) and \(h\) to Alice (the enemies may intercept them);
Alice has received \(p\),\(g\) and \(h\); she has a message \(m\) to send to Bob; she chooses secretely a positive integer \(y\) smaller than \(p-1\);
Alice computes two preliminary exponentiations in \(\mathbb{Z}_{p}\) : \(c_{1}\,=\,g^{y}\) and \(s\,=\,h^{y}\) (obviously \(h=g^{xy}\)).
Alice encrypts her message \(m\) by computing \(c_{2}\,=\,ms\); finally, she sends \(c_{1}\) and \(c_{2}\) to Bob (the enemies may intercept them);
Bob computes \(s\) by an exponentiation in \(\mathbb{Z}_{p}\), since \(s\,=\,{c_{1}}^{x}\);
Finally, Bob computes the message \(m\) by another exponentiation in \(\mathbb{Z}_{p}\), i.e. \(m\,=\,c_{2}\cdot s^{{-1}}\)
Thanks to the research in algebra developed so far, we observe that, even if the enemies simultaneously collect \(p\), \(g\), \(h=g^{x}\) and \(c_{1}=g^{y}\), \(s\,=\,h^{y}\) and \(c_{2}\,=\,ms\), then they have a negligible probability to reconstruct \(m\) or \(x\) and so the message remains hidden from them.
The system we have described is still used. We complete this subsection with some observations on the El-Gamal protocol as it used nowadays:
the prime number \(p\) is huge, at least \(p>2^{2048}\),
the prime number \(p\) has to be chosen with some specific algebraic properties, for example the factorization of \(p-1\) in prime numbers should contain one huge prime,
there are some primes that have been standardized and are used by many applications, as for instance those proposed by the IETF.
A stream cipher is a cryptographic algorithm that allows two peers to encrypt and decrypt messages, once a secret key has been securely shared (as for example with DH).
In this section we describe the easiest possible stream ciphers, which were used only briefly at about the same time of World War II. We call this design a ”classical stream cipher”.
To build a classical stream cipher we need some LFSR’s (see Section \ref{Sec:Vectors}), say \(n\), and a Boolean function with \(n\) inputs (and one output).
We illustrate the working with an example, which the reader will be able to generalize.
We consider three LFSR’s, with polynomials: \(x^{3}+x+1\), \(x^{4}+x^{3}+x^{2}+x+1\) and \(x^{2}+x+1\).
We consider the Bf \(x_{1}*x_{2}+x_{1}+x_{2}\), and we call it the combining function.
The secret key is the initial state (initial vector), which in this case must have \(3+4+2\) bits.
We are ready to describe encryption and decryption:
Alice wants to encrypt seven bits \(m=(0100110)\). Alice generates one bit from each of the three LFSR’s and uses the bits as input to the Bf; in other words, if \(b_{1}\),\(b_{2}\) and \(b_{3}\) are the bits generated respectively by the LFSR’s, then Alice computes \(z_{0}=b_{1}*b_{2}+b_{1}+b_{2}\). The bit \(z_{1}\) is the first bit of the so-called keystream;
Alice adds \(z_{0}\) to the first bit of \(m\), which is \(m_{0}=0\), and sends \(c_{0}=z_{0}+m_{0}\);
observe the LFSR’s have changed their state and so they may now generate another bit;
similarly, Alice computes \(z_{1},\ldots,z_{6}\), and performs the XOR \(c_{1}=z_{1}+m_{1},\ldots,c_{6}=z_{6}+m_{6}\); she will send \(c_{1},\ldots,c_{6}\);
Bob receives \(c_{0},\ldots,c_{6}\);
his LFSR’s are the same of those of Alice and have the same initial state; also the combining function is the same; so, Bob can compute the same bits of the keystream that Alice computed, that is, \(z_{0},\ldots,z_{6}\);
Bob computes the XOR’s \(c_{0}+z_{0},\ldots,c_{6}+z_{6}\), obtaining \(m_{0},\ldots,m_{6}\), since \(c_{i}+z_{i}=(z_{i}+m_{i})+z_{i}=(z_{i}+z_{i})+m_{i}=0+m_{i}=m_{i}\).
Stream ciphers used nowadays have a structure which is much more complex, however they still use normally
LFSR’s. The initial state goes from \(64\) bits to \(256\) bits being \(128\) the minimum length giving acceptable security.
As examples of strea ciphers in use:
E0, which is used in Blootooth;
RC4, which is used on the Internet;
A5/3, which is used in all mobile communications (GSM).