以下是RSA的基础简单题型
dp dq泄露：（dp=d%(p-1))
示例题干：
p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852(求解m)解法：
无e,比较特殊的情况，知道p,q，其实我挺好奇为什么不用CRT解决
dp是d%（p-1),无绝对的2边大小
这里引入一种基本常用的方法：将ka视作（mod a)
cd=cdp(modp)，把dp展开就是cd//c(p-1),欧拉约去p-1,同理
相减得到cdp-cdq=k2q-k1p,得到cdp-cdq=k2q(modp),(c*…)invert(q,p)=k2
将k2带回k2的上式得到(cd=m=cdq+(cdp-cdq)invert(q,p))q (modn)
注意一下先规约变小再算
import gmpy2
p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041
c=24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852
m=pow(c,dp,p)
n=pow(c,dq,q)
t=gmpy2.invert(p,q)
m=((((m-n)*t)%p)*p+m)%(p*q)
#不用inverse_mod的话，用pow(,-1,)也可以，现在有gmpy,用gmpy2.invert
from Crypto.Util.number import long_to_bytes
m=11630208090204506176302961171539022042721137807911818876637821759101
flag=long_to_bytes(m)
print(flag)
#其实可以用c**dq=c**d mod p的2个式子CRT，就会得到c**d的最小解，往后推dp泄露：
示例题干：
e = 65537
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657
c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751解法：
这里引入爆破消元，难点在于估计大小
引入一种思想：看见d往e*d上引，再往phi上引
dp+k1(p-1)=d,edp=ed-k1(p-1)这里省去了ek1的e,都未知，无所谓
e*d=(p-1)(q-1)k2+1,带回
e**dp+1=(p-1)(k2q-k2-k1)
dp=d%(p-1),dp小于(p-1),可以得到后面的串小于e,爆破他
整数爆破，结果是整数，就正确了
from Crypto.Util.number import long_to_bytes
from Crypto.Util.number import *
import gmpy2
e = 65537
n=248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp=905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657
c=140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751
a=dp*e-1
for x in range(1,e):
if a%x==0:
p=a//x+1#一定要用//不然返回的不是整数，后面pow不了
if n%p==0:
q=n//p
break
else:
continue
l=(p-1)*(q-1)
d=gmpy2.powmod(e,-1,l)
m=gmpy2.powmod(c,d,n)#实测gmpy2要快，直接就出了结果
print(long_to_bytes(m).strip())
input("写完答案后按enter退出:")
低广播指数攻击：
示例题干：
简称一个e加密多次
公共指数 $e$$3$
用于加密的 RSA 指数模数 $N_1$$1195651$
第一个用户的 RSA 模数密文 $C_1$$641872$
截获的密文 1
模数 $N_2$$1195657$
第二个用户的 RSA 模数密文 $C_2$$262319$
截获的密文 2模数 $N_3$$1195663$
第三个用户的 RSA 模数密文 $C_3$$1083437$
截获的密文 3
不用管密文（）解法：
#注意，CRT得到的是符合的最小解，实际上方程太少，规约不足，可能得到偏小
#这个时候x=x+k(n1*n2*n3*n4...)把他加会去
n_1=1195651
n_2=1195657
n_3=1195663
c_1=641872
c_2=262319
c_3=1083437
e=3
model=[n_1,n_2,n_3]
ciphertext=[c_1,c_2,c_3]
m_point=crt(ciphertext,model)
m=m_point.nth_root(e)共模攻击：
示例题目：
简称一个n用于多组加密
c1=22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361
n=22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801
e1=11187289
c2=18702010045187015556548691642394982835669262147230212731309938675226458555210425972429418449273410535387985931036711854265623905066805665751803269106880746769003478900791099590239513925449748814075904017471585572848473556490565450062664706449128415834787961947266259789785962922238701134079720414228414066193071495304612341052987455615930023536823801499269773357186087452747500840640419365011554421183037505653461286732740983702740822671148045619497667184586123657285604061875653909567822328914065337797733444640351518775487649819978262363617265797982843179630888729407238496650987720428708217115257989007867331698397
e2=9647291解法：
即我们有c1=m1e1(modn),c2=m2e2(modn),这个时候想到构造e1s1+e2s2=1
这样我们自然可以消掉e1,e2，得到c1s1*c2s2=m(modn)（可以使用模规约使进一步变小）
构造s1,s2:想办法把其中一个s放进c的模：s1(c1+c2)+c2(s2-s1)=1
就是s1*(c1+c2)=1(modc2),构造出模逆元，这届inverse得解
可以直接对2边取模s1,直接得s2是c2invert()
from Crypto.Util.number import *
c_1=22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361
c_2=18702010045187015556548691642394982835669262147230212731309938675226458555210425972429418449273410535387985931036711854265623905066805665751803269106880746769003478900791099590239513925449748814075904017471585572848473556490565450062664706449128415834787961947266259789785962922238701134079720414228414066193071495304612341052987455615930023536823801499269773357186087452747500840640419365011554421183037505653461286732740983702740822671148045619497667184586123657285604061875653909567822328914065337797733444640351518775487649819978262363617265797982843179630888729407238496650987720428708217115257989007867331698397
e_1=11187289
e_2=9647291
n=22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801
s_1=pow(e_1-e_2,-1,e_2)
s_2=(1-e_1*s_1)//e_2
m=(pow(c_1,s_1,n)*pow(c_2,s_2,n))%n
print(long_to_bytes(m))维纳攻击：
示例题目：
此时e过大
N = 101991809777553253470276751399264740131157682329252673501792154507006158434432009141995367241962525705950046253400188884658262496534706438791515071885860897552736656899566915731297225817250639873643376310103992170646906557242832893914902053581087502512787303322747780420210884852166586717636559058152544979471
e = 46731919563265721307105180410302518676676135509737992912625092976849075262192092549323082367518264378630543338219025744820916471913696072050291990620486581719410354385121760761374229374847695148230596005409978383369740305816082770283909611956355972181848077519920922059268376958811713365106925235218265173085
c= 266367266471585923035346980467315672043839080179258966276144775106482166900911004389808367589961536843898187180012055918063504477273067284037318171833017082239907978935274619109926579983150571298634653886980563681026116724117473808890951091279814434050754571460308728024448607359710055618866766919226511213734
import hashlib
flag = "flag{" + hashlib.md5(hex(d)).hexdigest() + "}"解法：
一般通过e判断d.e大d小，d<1/3n(1/4),这个是实际中得到的数据，经验性
看见小，格基来啦，这里不能直接用，没有d相关的方程
与d相关的只有ed,ed=(p-1)(q-1)k1+1,再得到ed-k1n=k1(p+q-1)+1
这个时候e…可以得到p+q,就想到再取一维，使他的长度相对短,LLL可以解出
d*(e,?)-k1(n,?)=(ed-k1n,d?),这里第1个？不能取1，结果是isqrt(n)级别，不够小
这里用t来控制他，d(e,t)-k1(n,0)=(…,t*d),用t的可能性来控制向量的可能大小
现在我们来看t怎么选择
ed=k1(p-1)(q-1)+1,得到k1=ed/(p-1)(q-1),k1=ed/n,这里的e大，近似去n,k的量级和d相近
得到ed-k1n=(p+q-1)k1+1=d*isqrt(n)
直接t取isqrt(n),回到矩阵构造
d*(e,isqrt(n))-k1(n,0)=(…,isqrt(n))，这里【1】更方便，直接得到td
from Crypto.Util.number import *
e=37397
n=115195246661899296028639479214891325305115740197043517335744054358241094309453507902975188178958594534737913378511105559677196176245627566192707230263564388898177072490991316742084693954005591101717858650082201767673318306285700462874758855629953791419053455748757840145087820046579513146121357780217011411123
c=75248333191595131862397992185034538712723287571693010607014801203479825437231436679635683920065418666985573137378225193369514573772053036481523021004953721256377139176939964793576631137392403005819268917976130614632896893172916838700080521568126949999158133434188929913824597791220886585840858909284559275439
G=Matrix(ZZ,2,2,[e,isqrt(n),n,0])#建立矩阵的标准形式
L=G.LLL()
for row in L:#查找所有
if row[1]%(isqrt(n))==0:#row[1]是td
d=row[1]//(isqrt(n))#整除检验
break
print(d)
m=pow(c,d,n)
m=long_to_bytes(m)
print(m)BF攻击（扩展）：
可以不理解原理，如果明确了e大的模型，维纳打不出来，用这个（改一下）
#这是维纳攻击得扩展，比维纳攻击得范围大一点，看见e大但维纳攻击打不下来可以试一下
#实现起来非常复杂，这里只给一个工具，意识到要用就用
#这是维纳攻击得扩展，比维纳攻击得范围大一点，看见e大但维纳攻击打不下来可以试一下
#实现起来非常复杂，这里只给一个工具，意识到要用就用
#./sage
import time
from Crypto.Util.number import *
"""
Setting debug to true will display more informations
about the lattice, the bounds, the vectors...
"""
debug = True
"""
Setting strict to true will stop the algorithm (and
return (-1, -1)) if we don't have a correct
upperbound on the determinant. Note that this
doesn't necesseraly mean that no solutions
will be found since the theoretical upperbound is
usualy far away from actual results. That is why
you should probably use `strict = False`
"""
strict = False
"""
This is experimental, but has provided remarkable results
so far. It tries to reduce the lattice as much as it can
while keeping its efficiency. I see no reason not to use
this option, but if things don't work, you should try
disabling it
"""
helpful_only = True
dimension_min = 7 # stop removing if lattice reaches that dimension
############################################
# Functions
##########################################
# display stats on helpful vectors
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")
# display matrix picture with 0 and 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)
# tries to remove unhelpful vectors
# we start at current = n-1 (last vector)
def remove_unhelpful(BB, monomials, bound, current):
# end of our recursive function
if current == -1 or BB.dimensions()[0] <= dimension_min:
return BB
# we start by checking from the end
for ii in range(current, -1, -1):
# if it is unhelpful:
if BB[ii, ii] >= bound:
affected_vectors = 0
affected_vector_index = 0
# let's check if it affects other vectors
for jj in range(ii + 1, BB.dimensions()[0]):
# if another vector is affected:
# we increase the count
if BB[jj, ii] != 0:
affected_vectors += 1
affected_vector_index = jj
# level:0
# if no other vectors end up affected
# we remove it
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
# level:1
# if just one was affected we check
# if it is affecting someone else
elif affected_vectors == 1:
affected_deeper = True
for kk in range(affected_vector_index + 1, BB.dimensions()[0]):
# if it is affecting even one vector
# we give up on this one
if BB[kk, affected_vector_index] != 0:
affected_deeper = False
# remove both it if no other vector was affected and
# this helpful vector is not helpful enough
# compared to our unhelpful one
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 if `strict=true`, and determinant doesn't bound
* x0,y0 the solutions of `pol`
"""
def boneh_durfee(pol, modulus, mm, tt, XX, YY):
"""
Boneh and Durfee revisited by Herrmann and May
finds a solution if:
* d < N^delta
* |x| < e^delta
* |y| < e^0.5
whenever 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-shifts
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-shifts list of monomials
monomials = []
for polynomial in gg:
for monomial in polynomial.monomials():
if monomial not in monomials:
monomials.append(monomial)
monomials.sort()
# y-shifts (selected by Herrman and May)
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-shifts list of monomials
for jj in range(1, tt + 1):
for kk in range(floor(mm/tt) * jj, mm + 1):
monomials.append(u^kk * y^jj)
# construct lattice 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)
# Prototype to reduce the lattice
if helpful_only:
# automatically remove
BB = remove_unhelpful(BB, monomials, modulus^mm, nn-1)
# reset dimension
nn = BB.dimensions()[0]
if nn == 0:
print ("failure")
return 0,0
# check if vectors are helpful
if debug:
helpful_vectors(BB, modulus^mm)
# check if determinant is correctly bounded
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.LLL()
if debug:
print ("LLL is done!")
# transform vector i & j -> polynomials 1 & 2
if debug:
print ("looking for independent vectors in the lattice")
found_polynomials = False
for pol1_idx in range(nn - 1):
for pol2_idx in range(pol1_idx + 1, nn):
# for i and j, create the two polynomials
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)
# resultant
PR.<q> = PolynomialRing(ZZ)
rr = pol1.resultant(pol2)
# are these good polynomials?
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(N,e,delta,m=None):
############################################
# How To Use This Script
##########################################
#
# Lattice (tweak those values)
#
# you should tweak this (after a first run), (e.g. increment it until a solution is found)
m = 4 if m == None else m # size of the lattice (bigger the better/slower)
# you need to be a lattice master to tweak these
t = int((1-2*delta) * m) # optimization from Herrmann and May
X = 2*floor(N^delta) # this _might_ be too much
Y = floor(N^(1/2)) # correct if p, q are ~ same size
#
# Don't touch anything below
#
# Problem put in equation
P.<x,y> = PolynomialRing(ZZ)
A = int((N+1)/2)
pol = 1 + x * (A + y)
#
# Find the solutions!
#
# Checking bounds
if debug:
print ("=== checking values ===")
print ("* delta:", delta)
print ("* delta < 0.292", delta < 0.292)
print ("* size of e:", int(log(e)/log(2)))
print ("* size of N:", int(log(N)/log(2)))
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)
# found a solution?
if solx > 0:
print ("=== solution found ===")
if False:
print ("x:", solx)
print ("y:", soly)
d = int(pol(solx, soly) / e)
print ("private key found:", d)
else:
print ("=== no solution was found ===")
if debug:
print("=== %s seconds ===" % (time.time() - start_time))
return d
if __name__ == "__main__":
n=int(input("输入n:"))
e=int(input("输入e:"))
c=int(input("输入c:"))
# the hypothesis on the private exponent (the theoretical maximum is 0.292)
delta = 0.28 # this means that d < N^delta
d = example(n,e,delta)
print(long_to_bytes(int(pow(c,d,n))))
图像解密：
#其实就是对每一个像素的RGB（红，绿，蓝）进行加密
from PIL import Image
import numpy as np#引入图像处理的必要库
p=
q=
n=p*q
c=
e=
l=(p-1)*(q-1)
d=pow(e,-1,l)
encrypted_array=np.load("encrypted_image.npy",allow_pickle=True)
#加载，使用图像为矩阵，后面为允许加载
h,w,_=encrypted_array.shape#获取长，宽，通道数（色彩数）
decrypted_array=np.zeros((h,w,3),dtype=np.uint8)#创建空形状，并且为2**8（256）像素
for i in range(h):
for j in range(w):#遍历图像
r_enc,g_enc,b_enc=encrypted_array[i,j]#提取每一个的RGB
r=pow(r_enc,d,n)%256#像素上限是256（&0xff也可以，上限255)
g=pow(g_enc,d,n)%256
b=pow(b_enc,d,n)%256
decrypted_array[i,j]=[r,g,b]#储存已经系欸获得图像
decrypted_img=Image.fromarray(decrypted_array,"RGB")#大写I
decrypted_img.save("decrypted_flag.png")#保存于当前目录，也可以（“desktop/../')来保存到具体地址
多项式解密：
示例题目：
from Crypto.Util.number import *
flag = b"xxx"
assert len(flag) < 64
p = getPrime(128)
q = getPrime(128)
n = p * q
e = 65537
R_.<t> = PolynomialRing(Zmod(p*q))
R.<x> = R_.quotient(t**8 - 1)
f = sum(bytes_to_long(flag[i:i+8])*x**(i//8) for i in range(0, len(flag), 8))
c = f**e
print("p =", p)
print("q =", q)
print("e =", e)
print("c =", c)
# p = 211381997162225534712606028333737323293
# q = 291844321073146066895055929747029949743
# e = 65537
# c = 40882135200347703593754473549436673146387957409540306808209934514868940052992*x^7 + 13673861744940819052324430973254902841262867940443611208276249322420769352299*x^6 + 14825937682750201471490037222143248112539971745568733623844924679519292569979*x^5 + 38679688295547579683397975810830690182925250157203662993481664387755200460738*x^4 + 48188456496545346035512990878010917911654453288374940837147218298761674630209*x^3 + 573073037892837477865699910635548796182825197336726898256762153949994844160*x^2 + 33191976337303879621137795936787377133622652419928253776624421127421475322069*x + 46680445255028101113817388282005859237776046219558912765486646689142241483104解法：
多项式背景下的RSA，掌握这个就是掌握了基础的RSA了
不必忙着去补环之类的知识，略微了解就行
from Crypto.Util.number import *
p = 211381997162225534712606028333737323293
q = 291844321073146066895055929747029949743
e = 65537
c = 40882135200347703593754473549436673146387957409540306808209934514868940052992*x^7 + 13673861744940819052324430973254902841262867940443611208276249322420769352299*x^6 + 14825937682750201471490037222143248112539971745568733623844924679519292569979*x^5 + 38679688295547579683397975810830690182925250157203662993481664387755200460738*x^4 + 48188456496545346035512990878010917911654453288374940837147218298761674630209*x^3 + 573073037892837477865699910635548796182825197336726898256762153949994844160*x^2 + 33191976337303879621137795936787377133622652419928253776624421127421475322069*x + 46680445255028101113817388282005859237776046219558912765486646689142241483104
R_.<t>=PolynomialRing(Zmod(p*q))
R.<x>=R_.quotient(t**8-1)#建立最高7次的商环
l=(p**8-1)*(q**8-1)#扩展欧拉公式，在多项式下对于最高次广泛可用
d=pow(e,-1,l)
f=(R(c)**d).lift()#将c置入R(x)中，再从环升回多项式
coefficients = f.list(8)
print(coefficients)
flag=b"".join(long_to_bytes(int(f.cofficients()[i]) for i in range(f.degree()+1)))
print(flag)Phi,e不互质的RSA
#不互质时，gcd(phi,e)得到的g是解的重数，即有g个e使c**e=m(mod n)
#思路就是把n分解成p,q,分开解2次，再用crt合并
n=
c=
e=
factors=list(n.factor())
p=factors[0][0]
q=factors[1][0]
l=(p-1)*(q-1)
g=gcd(e,l)
R.<x>=PolynomialRing(Zmod(p))
f=x**g-c
res1=f.roots(multiplicities=False)#这时因为g多重，解多重，使用这个直接无视重数
R.<x>=PolynomialRing(Zmod(q))
f=x**g-c
res2=f.roots(multiplicities=False)
res1 = Zmod(p)(c).nth_root(gcd, all=True)#先是把c转换到Zmod上，开g次，返回所有的g
res2 = Zmod(q)(c).nth_root(gcd, all=True)#否则会只返回一个开方结果
for i in res1:
for j in res2:
m=crt([p,q],[int(i),int(j)])
if m is not None:
try:
print()
except Exception as e:
continue高位泄露系列
p
#原理不用理解，，他针对的题型很明显，判断出来之后调用这个方法就行了
#主要是small_root的用法
n=
e=
p_high_number=
c=
p_high=p_high_number<<(512-p_high_number.bit_length())
R.<x>=PolynomialRing(Zmod(n))#建立模域
f=p_high+x
res=f.small_roots(X=2^256,beta=0.4，epsilon=0.02)#第1个系数是上限，isqrt(n),第2个是相对于模的幂数
if res!=[]:#有解 最后的系数是假设根的大小，更小更可能成功
p=ZZ(p_high+res[0])#不转化为整数，就可能在后面的invert出错
q=n//p
l=(p-1)*(q-1)
d=inverse_mod(e,l)
m=pow(c,d,n)
print(m)
#现在看来这个的原理是最难的，这里写下他的本质，是找到f与n的巨大公因子，解出当然是最大的
#对这里而言，解n显然是解不出的，只能从最大的公因子出发，得到p
d
c=
e=
n=
d_high=
X=2**L_low
#L_low为最大泄密位数
R.<x>=PolynomialRing(ZZ)
k_guess=(e*d_high)//n#就d低位的干扰而言，在除以phi后很小，可以在附近的范围爆破
for k in range(max(k_guess-2,0),k_guess+3):
f=e*(d_high+x)-k*n-1
res=f.small_root(X=X,ring=ZZ)
if res!=[]:
for ress,multiplicity in res:#后者是重数，与模上的形成差异，后者没有
d_low=int(ress)
d=d_high+d_low
m=c**d%n
print(m)
#此时的small_root因为不是在模域上，运用改变，这时是令结果尽可能小
#ring=ZZ使结果为整数，同时显示这是整数上，而非模上
#这里面的phi没有展开，而是近似视作n,这就是为什么没有出现负的问题
#可以如此近似的条件是p与q近似（一般p和q都是512），目标是找小根，LLL可以忍受这个误差
m
c=
n=
e=
m_high_number=
bits=
m_high=m_high_number<<(bits-m_high_number.bit_length())
R.<x>=PolynomialRing(Zmod(n))
f=(m_high+x)**e-c#构造f=0
res=f.small_root(X=2^bits,beta=1,epsilon=0.02)
if res!=[]:
m=m_high+int(res[0])
print(m)Schmidt-Samoa 密码体系
#不同之处在于此时的n=p**2*q,e=n,d=invert(n,(p-1)*(q-1))
#c=pow(m,n,n) m=pow(c,d,p*q)
#这里是初学者的例题，假设我们有c,n,e,d求m
#这里有一种处理方法，升至幂上，把(p-q)*(q-1)转化为p*q
from Crypto.Util.number import *
import gmpy2
n = input("输入n:")
d = input("输入d:")
c = input("输入c:")
pq = gmpy2.gcd(pow(2,n*d,n)-2,n)
print(long_to_bytes(pow(c,d,pq)))
#n*d=1 mod(p-1)*(q-1),升至幂上2**(n*d)=2 mod p*q
#接着使用2**(n*d)-2=0 mod p*q,转化为gcd问题解决(n=p*q*p mod p*q)
RSA处理junk padding
#有的时候明明解出来了，但是是无意义字符，这个时候没有内部提示，判断可能是flag前后有junk padding
from Crypto.Util.number import *
import re#这个可以去掉无效字符
p=105570604806073931560404187362816308950408774915960751676958845800335871518600455146040240314204606944641098914858159386588868785987100524581699043605351952348586132553458702298393907476955946990849442034441882748278181148503329309660427627438266645843535466462936882505833453738522673603026747578372964995367
q=143288358949089585215266953016278524463612148007190135453434243047032456958207376091733443584531919755660149037321119885867830905350806865862130270602628423547624190876473872180462192096873381471710899246073298439365336797201672838785511965949336068032011363484044690916570288372443303750426476423930352603827
e=33
c=2015688184356018702340063509729974600786840546364122789630929715337660295810961474144939260049892177486759513271253257458112942844435453563521353664294799145214833075575682837104619902593712323020851788866158742546117774717790910939444986189326649593286629046732910564929050955013637088916579175350308099506220813882274665233182543235264034038626524248300357250276274833999274982434790398489181021739913941634249265775997527901903799819193254397528348894700572493228638350806878366316533768758273322476421225382269304595973225131694907875536065669987510951854843686992445396860396865892650745594418900376500862332616
n=p*q
phi=(p-1)*(q-1)
d=pow(e,-1,phi)
m=pow(c,d,n)
m=long_to_bytes(m)
m=re.search(rb"flag\{.*?\}",m)#re.search()寻找,rb"flag\}(这里的\是转译，表示{是
print(m) #目标而非寻找符）开头，.*?表示找多个字符,\}停止于
#第一个}
