密码学基础3P.ppt

密码学基础3P Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望目目 录录1.消息鉴别与散列函数消息鉴别与散列函数2.散列算法散列算法3.数字签名数字签名消息鉴别与散列函数消息鉴别与散列函数 Message Authentication and Has 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)：公开函数：公开函数+密钥产生一个固密钥产生一个固定长度的值作为认证标识定长度的值作为认证标识散列函数：一个公开函数将任意长度的消息映散列函数：一个公开函数将任意长度的消息映射到一个固定长度的哈希值，作为认证标识射到一个固定长度的哈希值，作为认证标识鉴别函数分类鉴别函数分类消息加密：整个消息的密文作为认证标识消息加密：整个消息的密文作为认证标识消息鉴别码消息鉴别码(MAC)：公开函数：公开函数+密钥产生一个固密钥产生一个固定长度的值作为认证标识定长度的值作为认证标识散列函数：一个公开函数将任意长度的消息映散列函数：一个公开函数将任意长度的消息映射到一个固定长度的哈希值，作为认证标识射到一个固定长度的哈希值，作为认证标识消息加密消息加密对称加密保密和鉴别对称加密保密和鉴别AB对称加密保密和鉴别对称加密保密和鉴别明文明文M的自动确定的自动确定M定义为有意义的明文序列，便于自动识别定义为有意义的明文序列，便于自动识别强制定义明文的某种结构，这种结构是易于识别但又强制定义明文的某种结构，这种结构是易于识别但又不能复制且无需借助加密的不能复制且无需借助加密的可以在加密前对每个报文附加检错码，即所谓的可以在加密前对每个报文附加检错码，即所谓的帧检帧检验序列号验序列号或或检验和检验和FCS内部差错控制和外部差错控制内部差错控制和外部差错控制差错控制差错控制更难于构造更难于构造公钥加密保密性公钥加密保密性AB公钥加密鉴别和签名公钥加密鉴别和签名AB公钥加密保密、鉴别和签名公钥加密保密、鉴别和签名AB消息鉴别码消息鉴别码MAC消息鉴别码消息鉴别码使用一个密钥生成一个固定大小的小数据块，并加入到消息中，使用一个密钥生成一个固定大小的小数据块，并加入到消息中，称称MAC，或密码校验和（或密码校验和（cryptographic checksum）1、接收者可以确信消息接收者可以确信消息M未被改变未被改变 2、接收者可以确信消息来自所声称的发送者、接收者可以确信消息来自所声称的发送者 3、如果消息中包含顺序码（如、如果消息中包含顺序码（如HDLC,X.25,TCP），则接收者），则接收者可以保证消息的正常顺序可以保证消息的正常顺序MACMAC函数类似于加密函数，但不需要可逆性。因此在数学上比函数类似于加密函数，但不需要可逆性。因此在数学上比加密算法被攻击的弱点要少加密算法被攻击的弱点要少消息鉴别消息鉴别AB消息鉴别与保密，鉴别与明文连接消息鉴别与保密，鉴别与明文连接AB消息鉴别与保密，鉴别与密文连接消息鉴别与保密，鉴别与密文连接AB消息鉴别消息鉴别 VS 常规加密常规加密保密性与真实性是两个不同的概念保密性与真实性是两个不同的概念根本上根本上,信息加密提供的是保密性而非真实性信息加密提供的是保密性而非真实性加密代价大加密代价大(公钥算法代价更大公钥算法代价更大)鉴别函数与保密函数的分离能提供功能上的灵活性鉴别函数与保密函数的分离能提供功能上的灵活性某些信息只需要真实性某些信息只需要真实性,不需要保密性不需要保密性 广播的信息难以使用加密广播的信息难以使用加密(信息量大信息量大)网络管理信息等只需要真实性网络管理信息等只需要真实性 政府政府/权威部门的公告权威部门的公告散列函数散列函数Hash Function散列函数散列函数H(M):输入为任意长度的消息输入为任意长度的消息M;输出为一个固定长输出为一个固定长度的散列值，称为消息摘要度的散列值，称为消息摘要(MessageDigest）H(M)是消息是消息M的所有位的函数并提供错误检测能力：的所有位的函数并提供错误检测能力：消息中的任何一位或多位的变化都将导致该散列值的消息中的任何一位或多位的变化都将导致该散列值的变化变化H(M)又称为：哈希函数、数字指纹（又称为：哈希函数、数字指纹（Digital finger print)、压缩（、压缩（Compression)函数、数据鉴别码函数、数据鉴别码（Dataauthentication code）等）等散列函数基本用法散列函数基本用法(1)散列函数基本用法散列函数基本用法(2)散列函数基本用法散列函数基本用法(3)散列函数基本用法散列函数基本用法(4)散列函数基本用法散列函数基本用法(5)散列函数基本用法散列函数基本用法(6)消息鉴别码消息鉴别码MACMKMAC函数域：任意长度的报文函数域：任意长度的报文值域：所有可能的值域：所有可能的MAC和所有可能的密钥和所有可能的密钥MAC一般为多对一函数一般为多对一函数函数域：任意长度的报文函数域：任意长度的报文值域：所有可能的值域：所有可能的MAC和所有可能的密钥和所有可能的密钥假设假设假设攻击者使用强行攻击，且已经获得报文的明文和相应的假设攻击者使用强行攻击，且已经获得报文的明文和相应的MAC,MAC,即即 对对MAC的强行攻击的强行攻击假设假设假设攻击者已经获得报文的明文和相应的假设攻击者已经获得报文的明文和相应的MAC,MAC,即即 假设假设 对对MAC的强行攻击的强行攻击对对MAC的强行攻击的强行攻击对对MAC的强行攻击的强行攻击如果如果 kn kn，则第一轮就可以产生一个唯一对应。仍然可，则第一轮就可以产生一个唯一对应。仍然可以有多于一个以有多于一个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的其它攻击的其它攻击设设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的报文鉴别码的报文鉴别码n算法来源算法来源nFIPS publication(FIPS PUB 113)nANSI standard(X9.17)n使用使用CBC(Cipher Block Chaining)方式，初方式，初始向量为始向量为IV=0基于基于DES的报文鉴别码的报文鉴别码将数据按将数据按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)要相对易于计算，使得硬件和软件实现成为实际要相对易于计算，使得硬件和软件实现成为实际可能可能对任何给定的码对任何给定的码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值值MD5MD5描述描述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小结小结1.Hash函数把变长信息映射到定长信息函数把变长信息映射到定长信息2.Hash函数不具备可逆性函数不具备可逆性3.Hash函数速度较快函数速度较快4.Hash函数与对称密钥加密算法有某种相似性函数与对称密钥加密算法有某种相似性5.5.对对Hash函数的密码分析比对称密钥密码更困难函数的密码分析比对称密钥密码更困难6.Hash函数可用于消息摘要函数可用于消息摘要7.Hash函数可用于数字签名函数可用于数字签名目目 录录1.消息鉴别与散列函数消息鉴别与散列函数2.散列算法散列算法3.数字签名数字签名报文鉴别的局限性报文鉴别的局限性用于保护通信双方免受第三方攻击用于保护通信双方免受第三方攻击无法防止通信双方的相互攻击无法防止通信双方的相互攻击n信宿方伪造报文信宿方伪造报文n信源方否认已发送的报文信源方否认已发送的报文引入数字签名，是笔迹签名的模拟引入数字签名，是笔迹签名的模拟数字签名的性质数字签名的性质传统签名的基本特点传统签名的基本特点n能与被签的文件在物理上不可分割能与被签的文件在物理上不可分割n签名者不能否认自己的签名签名者不能否认自己的签名n签名不能被伪造签名不能被伪造n容易被验证容易被验证数字签名是传统签名的数字化数字签名是传统签名的数字化n能与所签文件能与所签文件“绑定绑定”n签名者不能否认自己的签名签名者不能否认自己的签名n容易被自动验证容易被自动验证n签名不能被伪造签名不能被伪造数字签名的性质数字签名的性质必须能够验证作者及其签名的日期时间必须能够验证作者及其签名的日期时间必须能够认证签名时刻的内容必须能够认证签名时刻的内容签名必须能够由第三方验证，以解决争议签名必须能够由第三方验证，以解决争议数字签名的设计要求数字签名的设计要求1.签名必须是依赖于被签名信息的一个位串模板签名必须是依赖于被签名信息的一个位串模板2.签名必须使用某些对发送者是唯一的信息，以防止双方的伪造与签名必须使用某些对发送者是唯一的信息，以防止双方的伪造与否认否认3.必须相对容易生成该数字签名必须相对容易生成该数字签名4.必须相对容易识别和验证该数字签名必须相对容易识别和验证该数字签名5.伪造该数字签名在计算复杂性意义上具有不可行性，既包括对一伪造该数字签名在计算复杂性意义上具有不可行性，既包括对一个已有的数字签名构造新的消息，也包括对一个给定消息伪造一个个已有的数字签名构造新的消息，也包括对一个给定消息伪造一个数字签名数字签名6.在存储器中保存一个数字签名副本是现实可行的在存储器中保存一个数字签名副本是现实可行的数字签名分类数字签名分类签名方式签名方式n直接数字签名直接数字签名direct digital signaturen仲裁数字签名仲裁数字签名arbitrated digital signature安全性安全性 无条件安全的数字签名无条件安全的数字签名 计算上安全的数字签名计算上安全的数字签名可签名次数可签名次数一次性的数字签名一次性的数字签名 多次性的数字签名多次性的数字签名直接数字签名直接数字签名直接数字签名直接数字签名直接数字签名直接数字签名直接数字签名的缺点直接数字签名的缺点验证模式依赖于发送方的保密密钥验证模式依赖于发送方的保密密钥 发送方要抵赖发送某一消息时，可能会声称其私有密钥丢失或被发送方要抵赖发送某一消息时，可能会声称其私有密钥丢失或被窃，从而他人伪造了他的签名窃，从而他人伪造了他的签名 通常需要采用与私有密钥安全性相关的行政管理控制手段来制止通常需要采用与私有密钥安全性相关的行政管理控制手段来制止或至少是削弱这种情况，但威胁在某种程度上依然存在或至少是削弱这种情况，但威胁在某种程度上依然存在 改进的方式例如可以要求被签名的信息包含一个时间戳（日期与时改进的方式例如可以要求被签名的信息包含一个时间戳（日期与时间），并要求将已暴露的密钥报告给一个授权中心间），并要求将已暴露的密钥报告给一个授权中心X的某些私有密钥确实在时间的某些私有密钥确实在时间T被窃取，敌方可以伪造被窃取，敌方可以伪造X的签名及早的签名及早于或等于时间于或等于时间T的时间戳的时间戳仲裁数字签名仲裁数字签名仲裁数字签名仲裁数字签名1.1.引入仲裁者引入仲裁者 所有从发送方所有从发送方X到接收方到接收方Y的签名消息首先送到仲裁者的签名消息首先送到仲裁者A A将消息及其签名进行一系列测试，以检查其来源和内容将消息及其签名进行一系列测试，以检查其来源和内容 A将消息加上日期并与已被仲裁者验证通过的指示一起发给将消息加上日期并与已被仲裁者验证通过的指示一起发给Y1.1.仲裁者在这一类签名模式中扮演敏感和关键的角色仲裁者在这一类签名模式中扮演敏感和关键的角色 所有的参与者必须极大地相信这一仲裁机制工作正常所有的参与者必须极大地相信这一仲裁机制工作正常仲裁数字签名单密钥加密方式仲裁数字签名单密钥加密方式1数字签名数字签名仲裁数字签名单密钥加密方式仲裁数字签名单密钥加密方式仲裁数字签名单密钥加密方式仲裁数字签名单密钥加密方式2仲裁数字签名双密钥加密方式仲裁数字签名双密钥加密方式仲裁数字签名双密钥加密方式仲裁数字签名双密钥加密方式数字签名算法数字签名算法1.1.普通数字签名算法普通数字签名算法 EIGamal RSA DSS/DSA1.1.不可否认的数字签名算法不可否认的数字签名算法2.2.群签名算法群签名算法3.3.盲签名算法盲签名算法数字签名算法数字签名算法DSADSADSADSADSA分析分析1.1.基于离散对数的难度，对手通过基于离散对数的难度，对手通过r r恢复恢复k k，或通过，或通过s s恢复恢复x x都很难都很难2.2.签名产生的计算任务仅是计算签名产生的计算任务仅是计算3.3.另一个需要完成的工作只是确定逆元另一个需要完成的工作只是确定逆元