素数算出装置、鍵発行システム及び素数算出方法
素数の算出を行う際に、簡単な管理により重複を避けながら素数を算出する素数算出装置を提供する。 素数算出装置は、既知の素数ｑと、素数の利用範囲における一意の管理情報を記憶している。素数算出装置は、管理情報を読み出し、読み出した管理情報に依存する攪乱情報Ｒを生成し、素数ｑを読み出し、読み出した素数ｑと生成した攪乱情報Ｒとを用いて、数Ｎ＝２×攪乱情報Ｒ×素数ｑ＋１により、素数候補Ｎを算出し、算出された素数候補Ｎが素数であるか否かを判定し、素数であると判定された場合に、算出された素数候補Ｎを素数として出力する。これにより、素数算出装置は、一意の管理情報から、重複を避けながら素数候補を算出することができる。
Notice: Undefined index: DEJ in /mnt/www/gzt_disp.php on line 298
【特許請求の範囲】
【請求項１】
既知の素数ｑより大きい素数候補Ｎを算出して素数判定する素数算出装置であって、
既知の素数ｑを記憶している素数記憶手段と、
素数の利用範囲における一意の管理情報を記憶している管理情報記憶手段と、
前記管理情報記憶手段から前記管理情報を読み出し、読み出した前記管理情報に依存する攪乱情報Ｒを生成する攪乱情報生成手段と、
前記素数記憶手段から前記素数ｑを読み出し、読み出した前記素数ｑ及び生成された前記攪乱情報Ｒを用いて、Ｎ＝２×攪乱情報Ｒ×素数ｑ＋１により、素数候補Ｎを算出する候補算出手段と、
算出された素数候補Ｎが素数であるか否かを判定する素数判定手段と、
素数であると判定される場合に、算出された素数候補Ｎを素数として出力する出力手段と
を備えることを特徴とする素数算出装置。
【請求項２】
前記攪乱情報生成手段は、
前記管理情報記憶手段から前記管理情報を読み出す読出部と、
乱数ｒを算出する乱数算出部と、
読み出した前記管理情報と生成した乱数ｒとを結合する結合部と、
前記管理情報と乱数ｒとの結合体に基づいて、攪乱情報Ｒを算出する演算部と
を含むことを特徴とする請求項１に記載の素数算出装置。
【請求項３】
前記演算部は、前記結合体に、単射の関数を施して攪乱情報Ｒを生成する
ことを特徴とする請求項２に記載の素数算出装置。
【請求項４】
前記単射の関数は、排他的論理和であり、
前記演算部は、所定の鍵情報を予め記憶しており、前記鍵情報と前記結合体とに排他的論理和を施して攪乱情報Ｒを生成する
ことを特徴とする請求項３に記載の素数算出装置。
【請求項５】
前記素数算出装置は、素数ｑの２倍のビット長を有する素数候補Ｎを算出し、
前記乱数算出部は、素数ｑのビット長から前記管理情報のビット長及び１を差し引いて得られるビット長の前記乱数ｒを算出する
ことを特徴とする請求項３に記載の素数算出装置。
【請求項６】
前記素数判定手段は、
前記素数候補Ｎに対して、２Ｎ−１＝１ ｍｏｄ Ｎを満たすか否かを判定する第１判定部と、
前記第１判定部により満たすと判定される場合に、さらに、素数候補Ｎ及び攪乱情報Ｒに対して、２２Ｒ≠１ ｍｏｄ Ｎを満たすか否かを判定し、満たすと判定する場合に、素数候補Ｎが素数であると決定する第２判定部と
を含むことを特徴とする請求項５に記載の素数算出装置。
【請求項７】
前記素数判定手段は、
前記素数候補Ｎに対して、２Ｎ−１＝１ ｍｏｄ Ｎを満たすか否かを判定する第１判定部と、
前記第１判定部により満たすと判定される場合に、さらに、素数候補Ｎ及び攪乱情報Ｒに対して、ＧＣＤ（２２Ｒ−１、Ｎ）＝１を満たすか否かを判定し、満たすと判定する場合に、素数候補Ｎが素数であると決定する第２判定部と
を含むことを特徴とする請求項５に記載の素数算出装置。
【請求項８】
前記素数算出装置は、さらに、
前記素数判定手段により素数であると判定されるまで、前記攪乱情報生成手段、前記候補算出手段及び前記素数判定手段に対して、攪乱情報Ｒの生成と、素数候補Ｎの算出と、前記判定とを繰り返すように制御する繰返制御手段
を含むことを特徴とする請求項１に記載の素数算出装置。
【請求項９】
前記素数算出装置は、さらに、
乱数Ｒ’を算出する次段乱数算出手段と、
出力された前記素数Ｎ及び生成された前記乱数Ｒ’を用いて、Ｎ’＝２×乱数Ｒ’×素数Ｎ＋１により、素数候補Ｎ’を算出する次段候補算出手段と、
算出された素数候補Ｎ’が素数であるか否かを判定する次段素数判定手段と、
素数であると判定される場合に、算出された素数候補Ｎ’を素数として出力する次段出力手段と、
前記次段素数判定手段により素数であると判定されるまで、前記次段乱数算出手段、前記次段候補算出手段及び前記次段素数判定手段に対して、乱数Ｒ’の生成と、素数候補Ｎ’の算出と、前記判定とを繰り返すように制御する次段繰返制御手段と
を含むことを特徴とする請求項８に記載の素数算出装置。
【請求項１０】
記素数算出装置は、さらに、
所定の検証値を記憶している次段情報記憶手段と、
乱数ｒ’を生成する次段乱数生成手段と、
前記管理情報に生成した前記乱数ｒ’を乗じて攪乱情報Ｒ’を算出し、Ｎ’＝２×攪乱情報Ｒ’×素数Ｎ＋検証値により、素数候補Ｎ’を算出する次段候補算出手段とを含み、
前記素数判定手段は、さらに、算出された素数候補Ｎ’が素数であるか否かを判定し、
前記出力手段は、さらに、素数候補Ｎ’が素数であると判定される場合に、算出された素数候補Ｎ’を素数として出力する
ことを特徴とする請求項８に記載の素数算出装置。
【請求項１１】
前記素数算出装置は、ＲＳＡ暗号の公開鍵及び秘密鍵を生成する鍵生成装置であり、
前記素数算出装置は、さらに、
算出された素数Ｎを用いて、ＲＳＡ暗号の公開鍵を生成する公開鍵生成手段と、
生成された公開鍵を用いて、ＲＳＡ暗号の秘密鍵を生成する秘密鍵生成手段とを含む
ことを特徴とする請求項８に記載の素数算出装置。
【請求項１２】
前記公開鍵生成手段は、前記繰返制御手段に対して、新たに素数Ｎ’が得られるように指示し、前記素数Ｎ及び新たに得られた素数Ｎ’を用いて、ｎ＝素数Ｎ×素数Ｎ’により、数ｎを算出し、乱数ｅを生成し、
算出された数ｎと生成された乱数ｅとの組が前記公開鍵であり、
前記秘密鍵生成手段は、ｅ×ｄ＝１ ｍｏｄ Ｌを満たすｄを算出し、
Ｌは、素数Ｎ−１と素数Ｎ’−１との最小公倍数であり、
算出されたｄが前記秘密鍵である
ことを特徴とする請求項１１に記載の素数算出装置。
【請求項１３】
前記素数算出装置は、端末装置に対して、ＲＳＡの秘密鍵及び公開鍵を生成し、発行する鍵発行サーバ装置であり、
前記素数算出装置は、さらに、
生成した前記秘密鍵を、端末装置に対して出力する鍵出力手段と、
生成した前記公開鍵を、公開する公開手段とを含む
ことを特徴とする請求項１１に記載の素数算出装置。
【請求項１４】
前記素数算出装置は、さらに、
前記端末装置を一意に識別する端末装置識別子を取得する識別子取得手段と、
取得した端末装置識別子を含む前記管理情報を生成する管理情報生成手段と、
生成した前記管理情報を前記管理情報記憶手段に書き込む書込手段とを
含むことを特徴とする請求項１３に記載の素数算出装置。
【請求項１５】
前記素数算出装置は、さらに、
鍵発行サーバ装置としての当該素数算出装置を一意に識別するサーバ識別子を予め記憶しているサーバ識別子記憶手段を含み、
前記管理情報生成手段は、さらに、前記サーバ識別子記憶手段から前記サーバ識別子を読み出し、読み出したサーバ識別子をさらに含む前記管理情報を生成する
ことを特徴とする請求項１４に記載の素数算出装置。
【請求項１６】
既知の素数より大きい素数を算出する素数算出装置であって、
既知の入力素数の２倍のビット長を有する出力素数を算出する素数算出手段と、
既知の素数初期値を記憶している素数記憶手段と、
前記素数算出手段に対して、算出を複数回繰り返すように制御する繰返制御手段とを備え、
前記繰返制御手段は、前記繰返しにおける初回の算出において、前記素数記憶手段に記憶されている素数初期値を、前記入力素数として、前記素数算出手段に与え、
前記繰返しの初回の算出以外の他の算出において、１つ前の回の算出においてされた出力素数を、当該他の算出における前記入力素数として、前記素数算出手段に与え、
前記複数回の算出のいずれか１の算出において、前記素数算出手段は、
素数の利用範囲における一意の管理情報を記憶している管理情報記憶部と、
前記管理情報記憶部から前記管理情報を読み出し、読み出した前記管理情報に依存する攪乱情報Ｒを生成する攪乱情報生成部と、
前記入力素数ｑを受け取り、受け取った前記入力素数ｑ及び生成された前記攪乱情報Ｒを用いて、Ｎ＝２×攪乱情報Ｒ×素数ｑ＋１により、素数候補Ｎを算出する候補算出部と、
算出された素数候補Ｎが素数であるか否かを判定する素数判定部と、
素数であると判定される場合に、算出された素数候補Ｎを出力素数として出力する出力部と、
前記素数判定部により素数であると判定されるまで、前記攪乱情報生成部、前記候補算出部及び前記素数判定部に対して、攪乱情報Ｒの生成と、素数候補Ｎの算出と、前記判定とを繰り返すように制御する繰返制御部とを含む
ことを特徴とする素数算出装置。
【請求項１７】
前記複数回の算出のうち、最終回の算出において、前記素数算出手段は、
所定の検証値を記憶している情報記憶部と、
乱数ｒ’を生成する乱数生成部と、
前記管理情報に生成した前記乱数ｒ’を乗じて攪乱情報Ｒ’を算出し、Ｎ’＝２×攪乱情報Ｒ’×１つ前の回において算出された出力素数＋検証値により、素数候補Ｎ’を算出する候補算出部と、
算出された素数候補Ｎ’が素数であるか否かを判定する素数判定部と、
素数候補Ｎ’が素数であると判定される場合に、算出された素数候補Ｎ’を素数として出力する出力部と、
前記素数判定部により素数であると判定されるまで、前記乱数生成部、前記候補算出部及び前記素数判定部に対して、乱数ｒ’の生成と、素数候補Ｎ’の算出と、前記判定とを繰り返すように制御する繰返制御部とを含む
ことを特徴とする請求項１６に記載の素数算出装置。
【請求項１８】
端末装置に対してＲＳＡの秘密鍵及び公開鍵を生成して発行する鍵発行サーバ装置と、前記端末装置とから構成される鍵発行システムであって、
鍵発行サーバ装置は、
既知の素数ｑより大きい素数Ｎを算出する素数算出手段と、
算出された素数Ｎを用いて、ＲＳＡ暗号の公開鍵を生成する公開鍵生成手段と、
生成された公開鍵を用いて、ＲＳＡ暗号の秘密鍵を生成する秘密鍵生成手段と、
生成された前記秘密鍵を、端末装置に対して出力する鍵出力手段と、
生成された前記公開鍵を公開する公開手段とを備え、
前記素数算出手段は、
既知の素数ｑを記憶している素数記憶部と、
一意の管理情報を記憶している管理情報記憶部と、
前記管理情報記憶部から前記管理情報を読み出し、読み出した前記管理情報に依存する攪乱情報Ｒを生成する攪乱情報生成部と、
前記素数記憶部から前記素数ｑを読み出し、読み出した前記素数ｑ及び生成された前記攪乱情報Ｒを用いて、Ｎ＝２×攪乱情報Ｒ×素数ｑ＋１により、素数候補Ｎを算出する候補算出部と、
算出された素数候補Ｎが素数であるか否かを判定する素数判定部と、
素数であると判定される場合に、算出された素数候補Ｎを素数として出力する出力部と、
前記素数判定部により素数であると判定されるまで、前記攪乱情報生成部、前記候補算出部及び前記素数判定部に対して、攪乱情報Ｒの生成と、素数候補Ｎの算出と、前記判定とを繰り返すように制御する繰返制御部とを含み、
前記端末装置は、
前記秘密鍵を受け取る受信手段と、
受信した秘密鍵を記憶する鍵記憶手段と
を備えることを特徴とする鍵発行システム。
【請求項１９】
前記鍵発行システムは、さらに、証明書発行サーバ装置を含み、
前記鍵出力手段は、前記公開鍵を前記証明書発行サーバ装置へ出力し、
前記証明書発行サーバ装置は、
当該証明書発行サーバ装置の秘密鍵を記憶している記憶手段と、
前記公開鍵を取得する取得手段と、
前記証明書発行サーバ装置の秘密鍵を用いて、前記公開鍵を含む公開鍵情報に、デジタル署名を施して、署名データを生成し、少なくとも前記公開鍵及び生成した前記署名データを含む公開鍵証明書を生成する証明書生成手段と、
生成した公開鍵証明書を鍵発行サーバ装置へ出力する出力手段とを備える
ことを特徴とする請求項１８に記載の鍵発行システム。
【請求項２０】
既知の素数ｑより大きい素数候補Ｎを算出して素数判定する素数算出装置で用いられる素数算出方法であって、
前記素数算出装置は、既知の素数ｑを記憶している素数記憶手段と、素数の利用範囲における一意の管理情報を記憶している管理情報記憶手段とを備え、
前記素数算出方法は、
前記管理情報記憶手段から前記管理情報を読み出し、読み出した前記管理情報に依存する攪乱情報Ｒを生成する乱数生成ステップと、
前記素数記憶手段から前記素数ｑを読み出し、読み出した前記素数ｑ及び生成された前記攪乱情報Ｒを用いて、Ｎ＝２×攪乱情報Ｒ×素数ｑ＋１により、素数候補Ｎを算出する候補算出ステップと、
算出された素数候補Ｎが素数であるか否かを判定する素数判定ステップと、
素数であると判定される場合に、算出された素数候補Ｎを素数として出力する出力ステップと
を含むことを特徴とする素数算出方法。
【請求項２１】
既知の素数ｑより大きい素数候補Ｎを算出して素数判定する素数算出装置で用いられる素数算出用のコンピュータプログラムであって、
前記素数算出装置は、既知の素数ｑを記憶している素数記憶手段と、素数の利用範囲における一意の管理情報を記憶している管理情報記憶手段とを備え、
前記素数算出用のコンピュータプログラムは、
前記管理情報記憶手段から前記管理情報を読み出し、読み出した前記管理情報に依存する攪乱情報Ｒを生成する乱数生成ステップと、
前記素数記憶手段から前記素数ｑを読み出し、読み出した前記素数ｑ及び生成された前記攪乱情報Ｒを用いて、Ｎ＝２×攪乱情報Ｒ×素数ｑ＋１により、素数候補Ｎを算出する候補算出ステップと、
算出された素数候補Ｎが素数であるか否かを判定する素数判定ステップと、
素数であると判定される場合に、算出された素数候補Ｎを素数として出力する出力ステップと
を含むことを特徴とするコンピュータプログラム。
【請求項２２】
前記コンピュータプログラムは、
コンピュータ読み取り可能な記録媒体に記録されている
ことを特徴とする請求項２１に記載のコンピュータプログラム。
【請求項２３】
前記コンピュータプログラムは、
搬送波に乗せられて送信される
ことを特徴とする請求項２１に記載のコンピュータプログラム。
【請求項１】
既知の素数ｑより大きい素数候補Ｎを算出して素数判定する素数算出装置であって、
既知の素数ｑを記憶している素数記憶手段と、
素数の利用範囲における一意の管理情報を記憶している管理情報記憶手段と、
前記管理情報記憶手段から前記管理情報を読み出し、読み出した前記管理情報に依存する攪乱情報Ｒを生成する攪乱情報生成手段と、
前記素数記憶手段から前記素数ｑを読み出し、読み出した前記素数ｑ及び生成された前記攪乱情報Ｒを用いて、Ｎ＝２×攪乱情報Ｒ×素数ｑ＋１により、素数候補Ｎを算出する候補算出手段と、
算出された素数候補Ｎが素数であるか否かを判定する素数判定手段と、
素数であると判定される場合に、算出された素数候補Ｎを素数として出力する出力手段と
を備えることを特徴とする素数算出装置。
【請求項２】
前記攪乱情報生成手段は、
前記管理情報記憶手段から前記管理情報を読み出す読出部と、
乱数ｒを算出する乱数算出部と、
読み出した前記管理情報と生成した乱数ｒとを結合する結合部と、
前記管理情報と乱数ｒとの結合体に基づいて、攪乱情報Ｒを算出する演算部と
を含むことを特徴とする請求項１に記載の素数算出装置。
【請求項３】
前記演算部は、前記結合体に、単射の関数を施して攪乱情報Ｒを生成する
ことを特徴とする請求項２に記載の素数算出装置。
【請求項４】
前記単射の関数は、排他的論理和であり、
前記演算部は、所定の鍵情報を予め記憶しており、前記鍵情報と前記結合体とに排他的論理和を施して攪乱情報Ｒを生成する
ことを特徴とする請求項３に記載の素数算出装置。
【請求項５】
前記素数算出装置は、素数ｑの２倍のビット長を有する素数候補Ｎを算出し、
前記乱数算出部は、素数ｑのビット長から前記管理情報のビット長及び１を差し引いて得られるビット長の前記乱数ｒを算出する
ことを特徴とする請求項３に記載の素数算出装置。
【請求項６】
前記素数判定手段は、
前記素数候補Ｎに対して、２Ｎ−１＝１ ｍｏｄ Ｎを満たすか否かを判定する第１判定部と、
前記第１判定部により満たすと判定される場合に、さらに、素数候補Ｎ及び攪乱情報Ｒに対して、２２Ｒ≠１ ｍｏｄ Ｎを満たすか否かを判定し、満たすと判定する場合に、素数候補Ｎが素数であると決定する第２判定部と
を含むことを特徴とする請求項５に記載の素数算出装置。
【請求項７】
前記素数判定手段は、
前記素数候補Ｎに対して、２Ｎ−１＝１ ｍｏｄ Ｎを満たすか否かを判定する第１判定部と、
前記第１判定部により満たすと判定される場合に、さらに、素数候補Ｎ及び攪乱情報Ｒに対して、ＧＣＤ（２２Ｒ−１、Ｎ）＝１を満たすか否かを判定し、満たすと判定する場合に、素数候補Ｎが素数であると決定する第２判定部と
を含むことを特徴とする請求項５に記載の素数算出装置。
【請求項８】
前記素数算出装置は、さらに、
前記素数判定手段により素数であると判定されるまで、前記攪乱情報生成手段、前記候補算出手段及び前記素数判定手段に対して、攪乱情報Ｒの生成と、素数候補Ｎの算出と、前記判定とを繰り返すように制御する繰返制御手段
を含むことを特徴とする請求項１に記載の素数算出装置。
【請求項９】
前記素数算出装置は、さらに、
乱数Ｒ’を算出する次段乱数算出手段と、
出力された前記素数Ｎ及び生成された前記乱数Ｒ’を用いて、Ｎ’＝２×乱数Ｒ’×素数Ｎ＋１により、素数候補Ｎ’を算出する次段候補算出手段と、
算出された素数候補Ｎ’が素数であるか否かを判定する次段素数判定手段と、
素数であると判定される場合に、算出された素数候補Ｎ’を素数として出力する次段出力手段と、
前記次段素数判定手段により素数であると判定されるまで、前記次段乱数算出手段、前記次段候補算出手段及び前記次段素数判定手段に対して、乱数Ｒ’の生成と、素数候補Ｎ’の算出と、前記判定とを繰り返すように制御する次段繰返制御手段と
を含むことを特徴とする請求項８に記載の素数算出装置。
【請求項１０】
記素数算出装置は、さらに、
所定の検証値を記憶している次段情報記憶手段と、
乱数ｒ’を生成する次段乱数生成手段と、
前記管理情報に生成した前記乱数ｒ’を乗じて攪乱情報Ｒ’を算出し、Ｎ’＝２×攪乱情報Ｒ’×素数Ｎ＋検証値により、素数候補Ｎ’を算出する次段候補算出手段とを含み、
前記素数判定手段は、さらに、算出された素数候補Ｎ’が素数であるか否かを判定し、
前記出力手段は、さらに、素数候補Ｎ’が素数であると判定される場合に、算出された素数候補Ｎ’を素数として出力する
ことを特徴とする請求項８に記載の素数算出装置。
【請求項１１】
前記素数算出装置は、ＲＳＡ暗号の公開鍵及び秘密鍵を生成する鍵生成装置であり、
前記素数算出装置は、さらに、
算出された素数Ｎを用いて、ＲＳＡ暗号の公開鍵を生成する公開鍵生成手段と、
生成された公開鍵を用いて、ＲＳＡ暗号の秘密鍵を生成する秘密鍵生成手段とを含む
ことを特徴とする請求項８に記載の素数算出装置。
【請求項１２】
前記公開鍵生成手段は、前記繰返制御手段に対して、新たに素数Ｎ’が得られるように指示し、前記素数Ｎ及び新たに得られた素数Ｎ’を用いて、ｎ＝素数Ｎ×素数Ｎ’により、数ｎを算出し、乱数ｅを生成し、
算出された数ｎと生成された乱数ｅとの組が前記公開鍵であり、
前記秘密鍵生成手段は、ｅ×ｄ＝１ ｍｏｄ Ｌを満たすｄを算出し、
Ｌは、素数Ｎ−１と素数Ｎ’−１との最小公倍数であり、
算出されたｄが前記秘密鍵である
ことを特徴とする請求項１１に記載の素数算出装置。
【請求項１３】
前記素数算出装置は、端末装置に対して、ＲＳＡの秘密鍵及び公開鍵を生成し、発行する鍵発行サーバ装置であり、
前記素数算出装置は、さらに、
生成した前記秘密鍵を、端末装置に対して出力する鍵出力手段と、
生成した前記公開鍵を、公開する公開手段とを含む
ことを特徴とする請求項１１に記載の素数算出装置。
【請求項１４】
前記素数算出装置は、さらに、
前記端末装置を一意に識別する端末装置識別子を取得する識別子取得手段と、
取得した端末装置識別子を含む前記管理情報を生成する管理情報生成手段と、
生成した前記管理情報を前記管理情報記憶手段に書き込む書込手段とを
含むことを特徴とする請求項１３に記載の素数算出装置。
【請求項１５】
前記素数算出装置は、さらに、
鍵発行サーバ装置としての当該素数算出装置を一意に識別するサーバ識別子を予め記憶しているサーバ識別子記憶手段を含み、
前記管理情報生成手段は、さらに、前記サーバ識別子記憶手段から前記サーバ識別子を読み出し、読み出したサーバ識別子をさらに含む前記管理情報を生成する
ことを特徴とする請求項１４に記載の素数算出装置。
【請求項１６】
既知の素数より大きい素数を算出する素数算出装置であって、
既知の入力素数の２倍のビット長を有する出力素数を算出する素数算出手段と、
既知の素数初期値を記憶している素数記憶手段と、
前記素数算出手段に対して、算出を複数回繰り返すように制御する繰返制御手段とを備え、
前記繰返制御手段は、前記繰返しにおける初回の算出において、前記素数記憶手段に記憶されている素数初期値を、前記入力素数として、前記素数算出手段に与え、
前記繰返しの初回の算出以外の他の算出において、１つ前の回の算出においてされた出力素数を、当該他の算出における前記入力素数として、前記素数算出手段に与え、
前記複数回の算出のいずれか１の算出において、前記素数算出手段は、
素数の利用範囲における一意の管理情報を記憶している管理情報記憶部と、
前記管理情報記憶部から前記管理情報を読み出し、読み出した前記管理情報に依存する攪乱情報Ｒを生成する攪乱情報生成部と、
前記入力素数ｑを受け取り、受け取った前記入力素数ｑ及び生成された前記攪乱情報Ｒを用いて、Ｎ＝２×攪乱情報Ｒ×素数ｑ＋１により、素数候補Ｎを算出する候補算出部と、
算出された素数候補Ｎが素数であるか否かを判定する素数判定部と、
素数であると判定される場合に、算出された素数候補Ｎを出力素数として出力する出力部と、
前記素数判定部により素数であると判定されるまで、前記攪乱情報生成部、前記候補算出部及び前記素数判定部に対して、攪乱情報Ｒの生成と、素数候補Ｎの算出と、前記判定とを繰り返すように制御する繰返制御部とを含む
ことを特徴とする素数算出装置。
【請求項１７】
前記複数回の算出のうち、最終回の算出において、前記素数算出手段は、
所定の検証値を記憶している情報記憶部と、
乱数ｒ’を生成する乱数生成部と、
前記管理情報に生成した前記乱数ｒ’を乗じて攪乱情報Ｒ’を算出し、Ｎ’＝２×攪乱情報Ｒ’×１つ前の回において算出された出力素数＋検証値により、素数候補Ｎ’を算出する候補算出部と、
算出された素数候補Ｎ’が素数であるか否かを判定する素数判定部と、
素数候補Ｎ’が素数であると判定される場合に、算出された素数候補Ｎ’を素数として出力する出力部と、
前記素数判定部により素数であると判定されるまで、前記乱数生成部、前記候補算出部及び前記素数判定部に対して、乱数ｒ’の生成と、素数候補Ｎ’の算出と、前記判定とを繰り返すように制御する繰返制御部とを含む
ことを特徴とする請求項１６に記載の素数算出装置。
【請求項１８】
端末装置に対してＲＳＡの秘密鍵及び公開鍵を生成して発行する鍵発行サーバ装置と、前記端末装置とから構成される鍵発行システムであって、
鍵発行サーバ装置は、
既知の素数ｑより大きい素数Ｎを算出する素数算出手段と、
算出された素数Ｎを用いて、ＲＳＡ暗号の公開鍵を生成する公開鍵生成手段と、
生成された公開鍵を用いて、ＲＳＡ暗号の秘密鍵を生成する秘密鍵生成手段と、
生成された前記秘密鍵を、端末装置に対して出力する鍵出力手段と、
生成された前記公開鍵を公開する公開手段とを備え、
前記素数算出手段は、
既知の素数ｑを記憶している素数記憶部と、
一意の管理情報を記憶している管理情報記憶部と、
前記管理情報記憶部から前記管理情報を読み出し、読み出した前記管理情報に依存する攪乱情報Ｒを生成する攪乱情報生成部と、
前記素数記憶部から前記素数ｑを読み出し、読み出した前記素数ｑ及び生成された前記攪乱情報Ｒを用いて、Ｎ＝２×攪乱情報Ｒ×素数ｑ＋１により、素数候補Ｎを算出する候補算出部と、
算出された素数候補Ｎが素数であるか否かを判定する素数判定部と、
素数であると判定される場合に、算出された素数候補Ｎを素数として出力する出力部と、
前記素数判定部により素数であると判定されるまで、前記攪乱情報生成部、前記候補算出部及び前記素数判定部に対して、攪乱情報Ｒの生成と、素数候補Ｎの算出と、前記判定とを繰り返すように制御する繰返制御部とを含み、
前記端末装置は、
前記秘密鍵を受け取る受信手段と、
受信した秘密鍵を記憶する鍵記憶手段と
を備えることを特徴とする鍵発行システム。
【請求項１９】
前記鍵発行システムは、さらに、証明書発行サーバ装置を含み、
前記鍵出力手段は、前記公開鍵を前記証明書発行サーバ装置へ出力し、
前記証明書発行サーバ装置は、
当該証明書発行サーバ装置の秘密鍵を記憶している記憶手段と、
前記公開鍵を取得する取得手段と、
前記証明書発行サーバ装置の秘密鍵を用いて、前記公開鍵を含む公開鍵情報に、デジタル署名を施して、署名データを生成し、少なくとも前記公開鍵及び生成した前記署名データを含む公開鍵証明書を生成する証明書生成手段と、
生成した公開鍵証明書を鍵発行サーバ装置へ出力する出力手段とを備える
ことを特徴とする請求項１８に記載の鍵発行システム。
【請求項２０】
既知の素数ｑより大きい素数候補Ｎを算出して素数判定する素数算出装置で用いられる素数算出方法であって、
前記素数算出装置は、既知の素数ｑを記憶している素数記憶手段と、素数の利用範囲における一意の管理情報を記憶している管理情報記憶手段とを備え、
前記素数算出方法は、
前記管理情報記憶手段から前記管理情報を読み出し、読み出した前記管理情報に依存する攪乱情報Ｒを生成する乱数生成ステップと、
前記素数記憶手段から前記素数ｑを読み出し、読み出した前記素数ｑ及び生成された前記攪乱情報Ｒを用いて、Ｎ＝２×攪乱情報Ｒ×素数ｑ＋１により、素数候補Ｎを算出する候補算出ステップと、
算出された素数候補Ｎが素数であるか否かを判定する素数判定ステップと、
素数であると判定される場合に、算出された素数候補Ｎを素数として出力する出力ステップと
を含むことを特徴とする素数算出方法。
【請求項２１】
既知の素数ｑより大きい素数候補Ｎを算出して素数判定する素数算出装置で用いられる素数算出用のコンピュータプログラムであって、
前記素数算出装置は、既知の素数ｑを記憶している素数記憶手段と、素数の利用範囲における一意の管理情報を記憶している管理情報記憶手段とを備え、
前記素数算出用のコンピュータプログラムは、
前記管理情報記憶手段から前記管理情報を読み出し、読み出した前記管理情報に依存する攪乱情報Ｒを生成する乱数生成ステップと、
前記素数記憶手段から前記素数ｑを読み出し、読み出した前記素数ｑ及び生成された前記攪乱情報Ｒを用いて、Ｎ＝２×攪乱情報Ｒ×素数ｑ＋１により、素数候補Ｎを算出する候補算出ステップと、
算出された素数候補Ｎが素数であるか否かを判定する素数判定ステップと、
素数であると判定される場合に、算出された素数候補Ｎを素数として出力する出力ステップと
を含むことを特徴とするコンピュータプログラム。
【請求項２２】
前記コンピュータプログラムは、
コンピュータ読み取り可能な記録媒体に記録されている
ことを特徴とする請求項２１に記載のコンピュータプログラム。
【請求項２３】
前記コンピュータプログラムは、
搬送波に乗せられて送信される
ことを特徴とする請求項２１に記載のコンピュータプログラム。
【国際公開番号】ＷＯ２００５／０６４８４３
【国際公開日】平成１７年７月１４日（２００５．７．１４）
【発行日】平成１９年１２月２０日（２００７．１２．２０）
【国際特許分類】
【出願番号】特願２００５−５１６５８９（Ｐ２００５−５１６５８９）
【国際出願番号】ＰＣＴ／ＪＰ２００４／０１９１０８
【国際出願日】平成１６年１２月２１日（２００４．１２．２１）
【出願人】（０００００５８２１）松下電器産業株式会社 (73,050)
【Ｆターム（参考）】
【国際公開日】平成１７年７月１４日（２００５．７．１４）
【発行日】平成１９年１２月２０日（２００７．１２．２０）
【国際特許分類】
【国際出願番号】ＰＣＴ／ＪＰ２００４／０１９１０８
【国際出願日】平成１６年１２月２１日（２００４．１２．２１）
【出願人】（０００００５８２１）松下電器産業株式会社 (73,050)
【Ｆターム（参考）】
[ Back to top ]