无标题无名氏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 丢弃，这么处理过后产生的结果就是均匀且高熵的。

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

无标题无名氏No.65164305

2025-02-01(六)13:58:07 ID: 22b93o1

信息熵和物理熵还是有区别的，信息熵最直观表示的是信息量而不是混乱程度。可以说一件事的结果提供的信息量越大，这件事信息熵越高。或者说，信息熵体现的是你知道一个事件的机制，知道这个事件的结果，你从这个结果中能获得多少信息。仅在概率分布均匀的情况下，信息熵只与每个结果出现的概率有关。

例如一个事件，50%的可能性输出1，50%的可能性输出0，信息熵为1；1%可能性输出1，99%可能性输出0，信息熵为0.08；1%可能性输出1，1%可能性输出2，...，1%可能性输出100，信息熵为6.6

无标题无名氏No.65164316

2025-02-01(六)13:59:16 ID: kdXdPyz (PO主)

> 计算复杂度理论

现实中，人和机器的算力都是有限的。我们希望能够在开始计算之前就知道我们计算所要花费的步骤、精力、资源需要多少，而这个往往和我们需要解决的问题和我们选择的算法有关。例如我们计算2位数乘法和两个 100位数相乘的代价肯定是不一样的，或者这个数字有规律的时候，我们可以选择一些更加取巧的方法去计算。问题规模和算法的选择这两种因素，我们想把他们分开，因此聪明的计算机科学家借用了数学函数增长趋势来描述这种差异。

把问题规模抽象成 n，则我们解决问题所需要的代价就变成有关 n 的一个数学函数。我们抛弃所有次要矛盾，抓住让这个函数增长最快的地方，抛弃系数，最后的结果就是算法复杂度。

例如一个普通的相同位数的两个数列竖式乘法就是 n 的平方的复杂度，因为竖式下方大概要写下来计算的数字大概在 n 平方的量级。

如果一个复杂度式子中没有出现 n 在指数上或者有 n 的阶乘这么恐怖的东西出现，那么就说这是一个“多项式时间（PPT）”算法。

> P 问题 与 NP 问题

不要被这个概念名字吓到，P (Polynomial Time) 问题就是做题可以多项式时间做出来的问题，NP 问题(Non-deterministic Polynomial Time)就是多项式时间可以看答案验算的问题。解方程的时候，移项求解的过程如果你觉得可以很简单就算出来那很大概率就是 P 问题，如果要看看标准答案对不对，只需要把解带进去计算看看等式两边相不相等就行，如果你觉得这个过程很容易那很大概率也是 NP 问题。

你肯定能大概的感受到，求解应该要比验算要更加困难一些，但目前还没有严格的证明出来这件事(|||ﾟДﾟ)，目前我们都是默认这应该就是对的，即 P≠NP。几乎所有的基于算力的密码学方案都暗含着这个假设。

无标题无名氏No.65164393

2025-02-01(六)14:08:20 ID: kdXdPyz (PO主)

>>No.65164305
对的！事件发生的概率越低，它含有的信息量就越大，因为它帮我们排除的不确定性越大。信息熵则是一个系统内发生某个事件时，它能带给你的信息量的期望，如果系统内由大量小概率事件构成，则它的信息熵就很大。这里用难以预测来表示“大量小概率事件”，直观上我感觉会更容易理解一点(つд⊂)

无标题无名氏No.65164498

2025-02-01(六)14:23:25 ID: 22b93o1

>>No.65164316
略微补充一下，密码学的经典险门函数，例如离散对数和ECC不仅是NP问题（因式分解不一定是），还是BQP问题，用量子密码学可轻易解

而后量子密码学的格问题，LWE问题之类的一些问题是NP问题，但不是BQP问题，因此具有抗量子性

无标题无名氏No.65164553

2025-02-01(六)14:30:33 ID: kdXdPyz (PO主)

>>No.65164316
PPT 和后面搞混了，这里补上洞（

> 可忽略函数

一个随着 n 的增大迅速接近 0 的函数，例如含 n 在指数上的函数的倒数，多项式的倒数不是可忽略函数。

> 概率求解/验证

你可曾听说过素数检验？如果要检验一个数是不是真的是素数，可以采用低效的遍历小于它的每个数看看是不是能够整除这个数，如果都不能整除则说明这是素数。有没有更快的方法呢？有，但是可能得牺牲一些“准确性”，即我检验出来是素数，它有可能不是素数，但我检验出来不是素数它就肯定不是素数，这种有一定概率成功的方法就是概率求解。可以证明，概率求解的复杂度是一定要小于非概率求解的复杂度的。

这里需要平衡的地方是复杂度的减少和成功概率的减少两者的矛盾。我们将能够有能力使用概率求解，并且能力限制在只能够使用多项式时间的算法的敌手称为概率多项式时间敌手（PPT 时间敌手）

无标题无名氏No.65164679

2025-02-01(六)14:44:30 ID: kdXdPyz (PO主)

>>No.65164498
好耶，是专业的密码肥( ´ρ`)( ´ρ`)只上了一学期课的小白献丑了