消息认证装置、消息认证方法及消息认证程序

摘要

消息认证装置将消息M压缩为2n比特的值H，并将值H分割为n比特的两个值H[1]和值H[2]。消息认证装置从值H[1]提取min{t，n/2}比特的两个值U[1]和值U[2]，将消息M和值U[1]作为输入而生成t比特的值V[1]，并且将消息M和值U[2]作为输入而生成t比特的值V[2]。消息认证装置使用值V[1]作为Tweak并利用可调分组密码E加密值H[2]而生成值Z[1]，并且使用值V[2]作为Tweak并利用可调分组密码E加密值H[2]而生成值Z[2]。消息认证装置根据值Z[1]和值Z[2]生成认证码Z。

说明书

技术领域

本发明涉及使用可调分组密码(tweakable block cipher)的消息认证技术。

背景技术

当使用消息认证算法时，能够检测数据的篡改。将用消息认证算法处理的数据称为消息。

消息认证算法是将任意长度的消息M和密钥K作为输入并输出固定长度的篡改检测用的认证码Z的函数。

将发送者设为Alice，将接收者设为Bob。在进行使用消息认证算法的篡改检测通信的情况下，Alice和Bob预先共享密钥K。

Alice根据消息M和密钥K，使用消息认证算法生成消息M的认证码Z，并将消息M和认证码Z发送给Bob。Bob接收消息M和认证码Z，根据消息M和密钥K，使用消息认证算法生成认证码Z'。如果接收到的认证码Z与生成的认证码Z'一致则Bob判断为消息M未被篡改，如果不一致则判断为被篡改。

消息认证算法的安全性能够使用伪随机数性。伪随机数性是如下安全性：使用输出0或1的1比特的值的识别者D，并考虑识别者D访问消息认证算法并观测输出值后输出1的概率与识别者D访问随机函数R并观测输出值后输出1的概率之差。该差称为伪随机数性的优势(advantage)。

相对于使用密钥K的消息认证算法F

Adv

随机选择密钥K。随机函数R的输入为任意长度，输出与F

作为消息认证算法F

将Set(K)及Set(T)设为某有限集合。可调分组密码E是将作为Set(K)的要素的密钥K、作为Set(T)的要素的Tweak的值T及n比特的明文P作为输入并输出n比特的密文C的函数。将其书写为C＝E

在非专利文献1、2中记载了可调分组密码E。

在使用可调分组密码来设计消息认证算法的情况下，使用伪随机数性作为消息认证算法的安全性。在评价伪随机数性的情况下，使用密钥K的可调分组密码E

可调随机置换π将作为Set(T)的要素的Tweak的值T和n比特的明文P作为输入，并输出n比特的密文C。可调随机置换π在固定Tweak的值T时成为n比特的随机置换，在改变Tweak的值T时成为其他随机置换。

对于成为a≤b的整数a、b，将[a，b]设为a至b的整数的集合，即[a，b]＝{a，a+1，…，b-1，b}。对于比特串X，将|X|设为比特串X的比特长度。对于满足a≤|X|的正整数a，将X[1，a]设为X的上位a比特。对于正整数a、b，将str

对于正整数t、n比特的值X及t比特的值Y，如数学式2所示的那样定义数学式1所示的运算符。

[数学式1]

[数学式2]

将数学式3所示的运算符设为有限域GF(2

[数学式3]

有使用两个参数(j，T)作为Tweak的可调分组密码。对于正整数r、满足i≤2

另外，当Tweak的第一参数j∈[0，i]时，将使用密钥K的可调分组密码记载为E

非专利文献1及非专利文献2所记载的可调分组密码对于某整数s定义为Set(T)＝{0，1}

在非专利文献3～5中记载有使用可调分组密码的消息认证算法。

在非专利文献3中，记载有对于正整数t将Tweak的集合定义为Set(T)＝[0，2]×{0，1}

[数学式4]

将该优势的上限值称为边界(bound)。在识别者D的查询次数成为q＝O(2

在非专利文献4中，提出了对于正整数t，定义为Set(T)＝[0，5]×{0，1}

[数学式5]

由此，在n≤t的情况下，能够在可调随机置换的调用次数成为σ＝O(2

在非专利文献5中记载了削减非专利文献4所记载的消息认证算法的运算量而得到的消息认证算法。在非专利文献5中，关于非专利文献5所记载的消息认证算法，示出数学式6所示的伪随机数性的优势的边界。在数学式6中，F是非专利文献5所记载的消息认证算法。

[数学式6]

由此，在n≤t的情况下，能够在可调随机置换的调用次数成为σ＝O(2

在此，由于q≤σ，所以在使用可调分组密码的消息认证算法中，非专利文献3成为最安全的算法。

在先技术文献

非专利文献

非专利文献1：Jeremy Jean，Ivica Nikolic，Thomas Peyrin.Tweaks and Keysfor Block Ciphers：The TWEAKEY Framework.ASIACRYPT 2014.pp.274-288.LNCS volume8874.Springer.

非专利文献2：Christof Beierle，Jeremy Jean，Stefan Kolbl，Gregor Leander，Amir Moradi，Thomas Peyrin，Yu Sasaki，Pascal Sasdrich，Siang Meng Sim.The SKINNYFamily of Block Ciphers and Its Low-Latency Variant MANTIS.CRYPTO2016.pp.123-153.LNCS volume 9815.Springer.

非专利文献3：Yusuke Naito.Full PRF-Secure Message Authentication CodeBased on Tweakable Block Cipher.ProvSec 2015.pp.167-182.LNCS volume9451.Springer.

非专利文献4：Tetsu Iwata，Kazuhiko Minematsu，Thomas Peyrin，YannickSeurin.ZMAC：A Fast Tweakable Block Cipher Mode for Highly Secure MessageAuthentication.CRYPTO 2017.pp.34-65.LNCS volume 10403.Springer.

非专利文献5：Eik List，Mridul Nandi.ZMAC+-An Efficient Variable-output-length Variant of ZMAC.IACR Trans.Symmetric Cryptol.2017 volume 4.pp.306-325.

非专利文献6：Eik List，Mridul Nandi.Revisiting Full-PRF-Secure PMAC andUsing It for Beyond-Birthday Authenticated Encryption.CT-RSA 2017.pp.258-274.LNCS volume 10159.Springer.

发明内容

发明要解决的课题

为了在识别者D的查询次数成为q＝O(2

作为满足t

本发明的目的在于能够实现使用可调分组密码的安全性较高的消息认证算法。

用于解决课题的技术方案

本发明的消息认证装置关于1以上的整数t、n使用将t比特的Tweak作为输入并输出n比特的值的可调分组密码E生成消息M的认证码Z，其中，所述消息认证装置具备：

压缩部，所述压缩部将所述消息M压缩为2n比特的值H，并将值H分割为n比特的两个值H[1]和值H[2]；

Tweak计算部，所述Tweak计算部从所述值H[1]提取min{t，n/2}比特的两个值U[1]和值U[2]，将所述消息M和所述值U[1]作为输入而生成t比特的值V[1]，并且将所述消息M和所述值U[2]作为输入而生成t比特的值V[2]；

第一加密部，所述第一加密部使用所述值V[1]作为Tweak并利用所述可调分组密码E加密所述值H[2]而生成值Z[1]，并且使用所述值V[2]作为Tweak并利用所述可调分组密码E加密所述值H[2]而生成值Z[2]；以及

认证码生成部，所述认证码生成部根据所述值Z[1]和所述值Z[2]生成所述认证码Z。

发明的效果

在本发明中，能够实现使用可调分组密码的安全性较高的消息认证算法。

附图说明

图1是实施方式1的消息认证装置10的结构图。

图2是实施方式1的消息认证装置10的整体动作的流程图。

图3是利用实施方式1的消息认证装置10实现的消息认证算法的说明图。

图4是实施方式1的压缩处理的流程图。

图5是实施方式1的压缩处理的说明图。

图6是实施方式1的函数F的流程图。

图7是变形例1的消息认证装置10的结构图。

图8是示出变形例1的消息认证装置10的结构例的图。

具体实施方式

实施方式1.

***结构的说明***

参照图1，说明实施方式1的消息认证装置10的结构。

消息认证装置10具备处理器11、内存(memory)12、存储器(storage)13及通信接口14这些硬件。处理器11经由信号线与其他硬件连接，并控制这些其他硬件。

处理器11是进行处理的IC(Integrated Circuit：集成电路)。作为具体例，处理器11是CPU(Central Processing Unit：中央处理单元)、DSP(Digital Signal Processor：数字信号处理器)、GPU(Graphics Processing Unit：图形处理器)。

内存12是暂时存储数据的存储装置。作为具体例，内存12是SRAM(Static RandomAccess Memory：静态随机存取存储器)、DRAM(Dynamic Random Access Memory：动态随机存取存储器)。

存储器13是保管数据的存储装置。作为具体例，存储器13是HDD(Hard DiskDrive：硬盘驱动器)。另外，存储器13可以是SD(注册商标，Secure Digital：安全数字)存储卡、CF(CompactFlash：压缩闪存，注册商标)、NAND闪存、软盘、光盘、高密度盘、蓝光(注册商标)盘、DVD(Digital Versatile Disk：数字通用光盘)这样的可移动记录介质。

通信接口14是用于与外部的装置进行通信的接口。作为具体例，通信接口14是Ethernet(注册商标)、USB(Universal Serial Bus：通用串行总线)、HDMI(注册商标，High-Definition MultimediaInterface：高清多媒体接口)的端口。

作为功能构成要素，消息认证装置10具备通信部21、压缩部22、Tweak计算部23、第一加密部24及认证码生成部25。压缩部22具备M

在存储器13中存储有实现消息认证装置10的各功能构成要素的功能的程序。该程序由处理器11读取到内存12，并由处理器11执行。由此，实现消息认证装置10的各功能构成要素的功能。

在图1中，仅示出一个处理器11。但是，处理器11可以是多个，多个处理器11可以协作地执行实现各功能的程序。

***动作的说明***

参照图2至图6，说明实施方式1的消息认证装置10的动作。

实施方式1的消息认证装置10的动作相当于实施方式1的消息认证方法。另外，实施方式1的消息认证装置10的动作相当于实施方式1的消息认证程序的处理。

参照图2及图3，说明实施方式1的消息认证装置10的整体动作。

消息认证装置10关于1以上的整数t、n使用将t比特的Tweak作为输入并输出n比特的值的可调分组密码E生成消息M的认证码Z。在此，消息认证装置10使用可调分组密码E

作为以下动作的前提，消息认证装置10将与消息M的发送目的地共享的密钥K存储于存储器13。

(步骤S1：输入处理)

通信部21经由通信接口14受理由消息认证装置10的利用者操作输入装置等并输入的消息M。通信部21将消息M写入内存12。

(步骤S2：压缩处理)

压缩部22从内存12读取消息M。压缩部22使用函数Hash，将消息M压缩为2n比特的值H。压缩部22将值H分割为n比特的两个值H[1]和值H[2]。压缩部22将值H[1]和值H[2]写入内存12。

(步骤S3：Tweak计算处理)

Tweak计算部23从内存12读取值H[1]。

Tweak计算部23从值H[1]提取min{t，n/2}比特的两个值U[1]和值U[2]。作为具体例，Tweak计算部23从值H[1]的开头提取min{t，n/2}比特作为值U[1]，从值H[1]的末端提取min{t，n/2}比特作为值U[2]。此外，也可以使用利用b比特的置换函数p计算得到的值p(H[1])代替值H[1]来提取值U[1]和值U[2]。

Tweak计算部23通过将消息M和值U[1]作为输入来计算函数F[1]，从而生成t比特的值V[1]。另外，Tweak计算部23通过将消息M和值U[2]作为输入来计算函数F[2]，从而生成t比特的值V[2]。

Tweak计算部23将值V[1]和值V[2]写入内存12。

(步骤S4：第一加密处理)

第一加密部24从内存12读取值V[1]、值V[2]及值H[2]。

第一加密部24使用值V[1]作为Tweak并利用可调分组密码E加密值H[2]，从而生成值Z[1]。另外，第一加密部24使用值V[2]作为Tweak并利用可调分组密码E加密值H[2]，从而生成值Z[2]。第一加密部24将值Z[1]和值Z[2]写入内存12。

具体而言，关于i＝1，2这些各整数i，第一加密部24使用index(i，|M|)作为Tweak的第一参数，使用值V[i]作为Tweak的第二参数。在此，|M|是消息M的比特长度。index是将[1，s]的值和消息的比特长度|M|作为输入并输出[1，s]的值的函数。然后，第一加密部24通过利用可调分组密码E加密值H[2]，从而生成值Z[i]。此时，第一加密部24使用存储于存储器13的密钥K。也就是说，第一加密部24计算Z[i]＝E

(步骤S5：认证码生成处理)

认证码生成部25从内存12读取值Z[1]和值Z[2]。认证码生成部25根据值Z[1]和值Z[2]生成消息M的认证码Z。作为具体例，认证码生成部25将值Z[1]与值Z[2]的逻辑异或生成为认证码Z。认证码生成部25将认证码Z写入内存12。

(步骤S6：发送处理)

通信部21从内存12读取消息M和认证码Z。通信部21经由通信接口14将消息M和认证码Z发送给发送目的地。

参照图4及图5，说明实施方式1的压缩处理(图2的步骤S2)。

在以下的说明中，将值c设为满足0≤c≤t的整数。另外，设为值d＝t-c。

(步骤S21：M

M

M

M

(步骤S22：分割处理)

分割部32从内存12读取值M

(步骤S23：第二加密处理)

关于i＝1，…，L这些各整数i，第二加密部33从内存12读取值M[i]。第二加密部33将值M[i]分割为n比特的值A[i]和d比特的值B[i]。第二加密部33使用t比特的值T作为Tweak，利用可调分组密码E加密值A[i]而生成值C[i]，所述t比特的值T根据值B[i]、用c比特表达值i的值str

具体而言，第二加密部33使用0作为Tweak的第一参数，使用t比特的值T作为Tweak的第二参数。例如，值T＝str

(步骤S24：H计算处理)

H计算部34从内存12读取关于i＝1，…，L这些各整数i的值C[i]。H计算部34使用关于i＝1，…，L这些各整数i的所述值C[i]，计算值H。然后，H计算部34根据值H计算值H[1]和值H[2]。此外，H计算部34也可以在不计算值H的情况下计算值H[1]和值H[2]。

作为具体例，H计算部34计算关于i＝1，…，L这些各整数i的值C[i]的逻辑异或而生成值H[1]。也就是说，H计算部34如数学式7所示那样计算值H[1]。

[数学式7]

另外，H计算部34关于i＝1，…，L这些各整数i计算值C[i]与值x

[数学式8]

参照图6说明实施方式1的函数F。

函数F是在Tweak计算处理(图2的步骤S3)中使用的函数。在以下的说明中，作为压缩处理(图2的步骤S2)，应用参照图4及图5说明的方法。

(步骤S31：W生成处理)

W生成部41从内存12读取关于i＝1，…，L这些各整数i的值B[i]。值B[i]是在图4的步骤S23中生成的值。

W生成部41计算关于i＝1，…，L这些各整数i的值B[i]的逻辑异或而生成值B。也就是说，W生成部41如数学式9所示那样计算值B。

[数学式9]

W生成部41向值B附加比特而生成t比特的值W。作为具体例，W生成部41在值B的末端附加一个以上的0的比特而生成t比特的值W。也就是说，W＝B||0…0。W生成部41将值W写入内存12。

此外，不限于附加一个以上的0的比特，W生成部41可以附加一个以上的1的比特，也可以附加将0和1组合而成的比特串。另外，W生成部41可以在值B的开头附加比特，也可以在值B中的其他任意位置附加比特，而不是在值B的末端附加比特。

(步骤S32：U'生成处理)

关于i＝1，2这些各整数i，U'生成部42在值U[i]不是t比特的情况下，向值U[i]附加比特而生成t比特的值U'[i]。值U[i]是在图2的步骤S3中提取的值。作为具体例，U'生成部42在值U[i]的末端附加一个以上的0的比特而生成t比特的值U'[i]。

此外，不限于附加一个以上的0的比特，U'生成部42可以附加一个以上的1的比特，也可以附加将0和1组合而成的比特串。另外，U'生成部42可以在值U的开头附加比特，也可以在值U中的其他任意位置附加比特，而不是在值U的末端附加比特。

另外，关于i＝1，2这些各整数i的U'生成部42在值U[i]是t比特的情况下，将值U[i]设定为值U'[i]。

U'生成部42将关于i＝1，2这些各整数i的值U'[i]写入内存12。

(步骤S33：V生成处理)

V生成部43从内存12读取值W和关于i＝1，2这些各整数i的值U'[i]。

关于i＝1，2这些各整数i，V生成部43计算值W与值U'[i]的逻辑异或而生成值V[i]。也就是说，V生成部43如数学式10所示那样计算值V[i]。

[数学式10]

以下说明实施方式1的index函数。

index函数是在第一加密处理(图2的步骤S4)中使用的函数。在以下的说明中，作为压缩处理(图2的步骤S2)，应用参照图4及图5说明的方法。另外，在此，设为s＝4。也就是说，设为Set(T)＝[0，4]×{0，1}

index函数对于作为输入的整数i和比特长度|M|，在比特长度|M|是n+d的倍数的情况下输出i，在不是n+d的倍数的情况下输出2i。也就是说，在比特长度|M|是n+d的倍数的情况下，index(i，|M|)＝i，在不是n+d的倍数的情况下，index(i，|M|)＝2i。

或者，index函数对于作为输入的整数i和比特长度|M|，在比特长度|M|是n+d的倍数的情况下输出2i，在不是n+d的倍数的情况下输出i。也就是说，在比特长度|M|是n+d的倍数的情况下，index(i，|M|)＝2i，在不是n+d的倍数的情况下，index(i，|M|)＝i。

***实施方式1的效果***

如以上那样，实施方式1的消息认证装置10实现使用可调分组密码的消息认证算法。

利用实施方式1的消息认证装置10实现的消息认证算法能够示出数学式11所示的伪随机数性的优势的边界。

[数学式11]

由此，在n/2≤t的情况下，能够在查询次数成为q＝O(2

在此，在将n固定的情况下，与满足n≤t的条件的可调分组密码相比，满足t

***其他结构***

<变形例1>

在实施方式1中，用软件实现各功能构成要素。但是，作为变形例1，各功能构成要素可以用硬件实现。关于该变形例1，说明与实施方式1不同的点。

参照图7说明变形例1的消息认证装置10的结构。

在各功能构成要素用硬件实现的情况下，消息认证装置10具备电子电路15代替处理器11。电子电路15是实现各功能构成要素的功能的专用电路。

作为电子电路15，设想了单一电路、复合电路、程序化的处理器、并联程序化的处理器、逻辑IC、GA(Gate Array：门阵列)、ASIC(Application Specific IntegratedCircuit：专用集成电路)、FPGA(Field-Programmable Gate Array：现场可编程门阵列)。

可以用一个电子电路15实现各功能构成要素，也可以使各功能构成要素分散于多个电子电路15来实现。

例如，如图8所示，消息认证装置10具备可调分组密码用的电子电路15A、哈希函数(hash function)用的电子电路15B及最终处理用的电子电路15C作为电子电路15。

可调分组密码用的电子电路15A进行可调分组密码E的计算。哈希函数用的电子电路15B进行压缩处理(图2的步骤S2)。最终处理用的电子电路15C进行Tweak计算处理、第一加密处理及认证码生成处理(图2的步骤S3至步骤S5)。但是，最终处理用的电子电路15C使可调分组密码用的电子电路15A执行可调分组密码E的计算。

<变形例2>

作为变形例2，可以一部分各功能构成要素用硬件实现，其他各功能构成要素用软件实现。

将处理器11、内存12及电子电路15称为电子电路。也就是说，各功能构成要素的功能利用电子电路实现。

附图标记的说明

10 消息认证装置，11 处理器，12 内存，13 存储器，14 通信接口，21 通信部，22压缩部，23 Tweak计算部，24 第一加密部，25 认证码生成部，31 M