文章总结： 本文解析CISCN2018SM密码学题目，剖析了异或结合AES的加密逻辑。通过发现数据构造的下三角矩阵特性，将问题转化为GF(2)线性方程组，利用前向替换法逐位求解恢复密钥。文中提供了完整的Python解密脚本，成功获取Flag并探讨了线性系统的安全性。 综合评分： 90 文章分类： CTF,逆向分析,漏洞分析
CISCN 2018 – SM 密码学题目深度技术解析
原创
破镜安全 破镜安全
破镜安全
2026年1月18日 08:00 四川
CISCN 2018 – SM 密码学题目深度技术解析
前言
本文将深入分析CISCN 2018中的一道密码学题目SM。这道题目巧妙地结合了异或运算、线性代数和AES加密，展示了线性密码系统的数学特性。通过本文的分析，读者将学习到如何将密码学问题转化为数学问题，并通过算法求解。
题目环境
题目提供了以下文件：
- sm.py：加密脚本源代码
- ps：包含512个大整数的文件
- r：一个大整数
- ef：Base64编码的加密数据
我们的目标是通过分析加密逻辑，从已知数据中恢复密钥，最终解密得到flag。
第一步：分析加密脚本
首先，我们需要仔细阅读sm.py的源代码，理解整个加密流程。
1.1 加密脚本的主函数分析
加密脚本的核心是run()函数，让我们逐行分析：
def run():
choose=getPrime(512)
ps=gen512num()
print "gen over"
bchoose=bin(choose)[2:]
r=0
bchoose = "0"*(512-len(bchoose))+bchoose
for i in range(512):
if bchoose[i]=='1':
r=r^ps[i]
flag=open("flag","r").read()
key=long_to_bytes(int(hashlib.md5(long_to_bytes(choose)).hexdigest(),16))
aes_obj = AES.new(key, AES.MODE_ECB)
ef=aes_obj.encrypt(flag).encode("base64")
open("r", "w").write(str(r))
open("ef","w").write(ef)
gg=""
for p in ps:
gg+=str(p)+"\n"
open("ps","w").write(gg)
从代码中可以看出加密流程：
- 生成一个512位的素数choose作为密钥
- 调用gen512num()生成512个特殊构造的数字，存入ps数组
- 将choose转换为512位的二进制字符串bchoose
- 根据bchoose的每一位，如果是’1’，就将对应的ps[i]异或到r中
- 使用choose的MD5哈希值作为AES密钥，加密flag
- 将r、ef（加密后的flag）、ps数组写入文件
1.2 核心加密逻辑分析
加密的核心在于这段代码：
for i in range(512):
if bchoose[i]=='1':
r=r^ps[i]
这段代码的含义是：
- 遍历choose的512个二进制位
- 如果第i位是1，就将ps[i]异或到r中
- 最终得到的r是若干个ps[i]的异或结果
用数学表达式表示：
r = ps[i₁] ⊕ ps[i₂] ⊕ ... ⊕ ps[iₖ]
其中i₁, i₂, …, iₖ是bchoose中值为1的位置。
这个加密方案的关键问题是：已知ps数组和r，能否反推出choose？
1.3 gen512num函数深度分析
gen512num函数是理解本题的关键，让我们仔细分析：
def gen512num():
order=[]
while len(order)!=512:
tmp=randint(1,512)
if tmp not in order:
order.append(tmp)
ps=[]
for i in range(512):
p=getPrime(512-order[i]+10)
pre=bin(p)[2:][0:(512-order[i])]+"1"
ps.append(int(pre+"0"*(512-len(pre)),2))
return ps
这个函数的执行过程：
第一步：生成随机排列
order=[]
while len(order)!=512:
tmp=randint(1,512)
if tmp not in order:
order.append(tmp)
生成一个包含1到512的随机排列，每个数字出现且仅出现一次。
第二步：构造特殊数字
for i in range(512):
p=getPrime(512-order[i]+10)
pre=bin(p)[2:][0:(512-order[i])]+"1"
ps.append(int(pre+"0"*(512-len(pre)),2))
对于每个ps[i]，构造过程如下：
- 生成一个素数p
- 取p的二进制表示的前(512-order[i])位
- 在后面添加一个”1″
- 再在后面填充0，使总长度达到512位
关键发现：每个ps[i]的二进制结构
让我们用一个具体例子来理解。假设order[0]=5，那么ps[0]的二进制结构是：
位置: 511 510 ... 6 5 4 3 2 1 0
值: x x ... x 1 0 0 0 0 0
从右往左数（从最低位开始），第5位是1，第0到第4位都是0。
这意味着：每个ps[i]都有一个唯一的”最低有效1位”位置，这个位置就是order[i]。
这个特殊构造是解题的关键！
第二步：数学建模与问题转化
2.1 异或运算的数学性质
在深入分析之前，我们需要理解异或运算的基本性质：
- 交换律：a ⊕ b = b ⊕ a
- 结合律：(a ⊕ b) ⊕ c = a ⊕ (b ⊕ c)
- 自反性：a ⊕ a = 0
- 恒等性：a ⊕ 0 = a
- 按位独立：异或运算在每一位上独立进行
第5点非常重要：这意味着我们可以将一个512位的异或问题分解为512个独立的1位问题。
2.2 问题的数学表达
设choose的二进制表示为c = (c₀, c₁, c₂, …, c₅₁₁)，其中cᵢ ∈ {0, 1}
设ps[i]的二进制表示为pᵢ = (pᵢ,₀, pᵢ,₁, …, pᵢ,₅₁₁)
那么r的第j位可以表示为：
rⱼ = c₀·p₀,ⱼ ⊕ c₁·p₁,ⱼ ⊕ ... ⊕ c₅₁₁·p₅₁₁,ⱼ
在GF(2)（二元有限域）上，这等价于：
rⱼ = Σ(cᵢ × pᵢ,ⱼ) mod 2
这实际上是一个线性方程组！我们有512个方程（对应r的512位），512个未知数（对应choose的512位）。
但是，一般的线性方程组可能无解或有多解。这道题为什么可解呢？关键就在于gen512num函数的特殊构造。
2.3 下三角矩阵结构的发现
回忆gen512num的构造：每个ps[i]的最低有效1位位置是唯一的。
如果我们按照最低有效1位的位置对ps数组重新排序，会发生什么？
假设我们将ps数组按照最低有效1位的位置从小到大排序，得到新的数组P。那么：
- P[0]的最低有效1位在第0位，第0位是1，第0位之前（右边）没有位
- P[1]的最低有效1位在第1位，第1位是1，第0位是0
- P[2]的最低有效1位在第2位，第2位是1，第0-1位都是0
- …
- P[i]的最低有效1位在第i位，第i位是1，第0到i-1位都是0
这形成了一个下三角矩阵结构！用矩阵表示：
位0 位1 位2 ... 位i ...
P[0]: 1 ? ? ... ? ...
P[1]: 0 1 ? ... ? ...
P[2]: 0 0 1 ... ? ...
...
P[i]: 0 0 0 ... 1 ...
这个矩阵的对角线全是1，对角线下方全是0，这就是下三角矩阵的特征。
第三步：推导解题算法
3.1 为什么下三角矩阵可以逐位求解
对于下三角矩阵，我们可以使用前向替换法（Forward Substitution）求解。
考虑第i位的方程：
rᵢ = C[0]·P[0][i] ⊕ C[1]·P[1][i] ⊕ ... ⊕ C[511]·P[511][i]
由于下三角矩阵的性质：
- 当j > i时，P[j][i] = 0（因为P[j]的第0到j-1位都是0）
- 当j = i时，P[i][i] = 1（这是标志位）
- 当j < i时，P[j][i]可能是0或1
因此方程可以简化为：
rᵢ = C[0]·P[0][i] ⊕ ... ⊕ C[i-1]·P[i-1][i] ⊕ C[i]·1
移项得到：
C[i] = rᵢ ⊕ (C[0]·P[0][i] ⊕ ... ⊕ C[i-1]·P[i-1][i])
这就是递推公式！当我们求解第i位时，第0到i-1位已经求解完毕，可以直接代入计算。
3.2 算法步骤总结
基于以上分析，我们的解题算法如下：
步骤1：读取ps数组，将每个数字转换为二进制并反转（让最低位在前）
步骤2：找到每个ps[i]的最低有效1位位置，按此位置排序
步骤3：读取r值，同样转换为二进制并反转
步骤4：从第0位开始，逐位求解choose的每一位
步骤5：将排序后的结果恢复到原始顺序
步骤6：构建完整的choose值，用于解密flag
第四步：实现解密脚本
4.1 数据预处理函数
首先定义一个辅助函数，用于将大整数转换为二进制并反转：
def tobinrev(str_num):
"""将数字字符串转换为二进制并反转"""
return bin(int(str_num))[2:][::-1]
这个函数的作用：
- 将字符串形式的大整数转换为整数
- 转换为二进制字符串（去掉’0b’前缀）
- 反转字符串，使最低位在最前面
4.2 读取并排序ps数组
dic = {}
dic_value = [0 for i in range(512)]
with open("ps", "r") as f:
lines = f.readlines()
for i in range(512):
line = lines[i].strip()
bin_rev = tobinrev(line)
index = bin_rev.find('1')
dic[index] = i
dic_value[index] = bin_rev
这段代码的作用：
dic字典：存储”最低有效1位位置”到”原始索引”的映射dic_value数组：按位置排序后的二进制字符串bin_rev.find('1')：找到第一个1的位置，即最低有效1位- 通过这种方式，我们实现了按最低有效1位位置的排序
4.3 处理r值
r = open("r", "r").read().strip()
r_rev = tobinrev(r)
将r值读取并转换为反转的二进制字符串，便于后续逐位处理。
4.4 核心算法：逐位求解choose
tmp_result = [0 for i in range(512)]
for i in range(512):
tmp = 0
for j in range(i):
tmp ^= (int(dic_value[j][i]) * tmp_result[j])
tmp_result[i] = int(r_rev[i]) ^ tmp
这段代码实现了前向替换算法：
外层循环：遍历第0到511位
内层循环：计算已知部分的贡献
dic_value[j][i]：排序后第j个数字的第i位tmp_result[j]：已经求解出的choose的第j位- 两者相乘再异或，累积到tmp中
求解当前位：tmp_result[i] = int(r_rev[i]) ^ tmp
- r的第i位异或掉已知部分的贡献，得到choose的第i位
4.5 恢复原始顺序
ans = [0 for i in range(512)]
for i in range(512):
ans[dic[i]] = tmp_result[i]
将排序后的结果映射回原始ps数组的顺序。
4.6 构建choose值
choose = ""
for i in ans:
choose += str(i)
choose = int(choose, 2)
将512个二进制位拼接成字符串，然后转换为整数。
4.7 解密flag
import base64
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes
import hashlib
flag_encrypted = open("ef", "r").read().strip()
key = long_to_bytes(int(hashlib.md5(long_to_bytes(choose)).hexdigest(), 16))
aes_obj = AES.new(key, AES.MODE_ECB)
ef = aes_obj.decrypt(base64.b64decode(flag_encrypted))
print("Flag:", ef.decode())
解密步骤：
- 读取Base64编码的加密flag
- 计算choose的MD5哈希值，转换为16字节的AES密钥
- 使用AES ECB模式解密
- 输出解密后的flag
4.8 完整解密脚本
将以上所有步骤整合，得到完整的解密脚本：
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes
import hashlib
import base64
def tobinrev(str_num):
return bin(int(str_num))[2:][::-1]
# 步骤1: 读取并排序ps数组
dic = {}
dic_value = [0 for i in range(512)]
with open("ps", "r") as f:
lines = f.readlines()
for i in range(512):
line = lines[i].strip()
bin_rev = tobinrev(line)
index = bin_rev.find('1')
dic[index] = i
dic_value[index] = bin_rev
# 步骤2: 处理r值
r = open("r", "r").read().strip()
r_rev = tobinrev(r)
# 步骤3: 逐位求解choose
tmp_result = [0 for i in range(512)]
for i in range(512):
tmp = 0
for j in range(i):
tmp ^= (int(dic_value[j][i]) * tmp_result[j])
tmp_result[i] = int(r_rev[i]) ^ tmp
# 步骤4: 恢复原始顺序
ans = [0 for i in range(512)]
for i in range(512):
ans[dic[i]] = tmp_result[i]
# 步骤5: 构建choose值
choose = ""
for i in ans:
choose += str(i)
choose = int(choose, 2)
# 步骤6: 解密flag
flag_encrypted = open("ef", "r").read().strip()
key = long_to_bytes(int(hashlib.md5(long_to_bytes(choose)).hexdigest(), 16))
aes_obj = AES.new(key, AES.MODE_ECB)
ef = aes_obj.decrypt(base64.b64decode(flag_encrypted))
print("Flag:", ef.decode())
第五步：运行验证
运行解密脚本后，成功获得结果：
Flag: flag{shemir_alotof_in_wctf_fun!}
恢复的choose值为：
0xd9acf82cc8d757b5b11b851079a6b65f7d04d6ba592cb24381f4cf7c11e58404ba1fdbda4424067facabb7ca3a00ae57c8ecf613a79be6974628cbc97ae68e71
这是一个512位的大整数，正是加密时使用的密钥。
第六步：技术原理深度剖析
6.1 为什么需要反转二进制表示
在原始加密逻辑中，choose的二进制是从左到右（高位到低位）的标准形式。但gen512num生成的ps数组中，每个数字的”标志位”是从右往左计数的（最低有效位）。
为了统一处理，我们将所有数字都反转：
- 反转后，索引0对应最低位，索引511对应最高位
- 这样”第i个1″就对应反转后的第i个位置
- 简化了索引计算和逻辑处理
6.2 时间复杂度分析
本解法的时间复杂度为O(n²)，其中n=512：
- 外层循环遍历512位
- 内层循环对于第i位需要计算i次异或
- 总计算次数约为512×512/2 = 131,072次
这是一个非常高效的解法。
6.3 GF(2)有限域上的线性方程组
本题本质上是在GF(2)（二元有限域）上求解线性方程组。在GF(2)中：
- 加法就是异或运算
- 乘法就是与运算
- 只有0和1两个元素
线性方程组的矩阵形式为：
P × C = R
其中P是512×512的系数矩阵，C是choose向量，R是r向量。
由于P是下三角矩阵且对角线全为1，所以P在GF(2)上可逆，方程组有唯一解。
第七步：安全性分析
7.1 线性加密系统的脆弱性
本题展示了基于线性运算（异或）的加密系统的脆弱性：
- 可建模性：如果加密系统可以被建模为线性方程组，通常可以通过数学方法求解
- 信息泄露：题目泄露了ps数组和r值，这些信息足以完全恢复密钥
- 密钥强度无效：虽然choose是512位素数，但由于方案的线性特性，密钥强度并不能保证安全
7.2 与Shamir秘密共享的关联
题目名称”SM”以及flag中的”shemir”暗示了与Shamir秘密共享方案的关联。
Shamir秘密共享是一种(k,n)门限方案，可以将秘密分成n份，需要至少k份才能恢复。本题的构造与Shamir方案有相似之处：
- 都涉及线性组合
- 都基于线性代数原理
- 都需要足够的信息才能恢复秘密
第八步：关键知识点总结
8.1 核心技术点
本题涉及的核心技术点包括：
- 异或运算的线性性质：在GF(2)域上，异或运算具有线性特性
- 下三角矩阵求解：利用前向替换法逐位求解
- 二进制位运算：反转、索引、位操作等技巧
- 线性方程组求解：将密码问题转化为数学问题
- AES加密应用：标准对称加密算法的使用
8.2 解题思路回顾
解题的关键步骤：
- 分析gen512num函数，发现每个数字的最低有效1位位置唯一
- 将ps数组按最低有效1位位置排序，形成下三角矩阵
- 利用递推关系从低位到高位逐位求解choose
- 恢复原始顺序，构建完整的choose值
- 使用choose的MD5哈希解密AES密文
第九步：学习建议
9.1 数学基础的重要性
密码学CTF题目往往需要扎实的数学基础：
- 线性代数：矩阵、向量、线性方程组
- 数论：模运算、素数、欧几里得算法
- 抽象代数：群、环、域的概念
9.2 解题技巧
- 观察数据特征：仔细分析题目给出的数据结构
- 从简单情况入手：先考虑小规模问题，理解原理后再推广
- 数学建模：将实际问题抽象为数学模型
- 编写清晰代码：结构清晰，便于调试和验证
9.3 相关工具和资源
推荐的工具和库：
- PyCryptodome：Python密码学库
- SageMath：强大的数学计算软件
- gmpy2：高性能大整数运算库
总结
本文深入分析了CISCN 2018的SM密码学题目，从加密原理到解密实现进行了全面讲解。
这道题目的核心价值在于：
- 展示了如何将密码问题转化为数学问题
- 演示了线性加密系统的分析方法
- 揭示了线性密码系统的安全隐患
通过本题的学习，我们不仅掌握了一种解题方法，更重要的是培养了分析问题、建模问题、解决问题的能力。
希望本文能够帮助读者理解线性密码系统的分析方法，提升密码学CTF的解题能力。
题目来源：CISCN 2018 难度等级：中等 核心知识点：异或运算、线性代数、下三角矩阵、AES加密、GF(2)有限域
免责声明：
本文所载程序、技术方法仅面向合法合规的安全研究与教学场景，旨在提升网络安全防护能力，具有明确的技术研究属性。
任何单位或个人未经授权，将本文内容用于攻击、破坏等非法用途的，由此引发的全部法律责任、民事赔偿及连带责任，均由行为人独立承担，本站不承担任何连带责任。
本站内容均为技术交流与知识分享目的发布，若存在版权侵权或其他异议，请通过邮件联系处理，具体联系方式可点击页面上方的联系我。
本文转载自：破镜安全 破镜安全 破镜安全《CISCN 2018 – SM 密码学题目深度技术解析》
版权声明
本站仅做备份收录，仅供研究与教学参考之用。
读者将信息用于其他用途的，全部法律及连带责任由读者自行承担，本站不承担任何责任。
评论