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 [ ]: