Asymmetric Crypto

Knani Mohamed Aziz

RSA Cryptosystem

What is this?

Abir encrypts using Bechir's public key

Sorry, your browser does not support SVG.

Bechir decrypts using his private key Sorry, your browser does not support SVG.

Why Does this work

Because math

How Does this work

How does that work

Well because

Sorry, your browser does not support SVG.

What the heck is phi(n)?

That's the euler totient

How does it work?

Euler proved that:

Sorry, your browser does not support SVG.

Ok.. so:

Sorry, your browser does not support SVG.

is

Sorry, your browser does not support SVG.

Ok.. How to generate keys ?

First step

Choose two large prime numbers p and q.

And calculate N

Sorry, your browser does not support SVG.

Second step

Calculate the euler totient

Sorry, your browser does not support SVG.

Third step

Choose randomly the public exponent e such that:

Sorry, your browser does not support SVG.

Fourth step

Calculate d such that

Sorry, your browser does not support SVG.

so..

Sorry, your browser does not support SVG.

Fifth step profit

Publish your publish key:

Sorry, your browser does not support SVG.

And keep your private key on your computer:

Sorry, your browser does not support SVG.

All this is fine how to do this?

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

Ok, how to factorize N

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:

Sorry, your browser does not support SVG.

and

Sorry, your browser does not support SVG.

What if recipients share a common modulus

Use CRT

Example

Diffie Hellman Key exchange

What is this

Abir calculates:

Sorry, your browser does not support SVG.

Bechir calculates:

Sorry, your browser does not support SVG.

A and B are exchanged

Abir calculates:

Sorry, your browser does not support SVG.

Bechir calculates:

Sorry, your browser does not support SVG.

Wut? How does this work

Simple math:

Abir calculates:

Sorry, your browser does not support SVG.

And Bechir does:

Sorry, your browser does not support SVG.

How to attack this?

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

But methods exist.