Articles Comments

ちからの備忘録的日記 » secret share » 秘密分散法より手軽な情報伝播アルゴリズム(IDA)を試してみる

秘密分散法より手軽な情報伝播アルゴリズム(IDA)を試してみる




IDA とは


出典: P2P File Shareing System using IDA Carleton University

ポーランドのコンピュータ・サイエンティスト Michael O. Robin氏が1989年に開発した情報伝播アルゴリズムである。
簡単に言うと、オリジナルファイルを複数に重複させながら分割し、分割時にしていたファイルの断片数で復元できるというアルゴリズムである。まあ、RAIDみたいもの。

たとえば、オリジナルを8個に分けて、6個集まれば復元可能にするための技術である。秘密分散法に似ているが、秘匿性という意味では、IDAの方が低いようである。

Efficient dispersal of information for security, load balancing, and fault tolerance by Michael O. Rabin Harvard Univ., Cambridge, MA

An Information Dispersal Algorithm (IDA) is developed that breaks a file F of length L = ↿ F↾ into n pieces Fi, l ≤ i ≤ n, each of length ↿Fi↾ = L/m, so that every m pieces suffice for reconstructing F. Dispersal and reconstruction are computationally efficient. The sum of the lengths ↿Fi↾ is (n/m) · L. Since n/m can be chosen to be close to l, the IDA is space efficient. IDA has numerous applications to secure and reliable storage of information in computer networks and even on single disks, to fault-tolerant and efficient transmission of information in networks, and to communications between processors in parallel computers. For the latter problem provably time-efficient and highly fault-tolerant routing on the n-cube is achieved, using just constant size buffers.

IDA のベンチマーク

IDA のベンチマークを取るには、IDAを実装したライブラリが必要です。いろいろな暗号ライブラリを実装したオープンソースのライブラリに、crypto++ がありますので、今回はこれを利用してベンチマークを取ってみようと思います。

crypto++インストール

# mkdir cryptopp; cd cryptopp
# wget http://prdownloads.sourceforge.net/cryptopp/cryptopp561.zip
# unzip cryptopp561.zip
# make
# make install

/usr/bin に cryptest.exe がインストールされます。

IDA ベンチマーク取得

■ オリジナルファイル作成(擬似乱数)

# head -c 10m /dev/urandom > 10m

■ IDA で分散してみる(3個に割って、2個で復元)

# time cryptest.exe id 2 3 10m
real    0m3.814s
user    0m3.772s
sys     0m0.040s

■ ファイルサイズ確認

# ls -lh 10m.*
-rw-r--r-- 1 root root 5.1M  7月 14 18:16 10m.000
-rw-r--r-- 1 root root 5.1M  7月 14 18:16 10m.001
-rw-r--r-- 1 root root 5.1M  7月 14 18:16 10m.002

■ IDA で復元してみる (3個のうち2個のファイル断片を指定)

# time cryptest.exe ir 10m.recover 10m.000 10m.002

real    0m1.125s
user    0m1.100s
sys     0m0.020s

■ オリジナルと復元したファイルが同じか確認

# md5sum 10m 10m.recover
f3aca0e3aeb08d0ec55b0cd3528f5423  10m
f3aca0e3aeb08d0ec55b0cd3528f5423  10m.recover

おまけ: 秘密分散法のベンチマーク

crypto++ では、秘密分散法も実装されていましたので、おまけでベンチマークを取得してみます。

尚、デフォルトのテストプログラムだと Random Seed の入力が求められますので、事前に Random Seed を設定してちょっとカスタマイズします。

■ crypto++ ライブラリのソースがある場所に移動
# cd ~/cryptopp 

■ patch 当てる
# patch < ss.patch
patching file test.cpp

■ コンパイル&インストール
# make;make install

ss.patch の中身は、以下の通り。

# cat ss.patch
--- test.cpp    2011-07-14 18:02:59.000000000 +0900
+++ test.cpp.ss 2011-07-07 10:26:48.000000000 +0900
@@ -293,10 +293,10 @@
                }
                else if (command == "ss")
                {
-                       char seed[1024];
-                       cout << "\nRandom Seed: ";
-                       ws(cin);
-                       cin.getline(seed, 1024);
+                       char seed[1024] = "ZDQ1ZTA3MTJiYTVhMTYyNjMzZjlhMmE0MWU4YjU3MzQgIC0K";
+                       //cout << "\nRandom Seed: ";
+                       //ws(cin);
+                       //cin.getline(seed, 1024);
                        SecretShareFile(atoi(argv[2]), atoi(argv[3]), argv[4], seed);
                }
                else if (command == "sr")

ということで、さっそくベンチマーク取得。

■ オリジナルファイル作成(擬似乱数)

# head -c 10m /dev/urandom > 10m

■ Secret Share で分散してみる(3個に割って、2個で復元)

# time cryptest.exe ss 2 3 10m

real    0m2.720s
user    0m2.528s
sys     0m0.188s

■ ファイルサイズ確認

# ls -lh 10m.*
-rw-r--r-- 1 root root  11M  7月 14 18:30 10m.000
-rw-r--r-- 1 root root  11M  7月 14 18:30 10m.001
-rw-r--r-- 1 root root  11M  7月 14 18:30 10m.002

■ Secret Share で復元してみる (3個のうち2個のファイル断片を指定)

# time cryptest.exe sr 10m.recover 10m.000 10m.002

real    0m1.409s
user    0m1.380s
sys     0m0.024s

■ オリジナルと復元したファイルが同じか確認

# md5sum 10m 10m.recover
f3aca0e3aeb08d0ec55b0cd3528f5423  10m
f3aca0e3aeb08d0ec55b0cd3528f5423  10m.recover

参考:商用利用の事例

Cleversafe

FSV #45 Amazonへの挑戦(2)Amazon S3を凌駕するか、NirvanixとCleaversafe! | Impress Innovation Lab.

スカパーJSAT

スカパーJSAT株式会社 | 安心・安全なデータ分散ネットワーク基盤「S*Plex3クラウド・ストレージサービス」登場

unisys と cleversafe の事例

Information dispersal algorithms: Data-parsing for network security

IDA をチップ化して、リアルタイムでIDA処理

CiteSeerX — A VLSI chip for the real-time Information Dispersal and retrieval for security and fault-tolerance

Related Posts Plugin for WordPress, Blogger...

Filed under: secret share · Tags: , , , ,

Leave a Reply

*