这是第一部分--密码协议的第一章,也是全书的第二章,叫“协议结构模块”。花了两星期,在地铁上看完了第二章。最近很忙,事情很多,身体也需要休息,但还是趁今晚总结下第二章的知识点和疑问。

协议概述

“密码学的用途是解决种种难题(实际上,很多人忘记了这也是计算机的主要用途)。密码学解决的各种难题围绕机密性、鉴别、完整性和不诚实的人。”

  • 协议 (Protocol)
    是一系列步骤,它包括两方或多方,设计它的目的是要完成一项任务。
    “一系列步骤”:协议从开始到结束的一个序列,每一步必须依次执行。
    “包括两方或多方”:完成协议至少需要两方,这是跟“算法”的不同之处。

协议的其他特点:

  • 协议中的每个人都必须了解协议,并且预先知道所要完成的所有步骤。
  • 协议中的每个人都必须同意并遵守它。
  • 协议必须是清楚的,每一步必须明确定义,并且不会引起误解。
  • 协议必须是完整的,对每种可能的情况必须规定具体的动作。

“本书中的协议是线性执行的...每一步至少完成两件事中的一件,即由一方或多方进行计算,或者在各方中传送信息。”

  • 密码协议(cryptographic protocol)是使用密码学的协议
    不可能完成或知道得比协议中规定的更多。

协议的目的

本书中的剧中人

人名 角色 人名 角色
Alice 所有协议的第一个参加者 Bob 所有协议的第二个参加者
Carol 三、四方协议中的参加者 Dave 四方协议中的参加者
Eve 窃听者 Mallory 恶意的主动攻击者
Trent 值得信赖的仲裁者 Walter 仲裁者:在某些协议中保护Alice和Bob
Peggy 证明人 Victor 验证者
  • 仲裁者 (arbitrator)
    在完成协议的过程中,值得信赖的公正的第三方。如律师和公证人。
    仲裁者的概念与人类社会一样悠久。总是有那么一些人--统治者、牧师等,他们有公平处理事情的权威。在我们的社会中,仲裁者总是有一定社会地位和声望的人。
  • 裁决协议
    由于雇佣仲裁者代价高昂,仲裁协议可以分成两个低级的子协议(subprotocol)
    非仲裁子协议:执行协议的各方每次想要完成的;
    仲裁子协议:仅在有争议的时候才执行,这种仲裁者叫裁决者(不必参与协议所有部分)。

  • 自动执行协议(self-enforcing protocol)
    协议中最好的,协议本身就保证了公平性,不需要仲裁者来完成协议,也不需要裁决者来解决争端。不幸的是,对于所有情形都没有一个自动执行协议。

  • 对协议的攻击
    密码攻击可以直接攻击协议中所用的密码算法或用来实现该算法和协议的密码技术或攻击协议本身。在这里只讨论对协议本身的攻击。

  • 被动攻击 (passive attack)
    与协议无关的人能够窃听协议的一部分或全部,不影响协议,比如唯密文攻击。Eve扮演。

  • 主动攻击 (active attack)
    可能改变协议以便对自己有利的攻击,如引入新消息、删掉消息、代替消息、重放旧消息和破坏通信信道等,依赖于网络。由Mallory扮演。

  • 骗子 (cheater)
    攻击者为与协议有关的一方时,可能在协议期间撒谎,或者不遵守协议。
    被动骗子(passive cheater)遵守协议,但试图获取协议外的其他消息。
    主动骗子(active cheater)破坏协议。

使用对称密码系统通信

“好的密码系统的全部安全性只与密钥有关,与算法没有任何关系。这就是为什么密钥管理在密码学中如此重要的原因”

对称密码算法简述:

  1. Alice和Bob协商用同一个密码系统
  2. Alice和Bob协商用同一个密钥
  3. Alice用加密算法和选取的密钥加密她的明文消息,得到密文消息
  4. Alice发送密文消息给Bob
  5. Bob用同样的算法和密钥解密密文,然后读取

对称密码算法存在下面的问题:

  • 密钥必须秘密地分配
  • 如果密钥被泄露了(被偷窃、猜出、逼迫而出、受贿等),那么Eve就能用密钥去解密或假装为通信的一方。

单向函数

  • 单向函数(one-way function)
    是公开密钥密码的中心,本身不是一个协议,但却是一个基本结构模块。
    x容易求出f(x),但是f(x)却难求出x。
    “难”:世界上所有的计算机都用来计算,从f(x)求出x也需要数百万年的时间。
    “打碎盘子”就是单向函数,打碎简单,拼凑起来难。
  • 陷门单向函数(trapdoor one-way function)
    有一个秘密陷门的一类特殊单向函数。他在一个方向上易于计算而反方向难,但如果知道秘密,则很容易计算。
    拆开表是一个很好的陷门单向函数的例子。把表拆成数百片小片很容易,但组装却很难。然而只要有秘密消息(表的装配指令),就很容易还原。

单向散列函数

  • 散列函数(hash function)
    把可变长度输入串(预映射,pre-image)转换成固定长度(经常更短)输出串(散列值, hash value)的一种函数。
    散列函数不全是单向散列函数,因为有些散列函数很容易逆向求出pre-image。
    好的散列函数是无冲突的(collision-free):难以产生两个预映射的值,使他们的散列值相同。
    散列函数是公开的,处理过程不必保密。

  • 单向散列函数(one-way hash function)-- 压缩函数、收缩函数、消息摘要、指纹、密码校验和、信息完整性检验(Message Intergrity Check, MIC)、操作检验码(Manipulation Detection Code, MDC)。
    是现代密码学的中心。
    可以用来当做指纹,比如md5验证。

  • 消息鉴别码(Message Authentication Code,MAC),也叫数据鉴别码(DAC)
    注意跟“介质访问控制Media Access Control,MAC”的不同。
    带有秘密密钥的单向散列函数。散列值是预映射的值和密钥的函数即f(x,key)。

使用公开密钥密码系统通信

“对称算法课看成是保险柜??”

“1976年, Whitfield Diffie 和 Martin Hellman永远改变了密码学的范例(NSA宣称早在1966年就有了这种概念的知识,但没有提供证据),他们提出了公开密钥密码学(public-key cryptography)。他们使用两个不同的密钥,一个公开一个秘密,从公开密钥很难推出私人密钥。持有公开密钥的任何人都可加密消息,但却不能解密。
...
从数学上来说,这个过程相当于单向陷门函数。”

混合密码系统

之前看过一篇关于网络加密的帖子,里面举的例子很形象,公开密钥相当于一把锁,大家都可以用来锁东西,然后寄给拥有钥匙的人开锁。把随机会话密钥锁起来,传送给有钥匙的人解开,再用对称算法通信。这里一共提到三个密钥:公开密钥(锁)、私人密钥(钥匙)和会话密钥(通信用)

“在大多数实际的实现中,公开密钥密码用来保护和分发会话密钥(session key)。这些会话密钥用在对称算法中,对通信消息进行保密。有时称这种系统为混合密码系统(hybird cryptosystem)。

  • Bob将他的公开密钥发给Alice
  • Alice产生随机会话密钥K,用Bob的公开密钥加密,并把加密的密钥Eb(K)发送给Bob
  • Bob用他的私人密钥解密Alice的消息,恢复出会话密钥:Db(Eb(K))=K
  • 他们两人用同一个会话密钥对他们的通信信息进行加密

数字签名

  • 可信
  • 不可伪造
  • 不可重用
  • 不可改变
  • 不可抵赖

算法和术语

  • 数字签名(digital signature)
  • 签名(signature)
  • 鉴别(authentic)
  • 密钥鉴定机关(Key Certification Authority)
  • 密钥分配中心(Key Distribution Center, KDC)
  • 伪随机序列发生器(pseudo-random-sequence generator)

其他知识点

  • 使用公开密钥密码系统对文件签名
  • 文件签名和时间标记
  • 使用公开密钥密码系统和单向散列函数对文件签名
  • 多重签名
  • 抗抵赖(repudiation)和数字签名
  • 数字签名的应用:最早用来对“禁止核试验条约”的验证
  • 带加密的数字签名
  • 对公开密钥密码系统的攻击

逸事

Donald Knuth引用冯诺依曼的话:“任何人考虑用数学的方法产生随机数肯定是不合情理的”。
计算机中没有真正的随机数!
现在我们走进哲学家的领域,真有随机数这样的东西吗?随机序列是什么?如何知道序列是随机的?量子力学告诉我们,在现实世界中有真正的随机性,但是在计算机芯片和有限状态机的确定世界中,这种随机性还保持吗?

伪随机序列的性质:

  • 看起来是随机的:满足我们所能找到的所有随机性统计检验。
  • 不可预测的:密码学意义上安全的伪随机序列(cryptographically secure pseudo-random sequence)
  • 不能重复产生(真正的随机 real random)

满足以上三条性质的发生器的输出,对于一次一密乱码本、密钥产生和任何其他需要真正的随机数序列发生器的密码应用来说都是足够好的。难点在于确定真正的随机数。

懒得写了,下面直接记录最重要的东西:我的问题

问题

  1. Merkle难题 这个看不懂,有空回来找资料看看。
  2. 数字签名树是啥?也是Palph Merkle提出的,这家伙很烦。