(57)【要約】【構成】  ｙ≡ｇｘ mod  m  のｙのハッシュ値f1,f2をアドレスとし、ｘをデータとする２つの表を記憶する。異なるｙに対してハッシュ値が一致する場合、次のアドレスにデータを記載する。離散対数ｘを求める際に、ｙのハッシュ値f1,f2をアドレスの出発点として、データが空になるまでのアドレス範囲で２つの表を検索し、一致するデータが有れば、表のデータを離散対数ｘとして出力する。【効果】  高速で離散対数を求めることができる。【選択図】    図２
2008158458.tif 000002
【特許請求の範囲】
【請求項１】
変数ｙの値に対する離散対数ｘ(ｙ≡ｇｘ)を求めるための、コンピュータを用いた離散対数処理装置であって、
ｙの値に対する第１のハッシュ値を求めるための第１のハッシュ処理部と、
ｙの値に対する第２のハッシュ値を求めるための第２のハッシュ処理部と、
第１のハッシュ値をアドレスとし、離散対数をデータとして記載すると共に、異なるｙの値に対して第１のハッシュ値が共通となる場合、第１のハッシュ値からアドレスが連続する各アドレスに、各ｙの値に対する離散対数をデータとして記載した第１のテーブルを記憶したメモリーと、
第２のハッシュ値をアドレスとして離散対数をデータとして記載すると共に、異なるｙの値に対して第２のハッシュ値が共通となる場合、第２のハッシュ値からアドレスが連続する各アドレスに、各ｙの値に対する離散対数をデータとして記載した第２のテーブルを記憶したメモリーと、
ｙの値が入力された際に、
・    前記第１及び第２のハッシュ処理部で求めたハッシュ値により、第１のハッシュ値を先頭のアドレスとして、連続してデータが記載されている範囲で、第１のテーブルから読み出したデータと、第２のハッシュ値を先頭のアドレスとして、連続してデータが記載されている範囲で、第２のテーブルから読み出したデータとで、一致するデータの有無を探索する試行を繰り返して、その試行回数Ｌをカウントするカウンタと、
・    一致するデータが有れば、そのデータと定数Ｔとの積と試行回数Ｌとから離散対数を求めて出力する演算部と、
・    一致するデータがなければ、ｙの値をｇ倍だけ変更し、前記第１及び第２ハッシュ処理部によりハッシュ値を変更して次の試行を行う算術論理演算部とを備えた制御ユニット、とを設けた離散対数処理装置。
【請求項２】
ユーザのIDを数値化した変数ｙの値に対する離散対数ｘ(ｙ≡ｇｘ)を求める、暗号通信システムでのコンピュータを用いたセンター装置であって、
ｙの値に対する第１のハッシュ値を求めるための第１のハッシュ処理部と、
ｙの値に対する第２のハッシュ値を求めるための第２のハッシュ処理部と、
第１のハッシュ値をアドレスとして離散対数をデータとして記載すると共に、異なるｙの値に対して第１のハッシュ値が共通となる場合、第１のハッシュ値からアドレスが連続する各アドレスに、各ｙの値に対する離散対数をデータとして記載した第１のテーブルを記憶したメモリーと、
第２のハッシュ値をアドレスとして離散対数をデータとして記載すると共に、異なるｙの値に対して第２のハッシュ値が共通となる場合、第２のハッシュ値からアドレスが連続する各アドレスに、各ｙの値に対する離散対数をデータとして記載した第２のテーブルを記憶したメモリーと、
ｙの値が入力された際に、
・    前記第１及び第２のハッシュ処理部で求めたハッシュ値により、第１のハッシュ値を先頭のアドレスとして、連続してデータが記載されている範囲で第１のテーブルから読み出したデータと、第２のハッシュ値を先頭のアドレスとして、連続してデータが記載されている範囲で第２のテーブルから読み出したデータとで、一致するデータの有無を探索する試行を繰り返して、その試行回数Ｌをカウントするカウンタと、
・    一致するデータが有れば、そのデータと定数Ｔとの積と試行回数Ｌとから、離散対数を求めて出力する演算部と、
・    一致するデータがなければ、ｙの値をｇ倍だけ変更し、前記第１及び第２ハッシュ処理部によりハッシュ値を変更して次の試行を行う算術論理演算部とを備えた制御ユニット、とを設けたセンター装置。
【請求項３】
変数ｙの値に対する離散対数ｘ(ｙ≡ｇｘ)を求める、コンピュータのための離散対数処理プログラムであって、
ｙの値に対する第１のハッシュ値を、コンピュータに求めさせるための第１のハッシュ命令と、
ｙの値に対する第２のハッシュ値を、コンピュータに求めるための第２のハッシュ命令と、
・      第１のハッシュ値をアドレスとして離散対数をデータとして記載すると共に、異なるｙの値に対して第１のハッシュ値が共通となる場合、第１のハッシュ値からアドレスが連続する各アドレスに、各ｙの値に対する離散対数をデータとして記載した第１のテーブルと、
・      第２のハッシュ値をアドレスとして離散対数をデータとして記載すると共に、異なるｙの値に対して第２のハッシュ値が共通となる場合、第２のハッシュ値からアドレスが連続する各アドレスに、各ｙの値に対する離散対数をデータとして記載した第２のテーブル、
とをコンピュータに記憶させるためのテーブル記憶命令と、
ｙの値が入力された際に、
・    前記第１及び第２のハッシュ処理部で求めたハッシュ値により、第１のハッシュ値を先頭のアドレスとして、連続してデータが記載されている範囲で第１のテーブルから読み出したデータと、第２のハッシュ値を先頭のアドレスとして、連続してデータが記載されている範囲で第２のテーブルから読み出したデータとで、一致するデータの有無を探索する試行を繰り返して、その試行回数Ｌをカウントし、
・    一致するデータが有れば、そのデータと定数Ｔとの積と試行回数Ｌとから、離散対数を求めて出力し、
・    一致するデータがなければ、ｙの値をｇ倍だけ変更し、前記第１及び第２ハッシュ命令によりハッシュ値を変更して次の試行を行う制御命令、とを設けた離散対数処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は離散対数処理装置やこれを用いた公開鍵暗号システムのセンター装置、離散対数処理プログラムに関し、例えば公開鍵暗号システムでの秘密鍵の発生や、電子署名システムでの署名用の鍵の発生に関する。
【背景技術】
【０００２】
離散対数問題を安全性の根拠としてIDに基づく共有鍵を発生させることが、非特許文献１に記載されている。また離散対数問題の解法として、ジャイアントステップ／ベイビーステップを用いる手法が公知である。  ｙ≡ｇｘとなる  値ｘを求めるものとして、ジャイアントステップでは複数個の変数ｙの値に対して離散対数ｘを求めて表に記載する。ベイビーステップでは、離散対数を求めるｙの値を底ｇ倍ずつ変化させながら、表から  ｙ≡ｇｘ  となる値ｘを求める。ここでＬ＋１回の試行でｙの値をｇＬだけ変化させたものとすると、  ｘ＋Ｌ  が求める離散対数の値である。
【０００３】
発明者らは、IDと離散対数問題とを用いて、共有鍵を発生させることを検討した(非特許文献２〜４)。この場合、センター装置には共有鍵の基礎となる秘密鍵を生成するため、IDを数値化した値に対する離散対数を求める能力が必要とされる。ここでジャイアントステップ／ベイビーステップ法では、IDを数値化した値を離散対数に変換するための巨大なテーブルが必要である。発明者は、
・  IDを数値化した値、以下単に”ID”を、ハッシュ関数で処理し、
・  求めたハッシュ値をアドレスとして、離散対数を記憶したテーブルを参照することを提案した(非特許文献５)。これによってテーブルの規模を劇的に小さくできる。しかしながら異なるIDに対してハッシュが共通となることがある。ジャイアントステップではハッシュ値毎に離散対数を求め、テーブルの規模を原像のID空間のサイズよりも充分小さくするので、ハッシュは単射ではない。
【０００４】
非特許文献５では、異なるIDに対してハッシュが同じとなる場合に備えて、
・  １つのハッシュ値当たりで、複数個の離散対数の値を記憶可能にする、従ってテーブルの規模が増加することと、
・  補助的なテーブルを用意し、複数のIDに対してハッシュ値が一致する場合、補助テーブルを参照して解決する、ことの２つの解決を用意した。実用的なID空間の規模では、同じハッシュ値に最大で１００個程度のIDが対応することがあり、第１の解決ではテーブルの規模が１００倍程度増加する。第２の解決では、離散対数の値を求めるのに補助テーブルを参照する必要があり、補助テーブルのアドレスはハッシュ値自体からは判明せず、補助テーブルの参照に時間が必要である。
【非特許文献１】W.Diffie, M.E.Hellman, "New directions in cryptography" IEEETrans. Inform. Theory Vol.IT-22,No.6,p.p.644-654,Nov.1976
【非特許文献２】村上，笠原:”ID情報に基づく鍵共有の一方式”,信学技法,ISEC 90-26,p.p.33-40
【非特許文献３】村上，笠原:”合成数を法とする離散対数問題”,信学技法,ISEC 90-42,p.p.29-36
【非特許文献４】村上，笠原:”村上-笠原ID鍵共有方式について”,信学技法,Vol.105,No.194,ISEC2005-42,p.p.9-16
【非特許文献５】A.Koyama, Y.Murakami, M.Kasahara, "On the feasibility of Murakami-Kasahara ID-based  key sharing scheme" Proc.SCIS'06,No.3D-2-1,2006.(in Japanese)
【発明の開示】
【発明が解決しようとする課題】
【０００５】
この発明の課題は、高速で離散対数問題を解き得るようにして、IDに基づく鍵共有方式でのセンターの構成を容易にする、あるいは離散対数を用いた電子署名を容易にすることにある。
【課題を解決するための手段】
【０００６】
この発明は、変数ｙの値に対する離散対数ｘ(ｙ≡ｇｘ)を求めるための、コンピュータを用いた離散対数処理装置であって、
ｙの値に対する第１のハッシュ値を求めるための第１のハッシュ処理部と、
ｙの値に対する第２のハッシュ値を求めるための第２のハッシュ処理部と、
第１のハッシュ値をアドレスとし、離散対数をデータとして記載すると共に、異なるｙの値に対して第１のハッシュ値が共通となる場合、第１のハッシュ値からアドレスが連続する各アドレスに、各ｙの値に対する離散対数をデータとして記載した第１のテーブルを記憶したメモリーと、
第２のハッシュ値をアドレスとして離散対数をデータとして記載すると共に、異なるｙの値に対して第２のハッシュ値が共通となる場合、第２のハッシュ値からアドレスが連続する各アドレスに、各ｙの値に対する離散対数をデータとして記載した第２のテーブルを記憶したメモリーと、
ｙの値が入力された際に、
・    前記第１及び第２のハッシュ処理部で求めたハッシュ値により、第１のハッシュ値を先頭のアドレスとして、連続してデータが記載されている範囲で、第１のテーブルから読み出したデータと、第２のハッシュ値を先頭のアドレスとして、連続してデータが記載されている範囲で、第２のテーブルから読み出したデータとで、一致するデータの有無を探索する試行を繰り返して、その試行回数Ｌをカウントするカウンタと、
・    一致するデータが有れば、そのデータと定数Ｔとの積と試行回数Ｌとから、離散対数を求めて出力する演算部と、
・    一致するデータがなければ、ｙの値をｇ倍だけ変更し、前記第１及び第２ハッシュ処理部によりハッシュ値を変更して次の試行を行う算術論理演算部とを備えた制御ユニット、とを設けた離散対数処理装置にある。
【０００７】
この発明はまた、ユーザのIDを数値化した変数ｙの値に対する離散対数ｘ(ｙ≡ｇｘ)を求める、暗号通信システムでのコンピュータを用いたセンター装置であって、
ｙの値に対する第１のハッシュ値を求めるための第１のハッシュ処理部と、
ｙの値に対する第２のハッシュ値を求めるための第２のハッシュ処理部と、
第１のハッシュ値をアドレスとして離散対数をデータとして記載すると共に、異なるｙの値に対して第１のハッシュ値が共通となる場合、第１のハッシュ値からアドレスが連続する各アドレスに、各ｙの値に対する離散対数をデータとして記載した第１のテーブルを記憶したメモリーと、
第２のハッシュ値をアドレスとして離散対数をデータとして記載すると共に、異なるｙの値に対して第２のハッシュ値が共通となる場合、第２のハッシュ値からアドレスが連続する各アドレスに、各ｙの値に対する離散対数をデータとして記載した第２のテーブルを記憶したメモリーと、
ｙの値が入力された際に、
・    前記第１及び第２のハッシュ処理部で求めたハッシュ値により、第１のハッシュ値を先頭のアドレスとして、連続してデータが記載されている範囲で第１のテーブルから読み出したデータと、第２のハッシュ値を先頭のアドレスとして、連続してデータが記載されている範囲で第２のテーブルから読み出したデータとで、一致するデータの有無を探索する試行を繰り返して、その試行回数Ｌをカウントするカウンタと、
・    一致するデータが有れば、そのデータと定数Ｔとの積と試行回数Ｌとから、離散対数を求めて出力する演算部と、
・    一致するデータがなければ、ｙの値をｇ倍だけ変更し、前記第１及び第２ハッシュ処理部によりハッシュ値を変更して次の試行を行う算術論理演算部とを備えた制御ユニット、とを設けたセンター装置にある。
【０００８】
この発明はさらに、変数ｙの値に対する離散対数ｘ(ｙ≡ｇｘ)を求める、コンピュータのための離散対数処理プログラムであって、
ｙの値に対する第１のハッシュ値を、コンピュータに求めさせるための第１のハッシュ命令と、
ｙの値に対する第２のハッシュ値を、コンピュータに求めるための第２のハッシュ命令と、
・      第１のハッシュ値をアドレスとして離散対数をデータとして記載すると共に、異なるｙの値に対して第１のハッシュ値が共通となる場合、第１のハッシュ値からアドレスが連続する各アドレスに、各ｙの値に対する離散対数をデータとして記載した第１のテーブルと、
・      第２のハッシュ値をアドレスとして離散対数をデータとして記載すると共に、異なるｙの値に対して第２のハッシュ値が共通となる場合、第２のハッシュ値からアドレスが連続する各アドレスに、各ｙの値に対する離散対数をデータとして記載した第２のテーブル、
とをコンピュータに記憶させるためのテーブル記憶命令と、
ｙの値が入力された際に、
・    前記第１及び第２のハッシュ処理部で求めたハッシュ値により、第１のハッシュ値を先頭のアドレスとして、連続してデータが記載されている範囲で第１のテーブルから読み出したデータと、第２のハッシュ値を先頭のアドレスとして、連続してデータが記載されている範囲で第２のテーブルから読み出したデータとで、一致するデータの有無を探索する試行を繰り返して、その試行回数Ｌをカウントし、
・    一致するデータが有れば、そのデータと定数Ｔとの積と試行回数Ｌとから、離散対数を求めて出力し、
・    一致するデータがなければ、ｙの値をｇ倍だけ変更し、前記第１及び第２ハッシュ命令によりハッシュ値を変更して次の試行を行う制御命令、とを設けた離散対数処理プログラムにある。
【発明の効果】
【０００９】
この発明では、離散対数を高速で求めることができるので、例えばIDを基礎とした鍵共有が容易になる。また電子署名での離散対数の計算が容易になる。この結果、鍵共有システムでのセンター装置の構成が容易になる。
【発明を実施するための最良の形態】
【００１０】
以下に本発明を実施するための最適実施例を示す。
【実施例】
【００１１】
図１〜図７に実施例を示す。図１は実施例の暗号通信システム２を示し、４はセンター装置で、コンピュータにより実現され、６，７はそれぞれコンピュータを用いた暗号通信装置で、インターネット８を介して通信する。装置６のIDを数値化した値をｙA、装置７のIDを数値化した値をｙBとする。なお以下、単にIDという場合、IDを数値化した値である。センター４はｙA≡ｇｘA  mod ｎとなる値ｘA、並びにｙB≡ｇｘB  mod ｎとなる値ｘBを求めて、これらを安全な通信路を介して、装置６，７へ提供する。ｇは離散対数の底で、ｘA，ｘBは離散対数の値である。装置６は装置７と暗号通信する際の鍵ＫABをＫAB≡ｙB２ｘA  mod ｎとして求める。装置７は同様にして、鍵ＫBA≡ｙA２ｘB  mod ｎを求める。するとＫABとＫBAは等しく、装置６と装置７は鍵を共有できる。なお適宜の法という意味で記号ｎを用い、後記のテーブル１０，１１を用いた計算での具体的な法には、記号ｍを用いる。また記号は全て整数である。この例ではｎ＝ｐｑ(ｐ，ｑは素数)とし、ｐ＝２ａ・ｐ'＋１  ｑ＝２・３ｂ・ｑ'＋１  (ｐ'，ｑ'は素数)とする。ここで法をｎとする離散対数問題は、法をｐ'とする離散対数問題と、法をｑ'とする離散対数問題とに還元できる。そこで以下、法ｐ'，ｑ'に関する離散対数問題を検討し、法ｐ'，ｑ'の個々の値は重要ではないので、法を一般に記号ｍで表す。
【００１２】
図２にセンター装置４の構成を示す。１０，１１はそれぞれテーブルで、テーブルのアドレスはハッシュ処理部１４，１５で得られるハッシュ値であり、データはハッシュ値に対する離散対数の値である。１２は読み出し制御で、テーブル１０，１１に対する読み出しを制御し、１３は出力バッファで、テーブルのデータ並びにデータの有無を出力する。なおデータが無いことをφで表す。テーブル１０からのデータをData1，テーブル１１からのデータをData2，テーブル１０での出力の有無を表す信号をＫ1，テーブル１１での出力の有無を表す信号をＫ2とする。１４，１５はハッシュ処理部で、記憶部２０から与えられるｙの値に対して、ハッシュ値を計算する。ハッシュは必ずしも１方向性関数である必要はなく、例えばID ｙの所定のビットを取り出してハッシュ値としてもよい。
【００１３】
１６は制御ユニットで、センター装置４の全体を制御する。制御ユニット１６はテーブル１０，１１から読み出したデータが一致するかどうかをチェックする。チェックする範囲は、ハッシュ処理部１４，１５で求めたハッシュ値、即ちaddress1，address2を先頭アドレスとして、データが連続して存在する範囲である。テーブル１０，１１間で一致するデータが存在すれば、べき乗剰余演算部１８で正しいデータかどうかを確認し、正しいデータであると確認されると、制御ユニット１６はｘ＝Ｔ×Data1＋Ｌとして離散対数ｘを出力する。ここにＴは定数で、ジャイアントステップで離散対数を求める回数に反比例し、Ｌは試行錯誤の回数で、具体的にはハッシュ処理部１４，１５でアドレスを発生させた回数である。Ｌの値は０〜Ｔ−１である。
【００１４】
テーブル１０，１１が同じｙの値に対して共通のデータを出力しない場合、共通のデータが出力されたがべき乗剰余演算部１８で棄却された場合、もしくはハッシュ値に対するアドレスにテーブル１０，１１のいずれかでデータがない場合、制御ユニット１６はＬの値を１加算し、モジュラー乗算部１９にｙ≡ｙ・ｇ−１ mod ｍを計算させ、これをｙの値として記憶部２０に入力する。なおハッシュ処理部１４，１５で発生したアドレスの値は、制御ユニット１６にも入力され、制御ユニット１６はハッシュ処理部１４，１５で求めたハッシュ値を先頭アドレスとして、連続してデータが存在する範囲でテーブル１０，１１からデータを読み出す。さらにべき乗剰余演算部１８は設けなくても良い。
【００１５】
図３に制御ユニット１６の構造を示す。算術論理演算部２１はｙの値や２つのハッシュ値address1，address2、及びテーブル１０，１１からのデータData1,2や信号Ｋ1,Ｋ2を入力され、テーブル１０，１１でData1,Data2が空となるまで、次の読み出しアドレスを発生する。またData1,Data2が一致するか否かを探索し、一致しないと、カウンタ２２で変数Ｌの値を１増加し、モジュラー乗算部１９にｙの次の値を発生させる。一致する場合、べき乗剰余演算部１８で確認し、演算部２３で離散対数ｘの値を求めて出力する。
【００１６】
図４にセンタープログラム３０を示す。このプログラムは適宜のコンピュータに記憶されて、図２のセンター装置４を構成する。３１はテーブル記憶命令で、図２のテーブル１０，１１をコンピュータのメモリーに記憶させる。このテーブルではＹ≡ＧＨ mod ｍとして、Ｈの値を変えながらＨの値をテーブル１０，１１に書き込む。書き込みでは、Ｙの値を第１のハッシュ処理部で処理したハッシュ値がテーブル１０への書き込みアドレスで、第２のハッシュ処理部で処理したハッシュ値がテーブル１１への書き込みアドレスである。テーブル記憶命令３１は、既に作成済みのテーブル１０，１１をコンピュータに記憶させるための命令でも、コンピュータ内でテーブル１０，１１をＹ≡ＧＨ mod ｍの計算を実行しながら作成するための命令でも良い。
【００１７】
第１ハッシュ命令３２はｙの値を第１のハッシュ値f1(y)(f1(y)＝address1)へ変換するための命令で、第２ハッシュ命令３３はｙの値を第２のハッシュ値f2(y)
(f2(y)＝address2)へ変換するための命令である。制御命令３４は、制御ユニット１６での処理をコンピュータに実行させるための命令で、ｙの値に対する離散対数を発見した場合、ｘ＝Ｔ×Data1＋Ｌ  により離散対数ｘの値を出力する。なおここにData1＝Data2である。比較命令３５はテーブル１０，１１から出力されたデータに一致するものがあるかどうかを探索する。探索命令３６はｙの値から求めたaddress1,address2からデータが連続して存在する範囲でデータを読み出す。べき乗剰余演算命令３８は、比較命令３５でデータが一致することを検出すると、一致するデータに対しＧData1 mod ｍを求めて、これがｙの値と一致するかどうかを検出する。モジュラー乗算命令３９は離散対数が求まらなかった際に、ｙにｙ・ｇ−１ mod ｍを代入する。
【００１８】
図５にテーブル作成アルゴリズムを示し、これはジャイアントステップ／ベイビーステップ法でのジャイアントステップに対応する。ステップ１で２つのテーブルのアドレス空間分のメモリーを用意し、各テーブルのアドレスサイズは２Ｓ である。なおハッシュ値f1，f2のビット数をｕとすると、Ｓは２ｕ程度となる。IDを数値化した値の空間サイズをｒとし、ｒ／Ｓを切り上げたものをＴとする。さらに底をｇ、法をｍとして、Ｇ≡ｇＴ mod ｍとする。
【００１９】
ステップ２で実際に作表する。作業変数をＨとし、Ｈを０からＳ−１まで変化させ、Ｙ≡ＧＨ mod ｍを求める。次にＹに対する２つのハッシュ値を求め、これらを書き込みアドレスaddress1，2とする。表の書き込みアドレスにデータがない場合、そのアドレスにＨの値を書き込む。既にデータが存在する場合、次のアドレスを探索し、最初の空きのアドレスを発見した際に、データＨを書き込む。以上によって作表が完成し、ステップ３で２つのテーブルを出力する。
【００２０】
図６に離散対数の算出アルゴリムを示し、これはジャイアントステップ／ベイビーステップでのベイビーステップに対応する。ステップ５では前記のステップ１と同様に
Ｙ≡ＧＨ mod ｍとする。ステップ６で、ユーザのIDを数値化した変数ｙの値に対する離散対数ｘを探索する。作業変数をＬとして、Ｌ＝０からＴ−１まで最大Ｔ回の試行を行う。ステップ７でｙに対する２つのハッシュ値を求め、これらをテーブル１，テーブル２に対するアドレスとする。このアドレスでテーブル１，テーブル２を読み出し、テーブルが空欄かデータが存在するかどうかを探索する。データが存在する場合、次のアドレスでのデータの有無を探索し、データが無い欄に達するまで、表のデータを読み出す(ステップ７，ステップ８)。
【００２１】
テーブル１，テーブル２に同じデータが存在する場合、Data1＝Data2なので、
ｙ≡ＧData1 mod ｍ  が成立するかどうかを確認する。これが成立すれば正しい離散対数が求まっていることになる(ステップ９)。正しい離散対数が求まっている場合、
ｘ＝Ｔ×Data1＋Ｌを求める離散対数として出力する(ステップ１０)。ステップ８で、
・  テーブル１，テーブル２のいずれかにハッシュ値から求めたアドレスにデータがない場合、
・  もしくはデータが存在するが一致しない場合、もしくは
・  同じデータが発見されたが、ｙ≡ＧData1 mod ｍが成立しない場合、
ステップ１１へ移行してＬの値を１増し、ｙ≡ｙ・ｇ−１ mod ｍとする。
【００２２】
以上のようにして、ｙの値に対する離散対数を発見する。離散対数の発見では、ハッシュ値を先頭アドレスとして、連続してデータが存在する範囲を検索すれば良く、テーブルの参照を高速で行える。同じハッシュ値に対するデータは連続したアドレスに記載するが、例えば１つ置きのアドレスに配置しても良い。
ｙの値の変更では、ｇ−１倍する代わりにｇ倍しても良い。
プログラム中のループの処理は、Ｌ等の作業変数について、昇順に行っても、降順に行っても良く、降順に行うと離散対数ｘは  ｘ＝Ｔ×Data1＋Ｌ  ではなく、
ｘ＝Ｔ×Data1＋Ｔ−１−Ｌ  となる。
また２つのハッシュ値に対してテーブル１０，１１から同一のデータが得られた場合、偶発的にこのようなことが生じる確率は極めて小さい。
【００２３】
図７に、法ｐ，ｑに関する離散対数問題を解く際の計算時間を示す。図中のＤＣ法は実施例を、ＭＭ法は非特許文献５の従来例を示す。また横軸のｐ'，ｑ'と図中のｐ，ｑとの関係は、ｐ＝２ａ・ｐ'＋１， ｑ＝２・３ｂ・ｑ'＋１  である。実施例では、大きな素数ｐ'，ｑ'に対し、効率的に離散対数を求めることができる。      
【００２４】
実施例では整数上の有限乗法群を取り扱ったが、離散対数問題は楕円曲線上でも定義でき、その場合にも、ジャイアントステップ／ベイビーステップ法を離散対数問題の解法として利用できる。従って本発明は、ジャイアントステップ／ベイビーステップ法により、楕円曲線上の離散対数問題を解く際にも応用できる。
【図面の簡単な説明】
【００２５】
【図１】実施例のセンター装置を用いた暗号通信システムのブロック図
【図２】実施例のセンター装置のブロック図
【図３】実施例の制御ユニットのブロック図
【図４】実施例でのセンタープログラムのブロック図
【図５】実施例での、ジャイアントステップでのテーブル作成を示すフローチャート
【図６】実施例での、ベイビーステップでの離散対数の算出を示すフローチャート
【図７】実施例(DC)と従来例(MM)とでの離散対数の算出時間を示す特性図
【符号の説明】
【００２６】
２          暗号通信システム
４          センター装置
６，７      暗号通信装置
８          インターネット
１０，１１  テーブル
１２        読み出し制御
１３        出力バッファ
１４，１５  ハッシュ処理部
１６        制御ユニット
１８        べき乗剰余演算部
１９        モジュラー乗算部
２０        記憶部
２１        算術論理演算部
２２        カウンタ
２３        演算部
３０        センタープログラム
３１        テーブル記憶命令
３２        第１ハッシュ命令
３３        第２ハッシュ命令
３４        制御命令
３５        比較命令
３６        探索命令
３８        べき乗剰余演算命令
３９        モジュラー乗算命令
【図１】
2008158458.tif 000003
【図２】
2008158458.tif 000004
【図３】
2008158458.tif 000005
【図４】
2008158458.tif 000006
【図５】
2008158458.tif 000007
【図６】
2008158458.tif 000008
【図７】
2008158458.tif 000009