説明

鍵共有装置、鍵共有システム、鍵共有方法及びプログラム

【課題】KCI攻撃に強い鍵共有方式を提供する。
【解決手段】鍵共有装置110−1が、任意値r(1)を生成し、X(1)=gr(1)∈Gを生成する。X(1)は鍵共有装置110−2に入力される。鍵共有装置110−2が、任意値r(2)を生成し、X(2)=gr(2)∈Gを生成する。X(2)は鍵共有装置110−1に入力される。鍵共有装置110−1は、a(1)、A(2)、r(1)、X(2)とを用い、巡回群Gの元gW(u)∈Gをσ(u)として生成し、鍵共有装置110−2は、a(2)、A(1)、r(2)、X(1)とを用い、巡回群Gの元gW(u)∈Gをσ(u)として生成する。なお、W(u)=w(u,1)・w(u,2)の積であり、w(u,p)は、a(p)とr(p)の線形和である。鍵共有装置110−1,2は、σ(u)に基づいて値が定まる鍵Kを生成する。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、情報セキュリティ技術の応用に関し、特に、装置間で鍵を共有する鍵交換技術に関する。
【背景技術】
【0002】
装置間で鍵を共有する鍵交換方式の従来技術の一つに以下の方式がある(例えば、非特許文献1参照)。
【0003】
[公開パラメータ]
GをLビット(L≧1)の位数q(qは素数)の巡回群、gをGの生成元とする。H:{0,1}→{0,1}を任意長のビット列をLビットのビット列に写すハッシュ関数とする。また、ID(algo)を、共有した鍵Kの使いかた(認証鍵、暗号化鍵など)を記述するアルゴリズム識別子とする。
【0004】
[鍵交換]
識別子ID(1)と秘密鍵a(1)∈Zと公開鍵A(1)=ga(1)∈Gをもつ装置PA(1)と、識別子ID(2)と秘密鍵a(2)∈Zと公開鍵A(2)=ga(2)∈Gをもつ装置PA(2)とは、以下のようにして鍵Kを共有する。
【0005】
1.装置PA(1)は、乱数r(1)∈Zを生成し、識別子ID(1)とX(1)=gr(1)∈Gを装置PA(2)に送る。
【0006】
2.装置PA(2)は、乱数r(2)∈Zを生成し、識別子ID(2)とX(2)=gr(2)∈GをPA(1)に送る。
【0007】
3.装置PA(1)は、φ(1)=X(2)r(1)∈Gとφ(2)=A(2)a(1)∈Gを計算し、鍵K=H(φ(1),φ(2),ID(1),ID(2),ID(algo))を計算する。
【0008】
4.装置PA(2)は、φ(1)=X(1)r(2)∈Gとφ(2)=A(1)a(2)∈Gを計算し、鍵K=H(φ(1),φ(2),ID(1),ID(2),ID(algo))を計算する。
【0009】
ここで、巡回群Gでの演算は可換であるため、装置PA(1),PA(2)で生成されるφ(1),φ(2)は、いずれも、
φ(1)=gr(1)・r(2)∈G …(1)
φ(2)=ga(1)・a(2)∈G …(2)
となり、装置PA(1),PA(2)で同一の鍵Kが共有される。
【先行技術文献】
【非特許文献】
【0010】
【非特許文献1】Elaine Barker, Don Johnson, and Miles Smid, "NIST Special Publication 800-56A: Recommendation for Pair-WiseKey Establishment Schemes Using Discrete Logarithm Cryptography", Section 6.1.1.2
【発明の概要】
【発明が解決しようとする課題】
【0011】
しかし、非特許文献1の方式は、KCI攻撃(Key-Compromise Impersonation attack) に弱いという問題がある。
【0012】
攻撃者Mは以下のようにKCI攻撃を行うことができる。
【0013】
0.攻撃者Mは、装置PA(1)の秘密鍵a(1)∈Zを得る。
【0014】
1.装置PA(1)は、乱数r(1)∈Zを生成し、識別子ID(1)とX(1)=gr(1)∈Gを装置PA(2)に送る。
【0015】
2.攻撃者Mは、乱数r(2)∈Zを生成し、識別子ID(2)とX(2)=gr(2)∈GをPA(1)に送る。
【0016】
3.装置PA(1)は、φ(1)=X(2)r(1)∈Gとφ(2)=A(2)a(1)∈Gを計算し、鍵K=H(φ(1),φ(2),ID(1),ID(2),ID(algo))を計算する。
【0017】
4.攻撃者Mは、φ(1)=X(1)r(2)∈Gとφ(2)=A(2)a(1)∈Gを計算し、鍵K=H(φ(1),φ(2),ID(1),ID(2),ID(algo))を計算する。
【0018】
以上のように、装置PA(1)の秘密鍵a(1)∈Zを得た攻撃者Mは、装置PA(2)の秘密鍵a(2)∈Zを知らないにもかかわらず、装置PA(2)に成り済まして装置PA(1)と鍵Kを共有できる。
【0019】
本発明はこのような点に鑑みてなされたものであり、KCI攻撃に強い鍵共有技術を提供することを目的とする。
【課題を解決するための手段】
【0020】
本発明では、他の装置と鍵を共有する鍵共有装置は、少なくとも、整数の秘密値a(i)又は巡回群Gの元Z(i)=ga(i)・MSK∈Gと、他の装置に対応する巡回群Gの元である公開値A(j)=ga(j)∈Gとを記憶する。なお、i,j∈{1,...,P}、j≠iであり、Pは2以上の整数定数、gはgによって巡回群Gのすべての元を表現できる生成元であり、MSK,m及びa(j)は整数である。この鍵共有装置は、以下の処理を実行する。
【0021】
まず、鍵共有装置は、整数の任意値r(i)を生成し、第1任意元X(i)=gr(i)∈Gを生成し、第1任意元X(i)を出力する。この第1任意元X(i)は他の装置に入力される。
【0022】
また、鍵共有装置には、他の装置から出力された第2任意元X(j)=gr(j)∈Gが入力される。なお、r(j)は整数である。
【0023】
鍵共有装置は、少なくとも、秘密値a(i)又は元Z(i)=ga(i)・MSK∈Gと、公開値A(j)=ga(j)∈Gと、任意値r(i)と、第2任意元X(j)=gr(j)∈Gとを用い、巡回群Gの元gW(u)∈Gを共有元σ(u)として生成するか、又は、さらに巡回群Gの元を巡回群Gの元に写像する関数eを用い、巡回群Gの元gW(u)∈Gを共有元σ(u)として生成する。なお、W(u)は、整数w(u,1),...,w(u,P)を含むP個以上の整数の積であり、整数w(u,p)は、a(p)とr(p)とを含む複数の整数の線形和であり、p∈{1,...,P}、u∈{1,...,U}、Uは1以上の整数定数であり、gはgによって巡回群Gのすべての元を表現できる生成元である。
【0024】
そして、鍵共有装置は、少なくとも共有元σ(u)に基づいて値が定まる鍵Kを生成し、当該鍵Kを出力する。
【0025】
ここで、W(u)は、整数w(u,1),...,w(u,P)を含むP個以上の整数の積であり、整数w(u,p)は、a(p)とr(p)(p∈{1,...,P})とを含む複数の整数の線形和である。この場合、鍵共有装置は、自ら生成した任意値r(i)と、それに対応する秘密値a(i)又は元Z(i)=ga(i)・MSK∈Gと、の両方を知らなければ共有元σ(u)を生成できない。そのため、他の装置の整数a(j)を知った攻撃者が、任意値r(i)を生成して鍵共有装置に成り済まそうとしても、攻撃者は任意値r(i)に対応する秘密値a(i)を知らないため、正しいσ(u)を生成できない。よって、KCI攻撃は成功しない。
【発明の効果】
【0026】
以上のように、本発明の鍵共有技術はKCI攻撃に強い。
【図面の簡単な説明】
【0027】
【図1】図1(A)は、本形態の鍵共有システムの全体構成を例示するための図である。図1(B)は、本形態の鍵共有装置の基本構成を説明するための図である。
【図2】図2は、第1実施形態の鍵共有システムの構成を説明するためのブロック図である。
【図3】図3(A)は、共有元生成部の構成を説明するためのブロック図である。図3(B)は、共有元生成部の構成を説明するためのブロック図である。
【図4】図4(A)は、鍵共有装置の鍵共有処理を説明するためのフローチャートである。図4(B)は、鍵共有装置の鍵共有処理を説明するためのフローチャートである。
【図5】図5は、第2実施形態の鍵共有システムの構成を説明するためのブロック図である。
【図6】図6は、第2実施形態の鍵共有システムの構成を説明するためのブロック図である。
【図7】図7は、第2実施形態の鍵共有システムの構成を説明するためのブロック図である。
【図8】図8(A)は、共有元生成部の構成を説明するためのブロック図である。図8(B)は、共有元生成部の構成を説明するためのブロック図である。
【図9】図9は、共有元生成部の構成を説明するためのブロック図である。
【図10】図10(A)は、鍵共有装置の鍵共有処理を説明するためのフローチャートである。図10(B)は、鍵共有装置の鍵共有処理を説明するためのフローチャートである。
【図11】図11は、鍵共有装置の鍵共有処理を説明するためのフローチャートである。
【図12】図12は、第3実施形態の鍵共有システムの構成を説明するためのブロック図である。
【図13】図13は、第3実施形態の鍵共有システムの構成を説明するためのブロック図である。
【図14】図14(A)は、共有元生成部の構成を説明するためのブロック図である。図14(B)は、共有元生成部の構成を説明するためのブロック図である。
【図15】図15(A)は、鍵共有装置の鍵共有処理を説明するためのフローチャートである。図15(B)は、鍵共有装置の鍵共有処理を説明するためのフローチャートである。
【発明を実施するための形態】
【0028】
以下、図面を参照して本発明の実施形態を説明する。
【0029】
〔概要〕
まず、本形態の概要を説明する。
【0030】
図1(A)は、本形態の鍵共有システム1の全体構成を例示するための図であり、図1(B)は、本形態の鍵共有装置の基本構成を説明するための図である。
【0031】
図1(A)に例示するように、本形態の鍵共有システム1は、複数の鍵共有装置10−p(p∈{1,...,P}、Pは2以上の整数定数)を有し、例えば、ネットワーク20を通じて情報のやり取りが可能に構成されている。なお、複数の鍵共有装置10−p間での情報のやり取りはネットワーク経由で行われるものに限定されず、例えば、USBメモリなどの可搬型の記録媒体への情報の読み書きによって行われてもよい。
【0032】
鍵共有装置10−iの記憶部11−i(図1(B))には、少なくとも、整数の秘密値a(i)又は巡回群Gの元Z(i)=ga(i)・MSK∈Gと、他の鍵共有装置10−jに対応する巡回群Gの元である公開値A(j)=ga(j)∈Gと、が格納される。なお、i,j∈{1,...,P}、j≠i、gはgによって巡回群Gのすべての元を表現できる生成元、MSK,m及びa(j)は整数である。
【0033】
鍵共有装置10−iが他の鍵共有装置10−jと鍵を共有する場合、まず、鍵共有装置10−iの任意値生成部12−i(図1(B))が整数の任意値r(i)を生成し、任意値r(i)を出力する。次に、任意元生成部13−iが任意値r(i)を入力として、第1任意元X(i)=gr(i)∈Gを生成し、第1任意元X(i)=gr(i)∈Gを出力する。出力部14−iは、第1任意元X(i)=gr(i)∈Gを入力として、当該第1任意元X(i)=gr(i)∈Gを出力する。第1任意元X(i)=gr(i)∈Gは、他の鍵共有装置10−jに入力される。
【0034】
また、鍵共有装置10−iの入力部15−iには、他の鍵共有装置10−jから出力された第2任意元X(j)=gr(j)∈Gが入力される。なお、r(j)は整数である。共有元生成部16−iは、少なくとも、秘密値a(i)又は元Z(i)=ga(i)・MSK∈Gと、公開値A(j)=ga(j)∈Gと、任意値r(i)と、第2任意元X(j)=gr(j)∈Gと入力とし、巡回群Gの元gW(u)∈Gを共有元σ(u)として生成するか、又は、さらに巡回群Gの元を巡回群Gの元に写像する関数eを用い、巡回群Gの元gW(u)∈Gを共有元σ(u)として生成する。なお、W(u)は、整数w(u,1),...,w(u,P)を含むP個以上の整数の積であり、整数w(u,p)は、a(p)とr(p)とを含む複数の整数の線形和であり、p∈{1,...,P}、u∈{1,...,U}、Uは1以上の整数定数であり、gはgによって巡回群Gのすべての元を表現できる生成元である。共有元生成部16−iは、生成した共有元σ(u)を出力する。
【0035】
鍵生成部17−iは、共有元σ(u)を入力として、少なくとも共有元σ(u)に基づいて値が定まる鍵K(少なくとも共有元σ(u)に値が依存する鍵K)を生成し、当該鍵Kを出力する。
【0036】
鍵共有装置10−iは、自ら生成した任意値r(i)と、それに対応する秘密値a(i)又は元Z(i)=ga(i)・MSK∈Gと、の両方を知らなければ共有元σ(u)を生成できない。そのため、鍵共有装置10−jの整数a(j)を知った攻撃者が、任意値r(i)を生成して鍵共有装置10−iに成り済まそうとしても、攻撃者は任意値r(i)に対応する秘密値a(i)を知らないため、正しいσ(u)を生成できない。よって、KCI攻撃は成功しない。
【0037】
また、少なくとも一部の整数w(u,p)が、少なくとも一方が整数d(p)によって重み付けされたa(p)とr(p)とを含む複数の整数の線形和であり、整数d(p)が、第1任意元X(i)及び/又は第2任意元X(j)に応じて値が定まる整数であってもよい。例えば、整数d(p)が、第1任意元X(i)に応じて値が定まる整数であった場合、整数d(p)の値は、第1任意元X(i)が定まるまで特定できないため、鍵共有装置10−i又はそれに成り済ました攻撃者は、鍵共有相手である鍵共有装置10−jによる共有元σ(u)の生成時にキャンセルされてしまうような第1任意元X(i)を、意図的に生成できない。また、例えば、整数d(p)が、第2任意元X(j)に応じて値が定まる整数であった場合、整数d(p)の値は、第2任意元X(j)が定まるまで特定できないため、鍵共有装置10−j又はそれに成り済ました攻撃者は、鍵共有相手である鍵共有装置10−iによる共有元σ(u)の生成時にキャンセルされてしまうような第2任意元X(j)を意図的に生成できない。以上により、安全性がより向上する。
【0038】
また、共有元生成部16−iが、複数種類の共有元σ(1),...σ(U)(U≧2)を生成し、鍵生成部17−iが、複数種類の共有元σ(1),...σ(U)に基づいて値が定まる鍵Kを生成してもよい。この場合、より安全性が向上する。
【0039】
〔第1実施形態〕
次に、本発明の第1実施形態を説明する。第1実施形態では、P=2であり、W(u)=w(u,1)・w(u,2)であり、w(u,p)がa(p)とr(p)との線形和である。また、第1鍵共有装置の記憶部が、少なくとも、秘密値a(i)と公開値A(j)=ga(j)∈Gとを格納し、第1鍵共有装置の共有元生成部が、少なくとも、秘密値a(i)と、公開値A(j)=ga(j)∈Gと、任意値r(i)と、第2任意元X(j)=gr(j)∈Gとを用い、巡回群Gの元gW(u)∈Gを共有元σ(u)として生成する。また、第2鍵共有装置の記憶部が、少なくとも、秘密値a(j)と公開値A(i)=ga(i)∈Gとを格納し、第2鍵共有装置の共有元生成部が、少なくとも、秘密値a(j)と、公開値A(i)=ga(i)∈Gと、任意値r(j)と、第1任意元X(i)=gr(i)∈Gとを用い、巡回群Gの元gW(u)∈Gを共有元σ(u)として生成する。
【0040】
<構成>
図2は、第1実施形態の鍵共有システム100の構成を説明するためのブロック図である。なお、図2では、鍵共有装置間で情報をやり取りするための手段であるネットワークや可搬型の記録媒体の記載は省略してある(他の図でも同様)。
【0041】
図2に例示するように、第1実施形態の鍵共有システム100は、鍵共有装置110−1(第1鍵共有装置)と鍵共有装置110−2(第2鍵共有装置)とを有する。
【0042】
鍵共有装置110−1は、記憶部111−1と、任意値生成部112−1と、任意元生成部113−1と、出力部114−1と、入力部115−1と、共有元生成部116−1と、鍵生成部117−1と、一時メモリ118−1と、制御部119−1とを有する。図3(A)は、共有元生成部116−1の構成を説明するためのブロック図である。図3(A)に例示するように、共有元生成部116−1は、ハッシュ演算部116b−1,116c−1と、共有元演算部116a−u−1(u∈{1,...,U}、Uは1以上の整数定数)とを有する。
【0043】
図2に例示するように、鍵共有装置110−2は、記憶部111−2と、任意値生成部112−2と、任意元生成部113−2と、出力部114−2と、入力部115−2と、共有元生成部116−2と、鍵生成部117−2と、一時メモリ118−2と、制御部119−2とを有する。図3(B)は、共有元生成部116−2の構成を説明するためのブロック図である。図3(B)に例示するように、共有元生成部116−2は、ハッシュ演算部116b−2,116c−2と、共有元演算部116a−u−2(u∈{1,...,U})とを有する。
【0044】
なお、鍵共有装置110−1,2は、例えば、CPU(Central Processing Unit)、RAM(Random Access Memory)、ROM(Read-Only Memoryなどを備える公知のコンピュータに所定のプログラムが読み込まれて実行されることで構成される。すなわち、任意値生成部112−1,2、任意元生成部113−1,2、共有元生成部116−1,2、鍵生成部117−1,2及び制御部119−1,2は、例えば、CPUが所定のプログラムを実行することで構成される処理部である。また、任意値生成部112−1,2を公知の乱数生成用IC(integrated Circuit)で構成するなど、処理部の少なくとも一部を集積回路で構成してもよい。また、記憶部111−1,2及び一時メモリ118−1,2は、例えば、RAM、レジスタ、キャッシュメモリ、集積回路内の素子若しくはハードディスク等の補助記憶装置、又は、これらの少なくとも一部の結合からなる記憶領域である。また、出力部114−1,2及び入力部115−1,2は、例えば、モデム、LAN(Local Area Network)カード等の通信装置や、記録媒体に情報を読み書きするリーダライタなどである。
【0045】
また、鍵共有装置110−1,2は、それぞれ、制御部119−1,2の制御のもと各処理を実行する。また、以下では説明を簡略化するが、各処理部から出力されたデータは、逐一、一時メモリ118−1,2又は記憶部111−1,2に格納される。一時メモリ118−1,2又は記憶部111−1,2に格納されたデータは、必要に応じて読み出され、各処理部に入力されてその処理に利用される。
【0046】
<公開パラメータ>
第1実施形態では、以下を公開パラメータとする。
【0047】
G:Lビット(L≧1)の位数q(qは素数)の巡回群。巡回群Gでの演算は可換である。巡回群Gの具体例は、qを法とした剰余類の乗法群や、楕円曲線上の点からなる部分群などである。
【0048】
g:巡回群Gの生成元。g(mは整数)によって巡回群Gのすべての元を表現できる。なお、gα∈Gは、生成元gに対し、巡回群G上で定義された演算をα回(αは整数)実行することを意味する。例えば、巡回群Gがpを法とした剰余類の乗法群の場合、巡回群G上で定義された演算はpを法とした剰余乗算であり、gα∈Gはgα mod pとなる。また、巡回群Gが楕円曲線上の部分群である場合、巡回群G上で定義された演算は楕円曲線上の楕円加算であり、gα∈Gは楕円曲線上の点である生成元gに対する楕円曲線上でのα倍演算となる。
【0049】
F:G→[0,q1/2]。巡回群Gの元を0以上q1/2以下の整数に写すハッシュ関数。
【0050】
H:{0,1}→{0,1}。任意長のビット列をLビットのビット列に写すハッシュ関数。
【0051】
ID(prot):鍵交換方式の名称の識別子。
【0052】
<事前処理>
鍵共有処理の事前処理として以下の処理が実行される。
【0053】
鍵共有装置110−1の記憶部111−1に、鍵共有装置110−1の秘密値(秘密鍵)a(1)∈Zと、鍵共有装置110−1に対応する巡回群Gの元である公開値(公開鍵)A(1)=ga(1)∈Gと、鍵共有装置110−2に対応する巡回群Gの元である公開値(公開鍵)A(2)=ga(2)∈Gと、鍵共有装置110−1の識別子ID(1)と、識別子ID(prot)とが格納される。また、鍵共有装置110−2の記憶部111−2に、鍵共有装置110−2の秘密値(秘密鍵)a(2)∈Zと、鍵共有装置110−1に対応する巡回群Gの元である公開値(公開鍵)A(1)=ga(1)∈Gと、鍵共有装置110−2に対応する巡回群Gの元である公開値(公開鍵)A(2)=ga(2)∈Gと、鍵共有装置110−2の識別子ID(2)と、識別子ID(prot)とが格納される。なお、Zは、法qについての整数の剰余環を意味し、その一例は0以上q−1以下の整数から構成される有限集合である。また、識別子ID(1),ID(2)は、例えば、メールアドレス、電話番号などである。
【0054】
<鍵共有処理>
図4(A)は、鍵共有装置110−1の鍵共有処理を説明するためのフローチャートであり、図4(B)は、鍵共有装置110−2の鍵共有処理を説明するためのフローチャートである。
【0055】
鍵共有装置110−1(図2)の任意値生成部112−1は、任意値r(1)∈Zを生成して出力する(図4(A)/ステップS112−1)。なお、任意値r(1)∈Zは、例えば、公知の擬似乱数生成アルゴリズムを用いて生成された擬似乱数や、予め定められた順序でZから選択された値である。任意元生成部113−1には、任意値r(1)∈Zが入力され、任意元生成部113−1は、任意値r(1)を用い、任意元X(1)=gr(1)∈Gを生成して出力する(ステップS113−1)。任意元X(1)=gr(1)∈Gと記憶部111−1から読み出された識別子ID(1)とが出力部114−1に入力され、出力部114−1は、任意元X(1)=gr(1)∈Gと識別子ID(1)とを出力(ネットワークへの送信や可搬型記録媒体への格納など)する(ステップS114−1)。任意元X(1)=gr(1)∈Gと識別子ID(1)とは、鍵共有装置110−2に送られる。
【0056】
一方、鍵共有装置110−2(図2)の任意値生成部112−2は、任意値r(2)∈Zを生成して出力する(図4(B)/ステップS112−2)。なお、任意値r(2)∈Zは、例えば、公知の擬似乱数生成アルゴリズムを用いて生成された擬似乱数や、予め定められた順序でZから選択された値である。任意元生成部113−2には、任意値r(2)∈Zが入力され、任意元生成部113−2は、任意値r(2)を用い、任意元X(2)=gr(2)∈Gを生成して出力する(ステップS113−2)。任意元X(2)=gr(2)∈Gと記憶部111−2から読み出された識別子ID(2)とが出力部114−2に入力され、出力部114−2は、任意元X(2)=gr(2)∈Gと識別子ID(2)とを出力(ネットワークへの送信や可搬型記録媒体への格納など)する(ステップS114−2)。任意元X(2)=gr(2)∈Gと識別子ID(2)とは、鍵共有装置110−1に送られる。
【0057】
鍵共有装置110−1の入力部115−1には、任意元X(2)=gr(2)∈Gと識別子ID(2)とが入力される(図4(A)/ステップS115−1)。任意元X(2)=gr(2)∈Gは共有元生成部116−1に送られ、識別子ID(2)は記憶部111−1に格納される。
【0058】
共有元生成部116−1には、入力部115−1から送られた任意元X(2)=gr(2)∈Gと、記憶部111−1から読み出された秘密値a(1)及び公開値A(2)=ga(2)∈Gと、任意値生成部112−1で生成(ステップS112−1)された任意値r(1)∈Zと、任意元生成部113−1で生成(ステップS113−1)された任意元X(1)=gr(1)∈Gとが入力される。共有元生成部116−1は、これらを用い、巡回群Gの元gW(u)∈G(u∈{1,...,U}、Uは1以上の整数定数)を共有元σ(u)として生成して出力する(ステップS116−1)。本形態では、
W(u)=w(u,1)・w(u,2)∈Zq …(3)
w(u,1)=(r(1)・s(u,1)+a(1)・t(u,1))∈Zq …(4)
w(u,2)=(r(2)・s(u,2)+a(2)・t(u,2))∈Zq …(5)
を満たすgW(u)∈Gが、共有元σ(u)として生成される。s(u,1),s(u,2),t(u,1),t(u,2)∈Zはuごとに定まる定数又は変数である。s(u,1),s(u,2),t(u,1),t(u,2)∈Z及びUの設定は任意でよいが、すべてのuについてs(u,1)とt(u,1)とや、s(u,2)とt(u,2)とが、必ず0となる設定は好ましくない。以下に、s(u,1),s(u,2),t(u,1),t(u,2)∈Z及びUの設定例と、そのときのステップS116−1の処理とを例示する。
【0059】
[ステップS116−1の例]
本形態では、
U=2 …(6)
s(1,1)=1, t(1,1)=1, s(1,2)=1, t(1,2)=d(2) …(7)
s(2,1)=1, t(2,1)=d(1), s(2,2)=1, t(2,2)=1 …(8)
としたステップS116−1の処理を例示する。すなわち、
σ(1)=g(r(1)+a(1))(r(2)+a(2)・d(2)) …(9)
σ(2)=g(r(1)+a(1)・d(1))(r(2)+a(2)) …(10)
とした場合の例を示す。
【0060】
この場合のステップS116−1では、ハッシュ演算部116b−1(図3(A))が、任意元X(1)を入力として、ハッシュ値(第1任意元X(i)に応じて値が定まる整数)
d(1)=F(X(1)) …(11)
を生成して出力する。また、ハッシュ演算部116c−1が、任意元X(2)を入力として、ハッシュ値(第2任意元X(j)に応じて値が定まる整数)
d(2)=F(X(2)) …(12)
を生成して出力する。
【0061】
共有元演算部116a−1−1(図3(A))は、ハッシュ値d(2)と、任意元X(2)=gr(2)∈Gと、秘密値a(1)と、公開値A(2)=ga(2)∈Gと、任意値r(1)∈Zとを入力とし、共有元
σ(1)=(X(2)・A(2)d(2))r(1)+a(1)∈G …(13)
=(gr(2)・ga(2)・d(2))r(1)+a(1)
=g(r(1)+a(1))(r(2)+a(2)・d(2))
を生成して出力する。共有元演算部116a−2−1は、ハッシュ値d(1)と、任意元X(2)=gr(2)∈Gと、秘密値a(1)と、公開値A(2)=ga(2)∈Gと、任意値r(1)∈Zとを入力とし、共有元
σ(2)=(X(2)・A(2))r(1)+a(1)・d(1)∈G …(14)
=(gr(2)・ga(2))r(1)+a(1)・d(1)
=g(r(1)+a(1)・d(1))(r(2)+a(2))
を生成して出力する([ステップS116−1の例]の説明終わり)。
【0062】
鍵生成部117−1(図2)は、少なくとも、共有元生成部116−1から出力された共有元σ(u)に基づいて値が定まる鍵Kを生成して出力する(図4(A)/ステップS117−1)。本形態の例では、鍵生成部117−1に、共有元生成部116−1で生成された共有元σ(u)と、任意元生成部113−1で生成された任意元X(1)(ステップS113−1)と、入力部115−1に入力された任意元X(2)(ステップS115−1)と、記憶部111−1から読み出した公開値A(1),A(2)、識別子ID(1),ID(2),ID(prot)とが入力される。鍵生成部117−1は、これらのビット結合のハッシュ値を鍵
K=H(σ(1), σ(2), X(1), X(2), A(1), A(2), ID(1), ID(2), ID(prot)) …(14')
として生成し、生成した鍵Kを出力する。
【0063】
一方、鍵共有装置110−2の入力部115−2には、任意元X(1)=gr(1)∈Gと識別子ID(1)とが入力される(図4(B)/ステップS115−2)。任意元X(1)=gr(1)∈Gは共有元生成部116−2に送られ、識別子ID(1)は記憶部111−2に格納される。
【0064】
共有元生成部116−2には、入力部115−2から送られた任意元X(1)=gr(1)∈Gと、記憶部111−2から読み出された秘密値a(2)及び公開値A(1)=ga(1)∈Gと、任意値生成部112−2で生成(図4(B)/ステップS112−2)された任意値r(2)∈Zと、任意元生成部113−2で生成(ステップS113−2)された任意元X(2)=gr(2)∈Gが入力される。共有元生成部116−2は、これらを用い、巡回群Gの元gW(u)∈G(u∈{1,...,U}、Uは1以上の整数定数)を共有元σ(u)として生成して出力する(ステップS116−2)。本形態では、鍵共有装置110−1と同じ、前述の式(3)〜(5)を満たすgW(u)∈Gが、共有元σ(u)として生成される。以下に、s(u,1),s(u,2),t(u,1),t(u,2)∈Z及びUの設定例と、そのときのステップS116−2の処理とを例示する。
【0065】
[ステップS116−2の例]
本形態では、鍵共有装置110−1と同じ、前述の式(6)〜(10)を満たす共有元σ(u)を生成する。
【0066】
この場合のステップS116−2では、ハッシュ演算部116b−2(図3(B))が、任意元X(1)を入力として、ハッシュ値(第1任意元X(i)に応じて値が定まる整数)
d(1)=F(X(1)) …(15)
を生成して出力する。また、ハッシュ演算部116c−2が、任意元X(2)を入力として、ハッシュ値(第2任意元X(j)に応じて値が定まる整数)
d(2)=F(X(2)) …(16)
を生成して出力する。
【0067】
共有元演算部116a−1−2(図3(B))は、ハッシュ値d(2)と、任意元X(1)=gr(1)∈Gと、秘密値a(2)と、公開値A(1)=ga(1)∈Gと、任意値r(2)∈Zとを入力とし、共有元
σ(1)=(X(1)・A(1))r(2)+a(2)・d(2)∈G …(17)
=(gr(1)・ga(1))r(2)+a(2)・d(2)
=g(r(1)+a(1))(r(2)+a(2)・d(2))
を生成して出力する。また、共有元演算部116a−2−2は、ハッシュ値d(1)と、任意元X(1)=gr(1)∈Gと、秘密値a(2)と、公開値A(1)=ga(1)∈Gと、任意値r(2)∈Zとを入力とし、共有元
σ(2)=(X(1)・A(1)d(1))r(2)+a(2)∈G …(18)
=(gr(1)・ga(1)・d(1))r(2)+a(2)
=g(r(1)+a(1)・d(1))(r(2)+a(2))
を生成して出力する([ステップS116−2の例]の説明終わり)。
【0068】
鍵生成部117−2(図2)は、少なくとも、共有元生成部116−2から出力された共有元σ(u)に基づいて値が定まる鍵Kを生成して出力する(ステップ図4(B)/S117−2)。本形態の例では、鍵生成部117−2に、共有元生成部116−2で生成された共有元σ(u)と、任意元生成部113−2で生成された任意元X(2)(ステップS113−2)と、入力部115−2に入力された任意元X(1)(ステップS115−2)と、記憶部211−2から読み出した公開値A(1),A(2)、識別子ID(1),ID(2),ID(prot)とが入力される。鍵生成部117−2は、これらのビット結合のハッシュ値を鍵
K=H(σ(1), σ(2), X(1), X(2), A(1), A(2), ID(1), ID(2), ID(prot)) …(19)
として生成し、生成した鍵Kを出力する。
【0069】
<本形態の特徴>
式(13)(14)(17)(18)の変形結果を見ればわかるように、鍵共有装置116−1,2でそれぞれ生成される共有元σ(1)は同一となり、かつ、鍵共有装置116−1,2でそれぞれ生成される共有元σ(2)は同一となる。そして、式(14')(19)を比べれば分かるように、鍵共有装置116−1,2でそれぞれ生成される鍵Kは同一となる。
【0070】
ここで、鍵共有装置116−1が式(13)(14)の共有元σ(1),σ(2)を計算できるのは、鍵共有装置116−1が自らの秘密値a(1)と任意値r(1)とを知っているからである。鍵共有装置116−2の秘密値a(2)を知っている攻撃者は、鍵共有装置116−1に成り済まして任意値r(1)や任意元X(1)を生成することはできても、秘密値a(1)を知らないため、式(13)(14)の共有元σ(1),σ(2)を計算できない。
【0071】
また、鍵共有装置116−2が式(17)(18)の共有元σ(1),σ(2)を計算できるのは、鍵共有装置116−2が自らの秘密値a(2)と任意値r(2)とを知っているからである。鍵共有装置116−1の秘密値a(1)を知っている攻撃者は、鍵共有装置116−2に成り済まして任意値r(2)や任意元X(2)を生成することはできても、秘密値a(2)を知らないため、式(17)(18)の共有元σ(1),σ(2)を計算できない。よって、本形態の方式に対して攻撃者がKCI攻撃を行うことは困難である。
【0072】
また、本形態では、式(11)(12)(15)(16)によって、任意元X(1)又は任意元X(2)に応じて値が定まる整数d(1),d(2)を生成し、これらを用いて式(13)(14)(17)(18)のように共有元σ(1),σ(2)を生成した。そのため、本形態では、高い安全性を確保できる。
【0073】
すなわち、整数d(1)は任意元X(1)に応じて値が定まる整数であるため、整数d(1)の値は、任意元X(1)が定まるまで特定できない。そのため、鍵共有装置110−1又はそれに成り済ました攻撃者は、鍵共有装置110−2による共有元σ(u)の生成時にキャンセルされてしまうような任意元X(1)を、意図的に生成できない。例えば、整数d(1)=1に固定されている場合に、鍵共有装置110−1又はそれに成り済ました攻撃者が任意元としてX(1)=1/A(1)を鍵共有装置110−2に送った場合、鍵共有装置110−2によって生成される共有元σ(1),σ(2)はいずれも1∈Gとなってしまう。これに対し、任意元X(1)に応じて値が定まる整数d(1)を用いた場合には、このような攻撃はできない。なお、任意元X(1)が得られるまで整数d(1)の値を推測することが困難である場合には、より高い安全性を確保できる。同様に、整数d(2)は任意元X(2)に応じて値が定まる整数であるため、整数d(2)の値は、任意元X(2)が定まるまで特定できない。そのため、鍵共有装置110−2又はそれに成り済ました攻撃者は、鍵共有装置110−1による共有元σ(u)の生成時にキャンセルされてしまうような任意元X(2)を、意図的に生成できない。任意元X(2)が得られるまで整数d(2)の値を推測することが困難である場合には、より高い安全性を確保できる。
【0074】
また、本形態では、複数の共有元σ(1),σ(2)を生成することとしたため、高い安全性を確保できる。
【0075】
〔第1実施形態の変形例1〕
第1実施形態の変形例1は、ステップS116−1,2の共有元σ(u)の生成処理の変形例である。第1実施形態の変形例1では、式(7)〜(10)の代わりに、
s(1,1)=1, t(1,1)=1, s(1,2)=1, t(1,2)=1 …(19')
s(2,1)=1, t(2,1)=d(1), s(2,2)=1, t(2,2)=d(2) …(20)
とする。すなわち、
σ(1)=g(r(1)+a(1))(r(2)+a(2)) …(21)
σ(2)=g(r(1)+a(1)・d(1))(r(2)+a(2)・d(2)) …(22)
を満たす共有元σ(u)を生成する。
【0076】
この場合、共有元演算部116a−1−1,116a−2−1(図3(A))が、式(13)(14)の代わりに、共有元
σ(1)=(X(2)・A(2))r(1)+a(1)∈G …(23)
=g(r(1)+a(1))(r(2)+a(2))
σ(2)=(X(2)・A(2)d(2))r(1)+a(1)・d(1)∈G …(24)
=g(r(1)+a(1)・d(1))(r(2)+a(2)・d(2))
を生成して出力する。
【0077】
また、共有元演算部116a−1−2,116a−2−2(図3(B))が、式(17)(18)の代わりに、共有元
σ(1)=(X(1)・A(1))r(2)+a(2)∈G …(25)
=g(r(1)+a(1))(r(2)+a(2))
σ(2)=(X(1)・A(1)d(1))r(2)+a(2)・d(2)∈G …(26)
=g(r(1)+a(1)・d(1))(r(2)+a(2)・d(2))
を生成して出力する。その他は第1実施形態と同様である。
【0078】
その他、U=1として、式(7)〜(10)の代わりに、
s(1,1)=1, t(1,1)=d(1), s(1,2)=1, t(1,2)=d(2)
、すなわち、
σ(1)=g(r(1)+a(1)・d(1))(r(2)+a(2)・d(2))
を満たす共有元σ(u)を生成する構成でもよい。その他、U≧3の構成、ハッシュ値d(1)又はd(2)の一方のみを用いて共有元σ(u)を生成する構成、任意元X(1)と任意元X(2)の両方に依存するハッシュ値d(3)を用いて共有元σ(u)を生成する構成、ハッシュ値d(1),d(2)を用いずに共有元σ(u)を生成する構成なども可能である。また、d(p)は、ハッシュ値に限定されず、任意元X(1)及び/又は任意元X(2)に応じて値が定まる整数であればよい。例えば、任意元X(1)や任意元X(2)の一部のビットをd(p)としてもよいし、任意元X(1)と任意元X(2)とのビット結合値の一部をd(p)としてもよい。また、
r(i)=F’(r’(i),a(i))
としてもよい。なお、F’は、ハッシュ関数F’:{0,1}*→Zであり、r’(i)は乱数である。r(j)についても同様な変形を行ってもよい。これによってU=1の場合でも高い安全性を確保できる。その他、本発明の趣旨を遺脱しない範囲で共有元σ(u)の生成方法を変形可能である。
【0079】
〔第1実施形態の変形例2〕
第1実施形態の変形例2は、ステップS117−1,2の鍵生成処理の変形例である。すなわち、第1実施形態では、式(14')(19)によって鍵Kを生成したが、鍵Kは共有元σ(u)に基づいて値が定まればよい。例えば、式(14')(19)のハッシュ関数Hへの入力値となるσ(u),X(1),X(2),A(1),A(2),ID(1),ID(2),ID(prot)のビット結合の順序には制限はない。また、X(1),X(2),A(1),A(2),ID(1),ID(2),ID(prot)の少なくとも一部が省略されてもよく、アルゴリズム識別子ID(algo)、セッション識別子ID(sess)などの他の情報がビット結合対象に加えられてもよい。例えば、
K=H(σ(1), σ(2), X(1), X(2), A(1), A(2), ID(1), ID(2))
K=H(σ(1), σ(2))
K=H(σ(1), σ(2), X(1), X(2), A(1), A(2), ID(1), ID(2), ID(prot), ID(algo))
K=H(σ(1), σ(2) , X(1), X(2), ID(sess))
などを共有する鍵としてもよい。また、例えば、鍵Kの生成に識別子ID(1),ID(2)を用いない場合、ステップS114−1,2で鍵共有装置110−1,2が識別子ID(1),ID(2)を出力せず、ステップS115−1,2で鍵共有装置110−1,2に識別子ID(1),ID(2)が入力されなくてもよい。また、ハッシュ関数Hの代わりに他の関数が用いられてもよいし、ハッシュ関数を用いずに、共有元σ(u)を含む値のビット結合値をそのまま鍵Kとしてもよい。ただし、ステップS117−1,2の鍵生成のための演算は同一でなければならない。
【0080】
〔第2実施形態〕
次に、本発明の第2実施形態を説明する。第2実施形態では、P=3、i=1、j∈{2,3}であり、W(u)=w(u,1)・w(u,2)・w(u,3)であり、w(u,p)はa(p)とr(p)との線形和である。第2実施形態では、3つの鍵共有装置で鍵の共有を行う。鍵共有装置の記憶部が、少なくとも、秘密値a(i)とA(j)=ga(j)∈Gとを格納し、鍵共有装置の共有元生成部が、少なくとも、秘密値a(i)と、2つの公開値A(j)=ga(j)∈Gと、任意値r(i)と、2つの第2任意元X(j)=gr(j)∈Gと、巡回群Gの2つの元を巡回群Gの1つの元に写像する双線形関数である関数eとを用い、巡回群Gの元gW(u)=e(g,g)W(u)∈Gを共有元σ(u)として生成する。
【0081】
<構成>
図5〜7は、第2実施形態の鍵共有システム200の構成を説明するためのブロック図である。なお、第1実施形態と共通する部分については、第1実施形態と同じ符号を用いて説明を簡略化する。
【0082】
図5に例示するように、第2実施形態の鍵共有システム200は、鍵共有装置210−1(第1鍵共有装置)と鍵共有装置210−2(第2鍵共有装置)と鍵共有装置210−3(第3鍵共有装置)とを有する。
【0083】
図6に例示するように、鍵共有装置210−1は、記憶部211−1と、任意値生成部112−1と、任意元生成部113−1と、出力部214−1と、入力部215−1と、共有元生成部216−1と、鍵生成部217−1と、一時メモリ118−1と、制御部119−1とを有する。図8(A)は、共有元生成部216−1の構成を説明するためのブロック図である。図8(A)に例示するように、共有元生成部216−1は、ハッシュ演算部116b−1,116c−1,216d−1と、共有元演算部216a−u−1(u∈{1,...,U}、Uは1以上の整数定数)とを有する。
【0084】
鍵共有装置210−2は、記憶部211−2と、任意値生成部112−2と、任意元生成部113−2と、出力部214−2と、入力部215−2と、共有元生成部216−2と、鍵生成部217−2と、一時メモリ118−2と、制御部119−2とを有する。図8(B)は、共有元生成部216−2の構成を説明するためのブロック図である。図8(B)に例示するように、共有元生成部216−2は、ハッシュ演算部116b−2,116c−2,216d−2と、共有元演算部216a−u−2(u∈{1,...,U})とを有する。
【0085】
図7に例示するように、鍵共有装置210−3は、記憶部211−3と、任意値生成部212−3と、任意元生成部213−3と、出力部214−3と、入力部215−3と、共有元生成部216−3と、鍵生成部217−3と、一時メモリ218−3と、制御部219−3とを有する。図9は、共有元生成部216−3の構成を説明するためのブロック図である。図9に例示するように、共有元生成部216−3は、ハッシュ演算部216b−3,216c−3,216d−3と、共有元演算部216a−u−3(u∈{1,...,U})とを有する。
【0086】
なお、第1実施形態と同様、鍵共有装置210−1,2,3は、例えば、公知のコンピュータに所定のプログラムが読み込まれて実行されることで構成される。また、鍵共有装置210−1,2,3は、それぞれ、制御部119−1,2、制御部219−3の制御のもと各処理を実行する。また、以下では説明を簡略化するが、各処理部から出力されたデータは、逐一、一時メモリ118−1,2、一時メモリ218−3又は記憶部111−1,2、記憶部211−3に格納される。一時メモリ118−1,2、一時メモリ218−3又は記憶部111−1,2、記憶部211−3に格納されたデータは、必要に応じて読み出され、各処理部に入力されてその処理に利用される。
【0087】
<公開パラメータ>
第2実施形態では、以下を公開パラメータとする。
【0088】
G:Lビットの位数q(qは素数)の巡回群。
【0089】
:Lビットの位数qの巡回群。
【0090】
g:巡回群Gの生成元。
【0091】
:巡回群Gの生成元。g(mは整数)によって巡回群Gのすべての元を表現できる。g=e(g,g)。
【0092】
e:e(α,β)→γ(α,β∈G,γ∈G)。巡回群Gの2つの元を巡回群Gの1つの元に写像する双線形関数。双線形関数eは、以下の性質を満たす。
【0093】
[双線形性]すべてのα,β∈G及びν,κ∈Zqについて以下の関係を満たす。
【0094】
e(ανκ)=e(α,β)ν・κ …(27)
[非退化性]すべてのα,β∈Gを巡回群Gの単位元に写す関数ではない。
【0095】
[計算可能性]あらゆるα,β∈Gについてe(α,β)を効率的に計算するアルゴリズムが存在する。
【0096】
なお、双線形関数eの具体例は、WeilペアリングやTateペアリングなどのペアリング演算を行うための関数である(例えば、「Alfred. J. Menezes,ELLIPTIC CURVE PUBLIC KEY CRYPTOSYSTEMS, KLUWER ACADEMIC PUBLISHERS, ISBN0-7923-9368-6,pp. 61-81」等参照)。
【0097】
F:G→[0,q1/2]。巡回群Gの元を0以上q1/2以下の整数に写すハッシュ関数。
【0098】
H:{0,1}→{0,1}。任意長のビット列をLビットのビット列に写すハッシュ関数。
【0099】
ID(prot):鍵交換方式の名称の識別子。
【0100】
<事前処理>
鍵共有処理の事前処理として以下の処理が実行される。
【0101】
鍵共有装置210−1の記憶部211−1に、鍵共有装置210−1の秘密値(秘密鍵)a(1)∈Zと、鍵共有装置210−1に対応する巡回群Gの元である公開値(公開鍵)A(1)=ga(1)∈Gと、鍵共有装置210−2に対応する巡回群Gの元である公開値(公開鍵)A(2)=ga(2)∈Gと、鍵共有装置210−3に対応する巡回群Gの元である公開値(公開鍵)A(3)=ga(3)∈Gと、鍵共有装置210−1の識別子ID(1)と、識別子ID(prot)とが格納される。鍵共有装置210−2の記憶部211−2に、鍵共有装置210−2の秘密値(秘密鍵)a(2)∈Zと、鍵共有装置210−1に対応する巡回群Gの元である公開値(公開鍵)A(1)=ga(1)∈Gと、鍵共有装置210−2に対応する巡回群Gの元である公開値(公開鍵)A(2)=ga(2)∈Gと、鍵共有装置210−3に対応する巡回群Gの元である公開値(公開鍵)A(3)=ga(3)∈Gと、鍵共有装置210−2の識別子ID(2)と、識別子ID(prot)とが格納される。鍵共有装置210−3の記憶部211−3に、鍵共有装置210−3の秘密値(秘密鍵)a(3)∈Zと、鍵共有装置210−1に対応する巡回群Gの元である公開値(公開鍵)A(1)=ga(1)∈Gと、鍵共有装置210−2に対応する巡回群Gの元である公開値(公開鍵)A(2)=ga(2)∈Gと、鍵共有装置210−3に対応する巡回群Gの元である公開値(公開鍵)A(3)=ga(3)∈Gと、鍵共有装置210−2の識別子ID(2)と、識別子ID(prot)とが格納される。
【0102】
<鍵共有処理>
図10(A)は、鍵共有装置210−1の鍵共有処理を説明するためのフローチャートであり、図10(B)は、鍵共有装置210−2の鍵共有処理を説明するためのフローチャートである。また、図11は、鍵共有装置210−3の鍵共有処理を説明するためのフローチャートである。
【0103】
まず、鍵共有装置210−1(図6)は、第1実施形態のステップS112−1,S113−1の処理を実行する。これによって得られた任意元X(1)=gr(1)∈Gと、記憶部111−1から読み出された識別子ID(1)とが出力部214−1に入力され、出力部214−1は、任意元X(1)=gr(1)∈Gと識別子ID(1)とを出力(ネットワークへの送信や可搬型記録媒体への格納など)する(図10(A)/ステップS214−1)。任意元X(1)=gr(1)∈Gと識別子ID(1)とは、鍵共有装置210−2,210−3に送られる。
【0104】
また、鍵共有装置210−2(図6)は、第1実施形態のステップS112−2,S113−2の処理を実行する。これによって得られた任意元X(2)=gr(2)∈Gと、記憶部111−2から読み出された識別子ID(2)とが出力部214−2に入力され、出力部214−2は、任意元X(2)=gr(2)∈Gと識別子ID(2)とを出力(ネットワークへの送信や可搬型記録媒体への格納など)する(図10(B)/ステップS214−2)。任意元X(2)=gr(2)∈Gと識別子ID(2)とは、鍵共有装置210−1,210−3に送られる。
【0105】
鍵共有装置210−3(図7)の任意値生成部212−2は、任意値r(3)∈Zを生成して出力する(図11/ステップS212−3)。なお、任意値r(3)∈Zは、例えば、公知の擬似乱数生成アルゴリズムを用いて生成された擬似乱数や、予め定められた順序でZから選択された値である。任意元生成部213−3には、任意値r(3)∈Zが入力され、任意元生成部213−3は、任意値r(3)を用い、任意元X(3)=gr(3)∈Gを生成して出力する(ステップS213−3)。任意元X(3)=gr(3)∈Gと記憶部211−3から読み出された識別子ID(3)とが出力部214−3に入力され、出力部214−3は、任意元X(3)=gr(3)∈Gと識別子ID(3)とを出力(ネットワークへの送信や可搬型記録媒体への格納など)する(ステップS214−3)。任意元X(3)=gr(3)∈Gと識別子ID(3)とは、鍵共有装置210−1,210−2に送られる。
【0106】
鍵共有装置210−1(図6)の入力部215−1には、任意元X(2)=gr(2)∈Gと識別子ID(2)とが入力され(図10(A)/ステップS115−1)、任意元X(3)=gr(3)∈Gと識別子ID(3)とが入力される(ステップS215−1)。任意元X(2)=gr(2)∈Gと任意元X(3)=gr(3)∈Gは共有元生成部216−1に送られ、識別子ID(2),ID(3)は記憶部211−1に格納される。
【0107】
共有元生成部216−1には、入力部215−1から送られた任意元X(2)=gr(2)∈G,X(3)=gr(3)∈Gと、記憶部211−1から読み出された秘密値a(1)及び公開値A(2)=ga(2)∈G,A(3)=ga(3)∈Gと、任意値生成部112−1で生成(ステップS112−1)された任意値r(1)∈Zと、任意元生成部113−1で生成(ステップS113−1)された任意元X(1)=gr(1)∈Gが入力される。共有元生成部216−1は、これらと巡回群Gの元を巡回群Gの元に写像する前述の関数eを用い、巡回群Gの元gW(u)∈G(u∈{1,...,U}、Uは1以上の整数定数)を共有元σ(u)として生成して出力する(ステップS216−1)。本形態では、
W(u)=w(u,1)・w(u,2)・w(u,3)∈Zq …(28)
w(u,1)=(r(1)・s(u,1)+a(1)・t(u,1))∈Zq …(29)
w(u,2)=(r(2)・s(u,2)+a(2)・t(u,2))∈Zq …(30)
w(u,3)=(r(3)・s(u,3)+a(3)・t(u,3))∈Zq …(31)
を満たすgW(u)∈Gが、共有元σ(u)として生成される。s(u,1),s(u,2),s(u,3),t(u,1),t(u,2),t(u,3)∈Zはuごとに定まる定数又は変数である。s(u,1),s(u,2),s(u,3),t(u,1),t(u,2),t(u,3)∈Z及びUの設定は任意でよいが、すべてのuについて、s(u,1)とt(u,1)とや、s(u,2)とt(u,2)とや、s(u,3)とt(u,3)とが、必ず0となる設定は好ましくない。以下に、s(u,1),s(u,2),s(u,3),t(u,1),t(u,2),t(u,3)∈Z及びUの設定例と、そのときのステップS216−1の処理とを例示する。
【0108】
[ステップS216−1の例]
本形態では、
U=4 …(32)
s(1,1)=1, t(1,1)=d(1), s(1,2)=1, t(1,2)=1, s(1,3)=1, t(1,3)=1 …(33)
s(2,1)=1, t(2,1)=1, s(2,2)=1, t(2,2)=d(2), s(2,3)=1, t(2,3)=1 …(34)
s(3,1)=1, t(3,1)=1, s(3,2)=1, t(3,2)=1, s(3,3)=1, t(3,3)=d(3) …(35)
s(4,1)=1, t(4,1)=d(1), s(4,2)=1, t(4,2)=d(2), s(4,3)=1, t(4,3)=d(3) …(36)
としたステップS216−1の処理を例示する。すなわち、
σ(1)=g(r(1)+a(1)・d(1))(r(2)+a(2))(r(3)+a(3)) …(37)
σ(2)=g(r(1)+a(1))(r(2)+a(2)・d(2))(r(3)+a(3)) …(38)
σ(3)=g(r(1)+a(1))(r(2)+a(2))(r(3)+a(3)・d(3)) …(39)
σ(4)=g(r(1)+a(1)・d(1))(r(2)+a(2)・d(2))(r(3)+a(3)・d(3)) …(40)
とした場合の例を示す。
【0109】
この場合のステップS216−1では、ハッシュ演算部116b−1,116c−1(図8(A))が、第1実施形態と同様に、ハッシュ値
d(1)=F(X(1)) …(41)
d(2)=F(X(2)) …(42)
を生成して出力する。また、ハッシュ演算部216d−1が、任意元X(3)を入力として、ハッシュ値(第2任意元X(j)に応じて値が定まる整数)
d(3)=F(X(3)) …(43)
を生成して出力する。
【0110】
共有元演算部216a−1−1(図8(A))は、ハッシュ値d(1)と、任意元X(2)=gr(2)∈G,X(3)=gr(3)∈Gと、秘密値a(1)と、公開値A(2)=ga(2)∈G,A(3)=ga(3)∈Gと、任意値r(1)∈Zとを入力とし、共有元
σ(1)=e(X(2)・A(2),X(3)・A(3))r(1)+a(1)・d(1)∈G …(44)
=e(gr(2)・ga(2),gr(3)・ga(3))r(1)+a(1)・d(1)
=e(g,g)(r(1)+a(1)・d(1))(r(2)+a(2))(r(3)+a(3)) (式(27)より)
=gT(r(1)+a(1)・d(1))(r(2)+a(2))(r(3)+a(3)) (gT=e(g,g)より)
を生成して出力する。
【0111】
共有元演算部216a−2−1は、ハッシュ値d(2)と、任意元X(2)=gr(2)∈G,X(3)=gr(3)∈Gと、秘密値a(1)と、公開値A(2)=ga(2)∈G,A(3)=ga(3)∈Gと、任意値r(1)∈Zとを入力とし、共有元
σ(2)=e(X(2)・A(2)d(2),X(3)・A(3))r(1)+a(1)∈G …(45)
=e(gr(2)・ga(2)・d(2),gr(3)・ga(3))r(1)+a(1)
=e(g,g)(r(1)+a(1))(r(2)+a(2)・d(2))(r(3)+a(3)) (式(27)より)
=gT(r(1)+a(1))(r(2)+a(2)・d(2))(r(3)+a(3)) (gT=e(g,g)より)
を生成して出力する。
【0112】
共有元演算部216a−3−1は、ハッシュ値d(3)と、任意元X(2)=gr(2)∈G,X(3)=gr(3)∈Gと、秘密値a(1)と、公開値A(2)=ga(2)∈G,A(3)=ga(3)∈Gと、任意値r(1)∈Zとを入力とし、共有元
σ(3)=e(X(2)・A(2),X(3)・A(3)d(3))r(1)+a(1)∈G …(46)
=e(gr(2)・ga(2),gr(3)・ga(3)・d(3))r(1)+a(1)
=e(g,g)(r(1)+a(1))(r(2)+a(2))(r(3)+a(3)・d(3)) (式(27)より)
=gT(r(1)+a(1))(r(2)+a(2))(r(3)+a(3)・d(3)) (gT=e(g,g)より)
を生成して出力する。
【0113】
共有元演算部216a−4−1は、ハッシュ値d(1),d(2),d(3)と、任意元X(2)=gr(2)∈G,X(3)=gr(3)∈Gと、秘密値a(1)と、公開値A(2)=ga(2)∈G,A(3)=ga(3)∈Gと、任意値r(1)∈Zとを入力とし、共有元
σ(4)=e(X(2)・A(2)d(2),X(3)・A(3)d(3))r(1)+a(1)・d(1)∈G …(47)
=e(gr(2)・ga(2)・d(2),gr(3)・ga(3)・d(3))r(1)+a(1)・d(1)
=e(g,g)(r(1)+a(1)・d(1))(r(2)+a(2)・d(2))(r(3)+a(3)・d(3)) (式(27)より)
=gT(r(1)+a(1)・d(1))(r(2)+a(2)・d(2))(r(3)+a(3)・d(3)) (gT=e(g,g)より)
を生成して出力する([ステップS216−1の例]の説明終わり)。
【0114】
鍵生成部217−1(図6)は、少なくとも、共有元生成部216−1から出力された共有元σ(u)に基づいて値が定まる鍵Kを生成して出力する(ステップ図10(A)/S217−1)。本形態の例では、鍵生成部217−1に、共有元生成部216−1で生成された共有元σ(u)と、任意元生成部113−1で生成された任意元X(1)(ステップS113−1)と、入力部215−1に入力された任意元X(2),X(3)(ステップS115−1,S215−1)と、記憶部211−1から読み出した公開値A(1),A(2),A(3)、識別子ID(1),ID(2),ID(3),ID(prot)とが入力される。鍵生成部217−1は、これらのビット結合のハッシュ値を鍵
K=H(σ(1), σ(2), σ(3), σ(4), X(1), X(2), X(3), A(1), A(2), A(3), ID(1), ID(2), ID(3), ID(prot)) …(48)
として生成し、生成した鍵Kを出力する。
【0115】
鍵共有装置210−2(図6)の入力部215−2には、任意元X(1)=gr(1)∈Gと識別子ID(1)とが入力され(図10(B)/ステップS115−2)、任意元X(3)=gr(3)∈Gと識別子ID(3)とが入力される(ステップS215−2)。任意元X(1)=gr(2)∈Gと任意元X(3)=gr(3)∈Gは共有元生成部216−2に送られ、識別子ID(1),ID(3)は記憶部211−2に格納される。
【0116】
共有元生成部216−2には、入力部215−2から送られた任意元X(1)=gr(1)∈G,X(3)=gr(3)∈Gと、記憶部211−2から読み出された秘密値a(2)及び公開値A(1)=ga(2)∈G,A(3)=ga(3)∈Gと、任意値生成部112−2で生成(ステップS112−2)された任意値r(2)∈Zと任意元生成部113−1で生成(ステップS113−2)された任意元X(1)=gr(1)∈Gが入力される。共有元生成部216−2は、これらと巡回群Gの元を巡回群Gの元に写像する前述の関数eを用い、巡回群Gの元gW(u)∈G(u∈{1,...,U})を共有元σ(u)として生成して出力する(ステップS216−2)。本形態では、式(28)〜(31)を満たすgW(u)∈Gが、共有元σ(u)として生成される。以下に、s(u,1),s(u,2),s(u,3),t(u,1),t(u,2),t(u,3)∈Z及びUの設定例と、そのときのステップS216−2の処理とを例示する。
【0117】
[ステップS216−2の例]
本形態では、前述の式(32)〜(40)を満たす共有元σ(u)を生成する。
【0118】
この場合のステップS216−2では、ハッシュ演算部116b−2,116c−2,216d−2(図8(B))が、ハッシュ演算部116b−1,116c−1,216d−1と同様に、ハッシュ値
d(1)=F(X(1)) …(49)
d(2)=F(X(2)) …(50)
d(3)=F(X(3)) …(51)
を生成して出力する。
【0119】
共有元演算部216a−1−1(図8(B))は、ハッシュ値d(1)と、任意元X(1)=gr(2)∈G,X(3)=gr(3)∈Gと、秘密値a(2)と、公開値A(1)=ga(1)∈G,A(3)=ga(3)∈Gと、任意値r(2)∈Zとを入力とし、共有元
σ(1)=e(X(3)・A(3),X(1)・A(1)d(1))r(2)+a(2)∈G …(52)
=e(gr(3)・ga(3),gr(1)・ga(1)・d(1))r(2)+a(2)
=gT(r(1)+a(1)・d(1))(r(2)+a(2))(r(3)+a(3))
を生成して出力する。
【0120】
共有元演算部216a−2−2は、ハッシュ値d(2)と、任意元X(1)=gr(2)∈G,X(3)=gr(3)∈Gと、秘密値a(2)と、公開値A(1)=ga(1)∈G,A(3)=ga(3)∈Gと、任意値r(2)∈Zとを入力とし、共有元
σ(2)=e(X(3)・A(3),X(1)・A(1))r(2)+a(2)・d(2)∈G …(53)
=e(gr(3)・ga(3),gr(1)・ga(1))r(2)+a(2)・d(2)
=gT(r(1)+a(1))(r(2)+a(2)・d(2))(r(3)+a(3))
を生成して出力する。
【0121】
共有元演算部216a−3−2は、ハッシュ値d(3)と、任意元X(1)=gr(2)∈G,X(3)=gr(3)∈Gと、秘密値a(2)と、公開値A(1)=ga(1)∈G,A(3)=ga(3)∈Gと、任意値r(2)∈Zとを入力とし、共有元
σ(3)=e(X(3)・A(3)d(3),X(1)・A(1))r(2)+a(2)∈G …(54)
=e(gr(3)・ga(3)・d(3),gr(1)・ga(1))r(2)+a(2)
=gT(r(1)+a(1))(r(2)+a(2))(r(3)+a(3)・d(3))
を生成して出力する。
【0122】
共有元演算部216a−4−2は、ハッシュ値d(1),d(2),d(3)と、任意元X(1)=gr(2)∈G,X(3)=gr(3)∈Gと、秘密値a(2)と、公開値A(1)=ga(1)∈G,A(3)=ga(3)∈Gと、任意値r(2)∈Zとを入力とし、共有元
σ(4)=e(X(3)・A(3)d(3),X(1)・A(1)d(1))r(2)+a(2)・d(2)∈G …(55)
=e(gr(3)・ga(3)・d(3),gr(1)・ga(1)・d(1))r(2)+a(2)・d(2)
=gT(r(1)+a(1)・d(1))(r(2)+a(2)・d(2))(r(3)+a(3)・d(3))
を生成して出力する([ステップS216−2の例]の説明終わり)。
【0123】
鍵生成部217−2(図6)は、少なくとも、共有元生成部216−2から出力された共有元σ(u)に基づいて値が定まる鍵Kを生成して出力する(ステップ図10(B)/S217−2)。本形態の例では、鍵生成部217−2に、共有元生成部216−2で生成された共有元σ(u)と、任意元生成部113−2で生成された任意元X(2)(ステップS113−2)と、入力部215−2に入力された任意元X(1),X(3)(ステップS115−2,S215−2)と、記憶部211−2から読み出した公開値A(1),A(2),A(3)、識別子ID(1),ID(2),ID(3),ID(prot)とが入力される。鍵生成部217−2は、これらのビット結合のハッシュ値を鍵
K=H(σ(1), σ(2), σ(3), σ(4), X(1), X(2), X(3), A(1), A(2), A(3), ID(1), ID(2), ID(3), ID(prot)) …(56)
として生成し、生成した鍵Kを出力する。
【0124】
鍵共有装置210−2(図7)の入力部215−3には、任意元X(1)=gr(1)∈Gと識別子ID(1)とが入力され(図11/ステップS215a−3)、任意元X(2)=gr(2)∈Gと識別子ID(2)とが入力される(ステップS215b−3)。任意元X(1)=gr(2)∈Gと任意元X(2)=gr(2)∈Gは共有元生成部216−3に送られ、識別子ID(1),ID(2)は記憶部211−3に格納される。
【0125】
共有元生成部216−3には、入力部215−3から送られた任意元X(1)=gr(1)∈G,X(2)=gr(2)∈Gと、記憶部211−3から読み出された秘密値a(3)及び公開値A(1)=ga(2)∈G,A(2)=ga(2)∈Gと、任意値生成部212−3で生成(ステップS212−3)された任意値r(3)∈Zと、任意元生成部213−3で生成(ステップS213−3)された任意元X(3)=gr(3)∈Gが入力される。共有元生成部216−3は、これらと巡回群Gの元を巡回群Gの元に写像する前述の関数eを用い、巡回群Gの元gW(u)∈G(u∈{1,...,U})を共有元σ(u)として生成して出力する(ステップS216−3)。本形態では、式(28)〜(31)を満たすgW(u)∈Gが、共有元σ(u)として生成される。以下に、s(u,1),s(u,2),s(u,3),t(u,1),t(u,2),t(u,3)∈Z及びUの設定例と、そのときのステップS216−3の処理とを例示する。
【0126】
[ステップS216−3の例]
本形態では、前述の式(32)〜(40)を満たす共有元σ(u)を生成する。
【0127】
この場合のステップS216−3では、ハッシュ演算部216b−3,216c−3,216d−3(図9)が、ハッシュ演算部116b−1,116c−1,216d−1と同様に、ハッシュ値
d(1)=F(X(1)) …(57)
d(2)=F(X(2)) …(58)
d(3)=F(X(3)) …(59)
を生成して出力する。
【0128】
共有元演算部216a−1−3(図9)は、ハッシュ値d(1)と、任意元X(1)=gr(2)∈G,X(2)=gr(2)∈Gと、秘密値a(3)と、公開値A(1)=ga(1)∈G,A(2)=ga(2)∈Gと、任意値r(3)∈Zとを入力とし、共有元
σ(1)=e(X(1)・A(1)d(1),X(2)・A(2))r(3)+a(3)∈G …(60)
=e(gr(1)・ga(1)・d(1),gr(2)・ga(2))r(3)+a(3)
=gT(r(1)+a(1)・d(1))(r(2)+a(2))(r(3)+a(3))
を生成して出力する。
【0129】
共有元演算部216a−2−3は、ハッシュ値d(2)と、任意元X(1)=gr(2)∈G,X(2)=gr(2)∈Gと、秘密値a(3)と、公開値A(1)=ga(1)∈G,A(2)=ga(2)∈Gと、任意値r(3)∈Zとを入力とし、共有元
σ(2)=e(X(1)・A(1),X(2)・A(2)d(2))r(3)+a(3)∈G …(61)
=e(gr(1)・ga(1),gr(2)・ga(2)・d(2))r(3)+a(3)
=gT(r(1)+a(1))(r(2)+a(2)・d(2))(r(3)+a(3))
を生成して出力する。
【0130】
共有元演算部216a−3−3は、ハッシュ値d(3)と、任意元X(1)=gr(2)∈G,X(2)=gr(2)∈Gと、秘密値a(3)と、公開値A(1)=ga(1)∈G,A(2)=ga(2)∈Gと、任意値r(3)∈Zとを入力とし、共有元
σ(3)=e(X(1)・A(1),X(2)・A(2))r(3)+a(3)・d(3)∈G …(62)
=e(gr(1)・ga(1),gr(2)・ga(2))r(3)+a(3)・d(3)
=gT(r(1)+a(1))(r(2)+a(2))(r(3)+a(3)・d(3))
を生成して出力する。
【0131】
共有元演算部216a−4−3は、ハッシュ値d(1),d(2),d(3)と、任意元X(1)=gr(2)∈G,X(2)=gr(2)∈Gと、秘密値a(3)と、公開値A(1)=ga(1)∈G,A(2)=ga(2)∈Gと、任意値r(3)∈Zとを入力とし、共有元
σ(4)=e(X(1)・A(1)d(1),X(2)・A(2)d(2))r(3)+a(3)・d(3)∈G …(63)
=e(gr(1)・ga(1)・d(1),gr(2)・ga(2)・d(2))r(3)+a(3)・d(3)
=gT(r(1)+a(1)・d(1))(r(2)+a(2)・d(2))(r(3)+a(3)・d(3))
を生成して出力する([ステップS216−3の例]の説明終わり)。
【0132】
鍵生成部217−3(図7)は、少なくとも、共有元生成部216−3から出力された共有元σ(u)に基づいて値が定まる鍵Kを生成して出力する(ステップ図11/S217−3)。
【0133】
本形態の例では、鍵生成部217−3に、共有元生成部216−3で生成された共有元σ(u)と、任意元生成部213−3で生成された任意元X(3)(ステップS213−3)と、入力部215−3に入力された任意元X(1),X(2)(ステップS215a−3,S215b−3)と、記憶部211−3から読み出した公開値A(1),A(2),A(3)、識別子ID(1),ID(2),ID(3),ID(prot)とが入力される。鍵生成部217−3は、これらのビット結合のハッシュ値を鍵
K=H(σ(1), σ(2), σ(3), σ(4), X(1), X(2), X(3), A(1), A(2), A(3), ID(1), ID(2), ID(3), ID(prot)) …(64)
として生成し、生成した鍵Kを出力する。
【0134】
<本形態の特徴>
式(44)〜(47)(52)〜(55)(60)〜(63)の変形結果を見ればわかるように、鍵共有装置216−1,2,3でそれぞれ生成される共有元σ(1)は同一となり、鍵共有装置216−1,2,3でそれぞれ生成される共有元σ(2)は同一となり、鍵共有装置216−1,2,3でそれぞれ生成される共有元σ(3)は同一となり、鍵共有装置216−1,2,3でそれぞれ生成される共有元σ(4)は同一となる。そして、式(48)(56)(64)を比べれば分かるように、鍵共有装置216−1,2,3でそれぞれ生成される鍵Kは同一となる。
【0135】
ここで、鍵共有装置216−1が、それぞれ式(44)〜(47)の共有元σ(1),σ(2),σ(3),σ(4)を計算できるのは、鍵共有装置216−1が自らの秘密値a(1)と任意値r(1)とを知っているからである。鍵共有装置216−2の秘密値a(2)を知っている攻撃者は、鍵共有装置216−1に成り済まして任意値r(1)や任意元X(1)を生成することはできても、秘密値a(1)を知らないため、式(44)〜(47)の共有元σ(1),σ(2),σ(3),σ(4)を計算できない。同様なことは、鍵共有装置216−2,3についてもいえる。よって、本形態の方式に対して攻撃者がKCI攻撃を行うことは困難である。
【0136】
また、本形態では、任意元X(1),X(2),X(3)に応じて値が定まる整数d(1),d(2),d(3)を生成し、これらを用いて共有元σ(1),σ(2),σ(3),σ(4)を生成した。そのため、本形態では、高い安全性を確保できる。
【0137】
また、本形態では、複数の共有元σ(1),σ(2),σ(3),σ(4)を生成することとしたため、高い安全性を確保できる。
【0138】
〔第2実施形態の変形例1〕
第2実施形態の変形例1は、ステップS216−1,2,3の共有元σ(u)の生成処理の変形例である。第2実施形態の変形例1では、式(33)〜(40)の代わりに、
s(1,1)=1, t(1,1)=1, s(1,2)=1, t(1,2)=d(2), s(1,3)=1, t(1,3)=d(3) …(64')
s(2,1)=1, t(2,1)=d(1), s(2,2)=1, t(2,2)=1, s(2,3)=1, t(2,3)=d(3) …(65)
s(3,1)=1, t(3,1)=d(1), s(3,2)=1, t(3,2)=d(2), s(3,3)=1, t(3,3)=1 …(66)
s(4,1)=1, t(4,1)=1, s(4,2)=1, t(4,2)=1, s(4,3)=1, t(4,3)=1 …(67)
、すなわち、
σ(1)=gT(r(1)+a(1))(r(2)+a(2)・d(2))(r(3)+a(3)・d(3)) …(68)
σ(2)=gT(r(1)+a(1)・d(1))(r(2)+a(2))(r(3)+a(3)・d(3)) …(69)
σ(3)=gT(r(1)+a(1)・d(1))(r(2)+a(2)・d(2))(r(3)+a(3)) …(70)
σ(4)=gT(r(1)+a(1))(r(2)+a(2))(r(3)+a(3)) …(71)
を満たす共有元σ(u)を生成する。
【0139】
この場合、共有元演算部216a−1−1〜216a−4−1(図8(A))は、式(44)〜(47)の代わりに、共有元
σ(1)=e(X(2)・A(2)d(2),X(3)・A(3)d(3))r(1)+a(1)∈G …(72)
=gT(r(1)+a(1))(r(2)+a(2)・d(2))(r(3)+a(3)・d(3))
σ(2)=e(X(2)・A(2),X(3)・A(3)d(3))r(1)+a(1)・d(1)∈G …(73)
=gT(r(1)+a(1)・d(1))(r(2)+a(2))(r(3)+a(3)・d(3))
σ(3)=e(X(2)・A(2)d(2),X(3)・A(3))r(1)+a(1)・d(1)∈G …(74)
=gT(r(1)+a(1)・d(1))(r(2)+a(2)・d(2))(r(3)+a(3))
σ(4)=e(X(2)・A(2),X(3)・A(3))r(1)+a(1)∈G …(75)
=gT(r(1)+a(1))(r(2)+a(2))(r(3)+a(3))
を生成して出力する。
【0140】
また、共有元演算部216a−1−2〜216a−4−2(図8(B))が、式(52)〜(55)の代わりに、共有元
σ(1)=e(X(3)・A(3)d(3),X(1)・A(1))r(2)+a(2)・d(2)∈G …(76)
=gT(r(1)+a(1))(r(2)+a(2)・d(2))(r(3)+a(3)・d(3))
σ(2)=eT(X(3)・A(3)d(3),X(1)・A(1)d(1))r(2)+a(2)∈G …(77)
=gT(r(1)+a(1)・d(1))(r(2)+a(2))(r(3)+a(3)・d(3))
σ(3)=e(X(3)・A(3),X(1)・A(1)・d(1))r(2)+a(2)・d(2)∈G …(78)
=gT(r(1)+a(1)・d(1))(r(2)+a(2)・d(2))(r(3)+a(3))
σ(4)=e(X(3)・A(3),X(1)・A(1))r(2)+a(2)∈G …(79)
=gT(r(1)+a(1))(r(2)+a(2))(r(3)+a(3))
を生成して出力する。
【0141】
また、共有元演算部216a−1−3〜216a−4−3(図9)が、式(60)〜(63)の代わりに、共有元
σ(1)=e(X(1)・A(1),X(2)・A(2)d(2))r(3)+a(3)・d(3)∈G …(80)
=gT(r(1)+a(1))(r(2)+a(2)・d(2))(r(3)+a(3)・d(3))
σ(2)=e(X(1)・A(1)d(1),X(2)・A(2))r(3)+a(3)・d(3)∈G …(81)
=gT(r(1)+a(1)・d(1))(r(2)+a(2))(r(3)+a(3)・d(3))
σ(3)=e(X(1)・A(1)・d(1),X(2)・A(2)d(2))r(3)+a(3)∈G …(82)
=gT(r(1)+a(1)・d(1))(r(2)+a(2)・d(2))(r(3)+a(3))
σ(4)=e(X(1)・A(1),X(2)・A(2))r(3)+a(3)∈G …(83)
=gT(r(1)+a(1))(r(2)+a(2))(r(3)+a(3))
を生成して出力する。
【0142】
また、例えば、U=1として、式(33)〜(40)の代わりに、
σ(1)=gT(r(1)+a(1)・d(1))(r(2)+a(2)・d(2))(r(3)+a(3)・d(3))
としてもよい。その他、U=2,3やU≧5の構成、ハッシュ値d(1)〜d(3)の一部のみを用いて共有元σ(u)を生成する構成、複数の任意元X(1),X(2),X(3)に依存するハッシュ値を用いて共有元σ(u)を生成する構成、ハッシュ値d(1)〜d(3)を用いずに共有元σ(u)を生成する構成なども可能である。また、d(p)は、ハッシュ値に限定されず、任意元X(1)及び/又は任意元X(2)及び/又は任意元X(3)に応じて値が定まる整数であればよい。例えば、任意元X(1)や任意元X(2)や任意元X(3)の一部のビットをd(p)としてもよいし、これらの任意元の一部をビット結合したビット列の一部をd(p)としてもよい。また、
r(i)=F’(r’(i),a(i))
としてもよい。なお、F’は、ハッシュ関数F’:{0,1}*→Zであり、r’(i)は乱数である。r(j)についても同様な変形を行ってもよい。これによってU=1の場合でも高い安全性を確保できる。その他、本発明の趣旨を遺脱しない範囲で共有元σ(u)の生成方法を変形可能である。
【0143】
〔第2実施形態の変形例2〕
第1実施形態の変形例2と同様、第2実施形態でも、鍵Kは共有元σ(u)に基づいて値が定まればよく、第1実施形態の変形例2で述べたように鍵Kの生成方法を変形してもよい。
【0144】
〔第3実施形態〕
次に、本発明の第3実施形態を説明する。第3実施形態では、IDベース暗号方式を応用した形態であり、P=2であり、W(u)=w(u,1)・w(u,2)・MSKであり、w(u,p)はa(p)とr(p)との線形和である。第1鍵共有装置の記憶部が、少なくとも、元Z(i)=ga(i)・MSK∈Gと、公開値A(j)=ga(j)∈Gと、巡回群Gの元MPK=gMSK∈Gとを格納し、第1鍵共有装置の共有元生成部が、少なくとも、元Z(i)=ga(i)・MSK∈Gと、公開値A(j)=ga(j)∈Gと、任意値r(i)と、任意元X(j)=gr(j)∈Gと、MPK=gMSK∈Gと、巡回群Gの2つの元を巡回群Gの1つの元に写像する双線形関数である関数eとを用い、巡回群Gの元gW(u)=e(g,g)W(u)∈Gを共有元σ(u)として生成する。また、第2鍵共有装置の記憶部が、少なくとも、元Z(j)=ga(j)・MSK∈Gと、公開値A(i)=ga(i)∈Gと、巡回群Gの元MPK=gMSK∈Gとを格納し、第2鍵共有装置の共有元生成部が、少なくとも、元Z(j)=ga(j)・MSK∈Gと、公開値A(i)=ga(i)∈Gと、任意値r(j)と、任意元X(i)=gr(i)∈Gと、MPK=gMSK∈Gと、巡回群Gの2つの元を巡回群Gの1つの元に写像する双線形関数である関数eとを用い、巡回群Gの元gW(u)=e(g,g)W(u)∈Gを共有元σ(u)として生成する。
【0145】
<構成>
図12,13は、第3実施形態の鍵共有システム300の構成を説明するためのブロック図である。なお、第1実施形態と共通する部分については、第1実施形態と同じ符号を用いて説明を簡略化する。
【0146】
図12に例示するように、第3実施形態の鍵共有システム300は、鍵共有装置310−1(第1鍵共有装置)と鍵共有装置310−2(第2鍵共有装置)とを有する。鍵共有装置310−1及び鍵共有装置310−2は、鍵生成装置330との情報のやり取りが可能に構成される。なお、この情報のやり取りは、ネットワーク経由で行われるものに限定されず、例えば、USBメモリなどの可搬型の記録媒体への情報の読み書きによって行われてもよい。
【0147】
図13に例示するように、鍵共有装置310−1は、記憶部111−1と、任意値生成部112−1と、任意元生成部113−1と、出力部114−1と、入力部115−1と、共有元生成部316−1と、鍵生成部317−1と、一時メモリ118−1と、制御部119−1とを有する。図14(A)は、共有元生成部316−1の構成を説明するためのブロック図である。図14(A)に例示するように、共有元生成部316−1は、ハッシュ演算部116b−1,116c−1と、共有元演算部316a−u−1(u∈{1,...,U}),316b−1とを有する。
【0148】
図13に例示するように、鍵共有装置310−2は、記憶部111−2と、任意値生成部112−2と、任意元生成部113−2と、出力部114−2と、入力部115−2と、共有元生成部316−2と、鍵生成部317−2と、一時メモリ118−2と、制御部119−2とを有する。図14(B)は、共有元生成部316−2の構成を説明するためのブロック図である。図14(B)に例示するように、共有元生成部316−2は、ハッシュ演算部116b−2,116c−2と、共有元演算部316a−u−2(u∈{1,...,U}),316b−2とを有する。
【0149】
なお、第1実施形態と同様、鍵共有装置310−1,2は、例えば、公知のコンピュータに所定のプログラムが読み込まれて実行されることで構成される。また、鍵共有装置310−1,2は、それぞれ、制御部119−1,2の制御のもと各処理を実行する。また、以下では説明を簡略化するが、各処理部から出力されたデータは、逐一、一時メモリ118−1,2又は記憶部111−1,2に格納される。一時メモリ118−1,2又は記憶部111−1,2に格納されたデータは、必要に応じて読み出され、各処理部に入力されてその処理に利用される。
【0150】
<公開パラメータ>
第3実施形態では、以下を公開パラメータとする。
【0151】
G:Lビットの位数q(qは素数)の巡回群。
【0152】
:Lビットの位数qの巡回群。
【0153】
g:巡回群Gの生成元。
【0154】
:巡回群Gの生成元。
【0155】
e:e(α,β)→γ(α,β∈G,γ∈G)。巡回群Gの2つの元を巡回群Gの1つの元に写像する双線形関数。
【0156】
F:G→[0,q1/2]。巡回群Gの元を0以上q1/2以下の整数に写すハッシュ関数。
【0157】
H:{0,1}→{0,1}。任意長のビット列をLビットのビット列に写すハッシュ関数。
【0158】
Y:{0,1}→G。任意長のビット列を巡回群Gに写すハッシュ関数。
【0159】
ID(prot):鍵交換方式の名称の識別子。
【0160】
MPK:IDベース暗号方式のマスタ公開鍵。なお、MPK=gMSK∈G(MSK∈ZはIDベース暗号方式のマスタ秘密鍵)を満たす。
【0161】
<事前処理>
鍵生成装置330の記憶部にはマスタ秘密鍵MSK∈Zが安全に格納されている。鍵生成装置330は、鍵共有装置310−1の識別子ID(1)を用い、鍵共有装置310−1の秘密鍵
Z(1)=Y(ID(1))MSK∈G …(84)
を生成する。ここで、
A(1)=Y(ID(1))=ga(1)∈G …(85)
とおくと、式(84)は、
Z(1)=ga(1)・MSK∈G …(86)
となる。秘密鍵Z(1)は、鍵共有装置310−1に送られ、その記憶部311−1に安全に格納される。
【0162】
また、鍵生成装置330は、鍵共有装置310−2の識別子ID(2)を用い、鍵共有装置310−2の秘密鍵
Z(2)=Y(ID(2))MSK∈G …(87)
を生成する。ここで、
A(2)=Y(ID(2))=ga(2)∈G …(88)
とおくと、式(87)は、
Z(2)=ga(2)・MSK∈G …(89)
となる。秘密鍵Z(2)は、鍵共有装置310−2に送られ、その記憶部311−2に安全に格納される。
【0163】
また、鍵共有装置210−1の記憶部211−1に、マスタ公開鍵MPK=gMSK∈Gと、鍵共有装置210−1に対応する巡回群Gの元である公開値A(1)=Y(ID(1))=ga(1)∈Gと、鍵共有装置210−2に対応する巡回群Gの元である公開値A(2)=Y(ID(2))=ga(2)∈Gと、鍵共有装置210−1の識別子ID(1)と、識別子ID(prot)とが格納される。鍵共有装置210−2の記憶部211−2に、マスタ公開鍵MPK=gMSK∈Gと、鍵共有装置210−1に対応する巡回群Gの元である公開値A(1)=Y(ID(1))=ga(1)∈Gと、鍵共有装置210−2に対応する巡回群Gの元である公開値A(2)=Y(ID(2))=ga(2)∈Gと、鍵共有装置210−2の識別子ID(2)と、識別子ID(prot)とが格納される。
【0164】
<鍵共有処理>
図15(A)は、鍵共有装置310−1の鍵共有処理を説明するためのフローチャートであり、図15(B)は、鍵共有装置310−2の鍵共有処理を説明するためのフローチャートである。
【0165】
図15(A)に示すように、鍵共有装置310−1(図13)は、第1実施形態のステップS112−1〜S115−1の処理を実行する。
【0166】
共有装置310−1の共有元生成部316−1には、入力部115−1に入力された任意元X(2)=gr(2)∈Gと、記憶部211−1から読み出された秘密鍵Z(1)=ga(1)・MSK∈G、マスタ公開鍵MPK=gMSK∈G及び公開値A(2)=ga(2)∈Gと、任意値生成部112−1で生成(ステップS112−1)された任意値r(1)∈Zとが入力される。共有元生成部316−1は、これらと巡回群Gの元を巡回群Gの元に写像する前述の関数eを用い、巡回群Gの元gW(u)∈G(u∈{1,...,U}、Uは1以上の整数定数)を共有元σ(u)として生成して出力する(ステップS316a−1)。本形態では
W(u)=w(u,1)・w(u,2)・MSK∈Zq …(90)
w(u,1)=(r(1)・s(u,1)+a(1)・t(u,1))∈Zq …(91)
w(u,2)=(r(2)・s(u,2)+a(2)・t(u,2))∈Zq …(92)
を満たすgW(u)∈Gが、共有元σ(u)として生成される。s(u,1),s(u,2),t(u,1),t(u,2)∈Zはuごとに定まる定数又は変数であり、第1実施形態と同様に設定すればよい。
【0167】
以下に、s(u,1),s(u,2),t(u,1),t(u,2)∈Z及びUの設定例と、そのときのステップS316a−1の処理とを例示する。
【0168】
[ステップS316a−1の例]
本形態では、まず、第1実施形態の式(6)〜(10)を満たす共有元σ(u)を生成する。この場合、まず、第1実施形態と同様に、ハッシュ演算部116b−1,116c−1(図14(A))が、式(11)(12)のハッシュ値d(1),d(2)を生成して出力する。
【0169】
共有元演算部316a−1−1(図14(A))は、ハッシュ値d(2)と、任意元X(2)=gr(2)∈Gと、秘密鍵Z(1)=ga(1)・MSK∈G、マスタ公開鍵MPK=gMSK∈Gと、公開値A(2)=ga(2)∈Gと、任意値r(1)∈Zとを入力とし、共有元
σ(1)=e(MPKr(1)・Z(1),X(2)・A(2)d(2))∈GT …(93)
=e(gMSK・r(1)・ga(1)・MSK, gr(2)・ga(2)・d(2))(MPK=gMSK∈Gより)
=e(g,g)(r(1)+a(1))(r(2)+a(2)・d(2))MSK(式(27)より)
=gT(r(1)+a(1))(r(2)+a(2)・d(2))MSK (gT=e(g,g)より)
を生成して出力する。共有元演算部316a−2−1は、ハッシュ値d(1)と、任意元X(2)=gr(2)∈Gと、秘密鍵Z(1)=ga(1)・MSK∈G、マスタ公開鍵MPK=gMSK∈Gと、公開値A(2)=ga(2)∈Gと、任意値r(1)∈Zとを入力とし、共有元
σ(2)=e(MPKr(1)・Z(1)d(1), X(2)・A(2))∈GT …(94)
=e(gMSK・r(1)・ga(1)・MSK・d(1), gr(2)・ga(2))(MPK=gMSK∈Gより)
=e(g,g)(r(1)+a(1)・d(1))(r(2)+a(2))MSK(式(27)より)
=gT(r(1)+a(1)・d(1))(r(2)+a(2))MSK(gT=e(g,g)より)
を生成して出力する([ステップS316a−1の例]の説明終わり)。
【0170】
また、共有元生成部316−1の共有元演算部316b−1が、任意元X(2)=gr(2)∈Gと、任意値r(1)∈Zとを入力とし、共有元
σ(3)=X(2)r(1)∈G …(95)
=gr(2)・r(1)
を生成する(ステップS316b−1)。なお、本形態はU=2の例である。
【0171】
鍵生成部317−1(図13)は、少なくとも、共有元生成部316−1から出力された共有元σ(u)に基づいて値が定まる鍵Kを生成して出力する(ステップ図15(A)/S217−1)。本形態の例では、鍵生成部317−1に、共有元生成部316−1で生成された共有元σ(1), σ(2), σ(3)と、任意元生成部113−1で生成された任意元X(1)(ステップS113−1)と、入力部115−1に入力された任意元X(2)(ステップS115−1)と、記憶部311−1から読み出した公開値A(1),A(2)、識別子ID(1),ID(2),ID(prot)とが入力される。鍵生成部317−1は、これらのビット結合のハッシュ値を鍵
K=H(σ(1), σ(2), σ(3), X(1), X(2), A(1), A(2), ID(1), ID(2), ID(prot))…(96)
として生成し、生成した鍵Kを出力する。
【0172】
一方、図15(B)に示すように、鍵共有装置310−2は、第1実施形態のステップS112−2〜S115−2の処理を実行する。
【0173】
共有装置310−2の共有元生成部316−2には、入力部115−2に入力された任意元X(1)=gr(1)∈Gと、記憶部211−2から読み出された秘密鍵Z(2)=ga(2)・MSK∈G、マスタ公開鍵MPK=gMSK∈G及び公開値A(1)=ga(1)∈Gと、任意値生成部112−2で生成(ステップS112−2)された任意値r(2)∈Zとが入力される。共有元生成部316−2は、これらと巡回群Gの元を巡回群Gの元に写像する前述の関数eを用い、巡回群Gの元gW(u)∈G(u∈{1,...,U})を共有元σ(u)として生成して出力する(ステップS316a−2)。本形態では、式(90)〜(92)を満たすgW(u)∈Gが、共有元σ(u)として生成される。
【0174】
以下に、s(u,1),s(u,2),t(u,1),t(u,2)∈Z及びUの設定例と、そのときのステップS316−2の処理とを例示する。
【0175】
[ステップS316a−2の例]
本形態では、まず、第1実施形態の式(6)〜(10)を満たす共有元σ(u)を生成する。この場合、まず、第1実施形態と同様に、ハッシュ演算部116b−2,116c−2(図14(B))が、式(15)(16)のハッシュ値d(1),d(2)を生成して出力する。
【0176】
共有元演算部316a−1−2(図14(B))は、ハッシュ値d(2)と、任意元X(1)=gr(1)∈Gと、秘密鍵Z(2)=ga(2)・MSK∈G、マスタ公開鍵MPK=gMSK∈Gと、公開値A(1)=ga(1)∈Gと、任意値r(2)∈Zとを入力とし、共有元
σ(1)=e(X(1)・A(1),MPKr(2)・Z(2)d(2))∈GT …(97)
=e(gr(1)・ga(1),g MSK・r(2)・ga(2)・MSK・d(2))(MPK=gMSK∈Gより)
=e(g,g)(r(1)+a(1))(r(2)+a(2)・d(2))MSK(式(27)より)
=gT(r(1)+a(1))(r(2)+a(2)・d(2))MSK (gT=e(g,g)より)
を生成して出力する。共有元演算部316a−2−2は、ハッシュ値d(1)と、任意元X(1)=gr(1)∈Gと、秘密鍵Z(2)=ga(2)・MSK∈G、マスタ公開鍵MPK=gMSK∈Gと、公開値A(1)=ga(1)∈Gと、任意値r(2)∈Zとを入力とし、共有元
σ(2)=e(X(1)・A(1)d(1),MPKr(2)・Z(2))∈GT …(98)
=e(gr(1)・ga(1)・d(1),gMSK・r(2)・ga(2)・MSK)(MPK=gMSK∈Gより)
=e(g,g)(r(1)+a(1)・d(1))(r(2)+a(2))MSK(式(27)より)
=gT(r(1)+a(1)・d(1))(r(2)+a(2))MSK(gT=e(g,g)より)
を生成して出力する([ステップS316a−2の例]の説明終わり)。
【0177】
また、共有元生成部316−2の共有元演算部316b−2が、任意元X(1)=gr(1)∈Gと、任意値r(2)∈Zとを入力とし、共有元
σ(3)=X(1)r(2)∈G …(99)
=gr(1)・r(2)
を生成する(ステップS316b−2)。なお、本形態はU=2の例である。
【0178】
鍵生成部317−2(図13)は、少なくとも、共有元生成部316−2から出力された共有元σ(u)に基づいて値が定まる鍵Kを生成して出力する(ステップ図15(B)/S217−2)。本形態の例では、鍵生成部317−2に、共有元生成部316−2で生成された共有元σ(1), σ(2), σ(3)と、任意元生成部113−2で生成された任意元X(2)(ステップS113−2)と、入力部115−2に入力された任意元X(1)(ステップS115−2)と、記憶部311−2から読み出した公開値A(1),A(2)、識別子ID(1),ID(2),ID(prot)とが入力される。鍵生成部317−2は、これらのビット結合のハッシュ値を鍵
K=H(σ(1), σ(2), σ(3), X(1), X(2), A(1), A(2), ID(1), ID(2), ID(prot))…(100)
として生成し、生成した鍵Kを出力する。
【0179】
<本形態の特徴>
式(93)〜(95)(97)〜(99)の変形結果を見ればわかるように、鍵共有装置316−1,2でそれぞれ生成される共有元σ(1)は同一となり、鍵共有装置316−1,2でそれぞれ生成される共有元σ(2)は同一となり、鍵共有装置316−1,2でそれぞれ生成される共有元σ(3)は同一となる。そして、式(96)(100)を比べれば分かるように、鍵共有装置316−1,2でそれぞれ生成される鍵Kは同一となる。
【0180】
ここで、鍵共有装置316−1が、それぞれ式(93)(94)の共有元σ(1),σ(2)を計算できるのは、鍵共有装置316−1が自らの秘密鍵Z(1)と任意値r(1)とを知っているからである。鍵共有装置316−2の秘密鍵Z(2)を知っている攻撃者は、鍵共有装置316−1に成り済まして任意値r(1)や任意元X(1)を生成することはできても、秘密鍵Z(1)を知らないため、式(93)(94)の共有元σ(1),σ(2)を計算できない。同様なことは、鍵共有装置216−2についてもいえる。よって、本形態の方式に対して攻撃者がKCI攻撃を行うことは困難である。
【0181】
また、本形態では、任意元X(1),X(2)に応じて値が定まる整数d(1),d(2)を生成し、これらを用いて共有元σ(1),σ(2)を生成した。そのため、本形態では、高い安全性を確保できる。
【0182】
また、本形態では、複数の共有元σ(1),σ(2)を生成することとしたため、高い安全性を確保できる。
【0183】
〔第3実施形態の変形例1〕
第3実施形態の変形例1は、ステップS316a−1,2、S316b−1,2の共有元σ(u)の生成処理の変形例である。第3実施形態の変形例1では、式(7)〜(10)の代わりに、式(19')〜(22)を満たす共有元σ(u)を生成し、共有元σ(3)は生成しない。
【0184】
この場合、共有元演算部316a−1−1,316a−2−1(図14(A))が、式(93)(94)の代わりに、共有元
σ(1)=e(MPKr(1)・Z(1),X(2)・A(2))∈GT …(101)
=gT(r(1)+a(1))(r(2)+a(2))MSK
σ(2)=e(MPKr(1)・Z(1)d(1), X(2)・A(2)d(1))∈GT …(102)
=gT(r(1)+a(1)・d(1))(r(2)+a(2)・d(2))MSK
を生成して出力する。
【0185】
また、共有元演算部316a−1−2,316a−2−2(図14(B))が、式(98)(98)の代わりに、共有元
σ(1)=e(X(1)・A(1),MPKr(2)・Z(2))∈GT …(103)
=gT(r(1)+a(1))(r(2)+a(2))MSK
σ(2)=e(X(1)・A(1)d(1),MPKr(2)・Z(2)d(2))∈GT …(104)
=gT(r(1)+a(1)・d(1))(r(2)+a(2)・d(2))MSK
を生成して出力する。また、この変形例では、共有元σ(3)は生成されない。その他は第3実施形態と同様である。
【0186】
その他、例えば、U=1として共有元
σ(1)=gT(r(1)+a(1)・d(1))(r(2)+a(2)・d(2))MSK
を生成してもよい。また、例えば、第1実施形態の変形例1で説明したようなs(1,1),t(1,1),s(1,2),t(1,2),s(2,1),t(2,1),s(2,2),t(2,2)やUやd(p)に関する変形を行ってもよい。また、
r(i)=F’(r’(i),a(i))
としてもよい。なお、F’は、ハッシュ関数F’:{0,1}*→Zであり、r’(i)は乱数である。r(j)についても同様な変形を行ってもよい。これによってU=1の場合でも高い安全性を確保できる。その他、本発明の趣旨を遺脱しない範囲で共有元σ(u)の生成方法を変形可能である。
【0187】
〔第3実施形態の変形例2〕
第1実施形態の変形例2と同様、第3実施形態でも、鍵Kは共有元σ(u)に基づいて値が定まればよく、第1実施形態の変形例2で述べたように鍵Kの生成方法を変形してもよい。
【0188】
〔その他の変形例等〕
なお、本発明は上述の実施の形態に限定されるものではない。例えば、上述の各実施形態では、位数qを素数としたが、位数qが素数でなく合成数であってもよい。また、上述の各実施形態では、任意値r(i),r(j)等を法qについての整数の剰余環Zの元としたが、各実施形態で法qについての整数の剰余環Zの元として扱った各値が整数集合の元であってもよい。
【0189】
また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【0190】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【0191】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【0192】
また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD−ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【0193】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASP(Application Service Provider)型のサービスによって、上述の処理を実行する構成としてもよい。
【0194】
また、各形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【0195】
本発明の利用分野としては、例えば、共通鍵暗号における共通鍵の共有、共通鍵暗号を用いた認証処理における共通鍵の共有などがある。
【符号の説明】
【0196】
1,100〜300 鍵共有システム
10−10〜P,110−110〜P,210−210〜P,310−310〜P 鍵共有装置

【特許請求の範囲】
【請求項1】
他の装置と鍵を共有する鍵共有装置であって、
少なくとも、整数の秘密値a(i)又は巡回群Gの元Z(i)=ga(i)・MSK∈Gと、前記他の装置に対応する巡回群Gの元である公開値A(j)=ga(j)∈G〔i,j∈{1,...,P}、j≠i、Pは2以上の整数定数、gはgによって巡回群Gのすべての元を表現できる生成元、MSK,m及びa(j)は整数〕と、を格納する記憶部と、
整数の任意値r(i)を生成する任意値生成部と、
前記任意値r(i)を用い、第1任意元X(i)=gr(i)∈Gを生成する任意元生成部と、
前記第1任意元X(i)を出力する出力部と、
第2任意元X(j)=gr(j)∈G〔r(j)は整数〕が入力される入力部と、
少なくとも、前記秘密値a(i)又は前記元Z(i)=ga(i)・MSK∈Gと、前記公開値A(j)=ga(j)∈Gと、前記任意値r(i)と、前記第2任意元X(j)=gr(j)∈Gとを用い、巡回群Gの元gW(u)∈G〔W(u)は整数w(u,1),...,w(u,P)を含むP個以上の整数の積、前記整数w(u,p)はa(p)とr(p)とを含む複数の整数の線形和、p∈{1,...,P}、u∈{1,...,U}、Uは1以上の整数定数〕を共有元σ(u)として生成するか、又は、さらに巡回群Gの元を巡回群Gの元に写像する関数eを用い、巡回群Gの元gW(u)∈G〔gはgによって巡回群Gのすべての元を表現できる生成元〕を共有元σ(u)として生成する共有元生成部と、
少なくとも前記共有元σ(u)に基づいて値が定まる鍵Kを生成し、当該鍵Kを出力する鍵生成部と、
を有する鍵共有装置。
【請求項2】
請求項1の鍵共有装置であって、
少なくとも一部の前記整数w(u,p)は、少なくとも一方が整数d(p)によって重み付けされたa(p)とr(p)とを含む複数の整数の線形和であり、
前記整数d(p)は、前記第1任意元X(i)及び/又は前記第2任意元X(j)に応じて値が定まる整数である、
ことを特徴とする鍵共有装置。
【請求項3】
請求項1又は2の鍵共有装置であって、
U≧2であり、
前記共有元生成部は、複数種類の前記共有元σ(1),...σ(U)を生成する、
ことを特徴とする鍵共有装置。
【請求項4】
請求項1から3の何れかの鍵共有装置であって、
P=2であり、W(u)=w(u,1)・w(u,2)であり、w(u,p)はa(p)とr(p)との線形和であり、
前記記憶部は、少なくとも、前記秘密値a(i)と前記公開値A(j)=ga(j)∈Gとを格納し、
前記共有元生成部は、少なくとも、前記秘密値a(i)と、前記公開値A(j)=ga(j)∈Gと、前記任意値r(i)と、前記第2任意元X(j)=gr(j)∈Gとを用い、巡回群Gの元gW(u)∈Gを前記共有元σ(u)として生成する、
ことを特徴とする鍵共有装置。
【請求項5】
請求項1から3の何れかの鍵共有装置であって、
P=3、i=1、j∈{2,3}であり、W(u)=w(u,1)・w(u,2)・w(u,3)であり、w(u,p)はa(p)とr(p)との線形和であり、前記関数eは、前記巡回群Gの2つの元を巡回群Gの1つの元に写像する双線形関数であり、
前記記憶部は、少なくとも、前記秘密値a(i)と前記公開値A(j)=ga(j)∈Gとを格納し、
前記共有元生成部は、少なくとも、前記秘密値a(i)と、2つの前記公開値A(j)=ga(j)∈Gと、前記任意値r(i)と、2つの前記第2任意元X(j)=gr(j)∈Gと、前記関数eとを用い、巡回群Gの元gW(u)=e(g,g)W(u)∈Gを前記共有元σ(u)として生成する、
ことを特徴とする鍵共有装置。
【請求項6】
請求項1から3の何れかの鍵共有装置であって、
P=2であり、W(u)=w(u,1)・w(u,2)・MSKであり、w(u,p)はa(p)とr(p)との線形和であり、前記関数eは、前記巡回群Gの2つの元を巡回群Gの1つの元に写像する双線形関数であり、
前記記憶部は、少なくとも、前記元Z(i)=ga(i)・MSK∈Gと、前記公開値A(j)=ga(j)∈Gと、巡回群Gの元MPK=gMSK∈Gと、を格納し、
前記共有元生成部は、少なくとも、前記元Z(i)=ga(i)・MSK∈Gと、前記公開値A(j)=ga(j)∈Gと、前記任意値r(i)と、前記第2任意元X(j)=gr(j)∈Gと、前記元MPK=gMSK∈Gと、前記関数eとを用い、巡回群Gの元gW(u)=e(g,g)W(u)∈Gを前記共有元σ(u)として生成する、
ことを特徴とする鍵共有装置。
【請求項7】
第1鍵共有装置と第2鍵共有装置とで鍵を共有する鍵共有システムであって、
前記第1鍵共有装置は、
少なくとも、整数の秘密値a(1)又は巡回群Gの元Z(1)=ga(1)・MSK∈Gと、前記第2鍵共有装置に対応する巡回群Gの元である公開値A(2)=ga(2)∈G〔gはgによって巡回群Gのすべての元を表現できる生成元、MSK,m及びa(2)は整数〕と、を格納する第1記憶部と、
整数の任意値r(1)を生成する第1任意値生成部と、
前記任意値r(1)を用い、第1任意元X(1)=gr(1)∈Gを生成する第1任意元生成部と、
前記第1任意元X(1)を出力する第1出力部と、
第2任意元X(2)=gr(2)∈G〔r(2)は整数〕が入力される第1入力部と、
少なくとも、前記秘密値a(1)又は前記元Z(1)=ga(1)・MSK∈Gと、前記公開値A(2)=ga(2)∈Gと、前記任意値r(1)と、前記第2任意元X(2)=gr(2)∈Gとを用い、巡回群Gの元gW(u)∈G〔W(u)は整数w(u,1),w(u,2)を含む2個以上の整数の積、前記整数w(u,p)はa(p)とr(p)とを含む複数の整数の線形和、p∈{1,2}、u∈{1,...,U}、Uは1以上の整数定数〕を第1共有元σ(u)として生成するか、又は、さらに巡回群Gの元を巡回群Gの元に写像する関数eを用い、巡回群Gの元gW(u)∈G〔gはgによって巡回群Gのすべての元を表現できる生成元〕を第1共有元σ(u)として生成する第1共有元生成部と、
少なくとも前記第1共有元σ(u)に基づいて値が定まる第1鍵Kを生成し、当該第1鍵Kを出力する第1鍵生成部と、を含み、
前記第2鍵共有装置は、
少なくとも、整数の秘密値a(2)又は巡回群Gの元Z(2)=ga(2)・MSK∈Gと、前記第1鍵共有装置に対応する巡回群Gの元である公開値A(1)=ga(1)∈Gと、を格納する第2記憶部と、
整数の任意値r(2)を生成する第2任意値生成部と、
前記任意値r(2)を用い、前記第2任意元X(2)=gr(2)∈Gを生成する第2任意元生成部と、
前記第2任意元X(2)を出力する第2出力部と、
前記第1任意元X(1)=gr(1)∈Gが入力される第2入力部と、
少なくとも、前記秘密値a(2)又は前記元Z(2)=ga(2)・MSK∈Gと、前記公開値A(1)=ga(1)∈Gと、前記任意値r(2)と、前記第2任意元X(1)=gr(1)∈Gとを用い、巡回群Gの元gW(u)∈Gを第2共有元σ(u)として生成するか、又は、さらに前記関数eを用い、巡回群Gの元gW(u)∈Gを第2共有元σ(u)として生成する第2共有元生成部と、
少なくとも前記第2共有元σ(u)に基づいて値が定まる第2鍵Kを生成し、当該第2鍵Kを出力する第2鍵生成部と、を含む、
ことを特徴とする鍵共有システム。
【請求項8】
第1鍵共有装置と第2鍵共有装置と第3鍵共有装置とで鍵を共有する鍵共有システムであって、
前記第1鍵共有装置は、
少なくとも、整数の秘密値a(1)と、前記第2鍵共有装置及び前記第3鍵共有装置にそれぞれ対応する巡回群Gの元である公開値A(2)=ga(2),ga(3)∈G〔gはgによって巡回群Gのすべての元を表現できる生成元、m,a(2)及びa(3)は整数〕と、を格納する第1記憶部と、
整数の任意値r(1)を生成する第1任意値生成部と、
前記任意値r(1)を用い、第1任意元X(1)=gr(1)∈Gを生成する第1任意元生成部と、
前記第1任意元X(1)を出力する第1出力部と、
第2任意元X(2)=gr(2)∈G及び第3任意元X(3)=gr(3)∈G〔r(2)及びr(3)は整数〕が入力される第1入力部と、
少なくとも、前記秘密値a(1)と、前記公開値A(2)=ga(2),A(3)=ga(3)∈Gと、前記任意値r(1)と、前記第2任意元X(2)=gr(2)∈G及び前記第3任意元X(3)=gr(3)∈Gと、巡回群Gの元を巡回群Gの元に写像する関数eとを用い、巡回群Gの元gW(u)∈G〔W(u)は整数w(u,1),w(u,2),w(u,3)を含む3個以上の整数の積、前記整数w(u,p)はa(p)とr(p)とを含む複数の整数の線形和、p∈{1,...,3}、u∈{1,...,U}、Uは1以上の整数定数、gはgによって巡回群Gのすべての元を表現できる生成元〕を第1共有元σ(u)として生成する第1共有元生成部と、
少なくとも前記第1共有元σ(u)に基づいて値が定まる第1鍵Kを生成し、当該第1鍵Kを出力する第1鍵生成部と、を含み、
前記第2鍵共有装置は、
少なくとも、整数の秘密値a(2)と、前記第1鍵共有装置及び前記第3鍵共有装置にそれぞれ対応する巡回群Gの元である公開値A(1)=ga(1),A(3)=ga(3)∈Gと、を格納する第2記憶部と、
整数の任意値r(2)を生成する第2任意値生成部と、
前記任意値r(2)を用い、第2任意元X(2)=gr(2)∈Gを生成する第2任意元生成部と、
前記第2任意元X(2)を出力する第2出力部と、
第1任意元X(1)=gr(1)∈G及び第3任意元X(3)=gr(3)∈Gが入力される第2入力部と、
少なくとも、前記秘密値a(2)と、前記公開値A(1)=ga(1),A(3)=ga(3)∈Gと、前記任意値r(2)と、前記第1任意元X(1)=gr(1)∈G及び前記第3任意元X(3)=gr(3)∈Gと、前記関数eとを用い、巡回群Gの元gW(u)∈Gを第2共有元σ(u)として生成する第2共有元生成部と、
少なくとも前記第2共有元σ(u)に基づいて値が定まる第2鍵Kを生成し、当該第2鍵Kを出力する第2鍵生成部と、を含み、
前記第3鍵共有装置は、
少なくとも、整数の秘密値a(3)と、前記第1鍵共有装置及び前記第2鍵共有装置にそれぞれ対応する巡回群Gの元である公開値A(1)=ga(1),A(2)=ga(2)∈Gと、を格納する第3記憶部と、
整数の任意値r(3)を生成する第3任意値生成部と、
前記任意値r(3)を用い、第3任意元X(3)=gr(3)∈Gを生成する第3任意元生成部と、
前記第1任意元X(3)を出力する第3出力部と、
前記第1任意元X(1)=gr(1)∈G及び前記第2任意元X(2)=gr(2)∈Gが入力される第3入力部と、
少なくとも、前記秘密値a(3)と、前記公開値A(1)=ga(1),A(2)=ga(2)∈Gと、前記任意値r(3)と、前記第1任意元X(1)=gr(1)∈G及び前記第2任意元X(2)=gr(2)∈Gと前記関数eとを用い、巡回群Gの元gW(u)∈Gを第3共有元σ(u)として生成する第3共有元生成部と、
少なくとも前記第3共有元σ(u)に基づいて値が定まる第3鍵Kを生成し、当該第3鍵Kを出力する第3鍵生成部と、を含む、
ことを特徴とする鍵共有システム。
【請求項9】
記憶部と任意値生成部と任意元生成部と出力部と入力部と共有元生成部と鍵生成部とを有する鍵共有装置が他の装置と鍵を共有する鍵共有方法であって、
少なくとも、整数の秘密値a(i)又は巡回群Gの元Z(i)=ga(i)・MSK∈Gと、前記他の装置に対応する巡回群Gの元である公開値A(j)=ga(j)∈G〔i,j∈{1,...,P}、j≠i、Pは2以上の整数定数、gはgによって巡回群Gのすべての元を表現できる生成元、MSK,m及びa(j)は整数〕と、が前記記憶部に格納されており、
前記任意値生成部が、整数の任意値r(i)を生成するステップと、
前記任意元生成部が、前記任意値r(i)を用い、第1任意元X(i)=gr(i)∈Gを生成するステップと、
前記出力部が、前記第1任意元X(i)を出力するステップと、
前記入力部に、第2任意元X(j)=gr(j)∈G〔r(j)は整数〕が入力されるステップと、
前記共有元生成部が、少なくとも、前記秘密値a(i)又は前記元Z(i)=ga(i)・MSK∈Gと、前記公開値A(j)=ga(j)∈Gと、前記任意値r(i)と、前記第2任意元X(j)=gr(j)∈Gとを用い、巡回群Gの元gW(u)∈G〔W(u)は整数w(u,1),...,w(u,P)を含むP個以上の整数の積、前記整数w(u,p)はa(p)とr(p)とを含む複数の整数の線形和、p∈{1,...,P}、u∈{1,...,U}、Uは1以上の整数定数〕を共有元σ(u)として生成するか、又は、さらに巡回群Gの元を巡回群Gの元に写像する関数eを用い、巡回群Gの元gW(u)∈G〔gはgによって巡回群Gのすべての元を表現できる生成元〕を共有元σ(u)として生成するステップと、
前記鍵生成部が、少なくとも前記共有元σ(u)に基づいて値が定まる鍵Kを生成し、当該鍵Kを出力するステップと、
を実行する鍵共有方法。
【請求項10】
請求項1から7の何れかの鍵共有装置としてコンピュータを機能させるためのプログラム。


【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate

【図13】
image rotate

【図14】
image rotate

【図15】
image rotate


【公開番号】特開2011−19042(P2011−19042A)
【公開日】平成23年1月27日(2011.1.27)
【国際特許分類】
【出願番号】特願2009−161663(P2009−161663)
【出願日】平成21年7月8日(2009.7.8)
【出願人】(000004226)日本電信電話株式会社 (13,992)
【Fターム(参考)】