今天自己写项目玩，想要实现一个类似邀请码的机制，没想到小小邀请码还真没那么简单 ## 需求分析首先是硬性需求： - 不可重复 - 单射看到这两点需求，我第一反应就是 Hash，但是Hash需要处理冲突，并不是一个很好的解决方案。另外出于美学之类的考虑，我们还有一些别的需求，毕竟谁也不想面对面分享邀请码的时候拿出来一串 ``18ce3ca04a725cc6b57d5ec0ae0ccd66`` 这样的~~乱码~~吧非硬性需求： - 定长 - 不易被推测出规律 - 效率高 - 支持并发 - 可溯源仔细思考了一下 Hash 的可行性后我决定放弃这种方案... ## 方案分析群里的菊苣给出了洗牌算法的方案，这是一个预生成的方案这里就预生成方案统一分析 ### 预生成讲真，不考虑别的因素，预生成方案确实不错，洗牌算法也非常的棒这种方案的思想是根据随机生成算法，预先生成一批邀请码，然后将这些邀请码缓存，当用户请求时将其分配给用户，当邀请码分配完时，再生成一批，如此循环。 #### 弊端 - 每次重新生成时都要检查是否重复 ~~而且多数情况下都为否~~ - 邀请码本身需要持久化存储 - 用户和邀请码的关系需要记录对于唯一性我啪的一下就想到了 UUID 和 MD5，~~很快啊~~ MD5作为一种 Hash 在一开始就被我放弃了，接下来我们看一下 UUID ## UUID 引用一下Wikipedia的说法 > 通用唯一识别码（英语：Universally Unique Identifier，缩写：UUID）是用于计算机体系中以识别信息数目的一个128位标识符，根据标准方法生成，不依赖中央机构的注册和分配，UUID具有唯一性，这与其他大多数编号方案不同。重复UUID码概率接近零，可以忽略不计。这下唯一性是真的强，但是分享一串128位标识符的画面确实也很美... 没啥好想法的我上网搜了一下，又得到了两种方案，一种类似于Base64，这种没啥好说的，接下来主要说一下另一种方案 ### 密码学方案这种方案本质上是一个实现了由用户ID空间到邀请码空间的双射，通过用户ID确定了邀请码的唯一性，同时又可通过反函数来对邀请码溯源，既不需要保存邀请码，又不需要保存关系，针不戳我们先来写个简单函数实现双射 ```go func test(id uint) { const Chars = "0123456789ABCDEF" const CodeLength = 6 const Base = 16 const Salt = 233 pid := id + Salt // 为了避免用户 ID的直接泄漏，我们可以先加点盐 var b [CodeLength] uint b[0] = pid for i := 0; i < CodeLength-1; i++ { b[i + 1] = b[i] / Base b[i] = b[i]% Base } fmt.Printf("ID: %-2d ---> %c %c %c %c %c %c\n",id, Chars[b[5]],Chars[b[4]],Chars[b[3]],Chars[b[2]],Chars[b[1]],Chars[b[0]]) } ``` 这个函数本质上和进制转换函数没什么区别，我们跑一下看看效果 ``` ➜ test go run test.go ID: 0 ---> 0 0 0 0 E 9 ID: 1 ---> 0 0 0 0 E A ID: 2 ---> 0 0 0 0 E B ID: 3 ---> 0 0 0 0 E C ID: 4 ---> 0 0 0 0 E D ID: 75 ---> 0 0 0 1 3 4 ID: 76 ---> 0 0 0 1 3 5 ID: 77 ---> 0 0 0 1 3 6 ID: 78 ---> 0 0 0 1 3 7 ID: 79 ---> 0 0 0 1 3 8 ``` 啊这...这完全在预料之中，~~换下Chars里字母的顺序也能当个凯撒密码用用~~ 好吧不就是看起来太规律了么，我们来把这个结果用密码学方法扩散和混淆一下 #### 扩散和混淆在密码学当中，混淆（confusion）与扩散（diffusion）是设计密码学算法的两种主要方法。这样的定义最早出现在克劳德·香农1945年的论文《密码学的数学理论》当中。在克劳德·香农的定义之中，混淆主要是用来使密文和对称式加密方法中密钥的关系变得尽可能的复杂；而扩散则主要是用来使用明文和密文关的关系变得尽可能的复杂，明文中任何一点小更动都会使得密文有很大的差异。混乱用于掩盖明文与密文之间的关系。这可以挫败通过研究密文以获取冗余度和统计模式的企图。做到这一点最容易的方法是“代替”。扩散通过将明文冗余度分散到密文中使之分散开来。即将单个明文或密钥位的影响尽可能扩大到更多的密文中去。产生扩散最简单的方法是换位（置换）。改进后的算法如下 ```go func test(id uint) { const Chars = "0123456789ABCDEF" const CodeLength = 6 const Base = 16 const Salt = 233 const Prime = 7 pid := id * Prime + Salt // 放大 var b [CodeLength] uint b[0] = pid for i := 0; i < CodeLength-1; i++ { b[i + 1] = b[i] / Base b[i] = (b[i] + uint(i) * b[0]) % Base } fmt.Printf("ID: %-2d ---> %c %c %c %c %c %c\n",id, Chars[b[5]],Chars[b[4]],Chars[b[3]],Chars[b[2]],Chars[b[1]],Chars[b[0]]) } ``` 这里我们给用户ID放大的时候乘了个和 Base 互质的数 Prime，这是基于循环群的性质：若 m 和 p 互质，则 ( id * m ) % p 的结果遍历[0, p) 的所有整数。这保证了放大后结果的分布和原数据的分布同样均匀。让我们来跑一下试试： ``` ➜ test go run test.go ID: 0 ---> 0 4 B 2 7 9 ID: 1 ---> 0 0 0 0 F 0 ID: 2 ---> 0 C 5 E 6 7 ID: 3 ---> 0 8 A C D E ID: 4 ---> 0 4 F B 5 5 ID: 75 ---> 0 8 2 E 5 6 ID: 76 ---> 0 4 7 C C D ID: 77 ---> 0 0 C B 4 4 ID: 78 ---> 0 C 1 9 B B ID: 79 ---> 0 8 6 7 3 2 ``` 啊这...怎么开头全是0啊...算了，正好拿它做校验位，顺便再给结果洗个牌最终代码如下 ```go func test(id uint) { const Chars = "0123456789ABCDEF" const CodeLength = 6 const Base = 16 const Salt = 233 const Prime = 7 const Prime2 = 5 pid := id * Prime + Salt // 放大 var b [CodeLength] uint b[0] = pid for i := 0; i < CodeLength-1; i++ { b[i + 1] = b[i] / Base b[i] = (b[i] + uint(i) * b[0]) % Base } // 校验位 for i := 0; i < CodeLength-1; i++ { b[CodeLength-1] += b[i] } b[CodeLength-1] = b[CodeLength-1] * Prime % CodeLength fmt.Printf("ID: %-2d ---> ",id) for i := 5; i >= 0; i-- { fmt.Printf(" %c",Chars[b[(i*Prime2) % CodeLength]]) // 洗牌 } fmt.Printf("\n") } ``` 这里用了一个和 CodeLength 互质的数 Prime2 对生成结果进行了洗牌，原因和之前的 Prime 一样跑一下看看效果 ``` ➜ test go run test.go ID: 0 ---> 7 2 B 4 3 9 ID: 1 ---> F 0 0 0 3 0 ID: 2 ---> 6 E 5 C 2 7 ID: 3 ---> D C A 8 3 E ID: 4 ---> 5 B F 4 4 5 ID: 75 ---> 5 E 2 8 5 6 ID: 76 ---> C C 7 4 0 D ID: 77 ---> 4 B C 0 1 4 ID: 78 ---> B 9 1 C 2 B ID: 79 ---> 3 7 6 8 2 2 ``` ohhhhhhhhh 效果相当不错！ #### 解码具体解码流程就是上面的最终函数倒过来写，可能反函数不太好理解，在纸上推一下就好了 ```go func test2(code string) int{ if len(code) != CodeLength { return -1 } var b [CodeLength] uint // 反洗牌 for i := 0; i < CodeLength; i++ { b[(i*Prime2) % CodeLength] = uint(i) } // 转换回 Chars 下标 for i := 0; i < CodeLength; i++ { j := strings.Index(Chars, string(code[b[i]])) if j == -1 { return -1 // 非法字符检查 } b[i] = uint(j) } // 校验 var expect uint for i := 0; i < CodeLength-1; i++ { expect += b[i] } expect = expect * Prime % CodeLength if b[5] != expect{ return -1 } // 反函数 for i := CodeLength-2; i >=0; i-- { b[i] = (b[i] - uint(i) * (b[0] - Base)) % Base } var res uint = 0 for i := CodeLength-2; i >0; i-- { res += b[i] res *= Base } // 反放大 res = ((res + b[0]) - Salt) / Prime fmt.Printf("%d\n",res) return int(res) } ``` 需要注意的是我们之前是从b[5]...b[0]反着print的所以解码的时候记得倒一下 ```go test(76) // CC740D test2("D047CC") // 因为我们之前是反着print的 ``` 最终输出如下 ``` ➜ test go run test.go ID: 76 ---> C C 7 4 0 D 76 ``` 稍微分析一下，6位16进制邀请码，1位校验，可用范围为0x00000到0xFFFFF，减去扩大和加盐带来的损耗，大概能生成14万个邀请码，对于我来说是够用了，如果你觉得少的话可以 - 扩大Base，比如用32进制或者64进制~~（其实我本人用的10进制，只有数字多好看啊小声bb）~~ - 增加邀请码位数，8位不也挺好的么？ ## 最终代码思路验证完毕，让我们把函数的输出补上，并把第一个函数的输出给倒回来，顺便润润色 ```go package main import ( "fmt" "strings" ) const Chars = "0123456789ABCDEF" const CodeLength = 6 const Salt = 233 const Prime = 7 const Prime2 = 5 const Base = uint(len(Chars)) func main() { str := genCode(76) decode(str) } func genCode(id uint) string{ var b [CodeLength] uint var res string pid := id * Prime + Salt //扩大 b[0] = pid for i := 0; i < CodeLength-1; i++ { b[i + 1] = b[i] / Base b[i] = (b[i] + uint(i) * b[0]) % Base } // 校验位 for i := 0; i < CodeLength-1; i++ { b[CodeLength-1] += b[i] } b[CodeLength-1] = b[CodeLength-1] * Prime % CodeLength for i := 0; i < CodeLength; i++ { res += string(Chars[b[(i*Prime2)%CodeLength]]) // 洗牌 } fmt.Println(res) return res } func decode(code string) int{ if len(code) != CodeLength { return -1 } var b [CodeLength] uint // 反洗牌 for i := 0; i < CodeLength; i++ { b[(i*Prime2) % CodeLength] = uint(i) } // 转换回 Chars 下标 for i := 0; i < CodeLength; i++ { j := strings.Index(Chars, string(code[b[i]])) if j == -1 { return -1 // 非法字符检查 } b[i] = uint(j) } // 校验 var expect uint for i := 0; i < CodeLength-1; i++ { expect += b[i] } expect = expect * Prime % CodeLength if b[5] != expect{ return -1 } // 反函数 for i := CodeLength-2; i >=0; i-- { b[i] = (b[i] - uint(i) * (b[0] - Base)) % Base } var res uint = 0 for i := CodeLength-2; i >0; i-- { res += b[i] res *= Base } // 反放大 res = ((res + b[0]) - Salt) / Prime fmt.Printf("%d\n",res) return int(res) } ``` ## Reference - https://my.oschina.net/bravozu/blog/1827254 ~~这老哥代码有问题（小声bb~~ - https://zh.wikipedia.org/wiki/P盒 - https://zh.wikipedia.org/wiki/循環群 - https://zh.wikipedia.org/wiki/通用唯一识别码 - https://www.knowpia.cn/pages/混淆与扩散

浅谈音乐生成算法