前置知识：RSA基础，python基础，中国剩余定理等
题目难度8/10。大佬随意。我反正是硬啃了一下午
Task
from Crypto.Util.number import *
def pad(msg):
return msg + b'\x00' * (2048 // 8 - len(msg))
def day():
print("# == Day Time == #")
A = [getRandomRange(1 << 30, 1 << 40) for _ in '01234']
from notebook import pubkeys
hint = str(A)[1:-1].replace(', ', '||').encode()
hint = bytes_to_long(pad(hint))
package = []
for pubkey in pubkeys:
e, n = pubkey
package.append(pow(hint, e, n))
print(f"{package = }")
return A
def night(A):
print("# == Night Time == #")
from secrets import secret
p, q = [getPrime(1024) for _ in '01']
e, n = 0x10001, p * q
message = bytes_to_long(pad(secret))
ciphertext = pow(message, e, n)
print(f"{e = }")
print(f"{n = }")
print(f"{ciphertext = }")
core = getRandomRange(1 << 70, 1 << 80)
box = (A[4] * p ** 4 + A[3] * p ** 3 + A[2] * p ** 2 + A[1] * p ** 1 + core) % n
shell = (A[4] * box ** 4 + A[3] * box ** 3 + A[2] * box ** 2 + A[1] * box ** 1 + A[0]) % n
print(f"{shell = }")
A = day()
night(A)
'''
pubkeys =[
[13, 16966923273393034574368601955241184391111444785998466710722972275633988040568029224272430397635357872449163107278928804572765398970752644900568552514020294813546024733050135082024292481598322682990045855877556853392263676715734911232910368712575738786450510156105046776600566496799942574786503183241332740784997363514285857446938222302824964396227964711868412832852194845619628366554904150230665043909281603861298992421759553638135733037244888585600075655017766713763334284974682754159767494437867386464788270392548503256135412609157993954349845981674000072937143857040970855382655304911806719316346552101453584266121],
[13, 13636547774903694433910615288816366243965221147245493790443257513469643051508482519945160993497983268746607032666514024577996510214003878851754244812785830861056511467944880656887067183093022088006603023892079757597903932697728395729605528467171403935076011715369931494813762896302405865063013876978950952553183445737415893862580946529557997177862386840671940665891984463553509323759394863514802662045074793125218445076375294720405008157895103559623204523371691063630903658360461001806917018298844432738514873530829540084732665560723768831816785580126848217585494349751859982707295270194451027637908966488433591336079],
[13, 13422209706853784863425138450444393536114566510977689013118842078064352816867606066548879016746689784867031499069217146653949323203507755857385123653072875573743110808787259755688613540214185294636104765964080842615717180413731820679997453377899736419007193552970900617704671115646941207925636014254352661937769415565529244046272257822921740649781322893596978112103176487718960676212380426151079825140922318909470514158027009961239217428522970405297292867815726509360369236095377704967444339421311749405316999191339677904499413281713365474466679134722393111495793887387332928227905039036942450742103526490509249576159],
[13, 21746430662648628292439055708644436184530740821098010749514133474681581832957631729292681550968108122182841907644832479495695011213810971334153360397292385819609198743433956578966857749821825621262178208409227379634952172419748956184624505995106932133301461499473823229623656490844764958301835433668618062743327682117611417235819168865744757242990985069648255779083246816509593018812991050741917153961245784296647661659339041115118272068392627299499703962645966495325055378652176922700072734325787550811454984878236039742147547963385471101805136506286953288566035101103034341742923072819774753918471775281464739904101],
[13, 16012920802348742413202394765537959589119609441428117329692661212660781149297315973073063954731746455220386673231725950116051390914388279415796378305381377822621647264088603927560119754278978906758212463937071494263575443156089509654950881813861479449401068535285885349738367249035960528895049222211387021733152221289202030407416118814341241382479971018611239102343929419190892133819275458474489856666791981711793637127167775551296403296397810821548297674986394286293380472089135564385129140069501205054853729781710604489652713172579677128036322403868618295553335257593973027194532512596143733434234439677513237984107]
]
package = [
1348275592172789430802632398715397831929456592129727148350341695822097922745546634103895397114240780119492097879709874341733998189314701220819602086989170395665694216144611451695210776788208725517321710496401109614989729783280209806513298851774400705822274570042128297336679615535569295725037051009221966882907606741910671983811835353310553679554656322510247012465612842055583530354825164440556725066351429241835394579392892121937744444324723509039593320520073762479405487678614235658010109343868772211070874500834820005557924944766175445227592086997786601600141172729543326022039897279215360210475222205314199752358,
11817047514083750028443306573161291960303002458276716688201587284992675854178250185695613342603396451495053496021018943618684096193774851513377343785523373066637422156529843356640438514917147007662989366432951340073247573347091422478343675687872524102452812391963856179412214914106817415620613886827405526709334122157218264253412138947978859771457788135381194396144386611627935519990330309154612803264373276472523863776757124489507206744895878709136339189551422814752920383697719212261820943113370067423118794871570596583232694067119303936516491830190746798281923693136901268220982292626728815051587839682733501582997,
3131427695639074007646625687827523632044624200167725001731246731463369200890045250738898155425873822581405723445926216099453276470655307513244478613248253397941362848890729091875615893643288181126353294271063912991208029628896380928878098320509891044728414542705582996774991148116051162157848421643082210867849206627757941596203046799655123006406284498009424107637970927771132706399889289085811447333980744767367889464364519571965014435281718495338752896521777070285880327861778156398424643033288480056322928449210425585380975486759287881877636187364299666207762828705236236071045450767253946524067440138527952996304,
3345060634868343217881273515503289974894457362066685037297545772310131198850220025672843957153107490874807599311288876818421468275658855183857485067696603798636556327070411528170381402923911922437076616994460720931230980991440337397730061039967493443152767007916713160518618697678791358770766857737217910848181657393760417031865203943283074078341988117567851667858026108335625589177179258992930648353570238327435125409871028669479754623782967450462280802423233657422873275069133939005033872391235288329468886849808534906305377008408076775145268714146937205940659708210819711903273898505450411746796296074348301840443,
689229715602713064347690095007369004049337459458047359544160409565437783924368962797071453687950582019132146435134269723546824657132278724115055713024437048832952574546581164678912794341156478859615959289720931333010836265396177238403118182219901102453660596556053537987705012972371809213618745302576874122654094213771963420178465724399112964705426548207838941065298709968044913923423922781681311806180694571535910059881703228238538782302346351472443730399075812346657046097375387076507982673848430573754749554553794234945423901111974280859817600907619255722739374513108613738135872066592727564964404002462119084702
]
e = 65537
n = 19628814650078845889624476490795800811418703155298421183649751922179289373872110164946485468758965499898659860381452920316689731813466611171330082419646032975535828938381971760997472673267667258345915647828047467420412766203712358122436358120743184983881044132767579608354023899206025747277296489890315455139161247982158229333619416375842911027431739437723838483131248360727904613423834627213036877579164949084954352768932164210879329537266501942223360207803513487189832308290555832923018589686990981697562750385892888271329399531648035355662276186237232094775404084845357101354614900716614704579902047366473325519851
ciphertext = 18231770979476945075115454933498285687471248736331968136534439886998853983159878091479109027681230666670001308495054141682281492473521819495259722942633525843224223138121210743435008344491182811096997837681349401919300801071760448609909297020846949507707329708251861866061443743942558286917774317607571379516986051564317860557772153943821431899226380831989795907857566336085097807330399388077758869632230636727348278392968946952484442630549599469645903047917899063746000458656292320802815605327181346234519795519772619774175495201258591571744214020509439053957080210165266709953654561600989486386199867341092142358249
shell = 7450311459083436799013470526820816670296314417175130490433500468646960366746415074085735399822973890608046359739147553438015771999419943640758794686461655503899174274852006852675273759918109697488252918038788275865249305840107266839320745067341253227218580768443831238305064450748932813304412926315551102620477056031794884272260575749720364002093756539399717557808977458033683588388899534871439955606629530406662400672087729944642496842353084711242911328651341343429685261174338868058208644730980459845089948243884209259777439653298562832822410224626781415627048867272937969823329086437858777995321438386601575065665
'''脚本分析
我写WP一般不单独写脚本分析，只在思路部分提两嘴。
但这题实在是太史了，绕的一批，我不写都能把自己绕晕。
我一直在想它为什么要把程序写的这么丑，我虽然代码能力也不强，但是题我做的不少，为什么生成几个随机数就要写的那么绕。不懂。
言归正传。开始分析。
首先分析加密程序，由三个主要函数pad(),day(),night()组成。
pad函数是最简单的，是一个填充函数。确保message是2048位，不足的以\x00补足位数
然后是day函数。这一串有点复杂。
A = [getRandomRange(1 << 30, 1 << 40) for _ in '01234']首先这串代码创建了一个循环范围，循环次数和'01234'的长度相同。也就是长度是5。
然后是'getRandomRange(1 << 30, 1 << 40)'，这一句代码意思是getRandomRange函数会生成一个大小在2^30到2^40范围内的随机数。
合起来就是生成5个大小在2^30到2^40范围内的随机数。A是包含 5 个随机数的列表。
from notebook import pubkeys这一句是导入公钥。公钥已经给我们了。
pubkeys =[
[13, 16966923273393034574368601955241184391111444785998466710722972275633988040568029224272430397635357872449163107278928804572765398970752644900568552514020294813546024733050135082024292481598322682990045855877556853392263676715734911232910368712575738786450510156105046776600566496799942574786503183241332740784997363514285857446938222302824964396227964711868412832852194845619628366554904150230665043909281603861298992421759553638135733037244888585600075655017766713763334284974682754159767494437867386464788270392548503256135412609157993954349845981674000072937143857040970855382655304911806719316346552101453584266121],
[13, 13636547774903694433910615288816366243965221147245493790443257513469643051508482519945160993497983268746607032666514024577996510214003878851754244812785830861056511467944880656887067183093022088006603023892079757597903932697728395729605528467171403935076011715369931494813762896302405865063013876978950952553183445737415893862580946529557997177862386840671940665891984463553509323759394863514802662045074793125218445076375294720405008157895103559623204523371691063630903658360461001806917018298844432738514873530829540084732665560723768831816785580126848217585494349751859982707295270194451027637908966488433591336079],
[13, 13422209706853784863425138450444393536114566510977689013118842078064352816867606066548879016746689784867031499069217146653949323203507755857385123653072875573743110808787259755688613540214185294636104765964080842615717180413731820679997453377899736419007193552970900617704671115646941207925636014254352661937769415565529244046272257822921740649781322893596978112103176487718960676212380426151079825140922318909470514158027009961239217428522970405297292867815726509360369236095377704967444339421311749405316999191339677904499413281713365474466679134722393111495793887387332928227905039036942450742103526490509249576159],
[13, 21746430662648628292439055708644436184530740821098010749514133474681581832957631729292681550968108122182841907644832479495695011213810971334153360397292385819609198743433956578966857749821825621262178208409227379634952172419748956184624505995106932133301461499473823229623656490844764958301835433668618062743327682117611417235819168865744757242990985069648255779083246816509593018812991050741917153961245784296647661659339041115118272068392627299499703962645966495325055378652176922700072734325787550811454984878236039742147547963385471101805136506286953288566035101103034341742923072819774753918471775281464739904101],
[13, 16012920802348742413202394765537959589119609441428117329692661212660781149297315973073063954731746455220386673231725950116051390914388279415796378305381377822621647264088603927560119754278978906758212463937071494263575443156089509654950881813861479449401068535285885349738367249035960528895049222211387021733152221289202030407416118814341241382479971018611239102343929419190892133819275458474489856666791981711793637127167775551296403296397810821548297674986394286293380472089135564385129140069501205054853729781710604489652713172579677128036322403868618295553335257593973027194532512596143733434234439677513237984107]
]上面这是公钥。Public key。与之相对的是私钥。
hint = str(A)[1:-1].replace(', ', '||').encode()这一句的'str(A)'首先是将A转化成字符串，然后'[1:-1]'的意思是将字符串A开头和结尾的" [ " 和 " ] "去除。.replace(', ', '||')的意思是将逗号替换成'||'，之后.encode()将之前处理的A转换成字节。
hint = bytes_to_long(pad(hint))这一句是将上一句的hint先走第一个pad函数，然后再走一个bytes_to_long(把字符串转化为长整数)
package = []
for pubkey in pubkeys:
e, n = pubkey
package.append(pow(hint, e, n))
print(f"{package = }")
return A这一段代码首先初始化了一个空列表package。
看着后面的代码中熟悉的'pow(message, e, n)'我们就能看出来这是我们的老朋友RSA
由RSA基础知识/题目代码得到，公钥public key的格式是(e,n)。即前面的是公钥e，后面的是n。单看n的位数就可以判断这题不需要我们自己分解n，因为个人计算机不具备那么大的算力。
'pow(hint, e, n)'这一句是标准的rsa加密方法。密文=hint^e mod n
然后是打印加密之后的hint，也就是package。
最后返回A。
然后是night函数，大概是加密程序中最恶心的一段了。
from secrets import secret这一串是import一个flag(我们CTFer都喜欢的东西)。
p, q = [getPrime(1024) for _ in '01']生成两个未知质数p和q。而且都是1024位的。相当大，不可分解。
e, n = 0x10001, p * q这一句是算公钥，e这里是十六进制表示，十进制值是65537，题做多了其实可以一眼看出来，算是密码手的基本修养？
message = bytes_to_long(pad(secret))这一句将flag先pad填充成2048位(256个字节)，再走一个bytes_to_long。
ciphertext = pow(message, e, n)
print(f"{e = }")
print(f"{n = }")
print(f"{ciphertext = }")rsa加密。再打印e，n，cipertext。
core = getRandomRange(1 << 70, 1 << 80)生成一个位数在70到80的随机数core。
box = (A[4] * p ** 4 + A[3] * p ** 3 + A[2] * p ** 2 + A[1] * p ** 1 + core) % n然后算box值。A的第四个数据*p的四次方加上A的第三个数据*p的三次方.........以此类推
shell = (A[4] * box ** 4 + A[3] * box ** 3 + A[2] * box ** 2 + A[1] * box ** 1 + A[0]) % n这一句是算shell值。A的第四个数据*box的四次方加上A的第三个数据*box的三次方.........以此类推。
出题人在玩叠叠乐？
最后打印shell值。print(f"{shell = }")。
A = day()
night(A)先执行了day函数，将返回值给了A。
然后将A执行night函数。
我们可以总结出题目总加密框架
- 生成随机数组 A。
- 将这些随机数转换为字符串，去掉头尾的方括号并用 || 分隔，然后转换为字节。
- 对字节串hint进行填充，转换为长整数形式。
- 使用多个公钥对生成的整数进行RSA加密，得到 package（rsa加密后的hint）。
- 生成p和q，e和n
- 对flag进行填充并转换为长整数形式。
- 对flag进行RSA加密，得到密文ciphertext。
- 生成一个70到80位的随机数 core。
- 计算 box 和 shell。
做的一图流，有点简陋，不过还好。
Think
很难的一道题目，对综合能力(数学/代码)的考查比较高
首先我们看一图流，明确一下解密流程。
- 我们需要解密package来解出数组A。因为A参与了shell的计算。没有A就解不出shell。
- shell又是和box相关。box里面有p。我们需要通过这个解出p和q。
看day函数，在我初读代码的时候就注意到，e只有13。也就是说我们可以使用rsa小指数攻击。而且 公钥相同，模数不同 符合广播攻击的板子。
P.S 其实小指数攻击和广播攻击也大有关系。有时间可以写篇文章讲一讲
但是hint是通过pad填充过的，也就是说我们目前的密文是假明文加密得到的，不能直接对板子来。而且广播攻击的话需要的数据条数大体上等于e的大小，不能硬来。得先分析一下。
首先明确pad之前的hint到底是什么样的。大概是这样的 b'1111||2222||3333||4444||5555'
幸好pad函数填充的比较简单，单纯的加\x00(也就是十进制的0)
这个是解day函数的重点！
这里应该详细讲一下。
我们设pad前的hint是hint1，pad后的是hint2。
那么将hint2用hint1表示的话，那就是hint2 = hint1*10x。x的大小是0的个数。因为hint2不就是hint1往前进位嘛(即添加0).
例：hint1是1，hint2是10.那么10x就是10.也就是说x是1.
所以我们只需要知道pad到底加了几个0就行。然后我们只需要将密文处理一下。就能得出将hint2^e 变为hint1^e。
10x具体多大我们是不知道的，不过我们可以尝试hint2/hint1算一下取平均值，不碍事的。
但是算的时候注意一点！pad函数填充的是\x00。是16进制。所以我们输出的时候也要16进制！
具体的算法就是截取一段加密脚本。稍微改一下就行了。
from Crypto.Util.number import *
def pad(msg):
return msg + b'\x00' * (2048 // 8 - len(msg))
def day():
print("# == Day Time == #")
A = [getRandomRange(1 << 30, 1 << 40) for _ in '01234']
hint = str(A)[1:-1].replace(', ', '||').encode()
h1 = bytes_to_long(hint)
h2 = bytes_to_long(pad(hint))
print(hex(h2//h1))
return A
day()我们要找的10x差不多是这样的。
0x1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
也就是说将那个 package ≡ (hint1*10x)^e (mod n)转化为hint1^e ≡ package * 10x^-e (mod n)
直接列一个CRT，就可以解出来明文hint。也就是解出来了A。
有了A我们就可以进一步解shell，把n分解来解出RSA
首先我们看一下box。
box = (A[4] * p ** 4 + A[3] * p ** 3 + A[2] * p ** 2 + A[1] * p ** 1 + core) % n我们可以得到box ≡ core （mod p），因为p是n的因子嘛，看下面这行。
k*n+box = (A[4] * p ** 4 + A[3] * p ** 3 + A[2] * p ** 2 + A[1] * p ** 1 + core)(k是任意整数
所以我们可以进一步推shell，因为box ≡ core （mod p）。所以我们可以转化shell式
shell = (A[4] * box ** 4 + A[3] * box ** 3 + A[2] * box ** 2 + A[1] * box ** 1 + A[0]) % n转化后的shell式将box全部化为core。最后模一个p。原因同上。
都是参数分析，算是密码手的基本修养？
所以night函数的关键就是求core。
所需算法是coppersmith，求得小根core。
具体怎么弄......就是程序里引用现成的函数。
算出来core，我们就能求得shell的具体值，因为shell和n含有相同质因数p。之后求一个gcd就能求出p。
也就是说，我们成功分解了n。
--------Q.E.D
Exp
我们用sage写exp，因为在我的认知范围里python中没有能直接引用来解copper小根的函数......我自己也不会写，代码/数学能力还是有待提高。
首先咱们先求A，因为我的sagemath抽风跑不了long_to_bytes，所以我们只能玩sage+python。
from gmpy2 import *
package = [11348275592172789430802632398715397831929456592129727148350341695822097922745546634103895397114240780119492097879709874341733998189314701220819602086989170395665694216144611451695210776788208725517321710496401109614989729783280209806513298851774400705822274570042128297336679615535569295725037051009221966882907606741910671983811835353310553679554656322510247012465612842055583530354825164440556725066351429241835394579392892121937744444324723509039593320520073762479405487678614235658010109343868772211070874500834820005557924944766175445227592086997786601600141172729543326022039897279215360210475222205314199752358, 11817047514083750028443306573161291960303002458276716688201587284992675854178250185695613342603396451495053496021018943618684096193774851513377343785523373066637422156529843356640438514917147007662989366432951340073247573347091422478343675687872524102452812391963856179412214914106817415620613886827405526709334122157218264253412138947978859771457788135381194396144386611627935519990330309154612803264373276472523863776757124489507206744895878709136339189551422814752920383697719212261820943113370067423118794871570596583232694067119303936516491830190746798281923693136901268220982292626728815051587839682733501582997, 3131427695639074007646625687827523632044624200167725001731246731463369200890045250738898155425873822581405723445926216099453276470655307513244478613248253397941362848890729091875615893643288181126353294271063912991208029628896380928878098320509891044728414542705582996774991148116051162157848421643082210867849206627757941596203046799655123006406284498009424107637970927771132706399889289085811447333980744767367889464364519571965014435281718495338752896521777070285880327861778156398424643033288480056322928449210425585380975486759287881877636187364299666207762828705236236071045450767253946524067440138527952996304, 3345060634868343217881273515503289974894457362066685037297545772310131198850220025672843957153107490874807599311288876818421468275658855183857485067696603798636556327070411528170381402923911922437076616994460720931230980991440337397730061039967493443152767007916713160518618697678791358770766857737217910848181657393760417031865203943283074078341988117567851667858026108335625589177179258992930648353570238327435125409871028669479754623782967450462280802423233657422873275069133939005033872391235288329468886849808534906305377008408076775145268714146937205940659708210819711903273898505450411746796296074348301840443, 689229715602713064347690095007369004049337459458047359544160409565437783924368962797071453687950582019132146435134269723546824657132278724115055713024437048832952574546581164678912794341156478859615959289720931333010836265396177238403118182219901102453660596556053537987705012972371809213618745302576874122654094213771963420178465724399112964705426548207838941065298709968044913923423922781681311806180694571535910059881703228238538782302346351472443730399075812346657046097375387076507982673848430573754749554553794234945423901111974280859817600907619255722739374513108613738135872066592727564964404002462119084702]
pubkeys = [
[13, 16966923273393034574368601955241184391111444785998466710722972275633988040568029224272430397635357872449163107278928804572765398970752644900568552514020294813546024733050135082024292481598322682990045855877556853392263676715734911232910368712575738786450510156105046776600566496799942574786503183241332740784997363514285857446938222302824964396227964711868412832852194845619628366554904150230665043909281603861298992421759553638135733037244888585600075655017766713763334284974682754159767494437867386464788270392548503256135412609157993954349845981674000072937143857040970855382655304911806719316346552101453584266121],
[13, 13636547774903694433910615288816366243965221147245493790443257513469643051508482519945160993497983268746607032666514024577996510214003878851754244812785830861056511467944880656887067183093022088006603023892079757597903932697728395729605528467171403935076011715369931494813762896302405865063013876978950952553183445737415893862580946529557997177862386840671940665891984463553509323759394863514802662045074793125218445076375294720405008157895103559623204523371691063630903658360461001806917018298844432738514873530829540084732665560723768831816785580126848217585494349751859982707295270194451027637908966488433591336079],
[13, 13422209706853784863425138450444393536114566510977689013118842078064352816867606066548879016746689784867031499069217146653949323203507755857385123653072875573743110808787259755688613540214185294636104765964080842615717180413731820679997453377899736419007193552970900617704671115646941207925636014254352661937769415565529244046272257822921740649781322893596978112103176487718960676212380426151079825140922318909470514158027009961239217428522970405297292867815726509360369236095377704967444339421311749405316999191339677904499413281713365474466679134722393111495793887387332928227905039036942450742103526490509249576159],
[13, 21746430662648628292439055708644436184530740821098010749514133474681581832957631729292681550968108122182841907644832479495695011213810971334153360397292385819609198743433956578966857749821825621262178208409227379634952172419748956184624505995106932133301461499473823229623656490844764958301835433668618062743327682117611417235819168865744757242990985069648255779083246816509593018812991050741917153961245784296647661659339041115118272068392627299499703962645966495325055378652176922700072734325787550811454984878236039742147547963385471101805136506286953288566035101103034341742923072819774753918471775281464739904101],
[13, 16012920802348742413202394765537959589119609441428117329692661212660781149297315973073063954731746455220386673231725950116051390914388279415796378305381377822621647264088603927560119754278978906758212463937071494263575443156089509654950881813861479449401068535285885349738367249035960528895049222211387021733152221289202030407416118814341241382479971018611239102343929419190892133819275458474489856666791981711793637127167775551296403296397810821548297674986394286293380472089135564385129140069501205054853729781710604489652713172579677128036322403868618295553335257593973027194532512596143733434234439677513237984107]
]
pads = 0x1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
n = []
for each in pubkeys:
n.append(each[1])
c = []
for index in range(len(package)):
c += [int(package[index] * pow(pads,-13,n[index]) % n[index])]
hint = crt(c,n)
print(iroot(hint,13)[0])这里求出来的是小指数攻击过的hint。
84152616749644009819335178014845195915060595584188870825938068471509777970442351973186379593722372184935335177670074210379972719587675942936580059181831559506610856227320757253679503009520239659504900718659202913750388481144274288640
然后我们python里走一个long_to_bytes。
看程序输出，这就是我上面说不碍事的原因，反正咱们可以删去嘛
10x具体多大我们是不知道的，不过我们可以尝试hint2/hint1算一下取平均值，不碍事的。
好，咱们终于解出来A了。
A = [646919678902,598613162045,90472013741,917100488664,838250498519]
然后是解出core。
A = [646919678902,598613162045,90472013741,917100488664,838250498519]
shell = 7450311459083436799013470526820816670296314417175130490433500468646960366746415074085735399822973890608046359739147553438015771999419943640758794686461655503899174274852006852675273759918109697488252918038788275865249305840107266839320745067341253227218580768443831238305064450748932813304412926315551102620477056031794884272260575749720364002093756539399717557808977458033683588388899534871439955606629530406662400672087729944642496842353084711242911328651341343429685261174338868058208644730980459845089948243884209259777439653298562832822410224626781415627048867272937969823329086437858777995321438386601575065665
R.<box> = Zmod(n)[]
f = (A[4] * box ** 4 + A[3] * box ** 3 + A[2] * box ** 2 + A[1] * box ** 1 + A[0]) - shell
core = f.monic().small_roots(X=2^80,beta=0.5,epsilon=0.03)[0]
print(core)beta是控制找到的小根大小，一般在0.1到0.5。epsilon是控制搜索精度，一般在0.01到0.1。
我们解出来core是72398025613557274548283
最后
from Crypto.Util.number import *
n = 19628814650078845889624476490795800811418703155298421183649751922179289373872110164946485468758965499898659860381452920316689731813466611171330082419646032975535828938381971760997472673267667258345915647828047467420412766203712358122436358120743184983881044132767579608354023899206025747277296489890315455139161247982158229333619416375842911027431739437723838483131248360727904613423834627213036877579164949084954352768932164210879329537266501942223360207803513487189832308290555832923018589686990981697562750385892888271329399531648035355662276186237232094775404084845357101354614900716614704579902047366473325519851
A = [646919678902,598613162045,90472013741,917100488664,838250498519]
shell = 7450311459083436799013470526820816670296314417175130490433500468646960366746415074085735399822973890608046359739147553438015771999419943640758794686461655503899174274852006852675273759918109697488252918038788275865249305840107266839320745067341253227218580768443831238305064450748932813304412926315551102620477056031794884272260575749720364002093756539399717557808977458033683588388899534871439955606629530406662400672087729944642496842353084711242911328651341343429685261174338868058208644730980459845089948243884209259777439653298562832822410224626781415627048867272937969823329086437858777995321438386601575065665
ciphertext = 18231770979476945075115454933498285687471248736331968136534439886998853983159878091479109027681230666670001308495054141682281492473521819495259722942633525843224223138121210743435008344491182811096997837681349401919300801071760448609909297020846949507707329708251861866061443743942558286917774317607571379516986051564317860557772153943821431899226380831989795907857566336085097807330399388077758869632230636727348278392968946952484442630549599469645903047917899063746000458656292320802815605327181346234519795519772619774175495201258591571744214020509439053957080210165266709953654561600989486386199867341092142358249
core = 72398025613557274548283
box = core
x = shell - (A[4] * box ** 4 + A[3] * box ** 3 + A[2] * box ** 2 + A[1] * box ** 1 + A[0])
p = int(GCD(x,n))
q = int(n//p)
phi = (p-1)*(q-1)
e = 65537
d = pow(e,-1,phi)
m = pow(ciphertext,d,n)
print(long_to_bytes(m))解出来明文是flag{8d24d7d491106a7974d5afe9342b2834}
总结
这是我做过的最难的一道题。
包括一大堆没用过的库，hint的处理，以及学了半暑假都没学会的coppersmith。真难啊。
Comments | NOTHING