Trong "Tôi lấy 3072 cho Paillier's $n$", 3072 chắc chắn là kích thước bit của $n$. Vì vậy, tôi sẽ đọc câu hỏi là:
OU nên rộng bao nhiêu $n=p^2q$ an toàn như của Paillier $n=pq$ của 3072 bit?
Cuộc tấn công được biết đến nhiều nhất chống lại cả hai hệ thống mật mã là nhân tố hóa của $n$.
Phương pháp nhân tử hóa được biết đến nhiều nhất cho $n=pq$ với $p$ và $q$ các số nguyên tố ngẫu nhiên có cùng kích thước là GNFS, chi phí $L_n[1/3,4\cdot3^{-2/3}]$, mỗi ký hiệu L.
Đối với thừa số của $n=p^2q$, GNFS cũng hoạt động với chi phí tương tự, do đó chúng ta phải có $n$ ít nhất là 3072-bit. Tuy nhiên, ECM của Lenstra cũng là để xem xét, và (tôi nghĩ) chi phí là khoảng $L_{\min(p,q)}[1/2,2^{1/2}]$. Do đó, để tối đa hóa khả năng chống lại thuật toán sau này, chúng ta nên có $p$ và $q$ của bên cạnh cùng kích thước. Kích thước đó phải ít nhất là 1024-bit để có được 3072-bit $n$. Và nếu chúng ta làm phép toán và bỏ qua $o(1)$ Trong $L_k[\alpha,c]=e^{(c+o(1))\ln(k)^\alpha\ln(\ln(k))^{1-\alpha}}$, chúng tôi nhận được 1024-bit đó $p$ và $q$ là (hầu như không) đủ để ECM đắt hơn GNFS.
Do đó chúng ta nên có $p$ và $q$ ít nhất là 1024-bit, ví dụ: trong phạm vi $[2^{1024-1/3},2^{1024}]$ cho 3072-bit $n$. Nếu chúng ta muốn sai lầm ở khía cạnh an toàn vì chúng ta đã bỏ qua $o(1)$, chúng ta có thể va chạm điều đó một chút để ví dụ: 1152-bit, ví dụ: trong phạm vi $[2^{1152-1/3},2^{1152}]$ cho 3456-bit $n$.
Tính toán tương tự hỗ trợ Câu nói bí ẩn "RSA Moduli nên có 3 yếu tố chính" của thuyền trưởng Nemo.
Ngoài ra: bằng chứng hỗ trợ trong Mathematica, mang lại 0,5⦠(tương ứng 10,3â¦) cho logarit cơ số 2 của tỷ lệ công việc giữa các yếu tố ECM @1024-bit (tương ứng @1152 bit), cho công việc cho Sản phẩm GNFS @3072-bit. Hãy dùng thử trực tuyến!.
L[n_, a_, c_] := Exp[c (Log[n]^a) (Log[Log[n]]^(1-a))];
LGNFS[n_] := L[n, 1/3, 4 3^(-2/3)];
Llenstra[p_] := L[p, 1/2, 2^(1/2)];
Nhật ký[2., Llenstra[2^{1024,1152}]/LGNFS[2^3072]]