20211120-西湖论剑-CryptoSecPartWriteUp

Posted on Edited on In , Views: Symbols count in article: 11k Reading time ≈ 10 mins.

 

unknown_dsa

考点

先来看DSA部分

1
2
3
4
5
6
7
8
9
10
11
t = powmod(g, p*q-(p+q), p*q)

hm1 = bytes_to_long(SHA.new(m1).digest())
hm2 = bytes_to_long(SHA.new(m2).digest())

k = random.randint(1, q-1)
r1 = powmod(g, k, p) % q
s1 = (hm1 + x1*r1) * invert(k, q) % q
s2 = (hm2 + x1*r1) * invert(k, q) % q
r2 = powmod(g, x1, p) % q
s3 = (hm1 + x2*r2) * invert(k, q) % q

典型的复用$k$攻击，只需要知道$hm_1$和$hm_2$，就可以通过
$$
k(s_2-s_1)\equiv hm_2-hm_1\ (mod\ q)\notag
$$
求$k$，进而$x_1$和$x_2$自然不在话下

再来看main函数部分

1
2
3
4
5
6
for i in range(len(ul)):
    assert ul[i]**2 - wl[i] * vl[i]**2 == 1
e = 7
cl1 = [int(powmod(bytes_to_long(m1), e, x)) for x in ul]
cl2 = [int(powmod(bytes_to_long(m2), e, y)) for y in vl]
print(wl, cl1, cl2, sep=', ')

$$
x^2-ny^2=1\notag
$$

典型的佩尔方程，二元二次不定方程存在无穷解，所有的解可以由$\sqrt{n}$的连分数求出

直接穷搜就好了，看到之前春哥强网杯写的一个脚本，拿来改了一下

求出来$wl$和$vl$之后，用中国剩余定理扩大模数（因为e=7是在太小了，但又没有满足广播，so try一下

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
#!/usr/bin/env sage
# -*- coding: utf-8 -*-
from Crypto.Util.number import long_to_bytes, bytes_to_long
from Crypto.Hash import SHA
from gmpy2 import invert, iroot


def solve_pell(_wl):
    cf = continued_fraction(sqrt(_wl))
    conv = cf.convergents()
    for _ in conv:
        numer, denom = _.numerator(), _.denominator()
        if numer ^ 2 - _wl * denom ^ 2 == 1:
            return ZZ(numer), ZZ(denom)


# n = pq
n, p_1_q, t = 85198615386075607567070020969981777827671873654631200472078241980737834438897900146248840279191139156416537108399682874370629888207334506237040017838313558911275073904148451540255705818477581182866269413018263079858680221647341680762989080418039972704759003343616652475438155806858735982352930771244880990190318526933267455248913782297991685041187565140859, 106239950213206316301683907545763916336055243955706210944736472425965200103461421781804731678430116333702099777855279469137219165293725500887590280355973107580745212368937514070059991848948031718253804694621821734957604838125210951711527151265000736896607029198, 60132176395922896902518845244051065417143507550519860211077965501783315971109433544482411208238485135554065241864956361676878220342500208011089383751225437417049893725546176799417188875972677293680033005399883113531193705353404892141811493415079755456185858889801456386910892239869732805273879281094613329645326287205736614546311143635580051444446576104548
r1, s1, s2 = 498841194617327650445431051685964174399227739376, 376599166921876118994132185660203151983500670896, 187705159843973102963593151204361139335048329243
r2, s3 = 620827881415493136309071302986914844220776856282, 674735360250004315267988424435741132047607535029

q = 895513916279543445314258868563331268261201605181
p = 95139353880772104939870618145448234251031105153406565833029787299040378395002190438381537974853777890692924407167823818980082672873538133127131356810153012924025270883966172420658777903337576027105954119811495411149092960422055445121097259802686960288258399754185484307350305454788837702363971523085335074839
g = invert(t, n)

# ul^2 - wl * vl^2 = 1
wl = [3912956711, 4013184893, 3260747771]
cl1 = [
    2852589223779928796266540600421678790889067284911682578924216186052590393595645322161563386615512475256726384365091711034449682791268994623758937752874750918200961888997082477100811025721898720783666868623498246219677221106227660895519058631965055790709130207760704,
    21115849906180139656310664607458425637670520081983248258984166026222898753505008904136688820075720411004158264138659762101873588583686473388951744733936769732617279649797085152057880233721961,
    301899179092185964785847705166950181255677272294377823045011205035318463496682788289651177635341894308537787449148199583490117059526971759804426977947952721266880757177055335088777693134693713345640206540670123872210178680306100865355059146219281124303460105424]
cl2 = [
    148052450029409767056623510365366602228778431569288407577131980435074529632715014971133452626021226944632282479312378667353792117133452069972334169386837227285924011187035671874758901028719505163887789382835770664218045743465222788859258272826217869877607314144,
    1643631850318055151946938381389671039738824953272816402371095118047179758846703070931850238668262625444826564833452294807110544441537830199752050040697440948146092723713661125309994275256,
    10949587016016795940445976198460149258144635366996455598605244743540728764635947061037779912661207322820180541114179612916018317600403816027703391110922112311910900034442340387304006761589708943814396303183085858356961537279163175384848010568152485779372842]

n1 = []
n2 = []
for i in range(3):
    n1.append(solve_pell(wl[i])[0])
    n2.append(solve_pell(wl[i])[1])

c1 = crt(cl1, n1)
c2 = crt(cl2, n2)
assert iroot(c1, 7)[1]
m1 = long_to_bytes(iroot(c1, 7)[0])
m2 = long_to_bytes(iroot(c2, 7)[0])
hm1 = bytes_to_long(SHA.new(m1).digest())
hm2 = bytes_to_long(SHA.new(m2).digest())

# k * (s1 - s2) ≡ (H(m1) - H(m2)) mod q
k = (hm1 - hm2) * invert(s1 - s2, q) % q
x1 = (s1 * k - hm1) * invert(r1, q) % q
x2 = (s3 * k - hm1) * invert(r2, q) % q
print(long_to_bytes(x1) + long_to_bytes(x2))
1
DASCTF{f11bad18f529750fe52c56eed85d001b}

hardrsa

300分的hardrsa，然而却是原题（话说这次西湖论剑和2020羊城杯还是有几分相似，看最后一题Wiener就知道

这是2020羊城杯的Power（好家伙另外两道都复现偏偏这道没看

先贴exp（python跑太慢了，改成sage下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#!/usr/bin/env sage
# -*- coding: utf-8 -*-
from Crypto.Util.number import *

dp = 379476973158146550831004952747643994439940435656483772269013081580532539640189020020958796514224150837680366977747272291881285391919167077726836326564473
c = 57248258945927387673579467348106118747034381190703777861409527336272914559699490353325906672956273559867941402281438670652710909532261303394045079629146156340801932254839021574139943933451924062888426726353230757284582863993227592703323133265180414382062132580526658205716218046366247653881764658891315592607194355733209493239611216193118424602510964102026998674323685134796018596817393268106583737153516632969041693280725297929277751136040546830230533898514659714717213371619853137272515967067008805521051613107141555788516894223654851277785393355178114230929014037436770678131148140398384394716456450269539065009396311996040422853740049508500540281488171285233445744799680022307180452210793913614131646875949698079917313572873073033804639877699884489290120302696697425
c1 = 78100131461872285613426244322737502147219485108799130975202429638042859488136933783498210914335741940761656137516033926418975363734194661031678516857040723532055448695928820624094400481464950181126638456234669814982411270985650209245687765595483738876975572521276963149542659187680075917322308512163904423297381635532771690434016589132876171283596320435623376283425228536157726781524870348614983116408815088257609788517986810622505961538812889953185684256469540369809863103948326444090715161351198229163190130903661874631020304481842715086104243998808382859633753938512915886223513449238733721777977175430329717970940440862059204518224126792822912141479260791232312544748301412636222498841676742208390622353022668320809201312724936862167350709823581870722831329406359010293121019764160016316259432749291142448874259446854582307626758650151607770478334719317941727680935243820313144829826081955539778570565232935463201135110049861204432285060029237229518297291679114165265808862862827211193711159152992427133176177796045981572758903474465179346029811563765283254777813433339892058322013228964103304946743888213068397672540863260883314665492088793554775674610994639537263588276076992907735153702002001005383321442974097626786699895993544581572457476437853778794888945238622869401634353220344790419326516836146140706852577748364903349138246106379954647002557091131475669295997196484548199507335421499556985949139162639560622973283109342746186994609598854386966520638338999059
y = 449703347709287328982446812318870158230369688625894307953604074502413258045265502496365998383562119915565080518077360839705004058211784369656486678307007348691991136610142919372779782779111507129101110674559235388392082113417306002050124215904803026894400155194275424834577942500150410440057660679460918645357376095613079720172148302097893734034788458122333816759162605888879531594217661921547293164281934920669935417080156833072528358511807757748554348615957977663784762124746554638152693469580761002437793837094101338408017407251986116589240523625340964025531357446706263871843489143068620501020284421781243879675292060268876353250854369189182926055204229002568224846436918153245720514450234433170717311083868591477186061896282790880850797471658321324127334704438430354844770131980049668516350774939625369909869906362174015628078258039638111064842324979997867746404806457329528690722757322373158670827203350590809390932986616805533168714686834174965211242863201076482127152571774960580915318022303418111346406295217571564155573765371519749325922145875128395909112254242027512400564855444101325427710643212690768272048881411988830011985059218048684311349415764441760364762942692722834850287985399559042457470942580456516395188637916303814055777357738894264037988945951468416861647204658893837753361851667573185920779272635885127149348845064478121843462789367112698673780005436144393573832498203659056909233757206537514290993810628872250841862059672570704733990716282248839
g = 2
c1, g = Mod(c1, y), Mod(g, y)
# x = discrete_log(c1, g)
# print(x)
x = 43776275628859890575232443794319298551934804213472744927022818696759188901977390266973172755658396197421139420206549889337117978597883154859965236605452518446448639813055134133587564045471804447818058571586426895800984805588363855865218690877547419152765512143095217413477343835473963637692441032136163289964756172316289469159500312630529091350636808491697553069388388303341623047737553556123142002737059936569931163197364571478509576816349348146215101250803826590694039096063858424405382950769415272111843039715632655831594224288099608827345377164375927559338153505991404973888594356664393487249819589915881178770048740
# var('p')
# a = solve([2019 * p**2 + 2020 * p**3 + 2021 * p**4 - x == 0], [p])
# print(a)
p = 12131601165788024635030034921084070470053842112984866821070395281728468805072716002494427632757418621194662541766157553264889658892783635499016425528807741
m = pow(c, dp, p)
print(long_to_bytes(m))
1
DASCTF{98d923h4344e3bf72f8775xy65tvftv5}

为什么呢，主要也简单，因为$y$是光滑数，$y-1$可以被完全分解，所以才可以用签到离散对数的方法来求指数

image-20211121101501148

后面的话根据欧拉定理将模数转换到$p$上，因为
$$
dp\equiv d\ (mod\ p-1)\notag
$$

SpecialCurve2

没有a和b咋整？看Nu1l战队的WP复现

那边的师傅用PARI的工具来求解离散对数，sage还真是强大，可以外加这么多语言和工具，更多请看官网文档

https://www.osgeo.cn/sagemath/developer/coding_in_other.html

1
e = int(pari(f"znlog({int(y)},Mod({int(g)},{int(n)}))"))

不懂了

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
#!/usr/bin/env sage
# -*- coding: utf-8 -*-
from Crypto.Util.number import *


def add(P1, P2):
    x1, y1 = P1
    x2, y2 = P2
    x3 = (x1 * x2 - y1 * y2) % n
    y3 = (x1 * y2 + x2 * y1) % n
    return (x3, y3)


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


n = 92916331959725072239888159454032910975918656644816711315436128106147081837990823
C = (44449540438169324776115009805536158060439126505148790545560105884100348391877176,
     73284708680726118305136396988078557189299357177640330968917927635171441710392723)
g = 2
y = 1225348982571480649501200428324593233958863708041772597837722864848672736148168 ** 2 * 2 % n

# e = int(pari(f"znlog({int(y)},Mod({int(g)},{int(n)}))"))
e = 96564183954285580248216944343172776827819893296479821021220123492652817873253

print(pow(g, e, n))
print(y)

p1 = 425886199617876462796191899
p2 = 434321947632744071481092243
p3 = 502327221194518528553936039

assert p1 * p2 * p3 == n

phi = (p1 ** 2 - 1) * (p2 ** 2 - 1) * (p3 ** 2 - 1)

d = inverse(e, phi)

M = mul(C, d)
print(M)
print(long_to_bytes(M[0])+long_to_bytes(M[1]))

WienerStudyTwice

参考https://www.ctfer.vip/#/note/set/wp/51