混成署名方式
【課題】メッセージにデジタル形式で署名する方法及び装置を提供する。
【解決手段】メッセージが認証中に復元される不可視部分である第1部分と認証アルゴリズムへの入力として必要な可視部分である第2部分とに分割された署名方式が提供される。第1署名成分は、第1部分のみを暗号化して生成される。第1成分と可視部分を組合せてこれを暗号化的にハッシュすることにより中間成分が生成される。次に、中間成分を用いて第2署名成分が生成され、この署名は可視部分を有する第1および第2成分を備える。署名の認証は、メッセージの不可視部分のみから得られた第1成分を、可視部分と組合せ、この組合せのハッシュを生成する。不可視部分に関連したビットストリングを生成するために、算出されたハッシュが、一般に公開された情報と共に使用される。必要な冗長性が存在する場合、署名が承認され、復元されたビットストリングと可視部分からメッセージが再構成される。
【解決手段】メッセージが認証中に復元される不可視部分である第1部分と認証アルゴリズムへの入力として必要な可視部分である第2部分とに分割された署名方式が提供される。第1署名成分は、第1部分のみを暗号化して生成される。第1成分と可視部分を組合せてこれを暗号化的にハッシュすることにより中間成分が生成される。次に、中間成分を用いて第2署名成分が生成され、この署名は可視部分を有する第1および第2成分を備える。署名の認証は、メッセージの不可視部分のみから得られた第1成分を、可視部分と組合せ、この組合せのハッシュを生成する。不可視部分に関連したビットストリングを生成するために、算出されたハッシュが、一般に公開された情報と共に使用される。必要な冗長性が存在する場合、署名が承認され、復元されたビットストリングと可視部分からメッセージが再構成される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、メッセージにデジタル形式で署名する方法および装置に関するものである。
【背景技術】
【０００２】
デジタル署名は、メッセージの発信者とその内容を認証するべく、通信者が作成したメッセージに署名するために使用される。その基本的な方法として、メッセージのデジタル署名は、発信者の秘密鍵を用いて署名を行うことで生成される。次に、発信者の公開鍵を用いてこのメッセージが復元される。この基本形態の特質が異なる応用が数多く提案されている。一般にデジタル署名方式は、2つの一般的な区分、すなわちビットデータが付加されるデジタル署名と、メッセージ復元を行うデジタル署名とに分けられると考えられる。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
ビットデータが付加されるデジタル署名は、認証アルゴリズムに入力する際に、署名したメッセージが必要であるという事実に基づいて分類されている。非常に人気はあるが（DSSとECDSAはこの機構の例である）、このデジタル署名では他の方法ほど十分な帯域幅効率を得ることができない。
【０００４】
メッセージ復元を行うデジタル署名は、認証アルゴリズムに入力する際に、メッセージが不要であるという事実に基づいて分類されている。メッセージ復元方式の1つの問題は、合法的に署名されたメッセージをランダムビットストリングと区別する適切な冗長機能を定義することにより、依然として無くならない署名偽造を防ぐことができないことである。
【０００５】
多くの実用的なアプリケーションにおいて、署名するデータは、ある程度の固有の冗長性を有している。例えば、その日に4バイトのデータが保存されても、実際には3バイトで十分なので、このフィールドには8ビットの冗長性がある。セキュリティを万全にするには、メッセージ内に所定の冗長性を付与する必要があり、これによって帯域幅効率が減少してしまう。
【０００６】
帯域幅効率を向上させるために、メッセージを2つの成分、すなわち、不可視成分と可視成分に分割することが知られている。不可視成分は認証中に復元され、可視部分は復元処理への入力として使用される。不可視成分は、無くならない署名偽造に対抗するのに十分な冗長性を有していなければならず、また、これによって処理ができない場合には、メッセージにビットを追加する必要がある。このような方式を実現するために提案された方法の1つであるISO9796 Part 2では、不可視成分は、形式DESR[H//SHA1(V)//IA]の署名成分cを生成するために使用されており、ここで、
Hは不可視成分、
Vは可視成分、
IAは署名者の識別子、
SHA1(V)は可視成分の暗号化ハッシュ、
DESRはビットストリングの暗号化である。
しかし、この方式には、cが少なくともSHA1(V)ビット長のビット内のビット数であり、これが署名に含まれているため、必要な帯域幅効率が得られないという欠点がある。さらに、この方式では、その後、署名成分に含まれているという理由から値cがハッシュされるため、2つのハッシュ動作を呼出す必要がある。アプリケーションによっては、この計算の複雑性が不適切であることもある。
【課題を解決するための手段】
【０００７】
従って、本発明の目的は、上述の欠点を克服または軽減した署名方式を提供することである。
【０００８】
一般に、本発明の1局面によれば、メッセージが、認証中に復元される、不可視の第1部分と、認証アルゴリズムへの入力として必要な、可視の第2部分とに分割される署名方式が提供される。第1署名成分は、第1部分のみを暗号化して生成される。第1成分と可視部分を組合せ、これを暗号化的にハッシュすることにより、中間成分が生成される。次に、中間成分を用いて第2署名成分が生成され、この署名は、可視部分を有する第1および第2成分を備えている。
【０００９】
第1部分だけから第1成分を生成する、必要な帯域幅を減らし、計算を簡素化する。第1および第2部分の相対的なサイズは、アプリケーション自体によって決定される。この方法では、初期の分割しない方式とは対照的に、冗長機能をアプリケーションに依存させることができる。
【００１０】
メッセージの復元は、送信者の署名と公開鍵を用いて実現することができる。
【００１１】
本発明の他の局面によれば、不可視および可視部分に分割されたメッセージの署名の認証が提供される。認証は、メッセージの不可視部分のみから得られた第1成分を可視部分と組合せて、この組合せのハッシュを生成する。算出されたハッシュは、一般に公開された情報と共に、不可視部分と関連したビットストリングを生成するために使用される。必要な冗長性が存在する場合には、署名が承認され、復元されたビットストリングと可視部分からメッセージが再構成される。
（項目１） データ伝送システムにおいて２人の通信者で交換されるメッセージにデジタル形式で署名する方法であって、前記方法が、
前記メッセージを1対のビットストリングに細分するステップと、
第1署名成分を算出するために、前記ビットストリングの1つを利用するステップと、
前記第1署名成分と他のビットストリングとから、中間署名成分を生成するステップと、
第2署名成分を得るために、前記中間成分を利用するステップと、
署名を得るために、前記第1および第2成分を前記ビットストリングの前記他方と組合せるステップと、
を有することを特徴とする方法。
（項目２） 前記ビットストリングの1つの冗長性が、前記第1署名成分を算出する前に、所定のレベルと比較されることを特徴とする項目1に記載の方法。
（項目３） 前記所定のレベル以上のレベルに前記冗長性が付与されることを特徴とする項目2に記載の方法。
（項目４） 前記冗長性を付与するために、前記ビットストリングの１つにデータが追加されることを特徴とする項目3に記載の方法。
（項目５） 前記追加されたデータを示すために、前記ビットストリングの１つにインジケータが含まれていることを特徴とする項目4に記載の方法。
（項目６） 前記第2成分が、前記第1成分と前記別のビットストリングをハッシュすることにより生成されることを特徴とする項目1に記載の方法。
（項目７） 暗号化されたビットストリングの1つと、前記他のビットストリングとを備えた少なくとも1つの成分を有する署名からの1対の前記ビットストリングに分割されたメッセージを確認する方法であって、前記方法が、
前記1つの成分を前記別のビットストリングと組合せるステップと、
署名者の公開された情報を使って、前記組合せから前記1つのビットストリングを復元するステップと、
前記復元された1つのビットストリングを、所定の特性について調べるステップと、
を含むことを特徴とする方法。
（項目８） 前記1つの成分と前記別のビットストリングの前記組合せが、前記1つの成分と前記別のビットストリングの組合せをハッシュするステップを含むことを特徴とする項目7に記載の方法。
（項目９） 前記所定の特性が、前記復元したビットストリングの１つが冗長性であることを特徴とする項目8に記載の方法。
（項目１０） 前記署名が、前記1つの成分と前記別のビットストリングの組合せから得られた2成分を有し、前記ビットストリングの１つが、前記第2成分を使って復元されることを特徴とする項目9に記載の方法。
【図面の簡単な説明】
【００１２】
【図１】データ通信システムの概略図である。
【図２】署名の生成を示すフローチャートである。
【図３】図2の署名の認証を示すフローチャートである。
【図４】署名生成の他の実施の形態を示すフローチャートである。
【発明を実施するための形態】
【００１３】
次に、添付した図面を参照しながら本発明の実施の形態を説明する。
【００１４】
図1を参照すると、データ通信システムには、２人の通信者10、12がおり、通信チャネル14を介してメッセージMを交換している。通信者10、12の各人は、各暗号化装置16、18と、メッセージMを生成、受信するための各端末20、22とを携帯している。各暗号化装置16、18は、公開鍵にセッション鍵の生成ができるようにし、また、このセッション鍵を用いてメッセージの暗号化および解読ができるようにする、または秘密鍵を用いてメッセージへ署名ができるようにする公開鍵暗号化方式を実現する。秘密鍵を用いたメッセージへの署名は、関連する公開鍵を用いて復元することができる。このような方式の一般的な実現と、その動作原理がよく知られている。汎用コンピュータの制御下でプロトコルを実現するために、または予めプログラムされた命令としてチップセット上で実現するために、暗号化方式がデータキャリアから暗号化装置にロードされる。
【００１５】
後述の好適な実施の形態では、暗号化方式は、有限群内の離散対数問題の困難さに基づくものであり、通常は楕円曲線の暗号系と呼ばれる、有限体における楕円曲線の点に関して定義された代数系で実現される。しかし、提案されている署名方式は、あらゆる有限群におけるあらゆるＥＩＧａｒｍａｌ署名に適用することができる。
【００１６】
このような楕円曲線暗号系の領域パラメータは、形式y2=x3+dx+cの曲線およびシードポイントＰである。一方の通信者は、0<a<n（ｎは点Ｐのオーダーである）の専用鍵ａと、対応する公開鍵QA=aPとを有する。公開鍵は、ゴーストラインによって通信者10、12と通信するように示されている認証機関24に保持することができる。
【００１７】
通信者10、12によって生成されたメッセージＭは、２ビット文字列ＨおよびＶに分割される（すなわち、M=H//V）。Ｈは、不可視であり、認証処理中に復元されるビット文字列であり、Ｖは、やはり署名されるが、認証処理への入力として必要とされる２ビット文字列である。
【００１８】
署名生成アルゴリズムは、図２のフローチャートに示されている。最初、ビット文字列Ｈが調べられ、無くならない偽造を防止するのに十分な所定の値を超える冗長性を有しているかどうかが判定される。メッセージＭを生成する最初のデータが十分な冗長性を有していることがこの検査によって判定された場合、Ｈはこのデータのサブセットに過ぎない。所定の冗長性を有していない場合、０の追加バイトなど人為的に付加された冗長性を有するようにＨを変更することができる。
【００１９】
一例として、セキュリティ保護上の理由で８０ビットの冗長性が所定の下限であることが決定されているものとする。ビット文字列Ｈが固有の冗長性を有していない場合、最大で１０バイト分の０を追加する必要がある。メッセージを復元できるようにするために、追加された０のバイト数を示すインジケータが、好適にはＨまたはＶの先頭バイトとして付加される。値は０ないし１０であるので、インジケータとしては４ビットのバイトで十分であり、したがって、このビット文字列は追加の４ビットの冗長性を有する。ｔが、追加できる冗長バイトの数である場合、このデータは基本的に、少なくとも80-8tビットの冗長性を有していなければならない。
【００２０】
通信者10は、メッセージM=H//Vに署名するために、暗号化装置14で0<k<nのランダムな整数ｋを発生する。次いで、通信者10は、ｋを使用してランダムな点の値R=kPを算出する。
【００２１】
次いで、c=SKER(H)にのみなるような値ｃがビット文字列Ｈから算出される。SKERは、ランダムな点Ｒから得られる鍵の制御下での対称鍵アルゴリズムを指す。これは、ハッシュ関数などの関数をＲに適用するか、あるいはＲを丸めるか、あるいは１つの座標、たとえば、ｘ座標を鍵として使用することによって得ることができる。Ｈが、Ｒから得られた鍵よりも小さい場合、１つの可能なSKEは、単にＨをXORし、Ｒから得られた鍵からビットを丸めることである。これは実際上、１回限りの暗号化通信方式である。Ｈが鍵よりも大きい場合、DESベースのアルゴリズムを使用するか、あるいは単にＨを用いて鍵を繰り返しXORすることが可能である。
【００２２】
ビット文字列Ｖを使用して、c’=SHA1(c//V)になるように中間成分c’が算出される。この場合、SHA1は、暗号による安全なハッシュ・アルゴリズムである。証明書などの追加情報または通信者10の識別情報が好ましい場合は、そのような情報を、ハッシュされた値c’に組み込むことができる。
【００２３】
署名成分ｃは、不可視部分Ｈのビット単位暗号であるので、この部分と同じ長さであり、かつ中間成分c’は単一のハッシュ演算を用いて得られることに留意されたい。
【００２４】
次いで、既知のＥＩＧａｍａｌ式のいずれかを使用して、通信者10が利用できる値から署名成分が算出される。従来の数式にはSchnorr署名アルゴリズムがあり、この場合、s=c’a+K(mod n)が成立する。次いで、成分（s、c、V）から署名が生成され、通信者12に転送される。
【００２５】
通信者12による署名の認証は、Schnorr署名に関する図３に示されているように対応するアルゴリズムを適用することによって行われる。通信者12は最初、通信者10の公開鍵QAの真正なコピーを認証機関24から得る。次いで、通信者12は、値c”=SHA1(c//V)を算出し、署名内の利用可能な情報、すなわちs、c、Vとシステムのドメインパラメータとから、値
X=sP
Y=c”QA
Z=X-Y
を得る。次いで、H’=SKEz(c)になるように点Ｚから得られた鍵の制御下での対称鍵アルゴリズムを、受信された署名成分ｃに適用することによって、ビット文字列H’が復元される。ビット文字列H’が調べられ、必要な冗長性を有しているかどうかが判定され、有している場合、通信者12はＭの署名を承認し、メッセージをH’//Vとして再構成する。
【００２６】
メッセージＭは分割されているので、必要な冗長性を有している必要があるのは一方の部分Ｈだけである。他方の部分Ｖは、暗号化しないで送信され、元のデータのデータ構造を保持し、それによって帯域幅効率を向上させることができる。
【００２７】
実際的でありかつ商業的に有益であるこの方式の他の特徴は、ｃに符号化されている情報を利用できるのが、通信者10の公開鍵QAを有する人だけであることである。Ｖに含まれているデータはすべての人が利用することができる。通信者10が、QAを有さない人から不可視にすることを望む情報があり、この場合、送信者、すなわち通信者10はこの情報をビット文字列Ｈに含める。
【００２８】
たとえば、メールに課された料金を認証するために署名が使用されるある応用例では、差出人は、いくつのメールを送ったかを受取人が知ることを望まない場合がある。（料金を検証し、したがってこの情報を必要とする）郵便局は差出人の公開鍵を有し、検証時にこの情報を復元することができるが、受取人は、差出人の公開鍵を有さない場合には復元することができない。
【００２９】
もちろん、差出人の公開鍵QAが印に含まれている場合、受取人もこれを利用することができる。あるいは、受取人が認証機関の公開鍵を有する場合にのみ復元することのできる証明書に差出人の公開鍵を含めることができる。これが一般には利用できない場合、Ｈの内容は受取人から不可視にされる。
【００３０】
上述したように、他の形式の署名式を使用することができる。図４のフローチャートに示した他の実施の形態では、ECDSA規格と同様な署名式が使用されている。通常、このような構成では、
・R=kP
・c=DESR(M)
・r’=SHA1(c)
・s=k-1{SHA1(c//IDA)+ar’}mod n（IDAは差出人の識別子である）であり、
・署名は(s,c)である。
この方式は、前述の混成方式と共に使用される際には、
・R=kP
・c=DESR(M)
・r’=SHA1(c)
・s=k-1{SHA1(c//V)+ar’}modnであり、
・署名が(s,c,V)になるように変更される。
したがって、この場合も、第１の成分ｃを生成するために使用されるのはメッセージの一部Ｈだけであるので、指定された冗長性を必要とするのはこの部分だけである。メッセージのバランスをとるには、低減された冗長性を使用して帯域幅効率を維持することができる。
【００３１】
修正された方式に関する検証は、部分的なメッセージ復元および必要な冗長性に適合するように変更される。
【技術分野】
【０００１】
本発明は、メッセージにデジタル形式で署名する方法および装置に関するものである。
【背景技術】
【０００２】
デジタル署名は、メッセージの発信者とその内容を認証するべく、通信者が作成したメッセージに署名するために使用される。その基本的な方法として、メッセージのデジタル署名は、発信者の秘密鍵を用いて署名を行うことで生成される。次に、発信者の公開鍵を用いてこのメッセージが復元される。この基本形態の特質が異なる応用が数多く提案されている。一般にデジタル署名方式は、2つの一般的な区分、すなわちビットデータが付加されるデジタル署名と、メッセージ復元を行うデジタル署名とに分けられると考えられる。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
ビットデータが付加されるデジタル署名は、認証アルゴリズムに入力する際に、署名したメッセージが必要であるという事実に基づいて分類されている。非常に人気はあるが（DSSとECDSAはこの機構の例である）、このデジタル署名では他の方法ほど十分な帯域幅効率を得ることができない。
【０００４】
メッセージ復元を行うデジタル署名は、認証アルゴリズムに入力する際に、メッセージが不要であるという事実に基づいて分類されている。メッセージ復元方式の1つの問題は、合法的に署名されたメッセージをランダムビットストリングと区別する適切な冗長機能を定義することにより、依然として無くならない署名偽造を防ぐことができないことである。
【０００５】
多くの実用的なアプリケーションにおいて、署名するデータは、ある程度の固有の冗長性を有している。例えば、その日に4バイトのデータが保存されても、実際には3バイトで十分なので、このフィールドには8ビットの冗長性がある。セキュリティを万全にするには、メッセージ内に所定の冗長性を付与する必要があり、これによって帯域幅効率が減少してしまう。
【０００６】
帯域幅効率を向上させるために、メッセージを2つの成分、すなわち、不可視成分と可視成分に分割することが知られている。不可視成分は認証中に復元され、可視部分は復元処理への入力として使用される。不可視成分は、無くならない署名偽造に対抗するのに十分な冗長性を有していなければならず、また、これによって処理ができない場合には、メッセージにビットを追加する必要がある。このような方式を実現するために提案された方法の1つであるISO9796 Part 2では、不可視成分は、形式DESR[H//SHA1(V)//IA]の署名成分cを生成するために使用されており、ここで、
Hは不可視成分、
Vは可視成分、
IAは署名者の識別子、
SHA1(V)は可視成分の暗号化ハッシュ、
DESRはビットストリングの暗号化である。
しかし、この方式には、cが少なくともSHA1(V)ビット長のビット内のビット数であり、これが署名に含まれているため、必要な帯域幅効率が得られないという欠点がある。さらに、この方式では、その後、署名成分に含まれているという理由から値cがハッシュされるため、2つのハッシュ動作を呼出す必要がある。アプリケーションによっては、この計算の複雑性が不適切であることもある。
【課題を解決するための手段】
【０００７】
従って、本発明の目的は、上述の欠点を克服または軽減した署名方式を提供することである。
【０００８】
一般に、本発明の1局面によれば、メッセージが、認証中に復元される、不可視の第1部分と、認証アルゴリズムへの入力として必要な、可視の第2部分とに分割される署名方式が提供される。第1署名成分は、第1部分のみを暗号化して生成される。第1成分と可視部分を組合せ、これを暗号化的にハッシュすることにより、中間成分が生成される。次に、中間成分を用いて第2署名成分が生成され、この署名は、可視部分を有する第1および第2成分を備えている。
【０００９】
第1部分だけから第1成分を生成する、必要な帯域幅を減らし、計算を簡素化する。第1および第2部分の相対的なサイズは、アプリケーション自体によって決定される。この方法では、初期の分割しない方式とは対照的に、冗長機能をアプリケーションに依存させることができる。
【００１０】
メッセージの復元は、送信者の署名と公開鍵を用いて実現することができる。
【００１１】
本発明の他の局面によれば、不可視および可視部分に分割されたメッセージの署名の認証が提供される。認証は、メッセージの不可視部分のみから得られた第1成分を可視部分と組合せて、この組合せのハッシュを生成する。算出されたハッシュは、一般に公開された情報と共に、不可視部分と関連したビットストリングを生成するために使用される。必要な冗長性が存在する場合には、署名が承認され、復元されたビットストリングと可視部分からメッセージが再構成される。
（項目１） データ伝送システムにおいて２人の通信者で交換されるメッセージにデジタル形式で署名する方法であって、前記方法が、
前記メッセージを1対のビットストリングに細分するステップと、
第1署名成分を算出するために、前記ビットストリングの1つを利用するステップと、
前記第1署名成分と他のビットストリングとから、中間署名成分を生成するステップと、
第2署名成分を得るために、前記中間成分を利用するステップと、
署名を得るために、前記第1および第2成分を前記ビットストリングの前記他方と組合せるステップと、
を有することを特徴とする方法。
（項目２） 前記ビットストリングの1つの冗長性が、前記第1署名成分を算出する前に、所定のレベルと比較されることを特徴とする項目1に記載の方法。
（項目３） 前記所定のレベル以上のレベルに前記冗長性が付与されることを特徴とする項目2に記載の方法。
（項目４） 前記冗長性を付与するために、前記ビットストリングの１つにデータが追加されることを特徴とする項目3に記載の方法。
（項目５） 前記追加されたデータを示すために、前記ビットストリングの１つにインジケータが含まれていることを特徴とする項目4に記載の方法。
（項目６） 前記第2成分が、前記第1成分と前記別のビットストリングをハッシュすることにより生成されることを特徴とする項目1に記載の方法。
（項目７） 暗号化されたビットストリングの1つと、前記他のビットストリングとを備えた少なくとも1つの成分を有する署名からの1対の前記ビットストリングに分割されたメッセージを確認する方法であって、前記方法が、
前記1つの成分を前記別のビットストリングと組合せるステップと、
署名者の公開された情報を使って、前記組合せから前記1つのビットストリングを復元するステップと、
前記復元された1つのビットストリングを、所定の特性について調べるステップと、
を含むことを特徴とする方法。
（項目８） 前記1つの成分と前記別のビットストリングの前記組合せが、前記1つの成分と前記別のビットストリングの組合せをハッシュするステップを含むことを特徴とする項目7に記載の方法。
（項目９） 前記所定の特性が、前記復元したビットストリングの１つが冗長性であることを特徴とする項目8に記載の方法。
（項目１０） 前記署名が、前記1つの成分と前記別のビットストリングの組合せから得られた2成分を有し、前記ビットストリングの１つが、前記第2成分を使って復元されることを特徴とする項目9に記載の方法。
【図面の簡単な説明】
【００１２】
【図１】データ通信システムの概略図である。
【図２】署名の生成を示すフローチャートである。
【図３】図2の署名の認証を示すフローチャートである。
【図４】署名生成の他の実施の形態を示すフローチャートである。
【発明を実施するための形態】
【００１３】
次に、添付した図面を参照しながら本発明の実施の形態を説明する。
【００１４】
図1を参照すると、データ通信システムには、２人の通信者10、12がおり、通信チャネル14を介してメッセージMを交換している。通信者10、12の各人は、各暗号化装置16、18と、メッセージMを生成、受信するための各端末20、22とを携帯している。各暗号化装置16、18は、公開鍵にセッション鍵の生成ができるようにし、また、このセッション鍵を用いてメッセージの暗号化および解読ができるようにする、または秘密鍵を用いてメッセージへ署名ができるようにする公開鍵暗号化方式を実現する。秘密鍵を用いたメッセージへの署名は、関連する公開鍵を用いて復元することができる。このような方式の一般的な実現と、その動作原理がよく知られている。汎用コンピュータの制御下でプロトコルを実現するために、または予めプログラムされた命令としてチップセット上で実現するために、暗号化方式がデータキャリアから暗号化装置にロードされる。
【００１５】
後述の好適な実施の形態では、暗号化方式は、有限群内の離散対数問題の困難さに基づくものであり、通常は楕円曲線の暗号系と呼ばれる、有限体における楕円曲線の点に関して定義された代数系で実現される。しかし、提案されている署名方式は、あらゆる有限群におけるあらゆるＥＩＧａｒｍａｌ署名に適用することができる。
【００１６】
このような楕円曲線暗号系の領域パラメータは、形式y2=x3+dx+cの曲線およびシードポイントＰである。一方の通信者は、0<a<n（ｎは点Ｐのオーダーである）の専用鍵ａと、対応する公開鍵QA=aPとを有する。公開鍵は、ゴーストラインによって通信者10、12と通信するように示されている認証機関24に保持することができる。
【００１７】
通信者10、12によって生成されたメッセージＭは、２ビット文字列ＨおよびＶに分割される（すなわち、M=H//V）。Ｈは、不可視であり、認証処理中に復元されるビット文字列であり、Ｖは、やはり署名されるが、認証処理への入力として必要とされる２ビット文字列である。
【００１８】
署名生成アルゴリズムは、図２のフローチャートに示されている。最初、ビット文字列Ｈが調べられ、無くならない偽造を防止するのに十分な所定の値を超える冗長性を有しているかどうかが判定される。メッセージＭを生成する最初のデータが十分な冗長性を有していることがこの検査によって判定された場合、Ｈはこのデータのサブセットに過ぎない。所定の冗長性を有していない場合、０の追加バイトなど人為的に付加された冗長性を有するようにＨを変更することができる。
【００１９】
一例として、セキュリティ保護上の理由で８０ビットの冗長性が所定の下限であることが決定されているものとする。ビット文字列Ｈが固有の冗長性を有していない場合、最大で１０バイト分の０を追加する必要がある。メッセージを復元できるようにするために、追加された０のバイト数を示すインジケータが、好適にはＨまたはＶの先頭バイトとして付加される。値は０ないし１０であるので、インジケータとしては４ビットのバイトで十分であり、したがって、このビット文字列は追加の４ビットの冗長性を有する。ｔが、追加できる冗長バイトの数である場合、このデータは基本的に、少なくとも80-8tビットの冗長性を有していなければならない。
【００２０】
通信者10は、メッセージM=H//Vに署名するために、暗号化装置14で0<k<nのランダムな整数ｋを発生する。次いで、通信者10は、ｋを使用してランダムな点の値R=kPを算出する。
【００２１】
次いで、c=SKER(H)にのみなるような値ｃがビット文字列Ｈから算出される。SKERは、ランダムな点Ｒから得られる鍵の制御下での対称鍵アルゴリズムを指す。これは、ハッシュ関数などの関数をＲに適用するか、あるいはＲを丸めるか、あるいは１つの座標、たとえば、ｘ座標を鍵として使用することによって得ることができる。Ｈが、Ｒから得られた鍵よりも小さい場合、１つの可能なSKEは、単にＨをXORし、Ｒから得られた鍵からビットを丸めることである。これは実際上、１回限りの暗号化通信方式である。Ｈが鍵よりも大きい場合、DESベースのアルゴリズムを使用するか、あるいは単にＨを用いて鍵を繰り返しXORすることが可能である。
【００２２】
ビット文字列Ｖを使用して、c’=SHA1(c//V)になるように中間成分c’が算出される。この場合、SHA1は、暗号による安全なハッシュ・アルゴリズムである。証明書などの追加情報または通信者10の識別情報が好ましい場合は、そのような情報を、ハッシュされた値c’に組み込むことができる。
【００２３】
署名成分ｃは、不可視部分Ｈのビット単位暗号であるので、この部分と同じ長さであり、かつ中間成分c’は単一のハッシュ演算を用いて得られることに留意されたい。
【００２４】
次いで、既知のＥＩＧａｍａｌ式のいずれかを使用して、通信者10が利用できる値から署名成分が算出される。従来の数式にはSchnorr署名アルゴリズムがあり、この場合、s=c’a+K(mod n)が成立する。次いで、成分（s、c、V）から署名が生成され、通信者12に転送される。
【００２５】
通信者12による署名の認証は、Schnorr署名に関する図３に示されているように対応するアルゴリズムを適用することによって行われる。通信者12は最初、通信者10の公開鍵QAの真正なコピーを認証機関24から得る。次いで、通信者12は、値c”=SHA1(c//V)を算出し、署名内の利用可能な情報、すなわちs、c、Vとシステムのドメインパラメータとから、値
X=sP
Y=c”QA
Z=X-Y
を得る。次いで、H’=SKEz(c)になるように点Ｚから得られた鍵の制御下での対称鍵アルゴリズムを、受信された署名成分ｃに適用することによって、ビット文字列H’が復元される。ビット文字列H’が調べられ、必要な冗長性を有しているかどうかが判定され、有している場合、通信者12はＭの署名を承認し、メッセージをH’//Vとして再構成する。
【００２６】
メッセージＭは分割されているので、必要な冗長性を有している必要があるのは一方の部分Ｈだけである。他方の部分Ｖは、暗号化しないで送信され、元のデータのデータ構造を保持し、それによって帯域幅効率を向上させることができる。
【００２７】
実際的でありかつ商業的に有益であるこの方式の他の特徴は、ｃに符号化されている情報を利用できるのが、通信者10の公開鍵QAを有する人だけであることである。Ｖに含まれているデータはすべての人が利用することができる。通信者10が、QAを有さない人から不可視にすることを望む情報があり、この場合、送信者、すなわち通信者10はこの情報をビット文字列Ｈに含める。
【００２８】
たとえば、メールに課された料金を認証するために署名が使用されるある応用例では、差出人は、いくつのメールを送ったかを受取人が知ることを望まない場合がある。（料金を検証し、したがってこの情報を必要とする）郵便局は差出人の公開鍵を有し、検証時にこの情報を復元することができるが、受取人は、差出人の公開鍵を有さない場合には復元することができない。
【００２９】
もちろん、差出人の公開鍵QAが印に含まれている場合、受取人もこれを利用することができる。あるいは、受取人が認証機関の公開鍵を有する場合にのみ復元することのできる証明書に差出人の公開鍵を含めることができる。これが一般には利用できない場合、Ｈの内容は受取人から不可視にされる。
【００３０】
上述したように、他の形式の署名式を使用することができる。図４のフローチャートに示した他の実施の形態では、ECDSA規格と同様な署名式が使用されている。通常、このような構成では、
・R=kP
・c=DESR(M)
・r’=SHA1(c)
・s=k-1{SHA1(c//IDA)+ar’}mod n（IDAは差出人の識別子である）であり、
・署名は(s,c)である。
この方式は、前述の混成方式と共に使用される際には、
・R=kP
・c=DESR(M)
・r’=SHA1(c)
・s=k-1{SHA1(c//V)+ar’}modnであり、
・署名が(s,c,V)になるように変更される。
したがって、この場合も、第１の成分ｃを生成するために使用されるのはメッセージの一部Ｈだけであるので、指定された冗長性を必要とするのはこの部分だけである。メッセージのバランスをとるには、低減された冗長性を使用して帯域幅効率を維持することができる。
【００３１】
修正された方式に関する検証は、部分的なメッセージ復元および必要な冗長性に適合するように変更される。
【特許請求の範囲】
【請求項１】
本明細書に記載の発明。
【請求項１】
本明細書に記載の発明。
【図１】
【図２】
【図３】
【図４】
【図２】
【図３】
【図４】
【公開番号】特開２０１１−１２０２６６（Ｐ２０１１−１２０２６６Ａ）
【公開日】平成２３年６月１６日（２０１１．６．１６）
【国際特許分類】
【出願番号】特願２０１１−２１２１６（Ｐ２０１１−２１２１６）
【出願日】平成２３年２月２日（２０１１．２．２）
【分割の表示】特願２０００−２７２３５９（Ｐ２０００−２７２３５９）の分割
【原出願日】平成１２年９月７日（２０００．９．７）
【出願人】（３９７０７１７９１）サーティコム コーポレーション (38)
【出願人】（５０６１８８９９８）ピットニー ボウズ インコーポレーテッド (1)
【Ｆターム（参考）】
【公開日】平成２３年６月１６日（２０１１．６．１６）
【国際特許分類】
【出願日】平成２３年２月２日（２０１１．２．２）
【分割の表示】特願２０００−２７２３５９（Ｐ２０００−２７２３５９）の分割
【原出願日】平成１２年９月７日（２０００．９．７）
【出願人】（３９７０７１７９１）サーティコム コーポレーション (38)
【出願人】（５０６１８８９９８）ピットニー ボウズ インコーポレーテッド (1)
【Ｆターム（参考）】
[ Back to top ]