Chứng minh rằng RSA CCA là có thể

Tác giả đã quên một số $\bmod n$ dọc đường. Đặc biệt, phương trình 9.2 là sai, và nên được $$E(PU,M_1)\times E(PU,M_2)\bmod n=E(PU,(M_1\times M_2\bmod n))$$ Ngoài ra, những gì sau "lưu ý rằng" là sai ở dòng đầu tiên, thì khi đi từ dòng thứ hai đến dòng cuối cùng (kết luận là đúng).

Có thể tránh được sự lộn xộn này bằng cách sử dụng modulo đồng dư $n$, một Quan hệ tương đương Trong $\mathbb Z$ lưu ý $\equiv$ với$\pmod n$ ở cuối dòng. Nhớ lại điều đó cho $n,k\in\mathbb N^*$, $u,v\in\mathbb Z$

• tuyên bố $u\equiv v\pmod n$ có nghĩa $v-u$ là bội số của $n$
• tuyên bố $u=v\bmod n$ bổ sung có nghĩa là $0\le u<n$.
• nó giữ $$\begin{align} (u\bmod n)+v&\equiv u+v&\pmod n\ (u\bmod n)\times v&\equiv u\times v&\pmod n\ (u\bmod n)^k&\equiv u^k&\pmod n\ \end{align}$$

Với $\equiv$ ký hiệu, bằng chứng trở thành:

• định nghĩa $X:=C\times2^e\bmod N$ và gửi cái này để giải mã, mang lại $Y:=X^d\bmod n$.
• nó giữ $Y\equiv X^d\equiv(C\times2^e)^d\equiv C^d\times(2^e)^d\equiv C^d\times2\pmod n$, ghi chú điều đó $(2^e)^d\equiv2\pmod n$ bởi vì $2$ được mã hóa và giải mã.
• từ $0\le Y<n$ nó giữ $Y=2M\bmod n$, cho phép chúng tôi tìm thấy $M$ từ $Y$: nếu $Y$ thậm chí sau đó $M:=Y/2$, nếu không thì $M:=(Y+n)/2$.