Coppersmith's Method

CopperSmith's Method

Coppersmith算法在ctf的密码学问题中应用越来越广泛，但少有人深究其原理，本文将介绍Coppersmith方法基本原理，所对应的格子构造与格基规约方法，调整Coppersmith求解上界的方法。
注：因blog渲染的原因，本文采用截图的方式展现大部分公式推导内容
本文检索目录：

Reference

https://www.math.auckland.ac.nz/~sgal018/crypto-book/ch19.pdf

Definition


Example


Howgrave-Graham


Proof


这波推导梦回高二MOer的日子////
How to Find G(x)



Example


Coppersmith's Method


Coppersmith


Proof




Coding

在实际运用过程中，我们往往使用sagemath中封装好的small_root函数，但部分题目会卡small_root函数的上界，即该函数计算得到的X上界小于求解未知量x0，这时需要我们调整参数，下面用github上开源的一段代码展示调整参数的过程：

1. def matrix_overview(B, bound):
2.     for ii in range(B.dimensions()[0]):
3.         a = ('%02d ' % ii)
4.         for jj in range(B.dimensions()[1]):
5.             a += '0' if B[ii,jj] == 0 else 'X'
6.             a += ' '
7.         if B[ii, ii] >= bound:
8.             a += '~'
9.         print (a)
10. def coppersmith(pol, modulus, beta, h, t, X):
11.     # 计算矩阵维度
12.     n = d * h + t
13.     # 将多项式转到整数环上
14.     polZ = pol.change_ring(ZZ)
15.     x = polZ.parent().gen()
16.     # 构造上文所述lattice，polZ(x * X) 就是环上的多项式f(X * x)
17.     g = []
18.     for i in range(h):
19.         for j in range(d):
20.             g.append((x * X)**j * modulus**(h - i) * polZ(x * X)**i)
21.     for i in range(t):
22.         g.append((x * X)**i * polZ(x * X)**h)
23.     # 构造格B
24.     B = Matrix(ZZ, n)
25.     for i in range(n):
26.         for j in range(i+1):
27.             B[i, j] = g[i][j]
28.     # 展示格的样式
29.     matrix_overview(B, modulus^h)
30.     # LLL
31.     B = B.LLL()
32.     # 将最短向量转化为多项式，并且去除相应的X
33.     new_pol = 0
34.     for i in range(n):
35.         new_pol += x**i * B[0, i] / X**i
36.     # 解方程
37.     potential_roots = new_pol.roots()
38.     # 检查根
39.     roots = []
40.     for root in potential_roots:
41.         if root[0].is_integer():
42.             result = polZ(ZZ(root[0]))
43.             if gcd(modulus, result) >= modulus^beta:
44.                 print("p: ",(gcd(modulus, result)))
45.                 roots.append(ZZ(root[0]))
46.     return roots
47. N =
48. ZmodN = Zmod(N)
49. P.<x> = PolynomialRing(ZmodN)
50. pbar =
51. f = pbar + x
52. beta = 0.4
53. d = f.degree()
54. epsilon = beta / 7
55. h = ceil(beta**2 / (d * epsilon))
56. t = floor(d * h * ((1/beta) - 1))
57. X = ceil(N**((beta**2/d) - epsilon))
58. roots = coppersmith(f, N, beta, h, t, X)

复制代码

可以看到：

1. X = ceil(N**((beta**2/d) - epsilon))

复制代码

Example

可以参考我的另一篇文章，“2023hgame-week3-RSA大冒险2”一题进行参数调整的尝试（还没发出来，等2.7hgame结束发）
Ending

以下内容待更新完善：
1.二元及多元coppersmith原理（大概会另开一篇文章）
2.Some Applications of Coppersmith’s method，这部分可以去原文翻，理解难度不大，也都是大家最常见的板题了，这里就没写（
3.相关函数源码解析，比如这里本来想拿small_root的源码来讲调参，但是咕咕咕了，尽快补一下（主要是想在发hgame crypto wp之前更出来
4.好多国际赛上出现过的有意思的coppersmith构造（或者也可以说是Lattice的构造）会陆续更到这里

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！