RSA详解

本文最后更新于 2025年10月24日晚上

使用gmpy2而不是Crypto中的数学函数（gmpy2速度快，可直接pip安装，不支持低版本python）

提供`pqec`求m

from Crypto.Util.number import *

p = 10554915510546378513140074459658086644656654144905337809416976066414771647836950941616441505897207397834928781511863699153349798682451297889979721668885951
q = 8246403321715011123191410826902524505032643184038566851264109473851746507405534573077909160292816825514872584170252311902322051822644609979417178306809223
e = 65537
c = 40005881669517895877352756665523238535105922590962714344556374248977905431683140065629966778249773228248201807844489945346731806741025157651474530811920115794270396320935022110691338083709019538562205165553541077855422953438117902279834449006455379382431883650004540282758907332683496655914597029545677184720

n=p*q

# 计算欧拉函数φ(n) = (p-1)*(q-1)
phi = (p-1)*(q-1)

# 计算逆元d（私钥）
d = inverse(e, phi)
# d = gmpy2.invert(e,phi)也可以 大数优化？
# d = pow(e, -1, phi)也可以

# 解出明文
m = pow(c, d, n)

print(long_to_bytes(m))

RSA 解密过程是：
$计算$

$计算$

$计算私钥$

$解出明文$

将m转成 bytes 得到 flag

计算
计算
计算私钥
解出明文
将m转成 bytes 得到 flag

提供nec求m

解题代码：

from Crypto.Util.number import *
n = 7382582015733895208810490097582153009797420348201515356767397357174775587237553842395468027650317457503579404097373070312978350435795210286224491315941881
p = 70538125404512947763739093348083497980212021962975762144416432920656660487657
q = 104660876276442216612517835199819767034152013287345576481899196023866133215633
e = 65537
c = 6511001389892474870028836129813814173158254564777610289284056550272120510686249909340499673868720839756059423749304765055919251717618117507007046973023557

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

print(long_to_bytes(m))

pq相近类型

直接开平方

# pq相近类型
from Crypto.Util.number import *
from gmpy2 import *
p = getPrime(512)
q = gmpy2.next_prime(p)

n = 115637000420176820831322601039129424406844427046456738651883381559357542765613732363445112111006849040385859313572091386802534464534403117787314180179562651607533039692795522388596550968316951090748054495960090527479954143448774136390568881020918710834542819900918984139672802889774720153267841255456602500057
e = 65537
c = 98161406745910866780822530171878255235776133393411573803496865047700715941955255328757920065032397556905095591171977170479344602512244671081108703687450560269408412671849929423399172588599903975793985819498354819305128607934552101433664794909855378636055525016664559476808490723554481335856183927702549281730

# 分解得到p与q
sn = isqrt(n)  # sn为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))

费马分解

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)

n = 148841588941490812589697505975986386226158446072049530534135525236572105309550985274214825612079495930267744452266230141871521931612761645600600201983605957650711248808703757693378777706453580124982526368706977258199152469200838211055230241296139605912607613807871432800586045262879581100319519318390454452117
e = 65537
c = 69038543593219231496623016705860610154255535760819426453485115089535439537440188692852514795648297200067103841434646958466720891016026061658602312900242658759575613625726750416539176437174502082858413122020981274672260498423684555063381678387696096811975800995242962853092582362805345713900308205654744774932

def find_complate_pingfang(n):
    a = gmpy2.isqrt(n)
    if a * a == n:
        return a, a
    a+=1  # 只有n是完全平方数时，a的平方等于n，此时b2=0，其他初始情况下b2均小于0,所以直接加1
    b2 = a**2 - n  
    b = gmpy2.isqrt(b2)
    while b**2 != b2:
        a+=1
        b2 = a*a - n
        b = gmpy2.isqrt(b2)
    p = a-b
    q = a+b
    assert n == p*q
    return p,q

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

多素数类型问题

类型一：2素数相乘得到两组n

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

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

q = gcd(n1, n2)
p1 = n1 // q
phi = (p1-1)*(q-1)
d = invert(e, phi)

m = pow(c1, d, n1)
print(long_to_bytes(m))

类型二：多素数相乘得到一组n

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

类型三：2素数包含多次方

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

难点：

如何得到`phi`？

求phi需要通过欧拉函数 φ(n) = (p-1)*(q-1) ，即需要通过分解n得到p和q，再求出phi，问题在于大数分解（即如何求pq）。

`factordb`：

使用[factordb](https://factordb.com/)来进行分解，该网站存储了大量的因数关系，将n提交至该网站，便可以得到结果

`yafu`：

使用factordb来分解题目中的n，大部分情况都是得不到的

例如n = 53690629441472827148854210396580805205350972614395425306316047967905824330731

对于不算太大的素数，我们可以尝试使用一些工具来分解这个数

（示例中n为77位十进制数字，分解为p和q是两个128位的素数，这个数相比之前我们生成的256或是512素数来说几乎是0（无特别说明，位数指二进制位数，位数＋1，值为2倍））

yafu便是这样一种工具，它内置了各种分解算法，能够对不太大或者一些特殊情况下的数进行因式分解。

下载地址

使用方法：yafu.md

`p`与`q`差值小类型

1.直接开平方：

如果素数都比较大，此时我们无法通过上述方法得到p和q。若题目生成p后，使用next_prime函数获取p的下一个素数作为q，此时p与q差值小（原因：素数在自然数中没那么少，大部分情况下二者的差值都小于1000），可以使用费马分解或直接开平方来求出p和q。

即：

题目告诉我们使用了next_prime得到q
题目给出n的值
题目告诉我们e和c（密文）
求m（明文）
使用直接开平方搜索附近来分解 (n)

由p与q差值小可得：

$的下一个素数也应是$

我们使用gmpy2中的isqrt函数（gmpy2更快）

1
2
3

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

注意除的时候需要用整除。

2.费马分解

代码：

1 2	`p = getPrime(512) # 512位素数 q = gmpy2.next_prime(p - getPrime(256))`

p是512位的素数

我们先来思考next_prime内的代码 p - getPrime(256)，设r = getPrime(256)

即p-r

可以将p-r看成p，因为r在p和q面前非常小

所以我们可以认为p和q依然是两个比较接近的数

但如果想和上一题一样便不能了，因为此时p和q不是相邻的素数，当我们求解sn=sqrt(n)后，q不再是sn=sqrt(n)相邻的素数，也就是说我们可以在r的范围内找到q,但256位是一个不小的数，显然不能通过遍历找到p和q。

上述可以理解为：

p和q是两个比较接近的数
尽管p和q的差值相对p和q非常小，但它本身仍是一个非常大的数，我们难以通过遍历找到p和q的值

在这种情况下，我们需要一种更加通用的算法

费马分解：

假设p和q是两个接近的正整数，且 n=p*q。

我们定义：

这里a是p和q的平均值，b是它们距离平均值的一半。可以发现由于p和q很接近，a（即p和q的平均值）可以看成sqrt(n)(后续讨论)

即
$时，$

$此时，$

或
$时，$

$此时，$

代入n=p*q

即

显然我们可以得出结论：
$必须是一个完全平方数$
于是我们可以：

从a=sqrt(n)开始尝试（理由在上面说明了）
计算a^2-n
检查它是否为完全平方数
如果是，我们就得到了b，然后计算p = a - b ，q = a + b（后续操作中p与q没区别，这里不需要在意是加是减）

注意p与q越接近，b越小，a越接近sqrt(n)，尝试次数越少

核心思想：
把n表示成两个平方数之差 ( a^2 - b^2 )，当p和q接近时，b很小，可以快速搜索到a。

个人理解：缩小搜索范围，优化搜索方法，降低复杂度

核心代码：

def fermat_attack(n):
    a = isqrt(n)  # 从a=sqrt(n)开始尝试（如有小数，向下取整）
    if a * a == n:
    	return a, a
    a+=1  # 只有n是完全平方数时，a的平方才等于n，此时b2=0，其他初始情况下b2均小于0,所以直接加1
    b2 = a**2 - n  # 计算出b的平方
    b = isqrt(n)  # 计算出整数b
    while b**2 != b2:  # 检查整数b是否为完全平方数（计算整数b的平方是否等于b的平方）
        # 整数b的平方不等于b的平方
        a = a + 1  # 准备尝试下一个a
        b2 = a*a - n  # 准备尝试下一个b的平方
        b = isqrt(b2)  # 计算出下一个整数b
    p = a+b
    q = a-b
    assert n == p * q  # 断言，False会触发错误并终止程序执行
    return p, q

注意第一次运行时会有问题，n如果不是完全平方数，则初始a的平方一定小于n，这会导致b2=a**2-n为负数，所以我们直接加1不去考虑此时的a和b。不考虑的原因为：如果此时的a和b是我们需要的a和b，只有可能n是完全平方数，a为p和q，但是这和我们的前提矛盾了：n不是完全平方数。因此我们不用考虑这种情况

以上为个人理解，可能有误

多素数类型问题

知识点：

两素数的乘积除了1和它本身外一定只有2个因子，且这两个因子分别为这两个素数

类型一：2素数相乘得到两组n

例题：

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

由题可知，题目通过2组n对明文m进行加密，加密后的2组密文m都可还原成明文，我们任取其一即可

n1，n2已知，那么我们的问题转变成了如何得到n1或n2的素数因子p和q

题目告诉我们n1和n2分别是p1和p2乘以q得到的，且p1，p2，q均为素数，则我们需要的p就是p1或p2，需要的q就是q。

由知识点可得，n1除了q和p1没有其他的因数，n2同理，所以n1和n2的最大公因数就是q，我们可以使用gcd函数来得到q

q已知，那么p1，p2就解出来了

核心代码：

1
2
3

from gmpy2 import *
q = gcd(n1, n2)
p1 = n1 // q

类型二：多素数相乘得到一组n

知识点：欧拉函数的推广
$欧拉函数：$

$推广：$

至于为什么？自个儿学去

例题：

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

由题可知，n由pqr相乘得到，根据知识点，我们可以知道phi=(p-1)(q-1)(r-1)

秒了

类型三：2素数包含多次方

$知识点：$

例题：

from Crypto.Util.number import *

p = 80505091208742938705306670241621545375764148093711243653439069254008824979403
q = 67599990875658931406915486208971556223245451500927259766683936131876689508521
e = 65537
c = 7958690969908064264211283192959937430539613460471121984649054121171267262097603091410178042319139582772142226087020110084551158367679146616732446561228522673699836019156243452069036383047309578614662564794584927846163157472211089368697387945469398750955336949678910159585015004994620777231073804301249774041

n = (p**3)*q

在本题中，n=p^3*q，所以

由知识点得：

所以

知识点原因：

我们以题目为例子，φ(p^3)即为在素数p^3范围内，有多少个与p^3互质的整数的个数。

显然和p^互质的整数有很多，且难以找出其中的规律

因此我们可以反过来思考，只要找出所有与p^3不互质的整数，再用p^3减去这些整数的个数，就是与p^3互质的整数的个数。

整数与p^3不互质意味着这个整数可以被p^3整除，因此我们可以发现当且仅当整数为素数p的倍数时，整数能被p^3整除，即当且仅当整数为素数p的倍数时，整数与p^3不互质。

那么有多少个这样的倍数呢？我们可以举例一下：
$在到中，能被整除的数有：$
或者如果觉得这样不够清晰，可以思考：在1到p^3中，每隔p就有一个整数能被p整除

那么一共有多少个这样的数？
就是p^3/p=p^2个

所以互质的整数的个数为

于是我们能推断

#密码学 #rsa

RSA详解

http://page.ccnyy.top/2025/10/21/rsa/

作者

ccnyy

发布于

2025年10月21日

更新于

2025年10月24日

许可协议

java学习下一篇

RSA详解

提供pqec求m

提供nec求m

解题代码：

pq相近类型

直接开平方

费马分解

多素数类型问题

类型一：2素数相乘得到两组n

类型二：多素数相乘得到一组n

类型三：2素数包含多次方

难点：

如何得到phi？

factordb：

yafu：

p与q差值小类型

1.直接开平方：

2.费马分解

多素数类型问题

类型一：2素数相乘得到两组n

类型二：多素数相乘得到一组n

类型三：2素数包含多次方

提供`pqec`求m

如何得到`phi`？

`factordb`：

`yafu`：

`p`与`q`差值小类型