天天看點
傳回

如何生成安全的資源ID

一、前言

對于一些圖檔，文章，或者使用者首頁等，需要構造URL提供給外部。

對外釋出URL時，通常是 “域名/路徑/資源ID”,

其中，路徑是可選項，比如生成短連結時可能就是直接“域名/資源ID”。

舉例：

掘金的URL格式 ：

https://juejin.im/user/59abef0af265da246c4a3de1 https://juejin.im/post/5d8ab56df265da5bb252d67c

簡書的 URL格式：

https://www.jianshu.com/u/11d3f06afbcd https://www.jianshu.com/p/3df395d8a6bc

這些連結最後的資源ID部分是怎麼構造的呢？

雖然無法确切知曉，但猜測一下也無妨。

掘金的資源ID，六進制字編碼，32位元組，可能時UUID（去掉分隔線）或者MD5。

無論是UUID還是MD5，都是有随機性的，是以不擔心被找規律，由于取值範圍有128bit, 發生沖突的機率也微乎其微。

簡書的資源ID，十六進制編碼，12位元組，也就是48bit，取值範圍兩百多萬億，夠配置設定了，可讀性也較好。

但是48bit的取值範圍，就不然像UUID一樣取随機值了，否則容易沖突，

是以，猜測原始ID是通過分段ID或者自增ID構造，自增ID的機率比較大，因為像snowflake算法這種需要的較長的有效位(bit數）。

但是自增ID的話，會呈現規律性（前面的字元不變），其他人就可以連續做幾個請求，算出其自增的step，然後就可以窮舉其所有資源了。

是以，在擷取增長ID之後，十六進制編碼之前，可能有一次加密。

那麼，如何做加密呢？

以下讨論就不說“猜測”了，而是如果讓我來做，我會如何設計。

二、對ID做加密

加密結果需要滿足以下幾點：

1、難以推測原ID；

2、加密後的ID和原ID一一映射，以避免重複；

3、對整數ID(64bit, 有效位<=64) 加密，加密後長度不變。

  • 第1點：

    MD5，SHA，AES，DES等都可以；

  • 第2點：

    MD5等摘要算法就不滿足了，不同的原文可能計算出相同的哈希；

要滿足一一映射，需要函數可逆。

  • 第3點：

    AES，DES也不滿足。

AES加密結果最短也有16位元組。

DES對小于8位元組的原文加密，密文為8位元組；對8位元組的原文加密，密文為16位元組。

綜上，我們需要一個對整數的加解密，且密文不會“膨脹”的函數。

不妨去看下AES是怎麼做的，抄個作業。

三、 AES 算法

接下來以AES128為例，看下AES的加密步驟。

部分圖文來自文章

《碼算法詳解——AES》

和

《AES算法描述及C語言實作》

，侵删。

3.1 整體流程

AES128的核心運算是對16位元組(128bit)的内容加解密。

若原文長于16位元組，則進行分組，16位元組一組，如果最後一組不足16位元組，則補齊到16位元組。

AES128要經曆10輪運算，其中1-9輪是相同的，第10輪稍有一點差別。

每輪運算涉及位元組替代、行移位、列混淆、輪密鑰加等四個子運算；

每個子運算都有逆運算，用相反順序逆運算可解密出原文。

3.2 位元組替代（SubBytes）

位元組替代需要用到S盒，S盒有兩個數組，且命名為：SBOX， INV_SBOX。

S盒有這樣的特點:

若y = SBOX[x]，則x = INV_SBOX[y]；

換個寫法： x = INV_SBOX[SBOX[x]]。

舉個栗子, 一個簡單的2階S盒：

int[] s_box = new int[]{2, 0, 3, 1};
    int[] inv_s_box = new int[]{1, 3, 0, 2};
    for (int x = 0; x < s_box.length; x++) {
        System.out.print(inv_s_box[s_box[x]] + " ");
    }
    System.out.println();
    for (int x = 0; x < s_box.length; x++) {
        System.out.print(s_box[inv_s_box[x]] + " ");
    }

輸出：

0 1 2 3

0 1 2 3

AES的S盒是8階的（8 x 8), 剛好取盡一個位元組的範圍(0-255)，至于怎麼構造S盒本文就不展開了。

位元組替代運算：

for (int j = 0; j < 16; j++) {
        state[j] = SBOX[state[j]];
    }

逆向位元組替代:

for (int j = 0; j < 16; j++) {
        state[j] = INV_S_BOX[state[j]];
    }

位元組替代運算提供了算法的混淆性。

和代碼混淆一樣，原文本來具備可讀性，混淆後就變得不可讀了；

但是混淆後模式沒有改變，比如原來方法foo()混淆後變為a(), 則混淆後所有調用foo()的地方都是a()。

也就是，位元組替代後仍然存在統計特征。

3.3 行位移（ShiftRows）

行位移比較簡單，就是将16位元組作為一個4行4列的矩陣，

其中1、2、3行分别左移（逆運算為右移）1、2、3個位元組。

3.4 列混淆（MixColumns）

列混淆是所有子運算中最複雜的。

和行位移一樣，将16位元組劃分為4行4列；

不同的是，列混淆是分别對每一列的4個位元組做運算（和一個4x4的矩陣左乘）。

解密時也是左乘矩陣，解密矩陣是加密矩陣的逆矩陣。

某一列的運算代碼如下：

static inline uint8_t mul2(uint8_t a) {
    return (a & 0x80) ? ((a << 1) ^ 0x1b) : (a << 1);
}

/*
 * 左乘置換矩陣
 * [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 multiply(uint8_t *b, uint8_t *d) {
    uint8_t t = b[0] ^ b[1] ^ b[2] ^ b[3];
    // d0 = (b0 << 1) + (b1 << 1) + b1 + b2 + b3 = ((b0 + b1) << 1) - b0 + t
    d[0] = mul2(b[0] ^ b[1]) ^ b[0] ^ t;
    d[1] = mul2(b[1] ^ b[2]) ^ b[1] ^ t;
    d[2] = mul2(b[2] ^ b[3]) ^ b[2] ^ t;
    d[3] = mul2(b[3] ^ b[0]) ^ b[3] ^ t;
}

矩陣運算需要進行加法運算和乘法運算，計算機的直接整數相加和直接整數相乘可能會溢出，進而丢失資訊，不可逆；

是以AES引入了“伽羅華域（也叫伽羅瓦域）”運算，感興趣的讀者可以閱讀文章《

伽羅華域運算及C語言實作

》了解一下。

行位移和列混淆共同提供了算法的擴散性。

擴散的目的是讓明文中的單個數字影響密文中的多個數字，進而使明文的統計特征在密文中消失。

最理想的情況是達到

雪崩效應

的效果:

當輸入發生最微小的改變（例如，反轉一個二進制位）時，也會導緻輸出的劇變（如，輸出中一半的二進制位發生反轉）。

如果隻有列混淆運算，則最終的效果是 [0,3] , [4,7], [8,11], [12,15] 四個分組分别擴充；

加上了行位移，才可以達到[0, 15]的位元組的擴散效果（明文一個位元組改變，密文16個位元組全都會随機變化）。

當然，需要經曆多輪運算才會有雪崩效應的效果，隻做一輪運算是不夠的。

3.5 輪密鑰加（AddRoundKey）

輪密鑰加是四個字運算中最簡單的，具體就是16個位元組分别和輪密鑰做異或運算。

輪密鑰是通過原始密鑰計算得來的，AES128一共要做11次輪密鑰加。

結合密鑰的運算，提供了算法的保密性。

如果沒有密鑰運算，就好比門沒上鎖，再堅固的防盜門也是形同虛設。

四、整數加密方案

AES是典型SP型密碼, SP型密碼網絡結構非常清晰，S被稱為混淆層（非線性層），主要起混淆作用，P被稱為擴散層，主要起擴散作用。

在AES算法中，

1、使用S盒做位元組替代操作來達到混淆效果；

2、通過在伽羅瓦域做矩陣運算（MixColumns），對分組中的4個位元組進行擴散；

3、同時結合行位移來交錯MixColumns的子分組，進而實作整個分組的擴散；

4、最後混入“密鑰”，實作算法的保密性。

值得注意的是，

AES128的分組大小是16位元組，可以作為4x4的矩陣；

AES256的分組大小是32位元組，可以作為4x8的矩陣。

MixColumns運算，可以看作時用4x4的矩陣左乘4xN的矩陣。

對于一個8位元組的整數，我們也可以将其看作4x2的矩陣來做MixColumns運算。

是以，我們可以仿照AES的結構和運算，對一個Long類型的數值做加密運算：

public class LongEncoder {
    private static final int ROUND = 8;

    private static final byte[] S_BOX = {
            99, 124, 119, 123, -14, 107, 111, -59
            ......
    };

    private static final byte[] KEY = {
            -14, 40, 52, -119, -126, -47, 74, 73,
            ......
    };

    private static byte mul2(byte a) {
        return (byte) (((a & 0x80) != 0) ? ((a << 1) ^ 0x1b) : (a << 1));
    }

    public static void mix_column(byte[] s, int i) {
        byte t = (byte) (s[i] ^ s[1 + i] ^ s[2 + i] ^ s[3 + i]);
        byte b0 = (byte) (mul2((byte) (s[i] ^ s[1 + i])) ^ s[i] ^ t);
        byte b1 = (byte) (mul2((byte) (s[1 + i] ^ s[2 + i])) ^ s[1 + i] ^ t);
        byte b2 = (byte) (mul2((byte) (s[2 + i] ^ s[3 + i])) ^ s[2 + i] ^ t);
        byte b3 = (byte) (mul2((byte) (s[3 + i] ^ s[i])) ^ s[3 + i] ^ t);

        s[i] = b0;
        s[1 + i] = b1;
        s[2 + i] = b2;
        s[3 + i] = b3;
    }

    private static void shift_rows(byte[] state) {
        byte t1 = state[7];
        byte t0 = state[6];
        state[7] = state[5];
        state[6] = state[4];
        state[5] = state[3];
        state[4] = state[2];
        state[3] = state[1];
        state[2] = state[0];
        state[1] = t1;
        state[0] = t0;
    }

    public static long encode64(long value) {
        byte[] state = long2Bytes(value);
        for (int i = 0; i < ROUND; i++) {
            for (int j = 0; j < 8; j++) {
                int m = ((i << 3) + j);
                // AddRoundKey and SubBytes
                state[j] = S_BOX[(state[j] ^ KEY[m]) & 0xFF];
            }
            shift_rows(state);
            mix_column(state, 0);
            mix_column(state, 4);
        }
        for (int j = 0; j < 8; j++) {
            state[j] ^= KEY[(ROUND << 3) + j];
        }
        return bytes2Long(state);
    }
    ......
}

事實上，輸入輸出的長度（位元組）不一定非要是4的倍數。

比如，對于6個位元組的輸入，可以這麼處理：

public static long encode48(long value) {
        byte[] state = long2Bytes(value);
        for (int i = 0; i < ROUND; i++) {
            for (int j = 0; j < 6; j++) {
                int m = ((i << 3) + j);
                // AddRoundKey and SubBytes
                state[j] = S_BOX[(state[j] ^ KEY[m]) & 0xFF];
            }
            // 對于48bit的輸入而言，就不需要ShiftRows了
            // 因為先後對[0,3], [2,5]進行MixColumns已經可以對整個輸入擴散了
            mix_column(state, 0);
            mix_column(state, 2);
        }
        for (int j = 0; j < 6; j++) {
            state[j] ^= KEY[(ROUND << 3) + j];
        }
        // 輸出的Long，高位的兩個位元組沒有變
        // 是以如果輸入時小于2^48的數值，則輸出也是小于2^48的數組
        return bytes2Long(state);
    }

再将加密後的數值進行進制轉換，即可輸出字元串形式的ID：

private static final byte[] HEX_DIGITS = {
            '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
            'a', 'b', 'c', 'd', 'e', 'f'};

    /**
     * 小于2^48的long數值轉十六進制字元串
     * @param n long類型整數
     * @return 12位元組的字元串（十六進制）
     */
    public static String long48ToHex(long n) {
        if((n >>> 48) > 0){
            throw new IllegalArgumentException(n + " is bigger than 2^48");
        }
        byte[] buf = new byte[12];
        for (int i = 5; i >= 0; i--) {
            int b = (int) n;
            int index = i << 1;
            buf[index] = HEX_DIGITS[(b >> 4) & 0xF];
            buf[index + 1] = HEX_DIGITS[b & 0xF];
            n = n >>> 8;
        }
        return new String(buf);
    }

至此，我們便完成了對整型ID的加密和編碼。

至于整型ID的生成，網上有很多“ID生成方案”，我們這裡就不作展開了。

五、總結

本文從網站URL入手，對資源ID做了簡要的分析，文章用了大量篇幅講AES的算法原理，稍有喧賓奪主的意味。

但就好比做包子，餡比面皮投入多也是正常的。

好吃的餡不單可以用來做包子，也可用于其他用途。

比如前些時候筆者寫的一篇文章：

《漫談唯一裝置ID》

，文中提到，需要根據主鍵ID計算出另一個的ID(作為UDID), 傳回給用戶端。

用本文的方法即可滿足需求。

完整代碼已上傳github,

位址：

https://github.com/No89757/LongEncrypt

參考資料

[1]

分組密碼

[2]

[3]

碼算法詳解——AES

[4]

AES算法描述及C語言實作

[5]

[6]

漫談唯一裝置ID
機器學習/深度學習 算法 安全 資料安全/隐私保護 c語言 ids資源 開源ice id生成規則 程式設計語言深度學習 id生成架構師
上一篇: 手把手用Python網絡爬蟲帶你爬取全國著名高校附近酒店評論
下一篇: 從排序算法到TopK問題

繼續閱讀