现代密码学-2016-3讲述

现代密码学

ModernCryptography

密码小故事---跳舞的小人原理:自然语言的字母出现频率有规律：

e:11.67t:9.53o:7.81a:7.73…

the:4.65to:3.02of:2.61and:1.85…e:11.67t:9.53….the:4.65…444455555

donttellherthesecrettttteeeeehhrrlldonsc课程信息

教学目的与要求:密码学是信息安全的核心技术,了解常用的密码算法,经典的密码协议及其在当前网络热点研究中的应用,掌握解决计算机网络安全问题的基本方法和策略.

教辅材料：

--杨波.现代密码学.清华大学出版社

--BruceSchneier著,吴世忠等译.应用密码学—协议、算法与C源程序.机械工业出版社教师信息段桂华

计算机楼413

duangh@主要内容1引言2现代密码算法

2.1密码机制分类2.2对称密码算法

2.3序列密码算法2.4数字摘要算法

2.5公钥密码算法2.6数字签名算法3经典的密码协议

3.1基本的密码协议3.2中级协议

3.3高级协议4加密模式

4.1概述4.2ECB模式

4.3CBC模式4.4CFB模式

4.5OFB模式5密码管理

5.1密钥管理概述5.2对称密钥的管理

5.3公钥的密钥管理1引言网络通信的困境与安全威胁网上黑客无孔不入个人隐私泄露国家信息安全网上犯罪形势不容乐观有害信息污染严重网络病毒的蔓延和破坏PC机用户虚假兼职44.1%退款欺诈13.4%网游交易12.4%手机用户诈骗短信53.8%钓鱼网站32.3%诈骗电话12.7%木马病毒1.2%虚假购物55.5%虚假中奖19.4%金融理财6.5%冒充熟人28.5%虚假中奖25.6%冒充银行19.9%保证信息安全要做什么呢认证:消息来源确认,身份的验证.你是谁?我怎么相信你就是你?

授权:根据实体身份决定其访问权限.我能干什么?

你能干这个,不能干那个.保密:非授权人无法识别信息.我与你说话时,别人能不能偷听?

完整性:防止消息被篡改.传送过程过程中别人篡改过没有?

不可否认:不能对所作所为进行抵赖.我收到货后,不想付款,想抵赖,怎么样?我将钱寄给你后,你不给发货,想抵赖,如何?

2现代密码算法2.1密码机制分类2.2对称密码算法2.3序列密码算法2.4数字摘要算法2.5公钥密码算法2.6数字签名算法2.1密码机制分类密码机制分类按照保密的内容分类古典密码:保密算法和密钥现代密码:保密密钥

按照密钥的特点分类对称密码机制,加密密钥和解密密钥相同,或可以容易地从一个推出另一个;特点:加密速度快,密钥管理复杂,主要用于加密信息.非对称密码机制,加密密钥和解密密钥不同,且很难从一个推出另一个;特点:密钥管理简单,加密速度慢,用于加密会话密钥和用于数字签名.Kerchoffs原则对称密码类似保险柜:密钥为保险柜密码加密文件---将文件放入保险柜,设置密码锁上解密文件---用密码打开保险柜,取出文件解密密钥加密密钥公钥密码类似邮箱:加密文件---将文件发到邮箱duangh@解密文件---用邮箱密码打开邮箱,取出文件加密密钥,公开解密密钥,保密文件签名---收到邮箱duangh@发来的文件经典的密码算法经典的古典密码算法主要有:代替密码换位密码古典密码多字母代替单字母代替单表代替密码多表代替密码（流密码）（分组密码）代替密码:将明文字符用另外的字符代替换位密码:明文的字母保持不变,但顺序打乱

经典的现代密码算法主要有很多,常用的有:DES,数据加密标准,对称密码,用于加密IDEA,国际数据加密标准,对称密码AES,高级加密标准,对称密码,用于加密RC4,序列密码,面向字节流RSA,最流行的公钥密码,用于加密和数字签名ECC,公钥密码,安全性高,密钥量小,灵活性好DSA,数字签名算法,用于数字签名SHA(MD5),散列算法,用于签名和认证2.2对称密码算法2.2.1DES算法2.2.2IDEA算法2.2.3AES算法1973年5月15日NBS开始公开征集标准加密算法DES(DataEncryptionStandard),并公布了它的设计要求:算法必须提供高度的安全性算法必须有详细的说明,并易于理解算法的安全性取决于密钥,不依赖于算法算法适用于所有用户算法适用于不同应用场合算法必须高效,经济算法必须能被证实有效算法必须是可出口的1.对称密码算法--DES1974年8月27日,NBS开始第二次征集,IBM提交了算法LUCIFER.1975年3月公开发表,1977年1月由美国国家标准局NBS颁布为数据加密标准DES，同年7月成为美国联邦信息处理标准FIPS-46.1980年,美国国家标准协会(ANSI)正式采纳DES作为美国商用加密算法DEA.1983年,国际化标准组织(ISO)同意将DES作为国际标准,称之为DEA-1.1998年,美国政府不再将DES作为联邦加密标准.但其结构和部件一直作为分组密码设计的标准参照物.后更名为NISTDES是一个分组加密算法,对称密码,64位分组,密钥长度为64位(实际长度为56位).DES的整个算法是公开的,系统的安全性靠密钥保证.算法包括三个步骤:初始置换IP,16轮迭代的乘积变换,逆初始变换IP-1.基本思想:混淆与扩散IP和IP-1的作用主要是打乱输入的ASCII码字划分关系,并将明文校验码变成IP输出的一个字节.初始置换IP和逆初始置换IP-1混淆:复杂化密文与明文,密钥之间的统计特性.扩散:将每一位明文的影响尽可能多地分散到多个输出密文中,以更隐秘明文的统计特性.f=1234…63644084816…5719f-1=1234…636458504234…157IP置换IP-1置换乘积变换是DES算法的核心部分.将经过IP置换后的数据分成32位的左右两组,在迭代过程中彼此左右交换位置.每次迭代时只对右边的32位进行一系列的加密变换,然后把左边的32位与右边得到的32位逐位进行异或操作,作为下一轮迭代时左边的段.乘积变换迭代公式为:Li=Ri-1，Ri=Li-1

f(Ri-1,ki)

:按位异或操作运算符,即按位作模2相加运算.运算规则为:1

0=1,0

1=1,0

0=0,1

1=0f的功能是将32比特的数据经过选择扩展运算E,密钥加密运算,选择压缩运算S和置换运算P转换为32比特的输出.位扩展位置换子密钥生成64比特初始密钥k经过换位函数PC-1将位置号为8,16,24,32,40,48,56和64的8位奇偶位去掉并换位;换位后的数据分为2组,经过循环左移位LSi和换位函数PC-2变换后得到每次迭代加密用的子密钥ki选择压缩运算

将密钥加密运算后的48比特数据从左至右分成8组,每组为6比特,并行送入8个S盒后压缩成32比特输出.每个S盒的输入为6比特,输出为4比特.安全性分析:穷举攻击:在得到明密文对的情况下,进行256≈1017次穷举.MitsuruMatsui提出的线性密码分析,采用近似值来逼近分组密码的操作,约243次.Biham和Shamir提出的差分密码分析,通过分析特定明文差分对密文差分影响来获得可能密钥,约247次.DES的出现在密码史上是个创举,自公布以来,它一直活跃在国际保密通信的舞台上,成为商用保密通信和计算机通信的最常用的加密算法.DES的安全性完全依赖于密钥,而其56bit的密钥太短,因而出现了许多DES的改进算法,如三重DES,分组反馈连接式DES以及密码反馈模式DES等.

来学嘉和JamesMassey1990年公布,1992年更名为IDEA(国际数据加密算法).分组长度为64位,分4子组进行操作,密钥长度为128位,使用异或,模216加,模216+1乘三个混合运算,在16位子分组上进行.强化了抗差分分析的能力,应用于PGP中.软件实现IDEA比DES快两倍.乘加结构(MA)保证了扩散的特点.特点:2.对称密码算法--IDEA模乘异或模加(1)64位数据分成4个16位子分组X1,X2,X3,X4;(2)共进行8轮操作,每轮与6个16位子密钥异或,相加,相乘;(3)在每轮之间,第2个和第3个子分组交换;(4)最终由一个输出变换,如下图所示:原理:128位的k分组:k1,k2,k3,k4,k5,k6,k7,k8;然后进行左环移(25位).子密钥产生:1k1k2k3k4k5k6k7k8128位的k分组左环移25位125k9k10k11k12k13k14k15k16该算法克服了DES算法的弱点,保留了多轮的合理模式,2002年成为现代加密标准AES.分组,密钥长度和轮数可变.支持长度为128位,192和256位的分组和密钥.

比利时密码学家JoanDaemen和VincentRijmen提出的密码算法方案,称之为Rijndael算法.特点:密钥长度4/16/1286/24/1928/32/256分组长度Nb4/16/1284/16/1284/16/128轮数Nr101214轮密钥长4/16/1284/16/1284/16/128扩展密钥总长44/17652/208

60/2403.对称密码算法--AES高级加密标准AES的诞生1997年,美国国家标准和技术研究所NIST向密码学界征寻用于新的高级加密标准AES候选算法,规定:密码系统是没有密级的;算法的全部描述必须公开;可在世界范围内免费使用;支持至少128位的分组;支持的密钥长度至少为128,192和256位.1998年8月提交了15个候选算法,NIST于1999年9月宣布5个候选算法进入第二轮;2000年10月选择Rijdeal作为AES,其特点为:安全,易实现,算法灵活与简便.2001年11月NIST将AES定为联邦信息处理标准FIPSPUB197,2002年5月正式生效.(1)从加解密时间上来看:MARS,RC6,Serpert:相同,与密钥长度无关;Rijndael:密钥为192比特的比128的慢20%,

密钥为256比特的比128的慢40%;Twofish:需要更多的时间来设置更长的密钥.(2)软件性能(PII,汇编,C实现,时钟周期)密码128比特密钥192比特密钥256比特密钥内存字节数MARS300380300380300380100RC6225240225240225240210Rijndael23040027552033060052Serpent75075075075075075050Twofish25038025038025038060AES最终候选算法性能比较算法分析:

128比特的明文分组被分成4×4的字节矩阵.字节替换SubBytes.非线性置换,独立作用于状态中的每一个字节.移位行运算ShiftRows.字节的循环移位运算,第1行~第4行字节分别向左移动0~3列.混合列运算MixColumns.由一个线性变换对状态的每一列进行变换.02030101010203010101020303010102轮密钥加密AddRoundKey.与相应的密钥进行异或.线性变换AES加密算法:

Rijndael(State,CipherKey){KeyExpansion(CipherKey,W[1,…,Nb*(Nr+1)]);

AddRoundKey(State,W[0,…,Nb-1]);for(i=1;i<Nr;i++){SubBytes(State);

ShiftRows(State);

MixColumns(State);

AddRoundKey(State,W[i*Nb,…,(i+1)*Nb-1]);}//中间Nr-1轮

SubBytes(State);ShiftRows(State);//末轮

AddRoundKey(State,W[Nr*Nb,…,(Nr+1)*Nb-1)];}12810非线性置换S盒SubBytes:19d49轮的操作过程如下:(Nb=128,Nr=10)

02×d4+03×bf+01×5d+01×3004密钥编排KeyExpansion

所需密钥比特总数等于Nb(Nr+1),如分组长度Nb为128比特,轮数Nr为10时,需要1408比特.AES解密算法InvSubBytes中逆S盒逆行移位运算InvShiftRows

字节的循环右移位运算,第1行~第4行字节分别向右移动0~3列.逆列运算InvMixColumns的线性变换矩阵0E0B0D09090E0B0D0D090E0B0B0D090E这是因为:0E0B0D09090E0B0D0D090E0B0B0D090E020301010102030101010203030101021000010000100001=算法密钥长度迭代次数数学运算应用DES5616XOR,S-BoxKerberos,SET3DES112,16848XOR,S-BoxPGP,S/MIMEIDEA1288XOR,+,

PGPBlowFish最大44816XOR,S-Box,+RC5最大2048<255+,-,XORCAST-12840-12816+,-,S-BoxPGP4.对称密码算法小结优点:效率高,算法简单,系统开销小,适合加密大量数据缺点:需要以安全方式进行密钥交换,密钥管理复杂2.3序列密码算法RC4算法

RonRivest在1987年为RSA数据安全公司开发的可变密钥长度的序列密码,广泛应用于商业密码产品中.是一个面向字节的流密码;RC4的密码序列独立于明文;RSA声称RC4对线性和差分分析具有免疫力;由于RC4是流密码,必须避免重复使用密钥;所需要代码少,比DES快10倍.RC4算法中密钥序列与明文相互独立,有一个256字节的S盒:

S0,S1,…,S255,其值是0到255之间不重复的值,是一个可变长度密钥的函数.特点RC4算法描述算法i=j=0;i=(i+1)mod256j=(j+Si)mod256

交换Si和Sjt=(Si+Sj)mod256k=St

k即为密钥流,为产生的随机字节.

i=j=0;

i=(i+1)mod256;j=(j+Si)mod256交换Si和Sj

t=(Si+Sj)mod256;k=St

107c64k17C8CS盒初始化S0=0,S1=1,…,S255=255然后用初始密钥key填充另一个256字节的数组,不断重复密钥直至填充整个数组;

j=0

对于i=0至255

j=(j+Si+ki)mod256

交换Si和Sj最后得到用密钥初始化的S盒.问题:为什序列密码的密钥流不能重复使用?分析:

原始明文:P1P2P3P4新明文:P1P’P2P3P4

原始密钥:k1k2k3k4密钥:k1k2k3k4k5

原始密文:C1C2C3C4新密文:C1C2’C3’C4’C5’由于Mallory知道P’,他可以根据k2=P’⊕C2’

得到k2,P2=C2⊕k2k3=P2⊕C3’

得到k3,P3=C3⊕k3以此类推,从而确定整个明文.P’2.4数字摘要算法2.4.1散列函数2.4.2MD5算法2.4.3SHA算法解决方法：数字摘要如何实现完整性？篡改公共网络AliceBobEve1.散列函数描述是一个公开的函数,它将任意长的信息映射成一个固定长度的信息.(公开性)为了保证安全,要求是单向的无碰撞的散列函数.即找不到y,当x≠y时,使得h(x)=h(y).(无碰撞性)预映射值单个位的改变,将引起散列值中一半的位发生改变.(扩散性)计算上的单向性.

易

难

x

h(x)作用:保证消息的完整性;用在数字签名中,提高签名效率.无法篡改z消息篡改公共网络AliceBobm,zm,zz=hk(m)y=hk(m)Eve如果y≠zm被篡改消息鉴别码MAC:与密钥有关的单向散列函数称为消息鉴别码.传送的消息为{m,z=hk(m)},接收方收到消息后计算y=hk(m),将y与z比较即可知道消息有无篡改.2.数字摘要算法-MD5亦称消息摘要(MessageDigest)或杂凑函数,由美国的RonaldRivest1992年开发.输入任意长度消息x,输出为128位的消息摘要值.算法描述:算法包括5个步骤.(1)附加填充比特在消息x后填充串1000…,使得消息的长度满足:|x|≡448mod512

填充比特总是有效,填充数为1~512.由4个32比特的寄存器A,B,C,D表示,其初始值:A=0x01234567B=0x89abcdefC=0xfedcba98D=0x76543210(2)附加长度

将原始消息的长度(64比特)附加到填充后的消息后面.令X[0,1,…,n-1]为填充后消息的各字(每字32比特),填充后消息的总长为512的倍数.

所以,n能被16整除.(3)初始化MD缓冲区主循环有4轮,每轮进行16次操作.(4)按每块16字(512比特)对数据进行处理轮数X[k]的k值

10,1,2,3,…,1521,6,11,0,…,1235,8,11,14,…,240,7,14,5,…,9X[k]:消息块X的第k个子分组(0~15);T[i]:为232×abs(sin(i))的整数部分,i为弧度;4轮的操作:a=b+((a+(g(b,c,d)+X[k]+T[i])<<<s)g在每轮中分别为F,G,H,I逻辑函数如第1轮的操作为:a=b+((a+(F(b,c,d)+X[k]+T[i])<<<s)s值(5)输出A=(A+a)mod232B=(B+b)mod232C=(C+c)mod232D=(D+d)mod232

说明3.数字摘要算法-SHASHA由NIST开发并于1993年采纳为安全杂凑标准,其基础是MD4,因此其设计与MD5类似.SHA-1是1995年的修改版,输入为长度小于264比特的消息,输出为160比特的消息摘要.有5个32比特的缓冲区寄存器,其初始值分别为:A=0x67452301B=0xefcdab89C=0x98badcfeD=0x10325476E=0xc3d2e1f0以分组512比特为单位对消息进行4轮压缩处理,每轮处理过程对缓冲区进行20次迭代运算.230×sqrt(2)=0x5a827999,0

t<20230×sqrt(3)=0x6ed9eba1,20

t<40230×sqrt(5)=0x8f1bbcdc,30

t<60230×sqrt(10)=0xca62c1d6,60

t<80Kt=(B∧C)∨(B∧D),0

t<20B⊕C⊕D,20

t<40(B∧C)∨(B∧D)∨(C∧D),40

t<60B⊕C⊕D,60

t<80ft=f(t,B,C,D)=Sk:循环左移k位与MD5不同的是,直接对输入分组X的16个字进行迭代,而SHA是将16个字扩展为80个字后进行迭代.

X[t]0

t<16(Wt-16⊕Wt-14⊕Wt-8⊕Wt-3)<<<1,16

t<80Wt=W1W2W3W4W5W6W7W8W9W10W11W0W12W13W14W15W17W18…W16算法安全性Dobbertin在1996年找到了两个不同的512bit块,它们在MD5计算下产生相同的hash;王小云教授于2004年8月和2005年2月分别破译MD5和SHA-1;实际运用中Hash函数算法通常与其他密码技术混合使用,伪造有意义的电子签名需要更尖端的技术.SHA和MD5的比较:

2.5公钥密码算法2.5.1RSA算法2.5.2ElGamal算法2.5.3ECC算法什么是公钥密码算法特点加密密钥和解密密钥不同,因而可以将加密密钥公开,将解密密钥保密.公钥密码的思想1976年被提出.代表性算法:RSA,ElGamal,Knapsnack,ECC等.密钥管理简单,运算速度较慢.安全性基于数学难题.Knapsnack:背包问题RSA:因子分解难题ELGamal算法:离散对数难题ECC算法:椭圆曲线点群上的离散对数难题1977年由RonRivest,AdiShamir和LenAdleman发明,1978年正式公布.RSA是一种分组加密算法.明文和密文在0~n-1之间,n是一个正整数.该算法的数学基础是初等数论中的Euler(欧拉)定理,并建立在大整数因子的困难性之上.目前应用最广泛的公钥密码算法.只在美国申请专利,且已于2000年9月到期.既能加密又可签名,易理解和实现,因而最流行.1.公钥密码算法-RSA(LefttoRight:RonRivest,AdiShamir,LenAdleman)2002年图灵奖获得者--RSA-2002RSA算法过程选择两个大素数p和q,计算:n=pq以及

(n)=(p-1)×(q-1)选择随机数1<e<

(n),gcd(e,

(n))=1,计算:d=e-1mod

(n)公钥(e,n),私钥(d,p,q);加密m:c=memodn

解密c:m=cdmodnx

(n)=1modnRSA算法可解性分析欧拉定理:

如果gcd(x,n)=1,则有:欧拉定理要求明文x与模数n互素但不互素的概率很小:

根据欧拉定理可以很容易地得出:cdmodn

m在选择e时,也要考虑与

(n)互素,一般选e为3,

17,

65537等等RSA算法安全性分析依赖于将整数n分解为素因子的难度公钥私钥的关系:

d=e-1mod

(n);已知e和n,要得到d,需要知道

(n),由

(n)的计算公式

(n)=(p-1)×(q-1)可知需要知道n的因子分解.当n很大时,这是一个难题.从安全性考虑,p与q必为足够大的素数使n的分解无法在多项式时间内完成;要求n至少要有1024或者2048比特(十进制的308位或616位).针对协议的攻击密钥使用不当c=meAliceEveBobyk选r<n，计算t=r-1modn，x=remodn，y=x·cmodn签名u=ydmodn计算tu=r-1yd=r-1(x·c)d=r-1·r·mmodn得到m共用模数n攻击者获得n,e1,e2,c1,c2c1=me1modnc2=me2modn若e1和e2互素,有re1+se2=1,则可以根据

((c1)-1)-r×(c2)s=mre1+se2=mmodn

选取素数p>10150,一个模p的原根g以及随机整数d(1<d<p),计算e=gdmodp,则公钥为(e,g,p),私钥为d

1985年发表,既可用于数字签名又用于加密.其安全性依赖于离散对数难题.ElGamal算法过程密钥的生成

选择随机数k,得到密文对(a,b)为:(a=gkmodp,b=m·ekmodp)加密m:

b·a-dmodp=m·ek·(gk)-dmodp=m解密m:

2.公钥密码算法-ElGamal(1)Bob选择随机数k=4,计算得到的密文:a=gkmodp=24mod11=5b=m·ekmodp=3·54mod11=5(2)Alice对收到的密文(5,5)解密：

b·a-dmodp=5·5-4mod11=3

选p=11,g=2,私钥d=4,则公钥e=gdmodp=5Bob要将消息m=3传送给Alice.【举例】特点:通过选择不同的随机数k,即使是相同的加密密钥,也可以将相同的明文加密成不同的密文对.

1985年N.Koblitz和V.Miller分别独立提出了椭圆曲线密码体制(ECC),其安全性依赖于定义在椭圆曲线点群上的离散对数问题(ECDLP)的难解性.椭圆曲线的基本概念已知有限域GF(p)(p=qn,q>3)上的椭圆曲线群

Ep(a,b):y2=x3+ax+b(modp),a,b∈GF(p)4a3+27b2≠0PQS-S=P+QS+P+Q=O,O为无穷点3.公钥密码算法-ECC选取EP(a,b)和生成元G,公开.将明文消息m通过编码嵌入到曲线上的点Pm.ECC算法过程密钥的生成：Bob选取私钥d,公钥为e=dGAliceBob随机选kCm={kG,Pm+ke}计算Pm+ke-dkG=Pm加解密过程：Alice将消息Pm发送给Bob.MIPS年表示用每秒完成100万条指令的计算机所需工作的年数RSA与ECC比较应用前景非常好,特别在移动通信,无线设备上的应用.【参考文献】1.ECDLP,百度百科

2.刘淳等.基于智能卡的RSA与ECC算法的比较与实现,计算机工程与应用,2007,43(4):96-99公钥/私钥对是对应的,公钥公开,私钥保密;公钥加密的消息只能用私钥解密,反之用私钥加密的消息只能用对应的公钥解密;用于加密:任何人用Bob的公钥对消息m加密,只有Bob才能用私钥解密.公共网络AliceBobBob公钥kBp密码分析Evec=EBp(m)其他人没有私钥kBv,故无法解密cBob私钥kBv公钥密码算法小结用于数字签名:Alice用自己的私钥加密消息m,其他任何人(如Bob)都可以用Alice的公钥进行验证.公共网络AliceBobAlice私钥kAv伪造签名Evem+sBob用Alice公钥kAp验证s确认mAlice公钥kAps=EAv(m)其他人没有Alice私钥,无法伪造s或篡改m3.5数字签名算法3.5.1RSA签名算法3.5.2DSA签名算法3.5.3离散对数签名方案数字签名算法但RSA算法的供应商RSADSI反对:DSA不能用于加密或者密钥分配;由NSA研制,可能有陷门;DSA速度比RSA慢;RSA是事实上的标准.1994年该标准被颁布.1998年12月规定DSA或RSA签名方案都可用于美国各机构生成数字签名,2000年NIST又颁布一个新的标准,指出椭圆曲线数字签名算法ECDSA也可用于签名.1991年,NIST提出DSA用于数字签名标准DSS中;2000年美国通过法律,数字签名和传统签名具有同等法律效力;我国于2005年也颁布了此法律.1.RSA签名算法算法描述设模数为n,签名私钥为d,验证公钥为e.对消息m签名:s=mdmodn验证签名s:semodn是否等于m安全性分析:利用指数的特点攻击ed=1mod(n)

y=xemodn,m'=y·mmodn

Trent对m'签名:s(m')=(m')d=yd·md=x·mdmodn

从而获得m的签名：

s(m)=mdmodn=s(m')·x-1modn盲签名的思想e=gdmodp2.DSA签名算法签名密钥:签名私钥为d,验证公钥为e;对消息m签名:选k(gcd(k,p-1)=1),计算签名对(r,s):r=gkmodp,m=(dr+ks)modp-1验证:若errsmodp=gmmodp,则签名有效.ElGamal签名算法数字签名算法DSA(Digitalsignature

algorithm)是ElGamal签名方案的变形.1994年被美国NIST采纳作为数字签名标准DSS),使用SHA作为散列函数.p:L位长的素数,512

L

1024,64|Lq:160位的素数且q|p-1g:g=h(p-1)/qmodp,1<h<p-1,g>1用户私钥:d,0<d<q用户公钥:e,e=gdmodpDSA算法描述密钥参数Alice(r,s),H(m)Bob选k<p,计算m的签名(r,s)r=(gkmodp)modqs=(k-1(H(m)+dr))modq签名与验证过程验证:w=s-1modqu1=(H(m)×w)modqu2=(rw)modqr==((gu1eu2)modp)modq?d=s1=(k-1(H(m1)+dr))s2=(k-1(H(m2)+dr))s1s2H(m1)+drH(m2)+drDSA算法安全性512位的DSA不能提供长期的安全性,

至少要2048位.若Eve获得同一个k签名的两个消息,则可恢复d结论:k的随机产生很关键.3.离散对数签名方案DSA是离散对数签名方案的一种.选择大素数p和q,q|p-1;选择g满足:1<g<p且gq=1modp;选私钥d<p,则公钥e=gdmodp;对消息m签名和验证:a,b,c的值是r’,m,s的组合,产生多达13000种变型.选择随机数k<p,r=gkmodp,r’=rmodq.签名等式:ak=b+cdmodq.验证等式:ramodp是否等于gbecmodp3.1基本的密码协议3.2中级协议3.3高级协议3.经典的密码协议3.1基本的密码协议3.1.1什么是密码协议3.1.2仲裁协议和裁决协议3.1.3保密通信协议3.1.4数字签名协议3.1.5密钥协商协议3.1.6身份鉴别协议3.1.7秘密共享协议1.什么是密码协议cryptographicprotocol

又称为安全协议,是网络安全的一个重要组成部分,以密码学为基础进行消息交换,在网络环境中提供各种安全服务,防止或发现窃听和欺骗.协议的特点:协议中各方都必须同意并遵循它;协议必须清楚,每一步须明确定义,无歧义;协议必须是完整的,对每种可能的情况必须规定具体的动作;协议的安全性.协议的目的:保证公平和安全,避免欺骗.2.仲裁协议和裁决协议

密码学中典型的两类协议,区别在于在裁决协议中仲裁者不直接参与协议执行过程,只是确定协议是否正常执行.仲裁者:是在完成协议的过程中,值得信赖的公正的第三方,能帮助互不信任的双方完成协议.如律师,银行,公证人等.仲裁者的选择要考虑:可信任度;仲裁协议的延迟与安全;仲裁者的数目与费用折中问题.密码协议示例【举例】:Alice向Bob借50万,仲裁人为法官.基于对称密码机制的协议--仲裁协议Alice?法官?BobEk(50万)Ek(10万)Ek(50万)Ek(50万)Ek(80万)Ek(10万)Ek(80万)k①Alice狡辩:借10万②Bob狡辩:借80万Alice向Bob借50万解决方法:Alice?法官?BobEkAv(50万)EkAv(10万)EkAv(50万)EkAv(50万)EkAv(80万)EkAv(10万)EkAv(80万)Alice?法官?BobEk(50万)Ek(10万)Ek(50万)Ek(50万)Ek(80万)Ek(50万)k基于非对称密码机制的协议--裁决协议①Alice狡辩借10万,Bob出示50万借据②Bob狡辩借80万,无法提供80万借据Alice向Bob借50万协议的安全性

可以对密码算法和协议的密码技术进行攻击,也可以对协议本身进行攻击.被动攻击:窃听协议的一部分或全部,目的是获取消息,不影响协议的执行.主动攻击:改变协议以对自己有利,插入,删除和修改消息,破坏通信等等.骗子:协议中的一方,不遵守协议或者破坏协议.协议的安全性举例

公钥密码算法本身较安全,若在协议中使用不当将会有安全隐患.【举例】

在同一组用户之间共享RSA算法的公共模数n((c1)-1)-r×(c2)s=mre1+se2

mmodn攻击者获得Carol发给Alice和Bob的同一个消息m的密文c1和c2;攻击者很容易知道n,e1,e2c1=me1modnc2=me2modn若e1和e2互素,有re1+se2=1,则可以根据①AliceBob加密解密mcm密钥密钥系统②③④⑤3.保密通信协议可能的攻击:窃听:唯密文攻击;破坏,伪造:通信双方能发现.所以:好的密码系统的安全性只与密钥有关,可以公开算法,因此,密钥的管理是非常重要的.会话密钥混合密码系统用公钥密码机制来保护和分发会话密钥k,会话密钥采用对称密码算法,对通信的消息m进行加密,通信结束后销毁会话密钥.Bob明文密文密文明文数字信封制作数字信封解开数字信封Alice网络保密通信的典型应用:----数字信封对称密钥加密对称密钥解密公钥加密私钥解密AliceBob明文明文摘要摘要摘要制作数字签名验证数字签名信息可审查性的典型应用:----数字签名摘要操作数字签名摘要操作私钥加密公钥解密比较?相同->通过不相同->失败通信信道加密理论上,加密可以在开放系统互连OSI通信模型的任何层进行.实际上加密一般在最低层或较高层进行.链-链加密(link-by-linkencryption)加密在物理层进行;包括数据,路由信息,协议信息等都被加密,亦称流量保密,攻击者不知道通信信息是否是有效信息;密钥管理简单,链路相邻节点之间有共享密钥;中间节点需要进行数据解密和加密处理,有安全隐患,而且开销大.E12()节点1PD34()节点4D12()节点2E23()D23()节点3E34()P端-端加密(end-to-endencryption)数据被选择加密(传输层信息),只在接收端解密,数据保密级别高;易受流量分析攻击,因为路由信息未被加密;密钥管理复杂,每个用户之间需有共同的密钥.EAB()节点1PDAB()节点4PEAB()节点2EAB()节点3用户A用户B比较:

链-链加密端-端加密优点:

易操作,安全保密级别更高密钥管理简单软件更易完成缺点:

中间节点数据易密钥管理困难被暴露,开销大允许流量分析4.数字签名协议在计算机中:复制,剪裁,粘贴等修改可以不留下痕迹,如何保证签名的性质？否认公共网络AliceBobTrent谁是正确的？举报签名的性质:可信,不可伪造,不可重用,不可改变,不可抵赖.基于对称密码机制的数字签名协议前提:Trent是一个权威可信的仲裁者,和Alice共享密钥KA,和Bob共享密钥KB;KA①AliceBobDB(c2)m2c2m2②③④⑤KBm2=S(A)+m1+c1EB(m2)KBTrentEA(m1)m1c1m1KADA(c1)分析签名的性质？(1)签名可信:由Trent提供S(A)证明;(2)签名不可伪造:只有Alice知道KA;(3)签名不可重用,签名文件不能改变:m2包含了文件消息m1和c1,m1的改变将使得其与c1不匹配;(4)签名不可抵赖:由S(A)和c1证明.基于非对称密码机制的数字签名协议基于对称密码机制的数字签名协议存在的问题:Trent必须是完全可信和安全的;存在通信瓶颈,密钥管理等问题.分析签名的性质？用私钥加密文件,拥有安全的签名:协议简单,不需要Trent进行验证,只要保证公钥是可靠的.KApAliceBobEAv(m)mcKAvDAp(c)m(1)签名可信,不可伪造:由Alice私钥保证;(2)签名不可重用:签名是文件的函数;(3)被签名的文件不能改变:由Alice私钥保证;(4)签名不可抵赖:只有Alice拥有私钥.基于非对称密码机制的数字签名协议存在的问题:重放攻击;注意加密与签名密钥不能共用;文件大时,效率低.解决方法:时间标记:重放攻击对合同来说问题不大,但是对于银行支票问题就大了,加入时间标记.单向散列函数:签名和文件可以分开保存;存储量要求大大降低.Carol根据m1=m2判断①Carols1②③④SAv(m1)m1AliceH(m)mms1VAp(s1)H(m)m1m2①Bobc②③④Bob公钥EBp(s)sAlice签名mSAv(m)AliceAlice公钥VAp(s)sBob解密DBv(c)m采用离散对数签名方案:私钥x,公钥y=gxmodp例如:Alice对消息m签名,z=mxmodp,Bob验证.d=ctmodpBobAlice选a,bc=za·yb计算t=x-1modp-1验证d=ma·gbmodp其他签名方案带加密的数字签名:签名者参与验证的数字签名:AliceBobm’=mk1modn可以恢复m：(m’)k2k3modn可以添加自己的签名：

m’’=(m’)k2=(m)k1k2modn事例:在一个网络中,Alice和Bob同时签名或者加密消息m,让接收者验证或者解密.RSA推广:模数n=pq,k1×k2×…×km≡1mod

(n)用其中若干个ki加密的消息可以用剩下的kj解密举例:Alice有k1,Bob有k2,k3公开多个参与者的数字签名:Alice请求一个与Bob的会话密钥kTrentBobm1k产生随机会话密钥km1=EKA(k)m2=EKB(k)m2①②③④⑤5.密钥协商协议产生会话密钥,以对每一次单独的会话加密.基于对称密码机制(如WideMouthFrog协议)该协议假设网络用户Alice,Bob和KDC共享一个秘密密钥.安全性分析该协议依赖于Trent的安全性;Trent参与每一次密钥交换,容易形成瓶颈.m2也可由Alice传给Bob,如Kerberos协议中用k通信①②③AliceBobEBp(k)kcDBv(c)kAliceBobkApMallorykMpkBpkMp当Alice和Bob互传公钥时,Mallory截获,用自己的公钥取代,从而能用私钥解密双方传送的消息.基于非对称密码机制中间人攻击解决方法:保证公钥的可信,公钥证书.Diffie-Hellman密钥协商协议1976年发明,基于离散对数难题,用于密钥分配.

协议描述Alice和Bob协商一个大的素数p和准原根g.DH密钥交换协议很容易扩充到三人或者更多人.选xgxmodpgymodp选y攻击公共网络AliceBobEve共享密钥为gxymodp椭圆曲线上的DH密钥协商协议

先选取满足方程y2=x3+ax+b(modp),4a3+27b2≠0的椭圆曲线以及其上面的点构成的Abel群EP(a,b),G是EP(a,b)的生成元.选xxGyG选y攻击公共网络AliceBobEve

共享密钥为xyGShamir的三次传输协议

允许Alice和Bob在互不知道对方密钥的情况下通信,不能防止中间人攻击.

协议描述Alice和Bob有各自的密钥kA和kB;E为可交换的加密算法(如异或,指数).AliceBob选kEA(k)解密将收到的信息加密EB(EA(k))EB(k)用kB解密获得kAliceBob产生kAp/kAvA,Ep(kAp)解密得k,选RA解密得到kAp,选kEp(EAp(k))Ek(RA)解密获得RA,选RBEk(RA,RB)解密得RA和RB验证RAEk(RB)解密并验证RB通过则采用k加密密钥交换EKE协议

SteveBellovin和MichaelMerritt设计,用共享密钥加密随机产生的公开密钥,建立会话密钥.前提:Alice和Bob共享公共口令p,要生成临时的会话密钥k.基于双线性对的密钥协商协议

双线性对(Weilpairing)双线性:对于任意P,Q,RG1和a,bZqx,有(1)ê(P,P)

1;(2)ê(P+Q,R)=ê(P,R)ê(Q,P);(3)ê(R,P+Q)=ê(R,P)ê(P,Q);(4)ê(aP,bQ)=ê(abP,Q)=ê(P,abQ)=ê(P,Q)ab;非退化性:存在P,Q

G1,使得ê(P,Q)1.可计算性:对于任意的P,Q

G1,存在一个高效的算法计算ê(P,Q).Alice公钥为QA,私钥为sQABob公钥为QB,

私钥为sQBAliceBob随机选rrG计算ê(rG,sQB)计算ê(rsG,QB)

双线性对用于密钥分配PKG选择s,公开G,sG;给用户分配私钥:PKG公开G;网络用户选择私钥分别为a,b,c,计算对应的公钥PA=aG,PB=bG,PC=cG公开.三方协商的共享密钥为k:

k=ê(PB,PC)a=ê(PA,PC)b=ê(PA,PB)cAliceKDCEAp(EKp(k))用私钥解密获得kEAp(k)匿名密钥分配协议

密钥的安全性很重要,由可信的KDC产生和分配.如何避免KDC知道用户选择的密钥？思想:KDC产生足够长的连续的密钥序列,用自己的公钥加密传到网上.用户选择:Alice的公钥为kAp,KDC的公钥为kKp如何鉴别通信对象的身份？公共网络AliceBob假冒Eve身份鉴别:就是确认实体是它所声明的,身份鉴别服务提供关于某个实体身份的保证,以对抗假冒攻击.6.身份鉴别协议解决方法:使用散列函数,数据库中保持用户口令的散列值.计算机如何识别登录用户？口令安全信道Alice服务器攻击:Eve侵入服务器数据库,窃取用户口令.窃取Eve段桂华duangh@口令安全信道Alice服务器猜测Eve口令选择:人们在选择自己的口令时,通常选择一个弱口令,如选择的是zs111而不是*9(hH/A.字典攻击:首先尝试最可能的密钥,非常有效,能破译一般计算机上40％的口令.段桂华duangh@常用的攻击方式：用户姓名,简写字母,帐户等有关个人信息;从各种数据库中得到的单词;各种单词的不同置换形式,如大小写,误写;尝试词组.要求:密钥既容易记忆,又难以被猜中.【举例】Standhighandseefar.→^Shasf^

Chuanguoshuiwuhen.→~Cgswh~建议:加入标点符号;由较长的短语的首字母组成字母串.口令公共网络Alice服务器截获Eve重放攻击:Eve在公共网络上截获Alice的口令,进行重放登录.解决方法:一次性口令.数据库中需保存很多口令散列值段桂华duangh@Alice服务器Alice,R保管计算f(xi),与xi+1比较,匹配成功则用xi代替xi+1保存Alice,xn+1x1,x2,…,xn登录Alice,xi确认取消xix1=f(R)x2=f(x1):xn+1=f(xn)SKEY协议由于每个数只用一次,因此对数据库攻击用处不大;节约存储开销.解决方法:密码技术通信双方如何鉴别对方的身份？公共网络AliceBob假冒Eve身份鉴别:就是确认实体是它所声明的,身份鉴别服务提供关于某个实体身份的保证,以对抗假冒攻击.使用对称密码技术鉴别前提：假设Alice和Bob共享密钥k.鉴别：拥有密钥k的人即是确认身份的人.AliceBobRA选随机数RB,Hk(RA,RB,B)RB,Hk(RA,RB,B)计算并比较Hk(RA,RB,B)Hk(RB,A)计算并比较Hk(RB,A)①②③④⑤使用公钥密码技术鉴别前提:用户保存自己的私钥,公开公钥文件.鉴别:拥有与公钥kp对应的私钥kv的人即是可确认身份的人.AliceBob请求对r加密在数据库中查找Alice的公钥验证随机数rAlice,EAv(r)7.秘密共享协议

秘密共享又称为门限方案,保证在协议中只有当足够多的一组成员达成一致时才能共享一个秘密.(k,n)门限方案:在n个人中,每人共享秘密m的部分信息Di

任何k-1部分信息不能恢复m

由任何k部分信息Di可以很容易计算出m

具有代表性的有Shamir门限方案和Asmuth-Bloom门限方案.则m=f(0)Shamir门限方案方案描述:构建k-1次多项式f(x)=m+a1x+a2x2+…+ak-1xk-1modp计算D1=f(1),D2=f(2),…Dn=f(n)从其中选k个即可恢复m,给定k个Dj1,Dj2,…,Djk,=88-1

(x-3)(x-5)+10(-4)-1

(x-1)(x-5)+118-1

(x-1)(x-3)mod17=120(x2-8x+15)+40(x2-6x+5)+165(x2-4x+3)mod17=2x2+10x+13mod17所以:m=f(0)=13【举例】设m=13,n=5,k=3,p=17，构建的k-1次多项式

f(x)=13+10x+2x2mod17

则各秘密份额为:D1=8,D2=7,D3=10,D4=0,D5=11取D1,D3,D5Bloom门限方案方案描述:选取t个严格递增的m1,m2,…,mn,满足gcd(mi,mj)=1计算

M=m1

m2

…

mn

Hk=m1

m2

…

mk-1

mk

hk-1=mn

mn-1

…

mn-(k-1)+1

要求Hk(N+1)hk-1,N为一个大的整数对于任意的秘密x(hk-1<x<Hk)计算：ai=x%mi，则{(a1,m1),(a2,m2),…(an,mn)}是一个(k,n)门限方案.分析根据中国剩余定理

m1,m2,…,mn两两互素,同余方程组

x=a1modm1

x=a2modm2

…

x=anmodmn

x的解等价于:x=a1T1M1+…+anTnMnmodM

其中M=m1

m2

…

mn

Mi=M/mi

Ti=Mi-1modmi

则可构建k项的同余方程组

x=a1modm1

x=a2modm2

…

x=akmodmk假设已知(a1,m1),(a2,m2),…(ak,mk)1

k

nx=a1T’1M’1+…+akT’kM’kmodM’根据前面已知的Hk为k个不同mi的最小乘积,而hk-1为k-1个不同mi的最大乘积,则有:M’

Hk>x

故可以通过上式获得x.

则可构建k-1项的同余方程组

x=a1modm1

x=a2modm2

…

x=ak-1modmk-1假设已知(a1,m1),(a2,m2),…(ak-1,mk-1)1

k

n根据前面已知的Hk为k个不同mi的最小乘积,而hk-1为k-1个不同mi的最大乘积,则有:x=a1T’’1M’’1+…+ak-1T’’k-1M’’k-1modM’’M’’

hk-1<x

故不能通过上式获得x,x可能的值有:

hk-1<x<Hk

(Hk-hk-1)/hk-1=N个举例则消息x=500的(3,4)门限方案为:a1=500mod9=5a2=500mod11=5a3=500mod13=6a4=500mod14=10{(5,9)(5,11)(6,13)(10,14)}已知k=3,t=4,m1=9,m2=11,m3=13,m4=14，假设已知(5,9)(5,11)(6,13),构造方程:x=5mod9=a1modm1x=5mod11=a2modm2x=6mod13=a3modm3M=91113=1287

M1=1113=143M2=913=117M3=911=99T1=143-1mod9=8-1mod9=-1T2=117-1mod11=7-1mod11=8T3=99-1mod13=8-1mod13=5所以x=5143(-1)+51178+6995mod1287=500mod1287假设已知(5,9)(6,13),构造方程:x=5mod9=a1modm1x=6mod13=a2modm2

x=513(13-1mod9)+69(9-1mod13)=617mod117=32mod117

所以x可能的值为：266,383,500,617,734,…3.2中级密码协议3.2.1数字时间标记协议3.2.2阈下信道3.2.3安全计算协议3.2.4位承诺协议3.2.5智力扑克协议3.2.6密钥托管协议3.2.7密钥分发协议1.数字时间标记协议

数字时间标记的性质数据本身必须有时间标记;文件的改变很明显;不可能用不同于当前日期和时间来标记文件.缺点:无保密性;数据库巨大;存在传输错误;Trent可信.事件:在版权和专利争端中,需要标记时间.仲裁解决办法策略:AliceTrent文件副本在文件副本上签时间标记并保存副本特点:散列值可保密;Trent不用保存文件副本;可验证签名.缺点:Alice和Trent合谋.解决方法是:将Alice的时间标记同以前由Trent产生的时间标记链接起来.改进的仲裁解决办法策略:使用散列函数和数字签名AliceTrenthash(m)对加上时间标记的文件副本签名STv(hash(m)+T)2.阈下信道协议要求:Walter和Bob都能验证m;Water无法发现s.Alice私钥为d,公钥为e=gdmodp,gcd(s,p-1)=1

Alice和Bob在Walter的监控下通过传送签名消息m来传送秘密s.基于ElGamal协议:p