密钥生成
随机选择两个不相等的质数p和q。
例子中选择了7和11。（实际应用中，这两个质数越大，就越难破解。）
计算p和q的乘积n。
n = 7×11 = 77
n的长度就是密钥长度。77写成二进制是1001101，一共有7位，所以这个密钥就是7位。实际应用中，RSA密钥一般是1024位，重要场合则为2048位。
计算n的欧拉函数φ(n)。
因为7和11为互质关系，根据欧拉定理可直接计算出φ(n)
φ(n) = (p-1) (q-1)
60 = 6 10
随机选择一个整数e，条件是1< e < φ(n)，且e与φ(n) 互质。
在本例子选择e等于67
计算e对于φ(n)的模反元素d。
ed ≡ 1 (mod φ(n))
ed - 1 = kφ(n)
ex + φ(n)y = 1
已知 e=67, φ(n)=60
67x + 60y = 1
根据欧几里得拓展算法，求x,y
67x + 120y = 1
120 = 67 + 53
67 = 53 + 14
53 = 14×3+11
14 = 11+3
11 = 3×3 +2
3 = 2+ 1
1 = 3-2
2 = 11 - 3×3
3 = 14 -11
11 = 53 - 14×3
14 = 67 - 53
53 = 120 -67
1 = 3 -2
1 = 3 -(11-3×3)
1 = 4×3 - 11
1 = 4×(14-11)-11
1 = 4×14 - 5×11
1 = 4×14 - 5×(53-143)
1 = 19×14 - 5×53
1 = 19×(67-53) - 5×(120-67)
1 = 24×67 - 19×53 - 5×120
1 = 24×67 -19(120-67)-5×120
1 = 24×67 -24×120 + 1967
1 = 43×67 -48×60
加密和解密
加密
加密要用公钥 (n,e)，m必须是整数（字符串可以取ascii值或unicode值），且m必须小于n。
$$m^e\equiv c(mod\quad n)$$
这里的公钥是(77,67),假设需要加密的M=75
$$75^{67}\equiv c(mod\quad 77)$$
计算c的过程如下
$$75^{1} mod\quad 77 = -2 $$
$$75^{2} mod\quad 77 = 4 $$
$$75^{4} mod\quad 77 = 16 $$
根据欧几里得原理
$$75^{60} mod\quad 77 = 1 $$
$$75^{67} mod\quad 77 =75^{60}75^{4}75^{2}75^{1} mod\quad 77 = 1164（-2）mod\quad 77 = （-13）*（-12） = 26$$
解密
解密要用私钥 (n,d)，这里的私钥是（77,43）需要解密的密文是26
$$26^{43}\equiv m(mod\quad 77)$$
计算m的过程如下
$$26^{1} mod\quad 77 = 26$$
$$26^{2} mod\quad 77 = 60$$
$$26^{4} mod\quad 77 = 58$$
$$26^{8} mod\quad 77 = 53$$
$$26^{16} mod\quad 77 = 37$$
$$26^{32} mod\quad 77 = 60$$
$$26^{43} mod\quad 77 = 26^{32}26^{8}26^{2}*26^{1} mod\quad 77 = 75$$
引用
无
