ctfnote.com
Search
⌃K

RSA

Rivest–Shamir–Adleman

The Textbook RSA Scheme

Key Generation (Alice)

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

Encryption (Bob)

Choose a plaintext
mm
 to be sent. Use the public key
K=(N,e)K = (N, e)
 to encrypt
mm
:
c≡memod  Nc \equiv m^e \mod N
In Python, this step is computed by c = pow(m, e, N). Send the ciphertext
cc
 to Alice.

Decryption (Alice)

Compute the private component
d=inverse(e,ϕ(N))d = inverse(e, \phi(N))
 and decrypt
cc
:
m≡cdmod  Nm \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

Reference

Attacking RSA for fun and CTF points – part 1
BitsDeep
Attacking RSA for fun and CTF points Part 1
Attacking RSA for fun and CTF points – part 2
BitsDeep
Attacking RSA for fun and CTF points Part 2
Attacking RSA for fun and CTF points – part 3
BitsDeep
Attacking RSA for fun and CTF points Part 3
Attacking RSA for fun and CTF points – 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
Cryptography - Previous
Diffie-Hellman
Next
Prime Factors
Last modified 7mo ago