(57)【要約】【課題】  ３素数の積からなる法ｎを用いた離散対数問題を解く。【解決手段】  ＩＤをハッシュ関数により既約剰余系Ｚn＊の元ｅkに変換し、ヤコビ記号(ｅk／ｎ)が１か−１かにより、ｅkをｅk'（ｅk'＝ｅkまたはαｅk）に変換する。ルジャンドル記号(ｅk'／ｐ)が１か−１かにより、ｅk'をｅk''（ｅk''＝ｅk'または−ｅk'）に変換する。ｅk''を法ｐ，ｑ，ｒに関し底をｇとして離散対数を求め、中国人の剰余定理により鍵Ｓkを求める。【選択図】    図３
2007181001.tif 000002
【特許請求の範囲】
【請求項１】
整数ｇを底とし法を整数ｎとする整数ｅの離散対数を、ユーザの秘密の鍵Ｓとして求める鍵生成装置において、
前記法ｎを３つの秘密の素数ｐ,ｑ,ｒの積とし(ｎ＝ｐｑｒ)、
ｎを法とする既約剰余系Ｚn＊中で、ヤコビ記号(ｘ／ｎ)が１となる元の集合をＺn＃とし、
Ｚn＃の元でかつ位数が最大の巡回乗法群の生成元ｇを、その巡回乗法群を〈ｇ〉nとして、−１が〈ｇ〉nに属さず、かつヤコビ記号(ｇ／ｎ)が１となるように定め、
前記の素数ｐ,ｑ,ｒを、(ｐ−１)／２,(ｑ−１)／２,(ｒ−１)／２が互いに素で、かつｎ＝ｐｑｒをヤコビ記号(−１／ｎ)が１となるように定めて、
ｇ＝ｇp２  modｐ   
ｇ＝ｇq   modｑ   
ｇ＝ｇr   modｒ  (ｇp,ｇq,ｇrは各々正整数)とし、
αがＺn＊の元でＺn＃の元ではないものとして、
前記ｅに対しヤコビ記号(ｅ／ｎ)が１か−１かを求めるためのヤコビ記号計算手段と、
求めたヤコビ記号(ｅ／ｎ)が−１の際にｅ'＝αｅとし、ヤコビ記号が１の際にｅ'＝ｅとするための乗算手段と、
前記ｅ'に対し、ルジャンドル記号(ｅ'／ｐ)が１か−１かを求めるためのルジャンドル記号計算手段と、
求めたルジャンドル記号(ｅ'／ｐ)が−１の際にｅ''＝−ｅ'とし、ルジャンドル記号が１の際にｅ''＝ｅ'とするための乗算手段を設け、
さらにｅ''のｐ,ｑ,ｒを法とする３つの離散対数ｘp,ｘq,ｘrを求めるための手段と、
求めた離散対数ｘp,ｘq,ｘrと
Ｓ＝ｘp  mod(ｐ-1)
Ｓ＝ｘq  mod(ｑ-1)
Ｓ＝ｘr  mod(ｒ-1)
との関係を持ち、かつｎを法とする鍵Ｓを求めるための中国人の剰余定理計算手段とを備えたことを特徴とする、鍵生成装置。
【請求項２】
ユーザのＩＤを前記の整数ｅへ変換するための一方向性関数ｈ(ｅ＝ｈ(ＩＤ))をさらに設けると共に、前記の法ｎが公開の整数で、
ユーザＡ,Ｂ間の暗号通信用の秘密鍵ＫAB(ＫAB＝ｅB'２ＳA＝ｇ２ＳAＳB,ここにＳA,ＳBはユーザＡ,Ｂの鍵 )を求めるために、鍵Ｓを求めることを特徴とする、請求項１の鍵生成装置。
【請求項３】
鍵生成装置がユーザのＩＤを受け付けて鍵Ｓをユーザに返す、暗号通信用の鍵生成センター装置であることを特徴とする、請求項２の鍵生成装置。
【請求項４】
ヤコビ記号計算手段は、(ｅ／ｐ),(ｅ／ｑ),(ｅ／ｒ)を各々求めてそれらの積をヤコビ記号の値とすることを特徴とする、請求項３の鍵生成装置。
【請求項５】
整数ｇを底とし法を整数ｎとする整数ｅの離散対数を、ユーザの秘密の鍵Ｓとして求める鍵生成装置用の鍵生成プログラムにおいて、
前記法ｎを３つの秘密の素数ｐ,ｑ,ｒの積とし(ｎ＝ｐｑｒ)、
ｎを法とする既約剰余系Ｚn＊中で、ヤコビ記号(ｘ／ｎ)が１となる元の集合をＺn＃とし、
Ｚn＃の元でかつ位数が最大の巡回乗法群の生成元ｇを、その巡回乗法群を〈ｇ〉nとして、−１が〈ｇ〉nに属さず、かつヤコビ記号(ｇ／ｎ)が１となるように定め、
前記の素数ｐ,ｑ,ｒを、(ｐ−１)／２,(ｑ−１)／２,(ｒ−１)／２が互いに素で、かつｎ＝ｐｑｒをヤコビ記号(−１／ｎ)が１となるように定めて、
ｇ＝ｇp２  modｐ   
ｇ＝ｇq   modｑ   
ｇ＝ｇr   modｒ      (ｇp,ｇq,ｇrは各々正整数)とし、
αがＺn＊の元でＺn＃の元ではないものとして、
前記ｅに対しヤコビ記号(ｅ／ｎ)が１か−１かを求めるためのヤコビ記号計算命令と、
求めたヤコビ記号(ｅ／ｎ)が−１の際にｅ'＝αｅとし、ヤコビ記号が１の際にｅ'＝ｅとするための乗算命令と、
前記ｅ'に対し、ルジャンドル記号(ｅ'／ｐ)が１か−１かを求めるためのルジャンドル記号計算命令と、
求めたルジャンドル記号(ｅ'／ｐ)が−１の際にｅ''＝−ｅ'とし、ルジャンドル記号が１の際にｅ''＝ｅ'とするための乗算命令を設け、
さらにｅ''のｐ,ｑ,ｒを法とする３つの離散対数ｘp,ｘq,ｘrを求めるための命令と、
求めた離散対数ｘp,ｘq,ｘrと
Ｓ＝ｘp  mod(ｐ-1)
Ｓ＝ｘq  mod(ｑ-1)
Ｓ＝ｘr  mod(ｒ-1)
との関係を持ち、かつｎを法とする鍵Ｓを求めるための中国人の剰余定理計算命令とを備えたことを特徴とする、鍵生成プログラム。
【請求項６】
ヤコビ記号計算命令は、(ｅ／ｐ),(ｅ／ｑ),(ｅ／ｒ)を各々求めてそれらの積をヤコビ記号の値とすることを特徴とする、請求項５の鍵生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、ユーザやエンティティのＩＤに基づいて鍵を生成する鍵生成装置と鍵生成プログラムとに関する。
【背景技術】
【０００２】
発明者はＩＤに基づいて鍵を生成することを検討し(非特許文献１)、特に２つの素数ｐ,ｑの積からなる合成数を法とする離散対数問題を用いて鍵を生成することを提案した(非特許文献２)。最近阿部らは３素数の積を法とする離散対数問題を用いた鍵生成について提案している(非特許文献３)。しかしながら阿部らはマウラーヤコビ型の鍵生成システムを検討し、マウラーヤコビ型の鍵生成システム自体が必ずしも安全でないため、阿部らの３素数の積を用いた鍵生成システムも必ずしも安全ではないと考えられる。
【非特許文献１】Y.Murakami and M.KaＳhara: "An ID-based key distribution system" Technical Report of IEICE,ISEC90-26, p.p.29-36,Sept.1990
【非特許文献２】Y.Murakami and M.KaＳhara: "The discrete logarithm problem under a composite modulus" Technical Report of IEICE,ISEC90-42, p.p.33-40,Dec.1990
【非特許文献３】W.Abe,N.Kunihiro and K.Ohta: "Maurer-Yacobi ID-based encryption scheme revisited" Proc.ofthe2005 symposium on cryptography and information security, p.p.2011-2016,2005
【発明の開示】
【発明が解決しようとする課題】
【０００３】
この発明の課題は、３素数の積を用いかつ安全な鍵生成システムと鍵生成プログラムとを提供することにある。
【課題を解決するための手段】
【０００４】
この発明は、整数ｇを底とし法を整数ｎとする整数ｅの離散対数を、ユーザの秘密の鍵Ｓとして求める鍵生成装置において、
前記法ｎを３つの秘密の素数ｐ,ｑ,ｒの積とし(ｎ＝ｐｑｒ)、
ｎを法とする既約剰余系Ｚn＊中で、ヤコビ記号(ｘ／ｎ)が１となる元の集合をＺn＃とし、
Ｚn＃の元でかつ位数が最大の巡回乗法群の生成元ｇを、その巡回乗法群を〈ｇ〉nとして、−１が〈ｇ〉nに属さず、かつヤコビ記号(ｇ／ｎ)が１となるように定め、
前記の素数ｐ,ｑ,ｒを、(ｐ−１)／２,(ｑ−１)／２,(ｒ−１)／２が互いに素で、かつｎ＝ｐｑｒをヤコビ記号(−１／ｎ)が１となるように定めて、
ｇ＝ｇp２  modｐ   
ｇ＝ｇq   modｑ   
ｇ＝ｇr   modｒ  (ｇp,ｇq,ｇrは各々正整数)とし、
αがＺn＊の元でＺn＃の元ではないものとして、
前記ｅに対しヤコビ記号(ｅ／ｎ)が１か−１かを求めるためのヤコビ記号計算手段と、
求めたヤコビ記号(ｅ／ｎ)が−１の際にｅ'＝αｅとし、ヤコビ記号が１の際にｅ'＝ｅとするための乗算手段と、
前記ｅ'に対し、ルジャンドル記号(ｅ'／ｐ)が１か−１かを求めるためのルジャンドル記号計算手段と、
求めたルジャンドル記号(ｅ'／ｐ)が−１の際にｅ''＝−ｅ'とし、ルジャンドル記号が１の際にｅ''＝ｅ'とするための乗算手段を設け、
さらにｅ''のｐ,ｑ,ｒを法とする３つの離散対数ｘp,ｘq,ｘrを求めるための手段と、
求めた離散対数ｘp,ｘq,ｘrと
Ｓ＝ｘp  mod(ｐ-1)
Ｓ＝ｘq  mod(ｑ-1)
Ｓ＝ｘr  mod(ｒ-1)
との関係を持ち、かつｎを法とする鍵Ｓを求めるための中国人の剰余定理計算手段とを備えたことを特徴とする。
【０００５】
好ましくは、ユーザのＩＤを前記の整数ｅへ変換するための一方向性関数ｈ(ｅ＝ｈ(ＩＤ))をさらに設けると共に、前記の法ｎが公開の整数で、
ユーザＡ,Ｂ間の暗号通信用の秘密鍵ＫAB(ＫAB＝ｅB'２ＳA＝ｇ２ＳAＳB,ここにＳA,ＳBはユーザＡ,Ｂの鍵 )を求めるために、鍵Ｓを求める。
【０００６】
特に好ましくは、鍵生成装置がユーザのＩＤを受け付けて鍵Ｓをユーザに返す、暗号通信用の鍵生成センター装置である。
【０００７】
最も好ましくは、ヤコビ記号計算手段は、(ｅ／ｐ),(ｅ／ｑ),(ｅ／ｒ)を各々求めてそれらの積をヤコビ記号の値とする。
【０００８】
この発明はまた、整数ｇを底とし法を整数ｎとする整数ｅの離散対数を、ユーザの秘密の鍵Ｓとして求める鍵生成装置用の鍵生成プログラムにおいて、
前記法ｎを３つの秘密の素数ｐ,ｑ,ｒの積とし(ｎ＝ｐｑｒ)、
ｎを法とする既約剰余系Ｚn＊中で、ヤコビ記号(ｘ／ｎ)が１となる元の集合をＺn＃とし、
Ｚn＃の元でかつ位数が最大の巡回乗法群の生成元ｇを、その巡回乗法群を〈ｇ〉nとして、−１が〈ｇ〉nに属さず、かつヤコビ記号(ｇ／ｎ)が１となるように定め、
前記の素数ｐ,ｑ,ｒを、(ｐ−１)／２,(ｑ−１)／２,(ｒ−１)／２が互いに素で、かつｎ＝ｐｑｒをヤコビ記号(−１／ｎ)が１となるように定めて、
ｇ＝ｇp２  modｐ   
ｇ＝ｇq   modｑ   
ｇ＝ｇr   modｒ      (ｇp,ｇq,ｇrは各々正整数)とし、
αがＺn＊の元でＺn＃の元ではないものとして、
前記ｅに対しヤコビ記号(ｅ／ｎ)が１か−１かを求めるためのヤコビ記号計算命令と、
求めたヤコビ記号(ｅ／ｎ)が−１の際にｅ'＝αｅとし、ヤコビ記号が１の際にｅ'＝ｅとするための乗算命令と、
前記ｅ'に対し、ルジャンドル記号(ｅ'／ｐ)が１か−１かを求めるためのルジャンドル記号計算命令と、
求めたルジャンドル記号(ｅ'／ｐ)が−１の際にｅ''＝−ｅ'とし、ルジャンドル記号が１の際にｅ''＝ｅ'とするための乗算命令を設け、
さらにｅ''のｐ,ｑ,ｒを法とする３つの離散対数ｘp,ｘq,ｘrを求めるための命令と、
求めた離散対数ｘp,ｘq,ｘrと
Ｓ＝ｘp  mod(ｐ-1)
Ｓ＝ｘq  mod(ｑ-1)
Ｓ＝ｘr  mod(ｒ-1)
との関係を持ち、かつｎを法とする鍵Ｓを求めるための中国人の剰余定理計算命令とを備えたことを特徴とする。
【０００９】
好ましくは、ヤコビ記号計算命令は、(ｅ／ｐ),(ｅ／ｑ),(ｅ／ｒ)を各々求めてそれらの積をヤコビ記号の値とする。
【００１０】
なおこの明細書において、鍵生成装置に関する記載はそのまま鍵生成プログラムにも当てはまる。また暗号通信は認証を含むものとする。
【発明の効果】
【００１１】
この発明では３素数ｐ,ｑ,ｒの積ｎを法とするので、ｐ,ｑ,ｒを知る鍵生成装置や鍵生成プロセスにとって、離散対数の演算が容易である。以下kをユーザを指定する添字として説明する。
ｎを法とする既約剰余系Ｚｎ＊は４種類に類別され、ヤコビ記号(ｅk／ｎ)が１か−１かからｅkがＺn＃に属するか否かを判別でき、ｅkがＺn＃に属さない場合  ｅk'＝αｅk  に変換するとｅk'はＺn＃に属する。ここにαはＺｎ＊に属してＺn＃に属さない整数で、例えば２である。
さらにルジャンドル記号(ｅk'／ｐ)が１か−１かから、ｅk'が〈ｇ〉nに属するか否かを判別でき、記号の値が１で属し、−１で属さない。ｅk'が〈ｇ〉nに属さない場合、ｅk''＝−ｅk'に変換して、〈ｇ〉nに属する元に変換する。
【００１２】
〈ｇ〉nに属する元はｇを底とする離散対数を持つ。これは〈ｇ〉nがｇを生成元とする巡回乗法群であるためである。そこでＺｎ＊の各元を〈ｇ〉nに属する元へ変換すると、Ｚｎ＊の各元に対するｐ,ｑ,ｒを法とする３つの離散対数を定義できる。ｐ,ｑ,ｒを法とする３つの離散対数を求めると、中国人の剰余定理によりｎを法とする離散対数を求めることができ、ＩＤ等に基づく鍵Ｓを生成できる。
【００１３】
詳細に説明すると、(ｐ−１)／２,(ｑ−１)／２,(ｒ−１)／２が互いに素であることにより、〈ｇ〉nがＺn＊の部分群になり、Ｚn＊が〈ｇ〉nにより４つに類別される。
次にＺn＃＝｛ｘ｜ｘ∈Ｚn＊；(ｘ／ｎ)＝１；(ｘ／ｎ)はヤコビ記号｝と定義することにより、(ｘ／ｎ)の値は１か−１なので、Ｚn＊はＺn＃により２種類に類別される。そしてＺn＃に属さないＺn＊の元に、Ｚn＃に属さないＺn＊の元αを乗算すると、Ｚn＃に属する元に変換できる。
(−１／ｎ)＝１であることから−１はＺn＃に属し、かつ−１は〈ｇ〉nに属さないものと仮定している。この一方で１はＺn＃と〈ｇ〉nの双方に属し、〈ｇ〉nはＺn＃の部分集合である。従ってＺn＃は〈ｇ〉nにより２通りに類別され、Ｚn＃に属し〈ｇ〉nに属さない元に−１を乗算すると、〈ｇ〉nに属する元に変換できる。
【００１４】
(ｇ／ｎ)＝１  より、ｐ,ｑ,ｒの順序を選ぶと、
(ｇ／ｐ)＝１,  
(ｇ／ｑ)＝−１,
(ｇ／ｒ)＝−１  とすることができる。即ち(ｇ／ｎ)＝１との条件は、(ｇ／ｐ)等が全て１か、いずれか１つが１で他の２つが−１であることを意味するが、全てが１とすると矛盾が生じる。そこで(ｇ／ｐ)＝１とすると、ｅk'が〈ｇ〉nに属すれば、〈ｇ〉nが巡回乗法群であることから、ｅk'はｇのべき乗で表すことができ、(ｅk'／ｐ)は１となる。これ以外の場合(ｅk'／ｐ)は−１となる。そこでルジャンドル記号(ｅk'／ｐ)の値からｅk'が〈ｇ〉nに属するか否かを確認でき、属さない場合−１を乗算する。以上のようにｐ,ｑ,ｒの定め方を利用して、(ｇ／ｐ)＝１かどうかでｅk'が〈ｇ〉nに属するか否かを判別できる。
以上の手順により、Ｚn＊の任意の元を〈ｇ〉nに属する元に一意に変換できる。この変換はＺn＊と〈ｇ〉nとの間の４：１の写像で、ｎが充分大きいとき、例えばｎ≧１００,あるいはｎ≧１０００の時、異なるｅに対して同じ鍵Ｓが得られる確率は無視し得る。
【００１５】
鍵Ｓは例えばディフィーヘルマン方式の暗号通信にも用い得るが、ユーザのＩＤを共通鍵の部分鍵に変換するための、ＩＤに基づいた鍵の生成センターで生成することが好ましい。この場合ユーザＡ,Ｂ間の共通鍵ＫABはｅB'2SA＝ｇ２ＳAＳBで与えられる。ｅB',ｅA'等は、ハッシュ関数等の一方向性関数ｈでＩＤB,ＩＤA等を処理して得られた整数ｅB,ｅAを、ヤコビ記号(ｅB／ｎ)や(ｅA／ｎ)の値が１でそのままｅB',ｅA'とし、−１でαを乗算してｅB',ｅA'としたものである。
【００１６】
ヤコビ記号(ｅ／ｎ)の計算ではルジャンドル記号(ｅ'／ｐ)を計算するので、(ｅ／ｎ)＝１の時は、ルジャンドル記号(ｅ'／ｐ)を再計算する必要がない。
【発明を実施するための最良の形態】
【００１７】
以下に本発明を実施するための最適実施例を示す。
【実施例】
【００１８】
図１〜図６に、実施例の鍵生成装置２と鍵生成プログラム３０とを示す。図１において、３はユーザ毎の鍵Ｓkを生成するセンターで、４は通信インターフェースで、インターネット６を介し、エンティティ８からのＩＤを受信し、鍵生成装置２でユーザ毎の鍵Ｓkに変換して、郵便などの安全な通信経路を経てエンティティ８に鍵Ｓkを返す。エンティティ８はパーソナルコンピュータなどで構成され、それぞれ通信インターフェース１０と、ＩＤをＺnの既約剰余系Ｚn＊の元ｅBに変換するハッシュ関数などの一方向性関数１２とを備えている。既約剰余系Ｚn＊の元ｅBは、Ｚn＊  →Ｚn＃変換部１４により、Ｚn＃の元ｅB'に変換される。べき乗剰余算器２２は公開の整数ｎと、記憶している自己の鍵ＳAとを用いて、エンティティBとの通信に用いる共通鍵ＫABをＫAB＝ｅＢ'２ｓＡ  modnにより求める。そして暗号処理部２４は、共通鍵ＫABを用い暗号通信や認証などを行う。
【００１９】
図２以降にセンター３での鍵生成装置２や鍵生成プログラム３０の構成を示し、エンティティ８の構成要素と同じ符号のものは同じものを表す。また各用語の意味や数学的構造は表１〜表４にまとめて示してある。鍵生成装置２にとって、エンティティとユーザは同じ概念であり、ユーザを一般的に指定する場合には添字kを用い、特定のユーザを指定する時には添字AもしくはBを用いる。
【００２０】
一方向性関数１２は例えばハッシュ関数であるが、例えば素数からなる公開の数ａを用い、ａは１以上で後記の巡回乗法群の位数｜ｇ｜n以下と定め、ｅk＝ＩＤkａ  modnとするとよい。この場合攻撃者の負担は、ハッシュ関数ｈの逆関数を求めることから、ＲＳＡ暗号システムを破ることへと置き換えられる。
【００２１】
Ｚn＊  →Ｚn＃変換部１４は、ｅkがＺn＃に属するなら、ｅk'＝ｅkとし、ｅkがＺn＃に属さないなら、ｅk'＝αｅk modnとする。ここにαは例えば２で、Ｚn＃に属さないＺn＊の元である。
【００２２】
Ｚn＊  →Ｚn＃変換部１４の出力ｅk'は、Ｚn＃ →〈ｇ〉n変換部１６でｅk''に変換される。この時ｅk'が巡回乗法群〈ｇ〉nに属するならｅk''＝ｅk'で、属さないならｅk''＝−ｅk'である。変換部１４,１６により整数ｅkは巡回乗法群〈ｇ〉nの元ｅk''に変換される。そしてｎ＝ｐｑｒであり、かつｅk''は巡回乗法群〈ｇ〉nの元なので、ｅk''はｐ,ｑ,ｒを法とする離散対数ｘｐ,ｘｑ,ｘｒを持つ。そこで離散対数変換部１８はこれらの離散対数を求め、中国人の剰余定理計算器２０は、連立合同方程式を解いて、エンティティkの部分鍵Ｓkを求める。
【００２３】
表１      準備と前提
離散対数問題：  法ｎと底ｇ(ｇ∈Ｚn)が与えられた際に、ｙ＝ｇｘmodｎとなるｘ(ｘ∈Ｚn)を求めること
ＩＤ：          ユーザの公開のＩＤ
ｈ(ＩＤk)＝ｅk  ｈはハッシュ関数等の一方向性関数
ＫAB＝ｅB'２ＳＡ＝ｇ２ＳAＳB：  ＫABはエンティティＡ,Ｂ間の共通鍵
ＳA、ＳBはエンティティＡ,Ｂに対する秘密の部分鍵でｅB'２＝ｇ２ＳＢ
【００２４】
表２      定義
ｎ：    (公開の数)  ｎ＝ｐｑｒ；ｐ,ｑ,ｒは秘密の奇素数
(ｐ−１)／２,(ｑ−１)／２,(ｒ−１)／２  は互いに素(条件２)
Ｚn：    Ｚn＝｛０,１,２,…、ｎ−１｝
Ｚn＊：   Ｚn＊＝｛ｘ｜ｘ∈Ｚn；gcd(ｘ,ｎ)＝１｝；ｎを法とする既約剰余系,
gcd(ｘ,ｎ)はｘとｎの最大公約数
Ｚn＃：  Ｚn＃＝｛ｘ｜ｘ∈Ｚn＊；(ｘ／ｎ)＝１｝  
(ｘ／ｎ)等はｎが合成数の場合はヤコビ記号を、素数の場合はルジャンドル記号を示す；  (ｘ／ｎ)＝(ｘ／ｐ)(ｘ／ｑ)(ｘ／ｒ)；(ｘ／ｐ)はｘがｐの倍数で０、ｘのｐを法とする剰余が完全平方数の場合は１,それ以外は−１
α：    (公開の数)  (α／ｎ)＝−１：  α∈(Ｚn＊−Ｚn＃)で例えば２
ｇ：    ｎを法とし位数が最大の巡回乗法群の生成元で離散対数の底；
ｇ∈Ｚn＊,巡回乗法群を〈ｇ〉nで、ｇの位数を｜ｇ｜nで表す  
Ｓｎ：  ｎを法とし位数が最大の巡回乗法群の生成元の集合
λ(ｎ)：  カーマイケル関数；λ(ｎ)＝｜ｇ｜n
【００２５】
表３      用語と数学的準備
〈ｇ〉n⊂Ｚn＃⊂Ｚn＊⊂Ｚn；  Ｚn＊  等の位数を｜Ｚn＊｜等で示すと、  
｜Ｚn＊｜＝２｜Ｚn＃｜＝４｜ｇ｜n  
Ｌ.１  (−１／ｐ)＝(−１)(ｐ−１)／２＝１    (ｐ＝１  mod４)     
＝−１  (ｐ＝３  mod４)    
Ｌ.2   (２／ｐ)＝(−１)(ｐ２−１)／８＝１     (ｐ＝１,７  mod８)    
＝−１   (ｐ＝３,５  mod８)
Ｔ.1   条件１〜４が充たされる場合、Ｚn＃の元ｅに対し、ｅまたは−ｅが、
ｎを法としｇを底とする離散対数を持つ
Ｔ.2  ｅ∈Ｚn＃  かつ  ｅ∈〈ｇ〉n  と(ｅ／ｐ)＝１  は同値
【００２６】
表４  条件
条件１：  Ｚnでの−１、言い換えるとｎ−１が巡回乗法群〈ｇ〉nに属さない
条件２：  (ｐ−１)／２,(ｑ−１)／２,(ｒ−１)／２  が互いに素
これによりＺn＊が〈ｇ〉nにより４段に分解
条件３：  (−１／ｎ)＝１；即ち−１∈Ｚn＃ 
条件３は(ｐ,ｑ,ｒ)＝(1,3,3),(3,1,3),or(3,3,1)  mod４  と同値
∵        (−１／ｎ)＝(−１／ｐ)・(−１／ｑ)・(−１／ｒ)  (ｎ＝ｐｑｒ)  
＝(1,-1,-1),(-1,1,-1),(-1,-1,1),or(1,1,1)
ここで  (−１／ｎ)＝(1,1,1)とすると、条件２の(ｐ−１)／２,
(ｑ−１)／２,(ｒ−１)／２が互いに素であることと矛盾  
条件４：  (ｇ／ｎ)＝１
条件４より、((ｇ／ｐ),(ｇ／ｑ),(ｇ／ｒ))＝(1,-1,-1),(-1,1,-1),or
(-1,-1,1)
なおｇが位数最大の生成元であることから、
((ｇ／ｐ),(ｇ／ｑ),(ｇ／ｒ))≠(1,1,1)
以上のことから、      ｇ＝ｇp２  modｐ
ｇ＝ｇq   modｑ
ｇ＝ｇr   modｒ        と表せる
【００２７】
図３に鍵生成装置での処理を詳細に示す。エンティティkのＩＤはハッシュ関数１２'でｅkに変換され、ヤコビ記号計算器１４'でヤコビ記号(ｅk／ｎ)の値を求める。ｅkはｎを法とする既約剰余系Ｚn＊の元なので、ｅkとｎは互いに素で、ヤコビ記号(ｅk／ｎ)の値は１か−１である。ここで既約剰余系Ｚn＊に属し、Ｚn＃に属さない任意の元α、例えば後述のようにα＝２を考える。Ｚn＃に属さない元に乗算器１５でαを乗算すると、Ｚn＃の元が得られる。仮にＺn＃の元にαを乗算すると、Ｚn＃に属さない元が得られる。以上のようにして、Ｚn＃に属さない元と属する元とを１：１に対応できる。そしてＺn＃に属さない元では、ヤコビ記号(ｅk／ｎ)が−１で、ｅk'＝αｅkとする。またＺn＃に属する元に対しては、ｅk'＝ｅkとする。
【００２８】
後述のように、条件１〜４(Ｃ.１〜４)が充たされる場合、定理１(Ｔ.１)が成立し、ｅk'もしくは−ｅk'に対して、ｐ,ｑ,ｒを法とする離散対数ｘｐ,ｘｑ,ｘｒを求めることができる。ｅk'が巡回乗法群〈ｇ〉nに属する否かをルジャンドル記号計算器１６'でルジャンドル記号(ｅk'／ｐ)の値を求め、この値が１で、ｅk'は巡回乗法群〈ｇ〉nに属し、値が−１の場合巡回乗法群に属さないので、符号反転器１７でｅk''＝−ｅk'とする。ｅk''に対して剰余算器１９'〜１９'''によりｐ,ｑ,ｒを法とする剰余を求め、離散対数変換部１８'〜１８'''により、図２に記載した離散対数ｘｐ,ｘｑ,ｘｒを求める。これを前記の中国人の剰余定理計算器２０で連立合同方程式を解き、鍵Ｓkを求める。
【００２９】
既約剰余系Ｚn＊と巡回乗法群〈ｇ〉nとの関係を図４に示すと、既約剰余系Ｚn＊に属するが、Ｚn＃に属さない元にαを乗算することにより、Ｚn＃に属する元ｅk'に変換できる。これに−１を乗算すると、巡回乗法群〈ｇ〉nに属する元ｅk''に変換できる。
【００３０】
そして条件２により、既約剰余系Ｚn＊は巡回乗法群〈ｇ〉nにより４段に分解し、４つの同値類が得られる。次にＺn＃により既約剰余系Ｚn＊は上下２段に分解する。ここで条件４より、巡回乗法群〈ｇ〉nはＺn＃の部分集合となり、条件１,３より−１や−ｇなどがＺn＃に属して巡回乗法群〈ｇ〉nに属さない。さらにＺn＃が巡回乗法群〈ｇ〉nにより２種類に類別できることにより、Ｚn＃の元ｅに対し、ｅまたは−ｅがｎを法としｇを底とする離散対数を持つ。なおこのことを定理１(Ｔ.１)と呼ぶ。
【００３１】
ヤコビ記号(ｇ／ｎ)について説明すると、この値は３つのルジャンドル記号(ｇ／ｐ)(ｇ／ｑ)(ｇ／ｒ)の積に分解でき、ヤコビ記号(ｇ／ｎ)が１との条件は、各ルジャンドル記号のうち、１つが１で他が−１か、３つのルジャンドル記号が全て１かのいずれかである。ここで全てのルジャンドル記号が１であると、ｇが位数最大の生成元となることと矛盾する。従って３つのルジャンドル記号の１つが１で他は−１であり、ｐ,ｑ,ｒの内、素数ｐでルジャンドル記号が１,素数ｑ,ｒでルジャンドル記号が−１とすることができる。
【００３２】
前記のαとして例えば２を用いた。ここでｐ,ｑ,ｒは
(p,q,r)=(3,3,5),(7,7,5),or(7,3,1)  mod8を充たすようにすると、表３の補題２(Ｌ.２)から、ヤコビ記号(２／n)＝(２／ｐ)(２／ｑ)(２／ｒ)＝−１となることが分かる。
【００３３】
図６の鍵生成プログラム３０について説明すると、一方向性変換命令３０は一方向性関数によるＩＤkのekへの変換を行い、Ｚn＊→Ｚn＃変換命令３２はヤコビ記号（ｅk／ｎ）の値に基づくｅk→ｅk'の変換を行い、Ｚn＃→〈ｇ〉n変換命令はルジャンドル記号（ｅk'／ｐ）の値に基づくｅk'→ｅk''の変換を行う。離散対数変換命令３４は法ｐ，ｑ，ｒに対する３つの離散対数ｘp,ｘq,ｘrを求め、中国人の剰余定理計算命令３５は離散対数ｘp, ｘq,ｘrを鍵Ｓkへ変換する。
【図面の簡単な説明】
【００３４】
【図１】実施例の鍵生成装置の使用環境を示す図
【図２】実施例の鍵生成装置のブロック図
【図３】実施例での鍵の生成過程を示す図
【図４】実施例での、Ｚnの既約剰余系Ｚn＊とＺn＃、及び〈ｇ〉nの対応を示す図
【図５】実施例での、エンティティにおける共通鍵ＫABの生成過程を示す図
【図６】実施例での鍵生成プログラムのブロック図
【符号の説明】
【００３５】
２          鍵生成装置
３          センター
４,１０    通信インターフェース
６          インターネット
８          エンティティ
１２        一方向性関数
１２'      ハッシュ関数
１４        Ｚn＊→Ｚn＃変換部
１４'      ヤコビ記号計算器
１５        乗算器
１６        Ｚn＃→〈ｇ〉n変換部
１６'      ルジャンドル記号計算器
１７        符号反転器
１８        離散対数変換部
１８'〜１８'''  離散対数変換器
１９'〜１９'''  剰余算器
２０        中国人の剰余定理計算器
２２        べき乗剰余算器
２４        暗号処理部
３０        鍵生成プログラム
３１        一方向性変換命令
３２        Ｚn＊→Ｚn＃変換命令
３３        Ｚn＃→〈ｇ〉n変換命令
３４        離散対数変換命令
３５        中国人の剰余定理計算命令
【図１】
2007181001.tif 000003
【図２】
2007181001.tif 000004
【図３】
2007181001.tif 000005
【図４】
2007181001.tif 000006
【図５】
2007181001.tif 000007
【図６】
2007181001.tif 000008