消息认证码生成装置、消息认证码验证装置和认证系统的制作方法
专利名称：消息认证码生成装置、消息认证码验证装置和认证系统的制作方法
技术领域：
本发明涉及信息安全技术，尤其涉及使用了消息认证码(MACMessage Authentication Code)的认证技术。
背景技术：
随着信息通信网络的发展，对电子信息的隐藏和认证所用的加密技术成为不可缺少的要素。作为加密技术要求的要件，除安全性之外，有处理速度和较少存储器使用量等，一般来说安全性、处理速度和存储器使用量之间有平衡关系，很难满足所有的要件。
加密技术有对称加密和公钥加密。对称加密有进行消息的加密·解密的所谓加密和用于表示消息的真实性的消息认证。
消息认证中，对所提供的消息，使用密钥生成作为用于表示其真实性的数据的消息认证码(第一消息认证码)。在消息的真实性的确认到认证中，对所提供的消息，使用与上述密钥相同的密钥再次生成消息认证码(第二消息认证码)，并根据这些消息认证码是否一致来加以判断。关于消息认证的方法(尤其是OMAC和PMAC)记载在T.Iwata and K.Kurosawa，“OMACOne-key CBCMAC”，in the proceedings of Fast Software Encryption(FSE 2003)，Lecture Note in Computer Science 2887，Springer-Verlag，pp.129-153，(2003).(称作文献1)和J.Black and P.Rogaway，“A Block-Cipher Mode of Operation for Parallelizable Message Authentication”，inthe proceedings of EUROCRYPT 2002，Lecture Note in ComputerScience 2332，Springer-Verlag，pp.384-397，(2002).(称作文献2)中。
此外，作为加密技术的安全性，除了以统计分析等数学理论为前提之外，还要求对旁道攻击这样的攻击的耐性，该旁道攻击使用在加密执行时从加密装置观测的物理量、例如计算时间和耗电量等来确定保密信息。关于旁道攻击记载在P.C.Kocher，J.Jaffe，andB.Jun，“Differential Power Analysis”，in the proceedings ofCRYPTO 1999，Lecture Note in Computer Science 1666，Springer-Verlag，pp.388-397，(1999).(称作文献3)中。
此外，关于对消息认证的旁道攻击，记载在K.Okeya，andT.Iwara，“Side Channel Attacks on Message Authentication Codes”，inthe proceedings of Security and Privacy in Ad-hoc and Sensor NetworksSecond European Workshop，ESAS 2005，Lecture Note in ComputerScience 3813，Springer-Verlag，pp.205-217，(2005).(称作文献4)中。在消息认证中存在如下这种异或逻辑(XOR)的情况下，该消息认证对旁道攻击脆弱。即，是如下这种情况对于异或逻辑的两个输入，一个是固定值且对攻击者来说是秘密的值，另一个对攻击者来说是已知的值，并且攻击者可以改变该值。
如果如前所述使用消息认证，则可以验证消息的真实性。但是，在所述文献1、2的技术中，提供了消息认证的方法，却没有充分考虑对旁道攻击的耐性。
发明内容
本发明鉴于上述这种问题而作出，提供一种对旁道攻击安全的消息认证技术。
本申请中公开的发明中，若简单说明代表技术的概要，则为如下这样。本发明是使用了消息认证码(根据需要简称为MAC)的消息认证技术，其特征在于，具有下面所示的技术手段。
(1-1)本发明的装置(消息认证码生成装置)根据消息(作为消息认证码对象的数据用记号M来表示)计算(生成)消息认证码(MAC用记号C或T表示)，其特征在于，通过具有如下所示的干扰信息生成部、消息变换部和认证码(MAC)计算部的各部分来执行所对应的处理。干扰信息生成部使用暂时使用数值(nonce用记号N来表示)进行生成干扰信息(用记号R表示)的处理(干扰信息生成处理)。消息变换部进行根据上述消息M计算变换消息(用记号M’来表示)的处理(消息变换处理)。认证码计算部进行根据上述干扰信息R和上述变换消息M’计算上述消息认证码C的处理(认证码计算处理)。由此，实现对旁道攻击安全的消息认证的方法和根据该方法进行处理动作的装置。
(1-2)此外，本装置中，也可以是，通过执行对上述暂时使用数值N加密(尤其是块加密E)的处理步骤来进行生成上述干扰信息R的处理。
(1-3)此外，本装置中，也可以是，通过将上述消息M分割为消息块(用符号B及M[i]表示)，并执行对该消息块B加密(尤其是块加密E)的处理步骤，来进行计算上述消息M’的处理。
(1-4)此外，本装置中，也可以是，根据作为公知技术的OMAC(One-key CBC MAC)或PMAC(Parallelizable MAC)的处理，来进行计算上述消息认证码C的处理。
在OMAC适用的结构中，在认证码计算部及其处理中，例如按每个消息块B的变换消息M’，具有异或逻辑或算术相加得到的相加和加密(块加密)。该结构中，计算最初(第一)的消息块的变换消息M’和干扰信息R的相加，并加密该输出，来得到第一处理结果。接着，计算第二消息块的变换消息M’和上述第一处理结果的相加，并加密该输出，来得到第二处理结果。之后，同样地进行连锁处理，计算第m消息块的变换消息M’和第(m-1)的处理结果的相加，并加密该输出，获得该第m处理结果作为消息认证码T。
在PMAC适用的结构中，在认证码计算部及其处理中，例如按每个消息块B的变换消息M’，具有异或逻辑或算术相加得到的第一(第一种)相加、加密(块加密)和异或逻辑或算术相加得到的第二(第二种)相加。该结构中，计算最初(第一)的消息块的变换消息M’和γ1L的第一相加，并加密该输出，通过该输出与干扰信息R的第二相加，得到第一处理结果。接着，计算第二消息块的变换消息M’和γ2L的第一相加，并加密该输出，通过该输出和第二处理结果的第二相加，得到第二处理结果。之后同样地进行连锁处理，计算第(m-1)的消息块的变换消息M’和γm-1L的第一相加，并加密该输出，通过该输出和第(m-2)的处理结果的第二相加，得到第(m-1)的处理结果。最后，计算第m的消息块的变换消息M’和第(m-1)的处理结果的相加，并加密该输出，获得第m处理结果作为消息认证码T。
(1-5)此外，本装置中，也可以如下这样进行计算上述消息认证码C的处理。在认证码计算部和处理中，执行以下步骤通过第一相加和加密，根据上述变换消息M’生成第一中间数据d1的处理步骤；使用上述干扰信息R变换上述第一中间数据d1，来生成第二中间数据d2的处理步骤；使用Lu-1，根据上述第二中间数据d2生成第三中间数据d3的处理步骤；使用上述干扰信息R变换上述第三中间数据，来生成第四中间数据d4的处理步骤；以及通过加密，根据上述第四中间数据d4计算上述消息认证码C的处理步骤。
本结构中，在认证计算部和处理中，例如按每个基于消息块B的变换消息M’，具有基于异或逻辑或算术相加的第一(第一种)相加、加密(块加密)、基于异或逻辑或算术相加的第二(第二种)相加和基于异或逻辑或算术相加的第三(第三种)的相加。该结构中，计算最初(第一)的消息块的变换消息M’和γ1L的第一相加，并加密该输出，通过该输出(第一中间数据d1)和干扰信息R的第二相加，得到第一处理结果(第二中间数据d2)。接着，计算第二消息块的变换消息M’和γ2L的第一相加，并加密该输出，通过该输出d1和第一处理结果d2的第二相加，得到第二处理结果d2。之后相同地进行连锁处理，计算第(m-1)的消息块的变换消息M’和γm-1L的第一相加，并加密该输出，通过该输出d1和第(m-2)的处理结果d2的第二相加，得到第(m-1)的处理结果(第d2)。并且，得到下述输出(第三中间数据d3)，该输出计算了第m的消息块的变换消息M’、第(m-1)的处理结果(d2)和Lu-1的相加。并且，得到了将该输出d3和与所述最初(第一)的处理中使用的信息相同的干扰信息R相加后的输出(第四中间数据d4)，获得加密该输出d4后的第m处理结果作为消息认证码T。
(2)本发明的装置(消息认证码验证装置)根据消息(作为消息认证对象的数据M)和第一消息认证码(C1验证前)的输入，进行验证上述消息M的真实性的处理(消息认证码验证处理或消息认证处理)，执行根据上述消息M和暂时使用数值N生成第二消息认证码(C2用于验证)的处理(消息认证码生成处理)、和比较上述第一消息认证码C1和上述第二消息认证码C2来得到其结果的处理。在生成上述消息认证码C1、C2的处理中，使用所述(1)这样的消息认证码生成装置或其处理来进行。
(3)本发明的系统(消息认证系统)在消息认证码验证装置中验证来自消息认证码生成装置的消息和第一消息认证码C1，所述(1)这样的消息认证码生成装置进行生成所述第一消息认证码C1的处理，将所述消息和第一消息认证码C1发送到如所述(2)这样的消息认证码验证装置，在如所述(2)这样的消息认证码验证装置中，进行根据所述消息生成第二消息认证码C2的处理、和进一步比较所述第一消息认证码C1和所述第二消息认证码C2来得到结果的处理。
发明的效果本申请所公开的发明中，若简单说明代表性的发明所得到的效果，则如下这样。根据本发明，可以提供一种对旁道攻击安全的消息认证的技术。
图1是表示本发明的实施方式1～3中的消息认证系统的结构图；图2是表示本发明的实施方式1～3中的消息认证码处理部的结构图；图3是示例了本发明的实施方式1～3中的消息认证码生成处理中的信息的交换的时序图；图4是示例了本发明的实施方式1～3中的消息认证码生成方法和处理的概要的流程图；图5是示例了实施方式1中的消息认证码生成方法及其框图结构和处理的图；图6是示例了实施方式1中的消息认证码生成方法和处理的细节的流程图；图7是示例了实施方式2中的消息认证码生成方法及其框图结构和处理的图；图8是表示实施方式2中的消息认证码生成方法和处理的细节的流程图；图9是表示实施方式3中的消息认证码生成方法及其框图结构和处理的图；图10是表示实施方式3中的消息认证码生成方法和处理的细节的流程图。
具体实施例方式
下面，根据附图来详细说明本发明的实施方式。此外，在说明实施方式用的所有图中，原则上对同一部件添加同一符号，而省略其重复的说明。
(实施方式1)图1～图6表示本发明的实施方式1的结构。图1表示适用了基于本发明的消息认证码计算方法的实施方式1的消息认证系统、消息认证码生成装置和消息认证码验证装置的结构。
<系统结构>
图1中，表示出作为消息认证码(MAC)生成装置的计算机(A)101和作为消息认证码(MAC)验证装置的计算机(B)121通过网络142连接的系统结构。计算机(A)101和(B)121是具有MAC处理部112、132的MAC处理装置，计算机(A)101特别是具有生成MAC的功能的MAC生成装置，计算机(B)121特别是具有验证MAC的功能的MAC验证装置。计算机(A)101、(B)121的MAC处理部112、132是主要特征部，但也可具有与安全处理等有关的其他处理功能。例如，是具有MAC处理部112、132来作为加密处理模块的一部分的结构。计算机(A)101和(B)121是构成整体的消息认证系统所对应的装置，是具有公共的部分(尤其是MAC生成功能)的结构。
首先，下面是本系统中的消息认证处理的概要。图1的消息认证系统中的计算机(A)101和(B)121预先私下秘密共用用于加密处理的密钥K。
计算机(A)101使用上述密钥K，生成对消息M的消息认证码(第一MACC1)。计算机(A)101将上述消息M和上述生成的消息认证码C1作为数据141，通过网络142发送到计算机(B)121。
计算机(B)121使用上述共用的密钥K，对所接收的作为数据141的消息M和消息认证码C1进行验证消息M的真实性的处理。消息M的真实性验证中，使用上述密钥K重新生成对上述消息M的消息认证码(第二MACC2)，并通过比较再次生成的消息认证码C2和所接收的消息认证码C1是否一致，来判断验证结果。即，在一致的情况下，判断为保证了消息M的真实性，在不一致的情况下，判断为不保证消息M的真实性。当然，由于上述消息认证码C2的重新生成的时刻是验证前，所以不能保证通过计算机(B)121和(A)101生成同一内容的数据。例如，有可能上述接收的消息识别符C1是被窜改后的数据。计算机(B)121将验证结果等作为数据143返还给计算机(A)101。
仅向网络142发送消息M和消息认证码C，不发送密钥K。由于消息认证码C的生成中使用了密钥K，所以仅保持有密钥K的计算机可以生成消息认证码C。在由上述计算机(B)121再次生成的消息认证码C2与上述接收的消息认证码C1一致的情况下，表示上述接收的消息认证码C1由保持同一密钥K的计算机(即计算机(A)101)生成。换而言之，表示在通过网络142发送数据141时，没有窜改消息M和消息认证码C，即，表示了消息M的真实性。
<装置结构>
接着说明装置结构等。计算机(A)101和(B)121例如可以是IC卡或是其中装载的IC芯片的形态，或者也可以是PC等形态。计算机(B)121除了与计算机(A)101相同的MAC生成功能之外，还具有MAC验证(比较)功能。
计算机(A)101包括CPU(主处理装置)113和协处理器(数值计算用处理装置)114等运算装置(包含在处理器111中)、RAM103、ROM106和外部存储装置107等存储装置、进行与计算机(A)101的外部之间的数据输入输出用的输入输出接口110等。计算机(A)101的外部连接用户操作计算机(A)101用的显示器(显示装置)108、键盘(输入装置)109和可装卸的可移动型存储媒体的读写装置等。另外，计算机(A)101通过输入输出接口110与网络142相连。
进一步，计算机(A)101通过上述存储装置实现存储部102，上述运算装置通过执行存储部102中存储的程序，来实现作为处理部111的一部分的消息认证码(MAC)处理部112。MAC处理部112生成对应所输入的消息M的消息认证码C1。处理部111使用MAC处理部112进行与消息认证有关的处理等。存储部102在例如RAM103中安全地存储常数(例如初始值和比特长度等参数)、保密信息105(例如密钥(K))等。
计算机(B)121具有与计算机(A)101相同的结构，主要处理部131不同。计算机(B)121通过RAM123、ROM126和外部存储装置127等存储装置来实现存储部122，CPU133和协处理器134等运算装置通过执行存储部122中存储的程序，来实现作为处理部131的一部分的MAC处理部132。MAC处理部132对所接收的消息M和消息认证码C1，通过消息认证码C2的再次生成和比较，来验证消息M的真实性。处理部131使用MAC处理部132来进行与消息认证有关的处理等。存储部122在例如RAM123上安全地存储常数124、保密信息125(例如密钥K)等。
此外，在各实施方式的结构中，计算机(A)101、(B)121可以是下面的结构。计算机(A)101、(B)121内的程序和数据可以预先存储在存储部102、122上，需要时，可以经计算机(A)101、(B)121可使用的媒体和输入输出接口110、130，从其他装置导入到上述存储部102、122中。进一步，计算机(A)101、(B)121内的程序和数据在需要时，也可通过经输入输出接口110、130连接的其他计算机或该计算机可使用的媒体导入到上述存储部102、122中。所谓上述可使用的媒体是指例如对该计算机可装卸的存储媒体或通信媒体(网络或在网络中传送的载波和数字信号等)。
另外，计算机(A)101和(B)121私下共用的上述密钥K除经输入输出接口110、130输入密钥K的数据之外，还可以通过输入将密钥K加密后的数据且计算机(A)101或(B)121解密该加密数据，来实现密钥K的共用。此外，还可以利用公钥加密的技术，将与公钥有关的信息经网络142发送到对方侧的计算机，并使用自己的保密信息从所接收的对方侧公钥的信息中导出新的密钥，来实现密钥K的共用。
<MAC生成处理>
接着，参考图2～图4来说明图1的消息认证系统中的计算机(A)101的MAC处理部112所进行的MAC生成处理。实施方式1中，使用图2所示的功能块结构的MAC处理部112。
图2中，MAC处理部112包括干扰信息生成部210、消息变换部220和认证码计算部230。干扰信息生成部210具有块加密计算部211。消息变换部220具有填充部221和块加密计算部222。认证码计算部230具有逻辑算术运算部231和块加密计算部232。
MAC处理部112输入消息M和暂时使用数值N，并输出通过MAC生成处理生成的MAC认证码C。干扰信息生成部210以暂时使用数值N为基础来生成干扰信息R。消息变换部220以消息M为基础来生成变换消息M’。认证码计算部230以干扰信息R和变换消息M’为基础来计算消息认证码C。
各个块加密计算部进行DES和AES这样的块加密计算。将该块加密表示为符号E。块加密E具有预定比特长度(密钥长度)的密钥K和预定比特长度(块长度)的消息M0这两个输入，输出使用了密钥K的消息M0的加密结果EK(M0)。密钥长度和块长度也可以相同。此外，在不需要明确表示密钥K的情况下，可以如E(M0)那样，省略密钥K来加以标记。此外，本例中，块加密计算部分别包含在干扰信息生成部210、消息变换部220和认证码计算部230中，但是也可统合这些块加密计算部211、222、232，通过分别从干扰信息生成部210、消息变换部220和认证码计算部230调用来构成。通过这种结构，可以减少电路规模和程序代码。
填充部221通过每隔块长度来分割所输入的消息M，来对生成消息块B时的最后消息块B追加适当的二进制串，而使比特长度与块长度一致(填充(padding)处理)。逻辑算术运算部231进行异或逻辑(XOR)和算术相加这样的逻辑运算和算术运算。
图3示例了基于本MAC生成方法的计算机(A)101的MAC处理部112的MAC生成处理中的信息交换。图4示例同一MAC处理部112的MAC生成处理的概要。S表示处理步骤。
图3和图4中，首先，MAC处理部112作为输入接收消息M和暂时使用数值N(S301)。接着，MAC处理部112将暂时使用数值N送到干扰信息生成部210(S302)。接着，干扰信息生成部210使用暂时使用数值N来进行生成干扰信息R的干扰信息生成处理401。接着，干扰信息生成部210将所生成的干扰信息R送到MAC处理部112(S303)。
接着，MAC处理部112将消息M送到消息变换部220(S304)。接着，消息变换部220通过变换消息M(包含对消息块B的变换)来进行获得变换消息M’的消息变换处理(402)。接着，消息变换部220将所得到的变换消息M’送到MAC处理部112(S305)。
接着，MAC处理部112将干扰信息R和变换消息M’送到认证码计算部230(S306)。接着，认证码计算部230使用干扰信息R和变换消息M’来进行计算消息认证码T的认证码计算处理403。接着，认证码计算部230将计算所得到的消息认证码T送到MAC处理部112(S307)。
接着，MAC处理部112根据所接收的消息认证码T，决定对应消息M的消息认证码C(尤其是第一MACC1)并输出(S308)。
此外，对于上述暂时使用数值N，相同值的暂时使用数值N仅一次(限于该情况)用于消息认证码C的生成。即，对不同的消息M使用不同值的暂时使用数值N。作为暂时使用数值N的例子，有使用计数器或随机数的方法等。例如，计算机(A)101、(B)121具有计数器和随机数生成部，使用计数器的增加值和由随机数生成部生成的随机数值。
<第一结构>
实施方式1中，作为消息认证码说明以所述文献1记载的OMAC的方法为基础构成的例子(MAC处理部112的第一结构)。使用图5和图6，详细说明MAC处理部112中的干扰信息生成部210、消息变换部220和认证码计算部230进行的处理。图5示例了与图2的MAC处理部112对应的MAC生成方法和该框图结构与该处理。图6示例了同一MAC生成处理的细节。图5所示的块结构表示干扰信息生成部210进行的干扰信息生成处401、消息变换部220进行的消息变换处理402及认证码计算部230进行的认证码计算处理403与下面所示的详细处理之间的关联。
图5中，在第一结构中，干扰信息生成部210及其处理401中，对暂时使用数值N(502)进行块加密E(511)，来生成干扰信息R。消息变换部220及其处理402中，通过分割为预定块长度，从消息M(501)中得到消息块(B)M[1](521)～M[m](523)。10i(524)是填充用的值。另外，对上述各消息块(B)进行块加密E(531～533)，而得到变换消息M’。认证码计算部230及其处理403中，每个基于消息块B的变换消息M’具有异或逻辑(51～53)和块加密E(541～543)。该结构中，计算基于最初(第一)消息块(M[1])的变换消息(M’)和干扰信息R的异或逻辑51，来对该输出进行块加密E(541)，而得到第一处理结果。接着，计算基于第二消息块(M[2])的变换消息M’和上述第一处理结果的异或逻辑52，对该输出进行块加密E(542)，而得到第二处理结果。之后，同样地进行连锁处理，计算基于第m消息块(M[m])的变换消息M’和第(m-1)的处理结果的异或逻辑53，并对该输出进行块加密E(543)，获得该第m处理结果作为消息认证码(T)551。
图5和图6中，MAC处理部112将消息M和暂时使用数值N作为输入加以接收(S601)。干扰信息生成部210对暂时使用数值N，使用块加密计算部211来计算块加密E的加密结果E(N)，并将该结果E(N)作为干扰信息(R)存储到变量T1中(S602)。
MAC处理部112将消息M的块数代入到m，将1代入到变量j(S603)。这里所谓块数(m)是指每隔块长度分割消息M时的分割所得到的消息块(B)的数目。消息M(501)通过分割变为消息块(B)M[1]～M[m](521～523)。
MAC处理部112判断是否是j＜m(S611)。在该条件成立的情况下(TRUE)，进入到S612。在条件不成立的情况下(FALSE)，进入到S621。
在S611中条件成立的情况下，在S612中，消息变换部220对消息块M[j]，使用块加密计算部222来计算块加密E的加密结果E(M[j])，并将该结果作为变换消息(M’)的一部分存储到变量T2中(S612)。接着，认证码计算部230使用逻辑算术运算部231来计算变量T1和变量T2的异或逻辑(T1xor T2)，并将该结果存储在变量T1中(S613)。接着，认证码计算部230对变量T1，使用块加密计算部232来计算块加密E的加密结果E(T1)，并将其结果存储到变量T1中(S614)。接着，MAC处理部112将j+1代入到变量j，并返回到S611(S615)。
在S611中条件不成立的情况下，在S621中，消息变换部220使用填充部211，对消息块M[m](最后的消息块(B))进行填充(S621)。本例中，将对M[m]填充的值设作10i＝‘10...0’(524)。另外，在消息块M[m]的比特长度与用于分割的块长度一致的情况下，也可不进行填充。此外，这时，也可以是追加新的消息块M[m+1]来作为第(m+1)的消息块B的形态。在追加第(m+1)的消息块的情况下，对M[m]进行S612～S615的处理，对第(m+1)的消息块进行S621之后的处理。
接着，消息变换部220对作为最后的消息块B的、填充后的消息块M[m]|10...0使用块加密计算部222来计算块加密E的加密结果E(M[m]|10...0)，并将该结果作为变换消息M’的一部分存储在变量T2中(S622)。此外，“M[m]|10...0”这样的表现表示在M[m]的填充前的原始数据之后，作为填充(值)的一例添加了10i＝‘10...0’(前端是1，之后i个全部是0)。通过这种填充的添加，可以进行从M[m]中取出原始数据的处理等。
接着，认证码计算部230使用逻辑算术运算部231计算变量T1和变量T2的异或逻辑(T1xor T2)，并将其结果存储到变量T1中(S623)。接着，认证码计算部230对变量T1，使用加密计算部232来计算块加密E的加密结果E(T1)，将其结果作为认证码计算部230输出的消息认证码T存储到变量T1中(S624)。并且，MAC处理部112从变量T1中截出预定的比特数，来作为消息认证码(T尤其是C1)输出(S625)。
此外，上述处理还可以进行如下这种变形。S612、S623中进行的运算为异或逻辑(xor)，但是也可以是算术相加。也可在干扰信息生成部210内生成作为对干扰信息生成部210的输入的暂时使用数值N。这时，需要输出所生成的暂时使用数值N。
此外，在干扰信息生成部210、消息变换部220和认证码计算部230中使用的块加密E中的密钥K可以使用不同的密钥。此外，各块加密E的计算中也可以使用不同的密钥。但是，前提是在计算机(A)101侧生成MAC(C1)时和在计算机(B)121侧进行验证时重新生成MAC(C2)时，在各个对应的块加密E的计算中使用相同密钥。
此外，在上述说明中，说明了消息变换部220进行消息变换的情况，但是也可不进行消息变换。这时，有可能降低消息认证的安全性，但是由于可以减少块加密E的加密处理的次数，所以可以高速化。
此外，用于块加密E的密钥可以原样使用计算机(A)101和(B)121私下共用的密钥K，但是也可将从密钥K导出的值作为新的密钥。例如，也可以将EK(0)作为密钥。
此外，S621中，进行对第m消息块M[m]的填充，但是作为填充方式，除了追加10i＝‘10...0’(524)之外，也可追加‘01...1’或表示块数(m)的数值等其他值。
此外，上述说明是分别分割消息变换处理402和认证码计算处理403、并交替进行分割后的处理的情况。即，本例中，以首先是对第一消息M[1]的变换处理521、531、接着是对M[1]的计算处理51、541、接着是对第二消息M[2]的变换处理522、532、接着是对M[2]的计算处理52、542.....这样的顺序来加以处理。但是，也可在对所有的消息块M[1]～M[m]的消息变换处理402完成后，开始对这些所有的变换消息M’的认证码计算处理403。此外，只要在干扰信息生成处理部401和消息变换处理402之后进行认证码计算处理403即可，干扰信息生成部401和消息变换处理402的顺序可以是任何一个。例如，也可在消息变换处理402之后进行干扰信息生成处理401。
此外，在消息变换处理402中，也可以在变换处理即消息块(B)M[1]～M[m]的计算时，进行并行计算带来的高速化。例如，也可并行进行E(M[1])和E(M[2])的加密计算。另外，也可调换消息块B的计算顺序。例如，也可在E(M[2])的加密计算后，进行E(M[1])的加密计算。
此外，本例是将MAC处理部112的一系列的块加密E(公知技术)的整体具有对旁道攻击的耐性作为前提的结构，但是也可以为对各块加密E的计算分别实施应对旁道攻击的对策的结构。通过该结构，在消息认证码C的生成中，可以进一步增加安全性。
上述说明中以OMAC为例来构成，但是也可对其他CBC(Cipher-Block Chaining加密块链接)模式的消息认证码构成。CBC是块加密(CB)的使用方法(模式)的一个。OMAC是使用了CBC模式的MAC中的一个。
以上，根据本实施方式1，通过使用干扰信息R，来隐藏和干扰处理中的对异或逻辑(51～53)的输入值，而使旁道攻击无效化。细节如下。
上述旁道攻击是指在确定保密信息时需要固定值的输入和已知值的输入。根据所述文献4，在消息认证中存在如下这种异或逻辑的情况下，该消息认证对旁道攻击脆弱。其是如下的情况对于异或逻辑的两个输入，一个是固定值且对攻击者来说是秘密的值，另一个对攻击者来说是已知的值，攻击者可以改变该值。考虑这种情况，在与认证码计算处理部403对应的现有认证码计算处理部整体中，认为没有对旁道攻击的耐性。
另一方面，本实施方式1中，例如，若看异或逻辑51，则由于作为其一个输入值的干扰信息R是每次改变的值，即对攻击者来说是秘密的值，所以即使作为另一个输入值的变换消息M’对攻击者来说是已知的值，也不能预测出异或逻辑51的输出结果。对于其他异或逻辑51～53也相同，这样，在隐藏和干扰认证码计算部403中的对异或逻辑51～53的输入值的本实施方式1的结构中，可以实现旁道攻击的无效化。
如以上所说明的，实施方式1的上述消息认证和MAC生成的方法及处理具有对旁道攻击的耐性良好的特点。
(实施方式2)接着，参考图7～图8来说明本发明的实施方式2。实施方式2中，作为消息认证码说明以所述文献2记载的PMAC的方法为基础构成的例子(MAC处理部112的第二构成)。实施方式2中，基本上与实施方式1共通的结构中，主要是认证码计算处理403不同。
<第二结构>
使用图7和图8，来详细说明MAC处理部112中的干扰信息生成部210、消息变换部220和认证码计算部230进行的处理。图7的块结构表示干扰信息生成部210进行的干扰信息生成处理401、消息变换部220进行的消息变换处理402、认证码计算部230进行的认证码计算处理403与下面所示的详细处理之间的关联。
图7中，第二结构中，在干扰信息生成部210及其处理401中，对暂时使用数值N(702)进行块加密E(711)，而生成干扰信息R。在消息变换部220及其处理402中，通过分割为预定块长度，从消息M(701)中得到消息块(B)M[1](721)～M[m](724)。10i(725)是填充用的值。另外，对上述各消息块(B)进行块加密E(731～734)，而得到变换消息M’。在认证码计算部230及其处理403中，每个基于消息块B的变换消息M’，具有第一异或逻辑(71～73，77)、块加密E(751～754)和第二异或逻辑(74～76)。该结构中，计算基于最初(第一)消息块(M[1])的变换消息(M’)和γ1L(741)的异或逻辑71，来对该输出进行块加密E(751)，通过该输出和干扰信息R的异或逻辑74，得到第一处理结果。接着，计算基于第二消息块(M[2])的变换消息M’和γ2L(742)的异或逻辑72，来对该输出进行块加密E(752)，通过该输出和第一处理结果的异或逻辑75，得到第二处理结果。之后，同样地进行连锁处理，计算基于第(m-1)消息块(M[m-1])的变换消息M’和γm-1L(743)的异或逻辑73，来对该输出进行块加密E(753)，通过该输出和第(m-2)处理结果的异或逻辑76，得到第(m-1)处理结果。最后，计算基于第m消息块(M[m])的变换消息M’和第(m-1)的处理结果的异或逻辑77，对该输出进行加密754，获得将第m处理结果作为消息认证码T(761)。
图7和图8中，MAC处理部112将消息M和暂时使用数值N作为输入加以接收(S801)。接着，干扰信息生成部210对暂时使用数值N，使用块加密计算部211来计算块加密E的加密结果E(N)，并将该结果E(N)作为干扰信息(R)存储到变量T1中(S802)。接着，MAC处理部112将消息M的块数代入到m，将1代入到变量j(S803)。
接着MAC处理部112判断是否是j＜m(S811)。在该条件成立的情况下(TRUE)，进入到S812。在条件不成立的情况下(FALSE)，进入到S821。
在S811中条件成立的情况下，在S812中，消息变换部220对消息块M[j]，使用块加密计算部222来计算块加密E的加密结果E(M[j])，并将该结果作为变换消息(M’)的一部分存储到变量T2中(S812)。
接着，认证码计算部230使用逻辑算术运算部231计算变量T2和数值γjL的异或逻辑(T1xor γjL)，并将该结果存储在变量T2上(S813)。这里，L是由对0的块加密E的加密结果L＝EK(0)提供的数值，γj称作格雷码，对于各i，γi和γi+1仅1比特不同。具体的，设γ0＝0，对于i＝0，1，...，可以通过决定为γi+1＝γixor((0...01)＜＜ntz(i))来构成。其中，“a＜＜b”表示将a左移b比特，ntz(i)是用二进制表现来表示数值i时比特值是1的最右比特位置。例如，ntz(7)＝0、ntz(8)＝3。另外，γjL是γj和L的二进制的相乘结果。
接着，认证码计算部230对变量T2，使用块加密计算部232来计算块加密E的加密结果E(T2)，并将其结果存储到变量T2中(S814)。接着，认证码计算部230使用逻辑算术运算部231来计算变量T1和变量T2的异或逻辑(T1xor T2)，并将该结果存储到变量T1中(S815)。接着，MAC处理部112将j+1代入到变量j，并返回到S811(S816)。
在S811条件不成立的情况下，在S821中，消息变换部220使用填充部211，对消息块M[m]进行填充。另外，在消息块M[m]的比特长度与块长度一致的情况下，也可不进行填充。这时，也可以是追加新的消息块M[m+1]来作为第(m+1)的消息块B。在追加第(m+1)的消息块M[m+1]的情况下，对M[m]进行S812～S816的处理，对第(m+1)的消息块M[m+1]进行S821之后的处理。
接着，消息变换部220对填充后的消息块M[m]|10...0使用块加密计算部222来计算块加密E的加密结果E(M[m]|10...0)，并将该结果作为变换消息M’的一部分存储在变量T2中(S822)。接着，认证码计算部230使用逻辑算术运算部231计算变量T1和变量T2的异或逻辑(T1xor T2)，并将其结果存储到变量T1中(S823)。接着，认证码计算部230对变量T1，使用块加密计算部232来计算块加密E的加密结果E(T1)，并将该结果作为认证码计算部230输出的消息认证码T存储到变量T1中(S824)。接着，MAC处理部112从变量T1中截出预定的比特数，来作为消息认证码(T尤其是C1)输出(S825)。
上述处理还可以进行与实施方式1中说明的相同的各种变形。
以上，根据本实施方式2，隐藏和干扰对处理中的异或逻辑74～77的输入值，来实现旁道攻击的无效化。与实施方式1相同，实施方式2的消息认证和MAC生成的方法及处理具有对旁道攻击的耐性良好的特点。
(实施方式3)接着，参考图9～图10来说明本发明的实施方式3。实施方式3中，作为消息认证码以所述文献2记载的PMAC的方法为基础来构成，进一步，说明作为输出与原始的PMAC(已经确立的方法)所输出的消息认证码相同的值的消息认证码的结构的例子(MAC处理部112的第三结构)。实施方式3中，在基本上与实施方式1和2公共的结构中，主要是消息变换处理402和认证码计算处理403不同。实施方式3的消息变换部220不具有块加密计算部222。通过为这种结构，可以减少电路规模和程序代码大小。所述实施方式2中，对PMAC即使输入值M相同，输出值T也不同。实施方式3中，对本结构的PMAC，若其输入值M和原始的PMAC的输入值相同，则这些输出值T也相同。输出相同的情况在替换性等方面有好处。
<第三结构>
使用图9和图10来详细说明MAC处理部112中的干扰信息生成部210、消息变换部220和认证码计算部230进行的处理。图9的块结构表示干扰信息生成部210进行的干扰信息生成处理401、消息变换部220进行的消息变换处理402、认证码计算部230进行的认证码计算处理403与下面所示的详细处理之间的关联。
图9中，在第三结构中，在认证码计算部230及其处理403中，每个基于消息块B的变换消息M’，具有第一(第一种)异或逻辑(91～93)、块加密E(941～943)、第二(第二种)异或逻辑(94～97)和第三(第三种)异或逻辑(98)。使用认证码计算处理403中的各种处理中的中间数据(d1～d4)来加以说明。在该结构中，计算基于最初(第一)消息块的变换消息(M’)和γ1L(931)的第一异或逻辑91，对该输出进行块加密E(941)，通过该输出(第一中间数据d1)和干扰信息R的第二异或逻辑94，得到第一处理结果(第二中间数据d2)。接着，计算基于第二消息块的变换消息M’和γ2L(932)的第一异或逻辑92，并对该输出进行块加密E(942)，通过该输出d1和第一处理结果d2的第二异或逻辑95，得到第二处理结果d2。之后，同样地进行连锁处理，计算基于第(m-1)消息块的变换消息M’和γm-1L的第一相加，并加密该输出，通过该输出d1和第(m-2)的处理结果(d2)的第二相加，得到第(m-1)的处理结果d2。并且，得到计算了基于第m消息块的变换消息M’、第(m-1)的处理结果d2和Lu-1的相加后的输出(第三中间数据d3)。并且，得到将该输出d3和与所述最初(第一)处理中所用的信息相同的干扰信息R相加后的输出(第四中间数据d4)，从而获得加密该输出d4后的第m处理结果作为消息认证码T。
图9和图10中，MAC处理部112将消息M和暂时使用数值N作为输入加以接收(S1001)。接着，干扰信息生成部210对暂时使用数值N，使用块加密计算部211计算块加密E的加密结果E(N)，并将该结果作为干扰信息(R)存储到变量T1及T3中(S1002)。接着，MAC处理部112将消息M的块数代入到m，将1代入到变量j(S1003)。
接着，MAC处理部112判断是否是j＜m(S1011)。在该条件成立的情况下(TRUE)，进入到S1012。在条件不成立的情况下(FALSE)，进入到S1021。
在S1011中条件成立的情况下，在S1012中，消息变换部220将消息块M[j]的值作为变换消息M’的一部分存储在变量T2中(S1012)。接着，认证码计算部230使用逻辑算术运算部231计算变量T2和数值γjL的异或逻辑(T2xor L)，并将该结果存储在变量T2上(S1013)。
接着，认证码计算部230对变量T2，使用块加密计算部232来计算块加密E的加密结果E(T2)，并将其结果存储到变量T2中(S1014)。接着，认证码计算部230使用逻辑算术运算部231计算变量T1和变量T2的异或逻辑(T1xor T2)，并将其结果存储到变量T1中(S1015)。接着，MAC处理部112将j+1代入到变量j，并返回到S1011(S1016)。
在S1011中条件不成立的情况下，在S1021中，消息变换部220使用填充部221，对消息块M[m]进行填充，并将其结果作为变换消息M’的一部分。此外，在消息块M[m]的比特长度与块长度一致的情况下，不进行填充。
接着，认证码计算部230对填充后的消息块M[m]|10...0使用块加密计算部232来计算块加密E的加密结果E(M[m]|10...0)，并将该结果存储在变量T2中(S1022)。接着，认证码计算部230使用逻辑算术运算部231计算变量T1、变量T2和数值Lu-1(944)的异或逻辑(T1xor T2xor Lu-1)，并将其结果存储到变量T1中(S1023)。其中，在消息块M[m]和块长度一致的情况，即不进行填充的情况，进行与数值Lu-1的异或逻辑。在不进行填充的情况下，使用逻辑算术运算部231计算异或逻辑(T1xor T2)，并将其结果存储到变量T1中。另外，u是表示“0...010”的数值，u-1是二进制中的u的倒数。即，u-1是在二进制的相乘中满足u u-1＝1的数值。Lu-1是L和u-1在二进制中的相乘结果。
接着，认证码计算部230使用逻辑算术运算部231计算变量T1和变量T3的异或逻辑(T1xor T3)，并将其结果存储到变量T1中(S1024)。接着，认证码计算部230对T1，使用块加密计算部232来计算块加密E的加密结果E(T1)，并将该结果作为认证码计算部230输出的消息认证码(T)存储到变量T1中(S1025)。接着，MAC处理部112从变量T1中截出预定的比特数，来作为消息认证码(T尤其是C1)输出(S1026)。
在认证码计算处理403中的块加密E后的通过异或逻辑94、98的处理中，在S1015中通过最初的异或逻辑94添加的干扰信息R在S1024中通过最后的异或逻辑94来加以取消(消除)。因此，本实施方式3中输出的消息认证码T的值与原始的PMAC输出的消息认证码的值相等。
此外，上述处理还可以进行与实施方式1中说明的相同的各种变形。
以上，根据本实施方式3，隐藏和干扰对处理中的异或逻辑94～98的输入值，来实现旁道攻击的无效。与实施方式1和2相同，实施方式3的消息认证和MAC生成的方法和处理对旁道攻击的耐性好，此外，具有输出与原始的PMAC相同的消息认证码的特点。
以上，根据实施方式具体说明了本发明人进行的发明，但是本发明并不限于所述实施方式，当然可以在不脱离其主旨的范围内进行各种改变。例如，各实施方式中的MAC处理部、干扰信息生成部、消息变换部、认证码计算部、逻辑算术运算部、块加密计算部和填充部等的处理可以使用协处理器或专用的硬件来进行。
产业上的可用性本发明可以用于使用了消息认证的信息处理装置等中。
权利要求
1.一种消息认证码生成装置，根据消息计算对所述消息的消息认证码，其特征在于，包括干扰信息生成部，进行使用暂时使用数值生成干扰信息的处理；消息变换部，进行根据所述消息计算变换消息的处理；以及认证码计算部，进行根据所述干扰信息和所述变换消息计算所述消息认证码的处理。
2.根据权利要求1所述的消息认证码生成装置，其特征在于，在所述干扰信息生成部所进行的生成所述干扰信息的处理中，执行对所述暂时使用数值进行加密的处理步骤。
3.根据权利要求2所述的消息认证码生成装置，其特征在于，在所述消息变换部所进行的计算所述变换消息的处理中，执行将所述消息分割为消息块，并对所述消息块进行加密的处理步骤。
4.根据权利要求3所述的消息认证码生成装置，其特征在于，所述认证码计算部所进行的计算所述消息认证码的处理是使用了OMAC的处理。
5.根据权利要求3所述的消息认证码生成装置，其特征在于，所述认证码计算部所进行的计算所述消息认证码的处理是使用了PMAC的处理。
6.根据权利要求2所述的消息认证码生成装置，其特征在于，在所述认证码计算部所进行的计算所述消息认证码的处理中，执行下述步骤根据所述变换消息生成第一中间数据的处理步骤；使用所述干扰信息变换所述第一中间数据，并生成第二中间数据的处理步骤；根据所述第二中间数据生成第三中间数据的处理步骤；使用所述干扰信息变换所述第三中间数据，并生成第四中间数据的处理步骤；以及根据所述第四中间数据计算所述消息认证码的处理步骤。
7.根据权利要求4所述的消息认证码生成装置，其特征在于，在所述认证码计算部所进行的计算所述消息认证码的处理中，执行按每个基于所述消息块的变换消息进行使所述干扰信息作用的异或逻辑或基于算术相加的加法、以及其输出的加密的处理步骤，并进行连锁处理。
8.根据权利要求5所述的消息认证码生成装置，其特征在于，在所述认证码计算部所进行的计算所述消息认证码的处理中，执行按每个基于所述消息块的变换消息进行使格雷码与对0的加密结果的二进制的相乘结果(γjL)作用的异或逻辑或基于算术相加的第一相加、其输出的加密、以及使所述干扰信息作用的异或逻辑或基于算术相加的第二相加的处理步骤，并进行连锁处理。
9.一种消息认证码验证装置，根据消息和用于验证所述消息的真实性的第一消息认证码，验证所述消息的真实性，其特征在于，执行下述步骤进行根据所述消息和暂时使用数值生成第二消息认证码的处理的处理步骤；以及进行比较所述第一消息认证码和所述第二消息认证码来得到结果的处理的处理步骤；在生成所述第二消息认证码的处理步骤中，执行下述步骤进行使用所述暂时使用数值生成干扰信息的处理的处理步骤；进行根据所述消息计算变换消息的处理的处理步骤；以及进行根据所述干扰信息和所述变换消息计算所述第二消息认证码的处理的处理步骤。
全文摘要
提供一种对旁道攻击安全的消息认证技术。在根据消息(M)计算对消息(M)的消息认证码(T)的消息认证码生成装置中，进行根据暂时使用数值(N)生成干扰信息(R)的处理(401)、根据消息(M)计算变换消息(M’)的处理(402)和根据干扰信息(R)和变换消息(M’)计算消息认证码(T)的处理(403)。在计算消息认证码(T)的处理(403)中，由于通过干扰信息(R)干扰或隐藏了处理信息，所以实现了对旁道攻击安全的消息认证。
文档编号G09C1/00GK101060408SQ20071009707
公开日2007年10月24日 申请日期2007年4月17日 优先权日2006年4月17日
发明者桶屋胜幸 申请人:株式会社瑞萨科技
技术领域：
本发明涉及信息安全技术，尤其涉及使用了消息认证码(MACMessage Authentication Code)的认证技术。
背景技术：
随着信息通信网络的发展，对电子信息的隐藏和认证所用的加密技术成为不可缺少的要素。作为加密技术要求的要件，除安全性之外，有处理速度和较少存储器使用量等，一般来说安全性、处理速度和存储器使用量之间有平衡关系，很难满足所有的要件。
加密技术有对称加密和公钥加密。对称加密有进行消息的加密·解密的所谓加密和用于表示消息的真实性的消息认证。
消息认证中，对所提供的消息，使用密钥生成作为用于表示其真实性的数据的消息认证码(第一消息认证码)。在消息的真实性的确认到认证中，对所提供的消息，使用与上述密钥相同的密钥再次生成消息认证码(第二消息认证码)，并根据这些消息认证码是否一致来加以判断。关于消息认证的方法(尤其是OMAC和PMAC)记载在T.Iwata and K.Kurosawa，“OMACOne-key CBCMAC”，in the proceedings of Fast Software Encryption(FSE 2003)，Lecture Note in Computer Science 2887，Springer-Verlag，pp.129-153，(2003).(称作文献1)和J.Black and P.Rogaway，“A Block-Cipher Mode of Operation for Parallelizable Message Authentication”，inthe proceedings of EUROCRYPT 2002，Lecture Note in ComputerScience 2332，Springer-Verlag，pp.384-397，(2002).(称作文献2)中。
此外，作为加密技术的安全性，除了以统计分析等数学理论为前提之外，还要求对旁道攻击这样的攻击的耐性，该旁道攻击使用在加密执行时从加密装置观测的物理量、例如计算时间和耗电量等来确定保密信息。关于旁道攻击记载在P.C.Kocher，J.Jaffe，andB.Jun，“Differential Power Analysis”，in the proceedings ofCRYPTO 1999，Lecture Note in Computer Science 1666，Springer-Verlag，pp.388-397，(1999).(称作文献3)中。
此外，关于对消息认证的旁道攻击，记载在K.Okeya，andT.Iwara，“Side Channel Attacks on Message Authentication Codes”，inthe proceedings of Security and Privacy in Ad-hoc and Sensor NetworksSecond European Workshop，ESAS 2005，Lecture Note in ComputerScience 3813，Springer-Verlag，pp.205-217，(2005).(称作文献4)中。在消息认证中存在如下这种异或逻辑(XOR)的情况下，该消息认证对旁道攻击脆弱。即，是如下这种情况对于异或逻辑的两个输入，一个是固定值且对攻击者来说是秘密的值，另一个对攻击者来说是已知的值，并且攻击者可以改变该值。
如果如前所述使用消息认证，则可以验证消息的真实性。但是，在所述文献1、2的技术中，提供了消息认证的方法，却没有充分考虑对旁道攻击的耐性。
发明内容
本发明鉴于上述这种问题而作出，提供一种对旁道攻击安全的消息认证技术。
本申请中公开的发明中，若简单说明代表技术的概要，则为如下这样。本发明是使用了消息认证码(根据需要简称为MAC)的消息认证技术，其特征在于，具有下面所示的技术手段。
(1-1)本发明的装置(消息认证码生成装置)根据消息(作为消息认证码对象的数据用记号M来表示)计算(生成)消息认证码(MAC用记号C或T表示)，其特征在于，通过具有如下所示的干扰信息生成部、消息变换部和认证码(MAC)计算部的各部分来执行所对应的处理。干扰信息生成部使用暂时使用数值(nonce用记号N来表示)进行生成干扰信息(用记号R表示)的处理(干扰信息生成处理)。消息变换部进行根据上述消息M计算变换消息(用记号M’来表示)的处理(消息变换处理)。认证码计算部进行根据上述干扰信息R和上述变换消息M’计算上述消息认证码C的处理(认证码计算处理)。由此，实现对旁道攻击安全的消息认证的方法和根据该方法进行处理动作的装置。
(1-2)此外，本装置中，也可以是，通过执行对上述暂时使用数值N加密(尤其是块加密E)的处理步骤来进行生成上述干扰信息R的处理。
(1-3)此外，本装置中，也可以是，通过将上述消息M分割为消息块(用符号B及M[i]表示)，并执行对该消息块B加密(尤其是块加密E)的处理步骤，来进行计算上述消息M’的处理。
(1-4)此外，本装置中，也可以是，根据作为公知技术的OMAC(One-key CBC MAC)或PMAC(Parallelizable MAC)的处理，来进行计算上述消息认证码C的处理。
在OMAC适用的结构中，在认证码计算部及其处理中，例如按每个消息块B的变换消息M’，具有异或逻辑或算术相加得到的相加和加密(块加密)。该结构中，计算最初(第一)的消息块的变换消息M’和干扰信息R的相加，并加密该输出，来得到第一处理结果。接着，计算第二消息块的变换消息M’和上述第一处理结果的相加，并加密该输出，来得到第二处理结果。之后，同样地进行连锁处理，计算第m消息块的变换消息M’和第(m-1)的处理结果的相加，并加密该输出，获得该第m处理结果作为消息认证码T。
在PMAC适用的结构中，在认证码计算部及其处理中，例如按每个消息块B的变换消息M’，具有异或逻辑或算术相加得到的第一(第一种)相加、加密(块加密)和异或逻辑或算术相加得到的第二(第二种)相加。该结构中，计算最初(第一)的消息块的变换消息M’和γ1L的第一相加，并加密该输出，通过该输出与干扰信息R的第二相加，得到第一处理结果。接着，计算第二消息块的变换消息M’和γ2L的第一相加，并加密该输出，通过该输出和第二处理结果的第二相加，得到第二处理结果。之后同样地进行连锁处理，计算第(m-1)的消息块的变换消息M’和γm-1L的第一相加，并加密该输出，通过该输出和第(m-2)的处理结果的第二相加，得到第(m-1)的处理结果。最后，计算第m的消息块的变换消息M’和第(m-1)的处理结果的相加，并加密该输出，获得第m处理结果作为消息认证码T。
(1-5)此外，本装置中，也可以如下这样进行计算上述消息认证码C的处理。在认证码计算部和处理中，执行以下步骤通过第一相加和加密，根据上述变换消息M’生成第一中间数据d1的处理步骤；使用上述干扰信息R变换上述第一中间数据d1，来生成第二中间数据d2的处理步骤；使用Lu-1，根据上述第二中间数据d2生成第三中间数据d3的处理步骤；使用上述干扰信息R变换上述第三中间数据，来生成第四中间数据d4的处理步骤；以及通过加密，根据上述第四中间数据d4计算上述消息认证码C的处理步骤。
本结构中，在认证计算部和处理中，例如按每个基于消息块B的变换消息M’，具有基于异或逻辑或算术相加的第一(第一种)相加、加密(块加密)、基于异或逻辑或算术相加的第二(第二种)相加和基于异或逻辑或算术相加的第三(第三种)的相加。该结构中，计算最初(第一)的消息块的变换消息M’和γ1L的第一相加，并加密该输出，通过该输出(第一中间数据d1)和干扰信息R的第二相加，得到第一处理结果(第二中间数据d2)。接着，计算第二消息块的变换消息M’和γ2L的第一相加，并加密该输出，通过该输出d1和第一处理结果d2的第二相加，得到第二处理结果d2。之后相同地进行连锁处理，计算第(m-1)的消息块的变换消息M’和γm-1L的第一相加，并加密该输出，通过该输出d1和第(m-2)的处理结果d2的第二相加，得到第(m-1)的处理结果(第d2)。并且，得到下述输出(第三中间数据d3)，该输出计算了第m的消息块的变换消息M’、第(m-1)的处理结果(d2)和Lu-1的相加。并且，得到了将该输出d3和与所述最初(第一)的处理中使用的信息相同的干扰信息R相加后的输出(第四中间数据d4)，获得加密该输出d4后的第m处理结果作为消息认证码T。
(2)本发明的装置(消息认证码验证装置)根据消息(作为消息认证对象的数据M)和第一消息认证码(C1验证前)的输入，进行验证上述消息M的真实性的处理(消息认证码验证处理或消息认证处理)，执行根据上述消息M和暂时使用数值N生成第二消息认证码(C2用于验证)的处理(消息认证码生成处理)、和比较上述第一消息认证码C1和上述第二消息认证码C2来得到其结果的处理。在生成上述消息认证码C1、C2的处理中，使用所述(1)这样的消息认证码生成装置或其处理来进行。
(3)本发明的系统(消息认证系统)在消息认证码验证装置中验证来自消息认证码生成装置的消息和第一消息认证码C1，所述(1)这样的消息认证码生成装置进行生成所述第一消息认证码C1的处理，将所述消息和第一消息认证码C1发送到如所述(2)这样的消息认证码验证装置，在如所述(2)这样的消息认证码验证装置中，进行根据所述消息生成第二消息认证码C2的处理、和进一步比较所述第一消息认证码C1和所述第二消息认证码C2来得到结果的处理。
发明的效果本申请所公开的发明中，若简单说明代表性的发明所得到的效果，则如下这样。根据本发明，可以提供一种对旁道攻击安全的消息认证的技术。
图1是表示本发明的实施方式1～3中的消息认证系统的结构图；图2是表示本发明的实施方式1～3中的消息认证码处理部的结构图；图3是示例了本发明的实施方式1～3中的消息认证码生成处理中的信息的交换的时序图；图4是示例了本发明的实施方式1～3中的消息认证码生成方法和处理的概要的流程图；图5是示例了实施方式1中的消息认证码生成方法及其框图结构和处理的图；图6是示例了实施方式1中的消息认证码生成方法和处理的细节的流程图；图7是示例了实施方式2中的消息认证码生成方法及其框图结构和处理的图；图8是表示实施方式2中的消息认证码生成方法和处理的细节的流程图；图9是表示实施方式3中的消息认证码生成方法及其框图结构和处理的图；图10是表示实施方式3中的消息认证码生成方法和处理的细节的流程图。
具体实施例方式
下面，根据附图来详细说明本发明的实施方式。此外，在说明实施方式用的所有图中，原则上对同一部件添加同一符号，而省略其重复的说明。
(实施方式1)图1～图6表示本发明的实施方式1的结构。图1表示适用了基于本发明的消息认证码计算方法的实施方式1的消息认证系统、消息认证码生成装置和消息认证码验证装置的结构。
<系统结构>
图1中，表示出作为消息认证码(MAC)生成装置的计算机(A)101和作为消息认证码(MAC)验证装置的计算机(B)121通过网络142连接的系统结构。计算机(A)101和(B)121是具有MAC处理部112、132的MAC处理装置，计算机(A)101特别是具有生成MAC的功能的MAC生成装置，计算机(B)121特别是具有验证MAC的功能的MAC验证装置。计算机(A)101、(B)121的MAC处理部112、132是主要特征部，但也可具有与安全处理等有关的其他处理功能。例如，是具有MAC处理部112、132来作为加密处理模块的一部分的结构。计算机(A)101和(B)121是构成整体的消息认证系统所对应的装置，是具有公共的部分(尤其是MAC生成功能)的结构。
首先，下面是本系统中的消息认证处理的概要。图1的消息认证系统中的计算机(A)101和(B)121预先私下秘密共用用于加密处理的密钥K。
计算机(A)101使用上述密钥K，生成对消息M的消息认证码(第一MACC1)。计算机(A)101将上述消息M和上述生成的消息认证码C1作为数据141，通过网络142发送到计算机(B)121。
计算机(B)121使用上述共用的密钥K，对所接收的作为数据141的消息M和消息认证码C1进行验证消息M的真实性的处理。消息M的真实性验证中，使用上述密钥K重新生成对上述消息M的消息认证码(第二MACC2)，并通过比较再次生成的消息认证码C2和所接收的消息认证码C1是否一致，来判断验证结果。即，在一致的情况下，判断为保证了消息M的真实性，在不一致的情况下，判断为不保证消息M的真实性。当然，由于上述消息认证码C2的重新生成的时刻是验证前，所以不能保证通过计算机(B)121和(A)101生成同一内容的数据。例如，有可能上述接收的消息识别符C1是被窜改后的数据。计算机(B)121将验证结果等作为数据143返还给计算机(A)101。
仅向网络142发送消息M和消息认证码C，不发送密钥K。由于消息认证码C的生成中使用了密钥K，所以仅保持有密钥K的计算机可以生成消息认证码C。在由上述计算机(B)121再次生成的消息认证码C2与上述接收的消息认证码C1一致的情况下，表示上述接收的消息认证码C1由保持同一密钥K的计算机(即计算机(A)101)生成。换而言之，表示在通过网络142发送数据141时，没有窜改消息M和消息认证码C，即，表示了消息M的真实性。
<装置结构>
接着说明装置结构等。计算机(A)101和(B)121例如可以是IC卡或是其中装载的IC芯片的形态，或者也可以是PC等形态。计算机(B)121除了与计算机(A)101相同的MAC生成功能之外，还具有MAC验证(比较)功能。
计算机(A)101包括CPU(主处理装置)113和协处理器(数值计算用处理装置)114等运算装置(包含在处理器111中)、RAM103、ROM106和外部存储装置107等存储装置、进行与计算机(A)101的外部之间的数据输入输出用的输入输出接口110等。计算机(A)101的外部连接用户操作计算机(A)101用的显示器(显示装置)108、键盘(输入装置)109和可装卸的可移动型存储媒体的读写装置等。另外，计算机(A)101通过输入输出接口110与网络142相连。
进一步，计算机(A)101通过上述存储装置实现存储部102，上述运算装置通过执行存储部102中存储的程序，来实现作为处理部111的一部分的消息认证码(MAC)处理部112。MAC处理部112生成对应所输入的消息M的消息认证码C1。处理部111使用MAC处理部112进行与消息认证有关的处理等。存储部102在例如RAM103中安全地存储常数(例如初始值和比特长度等参数)、保密信息105(例如密钥(K))等。
计算机(B)121具有与计算机(A)101相同的结构，主要处理部131不同。计算机(B)121通过RAM123、ROM126和外部存储装置127等存储装置来实现存储部122，CPU133和协处理器134等运算装置通过执行存储部122中存储的程序，来实现作为处理部131的一部分的MAC处理部132。MAC处理部132对所接收的消息M和消息认证码C1，通过消息认证码C2的再次生成和比较，来验证消息M的真实性。处理部131使用MAC处理部132来进行与消息认证有关的处理等。存储部122在例如RAM123上安全地存储常数124、保密信息125(例如密钥K)等。
此外，在各实施方式的结构中，计算机(A)101、(B)121可以是下面的结构。计算机(A)101、(B)121内的程序和数据可以预先存储在存储部102、122上，需要时，可以经计算机(A)101、(B)121可使用的媒体和输入输出接口110、130，从其他装置导入到上述存储部102、122中。进一步，计算机(A)101、(B)121内的程序和数据在需要时，也可通过经输入输出接口110、130连接的其他计算机或该计算机可使用的媒体导入到上述存储部102、122中。所谓上述可使用的媒体是指例如对该计算机可装卸的存储媒体或通信媒体(网络或在网络中传送的载波和数字信号等)。
另外，计算机(A)101和(B)121私下共用的上述密钥K除经输入输出接口110、130输入密钥K的数据之外，还可以通过输入将密钥K加密后的数据且计算机(A)101或(B)121解密该加密数据，来实现密钥K的共用。此外，还可以利用公钥加密的技术，将与公钥有关的信息经网络142发送到对方侧的计算机，并使用自己的保密信息从所接收的对方侧公钥的信息中导出新的密钥，来实现密钥K的共用。
<MAC生成处理>
接着，参考图2～图4来说明图1的消息认证系统中的计算机(A)101的MAC处理部112所进行的MAC生成处理。实施方式1中，使用图2所示的功能块结构的MAC处理部112。
图2中，MAC处理部112包括干扰信息生成部210、消息变换部220和认证码计算部230。干扰信息生成部210具有块加密计算部211。消息变换部220具有填充部221和块加密计算部222。认证码计算部230具有逻辑算术运算部231和块加密计算部232。
MAC处理部112输入消息M和暂时使用数值N，并输出通过MAC生成处理生成的MAC认证码C。干扰信息生成部210以暂时使用数值N为基础来生成干扰信息R。消息变换部220以消息M为基础来生成变换消息M’。认证码计算部230以干扰信息R和变换消息M’为基础来计算消息认证码C。
各个块加密计算部进行DES和AES这样的块加密计算。将该块加密表示为符号E。块加密E具有预定比特长度(密钥长度)的密钥K和预定比特长度(块长度)的消息M0这两个输入，输出使用了密钥K的消息M0的加密结果EK(M0)。密钥长度和块长度也可以相同。此外，在不需要明确表示密钥K的情况下，可以如E(M0)那样，省略密钥K来加以标记。此外，本例中，块加密计算部分别包含在干扰信息生成部210、消息变换部220和认证码计算部230中，但是也可统合这些块加密计算部211、222、232，通过分别从干扰信息生成部210、消息变换部220和认证码计算部230调用来构成。通过这种结构，可以减少电路规模和程序代码。
填充部221通过每隔块长度来分割所输入的消息M，来对生成消息块B时的最后消息块B追加适当的二进制串，而使比特长度与块长度一致(填充(padding)处理)。逻辑算术运算部231进行异或逻辑(XOR)和算术相加这样的逻辑运算和算术运算。
图3示例了基于本MAC生成方法的计算机(A)101的MAC处理部112的MAC生成处理中的信息交换。图4示例同一MAC处理部112的MAC生成处理的概要。S表示处理步骤。
图3和图4中，首先，MAC处理部112作为输入接收消息M和暂时使用数值N(S301)。接着，MAC处理部112将暂时使用数值N送到干扰信息生成部210(S302)。接着，干扰信息生成部210使用暂时使用数值N来进行生成干扰信息R的干扰信息生成处理401。接着，干扰信息生成部210将所生成的干扰信息R送到MAC处理部112(S303)。
接着，MAC处理部112将消息M送到消息变换部220(S304)。接着，消息变换部220通过变换消息M(包含对消息块B的变换)来进行获得变换消息M’的消息变换处理(402)。接着，消息变换部220将所得到的变换消息M’送到MAC处理部112(S305)。
接着，MAC处理部112将干扰信息R和变换消息M’送到认证码计算部230(S306)。接着，认证码计算部230使用干扰信息R和变换消息M’来进行计算消息认证码T的认证码计算处理403。接着，认证码计算部230将计算所得到的消息认证码T送到MAC处理部112(S307)。
接着，MAC处理部112根据所接收的消息认证码T，决定对应消息M的消息认证码C(尤其是第一MACC1)并输出(S308)。
此外，对于上述暂时使用数值N，相同值的暂时使用数值N仅一次(限于该情况)用于消息认证码C的生成。即，对不同的消息M使用不同值的暂时使用数值N。作为暂时使用数值N的例子，有使用计数器或随机数的方法等。例如，计算机(A)101、(B)121具有计数器和随机数生成部，使用计数器的增加值和由随机数生成部生成的随机数值。
<第一结构>
实施方式1中，作为消息认证码说明以所述文献1记载的OMAC的方法为基础构成的例子(MAC处理部112的第一结构)。使用图5和图6，详细说明MAC处理部112中的干扰信息生成部210、消息变换部220和认证码计算部230进行的处理。图5示例了与图2的MAC处理部112对应的MAC生成方法和该框图结构与该处理。图6示例了同一MAC生成处理的细节。图5所示的块结构表示干扰信息生成部210进行的干扰信息生成处401、消息变换部220进行的消息变换处理402及认证码计算部230进行的认证码计算处理403与下面所示的详细处理之间的关联。
图5中，在第一结构中，干扰信息生成部210及其处理401中，对暂时使用数值N(502)进行块加密E(511)，来生成干扰信息R。消息变换部220及其处理402中，通过分割为预定块长度，从消息M(501)中得到消息块(B)M[1](521)～M[m](523)。10i(524)是填充用的值。另外，对上述各消息块(B)进行块加密E(531～533)，而得到变换消息M’。认证码计算部230及其处理403中，每个基于消息块B的变换消息M’具有异或逻辑(51～53)和块加密E(541～543)。该结构中，计算基于最初(第一)消息块(M[1])的变换消息(M’)和干扰信息R的异或逻辑51，来对该输出进行块加密E(541)，而得到第一处理结果。接着，计算基于第二消息块(M[2])的变换消息M’和上述第一处理结果的异或逻辑52，对该输出进行块加密E(542)，而得到第二处理结果。之后，同样地进行连锁处理，计算基于第m消息块(M[m])的变换消息M’和第(m-1)的处理结果的异或逻辑53，并对该输出进行块加密E(543)，获得该第m处理结果作为消息认证码(T)551。
图5和图6中，MAC处理部112将消息M和暂时使用数值N作为输入加以接收(S601)。干扰信息生成部210对暂时使用数值N，使用块加密计算部211来计算块加密E的加密结果E(N)，并将该结果E(N)作为干扰信息(R)存储到变量T1中(S602)。
MAC处理部112将消息M的块数代入到m，将1代入到变量j(S603)。这里所谓块数(m)是指每隔块长度分割消息M时的分割所得到的消息块(B)的数目。消息M(501)通过分割变为消息块(B)M[1]～M[m](521～523)。
MAC处理部112判断是否是j＜m(S611)。在该条件成立的情况下(TRUE)，进入到S612。在条件不成立的情况下(FALSE)，进入到S621。
在S611中条件成立的情况下，在S612中，消息变换部220对消息块M[j]，使用块加密计算部222来计算块加密E的加密结果E(M[j])，并将该结果作为变换消息(M’)的一部分存储到变量T2中(S612)。接着，认证码计算部230使用逻辑算术运算部231来计算变量T1和变量T2的异或逻辑(T1xor T2)，并将该结果存储在变量T1中(S613)。接着，认证码计算部230对变量T1，使用块加密计算部232来计算块加密E的加密结果E(T1)，并将其结果存储到变量T1中(S614)。接着，MAC处理部112将j+1代入到变量j，并返回到S611(S615)。
在S611中条件不成立的情况下，在S621中，消息变换部220使用填充部211，对消息块M[m](最后的消息块(B))进行填充(S621)。本例中，将对M[m]填充的值设作10i＝‘10...0’(524)。另外，在消息块M[m]的比特长度与用于分割的块长度一致的情况下，也可不进行填充。此外，这时，也可以是追加新的消息块M[m+1]来作为第(m+1)的消息块B的形态。在追加第(m+1)的消息块的情况下，对M[m]进行S612～S615的处理，对第(m+1)的消息块进行S621之后的处理。
接着，消息变换部220对作为最后的消息块B的、填充后的消息块M[m]|10...0使用块加密计算部222来计算块加密E的加密结果E(M[m]|10...0)，并将该结果作为变换消息M’的一部分存储在变量T2中(S622)。此外，“M[m]|10...0”这样的表现表示在M[m]的填充前的原始数据之后，作为填充(值)的一例添加了10i＝‘10...0’(前端是1，之后i个全部是0)。通过这种填充的添加，可以进行从M[m]中取出原始数据的处理等。
接着，认证码计算部230使用逻辑算术运算部231计算变量T1和变量T2的异或逻辑(T1xor T2)，并将其结果存储到变量T1中(S623)。接着，认证码计算部230对变量T1，使用加密计算部232来计算块加密E的加密结果E(T1)，将其结果作为认证码计算部230输出的消息认证码T存储到变量T1中(S624)。并且，MAC处理部112从变量T1中截出预定的比特数，来作为消息认证码(T尤其是C1)输出(S625)。
此外，上述处理还可以进行如下这种变形。S612、S623中进行的运算为异或逻辑(xor)，但是也可以是算术相加。也可在干扰信息生成部210内生成作为对干扰信息生成部210的输入的暂时使用数值N。这时，需要输出所生成的暂时使用数值N。
此外，在干扰信息生成部210、消息变换部220和认证码计算部230中使用的块加密E中的密钥K可以使用不同的密钥。此外，各块加密E的计算中也可以使用不同的密钥。但是，前提是在计算机(A)101侧生成MAC(C1)时和在计算机(B)121侧进行验证时重新生成MAC(C2)时，在各个对应的块加密E的计算中使用相同密钥。
此外，在上述说明中，说明了消息变换部220进行消息变换的情况，但是也可不进行消息变换。这时，有可能降低消息认证的安全性，但是由于可以减少块加密E的加密处理的次数，所以可以高速化。
此外，用于块加密E的密钥可以原样使用计算机(A)101和(B)121私下共用的密钥K，但是也可将从密钥K导出的值作为新的密钥。例如，也可以将EK(0)作为密钥。
此外，S621中，进行对第m消息块M[m]的填充，但是作为填充方式，除了追加10i＝‘10...0’(524)之外，也可追加‘01...1’或表示块数(m)的数值等其他值。
此外，上述说明是分别分割消息变换处理402和认证码计算处理403、并交替进行分割后的处理的情况。即，本例中，以首先是对第一消息M[1]的变换处理521、531、接着是对M[1]的计算处理51、541、接着是对第二消息M[2]的变换处理522、532、接着是对M[2]的计算处理52、542.....这样的顺序来加以处理。但是，也可在对所有的消息块M[1]～M[m]的消息变换处理402完成后，开始对这些所有的变换消息M’的认证码计算处理403。此外，只要在干扰信息生成处理部401和消息变换处理402之后进行认证码计算处理403即可，干扰信息生成部401和消息变换处理402的顺序可以是任何一个。例如，也可在消息变换处理402之后进行干扰信息生成处理401。
此外，在消息变换处理402中，也可以在变换处理即消息块(B)M[1]～M[m]的计算时，进行并行计算带来的高速化。例如，也可并行进行E(M[1])和E(M[2])的加密计算。另外，也可调换消息块B的计算顺序。例如，也可在E(M[2])的加密计算后，进行E(M[1])的加密计算。
此外，本例是将MAC处理部112的一系列的块加密E(公知技术)的整体具有对旁道攻击的耐性作为前提的结构，但是也可以为对各块加密E的计算分别实施应对旁道攻击的对策的结构。通过该结构，在消息认证码C的生成中，可以进一步增加安全性。
上述说明中以OMAC为例来构成，但是也可对其他CBC(Cipher-Block Chaining加密块链接)模式的消息认证码构成。CBC是块加密(CB)的使用方法(模式)的一个。OMAC是使用了CBC模式的MAC中的一个。
以上，根据本实施方式1，通过使用干扰信息R，来隐藏和干扰处理中的对异或逻辑(51～53)的输入值，而使旁道攻击无效化。细节如下。
上述旁道攻击是指在确定保密信息时需要固定值的输入和已知值的输入。根据所述文献4，在消息认证中存在如下这种异或逻辑的情况下，该消息认证对旁道攻击脆弱。其是如下的情况对于异或逻辑的两个输入，一个是固定值且对攻击者来说是秘密的值，另一个对攻击者来说是已知的值，攻击者可以改变该值。考虑这种情况，在与认证码计算处理部403对应的现有认证码计算处理部整体中，认为没有对旁道攻击的耐性。
另一方面，本实施方式1中，例如，若看异或逻辑51，则由于作为其一个输入值的干扰信息R是每次改变的值，即对攻击者来说是秘密的值，所以即使作为另一个输入值的变换消息M’对攻击者来说是已知的值，也不能预测出异或逻辑51的输出结果。对于其他异或逻辑51～53也相同，这样，在隐藏和干扰认证码计算部403中的对异或逻辑51～53的输入值的本实施方式1的结构中，可以实现旁道攻击的无效化。
如以上所说明的，实施方式1的上述消息认证和MAC生成的方法及处理具有对旁道攻击的耐性良好的特点。
(实施方式2)接着，参考图7～图8来说明本发明的实施方式2。实施方式2中，作为消息认证码说明以所述文献2记载的PMAC的方法为基础构成的例子(MAC处理部112的第二构成)。实施方式2中，基本上与实施方式1共通的结构中，主要是认证码计算处理403不同。
<第二结构>
使用图7和图8，来详细说明MAC处理部112中的干扰信息生成部210、消息变换部220和认证码计算部230进行的处理。图7的块结构表示干扰信息生成部210进行的干扰信息生成处理401、消息变换部220进行的消息变换处理402、认证码计算部230进行的认证码计算处理403与下面所示的详细处理之间的关联。
图7中，第二结构中，在干扰信息生成部210及其处理401中，对暂时使用数值N(702)进行块加密E(711)，而生成干扰信息R。在消息变换部220及其处理402中，通过分割为预定块长度，从消息M(701)中得到消息块(B)M[1](721)～M[m](724)。10i(725)是填充用的值。另外，对上述各消息块(B)进行块加密E(731～734)，而得到变换消息M’。在认证码计算部230及其处理403中，每个基于消息块B的变换消息M’，具有第一异或逻辑(71～73，77)、块加密E(751～754)和第二异或逻辑(74～76)。该结构中，计算基于最初(第一)消息块(M[1])的变换消息(M’)和γ1L(741)的异或逻辑71，来对该输出进行块加密E(751)，通过该输出和干扰信息R的异或逻辑74，得到第一处理结果。接着，计算基于第二消息块(M[2])的变换消息M’和γ2L(742)的异或逻辑72，来对该输出进行块加密E(752)，通过该输出和第一处理结果的异或逻辑75，得到第二处理结果。之后，同样地进行连锁处理，计算基于第(m-1)消息块(M[m-1])的变换消息M’和γm-1L(743)的异或逻辑73，来对该输出进行块加密E(753)，通过该输出和第(m-2)处理结果的异或逻辑76，得到第(m-1)处理结果。最后，计算基于第m消息块(M[m])的变换消息M’和第(m-1)的处理结果的异或逻辑77，对该输出进行加密754，获得将第m处理结果作为消息认证码T(761)。
图7和图8中，MAC处理部112将消息M和暂时使用数值N作为输入加以接收(S801)。接着，干扰信息生成部210对暂时使用数值N，使用块加密计算部211来计算块加密E的加密结果E(N)，并将该结果E(N)作为干扰信息(R)存储到变量T1中(S802)。接着，MAC处理部112将消息M的块数代入到m，将1代入到变量j(S803)。
接着MAC处理部112判断是否是j＜m(S811)。在该条件成立的情况下(TRUE)，进入到S812。在条件不成立的情况下(FALSE)，进入到S821。
在S811中条件成立的情况下，在S812中，消息变换部220对消息块M[j]，使用块加密计算部222来计算块加密E的加密结果E(M[j])，并将该结果作为变换消息(M’)的一部分存储到变量T2中(S812)。
接着，认证码计算部230使用逻辑算术运算部231计算变量T2和数值γjL的异或逻辑(T1xor γjL)，并将该结果存储在变量T2上(S813)。这里，L是由对0的块加密E的加密结果L＝EK(0)提供的数值，γj称作格雷码，对于各i，γi和γi+1仅1比特不同。具体的，设γ0＝0，对于i＝0，1，...，可以通过决定为γi+1＝γixor((0...01)＜＜ntz(i))来构成。其中，“a＜＜b”表示将a左移b比特，ntz(i)是用二进制表现来表示数值i时比特值是1的最右比特位置。例如，ntz(7)＝0、ntz(8)＝3。另外，γjL是γj和L的二进制的相乘结果。
接着，认证码计算部230对变量T2，使用块加密计算部232来计算块加密E的加密结果E(T2)，并将其结果存储到变量T2中(S814)。接着，认证码计算部230使用逻辑算术运算部231来计算变量T1和变量T2的异或逻辑(T1xor T2)，并将该结果存储到变量T1中(S815)。接着，MAC处理部112将j+1代入到变量j，并返回到S811(S816)。
在S811条件不成立的情况下，在S821中，消息变换部220使用填充部211，对消息块M[m]进行填充。另外，在消息块M[m]的比特长度与块长度一致的情况下，也可不进行填充。这时，也可以是追加新的消息块M[m+1]来作为第(m+1)的消息块B。在追加第(m+1)的消息块M[m+1]的情况下，对M[m]进行S812～S816的处理，对第(m+1)的消息块M[m+1]进行S821之后的处理。
接着，消息变换部220对填充后的消息块M[m]|10...0使用块加密计算部222来计算块加密E的加密结果E(M[m]|10...0)，并将该结果作为变换消息M’的一部分存储在变量T2中(S822)。接着，认证码计算部230使用逻辑算术运算部231计算变量T1和变量T2的异或逻辑(T1xor T2)，并将其结果存储到变量T1中(S823)。接着，认证码计算部230对变量T1，使用块加密计算部232来计算块加密E的加密结果E(T1)，并将该结果作为认证码计算部230输出的消息认证码T存储到变量T1中(S824)。接着，MAC处理部112从变量T1中截出预定的比特数，来作为消息认证码(T尤其是C1)输出(S825)。
上述处理还可以进行与实施方式1中说明的相同的各种变形。
以上，根据本实施方式2，隐藏和干扰对处理中的异或逻辑74～77的输入值，来实现旁道攻击的无效化。与实施方式1相同，实施方式2的消息认证和MAC生成的方法及处理具有对旁道攻击的耐性良好的特点。
(实施方式3)接着，参考图9～图10来说明本发明的实施方式3。实施方式3中，作为消息认证码以所述文献2记载的PMAC的方法为基础来构成，进一步，说明作为输出与原始的PMAC(已经确立的方法)所输出的消息认证码相同的值的消息认证码的结构的例子(MAC处理部112的第三结构)。实施方式3中，在基本上与实施方式1和2公共的结构中，主要是消息变换处理402和认证码计算处理403不同。实施方式3的消息变换部220不具有块加密计算部222。通过为这种结构，可以减少电路规模和程序代码大小。所述实施方式2中，对PMAC即使输入值M相同，输出值T也不同。实施方式3中，对本结构的PMAC，若其输入值M和原始的PMAC的输入值相同，则这些输出值T也相同。输出相同的情况在替换性等方面有好处。
<第三结构>
使用图9和图10来详细说明MAC处理部112中的干扰信息生成部210、消息变换部220和认证码计算部230进行的处理。图9的块结构表示干扰信息生成部210进行的干扰信息生成处理401、消息变换部220进行的消息变换处理402、认证码计算部230进行的认证码计算处理403与下面所示的详细处理之间的关联。
图9中，在第三结构中，在认证码计算部230及其处理403中，每个基于消息块B的变换消息M’，具有第一(第一种)异或逻辑(91～93)、块加密E(941～943)、第二(第二种)异或逻辑(94～97)和第三(第三种)异或逻辑(98)。使用认证码计算处理403中的各种处理中的中间数据(d1～d4)来加以说明。在该结构中，计算基于最初(第一)消息块的变换消息(M’)和γ1L(931)的第一异或逻辑91，对该输出进行块加密E(941)，通过该输出(第一中间数据d1)和干扰信息R的第二异或逻辑94，得到第一处理结果(第二中间数据d2)。接着，计算基于第二消息块的变换消息M’和γ2L(932)的第一异或逻辑92，并对该输出进行块加密E(942)，通过该输出d1和第一处理结果d2的第二异或逻辑95，得到第二处理结果d2。之后，同样地进行连锁处理，计算基于第(m-1)消息块的变换消息M’和γm-1L的第一相加，并加密该输出，通过该输出d1和第(m-2)的处理结果(d2)的第二相加，得到第(m-1)的处理结果d2。并且，得到计算了基于第m消息块的变换消息M’、第(m-1)的处理结果d2和Lu-1的相加后的输出(第三中间数据d3)。并且，得到将该输出d3和与所述最初(第一)处理中所用的信息相同的干扰信息R相加后的输出(第四中间数据d4)，从而获得加密该输出d4后的第m处理结果作为消息认证码T。
图9和图10中，MAC处理部112将消息M和暂时使用数值N作为输入加以接收(S1001)。接着，干扰信息生成部210对暂时使用数值N，使用块加密计算部211计算块加密E的加密结果E(N)，并将该结果作为干扰信息(R)存储到变量T1及T3中(S1002)。接着，MAC处理部112将消息M的块数代入到m，将1代入到变量j(S1003)。
接着，MAC处理部112判断是否是j＜m(S1011)。在该条件成立的情况下(TRUE)，进入到S1012。在条件不成立的情况下(FALSE)，进入到S1021。
在S1011中条件成立的情况下，在S1012中，消息变换部220将消息块M[j]的值作为变换消息M’的一部分存储在变量T2中(S1012)。接着，认证码计算部230使用逻辑算术运算部231计算变量T2和数值γjL的异或逻辑(T2xor L)，并将该结果存储在变量T2上(S1013)。
接着，认证码计算部230对变量T2，使用块加密计算部232来计算块加密E的加密结果E(T2)，并将其结果存储到变量T2中(S1014)。接着，认证码计算部230使用逻辑算术运算部231计算变量T1和变量T2的异或逻辑(T1xor T2)，并将其结果存储到变量T1中(S1015)。接着，MAC处理部112将j+1代入到变量j，并返回到S1011(S1016)。
在S1011中条件不成立的情况下，在S1021中，消息变换部220使用填充部221，对消息块M[m]进行填充，并将其结果作为变换消息M’的一部分。此外，在消息块M[m]的比特长度与块长度一致的情况下，不进行填充。
接着，认证码计算部230对填充后的消息块M[m]|10...0使用块加密计算部232来计算块加密E的加密结果E(M[m]|10...0)，并将该结果存储在变量T2中(S1022)。接着，认证码计算部230使用逻辑算术运算部231计算变量T1、变量T2和数值Lu-1(944)的异或逻辑(T1xor T2xor Lu-1)，并将其结果存储到变量T1中(S1023)。其中，在消息块M[m]和块长度一致的情况，即不进行填充的情况，进行与数值Lu-1的异或逻辑。在不进行填充的情况下，使用逻辑算术运算部231计算异或逻辑(T1xor T2)，并将其结果存储到变量T1中。另外，u是表示“0...010”的数值，u-1是二进制中的u的倒数。即，u-1是在二进制的相乘中满足u u-1＝1的数值。Lu-1是L和u-1在二进制中的相乘结果。
接着，认证码计算部230使用逻辑算术运算部231计算变量T1和变量T3的异或逻辑(T1xor T3)，并将其结果存储到变量T1中(S1024)。接着，认证码计算部230对T1，使用块加密计算部232来计算块加密E的加密结果E(T1)，并将该结果作为认证码计算部230输出的消息认证码(T)存储到变量T1中(S1025)。接着，MAC处理部112从变量T1中截出预定的比特数，来作为消息认证码(T尤其是C1)输出(S1026)。
在认证码计算处理403中的块加密E后的通过异或逻辑94、98的处理中，在S1015中通过最初的异或逻辑94添加的干扰信息R在S1024中通过最后的异或逻辑94来加以取消(消除)。因此，本实施方式3中输出的消息认证码T的值与原始的PMAC输出的消息认证码的值相等。
此外，上述处理还可以进行与实施方式1中说明的相同的各种变形。
以上，根据本实施方式3，隐藏和干扰对处理中的异或逻辑94～98的输入值，来实现旁道攻击的无效。与实施方式1和2相同，实施方式3的消息认证和MAC生成的方法和处理对旁道攻击的耐性好，此外，具有输出与原始的PMAC相同的消息认证码的特点。
以上，根据实施方式具体说明了本发明人进行的发明，但是本发明并不限于所述实施方式，当然可以在不脱离其主旨的范围内进行各种改变。例如，各实施方式中的MAC处理部、干扰信息生成部、消息变换部、认证码计算部、逻辑算术运算部、块加密计算部和填充部等的处理可以使用协处理器或专用的硬件来进行。
产业上的可用性本发明可以用于使用了消息认证的信息处理装置等中。
权利要求
1.一种消息认证码生成装置，根据消息计算对所述消息的消息认证码，其特征在于，包括干扰信息生成部，进行使用暂时使用数值生成干扰信息的处理；消息变换部，进行根据所述消息计算变换消息的处理；以及认证码计算部，进行根据所述干扰信息和所述变换消息计算所述消息认证码的处理。
2.根据权利要求1所述的消息认证码生成装置，其特征在于，在所述干扰信息生成部所进行的生成所述干扰信息的处理中，执行对所述暂时使用数值进行加密的处理步骤。
3.根据权利要求2所述的消息认证码生成装置，其特征在于，在所述消息变换部所进行的计算所述变换消息的处理中，执行将所述消息分割为消息块，并对所述消息块进行加密的处理步骤。
4.根据权利要求3所述的消息认证码生成装置，其特征在于，所述认证码计算部所进行的计算所述消息认证码的处理是使用了OMAC的处理。
5.根据权利要求3所述的消息认证码生成装置，其特征在于，所述认证码计算部所进行的计算所述消息认证码的处理是使用了PMAC的处理。
6.根据权利要求2所述的消息认证码生成装置，其特征在于，在所述认证码计算部所进行的计算所述消息认证码的处理中，执行下述步骤根据所述变换消息生成第一中间数据的处理步骤；使用所述干扰信息变换所述第一中间数据，并生成第二中间数据的处理步骤；根据所述第二中间数据生成第三中间数据的处理步骤；使用所述干扰信息变换所述第三中间数据，并生成第四中间数据的处理步骤；以及根据所述第四中间数据计算所述消息认证码的处理步骤。
7.根据权利要求4所述的消息认证码生成装置，其特征在于，在所述认证码计算部所进行的计算所述消息认证码的处理中，执行按每个基于所述消息块的变换消息进行使所述干扰信息作用的异或逻辑或基于算术相加的加法、以及其输出的加密的处理步骤，并进行连锁处理。
8.根据权利要求5所述的消息认证码生成装置，其特征在于，在所述认证码计算部所进行的计算所述消息认证码的处理中，执行按每个基于所述消息块的变换消息进行使格雷码与对0的加密结果的二进制的相乘结果(γjL)作用的异或逻辑或基于算术相加的第一相加、其输出的加密、以及使所述干扰信息作用的异或逻辑或基于算术相加的第二相加的处理步骤，并进行连锁处理。
9.一种消息认证码验证装置，根据消息和用于验证所述消息的真实性的第一消息认证码，验证所述消息的真实性，其特征在于，执行下述步骤进行根据所述消息和暂时使用数值生成第二消息认证码的处理的处理步骤；以及进行比较所述第一消息认证码和所述第二消息认证码来得到结果的处理的处理步骤；在生成所述第二消息认证码的处理步骤中，执行下述步骤进行使用所述暂时使用数值生成干扰信息的处理的处理步骤；进行根据所述消息计算变换消息的处理的处理步骤；以及进行根据所述干扰信息和所述变换消息计算所述第二消息认证码的处理的处理步骤。
全文摘要
提供一种对旁道攻击安全的消息认证技术。在根据消息(M)计算对消息(M)的消息认证码(T)的消息认证码生成装置中，进行根据暂时使用数值(N)生成干扰信息(R)的处理(401)、根据消息(M)计算变换消息(M’)的处理(402)和根据干扰信息(R)和变换消息(M’)计算消息认证码(T)的处理(403)。在计算消息认证码(T)的处理(403)中，由于通过干扰信息(R)干扰或隐藏了处理信息，所以实现了对旁道攻击安全的消息认证。
文档编号G09C1/00GK101060408SQ20071009707
公开日2007年10月24日 申请日期2007年4月17日 优先权日2006年4月17日
发明者桶屋胜幸 申请人:株式会社瑞萨科技
最新回复(0)