Rsa

Published: by Creative Commons Licence

  • 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$作为输入,并进行公钥加密,其公式为:

定义$S$为私钥加密算法,其接受加密后的数值$M$为输入,并进行私钥加密,其公式为:

命题: $P(S(M))=S(P(M))=M \mod n$

证明:

首先$P(S(M))=M^{ec}=S(P(M))$,因此我们只要证明$M^{ec}=M\mod n$

由费马小定理可知$M^{p-1} \mod p=1$,因此

同理可得

由于$M^{ec}$对两个互质的数$p$,$q$同余,由中国余数定理可知$M^{ec} \mod n = M \mod n$。