第二届长城杯CTF Crypto wp(partial)

2024-12-15

难度分布过于均匀，前半小时意气风发，后面六小时坐牢~~（还把脑子烧坏了.sage~~
Crypto上尚待学习探索的区域还有很多呐...

rsand

from Crypto.Util.number import getPrime, bytes_to_long
from random import randint
import os

FLAG = os.getenv("FLAG").encode()
flag1 = FLAG[:15]
flag2 = FLAG[15:]

def crypto1():
    p = getPrime(1024)
    q = getPrime(1024)
    n = p * q
    e = 0x10001
    x1=randint(0,2**11)
    y1=randint(0,2**114)
    x2=randint(0,2**11)
    y2=randint(0,2**514)
    hint1=x1*p+y1*q-0x114
    hint2=x2*p+y2*q-0x514
    c = pow(bytes_to_long(flag1), e, n)
    print(n)
    print(c)
    print(hint1)
    print(hint2)


def crypto2():
    p = getPrime(1024)
    q = getPrime(1024)
    n = p * q
    e = 0x10001
    hint = pow(514*p - 114*q, n - p - q, n)
    c = pow(bytes_to_long(flag2),e,n)
    print(n)
    print(c)
    print(hint)
print("==================================================================")
crypto1()
print("==================================================================")
crypto2()
print("==================================================================")

crypto1()函数产生了hint1和hint2。
注意到 \(x_1\) 、\(x_2\) 的值均不大，且若已知之，存在 \(gcd(x_2hint_1-x_1hint_2,n) == q\)
故可以爆破 \(x_1\)、\(x_2\) 的值来分解n，代码如下

from itertools import product
from Crypto.Util.number import *
from gmpy2 import gcd

n1=22717688782107854545906794591350792188387875110194655242509979558461609026689126410958538692592463401522362356541060680408895294904619968427918132940416290637253975078909557570052294696752131550575267463205417657973110741875406631276906289161580355184931848747568838733566664530108459688971836475286014292763710955427636743872406784553276648507633638199756885671818682171699361643329537983168846325911881270521846099654288267068313463192062464398908330416955834032336069159066966753411191707859856389748617142937092219735847967559900971260163275274768523333750643268027704717919118936153897897131289192675763387811013
c1=1558252460972099536711225051588554580318072299427314767703923796142958329478177837363654442346261739741092040593629411679066822482727491716985291081418724270921015825854190667916784526990039016012998579465839964466544193668482366443421030413848501164167083542684099820843740534553329803216858946383113948594174252707382307857234879302568335916655231823986006116032577877784092927461435642266714835802321330508070457299737128702295341171291240636594559140008577327543379170891332505804603999880161479252367891021732181686834465274026830438997961540000598683834926675711282575578551072028019741577061900406050342688458
h1=1785400845353189749482286289179481615877733122115008276512206537767234304427512467620804745559571677050458859357456035669730928744227986060695929592626894225264031471880622019995439974759232998264197998661247884396744524865844791270731263298403015254884799180837584748516933203206716038313235184449245118539673100116727208395667843647446216575
h2=4768290722045376113291539697751845492297828894506607687019886528688947365279933318542249148120591713377136829810253611016690765615542919031118840184459133618654100026395299998797995448105138246862328974800269378627003305498938807053253155312899666823211626587642773325777459110096832523197515520831587264132693167407988204540224314122959560422620710487922928480844859739608566274988519288343603058586422940803845283584074835988958761787309635325070293038864953194
e = 65537

h1 += 0x114
h2 += 0x514

for x1,x2 in product(range(2**11),repeat=2):
    if gcd(x1*h2-x2*h1,n1) != 1:
        q1 = gcd(x1*h2-x2*h1,n1)
        if q1==n1:
            continue
        p1 = n1 // q1
        print(p1,q1)
        d1 = int(pow(e,-1,(p1-1)*(q1-1)))
        print(long_to_bytes(int(pow(c1,d1,n1))))

#b'flag{3e5ef8ee-c823-'

crypto2函数中，\(hint \equiv (514p - 114q)^{n-p-q} (mod n)\)
根据欧拉函数性质显然有 \((514p - 114q)^{n-p-q+1} \equiv 1 (mod n)\)
进而，\(hint^{-1} \equiv 514p-114q (mod n)\) 又由于 \(514p-114q \in (0,n)\) 显然成立，故 \(hint^{-1}\) 就是其值将之与方程 \(n=pq\)联立即可分解 \(n\)

from Crypto.Util.number import *

n2=23301270370141612330143249564959167999228952608712168779005620502267285156915999431165077980542964295999346892411751982792106531064749859998324403553828150458489912004321705559850482154675511319849888703426512353277473602134376825692345016437768245466469519768372263929100926977019866358427404868365153401534717296761071322172550730839392284228315564674287251955446739867333680875136131197078701261161473605292835590020412488259675818419919656303024005482784483529585855459082494687375253068135930378498456710949935330943648377764301078025458819757637193359534111017671688548495903880663891480831184157816239626750043
c2=15154362247416833654874538866222303523564655502350143155042495279226934061117190464416559600114696199066594736043690897596945588720795487024161560079279635555757929743621207095425417248155771743585809715364339743613170559263801923828346132740396834092233104169833261587028257094105183142686581463164262368477202915768936279703753445661191665158883833492034478618553842878077641070131158366324287975018862012100924617592087104048825937530826657263770569129787378008786436051567330825371173569403780114839873592637937742553526185515371878434795312157292258810274451720036653523188513529132197471378811832009182418760448
h = 11574440934831556034723051057283542407332101344903394221647161034006584633702312851012881096546725183871843470306347168596589056621524160818188725619205790524384122606005486500598885295323033448984884291965912156280740846422438998271175595659299898234463882384160290793302007988149229773440712388994937267153031701764033364222504099057654985080539279285158866715715993693994617506028704652676563435164588466433989525485331944330416415023529660239650818869745957136675397467577768769303074091298570418559011249779965136728956550856369106784649405705908086276018004285287057080288901547467887280926775732587854691256048
h = int(pow(h,-1,n2))
e = 65537

h2 = h^2 + 4*114*514*n2

print(pow(h2,1/2))

q2 = int((pow(h2,1/2) - h) / (114 * 2))

p2 = n2 // q2
d2 = int(pow(e,-1,(p2-1)*(q2-1)))
print(long_to_bytes(int(pow(c2,d2,n2))))