Vì lý do trong nhận xét của tôi Tôi sẽ cho rằng chúng ta thay đổi câu hỏi để xác định $δ$ với $2^\delta<\lvert p-q\rvert$, và $\kappa=k+\delta$. FIPS 186-4 tạo khóa chẳng hạn sẽ sử dụng $k=3072$ và $\delta=k/2-100=1436$.
Tôi không thể tìm thấy bất kỳ tài liệu tham khảo nào thảo luận về bảo mật RSA tiệm cận với ký hiệu như $1^k$ chỉ định tối thiểu $\lvert p-q\rvert$. Đó là bởi vì:
- Tăng dần $\delta$ qua một số điểm làm giảm đáng kể an ninh. Ví dụ. vì $k=3072$ (sẽ cung cấp bảo mật đối xứng khoảng 128 bit) và $δ=1912$ chúng tôi sẽ có $\min(p,q)<2^{161}$ và ECM Lentra có khả năng sẽ cho phép kéo yếu tố đó của $n$.
- Lập luận đơn giản rằng tăng $\delta$ cải thiện an ninh là thiếu sót.
- $\delta=0$ được cho là tốt.
- Lý do lịch sử để giới thiệu một giới hạn thấp hơn cho $\lvert p-q\rvert$ là hệ số Fermat có chi phí tỷ lệ thuận với $(p-q)^2/n$ nhân một số đa thức trong $k$, do đó $\lvert p-q\rvert$ không được quá nhỏ. Người ta đã đi từ thực tế đó đến kết luận rằng cần phải xác định mức tối thiểu rõ ràng $\lvert p-q\rvert$, mặc dù nó đủ rõ ràng để xác định rằng $p$ và $q$ được chọn độc lập và gần như thống nhất giữa các số nguyên tố trong một số khoảng như $[2^{(k-1)/2},2^{k/2})$ để đảm bảo thừa số Fermat là vô vọng, bất cứ khi nào $k$ đủ lớn để chống lại GNFS (hoặc PPMPQS, đã được biết đến từ lâu vào năm 1998 khi quyết định gây tranh cãi được ký trong ANS X9.31).
Theo yêu cầu trong bình luận Tuy nhiên, tôi sẽ cho rằng có một số lý do để chỉ định $\delta$, và điều đó ngày càng tăng $\delta$ tăng cường bảo mật trong một số miền. Để không mâu thuẫn với thực tế trong gạch đầu dòng đầu tiên ở trên, tôi sẽ giả sử $0\le\delta\le\alpha\,k+\beta$ cho một số thực tế $\alpha$ và $\beta$ với $\alpha\in[0,1)$. Theo giả thuyết như vậy, thật hợp lý khi xác định $\kappa=k+\delta$và sử dụng nó làm tham số bảo mật.
Chúng ta có thể định nghĩa việc tạo khóa RSA cho số nguyên lẻ không đổi $e>1$ như: trên đầu vào $1^\kappa$
- Trong thời gian đa thức, chọn số nguyên $k$ và $\delta$ với $\kappa=k+\delta$ và $0\le\delta\le\alpha k+\beta$ (thất bại nếu điều đó là không thể); cách phù hợp bao gồm $\delta\gets\left\lfloor\frac\alpha2\kappa\right\rfloor$ và $k\gets\kappa-\delta$.
- Chọn $p$ ngẫu nhiên đều giữa các số nguyên tố $p$ Trong $[2^{(k-1)/2},2^{k/2})$ với $\gcd(p-1,e)=1$
- Chọn $q$ ngẫu nhiên đều giữa các số nguyên tố $q$ Trong $[2^{(k-1)/2},2^{k/2})$ với $\gcd(q-1,e)=1$ và $2^\delta<\lvert p-q\rvert$.
- tính toán $n\được p\,q$ và $d\gets e^{-1}\bmod\operatorname{lcm}(p-1,q-1)$, xuất khóa công khai $(n,e)$ và khóa riêng $(n,d)$.
Có thể tin rằng: đối với bất kỳ lựa chọn hợp lệ nào về $e$ trong thuật toán tạo khóa này, cho bất kỳ đa thức nào $P$, không tồn tại thuật toán Thời gian đa thức xác suất mà khi $\kappa$ phát triển phá vỡ mã hóa RSA với xác suất không biến mất trong thời gian $P(\kappa)$.
Phỏng đoán hợp lý đó được ngụ ý rõ ràng¹ được ngụ ý bởi một dạng phỏng đoán RSA phổ biến và đơn giản hơn cho số mũ công khai cố định/nhỏ, loại bỏ bước (1.), thay thế điều kiện $2^\delta<\lvert p-q\rvert$ với $p\ne q$ ở bước (3.) và sử dụng $k$ ở đâu $\kappa$. Chúng tôi không có bằng chứng cho thấy các phỏng đoán là tương đương, nhưng không có lý do thuyết phục nào để tin vào điều khác, do đó, nhiều học viên và hầu hết các nhà lý thuyết sử dụng phỏng đoán đơn giản hơn².
¹ Phác thảo bằng chứng: chúng tôi giả sử tồn tại một $e$ và thuật toán $\mathcal A$ phá vỡ mã hóa RSA với xác suất không biến mất trong thời gian $P(\kappa)$ khi sử dụng tạo khóa RSA với $2^\delta<\lvert p-q\rvert$. Chúng tôi sử dụng $\mathcal A$ để xây dựng một thuật toán $\mathcal A'$ kêu gọi $\mathcal A$ như một chương trình con, mà cho cùng một $e$ phá vỡ mã hóa RSA với một số xác suất trong thời gian $P'(k)$ khi sử dụng tạo khóa RSA với $p\ne q$. Xác suất không biến mất vì $p$ và $q$ đáp ứng điều kiện bảo hiểm $\mathcal A$ hoạt động với xác suất mà chúng ta có thể giới hạn dưới và không biến mất. chúng ta có thể thành lập $P'$ từ $P$, $\alpha$ và $\beta$, và đó $P'$ vẫn là một đa thức. $\alpha<1$ vào trong chơi.
² Thường thì điều kiện $p\ne q$ cũng bị xóa, điều này dẫn đến khả năng giải mã không thành công.Điều đó xảy ra đối với một tỷ lệ biến mất của các khóa được tạo, nhưng một số định nghĩa về mật mã không loại trừ trường hợp góc như vậy, đó là lý do tại sao chúng tôi giữ $p\ne q$.
