(精品)密码学基础3.ppt

华南理工大学信息网络工程研究中心 Network Engineering and Research Center South China University of Technology密码学基础（密码学基础（3）目目 录录1.消息鉴别与散列函数消息鉴别与散列函数2.散列算法散列算法3.数字签名数字签名消息鉴别与散列函数消息鉴别与散列函数 Message Authentication and Hash Functions网络通信的攻击威胁网络通信的攻击威胁泄露：把消息内容发布给任何人或没有合法密钥的进泄露：把消息内容发布给任何人或没有合法密钥的进程程流量分析：发现通信双方之间信息流的结构模式，可流量分析：发现通信双方之间信息流的结构模式，可以用来确定连接的频率、持续时间长度；还可以发现以用来确定连接的频率、持续时间长度；还可以发现报文数量和长度等报文数量和长度等伪装：从一个假冒信息源向网络中插入消息伪装：从一个假冒信息源向网络中插入消息内容篡改：消息内容被插入、删除、变换、修改内容篡改：消息内容被插入、删除、变换、修改顺序修改：插入、删除或重组消息序列顺序修改：插入、删除或重组消息序列时间修改：消息延迟或重放时间修改：消息延迟或重放否认：接受者否认收到消息；发送者否认发送过消息否认：接受者否认收到消息；发送者否认发送过消息解决第一、第二个问题的措施：解决第一、第二个问题的措施：加加/解密解密解决第三解决第三 六个问题的措施：六个问题的措施：报文鉴别报文鉴别解决第三解决第三 七个问题的措施：七个问题的措施：数字签名数字签名鉴别和认证鉴别和认证鉴别鉴别：authentication 真伪性真伪性 (1)A process used to verify the integrity of transmitted data,especially a message 用来验证发送的数据,特别是一个信息的完整性的过程 (2)The act of establishing the identity of users when they start to use the system 在用户开始使用系统时对其身份进行的确认认证：认证：Certification 资格审查资格审查 In computer security,the technical evaluation made as part of and in support of the accreditation process,that established the extent to which a particular computer system or network design and implementation meet prespecified security requirements 计算安全学用语,指为了鉴定一个计算机系统或网络的设计和它提供的手段在多大程度上能满足预定的安全要求而进行的技术评估鉴别机制的结构鉴别机制的结构任何消息认证或数字签名机制可以看到两个层次：任何消息认证或数字签名机制可以看到两个层次：底层底层必须有某种函数产生一个认证标识：一个必须有某种函数产生一个认证标识：一个用于认证一个报文的值用于认证一个报文的值高层高层认证协议以底层函数为原语，使接收者完认证协议以底层函数为原语，使接收者完成报文的鉴别成报文的鉴别鉴别的目的鉴别的目的信源识别：验证信息的发送者是真正的，而不信源识别：验证信息的发送者是真正的，而不是冒充的是冒充的验证信息的完整性，在传送或存储过程中未被验证信息的完整性，在传送或存储过程中未被篡改，重放或延迟等篡改，重放或延迟等鉴别模型鉴别模型鉴别编码器和鉴别译码器可抽象为鉴别函数鉴别编码器和鉴别译码器可抽象为鉴别函数鉴别系统的需求鉴别系统的需求一个安全的鉴别系统，需满足一个安全的鉴别系统，需满足（1）指定的接收者能够检验和证实消息的合法性、）指定的接收者能够检验和证实消息的合法性、真实性和完整性真实性和完整性（2）消息的发送者和接收者不能抵赖）消息的发送者和接收者不能抵赖（3）除了合法的消息发送者，其它人不能伪造合法）除了合法的消息发送者，其它人不能伪造合法的消息的消息鉴别函数分类鉴别函数分类消息加密：整个消息的密文作为认证标识消息加密：整个消息的密文作为认证标识消息鉴别码消息鉴别码(MAC)：公开函数：公开函数+密钥产生一个密钥产生一个固定长度的值作为认证标识固定长度的值作为认证标识散列函数：一个公开函数将任意长度的消息映散列函数：一个公开函数将任意长度的消息映射到一个固定长度的哈希值，作为认证标识射到一个固定长度的哈希值，作为认证标识消息加密消息加密对称加密保密和鉴别对称加密保密和鉴别AB对称加密保密和鉴别对称加密保密和鉴别明文明文M的自动确定的自动确定M定义为有意义的明文序列，便于自动识别定义为有意义的明文序列，便于自动识别强制定义明文的某种结构，这种结构是易强制定义明文的某种结构，这种结构是易于识别但又不能复制且无需借助加密的于识别但又不能复制且无需借助加密的可以在加密前对每个报文附加检错码，即可以在加密前对每个报文附加检错码，即所谓的所谓的帧检验序列号帧检验序列号或或检验和检验和FCS内部差错控制和外部差错控制内部差错控制和外部差错控制自动的重要性及其问题FCS的应用过程的应用过程内部差错控制FCS的应用过程的应用过程 CONT外部差错控制比较内外部差错控制的区别：差错控制和抗攻击性公钥加密保密性公钥加密保密性AB公钥加密鉴别和签名公钥加密鉴别和签名AB公钥加密保密、鉴别和签名公钥加密保密、鉴别和签名AB消息鉴别码消息鉴别码 MACMAC -概念的引入概念的引入使用一个密钥生成一个固定大小的小数据块，并加入到使用一个密钥生成一个固定大小的小数据块，并加入到消息中，称消息中，称MAC，或密码校验和（或密码校验和（cryptographic checksum）1、接收者可以确信消息接收者可以确信消息M未被改变未被改变 2、接收者可以确信消息来自所声称的发送者、接收者可以确信消息来自所声称的发送者 3、如果消息中包含顺序码（如、如果消息中包含顺序码（如HDLC,X.25,TCP），），则接收者可以保证消息的正常顺序则接收者可以保证消息的正常顺序MACMAC函数类似于加密函数，但不需要可逆性。因此在数函数类似于加密函数，但不需要可逆性。因此在数学上比加密算法被攻击的弱点要少学上比加密算法被攻击的弱点要少消息鉴别消息鉴别 简单过程简单过程AB消息鉴别保密消息鉴别保密 鉴别与明文相关鉴别与明文相关连连AB消息鉴别与保密消息鉴别与保密 鉴别与密文相鉴别与密文相关连关连AB】消息鉴别消息鉴别 VS 常规加密常规加密保密性与真实性是两个不同的概念保密性与真实性是两个不同的概念根本上根本上,信息加密提供的是保密性而非真实性信息加密提供的是保密性而非真实性加密代价大加密代价大(公钥算法代价更大公钥算法代价更大)鉴别函数与保密函数的分离能提供功能上的灵鉴别函数与保密函数的分离能提供功能上的灵活性活性某些信息只需要真实性某些信息只需要真实性,不需要保密性不需要保密性 广播的信息难以使用加密广播的信息难以使用加密(信息量大信息量大)网络管理信息等只需要真实性网络管理信息等只需要真实性 政府政府/权威部门的公告权威部门的公告散列函数散列函数Hash Function散列函数散列函数Hash Function又称哈希函数为数字指纹（又称哈希函数为数字指纹（Digital finger print)、压缩、压缩（Compression)函数、数据鉴别码（函数、数据鉴别码（Data authentication code）等）等H(M):输入为任意长度的消息输入为任意长度的消息M;输出为一个固定输出为一个固定长度的长度的散列值散列值（HashHash），称为），称为消息摘要消息摘要(Message Digest）散列函数散列函数Hash Function(cont)H(M)是消息是消息M的所有位的函数并提供错误检测的所有位的函数并提供错误检测能力：消息中的任何一位或多位的变化都将导致能力：消息中的任何一位或多位的变化都将导致该散列值的变化该散列值的变化Hash Function Hash Function 的集合映射性质的集合映射性质多对一映射多对一映射Secure HASH FunctionsnPurpose of the HASH function is to produce a“fingerprint”.nProperties of a HASH function H:1.H can be applied to a block of data at any size2.H produces a fixed length output3.H(x)is easy to compute for any given x.4.For any given block x,it is computationally infeasible to find x such that H(x)=h5.For any given block x,it is computationally infeasible to find with H(y)=H(x).6.It is computationally infeasible to find any pair(x,y)such that H(x)=H(y)散列函数基本用法散列函数基本用法(1)散列函数基本用法散列函数基本用法(2)散列函数基本用法散列函数基本用法(3)散列函数基本用法散列函数基本用法(4)散列函数基本用法散列函数基本用法(5)散列函数基本用法散列函数基本用法(6)消息鉴别码消息鉴别码MACMKMAC函数域：任意长度的报文函数域：任意长度的报文值域：所有可能的值域：所有可能的MAC和所有和所有可能的密钥可能的密钥MAC一般为多对一函数一般为多对一函数函数域：任意长度的报文函数域：任意长度的报文值域：所有可能的值域：所有可能的MAC和所有可能的密钥和所有可能的密钥假设假设假设攻击者使用强行攻击，且已经获得报文的明文和假设攻击者使用强行攻击，且已经获得报文的明文和相应的相应的MAC,MAC,即即 对对MAC的强行攻击的强行攻击假设假设假设攻击者已经获得报文的明文和相应的假设攻击者已经获得报文的明文和相应的MAC,MAC,即即 假设假设 对对MAC的强行攻击的强行攻击(cont)对对MAC的强行攻击的强行攻击(cont)对对MAC的强行攻击的强行攻击(cont)如果如果 knkn，则第一轮就可以产生一，则第一轮就可以产生一个唯一对应。仍然可以有多于一个个唯一对应。仍然可以有多于一个keykey产生这一配对，这时攻击者只需产生这一配对，这时攻击者只需对一个新的对一个新的(message,MAC)(message,MAC)进行相同进行相同的测试的测试由此可见，强力攻击企图发现由此可见，强力攻击企图发现authentication keyauthentication key不小于甚至大于不小于甚至大于对同样长度的解密对同样长度的解密keykey的攻击的攻击对对MAC的其它攻击的其它攻击设设M=(X1|X2|Xm)是一个由是一个由64位位Xi数据块数据块连接而成连接而成 定义定义 (M)=X1 X2.Xm CK(M)=EK(M)其中其中 为异或操作；为异或操作；E为为 ECB工作模式的工作模式的DES算法算法则则Key length=56 bitMAC length=64 bit强力攻击需要至少强力攻击需要至少256次加密来决定次加密来决定K对对MAC的其它攻击的其它攻击(cont)设设M=(Y1|Y2|Ym-1|Ym)其中其中 Y1,Y2,Ym-1是替换是替换 X1,X2,Xm-1的任意值，而的任意值，而 Ym=Y1 Y2 ,Ym-1 (M)则则 CK(M)=EK(M)=EKY1 Y2 ,Ym-1 Ym =EKY1 Y2 ,Ym-1 (Y1 Y2 ,Ym-1 (M)=EK(M)这时消息这时消息M 和和 MAC=CK(M)=EK(M)是一对可被接收者认证是一对可被接收者认证的消息的消息用此方法，任何长度为用此方法，任何长度为64(m-1)位的消息可以被插入任意的欺骗位的消息可以被插入任意的欺骗性性信息信息MAC应具备的性质应具备的性质n如果一个攻击者得到如果一个攻击者得到M和和CK(M)，则攻击者构造一个消，则攻击者构造一个消息息M使得使得CK(M)=CK(M)应具有计算复杂性意义下的不可应具有计算复杂性意义下的不可行性行性nCK(M)应均匀分布，即：随机选择消息应均匀分布，即：随机选择消息M和和M，CK(M)=CK(M)的概率是的概率是2-n，其中，其中n是是MAC的位数的位数n令令M为为M的某些变换，即：的某些变换，即：M=f(M)，（例如：，（例如：f可以涉可以涉及及M中一个或多个给定位的反转），在这种情况下，中一个或多个给定位的反转），在这种情况下，PrCK(M)=CK(M)=2-n基于基于DES的报文鉴别码的报文鉴别码基于基于DES的报文鉴别码的报文鉴别码n算法来源算法来源nFIPS publication(FIPS PUB 113)nANSI standard(X9.17)n使用使用CBC(Cipher Block Chaining)方式，初方式，初始向量为始向量为IV=0基于基于DES的报文鉴别码的报文鉴别码(cont)将数据按将数据按64位分组，位分组，D1,D2,DN，必要时最后，必要时最后一个数据块用一个数据块用0向右填充向右填充运用运用DES算法算法E，密钥，密钥K数据认证码数据认证码(DAC)的计算如下：的计算如下：O1=EK(D1)O2=EK(D2O1)O3=EK(D3O2)ON=EK(DNON-1)FIPS PUB 113目目 录录1.消息鉴别与散列函数消息鉴别与散列函数2.散列算法散列算法3.数字签名数字签名散列函数散列函数散列函数的定义散列函数的定义散列函数：散列函数：M:变长报文变长报文H(M):定长的散列值定长的散列值主要用于为文件、报文或其它分组数据产生指纹主要用于为文件、报文或其它分组数据产生指纹散列函数的要求散列函数的要求H能用于任意大小的分组能用于任意大小的分组H能产生定长的输出能产生定长的输出对任何给定的对任何给定的x，H(x)要相对易于计算，使得硬件要相对易于计算，使得硬件和软件实现成为实际可能和软件实现成为实际可能散列函数的要求散列函数的要求(cont)对任何给定的码对任何给定的码h，寻找，寻找x使得使得H(x)=h在计算上是在计算上是不可行的，即单向性不可行的，即单向性对任何给定的分组对任何给定的分组x，寻找不等于，寻找不等于x的的y，使得，使得H(x)=H(y)在计算上是不可行的，即弱抗冲突性在计算上是不可行的，即弱抗冲突性寻找对任何的寻找对任何的(x,y)对使得对使得H(x)=H(y)在计算上是在计算上是不可行的，即强抗冲突性不可行的，即强抗冲突性Hash vs MACMAC需要对全部数据进行加需要对全部数据进行加MAC速度慢速度慢Hash是一种直接产生鉴别码的方法是一种直接产生鉴别码的方法Hash函数通用结构函数通用结构由由Ron Rivest于于1990年提出年提出MD4几乎被所有几乎被所有hash函数使用函数使用具体做法具体做法:把原始消息把原始消息M分成一些固定长度的块分成一些固定长度的块Yi 最后一块最后一块padding并使其包含消息并使其包含消息M长度长度 设定初始值设定初始值CV0 压缩函数压缩函数f,CVi=f(CVi-1,Yi-1)最后一个最后一个CVi为为hash值值Simple Hash FunctionnOne-bit circular shift on the hash value after each block is processed would improveMD5MD5描述描述Merkle于于1989年提出年提出hash function模型模型Ron Rivest于于1990年提出年提出MD41992年年,Ron Rivest 完成完成MD5(RFC 1321)在最近数年之前在最近数年之前,MD5是最主要的是最主要的hash算法算法现行美国标准现行美国标准SHA-1以以MD5的前身的前身MD4为基础为基础MD5描述描述 输入：任意长度的报文输入：任意长度的报文输入分组长度：输入分组长度：512 bit 输出：输出：128 bit 报文报文MD5描述描述step 1 附加长度值附加长度值对报文进行填充，使其比特数与对报文进行填充，使其比特数与448模模512同余，即同余，即填充长度为填充长度为512的整数倍减去的整数倍减去64填充方法：填充比特串的最高位为填充方法：填充比特串的最高位为1，其余各位均为，其余各位均为0MD5描述描述step 2 附加长度值附加长度值|M2|为为512的倍数的倍数:Y0,Y1,YL-1MD5描述描述step 3初始化初始化MD缓存缓存MD为为128bit，用于存放散列函数，用于存放散列函数的中间及最终结果的中间及最终结果MD可表示为可表示为4个个32bit的寄存器的寄存器(A,B,C,D)，初始化如下：，初始化如下：MD5描述描述step 4压缩：压缩：4个循环的压缩算法个循环的压缩算法MD5描述描述step 5输出输出HMD5单个单个512bit分组的分组的MD5处理过程处理过程(MD5压缩函数）压缩函数）当前正在处当前正在处理的理的512比特分组比特分组128bit的缓存值的缓存值更新缓存更新缓存T0,164每步操作形式每步操作形式单个单个512bit分组的分组的MD5处理过程处理过程(MD5压缩函数）压缩函数）X0.15:保存当前保存当前512bit待处理输入分组的值待处理输入分组的值Xk=Mq 16+k=在第在第q个个512位数据块中的第位数据块中的第k个个32位字位字每次循环每次循环(4)的每步的每步(16)内，内，Xi的使用循序各不相同的使用循序各不相同MD5的安全性的安全性Berson表明，对单循环表明，对单循环MD5，使用合适的密码分析可能在合理的，使用合适的密码分析可能在合理的时间内找出能够产生相同摘要的两个报文，这个结果被证明对四时间内找出能够产生相同摘要的两个报文，这个结果被证明对四个循环中的任意一个循环也成立，但作者没有能够提出如何攻击个循环中的任意一个循环也成立，但作者没有能够提出如何攻击包含全部包含全部4个循环个循环MD5的攻击的攻击Boer和和Bosselaers显示了即使缓存显示了即使缓存ABCD不同，不同，MD5对单个对单个512bit分组的执行将得到相同的输出分组的执行将得到相同的输出(伪冲突）伪冲突）Dobbertin的攻击技术：使的攻击技术：使MD5的压缩函数产生冲突，即寻找的压缩函数产生冲突，即寻找MD5被认为是易受攻击的，逐渐被被认为是易受攻击的，逐渐被SHA-1和和RIPEMD-160替代替代其它常用其它常用Hash算法算法SHA-1 RIPEMD-160 HMACHash小结小结Hash函数把变长信息映射到定长信息函数把变长信息映射到定长信息Hash函数不具备可逆性函数不具备可逆性Hash函数速度较快函数速度较快Hash函数与对称密钥加密算法有某种相似性函数与对称密钥加密算法有某种相似性对对Hash函数的密码分析比对称密钥密码更困难函数的密码分析比对称密钥密码更困难Hash函数可用于消息摘要函数可用于消息摘要Hash函数可用于数字签名函数可用于数字签名目目 录录1.消息鉴别与散列函数消息鉴别与散列函数2.散列算法散列算法3.数字签名数字签名报文鉴别的局限性报文鉴别的局限性用于保护通信双方免受第三方攻击用于保护通信双方免受第三方攻击无法防止通信双方的相互攻击无法防止通信双方的相互攻击n信宿方伪造报文信宿方伪造报文n信源方否认已发送的报文信源方否认已发送的报文引入数字签名，是笔迹签名的模拟引入数字签名，是笔迹签名的模拟数字签名的性质数字签名的性质传统签名的基本特点传统签名的基本特点n能与被签的文件在物理上不可分割能与被签的文件在物理上不可分割n签名者不能否认自己的签名签名者不能否认自己的签名n签名不能被伪造签名不能被伪造n容易被验证容易被验证数字签名是传统签名的数字化数字签名是传统签名的数字化n能与所签文件能与所签文件“绑定绑定”n签名者不能否认自己的签名签名者不能否认自己的签名n容易被自动验证容易被自动验证n签名不能被伪造签名不能被伪造数字签名的性质数字签名的性质(cont)必须能够验证作者及其签名的日期必须能够验证作者及其签名的日期时间时间必须能够认证签名时刻的内容必须能够认证签名时刻的内容签名必须能够由第三方验证，以解签名必须能够由第三方验证，以解决争议决争议数字签名的设计要求数字签名的设计要求 签名必须是依赖于被签名信息的一个位串模板签名必须是依赖于被签名信息的一个位串模板 签名必须使用某些对发送者是唯一的信息，以防止双签名必须使用某些对发送者是唯一的信息，以防止双方的伪造与否认方的伪造与否认 必须相对容易生成该数字签名必须相对容易生成该数字签名 必须相对容易识别和验证该数字签名必须相对容易识别和验证该数字签名 伪造该数字签名在计算复杂性意义上具有不可行性，伪造该数字签名在计算复杂性意义上具有不可行性，既包括对一个已有的数字签名构造新的消息，也包括既包括对一个已有的数字签名构造新的消息，也包括对一个给定消息伪造一个数字签名对一个给定消息伪造一个数字签名 在存储器中保存一个数字签名副本是现实可行的在存储器中保存一个数字签名副本是现实可行的数字签名分类数字签名分类签名方式签名方式n直接数字签名直接数字签名direct digital signaturen仲裁数字签名仲裁数字签名arbitrated digital signature安全性安全性 无条件安全的数字签名无条件安全的数字签名 计算上安全的数字签名计算上安全的数字签名可签名次数可签名次数一次性的数字签名一次性的数字签名 多次性的数字签名多次性的数字签名直接数字签名直接数字签名直接数字签名直接数字签名直接数字签名直接数字签名(cont)直接数字签名的缺点直接数字签名的缺点验证模式依赖于发送方的保密密钥验证模式依赖于发送方的保密密钥 发送方要抵赖发送某一消息时，可能会声称其私有密钥发送方要抵赖发送某一消息时，可能会声称其私有密钥丢失或被窃，从而他人伪造了他的签名丢失或被窃，从而他人伪造了他的签名 通常需要采用与私有密钥安全性相关的行政管理控制手通常需要采用与私有密钥安全性相关的行政管理控制手段来制止或至少是削弱这种情况，但威胁在某种程度上依段来制止或至少是削弱这种情况，但威胁在某种程度上依然存在然存在 改进的方式例如可以要求被签名的信息包含一个时间戳改进的方式例如可以要求被签名的信息包含一个时间戳（日期与时间），并要求将已暴露的密钥报告给一个授权（日期与时间），并要求将已暴露的密钥报告给一个授权中心中心X的某些私有密钥确实在时间的某些私有密钥确实在时间T被窃取，敌方可以伪造被窃取，敌方可以伪造X的的签名及早于或等于时间签名及早于或等于时间T的时间戳的时间戳仲裁数字签名仲裁数字签名仲裁数字签名仲裁数字签名引入仲裁者引入仲裁者 所有从发送方所有从发送方X到接收方到接收方Y的签名消息首先送到仲裁者的签名消息首先送到仲裁者A A将消息及其签名进行一系列测试，以检查其来源和内容将消息及其签名进行一系列测试，以检查其来源和内容 A将消息加上日期并与已被仲裁者验证通过的指示一起发将消息加上日期并与已被仲裁者验证通过的指示一起发给给Y仲裁者在这一类签名模式中扮演敏感和关键的角色仲裁者在这一类签名模式中扮演敏感和关键的角色 所有的参与者必须极大地相信这一仲裁机制工作正常所有的参与者必须极大地相信这一仲裁机制工作正常仲裁数字签名单密钥加密方式仲裁数字签名单密钥加密方式1数字签名数字签名仲裁数字签名单密钥加密方式仲裁数字签名单密钥加密方式仲裁数字签名单密钥加密方式仲裁数字签名单密钥加密方式2仲裁数字签名双密钥加密方式仲裁数字签名双密钥加密方式仲裁数字签名双密钥加密方式仲裁数字签名双密钥加密方式数字签名算法数字签名算法普通数字签名算法普通数字签名算法 EIGamal RSA DSS/DSA不可否认的数字签名算法不可否认的数字签名算法群签名算法群签名算法盲签名算法盲签名算法数字签名算法数字签名算法DSARSA签名方案RSA签名A的公钥私钥对的公钥私钥对KUa|KRaA对消息对消息M签名签名:SA=EKRa(M)问题问题:速度慢速度慢信息量大信息量大第三方仲裁时必须暴露明文信息第三方仲裁时必须暴露明文信息漏洞漏洞:EKRa(x y)EKRa(x)EKRa(y)mod no先做摘要先做摘要:HM=hash(M)o再对再对HM签名签名SA=EKRa(HM)hash函数的无碰撞性保证了签名的有效性函数的无碰撞性保证了签名的有效性思考题：请证明存在以上的漏洞，做了摘要之后漏洞还有吗？签名与加密签名提供真实性签名提供真实性(authentication)加密提供保密性加密提供保密性(confidentiality)“签名签名+加密加密”提供提供“真实性真实性+保密性保密性”两种实现方式两种实现方式:(AB)先签名先签名,后加密后加密:EKUbM|SigA(M)先加密先加密,后签名后签名:EKUb(M)|SigA(EKUb(M)方式方式的问题的问题:发生争议时发生争议时,B需要向仲裁者提供自己的私钥需要向仲裁者提供自己的私钥安全漏洞安全漏洞:攻击者攻击者E截获消息截获消息,把把SigA(EKUb(M)换成换成SigE(EKUb(M),让让B以为该消息来自以为该消息来自E保存信息多保存信息多:除了除了M,SigA(EKUb(M),还要保存还要保存EKUb(M)(KUb可能过期可能过期)EIGamal签名方案n ElGamal于1985年提出,很大程度上为Diffe-Hellman密钥交换算法的推广和变形。分为两种情形:p是大素数q=p或者q是p-1的大素因子DSS(数字签名标准)是后者的一种变形,该方案是特别为签名的目的而设计的。这个方案的改进已被美国NIST（国家标准和技术研究所）采纳作为数字签名标准数字签名标准。原根原根(primitive root)Euler定理表明定理表明,对两个互素的整数对两个互素的整数a,n,a(n)1 mod n定义：定义：素数素数p的原根定义：如果的原根定义：如果a是素数是素数p的原根，则数的原根，则数a mod p,a2 mod p,ap-1 mod p是不同的并且包含是不同的并且包含1到到p-1的整数的某种排列。的整数的某种排列。离散对数离散对数若若a是素数是素数p的一个原根的一个原根,则对任意整数则对任意整数b,b 0 mod p,存在唯一的整数存在唯一的整数i,1 i(p-1),使得使得:b ai mod pi称为称为b以以a为基模为基模p的的指数指数(离散对数离散对数),记作记作inda,p(b)离散对数的计算离散对数的计算:y gx mod p已知已知g,x,p,计算计算y是容易的是容易的已知已知y,g,p,计算计算x是困难的是困难的数字签名标准 公布于1994年5月19日的联邦记录上，并于1994年12月1日采纳为标准DSS。DSS为EIGamal签名方案的改进。DSS签名方案DSS算法说明-算法参数n全局公开密钥分量np 素数,其中2L-1p2L,512L1024,且L为64的倍数:即比特长度在512到1024之间,长度增量为64比特n q (p-1)的素因子,其中2159q2160ng=h(p-1)/q mod p,其中h是一整数,1h(p-1)n用户私有密钥nx 随机或伪随机整数,其中0 xqn用户公开密钥ny=gx mod pn用户每个报文的密数n k随机或伪随机整数,其中0kqDSS算法的签名与验证过程n签名nr=(gkmod p)mod qns=k-1(H(M)+xr)mod qn签名=(r,s)n验证nw=(s)-1 mod qnu1=H(M)w mod q,u2=(r)w mod qnv=(gu1yu2)mod p mod qnTEST:v=r n符号:nM 要签名的消息nH(M)使用SHA-1生成的M的散列码nM,r,s 接收到的M,r,s版本DSS签名和验证DSS的特点DSS的签名比验证快得多的签名比验证快得多DSS不能用于加密或者密钥分配不能用于加密或者密钥分配s-1 mod q要存在要存在 s 0 mod q,如果发生如果发生,接收者可拒绝该接收者可拒绝该签名签名.要求重新构造该签名要求重新构造该签名,实际上实际上,s 0 mod q的概率非的概率非常小常小若若p为为512位位,q为为160位位,而而DSS只需要两个只需要两个160位位,即即320位位一次数字签名n一次意味着只能签一个消息,当然可以进行若干次验证nLamport 数字签名方案Lamport方案缺陷:签名信息比较长.离散对数:p是1024位,则签名信息扩大1024倍对称密码:密钥是128位,则签名信息扩大128倍改进方案之一:Bos-Chaum签名方案群签名方案群中各个成员以群的名义匿名地签发消息.具备下列三个特性只有群成员能代表所在的群签名接收者能验证签名所在的群,但不知道签名者需要时,可借助于群成员或者可信机构找到签名者应用:投标盲签名盲签名要求:消息内容对签名者不可见签名被接收者泄漏后,签名者无法追踪签名应用:电子货币,电子选举盲签名过程:消息盲变换签名接收者逆盲变换DSADSA基于离散对数的难度，对手通过基于离散对数的难度，对手通过r r恢复恢复k k，或通过，或通过s s恢复恢复x x都很难都很难签名产生的计算任务仅是计算签名产生的计算任务仅是计算另一个需要完成的工作只是确定逆元另一个需要完成的工作只是确定逆元DSA分析分析思考与练习习题8.1习题8.5THE ENDUpdated on 2004-8-11