破解基本的 Merkle-Hellman 密码系统的多项式时间算法
本来想在网上找一些破译背包加密的脚本,结果没找到,那就只能自己写。既然这样,那总要知道是怎么破译的吧。于是把Shamir大神的论文—《A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystem》花了几天看完了,做了翻译,有些地方加上自己的理解,认真看应该能看懂。
不想再打一遍了,我就直接贴图了。
上面毕竟是破译的一个非正式描述,好好理解几遍之后(只是我的理解,可能不完全准确),我举个例子来说明破译过程。
私钥;生成公钥
,这里
。
破译算法的第一步:找的
,
是陷门对的必要条件是
;这样的
求解的思路在论文中如下处:
也就是说,我们要找的具有一个性质:对其他的
,
mod
都很小,具体的界见上。这里我用一个python脚本来筛选一下
,但是并未用论文中提到的Lenstra整数规划算法寻找。
A=[152,155,173,156]
lenA=len(A)
blockb=[16,32,64,128]
blocke=[240,224,192,128]
tmp=0
for i in range(1,A[0]):
tmp=0
for j in range(1,lenA):
delta=(A[j]*i)%A[0]
if delta>blockb[j] and delta<blocke[j]:
tmp=1
if tmp-1:
print i
通过这种性质选出,可以验证
,而52果然在候选的
中。
的可候选值的数量从151迅速下降到18,算法第一步到此结束。
再看算法的第二步:在第一步选出的进行分析,通过前
个锯齿曲线的间断点将
分成若干个子区间,然后在这些子区间上,看是否有满足超递增条件且模数大于所有超递增序列之和的解,也就是论文的如下处:
超递增条件与模数大于所有超递增序列之和分别对应第2,3个不等式。对所有的,它的每个子区间
,求解满足第2,3个不等式的解(在有的子区间上有可能为空)。
叶非花: 请问一下怎么安装第三方python包?
ckm1607011: 请安装sage:https://blog.csdn.net/ckm1607011/article/details/106724624
ckm1607011: 你可以认为G()是一个构造函数,g=G(rt)通过整数rt构造一个有限域上的元素g
聿十: 你好请问bsgs函数在哪个库里???
TIGER1693: 非0初始状态理解为生成随机数序列的种子k7k6...k0,而8元本原多项式可以对应于:c0=1(x^8系数为1),c1=0(x^7系数为0),c2=0,c3=0,c4=1,c5=1,c6=1,c7(x系数为0)=0。kj=kj-1 cj-1⊕kj-2 cj-2⊕...⊕k0 c0,也即k8=k7 c7⊕k6 c6⊕...⊕k0 c0。由初始种子就可以一步步推导出接下来的序列。个人理解,如有错误还请指正。