CTF 基础密码学：模素数二次剩余解题 Writeup

题目完整复述

理论背景

模素数 p 二次剩余定义： 若存在整数 a 满足 \(a^2 \equiv x \pmod p\)，则 x 为模 p二次剩余；不存在则为二次非剩余。 若 a 是 x 的平方根，则 \(p-a\)（即 \(-a \pmod p\)）也是平方根，一组根一大一小，取更小值作为答案。

已知条件： 模数素数 \(p=29\) 待判断数字列表：\(\text{ints} = [14, 6, 11]\) 题干说明列表内包含两个二次非剩余、一个二次剩余。

任务：

1. 找出列表中唯一的二次剩余；
2. 求出该数模 29 的一对平方根；
3. 输出两个根中更小的数字作为 flag。

解题思路

1. 暴力遍历 \(a \in [1,28]\)，计算 \(a^2 \bmod 29\)，建立「二次剩余值→平方根」映射表；
2. 依次判断 14、6、11 是否存在于映射表中，筛选出唯一二次剩余；
3. 取出该剩余对应的两个平方根，对比大小取较小值。

代码实现（Python）

运行结果与推导

执行代码输出：

手动验算：

1. \(8^2 = 64\)，\(64 \bmod 29 = 6\)；
2. 另一根：\(-8 \equiv 29-8 = 21 \pmod{29}\)，\(21^2 = 441\)，\(441 \bmod 29 = 6\)；
3. 对比 8 和 21，更小值为 8。

验证另外两个数字（非二次剩余）：

• 14：不存在任何 \(a \in [1,28]\) 满足 \(a^2 \equiv 14 \pmod{29}\)；
• 11：不存在任何 \(a \in [1,28]\) 满足 \(a^2 \equiv 11 \pmod{29}\)； 完全符合题干 “两非剩余一剩余” 的描述。

最终答案

flag：8

拓展知识点

1. 素数模 p 的有限域乘法群 \(\mathbb{F}_p^*\) 有 \(p-1\) 个元素，恰好一半是二次剩余、一半是非剩余；
2. 任意二次剩余必然成对出现平方根 a 和 \(p-a\)，二者大小不同；
3. 二次剩余是密码学 Rabin 加密、椭圆曲线、离散对数题型的基础前置知识。