|RSA| Việc $\phi(n)$ hoạt động như mô đun RSA có bình thường không?

Vì vậy, tôi tình cờ thực hành RSA trên giấy cho một kỳ thi, tôi đã thực hiện toàn bộ quy trình mà tôi đã viết dưới đây, và khi tôi thử mã hóa và giải mã, tôi đã bị phân tâm và thay vì thực hiện $m^e \mod n$

tôi đã làm $m^e \mod {\phi(n)}$ và cả quá trình giải mã và mã hóa đều hoạt động. Điều này có bình thường không?

Đây là những con số: $$ p = 11\ q = 23\ n = (p\cdot q) = (7 \cdot 23) = 253\ \phi(n) = (p-1) \cdot (q-1) = 220\ e = 7\ d = 63 \ $$ Tôi đã nhận được d khi sử dụng Thuật toán Euclide mở rộng: $$ gcd(220, 7)\ 220 = 7 * 31 + 3 \ 7 = 3 * 2 + 1 \ $$ $$ 1 = 7 + 3(-2)\\ 1 = 7 + (220 + 7(-31))(-2)\\ 1 = 7(63) + 220(-2)\\ $$

Nói chung, một cặp số mũ giải mã RSA được tính theo cách này cho một mô đun $N$ cũng sẽ hoạt động cho bất kỳ mô-đun nào $M$ thỏa mãn $\lambda(M)|\phi(N)$ ở đâu $\lambda$ là chức năng carmichael.

trong ví dụ của bạn $M=\phi(N)=220$ và $\lambda(M)=\mathrm{lcm}(\phi(4),\phi(5),\phi(11))=\mathrm{lcm}(2,4,10)=20$ thực sự chia $\phi(N)=220$. Tập hợp các tình huống này được hỗ trợ bởi thực tế là 11 chia hết $\phi(23)$. Nói chung nếu mô đun RSA $pq$ có $p|q-1$ sau đó $\phi(p)|\phi(\phi(q))$ và điều này giúp rất nhiều.

Loại hiện tượng này ít có khả năng xảy ra khi $p-1$ và $q-1$ có ước số nguyên tố lớn. Tuy nhiên, có thể xây dựng các ví dụ khác bằng cách chọn $p$ và $q$ ở đâu $p-1$ và $q-1$ không chia hết cho bất kỳ số nguyên tố lớn nào, nhưng chia hết cho tất cả các lũy thừa nguyên tố nhỏ.