マスターキーの構成と安全性の検討
梅澤真美

1(指導教官: 金子 晃)

はじめにとなるようなものである．
例として，次のようなものが考えられる：pj , qj , j =1, 2, . . . , J を互いに異なる素数で，かつfj = LCM(pj − 1, qj − 1), j = 1, 2, . . . , J

日常語としてのマスターキーとは，建物のすべての部屋の鍵を開けられる管理用の鍵のことである．本研
究では，ある組織 (以下簡単のため会社とする) の長(社長) が組織内の暗号通信で用いるために，各部署(企画課，技術課，営業課，人事課) の長 (課長) の鍵，およびそのメンバーの鍵をすべて把握できる効率的なシステムを考える．

2

マスターキーの要求仕様と基本実装

はじめに要求される仕様を整理する．
1. 社長は，社員の全ての暗号文を読めるような鍵情報を保持する．
2. 各課長は，課内のすべての部下の暗号文を読めるような鍵情報を保持する．
3. 以上のほかは，社員同士は通常の暗号通信を行う．
できれば ID 形公開鍵による暗号通信が望ましい．

は 2 以外に共通因子を持たないようなものとする．(これは例えば，pj , qj をすべて co Sophie-Germain 素数に取れば実現できる.) nj = pj qj を法として，J 個の独立な RSA 暗号を用意し，それぞれの秘密鍵，公開鍵を dj , ej とする： dj ej = 1 mod fj . このとき，JY(fj /2), Fj = F/fj
F =2
j=1と置けば，Fj と fj は互いに素となるので，各 j について bj Fj = 1 mod fj なる bj を選べる. このとき，J が奇数なら

D=
また J が偶数ならまず，雛形として次のような手順を考える：

D=JX

dj bj Fj ,j=1
JX

dj bj Fj + F/2,j=1と置けば，D はマスターキーとなる．
実際，任意の i に対して，暗号文 Ci = Miei mod niをとるとき，Mi = Cidi mod ni は当然として，1. 社内で共用するパラメータ付き一方向性ハッシュ関数 h(x, y) を用意する．
2. 社長は秘密の乱数 r を用意しマスターキーとする．

PCiD = Cidi bi Fi Ci j6=i

mod niであり，ここで3. 社長は各課の ID eigyou 等々をマスターキーと合わせ，その課の秘密鍵 seigyou = h(r, eigyou) 等々を作成して当該の課長に手渡す.

Cidi bi Fi = Cidi bi Fi mod fi = Cidi = Mi mod ni
PPまた，dj bj Fj mod fi
dj bj Fj= Ci j6=iCi j6=iにおいては，構成法から明らかに，j 6= i なる各 Fj はP
fi /2 で割り切れているので，最後の指数 j6=i dj bj Fj
は fi /2 で割り切れる．更に，dj , bj , Fj はすべて奇数なので，個数 J が奇数なら，この指数は全体として偶数となり， 2 でも割り切れ，結局 fi で割り切れることとなるから, Ci の冪を取れば 1 となる．また，J が奇数のときは，この指数に F/2 を足したものは偶数となり，この項はすべての fj /2 で割り切れるので同じ結論を得る．よって CiD = Mi mod ni が成り立つ．
このシナリオは ni をグループ化できるので課長にX
F
dj bj Fj + (#eigyou + 1 mod 2)
Deigyou =2

4. 各課長は，部下の各々に対し，課の秘密鍵と，その部下の ID yamada.taro 等を合わせて，その人の秘密鍵 tyamada.taro = h(seigyou , yamada.taro) を作り，本人に手渡す.
この後の各自の秘密鍵の使用法としては，例えば会社全体で巨大な可換群 G と位数の巨大な元 g を共有し，g tyamada.taro を公開鍵として Diffie-Hellman 型の鍵交換を行い，それを用いて共通鍵暗号通信を行うか，El-Gamal 型の公開鍵暗号通信を行えばよい．

3dj bj Fj

RSA 暗号系を用いたマスターキーの構成

j∈eigyou

上の仕組みを RSA 暗号を用いて構成する方法を示す。本物のマスターキーと同様，ある管理職が持っている鍵でその人の下部組織の発信した全ての暗号文を同じ復号関数でできることが重要である。
すなわち，
Cj = Enc(Mj , Kj ), j = 1, 2, . . . , Jから，
Mj = Dec(Cj , Kj′ ), j = 1, 2, . . . , J等を渡すことで階層化が可能である．また，安全性については，個々の RSA 暗号の安全性と同等である．
この方式は，一応所期の要求を満たしているが，ここで示されたマスターキーは，J が大きいと個々のキーdi に対して著しく巨大となり，すべての部屋の鍵の束に近いイメージである．また，マスターキーを持つ社
長が全ての素数データを生成して部下に配布しなければならず，計算量の点であまり実用的ではない．
建物のマスターキーのように，マスターキーが個々のキーと同程度のサイズとなるようなものが理論的に構成可能かどうか，現在検討中である．

かつ，あるマスターキー K ′ について
Mj = Dec(Cj , K ′ ), j = 1, 2, . . . , J

57

4ElGamal 暗号方式を用いたマスターキーの構成が，ElGamal 暗号の場合は，群 G と生成元 g を共通パラメータとして複数の暗号が作れるので，そのような暗号系に対してマスターキーを作ることを考える．
G, g を離散対数のシステムパラメータとし，各部下用に秘密鍵 aj j = 1, . . . , J を用意する. ai はすべて奇数に選ぶ．更に，社長は A = a1 · · · aJ を計算し，各部下用に公開鍵 g ai , g ai /A を発表する．ここで，ai /Aは g の位数 (G = F ×
p のときは p − 1) を法としての計算である．
i 番目の社員への ElGamal 暗号化は全く同様の技法で，ElGamal 暗号系に対するマスターキーを構成可能である．pj , j = 1, 2, . . . , J を互いに異なる素数で，かつfj = (pj − 1)/2, j = 1, 2, . . . , Jは互いに素となるように選ぶ．F ×
pj の生成元 gj を選ぶ必要があるので，pj をすべて co Sophie-Germain
素数に取るのが簡明である．pj を法として，J 個の独立な ElGamal 暗号を用意し，それぞれのシステムパラメータを pj , gj , また秘密鍵，公開鍵を aj , g aj とする.
JYfj , Fj = F/fj
F =Mi 7→ Ci1 , Ci2 , Ci3 ) := (g k , (g ai /A )k , g ai k Miとする．これは，この社員により復号鍵 (K1 , K2 ) =(ai , 0) を用いてj=1と置けば，Fj と fj , 更に pj − 1 は互いに素となるので，各 j について bj Fj = 1 mod pj − 1 なる bj を選べる. (RSA のときと若干記号の意味を変えている.)
このとき，J が奇数ならJX
aj bj Fj ,D=

K1K2)/Ci1(Ci3 /Ci2N で復号される．これが Mi に戻ることは，実質的にElGamal 暗号と同等なことから直ちに分かる．社長
は，マスターキー (K1 , K2 ) = (0, A) を用いて (1) と同じ復号関数で復号する．この場合は

j=1

また J が偶数なら

D=JX

K2= ((g ai /A )k )A = g ai k
Ci2

aj bj Fj + F,となるので，やはり Mi が得られる．
この方式の安全性は，g ai /A の公開が g ai の離散対数の解に有利な情報を与えているかどうかであるが，g ai /A は敵が勝手に A を選んで (g ai )1/A によりシミュレートできるので，何ら有効な情報を漏らしていないことが分かる．

j=1と置けば，D は ElGamal 暗号に対するマスターキーとなる．
実際，任意の i に対して，k をその場限りの乱数として，平文 Mi を Ci = (Ci1 , Ci2 ) := (gik , giai k Mi ) により暗号化するとき， Mi = Ci2 /(Ci1 )ai は当然として，Ci2 /(Ci 1)D = Mi ともなることが，以下のように分かる：

6であり，ここでP(gik )j6=i aj bj Fj

mod (pi −1)= (gik )ai = giai k

Mi 7→ (Ci1 , Ci2 ) := (ksP, Mi ⊕ H(e(sP, kQIDi )))とするとき，復号関数は，復号鍵を (a, Q) としてP= (gik )j6=i aj bj Fj

mod (pi −1)

Ci2 ⊕ H(e(aQIDi + Q, Ci1 ))においては，構成法から明らかに，j 6= i なる各 Fj
Pは fi で割り切れているので，最後の指数 j6=i aj bj Fjは (pi − 1)/2 で割り切れる．更に，aj , bj , Fj はすべて奇数なので，個数 J が奇数なら，この指数は全体として偶数となり，従って 2 でも割り切れ，結局 pi − 1で割り切れることとなるから, gik の冪を取れば 1 となる．また，J が奇数のときは，この指数に F を足したものは偶数となり，この項はすべての fj で割り切れているので同じ結論を得る．よって (gik )D = (gik )aiが成り立ち，i 番目の ElGamal 暗号はこの鍵でも同じ復号関数で復号できる．
この方式を実現するには，社長は通常の ElGamal 暗号と異なり，すべての部下の秘密鍵 ai を作って配布しなければならない．これは RSA の場合と同じである．

5ID ベース暗号への修正

s を社長が保持する秘密のシステムパラメータ，sPを公開のシステムパラメータ，QIDi を公開鍵，sQIDiをユーザー i の秘密情報とし，暗号化関数をP
D
Ci1= (gik )D = (gik )ai bi Fi · (gik ) j6=i aj bj Fj(gik )ai bi Fi = (gik )ai bi Fi
また，(1)と少しひねったものとする．ユーザー i は復号鍵(a, Q) = (0, sQIDi を用いれば，通常の ID ペース暗号の原理で復号できる．また，社長は (a, Q) = (s, O)を復号鍵として用いれば，同じ原理で復号できる．

参考文献[1] NEC ソ フ ト ウェア 北 陸“cybercrypt”
http:www.//hnes.co.jp/sol-pro/sol-pd-3s
ol/cybercrypt/concept.jsp[2] 岡本龍明, 山本博資:“現代暗号” (第３版), 産業図書, 2000.
[3] W. Stallings: “Cryptography and Network Security” (4-th ed.), Pearson Prentice Hall, 2006.

共通パラメータの ElGamal 暗号方式を用いたマスターキーの構成[4] D. Boneh, M. Franklin: “Identity-based encryption from the Weil pairing”, SIAM J. of Computing, 32-3 (2003), 586–615.

RSA 暗号の場合は，同じ n = pq を用いて複数の暗号を作ることは安全性の問題から全く実用的ではない
58