Abir encrypts using Bechir's public key

Bechir decrypts using his private key

**How** does that work

Well because

#### What the heck is **phi(n)**?

That's the euler totient

**How** does it work?

Euler proved that:

#### Ok.. so:

is

#### Ok.. **How** to generate keys ?

#### First step

Choose two large prime numbers p and q.

And calculate N

#### Second step

Calculate the euler totient

#### Third step

Choose randomly the public exponent e such that:

#### Fourth step

Calculate d such that

so..

#### Fifth step profit

Publish your publish key:

And keep your private key on your computer:

#### All this is fine **how** to do this?

Demo

#### Factorize n

if you find p and q you can:

- Calculate phi(n)
- Calculate d

#### Determine phi(n)

If you determine phi(n) you can calculate d.

#### Determine d

You can decrypt messages then, welp..

#### Determine messages directly

You can determine messages sharing a common public exponent quite easily

#### If N is small

Use a fast a factorization algorithm :)

Example

#### If N is big ~ > 512 bits

Compute it using shor's algorithm on quantum computer, shrug …

¯\_{(ツ)}_/¯

#### What if p and q are close?

Use fermat theorem for factorizing.

Example

#### What if d is small

Use wiener attack

This only works if:

and

#### What if recipients share a common modulus

Use CRT

Example

## Diffie Hellman Key exchange

Abir calculates:

Bechir calculates:

A and B are exchanged

Abir calculates:

Bechir calculates:

#### Wut? **How** does this work

Simple math:

Abir calculates:

And Bechir does:

**How** to attack this?

To solve **DHP** you have to solve **DLP** (which is hard).

But methods exist.