FactorDB

链接

• 在线工具

是什么

FactorDB 是在线大整数分解数据库。Crypto/RSA 题中，如果给出的 n 已经被公开分解过，FactorDB 可以直接给出因子。

它适合入门 RSA 题的第一轮判断：这个 n 是否已经可分解。

安装与配置

FactorDB 是在线服务，不需要安装：

https://factordb.com/

也可以使用 Python 查询库：

python3 -m pip install factordb-pycli

基本用法

网页查询

打开 FactorDB，输入 n，查看结果状态：

C: composite, unknown factorization
CF: composite, factors known
FF: fully factored
P: prime

Python 查询思路

from factordb.factordb import FactorDB

f = FactorDB(n)
f.connect()
print(f.get_factor_list())

更多用法

API 访问

import requests

def query_factordb(n):
    """查询 FactorDB"""
    url = f"http://factordb.com/api?query={n}"
    response = requests.get(url)
    return response.json()

# 使用
result = query_factordb(n)
print(result["status"])  # C, CF, FF, P
print(result["factors"])  # 因子列表

批量查询

import requests
import time

def batch_query(numbers):
    """批量查询 FactorDB"""
    results = {}
    for n in numbers:
        url = f"http://factordb.com/api?query={n}"
        response = requests.get(url)
        data = response.json()
        results[n] = data
        time.sleep(1)  # 避免请求过快
    return results

# 使用
numbers = [n1, n2, n3, ...]
results = batch_query(numbers)

解析结果

from factordb.factordb import FactorDB

def get_factors(n):
    """获取 n 的因子"""
    f = FactorDB(n)
    f.connect()
    
    status = f.get_status()
    if status == "P":
        return [n]  # 素数
    elif status == "FF":
        return f.get_factor_list()  # 完全分解
    elif status == "CF":
        return f.get_factor_list()  # 部分分解
    else:
        return None  # 未知

命令行查询

# 使用 curl
curl "http://factordb.com/api?query=123456789"

# 使用 Python 一行命令
python3 -c "
import requests
n = int(input('Enter n: '))
r = requests.get(f'http://factordb.com/api?query={n}').json()
print(r)
"

查询状态判断

from factordb.factordb import FactorDB

def analyze_n(n):
    """分析 n 的状态"""
    f = FactorDB(n)
    f.connect()
    
    status = f.get_status()
    factors = f.get_factor_list()
    
    print(f"n = {n}")
    print(f"Status: {status}")
    
    if status == "P":
        print("n is prime - not a valid RSA modulus")
    elif status == "FF":
        print(f"Fully factored: {factors}")
        # 验证
        product = 1
        for p, e in factors:
            product *= p ** e
        assert product == n
    elif status == "CF":
        print(f"Partially factored: {factors}")
    else:
        print("Factorization unknown")

CTF常用技巧

RSA 先查 n

拿到 RSA 参数时：

1. 看 n 位数
2. 查 FactorDB
3. 如果已分解，计算 phi 和 d
4. 如果未分解，再看 e、共模、低指数、p/q 泄露等条件

不要只依赖 FactorDB

FactorDB 查不到不代表题无解。CTF 题经常通过弱随机、共因子、低指数、广播攻击、泄露高低位等方式突破。

批量 gcd

多组 RSA 公钥时，FactorDB 查不到也可以做两两 gcd：

from math import gcd

for i in range(len(ns)):
    for j in range(i + 1, len(ns)):
        g = gcd(ns[i], ns[j])
        if 1 < g < ns[i]:
            print(i, j, g)

完整 RSA 解题模板

from factordb.factordb import FactorDB
from Crypto.Util.number import inverse, long_to_bytes
from sympy import factorint

def solve_rsa(n, e, c):
    """尝试解密 RSA"""
    # 方法1: FactorDB
    f = FactorDB(n)
    f.connect()
    if f.get_status() == "FF":
        factors = f.get_factor_list()
        p, q = factors[0][0], factors[1][0] if len(factors) > 1 else factors[0][0]
        phi = (p - 1) * (q - 1)
        d = inverse(e, phi)
        m = pow(c, d, n)
        return long_to_bytes(m)
    
    # 方法2: sympy 分解
    factors = factorint(n)
    if len(factors) >= 2:
        primes = list(factors.keys())
        p, q = primes[0], primes[1]
        phi = (p - 1) * (q - 1)
        d = inverse(e, phi)
        m = pow(c, d, n)
        return long_to_bytes(m)
    
    return None

# 使用
result = solve_rsa(n, e, c)
if result:
    print(f"Decrypted: {result}")

常见状态处理

状态 FF (完全分解):
  - 直接使用因子
  - 计算 phi 和 d
  - 解密消息

状态 CF (部分分解):
  - 可能有小因子
  - 尝试其他攻击
  - 结合题目条件

状态 C (未分解):
  - FactorDB 无法分解
  - 尝试其他攻击方式
  - 检查题目是否有其他线索

状态 P (素数):
  - n 是素数
  - 不是有效 RSA 模数
  - 题目可能故意构造

常见问题

状态是 C 怎么办

表示还没分解。回到题目给的其他条件继续分析。

状态是 P 怎么办

如果 n 是素数，那就不是正常 RSA 模数，题目可能故意构造了异常参数。

查网页慢怎么办

用脚本查询或换网络；但不要频繁刷请求。

API 限制

1. 不要过于频繁请求
2. 使用 time.sleep() 延迟
3. 缓存查询结果
4. 批量查询时控制频率

查询结果不准确

1. 检查输入是否正确
2. 尝试手动验证
3. 使用其他工具交叉验证
4. 检查是否有特殊格式

关联

• RSA基本概念
• Crypto题先判断什么
• Python密码学库
• RsaCtfTool
• SageMath