Giả sử bạn muốn "n" là 2048 bit (RSA 2048). Sau đó, "p" và "q" mỗi cái sẽ là 1024 bit.
Máy tính tạo ra một số 1024 bit ngẫu nhiên (gần như tức thời) và kiểm tra tính nguyên tố của nó. Có nhiều loại khác nhau của kiểm tra tính nguyên tố, hầu hết trong số họ là thống kê. Chúng rất nhanh (tôi biết điều này không được định lượng, nhưng tôi làm việc trên các bộ vi điều khiển nhúng chạy ở tốc độ 100MHz mà không có bộ đệm, vì vậy tôi không biết gì về tốc độ trên máy tính để bàn).
Vì vậy, tạo ra một loạt các số 1024 bit, cuối cùng bạn sẽ đạt được một số vượt qua nhiều lần lặp lại các bài kiểm tra tính nguyên tố. (không đi vào chi tiết ở đây về số liệu thống kê và thế nào là "đủ tốt", tất cả đều đủ dễ tìm). Làm tương tự để lấy "q" của bạn, nhân chúng lên, bạn có mô đun "n". "n" cộng với "e" của bạn (có thể là 65537) là khóa chung của bạn.
Như bạn có thể tưởng tượng, mật độ nguyên tố giảm khi các số lớn hơn; có nhiều cách để ước tính mật độ nguyên tố dựa trên kích thước của số nguyên tố mà bạn đang cố tạo. 40% các số dưới 10 là số nguyên tố, nhưng mật độ chỉ 25% đối với các số dưới 100 và thậm chí ít hơn đối với các số 1024 bit. Nếu tôi nhớ chính xác, Trung bình, bạn sẽ phải thử chu kỳ kiểm tra tạo/kiểm tra tính nguyên tố ~360 lần để tìm số 1024 bit kiểm tra là số nguyên tố. Nó không phải là hàng ngàn hay hàng triệu. Và đối với các số 512 bit, có thể dưới 100 lần thử.
Vì không gian số 2^1024 là rất lớn, rất khó có khả năng p & q của bạn khớp với p & q của bất kỳ ai khác. Trên thực tế, mỗi chuỗi 1024 bit đó có lẽ chưa từng tồn tại trên bất kỳ máy tính nào trong lịch sử trái đất.
Tôi hy vọng điều đó mang lại cho bạn đủ cảm giác về cách thức hoạt động của nó. Nó về cơ bản là đơn giản. Tôi đã bỏ qua một số chi tiết, thảo luận về các số nguyên tố mạnh, v.v. vì nó đi vào các chi tiết nằm ngoài phạm vi câu hỏi của bạn.
