博客基础信息

标题：CTF 密码学｜高斯整数环变种 RSA 题解（模数 n=p²q²） 分类：CTF-Crypto 标签：RSA 变种、高斯整数、复数模幂、Z [i]、自定义填充、n=p²q² 难度：中等偏上 前置知识：标准 RSA 原理、模快速幂、高斯整数基础、模逆元

一、题目整体介绍

本次 CTF 密码题为自定义高斯整数 RSA，区别于常规整数域 RSA，本题将明文封装为复数 a+bi，在高斯整数环 Z [i]下完成模幂加密；模数构造特殊 n=(p**2)*(q**2)，题目直接给出素因子私钥 (p,q)，无需大数分解，核心考察复数乘法、高斯整数欧拉函数、自定义填充还原。

附件文件

1. 加密源码 source_d8d60e7e8856687fa9d81f2c5eba7750.py

python

运行

from collections import namedtuple
from Crypto.Util.number import getPrime
import random

# 高斯整数结构体：实部re，虚部im
Complex = namedtuple("Complex", ["re", "im"])

# 复数模乘法 (a+bi)(c+di) mod modu
def complex_mult(c1, c2, modulus):
    return Complex(
        (c1.re * c2.re - c1.im * c2.im) % modulus,
        (c1.re * c2.im + c1.im * c2.re) % modulus,
    )

# 复数二分快速幂
def complex_pow(c, exp, modulus):
    result = Complex(1, 0)  # 乘法单位元 1+0i
    while exp > 0:
        if exp & 1:
            result = complex_mult(result, c, modulus)
        c = complex_mult(c, c, modulus)
        exp >>= 1
    return result

# 密钥生成 n = p² * q²
def generate_key_pair(nbits):
    while True:
        p = getPrime((nbits + 3) // 4)
        q = getPrime((nbits + 3) // 4)
        n = (p ** 2) * (q ** 2)
        if n.bit_length() == nbits:
            return (p, q), n

# 填充：随机前缀 + \x00分隔符 + 原始flag
def pad(data, length):
    assert len(data) < length
    pad_length = length - len(data) - 1
    pad_data = bytes(random.choices(range(1, 256), k=pad_length))
    sep = b'\x00'
    return pad_data + sep + data

# 去填充，截取分隔符后明文
def unpad(data):
    assert b"\x00" in data, "incorrect padding"
    return data.split(b"\x00", 1)[1]

# 加密逻辑
def encrypt(public_key, plaintext):
    n = public_key
    block_len = 2 * ((n.bit_length() - 1) // 8)
    plain_pad = pad(plaintext, block_len)
    half = len(plain_pad) // 2
    # 前半字节为实部，后半为虚部，构造高斯整数
    m = Complex(
        int.from_bytes(plain_pad[:half], "big"),
        int.from_bytes(plain_pad[half:], "big")
    )
    c = complex_pow(m, 65537, n)
    # 实虚部分别转字节拼接为密文
    return (c.re.to_bytes((n.bit_length() + 7) // 8, "big")
            + c.im.to_bytes((n.bit_length() + 7) // 8, "big"))

# 解密函数仅占位，需要选手自行实现
def decrypt(private_key, ciphertext):
    # TODO
    raise Exception("unimplemented")

def main():
    private_key, public_key = generate_key_pair(2021)
    from secret import flag
    print("private_key =", private_key)
    print("public_key =", public_key)
    print("ciphertext =", encrypt(public_key, flag))

if __name__ == '__main__':
    main()

1. 输出文件 output_f0813ec299f777b1ee2d3abe4d4e0df4.txt

python

运行

private_key = (128329415694646850105527417663220454989310213490980740842294900866469518550360977403743209328130516433033852724185671092403884337579882897537139175073013,
               119773890850600188123646882522766760423725010264224559311769920026142724028924588464361802945459257237815241227422748585976629359167921441645714382651911)
public_key = 236252683050532196983825794701514768601125614979892312308283919527619033977486749228418695923608569040825653688303374445536392159719426640289893369552258923597180869981053519695297428186215135878525530974780390951763007339139013157234202093279764459949020588291928614938201565110828675907781512603972957429701280916745719458738970910789383870206038035515777549907045905872280803964436193687072794878040018900969772972761081589529671158140590712503582004892067155769362463889653489918914397872964087471457070748108694165412065471040954221707557816986272311750297566993468288899523479556822418109112211944932649
ciphertext = b'\x00h\xbe\x94\x8c\xcd\xdd\x04\x80\xf4\x9d\t\xd8\x8dO\x08\xf1\xd1\xc4\xb9\xa06\xe7\xe3\xb6\xc3\x01+\xa9\xf2\xb9\xe8\x8d\xe6\xc9\x0c_#\x93\x11\xad\x0f\x90\xd3\x0b6\xb0n\x13\xea~"V6\xdbA&\x87\xfe\xa3C\xcb\x16\xae\xd9\x83\xdbU\xc6\x06\xcd\x9a\x94\xa9\xce\x15{d\x95s\xc2\xfb\x90q\xe7\x02\xa2\x081:_C\xc68\x00y\x7fj4@\xd2\xcdE\x06\x943\xbe\xbcC3\xca\x91\xb4\x0e}C\xab\xff?X\xc30u\x069:Dc\xb5\xdc\x9b0%\x98\xbd\xd9\x13\xc0\x02w\xc5\xe5:\xca\xcf\x0c\xab\xc2\x9b}\xab\xd0\xcc\xbc\x0f\x9e9\t\xf7M\xb3\xed\x86\xb5E\x8b\xbc4\xfaH\x9b4\x1c\xc4\xab\xc0\xaf\x8a5XcX\x19K\xed\x19\xe1\x1c\xd0\x1e\x97c\x9fF:L\x9d\x90p\x99\xb8\xde\xcblM\xb3\x80sSL\xe1\xa4\xd6,\x81\xd6\x9c\xf1\xbb\x9c)\xf03\x155\xc0\xd5v\x13\xd6#\xb7\x19\xdea%\xce<\x1c\xf7\xf2!;\xc1\xd7w\xd1\xc8\x8d/\xaew\xa1\x1d\xc5(\xc8\x9d\x82v\xf6j\x90A,e\xbd\xa7]\x10\x8f\xe5\xe7\x93}:\xdf1~\xec\xd0-o`\r\x96\xe4\x03\xb9E\x9fdF\xc3\xf8L\xa0\xda\xf0E[\xf7\x02\xef|*\x08\x8a5pI&\xa9i\x0fZ\xa8\xb3H\xed\xe8v\xc4H\xff\xdb\xcb\x00\xf1\xae\x9bO\x18\xd5\xd8&p\xf5\xf6\xe9\xf1\x1brs\xc2\r\xceZ\xd0\xb24\x97+\x98b\x0e\xbb\xb8.\x8dT\xe4"\xad\xe4\xa3f\xd0M\xbf\xafX\xbb"[\x99\xdap\xa5\xcfT2Wx\x87M\x7f\x99!>B[Q\x04\xf6\x03\xbc\x84\xf4\xdfj\xdd1^I\x1a\x05\x81\x91\xde9Mf*\x8e\x8d\xe64\xf8\x93\x99&yP\xcd\x00!\x82\xab\xbcy\xed\xf1\x13\xd3\x81\xeaz\xbbP>\x9a2\x8c\x08\x0es\xbc\xa9\xf6\xa3\x8c\xb0\xb9t\xd9?\x06@\xc9\x90\xb7\xa7<\x85\xeb\x1a\x88#\x1c\xc3 \xec\xc7\x94d\x99\xd6\x8e>\x06\xf8Y\xf4\x19\xcaI/hy\x18\x8e\x0e8\xf8\r\xbb\xf6\x11\xb9\x8dCWB6 '

二、核心原理拆解

1. 常规 RSA 与本题高斯 RSA 差异

标准 RSA：明文为整数，模数 n=pq，加密c=m**e (mod n)； 本题高斯整数 RSA：明文是复数 m =m_r+ m_i*i，所有运算在 Z [i]高斯整数环下完成，模数 n=(p**2)*(q**2)，自定义复数模乘与模幂。

2. 密钥生成规则

1. 生成两个素数 p,q；
2. 模数n=p**2×q**2；
3. 公钥：(n,e),e=65537；
4. 私钥：(p,q)（题目直接输出，无需大数分解，降低难度）。

3. 高斯整数乘法公式

(a+bi) * (c+di) = (ac-bd) + (ad+bc)i mod n代码中complex_mult严格实现该公式，实部减号极易写错，是高频踩坑点。

4. 加密数学流程

1. flag 经过pad填充：随机字节 + 分隔符\x00 + 原始明文；
2. 填充后字节对半拆分，前半转整数为实部、后半为虚部，组成复数明文 m；
3. 复数模幂加密：c = m**65537 mod n；
4. 将密文复数的实、虚部分别转字节拼接，输出最终ciphertext。

5. 解密核心：高斯整数欧拉函数

标准整数 RSA φ(n)=(p-1)(q-1) 完全不适用本题。 高斯整数环下，素数 p 满足 φ(n)Z[i](p**2) = p**2-p； 因此模数 n=(p**2)*(q**2) 的欧拉函数： φ(n)=(p**2-p)*(q**2-q) 私钥指数d = e**-1 mod φ(n)，满足e⋅d≡1(mod φ(n))； 解密运算：m=c**d(mod n)，还原复数明文后拼接字节、去填充得到 flag。

6. 填充与去填充逻辑

加密时填充串格式：随机乱码 + b'\x00' + flag； 解密拿到完整字节串后，按第一个\x00分割，取后半段即为原始 flag。

三、做题踩坑实录

坑 1：直接套用标准 RSA 欧拉函数

新手容易直接写phi=(p-1)*(q-1)计算 d，解密后字节乱码。高斯整数环欧拉函数与整数域完全不同，必须使用 (p**2-p)*(q**2-q) 。

坑 2：复数乘法实部符号写反

复数乘积实部为ac−bd，若写成加号，复数快速幂计算完全失效，解密无有效数据。

坑 3：密文字节拆分长度错误

密文由 c.re、c.im 分别用(n.bit_length()+7)//8字节存储，拆分时长度不匹配会导致实虚部整数解析错乱。

坑 4：解密后未拼接完整字节再去填充

加密阶段填充串对半分为实、虚部，解密后必须先合并两段字节，再执行unpad；只取单半字节会丢失分隔符，触发断言报错。

坑 5：误以为需要分解模数 n

题目直接输出完整私钥因子 (p,q)，无需 FactorDB、yafu 等分解工具，省去大数分解步骤。

四、完整解密实现代码

python

运行

from collections import namedtuple
import gmpy2

# 高斯整数结构体
Complex = namedtuple("Complex", ["re", "im"])

# 复数模乘法
def complex_mult(c1, c2, modulus):
    return Complex(
        (c1.re * c2.re - c1.im * c2.im) % modulus,
        (c1.re * c2.im + c1.im * c2.re) % modulus,
    )

# 复数二分快速幂
def complex_pow(c, exp, modulus):
    res = Complex(1, 0)
    while exp > 0:
        if exp & 1:
            res = complex_mult(res, c, modulus)
        c = complex_mult(c, c, modulus)
        exp >>= 1
    return res

# 去填充函数
def unpad(data):
    return data.split(b"\x00", 1)[1]

# 补全解密逻辑
def decrypt(priv_key, ciphertext, n, e=65537):
    p, q = priv_key
    # 高斯整数欧拉函数 φ = (p²-p)(q²-q)
    phi = (p*p - p) * (q*q - q)
    d = gmpy2.invert(e, phi)
    # 拆分密文实部、虚部字节
    byte_len = (n.bit_length() + 7) // 8
    c_re_bytes = ciphertext[:byte_len]
    c_im_bytes = ciphertext[byte_len:]
    c_re = int.from_bytes(c_re_bytes, "big")
    c_im = int.from_bytes(c_im_bytes, "big")
    c = Complex(c_re, c_im)
    # 复数模幂解密
    m = complex_pow(c, d, n)
    # 实虚部转回字节并拼接完整填充串
    full_len = len(ciphertext) // 2
    m_r_bytes = m.re.to_bytes(full_len // 2, "big")
    m_i_bytes = m.im.to_bytes(full_len // 2, "big")
    full_pad = m_r_bytes + m_i_bytes
    return unpad(full_pad)

# 题目给出参数
priv = (
    128329415694646850105527417663220454989310213490980740842294900866469518550360977403743209328130516433033852724185671092403884337579882897537139175073013,
    119773890850600188123646882522766760423725010264224559311769920026142724028924588464361802945459257237815241227422748585976629359167921441645714382651911
)
n = 236252683050532196983825794701514768601125614979892312308283919527619033977486749228418695923608569040825653688303374445536392159719426640289893369552258923597180869981053519695297428186215135878525530974780390951763007339139013157234202093279764459949020588291928614938201565110828675907781512603972957429701280916745719458738970910789383870206038035515777549907045905872280803964436193687072794878040018900969772972761081589529671158140590712503582004892067155769362463889653489918914397872964087471457070748108694165412065471040954221707557816986272311750297566993468288899523479556822418109112211944932649
cipher = b'\x00h\xbe\x94\x8c\xcd\xdd\x04\x80\xf4\x9d\t\xd8\x8dO\x08\xf1\xd1\xc4\xb9\xa06\xe7\xe3\xb6\xc3\x01+\xa9\xf2\xb9\xe8\x8d\xe6\xc9\x0c_#\x93\x11\xad\x0f\x90\xd3\x0b6\xb0n\x13\xea~"V6\xdbA&\x87\xfe\xa3C\xcb\x16\xae\xd9\x83\xdbU\xc6\x06\xcd\x9a\x94\xa9\xce\x15{d\x95s\xc2\xfb\x90q\xe7\x02\xa2\x081:_C\xc68\x00y\x7fj4@\xd2\xcdE\x06\x943\xbe\xbcC3\xca\x91\xb4\x0e}C\xab\xff?X\xc30u\x069:Dc\xb5\xdc\x9b0%\x98\xbd\xd9\x13\xc0\x02w\xc5\xe5:\xca\xcf\x0c\xab\xc2\x9b}\xab\xd0\xcc\xbc\x0f\x9e9\t\xf7M\xb3\xed\x86\xb5E\x8b\xbc4\xfaH\x9b4\x1c\xc4\xab\xc0\xaf\x8a5XcX\x19K\xed\x19\xe1\x1c\xd0\x1e\x97c\x9fF:L\x9d\x90p\x99\xb8\xde\xcblM\xb3\x80sSL\xe1\xa4\xd6,\x81\xd6\x9c\xf1\xbb\x9c)\xf03\x155\xc0\xd5v\x13\xd6#\xb7\x19\xdea%\xce<\x1c\xf7\xf2!;\xc1\xd7w\xd1\xc8\x8d/\xaew\xa1\x1d\xc5(\xc8\x9d\x82v\xf6j\x90A,e\xbd\xa7]\x10\x8f\xe5\xe7\x93}:\xdf1~\xec\xd0-o`\r\x96\xe4\x03\xb9E\x9fdF\xc3\xf8L\xa0\xda\xf0E[\xf7\x02\xef|*\x08\x8a5pI&\xa9i\x0fZ\xa8\xb3H\xed\xe8v\xc4H\xff\xdb\xcb\x00\xf1\xae\x9bO\x18\xd5\xd8&p\xf5\xf6\xe9\xf1\x1brs\xc2\r\xceZ\xd0\xb24\x97+\x98b\x0e\xbb\xb8.\x8dT\xe4"\xad\xe4\xa3f\xd0M\xbf\xafX\xbb"[\x99\xdap\xa5\xcfT2Wx\x87M\x7f\x99!>B[Q\x04\xf6\x03\xbc\x84\xf4\xdfj\xdd1^I\x1a\x05\x81\x91\xde9Mf*\x8e\x8d\xe64\xf8\x93\x99&yP\xcd\x00!\x82\xab\xbcy\xed\xf1\x13\xd3\x81\xeaz\xbbP>\x9a2\x8c\x08\x0es\xbc\xa9\xf6\xa3\x8c\xb0\xb9t\xd9?\x06@\xc9\x90\xb7\xa7<\x85\xeb\x1a\x88#\x1c\xc3 \xec\xc7\x94d\x99\xd6\x8e>\x06\xf8Y\xf4\x19\xcaI/hy\x18\x8e\x0e8\xf8\r\xbb\xf6\x11\xb9\x8dCWB6 '

flag = decrypt(priv, cipher, n)
print("最终Flag：", flag.decode())

五、知识点总结

1. 高斯整数 RSA 变种：加密单元为复数 \(a+bi\)，必须自定义复数模乘、二分模幂；
2. 特殊模数欧拉函数：n=(p**2)*(q**2) 在高斯整数环下 φ(n)=(p**2-p)*(q**2-q) ，和标准 RSA 完全区分；
3. 自定义分段填充：随机前缀 + 固定分隔符\x00隔离明文，解密依靠分隔符剥离填充数据；
4. 解题简化条件：题目直接泄露素因子 p,q，无需大数分解，核心难点为复模运算与欧拉函数推导；
5. 通用解题思路：遇到多项式 / 复数 / 矩阵等自定义代数结构 RSA，优先推导对应环的欧拉函数，再求 e 的模逆完成解密。

六、拓展学习方向

1. 高斯整数、艾森斯坦整数上的公钥加密体系；
2. n=(p**k)*(q**k) 模数在无私钥泄露场景下的格基分解攻击；
3. Padding Oracle 填充预言机漏洞攻击；
4. 多项式环 RSA、矩阵模幂类 CTF 密码题。

七、小结

这道高斯整数变种 RSA 是典型的「自定义代数结构」密码题，没有复杂大数分解压力，重点考察选手对 RSA 底层数学、高斯整数运算的理解。做题时切忌直接套用标准 RSA 公式，先分析加密域的乘法群与欧拉函数，再一步步实现复数运算、填充还原即可顺利拿到 flag。