RSA算法证明

随机选取两个质数p1、p2，n=p1xp2，再随机选取一个整数e，e与φ(n)互质, e通常为65537, 再次计算一个d, 它是e对于φ(n)的模反元素,也就是e x d ≡ 1 (mod φ(n))
加密过程：(m^e) mod n=c，其中m为原信息（注意m < n），c为加密信息，n、e为公开密钥。
解密过程：(c^d) mod n=m，其中d为解密密钥。

上面就是加密和解密进行的操作了，我们后面可以证明一下，在证明之前，我们先介绍几个数学概念：

模反元素：如果两个正整数a和n互质，那么一定可以找到整数b，使得 a x b-1 被n整除，或者说ab被n除的余数是1，即a x b ≡ 1 (mod n)
φ(n):小于n且与n互质的正整数的个数，比如φ(10) = 4,因为小于10且与10互质的的数为1，3，7，9
欧拉定理：m和n互质，则m^φ(n) ≡ 1 (mod n)
欧拉函数：如果n为质数，φ(n)=n-1
欧拉函数是积性函数：若m,n互质， φ(mxn)=(m-1)(n-1)
同余性质：
1).反身性：a≡a (mod m)；
2).对称性：若a≡b(mod m)，则b≡a (mod m)；
3).传递性：若a≡b(mod m)，b≡c(mod m)，则a≡c(mod m)；
4).同余式相加：若a≡b(mod m)，c≡d(mod m)，则a+c≡b+d(mod m)；
5).同余式相乘：若a≡b(mod m)，c≡d(mod m)，则axc≡bxd(mod m)。(特殊情况c=d下也成立)
6).幂运算：如果a≡b(mod m)，那么a^k≡b^k(mod m)；

下面开始证明,也就是证明：通过解密过程，可以从加密后的数据c得到加密前的数据m
解密过程的运算是

c^d ≡ m (mod n)

因为加密过程为

(m^e) ≡ c (mod n)
即
c = m^e - k x n

所以我们可以试图证明

(m^e - k x )^d ≡ m (mod n)

继续展开左边，相同与求证如下，因为看k x n的任意次方都是可以被n整除的，可以忽略

m^(e x d) ≡ m (mod n)

因为e和d是对于φ(n)的模反元素，即,exd = h x φ(n) + 1，就变成证明

m^(h x φ(n)+1) ≡ m (mod n)

考虑m和n互质与不互质两种情况
case 1：m和n互质，直接根据欧拉定理m^φ(n) ≡ 1 (mod n)，根据同余的乘法性质

m^(h x φ(n)) x m = m (mod n)
即
m^(h x φ(n)+1) ≡ m (mod n)

证明完毕

case 2：m和n不互质，因为m < n （这是算法前提），n = p x q,所以m必然为p或者q的k倍，假设m=kxp,
其实这时k一定和q互质，因为k x p < q x p,q又是质数，然后kxp也必然和q互质。还是根据欧拉定理

(k x p)^φ(q) ≡ 1 (mod q)
根据欧拉函数
(k x p)^(q-1) ≡ 1 (mod q)

继续根据同余的幂运算和乘法运算性质

(k x p)^((q-1) x h x (p-1)) x (k x p) ≡ k x p (mod q)

根据欧拉函数是积性函数

(k x p)^（φ(p x q) x h) x (k x p) ≡ k x p (mod q)
继续
(k x p)^(φ(n) x h + 1) ≡ k x p (mod q)

考虑到e和d是对于φ(n)的模反元素,即e x d = h x φ(n) + 1

(k x p)^(e x d) ≡ k x p (mod q)
换种写法
(k x p)^(e x d) = t x q + k x p

因为p是一个大质数，t x q必然整除p，q不能整除p，所以t必然整除p

(k x p)^(e x d) = t1 x p x q + k x p

因为m = k x p,n = p x q，所以

m^(e x d) = t1 x n + m
m^(e x d) ≡ m (mod n)

证明完毕。

折腾完毕之后发现跑题了，我们只向看看指数和模数的使用而已，一句话，它们就是公钥。也就是说证书里包含了公钥。前面看到，证书里还有一些签名的东西。签名是啥呢？
签名就是CA对其颁发证书的一个认同。