RSA

RSA (Rivest–Shamir–Adleman) is a public-key cryptosystem that is widely used for secure data transmission.

The strength of RSA relies on the fact that you need to factor n to obtain d and there is no known algorithm that can do that efficiently for large numbers.

Introduction

RSA is an asymmetric cipher with a public key (n, e) and a private key (n, d).

• p and q two large random primes that validate the following equation :

$$n = p * q$$

• Euler’s totient function : $$\varphi(n)=(p - 1)(q - 1)$$

• e (public key exponent) must verify :

$$1 < e < \varphi(n)$$ $$gcd(e, \varphi(n)) = 1$$ $$d * e \equiv 1 [\varphi(n))]$$

Info

Greatest common divisor (GCD) of two integers is the largest positive integer that divides each of the integers.

Key generation

The keys for the RSA algorithm are generated in the following way:

• Choose two distinct prime numbers p and q.

For security purposes, the integers p and q should be chosen at random, and should be similar in magnitude but differ in length by a few digits to make factoring harder. Prime integers can be efficiently found using a primality test. p and q are kept secret.

• Compute n = pq.

• Compute λ(n), where λ is Carmichael's totient function. Since n = pq, λ(n) = lcm(λ(p),λ(q)), and since p and q are prime, λ(p) = φ(p) = p − 1 and likewise λ(q) = q − 1. Hence λ(n) = lcm(p − 1, q − 1). λ(n) is kept secret. The lcm may be calculated through the Euclidean algorithm, since lcm(a,b) = |ab|/gcd(a,b).

• Choose an integer e such that 1 < e < λ(n) and gcd(e, λ(n)) = 1; that is, e and λ(n) are coprime. e having a short bit-length and small Hamming weight results in more efficient encryption – the most commonly chosen value for e is 216 + 1 = 65,537. The smallest (and fastest) possible value for e is 3, but such a small value for e has been shown to be less secure in some settings.[15] e is released as part of the public key.
• Determine d as d ≡ e−1 (mod λ(n)); that is, d is the modular multiplicative inverse of e modulo λ(n). This means: solve for d the equation d⋅e ≡ 1 (mod λ(n)); d can be computed efficiently by using the Extended Euclidean algorithm, since, thanks to e and λ(n) being coprime, said equation is a form of Bézout's identity, where d is one of the coefficients. d is kept secret as the private key exponent.

Encryption (public key)

• c : ciphertext (encrypted message, the result of calculation)
• m : cleartext (plain message to send)
• e : exponent (from public key)
• n : product of two large prime numbers (from public key)

$$c = m^e [n]$$

Decryption (private key)

• d : exponent (from private key)

$$m \equiv c^d [n]$$

Attacks on RSA

Small factors

d is secret and can be calculated very easily if you know φ(n).

$$\varphi(pq) = (p - 1)(q - 1)$$ $$n = p * q$$

The security of RSA depends on the two factors p and q. You can bruteforce this two factors if n is small (< 256 bits) or use a well-known database.

References

• https://bitsdeep.com/posts/attacking-rsa-for-fun-and-ctf-points-part-1/
• https://en.wikipedia.org/wiki/RSA_(cryptosystem)