鍵認証方式
【課題】少なくとも１組の通信者間で情報を送受信するのに用いる通信システムにおいてセキュリティを向上させる方法を提供すること。
【解決手段】一般に、通信者間で行われる通信は、一方の通信者が、所定のアルゴリズムの算術的属性に応じた鍵対を生成し、その一方の鍵、即ち公開鍵を証明書付きで相手側に送信すると共に、鍵対のうち秘密鍵を用いて署名を生成および送信する工程と、受信者が、相手側の通信者に上記署名を送信して上記署名を確認する工程とを有する。本発明は、さらに、上記所定のアルゴリズムの要件により決定される算術的属性に合致する公開鍵を確認する工程を提供する。
【解決手段】一般に、通信者間で行われる通信は、一方の通信者が、所定のアルゴリズムの算術的属性に応じた鍵対を生成し、その一方の鍵、即ち公開鍵を証明書付きで相手側に送信すると共に、鍵対のうち秘密鍵を用いて署名を生成および送信する工程と、受信者が、相手側の通信者に上記署名を送信して上記署名を確認する工程とを有する。本発明は、さらに、上記所定のアルゴリズムの要件により決定される算術的属性に合致する公開鍵を確認する工程を提供する。
【発明の詳細な説明】
【技術分野】
【０００１】
（発明の属する技術分野）
本発明は、通信システムのセキュリティ確保（ｓｅｃｕｒｅ）に関するものであり、特に、そのようなシステムにおけるパラメータや鍵の妥当性検証（認証；ｖａｌｉｄａｔｅ）を行う方式（手順；ｓｃｈｅｍｅ）に関する。
【背景技術】
【０００２】
（従来の技術）
セキュリティ機能を持つ（ｓｅｃｕｒｅ）データ通信システムを用いて、１組の通信者間で情報の送受信が行われる。交換される情報の少なくとも一部は、送信者が所定の数学的演算を行うことによって、暗号化される。そして、受信者は、上記の数学的演算に応じた相補的な数学的演算を行って、その暗号を解読する。公開鍵あるいは対称型鍵システムでは、通信者同士がいくつかのパラメータを予め知っておく必要がある。例えば、これまでにも、様々な方式やプロトコルが考案されており、送信者の公開鍵や身元などの妥当性検証（認証；ｖａｌｉｄａｔｅ）が行われている。これらのシステムのセキュリティ（ｓｅｃｕｒｉｔｙ）あるいは妥当性は、署名が妥当なものか否かに依存し、システムパラメータ（もしあれば）が妥当であり、公開鍵が妥当であり、かつ、署名が確認（検証；ｖｅｒｉｆｙ）された場合に限り確保される。さらに、非対称型システムのセキュリティが確保されるのは、システムパラメータ（もしあれば）が妥当であり、暗号化公開鍵が妥当であり、対称型鍵が指定通りにフォーマットされており、かつ、対称型鍵の復号検査（ｒｅｃｏｖｅｒｙ ｃｈｅｃｋｓ ）でフォーマットの妥当性が検査された場合に限られる。
【０００３】
一方、鍵一致プロトコルのセキュリティが確保されるのは、システムパラメータ（もしあれば）が妥当であり、鍵一致公開鍵が妥当であり、かつ、共有秘密および対称型鍵が規格の指定通り生成された場合に限られる。以上の全てにおいては、公開鍵あるいは対称型鍵、即ち共有秘密が、プロトコル方式にて指定された通りに生成され、妥当であるということを前提として考えている。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、これらのパラメータが偽物である場合や何らかの形で欠陥がある場合には、問題が生じてしまう。
【０００５】
以下の例を用いて、公開鍵暗号システムの１つあるいは複数のパラメータにおける欠陥が、どのようなことを意味するかについて説明する。例えば、ディジタル署名を用いて送信者の正当性（ａｕｔｈｅｎｔｉｃｉｔｙ）を示す場合を考える。受信者Ａが送信者Ｂから証明書付きの公開鍵を受信すると、Ａは証明書を確認する。次に、ＢがＡに署名付きのメッセージを送信すると、Ａは署名を確認し、さらなる通信が可能と判断することができる。しかしながら、この場合、Ｂが公開鍵を故意に改ざんすれば、この妥当でない公開鍵を受信者Ａが識別できなくなる。同様に、参加者Ｃが鍵対を生成し、続いて公開鍵証明書を受信し、その後に、上記参加者Ｃが、証明書に含まれている公開鍵が妥当であると仮定して、証明書とそれに続いて署名付きのメッセージをＢに送信した場合を考える。上記参加者Ｂは、Ｃの鍵情報を決定することができる。上記の両方の場合から分かるように、署名を確認する際に認証されていないパラメータを使用することに起因して問題が生じる可能性がある。
【０００６】
鍵送信プロトコルでは、通信者Ａが誤って違う相手に対称型鍵を送信してしまうことがある。例えば、通信者Ａが証明書付きの公開鍵を送信者Ｂから受信した場合に、Ａは該証明書を確認し、公開鍵により暗号化された対称型鍵および対称型鍵により暗号化されたメッセージをＢに送信する。これにより、Ａが承認される。逆に、通信者の１人であるＣが鍵対を生成し、公開鍵証明書を得た後にそれをＡに送信する。この場合、Ａは公開鍵を用いて対称型鍵およびメッセージを暗号化し、それをＣに返信する。したがって、この場合、Ｃが承認される。
【０００７】
鍵一致プロトコルにおいては、通信者の１人であるＡが、例えば、Ｂから証明書付きの公開鍵を受信し、Ａの証明書付き公開鍵をＢに送信する。ＡおよびＢはそれぞれ相手側の証明書を確認し、互いに一致した対称型鍵を有する。この例では、Ａが２度承認されることになる。
【０００８】
以上の例から分かるように、公開鍵システムのセキュリティが確保されていても、システムのセキュリティは、通信者の一方あるいは両方に大きく依存しており、要求された所定の鍵が実際のところ使用されている特定のアルゴリズムの所定の鍵であることに依存している。典型的には、受信者は、ビット列を受信すると、このビット列が要求される鍵を実際に表すものであるとみなしてしまうが、そのために対称型鍵システムでは特に問題が生じる。即ち、対称型鍵システムでは、典型的にはサイズが正しければどのようなビット列でも鍵であると解釈されてしまう。このビット列の中の１ビットが所定の鍵と異なっていても、別の鍵として解釈されるので、その鍵が誤ったものでない限り、妥当な暗号演算（ｃｒｙｐｔｏ ｏｐｅｒａｔｉｏｎ）を行うことができる。
【０００９】
非対称型秘密鍵システムでは、秘密鍵の所有者はその秘密鍵について全て知っているので、それが正しいか否かの妥当性を検証することができる。しかしながら、第３者が上記所有者のシステムに公開鍵を送信した場合、受信した鍵が公開鍵の算術的要件に合致するものか否か、あるいはその要求された公開鍵を用いて演算（ｏｐｅｒａｔｉｏｎ）を行った場合に機密性が確保された暗号演算となるか否かについては、疑問が生じる。所有者のシステムが検査を行わなければ確実には分からないので、所有者にしか分からないことになる。
【００１０】
以上のことから分かるように、鍵の確立は安全でない場合がある。Ｃｒｙｐｔｏ ’９７で発表されたリン（Ｌｉｍ）およびリー（Ｌｅｅ）による論文では、上記問題点が、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ方式において次数（ｏｒｄｅｒ）が正しくない偽公開鍵を用いた場合に、相手側の秘密鍵に関する情報を得ることができるという例を用いて指摘された。ＲＳＡあるいはＲａｂｉｎ方式においては、公開鍵および秘密鍵を１組の大きな素数の関数とすることで、そのような大きな数の因数分解の困難性からセキュリティを確保している。これらの鍵は、２つの任意の大きな素数の積から生成している。しかしながら、ｎが素数であって、２つの素数の積でないとすると、ｐｈｉ（ｎ）＝ｎ−１が成り立つので、偽の「公開鍵」（ｎ，ｅ）から誰でもｄを決定することができる。これらは、公開鍵の使用者が、要求された公開鍵についてアルゴリズムの要件に合致する算術的属性の妥当性を検証することができないが為に生じる問題であると言える。
【００１１】
本発明は、セキュリティ機能を持つ通信システムにおいて、改良された妥当性検証を行うことを目的としている。さらに、本発明は、誰でもいつでも公開情報のみを用いてそのような妥当性検証を行えるようにすることを目的としている。
【課題を解決するための手段】
【００１２】
本発明の公開鍵通信システムにおけるディジタル署名の妥当性検証方法によれば、公開鍵の算術的属性がシステムアルゴリズムに合致することを確認する工程と、上記ディジタル署名を確認する工程とを含む。
【００１３】
さらに、システムパラメータを確認する工程が設けられる。
【００１４】
さらに、要求された公開鍵がアルゴリズムと算術的に合致するか否かの妥当性検証が実行されたことを示す情報と、および適切な場合には、さらに、実行された妥当性検証の回数を示す情報とを証明書情報内に含める工程が設けられる。
（項目１）
データ通信システムにおいて、一方から他方の通信者に送信されるディジタル情報の妥当性を検証する方法において、
所定の算術的属性とシステムパラメータとを有する所定の暗号化方式に応じて公開鍵を生成する工程と、
上記公開鍵が上記暗号化方式の算術的属性に合致することを確認する工程と、
確認された上記公開鍵を受信者に送信する工程とを含むことを特徴とする方法。
（項目２）
上記公開鍵の妥当性が検証されたことを示す情報を、確認された上記公開鍵と共に送信することを特徴とする項目１に記載の方法。
（項目３）
上記公開鍵は楕円曲線公開鍵Ｑであり、上記暗号化方式は楕円曲線方式であることを特徴とする項目１に記載の方法。
（項目４）
上記公開鍵を確認する工程は、上記公開鍵Ｑが上記楕円曲線Ｅ上にあることを確認する工程を含むことを特徴とする項目３に記載の方法。
（項目５）
上記システムパラメータを確認する工程をさらに含むことを特徴とする項目１に記載の方法。
（項目６）
公開鍵および対称型鍵を有するセキュリティが確保された非対称型通信システムを提供する方法において、
上記公開鍵が妥当であると確認する工程と、
上記対称型鍵が所定のフォーマットを有することを確認する工程と、
上記対称型鍵を復号する工程と、
復号された上記対称型鍵が所定の妥当なフォーマットを有することを確認する工程とを含むことを特徴とする方法。
（項目７）
上記システムパラメータが妥当であると確認する工程をさらに含むことを特徴とする項目６に記載の方法。
（項目８）
公開鍵、対称型鍵、および秘密情報を有する通信システムにてセキュリティが確保された鍵一致を提供する方法において、
上記公開鍵が妥当であると確認する工程と、
上記秘密情報が妥当であると確認する工程と、
上記対称型鍵が妥当であると確認する工程とを含むことを特徴とする方法。
（項目９）
システムパラメータが妥当であると確認する工程をさらに含むことを特徴とする項目８に記載の方法。
（項目１０）
上記鍵の検証を示す情報を証明書情報に含める工程をさらに含むことを特徴とする項目８に記載の方法。
【図面の簡単な説明】
【００１５】
【図１】通信システムの概略図である。
【発明を実施するための形態】
【００１６】
（発明の実施の形態）
図１に示すように、データ通信システム１０は、１組の通信者を含み、該１組の通信者は、送信者１２および受信者１４であり、互いに通信チャネル１６により接続されている。送信者１２および受信者１４は、通信チャネル１６を介した送受信用に備えてディジタル情報を処理する暗号化ユニット１８および２０をそれぞれ有している。データ通信システム１０は、証明書発行局（ＣＡ；ｃｅｒｔｉｆｉｃａｔｉｏｎ ａｕｔｈｏｒｉｔｙ、認証機関とも言う）２２をさらに有していてもよい。
【００１７】
以下、本発明の実施の形態として、公開鍵アルゴリズムを用いた場合について説明する。鍵一致は、以下に示す６つのルーチンを有している。即ち、システムパラメータの生成、システムパラメータの妥当性検証、鍵対の生成、公開鍵の妥当性検証、共用機密の導出（ｄｅｒｉｖａｔｉｏｎ）、および対称型鍵の導出である。上記鍵検証工程においては、誰でもいつでも公開情報のみを用いて公開鍵の妥当性を検証することができる。これらのルーチンにより、公開鍵の値域（ｒａｎｇｅ）および次数（ｏｒｄｅｒ）が検証される。公開鍵の妥当性が検証されれば、論理的にはそれに対応する秘密鍵が存在する可能性があるが、実際に存在することは証明されない。
【００１８】
楕円曲線ディジタル署名アルゴリズム（ＥＣＤＳＡ）にも、６つのルーチンが含まれる。即ち、システムパラメータの生成、システムパラメータの妥当性検証、鍵対の生成、公開鍵の妥当性検証、署名の生成、および署名の確認（ｓｉｇｎａｔｕｒｅ ｖｅｒｉｆｉｃａｔｉｏｎ）である。一方、ＤＳＡの第１のタイプには、４つのルーチン、即ち、システムパラメータの生成、鍵対の生成、署名の生成、および署名の確認が含まれる。より最近のＤＳＡでは、５つのルーチン、即ち、システムパラメータの生成、（非明示の（ｉｍｐｌｉｃｉｔ））システムパラメータの妥当性検証、鍵対の生成、署名の生成、および署名の確認が含まれる。鍵の妥当性検証を行うために、ＤＳＡパラメータであるｐ、ｑ、およびｇは既に妥当性が検証されているものとみなす。秘密鍵をｘ、公開鍵ｙはｙ＝ｇｘ ｍｏｄ ｐである。そして、ｙの値域について、１＜ｙ＜ｐであることを確認することによって妥当性を検証するとともに、ｙの次数について、ｙｑ ｍｏｄ ｐ＝１であることを確認することによって妥当性を検証する。これらの妥当性検証により、ある要求されたＤＳＡ公開鍵が、そのような鍵に対する算術的要件を満たすものであるということが確認される。これらの妥当性検証は、誰もがいつでも公開情報のみを用いて実行することが可能である。
【００１９】
ＲＳＡあるいはＲａｂｉｎ署名アルゴリズムには、一般に３つのルーチン、即ち、鍵対の生成、署名の生成、および署名の確認が含まれる。ＲＳＡ公開鍵（ｎ，ｅ）の検証は以下の３つのステップを含む。即ち、まず最初にｅの妥当性を検証し、次にｎの妥当性を検証し、その次にｅおよびｎが互いに矛盾していないことを検証する。公開指数ｅの妥当性を検証するためには、指数ｅが２≦ｅ≦２（ｋ−１６０） （ｋは法（ｍｏｄｕｌｕｓ）ｎのビット長（ｌｅｎｇｔｈ））であることを利用する。指数ｅの範囲が上記のような特定された範囲であるべきというこの要件は、特に、ここでの検証を実現可能にしている。ｅ＞２であれば、ｅは奇数でなければならない。さらに、閉じたネットワークの場合には、公開指数ｅは他の全ての判定基準を満たすべきであることが知られている。即ち、例えばｅは３か、６５５３７か、あるいは６５５３７より大きな任意の数でなければならないといった判定基準である。これらの検証は、鍵の妥当性をさらに確認するために行ってもよい。これらの検証については、ＲＳＡ公開鍵部分認証ルーチン（ｐｕｂｌｉｃ ｋｅｙ ｐａｒｔｉａｌ ｖａｌｉｄａｔｉｏｎ ｒｏｕｔｉｎｅ）の仕様（ｓｐｅｃｉｆｉｃａｔｉｏｎ）の一部として含まれていてもよい。上記の指数ｅの検証は簡略なもののように見えるが、この検証により、ＲＳＡ／Ｒａｂｉｎアルゴリズムで選択が試みられるｄよりも前にｅが選択されたことが確認できる。なぜなら、この検証により、ｄｅ＝１ ｍｏｄ（ｌｃｍ（ｐ−１，ｑ−１））であり、法ｎに比べてｅでは桁数を表すゼロが少なくとも１６０個多いことが分かり、これはｄを先に選択すると実現不可能だからである。
【００２０】
法ｎの妥当性を検証するためには、ｎの大きさを求める。ｎは、正確に（１０２４＋１２８ｓ）ビット（ただし、ｓ＝０，１，２，３，…等）を含まなければならないことが知られている。このことは、簡単に検証でき、部分鍵認証の一部とすることができる。法ｎは２つの素数の積で、２より大きい全ての素数が奇数であることから、法ｎが奇数であるか否か判断することによって、法ｎに対してさらなる妥当性検証を行ってもよい。したがって、奇数同士の積は奇数であるので、ｎは奇数でなければならない。さらに、Ｒａｂｉｎアルゴリズムでｅ＝２の場合には、ｐ＝３ ｍｏｄ ｎ、およびｑ＝７ ｍｏｄ ８でなければならないことが分かっている。このことから、ｎ＝ｐｑ＝２１ ｍｏｄ ８＝５ ｍｏｄ ８でなければならない。このことは、ｅ＝２のときにｎ＝５ ｍｏｄ ８であることを確認することで検証できる。さらに、ｎは完全な累乗（ｐｅｒｆｅｃｔ ｐｏｗｅｒ）であってはならないことが分かっている。このことから、ｎが２つの異なる素因数からなることが確実に分かり、単純な検査により妥当性が検証できる。上記検証については、Ｍｅｎｅｚｅｓ、ｖａｎ Ｏｏｒｓｃｈｏｔ、およびＶａｎｓｔｏｎｅによる”Ｈａｎｄｂｏｏｋ ｏｆ Ａｐｐｌｉｅｄ Ｃｒｙｐｔｏｇｒａｐｈｙ（応用暗号手法ハンドブック）”に記述されている。
【００２１】
また、ｎは合成数でなければならないことも知られている。したがって、ｎが素数の場合には、容易に逆変換が可能になるため、セキュリティが全く確保されなくなる。ｎが合成数であるか否かの検証は、ｎが合成数であると実際に証明されると予想してＭｉｌｌｅｒ−Ｒａｂｉｎ確率的素数検証（ｐｒｏｂａｂｌｅ ｐｒｉｍｅ ｔｅｓｔ）を行うことによって、実現可能である。法ｎの検証を行うためのさらなる検査は、以下のことに基づくものである。即ち、ｎが２つの大きな素数の積であって、因数分解が難しく、したがって単純な方法で因数分解しようとしても成功しないものであることが分かっていることに基づいている。例えば：ｉとして小さな奇数の素数からある程度の大きさまでの全ての素数、例えば最初の５００００（５０Ｋ）個の奇数の素数について、ＧＣＤ（ｎ，ｉ）を計算してみてもよい。
【００２２】
前述の２つの検証により、前者からは少なくとも１つの因子が法のビットの半分以下の大きさでなければならないことが分かり、後者からは各因子が検証した最大素数よりも大きくなければならないことが分かる。さらに、ポテンシャル因子（ｐ，ｑ，ｒ，…）は、上記で検証した最大素数の大きさに依存した限られた数しか存在しなくなる。
【００２３】
以上の複数の検証を組み合わせると、相乗効果が得られる。検証の目的は、敵のとりうる行動の自由度を大幅に小さくすることである。攻撃がほぼ不可能な場合であっても、部分的鍵認証を行うことによって、攻撃をより一層困難にし、望ましくは攻撃を不可能あるいは少なくとも非経済的なものにすることができる。
【００２４】
さらに、ｐおよびｑの値は近くなりすぎてはならないものであるから、法ｎを検証する際には、これらが近接した値であると仮定し、ｎの因数分解を試みる。ｎの平方根をｐおよびｑの初期予想値とする。ｐを減少させる一方、ｑを増加させ、ｎが所定の限度まで因数分解できるか決定する。さらに、ＲＳＡの法のセットでは素数が繰り返してはならないことが分かっているため、ＲＳＡのある法のセットｎ１、ｎ２に対して、ＧＣＤ（ｎｉ，ｎｊ）を計算し、全ての計算結果が１に等しいことを確認することができる。
【００２５】
上述のオフライン検証には限界が存在するが、パラメータの所有者が特定の情報、例えばｎの因数分解を知っているので、これらの検証を拡張することができる。よって、所有者をオンラインオラクル（ｏｒａｃｌｅ）として利用してもよい。このオラクルに関してなされる質問に対する回答が不正解であることを識別することで、誰もが公開鍵が無効であると断言できることになる。
【００２６】
Ｖａｎｓｔｏｎｅらの”Ｈａｎｄｂｏｏｋ ｏｆ Ａｐｐｌｉｅｄ Ｃｒｙｐｔｏｇｒａｐｈｙ”によれば、所有者は（平方根 ｍｏｄ ｎ）を計算できるが、他者にはできない。検証者は、（任意値 ｍｏｄ ｎ）のヤコビ符号（ヤコビアン；Ｊａｃｏｂｉ Ｓｙｍｂｏｌ）を１または−１に決定し、半分は１、他方の半分は−１に決定する。１の場合には、その数が平方数か否かで、再度半々に分けられる。検証者は、（ある数 ｍｏｄ ｎ）を平方する。平方数のヤコビ符号は、常に１である。
【００２７】
検証者は、既知の平方数ｕおよびヤコビ符号が１である任意の要素ｒのいずれかを選択する。そして、所有者にこの２種類の要素に対して「これは平方数であるか」と質問する。所有者は、イエスかノーかで回答する。ｕが選択された場合、所有者がイエスと答えなければ鍵の法（ｍｏｄｕｌｕｓ）は無効となる。ｒが選択された場合、所有者がイエスと答える回数とノーと答える回数とがそれぞれ約半分でなければ、鍵の法が無効となる。
【００２８】
これを何度も繰り返すことにより、信頼性が高まる。検証者が全て平方数について所有者に質問した場合には、所有者は常にイエスと答えなければならない。検証者が全てヤコビ符号が１である任意の要素について所有者に質問した場合には、所有者はその半分にはイエスと答え、半分にはノーと答えなければならない。偽鍵の所有者は、少なくとも半分の答えがイエスであることを知っているだけである。しかしながら、秘密鍵の所有者であれば、ｎの因数分解を知っており、平方数を知っているので、擬似平方数についてそれらが平方数であると嘘をついて、検証者を騙しさえすればよい。検証者は、既知の擬似平方数を用いて「これは平方数であるか」と質問するだけでよい。通常、法の因数分解を知らなければ、ある数がその法の擬似平方数であると決定することは不可能である。しかしながら、所有者は、上述の質問に対して、ヤコビが１である数のいくつかは擬似平方数であると答えなければならない。検証者は、既知の擬似平方数と（平方数ｍｏｄ ｎ）とを掛け合わせることによって、任意の既知の擬似平方数を生成することはできる。検証者は、その結果として得られた値については、擬似平方数であると知っている。この３つめのタイプの数ｔ（既知の擬似平方数）について所有者に尋ねると、この場合には、所有者がいくつかの擬似平方数は平方数であると嘘をついても、その嘘が検証者に知られる。
【００２９】
ｅとｎとを共に検証するには、ＧＣＤ（ｅ，ｐ−１）＝１、かつＧＣＤ（ｅ，
ｑ−１）＝１でなければならない。ｅが奇数の場合には、整数ｘおよびｐに対してｐがｘｅ＋１の形で表されない数であり、かつ、整数ｙに対してｑがｙｅ＋１の形で表されない数でなければならないことが分かっている。ｐとｑとの両方が不正な場合には、ｎがｘｙｅ２ ＋ｘｅ＋ｙｅ＋１の形で表されないものであり、かつｎ≠１ ｍｏｄ ｅが成り立たなければならない。
【００３０】
ｅとｎとを共に検証する別の方法について以下に説明する。ＧＣＤ（ｅ，ｐｈｉ（ｎ））が１でなければならないことが分かっている。ｐｈｉ（ｎ）＝（ｐ−１）（ｑ−１）であることが分かっているので、式が２つで未知数が２つであるから、検証者は、ｎを因数分解することができる。
【００３１】
鍵対に対する他の要件が満たされているとする。ＧＣＤ（ｅ，ｐｈｉ（ｎ））＝１を満たす必要があるのは、ｅを用いた演算を確実に１：１対応（逆変換可能）の関数とするためである。さもなければ、ｅを用いた演算が多数：１になってしまう。ｅを用いた演算が多数：１対応の場合には、ｄ（ｅの逆元（ｉｎｖｅｒｓｅ））が存在しなくなるか、少なくとも通常では導き出せなくなる。所有者はｄが実際に存在するという証拠を提示しなければならない。しかしながら、上記質問は、秘密鍵の所有者の管理の元で行うべきではない。即ち、所有者自身で署名した証明書要求（ｓｅｌｆ−ｓｉｇｎｅｄ ｃｅｒｔｉｆｉｃａｔｅ ｒｅｑｕｅｓｔ）では、十分な証拠とはならない。
【００３２】
挑戦者は、承認を要求された所有者にダミーメッセージをいくつか送信して署名させることもできる。秘密鍵の所有者は、それらがダミーメッセージであると確認し、署名し、挑戦者に返信する。これは、ｄが存在するオンライン確率的オラクル検証（ｏｎｌｉｎｅ
ｐｒｏｂａｂｉｌｉｓｔｉｃ ｏｒａｃｌｅ ｔｅｓｔ）である。
【００３３】
したがって、誰でもオフライン検証がいつでも実行できる。所有者がオンライン状態にあれば、誰でもオンライン検証を実行できる。所有者は、オフラインおよびオンライン検証を行って、自身の秘密鍵が有効であることを確認することができる。ＣＡは、オンライン検証を行って、公開鍵証明書において何の妥当性がどの程度まで検証されているかを他者に伝える。
【００３４】
ＥＣＤＳＡにおけるシステムパラメータは、フィールドサイズｑ＝ｐまたは２ｍ である。オプションの種（ｏｐｔｉｏｎａｌ ｓｅｅｄ）によって（ａ，ｂ）が生成され、（ａ，ｂ）によって、曲線の次数がｈｎとなるように、Ｆｑ で表される楕円曲線、この曲線上の特異点Ｐ、Ｐの大きな素数の次数（ｌａｒｇｅ ｐｒｉｍｅ ｏｒｄｅｒ）であるｎ、および余因子（ｃｏｆａｃｔｏｒ）ｈを定義する。（ａ，ｂ）で定義されるフィールドサイズＥＣおよび点Ｐは主要パラメータである。
【００３５】
ＥＣシステムパラメータだけでなく、ＥＣ公開鍵についても確認することが重要である。例えば、楕円曲線公開鍵Ｑを想定し、ＱがＥ上にあるとする。鍵一致において素数の次数の曲線を使用している場合、Ｑの次数を検査する必要はない。なぜなら、Ｑが曲線上にあれば正確な次数を有していることが確かであるからである。Ｑが曲線上にあることを検査することは重要である。なぜなら、Ｑが曲線上になければ、偽鍵が、ａＱを計算する際に秘密鍵ａを明かしてしまうからである。公開鍵が曲線上にあると確認することは、曲線の式に代入するか、検証を行うことにより可能である。
【００３６】
以上のことから、鍵認証を行うことにより、攻撃にさらされることが抑制され、不慮のエラーの検出が助けられ、ＣＡが行う価値のあるサービスが提供されることになる。当業者ならば理解できるように、上記の技術および方法は、本発明の工程を実行する適切なプロセッサにおいて実現することができる。さらに、上述の様々な方法は、汎用のコンピュータを使用し、ソフトウェアにて選択的に起動あるいは再構成して実行するのが便利がよいが、当業者ならば理解できるように、そのような方法は、必要な各工程を実行するように構成された、ハードウェア、ファームウェア、あるいはより特殊な装置において実現してもよい。
(発明の効果)
【００３７】
本発明によれば、セキュリティ機能を持つ通信システムにおいて、改良された妥当性検証を行うことができる。さらに、本発明によれば、誰でもいつでも公開情報のみを用いてそのような妥当性検証を行うことが可能となる。
【技術分野】
【０００１】
（発明の属する技術分野）
本発明は、通信システムのセキュリティ確保（ｓｅｃｕｒｅ）に関するものであり、特に、そのようなシステムにおけるパラメータや鍵の妥当性検証（認証；ｖａｌｉｄａｔｅ）を行う方式（手順；ｓｃｈｅｍｅ）に関する。
【背景技術】
【０００２】
（従来の技術）
セキュリティ機能を持つ（ｓｅｃｕｒｅ）データ通信システムを用いて、１組の通信者間で情報の送受信が行われる。交換される情報の少なくとも一部は、送信者が所定の数学的演算を行うことによって、暗号化される。そして、受信者は、上記の数学的演算に応じた相補的な数学的演算を行って、その暗号を解読する。公開鍵あるいは対称型鍵システムでは、通信者同士がいくつかのパラメータを予め知っておく必要がある。例えば、これまでにも、様々な方式やプロトコルが考案されており、送信者の公開鍵や身元などの妥当性検証（認証；ｖａｌｉｄａｔｅ）が行われている。これらのシステムのセキュリティ（ｓｅｃｕｒｉｔｙ）あるいは妥当性は、署名が妥当なものか否かに依存し、システムパラメータ（もしあれば）が妥当であり、公開鍵が妥当であり、かつ、署名が確認（検証；ｖｅｒｉｆｙ）された場合に限り確保される。さらに、非対称型システムのセキュリティが確保されるのは、システムパラメータ（もしあれば）が妥当であり、暗号化公開鍵が妥当であり、対称型鍵が指定通りにフォーマットされており、かつ、対称型鍵の復号検査（ｒｅｃｏｖｅｒｙ ｃｈｅｃｋｓ ）でフォーマットの妥当性が検査された場合に限られる。
【０００３】
一方、鍵一致プロトコルのセキュリティが確保されるのは、システムパラメータ（もしあれば）が妥当であり、鍵一致公開鍵が妥当であり、かつ、共有秘密および対称型鍵が規格の指定通り生成された場合に限られる。以上の全てにおいては、公開鍵あるいは対称型鍵、即ち共有秘密が、プロトコル方式にて指定された通りに生成され、妥当であるということを前提として考えている。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、これらのパラメータが偽物である場合や何らかの形で欠陥がある場合には、問題が生じてしまう。
【０００５】
以下の例を用いて、公開鍵暗号システムの１つあるいは複数のパラメータにおける欠陥が、どのようなことを意味するかについて説明する。例えば、ディジタル署名を用いて送信者の正当性（ａｕｔｈｅｎｔｉｃｉｔｙ）を示す場合を考える。受信者Ａが送信者Ｂから証明書付きの公開鍵を受信すると、Ａは証明書を確認する。次に、ＢがＡに署名付きのメッセージを送信すると、Ａは署名を確認し、さらなる通信が可能と判断することができる。しかしながら、この場合、Ｂが公開鍵を故意に改ざんすれば、この妥当でない公開鍵を受信者Ａが識別できなくなる。同様に、参加者Ｃが鍵対を生成し、続いて公開鍵証明書を受信し、その後に、上記参加者Ｃが、証明書に含まれている公開鍵が妥当であると仮定して、証明書とそれに続いて署名付きのメッセージをＢに送信した場合を考える。上記参加者Ｂは、Ｃの鍵情報を決定することができる。上記の両方の場合から分かるように、署名を確認する際に認証されていないパラメータを使用することに起因して問題が生じる可能性がある。
【０００６】
鍵送信プロトコルでは、通信者Ａが誤って違う相手に対称型鍵を送信してしまうことがある。例えば、通信者Ａが証明書付きの公開鍵を送信者Ｂから受信した場合に、Ａは該証明書を確認し、公開鍵により暗号化された対称型鍵および対称型鍵により暗号化されたメッセージをＢに送信する。これにより、Ａが承認される。逆に、通信者の１人であるＣが鍵対を生成し、公開鍵証明書を得た後にそれをＡに送信する。この場合、Ａは公開鍵を用いて対称型鍵およびメッセージを暗号化し、それをＣに返信する。したがって、この場合、Ｃが承認される。
【０００７】
鍵一致プロトコルにおいては、通信者の１人であるＡが、例えば、Ｂから証明書付きの公開鍵を受信し、Ａの証明書付き公開鍵をＢに送信する。ＡおよびＢはそれぞれ相手側の証明書を確認し、互いに一致した対称型鍵を有する。この例では、Ａが２度承認されることになる。
【０００８】
以上の例から分かるように、公開鍵システムのセキュリティが確保されていても、システムのセキュリティは、通信者の一方あるいは両方に大きく依存しており、要求された所定の鍵が実際のところ使用されている特定のアルゴリズムの所定の鍵であることに依存している。典型的には、受信者は、ビット列を受信すると、このビット列が要求される鍵を実際に表すものであるとみなしてしまうが、そのために対称型鍵システムでは特に問題が生じる。即ち、対称型鍵システムでは、典型的にはサイズが正しければどのようなビット列でも鍵であると解釈されてしまう。このビット列の中の１ビットが所定の鍵と異なっていても、別の鍵として解釈されるので、その鍵が誤ったものでない限り、妥当な暗号演算（ｃｒｙｐｔｏ ｏｐｅｒａｔｉｏｎ）を行うことができる。
【０００９】
非対称型秘密鍵システムでは、秘密鍵の所有者はその秘密鍵について全て知っているので、それが正しいか否かの妥当性を検証することができる。しかしながら、第３者が上記所有者のシステムに公開鍵を送信した場合、受信した鍵が公開鍵の算術的要件に合致するものか否か、あるいはその要求された公開鍵を用いて演算（ｏｐｅｒａｔｉｏｎ）を行った場合に機密性が確保された暗号演算となるか否かについては、疑問が生じる。所有者のシステムが検査を行わなければ確実には分からないので、所有者にしか分からないことになる。
【００１０】
以上のことから分かるように、鍵の確立は安全でない場合がある。Ｃｒｙｐｔｏ ’９７で発表されたリン（Ｌｉｍ）およびリー（Ｌｅｅ）による論文では、上記問題点が、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ方式において次数（ｏｒｄｅｒ）が正しくない偽公開鍵を用いた場合に、相手側の秘密鍵に関する情報を得ることができるという例を用いて指摘された。ＲＳＡあるいはＲａｂｉｎ方式においては、公開鍵および秘密鍵を１組の大きな素数の関数とすることで、そのような大きな数の因数分解の困難性からセキュリティを確保している。これらの鍵は、２つの任意の大きな素数の積から生成している。しかしながら、ｎが素数であって、２つの素数の積でないとすると、ｐｈｉ（ｎ）＝ｎ−１が成り立つので、偽の「公開鍵」（ｎ，ｅ）から誰でもｄを決定することができる。これらは、公開鍵の使用者が、要求された公開鍵についてアルゴリズムの要件に合致する算術的属性の妥当性を検証することができないが為に生じる問題であると言える。
【００１１】
本発明は、セキュリティ機能を持つ通信システムにおいて、改良された妥当性検証を行うことを目的としている。さらに、本発明は、誰でもいつでも公開情報のみを用いてそのような妥当性検証を行えるようにすることを目的としている。
【課題を解決するための手段】
【００１２】
本発明の公開鍵通信システムにおけるディジタル署名の妥当性検証方法によれば、公開鍵の算術的属性がシステムアルゴリズムに合致することを確認する工程と、上記ディジタル署名を確認する工程とを含む。
【００１３】
さらに、システムパラメータを確認する工程が設けられる。
【００１４】
さらに、要求された公開鍵がアルゴリズムと算術的に合致するか否かの妥当性検証が実行されたことを示す情報と、および適切な場合には、さらに、実行された妥当性検証の回数を示す情報とを証明書情報内に含める工程が設けられる。
（項目１）
データ通信システムにおいて、一方から他方の通信者に送信されるディジタル情報の妥当性を検証する方法において、
所定の算術的属性とシステムパラメータとを有する所定の暗号化方式に応じて公開鍵を生成する工程と、
上記公開鍵が上記暗号化方式の算術的属性に合致することを確認する工程と、
確認された上記公開鍵を受信者に送信する工程とを含むことを特徴とする方法。
（項目２）
上記公開鍵の妥当性が検証されたことを示す情報を、確認された上記公開鍵と共に送信することを特徴とする項目１に記載の方法。
（項目３）
上記公開鍵は楕円曲線公開鍵Ｑであり、上記暗号化方式は楕円曲線方式であることを特徴とする項目１に記載の方法。
（項目４）
上記公開鍵を確認する工程は、上記公開鍵Ｑが上記楕円曲線Ｅ上にあることを確認する工程を含むことを特徴とする項目３に記載の方法。
（項目５）
上記システムパラメータを確認する工程をさらに含むことを特徴とする項目１に記載の方法。
（項目６）
公開鍵および対称型鍵を有するセキュリティが確保された非対称型通信システムを提供する方法において、
上記公開鍵が妥当であると確認する工程と、
上記対称型鍵が所定のフォーマットを有することを確認する工程と、
上記対称型鍵を復号する工程と、
復号された上記対称型鍵が所定の妥当なフォーマットを有することを確認する工程とを含むことを特徴とする方法。
（項目７）
上記システムパラメータが妥当であると確認する工程をさらに含むことを特徴とする項目６に記載の方法。
（項目８）
公開鍵、対称型鍵、および秘密情報を有する通信システムにてセキュリティが確保された鍵一致を提供する方法において、
上記公開鍵が妥当であると確認する工程と、
上記秘密情報が妥当であると確認する工程と、
上記対称型鍵が妥当であると確認する工程とを含むことを特徴とする方法。
（項目９）
システムパラメータが妥当であると確認する工程をさらに含むことを特徴とする項目８に記載の方法。
（項目１０）
上記鍵の検証を示す情報を証明書情報に含める工程をさらに含むことを特徴とする項目８に記載の方法。
【図面の簡単な説明】
【００１５】
【図１】通信システムの概略図である。
【発明を実施するための形態】
【００１６】
（発明の実施の形態）
図１に示すように、データ通信システム１０は、１組の通信者を含み、該１組の通信者は、送信者１２および受信者１４であり、互いに通信チャネル１６により接続されている。送信者１２および受信者１４は、通信チャネル１６を介した送受信用に備えてディジタル情報を処理する暗号化ユニット１８および２０をそれぞれ有している。データ通信システム１０は、証明書発行局（ＣＡ；ｃｅｒｔｉｆｉｃａｔｉｏｎ ａｕｔｈｏｒｉｔｙ、認証機関とも言う）２２をさらに有していてもよい。
【００１７】
以下、本発明の実施の形態として、公開鍵アルゴリズムを用いた場合について説明する。鍵一致は、以下に示す６つのルーチンを有している。即ち、システムパラメータの生成、システムパラメータの妥当性検証、鍵対の生成、公開鍵の妥当性検証、共用機密の導出（ｄｅｒｉｖａｔｉｏｎ）、および対称型鍵の導出である。上記鍵検証工程においては、誰でもいつでも公開情報のみを用いて公開鍵の妥当性を検証することができる。これらのルーチンにより、公開鍵の値域（ｒａｎｇｅ）および次数（ｏｒｄｅｒ）が検証される。公開鍵の妥当性が検証されれば、論理的にはそれに対応する秘密鍵が存在する可能性があるが、実際に存在することは証明されない。
【００１８】
楕円曲線ディジタル署名アルゴリズム（ＥＣＤＳＡ）にも、６つのルーチンが含まれる。即ち、システムパラメータの生成、システムパラメータの妥当性検証、鍵対の生成、公開鍵の妥当性検証、署名の生成、および署名の確認（ｓｉｇｎａｔｕｒｅ ｖｅｒｉｆｉｃａｔｉｏｎ）である。一方、ＤＳＡの第１のタイプには、４つのルーチン、即ち、システムパラメータの生成、鍵対の生成、署名の生成、および署名の確認が含まれる。より最近のＤＳＡでは、５つのルーチン、即ち、システムパラメータの生成、（非明示の（ｉｍｐｌｉｃｉｔ））システムパラメータの妥当性検証、鍵対の生成、署名の生成、および署名の確認が含まれる。鍵の妥当性検証を行うために、ＤＳＡパラメータであるｐ、ｑ、およびｇは既に妥当性が検証されているものとみなす。秘密鍵をｘ、公開鍵ｙはｙ＝ｇｘ ｍｏｄ ｐである。そして、ｙの値域について、１＜ｙ＜ｐであることを確認することによって妥当性を検証するとともに、ｙの次数について、ｙｑ ｍｏｄ ｐ＝１であることを確認することによって妥当性を検証する。これらの妥当性検証により、ある要求されたＤＳＡ公開鍵が、そのような鍵に対する算術的要件を満たすものであるということが確認される。これらの妥当性検証は、誰もがいつでも公開情報のみを用いて実行することが可能である。
【００１９】
ＲＳＡあるいはＲａｂｉｎ署名アルゴリズムには、一般に３つのルーチン、即ち、鍵対の生成、署名の生成、および署名の確認が含まれる。ＲＳＡ公開鍵（ｎ，ｅ）の検証は以下の３つのステップを含む。即ち、まず最初にｅの妥当性を検証し、次にｎの妥当性を検証し、その次にｅおよびｎが互いに矛盾していないことを検証する。公開指数ｅの妥当性を検証するためには、指数ｅが２≦ｅ≦２（ｋ−１６０） （ｋは法（ｍｏｄｕｌｕｓ）ｎのビット長（ｌｅｎｇｔｈ））であることを利用する。指数ｅの範囲が上記のような特定された範囲であるべきというこの要件は、特に、ここでの検証を実現可能にしている。ｅ＞２であれば、ｅは奇数でなければならない。さらに、閉じたネットワークの場合には、公開指数ｅは他の全ての判定基準を満たすべきであることが知られている。即ち、例えばｅは３か、６５５３７か、あるいは６５５３７より大きな任意の数でなければならないといった判定基準である。これらの検証は、鍵の妥当性をさらに確認するために行ってもよい。これらの検証については、ＲＳＡ公開鍵部分認証ルーチン（ｐｕｂｌｉｃ ｋｅｙ ｐａｒｔｉａｌ ｖａｌｉｄａｔｉｏｎ ｒｏｕｔｉｎｅ）の仕様（ｓｐｅｃｉｆｉｃａｔｉｏｎ）の一部として含まれていてもよい。上記の指数ｅの検証は簡略なもののように見えるが、この検証により、ＲＳＡ／Ｒａｂｉｎアルゴリズムで選択が試みられるｄよりも前にｅが選択されたことが確認できる。なぜなら、この検証により、ｄｅ＝１ ｍｏｄ（ｌｃｍ（ｐ−１，ｑ−１））であり、法ｎに比べてｅでは桁数を表すゼロが少なくとも１６０個多いことが分かり、これはｄを先に選択すると実現不可能だからである。
【００２０】
法ｎの妥当性を検証するためには、ｎの大きさを求める。ｎは、正確に（１０２４＋１２８ｓ）ビット（ただし、ｓ＝０，１，２，３，…等）を含まなければならないことが知られている。このことは、簡単に検証でき、部分鍵認証の一部とすることができる。法ｎは２つの素数の積で、２より大きい全ての素数が奇数であることから、法ｎが奇数であるか否か判断することによって、法ｎに対してさらなる妥当性検証を行ってもよい。したがって、奇数同士の積は奇数であるので、ｎは奇数でなければならない。さらに、Ｒａｂｉｎアルゴリズムでｅ＝２の場合には、ｐ＝３ ｍｏｄ ｎ、およびｑ＝７ ｍｏｄ ８でなければならないことが分かっている。このことから、ｎ＝ｐｑ＝２１ ｍｏｄ ８＝５ ｍｏｄ ８でなければならない。このことは、ｅ＝２のときにｎ＝５ ｍｏｄ ８であることを確認することで検証できる。さらに、ｎは完全な累乗（ｐｅｒｆｅｃｔ ｐｏｗｅｒ）であってはならないことが分かっている。このことから、ｎが２つの異なる素因数からなることが確実に分かり、単純な検査により妥当性が検証できる。上記検証については、Ｍｅｎｅｚｅｓ、ｖａｎ Ｏｏｒｓｃｈｏｔ、およびＶａｎｓｔｏｎｅによる”Ｈａｎｄｂｏｏｋ ｏｆ Ａｐｐｌｉｅｄ Ｃｒｙｐｔｏｇｒａｐｈｙ（応用暗号手法ハンドブック）”に記述されている。
【００２１】
また、ｎは合成数でなければならないことも知られている。したがって、ｎが素数の場合には、容易に逆変換が可能になるため、セキュリティが全く確保されなくなる。ｎが合成数であるか否かの検証は、ｎが合成数であると実際に証明されると予想してＭｉｌｌｅｒ−Ｒａｂｉｎ確率的素数検証（ｐｒｏｂａｂｌｅ ｐｒｉｍｅ ｔｅｓｔ）を行うことによって、実現可能である。法ｎの検証を行うためのさらなる検査は、以下のことに基づくものである。即ち、ｎが２つの大きな素数の積であって、因数分解が難しく、したがって単純な方法で因数分解しようとしても成功しないものであることが分かっていることに基づいている。例えば：ｉとして小さな奇数の素数からある程度の大きさまでの全ての素数、例えば最初の５００００（５０Ｋ）個の奇数の素数について、ＧＣＤ（ｎ，ｉ）を計算してみてもよい。
【００２２】
前述の２つの検証により、前者からは少なくとも１つの因子が法のビットの半分以下の大きさでなければならないことが分かり、後者からは各因子が検証した最大素数よりも大きくなければならないことが分かる。さらに、ポテンシャル因子（ｐ，ｑ，ｒ，…）は、上記で検証した最大素数の大きさに依存した限られた数しか存在しなくなる。
【００２３】
以上の複数の検証を組み合わせると、相乗効果が得られる。検証の目的は、敵のとりうる行動の自由度を大幅に小さくすることである。攻撃がほぼ不可能な場合であっても、部分的鍵認証を行うことによって、攻撃をより一層困難にし、望ましくは攻撃を不可能あるいは少なくとも非経済的なものにすることができる。
【００２４】
さらに、ｐおよびｑの値は近くなりすぎてはならないものであるから、法ｎを検証する際には、これらが近接した値であると仮定し、ｎの因数分解を試みる。ｎの平方根をｐおよびｑの初期予想値とする。ｐを減少させる一方、ｑを増加させ、ｎが所定の限度まで因数分解できるか決定する。さらに、ＲＳＡの法のセットでは素数が繰り返してはならないことが分かっているため、ＲＳＡのある法のセットｎ１、ｎ２に対して、ＧＣＤ（ｎｉ，ｎｊ）を計算し、全ての計算結果が１に等しいことを確認することができる。
【００２５】
上述のオフライン検証には限界が存在するが、パラメータの所有者が特定の情報、例えばｎの因数分解を知っているので、これらの検証を拡張することができる。よって、所有者をオンラインオラクル（ｏｒａｃｌｅ）として利用してもよい。このオラクルに関してなされる質問に対する回答が不正解であることを識別することで、誰もが公開鍵が無効であると断言できることになる。
【００２６】
Ｖａｎｓｔｏｎｅらの”Ｈａｎｄｂｏｏｋ ｏｆ Ａｐｐｌｉｅｄ Ｃｒｙｐｔｏｇｒａｐｈｙ”によれば、所有者は（平方根 ｍｏｄ ｎ）を計算できるが、他者にはできない。検証者は、（任意値 ｍｏｄ ｎ）のヤコビ符号（ヤコビアン；Ｊａｃｏｂｉ Ｓｙｍｂｏｌ）を１または−１に決定し、半分は１、他方の半分は−１に決定する。１の場合には、その数が平方数か否かで、再度半々に分けられる。検証者は、（ある数 ｍｏｄ ｎ）を平方する。平方数のヤコビ符号は、常に１である。
【００２７】
検証者は、既知の平方数ｕおよびヤコビ符号が１である任意の要素ｒのいずれかを選択する。そして、所有者にこの２種類の要素に対して「これは平方数であるか」と質問する。所有者は、イエスかノーかで回答する。ｕが選択された場合、所有者がイエスと答えなければ鍵の法（ｍｏｄｕｌｕｓ）は無効となる。ｒが選択された場合、所有者がイエスと答える回数とノーと答える回数とがそれぞれ約半分でなければ、鍵の法が無効となる。
【００２８】
これを何度も繰り返すことにより、信頼性が高まる。検証者が全て平方数について所有者に質問した場合には、所有者は常にイエスと答えなければならない。検証者が全てヤコビ符号が１である任意の要素について所有者に質問した場合には、所有者はその半分にはイエスと答え、半分にはノーと答えなければならない。偽鍵の所有者は、少なくとも半分の答えがイエスであることを知っているだけである。しかしながら、秘密鍵の所有者であれば、ｎの因数分解を知っており、平方数を知っているので、擬似平方数についてそれらが平方数であると嘘をついて、検証者を騙しさえすればよい。検証者は、既知の擬似平方数を用いて「これは平方数であるか」と質問するだけでよい。通常、法の因数分解を知らなければ、ある数がその法の擬似平方数であると決定することは不可能である。しかしながら、所有者は、上述の質問に対して、ヤコビが１である数のいくつかは擬似平方数であると答えなければならない。検証者は、既知の擬似平方数と（平方数ｍｏｄ ｎ）とを掛け合わせることによって、任意の既知の擬似平方数を生成することはできる。検証者は、その結果として得られた値については、擬似平方数であると知っている。この３つめのタイプの数ｔ（既知の擬似平方数）について所有者に尋ねると、この場合には、所有者がいくつかの擬似平方数は平方数であると嘘をついても、その嘘が検証者に知られる。
【００２９】
ｅとｎとを共に検証するには、ＧＣＤ（ｅ，ｐ−１）＝１、かつＧＣＤ（ｅ，
ｑ−１）＝１でなければならない。ｅが奇数の場合には、整数ｘおよびｐに対してｐがｘｅ＋１の形で表されない数であり、かつ、整数ｙに対してｑがｙｅ＋１の形で表されない数でなければならないことが分かっている。ｐとｑとの両方が不正な場合には、ｎがｘｙｅ２ ＋ｘｅ＋ｙｅ＋１の形で表されないものであり、かつｎ≠１ ｍｏｄ ｅが成り立たなければならない。
【００３０】
ｅとｎとを共に検証する別の方法について以下に説明する。ＧＣＤ（ｅ，ｐｈｉ（ｎ））が１でなければならないことが分かっている。ｐｈｉ（ｎ）＝（ｐ−１）（ｑ−１）であることが分かっているので、式が２つで未知数が２つであるから、検証者は、ｎを因数分解することができる。
【００３１】
鍵対に対する他の要件が満たされているとする。ＧＣＤ（ｅ，ｐｈｉ（ｎ））＝１を満たす必要があるのは、ｅを用いた演算を確実に１：１対応（逆変換可能）の関数とするためである。さもなければ、ｅを用いた演算が多数：１になってしまう。ｅを用いた演算が多数：１対応の場合には、ｄ（ｅの逆元（ｉｎｖｅｒｓｅ））が存在しなくなるか、少なくとも通常では導き出せなくなる。所有者はｄが実際に存在するという証拠を提示しなければならない。しかしながら、上記質問は、秘密鍵の所有者の管理の元で行うべきではない。即ち、所有者自身で署名した証明書要求（ｓｅｌｆ−ｓｉｇｎｅｄ ｃｅｒｔｉｆｉｃａｔｅ ｒｅｑｕｅｓｔ）では、十分な証拠とはならない。
【００３２】
挑戦者は、承認を要求された所有者にダミーメッセージをいくつか送信して署名させることもできる。秘密鍵の所有者は、それらがダミーメッセージであると確認し、署名し、挑戦者に返信する。これは、ｄが存在するオンライン確率的オラクル検証（ｏｎｌｉｎｅ
ｐｒｏｂａｂｉｌｉｓｔｉｃ ｏｒａｃｌｅ ｔｅｓｔ）である。
【００３３】
したがって、誰でもオフライン検証がいつでも実行できる。所有者がオンライン状態にあれば、誰でもオンライン検証を実行できる。所有者は、オフラインおよびオンライン検証を行って、自身の秘密鍵が有効であることを確認することができる。ＣＡは、オンライン検証を行って、公開鍵証明書において何の妥当性がどの程度まで検証されているかを他者に伝える。
【００３４】
ＥＣＤＳＡにおけるシステムパラメータは、フィールドサイズｑ＝ｐまたは２ｍ である。オプションの種（ｏｐｔｉｏｎａｌ ｓｅｅｄ）によって（ａ，ｂ）が生成され、（ａ，ｂ）によって、曲線の次数がｈｎとなるように、Ｆｑ で表される楕円曲線、この曲線上の特異点Ｐ、Ｐの大きな素数の次数（ｌａｒｇｅ ｐｒｉｍｅ ｏｒｄｅｒ）であるｎ、および余因子（ｃｏｆａｃｔｏｒ）ｈを定義する。（ａ，ｂ）で定義されるフィールドサイズＥＣおよび点Ｐは主要パラメータである。
【００３５】
ＥＣシステムパラメータだけでなく、ＥＣ公開鍵についても確認することが重要である。例えば、楕円曲線公開鍵Ｑを想定し、ＱがＥ上にあるとする。鍵一致において素数の次数の曲線を使用している場合、Ｑの次数を検査する必要はない。なぜなら、Ｑが曲線上にあれば正確な次数を有していることが確かであるからである。Ｑが曲線上にあることを検査することは重要である。なぜなら、Ｑが曲線上になければ、偽鍵が、ａＱを計算する際に秘密鍵ａを明かしてしまうからである。公開鍵が曲線上にあると確認することは、曲線の式に代入するか、検証を行うことにより可能である。
【００３６】
以上のことから、鍵認証を行うことにより、攻撃にさらされることが抑制され、不慮のエラーの検出が助けられ、ＣＡが行う価値のあるサービスが提供されることになる。当業者ならば理解できるように、上記の技術および方法は、本発明の工程を実行する適切なプロセッサにおいて実現することができる。さらに、上述の様々な方法は、汎用のコンピュータを使用し、ソフトウェアにて選択的に起動あるいは再構成して実行するのが便利がよいが、当業者ならば理解できるように、そのような方法は、必要な各工程を実行するように構成された、ハードウェア、ファームウェア、あるいはより特殊な装置において実現してもよい。
(発明の効果)
【００３７】
本発明によれば、セキュリティ機能を持つ通信システムにおいて、改良された妥当性検証を行うことができる。さらに、本発明によれば、誰でもいつでも公開情報のみを用いてそのような妥当性検証を行うことが可能となる。
【特許請求の範囲】
【請求項１】
本願明細書に記載された発明。
【請求項１】
本願明細書に記載された発明。
【図１】
【公開番号】特開２０１３−４２５５５（Ｐ２０１３−４２５５５Ａ）
【公開日】平成２５年２月２８日（２０１３．２．２８）
【国際特許分類】
【出願番号】特願２０１２−２５１２３１（Ｐ２０１２−２５１２３１）
【出願日】平成２４年１１月１５日（２０１２．１１．１５）
【分割の表示】特願２０１０−５３６３（Ｐ２０１０−５３６３）の分割
【原出願日】平成１０年１０月１４日（１９９８．１０．１４）
【出願人】（３９７０７１７９１）サーティコム コーポレーション (38)
【Ｆターム（参考）】
【公開日】平成２５年２月２８日（２０１３．２．２８）
【国際特許分類】
【出願日】平成２４年１１月１５日（２０１２．１１．１５）
【分割の表示】特願２０１０−５３６３（Ｐ２０１０−５３６３）の分割
【原出願日】平成１０年１０月１４日（１９９８．１０．１４）
【出願人】（３９７０７１７９１）サーティコム コーポレーション (38)
【Ｆターム（参考）】
[ Back to top ]