Tips无名氏No.9999999

2099-01-01 00:00:01 ID: Tips

( `д´)现充，杀！杀！杀！

无标题无名氏No.65151083

2025-01-30(四)20:49:02 ID: kdXdPyz (PO主)

> 二战中的密码系统

苏联：老一套多字母替换密码，用多个字母来替换一个字母，后面根据预定的情况不断地变换规则。这些规则可能涉及添加、删除或替换字母。没啥意思不说了

美国：这就有点意思了，电影《风语者》讲的就是这个。纳瓦霍语是一种地球上就那么一点人会说的语言，其语法和发音对于非纳瓦霍人而言也几乎无法学习，他们将常用的军事术语和原始的纳瓦霍词汇对应起来（一对多），然后请活人当编解码器。这么做还真的管用，整个二战期间还没有被破译过。

德国：典型失败案例。采用的是一个名为“enigma”的密码机来加密，长得大概和打字机差不多，按下键盘，加密后的对应字母灯泡就会亮起来。大概的操作方法如下：先用 10 根连接线两头分别插在 26 个洞里（一个洞只能插一根，也就是剩 6 个），然后转动机器上的转盘（转盘上刻度有字母标识，通过密钥可以确定位置）。设定完就可以愉快的敲字了，敲字的时候圆盘会不停的转动。因为转盘与接线的状态很多，所以德国佬很放心，觉得肯定破译不了。知道密码机内部连线泄露给了一个法国情报员也没放在心上。没想到这份情报兜兜转转到了波兰手里，由一名波兰数学家看出端倪了：如果每天的初始设置相同的话，收集大量信息的情况下可以推断出加密机器的内部设置，并逐步破译出加密信息。

英国的情报机构（没错又是他）又招募了一批数学家（图灵也在里面）来破译密码，图灵创新性地提出用机器代替人工的一种可行性方法：炸弹机（Bombe），用来高效率 24 小时无休的破译 enigma。毫无思考能力的机械结构通过巧妙设计，能够完成设定好的计算和逻辑任务，这便是计算机的雏形。

无标题无名氏No.65151379

2025-01-30(四)21:28:47 ID: kdXdPyz (PO主)

为什么有这么多个状态也会被破译？怎么衡量一个加密系统的安全性？说到底啥是安全？有没有能用数学上的东西来说明一下？这就要说回香农了。我想也不必多介绍这位最牛本科生了，他的毕设就是几个学科的基石，他借用了数学上谁也想不到的工具——概率论来描述信息的传递，当然也能够很好的描述加密这种对信息的二次加工的行为。

因为这个对于密码学来说实在太重要了，所以我不得不展示一些数学的公式来精确的描述其含义。下面我们一步步推导，来看看这个安全定义是怎么产生的 | ω・´)

> 安全目标一：敌手不能够得到密钥 k。（如 enigma 机的初始信息和机器状态）

这个安全吗？很明显，这完全不是我们想要的安全。试着想一个最幼稚的置换加密：从后往前写。它甚至没有密钥（或者你硬要说这是步长 -1 的栅栏加密也行），但是这安全吗？显然不行嘛。除了特例，也能这么想：如果有某种方法在不得到 k 的情况下就能得到 m，那么何必绕一圈呢，我直接拿到 m 就行了嘛。

> 安全目标二：给定密文 c，很难恢复整个明文 m

也不大行，如果我需要破译的信息就是敌军攻击的时间，而敌人刚好发送的是“致我最敬爱的上校，如果你能够与我共进晚餐就最好不过了，如果没有时间的话也无妨，顺带一提攻击时间为 1900”，那么你只要解密最后的几个字符就够了。关键在于明文有价值的地方不能简单的假设分布均匀，必须完完整整的保护起来

> 安全目标三：给定 c，很难恢复任何 m 的字符

看起来不错？其实在特定高性能的要求下这个目标确实是一个不错的妥协方案，但是从密码学的角度来说，它还有十足的漏洞：假设我有两个消息，一个是西部战线发过来的 900，一个是从东部战线发过来的 3000。我知道这个加密方法是：c=m+k，这个时候我确实不知道两个的任何一个的时间（任何一个字符），但是我知道西部战线的时间肯定更小一点，那么我就更有必要去防守西部战线。（假设两个消息共用一个 k）

这里的关键在于恢复字符并不是泄露消息信息的唯一方式，可以通过比较，差分，压缩等方法去对信息进行提取和利用，这里就是密文的大小关系泄露了明文的大小关系，从而泄露了关键信息

> 安全目标四：不管攻击者已经掌握了什么信息，密文都不应该泄露任何有关底层明文的额外信息

这个看起来没问题吧？确实，没什么问题。只不过这里的额外信息指的是啥呢？我们的香农同学给出了他的见解：

无标题无名氏No.65151648

2025-01-30(四)21:53:59 ID: kdXdPyz (PO主)

香农提出了两个相当苛刻的要求：（Pr 表示概率）

1. 密钥的均匀性：密钥在它能够选取的范围里被选取到概率是相等的，即对于所有密钥 k∈K，有 Pr[K=k]=1 / (K 的大小)
2. 唯一映射：知道 m 和 c 的情况下，只存在唯一的 k。这意味着每一个明文都能通过唯一的密钥映射到一个密文上，并且没有两个不同的明文能够产生相同的密文

如果满足上面的加密形式，我们就能够（自行）推导出敌手就无法从 c 中获取关于明文的任何额外信息：写成公式就是 Pr[M=m|C=c]=Pr[M=m] ，这说明了

> 明文和密文之间没有任何统计关联，密文是啥完全不影响明文是啥

这就是香农给出的关于“信息论安全”的数学定义，也就是我们前面提到的安全目标四。这看起来就强的不行吧，我们来尝试证明一下一次一密的信息论安全性：

我们假设我们能够在与 m 长度一致的随机 01 字符串中均匀随机的选取k，此时满足第一个要求。m^k=c 等价于 k=c^m ，此时满足第二点，所以满足信息论安全。

信息论安全有多强呢？下面是一个直观理解的例子：有一个方程 x+y=1，x是明文，那么此时x有无限多解，也满足信息论安全。这就是理论上不可破解（实际上也当然不可破解）。国际上的“通电话”用的热线加密用的方法就是这个玩意。

无标题无名氏No.65157470

2025-01-31(五)16:53:54 ID: kdXdPyz (PO主)

>>No.65153555
很好很直观的解释( ´ρ`)

无标题无名氏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.65162983

2025-02-01(六)10:53:16 ID: kdXdPyz (PO主)

>>No.65160528
这个感觉是后人对系统安全性的高度概括？(>д<)总之我还是从我课程的大概顺序讲下来吧

无标题无名氏No.65162987

2025-02-01(六)10:53:50 ID: kdXdPyz (PO主)

(　ﾟ 3ﾟ)亲亲

无标题无名氏No.65163970

2025-02-01(六)13:05:42 ID: kdXdPyz (PO主)

我们开始谈谈现实的一些东西

> 高熵、均匀一致和随机

熵是啥？物理学家借统计学家的口吻说，熵是一种衡量混乱度的值。香农提出的信息熵也借鉴了这个概念，信息熵越高，表示信息所含有的不确定性越大，可能性越多（某种意义上也是混乱度），也越难预测。

均匀一致是什么？指的是事后统计数据（事前的概率往往在现实中只是我们的一厢情愿，我们最实际的情况只能得知频率，概率则是通过数学模型假设后推导出来的），每一个情况发生的频率都相等。

那么，一个均匀一致的序列发生器（不断向外部吐出 01 的机器）是高熵的吗？答案是否定的，如果固定是 010101 这么出现，那么我们预测将会非常容易，这就不符合高熵的定义了。反过来高熵的序列发生器一定是均匀一致的吗？也不是，可能结果上有一些微妙的偏差，在熵不是最大的时候（实际也很难一直保持）一定 0 多一点或者 1 多一点，也不是均匀一致的。

不过很幸运，我们有很多方法让不同分布的高熵数据变成均匀一致的。如一个高熵的序列发生器，产生 0 的概率比 1 大那么一点，那么只要我们两位两位的读取，01 作为 1，10 作为 0，11 和 00 丢弃，这么处理过后产生的结果就是均匀且高熵的。

从结果上来说，我们所期望的真正“随机”就是这么个东西：一个均匀且高熵的数据。它的数学模型就是均匀分布，只不过这个在现实中难以直接实例化，所以我们绕了一大圈从信息熵和频率的角度去找到它。这个东西产生的难度就转移到了“高熵数据”的获取上（这东西可以产生的数据并非均匀，只要难预测就行了），它现实中的来源可以是分子热运动、混沌系统等等。