Chia sẻ thông tin mật – Secret Sharing

Related Articles

Watermarking

25/04/2020

Ẩn tin mật trên âm thanh – Audio steganography

25/02/2020

Ẩn tin mật trên ảnh – Image steganography

25/02/2020

Bài toán chia sẻ thông tin mật – Secret Sharing

Giả sử ta muốn chia sẻ một thông tin mật S cho n người

• Ta muốn phải có ít nhất là k người (k ≤ n) thì mới tái tạo được S
• Còn nếu có ít hơn k người thì sẽ không tái tạo được S (cũng không biết gì về S)

Giải pháp:

Chia thông tin mật S thành n phần S1, S2, … , Sn sao cho:

• Với ít nhất là k phần bất kỳ (k ≤ n) thì sẽ tái tạo được S
• Với ít hơn k phần thì sẽ không biết gì về S

Phương pháp chia sẻ thông tin mật của Shamir

Phân chia thông tin mật

Input:

• Thông tin mật S (một con số)
• Số phần cần chia n
• Ngưỡng k

Quá trình thực hiện:

• Tạo hàm f là một đa thức bậc k − 1 sao cho f(0) = S
• S1 = (1, f(1)) , S2 = (2, f(2)) , S3 = (3, f(3)) , …

Tái tạo thông tin mật

Input:

• Ngưỡng k
• n’ phần của thông tin mật (n′ ≥ k)

Quá trình thực hiện:

• Tái tạo hàm f (đa thức bậc k − 1) từ k phần trong n′ phần
• S = f(0)

Tái tạo hàm f (đa thức bậc k − 1) từ k phần của thông tin mật

Tìm hàm đa thức bậc k − 1: từ k điểm x1, y1 , … , (xk, yk) với yi = f(xi) → k phương trình, k ẩn:

• (a_k−1)x1^k−1 + (a_k−2)x1^k−2 + ⋯ + a0 = y1
• (a_k−1)x2^k−1 + (a_k−2)x2^k−2 + ⋯ + a0 = y2
• …
• (a_k−1)xk^k−1 + (a_k−2)xk^k−2 + ⋯ + a0 = yk

Giải -> Dùng phương pháp nội suy Lagrange

Nội suy Lagrange

Ví dụ, tìm hàm f (hàm đa thức bậc 3) biết:
 f(5) = 3
 f(7) = 2
 f(12) = 6
 f(30) = 15

Ta chỉ cần tìm một hàm: (i) bậc 3, và (ii) đi qua 4 điểm ở trên

f(x) = 3δ5(x) + 2δ7(x) + 6δ12 =(x) + 15δ30(x)

với δi(x) là một hàm bậc 3 và δi(x) =

• 1 nếu x = i
• 0 nếu x ∈ 5,7,12,30 − {i}
• “bất kỳ” trong những trường hợp khác

δ5(x) =(x − 7)/(5 − 7) (x − 12)/(5 − 12) (x − 30)/(5 − 30)

Ví dụ

S = 6, n = 3, k = 2

Phương pháp Shamir:

• Bước 1: tạo hàm f là một đa thức bậc nhất sao cho f(0) = S. Ví dụ, f(x) = −0.5x + 6
• Bước 2: S1 = (1, f(1)), S2 = (2, f(2)), S3 = (3, f(3))

Source code (python)