(57)【要約】  手間がかからず、帰着の効率が高い鍵交換装置、鍵交換システム、鍵交換方法、及び記憶媒体を提供する。  鍵交換装置システムは、鍵交換装置Πと鍵交換装置Π’とを備える。鍵交換装置Πは、鍵交換部、入力装置、乱数入力装置、認証装置、通信装置、記憶装置、及び出力装置と、を備え、鍵交換装置Π’は、鍵交換部、入力装置、乱数入力装置、認証装置、通信装置、記憶装置、及び出力装置を備える。
2010001957.tif 000002
【特許請求の範囲】
【請求項１】
命令及び識別子を入力する入力装置、乱数を入力する乱数入力装置、認証子を生成する認証装置、データの授受を行う通信装置、データを記憶する記憶装置、鍵交換結果を出力する出力装置、及び制御装置を備えた鍵交換装置であって、
前記制御装置の指示により、本人識別子πを保持し、鍵交換開始命令と相手識別子とが入力された場合に手続き番号iid を生成し、指示ビットあるいは数bを生成し、暫定数rを生成し、前記暫定数rを利用して生成された冪乗数と、前記暫定数rとは独立に生成した冪乗数とを準備し、この二種類の冪乗数複数個を、指示ビットが前者の冪乗数の場所を示すように並べたものを生成し、前記手続き番号iid、相手識別子π'、複数の冪乗数、指示ビットb、暫定数r を含むデータを所定の状態で前記記憶装置に記憶し、前記手続き番号iid、複数の冪乗数をメッセージとして相手識別子π’の対応する装置に前記通信装置で送信する第一ラウンド装置と、
前記制御装置の指示により、相手手続き番号iid'及び複数の相手の冪乗数を含むメッセージを受信した場合に、前記手続き番号iid、相手識別子π'、複数の冪乗数、指示ビットb、及び暫定数rを含むデータが記憶されている状態を用いて、前記本人識別子π、前記手続き番号iid、前記相手識別子π'、前記相手手続き番号を含むセッション番号sid を生成し、前記セッション番号sid、複数の冪乗数、複数の相手の冪乗数からなる貢献データcont を生成し、貢献データと指示ビット(cont,b) とを含むデータに対する認証子sig を前記認証装置で生成し、複数の鍵候補を生成し、記憶されている状態を、前記セション番号sid、前記貢献データ、及び前記複数の鍵候補を含む状態に変更し、前記セッション番号sid、前記指示ビット b、及び前記認証子を含むデータを送信する第二ラウンド装置と、
前記制御装置の指示により、相手セッション番号sid'、相手指示ビットb'、及び相手認証子sig'を含むメッセージ (sid',b',sig') を受信した場合に、記憶しているセッション番号sid、貢献データ、及び複数の鍵からなる状態を用いて、受信したメッセージの正当性を検証し、前記記憶している複数の鍵から、前記相手指示ビットb' の示す鍵を前記出力装置から出力し、記憶している状態を完全に消去する鍵生成装置と、
を備えたことを特徴とする鍵交換装置。
【請求項２】
命令及び識別子を入力する入力装置、乱数を入力する乱数入力装置、認証子を生成する認証装置、データの授受を行う通信装置、データを記憶する記憶装置、鍵交換結果を出力する出力装置、及び制御装置を備えた鍵交換装置であって、
前記制御装置の指示により、本人識別子πを保持し、鍵交換開始命令と相手識別子π’が入力された場合に、手続き番号 iid を生成し、指示ビット b を生成し、暫定数rを生成し、指示ビットbが 0 ならば第一の冪乗数 y[0] を、暫定数rから生成して第二の冪乗数 y[1] をランダムに生成し、指示ビットbが1ならば第二の冪乗数 y[1] を一時状態 rから生成して第一の冪乗数 y[0] をランダムに生成し、前記手続き番号 iid、相手識別子π'、第一の冪乗数y[0]、第二の冪乗数、指示ビットb、暫定数rを状態 (iid, π',y[0],y[1],b,r) として記憶し、前記手続き番号iid、第一の冪乗数 y[0]、第二の冪乗数をメッセージ (iid, y[0],y[1]) として相手識別子の対応する装置に前記通信装置で送信する第一ラウンド装置と、
前記制御装置の指示により、相手手続き番号 iid'、相手第一の冪乗数 y'[0]、及び相手第二の冪乗数 y'[1]よりなるメッセージ(iid',y'[0],y'[1]) を前記通信装置で受信した場合に、前記手続き番号iid、相手識別子π'、第一の冪乗数y[0]、第二の冪 乗数 y[1]、指示ビットb、及び暫定数rよりなる状態 (iid, π', y[0],y[1],b,r) を用いて、前記本人識別子π、前記手続き番号iid、前記相手識別子π'、前記相手手続き番号からなるセッション番号sid(π,iid,π',iid') を生成し、前記セッション番号sid、第一の冪乗数 y[0]、第二の冪 乗数 y[1]、相手第一の冪乗数y'[0]、相手第二の冪乗数y'[1] からなる貢献データcont(=sid,y[0],y[1],y'[0],y'[1])を生成し、貢献データと指示ビット(cont,b)に対する認証子 sigとを生成し、二つの鍵候補 z[0], z[1] を生成し、前記記憶装置に記憶されている状態を、前記セション番号sid、前記貢献データ、二つの鍵候補z[0],z[1]からなる状態 (sid,cont,z[0],z[1]) に変更し、前記セッション番号sid、前記指示ビットb、前記認証子を送信する第二ラウンド装置と、
前記制御装置の指示により、相手セッション番号 sid'、相手指示ビットb', 相手認証子sig'よりなるメッ セージ (sid',b',sig') で sid'(=π',iid',π,iid) となるものを受信した場合に、前記記憶手段に記憶しているセッション番号sid(=π,iid,π',iid')、貢献データ、二つの鍵からなる状態(sid,cont,z[0],z[1]) を用いて、受信したメッセージの正当性を検証し、前記記憶手段に記憶している二つの鍵 z[0],z[1] から、前記相手指示ビットb'の示す鍵z[b'] を前記出力手段から出力し、前記記憶手段に記憶している状態(sid,cont,z[0],z[1]) を完全に消去する前記鍵生成装置と、を備えたことを特徴とする鍵交換装置。
【請求項３】
命令及び識別子を入力する入力装置、乱数を入力する乱数入力装置、認証子を生成する認証装置、データの授受を行う通信装置、データを記憶する記憶装置、鍵交換結果を出力する出力装置、及び制御装置を備えた二つの鍵交換装置Π，Π’が互いに通信して同一の鍵を共有する鍵交換システムであって、
システムパラメター(q,G,g,Hash,v)が入力装置に入力されると起動し、鍵交換開始命令及び相手識別子π' が入力装置に入力されると、乱数入力装置から乱数を取り込み、手続き番号iid を生成し、指示ビットb ∈ [0,1] をランダム生成し、暫定数r ∈ Z/qZ を乱数からランダムに生成し、冪乗数y[b] = grを生成し、冪乗数y[1-b] ∈ G をランダムに生成、状態(iid, π',y[0],y[1],b,r) を生成してこれを記憶し、前記状態(iid,y[0],y[1]) を鍵交換装置Π' に通信装置により送信し、鍵交換装置Π' から前記状態(iid',y'[0],y'[1]) を通信装置により受信すると、y'[0],y'[1] が G の要素であることを確認し、セッション番号 sid =(π, iid,π',iid') を生成し、貢献データcont(=sid,y[0],y[1],y'[0],y'[1]) を生成し、貢献データ(cont,b) に対する認証を行って認証装置により認証子sigを得、c=0,1 に関して、鍵候補z[c] = Hash(y'[c]r,v) を生成し、前記状態 (iid,
π', y[0],y[1],b,r) を、(sid,cont,z[0],z[1]) に変更し、前記状態(sid,b,sig)を鍵交換装置Π' に通信装置により送信し、鍵交換装置Π' から状態(sid',b',sig')を通信装置により受信すると、("検証",π',(cont,b'),sig' ) が正当であることを確認し、状態(sid,cont,z[0],z[1]) を完全に消去して、(sid,z[b']) を出力装置により出力する、制御装置により動作する鍵交換装置Πと、
システムパラメター(q,G,g,Hash,v) が他の入力装置に入力されると起動し、鍵交換装置Π'は、鍵交換開始命令及び相手識別子πが他の入力装置に入力されると、他の乱数入力装置から乱数を取り込み、手続き番号iid' を生成し、指示ビットb' ∈[0,1] をランダム生成し、暫定数r' ∈ Z/qZ を乱数からランダムに生成し、y'[b] = gr'を生成し、冪乗数y'[1-b] ∈ G をランダムに生成し、状態 (iid', π,y'[0],y'[1],b',r') を生成してこれを他の記憶装置により記憶し、前記状態(iid',y'[0],y'[1]) を鍵交換装置Πに他の通信装置により送信し、鍵交換装置Π' は、鍵交換装置Πから前記状態(iid,y[0],y[1])を他の通信装置により受信すると、y[0],y[1] が G の要素であることを確認し、セッション番号 sid'(=π', iid',π,iid) を生成し、貢献データcont'(=sid',y'[0],y'[1],y[0],y[1]) を生成し、(cont',b') に対する認証を行ってセッション番号sig'を得、c=0,1に関して、鍵候補z'[c] = Hash(y[c]r',v) を生成し、状態 (iid',π,y'[0],y'[1],b',r')を、状態(sid',cont',z'[0],z'[1]) に変更し、状態(sid',b',sig')を鍵交換装置Πに他の通信装置により送信し、鍵交換装置 Π'は、鍵交換装置Πから状態(sid,b,sig)を他の通信装置により受信すると、("検証",π,(cont',b),sig ) が正当であることを確認し、状態 (sid',cont',z'[0],z'[1]) を完全に消去し、状態(sid',z'[b]) を他の出力装置により出力する、他の制御装置により動作する鍵交換装置Π’と、を備えたことを特徴とする鍵交換システム。
【請求項４】
二つの鍵交換装置Π，Π’を備えた鍵交換システムにおける鍵交換方法であって、
鍵交換装置Πは、システムパラメター(q,G,g,Hash,v)が入力されると起動し、
鍵交換装置Π' は、システムパラメター(q,G,g,Hash,v) が入力されると起動し、
鍵交換装置Πは、鍵交換開始命令及び相手識別子π' が入力されると、乱数を取り込み、手続き番号iid を生成し、指示ビットb ∈ [0,1] をランダム生成し、暫定数r ∈ Z/qZ を乱数からランダムに生成し、冪乗数y[b] = grを生成し、冪乗数y[1-b] ∈ G をランダムに生成、状態(iid, π',y[0],y[1],b,r) を生成してこれを記憶し、前記状態(iid,y[0],y[1]) を鍵交換装置Π' に送信し、
鍵交換装置Π'は、鍵交換開始命令及び相手識別子πが入力されると、乱数を取り込み、手続き番号iid' を生成し、指示ビットb' ∈[0,1] をランダム生成し、暫定数r' ∈ Z/qZ を乱数からランダムに生成し、y'[b] = gr'を生成し、冪乗数y'[1-b] ∈ G をランダムに生成し、状態 (iid', π,y'[0],y'[1],b',r') を生成してこれを記憶し、前記状態(iid',y'[0],y'[1]) を鍵交換装置Πに送信し、
鍵交換装置Π は、鍵交換装置Π' から前記状態(iid',y'[0],y'[1]) を受信すると、y'[0],y'[1] が G の要素であることを確認し、セッション番号 sid =(π, iid,π',iid')を生成し、貢献データcont(=sid,y[0],y[1],y'[0],y'[1]) を生成し、貢献データ(cont,b) に対する認証を行って認証子sigを得、c=0,1 に関して、鍵候補z[c] = Hash(y'[c]r,v) を生成し、前記状態 (iid,π',y[0],y[1],b,r) を、 (sid,cont,z[0],z[1]) に変更し、前記状態(sid,b,sig) を鍵交換装置Π' に送信し、
鍵交換装置Π' は、鍵交換装置Πから前記状態(iid,y[0],y[1]) を受信すると、y[0],y[1] が G の要素であることを確認し、セッション番号 sid'(=π', iid',π,iid) を生成し、貢献データ cont'(=sid',y'[0],y'[1],y[0],y[1]) を生成し、(cont',b') に対する認証を行ってセッション番号sig'を得、c=0,1 に関して、鍵候補z'[c] = Hash(y[c]r',v)を生成し、状態 (iid',π,y'[0],y'[1],b',r') を、状態(sid',cont',z'[0],z'[1]) に変更し、状態(sid',b',sig') を鍵交換装置Πに送信し、
鍵交換装置Πは、鍵交換装置Π' から状態(sid',b',sig')を受信すると、("検証",π',(cont,b'),sig' ) が正当であることを確認し、状態 (sid,cont,z[0],z[1]) を完全に消去して、(sid,z[b']) を出力し、
鍵交換装置 Π'は、鍵交換装置Πから状態(sid,b,sig) を受信すると、("検証",π,(cont',b),sig ) が正当であることを確認し、状態 (sid',cont',z'[0],z'[1]) を完全に消去し、状態(sid',z'[b]) を出力することを特徴とする鍵交換方法。
【請求項５】
二つの鍵交換装置Π，Π’が互いに通信して同一の鍵を共有する鍵交換プログラムを記憶した記憶媒体であって、
コンピュータに、鍵交換装置Πが、システムパラメター(q,G,g,Hash,v)が入力されると起動する手順、
鍵交換装置Π'が、システムパラメター(q,G,g,Hash,v) が入力されると起動する手順、
鍵交換装置Πが、鍵交換開始命令及び相手識別子π' が入力されると、乱数を取り込み、手続き番号iid を生成し、指示ビットb ∈ [0,1] をランダム生成し、暫定数r ∈ Z/qZ を乱数からランダムに生成し、冪乗数y[b] = grを生成し、冪乗数y[1-b] ∈ G をランダムに生成、状態(iid, π',y[0],y[1],b,r) を生成してこれを記憶し、前記状態(iid,y[0],y[1]) を鍵交換装置Π' に送信する手順、
鍵交換装置Π'が、鍵交換開始命令及び相手識別子πが入力されると、乱数を取り込み、手続き番号iid' を生成し、指示ビットb' ∈[0,1] をランダム生成し、暫定数r' ∈ Z/qZ を乱数からランダムに生成し、y'[b] = gr'を生成し、冪乗数y'[1-b] ∈ G をランダムに生成し、状態 (iid', π,y'[0],y'[1],b',r') を生成してこれを記憶し、前記状態(iid',y'[0],y'[1]) を鍵交換装置Πに送信する手順、
鍵交換装置Πが、鍵交換装置Π' から前記状態(iid',y'[0],y'[1]) を受信すると、y'[0],y'[1] が G の要素であることを確認し、セッション番号 sid =(π, iid,π',iid')を生成し、貢献データcont(=sid,y[0],y[1],y'[0],y'[1]) を生成し、貢献データ(cont,b) に対する認証を行って認証子sigを得、c=0,1 に関して、鍵候補z[c] = Hash(y'[c]r,v)を生成し、前記状態 (iid,π', y[0],y[1],b,r) を、 (sid,cont,z[0],z[1]) に変更し、前記状態(sid,b,sig) を鍵交換装置Π' に送信する手順、
鍵交換装置Π'が、鍵交換装置Πから前記状態(iid,y[0],y[1]) を受信すると、y[0],y[1] が G の要素であることを確認し、セッション番号 sid'(=π', iid',π,iid) を生成し、貢献データ cont'(=sid',y'[0],y'[1],y[0],y[1]) を生成し、(cont',b') に対する認証を行ってセッション番号sig'を得、c=0,1 に関して、鍵候補z'[c] = Hash(y[c]r',v) を生成し、状態 (iid',π,y'[0],y'[1],b',r') を、状態(sid',cont',z'[0],z'[1]) に変更し、状態(sid',b',sig') を鍵交換装置Πに送信する手順、
鍵交換装置Πが、鍵交換装置Π' から状態(sid',b',sig')を受信すると、("検証",π',(cont,b'),sig' ) が正当であることを確認し、状態 (sid,cont,z[0],z[1]) を完全に消去して、(sid,z[b']) を出力する手順、
鍵交換装置 Π'が、鍵交換装置Πから状態(sid,b,sig) を受信すると、("検証",π,(cont',b),sig ) が正当であることを確認し、状態 (sid',cont',z'[0],z'[1]) を完全に消去し、状態(sid',z'[b]) を出力する手順を実行させる鍵交換プログラムを記憶したことを特徴とする。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、鍵交換装置、鍵交換システム、鍵交換方法、及び記憶媒体に関する。
【背景技術】
【０００２】
鍵交換方式には二つの鍵交換装置が参加し、これら二つの鍵交換装置が互いに通信することにより、同一の鍵を共有する方式がある。特に、各鍵交換装置が自分である事の認証を受ける方法を備え、鍵を交換した相手の装置を認証する方式を、「認証付き鍵交換方式」と呼ぶ。【０００３】
本発明に関連する認証付き鍵交換方式として、非特許文献１に記されている方式があげられる。
以下、本認証付き鍵交換方式の概略を図１〜３を参照して示す。
図１は、本発明に関連する鍵交換システムの概念図である。図２は、図１に示した鍵交換装置に用いられる第一ラウンド装置の概念図である。図３は、図１に示した鍵交換装置に用いられる鍵生成装置の概念図である。
図１に示す鍵交換システムは、鍵交換装置Πと鍵交換装置Π’とを備える。
鍵交換装置Πは、鍵交換部[500a]、入力装置[501a]、乱数入力装置[502a]、認証装置[504a]、通信装置[505a]、記憶装置[503a]、及び出力装置[506a]を備え、鍵交換装置Π’は、鍵交換部[500b]、入力装置[501b]、乱数入力装置[502b]、認証装置[504b]、通信装置[505b]、記憶装置[503b]、及び出力装置[506b]を備える。【０００４】
システムパラメター[507a](q,G,g,Hash)、自己識別子[508a]πが入力されて起動され命令待ち状態となる。
命令待ち状態の鍵交換装置[500a]Πが、鍵交換開始命令[509]、セッション番号[512a] sid、相手識別子[510a] π'を入力された場合、次のように第一ラウンド装置[600a]が動作する(ここで、セッション番号sid は鍵交換装置Π と鍵交換装置Π'とが鍵交換に使う数としては唯一無二の数である。)。【０００５】
乱数入力装置[502a]より乱数[511a]を取り込む。
図２において、暫定数[601]r∈ Z/qZを乱数[511]からランダムに生成する[602]。
y = grを生成する[603]。yを冪乗数[604]と呼ぶ。【０００６】
状態[605] (sid, Π',r) を生成して、この状態を記憶[503]する。
("生成",(sid,y)) を認証装置[504]に入力し、識別子[606]sig を得る。
メッセージ[607](sid,y,sig) を、通信装置を用いて、送信者が 鍵交換装置Πで宛先が鍵交換装置Π'であるとして送信する。【０００７】
鍵交換装置[300]は命令待ち状態となる。
命令待ち状態の鍵交換装置[500] Πが、通信装置[505]を通じて、送信者が 鍵交換装置Π' 宛先が鍵交換装置Πであるメッセージ[701] (sid,y',sig') を受信した場合、鍵生成装置Π‘[700]が次のように動作する。【０００８】
図３に示す記憶装置[503]に保存されている状態を調べ[702]、いかなる y,r に対しても、状態 (sid,y,r) を記憶していなければ、鍵交換装置は直ちに命令待ち状態となる[703]。
ある y,r に対して、状態[704] (sid,y,r) を記憶していたとする("検証",π',(sid,y'),sig' ) を認証装置[504]に入力する。認証装置[504]が"不当"を出力した場合、鍵交換装置[500]は直ちに命令待ち状態となる[703]。
記憶装置[503]にある状態 (sid,π',y,r) を完全に消去し[705]、冪乗数[706] y を用いて(sid,z=y'r) を生成し[708]、出力する[707]。これが交換鍵[707]である。【０００９】
本発明に関連する技術の一例が特許文献１〜３に記載されている。
特許文献１の「１つまたは複数のコンピュータ読取り可能媒体」は、「１つまたは複数の処理装置によって実行されると、ネットワークを介した単一のラウンドトリップで、デバイスとの相互認証およびパーフェクトフォワードシークレシの両方を達成するネットワーク上のデバイスとの鍵交換を１つまたは複数の処理装置に実行させる複数の命令を格納した」ことを特徴とする。【００１０】
この「１つまたは複数のコンピュータ読取り可能媒体」によれば、ネットワーク上のデバイスとの鍵交換は、ネットワークを介した単一のラウンドトリップ（ｒｏｕｎｄｔｒｉｐ）で実行され、デバイスとの相互認証およびパーフェクトフォワードシークレシ（ｐｅｒｆｅｃｔ  ｆｏｒｗａｒｄ  ｓｅｃｒｅｃｙ）の両方を達成するとしている。【００１１】
特許文献２の「復元型電子署名方法」は、「コンピュータ通信網を利用した情報交換システムにおける、電子メッセージｍに対して電子署名を生成する復元型電子署名方法において、署名者が選択した任意数ｒについて演算手段を用いてｇを−ｒ乗してｇ−ｒを求めた後、これにメッセージｍを掛けてｐで割った剰余を計算する第１段階、演算手段を用い、ｘと自分の識別番号ＩＤとを共にハッシュ関数に入力してｈ（ｘ，ＩＤ）を求めて、これに自分の秘密鍵ａを掛けた後ｘの計算に使用した任意数ｒを足してｑで割った剰余を計算してメッセージｍに対する電子署名（ｘ，ｙ）を生成する第２段階、および、検証者が電子署名（ｘ，ｙ）および識別子ＩＤを受信すると、演算手段を用い、電子署名（ｘ，ｙ）のｘと署名者の識別番号ＩＤを共にハッシュ関数に入力してｈ（ｘ，ＩＤ）を求めた後、ｇをｙ乗してこれに署名者の公開鍵のｖをｈ（ｘ，ＩＤ）乗して掛けた値にさらにｘを掛けた後ｐで割った剰余ｘｇｙｖh(x,ID)  ｍｏｄ  ｐを計算して、ｘに包含されているメッセージｍを復元してこの内容を確認し、メッセージｍについての電子署名の正当性を検証する第３段階を、コンピュータを用いた計算にしたがって実行する」ことを特徴とする。【００１２】
この「復元型電子署名方法」によれば、二人の使用者が、第三者がわからないように共通の秘密鍵を交換することにより、システムの信頼性を向上できる効果があるとしている。【００１３】
特許文献３に記載の「データ伝送装置」は、「通信ネットワークを利用して互いに所望のデータの送／受信を行うデータ伝送装置において、データの授受を行うために他のデータ伝送装置との間で相互認証の処理を行い、他のデータ伝送装置との間の認証の有効／無効を判別する判別手段と、判別手段において認証を無効と判別すべき他のデータ伝送装置の識別情報を保持する保持手段とを備え、認証を無効とすべき他のデータ伝送装置の識別情報を、通信ネットワークを介して接続されるデータ伝送装置の識別情報管理装置より受信して、保持手段に保持させるようにした」ことを特徴とする。【００１４】
この「データ伝送装置」によれば、不特定多数のデータ送信装置、及び不特定多数のデータ受信装置が接続され、それら各々の装置同士の間でコンテンツデータの授受が行われる通信ネットワーク環境において、コンテンツデータの著作権を侵害する虞のある不正装置の排除を、より効率的に、且つ、確実に行うことができるようにすることができるとしている。
【先行技術文献】
【特許文献】
【００１５】
【特許文献１】特開２００４−１５８１３号公報
【特許文献２】特開２００４−１２９３０３号公報
【特許文献３】特開２００４−３１２２１６号公報
【非特許文献】
【００１６】
【非特許文献１】Ran Canetti, Hugo Krawczyk."Universally Composable Notions of Key Exchange and Secure Channels",Advances in Cryptology - EUROCRYPT 2002,International Conference on the Theory and Applications of Cryptographic Techniques, Amsterdam, The Netherlands, April 28 - May 2, 2002, Proceedings, pages 337-351, Springer, Lecture Notes in Computer Science, volume 2332, year2002.
【発明の概要】
【発明が解決しようとする課題】
【００１７】
第一の問題点は、本発明関連する鍵交換方式では、二つの装置に唯一無二であることが保証されたセッション番号 sid が入力されなければならないことである。このセッション番号を決定するには両装置の間で、更なる対話が必要になるなど、非常に手間がかかる。【００１８】
第二の問題は、この方式の安全性である、Diffie-Hellman判別問題の難しさに対する帰着の効率が低いことである。この理由に関しては発明の効果の最後に記す。【００１９】
そこで、本発明の目的は、手間がかからず、帰着の効率が高い鍵交換装置、鍵交換システム、鍵交換方法、鍵交換プログラム、及び記憶媒体を提供することにある。
【課題を解決するための手段】
【００２０】
本発明の第１の装置は、命令及び識別子を入力する入力装置、乱数を入力する乱数入力装置、認証子を生成する認証装置、データの授受を行う通信装置、データを記憶する記憶装置、鍵交換結果を出力する出力装置、及び制御装置を備えた鍵交換装置であって、前記制御装置の指示により、本人識別子πを保持し、鍵交換開始命令と相手識別子とが入力された場合に手続き番号iid を生成し、指示ビットあるいは数bを生成し、暫定数rを生成し、前記暫定数rを利用して生成された冪乗数と、前記暫定数rとは独立に生成した冪乗数とを準備し、この二種類の冪乗数複数個を、指示ビットが前者の冪乗数の場所を示すように並べたものを生成し、前記手続き番号iid、相手識別子π'、複数の冪乗数、指示ビットb、暫定数r を含むデータを所定の状態で前記記憶装置に記憶し、前記手続き番号iid、複数の冪乗数をメッセージとして相手識別子π’の対応する装置に前記通信装置で送信する第一ラウンド装置と、前記制御装置の指示により、相手手続き番号iid'及び複数の相手の冪乗数を含むメッセージを受信した場合に、前記手続き番号iid、相手識別子π'、複数の冪乗数、指示ビットb、及び暫定数rを含むデータが記憶されている状態を用いて、前記本人識別子π、前記手続き番号iid、前記相手識別子π'、前記相手手続き番号を含むセッション番号sid を生成し、前記セッション番号sid、複数の冪乗数、複数の相手の冪乗数からなる貢献データcont を生成し、貢献データと指示ビット(cont,b) とを含むデータに対する認証子sig を前記認証装置で生成し、複数の鍵候補を生成し、記憶されている状態を、前記セション番号sid、前記貢献データ、及び前記複数の鍵候補を含む状態に変更し、前記セッション番号sid、前記指示ビット b、及び前記認証子を含むデータを送信する第二ラウンド装置と、前記制御装置の指示により、相手セッション番号sid'、相手指示ビットb'、及び相手認証子sig'を含むメッセージ (sid',b',sig') を受信した場合に、記憶しているセッション番号sid、貢献データ、及び複数の鍵からなる状態を用いて、受信したメッセージの正当性を検証し、前記記憶している複数の鍵から、前記相手指示ビットb' の示す鍵を前記出力装置から出力し、記憶している状態を完全に消去する鍵生成装置と、を備えたことを特徴とする。【００２１】
本発明の第２の装置は、命令及び識別子を入力する入力装置、乱数を入力する乱数入力装置、認証子を生成する認証装置、データの授受を行う通信装置、データを記憶する記憶装置、鍵交換結果を出力する出力装置、及び制御装置を備えた鍵交換装置であって、前記制御装置の指示により、本人識別子πを保持し、鍵交換開始命令と相手識別子π’が入力された場合に、手続き番号 iid を生成し、指示ビット b を生成し、暫定数rを生成し、指示ビットbが 0 ならば第一の冪乗数 y[0] を、暫定数rから生成して第二の冪乗数 y[1] をランダムに生成し、指示ビットbが1ならば第二の冪乗数 y[1] を一時状態 rから生成して第一の冪乗数 y[0] をランダムに生成し、前記手続き番号 iid、相手識別子π'、第一の冪乗数y[0]、第二の冪乗数、指示ビットb、暫定数rを状態 (iid, π',y[0],y[1],b,r) として記憶し、前記手続き番号iid、第一の冪乗数 y[0]、第二の冪乗数をメッセージ (iid, y[0],y[1]) として相手識別子の対応する装置に前記通信装置で送信する第一ラウンド装置と、前記制御装置の指示により、相手手続き番号 iid'、相手第一の冪乗数 y'[0]、及び相手第二の冪乗数 y'[1]よりなるメッセージ(iid',y'[0],y'[1]) を前記通信装置で受信した場合に、前記手続き番号iid、相手識別子π'、第一の冪乗数y[0]、第二の冪 乗数 y[1]、指示ビットb、及び暫定数rよりなる状態 (iid, π', y[0],y[1],b,r) を用いて、前記本人識別子π、前記手続き番号iid、前記相手識別子π'、前記相手手続き番号からなるセッション番号sid(π,iid,π',iid') を生成し、前記セッション番号sid、第一の冪乗数 y[0]、第二の冪 乗数 y[1]、相手第一の冪乗数y'[0]、相手第二の冪乗数y'[1] からなる貢献データcont(=sid,y[0],y[1],y'[0],y'[1])を生成し、貢献データと指示ビット(cont,b)に対する認証子 sigとを生成し、二つの鍵候補 z[0], z[1] を生成し、前記記憶装置に記憶されている状態を、前記セション番号sid、前記貢献データ、二つの鍵候補z[0],z[1]からなる状態 (sid,cont,z[0],z[1]) に変更し、前記セッション番号sid、前記指示ビットb、前記認証子を送信する第二ラウンド装置と、前記制御装置の指示により、相手セッション番号 sid'、相手指示ビットb', 相手認証子sig'よりなるメッ セージ (sid',b',sig') で sid'(=π',iid',π,iid) となるものを受信した場合に、前記記憶手段に記憶しているセッション番号sid(=π,iid,π',iid')、 貢献データ、二つの鍵からなる状態(sid,cont,z[0],z[1]) を用いて、受信したメッセージの正当性を検証し、前記記憶手段に記憶している二つの鍵 z[0],z[1] から、前記相手指示ビットb'の示す鍵z[b'] を前記出力手段から出力し、前記記憶手段に記憶している状態(sid,cont,z[0],z[1]) を完全に消去する前記鍵生成装置と、を備えたことを特徴とする。【００２２】
本発明のシステムは、命令及び識別子を入力する入力装置、乱数を入力する乱数入力装置、認証子を生成する認証装置、データの授受を行う通信装置、データを記憶する記憶装置、鍵交換結果を出力する出力装置、及び制御装置を備えた二つの鍵交換装置Π，Π’が互いに通信して同一の鍵を共有する鍵交換システムであって、システムパラメター(q,G,g,Hash,v)が入力装置に入力されると起動し、鍵交換開始命令及び相手識別子π' が入力装置に入力されると、乱数入力装置から乱数を取り込み、手続き番号iid を生成し、指示ビットb ∈ [0,1] をランダム生成し、暫定数r ∈ Z/qZ を乱数からランダムに生成し、冪乗数y[b] = grを生成し、冪乗数y[1-b] ∈ G をランダムに生成、状態(iid, π',y[0],y[1],b,r) を生成してこれを記憶し、前記状態(iid,y[0],y[1]) を鍵交換装置Π' に通信装置により送信し、鍵交換装置Π' から前記状態(iid',y'[0],y'[1]) を通信装置により受信すると、y'[0],y'[1] が G の要素であることを確認し、セッション番号 sid =(π, iid,π',iid') を生成し、貢献データcont(=sid,y[0],y[1],y'[0],y'[1]) を生成し、貢献データ(cont,b) に対する認証を行って認証装置により認証子sigを得、c=0,1 に関して、鍵候補z[c] = Hash(y'[c]r,v) を生成し、前記状態 (iid,π', y[0],y[1],b,r) を、(sid,cont,z[0],z[1]) に変更し、前記状態(sid,b,sig) を鍵交換装置Π' に通信装置により送信し、鍵交換装置Π' から状態(sid',b',sig')を通信装置により受信すると、("検証",π',(cont,b'),sig' ) が正当であることを確認し、状態 (sid,cont,z[0],z[1]) を完全に消去して、(sid,z[b']) を出力装置により出力する、制御装置により動作する鍵交換装置Πと、システムパラメター(q,G,g,Hash,v) が他の入力装置に入力されると起動し、鍵交換装置Π'は、鍵交換開始命令及び相手識別子πが他の入力装置に入力されると、他の乱数入力装置から乱数を取り込み、手続き番号iid' を生成し、指示ビットb' ∈[0,1] をランダム生成し、暫定数r' ∈ Z/qZ を乱数からランダムに生成し、y'[b] = gr'を生成し、冪乗数y'[1-b] ∈ G をランダムに生成し、状態 (iid', π,y'[0],y'[1],b',r') を生成してこれを他の記憶装置により記憶し、前記状態(iid',y'[0],y'[1]) を鍵交換装置Πに他の通信装置により送信し、鍵交換装置Π' は、鍵交換装置Πから前記状態(iid,y[0],y[1]) を他の通信装置により受信すると、y[0],y[1] が G の要素であることを確認し、セッション番号 sid'(=π', iid',π,iid) を生成し、貢献データ cont'(=sid',y'[0],y'[1],y[0],y[1]) を生成し、(cont',b') に対する認証を行ってセッション番号sig'を得、c=0,1 に関して、鍵候補z'[c] = Hash(y[c]r',v) を生成し、状態 (iid',π, y'[0],y'[1],b',r') を、状態(sid',cont',z'[0],z'[1]) に変更し、状態(sid',b',sig') を鍵交換装置Πに他の通信装置により送信し、鍵交換装置 Π'は、鍵交換装置Πから状態(sid,b,sig) を他の通信装置により受信すると、("検証",π,(cont',b),sig ) が正当であることを確認し、状態 (sid',cont',z'[0],z'[1]) を完全に消去し、状態(sid',z'[b]) を他の出力装置により出力する、他の制御装置により動作する鍵交換装置Π’と、を備えたことを特徴とする。【００２３】
本発明の方法は、二つの鍵交換装置Π，Π’を備えた鍵交換システムにおける鍵交換方法であって、鍵交換装置Πは、システムパラメター(q,G,g,Hash,v)が入力されると起動し、鍵交換装置Π' は、システムパラメター(q,G,g,Hash,v) が入力されると起動し、鍵交換装置Πは、鍵交換開始命令及び相手識別子π' が入力されると、乱数を取り込み、手続き番号iid を生成し、指示ビットb ∈ [0,1] をランダム生成し、暫定数r ∈ Z/qZ を乱数からランダムに生成し、冪乗数y[b] = grを生成し、冪乗数y[1-b] ∈ G をランダムに生成、状態(iid, π',y[0],y[1],b,r) を生成してこれを記憶し、前記状態(iid,y[0],y[1]) を鍵交換装置Π' に送信し、鍵交換装置Π'は、鍵交換開始命令及び相手識別子πが入力されると、乱数を取り込み、手続き番号iid' を生成し、指示ビットb' ∈[0,1] をランダム生成し、暫定数r' ∈ Z/qZ を乱数からランダムに生成し、y'[b] = gr'を生成し、冪乗数y'[1-b] ∈ G をランダムに生成し、状態 (iid', π,y'[0],y'[1],b',r') を生成してこれを記憶し、前記状態(iid',y'[0],y'[1]) を鍵交換装置Πに送信し、鍵交換装置Π は、鍵交換装置Π' から前記状態(iid',y'[0],y'[1]) を受信すると、y'[0],y'[1] が G の要素であることを確認し、セッション番号 sid =(π, iid,π',iid') を生成し、貢献データcont(=sid,y[0],y[1],y'[0],y'[1]) を生成し、貢献データ(cont,b) に対する認証を行って認証子sigを得、c=0,1 に関して、鍵候補z[c] = Hash(y'[c]r,v) を生成し、前記状態 (iid,π', y[0],y[1],b,r) を、 (sid,cont,z[0],z[1]) に変更し、前記状態(sid,b,sig) を鍵交換装置Π' に送信し、鍵交換装置Π' は、鍵交換装置Πから前記状態(iid,y[0],y[1]) を受信すると、y[0],y[1] が G の要素であることを確認し、セッション番号 sid'(=π', iid',π,iid) を生成し、貢献データ cont'(=sid',y'[0],y'[1],y[0],y[1]) を生成し、(cont',b') に対する認証を行ってセッション番号sig'を得、c=0,1 に関して、鍵候補z'[c] = Hash(y[c]r',v) を生成し、状態 (iid',π, y'[0],y'[1],b',r') を、状態(sid',cont',z'[0],z'[1]) に変更し、状態(sid',b',sig') を鍵交換装置Πに送信し、鍵交換装置Πは、鍵交換装置Π' から状態(sid',b',sig')を受信すると、("検証",π',(cont,b'),sig' ) が正当であることを確認し、状態 (sid,cont,z[0],z[1]) を完全に消去して、(sid,z[b']) を出力し、鍵交換装置 Π'は、鍵交換装置Πから状態(sid,b,sig) を受信すると、("検証",π,(cont',b),sig ) が正当であることを確認し、状態 (sid',cont',z'[0],z'[1]) を完全に消去し、状態(sid',z'[b]) を出力することを特徴とする。【００２４】
本発明の記憶媒体は、二つの鍵交換装置Π，Π’が互いに通信して同一の鍵を共有する鍵交換プログラムを記憶した記憶媒体であって、コンピュータに、鍵交換装置Πが、システムパラメター(q,G,g,Hash,v)が入力されると起動する手順、鍵交換装置Π'が、システムパラメター(q,G,g,Hash,v) が入力されると起動する手順、鍵交換装置Πが、鍵交換開始命令及び相手識別子π' が入力されると、乱数を取り込み、手続き番号iid を生成し、指示ビットb ∈ [0,1] をランダム生成し、暫定数r ∈ Z/qZ を乱数からランダムに生成し、冪乗数y[b] = grを生成し、冪乗数y[1-b] ∈ G をランダムに生成、状態(iid, π',y[0],y[1],b,r) を生成してこれを記憶し、前記状態(iid,y[0],y[1]) を鍵交換装置Π' に送信する手順、鍵交換装置Π'が、鍵交換開始命令及び相手識別子πが入力されると、乱数を取り込み、手続き番号iid' を生成し、指示ビットb' ∈[0,1] をランダム生成し、暫定数r' ∈ Z/qZ を乱数からランダムに生成し、y'[b] = gr'を生成し、冪乗数y'[1-b] ∈ G をランダムに生成し、状態 (iid', π,y'[0],y'[1],b',r') を生成してこれを記憶し、前記状態(iid',y'[0],y'[1]) を鍵交換装置Πに送信する手順、鍵交換装置Πが、鍵交換装置Π' から前記状態(iid',y'[0],y'[1]) を受信すると、y'[0],y'[1] が G の要素であることを確認し、セッション番号 sid =(π, iid,π',iid') を生成し、貢献データcont(=sid,y[0],y[1],y'[0],y'[1]) を生成し、貢献データ(cont,b) に対する認証を行って認証子sigを得、c=0,1 に関して、鍵候補z[c] = Hash(y'[c]r,v) を生成し、前記状態 (iid,π', y[0],y[1],b,r) を、 (sid,cont,z[0],z[1]) に変更し、前記状態(sid,b,sig) を鍵交換装置Π' に送信する手順、鍵交換装置Π'が、鍵交換装置Πから前記状態(iid,y[0],y[1]) を受信すると、y[0],y[1] が G の要素であることを確認し、セッション番号 sid'(=π', iid',π,iid) を生成し、貢献データ cont'(=sid',y'[0],y'[1],y[0],y[1]) を生成し、
(cont',b') に対する認証を行ってセッション番号sig'を得、c=0,1 に関して、鍵候補z'[c] = Hash(y[c]r',v) を生成し、状態 (iid',π, y'[0],y'[1],b',r') を、状態(sid',cont',z'[0],z'[1]) に変更し、状態(sid',b',sig') を鍵交換装置Πに送信する手順、鍵交換装置Πが、鍵交換装置Π' から状態(sid',b',sig')を受信すると、("検証",π',(cont,b'),sig' ) が正当であることを確認し、状態(sid,cont,z[0],z[1]) を完全に消去して、(sid,z[b']) を出力する手順、鍵交換装置 Π'が、鍵交換装置Πから状態(sid,b,sig) を受信すると、("検証",π,(cont',b),sig ) が正当であることを確認し、状態 (sid',cont',z'[0],z'[1]) を完全に消去し、状態(sid',z'[b]) を出力する手順を実行させるプログラムを記憶したことを特徴とする。
【発明の効果】
【００２５】
本発明によれば、手間がかからず、帰着の効率が高い鍵交換装置、鍵交換システム、鍵交換方法、及び記憶媒体の提供を実現することができる。
【図面の簡単な説明】
【００２６】
【図１】本発明に関連する鍵交換システムの概念図である。
【図２】図１に示した鍵交換装置に用いられる第一ラウンド装置の概念図である。
【図３】図１に示した鍵交換装置に用いられる鍵生成装置の概念図である。
【図４】本発明に係る鍵交換装置を２つ用いた鍵交換システムの概念図の一例である。
【図５】図４に示した鍵交換装置に用いられる第一ラウンド装置の一例である。
【図６】図４に示した鍵交換装置に用いられる第二ラウンド装置の一例である。
【図７】図４に示した鍵交換装置に用いられる鍵生成装置の一例である。
【図８】本発明に係る鍵交換システムの動作を説明するためのシーケンス図の一例である。
【発明を実施するための形態】
【００２７】
q を素数とし、Gを位数qの乗法的巡回群とし、gをGの生成元とする。Hashをハッシュ関数とする。v をランダムに選ばれた文字列とする。φは、対応するデータが空である事を表す。"開始"のように引用記号でくくられる単語は文字列データとして扱われる。(q,G,g,Hash,v) をシステムパラメターと呼ぶ。鍵交換装置は群G の演算装置、Z/qZの体演算の装置、ハッシュ関数の演算装置が備わっているものとする。
鍵交換装置は認証装置を備えている。
【００２８】
認証装置は、次のように動作する。
Πの認証装置AM(Π) は、Π よりメッセージに ("生成",m) が与えられるとこれに対して認証子sigを生成して返す。Πより("検証",Π',m,sig) が与えられると、"正当" あるいは "不当" を返す。
【００２９】
ここで、認証装置は次のような性質を満足している。
(1) sig がΠ'の認証装置AM(Π')に Π' が("生成",m) を入力したときのAM (Π') の出力が sig であれば、AM(Π) は必ず"正当" を返す。
(2) Πの認証装置AM(Π) に" 正当" を出力させる様な入力("検証",Π', m,sig) の sig はΠ' の認証装置AM (Π') に Π' が("生成",m) を入力することによってしか生成できない。この様な性質を持つ認証装置は、電子署名やメッセージ認証コードにより実現できる。交換結果である効果鍵は、読み出し装置[214] により読み込まれ、外部部のアプリケーションにより利用される。
【実施例１】
【００３０】
次に本発明に係る鍵交換装置の一実施例について説明する。
図４は、本発明に係る鍵交換装置を２つ用いた鍵交換システムの概念図の一例である。
図５は、図４に示した鍵交換装置に用いられる第一ラウンド装置の一例である。図６は、図４に示した鍵交換装置に用いられる第二ラウンド装置の一例である。図７は、図４に示した鍵交換装置に用いられる鍵生成装置の一例である。【００３１】
図４に示す鍵交換装置システムは、鍵交換装置Πと鍵交換装置Π’とを備える。
鍵交換装置Πは、鍵交換部[100a]、入力装置[101a]、乱数入力装置[102a]、認証装置[103a]、通信装置[105a]、記憶装置 [104a]、及び出力装置[106a]とを備え、鍵交換装置Π’は、鍵交換部[100b]、入力装置[101b]、乱数入力装置[102b]、認証装置[103b]、通信装置[105b]、記憶装置 [104b]、及び出力装置[106b]を備える。【００３２】
図５に示す第一ラウンド装置は、手続き番号生成手段[201]、指示ビット生成手段[204]、暫定数生成手段[206]、及び冪乗数生成手段[207]を備える。【００３３】
システムパラメター[107](q,G,g,Hash)、自己識別子[108]πが入力されて起動され命令待ち状態となる。
命令待ち状態の鍵交換装置 Π[100]が、鍵交換開始命令[109]、相手識別子π' [110] を入力された場合、第一ラウンド 装置[200]が次のように動作する。【００３４】
第一ラウンド装置[200]は、乱数入力装置[102]より乱数[111]を取り込む。
第一ラウンド装置[200]は、手続き番号生成手段[201]により手続き番号iid を乱数[111]から手続き番号生成手段[201]が生成する(手続き番号iidは、自己識別子πの中で唯一無二である)。
第一ラウンド装置[200]は、指示ビット生成手段[204]により指示ビット[203] b ∈ [0,1] を乱数[111]からランダムに生成する。
第一ラウンド装置[200]は、暫定数生成手段[206]により暫定数[205] r ∈Z/qZ を乱数[111]からランダムに生成する。
第一ラウンド装置[200]は、冪乗数生成手段[207]によりy[b] = grを生成し、y[1-b] ∈ G を乱数[111]からランダ ムに生成する。y[0]、y[1] を第一と第二の冪乗数[208]と呼ぶ。
第一ラウンド装置[200]は、状態[209] (iid, π',y[0],y[1],b,r) を生成して、これを記憶[103]する。
第一ラウンド装置[200]は、メッセージ[212] (iid,y[0],y[1]) を通信装置[105]を用いて、送信者が 鍵交換装置Πで宛先が 鍵交換装置Π' である として送信する。((iid,y[0],y[1]) に対する認証子を生成し、共に送っても良い。この場合、受信先でこの認証子が検証される。)
鍵交換装置[100]は、命令待ち状態となる。
命令待ち状態の鍵交換装置 Π[100]が、通信装置[105]を通じて、送信者が鍵交換装置Π' で宛 先が鍵交換装置Πであるメッセージ 301 (iid',y'[0],y'[1]) を受信した場合、第二ラウンド装置[300]が次のように動作する。【００３５】
(メッセージ(iid',y'[0],y'[1]) 以外に 鍵交換装置Π' の認証子も添付されている場合は、これを検証して、不当であるならば鍵交換装置Π[100]は直ちに命令待ち状態となる。)
第二ラウンド装置[300]は、記憶装置[103]に保存されている状態を参照し、いかなるiid, y[0],y[1],b,r[b], に関しても、状態(iid, π', y[0],y[1],b,r) を記憶していなければ、鍵交換装置[100] は直ちに命令待ち状態となる[303]。
記憶装置[103]があるiid, y[0],y[1],b,r, に関して、状態(iid, π', y[0],y[1],b,r) を記憶しているとする。複数記憶している場合はそれらの内の一つを選ぶ[302]。選ばれた状態[303]を以降、(iid, π', y[0],y[1],b,r) と記す。【００３６】
第二ラウンド装置[300]は、y'[0],y'[1] が G の要素であることを要素確認手段[304]により確認し、いずれかがそうではない場合は、鍵交換装置[100] は直ちに命令待ち状態となる[303]。
第二ラウンド装置[300]は、セッション番号[305]としての sid =(π,iid,π',iid')を生成する[306]。セッション番号貢献データ生成手段[306]により貢献データ[307] としてのcont =(sid,y[0],y[1],y'[0],y'[1]) を生成する。
第二ラウンド装置[300]は、選ばれた状態[303]に含まれる指示ビット[308] と貢献データ[307]("生成 ",(cont,b)) を認証装置[104]に入力し、認証子 [309]sig を得る。
第二ラウンド装置[300]は、c=0,1 に関して、二つの鍵候補310] z[c] = Hash(y'[c]r,v)を生成する[311]。
第二ラウンド装置[300]は、記憶装置[103] の中にある上の選ばれた状態[303]としての(iid, π', y[0],y[1],b,r) を、新たな状態[312](sid,cont,z[0],z[1]) に変更する[313]。
第二ラウンド装置[300]は、メッセージ[314] (sid,b,sig) を通信装置[105]を用いて、送信者が鍵交換装置Πで宛先が鍵交換装置Π' であるとして送信する。
命令待ち状態の鍵交換装置 Π[100]が、通信装置[105]を通じて、送信者が鍵交換装置Π'で宛先が鍵交換装置Πであるメッセージ[401] (sid',b',sig') を受信した場合、鍵生成装置[400]が次のように動作する。【００３７】
鍵生成装置[400]は、ある iid,iid' が存在して sid'=(π',iid',π,iid) となっていなければ、鍵交換装置[100]は直ちに命令待ち状態となる。
以降、sid'=(π',iid',π,iid) であるとする。
鍵生成装置[400]は、sid =(π,iid,π',iid') として、記憶装置[103]に保存されている状態を参照状態と読み込み手段[402]により参照し、いかなるcont, z[0], z[1] に対しても、状態 (sid,cont,z[0],z[1]) を記憶していなければ、鍵交換装置[100] は直ちに命令待ち状態となる[303]。【００３８】
鍵生成装置[400]は、あるcont, z[0], z[1] に対して、ある状態[403] (sid,cont,z[0],z[1]) を記憶していたとする。鍵生成装置[400]は、貢献データと認証子[408]("検証",Π',(cont,b'),sig' )とを認証装置[104] に入力する。認証装置[104]が"不当"を出力した場合、鍵交換装置[100] は直ちに命令待ち状態となる[303]。【００３９】
鍵生成装置[400]は、記憶装置[103]の中の状態 (sid,cont,z[0],z[1]) を完全に消去し[404]、指示ビット[405]に従い鍵を選択して[406] 交換鍵[407] (sid,z[b']) を出力する。
z[b'] が、鍵交換装置[100] の出力する交換鍵[407]である。
【実施例２】
【００４０】
次に、本発明のシステムの一実施例について説明する。
図５は、本発明に係る鍵交換システムの動作を説明するためのシーケンス図の一例である。
以上説明した鍵交換装置を二つ走らせると、互いに認証しあった鍵を交換することができる。これは次のように確認することができる。【００４１】
鍵交換装置Πは、システムパラメター(q,G,g,Hash,v)が入力302されると起動する。
鍵交換装置Π'は、システムパラメター(q,G,g,Hash,v) が入力302されると起動する。【００４２】
鍵交換装置Πが、鍵交換開始命令、及び相手識別子π' を入力される。
鍵交換装置Πは、乱数を取り込み、手続番号iid [202]を生成し、指示ビットb ∈ [0,1] をランダム生成し、暫定数r ∈ Z/qZ を乱数からランダムに生成し、冪乗数y[b] = grを生成し、y[1-b] ∈ G をランダムに生成する。
鍵交換装置Πは、状態 (iid, Π',y[0],y[1],b,r) を生成して、これを記憶装置[503a]に記憶させる。
鍵交換装置Πは、状態(iid,y[0],y[1])を通信装置[105a]で鍵交換装置Π'に送信する。【００４３】
鍵交換装置Π'が、鍵交換開始命令、及び相手識別子πを入力される。
鍵交換装置Π’は、乱数を取り込み、手続番号iid'[202] を生成し、指示ビットb' ∈ [0,1] をランダム生成し、暫定数r' ∈ Z/qZ を乱数からランダムに生成し、冪乗数y'[b] = gr'を生成し、冪乗数y'[1-b] ∈ G をランダムに生成する。
鍵交換装置Π’は、状態(iid', π,y'[0],y'[1],b',r') を生成して、これを記憶装置[503b]に記憶させる。
鍵交換装置Π’は、状態(iid',y'[0],y'[1]) を鍵交換装置Πに通信装置[105b]で送信する。【００４４】
鍵交換装置Π が、鍵交換装置Π'から状態(iid',y'[0],y'[1]) を通信装置[105a]で受信する。
鍵交換装置Πは、冪乗数y'[0],y'[1] が G の要素であることを確認し、セッション番号 sid =(π, iid,π',iid') を生成し、貢献データ cont =(sid,y[0],y[1],y'[0],y'[1]) を生成する。
鍵交換装置Πは、(cont,b) に対する認証を行い、 sig を得、 c=0,1 に関して、z[c]= Hash(y'[c]r,v) を生成する。
鍵交換装置Πは、状態 (iid, Π', y[0],y[1],b,r) を、状態(sid,cont,z[0],z[1]) に変更する。
鍵交換装置Πは、状態(sid,b,sig) を鍵交換装置Π' に通信装置[105a]で送信する。【００４５】
鍵交換装置Π'が、鍵交換装置Π から状態(iid,y[0],y[1]) を通信装置[105b]で受信する。
鍵交換装置Π’は、冪乗数y[0],y[1] がG の要素であることを確認し、セッション番号sid' =(π', iid',π,iid) を生成し、貢献データ cont' =(sid',y'[0],y'[1],y[0],y[1]) を生成する。
鍵交換装置Π’は、(cont',b') に対する認証を行い、sig' を得、c=0,1 に関して、z'[c] = Hash(y[c]r',v) を生成する。
鍵交換装置Π’は、状態(iid', π, y'[0],y'[1],b',r') を、(sid',cont',z'[0],z'[1]) に変更する。
鍵交換装置Π’は、状態(sid',b',sig') を通信装置[105b]で鍵交換装置Π に送信する。【００４６】
鍵交換装置Πが、通信装置[105a]で鍵交換装置Π' から (sid',b',sig') を受信する。
鍵交換装置Πは、("検証",Π',(cont,b'),sig' ) が正当であることを確認する。
鍵交換装置Πは、状態(sid,cont,z[0],z[1]) を完全に消去し、(sid,z[b']) を通信装置[105a]で鍵交換装置Π’に出力する。【００４７】
鍵交換装置 Π'が、鍵交換装置Π から 状態(sid,b,sig) を通信装置[105b]で受信する。
鍵交換装置Π’は、("検証",Π,(cont',b),sig ) が正当であることを確認する。
鍵交換装置Π’は、状態(sid',cont',z'[0],z'[1]) を完全に消去し、(sid',z'[b])を出力する。【００４８】
ここで、交換した鍵z[b']と 鍵z'[b]とが等しい事を示す。これは、以下の通りに示される。
z[b'] = Hash(y'[b']r,v) 
= Hash((gr')r,v) 
= Hash((gr)r',v)
= Hash(y[b]r',v)
= z'[b]【００４９】
以上に示した通り、鍵交換装置 Π と鍵交換装置 Π' とは同じ鍵を交換することに成功する。上の鍵交換において、 y[1-b], y'[1-b'] が最終的な鍵の値に反映されないため、一見無駄な操作のように見える。しかし、方式の安全性を、方式を破ることの難しさをDiffie-Hellman 判別問題の難しさに帰着させることで証明出来るが、このときの帰着効率を挙げることに効果を発揮する。なお、この帰着効率が高ければ、 Diffie-Hellman 判別問題の難しさと方式の安全性の関係が高いため、方式で使う G をより小さなものとすることができる。【００５０】
この帰着効率が上がる理由は以下の通りである。方式の安全性をDiffie-Hellman判別問題に帰着させるには、Diffie-Hellman判別問題を方式で交換されるデータに埋め込み、攻撃者が鍵を判別できるかで、Diffie-Hellman判別問題を解くことになる。この様にして攻撃者を利用してDiffie-Hellman 判別問題を解くアルゴリズムを「帰着アルゴリズム」と呼ぶこととする。この帰着アルゴリズムは、y[0], y[1] のいずれか、最終的に鍵交換に利用される方に問題を埋め込む必要がある。その一方、鍵交換装置が攻撃を受け、内部の情報を盗まれた場合 r を攻撃者に提出する必要がある。【００５１】
もし、 y[0] のみを使って鍵交換を行う意場合、r を出すか問題を埋め込むかは、背反する操作となる。故に、予め攻撃者がどちらを選ぶか予想しなければならない。この予想が当る確率が低いために、帰着効率が下がるのである。【００５２】
一方、本発明の方法では、冪乗数y[0], y[1] の片方に問題を埋め込み、他方に対応する r を準備する。そして、内部状態を求められた場合は r を、鍵交換が遂行されれば埋め込まれた方を利用するのである。本来両者は同じものを利用せねばならないのであるが、攻撃者は冪乗数y[0], y[1] から指示ビットb を推測できないことを用いて、この両者が異なることを攻撃者に隠すことができる。
【実施例３】
【００５３】
次に、本発明の鍵交換プログラムの一実施例について説明する。
以上で説明した本発明の鍵交換システムは、コンピュータで鍵交換処理を実行させる鍵交換プログラムによって実現されている。コンピュータとしては、例えばパーソナルコンピュータやワークステーションなどの汎用的なものが挙げられるが、本発明はこれに限定されるものではない。【００５４】
二つの鍵交換装置Π，Π’が互いに通信して同一の鍵を共有する鍵交換プログラムであって、コンピュータに、
(1)鍵交換装置Πが、システムパラメター(q,G,g,Hash,v)が入力されると起動する手順、
(2)鍵交換装置Π'が、システムパラメター(q,G,g,Hash,v) が入力されると起動する手順、
(3)鍵交換装置Πが、鍵交換開始命令及び相手識別子π' が入力されると、乱数を取り込み、手続き番号iid を生成し、指示ビットb ∈[0,1] をランダム生成し、暫定数r ∈ Z/qZ を乱数からランダムに生成し、冪乗数y[b] = grを生成し、冪乗数y[1-b] ∈ G をランダムに生成、状態(iid, π',y[0],y[1],b,r) を生成してこれを記憶し、前記状態(iid,y[0],y[1]) を鍵交換装置Π' に送信する手順、
(4)鍵交換装置Π'が、鍵交換開始命令及び相手識別子πが入力されると、乱数を取り込み、手続き番号iid' を生成し、指示ビットb' ∈[0,1] をランダム生成し、暫定数r' ∈ Z/qZ を乱数からランダムに生成し、y'[b] = gr'を生成し、冪乗数y'[1-b] ∈ G をランダムに生成し、状態 (iid', π,y'[0],y'[1],b',r') を生成してこれを記憶し、前記状態(iid',y'[0],y'[1]) を鍵交換装置Πに送信する手順、
(5)鍵交換装置Πが、鍵交換装置Π' から前記状態(iid',y'[0],y'[1]) を受信すると、y'[0],y'[1] が G の要素であることを確認し、セッション番号 sid =(π, iid,π',iid') を生成し、貢献データcont(=sid,y[0],y[1],y'[0],y'[1]) を生成し、貢献データ(cont,b) に対する認証を行って認証子sigを得、c=0,1 に関して、鍵候補z[c] = Hash(y'[c]r,v) を生成し、前記状態 (iid,π', y[0],y[1],b,r) を、 (sid,cont,z[0],z[1]) に変更し、前記状態(sid,b,sig) を鍵交換装置Π' に送信する手順、
(6)鍵交換装置Π'が、鍵交換装置Πから前記状態(iid,y[0],y[1]) を受信すると、y[0],y[1] が G の要素であることを確認し、セッション番号 sid'(=π', iid',π,iid) を生成し、貢献データ cont'(=sid',y'[0],y'[1],y[0],y[1]) を生成し、(cont',b') に対する認証を行ってセッション番号sig'を得、c=0,1 に関して、鍵候補z'[c] = Hash(y[c]r',v) を生成し、状態 (iid',π,y'[0],y'[1],b',r') を、状態(sid',cont',z'[0],z'[1]) に変更し、状態(sid',b',sig') を鍵交換装置Πに送信する手順、
(7)鍵交換装置Πが、鍵交換装置Π' から状態(sid',b',sig')を受信すると、("検証",π',(cont,b'),sig' ) が正当であることを確認し、状態 (sid,cont,z[0],z[1]) を完全に消去して、(sid,z[b']) を出力する手順、
(8)鍵交換装置 Π'が、鍵交換装置Πから状態(sid,b,sig) を受信すると、("検証",π,(cont',b),sig ) が正当であることを確認し、状態 (sid',cont',z'[0],z'[1]) を完全に消去し、状態(sid',z'[b]) を出力する手順を実行させることを特徴とする。【００５５】
これにより、鍵交換プログラムが実行可能なコンピュータ環境さえあれば、どこにおいても本発明の鍵交換システムを実現することができる。【００５６】
このような鍵交換プログラムは、コンピュータに読み取り可能な記憶媒体に記憶されていてもよい。
ここで、記憶媒体としては、例えば、CD-ROM（Compact Disc Read Only Memory）、フレキシブルディスク（FD）、CD-R（CD Recordable）、DVD（Digital Versatile Disk）などのコンピュータで読み取り可能な記憶媒体、フラッシュメモリ、RAM（Random Access Memory）、ROM（Read Only Memory）、FeRAM（強誘電体メモリ）等の半導体メモリ、HDD（Hard Disc Drive）が挙げられる。【００５７】
なお、上述した実施例は、本発明の好適な実施例の一例を示すものであり、本発明はそれに限定されることなく、その要旨を逸脱しない範囲内において、種々変形実施が可能である。【００５８】
この出願は、２００８年７月２日に出願された日本出願特願２００８−１７３４０４を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【産業上の利用可能性】
【００５９】
本発明は、二つの鍵交換装置が互いに通信して同一の鍵を共有するシステムに利用できる。
【符号の説明】
【００６０】
１００    鍵交換部
１０１    入力装置
１０２    乱数入力装置
１０３    認証装置
１０４    記憶装置
１０５    通信装置
１０６    出力装置
Π、Π’    鍵交換装置
【図１】
2010001957.tif 000003
【図２】
2010001957.tif 000004
【図３】
2010001957.tif 000005
【図４】
2010001957.tif 000006
【図５】
2010001957.tif 000007
【図６】
2010001957.tif 000008
【図７】
2010001957.tif 000009
【図８】
2010001957.tif 000010
【国際調査報告】
2010001957.tif 000011
2010001957.tif 000012
2010001957.tif 000013
2010001957.tif 000014