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: [có dạng: f(x) = (a_k−1x)^k−1 + (a_k−2x)^k−2 + ⋯ + a_0)] 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)

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…

User Rating: 5 ( 1 votes)

About ngoton

Ngô Tôn is a programmer with passion for tailored software solutions. Comes with 6+ 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

Phương pháp dùng khoảng trắng của văn bản Ví dụ: bit 0 = 1 khoảng …

Leave a Reply

Your email address will not be published. Required fields are marked *