1、现代密码学教师教师孙达志联系方式联系方式教学网页教学网页http:/202.113.2.12/faculty/sundazhi/Class-Crypto-M2014.htm成绩评定成绩评定考试: 80%; 平时: 20% 参考书 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 app
2、lied cryptography, CRC Press, 1997第一讲 现代密码学概论现代密码学的里程碑事件现代密码学的里程碑事件1. 1976年，Diffie和Hellman提出了适应网络上保密通信的公钥密码思想，以及不久之后的RSA公钥密码算法，奠定了公钥密码学的基础。2. 1977年，美国国家标准局正式公布实施美国的数据加密标准(DES)公开它的加密算法，并批准用于非机密单位及商业上的保密通信。本讲提要q 密码系统q 对称与非对称密码思想q 现代密码学的基本目标q 现代密码学的基本概念和技术q 评估安全的模型1 安全系统安全系统1.1 Shannon保密系统发送者Alice密钥源分析
3、者Eve接收者Bob安 全信道公共信道加密器Ek解密器Dk明文m密文c明文m密钥k密钥k1.1.1 通信中的参与者 发送者发送者(Alice)：在双方交互中合法的信息发送实体。 接收者接收者(Bob)：在双方交互中合法的信息接收实体。 分析者分析者(Eve)：破坏通信接收和发送双方正常安全通信的其它实体。1.1.2 信道 信道信道：从一个实体向另一个实体传递信息的通路。 安全信道安全信道：分析者没有能力对其上的信息进行阅读、删除、修改、添加的信道。 公共信道公共信道：分析者可以任意对其上的信息进行阅读、删除、修改、添加的信道。1.1.3 分析者的目的 解读公共信道上的密文消息。 (被动) 确定
4、密钥以解读所有用该密钥加密的密文消息。 (被动) 变更密文消息已使接受者(Bob)认为变更消息来自发送者(Alice)。 (主动) 冒充密文消息发送者(Alice)与接收者(Bob)通信，以使接受者(Bob)相信消息来自真实的发送者(Alice)。(主动)1.2 常见的攻击形式唯密文攻击唯密文攻击：分析者仅仅掌握密文。已知明文攻击已知明文攻击：分析者掌握密文以及其对应的明文。选择明文攻击选择明文攻击：分析者可以临时访问加密机，可以用自己选择的明文加密，但不能直接要求输出密钥。选择密文攻击选择密文攻击：分析者可以临时访问解密机，可以解密一些自己想得到的符号串。1.3 Kerckhoffs准则在评
5、估一个密码系统安全性时，应该总是假定我们的敌人了解实际使用的各种方法。# 落实到现代密码算法中就是攻击者知道密码算法的所有执行细节，算法的安全不应该依赖于对算法的保密。2 私钥密码私钥密码VS公钥密码思想公钥密码思想2.1 私钥密码体制# 加密密钥与解密密钥同：K1=K2代表系统：DES和AES加密器EK1(m)=c分析者Eve解密器DK2(c)= m明文消息源目的地mmc公共信道AliceBob2.2 私钥密码在网络环境下遇到的挑战：密钥产生与管理问题若互联网上有n个用户，则需要个密钥，若n=1000，则NK500 000。# 如此众多的密钥如何建立，如何保存？) 1(22nnnNK2.3
6、公钥密码体制加密器EK1(m)=c分析者Eve解密器DK2(c)= m明文消息源目的地mmc公共信道AliceBob# 加密密钥与解密密钥不同：K1K2代表系统：RSA和ElGamal2.4 密码体制的演进及目前的状态安全依赖于保密加密方法安全依赖于保密密钥安全依赖于保密部分密钥古典密码私钥密码公钥密码#公钥密码体制以其强大的功能使得私钥密码体制显得已经过时，但是强大的功能不是无代价获得的，公钥密码的计算量远大于同情况下的私钥密码，因此，不适合加密大量数据，只适合于完成少量数据加密，如传送私钥密码算法的密钥、签名等等。3 现代密码学解决的基本安全问题现代密码学解决的基本安全问题 机密问题。机密
7、问题。这指的是除了信息的授权人可以拥有信息以外，其他人都不可获得信息内容。在密码学中，主要是通过加密和解密算法来完成这项任务。 数据真实完整问题。数据真实完整问题。这一问题的提出是为了发现对数据的非法变更。为了做到这一点，必须提供发现非授权人对数据变动的机制。许多密码工具可以提供这一机制，如Hash函数等。 认证问题。认证问题。这是一个与识别相关的问题，可以应用于实体也可以应用于信息本身。两方在进行通信之前，一般需要识别对方的身份。而在信道上传输的一条信息也需要识别它是何时、何地、何内容由何人发出。因此，认证在密码学中常常被分成两类：实体认证和数据源认证。可以看出数据源认证隐含了提供数据真实性
8、服务，这是因为数据被修改，数据源也就自然发生了变更。 不可否认问题不可否认问题。这一问题的提出是为了阻止实体否认从前的承诺或行为。争议的发生常常是由于实体否认从前的某个行为。例如，一个实体与另一个实体签署了购买合同，但事后又否认签署过，这时常常需要一个可信第三方来解决争议。这就需要提供必要的手段来解决争议。在密码学中，解决这一问题的手段常常是数字签名。4 现代密码学的基本概念和技术现代密码学的基本概念和技术4.1 单向函数和陷门单向函数 单向函数 定义定义 1 一个定义域为X值域为Y的函数y=f(x)称之为单向函数：如果对于所有x X计算f(x)都是“容易的”，而对于“基本上所有基本上所有y
9、Y”发现任意一个xX满足f(x)=y都是“计算不可能的”。xf(x)HardEasy实例：大整数分解问题离散对数问题背包问题 陷门单向函数 定义定义 2 一个陷门单向函数是单向函y=f(x)再附加一个特性，即如果给定一些附加信息称之为陷门信息陷门信息K，那么，就对任意yY求解xX满足fK(x)=y都变得“容易了”。4.2 加密加密4.2.1 加密基本术语明文消息空间M: 某个字母表集密文消息空间C: 可能的密文消息集加/解密密钥空间K: 可能的加/解密密钥集加/解密函数EeK(mM)/DdK(cC) : 一个从M到C/C到M的有效变换 加密方案是由一个加密函数集Ee: eK和解密函数集Dd:
10、dK构成，并且满足任意一个加密密钥eK存在唯一一个解密密钥dK使 Dd=Ee1，也就是对于所有明文消息mM ，存在Dd(Ee(m) = m，(e, d)称为密钥对。设计加密方案就是确定M、 C、 K、Ee: eK、Dd:dK的过程。 定义定义 3 一个加密方案可以被破译是指，第三方在没有事先得到密钥对(e, d)的情况下，可以在适当的时间里系统的从密文恢复出相对应的明文。 # 适当的时间是由被保护数据生命周期来确定。 4.2.2 加密方案 定义定义 4 一个由加密函数集Ee: eK和解密函数集Dd: dK组成加密方案，每一个相关联的密钥对(e, d) ，如果知道了e在计算上很容易确定d，知道了
11、d在计算上很容易确定e，那么，就是私钥加密方案。 # 私钥加密需要一条安全信道来建立密钥对。4.2.3 私钥加密 主要技术：分组密码分组密码与流密码流密码 定义定义 5(分组密码分组密码) 将明文消息在编码集按照固定长度t进行分组，再一组一组的加解密明密文消息。 #著名的DES、AES都是这类密码。 定义定义 6 令K 是加密变换集的密钥空间，序列 e1e2eiK称为密钥流。 定义定义 7(流密码流密码) 消息m以串的形式(m1m2mi)给出，密钥e1e2ei是K上的密钥流。流密码通过ci=Eei(mi)给出密文消息(c1c2ci)；如果di为ei的逆，解密则通过mi=Ddi(ci)完成。 定
12、义定义 8 一个由加密函数集Ee: eK和解密函数集Dd: dK组成加密方案，每一个相关关联的加/解密密钥对(e, d)，加密密钥e公开，称为公开密钥，而解密密钥d保密，称为秘密密钥。 # 显然安全公钥密码系统要求从e计算d为不可能。 4.2.4 公钥加密公钥加密实例Ee(m1)=c1A1Ee(m2)=c2A2Ee(m3)=c3A3Dd(c1)=m1Dd(c2)=m2Dd(c3)=m3Bobec1eec2c3# 因为存在替代攻击问题，公钥系统中公开密钥e必须认证，一般是建立PKI。4.2.5 对加密方案的攻击方法 唯密文攻击 已知明文攻击 选择明文攻击 适应性选择明文攻击 选择密文攻击 适应性
13、选择密文攻击4.3 数字签名技术4.3.1 签名的基本术语明文消息空间M:某个字母表中串的集合签名空间S:可能的签名集合签名密钥空间K:用于生成签名的可能密钥集，具体取值k需要保密验证密钥空间K:用于验证签名的可能密钥集，具体取值k需要公开签名函数SK(mM):从M到S的有效变换验证函数VK(mM, s):一个从MS到输出True, False的有效变换 签名过程签名过程(签名者完成) (1) 对一条需要签名的消息mM计算签名s=Sk(m)。 (2) 将对消息m 的签名(m, s)发送出去。 验证过程验证过程(验证者完成) (1) 得到对应签名者的验证算法Vk ，计算u=Vk (m, s)。
14、(2) 如果u=True，接受签名；如果u=False，拒绝签名。4.3.2 签名过程 (1) 当且仅当Vk (m, s)=True时，s是对消息m的合法签名。 (2) 对于任何签名者以外的实体得到任意的一组mf和sf满足Vk (mf , sf)=True是计算不可能的。4.3.3 签名和认证函数必须满足的性质4.3.4 数字签名的争议解决（不可否认）如果签名者和验证者对签名发生争议，可由验证者带签名(m, s)提交给可信任第三方(TTP)，由TTP验证该签名，最后进行仲裁。 定义定义 9 对于满足Dd(Ee(m)=Ee(Dd(m)=m和M=C的公钥加密算法，称为可逆公钥密码算法。 # 只有在
15、M=C的情况下对于所有的mM变换等式都成立。 可逆公钥密码算法可以直接构造数字签名如下： (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.3.5 数字签名与公钥加密的关系4.4 密钥管理模式4.4.1 私钥管理模式# TTP负荷大(在线、交互、存储密钥)，权限高A1A4A2A5A6k1TTPA3kk2k3k4k5k6密钥源Ek1(k)Ek(m)Ek5(k)4.4.2 公钥管理模式# TTP负荷小(离线、非交互
16、、存储证书)，权限低A1, e1, ST(A1 | e1)=s1A5, e5, ST(A5 | e5)=s5A6, e6, ST(A6 | e6)=s6A1A6认证VT(A6 | e6 , s6)秘密密钥 d6A2, e2, ST(A2 | e2)=s2A3, e3, ST(A3 | e3)=s3A4, e4, ST(A4 | e4)=s4e6, s6Dd6(c)=mc = Ee6(m)Public file4.5 认证与鉴别技术 定义定义 10 鉴别或实体认证是一个过程。在这个过程中一方通过获得一些确定的证据来确认参加实体认证的另一方的身份，而具有相应身份的实体也确实就是正在参与这一认证过程
17、的另一方。4.5.1 鉴别或实体认证 例子例子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的身份的可能性可以忽略。这里，可以忽略的含义是概率小到没有具体的实际意义，准确的度量需要根据
18、实际应用而定。 d.1宣称者A和验证者B之间以前进行的多项式次认证会话且被窃听； d.2 冒充击者C以前参与了同宣称者A或（和）验证者B的认证执行； d.3 冒充者C可能发起多个认证会话并行运行。d 即使如下情况存在，以上三个条件仍然成立。 对认证的常见攻击方法攻击方法 (1) 重放攻击 (2) 平行会话攻击 (3) 反射攻击 (4) 交错攻击 定义定义11 数据源认证或消息认证技术提供一方通过一些附加的证据确定消息的产生一方的真实身份。 例子例子3 实体A向实体B发送电子邮件，电子邮件通过网络传输并存储，最后，在某个时间由B接收到，由于没有直接通信，B这时可能要求认证邮件确实来自A。4.5.
19、2 数据源认证4.6 密码Hash函数技术定义定义12 Hash函数h()是一个有效的计算方法，它将一个任意长度的二进制位串影射成固定长度的二进制位串，这个固定长度的二进制位串叫Hash值。附加性质附加性质 (1) Hash函数是单向函数，即给定y，找到任意x，满足y=h(x)计算不可能。(2) 已知x，找x，满足h(x)=h(x)计算不可能。(3) 找一任意对x和x ，满足h(x)=h(x)计算不可能。# 修改发现码可以进一步分类，单向Hash函数(12)(OWHFs)和碰撞抵抗Hash函数(23)(CRHFs)。4.6.1 修改发现码(MDCs)4.6.2 消息认证码(MACs) 消息认证
20、码的目的通俗讲就是不附加任何其它机制，确保消息来源的真实性的Hash函数。消息认证码有两个不同功能的参数，即消息和秘密密钥。4.6.3 密码Hash函数的简单分类 Hash函数无密钥有密钥修改发现码(MDCs)其他应用其他应用消息认证码(MACs)4.7 随机数与随机序列 两个简单的真随机数产生方法 例子例子4 通过随机投币确定序列的每一位“0”和“1”，如果随机投币是无偏的，即“0”和“1”各有1/2可能，生成的序列即为随机序列。 例子例子5 使用噪声二极管产生随机序列。 # 开销大，速度慢，不适合计算系统。 密码中以伪随机序列发生器代替随机序列发生器。伪随机序列发生器以短的随机数做种子以固
21、定方式产生伪随机序列。 # 伪随机序列与真随机序列，不可区分假设与安全数字签名、陷门函数的存在性等价。4.8 丰富多彩的密码协议 当需要用私钥密码在网络上传输大量数据时，在实体不见面的情况下如何建立密钥。可以用公钥密码技术，Diffie-Hellman交换协议来解决，也可以依靠TTP使用私钥技术分配密钥。4.8.1 会话密钥建立协议4.8.2 秘密分享不论哪种密码方案，解密密钥都是需要严格保密的，将其放在特殊警卫的保险柜或以某种方式记于脑中都是不安全的，制出多个副本或交由多人保管也不安全。秘密分享就是研究将秘密分成多个子秘密，只有指定数量的子秘密才能恢复原始秘密的解决方案。 如何在公共信道上进
22、行安全的交易，如何保护用户的个人信用卡信息不被恶意商家骗取？信用卡和类似的设备可以提供现金支付的便利，但不能提供匿名性。简单的不记名电子现金可以提供匿名性，但在电子世界里复制这些现金变得特别容易。密码学提供了既可以保证匿名性又可以抓住使用复制现金的骗子的解决方案。4.8.3 电子商务与电子现金4.8.4 游戏坐在同一个屋子里玩投币或纸牌游戏是很容易的一件事。但是，如果在网上做这件事，就不一样了。例如，发牌就是一个问题，如何保证它的公正就很有挑战性。等等5 安全评估模型a 无论攻击者具有何种计算能力，都无法破解密码。b Shannon证明无条件安全需要私钥加密中密钥的长度与加密信息的长度相等。c
23、 私钥加密中有一次一密乱码本(one-time pad)是无条件安全的密码。d 公钥密码中没有。5.1 无条件安全(信息论意义下安全)5.2 计算复杂理论下安全 限定攻击者的计算能力为多项式能力(P)，证明破译密码需要指数能力(NP)。 规约破解密码的能力为一个数论(通常是)中的著名困难问题，如RSA问题或Diffie-Hellman问题。步骤通常如下： a 刻画安全模型。 b 在安全模型下，定义密码算法需要达到的安全目标。 c 描述密码算法。 d 规约密码算法可以达到设定的安全目标。 # 可以看作放宽条件的计算复杂理论下安全或下面所说的计算安全的特殊子类，这一方法是目前比较实用的公钥密码分析技术。5.3 规约安全 在已知的攻击方法和攻击者的计算能力下，攻击密码成功的可能性是可以忽略的。 特点：依赖困难问题，但不存在等价证明，大多数私钥密码属于这一类安全，也称为实践安全。5.4 计算安全 根据列出的著名攻击方法，结合使用的困难问题对密码进行逐条启发示分析，得出安全结论。很多高层复杂的密码协议通常采用这种方法，但经过这种分析方法的协议只能得到一定程度的计算复杂安全。 缺点：攻击的具体手段和方法可能无法穷尽，而且，设计者即使知道某一个攻击方法未必就可以设计出一个真正能抵抗这一攻击的密码，因此，设计的密码常常仍然存在漏洞。5.5 启发式安全谢谢！
