0
0

RSA2（p1-p12）

P1

这题给的n有25000000位，而e比较小，导致c也比较小，所以n是远大于c的，故对c直接开e次方根即可求出m：

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

n = 1392208858696945158251408085300402884210409327605255122395601049457847957306648819174395014931778575812308192875319127224095733396726388842605854427013313599830150182564652493067830031524869535522568868597852507293377043240832819715539722122306829543983051745406887140154364256267942350230636870212935356815475345989038318923389132101208917912083817520799490534351545373438629367819085151041702754019127891155542476560972125790519584018715794669416759039955180436830478697704458250990786586357019211642837879273967620287257818400267757312623543898635740200839249361087580046496969637043238450499583879116276661827372750638403042213043389905183760455450595752578482968202040860053524276678108325784161897719093223308370971388068813420487879756084379519128232693549989942550047529174783976176943482484756074638704076740157397067892580297182979526978967352014250386678155843772313996171396582929433057131989693861316408604436872931427368192437680361830753162284661119995125858203931094922686321756465463988790748131178263745308042820480140189644732824717255521633534750635979508673908361269979175726073254050574688259969290376926807033728165164896588540691889207252105903436659968119091774687841336252628343233161941187968365128093917171537997137001140227677728923114895809278926486615010954871408034272872411042537353956193868948909981683850857262457369506288525323882308421700421661036191853577105238753230479541719001794464585534292774768292358961920606891227776349593589481547577148801600196035588544512224775960892265021565124673788852875005526313525709353599584812394138968970647681759439523307392275602626903789154682706839530654070108096741181206975334567778238856983205004289416400671597321919876279909765650782227834097342294844294386380646928266942749144240020420237153276705785759403019072953506982997681174635673907151856644499332322321579088035719680421458310273802481031746012298208449699089203065699598926690947025679591160106357130634946357609420125223580319677387654711233585375013067828291928349946599077331636017784447090096340360087970540477975170379810969501197027775838769222713506443846417124839450184827707739588007707714623211453528342755023849716924694572679150284882978804641986457119009272574734697043321033091757474387114449914271460113979531460465175717705674905568446670579332667139075523255580471183372714211547822093365025438653384719374474230360983878837077517864405475258349436531094649276628214288499716485354283135575921258757214288792410583835467572916298688718758374714560819702413058421373661892101033513816116981698045524150518509405086125781764762145577981637953775680403132163846782252745029783387112660812179706752454175492501665442704630131729362621965258498471247871904163412798544329515689112368523703890083138721480476796720323855371775568097188216621368341228806795058046403892301673157631331636430392885315997250027372621883549649614866115616619234953579196607399899485002042456482969222428121605212017146571466818179341621066715472184636758016242256725063854155219754299817717414423725704356940589670902509021070871847017199593680033
e = 97
c = 79418540691422578656139651796213224829563266521211325595707569487401417030874358531413674275017334363641194166574500833916574827523075402219754470871728896772312056257743844227927800121160288525434484105786180547178403828613331285574461293211150728313415280329153597549251599876668080073528625299164784405291297754331374420687599875173508778209038236713812747215157059659564867241144529476211694011692007565732793105429228730285249025627762831080251661835294067942958070742202862164086250986988784472568266652325462247009294865764533077164470382743735937483173523682749295196383707694876943634298051820105410771024861599560176707940488888601355473498847493259474613261665538825299531665650233837474894442826242097663456648233384047622152817959729025415665280499618951478005159820575701483220155180955748454167435711033379910310483689839303198822665341421591234243891877857520663120183063591818656508336831518527692847950877186870610083654117153248336928856886934232488927132245720058243202637258025864487122393335118118013444397135476780564523166548571927547341556616683070253790368891423731046742936358877118104790084195711730135202600692806999992373490439385845158780392894927697171401722699273071306493916233696254958735540772870249139252741670476667099529502282392011715616110876451102234600267482991583515122052976378641894214562203326290939184469206074418127906704847146567350085797480500249400491003993809769407575997740985283755035509654310797061339563655229926356893455738361409861102662109994984398860070584568014471082484198504331014073023689622378943694856212172718725529473812336321642429261822836311084518735006587545920946664595488768239633950124822001162595168106106356115962424210028401369438479550293237915944302351566624339603616714683958384871326105542659559877758488581425288668613061792514360263277530824203967659102107889148367539858141289229124274098921748855341045565232484417195620758495861456624842263649414501657786484816662971421962216348340311859717286253287173293151613310383128702607971580042308515018120559903265609733911340589091613087560931098833849573462572181625894166772788435459280323623477689159384354671220634694792005231505741029567734616435905915192606539962414882105254409847885996949466940350184140166614950171110955365828033747003120697209120916652982201967537088553504504252785632280900095976870510754563400828951684036526240669112248351928072177486091157562600003336544767896806392523395037345770580482363058065676920013089896399387769312374871419827762872050800055872960573607645266626972865053489632548224840580503746879607167797904430560935476705014800973841917939689270919224595772574781478285359220463175042728750523639669204218676238297875644055563803457896409252533724486937378974745777400567080239687055154021761534918106133195512030935957251049812753269173090858930245212145938555697547499155977225759702066548720079477737104010668116693232798415289735481194922014811945312893853446826780868861295203942063380964100360870361328125

m = iroot(c,e)[0]
print(long_to_bytes(m))

运行得flag：NSSCTF{small}

P2

这题给的e只有3，说明c也比较小，但是对c不能直接开3次根，因为m^{3}可能比n略大，故给c加上k倍的n，得到的这个新的c可能就是m^{3}的精确值，此时对c开3次根就可以求出m：

from Crypto.Util.number import *
from gmpy2 import *
n = 111573371787314339229652810703380127177507745009618224416171957526984270337589283887959174610818933914845556276472159360153787395638087723501889651641965684241070152541291185349571453536221312112508437223801640552330390095266644485311958102687735113533739324296417077804219395793942670324182191309872918900717
e = 3
c = 90782646242308381145716338972639920044710403094882163620436540965475107006005657722222634294458956650085252212452241377251397323707019480880284004845674260662647720809672266571040936376737882878688872281858048646517100139303896804340224961592424635124272549514473232731744884837572128596217771005209683966262
for i in range(10000):
    c += n
    if(iroot(c,e)[1]):
        m = iroot(c,e)[0]
        print(long_to_bytes(m))
        print(i)
        break

运行得flag：NSSCTF{i_think_small_e_is_not_safe_enough!}

P3

这题给e只有2，但是没办法像P2一样开根。但是p，q均已给出，所以可以对c在有限域下开根，此题所给的p，q比较特殊，可以不使用AMM算法（有限域开根）而转用更简单的方法：

                       ![m^{2}\equiv c \mod(n) \Leftrightarrow\begin{cases} & m^{2} \equiv c \mod(p) \\ & m^{2} \equiv c \mod(q) \end{cases}](https://latex.csdn.net/eq?m%5E%7B2%7D%5Cequiv%20c%20%5Cmod%28n%29%20%5CLeftrightarrow%5Cbegin%7Bcases%7D%20%26%20m%5E%7B2%7D%20%5Cequiv%20c%20%5Cmod%28p%29%20%5C%5C%20%26%20m%5E%7B2%7D%20%5Cequiv%20c%20%5Cmod%28q%29%20%5Cend%7Bcases%7D)

由于p和q具有对称性，这里只展示如何求解右上的同余方程：

我们有：

                                               ![p\equiv 3\mod(4)](https://latex.csdn.net/eq?p%5Cequiv%203%5Cmod%284%29)

所以： 

                                             ![\frac{p+1}{2}\equiv0\mod(2)](https://latex.csdn.net/eq?%5Cfrac%7Bp+1%7D%7B2%7D%5Cequiv0%5Cmod%282%29)

由于c是模p的二次剩余，由欧拉判别准则：

                                            ![c^{\frac{p-1}{2}} \equiv 1\mod(p)](https://latex.csdn.net/eq?c%5E%7B%5Cfrac%7Bp-1%7D%7B2%7D%7D%20%5Cequiv%201%5Cmod%28p%29)

所以：

                              ![m^{2}\equiv c \equiv c\cdot c^{\frac{p-1}{2}} \equiv c^{\frac{p+1}{2}}\mod(p)](https://latex.csdn.net/eq?m%5E%7B2%7D%5Cequiv%20c%20%5Cequiv%20c%5Ccdot%20c%5E%7B%5Cfrac%7Bp-1%7D%7B2%7D%7D%20%5Cequiv%20c%5E%7B%5Cfrac%7Bp+1%7D%7B2%7D%7D%5Cmod%28p%29)

由于\frac{p+1}{2}为偶数，所以可以直接求出m在模p意义下的两个值：

                                    ![\begin{cases} & m_{1} \equiv c^{\frac{p+1}{4}}\ \ \mod(p) \\ & m_{2} \equiv -c^{\frac{p+1}{4}}\mod(p) \end{cases}](https://latex.csdn.net/eq?%5Cbegin%7Bcases%7D%20%26%20m_%7B1%7D%20%5Cequiv%20c%5E%7B%5Cfrac%7Bp+1%7D%7B4%7D%7D%5C%20%5C%20%5Cmod%28p%29%20%5C%5C%20%26%20m_%7B2%7D%20%5Cequiv%20-c%5E%7B%5Cfrac%7Bp+1%7D%7B4%7D%7D%5Cmod%28p%29%20%5Cend%7Bcases%7D)

同理求出模q意义下的两个值，将这4个值两两组合，最后用中国剩余定理就可以求出m，这里m会有4种情况，需要自己筛选一下，代码如下：

from Crypto.Util.number import *
from gmpy2 import *
def CRT (b:list[int], m:list[int], sum:int):
    n = 1
    re = 0
    for i in range(sum):
        n *= m[i]
    for k in range(sum):
        re = (re + b[k]*(n//m[k])*inverse(n//m[k],m[k]))%n
    return re

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

m_p1 = pow(c, (p+1)//4, p)
m_p2 = p - m_p1
m_q1 = pow(c, (q+1)//4, q)
m_q2 = q - m_q1
for i in [m_p1, m_p2]:
    for j in [m_q1, m_q2]:
        m = long_to_bytes(CRT([i, j], [p, q], 2))
        if b'NSSCTF' in m:
            print(m)

运行得flag：NSSCTF{rabin!rabin!rabin!not_just_rsa!}

P4

本题为wiener攻击，简要原理如下：

因为：

                    ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ![ed \equiv 1 \mod(\phi(n))](https://latex.csdn.net/eq?ed%20%5Cequiv%201%20%5Cmod%28%5Cphi%28n%29%29)

所以：

    ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ![ed = 1+k\phi(n)](https://latex.csdn.net/eq?ed%20%3D%201+k%5Cphi%28n%29)

等式两边同时除以d\phi(n)可得：

    ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ![\frac{e}{\phi(n)}=\frac{1}{d\phi(n)}+\frac{k}{d}](https://latex.csdn.net/eq?%5Cfrac%7Be%7D%7B%5Cphi%28n%29%7D%3D%5Cfrac%7B1%7D%7Bd%5Cphi%28n%29%7D+%5Cfrac%7Bk%7D%7Bd%7D)

由于d\phi(n)非常大，而\phi(n)又近似于n，则可得:

    ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ![\frac{e}{n} \approx \frac{k}{d}](https://latex.csdn.net/eq?%5Cfrac%7Be%7D%7Bn%7D%20%5Capprox%20%5Cfrac%7Bk%7D%7Bd%7D)

这里约等号两边的值非常接近，所以在误差较小的情况，\frac{e}{n}的连分数展开能精准覆盖\frac{k}{d}。而Wiener的理论告诉我们，当d < \frac{1}{3}N^{\frac{1}{4}}时，这个误差可以让\frac{e}{n}的连分数展开精准覆盖\frac{k}{d}，这样我们便可以求出d。具体的原理如下：

要证明\frac{e}{n}的连分数展开能精准覆盖\frac{k}{d}，根据勒让德的连分数定理，我们只需要证明：

                                    ​​​​​​​        ​​​​​​​       ![\begin{vmatrix} \frac{e}{n} - \frac{k}{d} \end{vmatrix} <\frac{1}{2d^2}](https://latex.csdn.net/eq?%5Cbegin%7Bvmatrix%7D%20%5Cfrac%7Be%7D%7Bn%7D%20-%20%5Cfrac%7Bk%7D%7Bd%7D%20%5Cend%7Bvmatrix%7D%20%3C%5Cfrac%7B1%7D%7B2d%5E2%7D)

证明：

                                    ​​​​![\begin{vmatrix} \frac{e}{n} - \frac{k}{d} \end{vmatrix} = \begin{vmatrix} \frac{ed-kn}{dn} \end{vmatrix} \\](https://latex.csdn.net/eq?%5Cbegin%7Bvmatrix%7D%20%5Cfrac%7Be%7D%7Bn%7D%20-%20%5Cfrac%7Bk%7D%7Bd%7D%20%5Cend%7Bvmatrix%7D%20%3D%20%5Cbegin%7Bvmatrix%7D%20%5Cfrac%7Bed-kn%7D%7Bdn%7D%20%5Cend%7Bvmatrix%7D%20%5C%5C)

    ​​​​​​​        ​​​​​​​        ​​​​​​​               ​​​​​​​        ​​​​​​​        ![=\begin{vmatrix} \frac{1+k\phi(n)-kn}{dn} \end{vmatrix}](https://latex.csdn.net/eq?%3D%5Cbegin%7Bvmatrix%7D%20%5Cfrac%7B1&amp;plus;k%5Cphi%28n%29-kn%7D%7Bdn%7D%20%5Cend%7Bvmatrix%7D)

     ​​​​​​​        ​​​​​​​        ​​​​​​​              ​​​​​​​        ​​​​​​​        ![= \frac{k(n-\phi(n))-1}{dn}](https://latex.csdn.net/eq?%3D%20%5Cfrac%7Bk%28n-%5Cphi%28n%29%29-1%7D%7Bdn%7D)

    ​​​​​​​        ​​​​​​​        ​​​​​​​               ​​​​​​​        ​​​​​​​        ![= \frac{k(p+q-1)-1}{dn}\ \ \ \ \ \ \ (1)](https://latex.csdn.net/eq?%3D%20%5Cfrac%7Bk%28p&amp;plus;q-1%29-1%7D%7Bdn%7D%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%281%29)

因为p+q-1是2 \sqrt{n}数量级的，但这里我们可以直接做以下放缩：

    ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​          ![p+q-1 < 3 \sqrt{n}\ \ \ \ \ \ \ \ \ \ (2)](https://latex.csdn.net/eq?p&amp;plus;q-1%20%3C%203%20%5Csqrt%7Bn%7D%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%282%29)

将（2）带入（1）中得：

    ​​​​​​​        ​​​​​​​                          ![\begin{vmatrix} \frac{e}{n} - \frac{k}{d} \end{vmatrix} < \frac{3k}{d\sqrt{n}} \ \ \ \ \ \ \ \ \ \ \ \ \ \ (3)](https://latex.csdn.net/eq?%5Cbegin%7Bvmatrix%7D%20%5Cfrac%7Be%7D%7Bn%7D%20-%20%5Cfrac%7Bk%7D%7Bd%7D%20%5Cend%7Bvmatrix%7D%20%3C%20%5Cfrac%7B3k%7D%7Bd%5Csqrt%7Bn%7D%7D%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%283%29)

因为：

                          ![ed = 1+k\phi(n)\ \ and\ \ e<\phi(n)\ \ and\ \ d<\frac{1}{3}n^{\frac{1}{4}}](https://latex.csdn.net/eq?ed%20%3D%201&amp;plus;k%5Cphi%28n%29%5C%20%5C%20and%5C%20%5C%20e%3C%5Cphi%28n%29%5C%20%5C%20and%5C%20%5C%20d%3C%5Cfrac%7B1%7D%7B3%7Dn%5E%7B%5Cfrac%7B1%7D%7B4%7D%7D)

所以有下列不等式：

    ​​​​​​​        ​​​​​​​        ​​​​​​​                ![k<d<\frac{1}{3}n^{\frac{1}{4}}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (4)](https://latex.csdn.net/eq?k%3Cd%3C%5Cfrac%7B1%7D%7B3%7Dn%5E%7B%5Cfrac%7B1%7D%7B4%7D%7D%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%284%29)

由（4）可得下列不等式：

    ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ![kd<\frac{1}{9}\sqrt{n}](https://latex.csdn.net/eq?kd%3C%5Cfrac%7B1%7D%7B9%7D%5Csqrt%7Bn%7D)

即：

    ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ![k < \frac{\sqrt{n}}{9d}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (5)](https://latex.csdn.net/eq?k%20%3C%20%5Cfrac%7B%5Csqrt%7Bn%7D%7D%7B9d%7D%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%285%29)

将（5）带入（3）中可得：

    ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ![\begin{vmatrix} \frac{e}{n} - \frac{k}{d} \end{vmatrix} < \frac{3k}{d\sqrt{n}} < \frac{1}{3d^2}<\frac{1}{2d^2}](https://latex.csdn.net/eq?%5Cbegin%7Bvmatrix%7D%20%5Cfrac%7Be%7D%7Bn%7D%20-%20%5Cfrac%7Bk%7D%7Bd%7D%20%5Cend%7Bvmatrix%7D%20%3C%20%5Cfrac%7B3k%7D%7Bd%5Csqrt%7Bn%7D%7D%20%3C%20%5Cfrac%7B1%7D%7B3d%5E2%7D%3C%5Cfrac%7B1%7D%7B2d%5E2%7D)

故原命题得证。

wiener攻击代码如下：

from Crypto.Util.number import *
from gmpy2 import *
def Fraction_to_ConFrac(numerator, denominator):
    lst = []
    if numerator > denominator:
        lst.append(0)
        numerator, denominator = denominator, numerator
    while numerator > 0:
        lst.append(denominator//numerator)
        denominator, numerator = numerator, denominator%numerator
    return lst
def ConFrac_to_Fraction(lst:list[int]):
    numerator, denominator = 0, 1
    for i in lst[::-1]:
        numerator, denominator = denominator, i*denominator+numerator
    return numerator, denominator

n = 6969872410035233098344189258766624225446081814953480897731644163180991292913719910322241873463164232700368119465476508174863062276659958418657253738005689
e = 3331016607237504021038095412236348385663413736904453330557803644384818257225138777641344877202234881627514102078530507171735156112302207979925588113589669
c = 1754994938947260364311041300467524420957926989584983693004487724099773647229373820465164193428679197813476633649362998772470084452129370353136199193923837

a = Fraction_to_ConFrac(e,n)
for i in range(len(a)):
    k ,d = ConFrac_to_Fraction(a[:i+1])
    m = long_to_bytes(pow(c,d,n))
    if b'NSSCTF' in m:
        print(m)
        break

运行得flag：NSSCTF{e_is_so_huge}

P5

none

P6

这题生成素数p满足p-1光滑，即p-1可以表示为一群小素数的乘积，令B为这群小素数中最大的素数，我们有：

    ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ![p-1\mid B!](https://latex.csdn.net/eq?p-1%5Cmid%20B%21)

由费马小定理得：

    ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ![a^{B!} \equiv a^{k(p-1)}\equiv 1 \mod(p)](https://latex.csdn.net/eq?a%5E%7BB%21%7D%20%5Cequiv%20a%5E%7Bk%28p-1%29%7D%5Cequiv%201%20%5Cmod%28p%29)

所以：

                    ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ![p\mid a^{B!}-1](https://latex.csdn.net/eq?p%5Cmid%20a%5E%7BB%21%7D-1)

也就是说a^{B!}-1含有素因子p，那么用GCD（a^{B!}-1，n）就可以求出p。

因为：

    ​​​​​​​        ​​​​​​​        ​​​​​​​                ![(a^{B!}-1,n) = ((a^{B!})\%n-1,n)](https://latex.csdn.net/eq?%28a%5E%7BB%21%7D-1%2Cn%29%20%3D%20%28%28a%5E%7BB%21%7D%29%5C%25n-1%2Cn%29)

所以我们可以采取以下方法来加速计算a^{B!}\%n：

    ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ![a^{B!}\equiv (a^{(B-1)!})^{B} \mod (n)](https://latex.csdn.net/eq?a%5E%7BB%21%7D%5Cequiv%20%28a%5E%7B%28B-1%29%21%7D%29%5E%7BB%7D%20%5Cmod%20%28n%29)

代码如下：

​
from Crypto.Util.number import *
n = 53763529836257082401813045869248978487210852880716446938539970599235060144454914000042178896730979463959004404421520555831136502171902051936080825853063287829
e = 65537
c = 50368170865606429432907125510556310647510431461588875539696416879298699197677994843344925466156992948241894107250131926237473102312181031875514294014181272618
a = 2
i = 1
while True:
    a = pow(a,i,n)
    p = GCD(a-1,n)
    if 1 < p < n:
        break
    i += 1
q = n//p
d = inverse(e,(p-1)*(q-1))
m = pow(c,d,n)
print(long_to_bytes(m))

​

运行得flag：NSSCTF{p-1_smooth_with_factor}

P7

本题是p+1光滑，网上找的原理还有部分没搞明白，所以直接用了别人的板子：

from Crypto.Util.number import *
from gmpy2 import *
def mlucas(v, a, n):
    """ Helper function for williams_pp1().  Multiplies along a Lucas sequence modulo n. """
    v1, v2 = v, (v**2 - 2) % n
    for bit in bin(a)[3:]: v1, v2 = ((v1**2 - 2) % n, (v1*v2 - v) % n) if bit == "0" else ((v1*v2 - v) % n, (v2**2 - 2) % n)
    return v1
def ilog(x, b):  # greatest integer l such that b**l <= x.
    l = 0
    while x >= b:
        x /= b
        l += 1
    return l
def attack(n):
    v = 1
    while True:
        for p in sieve_base:
            e = ilog(iroot(n,2)[0], p)
            if e == 0: break
            for _ in range(e): v = mlucas(v, p, n)
            g = GCD(v-2, n)
            if 1 < g < n: 
              return g ,n//g
            if g == n: break
        v += 1
n = 63398538193562720708999492397588489035970399414238113344990243900620729661046648078623873637152448697806039260616826648343172207246183989202073562200879290937
e = 65537
c = 26971181342240802276810747395669930355754928952080329914687241779532014305320191048439959934699795162709365987652696472998140484810728817991804469778237933925
p, q = attack(n)
d = inverse(e,(p-1)*(q-1))
m = pow(c,d,n)
print(long_to_bytes(m))

运行得flag：NSSCTF{p+1_smooth_number}

P8

这题用两个不同的e1、e2，相同的模数n，加密了相同的信息，这种情况可以用贝祖定理把加密指数降低到（e1,e2），原理如下：

由贝祖定理可知：对任意的整数e_{1}，e_{2}，存在整数x，y，使得：

    ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​     ![xe_{1}+ye_{2}=(e_{1},e_{2})](https://latex.csdn.net/eq?xe_%7B1%7D&amp;plus;ye_%7B2%7D%3D%28e_%7B1%7D%2Ce_%7B2%7D%29)

这里e1与e2互素，所以（e1，e2）=1，所以x就是e1模e2的逆元，求出x后带入上式可求出y，然后进行如下操作就可以求出m：

    ​​​​​​​        ​​​​​​​        ![(c_{1})^{x}\cdot (c_{2})^{y}\equiv m^{e_{1}x} \cdot m^{e_{2}y}\equiv m^{xe_{1}+ye_{2}}\equiv m\mod(n)](https://latex.csdn.net/eq?%28c_%7B1%7D%29%5E%7Bx%7D%5Ccdot%20%28c_%7B2%7D%29%5E%7By%7D%5Cequiv%20m%5E%7Be_%7B1%7Dx%7D%20%5Ccdot%20m%5E%7Be_%7B2%7Dy%7D%5Cequiv%20m%5E%7Bxe_%7B1%7D&amp;plus;ye_%7B2%7D%7D%5Cequiv%20m%5Cmod%28n%29)

代码如下：

from Crypto.Util.number import *
from gmpy2 import *
n = 120294155186626082670474649118722298040433501930335450479777638508444129059776534554344361441717048531505985491664356283524886091709370969857047470362547600390987665105196367975719516115980157839088766927450099353377496192206005171597109864609567336679138620134544004766539483664270351472198486955623315909571
e1 = 38317
e2 = 63409
c1 = 42703138696187395030337205860503270214353151588149506110731264952595193757235229215067638858431493587093612397165407221394174690263691095324298012134779703041752810028935711214038835584823385108771901216441784673199846041109074467177891680923593206326788523158180637665813642688824593788192044139055552031622
c2 = 50460092786111470408945316270086812807230253234809303694007902628924057713984397041141665125615735752600114964852157684904429928771531639899496987905067366415806771003121954852465731110629459725994454904159277228514337278105207721011579794604761255522391446534458815389983562890631994726687526070228315925638
x = inverse(e1,e2)
y = (1-x*e1)//e2
m = (pow(c1,x,n)*pow(c2,y,n))%n
print(long_to_bytes(m))

运行得flag：NSSCTF{same_module_attack!}

P9

原理如下：

    ​​​​​​​        ​​​​​​​        ​​​​​​​        ![m^e\equiv c\mod(n)\begin{cases} &amp; m^e\equiv c\mod(p)\\ &amp; m^e\equiv c\mod(q) \end{cases}](https://latex.csdn.net/eq?m%5Ee%5Cequiv%20c%5Cmod%28n%29%5Cbegin%7Bcases%7D%20%26%20m%5Ee%5Cequiv%20c%5Cmod%28p%29%5C%5C%20%26%20m%5Ee%5Cequiv%20c%5Cmod%28q%29%20%5Cend%7Bcases%7D)

我们来解右上的方程，右下同理：

因为：

    ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ![ed\equiv 1\mod(\phi(n))](https://latex.csdn.net/eq?ed%5Cequiv%201%5Cmod%28%5Cphi%28n%29%29)

所以:

    ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ![ed\equiv 1\mod(p-1)](https://latex.csdn.net/eq?ed%5Cequiv%201%5Cmod%28p-1%29)

所以：

    ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ![c^d\equiv m^{ed}\equiv m^{1+k(p-1)} \equiv m \mod(p)](https://latex.csdn.net/eq?c%5Ed%5Cequiv%20m%5E%7Bed%7D%5Cequiv%20m%5E%7B1&amp;plus;k%28p-1%29%7D%20%5Cequiv%20m%20%5Cmod%28p%29)

这样我们就求出了模p意义下的m，然后同理求出模q意义下的m，最后用CRT就可以求出模n意义下的m：

from Crypto.Util.number import *
p = 13070310882303377463944295715444821218324151935347454554272870042925400761984585838979931730897626589859098834802923539617244712852188293321626061072925723
q = 10411551818233737389114520103233235272671271111546186997024935593000298916988792710521511848414549553426943998093077337023514210631662189798921671306236009
c = 62492280219693914005334023569480350249964827909276875032578276064973191654731196407886841145547165693859745313398152742796887457192397932684370631253099255490064673499746314452067588181106154875239985334051909867580794242253066085627399488604907196244465911471895118443199543361883148941963668551684228132814
dp= 11568639544706374912496682299967972464196129347160700749666263275305083977187758414725188926013198988871173614336707804756059951725809300386252339177953017
dq= 3455040841431633020487528316853620383411361966784138992524801280785753201070735373348570840039176552952269927122259706586236960440300255065994052962742469
m1 = pow(c,dp,p)
m2 = pow(c,dq,q)
m = (m1*q*inverse(q,p) + m2*p*inverse(p,q))%(p*q) #CRT
print(long_to_bytes(m))

运行得flag：NSSCTF{dp&dq_leak}

P10

原理如下：

因为：

                              ![1 \equiv ed \equiv e(d\%(p-1)) \equiv ed_{p} \mod(p-1)](https://latex.csdn.net/eq?1%20%5Cequiv%20ed%20%5Cequiv%20e%28d%5C%25%28p-1%29%29%20%5Cequiv%20ed_%7Bp%7D%20%5Cmod%28p-1%29)

所以：

                            ​​​​​​​        ​​​​​​​        ​​​​​​​        ![p-1 \mid ed_{p}-1](https://latex.csdn.net/eq?p-1%20%5Cmid%20ed_%7Bp%7D-1)

所以：

    ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ![a^{ed_{p}-1} \equiv a^{k(p-1)} \equiv 1 \mod(p)](https://latex.csdn.net/eq?a%5E%7Bed_%7Bp%7D-1%7D%20%5Cequiv%20a%5E%7Bk%28p-1%29%7D%20%5Cequiv%201%20%5Cmod%28p%29)

这里a只要满足与p互素即可，然后用GCD(a^{ed_{p}-1}-1,n)就可以求出p，代码如下：

from Crypto.Util.number import *
from gmpy2 import *
n = 79201858340517902370077926747686673001645933420450220163567700296597652438275339093680329918615445030212417351430952656177171126427547284822789947152085534939195866096891005587613262293569611913019639653984932469691636338705418303482885987114085769045348074530172292982433373154900841135911548332400167290083
c = 70109332985937768446301118795636999352761371683181615470371772202170324747707233792154935611826981798791499937601162039878070094663516868746240133223110650205575807753345252087103328657073552992431511929172241702073381723302143955977662087561904058172777520360991685289300855900793806183473523998422682944404
dp = 3098334089252415941833934532457314870210700261428241562420857845879512952043729097866485406309479489101668423603305497982177150304625615059119312238777275
e = 65537
a = 2
p = GCD(n,pow(2,e*dp-1,n)-1)
q = n//p
d = inverse(e,(p-1)*(q-1))
print(long_to_bytes(pow(c,d,n)))

运行得flag：NSSCTF{just_dp_leak}

P11

原理同P10，代码如下：

from Crypto.Util.number import *
from gmpy2 import *
n = 108280026722298796068968170303156759745471686664814404724171434502249429011870583595808692893118419248225924869164875379709992190884930717654004006466664403479467573176438601715156464950045121937338569942817256182277141174728470067308962244296992229214749863655518517510026063088263849891990324547823192559069
e = 305691242207901867366357529364270390903
c = 26537258289122728220745496185201994733321402056894636636642710319261241111675937946139938310952968353253866895253865273981912174303818938005932883052177988834834575591342856235464380238486868448329727891268391728758132913642966389278296932186703733187105516710825918064228397602264185334108934765627411913661
dp = 2656631506624565349527023729530989647164022271235521672257622068579788839123502046687139927161669209201953909023994372208117081512139181611949631467292513
a = 2
p = GCD(n,pow(2,e*dp-1,n)-1)
q = n//p
d = inverse(e,(p-1)*(q-1))
print(long_to_bytes(pow(c,d,n)))

运行得flag：NSSCTF{p_leak_but_with_huge_e}

P12

本题的d泄露，但题目不是让我们用d解密，而是用泄露的d来分解n，如何分解呢？如下：

已知：

    ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ![ed \equiv 1 \mod (\phi(n))](https://latex.csdn.net/eq?ed%20%5Cequiv%201%20%5Cmod%20%28%5Cphi%28n%29%29)

则：

                                      ![ed-1=k(p-1)(q-1)](https://latex.csdn.net/eq?ed-1%3Dk%28p-1%29%28q-1%29)

由欧拉定理：

                                            ![a^{ed-1} \equiv 1 \mod(n)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)](https://latex.csdn.net/eq?a%5E%7Bed-1%7D%20%5Cequiv%201%20%5Cmod%28n%29%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%281%29)

这里因为ed-1为偶数，所以我们可以把它的素因子2全部提出来，最后剩一个奇数s，然后把ed-1写成如下形式：

            ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​       ​​​​​​​ ![ed-1 = 2^{t}s\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)](https://latex.csdn.net/eq?ed-1%20%3D%202%5E%7Bt%7Ds%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%282%29)

然后将(2)式代入(1)式得：

    ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​![n \mid (a^{2^{t}s}-1)](https://latex.csdn.net/eq?n%20%5Cmid%20%28a%5E%7B2%5E%7Bt%7Ds%7D-1%29)

这时如果我们求n与(a^{2^{t}s}-1)的最大公因数，那么得到的肯定是n，这是因为组成n的两个素因子p，q同时出现在了(a^{2^{t}s}-1)中，为了使p和q分开，我们可以对(a^{2^{t}s}-1)使用平方差公式作如下分解，直到p和q出现在两个不同的因式中，那么此时我们可以将分解得来的因式与n求最大公因数就可以求出n的一个素因子：

    ![n \mid (a^{2^{t-1}s}+1)(a^{2^{t-2}s}+1)(a^{2^{t-3}s}+1)\cdot \cdot \cdot (a^{2^{1}s}+1)(a^{2^{0}s}+1)(a^{2^{0}s}-1)](https://latex.csdn.net/eq?n%20%5Cmid%20%28a%5E%7B2%5E%7Bt-1%7Ds%7D&amp;plus;1%29%28a%5E%7B2%5E%7Bt-2%7Ds%7D&amp;plus;1%29%28a%5E%7B2%5E%7Bt-3%7Ds%7D&amp;plus;1%29%5Ccdot%20%5Ccdot%20%5Ccdot%20%28a%5E%7B2%5E%7B1%7Ds%7D&amp;plus;1%29%28a%5E%7B2%5E%7B0%7Ds%7D&amp;plus;1%29%28a%5E%7B2%5E%7B0%7Ds%7D-1%29)

代码如下：

from Crypto.Util.number import *
from gmpy2 import *
import hashlib as hs
e = 65537
n = 113917408220469425995764932761465306974540330325378601642830241920567032775895088098706711486764203845425248022960733155994427766750033219106642310531864450654102562104771892268897793145789045570107312401570269581223945259704851104645493075550316424129401227653740942495625720165869565257394427181127734628103
d = 15762135247924329080208071933121250646888501386858311483546464344350547831176536290630826247188272280853810047335214127264865205744683174860903496832368687060941437002920094364116706593296591581117381565805322046922482804679245558495134876677733584718947309975077159564300049936769192724856722338627154192353
tmp = e*d -1
t = 0
s = 0

while not tmp%2:
    tmp //= 2
    t += 1
s = tmp

flag = 0
for a in range(2,100000):
    p = GCD(pow(a,s,n)-1,n)
    if p != 1 and p != n :
        break
    for i in range(0,t):
        p = GCD(pow(a,(2**i)*s,n)+1,n)
        if p != 1 and p != n :
            flag = 1
            break
    if flag:
        break
q = n//p
if p > q:
    p, q = q, p
print('NSSCTF{%s}' % hs.md5(str(p).encode()).hexdigest())

运行得flag：NSSCTF{f56299b1e5339dfebe8ea3d32dd44043}

标签： python 开发语言 密码学
本文转载自: https://blog.csdn.net/AxuAxuA123/article/details/140254970
版权归原作者 AxuAxuA123 所有， 如有侵权，请联系我们删除。
登录后发布评论

“RSA2（p1-p12）”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

网络安全法-网络运行安全

使用selenium/drissionpage时如何阻止chrome自动跳转http到https

docker desktop 里部署的Open WebUI 管理员密码忘记了的处理方法

在ubuntu20.04中搭建onsite比赛运行环境

利用开源的低代码表单设计器FcDesigner高效管理和渲染复杂表单结构

Kafka学习笔记

【前端】浏览器输入url到页面呈现发生了什么？

文章导航