分布が部分空間に落ちていないかチェックする

某所で「あるN-bitの列がN次元空間中で均等に分布しているかどうか確認したい」という話題が出てて、面白そうだったので書いてみた。

まず正しく6次元空間に分布している例。

>>> from pylab import *
>>> data1 = [[random_integers(0, 1) for _x in range(6)] for _y in range(100)]
>>> from matplotlib.mlab import PCA
>>> PCA(array(data1))
<matplotlib.mlab.PCA instance at 0x110a23368>

>>> _.fracs
array([ 0.22253508,  0.18659093,  0.17676459,  0.15136027,  0.14785211,
        0.11489702])

主成分分析の結果のfracsは寄与率を返す。だいたい1/6(0.166...)前後になっているのがわかる。データの個数を100個と少ないので0.22〜0.11とばらついているけど。

一方、軸の間に相関がある場合。

>>> def make_vec():
    ret = [random_integers(0, 1) for _x in range(3)]
    return ret + ret

>>> data2 = [make_vec() for _y in range(100)]
>>> PCA(array(data2))
<matplotlib.mlab.PCA instance at 0x111cef7a0>

>>> _.fracs
array([  3.83213080e-01,   3.30321515e-01,   2.86465405e-01,
         3.05496905e-31,   5.77068439e-32,   6.60331164e-33])

このケースでは実質的には3次元の部分空間上にしか分布していないので、主成分分析の結果の寄与率が4〜6番目の軸に関してとても小さくなっていることがわかる。

もちろん「各軸の間に相関はないけども暗号論的には適切でない分布」はこの方法では判別できないけども、この方法は手軽に試せるので最初の一歩として確認してみると良いのではないだろうか。

追記: 「各軸ごとの平均値をみたらいいんじゃない？」という質問があったけども、それは「v[0]が常に0」みたいなタイプの潰れ方には有効だが、 この例のような「v[0] == v[3]」という潰れ方に気づくことができません。ただ、この方法でも「v[6] = v[0] ^ v[1] ^ ... ^ v[5]」みたいな潰れ方には気づくことができません。