(57)【要約】本発明は、暗号ユニットを開発し、製造し、かつ維持するコストを減らす目的で、離散的な対数問題を用いる公開鍵暗号スキーマ（schemas）のグループに関する。実体（１０）のうちの１つは、多くて、整数の少数の加算、減算および乗算を含むだけの計算を実行する。前記計算は、グループのスキーマの全てに共通である。前記の計算は、好ましくは、問題の実体によって実行されるべき主な計算である。一方、他の計算の大部分は、あらかじめ実行しておくことができる。詳細には、前記計算は、ｙ＝ａｒ＋ｂｓ型である。ここで、ｒは乱数であり、かつｓは実体（１０）に特有の秘密鍵である。この計算は、実体認証、メッセージ認証、デジタル署名および鍵交換のためのスキーマのグループに共通である。
2005500743.tif 000002
【特許請求の範囲】
【請求項１】
非対称暗号システムにおける整数の秘密鍵ｓと関連付けられた暗号ユニットを製造する方法において、前記暗号ユニットは、前記暗号システムとは無関係に製造され、かつ、いくつかの整数のオペランドの結合によって整数ｙを出力するのに適合したコンポーネント（１５）を備えていて、前記いくつかの整数のオペランドは、乱数ｒ、秘密鍵ｓおよび少なくとも１つの更なるオペランド（ａ，ｂ）を含んでいて、乗算演算を備えた集合Ｇの第１の要素ｇを含む公開鍵を、前記秘密鍵ｓと関連付けることによって、前記暗号システムを選択した後に、前記暗号ユニットは、暗号データ組の発生器（１３）を備えていて、前記暗号データ組の各々は、オペランドとして前記コンポーネントに送られる乱数ｒと、前記集合Ｇの要素ｇｒによって決まり、かつ整数ｙに関連して前記ユニットによって出力される値ｘとを含んでいることを特徴とする方法。
【請求項２】
前記公開鍵は、ｖ＝ｇｓまたはｖ＝ｇ−ｓであるような集合Ｇの第２の要素ｖを含んでいることを特徴とする請求項１に記載の方法。
【請求項３】
前記暗号データ組の発生器は、あらかじめ計算されたペア｛ｒ，ｘ｝または｛ｒ，ｇｒ｝を受け取るプログラマブルメモリ（１３）を有していることを特徴とする請求項１または２に記載の方法。
【請求項４】
前記コンポーネント（１５）によって実行される結合がｙ＝ａｒ＋ｂｓ形式であり、ａおよびｂは２つの更なるオペランドであることを特徴とする請求項１から３のうちのいずれか一項に記載の方法。
【請求項５】
前記更なるオペランドａおよびｂは、確認ユニットから受け取られ、この確認ユニットには、前記値ｘおよび整数ｙが送られることを特徴とする請求項４に記載の方法。
【請求項６】
前記更なるオペランドのうちの一方（ａ）は、１に等しいことを特徴とする請求項４に記載の方法。
【請求項７】
前記乗算演算を備えた集合Ｇは、グループ構造を有していることを特徴とする請求項６に記載の方法。
【請求項８】
前記コンポーネント（１５）は、前記更なるオペランドのうちの他方（ｂ）が確認ユニットから受け取られ、この確認ユニットには前記値ｘおよび整数ｙが送られるように配置され、かつ、要素ｇｒの関数として前記値ｘを得るステップでは、ハッシュ関数を適用することを特徴とする請求項７に記載の方法。
【請求項９】
メッセージ認証プロトコルを実現する暗号ユニットの製造のための方法において、前記コンポーネント（１５）は、前記更なるオペランドのうちの他方（ｂ）が確認ユニットから受け取られ、この確認ユニットには前記値ｘおよび整数ｙが送られるように配置され、かつ、前記値ｘは、前記暗号ユニットを組み込んでいる装置によって認証されるべきメッセージ（Ｍ）の要素ｇｒおよびコンテンツの関数であることを特徴とする請求項７または８に記載の方法。
【請求項１０】
デジタルメッセージ署名プロトコルを実現する暗号ユニットの製造のための方法において、前記更なるオペランドｂは、前記値ｘの関数として計算され、かつ、前記値ｘは、前記暗号ユニットを組み込んでいる装置によって認証されるべきメッセージ（Ｍ）の要素ｇｒおよびコンテンツの関数であることを特徴とする請求項７から９のうちのいずれか一項に記載の方法。
【請求項１１】
鍵交換プロトコルを実現する暗号ユニットの製造のための方法において、前記暗号ユニットは、別の暗号ユニットとの通信の手段を備えていて、前記別の暗号ユニットには、前記値ｘおよび整数ｙが送られ、前記他の暗号ユニットは、別の整数の秘密鍵ｓ’と関連付けられていて、かつ、前記暗号システムを選択するステップは、ｖ’＝ｇｓ’であるような集合Ｇの要素ｇおよび別の要素ｖ’から成る公開鍵を、前記秘密鍵ｓ’と関連付けるステップを含んでいて、前記発生器（１３）によって生成される各暗号データ組は、前記乱数ｒおよび前記値ｘに加えて、集合Ｇの要素ｖ’ｒによって決まる共通鍵Ｋを含んでいて、これは前記他の暗号ユニットに送られないことを特徴とする請求項１から１０のうちのいずれか一項に記載の方法。
【請求項１２】
前記暗号データ組の発生器は、あらかじめ計算された三つ組み｛ｒ，ｘ，Ｋ｝または｛ｒ，ｇｒ，ｖ’ｒ｝を受け取るプログラマブルメモリ（１３）を有していることを特徴とする請求項１１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号の技術分野に関し、より正確には、いわゆる非対称または公開（public）鍵暗号に関する。
【背景技術】
【０００２】
この種の暗号において、各ユーザは、所定の使用のために、秘密鍵および関連付けられた公開鍵から成る鍵のペア（pair）を持つ。
【０００３】
例えば、機密保持専用の鍵のペアを取り扱う場合には、公開鍵は、データを暗号化するために用いられ、一方、秘密鍵は、それらを解読するため、すなわち、これらのデータを判読するために用いられる。データの信憑性専用の鍵のペアを取り扱う場合には、秘密鍵は、デジタル的にデータに署名するために用いられ、一方、公開鍵は、このデジタル署名を確認するために用いられる。他の用途（実体（entity）の認証、鍵の交換等）も可能である。
【０００４】
秘密鍵暗号と違って、安全な通信をセットアップするために、秘密を共有することを伴うパーティ（parties）を必要としないという点では、公開鍵暗号は非常に有効である。しかし、安全に関するこの利点には、性能に関して不利な点が付いてくる。なぜなら、公開鍵暗号方法（「公開鍵方式（schemes）」とも呼ばれる）は、等しい資源に対して、いわゆる秘密鍵暗号方法（「秘密鍵方式」とも呼ばれる）より、しばしば１００または１，０００倍遅い。その結果、妥当な計算時間を得るためには、これらのアルゴリズムを実現する回路のコストは、しばしば非常に高くなる。
【０００５】
これは、特に、いわゆるＲＳＡデジタル暗号化および署名方式(R.L. Rivest, A. Shamir and L.M. Adleman, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems", Communications of the ACM, Vol.21, No.2, pp.120-126, １９７８年２月参照）にあてはまる。この方式は、整数の因数分解の問題の困難さに依存する。すなわち、相当する大きさの２つ以上の素因数の積に等しい（一般に２進数で表すと１，０００ビットを超える）大きい整数が与えられた場合に、これらの素因数を取り戻すための効率的な手順が存在しない。それゆえに、この方式において実行される計算は、非常に大きい数に関するものとなる。それらは、かなりそのコストを増やす専用の暗号コプロセッサを付けていない限り、チップカード上で、１秒未満で実行することはできない。さらに、時と共に、因数分解の手順の効率が、かなり急速に良くなりつつあるので、実行を阻むためには、鍵の長さを、長い方へ、たびたび修正しなければならない。
【０００６】
それゆえに、公開鍵方式を実現するチップのコストを減らすという問題が生じている。
【０００７】
この質問に取り組むために、主に２つの方法がある。第１の方法は、かなり計算時間の速度を上げることを可能にする、好ましくは（しかし必ずではない）因数分解以外の問題に基づく、新しい暗号方式を指定することである。この方法は、大いに調査され、非常に多くの成果が得られた。しかし、大多数の場合において、その改良は、ＲＳＡと比較して、置き換えを考えるほどではないか、または安全が十分に確立されていなかった。
【０００８】
第２の方法は、それらのコストが大きい割合で減少するような量のチップを製造することである。これは、将来のチップベースの銀行カードのために、国際銀行業務団体（the international banking organizations）が、ＲＳＡ方式の選択を正式に認めれば、多分ＲＳＡにも起こることである。しかし、ＲＳＡチップのコストは、初めから高いので、たとえどれほどの数のチップが製造されても、コストは常にそれ相当なままであろう。
【発明の開示】
【発明が解決しようとする課題】
【０００９】
多くの公開鍵暗号方式は、基本的な演算として整数上での演算を共通に使用することは分かるであろう。例えばモジュール（modular）乗算（ａｂ（モジュロｎ））、モジュール除算（ａ／ｂ（モジュロｎ））、またはモジュール累乗（ａｂ（モジュロｎ））である。ここでａ，ｂおよびｎは整数である。しかし、これらの演算は、決して正確に同じものではない。その結果として、暗号方式が修正されるたびに、暗号計算を実行する安全装置のプログラムまたは回路を変えることが必要になる。
【課題を解決するための手段】
【００１０】
本発明の目的は、上記の２つの方法を組み合わせることによって、公開鍵暗号ユニットのコストを減少させることである。
【００１１】
従って、本発明は、非対称暗号システムにおける整数の秘密鍵ｓと関連付けられた暗号ユニットを製造する（producing）方法を提案する。この暗号ユニットは、暗号システムとは無関係に製造され、かつ、いくつかの整数オペランド（operands）の結合（combination）によって整数ｙを出力するのに適合したコンポーネント（component）を備えていて、前記いくつかの整数オペランドは、乱数ｒ、秘密鍵ｓおよび少なくとも１つの更なるオペランド（ａ，ｂ）を含んでいる。乗算演算を備えた集合Ｇの第１の要素ｇを含む公開鍵を、前記秘密鍵ｓと関連付けることによって、前記暗号システムを選択した後に、前記暗号ユニットは、暗号データ組（suites）の発生器を備えていて、前記暗号データ組の各々は、オペランドとして前記コンポーネントに送られる乱数ｒと、前記集合Ｇの要素ｇｒによって決まり、かつ整数ｙに関連して前記ユニットによって出力される値ｘとを含んでいる。
【００１２】
一つ以上の回路部分または一つ以上のソフトウェアモジュールから成るコンポーネントは、非常に高速で実行される基本的な暗号項目を適用する。それは、好都合にも、多数の異なる暗号方式、すなわち多様な数学的オブジェクト（集合Ｇおよびいろいろな離散的な（discrete）対数関数を定義することを可能にする乗算演算）を用いる、認証、署名、鍵交換方式等に共通であってもよい。
【００１３】
このコンポーネントが多数の方式に共通であるということは、産業上の開発および製造コストのよりよい償却（amortization）を可能にする。これらのユニットが、関連したファミリー（family）の全ての方式に適合していて、このようなアプリケーションによって要求される動作を成し遂げることが、通常、可能であれば、このコンポーネントが取り付けられた一般的なユニット（例えばチップカード）は、好都合にも、非常に大量に生産することができる。
【００１４】
より詳細には、公開鍵は、更に、ｖ＝ｇｓまたはｖ＝ｇ−ｓであるような集合Ｇの要素ｖを含んでいる。この方法は、一般化された離散的な対数問題に基づいて、方式の全てのファミリーを適用することが可能な暗号ユニットを生じさせる。この問題は、概略、次のように述べることができる。Ｇを乗算演算（すなわち、２つの要素ａおよびｂを有していて、“ａ．ｂ”または単に“ａｂ”と表記される要素を、ａとｂの積と呼ぶように関連付ける関数）を備えた集合とし、ｇをＧの要素とし、ｕを（大きい）整数とし、ｗをｗ＝ｇｕ（すなわちｇがｕ個存在する積ｇｇ．．．ｇ）によって定義されるＧの要素とする。この時、ｇおよびｗからｕを取り戻すことは、実際問題として不可能である。
【００１５】
ヨーロッパ特許Ｎｏ．０  ６６６  ６６４には、このタイプの具体例としての電子署名方式が記載されていて、この中で、Ｇは、少なくとも０に等しい整数とｎより小さい整数の集合であり、かつ乗算演算は、整数の普通の積、モジュロｎである。
【００１６】
本発明の方法によれば、所定の集合Ｇおよび一定の乗算演算のために、以前に知られていたものより非常に効率的な離散的な対数計算アルゴリズムが発見されれば、計算が実行され、かつ／または所望の安全レベルを取り戻すための乗算演算が実行される集合を変えることで十分である。
【００１７】
離散的な対数問題（problem）は、演算を備えた任意の集合において、事前に決めておくことができる。しかし、それに対して、短い時間内で指数関数（exponential）の計算を実行し、かつ小さなサイズ（small size）の結果を提供することを可能にするためには、現在、最も適切な集合がグループであるようにするという一定の特性（properties）が必要である。１つのグループは、他の特性の中に、常に、中立の要素、すなわちε（または単に１）と表記される要素を含んでいる。任意の要素ａについて、積ε．ａおよびａ．εは、両方ともａに等しい。さらに、全ての要素ａは、グループの中に、ａ−１と表記される逆数、すなわち積ａ−１．ａおよびａ．ａ−１が両方ともεに等しい要素を持っている。暗号において用いられるグループの典型的な例は、整数かつ楕円曲線のリングまたはフィールド（rings or fields of integers and elliptic curves）である。
【００１８】
従って、どんな形であれ関連するグループに依らず、より一般的には考慮中の集合Ｇに依らない暗号コンポーネントを定義することが可能である。これは、第一に、このコンポーネントが、集合自体の要素に作用しないことを意味する。また、これは、それが、グループの特性または考慮中の要素ｇ、特にＧにおけるｇのオーダー（order）、すなわち（もしそれが存在するのであれば）ｇｑ＝εを満たす最も小さいゼロではない整数ｑに依らないことを意味する。
【００１９】
本発明の好適な実施形態においては、コンポーネントによって遂行される結合は、少数の整数間の加算、減算および乗算のみから成り、それらのうちのいずれも、Ｇおよびｇの特性と関係ない。特に、この結合をｙ＝ａｒ＋ｂｓ形式とすることができる。ここで、ａおよびｂは、２つの更なる整数オペランドである。更に簡略化するには、ａ＝１またはｂ＝１とする。
【００２０】
このようなコンポーネントのこの選択の利点は、その速度である。実行されるべき乗算が、わずかな数（１つまたは２つ）しかなければ、コンポーネントは、高速（２、３ミリ秒）になるであろうし、いかなる環境にも、特に低コストのマイクロプロセッサカードにも組み込むことができる。
【００２１】
暗号データ組の発生器は、集合Ｇ上での指数関数を計算するためのモジュールを有する乱数発生器と関連させることによって、つくることができる。
【００２２】
しかし、この方法の好ましい実施形態においては、暗号データ組の発生器は、あらかじめ計算したペア｛ｒ，ｘ｝または｛ｒ，ｇｒ｝を受け取るプログラマブルメモリを備えている。このように、暗号ユニットは、完全に、集合Ｇおよび採用される乗算演算とは無関係に製造することができる。あとは、単に、プログラマブルメモリに、あらかじめ計算した、秘密鍵ｓおよび一定の数のペア｛ｒ，ｘ｝または｛ｒ，ｇｒ｝を書くことが残るだけである。動作中に、共通のコンポーネントは、暗号ユニットのレベルにおいて要求される唯一の計算を実行する。
【００２３】
ユニットを自律的に（autonomously）用いることができることは、開発および製造コストの償却を更に改善することを可能にする。なぜなら、（回路の同じ部分というよりはむしろ）同じ回路を、さまざまなターゲットアプリケーションで用いることができるからである。さらに、コンポーネントが実行中に非常に高速ということは、それを非常に低コストの回路に取り付けることを可能にし、従って、自律（autonomous）モードの、非常に安いユニット、例えば接点（contacts）の有無に依らない通常のマイクロプロセッサカードに取り付けることを可能にする。
【００２４】
この自律性（autonomy）の更なる利点は、例えば、暗号方式が破られたという理由（すなわち、攻撃が発見されて、それが提供していた安全のレベルがかなり下がったという理由）で、暗号方式を変えることができるという可能性である。このとき、別の回路を開発して製造する必要はなく、結果として、生産性が節約される。
【００２５】
さらに、（例えば、ｇｒからのその計算が、予め定義されたハッシュ関数を含んでいるという理由で）、ユニットが、長さが時間軸上で変化することを意図していない値ｘを用いても、同じ方式を維持しながら、用いられる他の鍵の長さを変えることが可能である。このとき、別の回路を開発して製造する必要はない。
【００２６】
さらに、最後の２つの状況において、別の回路を開発して製造する理由がないばかりでなく、回路が適切に設計されていれば、これらの装置が配備された後で、それらを含んでいる安全装置（例えばチップカード）を変える理由さえもない。この利点は、非常に重要である。なぜなら、すでに流通された安全装置内の回路または回路のプログラム（または安全装置自体）の変更は、実施するには、常に、非常に高価であるからである。
【００２７】
本発明は、暗号ユニットの置き換えが、高い開発、製造、管理または維持費を招く、安全チップを製造している半導体製造業者、これらのチップから安全装置を組み立てている産業、例えばチップ組み込み業者（embedders）（接点の有無に依らないチップカード）、および、このような装置を配備している団体（organizations）（銀行、遠距離通信、トラック運送業者等）によって、都合よく用いられることができる。
【００２８】
要約すると、本発明は、離散的な対数問題を用いて公開鍵暗号方式のファミリーを生じさせる。この中で、実体のうちの１つは、多くて、整数の少数の加算、減算および乗算から成る計算を実行するだけである。この計算は、このファミリーの全ての方式に共通である。この計算は、好ましくは、この実体によって実行されるべき大部分の計算を示す。なぜなら、他の計算の大部分は、あらかじめ実行しておくことができるからである。
【発明を実施するための最良の形態】
【００２９】
他の本発明の特徴および効果は、添付の図面を参照する、本発明を限定するわけではない具体例としての実施形態の以下の説明において明らかになる。図１から４は、本発明によって製造される暗号ユニットの概要図である。
【００３０】
全て共通のコンポーネントを実現している、メッセージの認証およびメッセージのデジタル署名への拡張が可能な実体認証プロトコル、および鍵を交換するためのプロトコルのファミリーを、以下で考察する。別の実体Ｂによって用いられる実体Ａの公開鍵の信憑性は、あらかじめこの実体Ｂによって確認されたものとする。
【００３１】
Ｇを、乗算演算を備えた集合とし、ｇをＧの要素とする。実体Ａの秘密鍵は、整数ｓである。この整数ｓのサイズ（２進数に分解したときのビット数）は、Ｇおよびｇとは無関係であることに留意する必要がある。実体Ａのためのｓと関連付けられた公開鍵は、ペア｛ｇ，ｖ｝である。ここで、ｖ＝ｇｓである。
【００３２】
本発明の具体例としての一実施形態において、実体Ｂによる実体Ａの認証は、次のように行われる。
1. Ａは、ランダムに整数ｒを選び、ｘ＝ｇｒを計算し、かつｘをＢに送る。
2. Ｂは、ランダムに２つの整数オペランドａおよびｂを選び、かつそれらをＡに送る。
3. Ａは、ｙ＝ａｒ＋ｂｓを計算し、かつｙをＢに送る。
4. Ｂは、ｇｙ＝ｘａｖｂであることを確認する。
【００３３】
メッセージ認証およびデジタルメッセージ署名に適合するような、この基本的なプロトコルの多くの変形が可能である。
- ａまたはｂをあらかじめゼロ以外の値に固定することができ（例えばａ＝１）、その場合には、このオペランドは送信される必要がなく、かつ結合ｙ＝ａｒ＋ｂｓは、ただ１つの乗算だけを含んでいる。
- ｙ＝ａｒ＋ｂｓをｙ＝ａｒ−ｂｓによって置き換えることができ、確認の式はｇｙｖｂ＝ｘａによる。
- ｙ＝ａｒ＋ｂｓをｙ＝ｂｓ−ａｒによって置き換えることができ、確認の式はｇｙｖａ＝ｖｂによる。
- ｙ＝ａｒ＋ｂｓをｙ＝−ａｒ−ｂｓによって置き換えることができ、確認の式はｇｙｘａｖｂ＝１による。
- Ｇが１つのグループである場合、秘密鍵ｓの符号を逆にすることができ、すなわち、ｖ＝ｇ−ｓ＝（ｇｓ）−１をとることができ、その場合には、確認の式はｇｙｖｂ＝ｘａになる。この選択は、もちろん、上記の変形例のうちの任意の一つと組み合わせることができる。
- 確認の式がｇｙｖｂ＝ｘ形式であるところの各場合において、ａ＝１と仮定すると、ｘ＝ｇｒは、ｘ＝ｆ（ｇｒ）によって置き換えることができる。ここでｆは１つの関数、例えば暗号ハッシュ関数と等しいもの（またはこれを含んでいるもの）である。その時、確認の式はｆ（ｇｙｖｂ）＝ｘになる。
- 再び、確認の式がｇｙｖｂ＝ｘ形式であるところの各場合において、ａ＝１と仮定すると、ＭがＡによって認証されるべきメッセージである場合、ｘ＝ｇｒは、ｘ＝ｆ（ｇｒ，Ｍ）によって置き換えることができる。ここで、ｆは１つの関数、例えば暗号ハッシュ関数と等しいもの（またはこれを含んでいるもの）である。その時、確認の式はｆ（ｇｙｖｂ，Ｍ）＝ｘになる。得られるプロトコルは、メッセージ認証プロトコルである。
- 再び、確認の式がｇｙｖｂ＝ｘ形式であるところの各場合において、ａ＝１と仮定すると、ＭがＡによって認証されるべきメッセージである場合、ｘ＝ｇｒは、ｘ＝ｆ（ｇｒ，Ｍ）によって置き換えることができる。ここで、ｆは１つの関数、例えば暗号ハッシュ関数と等しいもの（またはこれを含んでいるもの）である。それから、ｂ＝ｈ（ｘ）を計算し、ここで、ｈは特別な暗号特性のない関数、例えばアイデンティティ（identity）であり、この場合、ステップ２（step 2）は、もはや実体Ａを含んでいない。確認の式はｆ（ｇｙｖｈ（Ｘ），Ｍ）＝ｘになる。得られるプロトコルは、デジタルメッセージ署名プロトコルである。（Ｇがｎ未満の負ではない整数の集合であって、かつ演算が乗算モジュロｎ（multiplication modulo n）である特別な場合においては、ヨーロッパ特許０  ６６６  ６６４に記載されている電子署名方式が得られる。）
【００３４】
ステップ３（step 3）において、実体Ａは、実行すべき、整数の、１つの加算および１つまたは２つの乗算のみを有していることが分かる。また、この結合は、選択された集合Ｇとは無関係であることが分かる。最後に、Ａが実行しなければならない他の計算（ｘ＝ｇｒまたはｆ（ｇｒ））は、あらかじめされていてもよいことが分かる。従って、あらかじめ、一定の数のｇｒの値を計算することが可能である。（これに対して、関数ｆが適用されるか、またはされない。）そして、それらを、対応する乱数ｒに関連するプログラマブルメモリに格納することが可能である。
【００３５】
同じパラメータで、秘密鍵ｓ’および関連付けられた公開鍵ｇ’で補われ、実体Ｂのためのｖ’が、実体Ａのためと同じルールに従って、ｇ’＝ｇとすることによって得られる。すなわち、ｖ’＝ｇｓ’である。鍵交換プロトコルは、次のように定義することができる。
1. Ａは、ランダムに整数ｒを選び、ｘ＝ｇｒを計算し、かつｘをＢに送る。Ａは、共通鍵Ｋ＝ｖ’ｒ（＝ｇｓ’ｒ）を計算する。
2. Ｂは、ランダムに２つの整数オペランドａおよびｂを選び、かつそれらをＡに送る。
3. Ａは、ｙ＝ａｒ＋ｂｓを計算し、かつｙをＢに送る。
4. Ｂは、ｇｙ＝ｘａｖｂであることを確認する。Ｂは、共通鍵Ｋ＝ｘｓ’（＝ｇｒｓ’）を計算する。
【００３６】
このプロトコルは、一方で、鍵がＤｉｆｆｉｅ−Ｈｅｌｌｍａｎ方式に従って交換されることを可能にし、他方で、この鍵交換が、両方の側で認証されることを可能にする。また、共通鍵Ｋは、ｖ’ｒのあらかじめ決められた関数として計算することができる。
【００３７】
再び、ステップ３において、実体Ａは、実行すべき、整数の、１つの加算および１つまたは２つの乗算のみを有していることが分かる。また、この結合は、選ばれた集合Ｇとは無関係であることが分かる。最後に、実体Ａが実行しなければならない他の計算は、あらかじめされていてもよいことが分かる。それゆえに、あらかじめ一定の数のｘおよびＫの値を計算して、それらをプログラマブルメモリに格納することが可能である。
【００３８】
従って、唯一の関数ｙ＝ａｒ＋ｂｓ（または上述した選択肢のうちの一つ）を実現するプログラムまたは回路を開発することによって、基本的なソフトウェアまたはハードウェアブリック（brick）が得られ、それを、異なる役割、例えば認証、鍵交換等を成し遂げる異なる暗号方式において用いることができる。所定の役割を成し遂げる方式は、このプログラムまたはこの回路を含んでいる安全装置の寿命の間に、修正することもできる。例えば、認証方式を他のものによって置き換えることが可能である。また、同じものを保って、計算が実行される集合またはグループＧを修正することも可能である。これらの修正は、あらかじめ計算された値にのみ影響し、コンポーネント自体には影響しない。
【００３９】
図１に、本発明に従って製造された具体例としての暗号ユニットＡを概略的に示す。このユニットは、部分１０を有するチップから成り、この部分１０へのアクセスは、当業者にとって周知の技術によって保護されている。
【００４０】
この保護されている部分１０は、一方では、ユニットＡの秘密鍵ｓ（領域１２）を、そして他方では、ひとたび集合Ｇおよびその乗算演算が定義されたならば、ｓとは無関係に決められるペア｛ｒ，ｇｒ｝（領域１３）を受け取ることを目的とするプログラマブルメモリ１１を有している。保護されている部分１０は、さらに、メモリ領域１３から受け取るランダムな整数ｒ、メモリ領域１２から受け取る秘密鍵ｓ、および制御モジュール１６から送り出される２つの更なるオペランドａ，ｂの関数として、整数ｙ＝ａｒ＋ｂｓを計算するコンポーネント１５を備えている。
【００４１】
いくつかのペア｛ｒ，ｇｒ｝を領域１３に格納するさまざまな方法が可能である。
ｒの各値およびｇｒの各値は、例えば、同じペアにおけるｒの値とｇｒの値との間で関連するものを突き合わせてテーブルの中に詳細に（in extenso）格納することができる。有益にも、限られたメモリサイズしかない超小型回路においては、メモリ空間を節約するために、単純なインデックスがｇｒの各値と関連付けられる。メモリ空間は、一般に大きなｒのいくつかの値を格納するために必要である。このインデックスに対するｇｒの値を予め計算して格納するために、ｒのさまざまな値が、疑似乱数発生器によってシード値ｒ０および対応するインデックスから予め計算される。プログラマブルメモリ１１は、疑似乱数発生器および最初のうちはシード値ｒ０を有していて、疑似乱数発生器を起動させることによって、対応するインデックスからｒの各値を受け取る。このとき、インデックスのおかげで、ｒの各値をｇｒの値と合わせるために詳細にｒの各値を記憶する必要はない。
【００４２】
遠く離れた実体Ｂから発せられる認証要求に応じて、制御モジュール１６は、メモリ領域１３に、整数ｒ、および実体Ｂに送られる値ｘを構成するかもしれない関連付けられた集合Ｇの要素ｇｒをコンポーネント１５に出力するよう命令する。実体Ｂから受け取った更なるオペランドａ，ｂが、制御モジュール１６によって、さらにコンポーネント１５に渡され、そして、コンポーネントによって返される整数ｙが、制御モジュール１６によって、実体Ｂに伝達される。そして、公開鍵ｇ，ｖを知っている実体Ｂは、確認式ｇｙ＝ｘａｖｂを用いて、Ａを認証することが可能になる。
【００４３】
図２における変形例において、ユニットＡは、メッセージＭの認証のための要求に応える。保護されている部分１０および制御モジュール１６は、本質的に図１の例と同じであり、ａ＝１に固定されている。保護されている領域１０には、あらかじめ決められた暗号ハッシュ関数ｆを適用するハッシュモジュール１８が追加されている。この関数ｆの引数は、メモリ領域１３から来る要素ｇｒおよび制御モジュール１６から提供される認証されるべきメッセージＭである。結果ｘは、制御モジュール１６に送られ、この制御モジュール１６は、それを実体Ｂに伝達する。
【００４４】
ハッシュモジュール１８は、集合Ｇとは無関係に指定されるサイズを有する鍵の値ｘを生成するために、引数Ｍなしで（またはこの引数のデフォルト値と共に）、図１の実施形態の中にあってもよい。
【００４５】
それゆえに、同じ回路が両方のアプリケーションに適していることが分かる。
【００４６】
同じものが、図３のユニットのためにも保たれていて、それは、メッセージＭの署名のための要求に応える。すなわち、ひょっとすると、この署名を調べることができるかもしれない実体とは無関係である。ハッシュモジュール１８から出力される結果ｘが整数の形をとる場合、それはコンポーネント１５にオペランドｂとして提供することができる。前述したように、それに対して事前に関数ｈを適用することも可能である。
【００４７】
図４の実施形態において、メモリ領域１３は、更に、実体Ｂの公開鍵ｇ，ｖ’の関数として決められる秘密セッション鍵Ｋを、各乱数ｒと関連付ける。（それゆえに、それは、あらかじめ知られていなければならない。）すなわち、Ｋ＝ｖ’ｒである。このセッション鍵Ｋは、対称暗号アルゴリズムに従って、従来の方法で動作している秘密鍵暗号ユニット２０に送られ、実体Ｂとの通信に用いられる。秘密鍵暗号ユニット２０は、確認式ｇｙ＝ｘａｖｂまたは前述したその変形例のうちの１つを用いて、秘密鍵Ｋの整合性（integrity）を確かめる。
【図面の簡単な説明】
【００４８】
【図１】本発明によって製造される暗号ユニットの概要図である。
【図２】本発明によって製造される暗号ユニットの概要図である。
【図３】本発明によって製造される暗号ユニットの概要図である。
【図４】本発明によって製造される暗号ユニットの概要図である。
【符号の説明】
【００４９】
１０  保護されている部分
１１  プログラマブルメモリ
１２  メモリ領域
１３  メモリ領域
１５  コンポーネント
１６  制御モジュール
【図１】
2005500743.tif 000003
【図２】
2005500743.tif 000004
【図３】
2005500743.tif 000005
【図４】
2005500743.tif 000006
【国際公開パンフレット】
2005500743.tif 000007
2005500743.tif 000008
2005500743.tif 000009
2005500743.tif 000010
2005500743.tif 000011
2005500743.tif 000012
2005500743.tif 000013
2005500743.tif 000014
2005500743.tif 000015
2005500743.tif 000016
2005500743.tif 000017
2005500743.tif 000018
2005500743.tif 000019
2005500743.tif 000020
2005500743.tif 000021
2005500743.tif 000022
2005500743.tif 000023
2005500743.tif 000024
【国際調査報告】
2005500743.tif 000025
2005500743.tif 000026
2005500743.tif 000027
2005500743.tif 000028
2005500743.tif 000029
2005500743.tif 000030