密码学 | 5.6.2 熵

密码学 1年前 (2023) admin
485 0 0

5.6.2 熵

在高效的密码系统中,都是用一个密钥来加密大量不同的明文,因此想要无条件安全是不可能的。于是退而求其次,我们试图构建计算安全的密码系统。不过不幸的是,任何不完全保密的信息都有可能泄露密钥等重要信息。为了研究这一现象,Shannon 引入了熵的概念,熵是系统中不确定性的度量。因此,如果我们将 视为某个实验的结果等于  的概率,那么如果单个实验的结果揭示了关于随机变量 的大量信息,则认为  的熵很小。
设  是具有有限个可能值  的随机变量,并设  是对应概率

 的熵  仅取决于变量  可能值的概率  ,因此我们记为

我们可以理解  是一个随机变量的期望值,该随机变量度量了实验结果  发生的不确定性。因此,的值越大,实验结果所揭示的关于  的信息就越少。那么  有哪些性质呢?
性质  函数  对于变量  来说应该是连续的。这反映了一种直觉,即  的微小变化会导致  所揭示的信息量的微小变化
性质  设  是均匀分布在集合  的随机变量,即随机变量  有  个不同的结果,且每个结果的概率都是 ,那么

这也反映了一种直觉,即如果所有结果出现的概率都相同,那么不确定性则会随着结果数量的增加而增加。(即每一种结果出现的概率随着结果数量的增多而减少)
性质  第三个性质不是那么自然,即,如果  的一个结果被认为是一个选择,并且如果该选择可以被分解为两个连续的选择,那么  的原始值是连续选择的  值的加权和。为了量化这种直觉,我们考虑随机变量  和在  集合中的取值

满足

即表示实验结果  被分解为连续的 ,其中 ,那么性质  可以表示为

例 5.58

设  是在  个结果上均匀分布的随机变量,那么我们有

我们将  视为在集合  中进行选择,并将这个选择分解为,首先选择 ,然后选择 ,那么根据性质 ,我们有

例 5.59

我们再用一个更详细的例子来说明 ,假设  有五个可能的结果 ,相应的概率为

图5.2a 中的分支树表示了  的五个结果。

密码学 | 5.6.2 熵


我们把  的可能结果视为一个选择,现在我们把这个选择分解为两个连续的选择,第一次选择子集  还是 ,第二次选择自己里具体元素。所以我们有随机变量  ,其中 ,并且

如图 5.2 b 所示。于是,用这个例子说明  就是
密码学 | 5.6.2 熵
定理 5.60 每个函数都有性质 ,并且  是下列函数(熵的计算公式)的常数倍

密码学 | 5.6.2 熵

明见《A mathematical theory of communication》

为了说明不确定性的概念,考虑当一个概率  而其他概率为零时会发生什么。在这种情况下,熵的计算公式(5.51)给出 ,这是有意义的,因为对于只有一个可能结果的实验,其本身并没有不确定性。
事实证明,当所有概率  都相等时,会出现另一个极端,即最大不确定性。为了证明这一点,我们使用了一个重要不等式,称为 Jensen 不等式。在介绍 Jensen 不等式之前,我们首先需要一个定义。

定义

如果以下不等式对于  中的所有  和所有  和  都成立,则实线上的函数  称为区间  上的凹(向下)函数:

密码学 | 5.6.2 熵

这个定义可能看起来很神秘,但它有一个简单的几何解释。注意,如果我们固定  和 ,并让  从 0 变为 1,则点  则是在区间  中从  走到  。所以不等式(5.52)是连接  图上任意两点的线段位于  图下方的几何描述。例如,函数  是凹的。图5.3 给出了凹形和非凹形函数的图例,以及代表性线段。如果函数  有二阶导数,那么你在微积分中学到的二阶导数可以用来测试凹性。密码学 | 5.6.2 熵
定理 5.61 ( Jensen 不等式)假设  在区间  中是凹函数,设  为非负数,满足

那么

密码学 | 5.6.2 熵

当且仅当  是线性函数或者  取等。(对于 n=2,不等式(5.53)正是凹(5.52)的定义)
引理 5.62 设  为具有有限个可能值  的随机变量,则有
  1. 当且仅当每一个  事件发生的概率均为  时 
证明:设 , 其中 。然后 ,所以我们对函数  应用 Jensen 不等式()。5.53 式左手边其实就是熵的公式(5.51),所以我们有

这就完成了 1 的证明。另外,函数  不是线性的,所以当且仅当  时才能取等,即所有的事件概率  时取等。这完成了 2 的证明。

注意推论 5.62 说当所有概率相等时熵最大化。这符合我们的直觉,即当每个结果都有可能且概率相等时,不确定性最大化。
熵理论也被应用于密码学,通过计算与密码系统相关的随机变量(如)的熵,并将实际值与最大可能值进行比较。显然,熵越大,对用户越好,因为增加的不确定性使密码分析员的工作更困难。
例如,考虑移位密码和与其密钥相关的随机变量 。随机变量  有26个可能的值,因为移位可以是 0 到 25 之间的任何整数,并且每个移位量都是相等的,因此 具有的最大熵为 

例 5.63

我们考虑示例 5.54 中描述的具有两个密钥的系统。每个密钥的概率相等,因此 。类似地,我们可以使用由(5.48)给出的该系统的明文概率来计算与明文相关的随机变量  的熵。

注意到  仅比  小了一点,而  是具有三个明文的密码系统中  的最大可能熵。
我们现在介绍条件熵的概念及其在密码系统中的应用。假设信号通过有噪声的信道发送,这意味着信号在传输过程中可能失真。Shannon 将 “equivocation” 定义为原始信号的条件熵。他使用这个量来测量在噪声信道上传输的  确定性。Shannon后来观察到,有噪声的通信信道可以看作保密系统的模型。原始信号(明文)通过应用加密过程而“失真”,因此接收的信号(密文)是原始信号的噪声版本。通过这种方式,“equivocation”的概念可以应用于密码学,其中如果 “equivocation” 很大,则表示密文隐藏了有关明文的大部分信息

定义

设随机变量 ,相应的可能结果为  关于  的条件熵定义为

当  是密钥随机变量, 是密文随机变量时,  称为“密钥 equivocation”。它度量密文所揭示的密钥的信息总量,或者更准确地说,它是给定  的单个观测值  后  的条件熵  的期望。 “密钥 equivocation”可以通过计算密码系统的所有条件概率  来确定。或者,可以使用以下结果。

命题 5.64 密码系统的 “密钥 equivocation” 与  的单个熵有关,公式如下:

密码学 | 5.6.2 熵

例 5.65

我们计算示例5.54和5.63中描述的密码系统的 “密钥 equivocation”。我们已经计算了 和 ,因此仍需计算。为此,我们需要每个密文  的  值。我们已经计算了 ,然后使用(5.48)和表5.12进行类似的计算

因此,,然后根据 (5.54)我们有

       

原文始发于微信公众号(山石网科安全技术研究院):密码学 | 5.6.2 熵

版权声明:admin 发表于 2023年3月3日 上午10:43。
转载请注明:密码学 | 5.6.2 熵 | CTF导航

相关文章

暂无评论

您必须登录才能参与评论!
立即登录
暂无评论...