第二章 密码学基础(NEW)

第二章密码学基础目标要求基本要求理解密码系统的模型理解对称密码体制和非对称密码体制的原理掌握IDEA算法、ECC等公开密码算法的原理与应用了解常见的加密方式和各自的特点目标要求重点掌握对称密码体制和非对称密码体制的原理熟悉IDEA算法、ECC公开密码算法的原理与应用熟悉各种加密方式和各自的特点难点非对称密码体制的原理本章内容2.1密码技术概述2.2密码算法2.3对称密钥密码加密模式2.4网络加密方式2.1密码技术概述2.1.1密码学历史1000BC:姜子牙阴阳符500-600BC:天书100-44BC:CaesarciphertheromansarecomingtodayCaesarcipher：移位密码密文表：abcdefghijklmnopqrstuvwxyz密文表：defghijklmnopqrstuvwxyzabcAnexample:–明文----Plaintext:Howareyou–密文----Ciphertext?1790:转轮密码，ThomasJefferson二战:GermanEnigmamachine二战:JapanesePurplemachine1948，香农ClaudeShannon与信息论ClaudeShannon与密码学Born:30April1916inGaylord,Michigan,USADied:24Feb2001inMedford,Massachusetts,USA2.1.2密码系统加密变换不安全信道PlainTextCipherTextCipherText解密变换PlainText发送者：AliceDecryptionKeyEncryptionKey接受者：AliceCipherText密码分析？窃密者：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(1835～1903)就给出了密码学的一个基本原则:密码的安全必须完全寓于密钥之中。尽管密码学家们大都同意这一看法,但直到制定DES时才首次认真地遵循这一原则。2.1.3密码体制密码体制：一个密码系统采用的基本工作方式密码体制从原理上可以分为两大类：对称密钥密码体制（或单钥密码体制）非对称密钥密码体制（或双钥密码体制）2.1.3.1对称密钥密码体制加密：E不安全信道PlainTextCipherTextCipherText解密:DPlainText发送者：AliceKK接受者：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）对称密钥密码体制的问题2.1.3.2非称密钥密码体制ENetworkorStorage明文PlainText密文CipherTextD原明文OriginalPlainTextBob私钥SecretKeyAlice私钥SecretKey密文CipherText若N个人相互保密通信，每人必须拥有（N-1）个私钥，N很大时，需要保存的私钥很多。如何解决？可信中心分发：共需要发N*(N-1)/2个私钥N=1000时,999*1000/2=499500双方事先约定：用户之间自己秘密会面（第一次远距离通信如何办？）加密：E不安全信道PlainTextCipherTextCipherText解密:DPlainText发送者：AliceK2K1接受者：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的“混淆”和“扩散”设计原则来自三种运算，它们易于软、硬件实现（加密速度快）：Z6F2F1Z5G1G2异或运算模2^16加模(2^16)+11.在IDEA的模乘运算中，为什么将模数取为216+1，而不是216？2.在其模加运算中，为什么模数取为216而不是216+1？IDEA加密的总体方案图循环2循环8循环1输出变换64位密文64位明文Z1Z6Z7Z12Z43Z48Z49Z52子密钥生成器128bit密钥Z1Z5216IDEA加密的单个循环图X1X2X3X4Z1Z2Z3Z4Z5Z6W11W12W13W14IDEA的密钥生成56个16bit的子密钥从128bit的密钥中生成前8个子密钥直接从密钥中取出；对密钥进行25bit的循环左移，接下来的密钥就从中取出；重复进行直到52个子密钥都产生出来。（3）IDEA的解密加密解密实质相同，但使用不同的密钥；解密密钥以如下方法从加密子密钥中导出：—解密循环I的头4个子密钥从加密循环10－I的头4个子密钥中导出；解密密钥第1、4个子密钥对应于1、4加密子密钥的乘法逆元；2、3对应2、3的加法逆元；—对前8个循环来说，循环I的最后两个子密钥等于加密循环9－I的最后两个子密钥；使用子分组：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的集合。232yaxybyxcxdxe,,,,abcde实数上的椭圆曲线例子：231yxx（2）运算定义：12121211;,,22,OOOOpOpXppppOOppQRXpQRpOQSQQS若曲线三点在一条直线上，则其和为，用作加法的单位：，一条竖直线交轴两点则于是，如果两个点和的轴不同，则画一连线，得到第三个点，则，倍，一个点的倍是，找到它的切线与曲线的另一交点于是有限域上的椭圆曲线：模P椭圆群记为群中的元素（x,y)是满足以上方程的小于P的非负整数另外加上无穷远点O计算2332mod4270modyxaxbppabp是奇素数，