JP3479015B2 - 暗号鍵分散生成方法、署名生成・検証方法、暗号鍵分散生成装置、署名生成・検証装置、暗号鍵分散生成プログラムおよび署名生成・検証プログラムをそれぞれ記録したコンピュータ読み取り可能な記録媒体 - Google Patents

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、デジタルＴＶ・衛
星放送におけるペイ・パー・ビュー（ｐａｙ ｐｅｒ
ｖｉｅｗ）システム・情報流通における鍵配送・電子メ
ール・電子決済等の通信におけるデータの暗号化を強力
なものとし得る暗号鍵分散生成方法および装置と暗号鍵
分散生成プログラムを記録した記録媒体に関する。

【０００２】

【従来の技術】近年、通信分野において、伝送される情
報の秘匿等の通信者間の秘密性を保護する技術として暗
号化技術が有効に働くことから、各種暗号化技術が提案
されている。これら暗号化技術の性能は、暗号方式の安
全強度と暗号化・復号化に要する速度の観点から評価し
うる。すなわち安全強度が高く、暗号化・復号化の速度
が速い暗号方式が優れた暗号方式である。

【０００３】このような暗号化技術の中に、ＲＳＡ（Ri
vest Shamir Adleman ）暗号として知られる、べき乗剰
余演算を用いるタイプの公開鍵暗号方式があり、既に実
用化されている。このＲＳＡ暗号方式では、公開鍵が素
因数分解できれば、暗号文から平文を得ることができる
ことが、文献「R.Rivest,A.Shamir and L.Adleman;"Ame
thod for obtaining digital signatures and public-k
ey cryptosystems.",Comm.,ACM,vol.21,No.2,pp.120-12
6,(1978) 」に示されている。

【０００４】このＲＳＡ暗号方式などの公開鍵暗号方式
は、公開された情報である公開鍵から秘密鍵を得ること
が計算量的に困難であることに安全性の根拠を置いてお
り、そのため公開鍵のサイズを大きく取れば、それだけ
安全強度が増すことになる。一方、安全の強化という点
では、秘密鍵を安全に保管することが重要な問題であ
る。これに対して、一つの鍵を一個所で保管するのでは
なく、一つの鍵を複数に分割し、その鍵の分割した部分
情報からはオリジナルの鍵を求めることができない秘密
分散方式が文献「A.Shamir ;“How to share a secret
”, Comm.Of the ACM,Vol.22,1979,pp.612-613」に示
されている。

【０００５】この秘密分散方式を、ＲＳＡ暗号の秘密鍵
管理に用いた方式は、多くの認証局ＣＡに用いられてい
る。

【０００６】ここで、ＲＳＡ暗号のオリジナルの鍵ｄか
ら分散鍵ｄｉ（ｄ＝Σｄｉ）を生成する際に、ある特定
のディーラを必要とする。つまり、このディーラが攻撃
されることにより、秘密鍵全体の情報が漏れてしまい、
分散の効果が無くなる可能性がある。

【０００７】Boneh とFranklinは、文献「D.Boneh, J.F
ranklin,“Efficient generation of shared RSA key
s,”Advances in Cryptology−CRYPTO ^,97, LNCS 1294,
(1997),pp.425-439.」に、ディーラを必要としないＲＳ
Ａ暗号の分散鍵の生成方法を示した（以下 Boneh-Frank
lin 法と呼ぶ）。

【０００８】しかし、 Boneh-Franklin 法は一つの鍵を
生成するのに、非常に多くの計算量を必要とし非効率で
ある。ある実験によると、各分散暗号鍵生成手段間で
１．５分の時間と約１メガバイトの通信量が必要であっ
た。

【０００９】

【発明が解決しようとする課題】上述したように、従来
の Boneh-Franklin の分散鍵生成法を利用した場合には
非常に多くの計算量を必要とし、通信を介した場合には
非常に非効率であるというような欠点があった。

【００１０】本発明は、上記課題に鑑みてなされたもの
で、 Boneh-Franklin の分散鍵生成法と比較しても処理
が高速である暗号鍵分散生成方法および装置と暗号鍵分
散生成プログラムを記録した記録媒体を提供することを
目的とする。

【００１１】

【課題を解決するための手段】上記目的を達成するた
め、請求項１記載の発明は、任意の通信手段で相互に接
続され、公開鍵暗号方式の暗号鍵を生成する暗号鍵生成
手段をそれぞれ有する複数のサーバｉ（ｉ＝１，２，・
・・，ｋ）が分散して暗号鍵を生成する暗号鍵分散生成
方法であって、第１の公開鍵ｎと第２の公開鍵ｅとを用
いて、平文Ｍから暗号文Ｃ＝Ｍ^ｅ（ｍｏｄｎ）を得るに
際して、各サーバｉが２個の乱数ｐｉおよびｑｉを自ら
の持つ秘密情報である第１の分散秘密鍵としてそれぞれ
生成するステップと、各サーバが自らの持つ秘密情報を
他のサーバに漏らすことなく全てのサーバで共有する計
算ができるＢＧＷプロトコルを用いて前記第１の公開鍵
ｎの候補であるＮ＝（Σ_{ｉ＝１，２，…，ｋ}ｐｉ）
^２（Σ_{ｉ＝１，２，…，ｋ}ｑｉ）を生成するステップと
を行うことを特徴とする。

【００１２】 請求項１記載の発明にあっては、ＢＧＷ
プロトコルを用いることによって、本願発明者らが既に
提案しているｐ^２ｑ暗号の鍵の候補を分散生成すること
が可能となり、これによりＮ＝Ｐ^２Ｑの形の合成数を用
いて、ディーラの必要ない処理が高速でかつ安全性に秀
でた分散鍵生成法の具体的な構成方法を与え、実現す
る。

【００１３】 請求項２記載の発明は、請求項１記載の
暗号鍵分散生成方法であって、前記第１の公開鍵ｎの候
補であるＮを生成するステップに続いて、さらに、前記
各サーバｉが、全てのサーバに共通な乱数ｇを用いてｖ
_ｐｉ＝ｇ^ｐｉ ｍｏｄＮをそれぞれ計算し、この計算し
た値を他のサーバに送信するステップと、前記各サーバ
ｉがｖ_ｐ＝Π_{ｉ＝１，２，…，ｋ}ｖ_ｐｉ ｍｏｄＮをそ
れぞれ計算するステップと、サーバ１がｕ_１＝ｇ^Ｎ ｍ
ｏｄＮ、サーバｉ（ここでｉ＝２，・・・，ｋ−１）が
ｕ_ｉ＝ｖ_ｐ ^{ｐｉ＋ｑｉ}ｍｏｄＮ、サーバｋがｕ_ｋ＝ｖ_ｐ
^{ｐｋ＋ｑｋ―１} ｍｏｄＮをそれぞれ計算して相互に配
布するステップと、このステップでの計算値がｕ_１＝ｕ
_ｋΠ_{ｉ＝２，…，ｋ―１}ｕ_ｉ ｍｏｄＮを満たすかどう
かを前記各サーバｉが検証し、この式が成り立つ場合に
は、Σ_{ｉ＝１，２，…，ｋ}ｐｉおよびΣ
_{ｉ＝１，２，…，ｋ}ｑｉが素数であると判定するステッ
プとを行うことを特徴とする。

【００１４】 請求項２記載の発明によれば、例えば請
求項１の暗号鍵分散生成方法で生成された暗号鍵の候補
が望み通りのＰ^２Ｑであるか、Ｐ，Ｑが素数であるか、
否かを分散検証できる。

【００１５】 請求項３記載の発明は、請求項２記載の
暗号鍵分散生成方法であって、前記Σ
_{ｉ＝１，２，…，ｋ}ｐｉおよび前記Σ
_{ｉ＝１，２，…，ｋ}ｑｉが素数であるとき、これらの素
数Σ_{ｉ＝１，２，…，ｋ}ｐｉおよびΣ
_{ｉ＝１，２，…，ｋ}ｑｉを用いてγ（Ｎ）＝（Σ
_{ｉ＝１，２，…，ｋ}ｐｉ）｛（Σ_{ｉ＝１，２，…，ｋ}ｐ
ｉ）−１｝｛（Σ_{ｉ＝１，２，…，ｋ}ｑｉ）−１｝とし
て、前記各サーバｉが、設定される素数Ｒに対して前記
ＢＧＷプロトコルを用いて、γ（Ｎ）＝Σ
_{ｉ＝１，２，…，ｋ}γ_ｉ（Ｎ）−ｓＲ（ここで、ｓ＝
０，１，２，…，ｋ−１）を満たすγ_ｉ（Ｎ）を生成す
るステップと、第２の公開鍵として選択されるｅを用い
て前記各サーバｉがγ_ｉ（Ｎ）ｍｏｄｅの値を他のサー
バにそれぞれ送信するステップと、前記各サーバｉが、
δ_ｅ，ｓ＝１／（γ（Ｎ）−ｓＲ） ｍｏｄｅ、および
ｄ_ｉ，ｓ ＝［（−δ_ｅ，ｓγ_ｉ（Ｎ））／ｅ］（但
し、ｓ＝０，１，２，…，ｋ−１）をそれぞれ計算する
ステップと、前記各サーバｉが、真の復号鍵である第２
の秘密鍵をｄ（ここでｄは、ｅｄ＝１ ｍｏｄγ（Ｎ）
を満たす）とするとき、このｄが満たす関係式ｄ＝Σ
_{ｉ＝１，２，…，ｋ}ｄ_ｉ，ｓ＋ｒ ｍｏｄγ（Ｎ）と、
あるメッセージＭにより、１＝Ｍ^ｅｄ ｍｏｄＮが成立
するｓ，ｒを決定することにより、第２の分散秘密鍵ｄ
_ｉをそれぞれ生成するステップとを行うことを特徴とす
る。

【００１６】 請求項３記載の発明によれば、Ｎ（＝Ｐ
^２Ｑ）が決まったとき、第２の秘密鍵ｄを分散生成する
ことから、各サーバｉは自らの第２の分散秘密鍵ｄ
_ｉ（１≦ｉ≦ｋ）のみの値しか知り得ない。

【００１７】 請求項４記載の発明は、請求項３記載の
暗号鍵分散生成方法によって生成された第１の公開鍵
Ｎ、第２の公開鍵ｅ、および第２の分散秘密鍵ｄ_ｉを用
いて署名を行い、かつ当該署名の検証を行う署名生成・
検証方法であって、任意の通信手段で相互に接続される
複数のサーバｉ（ｉ＝１，２，・・・，ｋ）が前記第１
の公開鍵Ｎおよび自らの前記第２の分散秘密鍵ｄ_ｉを用
いてメッセージＭに対してそれぞれ行う分散署名Ｓ_ｉ＝
Ｍ^ｄｉ ｍｏｄＮを用いて、真の署名Ｓ＝Π
_{ｉ＝１，２，…，ｋ}Ｓ_ｉ ｍｏｄＮを生成し、この署名
についての検証をＳ^ｅ＝Ｍ ｍｏｄＮにより行うことを
特徴とする。

【００１８】 請求項４記載の発明によれば、誰も第２
の秘密鍵ｄを知らないにも拘らず、ｄ_ｉのみの部分認証
を収集することにより全体認証が実現できる。

【００１９】 請求項５記載の発明は、任意の通信手段
で相互に接続される複数のサーバｉ（ｉ＝１，２，・・
・，ｋ）から構成され、公開鍵暗号方式の暗号鍵を分散
して生成する暗号鍵分散生成装置であって、第１の公開
鍵ｎと第２の公開鍵ｅとを用いて、平文Ｍから暗号文Ｃ
＝Ｍ^ｅ（ｍｏｄ ｎ）を得るに際して、サーバｉごとに
２個の乱数ｐｉおよびｑｉを自らの持つ秘密情報である
第１の分散秘密鍵として生成する乱数生成手段と、各サ
ーバが自らの持つ秘密情報を他のサーバに漏らすことな
く全てのサーバで共有する計算ができるＢＧＷプロトコ
ルを用いて前記第１の公開鍵ｎの候補であるＮ＝（Σ
_{ｉ＝１，２，…，ｋ}ｐｉ）^２（Σ_{ｉ＝１，２，…，ｋ}ｑ
ｉ）を生成する公開鍵候補生成手段とを有することを特
徴とする。

【００２０】 請求項５記載の発明にあっては、ＢＧＷ
プロトコルを用いることによって、本願発明者らが既に
提案しているｐ^２ｑ暗号の鍵の候補を分散生成すること
が可能となり、これによりＮ＝Ｐ^２Ｑの形の合成数を用
いて、ディーラの必要ない処理が高速でかつ安全性に秀
でた分散鍵生成法の具体的な構成方法を与え、実現す
る。

【００２１】 請求項６記載の発明は、請求項５記載の
暗号鍵分散生成装置であって、全てのサーバに共通な乱
数ｇを選択する共通乱数選択手段と、この共通乱数選択
手段で選択した乱数ｇ、および前記第１の公開鍵ｎの候
補であるＮを用いて、各サーバｉ（ここでｉ＝１，２，
・・・，ｋ）でｖ_ｐｉ＝ｇ^ｐｉ ｍｏｄ Ｎを計算し、
この計算したｖ_ｐｉを他のサーバに送信する手段と、サ
ーバ１でｖ_ｐ＝Π_{ｉ＝１，２，…，ｋ}ｖ_ｐｉ ｍｏｄＮ
を計算し、このｖ_ｐを用いてｕ_１＝ｇ^Ｎ ｍｏｄＮを計
算するサーバ１の計算手段と、サーバｉ（ここでｉ＝
２，・・・，ｋ−１）でｖ_ｐ＝Π_{ｉ＝１，２，…，ｋ}ｖ
_ｐｉ ｍｏｄＮを計算し、このｖ_ｐを用いてｕ_ｉ＝ｖ_ｐ
^{ｐｉ＋ｑｉ} ｍｏｄＮをそれぞれ計算するサーバｉ（ｉ
＝２，・・・，ｋ−１）の計算手段と、サーバｋでｖ_ｐ
＝Π_{ｉ＝１，２，…，ｋ}ｖ_ｐｉ ｍｏｄＮを計算し、こ
のｖ_ｐを用いてｕ_ｋ＝ｖ_ｐ ^{ｐｋ＋ｑｋ―１} ｍｏｄＮを
計算するサーバｋの計算手段と、各サーバの計算手段で
計算したｕ_１，ｕ_２，・・・，ｕ_ｋを相互に配布する手
段と、ｕ_１＝ｕ_ｋΠ_{ｉ＝２，…，ｋ―１}ｕ_ｉ ｍｏｄＮ
を満たすかどうかを検証し、この式が成り立つ場合に
は、Σ_{ｉ＝１，２，…，ｋ}ｐｉおよびΣ
_{ｉ＝１，２，…，ｋ}ｑｉが素数であると判定する素数判
定手段とをさらに有することを特徴とする。

【００２２】 請求項６記載の発明によれば、例えば請
求項１の暗号鍵分散生成方法で生成された暗号鍵の候補
が望み通りのＰ^２Ｑであるか、Ｐ，Ｑが素数であるか、
否かを分散検証できる。

【００２３】 請求項７記載の発明は、請求項６記載の
暗号鍵分散生成装置であって、前記素数判定手段が前記
Σ_{ｉ＝１，２，…，ｋ}ｐｉおよび前記Σ
_{ｉ＝１，２，…，ｋ}ｑｉが素数であると判定したとき、
これらのΣ_{ｉ＝１，２，…，ｋ}ｐｉおよびΣ
_{ｉ＝１，２，…，ｋ}ｑｉを用いてγ（Ｎ）＝（Σ
_{ｉ＝１，２，…，ｋ}ｐｉ）｛（Σ_{ｉ＝１，２，…，ｋ}ｐ
ｉ）−１｝｛（Σ_{ｉ＝１，２，…，ｋ}ｑｉ）−１｝とし
て、設定される素数Ｒに対して前記ＢＧＷプロトコルを
用いて、γ（Ｎ）＝Σ_{ｉ＝１，２，…，ｋ}γ_ｉ（Ｎ）−
ｓＲ（ここで、ｓ＝０，１，２，…，ｋ−１）を満たす
γ_ｉ（Ｎ）をサーバｉ（ここでｉ＝１，２，・・・，
ｋ）でそれぞれ生成するサーバｉの生成手段と、乱数ｅ
を第２の公開鍵として選択する乱数選択手段と、前記サ
ーバｉの生成手段でそれぞれ生成したγ_ｉ（Ｎ）および
前記乱数選択手段で選択したｅを用いてδ_ｅ，ｓ＝１／
（γ（Ｎ）−ｓＲ） ｍｏｄｅ、およびｄ_ｉ，ｓ ＝
［（−δ_ｅ，ｓγ_ｉ（Ｎ））／ｅ］（但し、ｓ＝０，
１，２，…，ｋ−１）をそれぞれ計算するサーバｉの計
算手段と、真の復号鍵である第２の秘密鍵をｄ（ここで
ｄは、ｅｄ＝１ ｍｏｄγ（Ｎ）を満たす）とすると
き、ｄ＝Σ_{ｉ＝１，２，…，ｋ}ｄ_ｉ，ｓ＋ｒ ｍｏｄγ
（Ｎ）と、あるメッセージＭにより、１＝Ｍ^ｅｄ ｍｏ
ｄＮが成立するｓ，ｒを決定することによって第２の分
散秘密鍵ｄ_ｉをそれぞれ生成するサーバｉの秘密鍵生成
手段とをさらに有することを特徴とする。

【００２４】 請求項７記載の発明によれば、Ｎ（＝Ｐ
^２Ｑ）が決まったとき、第２の秘密鍵ｄを分散生成する
ことから、各サーバｉは分散された自らの第２の分散秘
密鍵ｄ_ｉ（１≦ｉ≦ｋ）のみの値しか知り得ない。

【００２５】 請求項８記載の発明は、請求項７記載の
暗号鍵分散生成装置によって生成される第１の公開鍵
Ｎ、第２の公開鍵ｅ、および第２の分散秘密鍵ｄ_ｉを用
いて署名を行い、かつ当該署名の検証を行う署名生成・
検証装置であって、任意の通信手段で相互に接続される
複数のサーバｉ（ｉ＝１，２，・・・，ｋ）が前記第１
の公開鍵Ｎおよび自らの前記第２の分散秘密鍵ｄ_ｉを用
いてメッセージＭに対して行う分散署名Ｓ_ｉ＝Ｍ^ｄｉ
ｍｏｄＮを用いて、真の署名Ｓ＝Π_{ｉ＝１，２，…，ｋ}
Ｓ_ｉ ｍｏｄＮを生成する署名手段と、この署名手段で
生成した署名についての検証をＳ^ｅ＝Ｍ ｍｏｄＮによ
り行う署名検証手段とを有することを特徴とする。

【００２６】 請求項８記載の発明によれば、誰も第２
の秘密鍵ｄを知らないにも拘らず、ｄ_ｉのみの部分認証
を収集することにより全体認証が実現できる。

【００２７】 請求項９記載の発明は、請求項１乃至３
のいずれか１項に記載した暗号鍵分散生成方法をコンピ
ュータに実行させるための暗号鍵分散生成プログラムを
記録したコンピュータ読み取り可能な記録媒体である。

【００２８】 請求項９記載の発明によれば、暗号鍵分
散生成プログラムを記録媒体に記録しているため、該記
録媒体を利用して、その暗号鍵分散生成プログラムの流
通性を高めることができる。

【００２９】 請求項１０記載の発明は、請求項４に記
載した署名生成・検証方法をコンピュータに実行させる
ための署名生成・検証プログラムを記録したコンピュー
タ読み取り可能な記録媒体である。

【００３０】 請求項１０記載の発明によれば、署名生
成・検証プログラムを記録媒体に記録しているため、該
記録媒体を利用して、その暗号鍵分散生成プログラムま
たは署名生成・検証プログラムの流通性を高めることが
できる。

【００３１】

【００３２】

【００３３】

【００３４】

【００３５】

【００３６】

【００３７】

【００３８】

【００３９】

【００４０】

【００４１】

【発明の実施の形態】以下、図面を用いて本発明の実施
の形態について説明する。

【００４２】まず、図１を参照して、本発明の基本的な
概念について説明する。ここでは、簡単のためサーバの
数をサーバ１，２，３の３台とするが、特に台数は限定
されない。なおサーバの台数が増加するだけ、暗号鍵が
分散されることから、暗号の強度は増すものの、分散数
の増加に伴い暗号解読の時間も増加することから、その
通信内容（重要度、データ量）に応じて適宜、サーバ及
びサーバの台数を選択すると良い。

【００４３】 なお、ここでは２個の素数ｐ，ｑをｋ個
のサーバｉ（ｉ＝１，２，…，ｋ）に分散したｐｉ，ｑ
ｉ（但し、ｐ＝Σｐｉ，ｑ＝Σｑｉ）を第１の分散秘密
鍵として、ｐ^２ｑを第１の公開鍵ｎと設定し、ｅｄ＝１
ｍｏｄ Ｌ（ただしＬ＝ｐ（ｐ−１）（ｑ−１））を満
たすｅを第２の公開鍵と設定すると共に、ｄをサーバｉ
に分散したｄ_ｉ（ただしｄ＝Σｄ_ｉ）を第２の分散秘密
鍵と設定することにより暗号鍵を生成するｋ個の暗号鍵
生成手段を有し、この暗号鍵生成手段により生成された
前記第１の公開鍵ｎと第２の公開鍵ｅとを用いて、平文
Ｍから、Ｃ＝Ｍ^ｅ（ｍｏｄ ｎ）に従い暗号文Ｃを得る
ものとする。

【００４４】図１に示すサーバ１、サーバ２、サーバ３
は、それぞれ相互に任意の通信手段で接続され、各サー
バｉ（但し、ｉ＝１，２，３）には管理者がそれぞれい
るものとする。

【００４５】まず、各サーバｉで乱数ｐｉ，ｑｉがそれ
ぞれ生成され、それぞれの管理者により秘密にして保
管、管理される。つまりサーバ１ではｐ１，ｑ１が、サ
ーバ２ではｐ２，ｑ２が、サーバ３ではｐ３，ｑ３が生
成される。

【００４６】次に、サーバ（管理者）間でＢＧＷプロト
コル及び素数テストを行うことによって鍵を生成する。

【００４７】 ここで、ＢＧＷプロトコルについて簡単
に説明する。ＢＧＷプロトコルは、例えば、サーバ１が
（ｐ１，ｑ１）、サーバ２が（ｐ２，ｑ２）、サーバ３
が（ｐ３，ｑ３）をそれぞれを秘密情報として持ってい
るとき、 ｎ＝ｐ^２ｑ（ここでｐ＝ｐ１＋ｐ２＋ｐ３，ｑ＝ｑ１＋ｑ２＋ｑ３） を、各サーバ秘密情報である（ｐｉ，ｑｉ）を、他のサ
ーバに漏らすことなく、計算できるというプロトコルで
ある。

【００４８】 このようなＢＧＷプロトコルを用いるこ
とにより、 ｎ＝ｐ^２ｑ＝（ｐ１＋ｐ２＋ｐ３）^２（ｑ１＋ｑ２＋ｑ３） をサーバ１、サーバ２およびサーバ３で共有することが
できる。

【００４９】 次に、分散素数テストの前半を行う。こ
れには、まずサーバ１、サーバ２およびサーバ３に共通
な乱数ｇを生成し、それぞれで共有する。この乱数ｇを
用いて、サーバ１はサーバ２とサーバ３に対しｇ^ｐ１を
送信し、サーバ２はサーバ１とサーバ３に対しｇ^ｐ２を
送信し、サーバ３はサーバ１とサーバ２に対しｇ^ｐ３を
それぞれ送信する。続いて、サーバ１、サーバ２および
サーバ３は、 ｇ^ｐ１ｇ^ｐ２ｇ^ｐ３ ｍｏｄｎにより、 ｖ_ｐ＝ｇ^ｐ ｍｏｄｎ を共有する。

【００５０】 さらに、サーバ１はｖ_ｐ ^{ｐ１＋ｑ１} ｍ
ｏｄｎ 、サーバ２はｖ_ｐ ^{ｐ２＋ｑ２} ｍｏｄｎ、およ
びサーバ３はｖ_ｐ ^{ｐ３＋ｑ３―１} ｍｏｄｎを計算し
て、相互に配布し、 ｇ^{｛ｐ（ｐ―１）（ｑ―１）｝}＝１ ｍｏｄｎ が成立するか否かを確認する。同様の方法を用いて環Ｔ
_Ｎで分散素数テストの後半を行う。この式の成立が確認
され、ｐとｑがそれぞれ素数であることが確認されたな
らｐ１、ｐ２、ｐ３、ｑ１、ｑ２、ｑ３を分散鍵として
用いることが可能であり、これにより鍵が生成されたこ
とになる。

【００５１】次に、図２を参照して分散鍵の生成方法、
及び素数判定について詳細に説明する。ここではｐ² ｑ
を対象とし、サーバは暗号鍵生成手段を含むものであ
り、サーバの数はｋと仮定する。

【００５２】まず、ステップＳ１１において、各サーバ
ｉに設けられる乱数生成手段により２個の乱数ｐｉ，ｑ
ｉ（３ mod ４）を生成し、続いてステップＳ１３で、
文献「M.Ben-Or,S.Goldwasser,A.Wigderson;“Complete
ness theorems for non-cryptographic faulttolerant
distributed computation,”STOC,(1998), pp.1-10」の
記載にあるＢＧＷプロトコルを用いて、公開鍵候補生成
手段により第１の公開鍵ｎの合成数の候補をＮとすると
き、 Ｎ＝（Σ_i=1,2,…,kｐｉ）² （Σ_i=1,2,…,kｑｉ） を生成する。

【００５３】このとき、Σ_i=1,2,…,kｐｉおよびΣ
_i=1,2,…,kｑｉが、小さな素数で割れないように、文献
「M.Malkin,T.Wu and D.Boneh,Experimenting with Sha
red Generation of RSA keys,1999 Symposium on Netwo
rk and Distributed System Security(SNDSS), pp.43-5
6.」に書かれた分散篩法および小さな素数により繰り返
し割り算を行う。

【００５４】ステップＳ１５では、各サーバｉに設けら
れる共通乱数選択手段により全てのサーバに共通な乱数
ｇを選ぶ。続いて、ステップＳ１７において、各サーバ
ｉは、この通知された乱数ｇにより、 ｖ_pi＝ｇ^pi ｍｏｄ Ｎ を計算し各サーバに送信する。

【００５５】 これにより、ステップＳ１９において、
それぞれ計算手段により各サーバｉは、 ｖ_ｐ＝Π_{ｉ＝１，２，・・・，ｋ}ｖ_ｐｉ ｍｏｄＮ を計算する。さらに、サーバ１は ｕ_１＝ｇ^Ｎ ｍｏｄＮ を計算し、以下、同様にサーバｉ（ｉ＝２，・・・，ｋ
−１）は ｕ_ｉ＝ｖ_ｐ ^{ｐｉ＋ｑｉ} ｍｏｄＮ を計算し、サーバｋは ｕ_ｋ＝ｖ_ｐ ^{ｐｋ＋ｑｋ―１} ｍｏｄＮ を計算する。

【００５６】さらにステップＳ２１で、素数判定手段
は、 ｕ₁ ＝ｕ_k Π_i=2,…,k-1ｕ_i ｍｏｄ Ｎ が成り立つかどうか検証する。もし成立しない場合は、
Ｎは２個の素数の積（Ｎ＝Ｐ² Ｑ）ではないと判定する
（ステップＳ２３）。

【００５７】 ステップＳ２５乃至ステップＳ３３での
処理について説明する。ここでの計算は、環Ｔ_Ｎ＝（Ｚ
_Ｎ［ｘ］／（ｘ^２＋１））／Ｚ_Ｎ演算とする。

【００５８】まず、ステップＳ２５において、共通乱数
選択手段はｋ個、全てのサーバに共通な乱数ｈを選ぶ。
各サーバｉは、ステップＳ２７で、 ｒ_pi＝ｈ^pi を計算し各サーバｉに送信する。

【００５９】 各サーバｉの計算手段は、ステップＳ２
９において、各サーバｉは ｒ_ｐ＝Π_{ｉ＝１，２，…，ｋ}ｒ_ｐｉ ｍｏｄＮ を計算する。サーバ１は ｓ_１＝ｈ^Ｎ を計算し、同様にサーバｉ（ｉ＝２，・・・，ｋ−１）
は ｓ_ｉ＝ｒ_ｐ ^{―ｐｉ―ｑｉ} を計算し、サーバｋは ｓ_ｋ＝ｒ_ｐ ^{―ｐｋ―ｑｋ―１} を計算する。

【００６０】さらに、素数判定手段はステップＳ３１
で、 ｓ₁ ＝ｓ_k Π_i=2,…,k-1ｓ_i が成り立つかどうかを検証する。もし成立しない場合に
は、Ｎは２個の素数の積（Ｎ＝Ｐ² Ｑ）ではないと判定
する（ステップＳ３３）。

【００６１】以上のテストにパスした場合（ステップＳ
３５）、理論的に１／２以上の確率でＮは２個の素数の
積と判定できる。このテストを複数回実施することによ
り高い確率でＮは２個の素数の積と判定できる。また、
文献「R.Rivest, "Finding four million large random
primes," Advances in Cryptology -- Crypto'90,LNCS
537,pp.625-626 (1991)」 によると、５１２ビット以上
の数Ｎ＝Ｐ² Ｑに対してはステップＳ１５乃至ステップ
Ｓ２３（またはステップＳ２５乃至ステップＳ３３）の
テストを一回実施すれば、ほぼ１の確率でＰ，Ｑは素数
と判定可能である。

【００６２】従って、ステップＳ１５乃至ステップＳ２
３の処理、またはステップＳ２５乃至ステップＳ３３の
処理のいずれかの処理を実行すればＰ，Ｑを素数と判定
することが略可能であることから、いずれかの処理のみ
を行うようにすれば、さらに分散鍵の生成を高速におこ
なうことが可能となる。

【００６３】次に、図３を参照して暗号化復号化鍵生成
方式について説明する。

【００６４】ただし、 ｅｄ＝ｅΣ_i=1,2,…,kｄ_i ＝１ ｍｏｄ γ（Ｎ） γ（Ｎ）＝Ｐ（Ｐ−１）（Ｑ−１） とする。

【００６５】まず、ステップＳ４１で、大きな素数Ｒを
設定する。次に、ステップＳ４３で、各サーバｉは、こ
の素数Ｒに対してＢＧＷプロトコルを用いて、γ（Ｎ）
のシェアγ_i （Ｎ）、つまり γ（Ｎ）＝Σ_i=1,2,…,kγ_i （Ｎ）−ｓＲ を満たすγ_i （Ｎ）を生成する（但し、ｓ＝０，１，
２，…，ｋ−１）。

【００６６】次に、ステップＳ４５で、小さな値の乱数
ｅを選択する。続いて、ステップＳ４７で、各サーバｉ
はγ_i （Ｎ）ｍｏｄ ｅの値を他のサーバに送信するこ
とにより、 δ_e,s ＝１／（γ（Ｎ）−ｓＲ）ｍｏｄ ｅ ｄ_i,s ＝［（−δ_e,s γ_i （Ｎ））／ｅ］ を計算する（ｓ＝０，１，２，…，ｋ−１）。

【００６７】さらに、ステップＳ４９において、真の復
号鍵（第２の秘密鍵）をｄとするとき、 ｄ＝Σ_i=1,2,…,kｄ_i,s ＋ｒ ｍｏｄ γ（Ｎ） を満たす、あるメッセージＭにより、 １＝Ｍ^ｅｄ ｍｏｄ Ｎ が成立するｓ，ｒを決定する。

【００６８】次に、分散デジタル署名装置について説明
する。

【００６９】署名、検証において、ＲＳＡ暗号との差分
は、分散鍵ｄｉを使って Ｓｉ＝Ｍ^di ｍｏｄ ｎ（Ｍは平文） を一度計算して、その後にＳ１，Ｓ２，Ｓ３及びｍｏｄ
ｎと掛け合わせたものが真の署名となることである。

【００７０】まず、署名生成は、各サーバがそれぞれメ
ッセージＭに対して、 Ｓ_i ＝Ｍ^di ｍｏｄ Ｎ により署名を行うことで分散署名が成される。

【００７１】また、真の署名Ｓは、 Ｓ＝Π_i=1,2,…,kＳ_i ｍｏｄ Ｎ により生成される。

【００７２】この署名についての検証は、 Ｓ^e ＝Ｍ ｍｏｄ Ｎ により行われる。

【００７３】上述してきたＰ² Ｑを用いた分散鍵生成方
式の有効性を示すためにソフトウェアにより実装を行っ
た。

【００７４】同じ計算機環境で、同じビット長の鍵生成
に対して Boneh-Franklin 方式との比較を行った。同じ
環境で実装した結果、復号化アルゴリズムがＲＳＡ暗号
より高速となった。数値結果を次の表に示す。

【００７５】

【表１】 このように従来の Boneh-Franklin の分散鍵生成法を利
用して鍵生成を行った場合には非常に多くの計算量を必
要とし、時間を要したのに対し、本実施形態における分
散鍵生成法は、処理を高速で行うことができ、非常に効
率的であることは明らかである。

【００７６】

【発明の効果】以上説明したように、本願発明によれ
ば、分散鍵生成法を利用して鍵生成を行う場合に、処理
を高速で行うことができ、非常に効率的である。また、
分散された各暗号鍵生成手段では、自ら生成した分散鍵
部分のみ以外知り得ず、たとえば他の暗号鍵生成手段で
生成された分散鍵部分及び暗号鍵そのものを知ることは
できないことから安全性の強度に優れたものとなる。

【図面の簡単な説明】

【図１】本発明の基本的な概念を示すブロック図であ
る。

【図２】本発明に係る分散鍵生成の処理手順を概略的に
示すフローチャートである。

【図３】暗号化復号化鍵生成の処理手順を概略的に示す
フローチャートである。

───────────────────────────────────────────────────── フロントページの続き (54)【発明の名称】 暗号鍵分散生成方法、署名生成・検証方法、暗号鍵分散生成装置、署名生成・検証装置、暗号鍵 分散生成プログラムおよび署名生成・検証プログラムをそれぞれ記録したコンピュータ読み取り 可能な記録媒体

Claims (10)

(57)【特許請求の範囲】
1. 【請求項１】 任意の通信手段で相互に接続され、公開
   鍵暗号方式の暗号鍵を生成する暗号鍵生成手段をそれぞ
   れ有する複数のサーバｉ（ｉ＝１，２，・・・，ｋ）が
   分散して暗号鍵を生成する暗号鍵分散生成方法であっ
   て、 第１の公開鍵ｎと第２の公開鍵ｅとを用いて、平文Ｍか
   ら暗号文Ｃ＝Ｍ^ｅ（ｍｏｄｎ）を得るに際して、 各サーバｉが２個の乱数ｐｉおよびｑｉを自らの持つ秘
   密情報である第１の分散秘密鍵としてそれぞれ生成する
   ステップと、 各サーバが自らの持つ秘密情報を他のサーバに漏らすこ
   となく全てのサーバで共有する計算ができるＢＧＷプロ
   トコルを用いて前記第１の公開鍵ｎの候補であるＮ＝
   （Σ_{ｉ＝１，２，…，ｋ}ｐｉ）^２（Σ
   _{ｉ＝１，２，…，ｋ}ｑｉ）を生成するステップとを行う
   ことを特徴とする暗号鍵分散生成方法。
2. 【請求項２】 請求項１記載の暗号鍵分散生成方法であ
   って、 前記第１の公開鍵ｎの候補であるＮを生成するステップ
   に続いて、さらに、 前記各サーバｉが、全てのサーバに共通な乱数ｇを用い
   てｖ_ｐｉ＝ｇ^ｐｉ ｍｏｄＮをそれぞれ計算し、この計
   算した値を他のサーバに送信するステップと、 前記各サーバｉがｖ_ｐ＝Π_{ｉ＝１，２，…，ｋ}ｖ_ｐｉ
   ｍｏｄＮをそれぞれ計算するステップと、 サーバ１がｕ_１＝ｇ^Ｎ ｍｏｄＮ、サーバｉ（ここでｉ
   ＝２，・・・，ｋ−１）がｕ_ｉ＝ｖ_ｐ ^{ｐｉ＋ｑｉ}ｍｏｄ
   Ｎ、サーバｋがｕ_ｋ＝ｖ_ｐ ^{ｐｋ＋ｑｋ―１} ｍｏｄＮを
   それぞれ計算して相互に配布するステップと、 このステップでの計算値がｕ_１＝ｕ_ｋΠ
   _{ｉ＝２，…，ｋ―１}ｕ_ｉ ｍｏｄＮを満たすかどうかを
   前記各サーバｉが検証し、この式が成り立つ場合には、
   Σ_{ｉ＝１，２，…，ｋ}ｐｉおよびΣ_{ｉ＝１，２，…，ｋ}
   ｑｉが素数であると判定するステップとを行うことを特
   徴とする暗号鍵分散生成方法。
3. 【請求項３】 請求項２記載の暗号鍵分散生成方法であ
   って、 前記Σ_{ｉ＝１，２，…，ｋ}ｐｉおよび前記Σ
   _{ｉ＝１，２，…，ｋ}ｑｉが素数であるとき、これらの素
   数Σ_{ｉ＝１，２，…，ｋ}ｐｉおよびΣ
   _{ｉ＝１，２，…，ｋ}ｑｉを用いてγ（Ｎ）＝（Σ
   _{ｉ＝１，２，…，ｋ}ｐｉ）｛（Σ_{ｉ＝１，２，…，ｋ}ｐ
   ｉ）−１｝｛（Σ_{ｉ＝１，２，…，ｋ}ｑｉ）−１｝とし
   て、 前記各サーバｉが、設定される素数Ｒに対して前記ＢＧ
   Ｗプロトコルを用いて、γ（Ｎ）＝Σ
   _{ｉ＝１，２，…，ｋ}γ_ｉ（Ｎ）−ｓＲ（ここで、ｓ＝
   ０，１，２，…，ｋ−１）を満たすγ_ｉ（Ｎ）を生成す
   るステップと、 第２の公開鍵として選択されるｅを用いて前記各サーバ
   ｉがγ_ｉ（Ｎ）ｍｏｄｅの値を他のサーバにそれぞれ送
   信するステップと、 前記各サーバｉが、δ_ｅ，ｓ＝１／（γ（Ｎ）−ｓＲ）
   ｍｏｄｅ、およびｄ_ｉ，ｓ ＝［（−δ_ｅ，ｓγ
   _ｉ（Ｎ））／ｅ］（但し、ｓ＝０，１，２，…，ｋ−
   １）をそれぞれ計算するステップと、 前記各サーバｉが、真の復号鍵である第２の秘密鍵をｄ
   （ここでｄは、ｅｄ＝１ ｍｏｄγ（Ｎ）を満たす）と
   するとき、このｄが満たす関係式ｄ＝Σ
   _{ｉ＝１，２，…，ｋ}ｄ_ｉ，ｓ＋ｒ ｍｏｄγ（Ｎ）と、
   あるメッセージＭにより、１＝Ｍ^ｅｄ ｍｏｄＮが成立
   するｓ，ｒを決定することにより、第２の分散秘密鍵ｄ
   _ｉをそれぞれ生成するステップとを行うことを特徴とす
   る暗号鍵分散生成方法。
4. 【請求項４】 請求項３記載の暗号鍵分散生成方法によ
   って生成された第１の公開鍵Ｎ、第２の公開鍵ｅ、およ
   び第２の分散秘密鍵ｄ_ｉを用いて署名を行い、かつ当該
   署名の検証を行う署名生成・検証方法であって、 任意の通信手段で相互に接続される複数のサーバｉ（ｉ
   ＝１，２，・・・，ｋ）が前記第１の公開鍵Ｎおよび自
   らの前記第２の分散秘密鍵ｄ_ｉを用いてメッセージＭに
   対してそれぞれ行う分散署名Ｓ_ｉ＝Ｍ^ｄｉ ｍｏｄＮを
   用いて、真の署名Ｓ＝Π_{ｉ＝１，２，…，ｋ}Ｓ_ｉ ｍｏ
   ｄＮを生成し、 この署名についての検証をＳ^ｅ＝Ｍ ｍｏｄＮにより行
   うことを特徴とする署名生成・検証方法。
5. 【請求項５】 任意の通信手段で相互に接続される複数
   のサーバｉ（ｉ＝１，２，・・・，ｋ）から構成され、
   公開鍵暗号方式の暗号鍵を分散して生成する暗号鍵分散
   生成装置であって、 第１の公開鍵ｎと第２の公開鍵ｅとを用いて、平文Ｍか
   ら暗号文Ｃ＝Ｍ^ｅ（ｍｏｄ ｎ）を得るに際して、 サーバｉごとに２個の乱数ｐｉおよびｑｉを自らの持つ
   秘密情報である第１の分散秘密鍵として生成する乱数生
   成手段と、 各サーバが自らの持つ秘密情報を他のサーバに漏らすこ
   となく全てのサーバで共有する計算ができるＢＧＷプロ
   トコルを用いて前記第１の公開鍵ｎの候補であるＮ＝
   （Σ_{ｉ＝１，２，…，ｋ}ｐｉ）^２（Σ
   _{ｉ＝１，２，…，ｋ}ｑｉ）を生成する公開鍵候補生成手
   段とを有することを特徴とする暗号鍵分散生成装置。
6. 【請求項６】 請求項５記載の暗号鍵分散生成装置であ
   って、 全てのサーバに共通な乱数ｇを選択する共通乱数選択手
   段と、 この共通乱数選択手段で選択した乱数ｇ、および前記第
   １の公開鍵ｎの候補であるＮを用いて、各サーバｉ（こ
   こでｉ＝１，２，・・・，ｋ）でｖ_ｐｉ＝ｇ^ｐｉ ｍｏ
   ｄ Ｎを計算し、この計算したｖ_ｐｉを他のサーバに送
   信する手段と、 サーバ１でｖ_ｐ＝Π_{ｉ＝１，２，…，ｋ}ｖ_ｐｉ ｍｏｄ
   Ｎを計算し、このｖ_ｐを用いてｕ_１＝ｇ^Ｎ ｍｏｄＮを
   計算するサーバ１の計算手段と、 サーバｉ（ここでｉ＝２，・・・，ｋ−１）でｖ_ｐ＝Π
   _{ｉ＝１，２，…，ｋ}ｖ_ｐｉ ｍｏｄＮを計算し、このｖ
   _ｐを用いてｕ_ｉ＝ｖ_ｐ ^{ｐｉ＋ｑｉ} ｍｏｄＮをそれぞれ
   計算するサーバｉ（ｉ＝２，・・・，ｋ−１）の計算手
   段と、 サーバｋでｖ_ｐ＝Π_{ｉ＝１，２，…，ｋ}ｖ_ｐｉ ｍｏｄ
   Ｎを計算し、このｖ_ｐを用いてｕ_ｋ＝ｖ_ｐ
   ^{ｐｋ＋ｑｋ―１} ｍｏｄＮを計算するサーバｋの計算手
   段と、 各サーバの計算手段で計算したｕ_１，ｕ_２，・・・，ｕ
   _ｋを相互に配布する手段と、 ｕ_１＝ｕ_ｋΠ_{ｉ＝２，…，ｋ―１}ｕ_ｉ ｍｏｄＮを満た
   すかどうかを検証し、この式が成り立つ場合には、Σ
   _{ｉ＝１，２，…，ｋ}ｐｉおよびΣ_{ｉ＝１，２，…，ｋ}ｑ
   ｉが素数であると判定する素数判定手段とをさらに有す
   ることを特徴とする暗号鍵分散生成装置。
7. 【請求項７】 請求項６記載の暗号鍵分散生成装置であ
   って、 前記素数判定手段が前記Σ_{ｉ＝１，２，…，ｋ}ｐｉおよ
   び前記Σ_{ｉ＝１，２，…，ｋ}ｑｉが素数であると判定し
   たとき、これらのΣ_{ｉ＝１，２，…，ｋ}ｐｉおよびΣ
   _{ｉ＝１，２，…，ｋ}ｑｉを用いてγ（Ｎ）＝（Σ
   _{ｉ＝１，２，…，ｋ}ｐｉ）｛（Σ_{ｉ＝１，２，…，ｋ}ｐ
   ｉ）−１｝｛（Σ_{ｉ＝１，２，…，ｋ}ｑｉ）−１｝とし
   て、 設定される素数Ｒに対して前記ＢＧＷプロトコルを用い
   て、γ（Ｎ）＝Σ_{ｉ＝１，２，…，ｋ}γ_ｉ（Ｎ）−ｓＲ
   （ここで、ｓ＝０，１，２，…，ｋ−１）を満たすγ_ｉ
   （Ｎ）をサーバｉ（ここでｉ＝１，２，・・・，ｋ）で
   それぞれ生成するサーバｉの生成手段と、 乱数ｅを第２の公開鍵として選択する乱数選択手段と、 前記サーバｉの生成手段でそれぞれ生成したγ_ｉ（Ｎ）
   および前記乱数選択手段で選択したｅを用いてδ_ｅ，ｓ
   ＝１／（γ（Ｎ）−ｓＲ） ｍｏｄｅ、およびｄ_ｉ，ｓ
   ＝［（−δ_ｅ，ｓγ_ｉ（Ｎ））／ｅ］（但し、ｓ＝
   ０，１，２，…，ｋ−１）をそれぞれ計算するサーバｉ
   の計算手段と、 真の復号鍵である第２の秘密鍵をｄ（ここでｄは、ｅｄ
   ＝１ ｍｏｄγ（Ｎ）を満たす）とするとき、ｄ＝Σ
   _{ｉ＝１，２，…，ｋ}ｄ_ｉ，ｓ＋ｒ ｍｏｄγ（Ｎ）と、
   あるメッセージＭにより、１＝Ｍ^ｅｄ ｍｏｄＮが成立
   するｓ，ｒを決定することによって第２の分散秘密鍵ｄ
   _ｉをそれぞれ生成するサーバｉの秘密鍵生成手段とをさ
   らに有することを特徴とする暗号鍵分散生成装置。
8. 【請求項８】 請求項７記載の暗号鍵分散生成装置によ
   って生成される第１の公開鍵Ｎ、第２の公開鍵ｅ、およ
   び第２の分散秘密鍵ｄ_ｉを用いて署名を行い、かつ当該
   署名の検証を行う署名生成・検証装置であって、 任意の通信手段で相互に接続される複数のサーバｉ（ｉ
   ＝１，２，・・・，ｋ）が前記第１の公開鍵Ｎおよび自
   らの前記第２の分散秘密鍵ｄ_ｉを用いてメッセージＭに
   対して行う分散署名Ｓ_ｉ＝Ｍ^ｄｉ ｍｏｄＮを用いて、
   真の署名Ｓ＝Π_{ｉ＝１，２，…，ｋ}Ｓ_ｉ ｍｏｄＮを生
   成する署名手段と、 この署名手段で生成した署名についての検証をＳ^ｅ＝Ｍ
   ｍｏｄＮにより行う署名検証手段とを有することを特
   徴とする署名生成・検証装置。
9. 【請求項９】 請求項１乃至３のいずれか１項に記載し
   た暗号鍵分散生成方法をコンピュータに実行させるため
   の暗号鍵分散生成プログラムを記録したコンピュータ読
   み取り可能な記録媒体。
10. 【請求項１０】 請求項４に記載した署名生成・検証方
    法をコンピュータに実行させるための署名生成・検証プ
    ログラムを記録したコンピュータ読み取り可能な記録媒
    体。