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$。