CN101578813A - 跟踪实现的拷贝 - Google Patents

Abstract

一种用于方便跟踪计算方法(602)的实现的拷贝(634)的系统(600)。网络生成器(604)，用于产生代表计算方法(602)步骤的查找表的网络，所述网络通过将第一查找表的输出值用作不同的第二查找表的输入值而形成。个性化器(606)，用于通过改变查找表网络中的至少一个值来产生多个不同版本的查找表网络，对应于输入值的相关域的所述版本的最终结果对于每个版本来说基本相同。相关器(608)，用于将各个版本与各个基站(610)或基站(610)的用户(632)相关联。计算方法(602)包括10种加密策略和加密密钥。

Description

跟踪实现的拷贝

技术领域

本发明涉及一种用于方便跟踪计算方法的实现的拷贝的系统。

背景技术

因特网给用户提供了对数字内容的方便和随处进行的访问。因特网用作版权内容的分配介质形成了对确保内容提供者的利益的强烈挑战。特别是，需要给内容提供者授予版权和经营模式。逐渐地，使用装载有合适的软件的处理器来运行消费电子(CE)平台。这种软件包括用于呈现(重现)数字内容(例如音频和/或视频)的功能的主要部分。重现软件的控制是一种加强内容拥有者的利益(包括所述内容被使用的期限和条件)的方法。过去许多CE平台(除了PC和PDA)被关闭，今天越来越多的平台至少部分地被打开。特别是对于PC平台，一些用户被认为具有对提供有对内容和大量时间和资源的访问的硬件和软件的完全控制以攻击和绕过任何内容保护机制。因此，内容提供者必须越过不友好的网络到其中不是所有的用户或设备都可信的机构而将内容发送至合法用户。

为了防止数字内容(例如电影)盗版，通常以加密形式将其发送至用户。为了保持分配成本为低，所述内容一般被加密一次，即每个合法用户获得相同的密钥，利用该密钥他/她可以对所述内容解密。这隐含着的弱点在于攻击者可以将密钥分配给未授权的用户，这破坏了保护机制。

Stanley Chow、Philip Eisen、Harold Johnson和Paul C.VanOorschot的“White-Box Cryptography and an AES Implementation”，in Selected Areas in Cryptography：9th Annual InternationalWorkshop，SAC 2002，St.John’s，Newfoundland，Canada，August15-16，2002，此后称为“Chow 1”，和Stanley Chow、Phil Eisen、Harold Johnson和Paul C.Van Oorschot的“White-Box DESImplementation for DRM Applications”，in Digital RightsManagement：ACM CCS-9 Workshop，DRM 2002，Washington，DC，USA，November 18，2002，此后称为“Chow 2”，公开的方法中试图通过将查找表的网络中的密钥模糊化来隐藏密钥。这使得对于攻击者来说提取和分配密钥变得更加困难。

发明内容

一种用于方便跟踪计算方法的实现的拷贝的改进系统将是有利的。为了更好地诠释该想法，在本发明的第一方面中，提出的系统包括

网络生成器，用于产生代表计算方法步骤的查找表的网络，所述网络通过将第一查找表的输出值用作不同的第二查找表的输入值而形成；

个性化器，用于通过改变查找表网络中的至少一个值来产生多个不同版本的查找表网络，对应于输入值的相关域的所述版本的最终结果对于每个版本基本上是相同的；

相关器，用于将各个版本与各个基站或基站的用户相关联。

所述个性化器使用查找表网络中的固有冗余来创建不同版本的查找表网络。当找到版本的(潜在地非法的)拷贝时，与所述版本相关联的基站或用户可以被建立，因为所述版本不同，并且各个版本与各个基站或基站的用户相关联。

被采用来产生不同版本的所述变化指的是版本的水印。网络生成器和个性化器可以是相同的，即一个单元可以产生所有版本。所改变的值可以是查找表之一中的值。可以理解的是，网络的结构(即限定查找表的哪个输出被提供给查找表的哪个输入的结构)可以被参数化。这种情况下，所述改变的值可以与限定该结构的参数相关。

在实施例中，计算方法(602)包括加密策略和加密密钥，网络生成器(604)和个性化器(606)被设置以用于产生能够利用所述加密密钥执行加密策略的查找表网络。在此情况下所述系统特别有用，因为加密密钥常常十分宝贵。这种密钥的非法分配是不期望的。当找到查找表网络的版本的(非法分配的)拷贝时，所述系统有助于识别相关联的基站或用户。在找到明显被重新分配的版本拷贝的情况下，可以针对相关联的用户采取行动。

在实施例中，所述个性化器被设置为用于创建计算方法的白盒实现。从例如Chow等的文献中已知使用查找表网络的算法的白盒实现。这些白盒实现中的冗余以及特别是模糊化使得更加易于将变化应用于难以由第三方(即攻击者)隔离和/或去除的网络。

在实施例中，不同版本中白盒实现的输出编码和/或输入解码有所不同。一种相对简单的生成变化来创建不同版本的查找表网络的方法是以不同方式对查找表之一的输出进行编码，并且在查找表网络中的下一个查找表中对其解码。

在实施例中，所述个性化器被设置为用于利用运算符将白盒实现模糊化，针对不同版本所述运算符被不同地选择，其中所述运算符被集成在网络中的第一多个查找表中，而运算符的逆被集成在网络中的第二多个查找表中。

这使得对于攻击者来说相对复杂的是将水印完全去除，因为需要多个查找表中的协调变化或者对网络结构的协调变化。由于多个查找表作用于运算符的实现，运算符被集成在多个网络中。然而，运算符的结果可能不能直接在白盒实现中可视，因为查找表提供中间和/或最终结构的附加编码。

在实施例中，所述第一多个查找表中的至少一个或所述第二多个查找表中的至少一个具有输入和/或输出编码，相对于经过网络的数据流其没有被网络中它的各个前趋和/或后继取消。这使得对于攻击者来说更难以去除水印。

在实施例中，所述运算符为线性混合双射，并且所述输入和/或输出编码中的至少一个是非线性的。线性混合双射与非线性输入和/或输出编码的组合对于白盒实现是普遍存在的。所述线性混合双射可以有效地被集成在多个查找表中。所述非线性输入和输出编码使得白盒实现更加难以破坏。

在实施例中，所述个性化器被设置为用于使用运算符以不同的等价类创建各版本，其中所述等价类包括这样的运算符，即它的对应查找表网络可以通过将来自预定修改集合的修改提供给所述输入和/或输出编码而从彼此获得。给输入和/或输出编码提供修改(包括置换)被认为是攻击者所能及的工作。因此，所述水印应当“抵抗”这样的修改，即在已经进行这种修改之后水印和相关用户仍然可以被识别。各个等价类与各个基站或用户相关联，因为各个版本与各个基站或用户相关联。

在实施例中，所述个性化器被设置为用于以不同的等价类创建各版本，其中所述等价类包括可以通过将来自预定修改集合的修改提供给版本而从彼此获得的版本。预定修改集合代表那些被认为是攻击者所能及的修改。所述水印应当“抵抗”这种攻击者所能及的修改。如果所述版本处于不同等价类，则在已经应用这种修改之后，所述水印和相关用户仍然可以被识别。优选地，在每个等价类中最多产生一个版本。所述各个等价类与各个基站或用户相关联，因为各个版本与各个基站或用户相关联。

一个实施例包括用于将查找表网络的各个版本经由单个介质发送给相关基站或用户的输出。这允许所述基站或用户方便地经由单个介质接收查找表网络。所述网络不需要在所述基站中预先编程。以此方式，随着时间被不同地改变的版本可以与各个基站/用户相关联并且轻易地被发送至各个基站/用户，而无需使用第二介质或者对所述基站来说无需任何硬件或固件变化。这使得系统更加有效，因为所述基站可以在不受对各个版本所做变化影响的条件下被预先编程。可选地，所述基站完全一样。虽然所述版本可能在用户之间被(非法)分配，但是该被(非法)分配的版本的起源可以被跟踪，因为所述版本与使用介质将所述网络版本首先发送到的基站或基站的用户相关联。通过以加密形式发送查找表网络的版本仍然可以防止过于简单(非法)的分配。

在实施例中，所述系统用于受控地将内容分配给多个基站，并且所述计算方法包括解密方法，所述系统进一步包括

加密器，用于使用与用户相关联的用户专用的加密密钥来对与用户相关联的版本加密，以获得加密的版本；

内容预处理器，用于根据加密策略和加密密钥对内容加密，以获得加密的内容；

输出，用于向用户提供加密的版本和加密的内容。

该实施例描述特殊应用情况。所述版本可以使用用户专用的密钥被加密并且被提供给各个用户。或者，所述版本可以在不加密的前提下被发送，例如经由安全通道或介质。在另一实施例中，一部分查找表网络被预先固定并且已经在用户处存在，而且只有剩余部分的查找表网络被提供给用户。

一个实施例包括用于为用户执行计算的系统，包括

数据处理单元，用于将代表计算方法的步骤的查找表网络应用于数据，所述网络通过将第一查找表的输出值用作不同的第二查找表的输入值而形成；

所述查找表网络形成多个不同版本查找表网络的一个版本，所述多个不同版本通过改变查找表网络中的至少一个值而获得，对应于输入值的相关域的计算方法的最终结果对于每个版本来说基本上相同；

各个版本，与各个用户相关联。

这可以在基站或用户终端中实现，以根据查找表网络的版本处理数据。

一个实施例包括用于识别计算方法的实现的拷贝的系统，其中所述实现包括代表计算方法的步骤的查找表网络，所述网络通过将第一查找表的输出值用作不同的第二查找表的输入值而形成；

所述查找表网络作为通过改变查找表网络中的至少一个值而获得的多个不同版本的查找表网络的一个版本，对应于输入值的相关域的计算方法的最终结果对于每个版本来说基本上相同；

所述系统包括：

比较器，用于将所述实现中的至少一个查找表与至少一个版本进行比较。

这有助于识别与特殊版本相关联的用户。

一个实施例包括等价类建立器，用于建立对应于所述实现中的版本的等价类，其中等价类包括通过将来自被认为是攻击者所能及的修改集合的修改应用于开始版本来从所述开始版本获得的版本。这有助于即使在水印版本被改变之后识别所述用户。

一个实施例包括一种便于跟踪计算方法的实现的拷贝的用户的方法，所述系统包括

产生代表计算方法步骤的查找表网络，所述网络通过将第一查找表的输出值用作不同的第二查找表的输入值而形成；

产生多个不同版本的查找表网络，其通过改变查找表网络中的至少一个值而获得，对应于输入值的相关域的版本的输出值对于每个版本来说基本上相同；

将各个版本与各个用户相关联。

一个实施例包括一种识别计算方法的实现的拷贝的方法，其中所述实现包括代表计算方法步骤的查找表网络，所述网络(28)通过将第一查找表(20)的输出值用作不同的第二查找表的输入值而形成；

查找表网络作为通过改变查找表网络中的至少一个值而获得的多个不同版本的查找表网络的一个版本，对应于输入值的相关域的计算方法的最终结果对于每个版本来说基本上相同；

所述方法包括：

将所述实现中的至少一个查找表与至少一个版本进行比较。

一个实施例包括一种计算机程序产品，包括用于使得处理器执行上述任一方法的指令。

WO 01/31419公开了一种计算机执行的方法，其中信息被具有个人值并且对于客户端的用户已知的密钥所加密，以防止用户和其它人共享所述密钥。

附图说明

参考附图，对本发明的这些和其它方面做进一步阐述和说明，附图中：

图1是示出AES环路操作的示图；

图2是示出将表模糊化的示例的示图；

图3是示出白盒AES实现中列的环路的示图；

图4是示出体现在Ia型表中的映射的示图；

图5是示出体现在II型表中的映射的示图；

图6是示出体现在III型表中的映射的示图；

图7是示出体现在IV型表中的映射的示图；

图8是示出体现在Ib型表中的映射的示图；

图9是示出在查找表网络中从一个查找表到下一查找表信息位流的示图；

图10是示出实施例的示图；以及

图11是示出实施例的示图。

具体实施方式

白盒密码术是关于对固定密钥K实现分组密码，以便对于攻击者来说难以从所述实现中提取密钥K。白盒密码术中所认定的攻击模式为白盒攻击模式。以此攻击模式，攻击者被认为可以充分访问软件并且可以对实施环境进行充分控制。

一个实施例是关于用于付费TV的有条件访问系统。内容提供者将被AES和内容密钥K加密的内容进行传播。关于有条件访问系统必须解决的问题之一是如何将内容密钥K进行分配，以供为订户而不为其它人将所述内容进行解密。下面描述两种方法。首先，简单的方法是保持内容密钥K随着时间固定并且只向订户提供密钥K。然而，这种执行具有下列两个缺点。第一个缺点在于我们不能注销用户。只要拥有密钥K，用户永远都可以对内容解密。该简单方法的第二个缺点在于由于长时间使用固定的密钥，攻击者可以找到它的风险不断提高。

第二种方法的工作如下。内容密钥周期性地变化，例如每天或每周。每个订户s获得唯一的私钥k_s，并且对于每个订户s来说，密钥K由它的私钥k_s加密。密钥K的加密的集合{E_ks(K)|s是合法订户}和被加密的内容一起被传播。然后，只有合法订户可以获得K，并且随后解密所述内容。重要的是，私钥k_s隐藏得很好。这通常在硬件中进行。以此方法，可以注销用户。为了注销用户s，不向其提供下次会改变的被加密的内容密钥。因此，如果内容密钥从K变化到K’，则不向用户s提供E_ks(K’)。

虽然所述第二种方法优于第一种，但是由于接下来的攻击它仍然产生了易损的有条件访问系统。订户之一可以获得内容密钥K。例如这可以是这种情况，因为订户s可以检查解密算法并且从其提取密钥或者因为s能够确定他/她自己的私钥k_s。当内容密钥K接下来被非法分配时，内容提供者不能识别对该分配负责的有恶意的订户。其结果是，内容提供者不得不采取严厉的行动，例如为所有订户(包括合法订户)替换解密算法和/或他们的私钥k_s的实现。

在实施例中，用于利用密钥K对内容解密的解密算法的实现由基本上如Chow等所述的白盒实现代替。在该白盒实现中，AES解密算法由查找表集合执行，所述查找表集合通过对它们的输入和输出进行编码而被模糊化。此外，给不同订户的表提供不同的编码。其结果是，每个订户得到不同的白盒实现。然而，所有这些白盒实现具有相同的功能(它利用密钥K执行解密)。如果内容密钥K变化，则用户被提供新的白盒实现(即具有新的查找表集合)。

如果白盒实现足够可靠，则对于攻击者来说很难提取潜在的密钥K并公布之。替代地，他/她不得不公布完整的白盒实现(即查找表集合)。然而，如果恶意的订户公布了他/她的白盒实现，则内容提供者可以跟踪他/她，因为他有唯一的白盒实现。其结果是，内容提供者可以撤销所述攻击者，即取消攻击者的预定。这意味着对于由不同的密钥K’加密的其它内容，攻击者将接收不到利用密钥K’执行解密算法的白盒实现。

通过选择不同的编码，多个白盒实现可以被创建为具有相同功能(例如，它们都利用密钥K执行AES解密)。该区别可以用于叛逆者跟踪：每个用户被赋予不同的白盒实现变量，以便给定一白盒实现，则可以通过检查编码来识别所述白盒实现的起源。请注意，白盒实现的编码在这里起着取证水印的作用。

接下来，描述一些使用由Chow等提出的AES白盒实现的实施例。然而，所述实施例不局限于AES。本领域技术人员可以做出必要的变化以将所公开的技术同样应用于其它加密方案，特别是应用于其白盒实现。而且，所述技术可以在加密背景以外使用，只要算法包括应用查找表网络，正如本领域技术人员所明了的。

AES的白盒实现

AES是分组大小为128位或16字节的分组密码。明文被划分成16字节的分组，其形成编码算法的初始状态，而编码算法的最终状态是密文。为了从概念上解释AES，状态字节被组织成4×4字节的矩阵。AES包括多个环路。每个环路由对状态矩阵的字节、行或列进行操作的相似处理步骤组成，在这些处理步骤中每个环路使用不同的环路密钥。

图1示出AES环路的一些主要处理步骤。所述处理步骤包括：

AddRoundKey 2-状态的每个字节被环路密钥的字节“异或”。

SubBytes 4-使用查找表进行字节-字节置换。

ShiftRows 6-状态的每个行被旋转固定数量的字节。

MixColumns 8-使用GF(2⁸)的模乘来处理每个列。

步骤SubBytes 4、ShiftRows 6和MixColumns 8均与使用的特殊密钥无关。所述密钥在步骤AddRoundKey 2中被采用。除了步骤Shift Rows 6，处理步骤可以在不知道其它列的前提下在4×4状态矩阵的每个列上执行。因此，它们可以被看作32位操作，因为每个列包括4个8位值。虚线10示出所述进程被重复，直到已经执行了所需数量的环路。

这些步骤中的每一个或者步骤的组合可以由查找表或查找表网络(S-boxes)代表。也可以由查找表网络来代替AES的全环路。例如，AddRoundKey步骤可以通过简单地用环路密钥进行异或而被执行，而SubBytes、ShiftRows和MixColumns步骤使用查找表来执行。然而，这意味着所述密钥仍然对于白盒攻击背景下的攻击者是可视的。AddRoundKey步骤也可以嵌入查找表中，这使得更难找出所述密钥。

图2示出一种使得提取密钥更为困难的方法。让X和Y作为两个函数。考虑操作YοX(c)＝Y(X(c))，其中ο意指函数组合，如图2中图解12所示，其中c是输入值，例如4字节状态列。然而，所述方法适用于任何类型的输入值c。对X和Y的映射可以实施为可以存储在存储器中的查找表，然而，当它们被存储在存储器中时，所述值可以被攻击者读取。图解14示出如何通过使用输入编码F和输出编码H来将查找表的内容模糊化。如所示，对应于XοF^-1和HοY的查找表被存储，而不是X和Y，这使得更加难以提取X和Y。图解16示出如何增加附加的，例如随机的，双射函数G，以便两个表的中间结果也可以被编码。在此情况下，两个表被存储在存储器中：X′＝GοXοF^-1和Y′＝HοYοG^-1。这在图解18中又一次被示出：

Y′οX′＝(HοYοG^-1)ο(GοXοF^-1)＝Hο(YοX)οF^-1，

其中X和Y是适于通过查找表实现的函数。在此文献中，ο指代常规的函数组合(即对于任何两个函数f(x)和g(x)，定义为fοg(x)＝f(g(x)))。同样地，包括两个以上函数的网络也可以被编码。编码X和Y的实际表通过将HοYοG^-1组合在单个查找表中和将GοXοF^-1组合在单个查找表中而被模糊化。只要F、G和/或H保持未知，则攻击者不能从查找表提取有关X和/或Y的信息，并且因此攻击者不能提取作为X和/或Y的基础的密钥。其它密码算法，包括DES和Rijndael(AES是其特殊实例)也可以被编码为查找表(表达级联或网络)，其可以上述类似方法而被模糊化。这也可用于基于例如更替-置换网络或Feistel网络的密码。本发明不局限于所提到的示例性密码算法。

Chow1公开了一种方法，试图通过对其表进行编码来隐藏密钥，其具有代表组合而非单个步骤的随机双射。防止私钥提取的优点在于防止攻击者提取能够使得软件保护目标在其它机器上被绕过的关键材料，或者防止攻击者公布有效地创建破坏整个安装软件的大型用户基础的安全措施的“全局破解”的关键材料。假设所述限制为单纯使用软件的方案和敌-主事实，则它提供更大程度的保护。在Chow 1的方法中，密钥被这样隐藏，通过(1)使用用于组合而非单个步骤的表；(2)由随机双射对这些表进行编码和(3)将密码边界延伸至密码算法自身之外而进入包含应用，迫使攻击者(与工程师相对)获知显然更大的代码部分以实现他们的目标。Chow 1讨论了一种固定密钥方法：所述密钥通过针对所述密钥的局部评估而被嵌入所述实现中，以便不需要密钥输入。局部评估意味着涉及密钥的表达被尽可能地评估，并且结果被置于代码而非整个表达中。攻击者可以提取专用密钥的实现，并使用它来代替密钥，然而密码术典型地是更大包含系统的组件，其可以被操作或被编码的形式而向密码组件提供输入，为此对所述组件进行设计，但是敌人会发现难以去除。参考编码表的步骤，由于编码是任意的，因此结果只有在一个步骤的输出编码与下一步骤的输入编码匹配时才是有意义的。例如，如果步骤X之后是步骤Y(产生YοX的计算)，所述计算可以被编码为：

Y′οX′＝(HοYοG^-1)ο(GοXοF^-1)＝Hο(YοX)οF^-1。

以此，YοX被适当地计算，虽然输入需要用F编码而输出需要用H^-1解码。所述步骤被分开表示为对应于Y’和X’的表，以便F、G和H以及X和Y被隐藏。

除了这种混淆步骤，Chow 1使用了利用线性转换的扩散步骤，以进一步伪装潜在的操作。术语混合双射用于描述上面提到的线性双射。Chow 1的实现以可控形式进行输入，并且以不同的可控形式产生输出，从而使得抗白盒攻击环境(WBAC)的AES难以从它的包含应用中分离出来。

白盒AES执行可以描述如下。对于AES加密和解密算法的输入是简单的128位分组。该分组由包含16字节的4×4矩阵代表。AES通常包括AES-128的10个环路。每个环路更新十六字节集合，其形成AES状态，因此每个AES环路处理128位。AES-128使用128位密钥。该密钥充当将所述密钥转换成不同的128位环路密钥的算法的输入。基础环路包括四个部分：

·SubBytes

·ShiftRows

·MixColumns

·AddRoundKey。

该操作顺序适用于AES加密。虽然AES解密中的标准操作顺序有所不同，但是可以重写AES解密算法，以具有和AES加密相同的操作顺序。

在第一环路之前，发生额外的AddRoundKey操作，而在环路十中，省略了MixColumns操作。使用密钥的唯一部分是AddRoundKey，其它三个步骤不对密钥进行任何操作。在执行中，环路的边界被改变以将AddRoundKey步骤和下一环路的SubBytes步骤集成为一个步骤。环路从AddRoundKey和SubBytes开始，接着是ShiftRows，最后是MixColumns。

首先，通过将SubBytes步骤和AddRoundKey组合成一个步骤来将密钥隐藏。这使得密钥自身不再可视。因为密钥事先已知，因此涉及密钥的操作可以被预先评估。这意味着用在步骤SubBytes中的标准S-Boxes可以由专用密钥的S-Boxes代替。为了产生AES-128的专用密钥例子，所述密钥被并入SubBytes转换，通过创建十六个8×8(即8位输入，8位输出)查找表T_i，j ^r，其定义如下：

$T_{i,j}^r\left(x\right)=S(x\⊕k_{i,j}^{r-1}),i=0,...,3;j=0,...,3;r=1,...,9,$

其中S是AES S-Boxes(可逆8位映射)，k_i，j ^r是4×4矩阵的位置i，j处的AES子密钥字节，其代表环路r的环路密钥。这些T-Boxes将SubBytes步骤和之前环路的AddRoundKey步骤组合。环路10T-Boxes吸收白化之后的密钥，如下：

$T_{i,j}^{10}\left(x\right)=S(x\⊕k_{i,j}^9)\⊕k_{\mathrm{sr}(i,j)}^{10},i=0,...,3;j=0,...,3,$

其中sr(i，j)指代ShiftRows步骤之后单元i，j的新位置。所有T-Boxes的数量是10×16＝160。然而，所述密钥可以轻易地从T-Boxes去除，因为S^-1公知。这使得有必要进行附加编码。线性转换用于将输入扩散至T-Boxes。这些线性转换被称为混合双射，并且可以被表示为GF(2)的8×8矩阵。所述混合双射通过之前的计算而被反转，以消除它们的效应。

图3示出对于状态的一个32位列(在采用ShiftRows之后)的白盒AE8环路中涉及的表。这里引入不同类型表的名字。此后对此进行更为详细的描述。在环路之前，128位状态的每个字节被提供给各个类型Ia表。这导致各个128位值，其使用类型IV表的网络而被异或以提供被划分成四个32位值的128位输出。现在，开始第一环路。这里概述了每个32位值的处理步骤。32位值的四个字节被输入至四个不同的类型II表20。四个类型II表20中的每一个产生32位输出。这些输出使用类型IV表22而被按位异或。每个类型IV表22执行4位按位异或。通过合理地将类型IV表的输入和输出连接，四个32位输出的按位异或可以被实现，如本领域技术人员所明了的。这个步骤的结果是32位值。该值的四个字节中的每一个被提供给各个类型III表24。每个类型III表24提供32位输出。这些输出再次使用与类型IV表22的网络相似的类型IV表26的网络而被按位异或。输出是指示状态列的32位值。环路2到9与第一环路相似。128位值的每个字节被应用于类型Ib表；所述结果使用类型IV表的网络而被异或。最后的环路(通常是第十环路)被外部编码所吸收。

图4示出类型Ia表100。图5示出类型II表200。图6示出类型III表300。图7示出类型IV表400。图8示出类型Ib表500。

混合双射的使用如下。AES状态由包含字节的4×4矩阵表示。MixColumns步骤每次一列(4个8位单元)地操作。考虑32×32矩阵MC。如果其由表表示，则该表会花费2³²×32＝137438953472位＝16GB。为了避免如此大的表，所述矩阵被分组为四部分。

MC被分组为四个32×8部分，MC₀、MC₁、MC₂、MC₃(分组208)。32位矢量x＝(x₀，...，x₃₁)和MC的相乘由将x的位划分为四个字节并且将MC的每个部分和字节之一相乘而进行，产生四个32位矢量(z₀，...，z₃)。接下来的三个32位异或给出最终的32位结果z。四个表一共只花费4×2⁸×32＝32768位＝4KB。

三个异或将被划分为24个4位异或，每个由可能被编码的查找表所表示，具有适当的链接结合(例如((z[0，0]，z[0，1]，z[0，2]，z[0，3])+(z[1，0]，z[1，1]，z[1，2]，z[1，3]))‖((z[0，4]，z[0，5]，z[0，6]，z[0，7])+(z[1，4]，z[1，5]，z[1，6]，z[1，7]))‖...)，其中‖表示链接结合，+表示异或。通过使用这些带和细分的异或，每个步骤由小的查找表表示。特别地，对于i＝0，...，3，z_i使用8×32表被计算，而4位异或变成24个8×4表。图7示出输入解码402和输出编码406如何被置于异或404周围。这些编码通常是随机选择的非线性4×4双射。异或表被称为类型IV表400。类型IV表从之前的两个计算中的每一个取作输入4位。那些计算的输出编码212与类型IV表的输入解码402匹配，以使彼此失效。4×4非线性双射的选择取决于表的大小。在此情况下，类型IV表只是2⁸×4位＝128字节。需要24个表，总共花费3KB。如果所述异或没有被划分，则会需要三个异或表，其计算32位异或。T-boxes 206和8×32表208可以表示为分开的查找表。替代地，它们可以被组合来创建新的8×32表200，其计算SubBytes和AddRoundKey转换以及部分MixColumns。这既节省了(保存T-boxes的)空间，又节省了(执行表查找的)时间。

在将MC如上划分为MC_i之前，MC被32×32混合双射MB左乘，如图5中附图标记210所示，被选作整个排列中具有4×4子矩阵的非单独矩阵。混合双射的使用增加了特殊表的可能结构的数量。

图5示出8×32类型II表200，包括4×4输入解码202和4×4输出编码212。这些输出编码和输入解码是非线性4×4双射，其必须与类型IV表400的输入解码和输出编码匹配。类型II表200之后即类型IV表400。为了反转MB，使用额外的表集合来计算MB^-1。让(x’₀，...，x’₃₁)作为到MixColumns的输入，让(z₀，...，z₃₁)作为MixColumns之后的输出。让(z’₀，...，z’₃₁)^T作为与MB相乘之后的结果。(z’₀，...，z’₃₁)^T充当到类型III表300的输入。请注意输入解码和输出编码在这里不需要考虑，因为表的输出编码由下一表的输入解码消除。在类型III表300中，MB^-1被采用304和下一环路的四个类型II表200的四个输入混合双射204被反转308。

图6示出8×32类型III表300，包括4×4非线性输入解码和4×4非线性输出编码。这些表之后的是对应的类型IV表400。

数据操作的一个环路包括对128位状态矩阵的操作。在128位状态矩阵的四个32位带中的每一个上执行的数据操作如下。32位带被划分为4个8位字节。四个字节中的每一个被发送至不同的类型II表200，产生四个32位输出值。这些值必须使用模糊化的类型IV表400而被异或。为此，每个32位输出值被划分为8个4位元组，并且合适的元组对被输入至各个类型IV表，以便四个32位输出值的异或以编码形式获得。

该32位产生的编码异或结果再次被划分为字节，并且每个字节被输入至不同的类型III表300。类型III表300的每个元组的输入解码对应于上次使用的类型IV表的输出编码。所述类型III表再次产生四个32位输出值，其再次由模糊化的类型IV表400异或。

总之，所述环路由查找表执行。单个环路的查找表被如下联网。数据被发送至类型II表。这些表的输出被发送至表示被编码异或的类型IV表的网络。这些网络的输出被发送至类型III表，其取消了由类型II表插入的混合双射编码。所述环路的编码输出最终由再次将类型III表的输出发送至代表被编码异或的类型IV表的网络获得。

此外，白盒实现包括开始的(类型Ia表100)和结束的(类型Ib表500)类型I表，分别用于取消和插入外部编码。类型Ia表100可以用于通过提供单个的表查找而采用如图4所示的映射的链接结合。在链接结合中，4位元组输入解码102最先出现。然后，出现8位到128位双射104；该双射实现了网络的输入和输出的编码；该映射在程序中的其它地方不进行。双射104的结果被划分成16个8位片段，各个8位双射106被提供给它们。最后，采用输出元组编码108。如上所述，映射102、104、106和108的级联被预先评估，并且最终结果被列表于查找表中。这导致表最多每128位具有256个条目。并入类型Ib表500的映射的链接结合示意性地示于图8中。第一映射是输入元组解码502，接下来是8位双射504，T-box T_i，j ^r506，其中r对应于最后的环路，8位到128位映射用于提供输出编码，和输出元组编码510。这种表的128位输出被其它类型Ib表的输出所异或，再次使用元组输入和输出编码的类型IV表400。输出编码508在程序的其它地方(即在程序的密码部分以外)不进行。这使得攻击者更加难以通过仅仅分析程序的密码部分的输入和输出来破坏表的编码。

白盒密码术包括执行软件中的分组密码，以便攻击者不能提取白盒攻击模式中的密钥。白盒攻击模式属于最强的可能的攻击模式，因为攻击者被认为可以充分访问所述实现并且对执行环境完全控制。白盒实现存在于AES、DES和其它加密策略。这些白盒实现可以基于上述相似的想法，并且本领域技术人员能够采用白盒实现的原理以创建其它加密策略的白盒实现。

可以给白盒实现添加取证水印，以便如果恶意用户分配了他/她的实现，我们可以跟踪该用户。也就是说，多个白盒实现X₁，X₂，...，X_n可以被创建，以便如果给定特定的白盒实现Y则可以确定它对应于所述实现X₁，X₂，...，X_n的哪一个。执行Y不需要和执行X_i完全相同，因为恶意用户u能够对他/她的实现进行一些修改而不改变其功能。

在实施例中，给白盒AES实现添加取证水印。以此方法，通过选择不同的编码来模糊化白盒实现的表，创建了多个白盒AES实现。例如，限定X₁，X₂，...，X_n，以便它们只在给定类型II表U(图5中212)的第一输出元组的非线性元组编码f方面不同。请注意，这暗含着对于随后的类型IV异或表V，两个输入元组解码g之一也在不同的执行中有所不同。其原因是g＝f¹：置于U的第一输出元组上的输出编码f被异或表V中并入的元组解码所取消。本领域技术人员明了的是这不局限于类型II表的第一输出元组。任何对应的输出元组编码和输入元组解码对可以用于提供水印。而且这种对的任何组合可以被用作水印。特别强的水印可以通过随机地选择所有元组编码/解码而获得，对于每个用户有所不同地进行。这具有其它优点，如果攻击者能够只修改一些元组编码/解码对，则用户仍然可以通过余下的元组编码/解码对而被识别。

改变元组编码不影响解密的结果。因为元组输出编码在另一表的元组输入解码中不进行，因此最后结果相同。因此可以将表的多个不同版本分配给不同用户，其中所有这些版本代表相同的具有相同加密密钥的密码方法。

攻击者可以如下改变元组编码。让U、V作为白盒AES实现中的连续表，并让f作为由表U返回的元组的输出编码。请注意这意味着表V具有输入元组解码f¹，即表V将f¹应用于来自U的元组。该输出编码可以被改变为任意(非线性)编码g。限定h以便g＝h°f。然后由h对U的输出编码，并将元组解码h^-1并入V。在图9中，该原理被示为用于类型IV表的特定情况。该做法的结果在于表U的输出编码由g给出。此外，因为攻击者不需要有关U和V中所用编码的任何信息，他/她能够执行所述做法。攻击者可以实现的第二种修改包括重新设置表的输出和输入位。形成表V的输入位的表U的输出位可以由攻击者给出不同的顺序。该位的顺序中的变化在表V中不进行。这些攻击者可能采用的潜在变化增加了从查找表网络中删除水印的风险。

上面已经示出攻击者可以修改包含水印的查找表网络。在此背景下，下列各项在提供鲁棒的水印方面起作用。首先，如何制造所有功能相同的多个白盒AES实现X₁，X₂，...，X_n，即所有针对给定密钥K执行AES。第二，它有助于识别哪种修改被认为攻击者u会在实现X_u上实施，他试图去除水印并仍然具有期望的功能。第三，让Y作为(可以)通过采用这种修改而从白盒实现X_u获得的经修改的白盒实现。所期望的是仍然能够确定Y已经从X_u获得而不是从任何其它执行X_i。这三项可以作为取证水印项。

在实施例中，水印以这样的方式被添加，即使攻击者已经改变一个或多个元组编码和/或已经改变从一个表流至下一表的位顺序，所述水印仍可以被覆盖。更普遍的是，攻击者可以将任何转换应用于形成到相同的下一表的输入位的表的输出位集合。通过下面的数学原理可以更好地理解一种实现方法。

等价问题

使用下面的概念。元组(nibble)是4位示例，字节(byte)是8位示例，并且针对元组x₁，...，x_n认为每个(4n)-位矢量x被划分成如x＝(x₁，...，x_n)的n个元组。因此被划分的(4n)-位矢量x可以被称为长度n的元组矢量。元组转换是映射f＝(f₁，...，f_n)，其中每个f_i是元组映射，即将元组映射至元组；这样的映射实施于如上被划分成元组的(4n)-位矢量x＝(x₁，...，x_n)并且将这样的矢量x映射至

f(x)＝(f₁(x₁)，...，f_n(x_n))。

请注意，这种元组转换f是可逆的，当且仅当元组映射f_i可逆。可逆的元组转换可以用在查找表的输出，其中它们充当输出元组编码，或者用在查找表的输入，其中它们则充当输入元组解码。元组置换是置换π＝(π₁，...，π_n)，其中{π₁，π₂，...，π_n}＝{1，2，...，n)，其被认为通过置换其元组而作用于(4n)-位矢量x＝(x₁，...，x_n)；这样的π被认为将x映射至

$\mathrm{\π}\left(x\right)=(x_{{\mathrm{\π}}_1},x_{{\mathrm{\π}}_2},...,x_{{\mathrm{\π}}_n}).$

由类型II表200实现的操作0将包含两个元组a₁，a₂的输入字节a＝(a₁，a₂)转换成包含8个元组z₁，...，z₈的32位输出矢量z＝(z₁，...，z₈)并采取形式

O＝fοBοCοTοAοg，      (1)

其中各种操作具有下列形式。

·映射g＝(g₁，g₂)表示对输入字节a＝(a₁，a₂)的元组解码202，并将a映射至g＝(g₁(a₁)，g₂(a₂))；这里每个g_i是从元组到元组的可逆映射。

·映射A表示从字节到字节的非单个线性映射204。

·映射T表示将字节映射到字节的“T-box操作”206。

·映射C表示一部分混合操作208，并包括从字节到32位矢量的线性映射。

·映射B是混合双射210。它将32位矢量映射至32位矢量。在实施例中，该映射B用于编码水印。

·最后，f＝(f₁，...，f_n)表示元组编码212，将被划分成元组u₁，...，u₈的32位矢量u＝(u₁，...，u₈)映射至输出矢量z＝(z₁，...，z₈)＝(f₁(u₁)，...，f₈(u₈))。

如果a⁽¹⁾，...a⁽⁴⁾是四个输入字节，其作用于输出列b，则存在四个涉及到的类型II表0⁽¹⁾，...0⁽⁴⁾，形式为

O⁽ⁱ⁾＝f⁽ⁱ⁾οBοC_iοT_iοA_iοg⁽ⁱ⁾.                        (2)

然后输出列b满足

b＝(f⁽¹⁾)^-1z⁽¹⁾+(f⁽²⁾)^-1z⁽²⁾+(f⁽³⁾)^-1z⁽³⁾+(f⁽⁴⁾)^-1z⁽⁴⁾，(3)

其中

z⁽ⁱ⁾＝O⁽ⁱ⁾a⁽ⁱ⁾。

请注意32×32矩阵C＝[C₁C₂C₃C₄]表示整个混合操作，其中C_i是(2)中的那些。

(3)所需的操作由一些层的类型IV表来实现。这里，由类型IV表400实现的操作A将元组输入对(x，y)转换成元组z并采用如下形式

A＝fοSοg，               (4)

其中各种操作具有下列形式。

·映射g＝(g₁，g₂)表示对输入元组对(x，y)的元组解码402，将他们映射至g＝(g₁(x)，g₂(y))；这里每个g_i是从元组到元组的可逆映射。

·映射S表示404中4位异或操作。

·最后，f表示元组编码406，将元组u映射至元组f(u)。

因此为了实现(3)中输出列b的总和，首先表0⁽ⁱ⁾的32位被加数z⁽ⁱ⁾的每一个被划分成八个元组z_j ⁽ⁱ⁾，j＝1，...，8。然后输出列b的元组b_j由两层的类型IV表计算为

$b_j=[{\left(f^{\left(1\right)}\right)}^{-1}{z}_j^{\left(1\right)}\⊕{\left(f^{\left(2\right)}\right)}^{-1}{z}_j^{\left(2\right)}]\⊕[{\left(f^{\left(3\right)}\right)}^{-1}{z}^{\left(3\right)}\⊕{\left(f^{\left(4\right)}\right)}^{-1}{z}^{\left(4\right)}].---\left(5\right)$

作为最后一层中每个类型IV表中最终输出编码的结果，该部分查找表网络实际上为某输出元组编码h计算c＝h(b)。

希望隐藏它的取证水印B的攻击者具有制造输出矢量c＝h(b)的多种可能。首先，由相同置换π将每个矢量z⁽ⁱ⁾中的元组置换具有这样的效果，即输出矢量中的元组也由π置换。第二，改变最后一层类型IV表中输出元组编码(以可逆方式)有效地将该编码应用于元组c。请注意，通过首先置换c字节所发送至的后继网络，攻击者不进行所有这两种操作。

因此攻击者可以确保代替输出c＝h(b)而实际产生的输出为

b′＝ποfοb，          (6)

其中

π＝(π₁，...，π₈)

是未知的可逆元组置换，并且

f＝(f₁，...，f₈)

是未知的可逆元组转换，以便b’＝(b’₁，...，b’₈)满足

$b_{{\mathrm{\π}}^{-1}\left(i\right)}^{\′}=f_i\left(b_i\right).---\left(7\right)$

给定所述系统的(虚构的)非模糊化(标准)AES实现(这里其实现于本表查找网络中)，则计算的所有中间结果可以被检查，甚至通过解码操作而被设定为某预定值。特别地，所有中间结果

x⁽ⁱ⁾＝C_iοT_iοA_iοg⁽ⁱ⁾(a⁽ⁱ⁾)

在表0⁽ⁱ⁾中执行的计算中，其也发生在标准AES计算中，并且因此它们的总和

x＝x⁽¹⁾+x⁽²⁾+x⁽³⁾+x⁽⁴⁾，

可以被设定为任何预定值，而与攻击者的行动无关。由于

z⁽ⁱ⁾＝f⁽ⁱ⁾x⁽ⁱ⁾，

(3)之后为

b＝Bx.                   (8)

然而，作为攻击者操控(和原始元组输出编码)的结果，代替b，如(6)中从b获得的矢量b’被监视，由未知的但是固定的元组置换π和元组转换f。

结果是，未知映射T的输入/输出行为可以被监视，然而其由下列形式可知

T＝ποfοB，                (9)

根据未知的元组置换π、可逆元组转换f和代表(未知)水印的可逆线性映射B，由其获得关于原始取证水印B的信息。

可以说如果存在元组置换π、σ和可逆元组转换f、g，则两个32×32可逆矩阵(或取证水印)B和B’相等，由此两个操作

T＝ποfοB，T＝σοgοB′

相同。作为该分析的结果，以上述模式，很显然不能在相等的取证水印之间进行区分。

为了之后的使用，首先获取供矩阵相等的必要和充足的条件。为此，获取一些引理。第一个引理粗略地说明元组置换和元组转换的顺序可以置换。第二个引理研究何时元组转换之前的元组置换可以是线性映射。

引理1。让π作为元组置换，并让f＝(f₁，...f₈)作为可逆元组转换。然后ποf＝f^ποπ，其中

f^π＝(f_π(1)，...，f_π(8))。

证明：如果(x₁，...x₈)^T是任一32位矢量，具有元组x₁，...x₈，则所述矢量y＝ποf(x)满足

y_i＝f_π(i)x_π(i)，

对于所有i适用。现在，对于所有矢量x而言，π(x)＝(x_π(1)，...，x_π(8))，并且因此f^ποπ(x)＝y＝ποf(x)。

□

引理2。让τ作为元组置换，让h＝(h₁，...h₈)作为可逆元组转换，并让K作为可逆线性映射，以便τοh＝K。假设该映射的矩阵K被划分成4×4的子矩阵K_i，j，对于i，j＝1，...，8。则每个h_i是元组上的可逆线性映射；此外，对于每个j，当且仅当τ(i)＝j时可获得K_i，j≠0。

证明：让K＝(K₁，...K₈)^T被划分为8个4×32矩阵K₁，...，K₈。现在，如果x＝(x₁，...x₈)^T是任一32位矢量，具有元组x₁，...x₈，则所述矢量y＝π°h(x)＝Kx满足

y_i＝h_τ(i)x_τ(i)＝K_ix，          (10)

对于所有i。现在，让j随机，并且让j＝τ(s)。假定矩阵K_s＝(K_s，1，...K_s，8)被划分成4×4的子矩阵K_s，1...K_s，8。现在如果对于所有i≠j，x_i＝0，并且x_j＝z为随机，则从(10)可以得出

y_s＝h_j(z)＝K_s，jz；

因此

$h_j=K_{{\mathrm{\τ}}^{-1}\left(j\right),j}$

是线性映射，由于它是可逆的因此非零。此外，通过让x_s＝z，x_r＝u，和x_i＝0(对于所有i≠r，s)，且z、u随机，则接下来的是对于所有i≠τ^-1(j)。□

从这两个引理，可以获得如下。

定理3。让N＝(N₁...N₈)^T和M＝(M₁...M₈)^T作为两个矩阵，每个被划分成尺寸为4×32的子矩阵N₁，...，N₈和M₁，...，M₈。则当且仅当存在元组置换v和可逆4×4矩阵的集合L₁，...，L₈时N和M相等，以便

N_v(i)＝L_iM_i，

对于i＝1，...，8。

证明：设想M和N相等。则存在元组置换π、σ和可逆元组转换f、g，以便

ποfοN＝σοgοM。

因此

NM^-1＝f^-1οπ^-1οσοg。

使用引理1，对于合适的元组置换τ和可逆元组转换h，f^-1οπ^-1οσοg可以被写为τοh。则对于线性映射K＝NM^-1，可以保持

K＝τοh；

因此，通过引理2，映射 $L_j=K_{{\mathrm{\τ}}^{-1}\left(j\right),j}$ 是可逆的，并且当τ(i)≠j时K_i，j＝0。

因此，我们有

$N_i=\underset{j=1}{\overset{8}{\mathrm{\Σ}}}{K}_{i,j}{M}_j=K_{i,\mathrm{\τ}\left(i\right)}{M}_{\mathrm{\τ}\left(i\right)};$

写出i＝τ(i)和v＝τ^-1，可以获得

N_v(j)＝L_jM_j 。

相反地，可以简单地看出如果条件保持则两个矩阵N和M事实上相等。□

推论4。让可逆矩阵N被划分成尺寸为4×4的子矩阵N_i，j，对于i，j＝1，...，8。则当且仅当在每个元组行和每个元组列中精确地一个子矩阵N_i，j非零时N和尺寸32×32的单位矩阵I相等。

证明：定理3的直接结果。□

在所假定的攻击模式中，攻击者可以转换它的水印(尺寸32×32的矩阵)为等价矩阵，而不转换为其它。定理3可以用于估计与任一给定的一个相等的矩阵的最大数，并且因此估计本质上不同的取证水印的最小数。为此，让N_inv(n)表示可逆尺寸的n×n(二元)矩阵的数量。正如所公知并且简单地可以看出的，

N_inv(n)＝(2ⁿ-1)(2ⁿ-2)(2ⁿ-4)…(2ⁿ-2^n-1)；(11)

因此

N_inv(4)＝(16-1)(16-2)(16-4)(16-8).               (12)

而且，8个元组上的置换数为8！＝8.7.6.5.4.3.2.1。接下来的是定理3的结果。

定理5。等于给定尺寸的32×32矩阵的矩阵数N_eq(M)满足

N_eq(M)≤N_inv(4)⁸8！。

证明：实际上，通过定理3，每个这样的矩阵N由元组置换τ确定，其存在8！和八个可逆尺寸的4×4的矩阵L₁，...，L₈，对于其中每一个来说存在N_inv(4)个选择。□

推论6至少有

N_inv(32)/(N_inv(4)8⁸！)≈5.10²⁶⁸

个不等的可逆尺寸为32×32(二元)矩阵(不等价水印)。接下来，假设N个取证水印M₁，...，M_N已经被分发，想象攻击者已经将他的水印改变成等价水印N。为了建立攻击者的原始水印，上面已经注意到可以监视映射T的输入/输出表现，已知其形式

T＝ποfοN，(13)

但是具有未知的元组置换π，可逆元组转换f和可逆矩阵N。为了识别攻击者，需要能够测试(13)中的矩阵N是否与给定矩阵M相等。首先注意不失普遍性地可以认为M＝I，所述单位矩阵。实际上，如果有必要，取代T，操作T’＝T°M^-1可以被调查，其形式为

T＝ποfο(NM^-1)；

由所述分析显然的是当且仅当NM^-1等于I时N等于M。

下面，概括出程序来检测给定映射T＝ποfοN是否具有等于I的N。在此方面，所述任务是产生多个32位输入矢量x₁，...，x_m，以便对于i＝1，...，m，输出矢量y_i＝T(x_i)的检测足够决定N是否等于I。下面，将解释如果使用的输入矢量数m至少为32则如何测试等价。

让m＝33。对于j＝1，...，32，取x_j＝e_j，其中e_j表示第j个单元矢量，在第j位中具有“1”，其它位中具有“0”。最后，取x₃₃＝0，所有非零矢量。写出y_j＝T(e_j)以表示对于i＝1，...，32的第j个输出矢量，并且写作c＝T(0)以表示最后的输出矢量。想象c＝(c₁，...，c₈)^T具有元组c₁，...，c₈。对于i＝1，...，8，让C_i表示尺寸为4×4矩阵，其所有列等于c_i。

现在考虑尺寸为32×32的矩阵Y，其具有矢量y_j作为它的第j列，对于j＝1，...，32。将Y划分成尺寸为4×4的子矩阵Y_i，j。现在，如果(a)每个元组行i中除了子矩阵Y_i，s之外所有的都等于C_i，并且(b)每个元组行j中除了子矩阵Y_r，j之外所有的都等于C_r，则N等于I。相反地，如果不是所述情况，则N不等于I。(事实上，如果已知N可逆，则仅测试(b)即足够，因为(b)暗含(a))。

对此解释如下。将32位的位置划分成八个元组位置集合J₁＝{1，2，3，4)，...，J₈＝{29，30，31，32}。将N划分成尺寸为4×4的子矩阵N_i，j，对于i，j＝1，...，8。首先，假设N等于I。根据推论4，如果八个元组行的每一行中和八个元组列的每一列中一个子矩阵N_i，j精确地为非零，则N等于I。因此存在置换τ以便N_i，j精确地为非零，当τ(i)＝j时。请注意，如果八个元组列的每一列中一个子矩阵N_i，j精确地为非零，则或者是对于元组行保持相同的陈述，或者存在其中所有子矩阵为零的元组行；如果N可逆，则第二种可能性不会发生。

首先，考虑c＝T(0)。显然地，N(0)＝0，因此c＝ποf(0)，从而对于所有i来说c_i＝f_x(j)(0)。

接下来考虑元组集合J_j中包含的某r，对于{1，...，4}中的某s，r＝4j+s。然后，Ne_r＝z_r＝(z_r，1，...，z_r，8)^T，其中z_r，j等于N_i，j的第s列；其结果是，z_r，j＝0，四位全零矢量，除了τ(i)＝j时。则第r个输出矢量y_r＝(y_r，1，...，y_r，8＝ποf(z_r)满足

y_r，i＝f_π(i)(z_r，π(i))。

因此，y_r，i＝f_π(i)(0)＝c_i，除了可能在τ(i)＝j时。这对于J_j中的所有r适用；所以由于y_r，j是子矩阵Y_i，j的第s列，则接下来

Y_i，j＝C_i，

除了可能在τ(i)＝j时。

相反地，假设N不等于I。则存在元组列，叫做列j，其包含两个非零子矩阵，叫做元组行i₁和i₂(其中i₁≠i₂)。因此在1，...，4中存在列s₁，s₂，以便N_i1，j中的列s₁和N_i2，j中的列s₂二者非零。现在，让r₁＝8j+s₁，r₂＝8j+s₂(均在元组位置集合中)并考虑两个矢量 $z_{r_t}={\mathrm{Ne}}_{r_t}.$ 现在如果 $z_{r_t}=(z_{r_t,1},...,z_{r_t,8}),$ 则两个元组

和

非零，并且因此，对于t＝1，2， $f_{i_t}(z_{r_t,i_t}\≠c_{{\mathrm{\π}}^{-1}\left(i_t\right)}).$ 其结果是，对于t＝1，2，输出矢量

的元组π(i_i)不等于

并且因此矩阵Y不具有期望的形式。

下面给出上述程序的简单公式化。首先，计算c＝(c₁，...，c₈)，同时c＝T(0)。接下来，对于每个元组j＝1，...，8，在T到c条件下比较四个单元矢量e_8j+1，...，e_8j+4的图像u₁，...，u₄。现在应当存在唯一的元组数τ(j)，以便仅仅在元组τ(j)中矢量u₁，...，u₄与c不同。如果对于每个j都是这种情况，则N等于I，如果不是，则N不等于I。

该处理几乎是最理想的。实际上，下面的定理示出至少32个输入矢量需要被确定等价。

定理7.让x₁，...，x₃₂是任意31个输入矢量。则存在不等于I的尺寸为32×32的矩阵N，以便对于所有i，Nx_i＝x_i。

证明：让b表示与所有矢量x_i正交的非零矢量(必须存在这样的矢量，因为整个空间的维度为32)，并且让H＝b^⊥。让v作为矢量，(b，v)＝1；因此 $v\∉H.$ 最后，让 $w\∉H$ 作为H之外的第二矢量，且w≠v。因此(b，w)＝1，并且因此(b，v-w)＝0，即v-w∈H。考虑线性可逆映射N，其将h∈H映射到其自身上(以便N充当N上的单位)，并将v映射到w上。其保持

N＝I+[β₁(w-v)…β₃₂(w-v)]，              (14)

其中b＝(β₁，...，β₃₂)由位β_i组成。实际上，如果x＝(x₁，...，x₃₂)，则

Nx＝x+[β₁(w-v)…β₃₂(w-v)]x

＝x+(x₁β₁+…+x₃₂β₃₂)(w-v)

＝x+(x，b)(w-v)，

因此对于x∈H，Nx＝x，并且Nv＝v+(v，b)(w-v)＝v+(w-v)＝w。

最后的步骤是示出可以选择H之外的w以便N(具有如(14)中的矩阵)不等于I。为此，对于元组v₁，...，v₃₂，让v＝(v₁，...，v₈)，并且对于元组b₁，...，b₈，让b＝(b₁，...，b₈)。现在区分两种情况。

如果对于一些j≠1，b_j≠0，则取w＝(w₁，...，w₈)，对于i≠j来说w_i＝v_i以及对于一些元组u_j≠0((u_j，b_j)＝0)来说，w_j＝v_j+u_j。然后w-v＝u＝((w₁，...，w₈))，对于i≠j和u_j≠0来说u_i＝0。

如果b₂＝...＝b₈＝0，则b₁≠0现在取w＝(w₁，...，w₈)对于i≠2和w₂≠v₂来说w_i＝v_i。再次w≠v并且(w，b)＝(w₁，b₁)＝(v₁，b₁)＝(v，b)＝1，以便 $w\∉H.$

在两种情况下，N的第一元组列在元组行1和元组行j≠1(第一种情况下)或者元组行2(第二种情况下)中非零，并且因此在两种情况下根据推论4，N不等于I。总结：可以N＝I，因此N≡I。但是也可以是N＝T(考虑π和f为单位的情况)。

□

测试等价

假设对于某未知的元组置换π＝(π₁，...，π₈)、可逆元组转换f＝(f₁，...，f₈)，以及可逆尺寸为32×32的线性转换N，映射T的形式为T＝ποfοN。此外假设给定任何输入矢量x可以计算输出矢量y＝T(x)。则接下来的算法决定N是否等于任何给定的可逆尺寸为32×32的线性转换M。(这里0表示32位全零矢量，e_i表示32位第i个单元矢量，其在位i为“i”，在所有其它位为零。)

equivalent:＝true；

int array[1:32]c:＝T(0)；

int r:＝1；

while (r≤8and equivalent)do

begin

           int n:＝0；//nibble number known to differ

           int s:＝1；//testing image of vector e_4r+s

           while (s≤4and equivalent)do

           begin

                int array[1:32]d:＝T(M^-1e_4r+s)-c；

                if(d＝(d₁，...，d₈)has more than one nonzero

nibble)

                       or

                       (n≠0and d_m≠0andm≠n)

                 then begin equivalent:＝false；break；end；

                 if(d_m≠0)then  n:＝n；//nibble number n

differs

                  s:＝s+1；

            end；

            r:＝r+1；

end

//here M≡N  if and only if equivalent＝true.

创建不等价水印

考虑包含所有尺寸为32×32的二元矩阵W的集合{W}，在被划分为尺寸为4×4的子矩阵W_i，j(对于j＝1，...，8)时，其具有下列特点：

·每当i＞j，分组W_i，j是全零矩阵

·所有分组W_i，j是尺寸为4×4的单位矩阵。

因此任何矩阵W∈{W}可逆并且具有下列形式

$W=\left(\begin{array}{cccccccc}I& W_{\mathrm{1,2}}& W_{\mathrm{1,3}}& W_{\mathrm{1,4}}& W_{\mathrm{1,5}}& W_{\mathrm{1,6}}& W_{\mathrm{1,7}}& W_{\mathrm{1,8}}\\ O& I& W_{\mathrm{2,3}}& W_{\mathrm{2,4}}& W_{\mathrm{2,5}}& W_{\mathrm{2,6}}& W_{\mathrm{2,7}}& W_{\mathrm{2,8}}\\ O& O& I& W_{\mathrm{3,4}}& W_{\mathrm{3,5}}& W_{\mathrm{3,6}}& W_{\mathrm{3,7}}& W_{\mathrm{3,8}}\\ O& O& O& I& W_{\mathrm{4,5}}& W_{\mathrm{4,6}}& W_{\mathrm{4,7}}& W_{\mathrm{4,8}}\\ O& O& O& O& I& W_{\mathrm{5,6}}& W_{\mathrm{5,7}}& W_{\mathrm{5,8}}\\ O& O& O& O& O& I& W_{\mathrm{6,7}}& W_{\mathrm{6,8}}\\ O& O& O& O& O& O& I& W_{\mathrm{7,8}}\\ O& O& O& O& O& O& O& I\end{array}\right)---\left(15\right)$

任何两个来自{W}的不同的矩阵不等价。想看出这点，使用定理3。让N、M作为两个来自{W}的等价矩阵。然后存在元组置换τ和可逆尺寸为4×4的矩阵L₁，...，L₈，以便对于i＝1，...，8来说N_τ(i)＝L_iM_i。现在由于M和N在{W}中，因此M和N的元组行i精确地开始于分组i之前的i-1非零分组；而且L_iM_i精确地开始于某非零分组L_i之前的i-1全零分组。其结果是，元组行数i可以从N_i和L_iM_i而唯一地被识别出来。因此，置换τ必须是恒等式，每个L_i必须是单位矩阵，并且N＝M。请注意{W}包含(2¹⁶)^7+6+...+1＝2⁴⁴⁸＞10¹³⁴个矩阵。通过从{W}选择不同矩阵可以创建不同的水印版本。

以不同的等价类创建水印的替代方法包括随机地选择线性转换N并使用用于等价检测的算法以验证所选N是否等于任何先前所选的线性转换。

请注意上述内容中，重点在于查找表网络的一些特殊情况及其模糊化和水印化上。可以理解的是水印化原理可以在与这些特殊情况的特征无关的情况下而被采用。例如，AES已经被用作主要载体来解释使用编码和混合双射的白盒实现。然而，本领域技术技术人员明了，AES、编码和混合双射并不必须应用于查找表网络的水印。

图10示出本发明的实施例。图中示出系统600，用于方便跟踪计算方法602的实现的拷贝的用户。计算方法602的用户632可以具有他们的执行所处的基站，在此情况下各个用户可以通过他们各自基站而被统一。可替换地，用户可以具有不同的IP地址或者可以使用他们自己的登录ID和密码登录至他们从其获得执行的系统。例如查找表网络的版本的对象因此可以与用户或基站相关联，参考例如IP地址和登录ID。以将对象与基站或它们的用户相关联的其它分配系统和方法对于本领域技术人员是显然的。系统600可以实现于硬件和/或软件中。例如，它可以是运行在内容提供者处的服务器上的软件模块。系统600被设置为用于准备计算方法602的实现，以供分配至至少一个用户632(或基站610)。为此，系统600包括网络生成器604，用于产生代表计算方法的步骤的查找表网络。例如，查找表网络采取上面有关图1-9所述的白盒实现的形式。然而，本领域技术人员可以想到和采用产生这种用于给定计算方法的查找表网络的其它方法。

系统600还包括个性化器606。所述个性化器产生多个不同版本的查找表网络。它通过改变查找表网络中的至少一个值来产生。对于不同版本的查找表网络来说，由不同版本的查找表网络执行的计算的最终结果基本上相同，特别是对于相关的输入值域。相关的输入值域例如对应于这样的值，即其根据它的性能需要在所述实现的日复一日的使用中被处理。所述改变可以以不同方法进行。例如，第一查找表可以通过交换查找表的输出值对来改变。为了保持网络的相同输出值，查找表网络中至少下一表的条目可以被交换，以不进行对第一查找表所做的改变。取决于查找表网络的结构，可以对单个查找表进行变化，而不从整体上改变网络的输出值。所述网络也可以被附加的查找表扩展或者重新设置，只要相关的输入值域的结果基本上保持不变。

系统600还包括相关器608。所述相关器将所创建的不同网络与数据库614中存储的用户或基站通过他们的IP地址、登录ID或任何其它类型的标签而相关联。所产生的已经与用户相关联的查找表网络存储在数据库614中。

实施例中，计算方法的特征在于加密策略，例如AES。对于本领域技术人员来说，适用于数字权利管理的其它加密策略是显然的。所述加密策略与加密密钥一起作用。所述个性化器被设置为产生多个版本的查找表网络，所有使用相同密钥执行相同的加密策略。同时，各个查找表版本都是唯一的，以便从查找表版本可以找出谁是与所述版本相关联的用户。这对于传播系统特别有意义，其中大量用户被提供了相同的传播数据。所传播的数据被加密并且所有用户需要采用相同的加密策略和密钥来对所传播的数据解密。例如个性化器产生加密策略的不同白盒实现。

实施例中，个性化器被设置为创建计算方法的白盒实现。白盒实现的示例如上给出。按照原理，它们可以为任何计算方法所创建。个性化器608被设置为以最终结果不变的方式来改变查找表中的值。例如，可以改变元组编码或一个或多个混合双射。替代或附加地，网络结构可以被改变，即通过网络的数据流被改变的方式。各个查找表可以被添加至查找表网络或者从其去除。

实施例中，个性化器被设置为通过线性或非线性运算符将白盒实现模糊化。该运算符被集成在网络中的第一多个查找表中，而运算符的逆被集成在网络中的第二多个查找表中。不同的运算符用于不同的版本中。这意味着，当攻击者想要去除所选运算符的所有轨迹，他需要多多了解第一和第二多个查找表的相互依存性。这些表中的一个或多个可以具有输入和/或输出编码。这使得更加难以找出所使用的运算符，并且当针对不同版本不同地选择了这些输入和输出编码时，给水印增加了更多的特征特点。当应用于AES实例时，运算符可以是混合双射，并且输入和/或输出编码可以是元组编码。

优选地，所述个性化器被设置为使用不同等价类中的运算符来创建版本，其中等价类包括其对应的查找表网络可以通过对输入和/或输出编码进行变化而从彼此获得的运算符。所述输入和/或输出编码可以轻易地被攻击者改变，因此需要选择不同的运算符，以便在改变这些编码之后仍然能够将它们彼此区别开。标题为“等价问题”的部分中所述的等价类就是它的示例。

更普遍地，个性化器606被设置为以不同等价类创建版本，其中等价类包括从通过将来自被认为是攻击者所能及的修改集合的修改应用于版本而从彼此获得的版本。这可以通过随机地应用修改以产生版本并且验证它是否属于先前产生的版本的等价类而实现。如果结果是已经产生了相同等价类的版本，则新产生的版本被丢弃，并产生另一版本以代替被丢弃的版本。可替换地，个性化器606被设置为根据等式(15)(伪)随机地选择矩阵W∈{W}之一。

一个实施例包括分配服务器624。分配服务器624从数据库614中取与用户632相关联的版本并将所述版本提供给用户632或他的基站610。为了确保只有期望的接受者接收到所述版本，使用用户专用密钥对其加密。内容(例如音频数据、视频数据、软件等等)由查找表网络的版本中所执行的加密策略和加密密钥所加密。被加密的版本和内容被传输至用户632的基站610。可以理解的是这只是分配方法的一个实施例。被个性化的版本可以任何方式分配，全部或部分加密或不加密。它们可以经由网络(例如互联网)或经由存储介质(例如CD)而被分配。一种安全地分配所述版本的方法是通过经由分配渠道只发送查找表网络的一部分。该部分可以是类型II表20(具有对应的类型IV表22)。类型III表24(具有对应的类型IV表26)可以不同方法提供给基站，例如通过智能卡。这加强了水印和用户之间的相关性，因为水印可以完全或部分地由智能卡中存在的查找表部分所限定。

一个实施例包括基站610。基站610包括用于接收代表计算方法的步骤的查找表网络。可以利用用户专用密钥对所述网络加密，在此情况下它首先被解密。从分配服务器624接收所述网络。基站610包括数据处理单元612，用于将查找表网络634应用于处理数据。所述数据例如是音频或视频内容，例如从分配服务器624或从CD-ROM提供。查找表网络具有由系统600向其提供的水印。虽然原理上从服务器624接收的查找表网络因此是唯一的，但是，可以向基站610的输入提供另一查找表网络，例如通过攻击者。所述其它查找表网络可能提供比从分配服务器624接收的查找表更多或不同的功能。虽然基站由此具有和其它版本的查找表网络不同的功能，但是可以跟踪查找表网络的起源，因为它具有唯一的特性并且与原始用户或基站相关联。

一个实施例包括用于识别计算方法的实现的拷贝的系统616。系统616连接至包括这些实现的不同版本的数据库614。一个或多个查找表网络(此后称为输入版本)被提供给系统616的输入618，以供与数据库614中存储的版本匹配。每个实现包括代表计算方法的步骤的查找表网络。系统616包括比较器620，用于将实现中的查找表与版本中的至少一个进行比较。比较器可以由字节-字节比较来实现，它可以报告所述输入版本是否与数据库中的版本匹配。也可以报告所述输入版本与数据库中的版本之间的相似程度。也可以找出数据库614中与输入版本最为相似的版本。

系统616包括等价类建立器622，以建立输入版本所属的等价类，并识别数据库中的一个或多个版本是否具有相同的等价类。等价类优选地包括可以通过将来自被认为是攻击者所能及的修改集合的修改应用于版本而彼此可以被转换的所有版本。

图11示出本发明的实施例，其可以实施于例如内容提供者的服务器中。也可以实施于标准PC中。图中示出通信部分95，用于提供例如查找表网络的版本和/或将被处理的内容的信息。通信部分95被设置为例如连接至互联网。查找表网络的版本也可以存储在例如DVD或CD的存储介质96上。图中还示出处理器92和存储器91。所述存储器包括指令，用于使得处理器以上述方法产生多个版本的查找表网络。查找表网络代表计算方法的步骤，例如具有特殊加密密钥的加密策略。在存储器91中，所产生的各个版本与各个用户相关联，例如通过表。图中还示出例如键盘和/或鼠标的输入94，和供操作者操作系统的显示器93。

也可以参考图11解释另一实施例。该实施例包括基站，例如个人计算机、机顶盒、数字视频播放器、终端或智能卡。所述基站包括通信部分95，用于连接至服务器，以获得与用户相关联的查找表网络的版本。此外或替代地，基站包括用于读取存储介质96(例如CD或DVD)的装置，存储介质上可以存储查找表网络的版本。所述基站包括处理器92，用于通过采用查找表来处理数据。数据也可以经由通信部分95和/或存储介质96而获得。例如，查找表网络代表计算方法的步骤。计算方法可以包括任何数据处理方法。例如，视频加强算法的一个或多个处理步骤(例如PixelPlus)可以通过查找表网络实施。而且，查找表网络可以执行加密策略的步骤，例如加密算法或解密算法。这种解密算法可以用于解密内容以呈现在显示器93上。所述系统包括用户输入94，例如键盘或遥控，以让用户控制所述系统。

可以理解的是本发明还扩展至计算机程序，特别是载体上或其中的计算机程序，适用于将本发明付诸实践。所述程序可以是源代码、目标代码、代码中间源和目标代码，例如部分符合形式或其它任何适用于根据本发明的方法的执行的形式。所述载体可以是任何能够装载程序的实体或设备。例如，所述载体可以包括存储介质，例如ROM，例如CD ROM或半导体ROM，或磁性记录介质，例如软盘或硬盘。此外，所述载体可以是可传递载体，例如电或光信号，其可以经由电或光缆或通过无线电或其它方式传输。当程序包含在这种信号中时，所述载体可以由这种线缆或其它设备或装置构造。替代地，所述载体可以是集成电路，其中包含所述程序，所述集成电路适用于执行或用于相关方法的性能中。

应当注意，上述实施例说明而非限制本发明，并且本领域技术人员能够设计许多替换实施例，而不脱离权利要求的范围。权利要求中，括号内的附图标记不构成对权利要求的限制。词语“包括”及其变形的使用不排除存在权利要求所述之外的元件或步骤。元件之前的冠词“一”或“一个”不安排存在多个这样的元件。本发明可以通过包括一些不同元件的硬件并通过被适当编程的计算机所实现。在列举出一些装置的设备权利要求中，这些装置中的一些可以由一个相同的硬件项实现。主要的事实是多个不同的从属权利要求中所列的一些措施不指示这些措施的组合不能被有利地利用。

Claims (18)

1.一种用于方便跟踪计算方法(602)的实现的拷贝的系统(600)，所述系统包括

网络生成器(604)，用于产生代表计算方法(602)步骤的查找表的网络，所述网络通过将第一查找表的输出值用作不同的第二查找表的输入值而形成；

个性化器(606)，用于通过改变查找表网络中的至少一个值来产生多个不同版本的查找表网络，对应于输入值的相关域的所述版本的最终结果对于每个版本而言基本上是相同的；

相关器(608)，用于将各个版本与各个基站(610)或基站(610)的用户(632)相关联。

2.根据权利要求1的系统，其中所述计算方法(602)包括加密策略和加密密钥，网络生成器(604)和个性化器(606)被设置以用于产生能够利用所述加密密钥执行加密策略的查找表网络。

3.根据权利要求1的系统，其中所述个性化器(606)被设置为用于创建所述计算方法(602)的白盒实现。

4.根据权利要求1的系统，其中所述白盒执行的输出编码和/或输入解码在不同版本中是不同的。

5.根据权利要求1的系统，其中所述个性化器(606)被设置为用于由运算符将白盒实现模糊化，针对不同版本所述运算符被不同地选择，其中所述运算符被集成在网络中的第一多个查找表中，而运算符的逆被集成在网络中的第二多个查找表中。

6.根据权利要求1的系统，其中所述第一多个查找表中的至少一个或所述第二多个查找表中的至少一个具有输入和/或输出编码，所述输入和/或输出编码被网络中它的相对于经过网络的数据流的各个前趋和/或后继取消。

7.根据权利要求1的系统，其中所述运算符为线性混合双射，并且所述输入和/或输出编码中的至少一个是非线性的。

8.根据权利要求1的系统，其中所述个性化器(606)被设置为用于使用不同等价类中的运算符来创建各版本，其中等价类包括这样的运算符，即它的对应查找表网络可以通过将来自预定修改集合的修改提供给所述输入和/或输出编码而从彼此获得。

9.根据权利要求1的系统，其中所述个性化器(606)被设置为用于创建不同等价类中的各版本，其中所述等价类包括可以通过将来自预定修改集合的修改提供给所述版本而从彼此获得的各版本。

10.根据权利要求1的系统，进一步包括用于将查找表的各个版本(634)经由单个介质发送给相关基站(610)或用户(632)的输出。

11.根据权利要求1的系统，其中所述系统(600，624)用于受控地将内容分配给多个基站，并且所述计算方法(602)包括解密方法，所述系统进一步包括

加密器(626)，用于使用与用户相关联的用户专用加密密钥来对与用户相关联的版本加密，以获得加密的版本；

内容预处理器(628)，用于根据加密策略和加密密钥对内容加密，以获得加密的内容；

输出(630)，用于向用户提供加密的版本和加密的内容。

12.一种用于为用户执行计算的系统(610)，包括

数据处理单元(612)，用于将代表计算方法(602)的步骤的查找表网络(634)应用于数据，所述网络通过将第一查找表的输出值用作不同的第二查找表的输入值而形成；

所述查找表网络(634)形成多个不同版本查找表网络的一版本，所述多个不同版本通过改变查找表网络中的至少一个值而获得，对应于输入值的相关域的计算方法的最终结果对于每个版本来说基本上相同；

各个版本，其与各个用户相关联。

13.一种用于识别计算方法的实现的拷贝的系统(616)，其中所述实现包括代表计算方法(602)的步骤的查找表网络，所述网络通过将第一查找表的输出值用作不同的第二查找表的输入值而形成；

所述查找表网络作为通过改变查找表网络中的至少一个值而获得的多个不同版本的查找表网络的一版本，对应于输入值的相关域的计算方法的最终结果对于每个版本来说基本上相同；

所述系统(610)包括：

比较器(620)，用于将所述实现中的至少一个查找表与至少一个版本进行比较。

14.根据权利要求13的系统，进一步包括等价类建立器(622)，用于建立对应于所述实现中的版本的等价类，其中等价类包括能够通过将来自被认为是攻击者所能及的修改集合的修改应用于开始版本而从所述开始版本获得的版本。

15.一种便于跟踪计算方法的实现的拷贝的用户的方法，所述系统包括

产生代表计算方法步骤的查找表网络(28)，所述网络通过将第一查找表(20)的输出值用作不同的第二查找表(22)的输入值而形成；

通过改变查找表网络中的至少一个值而产生查找表网络(28)的多个不同版本，对应于输入值的相关域的版本的输出值对于每个版本来说基本上相同；

将各个版本与各个用户相关联。

16.一种计算机程序产品，包括用于使处理器执行根据权利要求15的方法的指令。

17.一种识别计算方法的实现的拷贝的方法，其中所述实现包括代表计算方法步骤的查找表网络(28)，所述网络(28)通过将第一查找表(20)的输出值用作不同的第二查找表(22)的输入值而形成；

查找表网络(28)作为通过改变查找表网络中的至少一个值而获得的多个不同版本的查找表网络的的一版本，对应于输入值的相关域的计算方法的最终结果对于每个版本来说基本上相同；

所述方法包括：

将所述实现中的至少一个查找表与至少一个版本进行比较。

18.一种计算机程序产品，包括用于使得处理器执行根据权利要求17的方法的指令。

Images