双素数密码
最早广为流传的公钥密码体系称为RSA(Rivest,Shamir, Adleman)密码体系。它是非对称密码体系，基于整数的模幂运算和大整数因子分解的难解性。一般技术通称位双素数密码，不同的是，RSA基于初等数论：令$n = pq$，其中$p,q$是较大的素数，也许它们都超过100位。这样的$n$被我们称为双素数，他指的是一个数$n$可以被分解为2个素数的乘积。现在我们假设存在一个合数$n$，它的位数可能有$140$或者200位，计算刚才提及的$pq$分解是十分困难的，或者直截了当，这是完全不可能的。因子分解的复杂难解性。对于因式分解，至今也没有好的方法。
现在我们将开始在环$Z_n$上展开讨论，其中$Z_n$是指整数上的模$n$同余类构成的环，若其中$n$是素数。在这种情况下$Z_n$构成一个域。现在，对$Z_n$，其中$n$是一个不相等的大素数乘积。现在，整数$n$是公开的，素数$p,q$由解密器保密，并且对加密器也保密。因为$n$是素数乘积，关于$n$的欧拉定理表示：$\phi=(p-1)(q-1)$。在这种情况下，我们可以通过$p,q$简单计算得到，但通过$n$则不现实。现在我们选取加密指数$b,b\in Z_n$，由欧几里得算法，我们计算$GCD(b,\phi) =1$是否成立，若不成立，重新选择$b$，若成立，则利用拓展欧几里得算法继续计算$a = b^{-1}\mod \phi(n)$，由于$b,\phi$互素，因此$a$的存在是被保证的。
而加密秘钥$b$是公开的，$n$也是公开的，但解密密钥$a$是保密的，且不能由$b,\phi(n)$计算得到。一个漏洞就是，$a = b^{-1}\mod \phi(n)$，但这无伤大雅，$\phi$对不知道$p,q$的人来说是不清楚的，他们没办法得到$\phi(n)$本身。所以计算$a$本身是不可能的。因为这等价于对$n$进行因式分解。
现在我们谈谈加密过程：对任意的$x\in Z_n$，定义映射$y = e_k(x) = x^b\mod n$，则一个加密的过程可以用$Z_n\to Z_n$的映射表示。而解密是一个反的过程，对$y\in Z_n$，我们计算$d_k(y) = y^a\mod n$，其中$a =b^{-1}\mod \phi(n)$
那么我们要做的事情就是，先来验证一下是否可以还原信息
命题1
在双素数密码体系中，对两个映射$d_k,e_k$存在$d_k(e_k(x)) = x$对任意$x\in Z_n$成立。
证明：首先，由于我们定义$a = b^{-1}\mod \phi(n)$，注意$\phi(n) = p-1$。于是我们可以重写位$ab = 1+r\phi(n)$对整数$r$成立，则$d_k(e_k(x)) = (x^b)^a \mod n = x^{1+r\phi(n)} \mod n = x(x^{\phi(n)})^r$，那么现在我们有2种情况，由于$n$不一定是素数，因此，若$x$有逆，则利用欧拉定理，我们有
因此在$\mod n$的情况下，最终我们得到$d_k(e_k(x)) = x \mod n$
其次，若$x$是不存在逆的。在这种情况下，$n,x$是不互素的，那么$\gcd(x,p) = p$或者有$\gcd(x,q) =q$成立，我们不妨假设$\gcd(x,q)=1$，其他不变，则$x = 0\mod p$。就有$x^{ab} = x=0\mod p$。另一方面，由于$\gcd(x,q)=1$，再由欧拉定理可知$\phi(n)=\phi(q)\phi(p)$，跟上面一样，我们重写$\phi(ab) = 1+r\phi(p)\phi(q)$。利用中国剩余定理，我们知道$p,q$互素，则这里存在一个解使得$\mod pq = \mod n$成立。即$x^{ab} = x^{1+\phi(q)\phi(p)} = x\mod pq$，在$\mod q$的情况下，我们有$x^{ab} =x\mod q$，综上所述，无论是$\mod p$还是$\mod q$，$x^{ab} = x$是成立的，因此就有$x^{ab}=x\mod n$成立。
因此，在任何情况$d_k(e_k(x)) = x$都是成立的。
上述证明的注意点是无论如何$x$都是可以表示出来的。而RSA的安全性基于一个事实，记$e_k(x)$实际上是一个单向函数，但是一个有点点缺陷的，所以选择RSA加密需要一个比较大的素数来防止破解。例如选择一个$p,q$在大概500位的素数，则这样会产生$1000~4000$的双素数，分解这些素数是非常困难的。
我们选取$p=1171$和$q =1019$，则$n = 1193249$，而$\phi(n) = 1191060$。现在我们由解码器随机选择解密指数$a =1076531$，则$b = a^{-1}\mod \phi(n) = 120251$，那么信息$x$将会被加密为$y = x^{120251}$，密文$y$被解密为$x = y^{1076531}$