常用到的密碼學工具#

• yafu：大整數分解工具
• factordb：質因數分解資料庫
• sagemath：數學計算軟體，常用於密碼學計算
• CoCalc：線上 SageMath 環境
• CyberChef：編碼解碼和數據分析工具

常用到的 Python 函式庫#

• gmpy2：高精度數學運算庫
• libnum：數論和密碼學工具庫
• sympy：符號數學庫
• pycryptodome：密碼學函式庫（Crypto 模組）
• owiener：Wiener attack 實現

正確安裝 Crypto#

如果遇到 ModuleNotFoundError: No module named 'Crypto' 錯誤，通常是因為安裝了錯誤的 crypto 套件。正確的安裝方式：

1
pip uninstall crypto pycryptodome
2
pip install pycryptodome

crypto.bytes_to_long 原理#

1
def bytes_to_long(bytes_data):
2
    result = 0
3
    for b in bytes_data:
4
        result = result * 256 + b
5
    return result

crypto.long_to_bytes 原理#

1
def long_to_bytes(long_val):
2
    if long_val == 0:
3
        return b'\x00'
4
    result = bytearray()
5
    while long_val > 0:
6
        result.append(long_val & 0xff)
7
        long_val >>= 8
8
    return bytes(result[::-1])

RSA 原理#

1. 隨意選擇兩個大的質數 $p$ 和 $q$，$p$ 不等於 $q$，計算 $N = p \times q$
2. 根據歐拉函數獲取 $\phi = (p-1) \times (q-1)$
3. 選擇一個小於 $\phi$ 並與 $\phi$ 互質的整數 $e$ (public key)，我們通常取 65537
4. 求得 $e$ 關於 $\phi$ 的模反元素 $d$ (private key)，即 $ed \equiv 1 \pmod{\phi}$
5. $p, q$ 丟棄（保留 $N, e, d$）
   • 加密: $C \equiv M^e \pmod{N}$
   • 解密: $M \equiv C^d \pmod{N}$
   • 公鑰: $(N, e)$
   • 私鑰: $(N, d)$

RSA 攻擊#