2.3使用素数的RSA算法
RSA公钥加密算法是第一个既能用于数据加密也能用于数字签名的算法。它易于理解和操作，也十分流行。RSA算法就是素数的典型应用。下面简单介绍一下RSA算法，要完整地实现RSA算法，需要较长的代码，本书就不给出相应的程序了，而是重点介绍RSA的概念、原理和实现的过程。
2.3.1 什么是RSA
在计算机中常用的加解密技术分为两类，即对称加密和非对称加密。
在对称加密技术中，对信息的加密和解密都使用相同的密钥Key，如图2-8所示，也就是说使用同一个密钥Key对数据进行加密和解密。这种加密方法可简化加解密的处理过程，信息交换双方都不必彼此研究和交换专用的加解密算法。如果在交换阶段，密钥Key没有泄露，那么加密数据的机密性和报文完整性就可以得到保证。
图2-8
对称加密技术虽然简单，但存在一些不足，由于加密、解密都需要使用同一个Key，这样，信息传送双方都要接触到这个Key，密钥Key更容易泄露。
而非对称加密（又称为公开密钥加密）中，不再只有一个密钥Key了。在非对称加密算法中，密钥被分解为一对，一个称为公开密钥（简称公钥PK），另一个称为私有密钥（简称私钥SK）。对于公钥，可以通过非保密方式向他人公开，而私钥则由解密方保存，不用对别人公开。
发送信息的一方通过公钥对数据进行加密，然后发送给接收方。接收方通过私钥对密文进行解密，加、解密的过程如图2-9所示。
图2-9
由于非对称加密方式可以使通信双方无须事先交换密钥就可以建立安全通信，因此被广泛应用于身份认证、数字签名等信息交换领域。
非对称加密体系一般是建立在某些已知的数学难题之上，是计算机复杂性理论发展的必然结果。最具有代表性的非对称加密方式是RSA公钥密码体制。
2.3.2 RSA算法基础
在RSA算法中，最基础的一个定理就是RSA定理，这个定理描述如下：
若P和Q是两个相异质数，另有正整数R和M，其中M的值与（P－1）（Q－1）的值互质，并使得（RM）mod（P－1）（Q－1）＝1。有正整数A，且A＜PQ，设：
则有：A＝B
在以上描述中mod表示取余的运算。
在RSA算法中还引用了很多定理，详细介绍的话需要很大篇幅，这里就不逐一介绍了。下面介绍一下RSA算法的基础操作步骤。
1．生成公钥和私钥
生成公钥PK和私钥SK的步骤如下。
（1）随意选择两个大的素数P和Q，P不等于Q。
（2）将P、Q两素数相乘得到一个数N，即N＝PQ。
（3）将P、Q分别减1，再相乘，得到一个数T，即T＝（P－1）（Q－1）。
（4）选择一个整数E，作为一个密钥，使E与T互质（即E与T的最大公约数为1），并且E必须小于T。
（5）根据公式DE mod T＝1，计算出D的值，作为另一个密钥。
（6）通过以上步骤计算得出N、E、D这3个数据，其中（N、E）作为公钥，（N、D）作为私钥（当然也可以将公钥和私钥互换）。
（7）生成公钥和私钥后，就可以将公钥对外发布了，如图2-10所示。
图2-10
2．用公钥加密信息
发送信息的一方收到公钥PK后，就可以通过公钥PK对数据进行加密。加密的操作步骤如下，其中明文为M，加密后得到的密文为C，公钥为（N，E）。
3．用私钥解密信息
接收方持有私钥（N，D），在接收到密文C后，即可通过私钥进行解密，得到明文M。解密的过程如下：
2.3.3 RSA算法实践
了解RSA算法生成密钥、加密、解密的过程之后，接下来进行一次RSA算法的模拟操作，进一步了解RSA算法的使用过程。
1．生成公钥和私钥
生成公钥PK和私钥SK的过程如下：
2．用公钥加密
有了公钥，就可方便地进行数据加密了。在上面这个例子中的公钥为（143，7），私钥为（143，103），由于是手工计算，为了使计算的数据量小一点，因此将公钥与私钥进行交换，即公钥使用（143，103），而私钥则使用（143，7）。设明文为2，则加密过程如下：
3．用私钥解密
收到密文C（这里为63）后，则可以通过私钥（143，7）进行解密，解密过程如下：
从以上生成密钥、加密、解密的过程可以看出，虽然我们这里只使用了两个小的素数11和13，但其计算量却很大，特别是在加密和解密过程中，需要进行幂运算，得到的结果将是一个非常大的整数。在实际应用中，P、Q要取很大值的素数，则得到的N、D、E值也将很大，所以在加密、解密过程中的幂运算结果将更大，通过C语言（或其他程序设计语言）提供的基本数据类型已经没办法保存这么大的数了。
因此，在RSA算法中，虽然过程很简单，但需要编写程序处理大整数，包括大整数的加、减、乘、除、幂运算等。
2.3.4 RSA应用：数字签名
RSA的典型应用就是数字签名技术。
数字签名技术是实现交易安全的核心技术之一，它的实现基础就是RSA加密技术。在这里，我们介绍数字签名的基本原理。
以往的书信或文件是根据亲笔签名或印章来证明其真实性的。但在计算机网络中传送的报文又如何盖章呢？这就是数字签名所要解决的问题。数字签名必须保证以下几点：
接收者能够核实发送者对报文的签名；
发送者事后不能抵赖对报文的签名；
接收者不能伪造对报文的签名。
现在已有多种实现数字签名的方法，但采用公开密钥算法要比常规算法更容易实现。下面就来介绍这种数字签名。
发送者A用其私密密钥SKA对报文M进行运算，将结果DSKA（M）传送给接收者B。接收者B用已知的A的公开密钥得出EPKA（DSKA（M））＝M，如图2-11所示。
图2-11
因为除A外没有别人能具有A的私密密钥SKA，所以除A外没有别人能产生密文DSKA（M）。这样，报文M就被签名了。用私钥加密后的密文发送给对方，对方只能用持有的公钥进行解密，以实现核实发送者对报文的签名。
假若用户A要抵赖曾经发送过报文给用户B。用户B可将M及DSKA（M）出示给第三方。第三方很容易用PKA去证实用户A确实发送消息M给用户B。反之，如果是用户B将M伪造成M′，则用户B不能在第三方面前出示DSKA（M′）。这样就证明用户B伪造了报文。可以看出，实现数字签名也同时实现了对报文来源的鉴别。
2.3.5 RSA被破解的可能性
加密与破解是一对矛盾，再强的加密方法，总有被破解的一天。RSA算法是否安全呢？是否能被很轻松地破解呢？
RSA是被研究得最广泛的公钥算法，从提出到现在经历了各种攻击的考验，逐渐为人们接受，被普遍认为是目前最优秀的公钥方案之一。
RSA的缺点主要有以下两点：
产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。
分组长度太大，为保证安全性，N至少也要600比特二进制位以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。目前，SET协议中要求CA采用2048比特二进制位长的密钥，其他实体使用1024比特的密钥。
根据前面的运算过程可看出，RSA算法的安全性依赖于大数分解。公钥和私钥都是两个大素数（大于100个十进制位）的函数。据猜测，从一个密钥和密文推断出明文的难度等同于分解两个大素数的积。
RSA的安全性在于对于一个大数N，没有有效的方法能够将其分解，从而在已知（N，D）的情况下无法获得E；同样在已知（N，E）的情况下无法求得D。
在本节前面演示RSA加密算法时，P、Q的取值很小，使得N的值也很小，当得知（N，E）可以很容易地被破解计算出D，根本不能保障安全性！
这里选择小的P、Q是因为通过手工计算，太大的数没办法处理，而在实际应用中必须选择较大的P、Q，使得计算出的N足够大，这样不容易被破解。当然，随着计算机运算速度的提高，被破解的可能性也就变大了。现在小于1024位的N已经被证明是不安全的，因此不应使用小于1024位的RSA，最好是使用2048位的N。
例如，下面是一个1024位的N值及D和E值：
怎么样，看着这么长的N值头痛了吧（1024比特二进制位是256位16进制数）。这么长的数不要说用手工计算，就是用计算机来计算，也需要专门编写处理大整数运算的相关方法，才能进行处理。
当将N值取为2048比特二进制位时，则计算量将更大，从而就可保障密文的安全。当计算机速度更快，能较快破解密文时，还需要将N值取得更大。