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 where
is the set of plaintexts
is the set of ciphertexts
is the set of keys
is the encryption function
is the decryption function
Let and
. We will write
and
to denote
and
, i.e., the encryption and decryption under key
of
and
, respectively.
We require that
, i.e., decrypting a ciphertext with the right key gives the original plaintext;
- computing
or
given a ciphertext
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 , 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
It is trivial to see that the first property holds: . The second property does not hold because of the above mentioned brute force attack on the key space.
Example (substitution cipher)
We have and
with
The first property trivially holds: . The second property does not hold because of the above mentioned statistical attack.
References
[1] D. R. Stinson, Cryptography, Theory and Practice, CRC Press