Base N + checksum

因為公司職務的關係很容易接觸到演算法相關議題,這邊提幾個單純的東西出來 … 學會這招應該很容易製作類似英數字夾雜的 coupon 卷或是站內的 serial num 有的沒的 …

首先,何謂 Base N,其實常見的應該都是 Base 2 / 10 / 16 / 36 / 58 / 64,這邊先以 IP 為例

114.32.151.90 # 人看的,以下為 raw data
01110010.00100000.10010111.01011010 # 二進位(Base2)
1914738522 # uint32 十進位 (Base10)

對自己而言,把 IPv4 存入 DB 最佳解應該是最後一個,也就是 4 bytes 即可,而非 string(15),且未來能方便做 mask 之類的計算(其實就是類似 & 4294967040 (11111111.11111111.11111111.00000000) 同 class C 區段會同值,很容易做 group),而非存入 “114.32.151.90” 這些文字,且對電腦而言, string to int 的速度慢過於 bit 位元的移動和操作之類的([left | right] shift operator,也就是 <<>>,還有 & | ^ 之類的運算),詳細不贅述,念一下 CCNA 或網路概論之類的鬼應該就會知道為何是 IP 配 mask 與前因後果之類的

虛擬幣的部分也是,如 Bitcoin wallet (testnet … 我怕有人匯錢進去哈哈)

require 'digest'
require 'base58'
# bitcoin_alphabets = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz"
wallet = "n1akTRMp4aravG2pym1no78WWnaMYjf8Gv" # Base58
Base58.base58_to_int("n1akTRMp4aravG2pym1no78WWnaMYjf8Gv" , :bitcoin)
#=> 702155195706704810540438501314396144758208656841492246595335 # Base10
hex = Base58.base58_to_int("n1akTRMp4aravG2pym1no78WWnaMYjf8Gv" , :bitcoin).to_s(16)
#=> "6fdc1a4c17bf1add4eae8717d9e7ee796e11092eda8a188707" # Base16
target_checksum = Digest::SHA256.hexdigest(Digest::SHA256.digest([hex[0...42]].pack("H*")))
#=> "8a188707ded9188ec0dd11ad7f5950d885b7adc539b36adf696f62653c51d661"
# pack H* 是把 hex 轉為 binary,因為 binary 不等於 hex,hex 是把 binary 轉成 Base16 的結果
source_checksum = hex[-8..-1]
#=> "8a188707"
is_vaild = target_checksum[0...8] == source_checksum
#=> true

看懂這些 code 就會知道如何寫作 BTC wallet validator,其實也就把兩次 sha256 的部分 checksum 結果放在 wallet hex 的結尾,然後用 base58 重新 encoding 之類的,而 Base58 的計算方式等同於 Base N,其實就是連除法後按照對照表(上面的 bitcoin_alphabets )塞回去而已,所以類似 Base16 是 0~F 一樣,你可以設計自己的對照表,類似亂數的英文之類的,Base58 那個 gem 的寫法其實很簡單(其實就連除法而已),想要 port 到 golang 也很容易就是

最後是 checksum … 其實我看過最差的 checksum 就是身分證字號,其容易猜測和運算,最後 1 碼換最差 9 次一定就會命中 … 而非上面的 BTC wallet … 因為是 Base16 的 8 碼 (4byte) 和 Base58 互換,所以應該是 5.887 碼 … 這應該是人類難以理解的就是 …

當然 BTC 的 checksum 不一定是個好方式,類似可以加上一些 mask / noise / salt 來做一些事情,hash 部分可以用 MD5 / SHA 或快一點的 CRC32,也可以對字母本身排列組合下手

所以如何設計一個 coupon code?首先先決定長度,類似 PS4 現金卡的 serial

A4HL-MQNA-HQFG

然後我們訂個表,不過不和 Base58 一樣,我們自定義 Base34 和取代表

"0123456789ABCDEFGHJKLMNPQRSTUVWXYZ"
"O" => "0"
"I" => "1"
"l" => "1"

上不上 checksum 沒關係,如果有自信每次都查 DB 的話,不過我們先解碼唄,這邊不以速度為前提的最簡 code

custom_base34_alphabets = "0123456789ABCDEFGHJKLMNPQRSTUVWXYZ"
ruby_base34_alphabets = (0...34).to_a.map{|i|i.to_s(34)}.join
#=> "0123456789abcdefghijklmnopqrstuvwx"
source = "A4HL-MQNA-HQFG".gsub("-" , "")
source_int = source.split("").map{|c|ruby_base34_alphabets[custom_base34_alphabets.index(c)]}.join.to_i(34)
# => ["A", "4", "H", "L", "M", "Q", "N", "A", "H", "Q", "F", "G"] 後 index 互換,把 string(指定 base34) 轉成 int
# => 711214993230988886

hmm 好吧,這邊忘記做一個最大數字的替換 … 簡單的來說要先求 max 才行 … 類似拿上面的 alphabets 最大數字做一次轉換,取得 binay 最長的位數,類似

max_int = "xxxxxxxxxxxx".to_i(34)
#=> 2386420683693101055
max_int.to_s(2)
#=> "10000100011110010001001111011111010000001011000000111111111111"
max_int.to_s(2).length
#=> 62

然後你可以開心製造個 mask / noise (以下簡稱 mask) 出來,類似 10 連續

"10" * (62 / 2)
#=> "10101010101010101010101010101010101010101010101010101010101010"
mask_int = ("10" * (62 / 2)).to_i(2)
#=> 3074457345618258602

但其實這個數字不能用哈哈 … 因為開頭的 101 就超過了 max 的 100 … 所以這樣做 mask 會把數字弄 overflow 的(encode base34 時會多一兩碼 …) … 所以建議對 max 再做一次 and

mask_int = mask_int & max_int
#=> 2308658456915610282
#=> "10000000001010000000001010001010000000001010000000101010101010"

最後把你的原本數字看是要上還是解 mask,其中 xor 能正反轉最好用

source_int
#=> 711214993230988886
source_int ^ noise_int
#=> 3014243946313223420
source_int ^ noise_int ^ noise_int
#=> 711214993230988886

或是你開心可以上點攪亂器(這邊只做範例)

x = "11001111".to_i(2) #=> 207
x = (((x & "1111".to_i(2)) << 4) + (x >> 4)).to_s(2) #=> 252
x.to_s(2) #=> "11111100"
# 其實就是把後四位和前四位兩個交換

以上,這邊描述如何上 checksum(其實轉 hex / binary 你想怎樣搞都行,單純看你是否要少 N 碼來當 checksum 而已),還有一些 base / noise 互轉互拼的方式,你可以把 checksum 丟到 source 內,或是兩個分別獨立,各有好壞處就是,而上 checksum 最好的地方是怕別人打錯字唄,所以看重要性與頻率加入之類的 …

最後給這篇文章的末尾加上一個開放性的議題:Ruby 很好寫,其 int 基本上為無限大或受限於你的記憶體大小,但是上到 golang 或其他語言後,最大可能只到 uint64 甚至 uint32,所以設計這些時 … 請把這個列入考量之類的,自己在實作別人家演算法時,對方用了 pow(N次方)來做某段的 checksum … 結果後來必須要用 bigInt 來解才行(float / double ? 你一定是在開玩笑 … 精確度會遺失),所以設計這類的東西也要考慮其他語言的因素就是了,大概這些,以上

延伸閱讀,想要攪亂器,其實 noise 應該夠了,但其實還能看到些 pattern,真的想要亂一點的話 … 看完這篇唄 : )