2 Fundamentals

A cryptosystem consists of five components:

1.	Set of plaintexts M
2.	Set of ciphertexts C
3.	Set of keys K
4.	Family of encrypting transformations Ek: M -> C with k from K
5.	Family of decrypting transformations Dk: C -> M with k from K

M, C, and K are at most countable. Every encrypting transformation E_k is defined by a key k and a decrypting algorithm E, which is the same for every transformation from the family. The corresponding holds true for every decrypting transformation D_k.
For a given k and for all m from M : D_k(E_k(m)) = m.

Cryptosystems must satisfy three requirements:

(1)	Encrypting and decrypting transformations must be efficient for all keys.
(2)	The systems must be easy to use. It must be easy to find a key and the functions Ek and Dk.
(3)	The security if the systems should rely on the secrecy of the keys, not of the algorithms; from knowledge of the method of en- or decrypting alone it should not be possible to determine the plaintext.

As to secrecy and authenticity there are special postulations. Secrecy requires that a cryptanalyst be not able to determine the plaintext from a received ciphertext. Authentciity requires that the cryptanalyst cannot insert a wrong ciphertext c' for another ciphertext c. This leads to two

Secrecy requirements:
It should be computationally infeasible for a cryptanalyst:

(1)	to systematically determine Dk from a caught ciphertext c, even if the plaintext m is known, and
(2)	to determine the plaintext m from c.

For secrecy only D_k has to be protected, as long as E_k does not reveal D_k. This means that E_k may be made public. Thus we have the

Authenticity requirements:
It should be computationally infeasible for a cryptanalyst:

(1)	to systematically determine Ek from c, even if the plaintext m with Ek(m) = c is known, or
(2)	to find a ciphertext c' such that Dk(c') is a valid plintext from M. This is imaginable with numeric data.

(1) assures that the cryptanalyst cannot insert a wrong plaintext m' through E_k(m') = c. For the authenticity only E_k must be protected, if D_k does not reveal E_k. So D_k can be made public.

For many algorithms (especially RSA) large primes and fast modulo operations are needed. Suitable algorithms will be introduced in the next chapters.

2.1 Euclidean Algorithm