RSA 基础

欧拉函数 φ(n)

φ(n) 表示 “小于等于 n 且与 n 互质的正整数的个数”

  • 如果 n 是质数 p，那么 φ(p) = p - 1（因为 1,2,…,p-1 都和 p 互质）

  • 如果 n = p * q，且 p、q 都是质数，那么 φ(n) = (p - 1) * (q - 1)

  • 例如 p = 5, q = 11，则 n = 55，φ(55) = 4 * 10 = 40

密钥生成

选两个大质数 p 和 q

实际中 p、q 有 1024 位或 2048 位，这里我们用小数字演示

1
2
p = 61
q = 53

计算 n 和 φ(n)

1
2
n = p * q = 61 * 53 = 3233
φ(n) = (61 - 1) * (53 - 1) = 60 * 52 = 3120

选公钥指数 e

要求：

  • 1 < e < φ(n)

  • e 与 φ(n) 互质（即最大公约数为 1）

小例子中我们选 e = 17

计算私钥指数 d

d 是 e 在模 φ(n) 下的乘法逆元，即满足：

1
(e * d) mod φ(n) = 1

换句话说，存在整数 k 使得：

1
e * d = k * φ(n) + 1

计算 d 可以用扩展欧几里得算法。小例子中，可以验证 d = 2753

加密过程

加密公式：

1
c = (m ^ e) mod n

例子：加密明文 m = 65

1
c = 65 ^ 17 mod 3233

直接算 65^17 巨大，但模运算可以逐步取余。结果：

1
c = 2790

解密过程

1
m = (c ^ d) mod n

例子：c = 2790, d = 2753, n = 3233

1
m = 2790 ^ 2753 mod 3233 = 65

推导过程

即要证明：

1
c^d ≡ m  (mod n)

将 c = m^e mod n 代入 c^d：

1
c^d ≡ (m^e)^d = m^(e*d)  (mod n)

利用 ed = kφ(n) + 1：

1
m^(e*d) = m^(k*φ(n) + 1) = [m^(φ(n))]^k * m

所以：

1
c^d ≡ [m^(φ(n))]^k * m  (mod n)

欧拉定理说：如果 m 和 n 互质（即 gcd(m, n) = 1），那么

1
m^(φ(n)) ≡ 1  (mod n)

因此

1
[m^(φ(n))]^k ≡ 1^k = 1  (mod n)

于是

1
c^d ≡ 1 * m = m  (mod n)

实战案例

equationSet（提公因数 p）

解题技巧先放前面：

  1. 符号化：所有给出的数值用数学符号表示出来，并建立它们之间的关系
  2. 寻找公因数：如果给出的两个大数 A 和 B 都是由相同的素数因子构成的，那么 GCD(A, B) 往往是解密的关键
  3. 确定解题路径：一旦 p 被分解出来，接下来就要想方设法得到 q 和 r 的信息

题目给出代码

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import *
from secret import flag

e = 65537
m = bytes_to_long(flag.encode())
p, q, r = getPrime(512), getPrime(512), getPrime(512)

n = p*q*r
c = pow(m, e, n)
print(c)
print(n)
print(p+q+r)
print(p*q+p*r)

转换成数学公式

1
2
3
4
5
n = p * q * r
t = p * q + p * r = p(q + r)
phi(n) = (p - 1)(q - 1)(r - 1)

gcd(pqr, p(q + r)) = p * gcd(qr, q + r)

我们可以清楚地看到，p 是 n 和 t 的公共因子

那 GCD(n, t) 会正好是 p 吗？会不会包含其他因子？

由于 q 和 r 都是生成的 512 位随机大素数，它们互质，且它们的和 q+r 极大概率与它们的积 qr 互质

因此 GCD(qr, q+r) = 1

结论：直接计算 GCD(n, t) 就能提取出素数 p

观察公因数 是 Crypto 选手的直觉。看到 n 和 t 有明显的公共结构（都含有 p），第一时间想到的就是 GCD

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Util.number import *

c = 216719040256186298397028655750064798850... 
n = 894056034566447301955142597300391580123...
t = 157435908314881832180551915807491465031...

p = GCD(n, t)

phi = (p - 1) * ((n - t) // p + 1)

d = inverse(65537, phi)

m = pow(c, d, n)

print(long_to_bytes(m))

easyRSA（线性组合泄露 d 与 φ(n)）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import *
from secret import flag

m = bytes_to_long(flag.encode())
e = 65537
p, q = getPrime(1024), getPrime(1024)
d = inverse(e, (p-1)*(q-1))
x = 11*d+7*(p-1)*(q-1)
c = pow(m, e, p*q)

print("n =", p*q)
print("c =", c)
print("x =", x)

# n = 15321211041844905603734344178124947500324300419514650914959277216026081094496518094622195813971694335738777589926626969243883848477814650916143749322154944235584863085124154540941941026813506509060939499627059712020664731558566028207969260861863294704292014958955493668692256998253634012942569080200336487172402729072437050952572508561453302097971258470685521456512378089846772560530301852104802168974905937732653119166440832834381675710869396094149006807933529429939569477709674581421481769103309376717894952118650888932952440197471338958967318775671821835706884032860123711415773758546392549257375305940969423099611
# c = 14896093236493033914781929755936872928003725648997746598164823180134348743474984136539422027221313199599273430548738399424773586673404519182726589878322104929749149555906399158136445184378100079558203687049497943904275695897824656260657349522646553949766831267321006314984113971129230701131171378457086851261467999754137290017989201512492586108768533159551545321805463224339252886492732021354821330371600069958523522302729848548167244423902572054475396534469987383265867036041513161170273368613864180696427386890714264902686976581317435011139081192227958859641684254938165261747405568369502852705979424383731908971282
# x = 265060901898485540806769085700708185460124724747068797929982044073895401490880169847709049380530156090772787935089173201664711759633269693627724735457902114209008145932150728406880988293457762401679305297063608204632708505031098047582175011825482347052645324085149631658741807382378778694666759557421043250548432429798543553950625554307402164142007388940921309688918410535907564996075660231557340541491155676279511654970843992008027830570227549010293790074386638365293013298327534604995316180405779571245069623638693068707267840181413082202552862853411080755107836252852929279422343700808788459217261282790226013328915

RSA 里，我们有：

  • p, q 两个大素数

  • n = p * q

  • φ(n) = (p-1)*(q-1)

  • 公钥指数 e = 65537（题目固定）

  • 私钥指数 d 满足 e * d ≡ 1 (mod φ(n))

这等价于存在一个整数 k，使得：

1
e * d = k * φ(n) + 1

即

1
d = (k * φ(n) + 1) / e

题目除了给 n 和密文 c，还给了

1
x = 11 * d + 7 * φ(n)

也就是说，x 是 d 和 φ(n) 的一个线性组合，系数分别是 11 和 7

将上面 d 的表达式代入 x

1
x = 11 * [ (kφ + 1)/e ] + 7φ

两边同时乘以 e，去掉分母

1
e * x = 11 * (kφ + 1) + 7eφ

展开

1
e * x = 11kφ + 11 + 7eφ

把常数项移到左边，含 φ 的项合并

1
e * x - 11 = (11k + 7e) φ

记 T = ex - 11，则

1
T = (11k + 7e) * φ

这是一个关键等式，T 是 φ 的整数倍，倍数 A = 11k + 7e 依赖于未知的 k

从 e * d = k φ + 1 得

1
k = (e * d - 1) / φ

因为 d < φ（实际上 d 是模 φ 下的逆元，通常比 φ 略小），所以

1
e * d - 1 < e * φ - 1  →  k < e

所以思路：

  • 计算 T = e * x - 11（已知 x 和 e）

  • 对每个可能的 k 从 0 到 e-1，计算 A = 11k + 7e

  • 如果 A 能整除 T，那么 φ = T // A 就是一个候选的欧拉函数值

  • 用这个 φ 去分解 n，因为 p + q = n - φ + 1，p * q = n，所以 p 和 q 是二次方程 X^2 - (p + q)X + n = 0 的两个根

  • 判断 p 和 q 是否为整数且满足 p * q == n，若是，则分解成功

已知

1
2
s = p + q
n = p × q

根据韦达定理，以 p 和 q 构造一个二次方程

1
2
(t-q)(t-p) = 0
           = t² - (p + q)t + qp

把已知条件带入得到

1
t² - s * t + n = 0

对于任意二次方程，判别式公式为

1
2
3
at² + bt + c = 0

Δ = b² - 4ac

代入得到

1
2
3
a = 1，b = -s，c = n

Δ = (-s)² - 4·1·n = s² - 4n

如果判别式是完全平方数，方程就有整数解

1
2
p = (s + √Δ)/2
q = (s - √Δ)/2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
from Crypto.Util.number import *
from math import isqrt

n = ...   # 从题目获取
c = ...   # 密文
x = ...   # 泄露的数值

e = 65537

T = e * x - 11

for k in range(1, e):               # 枚举 k = 1 .. e-1
    A = 11 * k + 7 * e
    if T % A != 0:
        continue
    phi = T // A

    # 用 phi 恢复 p+q
    s = n - phi + 1         # p + q = n - φ + 1
    delta = s * s - 4 * n   # 如果判别式 Δ = s² - 4n 是一个完全平方数，那么两个根就是整数
    r = isqrt(delta)        # 取整平方根（向下取整）
    if r * r != delta:      # 检查 Δ 是否为完全平方数
        continue

    p = (s + r) // 2
    q = (s - r) // 2
    if p * q != n:
        continue

    # 成功分解，计算 d 并解密
    d = pow(e, -1, phi)
    m = pow(c, d, n)
    flag = long_to_bytes(m)
    print(flag)
    break

little RSA（分解 n）

题目给了

1
2
3
c=32949
n=64741
e=42667

分解 n 得到 p，q

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import long_to_bytes

c = 32949
n = 64741
e = 42667
p = 101
q = 641

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

print("[+] bytes =", long_to_bytes(m))

解出为 18429 解压密码

Rivest Shamir Adleman（分解 n）

和上题一样的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from math import isqrt

n = 408579146706567976063586763758203051093687666875502812646277701560732347095463873824829467529879836457478436098685606552992513164224712398195503564207485938278827523972139196070431397049700119503436522251010430918143933255323117421712000644324381094600257291929523792609421325002527067471808992410166917641057703562860663026873111322556414272297111644069436801401012920448661637616392792337964865050210799542881102709109912849797010633838067759525247734892916438373776477679080154595973530904808231
e = 65537
c = 226582271940094442087193050781730854272200420106419489092394544365159707306164351084355362938310978502945875712496307487367548451311593283589317511213656234433015906518135430048027246548193062845961541375898496150123721180020417232872212026782286711541777491477220762823620612241593367070405349675337889270277102235298455763273194540359004938828819546420083966793260159983751717798236019327334525608143172073795095665271013295322241504491351162010517033995871502259721412160906176911277416194406909

# 已知或爆破得到的小素因子
p = 15485863
q = n // p

assert p * q == n

phi = (p - 1) * (q - 1)

# 求私钥指数 d
d = pow(e, -1, phi)

# RSA 解密
m = pow(c, d, n)

# long -> bytes
msg = m.to_bytes((m.bit_length() + 7) // 8, "big")

print("[+] flag =", msg.decode())