网络通讯与信息安全课件 10 信息安全技术

1密码学基础1.1密码学的起源、发展及应用1.1.1信息传递的一般问题信源、信道、信宿攻击的种类：中断（Interruption)（干扰）截取（Interception)(侦听）修改（Modification）伪造（Fabrication)角色：通信双方、可信第三方、不可信第三方介质：软件、硬件、数据10、1密码体制1InterruptionInterceptionFabricationModificationNormalFlowInformationSourceInformationDestination1.1.1信息传递的一般问题21.1.2数据的性质Interruption--Interception--Modification--Fabrication--

AvailabilityAvailability

ConfidentialityConfidentiality

Integrity

Integrity

Authenticity

Authenticity31.1.3攻击的类型被动攻击窃听获取消息内容流量分析主动攻击中断修改伪造破坏可用性破坏完整性破坏真实性4可信的第三方（秘密信息的判定者、分发者）MessageSecretInformationMessageSecretInformationSecurity-relatedTransformationSecurity-relatedTransformationOpponentPrincipalPrincipal1.1.4一个通用的网络安全模型5加密（编码）解密（解码）加密过程：对明文数据进行的可逆变换的过程，变换为加密变换。加密变换由一个参数k1控制，叫加密密钥。解密过程：恢复明文的过程为解密过程，其变换称为解密变换，它也由一个参数k2控制叫解密密钥。密码系统：用于加密与解密的系统密码员与密码分析员明文：变换前有意义的数据明文空间：所有可能的明文组成的集合密文：变换后表面上杂乱无章的数据密文空间：所有可能密文组成的集合称为密文空间。加密解密明文密文原来的明文1.1.5密码学术语61.1.5密码学术语加密解密明文密文原来的明文加密解密明文密文原来的明文加密解密明文密文原来的明文KKKEKD71.1.6保密系统的shannon模型CryptanalystMessagesourcecDestinationKeysourceEncryptionalgorithmDecryptionalgorithmPCPP’K’SecurechannelKC=EK(M)M=DK(C)P’estimationofPK’estimationofK8目标：试图破译单条消息试图识别加密的消息格式，以便借助直接的解密算法破译后续的消息试图找到加密算法中的普遍缺陷（无须截取任何消息）条件与工具：已知加密消息，已知加密算法，截取到明文、密文中已知或推测的数据项，数学或统计工具和技术，语言特性，计算机，技巧与运气。加密算法的好与坏—破译难度-理论难度，如解密运算需1012年（分析技巧可以降低破译代价）-运算能力，飞速发展1.1.7密码分析－－目标9破译以下密文：wuhdwb

lpsrvvleohTREATYIMPOSSIBLECi=E(Pi)=Pi+3加密算法：字母表：(密码本）ABCDEFGHIJKLMNOPQRSTUVWXYZdefghijklmnopqrstuvwxyzabc1.1.7密码分析－－恺撒密码举例：恺撒密码10恺撒密码的特点单字母密码（简单替换技术）简单，便于记忆缺点：结构过于简单，密码分析员只使用很少的信息就可预言加密的整个结构已知加密与解密算法C=E(p)=(p+k)mod(26)p=D(C)=(C-k)mod(26)25个可能的密钥k,适用Brute-ForceCryptanalysis明文已知且易于识别1.1.7密码分析－－恺撒密码111.1.7密码分析－－恺撒密码例:

PHHWPHDIWHUWKHWRJDSDUWB1 oggv

og

chvgt

vjg

vqic

rctva2 nffu

nf

bgufs

uif

uphb

qbsuz3 meetmeafterthetogaparty4 lddsldzesdq

sgd

snfz

ozqsx56...25 qiix

qi

ejxivxlixske

tevxc12其它单字母替换使用密钥keyABCDEFGHIJKLMNOPQRSTUVWXYZkeyabcdfghijlmnopqrstuvwxzspectacularABCDEFGHIJKLMNOPQRSTUVWXYZspectaulrbdfghijkmnoqvwxyz泄露给破译者的信息更少1.1.7密码分析－－其他单字母替换13对字母进行无规则的重新排列

E(i)=3*imod26ABCDEFGHIJKLMNOPQRSTUVWXYZadgjmpsvybehknqtwzcfilorux单字母变换的特点：任意替换：26！>4x1026可能的key,大于56位DES的密钥空间。基于语言统计规律仍可破译1.1.7密码分析－－单字母变换141.1.7密码分析－－英文字母频度表RelativeFrequencyoflettersinEnglishText151.1.7密码分析－－字母频度表举例例：UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ16多字母替换密码--平稳分布单字母替换E1和E2,分别用于明文信息中奇数和偶数位置的字符，从而打乱密文中的字母分布频率特性（通常E2应为的E1补充）1.1.7密码分析－－多字母替换密码例1：E1(a)=a E2(a)=25-aItwasthebestoftimes,itwastheworstoftimes…Ig

wzs

ghv

bvsg

ou

trmvs

rt

dah

tse

doisg

ou

trmvs…ABCDEFGHIJKLMNOPQRSTUVWXYZZyxwvutsrqponmlkjihgfedcba17例2：

E1(T)=a,E2(T)=b;E1(X)=b,E2(X)=aE1(a)=(3*a)mod26E2(a)=((5*a)+13)mod26)012345678910111213141516171819202122232425abcdefghijklmnopqrstuvwxyzTREATYIMPOSSIBL

E1.1.7密码分析－－多字母替换密码ftumnfdyvfczyshh18基本思想：扩大排列数目，轮流使用三种排列，则平滑分布的机会会大大增加。若三种排列效果好，则四种的效果很好，五种则更好。最大26种排列，这样，可以将一个明文字母编码成任意多个密文字母。维基尼亚表：26x26矩阵表示26种排列组合

abcdefghijklmnopqrstuvwxyzA abcdefghijklmnopqrstuvwxyz 0B bcdefghijklmnopqrstuvwxyza 1C cdefghijklmnopqrstuvwxyzab 2D defghijklmnopqrstuvwxyzabc 3E efghijklmnopqrstuvwxyzabcd 4F fghijklmnopqrstuvwxyzabcde 5G ghijklmnopqrstuvwxyzabcdef 6H hijklmnopqrstuvwxyzabcdefg 7I ijklmnopqrstuvwxyzabcdefgh 81.1.7密码分析－－Viginere维基尼亚表19

abcdefghijklmnopqrstuvwxyzJ jklmnopqrstuvwxyzabcdefghi 9K klmnopqrstuvwxyzabcdefghij10L lmnopqrstuvwxyzabcdefghijk11M mnopqrstuvwxyzabcdefghijkl12N nopqrstuvwxyzabcdefghijklm13O opqrstuvwxyzabcdefghijklmn14P pqrstuvwxyzabcdefghijklmno15Q qrstuvwxyzabcdefghijklmnop16R rstuvwxyzabcdefghijklmnopq17S stuvwxyzabcdefghijklmnopqr18T tuvwxyzabcdefghijklmnopqrs19U uvwxyzabcdefghijklmnopqrst20V vwxyzabcdefghijklmnopqrstu21W wxyzabcdefghijklmnopqrstuv22X xyzabcdefghijklmnopqrstuvw23Y yzabcdefghijklmnopqrstuvwx24Z zabcdefghijklmnopqrstuvwxy251.1.7密码分析－－Viginere维基尼亚表20例：密钥=julietjulie

tjuli

etjul

ietju

lietj

uliet

julie

BUTSOFTWHATLIGHTTHROUGHYONDERWINDOWkoeas

ycqsi-------------------------1.1.7密码分析－－Viginere维基尼亚表211.1.7密码分析－－其他方法

Message：Iamateacher!CipherText：421123114451113132512422密码分析的例：

wklv

phvvdjh

lv

qrw

wrr

kdug

wr

euhdn

T-------------OTTOO----TO-----2.先考虑英语中的短词，如：amistobehewe…,andareyoushe等1.空格给出了分词的重要信息（通常实用中将空格删除，甚至通常将字符分5个一组书写。）3.重要线索：wrr,英文中常用xyy结构的单词只有see和too,次常用的单词还有add,odd,off，特别生疏的单词woo和gee4.单词lv是wklv的结尾，有可能是双字母单词SO,IS,IN等等….T-SO不可能;q=N,IN不可能。Lv可能是IS.T------------NOTTOO----TO-----T-IS-------ISNOTTOO----TO-----1.1.7密码分析23替换是密码学中有效的加密方法。20世纪上半叶用于外交通信。破译威胁来自频率分布重合指数考虑最可能的字母及可能出现的单词重复结构分析及克思斯基方法持久性、组织性、创造性和运气1.1.7密码分析－－总结24Shannon特性（1949）所需的保密程度决定了用于加密和解密过程的相应的工作量密钥的组或加密算法应该不受其复杂性的影响处理的实现应尽可能简单编码中的错误不应传播及影响后面的消息加密后正文的尺寸不应大于明文的尺寸。1.1.7密码分析－－安全密码的特性25所谓传统的密码体制又称常规密钥密码体制，即加密密钥与解密密钥是相同的。对称密钥密码体制从加密模式上可分为序列密码和分组密码两大类。序列密码一直是作为军事和外交场合使用的主要密码技术之一，它的主要原理是，通过有限状态机产生性能优良的伪随机序列，使用该序列加密信息流，（逐比特加密）得到密文序列，所以，序列密码算法的安全强度完全决定于它所产生的伪随机序列的好坏。衡量一个伪随机序列好坏的标准有多种，比较通用的有著名的Golamb的三个条件，Rueppel的线性复杂度随机走动条件，线性逼近以及产生该序列的布尔函数满足的相关免疫条件等。产生好的序列密码的主要途径之一是利用移位寄存器产生伪随机序列。2.传统的密码体制262.1序列密码－－线性移位寄存器f(aj-1,aj-2,…,aj-n)aj-1aj-2aj-3aj-n+1aj-n…c0c1c2cn-2cn-1输出时间脉冲f(aj-1,……,aj-n)=c0aj-3……

cn-1aj-n272.1序列密码－－线性移位寄存器f(aj-3,aj-2,aj-1)aj-3aj-2aj-1C0=1C1=0C2=1输出f(aj-1,aj-2,aj-3)=c0aj-3c1aj-2c2aj-1=aj-3aj-1 00111010028例：一次一密密码体制292.1序列密码－－工作原理假设m＝

m0m1m2……是一个待加密的明文序列，k＝k0k1k2……是一个与明文序列等长的二元伪随机序列，称为密钥序列。明文序列m＝

m0m1m2……密钥序列k＝

k0k1k2……密文序列c＝

c0c1c2……序列密码的加密过程明文序列m＝

m0m1m2……密钥序列k＝

k0k1k2……密文序列c＝

c0c1c2……序列密码的解密过程302.2分组密码分组密码的工作方式是将明文分成固定长度的组（块），如64比特一组，用同一密钥和算法对每一块加密，输出也是固定长度的密文。例如DES密码算法的输入为64比特明文，密钥长度56比特，密文长度64比特。设计分组密码算法的核心技术是：在相信复杂函数可以通过简单函数迭代若干圈得到的原则下，利用简单圈函数及对等运算，充分利用非线性运算。312.2分组密码－－DES加密算法的背景发明人：美国IBM公司W.Tuchman和C.Meyer1971-1972年研制成功。基础：1967年美国HorstFeistel提出的理论产生：美国国家标准局（NBS)1973年5月到1974年8月两次发布通告，公开征求用于电子计算机的加密算法。经评选从一大批算法中采纳了IBM的LUCIFER方案。标准化：DES算法1975年3月公开发表，1977年1月15日由美国国家标准局颁布为数据加密标准（DataEncryptionStandard），于1977年7月15日生效。美国国家安全局（NSA,NationalSecurityAgency)参与了美国国家标准局制定数据加密标准的过程。NBS接受了NSA的某些建议，对算法做了修改，并将密钥长度从LUCIFER方案中的128位压缩到56位。1979年，美国银行协会批准使用DES。1980年，DES成为美国标准化协会(ANSI)标准。1984年2月，ISO成立的数据加密技术委员会(SC20)在DES基础上制定数据加密的国际标准工作。32为二进制编码数据设计的，可以对计算机数据进行密码保护的数学运算。64位明文变换到64位密文，密钥64位，实际可用密钥长度为56位。DES使用56位密钥对64位的数据块进行加密，并对64位的数据块进行16轮编码。与每轮编码时，一个48位的“每轮”密钥值由56位的完整密钥得出来。DES用软件进行解码需用很长时间，而用硬件解码速度非常快。幸运的是，当时大多数黑客并没有足够的设备制造出这种硬件设备。在1977年，人们估计要耗资两千万美元才能建成一个专门计算机用于DES的解密，而且需要12个小时的破解才能得到结果。当时DES被认为是一种十分强壮的加密方法。但是，当今的计算机速度越来越快了，制造一台这样特殊的机器的花费已经降到了十万美元左右，而用它来保护十亿美元的银行间线缆时，就要存细考虑了，另一方面，如果只用它来保护一台服务器，那么DES确实是一种好的办法，因为黑客绝不会仅仅为入侵一个服务器而花那么多的钱破解DES密文。由于现在已经能用二十万美元制造一台破译DES的特殊的计算机，所以现在对要求"强壮"加密的场合已经不再适用了。2.2分组密码－－DES概述33确定一种新的加密法是否真的安全是极为困难的，何况DES的密码学缺点只是密钥长度相对比较短，所以人们并没有放弃使用DES，而是想出了一个解决其长度方法，即采用三重DES，。这种方法用两个密钥对明文进行三次加密，假设两个密钥是K1和K2。1.用密钥K1进行DES加密。2.用K2对步骤1结果进行DES加密。3.用步骤2的结果使用密钥K1进行DES加密。这种方法的缺点，花费是原来三倍，但从另一方面来看，三重DES的112位密钥长度是很"强壮"的加密方式了。2.2分组密码－－三重DES34DES可提供72，000，000，000，000，000个密钥，用每微秒可进行一次DES加密的机器来破译密码需两千年。自从DES算法颁布以来，世界各地相继出现了多种密码算法，之所以出现这些算法，有政治原因和技术原因，各国在商用方面都需要自己设计的密码算法，不能依靠外国的算法。这些算法有：LUCIFER算法，Madryga算法，NewDES算法，FEAL-N算法，REDOC算法，LOKI算法，KHUFU算法，KHAFRE算法，RC2及RC4算法，IDEA算法，MMB算法，CA-1.1算法，SKIPJACK算法，Karn

算法以及MDC算法等。其中多数算法为专利算法。2.2分组密码－－其他的DES算法变体35清华大学研制开发了TUC系列密码算法，已申请国家专利。1.对称密码算法（专利）TUC，密钥长度：128-256Bit2.非对称密码算法，椭圆曲线密码系统，密钥长度：104-185Bit3.Hash函数HAS,128Bit4.证书系统5.改进的具有公钥系统的Kerberos系统2.2分组密码－－TUC算法36DES的两个主要弱点：密钥容量：56位不太可能提供足够的安全性S盒：可能隐含有陷井（Hiddentrapdoors）DES的半公开性：S盒的设计原理至今未公布2.2分组密码－－DES算法的公开性与脆弱性37可变的密钥长度数据相关的圈数密钥相关的圈数密钥相关的S盒变量F可变长明文/密文块长度可变圈数每圈操作作用于全部数据2.2分组密码－－先进对称分组加密算法的特点381.有很强的保密强度且经受住时间的检验和攻击。2.加密速度快，可用硬件加密。2.2分组密码－－常规密码体制密码的优点：392.2分组密码－－DES算法详解64位码64位码初始变换逆初始变换乘积变换明文密文输入输出IPIP-1402.2分组密码－－初始变换IP输入（64位）58504234261810260524436282012462544638302214664564840322416857494133251791595143352719113615345372921135635547393123157输出（64位）初始变换IPL0（32位）R0（32位）412.2分组密码－－迭代过程左32位右32位Li-1Ri-1选择E48位(明文)64位密钥作第i次迭代的计算机子密钥Ki密钥程序表48位(密钥)8组6位码S1S2S8模2加选择函数输入：6位输出：4位+++++…+++++422.2分组密码－－迭代过程32位置换32位32位LiRi左32位右32位Ri-1Li-1模2加+++++...++++++乘积变换中的一次迭代432.2分组密码－－逆初始变换IP-1置换码组输入（64位）40848165624643239747155523633138646145422623037545135321612936444125220602835343115119592734242105018582633141949175725输出（64位）逆初始变换IP-1442.2分组密码－－DES算法详解64位码64位码初始变换逆初始变换L0明文密文输入输出IPIP-1R0452.2分组密码－－密钥表的计算逻辑64位密钥置换选择1C0(28位)D0(28位)循环左移循环左移C1(28位)D1(28位)置换选择2K1(48位)(56位)循环左移循环左移Ci(28位)Di(28位)置换选择2Ki(48位)(56位)密钥表的计算逻辑循环左移：119121102321124212252132621427215282161462.2分组密码－－DES算法详解57494133251791585042342618102595143352719113605244366355473931331576254463830221466153453729211352820124置换选择1密钥（64位）C0(28位)D0(28位)472.2分组密码－－DES算法详解Ci(28位)Di(28位)1417112415328156211023191242681672720132415231374755304051453348444939563453464250362932Ki(48位)置换选择2482.2分组密码－－DES算法详解加密函数(A,Ki)A(32位)加密时A=Ri;解密时A=Li;选择运算E48位结果Ki+选择函数组(S1~S8)32位结果(A,Ki)置换运算P32位492.2分组密码－－DES算法详解A32位3212345456789891011121312131415161716171819202120212223242524252627282928293031321选择运算E选择运算E的结果48位加密函数的选择运算E502.2分组密码－－DES算法详解选择函数的输出（32位）1672021291228171152326518311028241432273919133062211425置换P加密函数的结果（32位）512.2分组密码－－DES算法详解

01234567891011121314150

14413121511831061259071

01574142131106121195382

41148136211151297310503

1512824917511314100613S11

0110

0

1020010输入6位输出4位使用选择函数S1的例子522.2分组密码－－DES算法加解密方程L0R0←IP(明文)L1←R0

R1←L0(R0,K1)L2←R1

R2←L1(R1,K2)……L16←R15

R16←L15(R15,K16)密文←IP-1(R16L16)加密方程：L0R0←IP(<64位明文>)Ln←Rn-1Rn←Ln-1(Rn-1,Kn)<64位密文>←IP-1(R16L16)解密方程：R16L16←IP(<64位密文>)Rn-1←LnLn-1←Rn(Ln,Kn)<64位明文>←IP-1(L0R0)531997年1月28日美国RSA数据安全公司悬赏“秘密密钥挑战”竞赛48位的RC5313小时/3500台计算机1997年3月13日Rocke

Verser设计一个攻击程序（DESCHALL），参加的志愿者有78516个，第96天（6月17日晚10：39）MichaelSanders破译成功，获1万美元奖金。搜索量为24.6%。2.2分组密码－－对DES攻击结果及其启示54密钥长度(bit) 穷举时间40 78秒48 5小时56 59天64 41年72 10，696年80 2，738，199年88 700，978，948年96 179，450，610，898年112 11，760，475，235，863，837年128 770，734，505，057，572，442，069年2.2分组密码－－对DES攻击结果及其启示DESCHALL搜索速度估算55IDEA加密算法1991年赖学佳和JamesMasseyofSwissFederalInstituteofTechnology64位分组，128位密钥，8圈Daemen发现该算法有多达251个弱密钥

BLOWFISHBruceSchneier1995发表,64位分组,最大到448位可变长密钥。Fast,compact,simple,variablysecure.RC5、RC2RonRivest开发，可变长加密算法64bitsblock,8-1024bitskeyusedinS/MIMEwith40-64-128-bitkeysizes2.2分组密码－－其它加密算法RC2562.2分组密码－－其它加密算法573、公开钥密码体制－概述1976年Diffie和Hellman以及Merkle分别提出了公开密钥密码体制的思想，这不同于传统的对称密钥密码体制，它要求密钥成对出现，一个为加密密钥(e)，另一个为解密密钥(d)，且不可能从其中一个推导出另一个。自1976年以来，已经提出了多种公开密钥密码算法，其中许多是不安全的，一些认为是安全的算法又有许多是不实用的，它们要么是密钥太大，要么密文扩展十分严重。多数密码算法的安全基础是基于一些数学难题，这些难题专家们认为在短期内不可能得到解决。因为一些问题(如因子分解问题)至今已有数千年的历史了。583、公开钥密码体制－概述公钥加密算法也称非对称密钥算法，用一对密钥：一个公共密钥和一个专用密钥。用户要保障专用密钥的安全；公共密钥则可以发布出去。公共密钥与专用密钥是有紧密关系的，用公共密钥加密的信息只能用专用密钥解密，反之亦然。由于公钥算法不需要联机密钥服务器，密钥分配协议简单，所以极大简化了密钥管理。除加密功能外，公钥系统还可以提供数字签名。公共密钥加密算法主要有:RSA(Receive、Shamir、Adelman)、Fertezza、EIGama等。593、公开钥密码体制－公钥系统的优缺点公用密钥的优点就在于，也许你并不认识某一实体，但只要你的服务器认为该实体的CA是可靠的，就可以进行安全通信，而这正是Web商务这样的业务所要求的。例如信用卡购物。服务方对自己的资源可根据客户CA的发行机构的可靠程度来授权。目前国内外尚没有可以被广泛信赖的CA。美国Natescape公司的产品支持公用密钥，但把Natescape公司作为CA。由外国公司充当CA在我国是一件不可想象的事情。公共密钥方案较保密密钥方案处理速度慢，因此，通常把公共密钥与专用密钥技术结合起来实现最佳性能。即用公共密钥技术在通信双方之间传送专用密钥，而用专用密钥来对实际传输的数据加密解密。另外，公钥加密也用来对专用密钥进行加密。603、公开钥密码体制－公钥系统的特点公开/私有密钥与单独的密钥不同，它使用相互关联的一对密钥，一个是公开密钥，任何人都可以知道，另一个是私有密钥，只有拥有该对密钥的人知道。公钥系统的特点：加密与解密由不同的密钥完成 加密:XY:Y=EKU(X)

解密:YX:X=DKR(Y)=DKR(EKU(X))知道加密算法,从加密密钥得到解密密钥在计算上是不可行的两个密钥中任何一个都可以用作加密而另一个用作解密(不是必须的) X=DKR(EKU(X))=EKU(DKR(X))613、公开钥密码体制－RSA加密算法公钥加密算法中使用最广的是RSA。RSA使用两个密钥，一个公共密钥，一个专用密钥。如用其中一个加密，则可用另一个解密，密钥长度从40到2048bit可变，加密时也把明文分成块，块的大小可变，但不能超过密钥的长度，RSA算法把每一块明文转化为与密钥长度相同的密文块。密钥越长，加密效果越好，但加密解密的开销也大，所以要在安全与性能之间折衷考虑，一般1024位是较合适的。RSA的一个比较知名的应用是SSL。623、公开钥密码体制－RSA加密算法简介RSA公开密钥密码系统公开密钥：n=pq，(p，q分别为两个互异的大素数，p，q必须保密)e与∮(n)=(p-1)(q-1)互素秘密密钥：d=e-1(mod(p-1)(q-1))公开密钥：KU

＝（n，e）私有密钥：KR

＝（n，d)加密过程：c=me(modn)其中m为明文，c为密文解密过程：m=cd(modn)633、公开钥密码体制－加解密过程643、公开钥密码体制－鉴别过程653、公开钥密码体制－RSA加密算法举例现在,用一个简单的例子来说明RSA公开密钥密码系统的工作原理。取两个质数p=11,q=13,p和q的乘积为n=p×q=143,算出另一个数z=(p-1)×(q-1)=120;再选取一个与z=∮(n)=(p-1)(q-1)=120互质的数,例如e=7(称为“公开指数”),对于这个e值,可以算出另一个值d=e-1(mod(p-1)(q-1))=103(称为“秘密指数”)满足e×d=1modz;其实7×103=721除以120确实余1。(n,e)和(n,d)这两组数分别为"公开密钥"和"秘密密钥。"663、公开钥密码体制－RSA加密算法举例设想张小姐需要发送机密信息(明文,即未加密的报文)s=85给李先生,她已经从公开媒体得到了李先生的公开密钥(n,e)=(143,7),于是她算出加密值c=semodn=857mod143=123并发送给李先生。李先生在收到“密文”(即经加密的报文)c=123后,利用只有他自己知道的秘密密钥(n,d)=(143,103)计算123103mod143,得到的值就是明文(值)85,实现了解密。所以,李先生可以得到张小姐发给他的真正的信息s=85。673、公开钥密码体制－RSA安全性依据RSA的安全性是基于加密函数ek(x)=xe(modn)是一个单向函数，所以对攻击的人来说求逆计算不可行。而Bob能解密的陷门是分解n=pq，知

(n)=(p-1)(q-1)。从而用欧氏算法解出解密私钥d.（猜想：攻破RSA与分解n是多项式等价的。然而，这个猜想至今没有给出可信的证明！！！）整数n的十进制位数因子分解的运算次数所需计算时间（每微秒一次）

50 1.4x1010 3.9小时 75 9.0x1012 104天 100 2.3x1015 74年

200 1.2x1023 3.8x109年 300 1.5x1029 4.0x1015年

500 1.3x1039 4.2x1025年683、公开钥密码体制－对RSA的攻击方法1、强力攻击（穷举法）：尝试所有可能的私有密钥2、数学分析攻击：各种数学方法，等价与两个素数乘积的因子分解3、对RSA实现的攻击693、公开钥密码体制－90年代大数分解的进程152415787806736785461057783115378780769699778424020880588324163934003166279682168625361170971040173316721449

=

123456789123456789123456789123456789123456789123456871

*

1234567891234567891234567891234567891234567891234567919（SSNFS数域筛法）703、DES和RSA性能比较(同等强度）DES密钥长度(bit)RSA密钥长度(bit)56384645121121792128230471消息鉴别（MessageAuthentication)是一个证实收到的消息来自可信的源点且未被篡改的过程。散列函数（HashFunctions)一个散列函数以一个变长的报文作为输入，并产生一个定长的散列码，有时也称报文摘要，作为输出。

数字签名（DigitalSignature）是一种防止源点或终点抵赖的鉴别技术10.2消息验证与数字签名721、鉴别的目的鉴别的主要目的有二：第一，验证信息的发送者是真正的，而不是冒充的，此为信源识别；第二，验证信息的完整性，在传送或存储过程中未被篡改，重放或延迟等。732、鉴别系统的模型一个单纯鉴别系统的模型窜扰者信宿信源鉴别编码器鉴别译码器信道安全信道密钥源742、鉴别系统的模型（cont）在这个系统中的发送者通过一个公开的无扰信道将消息送给接收者，接收者不仅想收到消息本身，而且还要验证消息是否来自合法的发送者及消息是否经过篡改。系统中的密码分析者不仅要截收和破译信道中传送的密报，而且可伪造密文送给接收者进行欺诈，将其称为系统的窜扰者(tamper)更加合适。实际认证系统可能还要防止收方、发方之间的相互欺诈。753、鉴别系统的组成鉴别编码器和鉴别译码器可抽象为鉴别函数。一个安全的鉴别系统，需满足（1）意定的接收者能够检验和证实消息的合法性、真实性和完整性（2）消息的发送者和接收者不能抵赖（3）除了合法的消息发送者，其它人不能伪造合法的消息首先要选好恰当的鉴别函数，该函数产生一个鉴别标识，然后在此基础上，给出合理的鉴别协议(AuthenticationProtocol)，使接收者完成消息的鉴别。764、鉴别函数可用来做鉴别的函数分为三类：(1)消息加密函数(Messageencryption)

用完整信息的密文作为对信息的鉴别。(2)消息鉴别码MAC(MessageAuthenticationCode)

公开函数+密钥产生一个固定长度的值作为鉴别标识(3)散列函数(HashFunction)

是一个公开的函数，它将任意长的信息映射成一个固定长度的信息。774.1、消息加密信息加密函数分二种，一种是常规的对称密钥加密函数，另一种是公开密钥的双密钥加密函数。下图的通信双方是，用户A为发信方，用户B为接收方。用户B接收到信息后，通过解密来判决信息是否来自A，信息是否是完整的，有无窜扰。对称加密：保密性与鉴别MEKMEK(M)DKSourceDestination提供保密提供鉴别:仅来自A、传输中没有被更改、需要某种结构或冗余不提供签名784.1、消息加密差错控制：ErrorControlMF||MF(M)EKEKMF(M)FcompareInternalErrorControl794.1、消息加密差错控制：ErrorControlExternalErrorControlEK(M)F||EKMDKMFcompareEK(M)F[EK(M)]804.1、消息加密(b)公钥加密：保密性提供保密不提供鉴别MEKUbMEKUb(M)DKRbSourceDestination814.1、消息加密(C)公钥加密：鉴别与签名提供鉴别和签名仅A有Kra可以进行加密任何一方均可以使用Kua验证签名MEKRaMEKRa(M)DKUa824.1、消息加密(d)公钥加密：保密、鉴别与签名KUb提供保密性Kra提供鉴别和签名MEKRaEKRa(M)EKUbEKUb[EKRa(M)]DKRbDKUaEKRa(M)M834.2、信息鉴别－问题？若对相当长的文件通过签名认证怎么办？如一个合法文件有数兆字节长。自然按64比特分划成一块一块，用相同的密钥独立地签每一个块。然而，这样太慢。844.3、散列函数解决办法：引入可公开的密码散列函数。它将取任意长度的消息做自变量，结果产生规定长度的消息摘要。[如，使用数字签名标准DSS，消息摘要为160比特]，然后签名消息摘要。对数字签名来说，散列函数h是这样使用的：消息：x任意长消息摘要：Z=h(x)160bits

签名：y=sigk(Z)320bits(签名一个消息摘要)验证签名:(x,y),其中y=sigk(h(x))，使用公开的散列函数h，重构作Z=h(x)。然后Verk(y)=Z,来看Z=Z'854.3、散列函数的基本用法a、bProvidesconfidentiality--onlyAandBshareKProvidesauthentication--H(M)iscryptographicallyprotectedProvidesauthentication--H(M)iscryptographicallyprotected864.3、散列函数的基本用法cProvidesauthenticationanddigitalsignature--H(M)iscryptographicallyprotected--onlyAcouldcreateEKRa[H(M)]874.3、散列函数的基本用法d(d)AB:EK[M||EKRa[H(M)]]ProvidesauthenticationanddigitalsignatureProvidesconfidentiality884.3、散列函数的基本用法e、fProvidesauthentication--onlyAandBshareSProvidesauthentication--onlyAandBshareSProvidesconfidentiality--onlyAandBshareK894.3、散列函数安全威胁（1）用以鉴别的散列函数，能否减弱认证方案的安全性？这个问题是要分析的。签名的对象由完整消息变成消息摘要，这就有可能出现伪造。(a)伪造方式一：Oscar以一个有效签名(x,y)开始，此处y=sigk(h(x))。首先他计算Z=h(x)，并企图找到一个x'=x满足h(x')=h(x)。若他做到这一点，则(x',y)也将为有效签名。为防止这一点，要求函数h具有无碰撞特性。

定义1(弱无碰撞)，散列函数h称为是弱无碰撞的，是指对给定消息x∈X，在计算上几乎找不到异与x的x'∈X使h(x)=h(x')。904.3、散列函数安全威胁（2）(b)伪造方式二：Oscar首先找到两个消息x=x',满足h(x)=h(x'),然后Oscar把x给Bob且使他对x的摘要h(x)签名，从而得到y,那么(x',y)是一个有效的伪造。

定义2(强无碰撞)散列函数h被称为是强无碰撞的,是指在计算上几乎不可能找到相异的x，x'使得h(x)=h(x')。

注：强无碰撞自然含弱无碰撞！914.3、散列函数安全威胁（3）(c)伪造方式三：在散列函数的用法(e)中,秘密值S本身并不发送,如果散列函数不是单向的,攻击者截获到M和H(M||S).然后通过某种逆变换获得M||S,因而攻击者就可以得到S.

定义3(单向的)称散列函数h为单向的，是指计算h的逆函数h-1在计算上不可行。92h=H(M) “fingerprint”ofamessage满足：1、H可以作用于一个任意长度的数据块；2、H产生一个固定长度的输出；3、H(x)对任意给定的x计算相对容易，无论是软件还是硬件实现。4、对任意给定码h，找到x满足H(x)=h具有计算不可行性；（单向性）5、对任意给定的数据块x，找到满足H(y)=H(x)的yx具有计算不可行性。6、找到任意数据对(x,y)，满足H(x)=H(y)是计算不可行的。前三条要求具有实用性，第4条是单向性质，即给定消息可以产生一个散列码，而给定散列码不可能产生对应的消息。第5条性质是保证一个给定的消息的散列码不能找到与之相同的另外的消息。即防止伪造。第6条是对已知的生日攻击方法的防御能力。4、

HASHFUNCTIONS93如果房间里有183个人，那么其中某个人和你的生日相同的概率是50%。然而，如果希望找到其中任意两个人生日相同的概率为50%，则房间里需要多少人呢？答案是23

这个就是生日悖论，结果要比我主观猜想的要小得多。也就是说你走进一个22人的教室，要其中一个人和你的生日相同的概率很小，但要其中任意两个生日相同的概率则很高。转到代码安全中的哈希加密，情况转换成两段不同的字符（人），用哈希加密可能得到相同的密码（生日），而生日悖论的结果说明只要不关心是哪两个字符，找到两个匹配的难度会降低很多。4.4、

HASHFUNCTIONS94由Merkle于1989年提出RonRivest于1990年提出MD4几乎被所有hash函数使用具体做法:把原始消息M分成一些固定长度的块Yi最后一块padding并使其包含消息M长度设定初始值CV0压缩函数f,CVi=f(CVi-1,Yi-1)最后一个CVi为hash值4.4、

hash函数通用结构954.4、

hash函数通用结构bY0nIV=CV0fbY1nfbYL-1nCVL-1fCV1nnCVLCV0=IV=initialn-bitvalueCVi=f(CVi-1,Yi-1)(1iL)H(M)=CVLGeneralStructureofSecureHashCodeIV=initialvalue初始值CV=chainingvalue链接值Yi=ithinputblock(第i个输入数据块)f=compressionalgorithm(压缩算法）n=lengthofhashcode(散列码的长度)b=lengthofinputblock(输入块的长度)96MessageDigestAlgorithm4.4、几种Hash算法简介－MD5消息散列函数MD5算法逻辑：输入：任意长度的消息输出：128位消息摘要处理：以512位输入数据块为单位MD5(RFC1321)developedbyRonRivestatMIT974.4、几种Hash算法简介－MD5

MessageKbitsL512bits=N32bitsPadding(1to512bits)100…0Y0512bitsY1512bitsYq512bitsYL-1Messagelength(Kmod264)512bitsHMD5IV128HMD5CV1128HMD5CVq128HMD5CVL-1128512512512512MessageDigestGenerationUsingMD598step1：添加填充位(一个1和若干个0)。在消息的最后添加适当的填充位使得数据位的长度满足length448mod512step2：添加长度。原始消息长度（二进制位的个数），用64位表示。如果长度超过264位，则仅取最低64位，即mod264。到此为止，我们已经得到一个512位的整倍数长度的新的消息。可以表示为L个512位的数据块：Y0,Y1,…,YL-1。其长度为L512bits。4.4、几种Hash算法简介－MD599Step3:InitializeMDbuffer(little-endian) A=01234567(0x67452301) B=89ABCDEF(0xEFCDAB89) C=FEDCBA98(0x98BADCFE) D=76543210(0x10325476)Step4:Compression CV0=IV

CVi=HMD5(CVi-1,Yi)Step5:Output MD=CVL4.4、几种Hash算法简介－MD5100Merkle于1989年提出hashfunction模型RonRivest于1990年提出MD41992年,MD5(RFC1321)developedbyRonRivestatMITMD5把数据分成512-bit块MD5的hash值是128-bit在现在,MD5是仍最主要的hash算法安全威胁：Dobbertin在1996年找到了两个不同的512-bit块,它们在MD5计算下产生相同的hash至今还没有真正找到两个不同的消息,它们的MD5的hash相等MD5不是足够安全的4.4、几种Hash算法简介－MD5101SecureHashAlgorithm1992年NIST制定了SHA(128位)1993年SHA成为标准（FIPSPUB180）1994年修改产生SHA-1(160位)1995年SHA-1成为新的标准,作为SHA-1(FIPSPUB180-1)SHA-1要求输入消息长度<264输入按512位的分组进行处理的SHA-1的摘要长度为160位基础是MD4安全威胁：没有发现两个不同的512-bit块,它们在SHA-1计算下产生相同的“hash”速度慢于MD5安全性优于MD54.4、几种Hash算法简介－SHA-1102step1：添加填充位(一个1和若干个0)。在消息的最后添加适当的填充位使得数据位的长度满足length448mod512step2：添加长度。原始消息长度，用64位表示。Step3:InitializeMDbuffer(big-endian) A=67452301(0x67452301) B=EFCDAB89(0xEFCDAB89) C=98BADCFE(0x98BADCFE) D=10325476(0x10325476) E=C3D2E1F0(0xC3D2E1F0)Step4:Compression CV0=IV

CVi=HSHA-1(CVi-1,Yi)Step5:Output MD=CVL4.4、几种Hash算法简介－SHA-1103欧洲RACEIntegrityPrimitivesEvaluation项目的结果RIPEMD为128位更新后成为RIPEMD-160基础是MD5安全威胁：没有发现两个不同的512-bit块,它们在RIPEMD-160计算下产生相同的“hash”速度略慢于SHA-1安全性优于MD5对密码分析的抵抗力好于SHA-14.4、几种Hash算法简介－RIPEMD-160104比较：

MD5 SHA-1 RIPEMD-160摘要长度 128位 160位 160位基本处理单位512位 512位 512位步数 64(4of16) 80(4of20) 160(10of16)最大消息长度无限 264-1位 264-1基本逻辑函数4 4 5加法常数 64 4 9Endianness Little-endian Big-endian Little-endian4.4、几种Hash算法简介－比较105hash函数把变长信息映射到定长信息hash函数不具备可逆性hash函数速度较快hash函数与对称密钥加密算法有某种相似性对hash函数的密码分析比对称密钥密码更困难hash函数可用于消息摘要hash函数可用于数字签名4.4、

hash函数小结106Messageauthentication用以保护双方之间的数据交换不被第三方侵犯；但它并不保证双方自身的相互欺骗。假定A发送一个认证的信息给B，双方之间的争议可能有多种形式：B伪造一个不同的消息,但声称是从A收到的。A可以否认发过该消息,B无法证明A确实发了该消息。4.5、

数字签名107数字签名的特点传统签名的基本特点:能与被签的文件在物理上不可分割签名者不能否认自己的签名签名不能被伪造容易被验证数字签名是传统签名的数字化,基本要求:能与所签文件“绑定”签名者不能否认自己的签名签名不能被伪造容易被自动验证4.5.1、数字签名108必须能够验证作者及其签名的日期时间；必须能够认证签名时刻的内容；签名必须能够由第三方验证，以解决争议；4.5.2、数字签名的性质因此，数字签名功能包含了认证的功能。109签名必须是依赖于被签名信息的一个位串模式；签名必须使用某些对发送者是唯一的信息，以防止双方的伪造与否认；必须相对容易生成该数字签名；必须相对容易识别和验证该数字签名；伪造该数字签名在计算复杂性意义上具有不可行性，既包括对一个已有的数字签名构造新的消息，也包括对一个给定消息伪造一个数字签名；在存储器中保存一个数字签名副本是现实可行的。4.5.3、数字签名的设计要求110直接数字签名directdigitalsignature仲裁数字签名arbitrateddigitalsignature(1)AB:EKRa[M]

提供了认证与签名：只有A具有KRa进行加密;传输中无法被篡改；需要某些格式信息/冗余度；任何第三方可以用KUa

验证签名(1’)AB:EKUb[EKRa(M)]

提供了保密(KUb)、认证与签名(KRa)：4.5.4、直接数字签名1114.5.4、直接数字签名(2)AB:M||EKRa[H(M)]提供认证及数字签名

--H(M)受到密码算法的保护；

--只有

A能够生成

EKRa[H(M)](2’)AB:EK[M||EKRa[H(M)]]提供保密性、认证和数字签名。1124.5.4、直接数字签名的缺点验证模式依赖于发送方的保密密钥；发送方要抵赖发送某一消息时，可能会声称其私有密钥丢失或被窃，从而他人伪造了他的签名。通常需要采用与私有密钥安全性相关的行政管理控制手段来制止或至少是削弱这种情况，但威胁在某种程度上依然存在。改进的方式例如可以要求被签名的信息包含一个时间戳（日期与时间），并要求将已暴露的密钥报告给一个授权中心。X的某些私有密钥确实在时间T被窃取，敌方可以伪造X的签名及早于或等于时间T的时间戳。1134.5.5、仲裁数字签名引入仲裁者。通常的做法是所有从发送方X到接收方Y的签名消息首先送到仲裁者A，A将消息及其签名进行一系列测试，以检查其来源和内容，然后将消息加上日期并与已被仲裁者验证通过的指示一起发给Y。仲裁者在这一类签名模式中扮演敏感和关键的角色。所有的参与者必须极大地相信这一仲裁机制工作正常。（trustedsystem）1144.5.5、仲裁数字签名仲裁数字签名技术(a)单密钥加密方式，仲裁者可以看见消息

(1)XA：M||EKxa[IDx||H(M)] (2)AY：EKay[IDx||M||EKxa[IDx||H(M)]||T]X与A之间共享密钥Kxa，Y与A之间共享密钥Kay；X：准备消息M，计算其散列码H(M)，用X的标识符IDx

和散列值构成签名，并将消息及签名经Kxa加密后发送给A；A：解密签名，用H(M)验证消息M，然后将IDx，M，签名，和时间戳一起经Kay加密后发送给Y；Y：解密A发来的信息，并可将M和签名保存起来。解决纠纷：Y：向A发送EKay[IDx||M||EKxa[IDx||H(M)]]

A：用Kay恢复IDx，M，和签名（

EKxa[IDx||H(M)]），然后用Kxa解密签名并验证散列码1154.5.5、仲裁数字签名注意：在这种模式下Y不能直接验证X的签名，Y认为A的消息已认证，只因为它来自A。因此，双方都需要高度相信A:X必须信任A没有暴露Kxa，并且没有生成错误的签名

EKxa[IDx||H(M)]Y必须信任A仅当散列值正确并且签名确实是X产生的情况下才发送的EKay[IDx||M||EKxa[IDx||H(M)]||T]

双方都必须信任A处理争议是公正的。只要A遵循上述要求，则X相信没有人可以伪造其签名；Y相信X不能否认其签名。上述情况还隐含着A可以看到X给Y的所有信息，因而所有的窃听者也能看到。1164.5.5、仲裁数字签名(b)单密钥加密方式，仲裁者不可以看见消息

(1)XA：

IDx||EKxy[M]||EKxa[IDx||H(EKxy[M])] (2)AY：EKay[IDx||EKxy[M]||EKxa[IDx||H(EKxy[M])]||T]在这种情况下，X与Y之间共享密钥Kxy，X：将标识符IDx,密文

EKxy[M]，以及对IDx和密文消息的散列码用Kxa加密后形成签名发送给A。A：解密签名，用散列码验证消息，这时A只能验证消息的密文而不能读取其内容。然后A将来自X的所有信息加上时间戳并用Kay加密后发送给Y。(a)和(b)共同存在一个共性问题：

A和发送方联手可以否认签名的信息；

A和接收方联手可以伪造发送方的签名；1174.5.5、仲裁数字签名(c)双密钥加密方式，仲裁者不可以看见消息

(1)XA：

IDx||EKRx[IDx||EKUy(EKRx[M])] (2)AY：EKRa[IDx||EKUy[EKRx[M]]||T]X：对消息M双重加密：首先用X的私有密钥KRx，然后用Y的公开密钥KUy。形成一个签名的、保密的消息。然后将该信息以及X的标识符一起用KRx签名后与IDx

一起发送给A。这种内部、双重加密的消息对A以及对除Y以外的其它人都是安全的。A：检查X的公开/私有密钥对是否仍然有效，是，则认证消息。并将包含IDx、双重加密的消息和时间戳构成的消息用KRa签名后发送给Y。本模式比上述两个模式具有以下好处：1、在通信之前各方之间无须共享任何信息，从而避免了联