Definition of cipher – Secgroup Ca' Foscari

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

$D_k(E_k(x)) = x$ , i.e., decrypting a ciphertext with the right key gives the original plaintext;
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