(57)【要約】【課題】耐タンパ性を有する媒体を必要とすることなく、かつ、秘密鍵の漏洩を好適に抑制可能な暗号鍵生成装置及びプログラムを提供する。【解決手段】暗号鍵生成装置１００は、生体情報読取部２０により読み取った第１生体情報Ｄ１及び第２生体情報Ｄ２を数値化した数値Ｐ及び数値Ｑを起点として、公開鍵と整合する秘密鍵を構成する数値Ｄを算出するために必要な素数ｐ、ｑを探索する。【選択図】図２
2015188148.tif 000002
【特許請求の範囲】
【請求項１】
利用者の生体情報を読み取る読み取り手段と、
前記生体情報を数値化することで所定ビットの数値を生成する数値化手段と、
前記所定ビットの数値を起点として素数の探索を行う素数探索手段と、
前記素数探索手段が探索した素数に基づき、公開鍵暗号に用いる秘密鍵を生成する鍵生成手段と、
を有することを特徴とする暗号鍵生成装置。
【請求項２】
前記利用者の生体情報に基づき生成した公開鍵を記憶する記憶手段と、
前記素数探索手段が探索した素数が前記公開鍵と整合性があるか否か判定する判定手段とをさらに備え、
前記鍵生成手段は、前記公開鍵と整合性があると判定された素数に基づき、前記秘密鍵を生成することを特徴とする請求項１に記載の暗号鍵生成装置。
【請求項３】
前記素数探索手段は、前記所定ビット数の数値を起点として、当該数値が大きくなる方向に前記素数の探索を行う第１探索処理と、前記所定ビット数の数値を起点として、当該数値が小さくなる方向に前記素数の探索を行う第２探索処理とを行うことを特徴とする請求項１または２に記載の暗号鍵生成装置。
【請求項４】
前記素数探索手段は、前記第１探索処理と前記第２探索処理との並列処理を行うことを特徴とする請求項３に記載の暗号鍵生成装置。
【請求項５】
前記読み取り手段は、前記利用者の異なる２つの生体情報を読み取り、
前記素数探索手段は、前記生体情報の各々に対応する前記所定ビットの数値をそれぞれ基準として２つの異なる素数の探索を行い、
前記鍵生成手段は、前記素数探索手段が探索した素数に基づき、ＲＳＡ暗号に用いる秘密鍵を生成することを特徴とする請求項１〜４のいずれか一項に記載の暗号鍵生成装置。
【請求項６】
請求項１〜５のいずれか一項に記載の暗号鍵生成装置としてコンピュータを機能させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号鍵を生成する技術に関する。
【背景技術】
【０００２】
従来から、ＲＳＡ暗号などの公開鍵認証基盤（ＰＫＩ：Ｐｕｂｌｉｃ  Ｋｅｙ  Ｉｎｆｒａｓｔｒｕｃｔｕｒｅ）を利用した暗号通信技術が知られている。例えば、特許文献１には、生体情報に基づいて生成された公開鍵及び秘密鍵を用いて、公開鍵暗号による暗号通信を行う技術が開示されている。その他、特許文献２、３には、暗号鍵に用いる素数を算出する方法が開示されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００６−２４６３６０号公報
【特許文献２】特許第４６６８７９６号
【特許文献３】特許第４６６８７９５号
【非特許文献】
【０００４】
【非特許文献１】岡本龍明・太田和夫共編、“暗号・ゼロ知識証明・数論”、共立出版、１９９５
【発明の概要】
【発明が解決しようとする課題】
【０００５】
公開鍵認証基盤において、秘密鍵が主体者以外の第３者への漏洩を防ぐため、ＩＣカード等の耐タンパ性を有する媒体を秘密鍵の格納媒体として用いた場合、ＩＣカードの発行やＩＣカードのリーダライタの設置が必要となり、コスト高の要因となる。また、特許文献１に記載の技術では、生体情報に基づいて秘密鍵を生成する際に、乱数を生成し、その乱数をＩＣカード等の耐タンパ媒体に記憶させておく必要があった。そこで、本発明は、耐タンパ性を有する媒体を必要とすることなく、かつ、秘密鍵の漏洩を好適に抑制可能な暗号鍵生成装置及びプログラムを提供することを主な課題とする。
【課題を解決するための手段】
【０００６】
本発明の１つの観点では、暗号鍵生成装置は、利用者の生体情報を読み取る読み取り手段と、前記生体情報を数値化することで所定ビットの数値を生成する数値化手段と、前記所定ビットの数値を起点として素数の探索を行う素数探索手段と、前記素数探索手段が探索した素数に基づき、公開鍵暗号に用いる秘密鍵を生成する鍵生成手段と、を有する。
【０００７】
上記の暗号鍵生成装置は、読み取り手段と、数値化手段と、素数探索手段と、鍵生成手段とを有する。読み取り手段は、利用者の生体情報を読み取る。数値化手段は、読み取り手段が読み取った生体情報を数値化することで所定ビットの数値を生成する。素数探索手段は、数値化手段が生成した所定ビットの数値を起点として素数の探索を行う。鍵生成手段は、素数探索手段が探索した素数に基づき、公開鍵暗号に用いる秘密鍵を生成する。この態様では、暗号鍵生成装置は、利用者から読み取った生体情報を所定ビットに数値化し、当該数値に基づき、秘密鍵の生成に必要な素数の探索を行う。これにより、暗号鍵生成装置は、耐タンパ性を有する媒体を必要とすることなく、かつ、秘密鍵の漏洩が発生することなく、利用者の身体的な特徴に基づき、好適に秘密鍵を生成し、公開鍵暗号を用いた通信を行うことができる。
【０００８】
上記暗号鍵生成装置の一態様では、暗号鍵生成装置は、前記利用者の生体情報に基づき生成した公開鍵を記憶する記憶手段と、前記素数探索手段が探索した素数が前記公開鍵と整合性があるか否か判定する判定手段とをさらに備え、前記鍵生成手段は、前記公開鍵と整合性があると判定された素数に基づき、前記秘密鍵を生成する。この態様により、暗号鍵生成装置は、既に記憶された公開鍵に対応する秘密鍵を好適に生成することができる。
【０００９】
上記暗号鍵生成装置の他の一態様では、前記素数探索手段は、前記所定ビット数の数値を起点として、当該数値が大きくなる方向に前記素数の探索を行う第１探索処理と、前記所定ビット数の数値を起点として、当該数値が小さくなる方向に前記素数の探索を行う第２探索処理とを行う。この態様により、暗号鍵生成装置は、好適に、秘密鍵の生成に必要な素数を探索することができる。
【００１０】
上記暗号鍵生成装置の他の一態様では、前記素数探索手段は、前記第１探索処理と前記第２探索処理との並列処理を行う。これにより、暗号鍵生成装置は、秘密鍵の生成に必要な素数を高速に探索することができる。
【００１１】
上記暗号鍵生成装置の他の一態様では、前記読み取り手段は、前記利用者の異なる２つの生体情報を読み取り、前記素数探索手段は、前記生体情報の各々に対応する前記所定ビットの数値をそれぞれ基準として２つの異なる素数の探索を行い、前記鍵生成手段は、前記素数探索手段が探索した素数に基づき、ＲＳＡ暗号に用いる秘密鍵を生成する。この態様により、暗号鍵生成装置は、耐タンパ性を有する媒体を必要とすることなく、ＲＳＡ暗号の秘密鍵を好適に生成することができる。
【００１２】
本発明のさらに別の観点では、プログラムは、上記いずれか記載の暗号鍵生成装置としてコンピュータを機能させる。このプログラムをコンピュータにインストールして機能させることで、本発明に係る暗号鍵生成装置を構成させることができる。なお、「コンピュータ」は、プログラムに従って演算を行う機械（回路も含む）の総称であり、ウェアラブルデバイスなどの携帯端末であってもよい。
【発明の効果】
【００１３】
本発明に係る暗号鍵生成装置によれば、耐タンパ性を有する媒体を必要とすることなく、かつ、秘密鍵の漏洩が発生することなく、利用者の身体的な特徴に基づき、好適に秘密鍵を生成することができる。
【図面の簡単な説明】
【００１４】
【図１】暗号鍵生成装置の構成例を示す。
【図２】秘密鍵生成処理の概要を示すフローチャートである。
【図３】第１素数判定処理を示すフローチャートである。
【図４】第１素数判定処理でのインクリメンタルサーチのフローチャートである。
【図５】第１素数判定処理でのデクリメンタルサーチのフローチャートである。
【図６】第２素数判定処理を示すフローチャートである。
【図７】第２素数判定処理でのインクリメンタルサーチのフローチャートである。
【図８】第２素数判定処理でのデクリメンタルサーチのフローチャートである。
【発明を実施するための形態】
【００１５】
以下、図面を参照しながら、本発明を実施するのに好適な実施形態について説明する。以下では、公開鍵認証基盤において、耐タンパ性を有する媒体を用いることなく、生体情報に基づき、公開鍵と整合する秘密鍵を生成する暗号鍵生成装置について説明する。以下では、代表例として、ＲＳＡ暗号を利用する場合について説明し、ＲＳＡ暗号での公開鍵となる数値の組を（Ｅ、Ｎ）、秘密鍵となる数値の組を（Ｄ、Ｎ）とする。
【００１６】
［暗号鍵生成装置の構成］
図１は、本実施形態に係る暗号鍵生成装置１００の構成例を示す。暗号鍵生成装置１００は、ディスプレイなどの表示部１１と、入力部１２と、記憶部１３と、データ通信を行う通信部１４と、制御部１５とを備える。これらの各要素は、バスライン１０を介して相互に接続されている。
【００１７】
入力部１２は、生体情報読取部２０を有する。生体情報読取部２０は、制御部１５の制御に基づき利用者の生体情報を読み取り、読み取った生体情報を制御部１５に出力する。生体情報は、ユーザ固有の身体的特徴を示す情報であり、例えば、指紋、網膜、虹彩、指静脈、掌静脈などを表す情報である。本実施形態では、生体情報読取部２０は、秘密鍵を構成する数値Ｄの生成に必要な２つの素数「ｐ」、「ｑ」（Ｎ＝ｐ×ｑ）のそれぞれに対応する生体情報（それぞれ「第１生体情報Ｄ１」及び「第２生体情報Ｄ２」と呼ぶ。）を生成する。この場合、生体情報読取部２０は、例えば、利用者の左半身の身体的特徴を表す生体情報（例えば左手の指紋データ）を第１生体情報Ｄ１として読み取り、右半身の身体的特徴を表す生体情報（例えば右手の指紋データ）を第２生体情報Ｄ２として読み取ってもよい。なお、入力部１２は、生体情報読取部２０に加え、キーボードやマウスなどの入力装置を有してもよい。
【００１８】
記憶部１３は、ハードディスク又はＲＯＭやＲＡＭといったメモリによって構成される。記憶部１３は、制御部１５が実行するプログラムを記憶する。また、記憶部１３は、ＲＳＡ暗号を利用するための公開鍵証明書２１を記憶する。公開鍵証明書２１には、ＲＳＡ暗号にて用いられる公開鍵（Ｎ、Ｅ）が含まれている。通信部１４は、制御部１５の制御に基づき、公開鍵（Ｎ、Ｅ）を共有するサーバとＲＳＡ暗号による通信を行う。
【００１９】
制御部１５は、図示しないＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）及びＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）などを備える。また、制御部１５は、プロセッサ・コアである第１コア２２Ａ及び第２コア２２Ｂを有するマルチコアプロセッサを備え、並列処理可能に構成されている。
【００２０】
そして、制御部１５は、暗号鍵生成装置１００内の各構成要素に対して種々の制御を行う。例えば、制御部１５は、第１生体情報Ｄ１及び第２生体情報Ｄ２を、利用者から生体情報読取部２０により読み取る。そして、制御部１５は、読み取った第１生体情報Ｄ１及び第２生体情報Ｄ２を所定のアルゴリズムを用いて所定ビット（例えば１０２４ビット）に数値化した数値「Ｐ」、「Ｑ」をそれぞれ算出し、数値Ｐ、Ｑを起点として素数ｐ、ｑをそれぞれ探索する。生体情報から所定ビットに数値化した数値を取り出す所定のアルゴリズムとしては任意の手法を用いることができる。例えば生体情報として指紋の画像データを取得し、この画像データの濃度値に対してしきい値を設定することにより白黒変換する。指紋画像を白黒変換することにより２値化（１，０）することができるので、その２値化した画像データから所定ビット分の数値を取り出すやり方などが利用できる。このように、制御部１５は、探索した素数ｐ、ｑに基づき、秘密鍵を構成する数値Ｄを算出する。そして、制御部１５は、本発明における「読み取り手段」、「数値化手段」、「素数探索手段」、「鍵生成手段」、「判定手段」、及びプログラムを実行するコンピュータの一例である。
【００２１】
ここで、数値Ｅ及び数値Ｄについて補足説明する。公開鍵を構成する数値Ｅは、「ｐ−１」と「ｑ−１」の最小公倍数である数値「Ｌ」（＝ＬＣＭ（ｐ−１，ｑ−１））を用いた以下の条件式
１＜Ｅ＜Ｌ、かつ、ＧＣＤ（Ｅ，Ｌ）＝１    （１）
を満たす自然数である。ここで、「ＧＣＤ（Ｅ，Ｌ）」は数値Ｅと数値Ｌの最大公約数を示す。また、秘密鍵を構成する数値Ｄは、以下の条件式
１＜Ｄ＜Ｌ、かつ、Ｅ×Ｄ  ≡  １  （ｍｏｄ  Ｌ）    （２）
を満たす自然数である。また、上述したように、数値Ｎは、素数ｐ、ｑを用いて以下の式（３）により定められる。
Ｎ＝ｐ×ｑ      （３）
そして、記憶部１３が記憶する公開鍵（Ｎ、Ｅ）は、予め生体情報読取部２０が正当な利用者に対して読み取った第１生体情報Ｄ１及び第２生体情報Ｄ２に基づき、後述する秘密鍵生成処理により算出した素数ｐ、ｑ及び式（１）、（３）を用いて算出された数値の組である。
【００２２】
［秘密鍵生成処理］
次に、秘密鍵生成処理について図２〜図８を参照して説明する。
【００２３】
（１）処理概要
図２は、制御部１５が実行する秘密鍵生成処理の概要を示すフローチャートである。
【００２４】
まず、制御部１５は、利用者に対し、生体情報読取部２０により第１生体情報Ｄ１の読み取りを行う（ステップＳ１０１）。そして、制御部１５は、生体情報読取部２０より読み取った第１生体情報Ｄ１に基づき、１０２４ビットの奇数の数値Ｐを生成する（ステップＳ１０２）。この場合、まず、制御部１５は、第１生体情報Ｄ１を所定のアルゴリズムを用いて数値化した後、数値化された第１生体情報Ｄ１から１０２４ビット分の数値を所定の規則に基づき抽出する。そして、制御部１５は、抽出した数値が奇数の場合には、当該数値を数値Ｐとし、抽出した数値が偶数の場合には、１だけずらした数値を数値Ｐとする。次に、制御部１５は、第１素数判定処理により数値Ｐから素数ｐを算出する（ステップＳ１０３）。第１素数判定処理については、図３〜図５を参照して後述する。
【００２５】
さらに、制御部１５は、利用者に対し、生体情報読取部２０により第２生体情報Ｄ２の読み取りを行う（ステップＳ１０４）。そして、制御部１５は、生体情報読取部２０より読み取った第２生体情報Ｄ２に基づき、１０２４ビットの奇数の数値Ｑを決定する（ステップＳ１０５）。この場合、まず、制御部１５は、第２生体情報Ｄ２を所定のアルゴリズムを用いて数値化した後、数値化された第２生体情報Ｄ２から１０２４ビットの数値を所定の規則に基づき抽出する。そして、制御部１５は、抽出した数値が奇数の場合には、当該数値を数値Ｑとし、抽出した数値が偶数の場合には、１だけずらした数値を数値Ｑとする。
【００２６】
次に、制御部１５は、公開鍵を構成する数値Ｎと素数ｐ、ｑとで整合性があるか否か判定する（ステップＳ１０７）。具体的には、公開鍵を構成する数値Ｎを定義した式（３）が成立するか否か判定する。
【００２７】
そして、制御部１５は、公開鍵を構成する数値Ｎと素数ｐ、ｑとが式（３）を満たし、整合性があると判断した場合（ステップＳ１０７；Ｙｅｓ）、秘密鍵を構成する数値Ｄを生成する（ステップＳ１０８）。具体的には、この場合、制御部１５は、公開鍵を構成する数値Ｅと、「ｐ−１」と「ｑ−１」の最小公倍数である数値Ｌを用いて、上述した条件式（２）を満たす数値Ｄを、所定のアルゴリズム（好適には非特許文献１のｐｐ．１２０−１２１にある拡張Euclid互除法）に基づき算出する。その後、制御部１５は、算出した数値Ｄを含む秘密鍵（Ｄ、Ｎ）を用いて、公開鍵（Ｅ、Ｎ）を共有するサーバから当該公開鍵により暗号化されて送信されたデータを復号する処理などを行う。
【００２８】
一方、制御部１５は、公開鍵を構成する数値Ｎと素数ｐ、ｑとが式（３）を満たさず、整合性がないと判断した場合（ステップＳ１０７；Ｎｏ）、素数ｐ、ｑの再計算を行う（ステップＳ１０９）。例えば、制御部１５は、第１素数判定処理を再開して現在の素数ｐと異なる次の素数ｐを算出すると共に、第２素数判定処理を再開して現在の素数ｑと異なる次の素数ｑを算出する。他の例では、制御部１５は、生体情報読取部２０による第１生体情報Ｄ１及び第２生体情報Ｄ２の読み取りに異常があったと判断し、再びステップＳ１０１〜ステップＳ１０６を行うことで、第１生体情報Ｄ１及び第２生体情報Ｄ２の読み取り及び素数ｐ、ｑの算出を再度行う。
【００２９】
（２）第１素数判定処理
図３は、制御部１５が実行する第１素数判定処理を示すフローチャートである。制御部１５は、図３に示すフローチャートの処理を、図２のステップＳ１０３で実行する。
【００３０】
まず、制御部１５は、素数ｐの候補であって、数値Ｐ以上に設定される候補値「Ｐ１」の初期値を数値Ｐに設定すると共に、素数ｐの候補であって、数値Ｐ以下に設定される候補値「Ｐ２」の初期値を数値Ｐに設定する（ステップＳ２０１）。そして、制御部１５は、第１コア２２Ａにより、候補値Ｐ１を徐々に大きくしていくことで素数ｐを探索する処理であるインクリメンタルサーチを行う（ステップＳ２０２）。また、制御部１５は、ステップＳ２０１と並行し、第２コア２２Ｂにより、候補値Ｐ２を徐々に減らしていくことで素数ｐを探索する処理であるデクリメンタルサーチを行う（ステップＳ２０３）。このように、制御部１５は、数値Ｐを基準としたインクリメンタルサーチとデクリメンタルサーチとを第１コア２２Ａ及び第２コア２２Ｂにより並行して実行する。これにより、制御部１５は、高速に素数ｐを探索することができる。
【００３１】
図４は、制御部１５の第１コア２２Ａが実行する候補値Ｐ１を用いたインクリメンタルサーチのフローチャートである。制御部１５の第１コア２２Ａは、図４に示すフローチャートの処理を、図４のステップＳ２０２で実行する。
【００３２】
まず、第１コア２２Ａは、非特許文献１のｐ．１３１にあるMiller-Rabinテストなどを用いて候補値Ｐ１が素数であるか否か判定する（ステップＳ２０５）。そして、第１コア２２Ａは、候補値Ｐ１が素数である場合（ステップＳ２０５；Ｙｅｓ）、公開鍵を構成する数値Ｅと「Ｐ１−１」との最大公約数が１であるか否か判定する（ステップＳ２０６）。即ち、候補値Ｐ１が素数ｐであると仮定した場合、条件式（１）を満たすには、数値Ｌの約数である「ｐ−１」（＝Ｐ１−１）と数値Ｅとの最大公約数は１になる必要があることから、第１コア２２Ａは、ステップＳ２０６の判定を行う。そして、数値Ｅと「Ｐ１−１」との最大公約数が１である場合（ステップＳ２０６；Ｙｅｓ）、第１コア２２Ａは、候補値Ｐ１を素数ｐとみなす（ステップＳ２０７）。そして、第１コア２２Ａは、図４のフローチャートを終了する。なお、第１コア２２Ａは、図２のステップＳ１０９で素数ｐの再計算を行う場合に備えて、候補値Ｐ１を２だけ増やし、引き続きフローチャートの処理を継続することで、素数ｐの次の候補を探索してもよい。
【００３３】
一方、数値Ｅと「Ｐ１−１」との最大公約数が１でない場合（ステップＳ２０６；Ｎｏ）、第１コア２２Ａは、候補値Ｐ１は素数ｐとなる条件を満たしていないと判断し、候補値Ｐ１を２だけ増やす（ステップＳ２０８）。そして、第１コア２２Ａは、再びステップＳ２０５の処理を行う。
【００３４】
なお、第１コア２２Ａは、第２コア２２Ｂが後述する図５のフローチャートの実行により素数ｐとなる候補値Ｐ２を検出した場合、図４のフローチャートの処理を強制的に終了してもよい。
【００３５】
図５は、制御部１５の第２コア２２Ｂが実行する候補値Ｐ２を用いたデクリメンタルサーチのフローチャートである。制御部１５の第２コア２２Ｂは、図５に示すフローチャートの処理を、図３のステップＳ２０３で実行する。
【００３６】
まず、第２コア２２Ｂは、非特許文献１のｐ．１３１にあるMiller-Rabinテストなどを用いて候補値Ｐ２が素数であるか否か判定する（ステップＳ２１０）。そして、第２コア２２Ｂは、候補値Ｐ２が素数である場合（ステップＳ２１０；Ｙｅｓ）、公開鍵を構成する数値Ｅと「Ｐ２−１」との最大公約数が１であるか否か判定する（ステップＳ２１１）。即ち、候補値Ｐ２が素数ｐであると仮定した場合、条件式（１）を満たすには、数値Ｌの約数である「ｐ−１」（＝Ｐ２−１）と数値Ｅとの最大公約数が１になる必要があることから、第２コア２２Ｂは、ステップＳ２１１の判定を行う。そして、数値Ｅと「Ｐ２−１」との最大公約数が１である場合（ステップＳ２１１；Ｙｅｓ）、第２コア２２Ｂは、候補値Ｐ２を素数ｐとみなす（ステップＳ２１２）。そして、第２コア２２Ｂは、図５のフローチャートを終了する。なお、第２コア２２Ｂは、図２のステップＳ１０９で素数ｐの再計算を行う場合に備えて、候補値Ｐ２を２だけ減らし、引き続きフローチャートの処理を継続することで素数ｐの次の候補を探索してもよい。
【００３７】
一方、数値Ｅと「Ｐ２−１」との最大公約数が１でない場合（ステップＳ２１１；Ｎｏ）、第２コア２２Ｂは、候補値Ｐ２は素数ｐとなる条件を満たしていないと判断し、候補値Ｐ２を２だけ減らす（ステップＳ２１３）。そして、第２コア２２Ｂは、再びステップＳ２１０の処理を行う。
【００３８】
なお、第２コア２２Ｂは、第１コア２２Ａが図４のフローチャートに基づき素数ｐとなる候補値Ｐ１を検出した場合、図５のフローチャートの処理を強制的に終了してもよい。
【００３９】
（３）第２素数判定処理
図６は、制御部１５が実行する第２素数判定処理を示すフローチャートである。制御部１５は、図６に示すフローチャートの処理を、図２のステップＳ１０６で実行する。
【００４０】
まず、制御部１５は、素数ｑの候補であって、数値Ｑ以上に設定される候補値「Ｑ１」の初期値を数値Ｑに設定すると共に、素数ｑの候補であって、数値Ｑ以下に設定される候補値「Ｑ２」の初期値を数値Ｑに設定する（ステップＳ３０１）。そして、制御部１５は、第１コア２２Ａにより、候補値Ｑ１を徐々に大きくしていくことで素数ｑを探索する処理であるインクリメンタルサーチを行う（ステップＳ３０２）。また、制御部１５は、ステップＳ３０１と並行し、第２コア２２Ｂにより、候補値Ｑ２を徐々に減らしていくことで素数ｑを探索する処理であるデクリメンタルサーチを行う（ステップＳ３０３）。このように、制御部１５は、数値Ｑを基準としたインクリメンタルサーチとデクリメンタルサーチとを第１コア２２Ａ及び第２コア２２Ｂにより並行して実行する。これにより、制御部１５は、高速に素数ｑを探索することができる。
【００４１】
図７は、制御部１５の第１コア２２Ａが実行する候補値Ｑ１を用いたインクリメンタルサーチのフローチャートである。制御部１５の第１コア２２Ａは、図７に示すフローチャートの処理を、図６のステップＳ３０２で実行する。
【００４２】
まず、第１コア２２Ａは、非特許文献１のｐ．１３１にあるMiller-Rabinテストなどを用いて候補値Ｑ１が素数であるか否か判定する（ステップＳ３０５）。そして、第１コア２２Ａは、候補値Ｑ１が素数である場合（ステップＳ３０５；Ｙｅｓ）、公開鍵を構成する数値Ｅと「Ｑ１−１」との最大公約数が１であるか否か判定する（ステップＳ３０６）。即ち、候補値Ｑ１が素数ｑであると仮定した場合、条件式（１）を満たすには、数値Ｌの約数である「ｑ−１」（＝Ｑ１−１）と数値Ｅとの最大公約数が１になる必要があることから、第１コア２２Ａは、ステップＳ３０６の判定を行う。そして、数値Ｅと「Ｑ１−１」との最大公約数が１である場合（ステップＳ３０６；Ｙｅｓ）、第１コア２２Ａは、候補値Ｑ１を素数ｑとみなす（ステップＳ３０７）。そして、第１コア２２Ａは、図４のフローチャートを終了する。なお、第１コア２２Ａは、図２のステップＳ１０９で素数ｑの再計算を行う場合に備えて、候補値Ｑ１を２だけ増やし、引き続きフローチャートの処理を継続することで、素数ｑの次の候補を探索してもよい。
【００４３】
一方、数値Ｅと「Ｑ１−１」との最大公約数が１でない場合（ステップＳ３０６；Ｎｏ）、第１コア２２Ａは、候補値Ｑ１は素数ｑとなる条件を満たしていないと判断し、候補値Ｑ１を２だけ増やす（ステップＳ３０８）。そして、第１コア２２Ａは、再びステップＳ３０５の処理を行う。
【００４４】
なお、第１コア２２Ａは、第２コア２２Ｂが後述する図８のフローチャートの実行により素数ｑとなる候補値Ｑ２を検出した場合、図７のフローチャートの処理を強制的に終了してもよい。
【００４５】
図８は、制御部１５の第２コア２２Ｂが実行する候補値Ｑ２を用いたデクリメンタルサーチのフローチャートである。制御部１５の第２コア２２Ｂは、図８に示すフローチャートの処理を、図６のステップＳ３０３で実行する。
【００４６】
まず、第２コア２２Ｂは、非特許文献１のｐ．１３１にあるMiller-Rabinテストなどを用いて候補値Ｑ２が素数であるか否か判定する（ステップＳ３１０）。そして、第２コア２２Ｂは、候補値Ｑ２が素数である場合（ステップＳ３１０；Ｙｅｓ）、公開鍵を構成する数値Ｅと「Ｑ２−１」との最大公約数が１であるか否か判定する（ステップＳ３１１）。即ち、候補値Ｑ２が素数ｑであると仮定した場合、条件式（１）を満たすには、数値Ｌの約数である「ｑ−１」（＝Ｑ２−１）と数値Ｅとの最大公約数が１になる必要があることから、第２コア２２Ｂは、ステップＳ３１１の判定を行う。そして、数値Ｅと「Ｑ２−１」との最大公約数が１である場合（ステップＳ３１１；Ｙｅｓ）、第２コア２２Ｂは、候補値Ｑ２を素数ｑとみなす（ステップＳ３１２）。そして、第２コア２２Ｂは、図８のフローチャートを終了する。なお、第２コア２２Ｂは、図２のステップＳ１０９で素数ｑの再計算を行う場合に備えて、候補値Ｑ２を２だけ減らし、引き続きフローチャートの処理を継続することで素数ｑの次の候補を探索してもよい。
【００４７】
一方、数値Ｅと「Ｑ２−１」との最大公約数が１でない場合（ステップＳ３１１；Ｎｏ）、第２コア２２Ｂは、候補値Ｑ２は素数ｑとなる条件を満たしていないと判断し、候補値Ｑ２を２だけ減らす（ステップＳ３１３）。そして、第２コア２２Ｂは、再びステップＳ３１０の処理を行う。
【００４８】
なお、第２コア２２Ｂは、第１コア２２Ａが図７のフローチャートに基づき素数ｑとなる候補値Ｑ１を検出した場合、図８のフローチャートの処理を強制的に終了してもよい。
【００４９】
［暗号鍵生成装置の作用効果］
暗号鍵生成装置１００は、生体情報読取部２０により読み取った第１生体情報Ｄ１及び第２生体情報Ｄ２を数値化した数値Ｐ及び数値Ｑを起点として、公開鍵と整合する秘密鍵を構成する数値Ｄを算出するために必要な素数ｐ、ｑを探索する。これにより、暗号鍵生成装置１００は、秘密鍵を記憶するための耐タンパ性を有する媒体を利用することなく、公開鍵に対応する秘密鍵を好適に生成することができる。
【００５０】
［変形例］
次に、上述の実施形態の変形例について説明する。以下の変形例は、組み合わせて上述の実施形態に適用してもよい。
【００５１】
（変形例１）
暗号鍵生成装置１００は、ＲＳＡ暗号に用いる素数ｐ、ｑに代えて、生体情報に基づき、ＲＳＡ暗号以外の公開鍵認証基盤に利用される任意の公開鍵暗号方式の暗号鍵の生成に必要な１又は複数の素数を算出してもよい。
【００５２】
この場合であっても、暗号鍵生成装置１００は、暗号鍵の生成に必要な素数の個数分だけ、生体情報読取部２０から生体情報を読み取り、これらを所定ビットに数値化した情報に基づき、予め公開鍵を作成する。そして、暗号通信時には、暗号鍵生成装置１００は、公開鍵の生成時と同一対象の生体情報を生体情報読取部２０により利用者から読み取り、読み取った生体情報を所定ビット数の数値に変換する。そして、暗号鍵生成装置１００は、変換した数値を起点としてインクリメンタルサーチ及びデクリメンタルサーチを行い、既に生成した公開鍵と整合する秘密鍵を生成するのに必要な素数の探索を行う。
【００５３】
（変形例２）
制御部１５は、第１コア２２Ａと第２コア２２Ｂとを有するマルチコアプロセッサを有していたが、これに代えて、マルチプロセッサを有してもよい。これによっても、制御部１５は、好適に、インクリメンタルサーチとデクリメンタルサーチとの並列処理を行うことができる。
【符号の説明】
【００５４】
１１…表示部
１２…入力部
１３…記憶部
１４…通信部
１５…制御部
１００…秘密鍵生成装置
【図１】
2015188148.tif 000003
【図２】
2015188148.tif 000004
【図３】
2015188148.tif 000005
【図４】
2015188148.tif 000006
【図５】
2015188148.tif 000007
【図６】
2015188148.tif 000008
【図７】
2015188148.tif 000009
【図８】
2015188148.tif 000010