(57)【要約】  本発明による方法は、任意選択の補足データを有する暗号アルゴリズムを自動的に生成する方法に関し、前記アルゴリズムは２つのそれぞれ異なるゾーン、すなわち、サイドチャネル解析にさらされるアルゴリズムの外側の部分にある外部アルゴリズム秘密ゾーン、ならびに、アルゴリズム秘密ゾーンではアルゴリズムのコードが命令のランダム（または擬似ランダム）および独立シーケンス、および／または命令と任意定数の何らかの固定セットから選択されるテーブルルックアップから何らかの固定で規定の確率分布で局所的に作られるような、かつ、内部暗号セキュリティゾーンは、アルゴリズムのセキュリティだけを処理しサイドチャネル攻撃から保護される必要がないいかなる暗号アルゴリズムまたは方法でもよいような、サイドチャネル解析にさらされない内部の純粋に暗号のゾーンを含む。
2008516502.tif 000002
【特許請求の範囲】
【請求項１】
電子装置で暗号アルゴリズムを生成する方法であって、
命令のランダムまたは擬似ランダムおよび独立シーケンス、および／または命令と任意定数の何らかの固定セットから選択されたテーブルルックアップを生成すること、ならびに
前記シーケンスおよび／またはテーブルルックアップを、アルゴリズムの安全な暗号アルゴリズムと呼ばれるアルゴリズムのセキュリティを処理する暗号アルゴリズムと組み合わせることによって前記暗号アルゴリズムを生成すること
を含む、方法。
【請求項２】
命令のランダムまたは擬似ランダムおよび独立シーケンス、および／または命令と任意定数の何らかの固定セットから選択されたテーブルルックアップを何らかの固定で規定の確率分布で生成することにあることを特徴とする、請求項１に記載の方法。
【請求項３】
前記アルゴリズムが、２つのゾーン、すなわち、サイドチャネル解析にさらされるアルゴリズムの外側の部分にある外部アルゴリズム秘密ゾーン、ならびに、アルゴリズム秘密ゾーンではアルゴリズムのコードが命令のランダムまたは擬似ランダムおよび独立シーケンス、および／または命令と任意定数の何らかの固定セットから選択されるテーブルルックアップから局所的に作られるような、かつ内部暗号セキュリティゾーンがアルゴリズムのセキュリティだけを処理するいかなる暗号アルゴリズムまたは方法でもよくサイドチャネル攻撃から保護されなくてもよいようなサイドチャネル分析にさらされない内部の純粋に暗号のゾーンを含むことを特徴とする、請求項１または２の一項に記載の方法。
【請求項４】
アルゴリズムの安全な暗号アルゴリズムが可逆暗号化アルゴリズムであり、前記命令のシーケンスおよび／またはテーブルルックアップは、鍵依存定数を加えてまたは加えることなく生成されたランダム命令のシーケンスから構築される一連の全単射ルーチンのシーケンスであること、および、ランダムに生成された関数を現在の状態に作用する全単射ルーチンに変換するために、ランダムに選択されたサブルーチンを構成することにあることを特徴とする方法であって、サブルーチンのいくつかは新規のまたは古い擬似ランダム置換Ｓボックスであり、他は一時に１つの現在の変数を変更しそれを他の全ての現在の変数、およびランダムにまたは擬似ランダムに生成された定数の任意関数と組み合わせると定義される一般化フェイステル方法で構成され、他のいくつかの関数もランダムにまたは擬似ランダムに選択されたＴ関数の大きな合成を含んでもよいパラメータと呼ばれる特別のタイプのＴ関数を現在の変数に加えるか、またはＸＯＲすることによって全単射にされてもよい、請求項１から３の一項に記載の方法。
【請求項５】
生成された暗号化アルゴリズムの第１の鍵依存命令が、何らかの規定の確率分布で任意に選択された命令の任意の長さのシーケンスを含むことができる一連の秘密変換の後で暗号化プロセスの内部深くで処理されること、および前記アルゴリズムが差分電力解析（ＤＰＡ）などのサイドチャネル攻撃から保護されるように攻撃者は鍵依存部分の入力の知識がないことを特徴とする、請求項１から４の一項に記載の方法。
【請求項６】
生成された暗号アルゴリズムの読み取り可能な仕様および／または出力アルゴリズムのテスト値をさらに生成することを特徴とする、請求項１から５の一項に記載の方法。
【請求項７】
テスト値が、テスト値を有するテスト暗号のランダム処理によるＤＦＡ攻撃からの保護を備えるコードを自動的に生成するために使用されることを特徴とする、請求項１から６の一項に記載の方法。
【請求項８】
擬似ランダムの一時的な一意の暗号アルゴリズムを生成すること、ならびにそれらを実行可能な形で現在のセッションにおいて鍵共有、認証および／または暗号化のために使用されるべきリモートデバイスに送ることにあることを特徴とする、請求項１から７の一項に記載の方法。
【請求項９】
記憶手段およびデータ処理手段を含む電子装置であって、前記処理手段は、命令のランダムまたは擬似ランダムおよび独立シーケンス、および／または命令と任意定数の何らかの固定セットから選択されたテーブルルックアップを生成する手段を含むこと、ならびに、前記データ処理手段は、前記シーケンスおよび／またはテーブルルックアップを、アルゴリズムのセキュリティを処理する前記記憶手段に記憶されている暗号アルゴリズムと組み合わせることによって暗号アルゴリズムを生成することを特徴とする、電子装置。
【請求項１０】
プログラムが電子装置で実行される場合、請求項１から８の一項に記載の方法のステップを実行するプログラムコード命令を含むコンピュータプログラム。
【請求項１１】
暗号アルゴリズムを含む電子システムを保護する方法であって、
命令のランダムまたは擬似ランダムおよび独立シーケンス、および／または命令と任意定数の何らかの固定セットから選択されたテーブルルックアップの計算、ならびに
前記命令のシーケンスおよび／またはテーブルルックアップの、アルゴリズムのセキュリティを処理する暗号アルゴリズムとの組み合わせの実行
を含むことを特徴とする、方法。
【請求項１２】
情報処理手段および情報記憶手段を含む電子システムであって、命令のランダムまたは擬似ランダムおよび独立シーケンス、および／または命令と任意定数の何らかの固定セットから選択されたテーブルルックアップを計算する手段、ならびに前記命令のシーケンスおよび／またはテーブルルックアップの、アルゴリズムのセキュリティを処理する暗号アルゴリズムとの組み合わせを実行する手段を含むことを特徴とする、電子システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、秘密データを使用してまたは使用せずに暗号アルゴリズムの自動的で安全な生成のための装置を構築することからなる。前記アルゴリズムは、安全なモジュールによって生成され相互に非常に異なっていなければならない。
【背景技術】
【０００２】
ペイＴＶの分野では、カードプロバイダはＴＶプロバイダごとに異なる暗号プロトコルおよび暗号アルゴリズムを提供する必要がある。さらに、システムのセキュリティを上げるために予め決められた周期で前記暗号アルゴリズムを変更したいと思うＴＶプロバイダもある。本発明の問題の１つは、ときどきまたは電子システムごとに異なる安全な暗号アルゴリズムを提供することである。
【０００３】
解決すべき他の主要な問題は、良好なレベルの「アルゴリズムの秘密性」を実現することである。さらに、その生成方法は、アルゴリズムに対するアルゴリズム攻撃に対しても、電子システムに対する実装（サイドチャネル）攻撃に対しても安全なアルゴリズムを体系的に実現することができるようなやり方で設計される。これら２つのセキュリティ特性は両方とも個々のアルゴリズムそれぞれの特性ではなく、生成装置のノントリビアルな特性である。実際、知られている暗号攻撃およびサイドチャネル攻撃は、本発明によって実現されるアルゴリズムの秘密性のために簡単かつ正確には働かない。「アルゴリズムの秘密性」の中心的な問題は、個々の暗号アルゴリズムそれぞれには理解することさえできず、攻撃者が１つのアルゴリズムについての何らかの有用な知識を別のアルゴリズムを観察することによって得ることができないことと定義されることができる。
【０００４】
アクセス、電子取引およびデータを保護するためには、暗号プロトコルおよび（サブコンポーネントとして）安全な暗号アルゴリズム（たとえば、暗号化アルゴリズムまたはデジタル署名アルゴリズム）を使用しなければならない。暗号アルゴリズムのセキュリティは見られることができない。それらの多くは毎年新規のノントリビアルな数学的方法またはアルゴリズム的方法によって破られるので、反対のものだけは見られることができる。スマートカードなどの電子装置にそのようなアルゴリズムを安全に実装することはさらにいっそう難しい。このため多くの企業および政府は決定的な暗号アルゴリズムの設計を常に秘密にしてきた。これはＧＳＭ  ＳＩＭカードおよびペイＴＶスマートカードに使用されるアルゴリズムにはよくあることである。これらのアルゴリズムの秘密性が、たとえばリバースエンジニアリングによって破られた場合、多くのシステムのセキュリティは崩壊し、クローン海賊版カードが蔓延する。
【０００５】
暗号の保護の確実な実行および暗号鍵の安全な保管を実現するためには、スマートカードなどの安全な不正防止ハードウェアセキュリティデバイスを使用することが推奨される。
【０００６】
スマートカードに実装される安全な暗号アルゴリズムは、数学的セキュリティをはるかに超える新規のセキュリティの問題をもたらす。今やアルゴリズムは敵の物理的支配下にあり、物理的手段による対話の無数の新規の可能性がある。スマートカードの場合、攻撃者はコード実行プロセスの物理的、電気的、磁気的、および光学的環境を測定することおよび／または混乱させることができるようになった。これらは全て、デバイスの中に隠された秘密情報と何らかのやり方で対話する追加チャネル、すなわちサイドチャネルである。それらは、この秘密情報の復元を可能にするか、あるいは秘密データを復元しなくても何らかの不正な対話を可能にする可能性のある情報を漏洩する。これらの理由で、今日では、スマートカードなど安全なハードウェアトークンのまじめなベンダは全て、様々な（物理的攻撃とも呼ばれる）サイドチャネル攻撃に対する無数のハードウェア対策およびソフトウェア対策を組み込む。
【０００７】
次のステップは、様々なサイドチャネル攻撃に対する良好な耐性を「それ自体で」有する暗号アルゴリズムを確実に設計することであって、そのための追加保護のコストはアルゴリズムの機能を実装する本質的なコストとなる。これはこれまで実行されてこなかったし、実際、誰もそれをどのように実現するか知らない。しかし、これが実行された場合、われわれは、ある程度まで、達成されたセキュリティレベルに戻る。３０年間数百人の研究者が熱心に精査してきて、しかも実用的な意味ではまだ誰も実際には破っていないトリプルＤＥＳなどよく知られているアルゴリズムの代わりに、われわれは新規のアルゴリズムを手に入れるであろうが、そのアルゴリズムは数年後に安全でないことが分かる可能性があり、そういうことは新規の暗号アルゴリズムには驚くほどよくあることである。
【０００８】
本発明で、われわれはこの欠点を回避し、ＡＥＳ（または別の標準暗号アルゴリズム）など、公開されていてよく知られているアルゴリズムと同じくらい安全なアルゴリズムを設計する。残念ながら、公開されているアルゴリズムを使用することは、サイドチャネル攻撃に対してそれをまた脆弱にする可能性がある。秘密アルゴリズムのほうが良い。
【０００９】
本発明では、われわれは、サイドチャネル攻撃に対するセキュリティと、有名な暗号規格と同じくらい安全である可能性とを同時に実現する。本発明は、一定のセキュリティ目的が達成されるようによく知られている暗号アルゴリズムを指定のやり方で新規のアルゴリズムに「組み込むこと」にある。これらのセキュリティ目的の要点は、良好なレベルの「アルゴリズムの秘密性」を達成することである。この目的は、下記で説明されるように、達成するのが決して明白ではなく、専門家によって表明された意見によれば、完全には解決されることはできず、まだ（たとえばペイＴＶまたはテレコムにおいて）対処されなければならない重要な産業問題が残っている。
【００１０】
アルゴリズムの秘密性の問題は３つの異なるレベルで見られるはずである。
１）数学では、「秘密アルゴリズム」を作り出すことはできない。知られていないビットの仕様を有するいかなるアルゴリズムも秘密であり、何らかのエントロピーを有する。このレベルでは、作り出すべきノントリビアルなことは何もない。
２）暗号学では、攻撃者がアルゴリズムと対話することができるようになるので、アルゴリズムの秘密性の表記が重要になる。何らかの部分的な情報が利用可能なので、アルゴリズムがどの程度本当に秘密であるかという複雑な問題を研究しなければならない。秘密であるアルゴリズムもあり、熟練した攻撃者によって部分的にまたは全体的に復元されることができるアルゴリズムもある。多くの場合、アルゴリズムはノントリビアルな数学的方法によって復元され、あるアルゴリズムではそのような方法は存在しないことをどのように証明するかは知られていない。期限切れのＲＳＡ暗号システムに関するＲｉｖｅｓｔ‐Ｓｈａｍｉｒ‐Ａｄｌｅｍａｎの米国特許も、暗号化アルゴリズムの秘密性に関する特許である。確かに、暗号化アルゴリズムを公開し、それでもなお復号アルゴリズムを秘密にしておく、知られている唯一の方法については、しばらくの間であった。今日まで、この目的（すなわち、公開鍵暗号化を実現すること）を達成する方法はほとんどなく、新規のものを発明することは高度にノントリビアルな仕事である。これは、アルゴリズムの秘密性は達成するのが非常に難しい目的であることを示す。
３）組み込み暗号学では、たとえば、暗号アルゴリズムがスマートカードに実装された場合、それはやはり、さらにいっそう制約された新しい世界である。この場合、セキュリティと同様に、アルゴリズムの秘密性は実現するのはさらにいっそう難しい。これは、敵がアルゴリズムの機能へのアクセスを有する場合（ポイント２参照）だけでなく、サイドチャネルが利用可能な場合にも、その秘密性は持続しなければならないからである。
【００１１】
現在では、いくつかのスマートカードは、（たとえばＧＳＭオペレータには）秘密であるアルゴリズムを使用する。しかし、どの程度まで本当に秘密なのかを見るためには、文献ではこの問題は研究されておらず、この問題に対処する解決策は何も提案されていない。
【発明の開示】
【発明が解決しようとする課題】
【００１２】
本発明の一目的は、良好なレベルのアルゴリズムの秘密性（どれほど良好かは後程説明される）および良好な暗号セキュリティを有する暗号アルゴリズムのバージョンを提供することである。
【００１３】
本発明は、任意選択の補足データを有する暗号アルゴリズムを自動的に生成する方法であって、
命令のランダムまたは擬似ランダムおよび独立シーケンス、および／または命令と任意定数の何らかの固定セットから選択されたテーブルルックアップを生成すること、ならびに
前記シーケンスを、アルゴリズムのセキュリティを処理する安全な暗号アルゴリズムと組み合わせること
を含む方法に関する。
【課題を解決するための手段】
【００１４】
用語擬似ランダムは、攻撃者にランダムに見えることを意味する。たとえば、擬似ランダムシーケンスは、擬似乱数発生器によってランダムな初期シードから得られることができる。
【００１５】
前記２つのステップの組み合わせは、ノントリビアルな技法で行われる。このため、アルゴリズムは２つの異なるゾーン、すなわち、サイドチャネル解析にさらされるアルゴリズムの外側の部分における外部アルゴリズム秘密ゾーン、およびサイドチャネル解析にさらされない内部の純粋に暗号のゾーンを含む。
【００１６】
外側の部分は、攻撃者に知られる可能性があり、したがってサイドチャネル解析にさらされるいくつかのデータを有する実行プロセスの初めの部分および終わりの部分で実行されるアルゴリズムの部分である。
【００１７】
アルゴリズム秘密ゾーンでは、アルゴリズムのコードは、命令のランダム（または擬似ランダム）および独立シーケンス、および／または（いったんアルゴリズムが生成されれば生成および定数で任意に選択される）命令と任意定数の何らかの固定セットから選択されるテーブルルックアップから局所的に作られる。命令および定数のシーケンスのランダム生成は固定かつ規定の確率分布によって行われる。この分布は一様であることを全く意味しない。各命令では、たとえば、通常、前に選択された命令のうちの前の１つまたは２つ（あるいは小さい数）に依存するその使用確率を固定する。この方法は、個々のアルゴリズムがそれぞれ、暗号の混乱を実現する多くの命令、暗号の拡散を実現する多くの命令、および電力解析攻撃によって認識するのが難しい多くの命令を含み、しかもなお、ターゲットＣＰＵ上で速度が非常に遅くかつ暗号的に弱い変換である命令をほとんどあるいは全然含まないことを確実にすることができるようにする。
【００１８】
内部暗号セキュリティゾーンは、アルゴリズムのセキュリティだけを処理しサイドチャネル攻撃から保護されなくてもよいいかなる暗号アルゴリズムまたは方法でもよい。内側の部分は外側の部分間で実行されるアルゴリズムの部分である。前記方法は、プロセッサおよびメモリを含む電子装置内で実施されてもよく、電子装置は、少なくとも、規定の特性を有する暗号アルゴリズムを生成するために使用される。この装置は、それ自体非常に多くの攻撃の目標になる可能性があるので、好ましくは安全なハードウェアデバイスであるべきである。
【００１９】
本発明によって提供される利点は非常に多い。
１．自動的かつ無人で暗号アルゴリズムを生成すること。
２．生成されるアルゴリズムの高多様性。本発明では、暗号アルゴリズムのデータが多様化されるばかりでなく、命令も多様化される。これはサイドチャネル解析に対する保護エリア内のプレミアである。
３．アルゴリズムのデータおよび命令を含むアルゴリズムの秘密性。
４．攻撃者が、多くの生成されたアルゴリズムの完全な記述からでさえ、同じ生成デバイスによって生成された他のアルゴリズムに関する攻撃者にとって有用な知識を何も得ることができないこと。
５．シードから決定論的にアルゴリズムを生成することができること。これは、生成されたアルゴリズムのデータベースを保持することを回避し、生成モジュールの（インサイダー）および攻撃者が暗号アルゴリズムを「盗む」ことができる速度を制限することができるようにする。
６．生成デバイスの使用ごとに、生成されるアルゴリズムのサイズを、ターゲットプラットフォーム上で利用可能なメモリと同じくらい大きいように、すなわちできる限り大きいように選択することができること。
７．生成デバイスの使用ごとに、生成されるアルゴリズムの速度がターゲットプラットフォームの計算能力を超えないように選択することができること。
８．現在のニーズに対して生成されるアルゴリズムの暗号セキュリティのレベルができる限り強いように、しかもなお暗号の使用に関する国内規制および輸出規制を超えないように調整することができること。
９．生成デバイスの設計時現在にのみ、ターゲットプラットフォームのサイドチャネル脆弱性に適応するように生成されるアルゴリズムの命令セットを選択することができること。
１０．アルゴリズムのセキュリティを確実にするために、暗号解読者に与えられなくてもよい暗号アルゴリズムを生成すること。
【００２０】
ポイント１、２、３、４、５、６、７および１０は、後程説明される、図１に示されている本発明をどのように実施するかの例によってすでに実現されている。目的８および９は、ユーザが割り当てられた確率で鍵のサイズおよび命令のセットを変更することができるようにする生成デバイスへの２つの追加の入力を可能にする本発明の技法を用いれば、達成するのが容易である。しかし、これは、ユーザが脆弱な暗号アルゴリズムを、（故意にまたは偶然に）、しかも検出するのが不可能でなくても難しいやり方で、生成することもできるようにするので、任意選択であり、任意選択のままであるべきである。
【００２１】
本発明の他の目的、利点および特徴は、図１では本発明による方法の異なるステップのダイヤグラムを示し、本明細書に添付された図面を参照しながら、本発明による方法実施形態、および非限定的な例として提供されたこの実施形態に適応される電子装置の実装形態の以下の説明を読むと明らかにされるであろう。
【発明を実施するための最良の形態】
【００２２】
本発明による方法の目的は、秘密データ（たとえば秘密鍵）が存在するかまたは存在しない（暗号アルゴリズムとも呼ばれる）暗号計算手順を含む何らかの暗号プロトコルを実装する電子システムまたはデバイス、たとえばスマートカードを保護することである。この保護は、別の（マスター）電子システムまたはデバイス、すなわち、他の全てのデバイス（たとえば個々のスマートカードそれぞれ）の暗号アルゴリズムを生成する前記生成デバイスによって実現される。個々の電子システムはそれぞれプロセッサなどの情報処理手段およびメモリなどの情報記憶手段を含む。それらはワイヤードロジックで実現されることもできる。以下では暗号アルゴリズムと呼ばれる暗号計算方法は、前記システムのメモリ、たとえばＲＯＭタイプにインストールされる。前記システムのプロセッサは、メモリ、たとえばＥＥＰＲＯＭタイプの秘密エリアに記憶されている秘密鍵を使用して（または使用しないで）計算方法を実行する。
【００２３】
暗号アルゴリズムを自動的に生成する本方法は、プロセッサなどのデータ処理手段およびメモリなどのデータ記憶手段を含む電子装置（マスター生成デバイス）で実施される。本方法は、前記装置のたとえばＲＯＭタイプのメモリに組み込まれる。前記装置のプロセッサは本方法を実行する。本方法はワイヤードロジックで完全に実現されることもできる。
【００２４】
本発明による方法は、前記電子システムを保護する暗号アルゴリズムを自動的に生成することからなり、図１に見られる以下の主要ステップを含む。
【００２５】
まず最初に、３つのパラメータ、すなわち、シードと、前記方法によって使用される初等関数の総数と、アルゴリズムによって使用される変数の数およびビットサイズ（たとえば１２８ビットアルゴリズムは８ビットごとに１６の変数を使用して実装されることができる）とが、前記方法の任意選択の入力として装置に導入される。
１）次いで、本方法は、提供される場合は前記シードから一連の乱数を生成することにある（ステップ１）。
２）次いで、アルゴリズムが、命令の（ある意味で）擬似ランダムシーケンスであるルーチンを生成する（ステップ２）。
３）次いで、アルゴリズムが、これらのシーケンスを集計して全単射ルーチンを形成する（このステップ３は任意選択であり、全ての暗号アルゴリズムが全単射でなければならないわけではない）。
４）次いで、ステップ４では、「暗号アルゴリズム生成」を実行する。
５）次いで、最終アルゴリズムをいくつかの所望のフォーマットに変換し、興味のある派生データを生成する（ステップ５）。
【００２６】
以下でそれぞれのステップが詳しく説明される。
ステップ１）第１ステップは初期化ルーチンを含む。任意選択の（しかし非常に有用な）要素は、本発明の装置の特性および第１（任意選択の）パラメータのストリングとして定義されるシードである。原則として、前記シードは、それをランダムビットの随意の長さのストリングに拡張するために擬似乱数発生器で使用される。代替として、シードが提供されない場合は、本プログラムで使用される任意選択性は、他のソース（たとえば内部乱数発生器）から来てもよい。本プログラムの第２パラメータは、生成されるアルゴリズムで使用されることができる初等関数の総数である（任意選択でもあり、固定でもよい）。このパラメータは、生成されるアルゴリズムのサイズ、実行速度、および暗号の複雑さを決定する。次いで、ステップ１で得られたストリングからランダムコインを取ることを除いて、完全に決定論的である（任意選択の）「全単射関数生成アルゴリズム」を適用する。出力は１つまたは複数の全単射関数である。これらの関数の逆関数（たとえば暗号化ルーチンと共に復号ルーチン）は、同時に生成されてもよい。
ステップ２）本方法は、基本命令の固定セットおよび規則の固定セットに従って擬似ランダムにまたはランダムに選択された命令のシーケンスであるルーチンを生成するアルゴリズムを実行する。命令はランダムに選択されるが、一様でなくてもよい一定の確率分布に従う、すなわち、生成デバイスをセットアップまたはパーソナライズする者は、ある命令をより頻繁に現れるように、他の命令をそれほど頻繁に現れないようにするために、ターゲットプラットフォームの命令を知る権利を有する。本方法は以下のように行われる。１つまたは複数の規則は、この命令または他の命令がこの確率で選択されること、および、どの種類の入力を使用することを許可されるかを述べる。たとえば、１つのタイプの命令では、入力は、ランダムにまたは擬似ランダムに選択され、初期変数のうちの１つか前の中間結果のうちの１つかのいずれかであるか、または前の関数による結果として得られるか、あるいはランダムにまたは擬似ランダムに選択された定数であることが明記される。命令は関数ごとにおよび場合ごとに、ある固定確率で実現される。規則は単に、上記で列挙された全ての場合に関して定義された１組の確率を指定するだけである（関数および定数の選択、ならびにそれらの順序は、ステップ１で生成された擬似ランダムストリングによって決定される）。明確な規則はまた、各関数に関して、どんな種類の引数をどんな確率で受け取るかを指定する。たとえば８ビットの足し算では、第１引数は、１任意定数あたり確率０．５であり、計算中に全ての入力変数および前の中間値の間で確率０．５で任意に選択されることを必要としてもよい。第２引数は常に中間値の１つとして選択され、１つもない場合は、初期変数が任意に選択される。
ステップ３）次いで、本プロセスは、全単射ルーチンを生成するためにステップ２からシーケンスを集計する「全単射関数生成アルゴリズム」を実行し（このステップ３は任意選択である）、これを実現する方法はまた、後ほど説明される、知られている簡単な方法の固定セットから任意に連続して選択される。出力は１つまたは複数の全単射関数である。これらの関数の逆関数は同時に生成される（任意選択）。原則として、これらの関数は秘密鍵に依存しないが、禁止されない。（別の選択肢は、関数が全単射であることを必要とせず、ステップ３をスキップする。）
ステップ４）「暗号関数生成アルゴリズム」では、本方法は、ステップ２または３で得られた１つまたは複数の関数あるいはルーチンと、（任意選択であり、別の種類の標準暗号プリミティブでもよい）ＡＥＳなど、公開して知られている安全な暗号アルゴリズムとを、連続した適用によって組み合わせることにある。鍵付きアルゴリズムの場合、原則として、ＡＥＳのようなアルゴリズムの入力、出力および鍵は全て、ステップ２からの関数の組み合わせによって変換されなければならない、あるいは、言い換えれば、ＡＥＳなど、前記鍵付きの、公開して知られていて安全な暗号アルゴリズムは、初めの部分および終わりの部分の両方において、および鍵において、他のルーチンによって内部に隠される。原則として、暗号化アルゴリズムと復号アルゴリズムの両方が生成される。一変形形態では、ステップ３なしで、本発明の方法は復号アルゴリズムを生成しない。
ステップ５）本方法の最終ステップは、最終アルゴリズムをいくつかの所望のフォーマットに変換することである。アルゴリズムは、原則として、少なくともＣまたはジャバソースコードとして出力される。興味のある選択肢は出力することも含み、参照関数的または数学的仕様も含む。さらに、自動的にテスト値を生成してもよい。たとえば、アルゴリズムのいくつかのランダム入力および鍵を選択し、得られるべき出力値を記録し、あらゆる主要ステップにおいてアルゴリズムの実行中に全ての中間値を保持してもよい。これらのテスト値は、アルゴリズムのいかなる実装のテストおよびデバッグにも使用されることができ、ＤＦＡタイプの攻撃からアルゴリズムを保護するために、計算のエラーを検出するために組み込まれたアルゴリズム全体またはその一部分のセルフテスト値として使用されることもできる。そのように保護された実装も出力されることができる。一般に、同じアルゴリズムの複数の実装が出力されてもよい。
【００２７】
ステップ３だけがさらなる説明を必要とする。
【００２８】
ステップ３はランダムに生成された関数を現在の状態で作用する全単射ルーチンに変換する。本方法は、ランダムに選択されたサブルーチンを構成することにあり、サブルーチンのうちのいくつかは、新規のまたは古い擬似ランダム置換Ｓボックスであり、他は一時に１つの現在の変数を変更し、それを他の全ての現在の変数およびランダムにまたは擬似ランダムに生成された定数の任意関数と組み合わせると定義される一般化されたフェイステル法で構成され、他のいくつかの関数も、ランダムにまたは擬似ランダムに選択されたＴ関数の大きな合成を含んでもよいパラメータと呼ばれる特別のタイプのＴ関数を現在の変数に加えるまたはＸＯＲすることによって全単射にされてもよい。
【００２９】
われわれは、以下で前記ステップ３をさらに詳細に説明した。
【００３０】
われわれは、ｌビットごとに、ｋ入力およびｋ出力で全単射関数を生成したいと考える。たとえば、ｋ＝４およびｌ＝３２である。
【００３１】
ステップ２では、われわれは、基本ＣＰＵ命令のいくつかのサブセットを選択した。それは、ＣＰＵ上で利用可能な全ての命令、Ｔ関数だけ、算術演算だけ、論理演算だけなどでよい。次いでステップ２において、これらの基本関数を組み合わせ、かつ規則によって定義された確率分布に従う関数のいくつかのランダムまたは擬似ランダムシーケンスを得る。
【００３２】
次いでステップ３において全単射関数を書くために、以下の３つの方法のうちの１つを使用することができる。
３．１．）
ｘと呼ばれるものを除いて全ての変数の任意関数を使用し、この関数の結果をグループ演算（プラス、ＸＯＲなど）によってｘに加える。これは一種の一般化されたフェイステル構成である。方法３．１．は、データ暗号化規格で使用された（そして、Ｈｏｒｓｔ
Ｆｅｉｓｔｅｌ：「Ｃｒｙｐｔｏｇｒａｐｈｙ  ａｎｄ  ｃｏｍｐｕｔｅｒ ｐｒｉｖａｃｙ」、Ｓｃｉｅｎｔｉｆｉｃ  Ａｍｅｒｉｃａｎ、第２２８巻、５号、１５〜２３ページ、１９７３年５月、に公開された）ホルスト・フェイステルの基本的な発明に由来する。全単射関数を構築するＴ関数の使用は、（Ａｌｅｘａｎｄｅｒ  Ｋｌｉｍｏｖ、Ａｄｉ  Ｓｈａｍｉｒ：Ａ  Ｎｅｗ  Ｃｌａｓｓ  ｏｆ  Ｉｎｖｅｒｔｉｂｌｅ  Ｍａｐｐｉｎｇｓ。ＣＨＥＳ  ２００２、Ｓｐｒｉｎｇｅｒ  ＬＮＣＳ  ２５２３、４７０〜４８３ページ、における）最近のＴ関数のシャミル・クリモフ理論によって多くのやり方で実現されることができる。本発明は、これらの構成に依存せず、知られているまたは将来発明されるであろう、関数を全単射関数に変換する他のいかなる方法（置換）をも使用することができる。
３．２．）
最近のシャミル・クリモフ構成を使用してもよい。ＸＯＲまたは足し算によって変数ｘを、「Ｔ関数」であり、かつ「パラメータ」である特別な種類の関数に加える。
３．３．）
（やはりステップ１から来る）いくつかの利用可能なランダムコインから擬似ランダムに前に生成された全単射代替テーブルを適用してもよい。
【００３３】
全単射関数は、これらの３つの方法のうちの１つによって定義される。各方法は、固定確率分布で任意に選択される。次いで、いくつかのそのような関数を組み合わせることができる。組み合わせる関数の総数、およびそれらのそれぞれで使用されるべき基本関数の総数は、第２パラメータを等しい部分に分割することによって決定される。
【００３４】
方法３．１．または３．２．の場合、いかなるｎに関しても、関数の総数を十分に大きいように選択した場合、生成される暗号化方式の最初のｎ命令は、任意演算およびランダム演算だけである。暗号アルゴリズムの初めの部分（および他の限定されたサイズの部分も）を調べる場合、われわれはアルゴリズムの完全な秘密性を実現する。これは、本発明の意義である。適度に「良好な」アルゴリズムの秘密性は、アルゴリズムの初めの部分および終わりの部分でその大部分の完全な秘密性を課すことによって実現される。この精密な種類のアーキテクチャはまた、実行の初めの部分または終わりの部分で作用するＤＰＡ攻撃によって動機を与えられ、これらの部分が実際によく保護されている場合は、ＤＰＡ攻撃は不可能になるはずである。
【００３５】
本発明では、生成された暗号アルゴリズムに２つのゾーンがある。すなわち、サイドチャネル攻撃から保護することを意味する秘密ゾーンである外部ゾーン、および暗号のセキュリティだけを実現する内部ゾーンである。前記内部ゾーンは、外部秘密ゾーンによって隠され、その結果、前記秘密ゾーンによってサイドチャネル攻撃から保護される。たとえば、この方法によって、ＡＥＳのセキュリティを保持し、それでもなお、危険なので、ＡＥＳ（ＡＥＳの機能）を使用する可能性を除去する。さらに、外部ゾーンではアルゴリズムの鍵は全然使用しないことが推奨される（ただし義務的ではない）。ＡＥＳは鍵の導入を実施する際にはよく注意することを必要としていて、原則として、暗号化全体をより安全にせずＤＰＡ攻撃に対してより安全でなくする可能性のある、他の所での鍵の使用は必要がない。
【００３６】
電子システムを保護するために生成される方法は、
命令のランダムまたは擬似ランダムおよび独立シーケンス、および／または命令と任意定数の何らかの固定セットから選択されたテーブルルックアップの方法の初めの部分および／または終わりの部分における計算、ならびに
前記命令のシーケンスおよび／またはテーブルルックアップの、アルゴリズムのセキュリティを処理する暗号アルゴリズムとの組み合わせの方法の真ん中における実行
を含む。
【００３７】
本発明の方法はアルゴリズムを擬似ランダムに生成することができるようにする、すなわち任意に計算されたシードがランダムなやり方でかつ決定論的にアルゴリズムを最終的に得ることができるようにする、すなわち同じシードでは、得られるアルゴリズムは同じである。
【００３８】
最先端技術の後を追うだけの「ハンドメイド」アルゴリズムと比較して、本発明は以下の利点を提供する。
ａ）あらゆる初期シードに一意で非常に異なるアルゴリズムを決定論的に生成する。
ｂ）厳格な暗号のセキュリティでは、これらのアルゴリズムは、内部にＡＥＳを組み込むので、ＡＥＳなど、よく知られているアルゴリズムと同じくらい安全である。
ｃ）さらに、これらのアルゴリズムは、少なくともサイドチャネル攻撃から保護されたＡＥＳの実装と同じくらい安全である。これは、本発明の方法によって、ＡＥＳが内部に組み込まれているにもかかわらず、実際に検証可能などんなやり方ででもこの内部のＡＥＳ機能に実際にアクセスする可能性がないからである（これは、実際、アルゴリズムの秘密性の結果である）。本発明の方法は、より良いセキュリティのために他の方法と組み合わされてもよい。アルゴリズムの秘密性は、他の対策にはない利点を有し、他の対策のセキュリティをも改善する。
ｄ）本発明のアルゴリズムは、さらに、多くのサイドチャネル攻撃に対する自然の「それ自体の」耐性を有する。これは、やはり、アルゴリズムの秘密性のためであるが、その秘密性が一定のレベルに持ってこられた場合のみである。実際、アルゴリズムが秘密であるばかりでなく、アルゴリズムの初期部分および最終部分も秘密であることを必要とし、しかも強い意味でこれを必要とする。それらは機能として再現されることができないばかりでなく、ＣＰＵによって実行されるそれらの命令も秘密である。
ｅ）本発明による方法は、３つの手法３．１．、３．２．、および３．３．、ならびに他の構成を自由に組み合わせる。
ｆ）ほとんどの暗号設計と違って、本発明による方法は、厳しい設計必要条件を有する何か非常に特別な関数または特別なＳボックスで構成をインスタンス化しないが、それらが、規定の分布内にある全ての可能なＳボックスまたは関数の間でランダムに取られなければならないことを強く主張する。
ｇ）本発明による方法は、擬似ランダム暗号アルゴリズムを生成する、しかも自動的に生成する。安全な暗号アルゴリズムを体系的にかつ決定論的に生成することは、１つのアルゴリズムだけを生成することよりはるかに難しい――それらのアルゴリズムはそれぞれが良好でなければならない。
ｈ）本方法は、暗号アルゴリズムのソースコードを調べる場合、非常に様々な暗号アルゴリズムを生成する。あらゆる良好な暗号アルゴリズムで実現されるアルゴリズムの中の内部データの擬似ランダム性を実現する代わりに、われわれは、アルゴリズムコード自体の擬似ランダム性を実現する傾向がある。さらに、この擬似ランダム性は、（本発明ではＡＥＳによって保証される）暗号のセキュリティを実現するために使用されるのではなく、アルゴリズムの秘密性を実現するために使用される。
【００３９】
本発明の実施には、いくつかの可能な拡張形態および選択肢がある。
・生成装置は、アルゴリズムで使用されるべき割り当てられた条件付き確率で命令のセットを追加入力として変更し、取ることができる。
・生成装置は、最終アルゴリズムの鍵サイズを追加入力として取ることができる。
・生成装置は、暗号アルゴリズムを提供する先のデバイスの一部分であることができる。
・生成装置は、直接または直接でなく接続される先のデバイス、および、たとえばリモートデバイスのアルゴリズムを生成してもよい。
・アルゴリズムの自動生成装置は、対応する暗号アルゴリズムを体系的に生成してもよい。
・アルゴリズム生成中の全てのランダム選択は、実際にランダムであるか、またはいかなるタイプのランダム発生器からでも行われることができる、あるいは擬似ランダムに行われ、シードから得られることができる。
・アルゴリズム秘密ゾーンの最もさらされる部分に秘密鍵の係わりを課さないことは可能であり擁護される。
・暗号化アルゴリズムの第１の鍵依存命令が、任意の長さの命令シーケンスを含むことができる一連の秘密変換の後で、暗号化プロセスの内部深くで処理されることを課すことは可能である。その場合、攻撃者は鍵依存部分の入力の知識がなく、その結果、アルゴリズムは差分電力解析（ＤＰＡ）などのサイドチャネル攻撃から保護される。
・生成装置は、テスト値が、テスト値を有するテスト暗号のランダム処理による物理的混乱（ＤＦＡ）攻撃からの保護を備えるコードを自動的に生成するために使用されるようなやり方で、実装されることができる。
・生成装置は、スマートカードまたは他の不正防止トークンを生成するかまたはパーソナライズするために使用されることができる。
・生成装置は、擬似ランダムで一時的な一意の暗号アルゴリズムを生成し、それらの実行可能なフォームをリモートデバイスに送るために使用されることができ、現在のセッションにおいて鍵共有、認証および暗号化のために使用されることができる。
【図面の簡単な説明】
【００４０】
【図１】本発明による方法の様々なステップの図である。
【図１】
2008516502.tif 000003
【国際調査報告】
2008516502.tif 000004
2008516502.tif 000005
2008516502.tif 000006