(57)【特許請求の範囲】
【請求項１】
秘密鍵（ｓ）を与えられた第１暗号化ユニット（Ａ）と第２暗号化ユニット（Ｂ）との間で交換される少なくとも一つのデジタルデータアイテム（ｚ）に関する暗号化タスクを公開鍵を用いて実行するための方法であって、当該方法は、
前記暗号化タスクを、少なくとも、
前記デジタルデータアイテムの部分値（ｚ’）を得るために前記公開鍵の全部または一部を用いてオープンデジタル処理に前記デジタルデータアイテム（ｚ）を委ねる仲介暗号化ユニット（Ｃ）によって実行される第１ステップ（６）と、
前記デジタルデータアイテムに関する前記暗号化タスクを達成するために前記公開鍵の全部または一部を用いてパブリックデジタル処理に前記部分値（ｚ’）を委ねる第２暗号化ユニット（Ｂ）によって実行される第２ステップ（８）と、
の二つのステップに分け、これらステップは、異なる暗号化ユニットによって実行されることを特徴とする方法。
【請求項２】
前記仲介暗号化ユニット（Ｃ）は、前記第２暗号化ユニット（Ｂ）が駐在する物理装置とは別の物理装置に駐在することを特徴とする請求項１に記載された暗号化タスクを実行する方法。
【請求項３】
前記仲介暗号化ユニット（Ｃ）は、前記第１暗号化ユニット（Ａ）が駐在する物理装置に駐在することを特徴とする請求項１に記載された暗号化タスクを実行する方法。
【請求項４】
前記暗号化タスクが、電子サインの検証を含み、前記デジタルデータアイテムが、前記秘密鍵（ｓ）により前記第１暗号化ユニットにおける数（ｍ＊）に適用される秘密デジタル処理の結果として得られるサイン（ｚ）であり、
前記オープンデジタル処理は、本質的に、前記公開鍵の第１部分を用いて前記サイン（ｚ）をサイン部分値（ｚ’）に変換することにあり、
前記パブリックデジタル処理は、本質的に、正当なサインに有利に完結する値（ｚ”）が前記数（ｍ＊）に等しい場合に、正当なサインに有利に完結することを可能にする前記値（ｚ”）を得るために、前記公開鍵の第２部分を用いて前記サイン部分値（ｚ’）を変換することにあることを特徴とする請求項１ないし３の何れか１項に記載された暗号化タスクを実行する方法。
【請求項５】
前記公開鍵が、第１整数（ｎ）と第２整数（ｖ）のペアであり、前記秘密デジタル処理が、前記公開鍵の第１累乗（ｓ）モジューロ第１整数（ｎ）に前記数（ｍ＊）を増加させることにあるとしたときに、
第２累乗（ａ）モジューロ第１整数（ｎ）に前記サイン（ｚ）を増加させるために、前記公開鍵の第２整数（ｖ）よりも厳密に小さく且つ１よりも厳密に大きな第３整数（ａ）が前記オープンデジタル処理において使用され、
前第３累乗（ｂ）モジューロ第１整数（ｎ）に前記サイン部分値（ｚ’）を増加させるために、記第３整数（ａ）による前記第２整数（ｖ）のユークリッド除算の商に等しい第４整数（ｂ）が前記パブリックデジタル処理において使用されることを特徴とする請求項４に記載された暗号化タスクを実行する方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の技術分野は暗号化の分野である。暗号化は、２又はそれ以上のエンティティ(entities)間のトランザクションを保護することにおいてアプリケーションを見出す。これらのアプリケーションの中から、メッセージ暗号化方法、識別(identification)方法、電子サイン(electronic signing)方法、あるいはメッセージ認証方法が見出される。暗号化方法は、本来、受信者のみが解読できるような方法でメッセージを暗号化することにある。識別方法は、本来、送信エンティティ(sending entity)の身元(identity)を検証することにある。電子サイン方法は、本来、メッセージがそのメッセージを生成したエンティティによってサインされたというようなものであることを検証することにある。メッセージ認証方法は、本来、受信されたメッセージが既知の身元の送信エンティティによって実際に送信されたことを検証することにある。
【０００２】
さらに詳しくは、本発明の技術分野は、いわゆる公開鍵(public key)暗号化の分野である。暗号化方法は、多くの場合プローバ(prover)と呼ばれる第１エンティティが、公開鍵が関連づけられた秘密鍵(private key)を用いて第１デジタル操作を秘密に実行する例で知られている。これらの操作の１又はそれ以上の実行結果は、多くの場合ベリファイア(verifier)と呼ばれる第２エンティティに伝送される。そして、ベリファイアは、第１操作が秘密鍵を用いて実際に実行されたことを検証する第２操作を、公開鍵を用いて実行する。これらの方法は、メッセージを認証またはサインするため、または他に第１エンティティを認証するために有用であり、後の例では識別(identification)について述べる。逆に、暗号化方法はまた、第２エンティティが公開鍵を用いてメッセージを暗号化することから始めることで知られている。そして、関連づけられた秘密鍵を保持する第１エンティティのみがそのメッセージを解読することができる。
【０００３】
いわゆるゼロ知識暗号化方法(zero knowledge cryptographic methods)において、検証は、立証された方法で且つ科学団体によって完全に妥当であると認知された前提の下で、プロトコルに従って進行し、秘密鍵については一切明らかにしない。
本発明がアプリケーションを見出すことに関する公知の方法のうち、ＲＳＡ(Rivest, Shamir, Adleman)アルゴリズムまたはいわゆる離散対数問題(discrete logarithm problem)に基づくものについて述べられるであろう。
【背景技術】
【０００４】
公開鍵暗号化は、とりわけ、例えばバンクカード(bank card)または電子財布(electronic purse)による電子決済(electronic payment)に有用である。近接決済(proximity payment)の場合においては、決済端末は全く同時刻に公共の場に設置されていなければならならず、従って公開鍵暗号化方法の使用を促し、そして、安価でなければならないことにより、限られた計算能力を有するチップの使用を促す。オンライン決済の場合においては、業者のサーバまたは決済サーバ（または他に仲介サーバ）は、或る時刻に大量の検証(verification)を同時に実行させられる可能性がある。双方の場合において、検証タスク(verification task)、即ち公開鍵を使用する暗号化タスクを軽減することを可能にする解決策を見つけることが望ましい。
【０００５】
公知の方法において、公開鍵暗号化は、極めて大きな整数の取り扱いから逆関数を取り出すことにおける整数の理論による困難性に基づいている。欠点は、十分なセキュリティを保証するために、公開鍵の使用が通常大きな数による相当量のユークリッド除算および相当量の乗算を必要とすることであり、その演算(operation)は対応する量の計算資源を消費する。
【０００６】
ベリファイア(verifier)のより大きな又はより小さな作業負荷の評価のような様々な評価基準の関数に従って検証(verification)のレベルを調節することを考えることは可能である。この解決策に関する問題は、この検証(verification)に合うかもしれない確信(conviction)が同じ割合で修正されることである。しかしながら、あるアプリケーションは、強い確信(strong conviction)を検証(verification)に合わせる能力を必要とする。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
本発明の第１の目的は、送信エンティティ及びまたはこのエンティティによって送信されたデータの信憑性について後(the latter)の確信のレベルを減じることなく、実行されるべき計算量を低減することにより、検証プロトコル(verification protocols)においてベリファイアのタスクを軽減することである。
【０００８】
本発明の第２の目的は、限られた計算能力を有する超小型回路を用いて、削減された時間で伝送を実行することを可能にすることである。
【課題を解決するための手段】
【０００９】
これを達成するため、本発明は、秘密鍵を与えられた第１エンティティと第２エンティティとの間で交換される少なくとも一つのデジタルデータアイテムに関する公開鍵を用いて暗号化タスクを実行する方法に関する。本方法は、上記暗号化タスクが、少なくとも、
前記データアイテムの部分的イメージを得るために前記公開鍵の全部または一部を用いてオープンデジタル処理に前記データアイテムを委ねる仲介エンティティによって実行される第１ステップと、
前記データアイテムに関する前記暗号化タスクを達成するような方法で前記公開鍵の全部または一部を用いてパブリックデジタル処理に前記部分的イメージを委ねる第２エンティティによって実行される第２ステップと、
の二つのステップに分けられることで特徴づけられる。
【００１０】
本方法は、第２エンティティからなるベリファイアが、その一部を仲介エンティティに委任することによってそれ自身の作業負荷を低減するために、ベリファイアに利用可能なものよりも多くの計算手段を与えられるか、ベリファイアよりも少ないトランザクションに参加することを可能にする。
【００１１】
デジタル処理は、自由にアクセス可能である点においてオープンである。後のエンティティのエンティティ(the latter entity)が公開鍵を用いた暗号化タスクにおいて部分的に介在し、そしてもし仲介エンティティが部分的イメージを害したとすれば、暗号化タスクの失敗をもたらし、第２エンティティが暗号化タスクを終了するので、仲介エンティティは、ベリファイアが関係している限り、信頼できるエンティティである必要はない。暗号化タスクが検証(verification)である場合、検証が承認(confirm)されたか拒否(deny)されたかどうかによって、ｙｅｓまたはｎｏで終了する。この場合、仲介エンティティは、ｎｏをｙｅｓに変えることはできない。第１ステップが公開鍵の全部または一部を用いて実行され、そしてオープンデジタル処理に委ねられたデータアイテムがまた第１エンティティにより秘密デジタル処理に委ねられるので、仲介エンティティとのやりとりはオープンワールド(open world)内でなされてもよい。
【００１２】
有利に、本方法は、第２エンティティが駐在する物理装置とは別個の物理装置に仲介エンティティが駐在することで特徴づけられる。
【００１３】
そして第２エンティティは、第１エンティティから受信したデータアイテムを、仲介エンティティを受け入れる任意のパワフルな計算装置に伝送する。計算装置は部分的イメージを第２エンティティに返す。オープンネットワーク上では、仲介エンティティは、第１エンティティから直接的にデータアイテムを受信する委任されたサーバ（プロキシサーバ）で受け入れられる。
【００１４】
さらに有利に、第２エンティティが、多くの第１エンティティに関して多くの暗号化タスクを実行するために適用される場合、本方法は、第１エンティティが駐在する物理装置に仲介エンティティが駐在することで特徴づけられる。
【００１５】
セキュリティ特性(security properties)を損なうことなく作業負荷の一部をベリファイア(verifier)からプローバ(prover)に移すことは、初期プロトコル(initial protocol)の特別な変形を特定することに等しい。
【００１７】
別に、本発明は、さらに詳しくは、前記暗号化タスクが、電子サイン(electronic signature)の検証(verification)を含み、秘密鍵を用いて第１エンティティにおける秘密デジタル処理に委ねられる数である前記デジタルデータアイテムがサイン(signature)を与えることで特徴づけられ、且つ、
オープンデジタル処理は、本質的に、前記公開鍵の第１部分を用いて前記サインをサイン部分イメージ(signature partial image)に変換することにあり、
パブリックデジタル処置は、本質的に、正当なサイン(valid signature)に有利に完結する値が前記数に等しい場合に、正当なサイン(valid signature)に有利に完結する前記値を得るために、前記公開鍵の第２部分を用いて前記サイン部分イメージを変換することにあることで特徴づけられる。
【００１９】
本発明の他の詳細および利点は、添付図面を参照して次に述べられる本発明の実施から一層よく理解されるであろう。その添付図面において、図１は、電子サイン方法における本発明の代表的実施を示し、図２から４は、識別方法における本発明の代表的実施を示し、図５は、認証方法における本発明の代表的実施を示す。
【発明を実施するための最良の形態】
【００２０】
図１は、電子サイン(electronic signing)方法における本発明の第１の代表的実施を示す。電子サインの本方法は、例えば、Rivert、ShamirおよびAdlemanにより説明されたＲＳＡサインアルゴリズム(“A method for obtaining digital signatures and public-key cryptosystems”, CACM, Vol.21 No.2, Feb. 1978, pp.120-126)を使用する。公知の方法において、ＲＳＡアルゴリズムは、ペア（ｎ，ｖ）からなる公開鍵(public key)の使用および秘密鍵(private key)ｓの使用を基にしている。ここで、ｎは、通常、秘密が保持された二つの素数ｐおよびｑの積(product)であり、ｖは、積（ｐ−１）（ｑ−１）についての素数である。
【００２１】
デジタル形式において、２進法の文字列(binary string)からなるメッセージｍは、この点について整数と考えられる。メッセージｍに電子的にサインするためのステップ１において、通常、第１エンティティ(first entity)Ａは、ｎよりも小さな整数ｍ＊を得るために、ハッシュ関数Ｈをメッセージｍに適用し、それからハッシュ関数の結果のフォーマッティング(formatting)をする。このフォーマッティングは、通常、数ｎを符号化するビット数に等しいビット数で整数がコード化されるような方法で、ハッシュ関数の結果として生じる２進数ワード(binary word)に全てゼロではないビットを付け加わえる。
【００２２】
エンティティＡは、次に、整数ｍ＊の累乗ｓモジューロｎに等しい電子サイン(electronic signature)ｚを生成する。電子サインｚは、従って累乗ｓに増加された整数ｍ＊を数ｎによりユークリッド除算した余りに等しい。数ｎは極めて大きく且つエンティティＡのみが値ｓを知っているので、実際にはＡ以外のエンティティが次の式を満足する整数ｚを生成することは不可能である。
ｚ＝（ｍ＊）ｓ（ｍｏｄｕｌｏ  ｎ）
ステップ１は、メッセージｍおよびその電子サインｚを送信して終了する。
【００２３】
第２エンティティ(second entity)によるメッセージｍおよびその電子サインの受信は、ステップ３を起動するトランジション(transition)２を有効にする。ステップ３では、エンティティＢは、数ｍ＊を局所的に再取得するために、ハッシュ関数Ｈをメッセージｍに適用する。
【００２４】
本発明によれば、ステップ４は、公開鍵の値ｖを次の形式に分解する。
ａ・ｂ＋ｃ＝ｖ
ここで、整数ａおよびｂは１よりも厳密に大きい。整数ｃは例えば余りであり、もしそれが存在すれば、ｖをｂでユークリッド除算したものである。
【００２５】
仲介エンティティＣによるサインｚの受信は、ステップ６を起動するトランジション５を有効にする。ステップ６において、エンティティＣは、サインｚモジューロｎのａ乗に等しいサイン部分値(signature partial value)ｚ’を生成する。ステップ６は、サイン部分値ｚ’を送信して終了し、そして必要であれば、整数ｂおよびｃの値を送信して終了する。
【００２６】
エンティティＢによるサイン部分値ｚ’の受信並びに値ｂおよびｃの受信は、ステップ８を起動するトランジション７を有効にする。ステップ８において、エンティティＢは、ｃ乗に増加されたサイン値ｚと、ｂ乗に増加(rise)されたサイン部分値ｚ’のプロダクトモジューロｎに等しい整数ｚ”を生成する。ここで、通例の慣習は、１に等しいゼロイクスポーネント(zero exponent)を用いて累乗(power)を定義する。
【００２７】
次に、エンティティＢは、整数ｚ”が整数ｍ＊に等しいかどうかをステップ８においてテストする。この場合、受信されたメッセージｍは、実際にエンティティＡによってサインされたものである。
【００２８】
具体的に言うと、二つの整数のｎによる除算の二つの余りの積のｎによる除算の余りが、これら二つの整数の積のｎによる除算の余りに等しいとすれば、次のことが得られる。
[(z’)b.(z)c](modulo n) = [(z’)b(modulo n).(z)c(modulo n)](modulo n)
= [(z)a.b(modulo n).(z)c(modulo n)](modulo n)
= [(z)a.b(z)c](modulo n)
= [(z)a.b+c](modulo n)
故に、
z”= (z)v(modulo n)
【００２９】
セキュリティがステップ６により減少される可能性が少ないか又はないので、仲介エンティティＣは、信頼のあるエンティティである必要はない。具体的に言うと、ｍ＊の値について、累乗ａモジューロｎにサイン値ｚを増加(rise)することによる以外に、ｍ＊に等しいｚ”の値を計算することを可能にする累乗ｂにそれを増加するような数ｚ’を見つけ出すことは実際には不可能である。
【００３０】
図１を参照して述べた代表的な実施において、エンティティＢのチャージ(charge)の下での暗号化タスクは、受信されたメッセージｍが実際にエンティティＡによってサインされたという事実の検証である。もしサインｚモジューロｎの累乗ｖへの増加が数ｍ＊に等しければ、この検証は肯定的(positive)である。累乗ｖへの増加のための計算時間は、実質的にビットにおけるｖのサイズに比例する。この暗号化タスク、さらに詳しくは累乗ｖへの増加の計算は、本明細書ではステップ６および８に割り当てられている。
【００３１】
仲介エンティティＣは、サインｚの累乗ｖへの増加の計算のパートであるステップ６において実行する。エンティティＢは、サインｚの累乗ｖへの増加の計算の相補的パートであるステップ８において実行する。エンティティＢにより実行される計算時間は、実質的にｂ＋ｃに比例する。従って、エンティティＢに必要とされる計算能力は、実質的にファクタａで除算することにより低減される。エンティティＢに必要とされる計算能力はまた、もし数ｃがゼロであれば低減される。これは、数ｖを二つの整数ａおよびｂの積に分解することが可能であるような場合である。
【００３２】
図１に表されたエンティティＣは、ステップ４を実行し、そしてトランジション５を有効にした後にステップ６を実行する。ステップ４は、メッセージｍをそのサインｚと共にそれぞれ送信して実行される必要はない。ｖの与えられた値について、もしｃがゼロでなければ、数ａ，ｂ，ｃが、エンティティＡ，Ｂ，Ｃとは関係なく、ただ一度だけ計算される。そしてエンティティＣは、単に番号ａを知ることを要するのみである。そしてエンティティＢは、もしｃがゼロでなければ、単に数ｂおよび数ｃを知ることを要するのみである。この場合、数ｂおよびｃは、ステップ６で送信されず、そしてサイン部分値ｚ’のトランジション７の簡単な受信により有効(enable)とされる。
【００３３】
有利に、エンティティＣはエンティティＢが駐在する装置とは別個の物理装置に駐在する。従って、エンティティＢが駐在する物理装置は、エンティティＢが暗号化タスクの全体を実行するとすれば備えるであろうものと比較して、低減された計算手段を備えることができる。
【００３４】
エンティティＣは、エンティティＡが駐在するものとは別個の物理装置、またはエンティティＡと同じ物理装置に駐在することができる。
【００３５】
エンティティＡおよびＣが一つの又は同じ物理装置に駐在する場合には、数ａ，ｂあるいはｃは、この物理装置に保存される。もしｃがゼロでなければ、エンティティＡおよびＣが駐在する物理装置は、メッセージｍ、サインｚ、部分的サインｚ’、および数ｂ，ｃを送信する。もしｃがゼロであれば、エンティティＡおよびＣが駐在する物理装置は、メッセージｍ、部分的サインｚ’、および数ｂを送信する。
【００３６】
図１を参照してまさに説明した代表的実施は、任意のエンティティによってサインされた任意のメッセージの検証に適合する。
【００３７】
プローバの（ｎ，ｖ）を証明(certificate)する公開鍵の検証を促進することも同様に有利である。証明(certificate)は、証明機関によって計算された電子的サインであり、プローバの公開鍵および身元(identity)に関係し、従って後者(the latter)が証明機関の公開検証を保持するという条件で、任意の他のエンティティによって検証されるかもしれない方法でそれらを関連づけている。
【００３８】
この証明もまたＲＳＡアルゴリズムを用いて計算されれば、証明を検証するために暗号化タスクの上述した分解(decomposition)は、証明を受け取るエンティティＢにおける検証計算の促進を可能にする。さらに一般に、もし証明が本発明が適合するサインスキームを用いて計算すれば、電子サインを検証するためにこの証明を使用するベリファイア(verifier)による証明の検証に本発明を適用することは有益である。
【００５８】
要約すると、本方法は、識別または電子サインの、メッセージ認証のメカニズムを組み込む安全な電子トランザクションにおいて、エンティティＢから構成されるベリファイアの計算負荷を減少させることを可能にする。
【００５９】
それは、ベリファイアが検証(verification)ステップに由来しているという確信を減じることなく、必ずしも信頼できない外部のエンティティＣにこれらの計算の一部を委任することにある。さらに正確には、それは、少なくともステップ（６，１５）が外部のエンティティＣによって実行できるような方法で、検証(verification)タスクを少なくとも二つのステップ（６，１５）および（８，１７）に分けることにある。本方法は、特に、ＲＳＡ(Rivest, Shamir, Adleman)電子サインスキームに適合すると共に、別々のアルゴリズムに基づくメッセージ認証プロトコルに適合する。
【図面の簡単な説明】
【００６０】
【図１】電子サイン方法における本発明の代表的実施を示す図である。
【符号の説明】
【００６１】
１，３，４，６，８  ステップ
２，５，７  トランジション
【図１】
0004354808.tif 000002