Wp for AntCTF X D^3CTF's crypto

我的格子和椭圆曲线实在是太烂了，奈何这次比赛基本都是（

这次只贡献了1k分，我对不起V&N的师傅们呜呜呜

babyLattice

联合第二题，发现此题应该要分解n，观察秘钥生成代码，发现如下关系：

$$
a_1 = k \cdot n + a_{11} \cdot q \cdot inv(q,p) + a_{21} \cdot p \cdot inv(p,q)
$$
$$
a_2 = k \cdot n + a_{12} \cdot q \cdot inv(q,p) + a_{22} \cdot p \cdot inv(p,q)
$$

所以
$$
a_1 = a_{11} \pmod{p} = a_{21} \pmod{q}
$$
$$
a_2 = a_{12} \pmod{p} = a_{22} \pmod{q}
$$

所以易知
$$
b =\frac{a_{11}}{a_{12}}\pmod{p}=\frac{a_{21}}{a_{22}}\pmod{q}
$$

即

$$
b\cdot a_{12} - a_{11} = 0 \pmod{p}
$$
$$
b\cdot a_{22} - a_{21} = 0 \pmod{q}
$$

所以

$$
(b\cdot a_{12}-a_{11})(b\cdot a_{22}-a_{21})=0 \pmod{n}
$$

即

$$
b^2\cdot a_{12}\cdot a_{22} - b\cdot (a_{12}\cdot a_{21}+a_{11}\cdot a_{22}) + (a_{11}\cdot a_{21}) = 0 \pmod{n}
$$

我们选择构造格子
$$
{\begin{bmatrix}
1 & 0 & b^2 \\
0 & 1 & b \\
0 & 0 & n
\end{bmatrix}}
$$

LLL格基规约后再分解就能得到a_12、a_22、a_12和a_22，就可以恢复出A，关于中间的顺序，首先 $gcd(n,b\cdot a_{12}-a_{11})=p，gcd(n,b\cdot a_{22} - a_{21})=q$ ，然后反过头来用b检验，即可得到A

1
2
3
4
5
6
7
n=69804507328197961654128697510310109608046244030437362639637009184945533884294737870524186521509776189989451383438084507903660182212556466321058025788319193059894825570785105388123718921480698851551024108844782091117408753782599961943040695892323702361910107399806150571836786642746371968124465646209366215361
b=65473938578022920848984901484624361251869406821863616908777213906525858437236185832214198627510663632409869363143982594947164139220013904654196960829350642413348771918422220404777505345053202159200378935309593802916875681436442734667249049535670986673774487031873808527230023029662915806344014429627710399196
m = [[1,0,b**2],
[0,1,b],
[0,0,n]]
M = Matrix(ZZ,m)
print(M.LLL()

私钥拿到之后跑一遍decrypt函数就行

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
from hashlib import sha256

def decrypt(c, sk):
	a2 = crt([sk.A[0,1], sk.A[1,1]], [sk.p, sk.q])
	s1 = a2 * c % sk.p
	s2 = a2 * c % sk.q
	m, r = sk.A.solve_right(vector([s1, s2]))
	return m
SecretKey = namedtuple('SecretKey', ['p', 'q', 'A'])
n = 698045073281979616541286975103101096080462440304373626396370091849455338842947378705241865215097761899894513834380845079036601822125564663210580257883191930598948255707851053881237189214806988515510241088447820911174087537825999619430406958923237023619101073xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
b = 654739385780229208489849014846243612518694068218636169087772139065258584372361858322141986275106636324098693631439825949471641392200139046541969608293506424133487719184222204047775053450532021592003789353095938029168756814364427346672490495356709866737744870xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
c = 646663549384661940527205918107837690305665046534094651211733313626546652315738092349139857587250480713115715497774817768266247287420861746098971608971187502431927910215773481811303025721859117507974577939210694737300392259917557553409275067663952621259499393xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
a21 = 2078066511675xxxxxxxxxxxxxxxxx
a11 = 1017199123798xxxxxxxxxxxxxxxxxx
a12 = 1018979931854xxxxxxxxxxxxxxxxxx
a22 = 1151291153120xxxxxxxxxxxxxxxxxx
assert a21*a12+a11*a22 == 1382843159437215516163973075066558157591473xxxxxxxxxxxxxxxxxx
p = gcd(n,(b*a12-a11)%n)
q = gcd(n,(b*a22-a21)%n)
print(p,q)
assert p*q == n
a1 = crt([a11, a21], [p, q])
a2 = crt([a12, a22], [p, q])
assert b == a1 * inverse_mod(a2, n) % n
A = Matrix(ZZ, [[a11, a12], [a21, a22]])
SK = SecretKey(p, q, A)
m = decrypt(c, SK)
flag = 'd3ctf{%s}' % sha256(int(m).to_bytes(50, 'big')).hexdigest()
print(flag)

simpleGroup

发现给的n和babyLattice是一样的，直接把p和q抄过来，然后发现 $e\mid\varphi(n)$

每次加密有 $C = y^m \cdot r^e % n$ ，则 $C^{(phi/e)} = {(y^m)}^{(phi/e)} * r^phi = {(y^m)}^{(phi/e)} = {(y^{(phi/e)})}^m\pmod{n}$

即 $C^{(phi/e)} = {(y^{(phi/e)})}^m\pmod{n}$ ，因为 $m = M \pmod{e}$ ，显然 $m<e$ ，bsgs爆破得到mlist，返回去即可得到flag

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
from Crypto.Util.number import *
from gmpy2 import *

def BSGS(G,H,P):
    L1,L2 = [],[]
    N = iroot(1928983487,2)[0]+1
    for i in range(N+1):
        L1.append(pow(G,i,P))
    for i in range(N+1):
        tmp=H * inverse(pow(G,i*N,P),P) % P
        L2.append(tmp)
        if tmp in L1:
            a=L1.index(tmp)
            b=i
            return int(b*N+a)

n = 698045073281979616541286975103101096080462440304373626396370091849455338842947378705241865215097761899894513834380845079036601822125564663210580257883191930598948255707851053881237189214806988515510241088447820911174087537825999619430406958923237023619101073xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
y = 120648015457233473229369911867385603110490612355410315808075494222588141707717382622649304416707083082596945889632243725304983056485785205520380297738493422061250742129127888238341527857566977572098044750319744459636919415157569012683762673605426564496697153xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
e = 1928983487
p = 76690363131011946213452652559942001330069215655966537979569408116015163064102321200576xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
q = 91021224151656818244208716736217812503118228056187318636281925498956930242472205943728xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
phi = (p-1) * (q-1)
C = [63173987757788284988620600191109581820396865828379773315280703314093571300861961873159324234626635582246705378908610341772657840682572386153960342976445563045427986000105931341168525422286612417662391801508953619857648844420751306271090777865836201978470895906780036112804110135446130976275516908136806153488, 9763526786754236516067080717710975805995955013877681492195771779269768465872108434027813610978940562101906769209984501196515248675767910499405415921162131390513502065270491854965819776080041506584540996447044249409209699608342257964093713589580983775580171905489797513718769578177025063630080394722500351718, 37602000735227732258462226884765737048138920479521815995321941033382094711120810035265327876995207117707635304728511052367297062940325564085193593024741832905771507189762521426736369667607865137900432117426385504101413622851293642219573920971637080154905579082646915297543490131171875075081464735374022745371, 1072671768043618032698040622345664216689606325179075270470875647188092538287671951027561894188700732117175202207361845034630743422559130952899064461493359903596018309221581071025635286144053941851624510600383725195476917014535032481197737938329722082022363122585603600777143850326268988298415885565240343957, 27796821408982345007197248748277202310092789604135169328103109167649193262824176309353412519763498156841477483757818317945381469765077400076181689745139555466187324921460327576193198145058918081061285618767976454153221256648341316332169223400180283361166887912012807743326710962143011946929516083281306203120, 27578857139265869760149251280906035333246393024444009493717159606257881466594628022512140403127178174789296810502616834123420723261733024810610501421455454191654733275226507268803879479462533730695515454997186867769363797096196096976825300792616487723840475500246639213793315097434400920355043141319680299224, 29771574667682104634602808909981269404867338382394257360936831559517858873826664867201410081659799334286847985842898792091629138292008512383903137248343194156307703071975381090326280520578349920827357328925184297610245746674712939135025013001878893129144027068837197196517160934998930493581708256039240833145, 33576194603243117173665354646070700520263517823066685882273435337247665798346350495639466826097821472152582124503891668755684596123245873216775681469053052037610568862670212856073776960384038120245095140019195900547005026888186973915360493993404372991791346105083429461661784366706770467146420310246467262823, 5843375768465467361166168452576092245582688894123491517095586796557653258335684018047406320846455642101431751502161722135934408574660609773328141061123577914919960794180555848119813522996120885320995386856042271846703291295871836092712205058173403525430851695443361660808933971009396237274706384697230238104, 61258574367240969784057122450219123953816453759807167817741267194076389100252707986788076240792732730306129067314036402554937862139293741371969020708475839483175856346263848768229357814022084723576192520349994310793246498385086373753553311071932502861084141758640546428958475211765697766922596613007928849964, 13558124437758868592198924133563305430225927636261069774349770018130041045454468021737709434182703704611453555980636131119350668691330635012675418568518296882257236341035371057355328669188453984172750580977924222375208440790994249194313841200024395796760938258751149376135149958855550611392962977597279393428]

m = []
for i in range(len(C)):
    m.append(BSGS(pow(y,phi//e,n),pow(C[i],phi//e,n),n))
    print(m)

flag = 0
for i in range(len(m)):
    flag = flag + m[len(m)-1-i]
    flag *= e
flag //= e
print(long_to_bytes(flag))

AliceWantFlag

复现中，估计一周左右更新

EasyCurve

据说有非预期，学了佩尔方程然后回来更新