Merkleho-Hellmanova knapsack schéma¶

In [1]:
# vygeneruj superrastúcu postupnosť pre parameter n (r0 priblične 2^n)
def gen_SR(n):
    r = [2^n+randint(1,7)]
    s = r[0]
    for i in range(1,n):
        x = s + randint(3,777)
        r.append(x)
        s = s+x
    return r

# rieš knapsack pre superrastúcu postupnosť
def solve_SR(r, s):
    x = []
    for ri in r[::-1]:
        if s>= ri:
            x.append(1)
            s = s-ri
        else:
            x.append(0)
    return x[::-1] if s==0 else False

# generuj Merkleho-Hellmanovu schému, parameter n
def gen_MH(n):
    r = gen_SR(n)
    sumr = sum(r)
    while True:
        m = sumr + randint(sumr,2*sumr)
        w = randint(m,2*m)
        if gcd(m,w) == 1:
            break
    a = [ri*w % m for ri in r]
    return (a, (m,w,r))

# šifrovanie v MH schéme
def enc_MH(a, x):
    return sum(a[i]*x[i] for i in range(len(x)))

# dešifrovanie v MH schéme
def dec_MH(m, w, r, c):
    return solve_SR(r, c*inverse_mod(w,m) % m)
In [2]:
n = 10
(a,(m,w,r)) = gen_MH(n)
print(f'a = {a}\nm = {m}\nw = {w}\nr = {r}')
a = [442187, 190237, 361507, 305173, 1641077, 1050980, 1419996, 1179386, 1636468, 864689]
m = 1844473
w = 2276893
r = [1029, 1327, 2735, 5115, 10885, 21671, 42948, 85986, 172431, 344255]
In [3]:
# testujeme korektnosť MH schémy
x = [randint(0,1) for _ in range(n)]
c = enc_MH(a,x)
x2 = dec_MH(m,w,r,c)
print(f'x = {x}\nc = {c}\nx2= {x2}\n{x==x2}')
x = [1, 1, 1, 1, 1, 0, 0, 0, 0, 0]
c = 2940181
x2= [1, 1, 1, 1, 1, 0, 0, 0, 0, 0]
True

Rekonštrukcia otvoreného textu pomocou LLL algoritmu¶

In [4]:
# konštrukcia bázy mriežky
def make_lattice(a, c, b = 1):
    rows = []
    n = len(a)
    for i in range(n):
        v = [0]*i + [1] + [0]*(n-i-1) + [-a[i]*b]
        rows.append(v)
    rows.append([0]*n + [c*b])
    return Matrix(rows)

B = make_lattice(a,c)
B
Out[4]:
[       1        0        0        0        0        0        0        0        0        0  -442187]
[       0        1        0        0        0        0        0        0        0        0  -190237]
[       0        0        1        0        0        0        0        0        0        0  -361507]
[       0        0        0        1        0        0        0        0        0        0  -305173]
[       0        0        0        0        1        0        0        0        0        0 -1641077]
[       0        0        0        0        0        1        0        0        0        0 -1050980]
[       0        0        0        0        0        0        1        0        0        0 -1419996]
[       0        0        0        0        0        0        0        1        0        0 -1179386]
[       0        0        0        0        0        0        0        0        1        0 -1636468]
[       0        0        0        0        0        0        0        0        0        1  -864689]
[       0        0        0        0        0        0        0        0        0        0  2940181]
In [5]:
# LLL
BL = B.LLL()
BL
Out[5]:
[ 1  1  1  1  1  0  0  0  0  0  0]
[ 0 -1  0  0 -1 -3  0  1  0  1 -2]
[ 1  2  0  0 -1  1 -2  0 -2  0  2]
[ 1  2 -1 -1  1  1 -1  1  2  0 -2]
[-1 -1  2  1 -1  2 -1 -1 -2 -1 -1]
[ 3  0  0 -3  1  0  1  0  2 -1  0]
[ 2  0 -2  1 -1  1 -1  0  2 -2  2]
[-1  1  1  0  1 -1  2  3 -2 -1  2]
[-1 -2 -1 -1  3 -1 -2 -1  1  0  0]
[-3  0  2  0  0 -1  0 -1  3  1  1]
[ 0  3  1 -2  0 -1  1 -3  1 -2 -1]
In [6]:
# BKZ
BK = B.BKZ()
BK
Out[6]:
[ 1  1  1  1  1  0  0  0  0  0  0]
[ 0 -1  0  0 -1 -3  0  1  0  1 -2]
[ 1  2  0  0 -1  1 -2  0 -2  0  2]
[ 1  2 -1 -1  1  1 -1  1  2  0 -2]
[-1 -1  2  1 -1  2 -1 -1 -2 -1 -1]
[ 2 -2  1 -2  0 -1  2 -1  0 -1  2]
[ 2  0 -2  1 -1  1 -1  0  2 -2  2]
[-1  1  1  0  1 -1  2  3 -2 -1  2]
[-1 -2 -1 -1  3 -1 -2 -1  1  0  0]
[-3  0  2  0  0 -1  0 -1  3  1  1]
[ 0  3  1 -2  0 -1  1 -3  1 -2 -1]
In [7]:
# hľadáme prvý vhodný vektor ako riešenie (obsahujúci len 0 a 1)
def find_sol(M):
    for row in M.rows():
        if set(row).issubset(set([0,1])) and row[-1]==0:
            return row[:-1]
    return [False]

# hľadáme vhodný vektor ako riešenie (najkratší vektor)
def find_sol2(M):
    nmin = M.rows()[0].norm()
    vmin = M.rows()[0]
    for row in M.rows()[2:]:
        if row.norm() < nmin:
            nmin = row.norm()
            vmin = row
    return vmin[:-1]
In [8]:
x3 = find_sol(BL)
x4 = find_sol2(BL)
print(f'x = {x}\nx3= {x3} {list(x3)==x}\nx4= {x4} {list(x4)==x}')
x = [1, 1, 1, 1, 1, 0, 0, 0, 0, 0]
x3= (1, 1, 1, 1, 1, 0, 0, 0, 0, 0) True
x4= (1, 1, 1, 1, 1, 0, 0, 0, 0, 0) True

Skúsme väčšiu inštanciu¶

In [9]:
n = 40
(a,(m,w,r)) = gen_MH(n)
print(f'a[:2] = {a[:2]}\nm = {m}\nw = {w}\nr[:2] = {r[:2]}')
x = [randint(0,1) for _ in range(n)]
#x = [1]*20 + [0]*(n-20)
c = enc_MH(a,x)
x2 = dec_MH(m,w,r,c)
print(f'x = {x}\nc = {c}\nx2= {x2}\n{x==x2}')
a[:2] = [684954160262858096446544, 1233856240567765898033623]
m = 1504032659380098368460081
w = 2557282124799839183984972
r[:2] = [1099511627779, 1099511628008]
x = [1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0]
c = 14176063363006447536716869
x2= [1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0]
True
In [10]:
B = make_lattice(a,c)
BL = B.LLL()
In [11]:
x3 = find_sol(BL)
x4 = find_sol2(BL)
print(f'x = {x}\nx3= {x3} {list(x3)==x}\nx4= {x4} {list(x4)==x}')
x = [1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0]
x3= [False] False
x4= (1, -1, 0, 0, -2, -1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -2, 1, 0) False
In [12]:
print(x4.norm().n(20))
print(vector(x).norm().n(20))
3.6056
4.1231
In [13]:
BK = B.BKZ()
x3 = find_sol(BK)
x4 = find_sol2(BK)
print(f'x = {x}\nx3= {x3} {list(x3)==x}\nx4= {x4} {list(x4)==x}')
print(x4.norm().n(20))
print(vector(x).norm().n(20))
x = [1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0]
x3= [False] False
x4= (-1, -1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, -1, 0, 0, 0, 0, 0, 0, 0, -2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0) False
3.6056
4.1231
In [ ]: