RSA Cryptosystem

Monish Singhal

Why a new cryptosystem?

Weakness in existing cryptosystems
Text can be mapped to numbers easily – Usage of number theory

The basics

Primes and co-primes

Modular Arithmatic

\(a \equiv r \pmod{N}\) where \(a = qN + r\)

Modular Division

\(a \cdot a^{-1} \equiv 1 \pmod{N}\)
EGCD Algorithm to find the inverse

Euler's Totient Function

\(\phi(n) = \sum_{k = 1}^{n} 1\) such that \(k\) is coprime to \(n\)
Example: \(\phi(6) = 2 \{1, 5\}\)
For a prime number: \(\phi(p) = p - 1\)
Why?
For two coprime numbers \(m\) and \(n\): \(\phi(mn) = \phi(m) \phi(n)\)
Why?

The Euler totient function has no particularly significant origins. It's rather simple to define. The value of the euler totient function for a number is merely the number of elements that are coprime to the number. Here, we take 1 to be coprime to all other numbers. Let us take a few examples, \(n = 6\) and \(n = 15\).

It is rather trivial to see that the euler totient function for a prime \(p\) is merely \(p - 1\). So, we don't really need to iterate for all values to calculate the euler totient function for p.

Something that is much harder to see is that the Euler totient function is multiplicative, that is, the product of the totient functions for two co prime numbers m and n will be the value of the totient function mn. There is a neat proof using the Chinese remainder theorem that can be found online, but I liked another visual proof that is on MathSE. Take, for example m = 5, n = 6. We draw a grid of size \(m \times n\), and then fill it in diagonally, starting from the bottom left. (fills grid). Now, we begin crossing out numbers that are not coprime to \(mn\). Observe that for every number, either the entire row is crossed out, the entire column is crossed out, or both. Also, the number of rows and columns is equal to \(\phi(n)\) and \(\phi(m)\) respectively. Can anyone tell why? Therefore, if we take all the numbers not crossed out, (which would form the set of all coprime numbers to \(mn\)), we get a grid of size \(\phi(n)\phi(m)\), and hence proved.

https://math.stackexchange.com/a/999599

Euler's Theorem

\(a ^ {\phi(n)} \equiv 1 \pmod{n}\)
Why?
Hint: Try finding a bijection

The Actual Cryptosystem

Two primes \(p\) and \(q\)
\(n = pq\)
\(de \equiv 1 \mod (p - 1)(q - 1)\)

Encryption: \(m^e \pmod n\)
Decryption: \(c^d \pmod n\)

Security of the RSA

Attacks

1. Small Values of \(m\) or \(n\)

If \(m\) is small: Bruteforce
If \(n\) is small: factorise

2. Unpadded Message Recovery

\(C' = C \cdot S^E\), find \(P' = \text{decrypt}(C')\), and hence \(P = P' S^{-1}\)

Flipping Bits (Square CTF 2018 C2)

ct1: <long num 1> ct2: <long num 2> e1: 13 e2: 15 modulus: <modulo>

You have two captured ciphertexts. The public key is (e1, n). But, due to a transient bit flip, the second ciphertext was encrypted with a faulty public key: (e2, n). Recover the plaintexts.

Bezout's Theorem

\(xa + yb = \gcd(a, b)\) for all \(a, b\)

The Attack

\(C_1 = M^{e_1}\), \(C_2 = M^{e_2}\)
\(C_1^{x} \cdot C_2^{y} = M^{xe_1} \cdot M^{ye_2} = M^{\gcd(a, b)}\)

4. Broadcast Attacks for small values of \(e\)

Given some number of ciphertexts encrypting the same plaintext, knowning the values of public keys, find the plaintext

Chinese Remainder Theorem

For a set of congruences \[x \equiv a_i \pmod n_i,\; 0 < i \leq k,\] there exists a solution, and that solution is unique under the congruence of \(N = \prod_{i = 1}^{k} n_i\), where each of \(n_i\) is pairwise coprime

Bonus: GCTF 2022 Cycling

Credits: https://ur4ndom.dev/posts/2022-07-04-gctf-cycling/

Problem

It is well known that any RSA encryption can be undone by just encrypting the ciphertext over and over again. If the RSA modulus has been chosen badly then the number of encryptions necessary to undo an encryption is small. However, if the modulus is well chosen then a cycle attack can take much longer. This property can be used for a timed release of a message. We have confirmed that it takes a whopping 2¹⁰²⁵-3 encryptions to decrypt the flag. Pack out your quantum computer and perform 2¹⁰²⁵-3 encryptions to solve this challenge. Good luck doing this in 48h.

How to attack the problem?

Bruteforce clearly out of the way
Need to use smart maths

Observations made

\(M^{e^{R + 1}} = M \mod {N}\)

Carmicheal Function

\(\lambda(n)\) = smallest positive integer such that \(a^m \equiv 1 \pmod n, \forall a\) coprime to \(n\)
Observe: \(\lambda(n) | \phi(n)\), and \(\lambda(n)\) can be used in RSA
Clean expression for \(\lambda(n)\)?

More observations

\(e^{R + 1} \equiv 1 \pmod{\lambda(n)}\)
Euler theorem vibes?

Assumptions pt. 1

\(R + 1 = \lambda(\lambda(n))\)?

More observations pt. 2

\[R + 1 = \lambda(\lambda(n)) = \mathrm{lcm}(s_1 - 1, \ldots, s_m -1)\]
Factorising: http://factordb.com/index.php?query=2%5E1025+-+2

Final Solution?

Lazy approach: Find \[\prod_{i = 1}^{m} s_i\], use that as exponent
Actual Solution: Pollard's \(p - 1\) Algorithm to factorise numbers

Implicit Assumptions

\(p - 1\), \(q - 1\) were square-free