crypto趣题分享

[强网杯 2024]21_steps

题目：

import re
import random
from secrets import flag
print(f'Can you weight a 128 bits number in 21 steps')
pattern = r'([AB]|\d+)=([AB]|\d+)(\+|\-|\*|//|<<|>>|&|\^|%)([AB]|\d+)'

command = input().strip()
assert command[-1] == ';'
assert all([re.fullmatch(pattern, i) for i in command[:-1].split(';')])

step = 21
for i in command[:-1].split(';'):
    t = i.translate(str.maketrans('', '', '=AB0123456789'))
    if t in ['>>', '<<', '+', '-', '&', '^']:
        step -= 1
    elif t in ['*', '/', '%']:
        step -= 3
if step < 0:exit()

success = 0
w = lambda x: sum([int(i) for i in list(bin(x)[2:])])
for _ in range(100):
    A = random.randrange(0, 2**128)
    wa = w(A)
    B = 0
    try : exec("global A; global B;" + command)
    except : exit()
    if A == wa:
        success += 1

if success == 100:
    print(flag)

题目分析：可以理解成，我们有A、B俩个寄存器，要用这俩个寄存器（或具体的数值）加上一些运算符号，来计算一个128位数的汉明重量（在step=21内）

解题思路：
在网上找到采用分治思想实现的32位（算法 - 计算 O（1） 中的汉明权重 - 堆栈溢出）：

v = v - ((v>>1) & 0x55555555);
v = (v & 0x33333333) + ((v>>2) & 0x33333333);
int count = ((v + (v>>4) & 0xF0F0F0F) * 0x1010101) >> 24;

解释：
0x55555555就是0b0101...01，第一行能够将每俩位1出现的频率数出来用二进制表示在这俩位
第二行代码就是整合出每4位1出现的频率表示在这四位
例子：

下面的数都是二进制表示
例如：10110110

（1）v>>1 ：01011011
（2）& 0x55555555 ：01010001
（3）v - ((v>>1) & 0x55555555) ： 01100101
    把01100101拆开看成：01 10 01 01 ，第一个01表示在第78位只有1个二进制‘1’，第二个10表示在第56位上有2个二进制‘1’，第三个01表示在34位上有1个‘1’，第四个类推
（4）(v & 0x33333333) + ((v>>2) & 0x33333333) ： 能算出00110010，看成 0011 + 0010，与第三步看法类似

第三行代码：
最巧妙的一行，(v + (v>>4) & 0xF0F0F0F)与前面理解一致，巧妙点在 * 0x1010101和 >> 24

十六进制 0x01010101 写成二进制，其实是在每个字节的最低位都有一个 1：

$$0x01010101 = 2^{24} + 2^{16} + 2^8 + 2^0$$

当你用 v 乘以这个数时，根据分配律，相当于：

$$Result = v \cdot (2^{24} + 2^{16} + 2^8 + 1)$$

$$Result = (v \ll 24) + (v \ll 16) + (v \ll 8) + (v \ll 0)$$
所以4个字节中1的个数就在24-31位的这个字节里，其他的字节都是些杂数据，可以根据下面的图来看为什么是 右移24位

题目分析时的脚本：

import random

bit_2 = b'0b' + b'01' * (128 // 2)
bit_4 = b'0b' + b'0011' * (128 // 4)
bit_8 = b'0b' + b'00001111' * (128 // 8)

bit_2 = int(bit_2,2)
bit_4 = int(bit_4,2)
bit_8 = int(bit_8,2)

print(bit_2)
print(bit_4)
print(bit_8)
A = random.randrange(0, 2**128)
w = lambda x: sum([int(i) for i in list(bin(x)[2:])])

print("w(A): ", w(A))

def solve_128(A):
    A = A - ((A >> 1) & bit_2)
    A = (A & bit_4) + ((A >> 2) & bit_4)
    A = (A + (A >> 4)) & bit_8
    
    # 折半相加
    A = (A + (A >> 8))
    A = (A + (A >> 16))
    A = (A + (A >> 32))
    A = (A + (A >> 64))

    return A & 0xFF # 注意记得这步
print(solve_128(A))

题目脚本：

#!/usr/bin/env sage
from Crypto.Util.number import *
from pwn import *

command='''
    B=A>>1;
    B=B&113427455640312821154458202477256070485;
    A=A-B;
    B=A>>2;
    B=B&68056473384187692692674921486353642291;
    A=A&68056473384187692692674921486353642291;
    A=A+B;
    B=A>>4;
    A=A+B;
    A=A&20016609818878733144904388672456953615;
    B=A>>8;
    A=A+B;
    B=A>>16;
    A=A+B;
    B=A>>32;
    A=A+B;
    B=A>>64;
    A=A+B;
    A=A&255;
'''
command = command.replace('\n', '').replace(' ', '')
print(command)
p = remote("node6.anna.nssctf.cn", 28641)
p.recvuntil(b'Can you weight a 128 bits number in 21 steps')
p.sendline(command.encode())
p.recvline()
print(p.recv())

下面是鸡块大佬的脚本，在最后处理的时候用了32位的思路，可以学习一下：

from Crypto.Util.number import *
from pwn import *

def popcountRE(A):
    B = 0
    B = A >> 1
    B = B & 113427455640312821154458202477256070485
    A = A - B
    #x -= (x >> 1) & 0x55555555555555555555555555555555
    B = A >> 2
    B = B & 68056473384187692692674921486353642291
    A = A & 68056473384187692692674921486353642291
    A = A + B
    #x = (x & 0x33333333333333333333333333333333) + ((x >> 2) & 0x33333333333333333333333333333333)
    B = A >> 4
    A = A + B
    A = A & 20016609818878733144904388672456953615
    #x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f
    A = A * 1334440654591915542993625911497130241
    A = A & 340282366920938463463374607431768211455
    A = A >> 120
    #return ((x * 0x01010101010101010101010101010101) & 0xffffffffffffffffffffffffffffffff) >> 120
    return A

instructions=[
    "B=A>>1",
    "B=B&113427455640312821154458202477256070485",
    "A=A-B",
    "B=A>>2",
    "B=B&68056473384187692692674921486353642291",
    "A=A&68056473384187692692674921486353642291",
    "A=A+B",
    "B=A>>4",
    "A=A+B",
    "A=A&20016609818878733144904388672456953615",
    "A=A*1334440654591915542993625911497130241",
    "A=A&340282366920938463463374607431768211455",
    "A=A>>120",
]

msg=";".join(instructions) + ";"
command=msg

sh = remote("47.94.195.201", 38958)
sh.recvuntil(b'Can you weight a 128 bits number in 21 steps')
sh.sendline(command.encode())
print(sh.recvline())
print(sh.recvline())