Triển khai thuật toán Shamir trong không gian Kernel
Chúng ta sẽ viết mã C trực tiếp trong kernel module để thực hiện hai hàm cốt lõi: shamir_split (chia bí mật) và shamir_reconstruct (tái tạo bí mật). Khác với user space, kernel không được phép sử dụng thư viện chuẩn như math.h hay malloc một cách tùy tiện. Mọi thao tác phải tuân thủ nghiêm ngặt về quản lý bộ nhớ và an toàn.
Thiết lập môi trường biên dịch Kernel Module
Trước khi viết logic thuật toán, cần đảm bảo môi trường build có sẵn các header kernel tương ứng với kernel đang chạy. Chúng ta sẽ tạo thư mục làm việc và file Makefile.
Thư mục làm việc:
mkdir -p ~/kernel-sss/part4 && cd ~/kernel-sss/part4
Kết quả mong đợi: Thư mục được tạo và chuyển đổi vào thành công.
File Makefile để liên kết với source kernel:
cat > Makefile
Kết quả mong đợi: File Makefile được tạo sẵn sàng để biên dịch module.
Triển khai hàm chia bí mật (Split) trong Kernel
Hàm shamir_split nhận một giá trị bí mật secret, số lượng mảnh n và ngưỡng k. Trong kernel, chúng ta phải tự tạo các hệ số ngẫu nhiên cho đa thức P(x) = secret + a1*x + ... + ak-1*x^(k-1). Không dùng rand() user space, phải dùng get_random_bytes của kernel.
File nguồn shamir_kernel.c:
cat > shamir_kernel.c 0) {
if (exp % 2 == 1) {
/* Phép nhân modulo lớn, tránh overflow */
__u128 temp = (__u128)result * base;
result = temp % mod;
}
exp = exp >> 1;
__u128 temp = (__u128)base * base;
base = temp % mod;
}
return result;
}
/* Hàm tính nghịch đảo modulo (a^-1 % mod) sử dụng Extended Euclidean Algorithm */
static u64 mod_inv(u64 a, u64 mod) {
u64 t = 0, newt = 1;
u64 r = mod, newr = a;
u64 quotient, temp;
while (newr != 0) {
quotient = r / newr;
temp = t; t = newt; newt = t - quotient * newt;
temp = r; r = newr; newr = r - quotient * newr;
}
if (r > 1) return 0; /* Không tồn tại nghịch đảo */
if (t < 0) t = t + mod;
return t;
}
/* Hàm chia bí mật: secret -> n shares (cần k để khôi phục) */
static int shamir_split(u64 secret, int n, int k, struct shamir_point *shares) {
if (n < k || k < 1) return -EINVAL;
if (n > MAX_SHAMIR_POINTS) return -EINVAL;
/* Lấy hệ số ngẫu nhiên từ kernel entropy pool */
u64 coeffs[MAX_SHAMIR_POINTS];
coeffs[0] = secret;
/* Sinh k-1 hệ số ngẫu nhiên */
if (get_random_bytes(&coeffs[1], (k - 1) * sizeof(u64)) != 0) {
pr_err("%s: Failed to generate random coefficients\n", __func__);
return -ENOMEM;
}
/* Tính y = P(x) cho mỗi điểm x từ 1 đến n */
/* Sử dụng trường hữu hạn GF(2^64) đơn giản hoặc modulo số nguyên tố lớn */
/* Ở đây dùng modulo 2^64 (unsigned long long wrap-around) cho tốc độ cao */
for (int i = 1; i
Kết quả mong đợi: File C được tạo với các hàm tính toán số học lớn sử dụng __u128 để tránh tràn số khi nhân modulo.
Biên dịch và nạp module vào Kernel
Thực hiện lệnh biên dịch module. Cần quyền root hoặc sudo để truy cập thư mục source kernel.
make
Kết quả mong đợi: Xuất hiện file shamir_kernel.ko và không có lỗi biên dịch.
Nạp module vào hệ thống:
sudo insmod shamir_kernel.ko
Kết quả mong đợi: Không có thông báo lỗi, log kernel ghi dòng "Loaded. Testing internal logic...".
Verify module đã chạy:
lsmod | grep shamir_kernel
Kết quả mong đợi: Hiển thị tên module và kích thước bộ nhớ đang sử dụng.
Xử lý ràng buộc bộ nhớ và an toàn trong Kernel
Việc chạy code trong kernel space (Ring 0) mang lại rủi ro nghiêm trọng nếu xử lý bộ nhớ sai. Một lỗi phân cấp bộ nhớ (segfault) trong user space chỉ làm crash ứng dụng, nhưng trong kernel sẽ làm sập toàn bộ hệ điều hành (Kernel Panic).
Quản lý bộ nhớ động an toàn
Trong kernel, tuyệt đối không dùng malloc, calloc hay new. Phải sử dụng các hàm kmalloc, kzalloc (zeroed allocation) và giải phóng bằng kfree. Nếu cần bộ nhớ lớn (>128KB) hoặc bộ nhớ liên tục về vật lý (physically contiguous), phải dùng vmalloc hoặc __get_free_pages.
Ví dụ sửa đổi trong code để phân bổ bộ nhớ cho mảng shares động thay vì static:
/* Thay thế mảng static bằng động */
struct shamir_point *dynamic_shares = kmalloc(n * sizeof(struct shamir_point), GFP_KERNEL);
if (!dynamic_shares) {
pr_err("%s: Memory allocation failed\n", __func__);
return -ENOMEM;
}
/* Sử dụng dynamic_shares... */
kfree(dynamic_shares); /* Giải phóng khi xong */
Kết quả mong đợi: Code trở nên linh hoạt hơn, không giới hạn số lượng shares cứng nhắc, và an toàn hơn khi hệ thống thiếu RAM.
Tránh các hàm không an toàn (Sleeping functions)
Nếu code chạy trong ngữ cảnh interrupt (interrupt context) hoặc spinlock, không được phép gọi các hàm có thể gây ngủ (sleeping functions) như kmalloc(GFP_KERNEL) (vì nó có thể sleep), printk (có thể gây deadlock nếu buffer đầy), hay get_random_bytes (có thể sleep nếu entropy thấp).
Giải pháp: Sử dụng GFP_ATOMIC cho phân bổ bộ nhớ trong các đoạn code không được phép sleep.
/* Phân bổ bộ nhớ an toàn trong atomic context */
ptr = kmalloc(size, GFP_ATOMIC);
Kết quả mong đợi: Module không gây deadlock hoặc panic khi được gọi từ các hook kernel tốc độ cao.
Truy cập an toàn giữa User và Kernel Space
Đừng bao giờ truy cập trực tiếp vào pointer của user space trong kernel. Phải dùng copy_from_user và copy_to_user.
Giả sử chúng ta tạo một file /dev/shamir_dev để user space truyền dữ liệu vào:
/* Trong file_operation write */
static ssize_t shamir_write(struct file *file, const char __user *buf, size_t count, loff_t *pos) {
u64 secret;
struct shamir_point shares[MAX_SHAMIR_POINTS];
/* Copy dữ liệu từ user space vào kernel space */
if (copy_from_user(&secret, buf, sizeof(u64))) {
return -EFAULT; /* Lỗi truy cập bộ nhớ */
}
/* Xử lý logic ở đây... */
shamir_split(secret, n, k, shares);
/* Copy kết quả trở lại user space */
if (copy_to_user(buf + sizeof(u64), shares, count)) {
return -EFAULT;
}
return count;
}
EXPORT_SYMBOL(shamir_write);
Kết quả mong đợi: Bảo vệ kernel khỏi các pointer không hợp lệ từ user space, ngăn chặn exploit.
Tối ưu hiệu năng tính toán số học lớn
Thuật toán Shamir đòi hỏi nhiều phép nhân và nghịch đảo modulo trên số nguyên lớn. Trong kernel, chi phí gọi hàm (function call overhead) và branch misprediction có thể làm giảm hiệu năng đáng kể so với user space (có JIT hoặc thư viện tối ưu như GMP).
Inline Assembly và Unrolling
Để tối ưu, chúng ta khai báo các hàm tính toán số học là static inline để compiler mở rộng mã trực tiếp vào chỗ gọi, giảm chi phí gọi hàm. Ngoài ra, sử dụng __u128 (128-bit integer) có sẵn trong GCC/Clang để thực hiện phép nhân 64-bit x 64-bit mà không cần hàm phức tạp.
So sánh hiệu năng:
- Không tối ưu: Dùng hàm
mod_mul riêng biệt cho mỗi bước.
- Tối ưu: Dùng
__u128 và inline.
/* Tối ưu: Inline function với __u128 */
static inline u64 fast_mod_mul(u64 a, u64 b, u64 mod) {
__u128 res = (__u128)a * b;
return (u64)(res % mod);
}
/* Sử dụng trong vòng lặp */
for (int i = 0; i < k; i++) {
y = fast_mod_mul(y, x, mod); /* Không gọi hàm, code được mở rộng tại chỗ */
}
Kết quả mong đợi: Giảm số lần nhảy lệnh (jumps), tăng tốc độ tính toán lên 2-5 lần tùy kiến trúc CPU.
Sử dụng Pre-computed Tables cho trường nhỏ
Nếu làm việc với trường hữu hạn nhỏ (ví dụ GF(256) hoặc GF(2^16)), nên tạo bảng tra cứu (lookup table) cho phép nghịch đảo và lũy thừa. Tuy nhiên, với số nguyên 64-bit, bảng quá lớn. Giải pháp là dùng thuật toán Montgomery Multiplication để chuyển đổi phép nhân modulo thành phép nhân thông thường và dịch bit.
/* Khởi tạo hằng số Montgomery (ví dụ minh họa) */
static u64 montgomery_r2; /* R^2 mod m */
/* Trong hàm init, tính toán trước các hằng số này */
Kết quả mong đợi: Giảm độ phức tạp của phép modulo từ O(log n) xuống O(1) cho mỗi bước nhân trong vòng lặp.
Verify kết quả triển khai
Để đảm bảo thuật toán hoạt động chính xác, chúng ta sẽ viết một script kiểm thử đơn giản trong user space, gọi module qua /proc hoặc /sys (nếu đã expose interface) hoặc chạy test case trực tiếp trong kernel log.
Test case logic: Chia bí mật 12345 thành 5 mảnh với ngưỡng 3, sau đó lấy 3 mảnh bất kỳ để khôi phục.
/* Chèn đoạn code test vào hàm init của module */
static int __init shamir_init(void) {
u64 secret = 12345;
int n = 5, k = 3;
struct shamir_point shares[MAX_SHAMIR_POINTS];
u64 recovered;
pr_info("%s: Starting self-test...\n", MODULE_NAME);
/* Bước 1: Split */
if (shamir_split(secret, n, k, shares) != 0) {
pr_err("%s: Split failed\n", MODULE_NAME);
return -1;
}
pr_info("%s: Split successful. Shares generated.\n", MODULE_NAME);
/* Bước 2: Reconstruct với 3 điểm đầu tiên */
if (shamir_reconstruct(shares, k, &recovered) != 0) {
pr_err("%s: Reconstruct failed\n", MODULE_NAME);
return -1;
}
/* Bước 3: So sánh */
if (recovered == secret) {
pr_info("%s: SUCCESS! Recovered secret: %llu\n", MODULE_NAME, recovered);
} else {
pr_err("%s: FAILURE! Expected: %llu, Got: %llu\n", MODULE_NAME, secret, recovered);
return -1;
}
return 0;
}
/* Sau đó biên dịch lại và nạp module */
Kết quả mong đợi: Sau khi chạy sudo insmod shamir_kernel.ko, xem log bằng dmesg | tail sẽ thấy dòng "SUCCESS! Recovered secret: 12345".
Command để kiểm tra log:
dmesg | grep -i "shamir"
Kết quả mong đợi: Hiển thị toàn bộ quá trình test tự động của module, xác nhận thuật toán chia và hợp nhất đúng chuẩn.
Đ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 3: Xây dựng module Linux Kernel: Cơ bản về cấu trúc và API
Phần 5: Tích hợp module Shamir vào hệ thống tệp tin phân tán »