Page 137 - Ellingham, Mark, Mariusz Meszka, Primož Moravec, Enes Pasalic, 2014. 2014 PhD Summer School in Discrete Mathematics. Koper: University of Primorska Press. Famnit Lectures, 3.
P. 137
s Pasalic: Symmetric Key Cryptography and its Relation to Graph Theory 125
4.1 Introduction
A modern cryptology relies on many disciplines such as information theory, computer
science, probability theory, number theory and abstract algebra. An information theo-
retical foundation of modern cryptology was established in the late forties. In his cel-
ebrated paper [9] from 1948 Claude E. Shannon laid the theoretical foundations of in-
formation theory. One of the greatest contribution of his work was a new concept of
measuring the information. In his second work [10], among other important notion,
Shannon introduced the concept of unconditional security of symmetric ciphers. Un-
conditional security means that even if an adversary is assumed to have unlimited com-
putational resources he still cannot defeat the cryptosystem. A necessary condition for
a symmetric-key encryption scheme to be unconditionally secure is that the encryption
key is at least as long as the message, which obviously restricts the practical use of such a
system. Also, Shannon introduced two extremely important concepts which have been
extensively used in design of modern ciphers, namely confusion and diffusion.
A standard cryptosystem model used for achieving confidentiality (secrecy), also call-
ed symmetric-key cryptosystem transforms the plaintext message m into the ciphertext
message c so that c = EK (m ), where EK denotes the encryption function, see Figure 4.1.
Eve estimate
Attack m*
plaintext Alice Bob
m ciphertext
Decryption
Encryption m=DK (c)
c=E K(m)
key K
Model of a classic cryptosystem
Figure 4.1: Symmetric-key cryptosystem
The ciphertext message received by Bob is now supposed to be decrypted before
reading. Equipped with the same key as Alice, Bob performs the following. He applies
the decryption algorithm DK on the encrypted message, i.e., m = DK (EK (m )) and re-
trieves the original message. The cryptanalyst Eve, not knowing the actual key K , may
perform various attacks on the cryptosystem. The most trivial one, is called exhaustive
search which checks for all possible keys in the key space to decrypt the message.
As an example of an insecure symmetric-key cryptosystem we consider the Vigenère
cipher. It is assumed that both the message and key symbols are letters from the English
4.1 Introduction
A modern cryptology relies on many disciplines such as information theory, computer
science, probability theory, number theory and abstract algebra. An information theo-
retical foundation of modern cryptology was established in the late forties. In his cel-
ebrated paper [9] from 1948 Claude E. Shannon laid the theoretical foundations of in-
formation theory. One of the greatest contribution of his work was a new concept of
measuring the information. In his second work [10], among other important notion,
Shannon introduced the concept of unconditional security of symmetric ciphers. Un-
conditional security means that even if an adversary is assumed to have unlimited com-
putational resources he still cannot defeat the cryptosystem. A necessary condition for
a symmetric-key encryption scheme to be unconditionally secure is that the encryption
key is at least as long as the message, which obviously restricts the practical use of such a
system. Also, Shannon introduced two extremely important concepts which have been
extensively used in design of modern ciphers, namely confusion and diffusion.
A standard cryptosystem model used for achieving confidentiality (secrecy), also call-
ed symmetric-key cryptosystem transforms the plaintext message m into the ciphertext
message c so that c = EK (m ), where EK denotes the encryption function, see Figure 4.1.
Eve estimate
Attack m*
plaintext Alice Bob
m ciphertext
Decryption
Encryption m=DK (c)
c=E K(m)
key K
Model of a classic cryptosystem
Figure 4.1: Symmetric-key cryptosystem
The ciphertext message received by Bob is now supposed to be decrypted before
reading. Equipped with the same key as Alice, Bob performs the following. He applies
the decryption algorithm DK on the encrypted message, i.e., m = DK (EK (m )) and re-
trieves the original message. The cryptanalyst Eve, not knowing the actual key K , may
perform various attacks on the cryptosystem. The most trivial one, is called exhaustive
search which checks for all possible keys in the key space to decrypt the message.
As an example of an insecure symmetric-key cryptosystem we consider the Vigenère
cipher. It is assumed that both the message and key symbols are letters from the English
