选择两个很大的素数，p，q

P与q相乘，获得大数n

计算w=（q-1）（p-1）

选一个数e，这个数和w互质（最大公约数为1）

计算d，e*d=1 mod (q-1)(p-1) d 是 e 在模 φ(n) 意义下的乘法逆元

得出公钥：e,n

得出私钥：d,n

加密算法：

假设输入一个数m

M^e mod n

得到运算结果，密文c

解密算法：

假设输入密文c

M^d mod n

得到运算结果，明文m

伪代码：

找两个大素数p,q

N=p*q

W=(p-1)*(q-1)

选一个数e，使gcd(e,w)=1

d*e = 1 mod w

公钥P = （e,n）

私钥S = （d,n）

对明文m加密得到密文c，1<m<n-1,有 C = m^e mod n

对密文c解密得到明文m，有m = c^d mod n

例题：令p=3、q=11，以手算方式进行RSA的实验计算：

N=3*11=33

W=2*10=20

令e=7，给出7与上述ϕ(n)的Euclid GCD算法的手算表(要求各个步骤中含有商 值列)。

E=7

手写公式：

Gcd(e,w)=1

=a51+w0

| No | A=e | B=w | R=a mod b | q | | 1 | 7 | 20 | 7 | 0 | | 2 | 20 | 7 | 6 | 2 | | 3 | 7 | 6 | 1 | 1 | | 4 | 6 | 1 | 0 | 6 | | 5 | 1 | 0 | | |