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)=(p1)(q1)\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
:
cmemodNc \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
:
mcdmodNm \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