演算法漫談 - Padding 填充如何表示原始資料長度？

在演算法中常有將原始資料補到固定長度的需求，例如：Base64 編碼是將三個 Byte 資料轉成四位英數字加 +、/ 符號(大寫x26 + 小寫x26 + 數字x10 + 符號x2 = 64 = 2⁶，四個字元 4 x 2⁶ == 3 x 2⁸ 三個Byte)，若資料 Byte 數非 3 的倍數就要補零到所需長度。而 AES 加密計算區塊以 128 bits 為處理單位，DES 區塊大小則是 64 bits，不同長度原始資料必須補足 16 Bytes 或 8 Bytes 整數倍再進行運算。

題外話：最近 Base64 編碼上了新聞，臺中市警察局提供交通違規檢舉資料出包(身分證未加密烏龍！臺中市警察局公布檢舉達人個資遭洩露)，承辦人員不知缺少相關知識還是故意裝糊塗，竟把 Base64 編碼當馬賽克用，讓檢舉人身分證號穿著國王新衣遊街。殊不知這跟當年第四台鎖碼成人頻道一樣，懂門道弄支解碼棒，人人能看。而 Base64 解碼棒更是唾手可得，在瀏覽器按 F12 用一行指令 atob('QTEyMzQ1Njc4OQ==') 即可破解...

補零的一項挑戰是必須記錄或辨別原始資料長度，否則還原時會搞不清楚最後一個區塊哪些是原始資料，哪些是填充物。

Base64 採用的做法是填充部分用 64 個字元之外的符號「=」來表示，資料三個 Bytes 為單位，若結尾有兩個 =，表示資料長度除 3 的餘數為 1；若結尾有一個 =，則表除 3 餘數為 2：

換到 AES 或 DES byte[16]/byte[8] 填充的場景，byte 0 - 255 每一個都可能是有效資料，無法像 Base64 找 64 個字元之外的符號表示。一個無腦解法是在資料前方加個長度欄位，用幾個 Byte 記錄長度，但資料結構跟處理邏輯會因此複雜化，不夠優雅。但是，若不這麼做，原始資料有無限多種可能，就是會遇到跟填補樣式一模一樣的組合，讓你分不出是長度不足填補過的內容，還是長度剛好內容雷同的原始資料。

問題看似無解，其實前人早就想到巧妙解法。以 PKCS #5: Password-Based Cryptography Specification Version 2.0 為例，它採用的填充規則如下：(註：另有 PKCS #7，原理相同，但區塊長度支援 1 ~ 255 Bytes)

Concatenate M and a padding string PS to form an encoded message EM:
    EM = M || PS ,
where the padding string PS consists of 8-(||M|| mod 8) octets
each with value 8-(||M|| mod 8). The padding string PS will
satisfy one of the following statements:

     PS = 01, if ||M|| mod 8 = 7 ;
     PS = 02 02, if ||M|| mod 8 = 6 ;
     ...
     PS = 08 08 08 08 08 08 08 08, if ||M|| mod 8 = 0.
     
The length in octets of the encoded message will be a multiple
of eight and it will be possible to recover the message M
unambiguously from the encoded message. (This padding rule is
taken from RFC 1423 [3].)

若要補足 8 Bytes，當長度除 8 餘 7，補 01；除 8 餘 6 補 02 02；除 8 餘 5 補 03 03 03；... 若除 8 整除，則補 08 08 08 08 08 08 08 08。

還原時，讀取最後區塊的最後 Bytes，若為 01 就取前 7 Bytes、02 取前 6 Bytes、03 取前 5 Bytes... 若為 08 則整個區塊丟棄，原始資料到前一區塊為止。

就醬，靠著長度整除 8 硬補一組 8 個 8，雖然浪費 8 個 Bytes，原本無法辨別最後區塊是填補後結果還是原始資料的困擾，就這麼巧妙解決了，聰明。不過，這個做法也有限制：其適用區塊長度只到 255，且區塊愈大，長度整除時浪費的空間/頻寬就愈多。儘管如此，PKCS #5/#7 在一般應用仍是簡單有效的填充方法。

最後，用一小段 C# 實測結束這回合。

for (int i = 1; i < 10; i++)
{
    var data = new byte[i];
    for (int j = 0; j < i; j++) data[j] = (byte)0xff;
    var padded = pad(data, 8);
    var trimmed = trimPadding(padded);
    Console.WriteLine(new string('-', 40));
    Console.WriteLine($"OrigData: {BitConverter.ToString(data)}");
    Console.WriteLine($"  Padded: {BitConverter.ToString(padded)}");
    Console.WriteLine($"Restored: {BitConverter.ToString(trimmed)}");
}

byte[] pad(byte[] data, int blockSize)
{
    var padSize = blockSize - (data.Length % blockSize);
    var padding = new byte[padSize];
    for (var i = 0; i < padSize; i++)
    {
        padding[i] = (byte)padSize;
    }
    byte[] padded = new byte[data.Length + padSize];
    data.CopyTo(padded, 0);
    padding.CopyTo(padded, data.Length);
    return padded;
}
byte[] trimPadding(byte[] data)
{
    int padSize = data[data.Length - 1];
    byte[] trimmed = new byte[data.Length - padSize];
    Array.Copy(data, trimmed, trimmed.Length);
    return trimmed;
}

Introduction to PKCS#5 padding.