内容有点多，希望各位能够慢慢看，水文一篇。
我只是一个渣渣，如有错误，希望各位大佬能够指正(THs)
前提知识
素数：素数又称质数，指在一个大于1的自然数中，除了1和此整数自身外，不能被其他自然数整除的数。
互质数：公因数只有1的两个数，叫做互质数
取模运算：两个整数a，b若它们除以正整数m所得的余数相等，则称a，b对于模m同余，记作:a≡b(mod m)；读作：a同余于b模m，或者，a与b关于模m同余。例如：26≡14(mod 12)。
欧拉函数：在数论，对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目（φ(1)=1）。
模反元素：如果两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1。这时，b就叫做a的“模反元素”。
公钥与私钥的产生
假设Alice想要通过一个不可靠的媒体接收Bob的一条私人消息。她可以用以下的方式来产生一个公钥和一个私钥：
1：随意选择两个大的素数p和q，p不等于q,计算N=pq.
2:根据欧拉函数：求得
3：选择一个小于r的整数e,使e与r互质。并求得e关于r的模逆元命名为d求d令
(模逆元存在，当且仅当e与r互质）
4:将p和q的记录销毁。
(N,e)是公钥，(N,d)是私钥。Alice将她的公钥(N,e)传给Bob，而将她的私钥(N,d)藏起来。
加密消息
假设Bob想给Alice送一个消息m，他知道Alice产生的N和e。他使用起先与Alice约好的格式将m转换为一个小于 N的非负整数 n，
比如他可以将每一个字转换为这个字的Unicode码，然后将这些数字连在一起组成一个数字。
假如他的信息非常长的话，他可以将这个信息分为几段，然后将每一段转换为n。用下面这个公式他可以将n加密为c：
计算c并不复杂。Bob算出c后就可以将它传递给Alice.
解密消息
Alice得到Bob的消息c后就可以利用她的密钥d来解码。她可以用以下这个公式来将c转换为n：
得到n后，她可以将原来的信息m重新复原。
解码的原理是:
已知 
即
。 由欧拉定理得：
0x01 基础RSA加密
用公钥和密文解密出明文，这建立在N可分解的基础上,
在 N 的比特位数小于 512 的时候，可以采用大整数分解的策略获取 p 和 q。
JarvisOJ - Medium RSA¶
这里我们以 JarvisOJ - Medium RSA 为例进行介绍，题目如下
还记得 veryeasy RSA 吗？是不是不难？那继续来看看这题吧，这题也不难。
已知一段 RSA 加密的信息为：0xdc2eeeb2782c 且已知加密所用的公钥：
N=322831561921859 e = 23
请解密出明文，提交时请将数字转化为 ascii 码提交
比如你解出的明文是 0x6162，那么请提交字符串 ab
提交格式：PCTF{明文字符串}
首先利用openssl 生成n e
root@kali:/media/sf_vboxshare/mediumRSA# openssl rsa -pubin -text -modulus -in pubkey.pem
Public-Key: (256 bit)
Modulus:
00:c2:63:6a:e5:c3:d8:e4:3f:fb:97:ab:09:02:8f:
1a:ac:6c:0b:f6:cd:3d:70:eb:ca:28:1b:ff:e9:7f:
be:30:dd
Exponent: 65537 (0x10001)
Modulus=C2636AE5C3D8E43FFB97AB09028F1AAC6C0BF6CD3D70EBCA281BFFE97FBE30DD
writing RSA key
-----BEGIN PUBLIC KEY-----
MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhAMJjauXD2OQ/+5erCQKPGqxsC/bNPXDr
yigb/+l/vjDdAgMBAAE=
其中Exponent即为e值，Modulus即为N值，用yafu分解。
N = 87924348264132406875276140514499937145050893665602592992418171647042491658461
factor(87924348264132406875276140514499937145050893665602592992418171647042491658461)
得到:p, q, d
p = 275127860351348928173285174381581152299
q = 319576316814478949870590164193048041239
d = 10866948760844599168252082612378495977388271279679231539839049698621994994673
利用python生成秘钥
# coding=utf-8
import math
import sys
from Crypto.PublicKey import RSA
keypair = RSA.generate(1024)
keypair.p = 275127860351348928173285174381581152299
keypair.q = 319576316814478949870590164193048041239
keypair.e = 65537
keypair.n = keypair.p * keypair.q
Qn = long((keypair.p-1) * (keypair.q-1))
i = 1
while (True):
x = (Qn * i ) + 1
if (x % keypair.e == 0):
keypair.d = x / keypair.e
break
i += 1
private = open('private.pem','w')
private.write(keypair.exportKey())
private.close()
然后解密得到flag:
root@kali:/1/mediumRSA# openssl rsautl -decrypt -in flag.enc -inkey private.pem -out flag.dec
root@kali:/1/mediumRSA# cat flag.dec
PCTF{256b_i5_m3dium}
0x02 wiener attack
Wiener攻击是一种针对RSA的加密攻击。当d很小时
，攻击使用连续分数方法来暴露私钥d。
Wiener’s attack的原理
由于：
存在一个整数ķ使得
限定
在上面的等式中被替换，它给出：
定义
和
，并代入以上式中得到
除以dpq:
得到：
所以，
略小于
，前者完全由公共信息组成。但是，仍然需要一种检查猜测的方法。假如说（合理的假设，除非G 很大）上面的最后一个等式可以写成：
通过使用简单的代数操作和身份，可以检查猜测的准确性。
如果希望了解更多关于Wiener’s RSA Attack可以查看：https://sagi.io/2016/04/crypto-classics-wieners-rsa-attack/#ZgotmplZ
第七届山东网络安全技能大赛
参考资料：https://xz.aliyun.com/t/3295
题目描述
请破解密文
知识点
rsa wiener attack
解题思路
ne已经给出，可以看出e特别大，在e特别大的情况下，可以使用wiener attack的方法进行破解，
正好工具RsaCtfTool集成了wiener attack的方法，所以可以直接使用RsaCtfTool计算私钥， 如下所示：
使用p q e直接解密密文，得到flag,代码如下所示:
#coding:utf-8
from libnum
import n2s,s2nimport base64
def gcd(a, b): #求最大公约数
if a < b:
a, b = b, a
while b != 0:
temp = a % b
a = b
b = temp
return a
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)
def modinv(a, m):
g, x, y = egcd(a, m)
if g != 1:
raise Exception('modular inverse does not exist')
else:
return x % mif __name__ == "__main__":
p=15991846970993213322072626901560749932686325766403404864023341810735319249066370916090640926219079368845510444031400322229147771682961132420481897362843199
q=28805791771260259486856902729020438686670354441296247148207862836064657849735343618207098163901787287368569768472521344635567334299356760080507454640207003
e = 354611102441307572056572181827925899198345350228753730931089393275463916544456626894245415096107834465778409532373187125318554614722599301791528916212839368121066035541008808261534500586023652767712271625785204280964688004680328300124849680477105302519377370092578107827116821391826210972320377614967547827619
# tmp = base64.b64decode("qzogS7X8M3ZOpkUhJJcbukaRduLyqHAPblmabaYSm9iatuulrHcEpBmil7V40N7gbsQXwYx5EBH5r5V2HRcEIOXjgfk5vpGLjPVxBLyXh2DajHPX6KvbFpQ8jNpCQbUNq8Hst00yDSO/6ri9dk6bk7+uyuN0b2K1bNG5St6sCQ4qYEA3xJbsHFvMqtvUdhMiqO7tNCUVTKZdN7iFvSJqK2IHosIf7FqO24zkHZpHi31sYU7pcgYEaGkVaKs8pjq6nbnffr4URfoexZHeQtq5UAkr95zD6WgvGcxaTDKafFntboX9GR9VUZnHePiio7nJ3msfue5rkIbISjmGCAlj+w==")
# =
d = modinv(e, (p - 1) * (q - 1))# c=s2n(tmp)
c = 38230991316229399651823567590692301060044620412191737764632384680546256228451518238842965221394711848337832459443844446889468362154188214840736744657885858943810177675871991111466653158257191139605699916347308294995664530280816850482740530602254559123759121106338359220242637775919026933563326069449424391192
#c = 225031483444634056931067907865853799650197225351377050632290334721073031287701730297815850654473721939907812470206115171738967740183098960272963323728747481560137205796840356532306950935686580268408289864109695494835661414073083573249882362332920722000099781994315336570711188934565379141406727420346806389405536474102730682155998263607095718543239272202402139286809779368710600842078606046563228470023546348908618719147790859257980882643030144242048154566691808688844513142261099020381730517293884263384819159874220288293023868919557980548807831273449743064237407705987056818011286315950476959812697067649075359373253
n = p*q
m=pow(c,d,n)
print n2s(m)
此处对于libnum库安装简单说明一下
git clone https://github.com/hellman/libnum
cd libnum
python setup.py install
把脚本跑一下就会得到flag
关于脚本在github中也有：https://github.com/pablocelayes/rsa-wiener-attack
0x03 利用公约数
如果在两次公钥的加密过程中使用的 n1 和 n2 具有相同的素因子，那么可以利用欧几里得算法直接将 n1 和 n2 分解。通过欧几里得算法可以直接求出 n1 和 n2 的最大公约数 p:
(n1,n2)=p
可以得出：
n1=pq1
n2=pq2
而欧几里得算法的时间复杂度为：O(log n)。即便是 4096 bit 也是 1s
题目
n1=18263905851567773440446838695766097054252159817375942220432646590577605535001102705343902666589196712209131000424743250389209817386462242094905266578654348699073317748484503797678183012090375022172700739930717847219593096973008967105897376613550069563133191469825170677181620033104899474861544205137427444083416158205978241738189319430709815369614381957092634679663073529915011800029514945250518582469896694087993939399022631417819581576165949892810231692555896017395242464371112868608767990194529216988324463096379599680586615395063392235579858007086701467453321499203151052012397135583838714605379937464734426058203
n2=16950818485762084795193828768953323876388698051219062552262211712110062204954209462306530235388240321343855913666709750794055992220667151032536667937762799073479211925880106492191394846770654371623007051501782616639485222511300384032213459590408774089539345780246233268007572472533774114330568959631749390932599046733958624832563792588926026242133422467392689761450865841250657088270966077177543599222351800102728976845282712937106806976091210265560260177661816495238213887970556095475226646345568545415814035277834069152282458515989066082948101449829801979628039212597995349260855092279108102204886522855975419755219
c1=16274856857661787783089247952446020386301296490309822420733326939579521159181274564159881569720941773424141684911497028248685883897404191432880449283023146073930043226457053587418510143359803678057561120305169670182063356905346792409675959838228170818653485027257264058185367161472527834396804757004371950225319647551718070122431050642186905590213972232201966833949845104276760241004644118590467546314025479853604227295841523010158969804175921406672115195772809154058842429049437301440993794765038365224477229612151404063782303298937771968709567577283974551173044172598459482531433545960749147311254443274915272200560
c2=9946468920119252596998213656931348575944985856629754429330209121534145245119561878513995066589817036899299533093751237144960328759208855732474853794711347203865156360078772132790431594811682581926722057546683437873159107885652842304739962490836998123152090675606004046425633751397173768982047965656687448847259753864171018963561303276197312504508548802813909914926514763930195218396740593919987596462341469781868335025782329081775818968846955110510048099746584203570892950955431181639182647914240604278151551608856971433512600491550082244566145491335738112881861092354219766862656988674738232228115996349755982641605
e1=1804229351
e2=17249876309
解密脚本
# coding: utf-8
from Crypto.PublicKey import RSA
import gmpy2
import codecs
n1=18263905851567773440446838695766097054252159817375942220432646590577605535001102705343902666589196712209131000424743250389209817386462242094905266578654348699073317748484503797678183012090375022172700739930717847219593096973008967105897376613550069563133191469825170677181620033104899474861544205137427444083416158205978241738189319430709815369614381957092634679663073529915011800029514945250518582469896694087993939399022631417819581576165949892810231692555896017395242464371112868608767990194529216988324463096379599680586615395063392235579858007086701467453321499203151052012397135583838714605379937464734426058203
n2=16950818485762084795193828768953323876388698051219062552262211712110062204954209462306530235388240321343855913666709750794055992220667151032536667937762799073479211925880106492191394846770654371623007051501782616639485222511300384032213459590408774089539345780246233268007572472533774114330568959631749390932599046733958624832563792588926026242133422467392689761450865841250657088270966077177543599222351800102728976845282712937106806976091210265560260177661816495238213887970556095475226646345568545415814035277834069152282458515989066082948101449829801979628039212597995349260855092279108102204886522855975419755219
c1=16274856857661787783089247952446020386301296490309822420733326939579521159181274564159881569720941773424141684911497028248685883897404191432880449283023146073930043226457053587418510143359803678057561120305169670182063356905346792409675959838228170818653485027257264058185367161472527834396804757004371950225319647551718070122431050642186905590213972232201966833949845104276760241004644118590467546314025479853604227295841523010158969804175921406672115195772809154058842429049437301440993794765038365224477229612151404063782303298937771968709567577283974551173044172598459482531433545960749147311254443274915272200560
c2=9946468920119252596998213656931348575944985856629754429330209121534145245119561878513995066589817036899299533093751237144960328759208855732474853794711347203865156360078772132790431594811682581926722057546683437873159107885652842304739962490836998123152090675606004046425633751397173768982047965656687448847259753864171018963561303276197312504508548802813909914926514763930195218396740593919987596462341469781868335025782329081775818968846955110510048099746584203570892950955431181639182647914240604278151551608856971433512600491550082244566145491335738112881861092354219766862656988674738232228115996349755982641605
e1=1804229351
e2=17249876309
q=gmpy2.gcd(n1,n2)
p1=n1//q
p2=n2//q
d1=gmpy2.invert(e1,(p1-1)*(q-1))
d2=gmpy2.invert(e2,(p2-1)*(q-1))
while d1<0:
d1+=(p1-1)*(q-1)
while d2<0:
d2+=(p2-1)*(q-1)
m2=hex(pow(c2,d2,n2))[2:].replace("L","")
m1=hex(pow(c1,d1,n1))[2:].replace("L","")
if(len(m2)%2==1):
m2='0'+m2
if(len(m1)%2==1):
m1 ='0'+ m1
print m1.decode('hex')
print m2.decode('hex')
0x04 共模攻击
攻击描述
如果在 RSA 的使用中使用了相同的模n和相同的明文m进行了加密，那么就可以在不分解n的情况下还原出明文m的值。即：
此时不需要分解 n，不需要求解私钥，如果两个加密指数互素，就可以直接使用共模攻击在两个密文和公钥还原出明文m的值。
过程如下，首先两个加密指数互质：
(e1,e2)=1，即存在 s2，使得：
代入化简可以得出：
RSA Cooler
题目描述：
public key 1:
n = 0x9ff2e873e1fcafbed22341b4eafdae01afec540e4e84e6041b0a0e83253f1c5da5dabc73004faa82cfaff8e83e5a99255f9790a7744dd18a694d09a89a5caf638d0cf4fe1150a9e894d47a17f386c107a083ae227efab851196de992a2441b7af3442f31a757234ef8997d8af1a3c3aecf2b6100d393a7b632913c2b1c921409
e = 0xe9a44960483b5ca224cfd18818944eaae47de3a158debbc7886b74d7e11165e2e4158c86add4ccc5317256e5323596c9947513766645aefdac4f0375a0296743
encrypted message 1:
c = 0x636f86fb2b1991d4788092563adf87d14b975e9c7ab7279b10f4741f515788bba2e6e788d6f6c165f4daf65eabee93cebfc55a1d651b1dfb1190174ab338d959775658cf1c6d42b0fe6b7b1abaf5a9aa4ca239367bfcbe88b304c99d5e5f8aac019ec74b11662a5deba523c2f93b7c68a731c019578e3ac64db64cfd3533e91b
public key 2:
n = 0x9ff2e873e1fcafbed22341b4eafdae01afec540e4e84e6041b0a0e83253f1c5da5dabc73004faa82cfaff8e83e5a99255f9790a7744dd18a694d09a89a5caf638d0cf4fe1150a9e894d47a17f386c107a083ae227efab851196de992a2441b7af3442f31a757234ef8997d8af1a3c3aecf2b6100d393a7b632913c2b1c921409
e = 0xd9b47cdd777deb3e94cfa3d416aa91b04f9391af0504a83de03e9e0c49faae8b79cf7c99f575af99ed2e9e5a7edb09219c4f79cf961092f9919ab33bc3c9a74f
encrypted message 2:
c = 0x53b601daa8f93166495a69fa747f8553bb8317cfe6dc3f7fec8c8511e209f9288038405fdee399f3ed68ab25dcd91be8bb2ef2ecac1173318b5d2bba932afdcab2d4e5b46987a0f774a29204ce481f79ea422943118f2eaf6c6820b501d9da8d3fbbcea464a2d158a39de6bae6ab845555e4646ae556d7b1e00567b00d41b06c
对题目所给出的数据进行分析，可看出本题是已知两组n，e、c，求 m，且两组中的模数 n 相等。
换言之，就是已知两个都在模n下的公钥，记为 e1、e2，以及相应的密文 c1、c2，还原明文的过程
import gmpy2
import binascii
# Extended Euclid Algorithm
def extendedGCD(a, b):
# a*xi + b*yi = ri
if b == 0:
return (1, 0, a)
# a*x1 + b*y1 = a
x1 = 1
y1 = 0
# a*x2 + b*y2 = b
x2 = 0
y2 = 1
while b != 0:
q = a / b
# ri = r(i-2) % r(i-1)
r = a % b
a = b
b = r
# xi = x(i-2) - q*x(i-1)
x = x1 - q*x2
x1 = x2
x2 = x
# yi = y(i-2) - q*y(i-1)
y = y1 - q*y2
y1 = y2
y2 = y
return (x1, y1, a)
n = gmpy2.mpz(0x9ff2e873e1fcafbed22341b4eafdae01afec540e4e84e6041b0a0e83253f1c5da5dabc73004faa82cfaff8e83e5a99255f9790a7744dd18a694d09a89a5caf638d0cf4fe1150a9e894d47a17f386c107a083ae227efab851196de992a2441b7af3442f31a757234ef8997d8af1a3c3aecf2b6100d393a7b632913c2b1c921409)
e1 = gmpy2.mpz(0xe9a44960483b5ca224cfd18818944eaae47de3a158debbc7886b74d7e11165e2e4158c86add4ccc5317256e5323596c9947513766645aefdac4f0375a0296743)
e2 = gmpy2.mpz(0xd9b47cdd777deb3e94cfa3d416aa91b04f9391af0504a83de03e9e0c49faae8b79cf7c99f575af99ed2e9e5a7edb09219c4f79cf961092f9919ab33bc3c9a74f)
c1 = gmpy2.mpz(0x636f86fb2b1991d4788092563adf87d14b975e9c7ab7279b10f4741f515788bba2e6e788d6f6c165f4daf65eabee93cebfc55a1d651b1dfb1190174ab338d959775658cf1c6d42b0fe6b7b1abaf5a9aa4ca239367bfcbe88b304c99d5e5f8aac019ec74b11662a5deba523c2f93b7c68a731c019578e3ac64db64cfd3533e91b)
c2 = gmpy2.mpz(0x53b601daa8f93166495a69fa747f8553bb8317cfe6dc3f7fec8c8511e209f9288038405fdee399f3ed68ab25dcd91be8bb2ef2ecac1173318b5d2bba932afdcab2d4e5b46987a0f774a29204ce481f79ea422943118f2eaf6c6820b501d9da8d3fbbcea464a2d158a39de6bae6ab845555e4646ae556d7b1e00567b00d41b06c)
x, y, r = extendedGCD(e1, e2)
m = hex(pow(c1, x, n) * pow(c2, y, n) % n)
print "plaintext:", m
print "flag:", binascii.a2b_hex(str(m)[2:])
代码执行后，打印出明文的十六进制数值，以及对应的 ASCII 字符串：
plaintext: 0x636e73737b5253415f63306d6d4f6e5f6d6f64754975355f34746b7d
flag: cnss{RSA_c0mmOn_moduIu5_4tk}
0x05 Lattice based attacks on RSA
强网杯2018 - nextrsa
# n=0x79982a272b9f50b2c2bc8b862ccc617bb39720a6dc1a22dc909bbfd1243cc0a03dd406ec0b1a78fa75ce5234e8c57e0aab492050906364353b06ccd45f90b7818b04be4734eeb8e859ef92a306be105d32108a3165f96664ac1e00bba770f04627da05c3d7513f5882b2807746090cebbf74cd50c0128559a2cc9fa7d88f7b2d
# e=0x3
# c=0x381db081852c92d268b49a1b9486d724e4ecf49fc97dc5f20d1fad902b5cdfb49c8cc1e968e36f65ae9af7e8186f15ccdca798786669a3d2c9fe8767a7ae938a4f9115ae8fed4928d95ad550fddd3a9c1497785c9e2279edf43f04601980aa28b3b52afb55e2b34e5b175af25d5b3bd71db88b3b31e48a177a469116d957592c
# b=0xfedcba98765432100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
# m=b+x (x:64bit)
e=3, M=m+x,m和c已知，x为64bit内的小整数，由于n无法分解，低指数爆破失败，但我们已有M(明文）的高位。
参考:https://github.com/mimoo/RSA-and-LLL-attacks
使用sage可以解出明文
# partial_m.sage
n = 0x79982a272b9f50b2c2bc8b862ccc617bb39720a6dc1a22dc909bbfd1243cc0a03dd406ec0b1a78fa75ce5234e8c57e0aab492050906364353b06ccd45f90b7818b04be4734eeb8e859ef92a306be105d32108a3165f96664ac1e00bba770f04627da05c3d7513f5882b2807746090cebbf74cd50c0128559a2cc9fa7d88f7b2d
e = 3
m = randrange(n)
c = pow(m, e, n)
beta = 1
epsilon = beta^2/7
nbits = n.nbits()
kbits = floor(nbits*(beta^2/e-epsilon))
#mbar = m & (2^nbits-2^kbits)
mbar = 0xfedcba98765432100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
c = 0x381db081852c92d268b49a1b9486d724e4ecf49fc97dc5f20d1fad902b5cdfb49c8cc1e968e36f65ae9af7e8186f15ccdca798786669a3d2c9fe8767a7ae938a4f9115ae8fed4928d95ad550fddd3a9c1497785c9e2279edf43f04601980aa28b3b52afb55e2b34e5b175af25d5b3bd71db88b3b31e48a177a469116d957592c
print "upper %d bits (of %d bits) is given" % (nbits-kbits, nbits)
PR.<x> = PolynomialRing(Zmod(n))
f = (mbar + x)^e - c
print m
x0 = f.small_roots(X=2^kbits, beta=1)[0] # find root < 2^kbits with factor = n
print mbar + x0
print x0
0x06 广播攻击
攻击条件
条件：如果一个用户使用同一个加密指数 e 加密了同一个消息，并发送给了其他 e 个用户。（相同的e，不同的N，同一明文）
攻击原理
m，e相同，不同的是c和n即：
由中国剩余定理可得：
所以m直接对C开e次方根即可
HCTF GAME 进击的 Crypto [5]
n is 17551188754807399016342420221734945766749930201727412345251590531404061480740932995199065332987719183197199448336435851015540272155441486746027315107821340969105623451575872580170978368650593880274076025520453956378539766228430429142117994616985318963125739076826635459215114946159348678398268099389525414431618517743889314085714390430972783223270985688988995257770363117225472590084489120958397189130958462784532637453482182763505791720641422686749616216521724012108378680177131928438795893866425040489551258902610047574579899692834984999209528110849342042529825594061894238371591910354584305136154355365191215400149
e is 10
c is 4675182605549711347653299514777826238559040200527747810846901991433127025723361807211672208052862870258047285285949212515664278410499603829663266213968511493974766674071825225536665267049044619340378438531615983696406305841945756396579371794826265549929503043134668360055027276522368879193620937457881486509311711905722483187734650127796510808637890189952840971330768913946884525594627652458745930532219238258911608744112001798136394806004726472890838481881026716605743812674350955258003794590748258523929460446986020794445478076559635145181909093786617716473870604463315696183050495143502762614767485881979217577416
n is 21840437284422601584177601857355845296420300157767339109572377640408362726674561246210400400760474187121246893712480109326893614162779470768415282900713800983815570602250068673695044749932532689851310770087552524620857623442019428044482787965428075984951982104920901562456426672111590909100736209153905853035127247720276974050404663847547090362780729077829594684995979457326414947449083219461617302643392904522733812903141301332227357689517880801845510579518887472928083718826890369016944549160461428710615747001273521253638766267143341819170249648385341127263707417642925464809788975715332938666417316695941347477577
e is 10
c is 4586033930015814975553487614321341290358072960539564849589758593801587823414394351862074093343255479635303199078561905260793645869942622136164615776822867275172888812989071016687658023005838776181437470204528335444413852561895603377955959308318399246963213964044984235974352824060625970587119586612774322385216810264819426458641852166009899106655036755913322283219739741020656812034348404092018340277026844114272699170323014050087289715403989671918767712613414346320222745328800096615947138667139053339483278319521201983885423491905171167675501563556563890821756892474999549635650486944010346554641603343238490572689
n is 30015914133986758133105015082922460910471726819000479872816812806794140887209294393963063273377891203069864711466776200108173672428779293308320460116493040572826915020654293929241843686728296387400110062099074573009645563520805301899962344680821396200256042478539540675850427377958553324581371362112652752444824919601767821622038488365501031636558236126052654241662743070651213369566898998898634441261811655053789384588711547685939927721116404429914329081432990913321296964957260691148704710581681774562904924080813274984809940008968629515304859518629473284018332651831587916402539386242421630250537030688162675751761
e is 10
c is 12012575342366442210994368605032582129674485327006093552902983877957202172783938071684841031902396156899396879136388606996807608296316795628987877357547213450360953742947781700549506469226564975927361748596520878542651668963131021269851928174681007347771519569914690980744941965086762285630082781013781879511681353119117280354102271439057204066405072328422057721895983540492150402309552609035008272366176657384174081229798739099558539083074489500359062010164358300087124447037922844709870430218019673914305742939927888838599616520300011913022792060392260618046807788302643742874847024153198113792628046678578753632923
n is 18009718435825445649372629634867772247035138229493108362713630947680338354227735572070882390378632440365163117094233413520107070581908224239210969172094402760924055334584259678276505919418191623762998249724248379302786621689049107500760348303940112840664926231345646325964133281550765454719628161600475143792567309947330130747860125557547051843620899629217636918002929846463097841539446014019579830347356084080488561917440356848465812937246809018168582635191619622041079012450531811237168105634382108634135880887093525611263186925213027913337454706919754923593714509998062073450679720905569489304398625255143801533277
e is 10
c is 4249005911324898630458723491151576810198619078332972911420166645127258598519950448507640904379342817486426262054889199369385257812524759761245588973651578211291344326619317559377360319507727729535083143293335799588196976241949218037833747839545295030259115279668065886560417877204054684495047181117075603468672292268831273735956964067626837975218539840667641885621426607941950306330198897187683754687379611844278471572791816397950634388907233312117920634807989734011132718334334850592111651631323130933438007008983489782601827321396168104668493332626558911838721998173148508994771473224050827471186478106896949413831
n is 27090736422393991189249636552945539144039087911497773160371557650625344533254580764344628540515132884576739746597729079146155130899009238110101654711303800340566538298798432929136509923129089904647023409146264405964139002638684510681372633714179570768685640570209727600215295330846361754314973731753734397312932947433225732597524076563605729037998272803472953079912899867244318073144564355326520230078681106746670895643454939714423661018216469020021429142336238301775948794784776906058601395026463842070755547793192470653204078222827768950823747061655106900276571547680451953562314376913592896427730473091360051391129
e is 10
c is 18557109853898405974924769550105345673703067457537813607252151469933140760798378574244439559372100428971400070351173140348823652755825601433268832363575896137364288069984314151346137206115518309597389268875150549696376813277778514591532615794294637044626683931367510181612383681914421702261592233265455950023252407680604041046629667703207133146853618989187597749132650514038584280417791134426596848369417626039533740827554552117727501565841065077835398951826747855393552731497438983274201599740189743630949174610722118659019630964669901438690028070213710833335622573526403588737092869273969581607637522572757015237506
n is 22277916445389799876692954866506052125036892596099795492064670519272419621528759837318253665292779127861537748967309681231938516330289846519214661138299205082421968922350230121526530080908053297879027158545040193774647350499415863211113776785399848472712293535289113810322398103983587423306282629848367328743089145940536913390664697321526306054579656600439140061667264516070003507841618352122567379038304294976725469305215682426898731699093794930417366769249256999177339843020364367769712776225743916112170787273891225926246407201080202593858063362565931942590349178361085396799890148505959437244983447934838792051793
e is 10
c is 19221531342713801219971420455098666365124810169512711030444063942333694562364114172361552139176582476168134219937393468391346535097965763785916484012657401095066804857900941482772687159471483908107669892419626059680168762119954068288719303591498504050604628627299671160225276355636519961578118413913001058744164531470610279168723402009469959377794138715204862239973561494796213624769358906726186769711689962808937828553399403173762034548974335960107700638910231658795639167906700770120741974418495196827830462542130080965552102416180517600397897065113788279096066792533807104187868678848857780735334749865813019681909
n is 20851005254704933958354817552975190588383962843827122226904964048318053243049822277049715505735762051530592940514007687138882551369906711787133432792478447465241409449145625470766867280545673313710877827491010966285871747638401315338616986782370641881615238434667687936400955629642629748987839996011550408156162317201139746453148874558603034756902297066835592748562014100033050736650359512497633206350878620421058840864178654150287452573363251543090733404389037241843869379543719804499640600546216051812575335078292203435075056740907356476508423562893159958041443951220933694064510275964264723600894558623421819904501
e is 10
c is 2043866718532927301454127017521835945401727173760352488220517028498861777262807036566165189285730569375083406234212921588654098421290088269551352101830688429903600880691046607902396566775005694148315605616437713115424223594710186677844867273218443350479253279231960061845711898262461185970057002138523262952260834191169438764964758526877361442277664448596129451496415695776781879266732057920583336999766633938582656240607973759756021032489262381190762825081392613689817792764844409877116240223852376311404164963595040347176139494461319495285348608562589901671620063620688524249523700500144604558899272202564535295466
n is 21745680718194037861694569863678082853797244380310200176477643943644972463871360669070584682807703870684830948023158889780219716829353665600564791257912082043905122048004593803193375178269942973208249276102769671038752489438400731535367257356207098737711096953679231300720903502192144476519811856646400822239966219746455729409375771797064825552958482297097797911599808242875799342438899636328763766908154658738969614707377852147843953614178305416594819846812426828300689497046389665982817209315784313108617753052015326937047712513569322963102500122038505770232917473260057408981125469607573191926134043719437868156273
e is 10
c is 9018406452041117867927204674649220929160509942604290572303644183451237944912470236367308266319079349289625873447647200474598755869642999213142758825809522474810817609751187533346902667225032452694187162262683056445775455963994237202296104812386374636270188433521927503415507963477240913270879794141170568393025367891003921090015993944946205723601349149601256727433716155121883420271498265967234259068535172501445643752691860997480636101699340740265505767091920668218018002976632111256430655619061247292025654740889077014179258647084698229733160071306390020603636210736363198302407289195286953980520285032528614492926
n is 23257483042331781031320004066395973098539881870433034498180628292164825476845647596122889756396987220787263478778647199033523248861079487991256044473644515960559630792146394039814096408486541588067643811077716428015000310006227815563853161604153799667073262886506475792902392829571472354691875108497532721686076971371510238161060553858839091026451266521753830084143245517459861325880906431205328541736948784727909518259034781432825317588016829248046749554245422672923121452470552323438808591118050034108325754535134236727740460190849252647561826203675666601441506024780605194340777802389960180532831878689458096046821
e is 10
c is 17978671919734595201524186618868659656036765546673883938819333911564948587858876495802600244078413312462813938682090761599961604959609423010904187720748539707172853352540370208991902929002036775381503365170196838626379685712050728875172622632447875368166743751159775611642629408534890684109652648484868876710697249351895355111511281037497347712241242908563699707272843032773107477368790419109907271096351457526240471975122296483655337150130000812813081239181653384419149292970320991892073352340649237387406498087734708162094476092368665794350968924289259192893289337038201504066310173284757044802449600666007821509553
n is 27637004622327338030988157906180324667829916751358977640832765328645718696385482091781513197472066052101704131751158627239657425473994441143385613105528200215275110466263289952962400664293602133856809475295970322767309563273999319926150648399522508592521685688896842833243324070987594588134776515978198364901455727292006058624015674914131447232032058875410956114939938460192876157612457774033922125553271809409381181134668696682847583314698759337802814876161751333701826176655372126746717533228292189928645064111959824895679517476699556313948724818860906006774808944802984477517788391260149504822396276593451707118257
e is 10
c is 8597067880812456123669594978660135058668875834924201279924162761020137582662367704504988576614934966062323191666982943113656186783894245035267051756178331490881264629774635620179678000947771928854566239213498586078670870127924696459041295848474073879336501325437194563845414699360564571136683492426292766799121155041276162673427700999761055592609213603158576637212003771003996722743170543342885011289692845493598413965688949325670519743413071479057382602222055902593614159427186017797992219490308930116850084553033461316509457834436420821916094206010206229370273622681413176347187252950087428868295965528772832409316
题目分析：
因为n1,n2,n3,⋯,n9是互质的，所以可以用中国剩余定理，求出me，e已知，就可以求m了。由于m和e太大，所以我使用二分法进行计算
下面代码中，n、c均为储存文件中所有n、c的list。
from operator import mul
from functools import reduce
def exgcd(m, n):
x, y, x1, y1 = 0, 1, 1, 0
while m % n:
x, x1 = x1 - m // n * x, x
y, y1 = y1 - m // n * y, y
m, n = n, m % n
return n, x, y
def prod(lst):
return reduce(mul, lst)
def China_remainder(a, m):
p = prod(m)
M = list(p // n for n in m)
t = list(exgcd(M[i], m[i])[1] for i in range(len(m)))
return sum(a[i] * t[i] * M[i] for i in range(len(m))) % p
def root_10(p):
l, r = 0, p
while l + 1 < r:
m = l + r >> 1
pm = m ** 10
if pm == p: return m
elif pm < p: l = m
elif pm > p: r = m
if r ** 10 == p: return r
else: return None
m_10 = China_remainder(c, n)
print(root_10(m_10).to_bytes(184, 'big').decode())
成功拿到flag:hctf{Hastad’s_broadcast_attack_is_interesting}
参考资料：
质数：https://zh.wikipedia.org/wiki/%E7%B4%A0%E6%95%B0
取模运算：https://zh.wikipedia.org/wiki/%E6%A8%A1%E9%99%A4
欧拉函数：https://zh.wikipedia.org/wiki/%E6%AC%A7%E6%8B%89%E5%87%BD%E6%95%B0
CTF Wiki RSA 基本介绍：https://ctf-wiki.github.io/ctf-wiki/crypto/asymmetric/rsa/rsa_theory/#_2
https://www.cse.wustl.edu/~jain/cse571-17/ftp/l_09pkc.pdf
Lattice based attacks on RSA：https://github.com/mimoo/RSA-and-LLL-attacks
使用SageMath尝试Coppersmith的攻击：http://inaz2.hatenablog.com/entry/2016/01/20/022936
中国剩余定理：https://www.wikiwand.com/zh-hans/%E4%B8%AD%E5%9B%BD%E5%89%A9%E4%BD%99%E5%AE%9A%E7%90%86
Crypto-RSA-公钥攻击小结：https://xz.aliyun.com/t/2731#toc-10