RSA的加密解密原理

基本认识基础

欧拉函数：任意给定正整数 $n$ ，欧拉函数 $\varphi(n)$ 表示在小于等于 $n$ 的正整数中与 $n$ 构成互质关系的 $n$ 的个数。

关于欧拉函数的计算需要明白一点，任意一个大于1的正整数可以写成一系列质数的积，及如果

$\varphi (n)=\varphi (p_1*p_2*p_3...p_m)$ ,其中 $p_1,p_2,p_3....p_m$ 均为质数 $prime$ ，那么 $p_1和p_2*p_3...p_m互质$ ，并且剩余部分切分以后也存在互质关系。因此根据欧拉函数的性质可以推倒出：

$\varphi (n)=\varphi (p_1)*\varphi (p_2)*\varphi (p3)....\varphi (p_m)=(p_1-1)*(p_2-1)*(p_3-1)....(p_m-1)$

欧拉定理：如果两个正整数 $m和n$ 互质，那么 $m^\varphi(n)mod(n)\equiv 1$ ,即就是 $m的\varphi(n)次方被n除的余数是1$

RSA的加密过程，假设alice和bob要通信。

1、alice随机选择两个不相等的大质数 $p和q$ 。

2、计算 $p和q$ 的乘积 $n$ ，即 $n=p*q$ 。

3、随机选择一个整数 $e使得1<e<\varphi (n)并且e跟\varphi(n)互质$ 。

4、计算 $e跟\varphi (n)的模反元素d，使得ed\equiv 1\varphi (n)。$

5、将n，e封装成公钥 $pub(n,e)$ ,n，d封装成私钥 $pri(n,d)$ 。

知道n，e的情况下很难推倒出d， $因为大整数的质因数分解是一件非常困难的事情$ 。

现在公钥和私钥已经生成，假设bob要向alice发送的明文为m,那么Bob需要用alice的公钥进行加密：

$m^e\equiv c mod(n)$

先在alice收到密文c需要进行解密：

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。