符号理論

Base64 エンコーディング

Takami Torao #Base64
  • このエントリーをはてなブックマークに追加

概要

Base64 エンコーディングは任意の長さを持つバイナリデータを ASCII テキストに変換するための符号化アルゴリズム。

通信に使用できるテキストが ASCII 文字 (7ビット文字) の範囲の限定されていたインターネットの初期に広く使用されていたが、現在でもバイナリデータをJSON 形式の文字列値として保存するケースなどでよく使用されている。

Table of Contents

  1. 概要
  2. アルゴリズム
  3. 派生符号化変換

アルゴリズム

Base64 を用いて任意長の 8 ビットバイトシーケンスをエンコードするには次の手順で行う。

  1. ビットシーケンスを 6 ビットに区切り、それぞれを Table 1 に示すアルファベット \(\mathcal{A}\) の対応する文字に置き換える。ビットシーケンスの末尾が 6 ビットに満たない場合は 0 でパディングして 6 ビットとする。

  2. 4 個のアルファベットごとに 1 つの符号語を構成する。アルファベットが 4 個に満たない場合は \({\tt =}\) でパディングする。

Table 1. Base64 のアルファベット \(\mathcal{A}\)
数値 文字 数値 文字 数値 文字 数値 文字 数値 文字 数値 文字 数値 文字 数値 文字
0 A 8 I 16 Q 24 Y 32 g 40 o 48 w 56 4
1 B 9 J 17 R 25 Z 33 h 41 p 49 x 57 5
2 C 10 K 18 S 26 a 34 i 42 q 50 y 58 6
3 D 11 L 19 T 27 b 35 j 43 r 51 z 59 7
4 E 12 M 20 U 28 c 36 k 44 s 52 0 60 8
5 F 13 N 21 V 29 d 37 l 45 t 53 1 61 9
6 G 14 O 22 W 30 e 38 m 46 u 54 2 62 +
7 H 15 P 23 X 31 f 39 n 47 v 55 3 63 /

例1. 0x0123456789ABCDEF の 8 バイトを Base64 で符号化する。この入力は次のような 8✕8 ビット列で表される。\[ {\tt \small 00000001.00100011.01000101.01100111.10001001.10101011.11001101.11101111} \] まず入力のビットシーケンスを 6 ビットに分割する。このとき 6 ビットに満たない端数は 0 でパディングして 6 ビットにする。\[ \begin{array}{l} {\tt \small 000000.010010.001101.000101.011001.111000.100110.101011.110011.011110.1111\underline{00}} \\ = 0,18,13,5,25,56,38,43,51,30,60 \end{array} \] そして、それぞれを Table 1 に示すアルファベット \(\mathcal{A}\) の対応する文字に置き換え、長さ 4 の符号語に変換する。不足分はパディング文字 \({\tt =}\) を使用する。\[ \begin{array}{l} \mathcal{A}(0,18,13,5).\mathcal{A}(25,56,38,43).\mathcal{A}(51,30,60)\underline{\tt =} \ = {\tt \small ASNF.Z4mr.ze8=} \end{array} \] この操作により 0x0123456789ABCDEF は 3 つの符号語で構成される ASNFZ4mrze8= という符号に変換される。

Base64 符号のデコードは逆の操作を行う。

  1. Base64 符号を 4 文字ごとの符号語に区切る。それぞれの符号語について:

    1. 最後の符号語ではない場合、符号語を構成するそれぞれの文字から Table 1 に従って 24 ビット (3 バイト) 分のデータを復元する。

    2. 最後の符号語の場合:

      1. 末尾に \({\tt =}\) を含まない場合、同様に 24 ビット (3 バイト) 分のデータを復元する。

      2. 末尾の \({\tt =}\) が 1 個の場合、符号語の前方 16 ビット (2 バイト) 分のデータを復元する。

      3. 末尾の \({\tt =}\) が 2 個の場合、符号語の前方 8 ビット (1 バイト) 分のデータを復元する。

Base64 は 8 ビットバイトを仮定しているため、最後の符号語にパディング文字 = が何個含まれているかを調べることで末尾の有効ビット数も決定することに注意。

例2. Base64 符号 ASNFZ4mrze8= をデコードする。\[ \begin{array}{l} {\tt ASNF}.{\tt Z4mr}.{\tt ze8=} = \mathcal{A}(0,18,13,5).\mathcal{A}(25,56,38,43).\mathcal{A}(51,30,60)\underline{\tt =} \\ \rightarrow {\small {\tt (00000001,00100011,01000101)}.{\tt (01100111,10001001,10101011)}.{\tt (11001101,11101111)}} \\ = {\tt 0x0123456789ABCDEF} \end{array} \]

Base64 符号に含まれる空白文字 (空白、改行、タブなど) は慣例的に無視されることが多い。これは古い電子メールシステムで 1 行あたりの桁数に制限があったり、改行の許可されている HTTP ヘッダで利用するためである。

派生符号化変換

Base64 はバイナリを 64 種類の文字を使用した文字列に変換する。これは、基数 256 の数列を基数 64 の数列に変換し、それぞれの桁を文字にマッピングすることと等価である。Base58 のような 64 以外の符号化についても、対象とする基数が異なるだけで同じ処理となることが分かるだろう。2 のべき乗となる基数に対しては余剰演算の代わりにシフト演算とビット操作が使用できるため効率が良い。