0x00

这是i春秋上的一道简单的RSA因数分解题。
题目链接：https://www.ichunqiu.com/battalion?q=4623

下载后打开rsa.txt，看到提供的参数

n（两个大素数p、q的乘积）
e（公钥）
c（密文）

0x01

对n进行因数分解

如果n比较小，那么可以通过工具进行直接n分解，从而得到私钥。如果n的大小小于256bit，那么我们通过本地工具即可爆破成功。例如采用windows平台的RSATool2v17，可以在几分钟内完成256bit的n的分解。

如果n在768bit或者更高，可以尝试使用一些在线的n分解网站，这些网站会存储一些已经分解成功的n，比如：http://factordb.com 通过在此类网站上查询n，如果可以分解或者之前分解成功过，那么可以直接得到p和q。

q = 310935513029228809998830208036655366162721470228774287453148308675193510132489142448801010943658159980501154153084396100
667001391643762749806500051502679498536716532334917842894939889468693960937309663256592497965458780801192062835123429808
544757340971089756707788360038227894054989413747980167536893779923551227744017809301855984582408943622461942486239113822
841696775958645014753081946441406022729616992302829930205076689399802050792392219242304302303180769915076199603301447453
070225380248784444587175874466015595462920262453189072935846093201153746322352707956339337553509285375982422142166744964
09625928997877221

p = 310935513029228809998830208036655366162721470228774287453148308675193510132489142448801010943658159980501154153084396100
667001391643762749806500051502679498536716532334917842894939889468693960937309663256592497965458780801192062835123429808
544757340971089756707788360038227894054989413747980167536893779923551227744017809301855984582408943622461942486239113822
841696775958645014753081946441406022729616992302829930205076689399802050792392219242304302303180769915076199603301447453
070225380248784444587175874466015595462920262453189072935846093201153746322352707956339337553509285375982422142166744964
09625928797450473

0x02

到现在RSA相关参数均已具备，编写代码，求出明文信息
（在此之前需要安装gmpy2模块，可参考此链接进行安装：https://blog.csdn.net/dongyanwen6036/article/details/77176731）

import gmpy2
n = 966808932627497190635859236054960349099463975227350564265384373280336699853387254070662881265937565163000758606154308757944030571837175048514574473061401566330836334647176655282619268592560172726526643074499534129878217409046045533656897050117438496357231575999185527675071002803951800635220029015932007465117818739948903750200830856115668691007706836952244842719419452946259275251773298338162389930518838272704908887016474007051397194588396039111216708866214614779627566959335170676055025850932631053641576566165694121420546081043285806783239296799795655191121966377590175780618944910532816988143056757054052679968538901460893571204904394975714081055455240523895653305315517745729334114549756695334171142876080477105070409544777981602152762154610738540163796164295222810243309051503090866674634440359226192530724635477051576515179864461174911975667162597286769079380660782647952944808596310476973939156187472076952935728249061137481887589103973591082872988641958270285169650803792395556363304056290077801453980822097583574309682935697260204862756923865556397686696854239564541407185709940107806536773160263764483443859425726953142964148216209968437587044617613518058779287167853349364533716458676066734216877566181514607693882375533
e = 65537
c = 168502910088858295634315070244377409556567637139736308082186369003227771936407321783557795624279162162305200436446903976385948677897665466290852769877562167487142385308027341639816401055081820497002018908896202860342391029082581621987305533097386652183849657065952062433988387640990383623264405525144003500286531262674315900537001845043225363148359766771033899680111076181672797077410584747509581932045540801777738548872747597899965366950827505529432483779821158152928899947837196391555666165486441878183288008753561108995715961920472927844877569855940505148843530998878113722830427807926679324241141182238903567682042410145345551889442158895157875798990903715105782682083886461661307063583447696168828687126956147955886493383805513557604179029050981678755054945607866353195793654108403939242723861651919152369923904002966873994811826391080318146260416978499377182540684409790357257490816203138499369634490897553227763563553981246891677613446390134477832143175248992161641698011195968792105201847976082322786623390242470226740685822218140263182024226228692159380557661591633072091945077334191987860262448385123599459647228562137369178069072804498049463136233856337817385977990145571042231795332995523988174895432819872832170029690848
p = 31093551302922880999883020803665536616272147022877428745314830867519351013248914244880101094365815998050115415308439610066700139164376274980650005150267949853671653233491784289493988946869396093730966325659249796545878080119206283512342980854475734097108975670778836003822789405498941374798016753689377992355122774401780930185598458240894362246194248623911382284169677595864501475308194644140602272961699230282993020507668939980205079239221924230430230318076991507619960330144745307022538024878444458717587446601559546292026245318907293584609320115374632235270795633933755350928537598242214216674496409625928797450473
q = 31093551302922880999883020803665536616272147022877428745314830867519351013248914244880101094365815998050115415308439610066700139164376274980650005150267949853671653233491784289493988946869396093730966325659249796545878080119206283512342980854475734097108975670778836003822789405498941374798016753689377992355122774401780930185598458240894362246194248623911382284169677595864501475308194644140602272961699230282993020507668939980205079239221924230430230318076991507619960330144745307022538024878444458717587446601559546292026245318907293584609320115374632235270795633933755350928537598242214216674496409625928997877221
d = int(gmpy2.invert(e, (p-1) * (q-1))) #计算私钥
m = pow(c, d, n) #解密
print(m)
print(hex(m))

运行结果十六进制输出：
0x666c61677b643166666572656e63655f6265747765656e5f705f416e645f715f31735f7430305f356d616c6c7d

0x03

将十六进制转化为字符串得到flag：
flag{d1fference_between_p_And_q_1s_t00_5mall}

工具地址：https://tool.lu/hexstr/