Mật mã học

Đây là định lý khiến RSA thực sự dùng được: nó đảm bảo rằng bất kể người gửi mã hoá gì bằng số mũ công khai, người giữ số mũ bí mật luôn giải mã được, với mọi thông điệp có thể, không chỉ hầu hết — chứng minh phải xử lý trường hợp biên khi một thông điệp vô tình có chung thừa số với modulo.

Vì $ed \equiv 1 \pmod{\phi(n)}$, theo định nghĩa đồng dư modulo tồn tại một số nguyên không âm $k$ với $ed = 1 + k\phi(n)$.

Trường hợp 1: $\gcd(m,n)=1$. Định lý Euler cho $m^{\phi(n)} \equiv 1 \pmod n$, nên nâng cả hai vế lên luỹ thừa $k$ rồi nhân với $m$ cho $m^{ed} = m \cdot (m^{\phi(n)})^{k} \equiv m \cdot 1^{k} \equiv m \pmod n$.

Trường hợp 2: $\gcd(m,n) \ne 1$. Vì $n = pq$, điều này nghĩa là $p$ chia hết $m$ hoặc $q$ chia hết $m$ (không thể cả hai, vì $m$ nhỏ hơn $n$). Xét theo modulo $p$: nếu $p$ chia hết $m$ thì cả $m$ và $m^{ed}$ đều đồng dư $0$ theo modulo $p$; nếu không thì $\gcd(m,p)=1$ và định lý nhỏ Fermat cho $m^{p-1} \equiv 1 \pmod p$, và vì $(p-1)$ chia hết $\phi(n)$ nên cùng tính toán như Trường hợp 1 cho $m^{ed} \equiv m \pmod p$. Lập luận giống hệt theo modulo $q$ cho $m^{ed} \equiv m \pmod q$.

Theo định lý số dư Trung Hoa, một đồng dư đúng theo modulo $p$ và theo modulo $q$ riêng biệt thì cũng đúng theo modulo tích của chúng $n=pq$, nên $(m^e)^d \equiv m \pmod n$ đúng với mọi thông điệp $m$, không chỉ những thông điệp nguyên tố cùng nhau với $n$.

Đây là điều cho phép hai bên thoả thuận một khoá bí mật qua một kênh công khai mà kẻ nghe lén đang theo dõi: kẻ nghe lén thấy cơ số, modulo, và cả hai giá trị công khai, nhưng để khôi phục bí mật chung từ những thứ đó cần giải một bài toán logarit rời rạc, được tin là khó về mặt tính toán với các tham số được chọn tốt.

Theo định nghĩa, $A = g^a \bmod p$ và $B = g^b \bmod p$ là kết quả của luỹ thừa modulo, nên Bob nhận được $A$ và tính $B^a = (g^b)^a \bmod p$, trong khi Alice nhận được $B$ và tính $A^b = (g^a)^b \bmod p$.

Luỹ thừa modulo tuân theo cùng quy tắc số mũ như luỹ thừa thông thường, vì phép nhân lặp lại theo modulo $p$ kết hợp giống hệt phép nhân lặp lại các số nguyên, chỉ khác là được rút gọn theo modulo $p$ ở mỗi bước: $(g^b)^a = g^{ba} = g^{ab} = (g^a)^b$ xét như số mũ của $g$, và đẳng thức này vẫn đúng sau khi rút gọn theo modulo $p$ ở mọi giai đoạn.

Do đó $B^a \bmod p = g^{ab} \bmod p = A^b \bmod p$: Alice và Bob độc lập tính ra cùng một giá trị $g^{ab} \bmod p$ từ số mũ bí mật của riêng mình và giá trị công khai của phía kia, mà không bao giờ bí mật $a$ hay $b$ xuất hiện trên kênh.

Lập luận về an toàn tách biệt với lập luận về tính đúng đắn này: tính đúng đắn chỉ cho thấy cả hai bên đi đến cùng một số; độ khó của việc tính $a$ từ $g$, $p$, và $A$ (bài toán logarit rời rạc) mới là điều giữ bí mật số chung đó khỏi người quan sát.