由于莫得学生身份了，所以上周五巅峰极客只报了个野队看了一下题，然后一下午就过去了。 HSSP 类的问题之前没怎么接触，再加上对垂直格这块的东西还没有琢磨透，所以比赛的时候没有把题给做出来，赛后也花了好长时间去理解，还是太菜了。
题目代码
123456789101112131415161718192021 |
# Problem by rec, without any sleep at all.from Crypto.Util.number import bytes_to_long as b2lfrom hashlib import sha256from os import urandomfrom secret import p, a, b, flagECC = EllipticCurve(GF(p), [a, b])R, E, C = [ECC.random_point() for _ in range(3)]pad = lambda m: urandom(8) + m + b'\x00' * (ZZ(p).nbits() // 8 - len(m) - 8 - 1)out = list()for i in range(len(flag)): m = pad(chr(flag[i]).encode()) nonce = urandom(16) sh = sha256(nonce + m).digest() Q = b2l(m)*R + b2l(nonce)*E + b2l(sh)*C out.append(Q.xy())with open('out.tuo', 'w') as f: f.write(str(out)) |
代码不难理解，题目基于椭圆曲线，但是没有给出曲线的参数。然后将 flag 逐字节进行一个操作：
- 首先对 flag 的一个字节进行填充得到 m ：八字节随机字符串||flag 的字节|| \x00，总共长度为 63
- 虽然生成 16 字节随机字符串 nonce
- 计算 nonce || m 的哈希 sh
- 输出 $Q = m\times R+nonce \times E+sh\times C$，其中 $R,E,C$ 为未知随机点。
我们手里仅有这一系列的 $Q$ 点。所以第一步肯定是要先恢复曲线的信息。
我们知道曲线的表达式为 $y^2 \equiv x^3 +ax+b \pmod p \to y^2 = x^3 +ax+b +kp$
于是有 $y^2-x^3 = ax+b+kp$
考虑消元，于是找两个点做减法（不是曲线上的点减法，是我们这里的等式相减）：
$Q_1-Q_2$ ：$(y_1^2-x_1^3) - (y_2^2-x_2^3) = a(x_1-x_2) + (k_1-k_2)p$
$Q_1-Q_3$：$(y_1^2-x_1^3) - (y_3^2-x_3^3) = a(x_1-x_3) + (k_1-k_3)p$
还想把 $a$ 项给消了，于是：
$(x_1-x_3)(Q_1-Q_2) - (x_1-x_2)(Q_1-Q_3)$
$= (x_1-x_3)(y_1^2-x_1^3) - (y_2^2-x_2^3)-(x_1-x_2)(y_1^2-x_1^3) - (y_3^2-x_3^3)$
$=(x_1-x_3)(k_1-k_2)p-(x_1-x_2)(k_1-k_3)p$
我们得到一个 $Kp$，即 $p$ 的一个倍数。
于是我们再用一点 $Q_4$ 就能得到 $p$ 的另一个倍数，然后求他们的公因子，再去除一些小因子，就能得到素数，也就是模数 $p$ 了。
有了模数 $p$，我们就能计算
$a \equiv \frac{(y_1^2-x_1^3) - (y_2^2-x_2^3) }{x_1-x_2} \pmod p$
$b \equiv y^2-x^3 - ax \pmod p $
从而恢复曲线的所有参数了。
12345678910111213141516171819202122232425262728 |
from Crypto.Util.number import GCD,isPrimedef recover_para(Q):x1,y1 = Q[0]x2,y2 = Q[1]x3,y3 = Q[2]x4,y4 = Q[3]t12_13 = ((y1**2 - x1**3)-(y2**2 - x2**3)) * (x1-x3)t13_12 = ((y1**2 - x1**3)-(y3**2 - x3**3)) * (x1-x2)k1p = t12_13-t13_12t12_14 = ((y1**2 - x1**3)-(y2**2 - x2**3)) * (x1-x4)t14_12 = ((y1**2 - x1**3)-(y4**2 - x4**3)) * (x1-x2)k2p = t12_14-t14_12p = factor(GCD(k1p,k2p))[-1][0]assert isPrime(int(p))a = ((y1^2-x1^3)-(y2^2-x2^3))/(x1-x2) % pb = (y1^2-x1^3-a*x1) % pE = EllipticCurve(GF(p),[a,b])assert E(Q[0])return E,(a,b,p)Q = [(),(),()....]E,_ = recover_para(Q) |
之后发现，这条曲线的 order 和 p 相等，因此利用 smart attack，我们能解决这条曲线上的 DLP 。
那么回到问题 $$Q = m\times R+nonce \times E+sh\times C$$，由于不知道 $R,E,C$，方便起见我们直接再生成一个点 $G$，分别设 $R = rG,E=eG,C=cG$，那么就有 $$Q = (mr+nonce\cdot e +sh \cdot c)\times G$$
然后我们利用 smart attack 解 DLP：
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647 |
def HenselLift(P,p,prec):E = P.curve()Eq = E.change_ring(QQ)Ep = Eq.change_ring(Qp(p,prec))x_P,y_P = P.xy()x_lift = ZZ(x_P)y_lift = ZZ(y_P)x, y, a1, a2, a3, a4, a6 = var('x,y,a1,a2,a3,a4,a6')f(a1,a2,a3,a4,a6,x,y) = y^2 + a1*x*y + a3*y - x^3 - a2*x^2 - a4*x - a6g(y) = f(ZZ(Eq.a1()),ZZ(Eq.a2()),ZZ(Eq.a3()),ZZ(Eq.a4()),ZZ(Eq.a6()),ZZ(x_P),y)gDiff = g.diff() # differential for i in range(1,prec):uInv = ZZ(gDiff(y=y_lift))u = uInv.inverse_mod(p^i)y_lift = y_lift - u*g(y_lift)y_lift = ZZ(Mod(y_lift,p^(i+1)))y_lift = y_lift+O(p^prec)return Ep([x_lift,y_lift])def SmartAttack(P,Q,p,prec):E = P.curve()Eqq = E.change_ring(QQ)Eqp = Eqq.change_ring(Qp(p,prec))P_Qp = HenselLift(P,p,prec)Q_Qp = HenselLift(Q,p,prec)p_times_P = p*P_Qpp_times_Q = p*Q_Qpx_P,y_P = p_times_P.xy()x_Q,y_Q = p_times_Q.xy()phi_P = -(x_P/y_P)phi_Q = -(x_Q/y_Q)k = phi_Q/phi_Pk = Mod(k,p)return kG = ECC.random_point()Points = []for each in Q: Points.append(E(each))h = []for P in Points:h.append(SmartAttack(G,P,p,8)) |
我们获得了一系列值：$m_ir+nonce_i\cdot e +sh_i \cdot c$，
其中 $m_i$ 是八个字节随机字符串+flag的一个字节+54个 ‘’\x00’’，$nonce_i$ 是16字节随机字符串，$sh_i$ 可以看作 32 字节随机字符串。
由于 $m_i$ 后面全是 “\x00”，所以有 bytes_to_long(mi) = bytes_to_long(mi[:9]) * 256^54，我们把这个 $256^{54}$ 算到 $r$ 身上的话，$m_i$ 也就可以看作是九个字节的随机字符串。于是我们注意到，这个式子中的三项都是由一个不变的很大的数 $r,e,c$ 和变化的但是很小的数 $m_i,nonce_i,sh_i$ 组成的。相较于经典的 HSSP 问题
这里的系数不是 ${0,1}$，但是也不是很大，也有称之为 The Hidden Lattice Problem（HLP），解决这一类问题使用的手法一般是构造垂直格：对由 $h$ 组成的向量 $\overrightarrow{h}$ 进行两次正交以找到组成 $h$ 中的较短的那一部分。
首先我们构造向量 $\overrightarrow{h}$ 的垂直格（也即找到 $\overrightarrow{h}$ 的解空间），格中每条向量 $l$ 均满足 $l \cdot \overrightarrow{h} = 0$
格的样式为
$H =\begin{bmatrix}k\cdot h_0 &1 & & & & & \newlinek\cdot h_1 & &1 & & & & \newlinek\cdot h_2 & & & \ddots & & & \newline\vdots & & & &1 & & \newlinek\cdot h_{n-1} & & &\dots & &1 & \newlinek\cdot p & & &\dots & & &1 \newline\end{bmatrix}$，其中 $k$ 是一个较大的常数，例如 $2^{1024}$，$p$ 是模数
12345678910111213 |
k = 2^1024h_v = matrix(ZZ,[h+ |
然后使用 LLL 进行规约。由于我们的 $\overrightarrow{h}$ 是 $n\times 1$ 的，因此解空间的秩应该是 $n-1$，所以我们可以拿到一个 $n-1 \times n$ 的格 $L=\overrightarrow{h}^{\bot}$。
于是我们有 $l \cdot \overrightarrow {h} = l \cdot \overrightarrow{m \cdot r}+l \cdot \overrightarrow{nonce\cdot e} +l \cdot \overrightarrow{sh \cdot c} + l \cdot \overrightarrow{kp}) = 0$
考虑到如果 $l\cdot \overrightarrow{m} = 0,l\cdot \overrightarrow{nonce} =0,l\cdot \overrightarrow{sh}=0,l \cdot \overrightarrow{k}=0$ 也能使得上式成立，而且 $\overrightarrow{m}$ 等向量还比较短，于是我们求一个 $L$ 的垂直格 $L^{\bot}$ （这一块其实不是很理解，虽然该条件能使得上式成立，但并不能说上式成立会保证满足该条件，属于是充分不必要条件，不过经过实践后发现确实存在该条件）
由于我们的 $\overrightarrow{h}$ 是由四项组成的，于是我们用 $(n-1-3) \times n$ 的矩阵（这样子解空间的秩为 $4$）
$O =\begin{bmatrix}L^\top & 1\end{bmatrix}$
然后使用 LLL 进行规约。在第一行我们能够得到的最短的向量，应该就是由八个随机字节和一个 flag 字节组成的 $\overrightarrow {m}$ ，然后我们取最低字节，就能获取到 flag 了。
123456789 |
ll = (matrix(ZZ,l[:-3]).T)*kmm = block_matrix(ZZ,[[ll,1]])LL = mm.LLL()assert sum(LL[0][:70]) == 0print("".join(chr(i & 0xff) for i in LL[0][70:]))# Congratulations! Your flag is: flag{893d041e-c0a2-3145-5320-cdee7d3c87fb} |
最后整合一下
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113 |
from Crypto.Util.number import GCD,isPrimedef recover_para(Q):x1,y1 = Q[0]x2,y2 = Q[1]x3,y3 = Q[2]x4,y4 = Q[3]t12_13 = ((y1**2 - x1**3)-(y2**2 - x2**3)) * (x1-x3)t13_12 = ((y1**2 - x1**3)-(y3**2 - x3**3)) * (x1-x2)k1p = t12_13-t13_12t12_14 = ((y1**2 - x1**3)-(y2**2 - x2**3)) * (x1-x4)t14_12 = ((y1**2 - x1**3)-(y4**2 - x4**3)) * (x1-x2)k2p = t12_14-t14_12p = factor(GCD(k1p,k2p))[-1][0]assert isPrime(int(p))a = ((y1^2-x1^3)-(y2^2-x2^3))/(x1-x2) % pb = (y1^2-x1^3-a*x1) % pE = EllipticCurve(GF(p),[a,b])assert E(Q[0])return E,(a,b,p)def HenselLift(P,p,prec):E = P.curve()Eq = E.change_ring(QQ)Ep = Eq.change_ring(Qp(p,prec))x_P,y_P = P.xy()x_lift = ZZ(x_P)y_lift = ZZ(y_P)x, y, a1, a2, a3, a4, a6 = var('x,y,a1,a2,a3,a4,a6')f(a1,a2,a3,a4,a6,x,y) = y^2 + a1*x*y + a3*y - x^3 - a2*x^2 - a4*x - a6g(y) = f(ZZ(Eq.a1()),ZZ(Eq.a2()),ZZ(Eq.a3()),ZZ(Eq.a4()),ZZ(Eq.a6()),ZZ(x_P),y)gDiff = g.diff() # differential for i in range(1,prec):uInv = ZZ(gDiff(y=y_lift))u = uInv.inverse_mod(p^i)y_lift = y_lift - u*g(y_lift)y_lift = ZZ(Mod(y_lift,p^(i+1)))y_lift = y_lift+O(p^prec)return Ep([x_lift,y_lift])def SmartAttack(P,Q,p,prec):E = P.curve()Eqq = E.change_ring(QQ)Eqp = Eqq.change_ring(Qp(p,prec))P_Qp = HenselLift(P,p,prec)Q_Qp = HenselLift(Q,p,prec)p_times_P = p*P_Qpp_times_Q = p*Q_Qpx_P,y_P = p_times_P.xy()x_Q,y_Q = p_times_Q.xy()phi_P = -(x_P/y_P)phi_Q = -(x_Q/y_Q)k = phi_Q/phi_Pk = Mod(k,p)return k# L: the orthoginal lattice of hdef orthoginal_of_vector_modp(h,p):k = 2^1024h_v = matrix(ZZ,[h+ |
（感觉自己现在所掌握的知识点有点杂乱了，后续想把这些搞成一个体系，比如整数分解问题搞一起，离散对数问题搞一起，SVP 搞一起，LWE 搞一起之类的。。。先立个 flag再说 ）
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可联系QQ 643713081，也可以邮件至 [email protected] - source:Van1sh的小屋
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论