生成固定长度不重复的随机字符串

问题

问题来自V2EX：如何生成固定长度唯一随机字符串？

不过需求后来有修改过，原始的需求略有不同，所以我的回答与现在的问题不太对得上，这里以原需求为基础重新提出这个问题，并且加上一些更有代表性的条件。

条件有以下几个：

• 串长固定为8位，大小写字母加数字组合
• 串内容随机，不可被猜测，不可重复
• 目标数据量不超过一千万
• 不需要数据库

分析

其实重点在不需要数据库，否则直接用一个随机数生成器生成一千万个随机串放到数据库里直接用就好了。

如果不依赖数据库的话，用任何随机数生成器，都不能保证绝对不重复——虽然概率非常低，比如8位大小写字母数字组合的空间超过14位十进制数，一千万不超过7位十进制数，即低于千万分之一——但理论上仍然可能发生。

要保持唯一就需要自增ID，但是如果只是简单地用自增ID又会导致可能被猜测，虽然可以把组合逻辑搞得复杂一点，但数据量大了还是有一定的可能性被猜出——不要对自己想的简单逻辑有太高的自信是一个很重要的安全原则。

实现

基本如我在评论里说的那方法：

• 8位大小写字母加数字转成二进制大概是47位多，一千万转成二进制不到27位
• 所以可以用一千万以内的自增ID，加上20位二进制的随机数，组合成一个47位的二进制数
• 因为上面的组合是可猜测的，所以需要进行一次加密，用一个自定义密码对这个数进行RC4加密
• 最后用BASE62转换为大小写字母加数字的字符串

恢复ID的方法：

• 把字符串转成47位二进制数
• 用RC4解密
• 去掉随机数部分，转为整数即为原始ID

关键点：

• 随机数与ID的组合方式，这个与加密算法是相关的
• 加密算法的选择，必须适合这样的需求，即消除可猜测性

综合这两点，加密算法的选择范围就不大了，大部分常用的分组加密算法（一般都是128位分组，老一些的TEA也是64位，即使DES也需要56位）都肯定是没办法用的，只能用弱一些的短分组加密算法，比如以字节为单位进行加密的RC4。

但是因为47位不是刚好整数字节，所以要分成40位和7位两组，其中40位由27位ID与13位随机数分散组合后进行RC4加密，再加7位随机数组成47位二进制数。

代码

初始化参数包括：

• key: RC4加密密钥
• chars: 目标字符串可用字符集合，不可重复
• length: 目标字符串长度，目标字符串转为二进制不超过64位无符号整数，即： log(pow(len(chars), length)) / log(2) <= 64
• bits_id: ID的二进制位数，不能超过目标串转为二进制位数除以8取整后乘以7的值，即： bits_id < int(log(pow(len(chars), length)) / log(2) / 8) * 7 ，之所以要如此，是为了保证加密的每个字节至少有一位随机数，确保RC4加密后仍然不可猜测
• secure_level: 取值0-4，为每个字节中随机数的位数，越多越安全，0则不含随机数，超过4位则意义不大，仅作初始化时检查之用，如果目标串长度设置不符合这个要求会报异常

主要功能函数是两个：

• encrypt: ID转目标串
• decrypt: 字符串转ID

完整代码在GayHub。

之所以有兴趣研究这个东西，是因为这种需求其实还挺有用的。比如与微信或支付宝之类的支付平台对接时都需要一个唯一的订单号，但是通常客户又不希望把自己的内部订单ID曝露在外，所以都需要转换一下，当然这类应用都有数据库，只要生成一个随机串再查一下数据库有没有重复即可。还有像短链接应用也是可以用的（用七位字符就可以支持到41位二进制ID，secure_level=0）。

然而毕竟还是要多查一次数据库，这种事情让CPU来干可能会更省资源一些。

推送到[go4pro.org]