(57)【特許請求の範囲】
【請求項１】
ネットワーク内の通信を保護するように第１のノードと第２のノードとの間の共有鍵を生成する方法において、前記第１のノードが、ルート鍵材料に基づく第１のノード鍵材料共有を記憶し、前記方法は、
ａ）前記第１のノードが、前記第２のノードの識別子を受信するステップと、
ｂ）前記第１のノードが、前記共有鍵を生成するように、前記第２のノードの識別子において前記第１のノード鍵材料共有を評価するステップと、
を有し、前記第１のノード鍵材料共有が、有限フィールドFq上の多項式ベースの鍵材料であり、前記ステップｂ）が、
ｂ１）前記第１のノードが、Fqのサブフィールド内の係数を持つ次数rの既約多項式を法として前記フィールドFq上の被約多項式の形で前記第１のノード鍵材料を因数分解するステップであって、前記被約多項式は、前記第２のノードの識別子において前記第１のノード鍵材料を評価することが、前記既約多項式を法として、前記フィールドFq上の、例えば前記第２のノードの識別子における、単項式を反復的に評価及び結合することを含む、当該因数分解するステップと、
ｂ２）前記第１のノードが、Fqのサブフィールド内の次数rの前記既約多項式を法としてFqのサブフィールド内の係数を持つ次数r-1の多項式を所定の点において評価することにより各単項式演算の結果を計算するステップであって、前記係数多項式は、前記係数多項式を評価することが、前記既約多項式を法としてFqのサブフィールド上の前記所定の点における単項式を反復的に評価及び結合することに相当するように構成される、当該計算するステップと、
を有する、方法。
【請求項２】
qが素数の累乗prであり、pが素数である、請求項１に記載の方法。
【請求項３】
Fqの前記サブフィールドが、pを法として全ての整数のセットに対応するサブフィールドZpである、請求項２に記載の方法。
【請求項４】
前記ステップｂ１）の因数分解が、ホーナー法の使用に相当する、請求項１に記載の方法。
【請求項５】
前記既約多項式の次数rの係数及び低次の係数のみが、ゼロとは異なる、請求項１に記載の方法。
【請求項６】
前記ネットワークが、前記ルート鍵材料を有する管理装置を有し、前記方法は、前記ルート鍵材料及び前記第１のノードの識別子に基づいて前記第１のノード鍵材料を生成し、前記第１のノード鍵材料を前記第１のノードに送信する準備ステップを有する、請求項１に記載の方法。
【請求項７】
前記ルート鍵材料及び前記第１のノード鍵材料共有が、複数のセグメントを有し、前記ステップｂ）が、鍵セグメントを生成するように各第１のノード鍵材料共有セグメントに対して実行され、前記方法が、
ｃ）前記共有鍵を得るように前記鍵セグメントを結合するステップ、
を有する、請求項１に記載の方法。
【請求項８】
前記鍵セグメントを結合するステップｃ）が、連結により又は論理的結合により実行される、請求項７に記載の方法。
【請求項９】
通信ネットワークであって、前記ネットワークの第１のノード及び第２のノードを表す２つの通信エンティティを有する通信ネットワークにおいて、
前記第１のノードが、
第１のノード鍵材料共有を記憶するメモリと、
共有鍵を生成するように、第２のノードの識別子において前記第１のノード鍵材料共有を評価する手段と、
を有し、
前記評価する手段が、
Fqのサブフィールド上の次数rの既約多項式を法として前記フィールドFq上の被約多項式の形で前記第１のノード鍵材料を因数分解する手段であって、前記被約多項式は、前記第２のノードの識別子における前記第１のノード鍵材料の評価が、前記既約多項式を法として、前記フィールドFq上の単項式を反復的に評価及び結合することに相当する、当該因数分解する手段と、
Fqの前記サブフィールド上の次数rの前記既約多項式を法として前記フィールドFq上の次数r-1の係数多項式を所定の点において評価することにより各単項式演算の結果を計算する手段であって、前記係数多項式は、前記係数多項式を評価することが、前記既約多項式を法としてFqの前記サブフィールド上の単項式を反復的に評価及び結合することに相当するように構成される、当該計算する手段と、
を有する、
通信ネットワーク。
【請求項１０】
ルート鍵材料と、
前記第１のノードの識別子及び前記ルート鍵材料に基づいて、第１のノード鍵材料共有を生成する手段と、
前記第１のノード鍵材料共有を前記第１のノードに送信する送信器と、
を有する管理装置を有する、請求項９に記載の通信ネットワーク。
【請求項１１】
ネットワーク内の通信を保護するように第１のノードと第２のノードとの間の共有鍵を生成するコンピュータプログラムにおいて、前記第１のノードが、ルート鍵材料に基づく第１のノード鍵材料共有を記憶し、前記コンピュータプログラムが、前記第１のノード上で実行される場合に、
ａ）前記第２のノードの識別子を受信するステップと、
ｂ）前記共有鍵を生成するように、前記第２のノードの識別子において前記第１のノード鍵材料共有を評価するステップと、
を前記第１のノードに実行させ、
前記第１のノード鍵材料共有が、有限フィールドFq上の多項式ベースの鍵材料であり、前記ステップｂ）が、
ｂ１）Fqのサブフィールド内の係数を持つ次数rの既約多項式を法として前記フィールドFq上の被約多項式の形で前記第１のノード鍵材料を因数分解するステップであって、前記被約多項式は、前記第２のノードの識別子において前記第１のノード鍵材料を評価することが、前記既約多項式を法として、前記フィールドFq上の、例えば前記第２のノードの識別子における、単項式を反復的に評価及び結合することを含む、当該因数分解するステップと、
ｂ２）Fqのサブフィールド内の次数rの前記既約多項式を法としてFqのサブフィールド内の係数を持つ次数r-1の多項式を所定の点において評価することにより各単項式演算の結果を計算するステップであって、前記係数多項式は、前記係数多項式を評価することが、前記既約多項式を法としてFqのサブフィールド上の前記所定の点における単項式を反復的に評価及び結合することに相当するように構成される、当該計算するステップと、
を有する、コンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信ネットワークに対するセキュリティシステムに関する。
【０００２】
より正確には、本発明は、ネットワーク内の異なるノードの間の通信を保護（securing）する暗号鍵を生成する方法に関する。
【０００３】
本発明は、例えば、医療用アクチュエータ及びセンサネットワーク又は家庭用電化製品ネットワークのような無線ネットワークに関する。
【背景技術】
【０００４】
同等のネットワークに対する、ある従来の保護システムは、ネットワークに属するノードが、既製の暗号鍵を直接的に与えられないが、通信を保護するために前記ネットワークの他のノードとの共有鍵を計算することを可能にする、あるノード固有の鍵材料を与えられるアルファセキュア（alpha-secure）と称される鍵材料共有（keying material share）配布スキームに基づく。このノード固有の情報は、前記ネットワークの管理装置に含まれるルート鍵材料から導出される鍵材料共有である。前記ルート鍵材料は、アルファより少ないノードの獲得、したがってアルファより少ない鍵材料共有の組み合わせが、前記ルート鍵材料に関して何も暴露しないようなものである。結果的に、このようなシステムは、アルファが十分に大きく選択される場合に、攻撃の下で良好な回復力を提供する。他の無相関技術は、前記ノードに配布された鍵材料共有を無相関にし、したがって鍵生成プロセス干渉することなしに、攻撃者が基本的なルート鍵材料に関する情報を得ることを防止することによりシステムセキュリティを更に増大させるのに使用されることができる。
【０００５】
アルファセキュアシステムは、鍵配布、情報を放送すること、及び計量デジタル証明書を用いてエンティティにより運ばれる鍵材料共有に情報を暗号的にリンク付けすることを含む異なるセキュリティ機能を可能にする。
【０００６】
前記ルート鍵材料は、例えば、次数アルファの対称二変数多項式であり、ノードの鍵材料共有は、このノードの識別子に対応する点においてこの二変数多項式を評価することにより得られる。
【０００７】
一般に、大きな有限フィールド上の多項式が使用され、これは、前記多項式の係数が、大きなプライム有限フィールドに含まれ、したがって計算を実行するのに高い要求を必要とすることを意味する。しかしながら、無線センサネットワーク又は同様の他のネットワークに含まれる装置は、一般に、計算及び通信リソースに関してリソース制約を受ける。したがって、従来の方法は、このようなネットワークに良好に適合されていない。
【０００８】
鍵セグメンテーションを実行する代替的な解決法も、提案されている。これらの解決法は、鍵材料を表す多項式を形成するように連結された複数のサブ多項式の使用にある。しかしながら、このセグメンテーションは、たとえ計算動作の数を減少させるとしても、メモリサイズに関してはリソース要件の問題を解決することを助けない。
【０００９】
多項式ベースの証明書の生成に対するアルファセキュアシステムの使用は、効率的な実施に更なる課題を持ち込む。アイデンティティセグメンテーション技術が使用されることができ、しかしながら、２つの可能な構成の間に重要なトレードオフが存在する。第１の構成は、多数の短いセグメントの使用に基づく。第２の構成は、少数の大きなセグメントを使用する。前記第１の構成が、より高いメモリ要件を要求するのに対し、前記第２の構成は、より長いセグメントサイズのため、より高い計算要件を要求する。
【発明の概要】
【発明が解決しようとする課題】
【００１０】
本発明の目的は、上述の欠点を克服するセキュアシステムを提供することである。
【００１１】
本発明の他の目的は、通信ネットワークにおける暗号鍵の効率的な生成に対する方法を提供することである。
【００１２】
本発明の更に他の目的は、多項式ベースの証明書及び鍵一致に対して使用されるアルファセキュアシステムにおいてメモリ要件及び計算要件の両方を最小化しながら暗号鍵を生成する方法を提供することである。
【００１３】
本発明の更に他の目的は、例えば、多項式ベースの証明書スキームにおいて攻撃の下で増大された回復力を持つ暗号鍵を生成する方法を提供することである。
【課題を解決するための手段】
【００１４】
このために、本発明は、ネットワーク内の通信を保護するために第１のノードと第２のノードとの間の共有鍵を生成する方法を提供し、前記第１のノードは、ルート鍵材料に基づく第１のノード鍵材料共有を記憶する。
【００１５】
前記方法は、以下のステップ、すなわち、
前記第１のノードが、前記第２のノードの識別子を受信することにあるステップａ）と、
前記第１のノードが、前記共有鍵を生成するために、第２のノードの識別子において前記第１のノード鍵材料共有を評価することにあるステップｂ）であって、前記第１のノード鍵材料共有が、有限フィールドFq上の多項式ベースの鍵材料である、当該ステップｂ）と、
を有する。
【００１６】
本発明の現在の定義によると、前記評価するステップは、
前記第１のノードが、Fqのサブフィールド内の係数を持つ次数ｒの既約多項式（irreducible polynomial）を法としてフィールドFq上の被約多項式（reduced polynomial）の形式で前記第１のノード鍵材料を因数分解するサブステップｂ１）であって、前記被約多項式は、前記第１のノードの識別子において前記第１のノード鍵材料を評価することが、前記既約多項式を法として、フィールドFq上の前記第２のノードの識別子における多項式、例えば単項式の対を反復的に評価及び結合することを含む、当該サブステップｂ１）と、
前記第１のノードが、Fqのサブフィールドにおける次数rの前記既約多項式を法としてFqのサブフィールド内の係数を持つ次数r-1の多項式を所定の点において評価することにより各単項式演算の結果を計算するサブステップｂ２）であって、前記係数多項式は、前記係数多項式を評価することが、前記既約多項式を法としてFqのサブフィールド上の前記所定の点において多項式、例えば単項式を反復的に評価及び結合することに対応する、当該サブステップｂ２）と、
を有する。
【００１７】
結果として、前記第１のノードのアルファセキュア鍵材料の評価は、既存の方法のように、有限フィールドFq上では実行されず、サブフィールド上で実行される。このようなフィーチャは、前記方法を実行する、すなわち、モジュラ乗算及び加算を実行するための前記計算要件を低減させることを可能にする。
【００１８】
典型的な実施例において、前記第１のノード鍵材料は、Fqのサブフィールド内の係数を持つ前記被約多項式及び次数アルファの多項式に基づき、アルファは、例えばr-1に等しい。
【００１９】
付加的な実施例によると、前記システムは、鍵が、tのサブ鍵セグメントの連結として計算されるように、システム構成後の鍵生成を可能にする。各サブ鍵セグメントは、次数アルファの異なる鍵材料セグメントの鍵材料から生成される。
【００２０】
更に、典型的な実施例において、前記有限フィールドを規定する整数qは、prに等しく、ここでpは素数であり、r-1は多項式として解釈される場合に前記第１のノードの鍵材料の単項式の次数である。このような実施例において、演算は、Zp[x]/f(x)において実行され、f(x)を法としたZpにおける係数を持つ次数r-1の多項式のセット、すなわちpを法とした整数のセットに対応する。このようなフィールドは、極めて小さく、したがって前記計算の効率は、高度に増大され、暗号要素を記憶するのに必要なビット数は、rlog(p)に制限される。
【００２１】
他の典型的な実施例において、鍵セグメンテーションが使用され、これは、前記ルート鍵材料及び前記第１のノード鍵材料共有が、複数の鍵材料セグメントを有することを意味する。したがって、前記方法のサブステップｂ）は、本実施例において、鍵セグメントを生成するために各鍵材料共有セグメントに対して実行され、前記方法は、更に、結果として生じる共有鍵を生成するために前記鍵セグメントを結合するステップを有する。
【００２２】
このような実施例は、多すぎる追加のリソースを要求することなしに、より長い鍵を生成することを可能にする。実際に、高度に複雑な演算ではない複数の鍵セグメントの連結によってのみ、最小限の計算でより長い共有鍵を得て、したがって前記システムの回復力を再び増大させることが可能である。
【００２３】
更に他の典型的な実施例において、前記方法は、前記ルート鍵材料を有する管理装置、例えば前記ルート鍵材料を確実に計算及び記憶するトラストセンタを有するネットワークにおいて実施される。したがって、前記第１のノード鍵材料共有は、前記ルート鍵材料及び前記第１のノードの識別子に基づいて前記管理装置により生成され、前記第１のノードに送信される。前記管理装置は、例えば、高度に保護されたトラストセンタであり、これは、前記ルート鍵材料に対して良好な保護を提供する利点を持つ。
【００２４】
本発明は、通信ネットワークにも関し、前記ネットワークは、前記ネットワークの第１のノード及び第２のノードを表す２つの通信エンティティを有する。
【００２５】
前記第１のノードは、第１のノード鍵材料共有を記憶するメモリと、共有鍵を生成するために、第２のノードの識別子において前記第１のノード鍵材料共有を評価する手段とを有する。
【００２６】
評価手段は、以下の手段、すなわち、
・例えば連続して、tの鍵セグメントを計算する手段と、
・前記第１のノード鍵材料を因数分解する、すなわち、例えばFqのサブフィールド上の次数r-1の、被約多項式の形式の第１のノード鍵材料の各単項式を因数分解することにより、各鍵材料セグメントから鍵セグメントを生成する手段であって、前記第２のノードの識別子における前記第１のノード鍵材料の評価は、Fqのサブフィールド内の要素を持つ次数rの既約多項式を法として、係数がFqのサブフィールド上の次数r-1の多項式として解釈される単項式を反復的に評価及び結合することに相当する、当該生成する手段と、
・Fqのサブフィールド上の次数r-1の前記既約多項式を法としてフィールドFq上の次数r-1の係数多項式を所定の点において評価することにより各単項式演算の結果を計算する手段であって、前記係数多項式は、前記係数多項式を評価することが前記既約多項式を法としてFqのサブフィールド上の単項式を反復的に評価及び結合することに相当するように構成される、当該計算する手段と、
の少なくとも一部を有する。
【００２７】
本明細書において、単項式は、次数１の１つの係数、及び次数０の１つの係数を有する。
【００２８】
本発明は、本発明による方法を実施するコンピュータプログラムにも関する。
【００２９】
本発明のこれら及び他の態様は、以下に記載される実施例を参照して説明され、明らかになる。
【００３０】
本発明は、ここで、添付の図面を参照して例として更に詳細に説明される。
【図面の簡単な説明】
【００３１】
【図１】本発明の第１の実施例が実施されるネットワークの例である。
【図２】本発明による方法の第２の実施例の動作シーケンスを示すブロック図である。
【発明を実施するための形態】
【００３２】
本発明は、安全な通信に対して２つのノードの間の共有鍵を生成する方法に関する。
【００３３】
図１は、本発明による方法の第１の実施例が実施されるネットワーク1を示す。
【００３４】
このネットワーク1は、前記ネットワークのノードを表す２つの通信エンティティD1及びD2を有し、更に、管理装置2を有する。
【００３５】
このようなネットワーク1の例は、
・エンティティD1及びD2が、医療用センサ及び医療用アクチュエータのような医療用装置である、無線医療ネットワーク、
・エンティティD1及びD2が、テレビ、ＤＶＤプレイヤ、オーディオシステムのような電化製品である、家庭用電化製品ネットワーク、
・エンティティD1及びD2が、建物内の照明機器である、照明ネットワーク、
・D1及びD2が、パーソナルデジタルアシスタント、携帯電話、コンピュータ、電子車載機器のような電子装置である、電子ネットワーク、
である。
【００３６】
管理装置2は、一実施例において、トラストセンタである。他の実施例において、前記ネットワークは、ユーザのものであるパーソナルエリアネットワークである。この場合、D1、D2及び管理装置2は、前記ユーザのものである。前記管理装置は、例えば、暗号材料を生成する手段、例えばＳＩＭカード、及びD1及びD2に暗号材料を送信する手段を有する、携帯電話又はデジタルアシスタントである。
【００３７】
前述の例を考慮して、本発明において対処するネットワークが、機密データを扱い、したがってこれらのデータがネットワークの装置間で交換される場合に高度のセキュリティを要求しうるように見える。他方で、体センサのような装置は、高度にリソース制約を受ける。本発明は、したがって、安全にデータを交換するために装置D1及びD2に対する共有鍵を生成する、又はこれらの装置における限定的な量の利用可能なリソースを考慮に入れて、承認多項式ベース証明書を生成する方法を提供する。
【００３８】
前記管理装置は、前記ネットワークの構成を管理し、前記ルート鍵材料を記憶する。本発明において、前記方法は、アルファセキュアシステムと一緒に使用され、したがって、前記ルート鍵材料は、有限フィールドFq上の多変数多項式であり、これは、前記多変数多項式の全ての係数が、このフィールドに属することを意味する。この実施例において、qはprに等しく、pは素数であり、rは厳密に１より大きい整数である。したがって、前記多変数多項式の係数及び識別子は、Fp内の要素を持つ次数r-1の多項式として解釈されることができる。q = prを使用することは、rを変更することにより異なるセグメントサイズを容易に達成し、異なるp値を選択することにより異なるアーキテクチャに前記システムを適合することが可能であるので、細かいパラメータ設定を可能にする。
【００３９】
Fqは、要素の数に対応する次数q = pr及び指標pの有限フィールドである。次数prのユニークなフィールドが存在し、これは、Zpのコピー、すなわち0ないしp-1の全ての整数の組を含む。Zpは、Fqのサブフィールドとして見られることができる。有限フィールドは、Fqに属する２つの要素がqを法として加算又は乗算されることができるようなものである。
【００４０】
前記ルート鍵材料に基づいて生成されることができる鍵の数は、qの値に依存する。この方法において使用されることができるqの特定の値は、例えば、28，216，232，264，2128，(28+1)4及び(216+1)2である。より一般的には、qに対する特定の関連する値は、q=2rであり、rは整数であり、前記管理装置は、異なるフィールドサイズを選択することにより長さrビットのセグメントを容易に較正することができ、鍵生成アルゴリズムは、rパラメータに依存する小さな修正のみを必要とする。
【００４１】
ネットワーク構成の段階中に、各装置は、前記ルート鍵材料及び前記装置の暗号識別子に基づいて、前記管理装置により生成された鍵材料共有を与えられる。前記ルート鍵材料が、多変数多項式、例えば二変数多項式である場合、特定の装置に対する前記鍵材料共有の生成は、単変数多項式を得るために、前記装置に記憶された、前記装置の識別子においてこの多項式を評価することに対応する。一度装置が構成されると、これは、前記ネットワークにおいて展開される（deployed）。装置D1及びD2が、通信することを望む場合、前記装置は、各装置が他方の装置の識別子において自身の鍵材料共有を評価することにより共通の共有鍵について一致する。
【００４２】
共有鍵を生成するこのプロセスは、ここで、図２に示されるブロック図を参照して、一例について詳述される。
【００４３】
この例において選択された特定のパラメータは、以下のとおりである。
・q=232、及び
・４つの鍵セグメントが使用され、これは、前記ルート鍵材料が、４つの鍵材料セグメントの連結に対応し、前記鍵材料セグメントの各々が二変数多項式であることを意味する。
ここで、パラメータp=2、r=32及び等しい長さの４つのセグメントは、所定のネットワークにおいてメモリ及び計算要件を最適化するように生成される。
【００４４】
初めに、前記管理装置は、ルート鍵材料
G(y,z) = g1(y,z)||g2(y,z)||g3(y,z)||g4(y,z)
を有し、ここで、
0005564053.tif 000002
であり、aij=aji∀{i,j}である。したがって、前記ルート鍵材料の各セグメントは対称であり、これは、２つの装置の間の共有鍵の生成を可能にする。
【００４５】
構成段階CONFIG中に、識別子IDを持つ装置は、以下のように前記管理装置により生成された鍵材料共有G(ID,z)を与えられる。
G(ID,z) = g1(y=ID,z)||g2(y=ID,z)||g3(y=ID,z)||g4(y=ID,z)
【００４６】
前記装置が、識別子ID'を持つ他の装置と通信することを必要とする場合、KEY_GENにおいて、
G(ID, z=ID') = g1(ID,z=ID')||g2(ID,z=ID')||g3(ID,z=ID')||g4(ID,z=ID')
の値を計算することにより共有鍵を生成することが必要である。
【００４７】
各セグメントは、別々に評価され、全てのセグメントは、結果として生じる共有鍵を得るために、このプロセスの終了時に連結される。
【００４８】
gkが、q = pr = 232である有限フィールドFq上の多項式であるから、これは、単項式が、多項式f(x)を法としてZp内の係数を持つ次数31の多項式として表されることができることを意味し、ここでf(x)は、以下のように、FqのサブフィールドZp上の次数r=32の既約多項式である。
0005564053.tif 000003
【００４９】
上の例において、λは、31の典型的な値を取るが、他の値を取ってもよい。前記システムの管理装置が、設定パラメータの他のセットを選択する場合、この表現は、例えば、新しいr値に容易に適合されることができる。
【００５０】
q=232である場合のf(x)の可能な値は、例えばx32+x7+x3+x2+1である。より一般的には、f(x)は、好ましくは、より効率的な実施を可能にするために非ゼロの低次の係数のみを持つように選択される。
【００５１】
このような多項式の評価は、長い計算時間を必要とし、したがって因数分解方法が、このような評価を速めるのに使用される。多項式に対する既知の因数分解方法は、ホーナー法（Horner's rule）であり、これは、多項式を単項式形式の組み合わせとして表すことからなる。この実施例において、このホーナー法が使用される。しかしながら、本発明は、この方法に限定されず、多項式因数分解の他の方法を用いて実施されることができる。
【００５２】
したがって、図２に示されるブロック図のHORNER Iステップにおいて、ホーナー法が、gk-ID(z)に対して使用され、これを因数分解し、単項式の組み合わせを得る。単項式の評価は、展開された多項式の評価より複雑さが低く、したがって、リソースに関してコストがかからない。この因数分解は、以下のように記載されることができ、ここでラムダ値は、31に等しいが、他の値を取ってもよい。
0005564053.tif 000004
【００５３】
コンピュータアルゴリズムにおいて、前記HORNER Iステップは、
r=blambda
for (ctr=lambda-1;ctr>0;ctr--){
r=r*ID'(mod (f(x));
r=r+bctr
}
return r;
と表されることができる。
【００５４】
上記のように、gk-IDは、Fp^r=F2^32上の多項式であり、これは、全ての係数biがこの有限フィールドに属することを意味する。F2^32内の各要素は、要素C[x]として多項式ベースで表されることができ、ここでC[x]は、f(x)を法として、Zp=Z2内の係数を持つ全ての多項式のセットを表すZp[x]/f(x)に属する。
C[x] = c31x31+c30x30+...+ cwxw+...+c2x2+c1x+c0== [c31c30...cw...c2c1c0]
【００５５】
したがって、主要な多項式共有の評価を再び速めるために、本発明のこの実施例は、第２の因数分解プロセスが、各係数biに対して、HORNER Iに加えられる。したがって、ステップHORNER IIにおいて、評価すべき前記鍵材料共有セグメントの各係数biは、Z2[x]/f(x)内の要素として表される。
【００５６】
したがって、両方のステップHORNER I及びHORNER IIを含む一般的なアルゴリズムは、
CalculateKey([blambda,blambda-1,...,b0], ID'){
r=blambda
for (ctr=lambda-1;ctr>0;ctr--){
r=MultiplyElementsGF(r, ID');
r=r XOR bctr
}
return r;
}
として表されることができる。関数"CalculateKey"は、点ID'において係数blambda, blambda-1, ..., b0を持つ主要な多項式の評価を実行する。この評価は、サブフィールドZpに属する２つの要素a及びbの乗算を実行する関数"MultiplyElementGF"の使用を必要とする。
MultiplyElementsGF(a,b){
aa=a, bb-b,r=0,t:
while(aa!0){
If((aa & 1)!0){r=r XOR bb;}
t=bb AND 0x80000000;
bb=bb<<1;
if(t!=0){bb=bb XOR 0x0000008D;}
aa=aa>>1;
}
return r;
}
【００５７】
図２のブロック図は、このようなアルゴリズムの演算シーケンスを示し、HORNER IIの周りの回帰矢印は、"while"ループ内の開方（evolution）を表し、HORNER I及びHORNER IIの両方の周りの回帰矢印は、"for"ループ内の開方を表す。この階層的な構成は、階層的な二段の形に演算を分散することにより多項式ベースのシステムの効率的な評価及び実行を可能にする。高いレベルで、我々は、評価がHORNER Iを使用することにより最適化される主要な多項式の評価を見つける。前記フィールドの特別な形式のため、我々は、HORNER Iと組み合わせて第２のレベルにおいて前記システムを最適化する。このために、我々は、各乗算においてHORNER Iと相互作用するHORNER IIを加える。
【００５８】
したがって、前記鍵材料共有セグメントの評価は、本発明の代表的な実施例においてZ2[x]/f(x)における算術的演算に約分（reduced）され、前記算術的演算は、かなり単純であり、したがって低いリソースを必要とし、
−Z2[x]/f(x)内の２つの要素の加算が、両方の要素のXORとして定義され、
C [x]+C'[x]= [c31c30…cw…c2c1c0] XOR [c'31c'30…c'w…c'2c'1c'0]
−Z2[x]/f(x)内の２つの要素の加算が、f(x)を法として、通常通りに定義される。
C[x]*C'[x]= (c31x31+ …+ cwxw+…+c1x+c0)*(c'31x31+ …+c'wxw+…+c'1x+c'0)(mod f(x))
【００５９】
例えば、フィールドF2^8上の単項式、P(y) = 64y + 225を仮定する。
【００６０】
a1= 3及びa0=173は、F2^8に属する整数であり、これは、これらが、2において評価されるZ2[x]/f(x)内の多項式として記載されることができることを意味する。
【００６１】
この場合、a1=53=a1(w=2)であり、ここでa1(w)=w6+w4+w2+1であり、したがってa1は、a1=01010101として表されることもできる。
【００６２】
同様に、a0=173=a0(w=2)であり、ここでa0(w)=w7+w5+w3+w2+1であり、a0は、a0=10101101として表されることもできる。
【００６３】
したがって、y=ID=10101111において前記多項式を評価したいと望む場合、この計算は、[01010101]*[10101111] XOR [01010101] (mod f(x))に相当し、これは、かなり単純な計算であり、低いリソースを必要とする。
【００６４】
典型的な実施例において、因数分解された多項式、又は被約多項式の各乗算は、次数r-1の２つの多項式の評価を因数分解することにより更に因数分解又は約分される。このような因数分解は、最大r-1の反復及びr-1の約分（reductions）を必要とする。
【００６５】
典型的にはHORNER I及びHORNER IIにおける、因数分解の２つのレベルは、アルファかけるrより少ない約分において多変数多項式ベースのアルファセキュアシステムにおける対鍵を計算することを可能にする。
【００６６】
一度、各鍵材料共有セグメントが、評価されると、これら全てのセグメントは、CONCATにおいて連結され、ハッシュ関数を用いることにより装置IDと装置ID'との間の結果として生じる共有鍵を生成する。この例において、前記結果として生じる共有鍵は、異なるセグメントの連結により得られる。しかしながら、他の実施例において、これは、前記鍵セグメントの算術的又は論理的結合のような他の組み合わせにより得られてもよい。
【００６７】
本発明が、ネットワーク内の装置を承認することを可能にする前記ネットワーク内の装置の暗号識別子IDを生成するのに使用されるアルファセキュアデジタル署名に関連して使用されることもできることに注意しなくてはならない。このようなアプローチは、装置又はエンティティに属し、そのデジタルアイデンティティを表すパラメータのセットに基づく。フィンガープリントに対応する識別子IDは、この場合、前記デジタルアイデンティティのパラメータをハッシュすることにより生成される。前記管理装置は、前記エンティティの前記鍵材料共有及び前記IDに基づいて、前記エンティティのデジタルアイデンティティが本物であるかどうかを決定することができる。
【００６８】
このデジタル署名アプローチの変形において、識別子IDは、複数の識別子にセグメント化される。Hash(Digital Identity)=ID=ID1||ID2||...||IDt
【００６９】
NWK_Sizeのノードを受け入れ、tのセグメントを持つアルファセキュアデジタル署名を使用し、各セグメントがb'ビット長（b'=log(q')=log(Fq'のサイズ)）であるネットワークにおいて、攻撃者は、確率
0005564053.tif 000005
で前記ネットワーク内のセグメント及びサブ識別子を再結合することによりkの衝突で偽造アイデンティティを生成することができる。
【００７０】
これは、前記偽造識別子が、前記ネットワークにおいて見つけられることができるkのサブ識別子を含むことを意味する。上記の式のこの確率は、p1に依存し、これは、
0005564053.tif 000006
として定義される。
【００７１】
したがって、我々は、より大きなb'が使用される場合、すなわちより長いセグメントが使用される場合にこの確率を減少させることができる。
【００７２】
b'のこの拡大は、このような場合に、前に説明したように、各セグメントが、Zp[x]/f(x)の要素として多項式ベースで表されることができるので、次数q=prを使用することにより可能にされる。したがって、IDにおける鍵材料共有セグメントの評価は、フィールドZp[x]/f(x)内の演算に約分されることができる。これは、モジュラ演算を必要とすることなしにより長いセグメントを実施することを可能にする。したがって、より長いセグメントの使用は、増大された証明書回復力を可能にする。最後に、同じ証明書セキュリティレベルを達成するのにより少ないセグメントが必要とされるので、より少ないメモリが必要とされる。
【００７３】
上記記載から、本発明の複数の利点が見える。まず、この方法は、メモリリソースの使用を最適化することを可能にする。実際に、本発明は、全ての係数がサイズ2rの有限フィールドに属する鍵材料を実行する。これは、全ての係数が、厳密にrビットで記憶されることができ、したがってメモリが、多項式ベースのアルファセキュアシステムにおいて浪費されないことを意味する。
【００７４】
更に、有限フィールドFp^rは、Zpのようなより小さなフィールドの拡張であり、本発明は、前記小さなフィールドにおいて全ての計算を実行することを可能にし、したがって計算速度を増大し、前記装置の計算要件を制限する。より正確には、本発明による方法の使用は、32ビットのセグメントを用いるデジタル署名アプローチの実施を可能にし、同時に、
・より長いセグメントが効率的に実施されることができるので16ビットのセグメントが使用される場合と同様のセキュリティレベルを、前記アルファセキュアデジタル署名において、達成するように前記メモリ要件を減少し、
・32ビットセグメントを使用する鍵生成に対する計算要件を減少する。
【００７５】
加えて、本発明によるコンピュータプログラムは、鍵生成のアルゴリズムを実施するのに、以前使用されていた方法に必要とされたコードメモリより少ないコードメモリを必要とする。
【００７６】
本明細書及び請求項において、要素に先行する単語"１つの"（"a"又は"an"）は、複数のこのような要素の存在を除外しない。更に、単語"有する"は、記載された要素又はステップ以外の要素又はステップの存在を除外しない。
【００７７】
本開示を読むことにより、他の修正例は、当業者に明らかになる。このような修正例は、通信を保護する分野において既知であり、ここに既に記載されたフィーチャの代わりに又は加えて使用されることができる他のフィーチャを含んでもよい。
【図１】
0005564053.tif 000007
【図２】
0005564053.tif 000008