浪子归家|密码学学习笔记之Coppersmith’s Method （三） 123456789101112131415

单元coppersmith’s method 学习最终章，详解第三届强网杯之copper study ，【这一波，这一波是首尾呼应。】
第一关：Stereotyped messages已知n,e=3,c ， m共512bit但是低72bit未知，原理可参考Mathematics of Public Key Cryptography ch19 。也即前文所述。
[+]Generating challenge 1[+]n=0x44e360ce873d18d33eecc0829eb0801e71950e26576963c470f91f4c5e7f3e951f65404c6a87f4328495c9c64d39271f3317081aeab34bdf350c5f9bf0c5a49668f763cbf404e66f210336042c6a6e43eed6c6eaca69287ed91b2841148668fd3881b241317574cc8b307fb41593ff7caaa6f09e32f657399c63fe5f68995c5dL[+]e=3[+]m=random.getrandbits(512)[+]c=pow(m,e,n)=0x20d40eecc8108d6c57b0ea2e1d7d165fb342813764f3760baf71e7929e3c22476de15b5e665ff8b869b5ed3a672aad4e9ef330bb7e18329ce2d0cccae369e244002882a273d3bf5a13b8936974768a920f5cbee52d0bb0323f867ff6305c5aa7ceb99453172332cd9837fdb05d6ea2d7eac39fd0d39960dc9ddbdd40f82b444bL[+]((m>>72)<<72)=0x5377a12cada023e2714b4a9e80f1da87ca567f084e2862e704b813cd7f69b8dbbf67d60e73610fabb7896eeb3cc5a2c0915d03f9f8d44d000000000000000000L[-]long_to_bytes(m).encode('hex')=这道题我们完全可以将题面转化为在求方程f(x) = (m+x)^3 在模N下的解
所以可以直接套我们前面所描述的方法
exp:
# 展示格的样式def matrix_overview(B, bound):for ii in range(B.dimensions()[0]):a = ('%02d ' % ii)for jj in range(B.dimensions()[1]):a += '0' if B[ii,jj] == 0 else 'X'a += ' 'if B[ii, ii] >= bound:a += '~'print (a)def coppersmith(pol, modulus, h, X):# 计算矩阵维度n = d * h# 将多项式转到整数环上polZ = pol.change_ring(ZZ)x = polZ.parent().gen()# 构造上文所述lattice ， polZ(x * X) 就是环上的多项式f(X * x) ，所以这里与上文不同的点就在于引入了变量x ，但变量x在后面的矩阵构造中会被抹掉。g = []for i in range(h):for j in range(d):g.append((x * X)**j * modulus**(h - 1 - i) * polZ(x * X)**i)B = Matrix(ZZ, n)for i in range(n):for j in range(i+1):B[i, j] = g[i][j]# 展示格的样式matrix_overview(B,modulus^h)# LLL算法B = B.LLL()# 将最短向量转化为多项式，并且去除相应的Xnew_pol = 0for i in range(n):new_pol += x**i * B[0, i] / X**i# 解方程potential_roots = new_pol.roots()return potential_rootsN =e =c =m =ZmodN = Zmod(N)P. = PolynomialRing(ZmodN)f = (m + x)^e - cepsilon = 1 / 7# 根据公式计算参数d、h、Xd = f.degree()h = ceil(1 / (d * epsilon)) X = ceil(N**((1/d) - epsilon))roots = (coppersmith(f, N, d, h, X))[0]for root in roots:if (m + root)^e %N== c %N :print(m + root)构造的格的样式
与example3 构造的格是类似的
但其实sage已经集成了coppersmith的求根方法，因此简单调用一下函数就可以解决这个问题。这里之所以这样做其实是想映照前文，展示一下利用coppersmith来解决此类问题的整个过程。
利用现成方法版exp

浪子归家|密码学学习笔记之Coppersmith’s Method （三）

推荐阅读

#北方网#由新作《薪传》解读许亨新北派现代主义雕刻

新华网|用脚“画”地图的“飞地书记”

上海热线体育综合：颜骏凌四外援参合练，上港未雨绸缪盼新赛季

美食|直接下锅就错了，多加一步，煮出来的玉米又甜又香煮玉米

新疆喀什：馕产业助脱贫

nba|30+20！韩德君也不放过王哲林，MVP被打成伪巨头，6犯离场一脸无奈

中医如何防癌11个好习惯有帮助

怎样看待一个人沉默不敢与人打交道，身边有其他人在就不那么害怕然后就是一个特别开朗敢于跟别人交流的心理

吴磊|据说《琅琊榜3》已经开始筹拍，主角阵容依旧未定，但吴磊和王一博呼声非常高

央视新闻|重型火炮压制、15式坦克突击解放军钢铁洪流席卷高原

小鱼段子手|这就是你拍给我的婚纱照？，修图的摄影师你给我出来

朱一龙|啥情况？朱一龙评论陈明昊幼稚陈明昊是谁？

星座女神Goddess|水逆逃生指南之水象星座

沏红茶用多少度的水温,青茶最适宜的冲泡水温

环球网|揪心！四川泸县一工厂起火致5人受伤，其中3人在ICU抢救

『海参功效』海参有什么功效作用煮海参时可以加醋吗

高考|岳云鹏给高考生送祝福：结果翻车了

「老树昏鸭」大批士兵荷枪实弹连夜出发，白宫：不能放过一个，美国后院起火

北京日报|恭王府博物馆将启动修缮数字化采集同步进行

果味仙女|《阳光灿烂的日子》：电影所呈现的文学真实性