DES算法由一个映射：DES:{0,1}64 × {0,1}56→{0,1}64构成，若选好密钥k，则有：DESk: {0,1}64 →{0,1}64,x|→DES(k,x)。

DES加密过程要经过16圈迭代，从56比特的有效密钥生成16个子密钥{k1,?,k16}，每个子密钥ki的长度是48比特，在16圈迭代中使用。解密和加密采用相同的算法，并且所使用的密钥也相同，只是各个子密钥的使用顺序不同(如图3-8所示)。

在图3-8所示的DES算法描述中，64比特明文经过初始置换IP后，分成左半部和右半部两块，每块32比特，进入16圈迭代。在DES的16圈迭代中，映射：f:{0,1}32×{0,1}48→{0,1}32是建立分组的基础之一。f取决于32比特的明文和48比特的密钥，它由一个替换S和一个置换P构成：f(x,k?)=P(S(E(x)⊕k))。32比特的明文x经x|→E(x)，扩展为48比特，并与48比特的密钥k异或，然后把所得的48比特分成8组，每组6比特，并被S替换为4比特。最后，将得到的32比特(即8组×4比特)进行P置换。对于每一个子密钥ki，可得

fki:{0,1}32→{0,1}32，x|→f(x,ki)，i=1, 2,?,16

对于i=1,2,?,16中的每一轮迭代，左半部32比特明文x与右半部32比特明文y的加密密文fi(y)进行异或，可得：?i:{0,1}32×{0,1}32→{0,1}32×{0,1}32，(x,y) |→(x⊕fi(y),y)。

函数DESk由?1,?,?16及μ: {0,1}32×{0,1}32→{0,1}32×{0,1}32，(x,y) |→(y,x)组合而成，即 DESk:{0,1}64→{0,1}64

DESk(x)=IP-1°?16°μ°…μ°?2°μ°?1°IP(x) 其中，IP是公开的已知置换，符号“°”表示组合操作。 由于?i-1= ?i及μ

-1=μ

，因此，对所有的明文消息x∈{0,1}64，恒有DESk16,…,k1(DESk1,…,k16(x))=x。

DES使用16个不同的密钥通过16轮相同类型的加密而得到密文，其中，16个密钥是由56比特的初始密钥生成的，?i称为第i轮加密函数，除了最后一轮，每一轮加密后左半部和右半部都互换。DES算法的密码强度取决于f的设计，特别是8个著名的处理替换的S盒的设计。

例3-6 DES加密示例。

设明文m= \，密钥k= \，相应ASCII码用二进制表示为： m=01100011 01101111 01101101 01110000 01110101 01110100 01100101 01110010 k=01110000 01110010 01101111 01100111 01110010 01100001 01101101

因为k只有56比特，必须插入第8、16、24、32、40、48、56、64位奇偶校验位，合成64比特，当然，这8位对加密过程没有影响。

m经过IP置换后得到：

L0=11111111 10111000 01110110 01010111 R0=00000000 11111111 00000110 10000011 k经过子密钥生成过程得到第1轮48位子密钥：

k1=00111101 10001111 11001101 00110111 00111111 00000110 m经过16轮迭代以后，再经过逆置换，得到密文：c=0xb2dcc3be594c571d

相应二进制表示为：

c=10110010 11011100 11000011 10111110 01011001 01001100 01010111 00011101 ②三重DES

三重DES(记为3DES)加密算法是一种改进的DES算法，它使用3组密钥k1、k2和k3对同一组明文进行多重加密(如图3-9所示)，密钥长度为168比特(即56比特×3)。

加密算法定义如下：c=Ek3(Dk2(Ek1(m))) 解密算法定义如下：m=Dk1(Ek2(Dk3(c)))

在DES的标准报告FIPS46-3中推荐使用k1=k3进行多重加密，此时密钥长度为112比特(即56比特×2)。

加密算法定义如下：c=Ek1(Dk2(Ek1(m))) 解密算法定义如下：m=Dk1(Ek2(Dk1(c))) 例3-7 三重DES加密示例。

设明文m=\，密钥k=\，经过3DES加密之后，得到密文c=0x95c560a3a9591798。

③AES和IDEA

DES已走到了尽头，56比特密钥实在太小，三重DES只是在一定程度上解决了密钥长度的问题。另外，DES的设计主要针对硬件实现，而今在许多领域都需要有软件的实现方法，在这种情况下，DES的效率相对较低。1997年4月15日，美国国家标准技术研究所发起征集高级加密标准(Advanced Encryption Standard, AES)算法的活动，并成立了AES工作组，目的是为了确定一个非保密的、公开的、全球免费使用的加密算法，用于保护敏感信息。AES的基本特点是：比三重DES快，至少和三重DES一样安全，分组长度为128比特，密钥长度为128/192/256比特。

2000年10月，美国国家标准技术研究所选择Rijndael密码作为高级加密标准。Rijndael密码是一种迭代型分组密码，由比利时密码学家Joan Daemon和Vincent Rijmen设计，使用了有限域F28上的算术运算。数据分组长度和密钥长度都可变，并可独立指定为128、192或256比特，随着分组长度不同迭代次数也不同。Rijndael密码可在很多处理器和专用硬件上高效地实现。

国际数据加密算法(International Data Encryption Algorithm, IDEA)是由瑞士的Xuejia Lai和James Massey等人于1990年提出的，能够抵抗差分密码分析。IDEA算法使用128比特的输入密钥k，将64比特的明文分组m加密成64比特的密文分组c。著名的电子邮件安全软件PGP(Pretty Good Privacy)就采用了IDEA算法进行数据加密。

3.2.2 基于公钥的加密方法及技术

公钥密码学的基本思想是公开密钥。为了保证公钥密码系统的安全，必须确保从公钥ke计算私钥kd是不可行的，密钥空间足够大，存在有效的算法实现随机选择密钥。公钥密码的安全簇取决于某些困难问题的难解性。公钥密码中常用的难解问题有大整数分解问题、离散对数问题、椭圆曲线上的离散对数问题等。RSA、EIGamal和ECC都是公钥加密方法的典型代表。

(1)RSA加密方法

1977年美国麻省理工学院的三位数学家Ron Rivest、Adi Shamir和Len Adleman成功地设计了一个公钥密码算法，该算法根据设计者的名字被命名为RSA算法。在其后的30年中，RSA成为世界上应用最为广泛的公钥密码算法。RSA密码的安全性基于大整数分解的困难性。若已知两个大素数p和q，求n:=pq是容易的，而由n求p和q则是困难的，这就是大整数分解问题。

RSA算法分为密钥生成、加密和解密三个阶段。在密钥生成阶段，密钥生成算法执行以下3个步骤： ? 选择不同的大素数p和q，计算n:= p·q，φ(n):=(p-1)(q-1)。 ? 选择e，满足1

其中，n、e、d分别为模数、加密指数和解密指数，φ(n)是n的欧拉函数值，d是e在模φ(n)下的乘法逆元。

在加密和解密阶段，加密时首先对明文比特串分组，使得每个分组对应的十进制数小于n，即分组长度小于log2n。对Zn={0,1,...,n-1}范围内的消息m进行加密。

加密函数定义如下： E: Zn→Zn，x|→xe 解密函数定义如下： D: Zn→Zn，x|→xd

映射E和D彼此互逆。即对于任意明文m∈Zn， 加密算法定义如下： c≡me (mod n) 解密算法定义如下：m≡cd (mod n)

例3-8 RSA应用示例，Alice向Bob发送加密消息。 Bob：选取p:= 101，q:=113，计算 n:= p·q:=101x113:=11413

φ(n):= (p-1)(q-1):= 100 x 112:= 11200

选取：e:= 3533，验证：gcd(e, φ(n)):= gcd(3533, 11200):= 1 计算：d≡e-1mod φ(n):= 3533-1 mod 11200:= 6597

Bob的公钥(n, e):=(11413, 3533)，私钥(n, d):=(11413, 6597)。

Alice：想加密明文m:= 9726，计算：c≡me(mod n):= 97263553 (mod 11413):= 5761 并把密文c=5761传送给Bob。

Bob：收到密文c=5761后，计算m≡cd(mod n):= 57616597 (mod 11413):= 9726 (2)EIGamal加密方法

EIGamal密码是1985年由T. ElGamal提出的，是基于离散对数问题的最著名的公钥密码体制。若给定一个大素数p，p-1有一大素数因子，则可构造一个乘法群Z*p，Z*p是一个p-1阶循环群。设g是Z*p的一个本原根，且1

EIGamal算法分为密钥生成、加密和解密三个阶段。在密钥生成阶段，密钥生成算法执行以下3个步骤：

? 选择大素数p，使p-1有大素数因子，选择g∈Z*p为本原根。 ? 随机选择整数d，满足1?d?p-2, d为私钥。 ? 计算e≡gd (mod p), e为公钥。

其中，p、g和e公开，为所有用户所共享，d保密。

在加密和解密阶段，对消息m∈Z*p进行加密，随机选择整数k，满足1?k?p-2。 加密函数定义如下：E: Zp→Zp，x|→xek 解密函数定义如下：D: Zp→Zp，x|→x(gk) -d 即对于任意明文m∈Z*p，随机整数1?k?p-2 加密算法定义如下：c1≡gk (mod p)

c2≡mek (mod p)≡mgdk (mod p)

解密算法定义如下：m≡c2 (c1)-d (mod p)≡mgdk (gk)-d (mod p)

加密结果依赖于消息m、公钥e和随机整数k。如果随机整数k的选择与消息m无关，那么几乎不可能出现两个明文生成同一个密文的情况。

例3-9 EIGamal应用示例，Alice向Bob发送加密消息。

Bob：选取素数p:= 2357, Z*2357上的本原根g:=2，私钥d:= 1751，计算 e≡gd (mod p):= 2 1751(mod 2357):= 1185 e=1185为Bob公钥。

Alice：想加密明文m:=2035，随机选取整数k:=1520，计算 c1≡gk (mod p) 21520 (mod 2357):= 1430

c2≡mek (mod p)≡2035 x 11851520 (mod 2357):= 697 将密文(c1, c2):=(1430,697)传送给Bob。 Bob：收到密文(c1, c2):=(1430,697)后，计算

m≡c2·(c1)-d (mod p)≡c2·(c1d)-1 (mod p)

≡697 x (14301751) -1 (mod 2357) ≡697·872 (mod 2357):= 2035 (3)ECC加密方法

1985年，Koblitz和Miller分别提出利用椭圆曲线来开发公钥密码体制。椭圆曲线密码ECC(Elliptic Curve Cryptography)的安全性基于椭圆曲线离散对数求解的困难性。目前普遍认为，椭圆曲线离散对数问题要比大整数因子分解和有限域上的离散对数问题难解得多。

椭圆曲线是满足一类方程的点的集合，通过在点间定义一种特殊的运算，可以得到一个群，称为椭圆曲线群。设E是某有限域上的椭圆曲线，G是椭圆曲线E的一个素数阶循环子群，α是该循环子群G的一个生成元，β∈G是该循环子群G的一个元素。已知α和β，求满足β=nα的唯一整数n，称为椭圆曲线上的离散对数问题。

与RSA密码相比，ECC密码能用较短的密钥实现较高的安全性。也就是说，要达到同样的安全强度，ECC算法所需的密钥长度远比RSA算法短，并且随着加密强度的提高，ECC的密钥长度变化不大(如表3-4所示)。

为了用好ECC加密方法，需要先来认识椭圆曲线。设p是一个大于3的素数，Fp是模p的有限域，Fp上的椭圆曲线E定义为：E:y2≡x3+ax+ b(mod p)

其中，a, b, x, y∈Fp且满足：4a2+27b3≠0 (mod p)

E(Fp)表示椭圆曲线E上的所有点(x, y)和无穷远点O的集合，也记为Ep (a,b)，或者直接记为E。 在椭圆曲线E上按如下法则定义加法运算：

? 定义无穷远点O为加法单位元，对于任意点P∈E有：P+O:=O+P:=P ? 若P:= (x, y)∈E，定义-P:= (x,-y)，(x,y)+(x,-y):=O。

? 若P:= (x1,y1)∈E，Q:= (x2,y2)∈E，定义P+Q:= (x3,y3)，其中， X3≡λ2- x1- x2 (mod p), y3≡λ(x1- x3)- y1 (mod p)

例3-10椭圆曲线点乘示例。设a:=1，b:=6，p:=11，椭圆曲线方程为

23

E:y≡x+x+6(mod 11)