はじめに
UUIDとは世界中でユニークになるように設計されたIDで、データベースの主キー等によく用いられています。
（UUID以外のユニークなIDについてはこちら！）
RustやRubyといったリッチなプログラミング言語では簡単にセキュアな（衝突しない）UUIDを生成できる関数が提供されています。
しかし、言語によってはそのような関数が提供されておらず、自前で生成する必要があります。
今回はLuaでUUID v4を生成することを考えます。
いろいろな方法
シンプルな方法
local function generateUuid()
local template ='RRRRRRRR-RRRR-4RRR-rRRR-RRRRRRRRRRRR'
return string.gsub(template, '[Rr]', function (c)
return string.format('%x', (c == 'R') and math.random(0, 0xf) or math.random(8, 0xb))
end)
end
この方法は懸念があります。
それは、math.random()が擬似乱数生成器であり、かつ、シード値が与えられていない点です。
一般に、プログラミング言語で関数として提供されている乱数生成器は擬似乱数生成器です。
擬似乱数生成器は、擬似乱数列と呼ばれる「一見乱数列のように見えるが、実際には確定的な計算によって求めている数列」を生成します。
Lua5.4のリファレンスによると、math.random()は xorshiro256** と呼ばれる擬似乱数生成器を使われています。
擬似乱数生成器は同一のシード値が与えられた時はあらゆる環境で同一の乱数列を生成します。
リファレンスによると、math.random()はシード値が与えられていない時は
Lua generates a seed with a weak attempt for randomness.
となっていて、弱い乱数をシード値としている、とだけ記述されており、同一のシード値によって乱数が生成されるリスクがありそうです。
/dev/urandomを使う
local function secureRand()
local urandom = assert(io.open('/dev/urandom', 'rb'))
local res = 0
for i = 1, 8 do
local r = urandom:read(1):byte(1)
res = res * 256 + r
end
urandom:close()
return res
end
local function generateUuid()
local template ='RRRRRRRR-RRRR-4RRR-rRRR-RRRRRRRRRRRR'
return string.gsub(template, '[Rr]', function (c)
return string.format('%x', (c == 'R') and secureRand() % 16 or 8 + secureRand() % 4)
end)
end
/dev/urandomはUnix系OSに組み込まれたほとんど真の乱数生成器です。（詳しい議論はしません。というか、できません。）
RubyのSecureRandom.uuidは/dev/urandomを使って実装されています。
/dev/urandomを使うことで、他の言語のUUID生成関数と同等のセキュアさになります。
シード値に/dev/urandomを使う
math.randomseed(secureRand(), secureRand())
local function generateUuid()
local template ='RRRRRRRR-RRRR-4RRR-rRRR-RRRRRRRRRRRR'
return string.gsub(template, '[Rr]', function (c)
return string.format('%x', (c == 'R') and math.random(0, 0xf) or math.random(8, 0xb))
end)
end
生成ごとにシード値に/dev/urandomを使う
local function generateUuid()
math.randomseed(secureRand(), secureRand())
local template ='RRRRRRRR-RRRR-4RRR-rRRR-RRRRRRRRRRRR'
return string.gsub(template, '[Rr]', function (c)
return string.format('%x', (c == 'R') and math.random(0, 0xf) or math.random(8, 0xb))
end)
end
これらは、シード値に/dev/urandomを、乱数生成にmath.random()を使うことで、高速でかつ、ある程度セキュアであることを期待しています。
os.time()をシード値とするパターンが良く紹介されますが、これは同一秒内だと同一のシード値になり同一のUUIDが生成されてしまうので避けたほうが良いでしょう。
パフォーマンス
自分の環境で、各手法でUUIDを100000個生成するのにかかった時間は以下のようになりました。
| 手法 | 時間 |
|---|---|
| シンプルな方法 | 0.721s |
/dev/urandomを使う |
157.124s |
シード値に/dev/urandomを使う |
0.715s |
生成ごとにシード値に/dev/urandomを使う |
10.297s |
/dev/urandomを呼び出す回数が多いほど、パフォーマンスは低下しました。
まとめ
UUIDを自前で生成する場合は、セキュアさとパフォーマンスを検討する必要があります。
ご意見・ご感想、よろしくお願いします。