ctfnote.com
Search
K

# 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

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.

## Reference

Attacking RSA for fun and CTF points &#8211; part 1
BitsDeep
Attacking RSA for fun and CTF points Part 1
Attacking RSA for fun and CTF points &#8211; part 2
BitsDeep
Attacking RSA for fun and CTF points Part 2
Attacking RSA for fun and CTF points &#8211; part 3
BitsDeep
Attacking RSA for fun and CTF points Part 3
Attacking RSA for fun and CTF points &#8211; part 4
BitsDeep
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