【手続補正書】
【提出日】平成19年8月28日(2007.8.28)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
暗号化装置および復号化装置を備え、任意の文字列を公開鍵として用いることのできるIDベース署名および暗号化システムにおける秘密鍵生成装置であって、
システム全体で用いる公開パラメータ及びマスター鍵を生成するとともに、
利用者からの要求に応じて前記マスター鍵を用いて利用者の公開鍵に対応する秘密鍵を生成して前記要求元の利用者に発行する秘密鍵生成発行手段と、
前記秘密鍵生成手段において生成した公開パラメータを公開するパラメータ公開手段と、を備え、
前記秘密鍵生成発行手段は、
前記公開パラメータに、選択した位数qの群の元Pを用いて予め計算したg=e(P,P)を加え（eはペアリングと呼ばれる双線形写像）、
前記群の2つの元P1、P2を、前記位数q未満であって前記位数ｑと互いに素な正の整数からなる集合Zq*に含まれる前記マスター鍵の一部である乱数s1、s2を用いて、P1=s1P、P2=s2Pと定義し、前記秘密鍵として(s1+us2)-1Pを算出すること
を特徴とする秘密鍵生成装置。
【請求項２】
請求項１記載の秘密鍵生成装置であって、
前記秘密鍵生成発行手段は、それぞれ、前記q、P、g、P1、P2、s1、s2を算出するために、
入力された正の整数kに対してkビットの素数qをランダムに生成する素数生成手段と、
前記位数qの2つの群G1、G2を生成する群生成手段と、
前記群G1の元Pを生成する元生成手段と、
0<s1、s2<qを満たす乱数s1、s2を生成する乱数生成手段と、
P1=s1P及びP2=s2Pの計算を行う群演算手段と、
ペアリングe:G1×G1→G2を選択するペアリング選択手段と、
g=e(P,P)を計算するペアリング演算手段と、
ハッシュ関数H1:{0,1}*→Zq*およびH2:G2→{0,1}*を選択するハッシュ関数選択手段と、
関数f: Zq*→Zq*を選択する関数選択手段と、
関数演算を行う関数演算手段と、
剰余計算を行う基本演算手段と、を備えること
を特徴とする秘密鍵生成装置。
【請求項３】
請求項２記載の秘密鍵生成装置であって、
前記公開パラメータとして、<q, G1, G2, e, g, P1, P2, H1, H2, f>を公開し、
前記マスター鍵として、<P, s1, s2>を保管すること
を特徴とする秘密鍵生成装置。
【請求項４】
請求項２記載の秘密鍵生成装置であって、
前記公開鍵をIDとした場合、u=H1(ID)としてdID=(s1+us2)-1Pが計算できない場合、dID=(s1+f(u)s2)-1Pを利用者の秘密鍵として生成すること
を特徴とする秘密鍵生成装置
【請求項５】
請求項１から４いずれか１項記載の秘密鍵成装置を備え、任意の文字列を公開鍵として用いることのできるIDベース署名及び暗号化システムにおける暗号化および署名生成装置であって、
前記秘密鍵生成装置において公開されている公開パラメータと受信者の公開鍵とを用いて行うメッセージの暗号化処理、および、前記公開パラメータと前記秘密鍵生成装置により発行された利用者の秘密鍵とを用いて行う署名生成処理の少なくとも１の処理を行う暗号化および署名生成手段を備え、
前記暗号化および署名生成手段は、
前記公開パラメータ生成時に選択した位数qの群の元PIDと公開鍵とを、前記位数q以下であって前記位数ｑと互いに素な正の整数からなる集合Zq*に含まれるuと前記群に含まれる2つの元P1、P2とを用いて、PID=P1+uP2を計算することにより対応させること
を特徴とする暗号化および署名生成装置。
【請求項６】
請求項５記載の暗号化および署名生成装置であって、
前記暗号化および署名生成手段は、
前記群上の点uを、u=H1(ID)（IDは公開鍵）とし、
前記PIDが前記群上の単位元となる場合、前記PID=P1+f(u)P2（ｆはZq*からZq*への関数）を計算させることにより、前記位数qの群の元PIDと公開鍵とを対応させること
を特徴とする暗号化および署名生成装置。
【請求項７】
請求項５または６記載の暗号化および署名生成装置であって、
前記暗号化および署名生成手段は、
乱数を生成する乱数生成手段と、
群演算を行う群演算手段と、
ハッシュ値の計算を行うハッシュ値計算手段と、
排他的論理和の計算を行う排他的論理和計算手段と、
関数演算を行う関数演算手段と、を備えること
を特徴とする暗号化および署名生成装置。
【請求項８】
請求項１から４いずれか１項記載の秘密鍵成装置および請求項５から７いずれか１項記載の暗号化および署名生成装置とを備え、任意の文字列を公開鍵として用いることのできるIDベース署名及び暗号化システムにおける復号および署名検証装置であって、
前記秘密鍵生成装置において公開された公開パラメータと前記秘密鍵生成装置により発行された利用者の秘密鍵とを用いて行う、前記暗号化および署名生成装置において暗号化されたメッセージの復号処理、および、前記公開パラメータと送信者の公開鍵とを用いて行う、前記暗号化および署名生成装置において署名生成処理を施されたメッセージの署名検証処理の少なくとも１の処理を行う復号および署名検証手段を備え、
前記復号および署名検証手段は、
前記公開パラメータ生成時に選択した位数qの群の元PIDと公開鍵とを、前記位数q以下であって前記位数ｑと互いに素な正の整数からなる集合Zq*に含まれるuと前記群に含まれる2つの元P1、P2とを用いて、PID=P1+uP2を計算することにより対応させること
を特徴とする復号および署名検証装置。
【請求項９】
請求項８記載の復号および署名検証装置であって、
前記PIDが前記群上の単位元となる場合、前記PID=P1+f(u)P2（ｆはZq*からZq*への関数）を計算させることにより、前記位数qの群の元PIDと公開鍵とを対応させること
署名検証装置。
【請求項１０】
任意の文字列を公開鍵として用いることのできるIDベース署名及び暗号化システムであって、
システム全体で用いる公開パラメータ及びマスター鍵を生成し、前記公開パラメータを公開するとともに、利用者からの要求に応じて前記マスター鍵を用いて利用者の公開鍵に対応する秘密鍵を生成し、要求元の利用者に発行する秘密鍵生成装置と、
前記秘密鍵生成装置において公開されている公開パラメータと受信者の公開鍵とを用いて行うメッセージの暗号化および前記公開パラメータと前記秘密鍵生成装置により発行された利用者の秘密鍵とを用いて行う署名生成の少なくとも１の処理を行う暗号化および署名生成装置と、
前記秘密鍵生成装置において公開された公開パラメータと前記秘密鍵生成装置により発行された利用者の秘密鍵とを用いて行う、前記暗号化および署名生成装置において暗号化されたメッセージの復号、および、前記公開パラメータと送信者の公開鍵とを用いて行う、前記暗号化および署名生成装置において署名生成されたメッセージの署名検証の少なくとも１の処理を行う復号および署名検証装置とを備え、
前記秘密鍵生成装置は、
前記公開パラメータに、位数qの群の元Pを選択し、予め計算したg=e(P,P)を加え（eはペアリングと呼ばれる双線形写像）、
前記群の2つの元P1、P2を、前記位数q未満であって前記位数ｑと互いに素な正の整数からなる集合Zq*に含まれる前記マスター鍵の一部である乱数s1、s2を用いて、P1=s1P、P2=s2Pと定義し、前記秘密鍵を、(s1+us2)-1Pと算出し、
前記暗号化および署名生成装置と前記復号および署名検証装置とは、
前記公開鍵と前記群の元PIDとを、前記集合Zq*に含まれる任意の文字列u及び前記2つの元P1、P2を用いて、PID=P1+uP2を計算することにより対応させること
を特徴とするIDベース署名及び暗号化システム。
【請求項１１】
任意の文字列を公開鍵として用いることのできるIDベース署名及び暗号化方法であって、
システム全体で用いる公開パラメータ及びマスター鍵を生成し、前記公開パラメータを公開する公開パラメータ及びマスター鍵生成ステップと、
利用者からの要求に応じて前記マスター鍵を用いて利用者の公開鍵に対応する秘密鍵を生成し、要求元の利用者に発行する秘密鍵発行ステップと、
前記公開パラメータと受信者の公開鍵とを用いて行うメッセージの暗号化処理および前記公開パラメータと前記利用者の秘密鍵とを用いて行う署名生成処理の少なくとも１の処理を行う暗号化および署名生成ステップと、
前記公開パラメータと前記利用者の秘密鍵とを用いて行う、前記暗号化されたメッセージの復号処理、および、前記公開パラメータと送信者の公開鍵とを用いて行う、前記署名生成処理を施されたメッセージの署名検証処理の少なくとも１の処理を行う復号および署名検証ステップとを備え、
前記公開パラメータ及びマスター鍵生成ステップにおいて、
前記公開パラメータに、位数qの群の元Pを選択し、予め計算したg=e(P,P)を加え（eはペアリングと呼ばれる双線形写像）、
秘密鍵発行ステップにおいて、
前記群の2つの元P1、P2を、前記位数q以下であって前記位数ｑと互いに素な正の整数からなる集合Zq*に含まれる前記マスター鍵の一部である乱数s1、s2を用いて、P1=s1P、P2=s2Pと定義し、前記秘密鍵を、(s1+us2)-1Pと算出し、
前記暗号化および署名生成ステップと前記復号および署名検証ステップとにおいて、
前記公開鍵と前記群の元PIDとを、前記集合Zq*に含まれる任意の文字列u及び前記2つの元P1、P2を用いて、PID=P1+uP2を計算することにより対応させること
を特徴とするIDベース署名及び暗号化方法。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００３４
【補正方法】変更
【補正の内容】
【００３４】
ここでは、pをp=2  mod  3, q>3を満たす素数qに対してp=lq-1を満たす素数とし、qはlを割り切らないとする。Eを有限体Fp上定義された楕円曲線y2=x3+1とし、E(Fp)をE上の点から構成される群とする。G1をE(Fp)の位数qの部分群とする。このとき、ハッシュ関数H1’:{0,1}＊→Fpが存在しているとしてH0:{0,1}＊→G1を構成する。
入力:ID∈{0,1}＊
出力:QID∈G1
処理手順：
1. y0=H1’(ID)を計算する。
2. x0=(y02-1)1/3=(y02-1)(2p-1)/3∈Fpを計算する。
3. Q=(x0, y0)∈E(Fp)とおく。
4. QID=lQ∈G1を計算する。
5. QIDを出力する。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００３８
【補正方法】変更
【補正の内容】
【００３８】
具体的には、任意の文字列を公開鍵として用いることのできるIDベース署名及び暗号化システムであって、システム全体で用いる公開パラメータ及びマスター鍵を生成し、前記公開パラメータを公開するとともに、利用者からの要求に応じて前記マスター鍵を用いて利用者の公開鍵に対応する秘密鍵を生成し、要求元の利用者に発行する秘密鍵生成装置と、前記秘密鍵生成装置において公開されている公開パラメータ、前記秘密鍵生成装置から発行を受けた利用者の秘密鍵、および、受信者の公開鍵を用いてメッセージ暗号化および署名生成の少なくとも１の処理を行う暗号化および署名生成装置と、前記秘密鍵生成装置において公開された公開パラメータ、前記秘密鍵生成装置から発行を受けた利用者の秘密鍵、および、送信者の公開鍵を用いて、前記暗号化装置において、暗号化および署名生成の少なくとも１の処理を施されたメッセージについて、前記施された処理に応じて、復号および署名検証の少なくとも１の処理を行う復号および署名検証装置とを備え、前記秘密鍵生成装置は、前記公開パラメータに、位数qの群の元Pを選択し、予め計算したg=e(P,P)を加え（eはペアリングと呼ばれる双線形 写像）、前記群の2つの元P1、P2を、前記位数q以下であって前記位数ｑと互いに素な正の整数からなる集合Zq*に含まれる前記マスター鍵の一部である乱数s1、s2を用いて、P1=s1P、P2=s2Pと定義し、前記秘密鍵を、(s1+us2)-1Pと算出し、前記暗号化および署名生成装置と前記復号および署名検証装置とは、前記公開鍵と前記群の元PIDとを、前記集合Zq*に含まれる任意の元u及び前記2つの元P1、P2を用いて、PID=P1+uP2を計算することにより対応させることを特徴とするIDベース署名及び暗号化システムを提供する。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００５６
【補正方法】変更
【補正の内容】
【００５６】
記憶部109は、演算部112で演算を行う際に必要となる中間データを一時保管する中間データ保持部114と、マスター鍵を公開パラメータと共に保管するマスター鍵保持部115とを備える。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００６４
【補正方法】変更
【補正の内容】
【００６４】
制御演算部132は、利用者Ａから署名、暗号化対象データや認証情報などの入力を受け付ける入出力部134と、暗号化および署名生成装置103全体を制御する制御部135と、暗号化、署名生成等を行う演算部136と、秘密鍵発行装置102、復号および署名検証装置104との間で、公開パラメータ、秘密鍵、暗号化データや署名データの入出力を行う外部入出力部137とを備える。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００７７
【補正方法】変更
【補正の内容】
【００７７】
暗号化および/または署名付与処理に先立ち、暗号化及び署名生成装置103の制御部135は、通信回線130または記憶媒体を利用して、パラメータ公開装置106で公開されている公開パラメータを、外部入出力部137を介して入手すると、データ保持部139に保管する。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００７９
【補正方法】変更
【補正の内容】
【００７９】
そして、制御部135は、入出力部134より入力された処理内容および対象データを中間データ保持部129に保持し、処理内容で示された指示に従って、演算部127に暗号化および/または署名付与の処理を行わせ、その演算結果を外部入出力部137より、復号及び署名検証装置104に、通信路141または記憶媒体を用いて送出する。なお、暗号化および/または署名付与処理は、後述する図7に示す処理に従って行われる。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】０１０５
【補正方法】変更
【補正の内容】
【０１０５】
次に、上記図12のステップ1207で行われる署名検証処理について説明する。図14は、署名検証処理を説明するためのフローチャートである。
<ステップ1401>
ハッシュ関数演算部1104において、署名者の公開鍵IDAを用いて、u=H1(IDA)を計算する。
<ステップ1402>
群演算部1102において、公開パラメータparamsを用いて、PA=P1+uP2を計算する。
<ステップ1403>
群演算部1102において、算出したPAがG1の単位元Oであるか否かを判別する。PAがG1の単位元Oであればステップ1404に進み、そうでなければ、ステップ1405に進む。
<ステップ1404>
PAがG1の単位元Oであれば、関数演算部1107において、公開パラメータparamsに含まれる関数ｆを用いて、uをf(u)に置き換え（u=f(u)と設定し直し）、ステップ1402に戻る。
<ステップ1405>
PAがG1の単位元Oでなければ、ハッシュ関数演算部1104において、公開パラメータparamsに含まれるハッシュ関数H1および署名S=(M,U,V)を用いて、h=H1(M||U)を計算する。
<ステップ1406>
群演算部1102、ペアリング演算部1103において、公開パラメータparams、署名等を用いてUgrとe(PA,V)とを計算し、署名検証部1106において、Ugr=e(PA,V)が成立するか否か判別することにより、署名検証を行う。成立すれば署名検証成功であり、ステップ1407に進み、成立しなければ署名検証失敗であり、ステップ1408に進む。
<ステップ1407>
成立した場合、入出力部1101からacceptを出力し終了する。
<ステップ1408>
不成立の場合、入出力部1101からrejectを出力し終了する。