资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,计算机科学与信息学院,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。,密码学复习,1/190,第1章、概论：信息时代与信息安全。,基本知识点：信息安全定义、发展趋势,要求掌握基本概念、理论、原理：,掌握信息概念,。,了解信息安全含义及发展趋势，掌握信息安全概念。,2/190,第1章、密码学基本概念,基本知识点：,密码学定义和分类、古典密码,要求掌握基本概念、理论、原理：,掌握密码定义、密码体制订义、密码学分类。掌握古典密码学计算方法。了解古典密码种类与统计分析。,重点是密码学定义和分类。古典密码学计算方法。,3/190,密码可能经受攻击,加密算法,加密黑盒子，可加密任意明文得到对应密文,选择明文攻击,加密算法,解密黑盒子，可解密任意密文得到对应明文,选择密文攻击,加密算法，,截获部分密文和对应明文,已知明文攻击,加密算法,截获部分密文,惟密文攻击,攻击者拥有资源,攻击类型,4/190,密码学目标,：Alice和Bob两个人在不安全信道上进行通信，而破译者Oscar不能了解他们通信内容。主动攻击者Joy不能将假信息注入系统或篡改、破坏信息。,加密通信模型,Alice,加密机,解密机,Bob,安全信道,密钥源K,1,Oscar,m,c,m,k,1,Joy,密钥源K,2,k,2,c,m,5/190,完善保密性、理论保密性、实际保密性,结论：,因为有式子：H(K|C,L,)H(K)-l 1-H(M,L,)/L,所以提升系统保密性路径有两条：,1、提升密钥量，增大H(K)。,2、对明文进行压缩减小1-H(M,L,)/L。,6/190,恺撒密码,破译以下密文：,wuhdwb lpsrvvleoh,TREATY IMPOSSIBLE,Ci=E(Pi)=Pi+3,加密算法：,字母表：(密码本）,ABCDEFGHIJKLMNOPQRSTUVWXYZ,defghijklmnopqrstuvwxyzabc,即：C=E(p)=(p+3)mod(26),7/190,其它单字母替换,乘数密码,对字母进行无规则重新排列,E(i)=3*i mod 26,ABCDEFGHIJKLMNOPQRSTUVWXYZ,adgjmpsvybehknqtwzcfilorux,普通形式：,E(i)=k*i mod 26,8/190,其它单字母替换,仿射密码（,乘数加移位）,E(i)=k,1,*i+k,0,mod 26,将仿射密码扩展到普通形式：多项式密码,E(x)=k,t,*x,t,+k,t-1,*x,t-1,+k,1,*x+k,0,mod 26,以上单表代换密码均能够经过统计规律简单破译。,9/190,多表置换实例：维吉尼亚密码,维吉尼亚密码引入了混同。,设：密钥为：,k,=,k,1,k,2,k,m,明文为：,M,加密变换：,1),将,M,按每,m,个字母分组：,M,=,M,1,M,2,M,n,，,其中,M,j,=,m,j,1,m,j,2,m,jm,，,j,=1,2,n,;,2)加密,E,k,(,m,j,)=,c,j,1,c,j,2,c,jm,，,其中,c,ji,=,m,ji,+,k,i,mod 26，,j,=1,2,n,；,i,=1,2,m,10/190,第2章、序列密码,基本知识点：,序列密码概念、线性移位存放器密码，非线性序列密码，有限状态自动机密码，,要求掌握基本概念、理论、原理：,掌握线性移位存放器密码基本原理。了解非线性序列密码,、,、有限状态自动机密码,。,重点和难点：,重点序列密码算法。难点序列密码算法详细实现。,11/190,加法流密码框图,k,I,安 全 信 道,k,I,KG KG,k,i,k,i,m,i,c,i,c,i,m,i,E,ki,(,m,i,),E,ki,(,m,i,),12/190,二元线性移位存放器,二元条件下,a,i,0,1，,c,j,0,1，即断开或连通，,为模2加，反馈函数可写成,n,阶线性递推关系式,c,n,c,n-1,c,n-2,c,1,c,0,a,i+n-1,a,i+n-2,a,i+1,a,i,a,i-1,a,1,a,0，,x,n,x,n-1,x,2,x,1,为模2加(异或),指每位信息只有0，1两种状态,13/190,m,序列破译,已知,a,i,a,i+1,a,i+2n,，由递推关系式可得出下式,式中有,n,个线性方程和,n,个未知量，故可惟一解出,c,i,，0,i,n,-1。,14/190,第3章、分组密码,基本知识点：,分组密码概念，数据加密标准（DES），IEDA密码，高级数据加密标准（AES）。分组密码工作模式和应用技术。,要求掌握基本概念、理论、原理：,掌握,分组密码概念，数据加密标准（DES），高级数据加密标准（AES）。分组密码工作模式，了解IEDA密码。,重点和难点：,DES，AES，分组密码工作模式。,15/190,基本概念,整除：有整数,a，若存在另一整数m能除尽a，余数为0，则称a能被m整除，记为：,m|a,素数：只能被1和本身整除数。,合数：能被本身和1之外数整除。,公因数(公因子)：有整数,a、b，若存在另一整数m能整除a和b，即有：m|a、m|b，则m是a、b,公因数。记为：,m=(a,b),最大公因子记为,(,greatest common divisor),gcd,互素：两个整数,a、b，若它们最大公因子为1，即：,gcd(a,b)=1,，则称,a、b,互素。,.,16/190,定理3-1,若,(,a,m,)=1,则,a,1,mod,m,存在.,例1,求,5,1,mod 13,和,11,1,mod 13.,设,m,1为整数,a,为任意整数,.假如存在整数,b,使得,ab,1,mod,m,则称,b,为,a,模,m,逆元,，记为,b,a,1,mod,m,求,5,1,mod 17.,逆元,逆元,17/190,定理 3-,2,模,m,同余关系是等价关系.,1、若有,a,mod,m,和,b,mod,m,则,a,b,mod,m,2、若有,a,b,mod,m,则有,b,a,mod,m,3、若有,a,b,mod,m，b,c,mod,m,则有,a,c,mod,m,定理,3-3,若,a,b,mod,m,，,c,d,mod,m,，则,(1),a,c,b,d,mod,m,;,(2),ac,bd,mod,m,定理,3-4,若,ac,bc,mod,m,且,c,与,m,互素，则,a,b,mod,m,同余部分性质,同余部分性质,18/190,例2,已知,42,7 mod 5,且,1,=,(7,5),则,6,1 mod 5,例3,63,3 mod 12,.,定理,3-5,若,ac,bc,mod,m,且,d=,(,c,m,),则,a,b,mod,m/d,同余部分性质,同余部分性质,19/190,同余运算（模运算）,加法：,a,mod,m,+,b,mod,m,(,a,+,b,)mod,m,乘法：,a,mod,m,b,mod,m,(,a,b,)mod,m,与普通算术运算类似，一样有：,交换率,结合率,分配率,当,m=,2时,a,mod,m,+,b,mod,m,就是 异或a,b,同余运算（模运算）,20/190,DES加密算法总框图,IP置换,T1,T2,T16,IP,-1,置换,子,密,钥,发,生,器,m,c,k,DES加密器,k1,k2,k16,21/190,子密钥发生器,16次,迭代,DES结构,22/190,4、,f,运算：,(,关键部分),E阵-加边运算：32-48,32位P置换阵,48位子密钥输入,32位前级右阵输入,异或运算,8个6输入4输出非线性代换盒S盒,23/190,S盒运算：S盒结构,以S1为例：,b1、b6组成两位2进数：0011,即03。,b2、b3、b4、b5组成4位2进数：00001111即015,b2b5,b1,b6,第一个S盒S1,24/190,5、子密钥发生器,k,PC-1,LS1,LS1,C,0,D,0,LS2,LS2,C,1,D,1,PC-2,K1,PC-2,K2,LS16,LS16,C,15,D,16,PC-2,K16,25/190,Electronic Codebook Book(ECB),电码本模式,26/190,Cipher Block Chaining(CBC),密码分组链接模式,27/190,Cipher FeedBack(CFB),密码反馈模式,28/190,Output FeedBack(OFB),输出反馈模式,29/190,1、IDEA描述,：,明文,：分组长度,64,位,密钥,：解密密钥和加密密钥不一样,长度,均为,128,位,基本运算,：,三个不一样代数群进行混合运算，用软件,和硬件均轻易实现,而且IDEA混同特征也是由这,三个运算来实现：,1.,异或运算,记为 ；,2.,模2,16,加法运算,记为 ；,3.,模2,16,+1乘法运算,记为 .,+,+,30/190,31/190,输出,设第八轮输出为,W,1,W,2,W,3,W,4,则分别与最终4个子密钥,Z,1,(9),Z,2,(9),Z,3,(9),Z,4,(9),作运算：,W,1,16,Z,1,(9),=,Y,1,W,2,+,16,Z,2,(9),=,Y,2,W,3,+,16,Z,3,(9),=,Y,3,W,4,16,Z,4,(9),=,Y,4,密文为：,Y,1,Y,2,Y,3,Y,4,32/190,解密过程与加密过程完全一样,只是所用解密蜜钥对应于加密密钥为:,轮次 加密密钥 解密密钥,1,Z,1,(1),Z,2,(1),Z,3,(1),Z,4,(1),Z,5,(1),Z,6,(1),Z,1,(9),1,Z,2,(9),Z,3,(9),Z,4,(9),1,Z,5,(8),Z,6,(8),2,Z,1,(2),Z,2,(2),Z,3,(2),Z,4,(2),Z,5,(2),Z,6,(2),Z,1,(8),1,Z,2,(8),Z,3,(8),Z,4,(8),1,Z,5,(7),Z,6,(7),3,Z,1,(3),Z,2,(3),Z,3,(3),Z,4,(3),Z,5,(3),Z,6,(3),Z,1,(7),1,Z,2,(7),Z,3,(7),Z,4,(7),1,Z,5,(6),Z,6,(6),4,Z,1,(4),Z,2,(4),Z,3,(4),Z,4,(4),Z,5,(4),Z,6,(4),Z,1,(6),1,Z,2,(6),Z,3,(6),Z,4,(6),1,Z,5,(5),Z,6,(5),5,Z,1,(5),Z,2,(5),Z,3,(5),Z,4,(5),Z,5,(5),Z,6,(5),Z,1,(5),1,Z,2,(5),Z,3,(5),Z,4,(5),1,Z,5,(4),Z,6,(4),6,Z,1,(6),Z,2,(6),Z,3,(6),Z,4,(6),Z,5,(6),Z,6,(6),Z,1,(4),1,Z,2,(4),Z,3,(4),Z,4,(4),1,Z,5,(3),Z,6,(3),7,Z,1,(7),Z,2,(7),Z,3,(7),Z,4,(7),Z,5,(7),Z,6,(7),Z,1,(3),1,Z,2,(3),Z,3,(3),Z,4,(3),1,Z,5,(2),Z,6,(2),8,Z,1,(8),Z,2,(8),Z,3,(8),Z,4,(8),Z,5,(8),Z,6,(8),Z,1,(2),1,Z,2,(2),Z,3,(2),Z,4,(2),1,Z,5,(2),Z,6,(2),9,Z,1,(9),Z,2,(9),Z,3,(9),Z,4,(9),Z,1,(1),1,Z,2,(1),Z,3,(1),Z,4,(1),1,其中,Z,1,为,Z,模,2,16,+1逆元.而,Z,为为,Z,模,2,16,负元,.,33/190,4.AES 算法普通描述,加密 解密,34/190,分组长度和密钥长度均为128 bits时Rijndael加密算法框图,Data/Key,Addition,Rnd,0,Rnd,1,Rnd,8,Final,Rnd,Key,Schedule,Cipher,Text,Key,Plain,Text,35/190,Rijndael Round组成（轮函数）,字节代换,字节移位(行移位),列混合,+,Round,Key,普通轮变换,字节代换,字节移位(行移位),+,Round,Key,最终一轮轮变换,密钥加,密钥加,36/190,ByteSubstitution,该变换能够用一个256字节表来实现,B,0,0,B,0,1,B,0,2,B,0,3,B,1,0,B,1,1,B,1,2,B,1,3,B,2,0,B,2,1,B,2,2,B,2,3,B,3,0,B,3,1,B,3,2,B,3,3,A,0,0,A,0,1,A,0,2,A,0,3,A,1,0,A,1,1,A,1,2,A,1,3,A,2,0,A,2,1,A,2,2,A,2,3,A,3,0,A,3,1,A,3,2,A,3,3,取逆,仿射变换,37/190,ByteRotation(字节移位),0,4,8,12,1,5,9,13,2,6,10,14,3,7,11,15,0,4,8,12,5,9,13,1,10,14,2,6,15,3,7,11,循环左移1字节,循环左移2字节,循环左移3字节,38/190,7、MixColumn(列混合),将状态列看作是有限域GF(,2,8)上多项式a(x)，与多项式c(x)=03,x,3+01,x,2+01,x,+02相乘(模,x,4,1,)。,令b(x)=c(x)a(x)，写成矩阵形式为：,b,0,02 03 01 01,a,0,b,1 =,01,02 03 01,a,1,b,2,01 01,02 03,a,2,b,3,03 01 01 02,a,3,39/190,A,0,0,A,0,1,A,0,2,A,0,3,A,1,0,A,1,1,A,1,2,A,1,3,A,2,0,A,2,1,A,2,2,A,2,3,A,3,0,A,3,1,A,3,2,A,3,3,K,0,0,K,0,1,K,0,2,K,0,3,K,1,0,K,1,1,K,1,2,K,1,3,K,2,0,K,2,1,K,2,2,K,2,3,K,3,0,K,3,1,K,3,2,K,3,3,B,0,0,B,0,1,B,0,2,B,0,3,B,1,0,B,1,1,B,1,2,B,1,3,B,2,0,B,2,1,B,2,2,B,2,3,B,3,0,B,3,1,B,3,2,B,3,3,A,3,3 ,K,3,3,B,3,3,(mod 2),40/190,Nk=6时密钥扩展,K,0,0,K,0,1,K,0,2,K,0,3,K,1,0,K,1,1,K,1,2,K,1,3,K,2,0,K,2,1,K,2,2,K,2,3,K,3,0,K,3,1,K,3,2,K,3,3,K,0,K,1,K,2,K,3,K,0,K,1,K,2,K,3,K,4,K,5,K,6,K,7,+,+,+,当i/Nk余数不为0时,41/190,K,0,K,1,K,2,K,3,K,4,K,5,K,6,K,7,字节代换,1字节移位,+,Rcon,轮常数,当i/Nk余数为0时,42/190,W,i-4,W,i-3,W,i-2,W,i-1,W,i,字节代换,1字节移位,+,Rcons,+,Key expansion,4 =i 0,P,i,互不相同,则,(n)=,P,i,ai,(1-1/,P,i,)即：,(n)=n(1-1/p,1,)(1-1/p,2,)(1-1/p,n,),若gcd(m,n)=1,则,(mn)=,(m),(n),尤其地,若p,q且都是素数,则：,(pq)=(p-1)(q-1),60/190,3、Euler定理,定理4.2：Euler定理:,若a与n为互素正整数,则:,a,(n),1 mod n,其中：a对n必须是互素；,(n)=n(1-1/p,1,)(1-1/p,2,)(1-1/p,n,),p,1,p,2,p,n,是r素数因子,(n)是n欧拉函数,，它确定1,2,n,中有多少个是与n互素。,比如：20=225，有两个素数2和5，这么，,(20)=20(1-1/2)(1-1/5)=8,即20中有8个整数与20是互素，即它们没有2或5为因子:,1,3,7,9,11,13,17,19,61/190,Euler定理推论,推论:若n=pq,p,q都是素数,k是任意整数,则,m,k(p-1)(q-1)+1,m mod n,对任意0,m,n,证实:若m=0或n,结论是显然;若m与n互素,注意到,(n)=(p-1)(q-1),由Euler定理可得到结论;不然m必定是p或者q倍数,不妨设m=sp,则0sq为正整数,m与q互素,由Euler定理得到:,m,(q),1 mod q,(,m,(q),),k,(p),1 mod q,m,k(p-1)(q-1),=tq+1 t是整数,等式两边乘以m=sp,得到:,m,k(p-1)(q-1)+1,=(tq+1)sp=tspq+sp,m mod n,62/190,来自孙子算经问题：,“今有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二,问物几何?”,普通地，称,ax,b,mod,m,为,线性同余式,.,4、线性同余式,63/190,中国剩下定理-孙子定理,64/190,6、欧基里德(Euclid)算法求最大公因数,一个结论：假如a是任意正整数，b是正整数，有：,gcd(a,b)=gcd(b,a mod b),欧基里德(Euclid)算法就是重复进行上述步骤,例：gcd(55,22)=gcd(22,55 mod 22),=gcd(22,11),=gcd(11,22 mod 11),=gcd(11,0),=11,这就是,Euclid,算法,也叫,碾转除法,65/190,扩展欧基里德(Euclid)算法求逆元,求d,-1,mod f,(X1,X2,X3)-(1,0,f);(Y1,Y2,Y3)-(0,1,d),If Y3=0 Then 无解,If Y3=1 Then Y2=d,-1,mod f,Q=X3/Y3 即Q是X3/Y3商部分,(T1,T2,T3)-(X1-QY1,X2-QY2,X3-QY3),(X1,X2,X3)-(Y1,Y2,Y3),(Y1,Y2,Y3)-(T1,T2,T3),66/190,素数定理,素数定理：,(,x,):小于,x,素数个数,素数定理说明：素数有没有穷多个，,但数越大素数越稀少。,67/190,费尔玛定理,定理：,(Fermat)定理,，若p是素数，a是正整数，且gcd(a,p)=1，则:,a,p-1,1 mod p,假如ap，则一定满足gcd(a,p)=1,68/190,强伪素数,强伪素数设n是一个大于4奇整数，s和t是使得(n-1)=2,s,*t正整数，其中t为奇数，设B(n)是以下定义整数集合：a属于集合B(n)当且仅当2an-2且,1:a,t,mod n=12:存在整数j，0=j1，t为奇数。任选正整数a，检验：,假如a不满足上述两条件，则n必为合数。选不一样a重复试验r次，若r次均满足上式，则n为不为素数概率,(1/4),r,。r足够大时能够相当有把握地认为n是素数。,Miller-Rabin素性检测法找一个m比特素数要O(m,4,)计算量。,70/190,Miller-Rabin素性检测法,1、找到奇整数n，计算n-1=2,s,*m2、随机选取整数b,1bn-13、a=b,m,(mod n),如a=1或n-1则经过验证4、for 1 to s-1 do5、a=a,2,t(mod n),如a=n-1则经过验证6、反之n为合数,71/190,1、RSA算法描述,加密：,C=M,e,mod N,其中,0,MN,解密：,M=C,d,mod N,公钥为（,e，N），,私钥为（,d，N）,必须满足以下条件：,M,ed,=M mod N,计算,M,e,和,C,d,是比较轻易,由,e,和,n,确定,d,是不可行,72/190,2、RSA,密钥产生过程,随机选择两个大素数,p,q,计算,N=p.q,注意,(N)=(p-1)(q-1),选择,e,使得,1,e,(N),且,gcd(e,(N)=1,解以下方程求出,d,e.d=1 mod,(N),且 0,dN,公布公钥:,K,U,=e,N,保留私钥:,K,R,=d,p,q,(N),73/190,3、RSA 使用,发送方要加密明文,M:,取得接收方公钥,K,U,=e,N,计算:,C=M,e,mod N,其中,0,M a,i,(i=1,n),，,然后选择一个与m互素整 数w，然后,a,i,=wa,i,(mod m)(i=1,n),。,这里a,i,是伪随机分布。这么得到背包是,非超递增背包,。,加密,将明文分为长度为n块X=(x,1,x,n,),然后用公钥A=(a,1,a,n,)，将明文变成密文,S=E(X)=a,i,x,i,解密,先计算S=w,-1,S mod m,再求解简单背包问题，S=a,i,x,i,超递增背包转换为非超递增背包,【9.3 公开密钥密码体制】,77/190,六、RSA改进Rabin密码体制,现在还没有证实破译RSA与分解大整数等价。,而,Rabin密码体制已经被证实与分解大整数等价。,78/190,Legendre符号,设p是一素数，a是整数，对方程：,x,2,=a mod p,有三种情况：a是p平方剩下；a是p非平方剩下；a能被p整除，即x=0。这三种情况用数字分别表示为：1、-1、0，记为 称为,Legendre符号。,79/190,Legendre符号计算,Legendre符号能够用下面公式计算：,即a是p平方剩下时，有：,80/190,六、椭圆曲线密码,为了确保安全RSA长度越来越长，这么计算规模就越来越大。,椭圆曲线密码,是一个新密码体制，它优点是在一样加密强度下，密钥比RSA短一个数量级。,81/190,椭圆曲线密码,RSA,512,768,1024,2048,21000,ECC,106,132,160,211,600,在同等安全条件下RSA与ECC密钥长度比较,112位3DES,128为AES,强度远大于2048RSA,82/190,1、离散对数,假如a与n互素，则最少有一整数m满足：,a,m,1,mod,n,满足上面方程最小正整数m称为模n下a阶。,定理,：,设a阶为m，则a,k,1,mod,n,充要条件是k为m倍数。,a阶整除,(n)。,83/190,本原根,假如a阶等于,(N)，,则称,a,为,n,本原根。,尤其：假如,a,是素数,p,本原根，则：,a、a,2,、a,3,、a,p-1,mod p,都不一样，即得到了比p小全部数。,84/190,离散对数,设p是素数，a是p本原根，,a、a,2,、a,3,、a,p-1,mod p,产生了1到p-1全部数，对于全部,b,1、2p-1,有唯一i,1、2p-1使得,b,a,i,mod,p,称为i模p下以a为底b离散对数。记为：,i log,a,b,mod,p,85/190,Elgamal 公钥密码,体制参数选取：,1、选一个大素数p,作模。,2、选一个随机数x,再选一个底g。,g和x均小于p,3、计算y=g,x,mod p,4、公钥（y,p,g）,私钥x,86/190,l,加密(A)：明文,m,p,选取,k,p,1,计算,K,y,k,mod,p,c,1,g,k,mod,p c,2,Km,mod,p,密文,c=,(,c,1,c,2,),=,(,g,k,y,k,m,),l,解密(B):先计算,K,y,k,(,g,k,),x,=,(,c,1,),x,mod,p,而,m=c,2,/,K,mod p,Elgamal 公钥密码,Elgamal加密解密过程,87/190,Elgamal 公钥密码,窃听者收到c1、c2要求m或k均面临离散对数难题.,c,1,g,k,mod,p,c,2,Km,mod,p K,y,k,mod,p,88/190,3、,椭圆曲线图象,椭圆曲线(记为,E,)不是椭圆，而是由一个三,次方程,y,2,+,axy,+,by,=,x,3,+,cx,2,+,dx,+,e,(1),所描述曲线.类似于求椭圆周长方程.,设,F,是一个域,假如,F,中一对数,x,y,满足(1),则称,(,x,y,)是,F,上椭圆曲线,E,点.另外,加上一个无穷远点,O,.,89/190,椭圆曲线上点加+运算,P,Q,R,-R,P,+,Q,+,R,=,O,或者,Q,+,P,=-,R -R,是,R,逆元,90/190,椭圆曲线上点加+运算,倍点定义：2Q=Q+Q=-S,过Q作切线，交于S，过S作垂线交于-S,Q,S,-S,91/190,+运算群性质,定理,设,P,Q,U,是椭圆曲线,E,上点,那么,(a),P,+,Q,=,Q,+,P,;,(b)(,P,+,Q,),+,U,=,P,+,(,Q,+,U,);,(c),P,+,O,=,P,;,(d),E,上每一点,P,存在点,P,使得,P,+,(,P,)=,O,；,(e)假如,P,Q,连线与,E,相交于另一点,R,则,(,P,+,Q,),+,R,=,O,.,92/190,椭圆群,E,p,(,a,b,),加法：,假如,P,=(,x,y,)，则,P,=(,x,y,),而且,P+,(,P,)=,O,；,假如,P,=(,x,1,y,1,)，,Q,=(,x,2,y,2,),那么,P+Q,=(,x,3,y,3,),其中,93/190,椭圆曲线,阶,定义,设,P,是椭圆曲线,E,上点,假如存在最小正整数,n,使得,nP,=,O,则称,n,为点,P,阶.,94/190,5、,有限域上椭圆曲线,模,p,椭圆群,选取两个非负整数,a,bp,使得,4,a,3,+27,b,2,(mod,p,),0,用,E,p,(,a,b,)表示满足以下条件,模,p,椭圆群：其元素(,x,y,)为满足以下方程小于,p,非负整数点加上无穷远点,O,:,y,2,x,3,+,ax,+,b,mod,p,95/190,思索：,考虑方程,Q=kP,其中,Q,P,E,p,(,a,b,),而,k,p,.,给定,Q,确定,k,和,P,相对困难.,在椭圆曲线上难题,模,96/190,6、,椭圆曲线上,Elgamal密码系统(ECC,)：,1.选取,p,2,180,和整数,a,b,得到群,E,p,(,a,b,),公开；,2.选取generator point,G,=(,x,1,y,1,),满足：,G,阶,n,是一个非常大素数，,公开,；,3.A 选取,n,A,n-,1为私人密钥，并产生,公开密钥,P,A,=,n,A,G,是,E,p,(,a,b,)中点,；,生成元,97/190,加密,：,A要发报文,P,m,给B，取随机数,k,，并将,P,m,加密为：,C,m,=,kG,P,m,+,kP,A,解密,：,P,m,+,kP,A,n,A,(,kG,),=,P,m,+,k,(,n,A,G,),n,A,(,kG,)=,P,m,加密与解密,98/190,l,加密(A)：明文,m,p,选取,k,p,1,计算,K,y,k,mod,p,c,1,g,k,mod,p c,2,Km,mod,p,密文,c=,c,1,c,2,=,g,k,y,k,m,l,解密(B):先计算,K,y,k,(,g,k,),x,=,(,c,1,),x,mod,p,而,m=c,2,/,K,mod p,ECC对照Elgamal加密解密过程,注意：其计算复杂度：ECC+与普通*相当。,ECC*与普通指数计算相当。,99/190,7、ECC信息嵌入,椭圆曲线上点数是有限。,定理：,在GF(p)上椭圆曲线y,2,=x,3,+ax+b 其中a,b,GF(p)，4a,3,+27b,2,0，在第一象限中整数点加O点有：,个，其中 是Legendre符号。,定理：,100/190,ECC信息嵌入,y,2,=x,3,+ax+b (a,b,GF(p)，4a,3,+27b,2,0),怎样将明文信息m嵌入到椭圆曲线上整数点中？,通常以x坐标作明文嵌入。,计算：,x=(mk+j)，通常30k50，j=0、1、2,jm 用来凑x坐标。,解密后取得信息m=x/k，即取x/k整数商。,101/190,ECC信息嵌入,对于椭圆曲线：y,2,=x,3,+ax+b mod p (a,b,GF(p)，4a,3,+27b,2,0),按照下面方法计算x坐标：,x=(mk+j)，通常30k50，j=0、1、2jm,其计算结果是曲线上坐标点概率大于：1-2,-k,。,这是因为：,y,2,=x,3,+ax+b mod p 中x,3,+ax+b有二分之一是模p平方剩下，所以k越大，0jk能凑出坐标点可能就越大。,所以k=30时凑不出概率是1/2,30,，几乎不可能。,102/190,8,、,Diffie-Hellman,密钥交换,Diffie-Hellman,算法,Diffie-Hellman算法是第一个公开密钥算法，创造于1976年。,Diffie-Hellman算法能够,用于密钥分配，,但不能,用于加密或解密信息,。,安全性：,在于在有限域上计算离散对数非常困难。,103/190,Diffie-Hellman密钥交换协议,安全性是基于求 mod,p,(素数)离散对数困难度,先选择一个大素数,p,和一个小于,p,数,g,给予公开;,l,A和B各选一个数,k,a,和,k,b,(l，是一大素数),，,以及随机数,a,1,a,2,a,l,1,GF(,q,).,结构多项式：,f,(,x,)=,s,+,a,1,x,+,a,2,x,2,+,a,l,1,x,l,1,其中,s,是秘密信息.,令,是,GF,(,q,),本原根.并令,k,i,=,f,(,i,),i,=1,2,l,称为子密钥,由,A,i,保管.,Shamir门限方案,127/190,由,拉格朗日,插值公式,：,有,p,*,(,a,j,)=,k,j,j,=1,2,l,p,*,(,x,)=,f,(,x,),而且,s,=,f,(0),从而只有,l,个合作者在一起才能确定,f,(,x,),进而恢复秘密,s,.,128/190,第6章 消息认证与杂凑算法,基本知识点：,消息认证与认证码，杂凑算法与杂凑函数，MD5、SHA1,。,要求掌握基本概念、理论、原理：,基本概念,：,消息认证与认证码，使用方法与对其攻击，杂凑函数。,原理：,认证码原理、杂凑函数普通结构MD5、SHA1原理、使用方法。,重点和难点：,MD5、SHA1使用方法和算法实现。,129/190,纯认证系统模型,信源,认证编码器,认证译码器,信宿,安全信道,密钥源k,篡扰者,k,窜扰者攻击分为两种：1、仿冒伪造（无密文伪造）,2、代换伪造（已知密文伪造）,130/190,2、消息认证码(MAC码)定义与使用,认证码产生：通惯用,哈希函数(杂凑函数),h,产生固定长度哈希值,h,(,m,)。,使用有各种方式：,a)消息认证,A,B,131/190,3、完善认证性,完善认证是指：窜扰者伪造认证码最正确策略只能随机选择认证码。,认证码安全性一样分为：理论安全性和实际安全性。,理论安全性,又称作,无条件安全性,。,窜扰者破译体制所做任何努力都不会优于随机试凑方式。,实际安全性,假如破译一个系统在原理上是可能，但以全部已知算法和现有计算工具不可能完成所要求计算量，就称其为,计算上安全,。假如能够证实破译某体制困难性等价于处理某个数学难题，就称其为,可证实安全,。,132/190,二、杂凑函数（Hash哈希函数）,哈希函数又叫,散列函数,或,杂凑函数,。,杂凑函数,又分为两类：,密码杂凑函数,普通杂凑函数,杂凑函数均为公开函数，都是将任意长消息转换成较短固定长度一个值作信息摘要。密码杂凑函数还需要一个密钥来控制。,改变消息中任意一位或几位都会使杂凑值改变。与密码不一样，消息到杂凑值改变是单向，从杂凑值不能恢复出消息。,133/190,1、单向杂凑函数,定义6.1,：若杂凑函数h是单向，则称h叫,单向杂凑函数,。即计算H=h(M)是轻易，要找一M使H=h(M)是不可行。,定义6.2,：若单向杂凑函数H=h(M)，在给定H下，要找一M使H=h(M)在计算上不可行，则称h是,弱单向杂凑函数,。,定义6.3,：对单向杂凑函数h，若要找一对M1，M2，M1,M2，使H=h(M1)=h(M2)在计算上不可行，称为,强单向杂凑函数,。即,无碰撞,。,134/190,2、应用杂凑函数基本方式,杂凑算法可与加密及数字签字结合使用，实现系统有效、安全、保密与认证。其基本方式如图6-3-1中所表示。,(,a,)发端,A,收端,B,M,E,k,M,|,h,(,M,),M,h,(,M,),MUX,E,D,h,h,k,k,比较,h,(,M,)判决,h,(,M,)输出,图中(,a),部分，发端,A,将消息M与其杂凑值,h,(,M,)链接，以单钥体制加密，后送至收端,B,。收端用与发端共享密钥解密后得,M,和,h,(,M,)，而后将,M,送入杂凑变换器计算出,h,(,M,)，并经过比较完成对消息,M,认证，从而提供了保密和认证。,135/190,应用杂凑函数基本方式,图中(,b),部分，消息,M,不保密，只对消息杂凑值进行加解密变换，它只提供认证。,M,M,|,E,k,h,(,M,),M,h,(,M,),(,b,),k,MUX,DMX,h,判决,h,E,k,比较 输出,h,(,M,),E,k,h,(,M,),E,k,h,(,M,),D,h,(,M,),图中(c)部分，发端,A,采取双钥体制，用,A,秘密钥,k,sa,对杂凑值进行签字得,E,ksa,h,(,M,)，而后与,M,链接发出。收端则用,A,公钥对,E,ksa,h,(,M,)解密得到,h,(,M,)。再与收端自己由接收消息,M,计算得到,h,(,M,)进行比较实现认证。,本方案提供了认证和数字签字。称作,签字一杂凑方案,(Signature-hashing Scheme)。这一方案用对消息,M,杂凑值签字来代替对任意长消息,M,本身签字。大大提升了签字速度和有效性。,136/190,应用杂凑函数基本方式,图中(,d,)部分是在(,c,)基础上加了单钥加密保护，可提供认证、数字签字和保密。,M,M,|,E,ksa,k,(,M,),M,h,(,M,),(,c,),k,sa,MUX,DMX,h,判决输出,h,E,k,pa,比较,h,(,M,),E,ksa,h,(,M,),E,ksa,h,(,M,),D,h,(,M,),M,E,k,M,|,E,ksa,h,(,M,),M,h,(,M,),(,d,),k,s,MUX,E,D,DMX,h,判决,h,E,k,k,k,pa,比较 输出,h,(,M,),E,ksa,h,(,M,),E,ksa,h,(,M,),D,h,(,M,),137/190,应用杂凑函数基本方式,图中(,e,)部分是在,h,运算中增加了通信双方共享秘密值,S,，加大了对手攻击困难性。它仅提供认证。图中(,f,)部分是在(,e,)基础上加了单钥加密保护，可提供保密和认证。在上述方案中杂凑值都是由明文，而不是由密文计算，这对于实用较方便。,M,M,|,h,(,M,|,s,),M,h,(,M,|,s,),(,e,),MUX,DMX,s,h,判决输出,s,MUX,h,比较,h,(,M,),h,(,M,|,s,),M,E,k,M,|,h,(,M,|,s,),M,h,(,M,|,s,),(,f,),MUX,E,D,DMX,s,h,判决,s,MUX,h,k,k,比较 输出,h,(,M,),h,(,M,|,s,),h,(,M,|,s,),应用迭代杂凑函数基本方式,138/190,2、杂凑函数安全性,攻击方法：,1）穷举,2）生日攻击攻击,3）中途相遇攻击,139/190,认证码安全性分析穷举,穷举攻击法穷举明文,：,给定,h,=,h,(,H,0,M,)，其中,H,0,为初值，攻击者在全部可能,M,中寻求有利于攻击者,M,，使,h,(,H,0,M,)=,h,(,H,0,M,)，因为限定了目标,h,(,H,0,M,)来寻找,h
展开阅读全文
浙ICP备2021020529号-1 | 浙B2-20240490 
