題目連結

https://learn.cylabacademy.org/library/470

題目解法

使用 nc 連線後題目會提供 $N$, $e$（每次都不一樣）。在這題題目中的 $N$ 有明顯的漏洞，就是是 2 的倍數，代表其中一個質數一定是 $p = 2$。 解密步驟：

  1. 計算出 $q$ $$q = \frac{N}{2}$$

  2. 計算出 $\phi(n)$ $$\phi(n) = \phi(p) \times \phi(q) = (p-1) \times (q-1) = (2-1) \times (q-1) = q-1$$

  3. 計算私鑰 $d$：
    使用模反元素（Modular Inverse）公式： $$d \equiv e^{-1} \pmod{\phi(N)}$$

  4. 解密密文 $C$： $$m = C^d \pmod{N}$$

  5. 轉換為文字：
    將得到的長整數 $m$ 轉回 bytes，再以 UTF-8 解碼。

解題腳本

將 $N$, $e$, $cyphertext$ 填入執行即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

from Crypto.Util.number import long_to_bytes, inverse

# 已知資訊
N = 24363402644768690727955172666209469821725905198393631084455253811708663554350947264649402937037672246381690969915451279285279631133822103514599606304356602
e = 65537
cyphertext = 13597050467487786638619946148639439992899445404956336122073567173641265830288842478196554274484546393046984321139824087540835441687603028763464962383947497

# 1. 分解 N (因為 N 是偶數，所以其中一個質數是 2)
p = 2
q = N // p

# 2. 計算 phi(N)
phi = (p - 1) * (q - 1)

# 3. 計算私鑰 d
d = inverse(e, phi)

# 4. 解密
m_long = pow(cyphertext, d, N)

# 5. 轉回字串
print(long_to_bytes(m_long).decode('utf-8'))

題目原始碼

 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

from sys import exit
from Crypto.Util.number import bytes_to_long, inverse
from setup import get_primes

e = 65537

def gen_key(k):
    """
    Generates RSA key with k bits
    """
    p,q = get_primes(k//2)
    N = p*q
    d = inverse(e, (p-1)*(q-1))

    return ((N,e), d)

def encrypt(pubkey, m):
    N,e = pubkey
    return pow(bytes_to_long(m.encode('utf-8')), e, N)

def main(flag):
    pubkey, _privkey = gen_key(1024)
    encrypted = encrypt(pubkey, flag) 
    return (pubkey[0], encrypted)

if __name__ == "__main__":
    flag = open('flag.txt', 'r').read()
    flag = flag.strip()
    N, cypher  = main(flag)
    print("N:", N)
    print("e:", e)
    print("cyphertext:", cypher)
    exit()