ctfplus-Crypto study

极客大挑战 2023-Crypto-SimpleRSA

这题很友好，提供 hint，说是m<p，然后我们能通过欧拉定理，将和 n 相关的 rsa 退化到和 p 相关即可，而且这里m<p，后面可以在mod p中直接拿到 m，下面是我的手写过程

‍

然后我手搓的 sage exp

from Crypto.Util.number import long_to_bytes
p=24724324630507415330944861660078769085865178656494256140070836181271808964994457686409910764936630391300708451701526900994412268365698217113884698394658886249353179639767806926527103624836198494439742123128823109527320850165486500517304731554371680236789357527395416607541627295126502440202040826686102479225702795427693781581584928770373613126894936500089282093366117940069743670997994742595407158340397268147325612840109162997306902492023078425623839297511182053658542877738887677835528624045235391227122453939459585542485427063193993069301141720316104612551340923656979591045138487394366671477460626997125944456537
c=510345661718450375632304764819724223824018609359964259503762283253350010161515190912152623604019093266967095847334388281390406831587663253164256543905694021952211220652820225527413861208452760215767828927039893435528572148282529198773772864255061213208279999011194952146362748485103032149806538140693537361755210176698895104708379400806511907719904867068865970241208806615061055047254026118016836750283966478103987375361826198930529462261013324904522014804502582865716441828895047550041401172127129749969507853355531197814919603963664646220505672302543085959372679395717892060245461464861507164276442140407308832537707450729432224150754603518526288767105682399190438680085925078051459448618725871249563011864525585870188123725554411655044152994826056900502298772802133526591794328224932405680583757307064395792317383571866619582974377344736930271554160701478385763426091091686496788999588340419226785217028504684542197970387916262126278955278523452903043316452825738030645100271595942652498852506660789605846309602343932245435421425673058238785509280366229754404949219663043627431437755087855502139890639468481922788973821783957766433857773771229298328019250652625289700950165414584983487319078090573179470893450632419467111117341472
e=65537

d_p=pow(e,-1,p-1)
m=pow(c,d_p,p)
flag=long_to_bytes(m).decode()
print(flag)
"""
❯ sage exp.sage
SYC{Just_a_s1mple_modular_equation}
"""

RSA?

这题还行，之前做过，考察的小 e 攻击，核心思路就是，正常加密逻辑是c=m^e (mod n)​但是呢，如果 e 足够小，我们可以得出这样的结论m^e < n,这样子就会导致压根没有进行 mod 取余运算，最后的密文 c 实质上就是 m^e，接下来对 c 进行开 e 次方即可，本题更简化了点，都不用开方

from Crypto.Util.number import long_to_bytes
N=0x180be86dc898a3c3a710e52b31de460f8f350610bf63e6b2203c08fddad44601d96eb454a34dab7684589bc32b19eb27cffff8c07179e349ddb62898ae896f8c681796052ae1598bd41f35491175c9b60ae2260d0d4ebac05b4b6f2677a7609c2fe6194fe7b63841cec632e3a2f55d0cb09df08eacea34394ad473577dea5131552b0b30efac31c59087bfe603d2b13bed7d14967bfd489157aa01b14b4e1bd08d9b92ec0c319aeb8fedd535c56770aac95247d116d59cae2f99c3b51f43093fd39c10f93830c1ece75ee37e5fcdc5b174052eccadcadeda2f1b3a4a87184041d5c1a6a0b2eeaa3c3a1227bc27e130e67ac397b375ffe7c873e9b1c649812edcd

e=0x1

c=0x4963654354467b66616c6c735f61706172745f736f5f656173696c795f616e645f7265617373656d626c65645f736f5f63727564656c797d
flag=long_to_bytes(c)
print(flag)
"""
sage ❯ sage exp.sage
b'IceCTF{falls_apart_so_easily_and_reassembled_so_crudely}'
"""

芸翎

这题稍微麻烦的地方感觉就是过 pow 验证以及那个字节序的问题

先审计各个部分代码

def proof_of_work() -> bool:
    s = ''.join(random.choice(string.ascii_letters+string.digits) for _ in range(32))
    print(f'[+] sha256(XXXX+{s[4:]}) == {sha256(s.encode()).hexdigest()}')
    if input(f'[-] Give me XXXX:') == s[:4]:
        return True
    else:
        return False

这里的 proof 证明，我们需要爆破 4 个字母，字符集就是小写字母以及数字

import hashlib
import itertools
import string

suffix = "aL1cmRVrWIpmAhLX8kkxgkpbo3M2"
target = "c59db0ad02316c69d7de1770b665b64d4f6c75d8d68bbf4a0423d61c52a70d64"
charset = string.ascii_letters + string.digits
found = False
for prefix in itertools.product(charset, repeat=4):
    xxxx = "".join(prefix)
    test_str = xxxx + suffix
    if hashlib.sha256(test_str.encode()).hexdigest() == target:
        print(f"found it:{xxxx}")
        found = True
        break
if not found:
    print("wrong!")

接下来再没啥了，看看后面的 RSA 部分

n = getPrime(2025)
e = 65537

m = int.from_bytes(flag.encode() + urandom(253 - len(flag)))
c = pow(m,e,n).to_bytes(254,'little').hex()

已知信息是 n,e,c

看到这里的 n 是一个大素数，就可以乐了，因为在模素数域上，欧拉函数的值就是素数 -1 ===> phi_n=n-1

接下来可以直接进行常规 RSA 解密了

但是我们细节需要仔细处理下，主要看这两部分

m = int.from_bytes(flag.encode() + urandom(253 - len(flag)))
c = pow(m,e,n).to_bytes(254,'little').hex()

m 构造：flag+随机字符(共 253)->int

c 构造: c -> bytes(填充 254 字节并且还是小端序) -> hex

恢复的时候反着来即可

n = 3334238353417369553492493263305683989530104920568141521626372780553337473257562963291245235143126583568295517268530659512996903152143094702199443201597335684279710693148949132513104140310059039763775349771452223387234495290781859567883284259712321178311242618464869791318613297550346965425222969072695370023247828590900471609084485200266681676753044509241366959792988805505262758289743817259346667025420869129680655423561063652202928727595918835762311003216180805175291790069366884871585535427379159938872075228185752422649431403488107263086469662669439386546754771307420089047921364696207611844181428214995301
phi_n = n - 1
e = 65537
d = inverse_mod(e, phi_n)
c = "620b80d7ac33a32bba19de1220a3462def0b12c07ee1577c9d7422390f0a63b166a4186159186aa722d301c444ceb9d23f10d58c28918a929383b3e52131b8a963c72aea0018550cf496d01948d80ab9baf79e06db4fb350180aa8c00f2a93dc4c8a3c5d85369f9ae62c07071a60528994a78b09eafad188991dd8dac08ab2f3ed95f15045e14e62a93506ef31470e9bc4027e33c4b4b136217b40cdd3c916f8514e98e3d4ddefb9e3a105fde38a6833021b5c5e7c8e853cf98f0e88fd122b6eff9ec9ea0072c005b3e71f41721523970089caaddb33a732d779581f2541800087cbcf81fa3bdb5145769bb5167117c7657708a91a87fdb7a8be676f7d01"
c_bytes = bytes.fromhex(c)
c = int.from_bytes(c_bytes, "little")
m = pow(c, d, n)
m_bytes = m.to_bytes(253, "big")
print(m_bytes)
"""
b'0xGame{cd050bb6-f827-432b-bd95-5bb463cbfe5c}\xbeF\xf2c\xcc\x10\x0e\xd9 \x8f\x18=\xe6o\xa1\xf0\x01\x86\xf2\xfe\x1e]\xa1;\x1e\x8e\xe3\x91\xa1~\x92\x0c\xd9M\xc6\xc3\xbc\x16_b\x96b]D"\xccn\xbb\xcc\xedTT@\\\xb0\xe8v\xb8g\x88\xf4}+Q9th\xbe\xc3\x9cX\xa6O\x9f\x99\xf8\x14\xe0\xcc\xc4(j.\x89\x03\xcb\xda\xbc\x98\xfe\xbd:\xa8\xe5@\x11\xfdz\xfa\xae\x1aG\x96\xc6u\xed\xb4G\x145T\xff)\xd0\xdc\xd0\r\xcf\xa0\xa6\x7f\x18\xe9\xfc\xef\x18\x0c\xb5\xc8k\x93\x13AR\xf0N P\x8a\xe1\xc5B\xd3Q5\x80\xf5*\xa8E\xc3\xc9O\xb8%\x89P!\xca\xdc\xb7\x8cL\xbb\x0b\xa9x\xf8\x02\x93{\x12\xfb]\xc6\x1cEr\xfd\xe6\xcdc\xf6\xb9\t\xa1y\xbc\x02\xce\xbdx\x80\x1c+$\xea\xda;\xbbz\xfbF\x03\xe3\x7f\xfb=\xa3'
"""

babyrsa

回顾了下前面学习的共 e 攻击

脚本难度不大

from Crypto.Util.number import long_to_bytes
n=20116181115185256137151544962617461969127485079539874123483790179691451026659727409952002522890170053136432251484598758202749921581090222404128778286934496528266389586853622784941814905724374659722595150921699219297623333597701057604954651692729250881800409786303147914726282180533059864870515367790648247781809163302813093152120079755029826297153011886828297246071460547641705486357297417233767122432498694486964352342801912061641754894572829465334992075139630449930115173945624459850685926333265959551792326024379566586598102224813413893610109613076229994854338779713676554568790353735720642800095499489845542499243
c1=12574615186232508658058781239986357997690221455470707882708919538344867889046756940392586425215083828833917124513057649780713973391884806015516720789553246206689136824212927709627728801288304629797527956697243414600762350309939098109707454770146886759387428373061131102235552303687641823437812335805429238591967849935403611629054866383093303269886760991083623181420555220699498615783586898665752705379697907365417049724321589193519522361497873285356095894318360385694468646045503420079559869794438944147268173957051158766280963203638656844473553699835099487100606197891044561669390594778573658401240732422863142027023
c2=8662571349644155432847824828393121776098409938437916669251107156874603954233944520039184762114790042807930511195272715449923236367967421315595229284040395158368328305331059953339506075385510377512416235056474493145376149687125036012499178684540639274797034307771820863938251633851132423882652884158338847776108707048056678532767030904154141724336547346190841924329986431350894721191694788035732072169271856487733779585742838903331792853668246043440328934976370767441620664696662437609635592559825455438053522844176591659902503216608366261175995953153271651775486985191394510128456927543378761783994086684673696547021
e1=65537
e2=2333

g,a,b=xgcd(e1,e2)

m=pow(c1,a,n)*pow(c2,b,n)%n
flag=long_to_bytes(m)
print(flag)
#b'FZNCTF{D0_U_kn0w_c0mm0n_m0du1u5_4tt4ck?}'

Ez_LLL

初步接触到了格密码，以及怎么利用 LLL 工具

(暂时没学会怎么写 latex 公式，就先手写吧

通过整理，可以拿到一组合适的基底，接下来进行 LLL 格约，可以获取 flag

from Crypto.Util.number import long_to_bytes
flag=fgc73f-08e0038l{25-94d5-c917a4147bl-60999}
p=151240196317566398919874094060690044886978001146739221635377812709640347441550250665168046149125216617951660209690860015625296899030453965800801283336223544189902980591153121592938172963303968803995733283426759581586368403208379337416298836517168491618212440911971420911495272791409112867645195821357346746831
h=124332746104765845147133491132959579184849644379099440465281812273660434050281263409975356196112560300248343107170084466976976410232928660489912629913525776979726428263975968343564076005019264661696777686114079504603568726429498116488469855127100166072195548037981863885014261706582936943023968781022607949646
M=Matrix(ZZ,[
    [1,h],
    [0,p]
])
L=M.LLL()
for i in range(L.nrows()):
    row=L[i]
    f_cand=abs(row[0])
    g_cand=abs(row[1])

    if (h*f_cand)%p==g_cand:
        print("found it!")
        print(f"g={g_cand}")
        print(f"f={f_cand}")

        try:
            flag=long_to_bytes(f_cand)
            print(flag)
        except:
            print("wrong")
"""
found it!
g=1484517451146479608051498281959475985712181649166711824444146519294528225188375398525971613043100392820791
f=1736961079362765316112377548696163295061018206456282547411229082355380624547015399206899287823574604800893
b'0xGame{8dc1f4b8-3f4e-4c3e-9d1a-2b5e6f7a8b9c}'
"""

极客大挑战 2023-Crypto-PolyRSA

这题给的信息确实稍微复杂了点，大致说说思路，通过 c1,c2，我能拿到一个一定是 p 或 q 的倍数 k，然后用 gcd 处理，就能拿到一个确定的 p 或 q，下面是我的思路和脚本

sage 脚本如下：

e1= 113717
e2= 80737
c1= 97528398828294138945371018405777243725957112272614466238005409057342884425132214761228537249844134865481148636534134025535106624840957740753950100180978607132333109806554009969378392835952544552269685553539656827070349532458156758965322477969141073720173165958341043159560928836304172136610929023123638981560836183245954461041167802574206323129671965436040047358250847178930436773249800969192016749684095882580749559014647942135761757750292281205876241566597813517452803933496218995755905344070203047797893640399372627351254542342772576533524820435965479881620338366838326652599102311019884528903481310690767832417584600334987458835108576322111553947045733143836419313427495888019352323209000292825566986863770366023326755116931788018138432898323148059980463407567431417724940484236335082696026821105627826117901730695680967455710434307270501190258033004471156993017301443803372029004817834317756597444195146024630164820841200575179112295902020141040090350486764038633257871003899386340004440642516190842086462237559715130631205046041819931656962904630367121414263911179041905140516402771368603623318492074423223885367923228718341206283572152570049573607906130786276734660847733952210105659707746969830132429975090175091281363770357
c2= 353128571201645377052005694809874806643786163076931670184196149901625274899734977100920488129375537186771931435883114557320913415191396857882995726660784707377672210953334914418470453787964899846194872721616628198368241044602144880543115393715025896206210152190007408112767478800650578941849344868081146624444817544806046188600685873402369145450593575618922226415069043442295774369567389939040265656574664538667552522329712111984168798829635080641332045614585247317991581514218486004191829362787750803153463482021229058714990823658655863245025037102127138472397462755776598314247771125981017814912049441827643898478473451005083533693951329544115861795587564408860828213753948427321483082041546722974666875065831843384005041800692983406353922680299538080900818930589336142421748023025830846906503542594380663429947801329079870530727382679634952272644949425079242992486832995962516376820051495641486546631849426876810933393153871774796182078367277299340503872124124714036499367887886486264658590613431293656417255355575602576047502506125375605713228912611320198066713358654181533335650785578352716562937038768171269136647529849805172492594142026261051266577821582011917001752590659862613307646536049830151262848916867223615064832279222
c= 375617816311787295279632219241669262704366237192565344884527300748210925539528834207344757670998995567820735715933908541800125317082581328287816628816752542104514363629022246620070560324071543077301256917337165566677142545053272381990573611757629429857842709092285442319141751484248315990593292618113678910350875156232952525787082482638460259354559904243062546518553607882194808191571131590524874275187750985821420412987586148770397073003186510357920710387377990379862185266175190503647626248057084923516190642292152259727446111686043531725993433395002330208067534104745851308178560234372373476331387737629284961288204368572750848248186692623500372605736825205759172773503283282321274793846281079650686871355211691681512637459986684769598186821524093789286661348936784712071312135814683041839882338235290487868969391040389837253093468883093296547473466050960563347060307256735803099039921213839491129726807647623542881247210251994139130146519265086673883077644185971830004165931626986486648581644383717994174627681147696341976767364316172091139507445131410662391699728189797082878876950386933926807186382619331901457205957462337191923354433435013338037399565519987793880572723211669459895193009710035003369626116024630678400746946356
n= 728002565949733279371529990942440022467681592757835980552797682116929657292509059813629423038094227544032071413317330087468458736175902373398210691802243764786251764982802000867437756347830992118278032311046807282193498960587170291978547754942295932606784354258945168927044376692224049202979158068158842475322825884209352566494900083765571037783472505580851500043517614314755340168507097558967372661966013776090657685241689631615245294004694287660685274079979318342939473469143729494106686592347327776078649315612768988028622890242005700892937828732613800620455225438339852445425046832904615827786856105112781009995862999853122308496903885748394541643702103368974605177097553007573113536089894913967154637055293769061726082740854619536748297829779639633209710676774371525146758917646731487495135734759201537358734170552231657257498090553682791418003138924472103077035355223367678622115314235119493397080290540006942708439607767313672671274857069053688258983103863067394473084183472609906612056828326916114024662795812611685559034285371151973580240723680736227737324052391721149957542711415812665358477474058103338801398214688403784213100455466705770532894531602252798634923125974783427678469124261634518543957766622712661056594132089

e=65537
lpt=(pow(7,e1*e2,n)*pow(c1,e2,n))%n
rpt=(pow(3,e1*e2,n)*pow(c2,e1,n))%n
k=(lpt-rpt)%n
p=gcd(k,n)
q=n//p
phi_n=(p-1)*(q-1)
d=inverse_mod(e,phi_n)
m=pow(c,d,n)
from Crypto.Util.number import long_to_bytes
print(long_to_bytes(m))
#b'SYC{poly_rsa_Just_need5_s1mple_gcd}'

baby_rabin

这题蛮难的，第一次见到 rabin 版本 RSA，很安利这篇文章

先简单审计代码，乍一看是那种常规的 RSA，只是n=pqr​,之前做过类似的，无非就是给欧拉函数phi_n​多乘一个(r-1)

but，本题很特殊，e=8，这是个偶数，因此不可能与欧拉函数值互素,也就是说不可能找到逆元来求解 d

结合题目信息，这里绝对考察了常规的 rabin 加密，因为特征 e 是偶数，然后满足 rabin 最常见的素数类型：

$$p,q,r \equiv 3 \pmod 4$$

还有，这里的 m 相对p*q​就小，更不用说再乘 r 了，那么，我们可以将 r 省略，直接就hint=p*q进行处理

对了，这里的 512 位其实不大了，也就是说，我们可以借助factordb进行因式分解，然后呢：$2^3=8=e$

常规 rabin 一次也就只能处理 2 次方，也就意味着我们需要连续三次 rabin 解密，每次解密都会拿到 4 个根，大致算算，我们最后应该会拿到 64 个根，哦，对了，rabin 存在关于 p 对称的性质，这也就是为啥不进行去重的脚本打印所有信息的时候会多次出现 flag

$$x^2 \equiv (p-x)^2 \pmod p$$

from Crypto.Util.number import long_to_bytes

C = 451731346880007131332999430306985234187530419447859396067624968918101700861978676040615622417464916959678829732066195225132545956101693588984833424213755513877236702139360270137668415610295492436471366218119012903840729628449361663941761372974624789549775182866112541811446267811259781269568865266459437049508062916974638523947634702667929562107001830919422408810565410106056693018550877651160930860996772712877149329227066558481842344525735406568814917991752005
p = 8126207696720549329082137712377866763714498107449360320398058077477163232178648217462900996288494410540148868460607029478677856276076857845820034721107771
q = 8126207696720549329082137712377866763714498107449360320398058077477163232178648217462900996290101348584407858736148991571019018878599060839602827556409243
n = p * q

def get_square_roots(c, p, q):
#这就是在进行rabin开方处理
    mp = pow(int(c), (p + 1) // 4, p)
    mq = pow(int(c), (q + 1) // 4, q)

    res = []
#会拿到两个平方根
    roots_p = [mp, p - mp]
    roots_q = [mq, q - mq]

    for rp in roots_p:
        for rq in roots_q:
            res.append(crt([int(rp), int(rq)], [int(p), int(q)]))
    return res

roots_e2 = set(get_square_roots(C, p, q))

roots_e4 = set()
for r in roots_e2:
    try:
        roots_e4.update(get_square_roots(r, p, q))
    except: # 如果 r 不是平方剩余，说明这条路走不通
        continue

final_roots = set()
for r in roots_e4:
    try:
        final_roots.update(get_square_roots(r, p, q))
    except:
        continue
for m in final_roots:
    msg = long_to_bytes(int(m))
    print(msg)
"""
b'syc{th1s_so_1z_mum_never_ca1r_mytstu1d}'
b'R\xcd\x97\x89\xf3\xdc\xdb\x82|\x0f\x99\'R17\xe6\xb0z\xc1\x93u~\xdb\x00\x85\t\x9c\x8cw\x02\nue\x10\x95\x12\xac\x06Qk\x13\xb9)\xf7"\x8f\xbc\xd9\xb0\xder`\xd3\x97\xac\x0b\xa5\r\xa2\x00\x98*A&\xc5\x91\xa8TI\xbb\x08\xbd\xb1_\xe7$\'.\xf6\xcdG&\xb7\xfe\xf5\'\xbe\xe1\x7fv\x13\x80\x8bA\tx\x85(P\xad\x8d\xa3\xb9S\x87%Dt\xf0G\xc8\x1eL\xea\xfaB\xa4\xa0\nJ\xab\x9aO\xdd\xc4\xa1\x9d\x9e'
b"\x0b;\xf6=\x85\x04Y\x13\xd8\x11\xffl\x9a\xfc\xfa'\xda\xbc\x1cl(\xfc\xed\xf9\xea\xf2eF\xdaP\x13B\xa1\xee^\x1d\x03\x83@E\xcf\xb1\x85#\x1f^kdUs\x03[\xd1\x88\xfa\x8b\x178`T\xbb\x1e^\x9a\x19n|\x96 \xe4\x8f\xb6\x04\xd0\x83\xefJA\x14\xedMe\xb3\xb7\xed\x8d\xfe\x96Q\xd1h\x11\xaa\xfb\xa1\\\xe2w\t\x9dM\x11zOl\xc1f\xc6\xfc\x8daX \xf5\xd2\xae'z\xffn\x1e\xabg\xce\x18\x12\x90\x1b"
b'^\t\x8d\xc7x\xe14\x96T!\x98\x93\xed.2\x0e\x8b6\xdd\xff\x9e{\xc8\xfao\xfc\x01\xd3QR\x1d\xb8\x06\xfe\xf3/\xaf\x89\x91\xb0\xe3j\xaf\x1aA\xee(>\x06Qu\xbc\xa5 \xa6\x96\xbcF\x02USH\x9f\xc0\xdf\x00$\xeaj\x9f\x98s\xb60k\x13qp\x0b\xba\x94\x8ck\xb6\xe2\xb5\xbdw\xd0\xd4\x02.\xba\xc8B\xa3\xf4?\xe6\xdb{\x83\xb9C\x86q=\xdc~o\xb3\x10\xfb\x81i\x8f\x9a\xa8\xaaKP\xd1D7g\x82\xc9<'
"""

Diffie-Hellman

第一次见识到 DH 共享密钥体系

本题中，我们可以指定 Bob 的公钥，而且没有限制，那么我们只需要指定 Bob 的私钥 b=0,通过计算，公钥 B=1,那么的话，完全可以在不知道 Alice 的私钥的情况下，让两人共同的密钥 s=1，就能确定后面 flag 的 aes 加密用到的 key 了

from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes
s = 1

key = sha256(long_to_bytes(s)).digest()

enc_hex = "bfbad03a4b1a3841e663832b6a8a0980ea40d1eabad7c26ba01c59f563ae613e0da86dc140512b2da90a2670f9be6db4"
enc = bytes.fromhex(enc_hex)
cipher = AES.new(key, AES.MODE_ECB)
flag = cipher.decrypt(enc)
print(flag)
#b'0xGame{348614a0-75c2-4230-a841-1d8e384f301e}\x04\x04\x04\x04'

ez_xor

这题也很不错，考察了一些位运算的知识 $s + r = (s \oplus r) + 2 \cdot (s \& r)$

证明下这个恒等式公式：

左式：$s+r$ 是简单的加法运算，比如说 1+1=10 在二进制中成立

右式：

• $s \oplus r$是一种没有进位的加法，本质上是，如果两个数字相同为 0，不同为 1，$1 \oplus 1 = 0$，这正好是 10 的低位

• $s \& r$是一种负责进位处理的运算，本质上就是两个数字相同就是 1，不同就是 0，$1 \& 1=1$，前面的那个 2 可以让这个与运算的结果向上进位

ok 了，通过这个恒等式，我们获取了 s+r，然后结合题目的 N 和 n

$$\begin{cases} N=p*q*r*s \\ n=p*q \end{cases}$$

我们可以获取到$s * r = \frac{N}{n}$

接下来可以利用韦达定理构造出关于 s 和 r 的二次方程，其中 s,r 是方程的两个根

$$\begin{cases} s + r = -\dfrac{b}{a} \\ s* r = \dfrac{c}{a} \end{cases} \Rightarrow x^2 - (s + r)x + sr = 0$$

接下来可以利用一元二次方程的求根方程快速求解 s,r

$$x = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}$$

至于 p 和 q 的提权，需要处理这两句

n = p * q
gift = p ^ q

• 确定最低位：p, q 都是奇数，所以 p_0 = 1, q_0 = 1，要求 gift_0 = 0。

• 从低位到高位逐位构造：

  • 对每位 i，根据 gift[i] 确定 p_bit 和 q_bit 的异或关系。
  • 尝试 p_bit = 0 或 1，得到 q_bit。
  • 检查当前构造的 p, q 的低 i+1 位的乘积是否等于 n 的低 i+1 位。
  • 满足则递归下一位。

• 当 i = 512 时，验证 p * q == n，返回结果。

我的 exp

import math

from Crypto.Util.number import *

N = 12114282140129030221139165720039766369206816602912543911543781978648770300084428613171061953060266384429841484428732215252368009811130875276347534941874714457297474025227060487490713853301440917877280771734998220874195868270983517296552761924477514745040473578887509936945790259245154138347432294762694643113545451605193155323886625417458980089197202274810691448592725400564114850712497863770625334209249566232989992606497076063348029665644680946906322428277225178838518025623254240893146791821359089473224900379808514993113560101567320224162858217031176854613011276425771708406954417610317789259885040739954642374667
n = 91891351711379799931394178123406137903027189477005569059936904007248535049052097057222486024223574959494899324706948906013350601442586596023020519058250868888847562977333671773188012014902448961387215600156932673504112816058893268362611211565216592933077956777032650164332488098756557422740070442941348084921
c = 3231265723829112665640925095346482445691074656152495613367006320791218303024667683148786980985160622882017055128261102169256263170652774489339801477001275058585666508737704987192764426162573977263344192886400249198007892940084066468570229353879431384001463041292940472308358540532108957894938586227682908251475990882169979412586767210087025064295224506676379057986353004282550774815876093769770845018817117647615011444989401149674886486770646765454314760906436659162076044268401041579090930954919862146749470426101754009562077505810024012143379326028465156444246440949112724465484939452061684185387430755268355807999
gift = 5160856643507450510397828582001051679762426399445648048700295372044216322163410374903665868763924707209143638999442462398781974627158916257502760763419216
gift1 = 10475668758451987289276918780968515546700284023143612685496241510488708701498972819305540608876501965534227236009502810417525671358108167575178008316645429
gift2 = 2089035701361172996472331829521141923363322027241591404259262848963755908765054555529259508147866255819680957406084877552079796025933552021516283158425474


def solve_sr(N, n, gift1, gift2):
    sr_prod = N // n
    sr_sum = gift2 + 2 * gift1
    D = sr_sum**2 - 4 * sr_prod
    sqrt_D = math.isqrt(D)
    if sqrt_D**2 != D:
        return None
    s = (sr_sum + sqrt_D) // 2
    r = (sr_sum - sqrt_D) // 2
    return s, r


def solve_pq(n, gift):
    def dfs(i, p, q):
        if i == 512:
            if p * q == n:
                return p, q
            return None

        bit_gift = (gift >> i) & 1
        mask = (1 << (i + 1)) - 1
        target = n & mask

        for p_bit in [0, 1]:
            q_bit = p_bit ^ bit_gift
            tp = p | (p_bit << i)
            tq = q | (q_bit << i)
            if (tp * tq) & mask == target:
                res = dfs(i + 1, tp, tq)
                if res:
                    return res
        return None

    if (1 ^ 1) == (gift & 1):
        return dfs(1, 1, 1)
    else:
        return None, None


p, q = solve_pq(n, gift)
s, r = solve_sr(N, n, gift1, gift2)


phi = (p - 1) * (q - 1) * (s - 1) * (r - 1)
e = 65537
d = inverse(e, phi)
m = pow(c, d, N)
print(f"[!] Flag: {long_to_bytes(m).decode()}")
#[!] Flag: syc{we1c0me_t190_ge1k_your_code_is_v1ey_de1psrc!}

没 e 也能玩

这题也挺有意思的，实际考察的是 crt

RSA 私钥本来应该满足：

$$ed \equiv 1 \pmod{\varphi(n)}$$

但是题目泄露模 p-1,q-1 下的小 d，没有 e：

$$dp = d \bmod (p-1)$$ $$dq = d \bmod (q-1)$$

存在整数 $k$：

$$d = dp + k(p-1)$$

因为：

$$(p-1)(q-1) \equiv 0 \pmod{p-1}$$

所以：

$$ed \equiv 1 \pmod{p-1}$$

又因为：

$$d \equiv dp \pmod{p-1}$$

代入得到：

$$e \cdot dp \equiv 1 \pmod{p-1}$$

因此：

$$e \equiv dp^{-1} \pmod{p-1}$$

同理，我们还能处理下，拿到模 q-1 下的 e

$$e \equiv dq^{-1} \pmod{q-1}$$

最后用 crt 直接拿到 e：

$$e = CRT(dp^{-1} \bmod (p-1),\ dq^{-1} \bmod (q-1))$$

接下来就没有什么好说的了，正常进行 RSA 解密即可

from Crypto.Util.number import long_to_bytes
c=312026920216195772014255984174463085443866592575942633449581804171108045852080517840578408476885673600123673447592477875543106559822653280458539889975125069364584140981069913341705738633426978886491359036285144974311751490792757751756044409664421663980721578870582548395096887840688928684149014816557276765747135567714257184475027270111822159712532338590457693333403200971556224662094381891648467959054115723744963414673861964744567056823925630723343002325605154661959863849738333074326769879861280895388423162444746726568892877802824353858845944856881876742211956986853244518521508714633279380808950337611574412909
p=108043725609186781791705090463399988837848128384507136697546885182257613493145758848215714322999196482303958182639388180063206708575175264502030010971971799850889123915580518613554382722069874295016841596099030496486069157061211091761273568631799006187376088457421848367280401857536410610375012371577177832001
q=121590551121540247114817509966135120751936084528211093275386628666641298457070126234836053337681325952068673362753408092990553364818851439157868686131416391201519794244659155411228907897025948436021990520853498462677797392855335364006924106615008646396883330251028071418465977013680888333091554558623089051503
dp=11282958604593959665264348980446305500804623200078838572989469798546944577064705030092746827389207634235443944672230537015008113180165395276742807804632116181385860873677969229460704569172318227491268503039531329141563655811632035522134920788501646372986281785901019732756566066694831838769040155501078857473
dq=46575357360806054039250786123714177813397065260787208532360436486982363496441528434309234218672688812437737096579970959403617066243685956461527617935564293219447837324227893212131933165188205281564552085623483305721400518031651417947568896538797580895484369480168587284879837144688420597737619751280559493857
n=p*q
phi_n=(p-1)*(q-1)
e1=inverse_mod(dp,p-1)
e2=inverse_mod(dq,q-1)
e=crt([e1,e2],[p-1,q-1])
print(f"find e:{e}")

d=inverse_mod(e,phi_n)
m=pow(c,d,n)
print(long_to_bytes(m))
"""
find e:65537
b'flag{No_course_e_can_play}'
"""

可以发现，这里的私钥指数就是常见的 65537