Asymmetric Crypto

RSA Cryptosystem

What is this?

Abir encrypts using Bechir's public key

Bechir decrypts using his private key

How Does this work

Well because

What the heck is phi(n)?

That's the euler totient

How does it work?

Euler proved that:

is

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:

Demo

How to break this?

Factorize n

if you find p and q you can:

1. Calculate phi(n)
2. 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 :)

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.

What if d is small

Use wiener attack

This only works if:

and

Use CRT

Diffie Hellman Key exchange

What is this

Abir calculates:

Bechir calculates:

A and B are exchanged

Abir calculates:

Bechir calculates:

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.