python - 从背包密码中的公钥计算私钥

Question

我为Merkle-Hellman 背包密码系统编写了一个 python 程序 目​​标是给定一个公钥 我必须找到一个有效的陷门秘密 这样得到的私钥是一个超级递增的私钥。还给出了vInverse/u ~ 0.3463790532。

所以我试图通过选择 vInverse 来找到一个有效的陷门秘密，以便它大约等于这个数字。

但不幸的是，程序永远不会终止。可能我需要巧妙地改变 vInverse 或者我做错了什么。

A = [6517080, 1056695235, 1220060160, 26032114, 3005098, 12816924, 1019797155, 103947426,
     735394924, 1280688572, 830674258, 367353505, 687914, 640579625, 1072069574,
     1262094708, 631083560, 157426933, 1918918, 207931058, 315759016, 415500056,
     609903359, 536252023, 51883198, 936198737]
u = max(A)+1

# S = A * v^-1 mod u

found = False

def mod_function(a):
    return (a*vInverseJ2) % u_mod_element

def checkSuperIncreasing(S):
    S.sort()
    for index, element in enumerate(S):
        if(element <= sum(S[0:index])):
            return False
    return True

for i in range(u, 10*u, 1):
    vInverse = int(0.3463790532 * i)
    for vInverseJ in range(vInverse-100, vInverse+100+1):
        global vInverseJ2
        vInverseJ2 = vInverseJ
        global u_mod_element
        u_mod_element = i
        S = list(map(mod_function, A))
        if(checkSuperIncreasing(S)):
            print("u = ", u_mod_element, " , vInverse = ", vInverse)
            found = True
            break
    if found:
        break

# The set S may not be in a sorted order

标签： pythonencryption