两年后，ronald l.rivest，adi shamir和leon：删adleman提出了一个满足上述要求的算法［rivest 78］。这个算法被命名为rsa算法，是目前使用的最著名也最通用的非对称加密算法。它的非常简单的工作原理立足于大整数的算术，两个密钥由两个大的素数产生。加密和解密

　　的过程可用数学表示如下：

　　n=公开模数=p.q p.q＝两个秘密的素数。

　　在进行编码之前，明文字组的大小必须填补到合适的字组大小，它随着所用密钥的长度在rsa算法中的不同而改变。加密的本身是执行明文的指数的模数运算，这一处理的结果就是密文。如果已知私有钥密，则只有用它才能解密，解密的过程类似于加密过程。

　　算法的安全性建立在分解大数因数的困难之上，用两个素数相乘很容易求得公开的模数，但要把此模数分解成两个素因数则非常困难，因为对这种运算没有有效的算法。

　　ic卡的ram容量对于执行加密和解密电文时所需的大数的指数运算来说是不适用的，因为在接受模数运算之前这个数就已经变得很大了。因此，使用了“模数”的指数，这就是说计算的中间结果，绝不会超过模数之值。例如，如果必须计算x2 mod n，则并不直接去计算表达式（x，x）mod n，因为中间结果（x，x）在模数运算把它减小之前就已经不必要地变得太大了。相反，计算的是表达式（（x mod n）·（x mod n））mod n，它可得到相同的数学结果。这样做的好处是明显地减少了计算而存储量也较小，因为中间结果的大小被立即减小了。

　　另一个提高rsa算法的方法是用中国剩余定理来计算①。当然，使用中国剩余定理的前提是要知道这两个秘密素数p和g，这就是说它只能用于解密（简而言之，用于签署）。

　　私有密钥应当尽可能地大，因为这样可阻止破译的企图。公开密钥和私有密钥可有不同的长度，事实上通常也是这种情形，因为验证数字签名所需的时间随着把公开密钥尽量减小而明显地缩短。第4个fermat数经常被用来作为公开密钥。这个素数之值为216+1=65 537，而由于它比较小，所以非常适合快速验证数字签名，同样也使用数字7和17，参见表1。

　　表1 rsa算法的典型的公开密钥

　　如果一个攻击者成功地把公开模数分解为两个素因数，将能重现整个加密过程。对于一个小的数值，例如l1，分解此模数是很容易的，但是目前没有快速的算法可用于大数。如果能找到两个素因数之值，系统就被攻破，因为私有密钥已被知道了。②因此。对rsa密钥的需求是要有足够长。长度为512位（“字节），在目前被认为是下限。无论如何，768位（96字节）和1 024位（128字节）的密钥都已在使用中。在即将来临的年月里，2 048位（256字节）的密钥将会投入使用。加密和解密所需的计算量随密钥长度而增加，这种增加不是线性的，相反却是近似于指数的。

　　具有8位cpu的智能卡微控制器通常不能在短于数分钟的时间内执行rsa计算。然而，现在已经特别开发了具有可以快速求幂的辅助算术处理器的微控制器。有了它们，就有可能以合理的软件开销在可以接受的时间长度之内执行rsa计算。有硬件支持的512位的rsa算法的编码长度大约为300字节。对于768位和1024位长的密钥在智能卡中的汇编代码长度约有1kb。如果观察一下表2，将看到即使是一个512位长的密钥，其可能的素因数的数目也是如此巨大，使得在两个不同的密钥对之间的碰撞永远不会发生。①

　　表2 典型的rsa密钥长度和特性参数
　　（比值ns/np表明非素数的数目与素因数数目之间的关系，它的倒数就是在数字空间的一
　　个随机数是素数的概率，对于产生一个rsa密钥所需要的时间长度来说这是极其重要的）

　　然而，和des（举例）相反，rsa算法的实力之一在于它的密钥不限于一个特定长度，如果需要增加安全性，就可用比较长的密钥而不需要对算法做任何改变。于是，rsa算法是可缩放的，当然必须不能忘记计算时间和所需要的存储空间。在目前，即使5l2位的密钥也还被认为是安全的。对于目前的因子算法，一个很好的经验规律是密钥长度每增加15位，计算量就要增加一倍②。andrew odlyzko［odlyzko 95］对分解因数和破译非对称加密算法二者所需处理量以及在整个世界上实际可用的处理量给出了一个出色的总结。

　　虽然，rsa算法是非常安全的，但它却很少用于加密数据，因为计算时间太长了。它主要用在数字签名的领域，在这里非对称处理的好处得到了充分的体现，参见表3。对智能卡来说，rsa算法的最大缺点是密钥所需的存储空间量。在某些情况下，密钥产生的复杂性也会引起一些问题。

　　rsa的普遍应用受到在几个国家中已经