Single

[2016“湖湘杯”]简单的RSA2 min read

题目下载

给了(n,e,d),但是flag是用new_n加密的,new_n的值暂时未知。

首先可以用http://factordb.com/这个网站分解出n,得到p和q:

p:25469341510015610710601677541490068882874022771473379147959682877979811860690835905177575433486769235926750944378553837429714908846121392087707617153368450157831411033840331452402635316893579428297241392591768100008774205252294780519995317089863801331600746389471563346749402400584048767782402832414560955794979239140648096754408560344380360521300295416056532504527346890878830708030202503589314586128121926254376071861981570648841288044240102936057199541504839050994656267226010545841307490110261343492485615893311098351703701000220286503350522201318815497988460167971677642567134161349144833221240627311534482202273
q:18549922009255682065873541075490523694236993018017378711472390294347289738564184852893543842874884431799749016007575801573141434444916044586366999351488315491792727433264614393421339756775694364361870792935536914730184638908553444398548728815983615033645725832510366617312824482715041572565651201973381892649356584003444436598024263892174846508030188237071677814016044004832440289894928290725654672618489148762420471282901956872617107075453840794524807351894754626817085978425574873605883098036587598323071317767994487432181224109477252086528459769424114149210975886656634032363487078722904015201345359534672812718167

从以下摘下来的这段代码可以看出:

p、q与new_p、new_q只有低900位是不一样的,高2048-900还是一样的。

p = getPrime(2048)
q = getPrime(2048)
print "Destory q, p"
new_p = destory(p, 900)
new_q = destory(q, 900)

这部分学习了40huo师傅写的WP,学到很多q q:

利用格基归约的方法,使用推广的 coppersmith 攻击。

求new_p的SageMath代码如下:

n = 0x73cec712124b33c0294e01eb52e8c3cd2fe9ddbcbf457b3b950360063dfae42cbbe9855bd986bcfea0948fadfb252f5e2ff3c982ff47afb6596a496636f1fc5ecfe9f5db7620b23fe9e30d230aa9299ab9a78bfb5e0630fd1149259b2b2104ea65d2e27b89785e4bf01d0594d9f94575cbcc3383f63c5aabe4d5b48eb761cce3ab21689b3f3155b5f15efee240d5ac11cee2acbd019de7c06f607ea618b5cd735b5a6972d2b446a12ff58cf8314822fa5ea09d0963acd00441b2a1b37aca01d7f39052927db98a0bd5ca1c49a7ad67923e3aac30ecd33cc8b4b30a40cdb3acc721ee5da53a02977cee959affe672a668525eb78df96af0a14f4ac04fab68efa8eabe9535e1064a5fc2ff7cac9520210311db0c3bf91101bc55a67a81e4f69364c724ee6ad6bdc301df642c9392e9befa4ff0d65481adb6feac251cd207044587da9710809700246cb3c63e659a97249f5e7418568e37db2fb2c1115e719d6682bb2e89b4e23d40ba4c532f289e10e0b89a5647c486a09b9e376844171b229d74f871004d4945a702a391a04ac704f43809e972891e6ab33b3c0f03f0b6f9ae005b26be6e647a1865c727277423f59a595187ffbfea13501e23b6b57ef115eaa6febcb207a3112628652a39578847241c33989e84607b0f683b30ddf773348b07360b063d9120a397809591ca18a04cd32ad9cbfe0494ed3ae8d2c5b43fdb51cbL
p_fake = 25469341510015610710601677541490068882874022771473379147959682877979811860690835905177575433486769235926750944378553837429714908846121392087707617153368450157831411033840331452402635316893579428297241392591768100008774205252294780519995317089863801331600746389471563346749402400584048767782402832414560955794979239140648096754408560344380360521300295416056532504527346890878830708030202503589314586128121926254376071861981570648841288044240102936057199541504839050994656267226010545841307490110261343492485615893311098351703701000220286503350522201318815497988460167971677642567134161349144833221240627311534482202273L
 
 
 
 
pbits = 2048
kbits = 900
pbar = p_fake & (2^pbits-2^kbits)
 
PR.<x> = PolynomialRing(Zmod(n))
f = x + pbar
 
x0 = f.small_roots(X=2^kbits, beta=0.4)[0]  # find root < 2^kbits with factor >= n^0.3
print(x0 + pbar)

利用SageMathCell在线运行代码,得到new_p:

new_p = 25469341510015610710601677541490068882874022771473379147959682877979811860690835905177575433486769235926750944378553837429714908846121392087707617153368450157831411033840331452402635316893579428297241392591768100008774205252294780519995317089863801331600746389471563346749402400584048767782402832414560955794979239140648096754408560344380360521296949892303389907769736015934314142003630949305013818258320986061050152391749744927750414406456844331212916757252664106717050422177732254023115330564252024804793822784448052701331761297133645421217718332137034826156560496020813364370285769780848619094541636625925906815949

再用new_n很容易算出new_q:

new_q = 18549922009255682065873541075490523694236993018017378711472390294347289738564184852893543842874884431799749016007575801573141434444916044586366999351488315491792727433264614393421339756775694364361870792935536914730184638908553444398548728815983615033645725832510366617312824482715041572565651201973381892649356584003444436598024263892174846508030770420183686897998285644302367866899840638369622217290489537959059780462703415271851188868247456080287061532074584546595405821143617748170955660518235370195713568906094673772115190597291737336608540077462642156787637875904278512658420610592836051568188911686690679110647

万事俱备,直接用RSA_TOOL算出flag。

flag{6b1ff461dc15e5476cafe887189178e3924dad84}