加密装置、解密装置、加密方法及集成电路的制作方法
专利名称：加密装置、解密装置、加密方法及集成电路的制作方法
技术领域：
本发明涉及一种加密装置、解密装置、加密方法及集成电路，它们能 够防止被通过对执行加密处理时的电力消耗量进行测量来对加密模块中 所嵌入的密钥进行分析的攻击方法所破解。
背景技术：
近年来，设计有各种以硬件或软件中所安装的加密模块进行加密处理 时所使用的副信息为线索来分析密钥的破解法。例如，在被称为时序攻击 的分析方法中，利用加密模块在加密处理中需要的时间和用在加密处理中 的密钥的值的细微的差异来进行密钥的分析。即，在时序攻击中，利用进 行加密处理时的称作处理时间的副信息，进行密钥的破解。在那样的破解 法中，作为以进行加密处理时的电力消耗量为副信息来进行破解的破解方
法，设计有简单能量分析攻击(Simple Power Analysis)或差分能量分析攻 击(Differential Power Analysis)等各种方法。近年来，在能够便宜购入高 性能的测量机器的背景下，有报告称这些破解法也能够对IC卡这样的施 加加密的实际产品进行分析。此外，设计有在以进行加密处理时从加密模 块产生的电磁波强度为副信息来进行破解的方法等各种破解方法。在下面 的记述中，把以加密处理时的加密模块的电力消耗量为线索分析密钥的破 解方法总称为"电力分析攻击"。下面，以电力分析攻击为例进行说明， 但本发明对利用副信息的其他分析方法也同样有效。即，本发明不仅适用 于电力分析攻击，只要是利用在加密处理中从加密模块产生的副信息来推 定密钥的分析方法就均可以适用。
电力分析攻击利用加密模块的电力消耗量和加密处理过程中的中间 值之间的关系来进行密钥的分析。因此，作为针对电力分析攻击的对策， 考虑到利用随机数对加密处理过程中的中间值进行随机化，从而使得电力 消耗量和中间值之间的相关关系难以理解的方法，所述随机数是在加密模块内部所生成的。这样，将对加密处理的中间值进行随机化的过程称为将 中间值进行"屏蔽"。此外，把通过屏蔽中间值来使得电力分析攻击的密 钥分析变困难的方法总称为"屏蔽法"。
在专利文献1中记载的屏蔽法中，公开有针对美国标准密码术DES
(Data Encryption Standard,即数据加密标准)加密的屏蔽法(称为现有技 术l)。
(现有技术1的概要)
根据现有技术l的方法，在加密处理之前，首先根据加密模块内部生 成的随机数，将在DES加密中使用的数据变换用表Sbox进行随机化，来 制作随机化Sbox表，并暂时保管。在加密处理中，使用该随机化Sbox表， 对加密处理的中间值进行屏蔽，以使得电力分析攻击就变得困难。这里， 在现有技术l中，需要用于暂时储存随机化Sbox表的RAM。因此，在对 RAM容量有严格限制的情况下，就出现了不能使用现有技术1的问题。 此外，在硬件中安装加密模块的情况下， 一般来说在逻辑电路中安装Sbox 表的情况较多。因此，由于不能制作随机化Sbox表，就出现了不能使用 现有技术1的问题。
(现有技术2的概要)
在非专利文献1所记载的屏蔽法中，公开有针对美国下一代标准密码 术AES (Advanced Encryption Standard)加密的屏蔽法(称为现有技术2)。 在现有技术2中，能够在逻辑电路中安装Sbox表，并且，如现有技术1 所示，由于没有必要制作随机化Sbox表，因此适用于硬件安装。下面， 对其概要进行说明。
已知AES加密的Sbox表与进行扩张域GF(2^)上的逆元计算("XAY" 表示"X的Y次方")和规定的进行仿射变换的处理等价。此外，作为用 电路实现扩张域GF (2A8)上的元素X的逆元计算的方法，有下面的既有 方法。
(1) 将X变换为和GF (2A8)同型的合成域GF ( ( (2A2) 、) A2) 上的元素A。
(2) 在上述合成域上计算A的逆元AA ( — l)。
(3) 将A八(一l)逆变换为扩张域上的元素，求得XA ( — l)。 在该方法中，通过在合成域上进行逆元计算，能够以较小的电路规模安装逆元计算。
如果将AES加密的Sbox表通过上述的逆元计算和仿射变换来安装并
适用屏蔽法，则能够以小的电路规模提高对电力分析攻击的耐性。此时，
怎样对逆元计算部分实施屏蔽成为关键。下面，对现有技术2中的逆元计
算部分的屏蔽方法进行简单的说明。
图1~图7是表示现有技术2中的加密装置中设置的随机化8位逆元计 算部81的图。
<随机化8位逆元计算部81>
图1是表示现有技术2中的随机化8位逆元计算部81的结构的框图。 随机化8位逆元计算部81以被屏蔽的逆元计算对象数据X (8位)、屏蔽 数据R (8位)及计算用随机数r (4位)作为输入，进行逆元计算，输出 被屏蔽的逆元计算结果Y (8位)。这里，X是用屏蔽数据R进行了屏蔽 的状态的数据，表示为X=M ( + ) R。这里，M (8位)是被屏蔽前的数据， "(+ )"是表示对每个位的按位加运算。此时，Y成为Y={MA (_1) } (+ ) R。 S卩，随机化8位逆元计算部81进行如下处理以用R进行了屏 蔽的M为输入，计算逆元，将其结果MA ( —1)在用R屏蔽了的状态下 进行输出。即，对于作为加密处理的中间值即M，由于在利用随机的屏蔽 数据R进行了屏蔽的状态下进行逆元计算，从而使得电力分析攻击变得困 难。
如图1所示，随机化8位逆元计算部81包括进行合成域GF( ((2、) A2) A2)上的17次方计算的17次方计算部810、 812; 4位校正项计算部 811 (图2) ; 4位输出计算部816、 817 (图3);进行4位的按位加运算 的按位加部813、 814、 818、 819;随机化4位逆元计算部815 (图4)。
这里，如图2所示，4位校正项计算部811包括进行在合成域GF ((2A2) A2)上的乘法运算的4位乘法部811a、 811b;以及进行4位的按 位加运算的按位加部811c、 811d。另外，对合成域GF ( (2A2) A2)进行 2次扩张的结果为合成域GF ( ( (2A2) A2) A2)。
此外，如图3所示，4位输出计算部816、 817包括进行在合成域 GF ( (2A2) A2)上的乘法运算的4位乘法部816a、 816b、 816c、 816d; 以及进行4位的按位加运算的按位加部816e、 816f、 816g、 816h、 816i、 816j。
8此外，如图4所示，随机化4位逆元计算部815 (图4)包括进行 在合成域GF ( (2A2) A2)上的5次方计算的5次方计算部820、 822; 2 位校正项计算部821 (图5) ; 2位输出计算部826、 827 (图6);进行2 位按位加运算的按位加部823、 824、 828、 829;以及随机化2位逆元计算 部825 (图7)。
这里，如图5所示，2位校正项计算部821 (图4、图5)包括进行 有限域GF (2A2)上的乘法运算的2位乘法部821a、 821b;以及进行2位 的按位加运算的按位加部821c、 821d。另外，对有限域GF (2A2)进行2 次扩张的结果为合成域GF ( (2l) A2)。
此外，如图6所示，2位输出计算部826、 827 (图6、图4)包括 进行在有限域GF (2A2)上的乘法运算的2位乘法部826a、 826b、 826c、 826d;以及进行2位的按位加运算的按位加部826e、 826f、 826g、 826h、 826i、 826j。
此外，如图7所示，随机化2位逆元计算部825 (图7、图4)包括进 行1位的按位加运算的按位加部825a、 825b。
如上所述，现有技术2中的设置在加密装置中的随机化8位逆元计算 部81 (图1)包括在内部递归性地执行随机化4位逆元计算部815和随机 化2位逆元计算部825，通过该结构，和其他现有技术相比，能够以较小 .的电路规模来安装。
在现有技术2中，公开有一种适于硬件安装的加密装置，该加密装置 通过设置上述的随机化8位逆元计算部81 (图l)，并利用逆元计算和仿 射变换安装AES加密的Sbox表。
非专利文献1:森岡澄夫、秋下徹、「合成域^r用v、/iAES S — B
o x回路〖対t3DPa攻撃」、〕/匕。工一夕-fe年二！Jx,、:/y求-々
厶2 0 0 4予稿集(平成l 6年1 0月)
非专禾lj文南犬2: Federal Information Processing Standards Publication
November 26 2001
专利文献l:美国专利第6295606号说明书
但是，在现有技术2中，如前所述，由于随机化8位逆元计算部81 (图1)具有递归的结构，所以具有最大逻辑级数变大的问题。在把现有技术2的随机化8位逆元计算部81用电路实现时，若预估关键路径和其
最大逻辑级数，则如下。
随机化8位逆元计算部81 (图1 图7)的关键路径如下。 首先，在图1中，关键路径如下。
17次方计算部810=〉按位加部813=〉按位加部814=〉随机化4位逆 元计算部815 (图4) =〉 4位输出计算部817 (图3)=〉按位加部818=〉 按位加部819
这里，在该路径中的4位输出计算部817 (图3)和随机化4位逆元
计算部815 (图4)的内部的关键路径如下。
首先，4位输出计算部817 (图3)的内部的关键路径如下。
4位乘法部816a=〉按位加部816e=〉按位加部816f=〉按位加部816i=〉
按位加部816j
此外，随机化4位逆元计算部815 (图4)的内部的关键路径如下。 5次方计算部820=〉按位加部823=〉按位加部824=〉随机化2位逆
元计算部825 (图7) =〉 2位输出计算部827 (图6)=〉按位加部828=〉
按位加部829
此路径中具有2位输出计算部827 (图6)和随机化2位逆元计算部
825 (图7)。它们内部的关键路径分别如下。
首先，2位输出计算部827 (图6)的内部的关键路径如下。
2位乘法部826a=〉按位加部826e=〉按位加部826f=〉按位加部826i=〉
按位加部826j
然后，随机化2位逆元计算部825 (图7)的内部的关键路径如下。 按位加部825a=〉按位加部825b
通过以上处理，随机化8位逆元计算部81 (图l)的最大逻辑级数成 为连续处理下面的处理时的逻辑级数。 17次方计算X1次 5次方计算X1次 4位乘法X1次 2位乘法X1次 按位加运算X18次
另外，这里，"按位加运算X18次"中的18是由18=4+4+4+4+2的计算得来的。
如上所述，现有技术2有最大逻辑级数变大的问题。
发明内容
本发明为解决上述现有技术2的加密处理中的问题，使用Sbox表的 安装法，提供一种比现有技术2还能够削减最大逻辑级数的加密装置，该 Sbox表使用和现有技术2同样的合成域GF ( ( (2A2) A2)、)上的逆元 运算。
为解决上述问题，本发明采用下面的结构。
艮口，采用如下的加密装置，其使用密钥，根据明文生成密文，并具备 第1随机化逆元数据生成部，该第1随机化逆元数据生成部接收随机化输 入数据和输入屏蔽值，将接收到的上述输入屏蔽值的在预定的第1有限域 中的逆元即输出屏蔽值和该输入数据的在上述第1有限域中的逆元相加， 生成随机化输出数据，所述随机化输入数据是将根据随机数决定的预定的 上述输入屏蔽值和利用上述密钥进行了预定的处理的输入数据相加得到 的数据；该加密装置根据所生成的上述随机化输出数据，生成上述密文。
根据该加密装置，输出屏蔽值是输入屏蔽值的逆元，能够实现级数较 少的简单结构的加密装置。
根据本发明，能够实现级数较少的简单结构的加密装置。
图1是表示现有技术中的随机化8位逆元计算部81的结构的框图。 图2是表示现有技术中的4位校正项计算部811的结构的框图。 图3是表示现有技术中的4位输出计算部816、 817的结构的框图。 图4是表示现有技术中的随机化4位逆元计算部815的结构的框图。 图5是表示现有技术中的随机化2位校正项计算部821的结构的框图。 图6是表示现有技术中的2位输出计算部826、 827的结构的框图。 图7是表示现有技术中的随机化2位逆元计算部825的结构的框图。 图8是表示本发明的实施方式的加密装置1的结构的框图。 图9是表示本发明的实施方式的加密部la的结构的框图。 图10是表示本发明的实施方式的随机化Roimd_n12的结构的框图。图11是表示本发明的实施方式的随机化Round—10 13的结构的框图。 图12是表示本发明的实施方式的随机化SubBytes120、 130的结构的 框图。
图13是表示本发明的实施方式的随机化S—boxl20a 120p的结构的 框图。
图14是表示本发明的实施方式的随机化8位逆元计算部101的结构 的框图。
图15是表示本发明的实施方式的17次方计算部110、 112的结构的 框图。
图16是表示本发明的实施方式的4位校正项计算部111的结构的框图。
图17是表示本发明的实施方式的16次方计算部115、 117的结构的 框图。
图18是表示本发明的实施方式的4位输出计算部118、 119的结构的 框图。
图19是表示本发明的实施方式的4位乘法部20的结构的框图。 图20是表示本发明的实施方式的2位乘法部21的结构的框图。 图21是表示本发明的实施方式的4位逆元计算部116的结构的框图。 图22是表示本发明的实施方式的2位逆元计算部142的结构的框图。 图23是表示本发明的实施方式的随机化4位逆元计算部114的结构 的框图。
图24是表示本发明的实施方式的5次方计算部141、 150、 152的结 构的框图。
图25是表示本发明的实施方式的2位校正项计算部151的结构的框图。
图26是表示本发明的实施方式的4次方计算部155、 157的结构的框图。
图27是表示本发明实施方式的2位输出计算部158、 159的结构的框图。
图28是表示本发明的实施方式的随机化2位逆元计算部154的结构 的框图。图29是表示本发明的实施方式的随机数更新部17的结构的框图。
图30是表示本发明的实施方式的8位逆元计算部171的结构的框图。
图31是表示本发明的实施方式的解密装置3的结构的框图。
图32是表示本发明的实施方式的解密部3a的结构的框图。
图33是表示本发明的实施方式的随机化InvRound_n 32的结构的框图。
图34是表示本发明的实施方式的随机化InvRoundJ) 33的结构的框图。
图35是表示本发明的实施方式的随机化Im/SubBytes331的结构的框图。
图36是表示本发明的实施方式的随机化InvS—Box331a 331p的结构 的框图。
图37是表示本发明的实施方式的随机数更新部37的结构的框图。 图38是表示加密装置1、加密装置1具有的部分之间的包含关系、及 其整体和部分之间的输入输出数据的图。 附图标记 1 加密装置 la 加密部 lb， 3b 轮密钥生成部 lc， 3c 密钥保管部 10， 30 屏蔽处理部
11， 123， 132， 31， 322， 322 AddRoundKey 12X 随机化Round—t
12 随机化Round—n
13 随机化Round—10 14， 34 中断屏蔽处理部 15， 35 随机数生成部
16， 36 随机数暂时存储部
17， 37 随机数更新部
100， 103， 170， 303 合成域变换部
101 随机化8位逆元计算部102， 172 扩张域变换兼矩阵变换部
104， 110a， 110e， lllc， 113， 115a， 118c， 118e， 140， 142a， 150a， 150e， 151c， 153， 154c， 155a， 158c， 158e， 171a， 204， 205， 207， 214， 215， 216 按位加部
110X， 110， 112， 171b 17次方计算部
20， 110b, 110c， 110d， llla， 111b, 118a， 118b， 118d， 171d， 171e 4位乘法部
111 4位校正项计算部
114 随机化4位逆元计算部
115X， 115， 117 16次方计算部
116， 171c 4位逆元计算部
118X， 118， 119 4位输出计算部
120X， 120， 130 随机化SubBytes
121X， 120a， 120b， 120c， 120p 随机化S — Box
121， 131 ShiftRows
122 MixColumns
141X， 141， 150， 152 5次方计算部 142， 156 2位逆元计算部
21， 143， 144， 150b， 150c， 150d， 151a， 151b， 158a， 158b， 158d， 200， 201， 202， 203， 2062位乘法部 151 2位校正项计算部 154 随机化2位逆元计算部 155X， 155， 157 4次方计算部 158X， 158， 159 2位输出计算部 171 8位逆元计算部 210， 211， 212， 213 逻辑积部 3 解密装置 3a 解密部
32 随机化InvRound—n
33 随机化InvRound—0
300， 370 合成域变换兼矩阵变换部301 8位随机化合成域逆元计算部
302， 372 扩张域变换部
320， 330 InvShiftRows
321， 331 随机化InvSubBytes
323 InvMixColumns
331a， 331b， 331c， 331p 随机化InvS —Box
371 8位合成域逆元计算部 81 随机化8位逆元计算部 810， 812 17次方计算部 811 4位校正项计算部 815 随机化4位逆元计算部 816， 817 4位输出计算部
8Ua， 811b， 816a， 816b， 816c， 816d 4位乘^去部
820， 822 5次方计算部
821 2位校正项计算部
825 随机化2位逆元计算部
826， 827 2位输出计算部
821a， 821b， 826a， 826b， 826c， 826d2位乘法部
811c， 811d， 813， 814， 816e， 816f， 816g， 816h， 816i， 816j， 818，
819， 821c， 821d， 823， 824， 825a， 825b， 826e， 826f， 826g， 826h， 826i，
826j， 828， 829 按位加部
具体实施例方式
技术方案l中所记载的方式(本发明的一个实施方式)的加密装置是
使用密钥从明文生成密文，具备随机数生成部，生成随机数；随机化输
入数据生成部，接收上述明文，将根据上述随机数决定的预定的输入屏蔽 值和对上述明文利用上述密钥进行了预定的处理的输入数据相加，生成随
机化输入数据；第1随机化逆元数据生成部，接收由上述随机化输入数据 生成部生成的上述随机化输入数据和上述输入屏蔽值，将接收的上述输入 屏蔽值的在预定的第1有限域中的逆元即输出屏蔽值和该输入数据的在上 述第1有限域中的逆元相加，生成随机化输出数据；以及输出数据处理部，
15接收由上述第1随机化逆元数据生成部生成的上述随机化输出数据，根据 接收到的该随机化输出数据生成上述密文。
根据本方式，为了防止通过测量副信息来分析出用于根据明文生成密 文的密钥，在根据用该密钥进行了预定的处理的输入数据加上输入屏蔽值 的随机化输入数据，生成己加上了输出屏蔽值的随机化输出数据时，输出 屏蔽值为输入屏蔽值的逆元，由此，通过级数较少的简单结构，根据随机 化输入数据生成随机化输出数据，能够形成级数少的简单结构的加密装 置。
另外，该加密装置进一步具备屏蔽值生成部，该屏蔽值生成部接收所 生成的上述随机数，根据所接收的该随机数生成上述输入屏蔽值，上述第 1随机化逆元数据生成部也可以接收所生成的上述输入屏蔽值，进行上述 生成过程。这样，就不需要从外部向加密装置输入输入屏蔽值的结构，就 能够形成简单的系统结构。
技术方案2中所记载的方式(本发明的一个实施方式)的加密装置的 上述第1随机化逆元数据生成部具备第1乘方计算部，对上述随机化输 入数据和上述输入屏蔽值进行预定的第1指数的乘方计算，分别通过各乘 方计算生成第1乘方随机化输入数据和第1乘方输入屏蔽值；校正数据生
成部，根据上述随机化输入数据和上述输入屏蔽值，生成预定的校正数据；
加法部，将所生成的上述校正数据和计算出的上述第1乘方随机化输入数
据相加，生成副随机化输入数据；第2随机化逆元数据生成部，接收上述 副随机化输入数据和上述第1乘方输入屏蔽值，将该第1乘方输入屏蔽值 的在预定的第2有限域中的逆元即屏蔽值和上述副随机化输入数据的在该 第2有限域中的逆元相加，生成随机化副输出数据；以及随机化输出数据 生成部，根据上述随机化副输出数据、上述随机化输入数据、上述输入屏 蔽值及上述第1乘方输入屏蔽值，生成上述随机化输出数据。
根据本方式，通过容易理解的结构生成随机化输出数据，减少了故障 和动作不良，能够实现设计容易，同时能够以级数少的简单结构实现加密 装置。
此外，方式A (本发明的一个实施方式)的加密装置，在随机化合成 域逆元计算部的运算中，把以往的从X二M+R向Y=MA ( — +11的变换， 替换为从X二M+R向Y=MA ( — l) +RA ( — l)变换，由此， 一方面能够比现有技术更削减最大逻辑级数， 一方面也能够实现现有方法的能够紧凑安 装的优点。
此外，方式B (本发明的一个实施方式)的加密装置，基于密钥，对 明文进行规定的加密处理，生成密文，具备随机数生成部，生成随机数; 以及第1随机化逆元计算部，接收随机化输入数据和输入屏蔽值，并进行 第l有限域上的逆元计算，输出随机化输出数据。其中，上述随机化输入 数据是通过把输入屏蔽值和输入数据相加来进行了屏蔽的值，上述随机化 输出数据是通过把输出屏蔽值和输出数据相加来进行了屏蔽的值，上述输 入屏蔽值是根据上述随机数决定的值，上述输出数据是上述输入数据的在 上述第1有限域中的逆元，上述输出屏蔽值是上述输入屏蔽值的在上述第 1有限域中的逆元。
这里，该方式B中的加密装置的上述第1随机化逆元数据计算部也可 以具备第l乘方计算部，分别对上述随机化输入数据和上述输入屏蔽值 进行第1指数的乘方运算，生成第1乘方随机化输入数据和第1乘方输入 屏蔽值；校正数据生成部，根据上述随机化输入数据和上述输入屏蔽值， 生成校正数据；加法部，将上述校正数据和上述第1乘方随机化输入数据 相加，生成副随机化输入数据；第2随机化逆元计算部，接收上述副随机 化输入数据和上述第1乘方输入屏蔽值，进行第2有限域上的逆元计算， 生成随机化副输出数据；以及随机化输出数据生成部，根据上述随机化副 输出数据、上述随机化输入数据、上述第1乘方输入屏蔽值及上述输入屏 蔽值，生成上述随机化输出数据。
另外，该方式B中的加密装置的上述随机化输出数据生成部也可以是 具备第2乘方计算部，对上述随机化输入数据和上述输入屏蔽值分别进 行第2指数的乘方计算，生成第2乘方随机化输入数据和第2乘方输入屏 蔽值；逆元运算部，对上述第1乘方输入屏蔽值进行上述第2有限域上的 逆元计算，生成逆元乘方输入屏蔽值；以及随机化输出数据计算部，根据 上述随机化副输出数据、上述第2乘方随机化输入数据、上述逆元乘方输 入屏蔽值和上述第2乘方输入屏蔽值，生成上述随机化输出数据。
另外，方式C的(本发明的一个实施方式)解密装置，基于密钥，对 密文进行规定的解密处理，生成译文，具备随机数生成部，生成随机数;' 第l随机化逆元计算部，接收随机化输入数据和输入屏蔽值，进行第l有
17限域上的逆元计算，输出随机化输出数据。其中，上述随机化输入数据是 通过把输入屏蔽值和输入数据相加而进行了屏蔽的值，上述随机化输出数 据通过把输出屏蔽值和输出数据相加而进行了屏蔽的值，上述输入屏蔽值 是根据上述随机数决定的值，上述输出数据是上述输入数据的在上述第1 有限域中的逆元，上述输出屏蔽值是上述输入屏蔽值的在上述第1有限域 中的逆元。
(实施方式)
下面，参照附图对本发明的实施方式加以说明。
另外，在实施方式中，虽然使用了合成域GF ( ( (2A2) A2) A2)及其 子域GF ( (2A2) A2) 、 GF (2、) 、 GF (2)的运算，但这些会成为下面 的关系。
用不可约多项式xA2+x+l对GF(2)进行2次扩张而得的是GF(2A2)。 用不可约多项式xA2+x+小对GF( 2A2)进行2次扩张而得的是GF( (2、) A2)。
用不可约多项式/2+x+入(二进制数)对GF ( (2A2)八2)进行2次 扩张而得的是GF ( ( (2A2) A2) A2)。
此时，设xA2+x+l=0的根为a时，4> = a、入=a 、+a ，所以分别进 行位标记为4)=10 (二进制数)、人=1100 (二进制数)。
<实施方式的概要〉
在进行实际处理的详细说明之前，首先，与非专利文献l即现有技术 2中公开的现有方式进行对比来说明本实施方式的概要。
在非专利文献1中公开的现有技术即现有技术2中，随机化8位逆元 计算部81 (图1等)对输入数据X二M ( + ) R，使用随机数R及r来进行 随机化逆元计算，生成了输出数据Y二MT ( — 1) ( + ) R。这里，X是将本 来的数据M用随机屏蔽R进行屏蔽后的值，随机化8位逆元计算部81求 得在GF ( ( (2A2) A2) A2)中的M的逆元M八(一l)，并以用随机屏蔽 R对该值实施了屏蔽的形式M^ ( — l) ( + ) R进行输出。
本发明的实施方式中，将上述随机化8位逆元计算处理，用随机数R 对输入数据X=M ( + ) R进行随机化逆元计算，生成输出数据Y=MA ( — l) (+) RA ( — 1)。即，输出数据的随机屏蔽值在现有技术2中是R，但在 本发明中，变成了y 。这样，通过计算不同于现有技术2的输出数据，如后面所述，就能够比现有技术更削减最大逻辑级数。
图8 图38是分别表示实施方式中加密装置1及加密装置1的各部分的图。
然后，图38是表示实施方式中的加密装置1的整体和各部分之间的 包含关系的图。下面，适当参照图38，对图1~图23所表示的加密装置1 进行说明。
如图38所示，加密装置1 (图8)具备随机化8位逆元计算部101 (图 13、图14)。加密装置1 (图8)具备加密部la (图8、图9)。加密部 la具备屏蔽处理部10 (图9)、随机化Round—tl2X(随机化Round—nl2(图 9、图10)、随机化Round—10 13(图9、图U))、中断屏蔽处理部14 (图9)。 另夕卜，在图38中，省略掉了图8~图37中所示的加密装置1的各部分中的 一部分。
并且，图38中所示的随机化Round一t12 (图9及图10中所示的随机 化Round—n12、图9及图11中所示的随机化Round—10)具备随机化 SubBytesl20X(图10、图ll、图12)。该随机化SubBytesl20X具备随机化 S — Boxl21X(图12中所示的随机化S — Boxl20a 随机化S—Boxl20p)，另 外，该随机化S—Boxl21X具备随机化8位逆元计算部IOI(图13，图14)。
并且，如图38所示，该随机化8位逆元计算部101 (图38、图14等) 被输入随机化输入数据ID8t=Tl (V8t) +T1 (Rt)，根据利用屏蔽值进行 了屏蔽的该随机化输入数据ID8t二Tl (V8t) +T1 (Rt)，计算出随机化输 出数据OD8t二Tl (V8t) A ( — l) +T1 (Rt) A ( — l)，并输出计算出的该 OD8t，所述屏蔽值是基于Rt变成Tl (Rt)的值。总之，该随机化8位逆 元计算部101 (图13、图14)对设为M-T1 (V8t) 、 R=T1 (Rt)的上述 输入数据X二M ( + ) R，进行生成输出数据Y二]Vr ( — l) ( + ) R ( — l) 的处理。
本实施方式中的加密装置1 (图38、图8)具备随机化8位逆元计算 部101，该随机化8位逆元计算部101根据X二M ( + ) R生成Y=MA ( —1) (+ ) RA ( — l)，能够削减最大逻辑级数。
下面，对那样的加密装置1的详细处理进行说明。 <加密装置1>
图8是表示本发明的实施方式中的加密装置1的结构的框图。加密装置l (图8)具备加密部la (图9)、轮密钥生成部lb及密钥 保管部lc。
加密装置1 (图8)针对输入加密装置1的128位明文(平文)P (128 位)，使用装置内部保持的密钥K (128位)进行被随机化的AES加密处 理(AES: Advanced Encryption Standard)，并输出密文C (128位)。密 文C和针对明文P使用密钥K进行AES加密处理的结果相同。此外，由 于在装置内部利用每次加密处理中随机生成的随机数对加密处理过程中 的加密处理中间值进行随机化，因此电力分析攻击的密钥K的分析就变得 困难。下面，对加密装置1的处理过程进行说明。
另外，详细的讲，AES加密是在加密处理中反复循环的、采用了以下 两种结构中后者的SPN结构的加密，所述两种结构之一是反复加密的代表 性的构成法即Feistel结构，另一结构是SPN (Substitution Permutation Network Structure)结构。
这里，加密装置1例如也可以是设置在IC卡中的加密装置。
密钥保管部lc保管在加密装置1中事先设定的密钥K。密钥K也可 以在制造加密装置1时设定，也可以在加密装置1制造完成后在装置内生 成的密钥保管部lc中设定。如果输入明文P，加密装置1就进行以下处理。
(1) 密钥保管部lc将保管的密钥K输入到轮密钥生成部lb。
(2) 轮密钥生成部lb按照AES加密方式的轮密钥生成处理，根据密 钥K生成轮密钥RK0 RK10 (各128位)，输入到加密部la。另外，轮 密钥生成处理已经记载在非专利文献2中而予以公开，这里就不做详细说 明。
(3) 加密部la使用轮密钥RK0 RK10对明文P进行后述的加密处理， 生成密文C并输出。
接着，对加密部la的处理进行说明。 <加密部la>
图9是表示加密部la的结构的框图。
如图所示，加密部la (图8、图38)具备屏蔽处理部10、 AddRoundKeyll、随机化Round—n12 (图IO)、随机化RoundJ0 13 (图
11)、中断屏蔽处理部14、随机数生成部15、随机数暂时存储部16以及 随机数更新部17。
20加密部la对明文P (128位)使用轮密钥RK0 RK10 (128位X11个) 进行加密处理，生成密文(128位)并输出。加密部la在被输入的轮密钥 RK0 RK10中，把轮密钥RKO输入AddRoundKeyl 1 ，轮密钥RKn(n=l 9) 输入随机化Round_nl2 (图10) ， RK10输入随机化Round—10 13 (图11)。
加密部la进行以下的处理。
(1) 随机数生成部15随机地生成随机数RO (8位)。然后，随机数 生成部15将生成的随机数RO暂时存储在随机数暂时存储部16。另外，作 为一个例子，在每一次新的明文P被输入到加密装置1中，加密装置1开 始新的加密处理时，随机数生成部15就生成新的随机数R0，也可以存储 生成的随机数R0。
(2) 屏蔽处理部10使用随机数暂时存储部16中存储的随机数R0， 对明文P进行如下的按位加运算，从而求得数据A (128位)。经过该处 理，利用随机屏蔽值RO对明文P进行屏蔽。
A=P ( + ) (R0， R0， R0，…,R0)
这里，(R0， R0， R0，…，R0)表示将16个R0 (8位)结合的128 位数据。另外，下面，如果不特别说明，就将16个8位数据X结合而成 的128位数据表示成(X， X， X，…，X)。
另外，图8所示的P在图38中由标记U表示。此外，图8中所示的 C在图38中由标记C表示。此外，图9中所示的A在图38中图示为IA。 此外，图9中所示的B、 D在图38中由标记IAt (t=l 9或t=10)表示。 此外，图9中表示的E在图38中由标记OA10=OAt (t=10)表示。
(3) 随机数更新部17对随机数暂时存储部16中存储的随机数R0进 行后述的随机数更新处理，生成R1，并将随机数暂时存储部16中存储的 随机数R0更新为R1。
(4) AddRoundKeyll对在上述(2)中由随机数生成部15求得的上 述A，使用下面的RKO进行密钥相加处理，求得B1。这就是AES加密算 法标准中规定的AddRoundKey处理。
B1=A ( + ) RKO
(5) 然后，随机化Round—nl2关于n4、 2、 3、…、9反复执行下面 的处理。
(5 — 1)随机化Round一n12使用轮密钥RKn和存储在随机数暂时存储部16中的随机数Rn，对Bn (向该随机化Round_nl2输入的输入数据B 中的第n个数据)进行后述的随机化Round—n处理，生成Bn+l。然后， 随机化Round—n12，在『9的情况下，即所生成的B (n+l)是B (n+l) =B10的情况下，使D=B10，将D输入随机化Round—10 13;在n#9的情 况下，即11=1、 2、…、9，所生成的B (n+l)是B2、 B3、…、B9中某一 个的情况下，将该B (n+l)再次输入到Round一n12。
(5—2)随机数更新部17对随机数暂时存储部16中存储的随机数Rn 进行后述的随机数更新处理，生成Rn+l，将随机数暂时存储部16中存储 的随机数Rn更新为Rn+1。随机数更新部17根据由随机数生成部15生成 的随机数RO,生成随机数R1、随机数R2、…、随机数Rll，并将随机数 暂时存储部16中存储的随机数更新为生成的各个随机数，由此将各该随 机数分别提供给屏蔽处理部10、随机化Round—n12、 Round—10 13以及中 断屏蔽处理部14中与该随机数对应的结构中。随机数更新部17通过随机 数暂时存储部16将随机数R0提供给屏蔽处理部10，将随机数R1 R9提 供给随机化Round—n12，将随机数R10提供给随机化Round—10 13，将随 机数Rll提供给中断屏蔽处理部14。
(5—3)加密部la在n=9的情况下，结束反复处理的循环，转移到 接下来的随机化Round—10 13的处理，在n#9的情况下，将n的值加1， 再次执行上述(5 — 1) (5 — 3)的处理。
(6) 随机化Round—10 13使用轮密钥RK10和随机数暂时存储部16 中存储的随机数R10，对经过上述(5)的处理得到的向随机化Round一10 13 输入的输入数据D (128位)进行后述的随机化Round—10处理，生成数据 E (128位)。随机化RoundJ0 13将数据E输入中断屏蔽处理部14中。
此外，随机数更新部17对随机数暂时存储部16中存储的随机数R10 进行后述的随机数更新处理，将随机数暂时存储部16中存储的随机数R10 更新为随机数Rll。随机数更新部17通过向该R11的更新，将随机数Rll 提供给中断屏蔽处理部14。
(7) 中断屏蔽处理部14使用随机数暂时存储部16中存储的随机数 Rll，在上述(6)中对从随机化Round—10得到的数据E进行下面的按位 加运算，生成密文C (128位)。经过该处理，被屏蔽的数据E被中断屏 蔽(去除屏蔽的影响)，从而得到没有被屏蔽的密文C。C=E ( + ) RU
(8)加密部la将在上述(7)中得到的密文C作为加密部la的输出 数据进行输出。
接着，对在加密部la(图9)内部使用的随机化Round—n12、随机化 Round—10 13的详细结构进行说明。 <随机化Round—nl2>
图10是表示随机化Round—n12 (图9)的结构的框图。
如图10中所示，随机化Round—n12 (图9、图10、图38)具备随机 化SubBytes120 (图12、图38) 、 ShiftRows121 、 MixColumns122以及 AddRoundKey123。
而且，随机化Round—n12使用随机数Rn和轮密钥RKn(n-l、 2、 ..9)， 对向该随机化Round—n12输入的输入数据X (与加密部la的处理说明(图 9)中的数据Bn相对应)进行随机化Round处理，生成输出数据Y(与加 密部la处理说明中的数据Bn+l (图9)相对应)。
另外，随机化Round—n12进行的随机化Round—n处理是如下的处理 对用屏蔽值(Rn， Rn，…，Rn)进行了屏蔽的输入数据X=M ( + ) (Rn， Rn，， Rn)执行AES加密算法标准中规定的1轮处理，从而生成用屏 蔽值(Rn+1， Rn+1，…，Rn+1)屏蔽了的轮处理结果Y-P ( + ) (Rn+1， Rn+1，…，Rn+1)。此时，P与对M进行了 AES加密算法标准中规定的 1轮处理的结果一致。这里，该X是图9的说明中的随机化Round—n处理 的输入数据Bn (n=l、 2、…、9)，此外，该Y是图9的说明中的输出数 据B (n+l) 。 M、 P是分别从Bn、 Bn+1去除屏蔽值的影响后的本来的值 (图38中图示的Vt、 V (t+l))。
另外，图10中的X在图38中由标记IAt (t=l、 2、…、9)表示，Y 由标记OBt (t=l、 2、…、9)表示，Rn由标记Rt (t=l、 2、…、9)表示。
具体说来，随机化Round—n12 (图9、图10)进行如下的处理。
(1) 随机化Round—nl2具备的随机化SubBytes120 (图10、图12) 使用从隨机数暂时存储部16取得的随机数Rn (8位)，对向该随机化 Round—n输入的输入数据X (128位)进行后述的随机化SubBytes处理， 生成数据A (图10)。
(2) ShiftRows121 (图10)对上述(1)中生成的上述数据A进行
23AES加密算法标准中规定的ShiftRows处理，生成数据B (128位)。另 外，关于ShiftRows的详细内容，由于在(非专利文献2)中已经公开， 故不做详细说明。
(3) 接着，MixColumns122 (图10)对上述(2)中生成的上述数据 B进行AES加密算法标准中规定的MixColumns处理，生成数据C (128 位)。另外，关于MixColumns的详细内容，由于在(非专利文献2)中 已经公开，故不做详细说明。
(4) 然后，AddRoundKey 123使用轮密钥RKn，对上述(3)中生成 的上述数据C进行AES加密算法标准中规定的AddRoundKey处理，生成 数据Y( 128位)。然后，AddRoundKey 123将生成的Y作为随机化Round—n12 的输出数据来进行输出。另外，关于AddRoundKey的详细内容，由于在
(非专利文献2)中己经公开，故不做详细说明。
另外，图10的数据A在图38中由标记OBt (t=l、 2、…、9)表示。 <随机化Round—10 13>
图11是表示随机化Round—10 13的结构的框图。
随机化Round—10 13 (图9、图11)具备随机化SubBytes130 (图11、 图12) 、 ShiftRows131、 AddRoundKey 132。
然后，如图11所示，随机化Round—10 13的结构与从随机化Round一n12 去掉MixColumns122的结构相同。这与AES加密算法的标准的最后一轮 不进行MixColumns处理的情况相对应。除此之外，和随机化Round一n12 相同，故省略详细的说明。
另外，随机化Round—10处理是如下的处理对用屏蔽值(R10，R10，…， R10)进行了屏蔽的输入数据X-M ( + ) (R10， R10，， R10)执行AES 加密算法标准中规定的最后一轮处理，生成用屏蔽值(Rll， Rll，…， Rll)屏蔽了的最后一轮处理结果Y=P ( + ) (Rll， Rll，…，Rll)。此 时，P与对M进行了 AES加密算法标准中规定的最后一轮处理的结果一 致。
另外，此处，该X在图9的说明中是数据D，此外，该Y在图9的说 明中是输出数据E， M、 P是从D、 E去除屏蔽值的影响的本来的值(图 38中的V10、 Vll)。
此外，在图38中，由标记OB100Bt (t=10)表示图10中的数据A。接着，随机化Round一n12 (图9、图10)对在随机化Round—10 13 (图 9、图11)中使用的随机化SubBytes120、 130 (图12)进行详细的说明。 <随机化SubBytes 120、 130>
图12是表示随机化SubBytesl20X(随机化SubBytes120(图9、图10)、 随机化SubBytes130 (图9、图11))的结构的框图。例如，随机化 SubBytesl20X是随机化SubBytes120，其他的随机化SubBytes120具有和 该随机化SubBytes120相同的结构。
随机化SubBytesl20X使用随机数R (8位)对输入数据X (128位) 进行随机化S—Box处理，生成输出数据Y (128位)。这里的输入数据X 和随机化Round—n12的处理说明(图10)中的数据X相当，此外，和随 机化RouncL10 13的处理说明(图IO)中的数据X相当。此外，随机数R 和随机化Round—n12的处理说明(图IO)中的随机数Rn相当，和随机化 Round—10 13的处理说明(图ll)中的随机数R10相当。此外，输出数据 Y和随机化RouncLn12的处理说明(图10)中的数据A相当，和随机化 Round—10 13的处理说明(图ll)中的数据A相当。
另夕卜，在图38中，图12中的X由标记IBt表示，Y由标记OBt表示， R由Rt表示。
随机化SubBytesl20X具备随机化S — Boxl20a 随机化S—Boxl20p。 随机化SubBytesl20X (随机化S—Boxl20a 随机化S —Boxl20p)进
行以下的处理。
(1) 随机化SubBytesl20X将输入数据从高位开始按每8位进行分割， 分割为X[O]、 X[l]、…、X[15](参照图12)。
(2) 随机化S—Boxl20a 120p对分割后的X
、 X[l]、…、X[15]， 分别用隨机数R进行随机化S—Box处理，分别生成Y
、Y[1]、…、Y[15]。 关于随机化S—Box处理的详细内容，将在后面加以说明。
(3) 然后，随机化SubBytesl20X将生成的Y[O]、 Y[l]、…、Y[15] 从高位开始按该顺序连结，变成128位数据Y。然后，随机化SubBytesl20X 将该Y作为随机化SubBytesl20X的输出数据来输出。
另夕卜，随机化SubBytes120、 130的处理是如下的处理对用屏蔽值(R， R，…，R)进行了屏蔽的输入数据X二M ( + ) (R， R，…，R)进行AES 加密算法标准中规定的SubBytes处理，生成用屏蔽值(S， S，…，.S)屏蔽的处理结果Y二P ( + ) (S， S，…，S)。此时，P与对M进行AES加
密算法标准中规定的SubBytes处理的结果一致，屏蔽值S与随机数更新部
17对屏蔽值R进行了随机数更新处理的结果相等。
另外，在图38中，该M图示为Vt， P则由S—Box (Vt)表示。 然后，对在随机化SubBytesl20X (随机化SubBytes120、 130)中使用
的随机化S — Boxl20a 120p的详细内容进行说明。 <随机化S—Boxl20a~120p>
图13是表示随机化S—Boxl20X(随机化S—Boxl20a 随机化S—Box 120p:图12)的结构的框图。
随机化S—Boxl21X (图13、图12)具备合成域变换部100 (参照 数学式l)、随机化8位逆元计算部101 (图ll、图38)、扩张域变换兼 矩阵变换部102 (参照数学式2)、按位加部104、合成域变换部103 (参 照数学式1)。
随机化S—Boxl21X是使用随机数R (8位)对输入数据X (8位)进 行随机化S—Box处理，求得输出数据Y(8位)的处理。这里的输入数据 X相当于随机化SubBytes 120X(图12)的处理说明中的数据X[O] 、 X[ 1 ]、…、 X[15]中的某一个，随机数R相当于随机化SubBytesl20X的处理说明(图 12)中的随机数R。此外，输出数据Y相当于随机化SubBytesl20X的处 理说明(图12)中的数据Y[O]、 Y[l]、…、Y[15]中的某一个。
另外，在图38中，由标记IC8t表示该X，由标记OC8t表示Y，由标 记Rt表示R。
随机化S—Boxl21X进行以下的处理。 (1)合成域变换部100将X (8位)从高位开始按每一位迸行分割， 分割成X7、 X6、、 X0。然后，合成域变换部100进行下面的数学式1 的矩阵计算，将通过矩阵计算求得的A7、 A6、…、AO从高位开始按该顺 序结合，作为合成域变换部100的输出数据A (8位)。另外，下述的矩 阵计算是用mod 2进行的。即，在下述的矩阵计算中，是0+0=1+1=0， 0+1=1+0=1。
数学式1广 、 A7卜010〇00、 0广 X7
A601111110X6
A5.01110010X5
A410100010X4
A3〇0011010X3
A201010110X2
A101101100X1
LA0JL10101001J
、
乂
(2) 并且，其他的合成域变换部103和上述的(1) 一样，将R (8 位)从高位开始按每l位进行分割之后，进行数学式l的矩阵计算，根据 R (8位)生成S (8位)。
(3) 接着，随机化8位逆元计算部101利用在上述(2)中生成的随 机数S (8位)对上述(1)中生成的输入数据A (8位)进行后述的随机 化8位逆元计算，生成输出数据B (8位)。
(4) 扩张域变换部兼矩阵变换部102对上述(3)中生成的数据B (8 位)，根据下述的数学式2的矩阵计算式，用和上述(1)同样的方法， 即从高位开始按每一位进行分割，并进行矩阵计算，来生成数据C (8位)。
数学式2
f071广 0111010、 0 、
C611010000巳6
C500101100B5
C41101001B4
C3'—10110101已3
C210010011已2
C110110111已i
—J111010」
(5)按位加部104将在上述(4)中生成的数据C(8位)和常数01100011 (二进制数)进行每位的按位加运算，生成数据Y (8位)。
随机化S—boxl21X将上述(5)中生成的该Y作为随机化S — Boxl21X
的输出数据进行输出。另外，随机化S—Boxl20a 120p的处理是如下的处理对用屏蔽值(R， R，…，R)进行了屏蔽的输入数据X二M ( + ) (R， R，…，R)进行AES 加密算法标准中规定的SubBytes处理内的S—Box表变换，生成用屏蔽值 (S， S,…，S)进行了屏蔽的处理结果Y=P ( + ) (S， S，…，S)。此 时，P与对M进行了 AES加密算法标准中规定的SubBytes处理内的S — Box表变换的结果一致，屏蔽值S和随机数更新部17对屏蔽值R进行随 机数更新处理的结果相等。
另外，在图38中，由标记V8t表示该M，由S—box (v8t)表示P。 在图38中，由标记ID8t表示该A，由标记OD8t表示B。
然后，对在随机化S — Boxl20a 120p内部分别使用的随机化8位逆元 计算部101的详细内容进行说明。
<随机化8位逆元计算部101>
图14是表示随机化8位逆元计算部101的结构的框图。
随机化8位逆元计算部101 (图13、图14、图38)具备17次方运 算部110 (图15) 、 17次方运算部112 (图15) 、 4位校正项计算部111 (图16) 、 16次方运算部115 (图17) 、 16次方运算部117 (图17) 、 4 位输出计算部118 (图18) 、 4位输出计算部U9 (图18) 、 4位逆元计 算部116(图21)、随机化4位逆元计算部114 (图23)、按位加部113。
随机化8位逆元计算部101 (图13、图14)使用随机数R (8位)， 对输入数据X (8位)进行随机化8位逆元计算处理，输出输出数据Y (8 位)。这里的输出数据X如前所述，相当于随机化S—Boxl20a 120p的处 理说明(图13)中的数据A，随机数R相当于随机化S—Boxl20a 120p 的处理说明(图13)中的随机数S。此外，输出数据Y相当于随机化S — Boxl20a 120p的处理说明(图13)中的数据B。
另外，在图38中，由标记ID8t表示该X，由标记RDt表示R，由标 记0D8t表示Y。
随机化8位逆元计算部101执行以下的处理。 (1)随机化8位逆元计算部101，首先将数据X (8位)从高位开始 按每4位进行分割，分割成XO (4位)、XI (4位)。然后，随机化8位 逆元计算部101同样地将随机数R (8位)从高位开始按每4位进行分割， 分割成RO (4位)、Rl (4位)。然后，随机化8位逆元计算部101将
28X0和XI输入17次方运算部110，将X0、 XI、 R0及Rl输入4位校正项 计算部111，将R0和Rl输入17次方运算部112。
(2) 然后，17次方运算部110对输入的X0和X1进行后述的17次 方计算处理，生成输出数据A (4位)。同样地，其他的17次方运算部 112对输入的R0和R1进行17次方计算处理，生成输出数据C (4位)。
(3) 另外，4位校正项计算部111对输入的XO、 XI、 RO、 Rl进行 后述的4位校正项计算处理，生成输出数据B (4位)。
(4) 然后，按位加部113对(2)中生成的数据A和(3)中生成的 数据B进行按位加运算，生成数据D (8位)。
(5) 然后，随机化4位逆元计算部114利用上述(2)中生成的数据 C (4位)，对上述(4)中生成的数据D进行后述的随机化4位逆元计算 处理，生成数据E (4位)。
(6) 此外，16次方运算部115对输入到随机化8位逆元计算部101 的数据X (8位)进行后述的16次方计算处理，生成数据F (8位)。然 后，随机化8位逆元计算部101将生成的数据F从高位开始按每4位进行 分割，分割为FO (4位)、Fl (4位)。同样地，其他的16次方运算部 117对输入到随机化8位逆元计算部101的数据R (8位)进行16次方计 算处理，生成数据H。与上述数据F的情况一样，随机化8位逆元计算部 101将生成的该数据H从高位开始按每4位进行分割，分割为HO (4位)、 Hl (4位)。
(7) 另外，4位逆元计算部116，在上述(2)中，对由在图14的下 侧示出的17次方运算部112生成的数据C (4位)进行后述的4位逆元计 算处理，生成数据G (4位)。
(8) 然后，4位输出计算部118对上述(5)中生成的数据E (4位)、 上述(7)中生成的数据G (4位)、上述(6)中由数据F分割成的数据 FO (4位)、及同样在上述(6)中由数据H分割成的数据HO (4位)进 行后述的4位输出计算处理，生成数据YO (4位)。同样地，其他的4位 输出计算部119对数据E (4位)、数据G (4位)、数据F1 (4位)、及 数据H1 (4位)进行4位输出计算处理，生成数据Y1 (4位)。然后，随 机化8位逆元计算部101，将这样生成的数据YO和Yl从高位开始按该顺 序连结成8位数据Y。然后，随机化8位逆元计算部101将连结的数据Y作为随机化8位逆元计算部101的输出数据来输出。
另外，这样进行的随机化8位逆元计算部101的处理是如下的处理
对用屏蔽值R进行了屏蔽的输入数据X=M( + )R进行合成域GF (((2A2) A2)A2)的逆元计算，生成用屏蔽值R、一1)进行了屏蔽的处理结果￥=乂八 (—1) ( + ) R ( — 1)。此时，XA ( — 1)是在合成域GF ( ( (2A2) A2) A2)中X的逆元，屏蔽值RA (—1)是在合成域GF ( ( (2A2) A2)、)中 R的逆元。
接着，对在随机化8位逆元计算部101的内部使用的17次方运算部 110、 112 (图15中示出的17次方运算部110X) 、 4位校正项计算部111 (图16)、 16次方运算部115、 117(图17中示出的16次方运算部115X)、 4位输出计算部118、 119 (图18中示出的4位输出计算部118X)的详细 内容依次进行说明。
<17次方运算部110、 112〉
图15是表示17次方运算部110X的图。
17次方运算部110X (图14、图15)具备4位乘法部110b (图19)、 4位乘法部110c (图19) 、 4位乘法部110d (图19)、按位加部110a、 按位加部110e。
而且，17次方运算部110X对输入数据X0 (4位)、XI (4位)进行 合成域GF ( ( (2A2) A2) A2)上的17次方计算处理，生成数据处理结果 Y (4位)。此时，对将输入数据X0、 XI从高位开始按该顺序连结而成的 8位数据X进行在合成域GF ( ( (2A2) A2) A2)上的17次方计算的结果 成为Y。艮口
Y=XA (17) in GF ( ( (2、) A2) A2)
此时，成为￥^5= (XA17) A15=XA255，由于X是GF ( ( (2、)、) 、)上的元素，所以YA15=XA255=1。即，Y的位数是15， Y是子域GF( (2、) A2)上的元素。gp， Y是4位的数据。
此外，这里的输入数据X0、 XI相当于随机化8位逆元计算部101的 处理说明(图14)中的数据X0、 X1或者R0、 Rl，输出数据Y相当于随 机化8位逆元计算部101的处理说明(图14)中的数据A或者C中的某 一个。
这里，17次方运算部110X在子域GF ( (2A2) A2)上进行下面的计
30算，生成输出数据Y。
Y=1100 (二进制数)X (X0A2) +X1X (X0+X1) in GF ( (2、) A2) 在GF ( (2A2) A2)上的加法运算是对每位的按位加运算(按位加部
110a、 110e)。关于GF ( (2、) A2)上的乘法运算(4位乘法部110b、
110c、 110d)的详细内容，将在后面加以说明。 <4位校正项计算部111>
图16是表示4位校正项计算部111的结构的框图。
4位校正项计算部111 (图14、图16)具备4位乘法部111a (图19)、 4位乘法部111b (图19)以及按位加部lllc。
然后，4位校正项计算部111对输入数据XO (4位)、XI (4位)、 R0 (4位)、Rl (4位)进行4位校正项计算处理，生成输出数据B (4 位)。这里的输入数据XO、 XI、 R0、 Rl分别相当于随机化8位逆元计算 部IOI的处理说明(图14)中的数据XO、 XI、 R0、 Rl，输出数据B相当 于随机化8位逆元计算部101的处理说明(图14)中的数据B。
这里，4位校正项计算部111在子域GF ( (2A2) A2)上进行下面的计 算，输出数据B。
B=X0XR1+X1XR0 in GF ( (2、)、)
然后，这里，在GF ( (2A2) A2)上的加法运算是对每个位的按位加 运算(按位加部lllc)。关于GF ( (2A2) A2)上的乘法运算(4位乘法 部llla、 111b)的详细内容，将在后面加以说明(图19)。
<16次方计算部115、 117>
图17是表示16次方计算部115X (16次方计算部115 (图4) 、 16 次方计算部117 (图14))的结构的框图。
而且，16次方计算部115X对输入数据X(8位)进行合成域GF(((2A2) A2) A2)上的16次方计算，将其计算结果作为Y (8位)输出。此时，对 输入数据X进行了合成域GF ( ( (2、) A2) A2)上的16次方计算的结果 成为Y。
Y=XA (16) inGF ( ( (2、) A2)、)
此外，这里的输入数据X相当于随机化8位逆元计算部101的处理说 明(图M)中的数据X或R中的某一个，输出数据Y相当于随机化8位 逆元计算部101的处理说明(图14)中的数据F或H中的某一个。这里，16次方计算部115、 117将输入数据X从高位开始按每4位进 行分割，分割成X0、 XI，然后在GF ( (2A2) A2)上进行下面的计算，求 得Y0、 Yl。
Y0=X0
Y1=X0+X1 inGF ( (2、)、)
然后，这里，GF ( (2A2) A2)上的加法运算是对每个位的按位加运算 (按位加部115a) 。 16次方计算部115X将这样求得的Y0、 Yl依照该顺 序结合成8位数据Y。该Y成为16次方计算部115、 117的输出数据。 <4位输出计算部118、 119>
图18是表示4位输出计算部118X (4位输出计算部118X (图14)、 4位输出计算部119 (图14))的结构的框图。
4位输出计算部118X具备4位乘法部118a(图19)、4位乘法部118b (图19) 、 4位乘法部118d (图19)、按位加部118c、按位加部118e。
然后，4位输出计算部118X对输入数据E (4位)、G (4位)、F (4 位)、H (4位)进行4位输出计算处理，输出输出数据Y。这里的输入数 据E、 G、 F、 H分别和随机化8位逆元计算部101的处理说明(图14)中 向4位输出计算部118输入的输入数据E、 G、 FO、 HO相对应，此外，分 别和向4位输出计算部119输入的输入数据E、 G、 Fl、 Hl相对应。此外， 输出数据Y和随机化8位逆元计算部101的处理说明(图14)中4位输 出计算部118的输出数据YO相对应，和4位输出计算部119的输出数据 Yl相对应。4位输出计算部118、 119在GF ( (2A2)、)上进行下面的计 算，求得Y，并输出所求得的Y。
Y=EXF+GXF+EXH in GF ( (2l) A2)
这里，在GF ( (2A2) A2)上的加法运算是对每个位的按位加运算(按 位加部118c、 118e)。关于GF ( (2、) A2)上的乘法运算(4位乘法部 118a、 118b、 118d)的详细内容，将在后面加以说明(图19)。
接着，对前面说明的各种处理中用到的各个4位乘法部的详细内容， 即图15所示的4位乘法部110b及4位乘法部110c、图16示出的4位乘 法部111a及4位乘法部lllb、图18示出的4位乘法部118a、 4位乘法部 118b及4位乘法部118d的详细内容进行说明。另夕卜，图30中示出的8位 逆元计算部171具备的4位乘法部171d和4位乘法部171e也相同。另外，这里，这些4位乘法部171d等都具有的图30所示的8位逆元计算部171 是图29示出的随机数更新部17 (参照图14)的一部分。 <4位乘法部20>
图19是表示4位乘法部20的结构的框图。
前面说明的各种处理中用到的、上述列举的4位乘法部的结构都和这 里说明了 4位乘法部20相同。另外，和这一点相同的是，上述的4位输 出计算部118、 4位输出计算部119的任一个的结构都和图18中示出的4 位输出计算部118X相同。
4位乘法部20具备2位乘法部200 (图19) 、 2位乘法部201 (图 19) 、 2位乘法部202 (图19) 、 2位乘法部203 (图19) 、 2位乘法部 206 (图19)、按位加部204、按位加部205、及按位加部207。
而且，4位乘法部20对输入数据X(4位)、Y(4位)进行在GF( (2A2) A2)上的乘法运算，输出乘法运算结果Z (4位)。此时，
Z=XXY in GF ( (2、)八2)
然后，4位乘法部20将输入数据X、 Y分别从高位开始按每2位分割， 分割成XO (2位)、XI (2位)、及YO (2位)、Yl (2位)。然后，在 GF (2、)上执行下面的计算式，求得ZO、 Zl。 ZO=XOXY1+X1XYO+XOXYO in GF (2、) Z140(二进制数)XX0XY0+X1XY1 in GF (2、) 然后，4位乘法部20将对上述Z0、 Zl从高位开始按该顺序连结而成 的4位数据Z，作为4位乘法部20的输出来输出。
这里，GF (2A2)上的加法运算是对每个位的按位加运算(按位加部 204、 205、 207)。关于GF (2'2)上的乘法运算(2位乘法部200、 201、 202、 203、 206:图19)的详细内容，将在下面加以说明。 <2位乘法部21>
图20是表示2位乘法部21的结构的框图。
前面说明的各种处理中用到的2位乘法部的结构都和这里说明的2位 乘法部20相同。另外，.图21的2位乘法部143及2位乘法部144、图 24的2位乘法部150b、 2位乘法部150c及2位乘法部150d、图25的2 位乘法部151a及2位乘法部151b、图27的2位乘法部158a、 2位乘法部 158b及2位乘法部158d都具有和该图20示出的2位乘法部21相同的结
33构。
2位乘法部21具备逻辑积部210、逻辑积部211、逻辑积部212、逻辑积部213、按位加部214、按位加部215、按位加部216。
然后，2位乘法部21对输入数据X (2位)、Y (2位)进行GF (2、)上的乘法运算，输出乘法运算结果Z (2位)。此时
Z=XXY inGF (2'2)
然后，2位乘法部21将输入数据X、 Y分别从高位开始按每1位进行分割，分割成X0 (1位)、XI (1位)、Y0 (1位)以及Yl (1位)。而且，2位乘法部21在GF (2)上执行下面的计算式，求得Z0、 Zl。
Z0=X0XY1+X1XY0+X0XY0 in GF (2)
Z1=X0XY0+X1XY1 in GF (2)
而且，2位乘法部21将上述的Z0、 Zl从高位开始按该顺序连结，将连结的2位数据Z作为2位乘法部21的输出来输出。
这里，GF (2)上的加法运算是对每个位的按位加运算(按位加部214、215、 216) 。 GF (2)上的乘法运算是逻辑积(逻辑积部210、—211 、 212、213)。
然后，对随机化8位逆元计算部101 (图14)中用到的4位逆元计算部116的详细内容进行说明。<4位逆元计算部116>
图21是表示4位逆元计算部116 (图14)的结构的框图。另外，图30的4位逆元计算部171c也和这个4位逆元计算部117相同。
4位逆元计算部116具备5次方计算部(图24) 、 2位逆元计算部142(图22) 、 2位乘法部143 (图20) 、 2位乘法部144 (图20)以及按位加部140。
而且，4位逆元计算部116对输入数据X (4位)进行在GF ( (2A2)A2)上的逆元计算，生成作为计算结果的输出数据Y (4位)。此时，Y=XA ( — l)in GF ( (2A2) A2)
这里的输入数据X与在随机化8位逆元计算部101的处理说明(图14)中向4位逆元计算部116输入的输入数据C相对应，输出数据Y与在随机化8位逆元计算部101的处理说明(图14)中4位逆元计算部116的输出数据G相对应。4位逆元计算部116进行下面的处理。(1) 首先，4位逆元计算部116将输入数据X从高位开始按每2位进行分割，分割成XO、 XI。而且，4位逆元计算部116将分割后的X0输入到按位加部140、 5次方计算部141、 2位乘法部143。此外，4位逆元计算部116将分割的其他X1输入到按位加部140、 5次方乘法部141。
(2) 5次方计算部141对输入的XO、 XI进行GF ( (2A2) A2)上的5次方计算，求得其结果A (2位)。这里，对数据X (4位)在GF ( (2A2)A2)上进行了 5次方运算的结果成为A，所述数据X (4位)是把XO、 XI按该顺序结合而成的。艮P:
A=XA5 in GF ( (2、)八2)
此外，通过AA3=XA15=1 in GF ( (2、) 、) ， A的位数是3， A也是GF (2A2)上的元素。因此，A变成2位数据。关于5次方计算部141的详细内容，将在后面加以说明。
(3) 然后，图21的4位逆元计算部116具有的2位逆元计算部142对5次方计算部141在上述(2)中所求得的上述A (2位)进行GF (2、)上的逆元计算，生成数据B (2位)并输出。此时，
B=AA ( — l) in GF (2A2)
关于2位逆元计算部142的详细内容，将在后面加以说明(图22)。
(4) 然后，基于以上的计算结果，图21的4位逆元计算部116具有的2位乘法部143、2位乘法部144根据由2位逆元计算部142在上述(3)生成的上述B (2位)及在上述(1)分割得到的XO、 XI，分别通过下面的计算求得YO (2位)、Yl (2位)。
YO=XOXB in GF (2、)
Yl= (X0+X1) XB in GF (2、)
而且，4位逆元计算部116将4位数据Y作为4位逆元计算部116的输出来输出，该4位数据Y是把上述求得的YO、 Yl从高位开始按该顺序连结而成的。
这里，GF (2A2)上的加法运算是对每个位的按位加运算(按位加运算部140) 。 GF (2A2)上的乘法运算(2位乘法部143、 144)的详细内容和前面的说明相同(图20的2位乘法部21)。
接着，利用这样的图21的4位逆元计算部116 (图21)对2位逆元计算部142的详细内容进行说明。<2位逆元计算部142>
图22是表示2位逆元计算部142的结构的框图。2位逆元计算部142具有按位加部142a。
而且，2位逆元计算部142对输入数据X (2位)进行GF (2A2)上的逆元计算，将计算结果作为Y (2位)来输出。此时，Y=XA ( — 1) in GF (2A2)
2位逆元计算部142将X的高位1位、低位1位分别分割为X0、 XI，通过下面的计算式，求得Y0、 Yl。Y0=X0Y1=X1+X0
然后，将Y0、 Y1依照该顺序结合而成的2位数据Y作为输出。然后，对在随机化8位逆元计算部101 (图14)的内部使用的随机化4位逆元计算部114的详细内容进行说明。<随机化4位逆元计算部114>
图23是表示随机化4位逆元计算部114 (图14)的结构的框图。随机化4位逆元计算部114 (图14、图23)具备5次方计算部150 (图24) 、 5次方计算部152 (图24) 、 2位校正项计算部151 (图25) 、 4次方计算部155 (图26) 、 4次方计算部157 (图26) 、 2位输出计算部158(图27) 、 2位输出计算部159 (图27)、随机化2位逆元计算部154 (图28) 、 2位逆元计算部156以及按位加部153。
而且，随机化4位逆元计算部114是如下的处理利用随机数R (4位)对输入数据X (4位)进行随机化4位逆元计算处理，生成输出数据Y (4位)。这里的输入数据X相当于随机化8位逆元计算部101的说明(图14)中的向随机化4位逆元计算部114输入的输入数据D，随机数R相当于C。此外，输出数据Y相当于E。随机化4位逆元计算部114在GF ( (2、)、)上进行与随机化8位逆元计算部101同样的计算处理。但是，在随机化8位逆元计算部101中，虽然将17次方计算部112的输出数据C还输入到随机化4位逆元计算部114，但是随机化4位逆元计算部114不将其输出C输入到随机化2位逆元计算部154。此外，输入到各个处理部的数据的数据大小、乘方运算时的指数等不同。除去上述的内容，由于其处理过程和随机化8位逆元计算部101相同，这里就不做详细说明。
36另外，随机化4位逆元计算部114的处理是如下的处理对用屏蔽值
R进行了屏蔽的输入数据X=M ( + ) R进行合成域GF ( (2A2) A2)上的逆元计算，生成用屏蔽值R^ (_1)屏蔽了的处理结果Y=XA ( — l) ( + )RA ( — 1)。此时，XA ( — l)是X在GF ( (2A2) A2)中的逆元，屏蔽值RA ( — 1)是R在GF ( (2A2) A2)中的逆元。<5次方计算部141、 150、 152>
图24是表示5次方计算部141X (5次方计算部141 (图21) 、 5次方计算部150 (图23) 、 5次方计算部152 (图23))的结构的框图。
5次方计算部141X具备2位乘法部150b、 2位乘法部150c、 2位乘法部150d、按位加部150a、按位加部150e。这里，2位乘法部150b、 2位乘法部150c、及2位乘法部150d的结构分别和图20中示出的2位乘法部21相同。
而且，5次方计算部141X (5次方计算部141、 150、 152)对输入数据XO (2位)、XI (2位)进行GF ( (2A2) A2)上的5次方计算处理，输出输出数据Y (2位)。这里的输入数据X0、X1相当于4位逆元计算部116的说明(图21)中的XO、 XI，相当于随机化4位逆元计算部114的说明(图23)中的XO、 X1及R0、 Rl。此外，输出数据Y相当于4位逆元计算部116的说明(图21)中的A，相当于随机化4位逆元计算部114的说明(图23)中的A及C。
此外，在将输入数据XO、 X1依照该顺序结合的4位数据作为X时，输出数据Y如下所示。
Y=XA5 in GF ( (2、) "2)
这里，由于丫、= XA15=1 in GF ( (2A2) A2) ， Y的位数是3， Y是GF (2A2)上的元素。因此，Y成为2位的数据。
另外，由于5次方计算部141X (5次方计算部141 (图21) 、 5次方计算部150 (图23) 、 5次方计算部152 (图23))的处理流程和己经说明的17次方计算部IIOX(图15、 17次方计算部110、 17次方计算部112)基本相同，因此省略其详细说明。此外，按位加部150a、 150e、 110e(图24)是对每个位的按位加运算，2位乘法部150b、 2位乘法部150c、 2位乘法部150d (图24)的处理和已经说明的2位乘法部21 (图20)相同。
<2位校正项计算部151>图25是表示2位校正项计算部151 (图23)的结构的框图。
2位校正项计算部151具备2位乘法部151a(图20)、2位乘法部151b(图20)和按位加部151c。
而且，2位校正项计算部151对输入数据XO (2位)、XI (2位)、RO (2位)、Rl (2位)进行在GF ( (2A2) 1)上的校正项计算处理，输出输出数据B (2位)。.这里的输入数据XO、 XI、 RO、 Rl相当于随机化4位逆元计算部114的说明(图23)中的XO、 XI、 RO、 Rl。
这里，由于2位校正项计算部151的处理流程和已经说明的4位校正项计算部111 (图16)基本相同，因此省略详细说明。此外，按位加部151c是对每个位的按位加运算，2位乘法部151a、 151b的处理和己经说明的2位乘法部21 (图21)相同。
<4次方计算部155、 157>
图26是表示4次方计算部155X (4次方计算部155、 4次方计算部157:图23)的结构的框图。
4次方计算部155X具备按位加部155a。
而且，4次方计算部155X对输入数据X(4位)进行合成域GF( (2A2)A2)上的4次方运算，将其计算结果作为Y (4位)输出。此时，对输入数据X进行合成域GF ( (2A2) A2)上的4次方计算的结果成为Y。艮P，
Y=XA4 in GF ( (2、) A2)
此外，这里的输入数据X相当于随机化4位逆元计算部114的处理说明(图23)中的数据X或R中的某一个。输出数据Y相当于随机化4位逆元计算部114的处理说明(图23)中的数据F或H中的某一个。
而且，4次方计算部155X将输入数据X从高位开始按每2位进行分割，分割成XO、 Xl之后，并在GF (2、)上进行下面的计算，求得YO、Yl。
YO=XO
Y1=X0+X1 in GF (2"2)
这里的GF (2A2)上的加法运算是对每个位的按位加运算(按位加部155a)。而且，4次方计算部155X将求得的YO、 Yl按该顺序结合来作成8位数据Y。该Y就是4次方计算部155、 157的输出数据。
<2位输出计算部158、 159>图27是表示2位输出计算部158X (2位输出计算部158、 2位输出计算部159:图23)的结构的框图。
2位输出计算部158X具备2位乘法部158a(图20) 、 2位乘法部158b(图20) 、 2位乘法部158d (图20)、按位加部158c及按位加部158e。
而且，2位输出计算部158X利用上述的各部分对输入数据E(2位)、G (2位)、F (2位)、H (2位)进行2位输出计算处理，输出输出数据Y。这里的输入数据E、 G、 F、 H，分别与在随机化4位逆元计算部114的处理说明(图23)中向2位输出计算部158输入的输入数据E、 G、 F0、H0对应，此外，分别与向2位输出计算部159输入的输入数据E、 G、 Fl、Hl对应。此外，输出数据Y与在随机化4位逆元计算部114的处理说明(图23)中的2位输出计算部158的输出数据Y0对应，此外，与2位输出计算部159的输出数据Y1对应。2位输出计算部158X在GF (2、)上进行下面的计算，求得Y，并输出Y。
Y=EXF+GXF+EXH in GF (2、)
这里，GF (2、)上的加法运算是对每个位的按位加运算(按位加部158c、 158e) 。 GF (2、)上的乘法运算(2位乘法部158a、 2位乘法部158b、2位乘法部158d)和己经说明的2位乘法部21 (图23)相同。
<随机化2位逆元计算部154>
图28是表示随机化2位逆元计算部154的结构的框图。随机化2位逆元计算部154具备按位加部154c。
而且，随机化2位逆元计算部154是进行如下的处理利用上述按位加部154c对输入数据X (2位)进行随机化2位逆元计算处理，生成输出数据Y(2位)。这里的输入数据X相当于随机化4位逆元计算部114的说明(图23)中向随机化2位逆元计算部154 (图23、图28)输入的输入数据D。此外，输出数据Y相当于E。随机化2位逆元计算部154将X的高位1位作为XO，低位1位作为XI，通过下面的计算式，计算YO、Yl。<formula>formula see original document page 39</formula>
这里，GF (2A2)上的加法运算是按位加运算(按位加运算部154c)。而且，输出把YO、 Yl从高位开始依次按该顺序结合的数据Y (2位)。另外，随机化2位逆元计算部154的处理是如下的处理对用屏蔽值
R进行了屏蔽的输入数据X=M ( + ) R进行合成域GF (2A2)上的逆元计算，生成用屏蔽值R ( — l)屏蔽了的处理结果Y=XA ( —1) (+)RA(_1)。此时，XA (—l)是GF (2A2)上的X的逆元，屏蔽但R: ( — 1)是R在GF (2A2)上的逆元。
接着，对在加密部la的内部使用的随机数更新部17 (图9)的详细内容进行说明。如前所述，随机数更新部17 (图9)对随机数暂时存储部16 (图9、图38)中存储的随机数进行更新。
<随机数更新部17>
图29是表示随机数更新部17的结构的框图。
随机数更新部17具备合成域变换部170、 8位逆元计算部171及扩张域变换兼矩阵变换部172。
而且，随机数更新部17对输入随机数X (8位)进行随机数更新处理，将更新随机数Y (8位)作为输出数据输出。这里的输入数据X与在加密部la的说明(图9)中随机数更新部17的输入随机数Rn (8位)相对应，输出数据Y与在加密部la的说明中随机数更新部17的输出随机数Rn+l(8位)相对应。随机数更新部17进行下面的处理。
(1) 首先，合成域变换部170将输入数据X从高位开始按每1位进行分割，分割出X7、 X6、…、X0，进行前述的数学式1的矩阵计算，求得A7、 A6、…、A0。并且，合成域变换部170将A7、 A6、…、A0从高位开始按该顺序连结的8位数据作为A。
(2) 而且，接着，8位逆元计算部171对在上述(1)中生成的上述A进行在GF ( ( (2、) A2)、)上的逆元计算处理，求得B (8位)。此时，
B=AA ( — 1) inGF ( ( (2八2) '2) '2)
关于GF ( ( (2A2) A2) A2)上的逆元计算处理的详细内容，将在后面加以说明。
(3) 而且，扩张域变换兼矩阵变换部172将在上述(2)中计算出的B从高位开始按每1位进行分割，分割成B7、 B6、…、B0，进行上述数学式2中的矩阵计算，求得Y7、 Y6、…、Y0。
而且，扩张域变换兼矩阵变换部172将通过上述处理求得的Y7、
40Y6、…、Y0按照该顺序连结成的8位数据作为Y，作为随机数更新部17的输出数据进行输出。
接着，对随机数更新部17中用到的8位逆元计算部171的详细内容进行说明。
<8位逆元计算部171〉
图30是表示8位逆元计算部171 (图29)的结构的框图。
8位逆元计算部171(图30、图29)具备17次方计算部171b(图15)、4位逆元计算部171c (图21) 、 4位乘法部171d (图19) 、 4位乘法部171e (图19)及按位加部171a。
然后，8位逆元计算部171对输入数据X (8位)进行GF ( ( (2A2)A2)、)上的逆元计算，生成计算结果即输出数据Y (8位)。此时，
Y=XA ( — 1) inGF ( ( (2A2) A2) A2)
这里的输入数据X与在随机数更新部17的处理说明(图29)中向8位逆元计算部171输入的输入A相对应，输出数据Y与8位逆元计算部171的输出数据B相对应。8位逆元计算部171进行下面的处理。
(1) 8位逆元计算部171将输入数据X从高位开始按每4位进行分割，分割为XO、 XI。然后，8位逆元计算部171将分割的X0输入按位加部171a、 17次方计算部171b、 4位乘法部171d。此外，8位逆元计算部171将分割的XI输入到按位加部171a、 17次方计算部171b。
(2) 然后，17次方计算部171b对输入到该17次方计算部171b的XO、 X1进行GF ( ( (2、) A2) A2)上的17次方计算，求得其结果A (4位)。这里，对将XO、 XI依照该顺序结合而成的数据X (8位)进行了GF ( ( (2A2) A2) A2)上的17次方运算的结果，成为A。艮P
A=XA17 in GF ( ( (2八2) A2) A2)
此外，根据八、5= XA255=1 in GF ( ( (2、) A2) A2) ， A的位数是15，因此A是GF ( (2A2) 1)上的元素。因此，A成为4位数据。有关17次方计算部171b的详细内容，和已经说明的17次方计算部110X(17次方计算部110 (图16) 、 17次方计算部112 (图16):图15)相同。
(3) 接着，4位逆元计算部171c (图30)对上述(2)中生成的上述A (4位)进行GF ( (2A2) A2)上的逆元计算，生成数据B (4位)，并输出。此时，B=AA ( — 1) inGF ( (2A2) A2)
4位逆元计算部171c的详细内容和已经说明的4位逆元计算部116(图21)相同。
(4)然后，8位逆元计算部171根据在上述(3)中生成的上述B (4位)及在上述(1)中分割的X0、 XI，经过下面的计算，分别通过4位乘法部171d、 4位乘法部171e，求得下面的Y0 (4位)、Yl (4位)。
Y0=X0XB in GF ( (2、) A2)
Yl= (X0+X1) XB in GF ( (2"2)、)
然后，8位逆元计算部171将上述YO、 Yl从高位开始按该顺序连结而成的S位数据Y作为该8位逆元计算部171的输出来输出。
GF ( (2A2) A2)上的加法运算是对每个位的按位加运算(按位加部171a) 。 GF ( (2A2) 1)上的乘法运算(4位乘法部171d、 171e)的详细内容跟前面己经说明的相同(图19的4位乘法部20)。
以上，说明了加密装置1的全部详细动作。
接着，对随机化S—boxl20a 120p(图13)保持与AES加密的S—box之间的兼容性、以及处理过程中的数据被屏蔽的情况加以说明。<随机化8位逆元计算部101的原理〉
随机化8位逆元计算部101 (图14)将合成域GF ( ( (2、) A2)、)上的元素X二M+R (图38中ID8t:Tl (V8t) +T1 (Rt) 、 M=T1 (V8t)、R=T1 (Rt))作为输入，输出Y=MA( —1) + R ( — l)(图38中的OD8t=Tl(V8t) A ( — l) +T1 (Rt) A ( — 1))。这里，MA ( — 1) 、 RA ( — 1)分别表示M、 R的在GF ( ( (2A2) A2)、)中的逆元。下面，对此进行说明。
17次方计算部110 (图14、图15)的输出值A利用扩张域的性质等，变成如下形式。A=XA17
=(M+R) 、7
=(M+R) X (M+R) 、6
=(M+R) X (MA16+RA16)
=Mfl 7+Ra1 7+MAl 6 X R+M X R、 6这里，由于GF ( ( (2A2) A2) A2)是将GF ( (2、) A2)用不可约多
42项式xA2+x+1100 (二进制数)进行2次展开的，所以如果把a作为xA2+x+1100 (二进制数)的根，则M、 R就能够表示为如下。
M: M0X a +M1
R: R0X a +R1
此时，如果使用扩张域的性质等，则能够如下计算出MA16XR+MXR、6。
(MOX a+M1) A16X (RO X a+R1 ) + (MO X a+M1 ) X (ROXa+R1) 、6
={MOX a + (M0+M1) }X (ROX a +R1 ) + (MOX a +M1) X {ROXa + (R0+R1) }
=(MO+RO) XR1+ (Ml+Rl) XRO
这与在图14的随机化8位逆元计算部101的处理中的X0XR1+X1XRO相等。因此，能够表示为
A=MA17+RA17+X0XR1+X1 XRO
但是，由于4位校正项计算部111 (图14、图16)计算B:X0XR1+X1XRO，结果，向随机化4位逆元计算部114 (图14、图23)输入的输入数据D是
D=A+B=MA17+RA17
随机化4位逆元计算部114如后面所述进行如下处理对于输入D=MA17+RA17、 C=RA17，输出输出E二M" ( — 17) +RA ( — 17)。此时，4位输出计算部118、 119相当于分别分为高位4位和低位4位来进行以下的计算。
Y=EXF+GXF+HXE={MA ( — 17) +RA ( — 17) }X (M+R) 、6+RA ( — 17) X (M+R)A16+RA16X{MA ( — 17) +RA ( — 17) }
计算上述的数学式，则Y^Nf (_1) +RA ( — l)，可知随机化8位逆元计算部101进行将X二M+R变换为Y=MA ( — l) +RA ( — 的处理。
然后，作为这样地将X^M+R变换为Y=MA ( — l) +RA ( — l)的随机化8位逆元计算部101的一部分的随机化4位逆元计算部114 (图14、图23)，由于在GF ( (2A2) A2)上进行和上述同等的处理，因此和上述一
43样的说明也成立。因此，可知对于输入D= MA17+RA17和C=RA17的输入， 输出E= MA ( — 17) +R ( — 17)。进一步，对于随机化4位逆元计算部 114也是同样的，这一点可通过对X、 R的全部的值的组合实际进行计算 来确定。
通过以上的处理，说明了随机化8位逆元计算部101进行如下的处理 将合成域GF ( ( (2A2) A2) A2)上的元素X二M+R变换为Y=MA ( — l) +RA (—1)。
<随机化S—boxl20a 120p的动作原理>
接着，对随机化S — boxl20a 120p (图13、图12)的动作原理进行说 明。在图13中，若设X二M+R (图38中IC8t=V8t+Rt， M=V8t， R=Rt)， 则合成域变换部100的输出就变为A=T (X) =T (M) +T (R)(图38中 的ID8t=Tl (V8t) +T1 (Rt))。这里，T (X)(图38中的Tl)是将 GF (2A8)上的元素变换成合成域GF ( ( (2A2)、)、)上的元素的结果。 同样地，其他的合成域变换部103将R (图38中的Rt)变换成S=T (R) (图38中的RDt二Tl (Rt))。
然后，如先前的说明，随机化8位逆元计算部101根据A=T (M) +T (R) 、 S=T (R)的输入，生成B:T (M) A ( — 1) +T (R) A ( — 1)(图 38中的OD8戶Tl (V8t) A ( — l) +T1 (Rt) ( — l))。然后，扩张域变 换兼矩阵变换部102 (图13)在将合成域GF ( ( (2A2) A2) A2)上的元素 变换为GF (2A2)上的元素后，将进行了 AES加密的S — box中定义的仿 射变换中的仅矩阵运算部分的结果进行输出。即，C二Mat (MA ( — ) +Mat (RA (_1))被输出(图38中的Mat (V8f ( — 1) ) +Mat (Rf (— 1)))。
这里，Mat (X)是表示对X进行上述矩阵运算即AES加密的S—box 中定义的仿射变换中的矩阵运算的结果。然后，按位加部104 (图13)将 输入的上述C和常数01100011 (二进制数)进行GF (2A8)上的加法运算， 该常数由AES加密的S — box定义的仿射变换来定义的常数加法运算中的 常数。即，按位加部104的输出结果Y成为Y= {Mat (Nf ( — l)) +01100011}+Mat(RA( — 0)(图38中的Mat(V8f( — 1 ) )+01100011+Mat (RtA ( — l))。上式中的"部分即是对于M进行AES加密的S—box变 换的结果，能够表示为Y=S —box[M]+ Mat (R八(一l))(图38中的S—box[V8t]+Mat (RtA ( — l)))。这里的S—box[X]表示对X进行AES 加密的S—box变换的结果。 <加密装置1的动作原理>
接着，加密装置1对保持与AES加密算法之间的兼容性的情况加以说明。
首先，在图9中，明文数据P (128位)通过随机数R0 (8位)被屏 蔽。屏蔽处理部10的处理结果A成为A=P+ (R0， R0，…，R0)。接着， 根据AddRoundKey 11的处理结果变换为B=P+RK0+ (R0， R0，…，R0)。 这里，P+RK0是未屏蔽时的AddRoundKey的处理结果，如果把P+RK0设 为M，贝U B=M+ (R0， R0，…，R0)。接着，对于n=l 9，进行随机化 Round—nl2处理，对于此，参照图10进行说明。
在图10中，若把未屏蔽时的随机化Round—n12的输入值(即原值) 设为M，则输入X表示为X=M+(R0， R0，…，R0)。随机化SubBytes120 如图12所示，是由随机化S—box构成的处理。现在，如果将M从高位开 始按每8位进行分割，分割成M0、 Ml、…、M15，则
X= (M0、 Ml、…、M15) + (R0、 R0、…、R0)
这里，根据先前的随机化S—boxl20a 120p的动作原理说明，随机化 SubBytes120的输出Y表示为Y= (S —box岡，S—box[Ml]，…，S — box[M15]) + (Mat[R(f ( —1) ]， Mat[R(f ( — 1 )]，…，Mat[R(T ( — 1 )])。 即，
Y= SubBytes (M) + (Mat[RCT ( — 1 ) ]， Mat[R0A ( — 1) ]， ...， Mat[R(T (一l)])
艮口，随机化SubBytes120的输出数据是用(Mat[R(f ( — 1) ]， Mat[R(T (—1)]，…，Mat[R(T( —1)])进行了屏蔽的数据。接着，关于ShiftRows121 的输出、MixColumnl22的输出，则可知都通过直接执行AES加密算法标 准中规定的ShiftRows处理、MixColumn处理，能够得到用(Mat[R(T( — 1) ]， Mat[R(T ( — 1)〗，…，Mat[R(f ( — 1)])屏蔽了的ShiftRows处理 结果、MixColumn处理结果。因此，如果随机化Round—n12处理的输入值 己用R进行了屏蔽，则其输出值以用Mat[R(T ( —1)]屏蔽了的状态输出。 因此，作为Rh Mat[R(T ( — l)]，如果执行『1的随机化Round—nl2处 理，则用Rl屏蔽了的状态下的输入数据则输出用R2= Mat[RlA ( — l)]屏蔽了的状态的输出数据。另外，Mat[RCT (—l) ]、 Mat[RlA ( — l)]的 处理是图29的随机数更新部处理。如果反复进行以上的直到随机化 Round—10 13的处理，则作为随机化Round—10 13 (图9、图11)的输出数 据，输出用Rl一Mat[R10八(一1)]对密文C进行了屏蔽的状态的数据， 所述密文C是对明文P进行了 AES加密处理的结果。因此，在中断屏蔽 部14中，通过用R11进行按位加处理来得到密文C (图9)。
此外，从前面的动作原理的说明也可知，加密处理过程的中间数据始 终被用根据随机数R0或R0通过规定的运算算出的值实施了屏蔽。因此， 通过电力分析攻击来对加密装置1进行密钥分析变得困难。
图38是表示加密装置1及加密装置1具有的部分之间的包含关系、 它们的整体、部分之间的输入输出数据的图。参照图38，整理上述说明中 所示的它们的包含关系及输入输出数据。
加密部la(图9、图31)被输入明文U，输出密文C。
这里，图38所示的Vt (t=l~ll)的标记是对明文U实施了直到轮t 为止的处理的中间数据。加密部la通过直到轮(t一l)为止的处理，生成 将该Vt用随机数Rt进行了屏蔽的随机化输出数据OAt=Vt+{Rt, Rt，…， Rt}。
随机数暂时存储部16 (图9)将随机数RO提供给屏蔽处理部10，将 随机数Rl 随机数R10提供给具有随机化8位逆元计算部101的随机化S 一boxl21X，将随机数Rll提供给中断屏蔽处理部14。
随机化Round一tl2X (图9、图10、图11)在各轮处理中，分别被输 AlAt=Vt+{Rt， Rt，…，Rt}(图9中的B或D、图10及图11中的X) 和随机数Rt (图9的Rn、图10的Rn、图11的R10)，将对所输入的IAt 表示的作为原值的中间值Vt进行了第t轮处理后的中间数据V (t+l)， 用随机数R(t+l)进行屏蔽而得到OAt^V(t+l)+(R(t+l) ， R(t+1)，…， R (t+l) }，并输出该得到的OAt。这里，随机化输出数据OAt的去除了 屏蔽值的影响的原值是被实施了第t轮处理的上述中间数据V。
随机化SubBytesl20X (图10、图11、图12)被输入作为向随机化 Round—tl2X输入的输入数据IAt的IB，IAt:Vt+(Rt， Rt，…，Rt }(图10 及图11的X、图12的X)及随机数Rt (图12的R、图10的Rn、图11 的R10)，输出被实施了第t轮SubBytes处理的OBt-S—Box( Vt)+{ R(t十1)，R(t+1)，…，R(t+1)}(图10及图11的A、图12的Y)。
随机化S—Boxl21X (图12、图13)中被输入向随机化SubBytes输 入的输入数据IBt被分割的8位IC8t=IB8t=V8t+Rt (图12所示的X[O]、 X[l]、、或X[15]中任一个、图13的X)及随机数Rt (图13的R、图 12的R)，输出对该8位进行了第t轮S—Box处理的OC8t=S—box (V8t) +R (t+l)(图12的Y[O]、 Y[l]、…、或Y[15]中任一个、图13的Y)。
然后，随机化8位逆元计算部101 (图13、图14)，设基于数学式l 的矩阵计算(参照合成域变换部100及合成域变换部103的说明)由标记 Tl表示，被输入基于输入到随机化S — box的上述IC8t的ID8t=Tl (IC8t) =T1 (V8t) +T1 (Rt)和基于随机数暂时存储部16的随机数Rt的RDt41 (Rt)(图13的S、图14的R)，根据这些输入把M+P运算为MA ( —1) +PA ( — 1)，并输出作为运算结果的OD8t二Tl(V8t)A (一l) +Tl(Rt)A (— 1)(图13的B、图14的Y)。
这里，随机化S — Boxl21X (图13、图12)基于该随机化8位逆元计 算部101的输出OD8t=Tl(V8t)A ( — l) +Tl(Rt)A ( — 1)(图13的B、图 14的Y)，利用扩张域变换兼矩阵变换部102和按位加部104进行计算， 求出OC8t:(Mat (V8tA ( — l) ) + Mat (Rf ( — l) ) }+01100011={ Mat (V8f ( — l) ) + 01100011}+ Mat (RtA ( — l) ) =S—box (V8t) + Mat (Rf ( — l) ) =S —box (V8t) +R (t+1)，并输出所求得的该OC8t (图 12的Y
、 Y[l]、…、或Y[15]中任一个、图13的Y)。
然后，随机化SubBytes 120X (图12、图10、图11)将由各个随机化 S—boxl20X (随机化S—boxl20a 随机化S—boxl20p)输出的该OC8t进 行连结，输出输出数据OBt=S—box(Vt)+{R(t+l) ， R(t+1)，…R(t+1) } (图10及图11的A，图12的Y)。
由此，随机化Round一tl2X根据输出的OBt，例如进行ShiftRows处理 等，计算OAt:V (t+1) +{R (t+l) ， R (t+l)，，…R (t+l) }，将计算 出的OAt作为随机化RoimdJ12X的下一轮及第t+l轮的随机化输入数据 IAt，输入到随机化Round—tl2X。
由此，在中断屏蔽处理部14中，经由t二10时的随机化Round一tl2X， 被输入OAt=OA10=Vll+{Rll， Rll，…，Rll}，此外，从随机数暂时存 储部16被输入随机数Rll (图9的E，图11的Y)，通过对被输入的该
47OA10=V11+{R11， Rll，…，Rll)用随机数Rll进行按位加运算，输出密 文OVll。
通过以上处理，利用密钥(RK0等)从明文U (图38)生成密文C (图 38)的加密装置1，其特征在于，具备随机数生成部15，生成随机数R0; 随机化输入数据生成部(屏蔽处理部10 (图9、图38、 AddRoundKeyll
(图9)、随机化Round—n12中的合成域变换部100 (图13)、扩张域变 换兼矩阵变换部102 (图13)、按位加部104 (图13))，接收上述明文 U，将根据上述随机数RO决定的预定的输入屏蔽值T1 (Rt)和对上述明 文U用上述密钥(RK0等)进行了预定的处理的输入数据T1 (V8t)相加， 生成随机化输入数据T1 (V8t) +T1 (Rt);随机化8位逆元计算部101， 接收由上述随机化输入数据生成部生成的上述随机化输入数据ID8t和上 述输入屏蔽值T1 (Rt) =RDt，将所接收的上述输入屏蔽值的在预定的第1 有限域中的逆元即输出屏蔽值T1 (Rt) A ( — 和上述输入数据T1 (V8t) 的在该第1有限域中的逆元T1 (V8t) A ( — l)相加，生成随机化输出数 据T1 (V8t) A ( — 1) +T1 (Rt) A ( — 1);输出部(随机化Round—10 13 中的扩张域变换兼矩阵变换部102 (图13)及按位加部104 (图13)、 ShiftRows131 (图11) 、 AddRoundKey 132 (图11)、中断屏蔽处理部14
(图9、图38))，接收上述随机化8位逆元计算部101生成的随机化输 出数据OD810 (t=10)，根据所接收的该随机化输出数据生成上述密文C。 而且，该加密装置l中，上述随机化8位逆元计算部101包括17次 方计算部110、 112 (图14)，对上述随机化输入数据ID8t (图14的X)、 上述输入屏蔽值(Tl (Rt)、图14的R)进行预定的第1指数(17次方) 的乘方运算，分别通过各乘方运算生成第1乘方随机化输入数据(图14 中的A)和第1乘方输入屏蔽值(图14的C) ; 4位校正项计算部111 (图 14、图16)，根据上述随机化输入数据(图14的X)和上述输入屏蔽值
(图14的R)，生成预定的校正数据(图14的B);按位加部U3 (图 14)，将生成的上述校正数据(图14的B)与计算出的上述第1乘方随机 化输入数据(图14的A)相加，生成副随机化输入数据(图14的D); 随机化4位逆元计算部114 (图14、图23)，接收上述副随机化输入数据
(图14的D)和上述第1乘方输入屏蔽值(图14的C)，将该第一乘方 输入屏蔽值(图14的C)的在第2有限域中的逆元即屏蔽值(CT ( —1))
48与上述副随机化输入数据(图14的D)的在上述第2有限域中的逆元即 输出数据(DA ( — 1))相加，生成随机化副输出数据(图14的E二DA (— 1) +CA ( — 1));其他部分，根据上述随机化副输出数据(图14的E)、 上述随机化输入数据(图14的X)、上述输入屏蔽值(图14的R)、上 述第1乘方输入屏蔽值(图14的C)来生成上述随机化输出数据(图14 的Y)。
而且，这里，"其他部分"包括16次方计算部115、 117 (图14、 图17),对上述随机化输入数据(图14的X)和上述输入屏蔽值(图14 的R)进行预定的第2指数(16次方)的乘方计算，通过各个乘方计算， 分别生成第2乘方随机化输入数据(图14的F)和第2乘方输入屏蔽值(图 14的H) ; 4位逆元计算部116 (图15、图21)，对上述第l乘方输入屏 蔽值(图14的C)进行在上述第2有限域上的逆元计算，生成上述第1 乘方输入屏蔽值(图14的C)的在上述第2有限域中的逆元即逆元乘方输 入屏蔽值(图14的G);其他部分(4位输出计算部118及4位输出计算 部119)，根据上述随机化副输出数据(图14的E)、上述第2乘方随机 化输入数据(图14的F)、上述第2乘方输入屏蔽值(图14的H)、上 述逆元乘方输入屏蔽值(图14的G)，生成上述随机化输出数据(图14 的Y)。
此外，该加密装置1对上述明文U进行AES (Advanced Encryption Standard)加密的加密处理，生成AES加密的密文C，上述输入数据的逆 元T1 (V8t) A ( — l)是对上述输入数据T1 (V8t)进行了与AES加密的 Sbox表等价的逆元计算及仿射中的逆元计算而得的计算结果。
因此，根据该加密装置l，通过级数少的简单结构能够进行AES加密 方式的加密的逆元计算，进而能够进行AES加密的加密处理。
此外，该加密装置1进一步具备屏蔽值生成部(随机数更新部17及 合成域变换部103 (图9、图13、图29))，用于生成上述随机化8位逆 元计算部101使用的上述输入屏蔽值RDt。
由此，能够在加密装置l内生成输入屏蔽值，使系统的结构变简单。
而且，该加密装置1的上述屏蔽输入数据生成部具备第1部分(屏 蔽处理部10 (图38、图9) 、 AddRoundKeyll (图9)、合成域变换部100 (图13))，根据上述明文U，生成第1随机化输入数据ID8t=ID81=Tl(V81) +T1 (Rl);第2部分(扩张域变换兼矩阵变换部102 (图13)、 按位加部104 (图13)、随机化Round—n12中的S础Rowsl21 (图10)、 MixColumns122 (图10) 、 AddRoundKey123 (图10)、合成域变换部100)， 接收第(t一l)的随机化输出数据OD8 (t—l)，加上根据第(t一l)输 出屏蔽值RD (t—l) A ( — l) -T1 (Rt)决定的预定的第t输入屏蔽值Tl
(Rt) =T1 (Mat (RtA ( — l )))，生成第t随机化输入数据ID8t=Tl (V8t) +T1 (Rt) (2《t《J)。上述屏蔽值生成部根据所生成的上述随机数RO， 生成上述第1输入屏蔽值RD1 第J输入屏蔽值RDJ (J=10);随机化8 位逆元计算部101根据上述第1部分生成的上述第1随机化输入数据ID81 和所生成的上述第1输入屏蔽值RD1，生成上述第1随机化输出数据 OD81，并且，根据由上述第2部分生成的上述第t随机化输入数据ID8t(2 《t《J)和所生成的上述第t输入屏蔽值RDt，生成上述第t随机化输出数 据OD8t (2《t《J)。
另外，这里，该加密装置1中，上述第1部分(屏蔽处理部10 (图 38、图9) 、 AddRoundKeyll (图9)、合成域变换部100 (图13))从 上述屏蔽值生成部(随机数更新部17)，取得用于确定第1输入屏蔽值 RD1=T1 (Rl)的确定数据R0，根据所取得的确定数据RO和上述明文U， 生成已加上了上述第1输入屏蔽值RD^T1 (Rl)的上述第l随机化输入 数据ID8，ID8^T1 (V81) +T1 (Rl)。上述屏蔽值生成部(随机数更新 部17)生成用于确定上述第J的输出屏蔽值T1 (R10) A ( — l)的确定数 据Rll，上述输出部接收所生成的该确定数据Rll和第J随机化输出数据 OD8t，并根据这些数据生成上述密文C，该第J随机化输出数据OD8t是 加上了该确定数据Rll所确定的上述第J输出屏蔽值T1 (R10) A ( — l) 而得到的数据。
另外，上述屏蔽值生成部具备保持部(随机数暂时存储部16(图9))， 该保持部保持值，若生成上述随机数R0，则保持所生成的随机数R0;保 持控制部(随机数更新部17 (图9))，根据保持的随机数R (t—l)生 成随机数Rt，将生成的随机数Rt保持在上述保持部，上述随机数Rt用于 通过预定的计算算出上述第t输入屏蔽值；计算部(合成域变换部103 (图 13))，根据所保持的上述随机数Rt，分别通过上述计算算出上述第t输 入屏蔽值(t=l、 2、…、J)。由此，通过保持随机数Rt，能够根据所保持的随机数Rt，通过简单处 理算出第(t+l)的输入屏蔽值，能够通过简单处理算出各个输入屏蔽值。 另外，在请求范围内记载的"随机数生成部"例如可以解释为对应于
随机数生成部15、随机数暂时存储部16及随机数更新部17的整体。在这
样解释的情况下，请求范围内记载的"屏蔽值生成部"也可以理解为不对
应于上述随机数更新部17及合成域变换部103，只对应于合成域变换部 103。
另外，这样的加密装置1也可以具备分别设置了用于实现上述各部分 的电路的集成电路，该集成电路也可以使用这些各部分来发挥上述作用， 来执行上述方法。
<解密装置3>
对应于解密装置1的解密装置3的结构如图31 图37所示。这些处理 是加密装置1的处理的逆变换处理，由于基本的处理流程和加密装置1中 说明的内容相同，省略其详细说明。另外，在图36中的随机化InvS — Box331a 331p的合成域变换兼矩阵变换部300中，下面的矩阵运算式使用 数学式3
<formula>formula see original document page 51</formula>
同样的在图36中所示的扩张域变换部302中，下面的矩阵运算式使 用数学式4广 、 Y7广 i000，11、 0广 、 已7
Y6011〇1100B6
Y5000〇1110已5
Y411010010已4
Y3—01001010已3
Y2〇0101010已2
Y10010000B1
1001011:
由此，使用密钥根据密文生成明文的解密装置3，其特征在于，具备:
随机数生成部35 (图32)，生成随机数；输入部(屏蔽处理部30(图32)、 AddRoundKey31 (图32) 、 InvShiftRows320 (图33)、图36所示的按位 加部、随机化IiwRound_n32 (图32、图33)所具备的扩张域变换部302 (图36) 、 AddRoundKey322 (图33) 、 InvMixColumns323 (图33)、随 机化InvRound—0 33 (图34)所具备的InvShiftRows330 (图34))，接收 上述密文，将根据上述随机数决定的预定的输入屏蔽值和对上述密文根据 上述密钥进行了预定的处理的输入数据相加，生成随机化输入数据；8位 随机化合成域逆元计算部301 (图36)，接收由上述随机化输入数据生成 部生成的上述随机化数据和上述输入屏蔽值，将接收的上述输入屏蔽值的 在预定的第1有限域中的逆元即输出屏蔽值和上述输入数据的在该第1扩 张域中的逆元相加，生成随机化输出数据；输出部(具有随机化InvRound—0 33 (图32、图34)的扩张域变换部302 (图36) 、 AddRoundKey332 (图 34)、中断屏蔽处理部34 (图32))，接收由上述8位随机化合成域逆 元计算部301生成的上述随机化输出数据，根据所接收的该随机化输出数 据生成上述译文。
<最大逻辑级数的预估>
在以上说明的实施方式中，预估随机化8位逆元计算部101 (图14、 图13)的最大逻辑级数。预估在电路中实现随机化8位逆元计算部101时 的关键路径的最大逻辑级数如下
随机化8位逆元计算部101的关键路径在图14中如下所示
17次方计算部110=>按位加部113=>随机化4位逆元计算部114=>4
52位输出计算部118
而且，在该路径途中的4位输出计算部118的关键路径如下(图18):
4位乘法部118a-〉按位加部1180=>按位加部118e 此外，图14的路径的途中的随机化4位逆元计算部114的关键路径 如下(图23):
5次方计算部150=〉按位加部153=>随机化2位逆元计算部154=>2位 输出计算部158
而且，该图23中所示的2位输出计算部158的关键路径如下所示(图 27):
2位乘法部158a^〉按位加部1580=>按位加部158e 然后，前述的图23的路径的途中的随机化2位逆元计算部154的关 键路径如下所示(图28): 按位加部154c
通过上述过程，随机化8位逆元计算部101 (图14)的最大逻辑级数 成为连续处理下面的处理时的逻辑级数。 17次方计算X1次 5次方计算X1次 4位乘法X1次 2位乘法X1次 按位加运算X7次
另外，这里，上述"按位加运算X7次"中的7次是基于下面的计算 7=1+2+1+2+1的。即，与现有技术2的随机化8位逆元计算部81 (图l) 相比，能够削减ll次按位加运算，能实现最大逻辑级数的削减。■ (变形例)
另外，在本实施方式中，将作为电力分析攻击对策的对象的加密作为 AES加密，但不仅限于AES加密，只要是在加密处理中使用逆元运算， 或者，在加密处理中所使用的表变换处理是可基于逆元运算构成的加密方 式就可以使用。作为那样的加密方式，其他的有ISO/IEC 18033 — 3:2005,
"Information technology Security techniques-Encryption algorithms —
一Part3: Block ciphers"有(非专利文献3)中记载的Camellia加密。
此外，在上述实施方式中，即使作为软件来实现的情况下，由于没有
53必要将变换表作为排列来进行保持，所以与以往技术同样能够节约代码规 模，并且，相比以往技术，能够起到削减加密处理时间的效果。
此外，在上述实施方式中，说明了将全部的处理安装在运算电路中的 情况，也可以将其中的处理的一部分安装为变换表。例如，在随机化4位
逆元计算部114的情况下，作为由4位X16个的要素构成的排列Inv4[16;] 来安装，对于4位输入X，可以将4位输出作为Inv4[X]来输出。
另外，虽然基于上述实施方式说明了本发明，但本发明当然不限定于 上述实施方式。下面的情况也包含在本发明中。
(1) 上述各装置具体来说是由下述部件构成的计算机系统微处理 器、ROM、 RAM、硬盘单元、显示器单元、键盘、鼠标等。在上述RAM 或硬盘单元中，存储有计算机程序。通过上述微处理器按照上述计算机程 序来动作，各装置实现其功能。这里的计算机程序为了实现规定的功能， 组合多个表示对计算机的指令的命令代码来构成该计算机程序。
(2) 构成上述各装置的构成要素的一部分或者全部，也可以由一个 系统LSI (Large Scale Integration:大规模集成电路)构成。系统LSI是将 多个构成部集成到一个芯片上来制造出来的超多功能LSI。具体说来，是 含有微处理器、ROM、 RAM等来构成的计算机系统。在上述RAM中， 存储有计算机程序。通过上述微处理器按照上述计算机程序来动作，系统 LSI实现其功能。
(3) 构成上述各装置的构成要素的一部分或者全部也可以是由在各 装置上可装卸的IC卡或单体模块构成。上述IC卡或者上述模块是由微处 理器、ROM、 RAM等构成的计算机系统。上述IC卡或上述模块也可以包 含上述超多功能LSI。通过微处理器按照计算机程序进行动作，上述IC卡 或上述模块实现其功能。该IC卡或者该模块也可以具有防篡改性。
(4) 本发明也可以是上述所示的方法。此外，也可以是通过计算机 来实现这些方法的计算机程序，也可以是上述计算机程序构成的数字信 号。
此外，本发明也可以将上述计算机程序或者上述数字信号记录在能够 通过计算机读取的记录介质中，例如，软盘、硬盘、CD—ROM、 MO、 DVD、 DVD—ROM、 DVD—RAM、 BD (Blu—rayDisc，即蓝光盘)、半 导体存储器等。此外，也可以是存储在这些记录介质上的上述数字信号。此外，本发明也可以是将上述计算机程序或者上述数字信号经由电气 通信线路、无线或有线通信线路、以英特网为代表的网络、数据广播等进 行传送。
此外，本发明也可以是具备微处理器和存储器的计算机系统，上述存 储器存储上述计算机程序，上述微处理器按照上述计算机程序进行动作。
此外，也可以是通过将上述程序或上述数字信号记录在上述记录介质 中来进行转移，或者通过将上述程序或者上述数字信号经由上述网络等进 行转移，由独立的其他的计算机系统实施。
(5) 另外，上述屏蔽值生成部也可以在随机化8位逆元计算部101 (图14)根据随机化输入数据计算随机化输出数据的同时，并行地，在生
成该随机化8位逆元计算部101在该计算中使用的RDt之后，再生成该随 机化8位逆元计算部IOI所使用的RD (t+l)等。这样，随机化8位逆元 计算部101能够无延迟地利用该RD (t+l)等，使得加密装置1高速动作。
(6) 此外，也可以采用下面的方式。 也可以采用加密处理程序的方式，即，使用计算机基于密钥对明文进
行规定的加密处理来生成密文的加密处理程序，其特征在于，生成随机数， 接收随机化输入数据和输入屏蔽值，进行第1有限域上的逆元计算，并输 出随机化输出数据，.上述随机化输入数据是将输入屏蔽值和输出数据相加 来进行了屏蔽的值，上述随机化输出数据是将输出屏蔽值和输出数据相加 来进行了屏蔽的值，上述输入屏蔽值是根据上述随机数决定的值，上述输 出数据是上述输入数据的在上述第1有限域中的逆元，上述输出屏蔽值是 上述输入屏蔽值的在上述第l有限域中的逆元，使上述计算机进行信息处 理。
此外，也可以采用下面的方式。即，采用使用计算机来用密钥从明文 生成密文的计算机程序的方式，该计算机程序使计算机实现如下功能随 机数生成功能，生成随机数；随机化输入数据生成功能，接收上述明文， 把根据上述随机数决定的预定的输入屏蔽值和对上述明文根据上述密钥 进行了预定的处理的输入数据相加，生成随机化输入数据；第l随机化逆 元数据生成功能，接收由上述随机化输入数据生成功能生成的上述随机化 输入数据和上述输入屏蔽值，将接收到的上述输入屏蔽值的在预定的第1 有限域中的逆元即输出屏蔽值和该输入数据的在上述第1有限域中的逆元相加，生成随机化输出数据；输出数据处理功能，接收通过上述第1随机 化逆元数据生成功能生成的上述随机化输出数据，根据接收到的该随机化 输出数据生成上述密文。
另外，可以分别通过并列执行相互不同的处理的多处理等来执行这些 加密处理程序、计算机程，在该种情况下，该计算机程序在根据随机化输 入数据生成随机化输出数据的同时，使上述计算机并行地生成上述输入屏
(7)也可以分别组合上述实施方式及上述变形例。
工业实用性
本发明涉及的加密装置，具有面阻止电力分析攻击、比现有技术更能 削减加密处理的处理量的特征，所以在追求实现高速处理或低成本的加密 装置的实现中有用。
5权利要求
1、一种加密装置，使用密钥，根据明文生成密文，其特征在于，具备随机数生成部，生成随机数；随机化输入数据生成部，接收上述明文，将根据上述随机数决定的预定的输入屏蔽值和对上述明文利用上述密钥进行了预定的处理的输入数据相加，生成随机化输入数据；第1随机化逆元数据生成部，接收由上述随机化输入数据生成部生成的上述随机化输入数据和上述输入屏蔽值，将接收的上述输入屏蔽值的在预定的第1有限域中的逆元即输出屏蔽值和该输入数据的在上述第1有限域中的逆元相加，生成随机化输出数据；以及输出数据处理部，接收由上述第1随机化逆元数据生成部生成的上述随机化输出数据，根据接收到的该随机化输出数据生成上述密文。
2、 如权利要求1所述的加密装置，其特征在于，上述第1随机化逆 元数据生成部具备第1乘方计算部，对上述随机化输入数据和上述输入屏蔽值进行预定 的第1指数的乘方计算，分别通过各乘方计算生成第1乘方随机化输入数 据和第1乘方输入屏蔽值；校正数据生成部，根据上述随机化输入数据和上述输入屏蔽值，生成 预定的校正数据；加法部，将所生成的上述校正数据和计算出的上述第1乘方随机化输 入数据相加，生成副随机化输入数据；第2随机化逆元数据生成部，接收上述副随机化输入数据和上述第1 乘方输入屏蔽值，将该第1乘方输入屏蔽值的在预定的第2有限域中的逆 元即屏蔽值和上述副随机化输入数据的在该第2有限域中的逆元相加，生 成随机化副输出数据；以及随机化输出数据生成部，根据上述随机化副输出数据、上述随机化输 入数据、上述输入屏蔽值及上述第1乘方输入屏蔽值，生成上述随机化输 出数据。
3、 如权利要求2所述的加密装置，其特征在于，上述随机化输出数据生成部具备第2乘方计算部，对上述随机化输入数据和上述输入屏蔽值进行预定 的第2指数的乘方计算，通过各乘方计算，分别生成第2乘方随机化输入 数据和第2乘方输入屏蔽值；逆元运算部，对上述第1乘方输入屏蔽值进行上述第2有限域上的逆 元计算，生成该第1乘方输入屏蔽值的在上述第2有限域中的逆元即逆元 乘方输入屏蔽值；以及随机化输出数据生成部，根据上述随机化副输出数据、上述第2乘方 随机化输入数据、上述第2乘方输入屏蔽值及上述逆元乘方输入屏蔽值， 生成上述随机化输出数据。
4、 如权利要求l所述的加密装置，其特征在于，该加密装置对上述明文进行AES加密的加密处理，生成AES加密的 密文，上述输入数据的逆元是对上述输入数据进行了与AES加密的Sbox表 等价的逆元计算及仿射中的逆元计算而得的计算结果。
5、 如权利要求l所述的加密装置，其特征在于， 上述随机化输入数据生成部具备第1部分，根据上述明文，生成已加上了第1输入屏蔽值的第1随机 化输入数据；第2部分，接收由上述第1随机化逆元数据生成部生成的第(t一l) 随机化输出数据，加上根据上述第(t一l)输出屏蔽值决定的第t输入屏 蔽值，生成第t随机化输入数据，其中，2《t《J， J是2以上的预定的整 数，该加密装置进一步具备屏蔽值生成部，该屏蔽值生成部根据上述随机 数，生成上述第1 第J输入屏蔽值，上述第1随机化逆元数据生成部根据上述第1部分生成的上述第1随 机化输入数据和所生成的上述第1输入屏蔽值，生成上述第1随机化输出 数据，并且，根据上述第2部分生成的上述第t随机化输入数据和所生成 的上述第t输入屏蔽值，生成上述第t随机化输出数据，其中，2《t《J，上述输出数据处理部根据所生成的第J随机化输出数据，生成上述密文。
6、 一种解密装置，使用密钥，根据密文生成译文，其特征在于，具备随机数生成部，生成随机数；随机化输入数据生成部，接收上述密文，将根据上述随机数决定的预 定的输入屏蔽值和对上述密文利用上述密钥进行了预定的处理的输入数 据相加，生成随机化输入数据；第l随机化逆元数据生成部，接收由上述随机化输入数据生成部所生 成的上述随机化输入数据和上述输入屏蔽值，将所接收到的上述输入屏蔽 值的在预定的第1有限域中的逆元即输出屏蔽值和该输入数据的在上述第 l有限域中的逆元相加，生成随机化输出数据；以及输出数据处理部，接收由上述第1随机化逆元数据生成部生成的上述 随机化输出数据，根据接收到的该随机化输出数据生成上述译文。
7、 一种加密方法，使用密钥，根据明文生成密文，其特征在于，包括随机数生成步骤，生成随机数；随机化输入数据生成步骤，接收上述明文，将根据上述随机数决定的 预定的输入屏蔽值和对上述明文利用上述密钥进行了预定的处理的输入 数据相加，生成随机化输入数据；第1随机化逆元数据生成步骤，接收由上述随机化输入数据生成步骤 生成的上述随机化输入数据和上述输入屏蔽值，将接收的上述输入屏蔽值 的在预定的第1有限域中的逆元即输出屏蔽值和该输入数据的在上述第1 有限域中的逆元相加，生成随机化输出数据；以及输出数据处理步骤，接收由上述第1随机化逆元数据生成步骤生成的 上述随机化输出数据，根据接收到的该随机化输出数据生成上述密文。
8、 一种集成电路，使用密钥，根据明文生成密文，其特征在于，具备随机数生成部，生成随机数；随机化输入数据生成部，接收上述明文，将根据上述随机数决定的预 定的输入屏蔽值和对上述明文利用上述密钥进行了预定的处理的输入数 据相加，生成随机化输入数据；第l随机化逆元数据生成部，接收由上述随机化输入数据生成部生成的上述随机化输入数据和上述输入屏蔽值，将所接收的上述输入屏蔽值的 在预定的第1有限域中的逆元即输出屏蔽值和该输入数据的在上述第1有 限域中的逆元相加，生成随机化输出数据；以及输出数据处理部，接收由上述第1随机化逆元数据生成部生成的上述 随机化输出数据，根据所接收到的该随机化输出数据生成上述密文。
全文摘要
作为针对AES加密的电力分析攻击对策，如果采用通过合成域上的逆元计算安装S-Box的屏蔽法，则存在最大逻辑级数变大而处理速度降低的问题。本发明的加密装置(1)，使用密钥，根据明文生成密文，具备随机化8位逆元计算部(101)，接收随机化输入数据和输入屏蔽值，将接收到的上述输入屏蔽值的逆元即输出屏蔽值和该输入数据的逆元相加，生成随机化输出数据，上述随机化输入数据是将根据随机数决定的预定的上述输入屏蔽值和利用上述密钥进行了预定的处理的输入数据相加得到的数据；该加密装置根据所生成的该随机化输出数据，生成上述密文。
文档编号G09C1/00GK101542558SQ20088000061
公开日2009年9月23日 申请日期2008年5月26日 优先权日2007年5月30日
发明者太田雄策, 横田薰 申请人:松下电器产业株式会社
技术领域：
本发明涉及一种加密装置、解密装置、加密方法及集成电路，它们能 够防止被通过对执行加密处理时的电力消耗量进行测量来对加密模块中 所嵌入的密钥进行分析的攻击方法所破解。
背景技术：
近年来，设计有各种以硬件或软件中所安装的加密模块进行加密处理 时所使用的副信息为线索来分析密钥的破解法。例如，在被称为时序攻击 的分析方法中，利用加密模块在加密处理中需要的时间和用在加密处理中 的密钥的值的细微的差异来进行密钥的分析。即，在时序攻击中，利用进 行加密处理时的称作处理时间的副信息，进行密钥的破解。在那样的破解 法中，作为以进行加密处理时的电力消耗量为副信息来进行破解的破解方
法，设计有简单能量分析攻击(Simple Power Analysis)或差分能量分析攻 击(Differential Power Analysis)等各种方法。近年来，在能够便宜购入高 性能的测量机器的背景下，有报告称这些破解法也能够对IC卡这样的施 加加密的实际产品进行分析。此外，设计有在以进行加密处理时从加密模 块产生的电磁波强度为副信息来进行破解的方法等各种破解方法。在下面 的记述中，把以加密处理时的加密模块的电力消耗量为线索分析密钥的破 解方法总称为"电力分析攻击"。下面，以电力分析攻击为例进行说明， 但本发明对利用副信息的其他分析方法也同样有效。即，本发明不仅适用 于电力分析攻击，只要是利用在加密处理中从加密模块产生的副信息来推 定密钥的分析方法就均可以适用。
电力分析攻击利用加密模块的电力消耗量和加密处理过程中的中间 值之间的关系来进行密钥的分析。因此，作为针对电力分析攻击的对策， 考虑到利用随机数对加密处理过程中的中间值进行随机化，从而使得电力 消耗量和中间值之间的相关关系难以理解的方法，所述随机数是在加密模块内部所生成的。这样，将对加密处理的中间值进行随机化的过程称为将 中间值进行"屏蔽"。此外，把通过屏蔽中间值来使得电力分析攻击的密 钥分析变困难的方法总称为"屏蔽法"。
在专利文献1中记载的屏蔽法中，公开有针对美国标准密码术DES
(Data Encryption Standard,即数据加密标准)加密的屏蔽法(称为现有技 术l)。
(现有技术1的概要)
根据现有技术l的方法，在加密处理之前，首先根据加密模块内部生 成的随机数，将在DES加密中使用的数据变换用表Sbox进行随机化，来 制作随机化Sbox表，并暂时保管。在加密处理中，使用该随机化Sbox表， 对加密处理的中间值进行屏蔽，以使得电力分析攻击就变得困难。这里， 在现有技术l中，需要用于暂时储存随机化Sbox表的RAM。因此，在对 RAM容量有严格限制的情况下，就出现了不能使用现有技术1的问题。 此外，在硬件中安装加密模块的情况下， 一般来说在逻辑电路中安装Sbox 表的情况较多。因此，由于不能制作随机化Sbox表，就出现了不能使用 现有技术1的问题。
(现有技术2的概要)
在非专利文献1所记载的屏蔽法中，公开有针对美国下一代标准密码 术AES (Advanced Encryption Standard)加密的屏蔽法(称为现有技术2)。 在现有技术2中，能够在逻辑电路中安装Sbox表，并且，如现有技术1 所示，由于没有必要制作随机化Sbox表，因此适用于硬件安装。下面， 对其概要进行说明。
已知AES加密的Sbox表与进行扩张域GF(2^)上的逆元计算("XAY" 表示"X的Y次方")和规定的进行仿射变换的处理等价。此外，作为用 电路实现扩张域GF (2A8)上的元素X的逆元计算的方法，有下面的既有 方法。
(1) 将X变换为和GF (2A8)同型的合成域GF ( ( (2A2) 、) A2) 上的元素A。
(2) 在上述合成域上计算A的逆元AA ( — l)。
(3) 将A八(一l)逆变换为扩张域上的元素，求得XA ( — l)。 在该方法中，通过在合成域上进行逆元计算，能够以较小的电路规模安装逆元计算。
如果将AES加密的Sbox表通过上述的逆元计算和仿射变换来安装并
适用屏蔽法，则能够以小的电路规模提高对电力分析攻击的耐性。此时，
怎样对逆元计算部分实施屏蔽成为关键。下面，对现有技术2中的逆元计
算部分的屏蔽方法进行简单的说明。
图1~图7是表示现有技术2中的加密装置中设置的随机化8位逆元计 算部81的图。
<随机化8位逆元计算部81>
图1是表示现有技术2中的随机化8位逆元计算部81的结构的框图。 随机化8位逆元计算部81以被屏蔽的逆元计算对象数据X (8位)、屏蔽 数据R (8位)及计算用随机数r (4位)作为输入，进行逆元计算，输出 被屏蔽的逆元计算结果Y (8位)。这里，X是用屏蔽数据R进行了屏蔽 的状态的数据，表示为X=M ( + ) R。这里，M (8位)是被屏蔽前的数据， "(+ )"是表示对每个位的按位加运算。此时，Y成为Y={MA (_1) } (+ ) R。 S卩，随机化8位逆元计算部81进行如下处理以用R进行了屏 蔽的M为输入，计算逆元，将其结果MA ( —1)在用R屏蔽了的状态下 进行输出。即，对于作为加密处理的中间值即M，由于在利用随机的屏蔽 数据R进行了屏蔽的状态下进行逆元计算，从而使得电力分析攻击变得困 难。
如图1所示，随机化8位逆元计算部81包括进行合成域GF( ((2、) A2) A2)上的17次方计算的17次方计算部810、 812; 4位校正项计算部 811 (图2) ; 4位输出计算部816、 817 (图3);进行4位的按位加运算 的按位加部813、 814、 818、 819;随机化4位逆元计算部815 (图4)。
这里，如图2所示，4位校正项计算部811包括进行在合成域GF ((2A2) A2)上的乘法运算的4位乘法部811a、 811b;以及进行4位的按 位加运算的按位加部811c、 811d。另外，对合成域GF ( (2A2) A2)进行 2次扩张的结果为合成域GF ( ( (2A2) A2) A2)。
此外，如图3所示，4位输出计算部816、 817包括进行在合成域 GF ( (2A2) A2)上的乘法运算的4位乘法部816a、 816b、 816c、 816d; 以及进行4位的按位加运算的按位加部816e、 816f、 816g、 816h、 816i、 816j。
8此外，如图4所示，随机化4位逆元计算部815 (图4)包括进行 在合成域GF ( (2A2) A2)上的5次方计算的5次方计算部820、 822; 2 位校正项计算部821 (图5) ; 2位输出计算部826、 827 (图6);进行2 位按位加运算的按位加部823、 824、 828、 829;以及随机化2位逆元计算 部825 (图7)。
这里，如图5所示，2位校正项计算部821 (图4、图5)包括进行 有限域GF (2A2)上的乘法运算的2位乘法部821a、 821b;以及进行2位 的按位加运算的按位加部821c、 821d。另外，对有限域GF (2A2)进行2 次扩张的结果为合成域GF ( (2l) A2)。
此外，如图6所示，2位输出计算部826、 827 (图6、图4)包括 进行在有限域GF (2A2)上的乘法运算的2位乘法部826a、 826b、 826c、 826d;以及进行2位的按位加运算的按位加部826e、 826f、 826g、 826h、 826i、 826j。
此外，如图7所示，随机化2位逆元计算部825 (图7、图4)包括进 行1位的按位加运算的按位加部825a、 825b。
如上所述，现有技术2中的设置在加密装置中的随机化8位逆元计算 部81 (图1)包括在内部递归性地执行随机化4位逆元计算部815和随机 化2位逆元计算部825，通过该结构，和其他现有技术相比，能够以较小 .的电路规模来安装。
在现有技术2中，公开有一种适于硬件安装的加密装置，该加密装置 通过设置上述的随机化8位逆元计算部81 (图l)，并利用逆元计算和仿 射变换安装AES加密的Sbox表。
非专利文献1:森岡澄夫、秋下徹、「合成域^r用v、/iAES S — B
o x回路〖対t3DPa攻撃」、〕/匕。工一夕-fe年二！Jx,、:/y求-々
厶2 0 0 4予稿集(平成l 6年1 0月)
非专禾lj文南犬2: Federal Information Processing Standards Publication
November 26 2001
专利文献l:美国专利第6295606号说明书
但是，在现有技术2中，如前所述，由于随机化8位逆元计算部81 (图1)具有递归的结构，所以具有最大逻辑级数变大的问题。在把现有技术2的随机化8位逆元计算部81用电路实现时，若预估关键路径和其
最大逻辑级数，则如下。
随机化8位逆元计算部81 (图1 图7)的关键路径如下。 首先，在图1中，关键路径如下。
17次方计算部810=〉按位加部813=〉按位加部814=〉随机化4位逆 元计算部815 (图4) =〉 4位输出计算部817 (图3)=〉按位加部818=〉 按位加部819
这里，在该路径中的4位输出计算部817 (图3)和随机化4位逆元
计算部815 (图4)的内部的关键路径如下。
首先，4位输出计算部817 (图3)的内部的关键路径如下。
4位乘法部816a=〉按位加部816e=〉按位加部816f=〉按位加部816i=〉
按位加部816j
此外，随机化4位逆元计算部815 (图4)的内部的关键路径如下。 5次方计算部820=〉按位加部823=〉按位加部824=〉随机化2位逆
元计算部825 (图7) =〉 2位输出计算部827 (图6)=〉按位加部828=〉
按位加部829
此路径中具有2位输出计算部827 (图6)和随机化2位逆元计算部
825 (图7)。它们内部的关键路径分别如下。
首先，2位输出计算部827 (图6)的内部的关键路径如下。
2位乘法部826a=〉按位加部826e=〉按位加部826f=〉按位加部826i=〉
按位加部826j
然后，随机化2位逆元计算部825 (图7)的内部的关键路径如下。 按位加部825a=〉按位加部825b
通过以上处理，随机化8位逆元计算部81 (图l)的最大逻辑级数成 为连续处理下面的处理时的逻辑级数。 17次方计算X1次 5次方计算X1次 4位乘法X1次 2位乘法X1次 按位加运算X18次
另外，这里，"按位加运算X18次"中的18是由18=4+4+4+4+2的计算得来的。
如上所述，现有技术2有最大逻辑级数变大的问题。
发明内容
本发明为解决上述现有技术2的加密处理中的问题，使用Sbox表的 安装法，提供一种比现有技术2还能够削减最大逻辑级数的加密装置，该 Sbox表使用和现有技术2同样的合成域GF ( ( (2A2) A2)、)上的逆元 运算。
为解决上述问题，本发明采用下面的结构。
艮口，采用如下的加密装置，其使用密钥，根据明文生成密文，并具备 第1随机化逆元数据生成部，该第1随机化逆元数据生成部接收随机化输 入数据和输入屏蔽值，将接收到的上述输入屏蔽值的在预定的第1有限域 中的逆元即输出屏蔽值和该输入数据的在上述第1有限域中的逆元相加， 生成随机化输出数据，所述随机化输入数据是将根据随机数决定的预定的 上述输入屏蔽值和利用上述密钥进行了预定的处理的输入数据相加得到 的数据；该加密装置根据所生成的上述随机化输出数据，生成上述密文。
根据该加密装置，输出屏蔽值是输入屏蔽值的逆元，能够实现级数较 少的简单结构的加密装置。
根据本发明，能够实现级数较少的简单结构的加密装置。
图1是表示现有技术中的随机化8位逆元计算部81的结构的框图。 图2是表示现有技术中的4位校正项计算部811的结构的框图。 图3是表示现有技术中的4位输出计算部816、 817的结构的框图。 图4是表示现有技术中的随机化4位逆元计算部815的结构的框图。 图5是表示现有技术中的随机化2位校正项计算部821的结构的框图。 图6是表示现有技术中的2位输出计算部826、 827的结构的框图。 图7是表示现有技术中的随机化2位逆元计算部825的结构的框图。 图8是表示本发明的实施方式的加密装置1的结构的框图。 图9是表示本发明的实施方式的加密部la的结构的框图。 图10是表示本发明的实施方式的随机化Roimd_n12的结构的框图。图11是表示本发明的实施方式的随机化Round—10 13的结构的框图。 图12是表示本发明的实施方式的随机化SubBytes120、 130的结构的 框图。
图13是表示本发明的实施方式的随机化S—boxl20a 120p的结构的 框图。
图14是表示本发明的实施方式的随机化8位逆元计算部101的结构 的框图。
图15是表示本发明的实施方式的17次方计算部110、 112的结构的 框图。
图16是表示本发明的实施方式的4位校正项计算部111的结构的框图。
图17是表示本发明的实施方式的16次方计算部115、 117的结构的 框图。
图18是表示本发明的实施方式的4位输出计算部118、 119的结构的 框图。
图19是表示本发明的实施方式的4位乘法部20的结构的框图。 图20是表示本发明的实施方式的2位乘法部21的结构的框图。 图21是表示本发明的实施方式的4位逆元计算部116的结构的框图。 图22是表示本发明的实施方式的2位逆元计算部142的结构的框图。 图23是表示本发明的实施方式的随机化4位逆元计算部114的结构 的框图。
图24是表示本发明的实施方式的5次方计算部141、 150、 152的结 构的框图。
图25是表示本发明的实施方式的2位校正项计算部151的结构的框图。
图26是表示本发明的实施方式的4次方计算部155、 157的结构的框图。
图27是表示本发明实施方式的2位输出计算部158、 159的结构的框图。
图28是表示本发明的实施方式的随机化2位逆元计算部154的结构 的框图。图29是表示本发明的实施方式的随机数更新部17的结构的框图。
图30是表示本发明的实施方式的8位逆元计算部171的结构的框图。
图31是表示本发明的实施方式的解密装置3的结构的框图。
图32是表示本发明的实施方式的解密部3a的结构的框图。
图33是表示本发明的实施方式的随机化InvRound_n 32的结构的框图。
图34是表示本发明的实施方式的随机化InvRoundJ) 33的结构的框图。
图35是表示本发明的实施方式的随机化Im/SubBytes331的结构的框图。
图36是表示本发明的实施方式的随机化InvS—Box331a 331p的结构 的框图。
图37是表示本发明的实施方式的随机数更新部37的结构的框图。 图38是表示加密装置1、加密装置1具有的部分之间的包含关系、及 其整体和部分之间的输入输出数据的图。 附图标记 1 加密装置 la 加密部 lb， 3b 轮密钥生成部 lc， 3c 密钥保管部 10， 30 屏蔽处理部
11， 123， 132， 31， 322， 322 AddRoundKey 12X 随机化Round—t
12 随机化Round—n
13 随机化Round—10 14， 34 中断屏蔽处理部 15， 35 随机数生成部
16， 36 随机数暂时存储部
17， 37 随机数更新部
100， 103， 170， 303 合成域变换部
101 随机化8位逆元计算部102， 172 扩张域变换兼矩阵变换部
104， 110a， 110e， lllc， 113， 115a， 118c， 118e， 140， 142a， 150a， 150e， 151c， 153， 154c， 155a， 158c， 158e， 171a， 204， 205， 207， 214， 215， 216 按位加部
110X， 110， 112， 171b 17次方计算部
20， 110b, 110c， 110d， llla， 111b, 118a， 118b， 118d， 171d， 171e 4位乘法部
111 4位校正项计算部
114 随机化4位逆元计算部
115X， 115， 117 16次方计算部
116， 171c 4位逆元计算部
118X， 118， 119 4位输出计算部
120X， 120， 130 随机化SubBytes
121X， 120a， 120b， 120c， 120p 随机化S — Box
121， 131 ShiftRows
122 MixColumns
141X， 141， 150， 152 5次方计算部 142， 156 2位逆元计算部
21， 143， 144， 150b， 150c， 150d， 151a， 151b， 158a， 158b， 158d， 200， 201， 202， 203， 2062位乘法部 151 2位校正项计算部 154 随机化2位逆元计算部 155X， 155， 157 4次方计算部 158X， 158， 159 2位输出计算部 171 8位逆元计算部 210， 211， 212， 213 逻辑积部 3 解密装置 3a 解密部
32 随机化InvRound—n
33 随机化InvRound—0
300， 370 合成域变换兼矩阵变换部301 8位随机化合成域逆元计算部
302， 372 扩张域变换部
320， 330 InvShiftRows
321， 331 随机化InvSubBytes
323 InvMixColumns
331a， 331b， 331c， 331p 随机化InvS —Box
371 8位合成域逆元计算部 81 随机化8位逆元计算部 810， 812 17次方计算部 811 4位校正项计算部 815 随机化4位逆元计算部 816， 817 4位输出计算部
8Ua， 811b， 816a， 816b， 816c， 816d 4位乘^去部
820， 822 5次方计算部
821 2位校正项计算部
825 随机化2位逆元计算部
826， 827 2位输出计算部
821a， 821b， 826a， 826b， 826c， 826d2位乘法部
811c， 811d， 813， 814， 816e， 816f， 816g， 816h， 816i， 816j， 818，
819， 821c， 821d， 823， 824， 825a， 825b， 826e， 826f， 826g， 826h， 826i，
826j， 828， 829 按位加部
具体实施例方式
技术方案l中所记载的方式(本发明的一个实施方式)的加密装置是
使用密钥从明文生成密文，具备随机数生成部，生成随机数；随机化输
入数据生成部，接收上述明文，将根据上述随机数决定的预定的输入屏蔽 值和对上述明文利用上述密钥进行了预定的处理的输入数据相加，生成随
机化输入数据；第1随机化逆元数据生成部，接收由上述随机化输入数据 生成部生成的上述随机化输入数据和上述输入屏蔽值，将接收的上述输入 屏蔽值的在预定的第1有限域中的逆元即输出屏蔽值和该输入数据的在上 述第1有限域中的逆元相加，生成随机化输出数据；以及输出数据处理部，
15接收由上述第1随机化逆元数据生成部生成的上述随机化输出数据，根据 接收到的该随机化输出数据生成上述密文。
根据本方式，为了防止通过测量副信息来分析出用于根据明文生成密 文的密钥，在根据用该密钥进行了预定的处理的输入数据加上输入屏蔽值 的随机化输入数据，生成己加上了输出屏蔽值的随机化输出数据时，输出 屏蔽值为输入屏蔽值的逆元，由此，通过级数较少的简单结构，根据随机 化输入数据生成随机化输出数据，能够形成级数少的简单结构的加密装 置。
另外，该加密装置进一步具备屏蔽值生成部，该屏蔽值生成部接收所 生成的上述随机数，根据所接收的该随机数生成上述输入屏蔽值，上述第 1随机化逆元数据生成部也可以接收所生成的上述输入屏蔽值，进行上述 生成过程。这样，就不需要从外部向加密装置输入输入屏蔽值的结构，就 能够形成简单的系统结构。
技术方案2中所记载的方式(本发明的一个实施方式)的加密装置的 上述第1随机化逆元数据生成部具备第1乘方计算部，对上述随机化输 入数据和上述输入屏蔽值进行预定的第1指数的乘方计算，分别通过各乘 方计算生成第1乘方随机化输入数据和第1乘方输入屏蔽值；校正数据生
成部，根据上述随机化输入数据和上述输入屏蔽值，生成预定的校正数据；
加法部，将所生成的上述校正数据和计算出的上述第1乘方随机化输入数
据相加，生成副随机化输入数据；第2随机化逆元数据生成部，接收上述 副随机化输入数据和上述第1乘方输入屏蔽值，将该第1乘方输入屏蔽值 的在预定的第2有限域中的逆元即屏蔽值和上述副随机化输入数据的在该 第2有限域中的逆元相加，生成随机化副输出数据；以及随机化输出数据 生成部，根据上述随机化副输出数据、上述随机化输入数据、上述输入屏 蔽值及上述第1乘方输入屏蔽值，生成上述随机化输出数据。
根据本方式，通过容易理解的结构生成随机化输出数据，减少了故障 和动作不良，能够实现设计容易，同时能够以级数少的简单结构实现加密 装置。
此外，方式A (本发明的一个实施方式)的加密装置，在随机化合成 域逆元计算部的运算中，把以往的从X二M+R向Y=MA ( — +11的变换， 替换为从X二M+R向Y=MA ( — l) +RA ( — l)变换，由此， 一方面能够比现有技术更削减最大逻辑级数， 一方面也能够实现现有方法的能够紧凑安 装的优点。
此外，方式B (本发明的一个实施方式)的加密装置，基于密钥，对 明文进行规定的加密处理，生成密文，具备随机数生成部，生成随机数; 以及第1随机化逆元计算部，接收随机化输入数据和输入屏蔽值，并进行 第l有限域上的逆元计算，输出随机化输出数据。其中，上述随机化输入 数据是通过把输入屏蔽值和输入数据相加来进行了屏蔽的值，上述随机化 输出数据是通过把输出屏蔽值和输出数据相加来进行了屏蔽的值，上述输 入屏蔽值是根据上述随机数决定的值，上述输出数据是上述输入数据的在 上述第1有限域中的逆元，上述输出屏蔽值是上述输入屏蔽值的在上述第 1有限域中的逆元。
这里，该方式B中的加密装置的上述第1随机化逆元数据计算部也可 以具备第l乘方计算部，分别对上述随机化输入数据和上述输入屏蔽值 进行第1指数的乘方运算，生成第1乘方随机化输入数据和第1乘方输入 屏蔽值；校正数据生成部，根据上述随机化输入数据和上述输入屏蔽值， 生成校正数据；加法部，将上述校正数据和上述第1乘方随机化输入数据 相加，生成副随机化输入数据；第2随机化逆元计算部，接收上述副随机 化输入数据和上述第1乘方输入屏蔽值，进行第2有限域上的逆元计算， 生成随机化副输出数据；以及随机化输出数据生成部，根据上述随机化副 输出数据、上述随机化输入数据、上述第1乘方输入屏蔽值及上述输入屏 蔽值，生成上述随机化输出数据。
另外，该方式B中的加密装置的上述随机化输出数据生成部也可以是 具备第2乘方计算部，对上述随机化输入数据和上述输入屏蔽值分别进 行第2指数的乘方计算，生成第2乘方随机化输入数据和第2乘方输入屏 蔽值；逆元运算部，对上述第1乘方输入屏蔽值进行上述第2有限域上的 逆元计算，生成逆元乘方输入屏蔽值；以及随机化输出数据计算部，根据 上述随机化副输出数据、上述第2乘方随机化输入数据、上述逆元乘方输 入屏蔽值和上述第2乘方输入屏蔽值，生成上述随机化输出数据。
另外，方式C的(本发明的一个实施方式)解密装置，基于密钥，对 密文进行规定的解密处理，生成译文，具备随机数生成部，生成随机数;' 第l随机化逆元计算部，接收随机化输入数据和输入屏蔽值，进行第l有
17限域上的逆元计算，输出随机化输出数据。其中，上述随机化输入数据是 通过把输入屏蔽值和输入数据相加而进行了屏蔽的值，上述随机化输出数 据通过把输出屏蔽值和输出数据相加而进行了屏蔽的值，上述输入屏蔽值 是根据上述随机数决定的值，上述输出数据是上述输入数据的在上述第1 有限域中的逆元，上述输出屏蔽值是上述输入屏蔽值的在上述第1有限域 中的逆元。
(实施方式)
下面，参照附图对本发明的实施方式加以说明。
另外，在实施方式中，虽然使用了合成域GF ( ( (2A2) A2) A2)及其 子域GF ( (2A2) A2) 、 GF (2、) 、 GF (2)的运算，但这些会成为下面 的关系。
用不可约多项式xA2+x+l对GF(2)进行2次扩张而得的是GF(2A2)。 用不可约多项式xA2+x+小对GF( 2A2)进行2次扩张而得的是GF( (2、) A2)。
用不可约多项式/2+x+入(二进制数)对GF ( (2A2)八2)进行2次 扩张而得的是GF ( ( (2A2) A2) A2)。
此时，设xA2+x+l=0的根为a时，4> = a、入=a 、+a ，所以分别进 行位标记为4)=10 (二进制数)、人=1100 (二进制数)。
<实施方式的概要〉
在进行实际处理的详细说明之前，首先，与非专利文献l即现有技术 2中公开的现有方式进行对比来说明本实施方式的概要。
在非专利文献1中公开的现有技术即现有技术2中，随机化8位逆元 计算部81 (图1等)对输入数据X二M ( + ) R，使用随机数R及r来进行 随机化逆元计算，生成了输出数据Y二MT ( — 1) ( + ) R。这里，X是将本 来的数据M用随机屏蔽R进行屏蔽后的值，随机化8位逆元计算部81求 得在GF ( ( (2A2) A2) A2)中的M的逆元M八(一l)，并以用随机屏蔽 R对该值实施了屏蔽的形式M^ ( — l) ( + ) R进行输出。
本发明的实施方式中，将上述随机化8位逆元计算处理，用随机数R 对输入数据X=M ( + ) R进行随机化逆元计算，生成输出数据Y=MA ( — l) (+) RA ( — 1)。即，输出数据的随机屏蔽值在现有技术2中是R，但在 本发明中，变成了y 。这样，通过计算不同于现有技术2的输出数据，如后面所述，就能够比现有技术更削减最大逻辑级数。
图8 图38是分别表示实施方式中加密装置1及加密装置1的各部分的图。
然后，图38是表示实施方式中的加密装置1的整体和各部分之间的 包含关系的图。下面，适当参照图38，对图1~图23所表示的加密装置1 进行说明。
如图38所示，加密装置1 (图8)具备随机化8位逆元计算部101 (图 13、图14)。加密装置1 (图8)具备加密部la (图8、图9)。加密部 la具备屏蔽处理部10 (图9)、随机化Round—tl2X(随机化Round—nl2(图 9、图10)、随机化Round—10 13(图9、图U))、中断屏蔽处理部14 (图9)。 另夕卜，在图38中，省略掉了图8~图37中所示的加密装置1的各部分中的 一部分。
并且，图38中所示的随机化Round一t12 (图9及图10中所示的随机 化Round—n12、图9及图11中所示的随机化Round—10)具备随机化 SubBytesl20X(图10、图ll、图12)。该随机化SubBytesl20X具备随机化 S — Boxl21X(图12中所示的随机化S — Boxl20a 随机化S—Boxl20p)，另 外，该随机化S—Boxl21X具备随机化8位逆元计算部IOI(图13，图14)。
并且，如图38所示，该随机化8位逆元计算部101 (图38、图14等) 被输入随机化输入数据ID8t=Tl (V8t) +T1 (Rt)，根据利用屏蔽值进行 了屏蔽的该随机化输入数据ID8t二Tl (V8t) +T1 (Rt)，计算出随机化输 出数据OD8t二Tl (V8t) A ( — l) +T1 (Rt) A ( — l)，并输出计算出的该 OD8t，所述屏蔽值是基于Rt变成Tl (Rt)的值。总之，该随机化8位逆 元计算部101 (图13、图14)对设为M-T1 (V8t) 、 R=T1 (Rt)的上述 输入数据X二M ( + ) R，进行生成输出数据Y二]Vr ( — l) ( + ) R ( — l) 的处理。
本实施方式中的加密装置1 (图38、图8)具备随机化8位逆元计算 部101，该随机化8位逆元计算部101根据X二M ( + ) R生成Y=MA ( —1) (+ ) RA ( — l)，能够削减最大逻辑级数。
下面，对那样的加密装置1的详细处理进行说明。 <加密装置1>
图8是表示本发明的实施方式中的加密装置1的结构的框图。加密装置l (图8)具备加密部la (图9)、轮密钥生成部lb及密钥 保管部lc。
加密装置1 (图8)针对输入加密装置1的128位明文(平文)P (128 位)，使用装置内部保持的密钥K (128位)进行被随机化的AES加密处 理(AES: Advanced Encryption Standard)，并输出密文C (128位)。密 文C和针对明文P使用密钥K进行AES加密处理的结果相同。此外，由 于在装置内部利用每次加密处理中随机生成的随机数对加密处理过程中 的加密处理中间值进行随机化，因此电力分析攻击的密钥K的分析就变得 困难。下面，对加密装置1的处理过程进行说明。
另外，详细的讲，AES加密是在加密处理中反复循环的、采用了以下 两种结构中后者的SPN结构的加密，所述两种结构之一是反复加密的代表 性的构成法即Feistel结构，另一结构是SPN (Substitution Permutation Network Structure)结构。
这里，加密装置1例如也可以是设置在IC卡中的加密装置。
密钥保管部lc保管在加密装置1中事先设定的密钥K。密钥K也可 以在制造加密装置1时设定，也可以在加密装置1制造完成后在装置内生 成的密钥保管部lc中设定。如果输入明文P，加密装置1就进行以下处理。
(1) 密钥保管部lc将保管的密钥K输入到轮密钥生成部lb。
(2) 轮密钥生成部lb按照AES加密方式的轮密钥生成处理，根据密 钥K生成轮密钥RK0 RK10 (各128位)，输入到加密部la。另外，轮 密钥生成处理已经记载在非专利文献2中而予以公开，这里就不做详细说 明。
(3) 加密部la使用轮密钥RK0 RK10对明文P进行后述的加密处理， 生成密文C并输出。
接着，对加密部la的处理进行说明。 <加密部la>
图9是表示加密部la的结构的框图。
如图所示，加密部la (图8、图38)具备屏蔽处理部10、 AddRoundKeyll、随机化Round—n12 (图IO)、随机化RoundJ0 13 (图
11)、中断屏蔽处理部14、随机数生成部15、随机数暂时存储部16以及 随机数更新部17。
20加密部la对明文P (128位)使用轮密钥RK0 RK10 (128位X11个) 进行加密处理，生成密文(128位)并输出。加密部la在被输入的轮密钥 RK0 RK10中，把轮密钥RKO输入AddRoundKeyl 1 ，轮密钥RKn(n=l 9) 输入随机化Round_nl2 (图10) ， RK10输入随机化Round—10 13 (图11)。
加密部la进行以下的处理。
(1) 随机数生成部15随机地生成随机数RO (8位)。然后，随机数 生成部15将生成的随机数RO暂时存储在随机数暂时存储部16。另外，作 为一个例子，在每一次新的明文P被输入到加密装置1中，加密装置1开 始新的加密处理时，随机数生成部15就生成新的随机数R0，也可以存储 生成的随机数R0。
(2) 屏蔽处理部10使用随机数暂时存储部16中存储的随机数R0， 对明文P进行如下的按位加运算，从而求得数据A (128位)。经过该处 理，利用随机屏蔽值RO对明文P进行屏蔽。
A=P ( + ) (R0， R0， R0，…,R0)
这里，(R0， R0， R0，…，R0)表示将16个R0 (8位)结合的128 位数据。另外，下面，如果不特别说明，就将16个8位数据X结合而成 的128位数据表示成(X， X， X，…，X)。
另外，图8所示的P在图38中由标记U表示。此外，图8中所示的 C在图38中由标记C表示。此外，图9中所示的A在图38中图示为IA。 此外，图9中所示的B、 D在图38中由标记IAt (t=l 9或t=10)表示。 此外，图9中表示的E在图38中由标记OA10=OAt (t=10)表示。
(3) 随机数更新部17对随机数暂时存储部16中存储的随机数R0进 行后述的随机数更新处理，生成R1，并将随机数暂时存储部16中存储的 随机数R0更新为R1。
(4) AddRoundKeyll对在上述(2)中由随机数生成部15求得的上 述A，使用下面的RKO进行密钥相加处理，求得B1。这就是AES加密算 法标准中规定的AddRoundKey处理。
B1=A ( + ) RKO
(5) 然后，随机化Round—nl2关于n4、 2、 3、…、9反复执行下面 的处理。
(5 — 1)随机化Round一n12使用轮密钥RKn和存储在随机数暂时存储部16中的随机数Rn，对Bn (向该随机化Round_nl2输入的输入数据B 中的第n个数据)进行后述的随机化Round—n处理，生成Bn+l。然后， 随机化Round—n12，在『9的情况下，即所生成的B (n+l)是B (n+l) =B10的情况下，使D=B10，将D输入随机化Round—10 13;在n#9的情 况下，即11=1、 2、…、9，所生成的B (n+l)是B2、 B3、…、B9中某一 个的情况下，将该B (n+l)再次输入到Round一n12。
(5—2)随机数更新部17对随机数暂时存储部16中存储的随机数Rn 进行后述的随机数更新处理，生成Rn+l，将随机数暂时存储部16中存储 的随机数Rn更新为Rn+1。随机数更新部17根据由随机数生成部15生成 的随机数RO,生成随机数R1、随机数R2、…、随机数Rll，并将随机数 暂时存储部16中存储的随机数更新为生成的各个随机数，由此将各该随 机数分别提供给屏蔽处理部10、随机化Round—n12、 Round—10 13以及中 断屏蔽处理部14中与该随机数对应的结构中。随机数更新部17通过随机 数暂时存储部16将随机数R0提供给屏蔽处理部10，将随机数R1 R9提 供给随机化Round—n12，将随机数R10提供给随机化Round—10 13，将随 机数Rll提供给中断屏蔽处理部14。
(5—3)加密部la在n=9的情况下，结束反复处理的循环，转移到 接下来的随机化Round—10 13的处理，在n#9的情况下，将n的值加1， 再次执行上述(5 — 1) (5 — 3)的处理。
(6) 随机化Round—10 13使用轮密钥RK10和随机数暂时存储部16 中存储的随机数R10，对经过上述(5)的处理得到的向随机化Round一10 13 输入的输入数据D (128位)进行后述的随机化Round—10处理，生成数据 E (128位)。随机化RoundJ0 13将数据E输入中断屏蔽处理部14中。
此外，随机数更新部17对随机数暂时存储部16中存储的随机数R10 进行后述的随机数更新处理，将随机数暂时存储部16中存储的随机数R10 更新为随机数Rll。随机数更新部17通过向该R11的更新，将随机数Rll 提供给中断屏蔽处理部14。
(7) 中断屏蔽处理部14使用随机数暂时存储部16中存储的随机数 Rll，在上述(6)中对从随机化Round—10得到的数据E进行下面的按位 加运算，生成密文C (128位)。经过该处理，被屏蔽的数据E被中断屏 蔽(去除屏蔽的影响)，从而得到没有被屏蔽的密文C。C=E ( + ) RU
(8)加密部la将在上述(7)中得到的密文C作为加密部la的输出 数据进行输出。
接着，对在加密部la(图9)内部使用的随机化Round—n12、随机化 Round—10 13的详细结构进行说明。 <随机化Round—nl2>
图10是表示随机化Round—n12 (图9)的结构的框图。
如图10中所示，随机化Round—n12 (图9、图10、图38)具备随机 化SubBytes120 (图12、图38) 、 ShiftRows121 、 MixColumns122以及 AddRoundKey123。
而且，随机化Round—n12使用随机数Rn和轮密钥RKn(n-l、 2、 ..9)， 对向该随机化Round—n12输入的输入数据X (与加密部la的处理说明(图 9)中的数据Bn相对应)进行随机化Round处理，生成输出数据Y(与加 密部la处理说明中的数据Bn+l (图9)相对应)。
另外，随机化Round—n12进行的随机化Round—n处理是如下的处理 对用屏蔽值(Rn， Rn，…，Rn)进行了屏蔽的输入数据X=M ( + ) (Rn， Rn，， Rn)执行AES加密算法标准中规定的1轮处理，从而生成用屏 蔽值(Rn+1， Rn+1，…，Rn+1)屏蔽了的轮处理结果Y-P ( + ) (Rn+1， Rn+1，…，Rn+1)。此时，P与对M进行了 AES加密算法标准中规定的 1轮处理的结果一致。这里，该X是图9的说明中的随机化Round—n处理 的输入数据Bn (n=l、 2、…、9)，此外，该Y是图9的说明中的输出数 据B (n+l) 。 M、 P是分别从Bn、 Bn+1去除屏蔽值的影响后的本来的值 (图38中图示的Vt、 V (t+l))。
另外，图10中的X在图38中由标记IAt (t=l、 2、…、9)表示，Y 由标记OBt (t=l、 2、…、9)表示，Rn由标记Rt (t=l、 2、…、9)表示。
具体说来，随机化Round—n12 (图9、图10)进行如下的处理。
(1) 随机化Round—nl2具备的随机化SubBytes120 (图10、图12) 使用从隨机数暂时存储部16取得的随机数Rn (8位)，对向该随机化 Round—n输入的输入数据X (128位)进行后述的随机化SubBytes处理， 生成数据A (图10)。
(2) ShiftRows121 (图10)对上述(1)中生成的上述数据A进行
23AES加密算法标准中规定的ShiftRows处理，生成数据B (128位)。另 外，关于ShiftRows的详细内容，由于在(非专利文献2)中已经公开， 故不做详细说明。
(3) 接着，MixColumns122 (图10)对上述(2)中生成的上述数据 B进行AES加密算法标准中规定的MixColumns处理，生成数据C (128 位)。另外，关于MixColumns的详细内容，由于在(非专利文献2)中 已经公开，故不做详细说明。
(4) 然后，AddRoundKey 123使用轮密钥RKn，对上述(3)中生成 的上述数据C进行AES加密算法标准中规定的AddRoundKey处理，生成 数据Y( 128位)。然后，AddRoundKey 123将生成的Y作为随机化Round—n12 的输出数据来进行输出。另外，关于AddRoundKey的详细内容，由于在
(非专利文献2)中己经公开，故不做详细说明。
另外，图10的数据A在图38中由标记OBt (t=l、 2、…、9)表示。 <随机化Round—10 13>
图11是表示随机化Round—10 13的结构的框图。
随机化Round—10 13 (图9、图11)具备随机化SubBytes130 (图11、 图12) 、 ShiftRows131、 AddRoundKey 132。
然后，如图11所示，随机化Round—10 13的结构与从随机化Round一n12 去掉MixColumns122的结构相同。这与AES加密算法的标准的最后一轮 不进行MixColumns处理的情况相对应。除此之外，和随机化Round一n12 相同，故省略详细的说明。
另外，随机化Round—10处理是如下的处理对用屏蔽值(R10，R10，…， R10)进行了屏蔽的输入数据X-M ( + ) (R10， R10，， R10)执行AES 加密算法标准中规定的最后一轮处理，生成用屏蔽值(Rll， Rll，…， Rll)屏蔽了的最后一轮处理结果Y=P ( + ) (Rll， Rll，…，Rll)。此 时，P与对M进行了 AES加密算法标准中规定的最后一轮处理的结果一 致。
另外，此处，该X在图9的说明中是数据D，此外，该Y在图9的说 明中是输出数据E， M、 P是从D、 E去除屏蔽值的影响的本来的值(图 38中的V10、 Vll)。
此外，在图38中，由标记OB100Bt (t=10)表示图10中的数据A。接着，随机化Round一n12 (图9、图10)对在随机化Round—10 13 (图 9、图11)中使用的随机化SubBytes120、 130 (图12)进行详细的说明。 <随机化SubBytes 120、 130>
图12是表示随机化SubBytesl20X(随机化SubBytes120(图9、图10)、 随机化SubBytes130 (图9、图11))的结构的框图。例如，随机化 SubBytesl20X是随机化SubBytes120，其他的随机化SubBytes120具有和 该随机化SubBytes120相同的结构。
随机化SubBytesl20X使用随机数R (8位)对输入数据X (128位) 进行随机化S—Box处理，生成输出数据Y (128位)。这里的输入数据X 和随机化Round—n12的处理说明(图10)中的数据X相当，此外，和随 机化RouncL10 13的处理说明(图IO)中的数据X相当。此外，随机数R 和随机化Round—n12的处理说明(图IO)中的随机数Rn相当，和随机化 Round—10 13的处理说明(图ll)中的随机数R10相当。此外，输出数据 Y和随机化RouncLn12的处理说明(图10)中的数据A相当，和随机化 Round—10 13的处理说明(图ll)中的数据A相当。
另夕卜，在图38中，图12中的X由标记IBt表示，Y由标记OBt表示， R由Rt表示。
随机化SubBytesl20X具备随机化S — Boxl20a 随机化S—Boxl20p。 随机化SubBytesl20X (随机化S—Boxl20a 随机化S —Boxl20p)进
行以下的处理。
(1) 随机化SubBytesl20X将输入数据从高位开始按每8位进行分割， 分割为X[O]、 X[l]、…、X[15](参照图12)。
(2) 随机化S—Boxl20a 120p对分割后的X
、 X[l]、…、X[15]， 分别用隨机数R进行随机化S—Box处理，分别生成Y
、Y[1]、…、Y[15]。 关于随机化S—Box处理的详细内容，将在后面加以说明。
(3) 然后，随机化SubBytesl20X将生成的Y[O]、 Y[l]、…、Y[15] 从高位开始按该顺序连结，变成128位数据Y。然后，随机化SubBytesl20X 将该Y作为随机化SubBytesl20X的输出数据来输出。
另夕卜，随机化SubBytes120、 130的处理是如下的处理对用屏蔽值(R， R，…，R)进行了屏蔽的输入数据X二M ( + ) (R， R，…，R)进行AES 加密算法标准中规定的SubBytes处理，生成用屏蔽值(S， S，…，.S)屏蔽的处理结果Y二P ( + ) (S， S，…，S)。此时，P与对M进行AES加
密算法标准中规定的SubBytes处理的结果一致，屏蔽值S与随机数更新部
17对屏蔽值R进行了随机数更新处理的结果相等。
另外，在图38中，该M图示为Vt， P则由S—Box (Vt)表示。 然后，对在随机化SubBytesl20X (随机化SubBytes120、 130)中使用
的随机化S — Boxl20a 120p的详细内容进行说明。 <随机化S—Boxl20a~120p>
图13是表示随机化S—Boxl20X(随机化S—Boxl20a 随机化S—Box 120p:图12)的结构的框图。
随机化S—Boxl21X (图13、图12)具备合成域变换部100 (参照 数学式l)、随机化8位逆元计算部101 (图ll、图38)、扩张域变换兼 矩阵变换部102 (参照数学式2)、按位加部104、合成域变换部103 (参 照数学式1)。
随机化S—Boxl21X是使用随机数R (8位)对输入数据X (8位)进 行随机化S—Box处理，求得输出数据Y(8位)的处理。这里的输入数据 X相当于随机化SubBytes 120X(图12)的处理说明中的数据X[O] 、 X[ 1 ]、…、 X[15]中的某一个，随机数R相当于随机化SubBytesl20X的处理说明(图 12)中的随机数R。此外，输出数据Y相当于随机化SubBytesl20X的处 理说明(图12)中的数据Y[O]、 Y[l]、…、Y[15]中的某一个。
另外，在图38中，由标记IC8t表示该X，由标记OC8t表示Y，由标 记Rt表示R。
随机化S—Boxl21X进行以下的处理。 (1)合成域变换部100将X (8位)从高位开始按每一位迸行分割， 分割成X7、 X6、、 X0。然后，合成域变换部100进行下面的数学式1 的矩阵计算，将通过矩阵计算求得的A7、 A6、…、AO从高位开始按该顺 序结合，作为合成域变换部100的输出数据A (8位)。另外，下述的矩 阵计算是用mod 2进行的。即，在下述的矩阵计算中，是0+0=1+1=0， 0+1=1+0=1。
数学式1广 、 A7卜010〇00、 0广 X7
A601111110X6
A5.01110010X5
A410100010X4
A3〇0011010X3
A201010110X2
A101101100X1
LA0JL10101001J
、
乂
(2) 并且，其他的合成域变换部103和上述的(1) 一样，将R (8 位)从高位开始按每l位进行分割之后，进行数学式l的矩阵计算，根据 R (8位)生成S (8位)。
(3) 接着，随机化8位逆元计算部101利用在上述(2)中生成的随 机数S (8位)对上述(1)中生成的输入数据A (8位)进行后述的随机 化8位逆元计算，生成输出数据B (8位)。
(4) 扩张域变换部兼矩阵变换部102对上述(3)中生成的数据B (8 位)，根据下述的数学式2的矩阵计算式，用和上述(1)同样的方法， 即从高位开始按每一位进行分割，并进行矩阵计算，来生成数据C (8位)。
数学式2
f071广 0111010、 0 、
C611010000巳6
C500101100B5
C41101001B4
C3'—10110101已3
C210010011已2
C110110111已i
—J111010」
(5)按位加部104将在上述(4)中生成的数据C(8位)和常数01100011 (二进制数)进行每位的按位加运算，生成数据Y (8位)。
随机化S—boxl21X将上述(5)中生成的该Y作为随机化S — Boxl21X
的输出数据进行输出。另外，随机化S—Boxl20a 120p的处理是如下的处理对用屏蔽值(R， R，…，R)进行了屏蔽的输入数据X二M ( + ) (R， R，…，R)进行AES 加密算法标准中规定的SubBytes处理内的S—Box表变换，生成用屏蔽值 (S， S,…，S)进行了屏蔽的处理结果Y=P ( + ) (S， S，…，S)。此 时，P与对M进行了 AES加密算法标准中规定的SubBytes处理内的S — Box表变换的结果一致，屏蔽值S和随机数更新部17对屏蔽值R进行随 机数更新处理的结果相等。
另外，在图38中，由标记V8t表示该M，由S—box (v8t)表示P。 在图38中，由标记ID8t表示该A，由标记OD8t表示B。
然后，对在随机化S — Boxl20a 120p内部分别使用的随机化8位逆元 计算部101的详细内容进行说明。
<随机化8位逆元计算部101>
图14是表示随机化8位逆元计算部101的结构的框图。
随机化8位逆元计算部101 (图13、图14、图38)具备17次方运 算部110 (图15) 、 17次方运算部112 (图15) 、 4位校正项计算部111 (图16) 、 16次方运算部115 (图17) 、 16次方运算部117 (图17) 、 4 位输出计算部118 (图18) 、 4位输出计算部U9 (图18) 、 4位逆元计 算部116(图21)、随机化4位逆元计算部114 (图23)、按位加部113。
随机化8位逆元计算部101 (图13、图14)使用随机数R (8位)， 对输入数据X (8位)进行随机化8位逆元计算处理，输出输出数据Y (8 位)。这里的输出数据X如前所述，相当于随机化S—Boxl20a 120p的处 理说明(图13)中的数据A，随机数R相当于随机化S—Boxl20a 120p 的处理说明(图13)中的随机数S。此外，输出数据Y相当于随机化S — Boxl20a 120p的处理说明(图13)中的数据B。
另外，在图38中，由标记ID8t表示该X，由标记RDt表示R，由标 记0D8t表示Y。
随机化8位逆元计算部101执行以下的处理。 (1)随机化8位逆元计算部101，首先将数据X (8位)从高位开始 按每4位进行分割，分割成XO (4位)、XI (4位)。然后，随机化8位 逆元计算部101同样地将随机数R (8位)从高位开始按每4位进行分割， 分割成RO (4位)、Rl (4位)。然后，随机化8位逆元计算部101将
28X0和XI输入17次方运算部110，将X0、 XI、 R0及Rl输入4位校正项 计算部111，将R0和Rl输入17次方运算部112。
(2) 然后，17次方运算部110对输入的X0和X1进行后述的17次 方计算处理，生成输出数据A (4位)。同样地，其他的17次方运算部 112对输入的R0和R1进行17次方计算处理，生成输出数据C (4位)。
(3) 另外，4位校正项计算部111对输入的XO、 XI、 RO、 Rl进行 后述的4位校正项计算处理，生成输出数据B (4位)。
(4) 然后，按位加部113对(2)中生成的数据A和(3)中生成的 数据B进行按位加运算，生成数据D (8位)。
(5) 然后，随机化4位逆元计算部114利用上述(2)中生成的数据 C (4位)，对上述(4)中生成的数据D进行后述的随机化4位逆元计算 处理，生成数据E (4位)。
(6) 此外，16次方运算部115对输入到随机化8位逆元计算部101 的数据X (8位)进行后述的16次方计算处理，生成数据F (8位)。然 后，随机化8位逆元计算部101将生成的数据F从高位开始按每4位进行 分割，分割为FO (4位)、Fl (4位)。同样地，其他的16次方运算部 117对输入到随机化8位逆元计算部101的数据R (8位)进行16次方计 算处理，生成数据H。与上述数据F的情况一样，随机化8位逆元计算部 101将生成的该数据H从高位开始按每4位进行分割，分割为HO (4位)、 Hl (4位)。
(7) 另外，4位逆元计算部116，在上述(2)中，对由在图14的下 侧示出的17次方运算部112生成的数据C (4位)进行后述的4位逆元计 算处理，生成数据G (4位)。
(8) 然后，4位输出计算部118对上述(5)中生成的数据E (4位)、 上述(7)中生成的数据G (4位)、上述(6)中由数据F分割成的数据 FO (4位)、及同样在上述(6)中由数据H分割成的数据HO (4位)进 行后述的4位输出计算处理，生成数据YO (4位)。同样地，其他的4位 输出计算部119对数据E (4位)、数据G (4位)、数据F1 (4位)、及 数据H1 (4位)进行4位输出计算处理，生成数据Y1 (4位)。然后，随 机化8位逆元计算部101，将这样生成的数据YO和Yl从高位开始按该顺 序连结成8位数据Y。然后，随机化8位逆元计算部101将连结的数据Y作为随机化8位逆元计算部101的输出数据来输出。
另外，这样进行的随机化8位逆元计算部101的处理是如下的处理
对用屏蔽值R进行了屏蔽的输入数据X=M( + )R进行合成域GF (((2A2) A2)A2)的逆元计算，生成用屏蔽值R、一1)进行了屏蔽的处理结果￥=乂八 (—1) ( + ) R ( — 1)。此时，XA ( — 1)是在合成域GF ( ( (2A2) A2) A2)中X的逆元，屏蔽值RA (—1)是在合成域GF ( ( (2A2) A2)、)中 R的逆元。
接着，对在随机化8位逆元计算部101的内部使用的17次方运算部 110、 112 (图15中示出的17次方运算部110X) 、 4位校正项计算部111 (图16)、 16次方运算部115、 117(图17中示出的16次方运算部115X)、 4位输出计算部118、 119 (图18中示出的4位输出计算部118X)的详细 内容依次进行说明。
<17次方运算部110、 112〉
图15是表示17次方运算部110X的图。
17次方运算部110X (图14、图15)具备4位乘法部110b (图19)、 4位乘法部110c (图19) 、 4位乘法部110d (图19)、按位加部110a、 按位加部110e。
而且，17次方运算部110X对输入数据X0 (4位)、XI (4位)进行 合成域GF ( ( (2A2) A2) A2)上的17次方计算处理，生成数据处理结果 Y (4位)。此时，对将输入数据X0、 XI从高位开始按该顺序连结而成的 8位数据X进行在合成域GF ( ( (2A2) A2) A2)上的17次方计算的结果 成为Y。艮口
Y=XA (17) in GF ( ( (2、) A2) A2)
此时，成为￥^5= (XA17) A15=XA255，由于X是GF ( ( (2、)、) 、)上的元素，所以YA15=XA255=1。即，Y的位数是15， Y是子域GF( (2、) A2)上的元素。gp， Y是4位的数据。
此外，这里的输入数据X0、 XI相当于随机化8位逆元计算部101的 处理说明(图14)中的数据X0、 X1或者R0、 Rl，输出数据Y相当于随 机化8位逆元计算部101的处理说明(图14)中的数据A或者C中的某 一个。
这里，17次方运算部110X在子域GF ( (2A2) A2)上进行下面的计
30算，生成输出数据Y。
Y=1100 (二进制数)X (X0A2) +X1X (X0+X1) in GF ( (2、) A2) 在GF ( (2A2) A2)上的加法运算是对每位的按位加运算(按位加部
110a、 110e)。关于GF ( (2、) A2)上的乘法运算(4位乘法部110b、
110c、 110d)的详细内容，将在后面加以说明。 <4位校正项计算部111>
图16是表示4位校正项计算部111的结构的框图。
4位校正项计算部111 (图14、图16)具备4位乘法部111a (图19)、 4位乘法部111b (图19)以及按位加部lllc。
然后，4位校正项计算部111对输入数据XO (4位)、XI (4位)、 R0 (4位)、Rl (4位)进行4位校正项计算处理，生成输出数据B (4 位)。这里的输入数据XO、 XI、 R0、 Rl分别相当于随机化8位逆元计算 部IOI的处理说明(图14)中的数据XO、 XI、 R0、 Rl，输出数据B相当 于随机化8位逆元计算部101的处理说明(图14)中的数据B。
这里，4位校正项计算部111在子域GF ( (2A2) A2)上进行下面的计 算，输出数据B。
B=X0XR1+X1XR0 in GF ( (2、)、)
然后，这里，在GF ( (2A2) A2)上的加法运算是对每个位的按位加 运算(按位加部lllc)。关于GF ( (2A2) A2)上的乘法运算(4位乘法 部llla、 111b)的详细内容，将在后面加以说明(图19)。
<16次方计算部115、 117>
图17是表示16次方计算部115X (16次方计算部115 (图4) 、 16 次方计算部117 (图14))的结构的框图。
而且，16次方计算部115X对输入数据X(8位)进行合成域GF(((2A2) A2) A2)上的16次方计算，将其计算结果作为Y (8位)输出。此时，对 输入数据X进行了合成域GF ( ( (2、) A2) A2)上的16次方计算的结果 成为Y。
Y=XA (16) inGF ( ( (2、) A2)、)
此外，这里的输入数据X相当于随机化8位逆元计算部101的处理说 明(图M)中的数据X或R中的某一个，输出数据Y相当于随机化8位 逆元计算部101的处理说明(图14)中的数据F或H中的某一个。这里，16次方计算部115、 117将输入数据X从高位开始按每4位进 行分割，分割成X0、 XI，然后在GF ( (2A2) A2)上进行下面的计算，求 得Y0、 Yl。
Y0=X0
Y1=X0+X1 inGF ( (2、)、)
然后，这里，GF ( (2A2) A2)上的加法运算是对每个位的按位加运算 (按位加部115a) 。 16次方计算部115X将这样求得的Y0、 Yl依照该顺 序结合成8位数据Y。该Y成为16次方计算部115、 117的输出数据。 <4位输出计算部118、 119>
图18是表示4位输出计算部118X (4位输出计算部118X (图14)、 4位输出计算部119 (图14))的结构的框图。
4位输出计算部118X具备4位乘法部118a(图19)、4位乘法部118b (图19) 、 4位乘法部118d (图19)、按位加部118c、按位加部118e。
然后，4位输出计算部118X对输入数据E (4位)、G (4位)、F (4 位)、H (4位)进行4位输出计算处理，输出输出数据Y。这里的输入数 据E、 G、 F、 H分别和随机化8位逆元计算部101的处理说明(图14)中 向4位输出计算部118输入的输入数据E、 G、 FO、 HO相对应，此外，分 别和向4位输出计算部119输入的输入数据E、 G、 Fl、 Hl相对应。此外， 输出数据Y和随机化8位逆元计算部101的处理说明(图14)中4位输 出计算部118的输出数据YO相对应，和4位输出计算部119的输出数据 Yl相对应。4位输出计算部118、 119在GF ( (2A2)、)上进行下面的计 算，求得Y，并输出所求得的Y。
Y=EXF+GXF+EXH in GF ( (2l) A2)
这里，在GF ( (2A2) A2)上的加法运算是对每个位的按位加运算(按 位加部118c、 118e)。关于GF ( (2、) A2)上的乘法运算(4位乘法部 118a、 118b、 118d)的详细内容，将在后面加以说明(图19)。
接着，对前面说明的各种处理中用到的各个4位乘法部的详细内容， 即图15所示的4位乘法部110b及4位乘法部110c、图16示出的4位乘 法部111a及4位乘法部lllb、图18示出的4位乘法部118a、 4位乘法部 118b及4位乘法部118d的详细内容进行说明。另夕卜，图30中示出的8位 逆元计算部171具备的4位乘法部171d和4位乘法部171e也相同。另外，这里，这些4位乘法部171d等都具有的图30所示的8位逆元计算部171 是图29示出的随机数更新部17 (参照图14)的一部分。 <4位乘法部20>
图19是表示4位乘法部20的结构的框图。
前面说明的各种处理中用到的、上述列举的4位乘法部的结构都和这 里说明了 4位乘法部20相同。另外，和这一点相同的是，上述的4位输 出计算部118、 4位输出计算部119的任一个的结构都和图18中示出的4 位输出计算部118X相同。
4位乘法部20具备2位乘法部200 (图19) 、 2位乘法部201 (图 19) 、 2位乘法部202 (图19) 、 2位乘法部203 (图19) 、 2位乘法部 206 (图19)、按位加部204、按位加部205、及按位加部207。
而且，4位乘法部20对输入数据X(4位)、Y(4位)进行在GF( (2A2) A2)上的乘法运算，输出乘法运算结果Z (4位)。此时，
Z=XXY in GF ( (2、)八2)
然后，4位乘法部20将输入数据X、 Y分别从高位开始按每2位分割， 分割成XO (2位)、XI (2位)、及YO (2位)、Yl (2位)。然后，在 GF (2、)上执行下面的计算式，求得ZO、 Zl。 ZO=XOXY1+X1XYO+XOXYO in GF (2、) Z140(二进制数)XX0XY0+X1XY1 in GF (2、) 然后，4位乘法部20将对上述Z0、 Zl从高位开始按该顺序连结而成 的4位数据Z，作为4位乘法部20的输出来输出。
这里，GF (2A2)上的加法运算是对每个位的按位加运算(按位加部 204、 205、 207)。关于GF (2'2)上的乘法运算(2位乘法部200、 201、 202、 203、 206:图19)的详细内容，将在下面加以说明。 <2位乘法部21>
图20是表示2位乘法部21的结构的框图。
前面说明的各种处理中用到的2位乘法部的结构都和这里说明的2位 乘法部20相同。另外，.图21的2位乘法部143及2位乘法部144、图 24的2位乘法部150b、 2位乘法部150c及2位乘法部150d、图25的2 位乘法部151a及2位乘法部151b、图27的2位乘法部158a、 2位乘法部 158b及2位乘法部158d都具有和该图20示出的2位乘法部21相同的结
33构。
2位乘法部21具备逻辑积部210、逻辑积部211、逻辑积部212、逻辑积部213、按位加部214、按位加部215、按位加部216。
然后，2位乘法部21对输入数据X (2位)、Y (2位)进行GF (2、)上的乘法运算，输出乘法运算结果Z (2位)。此时
Z=XXY inGF (2'2)
然后，2位乘法部21将输入数据X、 Y分别从高位开始按每1位进行分割，分割成X0 (1位)、XI (1位)、Y0 (1位)以及Yl (1位)。而且，2位乘法部21在GF (2)上执行下面的计算式，求得Z0、 Zl。
Z0=X0XY1+X1XY0+X0XY0 in GF (2)
Z1=X0XY0+X1XY1 in GF (2)
而且，2位乘法部21将上述的Z0、 Zl从高位开始按该顺序连结，将连结的2位数据Z作为2位乘法部21的输出来输出。
这里，GF (2)上的加法运算是对每个位的按位加运算(按位加部214、215、 216) 。 GF (2)上的乘法运算是逻辑积(逻辑积部210、—211 、 212、213)。
然后，对随机化8位逆元计算部101 (图14)中用到的4位逆元计算部116的详细内容进行说明。<4位逆元计算部116>
图21是表示4位逆元计算部116 (图14)的结构的框图。另外，图30的4位逆元计算部171c也和这个4位逆元计算部117相同。
4位逆元计算部116具备5次方计算部(图24) 、 2位逆元计算部142(图22) 、 2位乘法部143 (图20) 、 2位乘法部144 (图20)以及按位加部140。
而且，4位逆元计算部116对输入数据X (4位)进行在GF ( (2A2)A2)上的逆元计算，生成作为计算结果的输出数据Y (4位)。此时，Y=XA ( — l)in GF ( (2A2) A2)
这里的输入数据X与在随机化8位逆元计算部101的处理说明(图14)中向4位逆元计算部116输入的输入数据C相对应，输出数据Y与在随机化8位逆元计算部101的处理说明(图14)中4位逆元计算部116的输出数据G相对应。4位逆元计算部116进行下面的处理。(1) 首先，4位逆元计算部116将输入数据X从高位开始按每2位进行分割，分割成XO、 XI。而且，4位逆元计算部116将分割后的X0输入到按位加部140、 5次方计算部141、 2位乘法部143。此外，4位逆元计算部116将分割的其他X1输入到按位加部140、 5次方乘法部141。
(2) 5次方计算部141对输入的XO、 XI进行GF ( (2A2) A2)上的5次方计算，求得其结果A (2位)。这里，对数据X (4位)在GF ( (2A2)A2)上进行了 5次方运算的结果成为A，所述数据X (4位)是把XO、 XI按该顺序结合而成的。艮P:
A=XA5 in GF ( (2、)八2)
此外，通过AA3=XA15=1 in GF ( (2、) 、) ， A的位数是3， A也是GF (2A2)上的元素。因此，A变成2位数据。关于5次方计算部141的详细内容，将在后面加以说明。
(3) 然后，图21的4位逆元计算部116具有的2位逆元计算部142对5次方计算部141在上述(2)中所求得的上述A (2位)进行GF (2、)上的逆元计算，生成数据B (2位)并输出。此时，
B=AA ( — l) in GF (2A2)
关于2位逆元计算部142的详细内容，将在后面加以说明(图22)。
(4) 然后，基于以上的计算结果，图21的4位逆元计算部116具有的2位乘法部143、2位乘法部144根据由2位逆元计算部142在上述(3)生成的上述B (2位)及在上述(1)分割得到的XO、 XI，分别通过下面的计算求得YO (2位)、Yl (2位)。
YO=XOXB in GF (2、)
Yl= (X0+X1) XB in GF (2、)
而且，4位逆元计算部116将4位数据Y作为4位逆元计算部116的输出来输出，该4位数据Y是把上述求得的YO、 Yl从高位开始按该顺序连结而成的。
这里，GF (2A2)上的加法运算是对每个位的按位加运算(按位加运算部140) 。 GF (2A2)上的乘法运算(2位乘法部143、 144)的详细内容和前面的说明相同(图20的2位乘法部21)。
接着，利用这样的图21的4位逆元计算部116 (图21)对2位逆元计算部142的详细内容进行说明。<2位逆元计算部142>
图22是表示2位逆元计算部142的结构的框图。2位逆元计算部142具有按位加部142a。
而且，2位逆元计算部142对输入数据X (2位)进行GF (2A2)上的逆元计算，将计算结果作为Y (2位)来输出。此时，Y=XA ( — 1) in GF (2A2)
2位逆元计算部142将X的高位1位、低位1位分别分割为X0、 XI，通过下面的计算式，求得Y0、 Yl。Y0=X0Y1=X1+X0
然后，将Y0、 Y1依照该顺序结合而成的2位数据Y作为输出。然后，对在随机化8位逆元计算部101 (图14)的内部使用的随机化4位逆元计算部114的详细内容进行说明。<随机化4位逆元计算部114>
图23是表示随机化4位逆元计算部114 (图14)的结构的框图。随机化4位逆元计算部114 (图14、图23)具备5次方计算部150 (图24) 、 5次方计算部152 (图24) 、 2位校正项计算部151 (图25) 、 4次方计算部155 (图26) 、 4次方计算部157 (图26) 、 2位输出计算部158(图27) 、 2位输出计算部159 (图27)、随机化2位逆元计算部154 (图28) 、 2位逆元计算部156以及按位加部153。
而且，随机化4位逆元计算部114是如下的处理利用随机数R (4位)对输入数据X (4位)进行随机化4位逆元计算处理，生成输出数据Y (4位)。这里的输入数据X相当于随机化8位逆元计算部101的说明(图14)中的向随机化4位逆元计算部114输入的输入数据D，随机数R相当于C。此外，输出数据Y相当于E。随机化4位逆元计算部114在GF ( (2、)、)上进行与随机化8位逆元计算部101同样的计算处理。但是，在随机化8位逆元计算部101中，虽然将17次方计算部112的输出数据C还输入到随机化4位逆元计算部114，但是随机化4位逆元计算部114不将其输出C输入到随机化2位逆元计算部154。此外，输入到各个处理部的数据的数据大小、乘方运算时的指数等不同。除去上述的内容，由于其处理过程和随机化8位逆元计算部101相同，这里就不做详细说明。
36另外，随机化4位逆元计算部114的处理是如下的处理对用屏蔽值
R进行了屏蔽的输入数据X=M ( + ) R进行合成域GF ( (2A2) A2)上的逆元计算，生成用屏蔽值R^ (_1)屏蔽了的处理结果Y=XA ( — l) ( + )RA ( — 1)。此时，XA ( — l)是X在GF ( (2A2) A2)中的逆元，屏蔽值RA ( — 1)是R在GF ( (2A2) A2)中的逆元。<5次方计算部141、 150、 152>
图24是表示5次方计算部141X (5次方计算部141 (图21) 、 5次方计算部150 (图23) 、 5次方计算部152 (图23))的结构的框图。
5次方计算部141X具备2位乘法部150b、 2位乘法部150c、 2位乘法部150d、按位加部150a、按位加部150e。这里，2位乘法部150b、 2位乘法部150c、及2位乘法部150d的结构分别和图20中示出的2位乘法部21相同。
而且，5次方计算部141X (5次方计算部141、 150、 152)对输入数据XO (2位)、XI (2位)进行GF ( (2A2) A2)上的5次方计算处理，输出输出数据Y (2位)。这里的输入数据X0、X1相当于4位逆元计算部116的说明(图21)中的XO、 XI，相当于随机化4位逆元计算部114的说明(图23)中的XO、 X1及R0、 Rl。此外，输出数据Y相当于4位逆元计算部116的说明(图21)中的A，相当于随机化4位逆元计算部114的说明(图23)中的A及C。
此外，在将输入数据XO、 X1依照该顺序结合的4位数据作为X时，输出数据Y如下所示。
Y=XA5 in GF ( (2、) "2)
这里，由于丫、= XA15=1 in GF ( (2A2) A2) ， Y的位数是3， Y是GF (2A2)上的元素。因此，Y成为2位的数据。
另外，由于5次方计算部141X (5次方计算部141 (图21) 、 5次方计算部150 (图23) 、 5次方计算部152 (图23))的处理流程和己经说明的17次方计算部IIOX(图15、 17次方计算部110、 17次方计算部112)基本相同，因此省略其详细说明。此外，按位加部150a、 150e、 110e(图24)是对每个位的按位加运算，2位乘法部150b、 2位乘法部150c、 2位乘法部150d (图24)的处理和已经说明的2位乘法部21 (图20)相同。
<2位校正项计算部151>图25是表示2位校正项计算部151 (图23)的结构的框图。
2位校正项计算部151具备2位乘法部151a(图20)、2位乘法部151b(图20)和按位加部151c。
而且，2位校正项计算部151对输入数据XO (2位)、XI (2位)、RO (2位)、Rl (2位)进行在GF ( (2A2) 1)上的校正项计算处理，输出输出数据B (2位)。.这里的输入数据XO、 XI、 RO、 Rl相当于随机化4位逆元计算部114的说明(图23)中的XO、 XI、 RO、 Rl。
这里，由于2位校正项计算部151的处理流程和已经说明的4位校正项计算部111 (图16)基本相同，因此省略详细说明。此外，按位加部151c是对每个位的按位加运算，2位乘法部151a、 151b的处理和己经说明的2位乘法部21 (图21)相同。
<4次方计算部155、 157>
图26是表示4次方计算部155X (4次方计算部155、 4次方计算部157:图23)的结构的框图。
4次方计算部155X具备按位加部155a。
而且，4次方计算部155X对输入数据X(4位)进行合成域GF( (2A2)A2)上的4次方运算，将其计算结果作为Y (4位)输出。此时，对输入数据X进行合成域GF ( (2A2) A2)上的4次方计算的结果成为Y。艮P，
Y=XA4 in GF ( (2、) A2)
此外，这里的输入数据X相当于随机化4位逆元计算部114的处理说明(图23)中的数据X或R中的某一个。输出数据Y相当于随机化4位逆元计算部114的处理说明(图23)中的数据F或H中的某一个。
而且，4次方计算部155X将输入数据X从高位开始按每2位进行分割，分割成XO、 Xl之后，并在GF (2、)上进行下面的计算，求得YO、Yl。
YO=XO
Y1=X0+X1 in GF (2"2)
这里的GF (2A2)上的加法运算是对每个位的按位加运算(按位加部155a)。而且，4次方计算部155X将求得的YO、 Yl按该顺序结合来作成8位数据Y。该Y就是4次方计算部155、 157的输出数据。
<2位输出计算部158、 159>图27是表示2位输出计算部158X (2位输出计算部158、 2位输出计算部159:图23)的结构的框图。
2位输出计算部158X具备2位乘法部158a(图20) 、 2位乘法部158b(图20) 、 2位乘法部158d (图20)、按位加部158c及按位加部158e。
而且，2位输出计算部158X利用上述的各部分对输入数据E(2位)、G (2位)、F (2位)、H (2位)进行2位输出计算处理，输出输出数据Y。这里的输入数据E、 G、 F、 H，分别与在随机化4位逆元计算部114的处理说明(图23)中向2位输出计算部158输入的输入数据E、 G、 F0、H0对应，此外，分别与向2位输出计算部159输入的输入数据E、 G、 Fl、Hl对应。此外，输出数据Y与在随机化4位逆元计算部114的处理说明(图23)中的2位输出计算部158的输出数据Y0对应，此外，与2位输出计算部159的输出数据Y1对应。2位输出计算部158X在GF (2、)上进行下面的计算，求得Y，并输出Y。
Y=EXF+GXF+EXH in GF (2、)
这里，GF (2、)上的加法运算是对每个位的按位加运算(按位加部158c、 158e) 。 GF (2、)上的乘法运算(2位乘法部158a、 2位乘法部158b、2位乘法部158d)和己经说明的2位乘法部21 (图23)相同。
<随机化2位逆元计算部154>
图28是表示随机化2位逆元计算部154的结构的框图。随机化2位逆元计算部154具备按位加部154c。
而且，随机化2位逆元计算部154是进行如下的处理利用上述按位加部154c对输入数据X (2位)进行随机化2位逆元计算处理，生成输出数据Y(2位)。这里的输入数据X相当于随机化4位逆元计算部114的说明(图23)中向随机化2位逆元计算部154 (图23、图28)输入的输入数据D。此外，输出数据Y相当于E。随机化2位逆元计算部154将X的高位1位作为XO，低位1位作为XI，通过下面的计算式，计算YO、Yl。<formula>formula see original document page 39</formula>
这里，GF (2A2)上的加法运算是按位加运算(按位加运算部154c)。而且，输出把YO、 Yl从高位开始依次按该顺序结合的数据Y (2位)。另外，随机化2位逆元计算部154的处理是如下的处理对用屏蔽值
R进行了屏蔽的输入数据X=M ( + ) R进行合成域GF (2A2)上的逆元计算，生成用屏蔽值R ( — l)屏蔽了的处理结果Y=XA ( —1) (+)RA(_1)。此时，XA (—l)是GF (2A2)上的X的逆元，屏蔽但R: ( — 1)是R在GF (2A2)上的逆元。
接着，对在加密部la的内部使用的随机数更新部17 (图9)的详细内容进行说明。如前所述，随机数更新部17 (图9)对随机数暂时存储部16 (图9、图38)中存储的随机数进行更新。
<随机数更新部17>
图29是表示随机数更新部17的结构的框图。
随机数更新部17具备合成域变换部170、 8位逆元计算部171及扩张域变换兼矩阵变换部172。
而且，随机数更新部17对输入随机数X (8位)进行随机数更新处理，将更新随机数Y (8位)作为输出数据输出。这里的输入数据X与在加密部la的说明(图9)中随机数更新部17的输入随机数Rn (8位)相对应，输出数据Y与在加密部la的说明中随机数更新部17的输出随机数Rn+l(8位)相对应。随机数更新部17进行下面的处理。
(1) 首先，合成域变换部170将输入数据X从高位开始按每1位进行分割，分割出X7、 X6、…、X0，进行前述的数学式1的矩阵计算，求得A7、 A6、…、A0。并且，合成域变换部170将A7、 A6、…、A0从高位开始按该顺序连结的8位数据作为A。
(2) 而且，接着，8位逆元计算部171对在上述(1)中生成的上述A进行在GF ( ( (2、) A2)、)上的逆元计算处理，求得B (8位)。此时，
B=AA ( — 1) inGF ( ( (2八2) '2) '2)
关于GF ( ( (2A2) A2) A2)上的逆元计算处理的详细内容，将在后面加以说明。
(3) 而且，扩张域变换兼矩阵变换部172将在上述(2)中计算出的B从高位开始按每1位进行分割，分割成B7、 B6、…、B0，进行上述数学式2中的矩阵计算，求得Y7、 Y6、…、Y0。
而且，扩张域变换兼矩阵变换部172将通过上述处理求得的Y7、
40Y6、…、Y0按照该顺序连结成的8位数据作为Y，作为随机数更新部17的输出数据进行输出。
接着，对随机数更新部17中用到的8位逆元计算部171的详细内容进行说明。
<8位逆元计算部171〉
图30是表示8位逆元计算部171 (图29)的结构的框图。
8位逆元计算部171(图30、图29)具备17次方计算部171b(图15)、4位逆元计算部171c (图21) 、 4位乘法部171d (图19) 、 4位乘法部171e (图19)及按位加部171a。
然后，8位逆元计算部171对输入数据X (8位)进行GF ( ( (2A2)A2)、)上的逆元计算，生成计算结果即输出数据Y (8位)。此时，
Y=XA ( — 1) inGF ( ( (2A2) A2) A2)
这里的输入数据X与在随机数更新部17的处理说明(图29)中向8位逆元计算部171输入的输入A相对应，输出数据Y与8位逆元计算部171的输出数据B相对应。8位逆元计算部171进行下面的处理。
(1) 8位逆元计算部171将输入数据X从高位开始按每4位进行分割，分割为XO、 XI。然后，8位逆元计算部171将分割的X0输入按位加部171a、 17次方计算部171b、 4位乘法部171d。此外，8位逆元计算部171将分割的XI输入到按位加部171a、 17次方计算部171b。
(2) 然后，17次方计算部171b对输入到该17次方计算部171b的XO、 X1进行GF ( ( (2、) A2) A2)上的17次方计算，求得其结果A (4位)。这里，对将XO、 XI依照该顺序结合而成的数据X (8位)进行了GF ( ( (2A2) A2) A2)上的17次方运算的结果，成为A。艮P
A=XA17 in GF ( ( (2八2) A2) A2)
此外，根据八、5= XA255=1 in GF ( ( (2、) A2) A2) ， A的位数是15，因此A是GF ( (2A2) 1)上的元素。因此，A成为4位数据。有关17次方计算部171b的详细内容，和已经说明的17次方计算部110X(17次方计算部110 (图16) 、 17次方计算部112 (图16):图15)相同。
(3) 接着，4位逆元计算部171c (图30)对上述(2)中生成的上述A (4位)进行GF ( (2A2) A2)上的逆元计算，生成数据B (4位)，并输出。此时，B=AA ( — 1) inGF ( (2A2) A2)
4位逆元计算部171c的详细内容和已经说明的4位逆元计算部116(图21)相同。
(4)然后，8位逆元计算部171根据在上述(3)中生成的上述B (4位)及在上述(1)中分割的X0、 XI，经过下面的计算，分别通过4位乘法部171d、 4位乘法部171e，求得下面的Y0 (4位)、Yl (4位)。
Y0=X0XB in GF ( (2、) A2)
Yl= (X0+X1) XB in GF ( (2"2)、)
然后，8位逆元计算部171将上述YO、 Yl从高位开始按该顺序连结而成的S位数据Y作为该8位逆元计算部171的输出来输出。
GF ( (2A2) A2)上的加法运算是对每个位的按位加运算(按位加部171a) 。 GF ( (2A2) 1)上的乘法运算(4位乘法部171d、 171e)的详细内容跟前面己经说明的相同(图19的4位乘法部20)。
以上，说明了加密装置1的全部详细动作。
接着，对随机化S—boxl20a 120p(图13)保持与AES加密的S—box之间的兼容性、以及处理过程中的数据被屏蔽的情况加以说明。<随机化8位逆元计算部101的原理〉
随机化8位逆元计算部101 (图14)将合成域GF ( ( (2、) A2)、)上的元素X二M+R (图38中ID8t:Tl (V8t) +T1 (Rt) 、 M=T1 (V8t)、R=T1 (Rt))作为输入，输出Y=MA( —1) + R ( — l)(图38中的OD8t=Tl(V8t) A ( — l) +T1 (Rt) A ( — 1))。这里，MA ( — 1) 、 RA ( — 1)分别表示M、 R的在GF ( ( (2A2) A2)、)中的逆元。下面，对此进行说明。
17次方计算部110 (图14、图15)的输出值A利用扩张域的性质等，变成如下形式。A=XA17
=(M+R) 、7
=(M+R) X (M+R) 、6
=(M+R) X (MA16+RA16)
=Mfl 7+Ra1 7+MAl 6 X R+M X R、 6这里，由于GF ( ( (2A2) A2) A2)是将GF ( (2、) A2)用不可约多
42项式xA2+x+1100 (二进制数)进行2次展开的，所以如果把a作为xA2+x+1100 (二进制数)的根，则M、 R就能够表示为如下。
M: M0X a +M1
R: R0X a +R1
此时，如果使用扩张域的性质等，则能够如下计算出MA16XR+MXR、6。
(MOX a+M1) A16X (RO X a+R1 ) + (MO X a+M1 ) X (ROXa+R1) 、6
={MOX a + (M0+M1) }X (ROX a +R1 ) + (MOX a +M1) X {ROXa + (R0+R1) }
=(MO+RO) XR1+ (Ml+Rl) XRO
这与在图14的随机化8位逆元计算部101的处理中的X0XR1+X1XRO相等。因此，能够表示为
A=MA17+RA17+X0XR1+X1 XRO
但是，由于4位校正项计算部111 (图14、图16)计算B:X0XR1+X1XRO，结果，向随机化4位逆元计算部114 (图14、图23)输入的输入数据D是
D=A+B=MA17+RA17
随机化4位逆元计算部114如后面所述进行如下处理对于输入D=MA17+RA17、 C=RA17，输出输出E二M" ( — 17) +RA ( — 17)。此时，4位输出计算部118、 119相当于分别分为高位4位和低位4位来进行以下的计算。
Y=EXF+GXF+HXE={MA ( — 17) +RA ( — 17) }X (M+R) 、6+RA ( — 17) X (M+R)A16+RA16X{MA ( — 17) +RA ( — 17) }
计算上述的数学式，则Y^Nf (_1) +RA ( — l)，可知随机化8位逆元计算部101进行将X二M+R变换为Y=MA ( — l) +RA ( — 的处理。
然后，作为这样地将X^M+R变换为Y=MA ( — l) +RA ( — l)的随机化8位逆元计算部101的一部分的随机化4位逆元计算部114 (图14、图23)，由于在GF ( (2A2) A2)上进行和上述同等的处理，因此和上述一
43样的说明也成立。因此，可知对于输入D= MA17+RA17和C=RA17的输入， 输出E= MA ( — 17) +R ( — 17)。进一步，对于随机化4位逆元计算部 114也是同样的，这一点可通过对X、 R的全部的值的组合实际进行计算 来确定。
通过以上的处理，说明了随机化8位逆元计算部101进行如下的处理 将合成域GF ( ( (2A2) A2) A2)上的元素X二M+R变换为Y=MA ( — l) +RA (—1)。
<随机化S—boxl20a 120p的动作原理>
接着，对随机化S — boxl20a 120p (图13、图12)的动作原理进行说 明。在图13中，若设X二M+R (图38中IC8t=V8t+Rt， M=V8t， R=Rt)， 则合成域变换部100的输出就变为A=T (X) =T (M) +T (R)(图38中 的ID8t=Tl (V8t) +T1 (Rt))。这里，T (X)(图38中的Tl)是将 GF (2A8)上的元素变换成合成域GF ( ( (2A2)、)、)上的元素的结果。 同样地，其他的合成域变换部103将R (图38中的Rt)变换成S=T (R) (图38中的RDt二Tl (Rt))。
然后，如先前的说明，随机化8位逆元计算部101根据A=T (M) +T (R) 、 S=T (R)的输入，生成B:T (M) A ( — 1) +T (R) A ( — 1)(图 38中的OD8戶Tl (V8t) A ( — l) +T1 (Rt) ( — l))。然后，扩张域变 换兼矩阵变换部102 (图13)在将合成域GF ( ( (2A2) A2) A2)上的元素 变换为GF (2A2)上的元素后，将进行了 AES加密的S — box中定义的仿 射变换中的仅矩阵运算部分的结果进行输出。即，C二Mat (MA ( — ) +Mat (RA (_1))被输出(图38中的Mat (V8f ( — 1) ) +Mat (Rf (— 1)))。
这里，Mat (X)是表示对X进行上述矩阵运算即AES加密的S—box 中定义的仿射变换中的矩阵运算的结果。然后，按位加部104 (图13)将 输入的上述C和常数01100011 (二进制数)进行GF (2A8)上的加法运算， 该常数由AES加密的S — box定义的仿射变换来定义的常数加法运算中的 常数。即，按位加部104的输出结果Y成为Y= {Mat (Nf ( — l)) +01100011}+Mat(RA( — 0)(图38中的Mat(V8f( — 1 ) )+01100011+Mat (RtA ( — l))。上式中的"部分即是对于M进行AES加密的S—box变 换的结果，能够表示为Y=S —box[M]+ Mat (R八(一l))(图38中的S—box[V8t]+Mat (RtA ( — l)))。这里的S—box[X]表示对X进行AES 加密的S—box变换的结果。 <加密装置1的动作原理>
接着，加密装置1对保持与AES加密算法之间的兼容性的情况加以说明。
首先，在图9中，明文数据P (128位)通过随机数R0 (8位)被屏 蔽。屏蔽处理部10的处理结果A成为A=P+ (R0， R0，…，R0)。接着， 根据AddRoundKey 11的处理结果变换为B=P+RK0+ (R0， R0，…，R0)。 这里，P+RK0是未屏蔽时的AddRoundKey的处理结果，如果把P+RK0设 为M，贝U B=M+ (R0， R0，…，R0)。接着，对于n=l 9，进行随机化 Round—nl2处理，对于此，参照图10进行说明。
在图10中，若把未屏蔽时的随机化Round—n12的输入值(即原值) 设为M，则输入X表示为X=M+(R0， R0，…，R0)。随机化SubBytes120 如图12所示，是由随机化S—box构成的处理。现在，如果将M从高位开 始按每8位进行分割，分割成M0、 Ml、…、M15，则
X= (M0、 Ml、…、M15) + (R0、 R0、…、R0)
这里，根据先前的随机化S—boxl20a 120p的动作原理说明，随机化 SubBytes120的输出Y表示为Y= (S —box岡，S—box[Ml]，…，S — box[M15]) + (Mat[R(f ( —1) ]， Mat[R(f ( — 1 )]，…，Mat[R(T ( — 1 )])。 即，
Y= SubBytes (M) + (Mat[RCT ( — 1 ) ]， Mat[R0A ( — 1) ]， ...， Mat[R(T (一l)])
艮口，随机化SubBytes120的输出数据是用(Mat[R(f ( — 1) ]， Mat[R(T (—1)]，…，Mat[R(T( —1)])进行了屏蔽的数据。接着，关于ShiftRows121 的输出、MixColumnl22的输出，则可知都通过直接执行AES加密算法标 准中规定的ShiftRows处理、MixColumn处理，能够得到用(Mat[R(T( — 1) ]， Mat[R(T ( — 1)〗，…，Mat[R(f ( — 1)])屏蔽了的ShiftRows处理 结果、MixColumn处理结果。因此，如果随机化Round—n12处理的输入值 己用R进行了屏蔽，则其输出值以用Mat[R(T ( —1)]屏蔽了的状态输出。 因此，作为Rh Mat[R(T ( — l)]，如果执行『1的随机化Round—nl2处 理，则用Rl屏蔽了的状态下的输入数据则输出用R2= Mat[RlA ( — l)]屏蔽了的状态的输出数据。另外，Mat[RCT (—l) ]、 Mat[RlA ( — l)]的 处理是图29的随机数更新部处理。如果反复进行以上的直到随机化 Round—10 13的处理，则作为随机化Round—10 13 (图9、图11)的输出数 据，输出用Rl一Mat[R10八(一1)]对密文C进行了屏蔽的状态的数据， 所述密文C是对明文P进行了 AES加密处理的结果。因此，在中断屏蔽 部14中，通过用R11进行按位加处理来得到密文C (图9)。
此外，从前面的动作原理的说明也可知，加密处理过程的中间数据始 终被用根据随机数R0或R0通过规定的运算算出的值实施了屏蔽。因此， 通过电力分析攻击来对加密装置1进行密钥分析变得困难。
图38是表示加密装置1及加密装置1具有的部分之间的包含关系、 它们的整体、部分之间的输入输出数据的图。参照图38，整理上述说明中 所示的它们的包含关系及输入输出数据。
加密部la(图9、图31)被输入明文U，输出密文C。
这里，图38所示的Vt (t=l~ll)的标记是对明文U实施了直到轮t 为止的处理的中间数据。加密部la通过直到轮(t一l)为止的处理，生成 将该Vt用随机数Rt进行了屏蔽的随机化输出数据OAt=Vt+{Rt, Rt，…， Rt}。
随机数暂时存储部16 (图9)将随机数RO提供给屏蔽处理部10，将 随机数Rl 随机数R10提供给具有随机化8位逆元计算部101的随机化S 一boxl21X，将随机数Rll提供给中断屏蔽处理部14。
随机化Round一tl2X (图9、图10、图11)在各轮处理中，分别被输 AlAt=Vt+{Rt， Rt，…，Rt}(图9中的B或D、图10及图11中的X) 和随机数Rt (图9的Rn、图10的Rn、图11的R10)，将对所输入的IAt 表示的作为原值的中间值Vt进行了第t轮处理后的中间数据V (t+l)， 用随机数R(t+l)进行屏蔽而得到OAt^V(t+l)+(R(t+l) ， R(t+1)，…， R (t+l) }，并输出该得到的OAt。这里，随机化输出数据OAt的去除了 屏蔽值的影响的原值是被实施了第t轮处理的上述中间数据V。
随机化SubBytesl20X (图10、图11、图12)被输入作为向随机化 Round—tl2X输入的输入数据IAt的IB，IAt:Vt+(Rt， Rt，…，Rt }(图10 及图11的X、图12的X)及随机数Rt (图12的R、图10的Rn、图11 的R10)，输出被实施了第t轮SubBytes处理的OBt-S—Box( Vt)+{ R(t十1)，R(t+1)，…，R(t+1)}(图10及图11的A、图12的Y)。
随机化S—Boxl21X (图12、图13)中被输入向随机化SubBytes输 入的输入数据IBt被分割的8位IC8t=IB8t=V8t+Rt (图12所示的X[O]、 X[l]、、或X[15]中任一个、图13的X)及随机数Rt (图13的R、图 12的R)，输出对该8位进行了第t轮S—Box处理的OC8t=S—box (V8t) +R (t+l)(图12的Y[O]、 Y[l]、…、或Y[15]中任一个、图13的Y)。
然后，随机化8位逆元计算部101 (图13、图14)，设基于数学式l 的矩阵计算(参照合成域变换部100及合成域变换部103的说明)由标记 Tl表示，被输入基于输入到随机化S — box的上述IC8t的ID8t=Tl (IC8t) =T1 (V8t) +T1 (Rt)和基于随机数暂时存储部16的随机数Rt的RDt41 (Rt)(图13的S、图14的R)，根据这些输入把M+P运算为MA ( —1) +PA ( — 1)，并输出作为运算结果的OD8t二Tl(V8t)A (一l) +Tl(Rt)A (— 1)(图13的B、图14的Y)。
这里，随机化S — Boxl21X (图13、图12)基于该随机化8位逆元计 算部101的输出OD8t=Tl(V8t)A ( — l) +Tl(Rt)A ( — 1)(图13的B、图 14的Y)，利用扩张域变换兼矩阵变换部102和按位加部104进行计算， 求出OC8t:(Mat (V8tA ( — l) ) + Mat (Rf ( — l) ) }+01100011={ Mat (V8f ( — l) ) + 01100011}+ Mat (RtA ( — l) ) =S—box (V8t) + Mat (Rf ( — l) ) =S —box (V8t) +R (t+1)，并输出所求得的该OC8t (图 12的Y
、 Y[l]、…、或Y[15]中任一个、图13的Y)。
然后，随机化SubBytes 120X (图12、图10、图11)将由各个随机化 S—boxl20X (随机化S—boxl20a 随机化S—boxl20p)输出的该OC8t进 行连结，输出输出数据OBt=S—box(Vt)+{R(t+l) ， R(t+1)，…R(t+1) } (图10及图11的A，图12的Y)。
由此，随机化Round一tl2X根据输出的OBt，例如进行ShiftRows处理 等，计算OAt:V (t+1) +{R (t+l) ， R (t+l)，，…R (t+l) }，将计算 出的OAt作为随机化RoimdJ12X的下一轮及第t+l轮的随机化输入数据 IAt，输入到随机化Round—tl2X。
由此，在中断屏蔽处理部14中，经由t二10时的随机化Round一tl2X， 被输入OAt=OA10=Vll+{Rll， Rll，…，Rll}，此外，从随机数暂时存 储部16被输入随机数Rll (图9的E，图11的Y)，通过对被输入的该
47OA10=V11+{R11， Rll，…，Rll)用随机数Rll进行按位加运算，输出密 文OVll。
通过以上处理，利用密钥(RK0等)从明文U (图38)生成密文C (图 38)的加密装置1，其特征在于，具备随机数生成部15，生成随机数R0; 随机化输入数据生成部(屏蔽处理部10 (图9、图38、 AddRoundKeyll
(图9)、随机化Round—n12中的合成域变换部100 (图13)、扩张域变 换兼矩阵变换部102 (图13)、按位加部104 (图13))，接收上述明文 U，将根据上述随机数RO决定的预定的输入屏蔽值T1 (Rt)和对上述明 文U用上述密钥(RK0等)进行了预定的处理的输入数据T1 (V8t)相加， 生成随机化输入数据T1 (V8t) +T1 (Rt);随机化8位逆元计算部101， 接收由上述随机化输入数据生成部生成的上述随机化输入数据ID8t和上 述输入屏蔽值T1 (Rt) =RDt，将所接收的上述输入屏蔽值的在预定的第1 有限域中的逆元即输出屏蔽值T1 (Rt) A ( — 和上述输入数据T1 (V8t) 的在该第1有限域中的逆元T1 (V8t) A ( — l)相加，生成随机化输出数 据T1 (V8t) A ( — 1) +T1 (Rt) A ( — 1);输出部(随机化Round—10 13 中的扩张域变换兼矩阵变换部102 (图13)及按位加部104 (图13)、 ShiftRows131 (图11) 、 AddRoundKey 132 (图11)、中断屏蔽处理部14
(图9、图38))，接收上述随机化8位逆元计算部101生成的随机化输 出数据OD810 (t=10)，根据所接收的该随机化输出数据生成上述密文C。 而且，该加密装置l中，上述随机化8位逆元计算部101包括17次 方计算部110、 112 (图14)，对上述随机化输入数据ID8t (图14的X)、 上述输入屏蔽值(Tl (Rt)、图14的R)进行预定的第1指数(17次方) 的乘方运算，分别通过各乘方运算生成第1乘方随机化输入数据(图14 中的A)和第1乘方输入屏蔽值(图14的C) ; 4位校正项计算部111 (图 14、图16)，根据上述随机化输入数据(图14的X)和上述输入屏蔽值
(图14的R)，生成预定的校正数据(图14的B);按位加部U3 (图 14)，将生成的上述校正数据(图14的B)与计算出的上述第1乘方随机 化输入数据(图14的A)相加，生成副随机化输入数据(图14的D); 随机化4位逆元计算部114 (图14、图23)，接收上述副随机化输入数据
(图14的D)和上述第1乘方输入屏蔽值(图14的C)，将该第一乘方 输入屏蔽值(图14的C)的在第2有限域中的逆元即屏蔽值(CT ( —1))
48与上述副随机化输入数据(图14的D)的在上述第2有限域中的逆元即 输出数据(DA ( — 1))相加，生成随机化副输出数据(图14的E二DA (— 1) +CA ( — 1));其他部分，根据上述随机化副输出数据(图14的E)、 上述随机化输入数据(图14的X)、上述输入屏蔽值(图14的R)、上 述第1乘方输入屏蔽值(图14的C)来生成上述随机化输出数据(图14 的Y)。
而且，这里，"其他部分"包括16次方计算部115、 117 (图14、 图17),对上述随机化输入数据(图14的X)和上述输入屏蔽值(图14 的R)进行预定的第2指数(16次方)的乘方计算，通过各个乘方计算， 分别生成第2乘方随机化输入数据(图14的F)和第2乘方输入屏蔽值(图 14的H) ; 4位逆元计算部116 (图15、图21)，对上述第l乘方输入屏 蔽值(图14的C)进行在上述第2有限域上的逆元计算，生成上述第1 乘方输入屏蔽值(图14的C)的在上述第2有限域中的逆元即逆元乘方输 入屏蔽值(图14的G);其他部分(4位输出计算部118及4位输出计算 部119)，根据上述随机化副输出数据(图14的E)、上述第2乘方随机 化输入数据(图14的F)、上述第2乘方输入屏蔽值(图14的H)、上 述逆元乘方输入屏蔽值(图14的G)，生成上述随机化输出数据(图14 的Y)。
此外，该加密装置1对上述明文U进行AES (Advanced Encryption Standard)加密的加密处理，生成AES加密的密文C，上述输入数据的逆 元T1 (V8t) A ( — l)是对上述输入数据T1 (V8t)进行了与AES加密的 Sbox表等价的逆元计算及仿射中的逆元计算而得的计算结果。
因此，根据该加密装置l，通过级数少的简单结构能够进行AES加密 方式的加密的逆元计算，进而能够进行AES加密的加密处理。
此外，该加密装置1进一步具备屏蔽值生成部(随机数更新部17及 合成域变换部103 (图9、图13、图29))，用于生成上述随机化8位逆 元计算部101使用的上述输入屏蔽值RDt。
由此，能够在加密装置l内生成输入屏蔽值，使系统的结构变简单。
而且，该加密装置1的上述屏蔽输入数据生成部具备第1部分(屏 蔽处理部10 (图38、图9) 、 AddRoundKeyll (图9)、合成域变换部100 (图13))，根据上述明文U，生成第1随机化输入数据ID8t=ID81=Tl(V81) +T1 (Rl);第2部分(扩张域变换兼矩阵变换部102 (图13)、 按位加部104 (图13)、随机化Round—n12中的S础Rowsl21 (图10)、 MixColumns122 (图10) 、 AddRoundKey123 (图10)、合成域变换部100)， 接收第(t一l)的随机化输出数据OD8 (t—l)，加上根据第(t一l)输 出屏蔽值RD (t—l) A ( — l) -T1 (Rt)决定的预定的第t输入屏蔽值Tl
(Rt) =T1 (Mat (RtA ( — l )))，生成第t随机化输入数据ID8t=Tl (V8t) +T1 (Rt) (2《t《J)。上述屏蔽值生成部根据所生成的上述随机数RO， 生成上述第1输入屏蔽值RD1 第J输入屏蔽值RDJ (J=10);随机化8 位逆元计算部101根据上述第1部分生成的上述第1随机化输入数据ID81 和所生成的上述第1输入屏蔽值RD1，生成上述第1随机化输出数据 OD81，并且，根据由上述第2部分生成的上述第t随机化输入数据ID8t(2 《t《J)和所生成的上述第t输入屏蔽值RDt，生成上述第t随机化输出数 据OD8t (2《t《J)。
另外，这里，该加密装置1中，上述第1部分(屏蔽处理部10 (图 38、图9) 、 AddRoundKeyll (图9)、合成域变换部100 (图13))从 上述屏蔽值生成部(随机数更新部17)，取得用于确定第1输入屏蔽值 RD1=T1 (Rl)的确定数据R0，根据所取得的确定数据RO和上述明文U， 生成已加上了上述第1输入屏蔽值RD^T1 (Rl)的上述第l随机化输入 数据ID8，ID8^T1 (V81) +T1 (Rl)。上述屏蔽值生成部(随机数更新 部17)生成用于确定上述第J的输出屏蔽值T1 (R10) A ( — l)的确定数 据Rll，上述输出部接收所生成的该确定数据Rll和第J随机化输出数据 OD8t，并根据这些数据生成上述密文C，该第J随机化输出数据OD8t是 加上了该确定数据Rll所确定的上述第J输出屏蔽值T1 (R10) A ( — l) 而得到的数据。
另外，上述屏蔽值生成部具备保持部(随机数暂时存储部16(图9))， 该保持部保持值，若生成上述随机数R0，则保持所生成的随机数R0;保 持控制部(随机数更新部17 (图9))，根据保持的随机数R (t—l)生 成随机数Rt，将生成的随机数Rt保持在上述保持部，上述随机数Rt用于 通过预定的计算算出上述第t输入屏蔽值；计算部(合成域变换部103 (图 13))，根据所保持的上述随机数Rt，分别通过上述计算算出上述第t输 入屏蔽值(t=l、 2、…、J)。由此，通过保持随机数Rt，能够根据所保持的随机数Rt，通过简单处 理算出第(t+l)的输入屏蔽值，能够通过简单处理算出各个输入屏蔽值。 另外，在请求范围内记载的"随机数生成部"例如可以解释为对应于
随机数生成部15、随机数暂时存储部16及随机数更新部17的整体。在这
样解释的情况下，请求范围内记载的"屏蔽值生成部"也可以理解为不对
应于上述随机数更新部17及合成域变换部103，只对应于合成域变换部 103。
另外，这样的加密装置1也可以具备分别设置了用于实现上述各部分 的电路的集成电路，该集成电路也可以使用这些各部分来发挥上述作用， 来执行上述方法。
<解密装置3>
对应于解密装置1的解密装置3的结构如图31 图37所示。这些处理 是加密装置1的处理的逆变换处理，由于基本的处理流程和加密装置1中 说明的内容相同，省略其详细说明。另外，在图36中的随机化InvS — Box331a 331p的合成域变换兼矩阵变换部300中，下面的矩阵运算式使用 数学式3
<formula>formula see original document page 51</formula>
同样的在图36中所示的扩张域变换部302中，下面的矩阵运算式使 用数学式4广 、 Y7广 i000，11、 0广 、 已7
Y6011〇1100B6
Y5000〇1110已5
Y411010010已4
Y3—01001010已3
Y2〇0101010已2
Y10010000B1
1001011:
由此，使用密钥根据密文生成明文的解密装置3，其特征在于，具备:
随机数生成部35 (图32)，生成随机数；输入部(屏蔽处理部30(图32)、 AddRoundKey31 (图32) 、 InvShiftRows320 (图33)、图36所示的按位 加部、随机化IiwRound_n32 (图32、图33)所具备的扩张域变换部302 (图36) 、 AddRoundKey322 (图33) 、 InvMixColumns323 (图33)、随 机化InvRound—0 33 (图34)所具备的InvShiftRows330 (图34))，接收 上述密文，将根据上述随机数决定的预定的输入屏蔽值和对上述密文根据 上述密钥进行了预定的处理的输入数据相加，生成随机化输入数据；8位 随机化合成域逆元计算部301 (图36)，接收由上述随机化输入数据生成 部生成的上述随机化数据和上述输入屏蔽值，将接收的上述输入屏蔽值的 在预定的第1有限域中的逆元即输出屏蔽值和上述输入数据的在该第1扩 张域中的逆元相加，生成随机化输出数据；输出部(具有随机化InvRound—0 33 (图32、图34)的扩张域变换部302 (图36) 、 AddRoundKey332 (图 34)、中断屏蔽处理部34 (图32))，接收由上述8位随机化合成域逆 元计算部301生成的上述随机化输出数据，根据所接收的该随机化输出数 据生成上述译文。
<最大逻辑级数的预估>
在以上说明的实施方式中，预估随机化8位逆元计算部101 (图14、 图13)的最大逻辑级数。预估在电路中实现随机化8位逆元计算部101时 的关键路径的最大逻辑级数如下
随机化8位逆元计算部101的关键路径在图14中如下所示
17次方计算部110=>按位加部113=>随机化4位逆元计算部114=>4
52位输出计算部118
而且，在该路径途中的4位输出计算部118的关键路径如下(图18):
4位乘法部118a-〉按位加部1180=>按位加部118e 此外，图14的路径的途中的随机化4位逆元计算部114的关键路径 如下(图23):
5次方计算部150=〉按位加部153=>随机化2位逆元计算部154=>2位 输出计算部158
而且，该图23中所示的2位输出计算部158的关键路径如下所示(图 27):
2位乘法部158a^〉按位加部1580=>按位加部158e 然后，前述的图23的路径的途中的随机化2位逆元计算部154的关 键路径如下所示(图28): 按位加部154c
通过上述过程，随机化8位逆元计算部101 (图14)的最大逻辑级数 成为连续处理下面的处理时的逻辑级数。 17次方计算X1次 5次方计算X1次 4位乘法X1次 2位乘法X1次 按位加运算X7次
另外，这里，上述"按位加运算X7次"中的7次是基于下面的计算 7=1+2+1+2+1的。即，与现有技术2的随机化8位逆元计算部81 (图l) 相比，能够削减ll次按位加运算，能实现最大逻辑级数的削减。■ (变形例)
另外，在本实施方式中，将作为电力分析攻击对策的对象的加密作为 AES加密，但不仅限于AES加密，只要是在加密处理中使用逆元运算， 或者，在加密处理中所使用的表变换处理是可基于逆元运算构成的加密方 式就可以使用。作为那样的加密方式，其他的有ISO/IEC 18033 — 3:2005,
"Information technology Security techniques-Encryption algorithms —
一Part3: Block ciphers"有(非专利文献3)中记载的Camellia加密。
此外，在上述实施方式中，即使作为软件来实现的情况下，由于没有
53必要将变换表作为排列来进行保持，所以与以往技术同样能够节约代码规 模，并且，相比以往技术，能够起到削减加密处理时间的效果。
此外，在上述实施方式中，说明了将全部的处理安装在运算电路中的 情况，也可以将其中的处理的一部分安装为变换表。例如，在随机化4位
逆元计算部114的情况下，作为由4位X16个的要素构成的排列Inv4[16;] 来安装，对于4位输入X，可以将4位输出作为Inv4[X]来输出。
另外，虽然基于上述实施方式说明了本发明，但本发明当然不限定于 上述实施方式。下面的情况也包含在本发明中。
(1) 上述各装置具体来说是由下述部件构成的计算机系统微处理 器、ROM、 RAM、硬盘单元、显示器单元、键盘、鼠标等。在上述RAM 或硬盘单元中，存储有计算机程序。通过上述微处理器按照上述计算机程 序来动作，各装置实现其功能。这里的计算机程序为了实现规定的功能， 组合多个表示对计算机的指令的命令代码来构成该计算机程序。
(2) 构成上述各装置的构成要素的一部分或者全部，也可以由一个 系统LSI (Large Scale Integration:大规模集成电路)构成。系统LSI是将 多个构成部集成到一个芯片上来制造出来的超多功能LSI。具体说来，是 含有微处理器、ROM、 RAM等来构成的计算机系统。在上述RAM中， 存储有计算机程序。通过上述微处理器按照上述计算机程序来动作，系统 LSI实现其功能。
(3) 构成上述各装置的构成要素的一部分或者全部也可以是由在各 装置上可装卸的IC卡或单体模块构成。上述IC卡或者上述模块是由微处 理器、ROM、 RAM等构成的计算机系统。上述IC卡或上述模块也可以包 含上述超多功能LSI。通过微处理器按照计算机程序进行动作，上述IC卡 或上述模块实现其功能。该IC卡或者该模块也可以具有防篡改性。
(4) 本发明也可以是上述所示的方法。此外，也可以是通过计算机 来实现这些方法的计算机程序，也可以是上述计算机程序构成的数字信 号。
此外，本发明也可以将上述计算机程序或者上述数字信号记录在能够 通过计算机读取的记录介质中，例如，软盘、硬盘、CD—ROM、 MO、 DVD、 DVD—ROM、 DVD—RAM、 BD (Blu—rayDisc，即蓝光盘)、半 导体存储器等。此外，也可以是存储在这些记录介质上的上述数字信号。此外，本发明也可以是将上述计算机程序或者上述数字信号经由电气 通信线路、无线或有线通信线路、以英特网为代表的网络、数据广播等进 行传送。
此外，本发明也可以是具备微处理器和存储器的计算机系统，上述存 储器存储上述计算机程序，上述微处理器按照上述计算机程序进行动作。
此外，也可以是通过将上述程序或上述数字信号记录在上述记录介质 中来进行转移，或者通过将上述程序或者上述数字信号经由上述网络等进 行转移，由独立的其他的计算机系统实施。
(5) 另外，上述屏蔽值生成部也可以在随机化8位逆元计算部101 (图14)根据随机化输入数据计算随机化输出数据的同时，并行地，在生
成该随机化8位逆元计算部101在该计算中使用的RDt之后，再生成该随 机化8位逆元计算部IOI所使用的RD (t+l)等。这样，随机化8位逆元 计算部101能够无延迟地利用该RD (t+l)等，使得加密装置1高速动作。
(6) 此外，也可以采用下面的方式。 也可以采用加密处理程序的方式，即，使用计算机基于密钥对明文进
行规定的加密处理来生成密文的加密处理程序，其特征在于，生成随机数， 接收随机化输入数据和输入屏蔽值，进行第1有限域上的逆元计算，并输 出随机化输出数据，.上述随机化输入数据是将输入屏蔽值和输出数据相加 来进行了屏蔽的值，上述随机化输出数据是将输出屏蔽值和输出数据相加 来进行了屏蔽的值，上述输入屏蔽值是根据上述随机数决定的值，上述输 出数据是上述输入数据的在上述第1有限域中的逆元，上述输出屏蔽值是 上述输入屏蔽值的在上述第l有限域中的逆元，使上述计算机进行信息处 理。
此外，也可以采用下面的方式。即，采用使用计算机来用密钥从明文 生成密文的计算机程序的方式，该计算机程序使计算机实现如下功能随 机数生成功能，生成随机数；随机化输入数据生成功能，接收上述明文， 把根据上述随机数决定的预定的输入屏蔽值和对上述明文根据上述密钥 进行了预定的处理的输入数据相加，生成随机化输入数据；第l随机化逆 元数据生成功能，接收由上述随机化输入数据生成功能生成的上述随机化 输入数据和上述输入屏蔽值，将接收到的上述输入屏蔽值的在预定的第1 有限域中的逆元即输出屏蔽值和该输入数据的在上述第1有限域中的逆元相加，生成随机化输出数据；输出数据处理功能，接收通过上述第1随机 化逆元数据生成功能生成的上述随机化输出数据，根据接收到的该随机化 输出数据生成上述密文。
另外，可以分别通过并列执行相互不同的处理的多处理等来执行这些 加密处理程序、计算机程，在该种情况下，该计算机程序在根据随机化输 入数据生成随机化输出数据的同时，使上述计算机并行地生成上述输入屏
(7)也可以分别组合上述实施方式及上述变形例。
工业实用性
本发明涉及的加密装置，具有面阻止电力分析攻击、比现有技术更能 削减加密处理的处理量的特征，所以在追求实现高速处理或低成本的加密 装置的实现中有用。
5权利要求
1、一种加密装置，使用密钥，根据明文生成密文，其特征在于，具备随机数生成部，生成随机数；随机化输入数据生成部，接收上述明文，将根据上述随机数决定的预定的输入屏蔽值和对上述明文利用上述密钥进行了预定的处理的输入数据相加，生成随机化输入数据；第1随机化逆元数据生成部，接收由上述随机化输入数据生成部生成的上述随机化输入数据和上述输入屏蔽值，将接收的上述输入屏蔽值的在预定的第1有限域中的逆元即输出屏蔽值和该输入数据的在上述第1有限域中的逆元相加，生成随机化输出数据；以及输出数据处理部，接收由上述第1随机化逆元数据生成部生成的上述随机化输出数据，根据接收到的该随机化输出数据生成上述密文。
2、 如权利要求1所述的加密装置，其特征在于，上述第1随机化逆 元数据生成部具备第1乘方计算部，对上述随机化输入数据和上述输入屏蔽值进行预定 的第1指数的乘方计算，分别通过各乘方计算生成第1乘方随机化输入数 据和第1乘方输入屏蔽值；校正数据生成部，根据上述随机化输入数据和上述输入屏蔽值，生成 预定的校正数据；加法部，将所生成的上述校正数据和计算出的上述第1乘方随机化输 入数据相加，生成副随机化输入数据；第2随机化逆元数据生成部，接收上述副随机化输入数据和上述第1 乘方输入屏蔽值，将该第1乘方输入屏蔽值的在预定的第2有限域中的逆 元即屏蔽值和上述副随机化输入数据的在该第2有限域中的逆元相加，生 成随机化副输出数据；以及随机化输出数据生成部，根据上述随机化副输出数据、上述随机化输 入数据、上述输入屏蔽值及上述第1乘方输入屏蔽值，生成上述随机化输 出数据。
3、 如权利要求2所述的加密装置，其特征在于，上述随机化输出数据生成部具备第2乘方计算部，对上述随机化输入数据和上述输入屏蔽值进行预定 的第2指数的乘方计算，通过各乘方计算，分别生成第2乘方随机化输入 数据和第2乘方输入屏蔽值；逆元运算部，对上述第1乘方输入屏蔽值进行上述第2有限域上的逆 元计算，生成该第1乘方输入屏蔽值的在上述第2有限域中的逆元即逆元 乘方输入屏蔽值；以及随机化输出数据生成部，根据上述随机化副输出数据、上述第2乘方 随机化输入数据、上述第2乘方输入屏蔽值及上述逆元乘方输入屏蔽值， 生成上述随机化输出数据。
4、 如权利要求l所述的加密装置，其特征在于，该加密装置对上述明文进行AES加密的加密处理，生成AES加密的 密文，上述输入数据的逆元是对上述输入数据进行了与AES加密的Sbox表 等价的逆元计算及仿射中的逆元计算而得的计算结果。
5、 如权利要求l所述的加密装置，其特征在于， 上述随机化输入数据生成部具备第1部分，根据上述明文，生成已加上了第1输入屏蔽值的第1随机 化输入数据；第2部分，接收由上述第1随机化逆元数据生成部生成的第(t一l) 随机化输出数据，加上根据上述第(t一l)输出屏蔽值决定的第t输入屏 蔽值，生成第t随机化输入数据，其中，2《t《J， J是2以上的预定的整 数，该加密装置进一步具备屏蔽值生成部，该屏蔽值生成部根据上述随机 数，生成上述第1 第J输入屏蔽值，上述第1随机化逆元数据生成部根据上述第1部分生成的上述第1随 机化输入数据和所生成的上述第1输入屏蔽值，生成上述第1随机化输出 数据，并且，根据上述第2部分生成的上述第t随机化输入数据和所生成 的上述第t输入屏蔽值，生成上述第t随机化输出数据，其中，2《t《J，上述输出数据处理部根据所生成的第J随机化输出数据，生成上述密文。
6、 一种解密装置，使用密钥，根据密文生成译文，其特征在于，具备随机数生成部，生成随机数；随机化输入数据生成部，接收上述密文，将根据上述随机数决定的预 定的输入屏蔽值和对上述密文利用上述密钥进行了预定的处理的输入数 据相加，生成随机化输入数据；第l随机化逆元数据生成部，接收由上述随机化输入数据生成部所生 成的上述随机化输入数据和上述输入屏蔽值，将所接收到的上述输入屏蔽 值的在预定的第1有限域中的逆元即输出屏蔽值和该输入数据的在上述第 l有限域中的逆元相加，生成随机化输出数据；以及输出数据处理部，接收由上述第1随机化逆元数据生成部生成的上述 随机化输出数据，根据接收到的该随机化输出数据生成上述译文。
7、 一种加密方法，使用密钥，根据明文生成密文，其特征在于，包括随机数生成步骤，生成随机数；随机化输入数据生成步骤，接收上述明文，将根据上述随机数决定的 预定的输入屏蔽值和对上述明文利用上述密钥进行了预定的处理的输入 数据相加，生成随机化输入数据；第1随机化逆元数据生成步骤，接收由上述随机化输入数据生成步骤 生成的上述随机化输入数据和上述输入屏蔽值，将接收的上述输入屏蔽值 的在预定的第1有限域中的逆元即输出屏蔽值和该输入数据的在上述第1 有限域中的逆元相加，生成随机化输出数据；以及输出数据处理步骤，接收由上述第1随机化逆元数据生成步骤生成的 上述随机化输出数据，根据接收到的该随机化输出数据生成上述密文。
8、 一种集成电路，使用密钥，根据明文生成密文，其特征在于，具备随机数生成部，生成随机数；随机化输入数据生成部，接收上述明文，将根据上述随机数决定的预 定的输入屏蔽值和对上述明文利用上述密钥进行了预定的处理的输入数 据相加，生成随机化输入数据；第l随机化逆元数据生成部，接收由上述随机化输入数据生成部生成的上述随机化输入数据和上述输入屏蔽值，将所接收的上述输入屏蔽值的 在预定的第1有限域中的逆元即输出屏蔽值和该输入数据的在上述第1有 限域中的逆元相加，生成随机化输出数据；以及输出数据处理部，接收由上述第1随机化逆元数据生成部生成的上述 随机化输出数据，根据所接收到的该随机化输出数据生成上述密文。
全文摘要
作为针对AES加密的电力分析攻击对策，如果采用通过合成域上的逆元计算安装S-Box的屏蔽法，则存在最大逻辑级数变大而处理速度降低的问题。本发明的加密装置(1)，使用密钥，根据明文生成密文，具备随机化8位逆元计算部(101)，接收随机化输入数据和输入屏蔽值，将接收到的上述输入屏蔽值的逆元即输出屏蔽值和该输入数据的逆元相加，生成随机化输出数据，上述随机化输入数据是将根据随机数决定的预定的上述输入屏蔽值和利用上述密钥进行了预定的处理的输入数据相加得到的数据；该加密装置根据所生成的该随机化输出数据，生成上述密文。
文档编号G09C1/00GK101542558SQ20088000061
公开日2009年9月23日 申请日期2008年5月26日 优先权日2007年5月30日
发明者太田雄策, 横田薰 申请人:松下电器产业株式会社
最新回复(0)