总结一下收集到的RSA的所有攻击方法。
一、RSA的前世今生
RSA加密算法是一种非对称加密算法。在公开密钥加密和电子商业中RSA被广泛使用。RSA是1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。RSA就是他们三人姓氏开头字母拼在一起组成的。
RSA算法的可靠性由极大整数因数分解的难度决定。换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠。假如有人找到一种快速因数分解的算法的话，那么用RSA加密的信息的可靠性就肯定会极度下降。但找到这样的算法的可能性是非常小的。如今，只有短的RSA密钥才可能被强力方式解破。到2017年为止，还没有任何可靠的攻击RSA算法的方式
二、算法简述
1、选择两个大素数p和q，计算N=p·q
2、计算Φ(N)=φ(p)·φ(q) = (p-1)·(q-1)
这里的Φ(N)指的是小于等于N且与N互素的正整数的个数，它是等于φ(p)·φ(q)的，而p和q是素数，所以φ(p)=p-1，φ(q) = q-1
3、选择一个整数e，1<e<Φ(N)，且e与Φ(N)互素
4、计算d，e·d≡1 mod Φ(N)，d与e为Φ(N)的模逆元素（例如e·d≡1 mod 3120，意思是e与d的乘积模3120后等于1）
5、(e,n)为公钥，(d,n)为私钥
6、加密：c=me mod n 解密：m = cd mod n
import gmpy2
from Crypto.Util.number import long_to_bytes, bytes_to_long
p = 885320963
q = 238855417
n = p*q
phin = (p-1)*(q-1)
print('phin:', phin) # 211463706672030192
e = 65537
d = gmpy2.invert(e, phin)
print('d:', d) # 34737907838794529
# 加密
m = b'abc'
print("m_to_long:", bytes_to_long(m)) # 6382179
c = gmpy2.powmod(bytes_to_long(m), e, n)
print('encrypt:', c) # 151999436028678347
# 解密
m1 = gmpy2.powmod(c, d, n)
print('plain_long:',m1) # 6382179
print('plain_text:',long_to_bytes(m1)) #b'abc'
三、RSA攻击方法
3.1 模数分解（因数分解）
模数分解（因数分解）是指将 RSA 公钥中的模数 n 分解为两个素数 p、q 的乘积。
在实际应用中，RSA 算法使用的素数长度在 1024 位、2048 位或更高。
在 CTF 赛题中，若模数 n 的 位数比较小，则可以直接因式分解模数n，进而获得 p、q
1、SageMath直接分解
在线SageMath：https://sagecell.sagemath.org/
n = 23519325203263800569051788832344215043304346715918641803 ，这个n是10进制的56位。
2、Number Empire：https://zh.numberempire.com/numberfactorizer.php
该网站限制只能输入一个十进制70位的数。
p=59685983042841638719258366270961747
q=88167801722279687584452285001009403
p的长度：35
q的长度：35
n=5262381918520609262468042081596576903386373963211846734430902600307041
利用该网站分解：
3、FactorDB：https://factordb.com/
- 56位的n：
- 70位的n：
4、Integer factorization calculator：https://alpertron.com.ar/ECM.HTM
80位：7m 23.1s
90位：49m 57.5s
3.2 公约数模数分解
如果Alice和Bob之间进行了两次消息传递的过程，并且Bob不小心在两次通信中生成的大素数有一个是相同的，那么Cat就可以通过对两次通信的n进行求公约数的计算进而分解出两次通信的n
p1 = getPrime(512)
p2 = getPrime(512)
q = getPrime(512)
n1 = p1*q
n2 = p2*q
# 对n1和n2求最大公约数，可以求出他们的同一个素因子q，然后n1和n2分别除以q，即可得到p1和p2
例题：
n1=20738684819333548643191606154039112721439040675563306544625610909152027142345256262044893684039033760000345977227424255285988276861540874795272459885167107786711703072061037153346655860470716109813270970850484359246596333995482370527386351240478391323324528003628936781466053608725537623942740662936457390959060237568952795905984480747252131953431486919915454767666173211766324971698216729056823719403935948246337025169136328423690760181754201413129998612840290312288870691831451331041035467130371628700808661866849510093563933041998781857605089430254020646589100840668279175307364268614722979502349459733201313546503
e=65537
C1=10090071772506699356786817523796638879795767956430881122259413581074147487255697901583915872785212226386740804827031504209013873678271195490184347976909726113849992567822732157901385759397285354278581100781103793501095790350579211837202869075148545917946318684882307466012864770911316092169851618822067233715426324048255853708450136404819266324205387044518115007295318784925546421927454569531083129940396100397500370100209536940952970102117541579218613344705063697081553171695308476917272505352835269504338531141476596188545187942246478960128160164215522712217334328256482344238841803967431362175455511277916355166899
n2=8786943631445618907285673578128969065736407845231978676063517743990149971676108590838018478141539267830135297388946338133118212501753995881728323505028022046681892852390275287578455892948420022401725924370391459133256442791171090767044083995998801191405341251943486452967754059226625932411826416078823933001491318960906984915240483169327050095599908132247012527635762389099349506096964924979658397390303632051436652851864517075326335258047336448737074832375662685357471901942613707493194883688141285652944494050725201823425363699537027265328300525799788818915926941670469334797614788843342658967211459367897335358473
c2=2376551337745495498143783836277905001359434157198875983392352023653607956661119590940353134537809948406199264950807793814467908135189088355697785995909979521012650621199555373370092020230056650644191695731622240605564238060013790626918092343022945758900319577845906202131059334831755086808000264738974511885291809342237068425531476274334194179741298917802236690469954206288086549174681813931598960921390785087102754534749899379867108150767902748565046767786034338660373855710245844554905441305478943537774211805862142044160564509820005472808015696120569279067519522505841771038640641946630692512034529992860041798564
c1和c2用了同一个e，而n不同，考虑公约数模数分解，先尝试求n1和n2的公约数。
primefac.gcd(n1,n2)
# 138208427362519321415796957719893409115158845620691465306429847756182160793457792813274524318954977765983352345599351851847522651053763764408505742877046122880607112556561553947348312144520937951670858255004254249125124519847923450697994182336796590877082479065096323414024512145988695828388117148558948090639
通过最大公约数的计算得到了n1和n2的共同素因子p，接下来就用n1和n2分别除以p，就得到了q1和q2，成功分解n1与n2
3.3 |p-q|较小-费马质数分解
|p-q|很小，即p和q相差很小，可以使用费马质数分解。
对于n=p*q，可以写成一个平方差：
费马质因数分解算法，就是不停地循环尝试，找到两个数，使得：
a = (p+q)/2
b = (p-q)/2
然后：
p = a+b
q = a-b
我们知道n = p*q = (a+b) * (a-b) = a^2 - b^2
因为p * q = n，根据不等式(p+q)/2 ≥ √pq = √n得到a≥ √n
让a从√n开始遍历，直到a^2 - n是一个平方数为止。
找到后a^2-n就是 b^2 ，然后p=a+b，q=a-b
代码：
import math
def fermat(n):
a = math.ceil(math.sqrt(n)) # 向上取整
# b的平方
b2 = a * a - n
b = round(math.sqrt(b2)) # 四舍五入
while b * b != b2:
a += 1
b2 = a * a - n
b = round(math.sqrt(b2))
print(a, b, n)
return a + b, a - b
绿城杯
import gmpy2
from Crypto.Util.number import *
p = getPrime(2048)
q = gmpy2.next_prime(p)
for i in range(3600):
q = gmpy2.next_prime(q)
n = p * q
e = 0x10001
flag = xxx
m = bytes_to_long(flag)
c = pow(m,e,n)
print(c)
print(n)
# c = 5883797662470459824355663245986072888499217007658131616834157815812099907584034205088255553387720712715657503553785084616903197734118992506040765948815581238738585159640841277023597023582148173041980600751980206228524475872232080917683822098342300418744639304147771013376863895727877847094151770079046205501266017838881847833528612089868825489776289686550273385136080255799772961155599801690997753649087689949021276549323525754963020408864310302166537661098308581259246052869844362142747080042122189010627048397501817473817946566885487595098504403459522534124404289032779842658407728856164570059823567667669076044563549721918886430160041337156249733571322684187916005175717585587552966989348534775572282369273898182367851689305440672199427492706130124832744127722533758962606513875787129378871099575729793745175327897215145024490319291830298017471555440811147903390803597635585696411407922981136489077349754222355529320548946411677051716584081079246752768224289803323109047467790868885987703125118276891234633889937243303027095375365791207055516900563280115276282761652663098154769929217653527103304045922204641545963828632051715956492613217136463227530538723452005224696385225174844198627387638874395654771260577791169209134146482
# n = 371836308886540426192412096148744468186415625392487977879857531835902736615143801798286888910032757343063307437491756141584074211336204232321625860256198232674594289958977877151673559656231508894335267778421247120253811435320830719345924114507429603444867321985950626826991173077205178053362583897682032724665933945097478196733856621304091584618890629791164070168813615231192565754075364366134730406435348259862415601279551372742556900223695625597120400693500365067997937729674171334150610370961480163812842105971064886537235753552837000236613769498285320938741476925731411679897178247509473618923405834484514661807520252213326586104301410231354079662448182315435504639054167776200376152713328322609890314052157497227912497420886067642369853988427179097601651852373889536473835216949882465614231082448644133599830105850384251912580667211045553849789111685933572279734855596537588506333965238289830492091608095939699649204953662409772326162756616403885752077614154740093699490363803868230526757718971893753734479487055548790771458190489276504470984092766005111535651632518882006617378156289619913024674060627173821938856436490090896481522906788847664717355154445108253949612361422754030509689952049972855384980134472281224218581516679
解题代码：
c = 5883797662470459824355663245986072888499217007658131616834157815812099907584034205088255553387720712715657503553785084616903197734118992506040765948815581238738585159640841277023597023582148173041980600751980206228524475872232080917683822098342300418744639304147771013376863895727877847094151770079046205501266017838881847833528612089868825489776289686550273385136080255799772961155599801690997753649087689949021276549323525754963020408864310302166537661098308581259246052869844362142747080042122189010627048397501817473817946566885487595098504403459522534124404289032779842658407728856164570059823567667669076044563549721918886430160041337156249733571322684187916005175717585587552966989348534775572282369273898182367851689305440672199427492706130124832744127722533758962606513875787129378871099575729793745175327897215145024490319291830298017471555440811147903390803597635585696411407922981136489077349754222355529320548946411677051716584081079246752768224289803323109047467790868885987703125118276891234633889937243303027095375365791207055516900563280115276282761652663098154769929217653527103304045922204641545963828632051715956492613217136463227530538723452005224696385225174844198627387638874395654771260577791169209134146482
n = 371836308886540426192412096148744468186415625392487977879857531835902736615143801798286888910032757343063307437491756141584074211336204232321625860256198232674594289958977877151673559656231508894335267778421247120253811435320830719345924114507429603444867321985950626826991173077205178053362583897682032724665933945097478196733856621304091584618890629791164070168813615231192565754075364366134730406435348259862415601279551372742556900223695625597120400693500365067997937729674171334150610370961480163812842105971064886537235753552837000236613769498285320938741476925731411679897178247509473618923405834484514661807520252213326586104301410231354079662448182315435504639054167776200376152713328322609890314052157497227912497420886067642369853988427179097601651852373889536473835216949882465614231082448644133599830105850384251912580667211045553849789111685933572279734855596537588506333965238289830492091608095939699649204953662409772326162756616403885752077614154740093699490363803868230526757718971893753734479487055548790771458190489276504470984092766005111535651632518882006617378156289619913024674060627173821938856436490090896481522906788847664717355154445108253949612361422754030509689952049972855384980134472281224218581516679
e = 0x10001
def factor(n):
a = gmpy2.iroot(n, 2)[0] # 元组：(整数部分,小数部分)
while 1:
B2 = pow(a, 2) - n
if gmpy2.is_square(B2):
b = gmpy2.iroot(B2, 2)[0]
p = a + b
q = a - b
return p, q
a += 1 # 千万别忘了a的自增步长为1
p,q=factor(n)
phin = (p - 1) * (q - 1)
d = gmpy2.invert(e, phin)
m = pow(c, d, n)
print(long_to_bytes(m))
3.4 dp泄露
题目特征：提供了dp
注意：这里的dp，指的并不是d和p的乘积，而是d mod (p-1)的意思，至于为什么写成dp，好像是约定俗成了。
求出p后即可求出q，进而求得φ(n)，得到d，通过遍历x，可求出存在p，使得n % p=0
关键代码：
for i in range(1,e): #在范围(1,e)之间进行遍历
if(dp*e-1)%i == 0:
if n%(((dp*e-1)//i)+1) == 0: #存在p，使得n能被p整除
p=((dp*e-1)//i)+1
q=n//(((dp*e-1)//i)+1)
phi=(q-1)*(p-1) #欧拉定理
d=gmpy2.invert(e,phi) #求模逆
m=pow(c,d,n) #快速求幂取模运算
例题：
e = 65537
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657
c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751
解题脚本：
from gmpy2 import*
from libnum import*
e = 65537
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657
c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751
for i in range(1,e): #在范围(1,e)之间进行遍历
if(dp*e-1)%i == 0:
if n%(((dp*e-1)//i)+1) == 0: #存在p，使得n能被p整除
p=((dp*e-1)//i)+1
q=n//(((dp*e-1)//i)+1)
phi=(q-1)*(p-1) #欧拉定理
d=invert(e,phi) #求模逆
m=pow(c,d,n) #快速求幂取模运算
print(n2s(m)) #16进制转文本
3.5 dq、dp泄露
题目特征：已知p、q、dp、dq、c
PicoCTF 2017 Weird RSA
# c:95272795986475189505518980251137003509292621140166383887854853863720692420204142448424074834657149326853553097626486371206617513769930277580823116437975487148956107509247564965652417450550680181691869432067892028368985007229633943149091684419834136214793476910417359537696632874045272326665036717324623992885
# p:11387480584909854985125335848240384226653929942757756384489381242206157197986555243995335158328781970310603060671486688856263776452654268043936036556215243
# q:12972222875218086547425818961477257915105515705982283726851833508079600460542479267972050216838604649742870515200462359007315431848784163790312424462439629
# dp:8191957726161111880866028229950166742224147653136894248088678244548815086744810656765529876284622829884409590596114090872889522887052772791407131880103961
# dq:3570695757580148093370242608506191464756425954703930236924583065811730548932270595568088372441809535917032142349986828862994856575730078580414026791444659
解题代码：
import gmpy2
from Crypto.Util.number import long_to_bytes
c =95272795986475189505518980251137003509292621140166383887854853863720692420204142448424074834657149326853553097626486371206617513769930277580823116437975487148956107509247564965652417450550680181691869432067892028368985007229633943149091684419834136214793476910417359537696632874045272326665036717324623992885
p =11387480584909854985125335848240384226653929942757756384489381242206157197986555243995335158328781970310603060671486688856263776452654268043936036556215243
q =12972222875218086547425818961477257915105515705982283726851833508079600460542479267972050216838604649742870515200462359007315431848784163790312424462439629
dp =8191957726161111880866028229950166742224147653136894248088678244548815086744810656765529876284622829884409590596114090872889522887052772791407131880103961
dq =3570695757580148093370242608506191464756425954703930236924583065811730548932270595568088372441809535917032142349986828862994856575730078580414026791444659
qinv = gmpy2.invert(q,p)
m1 = gmpy2.powmod(c,dp,p)
m2 = gmpy2.powmod(c,dq,q)
h = qinv * (m1-m2)
m = m2 + h*q
print(long_to_bytes(m)) # b'Theres_more_than_one_way_to_RSA'
3.6 小指数明文爆破
RSA中如果公钥e很小，比如3，并且明文也很小，那么c=m^e mod n中，m^e < n，则c=m^3，那么对c开三次根号即可得到m，当然这是一种极端情况。
如果加密后的c虽然大于n但是并不太大，由于pow（m，e）=kn+c，可以暴力枚举k，然后开e次方，直到e次方可以开尽，解出了正确的c为止。
题目特征：加密指数e=3或很小
例题，已知题目信息如下，得e = 3，且密文c比n小，可直接计算密文的立方根。
# e: 3
# c:2780321436921227845269766067805604547641764672251687438825498122989499386967784164108893743279610287605669769995594639683212592165536863280639528420328182048065518360606262307313806591343147104009274770408926901136562839153074067955850912830877064811031354484452546219065027914838811744269912371819665118277221
n:23571113171923293137414347535961677173798389971011031071091131271311371391491511571631671731791811911931971992112232272292332392412512572632692712772812832933073113133173313373473493533593673733793833893974014094194214314334394434494574614634674794874914995035095215235415475575635695715775875935996016076136176196316416436476536596616736776836917017097197277337397437517577617697737877978098118218238278298398538578598638778818838879079119199299379419479539679719779839919971009101310191431936117404941729571877755575331917062752829306305198341421305376800954281557410379953262534149212590443063350628712530148541217933209759909975139820841212346188350112608680453894647472456216566674289561525527394398888860917887112180144144965154878409149321280697460295807024856510864232914981820173542223592901476958693572703687098161888680486757805443187028074386001621827485207065876653623459779938558845775617779542038109532989486603799040658192890612331485359615639748042902366550066934348195272617921683
# 解密脚本：
import gmpy2
from Crypto.Util.number import long_to_bytes
c =2780321436921227845269766067805604547641764672251687438825498122989499386967784164108893743279610287605669769995594639683212592165536863280639528420328182048065518360606262307313806591343147104009274770408926901136562839153074067955850912830877064811031354484452546219065027914838811744269912371819665118277221
m = gmpy2.iroot(c, 3)[0]
print(long_to_bytes(m)) # b'dsc{t0-m355-w1th-m4th-t4k35-4-l0t-0f-sp1n3}'
例题：暴力枚举k，然后开e次方
解题方法：
3.7 低加密指数广播攻击
对于相同的明文m，使用相同的指数e和不同的模数n1，n2，···，ni，加密得到i组密文时 （i≥e），可以使用中国剩余定理解出明文。设
联立方程组，使用中国剩余定理，可以求得一个Cx满足：
Cx = m^e mod (n1·n2 ···ni)
当i≥e时，m小于所有的n，那么所有n的乘积一定大于me，所以求出的cx一定是没有经过模操作 的。对cx开e次方，可以解出明文m。
题目特征：
加密指数e非常小
一份明文使用不同的模数n，相同的加密指数e进行多次加密
可以拿到每一份加密后的密文和对应的模数n、加密指数e
例题：
from functools import reduce
import gmpy2
from Crypto.Util.number import long_to_bytes
def crt(a, n):
sum = 0
prod = reduce(lambda a, b: a*b, n)
for n_i, a_i in zip(n, a):
p = prod // n_i
sum += a_i * gmpy2.invert(p,n_i)*p
return sum % prod
# 已知变量
e = 3
n1 =int('331310324212000030020214312244232222400142410423413104441140203003243002104333214202031202212403400220031202142322434104143104244241214204444443323000244130122022422310201104411044030113302323014101331214303223312402430402404413033243132101010422240133122211400434023222214231402403403200012221023341333340042343122302113410210110221233241303024431330001303404020104442443120130000334110042432010203401440404010003442001223042211442001413004', 5)
c1 =int('310020004234033304244200421414413320341301002123030311202340222410301423440312412440240244110200112141140201224032402232131204213012303204422003300004011434102141321223311243242010014140422411342304322201241112402132203101131221223004022003120002110230023341143201404311340311134230140231412201333333142402423134333211302102413111111424430032440123340034044314223400401224111323000242234420441240411021023100222003123214343030122032301042243', 5)
n2 =int('302240000040421410144422133334143140011011044322223144412002220243001141141114123223331331304421113021231204322233120121444434210041232214144413244434424302311222143224402302432102242132244032010020113224011121043232143221203424243134044314022212024343100042342002432331144300214212414033414120004344211330224020301223033334324244031204240122301242232011303211220044222411134403012132420311110302442344021122101224411230002203344140143044114', 5)
c2 =int('112200203404013430330214124004404423210041321043000303233141423344144222343401042200334033203124030011440014210112103234440312134032123400444344144233020130110134042102220302002413321102022414130443041144240310121020100310104334204234412411424420321211112232031121330310333414423433343322024400121200333330432223421433344122023012440013041401423202210124024431040013414313121123433424113113414422043330422002314144111134142044333404112240344', 5)
n3 =int('332200324410041111434222123043121331442103233332422341041340412034230003314420311333101344231212130200312041044324431141033004333110021013020140020011222012300020041342040004002220210223122111314112124333211132230332124022423141214031303144444134403024420111423244424030030003340213032121303213343020401304243330001314023030121034113334404440421242240113103203013341231330004332040302440011324004130324034323430143102401440130242321424020323', 5)
c3 =int('10013444120141130322433204124002242224332334011124210012440241402342100410331131441303242011002101323040403311120421304422222200324402244243322422444414043342130111111330022213203030324422101133032212042042243101434342203204121042113212104212423330331134311311114143200011240002111312122234340003403312040401043021433112031334324322123304112340014030132021432101130211241134422413442312013042141212003102211300321404043012124332013240431242', 5)
# 使用 gmpy2 的 crt 方法计算 Cx
Cx = crt([c1, c2, c3], [n1, n2, n3])
# 计算 m^e 的整数根
m, exact = gmpy2.iroot(Cx, e)
if exact:
print(f"解密得到的消息 m 为:{long_to_bytes(m)}")
# b'noxCTF{D4mn_y0u_h4s74d_wh47_4_b100dy_b4s74rd!}
else:
print("未能找到整数根")
3.8 低解密指数攻击（Wiener's attack，维纳攻击）
如果加密指数e非常大，由于ed在乘积时地位对等， 解密指数d可能较小，可以进行维纳攻击，具体来说就是：
在CTF竞赛中，识别出维纳攻击很简单，一般来说，e超过65537，就可以确定是维纳攻击。
例题：第十三届全国大学生网络安全竞赛
N : 460657813884289609896372056585544172485318117026246263899744329237492701820627219556007788200590119136173895989001382151536006853823326382892363143604314518686388786002989248800814861248595075326277099645338694977097459168530898776007293695728101976069423971696524237755227187061418202849911479124793990722597
e : 354611102441307572056572181827925899198345350228753730931089393275463916544456626894245415096107834465778409532373187125318554614722599301791528916212839368121066035541008808261534500586023652767712271625785204280964688004680328300124849680477105302519377370092578107827116821391826210972320377614967547827619
enc : 38230991316229399651823567590692301060044620412191737764632384680546256228451518238842965221394711848337832459443844446889468362154188214840736744657885858943810177675871991111466653158257191139605699916347308294995664530280816850482740530602254559123759121106338359220242637775919026933563326069449424391192
# python39 RsaCtfTool.py --createpub -n 460657813884289609896372056585544172485318117026246263899744329237492701820627219556007788200590119136173895989001382151536006853823326382892363143604314518686388786002989248800814861248595075326277099645338694977097459168530898776007293695728101976069423971696524237755227187061418202849911479124793990722597 -e 354611102441307572056572181827925899198345350228753730931089393275463916544456626894245415096107834465778409532373187125318554614722599301791528916212839368121066035541008808261534500586023652767712271625785204280964688004680328300124849680477105302519377370092578107827116821391826210972320377614967547827619
# python39 RsaCtfTool.py --attack wiener --publickey key.pub --decrypt 382309913162293996518235675906923010600446204 12191737764632384680546256228451518238842965221394711848337832459443844446889468362154188214840736744657885858943810177675871991111466653158257191139605699916347308294995664530280816850482740530602254559123759121106338359220242637775919026933563326069449424391192 --private
# python39 RsaCtfTool.py --dumpkey --key private.key
# d: 8264667972294275017293339772371783322168822149471976834221082393409363691895
# p: 15991846970993213322072626901560749932686325766403404864023341810735319249066370916090640926219079368845510444031400322229147771682961132420481897362843199
# q: 28805791771260259486856902729020438686670354441296247148207862836064657849735343618207098163901787287368569768472521344635567334299356760080507454640207003
直接利用RsaCtfTool就可以恢复明文：
1、利用n和e创建公钥
2、根据公钥和密文解出私钥
3、根据私钥得到d和p、q
4、利用d恢复明文
3.9 共模攻击
共模攻击（Common Modulus Attack）的前提是同 一个明文m使用相同的模数n但不同的加密指数 e1, e2,…, ek进行加密。
假设有同一个明文m使用相同的模数n但不同的加密指数e1和e2进行加密，分别得到密文c1和c2：
c1 = m^e1 mod n
c2 = m^e2 mod n
如果e1和e2互素，即gcd(e1, e2) = 1，则可以使用扩展欧几里得算法找到整数a和b，使得：a⋅e1+b⋅e2=1 ，然后可以通过以下步骤恢复消息m：
1.计算c1^a mod n和c2^b mod n
2.如果a是负数，则计算c1^(−a)mod n，这相当于计算(c1−1)a mod n，其中c1(−1)是c1在模n下的逆元。同理，如果b是负数，则计算c2(-b)mod n
3.最终消息m可以通过m = ((c1^a % n) ⋅ (c2^b % n)) % n来恢复。
brrctf rsa3:
c1=22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361
n=22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801
e1=11187289
c2=18702010045187015556548691642394982835669262147230212731309938675226458555210425972429418449273410535387985931036711854265623905066805665751803269106880746769003478900791099590239513925449748814075904017471585572848473556490565450062664706449128415834787961947266259789785962922238701134079720414228414066193071495304612341052987455615930023536823801499269773357186087452747500840640419365011554421183037505653461286732740983702740822671148045619497667184586123657285604061875653909567822328914065337797733444640351518775487649819978262363617265797982843179630888729407238496650987720428708217115257989007867331698397
e2=9647291
解题代码：
from Crypto.Util.number import long_to_bytes
from gmpy2 import gmpy2
c1=22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361
n=22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801
e1=11187289
c2=18702010045187015556548691642394982835669262147230212731309938675226458555210425972429418449273410535387985931036711854265623905066805665751803269106880746769003478900791099590239513925449748814075904017471585572848473556490565450062664706449128415834787961947266259789785962922238701134079720414228414066193071495304612341052987455615930023536823801499269773357186087452747500840640419365011554421183037505653461286732740983702740822671148045619497667184586123657285604061875653909567822328914065337797733444640351518775487649819978262363617265797982843179630888729407238496650987720428708217115257989007867331698397
e2=9647291
r,a,b = gmpy2.gcdext(e1, e2) # r 是 e1 和 e2 的最大公约数
# a 和 b 是扩展欧几里得算法中找到的系数，使得 r = a * e1 + b * e2 成立
m = (pow(c1,a,n)*pow(c2,b,n)) % n
print(long_to_bytes(m))
# b'flag{49d91077a1abcb14f1a9d546c80be9ef}'
3.10 选择密文攻击
1、场景介绍
设想攻击者拥有一个解密机和一个密文C，而这个解密机可以解除了C以外的任意密文。 解释：有没有觉得很奇怪，为什么可以解密除了C以外的任意密文，是不是为了做题故意这么设计的。其实是解密机基于安全考虑会拒绝同样的密文重复输入。攻击者发现一段密文c，直接输入到解密机被拒绝，因为密文c以前被解密过。
2、RSA具有延展性
对密文进行特定形式的代数运算，结果会反映到解密的明文中。比如有两段明文 m1和 m2，加密后产生c1=m1^e mod N和c2=m2^e mod N，那么(c1·c2)解密会得到什么？ 看等式：(C1·C2)d≡m1(ed)·m2^(ed)≡m1·m2(mod N)所以两段密文的乘积解密后得到的明文，等于两段明文的乘积，这一特性为选择密文攻击提供了机会。
3、攻击过程
假定攻击者截获的密文为C=M^e mod N，无法通过解密机获取其明文。
选择任意X与N互素。
计算Y = (C*X^e) mod N
得到的Y之前没有被解密机解密过，不会拒绝，发给解密机得到：Z = Y^d mod N
Z = Y^d mod N = (C·X^e mod N)^d mod N = C^d · (X^e) ^d mod N = M*X mod N
而X与N互素，可以求出其逆元X^(-1)，则M = Z*X^(-1) mod N
4、代码实现
import random
def attack(C, e, N):
# 选择任意X与N互素
while True:
X = random.randint(2, N - 1)
if gcd(X, N) == 1:
break
# 计算Y = C * X^e mod N
Y = (C*X**e) % N
# 发送给解密机得到Z = Y^d mod N
# Z = pow(Y, d, N)
# 求X的逆元X^(-1)
X_inv = pow(X, -1, N)
# 计算M = Z * X^(-1) mod N
M = (Z * X_inv) % N
return M
5、例题
RSA401 CCA选择密文攻击
程序提供了(n,e,c)，并且n不能直接分解，而程序还提供了解密功能，除了c，其他的都能解密。
解题：
选择X=2，计算Y=C * 2^e mod N，把Y发送给服务器解密得到Z，然后求出2在模N下的逆元2^(-1)，则 M = Z * 2^(-1) mod N
然后把Y发送给题目提供的解密程序得到Y的明文Z
最后：M = (Z * 2^(-1)) mod n
3.11 相关消息攻击
相关消息攻击就是如果两个消息之间存在某种线性关系，并且在相同的n和e下进行RSA加密，那么就有可能恢复出这两个消息，即m和a∗m+b(b!=0)两个明文在相同的(n,e)下进行RSA加密，那么m就可以破解。
c1=m1^e mod n
⇒
c1=(f(m2) mod n)^e mod n
于是：
显然，m2是上述两个多项式的根，因此它们有一个公因子x∗m2(g1( x )=0,g2(x)=0 ) 所以我们gcd(g1,g2) 就能得到m2，根据线性关系就能得到m1。
注意e=3时，最大公因子一定是线性的。
例题：2023 SICTF#Round2-签到题来咯！
from secret import flag
from Crypto.Util.number import *
m = bytes_to_long(flag)
p = getPrime(1024)
q = getPrime(1024)
e = getPrime(10)
n = p*q
c1 = pow(114*m+2333,e,n)
c2 = pow(514*m+4555,e,n)
print(f'n = {n}')
print(f'c1 = {c1}')
print(f'c2 = {c2}')
# n = 18993579800590288733556762316465854395650778003397512624355925069287661487515652428099677335464809283955351330659278915073219733930542167360381688856732762552737791137784222098296804826261681852699742456526979985201331982720936091963830799430264680941164508709453794113576607749669278887105809727027129736803614327631979056934906547015919204770702496676692691248702461766117271815398943842909579917102217310779431999448597899109808086655029624478062317317442297276087073653945439820988375066353157221370129064423613949039895822016206336117081475698987326594199181180346821431242733826487765566154350269651592993856883
# c1 = 3089900890429368903963127778258893993015616003863275300568951378177309984878857933740319974151823410060583527905656182419531008417050246901514691111335764182779077027419410717272164998075313101695833565450587029584857433998627248705518025411896438130004108810308599666206694770859843696952378804678690327442746359836105117371144846629293505396610982407985241783168161504309420302314102538231774470927864959064261347913286659384383565379900391857812482728653358741387072374314243068833590379370244368317200796927931678203916569721211768082289529948017340699194622234734381555103898784827642197721866114583358940604520
# c2 = 6062491672599671503583327431533992487890060173533816222838721749216161789662841049274959778509684968479022417053571624473283543736981267659104310293237792925201009775193492423025040929132360886500863823523629213703533794348606076463773478200331006341206053010168741302440409050344170767489936681627020501853981450212305108039373119567034948781143698613084550376070802084805644270376620484786155554275798939105737707005991882264123315436368611647275530607811665999620394422672764116158492214128572456571553281799359243174598812137554860109807481900330449364878168308833006964726761878461761560543284533578701661413931
感官上能看出m1和m2存在某种线性关系，所以是相关消息攻击(Franklin-Reiter)
需要注意的是，这里e是10bit素数中的一个，遍历一下10bit素数就行。
解题代码：
from Crypto.Util.number import *
import binascii
n =
c1 =
c2 =
def franklinReiter(n,e,c1,c2):
PR.<x> = PolynomialRing(Zmod(n))
g1 = (114*x+2333)^e - c1
g2 = (514*x+4555)^e - c2
def gcd(g1, g2):
while g2:
g1, g2 = g2, g1 % g2
return g1.monic()
return -gcd(g1, g2)[0]
def get_all_10_bit_primes(): # 求10bit的所有素数
return [i for i in range(2**9, 2**10) if isPrime(i)]
e_all = get_all_10_bit_primes()
print(e_all)
for e in e_all:
m=franklinReiter(n,e,c1,c2)
flag = long_to_bytes(int(m))
if b'SICTF' in flag:
print(flag)
break
print("over")
# SICTF{hhh!!franklin_reiter_is_easy}
3.12 Coppersmith's High Bits Attack
本方法由Don Coppersmith提出，如果已知明文的很大部分，即m=m0+x，已知m0或组成n中一个大素数的高位，就可以对私钥进行攻击。一般，对于1024位的大素数，只需要知道640 位即可成功攻击。攻击的详细实现，见：https://github.com/mimoo/RSA-and-LLL-attacks
2024网鼎杯-青龙组：crypto1
from Crypto.Util.number import *
from secret import flag
p = getPrime(512)
q = getPrime(512)
n = p * q
d = getPrime(299)
e = inverse(d,(p-1)*(q-1))
m = bytes_to_long(flag)
c = pow(m,e,n)
hint1 = p >> (512-70)
hint2 = q >> (512-70)
print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")
print(f"hint1 = {hint1}")
print(f"hint2 = {hint2}")
n = 107892573713246099817538936816485851035053538530228178586297516104462355899705036416845549988000543254717342505493461294554541098637839010844819316344397595836466293908827352240852019945855020602201742694540642287347823025883131162483705106324646432257707195307227627208850506071985510840207212074649893852289
e = 106026779355993573435326995058838659695563314723896436315704944869047461810171317853485834578907922477225219563648678852066399786593146779733369104463848604460901829459576565561299893410357693816050012889075185831684944657633027210516389798278082334754603104594287285628025433146548664548308055805258965566543
c = 74801258971353592087655273561994005413765184821038662179717923534370360999501931581907306714940348903440446458261785275314423770475637996343903355116249112854972152857616186571871846360852766323423533588570164035716759526288174656142706806500076294386681134096440267098094279442917447969106043371238327287569
hint1 = 895381917907042032873
hint2 = 934258518638868635029
解题脚本：
import time
time.clock = time.time
debug = True
strict = False
helpful_only = True
dimension_min = 7 # 如果晶格达到该尺寸，则停止移除
# 显示有用矢量的统计数据
def helpful_vectors(BB, modulus):
nothelpful = 0
for ii in range(BB.dimensions()[0]):
if BB[ii,ii] >= modulus:
nothelpful += 1
print (nothelpful, "/", BB.dimensions()[0], " vectors are not helpful")
# 显示带有 0 和 X 的矩阵
def matrix_overview(BB, bound):
for ii in range(BB.dimensions()[0]):
a = ('%02d ' % ii)
for jj in range(BB.dimensions()[1]):
a += '0' if BB[ii,jj] == 0 else 'X'
if BB.dimensions()[0] < 60:
a += ' '
if BB[ii, ii] >= bound:
a += '~'
#print (a)
# 尝试删除无用的向量
# 从当前 = n-1（最后一个向量）开始
def remove_unhelpful(BB, monomials, bound, current):
# 我们从当前 = n-1（最后一个向量）开始
if current == -1 or BB.dimensions()[0] <= dimension_min:
return BB
# 开始从后面检查
for ii in range(current, -1, -1):
# 如果它没有用
if BB[ii, ii] >= bound:
affected_vectors = 0
affected_vector_index = 0
# 让我们检查它是否影响其他向量
for jj in range(ii + 1, BB.dimensions()[0]):
# 如果另一个向量受到影响：
# 我们增加计数
if BB[jj, ii] != 0:
affected_vectors += 1
affected_vector_index = jj
# 等级：0
# 如果没有其他载体最终受到影响
# 我们删除它
if affected_vectors == 0:
#print ("* removing unhelpful vector", ii)
BB = BB.delete_columns([ii])
BB = BB.delete_rows([ii])
monomials.pop(ii)
BB = remove_unhelpful(BB, monomials, bound, ii-1)
return BB
# 等级：1
#如果只有一个受到影响，我们会检查
# 如果它正在影响别的向量
elif affected_vectors == 1:
affected_deeper = True
for kk in range(affected_vector_index + 1, BB.dimensions()[0]):
# 如果它影响哪怕一个向量
# 我们放弃这个
if BB[kk, affected_vector_index] != 0:
affected_deeper = False
# 如果没有其他向量受到影响，则将其删除，并且
# 这个有用的向量不够有用
#与我们无用的相比
if affected_deeper and abs(bound - BB[affected_vector_index, affected_vector_index]) < abs(bound - BB[ii, ii]):
#print ("* removing unhelpful vectors", ii, "and", affected_vector_index)
BB = BB.delete_columns([affected_vector_index, ii])
BB = BB.delete_rows([affected_vector_index, ii])
monomials.pop(affected_vector_index)
monomials.pop(ii)
BB = remove_unhelpful(BB, monomials, bound, ii-1)
return BB
# nothing happened
return BB
"""
Returns:
* 0,0 if it fails
* -1，-1 如果 "strict=true"，并且行列式不受约束
* x0,y0 the solutions of `pol`
"""
def boneh_durfee(pol, modulus, mm, tt, XX, YY):
"""
Boneh and Durfee revisited by Herrmann and May
在以下情况下找到解决方案：
* d < N^delta
* |x|< e^delta
* |y|< e^0.5
每当 delta < 1 - sqrt（2）/2 ~ 0.292
"""
# substitution (Herrman and May)
PR.<u, x, y> = PolynomialRing(ZZ) #多项式环
Q = PR.quotient(x*y + 1 - u) # u = xy + 1
polZ = Q(pol).lift()
UU = XX*YY + 1
# x-移位
gg = []
for kk in range(mm + 1):
for ii in range(mm - kk + 1):
xshift = x^ii * modulus^(mm - kk) * polZ(u, x, y)^kk
gg.append(xshift)
gg.sort()
# 单项式 x 移位列表
monomials = []
for polynomial in gg:
for monomial in polynomial.monomials(): #对于多项式中的单项式。单项式（）：
if monomial not in monomials: # 如果单项不在单项中
monomials.append(monomial)
monomials.sort()
# y-移位
for jj in range(1, tt + 1):
for kk in range(floor(mm/tt) * jj, mm + 1):
yshift = y^jj * polZ(u, x, y)^kk * modulus^(mm - kk)
yshift = Q(yshift).lift()
gg.append(yshift) # substitution
# 单项式 y 移位列表
for jj in range(1, tt + 1):
for kk in range(floor(mm/tt) * jj, mm + 1):
monomials.append(u^kk * y^jj)
# 构造格 B
nn = len(monomials)
BB = Matrix(ZZ, nn)
for ii in range(nn):
BB[ii, 0] = gg[ii](0, 0, 0)
for jj in range(1, ii + 1):
if monomials[jj] in gg[ii].monomials():
BB[ii, jj] = gg[ii].monomial_coefficient(monomials[jj]) * monomials[jj](UU,XX,YY)
#约化格的原型
if helpful_only:
# #自动删除
BB = remove_unhelpful(BB, monomials, modulus^mm, nn-1)
# 重置维度
nn = BB.dimensions()[0]
if nn == 0:
print ("failure")
return 0,0
# 检查向量是否有帮助
if debug:
helpful_vectors(BB, modulus^mm)
# 检查行列式是否正确界定
det = BB.det()
bound = modulus^(mm*nn)
if det >= bound:
print ("We do not have det < bound. Solutions might not be found.")
print ("Try with highers m and t.")
if debug:
diff = (log(det) - log(bound)) / log(2)
print ("size det(L) - size e^(m*n) = ", floor(diff))
if strict:
return -1, -1
else:
print ("det(L) < e^(m*n) (good! If a solution exists < N^delta, it will be found)")
# display the lattice basis
if debug:
matrix_overview(BB, modulus^mm)
# LLL
if debug:
print ("optimizing basis of the lattice via LLL, this can take a long time")
#BB = BB.BKZ(block_size=25)
BB = BB.LLL()
if debug:
print ("LLL is done!")
# 替换向量 i 和 j ->多项式 1 和 2
if debug:
print ("在格中寻找线性无关向量")
found_polynomials = False
for pol1_idx in range(nn - 1):
for pol2_idx in range(pol1_idx + 1, nn):
# 对于i and j, 构造两个多项式
PR.<w,z> = PolynomialRing(ZZ)
pol1 = pol2 = 0
for jj in range(nn):
pol1 += monomials[jj](w*z+1,w,z) * BB[pol1_idx, jj] / monomials[jj](UU,XX,YY)
pol2 += monomials[jj](w*z+1,w,z) * BB[pol2_idx, jj] / monomials[jj](UU,XX,YY)
# 结果
PR.<q> = PolynomialRing(ZZ)
rr = pol1.resultant(pol2)
if rr.is_zero() or rr.monomials() == [1]:
continue
else:
print ("found them, using vectors", pol1_idx, "and", pol2_idx)
found_polynomials = True
break
if found_polynomials:
break
if not found_polynomials:
print ("no independant vectors could be found. This should very rarely happen...")
return 0, 0
rr = rr(q, q)
# solutions
soly = rr.roots()
if len(soly) == 0:
print ("Your prediction (delta) is too small")
return 0, 0
soly = soly[0][0]
ss = pol1(q, soly)
solx = ss.roots()[0][0]
return solx, soly
def example():
############################################
# 随机生成数据
##########################################
#start_time =time.perf_counter
start =time.clock()
size=512
length_N = 2*size;
ss=0
s=70;
M=1 # the number of experiments
delta = 299/1024
# p = random_prime(2^512,2^511)
for i in range(M):
N = 107892573713246099817538936816485851035053538530228178586297516104462355899705036416845549988000543254717342505493461294554541098637839010844819316344397595836466293908827352240852019945855020602201742694540642287347823025883131162483705106324646432257707195307227627208850506071985510840207212074649893852289
e = 106026779355993573435326995058838659695563314723896436315704944869047461810171317853485834578907922477225219563648678852066399786593146779733369104463848604460901829459576565561299893410357693816050012889075185831684944657633027210516389798278082334754603104594287285628025433146548664548308055805258965566543
c = 74801258971353592087655273561994005413765184821038662179717923534370360999501931581907306714940348903440446458261785275314423770475637996343903355116249112854972152857616186571871846360852766323423533588570164035716759526288174656142706806500076294386681134096440267098094279442917447969106043371238327287569
hint1 = 895381917907042032873 # p高位
hint2 = 934258518638868635029 # q高位
# 解密指数d的指数( 最大0.292)
m = 7 # 格大小（越大越好/越慢）
t = round(((1-2*delta) * m)) # 来自 Herrmann 和 May 的优化
X = floor(N^delta) #
Y = floor(N^(1/2)/2^s) # 如果 p、 q 大小相同，则正确
for l in range(int(hint1),int(hint1)+1):
print('\n\n\n l=',l)
pM=l;
p0=pM*2^(size-s)+2^(size-s)-1;
q0=N/p0;
qM=int(q0/2^(size-s))
A = N + 1-pM*2^(size-s)-qM*2^(size-s);
#A = N+1
P.<x,y> = PolynomialRing(ZZ)
pol = 1 + x * (A + y) #构建的方程
# Checking bounds
#if debug:
#print ("=== 核对数据 ===")
#print ("* delta:", delta)
#print ("* delta < 0.292", delta < 0.292)
#print ("* size of e:", ceil(log(e)/log(2))) # e的bit数
# print ("* size of N:", len(bin(N))) # N的bit数
#print ("* size of N:", ceil(log(N)/log(2))) # N的bit数
#print ("* m:", m, ", t:", t)
# boneh_durfee
if debug:
##print ("=== running algorithm ===")
start_time = time.time()
solx, soly = boneh_durfee(pol, e, m, t, X, Y)
if solx > 0:
#print ("=== solution found ===")
if False:
print ("x:", solx)
print ("y:", soly)
d_sol = int(pol(solx, soly) / e)
ss=ss+1
print ("=== solution found ===")
print ("p的高比特为：",l)
print ("q的高比特为：",qM)
print ("d=",d_sol)
if debug:
print("=== %s seconds ===" % (time.time() - start_time))
#break
print("ss=",ss)
#end=time.process_time
end=time.clock()
print('Running time: %s Seconds'%(end-start))
if __name__ == "__main__":
example()
运行脚本后恢复d，题目给了p的高70位，所以exp中s为70
得到d之后正常解密恢复明文：
3.13 RSA LSB Oracle
这是一种侧信道攻击的方法。如果可以控制解密机，可以使用同一个未知的私钥对任意密文进行解密，那么只要知道明文的最后一位，就可以使用这种攻击方法在O（logn）的时间内 解出任意密文对应的明文。
已知c=m^e mod n，那么将c乘上2^e mod n，发送给服务器，服务器对它进行解密，即可得到
(m^e ·2^e)^d mod n=(2m)^(ed) mod n= 2m mod n
显然，2m是一个偶数，即末尾位为0。由于0<m<n，则可以得到0<2m<2n，因此2m mod n只存在 两种情况：
2m,0＜2m＜n
2m-n,n≤2m＜2n
其中，2m的情况和2m-n=0的情况时，结果是一个偶数，其他情况下是个奇数。这样，便可以根据奇偶性即获得的结果的最后1位求得m和n/2之间的大小关系：当获得的结果是偶数时，0＜m≤n/2，否则n/2<m<n。确定了m与n/2的大小后，便可以求得m的最高位是0还是1。将乘上2^e mod n后的c当作新的c，继续进行上述操作，相当于使用二分搜索的思想不断缩小搜索的范 围，即可一位一位地将m的值恢复出来。
使用伪代码描述算法如下：
l = 0
r = n
while(l!=r):
c = c*pow(2,e,n) % n
if get_m_lsb(c) == 0:
r = (l+r)/2
else:
l = (l+r)/2
标签：总结,gmpy2,BB,RSA,ii,print,c1,密码学,mod From： https://www.cnblogs.com/o-O-oO/p/18640749原创 北渚 南有禾木