Gabriele Biondo

Basic definitions

In a previous post (the problem of hiding stuff), we already introduced the meaning of cryptography. Still we miss to give the meaning of cryptology or cryptoanalysis. As usual, we leverage wikipedia:

Cryptanalysis (from the Greek kryptós, “hidden”, and analýein, “to loosen” or “to untie”) is the study of analyzing information systems in order to study the hidden aspects of the systems. Cryptanalysis is used to breach cryptographic security systems and gain access to the contents of encrypted messages, even if the cryptographic key is unknown.

In addition to mathematical analysis of cryptographic algorithms, cryptanalysis includes the study of side-channel attacks that do not target weaknesses in the cryptographic algorithms themselves, but instead exploit weaknesses in their implementation.

In this set of posts, we will use the usual concepts:

Alice and Bob are two entities who want to exchange information securely. Sometimes we’ll refer to Eve (as Eavesdropper, but also Evil) who wants to intercept/decypher/tamper the aforementioned information.

In the simplest situation, if Bob wants to send a secret message to Alice, he will take his plain text message (we’ll usually refer to it as \(m \)) and scramble it with a secret key (we’ll indicate it with \(k \), usually) and obtain a cyphertext (denoted with \(c\)). When Alice receives \(c\), she uses \(k\) in order to convert \(c\) into \(m\) back.

Seen from this perspective, Cryptography is used by Alice and Bob, whereas Cryptology/Cryptanalysis is used by Eve.

When we spoke about Password and Bruteforcing, we introduced the concept of Solution Tree. This is just a simplistic way of talking about the space of all possible keys \(\mathcal{K} \); this can be used to encrypt a message \(m\in\mathcal{M}\), where \(\mathcal{M}\) is the space of all possible messages. Finally, encryption gives a cyphertext \(c\in\mathcal{C}\), being \(\mathcal{C}\) the space of all possible cyphertexts. We can then define the process of encryption as a function:

\(\epsilon:\mathcal{K}\times\mathcal{M}\rightarrow\mathcal{C}\)

and the decryption function:

\(d:\mathcal{K}\times\mathcal{C}\rightarrow\mathcal{M}\)

With the property:

\(d\left(k,\epsilon\left(k,m\right)\right)=m\)

\(\forall k\in\mathcal{K}\) and \(m\in\mathcal{M}\). We will also write these functions as \(\epsilon_k:=\epsilon\left(k,m\right)\) and \(d_k:=d\left(k,m\right)\), being obviously \(\epsilon_k:\mathcal{M}\rightarrow\mathcal{C}\) and \(d_k:\mathcal{C}\rightarrow\mathcal{M}\).

It is intended that the encryption function must be an injective function; otherwise decryption wouldn’t give back the original message. In fact, if \(m_1, m_2\in \mathcal{M}\) and given if \(k\in \mathcal{K}\), if \(e_k\left(m_1\right)=e_k\left(m_2\right)\) then \(m_1=d_k\left(e_k\left(m_1\right)\right)=d_k\left(e_k\left(m_2\right)\right)=m_2\).

We did not yet define the concept of cryptography. Before doing so, we give the most important axiom of the discipline:

Kerckhoff’s principle (or axiom, or law)

The reader is suggested to read the Wikipedia lemma, which is reported partially below:

Kerckhoffs’s principle (also called Kerckhoffs’s desideratum, assumption, axiom, doctrine or law) was stated by Netherlands born cryptographer Auguste Kerckhoffs in the 19th century: A cryptosystem should be secure even if everything about the system, except the key, is public knowledge.

Shortly, the security of a cryptosystem should depend only on the secrecy of the key, and not on the secrecy of the encryption algorithm itself.

The lemma continues stating six principles reported on two journal articles on La Cryptographie Militaire:

  1. The system must be practically, if not mathematically, indecipherable;
  2. It should not require secrecy, and it should not be a problem if it falls into enemy hands;
  3. It must be possible to communicate and remember the key without using written notes, and correspondents must be able to change or modify it at will;
  4. It must be applicable to telegraph communications;
  5. It must be portable, and should not require several persons to handle or operate;
  6. Lastly, given the circumstances in which it is to be used, the system must be easy to use and should not be stressful to use or require its users to know and comply with a long list of rules.

Translating these principles into math language, we have some interesting properties a cryptosystem must have.

Cryptosystem’s requirements

In order for \(\left(\mathcal{K},\mathcal{M}, \mathcal{C}, e, d\right)\) to be a successful cipher, it must have the following properties:

  1. \(\forall k\in\mathcal{K}\) and \(\forall m\in\mathcal{M}\), \(e_k\left(m\right)\) must be easy to compute
  2. \(\forall k\in\mathcal{K}\) and \(\forall c\in\mathcal{c}\), \(d_k\left(c\right)\) must be easy to compute
  3. Given one or more \(c_1,c_2,\dots,c_n\in\mathcal{c}\) encrypted using an unknown \(k\in\mathcal{K}\), it must be highly complex deriving any plaintext \(d\left(c_1\right),d\left(c_2\right),\dots,d\left(c_n\right)\)
  4. Chosen plaintext attack: given \(n\) couples of plaintext messages and their cryptograms \(\left(m_1,c_1\right),\left(m_2,c_2\right),\dots,\left(m_n,c_n\right)\) it must be difficult to decrypt any ciphertext \(c\) that is not in the given list without knowing \(k\).

Leave a Reply

Your email address will not be published. Required fields are marked *