Số nguyên tố có vai trò hết sức quan trọng trong kỹ thuật mật mã khóa công khai, việc tạo, kiểm tra số nguyên tố lớn, an toàn sử dụng trong các hệ mật, giao thức quyết định mức độ an toàn của chúng (hệ mật khóa công khai, chữ ký số dựa trên RSA; trao đổi khóa Diffe-Hellman…).

Có hai phương pháp chính trong việc kiểm tra số nguyên tố là phương pháp xác suất, và phương pháp tất định.

- Các phương pháp kiểm tra tính nguyên tố xác suất, các phương pháp này có một xác suất lỗi nhỏ. Tất cả các phép kiểm tra xác suất được quy định ở đây có thể kết luận một hợp số là số nguyên tố hoặc ngược lại kết luận một số nguyên tố là hợp số.

- Các phương pháp kiểm tra tất định, đảm bảo đưa ra kết luận chính xác. Những thuật toán này được gọi là các chứng chỉ tính nguyên tố.

Bài viết này trình bày về xác suất lỗi trong các phương pháp kiểm tra số nguyên tố xác suất quy định trong TCVN 13176:2020.

1. Tiêu chuẩn TCVN 13176:2020.

TCVN 13176 : 2020 (ISO/IEC 18032:2005) Bộ sinh số nguyên tố do Cục Quản lý mật mã dân sự và Kiểm định sản phẩm mật mã biên soạn, Ban Cơ yếu Chính phủ đề nghị, Tổng cục Tiêu chuẩn Đo lườn,g Chất lượng thẩm định, Bộ Khoa học và Công nghệ công bố. Tiêu chuẩn này quy định các phương pháp sinh và kiểm tra số nguyên tố được yêu cầu trong các giao thức và thuật toán mật mã.

Đầu tiên, tiêu chuẩn này quy định các phương pháp để kiểm tra xem một số có phải là số nguyên tố hay không. Các phương pháp kiểm tra đưa ra trong tiêu chuẩn này có thể được chia thành 2 nhóm:

- Các phương pháp kiểm tra tính nguyên tố xác suất. Ba phép kiểm tra được quy định tại tiêu chuẩn này bao gồm: phép kiểm tra Miller-Rabin, phép kiểm tra Frobenius-Grantham, và phép kiểm tra Lehmann.

- Các phương pháp kiểm tra tất định, đảm bảo đưa ra kết luận chính xác. Những thuật toán này được gọi là các chứng chỉ tính nguyên tố. Hai chứng chỉ được quy định trong tiêu chuẩn này bao gồm: Chứng chỉ tính nguyên tố đường cong elliptic và Chứng chỉ tính nguyên tố dựa trên thuật toán Maurer.

Thứ hai, tiêu chuẩn này quy định các phương pháp sinh số nguyên tố. Một lần nữa, cả hai phương pháp xác xuất và tất định được quy định tại đây.

Chi tiết về các phương pháp kiểm tra và sinh số nguyên tố xem thêm tại TCVN 13176 : 2020 (ISO/IEC 18032:2005) Bộ sinh số nguyên tố.

2. Xác suất lỗi

Với mỗi phép kiểm tra xác suất, số phép lặp cần thực hiện tùy thuộc vào xác suất lỗi của một phép trong phép kiểm tra. Xác xuất lỗi của một phép lặp khác nhau phụ thuộc vào số kiểm tra được lựa chọn ngẫu nhiên hay có thể được chọn để có các tính chất đặt biệt.

Đối với phép kiểm tra Miller-Rabin và Frobenius-Grantham, các ước tính lỗi trong trường hợp xấu nhất được đưa ra cho xác xuất một đầu vào là hợp số được chấp nhận là số nguyên tố qua phép kiểm tra. Đối với phép kiểm tra Lehmann, các ước tính chỉ được đưa ra cho xác suất chấp nhận một hợp số, mặc dù cũng có xác suất khác 0 khi phép thử từ chối một số nguyên tố.

Với mỗi phép kiểm tra, giả sử rằng số được điểm tra là lẻ, lơn và được chọn ngẫu nhiên k-bit, thì xác suất lỗi thông thường của phép kiểm tra sẽ nhỏ hơn nhiều, điều này là hoàn toàn hợp lý. Đối với phép kiểm tra Miller-Rabin, dự đoán này có thể được định lượng, và các ước tính lỗi trong trường hợp trung bình tốt có thể được đưa ra, có nghĩa là các ước tính xác suất lỗi của các thuật toán được đề xuất. Đối với phép kiểm tra Frobenius-Gratham và phép kiểm tra Lehmann, chỉ một ước tính lỗi trong trường hợp xấu nhất được biết đến. Vì vậy, trước tiên bài viết đưa ra công thức chung cho phép chuyển các ước tính trong trường hợp xấu nhất thành ước tính trong trường hợp trung bình cho mỗi phép kiểm tra tính nguyên tố.

Nói chung, các ước tính dựa trên 2 tham số:

• k, độ dài của các số được sinh ra
• t, số lần kiểm tra tối đa được lặp với mỗi ứng viên.

Nhắc lại rằng hai thuật toán được quy định cho việc sinh số nguyên tố: thuật toán chọn ứng viên ngẫu nhiên (xem điều 8.2.1 TCVN 13176 : 2020) và thuật toán tìm kiếm gia tăng các ứng viên (xem điều 8.2.2 TCVN 13176 : 2020). Các ước tính lỗi cho cả hai thuật toán được đưa ra dưới đây. Thuật toán tìm kiếm gia tăng thường phụ thuộc vào tham số µ và các ước tính lỗi được đưa ra với giá trị khuyến nghị µ= 10ln(2^k).

2.1 Các ước tính chung

Lấy bất kỳ phép thử T chấp thuận bất kỳ số nguyên tố và chấp thuận một hợp số với xác suất tối đa ε  trong một phép lặp. Ngay cả khi đây là tất cả những gì được biết về phép thử, thì vẫn có thể đưa ra những ước tính trong trường hợp trung bình.

Xác suất thuật toán lựa chọn ngẫu nhiên sử dụng T là phép kiểm tra tính nguyên tố có đầu ra là một hợp số là lớn nhất (ví dụ ở [1])

 ε ^t /( ε ^t + 2.8/(k – 2.8)) 

Đối với thuật toán tìm kiếm gia tăng, đặt q_k,t,µ là xác suất cho đầu ra là một hợp số bắt đầu từ một điểm đơn, khi chúng ta:

• Sử dung t phép lặp trong phép thử T,
• Chọn điểm bắt đầu là số lẻ ngẫu nhiên k bit, và
• Kiểm tra tối đa µ ứng viên.

Sau đó xác suất lỗi trên toàn thuật toán, ở đây chúng tôi tiếp tục chọn một điểm bắt đầu mới cho đến khi chùng tôi thành công, tối đa [2] [3].

k² q_k,t,µ + 2(1 -2.8/k)k

Xem xét tìm kiếm trong một khoảng, khi µ ứng viên được kiểm tra, kịch bản trường hợp xấu nhất là tất cả các ứng viên đều là hợp số, xét trường hợp này có thể thấy rằng q_k,t,µ ≤ 1-(1-εt ) ^µ

2.2 Uớc tính lỗi trong trường hợp xấu nhất với phép kiểm Miller-Rabin, Frobenius-Grantham, và Lehmann

Đối với phép kiểm tra Miller-Rabin và Frobenius-Grantham, các ước tính lỗi trong trường hợp xấu nhất được đưa ra cho xác xuất một đầu vào là hợp số được chấp nhận là số nguyên tố qua phép kiểm tra. Đối với phép kiểm tra Lehmann, các ước tính chỉ được đưa ra cho xác suất chấp nhận một hợp số, mặc dù cũng có xác suất khác 0 khi phép thử từ chối một số nguyên tố.

2.3 Các ước tính lỗi trong trường hợp trung bình

2.3.1 Các ước tính lỗi trong trường hợp trung bình với thuật toán Miller-Rabin

Bảng 2.1 bao gồm các ước tính xác suất lỗi theo logarit cơ số 2 phép kiểm tra Miller-Rabin. Ví dụ, trong bảng phụ đầu tiên, với tham số k =256 và t =11 kết quả là 2^-84, có nghĩa là xác xuất lỗi cho 11 phép kiểm tra Miller-Rabin với một số 256 bit là 2^-84. Bảng phụ thứ 2 chỉ ra rằng 4 phép kiểm tra Miller-Rabin đối với số 1024 bit có giới hạn xác suất lỗi là 2^-109.  Các mục được lấy từ [4], [5].

Bảng 2.1 - Các ước tính lỗi trong trường hợp trung bình đối với phép kiểm tra
nguyên tố Miller-Rabin

2.3.2 Các ước tính lỗi trong trường hợp trung bình trong phép kiểm tra Frobenius-Gratham

Không có kết quả cho các ước tính lỗi trong trường hợp trung bình được biết đến, nhưng nói chung công thức đã đưa ra ở phụ lục 2.1 có thể được sử dụng để chuyên đổi các trường hợp xấu nhất thành các trường hợp trung bình sử dụng ε = 1/7710. Bảng 2.2 bao gồm các ước tính xác suất lỗi theo cơ số logarit 2.

Bảng 2.2 - Các ước tính lỗi trong trường hợp trung bình đối với phép kiểm tra nguyên tố Frobenus-Grantham

2.3.3 Ước tính lỗi trong trường hợp trung bình trong phép kiểm tra nguyên tố Lehmann

Không có kết quả cho ước tính lỗi trong trường hợp trung bình được biết đến, nhưng nói chung công thức đưa ra trong 2.1 có thể được sử dụng để chuyển đổi trường hợp các ước tính trong trường hợp xấu nhất thành các ước tính trong trường hợp trung bình sử dụng ε = ½.

Tổng kết

Khác với các phương pháp kiểm tra tính nguyên tố tất định, các phương pháp kiểm tra tính nguyên tố xác suất luôn tồn tại một xác suất lỗi nhỏ trong mỗi phép kiểm tra, khiến kết luận sai tính nguyên tố của ứng viên kiểm tra. Trong thực tế, khi thực hiện kiểm tra tính nguyên tố bằng các phương pháp kiểm tra xác suất cần chú ý đến chỉ số này, lựa chọn phương pháp kiểm tra phù hợp, tăng số lần thực hiện phép kiểm tra khi kiểm tra các số lớn, để giảm thiểu tỷ lệ lỗi xuất hiện.

TS. Hồ Văn Hương, Cục QLMMDS & KĐSPMM