分类： RSA

RSA基础题型一览

以下是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)

c^d=c^dp(modp)，把dp展开就是c^d//c^(p-1),欧拉约去p-1,同理

相减得到c^dp-c^dq=k2q-k1p,得到c^dp-c^dq=k2q(modp),(c*…)invert(q,p)=k2

将k2带回k2的上式得到(c^d=m=c^dq+(c^dp-c^dq)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

高位泄露系列

#原理不用理解，，他针对的题型很明显，判断出来之后调用这个方法就行了
#主要是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

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可以忍受这个误差

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)                      #目标而非寻找符）开头，.*?表示找多个字符,\}停止于
                              #第一个}

2026年3月19日

RSA基础索引

RSA是目前最常见的基于计算复杂度的加密方式，题型多变，注重技巧和经验，以下是RSA的概念，基础的处理技巧和我浅薄的经验之谈。

1.RSA的概念：

本版块不负责模运算，位运算基础，移步信息安全数学基础

基础原理：解密困难来源于n的分解

$加密：密文=明文**e modn$

$记为：c=m**emodn$

$解密：明文=密文**dmodn$

$记为：c**d=m modn$

e是公钥，d是私钥，e,d,n是生成密钥对

n=p*q(p,q是2个大素数），phi=lcm(p-1,q-1)

e:1<e<phi,gcd(e,phi)=1;d:e*d=1 modphi

以上数据范围皆有考究，大小变化可能导致漏洞

#推荐去看快速幂算法欧拉公式，贝祖定理，CRT等基础

2。RSA处理

这里可以有基础了再回来感受，这是我的经验之谈

流程上RSA可以先考虑特殊解法，RSA的p,q相近，e过大，

n分解查询网站，签到必备：https://factordb.com

一般有以下几种题型：

1.可以通过变形构造解的RSA

2.可以通过大小爆破的RSA

3.模板型RSA

4，伪RSA,实则考点位于随机数等位置

2026年3月19日

分类： RSA

RSA基础题型一览

无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)

这里引入爆破消元，难点在于估计大小

引入一种思想：看见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,爆破他

整数爆破，结果是整数，就正确了

即我们有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()

一般通过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

RSA基础索引

1.RSA的概念：

c^d=c^dp(modp)，把dp展开就是c^d//c^(p-1),欧拉约去p-1,同理

相减得到c^dp-c^dq=k2q-k1p,得到c^dp-c^dq=k2q(modp),(c*…)invert(q,p)=k2

将k2带回k2的上式得到(c^d=m=c^dq+(c^dp-c^dq)invert(q,p))q (modn)