文章总结： 文档附带战队招新信息，核心解析2026年hgame中babyrsa题目解法。针对RSA加密中明文m大于模数n的情形，作者提出利用已知明文前后缀将问题转化为隐数问题HNP，并构造格运用LLL算法求解未知部分。文章包含详细推导与完整SageMath脚本，技术含量高且实战性强。 综合评分： 90 文章分类： CTF,解决方案,实战经验

Crypto之M>N的特殊rsa

yumhaoxouhymxmuy yumhaoxouhymxmuy

OnePanda-Sec

2026年3月13日 11:05 浙江

招新

OnePanda-Sec

-招新说明-

**招新要求

· 热爱网络安全，喜欢CTF

· 拥有CTF比赛经验，有较好比赛成绩的

· 乐于奉献、热爱分享，愿意提升   自己同时帮助他人

· 时间允许参加各类赛事，服从战队管理与安排

· 各类比赛获奖者、能力出众者视情况考量

· 未参与其他高校联队

· 大一同学视情况放宽资历要求**

联系方式

发送简历于邮箱

· 简历邮箱：[email protected]

聘

题目信息：

题目名称：babyrsa（来自2026年hgame）

题目类型：Crypto

附件：task.py

Task.py:rsa的加密过程，给出了flag的格式，以及flag的大小

第一步：阅读代码

k = randint(30, 40)str = string.digits + string.ascii_letters + "_@"flag = b"VIDAR{" + "".join([choice(str) for i in range(k)]).encode() + b"}"

1.生成一个30 到 40 之间的随机整数 k，用来指定flag 中 VIDAR{} 中间部分的字符长度。

2.拼接字符集：包含数字（0-9）、大小写字母（a-z/A-Z）、下划线 _ 和@，后续用来随机生成flag 内容。

3.构造 flag 字节串：

choice(str)：从字符集str 中随机选一个字符；

[choice(str) for i in range(k)]：生成k 个随机字符的列表；

“”.join(…)：将列表转为字符串；

.encode()：将字符串转为字节串（如”123″ → b”123″）；

最终flag 格式为 b”VIDAR{随机字符}”，比如b”VIDAR{8a9_7B@89s…}”（中间30-40 个随机字符）。

可以得出flag是37-47个字符，约为296-376位

p = getPrime(120)q = getPrime(120)n = p * q

n为240位

第二步：分析给的信息

因为在加密或者解密的过程中会modN，那么m大于以后就会减掉k倍的N

那么对于解决这道题的关键就是找到m1，然后通过m//n（k)*n+m1就可以得到flag

而m1的值话则可以通过这样得到：

加密：c=m^e%n → 根据模运算性质，等价于 c = (m1)^e % n

解密：c^d %n=m

而在m>n，则

c^d % n = (m1^e % n)^d % n = m1^(e×d) % n

当0 ≤ m1 < n 时，m1^(e×d) ≡ m1 (mod n)（这是欧拉定理的推论）；

因此最终解密结果是：c^d % n = m1 = m % n。

下面我写了一个模拟加密过程的，给大家演示

from Crypto.Util.number import *from gmpy2 import *from random import *import stringk = randint(30, 40)str = string.digits + string.ascii_letters + "_@"flag = b"VIDAR{" + "".join([choice(str) for i in range(k)]).encode() + b"}"p = getPrime(120)q = getPrime(120)n = p * qe = 65537phi = (p-1)*(q-1)d = pow(e,-1,phi)m = bytes_to_long(flag)print("m=",m)c = pow(m, e, n)print(f'c = {c}')print(f'p = {p}')print(f'q = {q}')print("n=",n)print("d=",d)

结果：

m = 47182387137031888683193786631811481680018945054280589140335017056651965465398746556476496557542234493c = 271530001392968364132741416971348442690719532783738504885895356571604188p = 1105098843875526305577012916655789761q = 1003359477327253282628279227971265709n = 1108811398385899951350476094717464147948849489769168722713438298172605549d = 356835698969391578405067233985169237223548379331274138820991356400646913e = 65537 m1 = pow(c,d,n)print(m1)m1 = 973962589215066063395061466358659236539972501198758474963830687022499469print(m1==m%n)print(m//n)print(m//n*n+m1==m)

这是一个简单的m>n的展示过程

第三步：回到题目解决问题

我们由于 k 的范围很大，导致m//n的取值范围过大，我们没办法用上面的那办法去爆破k的直接，那么我们就需要用已知明文来求解这道题。

我们一直前缀和后缀，那么只需知道中间的就可以求解了，这就可以转化为一个隐数问题，利用 LLL 算法求解。

设A为前缀B为后缀C为中间未知部分，L为中间部分的比特长度，则明文结构为:

m=A⋅2^(L+8)+C⋅2^8+B

其中2^(L+8) = 把前缀往前挪多少位，让它刚好放在整个 flag 最前面的位置。

由于m≡m1(modn)，代入明文结构得：

A⋅2^(L+8)+C⋅2^8+B = m1(mod n)

整理后可解出未知部分C 的同余关系(2^8=256)：

C=(m1−A⋅2^(L+8)−B)⋅256^−1(mod n)

到这里，我们得到了一个非常关键的式子：

C≡T(modn)

其中T=(m1−A⋅2^(L+8)−B)⋅256^−1modn

这个式子告诉我们一件事：

未知的中间部分C，在模 n 下等于一个我们完全能算出来的数 Target。

但问题还没结束：满足C ≡ Target (mod n) 的 C 有无数个，比如：

C = Target

C = Target + n

C = Target + 2n

我们怎么知道哪一个才是真正的flag 中间部分？

关键：C 不是随便的大数

C 是一串可见字符：数字、大小写字母、_、@

每一个字符都是1 字节，也就是 0~255 之间的一个小数字。

如果把C 拆成一个个字节：

C=c0·256^(k−1)+c1·256^(k−2)+……+ck−1

这个公式就就相当于123的十进制：

123 = 1×10² + 2×10¹ + 3×10⁰

那么每一个ci都很小（只是一个 ASCII 码），而不是像 n 那样几百位的超大数。

这就是为什么要用LLL 格基算法

我们的问题变成：

在所有满足c0·256k−1+c1·256k−2+……+ck−1=Target(modn)的解里面，

找到一组c0～cK-1，每一个都很小（是合法字符）。

这种“在同余方程里找一组很小的未知数” 的问题，就是标准的 隐数问题，正是 LLL 格基规约算法 最擅长解决的。

下面就是构造格M的问题： M = [1   0   …  0  C0·W   80

0 1   …  0  C1·W   80

⋮⋮ ⋱ ⋮  ⋮

0 0   …  1  CK-1·W  80

0 0   …  0  n·W     0

0 0   …  0  T·W     1]

对矩阵 M 进行 LLL 规约，寻找最短向量。如果构造正确，最短向量的前 k 个分量即为 ci − 80 的差值，从而恢复出 C。

最终脚本:

from sage.all import *import string# 题目数据encrypted_flag = 451420045234442273941376910979916645887835448913611695130061067762180161prime1 = 722243413239346736518453990676052563prime2 = 777452004761824304315754169245494387encryption_exp = 65537from sage.all import *import string# 题目数据encrypted_flag = 451420045234442273941376910979916645887835448913611695130061067762180161prime1 = 722243413239346736518453990676052563prime2 = 777452004761824304315754169245494387encryption_exp = 65537# 计算模数和私钥modulus = prime1 * prime2phi = (prime1 - 1) * (prime2 - 1)private_key = inverse_mod(encryption_exp, phi)# 解密得到数字形式的明文decrypted_num = power_mod(encrypted_flag, private_key, modulus)# 定义合法字符allowed_chars = string.digits + string.ascii_letters + "_@"char_codes = {ord(c) for c in allowed_chars}def recover_flag_from_hnp(key_length):   flag_prefix = b"VIDAR{"   flag_suffix = b"}"   # 计算需要处理的比特数   total_byte_len = key_length + len(flag_suffix)   bit_shift = total_byte_len * 8      # 构建前缀和后缀的数值表示   prefix_val = Integer(int.from_bytes(flag_prefix, 'big')) * (Integer(2)**bit_shift)   suffix_val = Integer(int.from_bytes(flag_suffix, 'big'))      # 计算目标值（中间部分）   middle_val = (decrypted_num - prefix_val - suffix_val) % modulus   inv_256 = inverse_mod(256, modulus)   target_val = (middle_val * inv_256) % modulus      # 构建格   lattice_dim = key_length + 2   # 创建零矩阵   lattice = matrix(ZZ, lattice_dim, lattice_dim)      # 使用nbits()获取位数   weight_factor = 2 ** (modulus.nbits() + 10)ascii_mean = 80      # 填充变量部分   for idx in range(key_length):       lattice[idx, idx] = 1       power_factor = power_mod(256, key_length - 1 - idx, modulus)       lattice[idx, key_length] = power_factor * weight_factor       lattice[key_length + 1, idx] = ascii_mean          # 模数约束行   lattice[key_length, key_length] = modulus * weight_factor      # 目标值行   lattice[key_length + 1, key_length] = target_val * weight_factor   lattice[key_length + 1, key_length + 1] = 1      # 应用LLL算法   reduced_basis = lattice.LLL()      # 检查每一行寻找有效解   for basis_vector in reduced_basis:       if abs(basis_vector[key_length + 1]) != 1:           continue                  multiplier = -basis_vector[key_length + 1]              candidate_chars = []       is_valid = True              for idx in range(key_length):           char_val = basis_vector[idx] * multiplier + ascii_mean           # 转换为Python整数进行比较           char_val_int = int(char_val)           if char_val_int not in char_codes:               is_valid = False               break           candidate_chars.append(char_val_int)                  if is_valid:           return flag_prefix + bytes(candidate_chars) + flag_suffix   return Nonefor possible_length in range(30, 41):    result = recover_flag_from_hnp(possible_length)    if result is not None:        print(f"成功恢复Flag: {result.decode('utf-8')}")        breakelse:    print("未找到有效的Flag")

OnePandaSec团队交流群，欢迎网络安全爱好者加入

免责声明：

本文所载程序、技术方法仅面向合法合规的安全研究与教学场景，旨在提升网络安全防护能力，具有明确的技术研究属性。

任何单位或个人未经授权，将本文内容用于攻击、破坏等非法用途的，由此引发的全部法律责任、民事赔偿及连带责任，均由行为人独立承担，本站不承担任何连带责任。

本站内容均为技术交流与知识分享目的发布，若存在版权侵权或其他异议，请通过邮件联系处理，具体联系方式可点击页面上方的联系我。

本文转载自：OnePanda-Sec yumhaoxouhymxmuy yumhaoxouhymxmuy《Crypto之M>N的特殊rsa》