智能卡的算法的典型

　　两年后，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的普遍应用受到在几个国家中已经申请的的限制，以及包含有这种算法的设各在进出口上的主要限制。具有RSA协处理器的智能卡受到这些条款的影响，严重地妨碍了它们在国际上的应用。

　　RSA算法的密钥的产生是按照简单的处理进行的，下面是一个小型的逐步进行的例子：

　　（1）首先，选择两个素数p和g：                       P=3;q=11;

　　（2）其次，计算公开模数：                           n=P;q=33

　　（3）计算用于产生密钥的中间变量z：                  Z=（P-1）（q-1）

　　（4）计算满足条件e<z和gcd（z,e）=1的公开密钥e（这就是说z和e的公约数为1）

　　由于有几个数可满是这些条件选择其中之一：           e=7

　　（5）计算私有密钥d,它应满足条件（d,e）mod z=1;       d=3

　　这样就完成了密钥的计算，现在可用RSA算法对公开和私有密钥的加密和解密进行测试，用数字例子说明如下：

　　（1）以数字4为明文X（X＜n）：

　　（2）加密电文：

　　（3）计算的结果为密文y：

　　（4）对密文解密：

　　对密文解密的结果如所预期，重新得到了明文。

　　表3  作为密钥长度的函数的RSA加密和解密计算时间的样例
　　（所给出的数值的一部分有着明显的改变，这是因为它们依赖
　　密钥的位结构和采用了中国剩余定理算法，它仅能用于签署）

　　在实践中，产生密钥是比较辛苦的，因为测试大的数字以断定它们是否素数是极其困难的。的Eratosthenes的筛法在这里不能使用，因为它需要有关小于被检测数的所有素数的预各知识。对于像有512位这样大的数这在实际上是不可能的。因此，用概率测试来决定所选之数是素数的概率，Miller-Rabin检测和Solovay-Strassen检测①是这种检测的典型例子。为了避免过于经常使用这些耗费时间的测试，随机产生一个候选的数字并首先检验它是否具有小的素因子。如果这个随机产生的数字能够被诸如2、3、5或7这样的小素数整除，那么很明显它本身不是素数，一旦确定被检测之数没有任何小的素因子，则可应用像Miller-Rabin这样的检测。这一检测的原理已说明在图1中，而IEEE 1363标准的附录中则有详细描述。②。

　　表4  产生非对称加密算法RSA的公开和私有密钥对所需的时间之例
　　（无法给出准确的时间，因为对产生密钥的处理依赖于所产生的随机数是否素数）

　　产生RSA密钥的算法具有一特殊的性质，即产生一密钥对（一个公开密钥和相应之私有密钥）所需的时间只能是可统计预测的。这就是说，仅能以某个概率来指出产生密钥要占用的时间量。明确的断言，诸如“要占用笳秒”是不可能的，因为要对随机数运行素数测试，执行这一测试所需的时间无法预先断定，参见图2和表4所示。

　　图1  产生用于智能卡的RSA密钥的基本过程

　　图2  产生RSA算法的密钥对的概率的时间曲线（纵轴为以确定时间产
　　生一智能卡的1024位密钥的概率，曲线所覆盖的总面积之概率为1）

　　欢迎转载，信息来源维库电子市场网（www.dzsc.com）