团队名称： 金左手
参赛题目： 一尺之棰
题目答案： 504964774D526B756F467A705C4D654B7645587746634A7A75505F757A75776C
题目类型： Window平台CrackMe
系统需求： WIN10/64
成功提示： Good job!
设计说明
早在1948年，香农就提出将信源符号依其出现的概率降序排序，用符号序列累计概率的二进值作为对信源的编码，并从理论上论证了它的优越性。1960年，Peter Elias提出了算术编码的概念，Elias没有公布他的发现，因为他知道算术编码在数学上虽然成 立，但不可能在实际中实现。1976年，R. Pasco和J. Rissanen分别用定长的寄存器实现了有限精度的算术编码。1979年Rissanen和G. G. Langdon一起将算术编码系统化，并于1981年实现了二进制编码。1987年Witten等人发表了一个实用的算术编码程序，即CACM87（后用于H.263视频压缩标准）。IBM公司也发表过著名的Q-编码器（后用于JPEG和JBIG图像压缩标准）。从此，算术编码迅速得到了 广泛的注意。
算术编码的基本原理是将编码的消息表示成实数0和1之间的一个间隔，消息越长，编码表示它的间隔就越小，表示这一间隔所需的二进制位就越多。算术编码用到两个基本的参数：符号的概率和它的编码间隔。信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在0到1之间。编码过程中的间隔决定了符号压缩后的输出。
算术编码可以是静态的或者自适应的。在静态算术编码中，信源符号的概率是固定的。在自适应算术编码中，信源符号的概率根据编码时符号出现的频繁程度动态地进行修改，在编码期间估算信源符号概率的过程叫做建模。
（上面描述基本摘自参考资料）
在本题目中，利用了算术编码的编码原理，不考虑压缩率，所以输入的key经过16轮的编码后会越来越大。编码过程就是对一个小数区间无限细分，小数点后的位数或者是精度不断增加的过程。
考虑到直接常规编码的话题目难度太低，所以故意增加几处难点：
a.把浮点运算的舍入模式ROUND_NEAREST修改为ROUND_UP，使得误差积累到一定程度会产生不同的运算结果；
b.做了一个简单的宏把浮点数存储前做些移位交换，读出后再还原，这个也不算是障碍，ida下F5后会一览无余，虽然把整个表的257项都计算了，实际每个字符只用到其中一项；
c.频度自适应略作修改，每轮权重因子定长+1
破解思路
1.程序不大，结构简单，都在一个main函数里，ida里F5一下，基本和源码差不太多了
2.可以还原整理出代码，都在main函数里，也就100多行，自己编译模拟计算过程，大概可以猜出是个压缩编码算法，熟悉的话也能确定是属于算数编码，然后跟踪运算流程，对比可以发现，自己编译的出程序和题目程序在运算过程中存会在很小的误差，这里可以思考...？？？如果想到浮点运算的默认舍入模式，就可以几种 都尝试对比一下就能找到一种匹配的，或者你能发现下面一条提到的暗桩。
3.暗桩位置在printf内部有几行被patch过：
0000000140002ED1 push rax
0000000140002ED2 stmxcsr dword ptr [rsp]
0000000140002ED6 pop rax
0000000140002ED7 and ah, 0DFh
0000000140002EDA or ah, 40h
0000000140002EDD push rax
0000000140002EDE ldmxcsr dword ptr [rsp]
0000000140002EE2 pop rax
查询SSE指令集得知，这是把浮点运算的默认舍入模式ROUND_NEAREST修改为ROUND_UP
4.正确设置浮点
舍入模式之后，运算结果可以完全匹配了
不用汇编的正常调用方式可以这样：
#include <float.h>
_set_controlfp(RC_UP,MCW_RC);
5.求逆：
这个编码有个特点，以字节为单位往后进行的，所以每个字节可以穷举，对浮点值区间进行匹配，得到正确输入，其实只有256个分片的升序区间总是要做遍历的，不用穷举（而用二分法？）的话也好不了太多吧
设计说明
早在1948年，香农就提出将信源符号依其出现的概率降序排序，用符号序列累计概率的二进值作为对信源的编码，并从理论上论证了它的优越性。1960年，Peter Elias提出了算术编码的概念，Elias没有公布他的发现，因为他知道算术编码在数学上虽然成 立，但不可能在实际中实现。1976年，R. Pasco和J. Rissanen分别用定长的寄存器实现了有限精度的算术编码。1979年Rissanen和G. G. Langdon一起将算术编码系统化，并于1981年实现了二进制编码。1987年Witten等人发表了一个实用的算术编码程序，即CACM87（后用于H.263视频压缩标准）。IBM公司也发表过著名的Q-编码器（后用于JPEG和JBIG图像压缩标准）。从此，算术编码迅速得到了 广泛的注意。
算术编码的基本原理是将编码的消息表示成实数0和1之间的一个间隔，消息越长，编码表示它的间隔就越小，表示这一间隔所需的二进制位就越多。算术编码用到两个基本的参数：符号的概率和它的编码间隔。信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在0到1之间。编码过程中的间隔决定了符号压缩后的输出。
算术编码可以是静态的或者自适应的。在静态算术编码中，信源符号的概率是固定的。在自适应算术编码中，信源符号的概率根据编码时符号出现的频繁程度动态地进行修改，在编码期间估算信源符号概率的过程叫做建模。
（上面描述基本摘自参考资料）
在本题目中，利用了算术编码的编码原理，不考虑压缩率，所以输入的key经过16轮的编码后会越来越大。编码过程就是对一个小数区间无限细分，小数点后的位数或者是精度不断增加的过程。
考虑到直接常规编码的话题目难度太低，所以故意增加几处难点：
a.把浮点运算的舍入模式ROUND_NEAREST修改为ROUND_UP，使得误差积累到一定程度会产生不同的运算结果；
b.做了一个简单的宏把浮点数存储前做些移位交换，读出后再还原，这个也不算是障碍，ida下F5后会一览无余，虽然把整个表的257项都计算了，实际每个字符只用到其中一项；
c.频度自适应略作修改，每轮权重因子定长+1
[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入！
最后于 2020-4-27 08:28
被ccfer编辑
，原因： 添加Julia源码
