Làm cách nào để chứng minh tính đúng đắn của công thức mã hóa và giải mã RSA cho $GCD(m_i,n)=1$ và $GCD(m_i,n) \neq1$ trong đó mã hóa được định nghĩa là $c_i = m_{i}^e$ mod n và giải mã $m_i = c_{i}^d$ chế độ n.
Vì vậy, cảm ơn @poncho đã đưa ra lời khuyên, tôi đã viết một bằng chứng sau:
Nhớ lại rằng các số nguyên $e > 0$ và $k > 0$ được chọn sao cho
$ ed = 1 + k(p â 1)(q â 1)$
Chỉ cần chứng minh hai phương trình bằng nhau là đủ
$(m^e)^d \equiv m\ \textrm{mod}\ p $ và $(m^e)^d \equiv m\ \textrm{mod}\ q $ tổ chức. p và q là các số nguyên tố khác nhau, vì vậy $gcd(p,q) = 1$ và các đồng dạng trên ngụ ý rằng
$(m^e)^d \equiv m\ \textrm{mod}\ n $ bởi Định lý phần dư Trung Quốc. Nếu $m \equiv 0\ \textrm{mod}\ p $, thì chắc chắn
$(m^e)^d \equiv m\ \textrm{mod}\ p $. Nếu $m \not\equiv 0\ \textrm{mod}\ p $, sau đó $m^{p-1} \equiv 1\ \textrm{mod}\ p $ bởi vì định lý nhỏ của Fermat ($a^{p-1} \equiv 1\ \textrm{mod}\ p $) vì thế,
$$ (m^e)^d \equiv m^{1 + k(p - 1)(q - 1)} \equiv m(m^{p-1})^{k(q-1)} \ tương đương m 1^{k(q-1)} \equiv m\ \textrm{mod}\ p
$$
Vì vậy $(m^e)^d \equiv m\ \textrm{mod}\ p $ đúng với mọi số nguyên m. Thay thế p bằng q trong đối số trước cho thấy rằng $m \equiv (m^e)^d \textrm{mod}\ q $ đúng với mọi số nguyên m
Mọi nhận xét về tính đúng đắn của bằng chứng của tôi đều được đánh giá cao!
