危险的RSA（XMU纳新赛）

题目代码

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
import sympy
import random

def myGetPrime():
    A= getPrime(513)
    print(A)
    B=A-random.randint(1e3,1e5)
    print(B)
    return sympy.nextPrime((B!)%A)
p=myGetPrime()
#A1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467234407
#B1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467140596

q=myGetPrime()
#A2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858418927
#B2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858351026

r=myGetPrime()

n=p*q*r
#n=85492663786275292159831603391083876175149354309327673008716627650718160585639723100793347534649628330416631255660901307533909900431413447524262332232659153047067908693481947121069070451562822417357656432171870951184673132554213690123308042697361969986360375060954702920656364144154145812838558365334172935931441424096270206140691814662318562696925767991937369782627908408239087358033165410020690152067715711112732252038588432896758405898709010342467882264362733
c=pow(flag,e,n)
#e=0x1001
#c=75700883021669577739329316795450706204502635802310731477156998834710820770245219468703245302009998932067080383977560299708060476222089630209972629755965140317526034680452483360917378812244365884527186056341888615564335560765053550155758362271622330017433403027261127561225585912484777829588501213961110690451987625502701331485141639684356427316905122995759825241133872734362716041819819948645662803292418802204430874521342108413623635150475963121220095236776428
#so,what is the flag?

解题思路

题目分析

题目使用自定义的素数生成函数 myGetPrime() 生成三个素数 p, q, r，然后计算 n = p*q*r 并用 RSA 加密 flag。需要根据给定的部分信息恢复私钥并解密。

关键步骤

  1. 威尔逊定理：对于素数 p，有 (p − 1)! ≡ −1 (mod  p)
  2. 模逆元计算：pow(a, -1, m) 计算 a 模 m 的逆元
  3. RSA 解密：计算 φ(n) 和私钥 d

解题步骤

1. 理解素数生成逻辑

1
2
3
4
def myGetPrime():
    A = getPrime(513)                 # 513位随机素数
    B = A - random.randint(1e3,1e5)   # B 比 A 小 1000-100000
    return sympy.nextPrime((B!)%A)    # 返回 B! mod A 的下一个素数

2. 利用威尔逊定理简化计算

对于素数 A，根据威尔逊定理：

(A − 1)! ≡ −1 (mod  A)

因此：

$$ B! = \frac{(A-1)!}{(B+1)(B+2)\cdots(A-1)} $$

所以：

B! ≡ (−1) ⋅ [(B + 1)(B + 2)⋯(A − 1)]−1 (mod  A)

3. 定义compute_prime函数求解 p 和 q

1
2
3
4
5
6
7
8
9
10
11
def compute_prime(A, B):
    # Compute (B+1) * (B+2) * ... * (A-1)
    product = 1
        for i in range(B + 1, A):
            product = (product * i) % A
    # Compute inverse of product mod A
    inv_product = pow(product, -1, A)
    # B! ≡ (-1) * inv_product mod A (by Wilson's theorem)
    B_fact_mod_A = (-1) * inv_product % A
    # Return next prime
    return sympy.nextprime(B_fact_mod_A)

4. 计算p、q、r：

1
2
3
p = compute_prime(A1, B1)
q = compute_prime(A2, B2)
r = n // (p * q)

5. RSA 解密

计算 φ(n)、私钥d：

1
2
3

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

6. 解密 flag

1
2
flag = pow(c, d, n)
print(long_to_bytes(flag))

完整代码

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
import sympy
import math
from Crypto.Util.number import *

# Given data
A1 = 21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467234407
B1 = 21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467140596
A2 = 16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858418927
B2 = 16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858351026
n = 85492663786275292159831603391083876175149354309327673008716627650718160585639723100793347534649628330416631255660901307533909900431413447524262332232659153047067908693481947121069070451562822417357656432171870951184673132554213690123308042697361969986360375060954702920656364144154145812838558365334172935931441424096270206140691814662318562696925767991937369782627908408239087358033165410020690152067715711112732252038588432896758405898709010342467882264362733
e = 0x1001
c = 75700883021669577739329316795450706204502635802310731477156998834710820770245219468703245302009998932067080383977560299708060476222089630209972629755965140317526034680452483360917378812244365884527186056341888615564335560765053550155758362271622330017433403027261127561225585912484777829588501213961110690451987625502701331485141639684356427316905122995759825241133872734362716041819819948645662803292418802204430874521342108413623635150475963121220095236776428

# Compute p
def compute_prime(A, B):
    # Compute (B+1) * (B+2) * ... * (A-1)
    product = 1
    for i in range(B + 1, A):
        product = (product * i) % A
    # Compute inverse of product mod A
    inv_product = pow(product, -1, A)
    # B! ≡ (-1) * inv_product mod A (by Wilson's theorem)
    B_fact_mod_A = (-1) * inv_product % A
    # Return next prime
    return sympy.nextprime(B_fact_mod_A)

p = compute_prime(A1, B1)
q = compute_prime(A2, B2)
r = n // (p * q)

# Verify p, q, r
assert p * q * r == n

# Decrypt
phi = (p - 1) * (q - 1) * (r - 1)
d = pow(e, -1, phi)
flag = pow(c, d, n)
print(long_to_bytes(flag))
CTF > Crypto
#CTF #Crypto #RSA #Wilson's Therom
危险的RSA（XMU纳新赛）
http://yaesakuraq.github.io/2025/05/10/危险的RSA/
作者
SakuraQ
发布于
2025年5月10日
许可协议