Rsa
RSA
我们选择长度（位数）为$b$的两个大素数$p$，$q$。（由于$[1,2^{b})$中素数的分布大致为$\frac{2^b}{b\ln 2}$，因此可以有大约$\frac{1}{b}$的概率能够选中素数，再利用高效的miller-rabin算法进行测试，可以比较容易地得到这样的素数）
首先我们定义$n=(p-1)(q-1)$。
我们再选择一个与$n$互质的奇数$e$。
由于$e$与$n$互质，因此存在数$c$，满足$c\cdot e=1 \mod n$
我们将$(e, n)$作为公钥，将$(c, n)$作为私钥。
定义$P$为公钥加密算法，其接受一个数值$M$作为输入，并进行公钥加密，其公式为：
\[P(M)=M^e \mod n\]定义$S$为私钥加密算法，其接受加密后的数值$M$为输入，并进行私钥加密，其公式为：
\[S(M)=M^c \mod n\]命题： $P(S(M))=S(P(M))=M \mod n$
证明：
首先$P(S(M))=M^{ec}=S(P(M))$，因此我们只要证明$M^{ec}=M\mod n$
\[M^{ec} \mod p=M^{1+k(p-1)(q-1)} \mod p=M\cdot (M^{p-1} \mod p)^{k(q-1)} \mod p\]由费马小定理可知$M^{p-1} \mod p=1$，因此
\[M^{ec} \mod p=M \mod p\]同理可得
\[M^{ec}\mod q=M \mod p\]由于$M^{ec}$对两个互质的数$p$，$q$同余，由中国余数定理可知$M^{ec} \mod n = M \mod n$。