2.3 现代密码技术

加密技术经过几十年的发展已经趋于成熟，对于网络信息的加密技术也是多种多样，但从应用方面来讲大体分为两类：一类是对称密码技术，另一类是非对称密码技术。

2.3.1 对称密码技术

对称密钥密码系统使用的加密密钥和解密密钥是相同的，或者可以简单地相互推导出来。典型的对称密钥密码系统是数据加密标准（Data Encryption Standard，DES），此外还有国际数据加密算法（IDEA，International Data Encryption Algorithm）、高级加密标准（AES，Advanced Encryption Standard）等。

1．数据加密标准（DES）

DES加密算法的数据流程如图2-5所示。该算法输入的是64bit的明文，在64bit的密钥控制下，通过初始换位IP变成T₀=IP（T），再对T₀经过16层的加密变换，最后通过逆初始变换（也称最后变换）得到64bit的密文。密文的每一位都是由明文的每一位和密钥的每一位联合确定的。DES的加密过程可分为加密处理、加密变换及子密钥生成几个部分，如图2-6所示。下面，分别说明加密处理、加密变换、子密钥生成和解密处理几个过程。

（1）加密处理

1）初始换位：加密处理首先要对64bit的明文按照表2-3所示的初始换位表IP进行换位。

表中的数值表示输入bit被置换后的新bit位置。例如，输入的第58bit，在输出时被置换到第1bit的位置；输入的第2bit，在输出时被置换到第8bit的位置；输入的第1bit，在输出时被置换到第40bit的位置；输入的第7bit，在输出时被置换到第64bit的位置上。

2）加密处理：上述换位处理的输出，中间要经过16层复杂的加密变换。经过初始换位的64bit的输出变为下一步的输入，此64bit分成左、右两个32bit，左为L₀，右为R₀，从L₀和R₀到L₁₆和R₁₆共进行了如图2-7所示的16层加密变换。变换之后，若经过第n层处理后的左、右32bit分别为L_n和R_n，则L_n和R_n可作如下的定义：

L_n=R_n-1

R_n=L_n-1⊕f（R_n-1，K_n）

这里，K_n是向第n层输入的48bit的密钥；L_n-1和R_n-1分别是第n-1层的输出；f是以R_n-1和K_n为变量的输出32bit的函数。

3）最后换位：进行16次加密变换之后，将L₁₆和R₁₆合成64bit数据，再按照表2-4所示的最后换位表IP^-1进行换位，得到64bit的密文，这就是DES加密的结果。

由图2-8可以看出，表2-3和表2-4是完全的逆变换。

（2）加密变换

计算f（R，K）的方式如图2-9所示。在DES算法中，其他部分都是线性的，而这个f（R，K）变换是非线性的，因此可以产生强度很高的密码。

32bit的R首先按照表2-5所示的扩展型换位表E进行换位，同时把一部分bit重复使用，便可扩大成48bit，这样得到48bit的R′。按照从头算起，每4bit再加上后面的2bit，便形成每6bit一组的8个分组，即

R ₃₂ R ₁ R ₂ R ₃ R ₄ R ₅，R₄R₅R₆R₇R₈R₉，……，…R₂₈R₂₉，R₂₈R₂₉R₃₀R₃₁R₃₂R₁

这48bit的R′和48bit的密钥K进行异或运算，并分成每组6bit的8个分组，输入到S₁～S₈的8个S盒中去，S₁～S₈称为选择函数（Selection Function）。这些S盒输入是6bit，输出是4bit。

如表2-6所示，此表列举的是一个S盒中S₁的代替表。一个S盒中备有4种代替表（行号为0，1，2，3），究竟采用哪一种代替表，要通过输入的6bit的开头和末尾两个bit选定，然后按选定的代替表将输入的6bit的中间4bit进行代替。

下面举一个例子予以说明。当向S₁输入一个二进制状态011011时，因开头的0和末尾的1合起来为01（即十进制数1），所以选中了编号为1的代替表；又因中间4个bit状态为1101（十进制数13），表示选第13列。第1行第13列所指示的值为5，即输出状态为0101，这4个bit就是经过代替之后的状态。如表2-7所示，此表给出了S₁～S₈的S盒代替表，其中的每一行代表一种代替表。接着，从8个S盒输出的32bit，按照表2-8所示的单纯换位表P进行换位，这样便实现了f（R，K）的变换。

（3）子密钥生成

下面说明子密钥K₁～K₁₆的16层子密钥的生成过程。在64bit的密钥里包含了8位的奇偶校验位，所以实际密钥长度是56bit，而每层要生成48bit的子密钥。

输入64bit的密钥，首先通过压缩型换位PC-1（Permuted Choice 1）去掉奇偶校验位，再将不含奇偶校验位的56bit进行输出，而每层要分成两部分，上部分的28bit为C₀，下部分的28bit为D₀，如表2-9所示。C₀和D₀依次进行循环左移位，这样就生成了C₁和D₁，然后将C₁和D₁合成56位，再通过压缩型换位PC-2（如表2-10所示），输出的结果即为48位的子密钥K₁。再将C₁和D₁进行循环左移位和PC-2的转换，即得子密钥K₂……依此类推，就可以得出16层的子密钥K₁，K₂，…，K₁₆。16层子密钥的生成过程如图2-6右半部所示。值得注意的是，在产生16层子密钥的过程中，L₁、L₂、L₉、L₁₆是循环左移1位的变换，而其余的L_n都是循环左移2位的变换。16层变换中的循环左移位次数如表2-11所示。

（4）解密处理

从密文到明文的解密处理可采用与加密算法完全相同的算法。不过，解密要用加密的逆变换，也就是把上述的最后换位表IP^-1和初始换位表IP完全倒过来变换。另外，在16层的变换处理中，由于R_n-1=L_n和L_n-1=R_n⊕f（L_n，K_n），因此要求出R_n-1和L_n-1，只要知道L_n、R_n和K_n，并使用同一个函数f所表示的变换便可以实现，从而在各层变换中，如果采用与加密时相同的K_n来处理，就能实现解密。具体地说，输入DES算法中的密文，经过初始换位可得到L₁₆和R₁₆，第1层处理时的密钥是逆序的，用K₁₆可以求出L₁₅和R₁₅，其中f（R，K）即使不可逆也没有关系；然后用K₁₅进行变换求出L₁₄和R₁₄。依此类推，经过16层的变换即可得到L₀和R₀。

（5）DES加密的评价

DES加密法的保密性到底如何？早在DES被正式公布为数据加密标准之前，就展开了热烈的讨论。由于目前尚无一个评价加密系统性能的统一标准和严格的理论，因此人们只能从一个密码系统抵抗现有解密手段的能力来评价它的好坏。

自1975年以来，美国的许多机构、公司和学者，包括美国国家安全局（NSA）、标准局、IBM公司、DELL实验室和一大批著名的密码学专家都对DES进行了大量的研究，但迄今尚未找到破译DES的一种行之有效的方法。因此，认为DES具有良好的保密性能和抗分析破译性能，并已广泛地应用于金融业。不仅在美国，而且日本和西欧多国也使用DES。

20世纪80年代中期，人们看到DES算法迭代次数少，密钥长度短，其代替函数Si中可能有不安全因素，因而曾经有过不少批评，有人甚至还想取消它，但是DES以它顽强的生命力至今仍占据着加密技术的重要地位。

DES的研究和应用还在不断发展，出现了一些增强DES的设想，如增长密钥长度和改进代替函数Si等，对DES的分析和研究还在继续深入。虽然1984年美国国家安全局决定研制新的数据加密标准CCEP，但从发展趋势上看，CCEP是按封闭的原则管理的，应用范围很有限，它不再具有技术上的开放性和使用上的灵活性，因此受到金融界的强烈反对。由于反对的呼声很高，美国政府不得不于1987年初废除了1984年签署的用CCEP取代DES加密标准的命令，所以它很难取代DES的广泛应用。

然而，1997年，在一项“DES挑战赛”的活动中，志愿者4次分别用4个月、41天、56个小时和22个小时破解了RSA数据安全公司用56bit DES算法加密的密文。这说明，DES加密算法在计算机运算速度提升后被认为是不安全的。另外，有一些分析报告也提出了DES算法理论上的弱点，如不能对抗差分和线性密码分析等。在2001年，DES作为一个标准已经被取代。DES也不再作为美国国家标准科技协会（前美国国家标准局）的一个标准。不过，DES作为密码学史上影响最大、应用最广的数据加密算法，其成功是当之无愧的。

（6）二重DES

为了提高DES的安全性，并利用实现DES的现有软硬件，可将DES算法在多密钥下多重使用。如图2-10所示为二重DES。

二重DES是多重使用DES时最简单的形式，其中明文为P，两个加密密钥为K₁和K₂，密文为，解密时，以相反顺序使用两个密钥：。因此，二重DES所用密钥长度为112bit，强度大增。然而，如果对任意两个密钥K₁和K₂，能够找出另一密钥K₃，使得。那么，二重DES以及多重DES都没有意义，因为它们与56bit密钥的单重DES等价。

但上式对DES并不成立。将DES加密过程64bit分组到64bit分组的映射看作一个置换，如果考虑2⁶⁴个所有可能的输入分组，则密钥给定后，DES的加密将把每个输入分组映射到一个唯一的输出分组。否则，如果有两个输入分组被映射到同一分组，则解密过程就无法实施。对2⁶⁴个输入分组，总映射个数为（2⁶⁴）！＞（10²⁰）。

另一方面，对每个不同的密钥，DES都定义了一个映射，总映射数为2⁵⁶＜10¹⁷。

因此，可假定用两个不同的密钥两次使用DES，可得一个新映射，而且这一新映射不出现在单重DES定义的映射中。这一假定已于1992年被证明。所以使用二重DES产生的映射不会等价于单重DES加密。但对二重DES有以下一种称为“中途相遇攻击”的攻击方案，这种攻击不依赖于DES的任何特性，因而可用于攻击任何分组密码。其基本思想如下：

如果有，那么（参见图2-10）。

如果已知一个明—密文对（P，C），可实施以下攻击：首先，用2⁵⁶个所有可能的K₁对P加密，将加密结果存入一个表中，并对该表按X排序，然后用2⁵⁶个所有可能的K₂对C解密，在上述表中查找与C解密结果匹配的项，如果找到，则记下相应的K₁和K₂。最后再用一新的明—密文对（P′，C′）检验上面找到的K₁和K₂，用K₁和K₂对P′两次加密，若结果等于C′，就可确定K₁和K₂是所要找的密钥。

对已知的明文P，二重DES能产生2⁶⁴个可能的密文。而可能的密钥个数为2¹¹²，所以平均来说，对一个已知的明文，有2¹¹²/2⁶⁴=2⁴⁸个密钥可产生已知的密文。而再经过另外一对明—密文的检验，误报率将下降到2^48-64=2^-16。所以在实施“中途相遇攻击”时，如果已知两对明—密文，则找到正确密钥的概率为1-2^-16。

（7）两个密钥的三重DES

抵抗“中途相遇攻击”的一种方法是使用三个不同的密钥做三次加密，从而可使已知明文攻击的代价增加到2¹¹²。然而又会使密钥长度增加到56×3=168bit，因而过于笨重。一种实用的方法是仅使用两个密钥做三次加密，实现方式为加密—解密—加密，简记为EDE（Encrypt-Decrypt-Encrypt），如图2-11所示。

第二步解密的目的仅在于使得用户可对一重DES加密的数据解密。此方案已在密钥管理标准ANS X.917和ISO 8732中采用。

（8）三个密钥的三重DES

三个密钥的三重DES密钥长度为168bit，加密方式为，令K₃=K₂或K₁=K₂，则变为一重DES。

三个密钥的三重DES已在互联网的许多应用（如PGP和S/MIME）中采用。

2．国际数据加密算法（IDEA）

国际数据加密算法IDEA是瑞士的学者提出的。1990年XueJia Lai和Massey开发出IDEA加密算法雏形，称为PES，即“建议的加密标准”。第二年，根据有关专家对这一密码算法的分析结果，设计者对该算法进行了强化并称之为IPES，即“改进的建议加密标准”。该算法于1992年更名为IDEA，即“国际加密标准”。这种算法是在DES算法的基础上发展出来的，类似于三重DES。发展IDEA也是因为感到DES具有密钥太短等缺点。

IDEA算法的密钥长度为128位，针对64位的数据进行加密或解密操作。XueJia Lai已证明IDEA算法在其8轮迭代的第4圈之后便不受差分密码分析的影响了。假定穷举法攻击有效的话，那么即使设计一种每秒钟可以试验10亿个密钥的专用芯片，并将10亿片这样的芯片用于此项工作，仍需10²³年才能解决问题；另一方面，若用10²⁴片这样的芯片，有可能在一天内找到密钥，不过人们还无法找到足够的硅原子来制造这样一台机器。目前，尚无公开发表的试图对IDEA进行密码分析的文章。因此，就现在来看，应当说IDEA是非常安全的。

IDEA有大量的弱密钥，这些弱密钥是否会威胁它的安全性还是一个谜。IDEA密码能够抵抗差分分析和线性分析。设计者Lai认为IDEA不是一个群，但目前仍未得到证实。

类似于DES，IDEA算法也是一种数据块加密算法，它设计了一系列加密轮次，每轮加密都使用从完整的加密密钥中生成的一个子密钥。与DES的不同处在于，它采用软件实现和采用硬件实现同样快速。

由于IDEA是在美国之外提出并发展起来的，避开了美国法律上对加密技术的诸多限制，因此，有关IDEA算法和实现技术的书籍都可以自由出版和交流，可极大地促进IDEA的发展和完善。但由于该算法出现的时间不长，针对它的攻击也还不多，还未经过较长时间的考验。因此，尚不能判断出它的优势和缺陷。

3．高级加密标准（AES）

数据加密标准（DES）作为20世纪70年代的加密标准，其加密强度越来越不能满足人们的要求。DES的密钥长度只有56bit，随着计算能力的不断提高，利用穷搜索的方法攻破DES是完全可能的，特别是在政府或者其他组织的支持下使用专门设计的硬件来攻击DES已经是轻而易举的事情。在这种情况下，美国国家标准技术局（NIST）在1997年开始倡导制定高级加密标准（AES）替代DES，以满足21世纪的信息加密需求。经过几年的招标、筛选，NIST于2000年底最终确定了AES（RIJNDAEL）标准。AES是由比利时密码专家Joan Daemen和Vincent Rijmen共同设计的。下面简单地介绍AES。

AES的信息块长度和加密密钥长度都是可变的，它们都可以是128bit、192bit和256bit。为了方便数据的计算和算法的描述，首先把信息块做如下的处理。以192bit的信息块为例，假设信息块是m₀m₁…m₁₉₁，写成字节形式就是a₀₀a₀₁…a₀₅a₁₀a₁₁…a₁₅…a₃₀a₃₁…a₃₅，或者写成字的形式就是w₀w₁…w₅，如图2-12所示。

也可以对加密密钥做类似的处理。设N_b为信息块经过上述处理后得到的字的个数，N_k为加密密钥经过上述处理后得到的字的个数。那么根据信息块的长度，N_b=4，6，8，根据加密密钥的长度，N_k=4，6，8，加密的轮数N_r如表2-12所示，由N_b和N_k控制。

整个算法包括加密过程与轮密钥生成两个独立的部分。

（1）加密过程

设信息块是M，轮密钥分别是K₀，K₁，…，，加密过程如图2-13所示。解密过程把加密过程完全反过来即可。

1）ByteSub函数。

把每个8bit的字节看成有限域GF（2⁸）中的一个元素，那么函数ByteSub是作用在每个字节上的非线性变换，它定义为：ByteSub：GF（2⁸）→GF（2⁸）

如图2-14所示，描述了信息块长度是192bit时，函数ByteSub的作用情况。

2）ShiftRow函数。

把信息块记为4行、N_b列的矩阵形式，函数ShiftRow就是对每行实行不同的左移位，每行的左移位数C₁、C₂、C₃分别由N_b决定，见表2-13。

函数ShiftRow的作用如图2-15所示。

3）MixColumn函数。

MixColumn函数是GF（2⁸）⁴上的一个线性变换，变换矩阵C定义为：

其中的运算均为在GF（2⁸）中进行。如图2-16所示，描述了信息块长度是192bit时，MixColumn函数的作用情况。此处矩阵C中的元素理解为两个4bit长的二进制数的串接，比如02理解为0000 0010。

（2）轮密钥生成

轮密钥的生成过程包括加密密钥的扩张和轮密钥的选取两个部分。

1）加密密钥的扩张。

假设信息块的长度是N_b个32bit字，由于整个加密过程需要N_r+1个轮密钥，每个轮密钥的长度是N_b个32bit字，因此密钥的扩张过程需要产生N_b（N_r+1）个32bit字，记为w₀，w₁，…，。加密密钥的扩张根据密钥长度N_k的不同，有两种不同的扩张方式。假设加密密钥为wk₀wk₁…，令w₀=wk₀，。

当N_r≤6时，对于N_k≤i＜N_b（N_r+1），如图2-17a所示。

当N_r＞6时，对于N_k≤i＜N_b（N_r+1），如图2-17b所示。

其中，RotByte把（a，b，c，d）变为（b，c，d，a），a，b，c，d是8bit。

Rcont[i]=（RC[i]，00，00，00）；RC[1]=1，RC[i]=xRC[i-1]=x^i-1，即RC[i]表示有限域GF（2⁸）中值为x^i-1的元素。Rcont[i/N_k]为轮常数，其值与N_k无关。

2）轮密钥的选取。

加密密钥经过扩张产生了N_b（N_r+1）个32bit字，把它们等分成N_r+l块，每块包含N_b个32bit字，那么第一个轮密钥就是第一个块，第二个轮密钥就是第二个块，依此类推得到所有的轮密钥。

（3）关于AES的讨论

AES的原型是Square算法，它的设计策略是宽轨迹策略（Wide Trail Strategy）。这种策略是针对差分分析和线性分析提出来的，它是一个分组迭代密码，具有可变的分组长度和密钥长度。2000年10月，AES选择Rijndael加密算法作为自己的算法，Rijndael具备了安全、性能好、效率高、易实现和灵活等优点，Rijndael对内存的需求非常低，也使它很适合用于受限制的环境中，Rijndael操作简单，并可抵御强大和实时的攻击，此外，它还有许多未被特别强调的防御性。

与其他分组码相比，AES具有如下特点：①可变的密钥长度；②混合的运算方式；③数据相关的圈数；④密钥相关的圈数；⑤密钥相关的S盒；⑥长密钥调度算法；⑦可变长明文/密文块长度；⑧可变圈数；⑨每圈操作作用于全部数据。

2.3.2 非对称密码技术

20世纪70年代，一个数学上的突破震惊了世界密码学家，这就是公钥加密技术。与传统的加密方法不同，它使用两把密钥：一把公开密钥和一把秘密密钥。前者用于加密，后者用于解密，它也称为“非对称式”加密方法。公钥加密技术解决了对称加密方法的根本性缺陷，极大地简化了密钥分发过程。它若与对称加密方法结合，可以进一步增强对称加密方法的可靠性。此外，还可能利用公钥加密技术来进行数字签名。

1．公钥加密技术原理概述

1976年Diffie和Hellman在其划时代的文献New Directions in Cryptography（密码学新方向）中提出公钥加密的概念，公钥加密是基于单向陷门（trap door）函数来实现的，单向陷门函数是指满足下列条件的函数f（x）：

1）给定x，计算y=f（x）是容易的。

2）给定y，计算x=f^-1（y）是困难的。

3）存在δ，已知δ时，对给定的任何y，若相应的x存在，则计算x=f^-1（y）是容易的。

仅满足第1）条、第2）条的称为单向函数，第3）条称为陷门性，δ称为陷门信息。当用陷门函数f（x）作为加密函数时可将f（x）公开，这相当于公钥。f（x）函数的设计者将δ保密，用作解密密钥，这相当于私钥。由于加密函数是公开的，任何人都可以将信息x加密成y=f（x），然后送给函数的设计者，当然可以通过不安全信道传送，由于设计者拥有δ（私钥），他可以容易地解出x=f^-1（y）。单向陷门函数的第2）条性质表明窃听者由截获的密文y=f（x）推测x是不可行的。

目前公钥密码系统单向陷门函数的设计主要依赖下面3个数学难题：

1）背包问题。

2）大整数因子分解问题。

3）离散对数问题。

第1类公钥系统的安全性依赖于背包问题的NP完全性。背包问题可以这样描述：已知一容积为C的背包及体积分别为k₁，k₂，…，k_n的n个物品，若从这些物品中选出若干个正好装满这个背包，那么究竟选哪些物品？即求m_i（1≤i≤n），使得C=k₁m₁+k₂m₂+…+k_nm_n，其中k_i和C都是正整数，m_i取0或1。背包问题是著名的NP完全问题，至今没有很好的求解方法。穷举搜索的复杂度为O（2ⁿ）。第一个背包公钥算法是由Merkle和Hellman于1978年提出的MH算法。选取正整数k₁，k₂，…，k_n作为密钥，设明文分组位串为M=m₁m₂…m_n，则加密后的密文为C=k₁m₁+k₂m₂+…+k_nm_n。那么如何进行解密呢？奥妙在于存在一类特殊的背包问题，其物品体积序列k₁，k₂，…，k_n的每一项都大于它之前的所有项之和，这就是著名的超递增背包问题，超递增背包问题的复杂度为O（n）（读者可想一想为什么）。Merkle和Hellman设计了一种可以将超递增背包问题转换为同解非超递增背包问题的方法。MH算法用超递增背包问题的体积序列作私钥，而用同解的非超递增背包问题的体积序列作公钥，这样就很容易用私钥进行解密了。MH算法后来被证明是不安全的，但这种算法首次将NP完全问题用于公钥密码学，在密码学史上具有开创意义。

第2类公钥系统是由麻省理工学院的三位科学家Ron L.Rivest，Adi Shamir和Leonard M.Adleman于1978年提出的，简称为RSA系统。它的安全性是基于大整数因子分解的困难性，其公钥和私钥是一对大素数（100到200位的十进制数或更大）的函数。从一个公钥和密文中恢复出明文的难度等价于分解两个大素数之积的难度，而大整数因子分解问题是数学上的著名难题，因而可以确保RSA算法的安全性。RSA系统是公钥系统的最具有典型意义的方法，自提出以来就一直是人们研究的焦点，经受住了多年来许多资深密码学家的密码分析，说明该算法是有相当的可信度的。本节将重点介绍RSA算法。

第3类公钥系统的安全性依赖于离散对数的计算困难性。离散对数问题可细分为两类：一类为有限域上的离散对数问题，一类为椭圆曲线上的离散对数问题。下面举一个简单的有限域上离散对数的例子，设p为素数，g小于p，如果对每个b从1到p-1都存在x，使得g^x≡bmodp，则称g为模p的原根（primitive root）。例如5是模7的原根，这是因为：

5¹≡5（mod 7）

5²=5×5≡4（mod 7）

5³=4×5≡6（mod 7）

5⁴=6×5≡2（mod 7）

5⁵=2×5≡3（mod 7）

5⁶=3×5≡1（mod 7）

如果g为模p的原根，则对任意y，总是可以找出y=g^xmodp的解，x称为y模p的离散对数解（形如g^xmodp的运算称为模乘运算）。当p很小时，已知y和p可以用观察法求出x，但是当p为很大的随机素数时，就很难计算了。所以，可以认为y=g^xmodp是一个单向函数。

著名的椭圆曲线加密算法ECC（Elliptic Curve Cryptography）的安全性就是依赖于定义在椭圆曲线点上的离散对数问题的难解性。ECC算法由Neal Koblit和Victor Miller于1985年首先提出，从那时起ECC的安全性和实现效率就被众多的数学家和密码学家所广泛研究。所得的结果表明，较之RSA算法，ECC具有密钥长度短，加解密速度快，对计算环境要求低，在需要通信时，对带宽要求低等特点。近年来，ECC被广泛应用于商用密码领域，这可由ECC被许多著名的国际标准组织所采纳佐证，如ANSI、IEEE、ISO、NIST。此外，基于离散对数的公钥系统还有Massey-Omura公钥系统和ElGamal公钥系统等。

2．RSA加密算法

RSA算法因其创始人Ronald L.Rivest、Adi Shamir和Leonard M.Adleman而得名。RSA的基础是数论的欧拉定理，它的安全性依赖于大数的因数。

RSA算法研制的最初理念与目标是努力使互联网安全可靠，旨在解决DES算法秘密密钥的利用公开信道传输分发不安全的难题。而实际结果，RSA不但很好地解决了这个难题，还可利用它来完成对电文的数字签名以对抗对电文的否认与抵赖，同时还可以利用数字签名较容易地发现攻击者对电文的非法篡改，以保护数据信息的完整性。

RSA是第一个比较完善的公开密钥算法，它既能用于加密，也能用于数字签名。在已公开的公钥算法中，RSA是最容易理解和实现的。

（1）RSA算法的描述

RSA算法的实现步骤如下（B为实现者）：

1）B寻找出两个大素数p和q。

2）B计算出n=pq和f（n）=（p-1）（q-1）。

3）B选择一个随机数e（0＜e＜f（n）），满足（e，f（n））=1。

4）B使用辗转相除法计算d=e^-1（modf（n））。

5）B在目录中公开n和e作为他的公开密钥，保密p、q和d。

密码分析者攻击RSA体制的关键在于如何分解n。若分解成功使n=pq，则可以算出f（n）=（p-1）（q-1），然后由公开的e解出秘密的d。

加密时，对每一明文分组如下计算：

解密时，取每一密文分组c并计算：

RSA算法主要用于数据加密和数字签名。RSA算法用于数字签名时，公钥和私钥的角色变换即可。即将消息用d加密签名，用e验证签名。

（2）RSA算法实例

若B选择了p=101和q=113，那么，n=11413，f（n）=100×112=11200；再用辗转相除法（Euclidean算法）来求得e，使（e，f（n）=1）。假设B选择了e=3533，那么用辗转相除法将求得：d=e^-1（mod 11200），于是B的解密密钥d=6597。

B公开n=11413和e=3533，现假设A想发送明文9726给B，他计算：9726³⁵³³（mod 11413）=5761，且在一个信道上发送密文5761。当B接收到密文5761时，他用他的秘密解密指数（私钥）d=6597进行解密：

5761⁶⁵⁹⁷（mod 11413）=9726

（3）关于RSA算法的讨论

RSA的发明者Rivest、Shamir和Adleman建议取p和q为100位以上的十进制数，这样，n为200位的十进制数。按每秒10⁹次运算的高速计算机也要计算106年。

三种可能攻击RSA算法的方法如下。

1）强行攻击。这包含对所有的私有密钥都进行尝试。

2）数学攻击。有几种方法，实际上都等效于对两个素数的乘积的因子分解。

3）定时攻击。这依赖于解密算法的运行时间。

对RSA强行攻击的防范方式与其他秘密系统采用的方法相同，即采用一个大的密钥，因而e和d的比特数越多越好。然而因为在密钥产生和加密解密中包含的计算很复杂，密钥越大则系统运行越慢。

基于安全性考虑，一般在应用RSA时，必须做到以下几点。

1）绝对不要对陌生人提交的随机消息进行签名。

2）不要在一组用户间共享n。

3）加密之前要用随机值填充消息，以确保m和n的大小一样。

4）目前，129位十进制数字的模数是能够分解的临界数，因此，n应该大于这个数。

RSA技术既可用于加密通信，又能用于数字签名和认证。由于RSA的速度大大逊于DES等分组算法，因此RSA多用于加密会话密钥、数字签名和认证。RSA以其算法的简单性和高度的抗攻击性在实际通信中得到了广泛的应用。许多操作平台（如Windows、Sun和Novell等）都应用了RSA算法。另外，几乎所有的网络安全通信协议（如SSL和IPsec等）也都应用了RSA算法。ISO几乎已指定RSA用作数字签名标准。在ISO 9796中，RSA已成为其信息附件。法国银行界和澳大利亚银行界已使RSA标准化，ANSI银行标准的草案也利用了RSA。许多公司都采用了RSA安全公司的PKCS。RSA在目前和可预见的未来若干年内，在信息安全领域的地位是不可替代的，在没有良好的分解大数因子的方法以及不能证明RSA的不安全性的时候，RSA的应用领域会越来越广泛。但是一旦分解大数因子不再困难，那么，RSA的时代也会成为历史。如今只有短的RSA钥匙才可能被强力方式解破。迄今为止，世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长，用RSA加密的信息实际上是不能被解破的。但在分布式计算和量子计算机理论日趋成熟的今天，RSA加密安全性受到了挑战。

针对RSA最流行的攻击一般是基于大数因数分解。1999年，RSA-155（512bits）被成功分解，花了五个月时间（约8000 MIPS年）和224 CPU hours，在一台有3.2 GB中央内存的Cray C916计算机上完成。2002年，RSA-158也被成功因数分解。2009年12月12日，编号为RSA-768（768bits，232 digits）数也被成功分解。2013年2月15日，《纽约时报》报道，欧美数学家和密码学家偶然发现，被全世界广泛应用的公钥加密算法RSA存在漏洞。他们发现，在700万个实验样本中有2.7万个公钥并不是按理论随机产生的。也就是说，或许有人可以找出产生公钥的秘密质数。该研究项目是由美国独立密码学家James P.Hughes和荷兰数学家Arjen K.Lenstra牵头的。他们的报告称：“我们发现绝大多数公钥都是按理论产生的，但是每一千个公钥中会有两个存在安全隐患。为防止有人利用该漏洞，有问题的公钥已从公众访问的数据库中移除。为确保系统的安全性，网站需要在终端做出改变。”

3．Rabin加密算法

Rabin方案的安全性基于求合数的模平方根的难度。这个问题等价于因子分解。下面是该方案的描述。

（1）Rabin加密方案

首先选取两个质数p和q，两个质数都同余3模4。将这两个质数作为私人密钥，n=pq作为公开密钥。

加密一个信息M（M必须小于n）时，只需计算：

C=M²modn

解密信息一样容易，但稍微麻烦一些。由于接收者知道p和q，故可以用中国剩余定理解两个同余式。计算：

m ₁=C^（p+1）/4modp

m ₂=（p-C^（p+1）/4）modp

m ₃=C^（q+1）/4modq

m ₄=（q-C^（q+1）/4）modq

然后选择整数a=q（q^-1modp）和整数b=p（p^-1modq）。四个可能的等式为：

M ₁=（am₁+bm₃）modn

M ₂=（am₁+bm₄）modn

M ₃=（am₂+bm₃）modn

M ₄=（am₂+bm₄）modn

这四个结果M₁、M₂、M₃和M₄中之一等于M。如果信息是英语文本，很容易选择正确的M_i。另一方面，如果信息是一个随机位流（比如，密钥产生或数字签名），就没有办法决定哪一个M_i是正确的。解决这一问题的方法是在信息加密前加入一个已知的标题。

（2）Williams加密方案

Hugh Williams重新定义了Rabin方案以消除其缺陷。在他的方案中，p和q这样选取：

p≡3mod 8

q≡7mod 8

且

N=pq

还有一个小整数S，满足J（S，N）=-1（J是雅可比符号）。N和S公开。私人密钥k满足：

k=1/2×（1/4×（p-1）×（q-1）+1）

为了加密信息M，计算C₁使之满足。然后，计算modN。类似于Rabin方案，C=M′²modN，C₂=M′mod 2。最后的密文是三重组：（C，C₁，C₂）。

解密C时，接收者利用：

C^k≡±M″（modN）

计算M″。M″的符号由C₂给出。最后：

Williams后来进一步改进了这个方案：将信息平方代之以立方。大质数必须同余1模3，否则公开密钥和私人密钥相同。更好的是，对每个加密仅有唯一的解密。

Rabin和Williams算法在证明其安全性取决于大数因子分解上较RSA算法有优势。然而，它们对选择密文攻击是不安全的。如果你打算在攻击者能攻击的地方（例如，在数字签名算法中，攻击者选择签名的信息的地方）使用这些算法，要保证在签名前使用单向散列函数。Rabin提出了另一种抵抗这种攻击的方法：在每条信息散列运算和签名前添加一个不同的随机串。不幸的是，一旦你将单向散列函数添加到系统中，其安全性将不再依赖于因子分解，尽管添加的散列值在实际意义上对系统没有任何削弱。

4．EIGamal加密算法

EIGamal算法既可用于数字签名，又可用于加密，其安全性依赖于计算有限域上离散对数这一难题。

（1）密钥对产生方法

密钥对产生办法如下。

1）选择一个素数p，两个随机数g和x，要求g和x都小于p。

2）计算y=g^xmodp，则其公钥为y、g和p；私钥是x。g和p可由一组用户共享。

（2）EIGamal用于加密

假定被加密信息为M，首先选择一个随机数k，只要k与p-1互质，然后计算：

a=g^kmodp，b=y^kMmodp

（a，b）为密文对，密文是明文的两倍长。解密时计算：M=b/a^x（modp）

因为a^x≡g^kxmodp以及b/a^x≡y^kM/a^x≡g^xkM/g^xk≡Mmodp都成立（如表2-14所示），除了y是密钥的一部分以及加密是和y^k相乘得来。

（3）EIGamal用于数字签名

EIGamal主要用于数字签名。假定被签信息为M，首先选择一个随机数k，k与p-1互质，然后计算：a=g^kmodp，再用扩展Euclidean算法对下面方程求解b：

M=（xa+kb）mod（p-1）

签名就是（a，b）。随机数k必须保密。

要验证签名时，只要验证下式：

y^aa^bmodp=g^Mmodp

同时一定要检验是否满足1≤a＜p，否则签名容易伪造。

每个EIGamal签名或加密都需要一个新的k值，该值必须随机选取。表2-15总结了这种方法。

例如，选择p=11和g=2，私人密钥x=8，计算：

y=g^x（modp）=2⁸（mod 11）=3

公开密钥是y=3，g=2和p=11

为鉴别M=5，首先选择随机数k=9，验证gcd（9，10）=1，计算：

a=g^k（modp）=2⁹（mod 11）=6

利用Euclidean算法求b：

M=（xa+kb）mod（p-1）

5=（8×6+9×b）mod 10

解是b=3，签名是一对数：a=6和b=3。

验证签名时，只需确保：

y^aa^bmodp=g^Mmodp

3⁶6³（mod 11）=2⁵（mod 11）

EIGamal签名的安全性依赖于乘法群（IFp）∗上的离散对数计算。素数p必须足够大，且p-1至少包含一个大素数因子以抵抗Pohlig & Hellman算法的攻击。M一般都应采用信息的散列值（如SHA算法）。EIGamal的安全性主要依赖于p和g，若选取不当则签名容易伪造，应保证e对于p-1的大素数因子不可约。D.Bleichenbache在Generating EIGamal Signatures Without Knowing the Secret Key中提到了一些攻击方法和对策。EIGamal的一个不足之处是它的密文成倍扩张。

美国的DSS（Digital Signature Standard）的DSA（Digital Signature Algorithm）算法是经EIGamal算法演变而来的。

5．椭圆曲线密码算法

椭圆曲线第一次运用于公钥密码算法是在1985年由Neal Koblitz和Victor Miller分别独立提出来的。椭圆曲线数字签名算法（Elliptic Curve Digital Signature Algorithm，ECDSA）由IEEE工作组和ANSI（American National Standards Institute）X9组织开发。随即学者们展开了椭圆曲线密码学（Ellipse Curve Cryptography，ECC）研究。

除椭圆曲线外，还有人提出在其他类型的曲线如超椭圆曲线上实现公钥密码算法。其根据是有限域上的椭圆曲线上的点群中的离散对数问题（Ellipse Curve Discrete Logarithm Problem，ECDLP）。ECDLP是比因子分解问题更难的问题，许多密码专家认为它有指数级的难度。

从目前已知的最好求解算法来看，相比RSA，ECC优势是可以使用更短的密钥，来实现与RSA相当或更高的安全。据研究表明，160位ECC加密安全性相当于1024位RSA加密，210位ECC加密安全性相当于2048位RSA加密。使用短密钥的好处在于加解密速度快、节省能源、节省带宽、存储空间。目前我国居民“二代身份证”正在使用256位的椭圆曲线密码，虚拟货币“比特币”也选择ECC作为加密算法。

此外，有人在椭圆曲线上实现了类似EIGamal的加密算法及可恢复明文的数字签名方案。除有限域上的椭圆曲线密码算法外，人们还探索了在椭圆曲线上实现RSA算法，如KMOV。

（1）有限域上的椭圆曲线

数学上的椭圆曲线一般由如下形式给出：

E：y²=x³+ax²+bx+c，其中判别式

Δ（E）=-4a³c+a²b²-4b³-27c²+18abc≠0

椭圆曲线都是关于X轴对称的曲线。

典型的椭圆曲线如y²=x³-4x²+16，其图像如下。

更多的椭圆曲线图像：

在密码学中用到的椭圆曲线方程一般限定为：

E：y²=x³+ax+b，其中4a³+27b²≠0。

也即是这里的二次项系数为0。

密码学中普遍采用的是有限域上的椭圆曲线，也即是变元和系数均在有限域中取值的椭圆曲线。使用模素数p的有限域Zp，将模运算引入椭圆曲线算术中，变量和系数从集合0，1，2，…，p-1中取值而非是在实数上取值。

此时椭圆曲线形式如下：

y ²modp=（x³+ax+b）modp

其中（4a³+27b²）modp≠0modp，变量和系数均在Zp中取值。

将满足上式的所有非负整数对和O点记为集合Ep（a，b），这是一个有限的离散点集。由此可知集合中的点分布在（0，0）到（p-1，p-1）的象限中，集合中的点有可能刚好也在椭圆曲线上，更多的可能是在椭圆曲线外。例如点（13，7）是满足y²mod 23=（x³+x+1）mod 23的点，但是（13，7）并不在椭圆曲线上。

在后面的ECC加密算法过程中会有一个给定的基点G（也就是生成元）生成一个子群，然后秘钥空间在此子群取得，一般会要求保证子群的阶会尽量大，基点及其子群的阶n都是公开的信息。

构造一个数学难题来保证加密的安全性是现代密码学中加密算法的主要思想。类似RSA算法中大数的质因子分解难题一样，椭圆曲线也有类似的数学难题。

考虑K=kG，其中K，G∈Ep（a，b），k＜p。

对于给定的k和G，计算K是很容易的；反过来给定K和G，计算k是相当困难的，这就是椭圆曲线的离散对数问题（这里之所以称之为离散对数问题，大概是为了与其他加密算法的说法保持一致，便于理解）。

正因为如此，可以将K作为公钥，公开出去；k作为私钥，秘密保管，通过公钥来破解私钥十分困难。

（2）椭圆曲线加密算法ECC

假设私钥、公钥分别为k和K。其中K=kG，G为基点。其中K、G为椭圆曲线Ep（a，b）上的点，n为G的阶（nG=O∞），k为小于n的整数。则给定k和G，根据加法法则，计算K很容易；但反过来，给定K和G，求k就非常困难。因为实际使用中的ECC原则上把p取得相当大，n也相当大，要把n个解点逐一算出来是不可能的。

公钥加密过程：

① A选定一条椭圆曲线E，并取椭圆曲线上一点作为基点G。

② A选择一个私有密钥k（k＜n），并生成公开密钥K=kG。

③ A将E和点K、G传给B。

④ B收到信息后，将待传输的明文编码为一个坐标点M，并产生一个随机整数r（r＜n，n为G的阶数）。

⑤ B计算点C1=M+rK和C2=rG。

⑥ B将C1、C2传给A。

加密完成，可以看出加密需要公钥，加密将坐标点M加密为C1、C2两个坐标点。加密者B只需发送C1、C2给解密者A即可。

私钥解密过程：

① 由C1=M+rK，可知M=C1-rK。

② 由K=kG，将K代入上式可得M=C1-rkG。

③ 由C2=rG带入上式，可得M=C1-k（rG）=C1-kC2。

④ A根据收到的C1、C2，用自己的私钥k，可以计算出加密坐标点M。

参数要求：

① p越大安全性越好，但会导致计算速度变慢，200bit左右可满足一般安全要求；

② n应为质数。

实例：（具体计算过程遵循有限域椭圆曲线的运算法则）

公钥加密过程：

① 考虑参数a=0，b=-4，p=199，G=（2，2），椭圆曲线方程为E：y²=x³-4。

② A选定私钥k=119，其公钥K=kG=119G=（183，173）。

③ A将E、K、G发给B。

④ B将明文消息编码为Ep（a，b）中的坐标点M=（76，66），并随机选定r=133。

⑤ B计算C1=M+rK=（76，66）+133（183，173）=（180，163）；

C2=rG=133（2，2）=（40，147）。

⑥ B将C1、C2发给A。

私钥解密过程：

A根据收到的C1、C2，用自己的私钥k=119进行解密：

M=C1-kC2=（180，163）-119（40，147）=（180，163）-（98，52）=（76，66）

由此，A顺利解密得到明文消息M，A与B之间完成加密通信。

（3）椭圆曲线签名算法ECDSA

这里，依然假设私钥、公钥分别为k和K。其中K=kG，G为基点。

私钥签名过程：

A选择随机数r，计算点rG（x，y）。

A根据随机数r、消息M的哈希h、私钥k，计算s=（h+kx）/r。

A将消息M和签名{rG，s}发给接收方。

公钥验证过程：

B收到消息M以及签名{rG=（x，y），s}。

B根据消息M，求哈希h。

使用发送方公钥K计算：hG/s+xK/s，并与rG比较，如相等即验签成功。

验证原理：

hG/s+xK/s=hG/s+x（kG）/s=（h+xk）G/s=r（h+xk）G/（h+kx）=rG

这里关键的一点是引入了随机数r，提高了签名的安全性，即使同一条消息，只要改变随机数r，所得到的签名也会随之改变。