RSA (must read)

The Textbook RSA Scheme
Key Generation (Alice)
Generate two large random primes ppp
 and qqq
. Compute the modulus N=pqN = pqN=pq
. Compute ϕ(N)=(p−1)(q−1)\phi(N) = (p-1)(q-1)ϕ(N)=(p−1)(q−1)
. Choose a public exponent eee
 s.t. gcd(e,ϕ(N))=1gcd(e, \phi(N)) = 1gcd(e,ϕ(N))=1
 (usually we use e=65537e = 65537e=65537
). Publish the modulus N=pqN = pqN=pq
 and the public exponent eee
 as the public key K=(N,e)K = (N, e)K=(N,e)
.
Encryption (Bob)
Choose a plaintext mmm
 to be sent. Use the public key K=(N,e)K = (N, e)K=(N,e)
 to encrypt mmm
:
c≡memod  Nc \equiv m^e \mod Nc≡memodN
In Python, this step is computed by c = pow(m, e, N). Send the ciphertext ccc
 to Alice.
Decryption (Alice)
Compute the private component d=inverse(e,ϕ(N))d = inverse(e, \phi(N))d=inverse(e,ϕ(N))
 and decrypt ccc
:
m≡cdmod  Nm \equiv c^d \mod Nm≡cdmodN
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 challenges
CryptoHack
RSA - CryptoHack
Reference
Real-World Cryptography
Manning Publications
Real-World Cryptography
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

Crypto - Previous

Diffie-Hellman

Prime Factors

Last modified 2mo ago

Copy link

Contents

The Textbook RSA Scheme

Key Generation (Alice)