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

shenyue2（RSA 利用 ed 同余关系分解 n）

pasted_1787202168253_ayfy2c.png

源码里先把 FLAG 转成整数，然后设置 RSA 参数：e=65537，随机生成两个 2048 bit 素数 p,q，并给了一个固定的 100 bit 左右的 r

关键泄露点在这里：

1
2
3
phi = (p-1)*(q-1)
d = modular_mul_inverse(e, phi)
k = (p-r)*d

标准 RSA 中：

1
2
3
n = p * q
phi = (p - 1)(q - 1)
e * d ≡ 1 (mod phi)

所以一定存在一个整数 t，使得

1
e * d = 1 + t * phi

所以

1
d = (1 + t * phi) / e

因为 0 < d < phi，所以

1
2
3
1 <= t < e

1 <= t <= 65536

这就给了我们爆破空间，把泄露的 k 代入

1
2
3
k = (p - r) * d

e * k = (p - r) * e * d

又因为 e * d = 1 + t * phi，所以

1
e * k = (p - r) * (1 + t * phi)

在 RSA 中

1
2
3
4
5
6
7
phi = (p - 1)(q - 1)

phi = pq - p - q + 1

n = p * q

phi = n - p - q + 1

代入得到

1
e * k = (p - r) * (1 + t * (n - p - q + 1))

这个式子里，n,e,k,r 已知，t,p,q 未知

对于真实的 t

1
phi = n - p - q + 1

而 p + q 相比 n 非常小，所以

1
2
3
phi = n - (p + q - 1)

phi ≈ n

于是

1
2
3
e * k = (p - r) * (1 + t * phi)

e * k ≈ (p - r) * t * n

所以

1
p ≈ e * k / (t * n) + r

于是解题策略变成：

  • 枚举 t = 1 ~ 65536

  • 计算 p0 = floor(e*k / (t*n)) + r

  • 在 p0 附近小范围搜索

  • 如果某个候选 p_candidate 可以整除 n，说明找到了真正的 p

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
36
37
38
39
40
41
import re
from pathlib import Path

# 从注释中提取 n, e, k, enc
n = 
e = 
k = 
enc = 

# 从源码中提取 r
r = 

found = False

for t in range(1, e):
    # 由 e*k ≈ (p-r)*t*n 得到 p 的近似值
    p0 = (e * k) // (t * n) + r

    # 真实 p 只会在 p0 附近，搜索一个小范围即可
    for delta in range(-50, 51):
        p = p0 + delta

        if p > 1 and n % p == 0:
            q = n // p
            print("[+] found t =", t)
            print("[+] found delta =", delta)
            print("[+] p =", p)
            print("[+] q =", q)

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

            m = pow(enc, d, n)
            flag = m.to_bytes((m.bit_length() + 7) // 8, "big")

            print("[+] flag =", flag.decode())
            found = True
            break

    if found:
        break

运行结果

1
2
3
[+] found t = 38634
[+] found delta = 2
[+] flag = flag{61c31024-5dad-4f8f-b641-b2bf1f4afde7}

RSA（RSA PKCS#1 padding）

pasted_1787232590057_5jxbjb.png

核心代码如下，如果 RSA 加密失败则重新生成 p,q,e

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
flag = open('flag', 'r').read().strip() * 23

def encrypt(p, q, e, msg):
    while True:
        n = p*q

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

            pubkey = RSA.construct((int(n), int(e)))

            key = PKCS1_v1_5.new(pubkey)

            enc = b64encode(key.encrypt(msg))

            return enc

        except:
            p = gmpy2.next_prime(p**2+q**2)

            q = gmpy2.next_prime(2*p*q)

            e = gmpy2.next_prime(e**2)

首先查看公钥

1
openssl rsa -pubin -text -modulus -in pubkey.pem

得到

1
2
3
4
5
n =
893F055D0DC5FE764D881D5CD60E967B212CE049459E57D2E841ED4A81AF77ED

e =
9850747023606211927

分解 n

1
2
3
4
5
p =
184333227921154992916659782580114145999

q =
336771668019607304680919844592337860739

但是代码最后 flag * 23 长度非常大

RSA PKCS#1 v1.5 要求 明文长度 < n 长度 - padding，也就是说第一次必然失败

所以我们只需把题目中的 encrypt() 逻辑原样反过来写成 decrypt()，让 RSA 解密过程自己触发异常，然后继续更新 p、q、e，直到成功

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import gmpy2
import libnum
import base64
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_v1_5

# 从pubkey.pem读取
pub = RSA.importKey(open("pubkey.pem", "rb").read())
e = pub.e

# 分解得到的初始p q
# 注意顺序不要乱
q = 184333227921154992916659782580114145999
p = 336771668019607304680919844592337860739

# 读取密文
cipher = open("flag.enc", "rb").read()
cipher = base64.b64decode(cipher)


def decrypt(p, q, e, msg):
    while True:
        try:
            n = p * q
            phi = (p - 1) * (q - 1)
            d = libnum.invmod(e, phi)

            # 构造完整私钥
            private_key = RSA.construct(
                (
                    int(n),
                    int(e),
                    int(d),
                    int(p),
                    int(q)
                )
            )

            decipher = PKCS1_v1_5.new(private_key)
            flag = decipher.decrypt(msg, None)
            return flag

        except Exception as err:
            print("[+] decrypt failed")
            print(err)

            p = gmpy2.next_prime(p ** 2 + q ** 2)
            q = gmpy2.next_prime(2 * p * q)
            e = gmpy2.next_prime(e ** 2)


flag = decrypt(p, q, e, cipher)
print(flag.decode())

pasted_1787290524778_fnluxt.png

RSA（RSA 利用 p 和 q 的近似比例关系分解 n）

pasted_1788256127781_o72aic.png

题目大概是

1
2
3
4
5
6
7
A = (((y % x) ** 5) % (x % y)) ** 2019 + y ** 316 + (y + 1) / x

p = next_prime(z * x * y)
q = next_prime(z)

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

已知 A, n, c，从 A 推出 x 和 y

已知 A < 2 ^ 2019（题目给出的 A 具体数值可测出）

所以 (((y % x) ** 5) % (x % y)) ** 2019，如果底数 ≥ 2，就会爆到至少 2 ^ 2019，超过 A。因此这个底数只能是 0 或 1

于是 A 主要由 y ** 316 贡献

所以直接取 316 次整数根：y = iroot(A, 316)[0]

得到 y = 83，再代回原式爆小范围的 x，得到

1
2
3
x = 2
y = 83
x * y = 166
1
2
3
4
5
6
7
8
9
10
11
12
p = next_prime(z * x * y)
q = next_prime(z)

x * y = 2 * 83 = 166

p ≈ 166z
q ≈ z
p ≈ 166q

n = p * q ≈ 166 * q^2

q ≈ sqrt(n / 166)

然后在 sqrt(n // 166) 附近爆破，找到能整除 n 的 q

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
from math import isqrt

def iroot(n, k):
    """
    返回 floor(n ** (1/k))
    """
    lo, hi = 0, 1 << ((n.bit_length() + k - 1) // k)
    while lo + 1 < hi:
        mid = (lo + hi) // 2
        if mid ** k <= n:
            lo = mid
        else:
            hi = mid
    return lo

def long_to_bytes(x):
    return x.to_bytes((x.bit_length() + 7) // 8, "big")

A = 2683349182678714524247469512793476009861014781004924905484127480308161377768192868061561886577048646432382128960881487463427414176114486885830693959404989743229103516924432512724195654425703453612710310587164417035878308390676612592848750287387318129424195208623440294647817367740878211949147526287091298307480502897462279102572556822231669438279317474828479089719046386411971105448723910594710418093977044179949800373224354729179833393219827789389078869290217569511230868967647963089430594258815146362187250855166897553056073744582946148472068334167445499314471518357535261186318756327890016183228412253724

n = 117930806043507374325982291823027285148807239117987369609583515353889814856088099671454394340816761242974462268435911765045576377767711593100416932019831889059333166946263184861287975722954992219766493089630810876984781113645362450398009234556085330943125568377741065242183073882558834603430862598066786475299918395341014877416901185392905676043795425126968745185649565106322336954427505104906770493155723995382318346714944184577894150229037758434597242564815299174950147754426950251419204917376517360505024549691723683358170823416757973059354784142601436519500811159036795034676360028928301979780528294114933347127

c = 86974685960185109994565885227776590430584975317324687072143606337834618757975096133503732246558545817823508491829181296701578862445122140544748432956862934052663959903364809344666885925501943806009045214347928716791730159539675944914294533623047609564608561054087106518420308176681346465904692545308790901579479104745664756811301111441543090132246542129700485721093162972711529510721321996972649182594310700996042178757282311887765329548031672904349916667094862779984235732091664623511790424370705655016549911752412395937963400908229932716593592702387850259325784109798223415344586624970470351548381110529919234353

e = 65537

# 1. 由 A 推 y
y = iroot(A, 316)
print("[+] y =", y)

# 2. 由题目关系得到 x = 2
x = 2
assert (((y % x) ** 5) % (x % y)) ** 2019 + y ** 316 + (y + 1) // x == A

xy = x * y
print("[+] x*y =", xy)

# 3. q ≈ sqrt(n / 166)，在附近爆破
q0 = isqrt(n // xy)
q = None

for i in range(100000):
    for cand in (q0 + i, q0 - i):
        if cand > 1 and n % cand == 0:
            q = cand
            break
    if q:
        break

assert q is not None

p = n // q
assert p * q == n

print("[+] p =", p)
print("[+] q =", q)

# 4. RSA 解密
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
m = pow(c, d, n)

print(long_to_bytes(m))

simple_math（RSA Wilson 定理 + 利用 ed 同余关系分解 n）

pasted_1789308771771_cix0re.png

题目核心代码如下

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
def gen_p():
    A = gen_prime(513)
    print("A:", A)
    B = (A - 1) // 2
    C = A - randint(1e3, 1e5)
    print("C:", C)
    
    N1 = gen_N(A, B)
    N2 = gen_N(A, C)
    seed1 = 2019 * N1 + 2020 * N2
    return sympy.nextprime(seed1)

def gen_q():
    p = getPrime(1024)
    q = getPrime(1024)
    assert(p < q)
    n = p * q
    print("n:", n)

    e = getRandomNBitInteger(50)
    phi = (p - 1) * (q - 1)
    while gcd(e, phi) != 1:
        e = getRandomNBitInteger(50)

    d = invert(e, phi)
    print("e*d:", e * d)

    seed2 = 2020 * p - 2019 * q
    if seed2 < 0:
        seed2 = (-1) * seed2

    return sympy.nextprime(seed2)

最后加密

1
2
3
4
5
_E = 65537
_P = gen_p()
_Q = gen_q()
_M = bytes_to_long(flag)
_C = pow(_M, _E, _P * _Q)

所以真正用来加密 flag 的 RSA 模数是 N = _P * _Q，我们要分别恢复 _P 和 _Q

题目给了 A 和 C，并且

1
2
3
4
B = (A - 1) // 2
N1 = B! mod A
N2 = C! mod A
_P = nextprime(2019 * N1 + 2020 * N2)

其中 C = A - randint(1e3, 1e5)，所以 C 和 A 非常接近

令 k = A - C，附件里实际算出来 k = 67381，也就是说 C = A - 67381

如果直接算 C! mod A 肯定不行，因为 C 是一个 513 bit 级别的大数

Wilson 定理一句话：如果 A 是素数，那么 (A - 1)! ≡ -1 (mod A)

阶乘定义是 n! = 1 * 2 * 3 * …… * n，也就是说 1 * 2 * 3 * …… * (A - 1) ≡ A - 1 (mod A)

因为 -1 + A = A - 1，所以 A - 1 ≡ -1 (mod A)

由同余的传递性，得到 (A - 1)! ≡ -1 ≡ A - 1 (mod A)

题目里 C = A - K，因为 K 是正整数，且 K < A，所以 1 < C < A

也就是说 C 是 1 到 A - 1 之间的一个整数

因此 1 * 2 * 3 * …… * (A - 1) 可以拆成两段：第一段是从 1 到 C，第二段是从 C + 1 到 A - 1

1
(A - 1)! = (1 * 2 * 3 * …… * C) * ((C + 1) * (C + 2) * …… * (A - 1))

而 1 * 2 * 3 * …… * C = C!，所以

1
2
(A - 1)! = (1 * 2 * 3 * …… * C) * ((C + 1) * (C + 2) * …… * (A - 1))
(A - 1)! = C! * ((C + 1) * (C + 2) * …… * (A - 1))

又因为 C = A - K，所以 K = A - C，于是

1
2
C + 1 = A - K + 1 = A - (K - 1)
C + 2 = A - K + 2 = A - (K - 2)

一直到最后 A - 1 = A - 1，所以第二段变成 (A - (K - 1) * A - (K - 2) * …… * (A - 1))

在模 A 下

1
2
3
4
A - (K - 1) ≡ -(K - 1)
A - (K - 2) ≡ -(K - 2)
……
A - 1 ≡ -1

所以第二段模 A 等于 (-(K - 1) * (-(K - 2)) * …… * (-1))

一共有 K - 1 个负号，所以 (-1) ^ (K - 1) * (K - 1) * (K - 2) * …… * 1

也就是 (-1) ^ (K - 1) * (K - 1)!，再代回去

1
2
(A - 1)! = C! * ((C + 1) * (C + 2) * …… * (A - 1))
(A - 1)! ≡ C! * (-1) ^ (K - 1) * (K - 1)!

由于 A 是素数，Wilson 定理得到 (A - 1)! ≡ -1 (mod A)

所以 -1 ≡ C! * (-1) ^ (K - 1) * (K - 1)! (mod A)

两边同时乘以 (-1) ^ (K - 1)

1
2
3
-1 * (-1) ^ (K - 1) = (-1) ^ k

(C! * (-1) ^ (K - 1) * (K - 1)!) *  (-1) ^ (K - 1) = C! * (K - 1)!

所以 (-1) ^ k ≡ C! * (K - 1)! (mod A)，两边同时乘以 (K - 1)! 的逆元

因为 A 是素数，且 K - 1 < A，所以 1 * 2 * 3 * …… * (K - 1) = (K - 1)! 与 A 互素，即

1
gcd((K - 1)!, A) = 1

所以 (K - 1)! 在模 A 下存在逆元，设这个逆元为 inv = ((K - 1)!) ^ (-1) (mod A)

1
2
(-1) ^ k * inv ≡ C! * (K - 1)! * inv (mod A)
(-1) ^ k * inv ≡ C! * ((K - 1)! * inv) (mod A)

因为 (K - 1)! * inv = 1 (mod A)

1
2
3
4
(-1) ^ k * inv ≡ C! * ((K - 1)! * inv) (mod A)
(-1) ^ k * inv ≡ C! (mod A)
(-1) ^ k * ((K - 1)!) ^ (-1) ≡ C! (mod A)
C! ≡ (-1) ^ k * ((K - 1)!) ^ (-1) (mod A)

因此 N2 = C! (mod A) = (-1) ^ k * ((K - 1)!) ^ (-1) (mod A)

接下来继续恢复 N1 = ((A - 1) // 2)! mod A，令 m = (A - 1) / 2

根据 Wilson 定理：(A - 1)! ≡ -1 mod A，把 (A - 1)! 从 m 处切开

1
(A - 1)! = (1 * 2 * 3 * …… * m) * ((m + 1) * (m + 2) * …… * (A - 1))

前半段为 1 * 2 * 3 * …… * m = m!，后半段在模 A 下

1
2
3
4
m + 1 = -m (mod A)
m + 2 = -(m - 1) (mod A)
……
A - 1 = -1 (mod A)

所以

1
(m + 1) * (m + 2) * …… * (A - 1) ≡ (-m) * (-(m - 1)) * …… * (-1) (mod A)

这里一共有 m 个负号，所以

1
(-m) * (-(m - 1)) * …… * (-1) = (-1) ^ m * m * (m - 1) * …… * 1

而 m * (m - 1) * …… * 1 = m!，所以

1
2
3
4
5
(m + 1) * (m + 2) * …… * (A - 1) ≡ (-m) * (-(m - 1)) * …… * (-1) (mod A)
(m + 1) * (m + 2) * …… * (A - 1) ≡ (-1) ^ m * m! (mod A)

(A - 1)! ≡ (-1) ^ m * m! * m! (mod A)
(A - 1)! ≡ (-1) ^ m * (m!) ^ 2 (mod A)

由 Wilson 定理：(A - 1)! ≡ -1 (mod A)，所以

1
2
(A - 1)! ≡ (-1) ^ m * (m!) ^ 2 (mod A)
      -1 ≡ (-1) ^ m * (m!) ^ 2 (mod A)

因为 A ≡ 3 (mod 4)，设 A = 4t + 3，则

1
2
3
m = (A - 1) / 2
  = (4t + 3 - 1) / 2
  = 2t + 1

因为 m 是奇数，因此

1
2
3
(-1) ^ m = (-1) ^ (2t + 1)
         = (-1) ^ (2t) * (-1) ^ 1
         = -1

代入 -1 ≡ (-1) ^ m * (m!) ^ 2 (mod A) 中，得到

1
2
-1 ≡ (-1) ^ m * (m!) ^ 2 (mod A)
-1 ≡ (-1) * (m!) ^ 2 (mod A)

两边同时乘以 −1

1
2
1 ≡ (m!) ^ 2 (mod A)
(m!) ^ 2 ≡ 1 (mod A)

而 N1 ≡ m! (mod A)，所以 N1 ^ 2 ≡ 1 (mod A) 

1
2
3
N1 ^ 2 ≡ 1 (mod A)
N1 ^ 2 - 1 ≡ 0 (mod A)
(N1 - 1)(N1 + 1) ≡ 0 (mod A)

因为 A 是素数，所以 A | (N1 - 1) 或 A | (N1 + 1)，于是

1
N1 ≡ 1 (mod A) 或 N1 ≡ -1 (mod A)

即 N1 = 1 或 N1 = A - 1

题目里

1
2
seed1 = 2019 * N1 + 2020 * N2
   _p = nextprime(seed1)

所以对 N1 的两个取值，分别计算一次 seed1，得到两个候选 _p

当 N1 = 1 时，得到 _P = 29980405391237365494597168525833309900267720449837722663797882464292688736399471276643180209621186905684266642360886383187160507504219009609357296973525651439

题目给了

1
2
n = p * q
ed = e * d

其中 e * d ≡ 1 mod phi(n)，所以 e * d - 1 = k * phi(n)

也就是说，题目泄露了 ed，相当于泄露了一个 phi(n) 的倍数

对于任意与 n 互素的随机数 a，都有 a ^ (ed - 1) ≡ 1 (mod n)

把 ed - 1 拆成 ed - 1 = 2 ^ s * r，其中 r 是奇数，然后取随机底数 a，计算

1
x = pow(a, r, n)

不断平方 x = x ^ 2 mod n，如果某一步出现 x ^ 2 ≡ 1 mod n，但是

1
2
x != 1
x != -1 mod n

那么 x 是模 n 下的非平凡平方根，可以用 gcd(x - 1, n) 分解出 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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
import re
import math
import random
import sympy


def long_to_bytes(x: int) -> bytes:
    return x.to_bytes((x.bit_length() + 7) // 8, "big")


def read_params(filename="simple_math.py"):
    with open(filename, "r", encoding="utf-8") as f:
        data = f.read()

    A = int(re.search(r"A:(\d+)", data).group(1))
    C = int(re.search(r"C:(\d+)", data).group(1))
    n = int(re.search(r"n:(\d+)", data).group(1))
    ed = int(re.search(r"e\*d:(\d+)", data).group(1))
    ciphertext = int(re.search(r"ciphertext:(\d+)", data).group(1))

    return A, C, n, ed, ciphertext


def recover_N2(A, C):
    """
    N2 = C! mod A
    C = A - k

    Wilson:
        (A - 1)! ≡ -1 mod A

    又有：
        (A - 1)! = C! * (C + 1) * ... * (A - 1)

    由于 C = A - k：
        (C + 1) ... (A - 1)
        ≡ (-1)^(k-1) * (k-1)! mod A

    所以：
        C! ≡ (-1)^k * inverse((k-1)!) mod A
    """
    k = A - C

    fac = 1
    for i in range(1, k):
        fac = fac * i % A

    N2 = pow(-1, k, A) * pow(fac, -1, A) % A
    return N2


def factor_from_ed(n, ed):
    """
    已知 ed，分解 n。

    因为：
        ed ≡ 1 mod phi(n)

    所以：
        ed - 1 是 phi(n) 的倍数。

    利用 ed - 1 = 2^s * r，r 为奇数。
    通过寻找模 n 下的非平凡平方根分解 n。
    """
    k = ed - 1

    s = 0
    r = k
    while r % 2 == 0:
        s += 1
        r //= 2

    while True:
        a = random.randrange(2, n - 1)
        g = math.gcd(a, n)
        if g > 1:
            return g, n // g

        x = pow(a, r, n)

        if x == 1 or x == n - 1:
            continue

        for _ in range(s):
            y = pow(x, 2, n)

            if y == 1:
                p = math.gcd(x - 1, n)
                if 1 < p < n:
                    q = n // p
                    return min(p, q), max(p, q)

            if y == n - 1:
                break

            x = y


def main():
    A, C, n, ed, ciphertext = read_params("simple_math.py")

    e = 65537

    # ---------- recover _P ----------
    N2 = recover_N2(A, C)

    # N1 = ((A-1)//2)! mod A
    # 由 Wilson 可知 N1^2 ≡ 1 mod A
    # 所以 N1 只可能是 1 或 A-1，两个都试。
    N1_candidates = [1, A - 1]

    # ---------- recover _Q ----------
    p, q = factor_from_ed(n, ed)
    seed2 = abs(2020 * p - 2019 * q)
    Q = sympy.nextprime(seed2)

    # ---------- decrypt ----------
    for N1 in N1_candidates:
        seed1 = 2019 * N1 + 2020 * N2
        P = sympy.nextprime(seed1)

        phi = (P - 1) * (Q - 1)

        if math.gcd(e, phi) != 1:
            continue

        d = pow(e, -1, phi)
        m = pow(ciphertext, d, P * Q)
        flag = long_to_bytes(m)

        if flag.startswith(b"flag{"):
            print(flag.decode())
            return

    print("failed")


if __name__ == "__main__":
    main()