Người ta hỏi làm thế nào, trong RSA, người ta tìm thấy $e$ được cho $d$ và $N$. Tôi sẽ bỏ qua yêu cầu của câu hỏi rằng $e$ là nguyên tố cùng với $N$, điều này rất bất thường và không có liên quan đến toán học. Tôi cũng sẽ giả sử $p\ne q$, bởi vì nó là cần thiết cho đã nêu $\varphi(N)=(p-1)\cdot(q-1)$ để giữ.
Với định nghĩa của câu hỏi về RSA, phương pháp tìm $e$ đi
- Hệ số $N$ để tìm $p$ và $q$
- tính toán $\varphi=(p-1)\cdot(q-1)$
- tính toán $e$ biết $e\cdot d\bmod\varphi=1$ và $1<e<\varphi$. Điều đó $e$ được xác định duy nhất và nghịch đảo mô-đun của $d$ bên trong nhóm nhân của modulo số nguyên $\varphi$. Đối với các số nhỏ, một phương pháp làm việc là thử và sai số lẻ nhỏ $e>1$. Một phương pháp mang tính xây dựng hơn là (một nửa)-thuật toán Euclide mở rộng, tính toán $e=d^{-1}\bmod \varphi$ trực tiếp. Đối với một thuật toán thực tế chỉ sử dụng các số nguyên không âm:
- $a\được d\bmod \varphi$ , $b\được \varphi$ , $x\gets0$ và $y\gets1$
Ghi chú: $a\cdot x+b\cdot y=\varphi$ sẽ tiếp tục giữ
- nếu $a=1$, sau đó xuất "nghịch đảo mong muốn $e$ của $d$ modulo $\varphi$ Là $y$" và dừng lại
- Nếu $a=0$, sau đó xuất "nghịch đảo mong muốn $e$ của $d$ modulo $\varphi$ không tồn tại" và dừng lại
- $r\gets\lfloor b/a\rfloor$
- $b\được b-a\cdot r$ và $x\được x+r\cdot y$
- nếu $b=1$, sau đó xuất "nghịch đảo mong muốn $e$ của $d$ modulo $\varphi$ Là $\varphi-x$" và dừng lại
- Nếu $b=0$, sau đó xuất "nghịch đảo mong muốn $e$ của $d$ modulo $\varphi$ không tồn tại" và dừng lại
- $r\gets\lfloor a/b\rfloor$
- $a\được a-b\cdot r$ và $y\được y+r\cdot x$
- Tiếp tục lúc 2
Phương pháp tương tự này thường được sử dụng để tính toán $d$ từ $e$, từ $d$ và $e$ đối xứng trong $e\cdot d\bmod\varphi=1$. Tuy nhiên đó không phải là cách $d=11$ đã được tính toán trong câu hỏi; vì một số lý do kỳ lạ, câu hỏi yêu cầu $e<\varphi(N)$ nhưng không $d<\varphi(N)$, hoặc bình thường hơn $d<N$ hoặc $d<\operatorname{lcm}(p-1,q-1)$.
Vấn đề nghiêm trọng với phương pháp này đối với RSA như đã được thực hiện (do đó rất lớn $N$, ít nhất là hàng trăm chữ số thập phân): Nó sẽ không hoạt động, bởi vì $N$ sẽ lớn đến mức không thể tính được, do đó $\varphi$ không thể được tính toán theo cách này.
Ngoài ra, điều kiện của câu hỏi $e\cdot d\bmod\varphi(N)=1$ là điều kiện đủ, nhưng không phải là điều kiện cần để mã hóa RSA trong sách giáo khoa bằng cách sử dụng $(e,N)$ được hoàn tác bằng cách giải mã RSA bằng cách sử dụng $(d,N)$, và ngược lại. Điều kiện cần là $e\cdot d\bmod\lambda(N)=1$, ở đâu $\lambda(N)=\operatorname{lcm}(p-1,q-1)$. Điều kiện đó thường được sử dụng trong thực tế: nó được cho phép bởi PKCS#1, và được ủy quyền bởi FIPS 186-4. Ví dụ nhỏ nhân tạo: $N=341$, $e=7$, $d=13$ vẫn hoạt động tốt đối với mã hóa/giải mã RSA trong sách giáo khoa $e\cdot d\bmod\varphi(N)=1$ không giữ (trong ví dụ này $p=11$, $q=31$, $\varphi(N)=300$, $\lambda(N)=30$ ).
Tuy nhiên, trong RSA như thực tế, $e$ là nhỏ, thường đủ nhỏ để $e$ có thể được tìm thấy bằng cách liệt kê. Do đó, một phương pháp có thể là:
- tính toán $c\gets2^d\bmod N$
- tính toán $c_2\được c^2\bmod N$
- bộ $e\gets1$
- nói lại
- bộ $e\được e+2$
- bộ $c\được c\cdot c_2\bmod N$; lưu ý $c=2^{d\cdot e}\bmod N$
- nếu $c=2$
- vì $m$ hàng trăm số nguyên tố lẻ đầu tiên (lưu ý: đối với số nguyên tố nhỏ $N$, chúng tôi muốn dừng lại ngay khi $m^2>N$ )
- nếu $m^{e\cdot d}\bmod N\ne m$, tiếp tục tại nói lại ở trên
- đầu ra $e$ và dừng lại.
Gần như chắc chắn rằng nếu một $e$ là đầu ra, nó hợp lệ theo nghĩa mã hóa RSA trong sách giáo khoa bằng cách sử dụng $(e,N)$ được hoàn tác bằng cách giải mã RSA bằng cách sử dụng $(d,N)$, và (tương đương) $e\cdot d\bmod\lambda(N)=1$. Nó không hoàn toàn chắc chắn $e\cdot d\bmod\varphi(N)=1$, nhưng biết $e\cdot d$ và $N$ nó có thể yếu tố $N$ (dùng cái này thuật toán), rồi tính toán các $e$ với $e\cdot d\bmod\varphi(N)=1$ và $1<e<\varphi(N)$, nếu vì lý do nào đó được mong muốn.
Ngoài ra: Ở trên là xa tối ưu. Khi nào $\delta=\ln(e)/\ln(N)$ dưới một ngưỡng nhất định, theo thứ tự $0.292$, có nhiều cách để phân tích $N$ (và do đó giải quyết vấn đề bằng phương pháp đầu tiên được thảo luận). Về cơ bản, chúng tôi trao đổi $d$ và $e$ trong Dan Boneh và Glenn Durfee's Phân tích mật mã RSA bằng khóa riêng $d$ Ít hơn $N^{0,292}$, Trong thủ tục tố tụng của Eurocrypt 1999. Nhìn thấy ở đó để biết thêm.
