Shannon将扩散解释为一种将文本的统计特性分布在整个文本中的特性,从而阻止了统计分析。它经常被翻译成:对纯文本符号的更改会影响许多密文符号。假设位或字符的置换,如何通过简单置换实现扩散?我的意思是,如果您置换位,那么不会影响其他位。
但是如果您将符号视为字符并且置换了位,则字符的更改将影响许多其他字符。这是一个关于什么是符号的问题。
我还阅读了这种扩散概念的版本,其中的意义只是改变位的顺序,以避免对文本进行模式分析。但是,简单排列的雪崩效应在哪里?
那么,正确的定义和扩散的含义是什么?
我希望您了解困扰我的是什么。
再次感谢您
#1 楼
我认为您错过了该概念的关键点,即用于构成安全PRF(或PRP)的小块,即,当置换一位时,您实际上会更改该位的小块的值,也就是说,整个小区块都会受到影响,因此准备在下一轮中混淆,这样您很快就会对整个大区块感到困惑。我很好地解释了Lindell-Katz书中所述的概念
除了关于完美保密的工作,Shannon还介绍了一种基本的范式,用于构造简洁,随机的排列。
基本思想是从许多较小的随机(或看似随机数)
构建具有小块长度的随机外观置换$ F $,其中
具有小块长度。让我们看看这个
是如何在最基本的水平上工作的。假设我们希望$ F $的块长
为$ 128 $位。我们可以如下定义$ F $:$ F $的键$ k $将
指定$ 16 $排列$ f_1,\ ldots,f_ {16} $,每个都有$ 8 $位
($ 1 $ -byte)区块长度。给定输入$ x \ in \ {0,1 \} ^ {128} $,我们将其解析为$ 16 $字节$ x_1,\ ldots,x_ {16} $然后设置(公式6.2)
$ F_k(x)= f_1(x)|| \\ ldots || f_ {16}(x_ {16})$。这些舍入函数
$ \ {f_i \} $会给$ F $带来混乱。应该立即清除,但是,上面定义的F不会是伪随机的。具体来说,如果$ x $和$ x'$的前一个
位仅不同,则$ F_k(x)$和$ F_k(x')$的前一个字节仅不相同(br不论密钥k)。相反,如果$ F $是一个真正的随机排列,则更改输入的第一位将影响输出的所有字节。因此,引入了扩散步骤
,由此输出的位被置换或“混合”。
使用混合排列。这具有将局部
更改(例如,第一个字节中的更改)分布在整个块中的作用。
混淆/扩散步骤(统称为回合)被重复
多个次。这有助于确保更改
输入的单个位将影响输出的所有位。
例如,采用这种方法的两轮分组密码将
操作如下。首先,如等式(6.2)中那样,通过计算中间结果$ f_1(x_1)|| \ ldots || f_ {16}(x_ {16})$引入混乱。然后对结果的位进行“混洗”或重新排序,以给出$ x'$。然后计算$ f'_1(x'_1)|| \ ldots || f'_ {16}(x'_ {16})$
(其中$ x'= x'_1,\ ldots, x'_ {16} $),使用可能不同的函数
$ f'_i $,并对结果的位进行置换以给出输出$ x''$。
$ \ {f_i \ },\ {f'_i \} $,并且混合排列可以是随机的,并且取决于键,如上所述。实际上,
它们是经过特殊设计和固定的,并且密钥以不同的方式结合
#2 楼
我发现“混淆”和“扩散”这两个术语有些含糊,可能导致过分简化。混淆
例如,说“替代”导致“混乱”并不一定正确:“替代”实际上只是对状态的功能应用;该实现通常利用一个记忆函数,但是您可以轻松地1.在每个应用程序上显式计算非线性函数,以及2.使用记忆线性函数仅提供扩散而不引起混淆。所以说用Substitution提供混淆是一个过分的简化。
现在,非线性函数经常用备忘录表实现的原因是因为非线性函数的计算很复杂。一般来说,功能越复杂,评估它所花费的时间就越长。例如,AES S-Box利用有限域中元素的乘法模逆的计算。这可以显式地计算,而不是使用表查找。这样做将导致密码的运行速度大大降低。非线性函数越“线性”,就越容易进行密码分析和破坏(我们可以假设,它在某些输入/输出中像线性函数一样,以一定的概率为真)。关于哪种非线性函数对密码分析人员最大无益,已有大量研究。
因此,非线性可能是造成“混乱”的原因可能更为准确。在对称密码算法中始终需要非线性,因为否则可以很容易地操纵和求解代表密码的方程式的结果系统。
扩散
至于“扩散”,还有其他答案。但是更详细地说,当您真正了解它时,在尝试加密任何内容时,我们真正能做的就是将XOR和AND门应用于位。是的,还有其他运算,例如整数加法;但是,这些实际上是由XOR / AND电路实现的,因此,归根结底,这是我们真正有能力做的。 (这不是绝对正确的;作为反例,您可以使用NAND作为基础;这对当前的讨论没有太大帮助。)
这与扩散有关,因为XOR和AND都是位切片操作。它们将两位作为输入,而将一位作为输出。那么,如果您对两个8位字进行XOR运算会怎样?您实际上是对8个独立的数据组并行执行八个完全独立的XOR门。 XOR和AND(在任何大小上均大于1的值)实际上是SIMD操作。因此,单词中索引$ i $处的位不会影响单词中其他索引处的位。实际上,我们只有1位寄存器,我们只有很多并行。
这就是为什么需要“转置”(旋转和移位)才能产生扩散的原因:旋转和移位可确保将新的位对用作未来XOR / AND门的输入。基本上,线性扩散层负责混合这些1位寄存器的内容。
更具体而言:线性扩散层的工作是确保非线性函数的每个后续输入由平衡和最大数量的叠加输入位组成。如果您的非线性函数对X位字进行运算,那么理想情况下,每个输入位将在每个索引中超级定位X / 2个输入位(每个输入位的50%影响每个输出位,也称为“雪崩效应”)。 (注意:异或和是求和后的位的线性叠加)
简而言之,扩散和混淆的组合意味着我们要生成具有最大项数和最大代数复杂度的方程式。然后,当然,我们要重复该过程,直到描述概率的结果方程组完全无法通过概率推理进行处理。
评论
用更现代的术语来说,我相信我们将混淆表示非线性变换,将扩散表示线性变换。替换可以是线性的,不会造成混淆。这似乎是漩涡或谜团背后的想法,因为它的不可预测性是可以预测的。
惠而浦如何预测?