数据加密实质上是对以符号为基础的数据进行移位和置换的变换算法。一般来说，有一个称为密钥的关键数据作为这个变化算法的参数。而解密过程就是这个算法的逆算法，同时也需要密钥参数。

假设p、q为两个很大的质数，p*q=n。如果已知n，求唯一的p或q是一件很困难的事情。需要知悉的是，如果p、q为两个很大的合数，则其积的因式分解会有多个，不是唯一的。利用两个质数的积的因式分解的唯一性及逆运算的复杂性，似乎在加密领域可以做点事情。

质数（prime number，也叫素数，在大于1的自然数中，除了1和它本身以外不再有其他因数）被利用在密码学上，将想要传递的信息在编码时加入质数，编码之后传送给收信人，任何人收到此信息后，若没有此收信人所拥有的密钥 ，则解密的过程中（实为寻找素质数的过程），将会因为找质数的过程（分解质因数）过久，使即使取得信息也会无意义。

1 对称加密算法：DES和AES

在传统的加密算法中，加密密钥与解密密钥是相同的，或者可以由其中一个推知另一个，称为对称密钥算法。这样的密钥必须秘密保管，只能为授权用户所知，授权用户既可以用该密钥加密信息，也可以用该密钥解密信息。DES(Data Encryption Standard数据加密标准)是对称加密算法中最具代表性的。DES可以对任意长度的数据加密，实际可用密钥长度56ibt。加密时首先将数据分为64bit的数据块，采用ECB、CBC、CFB等模式之一，每次将输入的64bit明文变换为64bit密文。最终，将所有输出数据块合并，实现数据加密。DES的保密性仅取决于对密钥的保密，而算法是公开的。DES内部的复杂结构是很难找到破译方法的根本原因。

在对称加密算法中，数据发信方将明文（原始数据）和加密密钥一起经过特殊加密算法处理后，使其变成复杂的加密密文发送出去。收信方收到密文后，若想解读原文，则需要使用加密用过的密钥及相同算法的逆算法对密文进行解密，才能使其恢复成可读明文。在对称加密算法中，使用的密钥只有一个，发收信双方都使用这个密钥对数据进行加密和解密，这就要求解密方事先必须知道加密密钥。

攻击 DES 的主要形式被称为蛮力的或彻底密钥搜索，即重复尝试各种密钥直到有一个符合为止。DES采用64位密钥技术，实际只有56位有效，8位用来校验的。譬如，有这样的一台PC机器，它能每秒计算一百万次，那么256位空间它要穷举的时间为2285年。所以这种算法还是比较安全的一种算法。

在应用方面，尽管DES在安全上是脆弱的，但由于快速DES芯片的大量生产，使得DES仍能暂时继续使用，为提高安全强度，通常使用独立密钥的三级DES。

AES是美国国家标准技术研究所NIST旨在取代DES的21世纪的加密标准。

AES的基本要求是，采用对称分组密码体制，密钥的长度最少支持为128、192、256，分组长度128位，算法应易于各种硬件和软件实现。1998年NIST开始AES第一轮分析、测试和征集，共产生了15个候选算法。1999年3月完成了第二轮AES2的分析、测试。2000年10月2日美国政府正式宣布选中比利时密码学家Joan Daemen 和 Vincent Rijmen 提出的一种密码算法RIJNDAEL作为AES。

2 RSA

多年来，许多人都认为DES并不是真的很安全。事实上，即使不采用智能的方法，随着快速、高度并行的处理器的出现，强制破解DES也是可能的。"公开密钥"加密方法使得DES以及类似的传统加密技术过时了。公开密钥加密方法中，加密算法和加密密钥都是公开的，任何人都可将明文转换成密文。但是相应的解密密钥是保密的（公开密钥方法包括两个密钥，分别用于加密和解密），而且无法从加密密钥推导出，因此，即使是加密者若未被授权也无法执行相应的解密。

本世纪七十年代，几位美国数学家提出一种编码方法，这种方法可以把通讯双方的约定公开，然而却无法破译密码，这种奇迹般的密码就与质数有关。

人们知道，任何一个自然数都可以分解为素数（两个或两个以上）的乘积，如果不计因数的次序，分解形式是唯一的。这叫做算术基本定理，欧几里得早已证明了的。可是将一个大整数分解却没有一个简单通行的办法，只能用较小的素数一个一个去试除，耗时极大。如果用电子计算机来分解一个100位的数字，所花的时间要以万年计。可是将两个100位的数字相乘，对计算机却十分容易。

公开密钥加密思想最初是由Diffie和Hellman提出的，最著名的是Rivest、Shamir以及Adleman提出的，通常称为RSA（以三个发明者的首位字母命名）的方法，该方法基于下面的两个事实：

I 已有确定一个数是不是质数的快速算法；

II 尚未找到确定一个合数的质因子的快速算法。

RSA方法的工作原理如下：

1) 任意选取两个不同的大质数p和q，计算乘积r=p*q；

2) 任意选取一个大整数e，e与(p-1)*(q-1)互质，整数e用做加密密钥。注意：e的选取是很容易的，例如，所有大于p和q的质数都可用。

3) 确定解密密钥d：

(d * e) modulo（p - 1）*（q - 1） = 1

根据e、p和q可以容易地计算出d。

4) 公开整数r和e，但是不公开d；

5) 将明文P (假设P是一个小于r的整数)加密为密文C，计算方法为：

C = P^e modulo r

6) 将密文C解密为明文P，计算方法为：

P = C^d modulo r

然而只根据r和e（不是p和q）要计算出d是不可能的。因此，任何人都可对明文进行加密，但只有授权用户（知道d）才可对密文解密。

3 简单实例说明RSA工作原理

下面举一简单的例子对上述过程进行说明，显然我们只能选取很小的数字。

例：选取p=3, q=5，则r=15，（p-1）*（q-1）=8。选取e=11（大于p和q的质数），通过（d*11）modulo(8) = 1。

计算出d =3。

假定明文为整数13。则密文C为

C = P^e modulo r

= 13^11 modulo 15

= 1,792,160,394,037 modulo 15

= 7

复原明文P为：

P = C^d modulo r

= 7^3 modulo 15

= 343 modulo 15

= 13

因为e和d互逆，公开密钥加密方法也允许采用这样的方式对加密信息进行"签名"，以便接收方能确定签名不是伪造的。假设A和B希望通过公开密钥加密方法进行数据传输，A和B分别公开加密算法和相应的密钥，但不公开解密算法和相应的密钥。A和B的加密算法分别是ECA和ECB，解密算法分别是DCA和DCB，ECA和DCA互逆，ECB和DCB互逆。若A要向B发送明文P，不是简单地发送ECB（P），而是先对P施以其解密算法DCA，再用加密算法ECB对结果加密后发送出去。

密文C为：

C = ECB（DCA（P））

B收到C后，先后施以其解密算法DCB和加密算法ECA，得到明文P：

ECA（DCB（C））

= ECA（DCB（ECB（DCA（P））））

= ECA（DCA（P）） /*DCB和ECB相互抵消*/

= P /*DCB和ECB相互抵消*/

这样B就确定报文确实是从A发出的，因为只有当加密过程利用了DCA算法，用ECA才能获得P，只有A才知道DCA算法，没有人，即使是B也不能伪造A的签名。

RSA提出后，三位发明家曾经公布了一条密码，悬赏100美元破译，他们预言，人们至少需要20000年，才能破译，即使计算机性能提高百倍，也需要200年。但只过了不到18年，这个密码就被人破译，意思是：“The magic words are squeamish ossifrage”。这个密码如此快的破解，是因为全世界二十多个国家的六百多位工作者自发联合起来，利用计算机网络，同时进行因式分解，并不断交流信息，汇总计算结果，用了不到一年的时间，就将129位的N分解成64位和65位的两个素数的积。计算机网络将分解效率提高了近万倍，这是发明者当初没有预想到的。但是，如果提高位数到200或300位，工作量将会大的不可思议，即使计算机技术有重大突破，破译也几乎不可能。

RSA加密使用了"一对"密钥。分别是公钥和私钥，使用公钥加密的数据，利用私钥进行解密。使用私钥加密的数据，利用公钥进行解密。这个公钥和私钥其实就是一组数字！其二进制位长度可以是1024位或者2048位。长度越长其加密强度越大，目前为止公之于众的能破解的最大长度为768位密钥，只要高于768位，相对就比较安全。所以目前为止，这种加密算法一直被广泛使用。

4 关于质数的猜想

大约在公元前300年, 欧几里得 就证明了素数有无穷多个。设2,3,…, p 是不大于 p 的所有素数， q =2*3*…* p +1。容易看出 q 不是2，3，…， p 的倍数。由于 q 的最小正除数一定是素数，因此，或者 q 本身是一个素数，或者 q 可被 p 与 q 之间的某两个素数所整除[比如：2*3*5*7*11*13+1=30031=59*509]。所以必有大于 p 的素数存在，由此即知素数有无穷多个。

素数在自然数中占有极其重要的地位，但是它的变化非常不规则。人们至今没有找到，大概也不可能找到一个可以表示全体素数的有用公式。最初的研究方法，是通过观察素数表来发现素数分布的性质。现有的较完善的素数表是D.B.扎盖尔于1977年编制的，列出了不大于50000000的所有素数。从素数表可以看出：在1到100中间有25个素数,在1到1000中间有168个素数,在1000到2000中间有135个素数, 在2000到3000中间有127个素数，在3000到4000中间有120个素数,在4000到5000中间有119个素数,在5000到10000中间有560个素数。由此可看出，素数的分布越往上越稀少。

4.1 黎曼猜想

黎曼猜想是关于黎曼ζ函数ζ(s)的零点分布的猜想，由波恩哈德·黎曼1859年提出的，这位数学家于1826年出生在当时属于汉诺威王国的名叫布列斯伦茨的小镇。1859年，黎曼被选为了柏林科学院的通信院士。作为对这一崇高荣誉的回报，他向柏林科学院提交了一篇题为“论小于给定数值的素数个数”的论文，在这篇文章里，黎曼阐述了质数的精确分布规律。

素数分布是以黎曼公式为中心，高斯公式为上限的正态分布，这在现在来说是经验公式，待数学家给出严格证明之后才能成为数学定理。

4.2 哥德巴赫猜想

是否每个大于2的偶数都可写成两个素数之和？

1742年6月7日，哥德巴赫写信给欧拉，提出了著名的哥德巴赫猜想：随便取某一个奇数，比如77，可以把它写成三个素数之和，即77=53+17+7；再任取一个奇数，比如461，可以表示成461=449+7+5，也是三个素数之和，461还可以写成257+199+5，仍然是三个素数之和。例子多了，即发现“任何大于5的奇数都是三个素数之和。”

1742年6月30日欧拉给哥德巴赫回信。这个命题看来是正确的，但是他也给不出严格的证明。同时欧拉又提出了另一个命题：任何一个大于2的偶数都是两个素数之和。但是这个命题他也没能给予证明。

－End－