密码学—数学的勾心斗角刚考完热热还能看？No.65148341 只看PO
2025-01-30(四)15:06:53 ID:kdXdPyz 回应
（过年走亲戚有点太无聊了，坐到小孩一桌写一点有的没的打发时间
无标题无名氏No.65157615
2025-01-31(五)17:15:15 ID: kdXdPyz (PO主)
既然信息论安全这么厉害，为什么现在没有广泛应用呢？要达到这种程度的安全，就必须承受相应程度的代价：密钥必须和消息一样长。
这个结论可以从唯一映射要求中推导出来（后文的一切信息都看成二进制串）：因为知道 m 和 c 的情况下，只存在唯一的 k 与之对应，那么只需要固定 c，然后让 m 取不同的值，k 相应的就必须有这么多种不同的取值才能满足需求，这就要求 k 和 m 的长度要一样。
想象一下，如果你要加密一个 1G 的图片，必须事先安全的交换 1G 的密钥才能保证此加密的有效性，这显然是不可接受的。我们日常中习以为常的用一个短一点的密钥去加密长的消息，在这里是可能实现的吗？
很遗憾，如果密钥长度变小，密文解密的空间就一定会变小，那么就一定导致在得知密文下的明文的概率不同于明文本身的概率，这就不满足我们构想的信息论安全的定义了。
我们使用密码学的名词总结一下：能够达到信息论安全的加密方案称为“完善保密加密”，它的效果是密文的分布和明文的分布是完全没有关系的。
无标题无名氏No.65159839
2025-01-31(五)21:45:29 ID: kdXdPyz (PO主)
我知道你很急，你已经迫不及待的想引入“没那么安全的安全”的定义了，但你先别急，因为我们还需要再深入研究一下才能走的更远，因为这个安全定义（明文密文分布没有任何统计关联）并不是很好用。我们引入两个更好用的东西：不可区分性和基于若干交互游戏的证明 (Game-based Proof)
> 不可区分性（IND，indistinguishability）
什么是不可区分？不可区分就是两个本来不同的东西，加工之后没有能力分辨出来哪个是哪个。写成公式就是这样：对于任意给定的 c 和 k，任意两个 m 和 m' 有 Pr[Enc_k(m)=c] = Pr[Enc_k(m')=c] 始终成立。这个和之前的公式是等价的，称为“完美不可取分”。
等价的推导可以这么想（可略过）：猜对的概率根据信息论安全的结论都是 1/（k 空间的大小），也就相等了。反推回去也容易，对于所有可能的 m 概率都相等了，总的概率又是 1，所以每种情况的概率刚好就是 1/(m 空间的大小) ，这个结论对于和 c 一点关系都没有，所以 c 的分布与 m 独立。
我们也可以换一种思考方式去思考这个式子：如果我们拿到了 c，去猜测 m 是什么，不管用什么方法去猜，先猜这个或者通过某种计算得到某种猜测的顺序，能够猜正确的概率永远和乱猜是一样的。
> 敌手最好的方法就是乱猜
这就是不可区分所传达的核心信息。这里谈到了“敌手”，我们有没有办法去规范化、数学化这句话呢？这就到了 Game-base Proof 大显身手的时候了：
我们需要构造基于一个敌手 A（Attacker）的 Game，形式化定义 A 的能力：不能区分密文来自于那个明文的加密，
我们让 A 主动选择两个信息 m0 m1 交给我们，然后我们 roll 一个 r0[0,1] 作为 b，再 roll 一个密钥 k 加密对应下标的 m 发送回去（0 就发 m0,1 就发 m1），敌手要猜我们加密的是哪个信息，发送回来另一个 b‘ （挑战），如果猜对了就算 A 赢了。
如果敌手在游戏中获胜的概率严格等于二分之一，则称这个加密方案具有敌手不可取分性。这可以等价于上文的完美不可取分，证明不难读者自证 (` ゥ´ )
Game 中“我们”的角色在密码学领域有一个专有名词，叫做“预言机”（Oracle）。之所以叫这个名字是因为在证明当中它的能力一般都是天花板，没啥限制 ( ﾟ∀。)7" 上文的 Game 规范的流程给我们在现实中的攻击和防守方找到了一个非常有用的数学证明框架，给我们下文更加现实的加密方案铺平了道路。
至此，完善保密加密的部分算是结束了。但是在进入对称加密的世界之前，我们还需要掌握一些必要的知识……
无标题无名氏No.65160546
2025-01-31(五)23:11:03 ID: tvCQs1g
昨天晚上借着po的文章与ai相互服用习得了好多知识( ﾟ 3ﾟ)( ﾟ 3ﾟ)( ﾟ 3ﾟ)亲亲亲