Definition of cipher

Now that we have seen a few simple examples of ciphers, it is good to formalize what a cipher is [1].

Definition (cryptosystem)

A cryptosystem (or cipher) can be defined as a quintuple ({\cal P},{\cal C},{\cal K},E,D) where

  • \cal P is the set of plaintexts
  • \cal C is the set of ciphertexts
  • \cal K is the set of keys
  • E: {\cal K} \times {\cal P} \rightarrow {\cal C} is the encryption function
  • D: {\cal K} \times {\cal C} \rightarrow {\cal P} is the decryption function

Let x \in {\cal P}, y \in {\cal C} and k \in {\cal K} . We will write E_k(x)  and D_k(y) to denote E(k,x)  and D(k,y), i.e., the encryption and decryption under key k of x and y, respectively.

We require that

  1. D_k(E_k(x)) = x, i.e., decrypting a ciphertext with the right key gives the original plaintext;
  2. computing k or x given a ciphertext y is infeasible (so complex that cannot be done in a reasonable time).

Example (shift cipher)

The variant of Caesar cipher above can be formally defined by letting {\cal P} = {\cal C} = {\cal K} = \mathbb{Z}_{26}, meaning that we encode letters as numbers from 0 to 25, and we use arithmetic modulo 26. It is now easy to formalize encryption and decryption as

\begin{array}{rcl} E_k(x)&=&x+k \mbox{ mod } 26\\D_k(y)&=&y-k \mbox{ mod } 26\end{array}

It is trivial to see that the first property holds: D_k(E_k(x))= D_k(x+k \mbox{ mod } 26) = x+k-k \mbox{ mod } 26 = x. The second property does not hold because of the above mentioned brute force attack on the key space.

Example (substitution cipher)

We have {\cal P} = {\cal C}= \mathbb{Z}_{26} and {\cal K} = \{ \rho \ | \rho \mbox{ is a permutation of 0, \ldots, 25} \} with

\begin{array}{rcl} E_\rho(x)&=&\rho(x)\\D_\rho(y)&=&\rho^{-1}(y)\end{array}

The first property trivially holds: D_\rho(E_\rho(x))=D_\rho(\rho(x)) = \rho^{-1}(\rho(x)) = x. The second property does not hold because of the above mentioned statistical attack.

References

[1] D. R. Stinson, Cryptography, Theory and Practice, CRC Press