数据转换器、数据转换方法和程序的制作方法
专利名称：数据转换器、数据转换方法和程序的制作方法
技术领域：
本发明涉及数据转换器、数据转换方法和程序。更具体地，本发明涉及例如对输入 消息数据进行哈希值生成处理的数据转换器、数据转换方法和程序。
背景技术：
在数据转换处理如加密处理中经常使用对输入数据执行哈希处理的哈希(Hash) 函数。哈希函数是用于根据供应的消息来计算定长压缩值(摘要)的函数。已知的哈希函 数包括具有1 位输出值的MD5、具有160位输出值的SHA-1、具有256位输出值的SHA-256等。例如基于对增加抗分析性的请求，哈希函数需要以下抗性抗前像性(Preimage
resistance)抗第 2 前像性(Second pre image resistance)抗冲突性(Collision resistance)下文将简述这些抗性。在生成y = h(x)作为输出的哈希函数(其中输入是χ而哈希函数是h)中，抗前 像性对应于计算输入X使得输出y为y = h(x)的难度。抗第2前像性对应于在一个输入值χ已知的情况下发现满足h (X’)= h (χ)的另 一输入值X’的难度。抗冲突性对应于发现满足h(x’ ) =h(x)的两个不同输入值X和X’的难度。认为这些抗性越高、哈希函数具有的安全特性就越高。在前级使用的哈希函数中，分析方法的最新发展发现了上述抗性的弱点。例如已 经变得清楚，在经常用作哈希函数的MD5、SHA-I等中，抗冲突性不满足大量系统请求级。 另外作为现有哈希函数，包括输出长度相对长的SHA-256 ；然而仍有安全特性之忧，因为 SHA-256遵循SHA-I的设计原理，因此期望有基于其它设计原理的具有更高安全特性的哈 希函数。
发明内容
做出本发明以解决上述问题，并且本发明的目的在于提供一种实现具有高安全特 性和高处理效率的哈希函数的数据转换器、数据转换方法和程序。本发明的第一方面提供一种数据转换器，该数据转换器包括数据转换部，接收消 息数据以生成哈希值，该数据转换部被配置成在并行地处理构成消息数据的分割数据块的 多个处理序列中，执行利用多个压缩函数执行部的数据转换处理，其中多个压缩函数执行 部中的各压缩函数执行部被配置成进行以下处理利用消息调度部的处理，该消息调度部 接收消息数据的对应分割数据块以进行消息调度处理；以及利用链接变量处理部的处理， 该链接变量处理部接收来自消息调度部的输出和作为来自前级处理部的输出的中间值以 通过对接收的数据进行压缩来生成位数与中间值的位数相同的输出数据，并且在多个处理序列中分别进行并行处理的多个压缩函数执行部被配置成共同地使用消息调度部和链接 变量处理部中的一个或者两个并且允许利用单个消息调度部或者单个链接变量处理部。另外，在本发明的数据转换器的一个实施例中，在多个处理序列中分别进行并行 处理的多个压缩函数执行部包括由多个压缩函数执行部共同地使用的单个共同消息调度 部，共同消息调度部被配置成接收构成消息数据的分割数据块、通过对分割数据块进行消 息调度处理来生成输出数据并且将所生成的输出数据输出到多个链接变量处理部，并且多 个链接变量处理部中的各链接变量处理部被配置成并行执行如下处理，在各处理中对应的 链接变量处理部接收来自共同消息调度部的输出和作为来自前级压缩函数执行部的输出 的中间值来对接收的数据进行压缩，以由此生成位数与中间值的位数相同的输出数据。另外，在本发明的数据转换器的一个实施例中，在多个处理序列中分别进行并行 处理的多个压缩函数执行部包括由多个压缩函数执行部共同地使用的单个共同链接变量 处理部，在进行并行处理的多个压缩函数执行部中的各压缩函数执行部中提供的多个消息 调度部被配置成接收消息数据的相同的分割数据块、通过消息调度处理来生成输出数据并 且将所生成的输出数据输出到共同链接变量处理部，并且共同链接变量处理部被配置成接 收多个消息调度部的输出和作为来自前级压缩函数执行部的输出的中间值来对接收的数 据进行压缩以由此生成位数与中间值的位数相同的输出数据。另外，在本发明的数据转换器的一个实施例中，在进行并行处理的多个压缩函数 执行部中的各压缩函数执行部中提供的多个消息调度部被配置成接收消息数据的相同分 割数据块、通过消息调度处理来生成输出数据并且将所生成的输出数据的异或运算输出到 共同链接变量处理部。另外，在本发明的数据转换器的一个实施例中，消息调度部由具有中间输出的转 置函数执行部配置，转置函数执行部重复地执行转置处理以输出作为各转置处理的结果的 中间值，并且链接变量处理部被配置成包括具有附加输入的转置函数执行部，转置函数执 行部利用从具有中间输出的转置函数执行部输出的中间值作为附加输入来重复地执行转
置处理。另外，在本发明的数据转换器的一个实施例中，链接变量处理部被配置成利用XOR 结果作为用于随后的转置处理的输入数据，XOR结果是在从具有中间输出的转置函数执行 部输出的中间值与前级中的转置处理的结果之间的异或运算的逻辑值。另外，在本发明的数据转换器的一个实施例中，转置函数执行部执行的各转置处 理包括对输入数据的部分或者全部进行的非线性转换处理和作为数据互换处理的交换处 理。另外，在本发明的数据转换器的一个实施例中，非线性转换处理是包括使用常数 的异或运算、非线性转换和使用线性转换矩阵的线性转换的处理。另外，在本发明的数据转换器的一个实施例中，在转置函数执行部执行的各转置 处理中进行的线性转换处理是利用多个不同矩阵根据DSM(扩散切换机制)执行的处理。另外，在本发明的数据转换器的一个实施例中，转置函数执行部执行的转置处理 被配置成分别利用互不相同的多个常数组来进行数据处理，并且通过对基本组进行的数据 转换处理来生成的互不相同的多个常数组分别使用于转置处理中，基本组定义为将在一个 转置处理中使用的常数组。
6
另外，在本发明的数据转换器的一个实施例中，将作为基本组利用的常数组由通 过向互不相同的多个初始值S和T应用转换规则来生成的多个常数配置，并且转换规则被 配置成包括对初始值进行的更新处理，更新处理由以下表达式代表S — S · xa，T 一 T · χ其中a乒b。另外，在本发明的数据转换器的一个实施例中，对基本组进行的数据转换处理是 允许对构成基本组的各常数的位旋转操作的处理或者允许在构成基本组的各常数与预定 掩码数据之间的逻辑运算的处理。另外，在本发明的数据转换器的一个实施例中，数据转换部被配置成进行允许最 终输出的哈希值在位数上减少的减少处理，并且根据预定计算表达式来计算在构成数据转 换部的输出的多个输出数据级数中的各级数的输出位中的将减少的位数，然后根据计算的 结果来执行减少处理。另外，在本发明的数据转换器的一个实施例中，数据转换部还包括对输入数据执 行数据加扰处理的加扰处理部，多个压缩函数执行部被配置为被允许接收消息数据的所有 分割数据块的多级压缩部，多级压缩部中的一些压缩部被配置成接收加扰处理部的输出和 消息数据的分割数据块这两者以基于接收的数据来执行数据压缩处理，多级压缩部中的一 些压缩部被配置成接收前级压缩部的输出和消息数据的分割数据块这两者以基于接收的 数据来执行数据压缩处理，并且位于多级压缩部的最后一级中的压缩部被配置成输出消息 数据的哈希值。另外，本发明的第二方面提供一种数据转换方法，该方法是由数据转换器执行的 数据转换处理方法，该数据转换方法包括数据转换步骤，通过数据转换部接收消息数据 以生成哈希值，数据转换步骤是在并行地处理构成消息数据的分割数据块的多个处理序列 中，执行利用多个压缩函数执行部的数据转换处理的步骤，其中多个压缩函数执行部中的 各压缩函数执行部进行利用消息调度部的处理，消息调度部接收消息数据的对应分割数 据块以进行消息调度处理；以及利用链接变量处理部的处理，链接变量处理部接收来自消 息调度部的输出和作为来自前级处理部的输出的中间值以通过对接收的数据进行压缩来 生成位数与中间值的位数相同的输出数据，并且在多个处理序列中分别进行并行处理的多 个压缩函数执行部共同地使用消息调度部和链接变量处理部中的一个或者两个并且进行 利用单个消息调度部或者单个链接变量处理部的处理。另外，本发明提供一种在数据转换器中执行数据转换处理的程序，该程序包括数 据转换步骤，通过数据转换部接收消息数据以生成哈希值，数据转换步骤是在并行地处理 构成消息数据的分割数据块的多个处理序列中，执行利用多个压缩函数执行部的数据转换 处理的步骤，其中该程序允许多个压缩函数执行部中的各执行部执行利用消息调度部的 处理，消息调度部接收消息数据的对应分割数据块以进行消息调度处理；以及利用链接变 量处理部的处理，链接变量处理部接收来自消息调度部的输出和作为来自前级处理部的输 出的中间值以通过对接收的数据进行压缩来生成位数与中间值的位数相同的输出数据，并 且该程序允许在多个处理序列中分别进行并行处理的多个压缩函数执行部共同地使用消 息调度部和链接变量处理部中的一个或者两个并且进行利用单个消息调度部或者单个链 接变量处理部的处理。
此外，本发明的程序例如是被允许以计算机可读格式通过存储介质或者通信介质 向能够执行各种程序代码的通用系统提供的程序。以计算机可读格式提供程序；因此根据 程序的处理在计算机系统上实施。本发明的更多目的、特征或者优点根据基于附图对本发明一个示例性实施例的下 文描述或者更多具体描述将变得清楚。此外，在本说明书中，“系统”是指多个设备的逻辑集 合配置、无论个别组成设备是否容纳于一个罩中。本发明的一个示例性实施例具有如下构造，在该构造中在并行地处理构成所述消 息数据的分割数据块的多个处理序列中，执行利用多个压缩函数执行部的数据转换处理。 多个压缩函数执行部中的各压缩函数执行部进行利用消息调度部的处理和利用链接变量 处理部的处理，该消息调度部接收消息数据的对应分割数据块以进行消息调度处理，该链 接变量处理部接收来自消息调度部的输出和作为来自前级处理部的输出的中间值以通过 对接收的数据进行压缩来生成位数与中间值的位数相同的输出数据。在多个处理序列中分 别进行并行处理的多个压缩函数执行部共同地使用消息调度部和链接变量处理部中的一 个或者两个并且允许利用单个消息调度部或者单个链接变量处理部。这样的构造实现了硬 件配置尺寸的减少和处理步骤的简化。
图1是将压缩函数(f)描述为数据压缩部的图示。图2是描述具有消息填充(一种典型的域扩展方法)的MD (Merkle-Damgard)构 造的图示。图3是描述级联哈希构造的图示，该构造利用具有很小输出位大小的压缩函数来 实现具有很大输出位大小的哈希值。图4是描述具有增强安全特性的压缩部(压缩函数)的构造的图示。图5是描述哈希函数构造示例的图示，在该示例中，图4中所示压缩函数单元50 连接为MD构造。图6是将哈希函数构造示例描述为图5中所示构造使用压缩函数单元55的修改 示例的图示，在该示例中，各压缩函数中的加扰函数F以及压缩函数fl和f2的顺序改变。图7是描述通过从图6中所示构造中去除最后一个压缩函数单元中的加扰函数F 来配置的构造示例的图示。图8是描述设置每两个压缩函数处理插入加扰函数F的构造示例的图示。图9是描述推广的哈希函数执行部的构造示例的图示，在该示例中设置每k个压 缩函数插入加扰函数F。图10是描述利用两个压缩函数来实现加扰函数F的构造示例的图示。图11是描述在序列中有m个压缩函数的哈希函数的推广的构造示例的图示，其中 m是2或者更大的整数。图12是描述具有mb位输入/输出的加扰函数F的构造示例的图示。图13是描述压缩函数f的内部构造示例的图示。图14是描述为具有MD构造的哈希函数提供由消息调度部(MS部)和链接变量 (CV)处理部构成的压缩函数构造示例的图示。
图15是描述一般使用消息调度部的哈希函数的构造示例的图示。图16是描述压缩函数的构造示例的图示，该示例扩展压缩函数中的输入消息大图17是描述具有如下构造的压缩函数的构造示例的图示，在该构造中，消息调度 部分割成两个部分。图18是描述具有如下构造的压缩函数的构造示例的图示，在该构造中，消息调度 部分割成两个部分并且包括异或运算O(OR)部。图19是描述压缩函数的构造示例的图示，该函数被设置成通过推广图17中所示 的压缩函数的构造来响应于na位输入。图20是描述压缩函数的构造示例的图示，该函数被设置成通过推广图18中所示 的压缩函数的构造来响应于na位输入。图21是描述具有附加输入的转置函数的示例的图示。图22是描述具有中间输出的转置函数的示例的图示。图23是描述使用现有转置函数的压缩函数的构造示例的图示。图M是描述扩展向压缩函数施加的数据大小的压缩函数的构造示例的图示。图25是描述将输入位长度扩展为3a位的压缩函数的构造示例的图示。图沈是描述将输入位长度扩展为3a位的压缩函数的构造示例的图示。图27是描述在序列中的两个压缩函数共同地使用消息调度部的构造示例的图
示 ο图28是描述扩展向压缩函数施加的数据大小的压缩函数的构造示例的图示。图四是描述由具有中间输出的两个转置函数与具有附加输入的两个转置函数的 组合构成的加扰函数F的构造示例的图示。图30是描述被允许用作内部转置的转置函数的具体构造示例的图示。图31是描述在内部转置部(转置函数)中配置的非线性转换部的内部构造的示 例的图示。图32是描述为了使用多个不同矩阵作为在内部转置部(转置函数)的非线性转 换部中使用的线性转换矩阵[M]而设置的内部转置部的重复回合的构造示例的图示。图33是描述为了使用多个不同矩阵作为线性转换矩阵[M]而设置的内部转置部 的重复回合的构造示例的图示。图34是描述一种为总转置生成常数Cij O)、Cij (3)、…Cij(Hi)的技术的图示。
图35是描述一种减少哈希函数的输出位长度的技术的示例的图示。图36是描述一种减少哈希函数的输出位长度的技术的示例的图示。图37是IC模块的配置示例的图示，该模块作为执行根据本发明的处理的数据转换器。
具体实施例方式下文将参照附图具体描述本发明的数据转换器、数据转换方法和程序。将按以下顺序给出描述。1.域扩展方法
2.用于扩展输出大小的新颖域扩展方法3.提高新颖域扩展方法的处理效率的方法4.实现加扰函数F的方法5.域扩展方法的推广6.加扰函数的F的构造的推广7.使用不同压缩函数8.实现压缩函数的内部处理的高效方法9.扩展输入消息长度的方法10.在CV处理部和MS部中使用重复转置来实现哈希函数的方法11.扩展MS部大小的方法12.扩展CV处理部大小的方法13.扩展CV处理部和MS部大小的方法14.为域扩展方法构造加扰函数F的方法15.实现扩散能力高的转置处理的方法16.生成输出高度独立的转置函数的方法17.生成向转置函数施加的常数的处理18.为多个总转置生成常数的方法19.减少哈希函数的输出值的技术20.数据转换器的配置示例[1.域扩展方法]如上文所述，希望哈希函数执行部具有上述各种抗性、也就是抗前像性、抗第2前 像性和抗冲突性。注意本发明的数据转换器包括下文将描述的各种函数执行部，比如哈希函数执行 部和压缩函数执行部。在下文描述中，在本发明的数据转换器中执行各函数的函数执行部 中执行这里简单表达的术语“函数”。注意利用硬件或者软件或者二者来实现函数执行部。哈希函数将压缩函数用于根据施加的消息来计算定长压缩值(摘要)。当构造由 执行哈希函数的硬件或者软件构成的哈希部时，有必要让哈希部具有一种考虑到上述各种 抗性的构造。允许哈希部的构造广泛地分割成两个以下等级(1)作为第一等级的域扩展部，以及(2)作为第二等级的压缩函数的内部构造。域是作为哈希函数的输入值的最大可允许位大小(输入大小)。一个压缩函数执 行部进行将定长输入值转换成定长输出值的处理；然而一般而言，一个压缩函数执行部具 有很小的最大可允许输入位大小并且不被允许处理具有很大位大小的输入值；因此通过连 接多个压缩函数来扩展域，从而处置任意长度的消息输入。通过这样的处理允许对具有很 长位长度的输入数据进行哈希。进行这样的处理作为域扩展处理。上述抗性的级别取决于作为第一等级的域扩展构造或者作为第二等级的压缩函 数的内部构造。下文将首先描述前者(即域扩展处理)的一种新颖方案。压缩函数是用于将作为 输入值的位串转换成比输入位长度更短的位串的函数。图1图示了作为压缩部的压缩函数
图1中所示的压缩函数10是用于接收具有a位的输入值X和具有b位的初始值 Y(也就是说，共计a+b位)以生成具有b位的输出Z的函数。作为压缩函数的输入值的最 大可允许位大小称为域(输入大小)。不允许仅由一个压缩函数10处理长输入消息；因此 适当地连接压缩函数以扩展域(输入大小)，从而允许扩展输入消息大小。换而言之，允许 输入具有很长位长度的数据。图2图示了具有消息填充(一种典型的域扩展方法)的MD (Merkle-Damgard)构 造。注意例如在 R. Merkle 的"One way hash functions and des"(见 Proceedings of Crypto (密码学报)'89 (G. Brassard 编辑)，LNCS 中的 no. 435,第似8_446 页， Springer-Verlag(施普林格出版社)，1989)禾口 I. Damgard 的〃 A design principle for hash functions"(见Proceedings of Crypto (密码学 艮)'89 (G. Brassard编辑)，LNCS 中的 no. 435，第 417-427 页，Springer-Verlag(施普林格出版社)，1989)。如图2中所示，MD构造是一种允许通过串联布置压缩函数(f)来扩展输入大小的 构造。通过填充(padding)将输入消息校正为位数为a位的整数倍(压缩函数的消息输入 部大小)的值，填充是作为用于位长度调节的位数据添加处理而进行的。MtlJpM2、…、Mn_2、 Mn_」填充是受到填充的输入消息分割成的a位块。[Mn_」填充]是通过向作为输入消息最 后一块的数据[Mn_J添加作为附加位块的填充数据来获得的输入位大小为a位的数据。为了生成消息的摘要，在MD构造中利用多个压缩函数来重复如下操作在该操作 中向压缩函数11施加并且在压缩函数11中压缩具有b位的预定初始值IV和第一分割消 息Mtl以生成具有b位的值作为中间值、然后向压缩函数12施加并且在压缩函数12中压缩 中间值和后继消息，以最终获得哈希值(H)，。这时的中间值称为链接变量。已知只要各压缩函数具有抗冲突性，就允许MD构造表明整个哈希函数具有抗冲 突性，并且MD构造经常用于实际的哈希函数。使用MD构造的典型哈希函数包括MD5和 SHA-I0[2.用于扩展输出大小的新颖域扩展方法]在上述构造中描述了 b位输出的情况，现在下文将考虑生成具有很长的位长度为 2b位的哈希值的哈希函数的构造。在原样使用上述MD构造的情况下，有必要准备具有2b位输出的压缩函数。然而 一般而言，难以重新构造具有很大输出和高安全特性的压缩函数。有必要设计新颖压缩函 数并且评估该压缩函数的安全特性，并且输出大小越大，就越难以设计和评估压缩函数。因 此希望利用已经评估的具有b位输出的压缩函数来构造具有2b位输出的哈希函数。作为一种利用具有很小输出位大小的压缩函数来实现具有很大输出位大小的哈 希值的相关技术，已知一种级联(cascading)哈希构造。将参照图3描述级联哈希构造。级联哈希构造是被允许利用并联布置的两个压缩函数来生成具有很大输出大小 的哈希值的构造。如图3中所示，通过简单地并联布置两个压缩函数f\和f2来构造级联哈 希构造。然而通过布置这样的两个具有b位输出的压缩函数来执行2b位的输出的哈希函 数的安全特性未达到输出大小为2b位的哈希函数的希望水平。已知哈希函数具有与输出 大小为b位的哈希函数近似相等的安全特性。例如在A. Joux的〃 Multicollisions initerated hash functions, application to cascaded constructions" (JALProceedings of Crypto' 04 (M. Franklin, ed.)，no.3152in LNCS, p.306—316，Springer-Verlag, 2004) 中描述了这一点。接着下文将参照图4描述根据本发明一个示例实施例的具有增强安全特性的压 缩部(压缩函数)的构造。图4图示了压缩函数单元50，该单元是具有a位输入和2b位输 出的压缩部。图4中所示压缩函数单元50包括压缩函数f 1和f2 (具有a+b位输入和b位 输出的两个独立数据压缩部)以及加扰函数F (作为具有2b位输入/输出的数据加扰部)。 换而言之，函数单元50包括一个加扰函数F以及两个压缩函数Π和f2的序列。压缩函数单元50接收a位数据[X]和2b位数据[Y]作为输入、也就是共计2b+a 位的输入。在输入中，2b位数据[Y]穿过具有2b位输入/输出的加扰函数F并且被加扰。 接着，来自加扰函数F的2b位输出被分割成b位数据块，并且b位数据块之一和作为压缩 函数单元50的另一输入的a-位数据X由单元中的压缩函数f 1处理。另一 b位数据块和 a位数据X同时由单元中的压缩函数f2处理。最终，通过组合f 1和f2的输出来生成的2b 位是压缩函数50的输出。注意加扰函数F是用于对接收的2b位数据进行加扰并且输出2b 位数据的函数并且是与两个压缩函数Π和f2不同的压缩函数。图5图示了哈希函数构造示例，在该示例中连接图4中所示压缩函数单元50作为 用于域扩展的MD构造从而允许处理具有很长位长度的输入。图5中所示数据转换器包括 由MD构造构成的数据转换部。图5中所示构造是一种由包括η个参照图4描述的压缩函 数单元50的数据转换部构成的构造。换而言之，数据转换器是作为由η个如下压缩函数单 元50构成的哈希函数执行部的数据转换器，该压缩函数单元包括具有2b位输入/输出的 一个加扰函数F以及具有a+b位输入和b位输出的两个压缩函数fl和f2的序列。在图5中所示哈希函数中，压缩函数单元50-0至50-(n-l)用作η级的序列，并且 从最后一级中的压缩函数单元50-(η-1)生成沘位哈希值(H1IH2)15第一级中的压缩函数单元50-0接收位输入M0至Mlri中的第一 a位输入M0以及两 个b位初始值IV1和IV2,并且压缩函数Π和f2分别生成b位输出、也就是共计2b位的输 出。后继级中的压缩函数单元接收从前级中的压缩函数单元中的压缩函数fl和f2施加的 2b位以及作为M0至Mlri中的每个的组成位的a位以生成2b位的输出。在以后级中的压缩 函数单元中重复地执行相同处理，并且最后一级中的压缩函数单元接收从前级中的压缩函 数单元施加的2b位的输出和来自Mlri的a位以及填充数据以生成b位输出H1和H2、也就是 具有共计沘位的哈希值(H1IH2)15如果构成压缩函数单元50的压缩函数f 1和f2以及加扰函数F满足所谓随机启 示(oracle)的性质，则表明这种构造具有充分的安全特性。随机启示是一种在向其施加输 入时在其中生成随机数并且在向其施加以前已经施加过的输入时再次生成以往生成的随 机数的函数。在实践中，通过设计一种用于通过判决程序而无需与随机启示的行为近似的 随机数生成来计算输出的函数并且将函数转置成设计的函数来实现该构造。该构造允许在 压缩函数中使用具有容易评估的安全特性和轻负荷的处理的部分；因此可实现一种容易设 计并且具有高效率的哈希函数。在示例实施例中，在由多个回合(round)构成的压缩处理回合中至少按照固定间 隔执行加扰处理，因而实现一种生成具有增强抗分析性和高安全特性的哈希值的数据转换器。另外作为图5中所示构造的修改示例，如图6中所示，也在使用压缩函数单元 55 (其中改变加扰函数F以及压缩函数f 1和f2的顺序)的情况下允许使用该构造作为具 有相同效果的哈希函数。另外作为图5和图6中所示构造的修改示例，甚至允许使用通过从图6中所示构 造中去除最后一级中的加扰函数F来形成的构造作为在安全特性上具有相同效果的哈希 函数。由于通过重新定义图5中所示构造中作为IV1和IV2的第一加扰函数的输出来获得 这一构造，所以得到相同效果。因此允许用具有更小b位输出的压缩函数以及加扰函数F来构造具有2b位输出 和高安全特性的哈希函数而不是仅构造用于2b位输出的压缩函数。另夕卜，在图5、图6和图7的构造中，压缩函数单元中的各压缩函数fl和f2的输出 位数为b位，并且中间值、也就是内部压缩函数fl和f2中的链接变量彼此相等。然而并不一定让内部压缩函数Π和f2的链接变量(CV)的位大小彼此相等。例 如通过设置内部压缩函数fl和内部压缩函数f2以分别生成b位链接变量(CV)和c位链 接变量(CV)，总的链接变量(CV)可以具有b+c位。甚至在这样的构造中，通过更小函数的 构造可实现压缩函数单元，因而具有确认安全特性的针对小的位大小的压缩函数适用作为 内部压缩函数。[3.提高新颖域扩展方法的处理效率的方法]接着将参照图8描述使参照图5和图6描述的域扩展方法的处理效率提高的哈希 函数的构造示例。图8是哈希函数构造示例，在该示例中每两个压缩函数处理插入加扰函 数F。压缩函数单元60由加扰函数F、两个内部压缩函数fl和f3的序列以及两个内部 压缩函数f2和f4的序列构成。压缩函数单元60中包括的四个内部压缩函数是不同和独 立的压缩函数。换而言之，夹入于两个加扰函数F之间的区域中包括的四个压缩函数是独 立的压缩函数。第一级中的压缩函数单元60接收两个b位初始值IV1和IV2,并且加扰函数F对 接收的2b位数据进行加扰以向各压缩函数fl和f2施加b位。压缩函数fl和f2接收位 输入M0至Mlri中的第一 a位输入M0和来自加扰函数FWb位的输出以生成b位输出，然后 分别向后继序列中的压缩函数f3和f4施加b位输出。压缩函数f3和f4接收位输入Mtl至Mlri中的a位输入M1以及分别来自前级序列 中的压缩函数f 1和f2的b位输出以生成b位输出，然后向后继级中的压缩函数单元的加 扰函数施加b位输出。后继级中的压缩函数单元接收从前级中的压缩函数单元的压缩函数施加的2b位 和作为M0至Mlri的组成位的加位以生成2b位的输出。在以后级中的压缩函数单元中重复 地执行相同处理，并且最后一级中的压缩函数单元接收从前级中的压缩函数单元施加的2b 位、Mn_2的a位和Mlri的a位以及填充数据并且生成b位输出H1和H2、也就是具有共计2b 位的哈希值(HjH2)0在该构造中，与图5中所示构造相比，减少加扰函数F在处理具有相同长度的消息 时的调用次数，因而提高了处理效率。更具体地，在图5中所示构造中，需要两个加扰函数F和四个压缩函数以处理两个a位消息，而在图8中所示方案中，仅由一个加扰函数F和四 个压缩函数来处理消息，因而允许去除一个加扰函数，由此实现更高的处理效率。设置图8中所示构造以重复地执行加扰函数F和压缩函数的两个序列。可以应用 如下构造，在该构造中进一步减少加扰函数数目并且压缩函数的每三个或者更多序列插入 加扰函数F。在图9中图示了推广哈希函数执行部的构造示例，在该示例中每k个压缩函数 插入加扰函数F。在图9中所示构造中，压缩函数单元70包括具有2b位输入/输出的一个 加扰函数F和各包括具有a+b位输入和b位输出的两个压缩函数的k个序列。第一级中的压缩函数单元70接收两个b位初始值IV1和IV2,并且加扰函数F对 接收的2b位数据进行加扰以向一个序列中的各压缩函数fl和f2生成b位的输出。压缩 函数fl和f2接收位输入Mtl至Mlri中的第一 a位输入Mtl和来自加扰函数F的b位的输出 以生成b位输出，然后分别向后继序列中的压缩函数f3和f4施加b位输出。压缩函数f3和f4接收位输入Mtl至Mlri中的a位输入M1以及分别来自先级序列 中的压缩函数f 1和f2的b位输出以生成b位输出，然后分别向后继序列中的压缩函数施 加b位输出。重复以下处理k次，在该处理中向后继序列中的各压缩函数施加来自前级序 列中的各压缩函数的输出和构成各位输入Mtl至Mlri的a位并且各压缩函数生成b位输出， 并且向后继压缩函数单元71的加扰函数F施加来自第k个序列中的两个压缩函数的输出。压缩函数单元71的处理与压缩函数单元70的处理相同。然而向压缩函数单元71 施加位输入M0至Mlri中的后一半的位数据和填充数据。压缩函数单元71的最后一个序列 中的两个压缩函数分别生成b位输出H1和H2、也就是具有共计2b位的哈希值(H1IH2)。注意按照在无损于安全特性的范围内根据哈希值的2b位的输出长度来确定的间 隔来插入加扰函数F。例如在b = 256的情况下，值k为8。值k越大，处理效率就提高越
^^ ο图9中所示构造是如下构造，在该构造中，加扰函数F接收初始值并且各自包括两 个压缩函数的序列如图5中所示构造的情况那样跟随加扰函数F，但是可以使用如下压缩 函数单元，在该单元中，参照图6等描述的序列中的两个压缩函数接收初始值并且执行各 自包括两个压缩函数的多个序列，然后最终执行加扰函数F。[4.实现加扰函数F的方法]加扰函数F是用于对输入位进行加扰以生成位数与输入位相同的数据的函数。下 文将参照图10描述用于实现加扰函数的具体构造。图10是其中利用两个压缩函数来实现 加扰函数F的构造。图10(1)中所示加扰函数F80是如下示例，在该示例中利用具有b位输入和a位 输出的两个转换部81和82以及具有a+b位输入和b位输出的两个压缩函数83和84来实 现具有2b位输入/输出的加扰函数F80。供应将向加扰函数F80施加的两个分割的b位数 据块分别作为用于压缩函数83和84的b位输入。另外分别向转换部81和82同时施加两个b位数据块以转换成a位数据，然后供 应a位数据分别作为用于压缩函数83和84的a位输入数据。仅有必要让转换部81和82 进行用于调节位长度的简单处理，并且例如用简单的逻辑运算(比如通过复制位进行扩展 或者M)R)可实现转换部81和82。优选地设置转换部81和82以满足以下条件。具体而言，设置转换部81和82，从而用于加扰函数F80的输入的所有2b位对用于压缩函数83和84的a+b位的输入有影响。 允许通过图10中所示构造来构造加扰函数F，因而加扰函数F可仅由与两个压缩函数对应 的处理来实现。图10 (2)中所示加扰函数F85是其中用于转化部86和87的输入各自具有2b位 的示例。在例如a > b的情况下，用如下函数构造转换部86和87，该函数用于连接两个b 位数据、然后减少位数以通过简单的运算如XOR来生成a位。优选地设置转换部86和87 以满足以下条件。具体而言，设置转换部86和87，从而用于加扰函数F85的输入的所有2b 位对用于压缩函数88和89的a+b位的输入有影响。在该构造中，加扰函数F也可仅由与 两个压缩函数对应的处理来实现。允许使用图10中所示加扰函数F的构造作为参照图5至图9的哈希函数的构造 中的加扰函数F。当使用这样的构造时，通过重用最初为图5至图9中所示压缩函数单元提 供的压缩函数可实现加扰函数F。共享这样的部件在硬件实施时有效减少门规模，并且允许 器件尺寸减少和成本减少。[5.域扩展方法的推广]参照图5至图9描述的具有MD构造的哈希函数具有向包括两个压缩函数的序列 施加来自一个加扰函数F的输出这样的构造或者向一个加扰函数F施加来自包括两个压缩 函数的序列的输出这样的构造。换而言之，设置哈希函数以使用包括两个压缩函数的序列。序列中的压缩函数数目并不限于两个，并且可以使用其中在序列中包括三个或者 更多压缩函数的构造。在图11中图示了在序列中有m个压缩函数的哈希函数的推广构造 示例，其中m为2或者更大的整数。图11中的构造基于图9中所示构造并且在序列中包括m个压缩函数而不是两个 压缩函数。压缩函数单元90包括具有mb位输入/输出的加扰函数F和各自包括m个压缩 函数的多个序列。第一序列中的m个压缩函数Π至fm接收来自F函数的mb位的位数据 中的b位和位输入M0至Mlri中的第一 a位输入Mtl以生成b位的输出并且分别向后继序列 中的压缩函数施加b位的输出。第k个序列中的m个压缩函数接收分别来自前级序列中的 压缩函数的输出和位输入M0至Mlri中的a位以生成b位的输出。在第k个序列中的压缩函 数的处理之后，向后继压缩函数单元的加扰函数F施加来自压缩函数单元90的最后一个序 列中的压缩函数的mb位的输出。生成来自最后一级中的压缩函数单元91的最后一个序列中的m个压缩函数的b 位的输出氏至礼，即共计2mb位，作为哈希值(HjH2I- IHJo获得的哈希值H”H2、…、Hm 具有最多mb位。通过该技术容易实现具有更长长度的输出的哈希函数。[6.加扰函数F的构造推广]接着下文将描述加扰函数F的推广构造。上文参照图10描述了加扰函数F的具 体构造。参照图10描述的加扰函数F具有使用包括两个压缩函数的序列的构造。在图12中图示了通过推广参照图10描述的加扰函数F来形成的具有mb位输入/ 输出的加扰函数F的构造示例。图12中所示加扰函数FlOO由如下序列构成，该序列包括 具有c位输入和b位输出的m个压缩函数f 1至fm以及分别布置于压缩函数f 1至fm前面 的m个转换部。在图12中所示示例中，m种不同和独立的压缩函数fl至fm各自具有c位的输入大小。向各转换部暂时施加所有mb位，从而对压缩函数Π至fm施加所有输入位的影响， 并且减少输入大小以便对应于各压缩函数的输入大小。在转换部中，例如通过异或O(OR) 或者位大小扩展处理根据mb位输入生成c位输出。转换部必需的条件是作为用于加扰函数FlOO的输入位的所有mb位对c位输出中 的任何位施加影响。该条件可通过简单的操作实现。例如在C = Hlb的情况下，各转换部可 以不变地连接输入并且生成连接的输入。[7.不同压缩函数的使用]在上文描述中，在包括分割成多个序列的多个压缩函数fl、f2、…、fm的压缩函数 单元中，压缩函数单元中的压缩函数fl至fm具有不同构造。这一构造客观地表明最高安 全特性，并且即使使用单个压缩函数，仍然没有立即损害安全特性。在一些情况下，其中重 复使用单个压缩函数的构造具有实施上的优点；因此作为一个不同实施例，可以使用其中 所有压缩函数相同的构造。类似地，可以应用其中重复地使用较少种类而不是相同种类的 压缩函数的构造。[8.实现压缩函数的内部处理的高效方法]下文将描述为上述压缩函数单元提供的压缩函数fi的具体构造示例。在图13中 图示了压缩函数f的内部构造示例。图13是如下压缩函数fl的构造示例，允许使用该压 缩函数作为为参照图5至图12描述的压缩函数单元提供的压缩函数fi并且也作为加扰函 数F的组成要素。如图13中所示，压缩单元120包括消息调度部(MS部)121和链接变量(CV)处理 部122。在向压缩函数120施加的a+b位中，向消息调度部(MS部)121施加作为[X]的a 位，而向链接变量(CV)处理部122施加作为[Y]的其余b位。消息调度部(MS部)121基于a位输入通过消息调度处理来生成c位输出并且向链 接变量(CV)处理部122施加C位输出。链接变量(CV)处理部122接收用于压缩函数120 的b位的输入和从消息调度部(MS部)121施加的c位的输入，也就是b+c位，以生成b位 输出[Z]作为从压缩函数120的输出。图14图示了如下构造示例，在该示例中，为上文参照图5描述的具有MD构造的哈 希函数提供图13中所示压缩函数、也就是由消息调度部(MS部)和链接变量(CV)处理部 构成的压缩函数。图14中所示压缩函数单元130如上文参照图5描述的情况那样由加扰函数F以及 两个压缩函数Π和f2的序列构成。各压缩函数Π和f2具有参照图13描述的构造。换 而言之，各压缩函数Π和f2是由消息调度部(MS部)和链接变量(CV)处理部构成的压缩 函数。在图14中所示示例中，分别由MSl和MS2代表两种压缩函数fl和f2中的消息调 度部(MS部)，而分别由CVl和CV2代表链接变量(CV)处理部。通过该构造可实现哈希函 数。下文将描述一种实现进一步提高处理效率的构造。在图14中所示各压缩函数单元130-0至130-(η-l)中，向两个压缩函数中的消息 调度部MSl和MS2同时施加消息Mi。因此，当相互叠加布置的两个压缩函数共同地使用消 息调度部时，允许减少处理。图15图示了哈希函数的构造示例，在该示例中共同地使用消息调度部。提供了如下压缩函数142，在该压缩函数中，链接变量(CV)处理部CVl和CV2共同地使用一个消息调 度部(MS部)141而不是相互叠加布置并且包括在各压缩函数单元130-0至130-(η-l)中 的两个压缩函数中的消息调度部。当应用包括一个消息调度部(MS部)141的压缩函数142 的构造时，仅有必要在一个压缩函数单元140中让消息调度部(MS部)执行逻辑运算仅一 次，并且允许减少逻辑运算的必需次数。例如实现硬件配置尺寸的减少和处理步骤的简化。参照图15描述的其中多个压缩函数共同地使用消息调度部的构造适用于上述多 个哈希构造。换而言之，该构造适用于参照图5至图12描述的包括多个压缩函数的序列和 在加扰函数F中的压缩函数的压缩函数单元。[9.扩展输入消息长度的方法]接着将研究一种扩展压缩函数中的输入消息长度的方法。图16中所示压缩函数 150如参照图13描述的压缩函数120的情况那样由消息调度部(MS部)151和链接变量 (CV)处理部152构成。在上述图13中所示的压缩函数120中，用于消息调度部(MS)部121 的消息输入具有a位。另一方面，图16中所示压缩函数150包括响应于加位输入的消息 调度部151。一般而言，响应于a位输入的函数和响应于加位输入的函数互不相同，并且有必 要基于不同安全评估标准来评估它们。因此如果有可能则希望通过组合已经评估其安全特 性和性能的响应于a位输入的函数来构造响应于加位输入的消息调度部。另外，通过这样 做来允许再使用响应于a位输入的另一现有函数。后文将描述函数的具体构造示例，而现 在将描述一种利用响应于a位输入的函数来构造响应于加位输入或者更多位输入的压缩 函数的方法。图17图示了具有如下构造的压缩函数160的构造示例，在该构造中，消息调度部 分割成两个部分。消息输入(即用于压缩函数160的加位数据)分割成两个a位数据块， 然后消息调度部161和162分别进行根据a位数据块生成c位输出的处理。向一个链接变 量(CV)处理部163供应来自两个消息调度部161和162的c位输出。链接变量(CV)处理部163接收来自两个消息调度部161和162的c位输出和用 于压缩函数160的b位输入并且生成b位输出[Z]作为压缩函数的输出。该构造的一个优 点在于允许构造如下压缩函数，该压缩函数利用响应于长度比加短的a位输入的函数(消 息调度函数)来实现加位消息输入。图18中所示压缩函数170是具有如下构造的压缩函数170的构造示例，在该构造 中，消息调度部如图17中所示压缩函数160的情况那样分割成两个部分。压缩函数170包 括异或运算O(OR)部174。消息输入(即用于压缩函数170的加位数据)分割成两个a位数据块，然后消息 调度部171和172分别进行根据a位数据块生成c位输出的处理。异或运算O(OR)部174 进行在来自两个消息调度部171和172的c位输出之间的异或运算，然后向一个链接变量 (CV)处理部173施加c位输出。压缩函数170具有如下构造，在该构造中，异或运算部174暂时处理来自两个消息 调度部的输出，然后向链接变量(CV)处理部173施加输出。该构造的优点在于，由于没有 增加链接变量(CV)处理部173接收的消息的大小，所以允许简化链接变量(CV)处理部173 的内部构造。注意异或运算可以用模加法处理代替。
图19图示了通过推广图17中所示压缩函数160的构造来设置成响应于na位输入 的压缩函数210的构造示例。向压缩函数210施加的na位消息分割成η个a位消息，并且 消息调度部(MS部)211-1至211-n分别独立处理a位消息，而且消息调度部(MS部)211-1 至211-n分别生成c位输出。向链接变量(CV)处理部212施加来自消息调度部(MS部)211-1至211_n的c位 输出。链接变量(CV)处理部212接收从η个消息调度部(MS部)211-1至211_n施加的nc 位和用于压缩函数210的b位输入并且生成b位输出[Z]作为压缩函数的输出。这一构造也具有与上文参照图17描述的优点相同的优点。换而言之，允许构造如 下压缩函数，该函数利用响应于长度比na位短的a位输入的函数(消息调度部)来实现na 位消息输入。图20图示了通过推广图18中所示压缩函数170的构造来设置成响应于na位输 入的压缩函数220的构造示例。向压缩函数220施加的na位消息分割成η个a位消息，并 且响应于a位输入的消息调度部(MS部)221-1至221_n分别独立处理a位消息，并且消息 调度部(MS部)221-1至221-n分别生成c位输出。异或运算部O(OR) 223-1至223_n分别进行在来自消息调度部(MS部)221-1至 221-n的c位输出之间的异或运算，然后向一个链接变量(CV)处理部222施加c位输出。 链接变量(CV)处理部222接收来自异或运算部O(OR) 223-n的c位输出和作为用于压缩函 数220的输入的b位以生成b位输出[Z]作为压缩函数的输出。在这一构造中也允许构造 如下压缩函数，该压缩函数利用响应于长度比na位短的a位输入的函数(消息调度部)来 实现na位消息输入。注意可以使用通过将异或运算部替换为模加法处理部而形成的构造。因此，根据本发明示例实施例的数据转换器包括向其同时施加消息数据的分割数 据块的多个处理序列并且被配置成利用多个压缩函数执行部(f)来执行数据转换处理。多个压缩函数执行部(f)中的各压缩函数执行部被配置成进行利用消息调度部 (MS)的处理，其中消息调度部(MS)接收消息数据的分割数据块以对数据块进行消息调度 处理，和利用链接变量(CV)处理部的处理，其中链接变量(CV)处理部接收来自消息调度部 (MS部)的输出和作为来自前级处理部的输出的中间值(链接变量)以通过对接收的数据 进行压缩来生成位数与中间值的位数相同的输出数据。在多个处理序列中分别进行并行处理的多个压缩函数执行部共同地使用消息调 度部(MS部)和链接变量(CV)处理部中的一个或者两个并且进行利用单个消息调度部或 者单个链接变量处理部的处理。这样的构造实现硬件配置尺寸的减少和处理步骤的简化。[10.在CV处理部和MS部中使用重复的转置来实现哈希函数的方法]如上文所述，利用消息调度部(MS部)和链接变量(CV)处理部作为组成要素可实 现压缩函数。下文将描述消息调度部(MS部)和链接变量(CV)处理部的具体构造示例。一般已知基于转置函数的消息调度部(MS部)或者链接变量(CV)处理部。例如 已知为哈希函数的SHA-I或者Whirlpool具有基于转置函数的构造。向消息调度部(MS部)或者链接变量(CV)处理部施加的转置函数优选为具有高 加扰能力的转置函数。下文将描述通过重复地使用相对简单的转置函数来增强加扰能力的转置函数的 构造示例。在下文描述中，在转置函数中重复的相对简单的转置称为“内部转置”，而由此实现的转置称为“总转置”。注意转置函数是用于基于输入值生成输出值、使得输入大小和输出大小彼此相同 并且一个输入值对应于一个输出值的函数。此外，转置函数由于它的性质而具有反函数。在总转置中，可以从外部向两个内部转置处理之间的中间数据添加数据，或者可 以向函数的外部施加中间数据。在压缩函数中，利用中间数据，可以向除了总转置的原输入 部分和原输出部分之外的部分施加数据的输入或者附加数据的输出。向除了原输入部分之 外的部分施加的数据称为附加输入，而向除了原输出之外的部分施加的中间数据称为中间 输出。图21中所示转置函数(转置部)310是具有附加输入311的转置函数的示例。另 外，图22中所示转置函数(转置部)320是具有中间输出321的转置函数的示例。图21和图22中所示转置函数基于响应于a位输入/输出的总转置。在转置函数 中依次施加内部转置1至k。图21中所示转置函数310具有如下构造，在该构造中对附加 输入311与中间数据进行异或，该中间数据是将向后继内部转置部或者外部施加的内部转 置的输出值。在图22中所示转置函数320中，向外部施加作为内部转置的输出值的中间数 据作为中间输出321。下文为了区别这种类型的总转置与一般的总转置，图21中所示类型 的转置函数称为具有附加输入的转置函数，而图22中所示类型的转置函数称为具有中间 输出的转置函数。注意具有附加输入的转置函数继承转置的以下固有性质。*当附加数据固定时，一个输入对应于一个输出。另外，具有中间输出的转置函数具有从转置函数导出的以下性质。* 一个输入对应于一个中间输出。形成哈希函数的压缩函数如上文参照图13至图20所述由消息调度部(MS)部和 链接变量(CV)处理部构成。已经已知具有附加输入的转置函数用于链接变量(CV)处理部 而具有中间输出的转置函数用于消息调度部(MS部)，并且它们相互连接以构造压缩函数 (Whirlpool)。图23图示了使用现有转置函数的压缩函数330的构造示例。图23中所示压缩函 数330具有如下构造，在该构造中提供消息调度部(MS部)331作为具有中间输出的a位转 置函数并且中间输出连接到具有用于链接变量(CV)处理部332的附加输入的a位转置函 数的附加输入。在图23中所示构造中，为了简化描述，a位转置函数使用于消息调度部(MS 部)331和链接变量(CV)处理部332两者之中；然而消息调度部(MS部)331和链接变量 (CV)处理部332的转置大小并不一定彼此相等。在消息调度部(MS部)331和链接变量 (CV)处理部332的长度互不相同的情况下，可以通过适当地进行扩展和压缩运算来调节长 度。另外，不同于图23中所示情况，所有中间输出并不一定连接于消息调度部(MS部)331 与链接变量(CV)处理部332之间，并且可以考虑安全特性或者处理效率来执行比如适当地 减少中间输出的处理以选择连接于消息调度部(MS部)331与链接变量(CV)处理部332之 间的中间数据。[11.扩展MS部的大小的方法]图M图示了压缩函数的构造示例，在该示例中对要向压缩函数施加的数据大小进行扩展。图M中所示压缩函数340是其中将输入位长度扩展成3a位的压缩函数。图M 中所示压缩函数340具有与上文参照图18描述的构造相同的构造并且包括两个消息调度 部(MS部)341和342以及接收来自两个消息调度部(MS部)341和342的输出的异或运算 结果的一个链接变量(CV)处理部343。两个消息调度部(MS部)341和342各由具有中间输出的转置函数构成。一个链 接变量(CV)处理部343由具有附加输入的转置函数构成。图M中所示转置函数340具有如下构造，在该构造中，2a位输入X分割成a位块， 并且分别向两个消息调度部(MS部)341和342施加a位块，而且向一个链接变量(CV)处 理部343施加来自两个消息调度部(MS部)341和342的中间输出。当以这样的方式使用 具有附加输入的转置函数和具有中间输出的转置函数时，允许容易地增加输入长度。另外，在图M中所示转置函数340的构造中，不允许用作消息调度部(MS部)的 两个转置函数彼此相同，因为在转置函数彼此相同的情况下，当向两个转置函数施加相同a 位数据块时，对应的中间输出彼此相同，并且抵消了异或运算O(OR)的结果。因此有必要为 消息调度部(MS)准备不同的转置函数。通过使用内部转置的不同构造可实现这一点。允许通过推广图M中所示压缩函数的构造来将输入X的长度扩展为3a位或者更 多。例如通过添加消息调度部(MS部)可实现这一点。在图M中所示构造中使用一种减少吞吐量以实现加速的方法。在例如如参照图 4、图5等描述的构成哈希函数的具有多级构造的压缩函数中，要向压缩函数施加的值是作 为数据[X]的消息和作为数据Y的中间值、也就是链接变量(CV)。这时，用于消息处理的转置的重复次数并不一定等于用于链接变量(CV)序列的 转置的重复次数。例如下文将考虑在无损于安全特性的范围内将用于消息的转置的重复次 数减半的情况。图25图示了压缩函数350，在该函数中如图M中所示情况那样将输入位长度扩 展为3a位。用于压缩函数350的加位输入X分割成a位块，并且分别向两个消息调度部 (MS部)351和352施加a位块，而且向一个链接变量(CV)处理部353施加两个消息调度部 (MS部)351和352的中间输出。图25中所示两个消息调度部(MS部)351和352中的各消息调度部中的内部转置 的重复次数设置成等于链接变量(CV)处理部353中的内部转置的重复次数的一半。在消息调度部(MS部)351中，去除偶数编号的转置，而在消息调度部(MS部)352 中，去除奇数编号的转置；因此将两个消息调度部(MS部)351和352中的各消息调度部中 的内部转置的重复次数减半。通过这种构造允许将消息处理必需的运算减半。在图25中所示压缩函数350中，与图M中所示压缩函数340的构造相比较，处理 被减少。因此预期对软件处理进行改进。当在消息调度部(MS部)351和352中交替地去 除函数时，作为一个优点，允许将在硬件实施时同时被允许进行的转置次数设置成两次以 实现电路规模小的处理、也就是说，可实现硬件尺寸的减少。另外，如图25中所示情况那样，图沈中所示压缩函数360是其中输入位长度扩展 成3a位的压缩函数360。用于压缩函数360的加位输入X分割成a位块，并且分别向两个 消息调度部(MS部)361和362施加a位块，而且向一个链接变量(CV)处理部363施加两 个消息调度部(MS部)361和362的中间输出。
20CN 102138170 A
说明书
17/30 页图沈中所示压缩函数360中的链接变量(CV)处理部363具有如下构造，在该构 造中，在图25中所示压缩函数350中的链接变量(CV)处理部353前面添加一个内部转置 部364，并且内部转置的重复次数加1。在图沈中所示压缩函数360中，在用于链接变量(CV)处理部363的总转置前面 添加一个内部转置。根据这一改变，压缩函数360具有如下构造，在该构造中，上消息调度 部(MS部)361的输入值与链接变量(CV)处理部363的输入值进行异或。作为这种构造的一个特性，当关注消息调度部(MS部)之一时，链接变量(CV)处 理部363的每两个转置函数施加向链接变量(CV)处理部363施加的中间数据而无例外。 通过这种构造，对链接变量(CV)处理部363的序列同等地施加相互叠加布置的消息调度部 (MS部)361和362的影响以便实现平衡的加扰。因而有安全评估更容易的优点。[12.扩展CV处理部的大小的方法]图27中所示压缩函数370示出了如下构造，其中上文参照图15描述的形成序列 的两个压缩函数共同地使用消息调度部。当图15中呈现的域扩展方法应用于b = a的情 况时扩展了链接变量(CV)处理部的大小。在图27中所示压缩函数370中，向消息调度部(MS部)371施加作为消息[X]的 组成位的a位的输入，并且分别向链接变量(CV)处理部372和373施加作为两个链接变量 (CV)(中间值)的a位的输入。消息调度部(MS部)371由具有中间输出的转置函数构成。两个链接变量(CV)处 理部372和373各由具有附加输入的转置函数构成。设置消息调度部(MS部)371的中间 输出作为两个链接变量(CV)处理部372和373的附加输入。在两个链接变量(CV)处理部 372和373中的各处理部中对消息调度部(MS部)371的中间输出与输入或者中间值进行异 或以向内部转置部施加。可替换地，中间输入用来生成输出值。[13.扩展CV处理部和MS部的大小的方法]图28中所示压缩函数380是图27中所示压缩函数370的修改示例并且是如下压 缩函数的构造示例，其中通过与上文参照图M描述的压缩函数340的技术相同的技术来扩 展要向压缩函数施加的数据大小。图观中所示压缩函数380是其中输入位长度扩展成3a 位的压缩函数。图28中所示压缩函数380包括两个消息调度部(MS部)381和382以及接 收两个消息调度部(MS部)381和382的输出的异或O(OR)运算结果的一个链接变量(CV) 处理部383和384。两个消息调度部(MS部)381和382各由具有中间输出的转置函数构成。两个链 接变量(CV)处理部383和384各由具有附加输入的转置函数构成。提供消息调度部(MS 部)381的中间输出作为链接变量(CV)处理部383的附加输入。提供消息调度部(MS)部 382的中间输出作为链接变量(CV)处理部384的附加输入。两个链接变量(CV)处理部383 和384使用附加输入以与输入或者中间值进行异或、然后向内部转置部施加或者生成输出 值。[14.为域扩展方法构造加扰函数F的方法]加扰函数F可以由具有中间输出的转置函数与具有附加输入的转置函数构成。图 四是由具有中间输出的两个转置函数与具有附加输入的两个转置函数的组合构成的加扰 函数F390的构造示例。
加扰函数F390包括两个消息调度部(MS部)391和392以及接收来自两个消息调 度部(MS部)391和392的输出的异或运算O(OR)结果的一个链接变量(CV)处理部393和 394。两个消息调度部(MS部)391和392各由具有中间输出的转置函数构成。两个链 接变量(CV)处理部393和394各由具有附加输入的转置函数构成。提供消息调度部(MS部)391的中间输出作为链接变量(CV)处理部393的附加输 入。提供消息调度部(MS部)392的中间输出作为链接变量(CV)处理部394的附加输入。 两个链接变量(CV)处理部393和394使用附加输入以与输入或者中间值进行异或，然后向 内部转置部施加或者生成输出值。加扰函数F390接收加位作为输入[Y]并且生成加位输出[Z]。注意本发明的数 据转换器中的转置可以具有如下构造，在该构造中如上述图25和图沈中的构造的情况那 样去除一些部分。[15.实现具有高扩散能力的转置处理的方法]通过如上文所述重复地施加内部转置作为相对简单的转置函数可实现向消息调 度部(MS部)或者链接变量(CV)处理部施加的转置函数。当重复地应用这样的相对简单 的转置函数时，允许构造具有增强加扰能力的转置函数。下文将参照图30描述适用作为内部转置的转置函数的具体构造示例。图30是用 于构造具有高加扰能力的重复型转置函数、作为在执行总转置的转置函数中使用的内部转 置的转置函数的构造示例。通过重复和依次地施加内部转置来构成总转置。图30中的内 部转置部(转置函数)410具有其中进行256位输入/输出转置的构造。向内部转置部(转置函数)410施加的256位数据由32字节数据代表。各字节对 应于附图中所示一条输入数据线。首先将数据分割成4字节(32位)数据块、也就是从左侧起的八组(Gl至G8)。在 相应的对应非线性转换部411中对从左侧起的奇数编号组(G1、G3、G5和G7)中包括的4字 节的数据进行非线性转换处理。当从非线性转换部411生成四组(G1、G3、G5和G7)中的各组中的4字节(32位) 数据时，异或O(OR)运算部412执行4字节(32位)数据与其右侧上的一组中的4字节数 据的异或运算以更新四个偶数编号组(G2、G4、G6*G8)中的各组中的4字节(32位)数据。换而言之，通过以下处理更新四个偶数编号组(G2、G4、G6和G8)中的各组中的4 字节(32位)数据执行在对组(Gl)中的4字节数据的非线性转换结果的数据与组(G2)中的输入数 据之间的异或运算，执行在对组(G3)中的4字节数据的非线性转换结果的数据与组(G4)中的输入数 据之间的异或运算，执行在对组(G5)中的4字节数据的非线性转换结果的数据与组(G6)中的输入数 据之间的异或运算，并且执行在对组(G7)中的4字节数据的非线性转换结果的数据与组(G8)中的输入数 据之间的异或运算。
接着在互换部413中进行对各1字节数据的互换处理。移动包括从非线性转换部 411生成的数据的四组(G1、G3、G5和G7)，使得最左组移向最右组的位置，并且其它组分别 移向其紧接左侧上的组的位置。换而言之，用以下方式执行互换处理以生成数据向输出组(GoirtS)的位置施加组(Gl)，向输出组(Gout2)的位置施加组(G3)，向输出组(Gout4)的位置施加组(G5)，并且向输出组(Goute)的位置施加组(G7)，另一方面，异或O(OR)运算部412进行如下互换处理，该处理将通过执行异或运算 来更新的四个偶数编号组(G2、G4、G6和G8)中的各组中的4字节(32位)数据分割成1字 节数据块并且分别将1字节数据块移向不同组。对组(G》中的4字节数据进行以下互换处理。将组(6 的4字节数据分割成来 自第一 1字节数据块的由A、B、C和D代表的1字节数据块。用以下方式执行互换处理以生成数据生成组(G2)中的第一 1字节数据块A作为输出组(Goutl)中的第一 1字节数据 块，生成组(G2)中的第二 1字节数据块B作为输出组(Gout3)中的第二 1字节数据 块，生成组(G2)中的第三1字节数据块C作为输出组(Gout5)中的第三1字节数据 块，并且生成组(G2)中的第四1字节数据块D作为输出组(Gout7)中的第四1字节数据 块，对组(G4)中的4字节数据进行以下互换处理。组(G4)的4字节数据分割成来自第一 1字节数据块的由E、F、G和H代表的1字 节数据块。用以下方式执行互换处理以生成数据生成组(G4)中的第一 1字节数据块E作为输出组(Gout3)中的第一 1字节数据 块，生成组(G4)中的第二 1字节数据块F作为输出组(Gout5)中的第二 1字节数据 块，生成组(G4)中的第三1字节数据块G作为输出组(Gout7)中的第三1字节数据 块，并且生成组(G4)中的第四1字节数据块H作为输出组(Goutl)中的第四1字节数据 块，对组(G6)中的4字节数据进行以下互换处理。组(G6)的4字节数据分割成来自第一 1字节数据块的由I、J、K和L代表的1字 节数据块。用以下方式执行互换处理以生成数据生成组(G6)中的第一 1字节数据块I作为输出组(Gout5)中的第一 1字节数据块，生成组(G6)中的第二 1字节数据块J作为输出组(Gout7)中的第二 1字节数据 块，生成组(G6)中的第三1字节数据块K作为输出组(Goutl)中的第三1字节数据 块，并且生成组(G6)中的第四1字节数据块L作为输出组(Gout3)中的第四1字节数据 块。对组(G8)中的4字节数据进行以下互换处理。组(G8)的4字节数据分割成来自第一 1字节数据块的由M、N、0和P代表的1字 节数据块。用以下方式执行互换处理以生成数据生成组(G8)中的第一 1字节数据块M作为输出组(Gout7)中的第一 1字节数据 块，生成组(G8)中的第二 1字节数据块N作为输出组(Goutl)中的第二 1字节数据 块，生成组(G8)中的第三1字节数据块0作为输出组(Gout3)中的第三1字节数据 块，并且生成组(G8)中的第四1字节数据块P作为输出组(Gout5)中的第四1字节数据 块。注意在后继回合中的内部转置部(转置函数)中向非线性转换施加输出组 (GoutK Gout3λ Gout5 禾口 Gout7)。因此，当执行互换输入和输出的互换处理时，保证在各回合中执行对各字节数据 的不同种类的转换处理。如图30中的内部转置部(转置函数)410的输出部中所示，32字节输出分别由xl 至x32代表。例如，图22中所示具有中间输出的转置函数中的中间输出对应于这些输出。 换而言之，参照图23至27描述的压缩函数和加扰函数F的各构造中的消息调度部(MS部) 由具有中间输出的转置函数构成，并且这些输出对应于从消息调度部(MS部)生成的中间 输出。在图21中所示具有附加输入的转置函数中施加中间输出作为附加输入。例如参 照图23至27描述的压缩函数和加扰函数F的各构造中的链接变量(CV)处理部由具有附 加输入的转置函数构成，并且施加来自图30中所示内部转置部(转置函数)410的输出部 的32字节输出xl至x32作为链接变量(CV)处理部的附加输入。注意向如参照图23至图27描述的压缩函数或者加扰函数F的内部提供大量图30 中所示内部转置部(转置函数)410的构造。可以使用由内部转置部(转置函数)生成的 中间数据的所有输出值xl至x32，或者可以使用输出值xl至x32中的仅一些输出值。例如在图30中所示内部转置部(转置函数)410的构造中，可以仅使用来自非线 性转换部411的输出值x5至x8、xl3至xl6、x21至xM和口9至义32作为中间输出。可替 换地，可以仅使用要向后继转置函数中的非线性转换部施加的输出值xl至x4、x9至xl2、 xl7至x20和x25至x28作为中间值。
接着下文将参照图31描述参照图30描述的内部转置部(转置函数)410中的非 线性转换部411的内部构造的示例。允许将非线性转换部411构造作为接收4字节数据并 且生成4字节数据的转置函数。图31中所示非线性转换部411接收4字节数据。图31中所示一条线对应于1字 节数据块。在异或O(OR)运算部421中，接收的数据分别与非线性转换部411中预定的四 个常值(常数)C1、C2、C3和C4进行异或。注意在参照图30描述的内部转置部(转置函 数)410中包括四个非线性转换部411，并且这四个非线性转换部具有不同的常值(常数)。 后文将描述一种设置常值(常数)的处理。接着，小型非线性转换部422对在异或O(OR)运算部421中分别与非线性转换部 411中预定的四个常值(常数)C1、C2、C3和C4异或的数据执行1字节输入/输出非线性 转换处理。向线性转换部423施加小型非线性转换部422的输出，并且对输出进行线性转换 以生成输出。注意这里描述的小型非线性转换部422有时称为S框(S-box)并且可以表示 为用于256条1字节数据的转换表。另外执行线性转换部423作为一种通过利用线性转换 矩阵(M)对输入数据的转换处理来计算输出数据的处理。线性转换矩阵(M)也称为扩散矩 阵并且有时表示为具有GFQ8)个元素的4X4矩阵。在转置函数中希望在施加某些数据对尽可能多的数据的影响之时只要有可能就 防止输入/输出中包括的非零元素总数达到低水平。这对提高抗分析性和消除弱点是有效 的。具体而言，这是一种防范差分攻击或者线性攻击的措施。如参照图23至图27所述，为压缩函数或者加扰函数F提供大量图30中所示内部 转置部(转置函数)410的构造。换而言之，一种将图30中所示内部转置部(转置函数)410 重复多个回合的处理。大量加密算法具有执行如下回合操作的构造，在该操作中将相同转置处理重复多 个回合，并且已知作为一种防范弱点的措施，使用如下所谓DSM(扩散切换机制)是有效的， 在该机制中使用多个不同矩阵如两个矩阵[Ml]和[M2]而不是一个固定矩阵作为应用于每 个回合中的线性转换矩阵[M]。注意例如在本发明申请人的第2007-199156号日本未审查 专利申请公开中描述了一种使用DSM的加密算法。认为DMS克服弱点的效果在哈希函数中也有效。换而言之，当使用多个不同矩阵 而不是一个固定矩阵作为应用于所有回合的线性转换矩阵[M]时，哈希函数更加不可区别 于随机函数，并且也允许增强各种分析处理的难度。图32图示了为了使用多个不同矩阵作为在为压缩函数或者加扰函数F提供的多 个图30中所示内部转置部(转置函数)410的非线性转换部411中使用的线性转换矩阵 [M]而设置的内部转置部的重复回合的构造示例。图32是为压缩函数或者加扰函数F提供的多个图30中所示内部转置部(转置函 数)的两个回合的组合构造的简化图示。内部转置部(转置函数)440具有与图30中所示 内部转置部(转置函数)410相同的构造。内部转置部(转置函数)450表示执行后继内部 转置的一个回合。各输入线对应于4字节数据。如图30中所示内部转置部(转置函数)410的情况那样，内部转置部(转置函 数)440包括非线性转换部441、异或运算O(OR)部442和互换部443。非线性转换部441具有参照图31描述的构造。如参照图31所述，非线性转换部441包括异或运算部、小型非线性转换部和线性 转换部。线性转换部利用线性转换矩阵M来执行线性转换处理。在图32中图示了作为非线性转换部441提供的用于4字节数据的四个非线性转 换处理部，并且各处理部具有参照图31描述的构造。在图32中，在四个非线性转换部的线 性转换部中使用的线性转换矩阵M从左侧起分别由Ml、M2、M3和M4代表。线性转换矩阵 M1、M2、M3禾口 M4互不相同。回合中的内部转置部(转置函数)440和450具有相同构造。换而言之，在两个内 部转置部(转置函数)440和450中，在四个非线性转换部的线性转换部中使用的线性转换 矩阵M从左侧起是Ml、M2、M3和M4。因此，相同矩阵使用于内部转置中的相同位置。根据在图32中所示回合之间连接的线(粗线)理解，在上回合中的内部转置部 (转置函数)440中的非线性转换的输出与在下回合中的转置部(转置函数)450的一个非 线性转换的输出进行异或。例如来自上回合中的内部转置部(转置函数)440的非线性转换部441中的最左 侧上、具有线性转换矩阵Ml的非线性转换部441的输出(附图中的输出A)在异或运算部 452中与来自下回合中的内部转置部(转置函数)450的非线性转换部451中最右侧上的具 有线性转换矩阵M4的非线性转换部451d的输出(附图中的输出B)进行异或。该结果的 输出是附图中所示输出C。来自上回合中的内部转置部(转置函数)440的非线性转换部441的四个非线性 转换部的各输出与来自下回合中的内部转置部(转置函数)450中的非线性转换部451的 四个非线性转换部的输出之一进行异或。进行异或的来自上回合中的非线性转换部441的输出与来自下回合中的非线性 转换部451的输出的组合作为各非线性转换部中的线性转换矩阵[M]的组合示出如下。(I)Ml和M4(非线性转换部441a和45Id)(2)M2和Ml (非线性转换部441b和451a)(3)M3和M2(非线性转换部441c和451b)(4)M4和M3(非线性转换部441d和451c)当使用不同线性转换矩阵来执行线性转换处理的结果相互作用时，可设想一种使 用上述DSM(扩散切换机制)的构造以便增加抗分析性。注意两个矩阵的连接由符号“ I，，代表，并且当选择和使用为了增加分支数目(至 例如3个或者更多)而设置的矩阵作为上述矩阵对(1)至⑷(即Ml |M4、M2|M1、M3|M2和 M4|M3)时，允许进一步增加抗分析性。可替换地，使用如下构造，在该构造中通过对准将其 逆矩阵反转而获得的矩阵来获得的矩阵Ir11 tM^1, ^2"11 tMrW I ^2"1和tMf1113—1的分 支数目为3个或者更多。允许这样的增加分支数目的构造来提高对差分攻击或者线性攻击抗性。因此，为作为重复的回合操作而执行的内部转置部(转置函数)中的非线性转换 部提供的线性转换部优选地具有一种利用DSM构造来使用不同矩阵的构造。另外，优选地 设置要使用的矩阵使得增加包括相互作用的成对矩阵的组合矩阵的分支数目。在参照图32的描述中使用四个矩阵；然而可以用两个矩阵满足用于分支数目的相同条件。例如，如图33中所示，可以使用如下构造，在该构造中，布置矩阵使得M1|M2的 分支数目是3或者更多，或者通过对准将逆矩阵反转而获得的矩阵来获得的矩阵1Γ11 ^2-1 的分支数目是3或者更多。在图33中所示构造中，异或的来自上回合中的非线性转换部441的输出与来自下 回合的非线性转换部451的输出的组合作为各非线性转换部中的线性转换矩阵[M]的组合 示出如下。(I)Ml和M2(非线性转换部461a和47Id)(2)M2和Ml (非线性转换部461b和471a)(3) Ml和M2(非线性转换部461c和471b)(4)M2和Ml (非线性转换部461d和471c)图33中所示构造在实施方面被视为更优选的构造，因为允许减少矩阵所必需的 硬件电路和存储器上的表大小。当使用不同线性转换矩阵来执行线性转换处理的结果相互作用时，可实现一种使 用上述DSM(扩散切换机制)的构造，并且允许增加抗分析性。上文描述了用于实现具有增强加扰能力的总函数的内部转置的构造示例。描述上 述处理示例作为其中使用256位输入的示例；然而这仅为示例并且可以不同地设置数据大 小并且可以提供视数据大小而定的构造。在这种情况下，设置该构造以根据小型非线性转 换部的输入/输出大小和线性转换部的大小来进行处理。[16.生成具有高度独立输出的转置函数的方法]在上述处理示例中，描述为压缩函数或者加扰函数F提供的多个内部转置处理构 造作为如下处理示例，在该示例中使用图30中所示内部转置处理构造并且设置该构造以 重复多次。允许例如通过以上述方式在内部转置处理的非线性转换部中构造线性转换处理 矩阵来增加抗分析性。在一种需要多个总转置函数的构造中，在一些情况下，通过使用独立作用的多个 总转置来增加抗分析性。在这种情况下有一种通过使用总转置中包括的不同内部转置来实 现该构造的方法。下文将描述构造示例。为了实现多个不同总转置处理，一种改变总转置中的内部转置中包括的部分的技 术是有效的。然而在安全评估处理的实施效率或者容易方面，并不一定希望使用大量不同 部分。优选利用尽可能少的部分来实现各种处理。作为一种用于分别对总转置进行不同内部转置处理的构造，例如考虑以下构造。*用随着总转置而不同的常值转置要使用(使用于图31中的异或运算部中)的常值。*S框(图31中的小型非线性转换部422)或者线性转换矩阵(图31中的线性转 换部42 (这些S框或者线性转换矩阵是包括在总转置中的内部转置处理的部分)随着总 转置而不同，并且重复地使用它们以实现总转置。注意常值是向参照图30和图31描述的内部转置部410的非线性转换部411的异 或O(OR)运算部421供应的常数。然而为了随着总转置而彻底改变常值或者改变S框或者矩阵，有必要供应不同数 据或者不同部分构造，因而有必要增加电路或者存储器容量。这样的电路或者存储器容量增加引起比如实施上的缺点和安全再评估的成本增加这样的问题。因此，在本发明中，根据以下构造来将用于总转置的内部转置处理构造设置为互 不相同。(a)在使用多个不同小型非线性运算(S框)(图31中的小型非线性转换部422) 的情况下，随着总转置而改变内部转置的小型非线性运算(S框)。(b)将线性转换部(图31中的线性转换部423)中使用的矩阵设置成由一个矩阵 生成的多个不同矩阵，并且将内部转置的矩阵设置成随着总转置而不同的矩阵。例如通过 转置行或者列由一个矩阵生成多个不同矩阵。(c)在使用多种矩阵作为线性转换部(图31中的线性转换部423)中使用的矩阵 的情况下，随着总转置而对内部转置的矩阵进行转置。(例如在使用上述DSM的情况下，在 不脱离DSM条件的范围内改变。)(d)上述构造(a)至(C)中的两个或者更多构造的组合。允许高效地改变设置成任何上述构造并且重复地执行的内部转置处理中的转置 处理构造。换而言之，允许执行不同转置处理而不增加电路规模或者存储器容量。具体而言，通过上述构造(C)与(b)的组合可高效地实现不同总转置。换而言之， 在利用上述DSM构造在存储器中存储两种或者更多种线性转换矩阵的情况下，转置这些矩 阵的行和列以生成和使用新矩阵作为线性转换矩阵。在这样的构造中，允许基于少量数据 来高效地进行不同线性转换处理。在一种使用DSM并且包括多个不同线性转换矩阵的构造中，在对矩阵的行和列进 行转置的情况下的安全评估是一个问题，但是已知当使用具有预定规则的矩阵如循环矩阵 或者Hadamard(哈达马)矩阵时，使用通过转置行和列来生成的矩阵不影响安全评估。因 此认为安全评估是容易的并且该构造是用于通过简单的改变来生成不同转置函数的有效 手段。[17.生成向转置函数施加的常数的处理]如上文所述，作为一种随着回合改变转置处理构造的技术，每个回合或者每两个 或者更多回合将常数(在图31中的异或运算部421中使用的[C])转置成不同常数的技术 是有效的。然而需要有大存储器容量以维持与大量回合对应的常数。下文将描述如下构造示 例，在该示例中允许由少量常数高效地生成并且在转置函数中使用大量不同常数。首先定义转置函数所需要的常数。这里4个字节统称为1个字。例如图30中所示 内部转置部(转置函数)410包括四个非线性转换部，并且各非线性转换部具有图31中所 示构造。如图31中所示，四个常数用于一个非线性转换部411。各常数用于与1字节输入 数据的异或运算，因而一个常数Cn为1字节数据。一个非线性转换部411使用四个常数， 因此每个非线性转换需要1个字的常数。图30图示的内部转置部(转置函数)410包括四个非线性转换部，因此对于一个 内部转换处理，需要4个字的常数。在通过重复k次该基本转置来构造总转置的情况下，需 要共计4k字的常数。在k个内部转置中，在从输入侧起的第i个内部转置中包括的第j个常值由Cq 代表。因此允许将一次总转置所需的常数表示如下。
( 一次总转置所需的成组常数的示例)第--内部转置= C1,1，C1,2，C1,3，C
第二二内部转置:C2,1，C2,2，C2,3，C;
第三三内部转置=C3,1，C3,2，C3,3，C;
第四内部转置:C4,1，2，3，C,第k-Ι 内部转置=C1^1, Ck-U, Ck^1,3, Cn4第k 内部转置=Cu, Ckj2, Ckj3, Ck,4作为公开常数生成技术的有关技术，例如在第2008-58827号日本未审查专利申 请公开中描述了一种技术。在该有关技术中，作为一种生成64位常数的方法，使用8位变 量中存储的值8次来生成常数，并且通过对该变量中的视为GFQ8)的元素的值进行χ或者 χ—1倍乘以依次地增加数据种类来生成后继常数。注意在定义要使用的有限场GFQn)的不 可约分多项式由多项式f(x)代表时，这里使用的χ是变量χ。下文将描述一种基于通过对用于生成常数的数据的χ倍乘而获得的级数来生成 一些常数并且基于通过X—1倍乘X而获得的级数来生成其余常数的方法作为一种常数生成 处理构造。允许局部地干扰常数之间的简单关系而不增加通过该方法生成常数的工作量。 结果，允许增加常数的随机性。将利用由一个16位值生成与两个字对应的64位的示例来 描述该示例。将与在上述有关技术(第2008-58827号日本未审查专利申请公开)中公开的常 数生成处理相比较来描述根据本发明的常数生成处理。首先下文将描述有关技术中的常数生成步骤。有关技术中的常数生成步骤如下[1]在16位变量S中存储初始值。[2]对i = 1···1 进行以下处理。(2. DCia = (S XOR 掩码》< < < Rot11 (S XOR 掩码 2) < < < Rot2Ci,2 = (S XOR 掩码 3) <<< Rot3I (S XOR 掩码 4) <<< Rot4Ci,3 = (S XOR 掩码 5) <<< Rot51 (S XOR 掩码 6) <<< Rot6Ci,4 = (S XOR 掩码 7) <<< Rot71 (S XOR 掩码 8) <<< Rot8(2. 2) S — S · χ注意掩码η和Rotn是单独确定的常数。这里符号“ I ”代表位的连接。(AX0R B)代 表A与B的异或运算O(OR)处理。在一些情况下，以这样的方式生成的四个常数(Ciil至Ci,4)看似随机数；然而仅通 过掩码运算和旋转移位运算来改变常数，因而常数具有如下特性即使S为任何值，常数仍 然一致地保持由具体线性运算代表的关系。通过作为示例的块加密清楚的是仅通过线性转 换来增加随机性经常是不够的，而且希望让常数具有尽可能非线性的性质。接着下文将描述一种根据本发明通过在常数之间引入非线性关系来生成常数而 不增加实施成本和降低性能的技术。[1]在各16位变量S和T中存储初始值[2]对i = 1···1 进行以下处理。(2. DCia = (S XOR 掩码》<<< Rot11 (S XOR 掩码 2) <<< Rot2
Ci,2 = (S XOR 掩码 3) <<< Rot3I (S XOR 掩码 4) <<< Rot4Ci,3 = (T XOR 掩码 5) <<< Rot51 (T XOR 掩码 6) <<< Rot6Ci,4 = (T XOR 掩码 7) <<< Rot71 (T XOR 掩码 8) <<< Rot8(2. 2)S 一 S · χ, T 一 T · χ-1当根据上述处理利用16位变量S和T来生成四个常数(Ciil至Ci,4)时，在各内部 转置中包括的四个常数的一半属于X倍乘级数，而另一半属于X—1倍乘级数。通过这样的构造，没有保持在由S生成的常数与由T构成的常数之间的固定线性 关系，并且获得提高独立性的效果。当一般地描述上述常数生成处理时，常数生成处理是一种用具有不同指数如Xa和 Xb的值来更新初始值S和T的处理。当利用这样的变量S和T来生成多个常数时，生成的 常数的一半属于Xa倍乘级数，而另一半属于Xb倍乘级数。注意除了基于S和T的两个级数之外，当可接受增加初始值的数目时，可以使用一 种利用三个或者更多级数来生成常数的构造。[18.为多个总转置生成常数的方法]压缩函数包括多个总转置，并且需要准备由用于相应总转置的多个常数构成的成 组常值。当总转置的数目为m时，总转置分别由Ρ1、Ρ2···、Κιι代表。当使用上述常数生成技 术时，一种根据总转置的数目m随着总转置而改变m组初始值以生成向总转置中的内部转 置应用的常值是适用的。然而使用这样的技术，使得用于生成常值的工作量增加了 m倍，因 而它并不高效。下文将描述一种简化用于施加多个总转置的常数组的生成处理的技术。例如在压 缩函数中包括m个总转置的情况下，通过上述使用多个初始值S和T的方法来生成第一总 转置所需的常数，并且通过对为第一总转置生成的常数的简单运算来生成要向第二和后面 的总转置应用的常数。在一种数据转换处理构造(例如在构造中为压缩函数提供m个总转置的构造) 中，在从第X总转置的输入侧起的第i内部转置中包括的第j常值(字)由Cij(X)代表。 通过上述使用多个初始值S和T的方法来生成用于第一总转置的常数Cij(I)。这时生成用于第二和后面的总转置的常数Cu(2)、CU(3)、…、Cij(Hi)。下文将参照 图34描述一种生成用于第二和后面的总转置的常数Cij O)、Cij (3)、…、Cij(Hi)的技术。图34图示了通过上述使用多个初始值S和T的方法来生成的第一常数组480以 及通过对第一常数组480的转换处理来生成的第二常数组481、第三常数组482和第m常数 组483作为m个总转置所需的常数组。设置所有m个总转置为如下示例，在该示例中，在各总转置中包括k个内部转置并 且对于各内部转置需要四个常数字。通过对第一常数组480的转换处理来生成第二至第m常数组。下文将描述转换处 理的具体示例。作为转换处理，以下三种转换处理中的任一种可适用。(转换处理示例1)生成常数为Ciij(X) =Ciij(I) <<<Rx，其中在各总转置中确定的不同旋转量为 Rx。Ciij(I)是如下常数，该常数作为通过上述使用多个初始值S和T的方法生成的第一常数组480中的元素。另外，χ是常数组的标识号并且具有2至m的值。(转换处理示例2)生成常数为Cm(X) =Cio-(I)XOR Mx，其中在各总转置中确定的不同掩码值(字) 为Mx。Cm(I)是如下常数，该常数作为通过上述使用多个初始值S和T的方法生成的第一 常数组480中的元素。另外，χ是常数组的标识号并且具有2至m的值。(转换处理示例3)该方法组合上述转换处理示例1与示例2。生成常数为Ciij (χ) = (Cijj(I) <<< Rx)XOR Mx 或者 Ciij(X) = (Cijj(I)XOR Mx) <<<Rx。Cm(I)是如下常数，该常数作为通过上述使用多个初始值S和T的方法生成的 第一常数组480中的元素。另外，χ是常数组的标识号并且具有2至m的值。允许利用上述转换处理示例1至示例3中的任何示例、由一个常数组生成多个不 同常数组，并且设置常数组作为向相应总转置应用的常数。注意在上述转换处理示例1的情况下可保证除非Ciij(I)具有特殊位模式，否则在 用于任意X和y的Cq(X)与Cu(y)之间的异或运算的结果非0;因此允许构造不同总转 置。另外在上述转换处理示例2的情况下也可保证异或运算的结果非0 ；因此该处理示例 也适合于生成不同总转置。此外，在上述转换处理示例中表明的旋转量和掩码值使用各总转置中确定的值； 然而在如下构造中预期有相同效果，在该构造中为旋转量和掩码值提供多个值并且使用这 些值作为旋转量和掩码值以生成一个总转置所需的多个常值。当提供用于第一旋转函数的成组常值时，通过使用这些方法来允许以少量处理成 本生成用于不同转置函数的成组常值；因此预期有更快的处理。具体而言，在程序执行功能(也就是软件)安装于数据转换器中的情况下适用如 下编程模式，在该模式中在必要时动态地生成而不在存储器上暂时地解压用于所有总转置 的成组常值，因而预期提高存储器使用效率。在上述示例中描述其中随着字进行旋转运算的示例；然而可以修改旋转操作以每 两个或者更多字进行该操作并且预计与上述效果相同的效果。[19.减少哈希函数的输出值的技术]接着将描述数据转换器的配置示例，在该示例中，在哈希值生成处理构造中准备 用于生成η位哈希值的函数并且将输出的位数减少k位，从而允许生成n-k位哈希值。例如准备具有256位输出的哈希函数并且将输出的位数减少32位以生成2M位 哈希函数。图35图示了与图30中所示内部转置部(转置函数)410的构造相同的构造并且 图示了总转置的最后一级中的内部转置处理构造。输出71至78是来自总转置的输出并且 代表作为哈希函数的输出的哈希值。在图35中简化1个字G个字节)的数据线并图示为 一条数据线。所有输出Y1至y8合计为4X8 = 32字节=256位的输出。为了简化描述，在输出之前没有立即进行在异或运算之后转置数据的处理。另外 在输出之前立即要与数据级数异或的数据Xi代表前馈的数据并且由作为向压缩函数施加 的中间值的链接变量或者消息构成。考虑一种从作为输出的η位数据中删除作为删除数据的k位数据以减少输出数据的长度的方法。有必要从附图中的输出级数71至78中选择位长度要减少的数据级数。作 为一种方法，有一种从左侧起将位长度依次地减少k位的方案。在这种情况下考虑以下问 题。在k位超过从左侧起的两条数据线的总大小的情况下，当校验作为长度减少结果的输 出数据时，对最左侧的线性转换处理的结果对其余输出的任何位没有影响。这表明对这一 部分的计算是不必要的。作为为了消除这样的不必要处理而没有大量地减少具体数据级数的长度的技术， 下文将描述以下两个处理技术。(数据长度减少技术1)输出数据级数的数目为m，而要减少的位数(删除的位数)为k。为了尽可能均勻 地将k位划分为m个，通过以下数学表达式来计算参数a和b。[数学表达式1]
权利要求
1.一种数据转换器，包括数据转换部，接收消息数据以生成哈希值，所述数据转换部被配置成在并行地处理构 成所述消息数据的分割数据块的多个处理序列中，执行利用多个压缩函数执行部的数据转 换处理，其中所述多个压缩函数执行部中的各压缩函数执行部被配置成进行以下处理利用消息调度部的处理，所述消息调度部接收所述消息数据的对应分割数据块以进行 消息调度处理；以及利用链接变量处理部的处理，所述链接变量处理部接收来自所述消息调度部的输出和 作为来自前级处理部的输出的中间值以通过对接收的数据进行压缩来生成位数与所述中 间值的位数相同的输出数据，并且在所述多个处理序列中分别进行并行处理的所述多个压缩函数执行部被配置成共同 地使用所述消息调度部和所述链接变量处理部中的一个或者两个并且允许利用单个消息 调度部或者单个链接变量处理部。
2.根据权利要求1所述的数据转换器，其中在所述多个处理序列中分别进行并行处理的所述多个压缩函数执行部包括由所述多 个压缩函数执行部共同地使用的单个共同消息调度部，所述共同消息调度部被配置成接收构成所述消息数据的所述分割数据块、通过对所述 分割数据块进行所述消息调度处理来生成输出数据并且将所生成的输出数据输出到多个 链接变量处理部，并且所述多个链接变量处理部中的各链接变量处理部被配置成并行执行如下处理，在各所 述处理中对应的链接变量处理部接收来自所述共同消息调度部的输出和作为来自前级压 缩函数执行部的输出的中间值来对接收的数据进行压缩，以由此生成位数与所述中间值的 位数相同的输出数据。
3.根据权利要求1所述的数据转换器，其中在所述多个处理序列中分别进行并行处理的所述多个压缩函数执行部包括由所述多 个压缩函数执行部共同地使用的单个共同链接变量处理部，在进行并行处理的所述多个压缩函数执行部中的各压缩函数执行部中提供的多个消 息调度部被配置成接收所述消息数据的相同的分割数据块、通过消息调度处理来生成输出 数据并且将所生成的输出数据输出到所述共同链接变量处理部，并且所述共同链接变量处理部被配置成接收所述多个消息调度部的输出和作为来自前级 压缩函数执行部的输出的中间值来对接收的数据进行压缩，以由此生成位数与所述中间值 的位数相同的输出数据。
4.根据权利要求3所述的数据转换器，其中在进行并行处理的所述多个压缩函数执行部中的各压缩函数执行部中提供的所述多 个消息调度部被配置成接收所述消息数据的相同的分割数据块、通过消息调度处理来生成 输出数据并且将所生成的输出数据的异或运算输出到所述共同链接变量处理部。
5.根据权利要求1所述的数据转换器，其中所述消息调度部由具有中间输出的转置函数执行部配置，所述转置函数执行部重复地 执行转置处理以输出作为各所述转置处理的结果的中间值，并且所述链接变量处理部被配置成包括具有附加输入的转置函数执行部，所述转置函数执 行部利用从具有中间输出的所述转置函数执行部输出的所述中间值作为附加输入来重复 地执行转置处理。
6.根据权利要求5所述的数据转换器，其中所述链接变量处理部被配置成利用异或结果作为用于随后的所述转置处理的输入数 据，所述异或结果是在从具有中间输出的所述转置函数执行部输出的所述中间值与前级中 的转置处理的结果之间的异或运算的逻辑值。
7.根据权利要求5所述的数据转换器，其中所述转置函数执行部执行的各所述转置处理包括对输入数据的部分或者全部进行的 非线性转换处理和作为数据互换处理的交换处理。
8.根据权利要求7所述的数据转换器，其中所述非线性转换处理是包括使用常数的异或运算、非线性转换和使用线性转换矩阵的 线性转换的处理。
9.根据权利要求7所述的数据转换器，其中在所述转置函数执行部执行的各所述转置处理中进行的线性转换处理是利用多个不 同矩阵根据DSM(扩散切换机制)执行的处理。
10.根据权利要求5所述的数据转换器，其中所述转置函数执行部执行的所述转置处理被配置成分别利用互不相同的多个常数组 来进行数据处理，并且通过对基本组进行的数据转换处理来生成的互不相同的所述多个常数组分别使用于 所述转置处理中，所述基本组定义为在一个转置处理中要使用的常数组。
11.根据权利要求10所述的数据转换器，其中作为所述基本组利用的所述常数组由通过向互不相同的多个初始值S和T应用转换规 则来生成的多个常数配置，并且所述转换规则被配置成包括对所述初始值进行的更新处理，所述更新处理由以下表达 式代表S — S · xa，T — T · X其中a乒b。
12.根据权利要求10所述的数据转换器，其中对所述基本组进行的所述数据转换处理是允许对构成所述基本组的各常数的位旋转 操作的处理或者允许在构成所述基本组的各常数与预定掩码数据之间的逻辑运算的处理。
13.根据权利要求1所述的数据转换器，其中所述数据转换部被配置成进行允许最终输出的哈希值在位数上减少的减少处理，并且根据预定计算表达式来计算在构成所述数据转换部的输出的多个输出数据级数中的 各级数的输出位中的将减少的位数，然后根据所述计算的结果来执行所述减少处理。
14.根据权利要求1所述的数据转换器，其中所述数据转换部还包括对输入数据执行数据加扰处理的加扰处理部，所述多个压缩函数执行部被配置为被允许接收所述消息数据的所有分割数据块的多 级压缩部，所述多级压缩部中的一些压缩部被配置成接收所述加扰处理部的输出和所述消息数 据的所述分割数据块这两者以基于接收的数据来执行所述数据压缩处理，所述多级压缩部中的一些压缩部被配置成接收前级压缩部的输出和所述消息数据的 所述分割数据块这两者以基于接收的数据来执行所述数据压缩处理，并且位于所述多级压缩部的最后一级中的压缩部被配置成输出所述消息数据的哈希值。
15.一种数据转换方法，是由数据转换器执行的数据转换处理方法，所述数据转换方法 包括数据转换步骤，通过数据转换部接收消息数据以生成哈希值，所述数据转换步骤是在 并行地处理构成所述消息数据的分割数据块的多个处理序列中，执行利用多个压缩函数执 行部的数据转换处理的步骤，其中所述多个压缩函数执行部中的各压缩函数执行部进行利用消息调度部的处理，所述消息调度部接收所述消息数据的对应分割数据块以进行 消息调度处理；以及利用链接变量处理部的处理，所述链接变量处理部接收来自所述消息调度部的输出和 作为来自前级处理部的输出的中间值以通过对接收的数据进行压缩来生成位数与所述中 间值的位数相同的输出数据，并且在所述多个处理序列中分别进行并行处理的所述多个压缩函数执行部共同地使用所 述消息调度部和所述链接变量处理部中的一个或者两个并且进行利用单个消息调度部或 者单个链接变量处理部的处理。
16.一种在数据转换器中执行数据转换处理的程序，所述程序包括数据转换步骤，通过数据转换部接收消息数据以生成哈希值，所述数据转换步骤是在 并行地处理构成所述消息数据的分割数据块的多个处理序列中，执行利用多个压缩函数执 行部的数据转换处理的步骤，其中所述程序允许所述多个压缩函数执行部中的各压缩函数执行部执行 利用消息调度部的处理，所述消息调度部接收所述消息数据的对应分割数据块以进行 消息调度处理；以及利用链接变量处理部的处理，所述链接变量处理部接收来自所述消息调度部的输出和 作为来自前级处理部的输出的中间值以通过对接收的数据进行压缩来生成位数与所述中 间值的位数相同的输出数据，并且所述程序允许在所述多个处理序列中分别进行并行处理的所述多个压缩函数执行部 共同地使用所述消息调度部和所述链接变量处理部中的一个或者两个并且进行利用单个 消息调度部或者单个链接变量处理部的处理。
全文摘要
实现一种具有改进的压缩函数执行部的构造。在并行地处理构成所述消息数据的分割数据块的多个处理序列中，执行利用多个压缩函数执行部的数据转换处理。多个压缩函数执行部中的各压缩函数执行部进行利用消息调度部的处理和利用链接变量处理部的处理，该消息调度部接收消息数据的对应分割数据块以进行消息调度处理，该链接变量处理部接收来自消息调度部的输出和作为来自前级处理部的输出的中间值以通过对接收的数据进行压缩来生成位数与中间值的位数相同的输出数据。分别进行并行处理的多个压缩函数执行部共同地使用消息调度部和链接变量处理部中的一个或者两个并且允许利用单个消息调度部或者单个链接变量处理部。通过这样的构造实现硬件配置尺寸的减少和处理步骤的简化。
文档编号G09C1/00GK102138170SQ20098013229
公开日2011年7月27日 申请日期2009年8月25日 优先权日2008年8月25日
发明者岩田哲, 涩谷香士, 白井太三, 盛合志帆, 秋下彻 申请人:索尼公司
技术领域：
本发明涉及数据转换器、数据转换方法和程序。更具体地，本发明涉及例如对输入 消息数据进行哈希值生成处理的数据转换器、数据转换方法和程序。
背景技术：
在数据转换处理如加密处理中经常使用对输入数据执行哈希处理的哈希(Hash) 函数。哈希函数是用于根据供应的消息来计算定长压缩值(摘要)的函数。已知的哈希函 数包括具有1 位输出值的MD5、具有160位输出值的SHA-1、具有256位输出值的SHA-256等。例如基于对增加抗分析性的请求，哈希函数需要以下抗性抗前像性(Preimage
resistance)抗第 2 前像性(Second pre image resistance)抗冲突性(Collision resistance)下文将简述这些抗性。在生成y = h(x)作为输出的哈希函数(其中输入是χ而哈希函数是h)中，抗前 像性对应于计算输入X使得输出y为y = h(x)的难度。抗第2前像性对应于在一个输入值χ已知的情况下发现满足h (X’)= h (χ)的另 一输入值X’的难度。抗冲突性对应于发现满足h(x’ ) =h(x)的两个不同输入值X和X’的难度。认为这些抗性越高、哈希函数具有的安全特性就越高。在前级使用的哈希函数中，分析方法的最新发展发现了上述抗性的弱点。例如已 经变得清楚，在经常用作哈希函数的MD5、SHA-I等中，抗冲突性不满足大量系统请求级。 另外作为现有哈希函数，包括输出长度相对长的SHA-256 ；然而仍有安全特性之忧，因为 SHA-256遵循SHA-I的设计原理，因此期望有基于其它设计原理的具有更高安全特性的哈 希函数。
发明内容
做出本发明以解决上述问题，并且本发明的目的在于提供一种实现具有高安全特 性和高处理效率的哈希函数的数据转换器、数据转换方法和程序。本发明的第一方面提供一种数据转换器，该数据转换器包括数据转换部，接收消 息数据以生成哈希值，该数据转换部被配置成在并行地处理构成消息数据的分割数据块的 多个处理序列中，执行利用多个压缩函数执行部的数据转换处理，其中多个压缩函数执行 部中的各压缩函数执行部被配置成进行以下处理利用消息调度部的处理，该消息调度部 接收消息数据的对应分割数据块以进行消息调度处理；以及利用链接变量处理部的处理， 该链接变量处理部接收来自消息调度部的输出和作为来自前级处理部的输出的中间值以 通过对接收的数据进行压缩来生成位数与中间值的位数相同的输出数据，并且在多个处理序列中分别进行并行处理的多个压缩函数执行部被配置成共同地使用消息调度部和链接 变量处理部中的一个或者两个并且允许利用单个消息调度部或者单个链接变量处理部。另外，在本发明的数据转换器的一个实施例中，在多个处理序列中分别进行并行 处理的多个压缩函数执行部包括由多个压缩函数执行部共同地使用的单个共同消息调度 部，共同消息调度部被配置成接收构成消息数据的分割数据块、通过对分割数据块进行消 息调度处理来生成输出数据并且将所生成的输出数据输出到多个链接变量处理部，并且多 个链接变量处理部中的各链接变量处理部被配置成并行执行如下处理，在各处理中对应的 链接变量处理部接收来自共同消息调度部的输出和作为来自前级压缩函数执行部的输出 的中间值来对接收的数据进行压缩，以由此生成位数与中间值的位数相同的输出数据。另外，在本发明的数据转换器的一个实施例中，在多个处理序列中分别进行并行 处理的多个压缩函数执行部包括由多个压缩函数执行部共同地使用的单个共同链接变量 处理部，在进行并行处理的多个压缩函数执行部中的各压缩函数执行部中提供的多个消息 调度部被配置成接收消息数据的相同的分割数据块、通过消息调度处理来生成输出数据并 且将所生成的输出数据输出到共同链接变量处理部，并且共同链接变量处理部被配置成接 收多个消息调度部的输出和作为来自前级压缩函数执行部的输出的中间值来对接收的数 据进行压缩以由此生成位数与中间值的位数相同的输出数据。另外，在本发明的数据转换器的一个实施例中，在进行并行处理的多个压缩函数 执行部中的各压缩函数执行部中提供的多个消息调度部被配置成接收消息数据的相同分 割数据块、通过消息调度处理来生成输出数据并且将所生成的输出数据的异或运算输出到 共同链接变量处理部。另外，在本发明的数据转换器的一个实施例中，消息调度部由具有中间输出的转 置函数执行部配置，转置函数执行部重复地执行转置处理以输出作为各转置处理的结果的 中间值，并且链接变量处理部被配置成包括具有附加输入的转置函数执行部，转置函数执 行部利用从具有中间输出的转置函数执行部输出的中间值作为附加输入来重复地执行转
置处理。另外，在本发明的数据转换器的一个实施例中，链接变量处理部被配置成利用XOR 结果作为用于随后的转置处理的输入数据，XOR结果是在从具有中间输出的转置函数执行 部输出的中间值与前级中的转置处理的结果之间的异或运算的逻辑值。另外，在本发明的数据转换器的一个实施例中，转置函数执行部执行的各转置处 理包括对输入数据的部分或者全部进行的非线性转换处理和作为数据互换处理的交换处 理。另外，在本发明的数据转换器的一个实施例中，非线性转换处理是包括使用常数 的异或运算、非线性转换和使用线性转换矩阵的线性转换的处理。另外，在本发明的数据转换器的一个实施例中，在转置函数执行部执行的各转置 处理中进行的线性转换处理是利用多个不同矩阵根据DSM(扩散切换机制)执行的处理。另外，在本发明的数据转换器的一个实施例中，转置函数执行部执行的转置处理 被配置成分别利用互不相同的多个常数组来进行数据处理，并且通过对基本组进行的数据 转换处理来生成的互不相同的多个常数组分别使用于转置处理中，基本组定义为将在一个 转置处理中使用的常数组。
6
另外，在本发明的数据转换器的一个实施例中，将作为基本组利用的常数组由通 过向互不相同的多个初始值S和T应用转换规则来生成的多个常数配置，并且转换规则被 配置成包括对初始值进行的更新处理，更新处理由以下表达式代表S — S · xa，T 一 T · χ其中a乒b。另外，在本发明的数据转换器的一个实施例中，对基本组进行的数据转换处理是 允许对构成基本组的各常数的位旋转操作的处理或者允许在构成基本组的各常数与预定 掩码数据之间的逻辑运算的处理。另外，在本发明的数据转换器的一个实施例中，数据转换部被配置成进行允许最 终输出的哈希值在位数上减少的减少处理，并且根据预定计算表达式来计算在构成数据转 换部的输出的多个输出数据级数中的各级数的输出位中的将减少的位数，然后根据计算的 结果来执行减少处理。另外，在本发明的数据转换器的一个实施例中，数据转换部还包括对输入数据执 行数据加扰处理的加扰处理部，多个压缩函数执行部被配置为被允许接收消息数据的所有 分割数据块的多级压缩部，多级压缩部中的一些压缩部被配置成接收加扰处理部的输出和 消息数据的分割数据块这两者以基于接收的数据来执行数据压缩处理，多级压缩部中的一 些压缩部被配置成接收前级压缩部的输出和消息数据的分割数据块这两者以基于接收的 数据来执行数据压缩处理，并且位于多级压缩部的最后一级中的压缩部被配置成输出消息 数据的哈希值。另外，本发明的第二方面提供一种数据转换方法，该方法是由数据转换器执行的 数据转换处理方法，该数据转换方法包括数据转换步骤，通过数据转换部接收消息数据 以生成哈希值，数据转换步骤是在并行地处理构成消息数据的分割数据块的多个处理序列 中，执行利用多个压缩函数执行部的数据转换处理的步骤，其中多个压缩函数执行部中的 各压缩函数执行部进行利用消息调度部的处理，消息调度部接收消息数据的对应分割数 据块以进行消息调度处理；以及利用链接变量处理部的处理，链接变量处理部接收来自消 息调度部的输出和作为来自前级处理部的输出的中间值以通过对接收的数据进行压缩来 生成位数与中间值的位数相同的输出数据，并且在多个处理序列中分别进行并行处理的多 个压缩函数执行部共同地使用消息调度部和链接变量处理部中的一个或者两个并且进行 利用单个消息调度部或者单个链接变量处理部的处理。另外，本发明提供一种在数据转换器中执行数据转换处理的程序，该程序包括数 据转换步骤，通过数据转换部接收消息数据以生成哈希值，数据转换步骤是在并行地处理 构成消息数据的分割数据块的多个处理序列中，执行利用多个压缩函数执行部的数据转换 处理的步骤，其中该程序允许多个压缩函数执行部中的各执行部执行利用消息调度部的 处理，消息调度部接收消息数据的对应分割数据块以进行消息调度处理；以及利用链接变 量处理部的处理，链接变量处理部接收来自消息调度部的输出和作为来自前级处理部的输 出的中间值以通过对接收的数据进行压缩来生成位数与中间值的位数相同的输出数据，并 且该程序允许在多个处理序列中分别进行并行处理的多个压缩函数执行部共同地使用消 息调度部和链接变量处理部中的一个或者两个并且进行利用单个消息调度部或者单个链 接变量处理部的处理。
此外，本发明的程序例如是被允许以计算机可读格式通过存储介质或者通信介质 向能够执行各种程序代码的通用系统提供的程序。以计算机可读格式提供程序；因此根据 程序的处理在计算机系统上实施。本发明的更多目的、特征或者优点根据基于附图对本发明一个示例性实施例的下 文描述或者更多具体描述将变得清楚。此外，在本说明书中，“系统”是指多个设备的逻辑集 合配置、无论个别组成设备是否容纳于一个罩中。本发明的一个示例性实施例具有如下构造，在该构造中在并行地处理构成所述消 息数据的分割数据块的多个处理序列中，执行利用多个压缩函数执行部的数据转换处理。 多个压缩函数执行部中的各压缩函数执行部进行利用消息调度部的处理和利用链接变量 处理部的处理，该消息调度部接收消息数据的对应分割数据块以进行消息调度处理，该链 接变量处理部接收来自消息调度部的输出和作为来自前级处理部的输出的中间值以通过 对接收的数据进行压缩来生成位数与中间值的位数相同的输出数据。在多个处理序列中分 别进行并行处理的多个压缩函数执行部共同地使用消息调度部和链接变量处理部中的一 个或者两个并且允许利用单个消息调度部或者单个链接变量处理部。这样的构造实现了硬 件配置尺寸的减少和处理步骤的简化。
图1是将压缩函数(f)描述为数据压缩部的图示。图2是描述具有消息填充(一种典型的域扩展方法)的MD (Merkle-Damgard)构 造的图示。图3是描述级联哈希构造的图示，该构造利用具有很小输出位大小的压缩函数来 实现具有很大输出位大小的哈希值。图4是描述具有增强安全特性的压缩部(压缩函数)的构造的图示。图5是描述哈希函数构造示例的图示，在该示例中，图4中所示压缩函数单元50 连接为MD构造。图6是将哈希函数构造示例描述为图5中所示构造使用压缩函数单元55的修改 示例的图示，在该示例中，各压缩函数中的加扰函数F以及压缩函数fl和f2的顺序改变。图7是描述通过从图6中所示构造中去除最后一个压缩函数单元中的加扰函数F 来配置的构造示例的图示。图8是描述设置每两个压缩函数处理插入加扰函数F的构造示例的图示。图9是描述推广的哈希函数执行部的构造示例的图示，在该示例中设置每k个压 缩函数插入加扰函数F。图10是描述利用两个压缩函数来实现加扰函数F的构造示例的图示。图11是描述在序列中有m个压缩函数的哈希函数的推广的构造示例的图示，其中 m是2或者更大的整数。图12是描述具有mb位输入/输出的加扰函数F的构造示例的图示。图13是描述压缩函数f的内部构造示例的图示。图14是描述为具有MD构造的哈希函数提供由消息调度部(MS部)和链接变量 (CV)处理部构成的压缩函数构造示例的图示。
图15是描述一般使用消息调度部的哈希函数的构造示例的图示。图16是描述压缩函数的构造示例的图示，该示例扩展压缩函数中的输入消息大图17是描述具有如下构造的压缩函数的构造示例的图示，在该构造中，消息调度 部分割成两个部分。图18是描述具有如下构造的压缩函数的构造示例的图示，在该构造中，消息调度 部分割成两个部分并且包括异或运算O(OR)部。图19是描述压缩函数的构造示例的图示，该函数被设置成通过推广图17中所示 的压缩函数的构造来响应于na位输入。图20是描述压缩函数的构造示例的图示，该函数被设置成通过推广图18中所示 的压缩函数的构造来响应于na位输入。图21是描述具有附加输入的转置函数的示例的图示。图22是描述具有中间输出的转置函数的示例的图示。图23是描述使用现有转置函数的压缩函数的构造示例的图示。图M是描述扩展向压缩函数施加的数据大小的压缩函数的构造示例的图示。图25是描述将输入位长度扩展为3a位的压缩函数的构造示例的图示。图沈是描述将输入位长度扩展为3a位的压缩函数的构造示例的图示。图27是描述在序列中的两个压缩函数共同地使用消息调度部的构造示例的图
示 ο图28是描述扩展向压缩函数施加的数据大小的压缩函数的构造示例的图示。图四是描述由具有中间输出的两个转置函数与具有附加输入的两个转置函数的 组合构成的加扰函数F的构造示例的图示。图30是描述被允许用作内部转置的转置函数的具体构造示例的图示。图31是描述在内部转置部(转置函数)中配置的非线性转换部的内部构造的示 例的图示。图32是描述为了使用多个不同矩阵作为在内部转置部(转置函数)的非线性转 换部中使用的线性转换矩阵[M]而设置的内部转置部的重复回合的构造示例的图示。图33是描述为了使用多个不同矩阵作为线性转换矩阵[M]而设置的内部转置部 的重复回合的构造示例的图示。图34是描述一种为总转置生成常数Cij O)、Cij (3)、…Cij(Hi)的技术的图示。
图35是描述一种减少哈希函数的输出位长度的技术的示例的图示。图36是描述一种减少哈希函数的输出位长度的技术的示例的图示。图37是IC模块的配置示例的图示，该模块作为执行根据本发明的处理的数据转换器。
具体实施例方式下文将参照附图具体描述本发明的数据转换器、数据转换方法和程序。将按以下顺序给出描述。1.域扩展方法
2.用于扩展输出大小的新颖域扩展方法3.提高新颖域扩展方法的处理效率的方法4.实现加扰函数F的方法5.域扩展方法的推广6.加扰函数的F的构造的推广7.使用不同压缩函数8.实现压缩函数的内部处理的高效方法9.扩展输入消息长度的方法10.在CV处理部和MS部中使用重复转置来实现哈希函数的方法11.扩展MS部大小的方法12.扩展CV处理部大小的方法13.扩展CV处理部和MS部大小的方法14.为域扩展方法构造加扰函数F的方法15.实现扩散能力高的转置处理的方法16.生成输出高度独立的转置函数的方法17.生成向转置函数施加的常数的处理18.为多个总转置生成常数的方法19.减少哈希函数的输出值的技术20.数据转换器的配置示例[1.域扩展方法]如上文所述，希望哈希函数执行部具有上述各种抗性、也就是抗前像性、抗第2前 像性和抗冲突性。注意本发明的数据转换器包括下文将描述的各种函数执行部，比如哈希函数执行 部和压缩函数执行部。在下文描述中，在本发明的数据转换器中执行各函数的函数执行部 中执行这里简单表达的术语“函数”。注意利用硬件或者软件或者二者来实现函数执行部。哈希函数将压缩函数用于根据施加的消息来计算定长压缩值(摘要)。当构造由 执行哈希函数的硬件或者软件构成的哈希部时，有必要让哈希部具有一种考虑到上述各种 抗性的构造。允许哈希部的构造广泛地分割成两个以下等级(1)作为第一等级的域扩展部，以及(2)作为第二等级的压缩函数的内部构造。域是作为哈希函数的输入值的最大可允许位大小(输入大小)。一个压缩函数执 行部进行将定长输入值转换成定长输出值的处理；然而一般而言，一个压缩函数执行部具 有很小的最大可允许输入位大小并且不被允许处理具有很大位大小的输入值；因此通过连 接多个压缩函数来扩展域，从而处置任意长度的消息输入。通过这样的处理允许对具有很 长位长度的输入数据进行哈希。进行这样的处理作为域扩展处理。上述抗性的级别取决于作为第一等级的域扩展构造或者作为第二等级的压缩函 数的内部构造。下文将首先描述前者(即域扩展处理)的一种新颖方案。压缩函数是用于将作为 输入值的位串转换成比输入位长度更短的位串的函数。图1图示了作为压缩部的压缩函数
图1中所示的压缩函数10是用于接收具有a位的输入值X和具有b位的初始值 Y(也就是说，共计a+b位)以生成具有b位的输出Z的函数。作为压缩函数的输入值的最 大可允许位大小称为域(输入大小)。不允许仅由一个压缩函数10处理长输入消息；因此 适当地连接压缩函数以扩展域(输入大小)，从而允许扩展输入消息大小。换而言之，允许 输入具有很长位长度的数据。图2图示了具有消息填充(一种典型的域扩展方法)的MD (Merkle-Damgard)构 造。注意例如在 R. Merkle 的"One way hash functions and des"(见 Proceedings of Crypto (密码学报)'89 (G. Brassard 编辑)，LNCS 中的 no. 435,第似8_446 页， Springer-Verlag(施普林格出版社)，1989)禾口 I. Damgard 的〃 A design principle for hash functions"(见Proceedings of Crypto (密码学 艮)'89 (G. Brassard编辑)，LNCS 中的 no. 435，第 417-427 页，Springer-Verlag(施普林格出版社)，1989)。如图2中所示，MD构造是一种允许通过串联布置压缩函数(f)来扩展输入大小的 构造。通过填充(padding)将输入消息校正为位数为a位的整数倍(压缩函数的消息输入 部大小)的值，填充是作为用于位长度调节的位数据添加处理而进行的。MtlJpM2、…、Mn_2、 Mn_」填充是受到填充的输入消息分割成的a位块。[Mn_」填充]是通过向作为输入消息最 后一块的数据[Mn_J添加作为附加位块的填充数据来获得的输入位大小为a位的数据。为了生成消息的摘要，在MD构造中利用多个压缩函数来重复如下操作在该操作 中向压缩函数11施加并且在压缩函数11中压缩具有b位的预定初始值IV和第一分割消 息Mtl以生成具有b位的值作为中间值、然后向压缩函数12施加并且在压缩函数12中压缩 中间值和后继消息，以最终获得哈希值(H)，。这时的中间值称为链接变量。已知只要各压缩函数具有抗冲突性，就允许MD构造表明整个哈希函数具有抗冲 突性，并且MD构造经常用于实际的哈希函数。使用MD构造的典型哈希函数包括MD5和 SHA-I0[2.用于扩展输出大小的新颖域扩展方法]在上述构造中描述了 b位输出的情况，现在下文将考虑生成具有很长的位长度为 2b位的哈希值的哈希函数的构造。在原样使用上述MD构造的情况下，有必要准备具有2b位输出的压缩函数。然而 一般而言，难以重新构造具有很大输出和高安全特性的压缩函数。有必要设计新颖压缩函 数并且评估该压缩函数的安全特性，并且输出大小越大，就越难以设计和评估压缩函数。因 此希望利用已经评估的具有b位输出的压缩函数来构造具有2b位输出的哈希函数。作为一种利用具有很小输出位大小的压缩函数来实现具有很大输出位大小的哈 希值的相关技术，已知一种级联(cascading)哈希构造。将参照图3描述级联哈希构造。级联哈希构造是被允许利用并联布置的两个压缩函数来生成具有很大输出大小 的哈希值的构造。如图3中所示，通过简单地并联布置两个压缩函数f\和f2来构造级联哈 希构造。然而通过布置这样的两个具有b位输出的压缩函数来执行2b位的输出的哈希函 数的安全特性未达到输出大小为2b位的哈希函数的希望水平。已知哈希函数具有与输出 大小为b位的哈希函数近似相等的安全特性。例如在A. Joux的〃 Multicollisions initerated hash functions, application to cascaded constructions" (JALProceedings of Crypto' 04 (M. Franklin, ed.)，no.3152in LNCS, p.306—316，Springer-Verlag, 2004) 中描述了这一点。接着下文将参照图4描述根据本发明一个示例实施例的具有增强安全特性的压 缩部(压缩函数)的构造。图4图示了压缩函数单元50，该单元是具有a位输入和2b位输 出的压缩部。图4中所示压缩函数单元50包括压缩函数f 1和f2 (具有a+b位输入和b位 输出的两个独立数据压缩部)以及加扰函数F (作为具有2b位输入/输出的数据加扰部)。 换而言之，函数单元50包括一个加扰函数F以及两个压缩函数Π和f2的序列。压缩函数单元50接收a位数据[X]和2b位数据[Y]作为输入、也就是共计2b+a 位的输入。在输入中，2b位数据[Y]穿过具有2b位输入/输出的加扰函数F并且被加扰。 接着，来自加扰函数F的2b位输出被分割成b位数据块，并且b位数据块之一和作为压缩 函数单元50的另一输入的a-位数据X由单元中的压缩函数f 1处理。另一 b位数据块和 a位数据X同时由单元中的压缩函数f2处理。最终，通过组合f 1和f2的输出来生成的2b 位是压缩函数50的输出。注意加扰函数F是用于对接收的2b位数据进行加扰并且输出2b 位数据的函数并且是与两个压缩函数Π和f2不同的压缩函数。图5图示了哈希函数构造示例，在该示例中连接图4中所示压缩函数单元50作为 用于域扩展的MD构造从而允许处理具有很长位长度的输入。图5中所示数据转换器包括 由MD构造构成的数据转换部。图5中所示构造是一种由包括η个参照图4描述的压缩函 数单元50的数据转换部构成的构造。换而言之，数据转换器是作为由η个如下压缩函数单 元50构成的哈希函数执行部的数据转换器，该压缩函数单元包括具有2b位输入/输出的 一个加扰函数F以及具有a+b位输入和b位输出的两个压缩函数fl和f2的序列。在图5中所示哈希函数中，压缩函数单元50-0至50-(n-l)用作η级的序列，并且 从最后一级中的压缩函数单元50-(η-1)生成沘位哈希值(H1IH2)15第一级中的压缩函数单元50-0接收位输入M0至Mlri中的第一 a位输入M0以及两 个b位初始值IV1和IV2,并且压缩函数Π和f2分别生成b位输出、也就是共计2b位的输 出。后继级中的压缩函数单元接收从前级中的压缩函数单元中的压缩函数fl和f2施加的 2b位以及作为M0至Mlri中的每个的组成位的a位以生成2b位的输出。在以后级中的压缩 函数单元中重复地执行相同处理，并且最后一级中的压缩函数单元接收从前级中的压缩函 数单元施加的2b位的输出和来自Mlri的a位以及填充数据以生成b位输出H1和H2、也就是 具有共计沘位的哈希值(H1IH2)15如果构成压缩函数单元50的压缩函数f 1和f2以及加扰函数F满足所谓随机启 示(oracle)的性质，则表明这种构造具有充分的安全特性。随机启示是一种在向其施加输 入时在其中生成随机数并且在向其施加以前已经施加过的输入时再次生成以往生成的随 机数的函数。在实践中，通过设计一种用于通过判决程序而无需与随机启示的行为近似的 随机数生成来计算输出的函数并且将函数转置成设计的函数来实现该构造。该构造允许在 压缩函数中使用具有容易评估的安全特性和轻负荷的处理的部分；因此可实现一种容易设 计并且具有高效率的哈希函数。在示例实施例中，在由多个回合(round)构成的压缩处理回合中至少按照固定间 隔执行加扰处理，因而实现一种生成具有增强抗分析性和高安全特性的哈希值的数据转换器。另外作为图5中所示构造的修改示例，如图6中所示，也在使用压缩函数单元 55 (其中改变加扰函数F以及压缩函数f 1和f2的顺序)的情况下允许使用该构造作为具 有相同效果的哈希函数。另外作为图5和图6中所示构造的修改示例，甚至允许使用通过从图6中所示构 造中去除最后一级中的加扰函数F来形成的构造作为在安全特性上具有相同效果的哈希 函数。由于通过重新定义图5中所示构造中作为IV1和IV2的第一加扰函数的输出来获得 这一构造，所以得到相同效果。因此允许用具有更小b位输出的压缩函数以及加扰函数F来构造具有2b位输出 和高安全特性的哈希函数而不是仅构造用于2b位输出的压缩函数。另夕卜，在图5、图6和图7的构造中，压缩函数单元中的各压缩函数fl和f2的输出 位数为b位，并且中间值、也就是内部压缩函数fl和f2中的链接变量彼此相等。然而并不一定让内部压缩函数Π和f2的链接变量(CV)的位大小彼此相等。例 如通过设置内部压缩函数fl和内部压缩函数f2以分别生成b位链接变量(CV)和c位链 接变量(CV)，总的链接变量(CV)可以具有b+c位。甚至在这样的构造中，通过更小函数的 构造可实现压缩函数单元，因而具有确认安全特性的针对小的位大小的压缩函数适用作为 内部压缩函数。[3.提高新颖域扩展方法的处理效率的方法]接着将参照图8描述使参照图5和图6描述的域扩展方法的处理效率提高的哈希 函数的构造示例。图8是哈希函数构造示例，在该示例中每两个压缩函数处理插入加扰函 数F。压缩函数单元60由加扰函数F、两个内部压缩函数fl和f3的序列以及两个内部 压缩函数f2和f4的序列构成。压缩函数单元60中包括的四个内部压缩函数是不同和独 立的压缩函数。换而言之，夹入于两个加扰函数F之间的区域中包括的四个压缩函数是独 立的压缩函数。第一级中的压缩函数单元60接收两个b位初始值IV1和IV2,并且加扰函数F对 接收的2b位数据进行加扰以向各压缩函数fl和f2施加b位。压缩函数fl和f2接收位 输入M0至Mlri中的第一 a位输入M0和来自加扰函数FWb位的输出以生成b位输出，然后 分别向后继序列中的压缩函数f3和f4施加b位输出。压缩函数f3和f4接收位输入Mtl至Mlri中的a位输入M1以及分别来自前级序列 中的压缩函数f 1和f2的b位输出以生成b位输出，然后向后继级中的压缩函数单元的加 扰函数施加b位输出。后继级中的压缩函数单元接收从前级中的压缩函数单元的压缩函数施加的2b位 和作为M0至Mlri的组成位的加位以生成2b位的输出。在以后级中的压缩函数单元中重复 地执行相同处理，并且最后一级中的压缩函数单元接收从前级中的压缩函数单元施加的2b 位、Mn_2的a位和Mlri的a位以及填充数据并且生成b位输出H1和H2、也就是具有共计2b 位的哈希值(HjH2)0在该构造中，与图5中所示构造相比，减少加扰函数F在处理具有相同长度的消息 时的调用次数，因而提高了处理效率。更具体地，在图5中所示构造中，需要两个加扰函数F和四个压缩函数以处理两个a位消息，而在图8中所示方案中，仅由一个加扰函数F和四 个压缩函数来处理消息，因而允许去除一个加扰函数，由此实现更高的处理效率。设置图8中所示构造以重复地执行加扰函数F和压缩函数的两个序列。可以应用 如下构造，在该构造中进一步减少加扰函数数目并且压缩函数的每三个或者更多序列插入 加扰函数F。在图9中图示了推广哈希函数执行部的构造示例，在该示例中每k个压缩函数 插入加扰函数F。在图9中所示构造中，压缩函数单元70包括具有2b位输入/输出的一个 加扰函数F和各包括具有a+b位输入和b位输出的两个压缩函数的k个序列。第一级中的压缩函数单元70接收两个b位初始值IV1和IV2,并且加扰函数F对 接收的2b位数据进行加扰以向一个序列中的各压缩函数fl和f2生成b位的输出。压缩 函数fl和f2接收位输入Mtl至Mlri中的第一 a位输入Mtl和来自加扰函数F的b位的输出 以生成b位输出，然后分别向后继序列中的压缩函数f3和f4施加b位输出。压缩函数f3和f4接收位输入Mtl至Mlri中的a位输入M1以及分别来自先级序列 中的压缩函数f 1和f2的b位输出以生成b位输出，然后分别向后继序列中的压缩函数施 加b位输出。重复以下处理k次，在该处理中向后继序列中的各压缩函数施加来自前级序 列中的各压缩函数的输出和构成各位输入Mtl至Mlri的a位并且各压缩函数生成b位输出， 并且向后继压缩函数单元71的加扰函数F施加来自第k个序列中的两个压缩函数的输出。压缩函数单元71的处理与压缩函数单元70的处理相同。然而向压缩函数单元71 施加位输入M0至Mlri中的后一半的位数据和填充数据。压缩函数单元71的最后一个序列 中的两个压缩函数分别生成b位输出H1和H2、也就是具有共计2b位的哈希值(H1IH2)。注意按照在无损于安全特性的范围内根据哈希值的2b位的输出长度来确定的间 隔来插入加扰函数F。例如在b = 256的情况下，值k为8。值k越大，处理效率就提高越
^^ ο图9中所示构造是如下构造，在该构造中，加扰函数F接收初始值并且各自包括两 个压缩函数的序列如图5中所示构造的情况那样跟随加扰函数F，但是可以使用如下压缩 函数单元，在该单元中，参照图6等描述的序列中的两个压缩函数接收初始值并且执行各 自包括两个压缩函数的多个序列，然后最终执行加扰函数F。[4.实现加扰函数F的方法]加扰函数F是用于对输入位进行加扰以生成位数与输入位相同的数据的函数。下 文将参照图10描述用于实现加扰函数的具体构造。图10是其中利用两个压缩函数来实现 加扰函数F的构造。图10(1)中所示加扰函数F80是如下示例，在该示例中利用具有b位输入和a位 输出的两个转换部81和82以及具有a+b位输入和b位输出的两个压缩函数83和84来实 现具有2b位输入/输出的加扰函数F80。供应将向加扰函数F80施加的两个分割的b位数 据块分别作为用于压缩函数83和84的b位输入。另外分别向转换部81和82同时施加两个b位数据块以转换成a位数据，然后供 应a位数据分别作为用于压缩函数83和84的a位输入数据。仅有必要让转换部81和82 进行用于调节位长度的简单处理，并且例如用简单的逻辑运算(比如通过复制位进行扩展 或者M)R)可实现转换部81和82。优选地设置转换部81和82以满足以下条件。具体而言，设置转换部81和82，从而用于加扰函数F80的输入的所有2b位对用于压缩函数83和84的a+b位的输入有影响。 允许通过图10中所示构造来构造加扰函数F，因而加扰函数F可仅由与两个压缩函数对应 的处理来实现。图10 (2)中所示加扰函数F85是其中用于转化部86和87的输入各自具有2b位 的示例。在例如a > b的情况下，用如下函数构造转换部86和87，该函数用于连接两个b 位数据、然后减少位数以通过简单的运算如XOR来生成a位。优选地设置转换部86和87 以满足以下条件。具体而言，设置转换部86和87，从而用于加扰函数F85的输入的所有2b 位对用于压缩函数88和89的a+b位的输入有影响。在该构造中，加扰函数F也可仅由与 两个压缩函数对应的处理来实现。允许使用图10中所示加扰函数F的构造作为参照图5至图9的哈希函数的构造 中的加扰函数F。当使用这样的构造时，通过重用最初为图5至图9中所示压缩函数单元提 供的压缩函数可实现加扰函数F。共享这样的部件在硬件实施时有效减少门规模，并且允许 器件尺寸减少和成本减少。[5.域扩展方法的推广]参照图5至图9描述的具有MD构造的哈希函数具有向包括两个压缩函数的序列 施加来自一个加扰函数F的输出这样的构造或者向一个加扰函数F施加来自包括两个压缩 函数的序列的输出这样的构造。换而言之，设置哈希函数以使用包括两个压缩函数的序列。序列中的压缩函数数目并不限于两个，并且可以使用其中在序列中包括三个或者 更多压缩函数的构造。在图11中图示了在序列中有m个压缩函数的哈希函数的推广构造 示例，其中m为2或者更大的整数。图11中的构造基于图9中所示构造并且在序列中包括m个压缩函数而不是两个 压缩函数。压缩函数单元90包括具有mb位输入/输出的加扰函数F和各自包括m个压缩 函数的多个序列。第一序列中的m个压缩函数Π至fm接收来自F函数的mb位的位数据 中的b位和位输入M0至Mlri中的第一 a位输入Mtl以生成b位的输出并且分别向后继序列 中的压缩函数施加b位的输出。第k个序列中的m个压缩函数接收分别来自前级序列中的 压缩函数的输出和位输入M0至Mlri中的a位以生成b位的输出。在第k个序列中的压缩函 数的处理之后，向后继压缩函数单元的加扰函数F施加来自压缩函数单元90的最后一个序 列中的压缩函数的mb位的输出。生成来自最后一级中的压缩函数单元91的最后一个序列中的m个压缩函数的b 位的输出氏至礼，即共计2mb位，作为哈希值(HjH2I- IHJo获得的哈希值H”H2、…、Hm 具有最多mb位。通过该技术容易实现具有更长长度的输出的哈希函数。[6.加扰函数F的构造推广]接着下文将描述加扰函数F的推广构造。上文参照图10描述了加扰函数F的具 体构造。参照图10描述的加扰函数F具有使用包括两个压缩函数的序列的构造。在图12中图示了通过推广参照图10描述的加扰函数F来形成的具有mb位输入/ 输出的加扰函数F的构造示例。图12中所示加扰函数FlOO由如下序列构成，该序列包括 具有c位输入和b位输出的m个压缩函数f 1至fm以及分别布置于压缩函数f 1至fm前面 的m个转换部。在图12中所示示例中，m种不同和独立的压缩函数fl至fm各自具有c位的输入大小。向各转换部暂时施加所有mb位，从而对压缩函数Π至fm施加所有输入位的影响， 并且减少输入大小以便对应于各压缩函数的输入大小。在转换部中，例如通过异或O(OR) 或者位大小扩展处理根据mb位输入生成c位输出。转换部必需的条件是作为用于加扰函数FlOO的输入位的所有mb位对c位输出中 的任何位施加影响。该条件可通过简单的操作实现。例如在C = Hlb的情况下，各转换部可 以不变地连接输入并且生成连接的输入。[7.不同压缩函数的使用]在上文描述中，在包括分割成多个序列的多个压缩函数fl、f2、…、fm的压缩函数 单元中，压缩函数单元中的压缩函数fl至fm具有不同构造。这一构造客观地表明最高安 全特性，并且即使使用单个压缩函数，仍然没有立即损害安全特性。在一些情况下，其中重 复使用单个压缩函数的构造具有实施上的优点；因此作为一个不同实施例，可以使用其中 所有压缩函数相同的构造。类似地，可以应用其中重复地使用较少种类而不是相同种类的 压缩函数的构造。[8.实现压缩函数的内部处理的高效方法]下文将描述为上述压缩函数单元提供的压缩函数fi的具体构造示例。在图13中 图示了压缩函数f的内部构造示例。图13是如下压缩函数fl的构造示例，允许使用该压 缩函数作为为参照图5至图12描述的压缩函数单元提供的压缩函数fi并且也作为加扰函 数F的组成要素。如图13中所示，压缩单元120包括消息调度部(MS部)121和链接变量(CV)处理 部122。在向压缩函数120施加的a+b位中，向消息调度部(MS部)121施加作为[X]的a 位，而向链接变量(CV)处理部122施加作为[Y]的其余b位。消息调度部(MS部)121基于a位输入通过消息调度处理来生成c位输出并且向链 接变量(CV)处理部122施加C位输出。链接变量(CV)处理部122接收用于压缩函数120 的b位的输入和从消息调度部(MS部)121施加的c位的输入，也就是b+c位，以生成b位 输出[Z]作为从压缩函数120的输出。图14图示了如下构造示例，在该示例中，为上文参照图5描述的具有MD构造的哈 希函数提供图13中所示压缩函数、也就是由消息调度部(MS部)和链接变量(CV)处理部 构成的压缩函数。图14中所示压缩函数单元130如上文参照图5描述的情况那样由加扰函数F以及 两个压缩函数Π和f2的序列构成。各压缩函数Π和f2具有参照图13描述的构造。换 而言之，各压缩函数Π和f2是由消息调度部(MS部)和链接变量(CV)处理部构成的压缩 函数。在图14中所示示例中，分别由MSl和MS2代表两种压缩函数fl和f2中的消息调 度部(MS部)，而分别由CVl和CV2代表链接变量(CV)处理部。通过该构造可实现哈希函 数。下文将描述一种实现进一步提高处理效率的构造。在图14中所示各压缩函数单元130-0至130-(η-l)中，向两个压缩函数中的消息 调度部MSl和MS2同时施加消息Mi。因此，当相互叠加布置的两个压缩函数共同地使用消 息调度部时，允许减少处理。图15图示了哈希函数的构造示例，在该示例中共同地使用消息调度部。提供了如下压缩函数142，在该压缩函数中，链接变量(CV)处理部CVl和CV2共同地使用一个消息调 度部(MS部)141而不是相互叠加布置并且包括在各压缩函数单元130-0至130-(η-l)中 的两个压缩函数中的消息调度部。当应用包括一个消息调度部(MS部)141的压缩函数142 的构造时，仅有必要在一个压缩函数单元140中让消息调度部(MS部)执行逻辑运算仅一 次，并且允许减少逻辑运算的必需次数。例如实现硬件配置尺寸的减少和处理步骤的简化。参照图15描述的其中多个压缩函数共同地使用消息调度部的构造适用于上述多 个哈希构造。换而言之，该构造适用于参照图5至图12描述的包括多个压缩函数的序列和 在加扰函数F中的压缩函数的压缩函数单元。[9.扩展输入消息长度的方法]接着将研究一种扩展压缩函数中的输入消息长度的方法。图16中所示压缩函数 150如参照图13描述的压缩函数120的情况那样由消息调度部(MS部)151和链接变量 (CV)处理部152构成。在上述图13中所示的压缩函数120中，用于消息调度部(MS)部121 的消息输入具有a位。另一方面，图16中所示压缩函数150包括响应于加位输入的消息 调度部151。一般而言，响应于a位输入的函数和响应于加位输入的函数互不相同，并且有必 要基于不同安全评估标准来评估它们。因此如果有可能则希望通过组合已经评估其安全特 性和性能的响应于a位输入的函数来构造响应于加位输入的消息调度部。另外，通过这样 做来允许再使用响应于a位输入的另一现有函数。后文将描述函数的具体构造示例，而现 在将描述一种利用响应于a位输入的函数来构造响应于加位输入或者更多位输入的压缩 函数的方法。图17图示了具有如下构造的压缩函数160的构造示例，在该构造中，消息调度部 分割成两个部分。消息输入(即用于压缩函数160的加位数据)分割成两个a位数据块， 然后消息调度部161和162分别进行根据a位数据块生成c位输出的处理。向一个链接变 量(CV)处理部163供应来自两个消息调度部161和162的c位输出。链接变量(CV)处理部163接收来自两个消息调度部161和162的c位输出和用 于压缩函数160的b位输入并且生成b位输出[Z]作为压缩函数的输出。该构造的一个优 点在于允许构造如下压缩函数，该压缩函数利用响应于长度比加短的a位输入的函数(消 息调度函数)来实现加位消息输入。图18中所示压缩函数170是具有如下构造的压缩函数170的构造示例，在该构造 中，消息调度部如图17中所示压缩函数160的情况那样分割成两个部分。压缩函数170包 括异或运算O(OR)部174。消息输入(即用于压缩函数170的加位数据)分割成两个a位数据块，然后消息 调度部171和172分别进行根据a位数据块生成c位输出的处理。异或运算O(OR)部174 进行在来自两个消息调度部171和172的c位输出之间的异或运算，然后向一个链接变量 (CV)处理部173施加c位输出。压缩函数170具有如下构造，在该构造中，异或运算部174暂时处理来自两个消息 调度部的输出，然后向链接变量(CV)处理部173施加输出。该构造的优点在于，由于没有 增加链接变量(CV)处理部173接收的消息的大小，所以允许简化链接变量(CV)处理部173 的内部构造。注意异或运算可以用模加法处理代替。
图19图示了通过推广图17中所示压缩函数160的构造来设置成响应于na位输入 的压缩函数210的构造示例。向压缩函数210施加的na位消息分割成η个a位消息，并且 消息调度部(MS部)211-1至211-n分别独立处理a位消息，而且消息调度部(MS部)211-1 至211-n分别生成c位输出。向链接变量(CV)处理部212施加来自消息调度部(MS部)211-1至211_n的c位 输出。链接变量(CV)处理部212接收从η个消息调度部(MS部)211-1至211_n施加的nc 位和用于压缩函数210的b位输入并且生成b位输出[Z]作为压缩函数的输出。这一构造也具有与上文参照图17描述的优点相同的优点。换而言之，允许构造如 下压缩函数，该函数利用响应于长度比na位短的a位输入的函数(消息调度部)来实现na 位消息输入。图20图示了通过推广图18中所示压缩函数170的构造来设置成响应于na位输 入的压缩函数220的构造示例。向压缩函数220施加的na位消息分割成η个a位消息，并 且响应于a位输入的消息调度部(MS部)221-1至221_n分别独立处理a位消息，并且消息 调度部(MS部)221-1至221-n分别生成c位输出。异或运算部O(OR) 223-1至223_n分别进行在来自消息调度部(MS部)221-1至 221-n的c位输出之间的异或运算，然后向一个链接变量(CV)处理部222施加c位输出。 链接变量(CV)处理部222接收来自异或运算部O(OR) 223-n的c位输出和作为用于压缩函 数220的输入的b位以生成b位输出[Z]作为压缩函数的输出。在这一构造中也允许构造 如下压缩函数，该压缩函数利用响应于长度比na位短的a位输入的函数(消息调度部)来 实现na位消息输入。注意可以使用通过将异或运算部替换为模加法处理部而形成的构造。因此，根据本发明示例实施例的数据转换器包括向其同时施加消息数据的分割数 据块的多个处理序列并且被配置成利用多个压缩函数执行部(f)来执行数据转换处理。多个压缩函数执行部(f)中的各压缩函数执行部被配置成进行利用消息调度部 (MS)的处理，其中消息调度部(MS)接收消息数据的分割数据块以对数据块进行消息调度 处理，和利用链接变量(CV)处理部的处理，其中链接变量(CV)处理部接收来自消息调度部 (MS部)的输出和作为来自前级处理部的输出的中间值(链接变量)以通过对接收的数据 进行压缩来生成位数与中间值的位数相同的输出数据。在多个处理序列中分别进行并行处理的多个压缩函数执行部共同地使用消息调 度部(MS部)和链接变量(CV)处理部中的一个或者两个并且进行利用单个消息调度部或 者单个链接变量处理部的处理。这样的构造实现硬件配置尺寸的减少和处理步骤的简化。[10.在CV处理部和MS部中使用重复的转置来实现哈希函数的方法]如上文所述，利用消息调度部(MS部)和链接变量(CV)处理部作为组成要素可实 现压缩函数。下文将描述消息调度部(MS部)和链接变量(CV)处理部的具体构造示例。一般已知基于转置函数的消息调度部(MS部)或者链接变量(CV)处理部。例如 已知为哈希函数的SHA-I或者Whirlpool具有基于转置函数的构造。向消息调度部(MS部)或者链接变量(CV)处理部施加的转置函数优选为具有高 加扰能力的转置函数。下文将描述通过重复地使用相对简单的转置函数来增强加扰能力的转置函数的 构造示例。在下文描述中，在转置函数中重复的相对简单的转置称为“内部转置”，而由此实现的转置称为“总转置”。注意转置函数是用于基于输入值生成输出值、使得输入大小和输出大小彼此相同 并且一个输入值对应于一个输出值的函数。此外，转置函数由于它的性质而具有反函数。在总转置中，可以从外部向两个内部转置处理之间的中间数据添加数据，或者可 以向函数的外部施加中间数据。在压缩函数中，利用中间数据，可以向除了总转置的原输入 部分和原输出部分之外的部分施加数据的输入或者附加数据的输出。向除了原输入部分之 外的部分施加的数据称为附加输入，而向除了原输出之外的部分施加的中间数据称为中间 输出。图21中所示转置函数(转置部)310是具有附加输入311的转置函数的示例。另 外，图22中所示转置函数(转置部)320是具有中间输出321的转置函数的示例。图21和图22中所示转置函数基于响应于a位输入/输出的总转置。在转置函数 中依次施加内部转置1至k。图21中所示转置函数310具有如下构造，在该构造中对附加 输入311与中间数据进行异或，该中间数据是将向后继内部转置部或者外部施加的内部转 置的输出值。在图22中所示转置函数320中，向外部施加作为内部转置的输出值的中间数 据作为中间输出321。下文为了区别这种类型的总转置与一般的总转置，图21中所示类型 的转置函数称为具有附加输入的转置函数，而图22中所示类型的转置函数称为具有中间 输出的转置函数。注意具有附加输入的转置函数继承转置的以下固有性质。*当附加数据固定时，一个输入对应于一个输出。另外，具有中间输出的转置函数具有从转置函数导出的以下性质。* 一个输入对应于一个中间输出。形成哈希函数的压缩函数如上文参照图13至图20所述由消息调度部(MS)部和 链接变量(CV)处理部构成。已经已知具有附加输入的转置函数用于链接变量(CV)处理部 而具有中间输出的转置函数用于消息调度部(MS部)，并且它们相互连接以构造压缩函数 (Whirlpool)。图23图示了使用现有转置函数的压缩函数330的构造示例。图23中所示压缩函 数330具有如下构造，在该构造中提供消息调度部(MS部)331作为具有中间输出的a位转 置函数并且中间输出连接到具有用于链接变量(CV)处理部332的附加输入的a位转置函 数的附加输入。在图23中所示构造中，为了简化描述，a位转置函数使用于消息调度部(MS 部)331和链接变量(CV)处理部332两者之中；然而消息调度部(MS部)331和链接变量 (CV)处理部332的转置大小并不一定彼此相等。在消息调度部(MS部)331和链接变量 (CV)处理部332的长度互不相同的情况下，可以通过适当地进行扩展和压缩运算来调节长 度。另外，不同于图23中所示情况，所有中间输出并不一定连接于消息调度部(MS部)331 与链接变量(CV)处理部332之间，并且可以考虑安全特性或者处理效率来执行比如适当地 减少中间输出的处理以选择连接于消息调度部(MS部)331与链接变量(CV)处理部332之 间的中间数据。[11.扩展MS部的大小的方法]图M图示了压缩函数的构造示例，在该示例中对要向压缩函数施加的数据大小进行扩展。图M中所示压缩函数340是其中将输入位长度扩展成3a位的压缩函数。图M 中所示压缩函数340具有与上文参照图18描述的构造相同的构造并且包括两个消息调度 部(MS部)341和342以及接收来自两个消息调度部(MS部)341和342的输出的异或运算 结果的一个链接变量(CV)处理部343。两个消息调度部(MS部)341和342各由具有中间输出的转置函数构成。一个链 接变量(CV)处理部343由具有附加输入的转置函数构成。图M中所示转置函数340具有如下构造，在该构造中，2a位输入X分割成a位块， 并且分别向两个消息调度部(MS部)341和342施加a位块，而且向一个链接变量(CV)处 理部343施加来自两个消息调度部(MS部)341和342的中间输出。当以这样的方式使用 具有附加输入的转置函数和具有中间输出的转置函数时，允许容易地增加输入长度。另外，在图M中所示转置函数340的构造中，不允许用作消息调度部(MS部)的 两个转置函数彼此相同，因为在转置函数彼此相同的情况下，当向两个转置函数施加相同a 位数据块时，对应的中间输出彼此相同，并且抵消了异或运算O(OR)的结果。因此有必要为 消息调度部(MS)准备不同的转置函数。通过使用内部转置的不同构造可实现这一点。允许通过推广图M中所示压缩函数的构造来将输入X的长度扩展为3a位或者更 多。例如通过添加消息调度部(MS部)可实现这一点。在图M中所示构造中使用一种减少吞吐量以实现加速的方法。在例如如参照图 4、图5等描述的构成哈希函数的具有多级构造的压缩函数中，要向压缩函数施加的值是作 为数据[X]的消息和作为数据Y的中间值、也就是链接变量(CV)。这时，用于消息处理的转置的重复次数并不一定等于用于链接变量(CV)序列的 转置的重复次数。例如下文将考虑在无损于安全特性的范围内将用于消息的转置的重复次 数减半的情况。图25图示了压缩函数350，在该函数中如图M中所示情况那样将输入位长度扩 展为3a位。用于压缩函数350的加位输入X分割成a位块，并且分别向两个消息调度部 (MS部)351和352施加a位块，而且向一个链接变量(CV)处理部353施加两个消息调度部 (MS部)351和352的中间输出。图25中所示两个消息调度部(MS部)351和352中的各消息调度部中的内部转置 的重复次数设置成等于链接变量(CV)处理部353中的内部转置的重复次数的一半。在消息调度部(MS部)351中，去除偶数编号的转置，而在消息调度部(MS部)352 中，去除奇数编号的转置；因此将两个消息调度部(MS部)351和352中的各消息调度部中 的内部转置的重复次数减半。通过这种构造允许将消息处理必需的运算减半。在图25中所示压缩函数350中，与图M中所示压缩函数340的构造相比较，处理 被减少。因此预期对软件处理进行改进。当在消息调度部(MS部)351和352中交替地去 除函数时，作为一个优点，允许将在硬件实施时同时被允许进行的转置次数设置成两次以 实现电路规模小的处理、也就是说，可实现硬件尺寸的减少。另外，如图25中所示情况那样，图沈中所示压缩函数360是其中输入位长度扩展 成3a位的压缩函数360。用于压缩函数360的加位输入X分割成a位块，并且分别向两个 消息调度部(MS部)361和362施加a位块，而且向一个链接变量(CV)处理部363施加两 个消息调度部(MS部)361和362的中间输出。
20CN 102138170 A
说明书
17/30 页图沈中所示压缩函数360中的链接变量(CV)处理部363具有如下构造，在该构 造中，在图25中所示压缩函数350中的链接变量(CV)处理部353前面添加一个内部转置 部364，并且内部转置的重复次数加1。在图沈中所示压缩函数360中，在用于链接变量(CV)处理部363的总转置前面 添加一个内部转置。根据这一改变，压缩函数360具有如下构造，在该构造中，上消息调度 部(MS部)361的输入值与链接变量(CV)处理部363的输入值进行异或。作为这种构造的一个特性，当关注消息调度部(MS部)之一时，链接变量(CV)处 理部363的每两个转置函数施加向链接变量(CV)处理部363施加的中间数据而无例外。 通过这种构造，对链接变量(CV)处理部363的序列同等地施加相互叠加布置的消息调度部 (MS部)361和362的影响以便实现平衡的加扰。因而有安全评估更容易的优点。[12.扩展CV处理部的大小的方法]图27中所示压缩函数370示出了如下构造，其中上文参照图15描述的形成序列 的两个压缩函数共同地使用消息调度部。当图15中呈现的域扩展方法应用于b = a的情 况时扩展了链接变量(CV)处理部的大小。在图27中所示压缩函数370中，向消息调度部(MS部)371施加作为消息[X]的 组成位的a位的输入，并且分别向链接变量(CV)处理部372和373施加作为两个链接变量 (CV)(中间值)的a位的输入。消息调度部(MS部)371由具有中间输出的转置函数构成。两个链接变量(CV)处 理部372和373各由具有附加输入的转置函数构成。设置消息调度部(MS部)371的中间 输出作为两个链接变量(CV)处理部372和373的附加输入。在两个链接变量(CV)处理部 372和373中的各处理部中对消息调度部(MS部)371的中间输出与输入或者中间值进行异 或以向内部转置部施加。可替换地，中间输入用来生成输出值。[13.扩展CV处理部和MS部的大小的方法]图28中所示压缩函数380是图27中所示压缩函数370的修改示例并且是如下压 缩函数的构造示例，其中通过与上文参照图M描述的压缩函数340的技术相同的技术来扩 展要向压缩函数施加的数据大小。图观中所示压缩函数380是其中输入位长度扩展成3a 位的压缩函数。图28中所示压缩函数380包括两个消息调度部(MS部)381和382以及接 收两个消息调度部(MS部)381和382的输出的异或O(OR)运算结果的一个链接变量(CV) 处理部383和384。两个消息调度部(MS部)381和382各由具有中间输出的转置函数构成。两个链 接变量(CV)处理部383和384各由具有附加输入的转置函数构成。提供消息调度部(MS 部)381的中间输出作为链接变量(CV)处理部383的附加输入。提供消息调度部(MS)部 382的中间输出作为链接变量(CV)处理部384的附加输入。两个链接变量(CV)处理部383 和384使用附加输入以与输入或者中间值进行异或、然后向内部转置部施加或者生成输出 值。[14.为域扩展方法构造加扰函数F的方法]加扰函数F可以由具有中间输出的转置函数与具有附加输入的转置函数构成。图 四是由具有中间输出的两个转置函数与具有附加输入的两个转置函数的组合构成的加扰 函数F390的构造示例。
加扰函数F390包括两个消息调度部(MS部)391和392以及接收来自两个消息调 度部(MS部)391和392的输出的异或运算O(OR)结果的一个链接变量(CV)处理部393和 394。两个消息调度部(MS部)391和392各由具有中间输出的转置函数构成。两个链 接变量(CV)处理部393和394各由具有附加输入的转置函数构成。提供消息调度部(MS部)391的中间输出作为链接变量(CV)处理部393的附加输 入。提供消息调度部(MS部)392的中间输出作为链接变量(CV)处理部394的附加输入。 两个链接变量(CV)处理部393和394使用附加输入以与输入或者中间值进行异或，然后向 内部转置部施加或者生成输出值。加扰函数F390接收加位作为输入[Y]并且生成加位输出[Z]。注意本发明的数 据转换器中的转置可以具有如下构造，在该构造中如上述图25和图沈中的构造的情况那 样去除一些部分。[15.实现具有高扩散能力的转置处理的方法]通过如上文所述重复地施加内部转置作为相对简单的转置函数可实现向消息调 度部(MS部)或者链接变量(CV)处理部施加的转置函数。当重复地应用这样的相对简单 的转置函数时，允许构造具有增强加扰能力的转置函数。下文将参照图30描述适用作为内部转置的转置函数的具体构造示例。图30是用 于构造具有高加扰能力的重复型转置函数、作为在执行总转置的转置函数中使用的内部转 置的转置函数的构造示例。通过重复和依次地施加内部转置来构成总转置。图30中的内 部转置部(转置函数)410具有其中进行256位输入/输出转置的构造。向内部转置部(转置函数)410施加的256位数据由32字节数据代表。各字节对 应于附图中所示一条输入数据线。首先将数据分割成4字节(32位)数据块、也就是从左侧起的八组(Gl至G8)。在 相应的对应非线性转换部411中对从左侧起的奇数编号组(G1、G3、G5和G7)中包括的4字 节的数据进行非线性转换处理。当从非线性转换部411生成四组(G1、G3、G5和G7)中的各组中的4字节(32位) 数据时，异或O(OR)运算部412执行4字节(32位)数据与其右侧上的一组中的4字节数 据的异或运算以更新四个偶数编号组(G2、G4、G6*G8)中的各组中的4字节(32位)数据。换而言之，通过以下处理更新四个偶数编号组(G2、G4、G6和G8)中的各组中的4 字节(32位)数据执行在对组(Gl)中的4字节数据的非线性转换结果的数据与组(G2)中的输入数 据之间的异或运算，执行在对组(G3)中的4字节数据的非线性转换结果的数据与组(G4)中的输入数 据之间的异或运算，执行在对组(G5)中的4字节数据的非线性转换结果的数据与组(G6)中的输入数 据之间的异或运算，并且执行在对组(G7)中的4字节数据的非线性转换结果的数据与组(G8)中的输入数 据之间的异或运算。
接着在互换部413中进行对各1字节数据的互换处理。移动包括从非线性转换部 411生成的数据的四组(G1、G3、G5和G7)，使得最左组移向最右组的位置，并且其它组分别 移向其紧接左侧上的组的位置。换而言之，用以下方式执行互换处理以生成数据向输出组(GoirtS)的位置施加组(Gl)，向输出组(Gout2)的位置施加组(G3)，向输出组(Gout4)的位置施加组(G5)，并且向输出组(Goute)的位置施加组(G7)，另一方面，异或O(OR)运算部412进行如下互换处理，该处理将通过执行异或运算 来更新的四个偶数编号组(G2、G4、G6和G8)中的各组中的4字节(32位)数据分割成1字 节数据块并且分别将1字节数据块移向不同组。对组(G》中的4字节数据进行以下互换处理。将组(6 的4字节数据分割成来 自第一 1字节数据块的由A、B、C和D代表的1字节数据块。用以下方式执行互换处理以生成数据生成组(G2)中的第一 1字节数据块A作为输出组(Goutl)中的第一 1字节数据 块，生成组(G2)中的第二 1字节数据块B作为输出组(Gout3)中的第二 1字节数据 块，生成组(G2)中的第三1字节数据块C作为输出组(Gout5)中的第三1字节数据 块，并且生成组(G2)中的第四1字节数据块D作为输出组(Gout7)中的第四1字节数据 块，对组(G4)中的4字节数据进行以下互换处理。组(G4)的4字节数据分割成来自第一 1字节数据块的由E、F、G和H代表的1字 节数据块。用以下方式执行互换处理以生成数据生成组(G4)中的第一 1字节数据块E作为输出组(Gout3)中的第一 1字节数据 块，生成组(G4)中的第二 1字节数据块F作为输出组(Gout5)中的第二 1字节数据 块，生成组(G4)中的第三1字节数据块G作为输出组(Gout7)中的第三1字节数据 块，并且生成组(G4)中的第四1字节数据块H作为输出组(Goutl)中的第四1字节数据 块，对组(G6)中的4字节数据进行以下互换处理。组(G6)的4字节数据分割成来自第一 1字节数据块的由I、J、K和L代表的1字 节数据块。用以下方式执行互换处理以生成数据生成组(G6)中的第一 1字节数据块I作为输出组(Gout5)中的第一 1字节数据块，生成组(G6)中的第二 1字节数据块J作为输出组(Gout7)中的第二 1字节数据 块，生成组(G6)中的第三1字节数据块K作为输出组(Goutl)中的第三1字节数据 块，并且生成组(G6)中的第四1字节数据块L作为输出组(Gout3)中的第四1字节数据 块。对组(G8)中的4字节数据进行以下互换处理。组(G8)的4字节数据分割成来自第一 1字节数据块的由M、N、0和P代表的1字 节数据块。用以下方式执行互换处理以生成数据生成组(G8)中的第一 1字节数据块M作为输出组(Gout7)中的第一 1字节数据 块，生成组(G8)中的第二 1字节数据块N作为输出组(Goutl)中的第二 1字节数据 块，生成组(G8)中的第三1字节数据块0作为输出组(Gout3)中的第三1字节数据 块，并且生成组(G8)中的第四1字节数据块P作为输出组(Gout5)中的第四1字节数据 块。注意在后继回合中的内部转置部(转置函数)中向非线性转换施加输出组 (GoutK Gout3λ Gout5 禾口 Gout7)。因此，当执行互换输入和输出的互换处理时，保证在各回合中执行对各字节数据 的不同种类的转换处理。如图30中的内部转置部(转置函数)410的输出部中所示，32字节输出分别由xl 至x32代表。例如，图22中所示具有中间输出的转置函数中的中间输出对应于这些输出。 换而言之，参照图23至27描述的压缩函数和加扰函数F的各构造中的消息调度部(MS部) 由具有中间输出的转置函数构成，并且这些输出对应于从消息调度部(MS部)生成的中间 输出。在图21中所示具有附加输入的转置函数中施加中间输出作为附加输入。例如参 照图23至27描述的压缩函数和加扰函数F的各构造中的链接变量(CV)处理部由具有附 加输入的转置函数构成，并且施加来自图30中所示内部转置部(转置函数)410的输出部 的32字节输出xl至x32作为链接变量(CV)处理部的附加输入。注意向如参照图23至图27描述的压缩函数或者加扰函数F的内部提供大量图30 中所示内部转置部(转置函数)410的构造。可以使用由内部转置部(转置函数)生成的 中间数据的所有输出值xl至x32，或者可以使用输出值xl至x32中的仅一些输出值。例如在图30中所示内部转置部(转置函数)410的构造中，可以仅使用来自非线 性转换部411的输出值x5至x8、xl3至xl6、x21至xM和口9至义32作为中间输出。可替 换地，可以仅使用要向后继转置函数中的非线性转换部施加的输出值xl至x4、x9至xl2、 xl7至x20和x25至x28作为中间值。
接着下文将参照图31描述参照图30描述的内部转置部(转置函数)410中的非 线性转换部411的内部构造的示例。允许将非线性转换部411构造作为接收4字节数据并 且生成4字节数据的转置函数。图31中所示非线性转换部411接收4字节数据。图31中所示一条线对应于1字 节数据块。在异或O(OR)运算部421中，接收的数据分别与非线性转换部411中预定的四 个常值(常数)C1、C2、C3和C4进行异或。注意在参照图30描述的内部转置部(转置函 数)410中包括四个非线性转换部411，并且这四个非线性转换部具有不同的常值(常数)。 后文将描述一种设置常值(常数)的处理。接着，小型非线性转换部422对在异或O(OR)运算部421中分别与非线性转换部 411中预定的四个常值(常数)C1、C2、C3和C4异或的数据执行1字节输入/输出非线性 转换处理。向线性转换部423施加小型非线性转换部422的输出，并且对输出进行线性转换 以生成输出。注意这里描述的小型非线性转换部422有时称为S框(S-box)并且可以表示 为用于256条1字节数据的转换表。另外执行线性转换部423作为一种通过利用线性转换 矩阵(M)对输入数据的转换处理来计算输出数据的处理。线性转换矩阵(M)也称为扩散矩 阵并且有时表示为具有GFQ8)个元素的4X4矩阵。在转置函数中希望在施加某些数据对尽可能多的数据的影响之时只要有可能就 防止输入/输出中包括的非零元素总数达到低水平。这对提高抗分析性和消除弱点是有效 的。具体而言，这是一种防范差分攻击或者线性攻击的措施。如参照图23至图27所述，为压缩函数或者加扰函数F提供大量图30中所示内部 转置部(转置函数)410的构造。换而言之，一种将图30中所示内部转置部(转置函数)410 重复多个回合的处理。大量加密算法具有执行如下回合操作的构造，在该操作中将相同转置处理重复多 个回合，并且已知作为一种防范弱点的措施，使用如下所谓DSM(扩散切换机制)是有效的， 在该机制中使用多个不同矩阵如两个矩阵[Ml]和[M2]而不是一个固定矩阵作为应用于每 个回合中的线性转换矩阵[M]。注意例如在本发明申请人的第2007-199156号日本未审查 专利申请公开中描述了一种使用DSM的加密算法。认为DMS克服弱点的效果在哈希函数中也有效。换而言之，当使用多个不同矩阵 而不是一个固定矩阵作为应用于所有回合的线性转换矩阵[M]时，哈希函数更加不可区别 于随机函数，并且也允许增强各种分析处理的难度。图32图示了为了使用多个不同矩阵作为在为压缩函数或者加扰函数F提供的多 个图30中所示内部转置部(转置函数)410的非线性转换部411中使用的线性转换矩阵 [M]而设置的内部转置部的重复回合的构造示例。图32是为压缩函数或者加扰函数F提供的多个图30中所示内部转置部(转置函 数)的两个回合的组合构造的简化图示。内部转置部(转置函数)440具有与图30中所示 内部转置部(转置函数)410相同的构造。内部转置部(转置函数)450表示执行后继内部 转置的一个回合。各输入线对应于4字节数据。如图30中所示内部转置部(转置函数)410的情况那样，内部转置部(转置函 数)440包括非线性转换部441、异或运算O(OR)部442和互换部443。非线性转换部441具有参照图31描述的构造。如参照图31所述，非线性转换部441包括异或运算部、小型非线性转换部和线性 转换部。线性转换部利用线性转换矩阵M来执行线性转换处理。在图32中图示了作为非线性转换部441提供的用于4字节数据的四个非线性转 换处理部，并且各处理部具有参照图31描述的构造。在图32中，在四个非线性转换部的线 性转换部中使用的线性转换矩阵M从左侧起分别由Ml、M2、M3和M4代表。线性转换矩阵 M1、M2、M3禾口 M4互不相同。回合中的内部转置部(转置函数)440和450具有相同构造。换而言之，在两个内 部转置部(转置函数)440和450中，在四个非线性转换部的线性转换部中使用的线性转换 矩阵M从左侧起是Ml、M2、M3和M4。因此，相同矩阵使用于内部转置中的相同位置。根据在图32中所示回合之间连接的线(粗线)理解，在上回合中的内部转置部 (转置函数)440中的非线性转换的输出与在下回合中的转置部(转置函数)450的一个非 线性转换的输出进行异或。例如来自上回合中的内部转置部(转置函数)440的非线性转换部441中的最左 侧上、具有线性转换矩阵Ml的非线性转换部441的输出(附图中的输出A)在异或运算部 452中与来自下回合中的内部转置部(转置函数)450的非线性转换部451中最右侧上的具 有线性转换矩阵M4的非线性转换部451d的输出(附图中的输出B)进行异或。该结果的 输出是附图中所示输出C。来自上回合中的内部转置部(转置函数)440的非线性转换部441的四个非线性 转换部的各输出与来自下回合中的内部转置部(转置函数)450中的非线性转换部451的 四个非线性转换部的输出之一进行异或。进行异或的来自上回合中的非线性转换部441的输出与来自下回合中的非线性 转换部451的输出的组合作为各非线性转换部中的线性转换矩阵[M]的组合示出如下。(I)Ml和M4(非线性转换部441a和45Id)(2)M2和Ml (非线性转换部441b和451a)(3)M3和M2(非线性转换部441c和451b)(4)M4和M3(非线性转换部441d和451c)当使用不同线性转换矩阵来执行线性转换处理的结果相互作用时，可设想一种使 用上述DSM(扩散切换机制)的构造以便增加抗分析性。注意两个矩阵的连接由符号“ I，，代表，并且当选择和使用为了增加分支数目(至 例如3个或者更多)而设置的矩阵作为上述矩阵对(1)至⑷(即Ml |M4、M2|M1、M3|M2和 M4|M3)时，允许进一步增加抗分析性。可替换地，使用如下构造，在该构造中通过对准将其 逆矩阵反转而获得的矩阵来获得的矩阵Ir11 tM^1, ^2"11 tMrW I ^2"1和tMf1113—1的分 支数目为3个或者更多。允许这样的增加分支数目的构造来提高对差分攻击或者线性攻击抗性。因此，为作为重复的回合操作而执行的内部转置部(转置函数)中的非线性转换 部提供的线性转换部优选地具有一种利用DSM构造来使用不同矩阵的构造。另外，优选地 设置要使用的矩阵使得增加包括相互作用的成对矩阵的组合矩阵的分支数目。在参照图32的描述中使用四个矩阵；然而可以用两个矩阵满足用于分支数目的相同条件。例如，如图33中所示，可以使用如下构造，在该构造中，布置矩阵使得M1|M2的 分支数目是3或者更多，或者通过对准将逆矩阵反转而获得的矩阵来获得的矩阵1Γ11 ^2-1 的分支数目是3或者更多。在图33中所示构造中，异或的来自上回合中的非线性转换部441的输出与来自下 回合的非线性转换部451的输出的组合作为各非线性转换部中的线性转换矩阵[M]的组合 示出如下。(I)Ml和M2(非线性转换部461a和47Id)(2)M2和Ml (非线性转换部461b和471a)(3) Ml和M2(非线性转换部461c和471b)(4)M2和Ml (非线性转换部461d和471c)图33中所示构造在实施方面被视为更优选的构造，因为允许减少矩阵所必需的 硬件电路和存储器上的表大小。当使用不同线性转换矩阵来执行线性转换处理的结果相互作用时，可实现一种使 用上述DSM(扩散切换机制)的构造，并且允许增加抗分析性。上文描述了用于实现具有增强加扰能力的总函数的内部转置的构造示例。描述上 述处理示例作为其中使用256位输入的示例；然而这仅为示例并且可以不同地设置数据大 小并且可以提供视数据大小而定的构造。在这种情况下，设置该构造以根据小型非线性转 换部的输入/输出大小和线性转换部的大小来进行处理。[16.生成具有高度独立输出的转置函数的方法]在上述处理示例中，描述为压缩函数或者加扰函数F提供的多个内部转置处理构 造作为如下处理示例，在该示例中使用图30中所示内部转置处理构造并且设置该构造以 重复多次。允许例如通过以上述方式在内部转置处理的非线性转换部中构造线性转换处理 矩阵来增加抗分析性。在一种需要多个总转置函数的构造中，在一些情况下，通过使用独立作用的多个 总转置来增加抗分析性。在这种情况下有一种通过使用总转置中包括的不同内部转置来实 现该构造的方法。下文将描述构造示例。为了实现多个不同总转置处理，一种改变总转置中的内部转置中包括的部分的技 术是有效的。然而在安全评估处理的实施效率或者容易方面，并不一定希望使用大量不同 部分。优选利用尽可能少的部分来实现各种处理。作为一种用于分别对总转置进行不同内部转置处理的构造，例如考虑以下构造。*用随着总转置而不同的常值转置要使用(使用于图31中的异或运算部中)的常值。*S框(图31中的小型非线性转换部422)或者线性转换矩阵(图31中的线性转 换部42 (这些S框或者线性转换矩阵是包括在总转置中的内部转置处理的部分)随着总 转置而不同，并且重复地使用它们以实现总转置。注意常值是向参照图30和图31描述的内部转置部410的非线性转换部411的异 或O(OR)运算部421供应的常数。然而为了随着总转置而彻底改变常值或者改变S框或者矩阵，有必要供应不同数 据或者不同部分构造，因而有必要增加电路或者存储器容量。这样的电路或者存储器容量增加引起比如实施上的缺点和安全再评估的成本增加这样的问题。因此，在本发明中，根据以下构造来将用于总转置的内部转置处理构造设置为互 不相同。(a)在使用多个不同小型非线性运算(S框)(图31中的小型非线性转换部422) 的情况下，随着总转置而改变内部转置的小型非线性运算(S框)。(b)将线性转换部(图31中的线性转换部423)中使用的矩阵设置成由一个矩阵 生成的多个不同矩阵，并且将内部转置的矩阵设置成随着总转置而不同的矩阵。例如通过 转置行或者列由一个矩阵生成多个不同矩阵。(c)在使用多种矩阵作为线性转换部(图31中的线性转换部423)中使用的矩阵 的情况下，随着总转置而对内部转置的矩阵进行转置。(例如在使用上述DSM的情况下，在 不脱离DSM条件的范围内改变。)(d)上述构造(a)至(C)中的两个或者更多构造的组合。允许高效地改变设置成任何上述构造并且重复地执行的内部转置处理中的转置 处理构造。换而言之，允许执行不同转置处理而不增加电路规模或者存储器容量。具体而言，通过上述构造(C)与(b)的组合可高效地实现不同总转置。换而言之， 在利用上述DSM构造在存储器中存储两种或者更多种线性转换矩阵的情况下，转置这些矩 阵的行和列以生成和使用新矩阵作为线性转换矩阵。在这样的构造中，允许基于少量数据 来高效地进行不同线性转换处理。在一种使用DSM并且包括多个不同线性转换矩阵的构造中，在对矩阵的行和列进 行转置的情况下的安全评估是一个问题，但是已知当使用具有预定规则的矩阵如循环矩阵 或者Hadamard(哈达马)矩阵时，使用通过转置行和列来生成的矩阵不影响安全评估。因 此认为安全评估是容易的并且该构造是用于通过简单的改变来生成不同转置函数的有效 手段。[17.生成向转置函数施加的常数的处理]如上文所述，作为一种随着回合改变转置处理构造的技术，每个回合或者每两个 或者更多回合将常数(在图31中的异或运算部421中使用的[C])转置成不同常数的技术 是有效的。然而需要有大存储器容量以维持与大量回合对应的常数。下文将描述如下构造示 例，在该示例中允许由少量常数高效地生成并且在转置函数中使用大量不同常数。首先定义转置函数所需要的常数。这里4个字节统称为1个字。例如图30中所示 内部转置部(转置函数)410包括四个非线性转换部，并且各非线性转换部具有图31中所 示构造。如图31中所示，四个常数用于一个非线性转换部411。各常数用于与1字节输入 数据的异或运算，因而一个常数Cn为1字节数据。一个非线性转换部411使用四个常数， 因此每个非线性转换需要1个字的常数。图30图示的内部转置部(转置函数)410包括四个非线性转换部，因此对于一个 内部转换处理，需要4个字的常数。在通过重复k次该基本转置来构造总转置的情况下，需 要共计4k字的常数。在k个内部转置中，在从输入侧起的第i个内部转置中包括的第j个常值由Cq 代表。因此允许将一次总转置所需的常数表示如下。
( 一次总转置所需的成组常数的示例)第--内部转置= C1,1，C1,2，C1,3，C
第二二内部转置:C2,1，C2,2，C2,3，C;
第三三内部转置=C3,1，C3,2，C3,3，C;
第四内部转置:C4,1，2，3，C,第k-Ι 内部转置=C1^1, Ck-U, Ck^1,3, Cn4第k 内部转置=Cu, Ckj2, Ckj3, Ck,4作为公开常数生成技术的有关技术，例如在第2008-58827号日本未审查专利申 请公开中描述了一种技术。在该有关技术中，作为一种生成64位常数的方法，使用8位变 量中存储的值8次来生成常数，并且通过对该变量中的视为GFQ8)的元素的值进行χ或者 χ—1倍乘以依次地增加数据种类来生成后继常数。注意在定义要使用的有限场GFQn)的不 可约分多项式由多项式f(x)代表时，这里使用的χ是变量χ。下文将描述一种基于通过对用于生成常数的数据的χ倍乘而获得的级数来生成 一些常数并且基于通过X—1倍乘X而获得的级数来生成其余常数的方法作为一种常数生成 处理构造。允许局部地干扰常数之间的简单关系而不增加通过该方法生成常数的工作量。 结果，允许增加常数的随机性。将利用由一个16位值生成与两个字对应的64位的示例来 描述该示例。将与在上述有关技术(第2008-58827号日本未审查专利申请公开)中公开的常 数生成处理相比较来描述根据本发明的常数生成处理。首先下文将描述有关技术中的常数生成步骤。有关技术中的常数生成步骤如下[1]在16位变量S中存储初始值。[2]对i = 1···1 进行以下处理。(2. DCia = (S XOR 掩码》< < < Rot11 (S XOR 掩码 2) < < < Rot2Ci,2 = (S XOR 掩码 3) <<< Rot3I (S XOR 掩码 4) <<< Rot4Ci,3 = (S XOR 掩码 5) <<< Rot51 (S XOR 掩码 6) <<< Rot6Ci,4 = (S XOR 掩码 7) <<< Rot71 (S XOR 掩码 8) <<< Rot8(2. 2) S — S · χ注意掩码η和Rotn是单独确定的常数。这里符号“ I ”代表位的连接。(AX0R B)代 表A与B的异或运算O(OR)处理。在一些情况下，以这样的方式生成的四个常数(Ciil至Ci,4)看似随机数；然而仅通 过掩码运算和旋转移位运算来改变常数，因而常数具有如下特性即使S为任何值，常数仍 然一致地保持由具体线性运算代表的关系。通过作为示例的块加密清楚的是仅通过线性转 换来增加随机性经常是不够的，而且希望让常数具有尽可能非线性的性质。接着下文将描述一种根据本发明通过在常数之间引入非线性关系来生成常数而 不增加实施成本和降低性能的技术。[1]在各16位变量S和T中存储初始值[2]对i = 1···1 进行以下处理。(2. DCia = (S XOR 掩码》<<< Rot11 (S XOR 掩码 2) <<< Rot2
Ci,2 = (S XOR 掩码 3) <<< Rot3I (S XOR 掩码 4) <<< Rot4Ci,3 = (T XOR 掩码 5) <<< Rot51 (T XOR 掩码 6) <<< Rot6Ci,4 = (T XOR 掩码 7) <<< Rot71 (T XOR 掩码 8) <<< Rot8(2. 2)S 一 S · χ, T 一 T · χ-1当根据上述处理利用16位变量S和T来生成四个常数(Ciil至Ci,4)时，在各内部 转置中包括的四个常数的一半属于X倍乘级数，而另一半属于X—1倍乘级数。通过这样的构造，没有保持在由S生成的常数与由T构成的常数之间的固定线性 关系，并且获得提高独立性的效果。当一般地描述上述常数生成处理时，常数生成处理是一种用具有不同指数如Xa和 Xb的值来更新初始值S和T的处理。当利用这样的变量S和T来生成多个常数时，生成的 常数的一半属于Xa倍乘级数，而另一半属于Xb倍乘级数。注意除了基于S和T的两个级数之外，当可接受增加初始值的数目时，可以使用一 种利用三个或者更多级数来生成常数的构造。[18.为多个总转置生成常数的方法]压缩函数包括多个总转置，并且需要准备由用于相应总转置的多个常数构成的成 组常值。当总转置的数目为m时，总转置分别由Ρ1、Ρ2···、Κιι代表。当使用上述常数生成技 术时，一种根据总转置的数目m随着总转置而改变m组初始值以生成向总转置中的内部转 置应用的常值是适用的。然而使用这样的技术，使得用于生成常值的工作量增加了 m倍，因 而它并不高效。下文将描述一种简化用于施加多个总转置的常数组的生成处理的技术。例如在压 缩函数中包括m个总转置的情况下，通过上述使用多个初始值S和T的方法来生成第一总 转置所需的常数，并且通过对为第一总转置生成的常数的简单运算来生成要向第二和后面 的总转置应用的常数。在一种数据转换处理构造(例如在构造中为压缩函数提供m个总转置的构造) 中，在从第X总转置的输入侧起的第i内部转置中包括的第j常值(字)由Cij(X)代表。 通过上述使用多个初始值S和T的方法来生成用于第一总转置的常数Cij(I)。这时生成用于第二和后面的总转置的常数Cu(2)、CU(3)、…、Cij(Hi)。下文将参照 图34描述一种生成用于第二和后面的总转置的常数Cij O)、Cij (3)、…、Cij(Hi)的技术。图34图示了通过上述使用多个初始值S和T的方法来生成的第一常数组480以 及通过对第一常数组480的转换处理来生成的第二常数组481、第三常数组482和第m常数 组483作为m个总转置所需的常数组。设置所有m个总转置为如下示例，在该示例中，在各总转置中包括k个内部转置并 且对于各内部转置需要四个常数字。通过对第一常数组480的转换处理来生成第二至第m常数组。下文将描述转换处 理的具体示例。作为转换处理，以下三种转换处理中的任一种可适用。(转换处理示例1)生成常数为Ciij(X) =Ciij(I) <<<Rx，其中在各总转置中确定的不同旋转量为 Rx。Ciij(I)是如下常数，该常数作为通过上述使用多个初始值S和T的方法生成的第一常数组480中的元素。另外，χ是常数组的标识号并且具有2至m的值。(转换处理示例2)生成常数为Cm(X) =Cio-(I)XOR Mx，其中在各总转置中确定的不同掩码值(字) 为Mx。Cm(I)是如下常数，该常数作为通过上述使用多个初始值S和T的方法生成的第一 常数组480中的元素。另外，χ是常数组的标识号并且具有2至m的值。(转换处理示例3)该方法组合上述转换处理示例1与示例2。生成常数为Ciij (χ) = (Cijj(I) <<< Rx)XOR Mx 或者 Ciij(X) = (Cijj(I)XOR Mx) <<<Rx。Cm(I)是如下常数，该常数作为通过上述使用多个初始值S和T的方法生成的 第一常数组480中的元素。另外，χ是常数组的标识号并且具有2至m的值。允许利用上述转换处理示例1至示例3中的任何示例、由一个常数组生成多个不 同常数组，并且设置常数组作为向相应总转置应用的常数。注意在上述转换处理示例1的情况下可保证除非Ciij(I)具有特殊位模式，否则在 用于任意X和y的Cq(X)与Cu(y)之间的异或运算的结果非0;因此允许构造不同总转 置。另外在上述转换处理示例2的情况下也可保证异或运算的结果非0 ；因此该处理示例 也适合于生成不同总转置。此外，在上述转换处理示例中表明的旋转量和掩码值使用各总转置中确定的值； 然而在如下构造中预期有相同效果，在该构造中为旋转量和掩码值提供多个值并且使用这 些值作为旋转量和掩码值以生成一个总转置所需的多个常值。当提供用于第一旋转函数的成组常值时，通过使用这些方法来允许以少量处理成 本生成用于不同转置函数的成组常值；因此预期有更快的处理。具体而言，在程序执行功能(也就是软件)安装于数据转换器中的情况下适用如 下编程模式，在该模式中在必要时动态地生成而不在存储器上暂时地解压用于所有总转置 的成组常值，因而预期提高存储器使用效率。在上述示例中描述其中随着字进行旋转运算的示例；然而可以修改旋转操作以每 两个或者更多字进行该操作并且预计与上述效果相同的效果。[19.减少哈希函数的输出值的技术]接着将描述数据转换器的配置示例，在该示例中，在哈希值生成处理构造中准备 用于生成η位哈希值的函数并且将输出的位数减少k位，从而允许生成n-k位哈希值。例如准备具有256位输出的哈希函数并且将输出的位数减少32位以生成2M位 哈希函数。图35图示了与图30中所示内部转置部(转置函数)410的构造相同的构造并且 图示了总转置的最后一级中的内部转置处理构造。输出71至78是来自总转置的输出并且 代表作为哈希函数的输出的哈希值。在图35中简化1个字G个字节)的数据线并图示为 一条数据线。所有输出Y1至y8合计为4X8 = 32字节=256位的输出。为了简化描述，在输出之前没有立即进行在异或运算之后转置数据的处理。另外 在输出之前立即要与数据级数异或的数据Xi代表前馈的数据并且由作为向压缩函数施加 的中间值的链接变量或者消息构成。考虑一种从作为输出的η位数据中删除作为删除数据的k位数据以减少输出数据的长度的方法。有必要从附图中的输出级数71至78中选择位长度要减少的数据级数。作 为一种方法，有一种从左侧起将位长度依次地减少k位的方案。在这种情况下考虑以下问 题。在k位超过从左侧起的两条数据线的总大小的情况下，当校验作为长度减少结果的输 出数据时，对最左侧的线性转换处理的结果对其余输出的任何位没有影响。这表明对这一 部分的计算是不必要的。作为为了消除这样的不必要处理而没有大量地减少具体数据级数的长度的技术， 下文将描述以下两个处理技术。(数据长度减少技术1)输出数据级数的数目为m，而要减少的位数(删除的位数)为k。为了尽可能均勻 地将k位划分为m个，通过以下数学表达式来计算参数a和b。[数学表达式1]
权利要求
1.一种数据转换器，包括数据转换部，接收消息数据以生成哈希值，所述数据转换部被配置成在并行地处理构 成所述消息数据的分割数据块的多个处理序列中，执行利用多个压缩函数执行部的数据转 换处理，其中所述多个压缩函数执行部中的各压缩函数执行部被配置成进行以下处理利用消息调度部的处理，所述消息调度部接收所述消息数据的对应分割数据块以进行 消息调度处理；以及利用链接变量处理部的处理，所述链接变量处理部接收来自所述消息调度部的输出和 作为来自前级处理部的输出的中间值以通过对接收的数据进行压缩来生成位数与所述中 间值的位数相同的输出数据，并且在所述多个处理序列中分别进行并行处理的所述多个压缩函数执行部被配置成共同 地使用所述消息调度部和所述链接变量处理部中的一个或者两个并且允许利用单个消息 调度部或者单个链接变量处理部。
2.根据权利要求1所述的数据转换器，其中在所述多个处理序列中分别进行并行处理的所述多个压缩函数执行部包括由所述多 个压缩函数执行部共同地使用的单个共同消息调度部，所述共同消息调度部被配置成接收构成所述消息数据的所述分割数据块、通过对所述 分割数据块进行所述消息调度处理来生成输出数据并且将所生成的输出数据输出到多个 链接变量处理部，并且所述多个链接变量处理部中的各链接变量处理部被配置成并行执行如下处理，在各所 述处理中对应的链接变量处理部接收来自所述共同消息调度部的输出和作为来自前级压 缩函数执行部的输出的中间值来对接收的数据进行压缩，以由此生成位数与所述中间值的 位数相同的输出数据。
3.根据权利要求1所述的数据转换器，其中在所述多个处理序列中分别进行并行处理的所述多个压缩函数执行部包括由所述多 个压缩函数执行部共同地使用的单个共同链接变量处理部，在进行并行处理的所述多个压缩函数执行部中的各压缩函数执行部中提供的多个消 息调度部被配置成接收所述消息数据的相同的分割数据块、通过消息调度处理来生成输出 数据并且将所生成的输出数据输出到所述共同链接变量处理部，并且所述共同链接变量处理部被配置成接收所述多个消息调度部的输出和作为来自前级 压缩函数执行部的输出的中间值来对接收的数据进行压缩，以由此生成位数与所述中间值 的位数相同的输出数据。
4.根据权利要求3所述的数据转换器，其中在进行并行处理的所述多个压缩函数执行部中的各压缩函数执行部中提供的所述多 个消息调度部被配置成接收所述消息数据的相同的分割数据块、通过消息调度处理来生成 输出数据并且将所生成的输出数据的异或运算输出到所述共同链接变量处理部。
5.根据权利要求1所述的数据转换器，其中所述消息调度部由具有中间输出的转置函数执行部配置，所述转置函数执行部重复地 执行转置处理以输出作为各所述转置处理的结果的中间值，并且所述链接变量处理部被配置成包括具有附加输入的转置函数执行部，所述转置函数执 行部利用从具有中间输出的所述转置函数执行部输出的所述中间值作为附加输入来重复 地执行转置处理。
6.根据权利要求5所述的数据转换器，其中所述链接变量处理部被配置成利用异或结果作为用于随后的所述转置处理的输入数 据，所述异或结果是在从具有中间输出的所述转置函数执行部输出的所述中间值与前级中 的转置处理的结果之间的异或运算的逻辑值。
7.根据权利要求5所述的数据转换器，其中所述转置函数执行部执行的各所述转置处理包括对输入数据的部分或者全部进行的 非线性转换处理和作为数据互换处理的交换处理。
8.根据权利要求7所述的数据转换器，其中所述非线性转换处理是包括使用常数的异或运算、非线性转换和使用线性转换矩阵的 线性转换的处理。
9.根据权利要求7所述的数据转换器，其中在所述转置函数执行部执行的各所述转置处理中进行的线性转换处理是利用多个不 同矩阵根据DSM(扩散切换机制)执行的处理。
10.根据权利要求5所述的数据转换器，其中所述转置函数执行部执行的所述转置处理被配置成分别利用互不相同的多个常数组 来进行数据处理，并且通过对基本组进行的数据转换处理来生成的互不相同的所述多个常数组分别使用于 所述转置处理中，所述基本组定义为在一个转置处理中要使用的常数组。
11.根据权利要求10所述的数据转换器，其中作为所述基本组利用的所述常数组由通过向互不相同的多个初始值S和T应用转换规 则来生成的多个常数配置，并且所述转换规则被配置成包括对所述初始值进行的更新处理，所述更新处理由以下表达 式代表S — S · xa，T — T · X其中a乒b。
12.根据权利要求10所述的数据转换器，其中对所述基本组进行的所述数据转换处理是允许对构成所述基本组的各常数的位旋转 操作的处理或者允许在构成所述基本组的各常数与预定掩码数据之间的逻辑运算的处理。
13.根据权利要求1所述的数据转换器，其中所述数据转换部被配置成进行允许最终输出的哈希值在位数上减少的减少处理，并且根据预定计算表达式来计算在构成所述数据转换部的输出的多个输出数据级数中的 各级数的输出位中的将减少的位数，然后根据所述计算的结果来执行所述减少处理。
14.根据权利要求1所述的数据转换器，其中所述数据转换部还包括对输入数据执行数据加扰处理的加扰处理部，所述多个压缩函数执行部被配置为被允许接收所述消息数据的所有分割数据块的多 级压缩部，所述多级压缩部中的一些压缩部被配置成接收所述加扰处理部的输出和所述消息数 据的所述分割数据块这两者以基于接收的数据来执行所述数据压缩处理，所述多级压缩部中的一些压缩部被配置成接收前级压缩部的输出和所述消息数据的 所述分割数据块这两者以基于接收的数据来执行所述数据压缩处理，并且位于所述多级压缩部的最后一级中的压缩部被配置成输出所述消息数据的哈希值。
15.一种数据转换方法，是由数据转换器执行的数据转换处理方法，所述数据转换方法 包括数据转换步骤，通过数据转换部接收消息数据以生成哈希值，所述数据转换步骤是在 并行地处理构成所述消息数据的分割数据块的多个处理序列中，执行利用多个压缩函数执 行部的数据转换处理的步骤，其中所述多个压缩函数执行部中的各压缩函数执行部进行利用消息调度部的处理，所述消息调度部接收所述消息数据的对应分割数据块以进行 消息调度处理；以及利用链接变量处理部的处理，所述链接变量处理部接收来自所述消息调度部的输出和 作为来自前级处理部的输出的中间值以通过对接收的数据进行压缩来生成位数与所述中 间值的位数相同的输出数据，并且在所述多个处理序列中分别进行并行处理的所述多个压缩函数执行部共同地使用所 述消息调度部和所述链接变量处理部中的一个或者两个并且进行利用单个消息调度部或 者单个链接变量处理部的处理。
16.一种在数据转换器中执行数据转换处理的程序，所述程序包括数据转换步骤，通过数据转换部接收消息数据以生成哈希值，所述数据转换步骤是在 并行地处理构成所述消息数据的分割数据块的多个处理序列中，执行利用多个压缩函数执 行部的数据转换处理的步骤，其中所述程序允许所述多个压缩函数执行部中的各压缩函数执行部执行 利用消息调度部的处理，所述消息调度部接收所述消息数据的对应分割数据块以进行 消息调度处理；以及利用链接变量处理部的处理，所述链接变量处理部接收来自所述消息调度部的输出和 作为来自前级处理部的输出的中间值以通过对接收的数据进行压缩来生成位数与所述中 间值的位数相同的输出数据，并且所述程序允许在所述多个处理序列中分别进行并行处理的所述多个压缩函数执行部 共同地使用所述消息调度部和所述链接变量处理部中的一个或者两个并且进行利用单个 消息调度部或者单个链接变量处理部的处理。
全文摘要
实现一种具有改进的压缩函数执行部的构造。在并行地处理构成所述消息数据的分割数据块的多个处理序列中，执行利用多个压缩函数执行部的数据转换处理。多个压缩函数执行部中的各压缩函数执行部进行利用消息调度部的处理和利用链接变量处理部的处理，该消息调度部接收消息数据的对应分割数据块以进行消息调度处理，该链接变量处理部接收来自消息调度部的输出和作为来自前级处理部的输出的中间值以通过对接收的数据进行压缩来生成位数与中间值的位数相同的输出数据。分别进行并行处理的多个压缩函数执行部共同地使用消息调度部和链接变量处理部中的一个或者两个并且允许利用单个消息调度部或者单个链接变量处理部。通过这样的构造实现硬件配置尺寸的减少和处理步骤的简化。
文档编号G09C1/00GK102138170SQ20098013229
公开日2011年7月27日 申请日期2009年8月25日 优先权日2008年8月25日
发明者岩田哲, 涩谷香士, 白井太三, 盛合志帆, 秋下彻 申请人:索尼公司
最新回复(0)