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