CCTF2023

N1Key2023/8/13大约 3 分钟

中等难度

Risk

题目源码：

#!/usr/bin/envpython3  

fromCrypto.Util.numberimport*  
fromsecretimportm,flag  
  
defgenPrime(m,nbit):  
assertm>=2  
whileTrue:  
a=getRandomNBitInteger(nbit//m)  
r=getRandomNBitInteger(m**2-m+2)  
p=a**m+r  
ifisPrime(p):  
return(p,r)  
  
defgenkey(m,nbit):  
p,r=genPrime(m,nbit//2)  
q,s=genPrime(m,nbit//2)  
n=p*q  
e=r*s  
return(e,n)  
  
defencrypt(msg,pkey):  
e,n=pkey  
m=bytes_to_long(msg)  
c=pow(m,e,n)  
returnc  
  
pkey=genkey(m,2048)  
enc=encrypt(flag,pkey)  
  
print(f'pkey={pkey}')  
print(f'enc={enc}')
#pkey = (105524055, 5020467657792289286373962220896514844843311800307451396289130488363758501149525451873184581770251608183153992116628666678048542345149978948206318784254894702092884634959626708109342232344029446131761318991235021830307336879069990285152877402261629399279873415283081154042950489510015704972161714171248135886237698657746665442663657595842382148193401250472436206897598091943306567186249101906322915899867213314904550492399806035494580958892416135649889600476326148757948912964365494032927588894027623262018823340007579684679104908180122284738465351682030489778303792965247767202881248092765831954480714544681254071127)
#enc = 1079656086402553272225842402774906821703888705155872747874488721487280682974238529940189640205027256055033551574716007350512999534815218159321070295664267915704056108351717232443531194073408117151589388245725955315500379454250542782024135573640738661952719576166134524654123795393966161131894399609281280497151113751130470620951699570107649891392241431558649052533865450271827400234346234360610503700744457767284766656220340953082944574108451417337674525406659260939338191355178055066054528462815921678132923794801726467313680723427862283786662891654965879108276065668209663234535275899983577868923617295806596546989

Abstract

$m >= 2$

$a, b :$ 大约为 1024/m bit

$r, s :$ $(m^{2} - m + 2)$ bit

$p = a^{m} + r, q = b^{m} + s$

$N = p * q = (a^{m} + r) (b^{m} + s) = (a b)^{m} + r b^{m} + s a^{m} + r s$

$e = r s = 105524055$

Writeup1

计算：print(bit_length(e))
得到 e_bit = 28 bit

因为 $e = r s = 2^{2 (m^{2} - m + 2)} = 2^{28}$ ，所以得到 m = 4

r,s 的值是由 m 得来的，所以可以爆破范围值得到相对应的 r 和 s

# 求出 r,s
for i in range(pow(2, m ** 2 - m + 2 - 1), pow(2, m ** 2 - m + 2)):
    if e % i == 0:
        print(i)
r = 10728
s = 14071
assert e == r * s

现在可以知道 a,b 的值大约是 256 bit ，再回头看式： $N = p * q = (a b)^{m} + r b^{m} + s a^{m} + r s$

可知： $N - e = (a b)^{m} + r b^{m} + s a^{m}$

因为： $a^{m}, b^{m} >> r, s$ 所以 p，q 大约是 1024 bit

有： $(a b)^{4} ≃ (N - e)$

gmpy2.iroot(N-e,4)[0] = ab

现在需要计算出 a,b，然后就可以恢复出 p，q 的值了。

可以利用上面的已知信息构造方程
ab = gmpy2.iroot(N-e,4)[0]
令变量 x = a^4 ，y = b^4
1、 $f 1 = x * y - (a b)^{4}$
2、 $f 2 = N - (x + r) (y + s)$

#sage
ab = int(iroot(int(N-e),int(4))[0])

PR.<x,y> = PolynomialRing(ZZ)
f1 = x*y - ab^m
f2 = N - (x+r)*(y+s)
I = ideal(f1,f2).groebner_basis()
print(I)

#得到方程组的三个根
#[x*y - 373824666550208932851344358703053061405262438259996622188837935528607451817812480600479188884096072016823491996056842120586016323642383543231913508464973502962030059403443181467594283936168384790367731793997013711256520780338341018619858240958105689126133812557401122953030695509876185592917323138313818370078183622488492325510372620723458281322670126322487451798415065857893485061235332234643328604472532006852777188749018175995995141869651766501799719427754318115199007112742131582008382245054726684544048143750141235219832037171446181288981313309977073021857987984296469224633291294789702231875602652793732997376, 10728*y^2 - 511086150867555670991182215716996884365017094048011334498502864759458604412974525192545554902255616748785034586283311417267948637161905335789524940513213807388789747893057116518524986565352587286484213819873973314973576845522082944759362821020072842990178502502907835104629002180230922192278601476281549539304919*y + 5260086883027989894151266471310659627033447768756412470819138590823035454528439414529342666788115829348723355876515825478765835689971978836816254977610642160178724965865849006430519169265825342385264354073331979931090503900140796473000025308521505151693828876495191201072094916519467807477939653879213738285370121752035575512256453146199781476491291347483720934255498391686419228296642359873666276793532997868425427822887434754439647641247870006446823852067931010198965229083394533490439946570165059178219301430708237320778256595039419216917256059584687394490563748927035618459815041808985900104721604927460617006077696, 14071*x + 10728*y - 511086150867555670991182215716996884365017094048011334498502864759458604412974525192545554902255616748785034586283311417267948637161905335789524940513213807388789747893057116518524986565352587286484213819873973314973576845522082944759362821020072842990178502502907835104629002180230922192278601476281549539304919]

计算p,q的值，完整EXP:

from gmpy2 import *
from sage import all
pkey = (150953688,
        373824666550208932851344358703053061405262438259996622188837935528607451817812480600479188884096072016823491996056842120586016323642383543231913508464973502962030059403443181467594283936168384790367731793997013711256520780338341018619858240958105689126133812557401122953030695509876185592917323138313818881164334490044163316692588337720342646339764174333821950301279825316497898035760524780198230860089280791887363472060435443944632303774987556026740232641561706904946900169858650106994947597642013168757868017723456208796677559254390940651802333382820063200360490892131573853635471525711894510477078934343423255983)
enc = 275574424285842306309073814038154403551700455145115884031072340378743712325975683329051874910297915882286569143815715537085387363420246497061870251520240399514896001311724695996978111559476733709139080970977190150345474341853495386364275702356438666152069791355990718058189043717952080875207858163490627801836274404446661613239167700736337269924479349700031535265765885064606399858172168036794462235707003475360358004643720927563261787867952228496769300443415094124132722170498229611285689671203272698693505808912907778910378274197503048226322090611405601517624884408718689404556983397217070272851442351897456769883

# 通过 e 求出 m
e, N = pkey
# print(e.bit_length())
m = 4

# 求出 r,s
for i in range(pow(2, m ** 2 - m + 2 - 1), pow(2, m ** 2 - m + 2)):
    if e % i == 0:
        print(i)
r = 10728
s = 14071
assert e == r * s

ab = int(iroot(int(N-e),int(4))[0])

PR.<x,y> = PolynomialRing(ZZ)
f1 = x*y - ab^m
f2 = N - (x+r)*(y+s)
I = ideal(f1,f2).groebner_basis()
# print(I)

PR.<y> = PolynomialRing(ZZ)
f3 = 10728*y^2 - 511086150867555670991182215716996884365017094048011334498502864759458604412974525192545554902255616748785034586283311417267948637161905335789524940513213807388789747893057116518524986565352587286484213819873973314973576845522082944759362821020072842990178502502907835104629002180230922192278601476281549539304919*y + 5260086883027989894151266471310659627033447768756412470819138590823035454528439414529342666788115829348723355876515825478765835689971978836816254977610642160178724965865849006430519169265825342385264354073331979931090503900140796473000025308521505151693828876495191201072094916519467807477939653879213738285370121752035575512256453146199781476491291347483720934255498391686419228296642359873666276793532997868425427822887434754439647641247870006446823852067931010198965229083394533490439946570165059178219301430708237320778256595039419216917256059584687394490563748927035618459815041808985900104721604927460617006077696
# print(f3.roots())

# y = bm
bm = 15040222622096320078383580808680733765955114958694997949647342925417877088612792495485641348591026281373930569798925789027166056695954731923306109646611840570310396750856642056018981080439916663195842593441587057719678555907050674529272376248049062724657792390788687452049496308886252188791975094655675924736
b = iroot(int(bm),int(4))[1]
print(b)

q = bm + s
p = N // q
assert p*q == N

print("p =",p)
print("q =",q)

Tips

提示

关于构造方程：f1 = $x * y - (a b)^{m}$

对于源方程 $N = p q = (a^{m} + r) (b^{m} + s)$ , $(a b)^{m} ≃ (N - e)$

ab = gmpy2.iroot(N-e,m)[0]

我们可以随意构造一个类似的方程,如下：

a = 10
b = 12
r = 4
s = 5
m = 5
N = (a^m+r)*(b^m+s)
e = r*s
ab = int(iroot(int(N-e),int(m))[0])
print("ab =",ab)
(a^m)*(b^m) == ab^m

输出：

ab = 120
True

提示

上面的计算还用到了sage中的如下函数用于计算多项式方程组的解，我们可以通过Groebner_basis得到一些方程的根：

I = ideal(f1,f2).groebner_basis()

print(I)

writerup2

通过计算可知 e,phi 不互素，且 gcd(e,q-1) = 6

所以可以知道 $e d = 6 m o d (q - 1)$

因为 $c = m^{e} m o d N$

由式 $e d = 6 m o d (q - 1)$ 可以得到 $e d = 6 + k (q - 1)$ ，k为一个整数

等式左右两边同时除以 6 得到： $(e / 6) * d = 1 m o d (q - 1) / 6$

d = invert((e//6),(q-1)//6) # 计算私钥

$c^{d} m o d q = m^{e (6 / e + k * (\frac{q - 1}{6}))} m o d q = (m^{6} m o d q) * (m^{(q - 1) * k} m o d q) = m^{6} m o d q$

(第三个等式的化简利用到了费马小定理)

因为这里得到的 m 实际上是有损失数据的，所以应该采取在有限域 F(q) 上求根值的方法求解 m

构造一个模多项式方程，然后求出所有可能的根值

from sage.all import *
from Crypto.Util.number import long_to_bytes
from gmpy2 import *

e = 150953688
p = 24854995563762799317055160315647073592768859410925406616067526817964296709994775588158311030813096922905657553370793515214591086698010302872311633588541111630338981703494212247996116660819640489213219705595382514374022123356637290058228183400682431815794876393612877273757515867990847040787313812864434536969
q = 15040222622096320078383580808680733765955114958694997949647342925417877088612792495485641348591026281373930569798925789027166056695954731923306109646611840570310396750856642056018981080439916663195842593441587057719678555907050674529272376248049062724657792390788687452049496308886252188791975094655675938807

print(gcd(e,q-1))

d = invert((e//6),(q-1)//6)
print('d =', d)
assert e * d % (q-1) == 6

m6 = pow(enc % q, d, q)
assert pow(m6, e//6, q) == enc % q
print('m6 =',m6)

PR.<x> = PolynomialRing(Zmod(q))

m6 = 6737149052150272134972940516590980024331491319339741317342183169802474656888386084365871287308045730462954100927849817850868865189752921007067826413968051476282853264469660023301658697080152738648906257793188559177506701773637608811467111764155767760049813836531589499517889064750007039677591074035963533567

f = x^6 - m6
m = f.roots()
# print(m)
for i in m:
    flag = long_to_bytes(int(i[0]))
    if b"CTF" in flag:
        print(flag)

b'CCTF{S!mP1E_A7t4cK_0n_SpEc1aL-5trucTur3D_RSA_pR1me5!}'