(57)【要約】ラインダール・ＡＥＳ暗号化規格に従う暗号法に関する方法およびこれに関連する実装。一改良策によると、以前の暗号化の鍵スケジュール決定作業から保存された最後のＮｋ個のラウンド鍵から複合ラウンド鍵（ｗ［ｉ］）がラウンドごとに生成される。これにより待ち時間およびメモリの要件が最小限に抑えられる。ＡＥＳ鍵生成および暗号作業それ自体のためのＳ−ｂｏｘ（４１0〜４１3）は、換字されるべき異なるバイトについての経路を擬似ランダム的に選択する（３９0〜３９3，４１0〜４１3）ことにより、異なる電力特性による異なる態様で多数回実装され得る。事前混合作業（７３）は最初のラウンド鍵の生成と同時に行なわれ（７２，８３）、実際の事前混合回路と実質的に同一のタイミングによるダミー回路（図１３）が電力消費の雑音を事前混合に加える。
2005527853.tif 000002
【特許請求の範囲】
【請求項１】
高度暗号化規格（ＡＥＳ）すなわちラインダールブロック暗号アルゴリズムに従い鍵展開ルーチンを実行することによりＮｋワードからなる所与の暗号鍵からＮｂ（Ｎｒ＋１）ラウンド鍵ワードｗ［ｉ］からなる鍵スケジュール（ここでＮｂはワード数による暗号ブロックサイズであり、Ｎｒは前記暗号アルゴリズムで採用されるラウンド数である）を生成するように構成された鍵生成器において、前記鍵生成器は前記ラウンド鍵ワードｗ［ｉ］をラウンドごとに必要に応じ「オンザフライ」で生成するように構成されており、その改良は、ラウンド鍵ワードを前記暗号アルゴリズムの復号作業で使用されるように「オンザフライ」で逆方向に生成するための方法を含み、前記方法は、
Ｎｋラウンド鍵ワードの最後の組を格納するためのメモリを設けるステップと、
前記Ｎｋラウンド鍵ワードの最後の組を入手するために暗号化作業中に順方向で前記鍵展開ルーチンを実行し、そのために設けられた前記メモリに前記Ｎｋラウンド鍵ワードの最後の組を格納するステップと、
前記復号作業のために前記鍵生成器をセットするステップと、
格納されたラウンド鍵ワードｗ［ｉ］およびｗ［ｉ−１］を含むＸＯＲ論理演算により先行のラウンド鍵ワードｗ［ｉ−Ｎｋ］を「オンザフライ」で導き出すステップとを含み、ｗ［ｉ−１］は、ｉ  ｍｏｄ  Ｎｋ＝０であるときはいつでも、かつさらにＮｋ＞６およびｉ  ｍｏｄ  Ｎｋ＝４であるときはいつでも前記ＸＯＲ論理演算を適用するのに先立ち変換シーケンスにより最初に変更を加えられ、前記変換シーケンスは、循環バイトシフト、Ｓ−ｂｏｘバイト換字、およびｉ  ｍｏｄ  Ｎｋ＝０のときにおけるラウンド定数によるＸＯＲ演算を含み、前記変換シーケンスは、Ｎｋ＞６およびｉ  ｍｏｄ  Ｎｋ＝４のときにＳ−ｂｏｘバイト換字のみを含み、ｗ［ｉ−１］に対する前記変換シーケンスは、前記鍵展開ルーチンの順方向および逆方向において同一であり、かつＡＥＳ・ラインダールブロック暗号アルゴリズムに従う、鍵生成方法。
【請求項２】
前記鍵生成器はハードウェア回路として実装される、請求項１に記載の鍵生成方法。
【請求項３】
前記Ｓ−ｂｏｘバイト換字を実行するために多数のＳ−ｂｏｘが設けられ、各々のＳ−ｂｏｘは、ＡＥＳ・ラインダールについて指定された同一の機能を有するが、異なる電力消費特性により特徴付けられる異なるハードウェア実装によるものであり、かつ、擬似乱数発生器が、前記鍵展開ルーチンにおいて換字されるべきさまざまなバイトについて異なるＳ−ｂｏｘへの可変の経路を選択する、請求項２に記載の鍵生成方法。
【請求項４】
前記擬似乱数発生器は、ｎビットの擬似乱数出力と前記擬似乱数出力によりアドレス指定されるルックアップ表とを生成しかつ前記擬似乱数出力に対応する経路選択制御信号を生成する線形フィードバックシフトレジスタである、請求項３に記載の鍵生成方法。
【請求項５】
暗号文を生成するための暗号化ラウンドのシーケンスを始めるのに先立ち平文を暗号鍵と混合する暗号ブロックアルゴリズムの初期事前混合ＸＯＲ演算を実行するための事前混合副回路を有するハードウェアブロック暗号回路において、電力差分解析への対抗措置は、
前記初期事前混合ＸＯＲ演算中に活性でありかつ前記事前混合副回路の伝搬遅延に実質的に揃えられた伝搬遅延により特徴付けられる事前混合ダミー回路を含み、前記ダミー回路は擬似乱数発生器およびＸＯＲアレイを含み、前記ＸＯＲアレイは、前記擬似乱数発生器の出力部に接続された第１の入力部と、前記事前混合副回路と同じ暗号鍵ビットを受けるように接続された第２の入力部と、前記擬似乱数発生器にフィードバックする出力部とを有し、前記ダミー回路は、前記初期事前混合ＸＯＲ演算中に前記ハードウェアブロック暗号回路についてのすべてのＸＯＲゲート切換の全体電力特性に擬似ランダムな雑音を挿入する、回路。
【請求項６】
前記擬似乱数発生器は１組の線形フィードバックシフトレジスタを含む、請求項５に記載の回路。
【請求項７】
前記ダミー回路の前記擬似乱数発生器およびＸＯＲアレイは、前記事前混合副回路のビット数のワード幅と同一数のビットのワード幅を有する、請求項５に記載の回路。
【請求項８】
暗号文を生成するための暗号化ラウンドのシーケンスが始まるのに先立ち平文を暗号鍵と混合する初期事前混合ＸＯＲ演算を有する暗号法アルゴリズムを実行するように構成されたハードウェアブロック暗号回路において、その改良点は、前記事前混合演算を１番目の暗号化ラウンドと組合せる方法を含み、前記方法は、
平文がロードされている間に前記１番目の暗号化ラウンドについてのラウンド鍵ワードを生成するように前記暗号鍵を事前処理するステップを含み、前記事前混合ＸＯＲ演算は平文がロードされている際にも行なわれ、前記方法はさらに、
予め生成された前記最初のラウンド鍵ワードを用いて、ロードされ予め混合された平文に対して前記１番目の暗号化ラウンドを実行するステップを含む、方法。
【発明の詳細な説明】
【技術分野】
【０００１】
技術分野
この発明は暗号法についての方法および装置に関し、特にラインダール（Rijndael）またはＡＥＳとして知られる特定の対称鍵ブロック暗号アルゴリズムおよびこれに関連するハードウェアまたはソフトウェア実装に関する。この発明は具体的には、上記アルゴリズムにおける暗号化および復号の両方向でのラウンド鍵の生成に関し、さらにまた、実装をするハードウェアまたはソフトウェアに対し、暗号鍵を解読しようとして加えられる電力差分解析攻撃を防ぐための技術に関する。
【背景技術】
【０００２】
背景技術
米国商務省標準技術協会（ＮＩＳＴ）は、２００１年１１月２６日の「連邦情報処理規格刊行物（Federal Information Processing Standards Publication）１９７」（ＦＩＰＳ  １９７）に規定のように、同協会の高度暗号化規格（ＡＥＳ）としてラインダールによる対称鍵ブロック暗号アルゴリズムの一部を採用した。ＡＥＳアルゴリズムは、１２８、１９２および２５６ビットの暗号鍵を用いて１２８ビットのブロックにあるデータを暗号化および復号するものである。ラインダール・アルゴリズムは１９２および２５６ビットのブロックを扱うことも可能であり、さらに、或る中間のまたは潜在的にはこれらを上回る鍵長およびブロックサイズへの拡張にも対応しており、演算はその任意の鍵長およびブロックサイズ間に規定される。
【０００３】
上記アルゴリズムにおいては、鍵長およびブロックサイズに依存して或る数のほぼ同一のラウンドが反復される。ＡＥＳ１２８は１０ラウンドを用い、ＡＥＳ１９２は１２ラウンドを用い、ＡＥＳ２５６は１４ラウンドを用いて暗号化または復号の作業を完了させる。より一般的には、鍵長がＮｋ個の３２ビットワードでブロックサイズがＮｂ個の３２ビットワードの場合、ラインダール・アルゴリズムにおけるラウンド数Ｎｒは現在のところＮｒ＝ｍａｘ（Ｎｋ，Ｎｂ）＋６と指定されている。
【０００４】
ここに記載される発明は、ＡＥＳについて指定された１２８ビットのブロックサイズを含むラインダールによるどのような鍵長およびブロックサイズにも適用可能であり、さらにまたいずれの作業モードにも適用可能である。本特許明細書における残る部分は好ましいＡＥＳ実施例に関するものであるが、ラインダールによるその他いずれのブロックサイズへの拡張もまた含意されると理解されたい。
【０００５】
モリス・ドゥウォーキン（Morris Dworkin）によるＮＩＳＴ特別刊行物８００−３８Ａ「ブロック暗号作業モードに関する勧告：その方法および技術（Recommendation for Block Cipher Modes of Operation: Methods And Technique）」（２００１年１２月）においては、ＮＩＳＴにより認可された機密性に関する５つの作業モードであって、ＡＥＳなどあらゆる基礎となる対称鍵ブロック暗号アルゴリズムとの関連で用いられるものが明記されている。また、その他の可能な作業モードもＮＩＳＴ認可について検討されている。本願明細書に記載される発明はこれら作業モードのいずれに対しても適用可能である。
【０００６】
ＡＥＳにおいては、各ラウンド中に３つの主なステップが行なわれる。すなわち、（ａ）文のブロックに変更を加え、（ｂ）ラウンド鍵を生成し、そして（ｃ）ＸＯＲ演算を用いて上記変更を加えた文ブロックと上記ラウンド鍵とを加算し、次のラウンドについての開始文ブロックを得る。各ラウンド（Ｓ−ｂｏｘ換字、行のシフト、列の混合）において文ブロックには同様の変更が加えられるが、例外が２つある。第１の例外は鍵の事前混合
演算（ラウンド０）であり、これは平文メッセージブロックと、暗号鍵自体からの最初のＮｂワードを入れた初期ラウンド鍵とについてビットごとにＸＯＲを取るというものである（ＡＥＳではＮｂ＝４）。この鍵の事前混合演算によりラウンド１についての開始文が得られる。第２の例外は最終ラウンドで起こり、ここでは列の混合演算が省略される。ラウンドについてのＳ−ｂｏｘ換字、行のシフトおよび列の混合の各演算の詳細は上述のＦＩＰＳ１９７文書に記載されている。
【０００７】
ラウンド鍵からなる組（鍵スケジュール）は、鍵展開ルーチンを用いて初期暗号鍵から生成される。ＡＥＳにおけるラウンド鍵の長さは、元の暗号鍵の長さ（１２８、１９２または２５６ビット）にかかわらずブロックサイズ（１２８ビット＝４ワード）と常に同じである。暗号鍵をなすワードは、それが存続している早いラウンドにおいて用いられ、後続の連続するラウンドの鍵のワードは各々が、先行するラウンドの鍵のワードの関数となる。鍵展開ルーチンによるラウンド鍵の計算は各々の暗号鍵長ごとにわずかに異なる。すなわち、各々の場合において同じ基本ステップ（Ｓ−ｂｏｘ換字、バイトの回転、ラウンド定数によるＸＯＲ）が用いられるが、これらが行なわれる頻度は鍵長によって異なってくる。
【０００８】
復号を行なう単純な手法としては、個々の暗号変換を逆にして暗号化とは逆順で実現するというものがある。暗号化および復号の作業についての鍵スケジュールの形は同じであるが逆順で適用される。すなわち、復号での１番目のラウンドの鍵は暗号化での最後のラウンドの鍵と同じで、復号での２番目のラウンドの鍵は暗号化での最後から２番目のラウンドの鍵と同じ、などとなる。
【０００９】
鍵スケジュール決定の一般的な１手法においては、予め通信セッションに必要なラウンド鍵すべてを事前計算し、これらをメモリ内で鍵表として保存して各々のラウンドでの必要に応じ検索できるようにする。この手法においては、ラウンド鍵の組の計算中に長期間にわたる初期待ち時間があるが、その後は暗号ラウンドがより高速で実行される。さらに、この場合での復号ラウンドは暗号化ラウンドと同じ速さとなる。しかしながら、この手法においては、鍵スケジュール全体を格納するために利用可能なメモリ容量が十分に存在すること、および初期待ち時間の期間が許容できるものであることが前提となっている。
【００１０】
もう１つ、いくつかのハードウェアシステムで用いられる手法として、ラウンド鍵がラウンドごとに必要に応じ生成される「オンザフライ」の鍵スケジュール決定法が挙げられる。この手法においては鍵スケジュール全体を事前処理しないため、少なくとも順方向の暗号方向（暗号化）においては初期待ち時間の期間が回避され、ラウンド鍵のためのメモリ要件が大幅に緩和される。この手法は、暗号化のみを行なう必要がある装置であってメモリおよび処理の制約があるものにとりわけ有用である。しかしながら、逆の暗号方向（復号）においてはラウンド鍵は逆順で必要とされる。すなわち、復号での１番目のラウンドの鍵は暗号化での最後のラウンドの鍵と同じである。さらに、各ラウンド鍵は先行するラウンドの鍵の関数である。既存の「オンザフライ」鍵展開方法においては、復号方向で、とりわけ早い復号ラウンドにおいて長い待ち時間が生じるが、それは各々のラウンドにつき「オンザフライ」鍵生成器が現在の復号ラウンドのためのラウンド鍵に達するまで先行するラウンドの鍵すべてを再計算しなければならないからである。もし可能であれば、逆方向においてこの待ち時間を解消する改良された鍵生成ルーチンが必要とされている。
【００１１】
ＡＥＳなどの暗号は、現実世界の用途に採用される際にまずハードウェアまたはソフトウェアで実装されることになる。攻撃者としては、暗号自体にある数学的弱点を捜すよりも、上記実装についての或る弱点を突こうとする場合がある。これを行なうには、暗号法システムをその動作中に外的に監視し、内部動作についての情報が漏れ出てくるとその中で暗号鍵を求めるのに有用となり得るものを入手する。暗号法システムへの対実装型の攻
撃例としてはタイミングおよび電力解析攻撃があり、これは実行時間または電力消費のパターンにおける、鍵に依存するあらゆる変動を利用したものである。さまざまな対実装型攻撃に対する公知の対抗措置としては一般的に以下のものが挙げられる。すなわち、抵抗性チップパッケージの改変、信号放出を防ぐ物理的遮蔽措置、入力および出力のフィルタ処理、動作タイミングを一様またはランダムにする計算技術、暗号鍵から命令シーケンスの独立化または各命令ごとにおける命令シーケンスの変更、および電力消費パターンへのハードウェア雑音の付加などがある。たとえば、コッカー（Kocher）他への米国特許第６，３２７，６６１号には、予測不可能（ランダムまたは擬似ランダム）情報を暗号処理に組込む対抗措置が記載されている。しかしながら、取られ得るこれらの防護策はすべてがあらゆる状況で適用可能であるわけではない。たとえば、暗号法エンジンが組込まれたスマートカードにおいては、処理および記憶上の制約のため、多数の利用可能な対抗措置のうちどれを利用できるのかは制限される。スマートカードおよびその他プロセッサまたはメモリで制約のある用途については、最初に平文が処理される最も攻撃を受けやすい期間中に特に、実装における追加的な対抗措置が望まれている。
【発明の開示】
【発明が解決しようとする課題】
【００１２】
暗号化および復号は必然的に時間のかかる作業である。平文のブロックを暗号文に変換したりその逆を行なったりするために必要なデータビット、バイトおよびワードの転置および換字が多数あるためこれらの処理には時間がかかる。ブロックサイズおよびラウンド数が増加するのに伴い、これに対応してハードウェアの処理電力が増大することを除いても上記の問題は悪化する傾向にある。所与の実装において時間の節約分を利用することができれば、それがどれほどのものであれ有利であろう。ただし安全性が損なわれないことが前提である。
【００１３】
この発明の目的は、ＡＥＳ・ラインダールによるラウンド鍵を逆（復号）方向で効率的に生成することのできるオンザフライ鍵スケジュール決定方法およびこれに関連するハードウェアまたはソフトウェアを提供することである。
【００１４】
この発明のもう１つの目的は、暗号化における早い段階、とりわけ暗号についての鍵の事前混合段階（ラウンド０）中における電力解析攻撃への対抗措置が取られたＡＥＳ・ラインダール暗号のハードウェア実装を提供することである。
【００１５】
この発明のさらにもう１つの目的は、暗号の処理に必要なクロックサイクルの総数を減少させたＡＥＳ・ラインダール実装を提供することである。
【課題を解決するための手段】
【００１６】
発明の開示
上記目的は、ＡＥＳラウンド鍵ワードｗ［ｉ］を、暗号アルゴリズムの復号作業で使用されるようにラウンドごとに必要に応じ「オンザフライ」で逆方向に生成する、鍵生成器のための方法によって達成される。好ましくは、上記鍵生成器はハードウェア回路として実現されるが、所望であればソフトウェアで実現されることもあり得る。上記の逆方向の鍵生成は、順方向での暗号化作業の鍵展開中に導き出されたＮｋラウンド鍵ワードの最後の組を格納するためのメモリを設けることで達成される。そして、鍵生成回路が復号作業のためにセットされたとき、これは格納されたラウンド鍵ワードｗ［ｉ］およびｗ［ｉ−１］を含むＸＯＲ論理演算により先行のラウンド鍵ワードｗ［ｉ−Ｎｋ］を「オンザフライ」で導き出し、ここでｗ［ｉ−１］は、ｉ  ｍｏｄ  Ｎｋ＝０であるときはいつでも、かつさらにＮｋ＞６およびｉ  ｍｏｄ  Ｎｋ＝４であるときはいつでも上記ＸＯＲ論理演算を適用するのに先立ち変換シーケンスにより最初に変更を加えられる。ｗ［ｉ−１］に対する変換シーケンスは、鍵展開ルーチンの順方向および逆方向において同一である。上
記変換シーケンスは、循環バイトシフト、Ｓ−ｂｏｘバイト換字、およびｉ  ｍｏｄ  Ｎｋ＝０であるときはいつでもラウンド定数によるＸＯＲ演算を含む。上記変換シーケンスは、Ｎｋ＞６およびｉ  ｍｏｄ  Ｎｋ＝４のときにＳ−ｂｏｘバイト換字のみを含む。
【００１７】
また、この発明の上記目的は、ブロック暗号アルゴリズムの初期事前混合ＸＯＲ演算中に、ハードウェアブロック暗号回路の全体電力特性に擬似ランダム雑音を挿入する事前混合ダミー回路によっても達成される。この電力差分解析対抗措置においては、１番目の暗号化ラウンドに先立って平文が暗号鍵と混合される際にすべてのＸＯＲゲート切換からの電力の特性を隠す。上記事前混合ダミー回路はこの初期の事前混合ＸＯＲ演算中においてのみ活性であり、事前混合副回路の伝搬遅延に実質的に揃えられた伝搬遅延を特徴とする。上記ダミー回路は擬似乱数発生器およびＸＯＲアレイを含む。擬似乱数発生器としてはたとえば１組の線形フィードバックシフトレジスタを用いることができる。上記ＸＯＲアレイは、上記擬似乱数発生器の出力部に接続された第１の入力部を有する。上記ＸＯＲアレイの第２の入力部は上記事前混合副回路と同じ暗号鍵ビットを受けるように接続される。上記ＸＯＲアレイの出力部は上記擬似乱数発生器にフィードバックする。上記ダミー回路の擬似乱数発生器およびＸＯＲアレイは、上記事前混合副回路のビット数のワード幅と同一のビット数のワード幅を有することができる。
【００１８】
さらにまた、この発明の上記目的は、暗号文を生成するための暗号化ラウンドのシーケンスが始まるのに先立ち平文を暗号鍵と混合する初期事前混合ＸＯＲ演算を有する暗号アルゴリズムを実行するように構成されたハードウェアブロック暗号回路において、事前混合作業を１番目の暗号化ラウンドと組合せる方法を用いて、暗号アルゴリズムを処理するのに必要なクロックサイクル数を１ラウンドだけ減少させることにより達成される。この方法においては、暗号鍵を事前処理して、平文がロードされている１番目の暗号化ラウンドについてのラウンド鍵ワードを生成する。上記事前混合ＸＯＲ演算は平文がロードされている際にも行なわれる。１番目の暗号化ラウンドは、上記予め生成された最初のラウンド鍵ワードを用いて上記ロードされ予め混合された平文に対して実行される。
【発明を実施するための最良の形態】
【００１９】
発明を実施するための最良の形態
この発明は好ましくは、ハードウェア回路において、マイクロコントローラまたはその他のシステム回路たとえばスマートカードなどのための暗号法エンジンとして実現される。この暗号法エンジンは、ＡＥＳ演算を実行するように設計された特定用途向け集積回路（ＡＳＩＣ）であっても、ＡＥＳ演算を実行するようにファームウェアをプログラムした用途のより広い処理ハードウェアであってもよい。通常、この暗号法エンジンはより大きいシステム回路とメモリを共有する。また、この暗号法エンジンをソフトウェアで実現してもよい。
【００２０】
ＡＥＳ・ラインダール・アルゴリズムは、暗号鍵に対して鍵展開ルーチンを実行して鍵スケジュールを生成する。この鍵展開により合計でＮｂ（Ｎｒ＋１）ワードが生成され、ここでＡＥＳ規格についてはブロックサイズＮｂ＝４であるが、その他のラインダール実装例については異なることもあり、かつ、ラウンド数Ｎｒは現在のところ［ｍａｘ（Ｎｋ，Ｎｂ）＋６］と指定されており、ここでＮｋは３２ビット（４バイト）ワードでの暗号鍵サイズである。ラウンド鍵は各々がＮｂワードからなり、その結果として得られる鍵スケジュールはワードからなる線形アレイであり、これは［ｗi］で表わされ、ｉは０≦ｉ≦Ｎｂ（Ｎｒ＋１）の範囲内にある。暗号化の際には、ラウンド鍵ワードはｉ＝０からＮｂ（Ｎｒ＋１）への順方向で必要とされる。一方で復号に際しては、ラウンド鍵ワードはｉ＝Ｎｂ（Ｎｒ＋１）で始まる逆方向で必要とされる。
【００２１】
順方向の鍵展開についての擬似コードはＦＩＰＳ−１９７において以下のように定めら
れている。
【００２２】
【数１】
2005527853.tif 000003
【００２３】
ＳｕｂＷｏｒｄ（）は４バイトの入力ワードを取る関数であり、Ｓ−ｂｏｘ表（図１に示す）を上記４バイトの各々に対して適用して出力ワードを生成する。上記バイトは、４ビットの１６進値０〜ｆの対ｘｙによって表わされる。各々の対ｘｙはＳ−ｂｏｘ表より出力対をもたらす。たとえばバイト｛５３｝は、換字バイト｛ｅｄ｝によって取って代わられることになる。また、ＡＥＳ規格（ＦＩＰＳ−１９７）においては、逆暗号法で用いられる逆Ｓ−ｂｏｘも明記されている。鍵スケジュール決定に関するこの発明の利点として、逆Ｓ−ｂｏｘを必要とせず、同じＳ−ｂｏｘを順方向で使用することでラウンド鍵を逆順に生成できることが挙げられる。
【００２４】
関数ＲｏｔＷｏｒｄ（）は、入力としてワード［ａ0，ａ1，ａ2，ａ3］を取り、巡回置換を実行してワード［ａ1，ａ2，ａ3，ａ0］を返す。
【００２５】
ラウンド定数ワードアレイＲｃｏｎ［ｉ］は、［ｘi-1，｛００｝，｛００｝，｛００｝］で与えられる値を含み、ここでｘ＝｛０２｝であり、ｘi-1は、８次の既約多項式による係数の約分での有限体ＧＦ（２8）におけるｘの冪乗である。すなわちｍ（ｘ）＝ｘ8＋ｘ4＋ｘ3＋ｘ＋１＝｛０１｝｛１ｂ｝である（ｍ（ｘ）による係数の約分により、確実に結果をバイトで表わすことが可能となる）。参照のため、最初の１０ラウンド定数（ｉ＝１で始まる）は以下のとおりである。
【００２６】
【表１】
2005527853.tif 000004
【００２７】
１６進値０〜ｆについてのＸＯＲ（排他的ＯＲ）関数表を便宜のため図２に示す。なお、ＸＯＲ関数はビットごとの演算（２を法とした加法と等価）である。２つのバイト｛ａ7ａ6ａ5ａ4ａ3ａ2ａ1ａ0｝および｛ｂ7ｂ6ｂ5ｂ4ｂ3ｂ2ｂ1ｂ0｝については和は｛ｃ7ｃ6ｃ5ｃ4ｃ3ｃ2ｃ1ｃ0｝であり、各ｃi＝ａi   ＸＯＲ  ｂi である。これらのバイトは１対の１６進値による１６進記数法によって表わすことができる。なお、この発明の逆方向鍵展開ルーチンは、ＸＯＲ関数の或る特性、すなわちａi ＝ｃi   ＸＯＲ  ｂi であれば、そしてその場合にのみ、ｃi ＝ａi   ＸＯＲ  Ｂi であるという特性を利用する。
【００２８】
上述の擬似コードから見て取ることができるように、順方向の鍵展開ルーチンは、展開された鍵の最初のＮｋワードに暗号鍵を入れることで始まる。これに続く各々のワードｗ［ｉ］は、先行するワードｗ［ｉ−１］と、Ｎｋ位置だけ早いワードｗ［ｉ−Ｎｋ］とのＸＯＲと等しい。Ｎｋの倍数である位置にあるワード（すなわちｉ  ｍｏｄ  Ｎｋ＝０であるもの）については、ｗ［ｉ−Ｎｋ］でのＸＯＲに先立ち変換シーケンスがｗ［ｉ−１］に適用される。この変換シーケンスは、ワードの中にあるバイトの循環シフト（すなわちＲｏｔＷｏｒｄ（）関数）と、これに続いて行なわれる、当該ワードの４バイトすべてに対するＳ−ｂｏｘ表のルックアップの適用（すなわちＳｕｂＷｏｒｄ（）関数）と、これに続いて行なわれる、当該ワードについてのラウンド定数Ｒｃｏｎ［ｉ／Ｎｋ］でのＸＯＲとからなる。これに加え、２５６ビット暗号鍵（Ｎｋ＝８）またはその他ラインダール暗号アルゴリズムにおける大きい暗号鍵（Ｎｋ＞６）については、ｉ−４がＮｋの倍数（すなわちｉ  ｍｏｄ  Ｎｋ＝４）であれば、Ｓ−ｂｏｘルックアップ関数ＳｕｂＷｏｒｄ（）はｗ［ｉ−Ｎｋ］でのＸＯＲに先立ってｗ［ｉ−１］に適用される。
【００２９】
図３、図５および図７は、それぞれ１２８ビット、１９２ビットおよび２５６ビットの暗号鍵についての順方向鍵展開ルーチンの例を示す。
【００３０】
この発明の逆方向鍵展開方法においては、ラウンド鍵が「オンザフライ」で、すなわちラウンドごとに必要に応じて逆方向に生成される。逆方向鍵展開についての擬似コードは以下のとおりである。
【００３１】
【数２】
2005527853.tif 000005
【００３２】
逆方向鍵展開ルーチンにおいては、以前の順方向展開からのラウンド鍵の最後のＮｋワードがメモリに保存される必要がある。逆順においては、これら最後のラウンド鍵ワードは、等価の逆暗号法で用いられる最初のラウンド鍵ワードである。後続の各々のワードｗ［ｉ−Ｎｋ］は逆順に（すなわち減少するｉで）生成され、Ｎｋ位置だけ早いワードｗ［ｉ］と、その隣接するワードｗ［ｉ−１］とのＸＯＲに等しく、これは変換シーケンスにより好適な変更を加えられ得る。変換シーケンスを適用する条件および変換シーケンスそれ自体は順方向鍵展開におけるのと同じである。関数ＳｕｂＷｏｒｄ（）、ＲｏｔＷｏｒｄ（）およびＸＯＲ、ならびにラウンド定数ワードアレイＲｃｏｎ［ｉ］は、順方向鍵展開について上述したものとまったく同一である。Ｎｋの倍数である位置にあるワード（すなわちｉ  ｍｏｄ  Ｎｋ＝０であるもの）について、ｗ［ｉ−１］に適用される変換シーケンスは、バイトの循環シフト（すなわちＲｏｔＷｏｒｄ（）関数）と、これに続いて行なわれる、当該ワードの４バイトすべてに対するＳ−ｂｏｘ表ルックアップの適用（すなわちＳｕｂＷｏｒｄ（）関数）と、これに続いて行なわれる、対応のラウンド鍵Ｒｃｏｎ［ｉ／Ｎｋ］でのＸＯＲとからなる。また、２５６ビット暗号鍵（Ｎｋ＝８）またはその他ラインダール逆暗号法での大きな暗号鍵（Ｎｋ＞６）については、ｉ−４がＮｋの倍数（すなわちｉ  ｍｏｄ  Ｎｋ＝４）であれば、Ｓ−ｂｏｘルックアップ関数ＳｕｂＷｏｒｄ（）は、ｗ［ｉ−Ｎｋ］を生成するｗ［ｉ］でのＸＯＲに先立ってｗ［ｉ−１］に適用される。
【００３３】
図４、図６および図８は、それぞれ図３、図５および図７の順方向鍵展開例からの同じ１２８ビット、１９２ビットおよび２５６ビットの暗号鍵についての逆方向鍵展開ルーチンの例を示す。図３と図４とを比較すると、ＡＥＳにおけるラウンド０の事前混合および後続の１０ラウンドに必要な同じ４４ラウンド鍵ワードｗ［０］〜ｗ［４３］が生成されることを見て取ることができる（ラウンド当り４ラウンド鍵ワードが用いられるが、それ
はＡＥＳブロックサイズＮｂが４つの３２ビットワードまたは２５６ビットであるからである）。順方向については、展開は４つの暗号鍵ワードｗ［０］〜ｗ［３］で始まる。逆方向については、以前に順方向鍵展開で入手されメモリに保存された最後の４ワードｗ［４０］〜ｗ［４３］を用いて逆の順序にある別のラウンド鍵ワードｗ［３９］〜ｗ［０］を導き出す。いずれの方向においても、４ワードごとに、すなわちｉが４の倍数（＝Ｎｋ）のときにｗ［ｉ−１］に同一の変換シーケンスが適用される。図３と図４とにおけるｉの同じ値の行を比較すると、逆方向での変換シーケンス（図４）が、順方向の鍵展開方向で適用されるもの（図３）と同じであることが証明される。順方向および逆方向の鍵展開の異なりは最後の２列のワードで見られる。ＸＯＲ演算の対称性は明らかであり、これら最後の２列は上記２つの方向で逆にされている。すなわち順方向においてはｗ［ｉ−Ｎｋ］を用いてｗ［ｉ］を生成し（図３）、逆方向においてはｗ［ｉ］を用いてｗ［ｉ−Ｎｋ］を生成している（図４）。同様に、同じ例示の１９２ビット暗号鍵について図５と図６とを比較すると、逆方向鍵展開によって、ラウンド０での事前混合および１２個の暗号法ラウンドにつき、さらには逆順における等価の逆暗号ラウンドにつき、順方向鍵展開と同じ５２ラウンド鍵ワードが生成されることが示される。同様に、図７および図８において、逆方向鍵展開により、順方向展開から入手されて保存された８ワードを用いて逆方向の６０ラウンド鍵ワードが正しく生成されることが証明される。また、逆方向でも同じＳｕｂＷｏｒｄ（）変換が用いられていることに注目されたい。この発明の逆方向鍵展開のためには逆Ｓ−ｂｏｘ表は用いられず、また必要とされることもない。
【００３４】
図９Ａ，９Ｂを参照して、鍵スケジュール決定回路は、Ｎｋワード（ここでは数にして８まで）を格納する複数の入力レジスタ１１0〜１１7を含む。順方向の暗号化については、これらワードは暗号鍵の最初のＮｋワードである。逆方向の暗号化については、これらレジスタには、システムメモリに格納されている先の暗号化ラウンドからの最後のＮｋ個のラウンドワードがロードされる。入力レジスタ１１0〜１１7は、これら初期ワード値を選択マルチプレクサ１３0〜１３7経由でラウンド鍵レジスタ１５0〜１５7に送り込み、ロードされたワードはこれらレジスタに格納される。ラウンド鍵レジスタ１５0〜１５7の出力は、ｒｋ１〜ｒｋ４およびｒｋ１ｂ〜ｒｋ４ｂで表わされる。これら出力は、再びマルチプレクサ１３0〜１３7を通って反復され、１対のマルチプレクサ１７，１８に処理のため入力される。マルチプレクサ１７は、適当であれば指数ｉについて変換シーケンスにより演算が行なわれるワードｗ［ｉ−１］を受取り、マルチプレクサ１８は順方向の鍵展開方向についてｗ［ｉ−Ｎｋ］を、または逆方向の鍵展開方向についてｗ［ｉ］を受取る。これら２つのワードは、マルチプレクサ２１による選択に応じて、変換回路１９を通過またはバス２０でこれを迂回した後にＸＯＲゲート２３に入力され、その結果であるkeystrand-nextは次のラウンド鍵ワードとなり、これがラウンド鍵レジスタ１５0を更新する。
【００３５】
図１０は、変換シーケンスをラウンド鍵ワードｗ［ｉ−１］に適宜適用するための変換回路１９を示す。マルチプレクサ１７により選択されたワードｗ［ｉ−１］はkeycloud［３１：０］として入力され、４×４バイトのマルチプレクサ２５により分割および回転される。次に、各バイトは、ルックアップ表またはシーオブゲート（sea of gates）として実現され得るＳ−ｂｏｘ２７0〜２７4にそれぞれ入力される。各々のＳ−ｂｏｘがバイト結果を出力する。変換されたワードの最初のバイトはラウンド定数ＸＯＲ回路２９で受取られ、ｉ／Ｎｋに対応する特定のラウンド定数が加えられる。回路２９は、指数バイトｉ［３：０］および鍵サイズ［１：０］の標示（たとえば１２８ビット鍵については００、１９２ビット鍵では０１、そして２５６ビットの鍵には１０）を受取って正しいラウンド鍵定数を生成する。変換されたワードはマルチプレクサ３１により再結合される。Ｎｋ＝８の場合にＳ−ｂｏｘ２７0〜２７4からの代替経路はラウンド定数加算ブロックを飛越し、ｉ  ｍｏｄ  ８＝４である場合に上記バイトを正しい未回転の順序に復元する。この代替経路は、変換されたワード（ｔｅｍｐ）をマルチプレクサ３２と結合する。未変換ワードｗ［ｉ−１］は経路３３で変換を迂回する。正しいｔｅｍｐワードはマルチプレクサ３
５により選択される。
【００３６】
図１１を参照して、鍵スケジュール決定回路に対する電力解析攻撃を防ぐための対抗措置の一例が示され、ここでは１組の異なる種類のＳ−ｂｏｘ実現例が採用されている。たとえば、当該の機能は、すべて異なる電力特性を有するＳＲＡＭ、ＲＯＭ、クラウド回路、および計算回路を用いて実行され得る。Ｓ−ｂｏｘが４つある場合、４！＝２４の異なる置換がある。バイトが上記異なるボックスを通って取る順序をランダムに変更することにより、電力特性が取り得る形状を２４通りにする。図１１においては、ワード入力３７がバイトに分割され、これらバイトは異なるＳ−ｂｏｘ４１0〜４１3に送り込まれる。これらが次に再結合されてＳ−ｂｏｘ変換出力ワード４５が得られる。１組のバイト選択マルチプレクサ３９0〜３９3およびその相補の組のマルチプレクサ４３0〜４３3は乱数発生器４７および選択制御信号発生器４９により制御され、選択された経路の置換およびワードを復元する逆置換を生じさせる。乱数発生器４７としては、発生を支配するいくつかの選択された多項式の組での線形フィードバックシフトレジスタ（ＬＦＳＲ）を用いることができる。選択制御信号発生器４９は図１２に示す表に従い作動する。乱数発生器４７からのＬＦＳＲ出力についての各々の９ビット範囲について、２４の可能な経路置換のうち特定の１つが選択され、対応の選択ＳＥＬおよび逆選択ＳＥＬ-1制御信号が出力される。これに代えて、選択制御信号発生器４９の関数表を変更するか、または追加的にＬＦＳＲもしくは他の乱数発生器４７の指定の擬似乱数機能を変更することによって、他の経路置換を実現することもまた可能である。制御信号発生器４９はルックアップ表としても実現可能である。
【００３７】
図１３を参照して、電力およびタイミング解析に対する対抗措置のもう１つの例としては、事前混合（ラウンド０）作業中に電力雑音を導入するダミー回路がある。このダミー回路は、初期ＸＯＲ事前混合アレイに対する伝搬遅延に揃えられ、１組の乱数発生器、好ましくは線形フィードバックシフトレジスタ５１，５３により生成される擬似ランダム雑音を挿入する。マルチプレクサ要素５５〜５７は、実際の入力回路における対応する要素の遅延に揃えられる。ワード幅ＸＯＲアレイ５９からの出力は実際の平文の暗号法の処理で使用されることはなく、乱数発生器５１，５３の入力にフィードバックされる。それは実際のＸＯＲアレイ（やはりワード幅）の特性に揃えられるが、乱数発生のため異なる入力を有する。また、乱数発生器はワードごとに平文入力を受取るため、ダミー信号は平文に対していくらかの関係を有することができ（ただし暗号鍵に対しては何ら関係を有さない）、ダミー特性からのフィルタ処理をより困難としている。
【００３８】
図１４および図１５を参照すると、１番目のラウンドに先立って平文ブロックを暗号鍵と組合せる事前混合作業は、１番目の暗号ラウンドのためのラウンド鍵ワードが生成されている間においても実行可能である。１２８ビットの平文ブロックが入力バッファ７１で受取られる。暗号鍵の最初の１２８ビットも同様に入力バッファ７２で受取られる。これらのブロックサイズの単位は３２ビットワードへと処理され、それからマルチプレクサ７５を用いて事前混合ＸＯＲアレイ７３へ移される。最後のラウンド（または復号での最初のラウンド）については、ＡＥＳアルゴリズム仕様に従いプログラムされた状態機械で制御されるマルチプレクサ７７による選択に応じ、鍵混合作業は飛越される。それからＡＥＳラウンド１は７９でのＳ−ｂｏｘ変換、８１での列混合作業、そして８３でのラウンド鍵を用いた鍵ＸＯＲ演算へと進む。後続のラウンドは入力部８４で先行のラウンドからのブロックについての変換されたワードを受取る。変換されたワードに対する鍵ＸＯＲ演算のための鍵ストランドは上述の鍵スケジュール決定部に由来する。この鍵スケジュール決定動作は、最初のラウンド鍵（図１５のprestepkey_１〜prestepkey_４）がラウンド０の事前混合動作（preround１）中に生成されるような動作とし、このため最初のroundmを含む後続のラウンドは、待つことを必要とせずに上記ラウンドにとって既に利用可能なラウンド鍵ワードを有している。
【図面の簡単な説明】
【００３９】
【図１】ＡＥＳ・ラインダール暗号化の暗号について指定された入力バイトｘｙのためのＳ−ｂｏｘ換字値の表である。
【図２】１対の１６進法のオペランドについてのＸＯＲ演算の結果の表である。
【図３】１２８ビットの暗号鍵について、ＦＩＰＳ−１９７から取られた先行技術の暗号化方向での鍵展開例を示す表である。
【図４】図３と同じ１２８ビットの暗号鍵について、この発明に従い逆（復号）方向で実現された鍵展開例を示す表である。
【図５】１９２ビット暗号鍵について、ＦＩＰＳ−１９７から取られた先行技術の暗号化方向での鍵展開例を示す表である。
【図６】図５と同じ１９２ビット暗号鍵について、この発明に従い逆（復号）方向で実現された鍵展開例を示す表である。
【図７】２５６ビット暗号鍵について、ＦＩＰＳ−１９７から取られた先行技術の暗号化方向での鍵展開例を示す表である。
【図８】図６と同じ２５６ビット暗号鍵について、この発明に従い逆（復号）方向で実現された鍵展開例を示す表である。
【図９】この発明で用いられる鍵生成ハードウェアの概略的なブロック図である。
【図１０】図９の鍵生成器のためのラウンド鍵変換ハードウェアの概略的なブロック図である。
【図１１】ラウンド鍵変換シーケンスのためのＳ−ｂｏｘハードウェアの代替実施例であって、同一のＳ−ｂｏｘ機能が電力消費パターンの異なる４つの別個の態様で実現され、４つのＳ−ｂｏｘを通る可変経路が乱数発生器（ＬＦＳＲ）で制御されるものを示す図である。
【図１２】図１１の実施例の制御経路で使用されて２５６の乱数入力のいずれかを２４の経路置換選択に変換するためのルックアップ表である。
【図１３】この発明のハードウェア実装における対抗措置として、ＡＥＳ事前混合（ラウンド０）作業中にランダムな電力消費の雑音を導入するダミー回路の概略的なブロック図である。
【図１４】１番目のラウンドについてオンザフライ鍵スケジュール決定に一致する事前混合作業の動作を説明するデータおよび暗号鍵入力経路の概略的なブロック図である。
【図１５】図１４で実行される一致した事前混合／鍵スケジュール決定作業のフロー図である。
【図１】
2005527853.tif 000006
【図２】
2005527853.tif 000007
【図３】
2005527853.tif 000008
【図３Ａ】
2005527853.tif 000009
2005527853.tif 000010
【図４】
2005527853.tif 000011
【図４Ａ】
2005527853.tif 000012
2005527853.tif 000013
【図５】
2005527853.tif 000014
【図５Ａ】
2005527853.tif 000015
2005527853.tif 000016
【図６】
2005527853.tif 000017
【図６Ａ】
2005527853.tif 000018
2005527853.tif 000019
【図７】
2005527853.tif 000020
【図７Ａ】
2005527853.tif 000021
2005527853.tif 000022
2005527853.tif 000023
【図８】
2005527853.tif 000024
【図８Ａ】
2005527853.tif 000025
2005527853.tif 000026
2005527853.tif 000027
2005527853.tif 000028
【図９Ｂ】
2005527853.tif 000029
【図１０】
2005527853.tif 000030
【図１１】
2005527853.tif 000031
【図１２】
2005527853.tif 000032
【図１３】
2005527853.tif 000033
【図１４】
2005527853.tif 000034
【図１５】
2005527853.tif 000035
【手続補正書】
【提出日】平成15年10月20日(2003.10.20)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
高度暗号化規格（ＡＥＳ）すなわちラインダールブロック暗号アルゴリズムに従い鍵展開ルーチンを実行することによりＮｋワードからなる所与の暗号鍵からＮｂ（Ｎｒ＋１）ラウンド鍵ワードｗ［ｉ］からなる鍵スケジュール（ここでＮｂはワード数による暗号ブロックサイズであり、Ｎｒは前記暗号アルゴリズムで採用されるラウンド数である）を生成するように構成された鍵生成器において、前記鍵生成器は前記ラウンド鍵ワードｗ［ｉ］をラウンドごとに必要に応じ「オンザフライ」で生成するように構成されており、その改良は、ラウンド鍵ワードを前記暗号アルゴリズムの復号作業で使用されるように「オンザフライ」で逆方向に生成するための方法を含み、前記方法は、
Ｎｋラウンド鍵ワードの最後の組を格納するためのメモリを設けるステップと、
前記Ｎｋラウンド鍵ワードの最後の組を入手するために暗号化作業中に順方向で前記鍵展開ルーチンを実行し、そのために設けられた前記メモリに前記Ｎｋラウンド鍵ワードの最後の組を格納するステップと、
前記復号作業のために前記鍵生成器をセットするステップと、
格納されたラウンド鍵ワードｗ［ｉ］およびｗ［ｉ−１］を含むＸＯＲ論理演算により先行のラウンド鍵ワードｗ［ｉ−Ｎｋ］を「オンザフライ」で導き出すステップとを含み、ｗ［ｉ−１］は、ｉ  ｍｏｄ  Ｎｋ＝０であるときはいつでも、かつさらにＮｋ＞６およびｉ  ｍｏｄ  Ｎｋ＝４であるときはいつでも前記ＸＯＲ論理演算を適用するのに先立ち変換シーケンスにより最初に変更を加えられ、前記変換シーケンスは、循環バイトシフト、Ｓ−ｂｏｘバイト換字、およびｉ  ｍｏｄ  Ｎｋ＝０のときにおけるラウンド定数によるＸＯＲ演算を含み、前記変換シーケンスは、Ｎｋ＞６およびｉ  ｍｏｄ  Ｎｋ＝４のときにＳ−ｂｏｘバイト換字のみを含み、ｗ［ｉ−１］に対する前記変換シーケンスは、前記鍵展開ルーチンの順方向および逆方向において同一であり、かつＡＥＳ・ラインダールブロック暗号アルゴリズムに従う、鍵生成方法。
【請求項２】
前記鍵生成器はハードウェア回路として実装される、請求項１に記載の鍵生成方法。
【請求項３】
前記Ｓ−ｂｏｘバイト換字を実行するために多数のＳ−ｂｏｘが設けられ、各々のＳ−ｂｏｘは、ＡＥＳ・ラインダールについて指定された同一の機能を有するが、異なる電力消費特性により特徴付けられる異なるハードウェア実装によるものであり、かつ、擬似乱
数発生器が、前記鍵展開ルーチンにおいて換字されるべきさまざまなバイトについて異なるＳ−ｂｏｘへの可変の経路を選択する、請求項２に記載の鍵生成方法。
【請求項４】
前記擬似乱数発生器は、ｎビットの擬似乱数出力と前記擬似乱数出力によりアドレス指定されるルックアップ表とを生成しかつ前記擬似乱数出力に対応する経路選択制御信号を生成する線形フィードバックシフトレジスタである、請求項３に記載の鍵生成方法。
【請求項５】
暗号文を生成するための暗号化ラウンドのシーケンスが始まるのに先立ち平文を暗号鍵と混合する初期事前混合ＸＯＲ演算を有する暗号法アルゴリズムを実行するように構成されたハードウェアブロック暗号回路において、その改良点は、前記事前混合演算を１番目の暗号化ラウンドと組合せる方法を含み、前記方法は、
平文がロードされている間に前記１番目の暗号化ラウンドについてのラウンド鍵ワードを生成するように前記暗号鍵を事前処理するステップを含み、前記事前混合ＸＯＲ演算は平文がロードされている際にも行なわれ、前記方法はさらに、
予め生成された前記最初のラウンド鍵ワードを用いて、ロードされ予め混合された平文に対して前記１番目の暗号化ラウンドを実行するステップを含む、方法。
【国際調査報告】
2005527853.tif 000036
2005527853.tif 000037