6.1Hash函数

1第一节第一节HashHash函数函数西北工业大学理学院应用数学系西北工业大学理学院应用数学系2一、一、消息的鉴别与认证消息的鉴别与认证11、网络通信的攻击威胁、网络通信的攻击威胁ØØ泄露：把消息内容发布给任何人或没有合法密钥的进程泄露：把消息内容发布给任何人或没有合法密钥的进程ØØ流量分析：发现通信双方之间信息流的结构模式，可以用来确流量分析：发现通信双方之间信息流的结构模式，可以用来确定连接的频率、持续时间长度；还可以发现报文数量和长度等定连接的频率、持续时间长度；还可以发现报文数量和长度等ØØ伪装：从一个假冒信息源向网络中插入消息伪装：从一个假冒信息源向网络中插入消息ØØ内容篡改：消息内容被插入、删除、变换、修改内容篡改：消息内容被插入、删除、变换、修改ØØ顺序修改：插入、删除或重组消息序列顺序修改：插入、删除或重组消息序列ØØ时间修改：消息延迟或重放时间修改：消息延迟或重放ØØ否认：接受者否认收到消息；发送者否认发送过消息否认：接受者否认收到消息；发送者否认发送过消息322、消息的鉴别与认证、消息的鉴别与认证一、一、消息的鉴别与认证消息的鉴别与认证在网络通信中，除了需要利用各种加密算法对消息的在网络通信中，除了需要利用各种加密算法对消息的内容进行保密以外，还需要防止内容进行保密以外，还需要防止““假冒假冒””和和““篡改篡改””。。ØØ鉴别：鉴别：authenticationauthentication真伪性真伪性(1)(1)用来验证发送的数据用来验证发送的数据,,特别是一个信息的完整性的过程。特别是一个信息的完整性的过程。(2)(2)在用户开始使用系统时对其身份进行的确认。在用户开始使用系统时对其身份进行的确认。ØØ认证：认证：CertificationCertification资格审查资格审查计算安全学用语计算安全学用语,,指为了鉴定一个计算机系统或网络的指为了鉴定一个计算机系统或网络的设计和它提供的手段在多大程度上能满足预定的安全要求而设计和它提供的手段在多大程度上能满足预定的安全要求而进行的技术评估。进行的技术评估。4消息鉴别消息鉴别与与常规加密的比较常规加密的比较一、一、消息的鉴别与认证消息的鉴别与认证ØØ保密性与真实性是两个不同的概念保密性与真实性是两个不同的概念ØØ根本上根本上,,信息加密提供的是保密性而非真实性信息加密提供的是保密性而非真实性ØØ加密代价大加密代价大((公钥算法代价更大公钥算法代价更大))ØØ鉴别函数与保密函数的分离能提供功能上的灵活性鉴别函数与保密函数的分离能提供功能上的灵活性ØØ某些信息只需要真实性某些信息只需要真实性,,不需要保密性不需要保密性ØØ––广播的信息难以使用加密广播的信息难以使用加密((信息量大信息量大))ØØ––网络管理信息等只需要真实性网络管理信息等只需要真实性ØØ––政府政府//权威部门的公告权威部门的公告533、消息鉴别的目的与鉴别模型、消息鉴别的目的与鉴别模型一、一、消息的鉴别与认证消息的鉴别与认证ØØ信源识别：验证信息的发送者是真正的，而不是冒充的信源识别：验证信息的发送者是真正的，而不是冒充的ØØ验证信息的完整性，在传送或存储过程中未被篡改，重放或验证信息的完整性，在传送或存储过程中未被篡改，重放或延迟等延迟等644、消息鉴别函数的分类、消息鉴别函数的分类一、一、消息的鉴别与认证消息的鉴别与认证ØØ消息加密：整个消息的密文作为认证标识消息加密：整个消息的密文作为认证标识ØØ消息鉴别码消息鉴别码(MAC)(MAC)：：公开函数公开函数++密钥产生一个固定长密钥产生一个固定长度的值作为认证标识度的值作为认证标识ØØ散列函数（散列函数（HashHash函数）：一个公开函数将任意长度的函数）：一个公开函数将任意长度的消息映射到一个固定长度的哈希值，作为认证标识消息映射到一个固定长度的哈希值，作为认证标识711、、HashHash函数的定义函数的定义二、二、HashHash函数与函数与MACMAC:, fAB®函数若满足如下两个条件，就称为单向函数： 1,(); xAyfxyBÎ=Î（）计算很容易，其中 ,,() yBxAyfx （2）求使得是不可能的。ÎÎ=设映射设映射hh把把可变可变输入长度串（叫做预映射，输入长度串（叫做预映射，PrePre--imageimage））转换成转换成固定长度固定长度（经常更短）输出串（叫做（经常更短）输出串（叫做HashHash值）如值）如果果hh满足以下三个条件之一，就称满足以下三个条件之一，就称hh为为HashHash函数：函数：8实际上，一个好的实际上，一个好的HashHash函数还要求函数还要求HashHash值值CC的每一的每一bitbit都与预映射都与预映射mm的每一的每一bitbit相关，而且具有雪崩效应。相关，而且具有雪崩效应。 ** 2,,()()Î= xxAHxHx 条件（弱无碰撞）：已知寻找使在计算上是不可能的。 HHash 条件1：是个单向函数，这是保证函数安全的关键。 ** ,()()= xxHxHx 条件3（强无碰撞）：寻找一对和使得在计算上是不可能的。二、二、HashHash函数与函数与MACMAC9HashHash函数有很多名字函数有很多名字：：杂凑函数杂凑函数、、散列函数散列函数、、压缩函压缩函数数、缩短函数、、缩短函数、消息摘消息摘要要（（MDMD：：MessageDigestMessageDigest）、数）、数字指纹、密码校验和、信息完整性检验（字指纹、密码校验和、信息完整性检验（DICDIC）、操作）、操作检验码（检验码（MDCMDC）。它是现代密码学的）。它是现代密码学的核心内容。核心内容。22、消息认证码（、消息认证码（MACMAC：：MessageauthenticationCodeMessageauthenticationCode））MACMAC是带有秘密密钥的是带有秘密密钥的hashhash函数。其函数。其HashHash值是预映射值是预映射的值和密钥的函数。将的值和密钥的函数。将MACMAC附在消息后，作为认证附在消息后，作为认证用。用。只有拥有密钥的人才能验证只有拥有密钥的人才能验证hashhash值。可以用值。可以用hashhash函数或函数或分组加密算法产生分组加密算法产生MACMAC；也有专用于；也有专用于MACMAC的算法。的算法。二、二、HashHash函数与函数与MACMAC1033、、HashHash函数（函数（MACMAC）的工作模式）的工作模式 (m)Hash k Hkk 记为以为参数的函数，其中可以是密钥。工作模式工作模式11mmh=h=HHkk(m(m))kk||||mmhhhh’’==HHkk(m(m))kk比较比较hh和和hh’’信源信源信宿信宿条件：信源和信宿必须使用相同的密钥条件：信源和信宿必须使用相同的密钥缺点：消息缺点：消息mm未加保密未加保密二、二、HashHash函数与函数与MACMAC11工作模式工作模式22条件：信源和信宿必须使用两个相同的密钥，条件：信源和信宿必须使用两个相同的密钥，kk11也可也可以等于以等于kk22特点：消息特点：消息mm未保密，而未保密，而Hash(mHash(m))都得到了加密都得到了加密mmh=h=HHkk(m(m))kk11||||mmcchh’’==HHkk(m(m))kk11比较比较hh和和hh’’信源信源信宿信宿EEDDkk22kk22cc二、二、HashHash函数与函数与MACMAC12工作模式工作模式33mmh=h=HHkk(m(m))kk11||||mmhhhh’’==HHkk(m(m))kk11比较比较hh和和hh’’信源信源信宿信宿EEkk22DDkk22条件：信源和信宿必须使用两个相同的密钥，条件：信源和信宿必须使用两个相同的密钥，kk11也可也可以等于以等于kk22特点：消息特点：消息mm和和Hash(mHash(m))都得到了加密都得到了加密二、二、HashHash函数与函数与MACMAC13工作模式工作模式44特点：基于公钥密码算法的工作模式，验证时，需要特点：基于公钥密码算法的工作模式，验证时，需要使用信源的公钥。使用信源的公钥。mmh=h=HHkk(m(m))kk11||||mmcchh’’==HHkk(m(m))kk11比较比较hh和和hh’’信源信源信宿信宿DDAAEEAAKKAAkkAAcc二、二、HashHash函数与函数与MACMAC14工作模式工作模式55特点：基于公钥密码算法的工作模式，验证时，需要特点：基于公钥密码算法的工作模式，验证时，需要使用信源的公钥。使用信源的公钥。mmh=h=HHkk(m(m))kk11||||mmhhhh’’==HHkk(m(m))kk11比较比较hh和和hh’’信源信源信宿信宿DDAAkkAAEEAAKKAA二、二、HashHash函数与函数与MACMAC15DSADSA————DecimalShiftandAddDecimalShiftandAdd十进制移位加算法，是十进制移位加算法，是由由SieveSieve于于19801980年向年向ISOISO提出的一种产生提出的一种产生MACMAC的算法。特的算法。特别适用于金融支付中的数值消息交换业务。别适用于金融支付中的数值消息交换业务。三、三、DSADSA算法算法—— ——产生产生MACMAC的算法的算法1(): Rdmd （）表示十位的一组消息右旋转移动位后的结果：DSADSA算法将消息算法将消息mm转化成十进制数，并分成转化成十进制数，并分成1010位一组，位一组，若最后一组不足若最后一组不足1010位，可以通过右边补零凑足位，可以通过右边补零凑足1010位。位。DSADSA算法中涉及到的运算：算法中涉及到的运算：如如mm＝＝12345678901234567890，则，则R(3)mR(3)m＝＝8901234567890123456716例如：例如：mm＝＝12345678901234567890，则：，则：三、三、DSADSA算法算法—— ——产生产生MACMAC的算法的算法8901234567 1234567890 (3)0135802457= Sm (2)S(d)m(2)S(d)m：表示：表示R(d)mR(d)m＋＋mmod10mmod101010在在DSADSA算法中，收发信双方必须掌握两个十位十进制算法中，收发信双方必须掌握两个十位十进制密钥密钥kk11和和kk22，，17DSADSA算法实例：算法实例：三、三、DSADSA算法算法—— ——产生产生MACMAC的算法的算法设设kk11＝＝53792248635379224863，，kk22＝＝25623572842562357284，，消息消息mm＝＝238643781322356376.238643781322356376.首先，将首先，将mm分为分为mm11＝＝23864378132386437813，，mm22＝＝22356376223563760000，，补零第一轮：第一轮：先算先算pp11(1)(1)＝＝mm11+k+k11(mod10(mod101010),p),p22(1)(1)＝＝mm11+k+k22(mod10(mod101010),),而后根据而后根据kk22的第的第一一位数值位数值22，对，对pp11(1)(1)计算计算S(2)(pS(2)(p11(1)(1)))，记，记作作kk11(1)(1)；根据；根据kk11的第的第一一位数值位数值55，对，对pp22(1)(1)计算计算S(5)(pS(5)(p22(1)(1)))，，记作记作kk22(1)(1)，，即：即：18三、三、DSADSA算法算法—— ——产生产生MACMAC的算法的算法1 1(1) 1 (1)10 111 2386437813 379224863 77 5 65662676 mod10===º+ m kp pmk 1 2(1)2 (1)10 212 2386437813 562357284 49 2 4879