它如何使密码更安全？<我唯一的直觉是非线性函数，可以有很多根（解）。例如。对于非线性的$ y = F（x）$，如果攻击者知道$ y $可以找出$ x $，那么可能会有很多选择可以满足$ y = F（x）$，因此在攻击者的末端会增加复杂性当他尝试从密文回到纯文本时（<追溯）。
任何参考文献或详细资料都会受到赞赏。
#1 楼
这是密码学理论的观点。我们希望分组密码类似于伪随机排列（PRP）。 PRP是理想的建模目标，因为给定密钥下的分组密码是输入的排列，而PRP只是排列的随机集合。分组密码的密钥在创建置换方面永远不会比对它们进行实际随机采样更好，但是我们希望它尽可能地接近。可检测到的类似于PRP行为的偏差被认为是分组密码的弱点。
为了将分组密码与PRP进行比较，我们使用了CPA模型，在该模型中，攻击者使用明文查询黑匣子并接收相应的排列输出。他们试图通过对纯文本应用随机置换或具有未知密钥的给定分组密码来确定黑盒是否在选择密文输出。如果他们猜对了，他们将赢得比赛。如果他们能够以大于50％的概率赢得比赛，那么他们就打破了分组密码。 （有关这些模型的图片和更精确的定义，请参见第1至8页，特别是第7页，这些注释。）
如果分组密码具有线性，则攻击者可以将分组密码与PRP区分开属性。他们可以学习那些线性属性，然后用应该在密文中产生某些属性的纯文本查询黑盒。如果黑盒用与那些超过50％的输入查询的期望属性相匹配的密文答复，则攻击者猜测黑盒容纳了分组密码，因为随机排列将以仅50％的概率支持这些线性属性。 （否则，他们会猜测黑匣子使用的是随机排列。）然后，攻击者将赢得有区别的游戏。
当然，如果您正在寻找一个实际的原因，这会引发以下问题：为什么我们开始关注PRP模型。
评论
$ \ begingroup $
B-Con您好，感谢您对Block Cipher和PRP的详细阐述。我同意您提出的模型，但我的基本查询是非线性这些分组密码在构建中如何发挥作用。
$ \ endgroup $
–大卫
2012年6月9日下午6:09
#2 楼
如果分组密码相对于某个字段是线性的，则在给定几个已知的明文-密文对的情况下，可以使用简单的高斯消除来恢复密钥。这显然与人们期望从安全分组密码中获得的安全性相矛盾。#3 楼
在每个回合函数中，几乎所有分组密码都执行某些类型的替换和置换。对于AES，ShiftRow，MixColumn，AddRoundKey是线性操作；只有S-box操作是非线性操作。如果舍入函数中的所有操作都是线性的，那么使用多次（10,12,14）迭代加密回合从明文生成密文就没有任何好处。因为所有的线性运算都可以被单个线性运算所代替。与AES加密相同，可以用一个函数代替。更重要的是，当攻击者具有大量带有导出线性函数的明文和密文对时，它可以对密钥执行高斯消去。
评论
不是答案，而是正确方向的指针：en.wikipedia.org/wiki/Linear_cryptanalysis欢迎使用密码学堆栈交换。您的问题之所以被迁移到这里，是因为与IT安全（IT安全堆栈交换的主题）没有直接关系，并且在这里完全成为主题。请在这里也注册您的帐户，以便能够发表评论并接受答案。
重要的是要注意，将在不同字段中线性的两个操作组合在一起可以是非线性的。例如GF（2 ^ 32）aka 32位整数加法和GF（2）aka XOR加法是常见的选择。
@David：如果将同一字段的线性函数组合在一起，则会再次得到该字段的线性函数，并且线性方程很容易求解。因此，您确实需要非线性的东西才能使求解变得困难。非线性并不一定意味着有几种解决方案（看起来就像您认为复数上的多项式一样）。对于AES来说，S-Box是一个置换，因此对于$ y = S（x）$，总是存在一个精确的解决方案$ x $。
因此，我们在不同的环中使用加法。环$ \ mathbb Z / 2 ^ {32} \ mathbb Z $（整数$ 2 ^ {32} $）不是一个字段，尽管它具有与$ GF（2 ^ {32}）$相同数量的元素。 。