はじめに
現状、共通鍵暗号でもっとも有名なAES暗号の暗号化＆復号アルゴリズムの理解を深めるため作成した記事。
AESを使用したプログラムではなく、AESの仕組み自体に興味がある人向けなので悪しからず。
テスト実装はRustで、できる限りドメイン駆動設計で行うよう意識している。
実装のまとめはこれ
アルゴリズム概要
AES（Advanced Encryption Standard）は共通鍵暗号の一種。
128,192,256bitの秘密鍵によって、入力ブロック256bitを暗号化する。
秘密鍵のビットの違いはそのままセキュリティ強度に影響しており、鍵長の大きいほうが暗号強度は高い。
なお、鍵が大きいからと言って暗号化できるブロックの大きさは変わらないので、1ブロックは共通で256bit(=16byte)。
入力がそれ以上の場合は、ブロック毎に同じ鍵で暗号化を繰り返す。
（入力が足りない場合はパディング）
同じ鍵で処理を行うので、このまま使うと同じブロックは同じ暗号化を行ってしまい、ブロックの値が同じかどうかは簡単に分かってしまう。
そこで、暗号処理に加えて、AESにはモードと言われるものが存在している。
- ecb
- 通常モード特に入力もいじらずAESでそのまま暗号化する一番の基礎。理由は上記の通りで、絶対に使用してはいけない
- cbc
- 入力のブロックを連結させるイメージで暗号化するモード。これでも良いけど脆弱性がある
- cfb
- 入力のブロックでフィードバックをかけるイメージで暗号化するモード
- ofb
- 出力のブロックでフィードバックをかけるイメージで暗号化するモード
- ctr
- カウンターでインクリメントしてそれを入力と合わせて暗号化するモード
今回の記事ではECBモードの解説を行っている。
全てのモードの元なのでこちらが理解できれば、後は理解できる
（重ねて言うが、絶対に実運用でECBを使用してはいけない）
2024年現在、Openssl等暗号通信に使用されているAESは、AES-256-GCMといわれるものになる。
256は鍵の大きさ256bit。
GCMはCTR型の拡張と思えば良い。
つまり、実際に使用されている暗号通信はAES-256さえ理解できれば良く、鍵の大きさの違いは（後述するが）そこまでないため、AESの基本処理さえ理解できれば良い。
なので、今回ではAES-128-ECBをテスト実装する。
暗号化部分は基本的に、下記の構造になっている。
復号はこちら
見比べればわかると思うが、CipherとInvCipherの処理は処理の順番をひっくり返して関数をInvに変えているだけになる。
内部の関数も同様のため、全て通常関数とInv関数ワンセットで解説を行う。
設計のイメージとしては機械学習の誤差伝搬。
独断と偏見だが、アルゴリズムで使用する関数の理解難易度を示すと
SubBytes MixColumns
-------越えられない壁-------
KeyExpansion ShiftRows AddRoundKey
こんなイメージ
上二つは有限体や多項式剰余等の理解が必要なので、他に比べて段違いに難易度が高い（と思う）
実質的には解説が必要なのはこの二つといってもよい。
アルゴリズム解説
予備知識
プログラムの解説の前に、いくつか準備と解説をする要素がある
拡大体
GF(2^8)といわれてわかる場合はそれで。
使用する多項式は
f(x) = x^8 + x^4 + x^3 + x + 1
原論文にも割とわかりやすく説明されているので、詳細はそちらを見てほしい。
数学つかわず、プログラマのイメージですごく簡単にいえば、
-
x mod 256(=2^8)で計算される
誤解を恐れずイメージでいえば256という素数として考える
なので素数modとみなしてアルゴリズムを使用できる（フェルマーの小定理とか）
演算子は限られているので注意！ -
足し算はxor、係数は1or0
つまりマイナスは存在しないし、足し算で桁上がりは起きない
(例) $$ 5 + 3 = [x^2 + 1] + [x + 1] = x^2 + x $$ -
オーバーフロー時に0x1bを足す
(例) $$ 256 + 6 = 0b1,0000,0000 + 0b0000,0110 = 1b + 6 $$
元のf(x)が0になると考えると、
$$ x^8 + x^4 + x^3 + x + 1 = 0 $$
$$ x^8 = -(x^4 + x^3 + x + 1)
= x^4 + x^3 + x + 1 = 00011011 = 0x1b $$となる
例) $$ 0b10000000 \ll 1 = 0b00011011 $$
...なんか説明としてはよくない気がしてきたけど、許してほしい。
この部分だけで記事が作成できるほど時間がかかる。
AES上では、S-boxとMixColumnのみで使用されるので、これらの認識で理解できると思う。
他の暗号系アルゴリズムを読みたい場合は、必須な要素となるので調べる必要がある。
こんな感じで実装した。
#[derive(Default,Debug,Clone, Copy)]
pub struct aesGF{
pub value :u8
}
impl Add for aesGF{
type Output = Self;
fn add(self,rhs : Self)-> Self{
Self { value: (self.value ^ rhs.value) }
}
}
impl Mul for aesGF{
type Output = Self;
fn mul(self, rhs: Self) -> Self::Output {
let mut ret : u8 = 0;
let mut n : u8 = rhs.value;
let mut a : u8 = self.value;
while n > 0{
if n&1 == 1 {
ret = ret ^ a;
}
a = (a << 1) ^ (if a&0x80 == 0x80 {0x1b}else{0}) & 0xff;
//println!("{:>08b} {} {:>08b}",ret,n,a);
n >>= 1;
}
Self{value :ret}
}
}
impl aesGF{
pub fn inv(self)->Self{
let mut ret = self;
for i in 0..253 {
ret = ret * self;
}
ret
}
}
面倒くさかったのでベタ書きしているが、実装するならジェネリックにして他の拡大体も対応したほうが良い。
実際に使うときは、拡大体のライブラリを使いましょう。
S-box
固定で用意された16*16テーブル。
大体ハードコーディングされていて、invとワンセット（invは生成できるからいらないけど）
使用用途としてはsbox[0][9] のように取り出すだけ、変更もないので簡単。
いったいこれ何？
どこからでてきたの？
となること間違いない
..ならない場合は知らない、少なくとも自分はなったので調べといた。
簡単にいえば、Sboxとは線形性を壊すためのテーブル。
もっと簡単に言えば、計算式使わない変換テーブルのこと。
S-box
Rijindeal_S-box
今回使用しているSboxは、できる限り変換に相関や差分が無いよう作られているらしい、違うS-boxに置き換えてもうまくいく。
こちらのS-boxを作成するにあたって、拡大体や逆元を使用しているため、使用する分には難しくないが、理解するのが難しいものになっている。
基本の形はこれ、
s = b \oplus (b \lll 1)\oplus (b \lll 2)\oplus(b \lll 3)\oplus(b \lll 4)\oplus63_{16}
実装時にはこれをハードコーディングしても良いのだが、なんとなく残しておく
fn make_sbox() -> ([u8;256],[u8;256]){
let mut ret_sbox : [u8;256] = [0;256];
let mut ret_inv_sbox : [u8;256] = [0;256];
let shift = |x: u8,i : u8| x<<i | x >>(8-i);
for i in 0..ret_sbox.len(){
let t = aesGF{value :i as u8}.inv().value;
ret_sbox[i] = t ^ shift(t,1) ^ shift(t,2) ^ shift(t,3) ^ shift(t,4) ^ 0x63u8;
ret_inv_sbox[ret_sbox[i] as usize] = i as u8;
//println!("{:x}",ret[i]);
}
(ret_sbox,ret_inv_sbox)
}
アフィン変換での実装でも良いのだが、正直面倒くさかった。
Rcon
こちらはGF(2^8)な係数を事前に準備しておく。
Rcon[0]=0x01から始めて左シフトしていくだけ。
（例 Rcon[0] = 0x01, Rcon[1] = 0x02, Rcon[4] = 0x10）
鍵拡張の際に、Rconの値を使用する。
S-box同様線形性の破壊のためらしいけど、なぜこの値なのかはよくわからない。
詳しい人は教えてほしい。
const RCON : [u32;11] = [
0x00000000, /* invalid */
0x01000000, /* x^0 */
0x02000000, /* x^1 */
0x04000000, /* x^2 */
0x08000000, /* x^3 */
0x10000000, /* x^4 */
0x20000000, /* x^5 */
0x40000000, /* x^6 */
0x80000000, /* x^7 */
0x1B000000, /* x^4 + x^3 + x^1 + x^0 */
0x36000000, /* x^5 + x^4 + x^2 + x^1 */
];
各種パラメーター
word 32bitの値、具体的に言えば最小単位の4倍
Nr ラウンドの回数 鍵の大きさできまっている
Nk 鍵のサイズ
#[derive(Default,Debug,Clone, Copy)]
pub enum BitType {
#[default]
Aes128,
Aes192,
Aes256
}
impl BitType {
pub fn nk_nr(self)->(usize,usize){
match self{
BitType::Aes128 => (4,10),
BitType::Aes192 => (6,12),
BitType::Aes256 => (8,14)
}
}
}
input 4word（足りない場合、パディングはPKCS#7）
（絶対行からのほうがわかりやすいと思う。一回間違った）
//論文中での並び方順
00 04 08 12
01 05 09 13
02 06 10 14
03 07 11 15
output inputと同様
以上。
これらの知識を踏まえたうえで、実装と解説を行う。
MixColumns&InvMixColums
行っている内容は、入力列に固定の係数をかける。invはその逆。
難しいと言っている部分は処理内容というよりは、その実装時に使用されている拡大体と係数。
拡大体の説明はしているので省略。
係数に関しては、MixColumnsのほうで使用しているのが、MDS行列といわれるもので、invはその逆元。
この行列を使用すると、入力をうまい具合に拡散できるらしい。。
係数の値が小さいのはラウンドの計算処理に時間をかけず、拡散度合が大きいからとか。
正直ここに関しては、あったから使っている感しかない
拡散度合の証明ってどうやってやるんだろう？とかは思ったが、おいておく。
pub fn mix_column(blocks: Vec<u8>,inverse : bool)->Vec<u8>{
let blocks = blocks.into_iter().map(|x|aesGF{value:x}).collect::<Vec<aesGF>>();
let mut ret :[aesGF;16] = [aesGF::default();16];
for i in 0..4{
let i = i *4;
if !inverse {
ret[i] = aesGF{value : 2}*blocks[i] + aesGF{value :3}*blocks[i+1] + blocks[i+2] + blocks[i+3];
ret[i +1] = blocks[i] + aesGF{value : 2}*blocks[i+1] + aesGF{value :3}*blocks[i+2] + blocks[i+3];
ret[i +2] = blocks[i] + blocks[i+1] + aesGF{value : 2}*blocks[i+2] + aesGF{value :3}*blocks[i+3];
ret[i +3] = aesGF{value :3}*blocks[i] + blocks[i+1] + blocks[i+2] + aesGF{value : 2}*blocks[i+3];
}else{
ret[i] = aesGF{value : 0x0e}* blocks[i] + aesGF{value :0x0b}* blocks[i+1] + aesGF{value :0x0d}* blocks[i+2] + aesGF{value :0x09}* blocks[i+3];
ret[i+1] = aesGF{value :0x09}* blocks[i] + aesGF{value : 0x0e}* blocks[i+1] +aesGF{value :0x0b}* blocks[i+2] + aesGF{value :0x0d}* blocks[i+3];
ret[i+2] = aesGF{value :0x0d}* blocks[i] + aesGF{value :0x09}* blocks[i+1] + aesGF{value : 0x0e}* blocks[i+2] + aesGF{value :0x0b}* blocks[i+3];
ret[i+3] =aesGF{value :0x0b}* blocks[i] +aesGF{value :0x0d}* blocks[i+1] + aesGF{value :0x09}* blocks[i+2] + aesGF{value : 0x0e}* blocks[i+3];
}
}
let ret = ret.map(|x|{x.value}).to_vec();
ret
}
SubBytes&InvSubBytes
やっている内容は単純に入力バイトをS-boxとinvS-boxテーブルに従って置換するだけ
S-boxの理解を入れなければ一番簡単。
例）0x01ならばsbox[0][1] ,0x1aならばsbox[1][a] invはその逆
pub fn sub_bytes(blocks : Vec<u8>,inverse : bool) ->Vec<u8>{
let (sbox,inv_sbox) = make_sbox();
let mut ret = blocks;
for mut item in ret.iter_mut(){
if inverse{
*item = inv_sbox[*item as usize];
}else{
*item = sbox[*item as usize];
}
}
ret
}
AddRoundkey
増やした鍵でxorをとる。
pub fn add_round_key(blocks: Vec<u8>,key : Vec<u32>,inverse : bool)->Vec<u8>{
let mut ret = blocks;
for i in 0..4{
let key = key[i].to_be_bytes();
for j in 0..4{
ret[4*i +j] = blocks[4*i +j] ^ key[j];
}
}
ret
}
ShiftRows&InvShiftRows
データの回転。
論文上に回転方向が書かれているので、それを参考にしたほうがよい。
（最初間違えて行毎に進んでいると勘違いして作り直した。。）
pub fn shift_row(blocks : Vec<u8>,inverse : bool) -> Vec<u8>{
/*
forward
00 04 08 12 => 00 04 08 12
01 05 09 13 => 05 09 13 01
02 06 10 14 => 10 14 02 06
03 07 11 15 => 15 03 07 11
inverse
00 04 08 12 => 00 04 08 12
01 05 09 13 => 13 01 05 09
02 06 10 14 => 10 14 02 06
03 07 11 15 => 07 11 15 03
*/
let mut ret = blocks.clone();
for i in 0..4 {
for j in 0..4{
let slide = if inverse{
(i+j)%4
}else{ (i+4-j)%4};
ret[4*slide +j] = blocks[4*i+j];
}
}
ret
}
KeyExpansion
暗号、復号処理には入っていないが、重要なので記載する。
簡単に言えば、鍵をもとに鍵を増やすアルゴリズム。
入力は鍵毎で変わり、それをラウンド数分に増やすもの。
（例 aes_128の場合、key 4word => keyEx 44 word (4 word * 11 round) )
気づいた人もいると思うが、実は鍵長で処理が変わるのは実質ここだけであり、アルゴリズム自体に差はほとんどない。
拡張は最初の暗号時のみでいいのだが、AESというオブジェクトが鍵を持っているのは違和感があったので、暗号＆復号のたびに鍵を生成するかたちにした。
fn key_expansion(&self,key : Key)->Vec<u32>{
let (nk,nr) = key.bit_type.nk_nr();
let shift_word = |x : u32|x<<8 | x >> 24;
let sub_word = |x:u32|{
let connect = |x : [u8;4]|{
((x[0] as u32) << 24) +
((x[1] as u32) << 16) +
((x[2] as u32) << 8) +
((x[3] as u32) << 0)
};
let mut vec_u8 = x.to_be_bytes();
let s = vec_u8.map(|x|self.sbox[x as usize]);
connect(s)
};
let round = (nr as usize +1)*4;
let key_length = nk as usize;
let mut round_key : Vec<u32> = Vec::new();
round_key.extend(key.value.clone());
for i in key_length..round{
let mut word : u32 = round_key[i-1];
if i%key_length == 0 {
word = shift_word(word);
word = sub_word(word);
word = word ^ AES::RCON[i/key_length];
}else if 6<nk && i%key_length == 4{
word = sub_word(word);
}
let pre_word = round_key[i-key_length].clone();
word = word ^ pre_word;
round_key.push(word);
}
round_key
}
実装まとめ
上記の実装をまとめる
ディレクトリ構造（想定 後で変更するかも）
- src
- object_value
- aes_gf.rs
- key.rs
- type.rs
- cipher
- main.rs
- lib.rs
- object_value
暗号&復号の処理がペアになっているのに、別々の関数を作るのは恰好悪い気がしてたので、処理をまとめてニューラルネットワーク的な形にしてみようと考えていたが、正直面倒くさくなったので手を抜いてしまった。
ごめんなさい！
#[derive(Debug)]
pub struct AES{
sbox : [u8;256],
inv_sbox:[u8;256]
}
impl AES{
const RCON : [u32;11] = [
0x00000000, /* invalid */
0x01000000, /* x^0 */
0x02000000, /* x^1 */
0x04000000, /* x^2 */
0x08000000, /* x^3 */
0x10000000, /* x^4 */
0x20000000, /* x^5 */
0x40000000, /* x^6 */
0x80000000, /* x^7 */
0x1B000000, /* x^4 + x^3 + x^1 + x^0 */
0x36000000, /* x^5 + x^4 + x^2 + x^1 */
];
pub fn new()->Self{
let (sbox,inv) = make_sbox();
Self { sbox: sbox, inv_sbox: inv}
}
fn key_expansion(&self,key : Key)->Vec<u32>{
let (nk,nr) = key.bit_type.nk_nr();
let shift_word = |x : u32|x<<8 | x >> 24;
let sub_word = |x:u32|{
let connect = |x : [u8;4]|{
((x[0] as u32) << 24) +
((x[1] as u32) << 16) +
((x[2] as u32) << 8) +
((x[3] as u32) << 0)
};
let mut vec_u8 = x.to_be_bytes();
let s = vec_u8.map(|x|self.sbox[x as usize]);
connect(s)
};
let round = (nr as usize +1)*4;
let key_length = nk as usize;
let mut round_key : Vec<u32> = Vec::new();
round_key.extend(key.value.clone());
for i in key_length..round{
let mut word : u32 = round_key[i-1];
if i%key_length == 0 {
word = shift_word(word);
word = sub_word(word);
word = word ^ AES::RCON[i/key_length];
}else if 6<nk && i%key_length == 4{
word = sub_word(word);
}
let pre_word = round_key[i-key_length].clone();
word = word ^ pre_word;
round_key.push(word);
}
round_key
}
pub fn encrypt(&self,input : Vec<u8>,key : Key)->Vec<u8>{
let mut block : Vec<u8> = input;
let inverse = false;
let (nk,nr) = key.bit_type.nk_nr();
let key = self.key_expansion(key.clone());
block = add_round_key(block,key[0..4].to_vec(), inverse);
for i in 1..nr{
block = sub_bytes(block, inverse);
block = shift_row(block, inverse);
block = mix_column(block, inverse);
block = add_round_key(block, key[4*i..4*(i+1)].to_vec(), inverse);
}
block = sub_bytes(block, inverse);
block = shift_row(block, inverse);
block = add_round_key(block, key[4*nr..4*(nr+1)].to_vec(), inverse);
block
}
pub fn decrypt(&self,input : Vec<u8>,key : Key)->Vec<u8>{
let mut block : Vec<u8> = input;
let inverse = true;
let (nk,nr) = key.bit_type.nk_nr();
let key = self.key_expansion(key.clone());
block = add_round_key(block, key[4*nr..4*(nr+1)].to_vec(), inverse);
for i in (1..nr).rev(){
block = shift_row(block, inverse);
block = sub_bytes(block, inverse);
block = add_round_key(block, key[4*i..4*(i+1)].to_vec(), inverse);
block = mix_column(block, inverse);
}
block = shift_row(block, inverse);
block = sub_bytes(block, inverse);
block = add_round_key(block, key[0..4].to_vec(), inverse);
block
}
}
テスト
テスト内容は論文内にあるテストベクターを実行してみて確認
原論文に遷移時のデータが詳しく書いてあり非常に助かった。
他にもnistのこれとかでもテストしてみた。
とりあえずECBでは問題なく動いている模様。
mod test{
use super::*;
#[test]
fn test_vector1(){
//PLAINTEXT = 6bc1bee22e409f96e93d7e117393172a
//KEY = 2b7e1516 28aed2a6 abf71588 09cf4f3c
//CIPHERTEXT = 3ad77bb40d7a3660a89ecaf32466ef97
let input = vec![0x6b,0xc1,0xbe,0xe2,0x2e,0x40,0x9f,0x96,0xe9,0x3d,0x7e,0x11,0x73,0x93,0x17,0x2a];
let key = vec![0x2b7e1516,0x28aed2a6,0xabf71588,0x09cf4f3c];
let input = cipher(input, key.clone(), false);
assert_eq!(input,hex::decode("3ad77bb40d7a3660a89ecaf32466ef97").unwrap());
let input = cipher(input, key.clone(), true);
assert_eq!(input,hex::decode("6bc1bee22e409f96e93d7e117393172a").unwrap());
}
//...省略
#[test]
fn test_aes_256(){
//plain=00112233445566778899aabbccddeeff
//key=000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f
//cipher=8ea2b7ca516745bfeafc49904b496089
let input = hex::decode("00112233445566778899aabbccddeeff").expect("test ae2d error");
let key_str = hex::decode("000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f").expect("key ae2d error");
let key = (0..key_str.len()).step_by(4).map(|x |{
let y : u32 = (key_str[x] as u32) << 24 | (key_str[x+1] as u32) << 16 | (key_str[x+2] as u32) << 8 | (key_str[x+3] as u32);
y
}).collect::<Vec<u32>>();
//let key = vec![0x00010203,0x04050607,0x08090a0b,0x0c0d0e0f,0x10111213,0x14151617,0x18191a1b,0x1c1d1e1f];
let bit_type = aes_type::BitType::Aes256;
let mode = aes_type::Mode::Ecb;
let aes : AES = AES::new();
let input = aes.encrypt(input,Key{value :key.clone(),bit_type:bit_type.clone(),mode :mode.clone()});
assert_eq!(input,hex::decode("8ea2b7ca516745bfeafc49904b496089").unwrap());
let input = aes.decrypt(input,Key{value :key,bit_type:bit_type,mode :mode});
assert_eq!(input,hex::decode("00112233445566778899aabbccddeeff").unwrap());
}
}
番外編
PKCS#7
AESはブロック暗号なので、16byteに満たない場合、入力を16byteに穴埋め（パディング）する。
パディングの仕様も様々あるらしいが、基本的にはこのPKCS#7が使われているみたい？
入力に対するパディングの実装をしておく、
pub fn padding_pkcs_7(input : Vec<u8>)->Vec<u8>{
let block_byte = (input.len()/16 + 1)*16;
let value = (block_byte - input.len()) as u8;
let mut ret = input.clone();
for i in 0..value{
ret.push(value);
}
ret
}
AES-GCM
もうここまでくるとAESのアルゴリズムからずれている気がする。。
AESを使用するにあたって現在推奨されている使用方法がこれ。
暗号モードGCMで調べればでてくる。
ここまで実装すれば、現在推奨されているAES-256-GCMを使用することができる。
ここはここで別の記事にする。
感想
久々に記事書いたので、正直ちょっと疲れた。実装をもう少し詰めたかったが、時間がないのでとりあえず良しとする。
当たり前だけど、暗号は元に戻せる必要があるから、値をめちゃくちゃにした上で行きと帰りを考える必要がある。
しかも、暗号強度を数学面と情報科学面で考えないといけないのだから、暗号系理論を考える人には頭が上がらない。
AES暗号に関しては、何やらセキュリティ的な脆弱性があるのではないか、とか言われているらしいが、2024年現在では特に明確な脆弱性は見つかってはいないはず。
（2000年より前に作られてるのに凄まじい）
ただ今後とも変わらないとは言えないので、共通鍵暗号も最新のものを使うよう意識したほうが良いと思う。
参考文献
実装の参考になりました！感謝！