1. 选出两个比较大的质数p，q
2. 计算$n=p*q$
3. 根据欧拉函数，$φ(n)=φ(p)φ(q)=(p-1)(q-1)$
4. 选取一个与φ(n)互质的整数e
5. 计算e关于φ(n)的模逆元d
6. 公钥KU=(d,n)，私钥KR=(e,n)，满足$$M^d\ mod\ n=C$$ $$C^e\ mod\ n=M$$(M为原文且M小于n，C为加密后密文)
   这样我们就能利用公钥通过加密得到密文，也能通过私钥解密得到原文

基础补充

首先欧拉函数φ(n)的含义是小于n并且与n互质的正整数个数，比如对于6而言，只有1和5与他互质（互质的意思是两个数最大公因数是1），所以φ(6)=2。
根据定义可知，质数的欧拉函数值等于它本身减一，因为比他小的数都与他互质，即对于质数p，φ(p)=p-1
又因为欧拉函数是积性函数，在pq互质情况下满足φ(n)=φ(p)φ(q)，所以φ(n)=(p-1)(q-1)
至于模逆元，指的是若d*e mod n=1，则d与e互为对n的模逆元
注意，当e与n互质时，一定存在e对n的模逆元d（后面会证明）

最后一步的推导

至于为什么当$M^d\ mod\ n=C$时 存在$C^e\ mod\ n=M$，我们在以下进行证明：
$C^e\ mod\ n=(M^d\ mod\ n)^e\ mod\ n =M^{de}\ mod\ n =(M^{kφ(n)}\*M)\ mod\ n$
根据欧拉定理 当M与n互质时，$M^{φ(n)}\ mod\ n=1$,所以$(M^{kφ(n)}\*M)\ mod\ n=M$，即$$C^e\ mod\ n=M$$
当M与n不互质时，参照以下链接的证明过程：

https://blog.csdn.net/qq_25847123/article/details/103141321

欧拉定理证明

若$p_1\ mod\ m\not=p_2\ mod\ m$,且$gcd(a,m)=1$，则$p_1\*a\ mod\ m\not=p_2\*a\ mod\ m$
反证法，若$p_1\*a\ mod\ m=p_2\*a\ mod\ m$，则$a\*(p_1-p_2)=km$，由于a与m互质且p1与p2对m不同余，所以不成立。
因此对于m的缩系$p_1,p_2……p_{φ(m)}$，若a满足$gcd(a,m)=1$，则$a\*p_1,a\*p_2……a\*p_{φ(m)}$也是m的缩系
$p_1\*p_2\*……\*p_{φ(m)}\ mod\ m=(a\*p_1)\*(a\*p_2)\*……\*(a\*p_{φ(m)})\ mod\ m=a^{φ(m)}\*p_1\*p_2\*……\*p_{φ(m)}\ mod\ m$
即当a与m互质时，$a^{φ(m)}\ mod\ m=1$

欧拉定理证明模逆元的存在

当e与n互质，根据欧拉定理$e^{φ(n)}\ mod\ n=1$，所以取$d=e^{φ(n)-1}$，则$de\ mod\ n=e^{φ(n)}\ mod\ n=1$

举例

接下来我们实操举个例子，比如我们选的两个质数是31和151，则$n=31\*151=4681$，$φ(n)=30\*150=4500$，选取e=7的话，$de\ mod\ φ(n)=1$，可取d=643,使得$de\ mod\ φ(n)=7\*643\ mod\ 4500=4501\ mod\ 4500=1$，这样公钥KU=(d,n)=(643,4681)，私钥KR=(e,n)=(7,4681)。
假设原文M=13，利用公钥加密，$13^{643}\ mod\ 4681=4258$，4258即是密文，$4258^7\ mod\ 4681 =13$，即我们根据密文和私钥得到原文。

真实情况远比这里要复杂的多，这边我也是第一次学习相关内容，有不足的地方欢迎指正。