看雪2022 KCTF 春季赛 | 第11题设计思路及解析
他们分别是：
出题团队简介
赛题设计思路
参赛题目：ydmp <<原点磨盘>>
题目答案：lrY1314cXy2920as
现在终于发现怎么应用于加密了，原来的我总是因出题而自我限制自己。方法那就是在每一轮对每一个加数计次，并由总轮次减去某个数的加数次数。(称之为每个数的差省值)，而到最后只需要开放差省值、总轮次和生成的大公倍数充当校验即可。
这时，磨盘本身就是解的对象，问题并未得到转移。但想到按这个方法出题又得重新设计，那就算了吧。
题目设计：
1.数字映射为对应ascii码+175，字符映射为对应ascii码+100(1.式)
2.1.式分两个一组,第一项的平方*第二项+项数的平方(2.式)(由于差异较大，保证了这一步无多解发生)
3.判断奇偶，奇数+2，偶数+1(3.式)
4.磨盘(用以生成一个不能确定的公倍数)
由在3.式项数同乘的基础上分别相加得到此基础上的2.式的公倍数(Q)(不是很规则)并由公倍数作除得到最终值。
5.检验
最终开放首末最终值和其中6项的两两比值的doom后的值作为效验
解题思路：
开放首末项意味着Q和这几位对应的二式可以求出，但是这里一直沿用的是浮点运算，尤其是后边有一段代号doom的函数专门扩大了浮点数产生的误差，所以要解的同时得进行误差分析。
最终由已知关系即可求出2.式的所有项，此时只需要求解出对应的编码再转换一下就解出来了。
赛题解析
本赛题解析由看雪论坛专家 Zuni-W 给出：
第一次参与KCTF，毕竟难得遇到密码题可以试试身手。中间遇到了一些由于在之前其他密码题里的惯性思维带来的坑，但好在吹了个风及时冷静下来，最后拿到了三血，也算是个不错成绩。仅在此记录，希望还能启发其他师傅。
流程分析
本题只有两个主要函数，createkey和cheakkey。主流程里对输入的数据先进行createkey再进行cheakkey。
createkey
一个生成函数createkey，输入为一个字符串，正常输出为一个浮点数数组，异常输出为-1。合法输入长16，合法输入字符为可见字符；合法输出数组长为8。
具体流程分为四大步：
1、字符转整数，将非数字字符的ascii+100，将数字字符的ascii+175.这里导致了本题主要的多解：'0'和'{'，'1'和'|' ，'2'和'}' ，'3'和'~'，这四组字符的映射值一致。所以这一步得到的是一个16长数组，每个位置共有94-4=90种合法状态。
2、数组压缩，将上一步得到的数组每连续两个整数通过
p=lists[2*i]**2*lists[2*i+1]+i**2压缩为一个新的数据，最终得到一个8长的整数数组k1，可以发现这个时候由于偶数位乘了两次，而奇数位只乘了一次，所以二者地位不均等，还有一个位置标记i也会影响会得到的结果，因而共有90*90*8种合法状态。
但需要注意，在具体到每一位只有90*90种状态。同时维护一个k2数组，其是k1数组中对应元素的下一个奇数。本身并没有提供额外变量，主要是为下一步提供部分随机性。
3、维护控制变量Q。Q通过k2数组除去k2[3]外累乘初始化得到，然后根据Q是否整除于k1[j]为Q增加$$\Pi_{m=0}^{j-1}k1[m]$$ （j=0时则为1）,直到Q整除于其中一个变量为止，并退出循环。如果这个循环的过程少于600000次则成功进入下一步，否则返回报错。
4、用Q去依次浮点除k1得到finalkey输出。
cheakkey
输入为一个八个浮点数的数组，输出是否正确。硬编码了四个比对变量，两个浮点rkey和两个整数rmode；还定义了一个变换方法doom，输入两个数，输出一个数，数学表达$doom(x,y)=min(x,y)*abs(x-y)$。
具体对比项目如下：
1、将输入的key[0]和key[-1]与两个浮点rkey对比，相等则通过；
2、取某两个剩下的key相除，然后乘一个10**16进行整数化。这样得到三个mode（mode1和mode3其实是同一个数），然后分别送入doom方法得到两个Mode，与rmode对比，相等则通过。
数据流分析
可以发现数据流大概有个四层结构，第一层是输入，有90种可能，第二层为两个第一层元素组合，最终得到finalkey，有90*90可能，这两层都接受枚举；第三层为mode功能处，是将两个第二层元素组合而成，$90^4$种可能，很明显就超出了枚举的可能性；第四层是doom方法，将两个第三层元素组合，不可能枚举。
除此之外第一层和第三层均为整数，是无误差的，但第二层浮点数（python内浮点数为53位精度，等价于C中的double）有较大误差，本身就带来了不可逆性，所以第一层到第二层，第二层到第三层必须要枚举；但是第三四层由于是先进行了整数处理，所以是精准数据，本身具有理论可逆性，但需要看数据规模观察是否可计算，看数据细节判断是否多解。
解题流程
第一步：
在第一层进行初始化，将字符映射为整数，处理出第一层的合法数据集合s。
In [54]: s=set()...: for i in string.printable:...: p=ord(i)...: if p<=57 and p>=48:...: p=p+175...: else:...: p=p+100...: if p not in s:...: s|={p}...: else:...: print(p,i)...:
第二步：
先从最简单的第二层到第一层的rkey逆向枚举开始。由于这两个值都是绝对值，有一个未知量Q的影响，所以需要先尽可能排除，正好我们有两个rkey，所以可以通过相比消除掉影响，这时数据被提升到第二层，但仍可进行枚举。
In [56]: for i in tqdm(s):...: for l in s:...: for j in s:...: for m in s:...: if (i**2*l+7**2)/(j**2*m)==k0/k1:...: print((i,l),(j,m))...:62%|██████████████████████████▉ | 60/96 [00:24<00:14, 2.47it/s](197, 215) (208, 214)100%|███████████████████████████████████████████| 96/96 [00:39<00:00, 2.44it/s]
于是处理出前两个和最后两个字符对应的值。由于得到了key和对应的rkey，所以原则上我们可以逆推出Q的值，但由于浮点精度受限，我们算出的Q有130bit的精度失准，这就堵死了我们通过整除逆向算法流程单可能性。
第三步：
剩下的就是两个四层结构。注意到第四层是一个纯数学结构，我们可以先写出来：
$$abs(x-y)min(x,y)=m0,abs(x-z)min(x,z)=m1 $$
注意到均为正数，所以我们可以具体拆分为四种可能性：
$$(x-y)y=m0,(x-z)z=m1 $$，$$(y-x)x=m0,(x-z)z=m1 $$，
$$(x-y)y=m0,(z-x)x=m1 $$，$$(y-x)x=m0,(z-x)x=m1 $$，
观察四种情况，发现最后一种有公因子x,因而想到对m0和m1进行gcd，发现
sage: gcd(m0,m1)32
而由于三个数都在10**16数量级附近，所以很明显第四种情况错误。
对前三种情况求解，得到
$x=y+\dfrac{m0}{y},x=\dfrac{m1}{z}+z$
$y=x+\dfrac{m0}{x},x=\dfrac{m1}{z}+z$
$x=y+\dfrac{m0}{y},z=\dfrac{m1}{x}+x$
注意到m0m1是通过整数乘法得到，这时xyz必为相对应的因子，所以我们可以对m0m1进行因式分解，这样就得到了xyz的可能范围：
sage: factor(m0)2^6 * 3^3 * 19 * 19301 * 5651461 * 18765679 * 452548673sage: factor(m1)2^5 * 13 * 29 * 181 * 353 * 641 * 929 * 270532579 * 400359419sage: m0f=[]....: mtf=[2 , 3 , 19 , 19301 , 5651461 , 18765679 , 452548673]....: for i in range(7*4*2^5):....: k=bin(i)[2:].zfill(10)....: l=[int(k[:3],2),int(k[3:5],2),int(k[5],2),int(k[6],2),int(k[7],2),int(....: k[8],2),int(k[9],2)]....: tmp=1....: for u,v in zip(mtf,l):....: tmp*=u^v....: m0f.append(tmp)....:sage: m1f=[]....: mtf=[2 ,13 , 29 , 181 , 353 , 641 , 929 , 270532579 , 400359419]....: for i in range(6*2^8):....: k=bin(i)[2:].zfill(11)....: l=[int(k[:3],2),int(k[3],2),int(k[4],2),int(k[5],2),int(k[6],2),int(k[....: 7],2),int(k[8],2),int(k[9],2),int(k[10],2)]....: tmp=1....: for u,v in zip(mtf,l):....: tmp*=u^v....: m1f.append(tmp)....:sage: len(m0f);len(m1f)8961536
因子个数都在2000以内，可枚举。
对第一种情况进行枚举，得到一组可行解；
sage: xa=set()....: for i in m0f:....: xa|={(m0/i+i)}....:sage: xb=set()....: for i in m1f:....: xb|={(m1/i+i)}....:sage: xa&xb{14109109473780244}
对另外两种情况进行枚举，没有合法解。
sage: for y in m0f:....: x=m0//y+y....: if m1%x==0:....: print(x)....:sage: for z in m1f:....: x=m1//z+z....: if m0%x==0:....: print(x)....:sage:
于是第四层逆向结束，计算这时对应的yz，由于其对称性,yz总有两解，这需要到第三层解决。
第四步：
从第二层到第三层的逻辑主要是浮点数化整，由于精度问题，这步几乎是不可逆的，注意到题目已经进行了相对化处理，尽可能排除了Q的影响，所以与其逆向得到第二步，再尝试逆回去，不如直接一步到位，类比第一步逆回去。
定性分析虽如此，但毕竟Q的失准程度和浮点直接相除带来的误差并不好衡量，所以两种情况都进行一下枚举总是好的。此外，由于yz上一步中是多解，所以也都需要进行判断。
In [63]: for i in tqdm(s):...: for l in s:...: for j in s:...: for m in s:...: if int(((Qi/(i**2*l+1))/(Qi/(j**2*m+36)))*10**16)==x:...: print((i,l),(j,m))...:54%|███████████████████████▎ | 52/96 [00:34<00:28, 1.53it/s](189, 224) (225, 223)100%|███████████████████████████████████████████| 96/96 [01:02<00:00, 1.53it/s]In [61]: for i in tqdm(s):...: for l in s:...: for j in s:...: for m in s:...: if int((((i**2*l+25))/((j**2*m+9)))*10**16) in {y,m0//y} or \...: int(((Qi/(j**2*m+9))/(Qi/(i**2*l+25)))*10**16) in {y,m0//y}:...: print((i,l),(j,m))...:92%|███████████████████████████████████████▍ | 88/96 [02:09<00:11, 1.47s/it](225, 232) (227, 199)100%|███████████████████████████████████████████| 96/96 [02:21<00:00, 1.47s/it]In [58]: for i in tqdm(s):...: for l in s:...: for j in s:...: for m in s:...: if int((((i**2*l+16))/((j**2*m+4)))*10**16) in {z,m1//z} or \...: int(((Qi/(j**2*m+4))/(Qi/(i**2*l+16)))*10**16) in {z,m1//z}:...: print((i,l),(j,m))...:53%|██████████████████████▊ | 51/96 [01:16<01:06, 1.49s/it](188, 221) (226, 224)100%|███████████████████████████████████████████| 96/96 [02:24<00:00, 1.51s/it]
至此逆向了所有合法值。虽然有多解，但是本着数字可读性高于符号的原则，所以，逆向编码后优先得到数字字符，Serial:lrY1314cXy2920as。
题目总结
这个题之所以被定义为密码题，是因为与传统逆向题更重视处理流程相比，这个题在流程上无障碍，其主要考点在于数据信息的变换情况。
流程上被刻意破坏/隐藏的环节其信息为了使程序能正常运行必须始终存在，但数据上的信息如果丢失就是丢失了，无法逆回去，除非可以通过其他方案消去其影响。
而数据的丢失在计算机中无外乎以下几种情况：
数据丢弃，这样的情况是丢失了这个信息的全部，必须通过消去该变量取消其影响；
精度损失，在浮点下每一次乘除运算会明显带来数据的精度损失，虽然损失都是小量，但对于精密计算影响较大。精度的损失可以通过连续情况下的单调性逼近尽可能恢复；
有限域溢出，整数溢出等可以认为是特殊的有限域上的信息损失，这些损失只能通过数学方式处理。
在python中整数乘法原则上不会导致溢出，所以其整数乘法并没有完全损失相乘的两个数的信息，这两个数都是数学上可枚举的，只要实际规模属于可计算的情况，即可以在其他约束帮助下恢复。这也是本题的突破口。希望本题和本篇题解可以给大家带来一些新的思考。
第12题《尊严之战》正在进行中
[广告]赞助链接：
关注数据与安全，洞悉企业级服务市场：https://www.ijiandao.com/
让资讯触达的更精准有趣：https://www.0xu.cn/
关注KnowSafe微信公众号随时掌握互联网精彩
- Yakit，你的网络安全新利器
- Puter 一键部署个人云电脑，百万用户产品开源了！
- 世界上首个域名注册成功 | 历史上的今天
- 欧盟委员会以数据保护为由，要求工作人员卸载TikTok
- 金山回应“WPS 会删除用户本地文件”；腾讯游戏：未成年人暑假只能周五六日打游戏；iOS 16公测版发布|极客头条
- OPPO Watch 2系列：抬腕解锁智慧生活
- 华为胡厚崑：联接智能世界，赋能数字经济
- 迷惑行为赏析：把 jpg 图片加密后卖了 247 万
- 白话科普系列——网站靠什么提升加载速度？
- 诸子云 | 项目：代码审计建设调研报告
- 赛门铁克Symantec和Thawte，Digicert三个SSL证书CA机构有什么关系
- 免费SSL证书与收费SSL证书有什么区别？
