この記事について
長い間、私は、AESやMD5などの暗号化暗号化とハッシュアルゴリズムは非常に複雑で、手元に完全なドキュメントがあっても書くのが難しいと信じていました。 さまざまなプログラミング言語でのこれらのアルゴリズムの複雑な実装は、この意見を強めるだけでした。 しかし最近、私は多くの自由時間を持ち、これらのアルゴリズムを理解してそれらを書くことにしました。 それらは非常に単純に配置されており、実装のために必要な時間はほとんどないことが判明しました。
この記事では、AES暗号化アルゴリズム（Rijndaelと呼ばれることもある）の仕組みを記述し、JavaScriptで記述します。 なぜjavascriptで？ この言語でプログラムを実行するには、この記事を読むブラウザーのみが必要です。 たとえば、Cでプログラムを実行するには、コンパイラが必要であり、記事のコードのコンパイルに時間を費やすことを望んでいる人はほとんどいません。 最後に、htmlページといくつかのjsファイルを含むアーカイブをダウンロードできるリンクがあります-これは、AESのJavaScript実装の例です。
AESの適用方法
このアルゴリズムは、そのような変換に必要な秘密鍵を使用して、128ビットブロックを別のブロックに変換します。 受信した128ビットブロックを解読するには、同じ秘密キーを使用した2回目の変換が使用されます。 次のようになります。
cipher = encrypt(block, key) // block key block = decrypt(cipher, key) // cipher key
ブロックサイズは常に128ビットです。 キーサイズのサイズも固定されています。 任意のパスワードを任意のパスワードで暗号化するには、これを行うことができます：
- パスワードハッシュを取得
- AES標準で説明されている規則に従ってハッシュをキーに変換します
- テキストを128ビットのブロックに分割します
- 暗号機能で各ブロックを暗号化する
これは次のように書くことができます：
hash = md5(password) // MD5 128 key = keyexpansion(hash) // blocks = split(text, 16) // 16 for (i = 0; i < blocks.length; i++) cipher[i] = encrypt(blocks[i], key)
暗号ブロックの配列を復号化するには、各ブロックに復号化を適用する必要があります。
hash = md5(password) key = keyexpansion(hash) for (i = 0; i < cipher.length; i++) blocks[i] = decrypt(cipher[i], key) text = merge(blocks) //
もちろん、テキストの長さは128ビットの倍数ではない場合があります。 このような場合は、テキストをゼロで埋めて目的の長さにし、暗号化されたデータに元のテキストの暗号化されたサイズの数バイトを追加できます。 例のaes.jsファイルのaes.encryptおよびaes.decrypt関数は、このアプローチを使用します。
GFフィールド（2 8 ）
AESは、いわゆるGF有限体（2 8 ）を積極的に使用します。 JavaScriptでAESを記述するために、AESがどのフィールドであるかを知る必要はありませんが、AESをよりよく理解したい場合は、このセクションをお読みください。
フィールドGF（2 8 ）は、特別な乗算と特別な加算が決定された数値0..255です。 このフィールドからいくつかの番号を取得し、8ビットの形式で表します：a = a 7 a 6 a 5 a 4 a 3 a 2 a 1 a 0 。 同様に、数字bを想像してください。 aとbの追加は、よく知られているビット演算xorです。
a + b = a xor b
追加には単純なプロパティがあります：
a + a = 0
-a = 0 - a = a
a - b = a + (-b) = a + b
乗算を決定することはより困難です。 これらの数のビットからの係数で多項式を書きます：
p = a 7 x 7 + a 6 x 6 + a 5 x 5 + a 4 x 4 + a 3 x 3 + a 2 x 2 + a 1 x + a 0
q = b 7 x 7 + b 6 x 6 + b 5 x 5 + b 4 x 4 + b 3 x 3 + b 2 x 2 + b 1 x + b 0
次に、これら2つの多項式を乗算し、mによる除算の剰余を求めます。
m = x 8 + x 4 + x 3 + x + 1
r = pq mod (m)
なぜこれが選択されるのですか？ この多項式には、剰余なしで割り切れる除数多項式が2つだけあります。ユニットと彼自身です。 素数との類推により、多項式mは「素数」です。 除算の剰余を見つけることも通常の数と同様に行うことができます：このためには、多項式を乗算、加算、減算することができ、GF（2 8 ）の規則に従って加算と減算が実行されます。 多項式の加算と減算は、係数の各ペア間でxorです。 以下に2つの例を示します。
x 3 + x 2 + 1 mod (x 3 + 1) = x 2 // x 3 +1
x 3 + x 2 + 1 mod (x 2 + 1) = (x 3 + x 2 + 1) - (x + 1)(x 2 + 1) = -x
多項式rを次の形式で表します
r = r 7 x 7 + r 6 x 6 + r 5 x 5 + r 4 x 4 + r 3 x 3 + r 2 x 2 + r 1 x + r 0
その8つの係数は、GFフィールドからの8ビット数（2 8 ）を表し、この数は積a•bと呼ばれます。 加算と異なり、単純なビット演算のペアでは乗算を見つけることができません。 ただし、体GF（2 8 ）内の任意の多項式による乗算は、多項式xによる乗算に減らすことができ、xによる乗算は、以下で説明するいくつかのビット演算で実行できます。
GF（2 8 ）は、16進数を使用して多項式を示します。 例えば
m = x 8 + x 4 + x 3 + x + 1 = 100011011 = 0x011b = {01}{1b}
体GF（2 8 ）で多項式x = {02}を乗算することは非常に簡単です。 製品を検討してください。
xp = x(a 7 x 7 + a 6 x 6 + a 5 x 5 + a 4 x 4 + a 3 x 3 + a 2 x 2 + a 1 x + a 0 ) =
a 7 x 8 + a 6 x 7 + a 5 x 6 + a 4 x 5 + a 3 x 4 + a 2 x 3 + a 1 x <2 + a 0 x
p = a 7 a 6 a 5 a 4 a 3 a 2 a 1 a 0
xp = a 7 a 6 a 5 a 4 a 3 a 2 a 1 a 0 0 //
ここで、mによる除算の残りを見つける必要があります。 ビットa 7 = 1の場合、mを1回減算します。 7 = 0の場合、何も減算する必要はありません。 だから：
r = xp mod (m) = xp - m a 7 = 1
r = xp mod (m) = xp a 7 = 0
xによる乗算は、次の関数で記述できます。
gf.xtime = function(b) { var highbit = b & 0x80 var shl = (b << 1) & 0xff return highbit == 0 ? shl : shl ^ 0x1b }
xを掛ける方法を知っていると、他の多項式を掛けることができます。 例として、a = {3c}、b = {a1}のa•bを見つけます。
b = {a1} = 10100001 = {80} + {20} + {01}
a•b = a•{80} + a•{20} + a•{01} = a•x 7 + a•x 5 + a =
a•{02}•{02}•{02}•{02}•{02}•{02}•{02} + a•{02}•{02}•{02}•{02}•{02} + a =
{29} + {c1} + {3c} = {d4}
フィールドGF（2 8 ）には1つの単純な操作が残っています。 ゼロ以外の任意のバイトbには、プロパティa•b = {01}を持つバイトa = b -1があります。 フィールドを操作するための3つの関数（xによる乗算、任意の2バイトの乗算、およびその反対の検出）をすべて、JavaScriptの小さなgfライブラリに入れました。
SBoxテーブル
このテーブルは256バイトの配列であり、あるバイトを別のバイトに置き換えるために使用されます。 この配列をコードにコピーするだけなので、結果を理解する必要はありません。 SBox [b]要素が何であるかを調べるには、3つのアクションが必要です。
- GFフィールド（2 8 ）のbへの戻りバイトを見つけます（ゼロのままにします）
- 8ビットの結果に64ビットの8×8マトリックスを乗算する
- {63}を追加
合計で、これらの3つのアクションはアフィン変換を提供します。
このビットマトリックスがどのように構築されるかを理解するのは簡単です。 ビットの乗算では、加算に「and」、「xor」を適用する必要があります。 例：
r 0 = b 0 + b 4 + b 5 + b 6 + b 7 + 1
私はこのようにsbox関数を書きました：
aes.sbox = function(b) { var m = 0xf8 var r = 0 var q = gf.inv(b) || 0 for (var i = 0; i < 8; i++) { r = (r << 1) | bits.xorbits(q & m) m = (m >> 1) | ((m & 1) << 7) } return r ^ 0x63 }
構築されたテーブルは次のようになります。
63 7c 77 7b f2 6b 6f c5 30 01 67 2b fe d7 ab 76
ca 82 c9 7d fa 59 47 f0 ad d4 a2 af 9c a4 72 c0
b7 fd 93 26 36 3f f7 cc 34 a5 e5 f1 71 d8 31 15
04 c7 23 c3 18 96 05 9a 07 12 80 e2 eb 27 b2 75
09 83 2c 1a 1b 6e 5a a0 52 3b d6 b3 29 e3 2f 84
53 d1 00 ed 20 fc b1 5b 6a cb be 39 4a 4c 58 cf
d0 ef aa fb 43 4d 33 85 45 f9 02 7f 50 3c 9f a8
51 a3 40 8f 92 9d 38 f5 bc b6 da 21 10 ff f3 d2
cd 0c 13 ec 5f 97 44 17 c4 a7 7e 3d 64 5d 19 73
60 81 4f dc 22 2a 90 88 46 ee b8 14 de 5e 0b db
e0 32 3a 0a 49 06 24 5c c2 d3 ac 62 91 95 e4 79
e7 c8 37 6d 8d d5 4e a9 6c 56 f4 ea 65 7a ae 08
ba 78 25 2e 1c a6 b4 c6 e8 dd 74 1f 4b bd 8b 8a
70 3e b5 66 48 03 f6 0e 61 35 57 b9 86 c1 1d 9e
e1 f8 98 11 69 d9 8e 94 9b 1e 87 e9 ce 55 28 df
8c a1 89 0d bf e6 42 68 41 99 2d 0f b0 54 bb 16
よく行われるように、コードに単純にコピーするか、必要に応じてsbox関数で計算できます。
InvSBoxテーブル
テキストを復号化するために、AESはSBoxの逆のテーブルを使用します。 InvSBoxテーブルには、InvSBox [SBox [i]] = iという1つのプロパティがあります。 InvSBoxは次のようになります。
52 09 6a d5 30 36 a5 38 bf 40 a3 9e 81 f3 d7 fb
7c e3 39 82 9b 2f ff 87 34 8e 43 44 c4 de e9 cb
54 7b 94 32 a6 c2 23 3d ee 4c 95 0b 42 fa c3 4e
08 2e a1 66 28 d9 24 b2 76 5b a2 49 6d 8b d1 25
72 f8 f6 64 86 68 98 16 d4 a4 5c cc 5d 65 b6 92
6c 70 48 50 fd ed b9 da 5e 15 46 57 a7 8d 9d 84
90 d8 ab 00 8c bc d3 0a f7 e4 58 05 b8 b3 45 06
d0 2c 1e 8f ca 3f 0f 02 c1 af bd 03 01 13 8a 6b
3a 91 11 41 4f 67 dc ea 97 f2 cf ce f0 b4 e6 73
96 ac 74 22 e7 ad 35 85 e2 f9 37 e8 1c 75 df 6e
47 f1 1a 71 1d 29 c5 89 6f b7 62 0e aa 18 be 1b
fc 56 3e 4b c6 d2 79 20 9a db c0 fe 78 cd 5a f4
1f dd a8 33 88 07 c7 31 b1 12 10 59 27 80 ec 5f
60 51 7f a9 19 b5 4a 0d 2d e5 7a 9f 93 c9 9c ef
a0 e0 3b 4d ae 2a f5 b0 c8 eb bb 3c 83 53 99 61
17 2b 04 7e ba 77 d6 26 e1 69 14 63 55 21 0c 7d
AESの種類
AESアルゴリズムは、128ビットのブロックを同じ長さの別のブロックに変換します。 変換には、キーから取得したキースケジュールwが使用されます。 AESの128ビットブロックは、4×N b行列として表されます。 標準ではN b = 4の1つの値のみが許可されているため、ブロック長は常に128ビットですが、アルゴリズムは任意のN bで機能します。 キーの長さは4N kバイトです。 ブロック暗号化アルゴリズムは、N r回のラウンドで構成されます-同じ変換グループを128ビットのデータブロックに適用します。 この規格では、これら3つのパラメーターの以下の組み合わせが許可されています。
| N k | N b | N r | |
| AES-128 | 4 | 4 | 10 |
| AES-192 | 6 | 4 | 12 |
| AES-256 | 8 | 4 | 14 |
KeyExpansion変換
AESは、テキストを暗号化するためにパスワードやパスワードハッシュを使用しませんが、キーから取得したいわゆる「キースケジュール」を使用します。 このスケジュールは、サイズ4×N bの N r + 1行列として表すことができます。 暗号化アルゴリズムはN r + 1ステップを取り、各ステップで、とりわけ、「スケジュール」から1つの4×N bマトリックスを取り、要素ごとにデータブロックに追加します。
データブロック暗号化
暗号化アルゴリズムは、128ビットのデータブロック入力と、KeyExpansionの後に取得されるキースケジュールwを受け取ります。 16バイトの入力を、AES状態と呼ばれる4×N bマトリックスsの形式で書き込み、このマトリックスに4回の変換をN r回適用します。 最後に、彼は行列を配列の形式で書き込み、それを出力に送ります-これは暗号化されたブロックです。 4つの変換はそれぞれ非常に簡単です。
- AddRoundKeyは、キースケジュールから4×N bマトリックスを1つ受け取り、それを要素ごとに状態マトリックスに追加します。 AddRoundKeyを2回適用すると、何も変更されないため、AddRoundKeyへの逆変換自体が行われます。
- SubBytesは、状態行列の各要素をSBoxテーブルの対応する要素で置き換えます：s ij = SBox [s ij ]。 SubBytes変換は可逆です。 その逆は、InvSBoxテーブルを使用して検出されます。
- ShiftRowsは、マトリックスsのi番目の行をiの位置だけ左にシフトし、iをゼロからカウントします。 InvShiftRows逆変換は、行を右にシフトします。
- MixColumnsは、左側のマトリックスsの各列に特別な4×4マトリックスを乗算します。
暗号化には[abcd] = [{02} {03} {01} {01}]を使用します。 変換がMixColumns [{02} {03} {01} {01}]に逆であることを確認できます。これはMixColumns [{0e} {0b} {0d} {09}]です。
回路図暗号化は次のように表すことができます。
AddRoundKey(0) for (var i = 1; i <= Nr - 1; i++) { SubBytes() ShiftRows() MixColumns([0x02, 003, 0x01, 0x01]) AddRoundKey(i) } SubBytes() ShiftRows() AddRoundKey(Nr)
解読
ご覧のとおり、データブロックを暗号化するために、AESは一貫して多くの可逆変換を適用します。 復号化するには、逆変換を逆の順序で適用する必要があります。
少しの最適化
sbox関数には、合計256個の入力値と256個の出力値があります。 1つの引数のsboxを何度も計算しないようにするには、結果をキャッシュする必要があります。 JavaScriptでは、以前に作成したコードを変更することなく、これを簡単に実行できます。 これを行うには、以下を追加するだけです。
Function.prototype.cached = function() { var old = this var cache = {} return function(x) { if (cache[x] !== undefined) return cache[x] cache[x] = old(x) return cache[x] } } aes.sbox = aes.sbox.cached()
このコードは、sboxを、sboxの結果をキャッシュする関数に置き換えます。 invsboxやrconなど、どの機能でも同じことができます。 同じ手法は、GFフィールド（2 8 ）の2バイトを乗算するgf.mul関数にも適用できますが、この場合、キャッシュサイズは256×256要素になり、非常に多くなります。
参照資料
英語のAESドキュメントはFIPS 197と呼ばれます。