应用离散数学2016数学数学加密方法№3）（33）

数学加密法

UDK 519.7

从密码分析到布尔函数的密码特性1

啊。啊。戈罗季洛夫

利沃夫数学学院C.l.l.Sobeleva Soran，G.俄罗斯新西伯利亚

本概述的重点是布尔函数的基本密码特性，如高代数幂、平衡和完全平衡，雪崩特性，缺乏线性结构，相关免疫性和稳定性，高非线性，统计独立性，代数免疫性，仿射度和k-正规度，微分均匀性，可分解为特殊函数和乘法复杂性，线性集的高功率。研究了基于攻击的模块和流程密码的属性数据的形成，使用了作为密码组成部分的布尔函数的某些脆弱性；攻击数据的基本思想。对每一种特性所取得的基本理论结果进行了简短的审查，并提出了这一领域中的一些未决问题。

关键词：布尔函数，流水密码，块密码，代数幂，平衡，完全平衡，雪崩特性，线性结构，相关免疫性，稳定性，非线性，统计独立性，代数免疫性，仿射性水平，k-正规性，微分均匀性，阈值分解，乘法复杂性，线性集，线性复杂性，相关密码分析，快速相关攻击，线性密码分析，统计模拟，代数密码分析，微分密码分析，第三方攻击，线性攻击。

DOI 10.17223 20710410/33 2

FROM CRYPTANALYSIS TO CRYPTOGRAPHIC PROPERTY OF A BOLEAN FUNCTION

The survey is devoted to description of basic，but not all，cryptographic properties of Bolean functions:algebraic degree，balanceness and perfect balanceness，avalanche

1工作由RFFI赠款资助，第15-07-01328号。

Keywords:Bolean function，stream cipher，block cipher，algebraic degree，balanced-ness，perfect balanceness，avalanche characteristics，linear structure，correction immunity，resiliency，nonlinearity，statistical independence，algebraic immunity，affinity level，k-normality，differential uniformity，threshold implementation.multiplicative complexity，linearization set，linear complexity，correction attack，fast correction attack，linear cryptanaysis，statistical analogue，differential cryptanaysis，side-channel attacks，linearization attack.

导言

半个世纪以来，有相当多的要求，用于加密系统的布尔函数。符合这些要求的功能被称为“布尔加密功能”。

工作的主要目的是使不同的密码分析方法和布尔函数的数学要求之间的原始联系，这些密码用来对付这些攻击。该表反映了本工作的实质内容。为了更深入地了解不同加密特性领域的理论结果，可以推荐相关的工作。啊。洛加乔夫，A.啊。S.V.Salnikova，S.V.Ushirieva，V.B.[11]蜥蜴P.[1]俄汉互译B.[19]

所审议的加密特性及其用途

目标属性

1高代数比提高生成序列的线性复杂性；提高描述密码的非线性方程组的程度

2、平衡改善流水发电机产生的统计序列性能

完全平衡

4雪崩特性保证大输出变量值在小输入变量值变化时的变化

5缺乏线性结构改善函数的非线性特性

6相关免疫性，抗阻性

7高非线性阻碍了快速相关攻击的流水密码和线性密码分析

8统计独立性对统计加密分析的障碍

表尾

目标属性

9代数免疫性妨碍了代数密码分析

你找不到你想要的吗？尝试一个参考工具。

10能级仿射度和k-nor-mal阻碍线性化方法而不引入新的变量来解决布尔方程

11微分一致性的障碍进行微分密码分析块密码

12可分解性和特殊功能的总和

13乘法复杂性

14高功率线性集合障碍线性化攻击

1。基本定义和标志

1.1。布尔函数

输入一个符号：n-自然数；F2-集，由0和1；x=）xi“一个二进制向量的坐标为F2；F ^所有的二进制向量的长度n；；0=）0 ^ 0 ^零向量；F ^的加法模块2。汉明格wt）x）二进制向量的重量叫做单位，с-

n

在X:wt（x）=X”（d）x，y）两个向量之间的距离

i=1

米x，y称为不同的位置数，或相当的，d）（x，y）=Wt）xfy标量积）（x，y）二进制向量x，y）定义为（x），y）=xiyi F……f xnyn.

矢量布尔函数）（n，t-函数）F被称为任意显示F:Fn ^ FM。在m=1的情况下，他们说，F-布尔函数从n变量。你可以看到，n，t-函数是一个从n变量m坐标函数集：F=）1，……。坐标函数的任何非零线性组合，即E.布尔函数b，F，其中b是FM b=0。

wt/）函数的重量等于其载体的功率（supp）/）={x E Fn：/（x）x）=1}。汉明的（d）/，G）之间的布尔函数/和（g）是汉明的向量之间的距离（d）／G）={x e Fn：/）{x x x x x}G）x。让mn-从n变量的一些布尔函数。从功能g到许多功能mn定义为（d）g，mn）=分钟{d）/，G）：/e mn}。对于任何布尔函数/导数的方向A，其中E Fn，定义为：Da/（x）=x）F／x A。

任何（n，t-函数都可以用唯一的方式写下作为热伽林多项式的形式，或代数范式的）：（f）x1“

n

=A1爱。xik fa，其中{ib.。，^h}^ ^ ^ ^ ^ 1。，n}and ai 1，……。k=0

F函数的代数幂（deg）（F）称为最长的ANF分量中的变量数，其中系数不等于零向量。幂不大于1的函数称为仿射函数。在A0=0的情况下，线性函数。

对于每一个y-e-Fn系数沃尔什-阿达玛WF）（y）布尔函数/从n变量称为一个值，由WF）y等于

5块

■G

■平方米

DZ ^ HH

5块

阿布洛克

到

2。

■V-I■K

=^ 1 ^ ^ 2）胡所有E K的wf系数组）这就是所谓的光谱

希克？

你找不到你想要的吗？尝试一个参考工具。

ROM沃尔什-阿达玛布尔函数f.帕尔塞瓦尔公平：W ^ U）=22p.沃尔什-阿达玛谱

韦克？

沃尔什-阿达玛的所有组成的布尔函数的有效性：WF（

=^ 1 ^ ^ 1 ^ ^ 1 ^ h）^ hek？

1.2.块密码将打开文本块（信息）的长度N（信息）转换成代码块的文本，并使用一定的秘密密钥长度N。加密过程包括多个重复的回合，通常定义相同的圆函数，取决于一个回合连接到^，按特定规则生成的主钥匙

最常见的成组密码类型，br网络和费斯特勒网络，在图中给出了示意图。[交存秘书长的多边条约]这两个方案都体现了克劳德·香农在其工作中确定的两项代码转换原则，即散布和混合。让我们根据工作来解释这些原则：：”质量上可以说，这是一个复杂的混合，恢复开放和加密文本的统计和分析属性的关系，a/分布扩展了一个开放的字符对多个字符的影响，从而消除了统计属性对文本属性的影响。代码。在Br-Network的例子中，可以清楚地看到，p-砌块可供散布，而一组小的B-砌块可供搅拌。虽然通常选择线性函数作为r-blo-k，但b-blog则是非线性的加密变换。

基本上，b-块-这是一个矢量（p），t-函数，以及p和t值小，例如4，6，8位。尽管尺寸这么小，但很难找到这种具有“良好”加密特性的b-块。为了直观起见，我们注意到，各种各样的表现都有22048的存在，这是目前无法完全克服的！然而，即使是分析性的讨论也无法回答一些对加密应用程序很重要的问题。例如，我们不知道是否有一个匹配的几乎完全非线性的自我表现在偶数p ^ 8，在P.12。

1.3。[5]连续密码引用广泛使用的伽马码流水作业模式。这些系统的基础是“叠加”方法（例如，按模2）的关键序列加上）的公开文本上的密码信息。从克洛德·香农的作品中可以看出，如果钥匙的长度和消息的长度一样长，那么选择是随机的，并且是可能的，并且只使用

r-lock-k，

■R1 1小时

块，块

A.”

8

费斯特循环函数

图1

一次，此加密系统是绝对抵御基于代码的攻击。由于这种模式不适用于广泛的传播，因为很难产生与电文相同的数量的密钥，更不用说传送钥匙了，开发人员面临的任务是从一个短的随机密钥位序列获得一定长的伽马键序列，这将是接近随机的。请注意，密码的加密稳定性取决于该序列的性质。

移位回授寄存器常常被用作流水密码的一个组成部分。图2说明了他们的工作原理图，其中f-Buleva函数从p变量，作为反馈功能【20】

图2

在开始工作之前，开始用某些位填充登记册。接下来，在每一个工作步骤，计算一个优先值（a=f）【哔】然后将寄存器中的所有位向左移动，在最右边的位中输入一个值，而最左边的位将成为下一个输出序列位==M0.m1，页：1

最常见的是线性反馈移位寄存器）（在那些f线，比如说，f）的pp-1，（……，p0）=与，呃，其中，从€E.我们注意到，任何反馈登记处产生的一致性总是周期性的。很容易看到，事实上，任何周期序列可以产生一个有效的长度。在这种情况下，线性的复杂性和顺序被称为最小的长度和它产生的长度。序列的线性复杂性是描述其解析结构复杂性的主要参数[5]

提醒你，生成“好”的γ不是一个单一的yevy使用。的确，如果我们知道反馈功能（f）【J）=）与【J】，从€EP，只需连续运行位序列才能恢复寄存器的初始状态。通过线性方程组的解法。而初始状态通常是密码的秘密密钥。

此外，还有一个更强大的结果，可以为任何周期序列找到线性反馈功能。假设我们截获了相当长的一段时间的某种周期序列。然后，通过众所周知的伯勒坎普-梅西算法，你可以找到从有限序列的长度多项式的时间找到递归定律，它的产生，这相当于找到一个线性寄存器，产生这个序列段。在这种情况下，如果序列长度不小于2c，其中的线性复杂性，那么找到的yevy也产生了无限的序列，这是我们知道的部分。

另一方面，所产生的序列的线性复杂性在登记处的几乎任何初始状态——未知的钥匙——中必须是高的。因此，使用了一些复杂的方法。根据直线反馈移位记录器制作的两种主要的发电机模型【20]）图3。布尔函数分别称为组合函数和滤波函数。

组合发电机

图3

是啊。

••

音阶

滤波振荡器

2。高代数幂

你找不到你想要的吗？尝试一个参考工具。

*本文件迟交，是为了列入最新资料。[24]理论上的结果表明，代数幂小的，应当作为组合和过滤函数来选择。首先考虑由线性回授长度的寄存器组成的复合振荡器1，……，p.让组合的L函数以代数范式表示

E

h）…CP）=0“，”1。^ J！..HGH，在那里），，，……，与{1，…和^ ^ ^ ^ ^ ^ ^ 2。时而，时而

K=1 1 1

当一个线性的复杂性与所产生的序列，从上面通过寄存器长度评估如下：

E

与^和^ 1亲爱的，K=1

在这种情况下，已知的条件下，这种估计达到：如果rg匹配任何克和x数产生的e8和h序列的线性复杂性……两个的，互为简单。可以看到，国家货币基金组织的程度越高，可以得到的线性复杂性就越大。

在过滤模式中，没有类似的精确结果，尽管也有通过STE-T产生序列的线性复杂性的估计。

（g）（h）

pen过滤功能deg）h，即：c ^ ^ g，其中登记长，而

类型=0

双曲二项式系数。除此之外，如果一个简单的数字，那么从下一个估计数是正确的：c ^ ^

在组合密码中也应选择较大的功能。“”deg）F）布尔函数必须大。对于块加密来说，这一条件通常是为了使用密码结构分析而设计的关键位方程组，包括使用G的功能。作为其组成部分，具有很高的等级。[直义]系统的程度越高，解决问题就越难，而这就意味着确定钥匙。

3。平衡

定义1.布尔函数f从p变量称为平衡，如果其重量等于2 p-1，即E.函数接受0和1的值的次数相同。

这可能是在使用流水密码的布尔函数上最自然需要的特性之一。如果布尔函数是平衡的，那么它将接受0或1的概率是1/2。这可以减少函数输入和输出之间的统计关系。否则，密码分析师可以使用概率关系进行加密分析。

本定义概括为一种矢量情况。

定义2.矢量（p），t-函数被称为平衡，如果​​​1）={x：R）x）={u}=任何€s€s

在这种情况下

13.核准1。矢量（p），t-函数只有在其所有的分量函数均得到平衡时才得到平衡。

4。完全平衡

布尔函数完全平衡的性质是通常平衡的自然综合，当该函数扮演，例如，过滤函数发电机。这个属性是正式的S.H.[原件：俄文]

让发电机的f滤波函数从P变量，X=）X1。（……，X+++P-1）的输入序列段长度+P-1，其中加上一些自然数。然后发电机会产生一个序列段和==）1和××××××××××××××××××××××××××××××××××××××××××××××××××爱我们定义的函数（f）和数（不包括向量）＋P-1，），并根据上述规则确定x向量的对比函数。

定义3.布尔函数f称为完全平衡，如果对任何自然数而言，fg函数是平衡的。

特别是，如果功能完全是平衡的，那么它在普通意义上也是平衡的。相反的错误。

禁止布尔函数f称为矢量=（，和^为一个特定的，它带来了许多项目^-1）和^是空的。下一个定理反映了完全平衡的标准在禁止函数的术语。

定理1.布尔函数是完全平衡的时候，只有当它是一个函数没有禁止。

直观地可以理解，由于禁止发电机的过滤功能，使它在产生具有良好统计特性的序列方面“较弱”。但要小心，由于某种形式的完全平衡滤波函数将输入序列的性质转移到生成序列的特性中去，]比如说B.[第17条]有了一个新的标准，在思想上讲

你找不到你想要的吗？尝试一个参考工具。

下一个：“……过滤功能保留禁令的相应意义”，只有当它是完全平衡的。因此，如果函数的输入是由随机序列的“远方”，然后在其输出的统计性质是不好的。

请注意，如果线性的过滤函数根据其第一个和/或最后一个实质性变量，则完全是平衡的。但相反，这是不正确的，因为设计完全是平衡的功能，非线性地依赖于其极限变量）可以在[11]找到参考。对过滤发电机的所谓反演攻击证实了寻找这种功能的广泛类别的意义，使用第一个或最后一个实质性函数变量的线性滤波。这一攻击是由J.Dj提议的。[原件：西班牙文]

5。雪崩特性

布尔函数雪崩特性的概念反映了《香农密码变换设计原则》中的原则之一。1.2.即散布原则。以下定义是由A.F.Webster，S.E.Tavares在工作中§43。

定义4.布尔函数f从n变量符合严格的雪崩标准（

如果所有的坐标矢量函数）（n）是由SAC满足，那么当一个输入位的变化概率为1 2，每一个输出位的变化。因此，可以预计，大约一半的输出位将发生变化。

B.Preneel等已开始考虑的这一标准的综合说明如下。[39]

定义5.布尔函数f从n变量满足K（

根据PC定义，（1）符合SAC。展望未来，可以指出，符合PC（第11条定义8、理论16（12个员额）如果一个函数满足这些标准，这意味着多位输入向量的变化会改变函数的值，概率为1/2。

正如第11条所指出的那样，严格的雪崩标准及其概括“[最终为所研究的加密功能提供了局部性质的指示]。更正确的做法是，要求函数的平均“好”雪崩特性，这表现在自相关函数模块（a）（）=）1（f）x®f）x®x®a）等于或接近多数到零

矢量A E F ^。X-M.Zhang和Y.Zheng在工作中提出了这种办法[]45。

定义6.全球雪崩特性）【GAC】（f）的布尔函数从n个变量称为数字A/=2（a）和A/=最大A/…）A。

显然，数据越少，加密功能就越好，因为全球大气监测系统反映的平均雪崩指数。[11]可以找到GAC任意函数的基本特征及其某些关联

与其他加密特性，特别是非线性和稳定性顺序。

6。线性结构

定义7.矢量（n），t-函数具有线性结构，如果有一个矢量a G Fn，A=0，如，F）=const。

[32]尽管如[24]中所述，代码应选择不具有线性结构的功能。到目前为止，这些弱点没有被用来进行攻击。事实上，一个线性结构的存在表明它“类似”一个线性函数，因为它是线性等价的函数，有一个变量，它依赖于线性或虚拟。如前所述，在不同的意义上，功能接近线性系统是不可接受的加密系统。

7。相关免疫性和稳定性

这里所考虑的属性来自不同的应用程序，但事实证明，它是密切相关的。t.Siegenthaler在工作中的相关免疫性术语【40】它显示，高相关免疫率的函数，作为一个混合的发电机在流水密码，使密码抗相关攻击。攻击的本质是寻找一个组合函数的变量子集，其值可以在知道函数的意义的信息。同样在1980年代开放文献中也引入了可持续的功能，但正如[11]中所指出的那样，“……与分布式计算等研究领域有关，“防误差，并为量子-加密信道开发共同的钥匙。”从k.H.众所周知，苏联对类似的功能进行了研究。B.在1970年代，这是一个相当大的变化。

在流水密码中，发电机的综合功能必须是具有稳定性的功能。在这种情况下，稳定性越高，密码对相关密码分析的稳定性就越大。

让我们把这些属性的正式定义在组合的语言。我们首先定义子函数的概念。从f项函数中提取的f项职能从变量x \xA0 \nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn具体的因此，数值为0或1。这是一个函数标记为“^”。

定义8.布尔函数f称为K的相关免疫序，如果fiol ^函数的子函数的重量匹配wt^l'”^的关系。^ Wt）=Wt）^ F/2k任何一组指数1^我\……ik^n和任何值.ak G F2。

换言之，布尔函数的f称为K相关免疫序，如果P[f=1]=pf^1'^ 1 ^ 1是概率的P函数，即概率的P函数。一些输入位的知识不提供关于函数意义的统计信息。

定义9.布尔函数f称为k-稳定（

不难看出，f函数是k-稳定的时候，只有当它在k阶的平衡和相关免疫。

7.1。相关攻击思想

考虑这个密码分析的一般想法，遵循±14.

让f-completing函数发生器，LFSRI，，……，LFSR-他的移位寄存器与线性反馈长度L1。……，LN分别，和U==U0，Ui，U2……寄存器输出序列密码分析的劳动密集度E.登记处的所有初始状态的完整性，估计为2Ll++Ln。如果寄存器是“正确的”，那么U序列是非常接近随机的，所以你可以认为P[U类型=0]~ 1/2。因此，如果z=z0，z1，z2……-任意独立于u的序列，你可以认为P[u=Z]~ 1/2，因为P[u=Z][类型]=P[U=0][P]Z类型=0]+P±Z类型=0]+P±P±Z=1]“1/2±P±Z=0]+P±ZI=1]=1/2。

假设f函数是与功能相关的（当时有人说，可以恢复LFSR1登记处的未知初始状态。为了做到这一点，我们将回顾第一个寄存器的所有可能的起始状态）（并计算，多少次实现z系列=u系列。然后，如果最初的状态是假设错误的，那么P[Z类型=U]~ 1/2，如果是正确的，P[Z类型=U]~ 1/2+E。因此，越是相关的E，我们就越有可能找到正确的寄存器状态。因此，我们减少了麻烦的2 Ll+2 2++Ln。如果在这种情况下有f和其他变量的关联，那么复杂性可以进一步降低。如果（f）与功能（i）（x）没有关系，=嗯，你可以找到与其他线性函数（Wt）（c）=k小，例如，C=）1，1，0，……。然后它的复杂性减少到2版1+++2版k++我+++n。但如果k足够大，那么密码分析师可能没有特别的好处。

请注意，其中也载列了已知的结果，即具有f功能的过滤发电机可以归结为具有f功能的专用组合发电机，她已经作为一个组合。在这种情况下，新的发电机在一定的初始充满寄存器状态下产生相同的顺序。因此，相关攻击可以概括为针对过滤发电机。

你找不到你想要的吗？尝试一个参考工具。

7.2。基本定理及与非线性的关系

13.核准2。k系列相关免疫功能也是i系列k的相关免疫功能。

由于这种说法，自然地确定了相关免疫性的顺序（cor）（f）函数作为

cor f.）=max{0 ^ k^ n:f-相关免疫程序k}。

下一个众所周知的定理提供了相关免疫功能和稳定功能的光谱特征。

定理2）光谱特征。让f-布尔函数从n变量。正确的cor）（f）=k然后只有当WF（y）=0所有的向量Y，如1 ^ WT）Y ^ K。此外，F是平衡的时候，只有当WF（0）=0。

本定理直观地联系了k函数相关免疫序的定义和使用-

研究所将其作为流水发电机的综合功能。的确，为了进行攻击，必须找到f）x）=（c）x的线性函数，与f的组合函数相关，即[P][f=]=1/2.由于P]f===（2n-d），（f.f）/2n=1/2+（2n-1-d），[2n-1-d]（f.f）./2n=1/2，这相当于（d），[f]=2n-1.此外，很容易得到，f和线性函数之间的距离–（x）=）=（c，x）表示为（d），（f），f）=2n-1-wf）c/因此，d）f，f）=2n-1的时候，只有当WF）（c）=0。因此，如果组合函数的稳定顺序足够高，那么对该代码的相关攻击将难以进行。

（f）和（deg）（f）函数的范围之间的关系体现在下一个理论中。

定理3）Siegenthaler。让f-布尔函数从n变量。

1。如果cor）（f）=k，然后运行deg）+k ^ n。

2。如果cor）（f）=k，f是平衡的和k ^ n-2，然后运行（f）+k ^ n-1。

从理论上可以看出，功能越高，其相关免疫性的次序就越小，反之亦然。但是，正如我们所看到的，这两个参数必须是高的加密发生器的复杂性函数。

结果1.让f-布尔函数从n变量。如果cor）（f）=n，则f=const.如果cor）（f）=n-1，那么f）x）=x1 f……f xn f const.

已知的下一个估计（cor），（f）收到d.G.[原件：法文]

冯-德-flaass定理4）。让f-不平衡布尔函数从n变量。那么cor）（f）^ 2n 3）-1.

在这里还自然提到（Nf）非线性）。第10条定义（8）相关免疫功能。

定理5）关系（cor）（f）和Nf。让f-布尔函数从n变量。

1。如果cor）（f）=k，k ^ n-1，它是由NF ^ 2n-1-2k执行。

2。如果cor）（f）=k，f是平衡的和k ^ n-2，然后执行NF ^ 2n-1-2k+1。

8。高非线性

定义10.f的布尔函数的非线性从n变量被称为nf值，相当于汉明从f到a集的距离，“，所有的仿射函数从n变量。

在7.2我们已经提到了任意函数和线性函数（d）（f），（c），x）之间的距离=2n-1-WF）（c/2）。基于这一点，很容易获得，非线性f通过其沃尔什-阿达玛系数表示如下：=Nf=d）（f，An）=2n-1-max（wf），）c/2。此外，从帕塞瓦尔的平等

c€F

2

可以从下面找到一个估计数：max wf）^ 2n/2。因此，函数的非线性

总是满足Nf ^ 2n-1-2n/2-1的不平等。

定义11.最大非线性函数，其非线性达到最大可能值。对于偶数变量，最大非线性函数也称作Bent函数。

你找不到你想要的吗？尝试一个参考工具。

布尔函数的非线性越高，最好既在流水作业中，也在块式加密中使用。然后我们将两个攻击不同类型的加密。

8.1。这是一个很好的人。

这种类型的攻击联合发电机是在简单相关攻击后不久出现的）在п.7.1。我们描述一下它的基本想法，而不必详细叙述纠正错误的代码理论。

我们将使用相同的组合发电机，在P.7.1。和相关攻击一样，为了快速相关攻击，必须找到线性函数（i）（x）=）c、j，其中f有相关，即f有相关。[P]不同的是，现在我们不在乎什么是Wt）c，重要的是，只有尽可能多的相关意义。

我们进一步认为，E 0）将替代I F 1。让u=u0,u1,u2……发电机产生的序列。那么可以想象，这种“正确”的顺序）就是E.我们可以看到的）是由于干扰的z=z0，z1，z2…误差概率为1的2，其中z是由同一台发电机接收，但结合功能i而不是f。由于我们选择了相当大的误差概率，误差概率将是很小的。

让我们说我们可以看到序列段…，u^+n-1.各种各样的意义，z++n-1是一个线性码的长度N。然后，观察顺序U的片段，你可以通过纠错修复Z序列。这是一个赢得，z的线性复杂性远远低于u的线性复杂度，并且足够短的序列长度，以恢复递归律和寄存器的初始状态用伯莱克坎普-梅西算法。

在此指出，f函数与仿射函数的关联值可以从下面通过其非线性来评价：E^ 2n-2Nf。因此，因此

更高的非线性，更少的最大相关，这意味着更多的机会，在模拟噪声通道出错，从而使快速相关攻击不可能发生。在组合式f函数发生器。

8.2。线性密码分析的想法在1993。日本的密码M.Matsui提供了一个统计方法分析密码DES称为线性密码分析。描述了最简单的工作修改的想法[20]）算法1。

让P，C，K块打开文本，代码和一些块密码的关键。密码的线性近似叫做比例（

算法1.线性密码分析1：我们找到了一个线性的加密近似，对它的最大。2:00在N对抽样中固定未知密钥时）p，s3:对于每个样本对，我们计算步骤1中选择的左侧值。N0是零，N1是零，N0+N=N。

4：）我们认为（7），K）=0，如果（

结果发现，一个线性的比值为未知的关键位，因此，可以减少从2k到2k-1的完整的中断，在k-关键的K位数。有一个更强大的线性密码分析的修改，允许你立即找到一组未知的关键位，但它仍然是相同的-寻找线性逼近，但不是所有的密码，但它的一部分。

方法的基本复杂性在于如何找到线性逼近。在实践中，它是这样做的：分析为S-区块执行的比例，然后扩大到多个回合和大多数P，C，K。

让S-块密码设置矢量（（1/2++）（2n-1-d）【a.x】（b，F）【J】）/2n.同样，对于流水密码，为了成功的攻击，也就是说E.最大（e），必须最大限度地减少距离（d）：（a，J，），（b，F）：）所有可能的非零（E ^，B E ^ F ^ F ^。因此，对这次攻击的反应是，在所有可能的非零度（a）中，选择（d）至（a）、（j）、（b）、（F）等矢量函数作为S-区块。b尽可能多。请注意，这相当于审议F函数（b），F）的非线性。

8.3。[直义]理论结果和公开问题以工作为基础。[42]，25]让f-布尔函数从n变量。以前，我们已经获得了一个估计的Nf ^ 2n-1-2n/2-1非线性，这是在偶数n Bent函数实现。在一般情况下不知道最大非线性的奇数精度变量。例如，在n=1,3,5,7 f的nf ^ 2n-1-2）n-1的变量中，发现了n-1的^ 2，这是一个正方形函数的估计值；但在奇数的n-7的函数存在，严格大于2n-1-2的非线性）n-1/

定理6非线性随机函数）（有一个常数C，这是几乎所有的布尔函数从n变量Nf ^ 2n-1-2cy/n2ra 2-1。

结果显示，任意函数的非线性接近于上限，但往往是这样的，寻找高非线性的具体功能是一个非动态的任务。

在下一个理论，我们将介绍一些已知的事实，Bent函数。

定理7.

1。本特函数的所有变量都有很大的不同。

2。对于Bent-f函数从n个变量正确wt）Distr.-1±2n 2-1.

3。对于Bent-f函数从n个变量是正确的deg）^ n/2。

4。梅奥兰麦克法兰设计。让p-任何对多个FF的置换；h-任意布尔函数从n/2变量。然后（f）“，”）=）j'（p）（（

从理论7的批准3和4可以从n变量获得Bent函数类功率估计数。

批准3评价（bn）。公正的：：（2）2 n/2！^ Bn^22-1+cn/2.

人们知道，评价数据有所改进，但在质量上仍有改进。可以看出，随着n的增长，估计差距变得非常大。在这方面最紧迫的未决问题是确定海底函数的确切数量，或至少确定更适当的海底函数级功率估计数。这反过来又与寻找新的结构有关。[42]对此有更详细的说明。

现在我们来看看矢量布尔（n），T-功能F。我们看到，为了对抗线性密码分析，应该选择作为一个S-块功能，其组成函数很高的非线性。因此，矢量函数的非线性被定义为Nf=min Nv f）。因此，也公平评价Nf ^ 2Distr.-1-2n 2-1.非线性函数达到这一估计数，也被称为矢量本特函数。问题是，它们是否总是存在的？

第8定理本-函数的存在）。在M ^ n/2，其中n是明确的。

第9号定理）m^ n-1任意世纪的非线性

你找不到你想要的吗？尝试一个参考工具。

1 I）2Distr.-第一份工作）Distr.页：1

f函数是有效的估计NF ^ ^ 2±1——3•2n-2-2。

在n=t的情况下，从女护士的评价可以看出，NF ^ ^ 2±1-2）（同时我们知道，估计是准确的。最大非线性n，^函数存在于奇数n时，被称为几乎本特函数）但在下列情况下，最大非线性问题仍然悬而未决：

（a）n为奇数，m为n-1；

b）偶数和n 2/m n-1。

9。统计独立性

统计独立性概念是在审议职能的统计模拟时引入的[4]。

定义12.布尔函数f与n变量的统计不取决于其变量的子集U={x^，{Xik}，如果P[fia1。……，……，如果F]=0]=P[F=0]任何值，作为G F2。

对统计独立性进行公正的建设性检验。

定理10）统计独立性的标准。布尔函数（f）x.y）取决于n+m变量，其中x G F ^，和G FM，统计不取决于X的变量，除非和只有当WF ^ u，0）=0任何U G F。

9.1。从这两个时间

让F：FN x F2 ^ F ^。该函数可以是，例如，用长r键将n长度的开码块转换为m长度的代码块。

定义13.F函数的统计模拟方程^ ^ x.y，k）=0，其中x G Fn，y G FM，k G F2关系Y=F）x，k）和：Fn x FM x F2 ^ F2的函数是x，k）^ ^ x，F）x，k（k）统计不取决于变量的X。P==0）数被称为概率

统计模拟，在p=1/2模拟是有效的。

有效的统计类比被认为是与代码线性近似的相同目的，在P.8.2.，-用一些简单的方程来模拟密码，这些方程将开放文本位、代码文本和密钥连接在一起，具有一定的概率。但它们之间的重要区别是，与方程相关的函数在统计学上并不取决于开放文本的变量符号，这保证了在将开放文本和相关代码的任何值替换时，这一方程仍然有可能实现。

工作文件[4]还讨论了类似于“简单而复杂”方法的统计模拟问题，也就是说，统计模拟方法是一种“简单而复杂的”方法。E.如何建立整个密码的统计类比，从统计模拟其简单的成分。例如“”两个离散函数的叠加位置由其中一个在内部）和统计模拟另一个在外部）确定，并显示如果相加性所产生的叠加函数是第一个叠加函数的统计模拟功能，其外部函数统计模拟概率”[4]此外，还提供了用线性和非线性统计模拟系统的解决方案来对块加密进行加密分析的算法，这些模拟系统的加密功能采用了最大的似然性方法。由DES代码实例支持。

10。代数免疫性

让布尔函数从n变量f给定。布尔函数g从n变量称为f函数的零化器，如果fg=0实现了平等。

定义14.f）函数的f）值被称为最小的d数，存在g级d的零位整数，不等于f或f 1的函数。

10.1。这是一个很好的人。

在解释布尔函数的代数免疫性定义之前，必须指出以下几点。一般来说，任何代码，无论是连续的还是块的，都可以用布尔方程组的形式来描述。

这是关键位，打开的文本和代码。因此，如果我们知道在一个未知的密钥中的几个公开的文本和代码对，你可以尝试将它们放在这个系统中找到的关键。这种系统的独特之处在于它是共同保证的，但对于实际加密来说，解决办法似乎很难。众所周知，在一般情况下，解决非线性布尔方程组问题是困难的。

有一些方法来解决非线性逻辑方程（非线性逻辑）系统，详细了解他们的工作。P.[2]俄罗斯联邦我们描述他们中的一个。由于线性布尔系统有一个有效的高斯方法，在一般情况下，一个自然的想法是试图使非线性系统线性，但更多的变量。这就是所谓的线性化方法。然而，系统的代数幂越高，在一般情况下必须输入更多的变量。

因此，一个中间问题是：首先，是否可以在不丧失解决办法的情况下减少系统的规模，然后再采用线性化方法？2003年N.Courtois和W.Meier[29]提出了基于方程组度降低的滤波器振荡器代数密码分析。后来，这种方法也被用于组合发电机和块加密，并形成了布尔函数代数免疫性的最终概念。[根据本手册对过滤发电机进行代数密码分析的想法]

考虑函数h从n变量的过滤发电机。如果（f）=J）=）=（C，J）使用LFS的递归定律，其中c G F ^，然后在下一个i-m的工作节奏，我=1，2。……，过滤功能的输入是由矢量线性函数L ^ K ^的价值，其中L）【xn ^ u我】““，，W）=LP-2。（……，W0，f）【xn.u.i】【WO】和K==）kn-i【k0】-寄存器的初始状态。

如果\xA0\xA0\xA0\xA0\xA0\xA0\xA0发电机输出序列，然后

uu=h [email protected]【正确答案】【正确答案】【正确答案】】【正确答案】【正确答案】

ui=h l）k（

♪♪

UI=H^ kn-i爱

你找不到你想要的吗？尝试一个参考工具。

这些平等是由未知的K键位的布尔方程的非线性系统，如果已知的序列段{}。现在我们试图降低方程的程度。假设满足下列一个或两个条件：

1）有一个函数g，这是什么（

（2）存在着一个小的g f 0功能，就是（

然后我们可以降低方程的程度如下：

如果ui=0，而不是^ ^李），）kn-i.……，k0）=0看方程^李）kn-i，

……“，”k0“

如果ui=1，而不是^ ^李），）kn-i.……，k0）=1看方程g）kn-i，…

……“，”k0“

请注意条件1。我们有hg=t；h的房屋平等，获得hg=h。因此，t=t h，或（重复条件1，我们得到：

1'）有一个函数=0个小的程度，如：））G）F 1修正

因此，为了防止具有l功能的过滤发电机的代数密码分析，所有d功能，如LD=0或（deg）（g）级相当大。l函数的代数免疫性称该函数的最小值为d.

10.2。二.基线成果和与非线性的关系

[评论]24[指出一些已知事实。

很容易看到，deg）/）是对功能的代数免疫性的自然上评价。此外，下一次仅根据P变量数进行的代数免疫上一次评估是公平的。

定理11上一次估值）对于任意的布尔函数/从P变量完成1）^ ^ P/2，其中[K]的整数部分。

但众所周知，这种评估是可以实现的，下一个理论中的例子就证明了这一点。

定理12最大值的函数）下列变量的函数具有最大的代数免疫性±P/2

嗯…如果^-^ж）GP/2

（1）对于奇数（1）：/）我

1'u 1，如果^ ^ ^ж）g/g 2；

如果^）/2，则^）/2

E{0.1}，如果----Y）=P/2，1，如果^ ^ J）P/2。

虽然存在着最大代数免疫机能的例子，但对这一类功能知之甚少。另一个有趣的事实是，它表明，随机函数的代数免疫率相当高。

定理13是随机函数）。对于任何一个A ^ 1和几乎所有的布尔函数/变量是由1 ^ ^ 2 ^ 2•1 P）^ 2 ^ 2 ^ 1 P2

综合了代数免疫的概念以备万一）【t-函数可以通过工作来了解】【25】

我们还提供了一个已知的，精确的低非线性函数估计通过其获得的代数免疫性。C.[10]

定理14关系1和A）。对于布尔函数/从p变量参考-1）//2。

a/^ 2 ^ SP-1利维估计数

G=0

尽管根据这一评估，函数的非线性和代数免疫性的顺序是“不矛盾的”，高代数免疫率并不能保证高非线性。的确，在理想的GP/2代数免疫率下，^这一估计是：A/^ 2P-1-c）^ P ^ 11/2在奇数p和A ^ 2P-1 ^ 2在偶数p时。正如我们在P.8.3，这一估计距离函数2p-1-2p/2-1的最大非线性值很远，而且离随机函数的非线性也很远）（

你找不到你想要的吗？尝试一个参考工具。

11。仿射度和k-正规度

定义15.布尔函数f从n变量被称为k-仿射，0 ^ k^ n-1，如果有一组1 ^ ii…ik^ n和价值“，，ak G F2，如f次级函数1'i”

定义16.laf布尔函数f的仿射值叫做最小的非负整数k，对于后者f为k-仿射。

这一布尔函数参数已在拟议的O中作了审议。啊。洛加乔夫，A.啊。萨尼科夫，в.B.穿山甲攻击联合发电机[12]它涉及到一种线性化方法的可能性，而不引入新的布尔方程系统变量描述发电机的工作。复合函数的仿射性越低，越有效的密码分析。关于laf的详细研究在m.l.l.布里亚科夫[6]除其他外，研究了该参数与其他基本加密特性的关系。我们注意到，众所周知，仿射能级渐近行为，这表明它很高。

第15条定理（在n ^为几乎所有的f元函数的^从n元正确n-[log 2 nj^ laf^ n-~ log 2 n]+1.

[27,31]在外国文学中引入了类似的概念—k-规范性。

定义17.布尔函数f从n变量k-正规，如果有k维数的仿射子空间，在其中f是恒定的。

有一个成功的例子是成功的密码分析的主要依据是它使用的5个变量的过滤函数有一个低的标准阶，即它的2-正常。

12。微分一致性

人们普遍认为，在1990年代初期，由于对块加密进行了区分性密码分析，因此出现了K.Nyberg[38]号文件中的差异性功能定义，由E.Biham提议，A.Shamir为编码器DES 1990。但必须指出的是，这一概念所采取的办法实际上是1960年代苏联所考虑的，正如第7段所指出的那样。

定义18.布尔向量（n），t-函数F被称为微分8-均匀，如果任何一个（a=0，b方程F）F）F）F）F）F F（a）=b有不超过8个解决方案。

很容易看到，最小值为8等于2n m。

定义19.矢量布尔n，t-函数F被称为完全非线性的PN-函数，如果它是微分2p \ u t-一致。

对PN-函数的同等定义如下：

定义19。F-PN函数，如果其DAF衍生物在所有非零方向a G Fn的平衡，也就是说，在所有非零方向上都是相同的。{G Fn：Da F）{y}=所有的2n

y g FM。

请注意，在m=n PN函数不存在，因为如果F（J）方程的解法f）f（f）f（a）=b，那么F（a）也是他的决定。

定义20.矢量布尔n，^函数F几乎被称为完全非线性）【APN-函数，如果它是微分2-一致的。

12.1。微分密码分析思想

描述了组件加密的微分密码分析的想法，遵循工作【20]）算法2。考虑迭代块代码，由g圆。指定开放文本P，P，中间代码后的类型-C，C和最终代码-C，分别。一对向量，被称为一个类型-M的差异的密码，如果有开放的文本，R，如R R R=A和C=C。在这种情况下，概率-一个类型的差速器），”a,l'是一个值[p][c]=R R”

算法2.微分密码分析1：选择最有可能的）g-1型差速器。

2：在一个固定的未知键的N 4抽样

{p，p，c'，c'，如R=A。3:打破循环连接公斤，解密每对N对c，s”

在GSG-1、GSG-1和GSG-1、GSG-1、GSG-1、GSG-1、GSG-1、GSG-1、GSG-1、GSG-1、GSG-1、GSG-1、GSG-1、G4:关键，对于这个关键，俄罗斯联邦总统法令规定了平等的原则。3经常执行，我们认为是正确的。

12.2。PN和Bent函数的联系，开放的问题

关于APN函数

首先，注意完全非线性函数和p中所考虑的最大非线性函数的密切联系。8。

首先，标题本身“完全非线性”反映了这些功能在某种程度上也与最简单的线性功能有很大的不同。事实上，如果L是线性的）（（

第二，原来的PN函数类与Bent函数类！[22]根据审查结果，W.Meier、O.Staffelbach为布尔函数引入了完善的非线性概念。很快就发现，完全非线性函数与本特函数完全一致，本特函数早在1970年代就由O.S.Rothaus承担，下一个理论反映了这一点。

你找不到你想要的吗？尝试一个参考工具。

本-函数及其衍生物的定理16）。布尔函数f从n变量-Bent-函数的时候，只有当DAF导数在所有非零方向A E F ^平衡。

从矢量本位函数定义（1）可见。P.（3）和16定理表明，PN函数类和矢量本特函数类是一致的。因此，PN函数只存在于m ^ n/2。

一个有趣的未决问题是，APN函数的非线性是否同样高？我们知道以下论点。

13.核准4。F-APN函数，只有当它的沃尔什-阿达玛系数满足相同^ ^）u.v）=3 ^ 24n-2 ^ 23

3ga

这一恒等式不允许对APN函数的非线性估计，但它表明，任何AB-函数都是APN。因此，与本条一样，AB-函数在两个密码标准方面是最佳的。但一个大的负AB函数是因为他们只存在于奇数变量，这是不方便的实践。关于APN函数的非线性，可以肯定的是，它不是等于零。所有已知的APN函数的例子表明，他们的非线性是相当高的，但它的下或上的非平凡的估计数，即使是平方函数的情况下。

值得注意的是，在奇数变量的情况下，还有一个APN功能，这不是一个AB。一个已知的例子是一个元素在F2n:F）的最后一个值的反演函数=R2。如M.M.审查所述。毫米。[7]此功能的最佳性质由в.啊。发表於啊。叶戈罗夫早在1968年。注啊。叶戈罗夫还显示，对于偶数n，相应的代换不是APN函数，而是微分4-一致。这是八个变量的函数作为已知的代码AES S块。

因此，我们在APN功能领域面临的第二个紧迫问题是，在偶数变数的情况下，存在着APN代换。计算测试了两个和四个变量的函数，甚至有一个假设的问题的答案是否定的，在一般情况下，答案是正确的。可以想象，当2009年。在J.F.Dillon等的加密会议上。提出了六个变量的一个共同的APN函数。“The discovery in 2009 of an APN permutation in a field of characteristic 2 and even dimension has brought new motivation and new ideas to this field of research”[22]目前，所有努力的目的都是寻求对这一问题的答案，特别是对作为加密政策的八个变量的答案。注意本文中的第15条。]H.萨奇科夫正在发展一种新的组合方法来研究和构建一个共同的APN函数的方法。

还有一个有趣的问题。在工作中（

规则：yF）a，b）=1，其中，a，b，E F，如果A=0和F）x F）F）x F（A）=B有解决方案，和yf）a，b）=0其他。下面的连接已经建立。

13.核准5。让F-）n，p-函数。6.公平指控：

（1）F-APN-函数的时候，只有当wt）=22n-1-2n-1；

（2）F-AB函数在且只在Yf-Bent函数的情况下。

13。特殊函数的可分解性

这种矢量布尔函数的性质是为了解决数据掩蔽问题，这是由于第三方渠道攻击的出现而产生的。加密算法很容易受到这种攻击，其目的是为了削弱算法的实际执行。密码分析师研究了具体的参数，如所需的功率，运行时间，电磁辐射。通过比较他们在不同的输入数据和收集一些统计数据，他可以获得关于秘密密钥的信息，在设备中执行的操作及其参数。作为对策，采用的方法是将输入数据掩蔽起来，以确保计算工作不会明显依赖于这些数据。

定义21.阈值划分（n），t-s在r部分的功能被称为nr，t-sj，j=1.…，r，具有下列特性：

S

正确的。对于所有的x=）X1，xn）是真的：S），（xn）=Sj）……，xr）

j=i

对于任何HG=）X1……1.1.1.1.1.1.1.1.1.2.1.2.2.2.2.2.2.1.1.2.2.1.1.2.1.1.1.2.1.1.2.1.1.1.1联合国

不完全的。每一个函数的Sj，j=1……，r，独立于xj变量。

S

均匀性对于任何向量Y，1…，yr e f^如fyj=y，常开

j=1

（2）r-1）m-n.S-1）y.任何j=1.…注

理论证明，如果一个向量函数而不是一个矢量函数实现其在氪星系统的阈值分解，这将使系统稳定在一级的能量消耗的微分攻击（直观的，函数的R部分的阈值分解是一种分配的秘密输入值x-r的球员之间的x-r向量x j，j=1的方案……，r.在这种情况下

你找不到你想要的吗？尝试一个参考工具。

什么样的G-1玩家不能恢复秘密，这是由不完全的分拆要求：每个人都不依赖变量-7，因此，即使知道它，我们不能恢复X的原始输入值。正确性的要求是自然的：阈值的分拆实现了与原始函数相同的转换。为了确保各轮之间的“正确过渡”，需要有均衡性。E.在进入下一轮转换时要均匀分配值。

自然的问题是：函数5的最低克值是什么，对该函数有5/克的阈值？这是一个现实的问题，因为它直接关系到整个密码算法的规模和成本。众所周知，对于d的代数幂函数，d的最小值不小于d++1。在这种情况下，通常很容易建立一个只满足校正和不完整特性的阈值，更难确保一致性。此外，研究表明，从少变数数量到少变数数的单值函数中，21[不是所有的d级函数，你可以建立一个d+1的阈值，我们称之为最小的部分。因此，提出了一个开放的数学问题：是否可以选择一些容易测试的特征，这些功能，谁有最低限度的界限划分？如果没有最低限度的，那么是什么？

由于这些问题暂时还没有解决，该方法的开发人员走上了他们所说的道路，最小的阻力：我们找不到最小的分解-我们寻找的阈值的划分为更多的部分。例如，计算表明，从不超过五个变量中的任何一个相互作用的函数都可以被定义为5个部分的阈值。但是，必须在出售的规模和价值之间达成妥协。因此，另一个想法也得到了推广：那些无法找到最小的分解的功能5，作为两个或两个以上的功能的合成，如5==P O O C，这两个系数一个较低，另一个较容易确定最低限度的分拆阈值。

14。乘法复杂性

简单地提一下另一个方面，即利用面包作为密码要素。

定义22.乘乘（对于基础{f，1}中的任何一个e-p（p）{p}来说都是必要的和足够的。

功能的乘法复杂性与使用密码的硬件的大小和成本有关。函数的乘法复杂性越小，其方案的实现就越容易。这一点特别适用于所谓的“轻易的”（

如前所述13、在现代化的硬件执行中，需要隐藏所进行的计算，以防第三方渠道的攻击，而且重要的是把不同的面具是执行的非线性变换。因此，越少越好。虽然正如44所指出的那样，实现两位数的复杂性（在这种情况下，使用乘法复杂性是否更为有效？

[28]我们还注意到，存在着一种假设，即实现整个代码的低乘法变换的复杂性可能恰恰相反地反映出它的弱点，具体而言，可以使用密码代数密码分析。

15。线性集

该方法是由G.P.[直义]3.

让我们有一些5个布尔方程组。

定义23.5系统的X变量子集叫做线性化，如果系统中的这些变量的值被任何固定，后者变成一个线性方程组。

请注意，线性多变量系统的功率可以通过引入辅助变量降低。

让十一，x-系统变量5.如果一组值a ^…，是系统5的完整解决方案，任何子系统a…1 ^ ^ ^ ^ ^ ^ ^ ^分别^ ^ ^ K，称为系统的部分解决方案。如果将其替换成系统使其线性，则部分解准完整。

15.1。一个想法的L和N E E E E E E E E E E E E E E E E和Z Z Z E E和O O O O O E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E

关键流发生器的工作可以用一个布尔方程组的方式来描述，如果已知的输出序列的某些有限段。线性攻击的本质是寻找尽可能少的该系统的功率和相应的准全系统解决方案的线性多变量。事实上，通过执行从一个线性集的变量值的过量，并检查联合线性方程组，在代入数据时获得的值，可以找到该系统的准完全解算，从而也可以用多项式的复杂性来完全解得到的线性方程组。在这种情况下，攻击的复杂性估计为2 x，其中x-x是线性集变量的功率。

为了说明这次攻击的工作，我们提供了一个组合的发电机乌耶伊，由三个最大的长度，1,2，3相应地，并结合功能f）【x,u,g]=胡夫描述发电机工作的布尔方程组，如下：

11-t*1-g*2-g*2-g*3-g*3*

杜^ ^ HH ^ A ^ HH ^ L ^ ^ ^

1-1

==F，^=0，^类型=0〜2-1

0，^ 0

类型=0-3-1

3+*=F，^=0，^

类型=0

X

1 P-4，1 P-3，1 P-3，1 P-2，1 P-3，1 P-2，1 P-3，1 P-2，1 P-3，1 P-2，

，t-1-2，

你找不到你想要的吗？尝试一个参考工具。

，t-1-3，

在T ^ Shah 1，2，3；；和0，1，……，信息1-已知的初始输出序列段；和*一些给定的常数。未知的关键位变量是1…，X2……1，x 2-1，x 0，……，x 3-1.在这种情况下

X={R2”…,x12-1}形成线性化系统的许多变量。因此，线性攻击该发电机可以实现不超过2 ^ 2通过测试的X变量值集的困难。这种攻击的复杂性是在下面，（与相关的）见下一篇：http://www.xxdoc.comwww.xxdoc.comwww.xxdoc.comwww.xxdoc.comwww.xxdoc.comwww.xxdoc.comP.7.1.——复杂性2.1+2+2

对于交替控制的发电机、多路复用发电机和标量乘法发电机，同样的结果也公平。

结论

作为一个结论，我想指出数学的美，这是隐藏在密码学的布尔函数，特别是在非直线的不同意义。似乎Bent-函数或ARA-函数的定义也可以理解学生，而完全描写他们的阶级）（甚至找不到可以接受的估计这些类的能力）是不可能的著名的数学家！很可能，这些问题的答案）（这些问题迟早会出现）在应用上不会如此重要，然而，他们会很好奇的数学本身。

在本次审查中，我们对不同的加密特性之间的联系几乎没有加以说明。实践表明，作为密码的一个组成部分，必须选择“从各方面都很好”的功能，这实际上是一个非常困难的任务，因为许多特性有时相互矛盾。虽然，正如我们所看到的，理论结果表明，随机函数的许多密码参数接近最佳。问题是，如何选择它，偶然？

作者感谢同行的宝贵评论和补充。

参考资料

1。阿吉巴洛夫山P.最喜欢的初级加密理论：学习。参考资料托木斯克：2005年4月116C。

2。阿吉巴洛夫山P.解决多项式方程组的方法/托木斯克国立大学学报。附件。2006。编号17.C.4-9。

3。阿吉巴洛夫山P.托木斯克国立大学通报关键流发电机加密分析中的逻辑方程。附件。2003。编号6.C.31-41。

4。阿吉巴洛夫山潘克拉托夫и.啊。离散函数统计模拟理论要素，用于对迭代块加密/应用离散数学进行加密分析。2010。编号3.C.51-68。

5。阿尔费罗夫A.牙齿，牙齿库兹明а.谢列穆什金B.基本密码。M.：GELOS ARV，2002.480C。

6。布里亚科夫角l.l.布尔函数的仿射限制参数的代数，组合和密码性质：迪斯。嗯….kand。数学的科学。M.，2007年。

7。格卢莫夫角毫米。关于完全和几乎完全非线性函数//数学加密问题。2016。在报刊上）

8。格卢莫夫角毫米。有限域的平面映射和概括。会议介绍“代数和逻辑，理论和应用”。克拉斯诺亚尔斯克，2013年7月21-27日。

9。戈罗季洛夫A.啊。通过子函数//离散数学来描述几乎完全非线性函数。2015。因为27。干杯。C.3-16。

10。洛巴诺夫角C.非线性和代数免疫之间的精确关系//离散数学。2006。因为18。干杯。C.152-159。

11。洛加切夫岛密封圈发表於в，蜥蜴в.B.布尔函数在编码和氪学理论。第二版。M：国际海洋法法庭，2012年。584C。

12。洛加切夫岛密封圈蜥蜴в.B.相关免疫性和真实保密性/数学和信息技术安全。公司简介2003年10月23日至24日，莫斯科M：排雷中心，2004年。C.165-171。

13。潘科夫H.具有给定的密码特性的二进制显示数的渐近估计数//加密的数学问题。2014。因为5。干杯。4。C.73-97。

14。潘克拉托夫и.啊。布尔函数的密码：学习。参考资料托木斯克：托木斯克国立大学出版社，2014年。88 C.

15。萨奇科夫H.组合性能差2-均匀置换//数学密码问题。2015。因为6。干杯。1。C.159-179。

16。谢列兹涅夫S.H.逻辑代数的一些函数的乘法复杂性//离散数学。2014。因为26。干杯。4。C.100-109。

17。斯梅利捷夫B.关于一些二进制序列变换类的密码弱点//应用离散数学。2010。页：1C.5-15。

18。苏马罗科夫S.H.禁止二进制函数和一类编码装置的可逆性，//应用数学和工业数学评论。1994。因为1。干杯。1。C.33-55。

19。塔兰尼科夫B.相关免疫功能和稳定的布尔功能//ma-metic。控制论的问题。2002。干杯。11。C.91 148。

20。托卡列夫山H.对称加密短训班：学习。参考资料新西伯利亚：新西伯利亚国立大学，2012年。232 C.

你找不到你想要的吗？尝试一个参考工具。

21岁。比尔金布、尼科夫斯、尼科夫斯等。小型S盒的阈值实现//密码和通信。2015年。五、 7号。一号。P、 3-33岁。

22岁。Blondau C.和Nyberg K.完全非线性函数与密码学//有限域及其应用。2015年。五、 32岁。P、 120-147。

23岁。布尔函数和S盒的密码性质。2006年，鲁汶大学，博士论文。

24岁。Carlet C.《用于密码学和纠错码的布尔函数》/《数学、计算机科学和工程中的布尔方法和模型》专著第8章，剑桥大学出版社，2010年。P、 257-397年。

25岁。Carlet C.用于密码学的矢量布尔函数//《数学、计算机科学和工程中的布尔方法和模型》专著第9章，剑桥大学出版社，2010年。P、 398-472。

26岁。Carlet C.，Charpin P.和Zinoviev V.适合于DES（如加密系统）//DES）的码、bent函数和置换。密码密码。1998年。五、 15岁。P、 125-156页。

27岁。Charpin P.正规布尔函数//J复杂性。2004年。五、 20岁。P、 245-265页。

28岁。Courtois N.，Hulme D.和Mourouzis T.解决密码学和密码分析中的电路优化问题。密码学ePrint档案。报告2011/475（2011年）。

29岁。Courtois N.和Meier W.线性反馈流密码的代数攻击//LNCS。2003年。五、 2656年。P、 345-359。

30岁。库西克T.W.和斯坦尼卡P.密码布尔函数和应用。阿卡德。按。爱思唯尔，2009年。245页。

31岁。Dobbertin H.高非线性bent函数和平衡布尔函数的构造//FSE'95。LNCS公司。1995年。五、 1008年。P、 61-74岁。

32岁。EvertseJ.H.《分组密码中的线性结构》/《欧洲密码》87。LNCS公司。1988年。五、 304年。P、 249-266页。

33岁。Fon Der Flaass D.G.A在相关免疫上的界限//《西伯利亚电子报》。垫子。伊兹夫。2007年。4号。P、 133-135页。

34岁。高利基Dj。非线性滤波器发生器的安全性研究//FSE'96。LNCS公司。1996年。五、 1039年。P、 173-188年。

35岁。Gorodilova关于APN-Gold函数的一个显著性质。密码学ePrint档案。报告2016/286（2016）。

36岁。Mihaljevic M.，Gangopadhyay S.，Paul G.，和Imai H.Grain-v1//Proc内部状态恢复算法。CECC 2011年。匈牙利德布勒森，2011年6月30日至7月2日。P、 7-20岁。

37岁。Nikova S.，Rechberger C.和Rijmen V.针对侧信道攻击和故障的阈值实现//LNC。2006年。五、 4307年。P、 529-545。

38岁。Nyberg K.密码学的微分一致映射//Eurocrypt'93。LNCS公司。1994年。五、 765年。P、 55-64岁。

39岁。PreneelB.，Van Leekwijck W.，Van Linden L.，等人。布尔函数的传播特性//Eurocrypt'90。LNCS公司。1991年。五、 473号。P、 161-173页。

40岁。Siegenthaler T.《密码应用中非线性组合函数的相关性抗扰性》/《IEEETrans》。通知。理论。1984年。五、 30岁。5号。P、 776-780。

41岁。Tarannikov Y. V.推广了适当的矩阵，并构造了参数为/ /西伯利亚EELKTRON的具有最大非线性的具有最大非线性的M-弹性布尔函数。垫子。伊兹夫。2014年。11号。P、 229-245。

42岁。本特函数：结果和在密码学中的应用。阿卡德。按。爱思唯尔，2015年。220页。

43岁。韦伯斯特A.F.和塔瓦雷斯S.E.论S盒的设计//Crypto'85。LNCS公司。1986年。五、 218号。P、 523-534。

44岁。Zajac P.和Jokay M. Multiplicative的双射4×4盒/密码和通信的复杂性。2014年。五、 6。3号。P、 255-277年。

45岁。张学梅，郑益.GAC-密码函数全局雪崩特性的判据//J.通用计算机科学。1995年。五、 一。5号。P、 320-337。

参考文献

一。阿吉巴洛夫G.P.Izbrannye teoremy nachal'nogo kursa kriptografii:乌切布。波索比[密码学基础课程选集：教程]。托木斯克，NTL出版社，2005年。（俄语）

2。Agibalov G.P.Metody resheniya sistem Polinominial'nykh uravneniy nad konechnym polem[有限域上多项式方程组的求解方法]。汤姆斯卡戈大学。Prilozhenie，2006年，第17期，第4-9页。（俄语）

三。Agibalov G.P.Logicheskie uravneniya v kripotanalyze generatorov klyuchevogo potoka[密钥流生成器密码分析中的逻辑方程]。汤姆斯卡戈大学。Prilozhenie，2003年，第6期，第31-41页。（俄语）

四。Agibalov G. P.和PANKRATOVA I.E.TeRiist-StististCheKikh类似物DekReTykkh Funktsiy的PrimeNeNeM V KytotoNeV迭代算法Bulnykkh SHIFROV[离散函数的统计逼近理论及其在迭代分组密码分析中的应用]。Prikladnaya Diskretnaya Matematika，2010年，第3期，第51-68页。（俄语）

我是谁？Попробуйте сервис подбора литературы.

5个。AlferovA.P.，ZubovA.Yu.，Kuz'minA.S.，和Cheremushkin A.V.Osnovy Kriptografii[密码学基础]。莫斯科，Gelios ARV出版社，2002年。（俄语）

6。Buryakov M.L.Algebraicheskie，kombinatornye i kriptograficheskie svoystva parametrov affinykh ogranicheniy bulevykh funktsiy[布尔函数参数的代数、组合和密码性质仿射限制]。博士论文，莫斯科，2007年。（俄语）

7号。Glukhov M.M.O sovershenno i pochti sovershenno nelineynykh funktsiyakh[关于完美和几乎完美的非线性函数]。Matematicheskie Voprosy Kriptografii，2016年。（将出版）（俄语）

8个。Glukhov M.M.Planarnye otobrazheniya konechnykh poley i ikh obobshcheniya[平面地图及其有限域的推广]。Pres.conf.“代数与逻辑、理论与应用”，Krasnoyarsk，2013年7月21日至27日。

9号。Gorodilova A.A.Kharakterizatsiya pochti sovershenno nelineynykh funktsiy cherez podfunktsii[子函数几乎完全非线性函数的特征]。磁盘。材料，2015年，第27卷，第3期，第3-16页。（俄语）

10个。Lobanov M.S.Tochnoe sootnoshenie mezhdu nelineynost'yu i algebraicheskoy immunnost'yu[非线性与代数免疫的精确关系]。磁盘。材料，2006年，第18卷，第3期，第152-159页。（俄语）

11号。Logachev O.A.，Sal'nikov A.A.，Smyshlyaev S.V.和Yashchenko V.V.Bulevy funktsii V teorii kodirovaniya i Kripologi[编码理论和密码学中的布尔函数]。莫斯科，麦克姆出版社，2012年。（俄语）

12岁。Logachev O.A.，Sal'nikov A.A.，Yashchenko V.V.Korrelyatsionnaya immunnost'i real'naya sekretnost'[相关豁免和真实隐私]。过程。conf.“信息技术的数学和安全”，莫斯科，麦克梅出版社，2004年，第165-171页。（俄语）

13岁。Pankov K.N.Asimptoticheskie otsenki dlya凿子dvoichnykh otobrazheniy s zadannymi kriptograficheskimi svoystvami[具有给定密码特性的布尔映射数的渐近估计]。垫子。美国之音。Kriptogr.，2014年，第5卷，第4期，第73-97页。（俄语）

14岁。Pankratova I.A.Bulevy funktsii v kriptografii:乌切布。posobie[密码学中的布尔函数：教程]。Tomsk，TSU Publ.，2014年。（俄语）

15岁。Sachkov V.N.Kombinatornye svoystva differential'no 2-ravnomernykh podstanovok[差分2-均匀替换的组合性质]。垫子。美国之音。Kriptogr.，2015年，第6卷，国际空间站。1，第159-179页。（俄语）

16岁。SeleZeNVA S.N Mul'TiPikTivnayaSLoZHONSTO'NekOtRykkh Funktsiy代数Lojik[若干布尔函数的乘法复杂性]。磁盘。材料，2014年，第26卷，第4期，第100-109页。（俄语）

17岁。Smyshlyaev S.V.O kriptograficheskikh slabostyakh nekotorykh klassov Prebrazovaniy dvoichnykh posledovatel'nostey[关于某些类二进制序列变换的密码弱点]。Prikladnaya Diskretnaya Matematika，2010年，第1期，第5-15页。（俄语）

18岁。Sumarokov S.N.Zaprety dvoichnykh funktsiy i obratatist'dlya odnogo klassa Kodiruyushichikh ustroystv[禁止二进制函数和一类编码器的可逆性]。Obozrenie Prikladnoy i Promyshlennoy Matematiki，1994年，第1卷，第1期，第33-55页。（俄语）

19岁。塔兰尼科夫。五、 O korrelyatsionno immunnykh i ustoychivykh bulevykh funktsiyakh[关于相关免疫和弹性布尔函数]。垫子。Voprosy Kibernetiki，2002年，第11卷，第91-148页。（俄语）

20岁。托卡列娃N.N.西米特里克纳亚克里普托格拉菲亚。克拉特基·库尔斯：乌切布。波索比。[对称密码。短期课程：教程]。新西伯利亚，NSU出版社，2012年。（俄语）

21岁。比尔金布、尼科夫斯、尼科夫斯等。小型S盒的阈值实现。密码学与通信，2015年，第7卷，第1期，第3-33页。

22岁。完美非线性函数与密码学。有限域及其应用，2015年，第32卷，第120-147页。

23岁。布尔函数和S盒的密码性质。2006年，鲁汶大学，博士论文。

24岁。密码学和纠错码的布尔函数。《数学、计算机科学和工程中的布尔方法和模型》专著第8章，剑桥大学出版社，2010年，第257-397页。

25岁。Carlet C.用于密码学的向量布尔函数。《数学、计算机科学和工程中的布尔方法和模型》专著第9章，剑桥大学出版社，2010年，第398-472页。

26岁。Carlet C.，Charpin P.和Zinoviev V.适合类DES密码系统的bent函数和置换。德斯。密码组，1998年，第15卷，第125-156页。

27岁。正常布尔函数。J.复杂性，2004，第20卷，第245-265页。

28岁。Courtois N.，Hulme D.和Mourouzis T.解决密码学和密码分析中的电路优化问题。密码学ePrint档案。报告2011/475（2011年）。

29岁。Courtois N.和Meier W.线性反馈流密码的代数攻击。LNCS，2003年，第2656卷，第345-359页。

30岁。库西克T.W.和斯坦尼卡P.密码布尔函数和应用。阿卡德。按。爱思唯尔，2009年。245页。

31岁。Dobbertin H.高非线性bent函数和平衡布尔函数的构造。1995年，LNCS，1995年，第1008卷，第61-74页。

32岁。分组密码中的EvertseJ.H.线性结构。《欧洲密码》87年，LNCS，1988年，第304卷，第249-266页。

33岁。对相关免疫的限制。西伯利亚电子琴。垫子。伊兹夫，2007年，第4期，第133-135页。

34岁。高利基Dj。关于非线性滤波器发生器的安全性。FSE'96，LNCS，1996，第1039卷，第173-188页。

我是谁？Попробуйте сервис подбора литературы.

35岁。Gorodilova关于APN-Gold函数的一个显著性质。密码学ePrint档案。报告2016/286（2016）。

36岁。Mihaljevic M.，Gangopadhy S.，Paul G.，和Imai H.Grain-v1内部状态恢复算法。过程。CECC 2011年德布雷森，匈牙利，2011年6月30日至7月2日，第7-20页。

37岁。Nikova S.，Rechberger C.和Rijmen V.针对侧信道攻击和故障的阈值实现。LNCS，2006年，第4307卷，第529-545页。

38岁。Nyberg K.密码学中的微分一致映射。《欧洲密码》93年，LNCS，1994年，第765卷，第55-64页。

39岁。PreneelB.，Van Leekwijck W.，Van Linden L.，等人。布尔函数的传播特性。欧洲密码，LNCS，1991年，第473卷，第161-173页。

40岁。Siegenthaler T.密码应用中非线性组合函数的相关免疫性。IEEE传输。通知。《理论》，1984年，第30卷，第5期，第776-780页。

41岁。Tarannikov Y. V.推广了适当的矩阵和构造了具有最大非线性的m次弹性布尔函数。西伯利亚电子琴。垫子。伊兹夫，2014年，第11期，第229-245页。

42岁。本特函数：结果和在密码学中的应用。阿卡德。按。爱思唯尔，2015年。220页。

43岁。韦伯斯特A.F.和塔瓦雷斯S.E.谈S盒的设计。《密码》85年，LNCS，1986年，第218卷，第523-534页。

44岁。双射4×4 S盒的Zajac P.和Jokay M. Multiplicative复杂度密码学与通信，2014年，第6卷，第3期，第255-277页。

45岁。Zhang X.-M.和Zheng Y.GAC——密码函数全局雪崩特性的判据。J、 《通用计算机科学》，1995年，第1卷，第5期，第320-337页。