mobile wallpaper 1mobile wallpaper 2mobile wallpaper 3mobile wallpaper 4
Profile Image of the Author
Wangtanzhi
公告公告
我草莓招了
标签
2475 字
6 分钟
密码刷题笔记
2026-04-12
CTF
CTF
/
学习
/
Crypto

RSA#

题目：q = next_prime(p)#

题面

from Crypto.Util.number import *
import gmpy2
flag = b'NSSCTF{******}'
p = getPrime(512)
q = gmpy2.next_prime(p)
n = p*q
e = 65537
phi = (p-1)*(q-1)
m = bytes_to_long(flag)
c = pow(m, e, n)
print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')
'''
n = 115637000420176820831322601039129424406844427046456738651883381559357542765613732363445112111006849040385859313572091386802534464534403117787314180179562651607533039692795522388596550968316951090748054495960090527479954143448774136390568881020918710834542819900918984139672802889774720153267841255456602500057
e = 65537
c = 98161406745910866780822530171878255235776133393411573803496865047700715941955255328757920065032397556905095591171977170479344602512244671081108703687450560269408412671849929423399172588599903975793985819498354819305128607934552101433664794909855378636055525016664559476808490723554481335856183927702549281730
'''

解题思路

题目先生成一个 512 位素数 p，再通过 next_prime 取 p 的下一个素数作为 q，最后执行 RSA 加密。虽然 p、q 都很大，无法直接分解，但二者是相邻素数，因此距离非常近。

令 sn=⌊n⌋s_n = \lfloor\sqrt{n}\rfloor。因为 n=pqn=pq，所以 n\sqrt{n} 是 p 和 q 的几何平均值，有：

p<n<qp < \sqrt{n} < q

由于 p 与 q 是相邻素数，next_prime(s_n) 得到的仍然是 q，之后便可通过 p=n/qp=n/q 求出 p。

EXP

from Crypto.Util.number import *
from gmpy2 import *
p = getPrime(512)
q = gmpy2.next_prime(p)


n = 115637000420176820831322601039129424406844427046456738651883381559357542765613732363445112111006849040385859313572091386802534464534403117787314180179562651607533039692795522388596550968316951090748054495960090527479954143448774136390568881020918710834542819900918984139672802889774720153267841255456602500057
e = 65537
c = 98161406745910866780822530171878255235776133393411573803496865047700715941955255328757920065032397556905095591171977170479344602512244671081108703687450560269408412671849929423399172588599903975793985819498354819305128607934552101433664794909855378636055525016664559476808490723554481335856183927702549281730


sn = isqrt(n)
q = next_prime(sn)
p = n // q


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


m = pow(c, d, n)
print(long_to_bytes(m))

题目：q = next_prime(p - r)#

题面

from Crypto.Util.number import *
import gmpy2
flag = b'NSSCTF{******}'


p = getPrime(512)
q = gmpy2.next_prime(p - getPrime(256))
n = p*q
e = 65537
phi = (p-1)*(q-1)
m = bytes_to_long(flag)
c = pow(m, e, n)


print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')
'''
n = 148841588941490812589697505975986386226158446072049530534135525236572105309550985274214825612079495930267744452266230141871521931612761645600600201983605957650711248808703757693378777706453580124982526368706977258199152469200838211055230241296139605912607613807871432800586045262879581100319519318390454452117
e = 65537
c = 69038543593219231496623016705860610154255535760819426453485115089535439537440188692852514795648297200067103841434646958466720891016026061658602312900242658759575613625726750416539176437174502082858413122020981274672260498423684555063381678387696096811975800995242962853092582362805345713900308205654744774932
'''

解题思路

题目先生成一个 512 位素数 p，再取 p−rp-r 的下一个素数作为 q，其中 r 是随机的 256 位素数。相对于 p 和 q，r 仍然较小，因此 p 与 q 比较接近。

不过，此时 q 已经不是 ⌊n⌋\lfloor\sqrt{n}\rfloor 的相邻素数，无法直接沿用上一题的方法。若在 r 的范围内逐个遍历，搜索空间又过大，因此需要使用更通用的费马分解法。

费马分解基于以下等式：

(p+q)24−n=(p+q)24−pq=(p−q)24\frac{(p+q)^2}{4}-n =\frac{(p+q)^2}{4}-pq =\frac{(p-q)^2}{4}

当 p 与 q 很接近时，(p−q)24\frac{(p-q)^2}{4} 很小，因此 p+q2\frac{p+q}{2} 与 n\sqrt{n} 也很接近。可以从大于 n\sqrt{n} 的整数开始遍历 x：

  1. 计算 x2−nx^2-n。
  2. 判断 x2−nx^2-n 是否为完全平方数 y2y^2。
  3. 若是，则由 x=p+q2x=\frac{p+q}{2}、y=p−q2y=\frac{p-q}{2} 得到 p=x−yp=x-y、q=x+yq=x+y。

本质上，两个数越接近，它们的算术平均值与几何平均值也越接近。因此，当 p、q 相近时，可以利用费马分解法分解 n。

EXP

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


def factor(n):
    a = isqrt(n)
    b2 = a*a - n
    b = isqrt(n)
    while b*b!=b2:
        a = a+1
        b2 = a*a-n
        b = isqrt(b2)
    q = a+b
    p = a-b
    return q,p


n = 148841588941490812589697505975986386226158446072049530534135525236572105309550985274214825612079495930267744452266230141871521931612761645600600201983605957650711248808703757693378777706453580124982526368706977258199152469200838211055230241296139605912607613807871432800586045262879581100319519318390454452117
e = 65537
c = 69038543593219231496623016705860610154255535760819426453485115089535439537440188692852514795648297200067103841434646958466720891016026061658602312900242658759575613625726750416539176437174502082858413122020981274672260498423684555063381678387696096811975800995242962853092582362805345713900308205654744774932


q,p=factor(n)
phi=(q-1)*(p-1)
d = inverse(e,phi)
m = pow(c,d,n)
print(long_to_bytes(m))

题目：n1n_1 与 n2n_2 有相同因子#

题面

from Crypto.Util.number import *
flag = b'NSSCTF{******}'
p1 = getPrime(512)
q = getPrime(512)
p2 = getPrime(512)
n1 = p1*q
n2 = p2*q
e = 65537
m = bytes_to_long(flag)
c1 = pow(m, e, n1)
c2 = pow(m, e, n2)
print(f'n1 = {n1}')
print(f'n2 = {n2}')
print(f'e = {e}')
print(f'c1 = {c1}')
print(f'c2 = {c2}')
'''
n1 = 143348646254804947818644803938588739009782265465565896704788366218178523508874903492905378927641178487821742289009401873633609987818871281146199303052141439575438691652893995423962176259643151111739185844059243400387734688275416379337335777994990138009973618431459431410429980866760075387393812720247541406893
n2 = 138110854441015362783564250048191029327770295545362614687087481715680856350219966472039006526758450117969049316234863489558254565946242898336924686721846675826468588471046162610143748100096038583426519355288325214365299329095841907207926280081868726568947436076663762493891291276498567791697978693639037765169
e = 65537
c1 = 54957154834913405861345262613986460384513988240935244315981524013378872930144117440787175357956479768211180412158274730449811947349624843965933828130932856052315165316154486515277625404352272475136003785605985702495858150662789554694910771308456687676791434476722168247882078861234982509648037033827107552029
c2 = 122221335585005390437769701090707585780333874638519916373585594040154234166935881089609641995190534396533473702495240511296379249872039728112248708182969185010334637138777948970821974238214641235158623707766980447918480715835847907220219601467702961667091318910582445444058108454023108157805147341928089334736
'''

解题思路

本题生成了三个素数 p1、p2、q，并构造：

n1=p1q,n2=p2qn_1=p_1q,\qquad n_2=p_2q

可以将它们看作使用相同 e 的两组 RSA 公钥。由于 n1n_1 和 n2n_2 含有相同因子 q，直接计算二者的最大公因数即可恢复它：

q=gcd⁡(n1,n2)q=\gcd(n_1,n_2)

得到公共素因子后，再分别计算另一个素因子，即可按照常规 RSA 流程解密。

使用 c1 解密时，应搭配 n1 及其对应的两个素因子；不要混用 n2 或 c2。

EXP

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


n1 = 143348646254804947818644803938588739009782265465565896704788366218178523508874903492905378927641178487821742289009401873633609987818871281146199303052141439575438691652893995423962176259643151111739185844059243400387734688275416379337335777994990138009973618431459431410429980866760075387393812720247541406893
n2 = 138110854441015362783564250048191029327770295545362614687087481715680856350219966472039006526758450117969049316234863489558254565946242898336924686721846675826468588471046162610143748100096038583426519355288325214365299329095841907207926280081868726568947436076663762493891291276498567791697978693639037765169
e = 65537
c1 = 54957154834913405861345262613986460384513988240935244315981524013378872930144117440787175357956479768211180412158274730449811947349624843965933828130932856052315165316154486515277625404352272475136003785605985702495858150662789554694910771308456687676791434476722168247882078861234982509648037033827107552029
c2 = 122221335585005390437769701090707585780333874638519916373585594040154234166935881089609641995190534396533473702495240511296379249872039728112248708182969185010334637138777948970821974238214641235158623707766980447918480715835847907220219601467702961667091318910582445444058108454023108157805147341928089334736


p = gcd(n1,n2)
q1 = n1//p
phi = (p-1)*(q1-1)
d = inverse(e,phi)
m = pow(c1,d,n1)
print(long_to_bytes(m))

题目：n=pqrn=pqr#

题面

from Crypto.Util.number import *
flag = b'NSSCTF{******}' + b'1'*170
p = getPrime(512)
q = getPrime(512)
r = getPrime(512)
n = p*q*r
e = 65537
phi = (p-1)*(q-1)*(r-1)
m = bytes_to_long(flag)
c = pow(m, e, n)
print(f'p = {p}')
print(f'q = {q}')
print(f'r = {r}')
print(f'e = {e}')
print(f'c = {c}')
'''
p = 10666139331774428325755287635566473140804481321882464031499529816800186578792308674238646794969384836340484775213796013129603472328582005363876462361316357
q = 8419311673449738061914489023962717718536471719688567807316495262754711350004888752049108347226115000749280146228195893953964759818878155006622123533942989
r = 12875078327453384158245832541544758526474680184252540739652077682353277702054275525591573258723948221345537075374635382175740236093131628077747126356403959
e = 65537
c = 424552463648937499189041230155623101311087334789253159440707211761796081289342164253743235182597460622581134089949035117444838205449163269030784233435435681797627188717450074808905561404960693227573181548281296514743775615606388692910356320667720308219275107443303501165027740512539959960217657836317351146520079753390346207659007421416917274795119021374032194294225350901136669304225010974617136606299060486198480556729770211945777266366417547752798441211059402
'''

解题思路

常见 RSA 模数通常为 n=pqn=pq，而本题构造了 n=pqrn=pqr。当 p、q、r 是互不相同的素数时，欧拉函数为：

φ(n)=(p−1)(q−1)(r−1)\varphi(n)=(p-1)(q-1)(r-1)

更一般地，若 n=q1q2q3⋯n=q_1q_2q_3\cdots，且所有素因子互不相同，则：

φ(n)=(q1−1)(q2−1)(q3−1)⋯\varphi(n)=(q_1-1)(q_2-1)(q_3-1)\cdots

得到 φ(n)\varphi(n) 后，按照常规 RSA 流程求私钥并解密即可。

EXP

from Crypto.Util.number import *
p = 10666139331774428325755287635566473140804481321882464031499529816800186578792308674238646794969384836340484775213796013129603472328582005363876462361316357
q = 8419311673449738061914489023962717718536471719688567807316495262754711350004888752049108347226115000749280146228195893953964759818878155006622123533942989
r = 12875078327453384158245832541544758526474680184252540739652077682353277702054275525591573258723948221345537075374635382175740236093131628077747126356403959
e = 65537
c = 424552463648937499189041230155623101311087334789253159440707211761796081289342164253743235182597460622581134089949035117444838205449163269030784233435435681797627188717450074808905561404960693227573181548281296514743775615606388692910356320667720308219275107443303501165027740512539959960217657836317351146520079753390346207659007421416917274795119021374032194294225350901136669304225010974617136606299060486198480556729770211945777266366417547752798441211059402
n=p*q*r
phi = (p-1)*(q-1)*(r-1)
d = inverse(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))

题目：n=p3qn=p^3q#

题面

from Crypto.Util.number import *
flag = b'NSSCTF{******}' + b'1'*100
p = getPrime(256)
q = getPrime(256)
n = (p**3) * q
e = 65537
phi = (p-1)*(q-1)
m = bytes_to_long(flag)
c = pow(m, e, n)
print(f'p = {p}')
print(f'q = {q}')
print(f'e = {e}')
print(f'c = {c}')
'''
p = 80505091208742938705306670241621545375764148093711243653439069254008824979403
q = 67599990875658931406915486208971556223245451500927259766683936131876689508521
e = 65537
c = 7958690969908064264211283192959937430539613460471121984649054121171267262097603091410178042319139582772142226087020110084551158367679146616732446561228522673699836019156243452069036383047309578614662564794584927846163157472211089368697387945469398750955336949678910159585015004994620777231073804301249774041
'''

解题思路

本题与上一题类似，同样改变了 n 的构造方式。不过，φ(n)\varphi(n) 既不是 (p−1)3(q−1)(p-1)^3(q-1)，也不是 (p3−1)(q−1)(p^3-1)(q-1)。

由素数幂的欧拉函数公式 φ(pk)=pk−1(p−1)\varphi(p^k)=p^{k-1}(p-1) 可得：

φ(p3q)=p2(p−1)(q−1)\varphi(p^3q)=p^2(p-1)(q-1)

这里需要使用欧拉函数对素数幂的计算公式。

EXP

from Crypto.Util.number import *


p = 80505091208742938705306670241621545375764148093711243653439069254008824979403
q = 67599990875658931406915486208971556223245451500927259766683936131876689508521
e = 65537
c = 7958690969908064264211283192959937430539613460471121984649054121171267262097603091410178042319139582772142226087020110084551158367679146616732446561228522673699836019156243452069036383047309578614662564794584927846163157472211089368697387945469398750955336949678910159585015004994620777231073804301249774041
n = (p**3)*q
phi = (p**2)*(p-1)*(q-1)
d = inverse(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))

题目：逆元不存在，且 flag 较短#

题面

from Crypto.Util.number import *
flag = b'NSSCTF{******}'
p = getPrime(512)
q = getPrime(512)
e = 65537
while True:
    r = 2*getPrime(100)*e+1
    if isPrime(r):
        break
n = p*q*r
m = bytes_to_long(flag)
c = pow(m, e, n)
print(f'p = {p}')
print(f'q = {q}')
print(f'r = {r}')
print(f'e = {e}')
print(f'c = {c}')
'''
p = 7478755670255767435237487693415479182290330775502792675052667363676831056436638619069277770540533350723045234676443621124912287506103439704868369839725279
q = 9232828888049557325429111621080998490274442347556398052322580869768941301413255711626092627273543579067597113958627672298942570149816938335701615759283713
r = 102909133680612532601801231903654039
e = 65537
c = 142893174944324070830219394465469685943669308818639857030565389839224452373848570577201378981080333784852764502832587008270072323948511579823852437852643609820245476634896477031076952735298279618952398460203032125853063235638358942643559551563899381032067185778629120272032518475352761100115057449043142848203976076694124978394099839339406197
'''

解题思路

这仍然是一道多因子 RSA 题目。如果直接按常规方法求解，会发现解出的明文是乱码。先计算欧拉函数：

φ(n)=(p−1)(q−1)(r−1)\varphi(n)=(p-1)(q-1)(r-1)

由题目中 r 的构造方式可知，e 整除 r−1r-1，因此 e 与 φ(n)\varphi(n) 不互素，逆元 d 不存在。

不过，flag 较短，转成整数后的明文 m 也足够小。可以只保留模数中的 pq，把原密文转换成公钥 (pq, e) 下的密文：

c1≡c mod pq=(me mod n) mod pq=me mod pqed1≡1(modφ(pq))c1d1≡m(modpq)\begin{aligned} c_1 &\equiv c \bmod pq = \left(m^e \bmod n\right) \bmod pq = m^e \bmod pq \\ ed_1 &\equiv 1 \pmod{\varphi(pq)} \\ c_1^{d_1} &\equiv m \pmod{pq} \end{aligned}

这里使用了模运算的性质：当 a∣ka\mid k 时，

(x mod k) mod a=x mod a\left(x\bmod k\right)\bmod a=x\bmod a

因此，c1=c mod pqc_1=c\bmod pq 就是消息使用公钥 (pq, e) 加密后的结果。接下来按正常的 RSA 流程解密即可。

EXP

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


p = 7478755670255767435237487693415479182290330775502792675052667363676831056436638619069277770540533350723045234676443621124912287506103439704868369839725279
q = 9232828888049557325429111621080998490274442347556398052322580869768941301413255711626092627273543579067597113958627672298942570149816938335701615759283713
r = 102909133680612532601801231903654039
e = 65537
c = 142893174944324070830219394465469685943669308818639857030565389839224452373848570577201378981080333784852764502832587008270072323948511579823852437852643609820245476634896477031076952735298279618952398460203032125853063235638358942643559551563899381032067185778629120272032518475352761100115057449043142848203976076694124978394099839339406197
phi = (p-1)*(q-1)
d = inverse(e, phi)
m = pow(c, d, p*q)
print(long_to_bytes(m))

简单来说，当 m 较小时，即使原公钥对应的私钥不存在，也可以尝试重组原模数的因子，构造新的公钥并完成解密。

题目：e=131074e=131074#

题面

from Crypto.Util.number import *


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


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


e = 65537*2


n = p*q


m = bytes_to_long(flag)


c = pow(m, e, n)


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


'''
p = 9927950299160071928293508814174740578824022211226572614475267385787727188317224760986347883270504573953862618573051241506246884352854313099453586586022059
q = 9606476151905841036013578452822151891782938033700390347379468858357928877640534612459734825681004415976431665670102068256547092636766287603818164456689343
e = 131074
c = 68145285629092005589126591120307889109483909395989426479108244531402455690717006058397784318664114589567149811644664654952286387794458474073250495807456996723468838094551501146672038892183058042546944692051403972876692350946611736455784779361761930869993818138259781995078436790236277196516800834433299672560
'''

解题思路

这是另一种 e 与 φ(n)\varphi(n) 不互素的情况。由于 p−1p-1、q−1q-1 和 e 都是偶数，无法按上一题的方式重组模数来获得互素的指数。

注意到 e=2×65537e=2\times65537，因此：

c≡me≡(m2)65537(modn)c\equiv m^e\equiv\left(m^2\right)^{65537}\pmod n

题目：小明文攻击#

题面

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
'''

解题思路

题目中的 n 很大，暴力分解几乎不可行。但如果明文 m 足够小，满足：

me<nm^e<n

那么模运算不会丢失信息，此时 c=mec=m^e，可以直接对 c 开 e 次方得到 m。

EXP

from Crypto.Util.number import *
from gmpy2 import *
n  = 1392208858696945158251408085300402884210409327605255122395601049457847957306648819174395014931778575812308192875319127224095733396726388842605854427013313599830150182564652493067830031524869535522568868597852507293377043240832819715539722122306829543983051745406887140154364256267942350230636870212935356815475345989038318923389132101208917912083817520799490534351545373438629367819085151041702754019127891155542476560972125790519584018715794669416759039955180436830478697704458250990786586357019211642837879273967620287257818400267757312623543898635740200839249361087580046496969637043238450499583879116276661827372750638403042213043389905183760455450595752578482968202040860053524276678108325784161897719093223308370971388068813420487879756084379519128232693549989942550047529174783976176943482484756074638704076740157397067892580297182979526978967352014250386678155843772313996171396582929433057131989693861316408604436872931427368192437680361830753162284661119995125858203931094922686321756465463988790748131178263745308042820480140189644732824717255521633534750635979508673908361269979175726073254050574688259969290376926807033728165164896588540691889207252105903436659968119091774687841336252628343233161941187968365128093917171537997137001140227677728923114895809278926486615010954871408034272872411042537353956193868948909981683850857262457369506288525323882308421700421661036191853577105238753230479541719001794464585534292774768292358961920606891227776349593589481547577148801600196035588544512224775960892265021565124673788852875005526313525709353599584812394138968970647681759439523307392275602626903789154682706839530654070108096741181206975334567778238856983205004289416400671597321919876279909765650782227834097342294844294386380646928266942749144240020420237153276705785759403019072953506982997681174635673907151856644499332322321579088035719680421458310273802481031746012298208449699089203065699598926690947025679591160106357130634946357609420125223580319677387654711233585375013067828291928349946599077331636017784447090096340360087970540477975170379810969501197027775838769222713506443846417124839450184827707739588007707714623211453528342755023849716924694572679150284882978804641986457119009272574734697043321033091757474387114449914271460113979531460465175717705674905568446670579332667139075523255580471183372714211547822093365025438653384719374474230360983878837077517864405475258349436531094649276628214288499716485354283135575921258757214288792410583835467572916298688718758374714560819702413058421373661892101033513816116981698045524150518509405086125781764762145577981637953775680403132163846782252745029783387112660812179706752454175492501665442704630131729362621965258498471247871904163412798544329515689112368523703890083138721480476796720323855371775568097188216621368341228806795058046403892301673157631331636430392885315997250027372621883549649614866115616619234953579196607399899485002042456482969222428121605212017146571466818179341621066715472184636758016242256725063854155219754299817717414423725704356940589670902509021070871847017199593680033
e = 97
c = 79418540691422578656139651796213224829563266521211325595707569487401417030874358531413674275017334363641194166574500833916574827523075402219754470871728896772312056257743844227927800121160288525434484105786180547178403828613331285574461293211150728313415280329153597549251599876668080073528625299164784405291297754331374420687599875173508778209038236713812747215157059659564867241144529476211694011692007565732793105429228730285249025627762831080251661835294067942958070742202862164086250986988784472568266652325462247009294865764533077164470382743735937483173523682749295196383707694876943634298051820105410771024861599560176707940488888601355473498847493259474613261665538825299531665650233837474894442826242097663456648233384047622152817959729025415665280499618951478005159820575701483220155180955748454167435711033379910310483689839303198822665341421591234243891877857520663120183063591818656508336831518527692847950877186870610083654117153248336928856886934232488927132245720058243202637258025864487122393335118118013444397135476780564523166548571927547341556616683070253790368891423731046742936358877118104790084195711730135202600692806999992373490439385845158780392894927697171401722699273071306493916233696254958735540772870249139252741670476667099529502282392011715616110876451102234600267482991583515122052976378641894214562203326290939184469206074418127906704847146567350085797480500249400491003993809769407575997740985283755035509654310797061339563655229926356893455738361409861102662109994984398860070584568014471082484198504331014073023689622378943694856212172718725529473812336321642429261822836311084518735006587545920946664595488768239633950124822001162595168106106356115962424210028401369438479550293237915944302351566624339603616714683958384871326105542659559877758488581425288668613061792514360263277530824203967659102107889148367539858141289229124274098921748855341045565232484417195620758495861456624842263649414501657786484816662971421962216348340311859717286253287173293151613310383128702607971580042308515018120559903265609733911340589091613087560931098833849573462572181625894166772788435459280323623477689159384354671220634694792005231505741029567734616435905915192606539962414882105254409847885996949466940350184140166614950171110955365828033747003120697209120916652982201967537088553504504252785632280900095976870510754563400828951684036526240669112248351928072177486091157562600003336544767896806392523395037345770580482363058065676920013089896399387769312374871419827762872050800055872960573607645266626972865053489632548224840580503746879607167797904430560935476705014800973841917939689270919224595772574781478285359220463175042728750523639669204218676238297875644055563803457896409252533724486937378974745777400567080239687055154021761534918106133195512030935957251049812753269173090858930245212145938555697547499155977225759702066548720079477737104010668116693232798415289735481194922014811945312893853446826780868861295203942063380964100360870361328125


m = iroot(c, e)


print(long_to_bytes(m[0]))

题目：低加密指数#

题面

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
'''

解题思路

与上一题一样，直接暴力分解 n 不现实。但本题无法直接对 c 开方，说明 me>nm^e>n，模运算已经丢失了部分信息。

由同余关系可知：

me=c+knm^e=c+kn

由于 e 很小，可以遍历 k，逐步找回取模时丢失的信息。当 c+knc+kn 是一个完全 e 次方数时，就得到了正确的明文。

EXP

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]:
        m = res[0]
        break


print(long_to_bytes(m))
print('k:',k)

题目：Rabin 算法#

题面

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
'''

解题思路

本题的加密指数很小，有 e=2e=2。但 c 不是完全平方数，因此无法直接使用低加密指数攻击。同时，e 与 φ(n)\varphi(n) 都是偶数，二者不互素，无法求出常规 RSA 私钥。

Rabin 算法的加密流程如下：

  1. 取两个满足 p≡q≡3(mod4)p\equiv q\equiv3\pmod4 的大素数 p、q，并计算 n=pqn=pq。
  2. 计算密文 c≡m2(modn)c\equiv m^2\pmod n。

它的加密过程等同于 e=2e=2 时的 RSA，但解密过程更复杂，需要用到二次剩余和欧拉准则以及中国剩余定理。

由于模平方根存在正、负两个解，组合后共有四个候选明文，需要根据 flag 的格式判断哪一个正确。

设 n=pqn=pq，t1=p−1(modq)t_1=p^{-1}\pmod q，t2=q−1(modp)t_2=q^{-1}\pmod p。对于方程组：

{x≡a(modp)x≡b(modq)\begin{cases} x\equiv a\pmod p \\ x\equiv b\pmod q \end{cases}

由中国剩余定理可得模 pqpq 下的唯一解：

x=(qat2+pbt1) mod pqx=\left(qat_2+pbt_1\right)\bmod pq

这也解释了 EXP 中 m1、m2、m3、m4 的组合方式。

EXP

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*t1 + p*c2*t2) % n
    m2 = (q*c1*t1 + p*cp2*t2) % n
    m3 = (q*cp1*t1 + p*c2*t2) % n
    m4 = (q*cp1*t1 + p*cp2*t2) % n


    return m1, m2, m3, m4


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


for m in ms:
    print(long_to_bytes(m))

题目：Wiener 攻击#

题面

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
'''

解题思路

本题的密钥生成流程与常规 RSA 不同：通常先选定 e，再求逆元得到 d；本题则先选定较小的 d，再计算 e。这会带来 Wiener 攻击的风险。

由 RSA 密钥关系可知：

ed≡1(modφ(n))ed\equiv1\pmod{\varphi(n)}

因此存在整数 k，使得：

ed−1=kφ(n)ed-1=k\varphi(n)

两边同时除以 dφ(n)d\varphi(n)：

eφ(n)−1dφ(n)=kd\frac{e}{\varphi(n)}-\frac{1}{d\varphi(n)}=\frac{k}{d}

因为 φ(n)=(p−1)(q−1)=n−p−q+1≈n\varphi(n)=(p-1)(q-1)=n-p-q+1\approx n，且 1dφ(n)\frac{1}{d\varphi(n)} 极小，所以有：

en≈kd\frac{e}{n}\approx\frac{k}{d}

Wiener 证明了当满足下式时，可以通过对 e/ne/n 做连分数展开来恢复 k/dk/d：

d<13n14d<\frac{1}{3}n^{\frac14}

得到 k 和 d 后，可以计算：

φ(N)=ed−1k\varphi(N)=\frac{ed-1}{k}

进而得到 p+q=N−φ(N)+1p+q=N-\varphi(N)+1。令 S=p+qS=p+q、N=pqN=pq，则：

(x−p)(x−q)=x2−Sx+N(x-p)(x-q)=x^2-Sx+N

所以 p、q 是方程 x2−Sx+N=0x^2-Sx+N=0 的两个根。恢复 p、q 后，即可按常规 RSA 流程解密。

EXP

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


n = 6969872410035233098344189258766624225446081814953480897731644163180991292913719910322241873463164232700368119465476508174863062276659958418657253738005689
e = 3331016607237504021038095412236348385663413736904453330557803644384818257225138777641344877202234881627514102078530507171735156112302207979925588113589669
c = 1754994938947260364311041300467524420957926989584983693004487724099773647229373820465164193428679197813476633649362998772470084452129370353136199193923837


class ContinuedFraction():
    def __init__(self, numerator, denumerator):
        self.numberlist = []
        self.fractionlist = []
        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)

题目：低加密指数广播攻击#

题面

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

解题思路

本题是一道交互题。每次交互时，程序都会生成一组新的 RSA 公钥来加密同一个明文，并且所有公钥的加密指数 e 都相同。因此，对第 i 组数据有：

ci≡me(modni)c_i\equiv m^e\pmod{n_i}

由于可以反复交互，我们能够获得足够多组 (n_i, c_i)。把固定不变的 mem^e 看作一个整体，问题就转化成了：已知同一个整数模不同模数的余数，如何恢复这个整数？

当各个模数两两互素，且它们的乘积大于 mem^e 时，可以使用中国剩余定理恢复 mem^e，再开 e 次方得到明文 m。

EXP

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


def crt(n_list, c_list):
    n = 1
    for i in n_list:
        n *= i
    N = []
    for i in n_list:
        N.append(n//i)
    t = []
    for i in range(len(n_list)):
        t.append(invert(N[i], n_list[i]))


    summary = 0
    for i in range(len(n_list)):
        summary = (summary + c_list[i]*t[i]*N[i]) % n
    return summary


io = remote('node4.anna.nssctf.cn', 28798)
e = 127
n_list = []
c_list = []
for i in range(127):
    io.sendlineafter(b'input> ', b'1')
    n = int(io.recvline().decode()[2:])
    c = int(io.recvline().decode()[2:])
    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)

题目：p−1p-1 光滑#

题面

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
'''

解题思路

设 p 为素数，且整数 a 不被 p 整除。由费马小定理可得：

ap−1≡1(modp)a^{p-1}\equiv1\pmod p

等价地：

p∣(ap−1−1)p\mid\left(a^{p-1}-1\right)

如果 M 是 p−1p-1 的倍数，即 (p−1)∣M(p-1)\mid M，令 M=t(p−1)M=t(p-1)，则：

aM=at(p−1)=(ap−1)t≡1(modp)a^M =a^{t(p-1)} =\left(a^{p-1}\right)^t \equiv1\pmod p

因此：

p∣(aM−1)p\mid\left(a^M-1\right)

这意味着 gcd⁡(aM−1,n)\gcd(a^M-1,n) 很可能得到 n 的非平凡因子 p。在 Pollard p−1p-1 算法中，可以逐步令 M=k!M=k!，使 M 包含尽可能多的小素因子。

EXP

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:
        break
    m += 1


q = n // p


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

在具体计算中，不需要每次显式计算 k!k!。可以利用模运算的性质迭代计算 a←ak mod na\leftarrow a^k\bmod n，这等价于逐步构造 ak! mod na^{k!}\bmod n。

题目：p+1p+1 光滑攻击#

题面

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
'''

解题思路

p+1p+1 光滑攻击需要借助 Lucas 序列。其基本思路与 Pollard p−1p-1 算法相似：利用 p+1p+1 可被许多小素数整除的特性构造序列，再通过最大公因数提取 n 的非平凡因子。

EXP

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


n = 63398538193562720708999492397588489035970399414238113344990243900620729661046648078623873637152448697806039260616826648343172207246183989202073562200879290937
e = 65537
c = 26971181342240802276810747395669930355754928952080329914687241779532014305320191048439959934699795162709365987652696472998140484810728817991804469778237933925


def mlucas(v, a, 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 primegen():
    yield 2
    yield 3
    yield 5
    yield 7
    yield 11
    yield 13
    ps = primegen()  # yay recursion
    p = ps.__next__() and ps.__next__()
    q, sieve, n = p ** 2, {}, 13
    while True:
        if n not in sieve:
            if n < q:
                yield n
            else:
                next, step = q + 2 * p, 2 * p
                while next in sieve:
                    next += step
                sieve[next] = step
                p = ps.__next__()
                q = p ** 2
        else:
            step = sieve.pop(n)
            next = n + step
            while next in sieve:
                next += step
            sieve[next] = step
        n += 2


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):
    for v in count(1):
        for p in primegen():
            e = ilog(isqrt(n), p)
            if e == 0:
                break
            for _ in range(e):
                v = mlucas(v, p, n)
            g = gcd(v - 2, n)
            if 1 < g < n:
                return int(g), int(n // g)  # g|n
            if g == n:
                break


p, q = attack(n)




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

题目：共模攻击#

题面

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
'''

解题思路

本题使用相同的模数 n、不同的加密指数 e1e_1 和 e2e_2 对同一明文进行加密，并且满足 gcd⁡(e1,e2)=1\gcd(e_1,e_2)=1。

由贝祖定理，存在整数 s1s_1、s2s_2，使得：

s1e1+s2e2=1s_1e_1+s_2e_2=1

于是：

c1s1c2s2≡(me1)s1(me2)s2≡me1s1+e2s2≡m(modn)\begin{aligned} c_1^{s_1} c_2^{s_2} &\equiv \left(m^{e_1}\right)^{s_1} \left(m^{e_2}\right)^{s_2} \\ &\equiv m^{e_1 s_1 + e_2 s_2} \\ &\equiv m \pmod{n} \end{aligned}

因此，不需要分解 n 就能直接恢复明文 m。具体可以使用扩展欧几里得算法求出一组 (s1,s2)(s_1,s_2)；在 gmpy2 中可以调用 gcdext。

EXP

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


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


_, s1, s2 = gcdext(e1, e2)


m = powmod(c1, s1, n)*powmod(c2, s2, n) % n
print(long_to_bytes(m))

题目：dpd_p 与 dqd_q 泄漏攻击#

题面

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
'''

解题思路

先分别在模 p 和模 q 的意义下计算明文：

m1≡m≡cd(modp)m2≡m≡cd(modq)\begin{aligned} m_1 &\equiv m \equiv c^d \pmod{p} \\ m_2 &\equiv m \equiv c^d \pmod{q} \end{aligned}

根据欧拉降幂：

m1≡cd mod (p−1)≡cdp(modp)m2≡cd mod (q−1)≡cdq(modq)\begin{aligned} m_1 &\equiv c^{d\bmod(p-1)} \equiv c^{d_p} \pmod{p} \\ m_2 &\equiv c^{d\bmod(q-1)} \equiv c^{d_q} \pmod{q} \end{aligned}

令 m=m1+kpm=m_1+kp，代入第二个同余式：

m2≡m1+kp(modq)m_2\equiv m_1+kp\pmod q

因此：

k≡(m2−m1)p−1(modq)k\equiv(m_2-m_1)p^{-1}\pmod q

最终可以通过中国剩余定理合并得到：

m=m1+((m2−m1)p−1 mod q)pm=m_1+\left((m_2-m_1)p^{-1}\bmod q\right)p

EXP

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


p = getPrime(1024)
q = getPrime(1024)
e = 65537
m = getPrime(512)
phi = (p-1)*(q-1)
n = p*q
d = invert(e, phi)
c = powmod(m, e, n)
invp = invert(p, q)
dp = d % (p-1)
dq = d % (q-1)
def work():
    for _ in range(10):
        m1 = powmod(c, dp, p)
        m2 = powmod(c, dq, q)
        m = (((m2 - m1)*invp) % q)*p + m1


print(timed(work)[2])

题目：dpd_p 泄漏攻击#

题面

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
'''

解题思路

本题已知 e 和 dpd_p，但没有给出 dqd_q。由 dp≡d(modp−1)d_p\equiv d\pmod{p-1} 可得：

dpe≡de≡1+k(p−1)(q−1)≡1(modp−1)\begin{aligned} d_p e &\equiv d e \\ &\equiv 1 + k(p-1)(q-1) \\ &\equiv 1 \pmod{p-1} \end{aligned}

因此存在整数 k，满足：

dpe=1+k(p−1)d_pe=1+k(p-1)

又因为 dp<p−1d_p<p-1，所以 k<ek<e。可以在区间 [1,e)[1,e) 内遍历 k，当 edp−1e d_p-1 能被 k 整除，且求出的候选 p 能整除 n 时，即可恢复正确的素因子。

EXP

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


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


for k in range(1, e):
    if (e * dp - 1) % k == 0:
        p = (e * dp - 1) // k + 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))

题目：e 很大的 dpd_p 泄漏#

题面

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
'''

解题思路

由欧拉降幂有

aedp≡aedp mod (p−1)≡a(modp)a^{ed_p}\equiv a^{ed_p\bmod(p-1)}\equiv a\pmod p

因此：

aedp−a≡0(modp)a^{ed_p}-a\equiv0\pmod p

也就是 p∣(aedp−a)p\mid\left(a^{ed_p}-a\right)。选择一个合适的整数 a 后，只需求它与 n 的最大公因数即可恢复 p：

p=gcd⁡(aedp−a,n)p=\gcd\left(a^{ed_p}-a,n\right)

EXP

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


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


m = 10007
p = gcd(powmod(m, e*dp, n) - m, n)
q = n // p
d = invert(e, (p - 1) * (q - 1))
m = powmod(c, d, n)
print(long_to_bytes(m))

题目： d 泄漏攻击#

解题思路

本题的目标不再是恢复明文，而是在私钥已经泄漏的情况下，利用公私钥对模数 n 进行因数分解。首先列出公私钥之间的关系：

ed−1=kφ(n)ed-1=k\varphi(n)

同时有：

aed−1≡1(modn)a^{ed-1}\equiv1\pmod n

不妨设 ed−1=2sted-1=2^st，其中 t 为奇数。遍历 i∈[1,s]i\in[1,s]，尝试找到满足下列关系的 i：

a2i−1t≢±1(modn)a2it≡1(modn)\begin{aligned} a^{2^{i-1}t} &\not\equiv \pm1 \pmod{n} \\ a^{2^{i}t} &\equiv 1 \pmod{n} \end{aligned}

此时，gcd⁡(a2i−1t−1,n)\gcd\left(a^{2^{i-1}t}-1,n\right) 就可能是 n 的一个非平凡因子。

为了理解这一点，引入 Carmichael 函数：

λ(n)=lcm⁡(p−1,q−1)=φ(n)gcd⁡(p−1,q−1)\lambda(n)=\operatorname{lcm}(p-1,q-1) =\frac{\varphi(n)}{\gcd(p-1,q-1)}

若 r≡s(modλ(n))r\equiv s\pmod{\lambda(n)}，且 a 与 n 互素，则 ar≡as(modn)a^r\equiv a^s\pmod n。因此，可以将模 n 的幂同余关系转化为指数在模 λ(n)\lambda(n) 下的同余关系。

由：

a2it≡1(modn)a^{2^it}\equiv1\pmod n

可知对应指数已经进入模 n 的循环。若前一步 a2i−1ta^{2^{i-1}t} 既不是 1 也不是 -1，它就是 1 的一个非平凡平方根，从而可以通过：

gcd⁡(a2i−1t−1,n)\gcd\left(a^{2^{i-1}t}-1,n\right)

分离出 p 或 q。

EXP

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


n = 113917408220469425995764932761465306974540330325378601642830241920567032775895088098706711486764203845425248022960733155994427766750033219106642310531864450654102562104771892268897793145789045570107312401570269581223945259704851104645493075550316424129401227653740942495625720165869565257394427181127734628103
d = 15762135247924329080208071933121250646888501386858311483546464344350547831176536290630826247188272280853810047335214127264865205744683174860903496832368687060941437002920094364116706593296591581117381565805322046922482804679245558495134876677733584718947309975077159564300049936769192724856722338627154192353
e = 65537




t = e*d - 1
s = 0


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


found = False


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


if p > q:
    p, q = q, p


print('NSSCTF{%s}' % hashlib.md5(str(p).encode()).hexdigest())
分享

如果这篇文章对你有帮助，欢迎分享给更多人！

密码刷题笔记
https://wangtanzhi6.github.io/posts/密码刷题/
作者
Wangtanzhi
发布于
2026-04-12
许可协议
CC BY-NC-SA 4.0

部分信息可能已经过时

WP
密码重难知识点学习
相关文章 智能推荐
1
国密学习
CTF 备战浙密杯，好难...好麻烦...
2
PWN刷题笔记
CTF ..第一次参加长城杯...这AWDP和ISW是什么啊，我不是密码、Misc方向的吗...发奋转型Pwn。
3
密码重难知识点学习
CTF 烧一些脑，吐一些血，学习一些好难的算法和知识
4
2026ZJNU校赛WP
CTF 记录一下校赛的题目，感觉题目还是比较合胃口的，做起来没有特别难受，质量也很高୧꒰•̀ᴗ•́꒱୨
5
WP
CTF 用于写WP
随机文章 随机推荐
1
这是啥
记录一下 2026-04-12
2
2026ZJNU校赛WP
CTF 2026-05-21
3
国密学习
CTF 2026-09-01
4
WP
CTF 2026-04-12
5
密码重难知识点学习
CTF 2026-04-12
© 2026 Wangtanzhi. All Rights Reserved. / RSS / Atom / Sitemap
Powered by Astro & Mizuki  Version 9.0

目录