【乐正垂星】恺撒密码，完美加密，与现代密码学初探——乐正垂星
🔗资源链接
【乐正垂星】恺撒密码，完美加密，与现代密码学初探_哔哩哔哩_bilibili
✍我的笔记
第一部分：密码学的两个时代
- 划分标志：以克劳德·香农 1949 年的论文为界，密码学分为两个阶段。
- 古典密码学：
- 核心：以替换密码（如凯撒密码）为主。
- 特点：历史悠久（2000 年前至今），常出现在解密游戏中。
- 目标：力争让密文没有规律。
- 现代密码学：
- 代表：RSA等充满复杂数学运算的算法。
- 表面现象：似乎与古典密码学完全割裂，从地基到方法全部刷新。
- 核心观点：现代密码学的地基其实是一件被忽略了近 2000 年的简单小事。
第二部分：凯撒密码与完美加密的启示
-
凯撒密码简介：
- 将字母在字母表中前后移动固定位置进行加密。
- 在古代难以破解，在现代则非常脆弱。
-
常见的破解方法：
- 频率分析法：适用于长密文，是所有替换加密的通用破解法。
- 暴力破解法：因为只有 26 种可能，可以轻松试出原文。
-
凯撒密码的安全时刻：
-
当密文非常短（如只有一个单词）时，暴力穷举可能会遇到问题
- 神奇的巧合： 当我们尝试所有 26 种可能的偏移时，会发现一个关键现象：
- 单词 “sleep” 在所有 26 种偏移下所产生的 26 个密文，与单词 “bunny” 在所有 26 种偏移下所产生的 26 个密文，是完全相同的一组字符串。
- 换句话说，{“sleep”的所有可能密文} = {“bunny”的所有可能密文}。
具体来看几个偏移：
- 偏移 3： “sleep” → “vohhs”； “bunny” → “exqqb” （此时密文不同）
- 偏移 20： “sleep” → “hyyzk”； “bunny” → “vohhs” （此时 “bunny” 的密文恰好是 “sleep” 偏移 3 的结果）
- 关键点在于：无论你拿到这 26 个密文中的哪一个，你都无法断定它最初究竟是 “sleep” 还是 “bunny”。例如，当你看到密文 “vohhs” 时，它既可能是 “sleep” 偏移 3 得来的，也可能是 “bunny” 偏移 20 得来的。
-
-
由此得出的核心结论：
-
攻击者的困境：假设你截获了密文 “vohhs”，即便你拥有无穷的计算能力，尝试了所有 26 把密钥，你会发现：
- 用密钥 3 解密，得到 “sleep”。
- 用密钥 20 解密，得到 “bunny”。
- 你没有任何数学上或逻辑上的依据来判断哪一个才是真正的原文。 完美的加密就在此刻发生了。
-
现代密码学的精髓：完美加密并不追求密文本身看起来多么杂乱无章（古典密码学的思路），而是追求让不同的明文所对应的“密文可能性集合”完全重叠。只要攻击者无法从密文中找到任何可以用来区分不同明文的“痕迹”或“区别”，那么这套方案就是绝对安全的。
-
关键例子：单词 “sleep” 和 “bunny” 经过不同的凯撒偏移后，可以产生相同的密文。
-
核心困境：如果我们只拿到这个密文，将无法判断它究竟是由 “sleep” 还是 “bunny” 加密而来。
-
结论：当不同的明文（如sleep和bunny）经过加密后，能产生完全相同的密文集合时，加密就是安全的。因为攻击者无法从密文中找到任何区别来还原明文。
-
-
现代密码学的核心思想：
- 完美加密不依赖密文没有规律，而依赖于不同的明文产生的密文之间没有区别。
- 如果只看密文，无法区分它来自哪个明文，那么这就是完美加密。
- 实践方案：对文本中的每个字母独立地、随机地使用凯撒密码进行加密（即使用与明文等长的随机密钥）。这样，任何明文都能被加密成任何等长的密文，从而实现绝对安全。这套方案被称为 “单次密码簿”
第三部分：加密方案的通用框架与困境
-
加密方案的组成：
- 多对加密算法和解密算法。
- 密钥生成：从这些算法对中随机挑选一个的过程（在凯撒密码中，密钥就是偏移量）。
-
完美加密的要求：
- 必须让不同的明文生成的密文找不到任何区别。
- 这是现代密码学相比古典密码学（目标是让密文没规律）最大的思想转变。
-
单次密码簿的缺陷：
- 密钥过长：密钥长度必须等于明文长度。
- 密钥分发难题：如果能安全地分发密钥，那为什么不直接发送消息本身？这导致了“能用的加密方案不安全，安全的加密方案不能用”的尴尬局面。
-
对完美加密的拓展思考：
- 明文和密文不限于文本，可以是任何格式（如二战时用针织图案传递情报）。
- 任何一种编码都可以看作加密系统，只是大多数只有一套方案，毫无安全性。
第四部分：单向函数与公钥加密——向现实的妥协
-
新的思路：既然完美加密不实用，能否找到一种函数，使得根据输出反推输入极其困难？
- 这种函数被称为单向函数。
- RSA算法的加密步骤就被认为可能是一种单向函数。
-
公钥加密的原理：
- 问题：如果加密是单向的，那么合法的接收者也无法解密。
- 解决方案：在单向函数中设置一个“暗门”（Trapdoor）。掌握暗门的人可以轻松解密，而对于没有暗门的人来说，破解的难度不亚于暴力穷举。
- 公钥与私钥：公开的单向函数就是公钥，私有的“暗门”就是私钥。
-
两种加密的核心理念对比：
- 私钥加密（如单次密码簿）：安全性建立在密钥的随机性上，理论上绝对安全。
- 公钥加密（如RSA）：安全性建立在人类当前算力和智力的局限上，理论上可破解，但实际上不可行。
第五部分：后记与现代密码学的精神
- 现代密码学的丰富内涵：还包括伪随机数、零知识证明、哈希函数等。
- 共同核心：所有这些技术的目标都是在达成特定目标（如身份验证、交易）的同时，不泄露任何额外信息。