To cbrt or not to cbrt?
You open a crypto challenge, you check the provided scripts, and you see e = 3. The immediate instinct is to just \(\sqrt[3]{\text{N}}\) it and be done, right?
Type 1: The FREE!!! Version
Challenge description:
I encrypted my suuuuper duper secret flag. Good luck factoring my massive 1024-bit modulus! Mwehehehe.
💡 Interactive: How do we solve this? (Click to reveal)
Let's look at the textbook RSA encryption formula: $$C \equiv m^e \pmod N$$ If the message $m$ is relatively short, and $e$ is only $3$, then $m^3$ has a chance to be *smaller* than the massive modulus $N$.But what does this mean? Let's look at an example.
Let's say that you have a message. For simplicity's sake, we assume our message is a singular number. Let's say the number is 40. And if we take our p and q as a really large prime. For simplicity's sake, let's assume that $p*q$ is 1 million (1,000,000). What does this do? Well, going back to the following formula: $$C \equiv m^e \pmod N$$ Our ciphertext would be $40^3 \pmod {1000000}$, or $64000 \pmod {1000000}$. What does this mean?
Since the modulo didn't wrap around, the ciphertext $C$ is literally just the raw $m^3$.
You don't really need to factor the modulus or find the private key. You literally just take the standard integer cube root of $C$ to recover the flag.
Try it live!
The following block of code can be ran for your own interest, if you are curious as to how it works! (Solve script is written in SageMath)
Type 2: The Free(n't) flag...
Challenge description:
I figured out the cube root trick, so I padded the message with some extra text at the front. Good luck now!
Prefix: “i_pad_this_part_lol: “
💡 Interactive: How do we do this? (Click to reveal)
Let's go back to our formula: $$C \equiv m^e \pmod N$$ By adding a prefix, the author has made our message $m$ much larger. To solve this, we define a polynomial where our unknown flag is $x$: $$f(x) = (\text{prefix} \cdot 2^k + x)^3 - C \equiv 0 \pmod N$$ Wellllll...that's complex. Let's simplify it a bit more. Let's shrink everything down to see the problem. Imagine our modulus is 323. Our known prefix is 10, and our secret PIN $x$ is 2. The total message is 12.$12^3 = 1728$.
1728 modulo 323 is 113. So our ciphertext is $C = 113$.
So now, our polynomial looks like this: $$f(x) = (10 + x)^3 - 113 \equiv 0 \pmod{323}$$ If we expand that using basic algebra, we get: $$f(x) = x^3 + 30x^2 + 300x + 887 \equiv 0 \pmod{323}$$ We can simplify 887 by modulo-ing it 323, leaving us with the polynomial of: $$f(x) = x^3 + 30x^2 + 300x + 241 \equiv 0 \pmod{323}$$ "Can't we just solve this with simple algebra to find $x$"? Well, No. Maybe? Yes? If you plug $x = 2$ into that equation using normal math, you get 969. Mod 323 and you get 0. In mod 323, 969 is equal to 0 (because 969 mod 323 is 0). However, you can't just use a standard algebraic solver, cause it won't be able to know that substituting x = 2 is a valid answer. It just sees the answer as 969, which isn't 323, so it considers x = 2 an invalid answer when it should be valid (cause again, 969 mod 323 is 0).
Enter Howgrave-Graham's Theorem. The theorem states that if we have a polynomial equation $f(x) \equiv 0 \pmod{N}$ and a set bound X on the size of its' root ($|x_0| \leq X$), then the magnitude of the polynomial evaluated at its X will always be strictly less than N ($f(xX) \lt \frac{N}{\sqrt{d+1}}$), where d is the degree, and the modulo vanishes, which means that the equation becomes $f(x_0) = 0$ over standard integers. To allow this to happen, we need to build a lattice. Think of a lattice as an infinite grid of dots, and every point on this infinite grid is created by mixing and adding together a set of vectors.
Here, we want to find a new polynomial that evaluates to $0 \pmod N$. So we feed our lattice with a set of polynomials that we already know equals to $0 \pmod N$. For example:
- $N$ is a multiple of $N$, so $N \equiv 0 \pmod N$.
- $N \cdot x$ is just $N$ times something, so it is also $\equiv 0 \pmod N$.
- $N \cdot x^2$ is also $\equiv 0 \pmod N$.
- And our polynomial $f(x)$ is what we are trying to solve, so $f(x) \equiv 0 \pmod N$.
There's a problem though, and it's the fact that LLL doesn't know that $x$ is a variable that can grow exponentially quick. To force it to respect higher powers of $x$ are computationally (and mathematically) heavier, we apply an $X$ to the columns, where $X$ is the absolute maximum size we think our secret $x$ could be. Let's take a gamble and say that $X = 5$ (way higher than x = 2, which is what we want to have).
We build our 4x4 matrix row by row. Each column represents a power of $x$ ($x^0, x^1, x^2, x^3$), scaled by our $X$ value:
- Row 1 ($N$): 323, 0, 0, 0
- Row 2 ($Nx$): 0, $323 \cdot 5$, 0, 0 $\rightarrow$ 0, 1615, 0, 0
- Row 3 ($Nx^2$): 0, 0, $323 \cdot 5^2$, 0 $\rightarrow$ 0, 0, 8075, 0
- Row 4 ($f(x)$): 241, $300 \cdot 5$, $30 \cdot 5^2$, $1 \cdot 5^3$ $\rightarrow$ 241, 1500, 750, 125
Try it live!
The following block of code runs both the server generation and the LLL attacker script. (Solve script is written in SageMath)
Final Thoughts
If $m^3 < N$, just cube root it and take your points. If $m^3 > N$ and you know part of the plaintext, you have to let LLL do the heavy lifting. Once you understand what the small_roots function is actually doing under the hood, these Crypto challenges become incredibly satisfying to solve, hehe :3c