パラレル・モードでの先進暗号化標準(AES)の暗号化および復号を最適化する方法および装置

【課題】パラレルモードでの先進暗号化標準(AES)の暗号化及び復号を最適化する。
【解決手段】異なるデータ・ブロックの異なる独立した暗号化(復号)が、パイプライン化された実行ユニットをもつシステムにおいて、AESラウンド命令を毎サイクルにディスパッチすることによって並列に実行され、暗号化/復号のスループットが向上される。

【発明の詳細な説明】
【技術分野】
【0001】
本開示は、先進暗号化標準(AES: Advanced Encryption Standard)に、より詳細にはAESの暗号化/復号の最適化に関する。
【背景技術】
【0002】
暗号は、アルゴリズムおよび鍵に依拠して情報を保護するツールである。アルゴリズムは複雑な数学的アルゴリズムであり、鍵はビットのストリングである。暗号システムには二つの基本的タイプがある:秘密鍵システムおよび公開鍵システムである。対称システムとも称される秘密鍵システムは、二以上の当事者によって共有される単一の鍵(「秘密鍵」)をもつ。この単一の鍵が情報の暗号化および復号の両方に使われる。
【0003】
米国国家標準技術局(NIST: National Institute of Standards and Technology)によって連邦情報処理標準(FIPS: Federal Information Processing Standard)197として公表されている先進暗号化標準(AES)は秘密鍵システムである。AESは、情報を暗号化および復号できる対称ブロック暗号である。
【0004】
暗号化(暗号)は、秘密鍵(暗号鍵)を使って「平文(plaintext)」と称される理解できるデータを「暗号文(cipher text)」と称される意味不明な形に変換する一連の変換を実行する。この暗号における変換は次のものを含む:(1)ラウンド鍵(暗号鍵から導出される値)を状態(state)(バイトの二次元配列)に排他的OR(XOR)演算を使って加算する;(2)非線形のバイト置換テーブル(Sボックス)を使って状態を処理する;(3)状態の最後の3行を異なるオフセットにより巡回的にシフトする;(4)状態のすべての列を取り、そのデータを(互いに独立に)混合して新しい列にする。
【0005】
復号(暗号化の逆)は、暗号鍵を使って「暗号文」ブロックを同じサイズの「平文」ブロックに変換する一連の変換を実行する。逆暗号化における変換は、暗号における前記の変換の逆である。
【0006】
AES規格において、ラインダール(Rijndael)アルゴリズムは、128ビットのデータ・ブロックを長さ128、192および256ビットの暗号鍵を使って処理するよう規定されている。異なる鍵長は典型的にはAES-128、AES-192およびAES-256と称される。
【0007】
AESアルゴリズムは、平文を暗号文に、あるいは暗号文を平文に10回、12回または14回の相続くラウンドで変換する。ラウンド数は鍵長に依存する。
【発明の概要】
【発明が解決しようとする課題】
【0008】
パラレル・モードでの先進暗号化標準(AES)の暗号化および復号を最適化する。
【課題を解決するための手段】
【0009】
本発明の課題は請求項記載の手段によって達成される。
【0010】
特許請求される事項の実施形態の特徴は、以下の詳細な記述が進むにつれ、また図面を参照することで明白になるであろう。図面において、同様の参照符号は同様の部分を描いている。
【図面の簡単な説明】
【0011】
【図1】AES暗号化および復号を汎用プロセッサで実行するための命令を含むシステムのブロック図である。
【図2】図1に示したプロセッサのある実施形態のブロック図である。
【図3】本発明の原理に従って異なるデータ・ブロックに対する独立した処理を並列に実行することによりAES暗号化/復号処理のスループットを改善する方法のある実施形態を示す流れ図である。
【図4】サイクル当たり一つのAESラウンド命令をディスパッチする(dispatch)例を示す図である。
【発明を実施するための形態】
【0012】
以下の詳細な記述は特許請求される事項の例示的な実施形態を参照しつつ進められるが、当業者には数多くの代替、修正および変形が明白であろう。したがって、特許請求される事項は広義に見られ、付属の請求項において述べられていることによってのみ定義されることが意図されている。
【0013】
先進暗号化標準(AES)アルゴリズムは、計算集約的なアルゴリズムであり、典型的にはソフトウェアにおいて、あるいは特殊目的のプロセッサにおいて実行される。AESアルゴリズムは、メモリに記憶されているロード/記憶/インクリメント中央処理装置(CPU)命令のシーケンスを実行することによって、ソフトウェアで実行される。AESアルゴリズムは、平文または暗号文の各バイトを変換するために多くのCPUサイクルを消費するので、この変換は遅い。よって、暗号化は典型的にはコンピュータに記憶されている情報の部分集合、たとえば「トップ・シークレット」と分類されているような情報を暗号化するためにのみ使用される。しかしながら、コンピュータに記憶されている情報のさらに多くの部分を暗号化する必要がある。たとえば、モバイル・コンピュータに記憶されている全情報が暗号化されれば、モバイル・コンピュータが盗まれてもその情報は保護されるであろう。
【0014】
AESは128ビットのブロックに128、192または256ビットの鍵サイズで作用するブロック暗号である。AESアルゴリズムは、10回、12回または14回の相続くラウンドで、128ビットの平文ブロックを128ビットの暗号文のブロックに変換し(暗号化)、あるいは128ビットの暗号文のブロックを128ビットの平文のブロックに変換する(復号)。ラウンド数は鍵サイズ(128、192または256ビット)に依存する。各ラウンドについて処理シーケンスが逐次反復される(10、12または14回)。暗号化のための処理シーケンスは次のことを含む:(1)ラウンド鍵(暗号鍵から導出される値)を状態(state)(バイトからなる128ビットの二次元配列)に排他的OR(XOR)演算を使って加算する;(2)非線形のバイト置換テーブル(Sボックス)を使って状態を処理する;(3)状態の最後の3行を異なるオフセットにより巡回的にシフトする;(4)状態のすべての列を取り、そのデータを(互いに独立に)混合して新しい列にする。
【0015】
ブロック暗号は、複数の動作モードのうちの一つを使用しうる。動作モードは、電子コードブック(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)といった他の動作モードは、秘匿性とメッセージ完全性の両方を保証する。
【0016】
ECBモードでは、暗号化されるべき平文はnビットのブロックに分割され、各ブロックが別個に暗号化される。すなわち、ブロックは他のブロックとは独立して暗号化される。CBCモードでは、平文は一時にnビットずつ処理され、平文ブロックの暗号化を前のブロックの暗号化に依存して行うために連鎖機構が使用される。たとえば、暗号化処理のためのCBC動作モードは下記の表1に示されるように記述されうる。
【0017】
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平文ブロック(入力)である。
表1
【0018】
CBC動作モードでは、CjはCj-1が計算される前には計算できない。よって、CBC動作モードはシリアル・モードである。
【0019】
パラレル動作モードは、あるブロックの暗号化/復号が他のブロックの暗号化/復号の結果とは独立である動作モードである。たとえば、ECBおよびカウンタ動作モードはパラレル動作モードである。下記で、ECBモードを使ったAES暗号化処理についての擬似コードの例を表2に示し、カウンタ動作モードを使ったAES暗号化処理についての擬似コードの例を表3に示す。
【0020】
for j from 1 to 暗号化すべきブロック数(NB)
TargetBuffer[j]=AES_ENCRYPT_PROCEDURE(DataBlock[j],cipher_key)
End loop
ここで、
DataBlock //暗号化すべきデータを保持する128ビットのエントリーをNB個もつバッファ
TargetBuffer //暗号化された結果を記憶する128ビットのエントリーをNB個もつバッファ(DataBlockと同じでもよい)
表2
【0021】
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と同じでもよい)
表3
【0022】
表2および表3における暗号化処理(AES_ENCRYPT_PROCEDURE)は、汎用プロセッサにおいてAES暗号化および復号を実行するための命令セット拡張において実行されうる。単一のAES暗号化処理はシリアルな動作のシーケンスを含み、それはAES命令のシリアルなシーケンスを介して実行されうる。複数の128ビット・データ・ブロックの暗号化を実行するための命令のシーケンスの例を下記で図4に示す。
【0023】
for (i=1; i<NB; i++)
temp=Load(DataBlock[i])
temp=xor(temp,RK[0]); //ラウンド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ビットの変数である。
表4
【0024】
表4に示されたAES命令(AESENC、AESENCLAST)は、128ビット変数(temp)に記憶されたデータ(状態とも称される)を、AES規格(FIPS刊行物197)によって定義されるようにシリアルに処理する。該データを処理するための動作のシリアルなシーケンスの例を表5に示す。
【0025】
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
表5
【0026】
暗号化すべきN_Blocksのそれぞれについて、データ・ブロックはレジスタに記憶される。たとえば128ビットをもつXmmレジスタ(Xmm1)が128ビットのブロックを記憶するために使用されうる。10回の暗号化ラウンドは、そのデータ・ブロックに対して直列に実行される。10ラウンドのAES処理のうちラウンド1から9については、AESENC命令が呼び出され、ラウンド鍵および直前のラウンドの結果もしくは初期ブロック・データ(ラウンド1の場合)を使ってラウンド処理を実行する。AESENCLAST命令は、最後のラウンド(今の例ではラウンド10)を処理するために呼び出される。
【0027】
AESラウンド命令(AESENC、AESENCLAST)のレイテンシ(latency)がLプロセッサ・サイクルと表されるとする。ロード、記憶および他のオーバーヘッドのためのサイクルを無視すると、表5の例に示される10回のAESラウンドのためのN_BLOCKSの処理は、表5に示した順序で処理されるとすると、約N_BLOCKS*10*Lサイクルを消費する。明らかに、N_Blocksの暗号化/復号を実行する全体としてのレイテンシは、個々のAES命令(AESENC、AESENCLAST)のレイテンシに依存する。
【0028】
本発明のある実施形態では、本発明の原理に従って複数のデータ・ブロックを並列に暗号化する(復号する)ことによって、AESラウンド命令のレイテンシ(L)の効果が軽減され、AES暗号化/復号処理を実行するために必要とされる全体としてのレイテンシの低下につながる。パラレル動作モードでは、異なるデータ・ブロックの異なる独立した暗号化(復号)は、前の命令が完了するのを待つことなく毎サイクルにおいてAESラウンド命令をディスパッチすることによって、並列に実行されうる。
【0029】
図1は、汎用プロセッサにおいてAES暗号化および復号を実行するための命令を含むシステム100のブロック図である。システム100は、プロセッサ101、メモリ・コントローラ・ハブ(MCH: Memory Controller Hub)(またはグラフィクス・メモリ・コントローラ・ハブ(GMCH: Graphics Memory Controller Hub))102および入出力(I/O)コントローラ・ハブ(ICH: Input/Output Controller Hub)104を含む。MCH102は、プロセッサ101とメモリ108の間の通信を制御するメモリ・コントローラ106を含む。プロセッサ101およびMCH102は、システム・バス116を通じて通信する。
【0030】
プロセッサ101は、単一コアのインテル(登録商標)・ペンティアム(登録商標)IV・プロセッサ、単一コアのインテル・セレロン・プロセッサ、インテル(登録商標)・XScaleプロセッサまたはペンティアム(登録商標)D、インテル(登録商標)・ジーオン(登録商標)・プロセッサもしくはインテル(登録商標)・コア(登録商標)・デュオ・プロセッサといったマルチコア・プロセッサまたは他の任意の型のプロセッサといった複数のプロセッサのいかなるものであってもよい。
【0031】
メモリ108は動的ランダム・アクセス・メモリ(DRAM: Dynamic Random Access Memory)、静的ランダム・アクセス・メモリ(SRAM: Static Random Access Memory)、同期型動的ランダム・アクセス・メモリ(SDRAM: Synchronized Dynamic Random Access Memory)、倍速データレート2(DDR2: Double Data Rate 2)RAMまたはランバス動的ランダム・アクセス・メモリ(RDRAM: Rambus Dynamic Random Access Memory)または他のいかなる型のメモリであってもよい。
【0032】
ICH104は、高速のチップからチップへの相互接続114を使って直接メディア・インターフェース(DMI: Direct Media Interface)のようなMCH102に結合されうる。DMIは、二つの一方向レーンを介して毎秒2ギガビットの並行転送レートをサポートする。
【0033】
ICH104は、該ICH104に結合された少なくとも一つの記憶装置112との通信を制御するための記憶装置I/Oコントローラ110を含んでいてもよい。記憶装置はたとえば、ディスク・ドライブ、デジタル・ビデオ・ディスク(DVD)・ドライブ、コンパクト・ディスク(CD)・ドライブ、独立したディスクの冗長アレイ(RAID)、テープ・ドライブまたは他の記憶装置であってもよい。ICH104は、記憶プロトコル相互接続118を介して、シリアル付属小型コンピュータ・システム・インターフェース(SAS: Serial Attached Small Computer System Interface)またはシリアル先進技術付属物(SATA: Serial Advanced Technology Attachment)といったシリアル記憶プロトコルを使って、記憶装置112と通信してもよい。
【0034】
プロセッサ101は、AES暗号化および復号処理を実行するためのAES機能103を含む。AES機能103は、メモリ108に記憶されているおよび/または記憶装置112に記憶されているような情報を暗号化または復号するために使用されうる。
【0035】
図2は、図1に示したプロセッサ101のある実施形態のブロック図である。プロセッサ101は、レベル1(L1)命令キャッシュ202から受領されるプロセッサ命令をデコードするためのフェッチおよびデコード・ユニット206を含む。プロセッサ命令を実行するために使用されるべきデータはレジスタ・ファイル208に記憶されうる。ある実施形態では、レジスタ・ファイル208は複数の128ビット・レジスタを含み、これらの128ビット・レジスタがAESラウンド命令による使用のためのデータを記憶するためにAESラウンド命令によって使用される。
【0036】
ある実施形態では、レジスタ・ファイル208は、ストリーミング(単一命令複数データ(SIMD))拡張(SSE: Streaming (Single Instruction Multiple Data) Extension)(SSE)命令セットをもつインテル(登録商標)・ペンティアム(登録商標)・MMXプロセッサに設けられている128ビットのMMXレジスタと同様の128ビット・レジスタの群である。SIMDプロセッサでは、データは、一時に一つの128ビット・ブロックずつロードして、複数の128ビット・ブロックにおいて処理される。
【0037】
フェッチおよびデコード・ユニット206は、L1命令キャッシュ202からマクロ命令をフェッチして、該マクロ命令をデコードし、該マクロ命令をマイクロ演算(μop: micro operation)と呼ばれる単純な演算に分解する。マイクロ演算はマイクロコード読み出し専用メモリ(ROM)214に記憶されうる。パイプライン化されている実行ユニット210は、それらのマイクロ演算をスケジューリングし、実行する。図示した実施形態では、実行ユニット210中のAES機能103はAESラウンド命令のセットのためのマイクロ演算を含む。AES命令は完全にパイプライン化され(fully pipelined)、それによりプロセッサ(CPU)は、処理するためのデータの準備ができていれば、毎サイクルにおいて命令をディスパッチしうる。待避ユニット(retirement unit)212は、実行された命令の結果をレジスタまたはメモリに書き込む。AESラウンド命令によって使用されるラウンド鍵216は、L1データ・キャッシュ204に記憶され、AESラウンド命令のいずれかを実行するためのマイクロ演算による使用のために、実行ユニット210にロードされてもよい。ラウンド鍵216をL1データ・キャッシュ204に記憶することは、サイド・チャネル攻撃、たとえばシステム100に記憶されている暗号化された情報へのアクセスを得るためにラウンド鍵を得ようとする試みからラウンド鍵216を保護する。
【0038】
AESラウンド命令がフェッチおよびデコード・ユニット206によってデコードされたのち、実行ユニット210によるAESラウンド命令の実行は、マイクロコードROM214に記憶されていてもよいAESラウンド命令に関連付けられたマイクロ演算の実行に関わる。
【0039】
ある実施形態では、暗号化ラウンド、復号ラウンド、暗号化最終ラウンドおよび復号最終ラウンドを実行するための別個のAESラウンド命令を含むAES命令セットが設けられる。ある実施形態では、各AESラウンド命令は一意的な動作コード(operation code)(オペコード(opcode))をもつ。固定幅ラウンド鍵(たとえば128ビット)についてのある実施形態についてのAES命令セットにおけるAESラウンド命令を、下記で表6に示す。
【0040】
AESENC xmmsrcdst xmm
入力:データ(=宛先)、ラウンド鍵
出力:ラウンド鍵を使ったAESラウンドを通じた変換後のデータ
AESENCLAST xmmsrcdst xmm
入力:データ(=宛先)、ラウンド鍵
出力:ラウンド鍵を使ったAES最終ラウンドを通じた変換後のデータ
AESDEC xmmsrcdst xmm
入力:データ(=宛先)、ラウンド鍵
出力:ラウンド鍵を使ったAESラウンドを通じた変換後のデータ
AESDECLAST xmmsrcdst xmm
入力:データ(=宛先)、ラウンド鍵
出力:ラウンド鍵を使ったAES最終ラウンドを通じた変換後のデータ
表6
【0041】
このAES命令セットは四つのAESラウンド命令(暗号化、復号、最終ラウンド暗号化、最終ラウンド復号)を含む。このAES命令セットにおけるAESラウンド命令は、最終ラウンドを除いたすべてのラウンドのために使用されることになる暗号化および復号のラウンド演算を実行する単一ラウンド演算を含む。たとえば、表6のAESENC単一ラウンド命令では、入力データは128ビット・レジスタ(xmmsrcdst)に記憶され、ラウンド鍵は別の128ビット・レジスタ(Xmm)に記憶される。この命令は、128ビットのxmmsrcdstレジスタに記憶されている入力データ(ソース)に対してAESラウンド演算を実行し、128ビットのxmmsrcdstレジスタに記憶されている入力データを、ラウンド演算の実行の結果をもって上書きする。こうして、xmmsrcdstはまず入力データを記憶し、のちにAESラウンド演算の結果を記憶する。
【0042】
鍵のサイズは128ビット、192ビットまたは256ビットであってよい。実行されるべきラウンド数(n)は、鍵のサイズに依存して1、10、12または14でありうる。各ラウンド鍵は固定サイズ(128ビット)である。ラウンド数の値10、12、14では、AESマイクロ演算は、128ビット、192ビットまたは256ビットの鍵サイズについて、標準的なAES暗号化および復号を実行しうる。
【0043】
多くのブロックに同じ鍵が使われるとき、各ラウンドについてのラウンド鍵(鍵スケジュール)が事前計算されてメモリに記憶されていてもよい(たとえば、レベル1のデータ・キャッシュ204内にラウンド鍵216)。ラウンド鍵216は、その鍵についての鍵スケジュールを記憶するための10の要素をもつ配列(RK)を含んでいてもよい。AES-128暗号化のための入力鍵はRK[0]に記憶され、9個のラウンド鍵RK[0]‐RK[1]が事前計算される。
【0044】
AES命令セットは、最後の復号ラウンドのためのAES復号命令および最後の暗号化ラウンドのためのAES暗号化命令をも含む。たとえば、表1のAESENCLAST単一ラウンド命令では、入力データは128ビット・レジスタ(xmmsrcdst)に記憶され、ラウンド鍵は別の128ビット・レジスタ(Xmm)に記憶される。この命令は、xmmsrcdstレジスタに記憶されている入力データ(ソース)に対してAESラウンド演算を実行し、xmmsrcdstレジスタに記憶されている入力データを、ラウンド演算の実行の結果をもって上書きする。こうして、xmmsrcdstはまず入力データを記憶し、のちにAESラウンド演算の結果を記憶する。Xmmレジスタはラウンド演算のためのラウンド鍵を記憶する。
【0045】
ある実施形態では、レジスタ・ファイル304はAES命令によって使用されうる複数の128ビット・レジスタをもつ。これらの128ビット・レジスタは、ソース・オペランド(単数または複数)、ラウンド鍵およびAES命令の結果を記憶しうる。最初のラウンドについては、AES命令は、暗号化されるべき128ビットの平文または復号されるべき128ビットの暗号文でありうるソース・オペランドを受領する。
【0046】
図3は、本発明の原理に従って異なるデータ・ブロックに対する独立した処理を並列に実行することによりAES暗号化/復号処理のスループットを改善する方法のある実施形態を示す流れ図である。
【0047】
AES処理のスループットの改善は、あるデータ・ブロックの暗号化/復号のフローを、処理すべきデータを提供する別のデータ・ブロックの暗号化/復号のフローと並行して走ることを許容し、毎サイクルにAESラウンド命令がディスパッチされることを許容することによってなされる。データ・ブロックが並列に処理されうるのは、(1)複数データ・ブロックにわたって同じ暗号鍵が使われる、すなわち鍵スケジュールが一度生成され、その同じ鍵スケジュールを使って複数データ・ブロックが処理され、かつ(2)AESラウンドが、単一の完全にパイプライン化されたAESラウンド命令を使って実行される場合である。毎サイクルに一度AESラウンド命令をディスパッチすることは、たとえ各AESラウンド命令のレイテンシが1サイクルより大きくても、AES暗号化/復号処理のスループットを上げる。
【0048】
AES-128暗号化処理について、すなわち128ビットのデータ・ブロックおよび128ビットの鍵を使った10回のAESラウンドでのAES暗号化処理について、実施例を述べる。下記の表7は、並列して異なるデータ・ブロックに対する独立した処理を実行することによりAES暗号化のスループットを最大化するために使用されうるソフトウェア命令の例を示している。
【0049】
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
表7
【0050】
表7を参照すると、各Xmmレジスタを使う処理は他のXmmレジスタを使う処理と独立しているので、AESラウンド命令「AESENC」は毎サイクルにディスパッチされる。先に論じたように、これは、並列動作モードの性質のためである。たとえば、ECBモードでは、暗号化すべき平文はnビット・ブロックに分割され、各ブロックが別個に暗号化される。すなわち、ブロックは他のブロックとは独立して暗号化される。使用されるXmmレジスタの数(この例では8)が命令レイテンシ(L)、すなわち命令を完了させるためのサイクル数より大きいまたはこれに等しく選ばれる場合、AESラウンド命令は、複数のAESラウンドにまたがってでさえ、毎サイクルにディスパッチされることができる。
【0051】
ブロック300では、暗号化/復号されるべき複数のデータ・ブロックが複数のレジスタ(たとえば複数の128ビットXmmレジスタ)に記憶される。128ビット・レジスタをもつある実施形態では、AESのデータ・ブロック・サイズは128ビットなので、異なるデータ・ブロックがk個の128ビット・レジスタのそれぞれに記憶される。パフォーマンスを最大にするため、前記異なるデータ・ブロックを記憶するために使用されるレジスタ数はAESラウンド命令のレイテンシに依存する。これは、毎サイクルに一つのAESラウンド命令がディスパッチされ、複数の異なるデータ・ブロックが並列して処理されうることを許容する。処理はブロック302に続く。
【0052】
ブロック302では、AES暗号化/復号処理のラウンド0で実行される処理が、他のラウンドで実行される処理とは異なっている。よって、ラウンド0での処理は、k個の128ビット・レジスタに記憶されているk個の異なるデータ・ブロックのそれぞれに対して逐次的に実行される。処理はブロック304に続く。
【0053】
ブロック304では、すべての他のラウンド(たとえばAES-128についてはラウンド1ないし10)について同じAESラウンド命令がディスパッチされる。現在ラウンドについてk個のレジスタに記憶されているk個の異なるデータ・ブロックのそれぞれについて、当該ラウンドに関連付けられたラウンド鍵[RK]を使って、サイクル当たり一つのAES命令がディスパッチされる。k個のレジスタに記憶されているk個の異なるデータ・ブロックのそれぞれについてAESラウンド命令がディスパッチされたのち、処理はブロック306に続く。
【0054】
ブロック306では、そのAES処理のためにさらなるラウンドがあれば、処理はブロック304に続いて次のラウンドを処理する。さらなるラウンドがなければ、処理はブロック308に続く。
【0055】
ブロック308では、そのAES処理のために処理されるべき他のデータ・ブロックがあれば、処理はブロック300に続き、次のデータ・ブロック(単数または複数)を前記k個のレジスタにロードする。他のデータ・ブロックがなければ、処理はブロック310に続き、AES処理の結果を返す。
【0056】
図4は、サイクル当たり一つのAESラウンド命令をディスパッチする例を示している。図4に示される例では、レジスタ数(k)およびAESラウンド命令レイテンシ(L)はいずれも6である。図4は、表7に示され、図3のブロック304との関連で論じたforループの一つについてのAES命令のディスパッチを示している。k=L=6のときにラウンド2についてのforループについてディスパッチされる命令は、明示的には下記の表8のように書ける。
【0057】
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])
表8
【0058】
この例では、レジスタはXmmレジスタ・ファイルにおけるXmmレジスタであり、Xmmレジスタの6つ(Xmm1〜Xmm6とラベルされる)は6つの異なるデータ・ブロックを記憶するために使用される。しかしながら、本発明はXmmレジスタに限定されるものではなく、AESラウンドのために128ビット・データ・ブロックを記憶することができ、AESラウンド命令によってアクセス可能ないかなるレジスタを使ってもよい。Xmm1を使う処理は他のXmmレジスタ(Xmm2、…、Xmm6)のそれぞれを使う処理とは独立しているので、AESENC命令は毎サイクル、ディスパッチできる。理想的なスケジュール条件のもとでは、このforループは完了するのにk+L−1(6+6−1=11)サイクルかかる。
【0059】
図3を参照すると、Lおよびkの両方が6であるシステムにおいては、毎サイクル、AESENC命令がディスパッチされる。各ラウンド(ラウンド0以外)について、最初の6つの命令は同じラウンド鍵RKを使って6つの異なるXmmレジスタ(Xmm1〜Xmm6)上で動作する。たとえば、サイクル1ではXmm1およびRK[1]を使ってAESENC命令がディスパッチされ、サイクル2ではXmm2およびRK[2]を使ってAESENC命令がディスパッチされる。サイクル1においてディスパッチされたAESENC命令は6サイクルのレイテンシをもち、よってサイクル6の終わりに完了される。
【0060】
サイクル7においてディスパッチされる7番目のAESENC命令は、Xmm1レジスタに記憶されている7番目のデータ・ブロックをラウンド鍵RK[2]とともに使うことができる。これは、その時点までには、サイクル1においてXmm1レジスタに記憶された第一のデータ・ブロックおよびラウンド鍵RK[1]を使ってディスパッチされたAESENC命令はすでに完了している(6サイクルのレイテンシに基づく)からである。よって、6つのAESENC命令が、それぞれ6つのXmmレジスタの一つに記憶されている異なるデータ・ブロックを使って、並列に動作してもよい。こうして、前記レジスタの複数に記憶されているデータ・ブロックを使う第二のAESラウンドは、全部で11サイクル後に完了する。これに対し、これら二つのAESラウンドについてのデータ・ブロックが表5に示した例との関連で先に論じたように直列に処理されたとしたら、12サイクル後である。AES-128処理についての全10回のAESラウンドが完了するまで、各サイクルにおいてAESENC命令(またはAESENCLAST命令)がディスパッチされる。
【0061】
kをデータ・ブロックを記憶するために利用可能なレジスタの数に依存して選択されるものとして、論じたように、k個のデータ・ブロックが並列に暗号化されうる。レジスタ数(k)≧AES命令レイテンシ(L)であれば、AES命令は毎サイクルにディスパッチされうる。これは「複数のAESラウンドにまたがって」であってもよい。すなわち、ある特定のAESラウンドについてのAESラウンド命令のすべてが、次のAESラウンドについてのAESラウンド命令をディスパッチするのに先立って完了される必要はない。
【0062】
たとえば、ラウンド鍵RK[1]を使ってAESラウンド1を処理するために第一のレジスタが使用される場合、該第一のレジスタは、kサイクルが経過してしまうまではラウンド鍵RK[2]を使ってAESラウンド2を処理するために使用することはできない。よって、k≧Lであれば、AESラウンド1のためにAES命令がディスパッチされるk個のサイクルがあって、k+1番目のサイクルでは、ラウンド鍵RK[2]を用いて処理されるべきAESラウンド2のためのデータ・ブロックを記憶するために第一のレジスタが利用可能である。
【0063】
並列してk個の異なるデータ・ブロックを処理することは、kデータ・ブロック当たり、排他的OR(XOR)演算を実行するAESラウンド0についての約kサイクルに加えて、他のNR個のAESラウンドを処理するためにさらなるNR*k+L−1サイクルを必要とする。したがって、スループットは、kデータ・ブロック当たり(NR*k+L−1)サイクルによって見積もれる。これはデータ・ブロック当たりNR+(L−1)/kサイクルである。
【0064】
パフォーマンスは利用可能なレジスタ数によって、およびAESラウンド命令のレイテンシによって制約される。ラウンド鍵(RK)はメモリから読み込まれることもできるし(レジスタ‐メモリ・モード)、別のレジスタにロードされることもできる(レジスタ‐レジスタ・モード)。レジスタ‐メモリ・モードは、ラウンド鍵が最初に読み込まれたのち第一レベルのキャッシュに記憶されるならば、より高いパフォーマンスを提供しうる。
【0065】
前記の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サイクル/バイト)。このように、異なるデータ・ブロックに対する独立した処理を並列に実行することは、表5との関連で論じたデータを処理するためのシリアルな処理シーケンスを使うときよりほとんど9倍のパフォーマンス増を達成する。
【0066】
処理を並列に実行することにより、AESラウンド命令のレイテンシ(L)は、レジスタ数(k)がL以上である限り、「隠蔽される」。これは、あるブロックに対して他のブロックとは独立に動作する動作モード、たとえばECB、CCM、GCMおよびカウンタを含む動作モードを使うAES処理のための暗号化/復号のためのAESラウンド命令の効率的な使用を許容する。
【0067】
本発明の実施形態に関わる方法がコンピュータによって使用可能な媒体を含むコンピュータ・プログラム・プロダクトにおいて具現されてもよいことは当業者には明白であろう。たとえば、そのようなコンピュータによって使用可能な媒体は、コンピュータ読み取り可能なプログラム・コードが記憶されているコンパクト・ディスク読み出し専用メモリ(CD-ROM)ディスクもしくは通常のROMデバイスのような読み出し専用メモリ・デバイスまたはコンピュータ・ディスケットからなっていてもよい。
【0068】
本発明の実施形態についてその実施形態を参照しつつ具体的に図示し、説明してきたが、当業者は、付属の請求項が網羅する本発明の実施形態の範囲から外れることなく、形および詳細におけるさまざまな変更がなしうることを理解するであろう。
【符号の説明】
【0069】
101 プロセッサ
102 メモリ・コントローラ・ハブ(MCH)
103 AES暗号化/復号処理
104 入出力コントローラ・ハブ
106 メモリ・コントローラ
108 メモリ
110 記憶装置入出力コントローラ
112 記憶装置
200 バフ・インターフェース・ユニット
202 レベル1の命令キャッシュ
204 レベル1のデータ・キャッシュ
206 フェッチおよびデコード・ユニット
208 レジスタ・ファイル
210 実行ユニット
212 待避ユニット
214 マイクロコードROM
216 ラウンド鍵
300 k個のレジスタにk個の異なるデータ・ブロックをロード
302 k個のデータ・ブロックのそれぞれについてAESラウンド0処理を実行
304 k個のレジスタに記憶されている各データ・ブロックについて1ラウンドのためのラウンド処理を実行するラウンド命令をディスパッチ
306 さらなるラウンド[RK]?
308 さらなるデータ・ブロック?
310 結果を返す

【特許請求の範囲】
【請求項1】
あるブロックに対して他のブロックとは独立して作用する動作モードを使って先進暗号化標準(AES)処理を複数の固定サイズのブロックに対して実行することを含む方法であって:
前記複数の固定サイズのブロックのうちk個の相続くブロックのセットをk個のレジスタに記憶する段階であって、kは、ブロックに対してあるAESラウンドについてのAESラウンド演算のシーケンスを実行するAESラウンド命令のレイテンシ(L)以上である、段階と;
前記k個のブロックのそれぞれについてサイクル毎に一つのAESラウンド命令をディスパッチすることによって、前記k個の相続くブロックのセットに対して前記AESラウンド演算のシーケンスを並列に実行する段階とを有する、
方法。
【請求項2】
前記k個のブロックのそれぞれについての前記AESラウンド命令の結果を、前記k個のレジスタの一つに記憶する段階をさらに有する、
請求項1記載の方法。
【請求項3】
各ブロックが128ビットをもつ、請求項1記載の方法。
【請求項4】
前記レジスタがXmmレジスタである、請求項1記載の方法。
【請求項5】
前記AESラウンド命令がパイプラインされる、請求項1記載の方法。
【請求項6】
前記動作モードが、電子コードブック(ECB)、カウンタ、暗号ブロック連鎖メッセージ認証コード(CCM)またはガロア・カウンタ・モード(GCM)である、請求項1記載の方法。
【請求項7】
複数の固定サイズのブロックのうちk個の相続くブロックのセットをk個のレジスタに記憶するためのレジスタ・ファイルであって、kは、ブロックに対して当該ラウンドについてのAESラウンド演算のシーケンスを実行するAESラウンド命令のレイテンシ(L)以上である、レジスタ・ファイルと;
あるブロックに対して他のブロックとは独立して作用する動作モードを使って先進暗号化標準(AES)処理を複数の固定サイズのブロックに対して実行する実行ユニットであって、前記k個のブロックのそれぞれについてサイクル毎に一つのAESラウンド命令をディスパッチすることによって、前記k個の相続くブロックのセットに対して前記AESラウンド演算のシーケンスを並列に実行する実行ユニットとを有する、
装置。
【請求項8】
前記実行ユニットが、前記k個のブロックのそれぞれについての前記AESラウンド命令の結果を前記k個のレジスタの一つに記憶する、請求項7記載の装置。
【請求項9】
各ブロックが128ビットをもつ、請求項7記載の装置。
【請求項10】
前記レジスタがXmmレジスタである、請求項7記載の装置。
【請求項11】
前記AESラウンド命令がパイプラインされる、請求項7記載の装置。
【請求項12】
前記動作モードが、電子コードブック(ECB)、カウンタ、暗号ブロック連鎖メッセージ認証コード(CCM)またはガロア・カウンタ・モード(GCM)である、請求項7記載の装置。
【請求項13】
付随する情報をもつ機械アクセス可能媒体を含む物品であって、前記情報は、アクセスされたときに、機械に:
あるブロックに対して他のブロックとは独立して作用する動作モードを使って先進暗号化標準(AES)処理を複数の固定サイズのブロックに対して実行することを含む方法であって:
前記複数の固定サイズのブロックのうちk個の相続くブロックのセットをk個のレジスタに記憶する段階であって、kは、ブロックに対してあるAESラウンドについてのAESラウンド演算のシーケンスを実行するAESラウンド命令のレイテンシ(L)以上である、段階と;
前記k個のブロックのそれぞれについてサイクル毎に一つのAESラウンド命令をディスパッチすることによって、前記k個の相続くブロックのセットに対して前記AESラウンド演算のシーケンスを並列に実行する段階とを有する、
方法を実行させる、
物品。
【請求項14】
前記k個のブロックのそれぞれについての前記AESラウンド命令の結果を、前記k個のレジスタの一つに記憶する段階をさらに有する、
請求項13記載の物品。
【請求項15】
各ブロックが128ビットをもつ、請求項13記載の物品。
【請求項16】
前記レジスタがXmmレジスタである、請求項13記載の物品。
【請求項17】
前記AESラウンド命令がパイプラインされる、請求項13記載の物品。
【請求項18】
前記動作モードが、電子コードブック(ECB)、カウンタ、暗号ブロック連鎖メッセージ認証コード(CCM)またはガロア・カウンタ・モード(GCM)である、請求項13記載の物品。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate