类似于通信中的校验码功能，在密码学领域数据完整性用于验证收到信息的正确性，校验收到的信息是否经过篡改，校验收到的信息是真实的发送者发送而非伪造。发送者通过编码为消息增加一些“冗余”，生成一个校验值，并将该校验值附在消息之后。接收者根据协商好的规则，利用附加的校验值来检测接收到消息的正确性。
使用分组加密构造keyed hash函数，选择CBC模式，密钥为k，每一块加密函数为Ek(m)：
将(IV, H(t))作为MAC；
说明：
CBC-MAC是一个单向变换，不可求其逆数据：因为MAC里面包含的只是分组加密得到的最后一块H(t)与IV，根据CBC的加密解密流程：无论是接收者还是中间的攻击者都无法根据最后一块H(t)和IV反推出全部的MAC值，因此这是一个单向变换；
生日攻击又称平方根攻击，攻击者利用生日现象，找到冲突的哈希函数值，伪造报文，从而进行攻击。为了实施攻击，攻击者通过计算若干message-hash数值对，直到找到冲突。
【例】
M = (price, description, R), h = h(price, description, R)
M1 = (price1, description, R1), h1 = h(price1, description, R1)
M ≠ M1, h = h1, use (M1 || h1) to forge(M || h)
生日攻击：攻击者计算 2|h|/2 的规模即可以一个非常大的概率得到冲突的哈希数值对。
【证明】
假设计算K次，能够找到冲突的哈希数值对的概率为P。
在证明生日攻击这个问题之前，我们回想这样一个简单的问题：一个黑色的盒子里装了N个颜色各不相同的小球，每一次我们摸一个球记录一下它的颜色，再放回去，那么我们摸了K次，都没有摸到重复颜色的球的概率为1-P。
那么K次都是独立的事件：
1−p=(1−12|h|)∗(1−22|h|)∗(1−K−12|h|)
第一次肯定是100%不会相同，第二次只要和第一次颜色不同即可，所以分子是1，第三次要和前两次颜色不同，所以分子是2……以此类推。
回到我们的问题，两者是等同的，在我们的问题中，1-P代表了攻击者计算了K次，仍然还没有找到冲突的哈希数值对的概率（即不同的输入得到了相同的哈希值的情况）。因此，我们继续化简：
密钥建立：
p，q：两个长度差不多的大素数，公钥(N, e)，N=pq，e满足gcd(e, Φ(N))=1，私钥d，满足ed≡1 (mod Φ(N))；
签名生成：
对于消息m∈Z, Alice生成签名s=Sign_d (m)←m^d (mod N)；
验证：
公钥(N,e)，消息m，签名对(m,s)，Bob验证Verify_((N,e) ) (m,s)=true ⇔m≡s^e (mod N)；
密钥建立：
p，q：两个不同的奇素数（p=q=3 mod 4），公钥 N，N=pq，私钥(p, q)；
签名生成：
对于消息m∈Z, Alice生成签名s=m^(1/2) (mod N)；
验证：
公钥N，消息m，签名对(m, s)，Bob验证Verify_((N,e) ) (m,s)=true ⇔m≡s^2 (mod N)；
【例】
