四亿个兑换码的生成/验证算法？
12 个回答
原理基本上是加密解密过程，将一个32位的二进制int来表示4亿兑换码，然后扩充到合适长度用加密算法加密，Base24编码结果。总体上和序列号的方案差不多。再配合网络验证应该可以满足需求中的，高效、防爆刷、防重复兑换。
---------
在说明原理之前先说明下Base24编码。
Base24编码主要应用在序列号生成上，其实基本的算法思想和Base64都是一样的，只是编码的模式有点变化。
Base64所对应的编码表是
ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/=
共计64位。
那针对这个问题我们选定的Base24所对应的编码表是
ABCDEFGHJKLMNPQRSTUVWXYZ
共计24位。去除了影响识别的I和O
Base24的转换方式主要是通过除法的方式来进行
举例说明：假设数值0那么对应A，1对应B 那么24对应BA，25对应的是BB
那么1位字母所能表示的数值上限为24^1-1=23
2位字母能表示的数值上限即为24^2-1=575
13位数值表示的上限即为24^13-1 ，约等于log2(24^13)=59.6bits，也就是说，至少完美表示59位二进制编码内容
而我们需要编码的激活码上限为4亿 约等于log2(4亿)=28.6bits 接近29位，使用int存储占32bits,远小于59bits，因此可以被13位Base24编码。
在此基础上我们规划下bit的定义
[0{5}-0{48}-{6}]
|6 Bits标记位|48 Bits数据位|5 Bits校验位|
标记位我们可以写入用于表示兑换物、失效时间等一些离线简单验证的信息
数据位则是这个激活码的基础部分
校验位就是前54Bits校验，可以是简单的hash然后再对32(2^5)求余的余数
那么接下来的问题就是，有什么方便有效的加密解密方式能将我们的32bit存储的激活码编号转换成位48位的数据呢？
——————————
先把过程补完，原理以后再说
加密算法这里选择的是RC4，当然也可以选择其他加密算法。RC4是一个是应用最广泛的流加密算法，应用在安全套接字层（SSL）（用来保护网络上传输的数据）和WEP（无线网络数据保护）上，最大亮点就在于是算法的简单性和运行速度，在这里用于生成密文速度会非常快。
通过将激活码数字原始的32bits编码+6bits标记位内容+填充0扩充到48bits，随机生成一个密钥，再通过RC4加密，即可得到48bits的密文。因此之前构造的数据结构中的数据位的内容填入该密文，计算出校验位后即生成了59bits的兑换码，再通过Base24编码就可以转换为13位长度的兑换码。
如果需要解密，客户端先验证校验位是否正确，正确请求服务器，服务器取出数据位，解密得出激活码编号和兑换物内容，校验查询使用激活码目录查看数据库是否已经写入，如果已经写入，认为该激活码已经被使用，如果没有使用将该激活码编号存入数据库，因为激活码编号是一个纯32位无重复的整数，因此可以以激活码编号为主键建立数据库，查询效率将会非常高效。
这是一个很有趣的问题，牵涉到不少的知识点，试着答一下
要考虑的点题目中已经给出来了，包括生成/验证，高效，防爆刷，防重兑这几个大的点
预备知识：4亿的验证码需要29个bit来表示（向上舍入）、13位的字母验证码可以携带59bits的信息（向下舍去）以及Base24是怎么工作的，这些都可以在
@宣明庆的答案里找到详细解释。
先分析一下几种个人觉得可能不是很好的方式：
最粗暴的方式是从`/dev/urandom`里直接读取，然后做Base24转码，导入数据库中。在兑换时直接查询数据库，修改数据库记录防止重新兑换。
这个方法非常简单粗暴，由于是纯随机数，每个兑换码之间没有关联，能有效地防止爆刷。但这个方法对数据库要求比较高，导入和验证，防重兑的数据库开销都很大。
对于使用公私钥体系的兑换码有两个担忧。一个是有些算法开销太大了，比如RSA这种基于大数的算法。另外就是不清楚密文的分布是否足够随机（并没有研究过，请熟悉的同学拍砖）。同时，这个机制对数据库的开销和随机数法一样巨大。
@宣明庆同学的方法在实际操作中会遇到一些问题。比如RC4的密钥，如果400M个兑换码就都采用同一个密钥的话，那加密出的兑换码会有非常强的关联性，明文中相同的bit在密文中也是相同的，观察出规律后对密文异或特定值就可以直接篡改密文进行攻击。如果采用一号一密的机制话，验证兑换码时无法得知兑换码对应的密码，解密过程就无法进行下去，如果把一号一密对应的密码存数据库的话，还不如直接用随机数法呢。
下面是我的方法：
我选用的是chacha20作为随机数生成器，这是一个被Google选中的简单高效的流密码算法，内部是基于block工作的，一个block长度为512bits，可以指定block编号同步加/解密数据。其输入包含一个密钥K，一个新鲜值N和一个64位的block编号ic，输出一段512bits的伪随机数。熟悉的同学也许已经看出来了，CTR模式下的AES也可以胜任这个工作。
兑换码的明文结构是这样的：前29bits是0-400M的兑换码编号，后30bits是兑换码的payload。Payload中包括了一个特定的数据结构和HMAC校验码，数据结构可以用来指示兑换码可以兑换的物品，有效期等业务数据，HMAC校验码用来保证数据的完整性。数据结构的长度越短，HMAC的位数也就越长，安全性也越高。
兑换码的密文结构是这样的：前29bits还是0-400M的兑换码编号，以明文形式展示，后30bits是被加密的payload。
兑换码的生成流程：
1. 生成256bits的密钥K和64bits的新鲜值N，这两个值在400M个兑换码的生成周期中都是不变的。补充一句，密钥可以一直不变，但下次生成新一批验证码的时候一定要记得将新鲜值加1
2. 将兑换券编号I（0-400M）作为block编号ic，与K还有N一起使用chacha20算法计算出512bits的伪随机数R
3. 将512bits的伪随机数R平分截断为R1和R2，前256bitsR1作为HMAC的key，(I+payload+R2)作为HMAC的内容，得到结果H
4. 将payload和H拼起来，在30个bit位置截断，与R2的前30bits做异或操作，获得payload的密文C
5. 将I和C拼接起来，组成59bits的兑换券编号，使用base24算法转译为字母组合，这就是最终生成的兑换码
兑换码的验证流程：
1. 收到提交的兑换码后，转译为bit序列I，取其前29bits，与密钥K和新鲜值N一起使用chacha20算法计算出512bits的伪随机数R
2. 将512bits的伪随机数R平分截断为R1和R2，把R2的前30bits与I的后30bits做异或操作，获得payload明文和HMAC结果H
3. 以R1为HMAC的key，payload明文为HMAC的内容，计算HMAC结果H1，判断H和H1是否相等，这是密文是否合法的标识
4. 根据解出的payload兑换相应的东西
通过生成/验证流程可以看出，这个方法将业务数据直接集成在了兑换码中，计算简单高效，并且全程无需访问数据库。
对于暴力破解者，即使知道了兑换码的组成规则，但由于兑换码的后30bits是伪随机的，一个兑换码也需要2^30的穷举才能破解，兑换验证码可是网络请求，这么大的访问量完全可以当作DDOS被Drop掉，所以这个方法是防爆刷的。（其实从密码学上看，这个方法也许是存在弱点的，可能存在小于穷举数目的利用，但我没想出来，请高手指导）
至于防重兑就更加简单了，分配一段400M的内存，哪个券兑换了就把券ID对应的那个bit设为1就行了，简单高效，同样也不需要数据库支持。
以上只是一个基础的玩法，还可以加上本地校验，可以打乱字符顺序，反正可以玩出各种花出来，权当抛砖引玉，欢迎一起讨论