计算机网络安全

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,计算机网络安全,(3),公开密钥密码编码学与数字签名,202.38.64.11/syang,二,六,年,三,月,2024/9/22,1,对称密码体制,(Symmetric System, One-key System, Private-key System),加密密钥和解密密钥相同，或者一个密钥可以从另一个导出，能加密就能解密，加密能力和解密能力是结合在一起的，开放性差。,非对称密码体制,(Asymmetric System, Two-key System, Public-key System),加密密钥和解密密钥不相同，从一个密钥导出另一个密钥是计算上不可行的，加密能力和解密能力是分开的，开放性好。,对称密码体制和非对称密码体制,2024/9/22,2,公开密钥密码系统的原理,对称密码体制的问题,加密能力与解密能力是捆绑在一起的,密钥更换、传递和交换需要可靠信道,如有,N,用户，则需要,C=N (N-1)/2,个密钥，,n=1000,时，,C(1000, 2)500000,管理困难,无法满足不相识的人之间通信的保密要求,不能实现数字签名,非对称密码体制的基本特点,加密能力与解密能力是分开的,密钥分发简单,需要保存的密钥量大大减少，,N,个用户只需要,N,个,可满足不相识的人之间保密通信,可以实现数字签名,2024/9/22,3,公开密钥加密过程,2024/9/22,4,公开密钥认证过程,2024/9/22,5,常规和公开密钥加密的重要特征,2024/9/22,6,公开密钥密码系统,:,保密,2024/9/22,7,公开密钥密码系统,:,认证,2024/9/22,8,公开密钥密码系统,:,保密和认证,2024/9/22,9,公开密钥密码系统的应用,加密,/,解密：发送方用接收方的公开密钥加密报文,数字签名：发送方用自己的私有密钥“签署”报文,密钥交换：两方合作以交换会话密钥,2024/9/22,10,对公开密钥密码编码系统的要求,容易计算公开密钥,k,e,和私有密钥,k,d,不难计算,C=E(k,e, m),和,m=D(k,d, c),不知道,k,d,，即使知道,k,e, E, D,及,c,，计算,m,也不可行,即使知道,k,e, E, D,及,c,，计算,k,d,也不可行,D(k,d, E(k,e, m)=m,，且,E(k,e, D(k,d, c)=c,加密变换和解密变换可以互换顺序，即,D(E(m)=E(D(m),1976,年，,Whitfield Diffie,和,Martin Hellman,提出这样的设想：每个用户,A,有一加密密钥,k,a,，不同于解密密钥,k,a,，可将加密密钥,k,a,公开，,k,a,保密，要求,k,a,的公开不影响,k,a,的安全。若,B,要向,A,秘密发送明文,m,，可查,A,的公开密钥,k,a,，加密得密文,C,E,ka,(m),A,收到,C,后用只有,A,才拥有的解密密钥,k,a,对,C,进行解密得,m,D,ka,(C).,实用方案的发展依赖于单向陷井函数,2024/9/22,11,Diffie and Hellman,WHITFIELD DIFFIE,MARTIN HELLMAN,2024/9/22,12,公开密钥密码分析,强行攻击：采用长密钥，并考虑折衷,密钥必须足够长以使强行攻击不切实际，但又要足够小以便加密解密可以实用,根据公开密钥计算私有密钥,尚未从数学上证明这种攻击是不可能的,可能报文攻击,比如仅加密传送,56,位的密钥，用公开密钥加密所有可能的,56,位密钥，通过匹配所传输的密文来得到相应的密钥。防止方法是增加随机信息,2024/9/22,13,RSA,算法,概述,1977,年，,Rivest,、,Shamir,、,Adleman,提出的非对称密码体制，是基于大合数的质因子分解问题的困难性。目前人类已能分解十进制,150,位的特殊类型的大合数第,9,个费马数，,1994,年,4,月一个小组通过,Internet,合作，,8,个月时间成功分解,129,位的数，大约,428,比特，最新的记录是,1996,年分解,130,位合数。,RSA,专利于,2000,年,9,月,20,日到期。,2024/9/22,14,R-S-A,(Left to Right: Ron Rivest, Adi Shamir, Len Adleman),2024/9/22,15,算法流程,随机选择两个秘密大质数,p,和,q,；,计算公开模数,n=p*q,；,计算秘密的欧拉指数函数,(n)=(p-1)(q-1),选择一个与,(n),互素的数,K,，作为,e,或,d,；,用,Euclid,算法计算模,(n),的,K,的乘法逆元素，即依,ed mod,(n)=1,求,d,或,e,；,加密：,C = M,e,mod n,解密：,M= C,d,mod n = (M,e,mod n),d,mod n = M,这里，,(n),为,Euler Totient Function,欧拉商数，即模,n,的完全剩余集合,(0, 1, 2, ., n-1),中与,n,互素的数的个数。,RSA密码体制基本原理,2024/9/22,16,密钥的产生,2024/9/22,17,RSA,的加密和解密,2024/9/22,18,RSA,算法满足公开密钥加密的要求，必须符合下列条件,有可能找到,e, d, n,的值，使得对所有,Mn,有,M,ed,mod n = M,对于所有,Mn,的值，要计算,M,e,和,C,d,是相对容易的,在给定,e,和,n,时，计算出,d,是不可行的,几个关系,(n) =,(pq) =,(p),(q) = (p-1)(q-1), p, q are prime,ed mod,(n)=1, ed = k,(n) + 1,即,ed,1 mod,(n), d,e,-1,mod,(n),2024/9/22,19,定理 给定,ed mod,(n) = 1,，,m 0, n-1,，,gcd(m, n) = 1,则：,(m,e,mod n ),d,mod n = m,ed,mod n = m,证明：, ed mod,(n) = 1, ed = k,(n)+1,，对某些整数,k, m,ed,mod n = m,k(n)+1,mod n,= m(m,k(n),mod n) mod n,m,k(n),mod n = (m,(n),mod n),k,mod n = 1,k,mod n = 1 (,根据费马定理，,m,(n),mod n = 1),m,ed,mod n = (m* 1) mod n = m,2024/9/22,20,RSA,方案概述,Prime p, q,私有，选择,n = pq,公开，计算出,e, gcd(,(n), e) = 1; 1 e ,(n),公开，选择,d,e,-1,mod,(n),私有，计算出,RSA,实现方面的考虑,加密与解密,模运算特性之一,(a mod n) x (b mod n) mod n = (a x b) mod n,指数运算的效率问题,2024/9/22,21,计算,a,b,mod n,的算法和快速取模指数算法,2024/9/22,22,密钥的产生和检验素数,确定两个素数,p,和,q,，选择,e,或,d,并计算另外一个,检验素数,随机选择一个奇数，如使用伪随机数产生器,随机选一个整数,a n,完成随机数素性检验，如果,n,没有通过检验，则另选,n,如果,n,通过了足够多次的检验，则接受,n,，否则另选,RSA,算法举例,例：,p,5,，,q = 7,，,n = 35,，,(n)=24,选,d = 11,，则,e = inv(11, 24) = 11,，,m = 2,C = m,e,mod n = 2,11,mod 35 = 18,M = C,d,mod n = 18,11,mod 35 = 2,2024/9/22,23,例：,p = 53,，,q = 61,，,n = pq = 3233,，,(n),52x60 = 3120,令,d = 791,，则,e = 71,令,m = RE NA IS SA NC E,即,m = 1704 1300 0818 1800 1302 0426,1704,71,mod 3233 = 3106,，,，,C = 3106 0100 0931 2691 1984 2927,三种可能的对,RSA,的攻击方法,强行攻击：尝试所有可能的密钥,数学攻击：对两个素数乘积的因子分解,(FAC,问题,),定时攻击：依赖于解密算法的运行时间,2024/9/22,24,因子分解问题,RSA,的安全性问题依赖于大合数的素因子分解，即,factorization problem (FAC),，将,n,分解为两个素数因子，以便计算,(n),= (p-1)(q-1),，然后确定,d=e,-1,mod,(n),。,FAC,的计算复杂性为,T=exp(ln(n)ln(ln(n),1/2,),，同,DLP,问题。为避免选择容易分解的,n,，应该对素数,P,和,q,的选择施加限制。,2024/9/22,25,Discrete Logarithm Problem (DLP),离散对数问题,Discrete Logarithm Problem (DLP),如果,a,是素数,p,的一个原根,(,本原元素,),，则,a mod p, a,2,mod p, ., a,p-1,mod p,，生成模,p,的完全剩余集,1, 2, ., p-1,对于所有素数，其原根必定存在，即,对于一个整数,b,和素数,p,的一个原根，可以找到唯一的指数,i,，使得,b = a,i,mod p,其中,0 = i = p-1,指数,i,称为,b,的以,a,为基数的模,p,的离散对数或者指数。,给定整数,x,，求,y = a,x,mod p,容易；若给定,p, a,及,y,，求,x,，则为,DLP,问题，最快方法需要,L(p)=exp(lnpln(lnp),次运算。,2024/9/22,26,例：,p=11, a=2, =2,0,2,1,2,2,2,10,=1,2,4,8,5,10,9,7,3,6,1,即：,2,0,=1 mod 112,6,=9 mod 11,2,1,=2 mod 112,7,=7 mod 11,2,2,=4 mod 112,8,=3 mod 11,2,3,=8 mod 112,9,=6 mod 11,2,4,=5 mod 112,10,=1 mod 11,2,5,=10 mod 11,给定整数,x,，求,y = a,x,mod p,最多需要,log,2,x+w(x)-1,次乘法，,w(x),为,x,中所有,1,的个数。如,x,=15,，即,x,=(1111),2,，,w(x)=4,，则,a,15,=(a,2,)a),2,a),2,a mod p,，只需要,3+4-1=6,次乘法。但是若给定,p, a,及,y,，求,x,，则为,DLP,问题。最快方法需要,L(p)=exp(lnpln(lnp),次运算。,当,p=512,位时，,L(p),约为,2,256,10,77,，计算上不可行。因为,2,100,10,30,，计算要,10,16,年。,2024/9/22,27,A public-key distribution scheme,cannot be used to exchange an arbitrary message,rather it can establish a common key,known only to the two participants,Value of key depends on the participants (and their private and public key information),Based on exponentiation in a finite (Galois) field (modulo a prime or a polynomial) - easy,Security relies on the difficulty of computing discrete logarithms (similar to factoring) hard,Diffie-Hellman Key Exchange,2024/9/22,28,Diffie-Hellman Setup,All users agree on global parameters:,large prime integer or polynomial q,a primitive root mod q,Each user (e.g. A) generates their key,chooses a secret key (number): x,A, q,compute their,public key,: y,A,=,x,A,mod q,Each user makes public that key y,A,2024/9/22,29,Diffie-Hellman Key Exchange,Shared session key for users A & B is K,AB,:,K,AB,=,x,A.,x,B,mod q,= y,A,x,B,mod q (which,B,can compute),= y,B,x,A,mod q (which,A,can compute),K,AB,is used as session key in private-key encryption scheme between Alice and Bob,If Alice and Bob subsequently communicate, they will have the,same,key as before, unless they choose new public-keys,Attacker needs an x, must solve discrete log,2024/9/22,30,2024/9/22,31,Diffie-Hellman Example,Users Alice & Bob who wish to s:,Agree on prime q=353 and,=3,Select random secret keys:,A chooses x,A,=97, B chooses x,B,=233,Compute public keys:,y,A,=,3,97,mod 353 = 40(Alice),y,B,=,3,233,mod 353 = 248(Bob),Compute shared session key as:,K,AB,= y,B,x,A,mod 353 =,248,97,= 160(Alice),K,AB,= y,A,x,B,mod 353 =,40,233,= 160(Bob),2024/9/22,32,设用户,A,和,B,，共享,和,P,，,是本原元素，,P,是大素数。,A,、,B,各有一私有密钥，,x,A,和,x,B,，公布他们的公开密钥：,Y,A,= ,xA,mod P,，,Y,B,= ,xB,mod P,。,双方共享的会话密钥为,A,：,K,AB,= (Y,B,),xA,mod P = ,xAxB,mod P,B,：,K,BA,= (Y,A,),xB,mod P = ,xBxA,mod P,例：,P = 11,，, = 7,，,x,A,= 2,，,x,B,= 3,。,Y,A,= ,xA,mod P = 7,2,mod 11 = 5,Y,B,= ,xB,mod P = 7,3,mod 11 = 2,K,AB,= K,BA,= ,xAxB,mod P = 7,6,mod 11 = 4,用,Diffie-Hellman,的方法实现密钥共享,2024/9/22,33,离散对数密码体制的安全性基于,DLP,问题，在已知,C,和,P,的情况下，由,d,求,M,很容易，由,M,求,d,很困难，,d = log,C,M in GF(P),，最快的算法需要,L(P)=exp(ln(P)lnln(P),1/2,),次运算。当,P,是,200,位时，,L = 2.7x10,11,，如果,1s,做一次，需要,23,天；如果,P = 664,位，则,L = 1.2x10,23,，约,10,12,天或,2.739x10,9,年，约,2.7,亿年。只要,P,足够大，可以达到足够安全。,离散对数密码体制,DLP,问题,2024/9/22,34,ElGamal Cryptosystem,假定,A,和,B,互相通信，共享大素数,P,，本原元素,，,0,m,P-1,，,加密：,A,选择,k0, P-1,，,k,的作用其实即为,x,A,。,A,访问公共区域找到,B,的公开密钥,Y,B,= ,xB,mod P,。计算：,K = (Y,B,),k,mod P,，即,K = ,xBk,mod P,c,1,= ,k,mod P,c,2,= mK mod P,密文即为,(c,1, c,2,),解密：,B,首先恢复,K,：,K = c,1,xB,mod P = ,kxB,mod P,然后恢复,m,：,m = c,2,/K mod P = c,2,K,-1,mod P,基于,DLP,的概率密码系统,2024/9/22,35,这里特别注意，,k,不能重复使用，如果,(1) c,1,1,=,k,mod Pc,2,1,= m,1,K mod P,(2) c,1,2,= ,k,mod Pc,2,2,= m,2,K mod P,得：,m,1,/m,2,= c,2,1,/c,2,2,mod P.,如果,m,1,已知，,m,2,即可算出。,ElGamal,密码体制是概率密码体制，同样的明文每次加密得到不同的密文。,ElGamal,密码体制加密效率是,50,，因为密文大小是明文的两倍。,ElGamal,密码体制的破译难度同,Diffie-Hellman,的方法，即基于,DLP,，离散对数问题，最快的算法需要,L=exp(ln(P)lnln(P),1/2,),次运算。,2024/9/22,36,例：,P = 17,，, = 3,，,x,A,= 2,，,x,B,= 5,，,m = 11,，,m,从,A,发送到,B,，,A,选择,k = 7.,求：密文,(c,1, c,2,),并解密,加密：,Y,A,= ,xA,mod P = 3,2,mod 17 = 9,Y,B,= ,xB,mod P = 3,5,mod 17 = 5,K = (Y,B,),k,mod P = 5,7,mod 17 = 10,c,1,= ,k,mod P = 3,7,mod 17 = 11,c,2,= mK mod P = 10x11 mod 17 = 8,所以，密文,C = (c,1, c,2,) = (11, 8),解密：,K = c,1,xB,mod P = 11,5,mod 17 = 10,c,2,= mK mod P = 10m mod 17 = 8,m = c,2,/K mod P = c,2,K,-1,mod P,K K,-1,mod P = 1,，即,10 K,-1,mod 17 = 1,，得,K,-1,= 12,所以，明文,m = c,2,K,-1,mod P = 8x12 mod 17 = 11,2024/9/22,37,Modular Arithmetic,给定任意正整数,n,和,a,，如果用,a,除以,n,，得到的商,q,和余数,r,满足如下关系,:,a=qn + r 0r,n;,q=,a/n,x,表示小于等于,x,的最大整数,Ex: 11=1x7 + 4, r=4; -11=(-2)x7 + 3, r=3,同余,(,congruence),给定整数,a, b,及,n0,当且仅当,a-b=kn,时，,a,与,b,在模,n,时同余，记为,ab mod n,或,a,n,b,Ex: 17,5,7 17-7=2*5; 53,7,11 53-11=6*7,a,n,b,当且仅当,a mod n = b mod n,如果,n|(a-b),则,ab mod n,证明,:,如果,n|(a-b),则有,(a-b)=kn, k,为某些整数。所以,a=b+kn,故,a mod n = (b + kn),除以,n,的余数,= b,除以,n,的余数,= b mod n,2024/9/22,38,2024/9/22,39,模运算的基本定理,(a,1,op a,2,) mod n =(a,1,mod n ) op (a,2,mod n) mod n,反身性：,a=a mod n,对称性：若,a=b mod n,，则,b=a mod n,传递性,:,若,a=b mod n,且,b=c mod n,，则,a=c mod n,如果,a=b mod n,且,c=d mod n,，则,a+c=(b+d) mod n,a-c=(b-d) mod n,ac=(bd) mod n, (a+b) mod n = (a mod n + b mod n) mod n,(a-b) mod n = (a mod n - b mod n) mod n,(ab) mod n = (a mod n b mod n) mod n,如果,ac=bd mod n,且,c=d mod n, gcd (c, n)=1,则,a=b mod n,证明：（略）,例：,3*2=1*2 mod 4,且,2=2 mod 4,但,31 mod 4,，, gcd(2, 4)1,2024/9/22,40,加法逆元,(-w),对每一个,w,Z,n,，存在一个,z,，使得,w+z,0 mod n,，则,z,即为加法逆元,-w,乘法逆元,(w,-1,),对每一个,w,Z,p,，存在一个,z,，使得,w,z,1 mod p,，则,z,即为乘法逆元,w,-1,因为,w,与,p,互素，如果用,w,乘以,Z,p,中的所有数模,p,，得到的余数将以不同次序涵盖,Z,p,中的所有数，那么至少有一个余数的值为,1,。因此，在,Z,p,中的某个数与,w,相乘模,p,的余数为,1,这个数就是,w,的乘法逆元，,w,-1,某些但非全部整数存在一个乘法逆元就将使模数不再是素数。如果,gcd(a, n)=1,则能在,Z,n,中找到,b,，使得,a,b,1 mod n,，则,b,即为乘法逆元,a,-1,因为,a,与,n,互素。,2024/9/22,41,Arithmetic Modulo 7,2024/9/22,42,剩余系,(Residues),b,是,a mod n,的剩余，如果,a=b mod n,或,a,是,b mod n,的剩余，如果,b=a mod n,(1),模,n,的完全剩余系,Complete Set of Residues mod n,如果对每个整数,a,，在集合,r,1,r,2,r,n,中恰有一个余数,r,i,使得,a=r,i,mod n ,则称,r,1,r,2,r,n,为模,n,的完全剩余系，,0,1,n-1,形成模,n,的完全剩余系集。,与同余不同之处：,a,n,b,当且仅当,a mod n=b mod n,a,n,r,，即,a=r mod n,不是说,a mod n = r,比如,20,3,14,，得,20=14 mod 3, r=2,，但,20 mod 3 14,，而是,20 mod 3=14 mod 3,(2),模,n,的缩剩余系,(Reduced set of Residues mod n),完全剩余系的一个子集，指的是集合中的元素都和,n,互素,例：,n=10,，模,n,的完全剩余系集是,0, 1, 2,9,，,缩剩余系是,1, 3, 7, 9,2024/9/22,43,One-way Function and One-way Trapdoor Function,1,One-way Function,定义,1.1,单向函数,一函数,f,若满足下列条件，则称,f,为单向函数：,(1),对于所有属于,f,之域的任一,x,，容易计算,y=f(x),(2),对于几乎所有属于,f,之域的任一,y,求得,x,使,y=f(x),则在计算上不可行。,2,One-way Trapdoor Function,定义,1.2,单向陷井门函数,一“可逆”函数,F,若满足下列二条件，则称,F,为单向陷井门函数,(1),对于所有属于,F,之域的任一,x,，容易计算,F,(,x,)=,y,；,(2),对于几乎所有属于,F,之域的任一,y,，除非获得暗门信息,(trapdoor),，否则求出,x,，使得,x,=,F,-1,(,y,),在计算上不可行，,F,-1,为,F,之逆函数；如有额外信息,(,暗门,),，则容易求出,x,=,F,-1,(,y,),，如旅馆太平门。,2024/9/22,44,3,单向函数之例子,（,1,）,Discrete Logarithm Problem (DLP),离散对数问题,令质数,p,满足,p-1,含有另一大质数,q (q,整除,p-1),及一整数,g, 1g p-1,。,若给定整数,x,，求,y = g,x,mod p,最多需要,log,2,x+w(x)-1,次乘法，,w(x),为,x,中所有,1,的个数。如,x,=15,，即,x,=(1111),2,，,w(x)=4,，则,g,15,=(g,2,)g),2,g),2,g mod p,，只需要,3+4-1=6,次乘法。,但是若给定,p, g,及,y,，求,x,，则为,DLP,问题。最快方法需要,L(p)=exp(lnpln(lnp),次运算。,当,p=512,位时，,L(p),约为,2,256,10,77,，计算上不可行。因为,2,100,10,30,，计算要,10,16,年。,2024/9/22,45,（,2,）,Factorization Problem,因数分解问题,给定大素数,p,和,q，,求,n = p.q ,只要一次乘法。,给定,n,，求,p,和,q,，即为因数分解问题，,FAC,，最快方法需要,T(n) = exp c(ln n ln (ln n),次运算，其中,c,为大于,1,的正整数。若,pn,，解离散对数比因数分解难。,（,3,）背包问题,Knapsack Problem,给定有限个自然数序列集合,B=(b,1,b,2,b,n,),及二进制序列,x=(x,1,x,2,x,n,), x,i,(0,1),求,S,x,i,b,i,最多只需,n-1,次加法；但若给定,B,和,S,，求,x,则非常困难。,穷举时有,2,n,种可能，当,n,很大时为计算上不可行。,Garey,和,Johnson,证明，背包问题是,NP,问题（,Non-Polynomial,）。,单向函数之例子,(,续,),2024/9/22,46,4,单向函数的交换性,(commutative property),单向函数本身对近代密码学领域用处不大，但若具有交换性，则作用大。,定义,1.3,交换性,令,Z,为一集合，,F,为将,Z,映射到,Z,本身的函数集合。令,zZ,，,Fx(z),表示此函数集合之第,x,函数，若,Fx(Fy(z)=Fy(Fx(z),，则称此函数集合具有交换性。例：,D(E(m)=E(D(m),。,2024/9/22,47,ax mod n = 1, x=a,-1,=?,若,T,为,g,之序，对于所有的,Ox T,，,Ex(g,-1,)=E,T-X,(g), g,-1,即为,g,的乘法逆元素或乘法反元素。,给定,a0, n-1, gcd(a, n)=1,，若能找到唯一整数,x0,n-1,，满足：,ax mod n=1,则称,a,和,x,互逆。,如,n=10, a=3, x=7, ax mod n=1 =3x7 mod 10,n=17, a=5, x=7, ax mod n=1 =5x7 mod 17,引理,1.,如果,gcd(a, n)=1,则对于每个,i,j, 0ijn,ai mod naj mod n,证明：（略）可以用反证法证明,此性质意味着每一个,ai mod n (i=0,n-1),都是不同的模,n,剩余，而, ai mod n ,i=0,1,n-1,是完全剩余集,0,1,n-1,的置换形式,计算乘法逆元素,Computing multiplicative inverses,2024/9/22,48,例如：,n=5, a=3, gcd(3, 5)=1, 0,1,n-1=0,1,2,3,4,3*0 mod 5=0,3*1 mod 5=3,3*2 mod 5=1,3*3 mod 5=4,3*4 mod 5=2,ai mod n,i=0,1,n-1,=0,3,1,4,2,引理,1,说明当,gcd(a, n)=1,时，,a,一定有一个唯一的逆元素。,定理,1.4,如果,gcd(a, n)=1,一定存在整数,x, 0x=0, then inv:= x, else inv:= x+n,end,g,i,= u,i,n + v,i,a,是循环变量，当,g,i,=0,时,g,i-1,=gcd(a, n),。如果,gcd(a, n)=1,则,g,i-1,=1,，并且,v,i-1,a 1 = u,i-1,n,。,因此，,v,i-1,a mod n =1, v,i-1,x,，就是,a,的逆元素。,扩展的,Euclid,算法求逆,2024/9/22,50,例：,3x mod 7=1,，事实上,x=5.,ig,i,u,i,v,i,y,0710,13012,211-23,0,因此得到,v,i-1,= -2,，,x = -2 + 7 = 5,。,例：,5x mod 49=1,，,x=10,ig,i,u,i,v,i,y,04910,15019,241-91,31-1104,0,因此得到,v,i-1,=10=x,。,2024/9/22,51,数字签名技术,Digital Signature,数字签名的含义,数字签名的简单定义：数字签名是使以数字形式存储的明文信息经过特定密码变换生成密文，作为相应明文的签名，使明文信息的接收者能够验证信息确实来自合法用户，以及确认信息发送者身份。,对数字签名的基本要求,签名接收者能容易地验证签字者对消息所做的数字签名；,任何人，包括签名接收者，都不能伪造签名者的签字；,发生争议时，可由第三方解决争议。,2024/9/22,52,Digital Signature Properties,Must depend on the message signed,Must use information unique to sender,to prevent both forgery and denial,Must be relatively easy to produce,Must be relatively easy to recognize & verify,Be computationally infeasible to forge,with new message for existing digital signature,with fraudulent digital signature for given message,Be practical save digital signature in storage,2024/9/22,53,两类数字签名,直接数字签名,直接数字签名仅涉及通信方,(,信源、信宿,),，假定信宿知道信源的公开密钥，数字签名通过信源对整个报文用私有密钥加密，或对报文的摘要加密来实现。弱点在于方案的有效性依赖于信源私有密钥的安全性。,需仲裁的数字签名,直接数字签名的问题可以通过仲裁解决，签名方的签名报文首先送给仲裁者，仲裁者对报文和签名进行测试以检验出处和内容，然后注上日期和仲裁说明后发给接收方。,2024/9/22,54,Direct Digital Signatures,Involve only sender & receiver,Assumed receiver has senders public-key,Digital signature made by sender signing entire message or hash with private-key,Can encrypt using receivers public-key,Important that sign first then encrypt message & signature,Security depends on senders private-key,2024/9/22,55,Arbitrated Digital Signatures,Involves use of arbiter A,validates any signed message,then dated and sent to recipient,Requires suitable level of trust in arbiter,Can be implemented with either private or public-key algorithms,Arbiter may or may not see message,2024/9/22,56,需要仲裁的数字签名技术,2024/9/22,57,数字签名与消息认证的区别,消息认证是使消息接收方验证消息发送者发送的内容有无被修改过，对防止第三者破坏足够，但收发双方有利害冲突时就无法解决纷争，需要更严格的手段，即数字签名。,数字签名的基本形式,有两种数字签名的方法,对消息整体的签字，将被签消息整体经过密码变换得到签字；,对消息摘要的签字，附在被签消息之后，或嵌在某一特定位置上作一段签字图样。,两类数字签名,确定性数字签名，明文与签名一一对应；,概率性数字签名，一个明文可以有多个合法签名，每次都不一样。,2024/9/22,58,RSA,方法的数字签名,给定,n = pq,，,p,和,q,是大素数，,ed mod(n) = 1,，公开密钥为,(n,，,e),，秘密密钥为,(p,，,q,，,d),加密：,m 0, n-1,，,gcd(m, n) = 1,则,c = m,e,mod n,解密：,m = c,d,mod n = (m,e,mod n ),d,mod n,= m,ed,mod n = m,签名：,s = m,d,mod n,验证：,m = s,e,mod n = (m,d,mod n ),e,mod n,= m,ed,mod n = m,基于非对称密码体制的数字签名,2024/9/22,59,例：,n = 55 = 11x5,，,(n) = 40,，选,d = 11,，则,e = 11,，,m = 3,，,s = 3,11,mod 55 =47,验证：,m = s,11,mod 55 = 47,11,mod 55 = 3,n = 65,，,(n) = 48,，选,d = 5,，则,e = 29,，,m = 3,，,s = 3,5,mod 65 = 48,，验证：,m = 48,29,mod 65 = 3,用数字签名和加密同时实现报文的秘密和认证的传送,设有用户,A,和,B,，,A: n,A, e,A, d,A, E,A, D,A, B: n,B, e,B, d,B, E,B, D,B,从,AB,：,Secrecy: c = E,B,(m) = m,e,B,mod n,B,m = D,B,(c) = c,d,B,mod n,B,= m,e,B,d,B,mod n,B,Authenticity: c = D,A,(m) = m,d,A,mod n,A,m = E,A,(c) = c,e,A,mod n,A,= m,e,A,d,A,mod n,A,= m,2024/9/22,60,Both secrecy and authenticity:,c = E,B,(D,A,(m) = (m,d,A,mod n,A,),e,B,mod n,B,or: c = D,A,(E,B,(m) = (m,e,B,mod n,B,),d,A,mod n,A,m = E,A,(D,B,(c) = E,A,(D,B,(E,B,(D,A,(m),= (m,d,A,mod n,A,),e,B,mod n,B,),d,B,mod n,B,),e,A,mod n,A,= m,or: m = D,B,(E,A,(c) = D,B,(E,A,(D,A,(E,B,(m),= (m,e,B,mod n,B,),d,A,mod n,A,),e,A,mod n,A,),d,B,mod nB = m,注意：,1. n,A,n,B,，则,A,：,c = E,B,(D,A,(m),，,B,：,m = E,A,(D,B,(c) = E,A,(D,B,(E,B,(D,A,(m),2. n,B, n,A,，则,A,：,c = D,A,(E,B,(m),，,B,：,m = D,B,(E,A,(c) = D,B,(E,A,(D,A,(E,B,(m),例：,(n,A, e,A,)=(15, 3),，,(n,B, e,B,)=(35, 5),，,A,发送,m = 11,给,B,，要求既保密又认证地传送。,2024/9/22,61,假定,A,和,B,互相通信，共享大素数,P,，本原元素,，,0= m = P-1,，,gcd(,，,P) = 1,。,A,和,B,各有自己的秘密,x,A,和,x,B,。,加密：,A,选择,k0, P-1,，,k,的作用即为,x,A,。,A,访问公共区域找到,B,的公开密钥,Y,B,=,x,B,mod P,。计算：,K = (Y,B,),k,mod P,，即,K =,x,B,k,mod P,c,1,=,k,mod P,c,2,= mK mod P,密文即为,(c,1, c,2,),ElGamal,的数字签名方法,2024/9/22,62,解密,B,首先恢复,K,：,K = c,1,x,B,mod P =,kx,B,mod P,然后恢复,m,：,m = c,2,/K mod P = c,2,K,-1,mod P,这里特别注意，,k,不能重复使用，如果重复使用，则,(1) c,1,1,=,k,mod Pc,2,1,= m,1,K mod P,(2) c,1,2,=,k,mod P c,2,2,= m,2,K mod P,2024/9/22,63,签名,若,A,为,B,签署,m,，,0= m = P-1,，,A,随机选择,k0, P-1,，,gcd(k,，,P-1) = 1,计算,r =,k,mod P,计算,m,= Y,A,r,r,s,mod P, Y,A,=,x,A,mod P,即,m,=,x,A,r,k s,mod P,则,m = (x,A,r + ks) mod P-1,根据此式求,s,，则对于,m,的数字签名即为,(r, s),，,0= r, sP-1.,验证：给定,m, r,和,s,，容易计算,m,mod P = Y,A,r,r,s,mod P,看其是否一致。,K,不能重复使用。,2024/9/22,64,例：,P = 17,= 3, x,A,= 2, x,B,= 5, m = 11, k = 5,求签名及验证。,签名：,r =,k,mod P = 3,5,mod 17 = 5,11 = (2x5 + 5s) mod 16 = (10 + 5s) mod 16,5s mod 16 = 1, s = 13.,所以，签名为,(5, 13),。,验证,:,m,mod P = 3,11,mod 17 = 10,2,x10x9 mod 17 = 7,Y,A,r,r,s,mod P = (3,2,),5,x 5,13,mod 17 = 7,2024/9/22,65,Digital Signature,Standard,(DSS),US Govt approved signature scheme FIPS 186,Uses the SHA hash algorithm,Designed by NIST & NSA in early 90s,DSS is the standard, DSA is the algorithm,A variant on ElGamal and Schnorr schemes,Creates a 320 bit signature, but with 512-1024 bit security,Security depends on difficulty of computing discrete logarithms,2024/9/22,66,2024/9/22,67,DSA Key Generation,Have shared global public key values (p,q,g):,a large prime,p = 2,L,where L= 512 to 1024 bits and is a multiple of 64,choose q, a 160 bit prime factor of p-1,choose,g = h,(p-1)/q,where,h 1,Users choose private & compute public key:,choose,xq,compute,y = g,x,(mod p),2024/9/22,68,DSA Signature Creation,To,sign,a message,M, the sender:,generates a random signature key,k, kq,k,must be random, be destroyed after use, and never be reused,Then computes signature pair:,r = (g,k,(mod p)(mod q),s = (k,-1,.SHA(M)+ x.r)(mod q),Sends signature,(r,s),with message,M,2024/9/22,69,DSA Signature Verification,Having received M &,signature,(r,s),To,verify,a signature, recipient computes:,w = s,-1,(mod q),u1= (SHA(M).w)(mod q),u2= (r.w)(mod q),v = (g,u1,.y,u2,(mod p) (mod q),If,v=r,then signature is verified,See book web site for details of proof why,2024/9/22,70,2024/9/22,71,习 题,William Stallings,密码编码学与网络安全第二版第六章, 6.2, 6.4, 6.14,补充题：,1.,假定,A,和,B,要用,RSA,方法进行一次保密又认证的通信。,A,的公钥是,(n,A, e,A,)=(33, 7), B,的公钥是,(n,B, e,B,)=(15, 3),。,(a) A,和,B,的秘密密钥,d,A,和,d,B,各是什么,?,(b)A,送消息,m=2,给,B,，保密又认证，密文,C,是什么,?,(c)B,如何从,C,解得,m,？,2.,在,Elgamals,系统中,=7, p=13, x,a,=5, x,b,=3.,(a).,假定,A,加密传送,m=3,给,B,，随机选择,k=8,，密文是什么,?,(b). B,如何解密,?,(c).,如果,A,要签名,m=7,，随机选择,k=5,，签名是什么,? B,如何验证？,3. Alice,和,Bob,用,Diffie-Hellman,密钥交换方法建立会话密钥。,=5, p=17, x,A,和,x,B,分别为,7,和,3,，求他们之间形成的会话密钥。,2024/9/22,72,