如何生成安全的资源ID

2022-09-21 13:18:14

一、前言

对于一些图片，文章，或者用户主页等，需要构造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轮稍有一点区别。
每轮运算涉及字节替代、行移位、列混淆、轮密钥加等四个子运算；
每个子运算都有逆运算，用相反顺序逆运算可解密出原文。

如何生成安全的资源ID

3.2 字节替代（SubBytes）

字节替代需要用到S盒，S盒有两个数组，且命名为：SBOX， INV_SBOX。
S盒有这样的特点:
若y = SBOX[x]，则x = INV_SBOX[y]；
换个写法： x = INV_SBOX[SBOX[x]]。

举个栗子, 一个简单的2阶S盒：
如何生成安全的资源ID

    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个字节。

如何生成安全的资源ID

3.4 列混淆（MixColumns）

列混淆是所有子运算中最复杂的。
和行位移一样，将16字节划分为4行4列；
不同的是，列混淆是分别对每一列的4个字节做运算（和一个4x4的矩阵左乘）。
解密时也是左乘矩阵，解密矩阵是加密矩阵的逆矩阵。

如何生成安全的资源ID

某一列的运算代码如下：

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] 伽罗华域运算及C语言实现
[3] 码算法详解——AES
[4] AES算法描述及C语言实现
[5] 雪崩效应
[6] 漫谈唯一设备ID

上一篇：Fault-tolerance in Flink | 学习笔记


下一篇：英特尔RealSense 3D：让设备像人一样看世界