Cryptography

This post is a collection of basic topics needed for a proper understanding of Cryptography.

Contents hide

1 Cryptographic Systems

1.1 Symmetric Cryptosystem

1.2 Asymmetric Cryptosystem

2 The Discrete Logarithm Problem (DLP)

3 Diffie-Hellman Key Exchange

3.1 Proof of correctness

Cryptographic Systems

Primal goal: allow two people to exchange confidential information even if they can only communicate via a channel monitored by an adversary

Symmetric Cryptosystem

A 5-tuple

$(\mathcal{K}, \mathcal{M}, \mathcal{C}, e, d)$

Where

$\mathcal{K}, \mathcal{M}, \mathcal{C}$ are sets of possible keys, messages, ciphers
$e: \mathcal{K} \times \mathcal{M} \leftarrow \mathcal{C}$ : encryption function
$d: \mathcal{K} \times \mathcal{C} \leftarrow \mathcal{M}$ : decryption function
Satisfy
$\forall k \in \mathcal{K}$ , $d(k,e(k,m)) = m$

Formal requirements.

knowing $k \in \mathcal{K}$ and $m \in \mathcal{M}$ , $e_{k}(m) \in \mathcal{C}$ must be easy to compute
knowing $k \in \mathcal{K}$ and $c \in \mathcal{C}$ , $d_{k}(c) \in \mathcal{M}$ must be easy to compute
given one(or more) cypher $c_{i} \in \mathcal{C}$ encoded with key $k \in \mathcal{K}$ , it must be hard to compute the plaintext(s) $d_k(c_i)$

Asymmetric Cryptosystem

A 7-tuple

$(\mathcal{K}, \mathcal{K}_{pub}, \mathcal{K}_{priv}, \mathcal{M}, \mathcal{C}, e, d)$

Where

are sets satisfying
- $\mathcal{K} \subseteq \mathcal{K}_{pub} \times \mathcal{K}_{priv}$
and are satisfying
- $\forall (k_{pub}, k_{priv}) \in \mathcal{K}$ , $d(k_{priv}, e(k_{pub}, m))=m$

The Discrete Logarithm Problem (DLP)

Let $(G,\cdot)$ be a cyclic group with order $n = |G|$ , where $g \in G$ is one of its generators: $G=\langle g \rangle$ . The GDLP (Generalized Discrete Logarithm Problem) for the group $G$ is stated as follows:
Given $a \in \langle g \rangle$ , find the smallest positive integer $x \in \mathbb{Z}_n$ such that $g^x = a$

DLP: given a finite abelian group $G$ , and an element $g$ generating it, for any $a \in G$ , compute the smallest positive $k \in \mathbb{N}$ such that

$\underbrace{g \cdot \: \ldots \: \cdot g}_{k \; times} = a$

This $k$ is called the discrete logarithm of $a$ (with base $g$ ) or $log_g \: a$ .
The basic principle

if we can compute the group operation fast, then from $k$ is easy to get $a$
while, from $a$ , it is not obvious to get $k$

This asymmetry gives us the possibility to build public key cryptosystem.
Indeed, using a finite abelian group, we can build up certain cripto systems whose security rely on the difficulty of the DLP, which depends very much on the group.

Example 1: $G$ is the additive group $F^+_p$ of the prime field $F_p$ , aka $\langle F, + \rangle$ . For this case, the DLP is: given $g$ and $a$ compute the smallest possible $k$ such that:

$a \equiv \underbrace{g + \: \ldots \: + g}_{k \; times} \equiv gk \: mod \: p$

In this case the DLP is simple as $k=a \cdot g^{-1} \: mod \: p$ , and we can calculate the multiplicative inverse of $g$ in polynomial time.

Example 2: $G$ is the multiplicative group $F^{\times}_p$ of the prime field $F_p$ , aka $\langle F, \cdot \rangle$
In this case, the DLP is: given $g$ and $a$ , compute the smallest possible $k$ such that:

$g^k \equiv a \: mod \: p$

Consider the problem of sending an encrypted message through an insecure channel.

How can two parties A and B can agree on a session key to be used to encrypt and decrypt a message?

Diffie-Hellman Key Exchange

Alice and Bob want to exchange a message. They both know the parameters $\alpha$ , $p$ . They both generate private secret keys $a = K_{prA} \in[2..p-1]$ and $b = K_{prB}\in [2..p-1]$ , then compute their public keys as follows: