THẬN TRỌNG: Có điều gì đó không ổn trong câu hỏi nên có thể loại bỏ nó, xem phần thứ hai. Nhưng trước tiên chúng ta hãy cố gắng trả lời nó như thể chúng ta không để ý.
Trong một số định nghĩa hơi khác nhau về RSA trong sách giáo khoa,
- khóa riêng (được người giữ khóa sử dụng để giải mã) là $(d,n)$
- khóa công khai (được sử dụng để mã hóa bởi bất kỳ ai) là $(e,n)$,
- văn bản thô $m$ và bản mã $c$ là các số nguyên trong khoảng $[0,n-1]$,
- $n$, $d$ và $e$ được chọn sao cho với tất cả $m$ trong khoảng thời gian đã nói, chúng ta có thể tính toán
- $c:=m^e\bmod n$ để mã hóa, sau đó
- $m':=c^d\bmod n$ để giải mã, mang lại $m'=m$.
Ở trên$\bmod$là một toán tử có hai đối số, sao cho $x\bmod n$ là số nguyên được xác định duy nhất $y$ với $0\le y<n$ và $x-y$ bội số của $n$. Khi nào $x\ge0$ và $n>0$, điều đó $y$ là phần còn lại của phép chia Euclide $x$ qua $n$. Khoảng thời gian $[0,n-1]$ trong định nghĩa trên của RSA là vì nó là khoảng cho phần còn lại trong phép chia Euclide.
Câu hỏi yêu cầu số nguyên cao nhất $m$ tự tạo ra khi được mã hóa rồi giải mã. Các khóa đã cho cho thấy rằng $n=27$; do đó, câu trả lời (nhiều nhất) là $m=n-1=27-1=26$. Nó có ý nghĩa để xác minh rằng điều này $m$ được mã hóa và giải mã chính xác cho câu hỏi $d=5$ và $e=13$ theo định nghĩa trên của RSA. Bằng chứng đó rất dễ: ta có $m\equiv-1\pmod n$, và $e$ và $d$ là số lẻ, do đó $c\equiv(-1)^e\equiv-1\pmod n$, do đó $m'\equiv(-1)^d\equiv-1\pmod n$, do đó $m'=c=m=n-1$ vì đó là số nguyên duy nhất $y$ Trong $[0,n-1]$ với $y\equiv-1\pmod n$.
Lưu ý: ở trên $y\equiv x\pmod n$ có nghĩa: $x-y$ là bội số của khác không $n$. Trong sử dụng này$\bmod$không phải là toán tử có hai đối số, như được chỉ ra bởi dấu ngoặc đơn bên trái ngay bên trái của nó; hơn là,$\pmod n$ đủ điều kiện $\equiv$ (các) dấu hiệu ở bên trái, tương đương modulo $n$.
Có ít nhất một vấn đề nghiêm trọng trong câu hỏi: hầu hết các số nguyên $m$ trong khoảng thời gian $[0,26]$ sẽ không giải mã chính xác sau khi mã hóa! Nếu một người muốn thử, chỉ $0$, $1$ và $26$ làm như vậy (họ làm bất cứ điều gì kỳ lạ $e$ và $d$ được chọn). Hơn nữa, tất cả $m$ bội số của $3$ mã hóa giống nhau $c=0$, do đó trong số này nhiều nhất người ta có thể giải mã chính xác.
Vấn đề không chỉ có vậy $e$ và $d$ không phù hợp với điều đó $n$. Vấn đề là để RSA hoạt động cho tất cả $m$ trong phạm vi $[0,n-1]$ nó là cần thiết mà $n$ không vuông góc, không chia hết cho bình phương của bất kỳ số nguyên tố nào; nói cách khác, không có số nguyên tố nào xuất hiện hai lần trong quá trình nhân tử của $n$. Nhưng ở đây $27$ chia hết cho $3^2$. Nếu không có điều kiện bình phương đó, cho số lẻ $n$, vẫn có thể chọn $e$ và $d$ sao cho việc giải mã hoạt động với hầu hết $m$. Nhưng trong trường hợp hiện tại, $e$ và $d$ thậm chí không phù hợp với điều kiện¹ cho điều đó. Một khả năng là ban đầu câu hỏi được đặt ra cho $n=51$, mà làm cho $d=5$, $e=13$ đang làm việc; sau đó bất cẩn thay đổi thành $n=27$.
Nó đi tồi tệ hơn so với $(d,n)$ và $(e,n)$ tham số trong câu hỏi không hợp lệ đối với RSA: bất kỳ tham số RSA nào có kích thước tương tự đều không cho phép bí mật chia sẻ bất cứ điều gì.
RSA chỉ có thể an toàn nếu $n$ rất khó tính, đòi hỏi nó phải là hàng trăm chữ số thập phân. Vì vậy, bất kỳ bài tập với nhỏ hơn $n$ là về việc khởi tạo RSA không an toàn khi đối mặt với những kẻ thù có thẩm quyền bằng máy tính. Quan điểm của tôi là trong các ví dụ về RSA sư phạm $n$ phải đủ lớn để có một số khó khăn khi tính toán bằng tay. Ngoài ra, cần nhấn mạnh rằng mã hóa RSA xác định với văn bản gốc trong một tập hợp nhỏ (ví dụ: một khoảng thời gian nhỏ hoặc tên trên danh sách lớp) là không an toàn, bởi vì người ta có thể thử giải mã tất cả các văn bản gốc.
Ngoài ra, "hệ thống mật mã dựa trên RSA" được chỉ định một cách lỏng lẻo đến mức giả sử RSA trong sách giáo khoa như trong phần đầu tiên chỉ là suy đoán thuần túy.Đó là tuyên bố vấn đề chỉ là sai!
¹ Điều kiện cần và đủ để RSA sách giáo khoa giải mã chính xác, cho tất cả các số nguyên bản rõ $m$ Trong $[0,n-1]$ khi nào $n$ là vuông miễn phí, và ít nhất cho tất cả như vậy $m$ cùng nguyên tố với $n$ nếu không, là: $e\,d\equiv1\pmod{\lambda(n)}$, ở đâu $\lambda$ là chức năng carmichael. Nó thường được dạy một trong vài điều kiện hơi khác nhau, đủ nhưng không cần thiết. những cái phổ biến bao gồm $e\,d\equiv1\pmod{\varphi(n)}$, ở đâu $\varphi$ Là tổng của Euler; $d=e^{-1}\bmod{\varphi(n)}$, bổ sung ý nghĩa $0\le d<\varphi(n)$; $e=d^{-1}\bmod{\varphi(n)}$, được sử dụng trong bài viết gốc của RSA; $d=e^{-1}\bmod{\lambda(n)}$, mang lại giá trị dương nhỏ nhất $d$ để cho $e$.
