xyctf某题

xyctf wp

题目:

from Crypto.Util.number import *
import hashlib
from secrets import flag

def hash(x):
    return hashlib.sha256(x.encode()).digest()


def pad(message):
    return message + hash(str(len(message)))


m = bytes_to_long(pad(flag))
p = getStrongPrime(512)
q = getStrongPrime(512)
n = p * q
e = 3
print(pow(m, e, n))
print(n)

# 41114240955577895103973182354616009257350212064482446025812858566641718381281218093994896700140767635266663377586425898558099315375553287958882025958109765566681623453728472370134625131536739144226158625954308078356427514247684404989496475452898609058386951475642649945178862199599374503811829039930846383007
# 153611702524335217024082326953693564399200168431497676063243900319357738300910784986132296026672110090806387676146514812317915651361459828009371616376752560815339546667911601417645293846075664447051809094013783298133615995661317584721185010884267772902669067055126312676803092840020450000172246840643192188661

分析：

1.看一下m的组成 $m = x \cdot 2^{256} + \text{h\_val}$

这里的 $x$ 就是我们要找的 flag，而 h_val 是后面那一串已知的哈希值。

2.再来看看这个哈希函数

哈希函数的结果取决于 len(flag)，而flag长度是这个不大的值
看到这里笔者突然想到一句话：

密码学题目中，不大的值都可以当作已知

而h_val已知的情况下，题目便演变成了m低位泄露
我们去遍历flag长度得到哈希值。
再尝试Coppersmith求解就好

import hashlib
from Crypto.Util.number import long_to_bytes

def get_hash(l):
    h = hashlib.sha256(str(l).encode()).digest()
    return int.from_bytes(h, 'big')

n = 153611702524335217024082326953693564399200168431497676063243900319357738300910784986132296026672110090806387676146514812317915651361459828009371616376752560815339546667911601417645293846075664447051809094013783298133615995661317584721185010884267772902669067055126312676803092840020450000172246840643192188661
c = 41114240955577895103973182354616009257350212064482446025812858566641718381281218093994896700140767635266663377586425898558099315375553287958882025958109765566681623453728472370134625131536739144226158625954308078356427514247684404989496475452898609058386951475642649945178862199599374503811829039930846383007
e = 3

P.<x> = PolynomialRing(Zmod(n))

# 通常 flag 长度在 10 到 60 之间
for L in range(10, 70):
    h_val = get_hash(L)
    shift = 2^256
    
    # 构造原始多项式
    f = (x * shift + h_val)^e - c
    
    # 【关键步骤】使其变为首一多项式 (Monic)
    # 找到最高次项系数在模 n 下的逆元
    coeff = f.coefficients()[-1] 
    f_monic = f * (coeff^-1)
    
    # 设置界限 X。已知 x 是 flag，其长度为 L 字节，所以 x < 2^(8*L)
    # epsilon 控制精度，e=3 时 0.1 左右通常够用
    roots = f_monic.small_roots(X=2^(8*L), beta=1, epsilon=0.05)
    
    if roots:
        res = int(roots[0])
        print(f"Detected Flag Length: {L}")
        print(f"Flag: {long_to_bytes(res).decode()}")
        break