Source code Chia sẻ khóa bí mật dựa trên sơ đồ ngưỡng Shamir bằng javascript

Mô tả

Lược đồ chia sẻ bí mật Shamir
Lược đồ chia sẻ bí mật Shamir, được phát triển bởi Adi Shamir vào năm 1979, là một kỹ thuật chia sẻ bí mật hiệu quả để phân phối thông tin cá nhân ("bí mật"). Lược đồ sử dụng một đa thức bậc (k-1) với hệ số tự do là bí mật cần được bảo vệ. Các “shares” (thành phần chia sẻ) được tạo ra bằng cách tính giá trị của đa thức tại các điểm khác nhau. Để tái tạo bí mật, cần phải thu thập đủ số lượng thành phân chia sẻ tối thiểu là (k).

Mô tả lược đồ chia sẻ bí mật Shamir
A. Các tham số
- Không gian thông điệp: K là tập hợp các thông điệp khả dĩ mà có thể làm đầu vào của thuật toán chia sẻ thông điệp.
- Không gian phần thông điệp chia sẻ: giống như không gian thông điệp, là tập hợp các phần thông điệp chia sẻ khả dĩ mà có thể được xuất ra bởi thuật toán chia sẻ thông điệp.
- Số lượng các phần thông điệp chia sẻ: n, sao cho n≥2, n - Ngưỡng: k, sao cho n≥k≥2. sao cho bất kỳ k phần thông điệp chia sẻ nào cũng đủ để thực hiện thành công thuật toán tái tạo thông điệp.
- Các phần tử trường cố định: xi∈ K với 1 ≤ i ≤ n.
CHÚ THÍCH: Giả định rằng người nhận biết được các phần tử trường cố định. Các phần tử này có thể được gửi đến người nhận với phần thông điệp chia sẻ tương ứng hoặc được công bố dưới dạng tham số hệ thống.

B. Thuật toán chia sẻ thông điệp
- Đầu vào: thông điệp a ∈ K
- Đầu ra: Véc tơ chia sẻ ([a]1,..., [a]n) ∈ Kn
Chọn một cách ngẫu nhiên (r1,..., rk-1) ∈ K
Tính toán [a]i=a+j=1k-1rjxij∈ K với 1 ≤ i ≤ n
Xuất ra ([a]1,..., [a]n) ∈ Kn

C. Thuật toán tái tạo thông điệp
- Đầu vào: véc tơ chia sẻ ai1,…,aik∈Kk
- Đầu ra: thông điệp a∈K
Tính toán a=j=1kaiju=1,u≠jk(0-xiu)/(xij-xiu) ∈K
Tính toán a∈K
CHÚ THÍCH: Thuật toán tái tạo còn được biết tới là đa thức nội suy Lagrange. Nếu fx=a+j=1k-1rjxij thì thông điệp bí mật là f(0) và mỗi phần thông điệp chia sẻ [a]i là f(xi). Vì f(x) là một đa thức bậc k, f(0) có thể được tính từ tọa độ k sử dụng phép nội suy Lagrange.

D. Thuộc tính bảo mật
- Tính bí mật: Lược đồ chia sẻ bí mật Shamir hoàn toàn bảo mật lý thuyết thông tin khi người nhận chỉ có quyền truy cập đến ít hơn k phần thông điệp chia sẻ.
- Tỷ lệ thông tin: lược đồ chia sẻ bí mật Shamir có tỷ lệ thông tin là 1, vì kích thước của thông điệp và phần thông điệp chia sẻ giống như kích thước của một phần tử của trường hữu hạn K. Do đó, lược đồ này là lý tưởng.
- Phép toán đồng cấu: Lược đồ chia sẻ bí mật Shamir là đồng cấu (+, +), trong đó phép cộng trên véc tơ chia sẻ được thực hiện bằng cách tính [a+a']i=[a]i+[a']i.
- Độ phức tạp: Thuật toán chia sẻ thông điệp cần (k - 1) n phép nhân và (k-1) n phép cộng. Thuật toán tái tạo thông điệp cần k phép chia, 2k2 - 3k phép nhân và k2-1 phép cộng. Nếu bất cứ điều gì không liên quan đến a hoặc rj với 1≤j≤k-1 đã được chuẩn bị sơ bộ, cả hai thuật toán đều cần k phép nhân và k-1 phép cộng.