Nguyên lý toán học của thuật toán Shamir Secret Sharing (SSS)
Thuật toán Shamir Secret Sharing (SSS) dựa trên bài toán nội suy đa thức (Polynomial Interpolation). Nguyên lý cốt lõi là chia một giá trị bí mật (Secret) thành n phần (Shares) sao cho chỉ cần tập hợp k phần (Threshold) là có thể khôi phục lại giá trị gốc, nhưng với bất kỳ tập hợp nào có ít hơn k phần thì không thể suy ra được gì về bí mật.
Ta cần một trường hữu hạn (Finite Field) để đảm bảo tính bảo mật và tránh rò rỉ thông tin qua phép tính số học thông thường. Chúng ta sẽ sử dụng trường GF(256) hoặc GF(p) với p là số nguyên tố lớn. Trong ví dụ thực tế này, ta dùng Python để minh họa toán học trước khi đưa vào Kernel.
Tạo đa thức ngẫu nhiên để che giấu Secret
Bước 1: Chọn một số nguyên tố p lớn hơn secret. Giả sử secret là S. Ta xây dựng đa thức f(x) bậc k-1 sao cho f(0) = S. Các hệ số a1, a2, ..., a(k-1) được chọn ngẫu nhiên từ khoảng [1, p-1].
Bước 2: Tạo n shares bằng cách tính các điểm (x, f(x)) với x là các giá trị khác 0 (thường là 1 đến n).
Ta viết script Python để xác nhận nguyên lý toán học này chạy chính xác trên hệ thống Linux của bạn.
#!/usr/bin/env python3
# Lưu file: /root/sss_math_verify.py
import random
# Tham số cấu hình
p = 257 # Số nguyên tố (Field size), phải lớn hơn secret
secret = 42 # Giá trị bí mật cần chia
k = 3 # Ngưỡng khôi phục (Threshold)
n = 5 # Tổng số shares (Total shares)
def generate_shares(secret, k, n, p):
# Bước 1: Tạo các hệ số ngẫu nhiên cho đa thức bậc k-1
# a[0] = secret, a[1]...a[k-1] là ngẫu nhiên
coefficients = [secret]
for _ in range(k - 1):
coefficients.append(random.randint(1, p - 1))
shares = []
# Bước 2: Tính n điểm (x, y)
for x in range(1, n + 1):
y = 0
for i, coeff in enumerate(coefficients):
y += coeff * (x ** i)
y = y % p
shares.append((x, y))
return shares, coefficients
def recover_secret(shares, k, p):
# Sử dụng công thức nội suy Lagrange
secret = 0
for i, (xi, yi) in enumerate(shares):
# Tính hệ số Lagrange L_i(0)
numerator = 1
denominator = 1
for j, (xj, yj) in enumerate(shares):
if i != j:
numerator *= (0 - xj)
denominator *= (xi - xj)
# Tính nghịch đảo modulo p của denominator
# Vì p là số nguyên tố, dùng định lý Fermat nhỏ: a^(p-2) = a^-1 (mod p)
denom_inv = pow(denominator, p - 2, p)
term = (yi * numerator * denom_inv) % p
secret = (secret + term) % p
return secret
if __name__ == "__main__":
print(f"Secret gốc: {secret}")
shares, coeffs = generate_shares(secret, k, n, p)
print(f"Shares tạo ra: {shares}")
# Lấy ngẫu nhiên k shares để khôi phục
selected_shares = shares[:k]
recovered = recover_secret(selected_shares, k, p)
print(f"Khôi phục từ {k} shares: {recovered}")
# Verify: Thử với k-1 shares (phải fail hoặc ra số ngẫu nhiên không khớp)
if k > 1:
partial_shares = shares[:k-1]
partial_recovered = recover_secret(partial_shares, k-1, p)
print(f"Khôi phục từ {k-1} shares (sai threshold): {partial_recovered} (Không khớp với {secret})")
Kết quả mong đợi: Script in ra Secret gốc là 42, sau đó khôi phục lại đúng 42 từ 3 shares. Khi chỉ dùng 2 shares (k-1), giá trị khôi phục sẽ khác 42, chứng tỏ không thể suy ra secret.
Verify kết quả phần này
Chạy lệnh sau để xác nhận logic toán học hoạt động:
chmod +x /root/sss_math_verify.py && python3 /root/sss_math_verify.py
Đầu ra phải hiển thị dòng "Khôi phục từ 3 shares: 42" và dòng cuối cùng hiển thị giá trị khác 42.
So sánh SSS với các phương pháp mã hóa và dự phòng truyền thống
Để hiểu rõ lợi thế của kiến trúc phân tán dựa trên SSS, ta cần so sánh trực tiếp với hai phương pháp phổ biến: Mã hóa đối xứng (Symmetric Encryption) và RAID (Redundant Array of Independent Disks).
So sánh với Mã hóa đối xứng (AES)
Trong mô hình mã hóa AES, toàn bộ dữ liệu được mã hóa bằng một khóa duy nhất (Key). Nếu khóa này bị mất, dữ liệu mất vĩnh viễn. Nếu khóa bị đánh cắp, toàn bộ dữ liệu bị lộ.
SSS giải quyết vấn đề "Single Point of Failure" của khóa. Thay vì lưu 1 khóa, ta chia khóa thành n shares. Để mở khóa, cần tập hợp k shares. Điều này tạo ra tính bảo mật "Threshold Cryptography".
So sánh với RAID (RAID 5/6)
RAID 5 và RAID 6 sử dụng Parity để dự phòng. RAID 5 chịu được 1 đĩa hỏng, RAID 6 chịu được 2 đĩa hỏng. Tuy nhiên, Parity là dữ liệu dư thừa có thể suy ra dữ liệu gốc nếu biết đủ số lượng dữ liệu còn lại (thường là n-1 hoặc n-2).
SSS khác biệt ở chỗ: Các shares trong SSS (với k > 1) không chứa bất kỳ thông tin nào về secret. Ngay cả khi kẻ tấn công chiếm được n-1 shares, họ vẫn không biết gì về secret. Đây là tính "Information-Theoretic Security" (Bảo mật tuyệt đối về mặt thông tin) mà RAID không có.
Bảng so sánh kỹ thuật
Ta tạo file cấu hình so sánh để làm tài liệu tham khảo cho thiết kế hệ thống.
cat > /etc/sss_architecture/comparison.md Mất an toàn hoàn toàn.
- RAID: Không có bảo mật. Dữ liệu và Parity đều rõ văn bản (hoặc được mã hóa riêng). Parity giúp khôi phục nhưng không che giấu dữ liệu.
- SSS: Bảo mật tuyệt đối (Perfect Secrecy) nếu k > số shares bị lộ. k-1 shares không cung cấp thông tin gì về secret.
## 2. Khả năng chịu lỗi (Fault Tolerance)
- AES: Nếu mất key -> Mất dữ liệu vĩnh viễn. Không có khả năng tự phục hồi.
- RAID: Chịu được m đĩa hỏng (m=1 cho RAID5, m=2 cho RAID6). Cần ít nhất n-m đĩa còn lại.
- SSS: Chịu được mất n-k shares. Cần ít nhất k shares để khôi phục. Có thể cấu hình linh hoạt (ví dụ: 5 shares, cần 3).
## 3. Chi phí lưu trữ (Storage Overhead)
- AES: 1 bản copy dữ liệu + 1 key. Overhead ~0%.
- RAID 5: Overhead ~1/(n-1). RAID 6: Overhead ~2/(n-2).
- SSS: Overhead = n shares. Mỗi share có kích thước tương đương secret (hoặc lớn hơn một chút do overhead field). Tổng kích thước = n * Size(Secret).
## 4. Tính toán (Computational Cost)
- AES: Rất nhanh (Hardware AES-NI).
- RAID: Phép toán XOR đơn giản.
- SSS: Phép tính trên trường hữu hạn (Modular Arithmetic), nội suy Lagrange. Tốn CPU hơn AES và RAID đáng kể.
## Kết luận cho kiến trúc phân tán
- Dùng SSS khi: Cần chia sẻ quyền truy cập (Multi-sig), bảo vệ Key master, hoặc yêu cầu bảo mật cao hơn RAID.
- Dùng RAID khi: Cần hiệu năng I/O cao, dữ liệu không nhạy cảm, hoặc dự phòng đơn giản.
- Dùng AES khi: Mã hóa dữ liệu tĩnh (Data at rest) với một điểm quản lý khóa duy nhất.
EOF
Kết quả mong đợi: File so sánh được tạo tại /etc/sss_architecture/comparison.md với nội dung đầy đủ.
Verify kết quả phần này
Kiểm tra nội dung file vừa tạo:
cat /etc/sss_architecture/comparison.md | grep -A 3 "Kết luận cho kiến trúc"
Đầu ra phải hiển thị phần kết luận về việc khi nào dùng SSS, RAID và AES.
Thiết kế kiến trúc lưu trữ dữ liệu phân tán dựa trên ngưỡng (threshold)
Dựa trên nguyên lý SSS và so sánh ở trên, ta thiết kế kiến trúc hệ thống lưu trữ phân tán. Kiến trúc này sẽ không lưu dữ liệu gốc (Raw Data) mà lưu các "Shares" của khóa mã hóa hoặc chính dữ liệu đã được chia nhỏ.
Mô hình Topology: Client - Coordinator - Storage Nodes
1. Client: Nơi phát sinh dữ liệu. Client chia secret thành n shares và gửi đi.
2. Coordinator (Manager): Quản lý metadata (vị trí của shares, ngưỡng k). Coordinator KHÔNG lưu trữ secret hay shares. Nó chỉ biết "Share 1 nằm ở Node A, Share 2 nằm ở Node B...".
3. Storage Nodes (Shards): Các máy chủ lưu trữ từng share. Mỗi node chỉ biết mình đang lưu một share, không biết nội dung share đó là gì nếu share được mã hóa thêm.
Thiết kế cấu hình ngưỡng (Threshold Configuration)
Chúng ta cần một file cấu hình định nghĩa chính sách phân tán cho toàn hệ thống. File này sẽ được đọc bởi module Kernel hoặc User-space daemon.
Đường dẫn file: /etc/sss_dist/config.json
mkdir -p /etc/sss_dist
cat > /etc/sss_dist/config.json
Kết quả mong đợi: File JSON hợp lệ được tạo, định nghĩa 5 nodes với cấu hình threshold 3-of-5.
Thiết kế luồng dữ liệu (Data Flow)
1. Ghi (Write):
- Client nhận Secret.
- Client (hoặc Module Kernel) thực thi hàm SSS: Input = Secret, k=3, n=5. Output = [Share1, Share2, Share3, Share4, Share5].
- Hệ thống phân phối: Share1 -> Node Alpha, Share2 -> Node Beta, v.v.
- Metadata (ID của secret, danh sách nodes) -> Coordinator.
2. Đọc (Read):
- Client gửi yêu cầu Read ID đến Coordinator.
- Coordinator trả về danh sách 5 nodes chứa shares.
- Client (hoặc Module) kết nối đến bất kỳ 3 nodes nào (ví dụ: Alpha, Beta, Gamma).
- Thu thập 3 shares -> Thực thi hàm nội suy Lagrange -> Khôi phục Secret.
File cấu trúc dữ liệu cho Kernel Module (Header)
Để chuẩn bị cho Phần 3 (Xây dựng module), ta định nghĩa cấu trúc dữ liệu C sẽ dùng trong Kernel để quản lý shares. File này nằm trong thư mục nguồn.
mkdir -p /root/sss_kernel/src
cat > /root/sss_kernel/src/sss_types.h
Kết quả mong đợi: File header C hợp lệ được tạo, định nghĩa các struct cần thiết để lưu trữ và truyền tải shares trong không gian Kernel.
Verify kết quả phần này
Kiểm tra cú pháp file header C và cấu hình JSON:
gcc -fsyntax-only -I/usr/include/linux /root/sss_kernel/src/sss_types.h && python3 -c "import json; json.load(open('/etc/sss_dist/config.json'))" && echo "Kiểm tra cú pháp thành công"
Đầu ra phải là "Kiểm tra cú pháp thành công". Nếu có lỗi, kiểm tra lại dấu ngoặc hoặc include trong file.
Điều hướng series:
Mục lục: Series: Triển khai Database phân tán với Shamir Secret Sharing và Linux Kernel Modules
« Phần 1: Chuẩn bị môi trường: Phần cứng, hệ điều hành và công cụ cần thiết
Phần 3: Xây dựng module Linux Kernel: Cơ bản về cấu trúc và API »