activation code を設計する #JavaScript

activation code とは

ここでは次の特徴を持つデータのことをいう。

特定のサービスでのみ有効
文字列
1 度しか使えない

OS やプロプライエタリーなソフトウェア、プリペイド式の仮想通貨などで使われているようなアレ。

どういうフォーマットがいい ?

文字種

打ち間違いがないように 1 と I 、 0 と O など似ている文字がないほうがよいが、 1 桁にできるだけ情報量を持たせたい。ということでいろいろ見てみたところ Base32 が良さそう。

Base32 では ABCDEFGHIJKLMNOPQRSTUVWXYZ234567 の 32 文字を使ってエンコーディングする。 40bit 単位でエンコーディングするのではみ出した分は = でパディングされるが、 ID として使うときにはパディングをとってしまえばいい。

長さ

入力の手間を省くため短いほうがよいが、後述する衝突確率を小さくするためにはあるていどの長さが欲しい。英数字の場合、人間がぱっと記憶できる最大桁数は 6 桁のようなので、これを基準に考える。

具体的に 6 桁までで抑えるか、その倍数あたり。 4 桁なら確実に覚えられるでしょということで 4 桁の倍数でもよいかもしれない。

推測困難であること

数字の連番のように使えるものが推測可能、では使えないので生成される ID は完全にランダムであることが必要。
ランダムでも使える ID の数カ所を変えたら使えるほどにぎゅうぎゅうに詰まっていると意味をなさないので十分にスパースであることも重要になる。

乱数について

今までの流れで乱数を使うのだが、その質が重要になる。

乱数の周期について

推測不可能であってほしいので何らかの分布に従うものは避けたい。というわけで最近有名な一様分布な乱数となると次になる。

生成手法	周期
メルセンヌツイスター	$2^{19937}-1$
xorshift128	$2^{128}-1$

周期というのはある数が出現してから次にその数が出現するまでの間に生成される異なる数の個数。これが長いほうが乱数としてはすごい。

生成 ID の周期について

上記のような乱数をもとに ID を生成するわけなので生成された ID にも周期が存在する。扱いやすさのために 64bit 長とかで生成すると 1 個の乱数で済むが、ここでは桁数をカスタマイズしたいので複数の乱数を組み合わせて ID を生成していく。生成アルゴリズムは次のような感じにする。

const generateId = (digits: number) => {
  assert(0 < digits && Math.floor(digits) === digits)
  const chars = []
  for (let i = 0; i < digits; ++i) {
    chars.push(Math.floor(Math.random() * 16).toString(16))
  }
  return chars.join('')
}

で、乱数の周期が $r_1, r_2, ..., r_c$ のようになっているとすると、生成された ID の周期は一番最初に生成された ID からはじまり、 ID の一番最後の値がちょうど $r_c$ となるものまでなので、次のようになる。

C = \frac{lcm(c, n)}{n} \\

ここではそれぞれ次の意味とする。

lcm() は最小公倍数を計算する関数
c は乱数周期
n は ID を生成する際に使う乱数の個数

上記の式から計算すると、たいていの桁数で使用している乱数の周期そのものとなることがわかる。特に xorshift128 の場合、周期が素数なのでいくつ使おうが乱数の周期が ID の周期となる。

衝突確率

前述したスパースであることと重なるが、不正利用を防ぐため、なにかの ID をぽんと入力したときにそれが有効な ID でないことを担保したい。これは文字列の衝突確率を計算して、どのくらいを許容するかという閾値を設ける、という考え方でなんとかなる。

http://quesqa.com/random-string-collision-prob/ に示されているように文字列の衝突確率は次で計算可能。

P_n = 1 - \prod_{i=0}^{n-1}(1 - \frac{i}{b^d}) \approx 1 - \exp(-\frac{1}{b^d}\frac{n(n-1)}{2})

n は生成する ID の個数
b は文字種の数
d は桁数

さっと計算できるように実装してみた。

Base32 では次のようになる。

生成個数	6 桁	8 桁	12 桁
1,000 個	0.0004650874393118398	4.5429250039585867e-7	4.332090242087361e-13
10,000 個	0.04549411673171355	0.00004546915386183237	4.336375702962414e-11
100,000 個	0.9905009768022223	0.004537104138253034	4.336765280221755e-9

で、どのていどを許容するかだが、そもそも brute force attack を防ぐために単位時間あたりの試行回数を有限回に制限するなどの実装をするはずなので、大体 0.0001 よりも低ければ良いんじゃないかと思う。ここらへんは長さと安全のトレードオフということで各位で閾値を設けるところ。

落とし所

発行するコードの数によるが、次のようになるか。

1,000 個発行するなら Base32 6 桁
- XXXXXX の形式
100,000 個発行するなら Base32 8 桁
- XXXX-XXXX の形式
100,000,000 個発行するなら Base32 12 桁
- XXXX-XXXX-XXXX の形式

前提として activation code の入力を単位時間あたり有限回に制限する、というシステム実装が必要、ということで。