HNP的基础认知

首先是特征，类似$a*x-b=c modn$,要求x, c未知是小数（相对n小也是），有多组数据使得可以求x

求解基础：一般一组数据得到（x,k,1)时不能确认x,k比例关系使x不正确，这时多组数据在信息论的支撑下，比如这里c是8t时，一次泄露3bit,x如果是150bit,50组数据可以恢复x

这里用ECDSA的公式s=invert(k,q)(h+dr)modq举例，假设有50组数据，一组泄露k=8*t+b,t未知，b已知

第一步化简至标准形式：invert(s,q)h-b+drinvert(s,q)=8t mod n

设invert(s,q)h-b为C,invert(s,q)r为A，得到Ad-C-kq=8*t

为什么短：8*t相对于q,2157比2160，零头

第二步，利用i个方程得到一个包含d的短向量，这里方便只显示3组A1,A2,A3

-k1 (q 0 0 0
-k2 0 q 0 0
-k3 0 0 q 0
d A1 A2 A3 8
-1 C1 C2 C3 0) 竖着计算

8t1 8t2 8t3 8d

这时LLL取row[-1]%q得到8*d（实则是t1,t2,t3,d,这样更短