现代密码学概论

参考书[1]WadeTrappe,LawrenceC.Washington,Introductiontocryptographywithcodingtheory,Prentice-Hall,2002[2]AlfredJ.Menezes,PaulC.vanOorschot,ScottA.Vanstone,Handbookofappliedcryptography,CRCPress,1997第一讲现代密码学概论现代密码学的里程碑事件1.1976年，Diffie和Hellman提出了适应网络上保密通信的公钥密码思想，以及不久之后的RSA公钥密码算法，奠定了公钥密码学的基础。2.1977年，美国国家标准局正式公布实施美国的数据加密标准(DES)公开它的加密算法，并批准用于非机密单位及商业上的保密通信。本讲提要密码系统对称与非对称密码思想现代密码学的基本目标现代密码学的基本概念和技术评估安全的模型1安全系统1.1Shannon保密系统发送者Alice密钥源分析者Eve接收者Bob安全信道公共信道加密器Ek解密器Dk明文m密文c明文m密钥k密钥k1.1.1通信中的参与者发送者(Alice)：在双方交互中合法的信息发送实体。接收者(Bob)：在双方交互中合法的信息接收实体。分析者(Eve)：破坏通信接收和发送双方正常安全通信的其它实体。1.1.2信道信道：从一个实体向另一个实体传递信息的通路。安全信道：分析者没有能力对其上的信息进行阅读、删除、修改、添加的信道。公共信道：分析者可以任意对其上的信息进行阅读、删除、修改、添加的信道。1.1.3分析者的目的解读公共信道上的密文消息。(被动)确定密钥以解读所有用该密钥加密的密文消息。(被动)变更密文消息已使接受者(Bob)认为变更消息来自发送者(Alice)。(主动)冒充密文消息发送者(Alice)与接收者(Bob)通信，以使接受者(Bob)相信消息来自真实的发送者(Alice)。(主动)1.2常见的攻击形式唯密文攻击：分析者仅仅掌握密文。已知明文攻击：分析者掌握密文以及其对应的明文。选择明文攻击：分析者可以临时访问加密机，可以用自己选择的明文加密，但不能直接要求输出密钥。选择密文攻击：分析者可以临时访问解密机，可以解密一些自己想得到的符号串，借以帮助分析密钥。1.3Kerckhoffs准则在评估一个密码系统安全性时，应该总是假定我们的敌人了解实际使用的各种方法。#落实到现代密码算法中就是攻击者知道密码算法的所有执行细节，算法的安全不应该依赖于对算法的保密。2私钥密码VS公钥密码思想2.1私钥密码体制#加密密钥与解密密钥同：K1=K2代表系统：DES和AES加密器EK1(m)=c分析者Eve解密器DK2(c)=m明文消息源目的地mmc公共信道AliceBob2.2私钥密码在网络环境下遇到的挑战：密钥产生与管理问题若互联网上有n个用户，则需要个密钥，若n=1000，则NK500000。#如此众多的密钥如何建立，如何保存？)1(22nnnNK2.3公钥密码体制加密器EK1(m)=c分析者Eve解密器DK2(c)=m明文消息源目的地mmc公共信道AliceBob#加密密钥与解密密钥不同：K1K2代表系统：RSA和ElGamal2.4密码体制的演进及目前的状态安全依赖于保密加密方法安全依赖于保密密钥安全依赖于保密部分密钥古典密码私钥密码公钥密码#公钥密码体制以其强大的功能使得私钥密码体制显得已经过时，但是强大的功能不是无代价获得的，公钥密码的计算量远大于同情况下的私钥密码，因此，不适合加密大量数据，只适合于完成少量数据加密，如传送私钥密码算法的密钥、签名等等。3现代密码学解决的基本安全问题机密问题。这指的是除了信息的授权人可以拥有信息以外，其他人都不可获得信息内容。在密码学中，主要是通过加密和解密算法来完成这项任务。数据真实完整问题。这一问题的提出是为了发现对数据的非法变更。为了做到这一点，必须提供发现非授权人对数据变动的机制。许多密码工具可以提供这一机制，如Hash函数等。认证问题。这是一个与识别相关的问题，可以应用于实体也可以应用于信息本身。两方在进行通信之前，一般需要识别对方的身份。而在信道上传输的一条信息也需要识别它是何时、何地、何内容由何人发出。因此，认证在密码学中常常被分成两类：实体认证和数据源认证。可以看出数据源认证隐含了提供数据真实性服务，这是因为数据被修改，数据源也就自然发生了变更。不可否认问题。这一问题的提出是为了阻止实体否认从前的承诺或行为。争议的发生常常是由于实体否认从前的某个行为。例如，一个实体与另一个实体签署了购买合同，但事后又否认签署过，这时常常需要一个可信第三方来解决争议。这就需要提供必要的手段来解决争议。在密码学中，解决这一问题的手段常常是数字签名。4现代密码学的基本概念和技术4.1单向函数和陷门单向函数单向函数定义1一个定义域为X值域为Y的函数y=f(x)称之为单向函数：如果对于所有xX计算f(x)都是“容易的”，而对于“基本上所有yY”发现任意一个xX满足f(x)=y都是“计算不可能的”。xf(x)HardEasy实例：大整数分解问题离散对数问题背包问题陷门单向函数定义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的有效变换加密方案是由一个加密函数集{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.2加密方案定义4一个由加密函数集{Ee:eK}和解密函数集{Dd:dK}组成加密方案，每一个相关联的密钥对(e,d)，如果知道了e在计算上很容易确定d，知道了d在计算上很容易确定e，那么，就是私钥加密方案。#私钥加密需要一条安全信道来建立密钥对。4.2.3私钥加密主要技术：分组密码与流密码定义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)完成。定义8一个由加密函数集{Ee:eK}和解密函数集{Dd:dK}组成加密方案，每一个相关关联的加/解密密钥对(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对加密方案的攻击方法唯密文攻击已知明文攻击选择明文攻击适应性选择明文攻击选择密文攻击适应性选择密文攻击4.3数字签名技术4.3.1签名的基本术语明文消息空间M:某个字母表中串的集合签名空间S:可能的签名集合签名密钥空间K:用于生成签名的可能密钥集，具体取值k需要保密验证密钥空间K’:用于验证签名的可能密钥集，具体取值k’需要公开签名函数SK(mM):从M到S的有效变换验证函数VK’(mM,s):一个从MS到输出{True,False}的有效变换签名过程(签名者完成)(1)对一条需要签名的消息mM计算签名s=Sk(m)。(2)将对消息m的签名(m,s)发送出去。验证过程(验证者完成)(1)得到对应签名者的验证算法Vk’，计算u=Vk’(m,s)。(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的公钥加密算法，称为可逆公钥密码算法。#只有在M=C的情况下对于所有的mM变换等式都成立，否则对于mC，Dd(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.3.5数字签名与公钥加密的关系4.4密钥管理模式4.4.1私钥管理模式#TTP负荷大(在线、交互、存储密钥)，权限高A1A4A2A5A6k1TTPA3kk2k3k4k5k6密钥源Ek1(k)Ek(m)Ek5(k)4.4.2公钥管理模式#TTP负荷小(离线、非交互、存储证书)，权限低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)Publicfile4.5认证与鉴别技术定义10鉴别或实体认证是一个过程。在这个过程中一方通过获得一些确定的证据来确认参加实体认证的另一方的身份，而具有相应身份的实体也确实就是正在参与这一认证过程的另一方。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的身份的可能性可以忽略。这里，可以忽略的含义是概率小到没有具体的实际意义，准确的度量需要根据实际应用而定。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.2数据源认证4.6密码Hash函数技术定义12Hash函数h()是一个有效的计