メルセンヌツイスタはそんなに衝突しない

κeenです。こちらのスライドが話題になっているようです。

[10秒で衝突するUUIDの作り方 - Speaker Deck](https://speakerdeck.com/tanakahisateru/10miao-dechong-tu-suruuuidfalsezuo-rifang)

笑い話としても乱数の難しさの側面としても面白いのですが、これを見た人たちの反応がちょっと勘違いしてそうだったので補足します。
別に私は暗号とか乱数とかの専門家ではないです。

発表者の方の[コード](https://gist.github.com/tanakahisateru/ff65a6b572356fe3be3570e0d8977feb)は読みましたか？

少し速度が必要になるのでRustに移植します。

```toml

[package]
name = "genuuidv4"
version = "0.1.0"
edition = "2018"

# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html

[dependencies]
rand = "0.7.2"
sfmt = "0.6.0"

```

sfmtはメルセンヌツイスタのRNG(乱数生成器)ライブラリです。

```rust
use rand::{Rng, SeedableRng};
use sfmt::SFMT;
use std::io::{self, BufWriter, Write};

struct GenUuidV4(SFMT);

impl GenUuidV4 {
    const VERSION: u8 = 4;
    const VARIANT: u8 = 2;

    pub fn generate(&mut self) -> String {
        let bytes = self.random_16bytes();
        Self::from_16bytes(bytes)
    }

    pub fn random_16bytes(&mut self) -> [u8; 16] {
        self.0.gen()
    }

    pub fn from_16bytes(b: [u8; 16]) -> String {
        format!("{:x}{:x}{:x}{:x}-{:x}{:x}-{:x}{:x}-{:x}{:x}-{:x}{:x}{:x}{:x}{:x}{:x}",
                b[0], b[1], b[2], b[3],
                b[4], b[5],
                (Self::VERSION << 4 | 0b00001111u8 & b[6]), b[7],
                (Self::VARIANT << 6 | 0b00001111u8 & b[8]), b[9],
                b[10], b[11], b[12], b[13], b[14], b[15],
        )
    }
}
fn main() -> io::Result<()>{
    use std::env;

    let n = env::args().nth(1).expect("missing arg N").parse::<u32>().expect("arg N isn't a number");
    // IOがそこそこ重いので高速化しておく
    let out = io::stdout();
    let mut out = BufWriter::new(out.lock());
    for _ in 0..n {
        let mut uuid = GenUuidV4(SFMT::from_entropy());
        out.write(&uuid.generate().into_bytes())?;
        writeln!(out, "")?;
    };
    out.flush()?;
    Ok(())
}

```

これを実行すると衝突するので正しく移植できているようです。

```console
$ cargo run --release 65536 | LANG=C sort | uniq -d
    Finished release [optimized] target(s) in 0.01s
     Running `target/release/genuuidv4 65536`
2669ea66-d52f-4179-8758-462ccfa05
```

このコード、問題なのはループ内だけです。

```rust
for _ in 0..n {
    let mut uuid = GenUuidV4(SFMT::from_entropy());
    out.write(&uuid.generate().into_bytes())?;
    writeln!(out, "")?;
};
```

ループ内でシードを初期化しているのが問題です。`from_entropy` で内部の初期化に使われているのは追っていくとシステムコールの[`getrandom`](http://man7.org/linux/man-pages/man2/getrandom.2.html)です。`getrandom`ソースは `urandom` ですがこれはマニュアルによると暗号用途にも使えるらしいので乱数の質としては問題ないでしょう。

問題になっているのはこの `SFMT` のシードに使われるベクトルが [32bitしかない](https://docs.rs/sfmt/0.6.0/sfmt/struct.SFMT.html#impl-SeedableRng)点です。
シードが同じなら同じ乱数列が生成されるのでUUIDも同じものになってしまうのはスライドで紹介されている通りです。メルセンヌツイスタのアルゴリズムではなく、シードの空間の問題です。

シードの空間が32bitであるということは [誕生日のパラドックス](https://ja.wikipedia.org/wiki/誕生日のパラドックス) の考え方でいくとおおむね32bitの1/2乗くらいのオーダーで衝突するので、 平均して 2^16 = 65536 個のUUIDを生成すると衝突する組が得られる訳です。

メルセンヌツイスタ自体は2^19937-1の周期を持っているのでそう簡単には衝突しません。
初期化を一度だけして、メルセンヌツイスタの内部状態をずっと使い回すようにしてみましょう。

```rust
let mut uuid = GenUuidV4(SFMT::from_entropy());
for _ in 0..n {
    out.write(&uuid.generate().into_bytes())?;
    writeln!(out, "")?;
};
```

これなら16,777,216個くらい生成しても衝突しません。

```console
$ cargo run --release 16777216 | LANG=C sort | uniq -d
   Compiling genuuidv4 v0.1.0 (/home/shun/Rust/genuuidv4)
    Finished release [optimized] target(s) in 0.34s
     Running `target/release/genuuidv4 16777216`
$
```

原理的には少なくとも (2^19937)^(1/2) 個のUUIDを生成すれば乱数が1周しますが、その前にUUID v4の空間が122bitしかないことから2^61個生成すれば衝突するはずなのであんまり周期は関係なさそうですね。

該当のスライドを見て「メルセンヌツイスタは暗号論的疑似乱数生成器でないから衝突する」なんて言ってる人もいましたが暗号論的に次の値が予測できないことと122bit生成して衝突しないことはあんまり関係なさそうに見えます。暗号論詳しくないので詳しい方いましたら教えて下さい。

ということでUUIDが衝突する原理はメルセンヌツイスタのアルゴリズムではなく、32bitしかないシードを毎回与えていたのが原因であることを紹介しました。詳しくないことを正しく怖がるのはいいんですが半知半解のまま適当に怖がり回すのはやめましょうね。