[技術資料室] [ネットワーク編] [Linuxメモ] [Javaのsecurity]
[SSHメモ] [OpenSSL] [スマートカード]
[技術資料室] [ネットワーク編]
[Linuxメモ]
[Javaのsecurity]
[SSHメモ]
[OpenSSL] [スマートカード]
暗号全般については[PKI]などで。
今回は、JavaでDES、AESの実装をしてみたのでそのあたり。
AES基本
今回はAESの部分のみです。アメリカのNISTで募集されたアルゴリズムのなかのひとつ、Rijndael というような名前のアルゴリズムが元になっています。
AESは、鍵、入力、出力があります。
鍵、鍵から生成されたRoundKeyを保持し、内部状態の遷移はありません。
まずは鍵をroundKeyにするのですが、先にメインの方から見てみようかな。
128bit(16バイト)を入力し、128bitを出力します。
基本的な構成は、バイト列のシャッフル、ガロア体を元にしたビットのシャッフル、鍵の拡張とかそういうところかな。
ビットのシャッフルにはS-box という変換表のようなものと、その逆のi-boxというようなものを持っていたりします。これは、計算で作れるものですが、計算が小難しいので表で持っているパターンが多いようです。
鍵はてきとーに引き延ばされてラウンドに分けて使います。
中心の暗号処理は AES (FIPS 197) の 5.1くらいから
Cypher(byte in[4*Nb], byte out[4*Nb], word w[Nb*(Nr+1)]) begin byte state[4, Nb]
state = in
AddRoundKey(state, w[0, Nb-1]) // See Sec. 5.1.4.
for round = 1 step 1 to Nr-1 SubBytes(state) // See Sec.5.1.1 ShiftRows(state) // See Sec.5.1.2
MixColumns(state) // See Sec.5.1.3 AddRoundKey(state, w[round*Nb, (round+1)*Nb-1]) end for SubBytes(state) ShiftRows(state) AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1]) out = state end
の4つの処理を繰り返して暗号ができています。
逆の手順で元に戻すことができます。
まずは標準的な実装をしてみて、最適化をあとでしてみると理解しやすいです。
SubBytesとShiftRowsが入れ換え可能だったり、いろいろ隙はあります。
メインの処理をJavaに直すと
public byte[] encrypt(byte[] src, int offset) {
byte[] s = new byte[16];
System.arraycopy(src, offset, s, 0, 16);
addRoundKey(s, 0);
for (int r = 1; r < Nr; r++) {
subBytes(s);
shiftRows(s);
mixColumns(s);
addRoundKey(s, r);
}
subBytes(s);
shiftRows(s);
addRoundKey(s, Nr);
return s;
}
src から入力してsにコピー、sを更新してからreturn で返す形にしておく。
1回で処理できるのは128bit(8ビット×16バイト)固定なのでブロック暗号といわれています。暗号利用モードをつけないと安全には使えないのですがそれはまた別途。
鍵の長さはブロック長とは別に128,192,256bitの3つから選べます。鍵長はメインの処理でaddRoundKeyを含んでいる処理を繰り返す回数(Nrのところ)にも影響しますが、ブロック長などには影響しません。
Nr は鍵の長さから作るので鍵を初期設定するinit()の処理を少し書いておく。
private int Nr;
public void init(byte[] key) {
if (key.length != 16 && key.length != 24 && key.length != 32) {
throw new SecurityException("key length");
}
int Nk = key.length / 4;
Nr = Nk + 6;
}
initに鍵を渡して初期化する中で、鍵の長さを元にしてNrも決まる。10,12,14かな。128bit × (Nr+1) になるよう、鍵を10倍くらいに拡張します。暗号処理のなかではよく行われる謎です。
private static final int Nb = 4;
void addRoundKey(byte[] s, int round) {
round *= Nb;
for (int c = 0; c < 16; c++) {
s[c] ^= (byte)(w[round + c / 4] >> ((3 - (c % 4)) * 8));
}
}
keyから生成したroundkey の w を s列と XOR していく処理。wは32bit単位なので8bitに変換しながら適応している。最適化する場合は32bit側にまとめるといい。
round は 0からNrまで。
init() の続きでroundKey を作る
private int[] w; // ラウンド鍵
init()のつづき {
w = new int[Nb * (Nr + 1)];
btoi(key, 0, w, Nk); // byte列をint列に変換する
int temp = 0;
for (int i = Nk; i < Nb * (Nr + 1); i++) {
temp = w[i - 1];
if (i % Nk == 0) {
temp = subWord(rotWord(temp)) ^ Rcon[i / Nk];
} else if (Nk > 6 && i % Nk == 4) {
temp = subWord(temp);
}
w[i] = w[i - Nk] ^ temp;
}
}
keyのビット長でラウンド鍵の長さと暗号のループ回数も変わります。
鍵の後ろに足りない部分を足して128bit × ラウンド数(Nr+1)の長さになるように調整しています。
btoi は適当にbyte列をint列に変えられればいいです。
Javaなので? 上のMSBから順に埋めていきます。逆に下のLSBから並べても作れるかもしれません。KDDIのKCipher-2などはLSBが先のようでした。
仕様と実装の位置の対応を把握していればどの並び順でもよいです。
private static void btoi(byte[] src, int offset, int[] dst, int length) {
for (int i = 0; i < length; i++) {
int t = offset + i * 4;
dst[i] = 0;
for ( int b = 0; b < 4; b++ ) {
dst[i] <<= 8;
dst[i] |= src[t + b];
}
}
}
offsetは他で使うかも。
Rconはガロア体がでてくるのでどこかで初期設定しておく。10くらいまでしか使われない。
static {
int n = 1;
for (int i = 1; i < 11; i++) {
Rcon[i] = n << 24;
n = xtime(n);
}
}
xtimeはガロア体とやらの計算です。
m(x) = x8 + x4 + x2 + x + 1
というような式になっているのでそれっぽく。
static final int xtime(int b) {
b = b << 1;
if ( b & 0x100 ) {
b = (b & 0xff) ^ 0x1b;
}
return b;
}
というような処理を書きがちです。
最上位のビットが1のときに2倍してあふれたぶんを+0x1bしているので7bitシフトしてあげると0x1bをXORするフラグとして使えます。さらに0x100を加えることで桁あふれのぶんを消します。
static final int xtime(int b) {
return (b << 1) ^ ((b >> 7) * 0x11b);
}
条件分岐をなくしておくのがよいです。
鍵の初期化で使う
private static int rotWord(int word) {
return (word << 8) | (word >>> 24);
}
8ビット回転するだけです。 Javaでは符号ビットが邪魔しないよう >>> を使います。Integerにも#rotateLeft(int i, int distance) や#rotateRight(int i, int distance)があるので使ってみてもいいかもしれません。
sbox を使います。
鍵の初期化で使うSubWordsと暗号化で使うSubBytes
4バイト列と16バイト列にsboxを通した値を返します。intとbyteなので少々処理は変わります。
private static int subWords(int word) {
return (sbox(word >>> 24) << 24)
| (sbox(word >> 16) << 16)
| (sbox(word >> 8) << 8)
| sbox(word);
}
static void subBytes(byte[] s) {
for (int i = 0; i < s.length; i++) {
s[i] = (byte)sbox(s[i])];
}
}
sboxはAESで重要な変換表です。配列でも関数でもいいのですが、int[] な配列にしてあらかじめ計算しておくといいのかもしれません。今回は生成式があったので計算で作ってみます。
static final int sbox(int i) {
return sbox[i & 0xff];
}
作り方は後ほど。
sの配列はAESの上では4x4に分けられているので、それをシフトします。以下てきとーなコード。
◎④⑧⑫ → ◎④⑧⑫
①⑤⑨⑬ → ⑤⑨⑬①
②⑥⑩⑭ → ⑩⑭②⑥
③⑦⑪⑮ → ⑮③⑦⑪
説明上では縦に並んだ列を横にシャッフルしているので、バイト単位でなんとかなればいいです。
void shiftRows(byte[] s) {
byte t = s[1]; s[1] = s[5]; s[5] = s[9]; s[9] = s[13]; s[13] = t;
t = s[2]; s[2] = s[10]; s[10] = t;
t = s[6]; s[6] = s[14]; s[14] = t;
t = s[3]; s[3] = s[15]; s[15] = s[11]; s[11] = s[7]; s[7] = t;
}
SubBytes と ShiftRows は順番を入れ換えても何の影響もないので適度に速い方向を探ったりします。
列ごとにガロア体を効かせた計算をします。
|d0| | 02 03 01 01 | |b0|
|d1| | 01 02 03 01 | |b1|
|d2| = | 01 01 02 03 | |b2|
|d3| | 03 01 01 02 | |b3|
カスタマイズが大幅に効いてくる箇所です。
void mixColumns(byte[] s) {
byte[] d = new byte[16];
for (int c = 0; c < Nb; c++) {
d[c * 4 ] = (byte) (mul(2, s[c * 4]) ^ mul(3, s[c * 4 + 1]) ^ mul(1, s[c * 4 + 2]) ^ mul(1, s[c * 4 + 3]));
d[c * 4 + 1] = (byte) (mul(1, s[c * 4]) ^ mul(2, s[c * 4 + 1]) ^ mul(3, s[c * 4 + 2]) ^ mul(1, s[c * 4 + 3]));
d[c * 4 + 2] = (byte) (mul(1, s[c * 4]) ^ mul(1, s[c * 4 + 1]) ^ mul(2, s[c * 4 + 2]) ^ mul(3, s[c * 4 + 3]));
d[c * 4 + 3] = (byte) (mul(3, s[c * 4]) ^ mul(1, s[c * 4 + 1]) ^ mul(1, s[c * 4 + 2]) ^ mul(2, s[c * 4 + 3]));
}
System.arraycopy(d, 0, s, 0, 16);
}
だいたいこんな感じの処理です。Nb は4ですね。
int mul(int x, byte ys) {
int m = 0;
int y = ys & 0xff;
for (int i = 0; i < 4; i++) {
if ((x & 1 << i) != 0) {
m ^= y;
}
y = xtime(y);
}
return m;
}
mulでは桁上がりしない掛け算をします。xとyを入れ換えても成立しますが、intとbyteなのでそれっぽく。
xが小さいのでループを省略して少し速くするとこうなるのですが
int mul(int x, byte ys) {
int m = 0;
int y = ys & 0xff;
while (x > 0) {
if ((x & 1) != 0) {
m ^= y;
}
y = xtime(y);
x >>>= 1;
}
return m;
}
AESではxに4bitまでしか使っていないので i は0から3までで上のようにしておくのがいいのかもしれません。省略できるようにしておくと計算量が変わって脆弱性に繋がるらしいです。まだif文は残っていますがあとでなくなります。
他の方法もあるようですが、とりあえずこんな感じのを元にして最適化するのでここまで。
残ったsboxを作ってみます。説明が省かれていたり意味がわからなかったりすると思うので、わからなければAESで説明されている表をそのまま使いましょう。
Wikipedia (英語)版
static { // に加える
// Wikipedia版 sboxつくる
// https://en.wikipedia.org/wiki/Rijndael_S-box
int p = 1, q = 1;
do {
p ^= xtime(p); // p・3
q ^= q << 1;
q ^= q << 2;
q ^= q << 4;
q &= 0xff;
q ^= (q >> 7) * 0x09;
int xf = q ^ ( q << 1) ^ (q << 2) ^ (q << 3) ^ (q << 4);
xf = 0x63 ^ (xf ^ (xf >> 8)) & 0xff;
sbox[p] = xf;
ibox[xf] = p;
} while (p != 1);
sbox[0] = 0x63;
ibox[0x63] = 0;
}
順には作れないので次のがいいのか?
https://tociyuki.hatenablog.jp/entry/20160426/1461669307
https://tociyuki.hatenablog.jp/entry/20160427/1461721356
を参考に指数などを駆使して逆数を出しているもの
static { // に加える
int[] logGF = new int[256];
int[] expGF = new int[256];
int n = 1;
for int e = 0; e < 255; e++) {
logGF[n] = e;
expGF[e] = n;
n ^= xtime(n);
}
logGF[0] = 0;
expGF[255] = expGF[0];
for (int i = 0; i < 256; i++) {
// sbox
int s = (i == 0) ? 0 : expGF[256 - logGF[i]];
s = s ^ (s << 1) ^ (s << 2) ^ (s << 3) ^ (s << 4);
sbox[i] = (0x63 ^ s ^ (s >> 8)) & 0xff;
// ibox
s = (i << 1) ^ (i << 3) ^ (i << 6);
s = (0x5 ^ s ^ (s >> 8)) & 0xff;
ibox[i] = (s == 0) ? 0 : expGF[255 - logGF[s]];
}
}
これまでの処理で暗号化はできるようになったはずです。たったこれだけです。
あとは最適化をすると速く安全になります。
AESでは1バイトをランダムにしていく要素です。
数を2倍にしていくと、8ビットを超えてしまうのはすぐですが、ある数を加えたりすると8ビットで循環できる変換ができるようです。
GF(2) というようなビット列として繰り上がり、繰り下がりのない計算をするものっぽいので、デジタル的なところと似ています。深みにはまりたい場合は調べてみるとよいでしょう。
m(x) = x8 + x4 + x2 + x + 1
class GF などを作って mul や xtime などをまとめておくとあとから楽かもしれません。
ここでは深くは説明しません。
暗号化したものを元に戻す過程です。
手順を逆に辿ればいいのですが、mixColumnsなどは逆に辿れないので少し変則的です。
まずは計算量の多そうなところをなんとかしていきます。
mixColumns の mul の計算は 1, 2, 3 しかないので、ケースわけしておくことができます。
x = 1のとき、yそのまま。2のとき xtime(y & 0xff)。 3のとき、y ^ xtime(y & 0xff)
void mixColumns(byte[] s) {
byte[] d = new byte[16];
for (int c = 0; c < Nb; c++) {
d[c * 4 ] = (byte) (xtime(s[c * 4] & 0xff) ^ mul(3, s[c * 4 + 1]) ^ s[c * 4 + 2] ^ s[c * 4 + 3] );
d[c * 4 + 1] = (byte) ( s[c * 4] ^ xtime(s[c * 4 + 1] & 0xff) ^ mul(3, s[c * 4 + 2]) ^ s[c * 4 + 3] );
d[c * 4 + 2] = (byte) ( s[c * 4] ^ s[c * 4 + 1] ^ xtime(s[c * 4 + 2] & 0xff) ^ mul(3, s[c * 4 + 3]));
d[c * 4 + 3] = (byte) (mul(3, s[c * 4]) ^ s[c * 4 + 1] ^ s[c * 4 + 2] ^ xtime(s[c * 4 + 3] & 0xff));
}
System.arraycopy(d, 0, s, 0, 16);
}
xtime() は配列にしてしまいます。
invMixColumns も同様に分けることができますが少々複雑かもしれません。
データをbyte列からint列に変更します。これによりmixColumnsが高速化できます。
AES