Skip to main content

Section 3.1 A naïve cryptosystem and some related questions

Let us suppose that, armed as we are with our knowledge of modular arithmetic and the algebra of finite fields, we are going to attempted to send information using that mathematics. Our friends Alice and Bob, intending to avoid the scrutiny of the devious Eve, are going to use this system to send information to teach other. To simplify matters, we will assume that the system that we are designing is symmetric -- that is, that Alice and Bob share a secret piece of information.

  1. Alice and Bob choose a large prime \(p\) (say on the order of \(2^{512}\)) and an integer \(k \in \mathbb F_p\ad\text{,}\) the private key \(k_{priv}\text{,}\) that they both know.
  2. As an encryption function, Alice uses multiplication by \(k \bmod p\text{.}\) She knows that multiplication is one-to-one, since \(\F_p\ad\) is a field, so each message \(m \in \F_p\ad\) will be sent to a unique \(c \in \F_p\ad\) by the function
    \begin{equation*} e_k(m) = k\cdot m \bmod p. \end{equation*}
  3. Alice and Bob feel confident that Eve will not have an easy time figuring out what \(k\) and \(m\) are given \(c\text{.}\) In fact, they are correct: for each value of \(k\text{,}\) there will be an \(m\) so that \(km =c\text{.}\) This means that Eve will have to check every single pair \((k,m)\) to uncover the message.
  4. On receiving \(c\) from Alice, Bob first calculates \(k\inv \bmod p\) using the euclidean algorithm or fast inverse. He then applies the function
    \begin{equation*} d_k(c) = k\inv \cdot c = k\inv \cdot (k \cdot m) = m \bmod p. \end{equation*}

This scheme, as simple as it looks, has some powerful properties.

  1. Calculating \(e_k(m)\) is easy, even for enormous primes.
  2. Calculating \(d_k(c)\) is “easy” using one of the inverse methods we've discussed in \(\F_p\ad\text{.}\)
  3. The central mathematical problem is indeed quite hard - to discover which particular pair \((k,m)\) have been used to compute \(c\text{,}\) given that any number in \(\F_p\ad\) could be produced by some \(m\) and an appropriate \(k\text{.}\)

However, as a cryptographic scheme, this method has some flaws. If Eve can get her hands on a single plaintext pair \((m,c)\) so that \(c\) is the encryption of \(m\text{,}\) then she can use the same computational methods to calculate \(k\text{.}\) This is called a plaintext attack and our scheme is sadly vulnerable to it. A single pair is enough to break the entire system. Of course, if Alice and Bob could choose a new key each time, then the problem would be surmounted, but that goes to the question of HOW they can exchange a symmetric key each time they need a new one. (An answer to this question is the famous Diffie-Hellman key exchange to be discussed in the next section.)

Our example does sketch the main properties we want from a secure cryptographic scheme. First, we make the assumption that attacker Eve knows everything about the system except \(k\text{.}\) We design cryptographic methods on the principle that security should depend only on the secrecy of the key, not the algorithm.

Let \(\mathcal K\) be the keyspace, \(\mathcal M\) be the space of possible messages, \(\mathcal C\) be the space of ciphertexts, \(e\) be the encryption function, and \(d\) be the decryption function. What properties will make \((\mathcal K, \mathcal M, \mathcal C, e, d)\) secure?

A secure cryptosystem should have the following properties:

  1. For any \(k, m\text{,}\) the function \(e_k(m)\) should be easy to compute.
  2. For any \(k, c\text{,}\) the function \(d_k(c)\) should be easy to compute.
  3. Given any number of ciphertexts \(c_1, \ldots, c_n \in \mathcal C\text{,}\) the ciphertexts \(d_k(c_1), \ldots, d_k(c_n)\) must be difficult to compute without knowledge of the key \(k\text{.}\)
  4. (Good but harder to achieve) Given a set known pairs \((m_1, c_1), \ldots, (m_n, c_n)\text{,}\) it must be difficult to decrypt new ciphers without knowing \(k\text{.}\) This is called resistance to plaintext attacks.
  5. (Better but even more difficult) For any list of known pairs \((m_1, c_1), \ldots, (m_n,c_n)\text{,}\) it must be difficult to decrypt new ciphertexts without knowing \(k\text{.}\) (The point here is that Eve can choose the pairs). This is called resistance to chosen plaintext attack.

We should pause for a moment to talk about what we mean by easy and hard in the context of computational difficulty. We consider a calculation easy if it can be performed in seconds or less by a desktop computer. We consider a computation hard if the expected computation time is ten years or more harnessing all available computer power in world. There are two key points to make about this. One, we use the word expected - that is, there is a notion of probability involved. We could, in theory, solve a brute force check of a list with \(2^{1000}\) entries on the first try, but the probability is astronomically low.

The second thing to notice is that the definition of hard changes constantly with the development of new computational technology and techniques. Moore's Law is the observation that the number of transistors on dense integrated circuits (CPUs) has doubled every two years for decades. To keep computational problems hard, the size of keyspaces needs to increase accordingly. On the other hand, the invention of new technology can also change what is hard. It has been shown, for example, that working quantum computers will reduce some of the most important difficult math problems at the heart of modern cryptography into trivialities. This underscores the need to continue to develop new techniques in addition to enlarging the computational spaces.