Source code demo chương trình chia sẻ khóa bí mật Shamir bằng java

Mô tả

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 <K, là phạm vi các giá trị có thể có của n được lược đồ hỗ trợ.

- 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.