Crypto系列——RSA（二）

本文最后更新于：2023年11月28日下午

《从0开始的密码学世界生活》😋慢慢学密码方向

2023.09.14-

2023.10.27,重拾,感觉还是要跟着兴趣走吧😥😭😭😭😭😭😭😭

2023.11.14 😢

[RSA2]1(小明文攻击)

main

from Crypto.Util.number import *
from gmpy2 import *

flag = b'NSSCTF{******}'

p = getPrime(5120)
q = getPrime(5120)

n = p*q
e = 97
phi = (p-1)*(q-1)

m = bytes_to_long(flag)
c = powmod(m, e, n)

print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')

'''
n = 1392208858696945158251408085300402884210409327605255122395601049457847957306648819174395014931778575812308192875319127224095733396726388842605854427013313599830150182564652493067830031524869535522568868597852507293377043240832819715539722122306829543983051745406887140154364256267942350230636870212935356815475345989038318923389132101208917912083817520799490534351545373438629367819085151041702754019127891155542476560972125790519584018715794669416759039955180436830478697704458250990786586357019211642837879273967620287257818400267757312623543898635740200839249361087580046496969637043238450499583879116276661827372750638403042213043389905183760455450595752578482968202040860053524276678108325784161897719093223308370971388068813420487879756084379519128232693549989942550047529174783976176943482484756074638704076740157397067892580297182979526978967352014250386678155843772313996171396582929433057131989693861316408604436872931427368192437680361830753162284661119995125858203931094922686321756465463988790748131178263745308042820480140189644732824717255521633534750635979508673908361269979175726073254050574688259969290376926807033728165164896588540691889207252105903436659968119091774687841336252628343233161941187968365128093917171537997137001140227677728923114895809278926486615010954871408034272872411042537353956193868948909981683850857262457369506288525323882308421700421661036191853577105238753230479541719001794464585534292774768292358961920606891227776349593589481547577148801600196035588544512224775960892265021565124673788852875005526313525709353599584812394138968970647681759439523307392275602626903789154682706839530654070108096741181206975334567778238856983205004289416400671597321919876279909765650782227834097342294844294386380646928266942749144240020420237153276705785759403019072953506982997681174635673907151856644499332322321579088035719680421458310273802481031746012298208449699089203065699598926690947025679591160106357130634946357609420125223580319677387654711233585375013067828291928349946599077331636017784447090096340360087970540477975170379810969501197027775838769222713506443846417124839450184827707739588007707714623211453528342755023849716924694572679150284882978804641986457119009272574734697043321033091757474387114449914271460113979531460465175717705674905568446670579332667139075523255580471183372714211547822093365025438653384719374474230360983878837077517864405475258349436531094649276628214288499716485354283135575921258757214288792410583835467572916298688718758374714560819702413058421373661892101033513816116981698045524150518509405086125781764762145577981637953775680403132163846782252745029783387112660812179706752454175492501665442704630131729362621965258498471247871904163412798544329515689112368523703890083138721480476796720323855371775568097188216621368341228806795058046403892301673157631331636430392885315997250027372621883549649614866115616619234953579196607399899485002042456482969222428121605212017146571466818179341621066715472184636758016242256725063854155219754299817717414423725704356940589670902509021070871847017199593680033
e = 97
c = 79418540691422578656139651796213224829563266521211325595707569487401417030874358531413674275017334363641194166574500833916574827523075402219754470871728896772312056257743844227927800121160288525434484105786180547178403828613331285574461293211150728313415280329153597549251599876668080073528625299164784405291297754331374420687599875173508778209038236713812747215157059659564867241144529476211694011692007565732793105429228730285249025627762831080251661835294067942958070742202862164086250986988784472568266652325462247009294865764533077164470382743735937483173523682749295196383707694876943634298051820105410771024861599560176707940488888601355473498847493259474613261665538825299531665650233837474894442826242097663456648233384047622152817959729025415665280499618951478005159820575701483220155180955748454167435711033379910310483689839303198822665341421591234243891877857520663120183063591818656508336831518527692847950877186870610083654117153248336928856886934232488927132245720058243202637258025864487122393335118118013444397135476780564523166548571927547341556616683070253790368891423731046742936358877118104790084195711730135202600692806999992373490439385845158780392894927697171401722699273071306493916233696254958735540772870249139252741670476667099529502282392011715616110876451102234600267482991583515122052976378641894214562203326290939184469206074418127906704847146567350085797480500249400491003993809769407575997740985283755035509654310797061339563655229926356893455738361409861102662109994984398860070584568014471082484198504331014073023689622378943694856212172718725529473812336321642429261822836311084518735006587545920946664595488768239633950124822001162595168106106356115962424210028401369438479550293237915944302351566624339603616714683958384871326105542659559877758488581425288668613061792514360263277530824203967659102107889148367539858141289229124274098921748855341045565232484417195620758495861456624842263649414501657786484816662971421962216348340311859717286253287173293151613310383128702607971580042308515018120559903265609733911340589091613087560931098833849573462572181625894166772788435459280323623477689159384354671220634694792005231505741029567734616435905915192606539962414882105254409847885996949466940350184140166614950171110955365828033747003120697209120916652982201967537088553504504252785632280900095976870510754563400828951684036526240669112248351928072177486091157562600003336544767896806392523395037345770580482363058065676920013089896399387769312374871419827762872050800055872960573607645266626972865053489632548224840580503746879607167797904430560935476705014800973841917939689270919224595772574781478285359220463175042728750523639669204218676238297875644055563803457896409252533724486937378974745777400567080239687055154021761534918106133195512030935957251049812753269173090858930245212145938555697547499155977225759702066548720079477737104010668116693232798415289735481194922014811945312893853446826780868861295203942063380964100360870361328125
'''

exp

小明文攻击

加密指数指的是e，e一般取65535，但当e很小时，可直接解密

这里$ m^{e} < c$

from Crypto.Util.number import *
from gmpy2 import *

n = 1392208858696945158251408085300402884210409327605255122395601049457847957306648819174395014931778575812308192875319127224095733396726388842605854427013313599830150182564652493067830031524869535522568868597852507293377043240832819715539722122306829543983051745406887140154364256267942350230636870212935356815475345989038318923389132101208917912083817520799490534351545373438629367819085151041702754019127891155542476560972125790519584018715794669416759039955180436830478697704458250990786586357019211642837879273967620287257818400267757312623543898635740200839249361087580046496969637043238450499583879116276661827372750638403042213043389905183760455450595752578482968202040860053524276678108325784161897719093223308370971388068813420487879756084379519128232693549989942550047529174783976176943482484756074638704076740157397067892580297182979526978967352014250386678155843772313996171396582929433057131989693861316408604436872931427368192437680361830753162284661119995125858203931094922686321756465463988790748131178263745308042820480140189644732824717255521633534750635979508673908361269979175726073254050574688259969290376926807033728165164896588540691889207252105903436659968119091774687841336252628343233161941187968365128093917171537997137001140227677728923114895809278926486615010954871408034272872411042537353956193868948909981683850857262457369506288525323882308421700421661036191853577105238753230479541719001794464585534292774768292358961920606891227776349593589481547577148801600196035588544512224775960892265021565124673788852875005526313525709353599584812394138968970647681759439523307392275602626903789154682706839530654070108096741181206975334567778238856983205004289416400671597321919876279909765650782227834097342294844294386380646928266942749144240020420237153276705785759403019072953506982997681174635673907151856644499332322321579088035719680421458310273802481031746012298208449699089203065699598926690947025679591160106357130634946357609420125223580319677387654711233585375013067828291928349946599077331636017784447090096340360087970540477975170379810969501197027775838769222713506443846417124839450184827707739588007707714623211453528342755023849716924694572679150284882978804641986457119009272574734697043321033091757474387114449914271460113979531460465175717705674905568446670579332667139075523255580471183372714211547822093365025438653384719374474230360983878837077517864405475258349436531094649276628214288499716485354283135575921258757214288792410583835467572916298688718758374714560819702413058421373661892101033513816116981698045524150518509405086125781764762145577981637953775680403132163846782252745029783387112660812179706752454175492501665442704630131729362621965258498471247871904163412798544329515689112368523703890083138721480476796720323855371775568097188216621368341228806795058046403892301673157631331636430392885315997250027372621883549649614866115616619234953579196607399899485002042456482969222428121605212017146571466818179341621066715472184636758016242256725063854155219754299817717414423725704356940589670902509021070871847017199593680033
e = 97
c = 79418540691422578656139651796213224829563266521211325595707569487401417030874358531413674275017334363641194166574500833916574827523075402219754470871728896772312056257743844227927800121160288525434484105786180547178403828613331285574461293211150728313415280329153597549251599876668080073528625299164784405291297754331374420687599875173508778209038236713812747215157059659564867241144529476211694011692007565732793105429228730285249025627762831080251661835294067942958070742202862164086250986988784472568266652325462247009294865764533077164470382743735937483173523682749295196383707694876943634298051820105410771024861599560176707940488888601355473498847493259474613261665538825299531665650233837474894442826242097663456648233384047622152817959729025415665280499618951478005159820575701483220155180955748454167435711033379910310483689839303198822665341421591234243891877857520663120183063591818656508336831518527692847950877186870610083654117153248336928856886934232488927132245720058243202637258025864487122393335118118013444397135476780564523166548571927547341556616683070253790368891423731046742936358877118104790084195711730135202600692806999992373490439385845158780392894927697171401722699273071306493916233696254958735540772870249139252741670476667099529502282392011715616110876451102234600267482991583515122052976378641894214562203326290939184469206074418127906704847146567350085797480500249400491003993809769407575997740985283755035509654310797061339563655229926356893455738361409861102662109994984398860070584568014471082484198504331014073023689622378943694856212172718725529473812336321642429261822836311084518735006587545920946664595488768239633950124822001162595168106106356115962424210028401369438479550293237915944302351566624339603616714683958384871326105542659559877758488581425288668613061792514360263277530824203967659102107889148367539858141289229124274098921748855341045565232484417195620758495861456624842263649414501657786484816662971421962216348340311859717286253287173293151613310383128702607971580042308515018120559903265609733911340589091613087560931098833849573462572181625894166772788435459280323623477689159384354671220634694792005231505741029567734616435905915192606539962414882105254409847885996949466940350184140166614950171110955365828033747003120697209120916652982201967537088553504504252785632280900095976870510754563400828951684036526240669112248351928072177486091157562600003336544767896806392523395037345770580482363058065676920013089896399387769312374871419827762872050800055872960573607645266626972865053489632548224840580503746879607167797904430560935476705014800973841917939689270919224595772574781478285359220463175042728750523639669204218676238297875644055563803457896409252533724486937378974745777400567080239687055154021761534918106133195512030935957251049812753269173090858930245212145938555697547499155977225759702066548720079477737104010668116693232798415289735481194922014811945312893853446826780868861295203942063380964100360870361328125


a, b = gmpy2.iroot(c, 97)

print(long_to_bytes(a))

也能用 [RSA2]P2 的方法，可以得到k是等于0的，也验证了$ m^{e}= c$ ,也就是在取模的过程中没有丢失任何信息，我们可以直接开方从而获得m

[RSA2]2(低加密指数攻击)

main

from Crypto.Util.number import *
from gmpy2 import *

flag = b'NSSCTF{******}'

p = getPrime(512)
q = getPrime(512)

n = p*q
e = 3
phi = (p-1)*(q-1)
m = bytes_to_long(flag)

c = powmod(m, e, n)

print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')

'''
n = 111573371787314339229652810703380127177507745009618224416171957526984270337589283887959174610818933914845556276472159360153787395638087723501889651641965684241070152541291185349571453536221312112508437223801640552330390095266644485311958102687735113533739324296417077804219395793942670324182191309872918900717
e = 3
c = 90782646242308381145716338972639920044710403094882163620436540965475107006005657722222634294458956650085252212452241377251397323707019480880284004845674260662647720809672266571040936376737882878688872281858048646517100139303896804340224961592424635124272549514473232731744884837572128596217771005209683966262
'''

exp

低加密指数攻击

yafu和factordb.com都没分解成功，这里的n也不大，怎么就没成功呢🙄

那只能看看原理了

直接使用上题的方式开方并不行，则说明$ m^{e}> c$ ，不能直接开方。

我们考虑原理： \[ c \equiv m^{e} (mod\quad n) \] 消去取模，有： \[ m^{e} = c + k\cdot n \] 因为本题中加密指数e很小，我们可以考虑$m^{e}$的值并不是特别大，则我们可以通过遍历k的方式将取模后丢失的信息找回来，

遍历到何时停止呢？当$c + k\cdot n$是一个完全e次方数时，则说明我们得到了正确的答案，

from Crypto.Util.number import *
from gmpy2 import *
n = 111573371787314339229652810703380127177507745009618224416171957526984270337589283887959174610818933914845556276472159360153787395638087723501889651641965684241070152541291185349571453536221312112508437223801640552330390095266644485311958102687735113533739324296417077804219395793942670324182191309872918900717
e = 3
c = 90782646242308381145716338972639920044710403094882163620436540965475107006005657722222634294458956650085252212452241377251397323707019480880284004845674260662647720809672266571040936376737882878688872281858048646517100139303896804340224961592424635124272549514473232731744884837572128596217771005209683966262

for k in range(100000):
    cc = c + k*n
    res = iroot(cc, e)
    if res[1]:             #如果第二个参数返回的是true，则m等于第一个参数
        m = res[0]
        break

print(long_to_bytes(m))
print('k:',k)                # k=11

[RSA2]3(Rabin)

main

from Crypto.Util.number import *
from gmpy2 import *

flag = b'NSSCTF{******}'

p = getPrime(256)
q = getPrime(256)

assert p%4 == 3 and q%4 == 3

n = p*q
e = 2
m = bytes_to_long(flag)

c = powmod(m, e, n)

print(f'p = {p}')
print(f'q = {q}')
print(f'e = {e}')
print(f'c = {c}')

'''
p = 67711062621608175960173275013534737889372437946924512522469843485353704013203
q = 91200252033239924238625443698357031288749612243099728355449192607988117291739
e = 2
c = 5251890478898826530186837207902117236305266861227697352434308106457554098811792713226801824100629792962861125855696719512180887415808454466978721678349614
'''

exp

RSA 衍生算法——Rabin算法

公钥指数相关攻击 - CTF Wiki (ctf-wiki.org)

Rabin 算法的特征在于 $e=2$。

和上题一样，本题e非常小，有$e=2$，但我们会发现c不是一个完全平方数，则说明不能用低加密指数攻击的方法解决。

同时我们也发现本题e和phi不互素，他们都是偶数，所以我们也得不到RSA的私钥。实际上，除了RSA算法外，还有很多的非对称加密方案，例如在本题中实际上使用了Rabin算法进行加密，只是它类似于RSA，故在CTF中我们将其划分到RSA攻击范畴中，在后续学习中我们还会遇到很对实际并不是RSA但类似RSA的加密算法。

1.加密

取两个大素数p，q，满足$p≡q≡3\ mod\ 4$，即这两个素数形式为4k+3，计算$n=pq$
$C=m^2\ mod\ n$
n作公钥，p，q作私钥

2.解密

求m，$m^2≡c(mod\ n)$

CTF RSA题解集 (ruanx.net)

# Xenny的轮子
from Crypto.Util.number import *
from gmpy2 import *

p = 67711062621608175960173275013534737889372437946924512522469843485353704013203
q = 91200252033239924238625443698357031288749612243099728355449192607988117291739
e = 2
c = 5251890478898826530186837207902117236305266861227697352434308106457554098811792713226801824100629792962861125855696719512180887415808454466978721678349614

def rabin_attack(c, n, p, q):
    c1 = powmod(c, (p+1)//4, p)
    c2 = powmod(c, (q+1)//4, q)
    cp1 = p - c1
    cp2 = q - c2

    t1 = invert(p, q)
    t2 = invert(q, p)

    m1 = (q*c1*t2 + p*c2*t1) % n
    m2 = (q*c1*t2 + p*cp2*t1) % n
    m3 = (q*cp1*t2 + p*c2*t1) % n
    m4 = (q*cp1*t2 + p*cp2*t1) % n

    return m1, m2, m3, m4

ms = rabin_attack(c, p*q, p, q)

for m in ms:
    print(long_to_bytes(m))    # 四个只有一个是

[RSA2]4(Wiener)

main

from Crypto.Util.number import *
from gmpy2 import *

flag = b'NSSCTF{******}'

p = getPrime(256)
q = getPrime(256)

n = p*q
d = getPrime(128)
e = inverse(d, (p-1)*(q-1))
m = bytes_to_long(flag)

c = powmod(m, e, n)

print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')

'''
n = 6969872410035233098344189258766624225446081814953480897731644163180991292913719910322241873463164232700368119465476508174863062276659958418657253738005689
e = 3331016607237504021038095412236348385663413736904453330557803644384818257225138777641344877202234881627514102078530507171735156112302207979925588113589669
c = 1754994938947260364311041300467524420957926989584983693004487724099773647229373820465164193428679197813476633649362998772470084452129370353136199193923837
'''

exp1

Wiener攻击

已知（e，n，c），求m。d很小且e很大，可知是低解密指数攻击（Wiener攻击）。

这里相当于是反过来了，先生成了d，再由d去求e，当我们发现e 很大或者说很接近 n时，便可以考虑使用连分数展开的方式，遍历每一个系数，测试是否是解题中需要用到的关键因子，

RSA--维纳攻击--代码和题目分析_维纳攻击脚本_Emmaaaaaaaaaa的博客-CSDN博客

# 直接用xenny的轮子
import libnum
from Crypto.Util.number import long_to_bytes
from xenny.ctf.crypto.modern.asymmetric.rsa import wiener
# e很大 wiener攻击
n = 6969872410035233098344189258766624225446081814953480897731644163180991292913719910322241873463164232700368119465476508174863062276659958418657253738005689
e = 3331016607237504021038095412236348385663413736904453330557803644384818257225138777641344877202234881627514102078530507171735156112302207979925588113589669
c = 1754994938947260364311041300467524420957926989584983693004487724099773647229373820465164193428679197813476633649362998772470084452129370353136199193923837
 
d, p, q = wiener.attack(n, e)
m = pow(c, d, n)
flag = libnum.n2s(int(m))
print(flag)
# print(long_to_bytes(m))

exp2

用原理写的，还没理解

from Crypto.Util.number import *
from gmpy2 import *

n = 6969872410035233098344189258766624225446081814953480897731644163180991292913719910322241873463164232700368119465476508174863062276659958418657253738005689
e = 3331016607237504021038095412236348385663413736904453330557803644384818257225138777641344877202234881627514102078530507171735156112302207979925588113589669
c = 1754994938947260364311041300467524420957926989584983693004487724099773647229373820465164193428679197813476633649362998772470084452129370353136199193923837

class ContinuedFraction():
    def __init__(self, numerator, denumerator):
        self.numberlist = []  # number in continued fraction
        self.fractionlist = []  # the near fraction list
        self.GenerateNumberList(numerator, denumerator)
        self.GenerateFractionList()

    def GenerateNumberList(self, numerator, denumerator):
        while numerator != 1:
            quotient = numerator // denumerator
            remainder = numerator % denumerator
            self.numberlist.append(quotient)
            numerator = denumerator
            denumerator = remainder

    def GenerateFractionList(self):
        self.fractionlist.append([self.numberlist[0], 1])
        for i in range(1, len(self.numberlist)):
            numerator = self.numberlist[i]
            denumerator = 1
            for j in range(i):
                temp = numerator
                numerator = denumerator + numerator * self.numberlist[i - j - 1]
                denumerator = temp
            self.fractionlist.append([numerator, denumerator])


a = ContinuedFraction(e, n)
for k, d in a.fractionlist:
    m = powmod(c, d, n)
    flag = long_to_bytes(m)
    
    if b'NSSCTF' in flag:
        print(flag)

[RSA2]5(低加密指数广播攻击)

main

from Crypto.Util.number import *
import os

flag = os.getenv('FLAG')
m = bytes_to_long(flag.encode())
e = 127

def enc():
    p = getPrime(512)
    q = getPrime(512)
    n = p*q
    c = pow(m, e, n)
    print(f"n: {n}")
    print(f"c: {c}")

def main():
    while True:
        opt = int(input('input> '))
        if opt == 1:
            enc()

main()

exp

1、低加密指数

所谓低加密指数，指的是RSA加密过程中使用的参数e的值很小，这样往往会产生安全隐患，导致低加密指数攻击的发生。

2、广播、

所谓广播，就是发送方将一份明文进行多份加密，但是每份使用不同的密钥，即密钥中的模数n不同，但是指数e相同且很小，因此我们只要得到多份密文和对应的模数n就可以利用中国剩余定理进行解密。

3、低加密指数广播攻击

实现低加密指数广播攻击需要满足以下三个条件：

（1）加密指数e非常小。

（2）同一份明文使用不同的模数n，相同的加密指数e进行多次加密。

（3）攻击者可以得到每一份加密后的密文和对应的模数n、加密指数e。

# Xenny师傅wp，还在学，主要这个是交互的
from gmpy2 import *
from pwn import *
from Crypto.Util.number import *


def crt(n_list, c_list):  #中国剩余定理（CRT）
    n = 1
    for i in n_list:
        n *= i
    N = []
    for i in n_list:
        N.append(n // i)  #计算每个模数对应的 N 值，即将总乘积除以当前模数。
    t = []
    for i in range(len(n_list)):
        t.append(invert(N[i], n_list[i]))   #使用invert函数计算每个模数对应的模反元素，并将其添加到列表 t 中。

    summary = 0
    for i in range(len(n_list)):
        #使用CRT的公式计算解密结果，遍历每个模数，将其密文与相应的权重相乘，然后取模，最后累加到 summary 中。
        summary = (summary + c_list[i] * t[i] * N[i]) % n
    return summary


io = remote('node4.anna.nssctf.cn', 28522)
e = 127
n_list = []
c_list = []
for i in range(127):
    io.sendlineafter(b'input> ', b'1')  # 等待收到input> 后发送1
    n = int(io.recvline().decode()[2:])  # 接收一行数据 即 n: xxxx
    c = int(io.recvline().decode()[2:])  # 接收一行数据 即 c: xxxx
    n_list.append(n)
    c_list.append(c)

M = crt(n_list, c_list)
m = iroot(M, e)[0]
flag = long_to_bytes(m)
print(flag)

你是真的难啊，我的哥埃，配置b WSL 2环境给我折腾废了

其实就是你安装好之后直接去 pycharm 里面操作就可以了，有没有的包就安装，安装不成就换源

比如我安的时候第一次就失败了，然后换源解决： pip install -i https://pypi.doubanio.com/simple/ pycryptodome

注意：

在 Linux（如你当前的 Bash 终端）中，路径分隔符是斜杠 / 而不是反斜杠 \。如果你想切换到 D:\code\python\python3.8\Xenny_RSA2\[RSA2]P5 目录，你需要使用正斜杠，并且可能需要对特殊字符进行转义。

尝试使用以下命令：
1
cd /mnt/d/code/python/python3.8/Xenny_RSA2/[RSA2]P5

[RSA2]6(p-1光滑)

main

from Crypto.Util.number import *
from random import choice

flag = b'NSSCTF{******}'

def getMyPrime(nbits):
    while True:
        p = 1
        while p.bit_length() <= nbits:
            p *= choice(sieve_base)
        
        if isPrime(p+1):
            return p+1

p = getMyPrime(256)
q = getMyPrime(256)

n = p*q
e = 65537
m = bytes_to_long(flag)

c = pow(m, e, n)

print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')

'''
n = 53763529836257082401813045869248978487210852880716446938539970599235060144454914000042178896730979463959004404421520555831136502171902051936080825853063287829
e = 65537
c = 50368170865606429432907125510556310647510431461588875539696416879298699197677994843344925466156992948241894107250131926237473102312181031875514294014181272618
'''

exp

光滑数 (Smooth number)：指可以分解为小素数乘积的正整数

当p是N的因数，并且p−1 是光滑数，可以考虑使用Pollard's p-1算法来分解N

这篇文章讲的挺清晰的：

【大数分解】Pollard‘s p-1 method_大数分解程序-CSDN博客

其实就是计算$gcd(a^{B!}-1,n)$是否存在，并且结果不为1也不为n，那么存在的那个值就是p

然后对于$a^{B!}$，我们选取a=2，然后B!我们也从2开始累乘，

这里结合模的性质：$a^{(x+1) !} \equiv\left(a^{x !} \bmod n\right)^{x+1} \quad(\bmod n)$，就能写出代码

from Crypto.Util.number import *
from gmpy2 import *

n = 53763529836257082401813045869248978487210852880716446938539970599235060144454914000042178896730979463959004404421520555831136502171902051936080825853063287829
e = 65537
c = 50368170865606429432907125510556310647510431461588875539696416879298699197677994843344925466156992948241894107250131926237473102312181031875514294014181272618

a = 2
m = 2
while True:
    a = powmod(a, m, n)
    p = gcd(a-1, n)
    if p != 1 and p != n:
        print("p=",p)
        break
    m += 1

q = n // p
print("q=",q)

phi = (p-1)*(q-1)
d = invert(e, phi)
m = powmod(c, d, n)
print(long_to_bytes(m))

[RSA2]7(p+1光滑)

main

from Crypto.Util.number import *
from random import choice

flag = b'NSSCTF{******}'


def getMyPrime(nbits):
    while True:
        p = 1
        while p.bit_length() <= nbits:
            p *= choice(sieve_base)

        if isPrime(p - 1):
            return p - 1


p = getMyPrime(256)
q = getMyPrime(256)

n = p * q
e = 65537
m = bytes_to_long(flag)

c = pow(m, e, n)

print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')

'''
n = 63398538193562720708999492397588489035970399414238113344990243900620729661046648078623873637152448697806039260616826648343172207246183989202073562200879290937
e = 65537
c = 26971181342240802276810747395669930355754928952080329914687241779532014305320191048439959934699795162709365987652696472998140484810728817991804469778237933925
'''

exp

当p是N的因数，并且p+1是光滑数，可以考虑使用Williams's p+1算法来分解N

不行，这玩意的原理有些过于复杂了，咱就先略过，当个脚本小子先，有时间再回来看吧😢

文章列表 | NSSCTF

# from sage.all_cmdline import *
from xenny.ctf.crypto.modern.asymmetric.rsa import williams_pp1
from Crypto.Util.number import long_to_bytes
from gmpy2 import invert, powmod

# p+1光滑
n = 63398538193562720708999492397588489035970399414238113344990243900620729661046648078623873637152448697806039260616826648343172207246183989202073562200879290937
e = 65537
c = 26971181342240802276810747395669930355754928952080329914687241779532014305320191048439959934699795162709365987652696472998140484810728817991804469778237933925

p, q = williams_pp1.attack(n, 55)
phi = (p - 1) * (q - 1)
d = invert(e, phi)
m = powmod(c, d, n)
flag = long_to_bytes(m)
print(flag)

这个代码在WSL 2 Ubuntu运行成功了，但在windows运行错误，不知道为什么

[RSA2]8(共模攻击)

main

from Crypto.Util.number import *

flag = b'NSSCTF{******}'

p = getPrime(512)
q = getPrime(512)

n = p*q
e1 = getPrime(16)
e2 = getPrime(16)

m = bytes_to_long(flag)

c1 = pow(m, e1, n)
c2 = pow(m, e2, n)

print(f'n = {n}')
print(f'e1 = {e1}')
print(f'e2 = {e2}')
print(f'c1 = {c1}')
print(f'c2 = {c2}')

'''
n = 120294155186626082670474649118722298040433501930335450479777638508444129059776534554344361441717048531505985491664356283524886091709370969857047470362547600390987665105196367975719516115980157839088766927450099353377496192206005171597109864609567336679138620134544004766539483664270351472198486955623315909571
e1 = 38317
e2 = 63409
c1 = 42703138696187395030337205860503270214353151588149506110731264952595193757235229215067638858431493587093612397165407221394174690263691095324298012134779703041752810028935711214038835584823385108771901216441784673199846041109074467177891680923593206326788523158180637665813642688824593788192044139055552031622
c2 = 50460092786111470408945316270086812807230253234809303694007902628924057713984397041141665125615735752600114964852157684904429928771531639899496987905067366415806771003121954852465731110629459725994454904159277228514337278105207721011579794604761255522391446534458815389983562890631994726687526070228315925638
'''

exp

已知（n，e1，e2，c1，c2），求m。

当两个用户使用相同的模数 N、不同的私钥时，加密同一明文消息时即存在共模攻击。

本题使用两组公钥对同一消息进行加密，经过观察我们可以发现这两种公钥的n是同一个n，也就是说模数相同，那么此时我们便可以使用共模攻击进行解密。

扩展欧几里得算法（在gmpy2中的gcdext）

from gmpy2 import *
from Crypto.Util.number import *

n = 120294155186626082670474649118722298040433501930335450479777638508444129059776534554344361441717048531505985491664356283524886091709370969857047470362547600390987665105196367975719516115980157839088766927450099353377496192206005171597109864609567336679138620134544004766539483664270351472198486955623315909571
e1 = 38317
e2 = 63409
c1 = 42703138696187395030337205860503270214353151588149506110731264952595193757235229215067638858431493587093612397165407221394174690263691095324298012134779703041752810028935711214038835584823385108771901216441784673199846041109074467177891680923593206326788523158180637665813642688824593788192044139055552031622
c2 = 50460092786111470408945316270086812807230253234809303694007902628924057713984397041141665125615735752600114964852157684904429928771531639899496987905067366415806771003121954852465731110629459725994454904159277228514337278105207721011579794604761255522391446534458815389983562890631994726687526070228315925638

print(gcd(e1,e2))  # 1
_,r,s = gcdext(e1,e2)       # 扩展欧几里得算法求出r,s的值，满足e1*r + e2*s = 1
m = pow(c1,r,n) * pow(c2,s,n) % n   #这个算式最后的结果就是m
print(long_to_bytes(m))

[RSA2]9(dp&dq泄漏攻击)

main

from Crypto.Util.number import *

flag = b'NSSCTF{******}'

p = getPrime(512)
q = getPrime(512)

n = p*q
e = getPrime(128)
d = inverse(e, (p-1)*(q-1))

dp = d % (p-1)
dq = d % (q-1)

m = bytes_to_long(flag)

c = pow(m, e, n)

print(f'p = {p}')
print(f'q = {q}')
print(f'c = {c}')
print(f'dp = {dp}')
print(f'dq = {dq}')

'''
p = 13070310882303377463944295715444821218324151935347454554272870042925400761984585838979931730897626589859098834802923539617244712852188293321626061072925723
q = 10411551818233737389114520103233235272671271111546186997024935593000298916988792710521511848414549553426943998093077337023514210631662189798921671306236009
c = 62492280219693914005334023569480350249964827909276875032578276064973191654731196407886841145547165693859745313398152742796887457192397932684370631253099255490064673499746314452067588181106154875239985334051909867580794242253066085627399488604907196244465911471895118443199543361883148941963668551684228132814
dp = 11568639544706374912496682299967972464196129347160700749666263275305083977187758414725188926013198988871173614336707804756059951725809300386252339177953017
dq = 3455040841431633020487528316853620383411361966784138992524801280785753201070735373348570840039176552952269927122259706586236960440300255065994052962742469
'''

exp

已知（p，q，c，dp，dq，e），求m。

时刻记住：

\[ \begin{align} Enc（pk，m∈Z_N^*）:c = m^e\ mod \ N\\ Dec（sk，c）： m = c^d\ mod\ N \end{align} \] 这里不知道e，那我们看它要怎么求

已知：

解密：

$m \equiv c^d(\bmod n) \equiv c^d(\bmod p * q)=k * p * q+c^d$

分别模p和模q，得到：

公式中的k1就是表示一个整数，不要多想，因为k1*p之后再mod p就没了，只能说整个式子的推导很巧妙~

到这里，m就已经解出来了，这是其中的一种方法，其实非常的简单：

import gmpy2
from Crypto.Util.number import *

p = 13070310882303377463944295715444821218324151935347454554272870042925400761984585838979931730897626589859098834802923539617244712852188293321626061072925723
q = 10411551818233737389114520103233235272671271111546186997024935593000298916988792710521511848414549553426943998093077337023514210631662189798921671306236009
c = 62492280219693914005334023569480350249964827909276875032578276064973191654731196407886841145547165693859745313398152742796887457192397932684370631253099255490064673499746314452067588181106154875239985334051909867580794242253066085627399488604907196244465911471895118443199543361883148941963668551684228132814
dp = 11568639544706374912496682299967972464196129347160700749666263275305083977187758414725188926013198988871173614336707804756059951725809300386252339177953017
dq = 3455040841431633020487528316853620383411361966784138992524801280785753201070735373348570840039176552952269927122259706586236960440300255065994052962742469

mp = gmpy2.powmod(c, dp, p)
mq = gmpy2.powmod(c, dq, q)

print(long_to_bytes(mp))
print(long_to_bytes(mq)) #两个值一样

[RSA2]10(dp泄漏攻击)

main

from Crypto.Util.number import *

flag = b'NSSCTF{******}' + b'1'*100

p = getPrime(512)
q = getPrime(512)

n = p*q
e = 65537
d = inverse(e, (p-1)*(q-1))

dp = d % (p-1)

m = bytes_to_long(flag)

c = pow(m, e, n)

print(f'n = {n}')
print(f'c = {c}')
print(f'dp = {dp}')

'''
n = 79201858340517902370077926747686673001645933420450220163567700296597652438275339093680329918615445030212417351430952656177171126427547284822789947152085534939195866096891005587613262293569611913019639653984932469691636338705418303482885987114085769045348074530172292982433373154900841135911548332400167290083
c = 70109332985937768446301118795636999352761371683181615470371772202170324747707233792154935611826981798791499937601162039878070094663516868746240133223110650205575807753345252087103328657073552992431511929172241702073381723302143955977662087561904058172777520360991685289300855900793806183473523998422682944404
dp = 3098334089252415941833934532457314870210700261428241562420857845879512952043729097866485406309479489101668423603305497982177150304625615059119312238777275
'''

exp

已知（n，c，dp，e），求m。

本题我们又有e了，但是却失去了了一个dq，怎么解决呢？不知道，上网搜一下吧i😭

\[ \begin{align} &∵dp≡d\mod(p-1)，∴e*dp≡e*d\mod(p-1)，∴e*dp=k_1(p-1)+e*d\\ &又∵ed≡1\mod(p-1)(q-1)，∴ed=k_2(p-1)(q-1)+1\\ &第二行代入第一行：\\ &e*dp=k_1(p-1)+k_2(p-1)(q-1)+1\\ &=(p-1)(k_1+k_2(q-1))+1\\ &∵dp<p-1\\ &∴e＞(k_1+k_2(q-1))\\ &即(k_1+k_2(q-1))∈(1,e)\\ &令x=k_1+k_2(q-1)，用x遍历(1,e)即可求出p\\ &然后q=n//q\\ \end{align} \]

from Crypto.Util.number import *
from gmpy2 import *
import libnum

n = 79201858340517902370077926747686673001645933420450220163567700296597652438275339093680329918615445030212417351430952656177171126427547284822789947152085534939195866096891005587613262293569611913019639653984932469691636338705418303482885987114085769045348074530172292982433373154900841135911548332400167290083
c = 70109332985937768446301118795636999352761371683181615470371772202170324747707233792154935611826981798791499937601162039878070094663516868746240133223110650205575807753345252087103328657073552992431511929172241702073381723302143955977662087561904058172777520360991685289300855900793806183473523998422682944404
dp = 3098334089252415941833934532457314870210700261428241562420857845879512952043729097866485406309479489101668423603305497982177150304625615059119312238777275
e = 65537

for x in range(1,e):
    if e * dp % x ==1:
        p = (e*dp - 1) // x + 1
        if n % p == 0:
            q = n // p
            d = invert(e, (p-1) * (q-1))
            m = powmod(c,d,n)
            break

print(long_to_bytes(m))

print(type(m))

print(libnum.n2s(int(m)))

#或者直接用xenny师傅的库
from xenny.ctf.crypto.modern.asymmetric.rsa import dpleak
from Crypto.Util.number import long_to_bytes

e = 65537
n = 79201858340517902370077926747686673001645933420450220163567700296597652438275339093680329918615445030212417351430952656177171126427547284822789947152085534939195866096891005587613262293569611913019639653984932469691636338705418303482885987114085769045348074530172292982433373154900841135911548332400167290083
c = 70109332985937768446301118795636999352761371683181615470371772202170324747707233792154935611826981798791499937601162039878070094663516868746240133223110650205575807753345252087103328657073552992431511929172241702073381723302143955977662087561904058172777520360991685289300855900793806183473523998422682944404
dp = 3098334089252415941833934532457314870210700261428241562420857845879512952043729097866485406309479489101668423603305497982177150304625615059119312238777275

m = dpleak.attack(dp,c,e=e,n=n)
print(long_to_bytes(m))

[RSA2]11(e很大的dp泄露攻击)

main

from Crypto.Util.number import *

flag = b'NSSCTF{******}' + b'1'*80

p = getPrime(512)
q = getPrime(512)

n = p*q
e = getPrime(128)
d = inverse(e, (p-1)*(q-1))

dp = d % (p-1)

m = bytes_to_long(flag)

c = pow(m, e, n)

print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')
print(f'dp = {dp}')

'''
n = 108280026722298796068968170303156759745471686664814404724171434502249429011870583595808692893118419248225924869164875379709992190884930717654004006466664403479467573176438601715156464950045121937338569942817256182277141174728470067308962244296992229214749863655518517510026063088263849891990324547823192559069
e = 305691242207901867366357529364270390903
c = 26537258289122728220745496185201994733321402056894636636642710319261241111675937946139938310952968353253866895253865273981912174303818938005932883052177988834834575591342856235464380238486868448329727891268391728758132913642966389278296932186703733187105516710825918064228397602264185334108934765627411913661
dp = 2656631506624565349527023729530989647164022271235521672257622068579788839123502046687139927161669209201953909023994372208117081512139181611949631467292513
'''

exp

上一题中最后我们发现未知数k是一个小于e的数，所以我们采用了遍历[1,e)的方式来进行爆破，但这种方法不总是可行，例如在本题中e是128为的素数，显然我们不能去爆破它了。

本题可以看作10的升级版，比赛中其实会有很多的升级版本，这里可以分析一下条件

在RSA中，我们不仅有P10中e*dp的关系，还有其他我们可以利用的条件，由欧拉降幂有

$a^{e*dp}≡a^{e*dp \mod (p-1)}≡a\mod p$

则：$a^{e*dp}-a≡0\mod p$，即$ a^{edp} - a = kp$

所以$(a^{e*dp}-a)|p$，显然我们已经攻破了本题，接下来我们需要求解$(a^{e*dp}-a)$和n的最大公因数即可。

#其实是这种类型题的通解
from Crypto.Util.number import *
n = 108280026722298796068968170303156759745471686664814404724171434502249429011870583595808692893118419248225924869164875379709992190884930717654004006466664403479467573176438601715156464950045121937338569942817256182277141174728470067308962244296992229214749863655518517510026063088263849891990324547823192559069
e = 305691242207901867366357529364270390903
c = 26537258289122728220745496185201994733321402056894636636642710319261241111675937946139938310952968353253866895253865273981912174303818938005932883052177988834834575591342856235464380238486868448329727891268391728758132913642966389278296932186703733187105516710825918064228397602264185334108934765627411913661
dp = 2656631506624565349527023729530989647164022271235521672257622068579788839123502046687139927161669209201953909023994372208117081512139181611949631467292513

a = getPrime(64)
pp = pow(a, e*dp, n) - a

p = GCD(n, pp)
q = n // p
d = inverse(e, (p-1)*(q-1))
m = pow(c, d, n)
print(long_to_bytes(m))

或者：

⭐一招鲜吃遍天？

from Crypto.Util.number import long_to_bytes
from xenny.ctf.crypto.modern.asymmetric.rsa import dpleak

n = 108280026722298796068968170303156759745471686664814404724171434502249429011870583595808692893118419248225924869164875379709992190884930717654004006466664403479467573176438601715156464950045121937338569942817256182277141174728470067308962244296992229214749863655518517510026063088263849891990324547823192559069
e = 305691242207901867366357529364270390903
c = 26537258289122728220745496185201994733321402056894636636642710319261241111675937946139938310952968353253866895253865273981912174303818938005932883052177988834834575591342856235464380238486868448329727891268391728758132913642966389278296932186703733187105516710825918064228397602264185334108934765627411913661
dp = 2656631506624565349527023729530989647164022271235521672257622068579788839123502046687139927161669209201953909023994372208117081512139181611949631467292513

m = dpleak.attack(dp,c,e=e,n=n)
flag = long_to_bytes( m )
print(flag)

[RSA2]12(d泄露攻击)

main

from Crypto.Util.number import *
from gmpy2 import *

p = getPrime(512)
q = getPrime(512)

assert p < q

n = p*q
e = 65537
phi = (p-1)*(q-1)
d = invert(e, phi)

print(f'n = {n}')
print(f'd = {d}')
print('flag is NSSCTF{md5(p)}')

'''
n = 113917408220469425995764932761465306974540330325378601642830241920567032775895088098706711486764203845425248022960733155994427766750033219106642310531864450654102562104771892268897793145789045570107312401570269581223945259704851104645493075550316424129401227653740942495625720165869565257394427181127734628103
d = 15762135247924329080208071933121250646888501386858311483546464344350547831176536290630826247188272280853810047335214127264865205744683174860903496832368687060941437002920094364116706593296591581117381565805322046922482804679245558495134876677733584718947309975077159564300049936769192724856722338627154192353
flag is NSSCTF{md5(p)}
'''

exp

简化为（先知道结果，证明过程先略略😎）：

本题我们的目标不再是求解明文，而是考虑当私钥已经泄露的情况，能否利用公私钥来进行因数分解。

首先有一个定理 \[ r \equiv s(\bmod \phi(n)) \Leftrightarrow a^r \equiv a^s(\bmod n)\\ 也就是说我们可以将模n的同余幂式转换成其指数部分模ϕ(n)下的同余式。\\ 其中ϕ(n) = φ(n)/g，g=gcd(p-1,q-1) \] 所以有：$e * d \equiv 1(\bmod \phi(n)) \Rightarrow a^{e * d} \equiv a(\bmod n)$

我们令 $e * d-1=2^s * t$

使得 $t$ 是一个奇数，这样我们遍历 $[1, s]$ ，假设能够找到满足下列关系式的式子 $a^{2^i * t} \equiv 1(\bmod n)$ 且 $a^{2^{i-1} * t} \not \equiv \pm 1(\bmod n)$

就会有 $\operatorname{gcd}\left(a^{2^{i-1} * t}-1, n\right)=p$

from gmpy2 import *
from hashlib import md5

n = 113917408220469425995764932761465306974540330325378601642830241920567032775895088098706711486764203845425248022960733155994427766750033219106642310531864450654102562104771892268897793145789045570107312401570269581223945259704851104645493075550316424129401227653740942495625720165869565257394427181127734628103
d = 15762135247924329080208071933121250646888501386858311483546464344350547831176536290630826247188272280853810047335214127264865205744683174860903496832368687060941437002920094364116706593296591581117381565805322046922482804679245558495134876677733584718947309975077159564300049936769192724856722338627154192353
e = 65537

t = e * d - 1
s = 0

while(t % 2 == 0):
    t = t // 2
    s += 1

# 此时 e * d - 1 = ( 2^s ) * t
p = 2
q = 2

for i in range(1,s):
    c1 = powmod(2,powmod(2,i,n) * t , n )
    c2 = powmod(2,powmod(2,(i-1),n) * t, n )
    if(c2 != 1 and c2 != n-1 and c1 == 1 ):
        p = gcd(c2 - 1,n)
        q = n // p
        break


if p > q:
    p, q = q, p  #交换

flag = md5(str(p).encode()).hexdigest()
print("NSSCTF{"+flag+"}")

参考： Crypto--RSA系列_iroot函数_yolocth的博客-CSDN博客

CTF RSA题解集 (ruanx.net)

NewStarCTF 2023 Week2 官方WriteUp (shimo.im)

CTF RSA题解集 (ruanx.net)

CTF-Crypto

#CTF #Crypto #RSA

Crypto系列——RSA（二）

http://viper2383.github.io/2023/09/14/Crypto系列——RSA（二）/

作者

w1per3

发布于

2023年9月14日

许可协议

C语言学习记录上一篇

Crypto系列——RSA（一）下一篇