用于对称密钥密码的替换盒的制作方法
专利名称：用于对称密钥密码的替换盒的制作方法
技术领域：
本发明涉及基于一组排列以替换盒(S盒)的形式使用非线性操作将一个输入数据块加密转换成一个输出数据块。
加密在数字音频和/或视频的版权保护领域的应用变得尤为重要。这些应用包括内容加密/解密和访问管理功能。对于这些应用，可以使用公知的分组密码DES。DES是一个包含16个循环的Feistel密码。在每一循环中，数据右半部的前32个比特被扩展成48个比特。使用调度算法从一个56比特的DES密钥计算出的一个48比特循环密钥被逐比特地与上述48比特模2相加。然后，S盒层对数据执行一个非线性操作。在DES中，S盒层包括八个并行6至4比特S盒，即每个S盒使用它的一个固定映射表将一个6比特的输入块转换成一个4比特的输出块。S盒层的输出是一个32比特的数据块，对其执行一个比特排列。S盒替换是DES中唯一的非线性操作，对其安全性产生很大贡献。DES的缺点在于其56比特的短密钥长度，现在认为它不足以提供更高的安全性。然而，通过使用与用于计算16个48比特循环密钥的一个不同的密钥调度算法相组合的一个更长的密钥，可以避免穷尽密钥搜索。在所公布的公开文献中对DES最强大的两种攻击是差分和线性密码分析，它们是可广泛应用于分组密码的普通攻击。已经表明不能通过修改密钥长度和/或密钥调度算法来增强DES对抗这些攻击的能力。然而，改变算法的循环函数(例如在S盒中)能够明显影响其对抗这些攻击的强度。
一个目的是设计具有优良加密特性的S盒。进一步的目的是这种S盒可以通过硬件和软件被有效地实现，允许在用户电子应用中的广泛使用。
为了满足本发明的目的，用于S盒的排列被从一组预定的排列中动态地选择。该组中的每一排列最好被选择以提供对抗已知攻击，尤其是差分和线性密码分析的最佳抵抗力。通过(伪)随机地选择排列，系统的加密性可以强于每个S盒仅包含一个固定排列的系统。可以快速有效地执行从一组中选择一个排列。
如在从属权利要求2中定义的方法，并且在从属权利要求3和6中被进一步地描述，一个排列的加密弱点通过该组中至少一个其它排列的相应强度来补偿。弱点例如可以通过具有一个预定最大概率的非普通差分和/或线性特性来反映。这种方法的优点在于在不对未知(循环)密钥进行假设的情况下，对手不能基于这些特性的差分或线性攻击。
如从属权利要求4中所定义的方法，弱点被完全补偿。
如从属权利要求10中所定义的方法，最好在一个循环密钥的控制下执行排列的选择。生成循环密钥的算法(即密钥调度算法)可以被选择以获得所需要的伪随机度。使用循环密钥进行选择的优点在于在计算循环密钥的过程中从组中选择排列。为了效率，通常并最好为每个密钥和必须使用这个密码处理(例如加密)的所有数据执行一次操作。以这种方式，该加密/解密算法可以与基于S盒的仅包括用于每个S盒的一个固定排列的系统同样有效。
参考附图中图示的实施例，本发明的这些和其它特征将很明显。
图1图示结合非线性操作的密码的一个循环；图2图示循环函数的步骤；和图3提供循环函数的S盒层的细节。
为了解释本发明，加密系统被描述为电子密码本(ECB)模式中的一个分组密码。本领域的技术人员将能够在其它模式中使用该系统。这些模式包括用于DES操作的标准FIPS模式，即操作的密码块链接(CBC)、密码反馈(CFB)和输出反馈(OFB)模式。另外，该系统也可以在用于伪随机数发生器、消息鉴别码(MAC)和操作检测码(MDC)的公知结构中使用。
该加密设备包括一个输入，用于获得一个数字输入块。数字输入块M可以是任意合适的长度。该设备还包括一个加密处理器，用于将数字输入块转换成一个数字输出块。有利地，数字输出块的长度与数字输入块基本相同。该设备包括一个输出，用于输出数字输出块。在一个优选实施例中，加密处理器通过合并数字输入块和密钥比特，生成非线性地取决于输入块和密钥的输出块，将数字输入块转换成数字输出块。为了获得密钥(或输入密钥调度器的一个初始密钥)，该加密设备包括第二输入。显然，该加密设备可以使用常规计算机，例如PC，或使用一个专用加密/解密设备来实现。数字输入块可以通过各种方式来获得。例如通过通信网络，从数据存储介质，例如硬盘或软盘，或者由用户直接输入。类似地，数据输出块可以以各种方式被输出，例如通过一个通信网络、存储在一个数据存储介质上、或者显示给用户。为此，最好使用安全装置。加密处理器可以是一个常规处理器，例如在个人计算机中使用，但是也可以是一个专用加密处理器。处理器通常在一个合适程序(固件)的控制下操作以执行根据本发明的算法的步骤。这个计算机程序产品通常从一个后台存储器，例如硬盘或ROM加载。在已经在诸如CD-ROM的存储介质上或者通过诸如公共互联网的网络被分布之后，计算机程序产品可以被存储在后台存储器上。敏感信息，例如加密密钥最好以一种安全的方式被分布和存储。这些技术是公知的，不进行进一步的描述。加密设备可以部分或全部地在一个智能卡上实现。
由加密处理器执行的根据本发明的S盒的非线性操作将以作为一个示例性应用的分组密码中的循环函数f的形式被描述。本领域的技术人员完全能够使用其它加密系统和除了下面详细描述的密码之外的其它密码中的非线性函数。
标记和定义下述标记在示例性算法的描述中被使用。假设Z2n是长度为n(n≥1)的所有二进制向量的组，和相加Z2n×Z2n→Z2n，它被定义为模2的坐标方式相加(也被称作异或，或XOR)。例如，(1，0，1，0)和(0，1，1，0)是Z24的元素，(1，0，1，0)(0，1，1，0)＝(1，1，0，0)。如果n为7和x∈Z2n，则x(L)∈Z2n/2和x(R)∈Z2n/2被分别定义为x的左半部和右半部。例如，如果x＝(1，0，1，1，0，0，1，0)∈Z28，则x(L)＝(1，0，1，1)∈Z24和x(R)＝(0，0，1，0)∈Z24。符号‖被用于标识向量的级联，例如x＝(x(L)‖x(R))。向量x∈Z2n的元素(也称作比特)被从左到右从0到n-1排序，即x＝(X0，X1，X2，...，Xn-1)。内积*Z2n×Z2n→Z2被定义为x*y＝∑i＝0，1，...，n-1xiyi∈Z2，所有的x，y∈Z2n。
分组密码结构示例性的分组密码是一个Feistel密码并包括16个循环(类似于DES)。分组长度等于64比特和密钥长度等于128比特。在密钥K∈Z2128期间将明文X∈Z264以电子密码本(ECB)模式加密成密文C∈Z264用C＝E(K，X)表示。
循环函数用f表示并且是从Z240×Z232到Z232的一个映射。这个循环函数结合本发明的非线性S盒操作，下面将详细描述。循环函数的第一输入变量是循环密钥Ki∈Z240(其中i表示循环数，i＝1，2，...，16)。这些循环密钥使用所谓的密钥调度算法根据128比特的密钥K计算出。可以使用任意合适的密钥调度算法，不详细描述。第二输入变量是循环i之后的中间结果的右半部。这个中间结果被表示为Xi∈Z264(i＝0，1，...，16)，X＝(x0(R)‖x0(L))。
使用这些标记，密文C∈Z264的计算包括下述步骤，如图1所示1.计算Xi(R)=Xi-1(L)⊕f(Ki,Xi-1(R)),]]>并设置Xi(L)=Xi-1(R),]]>i＝1，2，...，15。
2.计算X16(L)＝X15(L)f(K16，X15(R))，并设置X16(R)＝X15(R)。密文被定义为C＝(X16(L)‖X16(R))。
图1A表示用于前十五个循环的密码结构(i＝1，2，...，15)。图1B表示最后一个，第16个循环。注意与图1A的先前循环的相比，图1B中的不规则交换。这通常以Feistel结构来实现，因为在这种情况下，解密算法(即计算X＝E-1(K，C))与加密算法相同(使用相反顺序的循环密钥)。没有加密上的意义。
循环函数图2表示循环函数f的优选实施例的整体方框图。首先，在步骤210，循环密钥的一部分，例如32个比特被相加给数据比特。接着，在步骤220，S盒执行一个非线性替换，最好提供一个对差分和线性密码分析的最佳(本地)抵抗。另外，最好使具有预定最大概率的非普通(本地)特性独立于(循环)密钥，如下面更详细地描述。最后，在步骤230，一个线性转换被用于提供在多个循环上的高度扩散。可以使用任意合适的线性转换。线性转换并非本发明的主题，将不进行详细描述。
Feistel结构不对循环函数的满射性进行任何限制。然而，循环函数对于固定(循环)密钥的每种选择最好是双射的。这避免了基于循环函数非一致性的攻击。
图3提供了根据本发明结合S盒的最佳结构的更多细节。在这一示例性系统中，循环函数f是从Z240×Z232到Z232的一个映射。第一输入变量是循环函数Ki∈Z240，第二变量是中间结果Xi-1的右半部。输出用f(Ki，Xi-1(R))∈Z232表示。在该图中，Ki(1)∈Z232和Ki(2)∈Z28被定义为Ki=:(Ki(1)||Ki(2)).]]>在步骤210中，进行密钥相加，继之以步骤220，通过使用一个密钥相关替换盒(S盒)层。在这个例子中，S盒层包括八个更小的S盒(S0，S1，S2，...，S7)，每个对数据块的1/8进行操作。S盒转换是从Z28×Z232到Z232的一个映射，循环I中的第一输入变量是循环密钥Ki(2)，第二输入变量是密钥相加的结果，即Xi-1(R)Ki(l)。S盒转换的32比特输出被表示为S(Ki(2)，Xi-1(R)Ki(l))。下面将给出这一映射的详细描述。最后，在步骤230，应用一个从Z232到Z232的合适的线性转换。输入是S(Ki(2)，Xi-1(R)Ki(l))，其输出用L(S(Ki(2)，Xi-1(R)Ki(l)))表示。使用这种标记，函数f表示为f(Ki,Xi-1(R))=L(S(Ki(2),Xi-1(R)⊕Ki(1))).]]>S盒根据本发明，S盒执行数据的替换。在在此所述的优选实施例中，S盒对一个4比特的子块进行操作。显然也可以使用其它长度的子块。根据本发明，对于每个S盒，使用一组至少两个预定排列，其中在每次使用S盒之前，以(伪)随机方式选择这些排列中的一个。最好将循环密钥用于这一选择。在优选实施例中，每个S盒与两个排列相关，其中循环密钥的一个预定比特被用于选择使用两个排列中的哪一个排列。使用较小的S盒，例如对4比特子块进行操作的S盒，通常将需要一行的并行S盒，每个S盒与一组相应的至少两个非线性排列相关。在对32比特块进行操作并使用4比特S盒的分组密码的优选实施例中，并行使用八个S盒，每个S盒包括两个排列。对于该实施例，使用下述标记。假设S盒转换的第一输入变量Ki(2)的比特用Kj(i)(j＝0，1，...，7)表示，即Ki(2)＝(k0(i)，k1(i)，...，k7(i)。向量Nj(i)∈Z24(j＝0，1，...，7)被定义为Xi-1(R)Ki(l)＝(N0(i)‖N1(i)‖...‖N7(i))。S盒映射包括八个映射Sj的级联Z2×Z24→Z24(j＝0，1，...，7)。第一输入变量是密钥比特kj(i)，它选择使用Sj的两个排列中的哪一个排列。第二输入变量是Nj(i)，它是用于Sj的选定4比特排列的输入。这个排列的相应4比特输出也是S盒的输出，并被表示为Sj(kj(i)Nj(i))。使用这种标记，函数S被表示为S(Ki(2)，Xi-1(R)Ki(1)＝(S0(k0(i)，N0(i))‖S1(k1(i)，N1(i)‖...‖S7(k7(i)，N7(i)))，排列的差分和线性特性下述设计标准最好被用于各个排列
1.对差分加密分析的抵抗力XOR分布表中的最大非普通值等于一个预定最大值。假设为4比特排列，这个最大值为4，即每个非普通差分特性具有最多1/4的概率。差分特性的概念和XOR分布表是公知的。已经由Biham和Shamir于1990年首次公开描述，例如加密学期刊，1991年，卷4(1)，3至72页“类似DES加密系统的差分加密分析(Differential Cryptoanalysis of DES-LikeCryptosystems)”。
2.对线性加密分析的抵抗力线性近似表中的最大非普通绝对值等于一个预定最大值。假设为4比特的排列，这个最大值为4，即每个非普通线性特性具有1/4和3/4之间的概率。线性特性的概念和线性近似表是公知的。已经由Matsui首次公开描述。在E.Biham的“Matsui’s的线性加密分析(On Matsui’s LinearCryptoanalysis)”，EUROCRYPT’94，LNCS 950，Springer，1995，341至355页中给出了描述。
每个排列最好符合这两个规格。针对4比特非线性排列，上述标准被详细描述。可以证明这些标准对于4比特排列是最佳的，即不存在最大非普通XOR分布表值小于4的4比特排列，并且不存在其线性近似表中的最大非普通绝对值小于4的4比特排列。
符合上述标准的排列可以通过随机生成一个排列，并测试所生成的排列是否符合该标准来创建。也可以使用其它合适的技术，例如穷尽搜索直到发现一个合适的排列或使用(数学)构建方法。构建方法的一个具体例子是基于在具有2n个元素的有限域中的逆映射，零映射到其自身，并可以在K.Nyberg的“用于加密的差分均匀映射(Differentially uniform mappingsfor cryptography)”，EUROCRYPT’93，LNCS 765，Springer，1994，55至64页中发现。根据该方法构建的n比特S盒所满足的相应标准，其中n为偶数，如下给出1.对差分加密分析的抵抗力XOR分布表中的最大非普通值等于4，即，每个非普通差分特性具有最大4/2n的概率。
2.对线性加密分析的抵抗力线性近似表中的最大非普通绝对值等于2n/2，即每个非普通线性特性具有1/2-1/2n/2和1/2+1/2n/2之间的一个概率。
容易看出这些标准概括了上述用于4比特排列的标准。公知将任意可逆仿射映射(在Z2n上)应用于一个n比特S盒的所有输入元素和/或所有输出元素并不影响其最大非普通XOR值或其线性近似表中的最大非普通绝对值。以这种方式，可以从单个S盒构建满足上述标准的多个S盒。
根据本发明，一个S盒与至少两个非线性排列相关。选择该组中的排列以便它们补偿彼此的弱点。这将针对差分和线性特性分别进行更详细地描述。其它标准将使用一个S盒来说明，例如具有下述两个排列的S0
第0行和第1行表示两个排列的输出，对应于用列号定义的输入。在下文中，这两个排列将分别用P0和P1表示。输入和输出都用十六进制表示法给出。例如，如果选择第一个排列)即(K0(i)＝0)，和N0(i)＝3，则输出等于9，即S0(0，3)＝9。类似地，S0(1，3)＝f。假设8个并行S盒，每个与专用于该盒的两个排列相关，需要产生总共16个不同的排列。这些排列每一个最好都符合上述标准。根据本发明，作为一组，属于一个S盒的排列也符合下面给出的至少一个标准，并且最好符合下面给出的两个标准。
一组排列的差分特性用于一个S盒的一组排列满足下述标准如果一个排列中的非普通差分特性具有最大概率，则这个差分特性在其它排列中的至少一个排列中具有较低的概率。
将理解以这种方式使一个排列中的弱点由一个其它排列的强度来补偿。较低的概率最好为零，最佳地补偿一个弱点。因此，用于一个S盒的一对4比特排列的最佳标准是如果两个排列之一的非普通差分特性具有概率1/4，则这个差分特性在另一个排列中概率为零，即一个S盒的每个独立于非普通(循环)密钥的差分特性具有最大1/8的概率。
为了说明上述两个排列P0和P1符合该标准，它们的XOR分布表如下。在Pi的异或分布表中的行α和列β的条目(α，β∈Z24)表示为Xiα，β，并被定义为Xiα,β:=#{x∈Z24|Pi(x)⊕Pi(x⊕α)=β},i=0,1.]]>即Xiα，β等于具有差值α的输入对的数目，差值α导致在相应排列Pi的输出对中的差值β。
P0的异或分布表
对于一个给定(本地)差分特性的概率，即一个输入差值α导致一个输出差值β(表示为α→β)的概率可以通过将相应条目除以具有给定输入差值的输入对的总数来找到。对于4比特排列，输入对的这个总数等于16，所以α→β的概率等于Xiα，β/16。注意这些表中第一行和第一列中的条目表示普通特性，即概率为0→0，它对于排列始终保持。容易看出所有其它的(非普通)差分特性的概率小于或等于1/4，因为对于这两个排列，所有其它条目上的最大值等于4。
P1的异或分布表
补偿效果例如可以通过针对两个排列考虑特性7→5看出。对于P0，7→5的概率等于X07，5/16＝1/4，对于P1，这一概率等于X17，5/16＝0。这种补偿最好为尽可能多的元素出现。在该例子中，对于最大异或差值为4的所有元素，这保持不变。使用用于生成和测试排列的公知技术，本领域的技术人员可以在几天内创建八对这样的排列用于4比特排列。另外，满足标准的一对不同的排列P0*和P1*可以从P0和P1构建出，例如通过将一个仿射转换应用于这两个排列的输出。这可以通过选择Z2上的一个非奇异4×4矩阵A和一个矢量b∈Z24并为所有的x∈Z24定义P0*(x):=P0(x)A⊕b]]>和P1*(x):=P1(x)A⊕b.]]>很容易验证以这种方式可以构建322560对不同的(有序)排列，每个排列满足所有上述标准。注意这些转换之一是从Z24→Z24的恒等映射，即P0*＝P0和P1*＝P1。
一组排列的线性特性用于一个S盒的一组排列满足下述标准
如果一个排列中的非普通线性特性具有不同于1/2的最大绝对差值的概率，则在至少一个其它的排列中，这一线性特性具有接近于1/2的概率。
将理解以这种方式，一个排列中的弱点可以通过一个其它排列中的强度来补偿。一个其它排列中的对应概率最好等于1/2，最佳地补偿一个弱点。因此，对于用于一个S盒的一对4比特排列的最佳标准是如果两个排列之一的线性特性的概率为1/4或3/4，则这一线性特性在另一排列中的概率为1/2，即S盒的每个独立于(循环)密钥的线性特性的概率在3/8和5/8之间。
为了说明上述两个排列P0和P1满足这一标准，它们的线性近似表如下。在Pi的线性近似表中的行α和列β的条目(α，β∈Z24)表示为Liα，β，并被定义为Liα,β:=#{x∈Z24|x·α=Pi(x)*β}-8,i=0,1.]]>即对于排列Pi，Liα，β表示输入数减8，对于该输入数，用α定义的输入比特的线性关系等于用β定义的相应输出比特的线性关系，这是对于4比特排列的理想数目(更普遍地，对于n比特排列，理想值为2n-1)。
P0的线性近似表
对于一个给定(本地)线性特性的概率，即用α定义的输入比特的线性关系等于用β定义的输出比特的线性关系(表示为α→β)的概率等于1/2+Liα，β/16。注意这些表中的第一行和第一列中的条目表示普通特性，即概率为零的0→0，它对于任何映射保持恒定。容易看出所有其它的(非普通)差分特性的概率在1/4和3/4之间，因为对于这两个排列，所有其它条目上的最小值和最大值分别等于负4和正4。
P1的线性近似表
补偿效果例如可以通过针对两个排列考虑线性特性2→3看出。对于P0，2→3的概率等于1/2+L02,3/16=3/4]]>，对于P1，这一概率等于1/2+L12,3/16=1/2]]>。这种补偿最好为尽可能多的元素出现。在该例子中，对于最大绝对值为4的所有元素，这保持不变。使用用于生成和测试排列的公知技术，本领域的技术人员可以在几天内创建八对这样的排列用于4比特排列。另外，满足标准的一对不同的排列P0*和P1*可以从P0和P1构建出，例如通过将一个仿射转换应用于这两个排列的输出。这可以通过选择Z2上的一个非奇异4×4矩阵A和一个矢量b∈Z24并为所有的x∈Z24定义P0*(x):=P0(x)A⊕b]]>和P1*(x):=P1(x)A⊕b]]>。很容易验证以这种方式可以构建322560对不同的(有序)排列，每个排列对满足所有上述标准。注意这些转换之一是从Z24→Z24的恒等映射，即P0*＝P0和P1*＝P1。
权利要求
1.一种用于将一个输入数据块加密转换成一个输出数据块的方法，该方法包括使用基于一个排列的一个S盒在输入数据块上执行非线性操作，其中该方法包括在每次使用S盒之前，(伪)随机地从与该S盒相关的一组预定的至少两个排列选择排列。
2.如权利要求1所述的方法，其中形成该组排列，以便该组中的一个排列的加密弱点被该组中的至少一个其它排列中的相应加密强度来至少部分地补偿。
3.如权利要求1所述的方法，其中数据块包括n个数据比特，并且该组排列的每个元素是一组2n个元素的一个排列，用Z2n表示，其中该组中的每个排列的每个非普通差分特性具有最大pdiff的概率；该组排列由已被选择的排列形成，以便对于在任一排列中的概率为pdiff的每个非普通差分特性，这个差动特性在该组中的至少一个其它排列中具有低于Pdiff的概率。
4.如权利要求3所述的方法，其中差分特性在至少一个排列中具有等于零的概率。
5.如权利要求4所述的方法，其中n＝4，和Pdiff＝1/4。
6.如权利要求1的方法，其中数据块包括n个数据比特，该组排列的每个元素是一组2n个元素的一个排列，用Z2n表示，其中该组中的每个排列的每个非普通线性特性具有最少1/2-plin和最多1/2+plin的概率，该组排列由被选择的排列形成，以便对于在任一排列中的概率为1/2-plin或1/2+plin的每个非普通线性特性，这个线性特性在该组中的至少一个其它排列中具有接近于1/2的概率。
7.如权利要求5所述的方法，其中线性特性在至少一个排列中具有等于1/2的概率。
8.如权利要求6所述的方法，其中n＝4和plin＝1/4。
9.如权利要求1所述的方法，其中该组排列由两个排列组成。
10.如权利要求1所述的方法，包括在一个加密密钥的控制下执行排列的选择。
11.如权利要求9和10所述的方法，其中在加密密钥的一个比特的控制下执行排列的选择。
12.一种计算机程序产品，其中操作该程序产品使一个处理器执行权利要求1的方法。
13.一种用于将一个输入数据块加密转换成一个输出数据块的系统，该方法系统包括-一个输入端，用于接收输入数据块；-一个存储器，用于存储与一个S盒相关的一组预定的至少两个排列；-一个加密处理器，用于使用基于一个排列的一个S盒对输入数据块执行一个非线性操作；操作该处理器，每次在使用S盒之前，(伪)随机地从与S盒相关的所存储的该组排列中选择排列；和-一个输出端，用于输出处理后的输入数据块。
全文摘要
一个输入数据块被加密转换成一个输出数据块;通过使用一个基于排列的S盒对输入数据块执行一个非线性操作。该S盒与一组至少两个排列相关。在每次使用S盒之前,一个排列被(伪)随机地从该组排列组中选择出,并用于该转换。
文档编号G09C1/00GK1383648SQ01801888
公开日2002年12月4日 申请日期2001年6月25日 优先权日2000年7月4日
发明者P·L·A·雷尔斯 申请人:皇家菲利浦电子有限公司
技术领域：
本发明涉及基于一组排列以替换盒(S盒)的形式使用非线性操作将一个输入数据块加密转换成一个输出数据块。
加密在数字音频和/或视频的版权保护领域的应用变得尤为重要。这些应用包括内容加密/解密和访问管理功能。对于这些应用，可以使用公知的分组密码DES。DES是一个包含16个循环的Feistel密码。在每一循环中，数据右半部的前32个比特被扩展成48个比特。使用调度算法从一个56比特的DES密钥计算出的一个48比特循环密钥被逐比特地与上述48比特模2相加。然后，S盒层对数据执行一个非线性操作。在DES中，S盒层包括八个并行6至4比特S盒，即每个S盒使用它的一个固定映射表将一个6比特的输入块转换成一个4比特的输出块。S盒层的输出是一个32比特的数据块，对其执行一个比特排列。S盒替换是DES中唯一的非线性操作，对其安全性产生很大贡献。DES的缺点在于其56比特的短密钥长度，现在认为它不足以提供更高的安全性。然而，通过使用与用于计算16个48比特循环密钥的一个不同的密钥调度算法相组合的一个更长的密钥，可以避免穷尽密钥搜索。在所公布的公开文献中对DES最强大的两种攻击是差分和线性密码分析，它们是可广泛应用于分组密码的普通攻击。已经表明不能通过修改密钥长度和/或密钥调度算法来增强DES对抗这些攻击的能力。然而，改变算法的循环函数(例如在S盒中)能够明显影响其对抗这些攻击的强度。
一个目的是设计具有优良加密特性的S盒。进一步的目的是这种S盒可以通过硬件和软件被有效地实现，允许在用户电子应用中的广泛使用。
为了满足本发明的目的，用于S盒的排列被从一组预定的排列中动态地选择。该组中的每一排列最好被选择以提供对抗已知攻击，尤其是差分和线性密码分析的最佳抵抗力。通过(伪)随机地选择排列，系统的加密性可以强于每个S盒仅包含一个固定排列的系统。可以快速有效地执行从一组中选择一个排列。
如在从属权利要求2中定义的方法，并且在从属权利要求3和6中被进一步地描述，一个排列的加密弱点通过该组中至少一个其它排列的相应强度来补偿。弱点例如可以通过具有一个预定最大概率的非普通差分和/或线性特性来反映。这种方法的优点在于在不对未知(循环)密钥进行假设的情况下，对手不能基于这些特性的差分或线性攻击。
如从属权利要求4中所定义的方法，弱点被完全补偿。
如从属权利要求10中所定义的方法，最好在一个循环密钥的控制下执行排列的选择。生成循环密钥的算法(即密钥调度算法)可以被选择以获得所需要的伪随机度。使用循环密钥进行选择的优点在于在计算循环密钥的过程中从组中选择排列。为了效率，通常并最好为每个密钥和必须使用这个密码处理(例如加密)的所有数据执行一次操作。以这种方式，该加密/解密算法可以与基于S盒的仅包括用于每个S盒的一个固定排列的系统同样有效。
参考附图中图示的实施例，本发明的这些和其它特征将很明显。
图1图示结合非线性操作的密码的一个循环；图2图示循环函数的步骤；和图3提供循环函数的S盒层的细节。
为了解释本发明，加密系统被描述为电子密码本(ECB)模式中的一个分组密码。本领域的技术人员将能够在其它模式中使用该系统。这些模式包括用于DES操作的标准FIPS模式，即操作的密码块链接(CBC)、密码反馈(CFB)和输出反馈(OFB)模式。另外，该系统也可以在用于伪随机数发生器、消息鉴别码(MAC)和操作检测码(MDC)的公知结构中使用。
该加密设备包括一个输入，用于获得一个数字输入块。数字输入块M可以是任意合适的长度。该设备还包括一个加密处理器，用于将数字输入块转换成一个数字输出块。有利地，数字输出块的长度与数字输入块基本相同。该设备包括一个输出，用于输出数字输出块。在一个优选实施例中，加密处理器通过合并数字输入块和密钥比特，生成非线性地取决于输入块和密钥的输出块，将数字输入块转换成数字输出块。为了获得密钥(或输入密钥调度器的一个初始密钥)，该加密设备包括第二输入。显然，该加密设备可以使用常规计算机，例如PC，或使用一个专用加密/解密设备来实现。数字输入块可以通过各种方式来获得。例如通过通信网络，从数据存储介质，例如硬盘或软盘，或者由用户直接输入。类似地，数据输出块可以以各种方式被输出，例如通过一个通信网络、存储在一个数据存储介质上、或者显示给用户。为此，最好使用安全装置。加密处理器可以是一个常规处理器，例如在个人计算机中使用，但是也可以是一个专用加密处理器。处理器通常在一个合适程序(固件)的控制下操作以执行根据本发明的算法的步骤。这个计算机程序产品通常从一个后台存储器，例如硬盘或ROM加载。在已经在诸如CD-ROM的存储介质上或者通过诸如公共互联网的网络被分布之后，计算机程序产品可以被存储在后台存储器上。敏感信息，例如加密密钥最好以一种安全的方式被分布和存储。这些技术是公知的，不进行进一步的描述。加密设备可以部分或全部地在一个智能卡上实现。
由加密处理器执行的根据本发明的S盒的非线性操作将以作为一个示例性应用的分组密码中的循环函数f的形式被描述。本领域的技术人员完全能够使用其它加密系统和除了下面详细描述的密码之外的其它密码中的非线性函数。
标记和定义下述标记在示例性算法的描述中被使用。假设Z2n是长度为n(n≥1)的所有二进制向量的组，和相加Z2n×Z2n→Z2n，它被定义为模2的坐标方式相加(也被称作异或，或XOR)。例如，(1，0，1，0)和(0，1，1，0)是Z24的元素，(1，0，1，0)(0，1，1，0)＝(1，1，0，0)。如果n为7和x∈Z2n，则x(L)∈Z2n/2和x(R)∈Z2n/2被分别定义为x的左半部和右半部。例如，如果x＝(1，0，1，1，0，0，1，0)∈Z28，则x(L)＝(1，0，1，1)∈Z24和x(R)＝(0，0，1，0)∈Z24。符号‖被用于标识向量的级联，例如x＝(x(L)‖x(R))。向量x∈Z2n的元素(也称作比特)被从左到右从0到n-1排序，即x＝(X0，X1，X2，...，Xn-1)。内积*Z2n×Z2n→Z2被定义为x*y＝∑i＝0，1，...，n-1xiyi∈Z2，所有的x，y∈Z2n。
分组密码结构示例性的分组密码是一个Feistel密码并包括16个循环(类似于DES)。分组长度等于64比特和密钥长度等于128比特。在密钥K∈Z2128期间将明文X∈Z264以电子密码本(ECB)模式加密成密文C∈Z264用C＝E(K，X)表示。
循环函数用f表示并且是从Z240×Z232到Z232的一个映射。这个循环函数结合本发明的非线性S盒操作，下面将详细描述。循环函数的第一输入变量是循环密钥Ki∈Z240(其中i表示循环数，i＝1，2，...，16)。这些循环密钥使用所谓的密钥调度算法根据128比特的密钥K计算出。可以使用任意合适的密钥调度算法，不详细描述。第二输入变量是循环i之后的中间结果的右半部。这个中间结果被表示为Xi∈Z264(i＝0，1，...，16)，X＝(x0(R)‖x0(L))。
使用这些标记，密文C∈Z264的计算包括下述步骤，如图1所示1.计算Xi(R)=Xi-1(L)⊕f(Ki,Xi-1(R)),]]>并设置Xi(L)=Xi-1(R),]]>i＝1，2，...，15。
2.计算X16(L)＝X15(L)f(K16，X15(R))，并设置X16(R)＝X15(R)。密文被定义为C＝(X16(L)‖X16(R))。
图1A表示用于前十五个循环的密码结构(i＝1，2，...，15)。图1B表示最后一个，第16个循环。注意与图1A的先前循环的相比，图1B中的不规则交换。这通常以Feistel结构来实现，因为在这种情况下，解密算法(即计算X＝E-1(K，C))与加密算法相同(使用相反顺序的循环密钥)。没有加密上的意义。
循环函数图2表示循环函数f的优选实施例的整体方框图。首先，在步骤210，循环密钥的一部分，例如32个比特被相加给数据比特。接着，在步骤220，S盒执行一个非线性替换，最好提供一个对差分和线性密码分析的最佳(本地)抵抗。另外，最好使具有预定最大概率的非普通(本地)特性独立于(循环)密钥，如下面更详细地描述。最后，在步骤230，一个线性转换被用于提供在多个循环上的高度扩散。可以使用任意合适的线性转换。线性转换并非本发明的主题，将不进行详细描述。
Feistel结构不对循环函数的满射性进行任何限制。然而，循环函数对于固定(循环)密钥的每种选择最好是双射的。这避免了基于循环函数非一致性的攻击。
图3提供了根据本发明结合S盒的最佳结构的更多细节。在这一示例性系统中，循环函数f是从Z240×Z232到Z232的一个映射。第一输入变量是循环函数Ki∈Z240，第二变量是中间结果Xi-1的右半部。输出用f(Ki，Xi-1(R))∈Z232表示。在该图中，Ki(1)∈Z232和Ki(2)∈Z28被定义为Ki=:(Ki(1)||Ki(2)).]]>在步骤210中，进行密钥相加，继之以步骤220，通过使用一个密钥相关替换盒(S盒)层。在这个例子中，S盒层包括八个更小的S盒(S0，S1，S2，...，S7)，每个对数据块的1/8进行操作。S盒转换是从Z28×Z232到Z232的一个映射，循环I中的第一输入变量是循环密钥Ki(2)，第二输入变量是密钥相加的结果，即Xi-1(R)Ki(l)。S盒转换的32比特输出被表示为S(Ki(2)，Xi-1(R)Ki(l))。下面将给出这一映射的详细描述。最后，在步骤230，应用一个从Z232到Z232的合适的线性转换。输入是S(Ki(2)，Xi-1(R)Ki(l))，其输出用L(S(Ki(2)，Xi-1(R)Ki(l)))表示。使用这种标记，函数f表示为f(Ki,Xi-1(R))=L(S(Ki(2),Xi-1(R)⊕Ki(1))).]]>S盒根据本发明，S盒执行数据的替换。在在此所述的优选实施例中，S盒对一个4比特的子块进行操作。显然也可以使用其它长度的子块。根据本发明，对于每个S盒，使用一组至少两个预定排列，其中在每次使用S盒之前，以(伪)随机方式选择这些排列中的一个。最好将循环密钥用于这一选择。在优选实施例中，每个S盒与两个排列相关，其中循环密钥的一个预定比特被用于选择使用两个排列中的哪一个排列。使用较小的S盒，例如对4比特子块进行操作的S盒，通常将需要一行的并行S盒，每个S盒与一组相应的至少两个非线性排列相关。在对32比特块进行操作并使用4比特S盒的分组密码的优选实施例中，并行使用八个S盒，每个S盒包括两个排列。对于该实施例，使用下述标记。假设S盒转换的第一输入变量Ki(2)的比特用Kj(i)(j＝0，1，...，7)表示，即Ki(2)＝(k0(i)，k1(i)，...，k7(i)。向量Nj(i)∈Z24(j＝0，1，...，7)被定义为Xi-1(R)Ki(l)＝(N0(i)‖N1(i)‖...‖N7(i))。S盒映射包括八个映射Sj的级联Z2×Z24→Z24(j＝0，1，...，7)。第一输入变量是密钥比特kj(i)，它选择使用Sj的两个排列中的哪一个排列。第二输入变量是Nj(i)，它是用于Sj的选定4比特排列的输入。这个排列的相应4比特输出也是S盒的输出，并被表示为Sj(kj(i)Nj(i))。使用这种标记，函数S被表示为S(Ki(2)，Xi-1(R)Ki(1)＝(S0(k0(i)，N0(i))‖S1(k1(i)，N1(i)‖...‖S7(k7(i)，N7(i)))，排列的差分和线性特性下述设计标准最好被用于各个排列
1.对差分加密分析的抵抗力XOR分布表中的最大非普通值等于一个预定最大值。假设为4比特排列，这个最大值为4，即每个非普通差分特性具有最多1/4的概率。差分特性的概念和XOR分布表是公知的。已经由Biham和Shamir于1990年首次公开描述，例如加密学期刊，1991年，卷4(1)，3至72页“类似DES加密系统的差分加密分析(Differential Cryptoanalysis of DES-LikeCryptosystems)”。
2.对线性加密分析的抵抗力线性近似表中的最大非普通绝对值等于一个预定最大值。假设为4比特的排列，这个最大值为4，即每个非普通线性特性具有1/4和3/4之间的概率。线性特性的概念和线性近似表是公知的。已经由Matsui首次公开描述。在E.Biham的“Matsui’s的线性加密分析(On Matsui’s LinearCryptoanalysis)”，EUROCRYPT’94，LNCS 950，Springer，1995，341至355页中给出了描述。
每个排列最好符合这两个规格。针对4比特非线性排列，上述标准被详细描述。可以证明这些标准对于4比特排列是最佳的，即不存在最大非普通XOR分布表值小于4的4比特排列，并且不存在其线性近似表中的最大非普通绝对值小于4的4比特排列。
符合上述标准的排列可以通过随机生成一个排列，并测试所生成的排列是否符合该标准来创建。也可以使用其它合适的技术，例如穷尽搜索直到发现一个合适的排列或使用(数学)构建方法。构建方法的一个具体例子是基于在具有2n个元素的有限域中的逆映射，零映射到其自身，并可以在K.Nyberg的“用于加密的差分均匀映射(Differentially uniform mappingsfor cryptography)”，EUROCRYPT’93，LNCS 765，Springer，1994，55至64页中发现。根据该方法构建的n比特S盒所满足的相应标准，其中n为偶数，如下给出1.对差分加密分析的抵抗力XOR分布表中的最大非普通值等于4，即，每个非普通差分特性具有最大4/2n的概率。
2.对线性加密分析的抵抗力线性近似表中的最大非普通绝对值等于2n/2，即每个非普通线性特性具有1/2-1/2n/2和1/2+1/2n/2之间的一个概率。
容易看出这些标准概括了上述用于4比特排列的标准。公知将任意可逆仿射映射(在Z2n上)应用于一个n比特S盒的所有输入元素和/或所有输出元素并不影响其最大非普通XOR值或其线性近似表中的最大非普通绝对值。以这种方式，可以从单个S盒构建满足上述标准的多个S盒。
根据本发明，一个S盒与至少两个非线性排列相关。选择该组中的排列以便它们补偿彼此的弱点。这将针对差分和线性特性分别进行更详细地描述。其它标准将使用一个S盒来说明，例如具有下述两个排列的S0
第0行和第1行表示两个排列的输出，对应于用列号定义的输入。在下文中，这两个排列将分别用P0和P1表示。输入和输出都用十六进制表示法给出。例如，如果选择第一个排列)即(K0(i)＝0)，和N0(i)＝3，则输出等于9，即S0(0，3)＝9。类似地，S0(1，3)＝f。假设8个并行S盒，每个与专用于该盒的两个排列相关，需要产生总共16个不同的排列。这些排列每一个最好都符合上述标准。根据本发明，作为一组，属于一个S盒的排列也符合下面给出的至少一个标准，并且最好符合下面给出的两个标准。
一组排列的差分特性用于一个S盒的一组排列满足下述标准如果一个排列中的非普通差分特性具有最大概率，则这个差分特性在其它排列中的至少一个排列中具有较低的概率。
将理解以这种方式使一个排列中的弱点由一个其它排列的强度来补偿。较低的概率最好为零，最佳地补偿一个弱点。因此，用于一个S盒的一对4比特排列的最佳标准是如果两个排列之一的非普通差分特性具有概率1/4，则这个差分特性在另一个排列中概率为零，即一个S盒的每个独立于非普通(循环)密钥的差分特性具有最大1/8的概率。
为了说明上述两个排列P0和P1符合该标准，它们的XOR分布表如下。在Pi的异或分布表中的行α和列β的条目(α，β∈Z24)表示为Xiα，β，并被定义为Xiα,β:=#{x∈Z24|Pi(x)⊕Pi(x⊕α)=β},i=0,1.]]>即Xiα，β等于具有差值α的输入对的数目，差值α导致在相应排列Pi的输出对中的差值β。
P0的异或分布表
对于一个给定(本地)差分特性的概率，即一个输入差值α导致一个输出差值β(表示为α→β)的概率可以通过将相应条目除以具有给定输入差值的输入对的总数来找到。对于4比特排列，输入对的这个总数等于16，所以α→β的概率等于Xiα，β/16。注意这些表中第一行和第一列中的条目表示普通特性，即概率为0→0，它对于排列始终保持。容易看出所有其它的(非普通)差分特性的概率小于或等于1/4，因为对于这两个排列，所有其它条目上的最大值等于4。
P1的异或分布表
补偿效果例如可以通过针对两个排列考虑特性7→5看出。对于P0，7→5的概率等于X07，5/16＝1/4，对于P1，这一概率等于X17，5/16＝0。这种补偿最好为尽可能多的元素出现。在该例子中，对于最大异或差值为4的所有元素，这保持不变。使用用于生成和测试排列的公知技术，本领域的技术人员可以在几天内创建八对这样的排列用于4比特排列。另外，满足标准的一对不同的排列P0*和P1*可以从P0和P1构建出，例如通过将一个仿射转换应用于这两个排列的输出。这可以通过选择Z2上的一个非奇异4×4矩阵A和一个矢量b∈Z24并为所有的x∈Z24定义P0*(x):=P0(x)A⊕b]]>和P1*(x):=P1(x)A⊕b.]]>很容易验证以这种方式可以构建322560对不同的(有序)排列，每个排列满足所有上述标准。注意这些转换之一是从Z24→Z24的恒等映射，即P0*＝P0和P1*＝P1。
一组排列的线性特性用于一个S盒的一组排列满足下述标准
如果一个排列中的非普通线性特性具有不同于1/2的最大绝对差值的概率，则在至少一个其它的排列中，这一线性特性具有接近于1/2的概率。
将理解以这种方式，一个排列中的弱点可以通过一个其它排列中的强度来补偿。一个其它排列中的对应概率最好等于1/2，最佳地补偿一个弱点。因此，对于用于一个S盒的一对4比特排列的最佳标准是如果两个排列之一的线性特性的概率为1/4或3/4，则这一线性特性在另一排列中的概率为1/2，即S盒的每个独立于(循环)密钥的线性特性的概率在3/8和5/8之间。
为了说明上述两个排列P0和P1满足这一标准，它们的线性近似表如下。在Pi的线性近似表中的行α和列β的条目(α，β∈Z24)表示为Liα，β，并被定义为Liα,β:=#{x∈Z24|x·α=Pi(x)*β}-8,i=0,1.]]>即对于排列Pi，Liα，β表示输入数减8，对于该输入数，用α定义的输入比特的线性关系等于用β定义的相应输出比特的线性关系，这是对于4比特排列的理想数目(更普遍地，对于n比特排列，理想值为2n-1)。
P0的线性近似表
对于一个给定(本地)线性特性的概率，即用α定义的输入比特的线性关系等于用β定义的输出比特的线性关系(表示为α→β)的概率等于1/2+Liα，β/16。注意这些表中的第一行和第一列中的条目表示普通特性，即概率为零的0→0，它对于任何映射保持恒定。容易看出所有其它的(非普通)差分特性的概率在1/4和3/4之间，因为对于这两个排列，所有其它条目上的最小值和最大值分别等于负4和正4。
P1的线性近似表
补偿效果例如可以通过针对两个排列考虑线性特性2→3看出。对于P0，2→3的概率等于1/2+L02,3/16=3/4]]>，对于P1，这一概率等于1/2+L12,3/16=1/2]]>。这种补偿最好为尽可能多的元素出现。在该例子中，对于最大绝对值为4的所有元素，这保持不变。使用用于生成和测试排列的公知技术，本领域的技术人员可以在几天内创建八对这样的排列用于4比特排列。另外，满足标准的一对不同的排列P0*和P1*可以从P0和P1构建出，例如通过将一个仿射转换应用于这两个排列的输出。这可以通过选择Z2上的一个非奇异4×4矩阵A和一个矢量b∈Z24并为所有的x∈Z24定义P0*(x):=P0(x)A⊕b]]>和P1*(x):=P1(x)A⊕b]]>。很容易验证以这种方式可以构建322560对不同的(有序)排列，每个排列对满足所有上述标准。注意这些转换之一是从Z24→Z24的恒等映射，即P0*＝P0和P1*＝P1。
权利要求
1.一种用于将一个输入数据块加密转换成一个输出数据块的方法，该方法包括使用基于一个排列的一个S盒在输入数据块上执行非线性操作，其中该方法包括在每次使用S盒之前，(伪)随机地从与该S盒相关的一组预定的至少两个排列选择排列。
2.如权利要求1所述的方法，其中形成该组排列，以便该组中的一个排列的加密弱点被该组中的至少一个其它排列中的相应加密强度来至少部分地补偿。
3.如权利要求1所述的方法，其中数据块包括n个数据比特，并且该组排列的每个元素是一组2n个元素的一个排列，用Z2n表示，其中该组中的每个排列的每个非普通差分特性具有最大pdiff的概率；该组排列由已被选择的排列形成，以便对于在任一排列中的概率为pdiff的每个非普通差分特性，这个差动特性在该组中的至少一个其它排列中具有低于Pdiff的概率。
4.如权利要求3所述的方法，其中差分特性在至少一个排列中具有等于零的概率。
5.如权利要求4所述的方法，其中n＝4，和Pdiff＝1/4。
6.如权利要求1的方法，其中数据块包括n个数据比特，该组排列的每个元素是一组2n个元素的一个排列，用Z2n表示，其中该组中的每个排列的每个非普通线性特性具有最少1/2-plin和最多1/2+plin的概率，该组排列由被选择的排列形成，以便对于在任一排列中的概率为1/2-plin或1/2+plin的每个非普通线性特性，这个线性特性在该组中的至少一个其它排列中具有接近于1/2的概率。
7.如权利要求5所述的方法，其中线性特性在至少一个排列中具有等于1/2的概率。
8.如权利要求6所述的方法，其中n＝4和plin＝1/4。
9.如权利要求1所述的方法，其中该组排列由两个排列组成。
10.如权利要求1所述的方法，包括在一个加密密钥的控制下执行排列的选择。
11.如权利要求9和10所述的方法，其中在加密密钥的一个比特的控制下执行排列的选择。
12.一种计算机程序产品，其中操作该程序产品使一个处理器执行权利要求1的方法。
13.一种用于将一个输入数据块加密转换成一个输出数据块的系统，该方法系统包括-一个输入端，用于接收输入数据块；-一个存储器，用于存储与一个S盒相关的一组预定的至少两个排列；-一个加密处理器，用于使用基于一个排列的一个S盒对输入数据块执行一个非线性操作；操作该处理器，每次在使用S盒之前，(伪)随机地从与S盒相关的所存储的该组排列中选择排列；和-一个输出端，用于输出处理后的输入数据块。
全文摘要
一个输入数据块被加密转换成一个输出数据块;通过使用一个基于排列的S盒对输入数据块执行一个非线性操作。该S盒与一组至少两个排列相关。在每次使用S盒之前,一个排列被(伪)随机地从该组排列组中选择出,并用于该转换。
文档编号G09C1/00GK1383648SQ01801888
公开日2002年12月4日 申请日期2001年6月25日 优先权日2000年7月4日
发明者P·L·A·雷尔斯 申请人:皇家菲利浦电子有限公司
最新回复(0)