Help us understand the problem. What is going on with this article?

C#でAES暗号化アルゴリズムを外部ライブラリに一切頼らず完全実装してみた

はじめに

今回、暗号化技術「AES」(Advanced Encryption Standard)について、深く知り学びたいとふと思ってしまったので、C#でアルゴリズムを完全再現してみました。
今回は学習目的ですが、本来であれば標準ライブラリに頼るべきです。

また、実装にあたって高度な数学は避けられません。
私の範囲を超えたものは、基本的に外部記事に解説を委ねます。

今回、以下の記事を参考にさせて頂きました。

@tobira-code「AESを理解する」

Wikipedia様:
出典: フリー百科事典『ウィキペディア(Wikipedia)』
Advanced Encryption Standard
Rijndael S-box
Rijndael MixColumns
AES key schedule

Wikiwand様:
Block cipher mode of operation

AppliedGo様:
(YouTube)AES Rijndael Cipher explained as a Flash animation

The Advanced Encryption Standard (Rijndael)

AESとは何か

※あくまで主観です
今の時代、Googleで探せばいくらでも情報が手に入りますが、
これに関しては、既知の情報をコピー&ペーストしたような情報記事ばかりで、正確でわかりやすい情報を見つけるのに苦労しました。

AESとは、アメリカ国立標準技術研究所で標準暗号とされている共通鍵暗号アルゴリズムです。
Rijndaelが採用されています。(ラインデールと読むそうです。かっこいい。)

rijnov.gif

画像出典: The Advanced Encryption Standard (Rijndael)

暗号化プロセス

鍵長128bitの場合、ラウンド数は合計10です。
暗号化プロセスは、以下の通りです。
cipherprocess.png

環境

・Visual Studio 2019 Professional
・Windows 10 1903 Build 18362.476
・C#
・.NET Framework 4.7.2

開発期間: 1.5日

実装

SubBytes

S-BOXと呼ばれるテーブルを使用して、バイトを変換します。
S-BOXのテーブルは以下の通りです。
なぜこうなっているのかは私の範囲外ですのでwikipedia様にお任せします。
71fe04fd9ff5679c611feac0c973ac46.png

ソースコード

実際にコードでSBOXの値を求めるにあたって、case-switch文で関数定義しました。
完全に脳死してます。
より良い方法はありますが、とりあえず動作していますし速度は求めていないので今回はこれで行きます。

コメント欄よりご指摘を頂き、ソースコードを修正しました。

SBOX.cs
private static readonly byte[] sbox_table = 
{
    0x63,  0x7c,  0x77,  0x7b,  0xf2,  0x6b,  0x6f,  0xc5,  0x30,  0x01,  0x67,  0x2b,  0xfe,  0xd7,  0xab,  0x76,
    0xca,  0x82,  0xc9,  0x7d,  0xfa,  0x59,  0x47,  0xf0,  0xad,  0xd4,  0xa2,  0xaf,  0x9c,  0xa4,  0x72,  0xc0,
    0xb7,  0xfd,  0x93,  0x26,  0x36,  0x3f,  0xf7,  0xcc,  0x34,  0xa5,  0xe5,  0xf1,  0x71,  0xd8,  0x31,  0x15,
    0x04,  0xc7,  0x23,  0xc3,  0x18,  0x96,  0x05,  0x9a,  0x07,  0x12,  0x80,  0xe2,  0xeb,  0x27,  0xb2,  0x75,
    0x09,  0x83,  0x2c,  0x1a,  0x1b,  0x6e,  0x5a,  0xa0,  0x52,  0x3b,  0xd6,  0xb3,  0x29,  0xe3,  0x2f,  0x84,
    0x53,  0xd1,  0x00,  0xed,  0x20,  0xfc,  0xb1,  0x5b,  0x6a,  0xcb,  0xbe,  0x39,  0x4a,  0x4c,  0x58,  0xcf,
    0xd0,  0xef,  0xaa,  0xfb,  0x43,  0x4d,  0x33,  0x85,  0x45,  0xf9,  0x02,  0x7f,  0x50,  0x3c,  0x9f,  0xa8,
    0x51,  0xa3,  0x40,  0x8f,  0x92,  0x9d,  0x38,  0xf5,  0xbc,  0xb6,  0xda,  0x21,  0x10,  0xff,  0xf3,  0xd2,
    0xcd,  0x0c,  0x13,  0xec,  0x5f,  0x97,  0x44,  0x17,  0xc4,  0xa7,  0x7e,  0x3d,  0x64,  0x5d,  0x19,  0x73,
    0x60,  0x81,  0x4f,  0xdc,  0x22,  0x2a,  0x90,  0x88,  0x46,  0xee,  0xb8,  0x14,  0xde,  0x5e,  0x0b,  0xdb,
    0xe0,  0x32,  0x3a,  0x0a,  0x49,  0x06,  0x24,  0x5c,  0xc2,  0xd3,  0xac,  0x62,  0x91,  0x95,  0xe4,  0x79,
    0xe7,  0xc8,  0x37,  0x6d,  0x8d,  0xd5,  0x4e,  0xa9,  0x6c,  0x56,  0xf4,  0xea,  0x65,  0x7a,  0xae,  0x08,
    0xba,  0x78,  0x25,  0x2e,  0x1c,  0xa6,  0xb4,  0xc6,  0xe8,  0xdd,  0x74,  0x1f,  0x4b,  0xbd,  0x8b,  0x8a,
    0x70,  0x3e,  0xb5,  0x66,  0x48,  0x03,  0xf6,  0x0e,  0x61,  0x35,  0x57,  0xb9,  0x86,  0xc1,  0x1d,  0x9e,
    0xe1,  0xf8,  0x98,  0x11,  0x69,  0xd9,  0x8e,  0x94,  0x9b,  0x1e,  0x87,  0xe9,  0xce,  0x55,  0x28,  0xdf,
    0x8c,  0xa1,  0x89,  0x0d,  0xbf,  0xe6,  0x42,  0x68,  0x41,  0x99,  0x2d,  0x0f,  0xb0,  0x54,  0xbb,  0x16
};

public static byte Convert(byte _byte_)
{
    return sbox_table[_byte_];
}

ShiftRows

4バイト単位の行を一定規則で左シフトします。
例として、以下の画像の通りです。
・2段目を1個左シフト
・3段目を2個左シフト
・4段目を3個左シフト
83e2927a26514dd0981573200c727097.png

ソースコード

1行目は操作の必要がありませんが、わかり易さのために残しています。

Cryption.cs
private static byte[] ShiftRows(byte[] bytes)
{
    byte[] result = new byte[bytes.Length];

    result[ 0] = bytes[ 0]; result[ 1] = bytes[ 1]; result[ 2] = bytes[ 2]; result[ 3] = bytes[ 3];

    result[ 4] = bytes[ 5]; result[ 5] = bytes[ 6]; result[ 6] = bytes[ 7]; result[ 7] = bytes[ 4];

    result[ 8] = bytes[10]; result[ 9] = bytes[11]; result[10] = bytes[ 8]; result[11] = bytes[ 9];

    result[12] = bytes[15]; result[13] = bytes[12]; result[14] = bytes[13]; result[15] = bytes[14];

    return result;
}

MixColumns

Rijindaelのガロア体という、定数を利用して計算を行います。
11256d7b581d0dfd1fdf3501451d2401.png
9c7c22d2ef50400fae38660217d86625.png

具体的には、ガロア体の4つの数字の座標ベクトルにMDS(最大距離分離)行列を乗算します。
これも、高度な数学で私の範囲を超えていますので、外部記事にお任せします。
巡回行列 - Wikipedia
MDS Matrix
MDS行列 の意味・用法を知る

ソースコード

ガロア体は以下のように定義しました。

byte[] matrix = 
{ 
    0x02, 0x03, 0x01, 0x01,
    0x01, 0x02, 0x03, 0x01,
    0x01, 0x01, 0x02, 0x03,
    0x03, 0x01, 0x01, 0x02
};

当ソースコードではわかり易さの為、ガロア体を定数として定義して使用していませんが
どちらにせよコンスタントな値であるため、直接書いても良いです。

Cryption.cs
private static byte[] MixColumns(byte[] bytes)
{
    byte[] result = new byte[bytes.Length];
    byte[,] bytes2d = new byte[4, 4];

    bytes2d = Bytes16To2DBytes4(bytes);

    byte[] matrix = 
    { 
        0x02, 0x03, 0x01, 0x01,
        0x01, 0x02, 0x03, 0x01,
        0x01, 0x01, 0x02, 0x03,
        0x03, 0x01, 0x01, 0x02
    };

    byte[,] matrix2d = new byte[4, 4];
    matrix2d = Bytes16To2DBytes4(matrix);

    byte[,] resultBytes2d = new byte[4, 4];
    for (int c = 0; c <= 3; c++)
    {
        resultBytes2d[0, c] = (byte)((GMul(0x02, bytes2d[0, c])) ^ (GMul(0x03, bytes2d[1, c])) ^ (GMul(0x01, bytes2d[2, c])) ^ (GMul(0x01, bytes2d[3, c])));
        resultBytes2d[1, c] = (byte)((GMul(0x01, bytes2d[0, c])) ^ (GMul(0x02, bytes2d[1, c])) ^ (GMul(0x03, bytes2d[2, c])) ^ (GMul(0x01, bytes2d[3, c])));
        resultBytes2d[2, c] = (byte)((GMul(0x01, bytes2d[0, c])) ^ (GMul(0x01, bytes2d[1, c])) ^ (GMul(0x02, bytes2d[2, c])) ^ (GMul(0x03, bytes2d[3, c])));
        resultBytes2d[3, c] = (byte)((GMul(0x03, bytes2d[0, c])) ^ (GMul(0x01, bytes2d[1, c])) ^ (GMul(0x01, bytes2d[2, c])) ^ (GMul(0x02, bytes2d[3, c])));
    }

    result = Bytes2D4ToBytes16(resultBytes2d);

    return result;
}

MDS(最大距離分離)行列を乗算
式が変換先の型の範囲外の値を生成した場合に、オーバーフローを検出させないために、unchecked()が必要です。

public static byte GMul(byte a, byte b)
{
    byte p = 0;

    for (int counter = 0; counter < 8; counter++)
        if ((b & 1) != 0) p ^= a;

    bool bs = (a & 0x80) != 0;
    a <<= 1;
    if (bs) a ^= unchecked((byte)0x11B);
    b >>= 1;

    return p;
}

KeySchedule : RotWord

ラウンド毎に行われる、新しい鍵の生成です。
まずはじめに、鍵の行(縦)4行目をとり、RotWordという入れ替え処理を行います。
d39a821c59df93eef1dc7245721d9895.png
次にRijindael S-BOX定数を用いて、該当行を変換します。

SBOX.Convert([byte]);

また、RCON(RoundConstant)と呼ばれる、ラウンドコンスタント定数を使用しています。

private static readonly byte[] RCON =
{
    0x00000000, 
    0x00000001, 
    0x00000002, 
    0x00000004, 
    0x00000008, 
    0x00000010, 
    0x00000020, 
    0x00000040, 
    0x00000080,
    0x0000001B,
    0x00000036
};

ソースコード

Cryption.cs
private static void KeySchedule(byte[] bytes, int currentRound)
{
    byte[,] bytes2d = Bytes16To2DBytes4(bytes);
    byte[,] round_key = new byte[4, 4];
    byte[] r = new byte[16];
    byte[] r_ = new byte[16];

    //Rot Word
    //一旦値を格納
    r[ 3]  = CURRENT_CHIPHER_KEY[ 3]; //09
    r[ 7]  = CURRENT_CHIPHER_KEY[ 7]; //cf
    r[11]  = CURRENT_CHIPHER_KEY[11]; //4f
    r[15]  = CURRENT_CHIPHER_KEY[15]; //3c
    //↓ 一番下を一番上に持ってくる
    r_[ 3] = CURRENT_CHIPHER_KEY[ 7]; //cf
    r_[ 7] = CURRENT_CHIPHER_KEY[11]; //4f
    r_[11] = CURRENT_CHIPHER_KEY[15]; //3c
    r_[15] = CURRENT_CHIPHER_KEY[ 3]; //09
    //↓ s-box変換
    r_[ 3] = SBOX.Convert(r_[ 3]); //8a
    r_[ 7] = SBOX.Convert(r_[ 7]); //84
    r_[11] = SBOX.Convert(r_[11]); //eb
    r_[15] = SBOX.Convert(r_[15]); //01

    r[ 0]  = CURRENT_CHIPHER_KEY[ 0];
    r[ 4]  = CURRENT_CHIPHER_KEY[ 4];
    r[ 8]  = CURRENT_CHIPHER_KEY[ 8];
    r[12]  = CURRENT_CHIPHER_KEY[12];

    round_key[0, 0] = (byte)(CURRENT_CHIPHER_KEY[ 0] ^ r_[ 3] ^ RCON[currentRound]);
    round_key[1, 0] = (byte)(CURRENT_CHIPHER_KEY[ 4] ^ r_[ 7] ^ RCON[0]);
    round_key[2, 0] = (byte)(CURRENT_CHIPHER_KEY[ 8] ^ r_[11] ^ RCON[0]);
    round_key[3, 0] = (byte)(CURRENT_CHIPHER_KEY[12] ^ r_[15] ^ RCON[0]);

    for (int x = 0; x <= 3; x++) //0,1,2 (3)
    {
        //0は除きたい(横インデックス1から埋め込んでいく)ので x は 1 2 3 のみに絞る
        if (x == 0) continue;
        round_key[0, x] = (byte)(CURRENT_CHIPHER_KEY[ 0 + (1 * x)] ^ round_key[0, x - 1]);
        round_key[1, x] = (byte)(CURRENT_CHIPHER_KEY[ 4 + (1 * x)] ^ round_key[1, x - 1]);
        round_key[2, x] = (byte)(CURRENT_CHIPHER_KEY[ 8 + (1 * x)] ^ round_key[2, x - 1]);
        round_key[3, x] = (byte)(CURRENT_CHIPHER_KEY[12 + (1 * x)] ^ round_key[3, x - 1]);
    }

    CURRENT_CHIPHER_KEY = Bytes2D4ToBytes16(round_key);
}

初期ラウンドにやること

初期ラウンドのAddRoundKeyでは、暗号化するByteと鍵とのXorをとります。

byte[] result = new byte[bytes.Length];
for (int x = 0; x < bytes.Length; x++)
{
    result[x] = (byte)(bytes[x] ^ CIPHER_KEY[x]);
}
暗号化するByte:
32 88 31 e0
43 5a 31 37
f6 30 98 07
a8 8d a2 34

鍵:
2b 28 ab 09
7e ae f7 cf
15 d2 15 4f
16 a6 88 3C

結果:
19 A0 9A E9
3D F4 C6 F8
E3 E2 8D 48
BE 2B 2A 08

結果

ラウンド1

round1.png

ラウンド2

round2.png

ラウンド3

round3.png

ラウンド4

round4.png

ラウンド5

round5.png

ラウンド6

round6.png

ラウンド7

round7.png

ラウンド8

round8.png

ラウンド9

round9.png

ラウンド10

round10.png

無事、暗号化に成功しました。

最後に

今回は、AES暗号化アルゴリズムを外部ライブラリに頼らずフル実装してみました。
解説に関しては、私が高校数学を未だ習っていない為外部に頼りきりですが、プロジェクトを通して、本当に沢山のことを学べました。
また、当プロジェクトでは暗号化のみ行っていますが、また機会があれば復号化にもチャレンジしてみたいです。

今回のプロジェクトは、Githubリポジトリよりフルソースコードを閲覧できます。
GitHub

当記事に間違いや訂正するべき点がございましたら、お手数ですがコメント欄よりご指摘を頂けますと幸いです。

kkent030315
もうすぐ高校1年生です。
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした