10. Gyakorlat

RöpZH

Tekintsük a Z19[x]-beli p(x) = 4x^5 + 13x^4 + x^3 + 7x^2 + 15 Shamir titokmegosztáshoz használt polinomot. Mi volt az eredeti titok?

p = GF(19)['x'](4*x^5 + 13*x^4 + x^3 + 7*x^2 + 15)

p

p(1)

p(2)

p(3)

# (1, 2), (2, 7), (3, 2)

1. feladat

Írjon SSS_secret_pieces_from_primenum_and_coeffs(num_of_people, secret, primenum, coeff) szignatúrával függvényt, amely a secret titkokból num_of_people db titokrészletet készít, ahol a használt prímszám primenum legyen, coeff pedig tartalmazza a polinom szabad tagján kívüli együtthatókat.

def SSS_secret_pieces_from_primenum_and_coeffs(num_of_people, secret, primenum, coeff):

list_of_coeff = coeff + [secret]

list_of_coeff.reverse()

p = GF(primenum)['x'](list_of_coeff)

#print(p)

result = list()

for i in [1..num_of_people]:

result.append((i, p(i)))

return result

SSS_secret_pieces_from_primenum_and_coeffs(4, 5, 7, [4, 3]) # 4x^2 + 3x + 5

# (1, 5), (2, 6), (3, 1), (4, 4)

GF(19)['x']([1, 2, 3])

# 3*x^2 + 2*x + 1

SSS_secret_pieces_from_primenum_and_coeffs(7, 1344, 2017, [10, 11, 12, 13, 14])

# [(1, 1404), (2, 2016), (3, 1114), (4, 1313), (5, 1024), (6, 1705), (7, 993)]

2. feladat

Írjon SSS_compute_secret(primenum, secret_pieces) szignatúrával függvényt, amely a secret_pieces titokrészletekből előállítja a titkot, a használt prímszám pedig primenum.

def SSS_compute_secret(primenum, secret_pieces):

p = GF(primenum)['x'].lagrange_polynomial(secret_pieces)

return p.constant_coefficient() # return p(0)

SSS_compute_secret(7, [(1, 5), (3, 1), (4, 4)]) # p = 4x^2 + 3x + 5 -> szabad tag (5)

# 5

SSS_compute_secret(7, [(1, 5), (3, 1)])

# 0

SSS_compute_secret(2017, [(1, 1404), (2, 2016), (3, 1114), (4, 1313), (5, 1024), (6, 1705)])

# 1344

3. feladat

Írjon get_possible_secrets(primenum) szignatúrával függvényt, amely egy Shamir titokmegosztáskor használt prímszámot kap paraméterként, és visszatér a lehetséges titok listájával.

def get_possible_secrets(primenum):

#result = list()

#for i in [previous_prime(primenum)..primenum]:

# result.append(i)

#return result

return [previous_prime(primenum)..primenum-1]

get_possible_secrets(7) # [5, 6]

get_possible_secrets(11) # [7, 8, 9, 10]

get_possible_secrets(51) # [47, 48, 49, 50]

def get_possible_secrets(primenum):

i = primenum - 1

res = list()

while i >= 0:

res.append(i)

prev = i

i -= 1

if is_prime(prev):

break

return res

get_possible_secrets(7) # [6, 5]

get_possible_secrets(11) # [10, 9, 8, 7]

get_possible_secrets(51) # [10, 9, 8, 7]