This compendium is made for the course [COM-401 Cryptography and Security](http://edu.epfl.ch/coursebook/en/cryptography-and-security-COM-401) at École Polyteqnique Fédérale de Lausanne ([EPFL](http://www.epfl.ch/)) and is a summary of the lectures and lecture notes. Is is not the complete curriculum, but rather a list of reading material. # Ancient Cryptography ## Terminology || Confidentiality || Only recieeiver shall recieeive message || || Authentication || Only sender can send the message || || Integrity || Message shall not change || ## Cryptography Prehistory ### Transposition Transposition moves the characters around, but all the characters are still in place. __Scylates__ is a cylider with a belt wrapped around. Only cylinder of same circumference can decrypt message. ### Simple substitution Substitute each letter in the alphabet by another letter. $ 26! \approx 2^{88} $ different permutations, i.e. a 88 bit key. Example of this is the __Ceasar cipher__ that is a shift in the alphabet by two positions. Simple substitution can easily be broken by statistical analysis, i.e. frequency analysis, digrams, trigrams, etc.. ### Vignère cipher Is configured by a key. Algorithm can be known. _Add more info_ Can be broken by guessing key lenght and doing statistical analysis on each column. __Kasinsky__: Frequent patterns is not random. Can guess key lenght out of this. __Index of coincidence__: Can guess key lenght and test with index of coincidence. This will reveal key length since natural languace does not have the same IoC as random text. ## Pre-Modern Industrial Cryptography ### Enigma ### Kerckhoffs principle Do not make security dependent on the secrecy of its design. Instead, use an easy to select secret key. ## Cryptography and Information Theory ### Vernam cipher: - $ (x_1, ... , x_n) \oplus (y_1, ... , y_n) = (x_1 \oplus y_1, ... , x_n \oplus y_n) $ - $ a \oplus b = (a + b)\bmod 2 $ for $a, b \in {0, 1} $ Do not encrypt two times with same key! # Elliptic Curve Cryptography ## Galois fields All finite fields have cardinality $p^k$ where $p$ is a prime number. The prime number $p$ is called the caracteristics of the field. We can therefore construct a finite field $GF(p^k)$ for any prime number $p$ and integer $k$. In cryptography we are interested in prime fields with cardinality of a large prime number $p$ as well as binary fields of cardinality $2^k$. Operations are taken modulo a fixed polynomial $P(x)$ and coeficcients are reduced by modulo 2. Characteristics of a binary field: - $-a = a$ - $(a + b)^2 = a^2 + b^2$ - $\sqrt{a} = a^{2^{k - 1}}$ - $Tr(a) = a + a^2 + ... + a^{2^{k - 1}}$ - $Tr(a^2) = Tr(a)$ ## Elliptic curves Over a field __R__ an elliptic curve with parameters $a$ and $b$ consists of a _point of infinity_ $O$ and points $(x, y)$ of the equation $y^2 = x^3 + ax + b$. Slope between two points $Q$ and $P$ is $\lambda = \frac{y_Q - y_P}{x_Q - x_P}$ ## Elliptic curves over a prime field $$ E_{a, b}(K) = \{O\} \cup \{(a, b) \in K^2; y^2 = x^3 + ax + b\} $$ Characteristics: - for $P = (x_P, y_P)$, we let $−P = (x_P,−y_P)$ and $−O = O$ - for $P = (x_P, y_P)$ and $Q = (x_Q, y_Q)$, if $Q = −P$ we let $P+Q = O$ - ...