消息认证课件.ppt
92页
第5章 消息认证消息认证 主要内容v消息认证基本概念消息认证基本概念 v消息加密认证消息加密认证 v消息认证码消息认证码 v hash函数函数 消息认证 5.1 消息认证基本概念v认证(Authentication)：即鉴别、确认，它是证实某事是否名副其实，或是否有效的一个过程v认证与加密的区别：加密用以确保数据的保密性，阻止对手的被动攻击，如截取、窃听认证用以确保报文发送者和接受者的真实性以及报文的完整性，阻止对手的主动攻击，如冒充、篡改、重播等v认证往往是应用系统中安全保护的第一道防线，极为重要消息认证 基本思想v通过验证称谓者(人或事)的一个或多个参数的真实性和有效性，来达到验证称谓者是否名副其实的目的v常用的参数有：口令、标识符、密钥、信物、智能卡、指纹、视网纹等v利用人的生理特征参数进行认证的安全性高，但技术要求也高，至今尚未普及目前广泛应用的还是基于密码的认证技术消息认证 没有消息认证的通信系统是极为危险的 消息认证 消息认证(Message Authentication) v消息认证用于抗击主动攻击消息认证用于抗击主动攻击v验证接收消息的完整性验证接收消息的完整性v完整性完整性未被篡改、插入和删除未被篡改、插入和删除v验证消息的顺序性和时间性（未重排、重放验证消息的顺序性和时间性（未重排、重放和延迟）和延迟）消息认证 需求1.泄密：将消息透露给没有合法秘密钥的任何人或程序。
2.传输分析：分析通信双方的通信模式，如连接频率，时间等3.伪装：攻击者产生一条消息并声称来自某合法实体4.内容修改：对消息进行插入、删除、转化、修改5.顺序修改：对消息顺序进行插入、删除、重新排序6.计时修改：对消息的延时和重放7.发送方否认8.接受方否然v对付1、2可用加密；v对付3、4、5、6可用消息认证；v对付7、8可用数字签名消息认证 消息认证的基本概念v消息认证：验证所收到的消息和该消息被发送时是否相同，即是否被修改过v认证符(authenticator)：一个用来认证消息的值由消息的发送方产生认证符，并传递给接收方v认证函数：产生认证符的函数，认证函数实际上代表了一种产生认证符的方法消息加密(Message encryption )消息认证码(Message authentication code ,MAC)Hash函数(Hash function )消息认证 5.2 消息加密认证v对称密码实现消息加密认证v公钥密码实现消息加密认证消息认证 消息加密认证---在对称加密体制下v由于攻击者不知道密钥K，他也就不知道如何改变密文中的信息位才能在明文中产生预期的改变MEKEK(M)DKMMM消息认证 消息加密认证---在对称加密体制下v接收方可以根据解密后的明文是否具有合理的语法结构来进行消息认证。
v但有时发送的明文本身并名优明显的语法结构或特征，例如二进制文件，因此很难确定解密后的消息就是明文本身MEKEK(M)DKM消息认证 v根据明文M和公开的函数F产生FCS，即错误检测码，或帧校验序列，校验和v把M和FCS合在一起加密，并传输v接收端把密文解密，得到Mv根据得到的M，按照F计算FCS，并与接收到的FCS比较是否相等MFFMFCS比较EKDKMFCS内部错误控制消息认证 110101 ← Q (商) P (除数) → 1101 101001000 ← 2nM (被除数) 1101 1110 1101 0111 0000 1110 1101 0110 0000 1100 1101 001 ← R (余数)，作为 FCS FCS的原理说明 M = 101001消息认证 MFFCSEKDKM外部错误控制F比较消息认证 消息加密认证---在公钥加密体制下MEKUbEKUb(M)DKRbMI. 普通加密ABMM消息认证 消息加密认证---在公钥加密体制下v由于只有A有用于产生EKRa (M)的密钥，所以此方法提供认证。
MEKRaEKRa (M)DKUaMII. 认证和签名ABMM消息认证 消息加密认证---在公钥加密体制下v提供认证和加密v一次通信中要执行四次复杂的公钥算法MEKRaEKUb (M)DKUaMIII. 加密认证和签名ABEKUbEKRa(EKUb (M))DKUaEKRa (M)消息认证 把加密与认证分开vThere are a number of applications in which the same message is broadcast to a number of destinations. vThe receiver has a heavy load and cannot afford the time to decrypt all incoming messages. vFor some applications, it may not be of concern to keep messages secret, but it is important to authenticate messages. vSeparation of authentication and confidentiality functions affords architectural flexibility. 消息认证 5.3 消息认证码(MAC)vMessage Authenticaion Codev消息认证码是消息和密钥的公开函数，它产生定长的值，以该值作为认证符。
v利用密钥和消息生成一个固定长度的短数据块，并将其附加在消息之后v通信双方共享密钥K消息认证 vA MAC, also known as a cryptographic checksum(密码校验和) , is generated by a function C of the form：MAC = C(K, M)vWhere：M is a variable-length messageK is a secret key shared only by sender and receiverMAC is the fixed-length authenticator. vThe MAC is appended to the message at the source at a time when the message is assumed or known to be correct. vThe receiver authenticates that message by recomputing the MAC.消息认证 消息认证码用于认证vA和B共享密钥KvA计算MAC=Ck(M),vM和MAC一起发送到BvB对收到的M，计算MAC，比较两个MAC是否相同。
MCMACKC比较KMAC如果两个MAC相等，则：1.接收方可以相信消息未被修改，因为如果攻击者改变了消息，由于不知道k，无法生成正确的MAC2.接收方可以相信消息的确来自确定的发送方因为其他人不能生成和原始消息相应的MAC消息认证 MAC函数与加密函数的区别vMAC函数与加密函数类似，都需要明文、密钥和算法的参与v但MAC算法不要求可逆性，而加密算法必须是可逆的v例如：使用100比特的消息和10比特的MAC，那么总共有2100个不同的消息，但仅有210个不同的MAC也就是说，平均每290个消息使用的MAC是相同的v因此，认证函数比加密函数更不易被攻破，因为即便攻破也无法验证其正确性关键就在于加密函数是一对一的，而认证函数是多对一的消息认证 消息认证码的基本用途v只提供消息认证，不提供保密性见前）v提供消息认证和保密性：M||CK1CMCK(M)K1比较EK2DK2ABA和B共享K1和K2K1：用于生成MACK2：用于加密与明文有关的认证消息认证 消息认证码的基本用途v提供消息认证和保密性：ABA和B共享K1和K2K1：用于生成MACK2：用于加密与密文有关的认证M||CK1CK1比较EK2DK2消息认证 5.3.2 消息认证码的安全性v攻击密钥v攻击算法消息认证 对MAC的攻击—攻击密钥v已知消息M1和MAC算法C，以及MAC1 = C k1 (M1) ，现要破解k1。
密钥为k个bit，MAC为n个bitv当k>nk>n：： 可能的密钥个数为2k可能的MAC个数为2n个 所以许多不同的密钥(约2k-n个)，计算出来的MAC都等于MAC1这些密钥中哪一个是正确的密钥不得而知这时需要新的M-MAC对来测试这2k-n个密钥，于是有如下的重复攻击：消息认证 重复攻击vStep 1:给定M1和MAC1 = C k1 (M1) 对所有2k个密钥，判断MACi = C ki (M1) 匹配数约为： 2k-n vStep 2:给定M2和MAC2 = C k2 (M1)对所有2k个密钥，判断MACi = C ki (M2)匹配数约为： 2k-2n v平均来讲，若k=x*n，则需x次循环才能找到正确的密钥v所以，用穷举法攻破MAC比攻破加密算法要困难得多消息认证 对MAC的攻击—攻击算法v考虑下面的算法： 消息M=(X1‖X2‖…‖Xm)是由64比特长的分组Xi(i=1,…,m)链接而成 MAC算法是： 加密算法是DES因此，密钥长为56比特 如果敌手得到M‖CK(M)，那么敌手使用穷搜索攻击寻找K将需做256次加密。
很困难!v但攻击者可以改变M的内容，却使MAC正确 方法如下：消息认证 v用Y1替换X1 ， Y2替换X2 ，…， Ym替换Xm ，其中Y1 ，Y2 ， … ，Ym 是攻击者编造的假消息且 Ym = Y1 Y2 … Ym-1 Δ(M)， v当接收者收到这个消息： M’=(Y1‖Y2‖…‖Ym) 则Δ(M’)= Y1 Y2 … Ym = Δ(M)所以：CK(M)=CK(M’) 通过了验证，攻击得逞消息认证 MAC函数应具有的性质v若攻击者已知M和CK(M)，则他构造满足： CK(M)=CK(M’)的消息M’在计算上不可行vCK(M)应是均匀分布的，即对于随机消息M和M’， CK(M)=CK(M’)的概率是2-n，n是MAC的位数v若M’是M的某个变换，即M’=f(M)，那么Pr[CK(M)=CK(M’)]= 2-n 消息认证 5.3.3 基于DES的消息认证码 Message Authentication Code Based on DES v使用最广泛的MAC算法之一：数据认证算法v过程：把需要认证的数据分成连续的64位的分组。
若最后一个分组不是64位，则填0利用DES加密算法E和密钥K，计算认证码消息认证 消息认证 数据认证算法似乎可以满足前面提出的要求DAC M-bits(16 to 64 bits)消息认证 5.4 Hash函数(杂凑函数、散列函数)vHash的特点：与消息认证码一样，hash函数的输入是可变的消息M，输出是固定大小的hash码H(M) ，或称消息摘要(Message Digest) 、hash值与消息认证码不同的是， hash码的产生过程中并不使用密钥Hash码是所有消息的函数，改变消息的任何一位或多位，都会导致hash码的改变Hash算法通常是公开的又称为：哈希函数、数字指纹（Digital finger print)、压缩（Compression)函数、紧缩（Contraction ）函数、数据鉴别码DAC（Data authentication code）、篡改检验码MDC(Manipulation detection code)消息认证 h=H(M) v假定两次输入同样的数据，那么散列函数应该能够生成相同的散列值输入数据中的一位发生了变化，会导致生成的散列值完全不一样。
v散列函数有个非常重要的特性为单向性，也就是从M计算h容易，而从h计算M不可能 消息认证 消息认证 消息认证 消息认证 消息认证 方法e的优点v不含加密处理加密软件很慢加密硬件的开销很大加密硬件是对大长度数据进行优化的加密算法可能受专利保护加密算法可能受出口的限制.消息认证 对对HASH函数h = H(M)的要求的要求1.H can be applied to a block of data of any size.2.H produces a fixed-length output.3.H(x) is relatively easy to compute for any given x, making both hardware and software implementations practical.4.For any given value h, it is computationally infeasible to find x such that H(x) = h. This is sometimes referred to in the literature as the one-way property（单向性）.消息认证 对对HASH函数h = H(M)的要求的要求5.For any given block x, it is computationally infeasible to find y≠x such that H(y) = H(x). This is sometimes referred to as weak collision resistance（弱碰撞性）（弱碰撞性）.6.It is computationally infeasible to find any pair (x, y) such that H(x) = H(y). This is sometimes referred to as strong collision resistance （强碰撞性）（强碰撞性）.消息认证 v前三条要求具有实用性v第4条是单向性质，即给定消息可以产生一个散列码，而给定散列码不可能产生对应的消息v第5条性质是保证一个给定的消息的散列码不能找到与之相同的另外的消息。
即防止伪造v第6条是对已知的生日攻击方法的防御能力,强无碰撞消息认证 Hash与MAC的区别vMAC需要对全部数据进行加密vMAC速度慢vHash是一种直接产生认证符的方法vHash可用于数字签名消息认证 5.4.3 常用Hash算法 消息认证 迭代型hash函数的一般结构fffY0Y1YL-1bbbnnnnnIV=CV0CV1CVL-1CVL明文M被分为L个分组Y0,Y1,…,YL-1b:明文分组长度n:输出hash长度CV：各级输出，最后一个输出值是hash值无碰撞压缩函数f是设计的关键消息认证 迭代型hash函数v这种结构的hash函数已被证明是合理的，如果采用其他结构，不一定安全v设计新的hash函数只是改进这种结构，或者增加hash码长v算法的核心技术是设计无碰撞的压缩函数f，而敌手对算法的攻击重点是f 的内部结构，由于f 和分组密码一样是由若干轮处理过程组成，所以对f 的攻击需通过对各轮之间的位模式的分析来进行，分析过程常常需要先找出f 的碰撞由于f 是压缩函数，其碰撞是不可避免的，因此在设计f 时就应保证找出其碰撞在计算上是不可行的消息认证 MD5 hash算法MD5 Hash Algorithm MD4是MD5杂凑算法的前身，由Ron Rivest于1990年10月作为RFC提出，1992年4月公布的MD4的改进（RFC 1320，1321）称为MD5。
消息认证 MD5的算法框图v输入消息可任意长，压缩后输出为128bits消息认证 算法步骤(1)－分组填充 消息100…064bit消息长度填充图样L×512bitKbitv如果消息长度大于264，则取其对264的模v执行完后，消息的长度为512的倍数（设为L倍），则可将消息表示为分组长为512的一系列分组Y0，Y1，…，YL-1，而每一分组又可表示为16个32比特长的字，这样消息中的总字数为N=L×16，因此消息又可按字表示为M[0,…,N-1]消息认证 算法步骤(2)－缓冲区初始化 hashhash函函数数的的中中间间结结果果和和最最终终结结果果保保存存于于128128位位的的缓缓冲冲区区中中，，缓缓冲冲区区用用3232位位的的寄寄存存器器表表示示可可用用4 4个个32bits32bits字字表表示示：：A A, ,B B, ,C,DC,D初初始始存存数数以以十十六进制表示为六进制表示为A A=01234567=01234567B B=89=89ABCDEFABCDEFC C==FEDCBAFEDCBA9898D D=76543210=76543210消息认证 算法步骤(3) -HMD5运算v以分组为单位对消息进行处理每一分组Yq(q=0,…,L-1)都经一压缩函数HMD5处理。
HMD5是算法的核心，其中又有4轮处理过程vHMD5的4轮处理过程结构一样，但所用的逻辑函数不同，分别表示为F、G、H、I每轮的输入为当前处理的消息分组Yq和缓冲区的当前值A、B、C、D，输出仍放在缓冲区中以产生新的A、B、C、Dv每轮又要进行16步迭代运算，4轮共需64步完成v第四轮的输出与第一轮的输入相加得到最后的输出消息认证 消息认证 压缩函数中的一步迭代消息认证 基本逻辑函数定义 轮基本函数gg(b, c, d)fFF( b,c,d)( b^c)V(b¯^d)fGG( b,c,d)( b^d)V(c^ d¯)fHH( b,c,d)b Å c Å dfII( b,c,d)c Å ( b V d¯)消息认证 X[k]v当前分组的第k个32位的字第1轮 x[0] x[1] x[2] x[3] x[4] x[5] x[6] x[7] x[8] x[9] x[10]x[11]x[12]x[13]x[14]x[15]第2轮 x[1] x[6] x[11] x[0] x[5] x[10]x[15] x[4] x[9] x[14] x[3] x[8] x[13] x[2] x[7] x[12]第3轮 x[5] x[8] x[11]x[14] x[1] x[4] x[7] x[10]x[13] x[0] x[3] x[6] x[9] x[12]x[15] x[2]第4轮 x[0] x[7] x[14] x[5] x[12] x[3] x[10] x[1] x[8] x[15] x[6] x[13] x[4] x[11] x[2] x[9]消息认证 T[i]vT[1,…,64]为64个元素表，分四组参与不同轮的计算。
T[i]为232×abs(Sin(i))的整数部分，i是弧度T[i]可用32 bit二元数表示，T是32 bit随机数源消息认证 T[1]= d76aa478T[17]= f61e2562T[33]= fffa3942T[49]= f4292244T[2]= e8c7b756T[18]= c040b340T[34]= 8771f681T[50]= 432aff97T[3]= 242070dbT[19]= 265e5a51T[35]= 6d9d6122T[51]= ab9423a7T[4]= c1bdceeeT[20]= e9b6c7aaT[36]= fde5380cT[52]= fc93a039T[5]= f57c0fafT[21]= d62f105dT[37]= a4beea44T[53]= 655b59c3T[6]= 4787c62aT[22]= 02441453T[38]= 4bdecfa9T[54]= 8f0ccc92T[7]= a8304613T[23]= d8a1e681T[39]= f6bb4b60T[55]= ffeff47dT[8]= fd469501T[24]= e7d3fbc8T[40]= bebfbc70T[56]= 85845dd1T[9]= 698098d8T[25]= 21e1cde6T[41]= 289b7ec6T[57]= 6fa87e4fT[10]= 8b44f7afT[26]= c33707d6T[42]= eaa127faT[58]= fe2ce6e0T[11]= ffff5bb1T[27]= f4d50d87T[43]= d4ef3085T[59]= a3014314T[12]= 895cd7beT[28]= 455a14edT[44]= 04881d05T[60]= 4e0811a1T[13]= 6b901122T[29]= a9e3e905T[45]= d9d4d039T[61]= f7537e82T[14]= fd987193T[30]= fcefa3f8T[46]= e6db99e5T[62]= bd3af235T[15]= a679438eT[31]= 676f02d9T[47]= 1fa27cf8T[63]= 2ad7d2bbT[16]= 49b40821T[32]= 8d2a4c8aT[48]= c4ac5665T[63]= eb86d391消息认证 CLSs ：循环左移s位v第一轮：7、12、17、22v第二轮：5、9、14、20v第三轮：4、11、16、23v第四轮：6、10、15、21消息认证 MD-5的安全性vMD-5的输出为128-bit，若采用纯强力攻击寻找一个消息具有给定Hash值的计算困难性为2128，用每秒可试验1 000 000 000个消息的计算机需时1.07×1022年。
v采用生日攻击法，找出具有相同杂凑值的两个消息需执行264次运算消息认证 碰撞v如果两个输入串的hash函数的值一样，则称这两个串是一个碰撞碰撞(Collision)既然是把任意长度的字符串变成固定长度的字符串，所以，必有一个输出串对应无穷多个输入串，碰撞是必然存在的v 2004年8月17日，美国加州圣巴巴拉正在召开国际密码学会议，山东大学王小云教授公布了快速寻求MD5算法碰撞的算法 消息认证 SHA 算法Secure Hash Algorithm消息认证 算法简介v美国标准与技术研究所美国标准与技术研究所NISTNIST设计设计v19931993年成为联邦信息处理标准年成为联邦信息处理标准(FIPS PUB 180)(FIPS PUB 180)v基于基于MD4MD4算法，与之非常类似算法，与之非常类似v输入为小于输入为小于2 26464比特长的任意消息比特长的任意消息v分组分组512bit512bit长长v输出输出160bit160bit消息认证 迭代型hash函数的一般结构fffY0Y1YL-1bbbnnnnnIV=CV0CV1CVL-1CVL明文M被分为L个分组Y0,Y1,…,YL-1b:明文分组长度n:输出hash长度CV：各级输出，最后一个输出值是hash值无碰撞压缩函数f是设计的关键消息认证 算法描述v消息填充：与消息填充：与MD5完全相同完全相同v附加消息长度：附加消息长度：64bit长度长度v缓冲区初始化缓冲区初始化A＝＝67452301B＝＝EFCDAB89C＝＝98BADCFBD＝＝10325476E＝＝C3D2E1F0消息认证 分组处理模232加消息认证 SHA-1压缩函数（单步）消息认证 ft ----基本逻辑函数消息认证 vCLS5：32位的变量循环左移5位。
vCLS30：32位的变量循环左移30位消息认证 Wt ---从当前512位输入分组导出的32位字v前16个值（即W0,W1,…,W15）直接取为输入分组的16个相应的字，其余值（即W16,W17,…,W79）取为消息认证 Kt ---加法常量步骤十六进制0≤t≤19Kt=5A82799920≤t≤39Kt=6ED9EBA140≤t≤59Kt=8F1BBCDC60≤t≤79Kt=CA62C1D6消息认证 SHA与MD5的比较v抗穷举搜索能力抗穷举搜索能力寻找指定寻找指定hashhash值，值， SHA SHA：：O(2O(2160160) )，，MD5MD5：：O(2O(2128128) )生日攻击：生日攻击： SHA SHA：：O(2O(28080) )，，MD5MD5：：O(2O(26464) )v抗密码分析攻击的强度抗密码分析攻击的强度SHASHA似乎高于似乎高于MD5MD5v速度速度SHASHA较较MD5MD5慢慢v简捷与紧致性简捷与紧致性描述都比较简单，都不需要大的程序和代换表描述都比较简单，都不需要大的程序和代换表消息认证 v2005年2月15日，在美国召开的国际信息安全RSA研讨会上，国际著名密码学专家Adi Shamir宣布，他收到了来自中国山东大学王小云、尹依群、于红波等三人的论文，论文证明SHA-1在理论上也被破解。
她证明了160位SHA-1，只需要大约269次计算就能找出来，而理论值是280次 消息认证 其它hash算法vMD4 MD4使用三轮运算，每轮16步； MD5使用四轮运算，每轮16步MD4的第一轮没有使用加法常量，第二轮运算中每步迭代使用的加法常量相同，第三轮运算中每步迭代使用的加法常量相同，但不同于第二轮使用的加法常量；MD5的64部使用的加法常量T[i]均不同MD4使用三个基本逻辑函数，MD5使用四个MD5中每步迭代的结果都与前一步的结果相加，MD4则没有MD5比MD4更复杂，所以其执行速度也更慢，Rivest认为增加复杂性可以增加安全性消息认证 RIPEMD-160v欧共体RIPE项目组研制v输入可以是任意长的报文，输出160位摘要v对输入按512位分组以分组为单位处理v算法的核心是具有十轮运算的模块，十轮运算分成两组，每组五轮，每轮16步迭代消息认证 5.4.4 对Hash函数的攻击 v对一个hash算法的攻击可分三个级别：预映射攻击（Preimage Attack）：给定Hash值h，找到其所对应的明文M，使得Hash(M)=h，这种攻击是最彻底的，如果一个hash算法被人找出预映射，那这种算法是不能使用的。
次预映射攻击（Second Preimage Attack）：给定明文M1，找到另一明文M2（M1≠M2），使得hash(M1)=hash(M2)，这种攻击其实就是要寻找一个弱碰撞；碰撞攻击 (Collision Attack)：找到M1和M2，使得hash(M1)=hash(M2) ，这种攻击其实就是要寻找一个强碰撞消息认证 生日攻击v给定一个散列函数H和某和某hash值值H(x)，，假定假定H有n个可能的输出如果H有k个随机输入, k必须为多大才能使至少存在一个输入y,使得H(y)=H(x)的概率大于0.5？？消息认证 结论v如果hash码为m位，则有2m个可能的hash码v如果给定h=H(X)，要想找到一个y，使H(y) =h的概率为0.5，则要进行多次的尝试，尝试的次数k=2m/2=2m-1v所以，对于一个使用64位的hash码，攻击者要想找到满足H(M’)=H(M)的M’来替代M，平均来讲，他要找到这样的消息大约要进行263次尝试v但是，存在一种攻击，称为“生日攻击”，却可以大大减小尝试的次数，对于64位的hash码，所需的代价仅为232次消息认证 生日悖论v一个教室中，最少应有多少学生，才使至少有两人具有相同生日的概率不小于1/2？消息认证 生日悖论v概率结果与人的直觉是相违背的.v实际上只需23人,即任找23人，从中总能选出两人具有相同生日的概率至少为1/2。
消息认证 一个不等式：(1-x)≤e-x (x≥0)当x很小，趋近于0时， (1-x)≈ e-x消息认证 两个集合中元素的重复v给定两个集合X和Y，每个集合有k个元素： X:{x1,x2,…,xk}, Y:{y1,y2,…,yk},v其中，各元素的取值是1~n之间的均匀分布的随机值(k 这太困难了！消息认证 v设M和hash算法生成64位的hash值v攻击者可以根据M，产生232个表达相同含义的变式(例如在词与词之间多加一个空格)v同时准备好伪造的消息M’，产生232个表达相同含义的变式v在这两个集合中，找出产生相同hash码的一对消息M1和M1’根据生日悖论，找到这样一对消息的概率大于0.5v最后，攻击者将拿M1给发送者签名，但发送时，把M1’和经加密的hash码一起发送消息认证 Birthday Attacks: examplevA准备两份合同M和M′ ，一份B会同意，一份会取走他的财产而被拒绝vA对M和M′各做32处微小变化(保持原意),分别产生232个64位hash值v根据前面的结论,超过0.5的概率能找到一个M和一个M′,它们的hash值相同vA提交M,经B审阅后产生64位hash值并对该值签名,返回给AvA用M′替换M消息认证 掷币v两个朋友Alice和Bob想在晚上一起外出，但是他们定不下是去电影院还是歌剧院于是，他们达成了一个通过掷硬币来决定的协议vAlice拿着硬币对Bob说：“你选择一面，我来抛”Bob选择后，Alice把硬币抛向空中然后他们都注视硬币，如果Bob选择的那一面朝上，则他可以决定要去的地方，否则由Alice决定。 消息认证 假如两人在两端vAlice对Bob说：“你选一面，我来抛，然后我告诉你你是否赢了”vBob会同意吗？v如何解决？消息认证 提示v引入一个函数，我们暂时称它为奇妙函数,它具有下面的特点 对于任意整数x，由x计算f(x)是容易的，而给出f(x)，计算x是不可能的 不可能找出一对整数（x,y），满足x≠y且f(x)=f(y)消息认证 解决方法v两个朋友达成一致，使用奇妙函数f用偶数表示正面，用奇数表示反面vAlice任意选择一个大随机数x并且计算f(x),然后通过告诉Bob f(x)的值vBob告诉Alice自己对x的奇偶性猜测vAlice告诉Bob她选择的x的值vBob验证f(x)并察看他的猜测是否正确消息认证 随机选择一个整数M奇数代表正面，偶数代表反面Hh=H(M)无法从h推出M，只能猜M的奇偶性HMh=H(M)验证消息认证 。
