【手続補正書】
【提出日】平成19年8月7日(2007.8.7)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ＲＳＡ暗号方式の秘密鍵ｄから新たに公開鍵ｅ’を生成するＲＳＡ公開鍵生成装置であって、
素数ｑは、素数ｐと異なり、公開鍵ｅは、ｐ−１とｑ−１との最小公倍数ｌｃｍと互いに素で、ｐ−１＞ｅを満たし、前記秘密鍵ｄは、ｌｃｍを法とする剰余体において公開鍵ｅの逆元であり、
前記ＲＳＡ公開鍵生成装置は、
ＲＳＡ暗号の秘密鍵ｄ及び素数ｐを取得する取得手段と、
取得された秘密鍵ｄと素数ｐを用い、素数ｐ−１を法とする前記秘密鍵ｄの剰余ｄ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 を用いて、中国剰余定理により、前記平文ＭにＲＳＡ署名を施して署名文Ｓを生成する
ことを特徴とする請求項１１に記載のＲＳＡ署名装置。
【請求項１３】
前記署名生成手段は、
ａ＝ｐ-1    （ｍｏｄ  ｑ）
ｙ1 ＝Ｍ    （ｍｏｄ  ｐ）
ｙ2 ＝Ｍ    （ｍｏｄ  ｑ）
ｄ2 ＝ｄ    （ｍｏｄ  ｑ−１）
ｘ1 ＝ｙ1dp （ｍｏｄ  ｐ）
ｘ2 ＝ｙ2d2 （ｍｏｄ  ｑ）  
Ｓ＝｛ａ（ｘ2 −ｘ1 ）（ｍｏｄ  ｑ）｝ｐ  ＋  ｘ1
の演算により、署名文Ｓを生成する
ことを特徴とする請求項１２に記載のＲＳＡ署名装置。
【請求項１４】
前記出力手段は、一致しないと判断される場合に、故障発生の旨を示すメッセージを出力する
ことを特徴とする請求項１１に記載のＲＳＡ署名装置。
【請求項１５】
前記署名生成手段、前記回復手段及び前記比較手段は、１個の集積回路から構成されている
ことを特徴とする請求項１１に記載のＲＳＡ署名装置。
【請求項１６】
ＲＳＡ署名方式により平文に署名を施して署名文を生成するＲＳＡ署名装置を構成する集積回路であって、
前記ＲＳＡ署名装置は、
請求項１のＲＳＡ公開鍵生成装置から、公開鍵ｅ' を取得する公開鍵取得手段と、
比較手段により、一致すると判断される場合に、生成された前記署名文Ｓを出力する出力手段とを備え、
前記集積回路は、
秘密鍵ｄを用いて、平文ＭにＲＳＡ署名を施して署名文Ｓを生成する署名生成手段と、
取得した公開鍵ｅ’を用いて、署名文Ｓに、ＲＳＡ署名回復を施して、復号文Ｄを生成する回復手段と、
平文Ｍと、生成した復号文Ｄとを比較し、一致するか否かを判断する比較手段と
を備えることを特徴とする集積回路。
【請求項１７】
ＲＳＡ暗号方式の秘密鍵ｄから新たに公開鍵ｅ’を生成するＲＳＡ公開鍵生成装置で用いられるＲＳＡ公開鍵生成方法であって、
素数ｑは、素数ｐと異なり、公開鍵ｅは、ｐ−１とｑ−１との最小公倍数ｌｃｍと互いに素で、ｐ−１＞ｅを満たし、前記秘密鍵ｄは、ｌｃｍを法とする剰余体において公開鍵ｅの逆元であり、
前記ＲＳＡ公開鍵生成方法は、
ＲＳＡ暗号の秘密鍵ｄ及び素数ｐを取得する取得ステップと、
取得された秘密鍵ｄと素数ｐを用い、素数ｐ−１を法とする前記秘密鍵ｄの剰余ｄp を算出する剰余演算ステップと、
算出された前記剰余ｄp 及び取得された前記素数ｐを用い、素数ｐ−１を法とする剰余体における前記剰余ｄp の逆元を算出し、算出した逆元を新たな公開鍵ｅ' とする逆元演算ステップと
を含むことを特徴とするＲＳＡ公開鍵生成方法。
【請求項１８】
ＲＳＡ暗号方式の秘密鍵ｄから新たに公開鍵ｅ’を生成するＲＳＡ公開鍵生成装置で用いられるＲＳＡ公開鍵生成用のコンピュータプログラムであって、
素数ｑは、素数ｐと異なり、公開鍵ｅは、ｐ−１とｑ−１との最小公倍数ｌｃｍと互いに素で、ｐ−１＞ｅを満たし、前記秘密鍵ｄは、ｌｃｍを法とする剰余体において公開鍵ｅの逆元であり、
ＲＳＡ暗号の秘密鍵ｄ及び素数ｐを取得する取得ステップと、
取得された秘密鍵ｄと素数ｐを用い、素数ｐ−１を法とする前記秘密鍵ｄの剰余ｄp を算出する剰余演算ステップと、
算出された前記剰余ｄp 及び取得された前記素数ｐを用い、素数ｐ−１を法とする剰余体における前記剰余ｄp の逆元を算出し、算出した逆元を新たな公開鍵ｅ' とする逆元演算ステップと
を含むことを特徴とするコンピュータプログラム。
【請求項１９】
ＲＳＡ暗号方式により生成された暗号文を復号するＲＳＡ復号装置で用いられるＲＳＡ復号方法であって、
請求項１のＲＳＡ公開鍵生成装置から、公開鍵ｅ' を取得する公開鍵取得ステップと、
前記公開鍵ｅを用いて、ＲＳＡ暗号方式により平文ＭがＲＳＡ暗号化されて生成された暗号文Ｃを取得する暗号文取得ステップと、
秘密鍵ｄを用いて、取得した前記暗号文ＣをＲＳＡ復号して復号文Ｄを生成するＲＳＡ復号ステップと、
取得した公開鍵ｅ' を用いて、生成された復号文ＤをＲＳＡ暗号化して再暗号文Ｃ’を生成する再暗号化ステップと、
取得した暗号文Ｃと生成した再暗号文Ｃ’とを比較し、一致するか否かを判断する比較ステップと、
一致すると判断される場合に、生成された前記復号文Ｄを出力する出力ステップと
を含むことを特徴とするＲＳＡ復号方法。
【請求項２０】
ＲＳＡ暗号方式により生成された暗号文を復号するＲＳＡ復号装置で用いられるＲＳＡ復号用のコンピュータプログラムであって、
請求項１のＲＳＡ公開鍵生成装置から、公開鍵ｅ' を取得する公開鍵取得ステップと、
前記公開鍵ｅを用いて、ＲＳＡ暗号方式により平文ＭがＲＳＡ暗号化されて生成された暗号文Ｃを取得する暗号文取得ステップと、
秘密鍵ｄを用いて、取得した前記暗号文ＣをＲＳＡ復号して復号文Ｄを生成するＲＳＡ復号ステップと、
取得した公開鍵ｅ' を用いて、生成された復号文ＤをＲＳＡ暗号化して再暗号文Ｃ’を生成する再暗号化ステップと、
取得した暗号文Ｃと生成した再暗号文Ｃ’とを比較し、一致するか否かを判断する比較ステップと、
一致すると判断される場合に、生成された前記復号文Ｄを出力する出力ステップと
を含むことを特徴とするコンピュータプログラム。
【請求項２１】
ＲＳＡ署名方式により平文に署名を施して署名文を生成するＲＳＡ署名方法であって、
請求項１のＲＳＡ公開鍵生成装置から、公開鍵ｅ' を取得する公開鍵取得ステップと、
秘密鍵ｄを用いて、平文ＭにＲＳＡ署名を施して署名文Ｓを生成する署名生成ステップと、
取得した公開鍵ｅ’を用いて、署名文Ｓに、ＲＳＡ署名回復を施して、復号文Ｄを生成する回復ステップと、
平文Ｍと、生成した復号文Ｄとを比較し、一致するか否かを判断する比較ステップと、
一致すると判断される場合に、生成された前記署名文Ｓを出力する出力ステップと
を含むことを特徴とするＲＳＡ署名方法。
【請求項２２】
ＲＳＡ署名方式により平文に署名を施して署名文を生成するＲＳＡ署名用のコンピュータプログラムであって、
請求項１のＲＳＡ公開鍵生成装置から、公開鍵ｅ' を取得する公開鍵取得ステップと、
秘密鍵ｄを用いて、平文ＭにＲＳＡ署名を施して署名文Ｓを生成する署名生成ステップと、
取得した公開鍵ｅ’を用いて、署名文Ｓに、ＲＳＡ署名回復を施して、復号文Ｄを生成する回復ステップと、
平文Ｍと、生成した復号文Ｄとを比較し、一致するか否かを判断する比較ステップと、
一致すると判断される場合に、生成された前記署名文Ｓを出力する出力ステップと
を含むことを特徴とするコンピュータプログラム。