简单的密码学生成唯一邀请码

密码学 评论

最近项目需要生成用户邀请码，网上找了几个算法都不太满意，就自己写了一个。里面借鉴了一些密码学里的思路，最后的算法效果还不错。想把思路记录下来，可以用在类似对加密强度要求不高的场合下。

需求分析

从业务需求和市面上其它产品邀请码的使用体验上来看，邀请码有以下几个强制性的要求：

  • 不可重复
  • 唯一确定

这两点要求首先就排除了 hash code 的可能，因为 hash code 是可以发生碰撞的。然后在强制性要求的基础之上，我们还有一些进一步的需求：

  • 长度不能太长，6-10 位是合适的区间
  • 不容易被推测出
  • 资源消耗尽可能小

在这些需求的约束下，我们先来看看常见的通用的序列码生成算法。

通用方案

通用方案的解决思路可以分为两种：一种是生成一串不重复随机数，然后将其保存到数据库里。使用邀请码时从数据库里查询就可以得到邀请人；另一种是对身份信息作加密，通常是用户 id，将加密后的密文作为邀请码，使用时可以不查询数据库，直接解密得到。理论上说，第二种方式稍好一点，可以少进行一次数据库查询。但是考虑到安全性，我们还是会把解密后的 id 拿到数据库中查询，防止有人输错或者伪造邀请码产生 NPE。因此在选择算法的时候，这两种思路我都有考虑到。

1、UUID

谈到不重复的随机数，最先想到的自然是 UUID。UUID 是一种软件构建的标准，也是开放软件基金会组织（OSF）在分布式计算环境领域的一部分。按照 OSF 制定的标准计算，它用到了以太网卡地址、纳秒级时间、芯片 ID 码和许多可能的数字，保证对在同一时空中的所有机器都是唯一的。Java 的工具类 java.util.UUID 是 Java 提供的一整套 UUID 生成方案，对于开发者来说可以很方便的调用。然而 UUID 并不适合用在这里，因为 UUID 的位数是固定的 32 位，这个对于我们的邀请码来说显然是太长了（想象一下用户面对面分享邀请码的时候居然需要报一串 32 位的数字+字母）。

网上也有用 UUID 的一部分当随机数的，但 UUID 只能保证完整的 32 位是不会重复的，不能保证其中的某一段不重复，因此这个方案也行不通。

2、系统当前时间

系统当前时间也是一种常见的随机数生成方案。它的做法是先获取到系统当前时间，再用它和某个时间点对比，将这两段时间的间隔以毫秒或者纳秒为单位存到内存中去。最后我们程序获取到的是一串数字。Java 提供了两个系统函数用于实现这个功能：System.currentTimeMillis() 和 System.nanoTime()。然而这两个系统函数在这个业务里都有各自的问题。

System.currentTimeMillis() 返回的是从 1970.1.1 UTC 零点开始到现在的时间，精确到毫秒。它的问题在于不能支持高并发的邀请码生成。在这套方案中，只要我们的系统在某 1 秒内生成的邀请码超过 32 个，那么出现相同邀请码的概率就超过 50%（详见生日攻击 ）。显然，这个规模的并发量是不能接受的。

System.nanoTime() 返回的是从某个固定但随意的时间点开始的时间，精确到纳秒。这个固定但随意的时间，在不同 JVM 中是不一样的。这也就是说不同计算机计算出来的 nanoTime() 是有可能重合的。甚至同一台计算机重启 JVM 后生成的 nanoTime() 也是可能重合的。这违背了我们的第一个要求。

3、RC4 算法

RC4 对于学过密码的同学来说肯定不会陌生。它是大名鼎鼎的 RSA 三人组中的头号人物 Ronald Rivest 在 1987 年设计的一种轻量级对称加密算法。它的特点是按字节流加密，也就是说明文多长，密文就多长。这一特点很好避免了 UUID 只能生成 32 位字符串的尴尬。而且 RC4 是一个轻量级加密算法，运行速度快，占用资源少，很好地满足了我们的第 5 点要求。乍一看 RC4 似乎是种理想的方案，然而实际一跑就出现了问题：

出现了乱码！这是因为字符的取值在 0~255，而我们熟悉的英文和数字只占了其中的 62 位，其它符号是我们不熟悉的，当然也不能作为邀请码。解决方法也很简单，把字符串转成 16 进制即可：

由于把 8 位的字符串转成了 4 位的 16 进制，字符串的长度增加了一倍，但长度尚在可接受范围之内。不太满意的一点是加密后的密文都是连续性的，高位的数字基本不变。这也意味着如果被邀请的同学输错了后几位数字，后台大概率检测不到他的这次操作失误，因为他输入的错误邀请码能在数据库里被找到。而且连续的密文容易被找出规律，安全性较低。因此这种方式也不建议。

4、用户身份标志+随机数

这种方法是我在网上找到的已经被用于实际业务中的方法，它的大致思路是这样：

  • 获取用户身份的唯一标志，比如用户 ID。
  • 将用户 ID 补全，补全的位数取决于你希望得到的邀请码长度，如：106 可以补全为 00106.
  • 随机生成一串大写字母串，长度和补全后的用户 ID 相同，如：SZUDF。
  • 将随机数隔位插入用户 ID，得到邀请码：S0Z0U1D0F6。

这种方式得到的邀请码基本能满足我们的要求：由用户 ID 的唯一性保证了邀请码的唯一性；随机生成的字母串又能保证不容易被找到规律，同时又提高了用户操作的容错率；长度也在可接受范围内。因此第一版的邀请码生成算法我们采用了这种方式。

但是它仍然有改进的空间。①、字母和数字的位置是固定的，有一定的容易被察觉的规律，且对于数字来说，仍然具有连续性；②、用户 ID 直接暴露在密文中，存在风险；③、没有校验位，邀请码的校验依赖于数据库，无法对恶意伪造大量错误邀请码的攻击进行有效防御。

因此我在这种算法上作了改进，克服了以上的缺点。

我的方案

为了让字母和数字的位置不再固定，我将用户 ID 作了 36 进制转换，即把用户 ID 映射为一串字母+数字的组合，高位用 0 补全。

1
2
3
4
5
6
int[] b = new int[CODE_LENGTH];
b[0] = id;
for (int i = 0; i < 5; ++i) {
    b[i + 1] = b[i] / 36;
    b[i] = (b[i]) % 36;
}

同时把随机数生成的范围扩大到字母和数字，这样密文中的每一位都可能是数字和字母，规律性就不易察觉得多。

然后是用户 ID 暴露在密文中的问题。这个问题的解决办法是我们可以加一点盐 。盐的取值最好不要太小，太小缺乏隐蔽性；也不能太大，太大会占用过多用户 ID 的取值空间。具体的取值取决于业务需求。

当然，最后是校验位的问题。这个问题我思考之后决定在随机数上作文章。目前的算法，会生成和补全后用户 ID 长度相等的随机数。这有两点问题：一是邀请码长度稍显过长，6 位用户 ID 就会产生 12 位的邀请码；二是随机数没有提供额外的信息，这对密文来说是一种资源浪费。鉴于此，我改变了随机数的生成方式，让它不再随机生成，而是承担起对密文其它部分的校验功能。同时改变了它的长度，把它固定在 2 位。当然，缩短后的校验码就没有办法隔位插入，我就把它放在了密文尾部。用这一套校验方式，理论上能保证 99.9%的误操作可以被后台检测出来而不需要查询数据库。

生成的邀请码如上，相比第一版，可以看到一些很明显的改进。而且理论上可以容纳 1000 万的用户量，比第一版的 10 万位有了很大提升。

但是这一版的算法仍有问题，细心的同学会发现 6 个验证码的 2~5 位是一样的。这是因为低位的变化不足以影响到高位，导致高位的字符没有发生变化。这样的算法在安全性上是比较薄弱的，攻击人可以利用这一规律大大降低猜测的区间。而且密文和密钥（超参数，本文中就是 salt 和 prime1）之间的关系比较直接，没有进行进一步的处理。现代密码学认为，密码的安全性应该由密钥来保障而不是加密算法，如果密钥和密文之间的联系过于直接，密码的安全性便会削弱。当然，密码学上对这些问题有解决方法，那就是扩散和混淆。

扩散和混淆

扩散 (diffusion) 和混淆 (confusion) 是 C.E.Shannon 提出的设计密码体制的两种基本方法，其目的是为了抵抗对手对密码体制的统计分析。在分组密码的设计中，充分利用扩散和混淆，可以有效地抵抗对手从密文的统计特性推测明文或密钥。扩散和混淆是现代分组密码的设计基础。

所谓扩散就是让明文中的每一位影响密文中的许多位，或者说让密文中的每一位受明文中的许多位的影响。这样可以隐蔽明文的统计特性。当然，理想的情况是让明文中的每一位影响密文中的所有位，或者说让密文中的每一位受明文中所有位的影响。

所谓混淆就是将密文与密钥之间的统计关系变得尽可能复杂，使得对手即使获取了关于密文的一些统计特性，也无法推测密钥。使用复杂的非线性代替变换可以达到比较好的混淆效果，而简单的线性代替变换得到的混淆效果则不理想。可以用”揉面团”来形象地比喻扩散和混淆。当然，这个”揉面团”的过程应该是可逆的。乘积和迭代有助于实现扩散和混淆。选择某些较简单的受密钥控制的密码变换，通过乘积和迭代可以取得比较好的扩散和混淆的效果。

改进后的算法

我用扩散和混淆的方式对算法进行了改进。

扩散的方式很简单，只需要将个位和其它每一位作和后取余，即可把变化传导到每一位。为了隐蔽，我还把变化进行了放大：

1
id = id * PRIME1;

PRIME1 可以为任意随机数，最好和 36 以及 10^n（n 为用户 id 位数）互质。这是因为根据循环群 的性质：若 m 和 p 互质，则 ( id * m ) % p 的结果遍历[0, p) 的所有整数。保证了放大后结果的分布和原数据的分布同样均匀。为了使结果看起来更随机，我还给每一位分配了不同系数：

1
2
3
4
5
6
7
8
9
10
id = id * PRIME1;
id = id + SALT;
int[] b = new int[CODE_LENGTH];
b[0] = id;
for (int i = 0; i < 5; ++i) {
    b[i + 1] = b[i] / ARY;
    b[i] = (b[i] + b[0] * i) % ARY;
}
b[5] = (b[0] + b[1] + b[2]) * PRIME1 % ARY;
b[6] = (b[3] + b[4] + b[5]) * PRIME1 % ARY;

ARY 表示进制，这里是 36，也可以设置成其它的数，比如 62（字母区分大小写）。
代码的第 7、9、10 行中我分别对每一位设置了不同的系数，使得每一次的增量显得更不固定。

然后是混淆。混淆我用了P-box 的方式，其实就是将数字洗牌。比如把 1234567 洗成 5237641。这样处理之后可以隐藏密钥和密文之间的关系。洗牌的方式也很简单，选择一个和 CODE_LENGTH（本文中为 7）互质的数 PRIME2，和数组角标相乘取余即可（原理同 PRIME1）。最终的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static String inviCodeGenerator(int id) {
    id = id * PRIME1;
    id = id + SALT;
    int[] b = new int[CODE_LENGTH];
    b[0] = id;
    for (int i = 0; i < 5; ++i) {
        b[i + 1] = b[i] / ARY;
        b[i] = (b[i] + b[0] * i) % ARY;
    }
    b[5] = (b[0] + b[1] + b[2]) * PRIME1 % ARY;
    b[6] = (b[3] + b[4] + b[5]) * PRIME1 % ARY;
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < CODE_LENGTH; ++i) {
        sb.append(HEX_36_Array.charAt(b[(i * PRIME2) % CODE_LENGTH]));
    }
    return sb.toString();
}

测试结果如下：

完美符合我们的需求^_^

邀请码和用户 ID 的转换也很简单，因为加密的过程都是可逆的，所以只需将加密过程作逆变换即可。这里要提一点就是我们是设置了校验位的，所以可以在解密的过程中对邀请码进行校验，如果是用户的误输入或者有人企图构造邀请码恶意攻击，我们在业务层就可以检测出来，不需要拿到数据层去做校验。具体的解密代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public static int inviDecoding(String inviCode) {
    if (inviCode.length() != CODE_LENGTH) {
        return -1;
    }
    int res = 0;
    int a[] = new int[CODE_LENGTH];
    int b[] = new int[CODE_LENGTH];
    char[] c = new char[CODE_LENGTH];
    for (int i = 0; i < CODE_LENGTH; ++i) {
        a[(i * PRIME2) % CODE_LENGTH] = i;
    }
    for (int i = 0; i < CODE_LENGTH; ++i) {
        c[i] = inviCode.charAt(a[i]);
    }
    for (int i = 0; i < CODE_LENGTH; ++i) {
        a[i] = HEX_36_Array.indexOf(c[i]);
    }
    b[5] = (a[0] + a[1] + a[2]) * PRIME1 % ARY;
    b[6] = (a[3] + a[4] + a[5]) * PRIME1 % ARY;
    if (a[5] != b[5] || a[6] != b[6]) {
        return -1;
    }
    for (int i = 4; i >= 0; --i) {
        b[i] = (a[i] - a[0] * i + ARY * i) % ARY;
    }
    for (int i = 4; i > 0; --i) {
        res += b[i];
        res *= ARY;
    }
    res = ((res + b[0]) - SALT) / PRIME1;
    return res;
}

代码 18~22 行就是在作校验。

总结

不同的业务有不同的需求，市面上通用的方案可能只能满足大部分共性的需求，但对于某些特定的需求，市面上找不到完善的解决方案，这时候就需要我们独立解决问题的能力。本科的时候觉得密码学没用，没想到在这用上了。越来越觉得世上没有无用的知识，多积累一些总是好的^_^