蓝桥杯Crypto练习题

Author Avatar
Timerain
发表：2024-04-15 19:26:00
修改：2024-04-15 20:56:44

遇到的离谱题目，本来以为不会难，没想到5555

差分曼彻斯特编码

已知ID为0x8893CA58的温度传感器的未解码报文为：3EAAAAA56A69AA55A95995A569AA95565556

此时有另一个相同型号的传感器，其未解码报文为：3EAAAAA56A69AA556A965A5999596AA95656

请解出其ID，提交flag{hex（不含0x）}。

最开始根本想不到的解题方式

首先详细分析曼彻斯特编码（Manchester Encoding）

曼彻斯特编码是一种广泛使用的编码方案，它将时钟信息嵌入到传输信号中（自含时钟）。

它通过确保在每个比特时间中间有一个转换（高到低或低到高）来实现这一点，使接收器很容易从传入的比特流中识别时钟信号并保持与传输信号的同步。

曼彻斯特编码有两种标准：G.E. Thomas Convention 和 IEEE 802.3 Convention

曼彻斯特编码G.E. Thomas Convention如图所示

在G.E. Thomas Convention的曼彻斯特编码中，在一个时钟周期T的T/2位置会发生跳变，电压由低到高的跳变被定义成二进制的0，电压由高到低的跳变被定义成二进制的1。

曼彻斯特编码IEEE 802.3 Convention
IEEE 802.3 Convention曼彻斯特编码对于0和1的定义如图所示。

在IEEE 802.3 Convention的曼彻斯特编码中，在一个时钟周期T的T/2位置会发生跳变，电压由高到低的跳变被定义成二进制的0，电压由低到高的跳变被定义成二进制的1。

然后了解一下差分曼彻斯特编码

差分曼彻斯特编码（Differential Manchester Encoding）是一种差分编码，使用比特时间开始位置是否发生跳变来表示二进制0或1（无跳变为1，有跳变为0）。不需要知道发送信号的极性，因为信息不是保存在电压的实际值中，而是保存在它们的变化中。被用于IEEE 802.5令牌环局域网。
和曼彻斯特编码一样，在一个时钟周期T的T/2位置一定会发生跳变。但是与曼彻斯特编码不同的是这个跳变不再代表0或1，而只起到一个同步时钟的作用。
在一个比特时间开始的时候跟前一个比特时间比，如果没有发生跳变就代表1，发生了跳变就代表0。

简单而言，就是

  1. 曼彻斯特码： 从低到高（趋势）表示 1 或者 0；（图中，从高到低表示 1，从低到高表示 0）

  2. 差分曼彻斯特码：在每个时钟周期的起始处（虚线处）有跳变表示 0；无跳变则表示1。或者说遇到 0 的时候，在起始处发生跳变。

EXP：

可以发现给出的编码一共有364位，因为四位代表1个，所以对应的解码应该为36位，但是实际上对应的id只有84位，推测有对应的取位方法，所以先根据样例进行破解。先将编码转化为2进制，然后再根据差分曼切斯特编码规则，如果前面跳变为0，不跳变为1.

from Crypto.Util.number import *

id1 = 0x8893CA58
msg = 0x3EAAAAA56A69AA556A965A5999596AA95656
s = bin(msg)[2:] 
print(s)

r = ""
for i in range(len(s)//2):  
    c = s[i*2]
    if c == s[i*2 - 1]:
        r += '1'
    else:
        r += '0'

print(hex(int(r, 2)).upper())

flag{8845ABF3}

SimpleMath

Simple个p

题目代码：

from Crypto.Util.number import *

from hashlib import md5

flag = "xxx"

assert len(flag) == 15

pad = bytes_to_long(md5(flag).digest())

hack = 0

for char in flag:

hack *= ord(char)

hack += pad

print hack

# hack = 280098481791453837177137197730537158171743673148935867304957882116

# flag = "flag{" + flag + "}"

程序逻辑如下：首先计算flag的MD5哈希值，然后将结果（字节串）转换为一个长整数，存储在变量pad中。hack = 0：初始化变量hack为0。

  • 在循环中，对于flag中的每个字符char：

    • hack *= ord(char)：将hack与该字符的ASCII值相乘。

    • hack += pad：然后将pad加到hack上。

  • 这个循环使得hack依赖于flag中每个字符的顺序和值，以及flag的MD5哈希。

最后程序给出了hack值和flag的最终格式

EXP：

首先寻找出破解逻辑

表达式 hack 定义为：(f1*f2...*f14 + f2*f3...*f14 + f3*f4...*f14 + f14 + 1)*pad

这里，`pad` 是 hack 的一个因子。通过使用 factordb 对 hack 进行质因子分解，我们得到以下质因子：

2^2 · 19 · 31 · 59 · 97 · 127 · 3727 · 44948980991 · 1753609692783577883 · 556795634058750798159011。

因此，`pad` 可以是这些质因子的任意乘积组合。

1. 由于 pad 与一个 MD5 值相关，它必须满足以下条件：

0x10000000000000000000000000000000 < pad < 0xffffffffffffffffffffffffffffffff。

我们将通过迭代法穷举所有质因子的乘积组合，以找到所有符合上述条件的 pad 值。

2. 对于表达式 hack / pad - 1，其结果应能被 f1*f2...*f14 + f2*f3...*f14 + f3*f4...*f14 + f14 整除，且 f1 至 f14 应为可见字符 (ASCII 32 至 126)。因此，以下条件必须满足：

(hack / pad - 1) % f14 = 0

((hack / pad - 1) / f14 - 1) % f13 = 0

......

通过迭代法，我们寻找符合以上条件的 pad，并按顺序检查每个符合条件的 pad 值对应的可见字符。我们找到了两个符合条件的结果：

301029523552535981934367911782880889228 对应的字符组合为：“veryl1keMath!!”

143231789432255023662320216090241713423 对应的字符组合为：“\2`Q{gKn{Sjjn)”

from Crypto.Util.number import *
from hashlib import md5

hack = 280098481791453837177137197730537158171743673148935867304957882116
numMin = 0x10000000000000000000000000000000
numMax = 0xffffffffffffffffffffffffffffffff
factors = [2, 2, 19, 31, 59, 97, 127, 3727, 44948980991, 1753609692783577883, 556795634058750798159011]

def checkValue(count, value):
    if count == 14 and value == 1:
        return 1
    for i in range(32, 127):
        if (value - 1) % i == 0:
            if checkValue(count + 1, (value - 1) / i) == 1:
                return 1
    return 0

def findFlag(count, value, flag):
    if count > 14 or (count == 14 and value != 1):
        return 0
    if count == 14 and value == 1:
        return 1
    for i in range(32, 127):
        if (value - 1) % i == 0:
            flag[count] = i
            if findFlag(count + 1, (value - 1) / i, flag) == 1:
                return 1
    return 0

def findpad(value, index):
    for i in range(index, 11):
        tmp = value * factors[i]
        if tmp >= numMin and tmp <= numMax:
            flag = [0] * 14
            if findFlag(0, hack / tmp, flag) == 1:
                for j in range(0, 14):
                    print(chr(flag[13 - j]), end=' ')
                print('\n')
            findpad(tmp, i + 1)
    findpad(1, 0)

for i in range(32, 127):
    flag = chr(i) + 'veryl1keMath!!'

    pad = bytes_to_long(md5(flag.encode()).digest())
    if pad == 301029523552535981934367911782880889228:
        print(flag)
        break

for i in range(32, 127):
    flag = chr(i) + '\\2`Q{gKn{Sjjn)'
    pad = bytes_to_long(md5(flag.encode()).digest())
    print(pad)
    if pad == 143231789432255023662320216090241713423:
        print(flag)
        break

评论