(57)【要約】  【課題】  ＩＣカード等に使用される故障利用攻撃を成立させないＲＳＡ復号装置を提供する。  【解決手段】  このＲＳＡ復号装置は、外部から公開鍵を取得することなく、またデータ検証に用いる公開鍵の演算を高速に行う。ＲＳＡ復号装置は、ｄp ＝ｄ  ｍｏｄ  （ｐ−１）を計算する剰余演算部４１２、及びｐ−１を法とした剰余体におけるｄp の逆元を求める逆数演算部４１４を備え、ｄp の逆元を公開鍵として復号文の検証を行う。公開鍵をｄの逆元として求めるのに比べ逆元演算のビット数が減少する分、高速な演算が可能となる。 【選択図】  図１０
2005165290.tif 000002
【特許請求の範囲】
【請求項１】
ＲＳＡ暗号方式の秘密鍵ｄから新たに公開鍵ｅ’を生成するＲＳＡ公開鍵生成装置であって、
素数ｑは、素数ｐと異なり、公開鍵ｅは、ｐ−１とｑ−１との最小公倍数ｌｃｍと互いに素で、ｐ−１＞ｅを満たし、前記秘密鍵ｄは、ｌｃｍを法とする剰余体において公開鍵ｅの逆元であり、
前記ＲＳＡ公開鍵生成装置は、
ＲＳＡ暗号の秘密鍵ｄ及び素数ｐを取得する取得手段と、
取得された秘密鍵ｄと素数ｐを用い、素数ｐ−１を法とする前記秘密鍵ｄの剰余ｄp を算出する剰余演算手段と、
算出された前記剰余ｄp 及び取得された前記素数ｐを用い、素数ｐ−１を法とする剰余体における前記剰余ｄp の逆元を算出し、算出した逆元を新たな公開鍵ｅ' とする逆元演算手段と
を備えることを特徴とするＲＳＡ公開鍵生成装置。
【請求項２】
前記剰余演算手段は、ｄp ＝ｄ  （ｍｏｄ  ｐ−１）により、前記剰余ｄp を算出し、
前記逆元演算手段は、ｅ' ＝ｄp -1  （ｍｏｄ  ｐ−１）により、前記公開鍵ｅ' を算出する
ことを特徴とする請求項１に記載のＲＳＡ公開鍵生成装置。
【請求項３】
前記剰余演算手段及び前記逆元演算手段は、１個の集積回路から構成されている
ことを特徴とする請求項１に記載のＲＳＡ公開鍵生成装置。
【請求項４】
ＲＳＡ暗号方式の秘密鍵ｄから新たに公開鍵ｅ’を生成するＲＳＡ公開鍵生成装置を構成する集積回路であって、
素数ｑは、素数ｐと異なり、公開鍵ｅは、ｐ−１とｑ−１との最小公倍数ｌｃｍと互いに素で、ｐ−１＞ｅを満たし、前記秘密鍵ｄは、ｌｃｍを法とする剰余体において公開鍵ｅの逆元であり、
ＲＳＡ公開鍵生成装置は、ＲＳＡ暗号の秘密鍵ｄ及び素数ｐを取得する取得手段を含み、
前記集積回路は、
取得された秘密鍵ｄと素数ｐを用い、素数ｐ−１を法とする前記秘密鍵ｄの剰余ｄp を算出する剰余演算手段と、
算出された前記剰余ｄp 及び取得された前記素数ｐを用い、素数ｐ−１を法とする剰余体における前記剰余ｄp の逆元を算出し、算出した逆元を新たな公開鍵ｅ' とする逆元演算手段と
を備えることを特徴とする集積回路。
【請求項５】
ＲＳＡ暗号方式により生成された暗号文を復号するＲＳＡ復号装置であって、
請求項１のＲＳＡ公開鍵生成装置から、公開鍵ｅ' を取得する公開鍵取得手段と、
前記公開鍵ｅを用いて、ＲＳＡ暗号方式により平文ＭがＲＳＡ暗号化されて生成された暗号文Ｃを取得する暗号文取得手段と、
秘密鍵ｄを用いて、取得した前記暗号文ＣをＲＳＡ復号して復号文Ｄを生成するＲＳＡ復号手段と、
取得した公開鍵ｅ' を用いて、生成された復号文ＤをＲＳＡ暗号化して再暗号文Ｃ’を生成する再暗号化手段と、
取得した暗号文Ｃと生成した再暗号文Ｃ’とを比較し、一致するか否かを判断する比較手段と、
一致すると判断される場合に、生成された前記復号文Ｄを出力する出力手段と
を備えることを特徴とするＲＳＡ復号装置。
【請求項６】
前記ＲＳＡ復号手段は、請求項１のＲＳＡ公開鍵生成装置から、剰余ｄp を取得し、取得した剰余ｄp を用いて、中国剰余定理により、取得した前記暗号文ＣをＲＳＡ復号して復号文Ｄを生成する
ことを特徴とする請求項５に記載のＲＳＡ復号装置。
【請求項７】
前記ＲＳＡ復号手段は、
ａ＝ｐ-1    （ｍｏｄ  ｑ）
ｙ1 ＝Ｃ    （ｍｏｄ  ｐ）
ｙ2 ＝Ｃ    （ｍｏｄ  ｑ）
ｄ2 ＝ｄ    （ｍｏｄ  ｑ−１）
ｘ1 ＝ｙ1dp （ｍｏｄ  ｐ）
ｘ2 ＝ｙ2d2 （ｍｏｄ  ｑ）  
Ｄ＝｛ａ（ｘ2 −ｘ1 ）（ｍｏｄ  ｑ）｝ｐ  ＋  ｘ1
の演算により、復号文Ｄを生成する
ことを特徴とする請求項６に記載のＲＳＡ復号装置。
【請求項８】
前記出力手段は、一致しないと判断される場合に、故障発生の旨を示すメッセージを出力する
ことを特徴とする請求項５に記載のＲＳＡ復号装置。
【請求項９】
前記ＲＳＡ復号手段、前記再暗号化手段及び前記比較手段は、１個の集積回路から構成されている
ことを特徴とする請求項５に記載のＲＳＡ復号装置。
【請求項１０】
ＲＳＡ暗号方式により生成された暗号文を復号するＲＳＡ復号装置を構成する集積回路であって、
前記ＲＳＡ復号装置は、
請求項１のＲＳＡ公開鍵生成装置から、公開鍵ｅ' を取得する公開鍵取得手段と、
前記公開鍵ｅを用いて、ＲＳＡ暗号方式により平文ＭがＲＳＡ暗号化されて生成された暗号文Ｃを取得する暗号文取得手段と、
比較手段により、一致すると判断される場合に、生成された前記復号文Ｄを出力する出力手段とを含み、
前記集積回路は、
秘密鍵ｄを用いて、取得した前記暗号文ＣをＲＳＡ復号して復号文Ｄを生成するＲＳＡ復号手段と、
取得した公開鍵ｅ' を用いて、生成された復号文ＤをＲＳＡ暗号化して再暗号文Ｃ’を生成する再暗号化手段と、
取得した暗号文Ｃと生成した再暗号文Ｃ’とを比較し、一致するか否かを判断する比較手段と
を備えることを特徴とする集積回路。
【請求項１１】
ＲＳＡ暗号方式により生成された暗号文を復号するＲＳＡ復号装置であって、
素数ｑは、素数ｐと異なり、公開鍵ｅは、ｐ−１とｑ−１との最小公倍数ｌｃｍと互いに素で、ｐ−１＞ｅを満たし、前記秘密鍵ｄは、ｌｃｍを法とする剰余体において公開鍵ｅの逆元であり、
前記ＲＳＡ復号装置は、
ＲＳＡ暗号の秘密鍵ｄ及び素数ｐを取得する取得手段と、
取得された秘密鍵ｄと素数ｐを用い、素数ｐ−１を法とする前記秘密鍵ｄの剰余ｄp を算出する剰余演算手段と、
算出された前記剰余ｄp 及び取得された前記素数ｐを用い、素数ｐ−１を法とする剰余体における前記剰余ｄp の逆元を算出し、算出した逆元を新たな公開鍵ｅ' とする逆元演算手段と、
暗号文Ｃを取得する、暗号文Ｃは、前記公開鍵ｅを用いて、ＲＳＡ暗号方式により平文ＭがＲＳＡ暗号化されて生成されたものである暗号文取得手段と、
秘密鍵ｄを用いて、取得した前記暗号文ＣをＲＳＡ復号して復号文Ｄを生成するＲＳＡ復号手段と、
取得した公開鍵ｅ' を用いて、生成された復号文ＤをＲＳＡ暗号化して再暗号文Ｃ’を生成する再暗号化手段と、
取得した暗号文Ｃと生成した再暗号文Ｃ’とを比較し、一致するか否かを判断する比較手段と、
一致すると判断される場合に、生成された前記復号文Ｄを出力する出力手段
を備えることを特徴とするＲＳＡ復号装置。
【請求項１２】
ＲＳＡ署名方式により平文に署名を施して署名文を生成するＲＳＡ署名装置であって、
請求項１のＲＳＡ公開鍵生成装置から、公開鍵ｅ' を取得する公開鍵取得手段と、
秘密鍵ｄを用いて、平文ＭにＲＳＡ署名を施して署名文Ｓを生成する署名生成手段と、
取得した公開鍵ｅ’を用いて、署名文Ｓに、ＲＳＡ署名回復を施して、復号文Ｄを生成する回復手段と、
平文Ｍと、生成した復号文Ｄとを比較し、一致するか否かを判断する比較手段と、
一致すると判断される場合に、生成された前記署名文Ｓを出力する出力手段と
を備えることを特徴とするＲＳＡ署名装置。
【請求項１３】
前記署名生成手段は、請求項１のＲＳＡ公開鍵生成装置から、剰余ｄp を取得し、取得した剰余ｄp を用いて、中国剰余定理により、前記平文ＭにＲＳＡ署名を施して署名文Ｓを生成する
ことを特徴とする請求項１２に記載のＲＳＡ署名装置。
【請求項１４】
前記署名生成手段は、
ａ＝ｐ-1    （ｍｏｄ  ｑ）
ｙ1 ＝Ｍ    （ｍｏｄ  ｐ）
ｙ2 ＝Ｍ    （ｍｏｄ  ｑ）
ｄ2 ＝ｄ    （ｍｏｄ  ｑ−１）
ｘ1 ＝ｙ1dp （ｍｏｄ  ｐ）
ｘ2 ＝ｙ2d2 （ｍｏｄ  ｑ）  
Ｓ＝｛ａ（ｘ2 −ｘ1 ）（ｍｏｄ  ｑ）｝ｐ  ＋  ｘ1
の演算により、署名文Ｓを生成する
ことを特徴とする請求項１３に記載のＲＳＡ署名装置。
【請求項１５】
前記出力手段は、一致しないと判断される場合に、故障発生の旨を示すメッセージを出力する
ことを特徴とする請求項１２に記載のＲＳＡ署名装置。
【請求項１６】
前記署名生成手段、前記回復手段及び前記比較手段は、１個の集積回路から構成されている
ことを特徴とする請求項１２に記載のＲＳＡ署名装置。
【請求項１７】
ＲＳＡ署名方式により平文に署名を施して署名文を生成するＲＳＡ署名装置を構成する集積回路であって、
前記ＲＳＡ署名装置は、
請求項１のＲＳＡ公開鍵生成装置から、公開鍵ｅ' を取得する公開鍵取得手段と、
比較手段により、一致すると判断される場合に、生成された前記署名文Ｓを出力する出力手段とを備え、
前記集積回路は、
秘密鍵ｄを用いて、平文ＭにＲＳＡ署名を施して署名文Ｓを生成する署名生成手段と、
取得した公開鍵ｅ’を用いて、署名文Ｓに、ＲＳＡ署名回復を施して、復号文Ｄを生成する回復手段と、
平文Ｍと、生成した復号文Ｄとを比較し、一致するか否かを判断する比較手段と
を備えることを特徴とする集積回路。
【請求項１８】
ＲＳＡ署名方式により平文に署名を施して署名文を生成するＲＳＡ署名装置であって、
素数ｑは、素数ｐと異なり、公開鍵ｅは、ｐ−１とｑ−１との最小公倍数ｌｃｍと互いに素で、ｐ−１＞ｅを満たし、前記秘密鍵ｄは、ｌｃｍを法とする剰余体において公開鍵ｅの逆元であり、
前記ＲＳＡ署名装置は、
ＲＳＡ暗号の秘密鍵ｄ及び素数ｐを取得する取得手段と、
取得された秘密鍵ｄと素数ｐを用い、素数ｐ−１を法とする前記秘密鍵ｄの剰余ｄp を算出する剰余演算手段と、
算出された前記剰余ｄp 及び取得された前記素数ｐを用い、素数ｐ−１を法とする剰余体における前記剰余ｄp の逆元を算出し、算出した逆元を新たな公開鍵ｅ' とする逆元演算手段と、
秘密鍵ｄを用いて、平文ＭにＲＳＡ署名を施して署名文Ｓを生成する署名生成手段と、
取得した公開鍵ｅ’を用いて、署名文Ｓに、ＲＳＡ署名回復を施して、復号文Ｄを生成する回復手段と、
平文Ｍと、生成した復号文Ｄとを比較し、一致するか否かを判断する比較手段と、
一致すると判断される場合に、生成された前記署名文Ｓを出力する出力手段と
を備えることを特徴とするＲＳＡ署名装置。
【請求項１９】
ＲＳＡ暗号方式の秘密鍵ｄから新たに公開鍵ｅ’を生成するＲＳＡ公開鍵生成装置で用いられるＲＳＡ公開鍵生成方法であって、
素数ｑは、素数ｐと異なり、公開鍵ｅは、ｐ−１とｑ−１との最小公倍数ｌｃｍと互いに素で、ｐ−１＞ｅを満たし、前記秘密鍵ｄは、ｌｃｍを法とする剰余体において公開鍵ｅの逆元であり、
前記ＲＳＡ公開鍵生成方法は、
ＲＳＡ暗号の秘密鍵ｄ及び素数ｐを取得する取得ステップと、
取得された秘密鍵ｄと素数ｐを用い、素数ｐ−１を法とする前記秘密鍵ｄの剰余ｄp を算出する剰余演算ステップと、
算出された前記剰余ｄp 及び取得された前記素数ｐを用い、素数ｐ−１を法とする剰余体における前記剰余ｄp の逆元を算出し、算出した逆元を新たな公開鍵ｅ' とする逆元演算ステップと
を含むことを特徴とするＲＳＡ公開鍵生成方法。
【請求項２０】
ＲＳＡ暗号方式の秘密鍵ｄから新たに公開鍵ｅ’を生成するＲＳＡ公開鍵生成装置で用いられるＲＳＡ公開鍵生成用のコンピュータプログラムであって、
素数ｑは、素数ｐと異なり、公開鍵ｅは、ｐ−１とｑ−１との最小公倍数ｌｃｍと互いに素で、ｐ−１＞ｅを満たし、前記秘密鍵ｄは、ｌｃｍを法とする剰余体において公開鍵ｅの逆元であり、
ＲＳＡ暗号の秘密鍵ｄ及び素数ｐを取得する取得ステップと、
取得された秘密鍵ｄと素数ｐを用い、素数ｐ−１を法とする前記秘密鍵ｄの剰余ｄp を算出する剰余演算ステップと、
算出された前記剰余ｄp 及び取得された前記素数ｐを用い、素数ｐ−１を法とする剰余体における前記剰余ｄp の逆元を算出し、算出した逆元を新たな公開鍵ｅ' とする逆元演算ステップと
を含むことを特徴とするコンピュータプログラム。
【請求項２１】
コンピュータ読み取り可能な記録媒体に記録されている
ことを特徴とする請求項２０に記載のコンピュータプログラム。
【請求項２２】
搬送波上に具現化されている
ことを特徴とする請求項２０に記載のコンピュータプログラム。
【請求項２３】
ＲＳＡ暗号方式により生成された暗号文を復号するＲＳＡ復号装置で用いられるＲＳＡ復号方法であって、
請求項１のＲＳＡ公開鍵生成装置から、公開鍵ｅ' を取得する公開鍵取得ステップと、
前記公開鍵ｅを用いて、ＲＳＡ暗号方式により平文ＭがＲＳＡ暗号化されて生成された暗号文Ｃを取得する暗号文取得ステップと、
秘密鍵ｄを用いて、取得した前記暗号文ＣをＲＳＡ復号して復号文Ｄを生成するＲＳＡ復号ステップと、
取得した公開鍵ｅ' を用いて、生成された復号文ＤをＲＳＡ暗号化して再暗号文Ｃ’を生成する再暗号化ステップと、
取得した暗号文Ｃと生成した再暗号文Ｃ’とを比較し、一致するか否かを判断する比較ステップと、
一致すると判断される場合に、生成された前記復号文Ｄを出力する出力ステップと
を含むことを特徴とするＲＳＡ復号方法。
【請求項２４】
ＲＳＡ暗号方式により生成された暗号文を復号するＲＳＡ復号装置で用いられるＲＳＡ復号用のコンピュータプログラムであって、
請求項１のＲＳＡ公開鍵生成装置から、公開鍵ｅ' を取得する公開鍵取得ステップと、
前記公開鍵ｅを用いて、ＲＳＡ暗号方式により平文ＭがＲＳＡ暗号化されて生成された暗号文Ｃを取得する暗号文取得ステップと、
秘密鍵ｄを用いて、取得した前記暗号文ＣをＲＳＡ復号して復号文Ｄを生成するＲＳＡ復号ステップと、
取得した公開鍵ｅ' を用いて、生成された復号文ＤをＲＳＡ暗号化して再暗号文Ｃ’を生成する再暗号化ステップと、
取得した暗号文Ｃと生成した再暗号文Ｃ’とを比較し、一致するか否かを判断する比較ステップと、
一致すると判断される場合に、生成された前記復号文Ｄを出力する出力ステップと
を含むことを特徴とするコンピュータプログラム。
【請求項２５】
コンピュータ読み取り可能な記録媒体に記録されている
ことを特徴とする請求項２４に記載のコンピュータプログラム。
【請求項２６】
搬送波上に具現化されている
ことを特徴とする請求項２４に記載のコンピュータプログラム。
【請求項２７】
ＲＳＡ署名方式により平文に署名を施して署名文を生成するＲＳＡ署名方法であって、
請求項１のＲＳＡ公開鍵生成装置から、公開鍵ｅ' を取得する公開鍵取得ステップと、
秘密鍵ｄを用いて、平文ＭにＲＳＡ署名を施して署名文Ｓを生成する署名生成ステップと、
取得した公開鍵ｅ’を用いて、署名文Ｓに、ＲＳＡ署名回復を施して、復号文Ｄを生成する回復ステップと、
平文Ｍと、生成した復号文Ｄとを比較し、一致するか否かを判断する比較ステップと、
一致すると判断される場合に、生成された前記署名文Ｓを出力する出力ステップと
を含むことを特徴とするＲＳＡ署名方法。
【請求項２８】
ＲＳＡ署名方式により平文に署名を施して署名文を生成するＲＳＡ署名用のコンピュータプログラムであって、
請求項１のＲＳＡ公開鍵生成装置から、公開鍵ｅ' を取得する公開鍵取得ステップと、
秘密鍵ｄを用いて、平文ＭにＲＳＡ署名を施して署名文Ｓを生成する署名生成ステップと、
取得した公開鍵ｅ’を用いて、署名文Ｓに、ＲＳＡ署名回復を施して、復号文Ｄを生成する回復ステップと、
平文Ｍと、生成した復号文Ｄとを比較し、一致するか否かを判断する比較ステップと、
一致すると判断される場合に、生成された前記署名文Ｓを出力する出力ステップと
を含むことを特徴とするコンピュータプログラム。
【請求項２９】
コンピュータ読み取り可能な記録媒体に記録されている
ことを特徴とする請求項２８に記載のコンピュータプログラム。
【請求項３０】
搬送波上に具現化されている
ことを特徴とする請求項２８に記載のコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、公開鍵暗号アルゴリズムの一つであるＲＳＡ暗号技術を用いた情報セキュリティ技術に関する。
【背景技術】
【０００２】
従来より情報の秘匿、認証等を実現する手段として公開鍵暗号方式が知られている。
公開鍵暗号方式では、自分のみが保持する秘密鍵と、前記秘密鍵に対応し公開される公開鍵とのペアが生成され、前記公開鍵を用いて暗号化が行われ、前記秘密鍵を用いて復号が行われる。例えば、メッセージの暗号化通信においては、メッセージ送信者がメッセージ受信者の公開鍵を用いてメッセージを暗号化し、秘密鍵の保持者であるメッセージ受信者のみが、メッセージ受信者の秘密鍵を用いて、その暗号化メッセージを復号できる。
【０００３】
公開鍵暗号法は、処理演算量が多いという欠点はあるものの、秘密鍵を複数の利用者により共有する必要がないので、高セキュリティを必要とする場合によく用いられる。一般に良く知られている公開鍵暗号法としては、ＲＳＡ暗号と楕円曲線暗号が存在する。
上述したような公開鍵暗号方式を用いることにより、第三者に知られないように、秘密情報を相手に送信することができるものの、特許文献１によると、例えば、ＩＣカードが暗号処理を行なっているときに、不正な第三者が、異常クロック、異常電圧、異常電磁波、異常温度等を用いて、故意にエラーを引き起こし、暗号で用いている鍵や秘密情報を取り出せる可能性があり、脅威となっている。このような攻撃は、故障利用攻撃（ＤＦＡ攻撃ともいう）と呼ばれている。
【０００４】
このような故障利用攻撃に対抗するために、特許文献２によると、ディジタル署名の作成を行う冪乗剰余計算を法ｎの素因数を用いて中国剰余定理（Chinese Remainder Theorem 、略称は、ＣＲＴ）により高速で処理し、中国剰余定理による計算過程において生成されるデータとともに、該データについてのエラー検出符号を同時に計算して記憶しておき、ディジタル署名の作成の際に、前記データのエラー検出符号を再度計算し、記憶しておいたエラー検出符号と照合してデータの誤りを検出し、誤りを検出した時にはエラーステータスを返す技術を開示している。こうして、中国剰余定理を利用して高速に署名作成処理をするＩＣカードの故障利用攻撃に対する安全性を高めている。
【特許文献１】特開２００２−２６１７５１号公報
【特許文献２】特開平１１−８６１６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
上述したように、従来技術によると、中国剰余定理を利用して署名作成処理をするＩＣカードの故障利用攻撃に対する安全性を高めているものの、さらに、高速に情報セキュリティ処理を行うことが要望されている。
上記の要望に応えるために、本発明は、従来技術と比較して高速に情報セキュリティ演算を行うことができるＲＳＡ公開鍵生成装置、ＲＳＡ復号装置、ＲＳＡ署名装置、方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
上記の目的を達成するために、本発明は、ＲＳＡ暗号方式の秘密鍵ｄから新たに公開鍵ｅ’を生成するＲＳＡ公開鍵生成装置であって、素数ｑは、素数ｐと異なり、公開鍵ｅは、ｐ−１とｑ−１との最小公倍数ｌｃｍと互いに素で、ｐ−１＞ｅを満たし、前記秘密鍵ｄは、ｌｃｍを法とする剰余体において公開鍵ｅの逆元であり、前記ＲＳＡ公開鍵生成装置は、ＲＳＡ暗号の秘密鍵ｄ及び素数ｐを取得する取得手段と、取得された秘密鍵ｄと素数ｐを用い、素数ｐ−１を法とする前記秘密鍵ｄの剰余ｄp を算出する剰余演算手段と、算出された前記剰余ｄp 及び取得された前記素数ｐを用い、素数ｐ−１を法とする剰余体における前記剰余ｄp の逆元を算出し、算出した逆元を新たな公開鍵ｅ' とする逆元演算手段とを備えることを特徴とする。
【発明の効果】
【０００７】
この構成によると、公開鍵を求めるために、逆元の演算の対象となる剰余ｄp は、秘密鍵ｄのおよそ半分のビット数の値であるので、逆元演算手段により、逆元演算にかかる時間が従来より大幅に短縮されるという効果がある。
また、本発明は、ＲＳＡ暗号方式により生成された暗号文を復号するＲＳＡ復号装置であって、前記ＲＳＡ公開鍵生成装置から、公開鍵ｅ' を取得する公開鍵取得手段と、前記公開鍵ｅを用いて、ＲＳＡ暗号方式により平文ＭがＲＳＡ暗号化されて生成された暗号文Ｃを取得する暗号文取得手段と、秘密鍵ｄを用いて、取得した前記暗号文ＣをＲＳＡ復号して復号文Ｄを生成するＲＳＡ復号手段と、取得した公開鍵ｅ' を用いて、生成された復号文ＤをＲＳＡ暗号化して再暗号文Ｃ’を生成する再暗号化手段と、取得した暗号文Ｃと生成した再暗号文Ｃ’とを比較し、一致するか否かを判断する比較手段と、一致すると判断される場合に、生成された前記復号文Ｄを出力する出力手段とを備える。
【０００８】
この構成によると、比較手段により一致すると判断される場合に、生成された復号文を出力するので、故障利用攻撃に対抗することができる。
ここで、前記ＲＳＡ復号手段は、請求項１のＲＳＡ公開鍵生成装置から、剰余ｄp を取得し、取得した剰余ｄp を用いて、中国剰余定理により、取得した前記暗号文ＣをＲＳＡ復号して復号文Ｄを生成するとしてもよい。
【０００９】
この構成によると、公開鍵を求めるために、逆元の演算の対象となる剰余ｄp をそのまま中国剰余定理アルゴリズムを用いるＲＳＡ復号のプロセスの中で用いることができるので、ＲＳＡ復号等にかかる時間を短縮することができる。
また、本発明は、ＲＳＡ署名方式により平文に署名を施して署名文を生成するＲＳＡ署名装置であって、前記ＲＳＡ公開鍵生成装置から、公開鍵ｅ' を取得する公開鍵取得手段と、秘密鍵ｄを用いて、平文ＭにＲＳＡ署名を施して署名文Ｓを生成する署名生成手段と、取得した公開鍵ｅ’を用いて、署名文Ｓに、ＲＳＡ署名回復を施して、復号文Ｄを生成する回復手段と、平文Ｍと、生成した復号文Ｄとを比較し、一致するか否かを判断する比較手段と、一致すると判断される場合に、生成された前記署名文Ｓを出力する出力手段とを備える。
【００１０】
この構成によると、比較手段により一致すると判断される場合に、生成された署名文を出力するので、故障利用攻撃に対抗することができる。
ここで、前記署名生成手段は、請求項１のＲＳＡ公開鍵生成装置から、剰余ｄp を取得し、取得した剰余ｄp を用いて、中国剰余定理により、前記平文ＭにＲＳＡ署名を施して署名文Ｓを生成するとしてもよい。
【００１１】
この構成によると、公開鍵を求めるために、逆元の演算の対象となる剰余ｄp をそのまま中国剰余定理アルゴリズムを用いるＲＳＡ署名のプロセスの中で用いることができるので、ＲＳＡ署名にかかる時間を短縮することができる。
【発明を実施するための最良の形態】
【００１２】
１．第１の実施の形態
本発明に係る１の実施の形態としての秘密通信システム１０について説明する。
１．１  秘密通信システム１０の構成
秘密通信システム１０は、図１に示すように、レジスタ装置１００とＩＣカード３００とから構成されている。
【００１３】
レジスタ装置１００は、小売店に設置されており、小売店の販売担当者により操作され、利用者が購入した商品の購入額に応じて、特典であるポイントを発行する。レジスタ装置１００は、発行したポイントを暗号化して暗号化ポイントを生成し、生成した暗号化ポイントをレジスタ装置１００に接続されているカードリーダ２００を介して、利用者のＩＣカード３００へ出力する。
【００１４】
ＩＣカード３００は、暗号化ポイントを受け取り、受け取った暗号化ポイントを復号して復号ポイントを生成し、生成した復号ポイントを記憶する。
利用者は、ＩＣカード３００に記憶された復号ポイントを次に商品を購入する際に、代金の一部として用いることができる。
１．２  ＩＣカード３００の公開鍵ｅ及び秘密鍵ｄの生成
以下に示すようにして、鍵生成装置（図示していない）は、ＩＣカード３００の公開鍵ｅ及び秘密鍵ｄを生成する。
【００１５】
（ａ）任意の相異なる２個の大きな素数ｐ及び素数ｑを選び、その積ｎを計算する。  ｎ＝ｐ×ｑ
（ｂ）（ｐ−１）と（ｑ−１）の最小公倍数Ｌを計算し、最小公倍数Ｌと互いに素で最小公倍数Ｌより小さい任意の整数ｅ（公開鍵）を選ぶ。
Ｌ＝ＬＣＭ（（ｐ−１）、（ｑ−１））
ＧＣＤ（ｅ、Ｌ）＝１
１＜ｅ＜Ｌ
ここで、ＬＣＭ（Ｘ，Ｙ）は、数Ｘと数Ｙとの最小公倍数を示し、ＧＣＤ（Ｘ，Ｙ）は、数Ｘと数Ｙとの最大公倍数を示す。ＬＣＭは、Least Common Multipleの略称であり、ＧＣＤは、Greatest Common Divisorの略称である。
【００１６】
（ｃ）（ｂ）で求めた公開鍵ｅと最小公倍数Ｌを基に、次の式を解き、秘密鍵ｄを求める。
ｅｄ＝１  （ｍｏｄ  Ｌ）
鍵生成装置は、素数ｐ、素数ｑ及び公開鍵ｅを予め、レジスタ装置１００へ通知しておく。また、素数ｐ、素数ｑ及び秘密鍵ｄを予め、ＩＣカード３００へ通知しておく。
【００１７】
レジスタ装置１００の公開鍵ＰＫ及び秘密鍵ＳＫについても同様にして鍵生成装置により生成され、秘密鍵ＳＫは、予め、レジスタ装置１００へ通知され、公開鍵ＰＫは、予め、ＩＣカード３００へ通知される。
１．３  レジスタ装置１００の構成
レジスタ装置１００は、図２に示すように、表示部１０１、表示部１０２、印字部１０３、入力部１０４、保管庫１０５、情報記憶部１０６、制御部１０７、認証部１０８、暗復号部１０９、入出力部１１０及び鍵記憶部１１１から構成されている。また、レジスタ装置１００の入出力部１１０には、カードリーダ２００が接続されている。
【００１８】
レジスタ装置１００は、利用者から支払われる購入代金の決済、保管などを行う金銭レジスタ装置であり、また、利用者が購入した商品の購入額に応じて、特典であるポイントを発行し、発行したポイントを暗号化して暗号化ポイントを生成し、生成した暗号化ポイントを、カードリーダ２００を介して、利用者のＩＣカード３００へ出力する。
レジスタ装置１００は、具体的には、マイクロプロセッサ、ＲＯＭ、ＲＡＭなどを含んで構成されるコンピュータシステムである。前記ＲＯＭには、コンピュータプログラムが記憶されている。前記マイクロプロセッサが、前記コンピュータプログラムに従って動作することにより、レジスタ装置１００は、その一部の機能を達成する。
【００１９】
（１）鍵記憶部１１１
鍵記憶部１１１は、外部からアクセスができないように設けられており、図２に示すように、予め、ＩＣカード３００の公開鍵ｅ、素数ｐ、素数ｑ及びレジスタ装置１００の秘密鍵ＳＫを記憶している。
公開鍵ｅは、ＲＳＡ公開鍵暗号方式の鍵生成アルゴリズムにより生成されたＩＣカード３００の公開鍵であり、１０２４ビット長のデータ領域に格納されている。
【００２０】
素数ｐ及び素数ｑは、任意の異なる大きな素数であり、それぞれ、５１２ビット長のデータ領域に格納されている。ここで、一例として、
ｐ＝
d32737e7 267ffe13 41b2d5c0 d150a81b 586fb313 2bed2f8d 5262864a 9cb9f30a
f38be448 598d413a 172efb80 2c21acf1 c11c520c 2f26a471 dcad212e ac7ca39d
であり、
ｑ＝
cc8853d1 d54da630 fac004f4 71f281c7 b8982d82 24a490ed beb33d3e 3d5cc93c
4765703d 1dd79164 2f1f116a 0dd852be 2419b2af 72bfe9a0 30e860b0 288b5d77
である。これらの表記は、16進数である。見やすいように、８桁ずつに区切って表示している。
【００２１】
秘密鍵ＳＫは、ＲＳＡ公開鍵暗号方式の鍵生成アルゴリズムにより生成されたレジスタ装置１００の秘密鍵であり、１０２４ビット長のデータ領域に格納されている。
（２）情報記憶部１０６
情報記憶部１０６は、利用者を識別する利用者識別子、利用者の購入金額、購入日付、発行ポイントなど、利用者による商品の購入に関する情報を記憶するための領域を備えている。
【００２２】
（３）認証部１０８
認証部１０８は、カードリーダ２００にＩＣカード３００が装着されたときに、入出力部１１０及びカードリーダ２００を介して、以下に示すようにして、ＩＣカード３００との間で相互に機器認証を行う。ここで、機器認証は、チャレンジ−レスポンス型の認証である。
【００２３】
（レジスタ装置１００によるＩＣカード３００の認証）
認証部１０８は、乱数Ｒ1 を生成し、生成した乱数Ｒ1 を入出力部１１０及びカードリーダ２００を介して、ＩＣカード３００へ出力する。
また、認証部１０８は、ＩＣカード３００から、カードリーダ２００及び入出力部１１０を介して、署名データＳ1 を受け取り、鍵記憶部１１１からＩＣカード３００の公開鍵ｅ、素数ｐ及び素数ｑを読み出す。次に、生成した乱数Ｒ1 にハッシュ関数Ｈａｓｈを施してハッシュ値Ｈ2 を生成する。
【００２４】
Ｈ2 ＝Ｈａｓｈ（Ｒ1 ）
ここで、Ｈａｓｈ（Ｒ1 ）は、乱数Ｒ1 にハッシュ関数Ｈａｓｈを施して得られた値を示す。また、ハッシュ関数Ｈａｓｈの一例は、ＳＨＡ−１である。
次に、認証部１０８は、ｎ＝ｐ×ｑを計算し、Ｓ1e （ｍｏｄ  ｎ）を計算し、生成したハッシュ値Ｈ2 と計算して得られた値Ｓ1e （ｍｏｄ  ｎ）とを比較し、一致するなら、認証成功とみなし、一致しないなら認証失敗とみなす。
【００２５】
認証部１０８は、認証が成功した場合に、機器認証の成功の旨を示す情報を制御部１０７へ通知する。また、機器認証が失敗した場合に、機器認証の失敗の旨を示す情報を制御部１０７へ通知する。
機器認証が失敗した場合には、それ以降、レジスタ装置１００は、当該ＩＣカード３００との間で情報の送受信は、行わない。
【００２６】
（ＩＣカード３００によるレジスタ装置１００の認証）
認証部１０８は、ＩＣカード３００から、カードリーダ２００及び入出力部１１０を介して、乱数Ｒ2 を受け取り、鍵記憶部１１１から秘密鍵ＳＫ、素数ｐ及び素数ｑを読み出し、受け取った乱数Ｒ2 にハッシュ関数Ｈａｓｈを施してハッシュ値Ｈ3 を計算する。
Ｈ3 ＝Ｈａｓｈ（Ｒ2 ）
次に、認証部１０８は、ｎ＝ｐ×ｑを計算し、署名データＳ2 ＝（Ｈ3 ）SK  （ｍｏｄ  ｎ）を計算し、計算して得られた署名データＳ2 を入出力部１１０及びカードリーダ２００を介して、ＩＣカード３００へ出力する。
【００２７】
（４）入出力部１１０及びカードリーダ２００
入出力部１１０は、制御部１０７の制御の元に、制御部１０７とカードリーダ２００との間で、又は認証部１０８の制御の元に認証部１０８とカードリーダ２００との間で、双方向に情報の送受信を行う。
カードリーダ２００は、ＩＣカード３００と入出力部１１０との間で情報の送受信を行う。
【００２８】
（５）暗復号部１０９
（セッション鍵の出力）
暗復号部１０９は、乱数を生成し、生成した乱数をセッション鍵Ｍとする。次に、鍵記憶部１１１から、素数ｐ、素数ｑ及び公開鍵ｅを読み出し、整数ｎ＝ｐ×ｑを計算し、セッション鍵Ｍ、整数ｎ及び公開鍵ｅを用いて、暗号化セッション鍵Ｃ1 を次の式により算出する。
【００２９】
暗号化セッション鍵Ｃ1 ＝Ｍe （ｍｏｄ  ｎ）
次に、算出して得られた暗号化セッション鍵Ｃ1 を入出力部１１０及びカードリーダ２００を介して、ＩＣカード３００へ出力する。
（ポイントの出力）
暗復号部１０９は、制御部１０７からポイントＰｔを受け取り、生成したセッション鍵Ｍを鍵として用いて、受け取ったポイントＰｔに暗号化アルゴリズムＥ1 を施して、暗号化ポイントＥｔを生成する。
【００３０】
暗号化ポイントＥｔ＝Ｅ1 （セッション鍵Ｍ、ポイントＰｔ）
ここで、Ｅ（Ａ、Ｂ）は、鍵Ａを用いて、平文Ｂに暗号化アルゴリズムＥを施して得られた暗号文を示す。また、暗号化アルゴリズムＥ1 は、一例として、共通鍵暗号方式のＤＥＳ（Ｄａｔａ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｔａｎｄａｒｄ）によるものである。
次に、暗復号部１０９は、暗号化ポイントＥｔを、入出力部１１０及びカードリーダ２００を介して、ＩＣカード３００へ出力する。
【００３１】
（６）制御部１０７
制御部１０７は、小売店の販売担当者の操作により、利用者が購入した商品の購入額に応じて、特典であるポイントＰｔを生成し、生成したポイントＰｔを暗復号部１０９へ出力する。
また、制御部１０７は、レジスタ装置１００を構成する他の構成要素を制御する。
【００３２】
（７）入力部１０４、表示部１０１、表示部１０２、印字部１０３及び保管庫１０５
入力部１０４は、レジスタ装置１００の操作者から入力情報を受け付け、受け付けた入力情報を制御部１０７へ出力する。また、表示部１０１及び表示部１０２は、制御部１０７から表示すべき情報を受け取り、受け取った情報を表示する。
印字部１０３は、制御部１０７の制御により、各種情報を印刷する。
【００３３】
保管庫１０５は、紙幣や貨幣を保管する。
１．４  ＩＣカード３００の構成
ＩＣカード３００は、長さ約８５ｍｍ、幅５４ｍｍ、厚さ０．７６ｍｍの薄板状の樹脂から形成されており、外表面に接触端子を備え、内部にシステムＬＳＩ（大規模集積回路、Large Scale Integrated circuit）３２０が封入されている。
【００３４】
ＩＣカード３００は、図３に示すように、入出力部３０１、認証部３０２、復号部３０３、高速公開鍵演算部３０４、制御部３０５、再暗号化部３０６、情報記憶部３０７、復号部３０８及び鍵記憶部３０９から構成されており、認証部３０２、復号部３０３、高速公開鍵演算部３０４、制御部３０５、再暗号化部３０６、情報記憶部３０７、復号部３０８及び鍵記憶部３０９は、システムＬＳＩ３２０を形成している。
【００３５】
システムＬＳＩ３２０は、上記の複数の構成部を１個のチップ上に集積して製造された長多機能ＬＳＩであり、具体的には、マイクロプロセッサ、ＲＯＭ、ＲＡＭなどを含んで構成されるコンピュータシステムである。前記ＲＡＭには、コンピュータプログラムが記憶されている。前記マイクロプロセッサが、前記コンピュータプログラムに従って動作することにより、システムＬＳＩ３２０は、その一部の機能を達成する。
【００３６】
（１）鍵記憶部３０９
鍵記憶部３０９は、図３に示すように、予め、レジスタ装置１００の公開鍵ＰＫ、素数ｐ、素数ｑ及びＩＣカード３００の秘密鍵ｄを記憶している。
公開鍵ＰＫは、ＲＳＡ公開鍵暗号方式の鍵生成アルゴリズムにより生成されたレジスタ装置１００の公開鍵であり、１０２４ビット長のデータ領域に格納されている。
【００３７】
素数ｐ及び素数ｑについては、上述した通りであり、それぞれ、５１２ビット長のデータ領域に格納されている。
秘密鍵ｄは、ＲＳＡ公開鍵暗号方式の鍵生成アルゴリズムにより生成されたＩＣカード３００の秘密鍵であり、１０２４ビット長のデータ領域に格納されている。
（２）高速公開鍵演算部３０４
高速公開鍵演算部３０４は、図３に示すように、秘密鍵取得部３１１、剰余演算部３１２、逆数演算部３１３及び法演算部３１４から構成されている。
【００３８】
秘密鍵取得部３１１は、鍵記憶部３０９から秘密鍵ｄ、素数ｐ及び素数ｑを読み出し、読み出した秘密鍵ｄ及び素数ｐを剰余演算部３１２へ出力し、また、読み出した素数ｐ及び素数ｑを法演算部３１４へ出力する。
剰余演算部３１２は、秘密鍵取得部３１１から秘密鍵ｄ及び素数ｐを受け取り、受け取った秘密鍵ｄ及び素数ｐを用いて、
ｄ1 ＝ｄ  （ｍｏｄ  ｐ−１）
を算出し、算出して得られた数ｄ1 及び素数ｐを逆数演算部３１３へ出力し、また、数ｄ1 を復号部３０３へ出力する。
【００３９】
逆数演算部３１３は、剰余演算部３１２から数ｄ1 及び素数ｐを受け取り、受け取った数ｄ1 及び素数ｐを用いて、次式により、公開鍵ｅ’を算出する。
ｅ’＝ｄ1 -1  （ｍｏｄ  ｐ−１）
次に、逆数演算部３１３は、算出して得られた公開鍵ｅ’を再暗号化部３０６及び認証部３０２へ出力する。
【００４０】
法演算部３１４は、秘密鍵取得部３１１から、素数ｐ及び素数ｑを受け取り、受け取った素数ｐ及び素数ｑを用いて、整数ｎ＝ｐ×ｑを算出し、算出して得られた整数ｎを認証部３０２及び再暗号化部３０６へ出力する。
（３）認証部３０２
（レジスタ装置１００によるＩＣカード３００の認証）
認証部３０２は、レジスタ装置１００から、カードリーダ２００及び入出力部３０１を介して、乱数Ｒ1 を受け取り、鍵記憶部３０９から素数ｐ及び素数ｑ及び秘密鍵ｄを読み出し、法演算部３１４から整数ｎを受け取り、受け取った乱数Ｒ1 を用いて、ハッシュ値Ｈ1 を次式により算出する。
【００４１】
Ｈ1 ＝Ｈａｓｈ（Ｒ1 ）
次に、認証部３０２は、次式を順に演算することにより、署名データＳ1 を算出する。
ａ＝ｐ-1    （ｍｏｄ  ｑ）
ｙ1 ＝Ｈ1   （ｍｏｄ  ｐ）
ｙ2 ＝Ｈ1   （ｍｏｄ  ｑ）
ｄ2 ＝ｄ    （ｍｏｄ  ｑ−１）
ｘ1 ＝ｙ1d1 （ｍｏｄ  ｐ）
ｘ2 ＝ｙ2d2 （ｍｏｄ  ｑ）
ｓ1 ＝｛ａ（ｘ2 −ｘ1 ）（ｍｏｄ  ｑ）｝ｐ  ＋  ｘ1
次に、計算して得られた署名データｓ1 を再暗号化部３０６へ出力し、再暗号化部３０６から、ｓ1 e'（ｍｏｄ  ｎ）を受け取る。
【００４２】
次に、ハッシュ値Ｈ1 とｓ1 e'（ｍｏｄ  ｎ）とが一致する否かを判断し、一致しないと判断する場合には、何らかのエラーが発生したものとみなして、認証部３０２は、エラー発生を示すエラー情報を制御部３０５へ通知する。これ以降、ＩＣカード３００は、その動作を停止する。
一致すると判断する場合には、認証部３０２は、生成した署名データＳ1 を入出力部３０１及びカードリーダ２００を介して、レジスタ装置１００へ出力する。
【００４３】
（ＩＣカード３００によるレジスタ装置１００の認証）
認証部３０２は、乱数Ｒ2 を生成し、生成した乱数Ｒ2 を、入出力部３０１及びカードリーダ２００を介して、レジスタ装置１００へ出力する。
次に、認証部３０２は、レジスタ装置１００から、カードリーダ２００及び入出力部３０１を介して、署名データＳ2 を受け取り、鍵記憶部３０９からレジスタ装置１００の公開鍵ＰＫ、素数ｐ及び素数ｑを読み出し、整数ｎ＝ｐ×ｑを計算し、生成した乱数Ｒ2 を用いて、ハッシュ値Ｈ4 を計算する。
【００４４】
Ｈ4 ＝Ｈａｓｈ（Ｒ2 ）
次に、認証部３０２は、Ｓ2 PK  （ｍｏｄ  ｎ）を計算し、Ｈ4 とＳ2 PK  （ｍｏｄ  ｎ）とが一致するか否かを判断し、一致するなら、認証成功とみなし、一致しないなら認証失敗とみなす。
認証部３０２は、認証が成功した場合に、機器認証の成功の旨を示す情報を制御部３０５へ通知する。また、機器認証が失敗した場合に、機器認証の失敗の旨を示す情報を制御部３０５へ通知する。
【００４５】
機器認証が失敗した場合には、それ以降、ＩＣカード３００は、レジスタ装置１００との間で情報の送受信を、行わない。
（４）再暗号化部３０６
再暗号化部３０６は、逆数演算部３１３から公開鍵ｅ’を受け取り、法演算部３１４から整数ｎを受け取り、次式を計算する。
【００４６】
ｓ1 e'（ｍｏｄ  ｎ）
次に、再暗号化部３０６は、得られた  ｓ1 e'（ｍｏｄ  ｎ）を認証部３０２へ出力する。
（５）制御部３０５
制御部３０５は、エラー情報、機器認証の成功の旨を示す情報、及び機器認証の失敗の旨を示す情報を受け取る。
【００４７】
制御部３０５は、認証部３０２からエラー情報を受け取ると、ＩＣカード３００を構成するその他の構成要素に対して、動作の停止を指示する。
制御部３０５は、認証部３０２から機器認証の失敗の旨を示す情報を受け取ると、ＩＣカード３００を構成するその他の構成要素に対して、動作の停止を指示する。一方、機器認証の成功の旨を示す情報を受け取ると、以降の動作を継続する。
【００４８】
（６）復号部３０３
復号部３０３は、レジスタ装置１００からカードリーダ２００及び入出力部３０１を介して、暗号化セッション鍵Ｃ1 を受け取る。
次に、復号部３０３は、鍵記憶部３０９から素数ｐ及び素数ｑを受け取り、剰余演算部３１２から数ｄ1 を受け取り、次式を順に演算することにより、復号セッション鍵ｘを算出する。
【００４９】
ａ＝ｐ-1    （ｍｏｄ  ｑ）
ｙ1 ＝Ｃ1   （ｍｏｄ  ｐ）
ｙ2 ＝Ｃ1   （ｍｏｄ  ｑ）
ｄ2 ＝ｄ    （ｍｏｄ  ｑ−１）
ｘ1 ＝ｙ1d1 （ｍｏｄ  ｐ）
ｘ2 ＝ｙ2d2 （ｍｏｄ  ｑ）
ｘ＝｛ａ（ｘ2 −ｘ1 ）（ｍｏｄ  ｑ）｝ｐ  ＋  ｘ1
次に、計算して得られた復号セッション鍵ｘを復号部３０８へ出力する。
【００５０】
（７）復号部３０８
復号部３０８は、レジスタ装置１００から、カードリーダ２００及び入出力部３０１を介して、暗号化ポイントＥｔを受け取り、復号部３０３から復号セッション鍵ｘを受け取り、受け取った復号セッション鍵ｘを鍵として用いて、受け取った暗号化ポイントＥｔに復号アルゴリズムＤ1 を施して復号ポイントＤｔを生成し、生成した復号ポイントＤｔを情報記憶部３０７へ書き込む。
【００５１】
ここで、復号アルゴリズムＤ1 は、共通鍵暗号方式のＤＥＳによるものであり、暗号化アルゴリズムＥ1 により生成された暗号文を復号する。
（８）入出力部３０１
入出力部３０１は、カードリーダ２００を介してレジスタ装置１００と、ＩＣカード３００を構成するその他の構成要素との間で情報の送受信を行う。
【００５２】
（９）情報記憶部３０７
情報記憶部３０７は、復号ポイントＤｔを記憶するための領域を備えている。
１．５  秘密通信システム１０の動作
秘密通信システム１０の動作について説明する。
（１）秘密通信システム１０の全体の概要動作
秘密通信システム１０の全体の概要動作について、図４に示すフローチャートを用いて説明する。
【００５３】
ＩＣカード３００が有する高速公開鍵演算部３０４の剰余演算部３１２は、
ｄ1 ＝ｄ  （ｍｏｄ  ｐ−１）を算出し（ステップＳ１０１）、逆数演算部３１３は、公開鍵ｅ’＝ｄ1 -1  （ｍｏｄ  ｐ−１）を算出する（ステップＳ１０２）。
次に、レジスタ装置１００は、ＩＣカード３００の認証を試み（ステップＳ１０３）、認証に失敗すると（ステップＳ１０４）、ＩＣカード３００との間の通信を終了する。認証に成功すると（ステップＳ１０４）、ＩＣカード３００との間の通信を継続する。
【００５４】
次に、ＩＣカード３００は、レジスタ装置１００の認証を試み（ステップＳ１０５）、認証に失敗すると（ステップＳ１０６）、レジスタ装置１００との間の通信を終了する。認証に成功すると（ステップＳ１０６）、レジスタ装置１００との間の通信を継続する。
次に、レジスタ装置１００は、セッション鍵を暗号化して暗号化セッション鍵を生成し、生成した暗号化セッション鍵をＩＣカード３００へ出力し、ＩＣカード３００は、暗号化セッション鍵を復号して復号セッション鍵を生成し（ステップＳ１０７）、レジスタ装置１００は、セッション鍵を用いて、ポイントを暗号化して暗号化ポイントを生成し、生成した暗号化ポイントを送信し、ＩＣカード３００は、復号セッション鍵を用いて、暗号化ポイントを復号する（ステップＳ１０８）。
【００５５】
（２）レジスタ装置１００によるＩＣカード３００の認証の動作
レジスタ装置１００によるＩＣカード３００の認証の動作について、図５〜図６に示すフローチャートを用いて説明する。
レジスタ装置１００の認証部１０８は、乱数Ｒ1 を生成し（ステップＳ１２１）、生成した乱数Ｒ1 を入出力部１１０及びカードリーダ２００を介して、ＩＣカード３００へ出力する（ステップＳ１２２）。
【００５６】
ＩＣカード３００の認証部３０２は、レジスタ装置１００から、カードリーダ２００及び入出力部３０１を介して、乱数Ｒ1 を受け取り（ステップＳ１２２）、鍵記憶部３０９から素数ｐ及び素数ｑ及び秘密鍵ｄを読み出し、法演算部３１４から整数ｎを受け取り（ステップＳ１２３）、受け取った乱数Ｒ1 を用いて、ハッシュ値Ｈ1 ＝Ｈａｓｈ（Ｒ1 ）を算出する（ステップＳ１２４）。
【００５７】
次に、認証部３０２は、ａ＝ｐ-1    （ｍｏｄ  ｑ）  を算出し（ステップＳ１２５）、
ｙ1 ＝Ｈ1   （ｍｏｄ  ｐ）  を算出し（ステップＳ１２６）、
ｙ2 ＝Ｈ1   （ｍｏｄ  ｑ）  を算出し（ステップＳ１２７）、
ｄ2 ＝ｄ    （ｍｏｄ  ｑ−１）  を算出し（ステップＳ１２８）、
ｘ1 ＝ｙ1d1 （ｍｏｄ  ｐ）  を算出し（ステップＳ１２９）、
ｘ2 ＝ｙ2d2 （ｍｏｄ  ｑ）  を算出し（ステップＳ１３０）、
ｓ1 ＝｛ａ（ｘ2 −ｘ1 ）（ｍｏｄ  ｑ）｝ｐ  ＋  ｘ1   を算出する（ステップＳ１３１）。
【００５８】
再暗号化部３０６は、逆数演算部３１３から公開鍵ｅ’を受け取り、法演算部３１４から整数ｎを受け取り（ステップＳ１３２）、ｓ1 e'（ｍｏｄ  ｎ）を計算する（ステップＳ１３３）。
認証部３０２は、ハッシュ値Ｈ1 とｓ1 e'（ｍｏｄ  ｎ）とが一致する否かを判断し、一致しないと判断する場合には（ステップＳ１３４）、何らかのエラーが発生したものとみなして、認証部３０２は、エラー発生を示すエラー情報を制御部３０５へ通知する。これ以降、ＩＣカード３００は、その動作を停止する。
【００５９】
一致すると判断する場合には（ステップＳ１３４）、認証部３０２は、生成した署名データＳ1 を入出力部３０１及びカードリーダ２００を介して、レジスタ装置１００へ出力する（ステップＳ１４１）。
次に、レジスタ装置１００の認証部１０８は、ＩＣカード３００から、カードリーダ２００及び入出力部１１０を介して、署名データＳ1 を受け取り（ステップＳ１４１）、鍵記憶部１１１からＩＣカード３００の公開鍵ｅ、素数ｐ及び素数ｑを読み出し（ステップＳ１４２）、次に、生成した乱数Ｒ1 にハッシュ関数Ｈａｓｈを施してハッシュ値Ｈ2 ＝Ｈａｓｈ（Ｒ1 ）を生成する（ステップＳ１４３）。
【００６０】
次に、認証部１０８は、ｎ＝ｐ×ｑを計算し、Ｓ1e （ｍｏｄ  ｎ）を計算し（ステップＳ１４４）、生成したハッシュ値Ｈ2 と計算して得られた値Ｓ1e （ｍｏｄ  ｎ）とを比較し、一致するなら（ステップＳ１４５）、認証成功とみなし、一致しないなら（ステップＳ１４５）、認証失敗とみなす。
（３）ＩＣカード３００によるレジスタ装置１００の認証の動作
ＩＣカード３００によるレジスタ装置１００の認証の動作について、図７に示すフローチャートを用いて説明する。
【００６１】
ＩＣカード３００の認証部３０２は、乱数Ｒ2 を生成し（ステップＳ２０１）、生成した乱数Ｒ2 を、入出力部３０１及びカードリーダ２００を介して、レジスタ装置１００へ出力する（ステップＳ２０２）。
レジスタ装置１００の認証部１０８は、ＩＣカード３００から、カードリーダ２００及び入出力部１１０を介して、乱数Ｒ2 を受け取り（ステップＳ２０２）、鍵記憶部１１１から秘密鍵ＳＫ、素数ｐ及び素数ｑを読み出し（ステップＳ２０３）、受け取った乱数Ｒ2 にハッシュ関数Ｈａｓｈを施してハッシュ値Ｈ3 ＝Ｈａｓｈ（Ｒ2 ）を計算する（ステップＳ２０４）。次に、認証部１０８は、ｎ＝ｐ×ｑを計算し、署名データＳ2 ＝（Ｈ3 ）SK  （ｍｏｄ  ｎ）を計算し（ステップＳ２０５）、計算して得られた署名データＳ2 を入出力部１１０及びカードリーダ２００を介して、ＩＣカード３００へ出力する（ステップＳ２０６）。
【００６２】
次に、ＩＣカード３００の認証部３０２は、レジスタ装置１００から、カードリーダ２００及び入出力部３０１を介して、署名データＳ2 を受け取り（ステップＳ２０６）、鍵記憶部３０９からレジスタ装置１００の公開鍵ＰＫ、素数ｐ及び素数ｑを読み出し（ステップＳ２０７）、整数ｎ＝ｐ×ｑを計算し、生成した乱数Ｒ2 を用いて、ハッシュ値Ｈ4 ＝Ｈａｓｈ（Ｒ2 ）を計算する（ステップＳ２０８）。次に、認証部３０２は、Ｓ2 PK  （ｍｏｄ  ｎ）を計算し（ステップＳ２０９）、Ｈ4 とＳ2 PK  （ｍｏｄ  ｎ）とが一致するか否かを判断し、一致するなら（ステップＳ２１０）、認証成功とみなし、一致しないなら（ステップＳ２１０）、認証失敗とみなす。
【００６３】
機器認証が失敗した場合には、それ以降、ＩＣカード３００は、レジスタ装置１００との間で情報の送受信を、行わない。
（４）セッション鍵の受け渡しの動作
セッション鍵の受け渡しの動作について、図８に示すフローチャートを用いて説明する。
【００６４】
レジスタ装置１００の暗復号部１０９は、乱数を生成し、生成した乱数をセッション鍵Ｍとする（ステップＳ２５１）。次に、鍵記憶部１１１から、素数ｐ、素数ｑ及び公開鍵ｅを読み出し、整数ｎ＝ｐ×ｑを計算し、セッション鍵Ｍ、整数ｎ及び公開鍵ｅを用いて、暗号化セッション鍵Ｃ1 ＝Ｍe （ｍｏｄ  ｎ）を算出する（ステップＳ２５２）。次に、算出して得られた暗号化セッション鍵Ｃ1 を入出力部１１０及びカードリーダ２００を介して、ＩＣカード３００へ出力する（ステップＳ２５３）。
【００６５】
次に、ＩＣカード３００の復号部３０３は、レジスタ装置１００からカードリーダ２００及び入出力部３０１を介して、暗号化セッション鍵Ｃ1 を受け取り（ステップＳ２５３）、次に、鍵記憶部３０９から素数ｐ及び素数ｑを受け取り、剰余演算部３１２から数ｄ1 を受け取り、次式を順に演算する。
ａ＝ｐ-1    （ｍｏｄ  ｑ）    （ステップＳ２５６）
ｙ1 ＝Ｃ1   （ｍｏｄ  ｐ）    （ステップＳ２５７）
ｙ2 ＝Ｃ1   （ｍｏｄ  ｑ）    （ステップＳ２５８）
ｄ2 ＝ｄ    （ｍｏｄ  ｑ−１）（ステップＳ２５９）
ｘ1 ＝ｙ1d1 （ｍｏｄ  ｐ）    （ステップＳ２６０）
ｘ2 ＝ｙ2d2 （ｍｏｄ  ｑ）    （ステップＳ２６１）
ｘ＝｛ａ（ｘ2 −ｘ1 ）（ｍｏｄ  ｑ）｝ｐ  ＋  ｘ1  （ステップＳ２６２）
次に、計算して得られた復号セッション鍵ｘを復号部３０８へ出力する（ステップＳ２６３）。
【００６６】
（５）ポイントの秘密通信の動作
ポイントの秘密通信の動作について、図９に示すフローチャートを用いて説明する。
レジスタ装置１００の制御部１０７は、小売店の販売担当者の操作により、利用者が購入した商品の購入額に応じて、特典であるポイントＰｔを生成する（ステップＳ２９１）。次に、暗復号部１０９は、生成したセッション鍵Ｍを鍵として用いて、ポイントＰｔに暗号化アルゴリズムＥ1 を施して、暗号化ポイントＥｔ＝Ｅ1 （セッション鍵Ｍ、ポイントＰｔ）を生成し（ステップＳ２９２）、次に、暗号化ポイントＥｔを、入出力部１１０及びカードリーダ２００を介して、ＩＣカード３００へ出力する（ステップＳ２９３）。
【００６７】
ＩＣカード３００の復号部３０８は、レジスタ装置１００から、カードリーダ２００及び入出力部３０１を介して、暗号化ポイントＥｔを受け取り（ステップＳ２９３）、復号部３０３から復号セッション鍵ｘを受け取り、受け取った復号セッション鍵ｘを鍵として用いて、受け取った暗号化ポイントＥｔに復号アルゴリズムＤ1 を施して復号ポイントＤｔを生成し（ステップＳ２９４）、生成した復号ポイントＤｔを情報記憶部３０７へ書き込む（ステップＳ２９５）。
【００６８】
１．６  ｅ’が公開鍵となることの証明
ここでは、ｄ1 ＝ｄ  （ｍｏｄ  ｐ−１）のとき、ｅ’＝ｄ1-1 （ｍｏｄ  ｐ−１）が公開鍵となることを証明する。
公開鍵ｅ’は、ｅ’＝ｄ-1  （ｍｏｄ  ＬＣＭ（ｐ−１、ｑ−１））により定義される。ここで、ＬＣＭ（ｘ、ｙ）は、ｘとｙとの最小公倍数を示す。
【００６９】
ＬＣＭ（ｐ−１、ｑ−１）は、ｎ×（ｐ−１）と表現できるので、
ｅ’×ｄ＝ｎ×（ｍ×（ｐ−１））＋１となる。
ここで、ｅ＜ｐ−１とすると、
ｅ’×（ｋ×（ｐ−１）＋ｄ1 ）＝ｎ×（ｍ×（ｐ−１））＋１
ｅ’×ｄ1 ＝（ｎ×ｍ−ｅ×ｋ）×（ｐ−１）＋１となり、
ｅ’＝ｄ1-1  （ｍｏｄ  ｐ−１）となる。
【００７０】
２．第２の実施の形態
本発明に係る別の実施の形態としてのＲＳＡ秘密通信システム２０について説明する。
（１）ＲＳＡ秘密通信システム２０の構成
ＲＳＡ秘密通信システム２０は、図１０に示すように、ＲＳＡ暗号装置５００、ＲＳＡ復号装置４００及びメモリカード６００から構成されており、ＲＳＡ暗号装置５００及びＲＳＡ復号装置４００は、ネットワーク５０を介して接続されている。
【００７１】
ＲＳＡ暗号方式における鍵生成において、相互に異なる大きい２個の素数ｐ及び素数ｑについて、数ｎ＝ｐ×ｑであり、ｐ−１とｑ−１との最小公倍数ｌｃｍと互いに素で、ｐ−１＞ｅを満たす公開鍵ｅが生成される。また、最小公倍数ｌｃｍを法とする剰余体において公開鍵ｅの逆元が生成され、生成された逆元が秘密鍵ｄとなる。こうして生成された公開鍵ｅは、予めＲＳＡ暗号装置５００に対して通知されている。
【００７２】
ＲＳＡ暗号装置５００は、ＲＳＡ暗号方式により、公開鍵ｅを鍵として用いて、平文Ｍを暗号化して暗号文Ｃ＝Ｍe （ｍｏｄ  ｎ）を算出する。ここで、ｎ＝ｐ×ｑである。
メモリカード６００は、可搬型の半導体メモリであって、復号処理に用いる秘密鍵ｄ、素数ｐ及び素数ｑを予め記憶している。
ＲＳＡ復号装置４００は、ＲＳＡ暗号装置５００により生成された暗号文
Ｃ＝Ｍe （ｍｏｄ  ｎ）を復号する装置であって、図１０に示すように、データ入力部４０１、ＬＳＩ部４２０、データ出力部４０４及びデータ入力部４０６から構成されている。ＬＳＩ部４２０は、システムＬＳＩであって、データ復号部４０２、高速公開鍵演算部４０３及びデータ再暗号部４０５を含んでいる。また、高速公開鍵演算部４０３は、秘密鍵取得部４１１、剰余演算部４１２、法演算部４１３及び逆数演算部４１４を含んでいる。
【００７３】
データ入力部４０１は、復号対象である暗号文Ｃ＝Ｍe （ｍｏｄ  ｎ）をネットワーク５０を介して、ＲＳＡ暗号装置５００から取得する。
データ入力部４０６は、メモリカード６００から復号処理に用いる秘密鍵ｄ、素数ｐ及び素数ｑを取得する。
データ復号部４０２は、処理の高速化のため中国剰余定理（Chinese Remainder Theorem 、ＣＲＴと略す）により、データ入力部４０６により取得された秘密鍵ｄ、素数ｐ、素数ｑ及び高速公開鍵演算部４０３により算出されたｄ1 を用いて、暗号文Ｃを復号して復号文Ｄを生成する。具体的には、以下に示す演算を行う。
【００７４】
ａ＝ｐ-1    （ｍｏｄ  ｑ）
ｙ1 ＝Ｃ    （ｍｏｄ  ｐ）
ｙ2 ＝Ｃ    （ｍｏｄ  ｑ）
ｄ2 ＝ｄ    （ｍｏｄ  ｑ−１）
ｘ1 ＝ｙ1d1 （ｍｏｄ  ｐ）
ｘ2 ＝ｙ2d2 （ｍｏｄ  ｑ）  
Ｄ＝｛ａ（ｘ2 −ｘ1 ）（ｍｏｄ  ｑ）｝ｐ  ＋  ｘ1
次に、データ復号部４０２は、生成した復号文Ｄをデータ出力部４０４及びデータ再暗号部４０５へ出力する。
【００７５】
高速公開鍵演算部４０３は、データ入力部４０６から秘密鍵ｅ、素数ｐ、素数ｑを取得し公開鍵ｅ1 を演算する。一部の途中結果はデータ復号部４０２に送られ、復号演算に使用される。
高速公開鍵演算部４０３の秘密鍵取得部４１１は、データ入力部４０６から秘密鍵ｄ、素数ｐ及び素数ｑを取得する。
【００７６】
法演算部４１３は、素数ｐと素数ｑの乗算を行って整数ｎを算出する。
剰余演算部４１２は、秘密鍵ｄ、素数ｐ、素数ｑから
ｄ1 ＝ｄ  ｍｏｄ  （ｐ−１）の値を算出し、算出したｄ1 を保持する。
逆数演算部４１４は、ｐ−１を法とする剰余体上でのｄ1 の
逆数ｅ1 ＝ｄ1 -1  （ｍｏｄ  ｐ−１）を算出し、次に、算出した逆数ｅ1 を公開鍵として、データ再暗号部４０５へ出力する。また、ｄ1 をデータ復号部４０２へ出力する。
【００７７】
データ再暗号部４０５は、高速公開鍵演算部４０３により生成された公開鍵ｅ1 を用いて、データ復号部４０２により復号して生成された復号文Ｄを、再暗号化して再暗号文Ｃ’＝Ｄe1 （ｍｏｄ  ｎ）を生成し、生成した再暗号文Ｃ’をデータ出力部４０４へ出力する。
データ出力部４０４は、データ再暗号部４０５により得られた再暗号文Ｃ’と、データ入力部４０１により得られた暗号文Ｃとを比較し、再暗号文Ｃ’と暗号文Ｃとが一致する場合、データ復号部４０２により得られた復号文Ｄを外部へ出力する。再暗号文Ｃ’と暗号文Ｃとが一致しない場合には、復号文Ｄを出力しない。
【００７８】
（２）ＲＳＡ復号装置４００におけるＲＳＡ復号の動作
次に、ＲＳＡ復号装置４００におけるＲＳＡ復号の動作について、図１１に示すフローチャートを用いて説明する。
データ入力部４０１は、暗号文Ｃを取得し、データ入力部４０６は、秘密鍵ｄ、素数ｐ及び素数ｑを取得する（ステップＳ４０１）。
【００７９】
次に、高速公開鍵演算部４０３の秘密鍵取得部４１１は、秘密鍵ｄ、素数ｐ及び素数ｑを取得し、法演算部４１３は、素数ｐと素数ｑの乗算を行って整数ｎを算出し、剰余演算部４１２は、秘密鍵ｄ、素数ｐ、素数ｑから
ｄ1 ＝ｄ  ｍｏｄ  （ｐ−１）の値を算出し、ｄ1 を保持し、逆数演算部４１４は、公開鍵ｅ1 ＝ｄ1 -1  （ｍｏｄ  ｐ−１）を算出する（ステップＳ４０２）。
【００８０】
次に、データ復号部４０２は、中国剰余定理（ＣＲＴ）を用いて、暗号文Ｃを復号して復号文Ｄを生成する（ステップＳ４０３）。
データ再暗号部４０５は、高速公開鍵演算部４０３により生成された公開鍵ｅ1 を用いて、復号文Ｄを、再暗号化して再暗号文Ｃ’を生成する（ステップＳ４０４）。
データ出力部４０４は、再暗号文Ｃ’と暗号文Ｃとを比較し、再暗号文Ｃ’と暗号文Ｃとが一致する場合（ステップＳ４０５）、復号文Ｄを外部へ出力する（ステップＳ４０６）。再暗号文Ｃ’と暗号文Ｃとが一致しない場合には（ステップＳ４０５）、復号文Ｄを出力することなく、故障が発生したことを示すメッセージを表示又は出力する（ステップＳ４０７）。
【００８１】
（３）まとめ
以上の第２の実施の形態によれば、公開鍵ｅ1 の値を計算する逆数演算への入力が、従来の半分のビット長となる。逆元演算に必要なメモリ量は入力ビット長に比例し、処理時間は入力ビット長の２乗に比例するため、メモリ量、処理時間とも大幅に削減できることになる。さらに逆数演算の入力値となるｄ1 は中国剰余定理を用いた復号演算にも流用できるため、復号演算の処理時間も削減できる効果がある。
【００８２】
なお、この実施の形態では、ｄ1 を計算する剰余演算部を高速公開鍵演算部内に置き、その値をデータ復号部に送って利用する構成を示したが、剰余演算部をデータ復号部内に置いてｄ1 を計算し、その値を高速公開鍵演算部に送るという形態としても良い。その場合、図１１のフローチャートにおいて、上の高速公開鍵生成ステップ（ステップＳ４０２）と高速復号ステップ（ステップＳ４０３）の順序が逆転する。
【００８３】
３．第３の実施の形態
第２の実施の形態のＲＳＡ秘密通信システム２０の変形例としての、ＲＳＡ秘密通信システム３０について説明する。
（１）ＲＳＡ秘密通信システム３０の構成
ＲＳＡ秘密通信システム３０は、ＲＳＡ秘密通信システム２０と類似の構成を有している。ここでは、ＲＳＡ秘密通信システム２０との相違点を中心として説明する。
【００８４】
ＲＳＡ秘密通信システム３０は、図１２に示すように、ＲＳＡ暗号装置５００、ＲＳＡ復号装置４００ｂ、ＣＲＴ情報生成装置７００及びメモリカード６００ｂから構成されており、ＲＳＡ暗号装置５００及びＲＳＡ復号装置４００は、ネットワーク５０を介して接続されている。
メモリカード６００ｂは、メモリカード６００と同様の可搬型の半導体メモリであって、復号処理に用いる秘密鍵ｄ、素数ｐ及び素数ｑを予め記憶している。
【００８５】
ＣＲＴ情報生成装置７００は、メモリカード６００ｂから秘密鍵ｄ、素数ｐ及び素数ｑを読み出し、読み出した秘密鍵ｄ、素数ｐ及び素数ｑを用いて、
ｄ1 ＝ｄ  ｍｏｄ  （ｐ−１）及び
ｄ2 ＝ｄ  ｍｏｄ  （ｑ−１）を算出し、算出して得られたｄ1 及びｄ2 をメモリカード６００ｂへ書き込む。
【００８６】
ＲＳＡ復号装置４００ｂは、ＲＳＡ復号装置４００と同様の構成を有し、ＲＳＡ暗号装置５００により生成された暗号文
Ｃ＝Ｍe （ｍｏｄ  ｎ）を復号する装置であって、図１２に示すように、データ入力部４０１、ＬＳＩ部４２０ｂ、データ出力部４０４及びデータ入力部４０６ｂから構成されている。ＬＳＩ部４２０ｂは、ＬＳＩ部４２０と同様の構成を有するシステムＬＳＩであって、データ復号部４０２、高速公開鍵演算部４０３ｂ及びデータ再暗号部４０５を含んでいる。また、高速公開鍵演算部４０３ｂは、秘密鍵取得部４１１ｂ、法演算部４１３及び逆数演算部４１４を含んでいる。
【００８７】
データ入力部４０６ｂは、メモリカード６００ｂから復号処理に用いる秘密鍵ｄ、素数ｐ、素数ｑ、ｄ1 及びｄ2 を取得する。
データ復号部４０２ｂは、データ入力部４０６ｂにより取得された秘密鍵ｄ、素数ｐ、素数ｑ、ｄ1 及びｄ2 を用いて、暗号文Ｃを復号して復号文Ｄを生成する。具体的には、以下に示す演算を行う。
【００８８】
ａ＝ｐ-1    （ｍｏｄ  ｑ）
ｙ1 ＝Ｃ    （ｍｏｄ  ｐ）
ｙ2 ＝Ｃ    （ｍｏｄ  ｑ）
ｘ1 ＝ｙ1d1 （ｍｏｄ  ｐ）
ｘ2 ＝ｙ2d2 （ｍｏｄ  ｑ）  
Ｄ＝｛ａ（ｘ2 −ｘ1 ）（ｍｏｄ  ｑ）｝ｐ  ＋  ｘ1
次に、データ復号部４０２ｂは、生成した復号文Ｄをデータ出力部４０４及びデータ再暗号部４０５へ出力する。
【００８９】
ここで、データ復号部４０２ｂは、  ｄ2 ＝ｄ    （ｍｏｄ  ｑ−１）の演算を行わず、ｄ2 をメモリカード６００ｂから取得する点において、データ復号部４０２と異なる。
高速公開鍵演算部４０３ｂは、データ入力部４０６から秘密鍵ｅ、素数ｐ、素数ｑ、ｄ1 を取得し公開鍵ｅ1 を演算する。一部の途中結果はデータ復号部４０２に送られ、復号演算に使用される。
【００９０】
高速公開鍵演算部４０３ｂの秘密鍵取得部４１１ｂは、データ入力部４０６ｂから素数ｐ、素数ｑ、ｄ1 を取得する。
法演算部４１３は、素数ｐと素数ｑの乗算を行って整数ｎを算出する。
逆数演算部４１４は、ｐ−１を法とする剰余体上でのｄ1 の
逆数ｅ1 ＝ｄ1 -1  （ｍｏｄ  ｐ−１）を算出し、次に、算出した逆数ｅ1 を公開鍵として、データ再暗号部４０５へ出力する。
【００９１】
（２）ＲＳＡ秘密通信システム３０の動作
ＲＳＡ秘密通信システム３０の動作について、図１３に示すフローチャートを用いて説明する。
ＣＲＴ情報生成装置７００は、メモリカード６００ｂから秘密鍵ｄ、素数ｐ及び素数ｑを読み出し（ステップＳ４３１）、読み出した秘密鍵ｄ、素数ｐ及び素数ｑを用いて、ｄ1 ＝ｄ  ｍｏｄ  （ｐ−１）及びｄ2 ＝ｄ  ｍｏｄ  （ｑ−１）を算出し（ステップＳ４３２）、算出して得られたｄ1 及びｄ2 をメモリカード６００ｂへ書き込む（ステップＳ４３３）。
【００９２】
ＲＳＡ復号装置４００ｂのデータ入力部４０６ｂは、メモリカード６００ｂから復号処理に用いる秘密鍵ｄ、素数ｐ、素数ｑ、ｄ1 及びｄ2 を取得する（ステップＳ４３４）。
データ入力部４０１は、ＲＳＡ暗号装置５００から、ネットワーク５０を介して、暗号文Ｃを取得する（ステップＳ４３５）。
データ復号部４０２ｂは、データ入力部４０６ｂにより取得された秘密鍵ｄ、素数ｐ、素数ｑ、ｄ1 及びｄ2 を用いて、中国剰余定理により、暗号文Ｃを復号して復号文Ｄを生成する（ステップＳ４３６）。
【００９３】
次に、逆数演算部４１４は、逆数ｅ1 ＝ｄ1 -1  （ｍｏｄ  ｐ−１）を算出し（ステップＳ４３７）、データ再暗号部４０５は、公開鍵ｅ1 を用いて、復号文Ｄを、再暗号化して再暗号文Ｃ’を生成する（ステップＳ４３８）。
次に、
データ出力部４０４は、再暗号文Ｃ’と暗号文Ｃとを比較し、再暗号文Ｃ’と暗号文Ｃとが一致する場合（ステップＳ４３９）、復号文Ｄを外部へ出力する（ステップＳ４４０）。再暗号文Ｃ’と暗号文Ｃとが一致しない場合には（ステップＳ４３９）、復号文Ｄを出力することなく、故障が発生したことを示すメッセージを表示又は出力する（ステップＳ４４１）。
【００９４】
（３）まとめ
以上説明したように、第３の実施の形態では、ＲＳＡ復号装置は、従来の秘密鍵ではなく、あらかじめ中国剰余定理（ＣＲＴ）の演算用に計算された秘密鍵を外部から取得する。つまり、ｄ1 ＝ｄ  ｍｏｄ  （ｐ−１）、ｄ2 ＝ｄ  ｍｏｄ  （ｑ−１）、ｐ、ｑの値を取得する。なお、中国剰余定理の利用のしかたによって、外部から取得したデータのうちに、少なくともｄ1 が含まれていればよい。
【００９５】
データ復号部４０２と高速公開鍵演算部４０３ｂは、データ入力部４０６ｂにより取得した値を使用してそれぞれの処理を行う。従って、第２の実施の形態で示したように、データ復号部４０２と高速公開鍵演算部４０３の間で値ｄ1 を送受信する必要はない。
値ｄ1 が外部から取得されるため、高速公開鍵演算部４０３ｂにおいては、第２の実施の形態で示す剰余演算部４１２は必要ない。
【００９６】
なお、第３の実施の形態では、ｄ1 ＝ｄ  ｍｏｄ  （ｐ−１）、ｄ2 ＝ｄ  ｍｏｄ  （ｑ−１）、ｐ、ｑを外部から取得するとしているが、中国剰余定理の利用のしかたによって、外部から取得したデータのうちに、少なくともｄ1 が含まれていればよい。
また、図１３に示すフローチャートでは、高速復号ステップ（ステップＳ４３６）の後に、高速公開鍵取得ステップ（ステップＳ４３７）を実施するようにしてるいが、高速復号ステップと高速公開鍵取得ステップとは、どちらを先に行っても良い。つまり、高速公開鍵取得ステップ（ステップＳ４３７）の後に、高速復号ステップ（ステップＳ４３６）を実施してもよい。
【００９７】
第３の実施の形態によれば、実施の形態２の効果に加え、ｄ2 を求めるための剰余演算も不要となり、さらに処理時間を削減できるという優れた効果がある。
なお、以上の説明ではＲＳＡ復号装置における例で説明したが、ＲＳＡ署名生成装置についても同様に実施可能である。
またＲＳＡ復号装置、ＲＳＡ署名生成装置に限らず、ＲＳＡ秘密鍵からＲＳＡ公開鍵を取得する場合についても同様に実施可能である。
【００９８】
４．まとめ
本発明は、素数ｐ、ｑと、ｐ−１とｑ−１の最小公倍数ｌｃｍと互いに素で、ｐ−１＞ｅを満たす数ｅと、ｌｃｍを法とした剰余体においてｅの逆元であるｄと、ｐとｑの積ｎを用い、（ｅ，ｎ）を公開鍵、（ｄ，ｐ，ｑ）を秘密鍵として用いるＲＳＡ暗号において、前記秘密鍵（ｄ，ｐ，ｑ）から前記公開鍵（ｅ，ｎ）を復元するＲＳＡ公開鍵復元装置であって、
ＲＳＡ暗号の秘密鍵（ｄ，ｐ，ｑ）を入力する第一の秘密鍵入力手段と、
前記第一の秘密鍵入力手段により入力された秘密鍵のｄとｐを用い、ｐ−１を法としたｄの剰余であるｄｐ＝ｄ  ｍｏｄ  （ｐ−１）を求める第一の剰余手段と、
前記第一の剰余手段により得られたｄｐと前記第一の秘密鍵入力手段により入力されたｐを用い、ｐ−１を法とした剰余体におけるｄｐの逆元を求める第一の逆元演算手段と、
前記第一の秘密鍵入力手段により入力された秘密鍵のｐとｑの積をｎとし、前記第一の逆元演算手段により得られた逆元をｅとして（ｅ，ｎ）をＲＳＡ公開鍵として出力する公開鍵出力手段とを備える。
【００９９】
また、本発明は、素数ｐ、ｑと、ｐ−１とｑ−１の最小公倍数ｌｃｍと互いに素で、ｐ−１＞ｅを満たす数ｅと、ｌｃｍを法とした剰余体においてｅの逆元であるｄと、ｐとｑの積ｎを用い、（ｅ，ｎ）を公開鍵、（ｄ，ｐ，ｑ）を秘密鍵として用いるＲＳＡ暗号において、前記公開鍵により暗号化された暗号文から、元の平文を復号するＲＳＡ復号装置であって、
暗号文Ｃを入力する暗号文入力手段と、
ＲＳＡ暗号の秘密鍵（ｄ，ｐ，ｑ）を入力する第二の秘密鍵入力手段と、
前記第二の秘密鍵入力手段により入力された秘密鍵を用い、前記暗号文入力手段により入力された暗号文Ｃから平文Ｐを復号する復号手段と、
前記第二の秘密鍵入力手段により入力された秘密鍵のｄとｐを用い、ｐ−１を法としたｄの剰余であるｄｐ＝ｄ  ｍｏｄ  （ｐ−１）を求める第二の剰余手段と、
前記第二の剰余手段により得られたｄｐと前記第二の秘密鍵入力手段により入力されたｐを用い、ｐ−１を法とした剰余体におけるｄｐの逆元を求める第二の逆元演算手段と、
前記第二の秘密鍵入力手段により入力された秘密鍵のｐとｑの積をｎとし、前記第二の逆元演算手段により得られた逆元をｅとして（ｅ，ｎ）をＲＳＡ公開鍵として保持する第一の公開鍵復元手段と、
前記第一の公開鍵復元手段により保持された公開鍵を用い、前記復号手段により求められた平文Ｐから暗号文Ｃ’を求める暗号手段と、
前記暗号手段で求められた暗号文Ｃ’と前記暗号文入力手段で入力された暗号文Ｃとを比較する第一の検算手段と、
前記第一の検算手段で比較した結果が一致する時のみ平文Ｐを出力する復号結果出力手段とを備える。
【０１００】
ここで、前記復号手段の代わりに、前記第二の秘密鍵入力手段により入力された秘密鍵と、前記第二の剰余手段により得られたｄp を用い、中国剰余定理（ＣＲＴ）を用いたアルゴリズムで前記暗号文入力手段により入力された暗号文Ｃから平文Ｐを復号するＣＲＴ復号手段を備えるとしてもよい。
ここで、前記第二の秘密鍵入力手段と、前記第二の剰余手段の代わりに、あらかじめ少なくともｄp を含み中国剰余定理を用いたアルゴリズムに必要な値をＲＳＡ暗号の秘密鍵として入力する第三の秘密鍵入力手段を備え、
前記第二の逆元演算手段、前記第一の公開鍵復元手段、前記ＣＲＴ復号手段は、前記第三の秘密鍵入力手段により入力された値を用いるとしてもよい。
【０１０１】
ここで、さらに前記第一の検算手段で比較した結果が一致しない時、故障発生の旨を出力する第一のエラー出力手段を備えるとしてもよい。
また、本発明は、素数ｐ、ｑと、ｐ−１とｑ−１の最小公倍数ｌｃｍと互いに素で、ｐ−１＞ｅを満たす数ｅと、ｌｃｍを法とした剰余体においてｅの逆元であるｄと、ｐとｑの積ｎを用い、（ｅ，ｎ）を公開鍵、（ｄ，ｐ，ｑ）を秘密鍵として用いるＲＳＡ暗号において、平文から、署名文を生成するＲＳＡ署名生成装置であって、
平文Ｐを入力する平文入力手段と、
ＲＳＡ暗号の秘密鍵（ｄ，ｐ，ｑ）を入力する第四の秘密鍵入力手段と、
前記第四の秘密鍵入力手段により入力された秘密鍵を用い、前記平文入力手段により入力された平文Ｐから署名文Ｓを生成する署名生成手段と、
前記第四の秘密鍵入力手段により入力された秘密鍵のｄとｐを用い、ｐ−１を法としたｄの剰余であるｄｐ＝ｄ  ｍｏｄ  （ｐ−１）を求める第三の剰余手段と、
前記第三の剰余手段により得られたｄｐと前記第四の秘密鍵入力手段により入力されたｐを用い、ｐ−１を法とした剰余体におけるｄｐの逆元を求める第三の逆元演算手段と、
前記第四の秘密鍵入力手段により入力された秘密鍵のｐとｑの積をｎとし、前記第三の逆元演算手段により得られた逆元をｅとして（ｅ，ｎ）をＲＳＡ公開鍵として保持する第二の公開鍵復元手段と、
前記第二の公開鍵復元手段により保持された公開鍵を用い、前記署名生成手段により求められた署名文Ｓから平文Ｐ’を求める平文回復手段と、
前記平文回復手段で求められた平文Ｐ’と前記平文入力手段で入力された平文Ｐとを比較する第二の検算手段と、
前記第二の検算手段で比較した結果が一致する時のみ署名文Ｓを出力する署名結果出力手段とを備える。
【０１０２】
ここで、前記署名生成手段の代わりに、前記第四の秘密鍵入力手段により入力された秘密鍵と、前記第三の剰余手段により得られたｄｐを用い、中国剰余定理（ＣＲＴ）を用いたアルゴリズムで前記平文入力手段により入力された平文Ｐから署名文Ｓを生成するＣＲＴ署名生成手段を備えるとしてもよい。
ここで、前記第四の秘密鍵入力手段と、前記第三の剰余手段の代わりに、あらかじめ少なくともｄｐを含み中国剰余定理を用いたアルゴリズムに必要な値をＲＳＡ暗号の秘密鍵として入力する第五の秘密鍵入力手段を備え、
前記第三の逆元演算手段、前記第二の公開鍵復元手段、前記ＣＲＴ署名生成手段は、前記第五の秘密鍵入力手段により入力された値を用いるとしてもよい。
【０１０３】
ここで、さらに、前記第二の検算手段で比較した結果が一致しない時、故障発生の旨を出力する第二のエラー出力手段を備えるとしてもよい。
また、本発明は、素数ｐ、ｑと、ｐ−１とｑ−１の最小公倍数ｌｃｍと互いに素で、ｐ−１＞ｅを満たす数ｅと、ｌｃｍを法とした剰余体においてｅの逆元であるｄと、ｐとｑの積ｎを用い、（ｅ，ｎ）を公開鍵、（ｄ，ｐ，ｑ）を秘密鍵として用いるＲＳＡ暗号において、前記秘密鍵（ｄ，ｐ，ｑ）から前記公開鍵（ｅ，ｎ）を復元するＲＳＡ公開鍵復元方法であって、
ＲＳＡ暗号の秘密鍵（ｄ，ｐ，ｑ）を入力する第一の秘密鍵入力ステップと、
前記第一の秘密鍵入力ステップにより入力された秘密鍵のｄとｐを用い、ｐ−１を法としたｄの剰余であるｄｐ＝ｄ  ｍｏｄ  （ｐ−１）を求める第一の剰余ステップと、
前記第一の剰余ステップにより得られたｄｐと前記第一の秘密鍵入力ステップにより入力されたｐを用い、ｐ−１を法とした剰余体におけるｄｐの逆元を求める第一の逆元演算ステップと、
前記第一の秘密鍵入力ステップにより入力された秘密鍵のｐとｑの積をｎとし、前記第一の逆元演算ステップにより得られた逆元をｅとして（ｅ，ｎ）をＲＳＡ公開鍵として出力する公開鍵出力ステップとを含む。
【０１０４】
また、本発明は、素数ｐ、ｑと、ｐ−１とｑ−１の最小公倍数ｌｃｍと互いに素で、ｐ−１＞ｅを満たす数ｅと、ｌｃｍを法とした剰余体においてｅの逆元であるｄと、ｐとｑの積ｎを用い、（ｅ，ｎ）を公開鍵、（ｄ，ｐ，ｑ）を秘密鍵として用いるＲＳＡ暗号において、前記公開鍵により暗号化された暗号文から、元の平文を復号するＲＳＡ復号方法であって、
暗号文Ｃを入力する暗号文入力ステップと、
ＲＳＡ暗号の秘密鍵（ｄ，ｐ，ｑ）を入力する第二の秘密鍵入力ステップと、
前記第二の秘密鍵入力ステップにより入力された秘密鍵を用い、前記暗号文入力ステップにより入力された暗号文Ｃから平文Ｐを復号する復号ステップと、
前記第二の秘密鍵入力ステップにより入力された秘密鍵のｄとｐを用い、ｐ−１を法としたｄの剰余であるｄｐ＝ｄ  ｍｏｄ  （ｐ−１）を求める第二の剰余ステップと、
前記第二の剰余ステップにより得られたｄｐと前記第二の秘密鍵入力ステップにより入力されたｐを用い、ｐ−１を法とした剰余体におけるｄｐの逆元を求める第二の逆元演算ステップと、
前記第二の秘密鍵入力ステップにより入力された秘密鍵のｐとｑの積をｎとし、前記第二の逆元演算ステップにより得られた逆元をｅとして（ｅ，ｎ）をＲＳＡ公開鍵として保持する第一の公開鍵復元ステップと、
前記第一の公開鍵復元ステップにより保持された公開鍵を用い、前記復号ステップにより求められた平文Ｐから暗号文Ｃ’を求める暗号ステップと、
前記暗号ステップで求められた暗号文Ｃ’と前記暗号文入力ステップで入力された暗号文Ｃとを比較する第一の検算ステップと、
前記第一の検算ステップで比較した結果が一致する時のみ平文Ｐを出力する復号結果出力ステップとを含む。
【０１０５】
ここで、前記復号ステップの代わりに、前記第二の秘密鍵入力ステップにより入力された秘密鍵と、前記第二の剰余ステップにより得られたｄｐを用い、中国剰余定理（ＣＲＴ）を用いたアルゴリズムで前記暗号文入力ステップにより入力された暗号文Ｃから平文Ｐを復号するＣＲＴ復号ステップを備えるとしてもよい。
ここで、前記第二の秘密鍵入力ステップと、前記第二の剰余ステップの代わりに、あらかじめ少なくともｄｐを含み中国剰余定理を用いたアルゴリズムに必要な値をＲＳＡ暗号の秘密鍵として入力する第三の秘密鍵入力ステップを含み、
前記第二の逆元演算ステップ、前記第一の公開鍵復元ステップ、前記ＣＲＴ復号ステップは、前記第三の秘密鍵入力ステップにより入力された値を用いるとしてもよい。
【０１０６】
ここで、さらに、前記第一の検算ステップで比較した結果が一致しない時、故障発生の旨を出力する第一のエラー出力ステップを含むとしてもよい。
また、本発明は、素数ｐ、ｑと、ｐ−１とｑ−１の最小公倍数ｌｃｍと互いに素で、ｐ−１＞ｅを満たす数ｅと、ｌｃｍを法とした剰余体においてｅの逆元であるｄと、ｐとｑの積ｎを用い、（ｅ，ｎ）を公開鍵、（ｄ，ｐ，ｑ）を秘密鍵として用いるＲＳＡ暗号において、平文から、署名文を生成するＲＳＡ署名生成方法であって、
平文Ｐを入力する平文入力ステップと、
ＲＳＡ暗号の秘密鍵（ｄ，ｐ，ｑ）を入力する第四の秘密鍵入力ステップと、
前記第四の秘密鍵入力ステップにより入力された秘密鍵を用い、前記平文入力ステップにより入力された平文Ｐから署名文Ｓを生成する署名生成ステップと、
前記第四の秘密鍵入力ステップにより入力された秘密鍵のｄとｐを用い、ｐ−１を法としたｄの剰余であるｄｐ＝ｄ  ｍｏｄ  （ｐ−１）を求める第三の剰余ステップと、
前記第三の剰余ステップにより得られたｄｐと前記第四の秘密鍵入力ステップにより入力されたｐを用い、ｐ−１を法とした剰余体におけるｄｐの逆元を求める第三の逆元演算ステップと、
前記第四の秘密鍵入力ステップにより入力された秘密鍵のｐとｑの積をｎとし、前記第三の逆元演算ステップにより得られた逆元をｅとして（ｅ，ｎ）をＲＳＡ公開鍵として保持する第二の公開鍵復元ステップと、
前記第二の公開鍵復元ステップにより保持された公開鍵を用い、前記署名生成ステップにより求められた署名文Ｓから平文Ｐ’を求める平文回復ステップと、
前記平文回復ステップで求められた平文Ｐ’と前記平文入力ステップで入力された平文Ｐとを比較する第二の検算ステップと、
前記第二の検算ステップで比較した結果が一致する時のみ署名文Ｓを出力する署名結果出力ステップとを含む。
【０１０７】
ここで、前記署名生成ステップの代わりに、前記第四の秘密鍵入力ステップにより入力された秘密鍵と、前記第三の剰余ステップにより得られたｄｐを用い、中国剰余定理（ＣＲＴ）を用いたアルゴリズムで前記平文入力ステップにより入力された平文Ｐから署名文Ｓを生成するＣＲＴ署名生成ステップを含むとしてもよい。
ここで、前記第四の秘密鍵入力ステップと、前記第三の剰余ステップの代わりに、あらかじめ少なくともｄｐを含み中国剰余定理を用いたアルゴリズムに必要な値をＲＳＡ暗号の秘密鍵として入力する第五の秘密鍵入力ステップを備え、
前記第三の逆元演算ステップ、前記第二の公開鍵復元ステップ、前記ＣＲＴ署名生成ステップは、前記第五の秘密鍵入力ステップにより入力された値を用いるとしてもよい。
【０１０８】
ここで、さらに、前記第二の検算ステップで比較した結果が一致しない時、故障発生の旨を出力する第二のエラー出力ステップを含むとしてもよい。
また、本発明は、素数ｐ、ｑと、ｐ−１とｑ−１の最小公倍数ｌｃｍと互いに素で、ｐ−１＞ｅを満たす数ｅと、ｌｃｍを法とした剰余体においてｅの逆元であるｄと、ｐとｑの積ｎを用い、（ｅ，ｎ）を公開鍵、（ｄ，ｐ，ｑ）を秘密鍵として用いるＲＳＡ暗号において、前記秘密鍵（ｄ，ｐ，ｑ）から前記公開鍵（ｅ，ｎ）を復元するＲＳＡ公開鍵復元プログラムであって、
ＲＳＡ暗号の秘密鍵（ｄ，ｐ，ｑ）を入力する第一の秘密鍵入力ステップと、
前記第一の秘密鍵入力ステップにより入力された秘密鍵のｄとｐを用い、ｐ−１を法としたｄの剰余であるｄｐ＝ｄ  ｍｏｄ  （ｐ−１）を求める第一の剰余ステップと、
前記第一の剰余ステップにより得られたｄｐと前記第一の秘密鍵入力ステップにより入力されたｐを用い、ｐ−１を法とした剰余体におけるｄｐの逆元を求める第一の逆元演算ステップと、
前記第一の秘密鍵入力ステップにより入力された秘密鍵のｐとｑの積をｎとし、前記第一の逆元演算ステップにより得られた逆元をｅとして（ｅ，ｎ）をＲＳＡ公開鍵として出力する公開鍵出力ステップとを含む。
【０１０９】
また、本発明は、素数ｐ、ｑと、ｐ−１とｑ−１の最小公倍数ｌｃｍと互いに素で、ｐ−１＞ｅを満たす数ｅと、ｌｃｍを法とした剰余体においてｅの逆元であるｄと、ｐとｑの積ｎを用い、（ｅ，ｎ）を公開鍵、（ｄ，ｐ，ｑ）を秘密鍵として用いるＲＳＡ暗号において、前記公開鍵により暗号化された暗号文から、元の平文を復号するＲＳＡ復号プログラムであって、
暗号文Ｃを入力する暗号文入力ステップと、
ＲＳＡ暗号の秘密鍵（ｄ，ｐ，ｑ）を入力する第二の秘密鍵入力ステップと、
前記第二の秘密鍵入力ステップにより入力された秘密鍵を用い、前記暗号文入力ステップにより入力された暗号文Ｃから平文Ｐを復号する復号ステップと、
前記第二の秘密鍵入力ステップにより入力された秘密鍵のｄとｐを用い、ｐ−１を法としたｄの剰余であるｄｐ＝ｄ  ｍｏｄ  （ｐ−１）を求める第二の剰余ステップと、
前記第二の剰余ステップにより得られたｄｐと前記第二の秘密鍵入力ステップにより入力されたｐを用い、ｐ−１を法とした剰余体におけるｄｐの逆元を求める第二の逆元演算ステップと、
前記第二の秘密鍵入力ステップにより入力された秘密鍵のｐとｑの積をｎとし、前記第二の逆元演算ステップにより得られた逆元をｅとして（ｅ，ｎ）をＲＳＡ公開鍵として保持する第一の公開鍵復元ステップと、
前記第一の公開鍵復元ステップにより保持された公開鍵を用い、前記復号ステップにより求められた平文Ｐから暗号文Ｃ’を求める暗号ステップと、
前記暗号ステップで求められた暗号文Ｃ’と前記暗号文入力ステップで入力された暗号文Ｃとを比較する第一の検算ステップと、
前記第一の検算ステップで比較した結果が一致する時のみ平文Ｐを出力する復号結果出力ステップとを含む。
【０１１０】
また、前記復号ステップの代わりに、前記第二の秘密鍵入力ステップにより入力された秘密鍵と、前記第二の剰余ステップにより得られたｄｐを用い、中国剰余定理（ＣＲＴ）を用いたアルゴリズムで前記暗号文入力ステップにより入力された暗号文Ｃから平文Ｐを復号するＣＲＴ復号ステップを含むとしてもよい。
また、前記第二の秘密鍵入力ステップと、前記第二の剰余ステップの代わりに、あらかじめ少なくともｄｐを含み中国剰余定理を用いたアルゴリズムに必要な値をＲＳＡ暗号の秘密鍵として入力する第三の秘密鍵入力ステップを含み、
前記第二の逆元演算ステップ、前記第一の公開鍵復元ステップ、前記ＣＲＴ復号ステップは、前記第三の秘密鍵入力ステップにより入力された値を用いるとしてもよい。
【０１１１】
また、さらに、前記第一の検算ステップで比較した結果が一致しない時、故障発生の旨を出力する第一のエラー出力ステップを含むとしてもよい。
また、本発明は、素数ｐ、ｑと、ｐ−１とｑ−１の最小公倍数ｌｃｍと互いに素で、ｐ−１＞ｅを満たす数ｅと、ｌｃｍを法とした剰余体においてｅの逆元であるｄと、ｐとｑの積ｎを用い、（ｅ，ｎ）を公開鍵、（ｄ，ｐ，ｑ）を秘密鍵として用いるＲＳＡ暗号において、平文から、署名文を生成するＲＳＡ署名生成プログラムであって、
平文Ｐを入力する平文入力ステップと、
ＲＳＡ暗号の秘密鍵（ｄ，ｐ，ｑ）を入力する第四の秘密鍵入力ステップと、
前記第四の秘密鍵入力ステップにより入力された秘密鍵を用い、前記平文入力ステップにより入力された平文Ｐから署名文Ｓを生成する署名生成ステップと、
前記第四の秘密鍵入力ステップにより入力された秘密鍵のｄとｐを用い、ｐ−１を法としたｄの剰余であるｄｐ＝ｄ  ｍｏｄ  （ｐ−１）を求める第三の剰余ステップと、
前記第三の剰余ステップにより得られたｄｐと前記第四の秘密鍵入力ステップにより入力されたｐを用い、ｐ−１を法とした剰余体におけるｄｐの逆元を求める第三の逆元演算ステップと、
前記第四の秘密鍵入力ステップにより入力された秘密鍵のｐとｑの積をｎとし、前記第三の逆元演算ステップにより得られた逆元をｅとして（ｅ，ｎ）をＲＳＡ公開鍵として保持する第二の公開鍵復元ステップと、
前記第二の公開鍵復元ステップにより保持された公開鍵を用い、前記署名生成ステップにより求められた署名文Ｓから平文Ｐ’を求める平文回復ステップと、
前記平文回復ステップで求められた平文Ｐ’と前記平文入力ステップで入力された平文Ｐとを比較する第二の検算ステップと、
前記第二の検算ステップで比較した結果が一致する時のみ署名文Ｓを出力する署名結果出力ステップとを含む。
【０１１２】
ここで、前記署名生成ステップの代わりに、前記第四の秘密鍵入力ステップにより入力された秘密鍵と、前記第三の剰余ステップにより得られたｄｐを用い、中国剰余定理（ＣＲＴ）を用いたアルゴリズムで前記平文入力ステップにより入力された平文Ｐから署名文Ｓを生成するＣＲＴ署名生成ステップを含むとしてもよい。
ここで、前記第四の秘密鍵入力ステップと、前記第三の剰余ステップの代わりに、あらかじめ少なくともｄｐを含み中国剰余定理を用いたアルゴリズムに必要な値をＲＳＡ暗号の秘密鍵として入力する第五の秘密鍵入力ステップを備え、
前記第三の逆元演算ステップ、前記第二の公開鍵復元ステップ、前記ＣＲＴ署名生成ステップは、前記第五の秘密鍵入力ステップにより入力された値を用いるとしてもよい。
【０１１３】
ここで、さらに、前記第二の検算ステップで比較した結果が一致しない時、故障発生の旨を出力する第二のエラー出力ステップを含むとしてもよい。
以上説明したように、本発明にかかるＲＳＡ暗号処理装置は、故障利用攻撃が成立せず高速にＲＳＡ復号処理等ができる性質を有し、ＩＣカード等故障利用攻撃を受ける可能性がありながらもＲＳＡ暗号処理を行わなければならない装置等として有用である。
【０１１４】
本発明のＲＳＡ公開鍵復元装置によれば、公開鍵を求めるために逆元を取る被演算値が秘密鍵のおよそ半分のビット数の値となる。従って逆元演算に必要となるメモリ量、及び処理時間を大幅に短縮することができる。
また、本発明のＲＳＡ暗号処理装置によれば、公開鍵を求めるために逆元を取る被演算値が、秘密鍵のおよそ半分のビット数の値となる。従って逆元演算にかかる時間が従来より大幅に短縮され、その結果故障利用攻撃が成立しないＲＳＡ復号処理等にかかる時間を短縮することができる。
【０１１５】
さらに、本発明のＲＳＡ暗号処理装置によれば、公開鍵を求めるために逆元を取る被演算値が、そのまま中国剰余定理アルゴリズムを用いるＲＳＡ復号処理に使うことができる。従って故障利用攻撃が成立しないＲＳＡ復号処理等にかかる時間を短縮することができる。
なお、本発明のＲＳＡ公開鍵復元装置、ＲＳＡ暗号処理装置によれば、公開鍵の値が素数ｐに対してｐ−１以下と制限されるが、一般的にＲＳＡ暗号の公開鍵は小さく取るものであり問題とならない。
【０１１６】
５．その他の変形例
なお、本発明を上記の実施の形態に基づいて説明してきたが、本発明は、上記の実施の形態に限定されないのはもちろんである。以下のような場合も本発明に含まれる。
（１）第１の実施の形態において、ＩＣカード３００は、システムＬＳＩ３２０を含むとしているが、これには、限定されない。例えば、高速公開鍵演算部３０４が１個の大規模集積回路を構成するとしてもよい。
【０１１７】
また、第２の実施の形態において、ＲＳＡ復号装置４００は、ＬＳＩ部４２０を含むとしている、これには、限定されない。例えば、高速公開鍵演算部４０３が１個の大規模集積回路を構成するとしてもよい。
また、第３の実施の形態において、ＲＳＡ復号装置４００ｂは、ＬＳＩ部４２０ｂを含むとしている、これには、限定されない。例えば、高速公開鍵演算部４０３ｂが１個の大規模集積回路を構成するとしてもよい。
【０１１８】
（２）上記の各装置は、具体的には、マイクロプロセッサ、ＲＯＭ、ＲＡＭ、などから構成されるコンピュータシステムである。前記ＲＡＭには、コンピュータプログラムが記憶されている。前記マイクロプロセッサが、前記コンピュータプログラムに従って動作することにより、各装置は、その機能を達成する。
（３）本発明は、上記に示す方法であるとしてもよい。また、これらの方法をコンピュータにより実現するコンピュータプログラムであるとしてもよいし、前記コンピュータプログラムからなるデジタル信号であるとしてもよい。
【０１１９】
また、本発明は、前記コンピュータプログラム又は前記デジタル信号をコンピュータ読み取り可能な記録媒体、例えば、フレキシブルディスク、ハードディスク、ＣＤ―ＲＯＭ、ＭＯ、ＤＶＤ、ＤＶＤ−ＲＯＭ、ＤＶＤ−ＲＡＭ、ＢＤ（Ｂｌｕ−ｒａｙ  Ｄｉｓｃ）、半導体メモリなど、に記録したものとしてもよい。また、これらの記録媒体に記録されている前記コンピュータプログラム又は前記デジタル信号であるとしてもよい。
【０１２０】
また、本発明は、前記コンピュータプログラム又は前記デジタル信号を、電気通信回線、無線又は有線通信回線、インターネットを代表とするネットワーク、データ放送等を経由して伝送するものとしてもよい。
また、本発明は、マイクロプロセッサとメモリとを備えたコンピュータシステムであって、前記メモリは、上記コンピュータプログラムを記憶しており、前記マイクロプロセッサは、前記コンピュータプログラムに従って動作するとしてもよい。
【０１２１】
また、前記プログラム又は前記デジタル信号を前記記録媒体に記録して移送することにより、又は前記プログラム又は前記デジタル信号を前記ネットワーク等を経由して移送することにより、独立した他のコンピュータシステムにより実施するとしてもよい。
（４）上記実施の形態及び上記変形例をそれぞれ組み合わせるとしてもよい。
【産業上の利用可能性】
【０１２２】
本発明を構成する各装置は、情報を秘密に取り扱う必要があるあらゆる産業において、また相手を認証する必要があるあらゆる産業において、経営的に、また継続的及び反復的に使用することができる。また、本発明を構成する各装置は、電器機器製造産業において、経営的に、また継続的及び反復的に、製造し、販売することができる。
【図面の簡単な説明】
【０１２３】
【図１】図１は、秘密通信システム１０の構成を示すシステム構成図である。
【図２】図２は、レジスタ装置１００の構成を示すブロック図である。
【図３】図３は、ＩＣカード３００の構成を示すブロック図である。
【図４】図４は、レジスタ装置１００及びＩＣカード３００の全体の動作の概要を示すフローチャートである。
【図５】図５は、レジスタ装置１００によるＩＣカード３００の認証の動作を示すフローチャートである。図６へ続く。
【図６】図６は、レジスタ装置１００によるＩＣカード３００の認証の動作を示すフローチャートである。図５から続く。
【図７】図７は、ＩＣカード３００によるレジスタ装置１００の認証の動作を示すフローチャートである。
【図８】図８は、セッション鍵の受け渡しの動作を示すフローチャートである。
【図９】図９は、ポイントの秘密通信の動作を示すフローチャートである。
【図１０】図１０は、第２の実施の形態としてのＲＳＡ秘密通信システム２０の構成を示すシステム構成図である。
【図１１】図１１は、ＲＳＡ復号装置４００におけるＲＳＡ復号の動作を示すフローチャートである。
【図１２】図１２は、第３の実施の形態としてのＲＳＡ秘密通信システム３０の構成を示すシステム構成図である。
【図１３】図１３は、ＲＳＡ秘密通信システム３０の動作を示すフローチャートである。
【符号の説明】
【０１２４】
１０    秘密通信システム
２０    ＲＳＡ秘密通信システム
３０    ＲＳＡ秘密通信システム
５０    ネットワーク
１００    レジスタ装置
１０１    表示部
１０２    表示部
１０３    印字部
１０４    入力部
１０５    保管庫
１０６    情報記憶部
１０７    制御部
１０８    認証部
１０９    暗復号部
１１０    入出力部
１１１    鍵記憶部
２００    カードリーダ
３００    ＩＣカード
３０１    入出力部
３０２    認証部
３０３    復号部
３０４    高速公開鍵演算部
３０５    制御部
３０６    再暗号化部
３０７    情報記憶部
３０８    復号部
３０９    鍵記憶部
３１１    秘密鍵取得部
３１２    剰余演算部
３１３    逆数演算部
３１４    法演算部
３２０    システムＬＳＩ
４００    ＲＳＡ復号装置
４００ｂ  ＲＳＡ復号装置
４０１    データ入力部
４０２    データ復号部
４０２ｂ  データ復号部
４０３    高速公開鍵演算部
４０３ｂ  高速公開鍵演算部
４０４    データ出力部
４０５    データ再暗号部
４０６    データ入力部
４０６ｂ  データ入力部
４１１    秘密鍵取得部
４１１ｂ  秘密鍵取得部
４１２    剰余演算部
４１３    法演算部
４１４    逆数演算部
４２０    ＬＳＩ部
４２０ｂ  ＬＳＩ部
５００    ＲＳＡ暗号装置
６００    メモリカード
６００ｂ  メモリカード
７００    ＣＲＴ情報生成装置
【図１】
2005165290.tif 000003
【図２】
2005165290.tif 000004
【図３】
2005165290.tif 000005
【図４】
2005165290.tif 000006
【図５】
2005165290.tif 000007
【図６】
2005165290.tif 000008
【図７】
2005165290.tif 000009
【図８】
2005165290.tif 000010
【図９】
2005165290.tif 000011
【図１０】
2005165290.tif 000012
【図１１】
2005165290.tif 000013
【図１２】
2005165290.tif 000014
【図１３】
2005165290.tif 000015