论文部分内容阅读
格基归约是格理论研究的一个重要内容，许多格上问题都通过归约来求解。LLL归约算法能够在多项式时间内找到格的一个短向量，该短向量的长度不超过格中最短向量长度的2(n-1)/2倍，其中n表示格中每个向量的长度。 MH背包密码方案是一个公钥密码体制，它的数学基础是基于子集和问题。目前，存在多种方法对MH背包算法进行攻击，LLL格基归约算法就是其中的一种。利用LLL算法将对MH背包算法的分析转换成寻找一个格中的最短向量，在这个最短向量中可能包含背包算法的解。 通过现有的研究发现利用LLL算法分析MH背包算法并不一定总能成功，存在一定的概率，这与背包算法中背包的长度和密度有密切的关系，也与LLL算法中的部分参数有一定的联系。论文所要做的工作就是利用实验的方法找出MH背包算法中背包长度和密度的阈值，直到能够抵抗LLL算法的分析。在实验的过程中，测试成功率与LLL算法中参数的关系，从而对其进行优化。 实验通过分组进行，在测试背包的密度对成功率的影响时，先固定背包的长度，然后逐渐增加背包的密度，实验中，背包的长度分别为70，80，90。具体的说，当背包的长度为80时，背包的密度从0.656逐渐增加到3.2，成功率从60％下降到7％，这说明当成功率随着背包密度的增加而逐渐降低。同样，在测试背包的长度对成功率的影响时固定背包的密度，然后逐渐增加背包的长度，实验中，将背包的密度分别固定为0.7，0.8，0.9。当背包的密度为0.8时，背包的长度从48增加到264，成功率从58％降低到4％，这说明成功率随着背包长度的增加而降低。