桂电密码学准大二 | 关于密码学底层概念：MAC，抗碰撞哈希与单向函数#

大家好，我是一名桂电准大二学生，目前就读于密码学，书接上文，上次看了Katz老师的密码学原理与协议，浅要探讨了前三章计算安全与伪随机性的相关概念，最近正继续往前推进，了解了一些其它概念的相关定义与联系，把相关底层逻辑进行了梳理，在此分享一下自己的见解。

首先，书中从第四章开始，便探讨的MAC以及抗碰撞函数，MAC的概念在前面，为什么要引入这个概念呢？因为第三章主要探讨的一些底层的必要概念，而像单向函数以及相关底层construction是绝对的底层数学层面的proof,主要是在后续章节详细阐述，第三章的PRG与PRF相当于是作为一个默认假设的已有的前提，这个前提则是MAC与抗碰撞的基础，同时引入安全通信的基础概念，说明在实际的通信中为什么一定需要MAC，相当于是与应用层做的一个衔接。

由此，既然是在安全通信中，请大家先想想，我们设想一个场景，在正常https协议加密过程中，先建立连接，经历TCP三次握手，CA证书+数字签名进行身份认证，非对称加密协商共享密钥后，就是对称加密传输数据了，去网上查肯定也是这个回答，这本身没问题，而MAC主要是在对称加密这里会用到。问题在于，如果只是传输数据，理论上只需要加密就可以了，为什么需要MAC呢？

事实上，如果只是想要传输数据，只用对称加密百分百没问题，问题在于我们实际情况下，不只想要数据安全传输，因为数据加密是前提，但是如何确认这个数据一定来自通信双方呢？假如A向B欠了100元钱，写了借条，那如何证明这个借条在传输过程中相关内容没有被篡改？这个就需要MAC了。

首先，我们来看一下MAC的定义（全称message authentication code）：

DEFINITION 4.2 A message authentication code Π = (Gen, Mac, Vrfy) is existentially unforgeable under an adaptive chosen-message attack, or just secure, if for all probabilistic polynomial-time adversaries A, there exists a negligible function negl such that:

Pr[Mac-forge_{A,Π}(n) = 1] ≤ negl(n)

此处existentially unforgeable意思是存在性不可伪造，意思是敌手无法伪造出一个有效的消息，MAC可以保证消息的完整性，不过无法保证不可否认性，至于公式则是数学层面的严谨论证，表示在教材对应的伪造实验中，敌手成功的概率，小到可以忽略（此处这个实验我感觉和第三章里面的很像），因此我们可以借助MAC去保证，并且因为带有密钥，跟哈希函数还是有区别的，只是说好像也是从PRF衍伸出来的（当然此处其实描述的很简略，Katz老师这本书描述写的很严谨，此处考虑文章篇幅和我自己的理解程度，没有去深究，严谨相关实验和推论参考原教材）。

其次便是抗碰撞哈希函数了，先说哈希函数，这个其实很好理解，也就是生成固定长度的摘要，保证数据完整的来源，和PRG有类似之处，但是输入输出空间大小是反着的，因此理论上其实是存在碰撞的，那为什么说抗碰撞呢？这里是因为碰撞存在，但是找到很难，意思是数学层面理论存在碰撞，但是实际计算量极大，因此名字也叫做抗碰撞（achievable）。

此处教材里面的严谨定义是：

DEFINITION 4.10 A hash function Π = (Gen, H) is collision resistant if for all probabilistic polynomial-time adversaries A there exists a negligible function negl such that:

Pr[Hash-coll_{A,Π}(n) = 1] ≤ negl(n)

同样限于篇幅，最严谨的内容建议回归相应教材查看，同时教材里面还有个很有意思的对比，针对抗原像/单向，也就是Preimage resistance来说，因为是单向函数，所以强度最低，针对抗第二原像，也就是Second preimage resistance,给定 x，找 x’ 撞固定的 x,强度中等,而对于抗碰撞哈希函数，也就是Collision resistance,强度是最大的，敌手也越难攻破。

最后便是单向函数了，也就是one-way function,（这个是在第六章，中间有第五章分组密码相关内容，但由于我主攻是非对称，所以目前这块只看了最重要的概念定义就跳读过去了）其实我在想单向函数和PRG作为密码学最底层的几大概念之一，为什么不放在前面的章节就讲了，后面看第六章发现，本篇Katz老师用了大量数学上的严谨语言去进行安全性证明，也就是安全规约，并且,PRG和PRF两者其实也是可以从单向函数推导出来的，只是由于推导过程太过复杂（至少对现在的我来说），因此下放到了第六章，而第三章里面则是直接把PRG与PRF当成前提了，这样子可能对读者也比较友好。

扯的有点远了，回归正题，众所周知，非对称算法和对称算法底层都是单向函数，这个很好理解（严格来说前者基于数学困难性问题，后者基于伪随机性），只是关于安全规约的证明对我来说实在是过于复杂，因此这里直接放上定义了：

DEFINITION 6.1 (one-way functions): A function f : {0,1}* → {0,1}* is called one-way if the following two conditions hold:

1. Easy to compute: There exists a polynomial-time algorithm M_f such that on input any x ∈ {0,1}*, M_f outputs f(x) (i.e., M_f(x) = f(x) for every x).

2. Hard to invert: For every probabilistic polynomial-time inverting algorithm A, there exists a negligible function negl such that:

Pr[A(f(x)) ∈ f⁻¹(f(x))] ≤ negl(n)　(6.1)

where the probability is taken over the uniform choice of x in {0,1}^n and the random coin tosses of A.

几个条件总结下来单向函数特点就是：在PPT内可以正向算出f（x）,反向计算出结果的概率不大于negl(n)，其实单向函数比较贴合实际，我自己觉得这个也比较好理解。

（当然我自己也只是研究了一下核心概念的定义，以及一些基础的证明实验，对于相关严格证明过程目前确实不在我能力和精力范围内，并且文章也写得比较浅，难免有细节疏忽，关于细节部分，各位读者要是有相关需求还是建议回归教材）

总之，以上只是我个人学习过程中的一些自我概念思考和辨析，如果有关键细节或者理解缺失，也恳求各位老师及时指出，我感激不尽！

原文发布于知乎（2026-08-19），收录于《桂电密码学本科生的密码学学习笔记》系列，作者：亦梦。