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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://ret2basic.gitbook.io/ctfnote/crypto/rsa.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.