RSA公开密钥生成装置、RSA解密装置及RSA署名装置转让专利
申请号 : CN200410094717.3
文献号 : CN1645791B
文献日 : 2010-09-01
发明人 : 小野贵敏 , 松崎枣 , 布田裕一
申请人 : 松下电器产业株式会社
摘要 :
本发明提供一种用于IC卡等以使故障利用攻击不能得逞的RSA解密装置。该RSA解密装置不从外部取得公开密钥，并且可高速进行数据验证用的公开密钥的运算。RSA解密装置具有计算dp＝d mod(p-1)的余数运算部412以及求算以p-1为除数的余数体中dp的逆元的求逆运算部414，以dp的逆元作为公开密钥，来进行解密码的验证。与以公开密钥作为d的逆元来求算的方法相比，可减少逆元运算的位数，可进行高速运算。
权利要求 :
1.一种从RSA加密方式的秘密密钥d来重新生成公开密钥e′的RSA公开密钥生成装置，包含：取得单元，其取得RSA密码的秘密密钥d及素数p，这里，任意选择的素数q与任意选择的素数p相异，任意选择的公开密钥e与p-1同q-1的最小公倍数1cm互素，而且满足p-1＞e，上述秘密密钥d是以1cm为除数的余数体中公开密钥e的逆元；
余数运算单元，其利用所取得的秘密密钥d与素数p，来算出以素数p-1为除数的上述秘密密钥d的余数dp；
逆元运算单元，其利用所算出的上述余数dp及所取得的上述素数p，来算出以素数p-1为除数的余数体中上述余数dp的逆元，并将所算出的逆元作为新的公开密钥e′。
2.权利要求1中的RSA公开密钥生成装置，其中，
上述余数运算单元由dp＝d(mod p-1)，来算出上述余数dp，上述逆元运算单元由e′＝dp-1(mod p-1)，来算出上述公开密钥e′。
3.权利要求1中的RSA公开密钥生成装置，其中，
上述余数运算单元及上述逆元运算单元由1个集成电路来构成。
4.一种构成从RSA加密方式的秘密密钥d重新生成公开密钥e′的RSA公开密钥生成装置的集成电路，其中，RSA公开密钥生成装置包含：
取得单元，其取得RSA密码的秘密密钥d及素数p，这里，任意选择的素数q与任意选择的素数p相异，任意选择的公开密钥e与p-1同q-1的最小公倍数1cm互素，而且满足p-1＞e，上述秘密密钥d是以1cm为除数的余数体中公开密钥e的逆元；
上述集成电路包含：
余数运算单元，其利用所取得的秘密密钥d与素数p，来算出以素数p-1为除数的上述秘密密钥d的余数dp；
逆元运算单元，其利用所算出的上述余数dp及所取得的上述素数p，来算出以素数p-1为除数的余数体中上述余数dp的逆元，并将所算出的逆元作为新的公开密钥e′。
5.一种对由RSA加密方式生成的加密码解密的RSA解密装置，包含：取得单元，其取得RSA密码的秘密密钥d及素数p，这里，任意选择的素数q与任意选择的素数p相异，任意选择的公开密钥e与p-1同q-1的最小公倍数1cm互素，并满足p-1＞e，上述秘密密钥d是以1cm为除数的余数体中公开密钥e的逆元；
余数运算单元，其利用所取得的秘密密钥d与素数p，来算出以素数p-1为除数的上述秘密密钥d的余数dp；
逆元运算单元，其利用所算出的上述余数dp及所取得的上述素数p，来算出以素数p-1为除数的余数体中上述余数dp的逆元，并将所算出的逆元作为新的公开密钥e′；
加密码取得单元，其取得加密码C，加密码C是一种利用上述公开密钥e，由RSA加密方式对明码M进行RSA加密而生成的码；
RSA解密单元，其利用秘密密钥d，对所取得的上述加密码C进行RSA解密，生成解密码D；
再加密单元，其利用所取得的公开密钥e′，对所生成的解密码D进行RSA加密，生成再加密码C′；
比较单元，其将所取得的加密码C与所生成的再加密码C′进行比较，判断是否一致；
输出单元，在判断为一致的场合下，输出所生成的上述解密码D。
6.一种由RSA署名方式对明码实施署名，以生成署名码的RSA署名装置，包含：取得单元，其取得RSA密码的秘密密钥d及素数p，这里，任意选择的素数q与任意选择的素数p相异，任意选择的公开密钥e与p-1同q-1的最小公倍数1cm互素，并满足p-1＞e，上述秘密密钥d是以1cm为除数的余数体中公开密钥e的逆元；
余数运算单元，其利用所取得的秘密密钥d与素数p，来算出以素数p-1为除数的上述秘密密钥d的余数dp；
逆元运算单元，其利用所算出的上述余数dp及所取得的上述素数p，来算出以素数p-1为除数的余数体中上述余数dp的逆元，并将所算出的逆元作为新的公开密钥e′；
署名生成单元，其利用秘密密钥d，对明码M实施RSA署名，生成署名码S；
恢复单元，其利用所取得的公开密钥e′，对署名码S实施RSA署名恢复，生成解密码D；
比较单元，其将明码M与所生成的解密码D进行比较，判断是否一致；
输出单元，其在判断为一致的场合下，输出所生成的上述署名码S。
7.一种从RSA加密方式的秘密密钥d来重新生成公开密钥e′的RSA公开密钥生成装置中所用的RSA公开密钥生成方法，包括：取得步骤，其取得RSA密码的秘密密钥d及素数p，这里，任意选择的素数q与任意选择的素数p相异，任意选择的公开密钥e与p-1同q-1的最小公倍数1cm互素，并满足p-1＞e，上述秘密密钥d是以1cm为除数的余数体中公开密钥e的逆元；
余数运算步骤，其利用所取得的秘密密钥d与素数p，来算出以素数p-1为除数的上述秘密密钥d的余数dp；
逆元运算步骤，其利用所算出的上述余数dp及所取得的上述素数p，来算出以素数p-1为除数的余数体中上述余数dp的逆元，并将所算出的逆元作为新的公开密钥e′。
说明书 :
技术领域
本发明涉及采用了公开密钥加密算法之一即RSA加密技术的信息安全技术。
背景技术
本申请基于日本注册申请No.2003-382191，本文引用了其内容作为参照。以往作为实现信息的隐秘、认证等的手段，公开密钥加密方式已为人们所知。
在公开密钥加密方式中，生成自己独自持有的秘密密钥同与上述秘密密钥对应公开的公开密钥的密钥对，利用上述公开密钥来进行加密，并利用上述秘密密钥来进行解密。比如，在消息的加密通信中，消息发送者利用消息接收者的公开密钥来对消息加密，唯有秘密密钥的保持者即消息接收者，才能利用消息接收者的秘密密钥，来对该加密消息解密。
虽然公开密钥加密法处理运算量较多，但是不必由多个利用者来共享秘密密钥，因而在需要高安全性的场合下，公开密钥加密法经常被使用。作为一般广为人知的公开密钥加密法，存在RSA加密及椭圆曲线加密这两种。
通过采用上述的公开密钥加密方式，虽然可使第三者不知晓地向对方发送秘密信息，但是依据专利文献1，例如IC卡正在进行密码处理时，非法第三者有可能利用异常时钟、异常电压、异常电磁波、异常温度等，故意引发错误，从而取出密码中所用的密钥及秘密信息，因而成为一种威胁。这种攻击称为故障利用攻击(也称为DFA攻击)。
为了对抗该故障利用攻击，专利文献2中披露了一种下列技术，即利用除数n的素因数，由中国余数定理(Chinese Remainder Theorem，简称CRT)来高速处理作成数字署名的幂乘余数计算，与在基于中国余数定理的计算过程中生成的数据一起，同时计算有关该数据的出错检测码并予以存储，在作成数字署名时，再次计算上述数据的出错检测码，并与已存储的出错检测码进行核对，从而检测出数据错误，当检测出错误时，返回出错状态。以此来提高利用中国余数定理来高速进行署名作成处理的IC卡的针对故障利用攻击的安全性。
【专利文献1】
特开2002-261751号公报
【专利文献2】
特开平11-8616号公报
在公开密钥加密方式中，生成自己独自持有的秘密密钥同与上述秘密密钥对应公开的公开密钥的密钥对，利用上述公开密钥来进行加密，并利用上述秘密密钥来进行解密。比如，在消息的加密通信中，消息发送者利用消息接收者的公开密钥来对消息加密，唯有秘密密钥的保持者即消息接收者，才能利用消息接收者的秘密密钥，来对该加密消息解密。
虽然公开密钥加密法处理运算量较多，但是不必由多个利用者来共享秘密密钥，因而在需要高安全性的场合下，公开密钥加密法经常被使用。作为一般广为人知的公开密钥加密法，存在RSA加密及椭圆曲线加密这两种。
通过采用上述的公开密钥加密方式，虽然可使第三者不知晓地向对方发送秘密信息，但是依据专利文献1，例如IC卡正在进行密码处理时，非法第三者有可能利用异常时钟、异常电压、异常电磁波、异常温度等，故意引发错误，从而取出密码中所用的密钥及秘密信息，因而成为一种威胁。这种攻击称为故障利用攻击(也称为DFA攻击)。
为了对抗该故障利用攻击，专利文献2中披露了一种下列技术，即利用除数n的素因数，由中国余数定理(Chinese Remainder Theorem，简称CRT)来高速处理作成数字署名的幂乘余数计算，与在基于中国余数定理的计算过程中生成的数据一起，同时计算有关该数据的出错检测码并予以存储，在作成数字署名时，再次计算上述数据的出错检测码，并与已存储的出错检测码进行核对，从而检测出数据错误，当检测出错误时，返回出错状态。以此来提高利用中国余数定理来高速进行署名作成处理的IC卡的针对故障利用攻击的安全性。
【专利文献1】
特开2002-261751号公报
【专利文献2】
特开平11-8616号公报
发明内容
如上所述，根据传统技术，提高对于利用中国余数定理来进行署名作成处理的IC卡的故障利用攻击的安全性，但是还期望能进一步高速进行信息安全处理。
为实现上述期望，本发明的目的在于，提供一种与传统技术相比可高速进行信息安全运算的RSA公开密钥生成装置、RSA解密装置、RSA署名装置、方法及程序。
为达到上述目的，本发明为一种从RSA加密方式的秘密密钥d来重新生成公开密钥e′的RSA公开密钥生成装置，包含：取得单元，其取得RSA密码的秘密密钥d及素数p，这里，素数q与素数p相异，公开密钥e与p-1同q-1的最小公倍数1cm互素，而且满足p-1＞e，上述秘密密钥d是以1cm为除数的余数体中公开密钥e的逆元；余数运算单元，其利用所取得的秘密密钥d与素数p，来算出以素数p-1为除数的上述秘密密钥d的余数dp；逆元运算单元，其利用所算出的上述余数dp及所取得的上述素数p，来算出以素数p-1为除数的余数体中上述余数dp的逆元，并将所算出的逆元作为新的公开密钥e′。
基于该构成，为求出公开密钥，成为逆元的运算对象的余数dp是秘密密钥d的大约一半位数的值，因而具有通过逆元运算单元，逆元运算所需时间与传统相比可大幅缩减的效果。
此外，本发明为一种对由RSA加密方式生成的加密码解密的RSA解密装置，包含：公开密钥取得单元，其从权利要求1的RSA公开密钥生成装置取得公开密钥e′；加密码取得单元，其取得加密码C，加密码C是一种利用上述公开密钥e，由RSA加密方式对明码M进行RSA加密而生成的码；RSA解密单元，其利用秘密密钥d，对所取得的上述加密码C进行RSA解密，生成解密码D；再加密单元，其利用所取得的公开密钥e′，对所生成的解密码D进行RSA加密，生成再加密码C′；比较单元，其将所取得的加密码C与所生成的再加密码C′进行比较，判断是否一致；输出单元，在判断为一致的场合下，输出所生成的上述解密码D。
基于该构成，在基于比较单元的判断为一致的场合下，输出所生成的解密码，因而可对抗故障利用攻击。
这里，上述RSA解密装置中，上述RSA解密单元从权利要求1的RSA公开密钥生成装置取得余数dp，利用所取得的余数dp，由中国余数定理，来对所取得的上述加密码C进行RSA解密，生成解密码D。
基于该构成，为求出公开密钥，可在按原样来利用中国余数定理算法的RSA解密过程中采用成为逆元的运算对象的余数dp，因而可缩短RSA解密等所需的时间。
此外，本发明为一种由RSA署名方式来对明码实施署名，以生成署名码的RSA署名装置，包含：公开密钥取得单元，其从权利要求1中的RSA公开密钥生成装置来取得公开密钥e′；署名生成单元，其利用秘密密钥d，对明码M实施RSA署名，生成署名码S；恢复单元，其利用所取得的公开密钥e′，对署名码S实施RSA署名恢复，生成解密码D；比较单元，其将明码M与所生成的解密码D进行比较，判断是否一致；输出单元，在判断为一致的场合下，输出所生成的上述署名码S。
基于该构成，在基于比较单元的判断为一致的场合下，输出所生成的署名码，因而可对抗故障利用攻击。
这里，上述RSA署名装置中，上述署名生成单元从权利要求1的RSA公开密钥生成装置取得余数dp，利用所取得的余数dp，由中国余数定理，来对上述明码M实施RSA署名，生成署名码S。
基于该构成，为求出公开密钥，可在按原样来利用中国余数定理算法的RSA署名过程中采用成为逆元的运算对象的余数dp，因而可缩短RSA署名所需的时间。
为实现上述期望，本发明的目的在于，提供一种与传统技术相比可高速进行信息安全运算的RSA公开密钥生成装置、RSA解密装置、RSA署名装置、方法及程序。
为达到上述目的，本发明为一种从RSA加密方式的秘密密钥d来重新生成公开密钥e′的RSA公开密钥生成装置，包含：取得单元，其取得RSA密码的秘密密钥d及素数p，这里，素数q与素数p相异，公开密钥e与p-1同q-1的最小公倍数1cm互素，而且满足p-1＞e，上述秘密密钥d是以1cm为除数的余数体中公开密钥e的逆元；余数运算单元，其利用所取得的秘密密钥d与素数p，来算出以素数p-1为除数的上述秘密密钥d的余数dp；逆元运算单元，其利用所算出的上述余数dp及所取得的上述素数p，来算出以素数p-1为除数的余数体中上述余数dp的逆元，并将所算出的逆元作为新的公开密钥e′。
基于该构成，为求出公开密钥，成为逆元的运算对象的余数dp是秘密密钥d的大约一半位数的值，因而具有通过逆元运算单元，逆元运算所需时间与传统相比可大幅缩减的效果。
此外，本发明为一种对由RSA加密方式生成的加密码解密的RSA解密装置，包含：公开密钥取得单元，其从权利要求1的RSA公开密钥生成装置取得公开密钥e′；加密码取得单元，其取得加密码C，加密码C是一种利用上述公开密钥e，由RSA加密方式对明码M进行RSA加密而生成的码；RSA解密单元，其利用秘密密钥d，对所取得的上述加密码C进行RSA解密，生成解密码D；再加密单元，其利用所取得的公开密钥e′，对所生成的解密码D进行RSA加密，生成再加密码C′；比较单元，其将所取得的加密码C与所生成的再加密码C′进行比较，判断是否一致；输出单元，在判断为一致的场合下，输出所生成的上述解密码D。
基于该构成，在基于比较单元的判断为一致的场合下，输出所生成的解密码，因而可对抗故障利用攻击。
这里，上述RSA解密装置中，上述RSA解密单元从权利要求1的RSA公开密钥生成装置取得余数dp，利用所取得的余数dp，由中国余数定理，来对所取得的上述加密码C进行RSA解密，生成解密码D。
基于该构成，为求出公开密钥，可在按原样来利用中国余数定理算法的RSA解密过程中采用成为逆元的运算对象的余数dp，因而可缩短RSA解密等所需的时间。
此外，本发明为一种由RSA署名方式来对明码实施署名，以生成署名码的RSA署名装置，包含：公开密钥取得单元，其从权利要求1中的RSA公开密钥生成装置来取得公开密钥e′；署名生成单元，其利用秘密密钥d，对明码M实施RSA署名，生成署名码S；恢复单元，其利用所取得的公开密钥e′，对署名码S实施RSA署名恢复，生成解密码D；比较单元，其将明码M与所生成的解密码D进行比较，判断是否一致；输出单元，在判断为一致的场合下，输出所生成的上述署名码S。
基于该构成，在基于比较单元的判断为一致的场合下，输出所生成的署名码，因而可对抗故障利用攻击。
这里，上述RSA署名装置中，上述署名生成单元从权利要求1的RSA公开密钥生成装置取得余数dp，利用所取得的余数dp，由中国余数定理，来对上述明码M实施RSA署名，生成署名码S。
基于该构成，为求出公开密钥，可在按原样来利用中国余数定理算法的RSA署名过程中采用成为逆元的运算对象的余数dp，因而可缩短RSA署名所需的时间。
附图说明
参照本发明的以下特定实施方式的说明及附图，可更明晓本发明的这些及其它目的、长处及特性。
附图中：
图1是表示秘密通信系统10的构成的系统构成图。
图2是表示寄存器装置100的构成的框图。
图3是表示IC卡300的构成的框图。
图4是表示寄存器装置100及IC卡300的全体动作概要的流程图。
图5是表示基于寄存器装置100的IC卡300的认证动作的流程图。下接图6。
图6是表示基于寄存器装置100的IC卡300的认证动作的流程图。上接图5。
图7是表示基于IC卡300的寄存器装置100的认证动作的流程图。
图8是表示会话密钥的收发动作的流程图。
图9是表示点秘密通信动作的流程图。
图10是表示作为第2实施方式的RSA秘密通信系统20的构成的系统构成图。
图11是表示RSA解密装置400中的RSA解密动作的流程图。
图12是表示作为第3实施方式的RSA秘密通信系统30的构成的系统构成图。
图13是表示RSA秘密通信系统30的动作的流程图。
附图中：
图1是表示秘密通信系统10的构成的系统构成图。
图2是表示寄存器装置100的构成的框图。
图3是表示IC卡300的构成的框图。
图4是表示寄存器装置100及IC卡300的全体动作概要的流程图。
图5是表示基于寄存器装置100的IC卡300的认证动作的流程图。下接图6。
图6是表示基于寄存器装置100的IC卡300的认证动作的流程图。上接图5。
图7是表示基于IC卡300的寄存器装置100的认证动作的流程图。
图8是表示会话密钥的收发动作的流程图。
图9是表示点秘密通信动作的流程图。
图10是表示作为第2实施方式的RSA秘密通信系统20的构成的系统构成图。
图11是表示RSA解密装置400中的RSA解密动作的流程图。
图12是表示作为第3实施方式的RSA秘密通信系统30的构成的系统构成图。
图13是表示RSA秘密通信系统30的动作的流程图。
具体实施方式
1.第1实施方式
以下对作为本发明涉及的第1实施方式的秘密通信系统10进行说明。
1.1秘密通信系统10的构成
秘密通信系统10如图1所示，其构成包括寄存器装置100及IC卡300。
寄存器装置100设置于小卖店内，由小卖店的销售人员来操作，并根据利用者所购入商品的购入额，来发行特惠即点数。寄存器装置100对所发行的点数加密，生成加密点数，经由与寄存器装置100连接的读卡器200，向利用者的IC卡300输出所生成的加密点数。
IC卡300接受加密点数，对所接受的加密点数解密，生成解密点数，并存储所生成的解密点数。
利用者在下次购入商品时，可将IC卡300中存储的解密点数作为货款的一部分来使用。
1.2IC卡300的公开密钥e及秘密密钥d的生成
如下所示，密钥生成装置(未图示)生成IC卡300的公开密钥e及秘密密钥d。
(a)选择任意相异的2个大素数p及素数q，并计算其积n。n＝p×q
(b)计算(p-1)与(q-1)的最小公倍数L，并选择与最小公倍数L互素而且小于最小公倍数L的任意整数e(公开密钥)。
L＝LCM((p-1)，(q-1))
GCD(e，L)＝1
1＜e＜L
这里，LCM(X，Y)表示数X与数Y的最小公倍数，GCD(X，Y)表示数X与数Y的最大公倍数。LCM是Least Common Multiple(最小公倍数)的简称，GCD是Greatest Common Divisor(最大公约数)的简称。
基于在(c)(b)中求出的公开密钥e及最小公倍数L来解算下式，以求出秘密密钥d。
ed＝1(mod L)
密钥生成装置将素数p、素数q及公开密钥e预先通知到寄存器装置100。将素数p、素数q及秘密密钥d预先通知到IC卡300。
寄存器装置100的公开密钥PK及秘密密钥SK也同样由密钥生成装置来生成，秘密密钥SK被预先通知到寄存器装置100，公开密钥PK被预先通知到IC卡300。
1.3寄存器装置100的构成
寄存器装置100如图2所示，其构成包括显示部101、显示部102、印字部103、输入部104、保管库105、信息存储部106、控制部107、认证部108、加解密部109、输入输出部110及密钥存储部111。此外寄存器装置100的输入输出部110与读卡器200相接。
寄存器装置100是进行由利用者支付的购入货款的结算及保管等的钱币寄存器装置，根据利用者所购入商品的购入额，来发行特惠即点数，对所发行的点数加密，生成加密点数，并经由读卡器200，向利用者的IC卡300输出所生成的加密点数。
具体地说，寄存器装置100是一种包含微处理器、ROM、RAM等的计算机系统。上述ROM中存储有计算机程序。上述微处理器按照上述计算机程序来动作，寄存器装置100由此来实现其部分功能。
(1)密钥存储部111
密钥存储部111被设置成不能从外部来访问，如图2所示，预先存储有IC卡300的公开密钥e、素数p、素数q及寄存器装置100的秘密密钥SK。
公开密钥e是由RSA公开密钥加密方式的密钥生成算法所生成的IC卡300的公开密钥，被保存到1024位长的数据区。
素数p及素数q是任意相异的大素数，分别被保存到512位长的数据区。这里作为一例，
p＝
d32737e7 267ffe13 41b2d5c0 d150a81b 586fb313 2bed2f8d 5262864a 9cb9f30a
f38be448 598d413a 172efb80 2c21acf1 c11c520c 2f26a471 dcad212e ac7ca39d
q＝
cc8853d1 d54da630 fac004f4 71f281c7 b8982d82 24a490ed beb33d3e 3d5cc93c
4765703d 1dd79164 2f1f116a 0dd862be 2419b2af 72bfe9a0 30e860b0 288b5d77
这些记载都是16进制数。为了看起来方便，每8位分开表示。
秘密密钥SK是由RSA公开密钥加密方式的密钥生成算法所生成的寄存器装置100的秘密密钥，被保存到1024位长的数据区。
(2)信息存储部106
信息存储部106，具有用于存储识别利用者的利用者识别符及利用者的购入金额、购入日期、发行点数等有关基于利用者的商品购入的信息的区域。
(3)认证部108
当在读卡器200中装有IC卡300时，认证部108经由输入输出部110及读卡器200，如下所示，在与IC卡300之间相互进行设备认证。这里，设备认证是查询响应型认证。
(基于寄存器装置100的IC卡300的认证)
认证部108生成随机数R1，并经由输入输出部110及读卡器200，向IC卡300输出所生成的随机数R1。
此外认证部108经由读卡器200及输入输出部110，从IC卡300接受署名数据S1，从密钥存储部111读出IC卡300的公开密钥e、素数p及素数q。接下来对所生成的随机数R1施行散列函数Hash，生成散列值H2。
H2＝Hash(R1)
这里，Hash(R1)表示对随机数R1施行散列函数Hash所得到的值。散列函数Hash的一例是SHA-1。
接下来，认证部108计算n＝p×q，并计算S1e(mod n)，对所生成的散列值H2与由计算所得到的值S1e(mod n)进行比较，如果一致便视为认证成功，如果不一致则视为认证失败。
在认证成功的场合下，认证部108向控制部107通知表示设备认证成功这一意思的信息。在设备认证失败的场合下，向控制部107通知表示设备认证失败这一意思的信息。
在设备认证失败的场合下，此后寄存器装置100在与该IC卡300之间不进行信息收发。
(基于IC卡300的寄存器装置100的认证)
认证部108经由读卡器200及输入输出部110，从IC卡300接受随机数R2，从密钥存储部111读出秘密密钥SK、素数p及素数q，并对所接受的随机数R2施行散列函数Hash，计算散列值H3。
H3＝Hash(R2)
接下来，认证部108计算n＝p×q，还计算署名数据S2＝(H3)SK(mod n)，并经由输入输出部110及读卡器200，向IC卡300输出由计算所得到的署名数据S2。
(4)输入输出部110及读卡器200
输入输出部110在控制部107与读卡器200之间，对控制部107的控制源进行双向信息收发，或者在认证部108与读卡器200之间，对认证部108的控制源进行双向信息收发。
读卡器200在IC卡300与输入输出部110之间进行信息的收发。
(5)加解密部109
(会话密钥的输出)
加解密部109生成随机数，并将所生成的随机数作为会话密钥M。接下来，从密钥存储部111读出素数p、素数q及公开密钥e，计算整数n＝p×q，并利用会话密钥M、整数n及公开密钥e，由下式来算出加密会话密钥C1。
加密会话密钥C1＝Me(mod n)
接下来，经由输入输出部110及读卡器200，向IC卡300输出由计算所得到的加密会话密钥C1。
(点数的输出)
加解密部109从控制部107接受点数Pt，将所生成的会话密钥M用作密钥，对所接受的点数Pt施行加密算法E1，生成加密点数Et。
加密点数Et＝E1(会话密钥M、点数Pt)
这里，E(A，B)表示利用密钥A，对明码B施行加密算法E所得到的加密码。作为一例，加密算法E1是一种基于共通密钥加密方式的DES(Data Encryption Standard，数据加密标准)的算法。
接下来，加解密部109经由输入输出部110及读卡器200，向IC卡300输出加密点数Et。
(6)控制部107
控制部107由小卖店销售人员的操作，根据利用者所购入商品的购入额，来生成特惠即点数Pt，并向加解密部109输出所生成的点数Pt。
控制部107控制构成寄存器装置100的其它构成要素。
(7)输入部104、显示部101、显示部102、印字部103及保管库105
输入部104从寄存器装置100的操作者来接受输入信息，并向控制部107输出所接受的输入信息。显示部101及显示部102从控制部107接受应显示的信息，并显示出所接受的信息。
印字部103由控制部107的控制，来印刷各种信息。
保管库105保管纸币及货币。
1.4IC卡300的构成
IC卡300由长度约为85mm，宽度为54mm，厚度为0.76mm的薄片状树脂来形成，外表面上有接触端子，在内部密封有系统LSI(大规模集成电路，Large Scale Integrated circuit)320。
IC卡300如图3所示，结构包括输入输出部301、认证部302、解密部303、高速公开密钥运算部304、控制部305、再加密部306、信息存储部307、解密部308及密钥存储部309，认证部302、解密部303、高速公开密钥运算部304、控制部305、再加密部306、信息存储部307、解密部308及密钥存储部309形成系统LSI320。
系统LSI320是一种在1个芯片上集成上述多个构成部来制造的较长多功能LSI，具体地说，是一种包含微处理器、ROM、RAM等来构成的计算机系统。上述RAM中存储有计算机程序。上述微处理器按照上述计算机程序来动作，系统LSI320由此来实现其部分功能。
(1)密钥存储部309
密钥存储部309如图3所示，预先存储有寄存器装置100的公开密钥PK、素数p、素数q及IC卡300的秘密密钥d。
公开密钥PK是由RSA公开密钥加密方式的密钥生成算法所生成的寄存器装置100的公开密钥，被保存到1024位长的数据区。
素数p及素数q与上述同样，分别被保存到512位长的数据区。
秘密密钥d是由RSA公开密钥加密方式的密钥生成算法所生成的IC卡300的秘密密钥，被保存到1024位长的数据区。
(2)高速公开密钥运算部304
高速公开密钥运算部304如图3所示，构成包括秘密密钥取得部311、余数运算部312、求逆运算部313及除数运算部314。
秘密密钥取得部311从密钥存储部309读出秘密密钥d、素数p及素数q，并向余数运算部312输出所读出的秘密密钥d及素数p，并且，向除数运算部314输出所读出的素数p及素数q。
余数运算部312从秘密密钥取得部311接受秘密密钥d及素数p，利用所接受的秘密密钥d及素数p，来算出：
d1＝d(mod p-1)，
并向求逆运算部313输出由计算所得到的数d1及素数p，此外还向解密部303输出数d1。
求逆运算部313从余数运算部312接受数d1及素数p，利用所接受的数d1及素数p，由下式来算出公开密钥e′。
e′＝d1-1(mod p-1)
接下来，求逆运算部313向再加密部306及认证部302输出由计算所得到的公开密钥e′。
除数运算部314从秘密密钥取得部311接受素数p及素数q，利用所接受的素数p及素数q，来算出整数n＝p×q，并向认证部302及再加密部306输出由计算所得到的整数n。
(3)认证部302
(基于寄存器装置100的IC卡300的认证)
认证部302经由读卡器200及输入输出部301，从寄存器装置100接受随机数R1，从密钥存储部309读出素数p与素数q及秘密密钥d，从除数运算部314接受整数n，利用所接受的随机数R1，由下式来算出散列值H1。
H1＝Hash(R1)
接下来，认证部302依次运算下式，由此来算出署名数据S1。
a＝p-1(mod q)
y1＝H1(mod p)
y2＝H1(mod q)
d2＝d(mod q-1)
x1＝y1d1(mod p)
x2＝y2d2(mod q)
s1＝{a(x2-x1)(mod q)}p+x1
接下来，向再加密部306输出由计算所得到的署名数据S1，从再加密部306接受s1e′(mod n)。
接下来，判断散列值H1与s1e′(mod n)是否一致，在判断为不一致的场合下，视为发生了某种错误，认证部302向控制部305通知表示发生错误的出错信息。此后，IC卡300停止其动作。
在判断为一致的场合下，认证部302经由输入输出部301及读卡器200，向寄存器装置100输出所生成的署名数据S1。
(基于IC卡300的寄存器装置100的认证)
认证部302生成随机数R2，并经由输入输出部301及读卡器200，向寄存器装置100输出所生成的随机数R2。
接下来，认证部302经由读卡器200及输入输出部301，从寄存器装置100接受署名数据S2，从密钥存储部309读出寄存器装置100的公开密钥PK、素数p及素数q，计算整数n＝p×q，并利用所生成的随机数R2来计算散列值H4。
H4＝Hash(R2)
接下来，认证部302计算S2PK(mod n)，并判断H4与S2PK(mod n)是否一致，如果一致便视为认证成功，如果不一致则视为认证失败。
在认证成功的场合下，认证部302向控制部305通知表示设备认证成功这一意思的信息。并且，在设备认证失败的场合下，向控制部305通知表示设备认证失败这一意思的信息。
在设备认证失败的场合下，此后IC卡300在与寄存器装置100之间不进行信息收发。
(4)再加密部306
再加密部306从求逆运算部313接受公开密钥e′，从除数运算部314接受整数n，并计算下式。
S1e′(mod n)
接下来，再加密部306向认证部302输出所得到的S1e′(mod n)。
(5)控制部305
控制部305接受出错信息、表示设备认证成功这一意思的信息以及表示设备认证失败这一意思的信息。
控制部305从认证部302接受到出错信息后，对构成IC卡300的其它构成要素，指示停止动作。
控制部305从认证部302接受到表示设备认证失败这一意思的信息后，对构成IC卡300的其它构成要素，指示停止动作。另一方面，在接受到表示设备认证成功这一意思的信息后，继续以后的动作。
(6)解密部303
解密部303经由读卡器200及输入输出部301，从寄存器装置100接受加密会话密钥C1。
接下来，解密部303从密钥存储部309接受素数p及素数q，从余数运算部312接受数d1，依次运算下式，由此来算出解密会话密钥x。
A＝p-1(mod q)
y1＝C1(mod p)
y2＝C1(mod q)
d2＝d(mod q-1)
x1＝y1d1(mod p)
x2＝y2d2(mod q)
x＝{a(x2-x1)(mod q)}p+x1
接下来，向解密部308输出由计算所得到的解密会话密钥x。
(7)解密部308
解密部308经由读卡器200及输入输出部301，从寄存器装置100接受加密点数Et，从解密部303接受解密会话密钥x，将所接受的解密会话密钥x用作密钥，对所接受的加密点数Et施行解密算法D1，生成解密点数Dt，并向信息存储部307写入所生成的解密点数Dt。
这里，解密算法D1是基于共通密钥加密方式的DES的算法，对由加密算法E1生成的加密码解密。
(8)输入输出部301
输入输出部301经由读卡器200，在寄存器装置100与构成IC卡300的其它构成要素之间进行信息的收发。
(9)信息存储部307
信息存储部307具有用于存储解密点数Dt的区域。
1.5秘密通信系统10的动作
对秘密通信系统10的动作进行说明。
(1)秘密通信系统10的整体概要动作
利用图4所示的流程图，对秘密通信系统10的整体概要动作进行说明。
IC卡300所具有的高速公开密钥运算部304的余数运算部312算出d1＝d(mod p-1)(步骤S101)，求逆运算部313算出公开密钥e′＝d1-1(modp-1)(步骤S102)。
接下来，寄存器装置100尝试IC卡300的认证(步骤S103)，一旦认证失败(步骤S104)，便结束与IC卡300之间的通信。一旦认证成功(步骤S104)，则继续与IC卡300之间的通信。
接下来IC卡300尝试寄存器装置100的认证(步骤S105)，一旦认证失败(步骤S106)，便结束与寄存器装置100之间的通信。一旦认证成功(步骤S106)，则继续与寄存器装置100之间的通信。
接下来，寄存器装置100对会话密钥加密，生成加密会话密钥，并向IC卡300输出所生成的加密会话密钥，IC卡300对加密会话密钥解密，生成解密会话密钥(步骤S107)，寄存器装置100利用会话密钥，对点数加密，生成加密点数，并发送所生成的加密点数，IC卡300利用解密会话密钥，对加密点数解密(步骤S108)。
(2)基于寄存器装置100的IC卡300的认证动作
利用图5～图6所示的流程图，对基于寄存器装置100的IC卡300的认证动作进行说明。
寄存器装置100的认证部108生成随机数R1(步骤S121)，并经由输入输出部110及读卡器200，向IC卡300输出所生成的随机数R1(步骤S122)。
IC卡300的认证部302经由读卡器200及输入输出部301，从寄存器装置100接受随机数R1(步骤S122)，从密钥存储部309读出素数p及素数q以及秘密密钥d，从除数运算部314接受整数n(步骤S123)，利用所接受的随机数R1来算出散列值H1＝Hash(R1)(步骤S124)。
接下来认证部302算出a＝p-1(mod q)(步骤S125)、
y1＝H1(mod p)(步骤S126)、
y2＝H1(mod q)(步骤S127)、
d2＝d(mod q-1)(步骤S128)、
x1＝y1d1(mod p)(步骤S129)、
x2＝y2d2(mod q)(步骤S130)、
s1＝{a(x2-x1)(mod q)}p+x1(步骤S131)。
再加密部306从求逆运算部313接受公开密钥e′，从除数运算部314接受整数n(步骤S132)，并计算S1e′(mod n)(步骤S133)。
认证部302判断散列值H1与S1e′(mod n)是否一致，在判断为不一致的场合下(步骤S134)，视为发生了某种错误，认证部302向控制部305通知表示发生错误的出错信息。此后，IC卡300停止其动作。
在判断为一致的场合下(步骤S134)，认证部302经由输入输出部301及读卡器200，向寄存器装置100输出所生成的署名数据S1(步骤S141)。
接下来，寄存器装置100的认证部108经由读卡器200及输入输出部110，从IC卡300接受署名数据S1(步骤S141)，从密钥存储部111读出IC卡300的公开密钥e、素数p及素数q(步骤S142)，接下来，对所生成的随机数R1施行散列函数Hash，生成散列值H2＝Hash(R1)(步骤S143)。
接下来，认证部108计算n＝p×q，计算S1e(mod n)(步骤S144)，并对所生成的散列值H2与由计算所得到的值S1e(mod n)进行比较，如果一致(步骤S145)，便视为认证成功，如果不一致(步骤S145)，则视为认证失败。
(3)基于IC卡300的寄存器装置100的认证动作
利用图7所示的流程图，对基于IC卡300的寄存器装置100的认证动作进行说明。
IC卡300的认证部302生成随机数R2(步骤S201)，并经由输入输出部301及读卡器200，向寄存器装置100输出所生成的随机数R2(步骤S202)。
寄存器装置100的认证部108经由读卡器200及输入输出部110，从IC卡300接受随机数R2(步骤S202)，从密钥存储部111读出秘密密钥SK、素数p及素数q(步骤S203)，对所接受的随机数R2施行散列函数Hash，并计算散列值H3＝Hash(R2)(步骤S204)。接下来，认证部108计算n＝p×q，并计算署名数据S2＝(H3)SK(mod n)(步骤S205)，经由输入输出部110及读卡器200，向IC卡300输出由计算所得到的署名数据S2(步骤S206)。
接下来，IC卡300的认证部302经由读卡器200及输入输出部301，从寄存器装置100接受署名数据S2(步骤S206)，从密钥存储部309读出寄存器装置100的公开密钥PK、素数p及素数q(步骤S207)，计算整数n＝p×q，并利用所生成的随机数R2，来计算散列值H4＝Hash(R2)(步骤S208)。接下来，认证部302计算S2PK(mod n)(步骤S209)，判断H4与S2PK(mod n)是否一致，如果一致(步骤S210)，便视为认证成功，如果不一致(步骤S210)，则视为认证失败。
在设备认证失败的场合下，此后IC卡300在与寄存器装置100之间不进行信息收发。
(4)会话密钥的交接动作
利用图8所示的流程图，对会话密钥的交接动作进行说明。
寄存器装置100的加解密部109生成随机数，并将所生成的随机数作为会话密钥M(步骤S251)。接下来从密钥存储部111读出素数p、素数q及公开密钥e，计算整数n＝p×q，并利用会话密钥M、整数n及公开密钥e，算出加密会话密钥C1＝Me(mod n)(步骤S252)。接下来，经由输入输出部110及读卡器200，向IC卡300输出由计算所得到的加密会话密钥C1(步骤S253)。
接下来，IC卡300的解密部303经由读卡器200及输入输出部301，从寄存器装置100接受加密会话密钥C1(步骤S253)，接着从密钥存储部309接受素数p及素数q，从余数运算部312接受数d1，并依次运算下式。
a＝p-1(mod q)(步骤S256)
y1＝C1(mod p)(步骤S257)
y2＝C1(mod q)(步骤S258)
d2＝d(mod q-1)(步骤S259)
x1＝y1d1(mod p)(步骤S260)
x2＝y2d2(mod q)(步骤S261)
x＝{a(x2-x1)(mod q)}p+x1(步骤S262)
接下来，向解密部308输出由计算所得到的解密会话密钥x(步骤S263)。
(5)点数的秘密通信的动作
利用图9所示的流程图，对点数的秘密通信动作进行说明。
寄存器装置100的控制部107由小卖店销售人员的操作，根据利用者所购入商品的购入额，来生成特惠即点数Pt(步骤S291)。接下来，加解密部109将所生成的会话密钥M用作密钥，对点数Pt施行加密算法E1，生成加密点数Et＝E1(会话密钥M、点数Pt)(步骤S292)，接下来，经由输入输出部110及读卡器200，向IC卡300输出加密点数Et(步骤S293)。
IC卡300的解密部308经由读卡器200及输入输出部301，从寄存器装置100接受加密点数Et(步骤S293)，从解密部303接受解密会话密钥x，将所接受的解密会话密钥x用作密钥，对所接受的加密点数Et施行解密算法D1，生成解密点数Dt(步骤S294)，并向信息存储部307写入所生成的解密点数Dt(步骤S295)。
1.6e′成为公开密钥的证明
以下，对在d1＝d(mod p-1)时，e′＝d1-1(mod p-1)成为公开密钥这一事实进行证明。
公开密钥e′由e′＝d-1(mod LCM(p-1，q-1))来定义。这里，LCM(x，y)表示x与y的最小公倍数。
由于LCM(p-1，q-1)可以表现为n×(p-1)，因而成为：
e′×d＝n×(m×(p-1))+1。
这里，如果假设e＜p-1，则成为：
e′×(k×(p-1)+d1)＝n×(m×(p-1))+1
e′×d1＝(n×m-e×k)×(p-1)+1，
从而成为：
e′＝d1-1(mod p-1)。
2.第2实施方式
以下对作为本发明涉及的其它实施方式的RSA秘密通信系统20进行说明。
(1)RSA秘密通信系统20的构成
RSA秘密通信系统20如图10所示，其构成包括RSA加密装置500、RSA解密装置400及存储卡600，RSA加密装置500及RSA解密装置400经由网络50来连接。
在RSA加密方式下的密钥生成中，对于大小相异的2个素数p及素数q，生成成为数n＝p×q，并与p-1同q-1的最小公倍数1cm互素，而且满足p-1＞e的公开密钥e。此外在以最小公倍数1cm为除数的余数体中，生成公开密钥e的逆元，所生成的逆元成为秘密密钥d。如此生成的公开密钥e被预先通知到RSA加密装置500。
RSA加密装置500由RSA加密方式，将公开密钥e用作密钥，对明码M加密，算出加密码C＝Me(mod n)。这里是n＝p×q。
存储卡600是可移动型半导体存储器，预先存储有解密处理所用的秘密密钥d、素数p及素数q。
RSA解密装置400是对由RSA加密装置500生成的加密码C＝Me(mod n)解密的装置，如图10所示，其构成包括由数据输入部401、LSI部420、数据输出部404及数据输入部406。LSI部420是系统LSI，包含数据解密部402、高速公开密钥运算部403及数据再加密部405。并且，高速公开密钥运算部403包含秘密密钥取得部411、余数运算部412、除数运算部413及求逆运算部414。
数据输入部401经由网络50，从RSA加密装置500取得解密对象即加密码C＝Me(mod n)。
数据输入部406从存储卡600取得解密处理用的秘密密钥d、素数p及素数q。
数据解密部402为实现处理高速化，由中国余数定理(ChineseRemainder Theorem，简称CRT)，并利用由数据输入部406取得的秘密密钥d、素数p、素数q以及由高速公开密钥运算部403算出的d1，对加密码C解密，生成解密码D。具体地说，进行以下所示的运算。
a＝p-1(mod q)
y1＝C(mod p)
y2＝C(mod q)
d2＝d(mod q-1)
x1＝y1d1(mod p)
x2＝y2d2(mod q)
D＝{a(x2-x1)(mod q)}p+x1
接下来，数据解密部402向数据输出部404及数据再加密部405输出所生成的解密码D。
高速公开密钥运算部403从数据输入部406取得秘密密钥e、素数p、素数q，运算公开密钥e1。部分中途结果被传送给数据解密部402，用于解密运算。
高速公开密钥运算部403的秘密密钥取得部411从数据输入部406取得秘密密钥d、素数p及素数q。
除数运算部413进行素数p与素数q的相乘，算出整数n。
余数运算部412从秘密密钥d、素数p、素数q算出d1＝d mod(p-1)的值，并保持所算出的d1。
求逆运算部414算出以p-1为除数的余数体上d1的逆e1＝d1-1(modp-1)，接下来将所算出的逆e1作为公开密钥，向数据再加密部405输出。此外向数据解密部402输出d1。
数据再加密部405利用由高速公开密钥运算部403生成的公开密钥e1，对由数据解密部402解密而生成的解密码D进行再加密，生成再加密码C′＝De1(mod n)，并向数据输出部404输出所生成的再加密码C′。
数据输出部404将由数据再加密部405得到的再加密码C′与由数据输入部401得到的加密码C进行比较，在再加密码C′与加密码C一致的场合下，向外部输出由数据解密部402得到的解密码D。在再加密码C′与加密码C不一致的场合下，不输出解密码D。
(2)RSA解密装置400中的RSA解密动作
接下来，利用图11所示的流程图，对RSA解密装置400中的RSA解密动作进行说明。
数据输入部401取得加密码C，数据输入部406取得秘密密钥d、素数p及素数q(步骤S401)。
接下来，高速公开密钥运算部403的秘密密钥取得部411取得秘密密钥d、素数p及素数q，除数运算部413进行素数p与素数q的相乘，算出整数n，余数运算部412从秘密密钥d、素数p、素数q来算出d1＝dmod(p-1)的值，并保持d1，求逆运算部414算出公开密钥e1＝d1-1(modp-1)(步骤S402)。
接下来，数据解密部402利用中国余数定理(CRT)，对加密码C解密，生成解密码D(步骤S403)。
数据再加密部405利用由高速公开密钥运算部403生成的公开密钥e1，对解密码D进行再加密，生成再加密码C′(步骤S404)。
数据输出部404将再加密码C′与加密码C进行比较，在再加密码C′与加密码C一致的场合下(步骤S405)，向外部输出解密码D(步骤S406)。在再加密码C′与加密码C不一致的场合下(步骤S405)，不输出解密码D，而显示或输出表示发生了故障这一意思的消息(步骤S407)。
(3)总结
根据上述第2实施方式，对计算公开密钥e1的值的求逆运算的输入成为传统位长的一半。由于逆元运算所需的存储量与输入位长成比例，处理时间与输入位长的平方成比例，因而存储量及处理时间均可大幅缩减。此外由于成为求逆运算的输入值的d1也可以挪用于采用了中国余数定理的解密运算，因而具有还可削减解密运算的处理时间的效果。
此外在本实施方式中，所表示的是一种在高速公开密钥运算部内设置计算d1的余数运算部，并将该值发送给数据解密部来利用的构成，但也可以在数据解密部内设置余数运算部来计算d1，并将该值发送到高速公开密钥运算部。在该场合下，在图11的流程图中，上部的高速公开密钥生成步骤(步骤S402)与高速解密步骤(步骤S403)的顺序颠倒。
3.第3实施方式
以下对作为第2实施方式的RSA秘密通信系统20的变形例的RSA秘密通信系统30进行说明。
(1)RSA秘密通信系统30的构成
RSA秘密通信系统30具有与RSA秘密通信系统20类似的构成。这里以与RSA秘密通信系统20的相异点为中心进行说明。
RSA秘密通信系统30如图12所示，其构成包括由RSA加密装置500、RSA解密装置400b、CRT信息生成装置700及存储卡600b，RSA加密装置500及RSA解密装置400经由网络50来连接。
存储卡600b是与存储卡600同样的可移动型半导体存储器，预先存储有解密处理用的秘密密钥d、素数p及素数q。
CRT信息生成装置700从存储卡600b读出秘密密钥d、素数p及素数q，利用所读出的秘密密钥d、素数p及素数q，来算出：
d1＝d mod(p-1)以及
d2＝d mod(q-1)，并向存储卡600b写入由计算所得到的d1及d2。
RSA解密装置400b是具有与RSA解密装置400同样的构成，并对由RSA加密装置500生成的加密码C＝Me(mod n)进行解密的装置，如图12所示，其构成包括数据输入部401、LSI部420b、数据输出部404及数据输入部406b。LSI部420b是具有与LSI部420同样构成的系统LSI，包含数据解密部402、高速公开密钥运算部403b以及数据再加密部405。此外高速公开密钥运算部403b包含秘密密钥取得部411b、除数运算部413及求逆运算部414。
数据输入部406b从存储卡600b取得解密处理用的秘密密钥d、素数p、素数q、d1及d2。
数据解密部402b利用由数据输入部406b取得的秘密密钥d、素数p、素数q、d1及d2，对加密码C解密，生成解密码D。具体地说，进行以下所示的运算。
a＝p-1(mod q)
y1＝C(mod p)
y2＝C(mod q)
x1＝y1d1(mod p)
x2＝y2d2(mod q)
D＝{a(x2-x1)(mod q)}p+x1
接下来，数据解密部402b向数据输出部404及数据再加密部405输出所生成的解密码D。
这里，数据解密部402b不进行d2＝d(mod q-1)的运算，而从存储卡600b取得d2，这一点与数据解密部402不同。
高速公开密钥运算部403b从数据输入部406取得秘密密钥e、素数p、素数q、d1，运算公开密钥e1。部分中途结果被传送给数据解密部402，用于解密运算。
高速公开密钥运算部403b的秘密密钥取得部411b从数据输入部406b取得素数p、素数q、d1。
除数运算部413进行素数p与素数q的相乘，算出整数n。
求逆运算部414算出以p-1为除数的余数体上d1的逆e1＝d1-1(modp-1)，接下来将所算出的逆e1作为公开密钥，向数据再加密部405输出。
(2)RSA秘密通信系统30的动作
利用图13所示的流程图，对RSA秘密通信系统30的动作进行说明。
CRT信息生成装置700从存储卡600b读出秘密密钥d、素数p及素数q(步骤S431)，利用所读出的秘密密钥d、素数p及素数q，算出d1＝dmod(p-1)及d2＝d mod(q-1)(步骤S432)，并向存储卡600b写入由计算所得到的d1及d2(步骤S433)。
RSA解密装置400b的数据输入部406b从存储卡600b取得解密处理用的秘密密钥d、素数p、素数q、d1及d2(步骤S434)。
数据输入部401经由网络50，从RSA加密装置500取得加密码C(步骤S435)。
数据解密部402b利用由数据输入部406b取得的秘密密钥d、素数p、素数q、d1及d2，由中国余数定理，对加密码C解密，生成解密码D(步骤S436)。
接下来，求逆运算部414算出逆e1＝d1-1(mod p-1)(步骤S437)，数据再加密部405利用公开密钥e1，对解密码D再次加密，生成再加密码C′(步骤S438)。
接下来，
数据输出部404将再加密码C′与加密码C进行比较，在再加密码C′与加密码C一致的场合下(步骤S439)，向外部输出解密码D(步骤S440)。在再加密码C′与加密码C不一致的场合下(步骤S439)，不输出解密码D，而显示或输出表示发生了故障的消息(步骤S441)。
(3)总结
如上所述，在第3实施方式中，RSA解密装置从外部取得的不是传统的秘密密钥，而是预先计算出的中国余数定理(CRT)运算用的秘密密钥。即取得d1＝d mod(p-1)、d2＝d mod(q-1)、p、q的值。此外根据中国余数定理的利用方法，在从外部取得的数据中也可以至少包含d1。
数据解密部402及高速公开密钥运算部403b利用由数据输入部406b取得的值，来进行各自的处理。因此如第2实施方式所示，不必在数据解密部402与高速公开密钥运算部403之间收发值d1。
由于值d1从外部来取得，因而在高速公开密钥运算部403b中，不必设置第2实施方式所示的余数运算部412。
此外第3实施方式中，从外部取得d1＝d mod(p-1)、d2＝d mod(q-1)、p、q，但根据中国余数定理的利用方法，在从外部取得的数据中也可以至少包含d1。
并且，在图13所示的流程图中，在高速解密步骤(步骤S436)之后，实施高速公开密钥取得步骤(步骤S437)，但先实施高速解密步骤与高速公开密钥取得步骤的任意一方都是可以的。即也可以在高速公开密钥取得步骤(步骤S437)之后，实施高速解密步骤(步骤S436)。
根据第3实施方式，除了实施方式2的效果之外，无需用于求算d2的余数运算，因而具有可进一步削减处理时间的优异效果。
另外，在上述说明中，以RSA解密装置中的示例来作说明，但对于RSA署名生成装置，也可同样实施。
此外不限于RSA解密装置及RSA署名生成装置，对于从RSA秘密密钥来取得RSA公开密钥的场合也可同样实施。
4.总结
本发明是一种RSA公开密钥复原装置，其在利用素数p与q、与p-1同q-1的最小公倍数1cm互素并满足p-1＞e的数e、以1cm为除数的余数体中e的逆元即d以及p与q之积n，将(e，n)用作公开密钥，将(d，p，q)用作秘密密钥的RSA密码中，从上述秘密密钥(d，p，q)来使上述公开密钥(e，n)复原，具有
第一秘密密钥输入单元，其输入RSA密码的秘密密钥(d，p，q)；
第一余数单元，其利用由上述第一秘密密钥输入单元输入的秘密密钥d与p，来求出以p-1为除数的d的余数即dp＝d mod(p-1)；
第一逆元运算单元，其利用由上述第一余数单元得到的dp及由上述第一秘密密钥输入单元输入的p，来求出以p-1为除数的余数体中dp的逆元；
公开密钥输出单元，其将由上述第一秘密密钥输入单元输入的秘密密钥p与q之积设为n，将由上述第一逆元运算单元得到的逆元设为e，将(e，n)作为RSA公开密钥来输出。
并且，本发明是一种RSA解密装置，其在利用素数p与q、与p-1同q-1的最小公倍数1cm互素并满足p-1＞e的数e、以1cm为除数的余数体中e的逆元即d以及p与q之积n，将(e，n)用作公开密钥，将(d，p，q)用作秘密密钥的RSA密码中，从由上述公开密钥加密的加密码，来对原明码解密，具有
输入加密码C的加密码输入单元；
第二秘密密钥输入单元，其输入RSA密码的秘密密钥(d，p，q)；
解密单元，其利用由上述第二秘密密钥输入单元输入的秘密密钥，从由上述加密码输入单元输入的加密码C来对明码P解密；
第二余数单元，其利用由上述第二秘密密钥输入单元输入的秘密密钥d与p，来求出以p-1为除数的d的余数即dp＝d mod(p-1)；
第二逆元运算单元，其利用由上述第二余数单元得到的dp及由上述第二秘密密钥输入单元输入的p，来求出以p-1为除数的余数体中dp的逆元；
第一公开密钥复原单元，其将由上述第二秘密密钥输入单元输入的秘密密钥p与q之积设为n，将由上述第二逆元运算单元得到的逆元设为e，将(e，n)作为RSA公开密钥来保持；
加密单元，其利用由上述第一公开密钥复原单元保持的公开密钥，从由上述解密单元求出的明码P来求出加密码C′；
第一验算单元，其将由上述加密单元求出的加密码C′与由上述加密码输入单元输入的加密码C进行比较；
解密结果输出单元，其只在上述第一验算单元的比较结果一致时，才输出明码P。
这里，也可以取代上述解密单元，而配备CRT解密单元，其利用由上述第二秘密密钥输入单元输入的秘密密钥以及由上述第二余数单元得到的dp，通过采用了中国余数定理(CRT)的算法，从由上述加密码输入单元输入的加密码C来对明码P解密。
这里，也可以取代上述第二秘密密钥输入单元及上述第二余数单元，而具备第三秘密密钥输入单元，其预先将至少包含dp而且利用了中国余数定理的算法所必需的值作为RSA密码的秘密密钥来输入，
上述第二逆元运算单元、上述第一公开密钥复原单元、上述CRT解码单元也可以采用由上述第三秘密密钥输入单元输入的值。
这里，也可以还具备第一出错输出单元，其当上述第一验算单元的比较结果不一致时，输出发生故障这一大意。
并且，本发明是一种RSA署名生成装置，其在利用素数p与q、与p-1同q-1的最小公倍数1cm互素并满足p-1＞e的数e、以1cm为除数的余数体中e的逆元即d以及p与q之积n，将(e，n)用作公开密钥，将(d，p，q)用作秘密密钥的RSA密码中，从明码来生成署名码，具有
输入明码P的明码输入单元；
第四秘密密钥输入单元，其输入RSA密码的秘密密钥(d，p，q)；
署名生成单元，其利用由上述第四秘密密钥输入单元输入的秘密密钥，从由上述明码输入单元输入的明码P来生成署名码S；
第三余数单元，其利用由上述第四秘密密钥输入单元输入的秘密密钥d与p，来求出以p-1为除数的d的余数即dp＝d mod(p-1)；
第三逆元运算单元，其利用由上述第三余数单元得到的dp及由上述第四秘密密钥输入单元输入的p，来求出以p-1为除数的余数体中dp的逆元；
第二公开密钥复原单元，其将由上述第四秘密密钥输入单元输入的秘密密钥p与q之积设为n，将由上述第三逆元运算单元得到的逆元设为e，将(e，n)作为RSA公开密钥来保持；
明码恢复单元，其利用由上述第二公开密钥复原单元保持的公开密钥，从由上述署名生成单元求出的署名码S来求出明码P′；
第二验算单元，其将由上述明码恢复单元求出的明码P′与由上述明码输入单元输入的明码P进行比较；
署名结果输出单元，其只在上述第二验算单元的比较结果一致时，才输出署名码S。
这里，也可以取代上述署名生成单元，而配备CRT署名生成单元，其利用由上述第四秘密密钥输入单元输入的秘密密钥以及由上述第三余数单元得到的dp，通过采用了中国余数定理(CRT)的算法，从由上述明码输入单元输入的明码P来生成署名码S。
这里，也可以取代上述第四秘密密钥输入单元及上述第三余数单元，而具备第五秘密密钥输入单元，其预先将至少包含dp而且利用了中国余数定理的算法所必需的值作为RSA密码的秘密密钥来输入，
上述第三逆元运算单元、上述第二公开密钥复原单元、上述CRT署名生成单元也可以采用由上述第五秘密密钥输入单元输入的值。
这里，也可以还具备第二出错输出单元，其当上述第二验算单元的比较结果不一致时，输出发生故障这一大意。
并且，本发明是一种RSA公开密钥复原方法，其在利用素数p与q、与p-1同q-1的最小公倍数1cm互素并满足p-1＞e的数e、以1cm为除数的余数体中e的逆元即d以及p与q之积n，将(e，n)用作公开密钥，将(d，p，q)用作秘密密钥的RSA密码中，从上述秘密密钥(d，p，q)来使上述公开密钥(e，n)复原，包括
第一秘密密钥输入步骤，其输入RSA密码的秘密密钥(d，p，q)；
第一余数步骤，其利用由上述第一秘密密钥输入步骤输入的秘密密钥d与p，来求出以p-1为除数的d的余数即dp＝d mod(p-1)；
第一逆元运算步骤，其利用由上述第一余数步骤得到的dp及由上述第一秘密密钥输入步骤输入的p，来求出以p-1为除数的余体中dp的逆元；
公开密钥输出步骤，其将由上述第一秘密密钥输入步骤输入的秘密密钥p与q之积设为n，将由上述第一逆元运算步骤得到的逆元设为e，将(e，n)作为RSA公开密钥来输出。
本发明是一种RSA解密方法，其在利用素数p与q、与p-1同q-1的最小公倍数1cm互素并满足p-1＞e的数e、以1cm为除数的余数体中e的逆元即d以及p与q之积n，将(e，n)用作公开密钥，将(d，p，q)用作秘密密钥的RSA密码中，从由上述公开密钥加密的加密码，来对原明码解密，包括
输入加密码C的加密码输入步骤；
第二秘密密钥输入步骤，其输入RSA密码的秘密密钥(d，p，q)；
解密步骤，其利用由上述第二秘密密钥输入步骤输入的秘密密钥，从由上述加密码输入步骤输入的加密码C来对明码P解密；
第二余数步骤，其利用由上述第二秘密密钥输入步骤输入的秘密密钥d与p，来求出以p-1为除数的d的余数即dp＝d mod(p-1)；
第二逆元运算步骤，其利用由上述第二余数步骤得到的dp及由上述第二秘密密钥输入步骤输入的p，来求出以p-1为除数的余数体中dp的逆元；
第一公开密钥复原步骤，其将由上述第二秘密密钥输入步骤输入的秘密密钥p与q之积设为n，将由上述第二逆元运算步骤得到的逆元设为e，将(e，n)作为RSA公开密钥来保持；
加密步骤，其利用由上述第一公开密钥复原步骤保持的公开密钥，从由上述解密步骤求出的明码P来求出加密码C′；
第一验算步骤，其将由上述加密步骤求出的加密码C′与由上述加密码输入步骤输入的加密码C进行比较；
解密结果输出步骤，其只在上述第一验算步骤的比较结果一致时，才输出明码P。
这里，也可以取代上述解密步骤，而包括CRT解密步骤，其利用由上述第二秘密密钥输入步骤输入的秘密密钥以及由上述第二余数步骤得到的dp，通过采用了中国余数定理(CRT)的算法，从由上述加密码输入步骤输入的加密码C来对明码P解密。
这里，也可以取代上述第二秘密密钥输入步骤及上述第二余数步骤，而包括第三秘密密钥输入步骤，其预先将至少包含dp而且利用了中国余数定理的算法所必需的值作为RSA密码的秘密密钥来输入，
上述第二逆元运算步骤、上述第一公开密钥复原步骤、上述CRT解密步骤也可以采用由上述第三秘密密钥输入步骤输入的值。
这里，也可以还具备第一出错输出步骤，其当上述第一验算步骤的比较结果不一致时，输出发生故障这一大意。
并且，本发明是一种RSA署名生成方法，其在利用素数p与q、与p-1同q-1的最小公倍数1cm互素并满足p-1＞e的数e、以1cm为除数的余数体中e的逆元即d以及p与q之积n，将(e，n)用作公开密钥，将(d，p，q)用作秘密密钥的RSA密码中，从明码来生成署名码，包括
输入明码P的明码输入步骤；
第四秘密密钥输入步骤，其输入RSA密码的秘密密钥(d，p，q)；
署名生成步骤，其利用由上述第四秘密密钥输入步骤输入的秘密密钥，从由上述明码输入步骤输入的明码P来生成署名码S；
第三余数步骤，其利用由上述第四秘密密钥输入步骤输入的秘密密钥d与p，来求出以p-1为除数的d的余数即dp＝d mod(p-1)；
第三逆元运算步骤，其利用由上述第三余数步骤得到的dp及由上述第四秘密密钥输入步骤输入的p，来求出以p-1为除数的余数体中dp的逆元；
第二公开密钥复原步骤，其将由上述第四秘密密钥输入步骤输入的秘密密钥p与q之积设为n，将由上述第三逆元运算步骤得到的逆元设为e，将(e，n)作为RSA公开密钥来保持；
明码恢复步骤，其利用由上述第二公开密钥复原步骤保持的公开密钥，从由上述署名生成步骤求出的署名码S来求出明码P′；
第二验算步骤，其将由上述明码恢复步骤求出的明码P′与由上述明码输入步骤输入的明码P进行比较；
署名结果输出步骤，其只在上述第二验算步骤的比较结果一致时，才输出署名码S。
这里，也可以取代上述署名生成步骤，而包括CRT署名生成步骤，其利用由上述第四秘密密钥输入步骤输入的秘密密钥以及由上述第三余数步骤得到的dp，通过采用了中国余数定理(CRT)的算法，从由上述明码输入步骤输入的明码P来生成署名码S。
这里，也可以取代上述第四秘密密钥输入步骤及上述第三余数步骤，而包括第五秘密密钥输入步骤，其预先将至少包含dp而且利用了中国余数定理的算法所必需的值作为RSA密码的秘密密钥来输入，
上述第三逆元运算步骤、上述第二公开密钥复原步骤、上述CRT署名生成步骤也可以采用由上述第五秘密密钥输入步骤输入的值。
这里，也可以还包括第二出错输出步骤，其当上述第二验算步骤的比较结果不一致时，输出发生故障这一大意。
并且，本发明是一种RSA公开密钥复原程序，其在利用素数p与q、与p-1同q-1的最小公倍数1cm互素并满足p-1＞e的数e、以1cm为除数的余数体中e的逆元即d以及p与q之积n，将(e，n)用作公开密钥，将(d，p，q)用作秘密密钥的RSA密码中，从上述秘密密钥(d，p，q)来使上述公开密钥(e，n)复原，包括
第一秘密密钥输入步骤，其输入RSA密码的秘密密钥(d，p，q)；
第一余数步骤，其利用由上述第一秘密密钥输入步骤输入的秘密密钥d与p，来求出以p-1为除数的d的余数即dp＝d mod(p-1)；
第一逆元运算步骤，其利用由上述第一余数步骤得到的dp及由上述第一秘密密钥输入步骤输入的p，来求出以p-1为除数的余数体中dp的逆元；
公开密钥输出步骤，其将由上述第一秘密密钥输入步骤输入的秘密密钥p与q之积设为n，将由上述第一逆元运算步骤得到的逆元设为e，将(e，n)作为RSA公开密钥来输出。
本发明是一种RSA解密程序，其在利用素数p及q、与p-1同q-1的最小公倍数1cm互素并满足p-1＞e的数e、以1cm为除数的余数体中e的逆元即d以及p与q之积n，将(e，n)用作公开密钥，将(d，p，q)用作秘密密钥的RSA密码中，从由上述公开密钥加密的加密码，来对原明码解密，包括
输入加密码C的加密码输入步骤；
第二秘密密钥输入步骤，其输入RSA密码的秘密密钥(d，p，q)；
解密步骤，其利用由上述第二秘密密钥输入步骤输入的秘密密钥，从由上述加密码输入步骤输入的加密码C来对明码P解密；
第二余数步骤，其利用由上述第二秘密密钥输入步骤输入的秘密密钥d与p，来求出以p-1为除数的d的余数即dp＝d mod(p-1)；
第二逆元运算步骤，其利用由上述第二余数步骤得到的dp及由上述第二秘密密钥输入步骤输入的p，来求出以p-1为除数的余数体中dp的逆元；
第一公开密钥复原步骤，其将由上述第二秘密密钥输入步骤输入的秘密密钥p与q之积设为n，将由上述第二逆元运算步骤得到的逆元设为e，将(e，n)作为RSA公开密钥来保持；
加密步骤，其利用由上述第一公开密钥复原步骤保持的公开密钥，从由上述解密步骤求出的明码P来求出加密码C′；
第一验算步骤，其将由上述加密步骤求出的加密码C′与由上述加密码输入步骤输入的加密码C进行比较；
解密结果输出步骤，其只在上述第一验算步骤的比较结果一致时，才输出明码P。
并且，也可以取代上述解密步骤，而包括CRT解密步骤，其利用由上述第二秘密密钥输入步骤输入的秘密密钥以及由上述第二余数步骤得到的dp，通过采用了中国余数定理(CRT)的算法，从由上述加密码输入步骤输入的加密码C来对明码P解密。
并且，也可以取代上述第二秘密密钥输入步骤及上述第二余数步骤，而包括第三秘密密钥输入步骤，其预先将至少包含dp而且利用了中国余数定理的算法所必需的值作为RSA密码的秘密密钥来输入，
上述第二逆元运算步骤、上述第一公开密钥复原步骤、上述CRT解码步骤也可以采用由上述第三秘密密钥输入步骤输入的值。
并且，也可以还具备第一出错输出步骤，其当上述第一验算步骤的比较结果不一致时，输出发生故障这一大意。
本发明是一种RSA署名生成程序，其在利用素数p与q、与p-1同q-1的最小公倍数1cm互素并满足p-1＞e的数e、以1cm为除数的余数体中e的逆元即d以及p与q之积n，将(e，n)用作公开密钥，将(d，p，q)用作秘密密钥的RSA密码中，从明码来生成署名码，包括
输入明码P的明码输入步骤；
第四秘密密钥输入步骤，其输入RSA密码的秘密密钥(d，p，q)；
署名生成步骤，其利用由上述第四秘密密钥输入步骤输入的秘密密钥，从由上述明码输入步骤输入的明码P来生成署名码S；
第三余数步骤，其利用由上述第四秘密密钥输入步骤输入的秘密密钥d与p，来求出以p-1为除数的d的余数即dp＝d mod(p-1)；
第三逆元运算步骤，其利用由上述第三余数步骤得到的dp及由上述第四秘密密钥输入步骤输入的p，来求出以p-1为除数的余数体中dp的逆元；
第二公开密钥复原步骤，其将由上述第四秘密密钥输入步骤输入的秘密密钥p与q之积设为n，将由上述第三逆元运算步骤得到的逆元设为e，将(e，n)作为RSA公开密钥来保持；
明码恢复步骤，其利用由上述第二公开密钥复原步骤保持的公开密钥，从由上述署名生成步骤求出的署名码S来求出明码P′；
第二验算步骤，其将由上述明码恢复步骤求出的明码P′与由上述明码输入步骤输入的明码P进行比较；
署名结果输出步骤，其只在上述第二验算步骤的比较结果一致时，才输出署名码S。
这里，也可以取代上述署名生成步骤，而包括CRT署名生成步骤，其利用由上述第四秘密密钥输入步骤输入的秘密密钥以及由上述第三余数步骤得到的dp，通过采用了中国余数定理(CRT)的算法，从由上述明码输入步骤输入的明码P来生成署名码S。
这里，也可以取代上述第四秘密密钥输入步骤及上述第三余数步骤，而包括第五秘密密钥输入步骤，其预先将至少包含dp而且利用了中国余数定理的算法所必需的值作为RSA密码的秘密密钥来输入，
上述第三逆元运算步骤、上述第二公开密钥复原步骤、上述CRT署名生成步骤也可以采用由上述第五秘密密钥输入步骤输入的值。
这里，也可以还具备第二出错输出步骤，其当上述第二验算步骤的比较结果不一致时，输出发生故障这一大意。
如上所述，本发明涉及的RSA密码处理装置具有使故障利用攻击不能得逞，并高速进行RSA解密处理等的性质，作为有可能受到IC卡等故障利用攻击，同时还必须进行RSA加密处理的装置等非常有用。
根据本发明的RSA公开密钥复原装置，为求出公开密钥而取用逆元的被运算值成为秘密密钥大约一半的位数的值。因此可大幅削减逆元运算所必需的存储量以及处理时间。
并且，根据本发明的RSA密码处理装置，为求出公开密钥而取用逆元的被运算值成为秘密密钥大约一半的位数的值。因此与传统相比，可大幅削减逆元运算所需的时间，其结果是，可缩短使故障利用攻击不能得逞的RSA解密处理等所需的时间。
此外，根据本发明的RSA密码处理装置，为求出公开密钥而取用逆元的被运算值，可按原样用于采用了中国余数定理算法的RSA解密处理。因而可缩短使故障利用攻击不能得逞的RSA解密处理等所需的时间。
此外，根据本发明的RSA公开密钥复原装置及RSA密码处理装置，公开密钥的值对于素数p被限制到p-1以下，但一般不会发生RSA密码的公开密钥取得较小的问题。
5.其它变形例
另外，基于上述实施方式对本发明作了说明，但毋庸赘言，本发明并非限定于上述实施方式。本发明也包含以下场合。
(1)在第1实施方式中，IC卡300包含系统LSI320，但并非限定于此。比如高速公开密钥运算部304也可以构成1个大规模集成电路。
并且，在第2实施方式中，RSA解密装置400包含LSI部420，但并非限定于此。比如高速公开密钥运算部403也可以构成1个大规模集成电路。
并且，在第3实施方式中，RSA解密装置400b包含LSI部420b，但并非限定于此。比如高速公开密钥运算部403b也可以构成1个大规模集成电路。
(2)具体地说，上述各装置是构成包括微处理器、ROM、RAM等的计算机系统。上述RAM中存储有计算机程序。上述微处理器按照上述计算机程序来动作，各装置由此来实现其功能。
(3)本发明可以是上述所示的方法。并且，也可以是由计算机实现这些方法的计算机程序，还可以是由上述计算机程序所组成的数字信号。
并且，本发明也可以将上述计算机程序或上述数字信号记录到计算机可读取的记录媒体，比如软盘、硬盘、CD-ROM、MO、DVD、DVD-ROM、DVD-RAM、BD(Blu-ray Disc，蓝光盘)、半导体存储器等。此外也可以是这些记录媒体中记录的上述计算机程序或上述数字信号。
并且，本发明也可以是经由电气通信线路、无线或有线通信线路、以因特网为代表的网络、数据广播等，来传送上述计算机程序或上述数字信号。
此外，本发明也可以是具有微处理器及存储器的计算机系统，上述存储器存储有上述计算机程序，上述微处理器按照上述计算机程序来动作。
并且，也可以通过将上述程序或上述数字信号记录移送到上述记录媒体，或者通过经由上述网络等来移送上述程序或上述数字信号，由此由其它独立的计算机系统来实施。
(4)也可以分别组合上述实施方式及上述变形例。
尽管参照示例及附图对本发明进行了详尽说明，但应注意的是，对本领域的普通技术人员而言，可以做各种变动及修改是显而易见的。因而除非这些变动及修改脱离本发明的范围，否则它们应构成本发明的一部分。
产业上的可利用性
构成本发明的各装置，可以经营性持续反复地用于有必要秘密地处理信息的所有产业、或者有必要认证对方的所有产业。此外在电气设备制造产业中，对构成本发明的各装置可以经营性地持续反复地制造及销售。
以下对作为本发明涉及的第1实施方式的秘密通信系统10进行说明。
1.1秘密通信系统10的构成
秘密通信系统10如图1所示，其构成包括寄存器装置100及IC卡300。
寄存器装置100设置于小卖店内，由小卖店的销售人员来操作，并根据利用者所购入商品的购入额，来发行特惠即点数。寄存器装置100对所发行的点数加密，生成加密点数，经由与寄存器装置100连接的读卡器200，向利用者的IC卡300输出所生成的加密点数。
IC卡300接受加密点数，对所接受的加密点数解密，生成解密点数，并存储所生成的解密点数。
利用者在下次购入商品时，可将IC卡300中存储的解密点数作为货款的一部分来使用。
1.2IC卡300的公开密钥e及秘密密钥d的生成
如下所示，密钥生成装置(未图示)生成IC卡300的公开密钥e及秘密密钥d。
(a)选择任意相异的2个大素数p及素数q，并计算其积n。n＝p×q
(b)计算(p-1)与(q-1)的最小公倍数L，并选择与最小公倍数L互素而且小于最小公倍数L的任意整数e(公开密钥)。
L＝LCM((p-1)，(q-1))
GCD(e，L)＝1
1＜e＜L
这里，LCM(X，Y)表示数X与数Y的最小公倍数，GCD(X，Y)表示数X与数Y的最大公倍数。LCM是Least Common Multiple(最小公倍数)的简称，GCD是Greatest Common Divisor(最大公约数)的简称。
基于在(c)(b)中求出的公开密钥e及最小公倍数L来解算下式，以求出秘密密钥d。
ed＝1(mod L)
密钥生成装置将素数p、素数q及公开密钥e预先通知到寄存器装置100。将素数p、素数q及秘密密钥d预先通知到IC卡300。
寄存器装置100的公开密钥PK及秘密密钥SK也同样由密钥生成装置来生成，秘密密钥SK被预先通知到寄存器装置100，公开密钥PK被预先通知到IC卡300。
1.3寄存器装置100的构成
寄存器装置100如图2所示，其构成包括显示部101、显示部102、印字部103、输入部104、保管库105、信息存储部106、控制部107、认证部108、加解密部109、输入输出部110及密钥存储部111。此外寄存器装置100的输入输出部110与读卡器200相接。
寄存器装置100是进行由利用者支付的购入货款的结算及保管等的钱币寄存器装置，根据利用者所购入商品的购入额，来发行特惠即点数，对所发行的点数加密，生成加密点数，并经由读卡器200，向利用者的IC卡300输出所生成的加密点数。
具体地说，寄存器装置100是一种包含微处理器、ROM、RAM等的计算机系统。上述ROM中存储有计算机程序。上述微处理器按照上述计算机程序来动作，寄存器装置100由此来实现其部分功能。
(1)密钥存储部111
密钥存储部111被设置成不能从外部来访问，如图2所示，预先存储有IC卡300的公开密钥e、素数p、素数q及寄存器装置100的秘密密钥SK。
公开密钥e是由RSA公开密钥加密方式的密钥生成算法所生成的IC卡300的公开密钥，被保存到1024位长的数据区。
素数p及素数q是任意相异的大素数，分别被保存到512位长的数据区。这里作为一例，
p＝
d32737e7 267ffe13 41b2d5c0 d150a81b 586fb313 2bed2f8d 5262864a 9cb9f30a
f38be448 598d413a 172efb80 2c21acf1 c11c520c 2f26a471 dcad212e ac7ca39d
q＝
cc8853d1 d54da630 fac004f4 71f281c7 b8982d82 24a490ed beb33d3e 3d5cc93c
4765703d 1dd79164 2f1f116a 0dd862be 2419b2af 72bfe9a0 30e860b0 288b5d77
这些记载都是16进制数。为了看起来方便，每8位分开表示。
秘密密钥SK是由RSA公开密钥加密方式的密钥生成算法所生成的寄存器装置100的秘密密钥，被保存到1024位长的数据区。
(2)信息存储部106
信息存储部106，具有用于存储识别利用者的利用者识别符及利用者的购入金额、购入日期、发行点数等有关基于利用者的商品购入的信息的区域。
(3)认证部108
当在读卡器200中装有IC卡300时，认证部108经由输入输出部110及读卡器200，如下所示，在与IC卡300之间相互进行设备认证。这里，设备认证是查询响应型认证。
(基于寄存器装置100的IC卡300的认证)
认证部108生成随机数R1，并经由输入输出部110及读卡器200，向IC卡300输出所生成的随机数R1。
此外认证部108经由读卡器200及输入输出部110，从IC卡300接受署名数据S1，从密钥存储部111读出IC卡300的公开密钥e、素数p及素数q。接下来对所生成的随机数R1施行散列函数Hash，生成散列值H2。
H2＝Hash(R1)
这里，Hash(R1)表示对随机数R1施行散列函数Hash所得到的值。散列函数Hash的一例是SHA-1。
接下来，认证部108计算n＝p×q，并计算S1e(mod n)，对所生成的散列值H2与由计算所得到的值S1e(mod n)进行比较，如果一致便视为认证成功，如果不一致则视为认证失败。
在认证成功的场合下，认证部108向控制部107通知表示设备认证成功这一意思的信息。在设备认证失败的场合下，向控制部107通知表示设备认证失败这一意思的信息。
在设备认证失败的场合下，此后寄存器装置100在与该IC卡300之间不进行信息收发。
(基于IC卡300的寄存器装置100的认证)
认证部108经由读卡器200及输入输出部110，从IC卡300接受随机数R2，从密钥存储部111读出秘密密钥SK、素数p及素数q，并对所接受的随机数R2施行散列函数Hash，计算散列值H3。
H3＝Hash(R2)
接下来，认证部108计算n＝p×q，还计算署名数据S2＝(H3)SK(mod n)，并经由输入输出部110及读卡器200，向IC卡300输出由计算所得到的署名数据S2。
(4)输入输出部110及读卡器200
输入输出部110在控制部107与读卡器200之间，对控制部107的控制源进行双向信息收发，或者在认证部108与读卡器200之间，对认证部108的控制源进行双向信息收发。
读卡器200在IC卡300与输入输出部110之间进行信息的收发。
(5)加解密部109
(会话密钥的输出)
加解密部109生成随机数，并将所生成的随机数作为会话密钥M。接下来，从密钥存储部111读出素数p、素数q及公开密钥e，计算整数n＝p×q，并利用会话密钥M、整数n及公开密钥e，由下式来算出加密会话密钥C1。
加密会话密钥C1＝Me(mod n)
接下来，经由输入输出部110及读卡器200，向IC卡300输出由计算所得到的加密会话密钥C1。
(点数的输出)
加解密部109从控制部107接受点数Pt，将所生成的会话密钥M用作密钥，对所接受的点数Pt施行加密算法E1，生成加密点数Et。
加密点数Et＝E1(会话密钥M、点数Pt)
这里，E(A，B)表示利用密钥A，对明码B施行加密算法E所得到的加密码。作为一例，加密算法E1是一种基于共通密钥加密方式的DES(Data Encryption Standard，数据加密标准)的算法。
接下来，加解密部109经由输入输出部110及读卡器200，向IC卡300输出加密点数Et。
(6)控制部107
控制部107由小卖店销售人员的操作，根据利用者所购入商品的购入额，来生成特惠即点数Pt，并向加解密部109输出所生成的点数Pt。
控制部107控制构成寄存器装置100的其它构成要素。
(7)输入部104、显示部101、显示部102、印字部103及保管库105
输入部104从寄存器装置100的操作者来接受输入信息，并向控制部107输出所接受的输入信息。显示部101及显示部102从控制部107接受应显示的信息，并显示出所接受的信息。
印字部103由控制部107的控制，来印刷各种信息。
保管库105保管纸币及货币。
1.4IC卡300的构成
IC卡300由长度约为85mm，宽度为54mm，厚度为0.76mm的薄片状树脂来形成，外表面上有接触端子，在内部密封有系统LSI(大规模集成电路，Large Scale Integrated circuit)320。
IC卡300如图3所示，结构包括输入输出部301、认证部302、解密部303、高速公开密钥运算部304、控制部305、再加密部306、信息存储部307、解密部308及密钥存储部309，认证部302、解密部303、高速公开密钥运算部304、控制部305、再加密部306、信息存储部307、解密部308及密钥存储部309形成系统LSI320。
系统LSI320是一种在1个芯片上集成上述多个构成部来制造的较长多功能LSI，具体地说，是一种包含微处理器、ROM、RAM等来构成的计算机系统。上述RAM中存储有计算机程序。上述微处理器按照上述计算机程序来动作，系统LSI320由此来实现其部分功能。
(1)密钥存储部309
密钥存储部309如图3所示，预先存储有寄存器装置100的公开密钥PK、素数p、素数q及IC卡300的秘密密钥d。
公开密钥PK是由RSA公开密钥加密方式的密钥生成算法所生成的寄存器装置100的公开密钥，被保存到1024位长的数据区。
素数p及素数q与上述同样，分别被保存到512位长的数据区。
秘密密钥d是由RSA公开密钥加密方式的密钥生成算法所生成的IC卡300的秘密密钥，被保存到1024位长的数据区。
(2)高速公开密钥运算部304
高速公开密钥运算部304如图3所示，构成包括秘密密钥取得部311、余数运算部312、求逆运算部313及除数运算部314。
秘密密钥取得部311从密钥存储部309读出秘密密钥d、素数p及素数q，并向余数运算部312输出所读出的秘密密钥d及素数p，并且，向除数运算部314输出所读出的素数p及素数q。
余数运算部312从秘密密钥取得部311接受秘密密钥d及素数p，利用所接受的秘密密钥d及素数p，来算出：
d1＝d(mod p-1)，
并向求逆运算部313输出由计算所得到的数d1及素数p，此外还向解密部303输出数d1。
求逆运算部313从余数运算部312接受数d1及素数p，利用所接受的数d1及素数p，由下式来算出公开密钥e′。
e′＝d1-1(mod p-1)
接下来，求逆运算部313向再加密部306及认证部302输出由计算所得到的公开密钥e′。
除数运算部314从秘密密钥取得部311接受素数p及素数q，利用所接受的素数p及素数q，来算出整数n＝p×q，并向认证部302及再加密部306输出由计算所得到的整数n。
(3)认证部302
(基于寄存器装置100的IC卡300的认证)
认证部302经由读卡器200及输入输出部301，从寄存器装置100接受随机数R1，从密钥存储部309读出素数p与素数q及秘密密钥d，从除数运算部314接受整数n，利用所接受的随机数R1，由下式来算出散列值H1。
H1＝Hash(R1)
接下来，认证部302依次运算下式，由此来算出署名数据S1。
a＝p-1(mod q)
y1＝H1(mod p)
y2＝H1(mod q)
d2＝d(mod q-1)
x1＝y1d1(mod p)
x2＝y2d2(mod q)
s1＝{a(x2-x1)(mod q)}p+x1
接下来，向再加密部306输出由计算所得到的署名数据S1，从再加密部306接受s1e′(mod n)。
接下来，判断散列值H1与s1e′(mod n)是否一致，在判断为不一致的场合下，视为发生了某种错误，认证部302向控制部305通知表示发生错误的出错信息。此后，IC卡300停止其动作。
在判断为一致的场合下，认证部302经由输入输出部301及读卡器200，向寄存器装置100输出所生成的署名数据S1。
(基于IC卡300的寄存器装置100的认证)
认证部302生成随机数R2，并经由输入输出部301及读卡器200，向寄存器装置100输出所生成的随机数R2。
接下来，认证部302经由读卡器200及输入输出部301，从寄存器装置100接受署名数据S2，从密钥存储部309读出寄存器装置100的公开密钥PK、素数p及素数q，计算整数n＝p×q，并利用所生成的随机数R2来计算散列值H4。
H4＝Hash(R2)
接下来，认证部302计算S2PK(mod n)，并判断H4与S2PK(mod n)是否一致，如果一致便视为认证成功，如果不一致则视为认证失败。
在认证成功的场合下，认证部302向控制部305通知表示设备认证成功这一意思的信息。并且，在设备认证失败的场合下，向控制部305通知表示设备认证失败这一意思的信息。
在设备认证失败的场合下，此后IC卡300在与寄存器装置100之间不进行信息收发。
(4)再加密部306
再加密部306从求逆运算部313接受公开密钥e′，从除数运算部314接受整数n，并计算下式。
S1e′(mod n)
接下来，再加密部306向认证部302输出所得到的S1e′(mod n)。
(5)控制部305
控制部305接受出错信息、表示设备认证成功这一意思的信息以及表示设备认证失败这一意思的信息。
控制部305从认证部302接受到出错信息后，对构成IC卡300的其它构成要素，指示停止动作。
控制部305从认证部302接受到表示设备认证失败这一意思的信息后，对构成IC卡300的其它构成要素，指示停止动作。另一方面，在接受到表示设备认证成功这一意思的信息后，继续以后的动作。
(6)解密部303
解密部303经由读卡器200及输入输出部301，从寄存器装置100接受加密会话密钥C1。
接下来，解密部303从密钥存储部309接受素数p及素数q，从余数运算部312接受数d1，依次运算下式，由此来算出解密会话密钥x。
A＝p-1(mod q)
y1＝C1(mod p)
y2＝C1(mod q)
d2＝d(mod q-1)
x1＝y1d1(mod p)
x2＝y2d2(mod q)
x＝{a(x2-x1)(mod q)}p+x1
接下来，向解密部308输出由计算所得到的解密会话密钥x。
(7)解密部308
解密部308经由读卡器200及输入输出部301，从寄存器装置100接受加密点数Et，从解密部303接受解密会话密钥x，将所接受的解密会话密钥x用作密钥，对所接受的加密点数Et施行解密算法D1，生成解密点数Dt，并向信息存储部307写入所生成的解密点数Dt。
这里，解密算法D1是基于共通密钥加密方式的DES的算法，对由加密算法E1生成的加密码解密。
(8)输入输出部301
输入输出部301经由读卡器200，在寄存器装置100与构成IC卡300的其它构成要素之间进行信息的收发。
(9)信息存储部307
信息存储部307具有用于存储解密点数Dt的区域。
1.5秘密通信系统10的动作
对秘密通信系统10的动作进行说明。
(1)秘密通信系统10的整体概要动作
利用图4所示的流程图，对秘密通信系统10的整体概要动作进行说明。
IC卡300所具有的高速公开密钥运算部304的余数运算部312算出d1＝d(mod p-1)(步骤S101)，求逆运算部313算出公开密钥e′＝d1-1(modp-1)(步骤S102)。
接下来，寄存器装置100尝试IC卡300的认证(步骤S103)，一旦认证失败(步骤S104)，便结束与IC卡300之间的通信。一旦认证成功(步骤S104)，则继续与IC卡300之间的通信。
接下来IC卡300尝试寄存器装置100的认证(步骤S105)，一旦认证失败(步骤S106)，便结束与寄存器装置100之间的通信。一旦认证成功(步骤S106)，则继续与寄存器装置100之间的通信。
接下来，寄存器装置100对会话密钥加密，生成加密会话密钥，并向IC卡300输出所生成的加密会话密钥，IC卡300对加密会话密钥解密，生成解密会话密钥(步骤S107)，寄存器装置100利用会话密钥，对点数加密，生成加密点数，并发送所生成的加密点数，IC卡300利用解密会话密钥，对加密点数解密(步骤S108)。
(2)基于寄存器装置100的IC卡300的认证动作
利用图5～图6所示的流程图，对基于寄存器装置100的IC卡300的认证动作进行说明。
寄存器装置100的认证部108生成随机数R1(步骤S121)，并经由输入输出部110及读卡器200，向IC卡300输出所生成的随机数R1(步骤S122)。
IC卡300的认证部302经由读卡器200及输入输出部301，从寄存器装置100接受随机数R1(步骤S122)，从密钥存储部309读出素数p及素数q以及秘密密钥d，从除数运算部314接受整数n(步骤S123)，利用所接受的随机数R1来算出散列值H1＝Hash(R1)(步骤S124)。
接下来认证部302算出a＝p-1(mod q)(步骤S125)、
y1＝H1(mod p)(步骤S126)、
y2＝H1(mod q)(步骤S127)、
d2＝d(mod q-1)(步骤S128)、
x1＝y1d1(mod p)(步骤S129)、
x2＝y2d2(mod q)(步骤S130)、
s1＝{a(x2-x1)(mod q)}p+x1(步骤S131)。
再加密部306从求逆运算部313接受公开密钥e′，从除数运算部314接受整数n(步骤S132)，并计算S1e′(mod n)(步骤S133)。
认证部302判断散列值H1与S1e′(mod n)是否一致，在判断为不一致的场合下(步骤S134)，视为发生了某种错误，认证部302向控制部305通知表示发生错误的出错信息。此后，IC卡300停止其动作。
在判断为一致的场合下(步骤S134)，认证部302经由输入输出部301及读卡器200，向寄存器装置100输出所生成的署名数据S1(步骤S141)。
接下来，寄存器装置100的认证部108经由读卡器200及输入输出部110，从IC卡300接受署名数据S1(步骤S141)，从密钥存储部111读出IC卡300的公开密钥e、素数p及素数q(步骤S142)，接下来，对所生成的随机数R1施行散列函数Hash，生成散列值H2＝Hash(R1)(步骤S143)。
接下来，认证部108计算n＝p×q，计算S1e(mod n)(步骤S144)，并对所生成的散列值H2与由计算所得到的值S1e(mod n)进行比较，如果一致(步骤S145)，便视为认证成功，如果不一致(步骤S145)，则视为认证失败。
(3)基于IC卡300的寄存器装置100的认证动作
利用图7所示的流程图，对基于IC卡300的寄存器装置100的认证动作进行说明。
IC卡300的认证部302生成随机数R2(步骤S201)，并经由输入输出部301及读卡器200，向寄存器装置100输出所生成的随机数R2(步骤S202)。
寄存器装置100的认证部108经由读卡器200及输入输出部110，从IC卡300接受随机数R2(步骤S202)，从密钥存储部111读出秘密密钥SK、素数p及素数q(步骤S203)，对所接受的随机数R2施行散列函数Hash，并计算散列值H3＝Hash(R2)(步骤S204)。接下来，认证部108计算n＝p×q，并计算署名数据S2＝(H3)SK(mod n)(步骤S205)，经由输入输出部110及读卡器200，向IC卡300输出由计算所得到的署名数据S2(步骤S206)。
接下来，IC卡300的认证部302经由读卡器200及输入输出部301，从寄存器装置100接受署名数据S2(步骤S206)，从密钥存储部309读出寄存器装置100的公开密钥PK、素数p及素数q(步骤S207)，计算整数n＝p×q，并利用所生成的随机数R2，来计算散列值H4＝Hash(R2)(步骤S208)。接下来，认证部302计算S2PK(mod n)(步骤S209)，判断H4与S2PK(mod n)是否一致，如果一致(步骤S210)，便视为认证成功，如果不一致(步骤S210)，则视为认证失败。
在设备认证失败的场合下，此后IC卡300在与寄存器装置100之间不进行信息收发。
(4)会话密钥的交接动作
利用图8所示的流程图，对会话密钥的交接动作进行说明。
寄存器装置100的加解密部109生成随机数，并将所生成的随机数作为会话密钥M(步骤S251)。接下来从密钥存储部111读出素数p、素数q及公开密钥e，计算整数n＝p×q，并利用会话密钥M、整数n及公开密钥e，算出加密会话密钥C1＝Me(mod n)(步骤S252)。接下来，经由输入输出部110及读卡器200，向IC卡300输出由计算所得到的加密会话密钥C1(步骤S253)。
接下来，IC卡300的解密部303经由读卡器200及输入输出部301，从寄存器装置100接受加密会话密钥C1(步骤S253)，接着从密钥存储部309接受素数p及素数q，从余数运算部312接受数d1，并依次运算下式。
a＝p-1(mod q)(步骤S256)
y1＝C1(mod p)(步骤S257)
y2＝C1(mod q)(步骤S258)
d2＝d(mod q-1)(步骤S259)
x1＝y1d1(mod p)(步骤S260)
x2＝y2d2(mod q)(步骤S261)
x＝{a(x2-x1)(mod q)}p+x1(步骤S262)
接下来，向解密部308输出由计算所得到的解密会话密钥x(步骤S263)。
(5)点数的秘密通信的动作
利用图9所示的流程图，对点数的秘密通信动作进行说明。
寄存器装置100的控制部107由小卖店销售人员的操作，根据利用者所购入商品的购入额，来生成特惠即点数Pt(步骤S291)。接下来，加解密部109将所生成的会话密钥M用作密钥，对点数Pt施行加密算法E1，生成加密点数Et＝E1(会话密钥M、点数Pt)(步骤S292)，接下来，经由输入输出部110及读卡器200，向IC卡300输出加密点数Et(步骤S293)。
IC卡300的解密部308经由读卡器200及输入输出部301，从寄存器装置100接受加密点数Et(步骤S293)，从解密部303接受解密会话密钥x，将所接受的解密会话密钥x用作密钥，对所接受的加密点数Et施行解密算法D1，生成解密点数Dt(步骤S294)，并向信息存储部307写入所生成的解密点数Dt(步骤S295)。
1.6e′成为公开密钥的证明
以下，对在d1＝d(mod p-1)时，e′＝d1-1(mod p-1)成为公开密钥这一事实进行证明。
公开密钥e′由e′＝d-1(mod LCM(p-1，q-1))来定义。这里，LCM(x，y)表示x与y的最小公倍数。
由于LCM(p-1，q-1)可以表现为n×(p-1)，因而成为：
e′×d＝n×(m×(p-1))+1。
这里，如果假设e＜p-1，则成为：
e′×(k×(p-1)+d1)＝n×(m×(p-1))+1
e′×d1＝(n×m-e×k)×(p-1)+1，
从而成为：
e′＝d1-1(mod p-1)。
2.第2实施方式
以下对作为本发明涉及的其它实施方式的RSA秘密通信系统20进行说明。
(1)RSA秘密通信系统20的构成
RSA秘密通信系统20如图10所示，其构成包括RSA加密装置500、RSA解密装置400及存储卡600，RSA加密装置500及RSA解密装置400经由网络50来连接。
在RSA加密方式下的密钥生成中，对于大小相异的2个素数p及素数q，生成成为数n＝p×q，并与p-1同q-1的最小公倍数1cm互素，而且满足p-1＞e的公开密钥e。此外在以最小公倍数1cm为除数的余数体中，生成公开密钥e的逆元，所生成的逆元成为秘密密钥d。如此生成的公开密钥e被预先通知到RSA加密装置500。
RSA加密装置500由RSA加密方式，将公开密钥e用作密钥，对明码M加密，算出加密码C＝Me(mod n)。这里是n＝p×q。
存储卡600是可移动型半导体存储器，预先存储有解密处理所用的秘密密钥d、素数p及素数q。
RSA解密装置400是对由RSA加密装置500生成的加密码C＝Me(mod n)解密的装置，如图10所示，其构成包括由数据输入部401、LSI部420、数据输出部404及数据输入部406。LSI部420是系统LSI，包含数据解密部402、高速公开密钥运算部403及数据再加密部405。并且，高速公开密钥运算部403包含秘密密钥取得部411、余数运算部412、除数运算部413及求逆运算部414。
数据输入部401经由网络50，从RSA加密装置500取得解密对象即加密码C＝Me(mod n)。
数据输入部406从存储卡600取得解密处理用的秘密密钥d、素数p及素数q。
数据解密部402为实现处理高速化，由中国余数定理(ChineseRemainder Theorem，简称CRT)，并利用由数据输入部406取得的秘密密钥d、素数p、素数q以及由高速公开密钥运算部403算出的d1，对加密码C解密，生成解密码D。具体地说，进行以下所示的运算。
a＝p-1(mod q)
y1＝C(mod p)
y2＝C(mod q)
d2＝d(mod q-1)
x1＝y1d1(mod p)
x2＝y2d2(mod q)
D＝{a(x2-x1)(mod q)}p+x1
接下来，数据解密部402向数据输出部404及数据再加密部405输出所生成的解密码D。
高速公开密钥运算部403从数据输入部406取得秘密密钥e、素数p、素数q，运算公开密钥e1。部分中途结果被传送给数据解密部402，用于解密运算。
高速公开密钥运算部403的秘密密钥取得部411从数据输入部406取得秘密密钥d、素数p及素数q。
除数运算部413进行素数p与素数q的相乘，算出整数n。
余数运算部412从秘密密钥d、素数p、素数q算出d1＝d mod(p-1)的值，并保持所算出的d1。
求逆运算部414算出以p-1为除数的余数体上d1的逆e1＝d1-1(modp-1)，接下来将所算出的逆e1作为公开密钥，向数据再加密部405输出。此外向数据解密部402输出d1。
数据再加密部405利用由高速公开密钥运算部403生成的公开密钥e1，对由数据解密部402解密而生成的解密码D进行再加密，生成再加密码C′＝De1(mod n)，并向数据输出部404输出所生成的再加密码C′。
数据输出部404将由数据再加密部405得到的再加密码C′与由数据输入部401得到的加密码C进行比较，在再加密码C′与加密码C一致的场合下，向外部输出由数据解密部402得到的解密码D。在再加密码C′与加密码C不一致的场合下，不输出解密码D。
(2)RSA解密装置400中的RSA解密动作
接下来，利用图11所示的流程图，对RSA解密装置400中的RSA解密动作进行说明。
数据输入部401取得加密码C，数据输入部406取得秘密密钥d、素数p及素数q(步骤S401)。
接下来，高速公开密钥运算部403的秘密密钥取得部411取得秘密密钥d、素数p及素数q，除数运算部413进行素数p与素数q的相乘，算出整数n，余数运算部412从秘密密钥d、素数p、素数q来算出d1＝dmod(p-1)的值，并保持d1，求逆运算部414算出公开密钥e1＝d1-1(modp-1)(步骤S402)。
接下来，数据解密部402利用中国余数定理(CRT)，对加密码C解密，生成解密码D(步骤S403)。
数据再加密部405利用由高速公开密钥运算部403生成的公开密钥e1，对解密码D进行再加密，生成再加密码C′(步骤S404)。
数据输出部404将再加密码C′与加密码C进行比较，在再加密码C′与加密码C一致的场合下(步骤S405)，向外部输出解密码D(步骤S406)。在再加密码C′与加密码C不一致的场合下(步骤S405)，不输出解密码D，而显示或输出表示发生了故障这一意思的消息(步骤S407)。
(3)总结
根据上述第2实施方式，对计算公开密钥e1的值的求逆运算的输入成为传统位长的一半。由于逆元运算所需的存储量与输入位长成比例，处理时间与输入位长的平方成比例，因而存储量及处理时间均可大幅缩减。此外由于成为求逆运算的输入值的d1也可以挪用于采用了中国余数定理的解密运算，因而具有还可削减解密运算的处理时间的效果。
此外在本实施方式中，所表示的是一种在高速公开密钥运算部内设置计算d1的余数运算部，并将该值发送给数据解密部来利用的构成，但也可以在数据解密部内设置余数运算部来计算d1，并将该值发送到高速公开密钥运算部。在该场合下，在图11的流程图中，上部的高速公开密钥生成步骤(步骤S402)与高速解密步骤(步骤S403)的顺序颠倒。
3.第3实施方式
以下对作为第2实施方式的RSA秘密通信系统20的变形例的RSA秘密通信系统30进行说明。
(1)RSA秘密通信系统30的构成
RSA秘密通信系统30具有与RSA秘密通信系统20类似的构成。这里以与RSA秘密通信系统20的相异点为中心进行说明。
RSA秘密通信系统30如图12所示，其构成包括由RSA加密装置500、RSA解密装置400b、CRT信息生成装置700及存储卡600b，RSA加密装置500及RSA解密装置400经由网络50来连接。
存储卡600b是与存储卡600同样的可移动型半导体存储器，预先存储有解密处理用的秘密密钥d、素数p及素数q。
CRT信息生成装置700从存储卡600b读出秘密密钥d、素数p及素数q，利用所读出的秘密密钥d、素数p及素数q，来算出：
d1＝d mod(p-1)以及
d2＝d mod(q-1)，并向存储卡600b写入由计算所得到的d1及d2。
RSA解密装置400b是具有与RSA解密装置400同样的构成，并对由RSA加密装置500生成的加密码C＝Me(mod n)进行解密的装置，如图12所示，其构成包括数据输入部401、LSI部420b、数据输出部404及数据输入部406b。LSI部420b是具有与LSI部420同样构成的系统LSI，包含数据解密部402、高速公开密钥运算部403b以及数据再加密部405。此外高速公开密钥运算部403b包含秘密密钥取得部411b、除数运算部413及求逆运算部414。
数据输入部406b从存储卡600b取得解密处理用的秘密密钥d、素数p、素数q、d1及d2。
数据解密部402b利用由数据输入部406b取得的秘密密钥d、素数p、素数q、d1及d2，对加密码C解密，生成解密码D。具体地说，进行以下所示的运算。
a＝p-1(mod q)
y1＝C(mod p)
y2＝C(mod q)
x1＝y1d1(mod p)
x2＝y2d2(mod q)
D＝{a(x2-x1)(mod q)}p+x1
接下来，数据解密部402b向数据输出部404及数据再加密部405输出所生成的解密码D。
这里，数据解密部402b不进行d2＝d(mod q-1)的运算，而从存储卡600b取得d2，这一点与数据解密部402不同。
高速公开密钥运算部403b从数据输入部406取得秘密密钥e、素数p、素数q、d1，运算公开密钥e1。部分中途结果被传送给数据解密部402，用于解密运算。
高速公开密钥运算部403b的秘密密钥取得部411b从数据输入部406b取得素数p、素数q、d1。
除数运算部413进行素数p与素数q的相乘，算出整数n。
求逆运算部414算出以p-1为除数的余数体上d1的逆e1＝d1-1(modp-1)，接下来将所算出的逆e1作为公开密钥，向数据再加密部405输出。
(2)RSA秘密通信系统30的动作
利用图13所示的流程图，对RSA秘密通信系统30的动作进行说明。
CRT信息生成装置700从存储卡600b读出秘密密钥d、素数p及素数q(步骤S431)，利用所读出的秘密密钥d、素数p及素数q，算出d1＝dmod(p-1)及d2＝d mod(q-1)(步骤S432)，并向存储卡600b写入由计算所得到的d1及d2(步骤S433)。
RSA解密装置400b的数据输入部406b从存储卡600b取得解密处理用的秘密密钥d、素数p、素数q、d1及d2(步骤S434)。
数据输入部401经由网络50，从RSA加密装置500取得加密码C(步骤S435)。
数据解密部402b利用由数据输入部406b取得的秘密密钥d、素数p、素数q、d1及d2，由中国余数定理，对加密码C解密，生成解密码D(步骤S436)。
接下来，求逆运算部414算出逆e1＝d1-1(mod p-1)(步骤S437)，数据再加密部405利用公开密钥e1，对解密码D再次加密，生成再加密码C′(步骤S438)。
接下来，
数据输出部404将再加密码C′与加密码C进行比较，在再加密码C′与加密码C一致的场合下(步骤S439)，向外部输出解密码D(步骤S440)。在再加密码C′与加密码C不一致的场合下(步骤S439)，不输出解密码D，而显示或输出表示发生了故障的消息(步骤S441)。
(3)总结
如上所述，在第3实施方式中，RSA解密装置从外部取得的不是传统的秘密密钥，而是预先计算出的中国余数定理(CRT)运算用的秘密密钥。即取得d1＝d mod(p-1)、d2＝d mod(q-1)、p、q的值。此外根据中国余数定理的利用方法，在从外部取得的数据中也可以至少包含d1。
数据解密部402及高速公开密钥运算部403b利用由数据输入部406b取得的值，来进行各自的处理。因此如第2实施方式所示，不必在数据解密部402与高速公开密钥运算部403之间收发值d1。
由于值d1从外部来取得，因而在高速公开密钥运算部403b中，不必设置第2实施方式所示的余数运算部412。
此外第3实施方式中，从外部取得d1＝d mod(p-1)、d2＝d mod(q-1)、p、q，但根据中国余数定理的利用方法，在从外部取得的数据中也可以至少包含d1。
并且，在图13所示的流程图中，在高速解密步骤(步骤S436)之后，实施高速公开密钥取得步骤(步骤S437)，但先实施高速解密步骤与高速公开密钥取得步骤的任意一方都是可以的。即也可以在高速公开密钥取得步骤(步骤S437)之后，实施高速解密步骤(步骤S436)。
根据第3实施方式，除了实施方式2的效果之外，无需用于求算d2的余数运算，因而具有可进一步削减处理时间的优异效果。
另外，在上述说明中，以RSA解密装置中的示例来作说明，但对于RSA署名生成装置，也可同样实施。
此外不限于RSA解密装置及RSA署名生成装置，对于从RSA秘密密钥来取得RSA公开密钥的场合也可同样实施。
4.总结
本发明是一种RSA公开密钥复原装置，其在利用素数p与q、与p-1同q-1的最小公倍数1cm互素并满足p-1＞e的数e、以1cm为除数的余数体中e的逆元即d以及p与q之积n，将(e，n)用作公开密钥，将(d，p，q)用作秘密密钥的RSA密码中，从上述秘密密钥(d，p，q)来使上述公开密钥(e，n)复原，具有
第一秘密密钥输入单元，其输入RSA密码的秘密密钥(d，p，q)；
第一余数单元，其利用由上述第一秘密密钥输入单元输入的秘密密钥d与p，来求出以p-1为除数的d的余数即dp＝d mod(p-1)；
第一逆元运算单元，其利用由上述第一余数单元得到的dp及由上述第一秘密密钥输入单元输入的p，来求出以p-1为除数的余数体中dp的逆元；
公开密钥输出单元，其将由上述第一秘密密钥输入单元输入的秘密密钥p与q之积设为n，将由上述第一逆元运算单元得到的逆元设为e，将(e，n)作为RSA公开密钥来输出。
并且，本发明是一种RSA解密装置，其在利用素数p与q、与p-1同q-1的最小公倍数1cm互素并满足p-1＞e的数e、以1cm为除数的余数体中e的逆元即d以及p与q之积n，将(e，n)用作公开密钥，将(d，p，q)用作秘密密钥的RSA密码中，从由上述公开密钥加密的加密码，来对原明码解密，具有
输入加密码C的加密码输入单元；
第二秘密密钥输入单元，其输入RSA密码的秘密密钥(d，p，q)；
解密单元，其利用由上述第二秘密密钥输入单元输入的秘密密钥，从由上述加密码输入单元输入的加密码C来对明码P解密；
第二余数单元，其利用由上述第二秘密密钥输入单元输入的秘密密钥d与p，来求出以p-1为除数的d的余数即dp＝d mod(p-1)；
第二逆元运算单元，其利用由上述第二余数单元得到的dp及由上述第二秘密密钥输入单元输入的p，来求出以p-1为除数的余数体中dp的逆元；
第一公开密钥复原单元，其将由上述第二秘密密钥输入单元输入的秘密密钥p与q之积设为n，将由上述第二逆元运算单元得到的逆元设为e，将(e，n)作为RSA公开密钥来保持；
加密单元，其利用由上述第一公开密钥复原单元保持的公开密钥，从由上述解密单元求出的明码P来求出加密码C′；
第一验算单元，其将由上述加密单元求出的加密码C′与由上述加密码输入单元输入的加密码C进行比较；
解密结果输出单元，其只在上述第一验算单元的比较结果一致时，才输出明码P。
这里，也可以取代上述解密单元，而配备CRT解密单元，其利用由上述第二秘密密钥输入单元输入的秘密密钥以及由上述第二余数单元得到的dp，通过采用了中国余数定理(CRT)的算法，从由上述加密码输入单元输入的加密码C来对明码P解密。
这里，也可以取代上述第二秘密密钥输入单元及上述第二余数单元，而具备第三秘密密钥输入单元，其预先将至少包含dp而且利用了中国余数定理的算法所必需的值作为RSA密码的秘密密钥来输入，
上述第二逆元运算单元、上述第一公开密钥复原单元、上述CRT解码单元也可以采用由上述第三秘密密钥输入单元输入的值。
这里，也可以还具备第一出错输出单元，其当上述第一验算单元的比较结果不一致时，输出发生故障这一大意。
并且，本发明是一种RSA署名生成装置，其在利用素数p与q、与p-1同q-1的最小公倍数1cm互素并满足p-1＞e的数e、以1cm为除数的余数体中e的逆元即d以及p与q之积n，将(e，n)用作公开密钥，将(d，p，q)用作秘密密钥的RSA密码中，从明码来生成署名码，具有
输入明码P的明码输入单元；
第四秘密密钥输入单元，其输入RSA密码的秘密密钥(d，p，q)；
署名生成单元，其利用由上述第四秘密密钥输入单元输入的秘密密钥，从由上述明码输入单元输入的明码P来生成署名码S；
第三余数单元，其利用由上述第四秘密密钥输入单元输入的秘密密钥d与p，来求出以p-1为除数的d的余数即dp＝d mod(p-1)；
第三逆元运算单元，其利用由上述第三余数单元得到的dp及由上述第四秘密密钥输入单元输入的p，来求出以p-1为除数的余数体中dp的逆元；
第二公开密钥复原单元，其将由上述第四秘密密钥输入单元输入的秘密密钥p与q之积设为n，将由上述第三逆元运算单元得到的逆元设为e，将(e，n)作为RSA公开密钥来保持；
明码恢复单元，其利用由上述第二公开密钥复原单元保持的公开密钥，从由上述署名生成单元求出的署名码S来求出明码P′；
第二验算单元，其将由上述明码恢复单元求出的明码P′与由上述明码输入单元输入的明码P进行比较；
署名结果输出单元，其只在上述第二验算单元的比较结果一致时，才输出署名码S。
这里，也可以取代上述署名生成单元，而配备CRT署名生成单元，其利用由上述第四秘密密钥输入单元输入的秘密密钥以及由上述第三余数单元得到的dp，通过采用了中国余数定理(CRT)的算法，从由上述明码输入单元输入的明码P来生成署名码S。
这里，也可以取代上述第四秘密密钥输入单元及上述第三余数单元，而具备第五秘密密钥输入单元，其预先将至少包含dp而且利用了中国余数定理的算法所必需的值作为RSA密码的秘密密钥来输入，
上述第三逆元运算单元、上述第二公开密钥复原单元、上述CRT署名生成单元也可以采用由上述第五秘密密钥输入单元输入的值。
这里，也可以还具备第二出错输出单元，其当上述第二验算单元的比较结果不一致时，输出发生故障这一大意。
并且，本发明是一种RSA公开密钥复原方法，其在利用素数p与q、与p-1同q-1的最小公倍数1cm互素并满足p-1＞e的数e、以1cm为除数的余数体中e的逆元即d以及p与q之积n，将(e，n)用作公开密钥，将(d，p，q)用作秘密密钥的RSA密码中，从上述秘密密钥(d，p，q)来使上述公开密钥(e，n)复原，包括
第一秘密密钥输入步骤，其输入RSA密码的秘密密钥(d，p，q)；
第一余数步骤，其利用由上述第一秘密密钥输入步骤输入的秘密密钥d与p，来求出以p-1为除数的d的余数即dp＝d mod(p-1)；
第一逆元运算步骤，其利用由上述第一余数步骤得到的dp及由上述第一秘密密钥输入步骤输入的p，来求出以p-1为除数的余体中dp的逆元；
公开密钥输出步骤，其将由上述第一秘密密钥输入步骤输入的秘密密钥p与q之积设为n，将由上述第一逆元运算步骤得到的逆元设为e，将(e，n)作为RSA公开密钥来输出。
本发明是一种RSA解密方法，其在利用素数p与q、与p-1同q-1的最小公倍数1cm互素并满足p-1＞e的数e、以1cm为除数的余数体中e的逆元即d以及p与q之积n，将(e，n)用作公开密钥，将(d，p，q)用作秘密密钥的RSA密码中，从由上述公开密钥加密的加密码，来对原明码解密，包括
输入加密码C的加密码输入步骤；
第二秘密密钥输入步骤，其输入RSA密码的秘密密钥(d，p，q)；
解密步骤，其利用由上述第二秘密密钥输入步骤输入的秘密密钥，从由上述加密码输入步骤输入的加密码C来对明码P解密；
第二余数步骤，其利用由上述第二秘密密钥输入步骤输入的秘密密钥d与p，来求出以p-1为除数的d的余数即dp＝d mod(p-1)；
第二逆元运算步骤，其利用由上述第二余数步骤得到的dp及由上述第二秘密密钥输入步骤输入的p，来求出以p-1为除数的余数体中dp的逆元；
第一公开密钥复原步骤，其将由上述第二秘密密钥输入步骤输入的秘密密钥p与q之积设为n，将由上述第二逆元运算步骤得到的逆元设为e，将(e，n)作为RSA公开密钥来保持；
加密步骤，其利用由上述第一公开密钥复原步骤保持的公开密钥，从由上述解密步骤求出的明码P来求出加密码C′；
第一验算步骤，其将由上述加密步骤求出的加密码C′与由上述加密码输入步骤输入的加密码C进行比较；
解密结果输出步骤，其只在上述第一验算步骤的比较结果一致时，才输出明码P。
这里，也可以取代上述解密步骤，而包括CRT解密步骤，其利用由上述第二秘密密钥输入步骤输入的秘密密钥以及由上述第二余数步骤得到的dp，通过采用了中国余数定理(CRT)的算法，从由上述加密码输入步骤输入的加密码C来对明码P解密。
这里，也可以取代上述第二秘密密钥输入步骤及上述第二余数步骤，而包括第三秘密密钥输入步骤，其预先将至少包含dp而且利用了中国余数定理的算法所必需的值作为RSA密码的秘密密钥来输入，
上述第二逆元运算步骤、上述第一公开密钥复原步骤、上述CRT解密步骤也可以采用由上述第三秘密密钥输入步骤输入的值。
这里，也可以还具备第一出错输出步骤，其当上述第一验算步骤的比较结果不一致时，输出发生故障这一大意。
并且，本发明是一种RSA署名生成方法，其在利用素数p与q、与p-1同q-1的最小公倍数1cm互素并满足p-1＞e的数e、以1cm为除数的余数体中e的逆元即d以及p与q之积n，将(e，n)用作公开密钥，将(d，p，q)用作秘密密钥的RSA密码中，从明码来生成署名码，包括
输入明码P的明码输入步骤；
第四秘密密钥输入步骤，其输入RSA密码的秘密密钥(d，p，q)；
署名生成步骤，其利用由上述第四秘密密钥输入步骤输入的秘密密钥，从由上述明码输入步骤输入的明码P来生成署名码S；
第三余数步骤，其利用由上述第四秘密密钥输入步骤输入的秘密密钥d与p，来求出以p-1为除数的d的余数即dp＝d mod(p-1)；
第三逆元运算步骤，其利用由上述第三余数步骤得到的dp及由上述第四秘密密钥输入步骤输入的p，来求出以p-1为除数的余数体中dp的逆元；
第二公开密钥复原步骤，其将由上述第四秘密密钥输入步骤输入的秘密密钥p与q之积设为n，将由上述第三逆元运算步骤得到的逆元设为e，将(e，n)作为RSA公开密钥来保持；
明码恢复步骤，其利用由上述第二公开密钥复原步骤保持的公开密钥，从由上述署名生成步骤求出的署名码S来求出明码P′；
第二验算步骤，其将由上述明码恢复步骤求出的明码P′与由上述明码输入步骤输入的明码P进行比较；
署名结果输出步骤，其只在上述第二验算步骤的比较结果一致时，才输出署名码S。
这里，也可以取代上述署名生成步骤，而包括CRT署名生成步骤，其利用由上述第四秘密密钥输入步骤输入的秘密密钥以及由上述第三余数步骤得到的dp，通过采用了中国余数定理(CRT)的算法，从由上述明码输入步骤输入的明码P来生成署名码S。
这里，也可以取代上述第四秘密密钥输入步骤及上述第三余数步骤，而包括第五秘密密钥输入步骤，其预先将至少包含dp而且利用了中国余数定理的算法所必需的值作为RSA密码的秘密密钥来输入，
上述第三逆元运算步骤、上述第二公开密钥复原步骤、上述CRT署名生成步骤也可以采用由上述第五秘密密钥输入步骤输入的值。
这里，也可以还包括第二出错输出步骤，其当上述第二验算步骤的比较结果不一致时，输出发生故障这一大意。
并且，本发明是一种RSA公开密钥复原程序，其在利用素数p与q、与p-1同q-1的最小公倍数1cm互素并满足p-1＞e的数e、以1cm为除数的余数体中e的逆元即d以及p与q之积n，将(e，n)用作公开密钥，将(d，p，q)用作秘密密钥的RSA密码中，从上述秘密密钥(d，p，q)来使上述公开密钥(e，n)复原，包括
第一秘密密钥输入步骤，其输入RSA密码的秘密密钥(d，p，q)；
第一余数步骤，其利用由上述第一秘密密钥输入步骤输入的秘密密钥d与p，来求出以p-1为除数的d的余数即dp＝d mod(p-1)；
第一逆元运算步骤，其利用由上述第一余数步骤得到的dp及由上述第一秘密密钥输入步骤输入的p，来求出以p-1为除数的余数体中dp的逆元；
公开密钥输出步骤，其将由上述第一秘密密钥输入步骤输入的秘密密钥p与q之积设为n，将由上述第一逆元运算步骤得到的逆元设为e，将(e，n)作为RSA公开密钥来输出。
本发明是一种RSA解密程序，其在利用素数p及q、与p-1同q-1的最小公倍数1cm互素并满足p-1＞e的数e、以1cm为除数的余数体中e的逆元即d以及p与q之积n，将(e，n)用作公开密钥，将(d，p，q)用作秘密密钥的RSA密码中，从由上述公开密钥加密的加密码，来对原明码解密，包括
输入加密码C的加密码输入步骤；
第二秘密密钥输入步骤，其输入RSA密码的秘密密钥(d，p，q)；
解密步骤，其利用由上述第二秘密密钥输入步骤输入的秘密密钥，从由上述加密码输入步骤输入的加密码C来对明码P解密；
第二余数步骤，其利用由上述第二秘密密钥输入步骤输入的秘密密钥d与p，来求出以p-1为除数的d的余数即dp＝d mod(p-1)；
第二逆元运算步骤，其利用由上述第二余数步骤得到的dp及由上述第二秘密密钥输入步骤输入的p，来求出以p-1为除数的余数体中dp的逆元；
第一公开密钥复原步骤，其将由上述第二秘密密钥输入步骤输入的秘密密钥p与q之积设为n，将由上述第二逆元运算步骤得到的逆元设为e，将(e，n)作为RSA公开密钥来保持；
加密步骤，其利用由上述第一公开密钥复原步骤保持的公开密钥，从由上述解密步骤求出的明码P来求出加密码C′；
第一验算步骤，其将由上述加密步骤求出的加密码C′与由上述加密码输入步骤输入的加密码C进行比较；
解密结果输出步骤，其只在上述第一验算步骤的比较结果一致时，才输出明码P。
并且，也可以取代上述解密步骤，而包括CRT解密步骤，其利用由上述第二秘密密钥输入步骤输入的秘密密钥以及由上述第二余数步骤得到的dp，通过采用了中国余数定理(CRT)的算法，从由上述加密码输入步骤输入的加密码C来对明码P解密。
并且，也可以取代上述第二秘密密钥输入步骤及上述第二余数步骤，而包括第三秘密密钥输入步骤，其预先将至少包含dp而且利用了中国余数定理的算法所必需的值作为RSA密码的秘密密钥来输入，
上述第二逆元运算步骤、上述第一公开密钥复原步骤、上述CRT解码步骤也可以采用由上述第三秘密密钥输入步骤输入的值。
并且，也可以还具备第一出错输出步骤，其当上述第一验算步骤的比较结果不一致时，输出发生故障这一大意。
本发明是一种RSA署名生成程序，其在利用素数p与q、与p-1同q-1的最小公倍数1cm互素并满足p-1＞e的数e、以1cm为除数的余数体中e的逆元即d以及p与q之积n，将(e，n)用作公开密钥，将(d，p，q)用作秘密密钥的RSA密码中，从明码来生成署名码，包括
输入明码P的明码输入步骤；
第四秘密密钥输入步骤，其输入RSA密码的秘密密钥(d，p，q)；
署名生成步骤，其利用由上述第四秘密密钥输入步骤输入的秘密密钥，从由上述明码输入步骤输入的明码P来生成署名码S；
第三余数步骤，其利用由上述第四秘密密钥输入步骤输入的秘密密钥d与p，来求出以p-1为除数的d的余数即dp＝d mod(p-1)；
第三逆元运算步骤，其利用由上述第三余数步骤得到的dp及由上述第四秘密密钥输入步骤输入的p，来求出以p-1为除数的余数体中dp的逆元；
第二公开密钥复原步骤，其将由上述第四秘密密钥输入步骤输入的秘密密钥p与q之积设为n，将由上述第三逆元运算步骤得到的逆元设为e，将(e，n)作为RSA公开密钥来保持；
明码恢复步骤，其利用由上述第二公开密钥复原步骤保持的公开密钥，从由上述署名生成步骤求出的署名码S来求出明码P′；
第二验算步骤，其将由上述明码恢复步骤求出的明码P′与由上述明码输入步骤输入的明码P进行比较；
署名结果输出步骤，其只在上述第二验算步骤的比较结果一致时，才输出署名码S。
这里，也可以取代上述署名生成步骤，而包括CRT署名生成步骤，其利用由上述第四秘密密钥输入步骤输入的秘密密钥以及由上述第三余数步骤得到的dp，通过采用了中国余数定理(CRT)的算法，从由上述明码输入步骤输入的明码P来生成署名码S。
这里，也可以取代上述第四秘密密钥输入步骤及上述第三余数步骤，而包括第五秘密密钥输入步骤，其预先将至少包含dp而且利用了中国余数定理的算法所必需的值作为RSA密码的秘密密钥来输入，
上述第三逆元运算步骤、上述第二公开密钥复原步骤、上述CRT署名生成步骤也可以采用由上述第五秘密密钥输入步骤输入的值。
这里，也可以还具备第二出错输出步骤，其当上述第二验算步骤的比较结果不一致时，输出发生故障这一大意。
如上所述，本发明涉及的RSA密码处理装置具有使故障利用攻击不能得逞，并高速进行RSA解密处理等的性质，作为有可能受到IC卡等故障利用攻击，同时还必须进行RSA加密处理的装置等非常有用。
根据本发明的RSA公开密钥复原装置，为求出公开密钥而取用逆元的被运算值成为秘密密钥大约一半的位数的值。因此可大幅削减逆元运算所必需的存储量以及处理时间。
并且，根据本发明的RSA密码处理装置，为求出公开密钥而取用逆元的被运算值成为秘密密钥大约一半的位数的值。因此与传统相比，可大幅削减逆元运算所需的时间，其结果是，可缩短使故障利用攻击不能得逞的RSA解密处理等所需的时间。
此外，根据本发明的RSA密码处理装置，为求出公开密钥而取用逆元的被运算值，可按原样用于采用了中国余数定理算法的RSA解密处理。因而可缩短使故障利用攻击不能得逞的RSA解密处理等所需的时间。
此外，根据本发明的RSA公开密钥复原装置及RSA密码处理装置，公开密钥的值对于素数p被限制到p-1以下，但一般不会发生RSA密码的公开密钥取得较小的问题。
5.其它变形例
另外，基于上述实施方式对本发明作了说明，但毋庸赘言，本发明并非限定于上述实施方式。本发明也包含以下场合。
(1)在第1实施方式中，IC卡300包含系统LSI320，但并非限定于此。比如高速公开密钥运算部304也可以构成1个大规模集成电路。
并且，在第2实施方式中，RSA解密装置400包含LSI部420，但并非限定于此。比如高速公开密钥运算部403也可以构成1个大规模集成电路。
并且，在第3实施方式中，RSA解密装置400b包含LSI部420b，但并非限定于此。比如高速公开密钥运算部403b也可以构成1个大规模集成电路。
(2)具体地说，上述各装置是构成包括微处理器、ROM、RAM等的计算机系统。上述RAM中存储有计算机程序。上述微处理器按照上述计算机程序来动作，各装置由此来实现其功能。
(3)本发明可以是上述所示的方法。并且，也可以是由计算机实现这些方法的计算机程序，还可以是由上述计算机程序所组成的数字信号。
并且，本发明也可以将上述计算机程序或上述数字信号记录到计算机可读取的记录媒体，比如软盘、硬盘、CD-ROM、MO、DVD、DVD-ROM、DVD-RAM、BD(Blu-ray Disc，蓝光盘)、半导体存储器等。此外也可以是这些记录媒体中记录的上述计算机程序或上述数字信号。
并且，本发明也可以是经由电气通信线路、无线或有线通信线路、以因特网为代表的网络、数据广播等，来传送上述计算机程序或上述数字信号。
此外，本发明也可以是具有微处理器及存储器的计算机系统，上述存储器存储有上述计算机程序，上述微处理器按照上述计算机程序来动作。
并且，也可以通过将上述程序或上述数字信号记录移送到上述记录媒体，或者通过经由上述网络等来移送上述程序或上述数字信号，由此由其它独立的计算机系统来实施。
(4)也可以分别组合上述实施方式及上述变形例。
尽管参照示例及附图对本发明进行了详尽说明，但应注意的是，对本领域的普通技术人员而言，可以做各种变动及修改是显而易见的。因而除非这些变动及修改脱离本发明的范围，否则它们应构成本发明的一部分。
产业上的可利用性
构成本发明的各装置，可以经营性持续反复地用于有必要秘密地处理信息的所有产业、或者有必要认证对方的所有产业。此外在电气设备制造产业中，对构成本发明的各装置可以经营性地持续反复地制造及销售。