信息安全装置、信息安全方法、计算机程序、计算机可读取的记录媒体及集成电路

摘要

提供一种对抗对RSA加密等的信息安全装置的简单功率攻击(SPA)的信息安全装置、信息安全方法、计算机程序、计算机可读取的记录媒体及集成电路。信息安全装置使用与蒙哥马利区域中的1之间的乘法运算。蒙哥马利区域中的1依存于比模p的位的数目大的整数k及模而决定，所以不知道p和k的攻击者难以进行解析。此外，即使万一在解析者能够预测到汉明重量的情况下，通过随机地变更k或模，也进一步提高了对SPA的安全性。

说明书

技术领域

本发明涉及进行使用私钥的公钥加密处理及签名处理的信息安全装置的耐篡改技术。

背景技术

近年来，随着信息通信技术的普及，信息安全技术的重要性显著增加。作为这样的信息安全技术之一，加密技术为了进行隐私的保护及通信对方的确认而使用。

但是，如果想要通过加密技术保护什么，则会出现想要将加密破解而得到它的人。例如，利用加密处理时的计算时间及消耗功率等根据私钥的值而不同的特性求出私钥的旁道攻击成为问题(例如非专利文献1)。

其中，作为代表性的问题，有对RSA加密方式、更准确地说是使用私钥的RSA签名的签名处理、或RSA加密的解密处理的简单功率攻击(SAP，Simple Power Analysis)。RSA加密方式的主要的处理是以私钥为幂的幂乘运算，幂乘运算通过平方运算与乘法运算的反复进行来实现。在此情况下，对应的私钥的位是“0”时不进行乘法运算、仅在“1”时进行乘法运算，所以在SPA中，根据通过消耗功率的波形判断得到的乘法运算及平方运算的序列信息来求出私钥。

为了对抗该SPA，只要在私钥的相应位是“0”的情况下也进行乘法运算就可以。以下，对两个具体的现有方法进行说明。

在第1方法中，当私钥的相应位是“0”时与“1”相乘(例如非专利文献2)。由于即使与“1”相乘结果也不变化，所以与实质上不实施乘法运算是相同的。这样，由于不依存于私钥的位值而进行乘法运算，所以不能根据乘法运算的有无来求出私钥。

此外，在对抗该SPA的第2方法中，进行控制，以使得不论位是“0”还是“1”，都首先进行乘法运算，仅在位是“1”的情况下使用乘法运算结果、在“0”的情况下不使用乘法运算结果(例如专利文献1、专利文献2)。该方法也不依存于位值而进行乘法运算，所以不能根据乘法运算的有无来求出私钥。

非专利文献1：现実の脅威「サイドチヤネル解析」(1)(现实的威胁“旁道攻击解析”(1))，日经エレクトロニクス2005.7.18号

非专利文献2：“R S A暗号の電力解析法による攻撃とその对策”(RSA加密的功率解析法的攻击和其对策)(Power Analysis andCountermeasure of RSA Cryptosystem)，電子情報通信学会論文誌A Vol.J88-A，No.52005

非专利文献3：P.L.Montgomery，“Modular Multiplication without TrialDivision，”Mathematics of Computation，Vol.44，No.170，pp.519-521(1985)

专利文献1：日本特开2000-165375号公报

专利文献2：美国专利第6408075号公报

但是，在对抗SPA的上述第1方法，由于向乘法运算的输入的一方是在汉明重量(hamming weight)中有偏倚的“1”，所以它对功率变化有影响而能够区别与“1”的相乘，有可能会被非法地解析。

此外，对于第2方法，以乘法运算时为目标，例如通过对电源电压施加尖峰噪声等的、故意产生错误的错误攻击，有可能解析私钥。详细地讲，如果在乘法运算时发生错误、其影响不在输出中表现出来，则可以解析出不使用结果的、即对应的私钥的位是“0”。相反，如果错误的影响表现在输出中，则可以解析出私钥的对应的位是“1”。该解析即使植入了作为对错误攻击的通常的对策的验算(proof)功能也可能实现。

发明内容

所以，在本发明中，目的是在使用第1方法的情况下，解决上述问题，提供一种能够对抗SPA的信息安全装置、信息安全方法、计算机程序、记录媒体及集成电路。另外，在本发明中，由于以第1方法为基础，所以上述第2方法的攻击不再有意义。

为了达到上述目的，本发明是一种信息安全装置，为了进行在规定的模下将输入值整数次幂的幂乘剩余运算，对上述整数的各位的每个重复乘法运算而计算幂乘值，进行上述输入值的安全或可靠的处理，其特征在于，具备：判断机构，判断上述整数的1个位的值是否是0；以及乘法运算机构，在判断为所取得的位的值是0的情况下，进行使用对于值1的蒙哥马利变换值的乘法剩余运算。

根据该结构，由于使用与对于“1”的蒙哥马利变换值之间的乘法剩余运算，所以能够避免在汉明重量中有偏倚的“1”的使用，能够对抗SPA而使非法的解析变得困难。

这里，也可以是，上述信息安全装置是基于RSA方式将RSA密文解密的RSA解密装置、或基于RSA方式对签名对象的消息进行签名数据的生成的RSA签名装置；该信息安全装置还包括：取得机构，取得RSA密文作为上述输入值，或者取得签名对象的消息作为上述输入值；存储机构，存储有上述整数作为私钥；以及输出机构，作为从上述RSA密文解密而得到的明文、或者作为对上述消息的签名数据，输出计算出的上述幂乘值。

根据该结构，在基于RSA方式将RSA密文进行解密的RSA解密中，以及，在基于RSA方式对签名对象的消息进行签名数据的生成的RSA签名中，能够避免在汉明重量中有偏倚的“1”的使用，能够使SPA的非法的解析变得困难。

这里，也可以是，上述信息安全装置具备：取得机构，取得输入值；存储机构，存储有整数；初始化机构，在保存运算结果的值的运算值变量中保存初始值；提取机构，从上述存储机构中，从上述整数的高位的位开始提取1个位的值；平方运算机构，将根据保存在上述运算值变量中的值的至少1次平方剩余运算而得到的值，覆盖写入至上述运算值变量；上述判断机构，判断所取得的位的值是否是0；上述乘法运算机构，在判断为所取得的位的值是0的情况下，将根据保存在上述运算值变量中的值和对1的蒙哥马利变换值之间的乘法剩余运算而得到的值覆盖写入至上述运算值变量，在判断为是0以外的情况下，将根据保存在上述运算值变量中的值和由上述输入值决定的值之间的乘法剩余运算而得到的值，覆盖写入至上述运算值变量；重复控制机构，对于上述整数的所有的位，对上述提取机构、上述平方运算机构、上述判断机构及上述乘法运算机构进行控制，以重复进行值的取得、平方剩余运算、判断、和乘法剩余运算；以及输出机构，如果对上述整数的所有的位结束了上述重复，则输出基于保存在上述运算值变量中的值的值。

此外，也可以是，上述信息安全装置具备：取得机构，取得输入值，保存在输入值变量中；存储机构，存储有整数；初始化机构，在保存运算结果的值的运算值变量中保存初始值；提取机构，从上述存储机构中，从上述整数的低位的位开始提取1个位的值；平方运算机构，将根据保存在上述输入值变量中的值的至少1次平方剩余运算而得到的值覆盖写入至上述输入值变量；上述判断机构，判断所取得的位的值是否是0；上述乘法运算机构，在判断为所取得的位的值是0的情况下，将根据保存在上述运算值变量中的值和对1的蒙哥马利变换值之间的乘法剩余运算而得到的值覆盖写入至上述运算值变量，在判断为是0以外的情况下，将根据保存在上述运算值变量中的值和由上述输入值变量决定的值之间的乘法剩余运算而得到的值，覆盖写入至上述运算值变量；重复控制机构，对于上述整数的所有的位，对上述提取机构、上述平方运算机构、上述判断机构及上述乘法运算机构进行控制，以重复进行值的取得、平方剩余运算、判断、和乘法剩余运算；以及输出机构，如果对上述整数的所有的位结束了上述重复，则输出基于保存在上述运算值变量中的值的值。

信息安全装置对应于实施方式的IC卡100，取得机构对应于输入输出部102，存储机构对应于私钥保存部113，初始化机构对应于图4的步骤S 102，提取机构对应于提取部122，平方运算机构对应于平方运算部115，判断机构对应于图4的步骤S106，乘法运算机构对应于乘法运算部116，重复控制机构对应于控制部114，输出机构对应于蒙哥马利逆变换部120及输入输出部102。

根据这些结构，能够进行从上述整数的高位的位开始或从低位的位开始的运算。

这里，也可以是，上述信息安全装置还包括蒙哥马利变换机构，该蒙哥马利变换机构计算对于值1的蒙哥马利变换值；上述乘法运算机构在上述乘法剩余运算中，使用由上述蒙哥马利变换机构计算出的蒙哥马利变换值。

蒙哥马利变换机构对应于第2蒙哥马利变换部112。

根据该结构，通过蒙哥马利变换机构计算对于值1的蒙哥马利变换值，乘法运算机构使用计算出的蒙哥马利变换值，所以不进行多次对值1的蒙哥马利变换值的计算，而能够削减运算次数。

这里，也可以是，上述信息安全装置还具备：模设定机构，设定上述模的值；以及整数设定机构，随机地选择比上述模的有效位的数目大的整数k；上述蒙哥马利变换机构根据所设定的上述模的值，利用上述整数k，计算上述蒙哥马利变换值。

模设定机构对应于模设定部117，整数设定机构对应于整数设定部118。

根据该结构，由于在蒙哥马利变换值的计算中使用比上述模的有效位的数目大、而且是随机地选择的整数k，所以能够进一步避免关于“1”的汉明重量的偏倚。

这里，也可以是，上述蒙哥马利变换机构在上述模下计算值2的k次幂值，作为上述蒙哥马利变换值。

根据该结构，能够可靠地计算蒙哥马利变换值。

这里，也可以是，上述蒙哥马利变换机构在作为上述模的值的随机倍的模下计算值2的k次幂值，作为上述蒙哥马利变换值。

根据该结构，能够计算可进一步避免关于“1”的汉明重量的偏倚的蒙哥马利变换值。

这里，也可以是，上述信息安全装置中，上述模设定机构进一步设定作为上述模的值的随机倍的模；上述蒙哥马利变换机构在由模设定机构进一步设定的上述模下计算值2的k次幂值。

根据该结构，能够计算可进一步避免关于“1”的汉明重量的偏倚的蒙哥马利变换值。

这里，也可以是，上述整数设定机构每当取得输入值时，随机地变更上述整数k的值。

根据该结构，能够使利用了最初的输入值的SPA的结果，在其他的输入值下的使用变得困难。

这里，也可以是，上述模设定机构每当取得输入值时，随机地变更在上述蒙哥马利变换机构中使用的上述模的值。

根据该结构，能够使利用了最初的输入值的SPA的结果，在其他的输入值下的使用变得困难。

这里，也可以是，上述整数设定机构在上述重复的中途，随机地变更上述整数k的值。

根据该结构，能够使重复的中途的过程中的SPA的结果，在重复的其他过程中的使用变得困难。

这里，也可以是，上述模设定机构在上述重复的中途，随机地变更在上述蒙哥马利变换机构中使用的上述模的值。

根据该结构，能够使重复的中途的过程中的SPA的结果，在重复的其他过程中的使用变得困难。

这里，也可以是，上述整数设定机构根据来自外部的指示，随机地变更上述整数k的值。

根据该结构，能够使来自外部的指示之前的SPA的结果，在来自外部的指示之后的使用变得困难。

这里，也可以是，上述模设定机构根据来自外部的指示，随机地变更在上述蒙哥马利变换机构中使用的上述模的值。

根据该结构，能够使来自外部的指示之前的SPA的结果，在来自外部的指示之后的使用变得困难。

这里，也可以是，上述信息安全装置还包括蒙哥马利变换机构，该蒙哥马利变换机构计算对于上述输入值的蒙哥马利变换值；上述乘法运算机构在判断为所取得的位的值是0以外的情况下，利用由上述蒙哥马利变换机构计算出的上述蒙哥马利变换值进行乘法剩余运算。

蒙哥马利变换机构对应于第1蒙哥马利变换部111。

根据该结构，在判断为所取得的位的值是0以外的情况下，也能够对抗SPA而使非法的解析变得困难。

这里，也可以是，上述信息安全装置还具备：模设定机构，设定上述模的值；以及整数设定机构，随机地选择比上述模的有效位的数目大的整数k；上述蒙哥马利变换机构基于设定的上述模的值，利用上述整数k，计算上述蒙哥马利变换值。

模设定机构对应于模设定部117，整数设定机构对应于整数设定部118。

根据该结构，由于在蒙哥马利变换值的计算中使用比上述模的有效位的数目大、而且是随机地选择的整数k，所以能够进一步避免关于输入值的汉明重量的偏倚。

这里，也可以是，上述蒙哥马利变换机构在上述模下计算值2的k次幂值，并将上述输入值与计算出的值相乘得到的值，作为上述蒙哥马利变换值。

根据该结构，能够可靠地计算出蒙哥马利变换值。

这里，也可以是，上述蒙哥马利变换机构在作为上述模的值的随机倍的模下计算值2的k次幂值，作为上述蒙哥马利变换值。

根据该结构，能够计算出进一步避免关于输入值的汉明重量的偏倚的蒙哥马利变换值。

附图说明

图1是表示作为有关本发明的1个实施方式的内容再现系统1的结构的系统结构图。

图2是表示IC卡100及DVD播放器200的结构的框图。

图3是表示公钥解密部101的结构的框图。

图4是表示公钥解密部101的高速幂乘剩余运算的动作的流程图。

图5是表示公钥解密部101的另一高速幂乘剩余运算的动作的流程图。

图6是从私钥的低位的位开始处理的情况下的公钥解密部110的高速幂乘剩余运算的动作的流程图。

标号说明

1 内容再现系统

10 网络

100 IC卡

101 公钥解密部

102 输入输出部

111 第1蒙哥马利变换部

112 第2蒙哥马利变换部

113 私钥保存部

114 控制部

115 平方运算部

116 乘法运算部

117 模设定部

118 整数设定部

119 设定控制部

120 蒙哥马利逆变换部

200 DVD播放器

201 监视器

202 扬声器

211 通信部

212 输入输出部

213 解密部

214 解密部

215 再现部

216 驱动部

300 DVD

400 服务器装置

具体实施方式

对作为有关本发明的1个实施方式是内容再现系统1进行说明。

1、内容再现系统1的结构

内容再现系统1如图1所示，由IC卡100、DVD播放器200及服务器装置400构成。DVD播放器200及服务器装置400经由网络10相互连接。

在DVD播放器200中，由使用者安装DVD300。DVD300如图2所示，记录有加密内容301及加密内容密钥302。加密内容301是利用内容密钥对由影像及声音构成的内容实施加密算法AES(Advanced EncryptionStandard：高级加密标准)而生成的，加密内容密钥302是利用表示允许使用上述内容的许可密钥L对上述内容密钥实施加密算法AES而生成的。

服务器装置400根据DVD播放器200的请求，利用IC卡100的使用者的公钥(e、p)，对许可密钥L实施加密算法RSA，生成加密许可密钥C。

C＝L^emod p

另外，关于RSA的公钥的生成，由于是公知的，所以省略说明。

接着，服务器装置400根据DVD播放器200的请求，将生成的加密许可密钥C经由网络10向DVD播放器200发送。

DVD播放器200如图2所示，由通信部211、输入输出部212、解密部213、解密部214、再现部215及驱动部216构成，在DVD播放器200上连接着监视器201及扬声器202。

DVD播放器200的通信部211从服务器装置400经由网络10接收加密许可密钥C。在DVD播放器200中，由使用者安装IC卡100。DVD播放器200的输入输出部212将接收到的加密许可密钥C向IC卡100输出。

IC卡100由公钥解密部101及输入输出部102构成。IC卡100的输入输出部102从DVD播放器200获取加密许可密钥C，公钥解密部101将作为输入数据获取的加密许可密钥C如后述那样解密，作为输出数据而生成解密许可密钥，输入输出部102将生成的解密许可密钥向DVD播放器200输出。

DVD播放器200的输入输出部212从IC卡100获取解密许可密钥，驱动部216从DVD300读出加密内容301及加密内容密钥302，解密部213利用所获取的解密许可密钥将加密内容密钥302解密而生成解密内容密钥，解密部214利用生成的解密内容密钥将加密内容301解密而生成解密内容，再现部215再现解密内容而生成影像信号及声音信号，将生成的影像信号向监视器201输出，将生成的声音信号向扬声器202输出。

这里，IC卡100及DVD播放器200分别具体而言是由微处理器、ROM、RAM等构成的计算机系统。在上述RAM中存储有计算机程序。通过上述微处理器按照上述计算机程序动作，各装置实现其功能。

另外，在图2中，表示DVD播放器200的各结构部的各块通过连接线与其他块连接。但是，省略了一部分连接线。这里，各连接线表示传递信号及信息的路径。此外，连接在表示解密部213的块上的多个连接线中的、在连接线上描绘有钥匙标志的连接线，表示向解密部213传递作为密钥的信息的路径。对于表示解密部214的块也同样。

这里，IC卡100是通过在规定的模下对输入值进行整数次幂的幂乘剩余运算进行输入值的安全的处理的信息安全装置。

2、公钥解密部101的结构

公钥解密部101如图3所示，由存储部121、第1蒙哥马利(Montgomery)变换部111、第2蒙哥马利变换部112、私钥保存部113、控制部114、平方运算部115、乘法运算部116、模设定部117、整数设定部118、设定控制部119及蒙哥马利逆变换部120构成。

公钥解密部101在内部中存储有私钥S和模p，将输入数据C作为输入进行公钥加密的计算，输出计算结果的输出数据M＝C^smod p。这里，输出数据M是以私钥S为幂、以p为模的输入数据C的幂乘剩余运算值。mod p表示用p除时的余数。另外，在本实施方式中，上述公钥加密的计算是RSA加密的解密处理。因而，输入数据对应于密文C，输出数据对应于明文M。具体而言，输入数据是上述加密许可密钥，输出数据是上述解密许可密钥。

公钥解密部101从上述私钥S的各位的高位开始，1位1位地重复进行所设定的模下的蒙哥马利区域中的平方运算和乘法运算——即高速幂指数运算。对公钥解密部101的整体的动作在后面叙述。

(1)模设定部117、整数设定部118及设定控制部119

模设定部117通过设定控制部119的控制，设定在蒙哥马利变换、平方运算、乘法运算中使用的模p。模设定部117将设定后的模p向第1蒙哥马利变换部111、第2蒙哥马利变换部112、平方运算部115、乘法运算部116及蒙哥马利逆变换部120输出。

整数设定部118通过设定控制部119的控制，随机地设定比p的位的数目大的整数k。另外，这里所谓的p的“位的数目”是p之中的从被设定为值“1”的最高位的位的位置到最低位的位的位置的位长，是指所谓的“有效位数”。整数设定部118将整数k向第1蒙哥马利变换部111、第2蒙哥马利变换部112、平方运算部115、乘法运算部116及蒙哥马利逆变换部120输出。

设定控制部119对整数设定部118控制整数k的设定范围及设定变更的定时。作为设定变更的定时的一例，设定控制部119可以每当输入数据C的值变化时进行变更，也可以在输入数据C的运算中途变更。

这里设定的整数k和模p在以后的蒙哥马利变换、平方运算、乘法运算及蒙哥马利逆变换中使用。

(2)存储部121、第1蒙哥马利变换部111及第2蒙哥马利变换部112

存储部121从输入输出部102获取输入数据C，存储所获取的输入数据C。

第1蒙哥马利变换部111从存储部121读出输入数据C，从模设定部117获取模p，从整数设定部118获取整数k。接着，使用输入数据C、模p及整数k，通过下式计算C的蒙哥马利变换值B。

蒙哥马利变换值B＝C×(2^k)mod p

接着，第1蒙哥马利变换部111将计算出的蒙哥马利变换值B向控制部114输出。

此外，第2蒙哥马利变换部112从模设定部117获取模p，从整数设定部118获取整数k。接着，利用模p及整数k，通过下式计算“1”的蒙哥马利变换值A。

蒙哥马利变换值A＝(2^k)mod p

接着，第2蒙哥马利变换部112将计算出的蒙哥马利变换值A向控制部114输出。

另外，以后将蒙哥马利变换记作Mon_{k，p}(X)。

Mon_{k，p}(X)＝X×2^k mod p    (式1)

另外，变换函数的{k，p}表示蒙哥马利变换值依存于整数k、模p。如果使用该表示方法，则由第1蒙哥马利变换部111输出的蒙哥马利变换值B是Mon_{k，p}(C)，由第2蒙哥马利变换部112输出的蒙哥马利变换值A是Mon{k，p}(1)。

(3)私钥保存部113

私钥保存部113保存着公钥加密的私钥S。私钥S为了确保安全性而至少需要2048位以上。

(4)提取部122、控制部114、平方运算部115及乘法运算部116

提取部122根据控制部114的指示，从保存于私钥保存部113中的私钥S的各位的高位开始1位1位地提取，将提取出的位的值向控制部114输出。

控制部114从私钥S的高位开始对1位重复进行平方运算和乘法运算的处理。例如，在私钥是2048位的情况下重复2048次平方运算和乘法运算的处理。在重复结束后，蒙哥马利逆变换部120对其运算结果进行蒙哥马利逆变换，公钥解密部101输出M＝C^S mod p。

控制部114进行上述重复控制，并且，当私钥的相应位是“1”时选择第1蒙哥马利变换部111的输出值，当“0”时选择第2蒙哥马利变换部112的输出值。

平方运算部115及乘法运算部116分别执行蒙哥马利区域中的平方运算及乘法运算。

这里的蒙哥马利区域的乘法运算是用来对变换到蒙哥马利区域的两个输入值、例如Mon_{k，p}(X)和Mon_{k，p}(Y)之积进行蒙哥马利约简(Montgomery reduction)处理，求出蒙哥马利区域的乘法运算结果Mon{k，p}(Z)＝Mon_{k，p}(X×Y)的运算。平方运算对应于上述X与Y相同的情况。

这里，蒙哥马利约简处理是将倍长值U(在上述中是X×Y)不进行除法而高速地实现U×(2^k)^-1mod p的运算的方法。关于蒙哥马利约简的详细情况详见例如非专利文献3。

另外，假设在位的数目是2048位的情况下，通过2048位的乘法运算器实现平方运算部115和乘法运算部116的安装规模变得巨大，是不现实的。因此，一般通过重复使用例如32位左右的乘法运算器的多倍长运算方法实现。

(5)蒙哥马利逆变换部120

蒙哥马利逆变换部120对蒙哥马利区域中的平方运算与乘法运算的重复进行的最终结果实施蒙哥马利逆运算，求出输出数据M。以后，将蒙哥马利逆运算表示为

Mon_{k，p}^-1()。

Mon_{k，p}^-1(X)＝X×(2^k)^-1mod p    (式2)

另外，关于蒙哥马利变换和蒙哥马利逆运算，式3成立。

Mon_{k，p}^-1(Mon_{k，p}(X))＝X     (式3)

蒙哥马利逆变换部120将输出数据M向输入输出部102输出。

3、公钥解密部101的动作

利用图4所示的流程图，对公钥解密部101的高速幂乘剩余运算的动作进行说明。

模设定部117决定模p，整数设定部118决定整数k，第1蒙哥马利变换部111计算蒙哥马利变换值B＝C×(2^k)modp，第2蒙哥马利变换部112计算蒙哥马利变换值A＝(2^k)mod p(步骤S101)。

控制部114选择第2蒙哥马利变换部112的蒙哥马利变换值A，在作为设在保存运算结果的值的运算值区域中的变量的、运算结果W中，写入作为初始值而选择的蒙哥马利变换值A。

W＝Mon_{k，p}(1)＝(2^k)mod p(步骤S102)

控制部114通过提取部122从保存于私钥保存部113中的私钥S的最高位开始尝试1位1位地进行提取(步骤S103)。

从私钥S的最高位的位到最低位的位，结束上述提取后(步骤S104中是)，控制部114对蒙哥马利逆变换部120进行控制以使其进行运算结果W的蒙哥马利逆运算，蒙哥马利逆变换部120对运算结果W实施蒙哥马利逆运算，生成输出数据M。

M＝Mon_{k，p}^-1(W)

接着，蒙哥马利逆变换部120将输出数据M向输入输出部102输出。这里，是M＝C^S mod p(步骤S109)。这样，公钥解密部101的高速幂乘剩余运算结束。

在提取没有结束的情况下(步骤S104中否)，控制部114对平方运算部115进行控制以使其将运算结果W在蒙哥马利区域中平方运算，平方运算部115将运算结果W在蒙哥马利区域中平方运算，将其平方运算值覆盖写入至运算结果W。

W＝Mon_{k，p}(W×W)(步骤S105)。

接着，控制部114判断所提取的位是“1”还是“0”，当从私钥S提取的该位是“1”时(步骤S106)，选择由第1蒙哥马利变换部111输出的蒙哥马利变换值B，对乘法运算部116控制以使其计算蒙哥马利乘法运算，乘法运算部116将运算结果W与由第1蒙哥马利变换部111输出的蒙哥马利变换值B＝Mon_{k，p}(C)相乘，将得到的值覆盖写入至运算结果W。

W＝Mon_{k，p}(W×B)(步骤S107)。

接着，控制部114将控制向步骤S103转移。

另一方面，当从私钥S提取的该位是“0”时，控制部114选择第2蒙哥马利变换部112的输出值，对乘法运算部116控制以使其计算蒙哥马利乘法运算，乘法运算部116将运算结果W与作为第2蒙哥马利变换部112的输出值的A＝Mon_{k，p}(1)相乘，将得到的值覆盖写入至运算结果W。

W＝Mon_{k，p}(W×A)(步骤S108)。

接着，控制部114将控制向步骤S103转移。

3、实施方式的效果

首先，由图4所示的流程图可知，不论私钥S的相应位是“1”还是“0”，乘法运算部116都一定动作。因此，作为通过乘法运算的有无来进行解析的SPA是很困难的。

在本实施方式中，在私钥的相应位是“0”的情况下的乘法运算中使用蒙哥马利区域中的“1”(标记为Mon_{k，p}(1))。该蒙哥马利区域中的“1”由于是依存于整数k和模p而决定的值，所以不知道k及p的攻击者不能预测汉明重量。因此，判别蒙哥马利区域中的“1”而进行解析是很困难的。

此外，在万一汉明重量被攻击者求出的情况下，判别蒙哥马利区域中的“1”的解析也许会成功。在本实施方式中，还在模p的位的数目以上的限制的基础上，通过任意地变更整数k，汉明重量也变更。由此，解析变得更加困难。

另外，该变更定时越频繁、并且该整数k可取的变化越多，区别假乘法运算越困难，安全性越提高。但是，如果将k胡乱地取较大，则1次的平方运算及乘法运算的处理时间一般会增加，所以设为具有怎样程度的变化的k的大小、或者怎样设定变更的定时，依据应用所需要的速度和安全性来决定。图3中的设定控制部119进行它们的控制。

4、其他变形例

另外，对于上述实施方式说明了本发明，但本发明当然并不限于上述实施方式。以下这样的情况也包含在本发明中。

(1)利用图5所示的流程图对公钥解密部101的与上述不同的高速幂乘剩余运算的动作进行说明。

模设定部117设定模p。这里，模p例如是512位的秘密的素数。此外，模设定部117设定比p大的任意的2的幂乘值R。例如，生成随机数k，设R＝2^k。例如，是R＝2⁵¹²。此外，模设定部117生成随机数r(步骤S201)。

接着，第2蒙哥马利变换部112计算蒙哥马利变换值y。

y＝M(1)＝R mod p＝R-p

y是设在用来保存运算结果的值的运算值区域中的变量。

另外，这里，将“Mon_{k，p}(1)”更简略地表现为“M(1)(步骤S202)。

控制部114通过提取部122从保存于私钥保存部113中的私钥S的最高位开始1位1位地尝试提取(步骤S203)。

从私钥S的最高位的位到最低位的位，提取结束后(步骤S204中是)，输出y(步骤S209)，公钥解密部101的高速幂乘剩余运算结束。

在提取没有结束的情况下(步骤S204中否)，平方运算部115进行下式的平方运算。

y＝{y×y}×R^-1mod r×p  (步骤S205)。

接着，控制部114判断所提取的位是“1”还是“0”，当从私钥S提取的该位是“1”时(步骤S206)，乘法运算部116进行下式的乘法运算。

y＝{y×M(C)}×R^-1mod r×p  (步骤S207)。

接着，控制部114将控制向步骤S203转移。

另一方面，当从私钥S提取的该位是“0”时，乘法运算部116进行下式的乘法运算。

y＝{y×M(1)}×R^-1mod r×p(步骤S208)。

接着，控制部114将控制向步骤S103转移。

在该变形例中，公钥解密部101不包含蒙哥马利逆变换部120。

(2)整数k的变更定时也可以是每当输入数据时。即，如果取得第1输入数据，则随机地变更整数k的值，如果接着取得第2输入数据，则再随机地变更整数k的值，如果再取得第3输入数据，则再随机地变更整数k的值。

此外，也可以对多个输入数据使用相同的k。也可以对接着的多个输入数据使用另外的相同的整数。

此外，也可以在某个输入数据的运算的中途(重复的中途)随机地变更。此外，也可以以应用或用户从外部指示的定时随机地变更。

关于在第1及第2蒙哥马利变换部中使用的模，也与上述同样，也可以按照每个输入数据随机地变更，也可以对多个输入数据使用相同的模，也可以对接着的多个输入数据使用其他的相同的整数，或者也可以在输入数据的运算的中途(重复的中途)随机地变更，也可以以应用或用户从外部指示的定时随机地变更。

(3)(a)也可以使用p的随机倍作为模，求出第2蒙哥马利变换部112的输出。即，模设定部117生成随机数r，将生成的随机数r向第2蒙哥马利变换部112输出。第2蒙哥马利变换部112输出

2^k mod(r×p)。

由此，区别出使用了第1蒙哥马利变换部111或第2蒙哥马利变换部112的哪个变得更加困难，安全性提高。

此时，第2蒙哥马利变换部112的模既可以是原样的p，也可以是另外的随机倍。

这样，也可以对第1蒙哥马利变换部111的模和第2蒙哥马利变换部112的模独立地设定。

另外，蒙哥马利逆变换部120的模是p的原状。

(b)此外，也可以将在第1蒙哥马利变换部111中使用的模设为p的随机倍。此时，第2蒙哥马利变换部112的模既可以是p的原状，也可以是另外的随机倍。另外，蒙哥马利逆变换部120的模是p的原状。由此，对于计算1个输入数据的运算中的多个部位的功率变化间的相关性的攻击提高了安全性。

此外，也可以首先求出p的随机倍作为新的模之后、使用它进行第1蒙哥马利变换部111、第2蒙哥马利变换部112、以及平方运算部115或乘法运算部116中的计算。但是，在此情况下，为了得到设定的模的原来的最终输出，需要在输出之前用模p进行剩余运算后进行输出。

(c)在上述(a)、(b)中，在第1蒙哥马利变换部111中使用p的随机倍的模(第1模)，在第2蒙哥马利变换部112中使用p的另外的随机倍的模(第2模)的情况下，即第1模与第2模不同的情况下，只要设平方运算部115和乘法运算部116中使用的模为第1模与第2模的公倍数、设在蒙哥马利逆变换部120中使用的模是p的原状就可以。

(4)也可以将输入数据及输出数据设为蒙哥马利区域的值。在此情况下，在实施方式中包括的、第1蒙哥马利变换部111与蒙哥马利逆变换部120也可以安装在公钥解密部101之外。这是作为例如较大的系统之中的一部分而安装公钥解密部101、不仅是公钥加密的运算、将全部在蒙哥马利区域中安装的情况。

(5)在本实施方式中采用将私钥1位1位地处理的高速二进制幂乘剩余运算，但并不仅限于每次1位的处理。

例如，如果是每两位的处理，则通过平方运算部115进行两次平方运算、由控制部114对应于私钥的两个位选择来自4种蒙哥马利变换部的输出值、用乘法运算部116乘以所选择的输出值。

另外，该4种蒙哥马利变换部中的一个为“1”的蒙哥马利变换部(即，求出假乘法运算的输入值的部分)，在私钥的该两位两者都是“0”的情况下被选择。

这里，当两位是“00”时，对应的蒙哥马利变换部输出“1”的蒙哥马利变换值，当两位是“01”时，对应的蒙哥马利变换部输出“C”的蒙哥马利变换值。此外，当两位是“10”时，对应的蒙哥马利变换部输出“C²”的蒙哥马利变换值，当两位是“11”时，对应的蒙哥马利变换部输出“C³”的蒙哥马利变换值。

当然，在每3位以上地处理私钥的情况下，也能够通过将上述情况扩展使用来实现。

此外，在本实施方式中，使用了从高位开始处理私钥的算法，但也可以是从低位开始处理的结构。在此情况下，将对应于输入数据的蒙哥马利变换值重复平方运算，当私钥的对应的位是1时，乘以上述平方运算值，当是C时，与本实施方式同样，进行使用由整数k和模p求出的值的假乘法运算。

对于此情况下的公钥解密部101的高速幂乘剩余运算的动作，以与图4的不同点为中心，利用图6所示的流程图进行说明。

代替图4所示的步骤S103，在步骤S103a中，控制部114通过提取部122从保存于私钥保存部113中的私钥S的最低位开始1位1位地尝试提取。

如果从私钥S的最低位的位到最高位的位上述提取结束(步骤S104a中是)，控制部114对蒙哥马利逆变换部120控制以使其进行运算结果W的蒙哥马利逆运算。

在提取没有结束的情况下(步骤S104a中否)，代替图4所示的步骤S105，在步骤S105a中，控制部114对平方运算部115控制以使其将输入数据C在蒙哥马利区域中进行平方运算，平方运算部115将输入数据C在蒙哥马利区域中进行平方运算，将该平方运算值覆盖写入至输入数据C。

C＝Mon_{k，p}(C×C)

(6)在本实施方式中，通过RSA加密的解密处理进行了说明，但也可以如下所示那样应用在RSA签名的签名生成中。

进行RSA的密钥生成。RSA的密钥生成与RSA加密的情况相同，所以省略详细情况。

这里，设私钥为d、设公钥为e、p。

签名生成装置通过下式对文本m生成签名数据s。

s＝h(m)^d mod p

这里，h()是单向性的哈希函数。

本发明在上述签名生成装置中与上述实施方式同样地应用。上述签名生成装置是通过在规定的模下将输入值整数次幂的幂乘剩余运算、进行输入值的可靠的处理的信息安全装置。

另外，签名验证装置通过下式进行签名的验证。

h(m)＝s^e mod p

此外，本发明在RSA加密的加密处理中，可以在隐秘公钥的应用的情况下使用。

进而，也可以作为椭圆曲线加密或超椭圆曲线加密中的、使用私钥的处理的SAP对策使用。

(7)上述实施方式及变形例在以下所示那样的情况下适用。

(a)实施方式及变形例在秘密的消息传送中应用。

在本实施方式中，作为秘密的消息传送的一例，对秘密地传送许可密钥的情况进行说明。

如上所述，IC卡100是通过在规定的模下将输入值进行整数次幂的幂乘剩余运算、进行输入值的安全的处理的信息安全装置。这里，所谓的“安全”，是指进行保密以使得消息不会被发送者及接收者以外的第三者知道。

本发明在由内容加密装置和内容再现装置构成的内容分发系统中适用，例如也可以以电影、动态图像、声音、音乐、小说、数据库等的数字信息为秘密通信的对象。这些内容通过从内容供给者对利用者销售或租借记录有这些内容的记录媒体而提供。此外，经由数字广播或因特网从内容供给者对使用者提供。

内容供给者所具有的内容加密装置将作为数字作品的电影加密而记录在DVD中。使用者所具有的内容再现装置从DVD读出加密数字作品，解密而生成电影，将生成的电影作为声音及影像再现，显示及输出。

在上述的例子中，也可以将用来将内容加密及解密的内容密钥作为实施方式所示的秘密通信的对象。在此情况下，内容密钥与实施方式所示的方法同样被加密并解密。

在此情况下，内容通过内容密钥使用共用密钥加密方式被加密、解密。

也可以应用在以下所示那样的金钱的结算系统中。

例如，将能够代替货币使用的电子货币作为秘密通信对象，IC卡存储有电子货币，当使用者购入商品时，IC卡将对应于商品的购入额的电子货币加密并发送，并且从存储在内部中的电子货币中减去已发送的量。设置在商店内的出纳装置接收加密电子货币，将接收到的电子货币解密而再现电子货币并存储。

此外，也可以是，代替上述IC卡，用来利用美术馆或博物馆等的各种设施的IC卡类型的电子钱包如上述那样存储相当于电子货币的信息。也可以是，设在各种设施的入口的入场管理装置请求对应于各种设施的使用费用的金额的电子货币，上述电子钱包将所请求的金额的电子货币加密并发送，入场管理装置接收加密电子货币，将接收到的加密电子货币解密而生成电子货币并存储。

此外，也可以是，在利用铁路、公共汽车等的交通工具时使用的IC卡型的IC卡乘车券如上述那样存储有相当于电子货币的信息。设在交通工具的车站的入口的入场管理装置发送识别该车站的识别信息，IC卡乘车券接收上述识别信息并存储。设在交通工具的车站的出口的出场管理装置从IC卡乘车券接收上述识别信息，利用接收到的识别信息和设置有该出场管理装置的车站，通过费用表计算乘车费用，请求对应于计算出的乘车费用的金额的电子货币，IC卡乘车券将所请求的金额的电子货币加密并发送，出场管理装置接收加密电子货币，将接收到的加密电子货币解密，生成电子货币并存储。

(b)实施方式及变形例在认证中适用。所谓认证，是消息是否由如其所自称的人物发送、并且消息是否未被篡改的验证。此外，实施方式及变形例在身份的证明中适用。所谓的身份的证明，例如是具有向数据的访问权、或向设施的访问权(入室权)的证明，或者是符合如自己所主张的人物的证明。进而，实施方式及变形例在否认防止中适用。所谓否认防止，是指对例如实际已同意某事但又主张不同意的人的对抗。

在上述变形例中，作为认证的一例，对RSA数字签名进行了说明。本发明在上述签名生成装置中与上述实施方式同样地适用。上述签名生成装置是通过在规定的模下将输入值进行整数次幂的幂乘剩余运算而进行输入值的可靠的处理的信息安全装置。

这里，所谓的“可靠”，例如是消息由如其所自称的人物发送、且消息没有被篡改。此外，例如是具有向数据的访问权、具有向设施的访问权(入室权)、或如其自己所主张的人物。

(c)实施方式及变形例在密钥交换(也称作密钥共用)中适用。所谓的密钥交换，例如是两个人使用广播电波并同意在某个私钥加密方式中使用的私钥。

作为密钥交换的典型的方法，有称作DH(Diffie-Hellman)密钥交换的方法。这里，相互交换密钥的各自任意地生成秘密的幂数，使用它进行幂乘运算。

在此时的幂乘运算中适用本发明，能够将秘密的幂数隐匿而共享共用密钥。

(d)实施方式及变形例在零知识证明中适用。所谓的零知识证明，例如是某个人将成功地解决了数理或组合论问题的情况，连解是什么的很少的信息都不给予，而使其他人相信该情况。

(e)如上所述，本发明可以在采用使用秘密的幂值的幂乘运算的协议方式中使用。

(8)本发明是使用输入数据和私钥、重复进行设定的模下的乘法运算而进行幂乘剩余运算的信息安全装置。上述信息安装装置具备：求出对应于上述输入数据的蒙哥马利变换值的第1蒙哥马利变换部；求出1的蒙哥马利变换值的第2蒙哥马利变换部；如果私钥的位是0则选择上述第2蒙哥马利变换部的输出、否则选择上述第1蒙哥马利变换部的输出的控制部；和利用到此为止计算的结果和由上述控制部选择的值来进行乘法运算的乘法运算部，当设上述模为p、比p的有效位的数目大的整数为k时，上述第2蒙哥马利变换部输出以上述p为模、以上述k为幂的2的幂乘值。根据该信息安全装置，第2蒙哥马利变换部的输出(蒙哥马利区域中的1)依存于整数k和模p而决定。因此，在汉明重量中没有偏倚，利用功率变化来区别作为乘法运算的输入是使用了第1蒙哥马利变换部的输出、还是使用了第2蒙哥马利变换部的输出是很困难的。

这里，也可以构成为具备随机地选择比上述p的有效位的数目大的整数k的整数k设定部。根据该结构，第2蒙哥马利变换部的输出依存于随机地选择的整数k而变化。因此，对于遍及多个数据计算功率变化的相关性的攻击提高了安全性。

这里，也可以构成为上述第2蒙哥马利变换部输出以上述p的随机倍为模、以上述k为幂的2的幂乘值。根据该结构，第2蒙哥马利变换部的输出依存于随机地选择的模的值而变化。因此，对于遍及多个数据计算功率变化的相关性的攻击提高了安全性。

这里，也可以构成为上述第1蒙哥马利变换部以上述p的随机倍为模、输出对应于上述输入数据的蒙哥马利变换值。根据该结构，第1蒙哥马利变换部的输出依存于模的变化而变化。因此，对于计算1个输入数据的运算中的多个部位的功率变化间的相关性的攻击提高了安全性。

这里，也可以构成为，具备将上述p的随机倍重新作为模的模变更部，利用设定的模通过上述第1蒙哥马利变换部、第2蒙哥马利变换部及上述乘法运算部处理规定的计算。根据该结构，依存于由变更部变更的模，不仅第1蒙哥马利变换部、第2蒙哥马利变换部，在乘法运算部中使用的模也被变换，所以功率变化与私钥的相关性变得更小，安全性提高。

这里，也可以构成为，根据来自外部的指示变更上述整数k或上述模。根据该结构，通过以外部的应用或用户指定的定时使整数k或模变化，能够实现具有对应于该定时的性能和安全性的信息安全装置。

(9)上述各装置具体而言是由微处理器、ROM、RAM等构成的计算机系统。在上述RAM中存储有计算机程序。这里，计算机程序是为了实现规定的功能、组合多个表示对计算机的指令的命令代码而构成的。通过上述微处理器按照上述计算机程序动作，各装置实现其功能。即，上述微处理器将包含在上述计算机程序中的各命令1个1个地读出，将读出的命令解读，按照解读结果动作。

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

此外，构成上述各装置的结构要素的各部也可以单独地单芯片化、也可以包含一部分或全部而单芯片化。此外，这里设为LSI，但根据集成度的差异，也有称作IC、系统LSI、超(super)LSI、甚(ultra)LSI的情况。

此外，集成电路化的方法并不限于LSI，也可以通过专用电路或通用处理器实现。也可以利用在LSI制造后能够编程的FPGA(Field ProgrammableGate Array：现场可编程门阵列)及可对LSI内部的电路单元的连接及设定进行再构成的可重构处理器。

进而，如果因半导体技术的进步或派生的其他技术而出现代替LSI的集成电路化的技术，则当然也可以利用该技术进行功能块的集成化。有可能是生物技术的应用等。

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

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

此外，本发明也可以是将上述计算机程序或上述数字信号记录在计算机可读取的记录媒体——例如软盘、硬盘、CD-ROM、MO、DVD、DVD-ROM、DVD-RAM、BD(Blu-ray Disc：蓝光光盘)、半导体存储器等中而成的产品。此外，也可以是记录在这些记录媒体中的上述计算机程序或上述数字信号。

此外，本发明也可以是将上述计算机程序或上述数字信号经由电气通信线路、无线或有线通信线路、以因特网为代表的网络、数据广播等传送的系统。

此外，本发明也可以是具备微处理器和存储器的计算机系统，上述存储器存储有上述计算机程序，上述微处理器按照上述计算机程序动作。

此外，也可以通过将上述程序或上述数字信号记录在上述记录媒体中并移送，或者通过将上述程序或上述数字信号经由上述网络等移送，由独立的其他计算机系统实施。

(13)也可以将上述实施方式及上述变形例分别组合。

工业实用性

本发明的信息安全装置及信息安全方法在使用私钥实现公钥加密运算及签名运算的加密模式中、特别是如IC卡或安全卡那样有可能传到解读者一方的手中、进行SPA等的攻击的情况下使用。

构成本发明的各装置可以在需要秘密的消息传送及认证的所有产业中经营性地、并持续性地及反复地使用。此外，构成本发明的各装置可以在电器设备制造产业中经营性地、并持续性地及反复地制造、销售。

权利要求书(按照条约第19条的修改)

1、(修正后)一种信息安全装置，为了进行在规定的模下将输入值整数次幂的幂乘剩余运算，对上述整数的各位的每个重复乘法运算而计算幂乘值，进行上述输入值的安全或可靠的处理，其特征在于，具备：

判断机构，判断上述整数的1个位的值是否是0；以及

乘法运算机构，在判断为所取得的位的值是0的情况下，进行使用对于值1的蒙哥马利变换值的乘法剩余运算；

该信息安全装置还包括蒙哥马利变换机构，该蒙哥马利变换机构计算对于值1的蒙哥马利变换值；

上述乘法运算机构在上述乘法剩余运算中，使用由上述蒙哥马利变换机构计算出的蒙哥马利变换值；

该信息安全装置还具备：

模设定机构，设定上述模的值；以及

整数设定机构，随机地选择比上述模的有效位的数目大的整数k；

上述蒙哥马利变换机构根据所设定的上述模的值，利用上述整数k，计算上述蒙哥马利变换值。

2、(删除)

3、(删除)

4、(删除)

5、(删除)

6、(删除)

7、(修正后)如权利要求1所述的信息安全装置，其特征在于，

上述蒙哥马利变换机构在上述模下计算值2的k次幂值，作为上述蒙哥马利变换值。

8、(修正后)如权利要求1所述的信息安全装置，其特征在于，

上述蒙哥马利变换机构在作为上述模的值的随机倍的模下计算值2的k次幂值，作为上述蒙哥马利变换值。

9、如权利要求8所述的信息安全装置，其特征在于，

上述信息安全装置中，

上述模设定机构进一步设定作为上述模的值的随机倍的模；

上述蒙哥马利变换机构在由模设定机构进一步设定的上述模下计算值2的k次幂值。

10、(修正后)如权利要求1所述的信息安全装置，其特征在于，

上述整数设定机构每当取得输入值时，随机地变更上述整数k的值。

11、(修正后)如权利要求1所述的信息安全装置，其特征在于，

上述模设定机构每当取得输入值时，随机地变更在上述蒙哥马利变换机构中使用的上述模的值。

12、(修正后)如权利要求1所述的信息安全装置，其特征在于，

上述整数设定机构在上述重复的中途，随机地变更上述整数k的值。

13、(修正后)如权利要求1所述的信息安全装置，其特征在于，

上述模设定机构在上述重复的中途，随机地变更在上述蒙哥马利变换机构中使用的上述模的值。

14、(修正后)如权利要求1所述的信息安全装置，其特征在于，

上述整数设定机构根据来自外部的指示，随机地变更上述整数k的值。

15、(修正后)如权利要求1所述的信息安全装置，其特征在于，

上述模设定机构根据来自外部的指示，随机地变更在上述蒙哥马利变换机构中使用的上述模的值。

16、(修正后)如权利要求1所述的信息安全装置，其特征在于，

上述信息安全装置还包括蒙哥马利变换机构，该蒙哥马利变换机构计算对于上述输入值的蒙哥马利变换值；

上述乘法运算机构在判断为所取得的位的值是0以外的情况下，利用由上述蒙哥马利变换机构计算出的上述蒙哥马利变换值进行乘法剩余运算；

该信息安全装置还具备：

模设定机构，设定上述模的值；以及

整数设定机构，随机地选择比上述模的有效位的数目大的整数k；

上述蒙哥马利变换机构根据所设定的上述模的值，利用上述整数k，计算上述蒙哥马利变换值。

17、(删除)

18、(修正后)如权利要求16所述的信息安全装置，其特征在于，

上述蒙哥马利变换机构在上述模下计算值2的k次幂值，并将上述输入值与计算出的值相乘得到的值，作为上述蒙哥马利变换值。

19、(修正后)如权利要求16所述的信息安全装置，其特征在于，

上述蒙哥马利变换机构在作为上述模的值的随机倍的模下计算值2的k次幂值，作为上述蒙哥马利变换值。

20、(修正后)一种信息安全方法，在信息安全装置中使用，该信息安全装置为了进行在规定的模下将输入值整数次幂的幂乘剩余运算，对上述整数的各位的每个重复乘法运算而计算幂乘值，进行上述输入值的安全或可靠的处理，其特征在于，该信息安全方法包括：

判断步骤，判断上述整数的1个位的值是否是0；以及

乘法运算步骤，在判断为所取得的位的值是0的情况下，进行使用对于值1的蒙哥马利变换值的乘法剩余运算；

该信息安全方法还包括蒙哥马利变换步骤，该蒙哥马利变换步骤计算对于值1的蒙哥马利变换值；

上述乘法运算步骤在上述乘法剩余运算中，使用由上述蒙哥马利变换步骤计算出的蒙哥马利变换值；

该信息安全方法还包括：

模设定步骤，设定上述模的值；以及

整数设定步骤，随机地选择比上述模的有效位的数目大的整数k；

上述蒙哥马利变换步骤根据所设定的上述模的值，利用上述整数k，计算上述蒙哥马利变换值。

21、(修正后)一种计算机程序，用于在信息安全装置中使用的信息安全，该信息安全装置为了进行在规定的模下将输入值整数次幂的幂乘剩余运算，对上述整数的各位的每个重复乘法运算而计算幂乘值，进行上述输入值的安全或可靠的处理，其特征在于，该计算机程序包括：

判断步骤，判断上述整数的1个位的值是否是0；以及

乘法运算步骤，在判断为所取得的位的值是0的情况下，进行使用对于值1的蒙哥马利变换值的乘法剩余运算；

该计算机程序还包括蒙哥马利变换步骤，该蒙哥马利变换步骤计算对于值1的蒙哥马利变换值；

上述乘法运算步骤在上述乘法剩余运算中，使用由上述蒙哥马利变换步骤计算出的蒙哥马利变换值；

该计算机程序还包括：

模设定步骤，设定上述模的值；以及

整数设定步骤，随机地选择比上述模的有效位的数目大的整数k；

上述蒙哥马利变换步骤根据所设定的上述模的值，利用上述整数k，计算上述蒙哥马利变换值。

22、(修正后)一种记录媒体，是记录有计算机程序的计算机可读取的记录媒体，该计算机程序用于在信息安全装置中使用的信息安全，该信息安全装置为了进行在规定的模下将输入值整数次幂的幂乘剩余运算，对上述整数的各位的每个重复乘法运算而计算幂乘值，进行上述输入值的安全或可靠的处理，其特征在于，上述计算机程序包括：

判断步骤，判断上述整数的1个位的值是否是0；以及

乘法运算步骤，在判断为所取得的位的值是0的情况下，进行使用对于值1的蒙哥马利变换值的乘法剩余运算；

该计算机程序还包括蒙哥马利变换步骤，该蒙哥马利变换步骤计算对于值1的蒙哥马利变换值；

上述乘法运算步骤在上述乘法剩余运算中，使用由上述蒙哥马利变换步骤计算出的蒙哥马利变换值；

该计算机程序还包括：

模设定步骤，设定上述模的值；以及

整数设定步骤，随机地选择比上述模的有效位的数目大的整数k；

上述蒙哥马利变换步骤根据所设定的上述模的值，利用上述整数k，计算上述蒙哥马利变换值。

23、(修正后)一种集成电路，为了进行在规定的模下将输入值整数次幂的幂乘剩余运算，对上述整数的各位的每个重复乘法运算而计算幂乘值，进行上述输入值的安全或可靠的处理，其特征在于，具备：

判断机构，判断上述整数的1个位的值是否是0；以及

乘法运算机构，在判断为所取得的位的值是0的情况下，进行使用对于值1的蒙哥马利变换值的乘法剩余运算；

该信息安全装置还包括蒙哥马利变换机构，该蒙哥马利变换机构计算对于值1的蒙哥马利变换值；

上述乘法运算机构在上述乘法剩余运算中，使用由上述蒙哥马利变换机构计算出的蒙哥马利变换值；

该信息安全装置还具备：

模设定机构，设定上述模的值；以及

整数设定机构，随机地选择比上述模的有效位的数目大的整数k；

上述蒙哥马利变换机构根据所设定的上述模的值，利用上述整数k，计算上述蒙哥马利变换值。