一、题目核心知识点梳理本次 CTF 模平方根题目围绕 Tonelli-Shanks 算法展开核心考察模素数平方根的求解逻辑与算法适用范围。模平方根用于求解同余方程 \(r^2 \equiv a \pmod p\)是椭圆曲线密码、RSA 类 CTF 题的基础运算。题目明确区分两类奇素数的求解方案当素数 \(p \equiv 3 \pmod 4\) 时存在简易幂运算公式而 \(p \equiv 1 \pmod 4\) 无直接计算公式必须依靠 Tonelli-Shanks 迭代算法求解这也是该算法的核心使用场景。在执行 Tonelli-Shanks 前需要先用勒让德符号判断a是否为模p二次剩余若勒让德符号结果为 - 1代表不存在平方根题目无合法解结果为 1 时才能继续计算根。二、Tonelli-Shanks 算法关键限制与密码学意义该算法存在硬性约束仅能处理素数模数无法直接用于合数。如果模数是两个大素数乘积的合数求解模平方根在数学上等价于整数大数分解而大数分解是密码学公认的计算难题不存在高效多项式解法这也是 RSA 加密体系的安全根基。该考点是 CTF 高频出题陷阱一旦遇到合数模数求平方根解题突破口一定是分解模数。算法命名源于两位研究者19 世纪由 Tonelli 提出雏形70 年代 Shanks 重新优化迭代流程因此合并命名。它的核心原理是将\(p-1\)分解为\(Q \cdot 2^S\)通过多轮迭代调整二次剩余幂次最终得到一对平方根r和\(p-r\)两个根互为模p相反数。三、算法主流应用场景椭圆曲线密码 ECC椭圆曲线方程 \(y^2x^3axb\)已知横坐标x求纵坐标y必须调用 Tonelli-Shanks 计算模平方根是密码学最核心的落地场景CTF 密码计算题如本题给出 2048 位超大素数手动实现迭代效率极低专业工具 SageMath 内置封装好的sqrt_mod函数底层直接调用优化后的 Tonelli-Shanks 算法适配千位级大数运算RSA 衍生攻击题型广播攻击、旁路泄露类 RSA 赛题常会用到模平方根作为前置运算。四、本题实战解题流程题目要求对 2048 位大素数p求a的模平方根输出两个根中更小的值。由于超大数运算对精度、迭代效率要求高不推荐手动复现算法使用 SageMath 是最简解题方案。 核心解题代码sage# 读取题目输出文件的a、p数值 with open(output.txt,r) as f: a, p map(Integer, f.readlines()) # 求解全部平方根 roots sqrt_mod(a, p, all_rootsTrue) # 输出较小根作为flag print(min(roots))代码中sqrt_mod原生集成 Tonelli-Shanks 算法all_rootsTrue同时返回正负一组根取最小值即可满足题目提交要求求解 2048 位素数仅需数秒完成。五、安全拓展与竞赛学习总结素数与合数模数下模平方根的计算难度差异直接决定了 RSA 的安全边界。攻击者若能多次获取同一明文的模平方根可借助中国剩余定理分解模数破解私钥大量经典 CTF RSA 题型均基于该漏洞设计。Tonelli-Shanks 是密码学基础工具也是分组密码、非对称密码交叉考点。通过本次题目调研可以总结两点竞赛解题技巧第一区分模数是素数还是合数快速判断解题方向第二处理超大素数模平方根优先使用 Sage 内置函数避免手写迭代产生效率与精度问题。熟练掌握该算法边界与工具用法能够快速拆解椭圆曲线、模运算类 CTF 赛题。