一、前言
对于一些图片，文章，或者用户主页等，需要构造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] 伽罗华域运算及C语言实现
[3] 码算法详解——AES
[4] AES算法描述及C语言实现
[5] 雪崩效应
[6] 漫谈唯一设备ID
