LOV3 -> OV3

PPT(图片)地址

视频地址(38 分 40 秒)

数据生成代码(题目/Sage)

from Crypto.Util.number import long_to_bytes, bytes_to_long, getPrime

flag = b'flag{xxxLOV3xxx}'
m = bytes_to_long(flag)
p = getPrime(1024)
q = getPrime(1024)
n = p * q
phi = (p - 1) * (q - 1)
e1 = getPrime(30)
e2 = getPrime(20)
print(f'{e1 = }')
print(f'{e2 = }')
print(f'{n = }')
d1 = inverse_mod(e1, phi)
d2 = inverse_mod(e2, phi)
c1 = pow(m, e1, n)
c2 = pow(m, e2, n)
print(f'{c1 = }')
print(f'{c2 = }')

推导

如果 e1 与 e2 互素(不互素就先直接算 r, s, 最后开gcd(e1, e2)次根), 则用拓展欧几里得解r, s

如果 r 是负数, (r 和 s 中有一个必定是负数) 那么再用欧几里得算法计算 $c_1^{-1}$, (为什么要求逆) 有:

$\begin{aligned} (c_1^{-1})^{-r} \cdot c_2^s &= m \pmod{N} \\ \end{aligned}$

证明

$\begin{aligned} r \cdot e1 + s \cdot e2 &= 1 \\ r \cdot e1 &\equiv 1 \pmod{e2} \\ s \cdot e2 &\equiv 1 \pmod{e1} \\ \end{aligned}$

得出 $e_1, e_2$，接着我们计算 $m$

$\begin{aligned} c_1^r * c_2^s &\equiv {m^{e_1}}^r * {m^{e_2}}^s \pmod {n} \\ c_1^r * c_2^s &\equiv m^{e_1*r} * m^{e_2*s} \pmod {n} \\ c_1^r * c_2^s &\equiv m^{e_1*r + e_2*s} \pmod {n} \\ \end{aligned}$

而我们又有 $e_1*r + e_2*s = 1$，证毕

exploit(Sage)

e1 = 909617123
e2 = 717341
n = 30805510041829887696476737525575706832953321802770268471704352002017400171324006202099312531646808508162944538397384616480741150546961531268315358586098057325996859188034311550611708253641719326076850408213529994773223320874934263090787516142900921485619344237276075381177694399817785697456833443016568755505389415236356870919267399763600472168284453699571155154443595944578112318261837398040381339293515757393594426663888460905678334994459881480475988568299180057517697185972764801132841623530350497000448156918201280445137693234839947121458210788026731332193577753122089681484122410185410948366708829064326876432859
c1 = 16658093030854908295795753524148398626026317522198113359544399568528156610414090507227308938551113369412923974122924221424807444026499995455110566118260451869333958886401663155854868834524619463831117646366586810194486109638268815677113800372145537318914835136008370193892997148742356022371498140375616809050723228136787612557277336893618037577494315158534901558237957535579635712415678742916661310045211405500669579173687842143764696975537383761395065848562735211612102776625893526325486297969540483193777537317573667678865406497021338030208517498840371807520502994445319771566903451867075074048413821805234824057901
c2 = 17808322974980887016662143719190441997000567881200766120580641670935212651236306224642103322910968650379131728323864222915545931222371120296772129840087299093791727032840382733855844530619481048152489534088492376879756419192491249259615931285843127244730454648014448805812743983290724110771253916645477220129762206866546721721744890864663007564473024528748100906234779870168387781677998385510129899537836915744193027501184895276205653755477195903855294908873582999506013235255664963867468640827420330257936007467017477515856721792712240867804938603336377173752708478851143801454417014403615414606334336329278621959575

GCD = gcd(e1, e2)
assert GCD == 1
# Extended Euclidean Algorithm
# ax + by = gcd(a, b)
import sympy
x, y, z = sympy.gcdex(e1, e2)
assert x * e1 + y * e2 == z
print(f'{x = }')
print(f'{y = }')
print(f'{z = }')

# 正的比较好算(密码学04｜公钥密码学（非对称密码）38:40s)
# if x < 0:
#     x = -x
#     c1 = inverse_mod(c1, n)
# elif y < 0:
#     y = -y
#     c2 = inverse_mod(c2, n)
import gmpy2
m = gmpy2.powmod(c1, int(x), n) * gmpy2.powmod(c2, int(y), n) % n # 对x, y 转换到 int 防止因为sympy的精度问题导致powmod报错
print(long_to_bytes(m))