CHƯƠNG 2. CÁC GIAO THỨC THỎA THUẬN KHÓA
2.1. Giao thức phân phối khóa
2.1.4. Sơ đồ chia sẻ bí mật ngƣỡng Shamir
Trên thực tế đôi khi xuất hiện bài toán chia sẻ bí mật cho một số người, với điều kiện là mỗi một người trong số đó chỉ có một phần bí mật (khóa mật). Và khóa mật đƣợc khôi phục khi liên kết tất cả hoặc một số lƣợng đủ lớn các thành viên có phần bí mật. Rõ ràng rằng khi liên kết tất cả các người có phần bí mật thì sẽ khôi phục được bí mật. Thế nhưng bài toán này đặt ra tình huống trên thực tế, một số người trong số đó vì lý do sức khỏe hay đi công tác, số người còn lại vẫn có thể khôi phục được khóa mật để đảm bảo công việc. Cho nên bài toán ở đây là có khả năng khôi phục đƣợc khóa mật trong trường hợp không tham gia của tất cả thành viên, nhưng chỉ khôi phục đƣợc khóa mật khi và chỉ khi số lƣợng thành viên tham gia khôi phục phải lớn hơn hoặc bằng ngƣỡng nào đó.
Input:
+ Số nguyên tố
+ Ngƣỡng
+ Số lƣợng thành viên + Các giá trị công khai + Các giá trị bí mật Output: Khóa chung bí mật
Method:
Một nhà phân phối D muốn chia sẽ bí mật cho thành viên, với , là số nguyên tố đủ lớn, ví dụ p có độ lớn là 512 bít. Và D muốn xây dựng ngƣỡng bằng k, bằng cách D chọn một đa thức ngẫu nhiên có bậc là , trong đa thức này hằng số là . Sơ đồ này cho nhƣ sau:
1. D chọn n phần tử trong , với với và với . Mỗi thành viên sẽ có một giá trị . Các giá trị là công khai.
2. D muốn chia sẻ khóa . D chọn ngẫu nhiên và độc lập phần tử thuộc . Các giá trị là bí mật.
3. Với 1in, D tính , trong đó ∑
4. D trao cho , với .
Bây giờ chúng ta xem xét liệu có một nhóm B gồm k thành viên có thể khôi phục đƣợc bí mật S hay không. Giả sử rằng các thành viên của nhóm B là muốn xác định bí mật . Nhóm này biết rằng:
Với và . Đa thức có bậc lớn nhất là nên có thể viết dưới dạng sau:
Ở đây thuộc Zp là các phần tử mật do D chọn và Chúng ta thu được hệ phương trình tuyến tính gồm k phương trình như sau:
{
Hệ này có thể viết lại nhƣ sau:
[
]
[
] [ ]
Đặt [
]
Chúng ta thấy ma trân A là ma trận Vandermonde. Định thức của ma trận này đƣợc tính theo công thức sau:
∏ ( )
Vì với nên không có thành phần nào của tích trên là bằng không. Mà tích này tính trong nên , nên hệ có nghiệm duy nhất.
Và rõ ràng nếu nhƣ có một nhóm có số lƣợng thành viên nhỏ hơn k muốn khôi phục k, thì họ sẽ thành lập một hệ mới có t ẩn nhƣng số lƣợng phương trình nhỏ hơn số ẩn nên hệ họ thu được không thể có nghiệm duy nhất.
VD2.4. Giả sử , , và các giá trị công khai , , giả sử D chọn các tham số bí mật và tính ra các giá trị .
Giả sử nhóm B={P1,P3,P5}, tương ứng với các giá trị của nhóm là y1=8, y2=10 và y5=11.
Khi đó nhóm B thu được hệ 3 phương trình tuyến tính sau:
{
Giải hệ này ta thu đƣợc nghiệm duy nhất là . Vậy khóa .
Tính chất của sơ đồ ngưỡng Shamir:
- Hoàn hảo theo nghĩa nếu có ít hơn giá trị thì mọi giá trị nằm trong khoảng [0, p – 1] đều có thể là .
- Lý tưởng theo nghĩa là độ dài bit của các chia sẻ bằng với độ dài bit của S.
- Khả năng mở rộng khi có thêm người dùng mới. tính thêm rồi chuyển giá trị cho người sử dụng mới gia nhập hệ thống, những giá trị của những người khác không hề thay đổi.
- Dễ dàng thay đổi mức độ điều khiển. Thành viên càng có nhiều giá trị thì càng chi phối nhiều hơn vào quá trình tính .
- Không có giả thiết nào không thể chứng minh đƣợc. Không giống nhƣ nhiều sơ đồ mã hóa khác, tính an toàn đặt dưới một giả thiết chưa được chứng minh đúng đắn bằng toán học.
Tổng quát hóa
Có thể tổng quát hóa sơ đồ ngưỡng như sau: Đưa ra tập tất cả người dùng P, xác định (cấu trúc truy nhập) là tập các tập con, đƣợc gọi là các tập con đƣợc quyền của . Các gói đƣợc tính toán và phân phối sao cho khi kết hợp các gói của các thành viên trong một tập con sẽ thu đƣợc giá trị của , nhưng nếu kết hợp các gói của những người trong tập sẽ không thể tính đƣợc giá trị của .
Các sơ đồ ngƣỡng là lớp đặc biệt của sơ đồ chia sẻ bí mật tổng quát, trong đó cấu trúc truy nhập bao gồm tất cả các tập con có người.