(57)【要約】【課題】  離散対数問題をBaby Step/Giant Step法で解く際の、テーブルの規模を小さくし、かつテーブルの参照回数を少なくする。【解決手段】  ｙ・ｇ−ｉの下位２ビットのビット列をａとし、ａをアドレスとして  ｙ・ｇ−ｉ＝Ｇｉ  を充たすｉの値の候補を記述したテーブルを作成する。テーブルには各アドレスに対してｉの値の候補を複数個記述できるようにし、作表時にはアドレスａ以降の空欄にｉの値の候補を記述する。参照時には、アドレスａから始めて空欄が生じるまでのｉの値の候補を読み出し、Ｇｉを演算してｙ・ｇ−ｉと一致するものをｉの値として出力する。【選択図】    図２
2007128001.tif 000002
【特許請求の範囲】
【請求項１】
法をｐとして、整数変数ｙと整数の底ｇとに対し、  ｙ＝ｇｘ    を充たす整数変数ｘを求めるための離散対数処理装置において、
整数変数ｊに対し、ｙ・ｇ−ｊをｊの値毎に求めるためのべき乗手段と、
べき乗手段で求めたｙ・ｇ−ｊにより生成され、かつｙ・ｇ−ｊよりもデータ長が短い整数データａをテーブル内アドレスとし、ｂを整数として、  ｙ・ｇ−ｊ＝ｇｂｉ    を充たす整数変数ｉの値の候補を記述した逆引きテーブルと、
ｉの値の候補をアドレスａにより前記の逆引きテーブルから検索し、候補中で
ｙ・ｇ−ｊ＝ｇｂｉ    を充たす候補の値をｉの値として出力し、  ｙ・ｇ−ｊ＝ｇｂｉ    を充たす候補がテーブルに存在しないと、次のｊの値に対してべき乗手段がｙ・ｇ−ｊを求めることを要求するための検索手段と、
検索手段から出力されたｉの値に対して、  ｘ＝ｉ・ｂ＋ｊ  を演算し出力するための演算手段、とを設けたことを特徴とする、離散対数処理装置。  
【請求項２】
前記検索手段は、ｉの値の候補に対してｇｂｉ  を求めて、ｙ・ｇ−ｊと一致するものをｉの値として出力するための手段を備えていることを特徴とする、請求項１の離散対数処理装置。
【請求項３】
テーブル内のアドレスを増す方向もしくはアドレスを減ずる方向のいずれか一方をアドレス方向として、
前記逆引きテーブルは１個のテーブル内アドレスａに対して複数のｉの値の候補を記述する欄を備え、かつアドレスａに対応するｉの値の候補を、アドレスａの欄もしくはアドレス方向に沿ってそれ以降の空欄に記述するように前記逆引きテーブルを作成し、
前記検索手段は、アドレスａから始めてアドレス方向に沿って最初の空欄の前の欄までをｉの値の候補として読み出すようにしたことを特徴とする、請求項１または２の離散対数処理装置。
【請求項４】
前記逆引きテーブルに第１テーブルと第２テーブルとを設けて、
第１テーブルでは、ｉの値の候補が１個のみ存在する場合その値を記述し、ｉの値の候補が複数存在する場合ｉの値の候補を検索するための第２テーブルでのアドレスを記述し、ｉの値の候補が存在しない場合その旨を記述し、
第２テーブルでは、第１テーブルに記述された第２テーブルでのアドレスに、ｉの値の候補を記述したことを特徴とする、請求項１または２の離散対数処理装置。
【請求項５】
前記逆引きテーブルに、ｉの値の候補とｙ・ｇ−ｊ中のビット列の一部でアドレスａとは異なる他のデータを記述し、検索手段では前記他のデータがｙ・ｇ−ｊ中のビット列と一致するものを選択するようにしたことを特徴とする、請求項１の離散対数処理装置。
【請求項６】
ユーザのIDを一方向性関数ｈで処理して整数変数ｙを求めると共に、  法をｐとして、整数の底ｇとに対し、  ｙ＝ｇｘ    を充たす整数変数ｘを秘密鍵として求めるための、公開鍵暗号システムでのセンター装置において、
整数変数ｊに対し、ｙ・ｇ−ｊをｊの値毎に求めるためのべき乗手段と、
べき乗手段で求めたｙ・ｇ−ｊにより生成され、かつｙ・ｇ−ｊよりもデータ長が短い整数データａをテーブル内アドレスとし、ｂを整数として、  ｙ・ｇ−ｊ＝ｇｂｉ    を充たす整数変数ｉの値の候補を記述した逆引きテーブルと、
ｉの値の候補をアドレスａにより前記の逆引きテーブルから検索し、候補中で
ｙ・ｇ−ｊ＝ｇｂｉ    を充たす候補の値をｉの値として出力し、  ｙ・ｇ−ｊ＝ｇｂｉ    を充たす候補がテーブルに存在しないと、次のｊの値に対してべき乗手段がｙ・ｇ−ｊを求めることを要求するための検索手段と、
検索手段から出力されたｉの値に対して、  ｘ＝ｉ・ｂ＋ｊ  を演算し出力するための演算手段、とを設けたことを特徴とする、センター装置。  
【請求項７】
テーブル内のアドレスを増す方向もしくはアドレスを減ずる方向のいずれか一方をアドレス方向として、前記逆引きテーブルは１個のテーブル内アドレスａに対して複数のｉの値の候補を記述する欄を備え、かつアドレスａに対応するｉの値の候補を、アドレスａの欄もしくはアドレス方向に沿ってそれ以降の空欄に記述するように前記逆引きテーブルを作成し、
前記検索手段は、アドレスａから始めてアドレス方向に沿って最初の空欄の前の欄までをｉの値の候補として読み出すようにしたことを特徴とする、請求項６のセンター装置。
【請求項８】
法をｐとして、整数変数ｙと整数の底ｇとに対し、  ｙ＝ｇｘ    を充たす整数変数ｘを秘密鍵として求めるための、離散対数処理プログラムにおいて、
整数変数ｊに対し、ｙ・ｇ−ｊをｊの値毎に求めるためのべき乗命令と、
べき乗手段で求めたｙ・ｇ−ｊにより生成され、かつｙ・ｇ−ｊよりもデータ長が短い整数データａをテーブル内アドレスとし、ｂを整数として、  ｙ・ｇ−ｊ＝ｇｂｉ    を充たす整数変数ｉの値の候補を記述した逆引きテーブルを記憶するための命令と、
ｉの値の候補をアドレスａにより前記の逆引きテーブルから検索し、候補中で
ｙ・ｇ−ｊ＝ｇｂｉ    を充たす候補の値をｉの値として出力し、  ｙ・ｇ−ｊ＝ｇｂｉ    を充たす値がテーブルに存在しないと、次のｊの値に対してべき乗命令がｙ・ｇ−ｊを求めることを要求するための検索命令と、
検索命令から出力されたｉの値に対して、  ｘ＝ｉ・ｂ＋ｊ  を演算し出力するための演算命令、とを設けたことを特徴とする、離散対数処理プログラム。  
【請求項９】
テーブル内のアドレスを増す方向もしくはアドレスを減ずる方向のいずれか一方をアドレス方向として、前記逆引きテーブルは１個のテーブル内アドレスａに対して複数のｉの値の候補を記述する欄を備え、かつアドレスａに対応するｉの値の候補を、アドレスａの欄もしくはアドレス方向に沿ってそれ以降の空欄に記述するように前記逆引きテーブルを作成し、
前記検索命令は、アドレスａから始めてアドレス方向に沿って最初の空欄の前の欄までをｉの値の候補として読み出すようにしたことを特徴とする、請求項８の離散対数処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は離散対数処理装置やこれを用いた公開鍵暗号システムのセンター装置、離散対数処理プログラムに関し、例えば公開鍵暗号システムでの秘密鍵の発生や、電子署名システムでの署名用の鍵の発生に関する。
【背景技術】
【０００２】
発明者らは、ユーザのIDを基礎にしてセンターが秘密鍵を作成する公開鍵暗号システムを提案してきた（特許文献１〜３，非特許文献１〜３）。この場合、公開鍵はユーザのIDからユーザ端末で作成できるものを使用する。このシステムではセンターのみがユーザのIDから秘密鍵を作成できることが必要で、このための手法として、ユーザが解くことが計算時間上不可能な離散対数問題がある。また離散対数問題は、他の公開鍵暗号システムや電子署名システムでも使用される（特許文献４〜６）。
【０００３】
離散対数問題の解法には、離散対数の法ｎが  ｎ＝ｐｑｒｓ＋１  などと表される場合に、素数ｐ，ｑ，ｒ，ｓを用いたより小さな離散対数問題に変換するためのPohlig-
Hellman法と、ｐ，ｑ，ｒ，ｓ等を用いた個々の離散対数問題を解くためのBaby Step/
Giant Step法とを組み合わせることが実用的である。しかしながらBaby Step/Giant Step法のBaby Stepでは、ｐの２乗根のオーダーの巨大な回数だけ、テーブルを検索しなければならない。例えば離散対数問題に５１２ビット程度の素数ｎを用いたとし、Pohlig-
Hellman法でこれを６４ビット程度の素数ｐを用いた問題に変換したとする。ｂを３２ビット程度の数とし、ｇを公開された離散対数の底とし、Ｇ＝ｇｂとする。Baby Stepでは、２３２回＝２ｂ回程度べき乗演算を行ってＧｉの値の候補を求め、Giant Stepで作成済みのテーブルを参照して、Ｇｉの候補と一致するものが存在すると、テーブルからｉを読み出す。テーブルにＧｉの値（５１２ビット長データ）とｉの値（例えば３２ビット長データ）とを記述すると、テーブルの各欄には５４４ビットの容量が必要で、テーブルの総容量はその２３２倍の２４１ビット程度となる。テーブルの容量は２テラビット程度で、メインメモリーに記憶させるのには無理があり、ディスクメモリに記憶させることになる。次にテーブル内のデータを２分木によりソートしておいたとして、毎回３０回程度のテーブルの参照が必要になり、２分木では参照するテーブルのアドレスが毎回離れているので、参照時間も長くなる。このため、Baby Stepの実行に必要なテーブルの容量が大きく、かつテーブルの参照に時間が必要である。従って、充分に安全な離散対数問題を使用するには、小さなテーブルを高速で参照できるようにして、Baby Stepの実行時間を短縮する必要がある。
【特許文献１】特開２００２−２９０３８８
【特許文献２】特開２００２−１１８５４４
【特許文献３】特開平１０−３３８１９０
【特許文献４】特開平１１−２０２７６６１
【特許文献５】特開平１１−１７４９５５
【特許文献６】特開平８−１０２７３４
【非特許文献１】村上，笠原:”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
【発明の開示】
【発明が解決しようとする課題】
【０００４】
この発明の課題は、離散対数問題を小さな容量のテーブルを用い、かつ少ない参照回数で解けるようにすることにある。
この発明での副次的な課題は、テーブルに  ｙ・ｇ−ｊ＝ｇｂｉ    を充たす整数変数ｉの候補が複数存在する場合の、具体的な対策を提供することにある。
この発明での他の副次的な課題は、テーブルの具体的な構成を提供することにある。
【課題を解決するための手段】
【０００５】
この発明は、法をｐとして、整数変数ｙと整数の底ｇとに対し、  ｙ＝ｇｘ    を充たす整数変数ｘを求めるための離散対数処理装置において、
整数変数ｊに対し、ｙ・ｇ−ｊをｊの値毎に求めるためのべき乗手段と、
べき乗手段で求めたｙ・ｇ−ｊにより生成され、かつｙ・ｇ−ｊよりもデータ長が短い整数データａをテーブル内アドレスとし、ｂを整数として、  ｙ・ｇ−ｊ＝ｇｂｉ    を充たす整数変数ｉの値の候補を記述した逆引きテーブルと、
ｉの値の候補をアドレスａにより前記の逆引きテーブルから検索し、候補中で
ｙ・ｇ−ｊ＝ｇｂｉ    を充たす候補の値をｉの値として出力し、  ｙ・ｇ−ｊ＝ｇｂｉ    を充たす候補がテーブルに存在しないと、次のｊの値に対してべき乗手段がｙ・ｇ−ｊを求めることを要求するための検索手段と、
検索手段から出力されたｉの値に対して、  ｘ＝ｉ・ｂ＋ｊ  を演算し出力するための演算手段、とを設けたことを特徴とする。
【０００６】
好ましくは、前記検索手段は、ｉの値の候補に対してｇｂｉ  を求めて、ｙ・ｇ−ｊと一致するものをｉの値として出力するための手段を備えている。
【０００７】
また好ましくは、テーブル内のアドレスを増す方向もしくはアドレスを減ずる方向のいずれか一方をアドレス方向として、
前記逆引きテーブルは１個のテーブル内アドレスａに対して複数のｉの値の候補を記述する欄を備え、かつアドレスａに対応するｉの値の候補を、アドレスａの欄もしくはアドレス方向に沿ってそれ以降の空欄に記述するように前記逆引きテーブルを作成し、
前記検索手段は、アドレスａから始めてアドレス方向に沿って最初の空欄の前の欄までをｉの値の候補として読み出す。
【０００８】
好ましくは、前記逆引きテーブルに第１テーブルと第２テーブルとを設けて、
第１テーブルでは、ｉの値の候補が１個のみ存在する場合その値を記述し、ｉの値の候補が複数存在する場合ｉの値の候補を検索するための第２テーブルでのアドレスを記述し、ｉの値の候補が存在しない場合その旨を記述し、
第２テーブルでは、第１テーブルに記述された第２テーブルでのアドレスに、ｉの値の候補を記述する。
【０００９】
好ましくは、前記逆引きテーブルに、ｉの値の候補とｙ・ｇ−ｊ中のビット列の一部でアドレスａとは異なる他のデータを記述し、検索手段では前記他のデータがｙ・ｇ−ｊ中のビット列と一致するものを選択する。
【００１０】
またこの発明は、ユーザのIDを一方向性関数ｈで処理して整数変数ｙを求めると共に、  法をｐとして、整数の底ｇとに対し、  ｙ＝ｇｘ    を充たす整数変数ｘを秘密鍵として求めるための、公開鍵暗号システムでのセンター装置において、
整数変数ｊに対し、ｙ・ｇ−ｊをｊの値毎に求めるためのべき乗手段と、
べき乗手段で求めたｙ・ｇ−ｊにより生成され、かつｙ・ｇ−ｊよりもデータ長が短い整数データａをテーブル内アドレスとし、ｂを整数として、  ｙ・ｇ−ｊ＝ｇｂｉ    を充たす整数変数ｉの値の候補を記述した逆引きテーブルと、
ｉの値の候補をアドレスａにより前記の逆引きテーブルから検索し、候補中で
ｙ・ｇ−ｊ＝ｇｂｉ    を充たす候補の値をｉの値として出力し、  ｙ・ｇ−ｊ＝ｇｂｉ    を充たす候補がテーブルに存在しないと、次のｊの値に対してべき乗手段がｙ・ｇ−ｊを求めることを要求するための検索手段と、
検索手段から出力されたｉの値に対して、  ｘ＝ｉ・ｂ＋ｊ  を演算し出力するための演算手段、とを設けたことを特徴とする。
【００１１】
好ましくはセンター装置では、テーブル内のアドレスを増す方向もしくはアドレスを減ずる方向のいずれか一方をアドレス方向として、前記逆引きテーブルは１個のテーブル内アドレスａに対して複数のｉの値の候補を記述する欄を備え、かつアドレスａに対応するｉの値の候補を、アドレスａの欄もしくはアドレス方向に沿ってそれ以降の空欄に記述するように前記逆引きテーブルを作成し、
前記検索手段は、アドレスａから始めてアドレス方向に沿って最初の空欄の前の欄までをｉの値の候補として読み出す。
【００１２】
またこの発明は、法をｐとして、整数変数ｙと整数の底ｇとに対し、  ｙ＝ｇｘ    を充たす整数変数ｘを秘密鍵として求めるための、離散対数処理プログラムにおいて、
整数変数ｊに対し、ｙ・ｇ−ｊをｊの値毎に求めるためのべき乗命令と、
べき乗手段で求めたｙ・ｇ−ｊにより生成され、かつｙ・ｇ−ｊよりもデータ長が短い整数データａをテーブル内アドレスとし、ｂを整数として、  ｙ・ｇ−ｊ＝ｇｂｉ    を充たす整数変数ｉの値の候補を記述した逆引きテーブルを記憶するための命令と、
ｉの値の候補をアドレスａにより前記の逆引きテーブルから検索し、候補中で
ｙ・ｇ−ｊ＝ｇｂｉ    を充たす候補の値をｉの値として出力し、  ｙ・ｇ−ｊ＝ｇｂｉ    を充たす値がテーブルに存在しないと、次のｊの値に対してべき乗命令がｙ・ｇ−ｊを求めることを要求するための検索命令と、
検索命令から出力されたｉの値に対して、  ｘ＝ｉ・ｂ＋ｊ  を演算し出力するための演算命令、とを設けたことを特徴とする。
【００１３】
好ましくは離散対数処理プログラムでは、テーブル内のアドレスを増す方向もしくはアドレスを減ずる方向のいずれか一方をアドレス方向として、前記逆引きテーブルは１個のテーブル内アドレスａに対して複数のｉの値の候補を記述する欄を備え、かつアドレスａに対応するｉの値の候補を、アドレスａの欄もしくはアドレス方向に沿ってそれ以降の空欄に記述するように前記逆引きテーブルを作成し、
前記検索命令は、アドレスａから始めてアドレス方向に沿って最初の空欄の前の欄までをｉの値の候補として読み出す。
【発明の効果】
【００１４】
この発明では、ｙ・ｇ−ｊを求めると、それからアドレスａを発生させて、そのアドレスでテーブルを検索する。次に  ｙ・ｇ−ｊ＝ｇｂｉを充たす候補がテーブルにない場合、降順あるいは昇順で次のｊに対して、べき乗あるいは別のテーブルを参照してｙ・ｇ−ｊを求める。ｉの値の候補がテーブルに存在すると、１個の場合それがｉの値であり、複数個の場合ｙ・ｇ−ｊ＝ｇｂｉを充たすｉの値を出力する。
【００１５】
この手続を所定のｊの範囲に対して繰り返せばｉの値は一意に求まる。発明の効果を数例で説明すると、ｉの値の候補が２３２個存在し、ｙ・ｇ−ｊのデータ長が５１２ビット、アドレスａのデータ長が３２ビットとする。従来例でのテーブルの規模は、各行に対してｙ・ｇ−ｊで５１２ビット，ｉで３２ビットで計５４４ビットで、行数が２３２である。この発明では、ｙ・ｇ−ｊはテーブルのデータではなく、データ長を圧縮した形でアドレスに用いられている。アドレスａに重複があること、即ち同じアドレスａに対してｉの候補の値が複数個存在することを無視すると、１行のデータはｉの値のみの３２ビットで、行数が２３２で合計のデータ量は２３７となり、従来例の約１／１６となる。ただし実際には重複の処理のためにテーブルのデータ量を２〜４倍程度にするのが好ましく、実用的にはテーブルの規模を前記の従来例の１／８〜１／４にできる。このため安全な離散対数問題を解くのに必要なテーブルの規模を実装可能なものにできる。
【００１６】
ｉの候補の探索はｊを変数として例えばｂ回程度繰り返し、２分木ではテーブルの参照回数はｂ回×３０回（log２ａmax）程度となる。２分木で参照するアドレスは毎回大きく変わるので、大きなテーブルに対して不連続な別々のアドレスで多数回参照する。この発明ではテーブルの参照は各ｊの値に対して基本的に１回で、ｉの値の候補が複数存在する場合でも、数回程度テーブルを参照するか、あるいはアドレスａから連続してテーブルの各行を読み出せばよく、テーブルの参照に要する時間を短縮できる。このため離散対数を解くのに必要な処理時間も短縮できる。この発明は、離散対数を解くことに使用でき、例えば公開鍵暗号システムでのセンター装置や、公開鍵暗号用や電子署名用にユーザ端末に実装すると良い。
【００１７】
テーブルのｉの値の候補が正しいかどうかを確認するため、例えばその値を用いてｇｂｉをべき乗演算もしくはテーブルなどを用いて算出し、ｙ・ｇ−ｊの値と一致するかどうかを行うと良い。ただしアドレスａのデータ長が長く、誤った候補が記載されている確率が充分に低い場合は、べき乗による確認を省略できる。
【００１８】
テーブルの規模を小さくしながら重複を処理することを検討する。テーブルのアドレスａのデータ長を増すと重複確率は減少するが、アドレス空間に比例してテーブルの規模が増す。ここで好ましくは、１つのアドレスａに対してデータをＦ行設け、Ｆは複数で例えば２〜４，好ましくは２または３とし、作表時にアドレスａもしくはそれ以降のアドレスの空欄にｉの値の候補を記述する。この場合、作表時にアドレスが共通するデータを事前にソートする必要がない。そして検索時には、アドレスａから始めてデータの無い欄（行）までのデータを読み出せば、１回の検索を終了できる。
【００１９】
また好ましくはテーブルを第１テーブルと第２テーブルに分割し、ｉの値の候補に重複が無い場合、第１テーブルにｉの値の候補を記述し、重複がある場合、第２テーブルでのアドレスを記述する。すると第１テーブルでは例えば１つのアドレスａに対してデータを１行設ければ良く、メモリ規模を最小にできる。第２テーブルは１つのテーブルでも、例えば１方向にリンクする複数のテーブルでも良い。
【００２０】
テーブルに、ｙ・ｇ−ｊのビット列の一部でアドレスａとは独立したものを記載すると、これからｉの値の候補が正しいかどうかを確認できる。従って確認用のべき乗演算を大部分不要にできる。
【発明を実施するための最良の形態】
【００２１】
以下に本発明を実施するための最適実施例を示す。
【実施例】
【００２２】
図１〜図７に、実施例とその変形とを示す。なお各変形例は逆引きテーブル３０，４０以外の部分は実施例と同様であり、実施例に関する記載は、逆引きテーブルに関する部分以外は、全てそのまま各変形例に当てはまる。離散対数問題を使用した公開鍵暗号システムでのセンター装置２を例に実施例を説明すると、４はユーザＡのユーザ端末、５はユーザＢのユーザ端末である。ユーザ端末４，５は物理的にはパーソナルコンピュータ６などで構成され、一方向性関数６と鍵生成部１０とを備えている。そして一方向性関数６はユーザのIDを整数型の変数ｅに変換し、鍵生成部１０はユーザＡがユーザＢと秘密の通信を行う際に、ユーザＢのIDから一方向性関数６で求めた変数ｅBと自己の秘密のデータSAとからｅB２SAを、秘密鍵として生成する。なお秘密のデータSAはセンター装置２が生成し、各ユーザに配布する。
【００２３】
ユーザ端末４は、自己のIDを通信を介してあるいは郵便などで、センター装置２へ入力する。１０は通信部で、１２は一方向性関数で、IDに対して、整数型の出力ｅを出力する。ここでは離散対数の法として公開の合成数Ｎを用い、  Ｎ＝ＰＱ  （Ｐ，Ｑは秘密の素数）とし、 Ｐ＝Πｐiｅｉ＋１  Ｑ＝Πｑiｅｊ＋１  （ｐi，ｑiは秘密の素数，ｅi，ｅjは秘密の正整数、ｉ，ｊは各々１〜ｆと１〜ｆ’）とする。またｇを法Ｎを用いた離散対数の公開の底とする。例えば  ｙ＝ｅA，  ｙ≡ｇｘ  modＮ  とする。
【００２４】
１６は離散対数算出部で、ｐi,ｑj等の素因数毎に設け、 ｐiｅｉ＝ｐ'i とし、かつ
ｇ'≡ｇ（Ｐ−１）／ｐ’ｉ  modＰ として、  ｙ≡ｇ'ｘ  modｐi となるｘを、ｘpiとして求める。同様に、 ｑjｅj＝ｑ'j とし、  ｇ''≡ｇ（Ｑ−１）／ｑ’j modＱ として ｙ≡ｇ''ｘ  modｑj となるｘを  ｘqjとして求める。なおＰ−１，Ｑ−１がｐi２，ｑj３等の素因数を含む場合、離散対数算出部１６でｅiやｅjのべき指数回処理を繰り返す。この処理がBaby  Step/Giant Stepの処理である。次にＰ−１の各因数についてｘpiを求めると、中国式剰余定理により、Ｐを法として ｙ≡ｇｘP  modＰ となるｘPや、Ｑを法として ｙ≡ｇｘｑ  modＱ となるｘQを、
Pohlig-Hellman法により部分鍵演算部１７，１７で求める。鍵演算部１８は、法Ｐに対する離散対数ｘPと法Ｑに対する離散対数ｘQを用い、中国式剰余定理により
ｘ≡ｘP (modＰ−１) かつ ｘ≡ｘQ (modＱ−１) となるｘを求め、これを秘密のデータSAとして通信部１０などからユーザ端末４へ出力する。センター装置２を介さない公開鍵暗号システムや電子署名用に、ユーザ端末４，５に離散対数算出部１６，部分鍵演算部１７，鍵演算部１８を設けても良い。
【００２５】
以下では簡単のため、Ｐ−１の一次の素因数ｐ（Ｐ−１はｐの倍数であるがｐ２の倍数ではない）について、説明する。またｉ，ｊは素因数ｐi，ｑjを表すために用いた添字とは別のものとする。ｐの２乗根程度の大きさの数ｂおよびｃに対し、０ 〜ｃ−１ までの整数型変数ｉに対し、ｇｂｉ（ｇｂ＝Ｇ）を求めてテーブルに記録する。次にBaby Stepでは、０〜ｂ−１ までのｊに対して、ｙ・ｇ−ｊを求めて、これと一致するデータがテーブルに記載されていれば、このデータをｉの値として出力し、記載されていなければ次のｊを探索する。実施例ではｉやｊの値、あるいはテーブルのアドレスは小さなものから大きなものへの順で説明するが、その逆に大きなものから小さなものへの順で処理しても良い。実施例ではテーブルのサイズを小さくすると共に、テーブルを検索する回数を減らして、離散対数の処理に必要なメモリの規模並びに処理時間を共に小さくする。
【００２６】
図２に実施例での離散対数算出部１６を示すと、２０は逆引きテーブルで、テーブル内のアドレスをａとすると、各アドレスａに対して２行分のデータ、即ち２つのｉの値の候補を記述できるようにしてある。逆引きテーブル２０のアドレスは０ 〜ｃ−１ までで、１つのアドレスに対して設ける行の数Ｆを２とし、Ｆの値は好ましくは２〜４，特に好ましくは２または３とする。さらにテーブル２０の終わりにｉの値の候補が多数存在する場合に備え、アドレスａ−１の次に例えば１００行〜２００行分程度の追加の行を設けておく。テーブル２０の各行（各欄）にはｉの値の候補を１個記載する。ｉの値の候補が存在しない場合、各欄のデータはnullとなる。
【００２７】
図１の一方向性関数１２から、  ｙ＝ｅA modＰ となるｙが入力されると、べき乗手段２２は、
Ｇｉ＝ｙ・ｇ−ｊ                                            (1)
となるｉを探索するため ｙ・ｇ−ｊ modＰ を算出する。この数をＧｉということがある。  ｙ・ｇ−ｊは文字通りにべき乗演算で求めてもよく、あるいはｇ−ｊのテーブルで作成しても良い。マスク２４はＧｉのうち例えば下位３２ビットをアドレスａとして出力する。なおａのデータ長はｂのデータ長程度が好ましく、マスク２４はＧｉの任意のｕビットをアドレスａとして出力でき、あるいはＧｉをハッシュしてアドレスａを作成しても良い。
【００２８】
アドレスａが与えられると、テーブル２０のアドレスａの２つの欄の上側から、アドレスの増す方向に沿って、最初の空欄の前の欄までのデータを読み出す。読み出しでは、例えば４行ないし１０行程度を連続して読み出すと効率的である。テーブル２０を作表する際に、アドレスａの上側の欄ａ／０が空欄であれば、アドレスａ−１／１が空欄かどうかを問わず、アドレスａ／０にｉの値を記載すると、作表が容易になる。これに代えて、アドレスａ−１／１にデータが既に記載されている場合、アドレスａ／０を空欄として、アドレスａ／１からデータを記載すると、複数のデータが空欄無しでつながった領域を、空欄で分離しやすい。
【００２９】
例えば図２で、アドレスａによりテーブル２０を参照しているとすると、アドレスａ／０からアドレスａ＋２／０まで空欄無しにデータが連続しているので読み出し、べき乗手段２６で、各欄に記載されているｉの値の候補ｉ*に対し、Ｇｉ＊を求める。比較手段２８はべき乗手段２２で求めた ｙ・ｇ−ｊと、べき乗手段２６で求めたＧｉ＊とを比較し、これが一致する場合、ｉの値（ｉ*）を演算部２９へ出力し、演算部２９で
ｘp＝ｉ・ｂ＋ｊ                                         (2)
を求めて出力する。またｙ・ｇ−ｊとＧｉ＊とが一致しない場合、べき乗手段２２に対し、次のｊに対して処理を行うように要求する。
【００３０】
実施例の作表アルゴリズムを図３に示す。法ｐに対してｂｃがｐよりも大きくなるようにｂ及びｃを定める。例えば法ｐが６４ビット程度の素数であれば、ｂやｃは共に３２ビット程度となり、図３の作表アルゴリズムではｉの初期値を０として、ｃ−１までの各ｉに対して、テーブル２０にデータを約２３２回書き込む（ステップ１〜６）。ステップ２で各ｉに対してＧｉを求め、そのうちの所定のｕビット、例えば下位３２ビットをａとして（ステップ３）、テーブル２０のアドレスａ／０からスタートして、最初の空欄にｉの値を書き込む（ステップ４）。次いでｉの値を１増加し（ステップ５）、ｃに達していれば作表を終了する。
【００３１】
図４にテーブル２０の読み出しアルゴリズムを示すと、ｊ＝０〜ｂ−１ まで約２３２回処理を繰り返すが、途中で正しいｉの値を発見した場合、ステップ１８で処理を終了する。またｊがｂに達する前に必ずｉの値を求め得るはずなので、ｊがｂ以上かどうかをチェックするステップは任意である。
【００３２】
ステップ１０でｊの初期値を０とし、ステップ１１でＧｉを求め、Ｇｉの所定のｕビットをアドレスａとする（ステップ１２）。次いでテーブル２０をアドレスａの上側の欄から参照を開始し、途中で正しいｉの値を発見できなければ、空欄が表れる欄まで読み出して（ステップ１３）、空欄の前の欄までのデータを利用する。Ｇｉ＝ｙ・ｇ−ｊ  充たすｉの値が存在する場合、読み出した範囲内に正しいｉの値が必ず含まれている。そこで読み出したｉの値の候補から、ｇｂｉを求めて、これをＧｉ＊とし（ステップ１４）、Ｇｉ＝Ｇｉ＊となるものが存在しない場合、次のｊに対する処理を行い、存在する場合この値を求めてｘpを算出する（ステップ１５〜ステップ１８）。
【００３３】
以上の手順によると、テーブル２０にＧｉのデータを記述する必要がないので、１行当たりのデータ長が５４４ビットから３２ビットの約１／１７になる。１つのアドレスに対して２つの欄を設けるので、テーブル全体のデータ量は従来例の約１／８となる。次にテーブル２０の参照時間では、２分木を用いて約３０回テーブルの別々のアドレスを参照する必要はなく、アドレスａ／０から始まる連続した複数行のデータを読み出せばよいので、参照時間は１／１０のオーダーとなる。この結果、離散対数を解くためのテーブルの容量も処理時間も著しく小さくできる。
【００３４】
図５に変形例の逆引きテーブル３０を示し、マスク２４には図２のべき乗手段２２からＧｉを入力し、比較手段２８からは図２の演算部２９へｉの値を出力する。逆引きテーブル３０には、アドレスａ毎に１行分のデータを記述し、Ｆの値は１となる。テーブル３０にはデータが空欄（００）、同じアドレスにｉの値の候補が複数存在するので、補助テーブル３２での参照アドレスｂ’を記述（０１）、ｉの候補の値を記述（１０）のフラグを記述する。そしてフラグの値が例えば（０１）の場合、テーブル３０に記述されたアドレスｂ’により補助テーブル３２のアドレスｂ’を参照する。補助テーブル３２にｉの候補の値ｉ1と次のｉの値の候補ｉ2が存在する場合、テーブル３２でのｉ1の欄にｉ2のアドレスｃ’が記述されている。このようにしてテーブル３２のアドレスｂ’から始めて、次のアドレスの欄が空欄となるまで参照を続けると、アドレスａに対応する全てのｉの値の候補を読み出すことができる。ここで補助テーブル３２の作成前に、アドレスａによるソートを行い、テーブル３０に対するアドレスａの値が共通のものは、補助テーブル３２内で上下にまとめても良い。すると補助テーブル３２の参照が簡単になり、かつ補助テーブル３２には次のアドレスではなく、同じアドレスａに対するデータの終わりを示すフラグ、例えば図５の鎖線内の０を記載すれば良く、データ長を短くできる。
【００３５】
図６は第３の変形例を示し、マスク２４には図２のべき乗手段２２からＧｉを入力し、比較手段２８からｉを図２の演算部２９へ入力し、次のｊについてＧｉを求めるとの要求をべき乗手段２２に入力する。テーブル４０では１つのアドレスａに対して２行のデータを記載する。アドレスａの各行には、Ｇｉでのａ以外の他の３２ビット等の充分長いデータと、ｉの値の候補、並びにＧｉから求めた正しいアドレス（重複が無い場合に有るべきアドレス）ａ’を知るために、  ａ−ａ’＝Δ  を記載する。従ってアドレスａのデータであればΔは０で、重複のため本来のアドレスよりも下の行に記載されていると、その行数を２で割ったものがΔとして記載されている。各行にはａ以外にＧｉの他の３２ビット等のデータが記載されているので、正しくない候補を誤ってｉの値として採用する確率は１０億分の１以下で、実際上無視できる。この結果、べき乗手段２６による検証をほぼ省略できる。
【００３６】
図７にセンター装置のプログラム５０を示すと、離散対数以外の一般的なセンターに関する命令、即ち一般センター命令５２と離散対数命令５４とを備えている。離散対数命令５４には、図２などのテーブルを作成するためのテーブル作成命令５６と、テーブルからの読み出しを行うためのテーブル読み出し命令５８とを設けてある。テーブル作成命令５６では、プログラム５０内のデータとして作成済みの完全なテーブルをメインメモリあるいはディスクストレージなどに記憶する命令としても良く、もしくはテーブル２０，３０，４０，３２を文字通りに作表する命令としても良い。テーブル作成命令５６は例えば図３の作表アルゴリズムに従い、テーブル読み出し命令５８は、図２，図５，図６の各テーブルを読み出すためのアルゴリズムを記述した命令である。
【００３７】
なおＰやＱを  Ｐ＝２ｄｐｅ＋１，  Ｑ＝２ｄ’ｑｅ’＋１（ｄ，ｅ，ｄ’，ｅ’は正整数、ｐ，ｑは素数）の形にすると、２ｄ等の位数の離散対数問題を解くのにテーブルは不要で、素数ｐ，ｑを法とする離散対数問題を解くための各１枚のテーブルのみでよい。またＰ−１等を、２α３β５δ７θ…などの小さな素数のべき乗と、大きな素数ｐｅとの積で構成しても同様に、１枚のテーブルでＰを法とする離散対数問題を解くことができる。
【図面の簡単な説明】
【００３８】
【図１】実施例のセンター装置とユーザ端末とを示すブロック図
【図２】実施例での逆引きテーブルを模式的に示す図
【図３】逆引きテーブルの作成アルゴリズムを示すフローチャート
【図４】実施例での逆引きテーブルの読み出しアルゴリズムを示すフローチャート
【図５】変形例での逆引きテーブルを模式的に示す図
【図６】第２の変形例での逆引きテーブルを模式的に示す図
【図７】実施例でのセンタープログラムのブロック図
【符号の説明】
【００３９】
２                センター装置
４，５            ユーザ端末
６                一方向性関数
７                鍵生成部
１０              通信部
１２              一方向性関数
１６              離散対数算出部
１７              部分鍵演算部
１８              鍵演算部
２０，３０，４０  逆引きテーブル
３２              補助テーブル
２２，２６        べき乗手段
２４              マスク
２８              比較手段
２９              演算部
５０              センタープログラム
５２              一般センター命令
５４              離散対数命令
５６              テーブル作成命令
５８              テーブル読み出し命令
【図１】
2007128001.tif 000003
【図２】
2007128001.tif 000004
【図３】
2007128001.tif 000005
【図４】
2007128001.tif 000006
【図５】
2007128001.tif 000007
【図６】
2007128001.tif 000008
【図７】
2007128001.tif 000009