强网杯-Qualifier-2020/强网先锋/baby_crt writeup
强网杯-Qualifier-2020/强网先锋/baby_crt writeup
描述信息
- 分值：105
- 已解答：77
- 第一名：WM
- 第二名：激流勇进队
- 第三名：L3H_Sec
题目分析
题目提供了两个文件
- task.py: 提供了具体的加密算法，但生成flag的大素数p未知
- output0: 三个数，分别对应task.py中的n,m,sig
task.py文件内容不长，可以快速翻译为数学语言如下：
典型RSA相关的参数： $$ \begin{align} \begin{cases} & e = 65537 \newline & p,q未知, n = p\cdot q \newline & e\cdot d \equiv 1\mod n \end{cases} \end{align} $$
基于d派生的相关参数: $$ \begin{cases} \begin{align} & t_1, t_2是16 bit的素数 \newline & gcd(d,t_{1,2}-1)==1 \newline & t_{1,2} \equiv 3 \mod 4 \newline & e_{t_1} \cdot d \equiv 1 \equiv \mod t_1 \newline & e_{t_2} \cdot d \equiv 1 \equiv \mod t_2 \end{align} \end{cases} $$
sign函数中涉及的等式： $$ \begin{cases} \begin{align} & m已知 \newline & k是16bit的随机素数 \newline & d_p \equiv d \mod phi(p\cdot t_1) \newline & d_q \equiv d \mod phi(q\cdot t_2) \newline & S_p \equiv {(m+k)}^{d_p} \mod (p\cdot t_1) \tag{0-1} \newline & S_q \equiv {m}^{d_q} \mod (q\cdot t_2) \tag{0-2} \newline & C_p \equiv q \cdot t_2 \cdot ((q \cdot t_2)^{-1} \mod (p \cdot t_1)) \tag{0-3} \newline & C_q \equiv p \cdot t_1 \cdot ((p \cdot t_1)^{-1} \mod (q \cdot t_2)) \tag{0-4} \newline & S \equiv C_p \cdot S_p + C_q\cdot S_q \mod (p \cdot q \cdot t_1 \cdot t_2) \tag{0-5} \newline & c_1 \equiv m - S^{e_1} + 1 \mod t_1 \newline & c_2 \equiv m - S^{e_2} + 1 \mod t_2 \newline & sig \equiv S^{c_1 \cdot c_2} \mod n \end{align} \end{cases} $$
题解
观察0-1,0-2,0-3,0-4,0-5式，可发现这是中国剩余定理的公式。因此想到$S_p, S_q和S应该分别在模p\cdot t_1, q\cdot t_2 上相等$，证明如下： $$ \begin{align} S & \equiv S_p \cdot C_p + S_q \cdot C_q \mod ( (p\cdot t_1)\cdot (q \cdot t_2)) \newline & \equiv S_p \cdot q \cdot t_2 \cdot ((q \cdot t_2)^{-1} \mod (p \cdot t_1)) + S_q \cdot p \cdot t_1 \cdot ((p \cdot t_1)^{-1} \mod (q \cdot t_2)) \mod (p\cdot t_1) \newline & \equiv S_p \cdot q \cdot t_2 \cdot (q \cdot t_2)^{-1} + S_q \cdot 0 \mod (p\cdot t_1) \newline & \equiv S_p \mod (p\cdot t_1) \end{align} $$
同理, 也有$S \equiv S_q \mod (q\cdot t_2)$
下面我们希望对最终的等式做一些化简，特别是$c_1\cdot c_2$，尽可能得减少未知数。
根据以上所有等式，结合模运算性质可得 \begin{cases} \begin{align} & S \equiv (m+k)^{d_p} \mod (p) \tag{1} \newline & S \equiv (m+k)^{d_p} \mod (t_1) \tag{2} \newline & S \equiv m^{d_q} \mod (q)\tag{3} \newline & S \equiv m^{d_q} \mod (t_2) \tag{4} \newline & d_p \equiv d \mod (p-1) \tag{5} \newline & d_p \equiv d \mod (t_1 - 1) \tag{6} \newline & d_q = d \mod (q-1) \tag{7} \newline & d_q = d \mod (t_2 - 1) \tag{8} \newline & e_1 = d^{-1} \mod (t_1 - 1) \tag{9} \newline & e_2 = d^{-1} \mod (t_2 - 1) \tag{10} \end{align} \end{cases}
由(2)(6)(9)可得
\begin{align} & S^{e_1} \mod t_1 \equiv (m+k)^{d_p \cdot e_1} \mod (t_1)\newline & \equiv (m+k)^{d \cdot d^{-1} \mod (t_1 -1)} \mod (t_1)\newline & \equiv (m+k)^{1+a1 \cdot (t_1 -1)} \mod (t_1)\newline & \equiv (m+k) \mod (t_1)\newline \end{align}
类似的，由(4)(8)(10)可得 \begin{align} & S^{e_2} \mod t_2 \equiv (m) \mod (t_2)\newline \end{align}
因此 \begin{align} & c_1 = (m-S^{e_1}\mod t_1 +1) \mod t_1 \newline & = [m-(m+k+a2 \cdot t_1)+1] \mod t_1 \newline & = 1-k+a3 \cdot t_1 \quad \quad(其中a3为1或2) \end{align}
同理 \begin{align} & c_2 = (m-S^{e_2}\mod t_2 +1) \mod t_2 \newline & = (m-m+a4 \cdot t_2 +1) \mod t_2 \newline & = 1 \end{align}
所以 \begin{align} & sig \equiv S^{c_1 \cdot c_2} \mod n \equiv S^{1-k+a3 \cdot t_1} \mod n \quad \quad (a3=1,2) \end{align}
此时，可以进一步将S化简为Sp 或 Sq，因Sq未知数更少，我们选择将S化简为Sq:
又因 \begin{align} & n = p \cdot q \newline & \Longrightarrow \newline & sig \equiv S_q^{1-k+a3 \cdot t_1} \mod q \quad \quad (a3=1,2) \quad \quad (11) \end{align}
由 \begin{align} & e \equiv d^{-1} \mod (p-1) \cdot (q-1) \end{align} 得 \begin{cases} \begin{align} & e \equiv d^{-1} \mod (p-1) \newline & e \equiv d^{-1} \mod (q-1) \tag{12} \end{align} \end{cases}
由(3)(7)(12)得 \begin{align} & S_q^e \equiv m^{d_q \cdot e} \mod q \newline & \equiv m^{d \cdot d^{-1} \mod (q-1)} \mod q\newline & \equiv m^{1+a5 \cdot(q-1)} \mod q \newline & \equiv m \mod q \quad \quad (13) \end{align}
由(11)(13)得 \begin{align} & (S^e)^{1-k+a3\cdot t_1} \equiv (S^{1-k+a3\cdot t_1})^e \mod q \newline & \equiv sig^e \mod q \newline & \equiv m^{1+k+a3 \cdot t_1} \mod q \quad \quad (a3=1,2) \end{align}
所以 \begin{align} & (m^{1-k+a3 \cdot t_1} - sig^e)|q \newline & \Longrightarrow \newline & gcd((m^{1-k+a3 \cdot t_1} - sig^e), n)=q \ne 1 \quad \quad (a3=1,2) \end{align}
exp
from hashlib import sha1
import libnum
from Crypto.Util.number import long_to_bytes
min = 1 - pow(2, 17) + pow(2, 15)
max = 1 - pow(2, 15) + pow(2, 17)
n = 26318358382258215770827770763384603359524444566146134039272065206657135513496897321983920652242182112479484135343436206815722605756557098241887233837248519031879444740922789351356138322947108346833956405647578838873425658405513192437479359531790697924285889505666769580176431360506227506064132034621123828090480606055877425480739950809109048177976884825589023444901953529913585288143291544181183810227553891973915960951526154469344587083295640034876874318610991153058462811369615555470571469517472865469502025030548451296909857667669963720366290084062470583318590585472209798523021029182199921435625983186101089395997
m = 26275493320706026144196966398886196833815170413807705805287763413013100962831703774640332765503838087434904835657988276064660304427802961609185997964665440867416900711128517859267504657627160598700248689738045243142111489179673375819308779535247214660694211698799461044354352200950309392321861021920968200334344131893259850468214901266208090469265809729514249143938043521579678234754670097056281556861805568096657415974805578299196440362791907408888958917063668867208257370099324084840742435785960681801625180611324948953657666742195051492610613830629731633827861546693629268844700581558851830936504144170791124745540
sig = 20152941369122888414130075002845764046912727471716839854671280255845798928738103824595339885345405419943354215456598381228519131902698373225795339649300359363119754605698321052334731477127433796964107633109608706030111197156701607379086766944096066649323367976786383015106681896479446835419143225832320978530554399851074180762308322092339721839566642144908864530466017614731679525392259796511789624080228587080621454084957169193343724515867468178242402356741884890739873250658960438450287159439457730127074563991513030091456771906853781028159857466498315359846665211412644316716082898396009119848634426989676119219246
e = 65537
sig_power = pow(sig, e, n)
for i in range(min, max):
x = pow(m, i, n)
if libnum.gcd((x - sig_power), n) != 1:
q = libnum.gcd((x - sig_power)%n, n)
p = n // q
assert p * q == n
print(p)
flag = "flag{" + sha1(long_to_bytes(p)).hexdigest() + "}"
print(flag)
break
总结
本题涉及到的知识点主要是数论、欧拉定理、欧拉函数、孙子定理，基本都涵盖在《信息安全数学基础》课程中。