(57)【特許請求の範囲】
【請求項１】
複数の異なりかつ独立した分岐（ＳＢ１，ＳＢ２）を用いて処理ユニットにより機密計算を実行する方法であって、
各分岐は実行されるべき所定数の処理ユニット時間単位を必要とし、前記方法は、機密計算の各実行に：
−少なくとも分岐の数と同じ数の多数の識別子を生成するステップと；
−各識別子を固有の分岐に関連付けるステップと；
−識別子のランダム配置を生成する（Ｓ１，Ｓ２）ステップであって、前記配置中での各識別子の出現回数が最短分岐中の中央処理ユニット時間単位の数と少なくとも等しいステップと；
−各識別子を前記ランダム配置に処理（Ｓ３）することにより、識別子の値に従って各連続中央処理ユニット時間単位で実行する分岐を連続的に決定するステップと；
−前記ランダム配置の各識別子のために、前記識別子の値に従って決定された前記分岐用の中央処理ユニット時間単位を実行する（Ｓ１１，Ｓ２１）ステップと；を備えることを特徴とする方法。
【請求項２】
−識別子を生成するステップは、前記識別子が値とその補数値とを備え、
−ランダム配置を生成するステップは、最初に識別子として値のシーケンスを生成し（Ｓ１）、次いで、このシーケンスを前記シーケンスの補数値によって完成させる（Ｓ２）ことを特徴とする請求項１に記載の機密計算を実行する方法。
【請求項３】
前記シーケンスは、以前に生成されたシーケンス内に２つの値のうちの１つの補数値を挿入することにより完成することを特徴とする請求項２に記載の機密計算を実行する方法。
【請求項４】
前記シーケンスは、値のシーケンスの最後に補数値のシーケンスを追加することにより完成することを特徴とする請求項２に記載の機密計算を実行する方法。
【請求項５】
前記機密計算は、暗号論理アルゴリズムの異なりかつ独立した分岐を備えることを特徴とする請求項１乃至４のいずれかに記載の方法。
【請求項６】
前記機密計算は、前記複数の分岐の少なくとも１つの実行の正確性を保証するための対策再実行又は余分なコードの実行であることを特徴とする請求項１乃至５のいずれかに記載の方法。
【請求項７】
前記分岐の１つが異なる長さであって、前記方法は、平衡するために最短の分岐を追加の処理ユニット時間単位で補完させる予備ステップを含むことを特徴とする請求項１乃至６のいずれかに記載の方法。
【請求項８】
前記方法が、さらに、実行処理ユニット時間単位の数をカウントするステップを含むことを特徴とする請求項１乃至７のいずれかに記載の方法。
【請求項９】
前記方法が、さらに、前記各分岐に対し、独立に実行処理ユニット時間単位の数をカウントするステップを含むことを特徴とする請求項１乃至８のいずれかに記載の方法。
【請求項１０】
請求項１乃至９のいずれかに従って機密計算を実行する方法において、
前記機密計算は、２つの異なりかつ独立した分岐（ＳＢ１，ＳＢ２）を用い、各分岐は実行されるべき所定数の処理ユニット時間単位を必要とし、前記方法が：
−ビットの連続として乱数（Ｒ（Ｌ））を生成するステップであって、前記乱数（Ｒ（Ｌ））のビットの数は、最短の分岐中の処理ユニット時間単位の数に少なくとも等しいステップと；
−前記生成された乱数（Ｒ（Ｌ））の補数ビット（ＣＯＭＰ（Ｒ（Ｌ））を使用して前記乱数（Ｒ（Ｌ））の長さを倍増してマスタ乱数（Ｍ＿Ｒ（２Ｌ））を作成するステップと；
−前記マスタ乱数（Ｍ＿Ｒ（２Ｌ））をビット順に処理し、前記分岐（ＳＢ１、ＳＢ２）のいずれが各連続処理ユニット時間単位を実行するかを前記マスタ乱数（Ｍ＿Ｒ（２Ｌ））の各ビットの０又は１の値に従って順に決定するステップであって、各値は前記２つの分岐の１つに関連付けられているステップと；
−前記マスタ乱数の各ビット毎に、前記ビット値に従って決定された前記分岐（ＳＢ１又はＳＢ２）のために処理ユニット時間単位を実行する（Ｓ１１，Ｓ２１）ステップと；
を備えることを特徴とする方法。
【請求項１１】
両方の分岐が同一数の処理ユニット時間単位を必要とし、前記生成された乱数（Ｍ＿Ｒ（２Ｌ））が１つの分岐中の処理ユニット時間単位の数と等しいことを特徴とする請求項８に記載の方法。
【請求項１２】
さらに、前記マスタ乱数（Ｍ＿Ｒ（２Ｌ））中の走査されたビットの数をカウントするステップを含むことを特徴とする請求項８又は９に記載の方法。
【請求項１３】
複数の異なりかつ独立した分岐を使用して機密計算を実行する処理ユニット（ＰＵ）を備えたデバイス（Ｄ）であって、各分岐は実行されるべき所定数の処理ユニット時間単位を必要とし、前記デバイス（Ｄ）はさらに分岐の数と少なくとも同一数の多数の識別子を生成する識別子ジェネレータを備え、各識別子は固有の分岐に関連付けられ、前記処理ユニット（ＰＵ）は識別子のランダム配列を計算可能であって、前記配列中の各識別子の出現回数は最短の分岐中の中央処理ユニット時間単位の数と少なくとも等しく、
前記処理ユニット（ＰＵ）は、各識別子をランダム配列に処理し、前記識別子の値に従って各連続中央処理ユニット時間単位で実行する前記分岐を連続的に決定し、前記ランダム配列の各識別子に対し、前記識別子の値に従って決定した分岐のために中央処理ユニット時間単位を実行することを特徴とするデバイス（Ｄ）。
【請求項１４】
前記デバイス（Ｄ）は、２つの異なる分岐（ＳＢ１，ＳＢ２）を使用して機密計算を実行する処理ユニット（ＰＵ）を含み、各分岐は実行されるべき所定数の処理ユニット時間単位を必要とし、前記デバイスはさらにビットの連続として乱数（Ｒ（Ｌ））を発生させる乱数発生器（ＲＮＧ）を含み又は前記乱数発生器（ＲＮＧ）に接続され、前記乱数（Ｒ（Ｌ））中のビット数は最短の分岐中の処理ユニット時間単位の数の少なくとも等しく、
前記処理ユニット（ＰＵ）は所定の乱数（Ｒ（Ｌ））の補数を計算することができ、
前記処理ユニット（ＰＵ）はビット毎に前記乱数（Ｒ（Ｌ））と前記発生された乱数（Ｒ（Ｌ））の連続する補数ビットとの連続ビットをビット順に処理し、ビットとその補数とは連続してマスタ乱数（Ｍ＿Ｒ（２Ｌ））を形成し、各走査されたビットの０又は１の値に従って各連続処理ユニット時間単位によって前記分岐（ＳＢ１，ＳＢ２）のどちらを実行するかを前記マスタ乱数（Ｍ＿Ｒ（２Ｌ））の各ビットについて順次決定し、ビットの値に従って決定された分岐に処理ユニット時間単位を実行することを特徴とする請求項１３に記載のデバイス（Ｄ）。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、各分岐が実行のために所定数の処理ユニット時間単位を必要とする複数の異なりかつ独立した分岐を用いて機密計算を実行する方法に関する。
【０００２】
機密計算に、いくつかの異なりかつ独立した分岐を使用することは、サイドチャネル分析や故障攻撃に対する対策を実装する埋設デバイスにおいては一般的な方法であり、物理的な漏洩や弱点を習得する必要のあるソフトウェア又はハードウェア設計においては備えられている。本発明では、対策自身が漏洩しないことを保証することにより対策を強化することができる。
【０００３】
本発明は、現在の実装では一般的な状況である２つの分岐が使用される時に特に適用される。本発明は、また、前記方法を実装したデバイスにも関連する。
【背景技術】
【０００４】
機密計算例えば暗号論理計算中のサイドチャネル攻撃や故障攻撃によりデバイスから秘密を取り出すことは良く知られている。
このような攻撃には、タイミング測定、消費電力測定、電磁気放射測定、故障注入、等が使用される。
物理攻撃に対しては特にメモリフットプリントと実行時間に関して最小のインパクトを伴った効率的な方法を見出すことが常に望ましい。
これらの攻撃に対抗するために、保全デバイス中には埋設ソフトウェア対策が実装されている。
【０００５】
これらのソフトウェア対策は主として以下の１つ又はいくつかの方法に基づいている。
−機密値からの信号を相関させないように機密データを乱数によってマスクする；
−ソフトウェアコードのどの分岐を取らなければならないかを知る可能性を取り消すために機密処理をマスクする；
−実行の正確性を保証するいくつかの余分のコードを追加する。通常、機密性の高い操作又は一貫性のある制御を伴う一貫した余分のコードを再実行する。
−攻撃の状況に対応する実行ループの場合に実行を非同期にするための余分なコードを追加する；
−計算を２倍にする；
−逆操作を行う；
−いくつかの偽の操作を追加する。
【０００６】
一般的に、このような対策の実装は、ＲＡＭ／ＲＯＭフットプリントと実行時間の点で高価となる。
本発明による機密計算では、計算は２つの異なりかつ独立した分岐によって構成される。一般に、機密分岐の一つが最初に実行され、次いで二番目が実行される。
実行される計算のブール又は算術特性に応じて、サイドチャネル攻撃を回避し、中間結果の一貫性をクロスチェックするために、例えば、ＤＥＳ（相補Ｍ、相補Ｋ）の相補に等しいＤＥＳ(Ｍ，Ｋ)計算の場合には、このような機密計算の処理をマスクする必要が確かに存在する。
したがって、さらなる代替的かつ有利な解決方法が当該技術分野で望ましいであろう。
【発明の概要】
【０００７】
本発明は上述した悪意の攻撃を回避又は少なくともより困難化させることを目的とする。
本発明は、最も広い意味で、複数の異なりかつ独立した分岐を用いて処理ユニットにより機密計算を実行する方法であって、
各分岐は実行されるべき所定数の処理ユニット時間単位を必要とし、前記方法は、機密計算の各実行に：
−少なくとも分岐の数と同じ数の多数の識別子を生成するステップと；
−各識別子を固有の分岐に関連付けるステップと；
−識別子のランダム配置を生成するステップであって、配置中での各識別子の出現回数が最短分岐中の中央処理ユニット時間単位の数と少なくとも等しいステップと；
−各識別子をランダム配置に処理することにより、識別子の値に従って各連続中央処理ユニット時間単位で実行する分岐を連続的に決定するステップと；
−ランダム配置の各識別子のために、識別子の値に従って決定された前記分岐用の中央処理ユニット時間単位を実行するステップ、として定義される。
【０００８】
従って、本発明の方法は、悪意の攻撃のリスクを削減するのに資する。少なくとも、攻撃はより複雑で、悪意の攻撃者のために実行される。機密計算の各実行でランダムに識別子を生成することにより、特に、分岐の異なるシーケンスに常に供される中央処理ユニットの処理サイクルにおいて、処理時間単位のシーケンスを持つことができる。
各時間単位の終了時及び各分岐毎にループの中間結果を格納するためにメモリが使用される。各分岐のリバースエンジニアリングは、その実現が他の分岐ユニットと混在するため、より困難となる。
【０００９】
ＲＡＭフットプリントの点では、本発明の実現は、各分岐の直接的な実行よりも少しコストがかかるが、実装を安全にするためには全く同じである。ＲＯＭフットプリントの点では、本発明の実現は単純で有利である。何故なら例えば、一時レジスタやループインデックスのようないくつかの変数は複数の分岐で共有できるからである。
【００１０】
さらに、注目すべきは、本発明は最適なコードフットプリントで構築することが容易なことである。実際、分岐ユニットのコードは本発明によって変更されず、どんな変更が呼び出され分割されるかである。
各分岐とそのユニットとを適格化するインデックスを含むバッファから分岐ユニットの連続を構成するわずかな命令で、正確性を保証しながら、それを利用することは容易である。
【００１１】
本発明は、各実行において、異なりかつ予測不可能な分岐のランダムな順序実行を得ることを可能とする。本発明は識別子の値に応じて分岐を選択し、好ましくは、各分岐が完全に動作するよう制御することにより、構築によって保証されるランダムな種である各分岐の識別子の存在から平衡したマスタ乱数を構築し、わずかな余分のコードを使ってこの目標に到達したものである。
本発明は、独立し、異なる分岐の実行を高効率で完全に混合する可能性を開くものである。この対策の品質はフットプリントと機能の点でさらに高度である。
【００１２】
好ましい実施例によると、識別子を生成するステップは、識別子が値とその補数値とを備え、ランダム配置を生成するステップは、最初に識別子として値のシーケンスを生成し、次いで、このシーケンスをシーケンスの補数値によって完成させる。
ランダム配列のこの特定の構造は、生成されるランダムシーケンスのサイズを小さくすることができる。また、各分岐に供されるサイクル数を同一となるよう保証する。
【００１３】
この実施例の第１の実装において、シーケンスは、以前に生成されたシーケンス内に２つの値のうちの１つの補数値を挿入することにより完成する。
代表的には、補数値は２つの値の１つがここで挿入される。これは本発明の目標に到達するために簡単な方法で最終配列を構成することを可能としている。
【００１４】
この実施例の第２の実装において、シーケンスは、値のシーケンスの最後に補数値のシーケンスを追加することにより完成する。
この方法では、最初に値に対応する第１セットの分岐の、次いで補数値に対応する第２セットの分岐の実行が行なわれる。
好ましい適用として、機密計算は、暗号論理アルゴリズムの異なりかつ独立した分岐を備える。
【００１５】
本発明は、特に、機密データを操り、性能に関して最適化される必要があるアルゴリズムを保護するよう適合される。
特に興味深い適用として、機密計算は、複数の分岐の少なくとも１つの実行の正確性を保証するための対策再実行又は余分なコードの実行である。
そのような対策は、暗号アルゴリズムでしばしば使用される。しかし、現在の実装では、それらは攻撃の場合に一般的に漏洩する。本発明をいくつかの独立し、異なる分岐を用いる対策に適用することにより、そのような漏洩を防止することができる。
【００１６】
有利な特徴によれば、分岐の１つが異なる長さであって、前記方法は、平衡するために最短の分岐を追加の処理ユニット時間単位で補完させる予備ステップを含む。
このような予備的なステップにより、全ての分岐での全ループセットに本発明の適用を可能とするＣＰＵサイクルに関して、各分岐で同一長を有することが可能となる。
【００１７】
特定の特徴によれば、前記方法が、さらに、実行処理ユニット時間単位の数をカウントするステップを含む。
このような特徴は、各分岐において時間ユニット数の和に対応する数の時間ユニットが到達したことを機密計算の終了時にチェックすることを可能とする。
【００１８】
その他の本発明の特徴によれば、前記方法が、さらに、各分岐に対し、独立に実行処理ユニット時間単位の数をカウントするステップを含む。
この特徴は、各分岐を独立して追跡することを可能とする。
コードの一部を飛ばすことを可能にするフォールト攻撃を検出できれば便利である。これは、分岐が実行されるたびに、いくつかの異なるトレーサをインクリメントすることにより行うことができる。すべての分岐の実行後に時間の正確な数を検出することは容易である。コードの一部をジャンプするのに成功したどんなフォールト攻撃であっても検出される。
【００１９】
好ましい実施例では、機密計算を実行する方法において、前記機密計算は、２つの異なりかつ独立した分岐を用い、各分岐は実行されるべき所定数の処理ユニット時間単位を必要とし、前記方法が：
−ビットの連続として乱数を生成するステップであって、乱数のビットの数は、最短の分岐中の処理ユニット時間単位の数に少なくとも等しいステップと；
−生成された乱数の補数ビットを使用して乱数の長さを倍増してマスタ乱数を作成するステップと；
−マスタ乱数をビット順に処理し、前記分岐のいずれが各連続処理ユニット時間単位を実行するかを前記マスタ乱数の各ビットの０又は１の値に従って順に決定するステップであって、各値は前記２つの分岐の１つに関連付けられているステップと；
−マスタ乱数の各ビット毎に、前記ビット値に従って決定された前記分岐のために処理ユニット時間単位を実行するステップと；を備える。
【００２０】
この実施例は、機密計算に２つの分岐のみを使用している共通の状況に対応している。配列として使用されるマスタランダムの構成はオリジナルで、非常に有利である。何故なら最短分岐における時間ユニットの数のサイズの半分のサイズの乱数を生成を必要とするだけで、両方の分岐では必要とされる時間単位のすべてのセットが処理されることが保証されるからである。
【００２１】
有利な実施例では、両方の分岐が同一数の処理ユニット時間単位を必要とし、生成された乱数が１つの分岐中の処理ユニット時間単位の数と等しい。
この実施例は、分岐が同一サイズのケースに対応する。
【００２２】
有利な特徴によると、さらに、マスタ乱数中の走査されたビットの数をカウントするステップを含む。
この特徴は、すべての機密計算の実行を追跡する非常にシンプルな方法である。
【００２３】
本発明はまたデバイスに関する複数の異なりかつ独立した分岐を使用して機密計算を実行する処理ユニットを備えたデバイスであって、各分岐は実行されるべき所定数の処理ユニット時間単位を必要とし、デバイスはさらに分岐の数と少なくとも同一数の多数の識別子を生成する識別子ジェネレータを備え、各識別子は固有の分岐に関連付けられ、処理ユニットは識別子のランダム配列を計算可能であって、配列中の各識別子の出現回数は最短の分岐中の中央処理ユニット時間単位の数と少なくとも等しく、
処理ユニットは、各識別子をランダム配列に処理し、識別子の値に従って各連続中央処理ユニット時間単位で実行する分岐を連続的に決定し、ランダム配列の各識別子に対し、識別子の値に従って決定した分岐のために中央処理ユニット時間単位を実行する。
【００２４】
本発明を実施することのできるデバイスは、機密計算のいくつかの実行中に攻撃者によって相関が行なわれないので、攻撃に対する大きな保護が与えられる。
実行されたコードのリバースエンジニアリングも古典的なアプローチに比し困難である。さらに、仮にコードが読み出しのためにアクセスが可能であったとしても、最終的な実行が何であるかは明らかとならない。
【００２５】
好ましい実施例では、デバイスは、２つの異なる分岐を使用して機密計算を実行する処理ユニットを含み、各分岐は実行されるべき所定数の処理ユニット時間単位を必要とし、デバイスはさらにビットの連続として乱数を発生させる乱数発生器を含み又は乱数発生器に接続され、乱数中のビット数は最短の分岐中の処理ユニット時間単位の数の少なくとも等しく、
処理ユニットは所定の乱数の補数を計算することができ、
処理ユニットはビット毎に乱数と発生された乱数の連続する補数ビットとの連続ビットをビット順に処理し、ビットとその補数とは連続してマスタ乱数を形成し、各走査されたビットの０又は１の値に従って各連続処理ユニット時間単位によって分岐のどちらを実行するかをマスタ乱数の各ビットについて順次決定し、ビットの値に従って決定された分岐に処理ユニット時間単位を実行する。
【００２６】
この実施例は、２つの独立し、かつ異なる分岐がアルゴリズム中で使用されている共通のケースに対応している。
前述の目的および関連する目的を達成するために、１つ又は複数の実施形態は以下で十分に説明され、特に特許請求の範囲において指摘される特徴を備える。
【図面の簡単な説明】
【００２７】
以下の詳細を説明と添付図面には、詳細に特定の例示的な態様が述べられており、実施形態の原理が採用されているほんのわずかな種々の方法が示されている。
【００２８】
【図１】本発明の方法を示すフローチャートである。
【図２】本発明のデバイスを示す概略図である。
【発明を実施するための形態】
【００２９】
本発明のより完全な理解のために、添付図面を参照して本発明を詳細に説明する。詳細な説明では、本発明が実施される際の本発明の好適と考えられる実施例、即ち、機密計算が２つの独立し、かつ異なる分岐で行なわれている状況が図示されて説明される。本実施例は当業者による本発明の実施を可能とするよう十分に詳細に説明される。
【００３０】
もちろん、フォーム又は詳細の種々の変更や変形は本発明の範囲から逸脱することなく容易に行うことができることは理解されるべきである。特に、特許請求の範囲での参照符号は、特許請求の範囲に規定された本発明の範囲を限定するように解釈してはならない。「含む（comprising）」という表現は他の要素やステップが含まれるのを排除するものではない。「１つ（ａ又はａｎ）」という表現は複数を排除するものではない。分かりやくすするために、本発明の理解に有用な要素とステップのみを図面に示し、説明する。
【００３１】
図１は、２つの異なり、かつ独立の分岐ＳＢ１，ＳＢ２を使用して機密計算を実行する本発明の方法を概略的に示したものである。図１に示す例では、分岐は処理単位サイクル数と同じ数である所定数Ｌを必要とする。２つの分岐が同じサイクル数を必要としないときには、短い分岐は同じサイクル数になるように非特定の操作を行って終了することが好ましい。さもなければ図１において、Ｌは最短分岐が必要とするサイクル数である。最長分岐の残りのサイクルは、本発明の実行方法が終了した後に行なわれる。
【００３２】
このような機密計算の一例は、暗号論理アルゴリズムであって、その構造は、２つの異なり、かつ独立した分岐によって構成されており、代表的にはＲＩＰＥＭＤ１６０ハッシュアルゴリズム、等がある。また実行の正確さを保証するために同等の余分なコードを返すか実行する対策もあり、代表的には、ＤＥＳ／〜ＤＥＳアルゴリズム、ＭｉｘＡＥＳ暗号化／解読化，Key Sheduling of Masked Data, then Mask,等がある。各分岐は同一データでは動作しないので異なっており、一方の分岐での計算は他方の分岐では使用されないので独立している。
【００３３】
ここでは、分岐の独立性が必要であることに注意すべきである。独立していないと、２つの分岐は互いに依存し、本発明で要請される実行の完全な配列が不可能となる。事実、本発明では、２番目の分岐が実行される前に分岐の１つを完全に実行する可能性がなければならない。従って分岐間の依存は排除される。
【００３４】
第１ステップＳ１で、長さＬの乱数Ｒが生成される。第２ステップＳ２で、乱数Ｒ（Ｌ）はその補数ビットにより完成する。図１にはＣＯＭＰＬ（Ｒ（Ｌ））として示してある。このようにして、長さ２Ｌを持つマスタ乱数Ｍ＿Ｒが得られる。
【００３５】
次いで、マスタ乱数Ｍ＿Ｒの連続する各ビットｉが図１に概略的に示すように順次処理される。ステップＳ３でビット１から始めてビット２Ｌまで、現在のビットＭ＿Ｒ（２Ｌ）ｉが０と等しいか否かがチェックされる。等しい場合（ケースＹ）には、ステップＳ１１で、第１分岐ＳＢ１の動作を行う処理ユニットサイクルループが使用される。そして、、マスタ乱数のビットの指標（インデックス）がステップＳ１２で増加する。等しくない場合（ケースＮ）には、ステップＳ２１で、第２分岐ＳＢ２の動作を行う処理ユニットサークルループが使用される。
【００３６】
そしてマスタ乱数のビットの指標がステップＳ２２で増加する。マスタ乱数Ｍ＿Ｒはその構造から０と１とが等しく含まれているため、２つの分岐が均等に選択されることを保証する。
ステップ４で、ｉの値が２Ｌの値に達したかが判定される。達していれば（ケースＹ）、機密計算の実行は終了する。達していない場合（ケースＮ）、ステップＳ３に戻り、ｉ番目のビット値がチェックされる。
【００３７】
図２は、本発明のデバイスＤを概略的に示したもので、処理ユニットＰＵを含んでいる。この処理ユニットＰＵは、中央処理ユニットＣＰＵ又はハードウェアコプロセッサとすることができ、典型的には暗号プロセッサタイプの１つである。
本発明を適用するために、処理ユニット１は２つの異なる分岐を用いて機密計算を実行するよう意図されており、各分岐は実行されるべき所定数の処理ユニットサイクルを必要とする。
デバイスＤは、さらに乱数発生器ＲＮＧを含んでいる。本発明の他の変形例では、デバイスＤは乱数発生器ＲＮＧを自身には含まず、必要時に乱数を取得する発生器ＲＮＧに接続されていてもよい。このため、図中ＲＮＧは点線で示されている。
【００３８】
機密計算の実行が起動されると、処理ユニットＰＵは要請ＲＥＱを乱数発生器ＲＮＧに送る。乱数発生器ＲＮＧは連続したビットとして乱数Ｒ（Ｌ）を発生し、乱数Ｒ（Ｌ）のビット数は、最短分岐中の処理ユニットサイクル数（Ｌ）に少なくとも等しい。乱数Ｒ（Ｌ）は次いで、処理ユニットＰＵに伝送される。
処理ユニットＰＵは連続したＬビットを有する乱数Ｒ（Ｌ）のビットの補数により所定の乱数の２の補数をＣＯＭＰ（Ｒ（Ｌ））として計算することができる。この連続したビットと補数とにより前述のマスタ乱数Ｍ＿Ｒ（２Ｌ）を形成する。
【００３９】
次いで、処理ユニットＰＵは、ビット順に、マスタ乱数Ｍ＿Ｒ（２Ｌ）の連続ビットを処理し、前述した本発明の方法の原理に従って、順にいずれの分岐ＳＰ１又はＳＰ２が各連続処理ユニットサイクルにより実行するのかを各走査ビットの０又は１の値に従って順次決定する。
マスタ乱数Ｍ＿Ｒ（２Ｌ）の各ビット毎に、ビット値に従って決定された分岐の処理ユニットサイクルを実行する。
【００４０】
２つの分岐を有する機密計算の場合、各分岐は１６ループで構成され、以下に対策の擬似コードの例を示す。
// 16ビットの乱数
Val_16Bits<=Random Value of 16 bits
// Val_16ビットと補数ビット値Val_16ビットの連結により構成される32ビット。この構造はすべての反復が実行されることを保証する。
MasterRNG_32Bits <= Val_16Bits | 〜(Val_16Bits)
（このステップで‘〜’演算子は値の２の補数を計算し、‘|’は２つの変数の連結を表わす）
bLoopTreatment_1=bLoopTreatment_2=0
For Loop = 0 to (16+16)
-if Bit(MasterRNG_32Bits) == 1
-Execute sensitive branch 1(in random order)
-Increment (bLoopTreatment_1,1)
-if Bit(MasterRNG_32Bits) == 0
-Execute sensitive branch 2(in random order)
-Increment (bLoopTreatment_2,1)
-go to next bit of MasterRNG_32Bits
//一貫性を制御する
-All bits of MasterRNG should be treated:
if not ErrorDetected()
-Loop == 32 ?
if not ErrorDetected()
-bLoopTreatment_1 == 16 ?
if not ErrorDetected()
-bLoopTreatment_2 == 16 ?
if not ErrorDetected()
【００４１】
機密計算の各実行時に、マスタＲＮＧの乱数値を取上げることにより、機密第１分岐と機密第２分岐の実行の順序は推測することは出来ない。マスタ乱数の構成により、すべての機密計算が実行される。同数のＣＰＵサイクルを必要とするよう分岐が平衡していると、効果的に取上げられた分岐は偵察されることはない。各機密分岐で異なる実行カウンタをインクリメントすることにより、正確性を保証するための複数のテストを簡単に実行できる。
これらのテストには、マスタ乱数のすべてのビットが取扱われたかのテスト、グローバルループインデックスが各分岐に必要とされるＣＰＵサイクルの合計であったかのテスト、各分岐カウンタが必要とされるＣＰＵサイクルであったかのテスト、等が含まれる。
【００４２】
次に、複数の分岐についての一般化の例を以下に示す。本発明の方法によると、分岐の数として少なくとも多数の識別子が生成される。これらの識別子は、それぞれ分岐の１つに関連付けられる。
好ましくは、可能な限り識別子は値と補数値として構成される。分岐の数が奇数の時は、完了していない識別子が作成されるか、偽の計算で分岐が追加される。
【００４３】
例えば４分岐の場合、識別子は、00, 01, 10, 11である。
分岐は次のように関連付けられる：
Ａ=>00，Ｂ=>01，Ｃ=>10，Ｄ=>11
【００４４】
次いで、本発明の方法は、各識別子の出現数が最短の分岐の中央処理ユニット時間単位と同じである２つの第１の識別子00，01のシーケンスをランダムに決定するステップを含む。
そして、補数シーケンスを計算する。この補数シーケンスは、第１のシーケンスに加えられるか又は第１のシーケンスに織り込まれる。次いで補完されたシーケンスが計算される。
【００４５】
この補完されたシーケンスは第１のシーケンスの最後に追加されるか、又は第１のシーケンスに織り込まれる。同等な方法では、すべての識別子を最短の分岐での時間ユニットの出現数と同じだけパックする。好ましくは、分岐はすべてが同一長となるよう前もって完成させるのが良い。例えば、すべての分岐で３ＣＰＵ時間単位のときは：00 00 00 01 01 01 10 10 10 11 11 11となる。次にランダム列が行なわれる。
例えば、4, 0, 10, 6, 5, 8, 11, 2, 3, 7, 1, 9で、これを識別子のパックに適用する。即ち（00 00 00 01 01 01 10 10 10 11 11 11）に適用すると、（01 00 11 10 01 10 11 00 01 10 00 11）となり、これが本発明におけるマスタ乱数となる。
【００４６】
次に、識別子はマスタ乱数から読み出され、処理ユニットは対応する分岐でＣＰＵ時間単位を実行する。マスタ乱数（01 00 11 10 01 10 11 00 01 10 00 11）から、次のような分岐のシーケンスが得られる：ＢＡＤＣＢＣＤＡＢＣＡＤ。
好ましい実施例では、２つの分岐が使用されており、生成される識別子は最もシンプルな０，１である。
【００４７】
結論として、本発明は機密処理の少なくとも２つの分岐での正確で完全な実行を予測不可能な方法で保証するソフトウェアでの対策に関するものである。
事実、この対策を講じることにより、どの分岐が先験的に行なわれるかを知る可能性はなく、デバイスを例えば、サイドチャネル搾取により覗き見ることによりどの分岐が実効的に行なわれているかを知る可能性もない。この対策は、すべての機密処理、即ち、すべての分岐が実効的に実行されていることを保証する。またこの対策は、いくつかの機密分岐の実行を完全に混在させる可能性を開く。
【００４８】
開示した実施例中での個々の素子の位置や配列は本発明の範囲から逸脱することなく変更可能であることに理解すべきである。
従って、上述した詳細な説明は、本発明の範囲を制限するものではなく、本発明の範囲は添付の請求の範囲によってのみ規定されるものであり、請求の範囲が資格を有する均等物の全範囲をカバーするように適切に解釈されなければならない。
【図１】
0006339295.tif 000002
【図２】
0006339295.tif 000003