现代密码学复习全解

你们好现代密码学（复习）目录概述流密码分组密码公钥密码杂凑算法数字签名密码协议第一章引言复习要点密码学的基本概念密码学的分类密码体制攻击的四种类型仿射密码体制的加密、解密原理，计算至少一个实例密码算法基本概念明文——要处理的数据密文——处理后的数据密钥——秘密参数加密函数解密函数密码算法密码算法如何构造？需求1：可逆——算法的使用者可以求得逆函数需求2：不可逆——敌手无法将密文恢复成明文秘密参数——密钥密码算法实际上是一个带有秘密参数的函数。知道秘密参数，求逆非常容易不知道秘密参数，求逆在计算上是不可行的密码学概述密码学是研究密码系统或通信安全的一门科学，它包括两个分支：密码编码学和密码分析学。密码编码学的主要目的是寻求保证消息机密性或认证的方法，密码分析学主要研究加密消息的破译和消息的伪造。密码学的目标：机密性、数据完整性、认证和不可否认性。加密和解密的函数表达式为：EK1（M）=CDK2（C）=M函数必须具有的特性是，DK2（EK1（M））=M，如下图所示。加密解密明文密文原始明文加密密钥解密密钥对称算法早期的密钥算法是对称算法（SymmetricAlgorithm），就是加密密钥能够从解密密钥中推算出来，反之亦然。多数对称算法中，加密和解密由同一个密钥来控制，也叫“单钥算法”，如图所示。非对称算法用作加密的密钥不同于用作解密的密钥，而且解密密钥不能根据加密密钥计算出来，就是非对称算法（AsymmetricAlgorithm），也叫公钥算法（Public-keyAlgorithm）或双钥算法，如图所示。1.3.3密码攻击概述根据密码分析者可能取得的分析资料不同，可将密码分析（或攻击）分为：唯密文攻击、已知明文攻击、选择明文攻击和选择密文攻击。唯密文攻击是指密码分析者取得一个或多个用同一密钥加密的密文，当然分析者也知道加密算法。已知明文攻击是指除要破译的密文外，密码分析者还取得一些用同一密钥加密的密文/明文对。选择明文攻击是指密码分析者可取得他所选择的任何明文所对应的密文（不包括他要恢复的明文），这些密文对和要破译的密文是用同一密钥加密的。选择密文攻击是指密码分析者可取得他所选择的任何密文所对应的明文（要破译的密文除外），这些密文和明文和要破译的密文是用同一解密密钥解密的。Vigenère密码第二章流密码复习要点流密码的基本思想线性反馈移位寄存器序列的基本概念特征多项式序列的周期m序列的定义m序列的伪随机性m序列的破译

流密码的基本概念流密码是将明文划分成字符(如单个字母)，或其编码的基本单元(如0,1数字)，字符分别与密钥流作用进行加密，解密时以同步产生的同样的密钥流实现。流密码强度完全依赖于密钥序列的随机性(Randomness)和不可预测性(Unpredictability)。核心问题是密钥流生成器的设计。保持收发两端密钥流的精确同步是实现可靠解密的关键技术。流密码的框图kI

安全信道kI

线性反馈移位寄存器

f(x)为线性函数，输出序列满足下式

n级线性移位寄存器的输出序列{ai}满足递推关系an+k=c1an+k-1c2an+k-2…cnak(*)LFSR的特征多项式p(x)=1+c1x+…＋cn-1xn-1＋cnxn线性移位寄存器的一元多项式表示 n级LFSR输出序列的周期r不依赖于初始条件，而依赖于特征多项式p(x)。序列的周期达到最大2n-1，这种序列就是m序列。 显然对于特征多项式一样，而仅初始条件不同的两个输出序列，一个记为{a(1)i}，另一个记为{a(2)i}，其中一个必是另一个的移位，即存在一个常数k，使得a(1)i=a(2)k+i,i=1,2,…4、n级LFSR输出序列为m序列，当且仅当其反馈多项式是本原多项式若敌手得到一段长为2n的密钥序列由此可推出线性反馈移位寄存器连续的n+1个状态：做矩阵而若X可逆，则第三章分组密码复习要点分组密码的设计准则分组密码的分类分组密码的四种工作模式DES算法的主要原理及参数AES算法的主要原理及参数有限域上元素的乘法运算GF（256）域中的模多项式运算分组密码概述

明文序列x1,x2,…,xi,…

加密函数E:Vn×K

Vn

这种密码实质上是字长为m的数字序列的代换密码。

解密算法加密算法密钥k=(k0,k1,…,kt-1)密钥k=(k0,k1,…,kt-1)明文x=(x0,x1,…,xm-1)明文x=(x0,x1,…,xm-1)密文x=(y0,y1,…,ym-1)分组密码设计准则混淆：人们所设计的密码应使用使得密钥和明文以及密文之间的依赖关系相当复杂以至于这种依赖性对密码分析者来说是无法利用的。扩散：人们所设计的密码应使得密钥的每一位数字影响密文的许多位数字以防止对密钥进行逐段破译，而且明文的每一位数字也应影响密文的许多位数字以便隐藏明文数字统计特性。分组密码的主要总体结构类型分组密码算法一般采用迭代的方式来使用乘积密码，其主要的总体结构类型有两种：Feistel密码和SP网络。DES是Feistel密码的代表。AES是SP结构的代表。

乘积密码指顺序地执行两个或多个基本密码系统，使得最后结果的密码强度高于每个基本密码系统产生的结果. Feistel还提出了实现代换和置换的方法。其思想实际上是Shannon提出的利用乘积密码实现混淆和扩散思想的具体应用。Feistel密码结构图3.3Feistel网络示意图Feistel加密结构 输入是分组长为2w的明文和一个密钥K。将每组明文分成左右两半L0和R0，在进行完n轮迭代后，左右两半再合并到一起以产生密文分组。其第i轮迭代的输入为前一轮输出的函数：其中Ki是第i轮用的子密钥，由加密密钥K得到。一般地，各轮子密钥彼此不同而且与K也不同。图3.4Feistel加解密过程

主要工作模式

即使有了安全的分组密码算法，也需要采用适当的工作模式来隐蔽明文的统计特性、数据的格式等，以提高整体的安全性，降低删除、重放、插入和伪造成功的机会。电子码本(ECB)密码反馈链接(CBC)密码反馈(CFB)输出反馈(OFB)。

电码本ECB模式直接利用加密算法分别对分组数据组加密。在给定的密钥下同一明文组总产生同样的密文组。这会暴露明文数据的格式和统计特征。明文数据都有固定的格式，需要以协议的形式定义，重要的数据常常在同一位置上出现，使密码分析者可以对其进行统计分析、重传和代换攻击。

电码本ECB模式

xykDESyxkDES-1密码分组链接CBC模式每个明文组xi加密之前，先与反馈至输入端的前一组密文yi-1按位模2求和后，再送至加密算法加密各密文组yi不仅与当前明文组xi有关，而且通过反馈作用还与以前的明文组x1,x2,…,xi-1，有关加密：yi=DESK(xiyi-1)，y0=IV

解密：xi=DESK-1(yi)yi-1密码分组链接CBC模式

初始矢量IV(InitialVector)：第一组明文xi加密时尚无反馈密文，为此需要在寄存器中预先置入一个。收发双方必须选用同一IV。实际上，IV的完整性要比其保密性更为重要。在CBC模式下，最好是每发一个消息，都改变IV，比如将其值加一。密码分组链接CBC模式

CBC模式xiyikDESyix’kDES-1++64bit存储64bit存储yi-1CBC的优缺点优点：能隐蔽明文的数据模式，在某种程度上能防止数据纂改，诸如重放、嵌入和删除等。缺点：会出现传播错误，对同步差错敏感（增加或丢失一个或多个比特）。CBC的错误传播1.明文有一组中有错，会使以后的密文组都受影响，但经解密后的恢复结果，除原有误的一组外，其后各组明文都正确地恢复。2.若在传送过程中，某组密文组yi出错时，则该组恢复的明文x’i和下一组恢复数据x’i+1出错。再后面的组将不会受yi中错误比特的影响。k-比特密码反馈CFB模式若待加密消息必须按字符(如电传电报)或按比特处理时，可采用CFB模式。CFB实际上是将加密算法DES作为一个密钥流产生器，当k＝1时就退化为前面讨论的流密码了。CFB与CBC的区别是反馈的密文长度为k，且不是直接与明文相加，而是反馈至密钥产生器。k-比特密码反馈CFB模式

CFB模式++xixiyiyikkXi64bitXi64bitYi64bitYi64bitDES

DES-1

选最左边

k位

选最左边

k位kbitkbityi-Lyi-2yi-1k-比特密码反馈CFB模式CFB的优点它特别适于用户数据格式的需要。能隐蔽明文数据图样，也能检测出对手对于密文的篡改。CFB的缺点对信道错误较敏感，且会造成错误传播。CFB也需要一个初始矢量，并要和密钥同时进行更换。输出反馈OFB模式将分组密码算法作为一个密钥流产生器，其输出的k-bit密钥直接反馈至分组密码的输入端，同时这k-bit密钥和输入的k-bit明文段进行对应位模2相加。克服了CBC和CFB的错误传播所带来的问题。对于密文被篡改难以进行检测不具有自同步能力，要求系统要保持严格的同步输出反馈OFB模式

OFB模式+xiyik64bit64bitDES

选最左边

k位ki64bit寄存器kbitkbit+xiyik64bit64bit

DES-1

选最左边

k位kbit64bit寄存器kbitki

DES算法分组长度为64bits(8bytes)密文分组长度也是64bits。密钥长度为64bits，有8bits奇偶校验，有效密钥长度为56bits。算法主要包括：初始置换IP、16轮迭代的乘积变换、逆初始置换IP-1以及16个子密钥产生器。

DES算法框图

标准数据加密算法DES的S1-盒的输入和输出关系(y3,y2,y1,y0)=(0,0,1,0)AES提出1997年1月，美国NIST向全世界密码学界发出征集21世纪高级加密标准（AES——AdvancedEncryptionStandard）算法的公告，并成立了AES标准工作研究室，1997年4月15日的例会制定了对AES的评估标准。

算法说明分组和密钥长度可变，各自可独立指定为128、192、256比特。状态算法中间的结果也需要分组，称之为状态，状态可以用以字节为元素的矩阵阵列表示，该阵列有4行，列数Nb为分组长度除32种子密钥以字节为元素的矩阵阵列描述，阵列为4行，列数Nk为密钥长度除32字节代换非线性代换，独立地对状态的每个字节进行，并且代换表(S盒)可逆，记为ByteSub(State),分两步将字节作为GF(28)上的元素映射到自己的逆元将字节做如下的GF(2)上变换字节代换AES的S盒y0123456789abcdefx0637c777bf26b6fc53001672bfed7ab761ca82c97dfa5947f0add4a2af9ca472c02b7fd9326363ff7cc34a5e5f171d83115304c723c31896059a071280e2eb27b275409832c1a1b6e5aa0523bd6b329e32f84553d100ed20fcb15b6acbbe394a4c58cf6d0efaafb434d338545f9027f503c9fa8751a3408f929d38f5bcb6da2110fff3d28cd0c13ec5f974417c4a77e3d645d1973960814fdc222a908846eeb814de5e0bdbae0323a0a4906245cc2d3ac629195e479be7c8376d8dd54ea96c56f4ea657aae08cba78252e1ca6b4c6e8dd741f4bbd8b8ad703eB5664803f60e613557b986c11d9eee1f8981169d98e949b1e87e9ce5528dff8ca1890dbfe6426841992d0fB054bb16

定理3.1系数在GF(28)上的多项式a3x3+a2x2+a1x+a0是模x4+1可逆的，当且仅当矩阵在GF(28)上可逆。

证明：a3x3+a2x2+a1x+a0是模x4+1可逆的，当且仅当存在多项式h3x3+h2x2+h1x+h0(a3x3+a2x2+a1x+a0)(h3x3+h2x2+h1x+h0)=1mod(x4+1)

因此有(a3x3+a2x2+a1x+a0)(h2x3+h1x2+h0x+h3)=xmod(x4+1)(a3x3+a2x2+a1x+a0)(h1x3+h0x2+h3x+h2)=x2mod(x4+1)(a3x3+a2x2+a1x+a0)(h0x3+h3x2+h2x+h1)=x3mod(x4+1)将以上关系写成矩阵形式即得（证毕）SMS4概况SMS4分组密码算法是国家密码管理局于2006年1月6日公布的无线局域网产品使用的密码算法，是国内官方公布的第一个商用密码算法。SMS4是一个分组密码算法，分组长度和密钥长度均为128比特。加密算法与密钥扩展算法都采用32轮非线性迭代结构。非线性变换中所使用的S盒是一个具有很好密码学特性的、由8比特输入产生8比特输出的置换，在设计原理上，SMS4比AES的S盒设计多了一个仿射变换。SMS4有很高的灵活性，所采用的S盒可以灵活地被替换，以应对突发性的安全威胁。算法的32轮迭代采用串行处理，这与AES中每轮使用代换和混淆并行地处理整个分组有很大不同。它的解密算法与加密算法的结构相同，只是轮密钥的使用顺序相反，解密轮密钥是加密轮密钥的逆序。SMS4算法的术语说明在SMS4算法中，用表示比特的向量集，中的元素称为字节，中的元素称为字。SMS4算法中构造了一个与AES类似的S盒，该S盒是一个固定的8比特输入8比特输出的置换，记为SMS4中的采用了两个基本运算：，32比特异或；，32比特循环左移i位。SMS4算法的术语说明（续）SMS4算法的加密密钥长度为128比特，表示为，其中，为字。轮密钥为，，为字。轮密钥由加密密钥通过密钥扩展算法生成。为系统参数，为固定参数，用于密钥扩展算法。SMS4的轮函数设输入为，轮密钥为，则轮函数为：其中称为合成置换，是一个由非线性变换和线性变换复合而成的可逆变换，即

XiXi+1Xi+2Xi+3rkia0a1a2a3b0b1b2b3ssssB<<<2B<<<10B<<<18B<<<24CXi+4AτBSMS4的加密算法和解密算法设明文输入为，密文为，轮密钥为，。加密变换为：SMS4算法的解密变换和加密变换结构相同，不同的仅是轮密钥的使用顺序。加密时轮密钥的使用顺序为，解密时轮密钥的使用顺序为。SMS4的S盒构造由三个函数复合而成L1是仿射变换，I是逆变换第四章公钥密码复习要点公钥密码的基本思想RSA算法原理解密正确性证明由n和求p，qElGamal算法原理和解密正确性证明椭圆曲线上点的加法运算公钥密码的起源非对称密码（公钥密码）算法想法的提出1976年，Diffie、Hellman在《密码学的新方向》（NewDirectionsinCryptography）一文中提出来）非对称密码，也称为公钥密码算法。AsymmetricalcryptographyPublickeycryptography基于公钥的加密过程欧拉定理设m>1，如果gcd(a,n)=1,则:aϕ(n)

≡1modn.

eg:

求3801的后两位数字解：3801（mod100）的结果

ϕ(100)=100(1-1/2)(1-1/5)=40，有3801

≡(340)2031

≡3(mod100)RSA加密算法描述－密钥产生独立地选取两大素数p和q(各100～200位十进制数字)计算n=p×q，其欧拉函数值

(n)=(p－1)(q－1)

随机选一整数e，1

e<

(n)，gcd(

(n),e)=1在模

(n)下，计算e的有逆元d=e-1mod

(n)以n，e为公钥。秘密钥为d。RSA算法描述－加密和解密加密将明文分组，各组对应的十进制数小于nc=memodn解密

m=cdmodn解密正确性证明cdmodn≡medmodn≡m1modj(n)modn≡mkj(n)+1modnm与n互素，由欧拉定理

mj(n)≡1modn,mkj(n)≡1modn,mkj(n)+1≡mmodn解密正确性证明gcd(m,n)≠1,m是p的倍数或q的倍数，设m=cp，此时gcd(m,q)=1,由欧拉定理，mj(q)≡1modq，mkj(q)≡1modq，[mkj(q)]j(p)≡1modqmkj(n)≡1modq，存在一整数r，使mkj(n)≡1＋rq

两边同乘m=cp,mkj(n)+1≡m+rcpq=m+rcn,即mkj(n)+1≡mmodn例

使用RSA算法计算：如果p=11，q=17，选取e=7，求解密密钥d。若令明文为m=5，求密文c。验证加解密的正确性。解：p=11，q=17，那么n=pq=187

加密密钥e=7，与互素，那么，通过扩展的欧几里德算法，可以求得解密密钥公开e和n，将d作为私钥保密，舍弃p和q。当m=5，则加密为验证解密正确性

所以，使用RSA可以正确进行公开密钥加解密。

是否有不通过分解大整数的其他攻击途径？下面证明由n直接确定φ(n)等价于对n的分解。设n=p×q中，p>q，由φ(n)=(p-1)(q-1)，则有p+q=n-φ(n)+1以及由此可见，由p、q确定φ(n)和由φ(n)确定p、q是等价的。(1)ElGamal密码体制的原理密钥产生过程：首先选择一素数p以及两个小于p的随机数g和x，计算y≡gxmodp。公钥：(y,g,p)私钥：xElGamal密码体制ElGamal加密加密过程：设欲加密明文消息M，随机选一与p-1互素的整数k，0<=k<=p-1计算密文对:C={C1,C2}C1≡gkmodp,C2≡ykMmodp，发送到接收者k需要永久保密解密过程：计算明文:这是因为ElGamal

解密ECC实现Elgamal密码体制选取一条椭圆曲线，得到Ep(a,b)。将明文消息通过编码嵌入曲线上得到点pm取Ep(a,b)的生成元G，Ep(a,b)和G为公开参数用户选取nA为秘密钥，PA=nAG为公开钥。加密：选随机正整数k，密文为

Cm=(C1,C2)=(kG,Pm+kPA)解密：C2+nAC1=Pm+kPA-nAkG=Pm椭圆曲线密码体制的优点安全性高攻击有限域上的离散对数可用指数积分法，运算复杂度为。对ECC上离散对数攻击并不有效。攻击ECC上离散对数问题的方法只有大步小步法，复杂度为。pmax是ECC形成的交换群的阶的最大素因子，因此ECC上的密码体制比基于有限域上离散对数问题的公钥体制更安全第五章Hash函数复习要点杂凑函数的定义及性质杂凑函数设计的一般模式MD5的分组长度、填充、摘要长度、迭代轮数SHA1的分组长度、填充、摘要长度、迭代轮数杂凑函数应满足的条件函数的输入可以是任意长函数的输出是固定长已知x,求H(x)较为容易已知h，求H(x)＝h的在计算上不可行，即单向杂凑函数，对于任意x,找不同的y，使H(x)=H(y)在计算上不可行，如果满足这一性质，称为弱单向杂凑函数（抗弱碰撞）找出任意两个不同的x,y，是H(x)=H(y)在计算上不可行，满足这一性质，称为强单向杂凑函数（抗强碰撞）迭代型杂凑函数的一般结构fffY0Y1YL-1bbbnnnnnIV=CV0CV1CVL-1CVL明文M被分为L个分组Y0,Y1,…,YL-1b:明文分组长度n:输出hash长度CV：各级输出，最后一个输出值是hash值无碰撞压缩函数f是设计的关键MD5杂凑算法MD4是MD5杂凑算法的前身，由RonRivest于1990年10月作为RFC提出，1992年4月公布的MD4的改进（RFC1320，1321）称为MD5。6.3.1算法描述MD5算法采用图6.4描述的迭代型杂凑函数的一般结构，算法的框图如图6.5所示。算法的输入为任意长的消息（图中为K比特），分为512比特长的分组，输出为128比特的消息摘要。图6.5MD5的算法框图MD5的安全性安全杂凑算法

安全杂凑算法SHA(SecureHashAlgorithm)由美国NIST设计，于1993年作为联邦信息处理标准（FIPSPUB180）公布。SHA-0是SHA的早期版本，SHA-0被公布后，NIST很快就发现了它的缺陷，修改后的版本称为SHA-1，简称为SHA。SHA是基于MD4算法，其结构与MD4非常类似。算法描述算法的输入为小于264比特长的任意消息，分为512比特长的分组，输出为160比特长的消息摘要。算法的框图与图6.5一样，但杂凑值的长度和链接变量的长度为160比特。算法的处理过程有以下几步：①对消息填充与MD5的步骤①完全相同。②附加消息的长度与MD5的步骤②类似，不同之处在于以big-endian方式表示填充前消息的长度。即步骤①留出的64比特当作64比特长的无符号整数。③对MD缓冲区初始化算法使用160比特长的缓冲区存储中间结果和最终杂凑值，缓冲区可表示为5个32比特长的寄存器(A,B,C,D,E)，每个寄存器都以big-endian方式存储数据，其初始值分别为A=67452301，B=EFCDAB89，C=98BADCFB，D=10325476，E=C3D2E1F0。④以分组为单位对消息进行处理每一分组Yq都经一压缩函数处理，压缩函数由4轮处理过程（如图6.8所示）构成，每一轮又由20步迭代组成。4轮处理过程结构一样，但所用的基本逻辑函数不同，分别表示为f1,f2,f3,f4。每轮的输入为当前处理的消息分组Yq和缓冲区的当前值A,B,C,D,E，输出仍放在缓冲区以替代A,B,C,D,E的旧值，每轮处理过程还需加上一个加法常量Kt，其中0≤t≤79表示迭代的步数。80个常量中实际上只有4个不同取值，如表6.5所示，其中为x的整数部分。（见178页表6.5）SHA与MD5的比较抗穷搜索能力寻找指定hash值，SHA：O(2160)，MD5：O(2128)生日攻击：SHA：O(280)，MD5：O(264)抗密码分析攻击的强度SHA高于MD5速度SHA较MD5慢简捷与紧致性描述都比较简单，都不需要大的程序和代换表第六章数字签名复习要点数字签名和手写签名的区别与联系RSA数字签名体制的原理、弱点及改进ElGamal数字签名体制DSS数字签名体制基于求解离散对数困难问题的数字签名的各种变体数字签名传统签名的基本特点:能与被签的文件在物理上不可分割签名者不能否认自己的签名签名不能被伪造容易被验证数字签名是传统签名的数字化,基本要求:能与所签文件“绑定”签名者不能否认自己的签名签名不能被伪造容易被自动验证数字签名应具有的性质必须能够验证作者及其签名的日期时间；必须能够认证签名时刻的内容；签名必须能够由第三方验证，以解决争议；因此，数字签名功能包含了认证的功能数字签名的设计要求签名必须是依赖于被签名信息的一个比特串；签名必须使用某些对发送者是唯一的信息，以防止双方的伪造与否认；必须相对容易生成该数字签名；必须相对容易识别和验证该数字签名；伪造该数字签名在计算上不可行，既包括对一个已有的数字签名构造新的消息，也包括对一个给定消息伪造一个数字签名；在存储器中保存一个数字签名副本是现实可行的。由加密算法产生数字签名RSA签名体制体制参数大素数p,q，n=p×q,y(n)=(p-1)(q-1)。选整数1<e<y(n),且gcd(e,y(n))=1;计算d满足de≡1mody(n).{e,n}为公开密钥，{d,n}为秘密密钥。签名过程S=Mdmodn，签名S与消息M一起发送给验证者验证过程是否有M=Semodn，若等式成立，则签名为真，反之为假RSA数字签名方案的弱点任何人能通过对某一S’计算M’=S’emodn，伪造一个随机消息M’的签名S’。如果M1和M2的签名分别为S1和S2，则任何拥有M1、M2、S1和S2的敌手都可以伪造M1M2的签名。签名者每次仅能签log2n比特长的消息。解决方法：引入hash函数。ElGamal数字签名体制

ElGamal数字签名体制是T.ElGamal在1985年发表关于ElGamal公开密钥密码时给出的两个体制之一，该体制中重要的有NIST于1991年公布的数字签名标准中所使用的数字签名算法（DSA），专门用于数字签名，它的安全性主要基于求解离散对数问题的困难性。ElGamal数字签名1．参数与密钥生成①选取大素数p,是一个本原元。p和g公开。②随机选取整数x,1≤x≤p

2，计算。③公钥为y，私钥为x。2．签名对于消息m，首先随机选取一个整数k,1≤k≤p

2，然后计算：

,

则m的签名为(r,s)，其中h为Hash函数。3．验证对于消息签名对(m,(r,s))，如果：

则(r,s)是m的有效签名。因为s=(h(m)

xr)k

1mod(p

1)我们有sk+xr=h(m)mod(p

1)所以签名合理性证明2.ElGamal签名的安全性分析

ElGamal数字签名可能存在以下三种攻击方式。第一种攻击方法：由于私钥是保密的，所以，攻击者要得到这个密钥，必须求解离散对数问题，这是一个困难问题。但是，秘密随机数一旦暴露，则解：，即可求得密钥，方案被攻破。第二种攻击方法：关于秘密随机数K的另一个问题是：不可用同一个K作两次签名。但若A利用相同K签名两次，即的签名为及，则攻击者可以由联立方程式

可得：，同时可以求得K。因此，同一个K不可重复使用。5.4DSS数字签名标准1．参数与密钥生成①选取大素数p，满足＜p＜，其中512≤L≤1024且L是64的倍数。显然，p是L位长的素数，L从512到1024且是64的倍数。②选取大素数q，q是p

1的一个素因子且，即q是160位的素数且是p

1的素因子。③选取一个生成元，其中h是一个整数，满足1＜h＜p

1并且。④随机选取整数x，0＜x＜q，计算。⑤p、q和g是公开参数，y为公钥，x为私钥。2．签名对于消息m，首先随机选取一个整数k,0＜k＜q，然后计算：

,

则m的签名为(r,s)，其中h为Hash函数，DSS规定Hash函数为SHA-1。3．验证对于消息签名对(m,(r,s))，首先计算：然后验证：如果等式成立，则(r,s)是m的有效签名；否则签名无效。算法合理性证明因为：s=k

1(h(m)+xr)modq所以：ks=(h(m)+xr)modq于是我们有：第七章密码协议复习要点Diffie-Hellman密钥交换原理及安全性Shamir门限方案Kerberos认证协议用户B用户ADiffie-Hellman密钥交换W.Diffie和M.Hellman1976年提出算法的安全性基于求离散对数的困难性选择随机数x<p计算YA=gxmodp选择随机数y<p计算YB=gymodpYAYB计算K=YA

y

=gxymodp计算K=YB

x

=gxymodp中间人攻击用户B选择随机数y<p计算YB=gymodp计算KBC=YCy

=gyzmodp用户A选择随机数x<p计算YA=gxmodp计算KAC=YC

x

=gxzmodp敌手C选择随机数z<p计算YC=gzmodp计算KBC=YB

z

=gyzmodpYAYCYC计算KAC=YA

z

=gxzmodpYB端到端协议1992年，Diffie、Oorschot和Wiener提出了一个端到端协议（station-