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

## 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

Where

- are sets of possible keys, messages, ciphers
- : encryption function
- : decryption function

Satisfy - ,

Formal requirements.

- knowing and , must be easy to compute
- knowing and , must be easy to compute
- given one(or more) cypher encoded with key , it must be hard to compute the plaintext(s)

### Asymmetric Cryptosystem

A 7-tuple

Where

- are sets satisfying
- and are satisfying
- ,

## The Discrete Logarithm Problem (DLP)

Let be a cyclic group with order , where is one of its generators: . The GDLP (Generalized Discrete Logarithm Problem) for the group is stated as follows:

Given , find the smallest positive integer such that

DLP: given a finite abelian group , and an element generating it, for any , compute the smallest positive such that

This is called the discrete logarithm of (with base ) or .

The basic principle

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

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**: is the additive group of the prime field , aka .
For this case, the DLP is: given and compute the smallest possible such that:

In this case the DLP is simple as , and we can calculate the multiplicative inverse of in polynomial time.

**Example 2**: is the multiplicative group of the prime field , aka

In this case, the DLP is: given and , compute the smallest possible such that:

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* , . They both generate *private secret keys* and , then compute their *public keys* as follows:

- Alice:
- Bob:

At this point Alice and Bob exchange the public keys, and compute the *session key* as follows:

- Alice:
- Bob:

They end up having the same session key: , which can be used for message encryption.

### Proof of correctness

Alice computes:

Bob computes:

## 0 Comments