type
status
date
summary
password
category
slug
icon
小师傅给的题后面好多都是HNP问题，在这里先学习一下再去做题🥹🥹🥹🥹好难好难我爱密码！！🤥🤥
🐳隐藏数问题（HNP / Hidden Number Problem）
📍隐藏数问题
📍HNP定义
MSB（most significant bits）
提出了most significant bits (MSB) 的定义。首先令p是一个素数, n是p的二进制位数,即n，用x mod p来表示一个定义在有限域的数a∈GF(p),即x=(modp)。定义(x)的值为t并且
or更简单的定义
(x)=z,|x-z|<
简单理解t=(x):
- 若满足,则 是一个输出
- k越大，越接近x
多大的k可以来解决HNP问题
定理1
定理1
定理2
定理2
LLL算法
LLL格约减算法的定义
LLL格约减之后得到优质基，优质基其中一条性质是基尽可能小
LLL的应用
可规约到格的另一个基本问题：最近向量问题（CVP)。
E.G
已知
构造格
肯定在格子中
?A,X*?B应该多大呢
保证vk中的每一项的长度都差不多，这样有利于找到vk
Lattice 之 HNP
有这样的一些等式，然后A,B已知,k的bit位数要小于p的bit位数，等式数量足够的情况下，少6bit位数可以求解k
具体构造如下矩阵
其中K为ki同bit位数的数（bit_length(ki)=250 K=2^250)
Z为需要自己构造的数
要尽可能的满足Z*x的bit位数与K一致
一般Z取K/q, K的构造也是为了让vk中的每一项的长度都差不多，这样有利于找到vk
注意：Z取K/q 这时候构造的矩阵不能是ZZ,K/q结果不一定是整数
例题
🥹MTCTF2022 strange_rsa3
📑题目
🪄题解
gift = (p[0] * a - p[1]) * inverse(b, p[0] * p[1] ** 2) % (p[0] * p[1] ** 2)先求出
p0,p1连分数求解出p0,p1
求b
第一种解法 HNP问题构造格
第二种解法 模上P（大师傅307教的👐🫣）
gift = (p[0] * a - p[1]) * inverse(b, p[0] * p[1] ** 2)
同时模上p[0]
gift%p[0]=-p[1]*ib
求出r0
👀wp
第一种
第二种
小研究
逆元的比特值靠近模数的比特
🥹红明谷CTF 2022 sm2
📑题目
out(sigs)
🪄题解
👀wp
📎 参考
- 一些引用
- 引用文章
🥹XCTF2020-高校战役
📑题目
🪄题解
多了一步筛选，if k_bits < 122:
构造格求出私钥x（128bit),筛选k的比特与X相差较小的
👀wp
🥹NPUCTF2020-babyLCG
📑题目
🪄题解
恢复seed，接下来生生随机数，KEY，iv可知，decrypt
恢复seed(已知a,b,m和伪随机数的高位，恢复seed）
hnp问题，构造格，恢复低位，高位已知，即可求出所有随机数
保证规约出来的bit差不多
算出seed之后脚本直接更改题目里这几个值就好啦
👀wp
总结
解决HNP问题
- 一般需要多组数据，每一组就像方程组中的每一条方程，据这些方程组构造一个Lattice（矩阵），像在用矩阵解决线代中的 XA=B 的问题，这个B中的每一项是我们获得的MSB这样子的比较模糊的信息（比如比特位等信息），这个B向量的长度（范式）需要相对与格中其他向量要短，然后我们就可以利用LLL算法找到这个B，进而根据我们的构造，确定X向量中我们需要的一个特定的值。也就是方程组的解。
- 有时候B很大，这时候就要通过这时候需要根据规约出来的相对较小值来计算出B，HZNU nothing那题通过规约出来的vi=得到k，根据ki与x的等式关系求x