实际上目前基本简化成lcm (p-1,q-1)而不再考虑carmichael函数，我们再取一个质数，随便选一个，比如8171,因为生成私钥过程的p,q非常大所以我们可以非常的确定 8171 < lcm (p-1,q-1).

这个时候找出8171在 lcm(p-1,q-1)上的模倒数，即 a*8171=1 mod lcm(p-1,q-1) 不知道什么是模倒数的同学可以这样理解， 也可以说存在这样一个k整数, such that k* lcm(p-1,q-1)+1 = a*8171.

这个时候 这个算出来的a,连带 lcm(p-1,q-1)的值就是私钥。

而8171 和pq的乘积就是公钥。当然现在RSA公钥可能连8171这种质数都不保存而是使用一个统一的大质数，也就是说公钥只保存pq的乘积。

下一步就是加密和解密过程了。

在先前计算出的私钥是：模倒数a, lcm(p-1,q-1)

公钥是8171, pq

讲要加密的信息数字化即可(比如最丑陋的可以按照ascii编码成一个二进制数字）叫数字t.

加密过程就是把t^8171=x mod pq, x这个值就是加密后的值。解密过程则就是 x^a=y mod pq, y其实是等于t的。

如何证明 x^a=y mod pq的 y 必然等于t?

我们来看 t^(8171*a)这个东西，也就是说某种程度t^8171是加密，而t^(8171*a)是解密。

还记不记得 8171*a= 1 mod lcm(p-1,q-1)， 对！这个就是关键，8171*a-1 = k* lcm (p-1, q-1) 某个常数k

所以 t^(8171*a) = t^(8171*a-1) *t

那么显然8171*a-1是等于p-1,或者q-1的倍数，我们单独的来看其中的一个p-1

则显然 t^(8171*a-1)*t= t^(k(p-1))*t 某个整数k符合。

交换一下冥 就得到 t^[(p-1)*k] *t

我蛮看一下在模上面的情况； t^[(p-1)*k] *t = ? mod p

这个时候要动用一个著名的定理，费马小定理: i^(p-1)=1 mod p 当p为质数的时候

所以t^[(p-1)*k]*t = ? mod p 得出( t^(p-1))^k * t =? mod p 得出 1^k *t = ? mod p 得出 t=? mod p，所以 ? 必然等t.

所以 t^(8171*a)=t mod p

然后运用中国剩余定理在质数p,q上即可以得出 t^(8171*a) =t mod (pq)

所以在模的角度，用公钥加密，私钥解密，还是用私钥加密，公钥解密，从费马小定理的角度来看是完全等价的，即公钥，私钥顺序无关且等价。另外可以看到中国剩余定理在代数数论上的频繁使用，无论是carmichael函数的推导还是加密解密的过程都动用了n次中国剩余定理，这个古老的定理是天朝为数不多的，给数学和计算机出的重大科学贡献的定理。

私钥强度的证明比较简单，用可计算理论即得得出：

因为密钥a是通过charmichael 函数lcm (p-1,q-1)取模反得出的，而carmichael lcm(p-1,q-1)的计算必须要分别知道p和q,而质数分解是个np问题，则显然密钥是无法通过分解pq这个公钥快速得出的。

好了，rsa的加密就讲完了，下次讲一下椭圆曲线的加密过程，东西会比这个更多一点。