块加密装置、块加密方法以及程序

摘要

在基于一般化Feistel网络的块加密中，高效达成伪随机性和强伪随机性。在对kn比特块的明文进行加密时，在按每2n比特应用了Feistel置换后，应用基于对称地进行Type2分支涂色的2值de Bruijn图表的块单位的置换。综合Feistel置换和块单位的置换作为1轮，在重复上述的轮规定次数后，输出密文。

权利要求

1.一种块加密装置，该块加密装置具备：

输入部，其将输入的数据分割为k个块，k为8的倍数；

R轮份的Feistel置换部，其使用按每个轮生成的加密密钥，将上述块的2个作为1组来实施Feistel置换并进行输出；

块置换部，其将从上述Feistel置换部输出的k个块作为输入，使用下述函数colorfunc(u，v)＝vt if u1＝ut，colorfunc(u，v)＝vt+1 if u1≠ut来进行由第一颜色的矢线表示从偶数块向奇数块的迁移并由第二颜色的矢线表示从奇数块向偶数块的迁移的、相当于实施了对称的Type2分支涂色的2值de Bruiin图t表的块置换，其中，上述de Bruijn图表具有上述分割数k的一半的2 个节点，上述函数colorfunc(u，v)用于决定从节点u＝(u1，u2，……，ut)朝向节点v＝(v1，v2，……，vt)的矢线的颜色，并且，上述节点u和v由t比特的系列来表示，且t>2；以及输出部，其将通过上述R轮份的Feistel置换部和配置在上述Feistel置换部之间的R-1轮份的块置换部进行了置换后的k个块结合起来进行输出。

2.根据权利要求1所述的块加密装置，其中，

上述块置换部，以从上述Feistel置换部输出的中间文Y＝(y[0]，……，y[k-1])为输入，应用以下置换：

0～k-1的块编号i不足k/2，且：

·i mod 4为0的情况下，y[i]＝z[2i+1 mod k]·i mod 4为1的情况下，y[i]＝z[2i mod k]·i mod 4为2的情况下，y[i]＝z[2i+3 mod k]·i mod 4为3的情况下，y[i]＝z[2i-2 mod k]上述块编号i为k/2以上，且

·i mod 4为0的情况下，y[i]＝z[2i+3 mod k]·i mod 4为1的情况下，y[i]＝z[2i-2 mod k]·i mod 4为2的情况下，y[i]＝z[2i+1 mod k]·i mod 4为3的情况下，y[i]＝z[2i mod k]来输出轮输出文Z＝(z[0]，……z[k-1])。

3.根据权利要求1所述的块加密装置，其中，

取代相当于实施了上述对称的Type2分支涂色的2值de Bruijn图表的块置换，进行以下块置换：第一块置换，对从上述Feistel置换部输出的中间文Y，按每4个块交替进行右循环置换和左循环置换；和第二块置换，通过对第一块置换的结果进行k个块整体的右或左2个块循环置换，来输出轮输出文Z＝(z[0]，……，z[k-1])。

4.根据权利要求1所述的块加密装置，其中，

上述块的分割数k为8的倍数，

取代相当于实施了上述对称的Type2分支涂色的2值de Bruijn图表的块置换，上述块置换部进行以下块置换：针对具有上述分割数k的一半的4w个节点的次数2的图表的各节点(j＝0，1，……，w-1)，使第一颜色的矢线从节点4j向节点4j+1迁移，使第二颜色的矢线从节点4j向节点

4j+2迁移，

使第一颜色的矢线从节点4j+1向节点4j+2迁移，使第二颜色的矢线从节点4j+1向节点4j+1迁移，使第一颜色的矢线从节点4j+2向节点4(j+1)迁移，使第二颜色的矢线从节点4j+2向节点4j+3迁移，使第一颜色的矢线从节点4j+3向节点4j+3迁移，使第二颜色的矢线从节点4j+3向节点4(j+1)迁移，如上述这样的由第一颜色的矢线表示从偶数块向奇数块的迁移并由第二颜色的矢线表示从奇数块向偶数块的迁移的、相当于实施了对称的Type2分支涂色的有向图表的块置换，其中，w>1，节点4w视为节点0。

5.一种块加密方法，该块加密方法包括：

将输入的数据分割为k个块的步骤，k为8的倍数；

进行R轮份的Feistel置换的步骤，其中，在该R轮份的Feistel置换中，使用按每个轮生成的加密密钥，将上述块的2个作为1组来实施Feistel置换并进行输出；

进行块置换的步骤，在该块置换的步骤中，将由上述Feistel置换而输出的k个块作为输入，使用下述函数colorfunc(u，v)＝vt if u1＝ut，colorfunc(u，v)＝vt+1 if u1≠ut来进行由第一颜色的矢线表示从偶数块向奇数块的迁移并由第二颜色的矢线表示从奇数块向偶数块的迁移的、相当于实施了对称的Type2分支涂色的2值de Bruijn图t表的块置换，其中，上述de Bruijn图表具有上述分割数k的一半的2 个节点，上述函数colorfunc(u，v)用于决定从节点u＝(u1，u2，……，ut)朝向节点v＝(v1，v2，……，vt)的矢线的颜色，并且，上述节点u和v由t比特的系列来表示，且t>2；以及将通过上述R轮份的Feistel置换和配置在上述Feistel置换之间的R-1轮份的块置换进行了置换后的k个块结合起来进行输出的步骤。

6.根据权利要求5所述的块加密方法，其中，

在上述进行块置换的步骤中，以上述Feistel置换后的中间文Y＝(y[0]，……，y[k-1])为输入，应用以下置换：

0～k-1的块编号i不足k/2，且：

·i mod 4为0的情况下，y[i]＝z[2i+1 mod k]·i mod 4为1的情况下，y[i]＝z[2i mod k]·i mod 4为2的情况下，y[i]＝z[2i+3 mod k]·i mod 4为3的情况下，y[i]＝z[2i-2 mod k]上述块编号i为k/2以上，且

·i mod 4为0的情况下，y[i]＝z[2i+3 mod k]·i mod 4为1的情况下，y[i]＝z[2i-2 mod k]·i mod 4为2的情况下，y[i]＝z[2i+1 mod k]·i mod 4为3的情况下，y[i]＝z[2i mod k]来输出轮输出文Z＝(z[0]，……z[k-1])。

7.根据权利要求5所述的块加密方法，其中，

取代相当于实施了上述对称的Type2分支涂色的2值de Bruijn图表的块置换，进行以下块置换：第一块置换，对上述Feistel置换后的中间文Y，按每4个块交替进行右循环置换和左循环置换；和第二块置换，通过对第一块置换的结果进行k个块整体的右或左2个块循环置换，来输出轮输出文Z＝(z[0]，……，z[k-1])。

8.根据权利要求5所述的块加密方法，其中，

上述块的分割数k为8的倍数，

取代相当于实施了上述对称的Type2分支涂色的2值de Bruijn图表的块置换，进行以下块置换：针对具有上述分割数k的一半的4w个节点的次数2的图表的各节点(j＝0，1，……，w-1)，使第一颜色的矢线从节点4j向节点4j+1迁移，使第二颜色的矢线从节点4j向节点

4j+2迁移，

使第一颜色的矢线从节点4j+1向节点4j+2迁移，使第二颜色的矢线从节点4j+1向节点4j+1迁移，使第一颜色的矢线从节点4j+2向节点4(j+1)迁移，使第二颜色的矢线从节点4j+2向节点4j+3迁移，使第一颜色的矢线从节点4j+3向节点4j+3迁移，使第二颜色的矢线从节点4j+3向节点4(j+1)迁移，如上述这样的由第一颜色的矢线表示从偶数块向奇数块的迁移并由第二颜色的矢线表示从奇数块向偶数块的迁移的、相当于实施了对称的Type2分支涂色的有向图表的块置换，其中，w>1，节点4w视为节点0。

说明书

块加密装置、块加密方法以及程序

技术领域

[0001] [针对关联申请的记载]

[0002] 本发明主张日本国专利申请：特愿2009-246307号(2009年10月27日申请)的优先权，该申请的全部记载内容被引用并记载加入本说明书中。

[0003] 本发明涉及块加密装置、块加密方法以及程序，特别地，涉及使用了Feistel置换(费斯特置换)的块加密装置、块加密方法以及程序。

背景技术

[0004] 所谓块加密，是共用密钥加密的一种，是使用密钥(key)对某确定的块尺寸的明文(plaintext)进行加密的技术。作为块加密的代表性的构成方法，存在有使用Feistel
置换的方式。Feistel置换是，将1个块分割为2个单位块A、B，将1个单位块A输入称为
轮函数(round function)的带密钥的非线性函数，并将该输出与另1个单位块B进行异或
逻辑处理后，对单位块进行调换(swap)并输出。具体来说，对于轮函数F和输入(A，B)来
输出(B，B+F(A))。将该处理重复规定的轮数，从而生成密文。

[0005] 已知将上述Feistel置换进行一般化，将1个块分割为2个以上，并按每2个单位块来应用Feistel置换的方法，也将其称为一般化Feistel网络(Generalized Feistel
Network：GFN)。

[0006] 在GFN中，针对某偶数k，将1个块分割为k个单位块。该k被称为分割数。在单位块为n比特的情况下，1明文为kn比特。在将分割1块后得到的k个单位块设为(m[0]，
m[1]，......，m[k-1])的情况下，GFN的1轮为Block Perm(m[0]，F(m[0])+m[1]，m[2]，
F(m[2])+m[3]，......，F(m[k-2])，F(m[k-2])+m[k-1])。F是轮函数，Block Perm是将k
单位块的位置进行相互调换的置换。

[0007] 这里，作为Block Perm，标准是使用循环置换。也就是说，成为

[0008] [数1]BlockPerm

[0009] BlockPerm(v[0]，v[1]，…，v[k-1])＝(v[1]，v[2]，…，v[k-1]，v[0])

[0010] 另外，如果从第0个输入块开始至第k-1个输入块为止，将分别与这些输入块对应的输出块的编号进行排列后得到列表，则该BlockPerm表现为{1，2，......，k-1，0}。

[0011] 作为设分割数k＝4并使用循环置换的GFN的例子，列举非专利文献1的“CLEFIA”。在图10中示出使用分割数k＝4的循环置换的GFN的例子。

[0012] 另一方面，作为评价包含GFN的块加密的构造的安全性的方法，有伪随机性和强伪随机性。

[0013] 这是在目标的块加密为分割数k、单位块n比特的R轮GFN的情况下，将全部Rk/2个轮函数视作全部独立的伪随机函数时，评价块加密整体是否为kn比特的伪随机置换以
及强伪随机置换的技术。

[0014] 这里，伪随机函数F是根据任意的输入x来输出伪随机数F(x)(在计算量方面难以判别为真随机数的系列)的函数，伪随机置换E是根据任意明文x来输出不重复的伪随
机数E(x)作为密文的置换，强伪随机置换E是在E满足伪随机置换的条件的基础上，针对
E的逆置换D，根据任意的密文y来输出不重复的伪随机数D(y)作为明文的置换。强伪随
机置换意味着具有现实中所能期望的最强安全性的块加密。

[0015] 例如，在设Block Perm为循环置换的情况下，根据非专利文献2，已知k+1轮的GFN为伪随机置换，2k轮的GFN为强伪随机置换。这些评价给出构筑实际的块加密时最小限度所需的轮数。从安全性和计算量的观点来看，由于期望能以更少的轮数来满足伪随机性和
强伪随机性的块加密，所以，满足伪随机性和强伪随机性的轮数大多作为评价实际的块加
密的构造的好坏的指标来使用。

[0016] 由于在实际的块加密中使用的轮函数一般比伪随机函数更弱，所以，相比伪随机性所需的最小轮数而言，取某程度更多的轮数，来确保安全性 中的裕度(margin)。当然，以较小的轮数来满足伪随机性和强伪随机性的方式能够削减确保某水平的安全性裕度所需
的轮数，能够削减整体的计算量。

[0017] 另外，在不是Feistel型而是Substitution-Permutation network型(SPN型)的块加密中，对kn比特块输入(m[0]，m[1]，......，m[k-1])使用带密钥非线性置换S，并设Mix(S(m[0])，S(m[1])，......，S(m[k-1]))这样的处理为1轮。这里，Mix是kn比特的
线性变换，但是由于Mix在基于n比特块单位的调换的置换下，不存在不同的块间的影响，
所以无论什么情况下都不是安全的。Mix必须是包含块间的线性运算在内的置换。

[0018] 例如，在记载于非专利文献3“SAFER”中的128比特块加密SAFER+中，设k＝16，n＝8，通过将称为Pseudo-Hadamard Transform(PHT)的2个块单位的矩阵运算和基于块
单位的调换的置换Armenian Shuffle组合起来，从而实现Mix。

[0019] 在先专利文献

[0020] 非专利文献

[0021] 非专利文献1：Taizo Shirai，Kyoji Shibutani，Toru Akishita，Shiho Moriai，Tetsu Iwata：The 128-Bit Blockcipher CLEFIA.Alex Biryukov(Ed.)：Fast Softwareth
Encryption，14 International Workshop，FSE 2007，Luxembourg，Luxembourg，
March 16-28，2007，Revised Selected Papers.Lecture Notes in Computer Science
4593Springer 2007，pp.181-195.

[0022] 非 专 利 文 献 2：Shiho Moriai，Serge Vaudenay：On the Pseudorandomness of Top-Level Schemes of Block Ciphers.Tatsuaki Okamoto(Ed.)：Advances inth
Cryptology-ASIACRYPT 2000，6 International Conference on the Theory and
Application of Cryptology and Information Security，Kyoto，Japan，December
3-7，2000，Proceedings.Lecture Notes in Computer Science 1976Springer 2000，
pp.289-302.

[0023] 非专利文献3：James L. Massey：On the Optimality of SAFER+Diffusion.Proceedings of the Second AES Candidate Conference，National Institute of
Standards and Technology，1999.(http://csrc.nist.gov/archive/aes/round1/conf2/
papers/massey.pdf)

发明内容

[0024] 发明要解决的课题

[0025] 上述非专利文献1至3的所有公开内容引用并编入记载于本说明书中。

[0026] 以下，给出本发明的关联技术的分析。

[0027] 在非专利文献3“SAFER”中，针对Armenian Shuffle，基于图表有以下探索性发现。首先，设通过置换Block Perm对(m[0]，m[1]，......，m[k-1])进行置换后的结果为
(c[0]，c[1]，......，c[k-1])。考虑用k/2个节点的图表来表现该置换Block Perm。设s
＝(k/2)-1，则对图表中的节点附加node＝0，......，s这样的标签。设节点i表示m[2i]
和m[2i+1]。如非专利文献3“SAFER”所记载的那样，一般，如果Block Perm是进出次数2
即进入哪个节点的分支的数目都是2个，且从哪个节点出来的分支的数目也是2个的有向
图表，则通过对该图表上的分支进行4色涂色可以唯一进行表现。

[0028] 进一步地，针对Block Perm，要求将所有第偶数个输入块置换为第奇数个输出块，并将所有第奇数个输入块置换为第偶数个输出块。也就是说，针对某偶数i、i’和奇数j、j’，c[i]＝m[j]且c[j’]＝m[i’]。

[0029] 要唯一表现满足上述制约的任意Block Perm，上述有向图表对分支的涂色模式为2色就足够了。具体来说，将标签0，1，......，s(s＝(k/2)-1)附加到k/2个节点，从各节点出来的2个分支的颜色为红色(第一颜色，为方便起见用细线表示)和蓝色(第二颜色，
为方便起见用粗线表示)分别各1个，并且进入各节点的2个分支也分别以红色和蓝色各
1个这样来进行涂色。以下，将这样的分支的涂色规则称为“Type-2分支涂色：(类型2分
支涂色)”。

[0030] 如果给出满足这些条件的分支被涂色为2色的有向图表，则将从节点i至节点j的红色的分支与块m[2i]向块c[2j+1]的置换建立对应，将从节点i’至节点j’的蓝色的
分支与块m[2i’+1]向块c[2j’]的置换建立对应，由此，唯一确定置换Block Perm。相反，在给出Block Perm时，也唯一确定相对应的有向图表。另外，在非专利文献3“SAFER”中
将未进行分支涂色 的进出次数2的有向图表称为基干(skeleton)。

[0031] 非专利文献3“SAFER”的Armenian Shuffle是设等级3的2值de Bruijn图表B(3)稍稍变形后得到的图表为基干，并对其进行适当的Type-2分支涂色而得到的置换。

[0032] 这里，针对de Bruijn图表(d)进行定义。码元数为2且等级d的2值de Bruijn图表B(d)是节点数2d的有向图表，进出次数与码元数相同，为2。此时，各节点用d比特
值(如果d＝3，则为000，001，......，111)来表现。设某d比特值x的下位d-1比特值
为LS(x)，用||来表示比特系列彼此之间的连接，则在图表B(d)中，从节点x出来的2个分
支进入节点LS(x)||0和LS(x)||1。

[0033] 作为2值de Bruijn图表B(d)的唯一特征，已知图表的直径即任意2个节点间的迁移所需的分支的数目的最大值为d。在为节点数2d、次数2的有向图表时，这是理论最小
值。

[0034] 在非专利文献3“SAFER”中，Armenian Shuffle的基干的直径与等级3的2值deBruijn图表B(3)的直径相同，达成理论最小值即3，因此在SPN型块加密中，通过将PHT和
Armenian Shuffle组合起来来实现线性变换Mix，由此表示某种安全性评价的最佳化。

[0035] 如开头所述，在基于一般化Feistel网络的分割数k的块加密中，如果使用一般的循环置换作为单位块的置换，则要达成伪随机性和强伪随机性，需要分别设k+1和2k轮，存在想要使轮数减少这样的要求。

[0036] 本发明在上述分析的基础上而形成，其目的在于，在基于一般化Feistel网络的块加密中，提供一种能够减少伪随机性和强伪随机性所需的轮数的块加密装置、块加密方
法以及程序。

[0037] 用于解决课题的手段

[0038] 根据本发明的第一观点，提供一种块加密装置，该块加密装置具备：输入部，其将输入的数据分割为k个块；R轮份的Feistel置换部，其使用按每个轮生成的加密密钥，将上述块的2个作为1组来实施Feistel置换；块置换部，其使用下述函数

[0039] colorfunc(u，v)＝vtifu1＝ut，

[0040] colorfunc(u，v)＝vt+1ifu1≠ut

[0041] 来进行由第一颜色的矢线表示从偶数块向奇数块的迁移并由第二颜色的矢线表示从奇数块向偶数块的迁移的、相当于实施了对称的Type2分支涂色的2值de Bruijn图
t
表的块置换，其中，上述de Bruijn图表具有上述分割数k的一半的2 个(其中，t＞2)节
点，上述函数colorfunc(u，v)用于决定从节点u＝(u1，u2，......，ut)朝向节点v＝(v1，v2，......，vt)的矢线的颜色，并且，上述节点u和v由t比特的系列来表示；以及输出部，其将上述置换后的k个块结合起来进行输出。

[0042] 根据本发明的第二观点，提供一种块加密方法，该块加密方法包括：将输入的数据分割为k个块的步骤；进行R轮份的Feistel置换的步骤，其中，在该R轮份的Feistel置换中，使用按每个轮生成的加密密钥，将上述块的2个作为1组来实施Feistel置换；进行块
置换的步骤，在该块置换的步骤中，使用上述函数colorfunc(u，v)来进行由第一颜色的矢线表示从偶数块向奇数块的迁移并由第二颜色的矢线表示从奇数块向偶数块的迁移的、相
当于实施了对称的Type2分支涂色的2值de Bruijn图表的块置换，其中，上述de Bruijn
t
图表具有上述分割数k的一半的2 个(其中，t＞2)节点，上述函数colorfunc(u，v)用
于决定从节点u＝(u1，u2，......，ut)朝向节点v＝(v1，v2，......，vt)的矢线的颜色，并且，上述节点u和v由t比特的系列来表示；以及将上述置换后的k个块结合起来进行输出
的步骤。本方法与对输入的数据进行暗解码的计算机这样的特定的机械结合。

[0043] 根据本发明的第3观点，提供一种使计算机执行以下处理的程序：将输入的数据分割为k个块的处理；进行R轮份的Feistel置换的处理，其中，在该R轮份的Feistel置
换中，使用按每个轮生成的加密密钥，将上述块的2个作为1组来实施Feistel置换；使用
上述函数colorfunc(u，v)来进行由第一颜色的矢线表示从偶数块向奇数块的迁移并由第
二颜色的矢线表示从奇数块向偶数块的迁移的、相当于实施了对称的Type2分支涂色 的2
值de Bruijn图表的块置换的处理，其中，上述de Bruijn图表具有上述分割数k的一半的
t
2 个(其中，t＞2)节点，上述函数colorfunc(u，v)用于决定从节点u＝(u1，u2，......，ut)朝向节点v＝(v1，v2，......，vt)的矢线的颜色，并且，上述节点u和v由t比特的系
列来表示；以及将上述置换后的k个块结合起来进行输出的处理。另外，该程序能够记录在计算机能读取的存储介质中。也就是说，本发明能够具体实现为计算机程序产品。

[0044] 发明效果

[0045] 根据本发明，得到使用了能够采用更少的轮数来达成伪随机性和强伪随机性的一般化Feistel网络的块加密。其理由从2值de Bruijn图表也能明确，本发明的块置换
与循环置换的情况相比，由涂色为2颜色的图表来表现的情况下的充分距离(sufficient
distance：SD)将大幅变小。

附图说明

[0046] 图1是表示本发明的第一实施方式的构成的图[Struc1]。

[0047] 图2是采用处理块来表示本发明的第一实施方式的构成的图[Block1]。

[0048] 图3是表示与采用图表来表示本发明的第一实施方式的块置换(分割数为8的情况)的图[CdB0]相对应的列表表现的图(粗线与蓝色(第二颜色)相对应，细线与红色
(第一颜色)相对应)。

[0049] 图4是表示本发明的第一实施方式的动作的流程图[Flow1]。

[0050] 图5是采用图表来表示本发明的第一实施方式的块置换(分割数为16的情况)的图[CdB1](粗线与蓝色(第二颜色)相对应，细线与红色(第一颜色)相对应)。

[0051] 图6是采用图表来表示本发明的第一实施方式的块置换(分割数为32的情况)的图[CdB2](粗线与蓝色(第二颜色)相对应，细线与红色(第一颜色)相对应)。

[0052] 图7是表示与图4[CdB1]的图表相对应的块置换(分割数为16的情况)的图[Perm1]。

[0053] 图8是采用图表来表示分割数为8的左循环置换的图[Cyclicgph](粗线与蓝色(第二颜色)相对应，细线与红色(第一颜色)相对应)。

[0054] 图9是表示本发明的第二实施方式的1轮份的构成(分割数为16的情况)的图[Struc2]。

[0055] 图10是采用图表来表示本发明的第二实施方式的块置换(分割数为16的情况)的图[SS1](粗线与蓝色(第二颜色)相对应，细线与红色(第一颜色)相对应)。

[0056] 图11是表示使用了分割数k＝4的循环置换的GFN的例子的图[CyclicGFN]。

具体实施方式

[0057] 首先，说明本发明的概要。本发明涉及的块加密装置具备：输入部，其将输入的数据分割为k个块；R轮份的Feistel置换部，其使用按每个轮生成的加密密钥，将上述块的2个作为1组来实施Feistel置换；块置换部，其使用下述函数，即

[0058] colorfunc(u，v)＝vtifu1＝ut，

[0059] colorfunc(u，v)＝vt+1ifu1≠ut

[0060] 来进行由第一颜色的矢线表示从偶数块向奇数块的迁移并由第二颜色的矢线表示从奇数块向偶数块的迁移的、相当于实施了对称的Type2分支涂色的2值de Bruijn图表
t
的置换，其中，上述de Bruijn图表具有上述分割数k的一半的2 个(其中，t＞2)节点，上
述函数colorfunc(u，v)决定从节点u＝(u1，u2，......，ut)朝向节点v＝(v1，v2，......，vt)的矢线的颜色，并且，上述节点u和v由t比特的系列来表示；以及输出部，其将上述置
换后的k个块结合起来进行输出。

[0061] 上述块置换部中的与实施了对称的Type2分支涂色的2值de Bruijn图表相当的块置换处理能够通过对由Feistel置换输出的中间文Y＝(y[0]，y[1]，......，y[k-1])进
行以下置换来实现，其中，该置换为，

[0062] 块编号i(i＝0～k-1)不足k/2，且：

[0063] ·i mod 4(i mod4表示i除以4后得到的余数)为0的情况下，y[i]＝z[2i+1modk]

[0064] ·i mod4为1的情况下，y[i]＝z[2i mod k]

[0065] ·i mod4为2的情况下，y[i]＝z[2i+3mod k]

[0066] ·i mod4为3的情况下，y[i]＝z[2i-2mod k]

[0067] 上述块编号i为k/2以上，且

[0068] ·i mod4为0的情况下，y[i]＝z[2i+3mod k]

[0069] ·i mod4为1的情况下，y[i]＝z[2i-2mod k]

[0070] ·i mod4为2的情况下，y[i]＝z[2i+1mod k]

[0071] ·i mod4为3的情况下，y[i]＝z[2i mod k]。

[0072] 此时，输出(z[0]，z[1]，......z[k-1])作为轮输出文Z。重复必要次的这样的Feistel置换和块置换，最后应用Feistel置换来输出密文。

[0073] [第一实施方式]

[0074] 接着，参照附图来详细说明本发明的第一实施方式。图1[Struc1]是表示本发明的第一实施方式的构成的图。图2[Block1]是采用处理块来表示本发明的第一实施方式的
构成的图。

[0075] 参照图2，表示具备如下各部的块加密装置10：输入部100、密钥放大部101、轮数R个份的Feistel置换部102、R-1个份的块置换部103、输出部104。

[0076] 块加密装置10能够由具备CPU、存储器、磁盘等的各种信息处理装置来实现。此外，块加密装置10的上述各部能够通过预先将程序保存在磁盘中，并在CPU上使该程序动
作而实现。

[0077] 接着，说明块加密装置10的上述各部。另外，在以下的说明中，设块加密的分割数t+1k为2 (其中，t为2以上的正数)。此外，设轮数为R。

[0078] 输入部100是输入作为对象的明文M和秘密密钥SK的部件。例如，能够由从外部输入数据的装置和键盘等文字输入装置等来实现输入部100。

[0079] 密钥放大部101是用于导出从秘密密钥SK至R轮份的轮函数的密钥的部件。只要是以秘密密钥SK作为输入的函数且具有足够的输出宽度，则可以是任意函数。

[0080] Feistel置换部102按每n比特来分割进入轮的输入文X(n×k比特)， 针对k个单位块x[0]，x[1]，......，x[k-1]，按每2个块来应用Feistel置换，并输出中间文Y＝
(y[0]，y[1]，......，y[k-1])。

[0081] 另外，将最初的轮输入文X初始化为明文M。此外，各Feistel置换由(y[0]，y[1]，......，y[k-1]) ＝ (x[0]，F(x[0])+x[1]，x[2]，F(x[2])+x[3]，......，x[k-2]，F(x[k-2])+x[k-1])来表示。这里，F是n比特输入输出的轮函数，其密钥由密钥放大部101
导出。各轮函数的密钥可以根据进行处理的第偶数个块的索引(0，2，......，k-2)的不同而不同，也可以相同。

[0082] 块置换部103是按照n比特块单位对中间文Y＝(y[0]，y[1]，......，y[k-1])进行重新排列而得到轮输出文Z＝(z[0]，z[1]，......，z[k-1])的置换，针对2值de Bruijn图表B(s)，通过按照以下的规则进行type2分支涂色来进行定义。

[0083] 考虑具有2t个节点的2值de Bruijn图表B(t)，设由t比特系列(00..0，00..1，......，11..1)表示各节点。

[0084] 每次将分支涂色为2颜色时，设颜色为红色(细线：第一颜色)和蓝色(粗线：第二颜色)，并且在由二进制表现的情况下，设分别与0和1对应。

[0085] 在存在从节点u＝(u1，u2，......，ut)朝向节点v＝(v1，v2，......，vt)的分支时，为了决定该颜色二进制表现，使用下述函数colorfunc。

[0086] [colorfunc]

[0087] colorfunc(u，v)＝vtifu1＝ut，

[0088] colorfunc(u，v)＝vt+1ifu1≠ut，

[0089] 这里，vt+1是vt的比特反转。具体来说，例如u1＝ut的情况下，在从u的最上位开始的n-1比特系列LS(u)中，针对从右附加0的节点LS(u)||0，将分支的颜色涂色为红色
(细线，采用二进制表现为0)，针对从右附加1的节点LS(u)||1，将分支的颜色涂色为蓝色
(粗线，采用二进制表现为1)。

[0090] 同样地，在u1≠ut的情况下，反转涂色的规则，来进行涂色。该涂色方法对于2值de Bruijn图表B(t)是type2分支涂色，并且具有对称性。

[0091] 图3[CdB0]是实施了作为分割数k＝8而涂色的对称的Type2分支涂色后的2值de Bruijn图表。如图右所示，分割数k＝8时置换Block Perm能够由具有k/2个即4个
(3-1)
(2 )节点的图表来表现。并且，设s＝(k/2)-1，对图表中的节点附加node＝0，1，2，3这
样的标签。如果通过上述函数colorfunc来给出将分支涂色为2颜色的有向图表，则使从
某节点m朝向某节点n的红色的分支(细线)与从偶数块y[2m]向奇数块z[2n+1]的置换
建立对应，使从节点m’朝向节点n’的蓝色的分支与从奇数块y[2m’+1]向偶数块z[2n’]
的置换建立对应，由此唯一确定置换Block Perm。例如，图3[CdB0]的块置换与图1的块置
换部103中的块置换相对应，能够采用{1，2，7，4，3，0，5，6}这样的列表来表现。

[0092] 如果采用轮输入文Y＝(y[0]，y[1]，......，y[k-1])和轮输出文Z＝(z[0]，z[1]，......，z[k-1])来表现基于该涂色方法的置换，则为

[0093] 上述块编号i不足k/2，且

[0094] ·i mod4为0的情况下，y[i]＝z[2i+1mod k]

[0095] ·i mod4为1的情况下，y[i]＝z[2i mod k]

[0096] ·i mod4为2的情况下，y[i]＝z[2i+3mod k]

[0097] ·i mod4为3的情况下，y[i]＝z[2i-2mod k]

[0098] 上述块编号为k/2以上，且

[0099] ·i mod4为0的情况下，y[i]＝z[2i+3mod k]

[0100] ·i mod4为1的情况下，y[i]＝z[2i-2mod k]

[0101] ·i mod4为2的情况下，y[i]＝z[2i+1mod k]

[0102] ·i mod4为3的情况下，y[i]＝z[2i mod k]。

[0103] 另外，将图3的图表的矢线反向后得到的置换也能够实现。这只要将图1中的块编号的顺序变为相反顺序即可。

[0104] 输出部104是将从最后级Feistel置换部102输出的Y＝(y[0]，y[1]，......，y[k-1])结合起来输出密文的部件。具体来说，能够通过计算机显示器、打印机或各种数据输出装置来实现。

[0105] 另外，上述块加密装置中的各处理能够通过使构成块加密装置的计算机执行的程序来实现。

[0106] 接着，参照附图详细说明上述本发明的第一实施方式的块加密装置的 动作。图4[Flow1]是表示本发明的第一实施方式的动作的流程图。

[0107] 参照图4，首先，如果向输入部100输入明文M和秘密密钥SK(图4的步骤A1)，则通过密钥放大部101使用秘密密钥SK来生成R轮份的放大密钥(图4的步骤A2)。

[0108] 接着，设轮数的计数器为J＝1，将轮输入文X＝(x[0]，x[1]，......，x[k-1])的初始值设定为明文M(图4的步骤A3)，将使用了第J轮放大密钥的Feistel置换应用于偶数(i＝0，2，4，......，k-2)的块和奇数块的组(x[i]，x[i+1])，得到中间文Y＝(y[0]，y[1]，......，y[k-1])(图4的步骤A4)。

[0109] 在计数器J不足R的情况下，按每个块置换中间文Y而得到轮输出文Z＝(z[0]，z[1]，......，z[k-1])(图4的步骤A5)，进一步将J增加后(增加1)，将轮输入文X更新
为Z(图4的步骤A6)。

[0110] 另一方面，在计数器J与R一致的情况下，输出部104将得到的中间文Y作为密文来输出(图4的步骤A7)。

[0111] 如以上，为了生成密文，将轮输入文X的初始值设为明文M，由Feistel置换部102从轮输入文X生成中间文Y，通过块置换部103置换中间文Y而得到轮输出文Z，将轮输入
文X的内容更新为Z。重复该处理R轮次得到密文。另外，在本实施方式中，最后的第R轮
的块置换部103对安全性没有帮助，所以省略。因此，Feistel置换部102执行总计R次处
理，块置换部103执行总计R-1次处理。

[0112] 上述图1、图3所示的块置换是分割数为8时的块置换，在分割数增加的情况下也能够通过同样的方法来制成图表，唯一确定块置换。图5[CdB1]、图6[CdB2]分别是分割数
为16(t＝3(相当于k＝16))、32(t＝4(相当于k＝32))的情况下的实施了对称的Type2
分支涂色的2值de Bruijn图表。

[0113] 此外，与图5、图6的图表相对应的块置换能够如下进行列表表现。

[0114] 表示t＝3、分割数k＝16时的图5的图表能够变换为{1，2，7，4，9，10，15，12，3，0，5，6，11，8，13，14}这样的列表表现。

[0115] 同样地，表示t＝3、分割数k＝32时的图6的图表能够变换为{1，2，7，4，9，10，15，12，17，18，23，20，25，26，31，28，3，0，5，6，11，8，13，14，19，16，21，22，27，24，29，30}这样的列表表现。

[0116] 图7[Perm1]是表示与图5[CdB1]的图表相对应的块置换(分割数为16的情况)的图。在分割数16的情况下，图1的Feistel置换部102以及块置换部103分别成为图
7[Perm1]中示出的置换部。

[0117] 在具有以上的块置换部103的本实施方式中，与使用现有的循环置换的一般化Feistel网络的块加密相比，实质上，不改变1轮的计算量，能够减少伪随机性和强伪随机
性所需的最小轮数。

[0118] 这是根据在由分支被涂色为蓝色(粗线)和红色(细线)的图表来表现块置换的情况下的充分距离(sufficient distance：SD)比循环置换的情况下的充分距离(SD)更大
幅地减少这一情况而导出的。这里，如果充分距离(SD)为N，则在节点间的移动中，最初的
2次和最后的移动为蓝色，并且不连续使用红色的分支，也就是说，在遵照红色的分支进行移动的下一个必需使用蓝色的分支这样的规则时，在任意的2个节点间存在长度N的路径。

[0119] 充分距离(SD)和伪随机性所需的轮数成比例，具体来说，在充分距离为N时，轮数为N+2且能保证伪随机性。进一步地，在解码侧使用的逆置换的充分距离也为N的情况下，2N+2也能保证强伪随机性。

[0120] 图8所示的循环置换的图表(在图Cyclicgph中表示分割数为8的情况下的图)中，充分距离为节点数的2倍，也就是说与分割数k一致，但是在本实施方式中使用的块置
换增大某程度k时，在置换和逆置换双方中，达成2Log k的充分距离。具体来说，基于图6
所示的2值de Bruijn图表B(4)的k＝32的块置换虽然达成充分距离8，但是在另一方
面，在k＝32的循环置换中，成为充分距离32。由此，能够将伪随机性和强伪随机性所需的轮数分别削减大约65％。

[0121] 另外，在非专利文献3中也示出利用2值de Bruijn图表的置换，但是在非专利文献3中公开的图表不是奇偶“始终改变”的置换(参照非专利文献3的Fig.9中例如最左的
图表)。此外，在非专利文献3中，没有记载怎样才能够一般性地得到实施了对称的type2
分支涂色的2值deBruijn图表，而只是使8节点的2值de Bruijn图表B(3)稍稍变形并
进行适当的涂色，从而提出了分割数k＝16的置换即Armenian Shuffle。

[0122] 根据本实施方式能够明确，本发明与非专利文献3相比较，除了使用GFN这样的本质差别以外，在分割数16以外能够进行对应的这一点上是 通用的。根据本发明，能够灵活地设定作为目标的块加密的块尺寸以及轮函数的输入输出宽度。

[0123] 进一步地，本发明的基于对称的type2分支涂色的2值de Bruijn图表的置换是与Armenian Shuffle不同的，由于是左右对称的，所以能够减小安装的电路规模或程序大
小。

[0124] [第二实施方式]

[0125] 接着，说明对块置换与图表增加了变更的第二发明的实施方式。本实施方式的构成与图2所示的第一实施方式的块加密装置基本构成相同，由于在该块置换中加入了变
更，所以将以下其不同点作为中心进行说明。

[0126] 图9是表示本发明的第二实施方式的1轮份的构成(分割数16的情况)的图[Struc2]。

[0127] 在本实施方式中，分割数k为8的倍数，这里，设为w＝2时的16。

[0128] 块置换部103是按照n比特块单位来置换中间文Y＝(y[0]，y[1]，......，y[k-1])而得到轮输出文Z＝(z[0]，z[1]，......，z[k-1])的置换，通过以下定义的图表
(以下，称为“步进石(stepping stone)图表(SS)”)来进行定义。

[0129] 图10是采用步进石图表(SS)来表示本发明的第二实施方式的块置换(分割数为16的情况)的图[SS1](粗线与蓝色(第二颜色)相对应，细线与红色(第一颜色)相对
应。)。

[0130] 步进石图表(SS)与第一实施方式相同，是将节点数设为分割数k的一半，也就是说，设为4w，按次数2进行type2分支涂色的图表。

[0131] 其是能够通过追加进行如下涂色的矢线而作成的有向图表，即，针对各节点(j＝0，1，......，w-1)，

[0132] 节点4j是将红色(第一颜色)的分支朝向节点4j+1，将蓝色(第二颜色)的分支朝向节点4j+2，

[0133] 节点4j+1是将红色(第一颜色)的分支朝向节点4j+2，将蓝色(第二颜色)的分支朝向节点4j+1，

[0134] 节点4j+2是将红色(第一颜色)的分支朝向节点4(j+1)，将蓝色(第二颜色)的分支朝向节点4j+3，

[0135] 节点4j+3是将红色(第一颜色)的分支朝向节点4j+3，将蓝色(第二颜 色)的分支朝向节点4(j+1)。其中，节点4w视为节点0。

[0136] 基于图10[SS1]的图表的置换与图9的块置换部103a相对应，相当于以下情况，即，首先，进行按每4块的循环置换(循环的方向左右交替)，之后进行k块整体的右2块循
环置换。

[0137] 在具有以上这样的块置换部103a的本实施方式中，与使用现有技术的循环置换的一般化Feistel网络的块加密相比，实质上，不改变1轮的计算量，能够减少伪随机性和
强伪随机性所需的最小轮数。这是根据能够将前面说明的充分距离(SD)设为大约k/4+8
的情况导出的。具体来说，基于步进石图表(SS)的k＝32的置换达成充分距离16，另一方
面，在k＝32的循环置换中，成为充分距离32。

[0138] 此外，本实施方式，如图9所示，由于能够实现将每4块的1块循环置换和k块整体的2块循环置换组合起来的置换，所以能够为非常简单的安装。

[0139] 以上，说明了本发明的最佳实施方式，但是本发明不限于上述实施方式，在不脱离本发明的基本技术思想的范围内，能够加入进一步的变形/置换/调整。例如，上述实施方式的块加密装置能够采用相同的构成作为解码装置来工作。

[0140] 在本发明的所有公开(包含权利要求的范围以及附图)的范围内，进一步基于其基本技术思想，能够进行实施方式乃至实施例的变更/调整。此外，在本发明的所有公开的范围内，能够进行各种公开要素的多样组合乃至选择。也就是说，本发明当然包括按照包含权利要求的范围在内的所有公开、技术思想而能由本领域技术人员进行的各种变形、修正。

[0141] 符号说明：

[0142] 10 块加密装置

[0143] 100 输入部

[0144] 101 密钥放大部

[0145] 102 Feistel置换部

[0146] 103，103a 块置换部

[0147] 10 4输出部