Tổng quan về thuật toán Kyber trong NIST PQC
Kyber (Cryptography for the Internet, a Secure, Resilient, and Efficient Algorithm) là thuật toán mã hóa khóa công khai dựa trên lưới (Lattice-based cryptography) đã được NIST chọn làm tiêu chuẩn PQC (Post-Quantum Cryptography) chính thức.
Khác với RSA hay ECC dựa trên bài toán phân tích số nguyên hoặc logarit rời rạc (bị phá vỡ bởi thuật toán Shor trên máy tính lượng tử), Kyber dựa trên bài toán Learning With Errors (LWE) và Module-LWE, được chứng minh là an toàn trước cả tấn công lượng tử.
Cơ chế hoạt động chính của Kyber bao gồm 3 hàm cốt lõi:
- KeyGen: Tạo cặp khóa (khóa công khai và khóa bí mật) từ các ma trận ngẫu nhiên trên lưới.
- Encapsulate (Encaps): Sử dụng khóa công khai để mã hóa một "shared secret" (bình thường là một giá trị ngẫu nhiên) thành ciphertext.
- Decapsulate (Decaps): Sử dụng khóa bí mật để giải mã ciphertext và khôi phục lại "shared secret" ban đầu.
Để xác minh hiểu biết về cấu trúc dữ liệu của Kyber, chúng ta sẽ tạo một file cấu hình giả lập kích thước tham số cho 3 mức độ an toàn (Kyber512, Kyber768, Kyber1024).
Việc xác định kích thước tham số là bước đầu tiên để hiểu cách Kernel sẽ phân bổ bộ nhớ cho các ma trận.
cat > /tmp/kyber_params_ref.txt
Kết quả mong đợi: File /tmp/kyber_params_ref.txt được tạo thành công, chứa các hằng số toán học định nghĩa kích thước ma trận và vector cho từng mức độ an toàn.
Verify kết quả bằng lệnh:
cat /tmp/kyber_params_ref.txt | grep -E "^KYBER768"
Phân tích cấu trúc thư viện KDF và CRYSTALS-Kyber trong Kernel
Trong Linux Kernel, việc tích hợp Kyber không đứng độc lập mà nằm trong kiến trúc crypto API và cụ thể là dưới module akcipher (asymmetric key cryptography) hoặc keyrings.
Thư viện CRYSTALS-Kyber gốc (C) cần được chuyển đổi sang chuẩn kernel coding style, loại bỏ các hàm I/O, dynamic memory allocation (như malloc/free) và thay thế bằng kmalloc/kfree hoặc sử dụng stack allocation nếu kích thước cố định.
Điểm mấu chốt là Key Derivation Function (KDF). Trong Kyber, sau khi giải mã (Decapsulate), shared secret sinh ra cần được qua một hàm KDF để tạo ra khóa hội nghị (session key) cho các thuật toán đối xứng (như AES-GCM). Kernel sử dụng SHA3-256 hoặc SHA3-512 cho mục đích này.
Cấu trúc thư mục nguồn tiêu chuẩn trong cây Linux Kernel cho PQC nằm tại:
crypto/postquantum/kyber/
Chúng ta sẽ phân tích cấu trúc file kyber.h giả lập để hiểu các struct cần thiết.
mkdir -p /tmp/kernel_mock/crypto/postquantum/kyber
cat > /tmp/kernel_mock/crypto/postquantum/kyber/kyber.h
Kết quả mong đợi: File kyber.h được tạo với các định nghĩa struct tương thích với kiến trúc kernel, bao gồm con trỏ bộ nhớ và tham số định cấu hình.
Verify kết quả bằng cách kiểm tra cú pháp C:
gcc -fsyntax-only -I/tmp/kernel_mock /tmp/kernel_mock/crypto/postquantum/kyber/kyber.h 2>&1 | head -n 5
Xác định các điểm tích hợp (hook) trong mã nguồn kernel cho mã hóa Post-Quantum
Để Kernel nhận diện và sử dụng Kyber, chúng ta cần hook vào cơ chế quản lý khóa Keyrings và AKCipher. Trong kernel hiện đại, điều này được thực hiện thông qua cấu trúc akcipher_alg.
Điểm tích hợp chính là file crypto/akcipher.c và file cấu hình crypto/Kconfig. Chúng ta cần đăng ký thuật toán Kyber như một akcipher mới.
File kyber.c (giả lập) sẽ chứa logic đăng ký này. Lưu ý: Trong thực tế, code này nằm trong cây nguồn kernel, nhưng ở đây chúng ta viết để minh họa cơ chế hook.
Chúng ta sẽ viết file kyber.c định nghĩa cấu trúc akcipher_alg trỏ vào các hàm kyber_keygen, kyber_encapsulate và kyber_decapsulate.
cat > /tmp/kernel_mock/crypto/postquantum/kyber/kyber.c h = crypto_shash_grab("sha3-256");
if (IS_ERR(ctx->h))
return PTR_ERR(ctx->h);
return 0;
}
static int kyber_exit(struct crypto_tfm *tfm)
{
struct kyber_ctx *ctx = crypto_tfm_ctx(tfm);
crypto_shash_put(ctx->h);
return 0;
}
/* Mapping kernel functions to Kyber logic */
static int kyber_akcipher_encrypt(struct akcipher_request *req)
{
struct kyber_ctx *ctx = crypto_akcipher_ctx(req->base.tfm);
/* Call internal kyber_encapsulate logic here */
return 0;
}
static int kyber_akcipher_decrypt(struct akcipher_request *req)
{
struct kyber_ctx *ctx = crypto_akcipher_ctx(req->base.tfm);
/* Call internal kyber_decapsulate logic here */
return 0;
}
static int kyber_akcipher_setkey(struct crypto_akcipher *tfm,
const u8 *key, unsigned int keylen)
{
struct kyber_ctx *ctx = crypto_akcipher_ctx(tfm);
/* Validate key length based on KYBER_512/768/1024 */
return 0;
}
/* Registration of the algorithm */
static struct akcipher_alg kyber_alg = {
.base = {
.cra_name = "kyber",
.cra_driver_name= "kyber-software",
.cra_priority = 100,
.cra_flags = CRYPTO_ALG_NEED_SKCIPHER,
.cra_module = THIS_MODULE,
.cra_ctxsize = sizeof(struct kyber_ctx),
.cra_init = kyber_init,
.cra_exit = kyber_exit,
},
.setkey = kyber_akcipher_setkey,
.encrypt = kyber_akcipher_encrypt,
.decrypt = kyber_akcipher_decrypt,
.max_pubkey_size = 1568, /* For Kyber512 */
.max_privkey_size = 1632,
.max_ciphertext_size= 1088,
};
static int __init kyber_module_init(void)
{
return crypto_register_akcipher(&kyber_alg);
}
static void __exit kyber_module_exit(void)
{
crypto_unregister_akcipher(&kyber_alg);
}
module_init(kyber_module_init);
module_exit(kyber_module_exit);
MODULE_LICENSE("GPL");
MODULE_DESCRIPTION("CRYSTALS-Kyber Post-Quantum Algorithm for Linux Kernel");
EOF
Kết quả mong đợi: File kyber.c được tạo, định nghĩa rõ ràng cách module này đăng ký vào hệ thống crypto của Linux.
Verify kết quả bằng cách kiểm tra xem cấu trúc akcipher_alg đã được khai báo đầy đủ chưa:
grep -A 10 "static struct akcipher_alg kyber_alg" /tmp/kernel_mock/crypto/postquantum/kyber/kyber.c
So sánh hiệu năng và độ an toàn của Kyber so với RSA/ECC truyền thống
Việc hiểu rõ sự đánh đổi giữa kích thước khóa, tốc độ và mức độ an toàn là bắt buộc trước khi triển khai thực tế vào Kernel.
Chúng ta sẽ tạo một bảng so sánh chi tiết dưới dạng file JSON để dễ dàng phân tích bằng các công cụ script, mô phỏng dữ liệu thực tế từ các báo cáo benchmark của NIST.
So sánh sẽ tập trung vào:
- Public Key Size: Kích thước khóa công khai.
- Private Key Size: Kích thước khóa bí mật.
- Ciphertext Size: Kích thước bản mã.
- Security Level: Mức độ bảo mật tương đương (bits).
- Quantum Resistance: Khả năng chống lại máy tính lượng tử.
cat > /tmp/security_comparison.json
Kết quả mong đợi: File JSON chứa dữ liệu so sánh chính xác giữa các thuật toán, cho phép bạn dùng công cụ như jq để trích xuất số liệu.
Verify kết quả bằng cách trích xuất kích thước khóa của Kyber768 và so sánh với ECC-P384:
jq '.algorithms[] | select(.name == "Kyber768") | {name, public_key_size_bytes}' /tmp/security_comparison.json && jq '.algorithms[] | select(.name == "ECC-P384") | {name, public_key_size_bytes}' /tmp/security_comparison.json
Nếu jq chưa được cài đặt, dùng grep để kiểm tra nhanh:
grep -A 5 '"name": "Kyber768"' /tmp/security_comparison.json
Điều hướng series:
Mục lục: Series: Triển khai Database Post-Quantum với Kyber trên Linux Kernel
« Phần 1: Chuẩn bị môi trường Linux và công cụ phát triển cho Post-Quantum
Phần 3: Tích hợp mã nguồn Kyber vào cây nguồn Linux Kernel »