Let's look at the running part first. With
n_size = 2000, m_size = 10, pk,sk,hint are
generated by calling gen(n_size, m_size). Thus, we look at
this function in details.
Part 2 Condition on parameters: \(d_p,
d_q\) are random \(d_s=60\) bits
integer; \(k,l\) are random \(k_s=60\) bits integer. And we have the
constraint: \[
\gcd(k,l) = \gcd(d_p,k) = \gcd(d_q,l)=1.
\]
Part 3 Condition on \(e\): observing
line 19, \(l\) and \(k\) are factors of two components in RHS
equation. Thus, we can actually \(\bmod
l\) and \(\bmod k\) to obtain
the condition on Chinese Remainder Theorem (CRT): \[
\left\{
\begin{aligned}
e &\equiv d_q^{-1} \bmod l\\
e &\equiv d_p^{-1} \bmod k
\end{aligned}
\right.
\]\(c\) is a random \(c_s = 880\) bits integer (very large). And
\(e = e + ckl\). (will not change the
property of \(\bmod l\) or \(\bmod k\).)
Then calculate \(p,q\) as below:
\[
\begin{aligned}
p &= \lfloor\frac{e\cdot d_p - 1}{k}\rfloor +1,\\
q &= \lfloor\frac{e\cdot d_q - 1}{l}\rfloor +1.
\end{aligned}
\]\(p,q\) are prime.
Part 4 Generate and return:
pk: \((pq, e)\)
sk: \((d_p, d_q, p, q)\)
hint: (magic, d_p & mask, d_q & mask)
where: \[
\begin{aligned}
\text{magic}&=1337\cdot k^{4} + 7331 \cdot l^3 + 73331 \cdot k^2 +
13337 \cdot l ^2 + 7 \cdot k \cdot l + 2 \cdot k + l,\\
\text{mask}&= 2^{m_s} - 1.
\end{aligned}
\] This indicates that d_p & mask and
d_q & mask are last \(m_s=10\) bits of \(d_p,d_q\).
We also want to look at how the program encrypts data:
input: \((m,pk=(pq, e))\) output:
\[
c = m ^ e \bmod n
\]
Now, let's look at the main function again.
flag is imported from secret, and is
concatenated by a random string with length related to flag itself.
Finally, we encrypt the hexed flag with public key.
Our solution will be divided into 3 parts: 1) Finding \(k,l\); 2) Using \(k,l\) and conditions on \(d_p,d_q\) to find \(d_p, d_q\); 3) Using \(d_p,d_q\) to find \(p,q\); 4) decrypt
Step 1: Finding \(k,l\)
Expected solution is posted on here.
My attempt also starts from taking the 4th root of magic
then iterates a small range of integers, but I know this quite depends
on luck. The idea is: \[
k'=(k^4+\frac{res}{1337})^{1/4}>k\text{, but also } k'\approx
k,
\] Thus, we let \[
\hat{k}=k'-i,i\in\text{ a small range of integers}.
\] But the problem is: how small should this integer set be? For
an accurate solution, we need further investigation on the value of
\(k'-k\), which probably involves
property of inequality of \((a^n+b^n)^{1/n}
\leq a+b\).
Proof of this inequality is simple, involving binomial expansion:
\[
\begin{aligned}
(a^{1/n}+b^{1/n})^{n} &= a +
\sum_{i=1}^{n-1}C_n^{i}(a^{1/n})^i(b^{1/n})^{n-i}+b\\
&\geq a+b=((a+b)^{1/n})^n
\end{aligned}
\]\[
\begin{aligned}
&\Longrightarrow (a+b)^{1/n}\leq a^{1/n}+b^{1/n}\\
&\Longrightarrow (a^n+b^n)^{1/n}\leq a+b.
\end{aligned}
\] Thus, let \(r =
(\frac{res}{1337})^{1/4}\), we have: \[
k'=(k^4+r^4)^{1/4} \leq k+r
\] The upper bound of \(k'-k\) is \(r\).
Since \(l\) is 60 bits, the range is
actually very large. So I'm not sure why the official solution succeed
from a theoretical perspective. But I can neither find another way to
solve this challenge. I just adapt the way it uses. So the way is to
have: \[\hat{k}=k'-i\text{ and }\hat{l} =
(\frac{\text{magic}-1337\hat{k}^4}{7331})^{1/3},\] and iterate
them in two loop until find a pair of \((\hat{k},\hat{l})\) such that: \[
1337\cdot \hat{k}^{4} + 7331 \cdot \hat{l}^3 + 73331 \cdot \hat{k}^2 +
13337 \cdot \hat{l} ^2 + 7 \cdot \hat{k} \cdot \hat{l} + 2 \cdot \hat{k}
+ \hat{l}.
\] And this is what we want for \((k,l)\).
Note:
When we write code to calculate \(k'\), pow(a, e, m) will
not work for such large calculation. Thus, we have to use
gmpy2 and iroot function.
Step 2: Finding \(d_p,d_q\)
We go back to line 19 and see the equation of \(e\). When we \(\bmod k\) and \(\bmod l\) obtained in step 1, we can obtain
\(d_p^{-1},d_q^{-1}\), then we can use
inverse function to obtain \(d_p,d_q\).
Step 3: Finding \(p,q\)
Look at equation of \(p,q\). Once we have \(d_p,d_q\), we can simply plug in all the
values and obtain \(p,q\), or we can
use \(n=pq\) to calculate the other
factor for convenience.
from math import gcd from Crypto.Util.number import * from z3 import * import gmpy2
N, e = (13144833961692953638155744717380612667335058302310815242506755676885208234342620331186804951145894484501542968789132832800279633590988848298405521677820600481054741175400784558190943019903268095468121342412114428860754522164657102624139527993254089574309927288457799155130004731846999722554981630609692264462023821778810225493633789543259034893395115658330417361250466876018981150507377427664192443342394808337473089411393262018525828475108149889915075872592673448211565529063972264324533136645650169687118301014325354524932405270872098633633071371124551496573869700120350489760340226474892703585296623, 4976865541630914024304930292600669330017247151290783019063407119314069119952298933566289617702551408322779629557316539138884407655160925920670189379289389411163083468782698396121446186733546486790309424372952321446384824084362527492399667929050403530173432700957192011119967010196844119305465574740437) g, dp_mask, dq_mask = (154118536863381755324327990994045278493514334577571515646858907141541837890, 431, 217) c = 12075538182684677737023332074837542797880423774993595442794806087281173669267997104408555839686283996516133283992342507757326913240132429242004071236464149863112788729225204797295863969020348408992315952963166814392745345811848977394200562308125908479180595553832800151118160338048296786712765863667672764499042391263351628529676289293121487926074423104988380291130127694041802572569416584214743544288441507782008422389394379332477148914009173609753877263990429988651290402630935296993764147874437465394433756515223371180032964253037946818633821940103044535390973722964105390263537722948112571112911062
defmagic(k, l): return1337 * k ** 4 + 7331 * l ** 3 + 73331 * k ** 2 + 13337 * l ** 2 + 7 * k * l + 2 * k + l
k_approx = gmpy2.iroot(g//1337, 4)[0]
for i inrange(50): k_bar = k_approx - i t1_approx = 1337 * k_bar ** 4 l_approx = gmpy2.iroot((g-t1_approx)//7331, 3)[0] for j inrange(50): l_bar = l_approx-j if magic(k_bar, l_bar) == g: if gcd(k_bar, l_bar) == 1: k = k_bar l = l_bar break
The code is pretty much similar to the previous one, but 2 things
changed:
no magic any more;
m_size = 12
Output from the challenge becomes:
1 2 3
N, e = (5943169364392579648240628105465400265561630477719849140342288893646282358845864829196464904298425034495515703590715696166689341849788423790118035115884268058450057766891418761627136386260375534474238287294722575087291704432681906513559934960801746158191355141430407698622886747610818853554584519369492697299961587570531415598410602926850787615266600194130088653542080297272898142822126215764285317511778718862825024939241749996811603610592132845393755564618871967716819173935553139267269362451423802419847919801412517294612793840767037662589233422389282092051866024514599213445596030685325227269609799, 1762727270442607836236621349004505613506359415168929966540357011133047321101203605340201016757203407375680206339341465088639129039278027484128644822299382121442456525803635369125157261704416172232695058332167310707999473221769390010733123910955508477009411113166141188309425895082608534271594076218827) dp_m, dq_m = (1361, 1475) c = 4531542437692818645025309324015912433184165181252393791711464775823247402127139569010657935303362440253951226047224610112010632226435610975118324658493911658016955717228741291266124372004503735693124810068041692730706167827666860062121413284053921548345924563903211959003376490264228814415500106847482893238907846512437694006785527867729127228361388592714377847012086312471372061723017560705890925568994607972832373362380226566506368932968108567819188587148829190811891555283157485379418388715910299951228404648535235675640369275644493614250037857212768450860647393276921502407057557208885073276533644
Solution
Although it just removed one line and changed m size, the influence
is huge. We cannot obtain \(k,l\) from
the magic any more. So our method to solve this problem
should be completely changed. This is where lattice attack involves.
I have studied two methods to solve this, but I'll save the official
one for ezRSA++ later. The method I used to solve this one is using LLL
to get the values of \(k,l\), and the
rest steps are pretty the same. This method is proposed by
Bleichenbacher and May [^1][^2].
We still look back at equation for \(p,q\), which can be rewritten as: \[
\left\{
\begin{aligned}
(p-1)k=ed_p-1\\
(q-1)l=ed_q-1\\
\end{aligned}
\right.
\]\[
\Longrightarrow
\left\{
\begin{aligned}
kp&=ed_p+(k-1)\\
lq&=ed_q+(l-1)\\
\end{aligned}
\right.
\] Multiply these two equations to obtain: \[
e^2X+eY+(1-N)Z = W,
\] where: \[
\begin{aligned}
X &= d_pd_q\\
Y &= d_p(l-1)+d_q(k-1)\\
Z &= kl\\
W &= k+l-1
\end{aligned}
\] We write the above in the matrix form: \[
\begin{bmatrix}
X & Y & Z
\end{bmatrix}
\cdot
\begin{bmatrix}
e^2 & 1 & 0 & 0 \\
e & 0 & 1 & 0 \\
1-N & 0 & 0 & 1
\end{bmatrix}
=
\begin{bmatrix}
W & X & Y & Z
\end{bmatrix}
\] Since \(d_p, d_q, k, l\) are
not very large (only 60 bits), we can actually construct a lattice to
solve this linear relationship and obtain the values of \(X,Y,Z,W\). Then, we put all the constraints
into z3 solver and obtain \(d_p,d_q,k,l\).
The rest will be the same as ezRSA.
Note:
Here's one thing that's interesting. When I use LLL()
from sage, it actually calculated and output \(\begin{bmatrix}-W & -X & -Y &
-Z\end{bmatrix}\). So I have to add another step to make them
positive.
from sage.allimport * from z3 import * from Crypto.Util.number import *
N, e = (5943169364392579648240628105465400265561630477719849140342288893646282358845864829196464904298425034495515703590715696166689341849788423790118035115884268058450057766891418761627136386260375534474238287294722575087291704432681906513559934960801746158191355141430407698622886747610818853554584519369492697299961587570531415598410602926850787615266600194130088653542080297272898142822126215764285317511778718862825024939241749996811603610592132845393755564618871967716819173935553139267269362451423802419847919801412517294612793840767037662589233422389282092051866024514599213445596030685325227269609799, 1762727270442607836236621349004505613506359415168929966540357011133047321101203605340201016757203407375680206339341465088639129039278027484128644822299382121442456525803635369125157261704416172232695058332167310707999473221769390010733123910955508477009411113166141188309425895082608534271594076218827) dp_m, dq_m = (1361, 1475) c = 4531542437692818645025309324015912433184165181252393791711464775823247402127139569010657935303362440253951226047224610112010632226435610975118324658493911658016955717228741291266124372004503735693124810068041692730706167827666860062121413284053921548345924563903211959003376490264228814415500106847482893238907846512437694006785527867729127228361388592714377847012086312471372061723017560705890925568994607972832373362380226566506368932968108567819188587148829190811891555283157485379418388715910299951228404648535235675640369275644493614250037857212768450860647393276921502407057557208885073276533644
M = Matrix(ZZ, [[ e*e, 1, 0, 0], [ e, 0, 1, 0], [ 1-N, 0, 0, 1]])
v = M.LLL()[0] v0, v1, v2, v3 = [int(-v[i]) for i inrange(4)]
sol = Solver() dp, dq, k, l = Ints('dp dq k l') # k, l = Ints('k l') sol.add(k + l - 1 == v0) sol.add(dp * dq == v1) sol.add(dp * (l - 1) + dq * (k - 1) == v2) sol.add(k * l == v3)
sol.check()
dp, dq, k, l = sol.model()[dp].as_long(), sol.model()[dq].as_long(), sol.model()[k].as_long(), sol.model()[l].as_long()
p = (e * dp - 1) // k + 1 q = N // p
d = inverse(e, (p-1)*(q-1)) m = pow(c, d, N) print(m) print(bytes.fromhex(hex(m)[2:]))
[^1] New Attacks on RSA with Small Secret CRT-Exponents: paper
[^2] A Polynomial Time Attack on RSA with Private CRT-Exponents Smaller
Than \(N^{0.073}\): paper
ezRSA++
Based on 0CTF 2021 Finals "ezRSA+",
the intended solution is "Partial Key Exposure Attack on Short
Secret Exponent CRT-RSA". Maybe the method in "Small
CRT-exponent RSA revisited" also works
Although I solved the previous two challenges, I didn't solve this
one. I was thinking about Bleichenbacher-May attack and hope that with
several modifications I can solve it, but the fact is
(to be finished)
Code
Reference
Partial Key Exposure Attack on Short Secret Exponent CRT-RSA: paper