# RSA

## The Textbook RSA Scheme

### Key Generation (Alice)

Generate two large random primes $$p$$ and $$q$$. Compute the modulus $$N = pq$$. Compute $$\phi(N) = (p-1)(q-1)$$. Choose a public exponent $$e$$ s.t. $$gcd(e, \phi(N)) = 1$$ (usually we use $$e = 65537$$). Publish the modulus $$N = pq$$ and the public exponent $$e$$ as the public key $$K = (N, e)$$.

### Encryption (Bob)

Choose a plaintext $$m$$ to be sent. Use the public key $$K = (N, e)$$ to encrypt $$m$$:

$$
c \equiv m^e \mod N
$$

In Python, this step is computed by `c = pow(m, e, N)`. Send the ciphertext $$c$$ to Alice.

### Decryption (Alice)

Compute the private component $$d = inverse(e, \phi(N))$$ and decrypt $$c$$:

$$
m \equiv c^d \mod N
$$

In Python, this step is computed by `m = pow(c, d, N)`.

## Key Exchange

{% hint style="warning" %}
Today, RSA is often not the preferred way of doing a key exchange, and it is being used less and less in protocols in favor of **Elliptic Curve Diffie-Hellman (ECDH)**. This is mostly due to historical reasons (many vulnerabilities have been discovered with RSA implementations and standards) and the attractiveness of the smaller parameter sizes offered by ECDH.
{% endhint %}

## Lab

{% embed url="<https://cryptohack.org/challenges/rsa>" %}
RSA - CryptoHack
{% endembed %}

## Reference

{% embed url="<https://www.manning.com/books/real-world-cryptography>" %}
Real-World Cryptography
{% endembed %}

{% embed url="<https://bitsdeep.com/posts/attacking-rsa-for-fun-and-ctf-points-part-1>" %}
Attacking RSA for fun and CTF points Part 1
{% endembed %}

{% embed url="<https://bitsdeep.com/posts/attacking-rsa-for-fun-and-ctf-points-part-2>" %}
Attacking RSA for fun and CTF points Part 2
{% endembed %}

{% embed url="<https://bitsdeep.com/posts/attacking-rsa-for-fun-and-ctf-points-part-3>" %}
Attacking RSA for fun and CTF points Part 3
{% endembed %}

{% embed url="<https://bitsdeep.com/posts/attacking-rsa-for-fun-and-ctf-points-part-4>" %}
Attacking RSA for fun and CTF points Part 4
{% endembed %}

{% embed url="<https://www.cryptologie.net/article/241/implementation-of-boneh-and-durfee-attack-on-rsas-low-private-exponents>" %}
Implementation of Boneh and Durfee attack on RSA's low private exponents - cryptologie
{% endembed %}