密钥生成生成 2048 位的 RSAn, e, d, phie 65537私钥分享机制poly是一个多项式常数项是d私钥多项式的其他系数是随机的 2048 位数字你选择朋友数量k实际份额数为k1你也有一份关键代码pythonM matrix(ZZ, [[x**i for i in range(n_shares)] for x in range(1, n_shares1)]) coeffs M.solve_left(vector(ZZ, [1] [0]*(n_shares - 1))) shares [(c*y) % phi for c,y in zip(coeffs, ys)]这段代码在做什么M是范德蒙矩阵行是[1, x, x^2, ..., x^(k)]x 1, 2, ..., k1coeffs是满足coeffs * M [1, 0, 0, ..., 0]的向量也就是说coeffs是拉格朗日插值系数使得sum(coeffs[i] * eval_poly(poly, i1, phi)) poly[0] d这是一个门限方案如果你收集了所有份额就可以恢复d mod phi。你能做的事解密查询给定密文c得到所有朋友的份额但不包括你自己的份额重新分享重新选择朋友数量得到新的份额分配结束得到一个用公钥加密的 flag 密文目标恢复d来解密 flag 密文。漏洞分析关键点份额是在模 phi下计算的而 phi 是未知的。但是我们得到了你自己的份额yours。观察你可以多次 Reshare选择不同的朋友数量每次得到一个新的yours值份额的计算在模 phi 下进行关键漏洞多项式的常数项始终是d。当你选择不同数量的份额时拉格朗日系数的计算方式不同但你得到的份额都是同一个多项式在不同点的求值组合。具体来说poly [d, r1, r2, ..., r99]常数项是d不同n_shares截取不同长度的多项式每次你得到的yours是sum(coeffs_j * poly(j)) mod phi攻击思路当n_shares 1时即朋友数为 0M 是 1×1 矩阵[1]coeffs [1]ys [eval_poly(poly, 1, phi)] [poly[0]] [d]你的份额yours d mod phi但朋友数不能为 0n_shares 1会退出。当n_shares 2时1 个朋友M [[1, 1], [1, 2]]coeffs 满足coeffs * M [1, 0]即coeffs [2, -1]ys [poly(1), poly(2)]你的份额取最后一个yours 2*poly(1) - poly(2) 2*(d r1) - (d 2*r1) d这就是关键当只有 1 个朋友时你得到的份额恰好就是d mod phi但是等等代码中pythonyours shares.pop(n_shares - 2)当n_shares 2时shares.pop(0)取的是第一个份额而第一个份额的计算textshares[0] coeffs[0] * ys[0] 2 * poly(1) 2*(d r1) shares[1] coeffs[1] * ys[1] -1 * poly(2) -(d 2*r1)你得到的yours shares[0] 2*(d r1) mod phi不是d。让我重新看pythonys [eval_poly(poly, i, phi) for i in range(1, n_shares1)] # 在点 1,2,...,n_shares 求值 M matrix(ZZ, [[x**i for i in range(n_shares)] for x in range(1, n_shares1)]) coeffs M.solve_left(vector(ZZ, [1] [0]*(n_shares - 1))) shares [(c*y) % phi for c,y in zip(coeffs, ys)] yours shares.pop(n_shares - 2)coeffs满足sum(coeffs[j] * (i1)^j) 1 if i0 else 0所以sum(coeffs[j] * i^j)在i1时为 1在i2,3,...,n_shares时为 0。这意味着sum(shares) sum(coeffs[j] * poly(j1))是一个拉格朗日插值恢复poly(0) d不对coeffs是对M的左解而M[i][j] (i1)^j所以coeffs * M [1, 0, ..., 0]。正确的拉格朗日插值理解如果我们有f(x) poly[0] poly[1]*x ... poly[k]*x^k在点1, 2, ..., k1的值那么存在系数λ_i使得∑ λ_i * f(i) f(0) d。而coeffs正是这些拉格朗日系数∑ coeffs[j] * (i1)^j 1当i0这意味着∑ coeffs[j] * eval_poly(poly, j1) poly(0) d。因此sum(shares) d mod phi你得到yours shares.pop(n_shares - 2)即除了索引 n_shares-2 的那个份额外所有其他份额都留给了朋友。当n_shares 2时shares [s1, s2]yours shares.pop(0) s1朋友得到s2通过解密查询可以看到攻击方法选择1 个朋友n_shares 2记下你的份额yours请求解密任意密文比如 2得到朋友的份额s_friend计算d_mod_phi (yours s_friend) % n我们不知道 phi但可以用 n 近似因为 d phi n所以 d_mod_phi 可能就是 d 本身或者 d d_mod_phi mod phi实际上d (yours s_friend) mod phi而d phi所以如果yours s_friend phi那么yours s_friend就是d。由于 phi ≈ n差约 √n 量级且 d 是随机均匀分布在 [1, phi] 中大概率d phi且yours s_friend已经小于 phi因此d yours s_friend。拿到d后直接解密 flag 密文即可。解题脚本pythonfrom pwn import remote from Crypto.Util.number import long_to_bytes r remote(archive.cryptohack.org, 33824) # 读取 n 和 e r.recvuntil(bn ) n int(r.recvline().strip()) r.recvuntil(be ) e int(r.recvline().strip()) # 选择 1 个朋友 r.recvuntil(bWith how many friends you want to share the private key? ) r.sendline(b1) r.recvuntil(bHere is your part: ) yours int(r.recvline().strip()) # 请求解密 2任意非零密文 r.recvuntil(b ) r.sendline(b1) r.recvuntil(bCiphertext: ) r.sendline(b2) r.recvuntil(bHere are the partial decryptions of your friends!\n) s_friend int(r.recvline().strip()) # 恢复 d d yours s_friend # 这应该就是私钥 print(fRecovered d: {d}) # 结束并获取 flag 密文 r.recvuntil(b ) r.sendline(b3) r.recvuntil(bBye bye, take this with you!\n) enc_flag int(r.recvline().strip()) # 解密 flag pow(enc_flag, d, n) print(long_to_bytes(flag))答案d sum(shares) mod phi由于d phi直接求和就得到私钥进而解密 flag。