加密和安全 V 0.92

轮变换由4个步骤组成：SubBytes，ShiftRows，MixColumns和AddRoundKey。最后一轮与前Nr -1次轮变换稍有不同，省掉了其中的MixColumns步骤。 字串1

步骤SubBytes是Rijndael算法中唯一的非线性变换——砖匠置换。

字串8

步骤ShiftRows是一个字节换位，它将状态中的行按照不同的偏移量进行循环移位。使第i 行第j 位的字节移动到位置（j -Ci）mod Nb，移动偏移量Ci 的值依赖于Nb 的取值。其中Nb =分组长度/32，对于AES，Nb 取固定长度4。 字串4

步骤MixColumns是作用在状态各列的砖匠置换。

密钥加法AddRoundKey将状态与一个轮密钥进行异或。轮密钥是由密码密钥通过密钥编排方案[1]导出。轮密钥的长度等于分组的长度。

Rijndael解密:

字串2

Rijndael解密算法有2种形式。一种是直接解密算法，即直接利用步骤InsubBytes，InvShiftRows，InvMixColumns和AddRoundKey的逆并倒置其次序对数据进行解密。

另一种是等价解密算法，其实现原理如图5所示。等价解密算法有利于有效实现良好的运算次序。

字串3

字串4

13.     非对称算法的概念

所谓非对称算法就是指加密和解密用的不是同一个密钥。

字串1

非对称算法的密钥分为二部分，通常称为“公钥”和“私钥”（或者称为“公开密钥”和“秘密密钥”）。公钥和私钥存在数学上的关系，使得用公钥加密的数据只能用对应的私钥解密，用私钥加密的数据只能用对应的公钥解密。但是从公钥中推导出私钥是很难的（理论上是可以推导出来的，但是实际上找不到这么强的计算能力）。 字串5

RSA,DSA等算法属于非对称算法。如图6所示

字串4

字串7

14.     RSA算法

RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA是被研究得最广泛的公钥算法，从1978年提出到现在已近三十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。通常认为破译RSA的难度与大数分解难度等价。算法以三个发明者的名字命名：Ron Rivest, Adi Shamir 和Leonard Adleman。 字串6

RSA算法的原理：

1、密钥对的产生：

选择两个大素数，p 和q 。计算：
n = p * q

然后随机选择加密密钥e，要求 e 和 ( p - 1 ) * ( q - 1 ) 互质。最后，利用
Euclid 算法计算解密密钥d, 满足 字串5

e * d = 1 ( mod ( p - 1 ) * ( q - 1 ) )

字串1

其中n和d也要互质。数e和n是公钥，d是私钥。两个素数p和q不再需要，应该丢弃，不要让任何人知道。 字串1

  字串8

2、加密

字串5

加密信息 m（二进制表示）时，首先把m分成等长数据块 m1 ,m2,..., mi ，块长s
，其中 2^s <= n, s 尽可能的大。加密的公式是：

字串3

ci = mi^e ( mod n )

字串3

3、解密
解密时作如下计算：
mi = ci^d ( mod n )

字串8

15.     散列算法

散列算法，也称为单向散列函数、杂凑函数、哈希算法、HASH算法或消息摘要算法。它通过把一个单向数学函数应用于数据，将任意长度的一块数据转换为一个定长的、不可逆转的数据。这段数据通常叫做消息摘要（比如，对一个几兆字节的文件应用散列算法，得到一个128位的消息摘要）。消息摘要代表了原始数据的特征，当原始数据发生改变时，重新生成的消息摘要也会随之变化，即使原始数据的变化非常小，也可以引起消息摘要的很大变化。因此，消息摘要算法可以敏感地检测到数据是否被篡改。消息摘要算法再结合其它的算法就可以用来保护数据的完整性。 字串9

好的单向散列函数必须具有以下特性： 字串9

1) 计算的单向性：给定M和H，求h＝H(M)容易，但反过来给定h和H，求M＝H-1(h)在计算上是不可行的。

字串1

2) 弱碰撞自由：给定M，要寻找另一信息 M′，满足 H(M′)＝H(M)在计算上不可行。 字串8

3) 强碰撞自由：，要寻找不同的信息M 和M′，满足 H(M′)＝H(M)在计算上不可行。 字串5

单向散列函数的使用方法为：用散列函数对数据生成散列值并保存，以后每次使用时都对数据使用相同的散列函数进行散列，如果得到的值与保存的散列值相等，则认为数据未被修改(数据完整性验证)或两次所散列的原始数据相同(口令验证)。

字串1

典型的散列函数有：MD5，SHA-1，HMAC，GOST等。单向散列函数主要用在一些只需加密不需解密的场合：如验证数据的完整性、口令表的加密、数字签名、身份认证等。

16.     关于MD5和SHA-1等

山东大学王小云教授攻破了MD5算法，引起密码学界的轩然大波。

MD5的全称是Message-Digest Algorithm 5（信息-摘要算法），在90年代初由MIT Laboratory for Computer Science和RSA Data Security Inc的Ronald L. Rivest开发出来，经MD2、MD3和MD4发展而来。

字串4

2004年8月17日的美国加州圣巴巴拉，正在召开的国际密码学会议（Crypto’2004）安排了三场关于杂凑函数的特别报告。在国际著名密码学家Eli Biham和Antoine Joux相继做了对SHA-1的分析与给出SHA-0的一个碰撞之后，来自山东大学的王小云教授做了破译MD5、HAVAL-128、 MD4和RIPEMD算法的报告。王小云教授的报告轰动了全场，得到了与会专家的赞叹。 字串3

最近密码学家Lenstra利用王小云提供的MD5碰撞，伪造了符合X.509标准的数字证书，这就说明了MD5的破译已经不仅仅是理论破译结果，而是可以导致实际的攻击，MD5的撤出迫在眉睫。 字串6

SHA-1与 DSA 公钥算法相似，安全散列算法1(SHA-1）也是由NSA设计的，并由NIST将其收录到 FIPS 中，作为散列数据的标准。它可产生一个 160 位的散列值。SHA-1是流行的用于创建数字签名的单向散列算法。 字串4

事实上，在MD5被王小云为代表的中国专家破译之后，世界密码学界仍然认为SHA－1是安全的。今年2月7日，美国国家标准技术研究院发表申明，SHA－1没有被攻破，并且没有足够的理由怀疑它会很快被攻破，开发人员在2010年前应该转向更为安全的SHA－256和SHA－512算法。而仅仅在一周之后，王小云就发布了消息，说明了SHA-1算法寻找一对碰撞的复杂度是2^68，而不是密码学家以前认为的2^80。 以现有计算机的能力，可以认为SHA-1不能保证安全了。 字串4

不过，暂时还有SHA-256和SHA-512可用。密码学家也在研究新的散列算法。 字串5

17.     数字鉴名

密码技术除了提供信息的加密解密外，还提供对信息来源的鉴别、保证信息的完整和不可否认等功能，而这三种功能都是结合数字签名技术来实现的。 字串5

简单地说，数字签名的原理可以这样理解：用非对称算法的私钥加密的内容只能用对应的公钥来解密。而私钥是不公开的。因此，如果一段信息能用某个人的公钥解密，那么它一定是用此人的私钥加密的。它和物理的签名一样，是很难伪造的。

字串3

在实际应用中，数字签名的过程通常是这样实现： 字串6

将要传送的明文通过一种函数运算（Hash）转换成报文摘要（不同的明文对应不同的报文摘要），报文摘要用私钥加密后与明文一起传送给接受方，接受方用发送方的公钥来解密报文摘要，再将接受的明文产生新的报文摘要与发送方的报文摘要比较，比较结果一致表示明文确实来自期望的发送方，并且未被改动。如果不一致表示明文已被篡改或不是来自期望的发送方。如图7

字串8

18.     数字信封

数字信封是一种综合运用对称算法、非对称算法、消息摘要算法和数字签名的消息加密机制。为什么要引入这种机制呢？这是因为： 字串4

1、对称算法速度比较快，与同等安全强度的非对称算法相比，一般要快三个数量级左右。但是对称算法需要通过一个安全的通道交换密钥（或协商密钥，或事先约定密钥）之后才能进行通信。

2、非对称算法较慢，但是它的优点是通信双方不必事先约定密钥就可以进行安全通信。 字串4

3、单纯的加密算法只能保证消息的机密性，但无法保证消息不被篡改。结合消息摘要和数字签名算法就可以保证数据的完整性，并能确认对方的身份。 字串6

具体操作如图所示。利用对称加密算法(比如3DES)对比较长的消息进行加密，再利用接收者的证书对密钥进行加密，加密消息和加密密钥一起发送给消息接收者。后者利用自己的私钥对加密密钥解密得到密钥，接着用密钥对加密消息进行解密得到消息原文。与数字签名一样，消息的发送者不会涉及任何保密内容，只要知道接收者证书的人都可以向他发送数据信封封装消息。如图8

字串4

字串7

字串9

19.     椭圆曲线算法

当今使用的非对称算法根据其基于的数学难题可大致分为三类： 字串3

1）整数分解（IF）体制，其安全性基于整数分解问题的难解性，典型例子是RSA体制和Rabin体制。

2）离散对数（DL）体制，其安全性基于（一般）离散对数问题的难解性，典型例子是DSA体制、ElGamal体制和Schnorr体制。 字串1

3）椭圆曲线（EC）体制，其安全性基于椭圆曲线离散对数问题的难解性，典型例子是ECDSA体制。

椭圆曲线密码是在1985年由Neal Koblitz和Victor Miller独立提出来的。近年来，椭圆曲线体制由于其具有的很多技术优势，而受到越来越多密码学者的关注，逐渐形成了一个研究热点。它已被诸如ANSI（American Natio nal Standards Institute）、IEEE（Institute of Electrical and Electroni cs Engineers）、ISO（International Standards Organization）和NIST（National Institute of Standards and Technology）等标准化组织纳入为标准。它的技术优点包括： 字串8

1）安全性能更高：椭圆曲线离散对数问题的计算复杂度目前是完全指数级的，而RSA是亚指数级的。 字串6

2）计算量小和处理速度快：在相同的计算资源条件下，椭圆曲线体制比RSA和DSA有更快的处理速度。

字串5

3）存储空间占用小：椭圆曲线体制的密钥尺寸和系统参数与RSA及DSA相比要小得多。160比特EC与1024比特RSA、DSA具有相同的安全强度，210比特EC则与2048比特RSA、DSA具有相同的安全强度，这意味着它所占的存储空间要小得多。

字串4

4）带宽要求低。 字串2

椭圆曲线体制中最著名的是ECDSA，它是数字签名算法（DSA）移植到椭圆曲线上得到的。在所基于的群是一般群和所用的Hash函数是抗冲突的假设下，它已被证明是安全的。它的系统参数中选择的椭圆曲线的阶是近乎素数的，且它的签名长度至少为320比特。

20.             未来发展方向：量子力学与信息安全

物理学从经典物理学发展到相对论，又发展到量子物理学，每一步都使我们对世界有更深刻的了解，并带来新的技术进步。在信息安全方面，量子力学以意想不到的方式带来了全新的思路和技术。 字串9

量子技术在密码学上的应用分为两类：一是利用量子计算机对传统密码体制的分析；二是利用单光子的测不准原理在光纤一级实现密钥管理和信息加密，即量子密码学。

字串4

下面对这种新的方向作一个简要的介绍。

21.             量子计算机

1996年，美国《科学》周刊科技新闻中报道，量子计算机引起了计算机理论领域的革命。同年，量子计算机的先驱之一，Bennett在英国《自然》杂志新闻与评论栏声称，量子计算机将进入工程时代。目前，有关量子计算机的理论和实验正迅猛发展。

与经典计算机相比，量子计算机最重要的优越性体现在量子并行计算上。因为量子并行处理，一些利用经典计算机只存在指数算法的问题，利用量子计算机却存在量子多项式算法，这方面最著名的一个例子当推Shor在1994年给出的关于大数因子分解的量子多项式算法。

字串4

大数的因子分解是数学中的一个传统难题，现在人们普遍相信，大数的因子分解不存在经典的多项式算法，这一结果在密码学中有重要应用。著名的RSA算法的安全性就基于大数因子分解。对于经典计算机，大数因子分解不存在有效的多项式时间算法。但Shor却证明，利用量子计算机，可以在多项式时间内将大数分解，这一结果向RSA公钥系统的安全性提出了严重挑战。

字串8

不过，量子计算机的实验方案还很初步。现在的实验只制备出单个的量子逻辑门，远未达到实现计算所需要的逻辑门网络。但是，总体来讲，实现量子计算，已经不存在原则性的困难。按照现在的发展速度，可以比较肯定地预计，在不远的将来，量子计算机一定会成为现实，虽然这中间还会有一段艰难而曲折的道路。 字串4

22.             量子密码

量子计算机对传统密码技术带来严重挑战的同时，也带来了全新的量子密码技术。

字串7

上世纪下半叶以来，科学家在“海森堡测不准定理”和“单量子不可复制定理”上，逐渐建立了量子密码术的概念。“海森堡测不准原理”是量子力学的基本原理，指在同一时刻以相同精度测定量子的位置与动量是不可能的，只能精确测定两者之一。“单量子不可复制定理”是“海森堡测不准原理”的推论，指在不知道量子状态的情况下复制单个量子是不可能的，因为要复制单个量子就只能先作测量，而测量必然改变量子的状态。
　　量子密码术突破了传统加密方法的束缚，以量子状态作为密钥,它具有不可复制性。任何截获或测试量子密钥的操作，都会改变量子状态。这样截获者得到的只是无意义的信息，而信息的合法接收者也可以从量子态的改变，知道密钥曾被截取过。与公开密钥算法不同，当量子计算机出现，量子密码术仍是安全的。这与以数学为基础的传统密码学不同，传统密码学的安全是一种相对的安全。而量子密码术是建立在物理定律基础上的，似乎可以说是“绝对安全”了。

具体通信过程如下：

字串8

在发送者和接收者之间传送量子密钥的一种方式是，激光发射以两种模式中的一种极化的单光子。在第一种模式中，光子垂直或水平摆放（直线模式）；在第二种模式中，光子与垂直线呈45度角摆放（斜线模式）。
　　发送者（密码学家通常称之为艾丽斯）发送一串比特序列（量子振动的方向，即它们的偏振态，代表0或1，形成一连串的量子位，或称量子比特）。随机选择光子直线或斜线的传送模式。接收者（在密码学语言中称为鲍勃）同样随机决定对接收比特的测量模式。海森伯的测不准原理表明，鲍勃只能用一种模式测量光子，而不能同时使用两种模式。只有鲍勃测量的模式和艾丽斯发送的模式相同，才能保证光子方向准确，从而保留准确数值。
　　传送完成后，鲍勃告诉艾丽斯，他使用哪种模式接收每一个光子，这一过程无须保密。然而，他不会透露每个光子代表的0或1的数值。然后，艾丽斯告诉鲍勃哪些模式是正确的。双方都将接收模式不正确的光子视为无效。正确的测量模式组成一个密钥，作为用来加密或解密一条信息的算法的输入值。