(57)【特許請求の範囲】
【請求項１】
プロセッサとメモリとを備えたコンピュータにおいて、公開鍵および非公開鍵から形成される公開鍵のペアを有する公開鍵暗号法を用いて真正な署名を生成するための方法であって、この方法は、
前記プロセッサが、入来するメッセージＭに対して真正な署名を形成するステップを含み、前記形成のステップは、
前記メモリに記憶された前記非公開鍵、
前記メッセージ、
前記メモリに記憶された、有限体上の楕円曲線上の複数の点から選択された予め定められた生成元の値ならびに
前記公開鍵および前記非公開鍵とは異なり、公開鍵暗号法におけるいずれのキーペアの公開鍵または非公開鍵でもない秘密鍵に応答する、方法。
【請求項２】
前記形成のステップは、
前記プロセッサが、前記生成元の値、前記秘密鍵および前記メッセージに応答して、前記真正な署名の第１の部分を生成するステップと、
前記プロセッサが、前記真正な署名の第１の部分ならびに前記秘密鍵および前記非公開鍵に応答して、前記真正な署名の第２の部分を生成するステップとを含む、請求項１に記載の方法。
【請求項３】
前記形成のステップは、
前記プロセッサが、前記秘密鍵の予め定められた擬似乱数の関数として第１のパラメータの値を生成するステップと、
前記プロセッサが、前記真正な署名の第１の部分を前記第１のパラメータの値、生成元の値およびメッセージの予め定められた関数として決定するステップとをさらに含む、請求項２に記載の方法。
【請求項４】
予め定められた擬似乱数の関数が第１の予め定められたハッシュ関数を含む、請求項３に記載の方法。
【請求項５】
前記秘密鍵は第１の鍵の部分（Ａ1）および第２の鍵の部分（Ａ2）の連結で形成され、前記第１のパラメータの値（ｋ）は以下の式を介して決定され、
【数１】
0004644368.tif 000010
この式ではＳＨＡ＿１はＳＨＡ＿１のハッシュ関数である、請求項４に記載の方法。
【請求項６】
前記第１のパラメータの値を入力として予め定められた擬似乱数の関数に適用し、前記第１のパラメータの値に対し新たな値を与えるステップをさらに含む、請求項４に記載の方法。
【請求項７】
プロセッサとメモリとを備えたコンピュータにおいて、メッセージに対して、公開鍵、非公開鍵および秘密鍵を有する公開鍵暗号法を用いて生成された署名を認証するための方法であって、前記秘密鍵は前記公開鍵および前記非公開鍵とは異なり、この方法は、
前記プロセッサが、前記署名から第１および第２の部分を抽出し、署名の抽出された第１および第２の部分を与えるステップと、
前記プロセッサが、前記メモリに記憶された有限体上の楕円曲線上の複数の点から選択された予め定められた生成元の値、前記メッセージならびに前記署名の抽出された第１および第２の部分に応答して、署名の第１の部分の新たな値を決定するステップと、
前記プロセッサが、前記第１の部分の新たな値が抽出された前記第１の部分と一致するか否かを確認し、前記署名が真正か否かを示すステップとをさらに含む、方法。
【請求項８】
入来するメッセージに応答して、公開鍵および非公開鍵から形成される公開鍵のペアを有する公開鍵暗号法とともに用いる、当該メッセージに対して真正な署名を生成する装置であって、この装置は、
プロセッサと
前記非公開鍵および有限体上の楕円曲線上の複数の点から選択された予め定められた生成元の値を記憶するメモリとを含み、
前記プロセッサは、入来するメッセージＭに対して、当該メッセージ、前記非公開鍵、前記生成元の値および前記公開鍵および前記非公開鍵とは異なり、公開鍵暗号法におけるいずれのキーペアの公開鍵または非公開鍵でもない秘密鍵に応答して、真正な署名を形成
する、ように構成されている、装置。
【請求項９】
前記プロセッサは、
前記生成元の値、前記秘密鍵および前記メッセージに応答して、前記真正な署名の第１の部分を生成し、
前記真正な署名の第１の部分ならびに前記秘密鍵および前記非公開鍵に応答して、前記真正な署名の第２の部分を生成する、ように構成されている、請求項８に記載の装置。
【請求項１０】
メッセージに対して、公開鍵、非公開鍵および秘密鍵を有する公開鍵暗号法を用いて生成された署名を認証するための装置であって、前記秘密鍵は前記公開鍵および前記非公開とは異なり、この装置は
プロセッサと
有限体上の楕円曲線上の複数の点から選択された予め定められた生成元の値を記憶するメモリとを含み、
前記プロセッサは、
前記署名から第１および第２の部分を抽出し、署名の抽出された第１および第２の部分を与え、
前記メモリに記憶された前記生成元の値、前記メッセージならびに前記署名の抽出された第１および第２の部分に応答して、署名の第１の部分の新たな値を決定し、
前記第１の部分の新たな値が抽出された前記第１の部分と一致するか否かを確認し、署名が真正か否かを示す、ように構成されている、装置。
【請求項１１】
プロセッサとソフトウェアを記憶したメモリとを備えたコンピュータにおいて、当該ソフトウェアに対応するソフトウェアの複製と関連した、真正な署名を含む、認証データを生成するための方法であって、真正な署名は公開鍵および非公開鍵を有する公開鍵暗号法と関連して用いられ、前記方法は、
前記プロセッサが、前記ソフトウェアの複製に対してメッセージＭとして一意な識別子を割当てるステップと、
前記プロセッサが、前記メッセージ、前記メモリに記憶された有限体上の楕円曲線の上の複数の点から選択された予め定められた生成元の値ならびに公開鍵および非公開鍵とは異なり、公開鍵暗号法におけるいずれのキーペアの公開鍵または非公開鍵でもない秘密鍵に応答して真正な署名を生成するステップと、
前記プロセッサが、前記識別子および前記真正な署名に応答して認証データを形成するステップと、
前記プロセッサが、前記ソフトウェアの複製と前記認証データを関連づけるステップとを含む、方法。
【請求項１２】
前記認証データ形成のステップは、前記プロセッサが、前記識別子を前記真正な署名と連結して前記認証データを与えるステップを含む、請求項１１に記載の方法。
【請求項１３】
前記割当てのステップは、前記プロセッサが、所与の範囲内の乱数の値またはその範囲内の予め定められたシーケンス内の次に利用可能な数のいずれかとして前記一意な識別子を選択するステップを含む、請求項１２に記載の方法。
【請求項１４】
前記生成のステップは、
前記プロセッサが、前記生成元の値、前記秘密鍵および前記メッセージに応答して、前記真正な署名の第１の部分を生成するステップと、
前記プロセッサが、前記真正な署名の第１の部分ならびに前記秘密鍵および前記非公開鍵に応答して、前記真正な署名の第２の部分を生成するステップとを含む、請求項１３に記載の方法。
【請求項１５】
前記生成のステップは、
前記プロセッサが、前記秘密鍵の予め定められた擬似乱数の関数として第１のパラメータの値を生成するステップと、
前記プロセッサが、前記第１のパラメータの値、前記生成元の値および前記メッセージの第１の予め定められた関数として、前記真正な署名の第１の部分を決定するステップとをさらに含む、請求項１４に記載の方法。
【請求項１６】
前記予め定められた擬似乱数の関数が第１の予め定められたハッシュ関数を含む、請求項１５に記載の方法。
【請求項１７】
前記秘密鍵は第１の鍵の部分（Ａ1）および第２の鍵の部分（Ａ2）の連結で形成され、前記第１のパラメータの値（ｋ）は以下の式を介して決定され、
【数２】
0004644368.tif 000011
この式ではＳＨＡ＿１はＳＨＡ＿１のハッシュ関数である、請求項１６に記載の方法。
【請求項１８】
前記プロセッサが、前記第１のパラメータの値を入力として予め定められた擬似乱数の関数に適用し、前記第１のパラメータの値に対し新たな値を与えるステップをさらに含む、請求項１７に記載の方法。
【請求項１９】
前記プロセッサが、前記第１のパラメータの値、前記非公開鍵および前記真正な署名の第１の部分の第２の予め定められた関数に応答して前記真正な署名の第２の部分を生成するステップと、
前記プロセッサが、前記真正な署名の第１および第２の部分を連結し、前記真正な署名を与えるステップとをさらに含む、請求項３または請求項１７に記載の方法。
【請求項２０】
前記真正な署名の第１の部分が以下の式に従って計算され、
【数３】
0004644368.tif 000012
この式ではｆは予め定められた安全な関数である、請求項１９に記載の方法。
【請求項２１】
前記関数ｆは予め定められたハッシュ関数である、請求項２０に記載の方法。
【請求項２２】
前記真正な署名の第２の部分（ｓ）が以下の式に従って計算され、
【数４】
0004644368.tif 000013
この式ではＸは非公開鍵であり、ｑは前記メモリに記憶された予め定められた素数である、請求項２０に記載の方法。
【請求項２３】
前記プロセッサが、前記認証データをアルファニューメリックの形式に変換してアルファニューメリックの認証データを与えるステップと、
前記コンピュータに関連付けられた出力手段が、前記ソフトウェアの複製の構成要素に添付するように、前記アルファニューメリックの認証データを出力するステップとをさらに含む、請求項２０に記載の方法。
【請求項２４】
プロセッサとメモリとを備えたコンピュータにおいて、当該コンピュータにインストールされるソフトウェアの複製と関連した認証データを認証するための方法であって、認証データは公開鍵暗号法を用いて生成されたソフトウェアの複製の識別子および関連づけられた署名を有し、公開鍵暗号法は公開鍵、非公開鍵および秘密鍵を有し、前記秘密鍵は前記公開鍵および前記非公開鍵とは異なり、この方法はコンピュータにソフトウェアの複製をインストールする間に、
前記プロセッサが、コンピュータにソフトウェアの複製をインストールする間にソフトウェアの複製に対する認証データを入手するステップと、
前記プロセッサが、前記認証データに含まれる署名を認証するステップとを含み、前記認証のステップは、
前記プロセッサが、前記認証データから署名の第１および第２の部分を抽出し、署名の抽出された第１および第２の部分ならびに識別子を与えるステップと、
前記プロセッサが、有限体上の楕円曲線上の複数の点から選択された予め定められた前記メモリに記憶された生成元の値、前記識別子ならびに前記署名の抽出された第１および第２の部分に応答して、前記署名の第１の部分の新たな値を決定するステップと、
前記プロセッサが、前記第１の部分の新たな値が前記抽出された第１の部分と一致するか否か確認し、前記認証データに含まれる前記署名が真正か否かを示すステップとを含み、
前記署名が真正か否かにより、前記プロセッサが、それぞれコンピュータにソフトウェアの複製のインストールを継続するかまたはインストールを終了する、方法。
【請求項２５】
前記決定のステップは、前記ソフトウェアの複製から前記生成元の値および公開鍵の値の記憶された値を入手するステップを含む、請求項２４に記載の方法。
【請求項２６】
前記新たな値を決定するステップは、前記プロセッサが、前記生成元の値、前記公開鍵、前記メッセージ、ならびに前記署名の抽出された第１および第２の部分の予め定められた関数として前記新たな値を生成するステップを含む、請求項７または請求項２５に記載の方法。
【請求項２７】
前記新たな値（＾ｒ）が以下の式に従って計算され、
【数５】
0004644368.tif 000014
この式ではｇpowは前記公開鍵であり、ＨＡＳＨは前記署名の生成に用いられる予め定められたハッシュ関数である、請求項２６に記載の方法。
【請求項２８】
前記予め定められたハッシュ関数がＳＨＡ＿１ハッシュ関数である、請求項２１または請求項２７に記載の方法。
【請求項２９】
前記有限体がガロア体上に定義される、請求項１８、２２または２７に記載の方法。
【請求項３０】
前記楕円曲線がｙ2＝ｘ3＋ｘの形式である、請求項１８、２２または２７に記載の方法。
【請求項３１】
請求項１、７、１３または２４に記載のプロセッサによるステップを、コンピュータのプロセッサに実行させるための、コンピュータで実行可能な命令を記憶したコンピュータで読取可能な記録媒体。
【請求項３２】
ソフトウェアの複製と関連した、真正な署名を含む、認証データを生成するための装置であって、真正な署名は公開鍵および非公開鍵を有する公開鍵暗号法と関連して用いられ、この装置は、
プロセッサと
前記非公開鍵および有限体上の楕円曲線上の複数の点から選択された予め定められた生成元の値を記憶するメモリとを含み、
前記プロセッサは、
前記ソフトウェアの複製に対してメッセージＭとして一意な識別子を割当て、
前記非公開鍵、前記メッセージ、前記生成元の値ならびに公開鍵および非公開鍵とは異なり、公開鍵暗号法におけるいずれのキーペアの公開鍵または非公開鍵でもない秘密鍵に応答して真正な署名を生成し、
前記識別子および前記真正な署名に応答して認証データを形成し、
ソフトウェアの複製と認証データを関連づける、ように構成されている、装置。
【請求項３３】
前記プロセッサは、前記識別子を前記真正な署名と連結し、認証データを与える、ように構成されている、請求項３２に記載の装置。
【請求項３４】
前記プロセッサは、所与の範囲内の乱数の値またはその範囲の予め定められたシーケンスの次に利用可能な数のいずれかとして前記一意な識別子を選択する、ように構成されている、請求項３３に記載の装置。
【請求項３５】
前記プロセッサは、
前記秘密鍵の予め定められた擬似乱数の関数として第１のパラメータの値を生成し、
前記真正な署名の第１の部分を前記第１のパラメータの値、前記生成元の値および前記メッセージの第１の予め定められた関数として決定する、ように構成されている、請求項８または請求項３４に記載の装置。
【請求項３６】
前記プロセッサは、
前記生成元の値、前記秘密鍵および前記メッセージに応答して、前記真正な署名の第１の部分を生成し、
前記真正な署名の第１の部分ならびに前記秘密鍵および前記非公開鍵に応答して、前記真正な署名の第２の部分を生成する、ように構成されている、請求項３４または３５に記載の装置。
【請求項３７】
前記予め定められた擬似乱数の関数が第１の予め定められたハッシュ関数を含む、請求項３６に記載の装置。
【請求項３８】
前記秘密鍵は第１の鍵の部分（Ａ1）および第２の鍵の部分（Ａ2）の連結で形成され、前記第１のパラメータの値（ｋ）は以下の式を介して決定され、
【数６】
0004644368.tif 000015
この式ではＳＨＡ＿１がＳＨＡ＿１のハッシュ関数である、請求項３７に記載の装置。
【請求項３９】
前記プロセッサは、前記第１のパラメータの値を入力として予め定められた擬似乱数の関数に適用し、前記第１のパラメータの値に対して新たな値を与える、ように構成されている、請求項３８に記載の装置。
【請求項４０】
前記プロセッサは、
前記第１のパラメータの値、前記非公開鍵および前記真正な署名の第１の部分の第２の予め定められた関数に応答して、真正な署名の第２の部分
を生成し、
前記真正な署名の第１および第２の部分を連結し、前記真正な署名を与える、ように構成されている、請求項３５に記載の装置。
【請求項４１】
前記真正な署名の第１の部分が以下の式に従って計算され、
【数７】
0004644368.tif 000016
この式ではｆが予め定められた安全な関数である、請求項４０に記載の装置。
【請求項４２】
前記関数ｆが予め定められたハッシュ関数である、請求項４１に記載の装置。
【請求項４３】
前記真正な署名の第２の部分（ｓ）が以下の式に従って計算され、
【数８】
0004644368.tif 000017
この式ではＸが非公開鍵であり、ｑが前記メモリに記憶された予め定められた素数である、請求項４１に記載の装置。
【請求項４４】
前記プロセッサは、
前記認証データをアルファニューメリックの形式に変換してアルファニューメリックの認証データを与え、
前記装置に関連付けられた出力手段が、前記ソフトウェアの複製の構成要素に添付できるように、前記アルファニューメリックの認証データの出力を制御する、ように構成された、請求項３９に記載の装置。
【請求項４５】
コンピュータにインストールされるソフトウェアの複製と関連した認証データを認証するための装置であって、認証データは前記ソフトウェアの複製の識別子および公開鍵暗号法を用いて生成された関連した署名を有し、前記公開鍵暗号法は公開鍵、非公開鍵および秘密鍵を有し、前記秘密鍵は前記公開鍵および前記非公開鍵とは異なり、この装置は、
プロセッサと
有限体上の楕円曲線上の複数の点から選択された予め定められた生成元の値を記憶するメモリとを含み、
前記プロセッサは、前記コンピュータに前記ソフトウェアの複製をインストールする間に、
前記コンピュータに前記ソフトウェアの複製をインストールする間に当該ソフトウェアの複製に対する認証データを入手し、
前記認証データから署名の第１および第２の部分を抽出し、署名の抽出された第１および第２の部分ならびに識別子を与え、
前記生成元の値、前記識別子ならびに前記署名の抽出された第１および第２の部分に応答して、署名の第１の部分の新たな値を決定し、
前記第１の部分の新たな値が抽出された前記第１の部分と一致するか否か確認し、前記認証データに含まれる署名が真正か否かを示し、
前記署名が真正か否かにより、それぞれコンピュータにソフトウェアの複製のインストールを継続するかまたはインストールを終了する、ように構成されている、装置。
【請求項４６】
前記プロセッサは、前記ソフトウェアの複製から前記生成元および公開鍵の値の記憶された値を入手する、ように構成されている、請求項４５に記載の装置。
【請求項４７】
前記プロセッサは、前記生成元の値、前記公開鍵、前記メッセージならびに前記署名の抽出された第１および第２の部分の予め定められた関数として前記新たな値を生成する、ように構成されている、請求項１０または請求項４６に記載の装置。
【請求項４８】
前記新たな値（＾ｒ）が以下の式に従って計算され、
【数９】
0004644368.tif 000018
この式ではｇpowが前記公開鍵であり、ＨＡＳＨが前記署名の生成に用いられる予め定められたハッシュ関数である、請求項４７に記載の装置。
【請求項４９】
前記予め定められたハッシュ関数がＳＨＡ＿１のハッシュ関数である、請求項４２または４８に記載の装置。
【請求項５０】
前記有限体がガロア体上に定義される、請求項３９、４３または４８に記載の装置。
【請求項５１】
前記楕円曲線がｙ2＝ｘ3＋ｘの形式である、請求項１０、３９、４３または４８に記載の装置。
【発明の詳細な説明】
【０００１】
【発明の分野】
この発明は暗号法に関し、特定的には、所与の署名すべきメッセージに対し、メッセージの署名者から発信されたものとして、署名されたメッセージの受信者によって非公開に認証され得る真正な暗号署名を生成し、かつそのような署名を適切に認証するための技術に関する。
【０００２】
【先行技術の説明】
何世紀にもわたり、情報が二人の個人の間で伝達される限り、情報は第三者によって傍受、盗聴、漏洩および／または破損されやすいものであった。そのような行為から情報を確実に保護するという問題が長きにわたり存在してきたのは明らかである。
【０００３】
伝統的にはこの問題は、長年にわたり、より複雑な暗号技術を開発することによって対処されてきた。これらの暗号技術の１種に鍵ベースの暗号の使用が含まれる。特定的には、鍵ベースの暗号を介して、全体的にメッセージを形成する理解可能なデータのシーケンスすなわち平文は、各々、暗号化アルゴリズムを介して一見しただけでは理解できないデータ、すなわちいわゆる暗号文に数学的に変換される。その変換は、暗号文はそれが対応するもとの平文に戻せなければならないという意味で完全に可逆、すなわち双方向でなければならないだけでなく、１対１対応に基づいていなければならない。すなわち各々の平文の要素は暗号文の１つかつ唯一の要素にのみ変換可能でなければならない。さらに、いずれの所与の暗号文を生成した特定の暗号も、暗号解析からは十分に安全でなければならない。秘密保持に必要なレベルを提供するためには、唯一の一意な対応する暗号を規定する一意な鍵が選択される。すなわち可能な限り多数の異なる鍵の各々が、同じ平文−暗号文対応関係の間の可逆変換をもたらすような状況を排除する。どのような暗号技術の強度も、したがってそれが与える第三者の侵入からの防御のレベルも、第三者がたとえば鍵ベースの暗号を用いて鍵の事前知識なしで暗号文をその対応する平文に変換する暗号解析に要する時間と正比例する。暗号解析を全く受け付けない暗号技術はないが、当時利用可能であったコンピュータ技術を考慮すると、事前にその鍵の知識なしに暗号を解読するのには膨大な数の計算および極めて長い時間が必要であるために、実際的な意図と目的とのすべてについては、多くの技術はそれらの幅広い採用および使用を正当化するに十分なほど安全である。その点では、ほんの数年前は、当時利用可能な情報処理技術の状態を鑑みれば、解読に人年（man-years）のオーダまたはそれ以上に長くかかるほど暗号が複雑ならば、その基本となる暗号技術はその使用を正当化するに十分な程度の安全性を有していると多くの人に考えられていた。
【０００４】
公開鍵アルゴリズムは鍵ベースの暗号の１つの形式である。このようなアルゴリズムでは、各々の情報伝達当事者が１対の公開−非公開鍵を生成する。各々は自分の公開鍵を公にアクセスが可能な掲示板、サーバまたは他の設備に公表し、対応する非公開鍵を秘密にしておく。本質的には、平文のメッセージを暗号化しそれを相手すなわち宛先に送信したい発信当事者は、この両者は同じ公開鍵アルゴリズムを用いるのだが、まず宛先当事者の公開鍵にアクセスし、その公開鍵を用いて平文のメッセージを暗号文のメッセージに暗号化し、暗号文のメッセージを宛先当事者に送信する。暗号文のメッセージを受取ると、宛先当事者はその非公開鍵を用いて、メッセージを解読し元の平文を回復する。鍵は非常に明確なアルゴリズムを用いて正確に計算され、完全な可逆性を保証しながら必要な安全レベルを提供している。
【０００５】
公開鍵暗号の解読に必要であると思われる純粋な作業数を考慮すると、公開鍵暗号システムは、その解読がはっきりと実行不可能であるという程度にまで安全性の高い暗号を提供しているが、そのようなシステムでもその使用を制限し得る欠点を有する。公開鍵システムの主要な欠点とは、その各々がかなり長いビットシーケンスを有する係数と、個別の鍵に対する依存性である。たとえばある係数は長さが容易に１０２４ビットとなり得るし、個別の鍵は数百ビットものシーケンスから形成され得る。アプリケーションによっては、たとえばそのような鍵が容易に記憶され、インデックス付けされ、かつ必要に応じてアクセスされ得る暗号アプリケーションプログラムでは、鍵の長さがユーザにとって実際的な問題を生ずることは、あるとしてもごくわずかである。しかし他のアプリケーションでは、そのような長い鍵のシーケンスは、仮にアルファニューメリックデータに変換されたとしても、依然としてユーザが簡単に手入力できないような長すぎる文字列を生成してしまうことがある。実際、公開鍵システムの高い安全性の要因はその鍵と係数の両者に非常に長いビットシーケンスを用いていることにある。係数が認め得るほど短くなってしまうと、暗号化されたメッセージが簡単に暗号解析されてしまうことになり、したがって、その基本となるシステムの安全性もすぐに危うくなる。
【０００６】
コンピュータ技術は急速に進化を続けている。ほんの数年前はその高い性能および速度について耳にしたこともなかったプロセッサが非常に安価な値段で商用的に利用可能となっている。その結果、多くのいわゆる「安全な」暗号を解読するには十分な処理能力を有しないと以前は見られていたパーソナルコンピュータおよびワークステーションのような情報処理システムが今や、その現在の能力と性能を考慮すると、第三者にそれらの同じ暗号を効果的に解読するのに必要な性能を提供している。１０年前は連続して計算しても何年もかかったであろうことが現在ではほんの少しの時間で達成される。このように、技術が進歩するにつれ、暗号技術は継続して取組むことで決まったやり方で進歩し、対応して進歩していく暗号解析に耐えるように高性能の暗号技術をますます発達させる。
【０００７】
暗号とは全く離れるが、少なくとも過去１０年の間、コンピュータのソフトウェア製造者は無許諾の第三者によりライセンスなしにその製品をかなり使用され、それは現在も続いている。これは、一部には、フレキシブルディスクまたはＣＤ−ＲＯＭのような、ソフトウェアプログラムを含む配布媒体が比較的簡単に複製できるためである。そのような無許諾での使用を防ぐために、比較的長いアルファニューメリックの認証データが各々のソフトウェア製品のパッケージの合法的な複製とともにしばしば配布され、ユーザがコンピュータにその複製をインストールする間に要求されれば、ユーザはその認証データを入力しなければならない。特に、この複製はインストールプログラムを含んでおり、ユーザはまずこれをロードしかつ実行してインストールのプロセスを開始し、順番にインストールのプロセス全体を実行する。典型的には、インストールのプロセスの早い段階で、インストールされる複製のユーザは認証データを手入力するようにプログラムに要求される。認証データはたとえば１０桁またはそれ以上の桁数を含んでもよい。コンパクトディスク（ＣＤ）を介して配布される場合は、認証データはＣＤを含む各々のケースに添付されたラベルに印刷される。フレキシブルディスクで配布される場合は、認証データは各々のソフトウェアパッケージの中に含まれる証明書または他の挿入物にしばしば印刷される。いずれにせよ、一旦ユーザが認証データを完全に入力し、典型的には画面上に現われる「ＯＫ」ボタン（または同様のもの）をクリックすることによりプログラムに信号を送ると、インストールプログラムはインストールされるその特定の複製がライセンスされたバージョンか否かを判断しようとしてその認証データの確認を試みる。認証データの有効性が確認されると、インストールのプロセスは進行する。有効でなければ、インストールは早期に終了する。すなわち、合法的に有効な複製を入手した各々のユーザ（すなわちライセンスを受けた者）は製造者によって提供されたパッケージ全体を所有し、したがって有効な認証データを有するが、添付のパッケージおよび／または挿入物のないプログラム自体の複製しか入手していない無許諾のユーザは認証データを有しないことが前提である。認証データの長さを考慮すると、ユーザが有効な認証データを当てずっぽうで選んでしまう可能性はかなり小さい。したがって、無許諾の複製をインストールしようとするユーザは間違った認証データを繰返し入力することが予測され、事実上入手したプログラムの複製をインストールすることができず、結果的にその複製は無用となる。
【０００８】
残念ながら実際には、そのような認証データを生成するための基本となるアルゴリズムは比較的簡単に識別できることが判明しており、かなり広くかつ違法に広まってしまったようである。したがって利用可能なアルゴリズムを考慮すると、無許諾のユーザでも多少作業をすれば、インストールしようとするプログラムの有効な認証データを入手することができる。このため、製造者はそのような無許諾の複製の使用を防ごうとしてしばしば失敗してしまう。
【０００９】
ソフトウェア製造者がその製品の無許諾の複製により収入を失っていることは明らかである。さらにソフトウェア製造者はいろいろな形態でその製品の顧客サポートをしばしば提供している。ライセンスを受けた人のみにそのようなサポートを限定するため、顧客サポートの担当者は、サポートを受ける条件として、ユーザがサポートを求める製品の複製と関連した認証データを提供するようユーザにしばしば求める。無許諾のユーザが簡単に有効な認証データを入手できることを考慮すると、ソフトウェア製造者が許諾された人にサポートを提供しながら無許諾のユーザにはサポートを拒否しようとしても、許諾された人と無許諾の人との区別が非常に困難となっている。その結果、製造者は知らないうちに無許諾のユーザにサポートを提供し、これにより追加のかつ不必要なサポートのコストがかかってしまう。所与のソフトウェア製品の無許諾のユーザの数が十分に多ければ、その製品と関連したこれらの超過コストはかなり大きくなり得る。
【００１０】
したがって、ソフトウェア製造者がそのソフトウェア製品の無許諾の複製の発生をかなり低減する技術に対する必要性が存在する。そのような技術によりその製品の各々の複製を独自に識別し、その特定の複製の認証が判断されなければならない。好ましくは、そのような技術は公開鍵システムを介して十分に安全な識別子を暗号的に生成するステップを含まなければならない（すなわちコンピュータ技術の現在の状況および今後予測される進化を考慮すると、第三者が鍵の知識なしに有効な識別子を生成することは不可能であろう）。さらに、識別子はその安全性を確実にするために十分に長くなければならず、しかし長くなりすぎて、必要なときたとえばインストールのプロセスまたは製品のサポートを受ける間、識別子を手で入力しなければならないユーザを苛立たせてはならない。そのような技術を用いることにより、ソフトウェア製造者はそのソフトウェア製品の許諾なしの使用およびさもなければかかってしまう関連費用を大幅に低減することができるであろう。そうすることにより、次に、製造者がプロモーションのような他のサービスをライセンスを受けた顧客に提供することが経済的に可能となり、それにより製品と製造者両者に対する顧客の満足度を高めることができる。
【００１１】
【発明の概要】
この発明は、たとえば数字で表わされた、製品の複製の識別子のようなメッセージが与えられると、公開鍵暗号システムに基づき、かつ有限体上の楕円曲線上の点から選択された生成元の値を用いて、真正な暗号署名を形成することによりこのニーズを有利に満たし、かつ先行技術の欠点を克服する。この技術は３つの鍵、すなわち公開鍵、非公開鍵および秘密鍵と関連した生成元の値を用いて真正な署名を形成し、従来の２つの鍵の公開鍵暗号システムを介して生成された暗号署名と関連して実質的に安全性を高めている。
【００１２】
この発明を利用すると、現時点での実行の可能性と秘密鍵の知識がないということから、真正な署名を含む新たな署名されたメッセージのペアを生成するには公開鍵および非公開鍵を知っているだけでは大いに不十分である。
【００１３】
この発明の教示に従うと、特定の楕円曲線上の点を与えられると、曲線上のある点の値が生成元の値として選択される。非公開鍵は無作為に選択される。公開鍵は生成元の値と非公開鍵との予め定められた関数、特に前者の後者による冪乗として決定される。秘密鍵が用いられて擬似乱数を生成する。真正な署名の第１の部分が、予め定められた生成元の関数、擬似乱数およびメッセージ（無作為に選択された識別子）を介して生成される。特定的には、生成元は擬似乱数の値でまず冪乗され、その値が次にメッセージと連結される。その結果生じた連結した数は予め定められたハッシュ関数を介して処理され、真正な署名の第１の部分を与える。真正な署名の残余の部分は第１の部分、擬似乱数の値および非公開鍵の予め規定された関数に応答して生成される。真正な署名全体は両者の署名の部分をともに連結させることにより最終的に生成される。
【００１４】
ソフトウェア製品の複製とともに用いられるようなバイナリ値の認証データは識別子を真正な署名と連結させることにより形成される。バイナリ値の認証データはアルファニューメリックの形式に変換され、次に典型的にはその複製のパッケージに添付されるラベルに印刷されることにより製品の複製と関連付けられる。公開鍵および生成元の値は、クライアントコンピュータにインストールする間に、製品の複製自体の中の適切なファイル内に記憶され、複製のその後の認証の間に用いられる。
【００１５】
製品の複製のインストールの間、ユーザが入力した署名は、クライアントコンピュータで生成元の値、公開鍵、およびユーザが入力した認証データ全体、特にその識別子および署名を用いて署名の第１の部分を計算することにより認証される。その後、この第１の部分の値は、ユーザが入力した認証データに含まれる署名の同じ部分の値と比較され、これら２つの値が同一に一致するか否かを判断する。一致すれば、入力された署名は真正であり、この複製のインストールが進行する。一致しなければその署名は真正ではなく、インストールは早期に終了する。
【００１６】
製品の複製の認証データの生成と関連して、３つの別個の段階が用いられてこの発明が実現する。すなわち（ａ）さまざまなパラメータの値を生成するために一度、典型的にはソフトウェア製造者により行われる初期化、（ｂ）媒体複製場所で繰返し行なわれる、初期化の間に生成されたパラメータの値を用いて、異なる製品の複製ごとにその複製とともに用いられる真正な署名を含む対応する認証データを生成するための認証データの生成、および（ｃ）ユーザ側でインストールプログラムを実行する間に、ユーザにより入力されかつユーザがインストールしようとする特定の製品の複製と関連した認証データ内で署名を認証するために別個におよびその後に行なわれる認証である。
【００１７】
この発明の教示は添付の図面と関連した以下の詳細な説明を考察することにより容易に理解される。
【００１８】
理解を容易にするために、可能なところでは、同一の参照番号が図面に共通な同一の要素を示すように用いられている。
【００１９】
【詳細な説明】
以下の説明を考慮すると、この発明の教示が送信者側で所与のメッセージに対し暗号署名を生成する必要が生じる幅広い適用例のいずれにも用い得ることが当業者には明確に理解されるであろう。この発明は、共通の送信者すなわち署名者から発信される一意な一連のメッセージに対し署名が生成されるべき事例において、特に好適に用いられるが、それのみに限られるわけではない。その結果生じる署名の各々は高い安全性を与える、すなわち暗号解析が不可能であるだけでなく、その共通の署名者のみから発信されるものとして認証され得る。この点において、そのような署名の各々は１組の有効な署名の一部として公開鍵の使用により公に検証され、さらに秘密鍵を用いて非公開にかつ一意に認証され得る。さらに有利なことにはこの発明を用いると、第三者（意図された署名者ではない）がその受信者にとって有効に見えるような署名を不正に生成する方法を決定しようとしたとしても、その第三者はその受信者に対して特定の署名を適切に認証するという不可能な作業に直面する。以下の議論を単純にするために我々は、たとえばソフトウェア製品の特定の複製をクライアントパーソナルコンピュータ（ＰＣ）にインストールする間に、それを認証する目的で、ソフトウェア製品の所与の複製と署名自身が一意に関連付けられた、対応する認証データ内で用いられるべき署名を生成するという文脈で、この発明を論じる。
【００２０】
Ａ  使用環境
ＣＤ−ＲＯＭ生産システム５の単純化されてはいるがハイレベルのブロック図である図１を考察する。このシステムは、図示されたその基本的な形態では、コンピュータ１０、ＣＤ書込装置５０およびプリンタ６０を含む。このシステムは、ソフトウェアの製品パッケージに含まれるようなアプリケーションプログラムの完全な複製を集合的に実現するのに必要なファイルをすべて含むＣＤ−ＲＯＭを生産する。この製品はたとえばワードプロセッサプログラム、表計算プログラム、集合的に提供される１組のそのようなプログラム、オペレーティングシステムまたはその製造者によって一体として生産されかつ配布されるいずれのソフトウェア製品のパッケージであってもよい。
【００２１】
システム５は所与の複製を実現するのに必要なすべてのファイルを複製するだけでなく、このシステムは、一般的にラベルに印刷されてＣＤ−ＲＯＭを含むケースまたはＣＤ−ＲＯＭがそこに入れられる箱のいずれかに添付されたアルファニューメリックの認証データを生成する。この認証データは２つの役割を果たす。すなわち（ａ）それと関連付けられる特定のＣＤ−ＲＯＭを一意に識別する、および（ｂ）この発明を介して、その特定のＣＤ−ＲＯＭに対し暗号的に認証を与え、本質的に他には認証を与えない。後者の役割については、次に特定のＣＤ−ＲＯＭからＰＣに製品をインストールしながら（このプロセスは図２と関連しておよび図５に詳細に一般的に説明される）、ユーザが要求されて認証データを入力するたびに、認証手順がインストールプログラムの一部として実行され、ＣＤ−ＲＯＭ上に記憶された特定の情報（公開鍵および秘密鍵を含む）と関連して、ユーザが入力した認証データが製造者から与えられたものか、またこの特定のＣＤ−ＲＯＭに対し真正かを暗号的に判断する。
【００２２】
製造者は自身で使用するために多数の組の有効な認証データを生成し、またはその組を安全にその製品の製造の間に、許諾された第三者であるディスク複製者に配布できるが、所与の製品の複製に対してシステム５によって生成された各々のおよびすべての認証データはその対応する製品の複製に対し一意に認証され得る。このように、もし第三者がすべてのアプリケーションおよびインストールファイルを含むソフトウェアの違法な複製を入手したとしても、その複製が置かれる媒体を問わず、その特定の複製に対して適切に認証される認証データをその第三者が生成することは、有効な認証データのリストを所有していたとしても不可能である。
【００２３】
特に図１を参照すると、コンピュータ１０はアプリケーションプログラム２０および特にソフトウェア複製生成プログラム３０をローカルに記憶しかつ実行する。関連する範囲内で、プログラム３０は、ソフトウェア製品のパッケージの複製を集合的に実現するのに必要なすべてのファイルの複製を記憶するたとえばＣＤ−ＲＯＭを生産するプロセスを制御する。これらのファイルは、リモートコンピュータたとえばクライアントＰＣに製品を完全にインストールし、かつ実現するのに必要なすべてのプログラムファイル（あれば、関連したデータファイルを含む）およびインストールファイルを含む。コンピュータ１０内では、これらのファイルは、例えばローカルのハードディスクのようなプログラム記憶装置１５に集合的に存在するがそれに代えて、ネットワーク接続を介してリモートファイルサーバに実現されてもよい。これらのファイルは線１７で示されたように、ソフトウェア複製生成プログラム３０内で実行される従来のファイル複製プログラム３２を介して順にダウンロードされる。プログラム３２はダウンロードすべきファイルを特定し、プログラム記憶装置１５から順にこれらのファイルの各々にアクセスし、次に書込装置に挿入されたＣＤ−ＲＯＭ上にそのファイルを書込むように命令されると、各々のそのようなファイルをＣＤ書込装置５０にダウンロードする。以下に詳述されかつ特に図４と関連して述べられる認証データ生成プロセス４００は、典型的には長さが２５桁であるアルファニューメリックの認証データ７５を生成し、それはこれらのファイルが書込まれる特定のＣＤ−ＲＯＭと関連付けられる。一旦認証データがプロセス４００によって生成されると、図１に示されたようにこのプロセスはこの認証データをプリンタ６０に与え、プリンタは認証データをラベルに印刷する。すべてのファイルがＣＤ−ＲＯＭに複製されると、破線５５で示されたように、それは次にＣＤ−ＲＯＭケースのような好適なパッケージ７０に挿入される。破線６５で示されたように、このラベルはこのパッケージの外の面に添付される。プロセス４００は、プログラムファイルがＣＤ−ＲＯＭに書込まれまたは時間をずらした関係で書込まれながら、実質的に同時に認証データが生成されるように実行されてもよい。単純化するためにシステム５は単一のコンピュータ、単一のＣＤ書込装置および単一のプリンタを含むように示されているが、実際にはシステム５は所望により、パイプライン化されかつ並列にプログラムを複製する動作を実現する、通常はリモートファイルサーバにネットワークで接続された多数のコンピュータ、多数の書込装置および多数のプリンタを含んでもよい。
【００２４】
表示８０に示された認証データ７５は、識別子（ＩＤ）と、その後に続く、その識別子から生成された署名すなわちＳＩＧＮ（ＩＤ）とをその後に伴う識別子（ＩＤ）を含む領域８３および８７を含む。認証データの詳細な表示９０に示されるように、識別子はメッセージＭを含み、それはソフトウェア製造者が生産したすべての製品の各々およびすべての複製に対し一意な値を有する。例示的には、このメッセージは、バイナリ値に変換されると、製造者が生産したすべての製品にわたり与えられた、１つのソフトウェア製品のただ１つの複製にのみ与えられる３２ビットのバイナリ値の連続番号である。署名は、バイナリ値に変換されると、以下に詳述されかつこの発明では識別子を用いる製造者により形成される２つの値ｒおよびｓを連結したものである、例示的な８３ビットの値を含む（連結演算は以下に示す記号で表わされる）。
【００２５】
【数１０】
0004644368.tif 000002
【００２６】
図２は、図１で示されたシステム５を介して生産されたようなＣＤ−ＲＯＭからプログラムをインストールする間、例示的にこの発明を利用する典型的なクライアントコンピュータ２００の高レベルのブロック図である。
【００２７】
ここでは、線２０７で示されたように、ＣＤ−ＲＯＭからプログラムをインストールするためにユーザはクライアントコンピュータ２００と関連付けられたＣＤ−ＲＯＭドライブにＣＤ−ＲＯＭを挿入する。ユーザがマニュアルでコンピュータ２００に命令して、ＣＤ−ＲＯＭ上に記憶されたインストールプログラム２２０（典型的にはたとえばsetup.exeまたはinstall.exeという名称）の実行を開始するかまたは従来のオートラン機能を介してこのプログラムが自動的に実行されるかのいずれかであり、両者ともプログラム２２０と関連付けられかつそのときそのクライアントコンピュータ上で実行中のオペレーティングシステム上で実現される。インストールプログラム２２０はそのときクライアント上で実行中のアプリケーションプログラム２１０の１つとして実行される。プログラム２２０は、製品に対し予め定められたインストールのプロセスを実現するが、ＣＤ−ＲＯＭからローカルの大容量記憶装置に製品のプログラムファイルを転送する前に、認証プロセス５００を実行する。図５と関連して以下に詳述されるが、このプロセスはそこからプログラムがインストールされる特定のＣＤ−ＲＯＭと関連付けられた認証データをユーザが入力することを要求する。ユーザはこの要求に応じて、マニュアルで、典型的にはコンピュータ２００と関連したキーボードで、この特定のＣＤと関連した特定の２５桁のアルファニューメリック認証データを入力する。典型的にはコンピュータ２００と関連したローカルの画面に表示される適切なボタンをマウスでクリックすることにより認証データの入力を完了したことを一旦ユーザが示すと、認証データ内に含まれた情報、特にＭ、ｒおよびｓの値を含む情報ならびにＣＤ−ＲＯＭ自体に記憶された、以下に定められたような特定のデータの値を用いて、認証プロセス５００はユーザが入力した認証データが真正か、すなわちそれが製造者から与えられたものか、およびこの特定のＣＤ−ＲＯＭに関して真正かを判断する。
【００２８】
認証プロセス５００がユーザが入力した認証データの認証に成功すると、次にこのプロセスはインストールプログラム２２０（図２に図示）にそのように通知し、するとそのインストールプログラム２２０はインストールのプロセスを継続し、その後ＣＤ−ＲＯＭからクライアントコンピュータ２００に適切なプログラムファイルを複製する。しかしながらプロセス５００が認証データを認証しないと、次にプロセス５００はプログラムファイルをクライアントコンピュータ２００に全く複製せずにインストールプロセスを早期に終了する。認証データが認証されたか否かに基づき、認証プロセス５００は線２３０で示されたようにユーザに対し好適なメッセージを生成しかつ表示する。認証データが認証されるか否かにかかわらず、このメッセージはそれぞれ、インストールプロセスの認証後の段階の引続いての画面の生成および表示中に暗黙のうちに示されてもよいし、またはインストールされる複製の使用をユーザが許諾されないためインストールが終了することを示す特定の警告のメッセージでもよい。
【００２９】
図３はクライアントコンピュータ（ＰＣ）２００のブロック図である。
図示されたように、クライアントコンピュータ２００は入力インターフェイス（Ｉ／Ｆ）３２０、プロセッサ３４０、通信インターフェイス３５０、メモリ３３０および出力インターフェイス３６０を含み、すべてが従来どおりバス３７０によって相互接続される。メモリ３３０は、一般的には種々の様式を含み、たとえば一時的なデータおよび命令の記憶のためのランダムアクセスメモリ（ＲＡＭ）３３２、ユーザのコマンドによりフロッピーディスケットと情報を交換するためのディスケットドライブ３３４、典型的には磁気性であるハードディスクを介して実現される不揮発性大容量記憶装置３３５、およびＣＤ−ＲＯＭドライバ３３６を含む。この発明はＣＤ−ＲＯＭで配布されたソフトウェア製品とともに使用するという点で論じられているが、この発明はたとえばフロッピーディスケットのような他の一般向けの媒体で配布されるソフトウェア製品にも適用が可能であり、フロッピーディスケットの場合はその媒体がフレキシブルディスクドライブ３３４のような適切なドライブに挿入され、そこからインストールプログラムが読取られかつ実行される。大容量記憶装置３３５はまた、好適な光学記憶媒体から情報を読取る（かつそこに情報を書込む）別の光学媒体読取装置（図示せず）（または書込装置）を含んでもよい。さらに、大容量記憶装置３３５はまた、オペレーティングシステム（Ｏ／Ｓ）３３７およびアプリケーションプログラム２１０に対する実行可能な命令および関連したデータを記憶する。プログラム２１０はインストールプログラム２２０を含み、インストールプログラム２２０自身は、ソフトウェアのインストールのプロセスの間に一旦ロードされると、この発明の認証プロセス５００（図５を参照）を含む。図３に示されたＯ／Ｓ３３７は、ＷＩＮＤＯＷＳ  ＮＴオペレーティングシステム（”ＷＩＮＤＯＷＳ  ＮＴ”はワシントン州、レッドモンドのマイクロソフト・コーポレイションの登録商標である。）のようないずれの従来のオペレーティングシステムにより実現されてもよい。したがって、Ｏ／Ｓ３３７の構成要素はすべて関連がないため、ここでは論じない。インストールプログラム２２０はアプリケーションプログラム２１０の１つであり、Ｏ／Ｓの制御下で実行されるといえば十分であろう。
【００３０】
有利には、この発明技術は、ソフトウェア製品内で用いるために埋込まれると、インストールされる特定の製品の複製に対する認証データを入力する以外にユーザの行動を要求しない。
【００３１】
図３に示されたように、入来する情報は２つの例示的な外部ソースから、すなわちネットワークにより与えられる情報、たとえばインターネットからおよび／または他のネットワークに接続した設備からネットワーク接続３５５を介して通信インターフェイス３５０へ、または専用入力ソースから経路３１０を介して入力インターフェイス３２０へ発生し得る。専用入力は幅広い種類のデータソースから発生し、そのいずれもここでは特に無関係である。我々はこの発明をＣＤ−ＲＯＭからのローカルでのインストールに用いるという文脈で論じているが、この発明は、インターネットまたは他のネットワーク設備（たとえばイントラネット）のようなものを介した、コンピュータ２００への製品のネットワークインストールとともに用いられてもよい。この場合は、製造者またはサイトライセンス管理者が、製品の複製に対する電子的支払またはライセンスを受けた複製に対する正当に許諾された要求を受取ると、リモートネットワークファイルサーバからその製品の複製に対する対応する認証データを含むファイルを次にダウンロードできる。関連したインストールプログラムがファイルサーバ上でリモートで実行できるのであれば、そのときはサーバは認証データを含むクライアントに記憶されたファイルにアクセスし、さらにコンピュータ２００にいずれかのプログラムファイルをダウンロードする前に認証データを認証するステップに進む。代替的に、インストールプログラムがローカルで実行されるのならば、一旦すべてのプログラムファイルおよびインストールファイルがサーバによりダウンロードされると、サーバが（またはユーザがある後の時点で）ローカルでインストールプログラムの実行を開始する。このプログラムは認証データを含むファイルにローカルでアクセスし、製品の複製を認証するステップに進む。
【００３２】
入力インターフェイス３２０は適切な回路を含み、コンピュータシステム２００への入力情報の各々の異なる専用ソースを物理的に接続しかつインターフェイスするのに求められる、必要かつ対応する電気的接続を与える。オペレーティングシステムの制御下では、アプリケーションプログラム２１０はネットワーク接続３５５または経路３１０を介して、コマンドおよびデータを外部ソースと交換し、プログラムの実行中に典型的にはユーザによって要求された情報を伝送しかつ受取る。
【００３３】
さらに、入力インターフェイス３２０はまた、キーボードおよびマウスのようなユーザの入力装置３９５をコンピュータシステム２００に電気的に接続かつインターフェイスする。従来のカラーモニタのようなディスプレイ３８０および従来のレーザプリンタのようなプリンタ３８５は、導線３６３および３６７を介して、それぞれ出力インターフェイス３６０に接続される。出力インターフェイスは必要な回路を提供し、ディスプレイおよびプリンタをコンピュータシステムに電気的に接続かつインターフェイスする。一般的には、また認められるようにこの発明技術を利用すると、単に製品の複製の認証データを生成するだけではなく、それを介してクライアントコンピュータ２００がこれらのメッセージを入手し、記憶しおよび／または伝達する様式にも関わらず、ほとんどどのタイプのメッセージに対しても、一意な、安全なおよび真正な署名を生成することができる。
【００３４】
さらに、コンピュータシステム２００の特定のハードウェア構成要素、およびメモリ３３５内に記憶されるあらゆるソフトウェアの局面は、この発明を実現するモジュールを除いて従来のものでありかつ周知であるので、詳細には論じない。一般的に、コンピュータ１０はクライアントコンピュータ２００と類似のアーキテクチャを有する。
【００３５】
Ｂ  発明技術
この発明では、たとえば数字で表わされた製品の複製の識別子のようなメッセージが与えられると、公開鍵暗号システムに基づきかつ有限体上の楕円曲線上の点から選択された生成元の値を用いて、真正な署名がそのメッセージに対して生成される。この技術は例示的な署名者Ａのための３つの鍵、すなわち公開鍵（ＰＡ）、非公開鍵（ＳＡ）および秘密鍵（ＫＡ）と関連した生成元の値を用いて真正な署名を生成することに依存している。
【００３６】
公開鍵暗号では、メッセージ（Ｍ）に対する署名はその署名者Ａによってメッセージならびに署名者の公開鍵および非公開鍵と相関して生成される。すなわちSign（M,PA,SA）  →  SIGNATURE＿A（M）
このメッセージの受信者Ｂは、自分の受取るメッセージの署名をメッセージ、その署名およびその署名者の公開鍵の関数として、すなわち、
Verify（M,SIGNATURE＿A（M），BA）で検証することができる。検証の結果は、一般的に署名が有効か否かを特定するイエス／ノーの表示で示される。署名が有効であれば、署名者の特定の公開鍵および非公開鍵（キーペア）の使用によるものとされる。第三者が、メッセージおよび関連した署名の暗号を解析して、またはたとえばこれらの鍵を盗んで不正にこのキーペアの知識を得たならば、第三者は署名されたメッセージのペアすなわちメッセージおよびそれらのメッセージの各々に対する有効な署名を新たに生成することができてしまう。
【００３７】
この発明技術は、真正な署名が署名者の公開鍵および非公開鍵からだけでなく、署名者の秘密鍵からも生成される必要があるために、署名と関連した安全性を実質的に高めている。すなわち、
Authentic＿Sign（M,PA,SA,KA）  →  Authentic＿SIGNATURE＿A（M）
この発明を用いると、現時点での実行可能性という点でおよび秘密鍵の知識なしに真正な署名を含む新たな署名されたメッセージのペアを生成するには公開鍵および非公開鍵を知っているだけでは大いに不十分である。多数のメッセージおよびその真正な署名が与えられても、署名されたメッセージのペアから、すなわち正当なメッセージおよび真正な署名からは、秘密鍵を再生する作業は不可能であると考える。その点に関し、８３ビットのバイナリ値の真正な署名に対しては、秘密鍵の事前の知識なしにそのような真正な署名を生成する確率は約（．５）30のオーダであり、この数字の微小さを考えると、でたらめに推測するのと同じ可能性しかない。
【００３８】
本質的に、この発明の教示に従うと、特定の楕円曲線上の点を与えられると、その曲線上のある点の値が生成元の値として選択される。非公開鍵は無作為に選択される。公開鍵は生成元および非公開鍵の値の予め定められた関数として決定され、特に前者の後者による冪乗として決定される。秘密鍵が用いられて擬似乱数を生成する。真正な署名の第１の部分は次に生成元、擬似乱数およびメッセージ（たとえば無作為に選択された製品の複製の識別子）の予め定められた関数を介して生成される。特定的には、生成元はまず擬似乱数の値で冪乗されてある値を与え、その値は次にメッセージと連結される。その結果生じた連結した数は予め定められたハッシュ関数を介して処理され、真正な署名の第１の部分を与える。真正な署名の残余の部分は第１の部分、擬似乱数の値および非公開鍵の予め定められた関数に応答して生成される。真正な署名全体は両者の署名の部分をともに連結させることにより最終的に生成される。
【００３９】
この発明が用いられて、製品の複製の認証データを実現すると、公開鍵および生成元の値は、クライアントコンピュータ、たとえば図２に示されたクライアントコンピュータ２００に複製をインストールする間にそれを認証するのに用いられる、製品の複製自体の中の適切なファイル内に記憶される。
【００４０】
その製品の複製のインストールの間、ユーザが入力した署名は、クライアントコンピュータで、生成元の値、公開鍵およびユーザが入力した認証データ全体、特に識別子および署名を用いて署名の第１の部分を計算することにより認証される。次にこの第１の部分の値がユーザが入力した署名の同じ部分の値と一致するかを判断する。一致すれば、入力された署名は真正であり、製品の複製のインストールが継続する。一致しなければ、それは真正ではなく、製品の複製のインストールは早期に終了する。
【００４１】
製品の複製の認証データの生成と関連して、３つの別個の段階が用いられてこの発明を実現する。すなわち（ａ）さまざまなパラメータの値を生成するために一度だけ、典型的にはソフトウェア製造者により行なわれる初期化、（ｂ）初期化の間に生成されたパラメータの値を用いて、異なる製品の複製ごとにその複製とともに用いられる真正な署名を含む対応する認証データを生成するために媒体の複製場所で繰返し行なわれる認証データ生成（図４と関連して以下に詳述される特にプロセス４００）、および（ｃ）ユーザ側（クライアントコンピュータ）でインストールプログラムを実行する間に、ユーザが入力し、かつユーザがインストールしようとする特定の製品の複製と関連した認証データ内で署名を認証するために別個にかつその後に行なわれ、その複製のインストールを継続する認証（図５と関連して以下に詳述される特にプロセス５００）である。
【００４２】
この発明を介して生成された真正な署名が公開鍵を用いて従来の方法で検証される限りは、どのように検証が特定的に達成されるかに関する詳細は、簡潔にするために省略する。
【００４３】
１  定義づけおよび初期設定の局面
この発明の技術に用いられるさまざまな変数およびこの技術の初期化に用いられるステップをまず定義する。
【００４４】
まず、好ましくはガロア体上に有限体（Ｋ）が定義される。すなわちＫ＝ＧＦ（ｐ）であり、ここでｐはたとえば３８４ビットまたはそれ以上のように非常に大きく、かつｐ＝１（ｍｏｄ  ４）である。その代わりに、この有限体はＫ＝ＧＦ（２m）と定義されてもよい。
【００４５】
次に、楕円曲線Ｅがこの有限体上に定義される。この発明の教示に従うと、その上に複雑な加算および複雑な乗算が存在する楕円曲線を用いるが、それはこの発明の技術で用いられるパラメータおよびその結果生じる認証データを比較的短くしながらある形態の暗号攻撃に対して必要な安全性を提供するためである。楕円曲線を用いなければ、そのような短いパラメータではその安全性を確保するのは不可能である。一般的に、楕円曲線は、ａ、ｂ、ｃおよびｄを予め定められた係数として、ｙ2＝ａｘ3＋ｂｘ2＋ｃｘ＋ｄ  という曲線を満たす点（ｘ、ｙ）を含む。これら４つの係数の値を変化させることにより、曲線上の点の数はそれに従って変化する。ここでは一般的な形の楕円曲線を用い得るが、好ましくはかつ例示的には、有限体Ｋの上でｙ2＝ｘ3＋ｘとなる曲線を選択し、これにより、曲線Ｅ上の点の数｜Ｅ｜が次のように計算される。すなわち、α＝１（ｍｏｄ  ４）としてｐ＝α2＋β2ならば、｜Ｅ｜＝ｐ＋１−２α＝（α−１）2＋β2である。したがって、曲線上の点の数はαおよびβをそれに従って選択することにより設定できる。
【００４６】
大きな素数ｑが、たとえば少なくとも長さが約６０ビットとなるように選択され、αおよびβはｑが確実に｜Ｅ｜に均等に分割され、かつ１（ｍｏｄ  ４）を満たすようにそれに従って設定される。
【００４７】
一旦ｑの値がそれに従って選択されると、典型的には無作為の点である生成元ｇの値が次数ｑのサブグループに対して曲線Ｅの上に定義される。これは、曲線Ｅ上に無作為の点であるｇを繰返し選択し、かつその特性、すなわち好適な数が判明するまでその数が以下の式を満たすかをテストすることにより、典型的には達成される。
Ｇ＝｛ｇ，２ｇ，３ｇ，  ．．．，（ｑ−１）ｇ｝かつ｜Ｇ｜＝ｑ
一旦適切な生成元の値が選択されると、次に乱数が非公開の指数Ｘとして選択される。この数字Ｘは非公開鍵となる。パラメータｇpowは公開鍵であり、ｇxと等しいとして計算される。
【００４８】
最後に、秘密鍵ＫＡは例示的に２つの予め定められた成分Ａ1およびＡ2を連結したものすなわち以下の式のように定義される。
【００４９】
【数１１】
0004644368.tif 000003
【００５０】
一旦上記のパラメータが定義されると、パラメータｑ、ｇ、ｇpowおよびＸは認証データ生成プロセス４００の各々の実行の間、その後に用いるために記憶され、製造者が生産するすべてのソフトウェア製品の各々のおよびすべての異なる複製に対し、一意の識別子および関連した真正な署名を含む各々の認証データを生成する。さらに、パラメータｇおよびｇpowの値ならびに以下に論じられるハッシュ関数の仕様（specification）はその複製のインストール、特にその複製のインストールの間ユーザが手入力する認証データの認証の間（すなわち以下に詳述される認証プロセス５００の実行の間）その後のアクセスおよび使用のために各々のそのような製品の複製の中にデータとしてすべて記憶される。
【００５１】
２  認証データ生成プロセス４００
図４は認証データ生成プロセス４００のフローチャートの図である。上述のように、このプロセスはコンピュータ１０によって別個に実行され、そのメモリ（特に図示せず）にある適切な記憶されたプログラムの（実行可能な）命令により実現され、各々の連続した製品の複製に対し一意な認証データを生成する。このプロセスは秘密鍵ＫＡ、ｑ、ｇ、ｇpowおよび非公開の指数Ｘの値を用いる。
【００５２】
プロセス４００に入ると、実行のプロセスはまずブロック４１０に進む。このブロックは、実行されると、次の連続した（しかしそれまでに用いられていない）値を、現在の製品の複製に対し（２32−１）＞Ｍ＞０の範囲で識別子（ここではＭ）として無作為に割当てる。代替的に、この識別子は順番に割当てられてもよい。その場合、識別子は第１の製品の複製に対しては１の値を、第２の製品の複製に対しては２の値を割当て、ソフトウェア製造者のすべての製品の複製およびすべての異なる製品にわたり、以下同様に識別子が割当てられる。いずれにせよ、いずれの製品の各々の複製も一意な識別子を有する。製品の認証データを生成するのにこの発明技術が用いられる期間にわたり、２32以上のソフトウェア製造者の製品の複製が製造される見込みであれば、この技術はより長い識別子、したがってより長い鍵およびパラメータの値を用いるように修正されなければならないことが当業者には明らかであろう。
【００５３】
適切な値が現在の製品の複製に対する識別子としてブロック４１０により一旦割当てられると、実行のプロセスはブロック４２０に進む。このブロックは現在の製品の複製に割当てられた秘密鍵および識別子Ｍを用いて、［１、ｑ−１］の範囲で指数ｋの擬似乱数の値を生成する。一般的に、Ｇ＿ｍｓを擬似乱数生成式として、ｋ＝Ｇ＿ＭＳ（Ｍ）である。好ましくは、擬似乱数生成式は、特定的にはＳＨＡ＿１である従来のかつ周知である安全なハッシュ関数を用いて実現される。そのようなハッシュ関数はどのような長さのデジタルの入力数も１６０ビットの値に写像し、それによりＳＨＡ＿１（ｘ）＝ＳＨＡ＿１（ｙ）となるような、同じ長さの数（ｘ、ｙ）の何らかのペアを探し出すことが不可能である、すなわちここでは２80回を超える演算が必要となる。特に、上述のように、秘密鍵ＫＡは例示的には２つの予め定められた成分Ａ1およびＡ2の連結、すなわち以下の式のとおりであり、
【００５４】
【数１２】
0004644368.tif 000004
【００５５】
一旦生成されると固定され、すべての製品の複製の認証データを生成する。ｋを計算するには、ブロック４２０は秘密鍵をその成分Ａ1およびＡ2に解析し、次に複数のハッシュ演算を用いて、次の式１および式２に示されるように指数ｋを計算する。
【００５６】
【数１３】
0004644368.tif 000005
【００５７】
安全性をさらに高めるには、式１および２を介して生成されたｋの値は、別の擬似乱数関数を介してシードとして処理されて新たな擬似乱数の値ｋを与え、現在の製品の複製のための認証データを生成するための残余のステップの間、これらの式によって生成される値の代わりに、代替的にこの新たな値が用いられてもよい。
【００５８】
上述のように、現在の製品の複製に対しｋの値が一旦そのように決定されると、ブロック４３０はｇkの計算を実行する。その後、実行のプロセスはブロック４４０に進み、認証する側には既知のハッシュ関数を用いて、ｇkおよびＭの関数としてかつ以下の式３に従ってパラメータｒの値を決定する。このハッシュ関数は例示的にはＳＨＡ＿１関数である。
【００５９】
【数１４】
0004644368.tif 000006
【００６０】
次に、ブロック４５０はｋ、Ｘ、ｒおよびｑの関数としてかつ以下の式４に従ってパラメータｓの計算を実行する。
【００６１】
【数１５】
0004644368.tif 000007
【００６２】
一旦ｓが完全に計算されると、実行のプロセスはブロック４６０に進み、そこではＭ、ｒおよびｓを連結したものとしての１１５ビットのバイナリ値の認証データを形成し、ただし真正な署名自体はｒおよびｓを連結したものである。バイナリ値の認証データが形成された後、ブロック４７０はこの認証データを２５桁のアルファニューメリックの形式に変換し、次に結果として生じる現在の製品の複製と関連して用いられるアルファニューメリックの認証データの出力値をたとえばプリンタ６０（図１参照）のようなものに与える。認証データを手入力する際のユーザの混乱および起こり得る間違いを低減しかつ使い勝手を高めるために、ブロック４７０（図４には図示せず）は、認証データが印刷されるフォントにもよるが、たとえば、文字ＩおよびＯ（大文字または小文字を問わない）、数字の０、小文字のＬ、および数字の１などユーザには同じに見える、あるアルファニューメリックの文字を好ましくは使用しない。さらに、小文字のＬと数字の１のように同じに見える文字を、共通の文字たとえば数字１に写像してもよい。
【００６３】
この発明を利用しかつ公開鍵−非公開鍵のペアを用いることにより、３２ビットの識別子の値を考慮すると、ゆうに１秒以内の処理時間で、現在利用可能なＰＣで真正な８３ビットの署名が生成されると見込んでいる。
【００６４】
３  認証プロセス５００
図５は、図２および図３で示されたコンピュータ２００のようなクライアントコンピュータ内で実行される認証プロセス５００のフローチャートの図である。上述のように、これはクライアントコンピュータに製品の複製をインストールする間に、所与の製品の複製に対しユーザが手入力した認証データを認証するプロセスである。ｇ、ｇpowの値および認証の間に用いられるハッシュ関数の仕様が所与の製品の複製内に記憶され、それらはソフトウェア製造者からのすべての製品の複製に共通である。単純化のために、パラメータｇおよびｇpowならびにハッシュ関数の仕様を所与のソフトウェア製造者のすべての製品の複製に共通としているが、安全性を高めるためには、これらのパラメータの値およびハッシュ関数の仕様はその製造者の特定の製品のすべての複製または一組のその製品の特定の複製にわたってのみ共通であってもよく、もしくはそのような複製のただ１つのみに特有であってもよい。
【００６５】
プロセス５００に入ると、実行のプロセスはまずブロック５１０に進む。このブロックは、図２および図３に示されたクライアントコンピュータ２００のような、ユーザのクライアントコンピュータにユーザがインストールしようとする特定の製品の複製に対してユーザが手入力したアルファニューメリックの認証データを読取る。この認証データが一旦読取られると、ブロック５２０はまずアルファニューメリックの認証データをバイナリ値のシーケンスに変換し、次にその認証データ内のパラメータＭ、ｒおよびｓの値を抽出するプロセスを実行する。その後、実行のプロセスはブロック５３０に進み、そこではパラメータｇおよびｇpowの記憶された値ならびに認証に用いられる特定のハッシュ関数の仕様を読取る。
【００６６】
これらのパラメータの値およびハッシュ関数の仕様が一旦ブロック５３０により読取られると、実行のプロセスはブロック５４０に進み、実行されると、そこでは認証データから抽出されたばかりのｒおよびｓの値を用いて、ｇsおよびｇpowrの値を計算する。一旦この値が計算されると、ブロック５５０および５６０はまず認証署名の一部、特にパラメータｒ（ここでは再計算された部分は以下の記号で示される。
【００６７】
【数１６】
0004644368.tif 000008
【００６８】
「以下明細書中ではこの記号を＾ｒと記載する」）を計算することにより認証データを集合的に認証し、次にその値を認証データから抽出された同じパラメータの値と比較するステップを実行する。特に、ブロック５５０は以下の式５に従って＾ｒを計算する。
【００６９】
【数１７】
0004644368.tif 000009
【００７０】
この式では、ＨＡＳＨは認証の間に用いられる、製品の複製に特定されたハッシュ関数である。この関数は典型的にはＳＨＡ＿１関数である。
値＾ｒが計算されると、実行のプロセスは判定ブロック５６０に進み、ユーザが入力した認証データから抽出されたｒの値に対してこの値をテストする。これらの２つの値が同一（一致）であれば、認証データ内の署名は認証された。したがって、認証プロセス５００からＹＥＳの経路５６３を介して実行のプロセスは終了し、この製品の複製のインストールを継続する。代替的に、これら２つの値が全く異なっていると、認証データ、特にそれが含む署名は、真正ではない。したがって、ユーザは製品の複製をインストールする認証が与えられない。この例では、判定ブロック５６０はＮＯの経路５６７を介してブロック５７０に実行のプロセスを経路指定する。この後者のブロックは、実行されると、ローカルのモニタ（たとえば図３に示されたディスプレイ３８０）にユーザは製品の複製をインストールする認証を与えられないとする適切なメッセージを表示する。一旦このメッセージがそのように表示されると、実行のプロセスは（図５に示されたように）プロセス５００から終了し、製品の複製のインストールを進めずに早期に終了する。
【００７１】
安全かつ真正な署名を生成するためのこの発明の技術を、ユーザのコンピュータにインストールされるソフトウェア製品の複製とともに用いる認証データの一部としてこれまで説明してきたが、この発明を用いて、ユーザがソフトウェア製造者により運営されるサーバとのネットワーク接続を確立するときは常に、以前にインストールされたソフトウェアの複製を非常に安全にシリアル番号をつける（serialize）ことができることが当業者には理解されるであろう。特に、クライアントコンピュータで実行されるＯ／ＳのユーザがそのＯ／Ｓの製造者のウェブサイトにインターネット接続を確立するならば、ウェブサーバはたとえば真正な署名を含む上述の認証データのようなインストール番号を生成し、その番号をクライアントコンピュータにダウンロードして記憶させることができる（もちろんクライアントコンピュータで実行されるウェブブラウザが「クッキー」を受け入れる、すなわちそのようなダウンロードを受け入れるように設定されていると仮定して）。このインストール番号を用いて製造者はその特定のＯ／Ｓのインストールを一意にかつ安全に識別できる。そのユーザがその後製造者のウェブサイトとインターネット接続を確立するときは常に、製造者はクライアントコンピュータに記憶されたインストール番号にアクセスしかつそれを認証することによりＯ／Ｓの特定のインストールを容易に識別することができる。記憶されたインストール番号をきちんと認証できることにより、製造者は許諾されたＯ／Ｓのインストールと許諾なしのＯ／Ｓのインストールを区別することができる。したがって製造者は前者のインストールのみにサポート、アップグレード、プロモーションおよび／または他のサービスを提供しながら、後者のインストールに対してはそれらを拒否することができる。同様に、製造者は以前にインストールされかつ製造者がその後に識別を行ないたい、アプリケーションプログラムのような他のタイプのソフトウェアプログラムの複製に対して一意なインストール番号を生成しかつダウンロードすることができる。
【００７２】
さらに、認証データはそれに対して真正な署名が生成されるメッセージとして製品の複製の識別子を用いたが、このメッセージはそのように限定されるものではない。このメッセージは電子的に暗号化されかつ一方から他方へ伝達されるいずれの形態のデジタルの情報も構成することができる。したがって、この発明は送信者と受信者の間を通過する暗号化されたメッセージの流れの中の各々のメッセージを認証する、高度な安全性を有するメカニズムを提供することができる。
【００７３】
さらに、認証データの生成および認証のプロセス（特に図４および図５それぞれの中のブロック４４０および５５０）の中でパラメータｒおよび＾ｒを生成するための安全なハッシュ関数を用いてこの発明の技術を説明したが、同じ関数が両者のプロセスに用いられ、またその関数の仕様が関連した製品の複製に記憶され、かつその特定の複製のインストールの間認証のプロセスによって読取られるならば、他の安全な関数が用いられてもよい。
【００７４】
さらに、この発明は３２ビットのメッセージ（ここでは、例示的に製品の複製の識別子）および８３ビットの真正な署名とともに用いられるように例示的に説明されたが、この発明はその意図された適用例を考慮すると、より長いメッセージおよび署名、もしくはより低いセキュリティが許容されるアプリケーションでは、より短いメッセージおよび署名を受け入れるよう容易に修正が可能である。
【００７５】
さまざまな修正とともに、この発明の教示を組込む実施例が詳細に示されかつ説明されたが、当業者はこの教示を利用する多数の他の実施例を容易に考案することができる。
【図面の簡単な説明】
【図１】  この発明の教示を組込んだＣＤ−ＲＯＭ生産システムの、単純化されてはいるが高レベルのブロック図である。
【図２】  図１に示されたシステム５を介して生産されたようなＣＤ−ＲＯＭからプログラムをインストールする間に、この発明を例示的に利用する典型的なクライアントコンピュータ２００の高レベルなブロック図である。
【図３】  図２に示されたクライアントコンピュータ２００のブロック図である。
【図４】  図１に示されたコンピュータ１０内で実行される認証データ生成プロセス４００のフローチャートの図である。
【図５】  図２および図３に示されたクライアントコンピュータ２００内で実行される認証プロセス５００のフローチャートの図である。
【図１】
0004644368.tif 000019
【図２】
0004644368.tif 000020
【図３】
0004644368.tif 000021
【図４】
0004644368.tif 000022
【図５】
0004644368.tif 000023