MiniL_Crypto复现

Curvesignin Revenge

经典DH问题。感觉这种阶都能猜 or or

这里是N+1

具体证明如下

方程

$$x^2 + e*y^2 \equiv 1 \bmod N$$

可转化为

$$(x-d*yi)*(x+d*yi)\equiv 1 \bmod N$$

其中

$$d^2 \equiv e \bmod N$$

设

$$s=x+d*yi$$

显然，任意一个曲线上的点，都有一个s与之对应，即同态。

然后我们对计算，，发现

$$s^{N+1}=x_0^{N+1}+\sum_{k=1}^{N-1}x_{0}^{k}{N\choose k}(i\cdot d\cdot y_0)^{N-k} + (i\cdot d\cdot y_0)^{N+1}\equiv x_0^2+e\cdot y_0^2\equiv 1\bmod N$$

对于首项与尾项，对应任意a，都有

因此，阶为

分解

sage: factor(N+1)
2^2 * 7 * 877 * 2269 * 37967 * 184279 * 504877 * 845833 * 12308089 * 25153483 * 135503999 * 149848639 * 223321729 * 264522527

可得阶是光滑的，用离散对数求解即可

from sage.rings import integer_ring

Z = integer_ring.ZZ

def bsgs_alg(a, b, bounds):

    identity = Point(x = 1 , y = 0)
    lb, ub = bounds
    if lb < 0 or ub < lb:
        raise ValueError("bsgs() requires 0<=lb<=ub")

    ran = 1 + ub - lb   # the length of the interval
    # c = op(inverse(b), multiple(a, lb, operation=operation))
    c = add(mul(b , N), mul(a , lb))

    if ran < 30:    # use simple search for small ranges  
        d = c
        for i0 in range(ran):
            i = lb + i0
            if d == identity:        # identity == b^(-1)*a^i, so return i
                return Z(i)
            d = add(a, d)
        raise ValueError("No solution in bsgs()")

    m = ran.isqrt() + 1  # we need sqrt(ran) rounded up
    table = dict()       # will hold pairs (a^(lb+i),lb+i) for i in range(m)

    d = c
    for i0 in xsrange(m):
        i = lb + i0
        if d == identity:        # identity == b^(-1)*a^i, so return i
            return Z(i)
        table[d] = i
        d = add(d, a)

    c = add(c, mul(d , N))     # this is now a**(-m)
    d = identity
    for i in xsrange(m):
        j = table.get(d)
        if j is not None:  # then d == b*a**(-i*m) == a**j
            return Z(i * m + j)
        d = add(c, d)
    
    raise ValueError("Log of %s to the base %s does not exist in %s." % (b, a, bounds))

def discrete_log_new(a, base , ord=N + 1):
    try:
        f = factor(ord)
        f = list(f)
        # print(f)
        l = [0] * len(f)
        for i, (pi, ri) in enumerate(f):
            for j in range(ri):
                c = bsgs_alg(mul(base , (ord // pi)),
                            mul((add(a ,  mul(base , l[i]*(order-1)))) , (ord // pi**(j + 1))),
                            (0, pi))
                l[i] += c * (pi**j)
        from sage.arith.all import CRT_list
        print(l)
        return CRT_list(l, [pi**ri for pi, ri in f])
    except ValueError:
        raise ValueError("No discrete log of %s found to base %s" % (a, base))
    
Point = namedtuple("Point", "x y")    
N = 61820395509869592945047899644070363303060865412602815892951881829112472104091
e = 133422
G = Point(37234080987968345210046814543941568534026683208134935256498818666416936228347,23681207802011885401101067347527183297441941230486570817545706194562153385116)
A = Point(53887628258266977236946886765125225993985116834354341126233510219966071523616,28158965058787630555744590318664291139012897721840003355218563579301165856248)
B = Point(34916507512495859038246013669842835077935990837718819374050138139835873991114,17695334453582551266443068581568418621987401844207090836349323784243222912322)
bsk = discrete_log_new(B , G , N+1)
print(bsk)

（从仓库copy的代码，这里用了bsgs优化）

这个可以算是个通用脚本吧，定义下就好

具体原理看密码学——离散对数问题(DLP) - 先知社区 (aliyun.com)

最后crt即可

(应该是这样.jpg)

Ezfactor

from sympy import symbols
from sympy.solvers.diophantine import diop_solve
from Crypto.Util.number import long_to_bytes
from Crypto.Util.Padding import unpad
from Crypto.Cipher import AES

n = 1612520630363003059353142253089981533043311564255746310310940263864745479492015266264329953981958844235674179099410756219312942121244956701500870363219075525408783798007163550423573845701695879459236385567459569561236623909034945892869546441146006017614916909993115637827270568507869830024659905586004136946481048074461682125996261736024637375095977789425181258537482384460658359276300923155102288360474915802803118320144780824862629986882661190674127696656788827
e = 107851261855564315073903829182423950546788346138259394246439657948476619948171
high_p = (484571358830397929370234740984952703033447536470079158146615136255872598113610957918395761289775053764210538009624146851126  << 360)
c = bytes.fromhex("725039090b61b83a729d1e1061de62f0aae6b3c13aa601e2302b88393a910086497ccb4ef1e8d588a0fffe1e7b2ac46e")

R.<x> = PolynomialRing(Zmod(n), implementation='NTL')
f = high_p + x
x0 = f.small_roots(X = 2^361, beta = 0.4, epsilon=0.01)
p = high_p + x0
assert n % p == 0
q = n // p


x, y = symbols('x, y')

ssp = diop_solve(x**2 + e*y**2 - p)
ssq = diop_solve(x**2 + e*y**2 - q)
ans = set()
for sp, sq in zip(ssp, ssq):
    xp, yp = sp
    xq, yq = sq
    x1, x2 = abs(xp*xq + e*yp*yq), abs(xp*xq - e*yp*yq)
    y1, y2 = abs(xp*yq - xq*yp), abs(xp*yq + xq*yp)
    assert x1 ** 2 + e * y1 ** 2 == p*q
    assert x2 ** 2 + e * y2 ** 2 == p*q
    ans.add((x1, y1))
    ans.add((x2, y2))
(x1, y1), (x2, y2) = ans
key = long_to_bytes(x1 + x2 + y1 + y2)[:16]
iv = long_to_bytes((x1 ^ x2)+(y1 ^ y2))[:16]
cipher = AES.new(key, AES.MODE_CBC, iv)
print(unpad(cipher.decrypt(c), 16))

先是来一手coppersmith，调参有点麻烦。后面会讲coppersmith，不急

然后是解一个丢番图方程，用的模块，发现他在解方程前会分解n

我们手动求出 和的式子，然后再想办法和成n，肯定是这样没错的

然后就能发现欧拉给出的一个式子刚好是我们想要的

$$\alpha(apr\pm \beta q s)^2+a\beta(\alpha ps \mp bqr)^2=(a\alpha p^2+b\beta q^2)(abr^2+\alpha \beta s^2)$$

在我们这个式子中a=b=α=1，β=e

然后就可以得到

$$x=\left\vert x_px_q \pm ey_py_q \right\vert, y=\left\vert x_p*y_q \mp x_q*y_p \right\vert$$

然后带到AES里面就结了

mintirx

就没想过分解矩阵，之前actf有个题和这个太像了

方法为矩阵满秩分解

麻了，西电✌的线代怎么还讲了这玩意，你电专输麻了

shA = []
matA, matB, flag = load(r'/root/ctf/mintrix/output.sobj')
for i in range(4):
    m1 = matA[i].rref()
    m2 = matB[i].rref()
    B1.append(m1[:66,:99])
    A1.append(m1[:99,:66])
    B2.append(m2[:66,:99])
    A2.append(m2[:99,:66])
shA = []
for i in range(4):
    shA.append(((A1[i].transpose())*A2[i]*B2[i]*(B1[i].transpose())).det())
print(shA)  

Modular

先来一手预期解

直接看2023西湖论剑的的L的wp,https://l.xdsec.org/archives/397.htm。把他的脚本拿来改一下就行：

p =  164845988554803570034210932437537368454111382224593662888381752205097830374220032126019668095170780104196793308898619165077628440843625297811060080191510695127294662392565386869488665989314790417153155199484603115711496029502166530435242963549027629739137822533436875021838499822082806570509681528804270137211
rs = [11073785215399803853235061745025562471766281988061641769170576363313934679887217569801706599445660251521490126719635890179790621896844392956750809517990639, 12784423683616355098221440270623389347446777829352207702598822877935018742664765859424225840149743452815607228031166385525161497357580362090660087099463561, 7577732948268541787833560588485400689498904836182855054537116304468801803503701362142780756917159201619693280432140363109600711705084476590538898348091495, 10036538640393786727964860426918224804395694550532020220245239953525930433428030055698778916572386196731753524645673726564120152278880865190304242838501920, 10350368650118830326935007050127643692116265403962735788790668428564040409091749460517049732741049767368020817994528495057047372858538413379955184253035769, 13082554968320497009249783104283288691709656534267611249943658226578147441363459169752889315185021462154340729253550232757143969324177683836471761515296113, 11723150434377457341138045422253564051303981348922807490004982382654753129474768284517683118936761131376439630001542756355826193794438839584263048602040310, 2312593563786911571681233063720151667279804480769620841211384417877924447027383126968652725221072664250609182525144659105664559685824277385834372886285094, 8049485076552016296159857980961344802126929658650665671825539449229142359019667254159718901978033859414007639521459856787506712053910501662601618610514914, 12822523655335498062846821483569187428698965071054245766972798473300669853079078505565238968193164176053130900424396330887238266290091854068639522572449339, 1988079154144136979677332642795216452632297338094750910617093873182523143339869438995891613910990545752839876846627284570472460679615904755635544112116092, 9194005022626331512379119874845502249344166649769798000933209476153024446423815364991330602243774497089790879352599144546648334988413603137287141470786227, 11727206829831450157203317046245035552298279328303831066317871736717278323280297412293674926381591364506598009757202174628385178306540269839380835605774245, 11215884114131863628931482493525076575449310680468928386799247991075129949742646459804819103409234048309002257507655620363713887571426410650360692900914699, 13229252051259887566909445786745289385337948372770305233565261009723186917196139796699867121485348607425821132607169548715417088553975822119578238895523265, 2434133230340215157166799626659846713913609778121753977290859118021406007835503746444795101542893453323303681652821047182210814815480500209549189261212091]
ds = [127689167482288014000425602448716351832061686812439342522706528519984932610953307949977350023021888687983251179153954114903130408334900302125917604314161605704555174302412954096635321614161214385582921381486515033274321858036598915744458540554641638486064496964212510591699130814604388251826605946884931609239, 56413040451215992468023998497689962423937259634730422435837574010842048007293695901884911359124444138173478449239034017088644337562220927468594721047524149961827124075147838400693750768945802932499189371097807548365894469129746580626236019137090009004220729941666144085424522735838394947258817989463046580083, 159096117503489718963992325680213552682830013716063476625015908241930978596419248762838492502713441290032524915163962289091138236114604143819360187403692143046854081221922184032793094745439121739937527053820166175718197141255384894581172929886611605237834758037034390281470190860024729504992421640301133083404, 148614330434083992178131965309280278458335893214841048516035856106213897958541973680637125288066896832409976839772740287748661345292024159485776320225956338647921725106379463224642461406265568922245631807144160289351197425214555754580233288475579979258758527061759197292322910306030807023192166185587921285671, 123345966798742829864063791304200566491120706593219158548382987040598862749861728657659502537047580298796463849444588459425801502067157624710064438370936408393253024836355432534385142463869549691987813313361098037942855131514209362841779839493625734946204159916085515497669218464956693057910996989418368224718, 143730572425993961234876793125643776784767574870493801394069361432939095891758175702481539677359617673034631044084638831967344534252877445924666622233969641174369690202553271751772918142543732283676883488826667008492638895690040854698522971159686315980188834562253564620383944905979625152892744587185914741619, 1899333675825489355648956982427596214776139771238039023541139046760215434943108710292661083292292953429117286234729966131691913785686567736252854362355954922873970819020441817967086919426033302536398011099152039375012125999540633921013012116333257553654574739476224062806921065018986994063829525027823407648, 40021946460891456694763667739829844641491219915874879792778254614695339805691219947475184567199479881579252472064910345853968456976632175231245612205653295824088485229980359745332624808591401283855146511631022408273586520877407674644614613998690455052346136191115393887831117621257895456840650358274704555826, 12587255965576618872424846983892765361571446840329606167872576672371962359763011155165681721852152650809792269562777388435588015401100477502385787955972250368547408410489592248270305167054993487526965497026997328059292719829447657379952511915845044662968837407738496706780296294079791108598328537710381157919, 35373123117894082903769877421701955286540504796790597579883645896246184957279758828485780634720987127549717035820445126876568629689752869185045633419105196626182281116564659179017183846877215180869022831602437473904695745472745901533685175353016286208073998879110512700881415857098355556619716927272875712543, 134932924556053419947479552023990513361719644723460306853893813536315826606671396974575808371962061681863431171645460950240068835345485082055042507057318484642248377464012190169846843382519054758782949721704286454756070440219919539517396121347211156022973464793745891250380424466962047539290876180276174954017, 27899997727957090644819589789584825770425643969528465008806641542434382954966398613498974641857103683569692073706544870428810334295672590103909799629869694715078979935157432679153773828133621666694959818824171709239244599243012260821032040518358082030953828035117001054087875399613540555646765816048615539771, 7990260348729651065061774330514759509564837031091710787389017717183671432285163356986386067690017705747754893027235277280940946101800970816540560960119674128607348218440305393345959072544795513286812841410488767361374115717105992844205502565330711799795306905954106878365241897255454156656558563160409751399, 27068508791948756691803985700118866000386053120093908814487276298724757390487696031090900109841931605137365394815754358395620936879082992913896989240280854388738478132736076967155970572855435930485296183348479074877371237239722477255173805754299750182013036348100323337537900501322375563232654474595361640515, 13068380881558918013590945724589640458561504299404063853219448769281966209348511384884736841017603963103299381103791221248018581424389899807981567417759391600600984972983942688701208630779299513897011464626036238552507148124206493947096118137357598103691906343263150876734284019870558697515292943970868900740, 144432759930368947380264594980501091338004849606824563808700906729893535126944352004834658811698724817007929870819639919440203958980489826241756941893529760770624315120979622281316834874867192315134768359044211887340768352160881022324364858511458276652532183301934534104684508521052564120793282785818867643234]
r0, d0 = rs[0], ds[0]

def get_coef(r0,d0,r1,d1):
    PR.<t0,t1> = PolynomialRing(Zmod(p))
    f = (d1+t1-d0-t0)-(r0-r1)*(d0+t0)*(d1+t1)
    return [int(i) for i in  f.coefficients()]

times = 15
aas = []
bbs = []
ccs = []
dds = []
for _ in range(times):
    a,b,c,d = get_coef(r0,d0,rs[1+_],ds[_+1])
    aas.append(a)
    bbs.append(b)
    ccs.append(c)
    dds.append(d)
M = Matrix(ZZ,3*times+2,3*times+2)
for _ in range(times):
    M[_,_] = aas[_]
    M[times,_] = bbs[_]
    M[times+1+_,_] = ccs[_]
    M[times*2+1,_] = dds[_]
    M[times*2+2+_,_] = p

for _ in range(2*times+2):
    M[_,_+times] = 1


bounds = [2^1024 for _ in range(times)] + [2^1024 // 2^(328*2) for _ in range(times)] + [2^1024 // 2^328 for _ in range(times + 1)] + [2 ^ 1023]
Q = diagonal_matrix(bounds)

A = M

A *= Q
A = A.LLL()
A /= Q


for row in range(3*times+2):
    if A[row][:times] != 0: continue
    if A[row][-1] < 0: A[row] = -A[row]
    if min(A[row][times:]) < 0: continue
    # print(A[row][times:][times:])
    t0 = A[row][times:][times:][0]
print(d0+t0)

需要注意的是，他的inverse_mod不知道出了什么问题（个人猜测是sagemath版本的问题）无法正常运行，所以使用pycryptodome里面的inverse

from Crypto.Util.number import inverse, long_to_bytes
p = 164845988554803570034210932437537368454111382224593662888381752205097830374220032126019668095170780104196793308898619165077628440843625297811060080191510695127294662392565386869488665989314790417153155199484603115711496029502166530435242963549027629739137822533436875021838499822082806570509681528804270137211
r0 = 11073785215399803853235061745025562471766281988061641769170576363313934679887217569801706599445660251521490126719635890179790621896844392956750809517990639
d0 = 127689167482288014000425602448716351832061686812439342522706528519984932610953307949977350023021888687983251179153954114903130408334900302125917604314161605704555174302412954096635321614161214385582921381486515033274321858036598915744458540554641638486064496964212510591699130814604388251826605946884931609239

t = 127689167482288014000425602448716351832061686812439342522706528519984932610953307949977350023021888687983251179153954114903130408334900302125917604314161605704555174302412954096635321614161214385582921381486515154410082314483014224958234763808497260546658621973031798202444255716772714345095556050617999087155
print("s = ", inverse(t, p) - r0)

@得到s之后直接解就行

from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes
from Crypto.Util.Padding import unpad
s = 9248940038040839057598632265764855803828614592033151220667438062454710430448514351740132586277363244788388587249049064222965708602595485072348985210053249
c = bytes.fromhex("94cec3dc63fba1e8383852d852468d25ed7a2e05b4006d6162c3fcd4bef2565a")
key = sha256(long_to_bytes(s)).digest()[:16]
iv = bytes.fromhex("27d72ebeda75d7dc922c928f151d2db0")
cipher = AES.new(key, AES.MODE_CBC, iv)
print(unpad(cipher.decrypt(c), 16))

b’miniLCTF{3njoy_th3_Lattic3}’

（我是脚本小子.jpg）

具体参考| 独奏の小屋 (hasegawaazusa.github.io)

再来一手非预期解，from 0x：https://zatqldvi7bs.feishu.cn/docx/TMxGdv8meoISRBxhkOrcZCvunUJ

分析核心加密式

h = [(inverse(s + t[i], p) - e[i]) % p for i in range(n)]

可得

$$h_{i} = ( s + t_i)^{-1}-e_i \ (mod \ p) \\ (h_i + e_i)*(s+t_i) = 1\ ( mod \ p )\\ h_i*t_i+t_i*e_i+h_i*s+e_i*s=1\ (mod \ p)\\ h_i*t_i+t_i*e_i+h_i*s = 1-e_i*s \ (mod\ p)$$

下面分析一下大小：

• 手动算一下h的长度是1024bit左右
• t是500bit多
• p是1024bit
• e是小于300bit

右边显然是负的，但是不模p的话还是很小的

所以我们可以构造格子

$$\left(k_1 , k_2,k_3\dots k_n,e_i,s,1 \right) \left( \begin{array}{c} p & & & & 0 & 0\\ & p & & & 0 & 0\\ & & p & & 0 & 0\\ & & & p \\ t_1 & t_2 & t_3\dots& t_n\\ h_1 & h_2 & h_3 \dots &h_n & 1\\ h_1t_1 & h_2 t_2 & h_3t_3 \dots & h_nt_n &0 & 2^{1024} \end{array}\right)$$

然后把这个规约，找到最后一维是$2^{1024}$的向量,$v[-2]$就是s

Sums

摸！—-