加密算法类型

加密算法类型
2010-12-09 15:51
加密算法类型
密码学（Cryptology）是一种设计各种用以提供安全的算法的理论。密码术（Cryptography）研究使用这些算法来保证系统和协议的安全。本节将概括描述各种可用的加密算法类型。
1、加密
从概念上来讲，最易于理解的算法就是加密（Encryption）算法。其思想是简单的：加密算法接收一些数据（称做明文）并在密钥（key）的控制下将其转换为密文（ciphertext）。密文看上去就像随机数据，不知道密钥就无法收集与明文有关的各种有用信息（长度信息可能除外）。密钥通常只是一个简短的随机字符串，通常约有8~24 个字节。图1 中描述了这些元素之间的相互关系。

明文 ---经过加密---> 密文  ---经过解密---> 明文
图1：加密与解密

加密算法应被视为纯粹是提供保密性。根据所使用的具体加密算法的不同，篡改密文对明文的确切影响也有所不同。但是这种篡改通常很难被发现。因此，当我们接收到一条只经加密的消息时，我们无法知道它是否被篡改过。
好的加密算法完全应当由可能的密钥数量决定其安全与否。最快的攻击应该是穷举搜索（exhaustive search）：在给定密文的情况下，每次尝试一个密钥直到产生大致正确的解密输出为止。算法的安全应当只依赖于密钥的保密，算法的保密不应当是安全性的必要条件。
攻击者在知道密文所对应明文情况下的攻击称做已知明文（known plaintext）攻击。攻击者在不知道明文情况下的攻击被称做只有密文（ciphertext only）攻击。即便是攻击者不知道明文的具体内容，他也有可能了解有关它的一些情况，这可以让他实施一种只有密文攻击。举例来说，攻击者或许知道明文为ASCII 码，在这种情况下，任何包含非ASCII 的解密输出都必定使用了错误的密钥。
由于发送者与接收者使用同一个密钥（这个密钥必须保密），我们刚才所描述的有时被称之为秘密密钥加密（secret key cryptography），以与公用密钥加密（public key cryptography）形成对照，我们稍后再来讲述有关后者的知识。
加密算法设计是一个非常活跃的领域，没有成百上千也有几十种可用的算法。最为流行的算法包括数据加密标准（DES）[NIST1993a]，Triple-DES（三重DES）[ANSI1985]，RC2[Rivest1998]和RC4（还没有出版任何正式的RC4 规范，请参阅[Schneier1996a]来了解有关的信息）。

2、消息摘要
消息摘要（Message Digest）是一种函数，它接收一个任意长度消息为输入，并产生一个表示消息特征的定长字符串。消息摘要最重要的属性就是不可逆性（irreversibility）。给定摘要值，要想计算出它所对应的消息应当是极其困难的。通过一个记数变元就可以很容易的表明摘要值，并没有提供足够产生原始消息的数据。可能的（任意长度）消息远比定长特征值长，从而使得几乎不可能存在函数的逆。然而，要想让一种摘要是安全的，就必须难以生成摘要值为该值的任何消息。我们所讲的困难就是指为了找到匹配的消息文本，你需要搜索与摘要值尺寸成比例的消息空间。
消息摘要值的第二个重要属性就是要想产生具有相同摘要值的两条消息M 和M'应当是困难的。该属性被称做抗冲突性（collision resistance）。实际上，任何抵御冲突发生的消息摘要的强度只有摘要值的一半，因此一个128 位的摘要值避免发生冲突的强度只有64 位，也就是说需要大约264 次操作才会产生一次冲突。因此，在选择摘要值长度时的限定性因素通常是抵御冲突的强度，而不是抵御可逆性的强度。
消息摘要的首要用途就是用于计算数字签名（digital signature）和信息验证码（MAC），我们将在本章的后面讲到这两项功能。不过，现在至少有一种显而易见的利用简单摘要值的用途：使用它，无需提供保密信息就能证明你拥有相应的保密信息。假设你发明了一种新东西，想在不告诉人们这是什么东西的条件下表明你是第一个发明它的人。你就可以记下保密信息，计算出它的摘要值，然后再将摘要值刊登在报纸的分类广告上。于是，如果有人对你作为第一发明人表示怀疑的话，你就可以将原始文本拿给他们看，而他们就可以独立的对摘要值进行验证。
使用最为广泛的消息摘要算法为消息摘要 5（MD5）[Rivest1992]和安全散列算法1（SHA-1）[NIST1994a]。散列算法这个字眼经常用做消息摘要的同义词，因为摘要算法表面上与普通的散列算法非常相似


3、MAC（信息验证码）
假设Alice 与Bob 共享一个密钥，Alice 想给Bob 发送一条消息，而Bob 将会知道它是Alice 发送的。如果她加密的话，那就非常简单，只需将他们共享的密钥用做加密密钥即可。但是如我们所讲的，这种方法并不能提供任何消息未被篡改的真正保证，只能保证消息来自于Alice。我们需要一种新的工具，即信息验证码（message authentication codes，MAC）。MAC 类似于摘要算法，但是它在计算的时候还要采用一个密钥，因此MAC 同时依赖于所使用的密钥以及要计算其MAC 的信息。实际上MAC 通常是根据摘要算法构造得出的。
尽管存在许多基于各种摘要算法来构造MAC 的尝试，但是因特网安全团体似乎就一种称做HMAC[Krawczyk1997]的构造方法达成了一致，这种方法描述了如何基于满足某种合理假定摘要来创建具有可证明的安全特性的MAC。SSLv3 中使用的是一种HMAC 的变种，而真正的HMAC 在TLS 中使用。

4、密钥管理的问题
现在有了MAC 这项新增的工具箱，就有了与本章开头所讨论的邮寄保险柜等价的电子系统。Alice 拿到我们的消息，使用共享密钥对信息进行加密，添加一个也是基于该密钥构造的MAC 并将其发送给Bob。她知道只有Bob 能够阅读这条信息，因为Bob 与其共享解密时所需要的密钥。类似的，Bob 知道发送这条消息的只有Alice，因为只有Alice 才具有创建消息上的MAC 时所需要的密钥。这样，Bob 就可以知道是Alice 发送的信息，而且还未被篡改。
那么，我们就有了所需要的一切，是吗？不。尽管这些消息比保险柜轻，邮寄也更为便宜，但是与每个人进行通信，仍然存在与其共享密钥的问题。周围有这么多密钥需要处理非常不方便。但更重要的是，这意味着为了进行密钥交换，你实际上必须要与每一个与之通信的人会面。这为通过因特网购买商品设置了障碍，除非你个人已经与供应商碰过面。这里面不便之处就是密钥管理的问题。

5、KDC（密钥分发中心）
针对密钥管理问题最流行的解决方案就是公用密钥加密（public key cryptography，PKC），将在下一节讲述相关的内容。
不过也存在一种只使用到目前为止所讨论的工具来解决密钥管理问题的措施。基本思想就是利用受信任的第三方，我们委托它对与我们通信的各方进行认证。这种第三方通常是由网络上某处一台安全的机器来实现的。这台机器被称做密钥分发中心（key distribution center，KDC）。每个需要保密通信安全的个人都与KDC 共享一个密钥。当Alice 想要与Bob 进行通信时，她就给KDC 发送消息，该消息以其与KDC 共享的密钥加以保护，请求与Bob 进行通信。KDC 产生了一个新的用于Alice 与Bob 之间进行通信的加密密钥，再将其放在一条称做许可证（ticket）的消息中返回。
一条许可证消息由两条消息组成。第一条消息是给Alice 的，其中带有新密钥。第二条消息是给Bob 的，用Bob 的密钥进行加密，其中也包含新密钥。Alice 将许可证中Bob 的那一部分转交给Bob，现在Alice 与Bob 共享密钥。这种协议的基础版本是由Needham 和Schroeder[Needham 1978]发明的，但是部署最为广泛的变种为Kerberos，在MIT 及其他地方大量应用于认证与加密（请参见[Miller1987]）。
这种方案有两种主要缺点。首先，KDC 必须总是处于联机状态，因为如果它下线的话，就无法完成通信初始化。其次KDC 能够读取任何两方之间传递的数据。它还能够伪造两方之间的通信。更糟的是，如果KDC 被攻克的话，任何两个KDC 用户之间的通信均将遭难。这可不行。尽管如此，对于封闭系统来说，人们对这种类型的协议还颇有兴趣。

6、公用密钥加密
1976 年，Stanford 有几个非常聪明的人，想出了一种更好的解决密钥管理问题的方法。在一篇名为“密码术新动向”[Diffie1976]的论文中，Whitfield Diffie 和Martin Hellman 提出了现在称之为公用密钥加密的方案。基本思想就是设计一种在加密和解密时使用不同密钥的函数。你公开自己的加密密钥（公用密钥），但解密密钥（私用密钥）要保密。（由于公用与私用密钥的不同，公用密钥加密有时被称做非对称加密，而共享密钥加密有时被称做对称加密）。这意味着无需碰面，任何人都能够给你发送保密信息。这在消除需要预先共享密钥的不方便之处的同时也解决了其中的保密性的问题。
事实表明PKC 针对问题中的认证部分也有一套解决方案。你的私用密钥可以用来创建某种称作数字签名的东西，它与MAC 之间的关系如同公用密钥加密与秘密密钥加密之间的关系一样。你使用私用密钥对消息进行签名，而接收方使用你的公用密钥来验证你的签名。注意，数字签名具有一项MAC 所不具备的重要属性：不可抵赖性（nonrepudiation）。发送方和接收方都可以产生MAC，但是只有签名者才能够产生签名。这样，接收者就可以证明发送方对消息进行了签名而发送方无法抵赖。

7、证书
尽管提供了我们解决问题所需要的工具，不幸的是，到目前为止我们所拥有的工具并不能完全解决密钥管理问题。要明白哪里存在问题，最简单的方法就是请问各方是如何得到彼此的公用密钥的。如果这些密钥是以电子形式发表的，或是通信各方通过交换得到的话，那么攻击者就能够在这些密钥传递给接收者的过程中进行篡改。当两方打算进行通信时，攻击者截获他们的密钥，并代之再将自己的密钥发送给每一方。这样每一方都会按照攻击者的要求来进行加密，而攻击者根据真正的接收者重新进行加密，如图2 所示，这被称作中间人攻击（man-in-the-middle attack）。然而，如果将密钥以物理方式印刷出来，则很不方便。解决方案（还是）就是通过称之为证书授予权（certificate authority，CA）的第三方。CA 发布以其私用密钥签名的目录。在实际应用中，CA 不是对目录进行签名，而是对包含密钥属主及其公用密钥的单一信息进行签名。这些信息一般被称作证书（Certificate），证书授予权因而得名。证书的主要标准为X.509[ITU1988a], 它是在RFC2459[Housley1999a]中为因特网编写的。

Alice                  Attacker攻击者           Bob
------>alice的密钥----------->------->攻击者的密钥------>
<------攻击者的密钥<---------<-------Bob的密钥<------
-->数据使用攻击者的密钥加密-->------->数据使用Bob的密钥加密-->
<--数据使用Alice的密钥加密<--<-------数据使用攻击者的密钥加密<--
        中间人攻击

CA 的公用密钥以某种物理形式发布，不过CA 并不多而且不经常变换密钥，因此这在实际应用中不成问题。通常将CA 密钥编译到需要使用它们的软件中，这样就能与软件一起发行。当软件以CD-ROM 或软盘方式发布时就非常有意义。但有时软件只是下载得到的，在这种情况下就又回到了刚开始时遇到的问题——即人们做事常常并不理智。


图3 描述了一份公用密钥证书展开后的视图。这里的细节并不重要，但请注意其中的基本结构：证书包含颁发者名称issuer name）（证书签名者的名字，这里就是“Secure Server... ”）， 主体名称（ subject name ）（ 证书所担保的密钥的持有者， 在这里就是“www.amazon.com...”），主体公用密钥（subject public key）（即密钥本身），一组控制信息，诸如有效期限、序列号以及对整个数据对象的签名。涉及证书的公用密钥解决方案仍然要包含受信的第三方（即CA），但是它们的确修正了我们前面所描述的基于KDC 系统的主要问题。由于同一个证书可以用来向任何人证明其公用密钥，所以CA 没有必要为了让Alice 与Bob 进行通信，而始终处于联机状态。同时因为CA 无法存取任何人的私用密钥，所以它也不能读取任何信息。

version: vl
serial number： 2A 17 EF 73 97 07 74 7B E2 4B FB
        61 95 DB 4D 77
signature
    algorithm: md5WithRSAEncryption
issuer:
    C=US
    O=RSA Data Security, Inc.
    OU=Secure Server Certification Authority
validity
    not before: Sat Jan 28 02:21:56 1995
    not after: Thu Feb 15 02:21:55 1996
subject:
    C=US
    ST=Washington
    L=Seattle
    O=Amazon.com, Inc.
    OU=Software
    CN=www.amazon.com
subject public key
    algorithm: rsaEncryption
    modulus
        bit length: 1024
        value:
            00 C8 lB 8B FA 40 C3 5B E3 46 3F 17 10 56 19 64 C4 F4 F9
            CC AE CA F7 OB 02 1C C3 2D 27 60 91 16 CO A1 23 8B CA 90
            77 31 25 CA D9 DE BO 87 F5 25 C9 12 7A 95 DF DC 6C E4 1C
            C3 31 9F 77 BE 69 3E 9F BB 35 BF F3 3D BA 7A 72 DA 5D 0C
            60 91 29 F8 89 67 50 5C 32 46 63 F2 FF 42 9D 24 F2 DC 6F
            E5 CA D3 CD 3A AB 9D 5F A9 4D BO 82 91 E3 D3 EA AA EF 78
            8A C1 06 B6 6D EA 56 B8 7E 68 5D AF 4D 85 AF
    public exponent:
        bit length: 2
    value: 03
signature
    value:
        03 43 60 4B 5B 4B Fl 78 56 BF B4 9B 81 E6 EE 0D 19 lB 4E 43 BD
        D9 C7 62 62 55 32 C7 15 A4 33 3A CA 0E 60 E5 FE D7 53 94 C6 AC
        17 D0 CE 7B 11 27 0C 3B 26 19 6D 35 55 4C D8 26 F4 5F FO 90 0D
        90 7F FC 39 47 FE EE B4 72 92 93 BF 93 7F 5C 56 38 10 F5 E5 58
        B5 6C 3E E0 B4 55 8D 74 BE 84 Fl 53 67 49 5B 14 12 E6 A7 59 A9
        97 9E 6C E4 59 A6 8F 4E 7E B5 D9 2D 80 3F 38 3C 4C 11 A7 37

            图3 公用密钥证书

8、DN（标识名）
证书中的主体名称及颁发者名称为X.500 标识名（Distinguished Names，DN）[ITU1988b]。标识名的目的就是为每个网络实体提供一个惟一的名字。为了达到这一目的，DN 具有一种分层的结构。一个DN 由一系列RDN（relative distinguished name，相对标识名）构成。RDN就像DNS 的组成部分那样，每个RDN 在其他一些实体的名字空间中指定实体的名字。因此，最上层的RDN 必须是全局范围内惟一的，而其下的每个RDN 只需在上一个RDN 作用域中保持惟一即可。RDN 也有结构，每个RDN 由一系列属性-值断言（attribute-value assertion，AVA）构成。基本上说，AVA 就是键/值对。图4 描述了一个DN 范例。

       Country = US
      Organization = RTFM
      Organization Unit = Consulting
      Common Name = Eric Rescorla

    图4 DN 范例

图4 中的每个方框代表一个RDN。于是顶层RDN 包含一个AVA，其中的属性为Country，值为US，以此类推。注意，尽管从理论上来讲，每个RDN 可以有多个AVA，但在实际应用中，几乎总是只有一个。与之类似，尽管从理论上讲，任何AVA 都可以在任何层次上出现，但在实际应用中，它们却总是从最不具体（如国家）到最具体的（普通名称——一般对应你的名字或email 地址）。标识名时常以文本形式来表述，其中将属性名书写为缩写形式。图4 中的名字会被表示为：
C=US， O=RTFM， OU=Consulting, CN=Eric Rescorla

9、扩展
证书包含一组标准值，但常常需要在其中安放其他一些信息。X.509 版本3 提供了一系列任意的扩展（Extension）。扩展就是类型-值对。尽管X.509 允许私有扩展，但还是提供了一些标准扩展。三种对我们来说是重要的扩展为：
subjectAltName 其中包含了这个用户其他的名称。这些可能是其他的DN，但也可能是其他的名字形式，其中包括dNSName（DNS 主机名）和emailAddress（email 地址）。
keyUsage 中包含了该密钥可接受用途的屏蔽位，这些用途包括签名、加密等等。
extendedKeyUsage 允许包含一组任意对象标识（OID）的列表，这个列表具体描述该密钥的用途。

10、证书的撤消
考虑这样一种情况，用户的密钥由于丢失或爆光而被泄露。我们想要以某种方式告诉其他用户这个公用密钥以及验证它的证书已经不再受信。处理这种问题最常见的方法就是使用某种称作证书撤消列表（Certificate Revocation List，CRL，发音为“krill”）的东西。
CRL 是一个经过签名的、标有日期的、包含所有已撤消证书的列表，撤消意味着不再被视为是有效的。假设某个CA 发布CRL，对证书进行验证则要求获得适当的（最新的）CRL，并检查该证书未在列表中出现。
不幸的是，由于两种原因，CRL 工作的并不是很好。第一，需要定期的发布CRL，这意味着在发布CRL 时与下一次发布CRL 之间存在安全隐患空挡。密钥或许已经被攻破，但是用户却无法得知，因为包含它的CRL 还没有发布。第二，CRL 的分发存在问题。CRL 可能变的越来越大，而任何一种协议都要捎带上它，或是从CA 获取，而这就又要求CA 是联机的。
如果CA 是联机的话，它还可以提供联机证书状况（online certificate status）报告。这样完全可以提供最新的撤消状况信息。用户可以向CA 请求得到给定证书的状况，而CA 则提供经过签名的应答。我们可以使用联机证书状况协议（Online Certificate Status Protocol，OCSP）[Myers1999]来完成这项工作。然而，对应答进行签名的要求会给服务器CPU 带来很高的负载。显然，这并不是我们想要的。存在一些减轻此类负载的优化措施[Kocher1996a]，但是并没有被广泛部署。

11、ASN.1、BER 和DER
ASN.1 属于那种让人“感到很不舒服”而有时又必须了解的东西。有许多基本的安全工具，特别是X.509 证书，最终都是以ASN.1 来定义的。ASN.1 是作为OSI（Open StandardsInterconnect，国际电信联盟开放标准互联）成果的一部分而定义的，它用作一种OSI 协议的描述语言。基本思想就是为描述数据结构而创建一种允许通过机器来产生数据编码解码器（一般称之为codec）的系统。
这在当时似乎是一种不错的想法：你有了一种可以用来将数据格式描述为结构化类型的语言，这非常类似于C 中的struct 以及Java 中的类。这种语言被称作抽象语法记法1（ASN.1）。你还描述如何将以这种语言书写的结构映射为线路上的数据编码。它使你能编写一种完成两项工作的编译器：
（1）产生从ASN.1 结构到任何一种你所使用语言的映射；
（2）自动为结构生成译码器。
不幸的是，ASN.1 复杂而且违背正常的思维，从而使得不仅开发编译器相当困难，就连编写ASN.1 本身也都很困难。更糟的是，尽管按理说，多就意味着好，但设计ASN.1 的人为在线路上的数据传输格式定义了不是一种，而是多达四组不同的编码规则。且每种编码只是为了一组稍有不同的目标提供服务，结果是一团糟。
将会与我们有关的两种ASN.1 编码规则为基本编码规则（Basic Encoding Rules，BER）和辩识编码规则（Distinguished Encoding Rules，DER）。鉴于BER 对任意给定数据段可以有多种编码方式，DER 是BER 的子集，它选取并坚持使用其中的一种方式，这样你就可以确信任何codec 对给定的任何结构都以同样的方式进行编码。BER 的优势就在于，以BER 编码的数据通常要比以DER 编码的效率要高。然而，如果你对数据进行数字签名，想让语义上等价的信息总以相同的方式进行编码，那么就需要使用DER。

现在已经有了足够多的工具来构建一些简单的安全系统。我们将要讲述的系统听起来很复杂，但是需要明白的重要一点是，所要讨论的几乎每一种通信安全技术都是简单地根据四种技术：加密、摘要计算、公用密钥加密和数字签名中的一种来构造的。这些技术常被称做安全原语（security primitive），组合使用这些原语可以构建出更为复杂的结构。
举例来说，公用密钥方式要比共享密钥方式慢得多，因此我们可以方便的组合使用这两种技术，使用公用密钥来完成共享密钥的交换。为了加密一条消息，Alice 产生一个随机的共享密钥（该密钥的不同称呼有会话密钥、信息加密密钥、内容加密密钥、数据加密密钥）并用Bob 的公用密钥对其进行加密，这个公用密钥是从Bob 的证书中获得的。然后她使用这个会话密钥通过对称加密算法对消息进行加密。这种组合使用公用密钥加密和对称加密的方法提供了对消息的快速加密，同时又具有基于证书的密钥管理的好处。与之类似，数字签名算法非常慢，且只适用于短小的信息。但是与消息摘要组合使用，就可以高效的对大块信息进行签名。为了对消息进行签名，Alice 计算出消息的摘要值并使用其私用密钥对摘要值进行签名。组合使用信息摘要和数字签名提供了消息完整性和发送方认证而不必共享密钥。