四億個兌換碼的生成/驗證演算法？

01-21

鵝廠面試題，當時有點懵，沒有什麼思路……
大致是，需要生成四億個兌換碼，兌換碼由13個字元組成，字元選擇為24個大寫字母(I和O易跟數字混淆所以除外)。要求生成/驗證演算法，高效、防爆刷、防重複兌換。
有沒有什麼好的思路，或是了解實際生產環境中的做法？謝謝！

原理基本上是加密解密過程，將一個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位無重複的整數，因此可以以激活碼編號為主鍵建立資料庫，查詢效率將會非常高效。

剛才有童鞋提醒我說是兌換碼，那麼也就是說可能是數學題，防止被別人暴力計算出來兌換？那麼這樣的話，我想我下面我談論的應該是錯誤的，因為我以為兌換碼是如同驗證碼的（尤其是他說I和1，O和0容易混淆後），不過我還是決定不刪除，因為我想可以當作驗證碼的生成原理看一看吧.

-------------------------------------------------------------------------------

謝邀，這個問題太開放，我沒有實際生產環境中做過驗證碼（你知道我是搞編譯器的，笑...），如果要我來回答這個問題，我想我會這樣思考。

其實驗證碼的基本原理大致是這樣的：

1. 客戶端看見一些有干擾背景的文本圖片，而這些驗證碼圖片是服務端利用隨機文本文字產生的圖片

2. 客戶識別文本，輸入正確的文本然後提交

3. 服務端檢測客戶輸入的文本，並與剛才生成的文本進行對比，看是否一致。如果一致，則繼續下一步驟，如果錯誤則提示錯誤信息並且產生一個新的驗證碼

好了，我們再來看這個問題，其實生成4億的驗證碼不難，因為你有24個字母，然後一個驗證碼由13位構成，那麼簡單的排列組合知識算一下就知道是遠遠超過了的，甚至還可以進行一些特殊處理，如不能全為同一個字母等等，這些你都可以理解為防刷的一些改善措施，雖然這是很小的檢測而已。所以，產生隨機文本文字這一步驟不是很難，那麼我們接下來看如何做到更好的驗證碼。

我們現在服務端已經生成了一些隨機的文本文字，如「WZQTYUPJKFCVD"（我隨便亂敲的）。這個時候，我們就可以繪製出一個透明的圖片，然後把這個文字置於圖片上，寬度為w，高度為h，而這個繪製生成可以隨便你使用什麼辦法，我剛才搜索了一下，發現世界最好的語言PHP內置了一個imagettftext()函數，而且還是TrueType字體來寫的，所以第一步就完成了。

然後由於我們後面要與客戶傳進來的內容進行對比，我們這裡給產生的驗證碼進行hash，然後算出一個hash值方便我們後面比較。

接下來是重點，也是我認為這個面試題開放的原因，也就是如何讓驗證碼能夠被人識別，卻又可以讓機器難以識別，從而達到被防刷的目的。一般來說，要識別圖片的文字，就是利用OCR技術，而一個辦法就是利用OCR的弱點，產生低質量的圖片，並且加一些干擾的背景，如隨便亂畫一些線條。而這也是現在一些驗證碼的辦法，所以我們可以看到一些驗證碼除了文字和白色背景，還有一些雜七雜八的線條。

那麼，除了這些還有沒有其它辦法呢？我們其實回想看到的驗證碼，會發現一些字母是傾斜的，歪七歪八的。沒錯，這也是一些加大OCR識別難度的辦法，所以我們也可以用，這樣的話，我們基本上就是現有的驗證碼的方式，有歪七歪八的文字，有背景，有干擾，大體是可以用了。然後，我們繼續升華，繼續改進，也就是把一個字母拆分為N個部分，然後對這N個部分進行扭曲，並且讓這N個部分之間形成部分空白斷層，即讓其不連續了，這也會加大識別的難度，如"W"，若扭曲得當，你第一眼是識別不出W的，而可能是兩個V，但是仔細看卻又的確是W，這就是我們的目的了，不能輕易被識別。然後經過這樣的處理，會形成一個newcaptcha.jpg，然後這才是我們想要客戶看到的最後驗證碼，而我們的驗證碼其實還是服務端生成的那些文本文字，只是經過了我們這些措施轉換了一下而已，但是這些轉換其實才是重點。

隨後就比較簡單了，客戶輸入了文字來，然後我們計算這些文字的hash，是否與之前保存的hash一樣，如果一樣就正確，然後清除圖片，並且標記這個兌換碼已被兌換。

所以整個題的難點我覺得只在如何讓驗證碼更加難識別，而這個很開放，不過這也只是我的理解。如果你能在生成隨機文本文字方面有非常高效的演算法，我認為也是有非常非常大的加分的。

拋個磚。

驗證碼的每個字母都純隨機生成的話，要靠盲猜命中一個驗證碼的概率是4*10^8 ／ 24^13 = 4.56*10^-10 這個概率可以忽略不計了的感覺…所以生成演算法就是純隨機了。

防重複兌換需要保證數據一致，直接使用資料庫就可以了。把驗證碼的值當作唯一索引，再加個狀態域。生成演算法只需要insert，驗證演算法只需要update單行。如果擔心單表4億條記錄太多，可以用最後一個字母做水平切分。純隨機生成的話，單表數據在最多2kw條記錄。所以防重複兌換用水平切分的資料庫保證。

防爆刷的話，可以根據用戶的其他特徵做判斷，比如帳號、ip啥的。並制定一些規則，比如簡單粗暴的單帳號單日錯誤次數不超過三次，超過之後此帳號當天不能提交兌換請求。按照前面算的，這個概率其實比支付的時候猜中六位數字驗證碼的概率都低。實現上，把這個帳號當日的錯誤次數放入緩存就可以了。

綜上，純隨機生成兌換碼 + 水平切分的資料庫 + 緩存帳號當日錯誤次數。都是簡單粗暴的實現方式，但是應該足夠有效了。

這是一個很有趣的問題，牽涉到不少的知識點，試著答一下

要考慮的點題目中已經給出來了，包括生成/驗證，高效，防爆刷，防重兌這幾個大的點

預備知識：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就行了，簡單高效，同樣也不需要資料庫支持。

以上只是一個基礎的玩法，還可以加上本地校驗，可以打亂字元順序，反正可以玩出各種花出來，權當拋磚引玉，歡迎一起討論

線上剛探索實現了一個，資料庫寫4億量太大，所以當時改進的需求就是解放資料庫，實際中經常需要生成不同批次的兌換碼，寫資料庫的方案往往遊戲例行維護兩小時還沒寫完。當時的思路是使用對稱密鑰的加密解密，用了rsa，比如要生成2000萬個，先對1到2000萬的數字加密，加密後的字元串為128位的數，對兌換碼長度有要求，就每幾位做一個映射，我們的是每5位映射，相當於2進位轉32進位，數字加字母-o01l剛好32進位，128/5長度還是大於要求就在映射一次，解密時，反映射回去，然後rsa解密就可以。當然，由於兩次映射會有重複，對解密後的數字在加密看一次是不是和兌換碼一樣即可。線上測試，生成1000萬要半小時左右，但生成後可以直接給渠道，玩家拿到就可以用，不用擔心玩家拿到結果伺服器資料庫還沒寫上這個兌換碼。

用哈希表配合定位然後數據保存在文件系統中吧，資料庫可能不太合適?四億個用無符號整形可以直接索引了，你就在兌換碼前面加四個位元組拿來定位，把第一個位元組拿來定位一級文件夾，第二個位元組定位二級文件夾。。。最後提取出來兌換碼。。。沒有實現過，全靠猜。。。

做過一個類似的，不過是生成12位數字

定一個時間點A，往後累加時間段T，計算毫秒差D(n)，取D(n)和D(n+1)之間的一個時間點作為兌換碼，T越大可生成的兌換碼越少，越小越容易生成連續的兌換碼

這樣保證了兌換碼不重複，可以很輕易生成幾億的兌換碼

生成的兌換碼存資料庫，加個隨機數一起放進去，取數據時按隨機數排序取值，也可以在存的時候做些處理，目的是取多條數據時不讓兌換碼串號

現在換成字母，兌換碼的數量更可觀，防爆能力更強了

肯定要有校驗位，一般有一兩位的校驗位，這樣可以通過校驗位判斷13位數字是否合法。生成規則再和時間相關聯，這樣防止重複生成！

24^13 差不多是2^59.6，找個非對稱加密演算法, 把V1(59bit), K1(私鑰), E(V1, K1) -&> V2 (59bit)，把V2編碼成長度13的24個字母。

驗證過程，D(V2, K2) -&> V3， V1, V3隻有0-400M是有效的，在服務端就用0-400M做切分，K1是私鑰，K2是公鑰。

兌換碼生成可以在受控環境中，用私鑰。校驗的話，用公鑰，控制可以相對寬鬆。

防止重複還是得用資料庫。但是，兌換碼的有效的範圍（解碼後）是非常緊湊的，如果要做切分，也就是把一個整數範圍做切分。

只要把生成兌換碼的個數與兌換碼字母可編碼總個數的比率控制到非常小，撞碼的概率可以忽略不計。

用資料庫是不是太慢了。

可以設計一個 24^13 --&> 24^13 的單射可逆函數f，f(n) 的24進位的每一位拿出來就是兌換碼了， n 取值範圍 0至(4億-1)。

逆函數g, 驗證的時候，只要 g(f(n)) =n 就是合法的了。

只要別人不知道f的公式就不能刷了。不過f本身需要盡量均勻一點，且可逆，數學學的不好的目測不太好設計。