large case·

题目:https://paste.ubuntu.com/p/DcPKKSdT9y/

题目是个3-RSA,每个素数1024bits,即n=210243|n|=2^{1024*3}ee未知,但可以知道是p1p-1q1q-1r1r-1中各取一个因子做乘积(第一个assert);mmpad前的长度为21024<m<220482^{1024}<m<2^{2048}(第二个assert),mmpad后是m=210243|m|=2^{1024*3}(即与nn同量级,看pad函数);flag里含SUSCTF(第三个assert)。

首先要解决的是ee的求值,先假设ee的三个分量为:e=epeqere=e_pe_qe_r,假设epgp=p1e_pg_p=p-1,推一下可得:

e=epeqere=p1gpeqeregp=(p1)eqeregp0(modp1)cgpmepgpm01(modp)e = e_pe_qe_r \\ e = \frac{p-1}{g_p}e_qe_r \\ eg_p = (p-1)e_qe_r \\ eg_p \equiv 0 \pmod {p-1} \\ c^{g_p} \equiv m^{e_pg_p} \equiv m^0 \equiv 1 \pmod p

由于epe_pp1p-1的一个因子,那么就可以对于p1p-1的每一个因子pip_i,先计算gpig_{pi},然后检测cgpi(modp)c^{g_{p_i}} \pmod p是否为11,若是的话则ep=pie_p=p_i;当然,这样做的前提是p1p-1可以分解,事实也确实可以分解(但其实接下来的做法需要epe_p是个较小的值,所以不用完全分解也行);qqrr也是同样的操作,最终得出ep=757e_p=757eq=66553e_q=66553er=5156273e_r=5156273。(其实解eqe_qere_r时还有个22的,但因为算epe_p时没有出现22,且ee的三个分量都是素数,所以可以忽略,简单的逻辑推理-)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
fp = [2, 7, 757, 1709, 85015583, 149105250954771885483776047, 339028665499, 1642463892686572578602085475101104723805585678675707586553009837707279291648160744722745420570786735582631019452016654157586623543454908938807521637550223579103317696104438456966780396624343550451096013730928292041667133825444056448136643704677066463120079]
for fpi in fp:
if pow(cp, (p-1)//fpi, p) == 1:
print(fpi) # 757

fq = [2, 2, 3, 3, 66553, 84405986771, 81768440203, 38037107558208320033, 16137718604846030589135490851713, 14369576056311038198362075935199486201201115381094289671031774994452214307042971166730146897009438957078052300683916910041250723573953110349566216311685009675744215421971185909678546052934704709232060199286321405045769976194110037]
for fqi in fq:
if pow(cq, (q-1)//fqi, q) == 1:
print('fqi: %s' % fqi) # 2, 66553

fr = [2, 11607389, 5156273, 10012111, 68872137169799749, 12030248809636768339, 9691125310820433463, 31518759824860728158228953] # 547187028373506113438510511293209786101461141918516130626947626757753454448192055890412658699775890681515562519111190252566146302544199621791901997687741038739625529014337424946054655263007302018300326403871]
for fri in fr:
if pow(cr, (r-1)//fri, r) == 1:
print('fri: %s' % fri) # 2, 5156273

然后要解决的第二个问题是,gcd(e,φ(n))1gcd(e, \varphi(n)) \ne 1,即eeφ(n)\varphi(n)是不互素的,即不能使用通过求逆算出私钥dd的方法来解,之前做过Elgamal的话就知道是经典AMM解法了,类似的解法,先以pp作例子:由于AMM不能解太大的指数,所以要先降低指数的规模,由于e=epeqere=e_pe_qe_r中,只有epe_pp1p-1是不互素的,所以可以通过求mpmepc(eqer)1(modp1)(modp)m_p \equiv m^{e_p} \equiv c^{(e_qe_r)^{-1} \pmod {p-1}} \pmod p,把指数降到ep=757e_p=757qqrr同理。

虽然上一步是把指数降下来了,但是er=5156273e_r=5156273还是太大了(反正我电脑跑了半天都还没出- -),需要优化一下,刚好题目里mm的大小的条件还没用。看一下pad函数,是在message后面pad\x00,用公式来说就是mpad=mori21024m_{pad} = m_{ori} * 2^{1024},如果能把210242^{1024}去掉的话刚好就不需要rr的分量,也就不用管ere_r了;去掉的方法就是RSA的CCA攻击:

cmpade(mori21024)emorie(21024)e(modn)cc((21024)1)emorie(modn)c \equiv m_{pad}^{e} \equiv (m_{ori}*2^{1024})^e \equiv m_{ori}^e (2^{1024})^e \pmod {n} \\ c' \equiv c*((2^{1024})^{-1})^e \equiv m_{ori}^e \pmod {n}

另:这里”不需要rr的分量“的意思是,最后我是需要用CRT来合成mm的,如果只求了mpm_pmqm_q的话,只能知道mpad(modpq)m_{pad} \pmod {pq},回损失数据;但是如果我用cc'求的话,由于morim_{ori}pqpq小,则不会损失数据。

最终代码(AMM抄了Arpe1s的代码):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#sage
from Crypto.Util.number import *
import libnum
import random
import time

p = 127846753573603084140032502367311687577517286192893830888210505400863747960458410091624928485398237221748639465569360357083610343901195273740653100259873512668015324620239720302434418836556626441491996755736644886234427063508445212117628827393696641594389475794455769831224080974098671804484986257952189021223
q = 145855456487495382044171198958191111759614682359121667762539436558951453420409098978730659224765186993202647878416602503196995715156477020462357271957894750950465766809623184979464111968346235929375202282811814079958258215558862385475337911665725569669510022344713444067774094112542265293776098223712339100693
r = 165967627827619421909025667485886197280531070386062799707570138462960892786375448755168117226002965841166040777799690060003514218907279202146293715568618421507166624010447447835500614000601643150187327886055136468260391127675012777934049855029499330117864969171026445847229725440665179150874362143944727374907
n = p*q*r
c = 2832775557487418816663494645849097066925967799754895979829784499040437385450603537732862576495758207240632734290947928291961063611897822688909447511260639429367768479378599532712621774918733304857247099714044615691877995534173849302353620399896455615474093581673774297730056975663792651743809514320379189748228186812362112753688073161375690508818356712739795492736743994105438575736577194329751372142329306630950863097761601196849158280502041616545429586870751042908365507050717385205371671658706357669408813112610215766159761927196639404951251535622349916877296956767883165696947955379829079278948514755758174884809479690995427980775293393456403529481055942899970158049070109142310832516606657100119207595631431023336544432679282722485978175459551109374822024850128128796213791820270973849303929674648894135672365776376696816104314090776423931007123128977218361110636927878232444348690591774581974226318856099862175526133892
cp = c % p
cq = c % q
cr = c % r

ep = 757
eq = 66553
er = 5156273
e = ep*eq*er

L = 128

# AMM
def eth_root(x, e, p):
assert isPrime(p)
assert (p - 1) % e == 0
assert (p - 1) % (e**2) != 0

l = (p - 1) % (e**2) // e
a = -libnum.invmod(l, e) % e
return pow(x, (1 + a * (p - 1) // e) // e, p)

def findAllPRoot(p, e):
print("Start to find all the Primitive {:#x}th root of 1 modulo {}.".format(e, p))
start = time.time()
proot = set()
while len(proot) < e:
proot.add(pow(random.randint(2, p-1), (p-1)//e, p))
end = time.time()
print("Finished in {} seconds.".format(end - start))
return proot

def findAllSolutions(mp, proot, cp, p, e):
print("Start to find all the {:#x}th root of {} modulo {}.".format(e, cp, p))
start = time.time()
all_mp = set()
for root in proot:
mp2 = mp * root % p
#print('debug -> %d' % pow(root, e3, p))
assert(pow(mp2, e, p) == cp)
all_mp.add(mp2)
end = time.time()
print("Finished in {} seconds.".format(end - start))
return all_mp

pad = 1 << (L*8)
c = ( c * pow(libnum.invmod(pad, n), e, n) ) % n
cp = c % p
cq = c % q
cr = c % r

dqr = libnum.invmod(eq*er, p-1)
mpp = pow(cp, dqr, p) # m ^ ep % p
mp0 = eth_root(mpp, ep, p)
assert pow(mp0, ep, p) == mpp
proot = findAllPRoot(p, ep)
mps = findAllSolutions(mp0, proot, mpp, p, ep)
# cp = mp ^ e % p

dpr = libnum.invmod(ep*er, q-1)
mqq = pow(cq, dpr, q) # m ^ eq % q
mq0 = eth_root(mqq, eq, q)
assert pow(mq0, eq, q) == mqq
qroot = findAllPRoot(q, eq)
mqs = findAllSolutions(mq0, qroot, mqq, q, eq)
# cq = mq ^ e % q

for mp in mps:
for mq in mqs:
m = crt([int(mp), int(mq)], [p, q])
flag = libnum.n2s(int(m))
if b'SUSCTF' in flag:
print(flag)

(渣机跑了大概半小时- -)

InverseProblem·

题目:https://paste.ubuntu.com/p/fNYd2zZH6c/

题目挺短的,简单来看就是Ax=bAx=bxxflagAA是已知矩阵(gravity跑一次就出来了),bb已知(b.txt),正常来说求个逆就可以拿xx了,但是,看一下b.txt的话,bb是小数,输出是使用了科学计数法,有精度损失,所以问题转化为:Ax+e=bAx+e=bee未知,经典LWE问题。

解的时候要注意AAbb的元素都是小数,调LLL需要整数,所以需要乘上一个大的NN,然后取整,即转化为:NAx+Ne=Nb⌊NA⌋x + ⌊Ne⌋ = ⌊Nb⌋(大概这个意思,能看懂就好-)

最后代码(抄了之前博客写的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# sage
import numpy as np

NN = 2^100
b = [3.657060500339054556, 3.832239212422502419, 4.006400878420690219, 4.178419900792603698, 4.347228858757071634, 4.511847676148433948, 4.671407458110251127, 4.825167947918074560, 4.972528090932780174, 5.113029695817293714, 5.246354631948004226, 5.372316391653928349, 5.490847173300799113, 5.601981891814167511, 5.705840667157972348, 5.802611340293560716, 5.892533389518160902, 5.975884263745526823, 6.052968650055386206, 6.124110630374365201, 6.189648165161182760, 6.249928981118596312, 6.305306816020913629, 6.356137112146116124, 6.402771610768811570, 6.445551788138646998, 6.484801562386791147, 6.520820067831411961, 6.553875449515115861, 6.584200543535777115, 6.611991006926840555, 6.637406026122149569, 6.660571276935107790, 6.681583443270599219, 6.700515409542964562, 6.717421256877905762, 6.732340393774057929, 6.745300469406174670, 6.756319058650934721, 6.765404381911505425, 6.772555468921494821, 6.777762178159265432, 6.781005372262200126, 6.782257385537030814, 6.781482768722584069, 6.778639205835502253, 6.773678481496929180, 6.766547414782241958, 6.757188729437999655, 6.745541865153842309, 6.731543734407333659, 6.715129401333222177, 6.696232624726493441, 6.674786187460366591, 6.650721936401939729, 6.623970470419692447, 6.594460419709976122, 6.562117241643640000, 6.526861416758931682, 6.488605883801759546, 6.447252539940367342, 6.402687687915280321, 6.354776457871529374, 6.303356463148024886, 6.248231231031890047, 6.189164222318630664, 6.125874450187269531, 6.058034773416537746, 5.985273843207024811, 5.907182434535461653, 5.823324532363482149, 5.733253130130134423, 5.636530294391988036, 5.532750701442269019, 5.421567579447032585, 5.302719786604150158, 5.176058598538473916, 5.041572643016256734, 4.899409301857818377, 4.749890824218749685, 4.593523418788242338, 4.430997787892412703, 4.263179996640761260, 4.091092256773656004, 3.915884105025300528]
b = [int(NN * i * 1e+02) for i in b]
b = vector(ZZ, b)
n = len(b)

def gravity(n,d=0.25):
A=np.zeros([n,n])
for i in range(n):
for j in range(n):
A[i,j] = int( NN * (d/n*(d**2+((i-j)/n)**2)**(-1.5)) )
return A

A = gravity(n)
A = matrix(ZZ, A)
#Ai = A.inverse()
#print(Ai * b)

z = matrix(ZZ, [0 for _ in range(n)]).transpose()
beta = matrix(ZZ, [10])
T = block_matrix([[A, z], [matrix(b), beta]])


L = T.LLL()
print(L[0])
e = vector(ZZ, L[0][:n])
#print(e)

x = A.solve_right(b-e)
print(x)

m = ''.join(chr(i) for i in x)
print('m = %s' % m)

手速够快,有幸三血(

SpecialCurve3 (1/3)·

题目:https://paste.ubuntu.com/p/tSGwsxRVYx/

题目是一个魔改的椭圆曲线,解ECDLP问题,给了三种情况,最后只解了一种;论文都找到了,就是不会写代码(逃

首先恢复一下曲线(虽然恢复了还没用到),看problem函数里bb参数的选取可推曲线为:y2=ax2bx(modp)y^2 = ax^2 - bx \pmod p,还可以验算一下,add里面计算的tt大概率是斜率(参考正常的ECC加法),那么P1==P2情况下的tt就是通过求偏导得出的,验证一下曲线确实是y2=ax2bx(modp)y^2 = ax^2 - bx \pmod p,然后加法的结果好像是直线axty=bax-ty=b与直线y=txy=tx的交点。

然后分别算下三条曲线下的群阶,在@Csome的帮助下得出了k=0时群阶恒为p的结论,然后瞎试了一下,最终得出:e1的群阶是p1p-1e2的群阶是ppe3的群阶是p+1p+1

对应的三种情况其实(应该)就是这篇文章第四章里的三种情况:阶为p1p-1的话好像可以把群同态到Zp\mathbb{Z}_p^*上;阶为pp的话是Smart攻击;阶为p+1p+1的话好像是Supersingular的攻击,但这里的话p+1p+1刚好可以分解成一堆小素数,就可以Pohlig-Hellman求解。

前两个不会改代码,只搞了最后一个:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
from Crypto.Util.number import *
import hashlib
import random

class SpecialCurve:
def __init__(self,p,a,b):
self.p=p
self.a=a
self.b=b

def __str__(self):
return f'SpecialCurve({self.p},{self.a},{self.b})'

def add(self,P1,P2):
x1,y1=P1
x2,y2=P2
if x1==0:
return P2
elif x2==0:
return P1
elif x1==x2 and (y1+y2)%self.p==0:
return (0,0)
if P1==P2:
t=(2*self.a*x1-self.b)*inverse(2*y1,self.p)%self.p
else:
t=(y2-y1)*inverse(x2-x1,self.p)%self.p
x3=self.b*inverse(self.a-t**2,self.p)%self.p
y3=x3*t%self.p
return (x3,y3)

def mul(self,P,k):
assert k>=0
Q=(0,0)
while k>0:
if k%2:
k-=1
Q=self.add(P,Q)
else:
k//=2
P=self.add(P,P)
return Q

def p(self):
return self.p

curve3=SpecialCurve(52373730653143623993722188411805072409768054271090317191163373082830382186155222057388907031638565243831629283127812681929449631957644692314271061305360051,28655236915186704327844312279364325861102737672471191366040478446302230316126579253163690638394777612892597409996413924040027276002261574013341150279408716,42416029226399083779760024372262489355327595236815424404537477696856946194575702884812426801334149232783155054432357826688204061261064100317825443760789993)
G3=(15928930551986151950313548861530582114536854007449249930339281771205424453985946290830967245733880747219865184207937142979512907006835750179101295088805979, 29726385672383966862722624018664799344530038744596171136235079529609085682764414035677068447708040589338778102975312549905710028842378574272316925268724240)
Q3=(38121552296651560305666865284721153617113944344833289618523344614838728589487183141203437711082603199613749216407692351802119887009907921660398772094998382, 26933444836972639216676645467487306576059428042654421228626400416790420281717654664520663525738892984862698457685902674487454159311739553538883303065780163)
enc=4161358072766336252252471282975567407131586510079023869994510082082055094259455767245295677764252219353961906640516887754903722158044643700643524839069337

assert curve3.mul(G3, curve3.p+1) == (0, 0)
factors = [2, 2, 2663, 5039, 14759, 18803, 21803, 22271, 22307, 23879, 26699, 35923, 42727, 48989, 52697, 57773, 58129, 60527, 66877, 69739, 74363, 75869, 79579, 80489, 81043, 81049, 82531, 84509, 85009, 91571, 96739, 98711, 102481, 103357, 103981]

n = curve3.p+1
e3s = []
for pi in factors: # all primes
print(pi)
Gi = curve3.mul(G3, n//pi)
Qi = curve3.mul(Q3, n//pi)
for e3i in range(pi):
if curve3.mul(Gi, e3i) == Qi:
e3s.append(e3i)
break
else:
print('ERROR')
exit(-1)

e3 = crt(e3s, factors) % n
print(e3)

print(Q3 == curve3.mul(G3, e3))

补充·

原来是圆锥曲线不是椭圆曲线,难怪一直没找到(:

前两种情况都在这里有说了

https://www.jiamisoft.com/blog/4068-yuanzhuiquxianjiamisuanfa.html

总结·

菜(: