Articles Comments

ちからの備忘録的日記 » secret share » シャミアの秘密分散法をPHPで実装して、どれくらい時間がかかるのか試してみた

シャミアの秘密分散法をPHPで実装して、どれくらい時間がかかるのか試してみた




仕事の関係で、シャミアのしきい値秘密分散法を勉強中。

» How to Share a Secret by Shamir, 1979

商用の製品もいろいろあるようですが、気軽に試せないため、オープンソースで実装されているのを探してみる。

» KennyNet » PHP: Shamir’s Secret Sharing Class
» Implementation of Shamir’s method for sharing a secret
» SourceForge.net: Shamir Secret Sharing in Java
» Shamir’s Secret Sharing Scheme

上記のように、PHP, Perl, Java, C の4つの言語で実装されているのを見つけることができました。個人的に一番なじみのある PHP を試してみることにしました。

// 分散したいデータ
$secret = "nemf";

// 復元するのに最低必要なシェア数
$quorum = 2;

// シェア数
$number = 3;

// 秘密分散処理実施!
$parts = Shamir::share($secret, $number, $quorum);

// シェアの中身をダンプ
print_r($parts);
【実行結果】
Array
(
    [0] => 0201dfd30fe9
    [1] => 02024f40b26b
    [2] => 0203c0ae54ee
)

real    0m0.072s
user    0m0.060s
sys     0m0.010s

4byte だと早いですね。ただ、1つあたりのシェアのサイズが 12byte で、全部で3つに分散したので 36byte になります。2つで復元できるので、4byte 復元するのに 24byte も必要な計算ですね。

3MB のファイルを試してみましたが、memory_limit を 4GB にしないとそもそも実行できませんでした。CPU使用率は、100%。で、肝心の実行時間ですが、以下の通りです。

【実行時間】

real    1m7.119s
user    1m6.120s
sys     0m0.988s

計算量が半端じゃないんだなぁと。あと、メモリ使いすぎ。。。

ということで、シャミアの理論どおりに実装すると、とてもじゃないですが、数GBのファイルを秘密分散するというのは夢のまた夢だということがよくわかりました。

ちなみに、検証環境は以下の通りです。

hpasmcli> show server
System        : ProLiant BL460c G6
Processor: 0
        Name         : Intel Xeon
        Stepping     : 5
        Speed        : 2533 MHz
        Bus          : 133 MHz
        Core         : 4
        Thread       : 8
        Socket       : 1
        Level2 Cache : 1024 KBytes
        Status       : Ok

Processor: 1
        Name         : Intel Xeon
        Stepping     : 5
        Speed        : 2533 MHz
        Bus          : 133 MHz
        Core         : 4
        Thread       : 8
        Socket       : 2
        Level3 Cache : 8192 KBytes
        Status       : Ok

Processor total  : 2
Memory installed : 24576 MBytes

# cat /etc/redhat-release
CentOS release 5.4 (Final)

# php -v
PHP 5.1.6 (cli) (built: Jan 13 2010 17:09:42)
Copyright (c) 1997-2006 The PHP Group
Zend Engine v2.1.0, Copyright (c) 1998-2006 Zend Technologies

【2011/7/15 追記】
C++ での実装を試した記事を書きましたので、「秘密分散法より手軽な情報伝播アルゴリズム(IDA)を試してみる」もご参考までに。

Related Posts Plugin for WordPress, Blogger...

Filed under: secret share · Tags: , ,

Leave a Reply

*