模表示法

  为了描述RSA公钥加密系统，可以方便地采用记号x(mod m)来表示数值x被m除得到的余数，如9(mod 7)=2。注意，若x是一个0到m-1范围的整数，那么x( mod m)=x。
数学告诉我们，若p和q是素数，m是从0到pq之间的一个整数，那么对于任意正整数k，有：

假定p和q分别为素数3和5，m为整数4，对于此论断来说，对于任意正整数k，值mk(p-1)(q-1)除以15将产生余数1。具体说，若k=1，则：

若k=2时：

公钥密码学

现在我们将在RSA算法的基础上建立和分析一个加密系统，首先挑选两个素数p和q，它们的乘积用n表示。然后挑选另两个正整数e和d，使得对于某个正整数k，有e×d=k(p-1)(q-1)+1。值e和d分别是加密和解密过程的组成部分（已被证明是数学事实）。
于是我们选取了五个值：p、q、n、e、d。值e和n是加密键，值d和n是解密键。值p和q值用来建立加密系统。

加密过程

现在来看消息怎样加密，这里假定一个消息编码为位模式（ASCII或Unicode），翻译为二进制时这个位模式的值小于n（如果它不小于n，就得把消息分割成小段，再分别对每段进行加密）。
假设翻译为二进制表示时，我们的消息表示为值m。于是消息的加密版是值c=me(mod n)的二进制表示。就是说，加密后的消息是me除以n所得余数的二进制表示。

解密过程

为了对以二进制表示的值所表示的信息解密，要计算cd(mod n)。就是计算cd，结果除以n，保留余数。这个余数就是原消息m。因为：

总结

概括来说，一个RSA系统的产生是通过选取两个素数p和q，再从这两个数产生值n、e、d。值n和e用来加密消息，即公钥。值n和d用来解密信息，即私钥。这种系统的漂亮在于，知道如何加密消息，却不能解密消息。所以加密键n和e可以广泛传播，确实，即使你的对手可能得到这些加密键，他们还是不能对截取的消息进行解密。因为只有知道解密键的那个人才能解密消息。
这种系统的安全所基于的基础是，只知道加密键n和e，不允许计算解密键d和n，但是，有做这种事的算法呀！一种方法可以找值n的因数来发现值p和q，再找一个值k，使得k(p-1)(q-1)+1被e整除（商为d），而确定d。另一方面，这个过程的第一步就可能是费时的（尤其如果值p和q取得非常大）。事实上，如果p和q大得其二进制表示需要几百位，那么即使最著名的求因数算法也要花上几年的时间才能从n求出p和q。因此，一个加密消息的内容，即使是在其保密性要求已经过时很久后，它的安全性仍会保持。