(57)【特許請求の範囲】
【請求項１】
署名を検証するためのコンピュータ実行可能命令を含む１つまたは複数のコンピュータ読み取り可能な記録媒体であって、コンピュータに、
メッセージデータおよび前記署名を含む署名入りメッセージを外部コンピューティング装置から受信する手順であって、前記署名入りメッセージは、法の値を含む秘密鍵を使用して署名されており、前記秘密鍵は、公開指数および前記法の値を含む公開鍵と対を成す、手順と、
前記公開指数によって増加し、次いで前記法の値で割った前記署名の商に対応する前記外部コンピューティング装置により事前に計算された値を当該外部コンピューティング装置から受信する手順と、
前記署名を検証するために、前記事前に計算された値を使用する手順と
を実行させるためのプログラムを記録したことを特徴とするコンピュータ読み取り可能な記録媒体。
【請求項２】
前記署名入りメッセージは、追加の署名値をさらに含み、前記署名を検証するために、前記事前に計算された値を使用する手順は、前記署名を検証するために前記事前に計算された値および前記追加の署名値を使用する手順を含むことを特徴とする請求項１に記載のコンピュータ読み取り可能な記録媒体。
【請求項３】
前記公開指数は、値３を有することを特徴とする請求項１に記載のコンピュータ読み取り可能な記録媒体。
【請求項４】
前記外部コンピューティング装置は、前記秘密鍵を使用してメッセージに署名したコンピューティング装置であることを特徴とする請求項１に記載のコンピュータ読み取り可能な記録媒体。
【請求項５】
前記外部コンピューティング装置は、サーバーコンピューティング装置であることを特徴とする請求項１に記載のコンピュータ読み取り可能な記録媒体。
【請求項６】
前記事前に計算された値および前記署名は、前記外部コンピューティング装置によって署名記録を使用して符号化されたものであることを特徴とする請求項１に記載のコンピュータ読み取り可能な記録媒体。
【請求項７】
前記事前に計算された値は、前記署名の前記検証以降、無期限に維持されることを特徴とする請求項１に記載のコンピュータ読み取り可能な記録媒体。
【請求項８】
署名の検証を助けるためのプログラムを記録したコンピュータ読み取り可能な記録媒体であって、前記プログラムは、コンピュータに、
メッセージデータおよび前記署名を含む署名入りメッセージを送信する手順であって、前記署名入りメッセージは、法の値を含む秘密鍵を使用して署名されており、前記秘密鍵は、公開指数および前記法の値を含む公開鍵と対を成す、手順と、
前記署名入りメッセージまたは前記公開鍵から前記公開指数および前記法の値を取得して前記公開指数によって増加し、次いで前記法の値で割った前記署名の商に対応する事前に計算された値を生成する手順と、
前記事前に計算された値を送信する手順と
を実行させることを特徴とするコンピュータ読み取り可能な記録媒体。
【請求項９】
前記プログラムは、前記コンピュータに、前記署名入りメッセージを生成する手順を実行させることを特徴とする請求項８に記載のコンピュータ読み取り可能な記録媒体。
【請求項１０】
前記署名入りメッセージは、前記署名を検証するのに必要な追加の署名値をさらに含むことを特徴とする請求項８に記載のコンピュータ読み取り可能な記録媒体。
【請求項１１】
前記公開指数は、値３を有することを特徴とする請求項８に記載のコンピュータ読み取り可能な記録媒体。
【請求項１２】
前記プログラムは、前記コンピュータに、署名記録を使用して、前記事前に計算された値および前記署名を符号化する手順を実行させることを特徴とする請求項８に記載のコンピュータ読み取り可能な記録媒体。
【請求項１３】
前記事前に計算された値を符号化する手順は、前記署名記録の余分のフィールドを使用して、前記事前に計算された値を符号化する手順を含むことを特徴とする請求項１２に記載のコンピュータ読み取り可能な記録媒体。
【請求項１４】
署名を検証する方法であって、コンピューティング装置が、
メッセージデータおよび前記署名を含む署名入りメッセージを外部コンピューティング装置から受信することであって、前記署名入りメッセージは、法の値を含む秘密鍵を使用して署名されており、前記秘密鍵は、公開指数および前記法の値を含む公開鍵と対を成す、署名入りメッセージを受信すること、
前記公開指数によって増加し、次いで前記法の値で割った前記署名の商に対応する前記外部コンピューティング装置により事前に計算された値を当該外部コンピューティング装置から受信すること、および、
前記署名を検証するために、前記事前に計算された値を使用すること
を備えたことを特徴とする方法。
【請求項１５】
前記コンピューティング装置が追加の署名値を前記外部コンピューティング装置から受信することをさらに備え、前記署名を検証するために前記事前に計算された値を使用することは、前記署名を検証するために、前記事前に計算された値および前記追加の署名値を使用することをさらに含むことを特徴とする請求項１４に記載の方法。
【請求項１６】
前記公開指数は、値３を有することを特徴とする請求項１４に記載の方法。
【請求項１７】
前記外部コンピューティング装置は、前記秘密鍵を使用してメッセージに署名したコンピューティング装置であることを特徴とする請求項１４に記載の方法。
【請求項１８】
前記外部コンピューティング装置は、サーバーコンピューティング装置であることを特徴とする請求項１４に記載の方法。
【請求項１９】
前記事前に計算された値および前記署名は、前記外部コンピューティング装置によって署名記録を使用して符号化されたものであることを特徴とする請求項１４に記載の方法。
【請求項２０】
前記事前に計算された値は、前記署名の前記検証以降、無期限に維持されることを特徴とする請求項１４に記載の方法。
【発明の詳細な説明】
【背景技術】
【０００１】
デジタル署名は、署名入りデータが特定のエンティティによって送信されたことをデジタル的に証明するために使用される。コンピュータユーザなどの各エンティティは、鍵ペアとして知られる１組のデータを導出する。ペアのうちの一方の鍵は、公開鍵として知られており、自由に配布することができる。ペアのうちの第２の鍵は、秘密鍵として知られており、特定のエンティティを一意に識別するデジタル署名の能力は、エンティティがその秘密鍵をどのぐらい注意深く保護するかに依存する。任意のデータは、秘密鍵を使用して「署名」することができる。より具体的には、署名すべきデータおよび秘密鍵は、既知の数学関数への入力として提供される。こうした関数の出力がデータのデジタル署名である。
【０００２】
次いで、公開鍵を使用して、データが署名されてから変更されていないことを検証することができる。より詳細には、署名入りデータ、デジタル署名、および公開鍵は、既知の数学関数への入力として提供される。データが署名された後、署名入りデータが変更された場合、数学関数は、一般に、データの変更がなかったら等しかったであろう結果として得られた値が等しくないことによって、そのように示す。秘密鍵のみが、対応する公開鍵により数学的に検証される署名を生成することができたならば、署名のこうした数学的検証は、データが秘密鍵を所有するある人によって署名されてから、変更されなかったことを示す。１つのエンティティのみが秘密鍵を所有している場合、署名の検証は、データが、実際には、そのエンティティによって送信されたこと、および送信中に変更されなかったことを検証するよう働く。
【０００３】
一般に使用される１つのデジタル署名アルゴリズムは、それを発見したと言われている３人の個人の名字の第１文字を借りた、ＲＳＡアルゴリズムとして知られている。ＲＳＡ公開鍵は、一般に文字「ｅ」によって指定される「公開指数」、および一般に文字「ｎ」によって指定される法を含む。従来「メッセージ」と呼ばれ、変数「ｍ」によって表される何らかのデータのＲＳＡ署名「ｓ」は、ｓe  ｍｏｄ  ｎがＦ（ｍ，ｎ）に等しいことを確認することによって検証することができ、この場合、「Ｆ」は、同意済みの埋め込み関数（ａｇｒｅｅｄ  ｕｐｏｎ  ｐａｄｄｉｎｇ  ｆｕｎｃｔｉｏｎ）である。
【０００４】
デジタル通信の使用が増えるにつれて、署名入りメッセージの数も同様に増える。したがって、署名入りメッセージの検証に費やされる時間は、重要となり得る。というのは、特に、メッセージへの署名は一度だけでよいが、その署名は、各受信者によって一度、複数回検証され得るからである。その結果、署名の検証は、メッセージ署名よりはるかに何度も実行される。
【０００５】
ＲＳＡアルゴリズムでは、署名検証は、「Ｆ」が同意済みの埋め込み関数である場合、Ｆ（ｍ，ｎ）、およびｓe  ｍｏｄ  ｎの両方の計算を必要とする。２つの式のうち、後者は、従来、より多くの計算を伴う。実際に、ｓe  ｍｏｄ  ｎは、一般に、個々のモジュラ乗算（ｍｏｄｕｌａｒ  ｍｕｌｔｉｐｌｉｃａｔｉｏｎ）およびモジュラ二乗（ｍｏｄｕｌａｒ  ｓｑｕａｒｉｎｇ）を使用して、漸次に評価される。ｓe  ｍｏｄ  ｎを直接計算し、こうした漸次的手法を避けるには、当業者には知られているように、非常に大きくなり得るｓe項の計算がもたらされ、結果的に性能の損失が伴うことになる。
【発明の概要】
【０００６】
ＲＳＡ署名を検証するために、メッセージデータ「ｍ」および署名「ｓ」の受信者は、ｓe  ｍｏｄ  ｎがＦ（ｍ，ｎ）に等しいことを検証する必要がある。この場合、「Ｆ」は同意済みの埋め込み関数であり、「ｅ」および「ｎ」はメッセージの署名者に対応するＲＳＡ公開鍵の要素である。しかし、等しいことが完全に真であることを検証するのではなく、１に非常に近い確率で、ｓe  ｍｏｄ  ｎがＦ（ｍ，ｎ）に等しいことを検証することで数学的に十分である。そうするための１つの機構は、「ｐ」の適切に選択された値について、（ｓe  ｍｏｄ  ｎ）ｍｏｄ  ｐがＦ（ｍ，ｎ）ｍｏｄ  ｐに等しいことを検証することである。
【０００７】
法演算の特性によって、値「Ｋ」がｓe  ｄｉｖ  ｎと定義される場合、ｓe  ｍｏｄ  ｎをｓe−Ｋｎと表すことができる。この式を上記のｐを法とした方程式に代入することによって、（ｓe−Ｋｎ）ｍｏｄ  ｐ＝Ｆ（ｍ，ｎ）ｍｏｄ  ｐが得られる。等号の左側の式は、（ｓ  ｍｏｄ  ｐ）e−（Ｋ  ｍｏｄ  ｐ）（ｎ  ｍｏｄ  ｐ）ｍｏｄ  ｐとして計算することができる。この式の項を検討すると、以下の値、（１）ｓ  ｍｏｄ  ｐ、（２）Ｋ  ｍｏｄ  ｐ、および（３）ｎ  ｍｏｄ  ｐを最初に計算する必要がある。これらの項のそれぞれは、ｐを法とし、したがって、比較的小さい値をもたらす。というのは、ｐは、管理可能に小さくなるように選択することができ、ｐを法とする任意の項は、数学的に、ｐより小さくなければならないからである。残りの計算はすべて、べき乗を計算するために、個々のモジュラ二乗およびモジュラ乗算を使用して、ｐを法として行うことができる。
【０００８】
しかし、まだ値「Ｋ」が決定されていない。指数「ｅ」が、例えばｅ＝２やｅ＝３など、十分に小さくなるように選択された場合、Ｋはｓeに正比例するため、Ｋの値は、同様に比較的小さい。Ｋの値が比較的小さいことによって、Ｋ  ｍｏｄ  ｐ項のより効率的な計算が可能になるとともに、Ｋを効率的に送信することもできる。指数項、すなわちｓeがＫに関与していることを考えると、Ｋの値を導出することは、計算上高価となり得る。しかし、Ｋは、効率的に送信することができるため、署名ｓを検証するよう務めるもの以外のコンピューティング装置によって決定し、次いで単に検証を行うコンピューティング装置に送信することができる。セキュリティの考察に対してさらに重要なこととして、値Ｋは、署名ｓ、公開指数ｅ、および法ｎを含めて、公に入手可能な情報に完全に基づく。したがって、Ｋを送信することによって、ＲＳＡ署名方式のセキュリティの低下がもたらされることはない。
【０００９】
一実施形態において、値Ｋは、署名入りメッセージを受信するコンピューティング装置以外のコンピューティング装置によって計算することができ、次いで、署名入りメッセージを受信するコンピューティング装置のうちの１つまたは複数に送信することができる。例えば、値Ｋは、メッセージを送信し、それに署名するコンピューティング装置によって計算することができる。Ｋを計算する計算コストは、メッセージ自体に署名する計算コストに比べて、ごく少ない。したがって、署名するコンピューティング装置によって行われる作業の実質的な増加はない。
【００１０】
代替実施形態において、値Ｋは、例えば、サーバのクライアントであるコンピューティング装置に署名入りメッセージのコピーを配布する責任のある電子メールサーバや、１つまたは複数のクライアント中で署名入りデータを共有するファイルサーバなど、中央サーバによって計算することができる。中央の場所でＫを計算することによって、署名入りメッセージの受信者によって行われる各個々の署名検証を、より効率的にすることができる。
【００１１】
別の代替実施形態において、署名入りメッセージを受信するコンピューティング装置は、Ｋを一度計算し、それを署名入りメッセージと共に格納することができる。次いで、Ｋのすでに計算された値を参照することによって、任意のその後の署名検証をより効率的に行うことができる。
【００１２】
さらに別の代替実施形態において、ＲＳＡ署名方式のＲａｂｉｎ変形体を使用して、公開指数ｅをｅ＝２になるように選択することができる。こうした小さいｅを選択することによって、効率的な方法で送信することができ、その後検証側コンピューティング装置によって効率的な方法で使用することができる比較的小さい値のＫが提供される。さらに別の代替実施形態において、公開指数ｅをｅ＝３になるように選択することができる。ｅ＝３の場合でさえ、Ｋの値は、比較的小さいままであり得るが、Ｒａｂｉｎ変形体の欠点は回避される。いずれの場合（ｅ＝２およびｅ＝３）でも、埋め込み関数Ｆは、小さい公開指数を選択するために、任意のセキュリティの低下を最低限に抑えるように選択される。
【００１３】
さらに別の代替実施形態において、下位互換性を提供するために、既存のフォーマットを使用して、値Ｋを送信することができる。例えば、多くの署名は、追加のフィールドを追加することに備えるフォーマットで符号化される。値Ｋは、こうした追加のフィールドを介して提供することができる。こうしたフィールドの探し方を知っている受信側コンピューティング装置は、Ｋを事前に計算させることによって得られる計算の効率性を利用することができ、更新されていない受信側コンピューティング装置は、依然として、署名を検証することができ、Ｋの値を含む追加のフィールドを単に無視することができる。従来、Ｋは、下位互換性のある方法で提供することができる。
【００１４】
この概要は、詳細な説明において下記でさらに説明されるいくつかの概念を簡単な形で紹介するために提供される。この概要は、特許請求された主題の鍵となる特徴または重要な特徴を識別するためのものではなく、特許請求された主題の範囲を限定するために使用されるためのものでもない。
【００１５】
追加の特徴および利点は、添付の図面を参照して進める以下の詳細な説明から明らかになる。
【図面の簡単な説明】
【００１６】
以下の詳細な説明は、添付の図面と併せ読めば、最もよく理解され得る。
【図１】従来の署名方式を示すブロック図である。
【図２】コンピューティング装置例を示すブロック図である。
【図３】署名の検証を行うコンピューティング装置によって受信された要素を示すブロック図である。
【図４】一実施形態によるコンピューティング装置に要素を送信することを示すブロック図である。
【図５】別の実施形態によるコンピューティング装置に要素を送信することを示すブロック図である。
【発明を実施するための形態】
【００１７】
以下の説明は、メッセージ署名をより効率的に検証するための機構に関する。ＲＳＡメッセージ署名は、ｓe  ｍｏｄ  ｎ＝Ｆ（ｍ，ｎ）であることを検証することによって検証することができ、この場合、「ｓ」は署名、「ｅ」はＲＳＡ公開鍵からの指数、「ｎ」はＲＳＡ公開鍵からの法、「ｍ」は署名されたデータ、および関数「Ｆ」は同意済みの埋め込み関数である。Ｋ＝ｓe  ｄｉｖ  ｎとして定義される値Ｋが、事前に計算され、署名を検証するコンピューティング装置への入力として提供される場合、等式ｓe  ｍｏｄ  ｎ＝Ｆ（ｍ，ｎ）を検証することができる効率は、１桁以上増加する。それ自体非効率であり得る大きい値Ｋの送信、およびそれについての数学的演算を避けるために、指数ｅは、例えばｅ＝２またはｅ＝３など、比較的小さくなるように選択することができる。
【００１８】
一実施形態において、値Ｋは、メッセージに署名するコンピューティング装置によって計算され、メッセージおよび署名と共に送信され得る。値Ｋを計算する計算複雑性は、メッセージの署名を計算する計算複雑性よりはるかに低く、したがって、メッセージに署名するコンピューティング装置に計算の負担をそれほど加えないことになる。
【００１９】
別の実施形態において、値Ｋは、電子メールサーバやファイルサーバなど、中央コンピューティング装置によって計算することができる。一実施形態において、電子メールサーバまたはファイルサーバは、署名入りメッセージを受信すると、サーバの任意のクライアントが署名入りメッセージを受信する前に、Ｋを計算することができる。集中化された方法でＫの計算を一度実行することによって、署名の非常に多くの個々の検証を、より効率的にすることができ、実質的に、サーバコンピューティング装置の追加の計算作業をオフセットする。
【００２０】
さらに別の実施形態において、メッセージおよび署名を受信するコンピュータは、一度Ｋを計算し、その後の署名検証で使用するために、それを格納することができる。アクセスしやすくするために、Ｋを、メッセージおよび署名と同じ場所に配置するように、受信コンピュータに格納することができる。
【００２１】
さらに別の実施形態において、署名を検証するコンピューティング装置によって効率的に送信され、効率的に使用され得るＫの比較的小さい値を提供するように、公開指数ｅの値を２になるよう選択することができる。さらに別の実施形態において、Ｋの値を比較的小さく保ちながら、追加のセキュリティを提供するように、公開指数ｅの値を３になるように選択することができる。ｅ＝２またはｅ＝３を使用することは、結果におけるすべてのビットを適切にランダム化する適切に選択された埋め込み関数Ｆを必要とする。
【００２２】
本明細書に記載された技術は、それだけには限定されないが、検証をより効率的にするために、事前に計算された値Ｋを使用することによって、ＲＳＡ署名の検証に焦点を当てる。値Ｋは、示されるように、任意の数のコンピューティング装置によって計算することができる。さらに、公開指数ｅの適切な選択が与えられ、署名の検証が無限の精度を必要とする必要がないならば、記載した検証は、従来のＲＳＡ署名検証より１桁以上速くなり得る。
【００２３】
図１を参照すると、システム例９９が示されており、部分的に、送信側コンピューティング装置２０、および受信側コンピューティング装置１０を含み、これら２つのコンピューティング装置は、ネットワーク９０を介して接続されている。送信側コンピュータ２０は、２つの鍵、公開鍵２１および秘密鍵２２を生成することができる。鍵の生成は、広く普及しているＲＳＡアルゴリズム、またはＲＳＡアルゴリズムのＲａｂｉｎ変形体によってなど、当業者に知られている方法で進む。公開鍵２１は、自由に配布するためのものであり、秘密鍵２２によって署名されたメッセージの署名を検証するために、受信側コンピューティング装置１０などの受信者によって使用されるため、そう呼ばれる。
【００２４】
メッセージ３０は、送信側コンピューティング装置２０によって生成することができ、送信側コンピューティング装置が送信することを望むデータの任意の集まりを含むことができる。メッセージ３０は、例えば、電子メールメッセージとすることができるが、それだけに限定されない。メッセージ３０は、ファイル、構成要素、モジュール、または送信側コンピューティング装置２０によって送信されているデータの他の任意の集まりとすることもできる。
【００２５】
メッセージ３０を送信する前に、コンピューティング装置は、ＲＳＡアルゴリズムによって記載されている方法など、当業者に知られている方法で、秘密鍵２２を使用して、署名入りメッセージ３１を生成することができる。秘密鍵２２は、メッセージデータ、署名自体、および公開鍵２１内に含まれる情報を使用して、署名入りメッセージの署名を検証することができるような方法で、メッセージ３０に署名するために使用される。より詳細には、秘密鍵２２は、変数「ｍ」によって表されるメッセージ３０のデータに基づいて、変数「ｓ」によって表される署名を生成するために使用され、したがって、ｓは、方程式ｓe  ｍｏｄ  ｎ＝Ｆ（ｍ，ｎ）を満たし、この場合、ｎおよびｅは、公開鍵２１の一部である。
【００２６】
メッセージデータおよび署名の両方を含む署名入りメッセージ３１は、コンピューティング装置２０によっていったん生成されると、例えばネットワーク９０を介してコンピューティング装置１０に送信することができる。コンピューティング装置１０は、署名が方程式ｓe  ｍｏｄ  ｎ＝Ｆ（ｍ，ｎ）を満たすことを検証することによって、署名入りメッセージ３１の署名を検証することができる。署名が方程式を満たす場合、受信されたメッセージデータが送信側コンピューティング装置２０によって送信されたのと同じメッセージデータである可能性が非常に高く、さらに、送信側コンピューティング装置２０、またはより適切には、送信側コンピューティング装置のユーザがそのメッセージの送信者であった可能性が非常に高い。というのは、そのユーザは、秘密鍵２２にアクセスすることができる唯一の人物であるはずであり、秘密鍵は、方程式ｓe  ｍｏｄ  ｎ＝Ｆ（ｍ，ｎ）を満たす署名を生成するために必要だからである。したがって、受信側コンピューティング装置１０は、署名入りメッセージ３１の署名を検証することによって、メッセージの内容がその送信者だと言われている人物によって本当に送信されたというデジタル保証を受信する。
【００２７】
図１に示されるように、ｓe  ｍｏｄ  ｎ＝Ｆ（ｍ，ｎ）を検証するために、受信側コンピューティング装置１０は、署名ｓおよびメッセージデータｍの値を署名入りメッセージ３１から取得し、ｎおよびｅの値を公開鍵２１から取得する。したがって、図示されるように、受信側コンピューティング装置１０は、公開鍵２１を使用して、署名入りメッセージ３１を検証する。別個のメッセージとして示されているが、検証済みメッセージ３２は、単に、署名入りメッセージの署名が検証されたという知識と組み合わせた、署名入りメッセージ３１にすぎない。
【００２８】
必須ではないが、下記は、１つまたは複数のコンピューティング装置によって実行されるプログラムモジュールなどのコンピュータ実行可能命令の一般的な文脈で説明する。より詳細には、この説明は、特に明記していない限り、１つまたは複数のコンピューティング装置または周辺装置によって実行される動作および操作の象徴を参照する。したがって、時としてコンピュータ実行可能と言うこともあるこうした動作および操作は、構造化された形式のデータを表す電気信号または光の量などの光信号の処理単位による操作を含むことは理解されよう。この操作は、データを変換し、またはデータをメモリ内のいくつかの場所において維持し、これによって、当業者によく理解されている方法で、コンピューティング装置または周辺装置の動作が再構成され、またはそうでない場合、変更される。データが維持されるデータ構造は、データのフォーマットによって定義された特定の特性を有する物理位置である。
【００２９】
一般にプログラムモジュールは、特定のタスクを実行する、または特定の抽象データ型を実装するルーチン、プログラム、オブジェクト、構成要素、データ構造などを含む。さらに、コンピューティング装置を従来のパーソナルコンピュータに制限する必要はなく、ハンドヘルド装置、マルチプロセッサシステム、マイクロプロセッサベースまたはプログラム可能家庭用電化製品、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータなどを含む他のコンピューティング構成を含むことを当業者であれば理解されよう。同様に、機構は、タスクが通信ネットワークを介してリンクされるリモート処理装置によって実行される分散コンピューティング環境でも実施することもできるので、コンピューティング装置をスタンドアロンコンピューティング装置に限定する必要はない。分散コンピューティング環境では、プログラムモジュールを、ローカルおよびリモートのメモリ記憶装置に置くことができる。
【００３０】
図２を参照すると、コンピューティング装置例１００が示されている。コンピューティング装置例１００は、それだけには限定されないが、１つまたは複数の中央処理装置（ＣＰＵ）１２０、システムメモリ１３０、およびシステムメモリを含む様々なシステム構成要素を処理装置１２０に結合するシステムバス１２１を含み得る。システムバス１２１は、様々なバスアーキテクチャのうちの任意のものを使用するメモリバスまたはメモリコントローラ、周辺バス、およびローカルバスを含むいくつかのタイプのバス構造のうちどんなものでもよい。
【００３１】
また、コンピューティング装置１００は、一般に、コンピューティング装置１００からアクセスできる任意の使用可能な媒体を含むことができ、揮発性および不揮発性媒体、取外式および固定式の媒体を含むコンピュータ可読媒体を含む。コンピュータ可読媒体は、それだけには限定されないが一例として、コンピュータ記憶媒体および通信媒体を含み得る。コンピュータ記憶媒体には、コンピュータ可読命令、データ構造、プログラムモジュール、他のデータなど、情報を記憶するための任意の方法または技術で実施される媒体がある。コンピュータ記憶媒体には、それだけには限定されないが、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリまたは他のメモリ技術、ＣＤ−ＲＯＭ、デジタル多用途ディスク（ＤＶＤ）または他の光ディスク記憶装置、磁気カセット、磁気テープ、磁気ディスク記憶装置または他の磁気記憶装置、または所望の情報の格納に使用でき、コンピューティング装置１００からアクセスできる他の任意の媒体などがある。通信媒体は一般に、コンピュータ可読命令、データ構造、プログラムモジュール、または他のデータを搬送波または他の移送機構などの変調されたデータ信号に組み込み、任意の情報配送媒体を含む。通信媒体には、それだけには限定されないが一例として、有線ネットワーク、直接配線された接続などの有線媒体、および音響、ＲＦ、赤外線、その他の無線媒体などの無線媒体がある。また、上記のどんな組み合わせでもコンピュータ可読媒体の範囲内に含まれるものとする。
【００３２】
システムメモリ１３０は、読み取り専用メモリ（ＲＯＭ）１３１やランダムアクセスメモリ（ＲＡＭ）１３２など、揮発性および／または不揮発性メモリの形のコンピュータ記憶媒体を含む。基本入出力システム１３３（ＢＩＯＳ）は、例えば起動中など、コンピューティング装置１００内の要素間での情報の転送を助ける基本ルーチンを含み、一般にＲＯＭ１３１に格納されている。ＲＡＭ１３２は一般に、処理ユニット１２０からすぐにアクセス可能な、および／または処理ユニット１２０が現在処理しているデータおよび／またはプログラムモジュールを含む。図２は、それだけには限定されないが一例として、オペレーティングシステム１３４、他のプログラムモジュール１３５、およびプログラムデータ１３６を示している。
【００３３】
コンピューティング装置１００は、他の取外式／固定式、揮発性／不揮発性コンピュータ記憶媒体を含むこともできる。一例にすぎないが、図２は、固定式不揮発性磁気媒体から読み取り、またはそこに書き込むハードディスクドライブ１４１を示している。コンピューティング装置例で使用できる他の取外式／固定式、揮発性／不揮発性コンピュータ記憶媒体には、それだけには限定されないが、磁気テープカセット、フラッシュメモリカード、デジタル多用途ディスク、デジタルビデオテープ、半導体ＲＡＭ、半導体ＲＯＭなどがある。ハードディスクドライブ１４１は、一般に、インターフェイス１４０など固定式メモリインターフェイスを介してシステムバス１２１に接続される。
【００３４】
上述し、図２に示したドライブおよびその関連のコンピュータ記憶媒体は、コンピュータ可読命令、データ構造、プログラムモジュール、およびコンピューティング装置１００の他のデータの記憶域を提供する。図２では例えば、ハードディスクドライブ１４１は、オペレーティングシステム１４４、他のプログラムモジュール１４５、およびプログラムデータ１４６を記憶するものとして示されている。これらの構成要素は、オペレーティングシステム１３４、他のプログラムモジュール１３５、およびプログラムデータ１３６と同じであっても、異なっていてもよいことに留意されたい。オペレーティングシステム１４４、他のプログラムモジュール１４５、およびプログラムデータ１４６は少なくとも異なるコピーであることを示すために、ここではそれらに異なる番号を付している。
【００３５】
以下の説明との関連で、コンピューティング装置１００は、１つまたは複数のリモートコンピュータへの論理接続を使用して、ネットワーク環境で動作することができる。例証を簡単にするために、コンピューティング装置１００は、図２において、任意の特定のネットワークまたはネットワーキングプロトコルに限定されないネットワーク９０に接続されているように示されている。図２に示した論理接続は、ローカルエリアネットワーク（ＬＡＮ）、広域ネットワーク（ＷＡＮ）、または他のネットワークとすることができる一般のネットワーク接続１７１である。コンピューティング装置１００は、ネットワークインターフェイスまたはアダプタ１７０を介して一般のネットワーク接続１７１に接続されており、ネットワークインターフェイスまたはアダプタ１７０は、次いでシステムバス１２１に接続されている。ネットワーク環境において、コンピューティング装置１００、またはその一部または周辺装置に対して記載されるプログラムモジュールは、一般のネットワーク接続１７１を介して、コンピューティング装置１００に通信可能に結合される１つまたは複数の他のコンピューティング装置のメモリに格納され得る。図示したネットワーク接続は例であり、通信リンクを確立する他の手段を使用してもよいことは理解されよう。
【００３６】
再度署名の検証に戻ると、ｓe  ｍｏｄ  ｎ、Ｆ（ｍ，ｎ）の計算、およびその方程式の決定は、システムメモリ１３０との組み合わせで、ＣＰＵ１２０による特定の数学関数の性能を必要とする。当業者には知られているように、項ｓeの値は、非常に大きくなり得る。したがって、ｓe  ｍｏｄ  ｎの計算は、最初にｓe項を計算し、次いでその法ｎを計算するのに対して、個々のモジュラ二乗およびモジュラ乗算を使用して増分的に行われる。より詳細には、ｓe  ｍｏｄ  ｎの増分的計算は、最初に（ｓ2  ｍｏｄ  ｎ）を計算し、次いでその結果の法ｎをとり、次いで、場合によっては結果にｓを掛け、次いでその結果の法ｎをとり、次いで結果を二乗し、次いでその結果の法ｎをとるなどして進む。一般に使用されるｅ＝６５５３７など、大きい値のｅでは、ｓe  ｍｏｄ  ｎの計算は、かなり時間がかかる可能性があり、Ｆ（ｍ，ｎ）項の計算よりはるかに計算上高価となり得る。言い換えれば、ｓe  ｍｏｄ  ｎ＝Ｆ（ｍ，ｎ）を検証するのに必要な時間は、ｓe  ｍｏｄ  ｎ項の計算にほとんど費やされる。
【００３７】
上述したように、変数「ｍ」は、メッセージ３０のデータを表し、変数「ｓ」は、署名入りメッセージ３１を作成するためにメッセージ３０用に生成された署名を表す。変数「ｎ」および「ｅ」によって表される項は、公開鍵２１から取得される。より詳細には、公開鍵２１および秘密鍵２２の生成は、２つの乱数の選択を必然的に伴い、これらを互いに掛けて、値「ｎ」になり、公開鍵２１および秘密鍵２２の「法」として知られている大きい乱数を生成する。変数「ｅ」は、「公開指数」であり、当業者によって知られている方法で、秘密指数との組み合わせで選択される。公開指数ｅは、法ｎとの組み合わせで、公開鍵２１を含み、秘密鍵２２は、秘密指数との組み合わせで、法ｎを含む。
【００３８】
ｓe  ｍｏｄ  ｎがＦ（ｍ，ｎ）に等しいことを絶対的に検証するのではなく、ｓe  ｍｏｄ  ｎがＦ（ｍ，ｎ）に等しい確率が非常に高いことを数学的に示すことができる場合、署名を検証することができる。そうするための１つの機構は、方程式ｓe  ｍｏｄ  ｎ＝Ｆ（ｍ，ｎ）を、比較的小さい値ｐを法として検証することである。法演算の特性により、（ｓe  ｍｏｄ  ｎ）ｍｏｄ  ｐがＦ（ｍ，ｎ）ｍｏｄ  ｐに等しい場合、ｓe  ｍｏｄ  ｎ＝Ｆ（ｍ，ｎ）であるか、ｓe  ｍｏｄ  ｎがちょうどＦ（ｍ，ｎ）のｐの倍数内であるかのいずれかである。簡単な例として、ｐ＝３、ｓe  ｍｏｄ  ｎ＝１６、およびＦ（ｍ，ｎ）＝１６であると仮定する。わかるように、ｓe  ｍｏｄ  ｎ＝Ｆ（ｍ，ｎ）であるが、（ｓe  ｍｏｄ  ｎ）ｍｏｄ  ｐおよびＦ（ｍ，ｎ）ｍｏｄ  ｐを計算する効果について考察する。１６を３で割ると、除数５、余り１が得られるため、いずれの場合も、結果は、１となる。しかし、ｓe  ｍｏｄ  ｎが１９または２２に等しい、あるいは１６に３の倍数を足す、または１６から３の倍数を引くことによって得られる他の値に等しい場合、（ｓe  ｍｏｄ  ｎ）ｍｏｄ  ｐも１に等しくなる。したがって、（ｓe  ｍｏｄ  ｎ）ｍｏｄ  ｐがＦ（ｍ，ｎ）ｍｏｄ  ｐに等しい場合、ｓe  ｍｏｄ  ｎ＝Ｆ（ｍ，ｎ）であるか、ｓe  ｍｏｄ  ｎがちょうどＦ（ｍ，ｎ）のｐの倍数内であるかのいずれかである。
【００３９】
当然、当業者には明らかなように、ｓe  ｍｏｄ  ｎおよびＦ（ｍ，ｎ）の値は、単に２桁の数字ではなく、むしろ、何百桁もの長さの非常に大きい数字である。したがって、（ｓe  ｍｏｄ  ｎ）ｍｏｄ  ｐがＦ（ｍ，ｎ）ｍｏｄ  ｐに等しいことの検証が、ｓe  ｍｏｄ  ｎ＝Ｆ（ｍ，ｎ）であることを、非常に高い確信をもって証明できるように、１組の特定の十分に大きい値の中から、ｐについてのランダムな値を選択することができる。
【００４０】
しかし、（ｓe  ｍｏｄ  ｎ）ｍｏｄ  ｐの計算は、依然として、上述したように計算上高価となり得る、指数項を計算するタスクに直面する。しかし、法演算の特性により、任意の除数が与えられると、任意の数を、除数の倍数プラス除数未満の何らかの余りとして表すことができる。この場合も、上記の簡単な例を考慮して、数字１６は、３の５倍（すなわち１５）プラス余り１として表すことができる。したがって、項ｓe  ｍｏｄ  ｎによって得られた余りを、元のｓeマイナス除数ｎの何らかの倍数として表すことができる。数学的に、これは、ｓe  ｍｏｄ  ｎ＝ｓe−（ｓe  ｄｉｖ  ｎ）ｎと表すことができる。値「Ｋ」がｓe  ｄｉｖ  ｎに等しいと定義される場合、この方程式は、ｓe  ｍｏｄ  ｎ＝ｓe−Ｋｎになる。
【００４１】
上記のｐを法とした公式においてｓe  ｍｏｄ  ｎをｓe−Ｋｎと置き換えることによって、（ｓe−Ｋｎ）ｍｏｄ  ｐ＝Ｆ（ｍ，ｎ）ｍｏｄ  ｐが得られる。法演算の特性によって、等号の左の項を展開することができ、この方程式は、（（ｓ  ｍｏｄ  ｐ）e−（Ｋ  ｍｏｄ  ｐ）（ｎ  ｍｏｄ  ｐ））ｍｏｄ  ｐ＝Ｆ（ｍ，ｎ）ｍｏｄ  ｐと書き換えることができる。左側の値は、（１）ｓ  ｍｏｄ  ｐ、（２）Ｋ  ｍｏｄ  ｐ、および（３）ｎ  ｍｏｄ  ｐに依存する。これらの項のそれぞれは、ｐを法とし、したがって、比較的小さい値をもたらす。というのは、ｐは、管理可能に小さくなるように選択することができ、ｐを法とする任意の項は、数学的に、ｐより小さくなければならないからである。さらに、指数項（ｓ  ｍｏｄ  ｐ）eは、ｐを法とした二乗および乗算を使用して、かなり効率的に計算することができる。これは、計算に使用される値が小さいままであり、したがって、計算が比較的効率的であることを確実にする。
【００４２】
上述したように、ｐは、１組の特定のかなり大きい値の中からランダムに選択することができる。一実施形態において、１組の特定の値は、１組の素数とすることができる。ｐがそこから選択されている素数が、かなり大きいことを確実にするために、１２８ビット以上の素数を使用することができる。代替実施形態において、ｐは、２つの素数ｐ1とｐ2の積になるように選択することができ、そのそれぞれは、６４ビット長さとすることができる。示されるように、こうした方法でｐを選択する１つの利点は、必要な計算を一度はｐ1を法として実行し、一度はｐ2を法として実行することができ、この場合、各計算は、現代の６４ビットプロセッサを使用することによって、特に効率的であり得るということである。さらに別の実施形態において、ｐは、３つ以上の素数の積として、または小さい素数のみの積である任意の「滑らかな」数を含まない１組の数から、特定の範囲内でランダムに選択することができる。
【００４３】
図３を参照すると、受信側コンピューティング装置１０および署名入りメッセージ３１、公開鍵２１および事前に計算された値Ｋ２１０を含む環境例２００が示されている。示されるように、受信側コンピューティング装置１０は、事前に計算された値Ｋ２１０を受信する場合、図３に示されるように、メッセージデータｍ２３１のように、署名入りメッセージ３１の構成要素である署名ｓ２３２をより効率的に検証することができる。同様に、図３には、公開鍵２１の構成要素、すなわち法ｎ２２１および公開指数ｅ２２２も示されている。
【００４４】
一実施形態において、事前に計算された値Ｋ２１０を、下位互換性のある機構を介して受信側コンピューティング装置１０に提供することができる。署名ｓ２３２など多くの署名は、追加のフィールドを追加することに備える符号化されたフォーマットで署名入りメッセージ３１を備えている。署名を提供するために一般に使用されているこうしたフォーマットの例には、ＡＳＮ．１標準またはＸＭＬ標準に準拠するフォーマットなどがある。こうした拡張可能なフォーマットを使用した署名の提供によって、事前に計算された値Ｋ２１０を含み得る新しいフィールドの追加が可能になる。受信側コンピューティング装置１０は、最新の妥当性検査ソフトウェアを含む場合、こうした最新のソフトウェアは、署名ｓ２３２を構文解析し、新しいフィールドを識別し、事前に計算された値Ｋ２１０を抽出し、本明細書に記載されているより効率的な機構を使用した署名の検証に取りかかることができる。一方、受信側コンピューティング装置１０が従来の妥当性検査ソフトウェアを含む場合、こうした従来のソフトウェアは、依然として、署名ｓ２３２を取得することができ、単に、事前に計算された値Ｋ２１０を含む新しいフィールドを無視することができる。こうした場合、従来の妥当性検査ソフトウェアは、単に、既知のあまり効率的ではない機構によってｓe  ｍｏｄ  ｎ＝Ｆ（ｍ，ｎ）を検証することによって、署名ｓ２３２の妥当性を検査することができる。
【００４５】
事前に計算された値Ｋ２１０は、こうした下位互換性がある方法で提供される場合、署名ｓ２３２の一部として、したがって、署名入りメッセージ３１ｋの一部として提供されることになり、図３に示されているように別々に提供されるのではない。しかし、代替実施形態において、事前に計算された値Ｋ２１０を、図３に示されているように、別々に提供することができ、それによって、こうしたコンピューティング装置が署名ｓ２３２を構文解析する必要なく、任意のコンピューティング装置がＫを事前に計算することができるようにする。
【００４６】
図３からわかるように、事前に計算された値Ｋ２１０は、それぞれ署名入りメッセージ３１または公開鍵２１のいずれかにすでに存在していたｓ、ｅ、およびｎの値のみに基づく。したがって、事前に計算された値Ｋ２１０を受信側コンピューティング装置１０に提供することにおける追加のセキュリティリスクはない。というのは、Ｋは、署名入りメッセージ３１および公開鍵２１にすでに存在していた以外の追加の情報を含まないからである。同様に、受信側コンピューティング装置１０とは異なるコンピューティング装置上で値Ｋ２１０を計算することにおける追加のセキュリティリスクはない。
【００４７】
しかし、事前に計算された値Ｋ２１０は、上述したように、項ｓeに正比例する。大きい値のｅでは、Ｋの値も同様に大きくなる。こうした大きいＫは、送信するには効率的ではない可能性があり、潜在的により重要なことは、こうした大きいＫは、受信側コンピューティング装置１０が、署名２３２を検証するために、（Ｋ  ｍｏｄ  ｐ）項の計算に使用するには効率的ではない可能性がある。適切にサイズ変更されたＫ値を維持するために、公開指数ｅ２２２を、２や３などの小さい値になるように選択することができる。ｅ＝２が使用される場合、コンピューティング装置１０によって実行される結果として生じる計算は、非常に効率的であり得る。しかし、ｅ＝２を使用することは、当業者にはよく知られているように、いくつかの欠点を有する。これらの欠点は、適切な関数Ｆ（ｍ，ｎ）との組み合わせで、ｅ＝３を選択することによって回避することができる。当業者には知られているように、Ｆ（ｍ，ｎ）が結果のビットを十分ランダム化しない場合、またはより正確には、疑似ランダム化しない場合、ｅ＝３は、あまり高いセキュリティを提供しない可能性がある。しかし、結果のビットをランダム化する適切に選択されたＦ（ｍ，ｎ）は、ｅ＝３で十分なセキュリティを提供することができる。
【００４８】
上述したように、署名ｓ２３２は、（（ｓ  ｍｏｄ  ｐ）e−（Ｋ  ｍｏｄ  ｐ）（ｎ  ｍｏｄ  ｐ））ｍｏｄ  ｐ＝Ｆ（ｍ，ｎ）ｍｏｄ  ｐを検証することによって検証することができる。したがって、等号の左の式を評価するために、コンピューティング装置１０は、（１）ｓ  ｍｏｄ  ｐ、（２）Ｋ  ｍｏｄ  ｐ、および（３）ｎ  ｍｏｄ  ｐを決定することができる。ｐが２つの６４ビットの数字ｐ1とｐ2の積として形成される場合、コンピューティング装置１０は、（１）ｓ  ｍｏｄ  ｐ1、（２）ｓ  ｍｏｄ  ｐ2、（３）Ｋ  ｍｏｄ  ｐ1、（４）Ｋ  ｍｏｄ  ｐ2、（５）ｎ  ｍｏｄ  ｐ1、および（５）ｎ  ｍｏｄ  ｐ2を決定することができる。当業者によって知られているように、ｎが２０４８ビット長さであると仮定すると、ｓ  ｍｏｄ  ｐ1の計算は、６４×６４ビットの約３２回の単純乗算を必要とし得る。ｅ＝３の場合、Ｋは、ｓの長さの２倍とすることができ、したがって、Ｋ  ｍｏｄ  ｐ1の計算は、６４×６４ビットの６４回の単純乗算を必要とし得る。最後に、ｎ  ｍｏｄ  ｐ1も同様に、３２回の単純乗算を必要とし得る。これらｐ2を法とする各項は、同様の数の単純乗算を必要とし得るため、ｐが２つの６４ビットの数字ｐ1とｐ2の積である場合、（（ｓ  ｍｏｄ  ｐ）e−（Ｋ  ｍｏｄ  ｐ）（ｎ  ｍｏｄ  ｐ））ｍｏｄ  ｐの全体的な計算は、６４ビットプロセッサにおける最小２５６回の単純乗算と、わずかの追加演算を必要とし得る。これに比べて、変数のすべてを上記の例と同じとしたｓe  ｍｏｄ  ｎの計算は、約３０００〜４０００回の単純乗算を必要とし得る。したがって、外部ソースから事前に計算された値Ｋ２１０を取得し、適切にサイズ変更されたｐと共に、ｅ＝２またはｅ＝３を選択することによって、記載した計算は、従来の署名検証より１０倍以上速い可能性がある。
【００４９】
図４を参照すると、一実施形態による環境例３００が示されている。示されるように、送信側コンピューティング装置２０は、署名入りメッセージ３１を作成するために関連する署名ｓ２３２だけではなく、事前に計算された値Ｋ１２０を計算する。当業者によって認識されるように、事前に計算された値Ｋ２１０の計算は、署名ｓ２３２の計算に比べて、ごく少ない。その結果、受信側コンピューティング装置１０は、外部ソースから事前に計算された値Ｋ２１０を受信した場合、１０倍もより効率的に署名ｓ２３２を検証することができる一方で、送信側コンピューティング装置２０は、署名ｓ２３２の計算と共に、事前に計算された値Ｋ２１０を計算する際に、対応する性能のペナルティを被らない。したがって、図４に示されている一実施形態において、送信側コンピューティング装置２０は、受信側コンピューティング装置１０に事前に計算された値Ｋ２１０を提供することができる。
【００５０】
図５を参照すると、代替実施形態による環境例４００が示されている。図示されるように、送信側コンピューティング装置２０は、メッセージに署名して、署名入りメッセージ３１を作成し、事前に計算された値Ｋ２１０を計算する能力を所有する必要はない。代わりに、事前に計算された値Ｋ２１０は、サーバコンピューティング装置４１０など、中間コンピューティング装置によって計算することができる。一実施形態において、サーバコンピューティング装置４１０は、下位互換性を提供するために、上述した方法で、事前に計算された値Ｋ２１０を新しいフィールドに挿入することができる。あるいは、サーバコンピューティング装置４１０は、単に、事前に計算された値Ｋ２１０を署名入りメッセージ３１に追加することができる。いずれの場合も、サーバコンピューティング装置４１０による事前に計算された値Ｋ２１０の単一回の計算は、サーバコンピューティング装置４１０のクライアントとしてそれぞれ働くように示されているコンピューティング装置１０、１１、１２など、署名入りメッセージ３１の各受信者によって別々に実行される署名ｓ２３２の検証の１０倍の効率を提供することができる。したがって、署名入りメッセージ３１を受信するコンピューティング装置１０、１１、および１２が署名ｓ２３２を検証しようと試みるとき、事前に計算された値Ｋ２１０の計算の際にサーバコンピューティング装置４１０によって経験される計算の任意の増加を、コンピューティング装置１０、１１、および１２のそれぞれによって経験される計算効率の付随的な増加によってそれ以上オフセットすることができる。
【００５１】
図４および図５に示されている実施形態のそれぞれ、および上記は、１つまたは複数の外部コンピューティング装置からの署名入りメッセージ３１、公開鍵２１および事前に計算された値Ｋ２１０の配布に焦点を置くが、代替実施形態は、送信者および受信者として働く同じコンピューティング装置の異なる構成要素を企図する。例えば、１つのコンピューティング装置におけるあるアプリケーションは、事前に計算された値Ｋ２１０を含めて、署名入りメッセージ３１を送信することができ、同じコンピューティング装置における別のアプリケーションは、署名を受信し、検証することができる。言い換えると、前者のアプリケーションは、図４のコンピューティング装置２０として働き、後者のアプリケーションは、図４のコンピューティング装置１０として働く。
【００５２】
同じように、図５を参照すると、１つのコンピューティング装置におけるあるアプリケーションは、中央サーバ４１０として働くことができ、Ｋを必要とし得る同じコンピューティング装置における１つまたは複数の他のアプリケーションのために、事前に計算された値Ｋ２１０を決定することができる。一実施形態例において、署名入りメッセージ３１は、コンピューティング装置内通信を介して受信されたか、コンピューティング装置間通信を介して受信されたかにかかわらず、受信側コンピューティング装置において、後で使用するために、事前に計算された値Ｋ２１０と共に格納される。したがって、前者のアプリケーションは、後者のアプリケーションのために、事前に計算された値Ｋ２１０を決定し、それが署名入りメッセージ３１に関連付けられ、任意選択で署名入りメッセージ３１と一緒に配置されるように、Ｋの格納をさらに容易にすることができる。別の実施形態において、コンピューティング装置１０などの受信側コンピューティング装置は、事前に計算された値Ｋ２１０を決定するための特定のアプリケーションを有する必要はなく、代わりに、決定されたＫの値が保存され、署名入りメッセージ３１に関連付けられ、任意選択で署名入りメッセージ３１と一緒に配置されることを除いて、それが通常使用するどんなアプリケーションでも使用することができる。こうした場合、署名２３２のその後の検証は、より効率的となり得る。
【００５３】
さらに別の実施形態において、署名２３２は、値ｓだけではなく、埋め込み関数Ｆへの入力として使用することができる１つまたは複数の追加の値ｔも含む。メッセージ３０に署名する際、署名者は、適切な値ｔを生成し、ｓe  ｍｏｄ  ｎ＝Ｆ（ｍ，ｎ，ｔ）となるように、値ｓを計算することができる。そして署名は、値ｓおよび値ｔの両方を含み得る。事前に計算された値Ｋ２１０は、上記で詳しく説明したように計算することができる。ｓおよびｔの両方を含む新しい署名の検証者は、Ｆへの追加の入力として使用するために、ｔを抽出することができ、上記で詳しく説明したのと同じ方法で、署名を検証するために、ｓを抽出することができる。
【００５４】
上記の説明からわかるように、特定の事前に計算された情報の、署名を検証しようと務めるコンピューティング装置への提供は、こうした署名を検証するのに必要な計算作業の１０分の１以上の低減を提供することができる。本明細書に記載された主題の多くの可能な変形を鑑み、以下の特許請求の範囲およびその均等物の範囲内に含まれ得るすべての実施形態を、我々の発明として主張する。