(57)【要約】本発明は、フォーマット関数（μ）により平文メッセージ（ｍ）をフォーマットするステップと、式ｃ＝μ（ｍ）ｅ  ｍｏｄ  Ｎに従って公開鍵（Ｎ，ｅ）により前のステップの結果を累乗するステップとを含む暗号化方法に関する。ここで、ｃは暗号化メッセージであり、μ（ｍ）はフォーマット・ステップの結果であり、ｅおよびＮは、公開鍵の要素である。本発明は、フォーマット関数（μ）がＰＳＳ関数であることを特徴とする。本発明は、例えば、スマートカード用の、例えば、ＲＳＡタイプのような暗号化に使用することができる。【特許請求の範囲】
【請求項１】
フォーマット関数（μ）により平文メッセージ（ｍ）をフォーマットするステップと、式ｃ＝μ（ｍ）ｅ  ｍｏｄ  Ｎに従って公開鍵（Ｎ，ｅ）により前のステップの結果を累乗するステップとを含み、ｃは暗号化したメッセージであり、μ（ｍ）はフォーマット・ステップの結果であり、ｅおよびＮは前記公開鍵の要素である暗号化方法であって、
前記フォーマット関数（μ）はＰＳＳ関数であることを特徴とする方法。
【請求項２】
前記フォーマット関数μは、下式
μ(m)=PSS(m)=ω｜｜s
により定義されることを特徴とし、
ｍはｋ−ｋ０−ｋ１ビットの平文テキストであり、ｒはｋ０ビットのランダム・パラメータであり、ｋ、ｋ０、ｋ１はフォーマット関数のパラメータであり、
｜｜は連結関数であり、
ω＝Ｈ（ｍ｜｜ｒ）、
【数１】
2005534068.tif 000005
Ｈ、Ｇは２つのハッシング関数であることを特徴とする、請求項１に記載の方法。
【請求項３】
フォーマット関数（μ）により平文メッセージ（ｍ）をフォーマットするステップと、式ｃ＝μ（ｍ）ｅ  ｍｏｄ  Ｎに従って公開鍵（Ｎ，ｅ）により前のステップの結果を累乗するステップとを含む暗号化方法を実行するための、フォーマット関数（μ）として規格ＰＫＣＳ  ＃２  ｖ  ２．１、ＲＳＡ暗号化規格が定義する確率的署名関数（ＰＳＳ）の使用であって、ｃが暗号化したメッセージであり、μ（ｍ）が前記フォーマット・ステップの結果であり、ＥおよびＮが公開鍵の要素であることを特徴とする使用。
【請求項４】
暗号化システムであって、
・確率的署名関数（ＰＳＳ）により平文メッセージ（ｍ）をフォーマットするステップと、
・平文メッセージ（ｍ）の暗号化が必要な場合には、式ｃ＝μ（ｍ）ｅ  ｍｏｄ  Ｎに従って第１の鍵（Ｎ，ｅ）により前記フォーマット・ステップの結果を累乗するステップであって、ｃは暗号化したメッセージであり、μ（ｍ）は前記フォーマット・ステップの結果であり、ｅおよびＮは前記第１の鍵の要素であるステップと、
・前記平文メッセージ（ｍ）に署名する必要がある場合には、式ｓ＝μ（ｍ）ｄ’  ｍｏｄ  Ｎ’に従って、第２の鍵（Ｎ’，ｄ’）により前記フォーマット・ステップの結果を累乗するステップであって、ｓは署名したメッセージであり、μ（ｍ）は前記フォーマット・ステップの結果であり、ｄ’およびＮ’は前記第２の鍵の要素であるステップと、を含むことを特徴とするシステム。
【請求項５】
前記第１の鍵および前記第２の鍵が、それぞれ第１のペアの鍵の公開鍵および第２のペアの鍵の秘密鍵であることを特徴とする、請求項３に記載のシステム。
【請求項６】
前記第１のペアの鍵および前記第２のペアの鍵が同じであることを特徴とする、請求項４に記載のシステム。
【請求項７】
ＲＳＡタイプであることを特徴とする、請求項４乃至６のいずれかに記載のシステム。
【請求項８】
請求項１または２に記載の暗号化方法を実施するためのプログラムされた手段を備える電子構成要素であって、前記プログラムされた手段が特に中央処理装置およびプログラム・メモリを備えることを特徴とする電子構成要素。
【請求項９】
請求項４乃至７のいずれかに記載の暗号化システムを実施するためのプログラムされた手段を備える電子構成要素であって、前記プログラムされた手段が、特に中央処理装置およびプログラム・メモリを備えることを特徴とする電子構成要素。
【請求項１０】
請求項７または８に記載の電子構成要素を備えるチップ・カード。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、特に公開鍵暗号化の分野で使用する暗号化方法および関連する暗号化システムに関する。本発明は、チップ・カードのような電子デバイスで実施することができる。
【背景技術】
【０００２】
完全な公開鍵暗号化システムは、一般的に、暗号化アルゴリズムおよび署名アルゴリズムを有する。このような暗号化システムは、例えば、特に集積回路、アルゴリズムを実施するようにプログラムされている計算手段、アルゴリズムを実行するのに必要な公開鍵および／または秘密鍵を記憶するための記憶手段を備えているチップ・カードで実施することができる。
【０００３】
公開鍵暗号化システムで使用される周知のアルゴリズムは、ＲＳＡアルゴリズム（Ｒｉｖｅｓｔ、ＳｈａｍｉｒおよびＡｄｌｅｍａｎにちなんで命名された）である。このアルゴリズムは、暗号化動作および署名動作を行うために使用することができる。通常、ＲＳＡアルゴリズムは、公開鍵または秘密鍵により、環境に応じて暗号化関数または署名関数によりフォーマットされている平文メッセージの累乗演算を行うためのものである。
【０００４】
それ故、ＲＳＡアルゴリズムを使用する暗号化方法は、暗号化関数μにより平文メッセージｍをフォーマットするステップと、次に下式に従ってその結果を累乗するステップとからなる。
Ｃ＝ｆ（μ（ｍ））＝［μ（ｍ）］ｅ  ｍｏｄ  Ｎ
ここで、μは暗号化関数であり、（Ｎ，ｅ）は公開鍵であり、ｆ（ｘ，Ｎ，ｅ）は指数関数ｆ（ｘ，Ｎ，ｅ）＝ｘｅ  ｍｏｄ  Ｎである。
【０００５】
次に、暗号化されたメッセージｃを、公開鍵（Ｎ，ｅ）に関連する秘密鍵である逆関数ｆ−１（ｘ，Ｎ，ｄ）により、再度ＲＳＡアルゴリズムを使用して解読することができる。
ＲＳＡアルゴリズムを使用する署名方法は、署名関数μ’により平文メッセージｍをフォーマットし、次に、下式に従ってその結果を累乗する類似の方法である。
【０００６】
ｓ＝ｆ−１［μ’（ｍ）］＝［μ’（ｍ）］ｄ’  ｍｏｄ  Ｎ’
ここで、μ’は署名関数であり、（Ｎ’，ｄ）は秘密鍵であり、ｆ−１（ｘ，Ｎ’，ｄ’）は指数関数ｆ−１（ｘ，Ｎ’，ｄ’）＝ｘｄ’  ｍｏｄ  Ｎ’である。
次に、署名は、逆関数ｆ（ｘ，Ｎ’，ｅ’）によりＲＳＡアルゴリズムを再度使用して確認することができる。（Ｎ’，ｅ’）は秘密鍵（Ｎ’，ｄ’）に関連する公開鍵である。
【０００７】
暗号化システムで使用する指数関数および暗号化または署名関数は通常既知のものである。それ故、暗号化システムのセキュリティは、秘密状態に維持するために必要不可欠な、使用する秘密鍵および公開鍵だけに依存する。
それ故、セキュリティは、特に長くなるように選択される鍵のサイズに依存する。数Ｎ、Ｎ’は、一般的に、例えば、１０２４ビットのような長い数であり、これらの数は２つの素数、Ｎ＝ｐ＊ｑ、Ｎ’＝ｐ’＊ｑ’の積に等しい。整数ｄ、ｄ’は、数Ｎ、Ｎ’に依存し、同様に長い数である。一方、整数ｅ、ｅ’は多くの場合、短い数である。
【０００８】
セキュリティのために、暗号化に使用する鍵（（Ｎ，ｅ）；（Ｎ，ｄ））、および署名に使用する鍵（（Ｎ’，ｅ’）；（Ｎ’，ｄ’））は異なるものである。
メッセージｍ１、ｍ２の署名ｓ１、ｓ２が既知のものである場合でも、秘密鍵を知らなければメッセージｍの署名ｓを生成できない場合には、署名関数μ’は機密保護されているという。暗号化システムで使用する関数μ’は、この条件を満足するように構成される。
【０００９】
署名演算のために機密保護されている既知の関数μ’は、文書Ｄ１（１９９６年Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ発行のＥｕｒｏｃｒｙｐｔ  ’９６議事録、ＬＮＣＳ  ｖｉｌ  １０７０、３９９〜４１６ページ掲載の、Ｍ．ＢｅｌｌａｒｅおよびＰ．Ｒｏｇａｗａｙの「Ｔｈｅ  ｅｘａｃｔ  ｓｅｃｕｒｉｔｙ  ｏｆ  ｄｉｇｉｔａｌ  ｓｉｇｎａｔｕｒｅｓ  −  Ｈｏｗ  ｔｏ  ｓｉｇｎ  ｗｉｔｈ  ＲＳＡ，  ａｎｄ  Ｒａｂｉｎ」）、および規格ＰＫＣＳ＃１  ｖ２．１、ＲＳＡ暗号化規格に詳細に記述されているＰＳＳ（確率的署名スキーム）関数である。
【００１０】
ＰＳＳ関数は、整数ｋ、ｋ０、ｋ１によりパラメータで表示され、２つのハッシング関数を使用する。
Ｈ：｛０，１｝ｋ−ｋ１  →  ｛０，１｝ｋ１
Ｇ：｛０，１｝ｋ１  →  ｛０，１｝ｋ−ｋ１
ｋ−ｋ０−ｋ１ビットの平文テキストｍおよびｋ０ビットの乱数ｒから、関数ＰＳＳは下式を生成する。
【００１１】
ＰＳＳ（ｍ，ｒ）＝ω｜｜ｓ
ここで、ｒは関数ＰＳＳに関連する乱数パラメータであり、｜｜は連結関数、ω＝Ｈ（ｍ｜｜ｒ）であり、
【００１２】
【数１】
2005534068.tif 000002
【００１３】
次に、メッセージｍの署名ｓが、秘密鍵（Ｎ，ｄ）による累乗により入手される。
Ｓ＝ｆ（［ＰＳＳ（ｍ．ｒ）］，Ｎ，ｄ）
＝［ＰＳＳ（ｍ，ｒ）］ｄ  ｍｏｄ  Ｎ
署名ｓは、以下を計算により確認することができる。
ｆ−１（ｓ）＝ｓｅ  ｍｏｄ  Ｎ＝ω｜｜ｓ
ここで、ｆ−１は指数関数ｆの逆関数である。
ωおよびｓ（それぞれｋ１ビットおよびｋ−ｋ１ビットである）のサイズを知っている場合には、ωおよびｓはｆ−１（ｓ）から演繹される。
【００１４】
【数２】
2005534068.tif 000003
およびＧから計算される。
【００１５】
【数３】
2005534068.tif 000004
【００１６】
であるので、Ｈ（ｍ｜｜ｒ）およびｍは最終的にはこれから演繹される。最終的に、ωとＨ（ｍ｜｜ｒ）の比較が行われる。Ｈ（ｍ｜｜ｒ）＝ωである場合には、平文テキストｍは返送され、そうでない場合には、エラー・メッセージだけが返送される。
【００１７】
同じように、関連する平文メッセージｍ１またはｍ２のうちの一方が分かっている場合でも、関数μから入手した２つの暗号化メッセージｃ１、ｃ２、および平文の２つのメッセージｍ１、ｍ２を区別することができない場合には、暗号化関数μは機密保護されているという。暗号化システムで使用する関数μは、このセキュリティ条件を満足するように構成される。
【非特許文献１】１９９６年Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ発行のＥｕｒｏｃｒｙｐｔ  ’９６議事録、ＬＮＣＳ  ｖｉｌ  １０７０、３９９〜４１６ページ掲載の、Ｍ．ＢｅｌｌａｒｅおよびＰ．Ｒｏｇａｗａｙの「Ｔｈｅ  ｅｘａｃｔ  ｓｅｃｕｒｉｔｙ  ｏｆ  ｄｉｇｉｔａｌ  ｓｉｇｎａｔｕｒｅｓ  −  Ｈｏｗ  ｔｏ  ｓｉｇｎ  ｗｉｔｈ  ＲＳＡ，  ａｎｄ  Ｒａｂｉｎ」という記事
【非特許文献２】１９９３年、ＡＣＭ、コンピュータ通信のセキュリティに関する第１回年次会議議事録記載の、Ｍ  ＢｅｌｌａｒｅおよびＰ  Ｒｏｇａｗａｙの「Ｒａｎｄｏｍ  ｏｒａｃｌｅｓ  ａｒｅ  ｐｒａｃｔｉｃａｌ：  ａ  ｐａｒａｄｉｇｍ  ｆｏｒ  ｄｅｓｉｇｎｉｎｇ  ｅｆｆｉｃｉｅｎｔ  ｐｒｏｔｏｃｏｌｓ」という記事
【発明の開示】
【発明が解決しようとする課題】
【００１８】
しかし、署名動作および暗号化動作に対するセキュリティ基準が同じでないために、署名関数μ’および暗号化関数μも同じではない。
それ故、暗号化および解読を行うことができる完全な暗号化システムを実施するために、２つの異なる関数、もっと一般的に言うと２つの異なるアルゴリズムを記憶するための手段が必要になるし、またこれらのアルゴリズムを実行するための異なるプログラムされた計算手段も必要になる。結果としての電子回路のサイズは、当然、記憶するアルゴリズムのサイズに比例する。
【課題を解決するための手段】
【００１９】
上記問題を解決するために、本発明の場合は、両方とも暗号化関数であり署名関数である１つの同じフォーマット関数を使用する。もっと正確に言うと、本発明の場合には、暗号化方法を実施するために、署名方法を実施するためのより周知なＰＳＳ関数を使用する。
【発明を実施するための最良の形態】
【００２０】
それ故、本発明は、フォーマット関数により平文メッセージをフォーマットするステップと、式ｃ＝μ（ｍ）ｅ  ｍｏｄ  Ｎに従って公開鍵により前のステップの結果を累乗するステップとを含む暗号化方法に関する。ここで、ｃは暗号化したメッセージであり、μ（ｍ）はフォーマット・ステップの結果であり、ｅおよびＮは、公開鍵の要素である。
【００２１】
本発明の場合、フォーマット関数は、ＰＳＳ関数である。
ＰＳＳ関数は、暗号化動作のためのセキュア関数である。それは文書Ｄ２（１９９３年、ＡＣＭ、コンピュータ通信のセキュリティに関する第１回年次会議議事録記載の、Ｍ  ＢｅｌｌａｒｅおよびＰ  Ｒｏｇａｗａｙの「Ｒａｎｄｏｍ  ｏｒａｃｌｅｓ  ａｒｅ  ｐｒａｃｔｉｃａｌ：  ａ  ｐａｒａｄｉｇｍ  ｆｏｒ  ｄｅｓｉｇｎｉｎｇ  ｅｆｆｉｃｉｅｎｔ  ｐｒｏｔｏｃｏｌｓ」）、さらに、現在の暗号化の分野における、ランダム・オラクル・モデルでのセキュリティのコンセプトおよびリアル・アプリケーションのための最高のセキュリティのコンセプト内に定義されている、ランダム・オラクル・モデルでの暗号化動作に対してＰＳＳ関数が機密保護になっているからである。
それ故、本発明の場合には、署名および暗号化動作の両方に対してセキュア関数を使用することができる。
【００２２】
本発明は、また、両方ともフォーマット関数としてＰＳＳ関数を使用する暗号化方法および署名方法を含む暗号化システムに関する。
もっと正確に言うと、暗号化システムは、下記のステップを含む。
・確率的署名関数（ＰＳＳ）により平文メッセージをフォーマットするステップ、
・平文メッセージの暗号化が必要な場合には、式ｃ＝μ（ｍ）ｅ  ｍｏｄ  Ｎに従って第１の鍵によりフォーマット・ステップの結果を累乗するステップであって、ｃが暗号化したメッセージであり、μ（ｍ）がフォーマット・ステップの結果であり、ｅおよびＮが第１の鍵の要素であるステップ、または
・平文メッセージに署名する必要がある場合には、式ｓ＝μ（ｍ）ｄ’  ｍｏｄ  Ｎ’に従って第２の鍵（Ｎ’，ｄ’）によりフォーマット・ステップの結果を累乗するステップであって、ｓが署名したメッセージであり、μ（ｍ）がフォーマット・ステップの結果であり、ｄ’およびＮ’が第２の鍵の要素であるステップ。
【００２３】
このような暗号化システムは、従来の暗号化システムより有利である。何故なら、実施するのに約半分の手段（プログラムした計算手段および特にメモリ空間の点で）ですむからである。
一実施形態の場合には、第１の鍵および第２の鍵は、それぞれ第１の鍵のペアの公開鍵であり、第２の鍵のペアの秘密鍵である。
【００２４】
他の好ましい実施形態の場合には、第１の鍵のペアおよび第２の鍵のペアは同じものである。すなわち、暗号化方法および署名方法の両方を実施するのに同じ組の鍵を使用している。ＰＳＳ関数および所与の組の鍵を使用する暗号化方法により暗号化したメッセージを解読しても、ＰＳＳ関数および同じ組の鍵を使用する署名方法によりメッセージ（おそらく解読メッセージ）に署名するための十分な情報を入手することはできないことが分かっている。同様に、ＰＳＳ関数および所与の組の鍵を使用する署名方法により、署名した方法の署名についての情報を入手しても、同じＰＳＳ関数および同じ組の鍵を使用する暗号化方法により暗号化した平文メッセージについての情報を入手することができないことが分かっている。
【００２５】
本発明は、暗号化の分野で現在最も広く使用されているアルゴリズムである、ＲＳＡ暗号化アルゴリズムに特に適している。
本発明は、また、フォーマット関数としてＰＳＳ関数を使用する、上記暗号化方法を実施するようにプログラムされている手段を備える電子構成要素に関する。上記のプログラムされた手段は、特に中央処理装置（ｃｅｎｔｒａｌ  ｕｎｉｔ）およびプログラム・メモリを備える。
【００２６】
本発明は、また、交互に実行される暗号化動作または署名動作を含む、上記暗号化システムを実施するためのプログラムされた手段を備える電子構成要素に関する。このプログラムされた手段は、特に中央処理装置およびプログラム・メモリを備える。
本発明は、使用する構成要素ができるだけ小さくなければならないし、上記方法をできるだけ速く実施しなければならないチップ・カード・タイプに使用した場合特に有利である。
【国際調査報告】
2005534068.tif 000006
2005534068.tif 000007
2005534068.tif 000008
2005534068.tif 000009