密码处理装置、密码处理装置制造装置及方法

摘要

实现一种能够维持对合性、安全性、且容易进行循环数变更的Feistel型共用密钥块密码处理结构。在具有包括非线性变换部以及线性变换部的SP型F函数的Feistel型密码处理结构中，构成具有对合性、以及满足作为预先设定的F函数排列条件的ODM-MR或者SDM-MR的矩阵排列的n循环的基本单元，通过对该单元选择并追加满足F函数排列条件的F函数、或者连接多个基本单元来构筑增加具有对合性、以及满足ODM-MR或者SDM-MR的排列的循环数的Feistel密码结构。

权利要求

1.一种密码处理装置，其特征在于，具有：

密码处理部，该密码处理部是执行将SP型F函数重复循环多次的Feistel型共用密钥块密码处理的密码处理部，所述SP型F函数执行包括非线性变换处理以及线性变换处理的数据变换处理，所述密码处理部具有密码处理基本单元，该密码处理基本单元具备对合性，仅通过使所使用的循环密钥的使用顺序相反就能够以相同电路实现加密函数和解密函数，并且将多个不同的F函数设为满足预先设定的F函数排列条件的排列；以及控制部，其根据在所述密码处理部中构成的密码处理基本单元的利用次数设定信息，进行将所述密码处理基本单元利用一次或者重复利用多次的密码处理运算的执行控制。

2.根据权利要求1所述的密码处理装置，其特征在于，

所述F函数排列条件是以下排列条件：

在执行所述Feistel型共用密钥块密码处理的密码处理部中所包含的各循环F函数是包含应用了三个不同的线性变换矩阵M0、M1、M2的三种F函数F0、F1、F2的结构的情况下，在从开头起依次选择了奇数循环的情况下在三个连续部分中包含三种F函数F0、F1、F2，在从最终循环起选择了偶数循环的情况下在三个连续部分中包含三种F函数F0、F1、F2。

3.根据权利要求1所述的密码处理装置，其特征在于，

所述F函数排列条件是以下排列条件：

在执行所述Feistel型共用密钥块密码处理的密码处理部中所包含的各循环F函数是包含应用了两个不同的线性变换矩阵M0、M1的两种F函数F0、F1的结构的情况下，在从开头循环起依次选择了奇数循环的情况下在两个连续部分中包含两种F函数F0、F1，在从最终循环起选择了偶数循环的情况下在两个连续部分中包含两种F函数F0、F1。

4.一种密码处理装置制造装置，其特征在于，具有：

密码处理基本单元生成部，其生成密码处理基本单元，该密码处理基本单元是执行将SP型F函数重复循环多次的Feistel型共用密钥块密码处理的密码处理部，所述SP型F函数执行包括非线性变换处理以及线性变换处理的数据变换处理，所述密码处理基本单元具备对合性，仅通过使所使用的循环密钥的使用顺序相反就能够以相同电路实现加密函数和解密函数，并且将多个不同F函数设为满足预先设定的F函数排列条件的排列；以及循环数变更部，其应用所述密码处理基本单元，根据在密码处理装置中设定的密码处理部的循环数，执行选择并追加满足所述F函数排列条件的F函数的处理。

5.根据权利要求4所述的密码处理装置制造装置，其特征在于，

所述F函数排列条件是以下排列条件：

在执行所述Feistel型共用密钥块密码处理的密码处理部中所包含的各循环F函数是包含应用了三个不同线性变换矩阵M0、M1、M2的三种F函数F0、F1、F2的结构的情况下，在从开头起依次选择了奇数循环的情况下在三个连续部分中包含三种F函数F0、F1、F2，在从最终循环起选择了偶数循环的情况下在三个连续部分中包含三种F函数F0、F1、F2。

6.根据权利要求4所述的密码处理装置制造装置，其特征在于，

所述F函数排列条件是以下排列条件：

在执行所述Feistel型共用密钥块密码处理的密码处理部中所包含的各循环F函数是包含应用了两个不同线性变换矩阵M0、M1的两种F函数F0、F1的结构的情况下，在从开头循环起依次选择了奇数循环的情况下在两个连续部分中包含两种F函数F0、F1，在从最终循环起选择了偶数循环的情况下在两个连续部分中包含两种F函数F0、F1。

7.根据权利要求4所述的密码处理装置制造装置，其特征在于，

所述循环数变更部是执行如下处理的结构：在构成所述密码处理基本单元的开头循环之前、以及最后循环之后，依次逐个选择并追加满足所述F函数排列条件的F函数。

8.根据权利要求4所述的密码处理装置制造装置，其特征在于，

所述循环数变更部是以下结构：多单元地连接所述密码处理基本单元来执行F函数追加处理。

9.一种密码处理方法，其特征在于，具有以下步骤：

密码处理步骤，该密码处理步骤是执行将SP型F函数重复循环多次的Feistel型共用密钥块密码处理的密码处理步骤，执行利用了密码处理基本单元的密码处理，所述SP型F函数执行包括非线性变换处理以及线性变换处理的数据变换处理，所述密码处理基本单元具备对合性，仅通过使所使用的循环密钥的使用顺序相反就能够以相同电路实现加密函数和解密函数，并且将多个不同F函数设为满足预先设定的F函数排列条件的排列；以及控制步骤，根据在所述密码处理部中构成的密码处理基本单元的利用次数设定信息，进行将所述密码处理基本单元利用一次或者重复利用多次的密码处理运算的执行控制。

10.根据权利要求9所述的密码处理方法，其特征在于，

所述F函数排列条件是以下排列条件：

在执行所述Feistel型共用密钥块密码处理的密码处理部中所包含的各循环F函数是包含应用了三个不同线性变换矩阵M0、M1、M2的三种F函数F0、F1、F2的结构的情况下，在从开头起依次选择了奇数循环的情况下在三个连续部分中包含三种F函数F0、F1、F2，在从最终循环起选择了偶数循环的情况下在三个连续部分中包含三种F函数F0、F1、F2。

11.根据权利要求9所述的密码处理方法，其特征在于，

所述F函数排列条件是以下排列条件：

在执行所述Feistel型共用密钥块密码处理的密码处理部中所包含的各循环F函数是包含应用了两个不同线性变换矩阵M0、M1的两种F函数F0、F1的结构的情况下，在从开头循环起依次选择了奇数循环的情况下在两个连续部分中包含两种F函数F0、F1，在从最终循环起选择了偶数循环的情况下在两个连续部分中包含两种F函数F0、F1。

12.一种密码处理装置制造方法，其特征在于，具有以下步骤：

密码处理基本单元生成步骤，生成密码处理基本单元，该密码处理基本单元是执行将SP型F函数重复循环多次的Feistel型共用密钥块密码处理的密码处理部，所述SP型F函数执行包括非线性变换处理以及线性变换处理的数据变换处理，所述密码处理基本单元具备对合性，仅通过使所使用的循环密钥的使用顺序相反就能够以相同电路实现加密函数和解密函数，并且将多个不同F函数设为满足预先设定的F函数排列条件的排列；以及循环数变更步骤，应用所述密码处理基本单元，根据在密码处理装置中设定的密码处理部的循环数，执行选择并追加满足所述F函数排列条件的F函数的处理。

13.根据权利要求12所述的密码处理装置制造方法，其特征在于，

所述F函数排列条件是以下排列条件：

在执行所述Feistel型共用密钥块密码处理的密码处理部中所包含的各循环F函数是包含应用了三个不同线性变换矩阵M0、M1、M2的三种F函数F0、F1、F2的结构的情况下，在从开头起依次选择奇数循环的情况下在三个连续部分中包含三种F函数F0、F1、F2，在从最终循环起选择偶数循环的情况下在三个连续部分中包含三种F函数F0、F1、F2。

14.根据权利要求12所述的密码处理装置制造方法，其特征在于，

所述F函数排列条件是以下排列条件：

在执行所述Feistel型共用密钥块密码处理的密码处理部中所包含的各循环F函数是包含应用了两个不同线性变换矩阵M0、M1的两种F函数F0、F1的结构的情况下，在从开头循环起依次选择奇数循环的情况下在两个连续部分中包含两种F函数F0、F1，在从最终循环起选择偶数循环的情况下在两个连续部分中包含两种F函数F0、F1。

15.根据权利要求12所述的密码处理装置制造方法，其特征在于，

所述循环数变更步骤执行如下处理：在构成所述密码处理基本单元的开头循环之前、以及最后循环之后，依次逐个选择并追加满足所述F函数排列条件的F函数。

16.根据权利要求12所述的密码处理装置制造方法，其特征在于，

所述循环数变更步骤是以下步骤：多单元地连接所述密码处理基本单元来执行F函数追加处理。

说明书

密码处理装置、密码处理装置制造装置及方法、以及计算机

程序

技术领域

[0001] 本发明涉及一种密码处理装置、密码处理装置制造装置及方法、以及计算机程序。更详细地说，涉及一种执行Feistel型共用密钥块密码处理的密码处理装置、密码处理装置制造装置及方法、以及计算机程序。

背景技术

[0002] 近来伴随着网络通信、电子商务的发展，通信中的安全保障成为重要的问题。安全保障的方法之一是密码技术，当前实际上正在进行使用了各种加密方法的通信。例如已经实用化了如下系统：在IC卡等小型装置中嵌入密码处理模块，在IC卡和作为数据读取写入装置的读写器之间进行数据发送接收，从而进行认证处理、或者发送接收数据的加密、解密。

[0003] 密码处理算法中有各种算法，大致分类为将加密密钥和解密密钥设定为不同密钥例如公开密钥和私密密钥的公开密钥密码方式、以及将加密密钥和解密密钥设定为共用密钥的共用密钥密码方式。

[0004] 共用密钥密码方式中也存在各种算法，其中之一是以共用密钥为基础生成多个密钥、并使用生成的多个密钥重复执行组单位(64比特、128比特等)的数据变换处理的方式。应用了这种密钥生成方式和数据变换处理的代表性算法是共用密钥块密码方式。

[0005] 作为共用密钥块密码方式的设计之一，大多使用被称为Feistel结构的结构，该Feistel结构对作为加密处理对象输入的明文数据重复执行成为基本的变换函数。Feistel结构是由被称为循环函数的基本的处理单元的重复所构成。循环函数的重复数量、即循环数(或者级数)设置为多少并不特别固定，而在设计时决定。

[0006] 如果将循环数设定得多，则处理时间变长，但是能够提高相对于各种攻击、即差分解析等密码解析的强度，使安全性强固。因而，在设为处理时间优先的情况、和设为安全性优先的情况等中，最好根据利用目的进行循环数设定。

发明内容

[0007] 发明所要解决的问题

[0008] 本发明的目的在于提供一种密码处理装置、密码处理装置制造装置及方法、以及计算机程序，在执行具有作为共用密钥块密码方式的设计之一的Feistel结构的Feistel型共用密钥块密码处理的结构中，能够容易地进行循环数的变更，并且能够在维持对差分攻击等攻击的高抵抗力的结构的情况下进行各种循环数设定下的密码处理。

[0009] 用于解决问题的方案

[0010] 本发明的第1侧面是一种密码处理装置，其特征在于，具有：

[0011] 密码处理部，该密码处理部是执行将SP型F函数重复循环多次的Feistel型共用密钥块密码处理的密码处理部，所述SP型F函数执行包括非线性变换处理以及线性变换处理的数据变换处理，所述密码处理部具有密码处理基本单元，该密码处理基本单元具备对合性，仅通过使所使用的循环密钥的使用顺序相反就能够以相同电路实现加密函数和解密函数，并且将多个不同的F函数设为满足预先设定的F函数排列条件的排列；

[0012] 控制部，其根据在所述密码处理部中构成的密码处理基本单元的利用次数设定信息，进行将所述密码处理基本单元利用一次或者重复利用多次的密码处理运算的执行控制。

[0013] 并且，在本发明的密码处理装置的一实施方式中，其特征在于，所述F函数排列条件是以下排列条件：在执行所述Feistel型共用密钥块密码处理的密码处理部中所包含的各循环F函数是包含应用了三个不同线性变换矩阵M0、M1、M2的三种F函数F0、F1、F2的结构的情况下，在从开头起依次选择了奇数循环的情况下在三个连续部分中包含三种F函数F0、F1、F2、在从最终循环起选择了偶数循环的情况下在三个连续部分中包含三种F函数F0、F1、F2。

[0014] 并且，在本发明的密码处理装置的一实施方式中，其特征在于，所述F函数排列条件是以下排列条件：在执行所述Feistel型共用密钥块密码处理的密码处理部中所包含的各循环F函数是包含应用了两个不同线性变换矩阵M0、M1的两种F函数F0、F1的结构的情况下，在从开头循环起依次选择了奇数循环的情况下在两个连续部分中包含两种F函数F0、F1、在从最终循环起选择了偶数循环的情况下在两个连续部分中包含两种F函数F0、F1。

[0015] 并且，本发明的第2侧面是一种密码处理装置制造装置，其特征在于，具有：密码处理基本单元生成部，其生成密码处理基本单元，该密码处理基本单元是执行将SP型F函数重复循环多次的Feistel型共用密钥块密码处理的密码处理部，所述SP型F函数执行包括非线性变换处理以及线性变换处理的数据变换处理，所述密码处理基本单元具备对合性，仅通过使所使用的循环密钥的使用顺序相反就能够以相同电路实现加密函数和解密函数，并且将多个不同F函数设为满足预先设定的F函数排列条件的排列；以及[0016] 循环数变更部，其应用所述密码处理基本单元，根据在密码处理装置中设定的密码处理部的循环数，执行选择并追加满足所述F函数排列条件的F函数的处理。

[0017] 并且，在本发明的密码处理装置制造装置的一实施方式中，其特征在于，所述F函数排列条件是以下排列条件：在执行所述Feistel型共用密钥块密码处理的密码处理部中所包含的各循环的F函数是包含应用了三个不同线性变换矩阵M0、M1、M2的三种F函数F0、F1、F2的结构的情况下，在从开头起依次选择了奇数循环的情况下在三个连续部分中包含三种F函数F0、F1、F2、在从最终循环起选择了偶数循环的情况下在三个连续部分中包含三种F函数F0、F1、F2。

[0018] 并且，在本发明的密码处理装置制造装置的一实施方式中，其特征在于，所述F函数排列条件是以下排列条件：在执行所述Feistel型共用密钥块密码处理的密码处理部中所包含的各循环的F函数是包含应用了两个不同线性变换矩阵M0、M1的两种F函数F0、F1的结构的情况下，在从开头循环起依次选择了奇数循环的情况下在两个连续部分中包含两种F函数F0、F1、在从最终循环起选择了偶数循环的情况下在两个连续部分中包含两种F函数F0、F1的排列条件。

[0019] 并且，在本发明的密码处理装置制造装置的一实施方式中，其特征在于，所述循环数变更部是执行如下处理的结构：在构成所述密码处理基本单元的开头循环之前、以及最后循环之后，依次逐个选择并追加满足所述F函数排列条件的F函数。

[0020] 并且，在本发明的密码处理装置制造装置的一实施方式中，其特征在于，所述循环数变更部是以下结构：多单元地连接所述密码处理基本单元来执行F函数追加处理。

[0021] 并且，本发明的第3侧面是一种密码处理方法，其特征在于，具有以下步骤：

[0022] 密码处理步骤，该密码处理步骤是执行将SP型F函数重复循环多次的Feistel型共用密钥块密码处理的密码处理步骤，执行利用了密码处理基本单元的密码处理，所述SP型F函数执行包括非线性变换处理以及线性变换处理的数据变换处理，所述密码处理基本单元具备对合性，仅通过使所使用的循环密钥的使用顺序相反就能够以相同电路实现加密函数和解密函数，并且将多个不同F函数设为满足预先设定的F函数排列条件的排列；以及[0023] 控制步骤，根据在所述密码处理部中构成的密码处理基本单元的利用次数设定信息，进行将所述密码处理基本单元利用一次或者重复利用多次的密码处理运算的执行控制。

[0024] 并且，在本发明的密码处理方法的一实施方式中，其特征在于，所述F函数排列条件是以下排列条件：在执行所述Feistel型共用密钥块密码处理的密码处理部中所包含的各循环F函数是包含应用了三个不同线性变换矩阵M0、M1、M2的三种F函数F0、F1、F2的结构的情况下，在从开头起依次选择了奇数循环的情况下在三个连续部分中包含三种F函数F0、F1、F2、在从最终循环起选择了偶数循环的情况下在三个连续部分中包含三种F函数F0、F1、F2。

[0025] 并且，在本发明的密码处理方法的一实施方式中，其特征在于，所述F函数排列条件是以下排列条件：在执行所述Feistel型共用密钥块密码处理的密码处理部中所包含的各循环F函数是包含应用了两个不同线性变换矩阵M0、M1的两种F函数F0、F1的结构的情况下，在从开头循环起依次选择了奇数循环的情况下在两个连续部分中包含两种F函数F0、F1、在从最终循环起选择了偶数循环的情况下在两个连续部分中包含两种F函数F0、F1。

[0026] 并且，本发明的第4侧面是一种密码处理装置制造方法，其特征在于，具有：

[0027] 密码处理基本单元生成步骤，生成密码处理基本单元，该密码处理基本单元是执行将SP型F函数重复循环多次的Feistel型共用密钥块密码处理的密码处理部，所述SP型F函数执行包括非线性变换处理以及线性变换处理的数据变换处理，所述密码处理基本单元基本对合性，仅通过使所使用的循环密钥的使用顺序相反就能够以相同电路实现加密函数和解密函数、并且将多个不同F函数设为满足预先设定的F函数排列条件的排列；以及[0028] 循环数变更步骤，应用所述密码处理基本单元，根据在密码处理装置中设定的密码处理部的循环数，执行选择并追加满足所述F函数排列条件的F函数的处理。

[0029] 并且，在本发明的密码处理装置制造方法的一实施方式中，其特征在于，所述F函数排列条件是以下排列条件：在执行所述Feistel型共用密钥块密码处理的密码处理部中所包含的各循环的F函数是包含应用了三个不同线性变换矩阵M0、M1、M2的三种F函数F0、F1、F2的结构的情况下，在从开头起依次选择奇数循环的情况下在三个连续部分中包含三种F函数F0、F1、F2、在从最终循环起选择偶数循环的情况下在三个连续部分中包含三种F函数F0、F1、F2。

[0030] 并且，在本发明的密码处理装置制造方法的一实施方式中，其特征在于，所述F函数排列条件是以下排列条件：在执行所述Feistel型共用密钥块密码处理的密码处理部中所包含的各循环F函数是包含应用了两个不同线性变换矩阵M0、M1的两种F函数F0、F1的结构的情况下，在从开头循环起依次选择奇数循环的情况下在两个连续部分中包含两种F函数F0、F1、在从最终循环起选择偶数循环的情况下在两个连续部分中包含两种F函数F0、F1。

[0031] 并且，在本发明的密码处理装置制造方法的一实施方式中，其特征在于，所述循环数变更步骤执行如下处理：在构成所述密码处理基本单元的开头循环之前、以及最后循环之后，依次逐个选择并追加满足所述F函数排列条件的F函数。

[0032] 并且，在本发明的密码处理装置制造方法的一实施方式中，其特征在于，所述循环数变更步骤是以下步骤：多单元地连接所述密码处理基本单元来执行F函数追加处理。

[0033] 并且，本发明的第5侧面是一种计算机程序，在密码处理装置中执行密码处理，其特征在于，具有：

[0034] 密码处理步骤，是在密码处理部中执行将SP型F函数重复循环多次的Feistel型共用密钥块密码处理的密码处理步骤，执行利用了密码处理基本单元的密码处理，所述SP型F函数执行包括非线性变换处理以及线性变换处理的数据变换处理，所述密码处理基本单元具备对合性，仅通过使所使用的循环密钥的使用顺序相反就能够以相同电路实现加密函数和解密函数，并且将多个不同F函数设为满足预先设定的F函数排列条件的排列；以及[0035] 控制步骤，在控制部中根据在所述密码处理部中构成的密码处理基本单元的利用次数设定信息，进行将所述密码处理基本单元利用一次或者重复利用多次的密码处理运算的执行控制。

[0036] 此外，本发明的计算机程序是例如可以对能够执行各种程序代码的计算机系统通过以计算机可读形式提供的存储介质、通信介质、例如CD、FD、MO等记录介质、或者网络等通信介质提供的计算机程序。通过以计算机可读形式提供这种程序，在计算机系统上实现与程序相应的处理。

[0037] 可通过基于后述的本发明实施例、附图的更详细的说明来明确本发明的其它目的、特征、优点。此外，在本说明书中，系统是指多个装置的逻辑集合结构，与各结构的装置是否在同一框体内无关。

[0038] 发明的效果

[0039] 根据本发明的结构，在将具有非线性变换部以及线性变换部的SP型F函数重复循环多次执行的Feistel型共用密钥块密码处理中，作为密码处理基本单元而构成n循环结构的Feistel密码结构，该n循环结构的Feistel密码结构具有满足预先设定的对合性、以及作为预先设定的F函数的排列条件的ODM-MR或者SDM-MR的矩阵排列，通过对该密码处理基本单元追加在满足F函数的排列条件的条件设定下所选择的F函数的处理、或者连接多个密码处理基本单元的处理，能够构筑使具有满足对合性以及ODM-MR或者SDM-MR的排列的循环数增加的Feistel密码结构。

附图说明

[0040] 图1是表示具有Feistel结构的代表性的共用密钥块密码结构的图。

[0041] 图2是说明作为循环函数部而设定的F函数的结构的图。

[0042] 图3是说明Feistel型密码处理中的对合性的图。

[0043] 图4是说明利用了两个不同的线性变换矩阵的Feistel型密码算法的图。

[0044] 图5是说明利用了三个不同的线性变换矩阵的Feistel型密码算法的图。

[0045] 图6是说明具有三种F函数部的6循环结构的Feistel型密码算法的图。

[0046] 图7是说明具有三种F函数部的8循环结构的Feistel型密码算法的图。

[0047] 图8是说明对具有三种F函数部的Feistel型密码处理基本单元进行循环数追加处理的图。

[0048] 图9是说明对具有三种F函数部的Feistel型密码处理基本单元进行循环数追加处理的图。

[0049] 图10是说明利用多个具有三种F函数部的Feistel型密码处理基本单元的循环数追加处理的图。

[0050] 图11是说明利用多个具有两种F函数部的Feistel型密码处理基本单元的循环数追加处理的图。

[0051] 图12是说明利用具有三种F函数部的Feistel型密码处理基本单元的密码处理装置的控制处理的图。

[0052] 图13是说明利用具有两种F函数部的Feistel型密码处理基本单元的密码处理装置的控制处理的图。

[0053] 图14是表示作为执行与本发明有关的密码处理的密码处理装置的IC模块的结构例的图。

[0054] 图15是表示与本发明有关的密码处理装置制造装置的结构例的图。

具体实施方式

[0055] 下面详细说明本发明的密码处理装置、密码处理装置制造装置及方法、以及计算机程序。按照以下项目进行说明。

[0056] 1.具有SP型F函数的Feistel结构

[0057] 2.关于最优扩散变换以及准最优扩散变换

[0058] 3.关于对合性

[0059] 4.具有利用多个不同的变换矩阵的SP型F函数的Feistel型密码结构[0060] 5.在具有利用多个不同的变换矩阵的SP型F函数的Feistel型密码中使循环数容易变更的结构

[0061] 6.密码处理装置的结构例

[0062] 7.密码处理装置制造装置的结构例

[0063] [1.具有SP型F函数的Feistel结构]

[0064] 首先，说明具有SP型F函数的Feistel结构。作为共用密钥块密码的设计大多使用被称作Feistel结构的结构，该结构是在明文数据的变换方法中将基本变换函数以某种特别顺序进行排列的结构。Feistel结构具有通过简单重复被称作循环函数的变换函数而将明文变换为密码文的结构。

[0065] 参照图1说明Feistel结构。将作为加密对象而输入的明文长度设为2mn比特。其中m、n都是整数。最初，将2mn比特的明文分割为mn比特的两个输入数据PL(Plain-Left)101、PR(Plain-Right)102，将其设为输入值。

[0066] 通过重复被称作循环函数的基本结构来表现Feistel结构，各循环函数中包含的数据变换函数被称作F函数120。在图1的结构中表示将F函数(循环函数)120重复r级而得到的结构例。

[0067] 例如在第1个循环中，mn比特的输入数据X、和从密钥生成部(未图示)输入的mn比特的循环密钥K1103输入到F函数120，在F函数120中的数据变换处理之后输出mn比特的数据Y。输出与来自另一方的前级的输入数据(第1级的情况下是输入数据PL)在异或部104中进行异或运算，将mn比特的运算结果向下个循环函数输出。该处理、即将F函数重复应用所决定的循环数(r)来完成加密处理，输出密码文的分割数据CL(Cipher-Lefr)、CR(Cipher-Right)。可知通过以上结构，Feistel结构的解密处理仅使插入循环密钥的顺序相反即可，而不需要构成逆函数。

[0068] 参照图2说明作为各循环的函数而设定的F函数120的结构。图2(a)是表示对一个循环中的F函数120的输入以及输出的图，图2(b)是表示F函数120的详细结构的图。如图2(b)所示，F函数120具有连接了非线性变换层(S层)和线性变换层(P层)的所谓SP型结构。

[0069] 图2所示的F函数120是具有输入输出长度设定为m×n(m、n：整数)比特的函数。在SP型F函数内部中，首先执行密钥数据Ki和数据Xi之间的异或，接着应用非线性变换层(S层)，然后应用线性变换层(P层)。

[0070] 具体地说，非线性变换层(S层)排列了m个被称作S盒(S-box)121的n比特输入n比特输出的非线性变换表而成，以每n比特对mn比特的数据进行分割，分别输入到对应的S盒(S-box)121来变换数据。在各S盒中，例如执行应用了变换表的非线性变换处理。

[0071] 线性变换层(P层)由线性变换部122构成，线性变换部122输入来自S盒121的输出数据的mn比特的输出值Z，对该输入实施线性变换来输出mn比特结果。线性变换部122执行输入比特位置的替换处理等线性变换处理，输出mn比特的输出值Y。该输出值Y与来自前级的输入数据进行异或，作为下一循环的F函数的输入值。

[0072] 此外，在下面说明的本实施例的结构中，在作为线性变换层(P层)的线性变换部122中执行的线性变换被定义为应用了在GF(2)上定义的mn×mn矩阵而进行的线性变换，并且将第i循环中包含的矩阵称作Mi。

[0073] [2.关于最优扩散变换以及准最优扩散变换]

[0074] 在具有上述SP型F函数的Feistel型密码中，在F函数的线性变换层中执行的线性变换中应用的线性变换矩阵优选为应用满足一定条件的矩阵使得密码强度不下降。对该条件进行说明。

[0075] 作为线性变换的特殊例子，如下定义最优扩散变换(ODM：Optimal Diffusion Mappings)。

[0076] 对于从n×a比特数据向n×b比特数据进行线性变换的映射，

[0077] θ：{0，1}na→{0，1}nb

[0078] 如下定义分支数B(θ)。

[0079] B(θ)＝minα≠0{hwn(α)+hwn(θ(α))}

[0080] 其中，minα≠0{Xα}设为表示满足α≠0的所有Xα中的最小值的Xα，hwn(Y)设为在以每n比特对比特列Y进行划分表示时、返回n比特数据全部都不是0(非零)的元素数量的函数。

[0081] 此时，将分支数B(θ)是b+1的映射θ定义为最优扩散变换(ODM：Optimal Diffusion Mappings)。另外为了方便，还将矩阵M的分支数表示为B(M)。

[0082] 并且，将分支数B(θ)不足b+1的映射θ定义为准最优扩散变换(SDM：Sub Optimal Diffusion Mappings)。

[0083] 在具有上述SP型F函数的Feistel型密码中，在决定在F函数的线性变换层中执行的线性变换中应用的线性变换矩阵的情况下，优选为研究是否设定为执行上述最优扩散变换(ODM)即分支数B(θ)是b+1的映射θ、以及准最优扩散变换(SDM)即分支数B(θ)不足b+1的映射θ，来决定矩阵。在后面说明具体的矩阵决定处理。

[0084] [3.关于对合性]

[0085] 如下这样定义执行具有上述SP型F函数的Feistel型密码的加密函数E。

[0086] E(PL||PR，K1，K2，...，Kr)

[0087] 上述加密函数E中所示的PL、PR表示作为密码处理对象而输入的明文，||表示连接，K1，K2，...，Kr表示在各循环中使用的循环密钥。

[0088] 在以这种函数E所示的密码处理中，能够如下地表示其解密函数D。

[0089] D(CL||CR，K1，K2，...，Kr)＝E(CL||CR，Kr，...，K2，K1)

[0090] 上述解密函数D中所示的CL、CR表示作为解密处理对象而输入的密码文，||表示连接，Kr，...，K2，K1表示在各循环中使用的循环密钥。

[0091] 这样，在Feistel结构共用密钥块密码中，通常具有仅使所使用的循环密钥的使用顺序相反就能够以相同的电路实现加密函数和解密函数的特征。即不在密码处理和解密处理中单独设定电路，而是应用相同的电路，仅将其处理顺序设定为相反就能够执行密码处理和解密处理两者。将Feistel结构共用密钥块密码所具有的该性质定义为对合性。

[0092] 参照附图说明Feistel结构共用密钥块密码所具有对合性。将图1所示的Feistel结构设为在加密处理中应用的Feistel结构。在这种情况下执行加密函数E。即执行：

[0093] E(PL||PR，K1，K2，...，Kr)

[0094] PL、PR如图1所示表示作为密码处理对象而输入的明文，K1，K2，...，Kr如图1所示表示在各循环中使用的循环密钥。

[0095] 另一方面，用于解密作为图1所示的Feistel结构的加密处理结果的密码文CL、CR的Feistel结构变成图3所示的结构。图3所示的Feistel结构执行解密函数D，即执行：

[0096] D(CL||CR，K1，K2，...，Kr)

[0097] ＝E(CL||CR，Kr，...，K2，K1)

[0098] CL、CR如图3所示是作为解密处理对象而输入的密码文，Kr，...，K2，K1如图3所示表示在各循环中使用的循环密钥。

[0099] 这样，在Feistel结构共用密钥块密码中，不在密码处理和解密处理中单独设定电路，而是应用相同的电路，仅将其处理顺序设定为相反就能够执行密码处理和解密处理两者。将这一性质定义为对合性。

[0100] [4.具有利用多个不同的变换矩阵的SP型F函数的Feistel型密码结构][0101] 在具有SP型F函数的Feistel型密码中，当将在各循环中应用的线性变换矩阵设定为不同矩阵时，能够提高对例如差分解析等攻击的抵抗力。即能够提高密码强度。此外，关于通过将在各循环中应用的线性变换矩阵设定为不同矩阵来提高具有SP型F函数的Feistel型密码的密码强度的详细结构，在与本发明相同申请人在先申请的专利申请：特愿2005-313842中进行了说明。

[0102] 在现有的Feistel型密码中，在全部循环(级)的F函数中使用相同的线性变换层，因此存在在差分传播时同时取消多个差分的性质。作为密码解析方法的代表性方法，已知有通过多次解析具有某种差分的输入数据(明文)及其输出数据(密码文)来解析各循环函数中的应用密钥的差分解析(或者差分解读法)，在现有的DES密码算法等共用密钥块密码中，将在F函数的线性变换部中应用的处理(变换矩阵)设定为在各级的循环中相同，因此容易进行差分解析，其结果导致密钥的解析容易。

[0103] 通过将在各循环的F函数中应用的线性变换矩阵设为按照特定序列的不同矩阵，能够排除差分在传播时同时取消多个差分的性质，能够提高对差分解析等攻击的抵抗力。

[0104] 参照图4、图5说明具体的例子。图4的例子是利用两个不同的矩阵M0、M1作为用于在具有多级(循环)的Feistel型共用密钥块密码处理结构中的各级F函数中的线性变换部中应用的线性变换处理的矩阵的例子。

[0105] 具体地说，如图4所示，

[0106] (a)在奇数级中以M0、M1的顺序排列

[0107] (b)从偶数级的最终级起以M0、M1的顺序排列

[0108] 设为应用两个不同的矩阵M0、M1使得满足上述(a)、(b)的条件的结构。此外，M0、M1的顺序也可以相反。即，相同矩阵在连续奇数级中不连续，相同矩阵当从最终级起看偶数级时也在连续偶数级中不连续，这成为提高对差分解析等攻击的抵抗力的条件。

[0109] 条件(a)是(a)在奇数级中以M0、M1的顺序排列的条件，如图4所示，将矩阵M0、M1按照循环1、3、5、...的顺序顺序排列。条件(b)是(b)从偶数级的最终级起以M0、M1的顺序排列的条件，如图4所示，将矩阵M0、M1按照循环12、10、8、...的顺序排列。在此，各矩阵M0、M1是在各循环中的F函数中被执行的两个不同的线性变换矩阵。

[0110] 图4所示的例子是利用了两个不同的线性变换矩阵的例子，在该结构中也能够提高对差分攻击的抵抗力，但是还可以是利用了三个不同矩阵M0、M1、M2的结构。图5是利用三个不同的矩阵M0、M1、M2作为用于在具有多级(循环)的Feistel型共用密钥块密码处理结构中的各级F函数中的线性变换部中应用的线性变换处理的矩阵的例子。

[0111] 如图5所示，

[0112] (a)在奇数级中以M0、M1、M2的顺序排列

[0113] (b)从偶数级的最终级起以M0、M1、M2的顺序排列

[0114] 设为应用三个不同矩阵M0、M1、M2来满足上述(a)、(b)的条件的结构。此外，M0、M1、M2的顺序也可以不同。即，在奇数级的三个连续部分中必须包含M0、M1、M2这三个不同的矩阵，当从最终级起观察偶数级时，在三个连续部分中必须包含M0、M1、M2这三个不同的矩阵，这成为提高对差分解析等攻击的抵抗力的条件。条件(a)是(a)在奇数级中以M0、M1、M2的顺序排列的条件，如图5所示，按照循环1、3、5、...的顺序将矩阵M0、M1、M2顺序排列。条件(b)是(b)从偶数级的最终级起以M0、M1、M2的顺序排列的条件，如图5所示，按照循环12、10、8、...的顺序将矩阵M0、M1、M2顺序排列。在此，各矩阵M0、M1、M2是在各循环中的F函数中被执行的线性变换矩阵。

[0115] 如参照图4、图5所说明的那样，通过设为以特定顺序排列不同的矩阵来执行F函数的结构，实现了提高对差分解析等攻击的抵抗力的、具有更高安全性的Feistel型密码。此外，关于其结构以及处理的详细内容，在与本发明是相同申请人的在先专利申请：特愿
2005-313842中进行说明。

[0116] 并且，为了保持一定的密码强度，希望参照图4、图5所说明的在设定多个不同线性变换矩阵的Feistel型密码中应用的线性变换矩阵利用具有特定性质的矩阵。评价、设定该线性变换矩阵时，可以使用最优扩散变换、准最优扩散变换的评价基准。

[0117] 说明最优扩散变换、准最优扩散变换的定义。在将参照图5说明的三个不同矩t -1 t -1 t -1 t -1 t -1 t -1阵设为M0、M1、M2的情况下，当{M0||M1||M2}、{M0 ||M1 }、{M0 ||M2 }、{M1 ||M2 }四个矩阵全部是最优扩散变换(Optimal Diffusion Mappings)时，将M0、M1、M2定义为具有ODM-MR(Optimal Diffusion Mappings across Multiple Rounds：多级最优扩散变换)t -1
结构的矩阵。其中，||表示连接，M表示M的转置矩阵，M 表示M的逆矩阵。另外，在将t -1 t -1
参照图5说明的三个不同的矩阵设为M0、M1、M2的情况下，当{M0||M1||M2}、{M0 ||M1 }、t -1 t -1 t -1 t -1
{M0 ||M2 }、{M1 ||M2 }的四个矩阵中任何一个是准最优扩散变换(SubOptimal Diffusi on Mappings)时，将M0、M1、M2定义为具有SDM-MR(Sub Optimal Diffusion Mappings across MultipleRounds：多级准最优扩散变换)结构的矩阵。

[0118] 此外，在将三个不同的矩阵设为M0、M1、M2的情况下，为了满足ODM-MR、或者SDM-MR，将三个不同矩阵M0、M1、M2的排列顺序按先前参照图5说明的排列顺序排列，即[0119] (a)在奇数级中以M0、M1、M2的顺序排列

[0120] (b)从偶数级的最终级起以M0、M1、M2的顺序排列

[0121] 条件是排列三个不同矩阵M0、M1、M2以满足上述(a)、(b)的条件。此外，如先前所说明的那样，M0、M1、M2的顺序也可以不同。即，在奇数级的三个连续部分中必须包含M0、M1、M2这三个不同的矩阵，当从最终级起看偶数级时在三个连续部分中也必须包含M0、M1、M2这三个不同的矩阵，这是成为满足ODM-MR、或者SDM-MR的矩阵排列、能够提高对差分解析等攻击的抵抗力的条件。

[0122] 另外，在将两个不同的矩阵设为M0、M1的情况下，为了满足ODM-MR、或者SDM-MR，将两个不同的矩阵M0、M1的排列顺序按先前参照图4说明的排列顺序排列，即[0123] (a)在奇数级中以M0、M1的顺序排列

[0124] (b)从偶数级的最终级起以M0、M1的顺序排列

[0125] 条件是排列两个不同的矩阵M0、M1以满足上述(a)、(b)的条件。此外，如先前所说明，M0、M1的顺序也可以相反。即，在连续奇数级中相同的矩阵不连续，从最终级起看偶数级时，在连续偶数级中相同的矩阵也不连续，这是成为满足ODM-MR、或者SDM-MR的矩阵排列、能够提高对差分解析等攻击的抵抗力的条件。

[0126] 如上所述，在利用多个不同矩阵的Feistel型密码结构中，通过将在各循环中应用的线性变换矩阵的设定设为ODM-MR结构、或者SDM-MR结构，能够实现安全性高的密码处理。

[0127] [5.在具有利用多个不同的变换矩阵的SP型F函数的Feistel型密码中使循环数的变更容易的结构]

[0128] 下面说明在具有利用多个不同的变换矩阵的SP型F函数的Feistel型密码中使循环数的变更容易的结构。

[0129] 在共用密钥块密码中，其处理循环数(级数)在速度、安全性之间进行折中，因此希望能够灵活地进行增减。通常存在如下关系：如果循环数(级数)增加则安全性变高，但是速度下降，如果级数减少则安全性变低，但是速度上升。因而，希望设为如下结构：在设为处理速度优先的情况、或者设为安全性优先的情况等下，能够根据其用途灵活地变更处理循环数。

[0130] 另外，也存在根据在应用了Feistel型密码的密码处理中应用的密钥大小而变更处理循环数的要求。例如，在变更在密码处理中应用的密钥大小的情况下，为了确保足够的安全性，最好是结合密钥的大小来适当变更处理循环数。例如，在执行AES密码算法的情况下，有如下要求：应用的密钥大小是128比特时是10级，密钥大小是192比特时是12级，密钥大小是256比特时是14级，与密钥大小一起变更处理循环数，从而设定能够有效利用密钥大小的密钥结构比特数据的循环数。

[0131] 在构筑具有将具有上述ODM-MR结构、SDM-MR结构的矩阵应用在线性变换中的SP型F函数的Feistel结构共用密钥块密码的情况下，也希望维持所述的对合性，但是在排列包含不同线性变换矩阵的不同的F函数时，必须在先前参照图4、图5说明的制约下进行排列。

[0132] 此外，在下面的说明中，将使用线性变换矩阵M0的F函数记为F0，使用线性变换矩阵M1的F函数记为F1，使用线性变换矩阵M2的F函数记为F2。

[0133] 在利用了利用三个不同矩阵M0、M1、M2的F函数F0、F1、F2的情况下，如先前参照图5所说明那样，

[0134] (a)在从上方起选择奇数循环的情况下，以F0，F1，F2，F0，F1，...的顺序排列[0135] (b)在从下方起选择偶数循环的情况下，以F0，F1，F2，F0，F1，...的顺序排列需要设为排列应用三个不同矩阵M0、M1、M2的F函数F0、F1、F2以满足上述(a)、(b)的条件的结构。此外，如先前所说明那样，F0、F1、F2的顺序也可以不同。即在奇数级的三个连续部分中必须包含利用了三个不同的矩阵M0、M1、M2的F函数F0、F1、F2，从最终级看偶数级时在三个连续部分中也必须包含应用了M0、M1、M2三个不同的矩阵的三个不同的F函数F0、F1、F2，这是成为满足ODM-MR、或者SDM-MR的矩阵排列、能够提高对差分解析等攻击的抵抗力的条件。

[0136] 同样，在利用了利用两个不同矩阵M0、M1的F函数F0、F1的情况下，如先前参照图4所说明那样，

[0137] (a)在从上方起选择奇数循环的情况下，以F0，F1，F0，F1，F0，...的顺序排列[0138] (b)在从下方起选择偶数循环的情况下，以F0，F1，F0，F1，F0，...的顺序排列[0139] 需要设为排列应用两个不同矩阵M0、M1的F函数F0、F1以满足上述(a)、(b)的条件的结构。此外，如先前所说明那样，F0、F1的顺序也可以相反。即，连续包含不同的两个F函数F0、F1使得在连续奇数级中相同矩阵不连续，连续包含不同的两个F函数F0、F1使得从最终级起看偶数级时、在连续偶数级中相同矩阵不连续，这是成为满足ODM-MR、或者SDM-MR的矩阵排列、能够提高对差分解析等攻击的抵抗力的条件。

[0140] 并且，在应用了利用不同的多个矩阵的F函数的Feistel型密码中，为了维持对合性、即如先前所说明那样仅使所使用的循环密钥的使用顺序相反就能够以相同的电路进行加密函数和解密函数的对合性，需要使Feistel型密码的各循环的F函数从上方起的排列顺序和从下方起的排列顺序相同。

[0141] 这样，在Feistel型密码中，为了维持对差分解析等密码攻击的抵抗力需要维持对合性的条件，并且，需要在设为应用利用了多个不同的线性变换矩阵的不同F函数的Feistel型密码结构的情况下、其排列也设为满足如上所述的ODM-MR、或者SDM-MR的矩阵排列的条件。

[0142] 在应用利用了多个不同线性变换矩阵的不同F函数的Feistel型密码结构中需要满足这种条件，在设计密码处理结构的情况下，预先决定循环数，根据决定的固定循环数决定具有多个不同的线性变换矩阵的不同F函数的排列。其结果是在固定了的循环数中能够进行满足对合性、以及满足ODM-MR、或者SDM-MR的矩阵排列这两个条件的设计，但是存在不能容易地变更这些循环数的问题。

[0143] 例如，在假设使用三个不同矩阵的ODM-MR结构Feistel密码作为6循环(6级)结构的情况下，所排列的F函数的顺序需要设为如图6所示的设定。即，如图6所示，[0144] 从上方起设为[F0→F2→F1→F1→F2→F0]的设定。

[0145] 另 外，在8 级 结 构 的ODM-MR结 构Feistel 密 码 的 情 况 下，所 排 列的F函数的顺序需要设为如图7所示的设定。即，如图7所示，从上方起设为[F0→F0→F1→F2→F2→F1→F0→F0]的设定。

[0146] 这样，能够与各循环数对应地分别地进行满足对合性、和ODM-MR、或者SDM-MR的矩阵排列这两个条件的设计，但是将6级结构变更为8级结构并不容易。即如图6、图7所示，6级结构、8级结构的ODM-MR结构Feistel密码F函数的顺序大为不同，因此能够重新利用的地方非常少。例如假设安装了如图6所示的6级结构的ODM-MR结构Feistel密码的硬件已制造完成。在此，在存在想使用如图7所示的8级结构的ODM-MR结构Feistel密码的请求的情况下，存在如下问题：几乎无法利用图6所示的6级结构的ODM-MR结构Feistel密码的硬件，需要重新制作图7所示的8级结构的ODM-MR结构Feistel密码的硬件。或者需要进行作为处理程序的软件变更的处理。

[0147] 下面说明减轻这种处理负担的结构例。即，说明能够在具有ODM-MR结构或者SDM-MR结构的Feistel密码处理结构中有效执行处理循环数的增加、减少等循环数变更的结构。

[0148] (处理例1)在Feistel密码处理基本单元中追加F函数的处理例

[0149] 首先，说明通过对预先设定的Feistel密码处理基本单元、即具有满足对合性和满足ODM-MR、或者SDM-MR的矩阵排列这两个条件的结构的Feistel密码处理基本单元追加F函数来增加循环数的处理结构。

[0150] 作为一例，将具有满足对合性和满足ODM-MR、或者SDM-MR的矩阵排列这两个条件的结构的6级结构的ODM-MR结构Feistel密码设为基本的密码处理基本单元。在此，设为由具有三个不同线性变换矩阵的不同的F函数F0、F1、F2构成的Feistel密码处理基本单元。如先前参照图6所说明那样，该基本密码处理基本单元的F函数排列成为从上方起[F0→F2→F1→F1→F2→F0]，具有满足对合性和满足ODM-MR、或者SDM-MR的矩阵排列这两个条件的结构。

[0151] 说明将该6级结构的ODM-MR结构Feistel密码变更为8循环(级)结构的处理。在将6级变更为8级的情况下，如图8所示，在具有[F0→F2→F1→F1→F2→F0]的排列的6级结构的密码处理基本单元201的上下分别追加[F0]的F函数。

[0152] 通过该F函数[F0]的追加，如图8所示，Feistel密码结构变更为8循环(级)结构，F函数的排列顺序变成从上方起[F0→F0→F2→F1→F1→F2→F0→F0]的设定。

[0153] 在该8级结构的情况下，F函数的排列顺序在从上方起选择奇数级的情况下，成为[0154] [F0→F2→F1→F0]，

[0155] 在从下方起选择偶数级的情况下，成为

[0156] [F0→F2→F1→F0]。

[0157] 该8级结构的Feistel密码结构，各循环的F函数从上方起的排列顺序和从下方起的排列顺序相同，因而满足对合性。并且，在奇数级的三个连续部分中必然包含利用了三个不同的矩阵M0、M1、M2的F函数F0、F1、F2，当从最终级起看偶数级时，在三个连续部分中也必然包含应用了M0、M1、M2三个不同的矩阵的三个不同的F函数F0、F1、F2，因此成为满足ODM-MR、或者SDM-MR的矩阵排列。

[0158] 这种情况下的F函数的选择条件是选择成为如下设定的F函数：

[0159] 在奇数级的三个连续部分中必须包含利用了三个不同的矩阵M0、M1、M2的F函数F0、F1、F2，且从最终级起看偶数级时，在三个连续部分中也必须包含应用了M0、M1、M2三个不同的矩阵的三个不同的F函数F0、F1、F2。

[0160] 当根据该选择条件选择进行追加的F函数时，在从图8所示的从6级向8级的循环数追加处理中，进行追加的F函数成为F函数[F0]，能够将6级结构的ODM-MR结构Feistel密码变更为具有对合性、以及满足ODM-MR、或者SDM-MR的矩阵排列的8循环(级)结构的Feistel密码。

[0161] 并且，参照图9说明将该图8所示的具有对合性以及满足ODM-MR、或者SDM-MR的矩阵排列的8循环(级)结构的Feistel密码结构变更为10级的情况的处理例。在将8级变更为10级的情况下，如图9所示，在具有[F0→F0→F2→F1→F1→F2→F0→F0]的排列的8级结构的密码处理基本单元202的上下分别追加[F2]的F函数。

[0162] 通过该F函数[F2]的追加，如图9所示，Feistel密码结构变更为10循环(级)结构，F函数的排列顺序成为从上方起[F2→F0→F0→F2→F1→F1→F2→F0→F0→F2]的设定。在该10级结构的情况下，F函数的排列顺序在从上方起选择奇数级的情况下，成为

[0163] [F2→F0→F1→F2→F0]，

[0164] 在从下方起选择偶数级的情况下，成为

[0165] [F2→F0→F1→F2→F0]。

[0166] 该10级结构的Feistel密码结构，各循环的F函数从上方起的排列顺序和从下方起的排列顺序相同，因而满足对合性。并且，在奇数级的三个连续部分中必然包含利用了三个不同的矩阵M0、M1、M2的F函数F0、F1、F2，从最终级起看偶数级时在三个连续部分中也必然包含应用了M0、M1、M2三个不同的矩阵的三个不同的F函数F0、F1、F2，因此成为满足ODM-MR、或者SDM-MR的矩阵排列。

[0167] 这种情况的F函数的选择条件也与从6级向8级的变更相同，是选择成为如下设定的F函数：

[0168] 在奇数级的三个连续部分中必须包含利用了三个不同的矩阵M0、M1、M2的F函数F0、F1、F2，且从最终级起看偶数级时在三个连续部分中也必须包含应用了M0、M1、M2三个不同的矩阵的三个不同的F函数F0、F1、F2。

[0169] 当根据该选择条件选择进行追加的F函数时，在图9所示的从8级向10级的循环数追加处理中，进行追加的F函数变成F函数[F2]，能够将8级结构的ODM-MR结构Feistel密码变更为具有对合性、以及满足ODM-MR、或者SDM-MR的矩阵排列的10循环(级)结构的Feistel密码。

[0170] 这样，在使预先设定的具有对合性、以及满足ODM-MR、或者SDM-MR的矩阵排列的n循环(级)结构的Feistel密码结构成为n+2循环(级)结构的Feistel密码结构的情况下，通过选择成为如下设定的F函数并追加到上下方，能够构筑具有对合性、以及满足ODM-MR、或者SDM-MR的矩阵排列的n+2循环(级)结构的Feistel密码结构。所述F函数的设定为：在奇数级的三个连续部分中必须包含利用了三个不同的矩阵M0、M1、M2的F函数F0、F1、F2，且从最终级看偶数级时在三个连续部分中也必须包含应用了M0、M1、M2三个不同的矩阵的三个不同的F函数F0、F1、F2。

[0171] 满足这种条件来进行F函数的追加处理，即对于预先设定的具有对合性、以及满足ODM-MR、或者SDM-MR的矩阵排列的n循环(级)结构的Feistel密码结构单元，在最上级和最下级分别附加适当的F函数的处理，由此附加的函数以外的部分能够直接重新利用变更以前的函数，能够高效地进行每次两级的级数的增减。

[0172] 通过以上的处理，能够维持ODM-MR或者SDM-MR结构Feistel密码的对合性并高效地每次两级地增减其处理循环数。另外，即使依次从上下逐一去除在上下追加设定的F函数，也能够剩下具有对合性、满足ODM-MR、或者SDM-MR的矩阵排列的n循环(级)结构的Feistel密码结构单元，不仅能够对应循环的增加，也能够对应到当初密码处理基本单元水平为止的循环数削减。

[0173] 此外，在上述处理例中，说明了包含具有三个不同线性变换矩阵的三个F函数F0、F1、F2的结构例，但是在包含具有两个不同线性变换矩阵的两个F函数F0、F1的结构中，通过相同的处理，也能够实现循环数的增加。

[0174] 对于包含具有两个不同线性变换矩阵的两个F函数F0、F1的Fesitel密码结构，进行循环数增加的情况下的条件如下。在使预先设定的具有对合性、以及满足ODM-MR、或者SDM-MR的矩阵排列的n循环(级)结构的Feistel密码结构变为n+2循环(级)结构的Feistel密码结构的情况下，通过选择如下设定的F函数并追加到上下方，能够构筑具有对合性、以及满足ODM-MR、或者SDM-MR的矩阵排列的n+2循环(级)结构的Feistel密码结构。所述F函数的设定为：在奇数级的两个连续部分中必须包含利用了两个不同的矩阵M0、M1的F函数F0、F1，且从最终级起看偶数级时在两个连续部分中也必须包含应用了M0、M1两个不同的矩阵的两个不同的F函数F0、F1。

[0175] (处理例2)利用多个Feistel密码处理基本单元的处理例

[0176] 在上述处理例中，说明了在基本的Feistel密码处理基本单元的上下方分别逐一追加F函数来构筑增加2循环的Feistel密码处理结构的例子。接着，说明通过组合多个基本的Feistel密码处理基本单元来进行循环数变更的处理例。

[0177] 参照图10说明通过组合多个基本的Feistel密码处理基本单元来进行循环数变更的处理例。图10所示的Feistel密码处理基本单元231、232分别是具有如下结构的6级结构的Feistel密码处理基本单元：F函数的排列从上起为[F0→F2→F1→F1→F2→F0]，具有满足对合性和满足ODM-MR、或者SDM-MR的矩阵排列这两个条件。

[0178] 图10所示的结构是使用该两个6级Feistel密码处理基本单元231、232来设定12级结构的Feistel密码处理结构的结构。图10所示的12级结构的Feistel密码结构，F函数排列从上方起变成[F0→F2→F1→F1→F2→F0→F0→F2→F1→F1→F2→F0]。

[0179] 在该12级结构的情况下，F函数的排列顺序在从上方起选择奇数级的情况下，成为

[0180] [F0→F1→F2→F0→F1→F2]，

[0181] 在从下方起选择偶数级的情况下，成为

[0182] [F0→F1→F2→F0→F1→F2]。

[0183] 该12级结构的Feistel密码结构，各循环的F函数从上方起的排列顺序和从下方起的排列顺序相同，因而满足对合性。并且，在奇数级的三个连续部分中必然包含利用了三个不同的矩阵M0、M1、M2的F函数F0、F1、F2，从最终级起看偶数级时在三个连续部分中也必然包含应用了M0、M1、M2三个不同的矩阵的三个不同的F函数F0、F1、F2，因此成为满足ODM-MR、或者SDM-MR的矩阵排列。

[0184] 图10中表示了连接两个6级单元来生成12级结构的Feistel密码结构的例子，但是通过进一步连接三个、四个…多个6级单元，能够同样地构成18级、24级的Feistel密码结构、即是ODM-MR结构且保持了对合性的Feistel密码结构。

[0185] 这样，通过组合多个(k)具有满足对合性和满足ODM-MR、或者SDM-MR的矩阵排列这两个条件的结构的n级Feistel密码处理基本单元，能够构筑k×n级的满足对合性和满足ODM-MR、或者SDM-MR的矩阵排列这两个条件的Feistel密码处理结构。

[0186] 说明将使用两个不同矩阵M0、M1的ODM-MR或者SDM-MR结构Feistel密码处理结构作为密码处理基本单元，同样地通过将其组合多个来进行循环数变更的处理例。图11所示的Feistel密码处理基本单元251、252、253分别是具有如下结构的4级结构的Feistel密码处理基本单元：F函数的排列从上方起成为[F0→F1→F1→F0]，具有满足对合性和满足ODM-MR、或者SDM-MR的矩阵排列这两个条件。

[0187] 图11所示的结构是使用该三个4级Feistel密码处理基本单元251、252、253来设定12级结构的Feistel密码处理结构的结构。图11所示的12级结构的Feistel密码结构，F函数的排列从上方起成为[F0→F1→F1→F0→F0→F1→F1→F0→F0→F1→F1→F0]。在该12级结构的情况下，F函数的排列顺序在从上方起选择奇数级的情况下，成为[0188] [F0→F1→F0→F1→F0→F1]，

[0189] 在从下方起选择偶数级的情况下，成为

[0190] [F0→F1→F0→F1→F0→F1]。

[0191] 该12级结构的Feistel密码结构，各循环的F函数从上方起的排列顺序和从下方起的排列顺序相同，因而满足对合性。并且，在奇数级的两个连续部分中必然包含利用了两个不同的矩阵M0、M1、M2的F函数F0、F1，从最终级看偶数级时在两个连续部分中也必然包含应用了M0、M1两个不同的矩阵的两个不同的F函数F0、F1，因此成为满足ODM-MR、或者SDM-MR的矩阵排列。

[0192] 图11中表示了连接三个4级单元来生成12级结构的Feistel密码结构的例子，但是通过进一步连接四个、五个…多个4级单元，能够同样地构成16级、20级的Feistel密码结构、即是ODM-MR结构且保持了对合性的Feistel密码结构。

[0193] 这样，通过组合多个(k)具有满足对合性和满足ODM-MR、或者SDM-MR的矩阵排列这两个条件的结构的n级Feistel密码处理基本单元，能够构筑k×n级的满足对合性和满足ODM-MR、或者SDM-MR的矩阵排列这两个条件的Feistel密码处理结构。例如，在IC卡等执行密码处理的信息处理装置中的安装处理中，设为如下结构：在硬件中仅安装一个例如参照图10说明的6级结构的ODM-MR结构Feistel密码处理基本单元，设定可选择使用次数的处理程序，根据用途执行变更使用次数的处理程序，由此能够执行根据各种数据处理而选择的循环数的密码处理，能够以低成本实现可进行处理循环数增减的装置。

[0194] 参照图12来说明具体的例子。图12中表示执行密码处理的6级结构的Feistel密码处理基本单元270、和开关271～274。此外，开关271～274可以是作为硬件进行设定的结构，也可以是在软件上进行与开关执行相同的处理的控制的结构。

[0195] 图12所示的6级结构的Feistel密码处理基本单元270与先前参照图6、图10说明相同，是如下6级结构的Feistel密码处理基本单元，其F函数的排列从上方起为[F0→F2→F1→F1→F2→F0]，具有满足对合性和满足ODM-MR、或者SDM-MR的矩阵排列这两个条件的结构。

[0196] 通过未图示的控制部的控制来控制开关271～274。输入初始数据时，开关271、272设定在[a]侧，例如输入明文数据PL、PR，在6级结构的Feistel密码处理基本单元270中执行6循环的Feistel密码处理。在开关273、274被设定在[c]侧的情况下输出处理结果。

[0197] 在执行6循环Feistel密码处理的情况下，开关273、274被设定在[c]侧，输出结果。例如在执行12循环的密码处理的设定的情况下，通过控制部的控制，开关273、274被设定在[d]侧，开关271、272被设定在[b]侧。其结果是在6级结构的Feistel密码处理基本单元270中执行的6循环的处理结果被再次输入到6级结构的Feistel密码处理基本单元270的最上级，并且执行+6循环的F函数的密码处理。

[0198] 在密码处理是12循环的处理设定的情况下，之后开关273、274被设定在[c]侧，进行输出。在进一步执行18、24...循环的F函数处理的情况下，开关273、274被设定在[d]侧，在预定的处理循环结束后，开关273、274被设定在[c]侧，进行输出。由此，将一个基本的密码处理基本单元、即具有满足对合性和满足ODM-MR、或者SDM-MR的矩阵排列这两个条件的结构的n级结构的Feistel密码处理基本单元构成在IC卡等密码处理装置内，通过设为能够由CPU等控制部执行的程序来选择利用该单元的处理的重复次数的结构，能够执行与各个数据处理相应的最优循环数的密码处理运算。

[0199] 图13表示利用了两种矩阵的结构例。表示有4级结构的Feistel密码处理基本单元280、以及开关281～284。图13所示的4级结构的Feistel密码处理基本单元280与先前参照图11说明的相同，是如下4级结构的Feistel密码处理基本单元，其F函数的排列从上方起成为[F0→F1→F1→F0]，具有满足对合性和满足ODM-MR、或者SDM-MR的矩阵排列这两个条件的结构。

[0200] 通过未图示的控制部的控制来控制开关281～284。输入初始数据时，开关281、282被设定在[a]侧，例如输入明文数据PL、PR，在4级结构的Feistel密码处理基本单元
280中执行4循环的Feistel密码处理。在开关283、284被设定在[c]侧的情况下输出处理结果。

[0201] 在执行4循环Feistel密码处理的情况下，开关283、284被设定在[c]侧，输出结果。例如在执行8循环密码处理的设定的情况下，通过控制部的控制，开关283、284被设定在[d]侧，开关281、282被设定在[b]侧。其结果是在4级结构的Feistel密码处理基本单元280中执行的4循环的处理结果被再次输入到4级结构的Feistel密码处理基本单元280的最上级，并且执行+4循环的F函数的密码处理。

[0202] 在密码处理是8循环的处理设定的情况下，之后开关283、284被设定在[c]侧，进行输出。在进一步执行12、16…循环的F函数处理的情况下，开关283、284被设定在[d]侧，在预定的处理循环结束后，开关283、28被4设定在[c]侧，进行输出。由此，将一个基本的密码处理基本单元、即具有满足对合性和满足ODM-MR、或者SDM-MR的矩阵排列这两个条件的结构的n级结构的Feistel密码处理基本单元构成在IC卡等密码处理装置内，通过设为能够由CPU等控制部执行的程序来选择利用该单元的处理的重复次数的结构，能够执行与各个数据处理相应的最优循环数的密码处理运算。

[0203] [6.密码处理装置的结构例]

[0204] 下面，参照图14说明作为执行密码处理的密码处理装置的IC模块300的结构例。密码处理能够在例如PC、IC卡、读写器、其它各种信息处理装置中执行，图14所示的IC模块300表示密码处理装置的一例。

[0205] 图14所示的CPU(Central processing Unit：中央处理单元)301是执行密码处理的开始、结束、数据发送接收控制、各结构部之间数据传输控制、其它各种程序的处理器。存储器302由保存CPU301执行的程序、或者运算参数等固定数据的ROM(Read-Only-Memory：只读存储器)、作为在CPU301的处理中执行的程序、以及在程序处理中适当变化的参数的保存区域、工作区域而使用的RAM(Random Access Memory：随机存取存储器)等构成。另外，存储器302可以用作密码处理所需的密钥数据、在密码处理中应用的变换表(置换表)、变换矩阵中应用的数据等的保存区域。此外，希望数据保存区域构成为具有防篡改结构的存储器。

[0206] 密码处理部303例如执行按照上述Feistel型共用密钥块密码处理算法的密码处理、解密处理。此外，在此表示了将密码处理单元设为单独模块的例子，但是也可以不设置这种独立的密码处理模块的结构，例如将密码处理程序保存在ROM中，CPU301读出ROM保存程序来执行。

[0207] 随机数产生器304执行在生成密码处理所需密钥等中所需的随机数的产生处理。

[0208] 发送接收部305是执行与外部的数据通信的数据通信处理部，例如执行读写器等与IC模块之间的数据通信，执行在IC模块内生成的密码文的输出、或者来自外部读写器等设备的数据输入等。

[0209] 在该IC模块300中，密码处理部303例如设为图12、图13所示的密码处理基本单元、即具有满足对合性和满足ODM-MR、或者SDM-MR的矩阵排列这两个条件的结构的n级结构的Feistel密码处理基本单元，能够根据作为控制部的CPU301所执行的程序来决定处理循环数，执行决定的循环数的Feistel密码处理。

[0210] [7.密码处理装置制造装置的结构例]

[0211] 下面参照图15说明制造例如上述密码处理装置的制造装置的结构例。如图15所示，制造密码处理装置的制造装置具有密码处理基本单元生成部501、以及循环数变更部502。

[0212] 密码处理基本单元生成部501生成密码处理基本单元，该密码处理基本单元是先前参照图1、图2所说明的执行将SP型F函数重复循环多次的Feistel型共用密钥块密码处理的密码处理部，该SP型F函数执行包括非线性变换处理以及线性变换处理的数据变换处理，密码处理基本单元具备仅通过使所使用的循环密钥的使用顺序相反就能够以相同电路实现加密函数和解密函数的对合性、且将多个不同F函数设为满足预先设定的F函数排列条件的排列。密码处理基本单元是例如参照图12、图13说明的密码处理基本单元。

[0213] 循环数变更部502应用密码处理基本单元，根据在密码处理装置中设定的密码处理部的循环数，执行选择并追加满足所述F函数排列条件的F函数的处理，从而制造密码处理装置510。

[0214] 循环数变更部502例如参照图8、图9所说明那样，在构成密码处理基本单元的开头循环之前、以及最后循环之后，执行依次逐一地选择并追加满足所述F函数排列条件的F函数的处理。或者如参照图10、图11所说明那样，多单元地连接密码处理基本单元来执行F函数追加处理。

[0215] 此外，上述F函数排列条件是如下排列条件：在执行Feistel型共用密钥块密码处理的密码处理部中包含的各循环的F函数是包含应用了三个不同的线性变换矩阵M0、M1、M2的三种F函数F0、F1、F2的结构的情况下，在从开头起依次选择奇数循环的情况下在三个连续部分中包含三种F函数F0、F1、F2、在从最终循环起选择偶数循环的情况下在三个连续部分中包含三种F函数F0、F1、F2。

[0216] 另外，F函数排列条件是如下排列条件：在执行Feistel型共用密钥块密码处理的密码处理部中包含的各循环的F函数是包含应用了两个不同的线性变换矩阵M0、M1的两种F函数F0、F1的结构的情况下，在从开头循环起依次选择奇数循环的情况下在两个连续部分中包含两种F函数F0、F1、在从最终循环起选择偶数循环的情况下在两个连续部分中包含两种F函数F0、F1。

[0217] 以上，参照特定的实施例详细说明了本发明。然而，本领域技术人员能够在不超出本发明精神的范围内进行该实施例的修正、代用是不言而喻的。即，以例示的方式公开了本发明，不应解释为用其限定了本发明。为了判断本发明的精神，应参酌权利要求书一栏。

[0218] 此外，在说明书中说明的一系列处理能够由硬件、或者软件、或者两者的复合结构来执行。在执行软件的处理的情况下，能够将记录了处理序列的程序安装到组装到专用硬件中的计算机内的存储器来执行、或者在能够执行各种处理的通用计算机上安装程序来执行。

[0219] 例如，程序能够预先记录在作为记录介质的硬盘、ROM(Read Only Memory：只读存储器)中。或者程序能够在软盘、CD-ROM(Compact Disc Read Only Memory：小型只读光盘)、MO(Magneto optical：光磁)盘、DVD(Digital Versatile Disc：数字通用光盘)、磁盘、半导体存储器等可移动记录介质上临时或者永久保存(记录)。能够作为所谓封装软件来提供这种可移动记录介质。

[0220] 此外，程序除了可以从如上述的可移动记录介质安装在计算机中之外，还可以从下载站点无线传输到计算机、或通过LAN(Local Area Network：局域网)、因特网等网络有线传输到计算机中，在计算机中能够接收这样传输过来的程序，并安装在内置的硬盘等记录介质中。

[0221] 此外，在说明书中记载的各种处理不仅可以按照记载以时间序列执行，还可以根据执行处理的装置的处理能力或者需要而并行或者单独执行。另外，在本说明书中，系统是指多个装置的逻辑集合结构，与各结构的装置是否在同一框体内无关。

[0222] 工业实用性

[0223] 如上所述，根据本发明的结构，在将具有非线性变换部以及线性变换部的SP型F函数重复循环多次执行的Feistel型共用密钥块密码处理结构中，将具有满足预先设定的对合性、以及满足作为预先设定的F函数排列条件的ODM-MR或者SDM-MR的矩阵排列的n循环结构的Feistel密码结构构成为密码处理基本单元，能够通过对该密码处理单元追加在满足F函数排列条件的条件设定下选择的F函数的处理、或者连接多个密码处理基本单元，来构筑增加具有对合性、以及满足ODM-MR或者SDM-MR的排列的循环数的Feistel密码结构。