Hi, I am

Ngô Tôn

I am a programmer.

Home / HCMUS / Data Hiding and Secret Sharing / Chia sẻ thông tin mật – Secret Sharing

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

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)

About ngoton

Ngô Tôn is a programmer with passion for tailored software solutions. Comes with 7+ years of IT experience, to execute beautiful front-end experiences with secure and robust back-end solutions.

Check Also

Ẩn tin mật trên văn bản – Text steganography

Mục lục Phương pháp dùng khoảng trắng của văn bảnPhương pháp dùng khoảng trắng giữa …

4
Leave a Reply

avatar
2 Comment threads
2 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
3 Comment authors
HaungotonNguyen Dao Vinh Hai Recent comment authors
  Subscribe  
newest oldest most voted
Notify of
Nguyen Dao Vinh Hai
Guest
Nguyen Dao Vinh Hai

Em có thể tham khảo source code python về thuật toán shamir được không ạ ? Em xin cảm ơn

Hau
Guest
Hau

Bạn có thể gửi cho mình source code tham khảo với ạ. thanks bạn