# 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

This site uses Akismet to reduce spam. Learn how your comment data is processed.