第二章 密码学基础(NEW).ppt

第二章密码学基础,目标要求,基本要求理解密码系统的模型理解对称密码体制和非对称密码体制的原理掌握IDEA算法、ECC等公开密码算法的原理与应用了解常见的加密方式和各自的特点,目标要求,重点掌握对称密码体制和非对称密码体制的原理熟悉IDEA算法、ECC公开密码算法的原理与应用熟悉各种加密方式和各自的特点难点非对称密码体制的原理,本章内容,2.1密码技术概述2.2密码算法2.3对称密钥密码加密模式2.4网络加密方式,2.1密码技术概述,2.1.1密码学历史,1000BC:姜子牙阴阳符500-600BC:天书100-44BC:Caesarcipher,Caesarcipher：移位密码,密文表：abcdefghijklmnopqrstuvwxyz密文表：defghijklmnopqrstuvwxyzabcAnexample:明文-Plaintext:Howareyou密文-Ciphertext?,1790:转轮密码，ThomasJefferson,二战:GermanEnigmamachine,二战:JapanesePurplemachine,1948，香农,ClaudeShannon与信息论ClaudeShannon与密码学,Born:30April1916inGaylord,Michigan,USADied:24Feb2001inMedford,Massachusetts,USA,2.1.2密码系统,加密变换,PlainText,CipherText,CipherText,解密变换,PlainText,发送者：Alice,DecryptionKey,EncryptionKey,接受者：Alice,CipherText,密码分析,窃密者：Eve,密钥信道,（1）密码学基本概念,密码学(Cryptology)：研究信息系统安全保密的科学。它包含两个分支：密码编码学(Cryptography)，对信息进行编码实现隐蔽信息的一门学问；密码分析学(Cryptanalysis)，研究分析破译密码的学问。,明文(消息)(Plaintext)：被隐蔽消息，常用M表示密文(Ciphertext)或密报(Cryptogram)：明文经密码变换成的一种隐蔽形式，常用C表示加密(Encryption)：将明文变换为密文的过程解密(Decryption)：加密的逆过程，即由密文恢复出原明文的过程加密员或密码员(Cryptographer)：对明文进行加密操作的人员。,加密算法(Encryptionalgorithm)：密码员对明文进行加密时所采用的一组规则，常用E（）表示解密算法：接收者对密文进行解密时所采用的一组规则，常用D（）表示密钥(Key)：控制加密和解密算法操作的数据处理，分别称作加密密钥和解密密钥，常用k表示截收者(Eavesdropper)：在信息传输和处理系统中的非受权者，通过搭线窃听、电磁窃听、声音窃听等来窃取机密信息。,密码分析(Cryptanalysis)：截收者试图通过分析从截获的密文推断出原来的明文或密钥。密码分析员(Cryptanalyst)：从事密码分析的人。被动攻击(Passiveattack)：对一个保密系统采取截获密文进行分析的攻击。,（2）密码系统组成,明文空间：信息本来的原始空间密文空间：明文经过加密后得到难以理解和辨认的信息空间密钥空间：控制算法的实现，由信息通信双方所掌握的专门信息空间密码算法：规定了明文和密文之间的一个复杂的函数变换方式，包括加密函数与解密函数,加密过程：EK(M)=C加密过程：DK(C)=M密码系统应满足：DK(EK(M)=)=M,密码学的Kerchoff准则,“一切秘密寓于密钥之中”,1883年荷兰密码学家A.Kerchoff(18351903)就给出了密码学的一个基本原则:密码的安全必须完全寓于密钥之中。尽管密码学家们大都同意这一看法,但直到制定DES时才首次认真地遵循这一原则。,2.1.3密码体制,密码体制：一个密码系统采用的基本工作方式密码体制从原理上可以分为两大类：对称密钥密码体制（或单钥密码体制）非对称密钥密码体制（或双钥密码体制）,对称密钥密码体制,加密：E,PlainText,CipherText,CipherText,解密:D,PlainText,发送者：Alice,K,K,接受者：Alice,密钥信道,密钥生成器,加密过程：EK(M)=C加密过程：DK(C)=M对称密钥密码根据对明文加密方式的不同分为：序列密码（StreamCipher）或流密码分组密码（BlockCipher）或块密码,（1）序列密码,对明文的单个位（有时对字节）运算的算法。军事和外交场合使用的主要密码技术工作原理：,明文序列：m=m0m1m2,密文序列：c=ccc1c2,密钥序列：k=k0k1k2,序列密码的加密过程,明文序列：m=m0m1m2,密文序列：c=ccc1c2,密钥序列：k=k0k1k2,序列密码的解密过程,加密过程：ci=(ki+mi)(mod2)加密过程：mi=(ki+ci)(mod2),（2）分组密码,对明文信息分割成块结构，逐块进行加密和解密。工作原理：首先将明文分成相同长度的数据块，然后分别对每个数据块加密产生一串灭为你数据块；解密时，第每个密文数据块进行解密后得到相应的明文数据块，将所有的明文数据块合并起来即得到明文。,明文序列：m=m0m1m2,密文序列：c=ccc1c2,密钥序列：k=k0k1k2,分组密码的加密过程,Ek,明文序列：m=m0m1m2,密文序列：c=ccc1c2,密钥序列：k=k0k1k2,分组密码的加密过程,Dk,（1）对称密钥密码体制的问题,非称密钥密码体制,E,NetworkorStorage,明文PlainText,密文CipherText,D,原明文OriginalPlainText,Bob,私钥SecretKey,Alice,私钥SecretKey,密文CipherText,若N个人相互保密通信，每人必须拥有（N-1）个私钥，N很大时，需要保存的私钥很多。如何解决？可信中心分发：共需要发N*(N-1)/2个私钥N=1000时,999*1000/2=499500双方事先约定：用户之间自己秘密会面（第一次远距离通信如何办？）,加密：E,PlainText,CipherText,CipherText,解密:D,PlainText,发送者：Alice,K2,K1,接受者：Alice,1976，由Diffie和Hellman提出，被公认为现代密码学诞生的标志。,工作原理：每个用户都有一对选定的密钥（公钥：K1，私钥K2）K1是可以公开的，可以像电话号码一样进行注册公布；K2则是秘密的。特点：（1）将加密和解密能力分开；（2）多个用户加密的消息只能由一个用户解读（秘密通信）；（3）一个用户加密的消息而使多个用户可以解读（认证）；（4）不用事先分配秘钥。,（2）非对称密钥密码体制,2.1.4密码分析,密码分析：试图获得加密体制细节、解密密钥和明文等机密信息的过程，通常包括：分析统计截获的密文材料、假设、推断和证实等步骤。密码分析方法有传统破译方法和物理破译方法两大类。,（1）基本概念,传统破译方法包括穷举破译法和数学分析法两类。数学分析法又分为确定性分析法的和统计分析法。,四种破译类型：唯密文破译（ciphertextonlyattacks），分析者仅知道有限数量的密文。已知明文破译（knownplaintextattacks），分析者除了拥有有限数量的密文外，还有数量限定的一些已知“明文密文”对。,四种破译类型（续）：选择明文破译（chosenplaintextattacks），分析者除了拥有有限数量的密文外，还有机会使用注入了未知密钥的加密机，通过自由选择明文来获取所希望的“明文密文”对（集合）。选择密文破译（chosenciphertextattacks），分析者除了拥有有限数量的密文外，还有机会使用注入了未知密钥的解密机，通过自由选择密文来获取所希望的“密文明文”对（集合）。,（2）防止密码破译的措施,为防止密码被破译，可以采取以下措施：强壮的加密算法；动态会话密钥保护关键密钥,2.2密码算法,（1）IDEA的历史1990年，瑞士的来学嘉（XuejiaLai）和JamesMassey于1990年公布了IDEA密码算法第一版，称为PES(ProposedEncryptionStandard)；1991年，为抗击差分密码攻击，他们增强了算法的强度，称IPES（ImprovedPES)；1992年，改名为IDEA（InternationalDataEncryptionAlgorithm）。,2.2.1IDEA算法,（2）IDEA加密过程,IDEA是一个分组长度为64bit的分组密码算法，密钥长度为128bit（抗强力攻击能力比DES强），同一算法既可加密也可解密。IDEA的“混淆”和“扩散”设计原则来自三种运算，它们易于软、硬件实现（加密速度快）：,在IDEA的模乘运算中，为什么将模数取为216+1，而不是216？,2.在其模加运算中，为什么模数取为216而不是216+1？,IDEA加密的总体方案图,IDEA加密的单个循环图,IDEA的密钥生成,56个16bit的子密钥从128bit的密钥中生成前8个子密钥直接从密钥中取出；对密钥进行25bit的循环左移，接下来的密钥就从中取出；重复进行直到52个子密钥都产生出来。,（3）IDEA的解密,加密解密实质相同，但使用不同的密钥；解密密钥以如下方法从加密子密钥中导出：解密循环I的头4个子密钥从加密循环10I的头4个子密钥中导出；解密密钥第1、4个子密钥对应于1、4加密子密钥的乘法逆元；2、3对应2、3的加法逆元；对前8个循环来说，循环I的最后两个子密钥等于加密循环9I的最后两个子密钥；,使用子分组：16bit的子分组；使用简单操作（易于加法、移位等操作实现）；加密解密过程类似；规则的结构（便于VLSI实现）。,（4）实现上的考虑,（5）IDEA的安全性,IDEA能抗差分分析和相关分析；IDEA似乎没有DES意义下的弱密钥；IDEA是PGP的一部分；BruceSchneier认为IDEA是DES的最好替代，但问题是IDEA太新，许多问题没解决。,2.2.2ECC公钥密码,（1）简要历史椭圆曲线(Ellipticcurve)作为代数几何中的重要问题已有100多年的研究历史1985年，N.Koblitz和V.Miller独立将其引入密码学中，成为构造公钥密码体制的一个有力工具。利用有限域GF(2n)上的椭圆曲线上点集所构成的群上定义的离散对数系统，可以构造出基于有限域上离散对数的一些公钥体制-椭圆曲线离散对数密码体制(ECDLC)，如Diffie-Hellman，ElGamal，Schnorr，DSA等,实数上的椭圆曲线：其中的是满足简单条件的实数一些曲线上的点连同无穷远点O的集合。,实数上的椭圆曲线例子：,（2）运算定义：,有限域上的椭圆曲线：模P椭圆群记为群中的元素（x,y)是满足以上方程的小于P的非负整数另外加上无穷远点O计算,的加法规则：,ECC的加解密：,ECC加解密例子,ECC特别适用：无线Modem的实现：对分组交换数据网提供加密，在移动通信器件上运行4MHz的68330CPU，ECC可实现快速Diffie-Hellman密钥交换，并极小化密钥交换占用的带宽，将计算时间从大于60秒降到2秒以下。Web服务器的实现：在Web服务器上集中进行密码计算会形成瓶颈，Web服务器上的带宽有限使带宽费用高，采用ECC可节省计算时间和带宽，且通过算法的协商较易于处理兼容性。集成电路卡的实现：ECC无需协处理器就可以在标准卡上实现快速、安全的数字签名，这是RSA体制难以做到。ECC可使程序代码、密钥、证书的存储空间极小化，数据帧最短，便于实现，大大降低了IC卡的成本。,Menezes，Okamoto和Vanstone指出应避免选用超奇异曲线，否则椭圆曲线群上的离散对数问题退化为有限域低次扩域上的离散对数问题，从而能在多项式时间上可解。他们还指出，若所用循环子群的阶数达2160，则可提供足够的安全性。,（3）ECC的安全性,ECC和RSA对比：在实现相同的安全性下，ECC所需的密钥量比RSA少得多，如下表所示。其中MIPS年表示用每秒完成100万条指令的计算机所需工作的年数，m表示ECC的密钥由2m点构成。以40MHz的钟频实现155bits的ECC，每秒可完成40,000次椭园曲线运算，其速度比1024bits的DSA和RSA快10倍。ECC的密钥长度mRSA的密钥长度MIPS-年1601024101232051201036600210001078120012000010168,2.3.1分组密码的工作模式,2.3网络加密方法,分组密码可以按不同的模式工作，实际应用的环境不同应采用不同的工作模式电码本(ECB)模式密码分组链接(CBC)模式密码反馈(CFB)模式输出反馈(OFB)模式计数器(CTR)模式,2.3.2电码本（ECB）模式,最简单的运行模式，一次对一个64bit长的明文分组加密，且每次加密密钥都相同。,在用于短数据（如加密密钥）时非常理想，是安全传递DES密钥的最合适的模式在给定的密钥下同一明文组总产生同样的密文组。这会暴露明文数据的格式和统计特征。明文数据都有固定的格式，需要以协议的形式定义，重要的数据常常在同一位置上出现，使密码分析者可以对其进行统计分析、重传和代换攻击,2.3.3密码分组链接（CBC）模式,一次对一个明文分组加密，每次加密使用同一密钥，加密算法的输入是当前明文分组和前一次密文分组的异或（在产生第1个密文分组时，需要有一个初始向量IV与第一个明文分组异或）；,解密时，每一个密文分组被解密后，再与前一个密文分组异或（第一个密文分组解密后和初始向量IV异或恢复出第一个明文分组）。,为使安全性最高，IV应像密钥一样被保护。可使用ECB加密模式来发送IV；保护IV原因是：如果敌手能欺骗接受方使用不同的IV，敌手就能够在明文的第一个分组中插入自己选择的比特值；IV的完整性要比其保密性更为重要。在CBC模式下，最好是每发一个消息，都改变IV，比如将其值加一；由于CBC模式的链接机制，该模式对于加密长于64bit的消息非常合适；CBC模式除能获得保密性外，还能用于认证。,2.3.4密码反馈（CFB）模式,加密算法的输入是64bit移位寄存器，其初始值为某个初始向量IV，加密算法输出的最左（最高有效位）jbit与明文的第一个单元进行异或，产生第一个密文单元并传送该单元。然后将移位寄存器的内容左移j位并将送入移位寄存器最右边（最低有效位）j位。这一过程持续到明文的所有单元都被加密为止,解密时，将收到的密文单元与加密函数的输出进行异或,为什么此时仍然使用加密算法而不是解密算法？,利用CFB模式或者OFB模式可将DES转换为流密码；流密码不需要对消息进行填充，而且运行是实时的，因此如果传送字母流，可使用流密码对每个字母直接加密进行传送；CFB模式除了获得保密性外，还能用于认证。,2.