模数 N 相关攻击

Schmidt-Samoa 密码系统

密钥生成：

选取两个大的质数 p 和 q 并进行计算 $N=p^{2}q$
计算 $d=invert(N,(p-1)\ast (q-1))$

加密：

对消息 m，计算密文 $C=m^{N}modN$

解密：

计算明文 $m=c^{d}mod(p\ast q)$

例题：

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

p = getPrime(512)
q = getPrime(512)
n = p*p*q
e = n

c = pow(bytes_to_long(flag), e, n)
d = inverse(e, (p-1)*(q-1))

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

'''
n = 539403894871945779827202174061302970341082455928364137444962844359039924160163196863639732747261316352083923762760392277536591121706270680734175544093484423564223679628430671167864783270170316881238613070741410367403388936640139281272357761773388084534717028640788227350254140821128908338938211038299089224967666902522698905762169859839320277939509727532793553875254243396522340305880944219886874086251872580220405893975158782585205038779055706441633392356197489
d = 58169755386408729394668831947856757060407423126014928705447058468355548861569452522734305188388017764321018770435192767746145932739423507387500606563617116764196418533748380893094448060562081543927295828007016873588530479985728135015510171217414380395169021607415979109815455365309760152218352878885075237009
c = 192900246089028524753714085947506209686933390275949638288635203069117504901164350538204619142802436833736532680210208373707687461486601253665313637541968852691434282584934523173439632554783111037594035333325446559685553119339191110056283203940511701992217372405369575376549738295022767068810511670144120539082403063406787770958515441813335548550876818218065412869322721395317537328975187612606437225577060414403223288106406471061759010085578263501971809720648827
'''

题目分析：

$n=p\ast p\ast q，e=n，c=(flag{)}^{e}modn，ed\equiv 1mod(p-1)\ast (q-1)$

由欧拉定理 ：$a^{phi(N)}\equiv 1modN$

令 a = 2有：$2^{ed}=2^{1+k\ast (p-1)\ast (q-1)}modn=2modn$（k为整数）

得：$2^{ed}-2=k\ast n$（k为整数）

所以：p*q = gcd($2^{ed}-2,n$)

分解 N 得到 p 或 q 的近似值

这种类型的题一般只能求出私钥 p、q 的近似值，一般在可搜索的范围内进行爆破搜索，获取准确的 p、q 值

例题：[2022美团MTCTF] strange_rsa

from Crypto.Util.number import *
from sage.all import RealField
from secret import flag1


Bits = 512
p = getPrime(Bits)
q = getPrime(Bits)
n = p * q

gift = RealField(prec=Bits*2)(p) / RealField(prec=Bits*2)(q)
e = 0x10001
m = bytes_to_long(flag1)
c = pow(m, e, n)

output = open('output.txt', 'w')
output.write('n = ' + str(n) + '\n')
output.write('c = ' + str(c) + '\n')
output.write('gift = ' + str(gift) + '\n')


n = 108525167048069618588175976867846563247592681279699764935868571805537995466244621039138584734968186962015154069834228913223982840558626369903697856981515674800664445719963249384904839446749699482532818680540192673814671582032905573381188420997231842144989027400106624744146739238687818312012920530048166672413
c = 23970397560482326418544500895982564794681055333385186829686707802322923345863102521635786012870368948010933275558746273559080917607938457905967618777124428711098087525967347923209347190956512520350806766416108324895660243364661936801627882577951784569589707943966009295758316967368650512558923594173887431924
gift = 0.9878713210057139023298389025767652308503013961919282440169053652488565206963320721234736480911437918373201299590078678742136736290349578719187645145615363088975706222696090029443619975380433122746296316430693294386663490221891787292112964989501856435389725149610724585156154688515007983846599924478524442938

首先了解一下 RealField (prec = 53, sci_not = 0, rnd = 'MPFR_RDNN' ) 函数，是用于计算浮点数时设置小数的精度，也就是小数的尾数有多少位。

参数：

prec –（整数）精度，默认是53

rnd – （字符串）舍入模式

详情参考： https://doc.sagemath.org/html/en/reference/rings_numerical/sage/rings/real_mpfr.html

由条件知道：n = pq ，gift = p/q ，且 gift 的精度在 1024 bit

由 $n/gitf=q^2$ 开平方根后得到 q 的近似值，然后在附件爆破素数值即可。

上面的设置精度操作需要在 sagemath 中进行

EXP：

#sage
from Crypto.Util.number import long_to_bytes
from gmpy2 import *
from sage.all import *

Bits = 512
e = 0x10001

n = 108525167048069618588175976867846563247592681279699764935868571805537995466244621039138584734968186962015154069834228913223982840558626369903697856981515674800664445719963249384904839446749699482532818680540192673814671582032905573381188420997231842144989027400106624744146739238687818312012920530048166672413
c = 23970397560482326418544500895982564794681055333385186829686707802322923345863102521635786012870368948010933275558746273559080917607938457905967618777124428711098087525967347923209347190956512520350806766416108324895660243364661936801627882577951784569589707943966009295758316967368650512558923594173887431924
gift = 0.9878713210057139023298389025767652308503013961919282440169053652488565206963320721234736480911437918373201299590078678742136736290349578719187645145615363088975706222696090029443619975380433122746296316430693294386663490221891787292112964989501856435389725149610724585156154688515007983846599924478524442938

n = RealField(prec=Bits*2)(n)
q2 = int(n/gift)
print(q2)

n = 108525167048069618588175976867846563247592681279699764935868571805537995466244621039138584734968186962015154069834228913223982840558626369903697856981515674800664445719963249384904839446749699482532818680540192673814671582032905573381188420997231842144989027400106624744146739238687818312012920530048166672413
q_ = iroot(q2,int(2))[0]

limit = 500  # 一步步扩大范围，由小到大扩大范围区间
for q in range(q_ - limit, q_ + limit):
    if is_prime(q) and n // q * q == n:
        print("q =", q)
        print("p =", n // q)

q = 10481297369477678688647473426264404751672609241332968992310058598922120259940804922095197051670288498112926299671514217457279033970326518832408003060034369
p = 10354173078239628635626920146059887542108509101478542108107457141390325356890199583373894457500644181987484104714492532470944829664847264360542662124954077
d = invert(e,(q-1)*(p-1))
print(long_to_bytes(int(pow(c,d,n))))

私钥 P = str(p)+str(q)+str(q)+str(p)

选自 [2021 CryptoCTF] Hamul

题目：

#!/usr/bin/env python3

from Crypto.Util.number import *
from flag import flag

nbit = 64

while True:
    p, q = getPrime(nbit), getPrime(nbit)
    P = int(str(p) + str(q))
    Q = int(str(q) + str(p))
    PP = int(str(P) + str(Q))
    QQ = int(str(Q) + str(P))
    if isPrime(PP) and isPrime(QQ):
        break

n = PP * QQ
m = bytes_to_long(flag.encode('utf-8'))
if m < n:
    c = pow(m, 65537, n)
    print('n =', n)
    print('c =', c)

# n = 98027132963374134222724984677805364225505454302688777506193468362969111927940238887522916586024601699661401871147674624868439577416387122924526713690754043
# c = 42066148309824022259115963832631631482979698275547113127526245628391950322648581438233116362337008919903556068981108710136599590349195987128718867420453399

题目分析：

上述加密程序的突破点在于，计算出 n 的欧拉函数值 phi ，然后计算出私钥 d。

$phi=(PP-1)\ast (QQ-1)$,

$PP=str(p)+str(q)+str(q)+str(p)$；

$QQ=str(q)+str(p)+str(p)+str(q)$

设 x,y = len(str(p)) , len(str(q)) ，则：

$P={10}^{x}p+q，Q={10}^{y}q+p$

设x',y' = len(str(P)) , len(str(Q)) ，则：

$PP={10}^{x^{\prime }}P+Q，QQ={10}^{y^{\prime }}Q+P$

利用上面的两个等式计算 N：

$N=PP\ast QQ={10}^{x+x^{\prime }+y+y^{\prime }}pq+...+pq$

所以我们可以知道 N 的部分高位等于 pq 的部分高位，N 的部分低位也等于 pq 的部分低位

利用这个方法得到 pq 的值，对于不足的中间部分，可以采用爆破的方法获取到

EXP：

from Crypto.Util.number import *

n = 98027132963374134222724984677805364225505454302688777506193468362969111927940238887522916586024601699661401871147674624868439577416387122924526713690754043
e = 65537
c = 42066148309824022259115963832631631482979698275547113127526245628391950322648581438233116362337008919903556068981108710136599590349195987128718867420453399

n_high = str(n)[:18]
n_low = str(n)[-18:]

for i in range(10):
    for j in range(10):
        n = n_high + str(i) + str(j)+ n_low
        x = factor(int(n))
        if len(x)==2 and x[0][0].nbits() == 64:
            p,q = x[0][0],x[1][0]
            print(p)
            print(q)
            
            P = int(str(p) + str(q))
            Q = int(str(q) + str(p))
            PP = int(str(P) + str(Q))
            QQ = int(str(Q) + str(P))
            N = PP * QQ
            print(N)
            
            phi = (QQ-1)*(PP-1)
            d = invert(e,phi)
            m = pow(c,d,N)
            print(long_to_bytes(int(m)))

CCTF{wH3Re_0Ur_Br41N_Iz_5uP3R_4CtIVe_bY_RSA!!}

基于多项式的 RSA

在基于多项式的 RSA 加密中，模数 N 采用的是有限域 $F_p$ 上的两个不可约多项式的乘积，即：$N(x)=P(x)Q(x)$

其中 $P(x)=a_n{x}^n+a_{n-1}{x}^{n-1}+···+a_{1}x+a_0$

$Q(x)=b_n{x}^n+b_{n-1}{x}^{n-1}+···+b_{1}x+b_0$

根据论文：Polynomial based RSA

image-20230408142849163

我们可以 计算出模数 N 的欧拉函数值： $phi=(p^{P(x).degree()}-1)(p^{Q(x).degree()}-1)$

其中的 P(x).degree 即多项式 P(x) 的最高次幂 ，底数p为有限域 $F_p$ 值

例题：[2023 NKCTF] ez_polynomial

题目：

#sage
from Crypto.Util.number import *
flag = list(bytearray(''))
p = getPrime(16)
R.<y> = PolynomialRing(GF(p))
while True:
    P1 = R.random_element(degree=(ZZ.random_element(len(flag), 2*len(flag))))
    Q1 = R.random_element(degree=(ZZ.random_element(len(flag), 2*len(flag))))
    if P1.is_irreducible() and Q1.is_irreducible():
        P = P1
        Q = Q1
        break
e = 65537
N = P*Q
S.<x> = R.quotient(N)
c = S(flag) ^ e
print("P:" + str(p) + "\n")
print("N:" + str(N) + "\n")
print("C:" + str(c))

#P:40031
#N:24096*y^93 + 38785*y^92 + 17489*y^91 + 9067*y^90 + 1034*y^89 + 6534*y^88 + 35818*y^87 + 22046*y^86 + 12887*y^85 + 445*y^84 + 26322*y^83 + 37045*y^82 + 4486*y^81 + 3503*y^80 + 1184*y^79 + 38471*y^78 + 8012*y^77 + 36561*y^76 + 19429*y^75 + 35227*y^74 + 10813*y^73 + 26341*y^72 + 29474*y^71 + 2059*y^70 + 16068*y^69 + 31597*y^68 + 14685*y^67 + 9266*y^66 + 31019*y^65 + 6171*y^64 + 385*y^63 + 28986*y^62 + 9912*y^61 + 10632*y^60 + 33741*y^59 + 12634*y^58 + 21179*y^57 + 35548*y^56 + 17894*y^55 + 7152*y^54 + 9440*y^53 + 4004*y^52 + 2600*y^51 + 12281*y^50 + 22*y^49 + 17314*y^48 + 32694*y^47 + 7693*y^46 + 6567*y^45 + 19897*y^44 + 27329*y^43 + 8799*y^42 + 36348*y^41 + 33963*y^40 + 23730*y^39 + 27685*y^38 + 29037*y^37 + 14622*y^36 + 29608*y^35 + 39588*y^34 + 23294*y^33 + 757*y^32 + 20140*y^31 + 19511*y^30 + 1469*y^29 + 3898*y^28 + 6630*y^27 + 19610*y^26 + 11631*y^25 + 7188*y^24 + 11683*y^23 + 35611*y^22 + 37286*y^21 + 32139*y^20 + 20296*y^19 + 36426*y^18 + 25340*y^17 + 36204*y^16 + 37787*y^15 + 31256*y^14 + 505*y^13 + 27508*y^12 + 20885*y^11 + 32037*y^10 + 31236*y^9 + 7929*y^8 + 27195*y^7 + 28980*y^6 + 11863*y^5 + 16025*y^4 + 16389*y^3 + 570*y^2 + 36547*y + 10451
#C:3552*x^92 + 6082*x^91 + 25295*x^90 + 35988*x^89 + 26052*x^88 + 16987*x^87 + 12854*x^86 + 25117*x^85 + 25800*x^84 + 30297*x^83 + 5589*x^82 + 23233*x^81 + 14449*x^80 + 4712*x^79 + 35719*x^78 + 1696*x^77 + 35653*x^76 + 13995*x^75 + 13715*x^74 + 4578*x^73 + 37366*x^72 + 25260*x^71 + 28865*x^70 + 36120*x^69 + 7047*x^68 + 10497*x^67 + 19160*x^66 + 17939*x^65 + 14850*x^64 + 6705*x^63 + 17805*x^62 + 30083*x^61 + 2400*x^60 + 10685*x^59 + 15272*x^58 + 2225*x^57 + 13194*x^56 + 14251*x^55 + 31016*x^54 + 10189*x^53 + 35040*x^52 + 7042*x^51 + 29206*x^50 + 39363*x^49 + 32608*x^48 + 38614*x^47 + 5528*x^46 + 20119*x^45 + 13439*x^44 + 25468*x^43 + 30056*x^42 + 19720*x^41 + 21808*x^40 + 3712*x^39 + 25243*x^38 + 10606*x^37 + 16247*x^36 + 36106*x^35 + 17287*x^34 + 36276*x^33 + 1407*x^32 + 28839*x^31 + 8459*x^30 + 38863*x^29 + 435*x^28 + 913*x^27 + 36619*x^26 + 15572*x^25 + 9363*x^24 + 36837*x^23 + 17925*x^22 + 38567*x^21 + 38709*x^20 + 13582*x^19 + 35038*x^18 + 31121*x^17 + 8933*x^16 + 1666*x^15 + 21940*x^14 + 25585*x^13 + 840*x^12 + 21938*x^11 + 20143*x^10 + 28507*x^9 + 5947*x^8 + 20289*x^7 + 32196*x^6 + 924*x^5 + 370*x^4 + 14849*x^3 + 10780*x^2 + 14035*x + 15327

EXP：

先将 N 分解为两个多项式，校验是否为不可约多项式，然后计算出私钥 d，解密公式 $m=C^d$ 即可得到明文序列，提取其系数即可。

p = 40031
R.<y> = PolynomialRing(GF(p))
N = 24096*y^93 + 38785*y^92 + 17489*y^91 + 9067*y^90 + 1034*y^89 + 6534*y^88 + 35818*y^87 + 22046*y^86 + 12887*y^85 + 445*y^84 + 26322*y^83 + 37045*y^82 + 4486*y^81 + 3503*y^80 + 1184*y^79 + 38471*y^78 + 8012*y^77 + 36561*y^76 + 19429*y^75 + 35227*y^74 + 10813*y^73 + 26341*y^72 + 29474*y^71 + 2059*y^70 + 16068*y^69 + 31597*y^68 + 14685*y^67 + 9266*y^66 + 31019*y^65 + 6171*y^64 + 385*y^63 + 28986*y^62 + 9912*y^61 + 10632*y^60 + 33741*y^59 + 12634*y^58 + 21179*y^57 + 35548*y^56 + 17894*y^55 + 7152*y^54 + 9440*y^53 + 4004*y^52 + 2600*y^51 + 12281*y^50 + 22*y^49 + 17314*y^48 + 32694*y^47 + 7693*y^46 + 6567*y^45 + 19897*y^44 + 27329*y^43 + 8799*y^42 + 36348*y^41 + 33963*y^40 + 23730*y^39 + 27685*y^38 + 29037*y^37 + 14622*y^36 + 29608*y^35 + 39588*y^34 + 23294*y^33 + 757*y^32 + 20140*y^31 + 19511*y^30 + 1469*y^29 + 3898*y^28 + 6630*y^27 + 19610*y^26 + 11631*y^25 + 7188*y^24 + 11683*y^23 + 35611*y^22 + 37286*y^21 + 32139*y^20 + 20296*y^19 + 36426*y^18 + 25340*y^17 + 36204*y^16 + 37787*y^15 + 31256*y^14 + 505*y^13 + 27508*y^12 + 20885*y^11 + 32037*y^10 + 31236*y^9 + 7929*y^8 + 27195*y^7 + 28980*y^6 + 11863*y^5 + 16025*y^4 + 16389*y^3 + 570*y^2 + 36547*y + 10451

P,Q = N.factor()
P,Q = P[0],Q[0]
assert P.is_irreducible() and Q.is_irreducible()

S.<x> = R.quotient(N)
e = 65537
d = invert(e,(p^P.degree()-1)*(p^Q.degree()-1))
C = 3552 * x ^ 92 + 6082 * x ^ 91 + 25295 * x ^ 90 + 35988 * x ^ 89 + 26052 * x ^ 88 + 16987 * x ^ 87 + 12854 * x ^ 86 + 25117 * x ^ 85 + 25800 * x ^ 84 + 30297 * x ^ 83 + 5589 * x ^ 82 + 23233 * x ^ 81 + 14449 * x ^ 80 + 4712 * x ^ 79 + 35719 * x ^ 78 + 1696 * x ^ 77 + 35653 * x ^ 76 + 13995 * x ^ 75 + 13715 * x ^ 74 + 4578 * x ^ 73 + 37366 * x ^ 72 + 25260 * x ^ 71 + 28865 * x ^ 70 + 36120 * x ^ 69 + 7047 * x ^ 68 + 10497 * x ^ 67 + 19160 * x ^ 66 + 17939 * x ^ 65 + 14850 * x ^ 64 + 6705 * x ^ 63 + 17805 * x ^ 62 + 30083 * x ^ 61 + 2400 * x ^ 60 + 10685 * x ^ 59 + 15272 * x ^ 58 + 2225 * x ^ 57 + 13194 * x ^ 56 + 14251 * x ^ 55 + 31016 * x ^ 54 + 10189 * x ^ 53 + 35040 * x ^ 52 + 7042 * x ^ 51 + 29206 * x ^ 50 + 39363 * x ^ 49 + 32608 * x ^ 48 + 38614 * x ^ 47 + 5528 * x ^ 46 + 20119 * x ^ 45 + 13439 * x ^ 44 + 25468 * x ^ 43 + 30056 * x ^ 42 + 19720 * x ^ 41 + 21808 * x ^ 40 + 3712 * x ^ 39 + 25243 * x ^ 38 + 10606 * x ^ 37 + 16247 * x ^ 36 + 36106 * x ^ 35 + 17287 * x ^ 34 + 36276 * x ^ 33 + 1407 * x ^ 32 + 28839 * x ^ 31 + 8459 * x ^ 30 + 38863 * x ^ 29 + 435 * x ^ 28 + 913 * x ^ 27 + 36619 * x ^ 26 + 15572 * x ^ 25 + 9363 * x ^ 24 + 36837 * x ^ 23 + 17925 * x ^ 22 + 38567 * x ^ 21 + 38709 * x ^ 20 + 13582 * x ^ 19 + 35038 * x ^ 18 + 31121 * x ^ 17 + 8933 * x ^ 16 + 1666 * x ^ 15 + 21940 * x ^ 14 + 25585 * x ^ 13 + 840 * x ^ 12 + 21938 * x ^ 11 + 20143 * x ^ 10 + 28507 * x ^ 9 + 5947 * x ^ 8 + 20289 * x ^ 7 + 32196 * x ^ 6 + 924 * x ^ 5 + 370 * x ^ 4 + 14849 * x ^ 3 + 10780 * x ^ 2 + 14035 * x + 15327
# print("d =",d)

m = pow(C,d)

print("".join([chr(i) for i in m.list()]))
#NKCTF{We_HaV3_n0th1ng_But_dr3amS}

已知N、phi 分解N

考的知识是关于在 RSA 的加密过程中要注意对 phi(N) 值的保密，当我们已知 N 及其欧拉函数值 phi(N) 时，即可将 N 成功分解拿到私钥。

对于 N=pq 和 phi(N)=(p-1)(q-1) 我们有如下关系：

$\phi (N)=(p-1)(q-1)=pq-p-q+1=(N+1)-(p+q)$

易得到：$(n+1)-\phi (N)=p+q\Rightarrow (n+1)-\phi (N)-p=q$

由 N = pq 代入上式得：$N=p(n+1-\phi (N)-p)=-p^2+(N+1-\phi (N))p$

所以：$p^2-(N+1-\phi (N))p+N=0$

这是一个关于 p 的二次方程：

有 $a=1，b=-(N+1-\phi (N))，c=N$

所以我们能够根据一元二次方程的求根公式求解： $p=\frac{-b\pm \sqrt{b^2-4ac}}{2a}$

即可成功分解 N=pq的因子。

github上的实现脚本：能够成功分解双素因子和多素因子的N

from math import gcd
from math import isqrt
from random import randrange

from sage.all import is_prime


def factorize(N, phi):
    """
    Recovers the prime factors from a modulus if Euler's totient is known.
    This method only works for a modulus consisting of 2 primes!
    :param N: the modulus
    :param phi: Euler's totient, the order of the multiplicative group modulo N
    :return: a tuple containing the prime factors, or None if the factors were not found
    """
    s = N + 1 - phi
    d = s ** 2 - 4 * N
    p = int(s - isqrt(d)) // 2
    q = int(s + isqrt(d)) // 2
    return p, q


def factorize_multi_prime(N, phi):
    """
    Recovers the prime factors from a modulus if Euler's totient is known.
    This method works for a modulus consisting of any number of primes, but is considerably be slower than factorize.
    More information: Hinek M. J., Low M. K., Teske E., "On Some Attacks on Multi-prime RSA" (Section 3)
    :param N: the modulus
    :param phi: Euler's totient, the order of the multiplicative group modulo N
    :return: a tuple containing the prime factors
    """
    prime_factors = set()
    factors = [N]
    while len(factors) > 0:
        # Element to factorize.
        N = factors[0]

        w = randrange(2, N - 1)
        i = 1
        while phi % (2 ** i) == 0:
            sqrt_1 = pow(w, phi // (2 ** i), N)
            if sqrt_1 > 1 and sqrt_1 != N - 1:
                # We can remove the element to factorize now, because we have a factorization.
                factors = factors[1:]

                p = gcd(N, sqrt_1 + 1)
                q = N // p

                if is_prime(p):
                    prime_factors.add(p)
                elif p > 1:
                    factors.append(p)

                if is_prime(q):
                    prime_factors.add(q)
                elif q > 1:
                    factors.append(q)

                # Continue in the outer loop
                break

            i += 1

    return tuple(prime_factors)

例题：[2023 NKCTF] ezRSA

from Crypto.Util.number import *
from secret import flag

m1 = bytes_to_long(flag[:len(flag)//3])
m2 = bytes_to_long(flag[len(flag)//3:])

def gen():
    prime_list  = []
    for i in range(4):
        prime_list.append(getPrime(512))
    return sorted(prime_list)

prime_list = gen()
p,q,r,t = prime_list[0],prime_list[3],prime_list[1],prime_list[2]
e = 65537
n = p*q*r*t
phi = (p-1)*(q-1)*(r-1)*(t-1)
c1 = pow(m1,e,p*q)

p1 = getPrime(512)
q1 = getPrime(512)
N = p1*q1
c2 = pow(m2,p1,N)
c3 = pow(m2,q1,N)
print(f'n = {n}')
print(f'phi = {phi}')
print(f'c1 = {c1}')
print(f'N = {N}')
print(f'c2 = {c2}')
print(f'c3 = {c3}')

'''
n = 8836130216343708623415307573630337110573363595188748983290313549413242332143945452914800845282478216810685733227137911630239808895196748125078747600505626165666334675100147790578546682128517668100858766784733351894480181877144793496927464058323582165412552970999921215333509253052644024478417393146000490808639363681195799826541558906527985336104761974023394438549055804234997654701266967731137282297623426318212701157416397999108259257077847307874122736921265599854976855949680133804464839768470200425669609996841568545945133611190979810786943246285103031363790663362165522662820344917056587244701635831061853354597
phi = 8836130216343708623415307573630337110573363595188748983290313549413242332143945452914800845282478216810685733227137911630239808895196748125078747600505622503351461565956106005118029537938273153581675065762015952483687057805462728186901563990429998916382820576211887477098611684072561849314986341226981300596338314989867731725668312057134075244816223120038573374383949718714549930261073576391501671722900294331289082826058292599838631513746370889828026039555245672195833927609280773258978856664434349221972568651378808050580665443131001632395175205804045958846124475183825589672204752895252723130454951830966138888560
c1 = 78327207863361017953496121356221173288422862370301396867341957979087627011991738176024643637029313969241151622985226595093079857523487726626882109114134910056673489916408854152274726721451884257677533593174371742411008169082367666168983943358876017521749198218529804830864940274185360506199116451280975188409
N = 157202814866563156513184271957553223260772141845129283711146204376449001653397810781717934720804041916333174673656579086498762693983380365527400604554663873045166444369504886603233275868192688995284322277504050322927511160583280269073338415758019142878016084536129741435221345599028001581385308324407324725353
c2 = 63355788175487221030596314921407476078592001060627033831694843409637965350474955727383434406640075122932939559532216639739294413008164038257338675094324172634789610307227365830016457714456293397466445820352804725466971828172010276387616894829328491068298742711984800900411277550023220538443014162710037992032
c3 = 9266334096866207047544089419994475379619964393206968260875878305040712629590906330073542575719856965053269812924808810766674072615270535207284077081944428011398767330973702305174973148018082513467080087706443512285098600431136743009829009567065760786940706627087366702015319792328141978938111501345426931078
'''

分析题目：

根据给的加密代码可知题目分为两个加密部分：m1 和 m2

一、m1加密部分

p,q,r,t = prime_list[0],prime_list[3],prime_list[1],prime_list[2]
e = 65537
n = p*q*r*t
phi = (p-1)*(q-1)*(r-1)*(t-1)
c1 = pow(m1,e,p*q)

给了 n 和 phi 的值，直接用上面的脚本即可成功分解N 的素因子。然后进行常规RSA解密即可，需要试一下解密的素因数具体是那两个。

二、m2 加密部分

c2 = pow(m2,p1,N)
c3 = pow(m2,q1,N)

这里直接写 m ,p ,q 了

$$c2=m^{p}modN\Rightarrow c2=m^p+k1\ast pq$$

等式两边用时除以 p：

$$c2=m^{p}modp$$

由费马小定理得式1：

$$c2=mmodp\Rightarrow c2=m+k_1\ast p$$

同理得：

$$c3=m^{q}modN\Rightarrow c3=m^q+k2\ast pq$$

等式两边用时除以 q：

$$c3=m^{q}modq$$

式2：

$$c3=mmodq\Rightarrow c3=m+k_2\ast q$$

联立式1、式2得：

$$c2\ast c3=(m+k_1\ast p)\ast (m+k_2\ast q)=-m^2+(c2+c3)\ast m+k_1{k}_2\ast pq$$$$\Rightarrow c2\ast c3=-m^2+(c2+c3)\ast mmodN$$

这样就构造成了一个关于 m 的模多项式，我们用 sagemath 计算出其根值即可。

EXP：

from Crypto.Util.number import *
from gmpy2 import gcd, invert
from math import gcd, isqrt
from random import randrange
from gmpy2 import is_prime


def factorize_multi_prime(N, phi):
    """
    Recovers the prime factors from a modulus if Euler's totient is known.
    This method works for a modulus consisting of any number of primes, but is considerably be slower than factorize.
    More information: Hinek M. J., Low M. K., Teske E., "On Some Attacks on Multi-prime RSA" (Section 3)
    :param N: the modulus
    :param phi: Euler's totient, the order of the multiplicative group modulo N
    :return: a tuple containing the prime factors
    """
    prime_factors = set()
    factors = [N]
    while len(factors) > 0:
        # Element to factorize.
        N = factors[0]

        w = randrange(2, N - 1)
        i = 1
        while phi % (2 ** i) == 0:
            sqrt_1 = pow(w, phi // (2 ** i), N)
            if sqrt_1 > 1 and sqrt_1 != N - 1:
                # We can remove the element to factorize now, because we have a factorization.
                factors = factors[1:]

                p = gcd(N, sqrt_1 + 1)
                q = N // p

                if is_prime(p):
                    prime_factors.add(p)
                elif p > 1:
                    factors.append(p)

                if is_prime(q):
                    prime_factors.add(q)
                elif q > 1:
                    factors.append(q)

                # Continue in the outer loop
                break
            i += 1

    return tuple(prime_factors)


e = 65537
n = 8836130216343708623415307573630337110573363595188748983290313549413242332143945452914800845282478216810685733227137911630239808895196748125078747600505626165666334675100147790578546682128517668100858766784733351894480181877144793496927464058323582165412552970999921215333509253052644024478417393146000490808639363681195799826541558906527985336104761974023394438549055804234997654701266967731137282297623426318212701157416397999108259257077847307874122736921265599854976855949680133804464839768470200425669609996841568545945133611190979810786943246285103031363790663362165522662820344917056587244701635831061853354597
phi = 8836130216343708623415307573630337110573363595188748983290313549413242332143945452914800845282478216810685733227137911630239808895196748125078747600505622503351461565956106005118029537938273153581675065762015952483687057805462728186901563990429998916382820576211887477098611684072561849314986341226981300596338314989867731725668312057134075244816223120038573374383949718714549930261073576391501671722900294331289082826058292599838631513746370889828026039555245672195833927609280773258978856664434349221972568651378808050580665443131001632395175205804045958846124475183825589672204752895252723130454951830966138888560
c1 = 78327207863361017953496121356221173288422862370301396867341957979087627011991738176024643637029313969241151622985226595093079857523487726626882109114134910056673489916408854152274726721451884257677533593174371742411008169082367666168983943358876017521749198218529804830864940274185360506199116451280975188409

p, q, r, t = factorize_multi_prime(n, phi)
assert p * q * r * t == n
Phi = (q - 1) * (t - 1)
n1 = q * t
d = invert(e, Phi)
m1 = pow(c1, d, n1)
print(long_to_bytes(m1))

#%%
#sage
from sage.all import PolynomialRing
from Crypto.Util.number import *

N = 157202814866563156513184271957553223260772141845129283711146204376449001653397810781717934720804041916333174673656579086498762693983380365527400604554663873045166444369504886603233275868192688995284322277504050322927511160583280269073338415758019142878016084536129741435221345599028001581385308324407324725353
c2 = 63355788175487221030596314921407476078592001060627033831694843409637965350474955727383434406640075122932939559532216639739294413008164038257338675094324172634789610307227365830016457714456293397466445820352804725466971828172010276387616894829328491068298742711984800900411277550023220538443014162710037992032
c3 = 9266334096866207047544089419994475379619964393206968260875878305040712629590906330073542575719856965053269812924808810766674072615270535207284077081944428011398767330973702305174973148018082513467080087706443512285098600431136743009829009567065760786940706627087366702015319792328141978938111501345426931078

R.<x> = PolynomialRing(Zmod(N))
f = -(x**2) + (c2+c3)*x - c2*c3
f = f.monic()
root = f.small_roots(X=2^432)[0]
print(root)
print(long_to_bytes(int(root)))

b'NKCTF{it_i5_e45y_th4t_Kn0wn'

b'_phi_4nd_N_dec0mp0ses_N_w1th_th3_s4m3_c0mm0n_n_but_pq}'

法二：

关于第二部分 m2 的加密，我们还可以通过联立两个等式，构造出和 N 存在公约数 p或 q

c2 = pow(m2,p1,N)
c3 = pow(m2,q1,N)

$$c_2=m^{p}modN\Rightarrow c_2^q=m^{pq}modN$$

将 c3 的等式代入，得到：

$$c_2^q=c_3^{p}modN\Rightarrow c_2^{pq}=(c_3^p{)}^{p}modN\Rightarrow c_2^{pq}=(c_3^p{)}^p+k\ast N$$

两边模 p 得：

$$c_2^N=(c_3^p{)}^{p}modp$$

费马小定理得：

$$c_2^N=c_{3}modp\Rightarrow c_2^N=c_3+k\ast p$$

所以：

$$p=gcd(N,c_2^N-c_3)$$

共模攻击

常规共模攻击

共模攻击，Common Modulus Attack，也称为同模攻击。同模攻击利用的大前提就是，RSA体系在生成密钥的过程中使用了相同的模数 N。对于同一条明文m，新手小白 A 和 B 对其进行加密：

$$A:C_1\equiv M^{e_1}modn，B:C_2\equiv M^{e_2}modn$$

如果，此时有一个攻击者，同时监听了A和B接收到的密文 C1,C2 。因为模数不变，以及所有的公钥都是公开的，那么利用同模攻击，就可以在不知道 $d1,d2$ 的条件下破解明文 M

算法分析过程：

image-20230329131102785|600

例题：

c1=22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361
n=22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801
e1=11187289
c2=18702010045187015556548691642394982835669262147230212731309938675226458555210425972429418449273410535387985931036711854265623905066805665751803269106880746769003478900791099590239513925449748814075904017471585572848473556490565450062664706449128415834787961947266259789785962922238701134079720414228414066193071495304612341052987455615930023536823801499269773357186087452747500840640419365011554421183037505653461286732740983702740822671148045619497667184586123657285604061875653909567822328914065337797733444640351518775487649819978262363617265797982843179630888729407238496650987720428708217115257989007867331698397
e2=9647291

EXP：

from libnum import*   #python第三方库
from gmpy2 import*    #python第三方库

n = 22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801
c1 = 22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361
c2 = 18702010045187015556548691642394982835669262147230212731309938675226458555210425972429418449273410535387985931036711854265623905066805665751803269106880746769003478900791099590239513925449748814075904017471585572848473556490565450062664706449128415834787961947266259789785962922238701134079720414228414066193071495304612341052987455615930023536823801499269773357186087452747500840640419365011554421183037505653461286732740983702740822671148045619497667184586123657285604061875653909567822328914065337797733444640351518775487649819978262363617265797982843179630888729407238496650987720428708217115257989007867331698397
e1 = 11187289
e2 = 9647291

s = gcdext(e1,e2)    #gmpy2.gcdext(),扩展欧几里得算法，返回tuple元组，满足s[1]*e1+s[2]*e2=1
m = pow(c1,s[1],n)*pow(c2,s[2],n)%n   #获取明文m
print(n2s(m))

指数e1、e2不互素

直接上面的原理推导就行，最后的结果要开根 gcd(e1,e2)

EXP：

from gmpy2 import gcdext, iroot
from Crypto.Util.number import long_to_bytes

c1 = 65902678572727724179176496573968997182712063317082289120453094068199325419989688382177808529042322217887334005084504796397220804856167255176415690217348252126097809130195208020694026250194047460581165024178358434305495364983830756552379335985399876528922076030595232679046941310786637260764992499375421464529
c2 = 85809403678250150153291471185999805870858123001273034212582847731825296891016810871397546134117012197599651729401590980020028382884068513201758926416192211821922593686232475967808964006786076460160428639353153658323208119453055070199243295330522804974849330926501091430419775155670264306222962413289616957519
n = 93012379949596679874010836520972463438155175961283277743514203871114329008044735500726440012464029144204813413909322389585966313426611488927292874319628063526009405144436605996389985977340280983469803412119458185047475253059636126555451557348169514975249710901899526974246139559730461540660990375034669042959
e1 = 667430104865289
e2 = 537409930523421

g, x, y = gcdext(e1, e2)
m = pow(c1, x, n) * pow(c2, y, n) % n
m = iroot(m, 3)[0]

print(long_to_bytes(m))

指数 e1、e2、e3不互素

例题：

n = 14142010206099386143235977555692857399310494373372334255226213043954222671886219214790080363755519983589419573494262932031062165425660149023699589427423291076757673539031113758789961660789969074666728548356143546954548237178966812807683542026090314756465049840269239582841323515153189937744280883895942616355068450477244038093783025761830910527817275117470273068582606801561816182028771714266926279491448124072638544823523354972471012076902504991756879694948477398253632905720027515230565063830199860044535605314432273647912553716877788661706091962626029470938285869557993283863813783012548154763397158585969860496209
e1 = 8044170206501208651566242545498471362911890649958881015968520025930186294576023443506808099677296038797758573489705294289102108150592764180571398770862282775413964383616485564171756065468610971753771700993772575426420613330938626182989999507422559869431997096499661057456703567386749182728255894961711
c1 = 11517322714245526592044873592382373283428914348422645739336159016405003731268657488015847458779166523731678788259036486197351408324218938844963108776390284845014868126098529982171539875948326597563481747612010865265679909207769244324752454968172401384300433252342047155447253514663020084257315172025978213587941036806257025876560069777775117798912056950800470305039358493009376541529192357082470617915062674822440632959240104574498373020678875137349967659371746447815516349204225897744273956308472359601558104152900628002351072193856499370256139818744736463310402972428459727204523498170929275318085749369313370330104
e2 = 7981110843177277522743262582712207767500318326009118362192817529414323700650435360291001887232564132664914694220334201133850645107707193720930288877874115700468049318771691746592219604611120450612600603061311788240065247605723819417162805390035814213048743243801428908542140081097421519822132590047533
c2 = 12907231513900923422005862146378905589636791955213455533815625546155661275692081099543894853443339737652933422555561840945917851059973294781475696342510739464313686827430856742266071924616860913810640580296234473777303348248031669837803543965896443694327322478656672147536068477193332582821244877632320706358476947499828283809012293724747791713411303065091158644428874828519807586496004634361827049528190857803358038226873772036022804215684911051370929474550764142943510840488678370689581686370179457811111602201500802245275266633124851078915997894235280935026230159846619929979668248511374747926732890795947582868735
e3 = 8321945773137532897701269832287423438330975369722946793416731752574708023263908693097168458920645511451157398450278461406044452962800707032660103849647429968263806321843635237930345258217128805872313308435747131438472827261934005675575066641207582827978944766548998867180054428477087525524476746729443
c3 = 14065425026445215199826296511184881258323064633386950509660192854866326626040354040592178906620984652169865998063876885421774133239148395916412178848784041317916589243316140373118461629430419305769180856968279675982734449182890302977853892881391084830333333875116598959777525928574769839174695101654696531535920235825780434207646161363349309470260223615977113109458426965856166705879375711518022880712089324008258280991081209228374850515248942548172463741894540420262751207821783524890116559086561517224038086473047623408064157594299815732082781632190258405091440187576055868450259807171733509904666142689629066721239

算法分析：

通过观察可以知道如下数学关系

$$e_1=a\ast b，e_2=a\ast c，e_3=b\ast c$$$$c_1=m^{e_1}modn，c_2=m^{e_2}modn，c_3=m^{e_3}modn$$$$\Rightarrow c_1=m^{ab}modn，c_2=m^{ac}modn，c_3=m^{bc}modn$$

由 $gcd(e_1,e_2)=a，gcd(e_1,e_3)=b，gcd(e_2,e_3)=c$ ，结合共模攻击的理论知识得：

1. $c_1^{s_1}\ast c_2^{s_2}modn，b{s}_1+c{s}_2=1$ 后面有些步骤就省略模 n 了，这里因为 b,c 互质用扩展欧几里得算法可以求出解 s1,s2

由 $c \equiv m^e \ mod \ n $，\mathrm{得}：$ m^{e_1*s_1}*m{e_2s_2} = m^{abs_1 + ac*s_2} = m^a \ mod \ n$

2. 同理可得： $c_2^{s_2}\ast c_3^{s_3}modn，a{s}_2+b{s}_3=1\Rightarrow$ $m^{e_2\ast s_2}\ast m^{e_3\ast s_3}=m^{c\ast (a\ast s_2+b\ast s_3)}=m^{c}modn$

3. 通过上面两个式子能够得到：$m^a\mathrm{和}{m}^c$ ，由：$m^{a\ast s_1}\ast m^{c\ast s_3}，a{s}_1+c{s}_3=1\Rightarrow$ $m^{a{s}_1+c{s}_3}modn=mmodn$

EXP：

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

n = 14142010206099386143235977555692857399310494373372334255226213043954222671886219214790080363755519983589419573494262932031062165425660149023699589427423291076757673539031113758789961660789969074666728548356143546954548237178966812807683542026090314756465049840269239582841323515153189937744280883895942616355068450477244038093783025761830910527817275117470273068582606801561816182028771714266926279491448124072638544823523354972471012076902504991756879694948477398253632905720027515230565063830199860044535605314432273647912553716877788661706091962626029470938285869557993283863813783012548154763397158585969860496209
e1 = 8044170206501208651566242545498471362911890649958881015968520025930186294576023443506808099677296038797758573489705294289102108150592764180571398770862282775413964383616485564171756065468610971753771700993772575426420613330938626182989999507422559869431997096499661057456703567386749182728255894961711
c1 = 11517322714245526592044873592382373283428914348422645739336159016405003731268657488015847458779166523731678788259036486197351408324218938844963108776390284845014868126098529982171539875948326597563481747612010865265679909207769244324752454968172401384300433252342047155447253514663020084257315172025978213587941036806257025876560069777775117798912056950800470305039358493009376541529192357082470617915062674822440632959240104574498373020678875137349967659371746447815516349204225897744273956308472359601558104152900628002351072193856499370256139818744736463310402972428459727204523498170929275318085749369313370330104
e2 = 7981110843177277522743262582712207767500318326009118362192817529414323700650435360291001887232564132664914694220334201133850645107707193720930288877874115700468049318771691746592219604611120450612600603061311788240065247605723819417162805390035814213048743243801428908542140081097421519822132590047533
c2 = 12907231513900923422005862146378905589636791955213455533815625546155661275692081099543894853443339737652933422555561840945917851059973294781475696342510739464313686827430856742266071924616860913810640580296234473777303348248031669837803543965896443694327322478656672147536068477193332582821244877632320706358476947499828283809012293724747791713411303065091158644428874828519807586496004634361827049528190857803358038226873772036022804215684911051370929474550764142943510840488678370689581686370179457811111602201500802245275266633124851078915997894235280935026230159846619929979668248511374747926732890795947582868735
e3 = 8321945773137532897701269832287423438330975369722946793416731752574708023263908693097168458920645511451157398450278461406044452962800707032660103849647429968263806321843635237930345258217128805872313308435747131438472827261934005675575066641207582827978944766548998867180054428477087525524476746729443
c3 = 14065425026445215199826296511184881258323064633386950509660192854866326626040354040592178906620984652169865998063876885421774133239148395916412178848784041317916589243316140373118461629430419305769180856968279675982734449182890302977853892881391084830333333875116598959777525928574769839174695101654696531535920235825780434207646161363349309470260223615977113109458426965856166705879375711518022880712089324008258280991081209228374850515248942548172463741894540420262751207821783524890116559086561517224038086473047623408064157594299815732082781632190258405091440187576055868450259807171733509904666142689629066721239

a = gcd(e1, e2)
b = gcd(e1, e3)
c = gcd(e2, e3)
assert gcd(a, b) == 1 and gcd(a, c) == 1 and gcd(b, c) == 1
assert e1 == a * b


def common_mon(e1, e2, c1, c2, n):
    s = gcdext(e1, e2)
    m = pow(c1, s[1], n) * pow(c2, s[2], n) % n  # 获取明文m
    return m


enc1 = common_mon(b, c, c1, c2, n)
enc2 = common_mon(a, b, c2, c3, n)

flag = common_mon(a, c, enc1, enc2, n)
print(long_to_bytes(flag))

需构造模多项式类型

题目：[SWPUCTF 2021 新生赛]crypto3

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

flag  = '******************'
p = getPrime(512)
q = getPrime(512)
m1 = bytes_to_long(bytes(flag.encode()))
n = p*q

flag1 = pow(m1,p,n)
flag2 = pow(m1,q,n)
print('flag1= '+str(flag1))
print('flag2= '+str(flag2))
print('n= '+str(n))

#flag1= 17893542812755845772427795161304049467610774531005620109503081344099161906017295486868699578946474114607624347167976713200068059018517606363517478396368430072890681401898145302336139240273132723451063402106360810413024642916851746118524166947301681245568333254648265529408446609050354235727237078987509705857
#flag2= 95580409405085606847879727622943874726633827220524165744517624606566789614499137069562997931972825651309707390763700301965277040876322904891716953565845966918293178547100704981251056401939781365264616997055296773593435626490578886752446381493929807909671245959154990639046333135728431707979143972145708806954
#n= 140457323583824160338989317689698102738341061967768153879646505422358544720607476140977064053629005764551339082120337223672330979298373653766782620973454095507484118565884885623328751648660379894592063436924903894986994746394508539721459355200184089470977772075720319482839923856979166319700474349042326898971

分析：

这里 $c1=m^{p}modn，c2=m^{q}modn$

推导： $c1=m^p+k1\ast n，c2=m^q+k2\ast n$

c1，c2分别两边同时模 p 模 q，利用费马小定理得：$c1=m+k_1^{\prime }\ast p，c2=m+k_2^{\prime }\ast q$

式一：$c_1\ast c_2=(m+k_1^{\prime }\ast p)\ast (m+k_2^{\prime }\ast q)=m^2+m\ast (k_1^{\prime }\ast p+k_2^{\prime }\ast q)+k_1^{\prime }{k}_2^{\prime }\ast n$

式二：$c_1+c_2=2m+k_1^{\prime }\ast p+k_2^{\prime }\ast q$

等式两边同时乘以 m 得式三：$m\ast (c_1+c_2)=2m^2+m\ast (k_1^{\prime }\ast p+k_2^{\prime }\ast q)$

联立式一、三得到：$m^2-(c_1+c_2)m+c_1{c}_2\equiv 0modn$

成功构造模多项式，然后用coppersmith求根即可得到m

EXP:

from Crypto.Util.number import *
from gmpy2 import *
from sage.all import PolynomialRing 

c1 = 
c2= 
n = 

PR.<x> = PolynomialRing(Zmod(n))

f = x^2 - (c1+c2)*x + c1*c2
f = f.monic()
root = f.small_roots(X=2^200)
print(root)
print(long_to_bytes(int(root[0])))

#[1920535408007397834236393374892057067669865609963495845501]
#b'NSSCTF{why_gongmo_again}'

Fermat 分解（|p-q|过小）

$N=p\ast q,N=(\frac{p+q}{2}{)}^2-(\frac{p-q}{2}{)}^2$

例如 N = 21, p= 3 , q= 7

例题实现 ： [2022柏鹭杯] Anti-Fermat？

from Crypto.Util.number import isPrime,getStrongPrime,bytes_to_long
from gmpy2 import next_prime
from secret import flag

p = getStrongPrime(1024)
q = next_prime(p ^ ((1 << 1024)-1))
n = p * q
e = 65537

m = bytes_to_long(flag)
assert m < n
c = pow(m, e, n)

print('n = ', hex(n))
print('c = ', hex(c))

#n= 0x31e22a7a2c5ec946692357dc51014a80530afeb46f419831fcbd896aa1d5cee2d0c69123b3017067afdb3d82b2be3535aebdf11da0fa2b4873233bae6af8a1c2a9344b6f64ade1c6c48a2828130c352053e1729b850774589e8947c8c0a472a8dc90caa542da5cec7f5fa7581747dcb558300437c30b016f769d4a85af8584f311dfb2f9e87fa7d16eaccb0303ecba491619ec7dda72e4037d96c607e666eced582d6eb2c232689fce1c08a54b80cf6d39ef1f2b467d970998c6d54d1779979c89a3b301cd1435bde8787d1141c912cf32b56610fba9205c6e86fefc490c8b2e06f5ed9f775f5b0fe945fa9fca3fc217b4c9dcd4b26676f576d0273b79417b81
#c= 0x118dd8ab5df8685c5db5b1242896df41e8e9016f5f16276b6d311b29f0e5f9315530574b51c6e7c82d0c88ab92787d639443b921a452c850db580256ccfd55ee52ea9732821525da1d21351acb230a799ecaa1802c6f24487176c9cae537c3188e083552a84a2aebdd55c4014b41846768d7608970c1e52d9a68e550ef8bb6016adb6f8e0672e1c8198a5442799a5b8142e8d0fadb6e6146a062ef906bd58c46f31bf65263b6142b1976773289dee408ae233b6c0c534dd5092bd7f331c3457971278d335923edc044ba88852680ee39d1cc84a66dc81b70039e2435892b11f310b490c872448f7a8dc718759b2052b0911f758102a59c54dea061a8a3ff6879

题目中提到了 Fermat 肯定和 费马分解相关，由已知条件通过做一个小测试可以分析出解题步骤

p = getStrongPrime(1024)

q = next_prime(p ^ ((1 << 1024)-1))

from Crypto.Util.number import *

a = (1<<10) - 1
b = getPrime(10)
print(bin(a))
print(bin(b))
print(bin(b^a))
print(bin(a - b))

0b1111111111
0b1111000111
0b111000
0b111000

得到 b ^ a = a - b

所以：p ^ ((1 << 1024)-1) = ((1<<1024) - 1) - p ，

因为：q = next_prime(p ^ ((1 << 1024)-1)) ，设 q = ((1<<1024) - 1) - p + k （设 k 为相差的值）

所以：q + p = ((1<<1024) - 1) + k

由费马分解定理得：$p-q=\sqrt{(p+q{)}^2-4N}$

k 为 p ^ ((1 << 1024)-1) 与下一个素数之差，所以可以爆破 k 寻找满足 $q+p=((1<<1024)-1)+k\mathrm{和}p-q=\sqrt{(p+q{)}^2-4N}$ 的 k 值

EXP :

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

n = 6297203518453373381548792689756717804994855144069657925537066909086145361389510779319742213376443676964163560360595857883766237108244147281086046999346010340574774615945352346123540205567621400382386920894901104694516425648896927590700430740544169734382910081671229317752924872431047591721579815244003541817065076525458738561329976681215510817951929803558554464575347850312449496557973529505408688069977936527771757913887401610737508152501064107892794789679083915786747045353769083004406219388364076959570440651592148837721420118405881916093745127268783062444829432493510965152911233950429724509905557307558123895681
c = 0x118dd8ab5df8685c5db5b1242896df41e8e9016f5f16276b6d311b29f0e5f9315530574b51c6e7c82d0c88ab92787d639443b921a452c850db580256ccfd55ee52ea9732821525da1d21351acb230a799ecaa1802c6f24487176c9cae537c3188e083552a84a2aebdd55c4014b41846768d7608970c1e52d9a68e550ef8bb6016adb6f8e0672e1c8198a5442799a5b8142e8d0fadb6e6146a062ef906bd58c46f31bf65263b6142b1976773289dee408ae233b6c0c534dd5092bd7f331c3457971278d335923edc044ba88852680ee39d1cc84a66dc81b70039e2435892b11f310b490c872448f7a8dc718759b2052b0911f758102a59c54dea061a8a3ff6879
e = 65537

for k in range(1000000):
    t1 = ((1 << 1024) - 1) + k
    t2, s = iroot(pow(t1, 2) - 4 * n, 2)
    if s:
        p = (t1 + t2) // 2
        q = n // p
        assert p*q == n
        # print(p, q)
        d = invert(e,(q-1)*(p-1))
        print(long_to_bytes(pow(c,d,n)))

例题：[2022祥云杯]little little fermat

#题目
from Crypto.Util.number import *
from random import *
from libnum import *
import gmpy2
from secret import x

flag = b'?????????'
m = bytes_to_long(flag)
def obfuscate(p, k):
    nbit = p.bit_length()
    while True:
        l1 = [getRandomRange(-1, 1) for _ in '_' * k]
        l2 = [getRandomRange(100, nbit) for _ in '_' * k]
        l3 = [getRandomRange(10, nbit//4) for _ in '_' * k]
        l4 = [getRandomRange(2, 6) for _ in '_' *k]
        A = sum([l1[_] * 2 ** ((l2[_]+l3[_])//l4[_]) for _ in range(0, k)])
        q = p + A
        if isPrime(q) * A != 0:
            return q

p = getPrime(512)
q = obfuscate(p, 5)
e = 65537
n = p*q
print(f'n = {n}')

assert 114514 ** x % p == 1
m = m ^ (x**2)
c = pow(m, e, n)
print(f'c = {c}')

'''
n = 141321067325716426375483506915224930097246865960474155069040176356860707435540270911081589751471783519639996589589495877214497196498978453005154272785048418715013714419926299248566038773669282170912502161620702945933984680880287757862837880474184004082619880793733517191297469980246315623924571332042031367393
c = 81368762831358980348757303940178994718818656679774450300533215016117959412236853310026456227434535301960147956843664862777300751319650636299943068620007067063945453310992828498083556205352025638600643137849563080996797888503027153527315524658003251767187427382796451974118362546507788854349086917112114926883
'''

题目提到 fermat ，所以可以用到费马分解算法求出 p,q 的值，通过测试中间数据 A 的值得到 A为负数，且 A 大概在 100-200bit之间的大小，所以 p,q相差不大

其实这里直接用 yafu就分解出来 p,q了，因为 yafu分解N的算法就包含了费马分解，一般只能解决 p,q相差较小或者特别大的整数 N

得到 p,q 后正常RSA解密就能得到 m，然后题目中对 m进行了异或，再次进行异或就能得到 flag了

assert 114514 ** x % p == 1

m = m ^ (x**2)

这里考的是费马小定理，$a^{p-1}\equiv 1modp，\mathrm{推}\mathrm{导}\mathrm{公}\mathrm{式}{a}^p\equiv amodp$

EXP :

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

e = 65537
n = 141321067325716426375483506915224930097246865960474155069040176356860707435540270911081589751471783519639996589589495877214497196498978453005154272785048418715013714419926299248566038773669282170912502161620702945933984680880287757862837880474184004082619880793733517191297469980246315623924571332042031367393
c = 81368762831358980348757303940178994718818656679774450300533215016117959412236853310026456227434535301960147956843664862777300751319650636299943068620007067063945453310992828498083556205352025638600643137849563080996797888503027153527315524658003251767187427382796451974118362546507788854349086917112114926883
# yafu
p = 11887853772894265642834649929578157180848240939084164222334476057487485972806971092902627112665734648016476153593841839977704512156756634066593725142934001
q = 11887853772894265642834649929578157180848240939084164222334476057487485972806971092902627112665734646483980612727952939084061619889139517526028673988305393
if p<q:
    p,q = q,p

d = invert(e,(q-1)*(p-1))
m = pow(c,d,n)

# 费马小定理
x = p-1
assert 114514 ** x % p == 1

m = m ^ (x**2)
print(long_to_bytes(m))

中间分解 N 的过程用费马分解算法

费马分解算法 Fermat_factor

def fermat_factor(N):
    x = iroot(N,2)[0]
    if x*x < N:
        x+=1
    while(True):
        y2 = x*x-N
        y = iroot(y2,2)[0]
        if y*y == y2:
            break
        x += 1
    return(x+y,x-y)

p,q = fermat_factor(n)
print(p)
print(q)

模N不互素（多组公钥，其中的模数共用了素因子）

用 gcd() 函数实现

例题实现 ：[2022羊城杯] EasyRsa

from flag import flag
from Crypto.Util.number import *

m = bytes_to_long(flag)
e = 65537
f = open("output.txt", "r")
a = f.readlines()
for i in a:
    n = int(i)
    c = pow(m, e, n)
    m = c
print 'c = %s' % (m)
f.close()

'''
c = 38127524839835864306737280818907796566475979451567460500065967565655632622992572530918601432256137666695102199970580936307755091109351218835095309766358063857260088937006810056236871014903809290530667071255731805071115169201705265663551734892827553733293929057918850738362888383312352624299108382366714432727
'''

output.txt

65439077968397540989065489337415940784529269429684649365065378651353483030304843439003949649543376311871845618819107350646437252980144978447924976470943930075812834237368425374578215977641265884859875440799334807607478705932175148673160353577875890074101393042506714001617338265284910381849259298772642190619
86843235426823545017422014398916780909062053456790256392304973548517489132984667679637386416948409930796162377844525829968317585749956057149930523547463230147376192820753802868362225137830225967953826475779047454555958271846035526319036389127587352017149417549187850782892924691511398536178090031958365483499
57839320383142814687522363258949714784622321678585619281948174372461045134361003939684803510572969567182690634502610963365500727981041136988638273942465134797850643121827808482673619534240872593224537996099454035648829692386918230535360101064254854063175494150147494342652670585674593236663514793256521719547
52668168898129361356420333177679019946307853075463961068071790653159090226904625885080236174231665178538405547828768043706515464922611051221394704678558922339886480247663138702481349098077291584992082414494275463670330534613607852999291645500391111597009868188974671249118213040057429113174377610094956993269
79875848044631194160351918105738804229446748736206976033243436373010695259945613104837645712048695514204494137005015770637421510392760763371639480133851920449252506525423837434811693638210458851990502785655738042348115385964604080872180121543147063180945532713593712726527002909054818485584237993215139630243
73100501797447180147684637554796375398455002202770022931512541062214916136294604754404667725341796896161398464327153718845280194035978972665664657052946003418121755545770123205426883869361411412259838522099085901563107814985172942977520233320215882707710717870398128412272218474014381169303848087621856187879
89149546555397759430343098936690138982544367561661914051499112345535238108800665531588376806546499374457634397161670140520060064963391826220177798442707381640723248034061313974522233415815795656570220902974484865176728535660627712374835329967608728216749734529761431592345816592875807318876347151421393671763
66449107450661172442868032153863675098235855689218695279414435182923510356012957155941548483160873271040452368644926703812707864779900715051152673705082002761445847561495295455460041902473282731259268870375921215589157288622757488879539441498396276257589120302991242300378364101246448094955634459779361686643
79694880331320743031437708811856697413105291652061062223857313580221562305807771003185061831752133665835648647560103986928466217390444724672894866216636981793418219455653595717274553950715056120806463449033181486699963584346517910081706586345546292894426402568226579894766693070066214488743160957135286739213
70521001788476157145543175674209083194325853388116385624440232036679708917857095748070597575068955423165296665429648694541353249787337464272095260410717659726012806836884799476995758902361678737968193674368688353935424186389207123637734230550266810766585903134004322848985320790788169777840924595645463787189
51801430118171456966246071852561156183140136541960623661080056673664466785669585092926482194691254461430866302262960624015915371927788809661387318097968209364907625599562339722700041444342116899266802018340155635959614677597708758012024981583143521259152639480003228924151971208695043251548758407218187895663
87310111118839703578797261862424304499548882114635944516216618095145194843718635007052242072452831460162126955481326379219639313067967998826898344673513019946299427614605216960081461930080199023399060417820769438661351988322185620598552697590115678078498754112860310272842870106790357443602405008865116282919

EXP:

用 factorDB 和 Yafu 分解都无效，所以尝试 gcd()求最大公约数

from gmpy2 import *
from Crypto.Util.number import *
n_list = list(map(int, open('output.txt').read().splitlines()))
# 最大公约数p
p = 7552850543392291177573335134779451826968284497191536051874894984844023350777357739533061306212635723884437778881981836095720474943879388731913801454095897
c = 38127524839835864306737280818907796566475979451567460500065967565655632622992572530918601432256137666695102199970580936307755091109351218835095309766358063857260088937006810056236871014903809290530667071255731805071115169201705265663551734892827553733293929057918850738362888383312352624299108382366714432727

# for i in range(len(n_list)):
    # assert gcd(n_list[i],n_list[i+1]) == p
    # print('ok')

for n in n_list[::-1]:
    q = n//p
    d = invert(e,(q-1)*(p-1))
    m = pow(c,d,n)
    c = m
print(long_to_bytes(m))

威尔逊定理

若 p 为素数，则：$(p-1)!\equiv -1modp\Rightarrow$ 推导：$(p-2)!\equiv 1modp$

例题：[2022鹏城杯] babyrsa

from Crypto.Util.number import *
from libnum import s2n
from secret import flag
p = getPrime(1024)
q = getPrime(16)
n = p*q
m = s2n(flag)
for i in range(1,p-q):
    m = m*i%n
e = 1049
print(pow(2,e,n))
print(pow(m,e,n))
#4513855932190587780512692251070948513905472536079140708186519998265613363916408288602023081671609336332823271976169443708346965729874135535872958782973382975364993581165018591335971709648749814573285241290480406050308656233944927823668976933579733318618949138978777831374262042028072274386196484449175052332019377
#3303523331971096467930886326777599963627226774247658707743111351666869650815726173155008595010291772118253071226982001526457616278548388482820628617705073304972902604395335278436888382882457685710065067829657299760804647364231959804889954665450340608878490911738748836150745677968305248021749608323124958372559270

分两步解决：

先求出 n ，因为 p,q值相差很大，计算 pow(2,1049)得到 1050bit，大于 bit_length(n) = 1040bit

所以有：c1 = 2^1049 + K*n

再用在线分解 kn 得到 p,q 的值

第二步，利用威尔逊定理

EXP:

from Crypto.Util.number import *
from libnum import *
from gmpy2 import *
e = 1049
c1 = 4513855932190587780512692251070948513905472536079140708186519998265613363916408288602023081671609336332823271976169443708346965729874135535872958782973382975364993581165018591335971709648749814573285241290480406050308656233944927823668976933579733318618949138978777831374262042028072274386196484449175052332019377
c2 = 3303523331971096467930886326777599963627226774247658707743111351666869650815726173155008595010291772118253071226982001526457616278548388482820628617705073304972902604395335278436888382882457685710065067829657299760804647364231959804889954665450340608878490911738748836150745677968305248021749608323124958372559270
kn = pow(2,e) - c1
# print(kn)

p = 170229264879724117919007372149468684565431232721075153274808454126426741324966131188484635914814926870341378228417496808202497615585946352638507704855332363766887139815236730403246238633855524068161116748612090155595549964229654262432946553891601975628848891407847198187453488358420350203927771308228162321231
q = 34211
n = p*q
assert pow(2,e,n) == c1
k = 9 * 5 * 23

d = invert(e,(q-1)*(p-1))
M = pow(c2,d,p*q)
# print(M)

# 威尔逊定理
for i in range(p-q,p-1):
    M = M * i % n
m = (M % p)
print(long_to_bytes(m))

下面是一个学习威尔逊计算过程的 Demo，自己尝试一下，为什么取-1的时候，应该这样写

m1 = （-m） % p

p=17
q = 3
n = p*q
m = 4
for i in range(1,p-q):
    # m = m*i%n
    m = m*i
print(m)

for i in range(p-q,p-1):
    # m = m * i % n
    m = m * i
# m1 = m % p
m1 = (m % p)%n
print(m1)

利用公约数求解

一般方法就是当无法分解 N 的时候，通过观察已知条件的数学关系，判断是否存在公约数 p 或者 q，计算出p或者q的值，进而得到私钥d。

例题：

def encrypt3(m):
    p = getPrime(1024)
    q = getPrime(1024)
    n = p * q
    e = 65537
    M = 2022 * m * 1011 * p
    c = pow(M, e, n)
    print({'c': format(c, 'x'), 'n': format(n, 'x'),'e':format(e, 'x')})
    
# {'c': '1bd2a47a5d275ba6356e1e2bd10d6c870693be540e9318c746e807a7672f3a75cc63841170126d7dba52d7f6f9cf0f8dce9705fc1785cc670b2658b05d4b24d8918f95594844bfa920c8ffe73160c2c313b3fdbc4541ec19828165e34afa7d05271cc6fd59d08138b88c11677e6ac3b39cff525dcb19694b0388d895f53805a5e5bd8cfb947080e4855aaf83ebd85a397526f7d76d26031386900cb44a2e4bd121412bcee7a6c1e9af411e234f130e68a428596265d3ec647e50f65cb81393f4bd38389a2b9010fd715582506b9054dc235aced50757462b77a5606f116853af0c1ea3c7cf0d304f885d86081f8bac8b67b0625122f75448c5b6eb8f1cc8a0df', 'n': 'c2b17c86a8950f6dafe0a633890e4271cfb20c5ffda2d6b3d035afa655ed05ec16c67b18832ed887f2cea83056af079cc75c2ce43c90cce3ed02c2e07d256f240344f1734adeee6dc2b3b4bbf6dcfc68518d0a74e3e66f1865db95ef4204457e6471903c2321ac97f3b8e3d8d935896e9fc9145a30a3e24e7c320490a9944c1e94d301c8388445532699e6189f4aa6a86f67f1d9b8fb0de4225e005bd27594cd33e36622b2cd8eb2781f0c24d33267d9f29309158942b681aab81f39d1b4a73bd17431b46a89a0e4c2c58b1e24e850355c63b72392600d3fff7a16f6ef80ea515709da3ef1d28782882b0dd2f76bf609590db31979c5d1fd03f75d9d8f1c5069', 'e': '10001'}

这里需要求解的明文是 m ，已知量为 c，n，e ;

$c\equiv M^{e}modn\Rightarrow c=M^e+k\ast p\ast q$ ，M = 2022 * m * 1011 * p

所以，$c=(2022\ast m\ast 1011\ast p{)}^e+k\ast p\ast q\Rightarrow c=[(2022\ast m\ast 1011{)}^e\ast p^{e-1}+k\ast q]\ast p$

所以 p = gcd(c, n)

dp泄露

理论参考：

https://cn1nja.github.io/posts/rsa%E5%B8%B8%E8%A7%81%E6%94%BB%E5%87%BB/#font-coloref6c00dp-%E6%B3%84%E9%9C%B2font

例题：

m = hint
p = getPrime(512)
q = getPrime(512)
n = p * q
e = 65537
phi = (p-1)*(q-1)
dp = gp.invert(e, p-1)
c = pow(m, e, n)
#n =  85413323752199019806030766630760449394238054889872415531186815348349883843039718091361611175963675771467536496812507338620957273406076058263122453235926619595761737396698699834116678598534261542535530241537247151318756003375573850725841254167462648747492270335084402716816450008370008491069875351593380154253
#dp =  1576424214336939000475035870826282526256046059505538052583882122452307602095912733650442447289122473348318614749578285418144935611098423641334952097553125
#c =  53653254613997095145108444611576166902006080900281661447007750088487109015427510365774527924664116641019490904245926171500894236952984157500461367769566121581870986304353174732328118576440353500038670030097108081972287049673200783198844842527470746431369314585103203118824985764754487936404004696485346196488

EXP:

from gmpy2 import *
from libnum import *

e = 65537
n =  85413323752199019806030766630760449394238054889872415531186815348349883843039718091361611175963675771467536496812507338620957273406076058263122453235926619595761737396698699834116678598534261542535530241537247151318756003375573850725841254167462648747492270335084402716816450008370008491069875351593380154253
dp =  1576424214336939000475035870826282526256046059505538052583882122452307602095912733650442447289122473348318614749578285418144935611098423641334952097553125
c =  53653254613997095145108444611576166902006080900281661447007750088487109015427510365774527924664116641019490904245926171500894236952984157500461367769566121581870986304353174732328118576440353500038670030097108081972287049673200783198844842527470746431369314585103203118824985764754487936404004696485346196488

for i in range(1,e):                   #在范围(1,e)之间进行遍历
    if(dp*e-1)%i == 0:
        if n%(((dp*e-1)//i)+1) == 0:   #存在p，使得n能被p整除
            p=((dp*e-1)//i)+1
            q=n//(((dp*e-1)//i)+1)
            phi=(q-1)*(p-1)            #欧拉定理
            d=invert(e,phi)         #求模逆
            m=pow(c,d,n)               #快速求幂取模运算
            print(n2s(m))

Common Prime RSA (公共素数RSA)

Common Prime RSA 是RSA的一种变体，其中首先是定义一个大素数 g ，使 p，q 满足:

$p=2ga+1，q=2gb+1$ ，且 $gcd(a,b)=1$

相关论文：

Paper1

Paper2

论文讲的东西看不懂，主要就是使用第一篇Paper中 这个 Jochemsz-May Attack 算法进行攻击，就能成功分解N

image.png

这里是第二篇 Paper 的内容

image.png

已知 g，d 的比特值大小

例题： [祥云杯 2022] common_RSA 以及 [Unknown] common_prime_rsa

from Crypto.Util.number import getPrime, isPrime, bytes_to_long, inverse
from gmpy2 import lcm
from secret import flag

def gen(g):
    bits = 512 - g.bit_length()
    while True:
        a = getPrime(bits)
        p = 2 * a * g + 1
        if isPrime(p):
            return p

flag = bytes_to_long(flag)
g = getPrime(320)
p = gen(g)
q = gen(g)
n = p * q

d = getPrime(135)
phi = lcm(p - 1, q - 1)
e = inverse(d, phi)
c = pow(flag, e, n)

print("n = {}".format(n))
print("e = {}".format(e))
print("c = {}".format(c))


# n = 226165344948523695550317829045043301755038098520452624660349292451995383453438289393781798353852345351793447259067034277175312000439714746707076461950784526936960213165522383440080690205136204470885632591338647238110900688476644840652840550811475271011865045295673906950241527927296639555904136659503883578477
# e = 5567244806132990650525283298184362097543657183189728255568114179202725826111751535660207402892872159118913249819234722178944445439968738188714785145503922061686027757846021298576445706913642685977037770387737999
# c = 57682158710465983171562026269739297396728817506153693021896820074106872415768816411139367981754433123318218398135998490673098044266600075040944872524869723199130235787419190583390252662209383842910402954721426214605921626460687965255321698030504911332211630203201003008746669994467884389565443089663096988198

2017 的 PlaidCTF 也有一样的题，下面的脚本来自这题对应的exp， github链接

EXP：

#sagemath
from libnum import n2s


n = 226165344948523695550317829045043301755038098520452624660349292451995383453438289393781798353852345351793447259067034277175312000439714746707076461950784526936960213165522383440080690205136204470885632591338647238110900688476644840652840550811475271011865045295673906950241527927296639555904136659503883578477
e = 5567244806132990650525283298184362097543657183189728255568114179202725826111751535660207402892872159118913249819234722178944445439968738188714785145503922061686027757846021298576445706913642685977037770387737999
c = 57682158710465983171562026269739297396728817506153693021896820074106872415768816411139367981754433123318218398135998490673098044266600075040944872524869723199130235787419190583390252662209383842910402954721426214605921626460687965255321698030504911332211630203201003008746669994467884389565443089663096988198

gamma = 320/1024
delta = 135/1024
m = 2
tau = (1 / 2 + gamma - 4 * delta) / (2 * delta)
t = ZZ(floor(tau * m))

X = ZZ(floor(n ^ delta))
Y = ZZ(floor(n ^ (delta + 1 / 2 - gamma)))
Z = ZZ(floor(n ^ (delta + 1 / 2 - gamma)))
W = ZZ(floor(n ^ (2 + 2 * delta - 2 * gamma)))
R = W * X ^ (2 * (m - 1) + t) * (Y * Z) ^ (m - 1)

# assert X ^ (7 + 9 * tau + 3 * tau ^ 2) * (Y * Z) ^ (5 + 9 * tau / 2) < W ^ (3 + 3 * tau)

P = PolynomialRing(ZZ, 'x,y,z')
x,y,z = P.gens()

# we know that ed = k(2gab) + 1 = k(p - 1)b + 1 = ka(q - 1) + 1
# we can multiply the last two expressions to get a semi-symmetric equation for
# (ed)^2, of which we want to find its roots
f = e^2 * x^2 + e * x * (y + z - 2) - (n - 1) * y * z - (y + z - 1)
assert f.constant_coefficient() == 1

M = set()
S = set()
# generate monomials
# S contains monomials of f^{m - 1} with x-shifts
# M contains monomials of f^{m} with x-shifts \setminus S
for i3 in range(0, m):
    for i2 in range(0, m):
        for i1 in range(0, 2 * (m - 1) - (i2 + i3) + t + 1):
            S.add(x ^ i1 * y ^ i2 * z ^ i3)
for i3 in range(0, m + 1):
    for i2 in range(0, m + 1):
        for i1 in range(0, 2 * m - (i2 + i3) + t + 1):
            M.add(x ^ i1 * y ^ i2 * z ^ i3)
M_S = M - S
M_S = sorted(M_S)
S   = sorted(S)
M   = sorted(M)

# use a dict to map each shift polynomial with its lowest order monomial to
# make diagonalizing the basis matrix easier
g   = {}

# generate shift polynomials
# the shift polynomials are generated with a polynomial derived from f (mod R)
# namely ff = a0^{-1} * f (mod R) such that the constant term of ff is 1
# i am fairly certain any polynomial with constant term 1 and the correct roots
# can be used here, although i have only tested it with ff and f
ff = f.change_ring(Zmod(R)).change_ring(ZZ)
for mono in S:
    i1, i2, i3 = mono.degree(x), mono.degree(y), mono.degree(z)
    fn = mono * ff(x, y, z) * X ^ (2 * (m - 1) + t - i1) * Y ^ (m - 1 - i2) * Z ^ (m - 1 - i3)
    fn = expand(fn(x * X, y * Y, z * Z))
    g[mono] = fn
for mono in M_S:
    fn = R * mono
    fn = expand(fn(x * X, y * Y, z * Z))
    g[mono] = fn

npolys = len(g)
nmonos = len(M)
print("polynomials: {}".format(npolys))
print("monomials:   {}".format(nmonos))
assert npolys == nmonos

B = Matrix(ZZ, npolys, nmonos)
C = Matrix(ZZ, npolys, nmonos)

for row, mono in enumerate(M):
    i1, i2, i3 = mono.degree(x), mono.degree(y), mono.degree(z)
    for c, mono_ in g[mono]:
        col = M.index(mono_)
        C[row, col] = 1
        B[row, col] = c

    # assert that diagonal elements are what they should be
    idx = M.index(mono)
    if mono in S:
        assert B[idx, idx] == X ^ (2 * (m - 1) + t) * (Y * Z) ^ (m - 1)
    elif mono in M_S:
        assert B[idx, idx] == R * X ^ i1 * Y ^ i2 * Z ^ i3
    else:
        raise Exception("what")

# print(C.str())

# assert triangular form
for col in range(nmonos):
    for row in range(col + 1, npolys):
    # for row in xrange(col):
        assert B[row, col] == 0
    assert B[col, col] != 0

print("LLL...")
BB = B.LLL(algorithm='fpLLL:proved', fp='rr')
CC = Matrix(ZZ, npolys, nmonos)
for row in range(npolys):
    for col in range(nmonos):
        if BB[row, col] != 0:
            CC[row, col] = 1
# print(CC.str())

# helper to construct a polynomial from coefficients
def topoly(r):
    RR = PolynomialRing(QQ, 'x,y,z')
    pol = 0
    for col in range(nmonos):
        pol += r[col] * M[col]
    pol = RR(pol(x / X, y / Y, z / Z))
    for c, _ in pol:
        assert c.is_integer()
    return P(pol)

# pull out h1, h2
hv = [expand(topoly(r)) for r in BB]
h1, h2 = hv[0:2]

# at some point we need to polynomial engines to something that can solve for
# roots, the default univariate engine works
s, = PolynomialRing(ZZ, 's').gens()

# these should be algebraically independent
assert h1.gcd(f).degree() == 0
assert h2.gcd(f).degree() == 0
assert h1.gcd(h2).degree() == 0

# take care that resultants are computed with f and not ff, which is a
# polynomial mod R
# these resultants eliminate z
h1x = h1.resultant(f, z)
h2x = h2.resultant(f, z)
hh  = h1.resultant(h2, z)

# this eliminates y
hy = h1x.resultant(h2x, y)

# now we can solve for roots via back substitution
d = []
for r, m in hy(x=s).roots():
    if r == 0:
        continue
    d.append(r)
assert len(d) == 1
d = d[0]

ka = []
for r, m in hh(x=d, y=s).roots():
    if r == 0:
        continue
    ka.append(r)
# f(x, y, z) = f(x, z, y) so we should have two solutions here
assert len(ka) == 2
ka = ka[0]

kb = []
for r, m in f(x=d, y=ka, z=s).roots():
    if r == 0:
        continue
    kb.append(r)
assert len(kb) == 1
kb = kb[0]

print("found d  = {}".format(d))
print("found ka = {}".format(ka))
print("found kb = {}".format(kb))

k = gcd(ka, kb)
a = ka // k
b = kb // k
g = (e * d - 1) // (2 * k * a * b)
p = 2 * g * a + 1
q = 2 * g * b + 1
 
n = 226165344948523695550317829045043301755038098520452624660349292451995383453438289393781798353852345351793447259067034277175312000439714746707076461950784526936960213165522383440080690205136204470885632591338647238110900688476644840652840550811475271011865045295673906950241527927296639555904136659503883578477
e = 5567244806132990650525283298184362097543657183189728255568114179202725826111751535660207402892872159118913249819234722178944445439968738188714785145503922061686027757846021298576445706913642685977037770387737999
c = 57682158710465983171562026269739297396728817506153693021896820074106872415768816411139367981754433123318218398135998490673098044266600075040944872524869723199130235787419190583390252662209383842910402954721426214605921626460687965255321698030504911332211630203201003008746669994467884389565443089663096988198

print(n2s(int(pow(c,d,n))))

已知参数 a， b 的值

例题：

from Crypto.Util.number import *
import gmpy2

FLAG = b'DASCTF{xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx}'

def gen_prime(nbits, gamma):
    global g, a, b
    g = getPrime(int(nbits * gamma))
    alpha = 0.5 - gamma
    while True:
        a = getRandomNBitInteger(int(alpha * nbits))
        p = 2 * g * a + 1
        if isPrime(p):
            b = getRandomNBitInteger(int(alpha * nbits))
            q = 2 * g * b + 1
            h = 2 * g * a * b + a + b
            while not isPrime(q) or isPrime(h) or gmpy2.gcd(a, b) != 1:
                b = getRandomNBitInteger(int(alpha * nbits))
                q = 2 * g * b + 1
            return p, q

def encrypt(nbits, gamma):
    p, q = gen_prime(nbits, gamma)
    n = p * q
    e = getPrime(16)
    while gmpy2.gcd(e, gmpy2.lcm(p-1,q-1)) != 1:
        e = getPrime(16)
    m = bytes_to_long(FLAG)
    c = pow(m, e, n)
    return n, e, c

n, e, c = encrypt(1024, 0.3)
print('n =', n)
print('e =', e)
print('c =', c)
print('a =', a)
print('b =', b)

# n = 66653979485804283352149461881880166787411331235368147630654293448332690656918078092092379134534311839509692935334583374088069879927465573728557493141897930747827809534703034943242300076132786813762424274468672787928324412657839164661989103228058195799751623912510565903915115255907753401534854679952421734721
# e = 33287
# c = 27705551212041312253885915523456436420281849369875307842183789238070482317396815044209118835285962981364912778262511808272047695427214205559426607869346742801785301455096346097004914288224515869504777953792142991577273831153954758430491702159238818936997698447229078777460549085526762086620581405869943141566
# a = 15732977419470204953507967358788028494859190922257412640596477
# b = 24850402768907372800226308145085094710759377708291492991352981

分析： 已知量 N , e, c, a, b

已知 $p=2\ast g\ast a+1，q=2\ast g\ast b+1，N=p\ast q$

即：$N=(2ga+1)\ast (2gb+1)=4g^{2}ab+2g(a+b)+1$

现在构造为一元模多项式，然后用sage求未知量 g 的根值即可

$f=4g^{2}ab+2g(a+b)+1modN$

EXP:

from Crypto.Util.number import *
from sage.all import PolynomialRing
from gmpy2 import *

n = 66653979485804283352149461881880166787411331235368147630654293448332690656918078092092379134534311839509692935334583374088069879927465573728557493141897930747827809534703034943242300076132786813762424274468672787928324412657839164661989103228058195799751623912510565903915115255907753401534854679952421734721
e = 33287
c = 27705551212041312253885915523456436420281849369875307842183789238070482317396815044209118835285962981364912778262511808272047695427214205559426607869346742801785301455096346097004914288224515869504777953792142991577273831153954758430491702159238818936997698447229078777460549085526762086620581405869943141566
a = 15732977419470204953507967358788028494859190922257412640596477
b = 24850402768907372800226308145085094710759377708291492991352981

PR.<g> = PolynomialRing(Zmod(n))
f = 4*g^2*a*b+2*g*(a+b)+1

f = f.monic()
g_root = f.small_roots(X=2^308,beta=0.4)
print(g_root)

g = int(g_root[0])
p = 2 * g * a + 1 
q = 2 * g * b + 1
phi = (q-1)*(p-1)
d = invert(e,phi)
m = pow(c,d,n)
print(long_to_bytes(int(m)))

DASCTF{110484ec9f77c1e937d288206b027d85}

已知参数 a 的值

例题：[2023 天一永安杯] rsa

from Crypto.Util.number import *
from math import gcd
from secret import flag

def gen_key(nbits, gamma):
    g = getPrime(int(nbits * gamma))
    alpha = 0.5 - gamma
    while True:
        a = getPrime(int(alpha * nbits))
        p = 2 * g * a + 1
        if isPrime(p):
            break
    while True:
        b = getRandomNBitInteger(int(alpha * nbits))
        q = 2 * g * b + 1
        h = 2 * g * a * b + a + b
        if isPrime(q) and isPrime(h) and gcd(a, b) == 1:
            return p*q,a,g
        else:
            continue
        
n,a,g = gen_key(1024, 0.05)
e = 65537
c = pow(bytes_to_long(flag),e,a*g)
print(n,c,a)

'''
n=36535558847082719901201561031181835346574576610950713924924272947759193576365817762980927638691696601293089537315055413746788190208875234794229119049056299551864869870291634941246362436491006904347559559494705922259007299126640817275929491680601926404543198957206717290905220235571289759182878331893962038379
c=532997872940452282189043430008002793694788439822465302532208754231005799057972378308576109082463996551992533174546386979606697890310597738637156771564229
a=2694858406312563434474553988904403597551484373358339092528913028454100111881368126493990657117571672510331411186745639563619323775673115439
'''

题目分析：

方法一：构造模多项式求根

由已知条件：$p=2\ast g\ast a+1$ ，已知 a，n，c 的值， g、p 未知，n = p*q

g = 1024*0.05 近似等于51 ，a 的比特值为 460 比特

相当于已知p的高位，求解p的低位数据，用coppersmith即可恢复出完整的p值

方法二：找关系分解N值

因为 $h=2gab+a+b$

$p=2\ast g\ast a+1，q=2\ast g\ast b+1，N=p\ast q$

$N=(2ga+1)\ast (2gb+1)=4g^{2}ab+2g(a+b)+1$

则：$(N-1)//2=g(2gab+a+b)=gh$

又因为 g ,h 都为素数，且 g 为51 bit，h肯定大于460 bit，两数值相差很大，所以可以尝试用yafu分解 (N-1)//2

得到：

g = 1346104232461691
h = 13570850594633462506426369052182298554140635599543685835372377476383038708650421475723391142118956001358520246769650699398490037618758005241062608387057439283872260149565854577827352267289963736282502923131251179400580891491236925451166755184695335564693793568286112036468975877609637392241679

EXP1:

from Crypto.Util.number import *
from sage.all import PolynomialRing
from gmpy2 import *

n=36535558847082719901201561031181835346574576610950713924924272947759193576365817762980927638691696601293089537315055413746788190208875234794229119049056299551864869870291634941246362436491006904347559559494705922259007299126640817275929491680601926404543198957206717290905220235571289759182878331893962038379
c=532997872940452282189043430008002793694788439822465302532208754231005799057972378308576109082463996551992533174546386979606697890310597738637156771564229
a=2694858406312563434474553988904403597551484373358339092528913028454100111881368126493990657117571672510331411186745639563619323775673115439
e = 65537

PR.<g> = PolynomialRing(Zmod(n))
f = 2*a*g + 1

f = f.monic()
g_root = f.small_roots(X=2^52,beta=0.4)
print(g_root)
print(bit_length(int(g_root[0])))

g = int(g_root[0])
phi = (g-1)*(a-1)
d = invert(e,phi)
m = pow(c,d,a*g)
print(long_to_bytes(int(m)))

flag{p01la4d_rHo_a1gOr1thM_r1gh4}

整数分解工具 primefac

提示

介绍链接：https://pypi.org/project/primefac/

这是一个用于分解整数的模块和命令行实用程序。作为一个模块，我们提供了一个素数测试，几个用于提取整数的非平凡因子的函数，一个产生所有数字的素因子（具有多重性）的生成器，以及用于计算这些东西的辅助函数。作为命令行实用程序，该项目旨在用更通用的实用程序取代 GNU 的factor命令——特别是，该实用程序可以对任意大的数字进行操作，并行使用多个内核，使用更好的算法，以逆波兰表示法处理输入，并且可以通过命令行标志进行调整。具体来说，

• GNU 的factor命令不会因式分解任何大于 2 127 -1 的值。primefac 处理任意大的整数。
• GNU 的factor命令使用 Pollard 的 rho 算法。虽然这可以快速提取小因素，但需要一段时间才能找到大因素。primefac 使用了椭圆曲线方法和自初始化二次筛等方法，它们在提取大因子方面效率更高。
• GNU 的factor命令是一个单线程应用程序。primefac 默认使用五个线程来利用现代机器上通常可用的多核。这些线程中的每一个都使用不同的算法来分解数字：
  • 一个线程运行 Brent 对 Pollard 的 rho 算法的变体。这有利于快速提取较小的因子。
  • 一个线程运行 Pollard 的p -1 方法的两阶段版本。这很擅长寻找因子p，其中p -1 是小素数的乘积。
  • 一个线程运行 Williams 的p +1 方法。这很擅长寻找因子p，其中p +1 是小素数的乘积。
  • 一个线程运行椭圆曲线方法。当提取的因子较小时，这比 Pollard 的 rho 算法慢一点，但它在困难因子上有明显更好的性能。
  • 一个线程运行自初始化二次筛。这是分解“硬”数而不是一般数域筛的最佳算法。然而，当数字较小时，它（相对而言）会慢一点，而且它花费的时间仅取决于被分解的数字的大小，而不是像 Pollard 的 rho 算法和椭圆算法那样被提取的因子的大小曲线方法，所以我们使用前面的算法来处理这些。

命令行用法

python3 -m primefac [-vs|-sv] [-v|--verbose] [-s|--summary|--summarize] [-t=NUMBER]
                    [-r=NUMBER] [-m=[prb][,p-1][,p+1][,ecm][,siqs]] rpn

rpn 是一个反波兰表示法的表达式，使用整数算术计算。然后将评估后保留在堆栈中的每个数字分解。

-t 设置试验划分限制；默认值为 1000。使用-t=inf以专门使用试验除法。

-r 设置 Pollard 的 rho 算法在称一个因素为“困难”之前要尝试的轮数。默认值为 42,000。使用-r=inf以在试验除法完成后专门使用 Pollard 的 rho。

如果调用详细信息，那么我们会提供进度报告，并说明在多因素阶段哪些算法产生了哪些因素。

如果不存在摘要和冗长标志，则输出应与 GNU factor 命令的输出相同，即因子的模排列。如果调用详细标志，那么我们会提供进度报告，打开摘要标志，并说明在多因素阶段哪些方法产生了哪些因素。

-v 和 -s 标志可以按任意顺序组合成一个标志——即组合成 -vs 或 -sv。

-m 标志控制多因素阶段使用的函数。选项为 prb、p-1、p+1、ecm 和 siqs，分别代表 Pollard 的 rho、Pollard 的p -1、Williams 的p +1、椭圆曲线法和自初始化二次筛法。选项必须用逗号分隔。选项可以重复：例如，如果prb被列出两次，那么multifactor将同时运行pollardrho_brent的两个实例。在prb和ecm的情况下，这会降低查找因子所需时间的期望值，而其他三种算法（p -1、p +1 和 MPQS）没有随机成分，因此运行这三种算法的重复实例不会带来任何好处。因此，我们忽略后三种方法的重复列表：例如，调用

python3 -m primefac -m=prb,prb,ecm,ecm,ecm,mpqs,mpqs 38 ! 1 +

将在多因素阶段运行 Pollard 的 rho 的两个实例、椭圆曲线方法的三个实例和 MQPS 的一个实例。调用比可用内核更多的方法不太可能带来任何好处。

光滑数

Pollard’s p - 1算法（p-1光滑）

• 光滑数(Smoooth number)：指可以因数分解为小质数乘积的正整数。

• 当 p 是 N 的因数，且 p-1 为光滑数时，可以考虑使用 Pollard’s p - 1算法来分解 N

B-Smooth number定义：

若一正整数的质因数均不大于B，此整数即为B-光滑数。例如1620的因数分解为 $2^2\times 3^4\times 5$，质因数均不大于5，因此1620是5-光滑数。 10和12的因数分解分别为2 × 5和$2^2\times 3$，二者质因数也都不大于5，因此二者均是是5-光滑数，虽然其质因数未包括小于 5 的所有质数，但仍然可以是5-光滑数。

Pollard’s p − 1 算法：

是一种整数分解算法，由John Pollard于 1974 年发明。

由费马小定理：If $gcd(a,p)=1$，$a^{p-1}\equiv 1modp$

则有：$a^{K\ast (p-1)}\equiv 1modp，K\mathrm{为}\mathrm{正}\mathrm{整}\mathrm{数}$

算法实现：

**输入：**整数N（为合数）

**输出：**N或者失败的因子

1、选择平滑边界 B

2、定义 $M=\prod _{primesq\le B}{q}^{[lo{g}_{q}B]}$

3、随机选择一个和 n 互质的数（注意：我们实际上可以固定 a，例如，如果n是奇数，那么我们总是可以选择 a=2，这里的随机选择不是必须的）

4、计算 $g=gcd(a^M-1,n)$，（其中 M 能被 p-1 整除）（注意：求幂可以进行模 n）

5、如果 $1<g<n$ 则返回 g

6、如果 $g=1$ 则选择更大的B并转到步骤 2 或返回失败

7、如果 $g=n$ 则选择较小的B并转到步骤 2 或返回失败

因为我们只关心最后的 gcd 结果，同时 N 只包含两个素因子，则我们不需要计算 M，考虑 n=2,3,…，令 M = n! 即可覆盖正确的 M 同时方便计算 。

在具体计算中，可以代入降幂进行计算 ：$a^{n!}modN=(a^{(n-1)!}modN{)}^{n}modN，n\ge 3$

Example：

If we want to factor the number $n=299$.

1、We select B = 5

2、Thus M = 22 × 31 × 51.

3、We select a = 2.

4、$g=gcd(a^M-1,n)=13.$

5、Since 1 < 13 < 299, thus return 13.

6、299 / 13 = 23 is prime, thus it is fully factored: 299 = 13 × 23.

实现EXP：

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


# Pollard's p-1
def Pollard_p(N):
    a = 2
    n = 2
    while True:
        a = pow(a, n, N)
        g = gcd(a - 1, N)
        if g != 1 and g != N:
            p = g
            q = N // g
            print('p =', p)
            print('q =', p)
            print("n =",n)
            return p,q
        n += 1

e = 0x10001
N = 32849718197337581823002243717057659218502519004386996660885100592872201948834155543125924395614928962750579667346279456710633774501407292473006312537723894221717638059058796679686953564471994009285384798450493756900459225040360430847240975678450171551048783818642467506711424027848778367427338647282428667393241157151675410661015044633282064056800913282016363415202171926089293431012379261585078566301060173689328363696699811123592090204578098276704877408688525618732848817623879899628629300385790344366046641825507767709276622692835393219811283244303899850483748651722336996164724553364097066493953127153066970594638491950199605713033004684970381605908909693802373826516622872100822213645899846325022476318425889580091613323747640467299866189070780620292627043349618839126919699862580579994887507733838561768581933029077488033326056066378869170169389819542928899483936705521710423905128732013121538495096959944889076705471928490092476616709838980562233255542325528398956185421193665359897664110835645928646616337700617883946369110702443135980068553511927115723157704586595844927607636003501038871748639417378062348085980873502535098755568810971926925447913858894180171498580131088992227637341857123607600275137768132347158657063692388249513
c = 26308018356739853895382240109968894175166731283702927002165268998773708335216338997058314157717147131083296551313334042509806229853341488461087009955203854253313827608275460592785607739091992591431080342664081962030557042784864074533380701014585315663218783130162376176094773010478159362434331787279303302718098735574605469803801873109982473258207444342330633191849040553550708886593340770753064322410889048135425025715982196600650740987076486540674090923181664281515197679745907830107684777248532278645343716263686014941081417914622724906314960249945105011301731247324601620886782967217339340393853616450077105125391982689986178342417223392217085276465471102737594719932347242482670320801063191869471318313514407997326350065187904154229557706351355052446027159972546737213451422978211055778164578782156428466626894026103053360431281644645515155471301826844754338802352846095293421718249819728205538534652212984831283642472071669494851823123552827380737798609829706225744376667082534026874483482483127491533474306552210039386256062116345785870668331513725792053302188276682550672663353937781055621860101624242216671635824311412793495965628876036344731733142759495348248970313655381407241457118743532311394697763283681852908564387282605279108
p,q = Pollard_p(N)
d = invert(e,(q-1)*(p-1))
m = pow(c,d,N)
print(long_to_bytes(m))

采用 Primefac 工具中的Pollard p-1 算法分解N速度更快，执行命令：

python3 -m primefac -s -m=p-1 19872819125708160603084603242671651221458323254854801951930001621801221325473092408279659550333848286004026671335637562704497257686677778141999203867039868185825576833043603136145799288616508702194447326392478161893685557369421460874245216819654603274465749239798470288808373168802168209785408191322772427936272224569337024420589798911057135691495185720378719841160586054317741408208300873893461929130849929571632915326482122345207616119451295194119350358891391518996948731493939187461870424799697620828106283173949218685181570151652736639929180849462982438480124266270377324109582144381959453392024504336863997742369

例题：[NCTF 2019]childRSA

from random import choice
from Crypto.Util.number import isPrime, sieve_base as primes
from flag import flag


def getPrime(bits):
    while True:
        n = 2
        while n.bit_length() < bits:
            n *= choice(primes)
        if isPrime(n + 1):
            return n + 1

e = 0x10001
m = int.from_bytes(flag.encode(), 'big')
p, q = [getPrime(2048) for _ in range(2)]
n = p * q
c = pow(m, e, n)

# n = 32849718197337581823002243717057659218502519004386996660885100592872201948834155543125924395614928962750579667346279456710633774501407292473006312537723894221717638059058796679686953564471994009285384798450493756900459225040360430847240975678450171551048783818642467506711424027848778367427338647282428667393241157151675410661015044633282064056800913282016363415202171926089293431012379261585078566301060173689328363696699811123592090204578098276704877408688525618732848817623879899628629300385790344366046641825507767709276622692835393219811283244303899850483748651722336996164724553364097066493953127153066970594638491950199605713033004684970381605908909693802373826516622872100822213645899846325022476318425889580091613323747640467299866189070780620292627043349618839126919699862580579994887507733838561768581933029077488033326056066378869170169389819542928899483936705521710423905128732013121538495096959944889076705471928490092476616709838980562233255542325528398956185421193665359897664110835645928646616337700617883946369110702443135980068553511927115723157704586595844927607636003501038871748639417378062348085980873502535098755568810971926925447913858894180171498580131088992227637341857123607600275137768132347158657063692388249513
# c = 26308018356739853895382240109968894175166731283702927002165268998773708335216338997058314157717147131083296551313334042509806229853341488461087009955203854253313827608275460592785607739091992591431080342664081962030557042784864074533380701014585315663218783130162376176094773010478159362434331787279303302718098735574605469803801873109982473258207444342330633191849040553550708886593340770753064322410889048135425025715982196600650740987076486540674090923181664281515197679745907830107684777248532278645343716263686014941081417914622724906314960249945105011301731247324601620886782967217339340393853616450077105125391982689986178342417223392217085276465471102737594719932347242482670320801063191869471318313514407997326350065187904154229557706351355052446027159972546737213451422978211055778164578782156428466626894026103053360431281644645515155471301826844754338802352846095293421718249819728205538534652212984831283642472071669494851823123552827380737798609829706225744376667082534026874483482483127491533474306552210039386256062116345785870668331513725792053302188276682550672663353937781055621860101624242216671635824311412793495965628876036344731733142759495348248970313655381407241457118743532311394697763283681852908564387282605279108

根据题目可知素数 p、q ,由多个小素因子相乘之积然后加 1 得到。符合 p-1 光滑数的定义，所以用 Pollard's p-1 算法可以成功分解 N。

光滑数生成代码：

from Crypto.Util.number import *
from binascii import hexlify
from gmpy2 import *
import os
flag = b"flag{Congratulations_0n_Learn1ng_p0llard's_p-1_Alg0rithm}"

SEED = mpz(hexlify(os.urandom(32)).decode(), 16)
STATE = random_state(SEED)

def get_prime(state, bits):
    return next_prime(mpz_urandomb(state, bits) | (1 << (bits - 1)))

def get_smooth_prime(state, bits, smoothness=16):
    p = mpz(2)
    p_factors = [p]
    while p.bit_length() < bits - 2 * smoothness:
        factor = get_prime(state, smoothness)
        p_factors.append(factor)
        p *= factor

    bitcnt = (bits - p.bit_length()) // 2

    while True:
        prime1 = get_prime(state, bitcnt)
        prime2 = get_prime(state, bitcnt)
        tmpp = p * prime1 * prime2
        if tmpp.bit_length() < bits:
            bitcnt += 1
            continue
        if tmpp.bit_length() > bits:
            bitcnt -= 1
            continue
        if is_prime(tmpp + 1):
            p_factors.append(prime1)
            p_factors.append(prime2)
            p = tmpp + 1
            break

    p_factors.sort()

    return (p, p_factors)

e = 65537

while True:
    p, p_factors = get_smooth_prime(STATE, 1024, 16)
    if len(p_factors) != len(set(p_factors)):
        continue
    # Smoothness should be different or some might encounter issues.
    q, q_factors = get_smooth_prime(STATE, 1024, 17)
    if len(q_factors) != len(set(q_factors)):
        continue
    factors = p_factors + q_factors
    if e not in factors:
        break

N = p*q
print("p =",p)
print("q =",q)
print("N =",p*q)
m = bytes_to_long(flag)
c = pow(m,e,N)
print('c =',c)
print('e =',e)

Williams’s p + 1 算法（p+1光滑）

试除法（|p-q|过大）