密码学 教师 孙达志 联系方式 sundazhi@tju.edu.cn 教学网页 成绩评定(暂定) 考试: 90%; 平时: 10% http://202.113.2.12/faculty/sundazhi/Class-Crypto-CS2016.htm 成绩评定(暂定) 考试: 90%; 平时: 10%

参考书 [1] Wade Trappe, Lawrence C. Washington, Introduction to cryptography with coding theory, Prentice-Hall, 2002 [2] Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, Handbook of applied cryptography, CRC Press, 1997

第一讲 现代密码学概论

现代密码学的里程碑事件 1976年，Diffie和Hellman提出了适应网络上保密通信的公钥密码思想，以及不久之后的RSA公钥密码算法，奠定了公钥密码学的基础。 1977年，美国国家标准局正式公布实施美国的数据加密标准(DES)公开它的加密算法，并批准用于非机密单位及商业上的保密通信。

本讲提要 密码系统 对称与非对称密码思想 现代密码学的基本目标 现代密码学的基本概念和技术 评估安全的模型

1 安全系统 1.1 Shannon保密系统 发送者 Alice 密钥源 分析者 Eve 接收者 Bob 安全信道 公共信道 加密器Ek 解密器Dk 明文m 密文c 密钥k

1.1.1 通信中的参与者 发送者(Alice)：在双方交互中合法的信息发送实体。 接收者(Bob)：在双方交互中合法的信息接收实体。 分析者(Eve)：破坏通信接收和发送双方正常安全通信的其它实体。 1.1.2 信道 信道：从一个实体向另一个实体传递信息的通路。 安全信道：分析者没有能力对其上的信息进行阅读、删除、修改、添加的信道。 公共信道：分析者可以任意对其上的信息进行阅读、删除、修改、添加的信道。 1.1.3 分析者的目的 解读公共信道上的密文消息。 (被动) 确定密钥以解读所有用该密钥加密的密文消息。 (被动) 变更密文消息已使接受者(Bob)认为变更消息来自发送者(Alice)。 (主动) 冒充密文消息发送者(Alice)与接收者(Bob)通信，以使接受者(Bob)相信消息来自真实的发送者(Alice)。(主动)

1.2 常见的攻击形式 1.3 Kerckhoffs准则 唯密文攻击：分析者仅仅掌握密文。 已知明文攻击：分析者掌握密文以及其对应的明文。 选择明文攻击：分析者可以临时访问加密机，可以用自己选择的明文加密，但不能直接要求输出密钥。 选择密文攻击：分析者可以临时访问解密机，可以解密一些自己想得到的符号串。 1.3 Kerckhoffs准则 在评估一个密码系统安全性时，应该总是假定我们的 敌人了解实际使用的各种方法。 # 落实到现代密码算法中就是攻击者知道密码算法的所有执行细节，算法的安全不应该依赖于对算法的保密。

2 私钥密码VS公钥密码思想 2.1 私钥密码体制 # 加密密钥与解密密钥同：K1=K2 代表系统：DES和AES 加密器 EK1(m)=c 分析者 Eve 解密器 DK2(c)= m 明文消息源 目的地 m c 公共信道 Alice Bob # 加密密钥与解密密钥同：K1=K2 代表系统：DES和AES

2.2 私钥密码在网络环境下遇到的挑战：密钥 产生与管理问题 若互联网上有n个用户，则需要 个密钥，若n=1000，则NK500 000。 # 如此众多的密钥如何建立，如何保存？

2.3 公钥密码体制 # 加密密钥与解密密钥不同：K1K2 代表系统：RSA和ElGamal 加密器 EK1(m)=c 分析者 Eve 解密器 DK2(c)= m 明文消息源 目的地 m c 公共信道 Alice Bob # 加密密钥与解密密钥不同：K1K2 代表系统：RSA和ElGamal

2.4 密码体制的演进及目前的状态 #公钥密码体制以其强大的功能使得私钥密码体制显得已经过时，但是强大的功能不是无代价获得的，公钥密码的计算量远大于同情况下的私钥密码，因此，不适合加密大量数据，只适合于完成少量数据加密，如传送私钥密码算法的密钥、签名等等。 安全依赖于保密加密方法 安全依赖于保密密钥 安全依赖于保密部分密钥 古典密码 私钥密码 公钥密码

3 现代密码学解决的基本安全问题 机密问题。这指的是除了信息的授权人可以拥有信息以外，其他人都不可获得信息内容。在密码学中，主要是通过加密和解密算法来完成这项任务。 数据真实完整问题。这一问题的提出是为了发现对数据的非法变更。为了做到这一点，必须提供发现非授权人对数据变动的机制。许多密码工具可以提供这一机制，如Hash函数等。

认证问题。这是一个与识别相关的问题，可以应用于实体也可以应用于信息本身。两方在进行通信之前，一般需要识别对方的身份。而在信道上传输的一条信息也需要识别它是何时、何地、何内容由何人发出。因此，认证在密码学中常常被分成两类：实体认证和数据源认证。可以看出数据源认证隐含了提供数据真实性服务，这是因为数据被修改，数据源也就自然发生了变更。

不可否认问题。这一问题的提出是为了阻止实体否认从前的承诺或行为。争议的发生常常是由于实体否认从前的某个行为。例如，一个实体与另一个实体签署了购买合同，但事后又否认签署过，这时常常需要一个可信第三方来解决争议。这就需要提供必要的手段来解决争议。在密码学中，解决这一问题的手段常常是数字签名。

4 现代密码学的基本概念和技术 4.1 单向函数和陷门单向函数 单向函数 定义 1 一个定义域为X值域为Y的函数y=f(x)称之为单向函数：如果对于所有x X计算f(x)都是“容易的”，而对于“基本上所有yY”发现任意一个xX满足f(x)=y都是“计算不可能的”。

x f(x) Hard Easy 实例： 大整数分解问题 离散对数问题 背包问题

陷门单向函数 定义 2 一个陷门单向函数是单向函y=f(x)再附加一个特性，即如果给定一些附加信息称之为陷门信息K，那么，就对任意yY求解xX满足fK(x)=y都变得“容易了”。

4.2 加密 4.2.1 加密基本术语 明文消息空间M: 某个字母表集 密文消息空间C: 可能的密文消息集 加/解密密钥空间K: 可能的加/解密密钥集 加/解密函数EeK(mM)/DdK(cC) : 一个从M到C/C到M的有效变换

4.2.2 加密方案 加密方案是由一个加密函数集{Ee: eK}和解密函数集{Dd: dK}构成，并且满足任意一个加密密钥eK存在唯一一个解密密钥dK使 Dd=Ee-1，也就是对于所有明文消息mM ，存在Dd(Ee(m)) = m，(e, d)称为密钥对。设计加密方案就是确定M、 C、 K、{Ee: eK}、{Dd:dK}的过程。 定义 3 一个加密方案可以被破译是指，第三方在没有事先得到密钥对(e, d)的情况下，可以在适当的时间里系统的从密文恢复出相对应的明文。 # 适当的时间是由被保护数据生命周期来确定。

4.2.3 私钥加密 定义 4 一个由加密函数集{Ee: eK}和解密函数集{Dd: dK}组成加密方案，每一个相关联的密钥对(e, d) ，如果知道了e在计算上很容易确定d，知道了d在计算上很容易确定e，那么，就是私钥加密方案。 # 私钥加密需要一条安全信道来建立密钥对。

主要技术：分组密码与流密码 定义 5(分组密码) 将明文消息在编码集按照固定长度t进行分组，再一组一组的加\解密明\密文消息。 #著名的DES、AES都是这类密码。 定义 6 令K 是加密变换集的密钥空间，序列 e1e2…eiK称为密钥流。 定义 7(流密码) 消息m以串的形式(m1m2…mi)给出，密钥e1e2…ei是K上的密钥流。流密码通过ci=Eei(mi)给出密文消息(c1c2…ci)；如果di为ei的逆，解密则通过mi=Ddi(ci)完成。

4.2.4 公钥加密 定义 8 一个由加密函数集{Ee: eK}和解密函数集{Dd: dK}组成加密方案，每一个相关关联的加/解密密钥对(e, d)，加密密钥e公开，称为公开密钥，而解密密钥d保密，称为秘密密钥。 # 显然安全公钥密码系统要求从e计算d为不可能。

公钥加密实例 # 因为存在替代攻击问题，公钥系统中公开密钥e 必须认证，一般是建立PKI。 Ee(m1)=c1 Dd(c1)=m1 A1 Ee(m2)=c2 A2 Ee(m3)=c3 A3 Dd(c1)=m1 Dd(c2)=m2 Dd(c3)=m3 Bob e c1 c2 c3 # 因为存在替代攻击问题，公钥系统中公开密钥e 必须认证，一般是建立PKI。

4.2.5 对加密方案的攻击方法 唯密文攻击 已知明文攻击 选择明文攻击 适应性选择明文攻击 选择密文攻击 适应性选择密文攻击

4.3 数字签名技术 4.3.1 签名的基本术语 明文消息空间M:某个字母表中串的集合 签名空间S:可能的签名集合 签名密钥空间K:用于生成签名的可能密钥集，具体取值k需要保密 验证密钥空间K’:用于验证签名的可能密钥集，具体取值k’需要公开 签名函数SK(mM):从M到S的有效变换 验证函数VK’(mM, s):一个从MS到输出{True, False}的有效变换

4.3.2 签名过程 签名过程(签名者完成) (1) 对一条需要签名的消息mM计算签名s=Sk(m)。 验证过程(验证者完成) (1) 得到对应签名者的验证算法Vk’ ，计算u=Vk’ (m, s)。 (2) 如果u=True，接受签名；如果u=False，拒绝签名。

4.3.3 签名和认证函数必须满足的性质 4.3.4 数字签名的争议解决（不可否认） (1) 当且仅当Vk’ (m, s)=True时，s是对消息m的合法签名。 (2) 对于任何签名者以外的实体得到任意的一组mf和sf满足Vk’ (mf , sf)=True是计算不可能的。 4.3.4 数字签名的争议解决（不可否认） 如果签名者和验证者对签名发生争议，可由验证者带签名(m, s)提交给可信任第三方(TTP)，由TTP验证该签名，最后进行仲裁。

定义 9 对于满足Dd(Ee(m))=Ee(Dd(m))=m和M=C的公钥加密算法，称为可逆公钥密码算法。 4.3.5 数字签名与公钥加密的关系 定义 9 对于满足Dd(Ee(m))=Ee(Dd(m))=m和M=C的公钥加密算法，称为可逆公钥密码算法。 # 只有在M=C的情况下对于所有的mM变换等式都成立。 可逆公钥密码算法可以直接构造数字签名如下： (1) 加密的C 就是签名的M。 (2) 加密的M就是签名的S 。 (3) 签名函数Sk定义为Dd ，也就是s=Dd(m)。 (4) 当Ee(s)=m，认证函数Vk’ (m, s)=True；其它情况，Vk’ (m, s)=False。

4.4 密钥管理模式 4.4.1 私钥管理模式 # TTP负荷大(在线、交互、存储密钥)，权限高 密钥 源 TTP A1 A2 k1 k2 Ek1(k) Ek(m) Ek5(k) # TTP负荷大(在线、交互、存储密钥)，权限高

4.4.2 公钥管理模式 # TTP负荷小(离线、非交互、存储证书)，权限低 认证 VT(A6 || e6 , s6) 秘密密钥 d6 A2, e2, ST(A2 || e2)=s2 A3, e3, ST(A3 || e3)=s3 A4, e4, ST(A4 || e4)=s4 e6, s6 Dd6(c)=m c = Ee6(m) Public file A1, e1, ST(A1 || e1)=s1 A5, e5, ST(A5 || e5)=s5 A6, e6, ST(A6 || e6)=s6 # TTP负荷小(离线、非交互、存储证书)，权限低

4.5 认证与鉴别技术 4.5.1 鉴别或实体认证 定义 10 鉴别或实体认证是一个过程。在这个过程中一方通过获得一些确定的证据来确认参加实体认证的另一方的身份，而具有相应身份的实体也确实就是正在参与这一认证过程的另一方。

例子1 实体A与B通电话，如果A与B认识就可以通过声音来确定对方的真实性。 例子2 实体A通过信用卡在银行ATM机上取钱。 # 特点：时实性。

直观安全目标： a 在宣称者A和验证者B都诚实的执行认证时，A 能向B成功的证明自己，也就是B将完成执行并接 受A所宣称的身份。 b (不可转移性)验证者B不能从与宣称者A交互中 获得的信息，成功地向第三方C来冒充A 。 c (不可冒充性)任何一个非宣称者A的C想通过扮 演A的身份，通过验证者B的认证让B接受A的身 份的可能性可以忽略。这里，可以忽略的含义是 概率小到没有具体的实际意义，准确的度量需要 根据实际应用而定。

d 即使如下情况存在，以上三个条件仍然成立。 d.1宣称者A和验证者B之间以前进行的多项式次认证会话且被窃听； d.2 冒充击者C以前参与了同宣称者A或（和）验证者B的认证执行； d.3 冒充者C可能发起多个认证会话并行运行。

对认证的常见攻击方法 (1) 重放攻击 (2) 平行会话攻击 (3) 反射攻击 (4) 交错攻击

4.5.2 数据源认证 定义11 数据源认证或消息认证技术提供一方通过一些附加的证据确定消息的产生一方的真实身份。 例子3 实体A向实体B发送电子邮件，电子邮件通过网络传输并存储，最后，在某个时间由B接收到，由于没有直接通信，B这时可能要求认证邮件确实来自A。

4.6 密码Hash函数技术 4.6.1 修改发现码(MDCs) 定义12 Hash函数h()是一个有效的计算方法，它将 一个任意长度的二进制位串影射成固定长度的二进 制位串，这个固定长度的二进制位串叫Hash值。 4.6.1 修改发现码(MDCs) 附加性质 (1) Hash函数是单向函数，即给定y，找到任意x，满足y=h(x)计算不可能。 (2) 已知x，找x'，满足h(x)=h(x')计算不可能。 (3) 找一任意对x和x' ，满足h(x)=h(x')计算不可能。 # 修改发现码可以进一步分类，单向Hash函数(1-2)(OWHFs)和碰撞抵抗Hash函数(2-3)(CRHFs)。

4.6.2 消息认证码(MACs) 4.6.3 密码Hash函数的简单分类 无密钥 有密钥 修改发现码 (MDCs) 其他应用 消息认证码 (MACs)

4.7 随机数与随机序列 两个简单的真随机数产生方法 例子4 通过随机投币确定序列的每一位“0”和“1”，如果随机投币是无偏的，即“0”和“1”各有1/2可能，生成的序列即为随机序列。 例子5 使用噪声二极管产生随机序列。 # 开销大，速度慢，不适合计算系统。 密码中以伪随机序列发生器代替随机序列发生器。伪随机序列发生器以短的随机数做种子以固定方式产生伪随机序列。 # 伪随机序列与真随机序列，不可区分假设与安全数字签名、陷门函数的存在性等价。

4.8 丰富多彩的密码协议 4.8.1 会话密钥建立协议 4.8.2 秘密分享 当需要用私钥密码在网络上传输大量数据时，在实体不见面的情况下如何建立密钥。可以用公钥密码技术，Diffie-Hellman交换协议来解决，也可以依靠TTP使用私钥技术分配密钥。 4.8.2 秘密分享 不论哪种密码方案，解密密钥都是需要严格保密的，将其放在特殊警卫的保险柜或以某种方式记于脑中都是不安全的，制出多个副本或交由多人保管也不安全。秘密分享就是研究将秘密分成多个子秘密，只有指定数量的子秘密才能恢复原始秘密的解决方案。

4.8.3 电子商务与电子现金 如何在公共信道上进行安全的交易，如何保护用户的个人信用卡信息不被恶意商家骗取？信用卡和类似的设备可以提供现金支付的便利，但不能提供匿名性。简单的不记名电子现金可以提供匿名性，但在电子世界里复制这些现金变得特别容易。密码学提供了既可以保证匿名性又可以抓住使用复制现金的骗子的解决方案。 4.8.4 游戏 坐在同一个屋子里玩投币或纸牌游戏是很容易的一件事。但是，如果在网上做这件事，就不一样了。例如，发牌就是一个问题，如何保证它的公正就很有挑战性。 等等

5 安全评估模型 5.1 无条件安全(信息论意义下安全) a 无论攻击者具有何种计算能力，都无法破解 密码。 b Shannon证明无条件安全需要私钥加密中密 钥的长度与加密信息的长度相等。 c 私钥加密中有一次一密乱码本(one-time pad) 是无条件安全的密码。 d 公钥密码中没有。

5.2 计算复杂理论下安全 限定攻击者的计算能力为多项式能力(P)，证明破译密码需要指数能力(NP)。

5.3 规约安全 规约破解密码的能力为一个数论(通常是)中的著名困难问题，如RSA问题或Diffie-Hellman问题。步骤通常如下： b 在安全模型下，定义密码算法需要达到的安全目标。 c 描述密码算法。 d 规约密码算法可以达到设定的安全目标。 # 可以看作放宽条件的计算复杂理论下安全或下面所说的计算安全的特殊子类，这一方法是目前比较实用的公钥密码分析技术。

在已知的攻击方法和攻击者的计算能力下，攻击密码成功的可能性是可以忽略的。 5.4 计算安全 在已知的攻击方法和攻击者的计算能力下，攻击密码成功的可能性是可以忽略的。 特点：依赖困难问题，但不存在等价证明，大多数私钥密码属于这一类安全，也称为实践安全。

5.5 启发式安全 根据列出的著名攻击方法，结合使用的困难问题对密码进行逐条启发示分析，得出安全结论。很多高层复杂的密码协议通常采用这种方法，但经过这种分析方法的协议只能得到一定程度的计算复杂安全。 缺点：攻击的具体手段和方法可能无法穷尽，而且，设计者即使知道某一个攻击方法未必就可以设计出一个真正能抵抗这一攻击的密码，因此，设计的密码常常仍然存在漏洞。

谢谢！