Rsa

Published: December 14, 2018 by Daltao

• Categories:
• algorithm 84

• Tags:

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