RSA

Rivest–Shamir–Adleman

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

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.

Lab

CryptoHack – RSA challengesCryptoHack

RSA - CryptoHack

Reference

Real-World CryptographyManning Publications

Real-World Cryptography

Attacking RSA for fun and CTF points – part 1BitsDeep

Attacking RSA for fun and CTF points Part 1

Attacking RSA for fun and CTF points – part 2BitsDeep

Attacking RSA for fun and CTF points Part 2

Attacking RSA for fun and CTF points – part 3BitsDeep

Attacking RSA for fun and CTF points Part 3

Attacking RSA for fun and CTF points – part 4BitsDeep

Attacking RSA for fun and CTF points Part 4

Implementation of Boneh and Durfee attack on RSA's low private exponents

Implementation of Boneh and Durfee attack on RSA's low private exponents - cryptologie