信息安全技术丛书：实用化的签密技术

序
序（英文版）
前言（英文版）
第1章 引言
1.1 签密的历史发展
1.1.1 编码调制
1.1.2 对混合方法的思考
1.1.3 签密
1.1.4 可证明安全签密
1.2 扩展、标准化及其未来的研究方向
1.3 符号和安全性的概念
1.3.1 算法和赋值
1.3.2 数字签名方案
1.3.3 公钥加密
1.3.4 对称加密
1.3.5 消息认证码

第Ⅰ部分签密的安全模型
第2章 签密的安全性：双用户模型
2.1 简介
2.2 双用户场合下签密的定义
2.2.1 双用户场合下的两个安全性概念
2.2.2 对安全性概念的讨论
2.3 签名和加密的通用构造方法
2.3.1 构造
2.3.2 并行组合方式的安全性
2.3.3 顺序组合方式的安全性
2.4 多用户环境
2.4.1 语法环境
2.4.2 安全性
2.4.3 签密的扩展
第3章 签密的安全性：多用户模型
3.1 引言
3.2 BSZ模型
3.2.1 多用户BSZ模型中签密的机密性
3.2.2 多用户BSZ模型下签密的不可伪造性
3.2.3 多用户BSZ模型的进一步讨论
3.3 举例：Zheng的签密方案在BSZ模型下的安全性

第Ⅱ部分签密方案
第4章 基于Diffie-Hellman问题的签密方案
4.1 简介
4.2 Diffie-Hellman问题
4.3 Zheng方案及其变形
4.3.1 Zheng的原始方案
4.3.2 Bao-Deng的修改方案
4.3.3 具有公开可验证性的改进方案
4.4 先加密后签名的组合方案
4.5 基于大整数分解的抗伪造方案
4.6 具有抗否认性的方案
4.6.1 基于DSA的构造
4.6.2 基于Schnorr签名方案的构造
4.7 CM方案
第5章 基于双线性映射的签密方案
5.1 简介
5.2 双线性映射群
5.3 假设
5.4 用于匿名通信的签密方案
5.4.1 消息保密性
5.4.2 密文抗伪造性与签名抗伪造性
5.4.3 匿名性
5.5 紧致安全的方案
5.5.1 方案
5.5.2 效率
5.5.3 安全性
5.6 具有短的可分签名的方案
5.6.1 效率
5.6.2 匿名通信
5.6.3 安全性
第6章 基于RSA问题的签密方案
6.1 简介
6.2 RSA变换
6.3 基于RSA的专用签密方案
6.4 由填充方案构造的签密方案
6.4.1 陷门置换
6.4.2 可提取的承诺
6.4.3 基于填充的签密方案
6.4.4 直观证明
6.5 基于RSA-TBOS的签密
6.5.1 TBOS构造
6.5.2 TBOS签密方案的安全性证明

第Ⅲ部分构造技术
第7章 混合签密
7.1 背景知识
7.1.1 符号说明
7.2 预备知识
7.2.1 混合框架
7.2.2 数据封装机制的安全性准则
7.3 具有外部安全性的混合签密
7.3.1 一个外部安全的签密KEM
7.3.2 外部安全签密KEM的安全标准
7.3.3 SKEM+DEM构造的安全性
7.3.4 实用的外部安全混合签密
7.4 具有内部安全性的混合签密
7.4.1 从外部安全性到内部安全性
7.4.2 签密标签KEM
7.4.3 签密标签KEM的安全标准
7.4.4 SCTK+DEM构造的安全性
7.4.5 实用的内部安全混合签密
第8章 隐藏及其在认证加密中的应用
8.1 引言
8.1.1 认证加密的范畴扩展
8.1.2 远程密钥认证加密
8.2 隐藏的定义
8.2.1 句法上的定义
8.2.2 隐藏的安全性
8.2.3 松散隐藏
8.2.4 超松散隐藏
8.2.5 隐藏与承诺的比较
8.3 隐藏方案的构造
8.3.1 如何实现隐藏
8.3.2 如何实现绑定
8.3.3 假设的必要性
8.4 隐藏在认证加密中的应用
8.4.1 认证加密的定义
8.4.2 对长消息的认证加密
8.4.3 远程密钥认证加密
第9章 并行签密
9.1 引言
9.2 并行签密的定义
9.3 构造方法概述
9.4 通用并行签密
9.4.1 方案描述
9.4.2 安全性分析
9.5 最优的并行签密
9.5.1 方案描述
9.5.2 安全性分析

第Ⅳ部分签密的扩展
第10章 基于身份的签密
10.1 引言
10.1.1 基于身份密码体制
10.1.2 优势与劣势分析
10.1.3 从IBE到签密
10.1.4 IBSC系统的具体说明
10.1.5 基于对的具体IBSC
10.2 基于身份的签密模型
10.3 安全性定义
10.3.1 消息的机密性
10.3.2 签名的不可否认性
10.3.3 密文不可链接性
10.3.4 密文正确性
10.3.5 密文匿名性
10.4 具体的IBSC方案
10.4.1 Boneh-Franklin结构
10.4.2 全安全的IBSC构造
10.4.3 效率与安全性的转换
10.4.4 多接收方的签密
第11章 利用签密技术建立密钥
11.1 引言
11.2 密钥建立的形式化安全模型
11.2.1 动机
11.2.2 会话
11.2.3 形式化安全模型
11.2.4 实体认证
11.2.5 前向安全性
11.2.6 密钥损害模拟攻击
11.2.7 标号
11.3 密钥传输
11.4 基于Zheng的签密方案的密钥建立协议
11.5 基于签密密钥封装机制的密钥协商协议
11.5.1 基于签密KEMs的密钥协商协议
11.5.2 基于签密Tag-KEMs的密钥协商协议
11.5.3 Bj?rstad-Dent协议的安全性证明
11.6 基于时间戳的密钥建立协议
第12章 签密的应用
12.1 签密应用的领域
12.2 签密应用的例子
12.2.1 互联网中的安全组播
12.2.2 认证密钥恢复
12.2.3 安全ATM网
12.2.4 移动自组网中的安全路由
12.2.5 防火墙加密和认证邮件
12.2.6 安全VoIP中的签密应用
12.2.7 电子支付中签密的应用
参考文献
跋

　　第1章引言
　　YuliangZheng
　　1.1签密的历史发展
　　1.1.1编码调制
　　在一个典型的通信系统中，数据从发送者发出，在传输到既定的接收者之前要经过一系列变换。这些变换可能包括用来压缩数据或去除冗余信息的信源编码、确保检测非授权篡改的认证，阻止数据在路由过程中被非授权访问的加密、使接收者能够检测和纠正传输错误的纠错编码，最后是对在发送方和接收方之间的信道上传输的信号进行调制。一般情况下，通信信道不仅容易产生传输错误，而且还是不安全的。数据在到达接收方后，将以相反的顺序进行解码变换。图1.1描述了数据在信道中传输时所要进行的各种操作。注意认证在加密之前进行。反过来，也可以先加密再认证。
　　图1.1通信系统
　　作为数字通信工程的核心，纠错编码和调制技术从20世纪中叶就开始引起人们关注并对其进行研究。由于典型的通信信道只有有限的带宽，一个重要问题是如何使由纠错编码所导致的有效数据传输率的损失最小化。另一个重要问题是如何充分发挥多电平/相位调制带来的数据传输率增长的效益，而不加剧信号间的干扰。然而，尽管在第二次世界大战后伴随着数字通信的发展，出现了大量的纠错编码和调制技术，但历史上纠错和调制一直都是分开进行的。
　　20世纪70年代，为了获得良好的性能，且不会带来带宽的膨胀或显著降低数据传输率，研究者着手寻求将纠错和调制相结合的技术。这些尝试中最成功的代表是Ungerboeck[190–193]，以及Imai和Hirakawa[97，197]各自独立的工作。Ungerboeck的工作侧重于将网格编码或卷积码和多电平调制融为一体而不牺牲带宽效率。Imai和Hirakawa的目标相同，但使用了与Ungerboeck不同的方法，他们结合了分组纠错码和多电平调制。编码调制同时解决了两个看似互相矛盾的问题：①高的传输可靠性；②高的传输效率。这些混合技术，无论基于网格编码还是分组纠错码，都使得可靠且带宽高效的数据传输成为现实（图1.2）。
　　图1.2带宽高效通信中的编码调制
　　1.1.2对混合方法的思考
　　20世纪80年代，对于在电信领域工作的人是一个令人兴奋的时期。当时，Imai在日本横滨国立大学主持了大量的研究项目。这些项目几乎涵盖有关数据处理和通信的所有重要方面。具体而言，研究项目涉及信源编码、加密、纠错编码、调制和编码调制。
　　20世纪80年代中期，我加入了Imai的团队来完成研究生学习。虽然我的研究领域为密码学，但很幸运能够参与每周的研讨会，与工作在一系列不同研究项目的同学讨论。我至今仍清晰地记得，在一个一直持续到深夜的研讨会上，经过了一整天的研究和讨论后，当我觉得有点累时，一个同学开始解释Imai-Hirakawa多电平编码调制技术[97]。我立刻被一种奇妙的想法吸引，即将纠错编码和调制混合在一起比独立使用效果更好。在接下来的几年中，我对编码调制保持了浓厚的兴趣。觉得最迷人的不仅是技术背后的漂亮思想，还有该技术的逐步完善、标准化，并得到实际应用的惊人速度。
　　作为一个见证了编码调制技术的快速成熟及其在数字通信中应用的密码学研究者，我很自然地问自己：“将两种密码学原语结合成一种比独立使用它们更高效的新事物是否可行”。这个问题在我研究生学习的剩余阶段一直伴随着我。数年后，我完成了博士学业并移居澳大利亚后发现很难彻底摆脱对这一问题的思索。
　　现代密码技术两个最重要的功能是确保数据的机密性和完整性。机密性可以采用加密算法来获得，而完整性可由认证技术提供。
　　加密算法可以分为两大类：私钥加密和公钥加密。同样地，认证技术也可分为私钥认证算法和公钥数字签名。当评估一个加密算法时，不仅需要考虑算法能够提供的安全强度或水平，同时还要考虑该算法在执行时所需要的计算时间，以及所产生的消息扩展。当两种加密算法提供了相似的安全级别时，计算时间和消息扩展成为其比较时关注的焦点。作为一项原则，通常认为具有较小计算时间和更短消息扩展的方案是更理想的。
　　私钥加密和私钥认证都非常快，消息扩展也很小，而公钥加密和数字签名通常需要大量的计算，如涉及大整数的幂，同时消息扩展与安全参数（如一个大合数或大有限域的规模）成正比。图1.3说明了对消息依次使用数字签名和公钥加密时的计算和消息扩展开销。
　　图1.3公钥加密中的数字签名
　　我意识到，至少有两种组合在实践中是有意义的：
　　（1）私钥加密结合私钥认证；
　　（2）公钥加密结合数字签名。
　　我也意识到，将两个不同加密算法成功地结合，最重要的目标应该是，得到的结果相比独立使用两个原始算法，不仅能更快速地计算，也要有更短的消息扩展。
　　将目光锁定在第二类型的组合上，即公钥加密与数字签名的组合，原因如下。
　　（1）将来广泛使用电池供电的小型设备，如智能卡、智能电话、个人数字助理（PDA）、电子护照、电子钱包和其他类型的小工具，需要的新型公钥加密技术要求电池电量消耗尽可能少。
　　（2）在资源受限的环境中，如非接触无线识别令牌和无人值守的远程数据采集系统，需要使用不仅可以快速计算，而且引入数据扩展也最少的公钥加密算法。
　　（3）寻求组合的公钥加密解决方案似乎更具挑战性。
　　（4）我认为自己在对选择密文攻击[210，211]“免疫”的公钥加密设计技术方面的经验，可以用于应对这个新挑战。这些“免疫”技术的本质是使用认证标签，尤其是那些由（有密钥控制的）单向散列算法产生的标签。在进行公钥加密之前，可以利用这些标签将非结构化的明文转换为高度结构化的明文。这种转换能够挫败在不知道相应明文的情况下试图创建一个新密文的选择密文攻击者。这些想法后来由其他研究人员阐述为“随机预言机”模型和明文可意识性，并构成了公钥密码可证明安全性的重要基础。
　　1.1.3签密
　　在设定了将公钥加密与数字签名相结合的目标之后，我将待选算法限定到ElGamal公钥加密和签名，尤其是那些安全性依赖大有限域的子群上离散对数困难性的算法，因为其具有出色的效率，并存在有效的椭圆曲线上实现的版本。
　　1．子群上的ElGamal公钥加密和签名
　　我所感兴趣的ElGamal公钥加密和数字签名版本，使用了三个公开参数：
　　（1）p：大素数；
　　（2）q：的一个素因子；
　　（3）g：中阶为qmodp的一个整数。
　　例如，有两个用户Alice和Bob，Alice拥有从中随机选择的私钥xa，相应的公钥是。类似地，Bob的私钥xb是从中随机选择的整数，对应的公钥是。
　　现假定Alice想安全地给Bob发送消息m。Alice首先从公钥目录中查找Bob的公钥yb。然后从中选择一个随机整数x，并计算。然后，针对一个适当的私钥密码方案，利用单向散列函数hash计算加密密钥。最后，Alice将如下的一对数据作为m的密文发送给Bob。
　　式中，E为私钥密码方案中的加密算法。
　　当收到后，Bob能够通过计算恢复k。然后利用k和同一私钥密码方案中的解密算法D解密c2并获得m。
　　Alice对消息m的签名包括两个数：r和s，定义为
　　式中，x为从]中随机选择的整数，hash是一个合适的单向散列函数。Bob和其他任何人能够使用Alice的有效公钥ya来验证其对消息m的签名的认证性。
　　针对原始ElGamal签名存在大量的变形和改进。最值得注意的包括NIST数字签名标准（digitalsignaturestandard，DSS）或称为数字签名算法（digitalsignaturealgorithm，DSA）[149]，以及Schnorr签名[173]。这两种签名技术定义为
　　通过对DSS进行变形作进一步缩短，可以得到两个更有意思的变形。这两个缩短版本称为SDSS1和SDSS2，定义为
　　2．基本签密算法
　　仔细观察ElGamal加密和签名算法，会发现它们都包括如下元素
　　gxmodp
　　这个值在两个算法中起着“临时密钥”的作用。一个有趣的问题是，“有没有可能将‘临时密钥’作为连接加密算法和签名算法的渠道”。
　　而且，还注意到gxmodp并没有显式地出现在任意一个上述四种ElGamal签名的变形中。但是，这个值又可以很容易地由签名验证者从签名中计算出来。所有这四种变形均具有比原始ElGamal签名更短的签名长度。这带来了另一个有趣的问题，那就是“是否有可能以这样一种方式结合ElGamal加密和签名，所得到的算法中不包含gxmodp”。
　　经过大量的试验和失败之后，1996年冬天，在南方工作的我更加坚定了自己的想法。得到的结果是对ElGamal加密和签名的精密结合，称为“签密”，从而肯定地回答了上述两个问题。后面使用SDSS1来解释这种结合。在后面描述的签密技术中，使用hash表示一种单向散列算法，KH表示一个有密钥控制的单向散列算法，表示一种私钥密码方案。
　　基本算法
　　发送者Alice对消息m签密
　　①从中随机、均匀地选择x，令，将k分成长度合适的k1和k2。
　　②。
　　③。
　　④。
　　输出为发送给Bob的签密文。 基本算法
　　接收者Bob对签密文的解签密
　　①利用通过计算恢复出k。
　　②将k分成k1和k2。
　　③。
　　④只有当时，才输出m，作为Alice发出的合法消息，否则拒绝接收。
　　尽管研究论文一年以后才发表于1997年的Crypto[203，204]，但这个技术首先在1996年10月的专利申请[207]中进行了详细描述。
　　1.1.4可证明安全签密
　　上面所讨论的基本签密算法发表之后，寻找对于算法的机密性和不可伪造性的形式化证明成为下一个挑战。我很幸运，1999年秋天，作为一名博士研究生，RonSteinfeld加入了我在Monash大学的实验室。Ron接受了我的建议来寻找签密安全性的形式化证明。我们很快就意识到确定一个合适的签密安全模型是最重要的。1999年底，我们朝这个方向迈出了第一步：形式化地证明了一个安全性基于因子分解的签密算法的不可伪造性。结果发表于ISW2000[184]，而该签密算法的机密性证明成为一个公开问题。
　　2000年初，迎来了JoonsangBaek加入我的实验室攻读博士研究生学位。Joonsang来后不久，就和Ron还有我一起开始研究签密的安全性证明。我们的合作研究成果极为丰硕，构造了多用户环境中签密的强安全模型，并在该模型下对签密的不可伪造性和机密性给出了形式化证明[12，13]。
　　独立于实验室的工作，An、Dodis和Rabin在双用户环境中成功获得了对结合公钥加密和数字签名的一大类方案的安全性证明[10]。这些结果与多用户环境中的研究结果互为补充，向着可证明安全的签密方案的设计迈出了重要一步。
　　原始的签密算法为了从数学上严谨地证明安全性，需要进行一些优化[12，13]。优化算法采用两个独立的单向散列算法G和H，前者用于生成私钥加密算法的密钥，而后者则用于计算r的值。并且，Alice和Bob的公钥都参与了r的散列计算，据此将密文绑定到Alice和Bob，消除了不诚实的Alice或Bob滥用的可能性。
　　可证明安全的算法
　　发送者Alice对消息m签密
　　①从中随机、均匀地选择x。
　　②。
　　③。
　　④。
　　⑤。
　　⑥如果，则返回到①，否则令。
　　⑦输出作为发送给Bob的签密文。 可证明安全的算法
　　接收者Bob对签密文解签密
　　①。
　　②。
　　③。
　　④仅当时，输出m，作为由Alice发出的合法消息，否则拒绝接收。