程序难破解化系统、程序难破解化装置及程序难破解化方法

摘要

提供一种进一步强化程序解析的困难性的难破解化装置。难破解化装置针对乘法和平方的处理，生成将相同个数的自变量作为输入的表格，并且，设定表格的输出值，以使输出依存于这些自变量。具体而言，对于平方处理，通过附加使用了仅乘法中所需的自变量的追加处理之后，进行表格化，将自变量的数与乘法一致。并且，此时，由于输出依存于全部自变量，所以与追加实际未被处理的伪自变量的情况不同，不知是否有追加的自变量。

说明书

技术领域

本发明涉及一种作为信息安全技术的计算机程序的难破解化技术。

背景技术

近年来，随着信息通信技术的普及，信息安全技术的重要性进一步增大。作为这种信息安全技术之一，密码技术具体体现为作为计算机程序的密码用软件，用于秘密通信、隐私的保护、通信对方的确认等。

在信息处理装置或通信装置等计算机系统中安装密码用软件的情况下，一旦不对秘密密钥或密码算法实施任何加工就原样安装这些软件，则当不正当利用者在程序执行时解析(称为程序解析)这些软件时，会简单地泄漏秘密密钥。因此，期望使程序解析变困难的耐篡改软技术。作为耐篡改软技术的一例，在专利文献1中记载通过将随机变换包含在密码等处理内，对密码等处理和随机变换进行表格化来难破解化程序的方法。

图39中示出专利文献1中记载的现有难破解化方法的处理。

在以前的该难破解化方法中，对共用密钥密码的密码用程序或解密用程序等难破解化前的通常程序9000，实施难破解化处理(步骤S9001-S9002)，生成并输出难破解化程序9002。下面说明该难破解化方法的细节。

在现有的难破解化方法中，最初将构成通常程序9000的多个程序命令分成使用共用密钥密码中的密钥key₁-key_n的处理1-n(n为自然数)，生成包含处理1-n的处理分割程序9001(步骤S9001)。

接着，在处理1紧后，插入输出值变换π₁与输出值逆变换π₁^-1，在处理2紧后，插入输出值变换π₂与输出值逆变换π₂^-1，在处理3紧后，插入输出值变换π₃与输出值逆变换π₂^-1，...，在处理i紧后，插入输出值变换π_i与输出值逆变换π_i^-1，...，在处理n-1紧后，插入输出值变换π_n-1与输出值逆变换π_n-1^-1。这里，π_i^-1表示变换π_i的逆变换。(i＝1、2、3、...、n-1)

接着，表格化处理1及输出值变换π₁，生成表格RT₁，表格化输出值逆变换π₁^-1、处理2及输出值变换π₂，生成表格RT₂，表格化输出值逆变换π₂^-1、处理3及输出值变换π₃，生成表格RT₃，...，表格化输出值逆变换π_i^-1、处理i+1及输出值变换π_i+1，生成表格RT_i+1，...，最后，表格化输出值逆变换π_n-1^-1及处理n，生成表格RT_n。这样，生成包含表格RT₁、RT₂、...、RT_n的难破解化程序9002(步骤S9002)。

此时，若密钥key₁-key_n分别是事先设定的常数，则也可包含上述密钥来表格化。

在专利文献1中记载的技术中，各表格RT₁、...、RT_n-1利用输出值变换π₁、...、π_n-1来变换各处理1、...、n的输出值。这样，至各表格的输入值或来自各表格的输出值变为变换后的值，所以即便使用各表格的输入值和输出值，也难以解析各表格中进行的运算，难以进行程序解析。另外，表格RT_i中实施的输出值变换π_i通过在继表格RT_i之后的表格RT_i+1中实施的输出值变换π_i^-1来逆变换，所以程序的执行结果与难破解化前的通常程序相同。

图40示出由以前的难破解化方法生成的表格一例。如该图所示，对集合9011中包含的各输入值in，利用处理1计算中间值a₁(步骤S9003)，对各个中间值a₁，设定作为随机的双射变换的输出值变换π₁，计算基于输出值变换π₁的变换后的值π₁(a₁)(步骤S9004)，形成将输入值in与变换后的值π₁(a₁)相对应的表格RT₁9014(步骤S9005)。

这样，专利文献1中记载的现有难破解化方法实现难破解化程序等一定的目的，但还期望强化程序解析的困难性的难破解化技术。

专利文献1：国际公开第WO02/46890号公报

非专利文献1：冈本龙明、山本博资、《现代密码》(現代暗号)、产业图书(1997年)

非专利文献2：H.Cohen，“A Course in Computational Algebraic NumberTheory”，GTM 138，Springer-Verlag，1996，p9

发明内容

本发明为了对应于上述期望，其目的在于提供一种进一步强化程序解析的困难性的难破解化系统、程序难破解化装置、程序难破解化方法、程序难破解化程序、存储程序难破解化程序的记录介质。

为了实现上述目的，本发明是一种程序难破解化装置，使信息安全程序难破解化，该信息安全程序包含使用密钥信息来安全或确实地处理对象信息的安全运算，其特征在于具备：取得单元，取得所述信息安全程序，该信息安全程序以由密钥信息确定的顺序来配置多个基本运算以便与所述安全运算等效，所述多个基本运算包括需要多个输入的第1基本运算和仅需要所述多个输入的一部分的第2基本运算；变换单元，对所述信息安全程序中包含的各第2基本运算，在该第2基本运算前后，配置与该第2基本运算中不需要的输入相依存的输入依存变换和作为其逆变换的输入依存逆变换；表格生成单元，对各第2基本运算，生成得到与一组运算等效的运算结果的表格，并生成参照该表格的参照命令，所述一组运算包括该第2基本运算紧前配置的所述输入依存变换、该第2基本运算和该第2基本运算紧后配置的所述输入依存逆变换；和输出单元，输出包含所生成的所述表格及所述参照命令的难破解化程序。

发明效果如下：

根据该构成，对于需要多个输入的第1基本运算和仅需要所述多个输入的一部分的第2基本运算中的第2基本运算，在该第2基本运算的前后，配置与该第2基本运算中不需要的输入相依存的输入依存变换和作为其逆变换的输入依存逆变换，可减少第1基本运算和第2基本运算的输入数量之差，对抗基于输入数量不同的攻击，进一步提高程序解析的困难性。

这里，也可以是所述变换单元还对所述信息安全程序中包含的各第1基本运算，在该第1基本运算之前和之后之一、或者之前和之后双方，配置与在该第1基本运算中需要的输入相依存的输入依存变换和作为其逆变换的输入依存逆变换。

根据该构成，由于对第1基本运算也在该第1基本运算之前和之后之一、或者之前和之后双方，配置与该第2基本运算中不需要的输入相依存的输入依存变换和作为其逆变换的输入依存逆变换，所以可进一步提高程序解析的困难性。

这里，也可以是所述变换单元中，所述输入依存变换为减法，所述输入依存逆变换为加法。

根据该构成，由于配置依存于输入值的减法和加法，所以运算结果与不配置的情况等效。

这里，也可以是所述变换单元还对除在所述信息安全程序的开始配置的基本运算以外的其它基本运算，分别在该基本运算紧前，配置向该基本运算紧前的基本运算的运算结果实施第1变换的第1变换运算、以及向所述第1变换运算的运算结果实施第2变换的第2变换运算，其中，所述第2变换是第1变换的逆变换；所述表格生成单元还生成得到与包括配置在所述信息安全程序的开始的基本运算和配置在其紧后的第1变换运算的一组运算等效的运算结果的表格，生成参照该表格的参照命令，对中间配置的各基本运算，生成得到与不仅包括该基本运算紧前配置的所述减法、该基本运算及该基本运算紧后配置的所述加法，还包括第2变换运算及第1变换运算的一组运算等效的运算结果的所述表格，生成参照该表格的所述参照命令，并且，生成得到与包括在所述信息安全程序的末尾配置的基本运算和紧前配置的第2变换运算的一组运算等效的运算结果的表格，生成参照该表格的参照命令，所述输出单元输出包含所生成的所述表格及所述参照命令的所述难破解化程序。

根据该构成，由于在基本运算的前后配置第1变换运算与作为其逆变换的第2变换运算，所以可进一步提高程序解析的困难性。另外，由于配置第1变换运算与作为其逆变换的第2变换运算，所以运算结果与不配置的情况等效。

这里，也可以是所述变换单元对每位数分解所述基本运算、所述减法、所述加法、所述第1变换运算及所述第2变换运算，生成多位数运算，配置生成的所述位数运算；所述表格生成单元为了得到与包括在所述信息安全程序的开始配置的基本运算和在紧后配置的第1变换运算的一组运算等效的运算结果，生成得到与生成的所述位数运算等效的运算结果的位数运算表格，生成参照该位数运算表格的位数运算参照命令，对于中间配置的各基本运算，为了得到与包括该基本运算紧前配置的所述减法、该基本运算及该基本运算紧后配置的所述加法、第2变换运算及第1变换运算的一组运算等效的运算结果，生成得到与生成的所述位数运算等效的运算结果的位数运算表格，生成参照该位数运算表格的位数运算参照命令，为了得到与包括在所述信息安全程序的末尾配置的基本运算和在紧前配置的第2变换运算的一组运算等效的运算结果，生成得到与生成的所述位数运算等效的运算结果的位数运算表格，生成参照该位数运算表格的位数运算参照命令；所述输出单元输出包含所生成的所述位数运算表格及所述位数运算参照命令的所述难破解化程序。

根据该构成，由于对每位数分解各运算，所以可进一步减少生成的表格的总量。

这里，也可以是所述表格生成单元在位数运算表格生成时，从规定数量的被共用化的表格中选择一个表格。

根据该构成，由于所述表格生成单元从规定数量个的共用表格中选择，所以可进一步减少保持的表格的总量。

这里，也可以是所述安全运算是以n为模数的、使用作为密钥信息的秘密密钥d的针对对象信息C的模幂运算Cⁿ mod n，以由密钥信息确定的顺序配置的输入数量不同的所述多个基本运算，利用二进制法，根据秘密密钥d的各比特值，配置了模乘运算和模平方运算作为所述基本运算，以便与模幂运算Cⁿ mod n等效，所述变换单元在中间配置的模乘运算或模平方运算的紧前和紧后，配置与输入到该模乘运算或模平方运算的一个输入值相依存的减法和加法，所述表格生成单元对中间配置的各模乘运算或模平方运算，生成得到与包括在该模乘运算或模平方运算紧前配置的所述减法、该模乘运算或模平方运算、及在该模乘运算或模平方运算紧后配置的所述加法的一组运算等效的运算结果的表格。

根据该构成，由于所述安全运算是以n为模数的、使用作为密钥信息的秘密密钥d的针对对象信息C的模幂运算Cⁿ mod n，所以可使用某种程度确立安全性的RSA密码技术。

这里，也可以是所述安全运算是以n为模数的、使用作为密钥信息的秘密密钥d的针对对象信息C的模幂运算Cⁿ mod n，以由密钥信息确定的顺序配置的输入数量不同的所述多个基本运算，利用二进制法，根据秘密密钥d的各比特值，配置了模乘运算和模平方运算作为所述基本运算，以便与模幂运算Cⁿ mod n等效，所述变换单元分解中间配置的各模乘运算，配置乘法运算及模运算，在配置的乘法运算的紧前和紧后，配置与输入到该乘法运算的一个输入值相依存的减法和加法，分解中间配置的各模平方运算，配置平方运算及模运算，在配置的平方运算紧前和紧后，配置与输入到该平方运算的一个输入值相依存的减法和加法，所述表格生成单元对中间配置的各乘法运算或各平方运算，所述表格生成单元对中间配置的各乘法运算或各平方运算，生成得到与包括该乘法运算或平方运算紧前配置的所述减法、该乘法运算或平方运算、及该乘法运算或平方运算紧后配置的所述加法的一组运算等效的运算结果的表格。

根据该构成，由于分别分解模幂运算Cⁿ mod n中的模乘运算和模平方运算，配置乘法运算和模运算、以及平方运算和模运算，在乘法运算紧前和紧后，配置所述减法和加法，在平方运算的紧后和紧后，配置所述减法和加法，所以可进一步提高程序解析的困难性。另外，由于配置依存于输入值的减法和加法，所以运算结果与不配置的情况等效。

附图说明

图1是表示实施方式1中从通常程序5001变换到难破解化程序5002的图。

图2是表示实施方式1的乘法难破解化及平方难破解化的图。

图3是表示实施方式2的难破解化系统1的构成框图。

图4是表示难破解化系统1的第1难破解化方法的想法的图。

图5是表示变换模乘处理的构成图。图5(a)表示i＝1的情况，图5(b)表示2≦i≦k-1的情况，图5(c)表示i＝k的情况。

图6(a)表示2≦i≦k-1的情况下插入了输入值变换及输出值变换的变换模乘处理的构成，图6(b)表示2≦i≦k-1的情况下分割后的模乘处理的构成。

图7(a)表示i＝k的情况下插入了输入值变换的变换模乘处理的构成，图7(b)表示i＝k的情况下分割后的模乘处理的构成。

图8表示2≦i≦k-1的情况下对每位数分割的变换乘法处理的构成。图8(a)表示分割前的变换乘法处理，图8(b)表示分割后的变换乘法处理。

图9表示i＝k的情况下对每位数分割的变换乘法处理的构成。

图10表示对每位数分割的情况下的各加法处理的构成。

图11表示分割后的变换模处理的构成。

图12表示对各位数进一步分割时的乘法处理的构成。

图13表示共用的表格模式(pattern)。

图14是表示对RT₁分割的乘法处理1002的构成图。

图15是表示对RT₁分割的乘法处理1002的构成图。图面上，输入值变换及输出值变换变得清楚。

图16是表示对RT_i(2≦i≦k-1)分割的乘法处理1004的构成图。

图17是表示对RT_i(2≦i≦k-1)分割的乘法处理1004的构成图。图面上，输入值变换及输出值变换变得清楚。

图18是表示对RT_k分割的乘法处理1009的构成图。

图19是表示对RT_k分割的乘法处理1009的构成图。图面上，输入值变换及输出值变换变得清楚。

图20表示分割后的模处理1005的构成。下接图21。

图21表示分割后的模处理1005的构成。下接图22。

图22表示分割后的模处理1005的构成。下接图23。

图23表示分割后的模处理1005的构成。上接图22。

图24对RT_i(2≦i≦k-1)示出图17所示的RM₁的细节。

图25对RT_i(2≦i≦k-1)示出图17所示的RM₁的表格的具体例。

图26(a)、图26(b)、图26(c)和图26(d)分别对RT_i(2≦i≦k-1)表示作为图17所示的RM₁的变换β、变换Φ^-1、变换g和变换γ₃的具体例的表格。

图27对RT_k示出图19所示的RM₁的细节。

图28对RT_k示出图19所示的RM₁的表格的具体例。

图29(a)、图29(b)、图29(c)和图29(d)分别对RT_k表示作为图19所示的RM₁的变换β、变换Φ^-1、变换g和变换γ₃的具体例的表格。

图30对RT₁示出图15所示的RA₁的细节。

图31对RT₁示出图15所示的RA₁的表格的具体例。

图32(a)、图32(b)和图32(c)分别对RT₁表示作为图15所示的RA₁的变换β、变换γ₁和变换β^-1的具体例的表格。

图33是表示难破解化装置100的构成图。

图34是表示密码处理装置300的构成图。

图35是表示难破解化装置100执行难破解化处理时的动作的流程图。

图36是表示密码处理装置300执行解密处理的动作的流程图。

图37是表示密码处理装置300执行署名生成处理的动作的流程图。

图38是表示难破解化装置100执行表格化动作的流程图。

图39是表示现有的难破解化方法的处理步骤图。

图40是表示现有的难破解化方法的表格化一例的图。

图41对RT₁示出图15所示的RM₁的细节。

图42(a)、图42(b)和图42(c)分别对RT₁表示作为图15所示的RM₁的变换β、变换g和变换γ₃的具体例的表格。

图43对RT₁示出图15所示的RM₁的表格的具体例。

符号说明

1     难破解化系统

100   难破解化装置

101   输入部

102   乘法配置信息生成部

103   分割处理配置信息生成部

104   变换生成部

105   表格生成部

106   读出信息配置部

107   程序生成部

108   介质记录部

200   介质

300   密码处理装置

301   输入部

302   输出部

303   数据存储器

304   程序存储器

305   CPU

306   介质读入部

具体实施方式

1.实施方式1

说明作为涉及本发明的1实施方式的难破解化方法。

这里，作为构成难破解化对象的程序，说明使用公钥密码而非共用密钥密码的解密程序的情况，具体而言，说明作为公钥密码的实例、使RSA密码的解密程序难破解化的难破解化方法。由于RSA密码记载于非专利文献1的110-113页中，所以省略详细说明。

在RSA密码的解密中，使用作为正整数的秘密密钥d，计算作为密码文C的解密文的M。

M＝C^d mod n

也将这种运算称为安全运算。

这里，n是素数p与素数q的积，在本说明书中，‘X^Y’表示X的Y次方，‘X mod Y’表示用Y去除X时的余数。

C^d mod n的计算可由乘法与平方的重复来实现，在将RSA密码安装于计算机系统等的情况下，多利用该性质。此时，由于适用乘法与平方的顺序依存于秘密密钥的值，所以通过解析，攻击者可知道秘密密钥。

作为RSA密码的解密程序的难破解化前的通常程序5001如图1所示，包含平方S5011、乘法S5012、...、乘法S5013。此时，适用乘法与平方的顺序依存于秘密密钥d的值。这里，秘密密钥d是n比特(bit)长度，作为一例，秘密密钥d是‘01...1’。

X₁＝C×C mod n

X₂＝X₁×C mod n

…

X_n＝X_n-1×C mod n

这样，得到解密文M＝X_n(＝C^d mod n)。

这里，为了便于说明，将

X₁＝C×C mod n

X₂＝X₁×C mod n

…

X_n＝X_n-1×C mod n

分别称为运算1(S5011)、运算2(S5012)、...、运算n(S5013)。

该难破解化方法在运算1(S5011)紧后插入输出值变换π₁S5031与输出值逆变换π₁^-1S5032，在运算2(S5012)紧后插入输出值变换π₂S5033与输出值逆变换π₂^-1，在运算3紧后插入输出值变换π₃与输出值逆变换π₃^-1，...，在运算i紧后插入输出值变换π_i与输出值逆变换π_i^-1，...，在运算(n-1)紧后插入输出值变换π_n-1与输出值逆变换π_n-1^-1S5034。这里，π_i^-1表示变换π_i的逆变换。(i＝1、2、3、...、n-1)

接着，该难破解化方法使运算X1(S5011)和输出值变换π₁S5031表格化，生成表格RT₁5021，使输出值逆变换π₁^-1S5032、运算X2(S5012)和输出值变换π₂S5033表格化，生成表格RT₂5022，使输出值逆变换π₂^-1、运算X3和输出值变换π₃表格化，生成表格RT₃，...，使输出值逆变换π_i^-1、运算Xi+1和输出值变换π_i+1表格化，生成表格RT_i+1，...，最后，使输出值逆变换π_n-1^-1S5034和运算Xn(S5013)表格化，生成表格RT_n5023。这样，生成包含表格RT₁5021、RT₂5022、...、RT_n5023的难破解化程序5002(步骤S5001)。

这样，在该难破解化方法中，在除最初与最后的运算以外的中途运算的前后，以组插入输出值变换及输出值逆变换。接着，使最初的运算与输出值变换表格化。之后，对中途的各运算，使输出值逆变换和该运算和输出值逆变换表格化。并且，对于最后的运算，使输出值逆变换与该运算表格化。由此，由于变换运算中途的中间值，所以可隐藏运算内容。

但是，在利用乘法与平方的重复执行幂运算来实现RSA密码的情况下，乘法与平方中使用的输入值不同。即，如图2(a)所示，乘法中执行对第1输入值in1乘以第2输入值in2的运算，相反，如图2(b)所示，平方中仅使用第1输入值in1，执行第1输入值in1的平方。

因此，乘法的表格输出依存于in1和in2双方，平方的表格的输出仅依存于in1。

若利用该性质，则攻击者通过着眼于表格的输入输出，可区别各表格执行乘法与平方哪一个。即，由于平方的表格中不需要输入值in2，所以可推测未输入输入值in2的表格是平方表格，输入输入值in2的表格是乘法表格。另外，即便假设将平方表格构成为(虽然实际处理中不使用)输入输入值in2，但由于平方表格的输出值不依存于输入值in2，所以有可能根据该性质来推测表格执行平方还是执行乘法。

因此，可能推测乘法与平方的顺序，结果，有可能知道秘密密钥的值。

2.实施方式2

下面示出的实施方式2的目的在于解决实施方式1的问题，防止基于乘法与平方的输入数量不同的攻击。

说明作为本发明实施方式2的难破解化系统1。

2.1 难破解化系统1的概要

图3示出实施方式2的难破解化系统1的构成。难破解化系统1包括：难破解化装置100，将受理秘密密钥d作为输入值来生成难破解化程序，并输出生成的难破解化程序；介质200，记录输出的难破解化程序；和密码处理装置300，从介质200中读出难破解化程序，执行读出的难破解化程序，根据密码文生成解密文，或根据报文生成署名数据。

难破解化系统1中，难破解化装置100对秘密密钥d、与RSA密码的解码或署名生成中使用的对象数据X，生成计算X^d mod n的难破解化程序，将生成的难破解化程序记录在介质200中。密码处理装置300读出介质200中记录的难破解化程序，密码处理装置300具备的CPU根据读出的难破解化程序动作，从而根据密码文生成解密文，或根据报文生成署名数据。

2.2 RSA密码方法和RSA署名方法

这里，说明RSA密码方法和RSA署名方法。通过使用RSA密码方法和RSA署名方法，可安全或确实地处理信息。

(1)RSA密码方法

(a)密钥的生成

在RSA密码方法中，如下所示，计算公钥和秘密密钥。

(i)随机选择大的素数p、q，计算其积n＝p×q。p、q的大小例如是512比特，n的大小例如是1024比特。

(ii)计算(p-1)和(q-1)的最小公倍数L＝LCM(p-1，q-1)。

(iii)随机选择与L彼此为素数(与L的最大公约数为1)、比L小的自然数e。

1≦e≦L—1、GCD(e，L)＝1

这里，GCD(e，L)表示e与L的最大公约数。

(iv)计算满足e×d＝1mod L的d。在GCD(e，L)＝1的情况下，数学上已知必然存在这种d。因此，得到的整数e和整数n为公钥。另外，整数d为秘密密钥。

(b)密码文的生成

使用作为公钥的整数e和整数n，对平文m实施下面的密码运算，计算密码文c。其中，平文m比整数n小。

c＝m^e mod n

(c)解密文的生成

使用作为秘密密钥的整数d，对密码文c实施解密运算，计算解密文m’。

m’＝c^d mod n

另外，

m’＝c^d mod n

＝(m^e)^d mod n

＝m^(e×d mod L)mod n

＝m^1mod n

＝m mod n

由于m<n，所以m mod n＝m，因此解密文m’与平文m一致。

RSA密码方法在非专利文献1的110-113页中详细说明。

(2)RSA署名方法

(a)密钥的生成

密钥的生成方法与RSA密码方法一样。

(b)署名生成

如下所示，对报文数据D计算署名数据S。

首先，使用散列函数Hash，计算报文数据D的散列值h＝Hash(D)。

接着，使用作为秘密密钥的整数d，将散列值h乘以d，计算署名数据S。

S＝h^d mod n

即，将散列值h作为平文，利用RSA密码密码的值是署名数据S。

(c)署名验证

如下验证署名数据S是否是报文数据D正确的署名。

接收报文数据D与署名数据S，计算Hash(D)，计算S^e mod n(相当于利用RSA密码解密署名数据S的值)。

接着，确认Hash(D)与S^e mod n是否相等。在相等的情况下，作为署名数据S是正确的署名，受理。在不相等的情况下，作为署名数据S是不正确的署名，拒绝。

RSA署名在非专利文献1的175-176页中详细说明。

2.3 由难破解化装置100执行的难破解化

(1)基于二进制法(Binary Method)的幂运算

构成难破解化装置100的难破解化对象的难破解化前的通常程序包含对对象数据X计算幂数值X^d mod n的命令。也将这种模幂运算称为安全运算。

该通常程序使用基于二进制法的幂运算作为该幂运算。这里，所谓基于二进制法的幂运算是利用乘法与平方的重复来计算X^d mod n等公式(一般称为模幂)的值的方法。二进制法的细节记载于非专利文献2中。

(2)难破解化装置100执行的难破解化处理的方法(第1难破解化方法)

用图4来说明难破解化装置100执行的难破解化处理的方法(第1难破解化方法)。图4中记载难破解化处理的想法。

在该难破解化处理的方法(第1难破解化方法)中，如图4所示，将难破解化前的通常程序400变换为中间程序420(步骤S401)，再变换为难破解化程序440(步骤S402)。

这里，通常程序400、中间程序420和难破解化程序440的运算结果分别相同。将这种性质称为等效。

(通常程序400的内容)

图4所示的难破解化前的通常程序400包含执行基于二进制法的模幂运算的命令块401，命令块401包含命令411、412和413。将这种通常程序400称为信息安全程序。

通常程序400在变量X中存储作为模幂运算的对象数据的值，在变量len中存储秘密密钥d的总比特长度，在变量Y中存储运算中途的结果值。另外，变量i表示秘密密钥d中着眼的比特位置。这里，设秘密密钥d的比特将最低位比特设为第0比特，从低位起顺序计数。

命令411将变量X的值代入变量Y中。

命令412在变量len中存储秘密密钥d的总比特长度。

命令413在变量i中首先存储(len-1)的值，每次从变量i减去‘1’，同时满足变量i≧0的期间，重复如下所示的命令414和命令415。

命令414就模数n执行变量Y的平方，将结果存储在变量Y中。

命令415观察秘密密钥d中变量i的值表示的比特，在其比特值为‘1’的情况下，再就模数n执行变量Y与变量X的乘法，将结果存储在变量Y中。

一旦基于命令块401的运算完成，则在变量Y中存储就模数n向变量X乘以d得到的值。

Y＝X^d mod n

这样，就基于二进制法的幂而言，观察秘密密钥d的各比特，在该比特值为‘0’的情况下，仅执行平方，在为‘1’的情况下，执行平方和乘法。因此，若知道是仅执行平方或是执行平方和乘法，则可复原秘密密钥d。因此，在难破解化处理中，就秘密密钥d的各比特所对应的处理而言，需要不附加区别执行平方和乘法哪个。

(从通常程序400向中间程序420的变换)

说明图4所示的步骤S401中从通常程序400向中间程序420的变换。

在难破解化装置100执行的难破解化处理的方法中，中间程序420内首先生成将变量X的值代入变量Y中的初始化命令422‘Y＝X；’。

接着，从通常程序400内的命令块401中，将作为基于秘密密钥d的值的分支命令的if语句和作为暴力破解(brute force)命令的for语句去除，在中间程序420内，从秘密密钥d的最低位比特向最高位比特，每个比特中若该比特的值为‘0’，则生成模平方命令‘Y＝X×Y mod n；’。若该比特的值为‘1’，则生成模平方命令‘Y＝X×Y mod n；’和模乘命令‘Y＝Y×X mod n；’。

这样，生成由初始化命令422、一个以上的模平方命令、与由一个以上的模平方命令和模乘命令构成的组命令所构成的乘法配置信息421。这里，将模平方命令和模乘命令称为基本模运算或简称为基本运算。另外，模平方命令和模乘命令分别称为第2基本运算和第1基本运算。这里，作为第1基本运算的模乘命令需要多个输入，作为第2基本运算的模平方命令仅需要所述多个输入的一部分。

在乘法配置信息421内，初始化命令422配置在开始，接着，对应于秘密密钥d的值来配置一个以上的模平方命令、与一个以上的模平方命令和模乘命令的组命令。乘法配置信息421内的这些命令的配置顺序规定初始化命令422、模平方命令和模乘命令的执行顺序。

作为一例，图4的中间程序420表示秘密密钥d是‘101...01’时的状态。乘法配置信息421由初始化命令422、组命令423、模平方命令424、组命令425、...、模平方命令426和组命令427构成，按该顺序配置。

这里，模乘表示在执行乘法之后，执行模(mod)运算的运算，模平方表示在执行平方之后，执行模运算的运算。

(从中间程序420向难破解化程序440的变换)

说明图4所示的步骤S402中从中间程序420向难破解化程序440的变换。

在难破解化装置100执行的难破解化处理的方法中，将中间程序420内的乘法配置信息421中包含的全部模平方命令和全部模乘命令变换为参照将变换了中间值Y的变量Z和对象数据X设为输入、将变量Z设为输出的2输入1输出的处理表格(RT₁、...、RT_k)的命令。这里，RT_i是使第i个模平方命令或模乘命令表格化的。

初始化命令422被变换为将变量X的值代入变量Z的初始化命令442。

作为一例，如图4所示，生成包含初始化命令442、表格参照命令443、444、445、446、447、...、448和449的命令块441。在命令块441中按该顺序配置所述命令。

通过根据该顺序来执行这些命令，执行模幂运算，算出幂数值。

(3)难破解化装置100执行的难破解化处理的方法(第2难破解化方法)

说明难破解化装置100执行的难破解化处理的方法(第2难破解化方法)。

(i)运算命令的展开

在该难破解化处理的方法(第2难破解化方法)中，如图4所示，将难破解化前的通常程序400变换为中间程序420(步骤S401)。此前与第1难破解化方法一样。

这里，将中间程序420的乘法配置信息421内的模平方命令和模乘命令称为运算命令，在乘法配置信息421内配置k个运算命令。即，乘法配置信息421内的模平方命令的数量与乘法配置信息421内的模乘命令的数量之合计为k个。

(ii)输出值变换和输入值变换的插入

下面，在该难破解化处理的方法(第2难破解化方法)中，将中间程序420的乘法配置信息421内的全部运算命令中最后配置的运算命令去除，对最初与中途配置的第i个运算命令(i＝1、2、3、...、k-1)，在该运算命令紧后按顺序插入输出值变换∏_i及输入值变换∏_i^-1。

这里，输出值变换∏_i是使用作为前级运算命令输出的中间值Z与对象数据X的变换。另外，输入值变换∏_i^-1是使用作为对应的输出值变换∏_i的输出的中间值Z与对象数据X的变换。并且，输入值变换∏_i^-1是与输出值变换∏_i的逆变换相同的变换。

这样，在运算命令之后，插入变换及其逆变换，由此可抵消变换的影响，得到与不插入这些变换及逆变换时相同的运算结果。

图5(a)、(b)和(c)中示出i＝1的情况、2≦i≦k-1的情况及i＝k的情况下各输出值变换∏_i及输入值变换∏_i^-1的插入一例。

如图5(a)所示，在i＝1的情况下，在第1个运算命令461紧后插入输出值变换∏₁462。

如图5(b)所示，在2≦i≦k-1的情况下，在第i个运算命令472紧后插入输出值变换∏_i473。在第i个运算命令472紧前插入输入值变换∏_i-1^-1471。

并且，如图5(c)所示，在i＝k的情况下，在第k个运算命令482紧前插入输入值变换∏_k-1^-1481。

(iii)表格化

并且，在该难破解化处理的方法(第2难破解化方法)中，如图5(a)所示，在i＝1的情况下，将第1个运算命令461和输出值变换∏₁462汇总设为一个表格RT₁460，生成参照表格RT₁460的命令。

如图5(b)所示，在2≦i≦k-1的情况下，将输入值变换∏_i-1^-1471、运算命令472和输出值变换∏_i473汇总设为一个表格RT_i470，生成参照表格RT_i470的命令。

并且，如图5(c)所示，在i＝k的情况下，将输入值变换∏_k-1^-1481和运算命令482汇总设为一个表格RT_k480，生成参照表格RT_k480的命令。

(4)难破解化装置100执行的难破解化处理的方法(第3难破解化方法)

说明难破解化装置100执行的难破解化处理的方法(第3难破解化方法)。

(i)运算命令的展开

在该难破解化处理的方法(第3难破解化方法)中，与第1难破解化方法和第2难破解化方法一样，如图4的步骤S401所示，将难破解化前的通常程序400变换为中间程序420。

(ii)输出值变换和输入值变换的插入

下面，在该难破解化处理的方法(第3难破解化方法)中，与第2难破解化方法一样，在中间程序420的乘法配置信息421内插入输出值变换和输入值变换。此前与第2方法一样。

第3难破解化方法还如下所示。

在i＝1的情况下，将输出值变换∏₁设为变换π₁，作为输出值变换∏₁，插入变换π₁。

在i＝k的情况下，将输入值变换∏_k-1^-1设为变换π_k-1^-1，作为输入值变换∏_k-1^-1，插入变换π_k-1^-1。

并且，在2≦i≦k-1的情况下，如图6(a)所示，将输入值变换∏_i-1^-1471设为变换π_i-1^-1471a和输入依存值减法471b，作为输入值变换∏_i-1^-1471，插入变换π_i-1^-1471a和输入依存值减法471b。另外，将输出值变换∏_i473设为输入依存值加法473a和变换π_i473b，作为输出值变换∏_i473，插入输入依存值加法473a和变换π_i473b。

这里，变换π_i^-1是变换π_i的逆变换，变换π_i^-1和变换π_i分别是从具有与Z相同比特大小的数量至相同比特大小的数量的双射变换。

另外，输入依存值减法是减去对对象数据X实施变换f后的f(X)的运算，输入依存值加法是加上对对象数据X实施变换f后的f(X)的运算。这里，输入依存值加法是输入依存值减法的逆变换。

图6(a)中，示出乘法，但平方也同样配置输入值变换和输出值变换。

(iii)表格化

并且，在该难破解化处理的方法(第3难破解化方法)中，与第2难破解化方法一样，在如上所述配置变换之后，表格化RT_i，配置参照各表格的命令。

通过表格化，可将一连串的计算过程变换为从表格中减去值的处理，所以从外部仅知道使用了哪个表格。由此，可防止追踪计算过程导致的不正当解析。

(第3难破解化方法的汇总)

如上所述，在第3方法中，通过将模乘处理和模平方处理变换为配置了包含输入依存加法、输入依存减法的输入值变换和输出值变换的变换后模乘处理和变换后模平方处理并表格化，对应于乘法和平方的表格的输入双方均使用中间值Z与对象数据X。结果，各表格的输出依存于中间值Z与对象数据X变化。

由此，即便监视表格的输入，也难以追踪各个表格中执行乘法与平方哪一个处理。另外，在上述变换得到的表格RT_i中，任一表格的输出均依存于中间值Z与对象数据X双方。由此，即便监视表格的输出，也难以解析各个表格中执行乘法与平方哪一个处理。

(5)难破解化装置100执行的难破解化处理的方法(第4难破解化方法-处理的分割(之一))

如上所述，使变换后模乘处理和变换后模平方处理表格化，但若设中间值z和对象数据X例如为1024比特的整数，则一个表格大小变为2²⁰⁴⁸×(表格的输出字节大小)字节，非常大，难以安装。

因此，在本实施方式的第4难破解化方法中，通过将变换后模乘处理和变换后模平方处理分割为小的值(例如4比特或8比特的整数)设为输入的处理(称为分割处理)，进行表格化。

说明难破解化装置100执行的难破解化处理的方法(第4难破解化方法)。

在难破解化处理的方法(第4难破解化方法)中，与第3难破解化方法一样，执行运算命令的展开。此前与第3难破解化方法一样。

在第4难破解化方法中，还如下所示。

分割各运算命令。即，将模乘运算分割为乘法和模运算，将模平方运算分割为平方和模运算。

在i＝1的情况下，在最初的乘法或平方紧后插入变换π₁。

另外，在2≦i≦k-1的情况下，以分割模乘运算的情况为例进行说明。如图6(b)所示，分割模乘运算，得到乘法512与模运算515。之后，在乘法512紧前插入输入值变换∏_i-1^-1511。这里，输入值变换∏_i-1^-1511由变换π_i-1^-1511a和输入依存值减法511b构成。另外，在乘法512紧后插入输出值变换A513。这里，输出值变换A513由输入依存值加法513a和变换α513b构成。另外，在模运算515紧前，插入变换α^-1514，在模运算515紧后，插入π_i516。这里，变换α^-1是变换α的逆变换。

并且，在i＝k的情况下，在最后的乘法或平方紧前插入输入值变换∏_k-1^-1。以分割模乘运算的情况为例进行说明，如图7(b)所示，在最后的乘法813紧前插入输入值变换∏_k-1^-1812。这里，输入值变换∏_k-1^-1812由变换π_k-1^-1812a和输入依存值减法812b构成。最后的模运算812是单独的，即不插入变换等存在。

分割模平方运算的情况也一样。

如上所述，根据第4难破解化方法，由于乘法处理侧的变换α513b被模运算处理侧的变换α^-1514抵消，所以若以分割处理整体看，可知执行与变换前一样的处理。

下面，将包含输入值变换∏_i-1^-1511、乘法512和输出值变换A513的处理称为变换乘法处理，将包含变换α^-1514、模运算515和变换π_i516的处理称为变换模处理。

在第4难破解化方法中，还将变换乘法处理和变换模处理分别分割成中间值Z与对象数据X的每位数(digit)的处理。

例如，将Z和X分割成每4比特的位数。

这里，设Z＝Z₀⁺Z₁×2⁴+Z₂×2⁸+…、

且X＝X₀+X₁×2⁴+X₂×2⁸+…时，

则Z从最低位位数起，被分割成每4比特的Z₀、Z₁、Z₂、...，X从最低位位数起，被分割成每4比特的X₀、X₁、X₂、...。

这里，变换π_i、变换α和变换f分别是一旦使每位数的变换相符合则恢复成分割前的变换的变换。

即，变换π_i为使用从4比特的数变换为4比特的数的双射变换Φ_i，表示为π_i(X)＝φ_i(X₀)+φ_i(X₁)ײ⁴⁺φ_i(X₂)×2⁸+…的变换。

同样，设表示为变换f(X)＝g(x₀)+g(X₁)×2⁴+g(X₂)×2⁸+…，表示为α(X)＝β(X₀)+β(X₁)×2⁴+β(X₂)×2⁸+…。另外，设各个逆变换也同样表示。

作为这些变换的具体例，例如基于与规定值的每比特的逻辑与或逻辑或、异或等逻辑运算的变换等。但是，为了提高安全性，与逻辑与或逻辑或、异或等逻辑运算等相比，期望这些变换是随机置换。

接着，用图8来说明分割处理的实例。图8表示2≦i≦k-1的情况下的变换乘法处理的分割状态，图8(a)表示分割前的变换乘法处理，图8(b)表示分割后的变换乘法处理。

若分割图8(a)所示的变换乘法处理501，则得到图8(b)所示的变换乘法处理520。图8中，变换成分割各位数的处理，将各个加法处理后的值设为输出。这利用大的数的乘法是小的数的乘法结果之和。

这里，各位数的变换表格RM₀、...、RM_k如下求出。

首先.以公式表示分割前的变换乘法处理整体时，如图6(b)所示，为α(((π_i-1^-1(Z)—f(X))×X)+f(X))。

这里，对于X、Z以及各变换，代入上述分割后的公式后展开，汇总成乘以2⁴、2⁸...的值或公式的每个。

由此，相当于第0位数变换的公式变为公式531，由2⁴汇总的公式变为相当于第1位数变换的公式532，由2⁸汇总的公式变为相当于第2位数变换的公式533。这样，每4比特汇总，将4比特作为1位数。下面同样求出相当于最高位位数前的各位数变换的公式。在这些公式中，为了简化，省略索引i。

根据各个位数的公式，将分别分割了该公式中使用的中间值Z和对象数据X的Z₀、Z₁、Z₂...、X₀、X₁、X₂...等设为输入，执行相当于各个位数的公式的变换的表格变为RM₀521、RM₁522、RM₂523。

这里，由于需要对各个位数反映距低位位数的进位，所以为了算出第1位数以上的位数的值，除基于各变换表格RM_i的运算外，还需要执行图10所示的加法处理1(551)。并且，执行加法处理1(551)的结果，有可能发生进一步的进位，所以为了算出第2位数以后的值，需要执行图10所示的加法处理2(552)。在加法处理1(551)和加法处理2(552)中，如图10所示，包含输入依存值减法或输入依存值加法，追加将对输入实施的变换去除的逆变换，作为输入值变换，并且，需要还向输出值变换追加下一段RT(严格地讲为变换RT得到的RM)中抵消的输出值变换。在本实施方式中，加法处理也同样表格化，由此对加法处理的解析也变困难。

以上内容的汇总为图8。这里，示出相当于各个位数的RM₀521、RM₁522和RM₂523的公式531、532和533。

RM₀521的输出的低位4比特变为该变换乘法处理520的第0位数的输出值，将RM₀521的高位4比特输出到加法处理1(541)。将RM₁522的输出的低位4比特输出到加法处理1(541)，将RM₁522的输出的高位4比特输出到加法处理1(542)。将RM₂523的输出的低位4比特输出到加法处理1(542)，将RM₂523的输出的高位4比特输出到未图示的加法处理1。

加法处理1(541)的输出的低位4比特变为该变换乘法处理520的第1位数的输出值，加法处理1(541)的输出的高位4比特输出到加法处理2(543)。加法处理1(542)的输出的低位4比特输出到加法处理2(543)，加法处理1(542)的输出的高位4比特输出到未图示的加法处理2。

用图9说明分割处理的实例。图9表示i＝k的情况下的变换乘法处理的分割状态，若分割变换乘法处理841，则得到变换乘法处理851。与图8一样，图9中，变换成分割各位数的处理，输出各个加法处理后的值。这利用大的数的乘法是小的数的乘法结果之和。

RM₀861的输出的低位4比特变为该变换乘法处理851的第0位数的输出值，将RM₀861的高位4比特输出到加法处理1(871)。将RM₁862的输出的低位4比特输出到加法处理1(871)，将RM₁862的输出的高位4比特输出到加法处理1(872)。将RM₂863的输出的低位4比特输出到加法处理1(872)，将RM₂863的输出的高位4比特输出到未图示的加法处理1。

加法处理1(871)的输出的低位4比特变为该变换乘法处理851的第1位数的输出值，加法处理1(871)的输出的高位4比特输出到加法处理2(873)。加法处理1(872)的输出的低位4比特输出到加法处理2(873)，加法处理1(872)的输出的高位4比特输出到未图示的加法处理2。

如上所述，通过对各个位数分割处理，输入的比特大小之和(在上述实例中，为1024+1024＝2048比特)变小，所以可削减表格化时的表格大小。

例如，第100位数、即RM₁₀₀中，输入为4比特的整数202个，输入的比特大小之和为202×4＝808比特。因此，第100位数的表格大小为2⁸⁰⁸×(表格的输出字节大小)字节。在分割前，一个表格大小为2²⁰⁴⁸×(表格的输出字节大小)字节，所以可削减表格大小。

在上述中，示出变换乘法处理，但变换模处理也可通过同样的代入及展开处理，如图11所示进行分割。图11中的π表示变换模乘处理RT_i内的π_i，但为了简化，省略索引。

下面，用图11来说明分割处理。

向表示变换模处理的公式中的输入Z中代入

Z₀+Z₁×2⁴+Z₂×2⁸+…+Z_b-1×2^4(b-1)+Z_b×2^4b+…+Z_2b-1×2^4(2b-1)。

这里，b是用4去除整数n的比特大小，表示本实施方式中的整数n的位数数量。当设n的比特大小为1024时，b＝256。

在上述式中，将变换模处理的输入Z的位数数量设为2×b-1位数，这是基于如下理由。变换模处理的输入Z是变换乘法处理的结果。在该变换乘法处理中，执行前段的表格的输出结果与对象数据X的运算。这里，前段表格的输出结果，为了在前段表格中乘以mod n，需要持有b-1位数以下的位数数量，而且，对象数据X需要是RSA密码下n以下的值，所以均持有b-1位数以下的位数数量。b-1位数彼此的乘法取2×b-2位数的运算结果，再发生1位数的进位，所以此外变换后模处理的输入最大为2×b-1位数。

这里，利用

Z mod n

＝((Z₀+Z₁×2⁴+...+Z_b-1×2^4(b-1))

  +(Z_b×2^4b mod n)

  +(Z_b+1×2^4(b+1))mod n)

  +…

  +(Z_2b-1×2^4(2b-1) mod n))mod n

分割成表示Z_b×2^4b mod n运算的处理、

表示Z_b+1×2^4(b+1) mod n运算的处理、

...、表示Z_2b+1×2^4(2b-1) mod n的处理，分别表格化，使用加法表格，将这些表格的输出相加，由此执行模运算。

图11中，将表示对i≧b的Z_i×2⁴ⁱ mod n的处理表现为RD_i。图11中，在分割的各处理RD_i之间插入加法“+”，但该加法与变换后乘法处理分割时使用的加法相同，表示对各个位数分割，向分割后的加法处理中分别附加输入值变换和输出值变换的处理。

(6)难破解化装置100执行的难破解化处理的方法(第5难破解化方法-处理的分割(之二))

如第4难破解化方法中说明的那样，在分割处理的情况下，若是第0位数(最低位位数)或第1位数，则由于输入(4比特的整数个数)少，所以表格大小不太大。但是，位置越增加，表格大小越变大。

例如，在第100位数中，输入为4比特的整数202个，输入的比特大小之和为202×4＝808比特。因此，第100位数的表格大小为2⁸⁰⁸×(表格的输出字节大小)字节，非常大。

因此，在第5难破解化方法中，即便对各位数也进一步分割处理。图12中示出第2位数的处理的进一步分割。在第2位数的分割前处理601中，设RM₂602的输入为Z₀、Z₁、Z₂、X₀、X₁和X₂，但在进一步分割后的处理611中，将处理601分割成为Z₀、Z₂、X₀和X₂的4输入的处理621、以及Z₁和X₁的2输入的处理622。

即便对其它位置的处理，也同样分割成4输入的表格与2输入的表格。

这里，处理621是将索引值的加法结果与位数数量相同的模式、即Z的各位数(例如分割第2位数的情况下，0+2＝2，所以为Z₀、Z₂)、与持有与其相同索引的X的各位数(X₀、X₂)设为4个输入的表格。

并且，在位数数量为偶数的情况下，处理622是将持有位数数量一半的索引的Z位数(这是因为位数数量为2时，Z₁为1+1＝2。)、与持有与其相同索引的X的位数(X₁)设为2个输入的表格。这种位数与变换的内容自身为4输入的情况一样，但由于4输入中的输入值中包含彼此相同的输入值，所以可汇总成2输入。

即便对其它位数，也可以与其一样的方法来进行表格分割。例如，第5位数的表格分割成持有以下输入的表格。

RM＿(5，0)：Z₀，Z₅，X₀，X₅

RM＿(5，1)：Z₁，Z₄，X₁，X₄

RM＿(5，2)：Z₂，Z₃，X₂，X₃

另外，第8位数的表格分割成持有以下输入的表格。

RM＿(8，0)：Z₀，Z₈，X₀，X₈

RM＿(8，1)：Z₁，Z₇，X₁，X₇

RM＿(8，2)：Z₂，Z₆，X₂，X₆

RM＿(8，3)：Z₃，Z₅，X₃，X₅

RM＿(8，4)：Z₄，X₄

附加于RM的索引(X、Y)表示最初的X是第几位数，第二个的Y表示输入的索引的最小值。

如上所述，通过分割处理，表格化分割后的处理，一个表格大小变为2¹⁶×(表格的输出字节大小)字节，可削减表格。

平方也可同样分割。分割的方式与乘法基本一样，所以省略。

(7)分割的表格的共用化

若如上所述分割表格，则如图13所示，表格的处理中存在共用点，使用该共用点，可共用化多个表格。图13中，示出RM分割表格的共用化657与RS的分割表格的共用化658。这里，RS是表示平方的处理。

在图13所示的RM的分割表格的共用化657中，用框包围的两个表格、例如表格661和表格662分别对输入执行相同处理。表格661和表格662是索引为2×i，i(i≠0)的表格。索引为2×i，i(i≠0)的表格可共用化，可使用同一个表格来代替多个表格。

另外，表格663和表格664分别对输入执行相同处理。表格663和表格664是索引为i，0(i≠0)的表格。这些表格也可共用化。

并且，表格665和表格656分别对输入执行相同处理。这些表格也可共用化。

这样，各表格依存于索引的组合，可分类为如下4个情况。

(情况a)索引为0，0的表格

(情况b)索引为2×i，i(i≠0)的表格

(情况c)索引为i，0(i≠0)

(情况d)持有其它索引的表格

这里，索引为i，0(i≠0)的表格与持有其它索引的表格的不同之处仅在于是否向输出加上g(X_i)。另外，索引为0，0的表格与索引为2×i，i(i≠0)的表格与上述一样，不同之处仅在于是否加上g(X_i)(在索引为0，0的情况下为g(X₀))。即，索引的第2个为0的表格与其它不同，向输出加上g(X_i)或g(X₀)。

这样，就分别属于情况a、情况b、情况c和情况d的多个表格而言，仅表格的输入值不同，输入值与输出值的对应关系相同。因此，可不分别使用属于各情况的多个表格，对每个情况共用化表格，使用一个共用化后的表格。

这样，在分割的乘法处理中，可仅使用4个表格，代替使用多个表格。只要对应于输入的X和Z的索引、从4个表格中选择一个适当的表格即可。

另外，图13所示的RS分割表格的共用化658也与上述一样，用框包围的两个表格、例如表格681和表格682分别对输入执行相同处理。表格681和表格682是索引为2×i，i(i≠0)的表格。索引为2×i，i(i≠0)的表格可共用化，可使用同一个表格来代替多个表格。

另外，表格683和表格684分别对输入执行相同处理。表格683和表格684是索引为i，0(i≠0)的表格。这些表格也可共用化。

并且，表格685和表格686分别对输入执行相同处理。

图13所示的RS分割表格的共用化658也与上述一样，各表格依存于索引的组合，可分类为上述4个情况。

这样，即便分割的平方处理也可仅使用4个表格来代替使用多个表格。

(8)难破解化装置100执行难破解化

如上所示，通过实施输入值变换或输出值变换、处理的分割、使分割的处理表格化时的共用化，难破解化装置100执行难破解化。

下面，将图4的模乘与模平方的配置信息称为乘法配置信息。另外，确定图5-图13中说明的输入值变换或输出值变换、处理的分割结果、得到的处理或表格的配置。下面，将表示该处理或表格的配置的信息称为分割处理配置信息。

难破解化装置100首先生成乘法配置信息，接着生成分割处理配置信息。之后，决定分割处理配置信息使用的输入值变换或输出值变换，据此来生成表格。

表格例如通过对输入值分别计算输入了该输入值的情况下在变换后处理中算出的值，并对应来生成。作为具体的实现方法，考虑多维排列等。并且，根据分割处理配置信息，生成表示表格的读出命令顺序的读出命令顺序信息。之后，通过将生成的读出命令顺序信息与生成的表格结合，完成难破解化程序。

难破解化装置100生成的难破解化程序也可包含上述读出命令顺序信息与表格以外的命令或数据。另外，也可事先将分割处理配置信息提供给难破解化装置100。

(9)乘法处理的分割具体例

用图14-图19来说明乘法处理的分割具体例。

(a)RT₁的分割

对作为相当于秘密密钥d的第1位数的变换之RT₁的分割，以RT₁为乘法处理的情况为例进行说明。图14是表示对RT₁分割的乘法处理1002的构成图。

该RT₁是相当于秘密密钥d的第1位数的变换，所以不包含输入值依存减法、变换π^-1。在本例中，设n的比特大小为6比特，将该6比特的数据分割成2位数。这里，各位数由3比特构成。另外，中间值Z、X分别为

Z＝Z₀+Z₁×2³，

X＝X₀+X₁×2³。

即，Z₀、Z₁、X₀、X₁分别是每3比特分割Z、X的值。此时，乘法处理根据上述方法，对各位数分割，乘法处理1002如图14所示，包含RM₀1121、RM₁1122、RM₂1123、加法处理RA₁1124、RA₂1125、RA₃1126、RA₁1127、RA₂1128、RA₂1129、RA₄1130和RA₅1131。

这里，RM₀1121是RT₁的第0位数的计算，是将Z₀、X₀设为输入的分割后的乘法处理，RM₁1122是RT₁的第1位数的计算，是将Z₀、Z₁、X₀、X₁设为输入的分割后的乘法处理，RM₂1123是RT₂的第2位数的计算，是将Z1、X1设为输入的分割后的乘法处理。

利用加法处理RA₁、RA₂、...、RA₅将RM₀、RM₁、RM₂各自的输出相加得到的结果是Z与X的乘法结果的变换后的值。

在本实施方式中，如上所述，通过也分别表格化RM₀、RM₁、RM₂、RA₁、RA₂、...、RA₅，从而难以解析。RA₁、RA₂、...、RA₅与图10所示的加法处理1、加法处理2一样，分别包含输入值变换和输出值变换。

这里，表格RM₀1121、RM₁1122和RM₂1123的框内部存在“[0，56]”、“[0，105]”和“[0，105]”的记述，这表示这些处理中的输出值在这些处理内的输出值变换前的值分别为从‘0’到‘56’的范围、从‘0’到‘105’的范围和从‘0’到‘49’的范围的值。

另外，RM₀1121、RM₁1122、RM₂1123、RA₁1124、RA₂1125、RA₃1126具有多个输出(就RM₁而言，是3位数的输出，所以还存在中位部分，具有3个输出，就其它而言，具有2个输出)。这里，就RM₁1122以外的部分而言，面向图面左侧的输出表示输出值变换前的输出的高位部分，右侧的输出表示输出值变换前的输出的低位部分。就RM₁1122而言，由于是3位数的输出，所以还存在中位部分。

例如，就RM₀1121而言，输出值为‘0’至‘56’的范围，将其输出值的高位3比特输入RA₁1124，低位3比特为乘法处理1002的输出。RM₀1121的高位部分和低位部分的“[0，7]”表示各自的输出值变换前的值是0-7范围的值。另外，乘法处理1002输出图14的最下部记载的各3比特的输出值1142a、1142b、1142c、1142d和1142e，作为最终输出值。在本例中，乘法处理1002输入6比特的Z和X，输出15比特的值。

在图15中，有关构成图14的乘法处理1002的RM₀1121、RM₁1122、RM₂1123、RA₁1124、RA₂1125、...、RA₅1131的每个，在附图中，输入值变换和输出值变换变得明显。

例如，RA₁1124在高位侧的输入值紧后，包含输入值变换β^-11124b，在低位侧的输入值紧后，包含输入值变换β^-11124a，包含将输入值变换β^-11124b的输出值与输入值变换β^-11124a的输出值相加的加法1124c，在加法1124c的高位侧的输出值紧后包含输出值变换γ₁1124e，在加法1124c的低位侧的输出值紧后包含输出值变换β1124d。

另外，RM₀1121包含相对高位侧输入值和低位侧输入值的乘法1121a，在乘法1121a高位侧的输出值紧后，包含输出值变换β1121c，在乘法1121a低位侧的输出值紧后，包含输出值变换β112b。

(b)RT_i(2≦i≦k-1)的分割

接着，说明RT_i(2≦i≦k-1)分割的乘法处理的构成。由于这些变换中包含前段的输出值变换等的逆变换，所以内容与RT₁稍有不同。图16是表示对RT_i(2≦i≦k-1)分割的乘法处理1004的构成图。在本例中，也将n的比特大小设为6比特，将6比特的数据分割成2位数。各位数由3比特构成。

此时，对各位数分割乘法处理，与对RT₁的乘法处理时一样，乘法处理1004如图16所示，包含RM₀1181、RM₁1182、RM₂1183、加法处理RA₆1184、RA₇1185、RA₈1186、RA₁1187、RA₇1188、RA₂1189、RA₉1190和RA₁₀1191。

这里，RM₀1181是将Z₀、X₀设为输入的分割后的乘法处理，RM₁1182是将Z₀、Z₁、X₀、X₁设为输入的分割后的乘法处理，RM₂1183是将Z₁、X₁设为输入的分割后的乘法处理。

并且，利用加法处理RA₁、RA₂、...、RA₁₀将RM₀、RM₁、RM₂的输出相加得到的结果是Z与X的乘法结果的变换后的值。这里，使RM₀、RM₁、RM₂、RA₁、RA₂、...、RA₁₀表格化。

这里，RM₀、RM₁、RM₂中存在“[-7，56]”等记述，这表示该处理的输出是从-7到56的范围的值。这里，与对RT₁的乘法处理不同，注意范围中包含负值。发生负的输出以执行用于抵消前段的输入值依存加法的输入依存值减法。这里，RM₀、RM₁、RM₂、RA₁、RA₂、...、RA₁₀具有作为负值范围包含的高位部分、与将正值设为范围的低位部分的2个输出。面向图面左侧的输出表示输出值变换前的输出的高位部分，右侧的输出为输出值变换前的输出的低位部分(RM₁取0-105的106种值，以2进制标记需要7比特，所以在将1位数设为3比特的情况下，变为3位数，还存在将正值设为范围的中位部分)。

例如，就RM₀而言，对于输出out，

低位部分＝out mod 8，

高位部分＝(out-(低位部分))/8。

另外，就RM_1而言，对于输出out，

低位部分＝out mod 8，

中位部分＝(out-(低位部分))/8 mod 8，

高位部分＝(out-低位部分-中位部分×8)/64。

对输出的高位部分、低位部分等的值的范围是输出值变换前的值，输出值变换后为该范围的值不限。例如，RM₀的输出的高位部分在输出值变换前为[1，7]，而输出值变换后为[0，8]等以易于处理。在本实例中，乘法处理中输入6比特的Z和X，输出16比特的值(包含最高位位数为符号的信息)。

在图17中，图16所示的RM₀1181、RM₁1182、RM₂1183、...、RA₁1187、RA₇1188、RA₂1189、...、RA₁₀1191的每个中包含的输入值变换和输出值变换变得明显。例如，示出RA₆1184在高位侧的输入值紧后，包含输入值变换β^-11184b，在高位侧的输入值紧后包含γ₅^-11184a，在输出值的高位部分紧前包含输出值变换γ₇1184d，在输出值的低位侧紧后，包含输出值变换β1184c。

各输入值变换与输出值变换只要是在图中直接联系的部位彼此抵消的变换，则可以是任何变换。

(c)RT_k的分割

下面，说明对RT_k分割的乘法处理的构成。

图18是表示对RT_k分割的乘法处理1009的构成图。

乘法处理1009如图18所示，包含RM₀1331、RM₁1332、RM₂1333、加法处理RA₁₇1334、RA₇1335、RA₈1336、RA₁₄1337、RA₇1338、RA₁₅1339、RA₉1340和RA₁₈1341。

这里，RM₀1331是将Z₀、X₀设为输入的分割后的乘法处理，RM₁1332是将Z₀、Z₁、X₀、X₁设为输入的分割后的乘法处理，RM₂1333是将Z₁、X₁设为输入的分割后的乘法处理。

并且，利用加法处理RA₁₇、RA₇、...、将RM₀、RM₁、RM₂的输出相加得到的结果是Z与X的乘法结果的变换后的值。

图19中，有关构成图18所示的乘法处理1009的RM₀1331、RM₁1332、RM₂1333、RA₁₇1334、RA₇1335、RA₈1336、RA₁₄1337、RA₇1338、RA₁₅1339、RA₉1340和RA₁₈1341的每个，在附图上，输入值变换和输出值变换变得明显。

图19所示的RM₀1331、RA₁₇1334、RA₁₄1337、RA₁₅1339和RA₁₈1341中分别包含变换E。这里，变换E表示不执行任何变换。

(d)对RT₁的对应于RM₁的表格的具体例

图41-图43中示出对RT₁的对应于图15所示的RM₁1122的表格的具体例。

图41对RT₁示出图15所示的RM₁1122的细节。RM₁对由4个输入值in1、in2、in3和in4构成的输入值群(in1、in2、in3、in4)，实施使用图43所示的表格1421的变换，输出由3个输出值out1、out2、和out3构成的输出值群(out1、out2、out3)。

这里，若设in1＝Z₀、in2＝Z₁、in3＝X₀、和in4＝X₁，则RT₁算出

val＝Z₀×X₁+Z₁×X₀

    -g(X₀)×X₁-g(X₁)×X₀+g(X₁)，算出

out1＝γ₃[val-(val mod 8)-(((val-(val mod 8)))mod 8)×8))/64]、

out2＝β[((val-(val mod 8))8)mod 8]、

out3＝β[val mod 8]

表格1421如图43所示，由多个输入值群(in1、in2、in3、in4)与分别对应于所述多个输入值群的多个输出值群(out1、out2、out3)构成。

图43中，为了容易理解运算过程，除多个输入值群(in1、in2、in3、in4)和多个输出值群(out1、out2、out3)外，还记载运算中途的中间值，但如上所述，表格1421仅由多个输入值群(in1、in2、in3、in4)和多个输出值群(out1、out2、out3)构成，所以需要注意。

图42(a)、图42(b)和图42(c)分别对RT₁示出作为图15所示的RM₁的变换β、变换g和变换γ₃的具体例的表格1422、1423、1424。

(e)对RT_i(2≦i≦k-1)的对应于RM₁的表格的具体例

图24-图26示出对RT_i(2≦i≦k-1)的对应于图17所示的RM_i1182的表格的具体例。

图24对RT_i(2≦i≦k-1)示出图17所示的RM₁1182的细节。RM₁对由4个输入值in1、in2、in3和in4构成的输入值群(in1、in2、in3、in4)，实施使用图25所示的表格1360的变换，输出由3个输出值out1、out2、和out3构成的输出值群(out1、out2、out3)。

这里，若设in1＝Z₀、in2＝Z₁、in3＝X₀和in4＝X₁，则RT_i(2≦i≦k-1)算出

val＝φ^-1(Z₀)×(X₁)+φ^-1(Z₁)×(X₀)

     -g(X₀)×X₁-g(X₁)×X₀+g(X₁)，算出

out1＝γ₃[val-(val mod 8)-(((val-(val mod 8))/8)mod 8)×8))/64]、

out2＝β[((val-(val mod 8))/8)mod 8]、

out3＝β[val mod 8]。

表格1360如图25所示，由多个输入值群(in1、in2、in3、in4)与分别对应于所述多个输入值群的多个输出值群(out1、out2、out3)构成。

图25中，为了容易理解运算过程，除多个输入值群(in1、in2、in3、in4)和多个输出值群(out1、out2、out3)外，还记载运算中途的中间值，但如上所述，表格1360仅由多个输入值群(in1、in2、in3、in4)和多个输出值群(out1、out2、out3)构成，所以需要注意。

图26(a)、图26(b)和图26(c)和图26(d)分别对RT₁表示作为图17所示的RM₁的变换β、变换Φ^-1、变换g和变换γ₃的具体例的表格。

图25中，out1的输出值变换前的值是从-2到2的范围的5种，但通过实施γ₃，变换为从0到7的范围的值(8种)。由此，攻击者难以调查变换后的值各自的发生概率，推测变换前的值。例如，防止通过推测为发生概率最高的值是变换前的0，解析表格的处理内容的攻击。此时，对应于-1的γ₃(-1)为0与1等2值，但设定γ₃，使整体的RM₁的表格的输出out1的值尽可能一样。即，输出out1的值以0到7分布，但设定γ₃，使该各个值为相同的发生概率。图26中，由于作为对γ₃的输入，-1、0、1的发生概率高，所以将其分别变换为2值。另外，后述图31的out1中的γ₁也同样变换为多值。

(f)对RT_k的对应于RM₁的表格的具体例

图27-图29中示出对RT_k的对应于图19所示的RM₁1332的表格的具体例。

图27对RT_k示出图19所示的RM₁1332的细节。RM₁对由4个输入值in1、in2、in3和in4构成的输入值群(in1、in2、in3、in4)，实施使用图28所示的表格1390的变换，输出由3个输出值out1、out2、和out3构成的输出值群(out1、out2、out3)。

这里，若设in1＝Z₀、in2＝Z₁、in3＝X₀、和in4＝X₁，则RT_k算出

val＝φ^-1(Z₀)×(X₁)+φ^-1(Z₁)×(X₀)

     -g(X₀)×X₁-g(X₁)×X₀，算出

out1＝γ₃[val-(val mod 8)-(((val-(val mod 8)))mod 8)×8))/64]、

out2＝β[((val-(val mod 8)))mod 8]、

out3＝β[val mod 8]。

表格1390如图28所示，由多个输入值群(in1、in2、in3、in4)与分别对应于所述多个输入值群的多个输出值群(out1、out2、out3)构成。

图28中，为了容易理解运算过程，除多个输入值群(in1、in2、in3、in4)和多个输出值群(out1、out2、out3)外，还记载运算中途的中间值，但如上所述，表格1390仅由多个输入值群(in1、in2、in3、in4)和多个输出值群(out1、out2、out3)构成，所以需要注意。

图29(a)、图29(b)、图29(c)和图29(d)分别对RT_k表示作为图19所示的RM₁的变换β、变换Φ^-1、变换g和变换γ₃的具体例的表格1391、1392、1393、1394。

(g)对RT₁的对应于RA₁的表格的具体例

图32-图32示出对RT₁的对应于图15所示的RA₁1124的表格的具体例。

图30对RT₁示出图15所示的RA₁1124的细节。RA₁对由2个输入值in1和in2构成的输入值群(in1、in2)，实施使用图31所示的表格1410的变换，输出由2个输出值out1和out2构成的输出值群(out1、out2)。

RT₁算出

out1＝γ₁[(β^-1(in1)+β^-1(in2)-out2)/8]、

out2＝β[β^-1(in1)+β^-1(in2)mod8]。

表格1410如图31所示，由多个输入值群(in1、in2)与分别对应于所述多个输入值群的多个输出值群(out1、out2)构成。

图31中，为了容易理解运算过程，除多个输入值群(in1、in2)和多个输出值群(out1、out2)外，还记载运算中途的中间值，但如上所述，表格1410仅由多个输入值群(in1、in2)和多个输出值群(out1、out2)构成，所以需要注意。

图32(a)、图32(b)和图29(c)分别对RT₁表示作为图15所示的RA₁的变换β、变换γ₁和变换β^-1的具体例的表格1411、1412、1413。

(10)模处理的分割具体例

用图20-图23说明模处理的分割具体例。

分割后的模处理1005如图20-图23所示，由模运算RD₀1201、RD₁1206、RD₂1212、RD₃1218、加法RA₁1202、RA₁1203、RA₂1204、RA1₂1205、RA₁1207、RA₁1208、RA₂1209、RA₁₂1210、RA₄1211、RA₁1213、RA₁1214、RA₂1215、RA₁₃1216、RA₄1217、RA₁1219、RA₁1220、RA₂1221和RA₄1222构成。

这里，模运算RD₀1201、RD₁1206、RD₂1212、RD₃1218是用于执行模运算的表格。这些表格存储多个将作为运算对象的对象值与对应对象值的模值相对应所构成的组，若将某个对象值指定为输入，则将对应于该对象值的模值从该表格中减去后输出。另外，模运算RD₀1201、RD₁1206、RD₂1212、RD₃1218在上述模运算前后实施变换。

另外，RA₁、RA₂、RA₁₂、...是执行用于反映每位数的加法或进位的加法的加法处理的表格。这些表格也存储多个将作为运算对象的2个对象值与所述2个对象值的加法值对应所构成的组，若将某2个对象值指定为输入，则将对应于该对象值的加法值从该表格中减去后输出。另外，RA₁、RA₂、RA₁₂、...在上述加法前后实施变换。

在本例中，模处理1005计算设整数n为模数时的

Z＝Z₀+Z₁×2³+Z₂×2⁶+Z₃ײ⁹+Z₄×2¹²的模。

(a)模处理1005中，在图20所示的运算中，计算

(Z₀+Z₁×2³)+(Z₂×2⁶mod n)。

即，在图20所示的运算中，模处理1005的模运算RD₀1201、加法RA₁1203、RA₁1202分别受理3个3比特的输入值Z₂、Z₁、Z₀的输入。

模运算RD₀1201分别将其运算结果的高位3比特和低位3比特输出到加法RA₁1203、RA₁1202。加法RA₁1203分别将其运算结果的高位1比特及低位3比特输出到加法RA₁₂1205和RA₂1204。加法RA₁1202分别将其运算结果的高位1比特及低位3比特输出到加法RA₂1204和RA₁1207。加法RA₂1204分别将其运算结果的高位1比特及低位3比特输出到加法RA₁₂1205和RA₁1208。加法RA₁₂1205将其运算结果的1比特输出到加法RA₄1211。

(b)模处理1005中，在图21所示的运算中，输入1个输入值Z₃，使用输入值Z₃和图20中的3个最终运算结果，相加(Z₃×2⁹mod n)。

模运算RD₁1206受理1个3比特的输入值Z₃的输入，将其运算结果的高位3比特及低位3比特分别输出到加法RA₁1208、RA₁1207。

加法RA₁1208分别将其运算结果的高位1比特及低位3比特输出到加法RA₁₂1210和RA₂1209。加法RA₁1207分别将其运算结果的高位1比特及低位3比特输出到加法RA₂1209和RA₁1213。加法RA₂1209分别将其运算结果的高位1比特及低位3比特输出到加法RA₁21210和RA₁1214。加法RA₁₂1210将其运算结果的1比特输出到加法RA₄1211。加法RA₄1211将其运算结果的1比特输出到加法RA₁₃1216。

(c)并且，模处理1005中，在图22所示的运算中，输入1个输入值Z₄，使用输入值Z₄和图21中的3个最终运算结果，相加(Z₄×2¹²mod n)。

模运算RD₂1212受理1个4比特的输入值Z₄的输入，将其运算结果的高位3比特及低位3比特分别输出到加法RA₁1214、RA₁1213。

加法RA₁1214分别将其运算结果的高位1比特及低位3比特输出到加法RA₄1217和RA₂1215。加法RA₁1213分别将其运算结果的高位1比特及低位3比特输出到加法RA₂1215和RA₁1219。加法RA₂1215分别将其运算结果的高位1比特及低位3比特输出到加法RA₄1217和RA₁1220。加法RA₄1217将其运算结果的1比特输出到加法RA₁₃1216。加法RA₁₃1216将其运算结果的2比特输出到模运算RD₃1218。

(d)模处理1005中，由于图22的最终计算结果为3位数，所以接着需要进一步的模处理。

模处理1005中，图23所示的运算执行该模处理。有时图23所示的运算的计算结果也为3位数，此时，需要进一步模处理，重复与图23一样的处理。结果，若为2位数的值，则为模运算结果(的输出值变换后)的值。

模处理1005中，在图23所示的运算中，模运算RD₃1218分别将其运算结果的高位3比特及低位3比特输出到加法RA₁1220、RA₁1219。加法RA₁1220分别将其运算结果的高位1比特及低位3比特输出到加法RA₄1222和RA₂1221。加法RA₁1219将其运算结果的高位1比特输出到加法RA₂1221，将其运算结果的低位3比特设为最终输出。加法RA₂1221将其运算结果的高位1比特输出到加法RA₄1222，将其运算结果的低位3比特设为最终输出。加法RA₄1222将其运算结果的1比特设为最终输出。

(e)上述数值例中，n为6比特的值，小，所以将乘法处理作为至各位数的分割，但在比特大小大的情况下，也可进一步如‘处理的分割(之二)’那样分割各位数的处理。

2.4 难破解化系统1的构成及动作

这里，说明构成难破解化系统1的难破解化装置100和密码处理装置300的构成和动作。

(1)难破解化装置100的构成

图33是表示难破解化装置100的构成图。

难破解化装置100如图33所示，具备：输入部101，受理秘密密钥d的输入；乘法配置信息生成部102，根据秘密密钥d，生成表示乘法处理和平方处理的处理顺序的乘法配置信息；分割处理配置信息生成部103，生成分割了乘法处理和平方处理的处理、和对其追加的一个以上的输入值变换与一个以上的输出值变换的配置信息，即分割处理配置信息；变换生成部104，生成表示输入值变换和输出值变换的函数；表格生成部105，使用分割处理配置信息、输入值变换及输出值变换，生成表格；读出信息配置部106，使用乘法配置信息与分割处理配置信息，生成表示读出表格的命令配置的读出命令顺序信息；程序生成部107，使用表格与读出命令顺序信息，生成难破解化程序；和介质记录部108，将难破解化程序记录在介质中。

输入部101受理秘密密钥d作为输入。

乘法配置信息生成部102根据秘密密钥d，生成表示模乘处理和模平方处理的处理顺序的乘法配置信息。这对应于图4的步骤S401所示的处理。在图4的情况下，乘法配置信息421为表示{模平方、模乘、模平方、模平方、模乘、...}等顺序的信息。

分割处理配置信息生成部103根据事先提供的配置方法，生成分割了模乘处理和模平方处理的处理、和对其追加的一个以上的输入值变换与一个以上的输出值变换的配置信息，即分割处理配置信息。这里生成的信息仅是各处理或变换的配置信息，不生成对应于处理或变换的函数。

变换生成部104参照分割处理配置信息，生成对配置的输入值变换和输出值变换的函数。对输入值变换和输出值变换的函数的生成方法如在先的‘2.3难破解化装置100执行的难破解化’中所述。

表格生成部105使用分割处理配置信息、输入值变换及输出值变换，生成表格。表格的生成方法如在先的‘2.3难破解化装置100执行的难破解化’中所述。

读出信息配置部106使用乘法配置信息与分割处理配置信息，生成顺序配置读出表格的命令的读出命令顺序信息。具体而言，使用分割处理配置信息，顺序配置对应于变换后模乘处理内和变换后模平方处理内的各处理的表格读出命令，生成表格读出命令群，使用乘法配置信息，配置这些变换后模乘处理内和变换后模平方处理内所对应的表格读出命令群，从而配置表格读出命令。

程序生成部107生成使上述读出命令顺序信息与表格相结合的难破解化程序。

介质记录部108将难破解化程序记录在介质200中。

(2)密码处理装置300的构成

图34是表示密码处理装置300的构成图。

密码处理装置300如图34所示，具备输入密码化数据或报文数据的输入部301；输出解密数据或署名数据的输出部302；数据存储器303；程序存储器304；CPU305；从介质200中读入难破解化程序的介质读入部306。

输入部301在后述的解密处理时受理密码化数据作为输入，在署名生成处理时受理报文数据作为输入。

输出部302在后述的解密处理时输出解密数据，在署名生成处理时输出署名数据。

数据存储器303存储作为输入的解密数据或报文数据、执行难破解化程序时的中间值数据。

程序存储器304存储难破解化程序。

CPU305执行难破解化程序中记述的命令。

介质读入部306从介质200中读入难破解化程序，存储在程序存储器304中。

(3)难破解化系统1的动作

难破解化系统1的动作由难破解化装置100生成难破解化程序、记录在介质200中的‘难破解化处理时’的动作；和密码处理装置300执行介质200中记录的难破解化程序、执行解密处理的‘解密处理时’与执行署名生成处理的‘署名生成处理时’的动作构成。

下面，说明各个动作。

(a)难破解化装置100执行难破解化处理时的动作

用图35所示的流程图来说明难破解化装置100执行的难破解化处理时的动作。

难破解化装置100的输入部101受理秘密密钥d(步骤S1101)，乘法配置信息生成部102生成乘法配置信息(步骤S1102)，分割处理配置信息生成部103生成分割处理配置信息(步骤S1103)，变换生成部104生成对输入值变换和输出值变换的函数(步骤S1104)，表格生成部105生成表格(步骤S1105)，读出信息配置部106生成读出命令顺序信息(步骤S1106)，程序生成部生成难破解化程序(步骤S1107)，难破解化装置100的介质记录部108将难破解化程序记录在介质200中(步骤S1108)。这样，难破解化处理结束。

(b)密码处理装置300执行的解密处理的动作

用图36所示的流程图来说明密码处理装置300执行的解密处理的动作。

密码处理装置300的输入部301受理作为输入的密码化数据，作为对象数据X，存储在数据存储器中(步骤S1201)，介质读入部306从介质200中读入难破解化程序，存储在程序存储器304中(步骤S1202)，CPU305根据存储在程序存储器304中的难破解化程序，使用数据存储器303，计算对象数据X的幂数值X^d mod n，存储在数据存储器303中(步骤S1203)，输出部302将存储在数据存储器303中的值(对象数据的幂数值)作为解密数据输出(步骤S1204)。这样，解密处理的动作结束。

(c)密码处理装置300执行的署名生成处理的动作

使用图37所示的流程图来说明密码处理装置300执行的署名生成处理的动作。

密码处理装置300的输入部301受理作为输入的报文数据，作为对象数据X存储在数据存储器中(步骤S1301)，介质读入部306从介质200中读入难破解化程序，存储在程序存储器304中(步骤S1302)，CPU305根据存储在程序存储器304中的难破解化程序，使用数据存储器303，计算对象数据X的幂数值X^d mod n，存储在数据存储器303中(步骤S1303)，输出部302将存储在数据存储器303中的值(对象数据的幂数值)作为解密数据输出(步骤S1304)。这样，署名生成处理的动作结束。

(d)难破解化装置100执行的表格化动作

用图38所示的流程图来说明难破解化装置100执行的表格化动作。这里，将图15所示的乘法处理1002的表格化作为一例进行说明，但其它表格化的实例也可同样实现，所以省略其说明。

难破解化装置100的表格生成部105事先仅存储图15所示的表格配置中的RM₀1121、RM₁1122、RM₂1123、RA₁1124、RA₂1125、RA₃1126、RA₁1127、RA₂1128、RA₂1129、RA₄1130和RA₅1131的连接关系。这里，该连接关系如上所述，是设计者制作且数据化后的关系。

表格生成部105首先仅存储这些连接关系，不存储RM₀1121、RM₁1122、RM₂1123、RA₁1124、RA₂1125、RA₃1126、RA₁1127、RA₂1128、RA₂1129、RA₄1130和RA₅1131的内容。

难破解化装置100执行的表格化的步骤根据上述连接关系，决定RM₀1121、RM₁1122、RM₂1123、RA₁1124、RA₂1125、RA₃1126、RA₁1127、RA₂1128、RA₂1129、RA₄1130和RA₅1131的内容。

另外，表格生成部105事先存储40种不同的乘法模式表格。这些乘法模式表格在这里是将2个输入值变换为2个输出值的2输入2输出的表格，各输入值是3比特长度，各输出值也是3比特长度。

表格生成部105在图38所示的步骤S1401-S1404中，对图15所示的RM₀1121、RM₁1122、和RM₂1123，分别从上述40种乘法模式表格中随机选择1个乘法模式表格(步骤S1402)，向这些RM₀1121、RM₁1122、和RM₂1123分配选择到的乘法模式表格(步骤S1403)。这里，当从上述40种乘法模式表格中随机选择1个乘法模式表格时，由于对不同的RM不选择相同的乘法模式表格，所以从选择对象中去除选择过的乘法模式表格，以在下次选择中不选择。

接着，表格生成部105在图38所示的步骤S1405-S1410中，对乘法处理1002的开始输入值至最终输出值的各路径，重复以下步骤。

这里，乘法处理1002的开始输入值至最终输出值的路径的一例是从输入值1141a经RM₀1121的乘法1121a、变换1121b至输出值1142a的路径，另外，另一路径的一例是从输入值1141b经RM₀1121的乘法1121a、变换1121c、RM₁1124的变换1124a、加法1124c、变换1124d至输出值1142b的路径。

这样，所谓所述路径是以3比特的输入值为开始点、经1个RM和至少一个RA至3比特的输出值的路径。

在各路径上，事先确定应配置变换的位置。表格生成部105事先存储各路径上应配置变换的位置。所谓应配置变换的位置在图15中是例如RM₀1121中配置变换1121b和变换1121c的位置，另外，RM₁1124中是配置变换1124a、变换1124b、变换1124d和变换1124e的位置。

表格生成部105从各路径的开始，每次一个顺序选择配置变换的位置。

若选择的位置之后是最终输出值(步骤S1406为是)，则表格生成部105选择一个变换，将选择到的变换配置在该位置上(步骤S1409)，结束该路径中的处理。

若选择的位置之后不是最终输出值(步骤S1406为否)，则表格生成部105选择一个变换，将选择到的变换配置在该位置上。这里，在同一路径中之前选择变换的情况下，选择与之前选择的变换不同的变换(步骤S1407)。接着，在下一位置，配置步骤S1407中配置的变换的逆变换(步骤S1408)，接着返回步骤S1406，重复处理。

2.5 实施方式2的效果

在实施方式2中，对分割了乘法和平方的处理的处理生成将相同个数的自变量设为输入的表格，再设定表格的输出值，以使输出依存于这些自变量，从而可防止乘法与平方的处理由于输入数量不同而被攻击者攻击。下面详细说明。

乘法是2输入1输出，平方是1输入1输出的运算，所以有可能因该不同而被攻击者攻击。相反，在实施方式2中，如上所述，在通常的RSA密码等处理中，将包含包含于乘法处理的输入中、但不包含于平方处理的输入中的输入之输入值变换和输出值变换，配置在乘法处理和平方处理的前后，生成包含上述变换的表格。

由此，在对应于乘法处理的表格与对应于平方处理的表格中，由于无输入数量差异，所以可防止攻击者解析输入、区别乘法与平方的攻击。

并且，通过输入值变换或输出值变换，可将原本不包含于平方处理中的输入的值反映到各表格的输出上，所以可防止攻击者解析输出并发现输入是哑元(dummy)时进行区别乘法与平方的攻击。

在实施方式2中，如上所述，由于乘法和平方的各个输入值和输出值是非常大的数(1024比特左右)，所以将乘法及平方的处理分割成各位数的处理。

此时，无论乘法还是平方，均可采取通过将各位数的处理分割成4输入1输出与2输入1输出的表格，容易配置上述输入值变换和输出值变换的构成。

由此，对于对各位数分割了乘法和平方的处理的处理，生成乘法和平方均将相同个数的自变量设为输入，各个输入影响输出的表格，所以不能根据表格的分割方式来区别是乘法还是平方。即，可防止解析该表格并区别是乘法处理还是平方处理的攻击。因此，攻击者难以区别乘法与平方的处理，本发明有效。

另外，通过将乘法处理或平方处理分割成各位数的处理表格，一个乘法处理或平方处理所需的表格大小为2²⁰⁴⁸×(表格的输出字节大小)字节左右，但通过将各位数的处理分割成4输入1输出与2输入1输出的表格，可削减到(256×256)/2×2¹⁶×(表格的输出字节大小)＝2³¹×(表格的输出字节大小)左右。

并且，通过使表示同一变换的表格共用化，作为分割后的表格，4输入1输出的表格变为2个，2输入1输出的表格变为2个，结果，一个乘法处理或平方处理所需的表格大小可削减到2×2¹⁶×(表格的输出字节大小)+2×2⁸×(表格的输出字节大小)＝131,584×(表格的输出字节大小)左右。这样，通过执行表格的分割、共用化，可削减表格大小。

如上所述，可防止乘法与平方的处理由于输入数量不同而被攻击者攻击，另外，由于使用的表格大小可削减，所以利用本发明，可生成计算机上可安装的RSA密码的源代码难破解化的程序。

2.6 对安全性的研究

对实施方式2研究对双射映射(bijective-mapping)的暴力破解攻击的安全性。这里，所谓双射映射的暴力破解攻击是指从全部取得的双射映射的变化得到正确的双射映射的攻击。具体而言，对双射映射分别生成表格，与实际包含于程序中的表格相比较，由此判定是否是正确的双射映射。在是正确的双射映射的情况下，表格的值全部一致。

(1)攻击乘法表格或平方表格的情况

在攻击乘法表格或平方表格的情况下，各表格中包含上述g、Φ的双射映射，若不对两个表格执行使用各表格中相应的正确映射的攻击，则对表格的攻击不成功。

在实施方式2中，如上所述，在以4比特分割各位数的情况下，由于g、Φ各自的双射映射的变化为16！＝2⁴⁴，所以为了执行暴力破解，需要16！＝2⁴⁴的计算量。攻击者由于需要得到g、Φ的双射映射双方，所以攻击所需的计算量为(2⁴⁴)2＝2⁸⁸。

(2)攻击加法表格的情况

在攻击加法表格的情况下，由于加法表格中至少包含2种Φ，所以攻击所需的计算量为(2⁴⁴)²＝2⁸⁸。

接着，若对实施方式2研究对每位数的分割前表格是乘法表格还是平方表格的暴力破解攻击的安全性，则乘法表格和平方表格存在80种，分别可能是乘法表格或平方表格，所以暴力破解攻击的计算量为2⁸⁰。

为了使对攻击的安全性提高，在以4比特分割各位数的同时，依存于2种函数生成表格是有效的。

3.其它变形例

上述说明的各实施方式是本发明的实施一例，本发明不限于该实施方式，在不脱离其主旨的范围下，可以各种方式实施。例如，以下情况也包含于本发明中。

(1)在实施方式2中，将表格化的对象处理设为RSA密码中的模乘处理和模平方处理，统一其输入，但不限于此。

也可使输入的数量不同的处理表格化。例如，也可将椭圆曲线密码的椭圆加法(以两个点的坐标为输入)与椭圆2倍(以一个点的坐标为输入)的处理作为表格化对象。即便在椭圆曲线密码的情况下，也由于当区别椭圆加法与椭圆2倍加法时不正当解析麻烦，所以如本发明所示不加以区别地防止攻击的方法是有效的。

本发明不仅是关联于密码的处理，只要是包含输入数量不同的处理，当区别各个处理时不正当解析麻烦的程序，则可适用于任何程序，并且有效。

在实施方式2中，对输入值仅为对象数据X的平方处理和输入值是对象数据X和中间值Y的乘法处理，执行使输入值数量一致的变换，但不限于此。若适用本发明的方法，则即便在输入值为X、Y的第1处理与输入值为Y、Z的第2处理的组等一个输入值的集合不完全包含另一输入值的集合的情况下，也可执行难破解化。此时，通过在第1处理中施加依存于输入值Z的处理(相当于实施方式2中的输入依存加法或减法)，表格化，在第2处理中施加依存于输入值X的处理，表格化即可。

(2)在实施方式2中，使用难破解化程序，执行RSA密码方式的解密处理或RSA署名方式的署名生成时处理，但只要是包含将秘密密钥设为幂数值值的幂运算处理的运算即可。例如，可以是RSA-PSS署名方式的署名方式，可以是RSA-OAEP密码方式的解密处理，也可以是RSA-KEM方式的解密处理。另外，可以是ELGamal密码方式的解密处理。

(3)在密码处理装置中，将从介质读入的难破解化程序存储在程序存储器中，但也可将该程序分几次读入，同时存储在程序存储器中，每次由CPU执行。

(4)在署名生成时的处理中，将作为输入的消息作为对象数据，计算对象数据的幂数值，但也可使用消息m，设为X＝Hash(m)，计算对象数据X的幂数值。

这里，Hash表示散列函数，Hash(m)表示消息m的散列值。使用的散列函数例如是SHA-1、SHA-224、SHA-256、SHA-384、SHA-512、MD5、WHIRLPOOL、RIPEMD128、RIPEMD160。

(5)在实施方式2中，难破解化程序记录在介质中分配，但也可使用通信路径来发送该程序。

(6)在实施方式2中，输入值变换中包含输入依存减法，输出值变换中包含输入依存减法，但不限于此。例如，也可将输入依存减法与输入依存加法配置颠倒。另外，不限于减法或加法，也可以是乘法与除法的组等。即，只要执行依存于对象数据X的变换，则可以是任何变换的组。但是，在上述方式中利用表格的分割来抑制表格大小的情况下，期望是加法与减法的组。

另外，也可在各模乘运算和各模平方运算紧前和紧后，配置依存于对该运算的一个输入值的减法和加法。

另外，在分别分解各模乘运算和各模平方运算，生成乘法运算和模运算、平方运算和模运算的情况下，也可在各乘法运算和各平方运算紧前和紧后，配置依存于对该运算的一个输入值的减法和加法。

(7)在实施方式2中，通过乘法处理和平方处理均追加输入依存加法和输入依存减法，进行表格化，但不限于此。即，在本发明中，若至少对平方的处理包含依存于对象数据X的变换(输入依存加法)，则即便解析各表格的输入输出值的关系，也难以区别乘法的表格与平方的表格，所以也可如此。

(8)在现有技术中，在使用二进制法解密RSA密码的情况下，在应用将处理变换为随机表格的现有方法的方法中，由于乘法与平方中输入数量不同，所以存在攻击者可利用该情况解析的课题。具体而言，存在可根据至各表格的输入数量来区别该表格执行乘法还是执行平方的问题。

在本发明中，对于乘法和平方的处理，生成将相同个数的自变量设为输入的表格，并且，设定表格的输出值，使输出依存于这些自变量。具体而言，通过对平方处理附加使用仅乘法所需的自变量的追加处理，进行表格化，使自变量的数量与乘法一致。并且，此时，由于输出依存于全部自变量，所以与追加实际上未处理的伪自变量的情况不同，不知是否有追加的自变量。

(9)本发明提供防止基于乘法与平方的输入数量不同的攻击的源代码难破解化程序、装置和方法。

如上所述，本发明是一种难破解化装置，将根据由一个以上数量构成的第一处理输入信息算出由一个以上数量构成的第一处理输出信息的第一处理设为输入，输出第一表格，其中具有：第一变换单元，将由一个以上数量构成的第一变换输入信息变换为由一个以上数量构成的第一变换输出信息；和第一表格生成单元，生成表示由一个以上数量构成的第一表格输入信息和由一个以上数量构成的第一表格输出信息的对应之所述第一表格，所述第一表格输入信息由所述第一处理输入信息或第一变换输入信息中包含的数量、和由一个以上数量构成的追加输入信息中包含的数量构成，所述第一表格输出信息包含所述第一处理输出信息或第一变换输出信息。

这里，所述难破解化装置还具有第二变换单元，将由一个以上数量构成的第二变换输入信息变换为由一个以上数量构成的第二变换输出信息，所述第一表格输入信息由所述第一变换输入信息中包含的数量、和所述追加输入信息中包含的数量构成，所述第一处理输入信息包含所述变换输出信息的至少一个数量，所述第二变换输入信息包含所述第一处理输出信息的至少一个数量，所述第一表格输出信息包含所述第二变换输出信息。

这里，所述第一变换单元执行的变换是基于所述第一表格输入信息的变换。

这里，所述难破解化装置具有追加输入信息决定单元，除所述第一处理外，还将根据由一个以上数量构成的第二处理输入信息算出由一个以上数量构成的第二处理输出信息的第二处理设为输入，将所述第二处理输入信息中、未包含于所述第一处理输入信息中的数量设为所述追加输入信息。

这里，所述第二处理是根据由第一数量与第二数量构成的所述第二处理输入信息、算出由所述第一数量与所述第二数量的积构成的所述第二处理输出信息的处理，所述第一处理是根据由所述第一数量构成的所述第一处理输入信息、算出由所述第一数量的平方构成的所述第一处理输出信息的处理。

这里，所述难破解化装置是一种难破解化装置，除所述第一处理与所述第二处理外，还将根据包含一个以上数量、或至少一个第二中间值信息数量的第三处理输入信息、算出由一个以上数量构成的第三处理输出信息的第三处理设为输入，输出所述第一表格和第二表格，其中，具有第三变换单元，将由一个以上数量构成的第三变换输入信息变换为由一个以上数量构成的第三变换输出信息；第二表格生成单元，生成表示由一个以上数量构成的第二表格输入信息与由一个以上数量构成的第二表格输出信息的对应的所述第二表格；和第三变换单元，将由一个以上数量构成的第三变换输入信息变换为由一个以上数量构成的第三变换输出信息；所述第二表格输入信息包含至少一个所述第一表格输出信息，所述第三变换输入信息包含至少一个所述第一表格输出信息，所述第二表格输出信息包含所述第三处理输出信息。

这里，所述难破解化装置除所述第一处理、所述第二处理、所述第三处理外，将根据由一个以上数量构成的第四处理输入信息、算出由一个以上数量构成的第四处理输出信息的第四处理设为输入，所述第二表格输入信息包含至少一个所述第一表格输出信息中包含的数量、与第二追加输入信息，具有第二追加输入信息决定单元，将所述第四处理输入信息中、未包含于所述第三处理输入信息中的数量设为所述第二追加输入信息。

这里，所述难破解化装置中由所述第一变换单元和所述第三变换单元执行的变换还是基于所述第一处理输入信息中包含的数量中、所述第三处理输入信息中包含的数量的变换。

这里，所述难破解化装置具有第四变换单元，将由一个以上数量构成的第四变换输入信息变换为由一个以上数量构成的第四变换输出信息，所述第四变换输入信息包含所述第三处理输出信息的至少一个数量，所述第二表格输出信息包含所述第四处理输出信息，代替包含所述第三处理输出信息。

这里，所述难破解化装置具有处理分割单元，将根据由一个以上数量构成的第五处理输入信息、算出由一个以上数量构成的第五处理输出信息的第五处理设为输入，将所述第五处理分割成根据由4个数量构成的处理输入信息、算出由一个数量构成的处理输出信息的一个以上的4输入1输出处理、与根据由2个数量构成的处理输入信息、算出由一个数量构成的处理输出信息的一个以上的2输入1输出处理，将所述4输入1输出处理与所述2输入1输出处理的至少一个设为所述第一处理，将所述4输入1输出处理与所述2输入1输出处理的至少一个设为所述第三处理。

另外，本发明是一种难破解化方法，将根据由一个以上数量构成的第一处理输入信息算出由一个以上数量构成的第一处理输出信息的第一处理设为输入，输出第一表格，其中，具有第一变换步骤，将由一个以上数量构成的第一变换输入信息变换为由一个以上数量构成的第一变换输出信息；和第一表格生成步骤，生成表示由一个以上数量构成的第一表格输入信息和由一个以上数量构成的第一表格输出信息的对应之所述第一表格，所述第一表格输入信息由所述第一处理输入信息或第一变换输入信息中包含的数量、和由一个以上数量构成的追加输入信息中包含的数量构成，所述第一表格输出信息包含所述第一处理输出信息或第一变换输出信息。

这里，所述难破解化方法还具有第二变换步骤，将由一个以上数量构成的第二变换输入信息变换为由一个以上数量构成的第二变换输出信息，所述第一表格输入信息由所述第一变换输入信息中包含的数量、和所述追加输入信息中包含的数量构成，所述第一处理输入信息包含所述变换输出信息的至少一个数量，所述第二变换输入信息包含所述第一处理输出信息的至少一个数量，所述第一表格输出信息包含所述第二变换输出信息。

这里，所述第一变换步骤执行的变换是基于所述第一表格输入信息的变换。

这里，所述难破解化方法具有追加输入信息决定步骤，除所述第一处理外，还将根据由一个以上数量构成的第二处理输入信息算出由一个以上数量构成的第二处理输出信息的第二处理设为输入，将所述第二处理输入信息中、未包含于所述第一处理输入信息中的数量设为所述追加输入信息。

这里，所述第二处理是根据由第一数量与第二数量构成的所述第二处理输入信息、算出由所述第一数量与所述第二数量的积构成的所述第二处理输出信息的处理，所述第一处理是根据由所述第一数量构成的所述第一处理输入信息、算出由所述第一数量的平方构成的所述第一处理输出信息的处理。

这里，所述难破解化方法是一种难破解化方法，除所述第一处理与所述第二处理外，还将根据包含一个以上数量、或至少一个第二中间值信息数量的第三处理输入信息、算出由一个以上数量构成的第三处理输出信息的第三处理设为输入，输出所述第一表格和第二表格，其中，具有第三变换步骤，将由一个以上数量构成的第三变换输入信息变换为由一个以上数量构成的第三变换输出信息；第二表格生成步骤，生成表示由一个以上数量构成的第二表格输入信息与由一个以上数量构成的第二表格输出信息的对应的所述第二表格；和第三变换步骤，将由一个以上数量构成的第三变换输入信息变换为由一个以上数量构成的第三变换输出信息，所述第二表格输入信息包含至少一个所述第一表格输出信息，所述第三变换输入信息包含至少一个所述第一表格输出信息，所述第二表格输出信息包含所述第三处理输出信息。

这里，所述难破解化方法具有第二追加输入信息决定步骤，除所述第一处理、所述第二处理、所述第三处理外，将根据由一个以上数量构成的第四处理输入信息、算出由一个以上数量构成的第四处理输出信息的第四处理设为输入，所述第二表格输入信息包含至少一个所述第一表格输出信息中包含的数量、与第二追加输入信息，将所述第四处理输入信息中、未包含于所述第三处理输入信息中的数量设为所述第二追加输入信息。

这里，所述难破解化方法中由所述第一变换步骤和所述第三变换步骤执行的变换是基于所述第一处理输入信息中包含的数量中、所述第三处理输入信息中包含的数量的变换。

这里，所述难破解化方法具有第四变换步骤，将由一个以上数量构成的第四变换输入信息变换为由一个以上数量构成的第四变换输出信息，所述第四变换输入信息包含所述第三处理输出信息的至少一个数量，所述第二表格输出信息包含所述第四处理输出信息，代替包含所述第三处理输出信息。

这里，所述难破解化方法将根据由一个以上数量构成的第五处理输入信息、算出由一个以上数量构成的第五处理输出信息的第五处理设为输入，具有处理分割步骤，将所述第五处理分割成根据由4个数量构成的处理输入信息、算出由一个数量构成的处理输出信息的一个以上的4输入1输出处理、与根据由2个数量构成的处理输入信息、算出由一个数量构成的处理输出信息的一个以上的2输入1输出处理，将所述4输入1输出处理与所述2输入1输出处理的至少一个设为所述第一处理，将所述4输入1输出处理与所述2输入1输出处理的至少一个设为所述第三处理。

另外，本发明是由所述难破解化装置、程序和执行所述程序的信息处理装置构成的信息处理系统，所述程序包含使用所述第一表格、根据所述第一表格输入信息来算出所述第一表格输出信息的处理。

另外，本发明是由所述难破解化装置、程序和执行所述程序的信息处理装置构成的信息处理系统中的程序，包含使用所述第一表格、根据所述第一表格输入信息来算出所述第一表格输出信息的处理。

这里，所述第一处理是解密处理的一部分。

这里，所述第一处理是署名生成处理的一部分。

另外，本发明是记录所述介质的记录介质。

另外，本发明是由所述难破解化装置、程序和执行所述程序的信息处理装置构成的信息处理系统中的信息处理装置，所述程序包含使用所述第一表格、根据所述第一表格输入信息来算出所述第一表格输出信息的处理。

另外，本发明是一种难破解化装置的集成电路，将根据由一个以上数量构成的第一处理输入信息算出由一个以上数量构成的第一处理输出信息的第一处理设为输入，输出第一表格，其中具有：第一变换单元，将由一个以上数量构成的第一变换输入信息变换为由一个以上数量构成的第一变换输出信息；和第一表格生成单元，生成表示由一个以上数量构成的第一表格输入信息和由一个以上数量构成的第一表格输出信息的对应之所述第一表格，所述第一表格输入信息由所述第一处理输入信息或第一变换输入信息中包含的数量、和由一个以上数量构成的追加输入信息中包含的数量构成，所述第一表格输出信息包含所述第一处理输出信息或第一变换输出信息。

另外，本发明是执行包含所述第一处理的信息处理的信息处理装置的集成电路，具有表格保持单元，保持所述第一表格；和输出值算出单元，将所述第一表格输入信息设为输入，输出所述第一表格输出信息。

另外，所述难破解化装置输出程序代替所述第一表格，所述难破解化装置还具有程序生成单元，生成由所述第一表格、和由一个以上的程序命令构成的程序命令群构成的所述程序，所述程序命令群包含将所述第一表格输入信息设为输入、输出对应的所述第一表格输出信息的处理。

另外，本发明是一种难破解化装置，难破解化包含执行使用了一个以上输入值的集合、即第1输入值群的处理的第1处理、和执行使用了包含比所述第1处理多的输入值的集合、即第2输入值群的处理的第2处理的程序，生成难破解化程序，其中，具备受理所述程序的输入单元；表格生成单元，生成将所述第2输入值群与所述第2处理结果对应的第2表格、和将所述第1输入值群和追加输入值群与变换后的第1处理的处理结果对应的第1表格；和程序生成单元，将所述程序中的所述第1处理置换为使用所述第1输入值群从所述第1表格中取出所述处理结果的处理，且将所述第2处理置换为使用所述第2输入值群从所述第2表格中取出所述处理结果的处理，生成所述难破解化程序，所述追加输入值群是所述第2输入值群中未包含于所述第1输入值群中的输入值的集合，所述变换后的第1处理是向所述第1处理中追加使用所述追加输入值群的处理的处理。

根据这些构成，可防止基于乘法与平方的输入数量不同的攻击，其价值大。

(10)上述各装置具体而言，是由微处理器、ROM、RAM、硬盘单元、显示器单元、键盘、鼠标等构成的计算机系统。所述RAM或硬盘单元中存储计算机程序。通过所述微处理器根据所述计算机程序动作，各装置实现其功能。这里，计算机程序为了实现规定功能，组合多个表示对计算机的指令之命令代码来构成。

(11)构成上述各装置的构成要素的一部分或全部也可由一个系统LSI(Large Scale Integration：大规模集成电路)构成。系统LSI是在一个芯片上集成多个构成部制造的超多功能LSI，具体而言，是包含微处理器、ROM、RAM等构成的计算机系统。在所述RAM中存储计算机程序。通过所述微处理器根据所述计算机程序动作，系统LSI实现其功能。

另外，构成上述各装置的构成要素的各部也可单独单芯片化，或包含部分或全部地单芯片化。

另外，这里为系统LSI，但也可根据集成度的不同称为IC、LSI、超LSI、甚LSI。另外，集成电路化的方法不限于LSI，也可由专用电路或通用处理器来实现。也可利用在LSI制造后可编程的FPGA(FieldProgrammable GateArray)或可再构成LSI内部的电路单元连接或设定的可重构处理器。

并且，如果因半导体技术的进步或派生的其它技术而出现置换LSI的集成电路化技术，则当然也可使用该技术来进行功能块的集成化。可适应于生物技术等。

(12)构成上述各装置的构成要素的一部分或全部也可由可拆装于各装置上的IC卡或单体模块构成。所述IC卡或所述模块是由微处理器、ROM、RAM等构成的计算机系统。所述IC卡或所述模块也可包含上述超多功能LSI。通过微处理器根据计算机程序动作，所述IC卡或所述模块实现其功能。该IC卡或该模块也可具有耐篡改性。

(13)本发明也可以是上述所示的方法。另外，也可是由计算机来实现这些方法的计算机程序，或是由所述计算机程序构成的数字信号。

(14)另外，本发明也可将所述计算机程序或所述数字信号记录在计算机可读的记录介质中，例如软盘、硬盘、CD-ROM、MO、DVD、DVD-ROM、DVD-RAM、BD(Blu-ray Disc)、半导体存储器等中。另外，也可以是记录在这些记录介质中的所述数字信号。

(15)另外，本发明也可经由电气通信线路、无线或有线通信线路、以因特网为代表的网络、数据广播等来传送所述计算机程序或所述数字信号。

(16)另外，本发明也可以是具备微处理器与存储器的计算机系统，所述存储器存储上述计算机程序，所述微处理器根据所述计算机程序动作。

(17)另外，也可通过将所述程序或所述数字信号记录在所述记录介质中移送，或经由所述网络等移送所述程序或所述数字信号，由独立的其它计算机系统来实施。

(18)另外，本发明也可以是上述实施方式及变形例的组合。

产业上的可利用性

根据上述构成，可防止基于乘法与平方的输入数量不同的攻击。

构成本发明的各装置在通过密码信息后解密，不让第三者知道地秘密处理信息，对信息实施数字署名，并实施署名验证，从而防止信息的篡改或他人的冒充等，需要安全或确实处理信息的产业中，可经营地继续反复使用。另外，构成本发明的各装置可在电器机器制造产业中经营地继续反复制造、出售。

表格生成步骤，对各第2基本运算，生成得到与一组运算等效的运算结果的表格，并生成参照该表格的参照命令，所述一组运算包括该第2基本运算紧前配置的所述输入依存变换、该第2基本运算和该第2基本运算紧后配置的所述输入依存逆变换；和

输出步骤，输出包含所生成的所述表格及所述参照命令的难破解化程序。

14、一种程序难破解化装置中使用的程序难破解化用计算机程序，该程序难破解化装置使信息安全程序难破解化，该信息安全程序包含使用密钥信息来安全或确实地处理对象信息的安全运算，其特征在于，

所述计算机程序让计算机执行以下步骤：

取得步骤，取得所述信息安全程序，该信息安全程序以由密钥信息确定的顺序来配置多个基本运算以便与所述安全运算等效，所述多个基本运算包括需要多个输入的第1基本运算和仅需要所述多个输入的一部分的第2基本运算；

变换步骤，对所述信息安全程序中包含的各第2基本运算，在该第2基本运算前后，配置与该第2基本运算中不需要的输入相依存的输入依存变换和作为其逆变换的输入依存逆变换；

表格生成步骤，对各第2基本运算，生成得到与一组运算等效的运算结果的表格，并生成参照该表格的参照命令，所述一组运算包括该第2基本运算紧前配置的所述输入依存变换、该第2基本运算和该第2基本运算紧后配置的所述输入依存逆变换；和

输出步骤，输出包含所生成的所述表格及所述参照命令的难破解化程序。

15、(追加)根据权利要求1所述的程序难破解化装置，其特征在于：

所述变换单元分别配置依存于与所述第1基本运算需要的输入数量相同数量的输入的变换，作为所述输入依存变换和所述输入依存逆变换。

16、(追加)根据权利要求16所述的程序难破解化装置，其特征在于：

所述输入依存变换和所述输入依存逆变换分别依存于所述第1基本运算需要且所述第2基本运算不需要的输入。