数据加密及认证技术

数据加密及认证技术主要内容数据加密概述密码学的发展密码学基本概念与分类密码分析学传统密码技术对称密钥密码公钥密码体制数字签名与认证技术加密软件密码学的起源古代加密方法大约起源于公元前440年出现在古希腊战争中的隐写术。古希腊的斯巴达人曾将军事情报刻在普通的木板上，用石蜡填平，收信的一方只要用火烤热木板，融化石蜡后，就可以看到密信。密码学用于通信的另一个记录是斯巴达人于公元前400年应用锥形指挥棒在军官间传递秘密信息。我国古代的藏头诗、藏尾诗、漏格诗《水浒传》“吴用智赚玉麒麟”一回中的诗

卢花滩上有扁舟，俊杰黄昏独自游。

义到尽头原是命，反躬逃难必无忧。明代怪杰徐文长：

平湖一色万顷秋，

湖光渺渺水长流。

秋月圆圆世间少，

月好四时最宜秋。密码学在军事中的应用1894年甲午海战中北洋水师的覆灭，虽然其根本的原因在于清朝廷的腐败,但是日本人破译了清军的密码也是一个重要的原因；二战中,美国利用破译密码所获得的情报为其外交服务；在1962年的古巴导弹危机中,苏美剑拔弩张,形势严峻。据悉，美国人心生一计，故意用能被苏联截收、破译的密码告知其军队，准备与苏联开战。这一手果然吓住了赫鲁晓夫；1994年,美国的情报机构通过截获国际电讯得知，法国与沙特阿拉伯正在进行一笔数亿美元的军火交易，美国先行一步从法国人手中抢下了这笔大生意。密码学从军事走向生活电子邮件自动提款机（ATM）网上银行/网上证券信用卡购物（POS机）生活中的密码学案例一：甲给乙写的私人信件，丙未经甲乙允许擅自阅读此信——非授权访问案例二：甲和乙正常通信，丙冒充甲并且：制造欺诈信息给乙；窜改甲给乙发的合法信息；——中间人攻击案例三：甲在某时某地给乙发了信，乙否认收到了该信——抵赖密码学的发展史第一阶段：1949年以前

古典密码阶段计算机技术出现以前密码学作为一种艺术，而不是一门科学第二阶段：1949年~1975年现代密码学初期

标志：1949年Shannon发表的《保密系统的信息理论》一文。密码学进入了科学的轨道，密码学成为科学主要技术:单密钥的对称密钥加密算法第三阶段：1976年~现代密码学阶段标志：1976年Diffie和Hellman发表了《密码学新方向》一文。新的密码体制:公开密钥体制第一阶段－古典密码古典密码的加密方法一般是代换与置换，使用手工或机械变换的方式实现；代表密码体制主要有：单表替代密码：Caesar密码；多表替代密码：Playfair密码、Hill密码、Vigenere密码；转轮密码：著名的Enigma密码，第二次世界大战中使用过。主要特点：数据的安全基于算法的保密。第二阶段现代密码学初期1949~19751949年，香农发表了《保密系统的信息理论》证明了密码编码学是如何置于坚实的数学基础之上的，从此密码学发展成为一个专门学科——标志性事件为对称密码体制的发展奠定了理论基础；1967年，大韦卡恩的专著《破译者》详细描述了密码学的历史；1971-73年，IBMWatson实验室的HorstFeistel等几篇技术报告，DES算法的产生；主要特点：数据的安全基于密钥而不是算法的保密。第三阶段：1976～公钥密码学公钥密码学成为主要研究方向；主要特点:公钥密码使得发送端和接收端无密钥传输的保密通信成为可能。代表性事件：1976年,Diffie和Hellman发表的革命性论文《密码学新方向》(Newderyctionsincryptography),突破了传统密码体制使用秘密密钥所带来的密钥管理难题,使密码的发展进入了一个全新的发展时期。1977年，Rivest，Shamir和Adleman提出了RSA公钥算法。DES算法出现。80年代，出现IDEA和CAST等算法。90年代，对称密钥密码算法进一步成熟，Rijndael，RC6等出现，逐步出现椭圆曲线等其他公钥算法。2001年，Rijndael成为DES算法的替代者。密码学的新方向密码专用芯片集成密码技术是信息安全的核心技术，无处不在，目前已经渗透到大部分安全产品之中，正向芯片化方向发展。在芯片设计制造方面，目前微电子水平已经发展到0.1um工艺以下，芯片设计的水平很高。我国在密码专用芯片领域的研究起步落后于国外，近年来我国集成电路产业技术的创新和自我开发能力得到了提高，微电子工业得到了发展，从而推动了密码专用芯片的发展。加快密码专用芯片的研制将会推动我国信息安全系统的完善。量子密码技术量子技术在密码学上的应用分为两类：一是利用量子计算机对传统密码体制的分析；二是利用单光子的测不准原理在光纤级实现密钥管理和信息加密，即量子密码学。量子计算机是一种传统意义上的超大规模并行计算系统，利用量子计算机可以在几秒钟内分解RSA129的公钥。量子计算机处理器DNA密码技术随着DNA计算的发展，有科学家开始把DNA用于密码学领域。Reif等人提出用DNA实现一次一密的密码系统，Celland等人提出用DNA隐藏消息。

DanBoneh等人用DNA计算机破译了DES，并且声称任何小于64位的密钥都可以用这种方法破译Salomaa也宣称现有的很多数学困难问题可以通过DNA计算机进行穷举搜索得到结果，而其中很多困难问题都是现代密码系统的安全依据。什么是密码学密码学基本概念密码体制分类密码学基本概念密码学(cryptology)：研究信息的保密和复原保密信息以获取其真实内容的学科称为密码学。包括：密码编码学(cryptography)：研究对信息进行编码，实现隐蔽信息的一门学科。密码分析学(cryptanalytics)：不知道任何加密细节的条件下解密消息的技术，即“破译”。密码编码学（1）密码编码学是密码学的一个分支，研究与信息安全（例如：机密性、完整性、可鉴别性）有关的数学技术。（2）密码编码学是包含数据变换的原理、工具和方法的一门学科，这种数据变换的目的是为了隐藏数据的信息内容，阻止对数据的篡改以及防止未经认可使用数据。（3）密码编码学是论述使明文变得不可懂的密文，以及把已加密的消息变换成可懂形式的艺术和技巧。加密（Encryption）：将明文变换为密文的过程。把可懂的语言变换成不可懂的语言，这里的语言指人类能懂的语言和机器能懂的语言。解密（Decryption）：加密的逆过程，即由密文恢复出原明文的过程。把不可懂的语言变换成可懂的语言。加密算法密钥密文明文解密算法密钥密文明文加密和解密算法的操作通常都是在一组密钥的控制下进行的，分别称为加密密钥(EncryptionKey)和解密密钥(DecryptionKey)。加密：Ek(M)=C解密：Dk(C)=M密码学基本概念Kerckhoff原理AugusteKerckhoff在1883年发表了一篇论文，认为一个密码系统中唯一应该保密的只有密钥。他认为，密码算法应该对外公开，如果一个密码系统需要保密的越多，可能的弱点也越多。这种观点对于密码研究者和私营部门来说已经是一种常识，但是军事部门和政府则不这么认为。世界上大部分的政府都研制自己的算法并且不对外公开。Kerchhoff假设：密码分析者知道双方使用的密码系统，包括明文的统计特性、加解密体制等，唯一不知道的是密钥。在设计一个密码系统时，目标是在Kerckhoffs假设的前提下实现安全。密码体制分类的三种方法替代密码vs.换位密码对称密码算法vs.非对称密码算法分组密码vs.流密码密码体制分类按转换明文为密文的运算类型分类：替代密码（SubstitutionCipher）：就是明文中的每一个字符被替换成密文中的另一个字符。接收者对密文做反向替换就可以恢复出明文。置换密码（PermutationCipher）：又称换位密码(TranspositionCipher)：明文的字母保持相同，但顺序被打乱了。密码体制分类按所用的密钥数分类：对称密码算法（Symmetriccipher）：加密密钥和解密密钥相同，或实质上等同，即从一个易于推出另一个。又称传统密码算法（Conventionalcipher)、秘密密钥算法或单密钥算法。DES、3DES、IDEA、AES非对称密码算法（Asymmetriccipher）：加密密钥和解密密钥不同，从一个很难推出另一个。又叫公钥密码算法（Public-keycipher)。其中的加密密钥可以公开，称为公开密钥（publickey)，简称公钥；解密密钥必须保密，称为私人密钥（privatekey)，简称私钥。RSA、ECC、ElGamal密码体制分类按处理明文的方法分类：分组（块）密码：将明文分成固定长度的组，用同一密钥和算法对每一块加密，输出也是固定长度的密文；DES、IDEA、RC2、RC4、RC5；序列（流）密码：序列密码每次加密一位或一字节的明文；One-timepadding、Vigenére、Vernam；流密码模型24密钥流产生器密钥k明文m密文c流密码体制模型异或运算25明文为“university”，密钥流为key=(1001011101100110001011010101111000110010111011001100010110101011110001)分组密码模型分组密码是将明文消息编码表示后的数字（简称明文数字）序列，划分成长度为n的组（可看成长度为n的矢量），每组分别在密钥的控制下变换成等长的输出数字（简称密文数字）序列。密码分析学攻击传统密码体制的一般方法：穷举攻击：对一条密文尝试所有可能的密钥。平均而言，成功至少需要尝试所有可能密钥的一半。密码分析：利用算法的性质和明文的特征或某些明密文对。密码分析学是在不知道密钥的情况下，恢复出明文的科学；成功的密码分析能恢复出消息的明文或密钥；密码分析学（1）密码分析学是密码学的一个分支，它与另一个分支学科——密码编码学是两个相互对立、相互依存、相辅相成、相互促进的学科。（2）密码分析学是企图挫败编码技术以及更一般说来的信息安全服务的数学技术学科。（3）密码分析学是对密码体制、密码体制的输入输出关系进行分析，以便推出机密变量、包括明文在内的敏感数据。有时又称作密码破译学（codebreaking）密码分析攻击的典型方式假设通信双方，Alice和Bob已经完成了秘钥交换，秘钥k是双方已知的，开始进行如下通信：AliceBob密码分析攻击的典型方式攻击者已知加密算法，已知待破解的密文：

唯密文攻击：密码分析者有一些消息的密文，这些消息都用同一加密算法加密。密码分析者的任务是恢复尽可能多的明文，或者最好是能推算出加密消息的密钥来，以便可采用相同的密钥解出其他被加密的消息。密码分析攻击的典型方式攻击者已知加密算法，已知待破解的密文，已知一条或者多条明文-密文对；已知明文攻击：密码分析者不仅可得到一些消息的密文，而且也知道这些消息的明文。分析者的任务就是用加密信息推出用来加密的密钥或推导出一个算法，此算法可以对用同一密钥加密的任何新的消息进行解密。密码分析攻击的典型方式攻击者已知加密算法，已知待破解的密文，能够获得通过加密算法生成自选的明文-密文对；选择明文攻击：分析者不仅可得到一些消息的密文和相应的明文，而且他们也可选择被加密的明文。这比已知明文攻击更有效。因为密码分析者能选择特定的明文块去加密，那些块可能产生更多关于密钥的信息，分析者的任务是推出用来加密消息的密钥或导出一个算法，此算法可以对用同一密钥加密的任何新的消息进行解密.通常，加密算法被设计成能够抵御已知明文攻击攻击强度：唯密文攻击<已知明文攻击<选择明文攻击密码分析攻击的典型方式自适应选择明文攻击：这是选择明文攻击的特殊情况。密码分析者不仅能选择被加密的明文，而且也能基于以前加密的结果修正这个选择。在选择明文攻击中，密码分析者还可以选择一大块被加密的明文，而在自适应选择密文攻击中，可选取较小的明文块，然后再基于第一块的结果选择另一明文块，依此类推。选择密文攻击：密码分析者能选择不同的被加密的密文，并可得到对应的解密的明文，例如密码分析者存取一个防窜改的自动解密盒，密码分析者的任务是推出密钥。两个概念绝对安全，unconditionalsecurity无论花多少时间，攻击者都无法将密文解密原因：攻击者所需要的信息不在密文里。除一次一密外，所有的加密算法都不是绝对安全的计算安全，computationalsecurity破译密码的代价超过密文信息的价值；破译密码的时间超出了密文信息的有效生命期。穷举攻击密钥大小（位）密钥个数每微秒执行一次解密所需时间每微秒执行一百万次解密所需时间32232=4.3109231µs=35.8minutes2.15milliseconds56256=7.21016255µs=1142years10.01hours1282128=3.410382127µs=5.41024years5.41018years1682168=3.710502167µs=5.91036years5.91030years26characters(permutation)26!=4102621026µs =6.41012years6.4106years主要内容数据加密概述传统密码技术（一）替代技术（二）换位技术对称密钥密码技术公钥密码体制数字签名与认证技术加密软件（一）替代技术替代法：将明文字母替换成其他字母、数字或符号的方法；如果把明文看成是0或1的序列，那么密文就是0或1比特序列的另一种表达。包括：（1）凯撒密码（2）单表替代密码（3）多表替代密码（1）凯撒密码（CaesarCipher）由古罗马人JuliusCaesar发明的一种密码体制，它是使用最早的密码体制之一；首先用在军事通信中；替代原理：用字母后的第三个字母代替字母表看作是循环的，即z后面的字母是a明文abcdefghijklmnopqrstuvwxyz密文DEFGHIJKLMNOPQRSTUVWXYZABC凯撒密码映射表中，明文字母中在字母表中的相应位置数为C，（如A=1，B=2，…）形式如下：设k＝3；对于明文P＝computesystems则f（C）=（3+3）mod26=6=Ff（O）=（15+3）mod26=18=Rf（M）=（13+3）mod26=16=P ┆f（S）=（19+3）mod26=22=V密文C=Ek（P）=FRPSXRWHUVBVWHPV。凯撒密码的一般形式将英文字母表左环移k（0≤k<26）位得到替换表，则得一般的Caesar算法。共有26种可能的密码算法（25种可用）将每个字母分配一个数值，如a＝0，b=1等，则算法可表示为：加密算法：C=Ek(P)=(P+k)mod26解密算法：P=Dk(C)=(C–k)mod26凯撒密码的安全性分析凯撒密码的三个特征：加密和解密算法已知需尝试的密钥只有25个所破译的明文语言已知，其意义易于识别大多数情况下，密码算法是已知的，这三个特征使穷举攻击很容易实现抗攻击分析：使明文的语言未知：例如将明文压缩再进行加密加大密钥空间：如允许字母的任意替代（2）单表替代密码不是简单有序地字母移位每个明文字母映射到一个不同的随机密文字母

密钥数目：26！

包括：棋盘密码 仿射密码移位代换密码：凯撒密码 多项式代换密码乘数/采样密码 密钥短语密码单表替代密码分析密钥空间：26!＞4x1026大于56位DES(数据加密标准)的密钥空间貌似安全，实则不然：－基于语言统计规律仍可破译单表替代密码分析举例：字母相对频率分析：英文字母相对频率单表替代密码分析初步分析：解密结果：解决方法：目标-减少密文中的明文结构残留度字母组合加密：playfair密码多表替代密码：Vigenère密码Playfair密码单表替代缺陷是：密文带有原始字母使用频率的一些统计学特征。对策：每个字母提供多种代换。最著名的多表代换密码——Playfair密码:CharlesWheatstone于1854年发明,用其朋友BaronPlayfair命名把明文中的双字母音节作为一个单元并将其转换成密文的“双字母音节”Playfair密钥矩阵

加密结果基于一个5x5字母矩阵从左到右，从上到下：填写密钥单词用其他字母填写剩下的空缺I=JMONARCHYBDEFGI/JKLPQSTUVWXZmonarchy为密钥加/解密步骤加密明文分组（填充）：2个字母／组同行字母对加密：循环向右，ei→FK同列字母对加密：循环向下，cu→EM，xi→AS其它字母对加密：矩形对角线字母，且按行排序，hs→BP，es→IL（或JL）解密加密的逆向操作安全性分析安全性优于简单的单表代换密码：共有26x26个字母对，判断单个字母对困难；字母对的相对频率的统计规律低于单个字母的频率；利用频率分析字母对较困难；虽然明文中字母的统计规律在密文中得到了降低，但密文中仍含有明文的部分结构信息；给定几百个字母，即可被攻破；字母出现的相对频率（3）多表替代密码替代规则：使用一系列相关的单表替代规则密钥决定给定变换的具体规则例如：Vigenère密码（1858）Beaufort密码Vernam密码Vigenère方阵使用一系列单表替代规则密钥决定给定变换的具体规则Vigenère密码示例加密过程：P＝“encodeanddecode”，k＝“mykey”字母序号encodeanddecode明文编码P=4132143401333421434密钥编码k=122410424122410424122410424加密C=1637121827162423727162624728模运算111102密文C=QLMSBQYXHBQAYHC明文中不同位置的相同字母，被映射为不同的字母Vigenère密码示例解密过程：C＝“QLMSBQYXHBQAYHC”，k＝“mykey”字母序号123456789101112131415密文编码C=161112181162423711602472密钥编码k=122410424122410424122410424加密C=4-13214-2340133-234-24143-22模运算133324密文解码C=encodeanddecodeVigenère密码加密过程：数学公式计算设明文P=p1p2…pn，密钥K=k1k2…km，密文C=c1c2…cn加密：ci=(pi+kimodm)mod26；说明：若明文长度大于n，则k重复使用。Vigenère密码解密过程：数学公式计算pi=(ci－kimodm)mod26；安全性分析每个明文字母对应着多个密文字母，明、密文字母不是一一对应关系一条消息中，同样的字母在不同的位置映射成不同的密文；字母的统计规律进一步降低；Vigenère本人建议：密钥与明文一样长；Vigenère代换表中的每一行就是一Caesar密码；安全性分析举例：密文用数字描述后：密码分析思路：集中精力找到密钥长度；采用单表替代分析方法；Germany:Enigma轮转机密码系统ArthurScherbius于1919年发明，4轮Enigma在1944年装备到德国海军，使得英国从1944年2月到12月没有检测到德国潜艇信号。基于多表替代密码的原理；重要性质：反射器使得恩格玛机的加密过程是自反的；一个字母加密后的输出结果绝不会是它自身密码表数量：10万以上（二）换位密码TranspositionCiphers换位：对明文字母的某种置换，采用移位发进行加密；明文中的字母重新排列，位置发生变化；栅栏技术：按对角线的顺序写出明文，以行的顺序读出作为密文易破译矩阵排列法：纯置换密码易识别多次置换：多阶段加密，安全性更高例：明文：meetmeafterthetogaparty写为:mematrhtgpryetefeteoaat读出密文为：MEMATRHTGPRYETEFETEOAAT改进带有密钥再改进：重复加密，多步置换61更加复杂的移位以指定的行将明文写作多行按照密钥指定的列读出Key:Plaintext:Ciphertext:TTNAAPTMTSUOAODWCOIXKNLYPETZ

4312567attackpostponeduntiltwoamxyz62矩阵排列法主要内容数据加密概述传统密码技术对称密钥密码技术Feistel密码结构数据加密标准DES公钥密码体制数字签名与认证技术加密软件对称密码算法数据加密标准（DES）国际数据加密算法（IDEA）高级数据加密标准（AES）对称加密的安全性取决于密钥的安全，而非算法的安全。Alice加密机解密机Bob安全信道密钥源Oscar明文x密文y密钥k明文x密钥k对称加密模型密码学的目的：Alice和Bob两个人在不安全的信道上进行通信，而破译者Oscar不能理解他们通信的内容。回顾代替密码（SubstitutionCipher）：就是明文中的每一个字符被替换成密文中的另一个字符。接收者对密文做反向替换就可以恢复出明文。置换密码（PermutationCipher）：又称换位密码：明文的字母保持相同，但顺序被打乱了。基本思想扩散（Diffusion）:将每一位明文数字的影响尽可能的散布到多个输出密文数字中，更隐蔽明文数字的统计特性。混乱（Confusion）：使得密文的统计特征与明文、密钥之间的关系尽量复杂化。使用标准的算术运算和逻辑运算。Shannon：在理想的密码系统中，密文的所有的统计特性与所使用的密钥独立。Feistel密码结构明文分组分为左右两个部分L0和R0，数据的这两部分通过n次循环处理后，再结合起来生成密文分组；每i次循环都以上一次循环输出比特串的左右两个部分Li-1和Ri-1，以及K产生的子密钥Ki作为输入。子密钥Ki是用子密钥生成算法从密钥K中生成的Li-1Ri-1一个分组LiRiFKi第i次循环Feistel密码结构所有循环的结构都相同，置换在数据的左半部分进行，先对数据的右半部分应用循环函数F，然后对函数输出结果和数据的左半部分取异或(XOR)；循环函数对每次循环都有相同的通用结构，仅仅是每次循环子密钥Ki不同；在置换之后，执行由数据左右两部分互换构成的交换；Feistel密码结构加密过程和解密过程形式化描述分别如下公式所示：

加密:Li=Ri-1；Ri=Li-1F(Ri-1,Ki)

解密:Ri-1=Li；Li-1=RiF(Ri-1,Ki)=RiF(Li,Ki)Feistel的核心参数分组大小密钥长度循环次数子密钥产生算法循环函数DES的产生1974年8月27日，NBS开始第二次征集，IBM提交了算法LUCIFER。1975年3月17日，NBS公开了全部细节。1976年，NBS指派了两个小组进行评价。1976年11月23日，采纳为联邦标准，批准用于非军事场合的各种政府机构。1977年1月15日，“数据加密标准”FIPSPUB46发布。DES的应用1979年，美国银行协会批准使用DES。1980年，美国国家标准局（ANSI）同意DES作为私人使用的标准，称之为DEA（ANSIX.392）1983年，国际化标准组织（ISO）同意将DES作为国际标准，称之为DEA-11998年12月以后，美国政府不再将DES作为联邦加密标准DES特点设计目标：用于加密保护静态储存和传输信道中的数据，安全使用10-15年综合应用了置换、代替等多种密码技术分组密码：分组长度为64位，密钥56位采用feistel结构面向二进制的密码算法加密解密共用一个算法DES算法流程输入64比特明文数据初始置换IP在密钥控制下16轮迭代初始逆置换IP-1输出64比特密文数据交换左右32比特明文IPL0R0fR1＝L0fL1＝R0K1fR2＝L1fL2＝R1K2fR16＝L15fL16＝R15K16IP－1密文L15R15InitialPermutation用56位密钥产生16个56位的子密钥DES加密过程首先把明文分成以64bit为单位的块m，对于每个m,执行如下操作DES(m)=IP-1•T16•T15•.....T2•T1•IP(m)IP，IP-1

：初始置换原数据块，再分成L0和R0R0与第一子密钥k1经函数f运算后，得到的32位输出再与L0异或运算，其结果成为下一轮的R1，R0则为下一轮的L1如此连续运作16轮迭代子密钥生成76DES解密过程DES解密过程与加密过程完全相似，只不过将16次迭代的子密钥顺序倒过来，即m=DES-1(c)=IP-1•T1•T2•.....T15•T16•IP(c)可以证明，DES-1(DES

(m))=m77DES的安全性密钥长度=56比特强力攻击=尝试次差分密码分析=尝试次线性密码分析=尝试次（但是后两种攻击是不实用的）1976年，耗资2000万美元的计算机，可以在一天中找到密钥。1998年，EFF(电子前哨基金会)宣布破译了DES算法，耗时不到三天时间，使用的是25万美元的“DES破译机”。破解密码的时间与密钥长度之间的关系应该注意到的一个事实是，DES经过了可能是当今最多的被分析或被攻击的对象，但未发现任何结构方面的漏洞。DES算法最终之所以被破译的关键是密钥的长度问题。DES总结DES算法对个人用户仍值得信赖DES算法本身没有大的缺陷DES使用的2^56密钥空间不够大，蛮力攻击目前已能够奏效(DESChallenges

III)，所以关键场合不能使用了DES已经不再是推荐标准DES还是AES，或者RC4、RC5、IDEA、BFFree/OpenDES模块仍广泛存在保护和延续DES投资对DES的改造使用现存的软件硬件在强度上提高DES改造思路算法基本函数不能改变否则将不能利用现有的软硬件部署密钥空间得加大密钥过短正是目前DES的主要弱点，加大密钥空间以抵抗穷举攻击三个递进思路： *用2个key，加密2回 *用3个key，加密3回 *用2个key，加密3回两重DES给定明文P和两个加密密钥k1和k2，采用DES对P进行加密E，有 密文 C=EK2(EK1(P))对C进行解密D，有 明文P=DK1(DK2(C))三重DES双密钥的EDE

(Encrypt-Decrypt-Encrypt，加密-解密-加密)模式：

C=EK1(DK2(EK1(P))) 对P加密

P=DK1(EK2(DK1(C))) 对C解密三重DES主要内容数据加密概述传统密码技术对称密钥密码技术公钥密码体制公钥密码算法原理RSA算法其他公钥密码算法数字签名与认证技术加密软件公钥密码算法对称密钥密码系统的缺陷：密钥必须经过安全的信道分配，密钥管理复杂无法用于数字签名非对称密钥密码，也称公开密钥密码，由Diffie,Hellman1976年提出；使用两个密钥，对于密钥分配、数字签名、认证等有深远影响；和DES等对称算法不同，公钥体制的形式和结构导致公钥算法必须使用某种数学结构，而不能再使用替代和置换等初等方法。从形式上看，公钥算法将比对称算法更简洁和易于理解。公钥密码用于加密每个通信实体有一对密钥（公钥，私钥）。使用方式一：A向B发送消息，用B的公钥加密B收到密文后，用自己的私钥解密PlainText加密算法解密算法ABcipherPlainTextB的私钥C的公钥B的公钥任何人向B发送信息都可以使用同一个密钥(B的公钥)加密没有其他人可以得到B的私钥，所以只有B可以解密公钥密码用于签名使用方式二：A向B发送消息，用A的私钥加密（签名）B收到密文后，用A的公钥解密（验证）PlainText加密算法解密算法cipherPlainTextABA的私钥A的公钥公钥密码算法的表示对称密钥密码密钥：会话密钥（Ks）加密函数：C=EKs[P]对密文C，解密函数：DKs[C]，公开密钥(KUa，KRa)加密/签名：C=EKUb[P]，EKRa[P]解密/验证：P=DKRb[C]，DKUa[C]签名和加密同时使用X加密（签名）加密解密解密（验证）XYZYZ=EKUb[Y]=EKUb[EKRa(X)]X=DKUa[Y]=DKUa[DKRb

(Z)]AB产生密钥对产生密钥对KRaKUaKRbKUb对公钥密码算法的要求参与方B容易产生密钥对公钥KUb，私钥KRb已知KUb，发送者A的加密操作是容易的：

C=EKUb(P)已知KRb，接收者B解密操作是容易的:P=DKRb

(C)=DKRb

(EKUb

(P))已知KUb，求KRb是计算上不可行的；已知KUb和C,欲恢复P是计算上不可行的。常见公钥密码算法及应用三种用途：加密/解密：发送方用对方公钥加密，接收方用自己的私钥解密数字签名：发送方用自己的私钥签署报文，接收方用对方的公钥验证对方的签名密钥交换：双方协商会话密钥算法加密/解密数字签名密钥交换RSAYYYDiffie-HellmanNNYDSANYNRSA密码体制1978年，MIT三位年青数学家R.L.Rivest，A.Shamir和L.Adleman用数论构造双钥密码的方法，称作MIT体制，后被广泛称为RSA体制；它既可用于加密、又可用于数字签名；RSA算法的安全性基于数论中大整数分解的困难性；参数选择1.取两个大素数p,q,保密;2.计算n=pq，公开n;3.计算欧拉函数ф(n)=（p-1）(q-1)；4.任意取一个与ф(n)互素的小整数e,即gcd(e,ф(n))=1，1<e<ф(n)e作为公钥公开5.寻找d,使得demodф(n)=1,ed=kф(n)+1

d

作为私钥保密最终：公钥(e,n)，私钥(d,n)，销毁p和q加密解密过程将明文分组，各组长1024比特加密过程C=Memodn解密过程M=Cdmodn其中，公钥(e,n)，私钥(d,n)(1)可以找到e,d,n，使得对所有M<n，Med=Mmodn成立；(2)对所有满足M<n的值，计算Me

和Cd；(3)给定e和n，不可能推出d；RSA算法操作举例密钥产生1.取两个大素数p,q,保密;2.计算n=pq，公开n;3.计算欧拉函数ф(n)=（p-1）(q-1)；4.任意取一个与ф(n)互素的小整数e,即

gcd(e,ф(n))=1，1<e<ф(n)e作为公钥公开5.寻找d,使得

demodф(n)=1,即：ed=kф(n)+1

d作为私钥保密p=17,q=11n=17×11=187Ф(n)=160选择e=77d=160K＋1令k=1,得到求得d=23由此得到公钥{7，187}私钥{23，187}RSA加密解密过程举例RSA算法操作举例公钥{7，187}私钥{23，187}明文输入为88，加密过程C=887mod187，利用模的运算性质：密文输入为11，解密过程M=1123mod187练习1.在使用RSA公钥密码体制中，已截获发给某用户的密文为c＝10，该用户的公钥e＝5，n＝35，那么明文m等于多少？2.利用RSA算法运算，如果p=11,q＝13，e＝103，对明文3进行加密。求d及密文。RSA算法的性能及安全性运算速度：软件实现比DES慢100倍，硬件实现比DES慢1000倍攻击方法蛮力攻击：对所有密钥都进行尝试数学攻击：等效于对两个素数乘积(n)的因子分解对RSA算法的数学攻击实际上等效于对n的乘积分解由于M=Cdmodn,n公开,则需要求出d又由于de≡1modØ(n),e已知需要求出Ø(n)由于Ø(n)=(p-1)(q-1)，所以必须求出p,qn=pq,所以必须对n进行分解因子分解复杂度密钥长(bit)所需的MIPS-年*

1164001295,00051230,000768200,000,0001024300,000,000,0002048300,000,000,000,000,000,000*MIPS-年指以每秒执行1,000,000条指令的计算机运行一年澄清误解公钥算法更安全不能简单比较传统对称算法已经过时事实上，现在使用的是混合密码体制公钥体制避免了传统密钥分配中心带来的麻烦事实上，证书体制有其优点但绝非简单公钥算法就是RSARSA只是当前最重要的公钥算法103公开密钥加密方法1用户A用户BCKeBKdBA查到B的公开加密钥KeB,用它加密M后得到C,将C发给BB收到C以后，用自己保密的解密钥KdB解密C,得到明文M查找找到KeB104方法1缺点任何人都能够冒充用户A给B发消息，B无法察觉用户A用户BCKeBKdB查找找到KeB用户C此消息对用户A可能不利无法保证信息的真实性105公开密钥加密方法2A用自己保密的密钥KdA解密M,得到密文C将C发给BB收到C以后，查A的公开加密钥KeA,用KeA加密C后得到明文M用户A用户BCKdAKeA查找找到KeA106方法2缺点无法保证信息的秘密性用户A用户BCKdAKeA查找找到KeA用户C截获密文用户C获取了明文Maninthemiddleattack:TrudyposesasAlice(toBob)andasBob(toAlice)IamAliceIamAliceRTK(R)-SendmeyourpublickeyTK+AK(R)-SendmeyourpublickeyAK+TK(m)+Tm=K(K(m))+T-TrudygetssendsmtoAliceencryptedwithAlice’spublickeyAK(m)+Am=K(K(m))+A-RMan-in-the-MiddleAttack（中间人攻击）练习A向B发送消息（假设是短消息），设计一种加密方案使得A到B的消息具有保密性，同时保证消息的来源是真实的。用户A用户BCKeBKdB查找找到KeBKdAKeA查找找到KeA公钥密码体制的优缺点优点：解决密钥传递的问题大大减少密钥持有量提供了对称密码技术无法或很难提供的服务（数字签名）缺点：计算复杂、耗用资源大非对称会导致得到的密文变长数字信封数字信封技术使用两层加密体制，内层使用对称加密技术，外层使用非对称加密技术。具体过程为：发送方：采用对称密钥来加密信息内容，然后将此对称密钥用接收方的公开密钥来加密（这部分称数字信封）；将它和加密后的信息一起发送给接收方，接收方：先用相应的私有密钥打开数字信封，得到对称密钥，然后使用对称密钥解开加密信息。数字信封OpenSSLOpenSSL是一个强大的安全套接字层密码库，囊括主要的密码算法、常用的密钥和证书封装管理功能及SSL协议，并提供丰富的应用程序供测试或其它目的使用/OpenSSL工具的使用相关命令：例如opensslgenrsa-outtest.key1024//产生公钥私钥opensslrsa-intest.key-pubout-outtest_pub.key//导出公钥opensslrsautl-encrypt-inhello-inkeytest_pub.key-pubin-outhello.en//用公钥加密指定文件到指定输出opensslrsautl-decrypt-inhello.en-inkeytest.key-outhello.de

//解密OpenSSLAPI的使用主要内容数据加密概述传统密码技术对称密钥密码技术公钥密码体制数字签名与认证技术消息认证的概念散列函数数字签名加密软件问题的引入-通信威胁泄露：把消息内容发布给任何人或没有合法密钥的进程。传输分析：分析通信双方的通信模式伪造：从一个假冒信息源向网络中插入消息。内容修改：消息内容被插入删除变换修改。顺序修改：插入删除或重组消息序列。时间修改：消息延迟或重放。发送方否认：发送方否认发送过消息接收方否认：接收方否认接收过消息加密认证数字签名认证技术现代密码学的最重要的分支就是加密和认证。加密：防止对方获得机密信息（被动攻击）。认证：防止对方的主动攻击，例如伪造，纂改消息等。保密和认证是信息安全的两个不可或缺的内容，他们是两个不同属性的问题。认证不能自动提供保密性，保密性不提供认证功能。消息认证消息认证：消息来自真正的发送方且未被修改（包括顺序和及时性），具体包括：消息的来源消息的完整性消息的序号和时间它包含两方面的含义：（1）验证信息的发送者是真正的而不是冒充的，即数据起源验证；（2）验证信息在传递过程中未被篡改、重放或延迟等。一个纯的认证系统认证系统模型消息认证函数（一）消息加密将明文加密后以密文作为认证；（二）散列函数是一个公开的函数它将任意长的信息映射成一个固定长度的散列值，以散列值作为认证符。常见的散列函数有：MD4、MD5、SHA和SHA-1（一）消息加密函数信息加密函数分两种，一种是常规的对称密钥加密函数，另一种是公开密钥的双密钥加密函数。下图的通信双方是，用户A为发信方，用户B为接收方。用户B接收到信息后，通过解密来判决信息是否来自A，信息是否是完整的，有无窜扰。消息加密函数(1)对称加密：具有机密性，可消息认证，不提供签名如果攻击者获取到密文，并且对密文进行了修改，接收方如何判断收到的密文是被纂改过的？•如何自动确定是否收到的明文可解密为可懂的明文?•一种解决办法是强制明文有某种结构.差错控制：ErrorControl消息加密函数(2)公钥加密：具有机密性，不能提供认证（任何人都可以得到公钥），不提供签名；消息加密函数(3)私钥加密认证和签名，没有机密性A的私钥A的公钥消息加密函数(4)公钥加密体制机密性，可认证和签名加密vs.认证保密性与完整性是两个不同的概念；某些信息只需要真实性（来源与消息），不需要保密性：广播的信息难以使用加密(信息量大)网络管理信息等只需要真实性政府/权威部门的公告加密算法代价大（尤其是公钥加密算法）；因此，认证函数与保密函数的分离能提供功能上的灵活性！思路：散列函数散列函数是一个公开的函数它将任意长的信息映射成一个固定长度的散列值，以散列值作为认证符。消息验证码/认证符/消息摘要散列函数散列函数（又称杂凑函数、哈希函数、数字指纹、压缩函数、数据鉴别码）：是对不定长的输入产生定长输出的一种特殊函数：h=H(M)

其中：M:变长消息h=H(M)是定长的散列值（或称消息摘要）

H：散列函数，是公开的；散列值在信源处被附加在消息上，接收方重新计算散列值来确认消息未被篡改。散列函数的基本性质单向性：对于预先给定的散列值找到对应的数据块在计算上不可行抗冲突性：找不到不同的数据块对应相同的散列值散列函数的性质(1)H能用于任何大小的数据分组，都能产生定长的输出，例如，512比特(2)对于任何给定的M，H(M)要相对易于计算；(3)单向性：对任何给定的散列码h，寻找M使得H(M)=h在计算上不可行；(4)抗弱冲突：给定M，要寻找另一信息M′，满足H(M′)＝H(M)在计算上不可行；(5)抗强冲突：要寻找不同的信息M和M′，满足H(M′)＝H(M)在计算上不可行，例如生日攻击。找到强冲突要比找到弱冲突更容易，因此，实现具有抗弱冲突性的散列函数要难于具有抗强冲突性的函数散列函数问题生日问题：一个教室中，最少应有多少学生，才使至少有两人具有相同生日的概率不小于1/2？实际上只需23人,即任找23人，从中总能选出两人具有相同生日的概率至少为1/2。思考CRC是否可以作为散列函数？严格意义上，不可以；主要用于通信传输中对错误码的校验，而非安全领域；压缩算法（ZIP,RAR）是否可以作为散列函数？否，压缩算法是可逆函数，不满足散列函数单向性的要求(b)Usingpublic-keyxxyHashKeyEncryptDecrypt(a)Usingsecret-keyEncryption使用对称密钥算法加密Hashencryption(digitalsignature)使用公钥算法加密HASHSecretValue（秘密值）

isaddedbybothpartiestomessagebeforethe“hash,”functionisusedtogettheMessageIntegrityCheck(MIC).Itisremovedbeforetransmission.MICMICItiscriticalthataforger（伪造者）cannotcomposeadifferentmessagethatwouldproducethesameMICvalue.不使用加密算法，但仍然安全传输Hash值134极其不安全安全Hash函数的一般结构散列函数MD5

（消息摘要算法5）：对输入消息（任意长）按照512位进行分组处理，输出128位消息摘要SHA-1（安全哈希算法-5）：输入长度小于2^64位消息，按512位进行分组处理，输出160位消息摘要SHA-256、SHA-383和SHA-512提供更长的消息摘要，大小分别是256位、383位和512位；RIPEMD-160：对输入消息（任意长）按照512位进行分组处理，输出160位消息摘要MD5（消息摘要算法）RonRivest于1990年提出了一个称为MD4的散列函数。他的设计没有基于任何假设和密码体制，不久，他的一些缺点也被提出。为了增强安全性和克服MD4的缺陷，Rivest于1991年对MD4作了六点改进，并将改进后的算法称为MD5MD5算法：将明文按512比特进行分组，即MD5中的b=512bit，经填充后信息长度为512的倍数（包括64比特的消息长度）。100…0消息K比特Lx512比特1到512比特的填充消息长度Y0512bitHMD5512128CV0=VIY1512bitHMD5512128CV1Yq512bitHMD5512128CVqYL-1512bitHMD5512128CVlL-1……消息摘要128bitMD5的框图破解MD5？2004年8月，在美国加州圣巴巴拉召开的年度密码学国际会议上，王小云首次宣布了她和她的研究小组近年来的研究成果——对MD5、HAVAL－128、MD4和RIPEMD等四个著名密码算法的破译结果。在王小云教授仅公布到他们的第三个惊人成果的时候，会场上已经是掌声四起，报告不得不一度中断。报告结束时，与会者长时间热烈鼓掌，部分学者起立鼓掌致敬，这在密码学会议上是少见的盛况。之后，王小云又继续发展她的研究，于2005年初破解了美国国家标准与技术研究所（NIST）为美国政府及商企界制定的SHA-1密码算法。MD5的破解使用“穷举”法：即程序在一定的数据范围内产生一系列数据组合进行MD5运算，再把运算结果与获取的摘要进行比较，如果两者相同，就被定义为“破解”了。MD5在线破解安全散列算法（SHA）目前，MD5被认为是易受攻击的（很容易遭遇强碰撞的生日攻击），因此，有必要用一个具有更长散列码和更能抗击已知密码分析攻击的散列函数来代替现在流行的MD5。现在已经有两个散列码长度为160比特的替代者SHA-1和RIPEMD-160。我们了解SHA-1即可。安全散列算法SHA(SecureHashAlgorithm)是由美国国家标准和技术协会提出的，并作为联邦信息处理标准在1993年公布。1995年又发布了一个修订版，通常称为SHA-1。SHA是基于MD4算法的。MD5与SHA-1对比

MD5SHA-1消息长度128bit160bit分组长度512bit512bit步骤数6480消息最大长度264-1速度较快慢问题的提出1996年7月9日，北京市海淀区法院审理国内第一起电子邮件侵权案。此案的原、被告均系北大心理学系93级女研究生。4月9日，原告薛燕戈收到美国密执安大学教育学院通过互联网发给她的电子邮件，内容是该学院将给她提供1.8万美元金额奖学金的就学机会。此后，久等正式通知，但杳无音训，蹊跷之中委托在美国的朋友去密执安大学查询。在4月27日查到密执安大学收到一封北京时间4月12日10时16分发出的署名薛燕戈的电子邮件，表示拒绝该校的邀请。因此密执安大学以将原准备给薛的奖学金转给他人。经调查，证明以原告名义发送电子邮件的是被告。数字签名消息认证用于防止第三方攻击；数字签名用于防止通信对方的欺骗或抵赖（否认）数字签名：一种基于机密技术的认证技术，用于确认发送者身份和消息完整性的一个加密的消息摘要。分类：直接数字签名需仲裁的数字签名数字签名应满足的基本条件签名者不能否认自己的签名；接收者能够验证签名，而其他任何人都不能伪造签名；当关于签名的真伪发生争执时，存在一个仲裁机构或第三方能够解决争执。直接签名直接数字签名仅涉及通信方。假设接收方知道发方的公钥。数字签名通过使用发方的私钥对整个消息进行加密或使用发方的私钥对消息的散列码（消息摘要）进行加密来产生。如何实现？直接签名--RSA数字签名机制直接数字签名仅涉及通信方RSA是最流行的一种加密标准，许多产品的内核都有RSA的软件和类库，RSA与Microsoft、IBM、Sun和Digital都签订了许可协议，使其在生产线上加入了类似的签名特性。与DSS不同，RSA既可用于加密数据，也可用于身份认证。RSA数字签名体制MEH||MEKRa(HM))HD比较KRaKUa数字签名在接收方具体步骤发送方(1)A把发送给B的消息作为散列函数的输入，生成消息摘要；(2)A用自己的私钥加密消息摘要，生成数字签名；(3)A将消息与数字签名一起发送到B接收方：(4)B接收到后，将消息和数字签名进行拆分；(5)B用A的公钥对数字签名进行解密，得到消息摘要(6)B将收到的消息作为A的散列函数的输入，产生消息摘要(7)B比较两个消息摘要，若相同，验证成功思考以上过程可以提供什么样的安全服务？完整性服务、发送方的身份认证和发送方的不可抵赖服务。课堂练习1.实现消息认证有两种方式，分别是使用加密函数和使用认证函数，分别举例说明。并比较两类函数应用在消息认证上的特点。2.列举散列函数的性质。课堂练习3：说明以上认证函数的应用所提供的安全性服务S:双方共享的秘密值课堂练习3：说明以上认证函数的应用所提供的安全性服务课堂练习4.假设Oscar可以看到Alice到Bob之间的所有消息，并且能够获取到数字签名的公钥。A)（消息完整性）Alice将消息x=“Transfer$1000toMark”以明文形式，加上auth(x)一起发送到Bob。Oscar截获上述内容，并将“Mark”替换为”Oscar”，Bob能否检测到？说明原因。B)（重放）Alice将消息x=“Transfer$1000toOscar”以明文形式，加上auth(x)一起发给Bob。Oscar观测到后，重复100遍发送到Bob，Bob是否能够检测到？如果不能，尝试说明解决方法。C)（认证中Bob存在欺骗行为）Bob声称收到了Alice的消息x=“Transfer$1000fromAlicetoBob”，并附带有效的数字签名auth(x)。但Alice表示并没有发送过上述内容。说明Alice如何证实是哪种情况？D)（发送者认证，同时第三方存在欺骗）Oscar声称Bob发送了消息x，并附带数字签名auth(x)，但Alice声称它也发送了上述内容。说明Bob如何区分是哪种情况？课堂练习5.请依据加密技术和数字签名技术原理，设计一个同时能够防窃听、防纂改、防抵赖并可具有身份认证功能的加/解密方案。依次写出发送方和接收方的处理步骤，并用公式表达，并文字进行说明。如：M，H，E，K，KUX（X表示通信方）、KRX发送方使用H对消息M生成消息摘要：H(M)一个加密通信实例的演化假设服务器和客户端要进行通信，且协商使用RSA来对通信进行加密以保证谈话内容的安全；问题如何知道每次通信或交易中所使用的密钥就是用户的密钥对而非伪造呢？数字证书：需要验证公钥和用户之间的关系：CA：数字证书颁发中心注意：数字证书并不是身份证，只是身份证上的公章，表示身份证是有效的CertificateAuthoritygeneratesthe“signature”thatisaddedtoraw“Certificate”MICHashRaw“Certificate”

包括用户名，公钥，有效日期等RawCert.SignedCert.第一步：产生证书的Hash值，也称为指纹第二步：使用CA的私钥加密指纹SignedCertificateRecipientcanverifysignatureusingCA’spublickey.CASecureArea数字证书构成证书的发布机构证书的有效期公钥证书所有者（Subject）签名所使用的算法对指纹进行签名，生成证书的数字签名指纹以及指纹算法指纹：计算整个证书的消息摘要，保证证书的完整性（未被篡改）证书使用者用指纹算法根据证书明文产生本地指纹，并和证书中的指纹进行对比在浏览器中查看数字证书向CA申请数字证书假设“ABCCompany”花了1000块钱，向一个证书发布机构“SecureTr