(57)【特許請求の範囲】
【請求項１】
プロセッサにより、あるブロックに対して他のブロックとは独立して作用する動作モードを使って先進暗号化標準（AES）処理を複数の固定サイズのブロックに対して実行することを含む方法であって：
前記複数の固定サイズのブロックのうちk個の相続くブロックのセットを前記プロセッサ中のk個のレジスタに記憶する段階であって、kは、ブロックに対してあるAESラウンドについてのAESラウンド演算のシーケンスを実行するAESラウンド命令のレイテンシ（L）以上である、段階と；
前記プロセッサの実行ユニットによって、前記k個の相続くブロックのそれぞれについてプロセッサ・サイクル毎に一つのAESラウンド命令をディスパッチすることによって、前記k個の相続くブロックのセットに対して前記AESラウンド演算のシーケンスを並列に実行する段階とを有する、
方法。
【請求項２】
前記k個のブロックのそれぞれについての前記AESラウンド命令の結果を、前記k個のレジスタのうちそのブロックをもともと記憶していたレジスタに記憶する段階をさらに有する、
請求項１記載の方法。
【請求項３】
各ブロックが128ビットをもつ、請求項１記載の方法。
【請求項４】
前記レジスタがXmmレジスタである、請求項１記載の方法。
【請求項５】
前記AESラウンド命令がパイプラインされる、請求項１記載の方法。
【請求項６】
前記動作モードが、電子コードブック（ECB）、カウンタ、暗号ブロック連鎖メッセージ認証コード（CCM）またはガロア・カウンタ・モード（GCM）である、請求項１記載の方法。
【請求項７】
複数の固定サイズのブロックのうちk個の相続くブロックのセットをk個のレジスタに記憶するためのレジスタ・ファイルであって、kは、ブロックに対してあるAESラウンドについてのAESラウンド演算のシーケンスを実行するAESラウンド命令のレイテンシ（L）以上である、レジスタ・ファイルと；
あるブロックに対して他のブロックとは独立して作用する動作モードを使って先進暗号化標準（AES）処理を複数の固定サイズのブロックに対して実行する実行ユニットであって、前記k個の相続くブロックのそれぞれについてプロセッサ・サイクル毎に一つのAESラウンド命令をディスパッチすることによって、前記k個の相続くブロックのセットに対して前記AESラウンド演算のシーケンスを並列に実行する実行ユニットとを有する、
装置。
【請求項８】
前記実行ユニットが、前記k個のブロックのそれぞれについての前記AESラウンド命令の結果を前記k個のレジスタのうちそのブロックをもともと記憶していたレジスタに記憶する、請求項７記載の装置。
【請求項９】
各ブロックが128ビットをもつ、請求項７記載の装置。
【請求項１０】
前記レジスタがXmmレジスタである、請求項７記載の装置。
【請求項１１】
前記AESラウンド命令がパイプラインされる、請求項７記載の装置。
【請求項１２】
前記動作モードが、電子コードブック（ECB）、カウンタ、暗号ブロック連鎖メッセージ認証コード（CCM）またはガロア・カウンタ・モード（GCM）である、請求項７記載の装置。
【請求項１３】
情報を記憶した機械アクセス可能記憶媒体であって、前記情報は、機械によってアクセスされたときに、該機械に：
あるブロックに対して他のブロックとは独立して作用する動作モードを使って先進暗号化標準（AES）処理を複数の固定サイズのブロックに対して実行することを含む方法であって：
前記複数の固定サイズのブロックのうちk個の相続くブロックのセットを前記機械内のk個のレジスタに記憶する段階であって、kは、ブロックに対してあるAESラウンドについてのAESラウンド演算のシーケンスを実行するAESラウンド命令のレイテンシ（L）以上である、段階と；
前記機械の実行ユニットによって、前記k個の相続くブロックのそれぞれについてプロセッサ・サイクル毎に一つのAESラウンド命令をディスパッチすることによって、前記k個の相続くブロックのセットに対して前記AESラウンド演算のシーケンスを並列に実行する段階とを有する、
方法を実行させる、
機械アクセス可能記憶媒体。
【請求項１４】
前記k個のブロックのそれぞれについての前記AESラウンド命令の結果を、前記k個のレジスタのうちそのブロックをもともと記憶していたレジスタに記憶する段階をさらに有する、
請求項１３記載の機械アクセス可能記憶媒体。
【請求項１５】
各ブロックが128ビットをもつ、請求項１３記載の機械アクセス可能記憶媒体。
【請求項１６】
前記レジスタがXmmレジスタである、請求項１３記載の機械アクセス可能記憶媒体。
【請求項１７】
前記AESラウンド命令がパイプラインされる、請求項１３記載の機械アクセス可能記憶媒体。
【請求項１８】
前記動作モードが、電子コードブック（ECB）、カウンタ、暗号ブロック連鎖メッセージ認証コード（CCM）またはガロア・カウンタ・モード（GCM）である、請求項１３記載の機械アクセス可能記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、先進暗号化標準（AES:  Advanced  Encryption  Standard）に、より詳細にはAESの暗号化／復号の最適化に関する。
【背景技術】
【０００２】
暗号は、アルゴリズムおよび鍵に依拠して情報を保護するツールである。アルゴリズムは複雑な数学的アルゴリズムであり、鍵はビットのストリングである。暗号システムには二つの基本的タイプがある：秘密鍵システムおよび公開鍵システムである。対称システムとも称される秘密鍵システムは、二以上の当事者によって共有される単一の鍵（「秘密鍵」）をもつ。この単一の鍵が情報の暗号化および復号の両方に使われる。
【０００３】
米国国家標準技術局（NIST:  National  Institute  of  Standards  and  Technology）によって連邦情報処理標準（FIPS:  Federal  Information  Processing  Standard）197として公表されている先進暗号化標準（AES）は秘密鍵システムである。AESは、情報を暗号化および復号できる対称ブロック暗号である。
【０００４】
暗号化（暗号）は、秘密鍵（暗号鍵）を使って「平文（plaintext）」と称される理解できるデータを「暗号文（cipher  text）」と称される意味不明な形に変換する一連の変換を実行する。この暗号における変換は次のものを含む：（１）ラウンド鍵（暗号鍵から導出される値）を状態（state）（バイトの二次元配列）に排他的OR（XOR）演算を使って加算する；（２）非線形のバイト置換テーブル（Sボックス）を使って状態を処理する；（３）状態の最後の3行を異なるオフセットにより巡回的にシフトする；（４）状態のすべての列を取り、そのデータを（互いに独立に）混合して新しい列にする。
【０００５】
復号（暗号化の逆）は、暗号鍵を使って「暗号文」ブロックを同じサイズの「平文」ブロックに変換する一連の変換を実行する。逆暗号化における変換は、暗号における前記の変換の逆である。
【０００６】
AES規格において、ラインダール（Rijndael）アルゴリズムは、128ビットのデータ・ブロックを長さ128、192および256ビットの暗号鍵を使って処理するよう規定されている。異なる鍵長は典型的にはAES-128、AES-192およびAES-256と称される。
【０００７】
AESアルゴリズムは、平文を暗号文に、あるいは暗号文を平文に10回、12回または14回の相続くラウンドで変換する。ラウンド数は鍵長に依存する。
【発明の概要】
【発明が解決しようとする課題】
【０００８】
パラレル・モードでの先進暗号化標準（AES）の暗号化および復号を最適化する。
【課題を解決するための手段】
【０００９】
本発明の課題は請求項記載の手段によって達成される。
【００１０】
特許請求される事項の実施形態の特徴は、以下の詳細な記述が進むにつれ、また図面を参照することで明白になるであろう。図面において、同様の参照符号は同様の部分を描いている。
【図面の簡単な説明】
【００１１】
【図１】AES暗号化および復号を汎用プロセッサで実行するための命令を含むシステムのブロック図である。
【図２】図１に示したプロセッサのある実施形態のブロック図である。
【図３】本発明の原理に従って異なるデータ・ブロックに対する独立した処理を並列に実行することによりAES暗号化／復号処理のスループットを改善する方法のある実施形態を示す流れ図である。
【図４】サイクル当たり一つのAESラウンド命令をディスパッチする（dispatch）例を示す図である。
【発明を実施するための形態】
【００１２】
以下の詳細な記述は特許請求される事項の例示的な実施形態を参照しつつ進められるが、当業者には数多くの代替、修正および変形が明白であろう。したがって、特許請求される事項は広義に見られ、付属の請求項において述べられていることによってのみ定義されることが意図されている。
【００１３】
先進暗号化標準（AES）アルゴリズムは、計算集約的なアルゴリズムであり、典型的にはソフトウェアにおいて、あるいは特殊目的のプロセッサにおいて実行される。AESアルゴリズムは、メモリに記憶されているロード／記憶／インクリメント中央処理装置（CPU）命令のシーケンスを実行することによって、ソフトウェアで実行される。AESアルゴリズムは、平文または暗号文の各バイトを変換するために多くのCPUサイクルを消費するので、この変換は遅い。よって、暗号化は典型的にはコンピュータに記憶されている情報の部分集合、たとえば「トップ・シークレット」と分類されているような情報を暗号化するためにのみ使用される。しかしながら、コンピュータに記憶されている情報のさらに多くの部分を暗号化する必要がある。たとえば、モバイル・コンピュータに記憶されている全情報が暗号化されれば、モバイル・コンピュータが盗まれてもその情報は保護されるであろう。
【００１４】
AESは128ビットのブロックに128、192または256ビットの鍵サイズで作用するブロック暗号である。AESアルゴリズムは、10回、12回または14回の相続くラウンドで、128ビットの平文ブロックを128ビットの暗号文のブロックに変換し（暗号化）、あるいは128ビットの暗号文のブロックを128ビットの平文のブロックに変換する（復号）。ラウンド数は鍵サイズ（128、192または256ビット）に依存する。各ラウンドについて処理シーケンスが逐次反復される（10、12または14回）。暗号化のための処理シーケンスは次のことを含む：（１）ラウンド鍵（暗号鍵から導出される値）を状態（state）（バイトからなる128ビットの二次元配列）に排他的OR（XOR）演算を使って加算する；（２）非線形のバイト置換テーブル（Sボックス）を使って状態を処理する；（３）状態の最後の3行を異なるオフセットにより巡回的にシフトする；（４）状態のすべての列を取り、そのデータを（互いに独立に）混合して新しい列にする。
【００１５】
ブロック暗号は、複数の動作モードのうちの一つを使用しうる。動作モードは、電子コードブック（ECB:  Electronic  Code  Book）、暗号ブロック連鎖（CBC:  Cipher-Block  Chaining）、出力フィードバック（OFB:  Output  Feedback）、カウンタ（Counter）および暗号フィードバック（CFB:  Cipher-Feedback）を含み、任意の長さのメッセージについて秘匿性を提供する。暗号ブロック連鎖によるメッセージ認証コードを備えたカウンタ（CCM:  Counter  with  Cipher  Block  Chaining-Message  Authentication  Code）、ガロア・カウンタ・モード（GCM:  Galois  Counter  Mode）およびオフセット・コードブック・モード（OCM:  Offset  Codebook  Mode）といった他の動作モードは、秘匿性とメッセージ完全性の両方を保証する。
【００１６】
ECBモードでは、暗号化されるべき平文はnビットのブロックに分割され、各ブロックが別個に暗号化される。すなわち、ブロックは他のブロックとは独立して暗号化される。CBCモードでは、平文は一時にnビットずつ処理され、平文ブロックの暗号化を前のブロックの暗号化に依存して行うために連鎖機構が使用される。たとえば、暗号化処理のためのCBC動作モードは下記の表１に示されるように記述されうる。
【００１７】
C-1＝初期化ベクトル（IV:  initialization  vector）
Cj＝AES_ENCRYPT(Pj  XOR  Cj-1)  for  j＝1,2,…,暗号化すべきブロック数（NB:  number  of  blocks  to  encrypt）
ここで、
Cjは第j暗号文ブロックであり、
Pjは第j平文ブロック（入力）である。
表１
【００１８】
CBC動作モードでは、CjはCj-1が計算される前には計算できない。よって、CBC動作モードはシリアル・モードである。
【００１９】
パラレル動作モードは、あるブロックの暗号化／復号が他のブロックの暗号化／復号の結果とは独立である動作モードである。たとえば、ECBおよびカウンタ動作モードはパラレル動作モードである。下記で、ECBモードを使ったAES暗号化処理についての擬似コードの例を表２に示し、カウンタ動作モードを使ったAES暗号化処理についての擬似コードの例を表３に示す。
【００２０】
for  j  from  1  to  暗号化すべきブロック数（NB）
TargetBuffer[j]＝AES_ENCRYPT_PROCEDURE(DataBlock[j],cipher_key)
End  loop
ここで、
DataBlock  //暗号化すべきデータを保持する128ビットのエントリーをNB個もつバッファ
TargetBuffer  //暗号化された結果を記憶する128ビットのエントリーをNB個もつバッファ（DataBlockと同じでもよい）
表２
【００２１】
Initialize  COUNTER  （ランダムな初期化ベクトル（IV））
for  j  from  1  to  暗号化すべきブロック数（NB）
Tmp1＝AES_ENCRYPT_PROCEDURE(COUNTER,cipher_key)
TargetBuffer[j]=XOR(Tmp1,DataBlock[j])
End  loop
ここで、
DataBlock  //暗号化すべきデータを保持する128ビットのエントリーをNB個もつバッファ
TargetBuffer  //暗号化された結果を記憶する128ビットのエントリーをNB個もつバッファ（DataBlockと同じでもよい）
表３
【００２２】
表２および表３における暗号化処理（AES_ENCRYPT_PROCEDURE）は、汎用プロセッサにおいてAES暗号化および復号を実行するための命令セット拡張において実行されうる。単一のAES暗号化処理はシリアルな動作のシーケンスを含み、それはAES命令のシリアルなシーケンスを介して実行されうる。複数の128ビット・データ・ブロックの暗号化を実行するための命令のシーケンスの例を下記で図４に示す。
【００２３】
for  (i=1;  i＜NB;  i++)
temp＝Load(DataBlock[i])
temp＝xor(temp,RK[0]);    //ラウンド０
for(j=1;  j＜10;  j++)  //10回のAESラウンドについて
temp＝AESENC(temp,RK[j]);
temp＝AESENCLAST(temp,RK[10]);
Store  temp  to  TargetBuffer[i]
ここで、
NBは暗号化すべきブロック数；
IVはカウンタを初期化する（initialize）ために使われるランダムな数；
DataBlockは暗号化すべきデータを記憶するバッファ；
TargetBufferは暗号化した結果を記憶するバッファ；
RKはラウンド鍵（Round  keys）を記憶するバッファ；
tempは128ビットの変数である。
表４
【００２４】
表４に示されたAES命令（AESENC、AESENCLAST）は、128ビット変数（temp）に記憶されたデータ（状態とも称される）を、AES規格（FIPS刊行物197）によって定義されるようにシリアルに処理する。該データを処理するための動作のシリアルなシーケンスの例を表５に示す。
【００２５】
For  i  from  1  to  N_BLOCKS  do
Xmm1＝BLOCK[i]    //ロード
Xmm1＝AESENC(Xmm1,RK[1])
Xmm1＝AESENC(Xmm1,RK[2])
Xmm1＝AESENC(Xmm1,RK[3])
…
Xmm1＝AESENC(Xmm1,RK[9])
Xmm1＝AESENCLAST(Xmm1,RK[10])
store  Xmm1
End
表５
【００２６】
暗号化すべきN_Blocksのそれぞれについて、データ・ブロックはレジスタに記憶される。たとえば128ビットをもつXmmレジスタ（Xmm1）が128ビットのブロックを記憶するために使用されうる。10回の暗号化ラウンドは、そのデータ・ブロックに対して直列に実行される。10ラウンドのAES処理のうちラウンド1から9については、AESENC命令が呼び出され、ラウンド鍵および直前のラウンドの結果もしくは初期ブロック・データ（ラウンド1の場合）を使ってラウンド処理を実行する。AESENCLAST命令は、最後のラウンド（今の例ではラウンド10）を処理するために呼び出される。
【００２７】
AESラウンド命令（AESENC、AESENCLAST）のレイテンシ（latency）がLプロセッサ・サイクルと表されるとする。ロード、記憶および他のオーバーヘッドのためのサイクルを無視すると、表５の例に示される10回のAESラウンドのためのN_BLOCKSの処理は、表５に示した順序で処理されるとすると、約N_BLOCKS*10*Lサイクルを消費する。明らかに、N_Blocksの暗号化／復号を実行する全体としてのレイテンシは、個々のAES命令（AESENC、AESENCLAST）のレイテンシに依存する。
【００２８】
本発明のある実施形態では、本発明の原理に従って複数のデータ・ブロックを並列に暗号化する（復号する）ことによって、AESラウンド命令のレイテンシ（L）の効果が軽減され、AES暗号化／復号処理を実行するために必要とされる全体としてのレイテンシの低下につながる。パラレル動作モードでは、異なるデータ・ブロックの異なる独立した暗号化（復号）は、前の命令が完了するのを待つことなく毎サイクルにおいてAESラウンド命令をディスパッチすることによって、並列に実行されうる。
【００２９】
図１は、汎用プロセッサにおいてAES暗号化および復号を実行するための命令を含むシステム１００のブロック図である。システム１００は、プロセッサ１０１、メモリ・コントローラ・ハブ（MCH:  Memory  Controller  Hub）（またはグラフィクス・メモリ・コントローラ・ハブ（GMCH:  Graphics  Memory  Controller  Hub））１０２および入出力（I/O）コントローラ・ハブ（ICH:  Input/Output  Controller  Hub）１０４を含む。MCH１０２は、プロセッサ１０１とメモリ１０８の間の通信を制御するメモリ・コントローラ１０６を含む。プロセッサ１０１およびMCH１０２は、システム・バス１１６を通じて通信する。
【００３０】
プロセッサ１０１は、単一コアのインテル（登録商標）・ペンティアム（登録商標）ＩＶ・プロセッサ、単一コアのインテル・セレロン・プロセッサ、インテル（登録商標）・XScaleプロセッサまたはペンティアム（登録商標）Ｄ、インテル（登録商標）・ジーオン（登録商標）・プロセッサもしくはインテル（登録商標）・コア（登録商標）・デュオ・プロセッサといったマルチコア・プロセッサまたは他の任意の型のプロセッサといった複数のプロセッサのいかなるものであってもよい。
【００３１】
メモリ１０８は動的ランダム・アクセス・メモリ（DRAM:  Dynamic  Random  Access  Memory）、静的ランダム・アクセス・メモリ（SRAM:  Static  Random  Access  Memory）、同期型動的ランダム・アクセス・メモリ（SDRAM:  Synchronized  Dynamic  Random  Access  Memory）、倍速データレート２（DDR2:  Double  Data  Rate  2）RAMまたはランバス動的ランダム・アクセス・メモリ（RDRAM:  Rambus  Dynamic  Random  Access  Memory）または他のいかなる型のメモリであってもよい。
【００３２】
ICH１０４は、高速のチップからチップへの相互接続１１４を使って直接メディア・インターフェース（DMI:  Direct  Media  Interface）のようなMCH１０２に結合されうる。DMIは、二つの一方向レーンを介して毎秒2ギガビットの並行転送レートをサポートする。
【００３３】
ICH１０４は、該ICH１０４に結合された少なくとも一つの記憶装置１１２との通信を制御するための記憶装置I/Oコントローラ１１０を含んでいてもよい。記憶装置はたとえば、ディスク・ドライブ、デジタル・ビデオ・ディスク（DVD）・ドライブ、コンパクト・ディスク（CD）・ドライブ、独立したディスクの冗長アレイ（RAID）、テープ・ドライブまたは他の記憶装置であってもよい。ICH１０４は、記憶プロトコル相互接続１１８を介して、シリアル付属小型コンピュータ・システム・インターフェース（SAS:  Serial  Attached  Small  Computer  System  Interface）またはシリアル先進技術付属物（SATA:  Serial  Advanced  Technology  Attachment）といったシリアル記憶プロトコルを使って、記憶装置１１２と通信してもよい。
【００３４】
プロセッサ１０１は、AES暗号化および復号処理を実行するためのAES機能１０３を含む。AES機能１０３は、メモリ１０８に記憶されているおよび／または記憶装置１１２に記憶されているような情報を暗号化または復号するために使用されうる。
【００３５】
図２は、図１に示したプロセッサ１０１のある実施形態のブロック図である。プロセッサ１０１は、レベル１（L1）命令キャッシュ２０２から受領されるプロセッサ命令をデコードするためのフェッチおよびデコード・ユニット２０６を含む。プロセッサ命令を実行するために使用されるべきデータはレジスタ・ファイル２０８に記憶されうる。ある実施形態では、レジスタ・ファイル２０８は複数の128ビット・レジスタを含み、これらの128ビット・レジスタがAESラウンド命令による使用のためのデータを記憶するためにAESラウンド命令によって使用される。
【００３６】
ある実施形態では、レジスタ・ファイル２０８は、ストリーミング（単一命令複数データ（SIMD））拡張（SSE:  Streaming  (Single  Instruction  Multiple  Data)  Extension）（SSE）命令セットをもつインテル（登録商標）・ペンティアム（登録商標）・MMXプロセッサに設けられている128ビットのMMXレジスタと同様の128ビット・レジスタの群である。SIMDプロセッサでは、データは、一時に一つの128ビット・ブロックずつロードして、複数の128ビット・ブロックにおいて処理される。
【００３７】
フェッチおよびデコード・ユニット２０６は、L1命令キャッシュ２０２からマクロ命令をフェッチして、該マクロ命令をデコードし、該マクロ命令をマイクロ演算（μop:  micro  operation）と呼ばれる単純な演算に分解する。マイクロ演算はマイクロコード読み出し専用メモリ（ROM）２１４に記憶されうる。パイプライン化されている実行ユニット２１０は、それらのマイクロ演算をスケジューリングし、実行する。図示した実施形態では、実行ユニット２１０中のAES機能１０３はAESラウンド命令のセットのためのマイクロ演算を含む。AES命令は完全にパイプライン化され（fully  pipelined）、それによりプロセッサ（CPU）は、処理するためのデータの準備ができていれば、毎サイクルにおいて命令をディスパッチしうる。待避ユニット（retirement  unit）２１２は、実行された命令の結果をレジスタまたはメモリに書き込む。AESラウンド命令によって使用されるラウンド鍵２１６は、L1データ・キャッシュ２０４に記憶され、AESラウンド命令のいずれかを実行するためのマイクロ演算による使用のために、実行ユニット２１０にロードされてもよい。ラウンド鍵２１６をL1データ・キャッシュ２０４に記憶することは、サイド・チャネル攻撃、たとえばシステム１００に記憶されている暗号化された情報へのアクセスを得るためにラウンド鍵を得ようとする試みからラウンド鍵２１６を保護する。
【００３８】
AESラウンド命令がフェッチおよびデコード・ユニット２０６によってデコードされたのち、実行ユニット２１０によるAESラウンド命令の実行は、マイクロコードROM２１４に記憶されていてもよいAESラウンド命令に関連付けられたマイクロ演算の実行に関わる。
【００３９】
ある実施形態では、暗号化ラウンド、復号ラウンド、暗号化最終ラウンドおよび復号最終ラウンドを実行するための別個のAESラウンド命令を含むAES命令セットが設けられる。ある実施形態では、各AESラウンド命令は一意的な動作コード（operation  code）（オペコード（opcode））をもつ。固定幅ラウンド鍵（たとえば128ビット）についてのある実施形態についてのAES命令セットにおけるAESラウンド命令を、下記で表６に示す。
【００４０】
AESENC  xmmsrcdst  xmm
入力：データ（＝宛先）、ラウンド鍵
出力：ラウンド鍵を使ったAESラウンドを通じた変換後のデータ
AESENCLAST  xmmsrcdst  xmm
入力：データ（＝宛先）、ラウンド鍵
出力：ラウンド鍵を使ったAES最終ラウンドを通じた変換後のデータ
AESDEC  xmmsrcdst  xmm
入力：データ（＝宛先）、ラウンド鍵
出力：ラウンド鍵を使ったAESラウンドを通じた変換後のデータ
AESDECLAST  xmmsrcdst  xmm
入力：データ（＝宛先）、ラウンド鍵
出力：ラウンド鍵を使ったAES最終ラウンドを通じた変換後のデータ
表６
【００４１】
このAES命令セットは四つのAESラウンド命令（暗号化、復号、最終ラウンド暗号化、最終ラウンド復号）を含む。このAES命令セットにおけるAESラウンド命令は、最終ラウンドを除いたすべてのラウンドのために使用されることになる暗号化および復号のラウンド演算を実行する単一ラウンド演算を含む。たとえば、表６のAESENC単一ラウンド命令では、入力データは128ビット・レジスタ（xmmsrcdst）に記憶され、ラウンド鍵は別の128ビット・レジスタ（Xmm）に記憶される。この命令は、128ビットのxmmsrcdstレジスタに記憶されている入力データ（ソース）に対してAESラウンド演算を実行し、128ビットのxmmsrcdstレジスタに記憶されている入力データを、ラウンド演算の実行の結果をもって上書きする。こうして、xmmsrcdstはまず入力データを記憶し、のちにAESラウンド演算の結果を記憶する。
【００４２】
鍵のサイズは128ビット、192ビットまたは256ビットであってよい。実行されるべきラウンド数（n）は、鍵のサイズに依存して1、10、12または14でありうる。各ラウンド鍵は固定サイズ（128ビット）である。ラウンド数の値10、12、14では、AESマイクロ演算は、128ビット、192ビットまたは256ビットの鍵サイズについて、標準的なAES暗号化および復号を実行しうる。
【００４３】
多くのブロックに同じ鍵が使われるとき、各ラウンドについてのラウンド鍵（鍵スケジュール）が事前計算されてメモリに記憶されていてもよい（たとえば、レベル１のデータ・キャッシュ２０４内にラウンド鍵２１６）。ラウンド鍵２１６は、その鍵についての鍵スケジュールを記憶するための10の要素をもつ配列（RK）を含んでいてもよい。AES-128暗号化のための入力鍵はRK[0]に記憶され、９個のラウンド鍵RK[0]‐RK[1]が事前計算される。
【００４４】
AES命令セットは、最後の復号ラウンドのためのAES復号命令および最後の暗号化ラウンドのためのAES暗号化命令をも含む。たとえば、表１のAESENCLAST単一ラウンド命令では、入力データは128ビット・レジスタ（xmmsrcdst）に記憶され、ラウンド鍵は別の128ビット・レジスタ（Xmm）に記憶される。この命令は、xmmsrcdstレジスタに記憶されている入力データ（ソース）に対してAESラウンド演算を実行し、xmmsrcdstレジスタに記憶されている入力データを、ラウンド演算の実行の結果をもって上書きする。こうして、xmmsrcdstはまず入力データを記憶し、のちにAESラウンド演算の結果を記憶する。Xmmレジスタはラウンド演算のためのラウンド鍵を記憶する。
【００４５】
ある実施形態では、レジスタ・ファイル３０４はAES命令によって使用されうる複数の128ビット・レジスタをもつ。これらの128ビット・レジスタは、ソース・オペランド（単数または複数）、ラウンド鍵およびAES命令の結果を記憶しうる。最初のラウンドについては、AES命令は、暗号化されるべき128ビットの平文または復号されるべき128ビットの暗号文でありうるソース・オペランドを受領する。
【００４６】
図３は、本発明の原理に従って異なるデータ・ブロックに対する独立した処理を並列に実行することによりAES暗号化／復号処理のスループットを改善する方法のある実施形態を示す流れ図である。
【００４７】
AES処理のスループットの改善は、あるデータ・ブロックの暗号化／復号のフローを、処理すべきデータを提供する別のデータ・ブロックの暗号化／復号のフローと並行して走ることを許容し、毎サイクルにAESラウンド命令がディスパッチされることを許容することによってなされる。データ・ブロックが並列に処理されうるのは、（１）複数データ・ブロックにわたって同じ暗号鍵が使われる、すなわち鍵スケジュールが一度生成され、その同じ鍵スケジュールを使って複数データ・ブロックが処理され、かつ（２）AESラウンドが、単一の完全にパイプライン化されたAESラウンド命令を使って実行される場合である。毎サイクルに一度AESラウンド命令をディスパッチすることは、たとえ各AESラウンド命令のレイテンシが１サイクルより大きくても、AES暗号化／復号処理のスループットを上げる。
【００４８】
AES-128暗号化処理について、すなわち128ビットのデータ・ブロックおよび128ビットの鍵を使った10回のAESラウンドでのAES暗号化処理について、実施例を述べる。下記の表７は、並列して異なるデータ・ブロックに対する独立した処理を実行することによりAES暗号化のスループットを最大化するために使用されうるソフトウェア命令の例を示している。
【００４９】
For  i  from  0  to  N_BLOCKS/8−1  do
xmm1＝BLOCK[8*i+1],  xmm2＝BLOCK[8*i+2];  …  xmm8＝BLOCK[8*i+8]
xmm1＝AESENC(xmm1,RK[1])
xmm2＝AESENC(xmm2,RK[1])
xmm3＝AESENC(xmm2,RK[1])
…
xmm8＝AESENC(xmm8,RK[1])
xmm1＝AESENC(xmm1,RK[2])
xmm2＝AESENC(xmm2,RK[2])
…
xmm8＝AESENC(xmm8,RK[2])
…
xmm1＝AESENCLAST(xmm1,RK[10])
xmm2＝AESENCLAST(xmm2,RK[10])
…
xmm8＝AESENCLAST(xmm8,RK[10])
store  xmm1;  store  xmm2;  …  store  xmm8
End
表７
【００５０】
表７を参照すると、各Xmmレジスタを使う処理は他のXmmレジスタを使う処理と独立しているので、AESラウンド命令「AESENC」は毎サイクルにディスパッチされる。先に論じたように、これは、並列動作モードの性質のためである。たとえば、ECBモードでは、暗号化すべき平文はnビット・ブロックに分割され、各ブロックが別個に暗号化される。すなわち、ブロックは他のブロックとは独立して暗号化される。使用されるXmmレジスタの数（この例では8）が命令レイテンシ（L）、すなわち命令を完了させるためのサイクル数より大きいまたはこれに等しく選ばれる場合、AESラウンド命令は、複数のAESラウンドにまたがってでさえ、毎サイクルにディスパッチされることができる。
【００５１】
ブロック３００では、暗号化／復号されるべき複数のデータ・ブロックが複数のレジスタ（たとえば複数の128ビットXmmレジスタ）に記憶される。128ビット・レジスタをもつある実施形態では、AESのデータ・ブロック・サイズは128ビットなので、異なるデータ・ブロックがk個の128ビット・レジスタのそれぞれに記憶される。パフォーマンスを最大にするため、前記異なるデータ・ブロックを記憶するために使用されるレジスタ数はAESラウンド命令のレイテンシに依存する。これは、毎サイクルに一つのAESラウンド命令がディスパッチされ、複数の異なるデータ・ブロックが並列して処理されうることを許容する。処理はブロック３０２に続く。
【００５２】
ブロック３０２では、AES暗号化／復号処理のラウンド0で実行される処理が、他のラウンドで実行される処理とは異なっている。よって、ラウンド0での処理は、k個の128ビット・レジスタに記憶されているk個の異なるデータ・ブロックのそれぞれに対して逐次的に実行される。処理はブロック３０４に続く。
【００５３】
ブロック３０４では、すべての他のラウンド（たとえばAES-128についてはラウンド1ないし10）について同じAESラウンド命令がディスパッチされる。現在ラウンドについてk個のレジスタに記憶されているk個の異なるデータ・ブロックのそれぞれについて、当該ラウンドに関連付けられたラウンド鍵［RK］を使って、サイクル当たり一つのAES命令がディスパッチされる。k個のレジスタに記憶されているk個の異なるデータ・ブロックのそれぞれについてAESラウンド命令がディスパッチされたのち、処理はブロック３０６に続く。
【００５４】
ブロック３０６では、そのAES処理のためにさらなるラウンドがあれば、処理はブロック３０４に続いて次のラウンドを処理する。さらなるラウンドがなければ、処理はブロック３０８に続く。
【００５５】
ブロック３０８では、そのAES処理のために処理されるべき他のデータ・ブロックがあれば、処理はブロック３００に続き、次のデータ・ブロック（単数または複数）を前記k個のレジスタにロードする。他のデータ・ブロックがなければ、処理はブロック３１０に続き、AES処理の結果を返す。
【００５６】
図４は、サイクル当たり一つのAESラウンド命令をディスパッチする例を示している。図４に示される例では、レジスタ数（k）およびAESラウンド命令レイテンシ（L）はいずれも6である。図４は、表７に示され、図３のブロック３０４との関連で論じたforループの一つについてのAES命令のディスパッチを示している。k＝L＝6のときにラウンド2についてのforループについてディスパッチされる命令は、明示的には下記の表８のように書ける。
【００５７】
Xmm1＝AESENC
(Xmm1,RK[1])
Xmm2＝AESENC
(Xmm2,RK[1])
Xmm3＝AESENC
(Xmm3,RK[1])
Xmm4＝AESENC
(Xmm4,RK[1])
Xmm5＝AESENC
(Xmm5,RK[1])
Xmm6＝AESENC
(Xmm6,RK[1])
表８
【００５８】
この例では、レジスタはXmmレジスタ・ファイルにおけるXmmレジスタであり、Xmmレジスタの6つ（Xmm1〜Xmm6とラベルされる）は6つの異なるデータ・ブロックを記憶するために使用される。しかしながら、本発明はXmmレジスタに限定されるものではなく、AESラウンドのために128ビット・データ・ブロックを記憶することができ、AESラウンド命令によってアクセス可能ないかなるレジスタを使ってもよい。Xmm1を使う処理は他のXmmレジスタ（Xmm2、…、Xmm6）のそれぞれを使う処理とは独立しているので、AESENC命令は毎サイクル、ディスパッチできる。理想的なスケジュール条件のもとでは、このforループは完了するのにk＋L−1（6＋6−1＝11）サイクルかかる。
【００５９】
図３を参照すると、Lおよびkの両方が6であるシステムにおいては、毎サイクル、AESENC命令がディスパッチされる。各ラウンド（ラウンド0以外）について、最初の６つの命令は同じラウンド鍵RKを使って６つの異なるXmmレジスタ（Xmm1〜Xmm6）上で動作する。たとえば、サイクル1ではXmm1およびRK[1]を使ってAESENC命令がディスパッチされ、サイクル2ではXmm2およびRK[2]を使ってAESENC命令がディスパッチされる。サイクル1においてディスパッチされたAESENC命令は6サイクルのレイテンシをもち、よってサイクル6の終わりに完了される。
【００６０】
サイクル7においてディスパッチされる7番目のAESENC命令は、Xmm1レジスタに記憶されている7番目のデータ・ブロックをラウンド鍵RK[2]とともに使うことができる。これは、その時点までには、サイクル1においてXmm1レジスタに記憶された第一のデータ・ブロックおよびラウンド鍵RK[1]を使ってディスパッチされたAESENC命令はすでに完了している（6サイクルのレイテンシに基づく）からである。よって、6つのAESENC命令が、それぞれ6つのXmmレジスタの一つに記憶されている異なるデータ・ブロックを使って、並列に動作してもよい。こうして、前記レジスタの複数に記憶されているデータ・ブロックを使う第二のAESラウンドは、全部で11サイクル後に完了する。これに対し、これら二つのAESラウンドについてのデータ・ブロックが表５に示した例との関連で先に論じたように直列に処理されたとしたら、12サイクル後である。AES-128処理についての全10回のAESラウンドが完了するまで、各サイクルにおいてAESENC命令（またはAESENCLAST命令）がディスパッチされる。
【００６１】
kをデータ・ブロックを記憶するために利用可能なレジスタの数に依存して選択されるものとして、論じたように、k個のデータ・ブロックが並列に暗号化されうる。レジスタ数（k）≧AES命令レイテンシ（L）であれば、AES命令は毎サイクルにディスパッチされうる。これは「複数のAESラウンドにまたがって」であってもよい。すなわち、ある特定のAESラウンドについてのAESラウンド命令のすべてが、次のAESラウンドについてのAESラウンド命令をディスパッチするのに先立って完了される必要はない。
【００６２】
たとえば、ラウンド鍵RK[1]を使ってAESラウンド1を処理するために第一のレジスタが使用される場合、該第一のレジスタは、kサイクルが経過してしまうまではラウンド鍵RK[2]を使ってAESラウンド2を処理するために使用することはできない。よって、k≧Lであれば、AESラウンド1のためにAES命令がディスパッチされるk個のサイクルがあって、k+1番目のサイクルでは、ラウンド鍵RK[2]を用いて処理されるべきAESラウンド2のためのデータ・ブロックを記憶するために第一のレジスタが利用可能である。
【００６３】
並列してk個の異なるデータ・ブロックを処理することは、kデータ・ブロック当たり、排他的OR（XOR）演算を実行するAESラウンド0についての約kサイクルに加えて、他のNR個のAESラウンドを処理するためにさらなるNR*k＋L−1サイクルを必要とする。したがって、スループットは、kデータ・ブロック当たり（NR*k＋L−1）サイクルによって見積もれる。これはデータ・ブロック当たりNR＋(L−1)/kサイクルである。
【００６４】
パフォーマンスは利用可能なレジスタ数によって、およびAESラウンド命令のレイテンシによって制約される。ラウンド鍵（RK）はメモリから読み込まれることもできるし（レジスタ‐メモリ・モード）、別のレジスタにロードされることもできる（レジスタ‐レジスタ・モード）。レジスタ‐メモリ・モードは、ラウンド鍵が最初に読み込まれたのち第一レベルのキャッシュに記憶されるならば、より高いパフォーマンスを提供しうる。
【００６５】
前記のAESラウンド命令を使用しないAES-128の実装は、バイト当たり約12サイクルを消費する。記憶／ロード／インクリメントおよび他のオーバーヘッドのレイテンシを無視し、k＝L＝8とすると、シリアル・データ・モードでは、前記のAESラウンド命令を使用するAES-128（10ラウンド）暗号化は、128ビット（16バイト）当たり約10*Lサイクルを消費する。すなわち、約5サイクル／バイトである。複数の異なるデータ・ブロックを並列に処理することにより、先に論じたように、8ブロックの暗号化はNR*k＋L−1サイクルを消費する。つまり、8ブロック当たり約72サイクルである（0.56サイクル／バイト）。このように、異なるデータ・ブロックに対する独立した処理を並列に実行することは、表５との関連で論じたデータを処理するためのシリアルな処理シーケンスを使うときよりほとんど9倍のパフォーマンス増を達成する。
【００６６】
処理を並列に実行することにより、AESラウンド命令のレイテンシ（L）は、レジスタ数（k）がL以上である限り、「隠蔽される」。これは、あるブロックに対して他のブロックとは独立に動作する動作モード、たとえばECB、CCM、GCMおよびカウンタを含む動作モードを使うAES処理のための暗号化／復号のためのAESラウンド命令の効率的な使用を許容する。
【００６７】
本発明の実施形態に関わる方法がコンピュータによって使用可能な媒体を含むコンピュータ・プログラム・プロダクトにおいて具現されてもよいことは当業者には明白であろう。たとえば、そのようなコンピュータによって使用可能な媒体は、コンピュータ読み取り可能なプログラム・コードが記憶されているコンパクト・ディスク読み出し専用メモリ（CD-ROM）ディスクもしくは通常のROMデバイスのような読み出し専用メモリ・デバイスまたはコンピュータ・ディスケットからなっていてもよい。
【００６８】
本発明の実施形態についてその実施形態を参照しつつ具体的に図示し、説明してきたが、当業者は、付属の請求項が網羅する本発明の実施形態の範囲から外れることなく、形および詳細におけるさまざまな変更がなしうることを理解するであろう。
【符号の説明】
【００６９】
１０１  プロセッサ
１０２  メモリ・コントローラ・ハブ（MCH）
１０３  AES暗号化／復号処理
１０４  入出力コントローラ・ハブ
１０６  メモリ・コントローラ
１０８  メモリ
１１０  記憶装置入出力コントローラ
１１２  記憶装置
２００  バフ・インターフェース・ユニット
２０２  レベル１の命令キャッシュ
２０４  レベル１のデータ・キャッシュ
２０６  フェッチおよびデコード・ユニット
２０８  レジスタ・ファイル
２１０  実行ユニット
２１２  待避ユニット
２１４  マイクロコードROM
２１６  ラウンド鍵
３００  k個のレジスタにk個の異なるデータ・ブロックをロード
３０２  k個のデータ・ブロックのそれぞれについてAESラウンド0処理を実行
３０４  k個のレジスタに記憶されている各データ・ブロックについて１ラウンドのためのラウンド処理を実行するラウンド命令をディスパッチ
３０６  さらなるラウンド［RK］？
３０８  さらなるデータ・ブロック？
３１０  結果を返す
【図１】
0005020987.tif 000002
【図２】
0005020987.tif 000003
【図３】
0005020987.tif 000004
【図４】
0005020987.tif 000005