为什么底层概念不放在第一章#

其实，这本书开篇并不是讲的上述这些概念。相反，关于伪随机数的概念是放在的第三章才正式引入，而第一章 Introduction and Classical Ciphers 是简单引入，第二章 Perfectly-Secret Encryption 讲的是理论上的完美安全。

那为什么底层概念不放在第一章直接开讲？因为数学上的可证明安全性，和实际情况下的安全性，是两码事。伪随机数，严格来说是有了计算机科学需求才引入的概念，本身在 cs 领域是没有的——这一点接下来会讲。

完美保密：Perfectly-Secret Encryption#

（在这里我只是简要概括核心，最准确的定义建议回归原文查看）在密码学里面，对于一个特定的加密算法，也就是单向函数来说，是输入对应输出，而输入的就是明文 + 密钥（为什么不是一个明文就可以，具体原因参考香农定理）。

理论上，在加密数据过程中，明文密钥长度一样才可以保证绝对安全。但是实际情况下，密钥长度过长，计算复杂度会急剧上升，这就导致：如果想要对 1G 明文加密，实际情况下用 1G 的密钥纯属扯淡。（举个可能不太合适的例子：假如甲乙两地相距只有 50km，你坐车过去不好，非要坐飞机——举这个是因为实在想不出合适的 qwq）

计算安全：Computational Security#

那么这个时候可能就有人要问了：既然你实际情况下密钥不能过长，如何保证安全？这就要扯到计算安全了，全称 Computational Security。

此时如果我们不去限制黑客算力，给足足够长的时间，理论上暴力穷举是肯定可以攻破的。但是问题在于实际情况下，限制黑客算力为多项式时间——那么只需要黑客在 PPT，也就是多项式时间内，不能做到攻破得到明文，那么我们就说此时是计算安全的（PPT 的准确定义建议回归上述教科书自行查看）。

伪随机性：PRG 与语义安全#

但是此时还是有一个问题：在理论数学层面，根据香农定理，一个绝对安全的算法，其对应密钥在理论层面一定是完全随机的，只有这样才能确保黑客在多项式时间内无法攻破。但是实际情况下，我们不妨想想：这里这个密钥真的可以做到完全随机吗？

答案肯定是否定的。此时我们就必须引入伪随机数了。实际上，一个极短的、真正的随机种子 seed，理论上通过伪随机数生成器，也就是 PRG（全称 Pseudorandom generators），可以生成对应的伪随机数序列：输入空间大小是 2 的 n 次方，输出空间大小是 2 的 ℓ(n) 次方。

但是聪明的你用一点点统计学的知识就会知道：因为 ℓ(n) > n，所以这意味着 PRG 只能生成所有可能的字符串中的很小一部分——理论上数量很多，但是实际情况下大部分伪随机数都是不会出现的，也就是在实际情况下的数量其实是小于理论数量的（具体证明过程详见教科书）。

那怎么办嘞？这个时候聪明的你又想到了一个办法：把 n 取到一个合适的程度不就行了？使得最终生成的伪随机序列和真正的随机序列不可分。这里教材的严格定义是：

语义安全定义：攻击者通过密文猜出明文任意一位比特的优势可以忽略不计，仅比随机猜测的概率 1/2 高可以忽略的程度。也就是，给攻击者提供伪随机序列和真正的随机序列，只要猜中伪随机数的概率只比 1/2 高一点点就可以了。

具体地，在教材里面还有一个不可区分性实验：也就是加密方案在唯密文攻击下具有安全性，即密文不会泄露任何有关明文的信息，也就是无法区分密文（具体的严格定义见教材原文）。

其实，在我看来，此处的核心思想内容其实和上述语义安全有异曲同工之妙。

总之，以上只是我个人关于一些底层概念的自我思考，内容难免有不严谨或者细节有误的地方，也诚恳地欢迎各位老师进行指点！

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