第1章 标识密码学介绍
1.1 标识密码的起源
密码学 (Cryptography) 一词源自希腊语“Krypt′os Graphein”(隐藏的书写).用于信息秘密传递的密码技术在人类历史特别是战争中发挥着举足轻重的作用.早期历史上， *著名的密码是凯撒密码. 公元前 1 世纪， 凯撒使用密码技术来隐藏传递命令. 凯撒密码仅是将字母表中的每个字母使用循环右移三个位置的字母来代替， 例如字母 A 变为 D， 消息 CHARGE 变为 FKDUJH. 原消息称为明文 P，变换过程称为加密 Enc， 变换后的新消息称为密文 C. 循环右移的位数称为密钥K. 从密文还原消息的过程称为解密 Dec.
可以看到凯撒密码非常简单， 容易破解. 后来人们设计了一些更加高级的加密技术. 在第二次世界大战中， 德国使用著名的恩尼格玛机进行消息加密. 当要加密一串字符时， 操作员在机器下方的键盘上输入明文字符串. 每按下一个字母， 键盘上方背光字母盘上的一个字母就会亮起来. 这就是机器所生成的密文. 要解密消息时， 只需在键盘上输入密文字符串， 从背光字母盘顺序读取亮起的各个字母作为明文. 明密文之间的对应关系由机器中三个转子来控制. 每个转子有 26 格，每按下键盘上的一个字母， *右边转子会转动一格. 一个转子转完一整圈后， 将带动其左边的转子转动一格. 每个转子的初始位置可以调整. 两个地方使用恩尼格玛机实现正常通信需要两台机器按照预先分发到两地的密钥来设置齿轮初始位置. 两地使用相同的密钥进行加密和解密. 这种密码机制称为对称密钥机制.
对称密码机制的密钥需要周期性地更新. 在战争中实现多地之间安全地分发对称密钥是一个巨大挑战， 经常出现密码本被拦截的情况. 即使加密机制是安全的， 密钥泄露仍然会导致加密消息的泄露. 在 1976 年， Diffie 和 Hellman[1] 发表了具有里程碑意义的论文《密码学的新方向》， 提出公钥密码的概念. 在公钥密钥系统中， 用户有一对密钥: 一个是公开的密钥， 称为公钥; 另一个是仅由用户掌握的密钥， 称为私钥. 从用户的公钥难以计算出对应的私钥. 消息发送方使用接收方的公钥加密消息获得密文， 接收方使用其私钥解密密文获得明文. 在这种系统中， 用户的私钥不需要进行远程传递， 因此泄露的风险大大降低， 而用户的公钥是公开的， 不必担心泄露的风险. 显然我们可以使用公钥机制来安全地分发对称密钥. 除了实现基于公钥密码的密钥分发外， Diffie 和 Hellman 在 [1] 中同时提出数字签名的概念. 数字签名技术实现类似于手写签名或者印章的功能， 即实现对数字文档的数字签名. 签名人使用其私钥对数字内容生成数字签名， 验证人使用签名人的公钥验证对数字内容的数字签名的有效性. 在 1978 年， Rivest， Shamir 和Adleman[2] 发表著名的 RSA 公钥算法， 实现了 Diffie 和 Hellman 提出的两个重要公钥密码机制: 公钥加密和数字签名.
公钥密码机制可以有效降低对称密钥管理的复杂性， 但是该机制也带来了新的问题: 如何安全有效地对公钥进行管理? 公钥密码系统需要确保用户和其拥有的公钥之间的对应关系是真实的， 否则攻击者可以发起如图 1.1 所示的中间人攻击: 发送人 Alice 要加密消息给 Bob 时， *先需要通过某种方式获取 Bob 的公钥X. 中间人 Eve 在公钥传递的过程中使用其拥有的公钥 Y 代替 Bob 的公钥， 然后提供给 Alice. Alice 使用公钥 Y 加密消息 m 生成密文 CY ， 然后发送给 Bob. Eve拦截密文消息 CY ， 使用其私钥 y 解密密文还原消息 m， 再使用 X 加密 m 生**密文 CX 传递给 Bob. Bob 使用其私钥解密还原消息 m. 在整个过程中， Alice和 Bob 认为两者间的通信是安全的， 但是 Eve 可以获取两者间传递的所有秘密.类似地， 在数字签名应用中， Eve 使用其私钥签名， 但是通知验证人 Peter 其公钥Y 属于 Charlie. Peter 验证数字签名后， 误认为数字内容源自 Charlie.
图1.1 中间人攻击
公钥密码系统中用户与公钥对应关系真实性的问题大体上有如下几种解决方法.
. 公开目录: 目录管理者管理一个公开可访问目录. 用户在获得目录管理者授权后可以在目录中发布 (用户身份， 公钥) 信息. 其他用户在线访问该目录获得 (用户身份， 公钥) 目录项. 访问过程由目录管理者保证传递数据的真实性， 例如目录管理者可对在线传递的数据进行数字签名. 目录访问者需要利用安全机制验证获取数据的真实性. 这种方式需要公开目录总是在线， 并且数据传递过程需要安全机制保护.
. 权威机构颁发的数字证书: 用户的身份和公钥的对应关系由一张权威机构签发的数字证书证明. 证书权威机构 (CA: Certificate Authority) 是系统中受到各用户信任的机构. 用户向 CA 证明其身份并证明其拥有公钥对应的私钥后， CA 对包括用户身份、用户公钥、有效期等的数字内容进行数字签名， 生成包括被签名数据以及 CA 签名的数字证书. 证书查询用户获得某个数字证书后， *先验证 CA 签名的有效性. 如果查询用户信任 CA 并且签名有效且证书未过期、未被撤销， 则接受数字证书中用户身份和公钥的对应关系. 这类系统多是采用 X. 509 [3] 标准的公钥基础设施(PKI: Public Key Infrastructure). 系统中， 用户需要预先向 CA 申请数字证书， 数字证书需要通过某种分发机制进行分发. 如果私钥丢失， 用户需要向 CA 申请挂失数字证书， CA 需要提供能确定数字证书当前有效性的机制， 例如， 提供在线证书状态查询[4] 或者适时发布证书撤销列表 (CRL:Certificate Revocation List)[3].
. 信任网 (Web of Trust) 中的证书. 信任网[5] 中没有单一的权威机构， 用户的证书由其他用户签发. 证书查询用户获得某个证书后， 若信任证书签发者， 则接受证书; 否则需要找到足够多的部分信任的背书人对证书的真实性提供背书才接受证书. 由于系统没有一个权威机构， 新用户加入系统时很难快速找到足够多的背书人对其身份和公钥的真实性提供背书. 另外，用户需要撤销证书时， 需要发出公钥撤销证书.
在具有权威机构的公钥管理系统中， 公开目录机制需要目录管理系统实时在线; 数字证书机制需要用户预先申请证书， 消息加密方需要*先获取接收方的有效证书才能进行消息加密. 鉴于传统公钥系统中公钥管理的复杂性， Shamir[6] 在1984 年提出一种新的公钥密码机制: 基于身份的密码 (IBC: Identity-Based Cryptography). 基于身份的密码系统中， 用户的身份作为用户的公钥， 而身份对应的私钥由权威机构生成后分发给用户. 鉴于通信系统都需要指定通信双方的身份，采用通信方的身份标识作为公钥， 例如邮件系统中使用接收人邮件地址作为公钥，消息发送方可直接使用接收方的标识进行消息加密， 无须额外执行公钥查询过程，公钥管理的复杂性显著降低. 另外， 发送方可以先使用接收方身份标识进行消息加密， 根据需要， 接收方从权威机构获取与其身份对应的私钥后再解密密文. 因此，基于身份的密码系统中加密过程更加灵活. 实际上， 系统中任意具有唯一性的标识都可作为公钥使用， 比如， 医疗健康系统的患者身体检查数据的访问控制策略:“在 2022 年到 2023 年期间主治医生或化验师可读取” 就可作为患者体检数据的加密公钥. 因此， 本书将这类密码技术称为标识密码技术.
1.2 标识密码的发展历程
Shamir[6] 在 1984 提出基于身份的密码的概念， 同时基于 RSA 问题构造了**个标识签名算法 (IBS: Identity-Based Signature). Okamoto[7] 在 1987 年采用类似于 [6] 中的密钥生成方法构造了**个标识密钥协商协议 (IBKA: Identity-Based Key Agreement). 但是标识加密算法的构造经过 15 年时间都没有实现. 直到 2000 年， Sakai， Ohgishi 和 Kasahara[8] 使用椭圆*线上的双线性对构造了一个标识密钥生成算法并以此提出了一个非交互的标识密钥协商协议. 此协议经过简单变换就可实现标识加密算法 (IBE: Identity-Based Encryption). 在 2001 年，Cocks[9] 基于平方剩余问题构造了按比特加密消息的标识加密算法， 同年， Boneh和 Franklin[10] 基于双线性对构造了标识加密算法 BF-IBE. Boneh 和 Franklin 的工作产生了巨大的影响. 普遍认为， BF-IBE 和 Joux 在 2000 年发表的基于双线性对的单轮三方密钥协商协议 [11] 一起开启了基于双线性对的密码研究. 标识密码学是双线性对密码研究的主要组成部分.
标识密码学的内容异常丰富. 研究人员利用双线性对的强大能力构造了众多使用大数分解、离散对数等传统复杂性假设， 难以实现的密码系统. 除了通常的基于标识的加密、签名、密钥交换协议等方面的研究以外， 标识密码学还包括标识 加密机制的进一步推广， 如基于属性的加密[12]、广播加密[13]、函数加密[14] 等; 各类密钥管理扩展， 如分层标识密码系统[15]、可撤销标识密码系统[16]、门限标识密码系统[17]、主密钥的分布式生成[18]、代理重加密系统[19] 等; 双线性对相关的基础数学理论研究， 如双线性对友好*线的构造[20]、双线性对问题的计算复杂性[21]、双线性对的高效实现[22] 等， 以及更多内容. 鉴于标识密码学的内容如此广泛并且许多新研究不断发展深入， 本书仅撷取部分基础内容与读者分享. 图 1.2 展示了本书关于标识密码学的主要内容.
图 1.2 本书主要技术内容
参考文献
[1] Diffie W， Hellman M. New directions in cryptography. IEEE Tran. on Information Theory， 1976， 22 (6): 644-654.
[2] Rivest R， Shamir A， Adleman L. A method for obtaining digital signatures and publickey cryptosystems. Communications of the ACM， 1978， 21 (2): 120-126.
[3] IETF. RFC 5280: Internet X.509 public key infrastructure certificate and certificate revocation list (CRL) profile. 2008.
[4] IETF. RFC 2560: X.509 internet public key infrastructure online certificate status protocol - OCSP. 1999.
[5] Ulrich A， Holz R， Hauck P， et al. Investigating the OpenPGP web of trust. ESORICS 2011， LNCS 6879: 489-507.
[6] Shamir A. Identity-ba
展开
