[C++] Base32をデコードする

#Base32をデコードしたいとき

自分用のGoogle Authenticatorライクなアプリを、iPhoneとかMacとかに、できるだけセキュアに作りたいとかいう要望があるかとは思います。Google Authenticatorとかの構造は、QRコードを読み込んでURIからDomain Secretキーを保存して、 Secretキーと現在の時間からHMAC-SHA1で出てきた値をTOTPのワンタイム認証トークンとして使うというのが構造です。

このときに、以下のようなフローになります。

1. QRコードからURIを取得する（オープンソースにいくつかある）
* URIからSecretを取り出す（文字列処理）
* SecretをBase32でデコードしてSecretバッファに変換
* Secretバッファと現在時刻をHMAC-SHA1でダイジェストを取得（OpenSSLとかMac/iOSではCommonCryptoとか）

Secretを名前をつけて、いくつもセキュアに端末内に保存できるようにするのが、iOSアプリとかを作るうえでは肝になりそうです。このときに、**SecretをBase32でデコードしてSecretバッファに変換** が意外にハマるので、解説を書いておこうと思いました。

#Base32とは

Base32は、[RFC4648](http://tools.ietf.org/html/rfc4648.html)で規定されています。
要は32種類（A-Z、2-7）＋1記号（=）の文字でバイナリ列を表現するための仕組みです。エンコードのアルゴリズムは、harasouさんの以下の記事が分かりやすいです。

https://harasou.jp/2015/08/13/base32/

5ビット1文字でデータが流れてくるものを、処理しやすいように8ビットのデータに直すことになります。それには、最小公倍数である40ビット単位（8文字、5バイト）で埋めてゆくという処理が必要で、余った時の処理も必要になります。

#Base32のデコード処理

Base32のデコード処理は、おおよそ以下のようになります。

1. （前処理1）文字列バッファのバリデーション
* （前処理2）バッファの最終的な長さ（バイト数）の取得
* （デコード本体1）１文字ずつ文字列を数値列に変換する
* （デコード本体2）40ビットごとにおおきいvectorにうめてゆく
* （デコード本体3）ターゲットのバッファに埋める

ちょっと細かく解説してみます。

## （前処理1）文字列バッファのバリデーション
使ってはいけない文字をつかっていないかの確認します。
使う文字は以下です。

|数値|文字シンボル|ASCIIコード|
|:---:|:---:|:---:|
|0|A|0x41|
|1|B|0x42|
|...|...|
|24|Y|0x59|
|25|Z|0x5a|
|26|2|0x32|
|27|3|0x33|
|...|...|
|30|6|0x36|
|31|7|0x37|
|パディング符号|=|

つまり、「A-Z」「2-7」「=」以外は使ってはいけませんので、文字列を走査して確かめます。


```cpp:Base32Decoder.cpp
    // check Range of values
    for (char c : input_str_) {
        if (((c > 0x31) && (c<0x38)) || ((c>0x40) && (c<0x5b))) {
            continue;
        } else {
            if (0x3d != c) {
                // base32 validation error
                return -1;
            }
        }
    }
```
## （前処理2）バッファの最終的な長さ（バイト数）の取得
バッファの最終的な長さ（バイト数）の取得します。
パディング文字は決まっていますから、パディング文字があるところまでは、string::findで見つかった場合は、そこの位置x5/8をすれば、バッファの長さが出てきます。パディング文字がなかったら、文字列の長さをx5/8して求めます。

```cpp:Base32Decoder.cpp
int Base32Decoder::length() const{
    ...
    // find first position of Padding
    std::size_t found = input_str_.find(std::string("="));
    if (found == std::string::npos) {
        return (input_str_.length() * 5)/8;
    }
    return (found) * 5 / 8;
}
```

##（デコード本体1）１文字ずつ文字列を数値列に変換する
１文字ずつ文字列を数値列vector<uint8_t>のbase32digitVectorに変換します（高速化するときはここを並行化する）。上記の表を、テーブルを作って処理している方も多いです。ただ、変換テーブルの規則性が簡単なので、以下のように、ASCIIコードから直接数字を作りました。

```cpp:Base32Decoder.cpp
    std::vector<uint8_t> base32digitVector;
    for (char c : input_str_) {
        if ((c > 0x31) && (c<0x38)) { // 2-7の場合
            base32digitVector.push_back((c - 0x32 + 26));
        }
        if ((c>0x40) && (c<0x5b)) { // A-Zの場合
            base32digitVector.push_back((c - 0x41));
        }
    }
```

##（デコード本体2）40ビットごとに大きいvectorに埋めてゆく

40ビットごとに処理するために、vector<uint64_t>のfortyBitValueVectorを用意し、一つのuint64_tの下位40ビットを上から5ビットずつ8回で埋めてゆきます。

```cpp:Base32Decoder.cpp
    std::vector<uint64_t> fortyBitValueVector;
    bool bExistPadding = base32digitVector.size() % 8 == 0;
    int fortyBitValueVector_length = bExistPadding ? (base32digitVector.size()/8) : (base32digitVector.size()/8) +1;
    for (int i = 0; i < fortyBitValueVector_length; i++) {
        uint64_t bin = 0;
        if (i != bExistPadding ? fortyBitValueVector_length : fortyBitValueVector_length-1) {
            for (int j = 0; j < 8; j++) {
                bin |= ((uint64_t)base32digitVector[i*8+j]) << ((7-j)*5);
            }
            fortyBitValueVector.push_back(bin);         
        }  else {
            for (int j = 0; j < base32digitVector.size()%8; j++) {
                bin |= ((uint64_t)base32digitVector[i*8+j]) << ((7-j)*5);
            }
            fortyBitValueVector.push_back(bin);         
        }
    }

```

それを数値列の長さが8で割り切れたときは数値列の長さを8で割った回数を、8で割り切れなかったときは数値列の長さを8で割った数に1足した回数繰り返し、fortyBitValueVectorに足していきます。


```cpp:Base32Decoder.cpp
            for (int j = 0; j < 8; j++) {
                bin |= ((uint64_t)base32digitVector[i*8+j]) << ((7-j)*5);
            }
```

このとき、対象のuint64_tのオブジェクトの40ビットのところから5ビット単位で埋めてゆくために、 ((7-j)*5)ずつビットシフトさせてビットを埋めるという工夫をしています。


##（デコード本体3）ターゲットのバッファに埋める
fortyBitValueVectorに対して、1つずつに、**エンディアンをひっくり返して**から、24ビット右にシフトし、ターゲットのバッファに対して、memcpyで5バイトだけコピーする。これを全部に適用させると、ターゲットバッファに対して綺麗にデータが並んでいきます。

```cpp:Base32Decoder.cpp

    int i = 0;
    for (uint64_t t : fortyBitValueVector) {
        uint64_t bs_t_val = bswap_64(t) >> 24;
        if (i != fortyBitValueVector.size()%5 == 0 ? fortyBitValueVector.size() : fortyBitValueVector.size() - 1) {
            memcpy( &data[i*5], &bs_t_val, 5);        
        } else {
            memcpy( &data[i*5], &bs_t_val, keylen % 5);        
        }
        i++;
    }
```

#まとめ
Base32は、このような処理でデコードすることができます。最近のMac/Linux/Win/iOS/Android周りではLittle Endianが普通ですが、通信バッファは通常、Big Endianなので、エンディアンをひっくり返して、前から埋めていく必要があります。ビットシフトやビットスワップが必要なので、そこはちょっと慣れが必要かもしれません。とくに、エンディアンをひっくり返す、byteswap.hがLinux（glibc）では含まれていますが、OSXやiOSにはないので、別に用意する必要があったりするという落とし穴もあります。


なお、ここ書いた処理は、こちらにありますのでぜひ参考にしてみてください。
https://github.com/1mc1dj/TotpCommonCrypto/blob/master/src/Base32Decoder.cpp

こちらはmacで、コマンドラインでOpenSSLを使わずにMacのSystem FrameworkにあるCommonCryptoの実装を使って、Secretから直接onetime passを算出する実装の一部です。そちらをMITライセンスで公開しています。

**何かの参考になれば嬉しいです**