Độ khó của việc tạo số nguyên tố 1024 bit

 (glitchcomet.com)
4 điểm bởi GN⁺ 2024-05-05 | 1 bình luận | Chia sẻ qua WhatsApp
  • Đây là một thử nghiệm tự tạo trực tiếp hai số nguyên tố khoảng 1024 bit cần cho khóa RSA 2048 bit bằng Rust, tự triển khai từ sinh số ngẫu nhiên đến phép toán số nguyên lớn mà không dùng phụ thuộc bên ngoài
  • Trial division đơn thuần đủ dùng ở 16 bit với khoảng 40ms, nhưng ngay cả ở 64 bit cũng mất 6,4 giây sau khi tối ưu, nên khó mở rộng lên 1024 bit
  • Kiểm tra Fermat thì nhanh nhưng có thể không loại được pseudoprime, nên phán định cuối cùng dùng kiểm tra Miller-Rabin với k=10
  • Để vượt qua giới hạn của kiểu số nguyên cơ bản, tác giả tự làm BigInt, rồi chuyển từ mảng bool sang mảng byte và cấu trúc chunk u64, giúp thời gian tạo số nguyên tố 1024 bit giảm từ khoảng 32 phút xuống còn 60~90 giây
  • Bản triển khai cuối cùng kết hợp BigInt chunk u64, phép chia nhanh, trial division với các số nguyên tố nhỏ, tăng giá trị ứng viên bằng +2, và chạy song song trên 16 luồng, nhờ đó tìm được số nguyên tố 1024 bit trung bình trong khoảng 40ms, nhưng đây không phải thư viện mật mã đã được kiểm chứng

Tự tạo số nguyên tố 1024 bit cho RSA

  • Mục tiêu là tự tạo ra số nguyên tố có thể dùng để sinh khóa RSA
    • Khóa RSA 2048 bit được tạo từ tích của hai số nguyên tố, nên cần hai số nguyên tố kích thước khoảng 1024 bit mỗi số
    • Vì vậy, bài toán tự nhiên được thu hẹp thành tạo số nguyên tố 1024 bit
  • Thử nghiệm đặt ra ba ràng buộc
    • Mã được viết từ đầu và không dùng phụ thuộc bên ngoài
    • Dùng laptop có CPU AMD Ryzen 7 và RAM 16GB, không dùng phần cứng ngoài hay cloud
    • Phải tạo được số nguyên tố trong “thời gian hợp lý”
  • Ngôn ngữ được chọn là Rust, thứ mà tác giả mới học gần đây
    • Tác giả cho rằng nó đủ gần với các khái niệm mức thấp, nhưng vẫn đủ cấp cao để dễ hiểu các đoạn mã

Giới hạn của trial division bộc lộ ở 16 bit và 64 bit

  • Luồng cơ bản là lặp lại việc sinh số ngẫu nhiên N bit, rồi dừng khi nó vượt qua kiểm tra nguyên tố
  • Số ngẫu nhiên được tạo bằng cách đọc trực tiếp /dev/urandom của Linux thay vì dùng crate rand của Rust
    • /dev/urandom là tệp thiết bị giả để truy cập CSPRNG của kernel Linux
    • Kernel thu thập entropy từ môi trường người dùng và định kỳ seed cho bộ mã dòng xác định dựa trên ChaCha20
  • Với số ngẫu nhiên 16 bit, bit đầu và bit cuối được đặt thành 1
    • Bit cuối 1 để đảm bảo số lẻ
    • Bit đầu 1 để đảm bảo dùng đủ toàn bộ dải bit cần thiết
  • Ở 16 bit, chỉ dùng trial division bằng cách thử chia từ 3 đến sqrt(num) cũng đã tìm được số nguyên tố trong khoảng 40ms
    • Ví dụ chạy cho ra Prime found: 44809, với tổng thời gian khoảng 0,038 giây
  • Khi mở rộng lên 64 bit, trial division đơn thuần mất khoảng 30 giây
    • Sau đó tác giả cải tiến bằng cách chỉ kiểm tra các ứng viên dạng 6k±1 và thử chia trước với danh sách số nguyên tố nhỏ
    • Sau cải tiến, thời gian tạo số nguyên tố 64 bit còn khoảng 6,414 giây
  • Ngay cả ở 64 bit mà đã mất 6 giây, giới hạn của cách này trở nên rõ ràng: rất khó tiến tới tạo số nguyên tố 1024 bit

Chuyển sang kiểm tra nguyên tố xác suất

  • Tác giả có tìm APR-CL và ECPP, là các thuật toán xác định, nhưng chúng quá phức tạp về mặt toán học và thiếu tài liệu giải thích dễ tiếp cận, nên khó chọn để tự triển khai
  • Sau khi xem mã nguồn OpenSSL và khuyến nghị của NIST, tác giả xác nhận rằng kiểm tra nguyên tố xác suất được dùng rộng rãi trong thực tế, bao gồm cả RSA
  • Từ đó, thuật toán chuyển sang cách phán định một số là probable prime với độ chính xác nhất định, thay vì “chứng minh đó là số nguyên tố”

  • Kiểm tra Fermat

    • Định lý nhỏ Fermat dùng quan hệ: nếu p là số nguyên tố và a không chia hết cho p thì a^(p-1) = 1 mod p
    • Vì lũy thừa thông thường gây tràn trong u128, tác giả triển khai lũy thừa modulo
    • pow() nhận số mũ kiểu u32, và việc nâng u128 lên số mũ lớn hơn có thể gây tràn
    • Bản thân phép nhân cũng có thể vượt khỏi phạm vi u128, nên tạm thời tác giả lưu số 64 bit trong u128
    • Kiểm tra Fermat nhanh, nhưng do Fermat pseudoprime, nó có thể nhầm số hợp thành là số nguyên tố
    • Loại số hợp thành này tuy hiếm nhưng vẫn đủ nhiều để tác giả cho rằng chỉ dùng Fermat là không đáng tin cậy

  • Kiểm tra Miller-Rabin

    • Miller-Rabin dựa trên cùng nguyên lý với Fermat nhưng được dùng như một thuật toán kiểm tra nguyên tố xác suất mạnh hơn
    • Cách triển khai là tách n-1 = 2^s × d, rồi kiểm tra nhiều điều kiện
    • a^d = 1 mod n
    • Hoặc với một 0 <= r < s nào đó, a^(2^r × d) = n - 1 mod n
    • Trong thử nghiệm 128 bit, nó tìm được số nguyên tố trong khoảng 0,042 giây, tương tự kiểm tra Fermat
    • Giới hạn sai số tệ nhất của Miller-Rabin là 4^-k, còn trung bình với n lớn là cỡ 8^-k
    • Khi k=10, xác suất sai số trung bình được tính là 0.000000000931323%
    • Tác giả so sánh điều này với xác suất tung đồng xu 30 lần liên tiếp đều ra mặt ngửa, tức 2^-30
    • Trong mật mã thực tế, vẫn cần cẩn thận hơn với việc chọn base ngẫu nhiên và các điều kiện đối kháng

Tự làm BigInt

  • Chỉ với các kiểu số nguyên mặc định của Rust thì khó xử lý các số đủ lớn vượt quá 64 bit, nên cần triển khai số nguyên độ chính xác tùy ý (BigInt)
  • Vì ràng buộc không dùng crate bigint bên ngoài, BigInt cũng được tự viết

  • Thử nghiệm 1: mảng chữ số

    • Ban đầu tác giả thử lưu số lớn dưới dạng mảng chữ số thập phân
    • Có thể triển khai cộng và nhân theo kiểu tính tay, nhưng bị mắc ở phép chia nên bỏ dở

  • Thử nghiệm 2: mảng nhị phân dựa trên bool

    • Cách thứ hai là lưu số dưới dạng mảng các bit 0 và 1
    • BigInt dùng mảng [bool; 2048]
    • Vì nhân hai số 1024 bit có thể cần tối đa 2048 bit, nên cấp phát 2048 bit
    • Phép cộng và trừ được triển khai theo kiểu full adder
    • Phép nhân được xử lý bằng shift-and-add dựa trên tính chất nhị phân
    • Phép chia được triển khai bằng binary long division
    • Với cách này, tác giả đã tìm được số nguyên tố 1024 bit đầu tiên, nhưng thời gian chạy là khoảng 32 phút 44,90 giây
    • Về mặt kỹ thuật thì đã đạt mục tiêu, nhưng không đáp ứng ràng buộc “thời gian hợp lý”

  • Thử nghiệm 3: chunk byte

    • Tác giả nhận ra mỗi bool trong mảng bool không chiếm 1 bit mà chiếm 1 byte
    • [bool; 2048] vì thế dùng 2048 byte chứ không phải 2048 bit
    • Sau đó tác giả chuyển sang lưu 2048 bit trong mảng 256 byte
    • Cộng, trừ và nhân hoạt động mà gần như không cần thay đổi lớn, còn phép chia được điều chỉnh để xử lý chunk byte như danh sách bit
    • Với cách này, thời gian tạo số nguyên tố 1024 bit giảm xuống còn 4 phút 43 giây

  • Thử nghiệm 4: chunk u64

    • Cách chunk byte thực chất là BigInt kiểu digit nhưng dùng cơ số cao hơn
    • Bước tiếp theo là lưu 2048 bit thành 32 chunk u64
    • Mỗi chunk hoạt động như một “chữ số”
    • Kết quả nhân của hai chunk u64 được chứa bằng u128
    • Với cấu trúc này, số 1024 bit có thể được biểu diễn bằng 16 chunk u64 thay vì 309 chữ số thập phân
    • Thời gian tạo số nguyên tố 1024 bit được cải thiện còn 60~90 giây

Tối ưu các nút thắt cổ chai

  • Trong benchmark đơn giản, khác biệt giữa bản nhị phân và bản chunk u64 là rất rõ
    • a + b và a - b: 5537.35ns → 123.57ns
    • a * b: 1292283.14ns → 842.32ns
    • a / b và a % b: 733446.76ns → 44440.12ns
    • a < b và a > b: 2506.02ns → 58.91ns
  • Sau đó việc tối ưu chủ yếu tập trung vào phép chia, phép nhân, các phép toán bên trong Miller-Rabin, và logic tạo ứng viên

  • Phép chia

    • Nút thắt lớn nhất là phép chia
    • Ngay cả với cấu trúc chunk u64, phép chia cũ vẫn thực hiện long division từng bit một
    • Tác giả tham khảo thuật toán ở trang 598 của Handbook of Applied Cryptography để triển khai long division dựa trên radix
    • Cách làm là ước lượng “chữ số” thương hiện tại từ 3 “chữ số” đầu của số bị chia và 2 “chữ số” đầu của số chia
    • Cách triển khai này tiết kiệm khoảng 40.000ns cho mỗi phép chia
    • Nếu số chia chỉ là một chunk u64, tác giả xử lý riêng bằng long division trực tiếp hơn với u128
    • Trường hợp này xuất hiện thường xuyên trong Miller-Rabin

  • Phép nhân

    • Phép nhân nhanh hơn khoảng 2 lần nhờ sắp xếp lại vòng lặp để loại bỏ BigInt dùng lưu kết quả trung gian
    • Tác giả tính số chunk đang được sử dụng và chỉ lặp qua các chunk khác 0
    • Vì BigInt chủ yếu lưu số không quá 1024 bit, nên thường có một nửa không gian 2048 bit để trống
    • Tác giả cũng cân nhắc Karatsuba hay nhân dựa trên FFT, nhưng thấy việc tự triển khai quá phức tạp và phép nhân hiện tại đã đủ nhanh

  • Tối ưu bên trong Miller-Rabin

    • Với Miller-Rabin, trọng tâm là giảm số phép toán đắt đỏ
    • Thay vì x = mod_exp(x, 2, n), tác giả thực hiện trực tiếp x = (x * x) % n
    • Lần gọi mod_exp() đầu tiên được thay bằng phiên bản inline rút gọn để giảm overhead gọi hàm
    • Thêm num.is_even() để kiểm tra chẵn, tránh tính % 2
    • d / 2 được thay bằng d >>= 1
    • += 1, -= 1 được xử lý riêng bằng increase() và decrease()
    • Đặc biệt, is_even() và d >>= 1 mỗi tối ưu mang lại khoảng 70.000ns
    • Trong benchmark cuối, bản chunk u64 đã tối ưu nhanh hơn đáng kể
    • a * b: 842.32ns → 295.04ns
    • a / b và a % b: 44440.12ns → 831.77ns
    • a / 2: 75121.58ns → 60.89ns
    • a % 2 == 0: 78400.87ns → 21.65ns
    • a - 1: 103.15ns → 67.54ns

Trình tạo số nguyên tố 1024 bit cuối cùng

  • Hàm cuối cùng trước hết đọc số ngẫu nhiên 1024 bit từ /dev/urandom
    • Bật bit cao nhất để đảm bảo kích thước 1024 bit
    • Bật bit thấp nhất để đảm bảo số lẻ
  • Sau đó, thay vì đọc lại số ngẫu nhiên mới mỗi lần, nó cộng 2 vào giá trị ứng viên để chuyển sang ứng viên lẻ tiếp theo
    • increase_by_2() trong đa số trường hợp chỉ cần cộng trên một chunk u64
  • Trước Miller-Rabin, chương trình chạy trial division trước với danh sách số nguyên tố nhỏ
    • Trong mã cuối, tác giả dùng 1000 số nguyên tố nhỏ đầu tiên
    • Các số nguyên tố nhỏ đều nằm trong một chunk u64, nên có thể tận dụng xử lý đặc biệt cho phép chia một chunk nhanh
  • Bài toán này có thể xử lý theo kiểu embarrassingly parallel, vì không cần bộ nhớ chia sẻ hay đồng bộ giữa các luồng
    • 16 luồng CPU mỗi luồng tự tìm số nguyên tố, rồi dùng giá trị từ luồng gửi kết quả sớm nhất
  • Ví dụ chạy cuối cùng ghi nhận elapsed time khoảng 0,086 giây
    • Mức sử dụng CPU hiển thị là 690%
  • Trung bình sau 100 lần chạy là 0.04109 ± 0.00307 giây
    • Trung bình mất khoảng 40ms để tìm số nguyên tố 1024 bit
    • Mỗi lần gọi prime_1024bit() riêng lẻ có thể dao động từ khoảng 8ms đến khoảng 800ms do tính ngẫu nhiên
    • Chạy song song giúp làm mượt biến động bằng cách lấy kết quả nhanh nhất

Mã nguồn và giới hạn

  • Toàn bộ mã và kho lưu trữ được công khai trên github
  • Liên kết thảo luận có trên hackernews và reddit
  • Bản triển khai này khó có thể xem là an toàn về mặt mật mã trong thực tế, và mục tiêu của nó cũng không phải làm thư viện cho mật mã mà gần hơn với học tập và thử nghiệm triển khai

Bài viết liên quan

1 bình luận

 
GN⁺ 2024-05-05
Ý kiến trên Hacker News

  • Đã từng có vài đồng tiền mã hóa dùng việc tìm số nguyên tố lớn như một phần của hàm bằng chứng công việc, và khoảng 8 năm trước chỉ cần một bản cài đặt kiểm tra nguyên tố thật nhanh cũng có thể kiếm được khá nhiều tiền
    Tôi từng là tác giả và người bảo trì phần mềm đào riecoin một thời gian, chắc là vì tôi thích số nguyên tố thôi chứ cũng không rõ lý do lắm
    Bài này đã bỏ qua phép nhân Montgomery, tối ưu số một cho kiểm tra nguyên tố nhanh: https://en.m.wikipedia.org/wiki/Montgomery_modular_multiplic...
    Đây là nền tảng của các bản cài đặt lũy thừa mô-đun tốc độ cao thực dụng
    Niall Emmart, người mà tôi biết là khi đó còn ở giới học thuật và giờ đang ở Nvidia, đã công bố thư viện số nguyên lớn GPU CGBN cực kỳ nhanh: https://github.com/NVlabs/CGBN
    Đó vẫn là bản cài đặt lũy thừa mô-đun theo lô nhanh nhất mà tôi biết, và nói hơi kiểu mọt sách một chút thì nó đẹp đến nghẹt thở
    Một ngày nào đó tôi nên viết về chuyện nhờ vậy mà tôi đã thống trị việc tạo ra một đồng tiền mã hóa nhỏ trong khoảng 5 năm. Và Python có sẵn một hàm lũy thừa mô-đun khá ổn dưới dạng ba tham số pow(x, y, m) để tính x^y % m
    Dùng cái này, nếu muốn tự cài đặt, bạn có thể làm kiểm tra nguyên tố Fermat hoặc Miller-Rabin rất dễ và khá vui. Nếu không muốn tự làm thì mpz_probab_prime() của thư viện gmp cũng rất tốt. Tất nhiên gmp nhanh hơn, nhưng khi nghịch với số nguyên tố lớn thì khó gì thắng được niềm vui của một bài kiểm tra Fermat chỉ trong hai dòng

    • Niall cũng tham gia vào một trong các bài nộp đoạt giải ZPrize liên quan đến phép nhân đa vô hướng tốc độ cao
      Nó có liên hệ rất gần với lũy thừa mô-đun theo lô, chỉ khác là chạy trên đường cong elliptic thay vì mô-đun nguyên tố. Có thể xem đây là sự tiếp nối công việc từ CGBN
      Năm ngoái anh ấy có một bài trình bày hay tại seminar ăn trưa mật mã học của Stanford, và slide cùng bản ghi hình đều có trên mạng
      https://cbr.stanford.edu/seminarTalks/slides_20230526_niall_...
      https://www.youtube.com/watch?v=KAWlySN7Hm8
    • Tôi tò mò vì sao những đồng tiền mã hóa như vậy lại dùng các hàm bằng chứng công việc tùy biến như thế
      Không biết là họ chỉ có ý niệm mơ hồ rằng mật mã học kiểu gì cũng dùng số nguyên tố mà không biết khi nào và vì sao, hay là có một lý do sâu xa hơn
    • Tôi đã chuyển từ Perl sang Python chỉ vì pow(x,e,mod)

  • Nếu có một giới hạn trên cho phạm vi giá trị, thì việc làm cho Miller-Rabin gần như mang tính quyết định là khá đơn giản
    Chỉ cần chọn các cơ số đã được chứng minh là loại bỏ toàn bộ các số giả nguyên tố trong phạm vi đó
    Danh sách này cũng không dài. Miller-Rabin thực sự rất mạnh

    • Tôi tò mò các cơ số đó là gì trong phạm vi số 1024 bit
      Tôi không tìm được câu trả lời trên mạng
    • Hơn nữa, nếu bạn chỉ đang tìm số nguyên tố, thì có thể chọn các ứng viên trông có vẻ nguyên tố rồi xác nhận bằng một kiểm tra tất định

  • Chỉ cần một dòng inline assembly là có thể đơn giản hóa phép nhân số lớn kiểu học sinh tiểu học: https://github.com/jcalvinowens/toy-rsa/blob/master/bfi.c#L4...
    Nếu có thể quay lại quá khứ và chỉ thay đổi một thứ trong C, tôi muốn thêm khái niệm nhân mở rộng. Thật tiếc là Rust cũng không có. Hỗ trợ phần cứng thì ở đâu cũng có. Cortex M0 thậm chí không có phép chia nhưng lại có nhân mở rộng
    Đoạn mã này lấy từ một bản cài đặt RSA đồ chơi rất xấu mà tôi đã viết từ lâu: https://github.com/jcalvinowens/toy-rsa
    Lý do chỉ dùng kiểm tra Fermat mà vẫn chịu được là vì nếu các số nguyên tố thực ra không phải nguyên tố thì thuật toán sẽ không hoạt động. Kiểm tra Fermat thì nhanh, và chỉ cần mã hóa/giải mã một lần là cũng loại bỏ được khả năng cực kỳ nhỏ rằng một trong hai số là kẻ nói dối Fermat
    Tuy vậy, tôi không biết liệu có thể chứng minh rằng không tồn tại cặp khóa RSA nào vẫn mã hóa/giải mã thành công thông điệp với các giá trị P/Q không phải nguyên tố hay không. Trong triển khai thực tế thì dĩ nhiên đây không phải cách làm chuẩn, nhưng tôi chưa từng tìm được câu trả lời

    • Thú vị là giờ C đã có số nguyên lớn
      C23 bổ sung kiểu _BitInt(N), ví dụ có thể dùng _BitInt(1024) cho kiểu 128 byte
      Tuy vậy hỗ trợ từ trình biên dịch còn hạn chế. Trong Clang, để cho phép N lớn hơn 128, bạn có thể dùng cờ -fexperimental-max-bitint-width=N. Nếu N lớn hơn 128 và bạn chia một _BitInt(N), trình biên dịch sẽ просто bị crash, nhưng +, -, * thì vẫn hoạt động như mong đợi
    • Trong Zig thì việc này tương đối dễ
      Có hàm dựng sẵn @mulWithOverflow trả về kết quả cùng bit tràn, và các kiểu số nguyên có tới (u|i)65535
      Tùy việc bạn làm, có thể phát hiện tràn rồi nâng lên kiểu lớn hơn, hoặc nâng trước rồi tùy chọn cắt bớt sau
      Ngoài ra còn có toán tử riêng *| cho phép nhân bão hòa, và *% cho phép nhân vòng. Có thể dùng khi cần các ngữ nghĩa như vậy. Còn các trường hợp tràn khác là hành vi không xác định có kiểm tra an toàn, sẽ panic trong chế độ build Debug và ReleaseSafe
    • Nếu p và q là các số Carmichael nguyên tố cùng nhau, thì RSA vẫn có thể mã hóa và giải mã thông điệp thành công
      Tuy nhiên, p*q khi đó sẽ có các thừa số nguyên tố nhỏ hơn nên dễ phân tích nhân tử hơn, vì vậy mức độ an toàn sẽ thấp hơn
    • Theo tôi biết, trong hầu hết trình biên dịch C và trong Rust, chỉ cần ép kiểu sang một kiểu lớn hơn rồi nhân là sẽ sinh ra đúng lệnh máy mà bạn muốn
    • Bản Pretty Good Privacy (PGP) gốc năm 1994 của Philip Zimmermann chỉ dùng một sàng chia cho tất cả các số nguyên tố 16 bit đã biết, và bảng đó được tạo bằng sàng Eratosthenes. Sau đó nó áp dụng kiểm tra Fermat

  • Tôi tò mò không biết việc này mất bao lâu
    Tôi từng làm phép nhân số nguyên lớn cho một dự án nghiên cứu bậc cử nhân và gần như mất trọn hai học kỳ. Tôi đã triển khai Karatsuba, Toom-Cook, FFT phức, vài biến thể NTT và Schonhage-Strassen
    Số nguyên tố gần như là một dạng phép thuật toán học. Với ai quan tâm, A Friendly Introduction to Number Theory của Silverman là một cuốn sách toán nhập môn rất hay
    Nhân tiện, liên kết trên trang đang là 4025051 chứ không phải 40250519

  • Bài viết hay. Gần đây tôi cũng tự viết một ít mã số nguyên lớn cho phiên bản đầu của [0], và tôi nhớ việc biến những mô tả cấp cao trong các bài báo toán học thành phép toán thực tế khó chịu đến mức nào
    Tuy vậy tôi có một phản biện nhỏ
    Nếu dùng toàn bộ phạm vi của u64 thì các con số là ở cơ số 2^64, không phải cơ số 2^64-1. Mỗi từ có giá trị từ 0 đến 2^64-1, giống như mỗi chữ số trong hệ thập phân có giá trị từ 0 đến 9
    [0] https://github.com/LegionMammal978/bigfoot-sim

  • Nếu như tối ưu hóa cuối cùng, khi thất bại mà không tạo số ngẫu nhiên mới mà chỉ tăng số đó thêm 2, thì tính bảo mật sẽ bị suy yếu đôi chút
    Vì số nguyên tố không phân bố đồng đều, nên sẽ có thiên lệch về phía các số nguyên tố nằm ngay sau những khoảng trống giữa các số nguyên tố lớn

    • Tôi có đọc về điều đó trong lúc tìm hiểu
      Đây là sự đánh đổi giữa tốc độ chạy và tính ngẫu nhiên của số nguyên tố, và tôi chọn tốc độ vì cho rằng việc để 16 luồng, mỗi luồng bắt đầu từ một số ngẫu nhiên rồi chạy đua tìm số nguyên tố, đã bổ sung đủ độ ngẫu nhiên
      Nếu muốn ưu tiên tính ngẫu nhiên hơn tốc độ thì thay +=2 bằng lời gọi rng() là một thay đổi rất dễ

  • Bài hay và viết tốt
    Có vẻ tác giả muốn nói cơ số 256 chứ không phải base-255

  • Vài con số cỡ 1–2KB hoàn toàn đủ nằm trong cache L1, và ngay cả khi không thì vẫn còn cache L2 cỡ hơn megabyte với thời gian truy cập khoảng 3ns
    Bài viết nói có lẽ đã phải chờ RAM đọc/ghi vì trượt cache L1, nhưng sau đó lại không quay lại điểm này
    Ngoài ra, đây chỉ là về sinh số nguyên tố nên tránh được phần lớn cạm bẫy của RSA, và urandom đáng ra phải an toàn. Nếu mã hoạt động đúng thì không có nhiều chỗ có thể sai nghiêm trọng
    Có một vài vấn đề liên quan đến số nguyên tố yếu trong RSA cần tránh, nhưng tôi không rõ chúng có đủ phổ biến để thật sự thành vấn đề ở đây không

  • Làm tôi nhớ lại một dự án năm nhất đại học từ vài chục năm trước
    Ý tưởng là của người bạn đồng thời là bạn cùng nhóm, sau này trở thành thủ khoa tốt nghiệp, và cậu ấy cũng là người triển khai phần toán cốt lõi: tạo ra mã hóa RSA 4096-bit
    Tôi còn nhớ việc sinh số nguyên tố trong bản triển khai cuối chậm đến mức nào. Trên một máy trạm PA-RISC, việc tạo mất khoảng 20 phút
    Người bạn mê toán đó tiếp tục tối ưu mã ngay cả sau khi dự án kết thúc, và tôi vẫn nhớ cảnh cậu ấy ngồi đọc các bài báo về kiểm định số nguyên tố và triển khai toán số nguyên lớn
    Ví dụ, đã có cải thiện rất lớn khi để phép nhân thành phần bỏ qua nếu một số nào đó là 0 và cho kết quả bằng 0

    • Trên phần cứng chậm thì sinh khóa đường cong elliptic tốt hơn nhiều
      Hoặc là phải chờ rất lâu, hoặc phải hy sinh mức bảo mật đủ để dùng được tới tương lai

  • Tôi hiểu việc đặt bit thấp thành 1, vì số chẵn thì chắc chắn không phải số nguyên tố. Tất nhiên 2 là ngoại lệ
    Nhưng tôi không hiểu vì sao bit cao cũng được đặt thành 1. Tôi không rành về số nguyên tố hay mật mã, nhưng trông như đang từ bỏ không cần thiết 1 bit entropy. Tôi đang bỏ sót điều gì vậy?

    • Nếu bit cao luôn được đặt và số nguyên tố được mã hóa bao gồm bit đó, thì số nguyên tố sẽ luôn được mã hóa với cùng số byte
      Mã hóa byte độ dài biến thiên có thể gây ra vấn đề khi trao đổi dữ liệu giữa các phần mềm khác nhau nếu đặc tả không thật rõ ràng và không được kiểm thử kỹ
      Hãy xem các vấn đề trong DHE dựa trên RSA khi khóa công khai của máy chủ có số 0 ở đầu
    • Cũng giống như tạo số có hai chữ số vậy
      Nếu chữ số đầu là 0 thì nó không còn là số có hai chữ số nữa
    • Đặt bit đầu thành 1 đúng là mất 1 bit entropy, nhưng đổi lại bảo đảm số nguyên tố đủ lớn
      Thêm nữa, trong RSA người ta nhân hai số nguyên tố. Nếu một số là 1024 bit thì số kia, nếu tôi nhớ không nhầm, chỉ cần khoảng 200 bit cũng có thể đạt số bit entropy cần cho khóa
      Vì vậy để cả hai số nguyên tố đều là 1024 bit cũng tạo ra một chút dư địa an toàn
    • Đúng là từ bỏ 1 bit entropy, nhưng vẫn còn lại 1022 bit
      Có lẽ như vậy an toàn hơn là khi ai đó yêu cầu số nguyên tố 1024 bit mà lại phải băn khoăn liệu số nguyên tố 1020 bit có đủ ổn không. Giống như bình thường người ta không xem 00042 là số có 5 chữ số
      Về mặt kỹ thuật, lựa chọn tối ưu chính xác có thể thay đổi tùy dùng vào đâu, nhưng cách trong bài có vẻ là mặc định an toàn hơn
    • Chắc chắn việc mất 1 bit entropy để bảo đảm tạo ra số nguyên tố không chỉ dừng ở 50 bit là một sự đánh đổi hoàn toàn chấp nhận được