(57)【要約】      （修正有）【課題】秘密鍵または個人鍵をもつ暗号電子アセンブリまたはシステムの、すべてのｎの値についての「ｎ次のＤＰＡ」攻撃のリスクをなくす。【解決手段】秘密鍵を使用してメモリ中に記憶される暗号計算プロシージャを実装する、プロセッサおよびメモリを含む電子システムのためのセキュリティ保護を行う方法であって、前記プロシージャについての少なくとも１つのクリティカル関数の入力または出力中の中間結果をマスキングすることから成る。【選択図】図１ａ
2011101413.tif 000002
【特許請求の範囲】
【請求項１】
秘密鍵を使用する暗号計算プロシージャを使用した電子システムについてのセキュリティ保護を行う方法であって、クリティカル関数が、マスキングされない中間結果を出力で提供し入力で受け取るように前記プロシージャの少なくとも１つのクリティカル関数の入力または出力中の中間結果をマスキングすることを特徴とする方法。
【請求項２】
同じ計算を行うが入力または出力中で結果がマスキングされる前記プロシージャのクリティカル関数についての置換関数を含むことを特徴とする請求項１に記載の方法。
【請求項３】
置換関数を順序づけて前記プロシージャの入力および出力についてのマスキングされない結果を提供することから成ることを特徴とする請求項１または２に記載の方法。
【請求項４】
関係するクリティカル関数による異なるマスクを使用することから成ることを特徴とする請求項１から３のいずれか一項に記載の方法。
【請求項５】
入力がマスキングされる結果に対する置換関数が、以下の演算、すなわち、
公開ではないマスキング演算、
クリティカル関数と同じ計算を行うが結果がマスキング関数を使用してマスキングされる演算
に基づいて構築されることを特徴とする請求項２に記載の方法。
【請求項６】
出力がマスキングされるデータに対する置換関数が、以下の演算、すなわち、
クリティカル関数と同じ計算を行うがマスキング関数によってマスキングされる必要がある結果に対する演算、
非公開のマスキング関数
に基づいて構築されることを特徴とする請求項２に記載の方法。
【請求項７】
マスキング関数の演算をランダムな方法で順序づけることから成ることを特徴とする請求項５または６のいずれか一項に記載の方法。
【請求項８】
秘密鍵を使用する暗号計算プロシージャを記憶する手段と、前記計算プロシージャを実行する手段とを備える電子システムであって、クリティカル関数がマスキングされない中間結果を出力で提供し入力で受け取るように前記プロシージャの少なくとも１つのクリティカル関数の入力または出力中の中間結果をマスキングする手段を備えることを特徴とする電子システム。
【請求項９】
中間結果についてのマスキング手段、およびクリティカル関数による、マスキングされる前記結果を伴う計算が、Ｓ−ボックスから作られることを特徴とする請求項８に記載の電子システム。
【請求項１０】
プログラムが電子システム中で実行されるときに請求項１から７のいずれか一項に記載の方法のステップを実行するプログラムコード命令を含むコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、秘密鍵を使用した暗号アルゴリズムを含む電子アセンブリを安全に守る方法に関する。より詳細には、本方法は、計算の実行中に電子アセンブリの電力消費を調査した後に秘密鍵についての情報を取得しようとする（高次電力差分解析（Ｈｉｇｈ−Ｏｒｄｅｒ  Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ）と呼ばれる）一部のタイプの物理攻撃による攻撃が不可能となるアルゴリズムのバージョンを実現することを目指すものである。
【背景技術】
【０００２】
ここで考慮される暗号アルゴリズムでは、秘密鍵を使用して入力情報に従って出力情報が計算される。すなわち、これらは、符号化演算、復号化演算、署名演算、署名の検査演算、認証演算、または否認防止演算でもよい。これらは、入力と出力とを知っている攻撃者が、この秘密鍵それ自体に関する情報を実際上何も推論できないようにするために行われる。
【０００３】
したがって、これは、秘密鍵をもつ表現アルゴリズムまたは対称アルゴリズムによって古典的に指定されるものに比べて大きなカテゴリの問題である。特に、本特許出願で説明するものはどれも、公開鍵または非対称アルゴリズムを伴うと言われるアルゴリズムにも適用され、これらは実際のところ２つの鍵、すなわち一方は公開鍵、他方は公開されない秘密鍵を有しており、この後者の秘密鍵が、以下で説明する攻撃の対象となっている。
【０００４】
電力解析タイプの攻撃は、実際に攻撃者が、計算を実行するときに、例えばマイクロコントローラの電力消費または回路によって生成される電磁放射として単なる入力および出力の放出以外の情報を獲得することができるという事実に起因している。
【０００５】
電力消費差分解析は、短縮してＤＰＡと言う電力差分解析（Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ）と呼ばれる攻撃のカテゴリについての原理であり、同じ鍵を用いて多数回、計算する間になされる電力消費の記録を統計的に解析することによって電子アセンブリ中に含まれる秘密鍵についての情報を取得することを可能にするものである。
【０００６】
「１次のＤＰＡ」または混同する可能性がないときに単に「ＤＰＡ」と呼ばれる最も簡単な攻撃では、攻撃者は、電流消費信号を記録し、各瞬間におけるこの信号についての個別の統計的特性を計算する。ここでは、発明者らは、「１次のＤＰＡ」攻撃を一般化した、短縮してＨＯ−ＤＰＡと言う高次電力差分解析（Ｈｉｇｈ−Ｏｒｄｅｒ  Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ）と呼ばれる攻撃のことを考えている。すなわち、攻撃者は、今では、いくつかの異なる時点で取られた電力消費の総合統計的特性を計算することになる。より詳細には、ｎ次のＤＰＡ攻撃では、暗号アルゴリズムの計算中に現れる、ｎ個の異なる中間値に対応する消費信号のｎ個の値が考慮に入れられる。攻撃によって検出される中間値のことを、以下のテキストでは、クリティカル情報と呼ぶことにする。
【０００７】
非限定的な例として、参照として述べられている文献、ＦＩＰＳ  ＰＵＢ  ４６−２、  Ｄａｔａ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｔａｎｄａｒｄ、１９９４年に記載されているＤＥＳ（Ｄａｔａ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｔａｎｄａｒｄデータ暗号化規格）アルゴリズムの場合を考慮している。
【０００８】
ＤＥＳアルゴリズムは、ラウンドと呼ばれる１６ステップで実行される（図２参照）。１６ラウンドのそれぞれで、３２ビットを用いた変換ｆが行われる。この変換ｆは、それぞれＳ−ボックス（Ｓ−ｂｏｘ）（図２上のＳ）と呼ばれるテーブル中で符号化される、８個の４ビットにわたる６ビットの非線形変換を使用している。
【０００９】
ＤＥＳに対する２次のＤＰＡ攻撃は、以下のように実行することができる。
【００１０】
第１のステップでは、消費測定が、１０００回のＤＥＳ計算について第１ラウンドの間で行われる。Ｅ［１］、．．．、Ｅ［１０００］は、これら１０００回の計算についての入力値であることに留意すべきである。Ｃ［１］、．．．、Ｃ［１０００］は、これらの計算を行う際に測定される電力消費の１０００本の対応する曲線であることに留意すべきである。
【００１１】
第２のステップでは、それぞれ値ｂ１およびｂ２をもつ（クリティカル情報である）２ビットがこの計算中に現れ、
【数１】
2011101413.tif 000003
が第１ラウンドの間に第１のＳ−ボックスからの第１の出力ビットの値ｂに等しくなるように想定することにする。ここで、
【数２】
2011101413.tif 000004
は、ビットごとの「排他的論理和」関数を示す。ｂ１に対応する消費曲線ポイントが存在する時間とｂ２に対応する消費曲線ポイントが存在する時間との間に、δの時間間隔があると想定する。次いで、各曲線Ｃ［ｉ］（式中ｉは、連続的に１、２、．．．、１０００に等しくなる整数）に対して、Ｃ［ｉ］と、Ｘ軸に沿ってδ値だけ平行移動することによってＣ［ｉ］から得られる曲線との間の差に等しい他の曲線Ｃδ［ｉ］を関連づける。１０００本のＣδ［ｉ］曲線の平均ＣＭ曲線についても計算する。
【００１２】
第３のステップでは、ｂは、その秘密鍵のうちの６ビットにしか依存しないことを理解するのは、容易である。この攻撃者は、この６ビットに関するある想定を行う。この攻撃者は、これらの６ビットおよびＥ［ｉ］から、ｂについて予想される理論値を計算する。これによって、１０００個の入力Ｅ［１］、．．．、Ｅ［１０００］を、ｂ＝０をもたらすものとｂ＝１をもたらすものの２つのクラスに分けることが可能になる。
【００１３】
第４のステップでは、次いで、ｂ＝０（ｂ＝１）となる第１のクラス（第２のクラス）の入力に関するＣδ［ｉ］曲線のＣＭ’（ＣＭ”）平均値の計算が行われる。ＣＭ’とＣＭ”の間に大きな差が示される場合、その鍵の中のその６ビットについて採用された値、ならびにδ値の選択が正しいものであったと考えられる。ＣＭ’とＣＭ”の間に統計的な意味であまり大きな差が示されない場合、すなわち、測定されたノイズについての典型的なオフセットに比べて明らかに大きな差がない場合には、この６ビットについての別の選択肢を用いて第２のステップを再開する。鍵の６ビットについて有効な選択がない場合には、δについて別の選択を用いてステップ３およびステップ４を再開する。
【００１４】
第５のステップでは、「排他的論理和」が第２のＳ−ボックスからの場合にそこからの２ビットを用いてステップ２、ステップ３、およびステップ４を反復し、次いで、第３のＳ−ボックス、．．．、第８のＳ−ボックスに至るまで繰り返す。このようにして、最終的にその秘密鍵の４８ビットが取得される。
【００１５】
第６のステップでは、その残りの８ビットを完全探索を使用して見出すことができる。
【００１６】
理論的に、ｎ次のＤＰＡでは、各命令ごとの個々の電力消費、または各命令ごとの時間的な位置についてのどのような知識も必要とされない。この攻撃者が一部のアルゴリズムの出力およびその対応する消費曲線について知っていると想定されるときにも、ｎ次のＤＰＡは同様に適用される。ｎ次のＤＰＡは、以下の基本的な仮説に基づいているだけである。
【００１７】
すなわち、仮説とは、２つの入力、およびそのそれぞれの２つに対する出力が、これらのｎ個の変数の知られている関数について同じ値をもたらすか否かを判定できるようにする、実際には３２ビット未満の数ビットの鍵ビットの知識など、アルゴリズム計算中に現れる１組のｎ個の中間変数が存在するというものである。
【００１８】
「１次のＤＰＡ」攻撃に抵抗するように設計されたものを含めて通常の実施形態の態様では、一般に前述の仮説が成立したままなので、ＤＥＳなど、Ｓ−ボックスを使用するすべてのアルゴリズムは、「高次のＤＰＡ」による攻撃を受けやすい可能性がある。
【００１９】
実際には、このインストレーションでは、考慮されるｎ個の変数に対応する消費曲線ポイント間の時間間隔を（完全探索、または他の情報の知識、例えば暗号アルゴリズムの実装の詳細の知識を用いて）見出すことも必要になる。
【先行技術文献】
【非特許文献】
【００２０】
【非特許文献１】ＦＩＰＳ  ＰＵＢ  ４６−２、  Ｄａｔａ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｔａｎｄａｒｄ、１９９４年
【発明の概要】
【発明が解決しようとする課題】
【００２１】
本発明の一目的は、秘密鍵または個人鍵をもつｎ個のセットまたは暗号電子システムの、すべてのｎの値についての「ｎ次のＤＰＡ」攻撃のどのようなリスクもなくすることである。
【００２２】
本発明の他の目的は、前述の基本的な仮説がもはや正しいことが確認されないような、すなわち、１組のｎ個の中間変数のいずれの知られている関数も、秘密鍵または個人鍵の簡単にアクセス可能なサブセットの知識に依存しないような、暗号電子システムについての保護を与えることであり、したがって「高次のＤＰＡ」攻撃を動作不可能にすることである。
【課題を解決するための手段】
【００２３】
本発明は、秘密鍵を使用してメモリ中に記憶される暗号計算プロシージャを実装する、プロセッサおよびメモリを含む電子システムのためのセキュリティ保護を行う方法であって、そのクリティカル関数が、マスキングされない中間結果を出力において提供し入力において受け取るように、そのプロセッサを用いて実行される前記プロシージャの少なくとも１つのクリティカル関数の入力または出力の中間結果をマスキングすることから成ることを特徴とする方法に関する。
【００２４】
本発明の他の目的、利点、および特徴は、ここに添付された図面を参照して非限定的な例として提供された本発明による方法の実装、およびこの実装に合わせて構成された電子システムの実施形態の態様についての以下の説明を読めば、理解されよう。
【図面の簡単な説明】
【００２５】
【図１ａ】本発明による方法の２つのタイプの置換関数のうちの一方を示す図である。
【図１ｂ】本発明による方法の２つのタイプの置換関数のうちの他方を示す図である。
【図２】古典的なＤＥＳアルゴリズムについての１ラウンドを示す図である。
【図３ａ】本発明による方法が適用される、ＤＥＳアルゴリズムについての可能な１つのタイプのラウンドを示す図である。
【図３ｂ】本発明による方法が適用される、ＤＥＳアルゴリズムについての可能な１つのタイプのラウンドを示す図である。
【図３ｃ】本発明による方法が適用される、ＤＥＳアルゴリズムについての可能な１つのタイプのラウンドを示す図である。
【図３ｄ】本発明による方法が適用される、ＤＥＳアルゴリズムについての可能な１つのタイプのラウンドを示す図である。
【図３ｅ】本発明による方法が適用される、ＤＥＳアルゴリズムについての可能な１つのタイプのラウンドを示す図である。
【図４】本発明による方法が適用される、ＤＥＳアルゴリズムのオートマトンを示すシンボリック図である。
【発明を実施するための形態】
【００２６】
本発明による方法は、秘密鍵を伴う暗号計算プロシージャを使用した電子システム、および例えばチップカードなどの基板上の（ｏｎ−ｂｏａｒｄ）システムのセキュリティ保護を行うことを目指したものである。この電子システムは、プロセッサおよびメモリを含んでいる。この暗号計算プロシージャは、例えば前記システム用のＲＯＭタイプのメモリに組み込まれている。前記システム用のプロセッサは、例えばＥ２ＰＲＯＭタイプのメモリの秘密区域に記憶される秘密鍵を使用してこの計算プロシージャを実行する。
【００２７】
本発明による方法は、以下でクリティカル関数と呼ぶ関数の入力または出力としてこの計算プロシージャ中で取得される、クリティカル情報を構成する中間結果をマスキングすることから成っている。
【００２８】
この方法は、クリティカル関数を「同じ」計算を行うが修正された入力データまたは出力データを伴う関数で置き換えるものである。
【００２９】
図１ａおよび図１ｂ上に示すように、ある計算（テーブルを調べる一連の基本演算を介した計算）を行う、ｎビットからｍビットへの任意のｆ関数は、別の（ｎ’ビットからｎビットへの）関数ｇ（図１ａ）、または（ｍビットからｍ’ビットへの）関数ｈ（図１ｂ）を伴い、ｇがｆの前に実行され、ｈがｆの後で実行される、ｆから成る新しい関数ｐで置き換えられる。したがって、この方法では、この計算ｆが（ｇ−＞ｆ）または（ｆ−＞ｈ）で置き換えられる。
【００３０】
図に示す例によれば、ｇおよびｈは、「排他的論理和」形式のデータマスキング演算である。このｐ関数は、入力がｇでマスキングされたデータを取り込み、または、ｈでマスキングされたデータを出力する。
【００３１】
本説明中の用語「マスキング（ｍａｓｋ）」は、（内部的な、カードユーザによって知られていない）非公開関数、例えばハザードを使用した関数を使用して変換することを意味する。
【００３２】
計算プロシージャにおける最初のクリティカル関数のマスキングは、ｈ関数を伴う出力で行われる。計算プロシージャにおける最後のクリティカル関数のマスキングは、ｇ関数を伴う入力で行われる。このようにして、この計算プロシージャは、非マスクデータを入力で受け取り出力で提供する。マスキングは、外側では透明（ｃｌｅａｒ）である。このシステムに対してＤＰＡタイプの攻撃を行おうと思う人は、検出可能な情報を作成するその中間結果がマスキングされていることを知らず、その人にとっては、その理由を理解せずにその結果からどのような結論を引き出すこともできないはずである。
【００３３】
ｇの入力データ（およびｈの出力データ）のサイズは、必ずしもｆと同じサイズである必要はないことに留意されたい。
【００３４】
本発明は、（修正された関数をどのようにして含めるかという）計算プロシージャそれ自体を変換すること、ならびに（例えばこの方法が、テーブルに基本的にアクセスする場合、新しいテーブルを構築する方法という）修正された関数の計算態様という２つの態様を有している。
【００３５】
以下の説明では、ＤＥＳアルゴリズムに対する本発明の適用について説明している。まず、簡単化されているが理解しやすい第１の例を示して、次にこの第１の例に直接由来する様々な開発形態について検討することにする。
【００３６】
本発明による方法では、以下の２つの問題が別々に解決される。
修正されたＳ−ボックスを使用してＤＥＳをどのように構成するか
どのようにしてこれらのＳ−ボックスを構築するか
【００３７】
図２、図３ａから図３ｅ、および図４を参照して第１の簡単化された例における修正されたＳ−ボックスを使用するＤＥＳの構成を以下に説明する。
【００３８】
まず、ＤＥＳのｉ番目のラウンドについて考察する（図２）。マスキングされたデータを操作するために古典的なＤＥＳのＳ−ボックスを修正する。次いで、３２ビットの任意の値を伴うαについて考察する。４８ビットから３２ビットへの２つの新しい関数Ｓ’１およびＳ’２を以下のように定義する。
Ｓ’１（ｘ）＝Ｓ（ｘ  ｘｏｒ  Ｅ（α））  ３２ビットの任意のｘについて
Ｓ’２（ｘ）＝Ｓ（ｘ）  ｘｏｒ  Ｐ−１（α）  ３２ビットの任意のｘについて
【００３９】
次いで、関数ｆＫｉに類似しているが、Ｓの代わりにＳ’１ボックスおよびＳ’２ボックスを使用した２つの関数ｆ’１，Ｋｉおよびｆ’２，Ｋｉを定義する。
【００４０】
これらの２つの新しい関数により、ｆ’１，Ｋｉがマスキングされない値から出発してαによってマスキングされた値を取得し、ｆ’２，Ｋｉではその逆になるようにすることができる。
【００４１】
図３ａから図３ｅは、αによってマスキングされ、またはマスキングされない値と様々なボックス（ＳＫｉ、Ｓ’１，ＫｉまたはＳ’２，Ｋｉ）とを使用することによって得られるＤＥＳのラウンド（ＡからＥ）についての図を全部示したものである。明瞭に示すためにそのマスキングされたデータは破線で示すのに対して、マスキングされていないデータ（通常のもの）は実線で示している。
【００４２】
図４は、オートマトンとして記号で表される、得られる可能性のあるラウンドシーケンスの全体を示している。前述のように、マスキングされていないデータで出発し到着するために開始状況はＡまたはＢであるのに対し、終了状況はＡまたはＥである。
【００４３】
したがって、シーケンス：ＩＰ−ＢＣＤＣＤＣＥＢＣＤＣＤＣＤＣＥ−ＩＰ−１を用いた完全なＤＥＳ（１６ラウンド）を実行することが可能である。メッセージＭと共に出発して、この方法では、マスキングされない入力および出力のない通常の暗号文（シーケンスＩＰ−ＡＡＡＡＡＡＡＡＡＡＡＡＡＡＡＡ−ＩＰ−１を用いて得られた暗号文）を得ることが可能になる。
【００４４】
多くの有効な組合せが存在する。一部には、例えばＩＰ−ＢＣＥＡＡＡＡＡＡＡＡＡＡＢＣＥ−ＩＰ−１など、マスキングされたラウンドの間には通常のラウンド（タイプＡ）を使用して最初と最後のラウンドだけをマスキング可能にするものさえある。
【００４５】
本発明の開発によれば、データは、ラウンドに応じて異なるマスクを用いてマスキングされる。以上で使用されるラウンド表記法（Ａ、Ｂ、Ｃ、Ｄ、およびＥ）を採用して、マスキングの際に使用される３２ビットマスクを記号化するインデックス（α、β、γ．．．）が追加される。したがって、上記簡単化された例におけるＢラウンドは、Ｂαと書かれることが分かる。マスクが含まれないのでＡラウンドは、マスク値でインデックス付けする必要がないことにも留意されたい。かかる一般化例では、ＤＥＳは、以下のシーケンスに従って行われる。
ＩＰ−ＢαＣαＤαＣαＤαＣαＥαＢβＣβＤβＣβＤβＣβＤβＣβＥβ−ＩＰ−１
【００４６】
このようにして、これらのラウンド、および特に攻撃を受けやすい最初と最後のラウンドは、別々のマスクによって保護される。
【００４７】
前述の計算を実行するためには、タイプＳ、Ｓ’１，α、Ｓ’２，α、Ｓ’１，βおよびＳ’２，βのＳ−ボックスを構築する必要がある。
【００４８】
本発明によるこの方法に従って使用されるこれらの様々な修正されたＳ−ボックスは、以下の式に基づいてセキュリティ保護された方法で構築される。
Ｓ’１，α（ｘ）＝Ｓ（ｘ  ｘｏｒ  Ｅ（α））
Ｓ’１，β（ｘ）＝Ｓ（ｘ  ｘｏｒ  Ｅ（β））
Ｓ’２，α（ｘ）＝Ｓ（ｘ）  ｘｏｒ  Ｐ−１（α）
Ｓ’２，β（ｘ）＝Ｓ（ｘ）  ｘｏｒ  Ｐ−１（β）
【００４９】
前記式は、以下に示される基本演算に従って分割される。
（α、β．．．などの）ランダム値を抽出する、
（Ｅ（α）、Ｐ−１（β）．．．などの）秘密値のビットの置換、
Ｓ−ボックス（入力または出力）の通常の値に対応する値テーブルを用いて（例えばＰ−１（α）などの）値のＸＯＲを実行する。
【００５０】
ｎビット（ＤＥＳでは、ｎ＝３２）のランダム値の抽出が、以下のアルゴリズムに基づいて行われる。
【００５１】
この方法が使用されるシステムは、ｎオクテットのテーブル「ｔ」と、「ランド（ｒａｎｄ）」と呼ばれるオクテットにわたるハザードソースとを含んでいる。このアルゴリズムは、以下のように実行される。
０からｎ−１のｉについて：ｔ［ｉ］：＝ｒａｎｄ％２
０からｍ−１のｉについて：ｔ［ｒａｎｄ％ｎ］とｔ［ｒａｎｄ％ｎ］を置換する
式中、ｍは、基本的にｎ以上の数である。
「％」は、モジュロ演算、すなわち全除算の残余である。
【００５２】
求める結果は、テーブルｔに含まれるｎビットのチェーン（ｃｈａｉｎ）である。
【００５３】
第１のバージョンによれば、このシステムは、ｎ／４オクテットのテーブルｔを含む。
０とｎ／４−１の間のｉについて：ｔ［ｉ］：＝ｒａｎｄ
０とｍの間のｉについて：ｔ［ｒａｎｄ％（ｎ／４）］に対してｔ［ｒａｎｄ％（ｎ／４）］を置換する
式中、ｍは基本的にｎ／４より大きな数である。
【００５４】
結果は、ｔの各ｎ／４オクテットについて最初の４ビットの連結となる。
【００５５】
第２のバージョンによれば、ｎ／２、ｎ／３、ｎ／８またはｎについての任意の除算結果（ｄｉｖｉｄｅｒ）を使用して、第１のバージョンに従ってこのアルゴリズムを再度行う。
【００５６】
第３のバージョンによれば、ランダムな方法でケースを交換する代わりに、あるケースをランダムに選択し、それにランダム値に対するＸＯＲ演算を追加する。
【００５７】
（ＤＥＳの場合には、Ｐ−１（β）：ｎ＝４８およびｍ＝３２の置換、Ｅ（α）：ｎ＝ｍ＝３２の置換における）秘密値からのｎビットのｍビットへの置換は、以下のアルゴリズムに基づいている。
【００５８】
記述例では、ｎビットの「ｉｎ」とマークされたテーブルをｍビットの「ｍ」とマークされたテーブルへ置換するのが望まれる。このシステムは、ｍ個の値の「テンプ（ｔｅｍｐ）」テーブルを含んでいる（各ケースが、値ｎ−１を含むこともある）。
【００５９】
テンプテーブル中で、数字０、１、２、．．．、ｍ−２、ｍ−１の置換が行われる。
０からｍ−１のｉについて：ｏｕｔ［Ｖ［ｔｅｍｐ［ｉ］］］：＝ｉｎ［ｔｅｍｐ［ｉ］］
【００６０】
実際には、これはランダムな方法でビットごとに置換を行うという問題である。
【００６１】
第１のバージョンによれば、この置換は、ビットごとではなくてｋビットごとに、すべてランダムな方法で行われる。
【００６２】
第２のバージョンによれば、テーブルＶ中、または入力テーブルおよび／または出力テーブル中に、あるいはその両方にダミー値を追加することもできる。したがって、オクテットを使用してビットを記憶する場合、他の「空いている」ビットをハザードで完全なものにすることが可能である。
【００６３】
このＸＯＲ演算の実施形態は、ｍ個の値のｔテーブル中のｎビットの（Ｐ−１（α）などの）値を追加することから構成される。
【００６４】
この演算は、出力テーブルのオクテットに対して、ならびにこれらのオクテットのビットに対してランダムな方法で実行することができる。
【００６５】
あるバージョンによれば、αのビット中、ならびにテーブルｔ中にダミー値を追加することも可能である。
【００６６】
本発明による方法では、Ｓ−ボックスが鍵を使用しないで構築されるときには、マスキングするための非公開関数が使用される。計算プロシージャが実行されるときには、マスクは使用されない。したがって、本発明による方法では、たとえそれを知らない場合でさえ、マスクを使用するどのような攻撃に対してもこの電子システムをセキュリティで保護することが可能になる。
【００６７】
この修正されたＳ−ボックスを構築するためには他の任意のタイプの抽出および置換を使用することができることを強調しておく必要がある。
【００６８】
さらに、説明した３つの演算に基づくＳ−ボックスの構築については、他の任意のタイプの形態を用いて、また特にこの説明における例として使用されるＤＥＳに特有のＳ−ボックス以外の別の形態で実行することができる。
【図１ａ】
2011101413.tif 000005
【図１ｂ】
2011101413.tif 000006
【図２】
2011101413.tif 000007
【図３ａ】
2011101413.tif 000008
【図３ｂ】
2011101413.tif 000009
【図３ｃ】
2011101413.tif 000010
【図３ｄ】
2011101413.tif 000011
【図３ｅ】
2011101413.tif 000012
【図４】
2011101413.tif 000013
【手続補正書】
【提出日】平成23年1月13日(2011.1.13)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
秘密鍵を使用する暗号計算プロシージャを記憶する手段と、前記計算プロシージャを実行する手段とを備える電子システムにして、暗号計算プロシージャはラウンドのシーケンスで実行され、中間結果を構成する中間ラウンドの出力（Ｌｉ＋１，Ｒｉ＋１）は次のラウンドの入力（Ｌｉ，Ｒｉ）として使用され、各ラウンドが、変換関数（ｆＫｉ）を実行するシステムであって、
各オリジナルのラウンドについて代用ラウンド（Ａ，Ｂ，Ｃ，Ｄ，Ｅ）の組を定義する手段と、
各ラウンドの代わりに、代用ラウンド（Ａ，Ｂ，Ｃ，Ｄ，Ｅ）の１つを実行する手段を含み、代用ラウンド（Ａ，Ｂ，Ｃ，Ｄ，Ｅ）の組は、代用ラウンドの１つ（Ａ）が修正されないラウンドであり、他の代用ラウンド（Ｂ，Ｃ，Ｄ，Ｅ）の各々が、置換変換関数（ｆ’１Ｋｉ，ｆ’２Ｋｉ）を使用すること、または、マスキングされた中間結果を、出力で与えることまたは、入力で受信すること、を含むものである、ことを特徴とする、電子システム。
【請求項２】
各代用ラウンドの入力は左側部分（Ｌｉ）と右側部分（Ｒｉ）に分けられ、各代用ラウンドの出力は左側部分（Ｌｉ＋１）と右側部分（Ｒｉ＋１）に分けられる、請求項１に記載の電子システム。
【請求項３】
Ａと呼ぶ第１の代用ラウンド（Ａ）は、修正されないラウンドであり、
Ｂと呼ぶ第２の代用ラウンド（Ｂ）は、マスキングされていない入力（Ｌｉ，Ｒｉ）から右側部分（Ｒｉ＋１）がマスキングされた出力（Ｌｉ＋１，Ｒｉ＋１）を生成するために、置換変換関数（ｆ’２Ｋｉ）を使用することを含み、
Ｃと呼ぶ第３の代用ラウンド（Ｃ）は、右側部分（Ｒｉ）がマスキングされた入力（Ｌｉ，Ｒｉ）から左側部分（Ｌｉ＋１）がマスキングされた出力（Ｌｉ＋１，Ｒｉ＋１）を生成するために、置換変換関数（ｆ’１Ｋｉ）を使用することを含み、
Ｄと呼ぶ第４の代用ラウンド（Ｄ）は、左側部分（Ｌｉ）がマスキングされた入力（Ｌｉ，Ｒｉ）から右側部分（Ｒｉ＋１）がマスキングされた出力（Ｌｉ＋１，Ｒｉ＋１）を生成するために、オリジナルの変換関数（ｆＫｉ）を使用することを含み、
Ｅと呼ぶ第５の代用ラウンド（Ｅ）は、左側部分（Ｌｉ）がマスキングされた入力（Ｌｉ，Ｒｉ）からマスキングされていない出力（Ｌｉ＋１，Ｒｉ＋１）を生成するために、置換変換関数（ｆ’２Ｋｉ）を使用することを含む、
５つの代用ラウンドを定義することを含む、請求項２に記載の電子システム。
【請求項４】
代用ラウンドのランダムシーケンスを含み、ランダムシーケンスは暗号計算プロシージャの入力と出力に対してマスキングされていない結果を与えるように定義され、ＡまたはＢを第１の代用ラウンドとして使用し、ＡまたはＥを最後の代用ラウンドとして使用し、任意の代用ラウンドを中間代用ラウンドとして使用するが、ＡにはＡまたはＢのみが続くことができ、ＢにはＣのみが続くことができ、ＣにはＤまたはＥのみが続くことができ、ＤにはＣのみが続くことができ、ＥにはＡまたはＢのみが続くことができる、という規則に従う、請求項３に記載の電子システム。
【請求項５】
暗号計算プロシージャはＤＥＳアルゴリズムの実装であり、代用ラウンドのシーケンスは固定され、ＢＣＤＣＤＣＥＢＣＤＣＤＣＤＣＥまたは、ＢＣＥＡＡＡＡＡＡＡＡＡＡＢＣＥのいずれかである、請求項３に記載の電子システム。
【請求項６】
異なる代用ラウンドに対して、異なるマスク（α，β，γ）を使用する、請求項１から５のいずれか一項に記載の電子システム。
【請求項７】
暗号計算プロシージャはＤＥＳアルゴリズムの実装であり、代用ラウンドのシーケンスは固定され、ＢαＣαＤαＣαＤαＣαＥαＢβＣβＤβＣβＤβＣβＤβＣβＥβである、請求項６に記載の電子システム。
【請求項８】
各代用ラウンドの出力の左側部分（Ｌｉ＋１）は入力の右側部分（Ｒｉ）に等しく、各代用ラウンドの出力の右側部分（Ｒｉ＋１）は、入力の右側部分（Ｒｉ）に適用された変換関数（ｆＫｉ，ｆ’１Ｋｉ，ｆ’２Ｋｉ）の結果と排他的論理和（ＸＯＲ）の演算がなされた入力の左側部分（Ｌｉ）に等しい、請求項２に記載の電子システム。
【請求項９】
ラウンド（Ｃ）が置換変換関数（ｆ’１Ｋｉ）を含み、ラウンド（Ｃ）が入力のマスキングされた部分（Ｒｉ）を使用し、ラウンド（Ｃ）が、以下の演算、すなわち、
公開ではないマスク（α，β，γ）との排他的論理和（ＸＯＲ）演算から成るマスキング／アンマスキングの第１の演算であって、マスキング／アンマスキングの演算は入力のマスキングされた部分（Ｒｉ）に適用され、
変換関数（ｆＫｉ）と同じ計算を行うが、入力が、マスキング／アンマスキングの第１の演算の結果に対応する、第２の演算
に基づいて構築される、請求項８に記載の電子システム。
【請求項１０】
ラウンド（Ｂ）が、その出力をマスキングする置換変換関数（ｆ’２Ｋｉ）を含み、ラウンド（Ｂ）が入力のマスキングされていない部分（Ｒｉ）を使用し、ラウンド（Ｂ）は、以下の演算、すなわち、
変換関数（ｆＫｉ）と同じ計算を行う第１の演算であって、入力が前記入力のマスクされていない部分（Ｒｉ）に等しいが、第１の演算の結果が第２のマスキング／アンマスキング演算により続いてマスキングされる第１の演算、
非公開のマスク（α，β，γ）との排他的論理和（ＸＯＲ）演算から成る第２のマスキング／アンマスキング演算
に基づいて構築される、請求項８に記載の電子システム。
【外国語明細書】
2011101413000001.pdf