ノルウェーの突撃隊：閾値秘密分散共有法

『閾値秘密分散共有法』についてネットで調べてみたが意外と資料が少なかったので、折角だから分かったことをここに載せておこうと思う｡

『閾値秘密分散共有法』は情報の分散と共有によって情報を保護するためのセキュリティ技術である。
今回は特に『(k,n)閾値秘密分散共有法』について説明する｡
（以下からは『(k,n)閾値秘密分散共有法』のアルゴリズムを実装したソースコードに沿って説明する）

『(k,n)閾値秘密分散共有法』の原理は、 n次の線形方程式の性質を応用している。

 

上図のようなある1次方程式の直線の切片の値を秘密にしたいデータとしたとき、その直線が求まるには最低でも直線上の２点が定まらなければならない｡だが勿論、直線上の点は無数に存在できる。このとき、いずれか２つの点の座標が復号化のための鍵となる。
つまり、N次の線形方程式の形（各係数の値（切片含む）と同義）は、その方程式の解が N + 1個以上定まることで導出できる。逆にいえば、それらが N個以下では絶対に線型方程式の形は定まらないので、情報は一切洩れない。

 

次に実際のプログラムの説明である｡
このプログラムの振る舞いは
①1次方程式の各係数にランダムな数字を割り当てる（Line 39: "ran"メソッド）

②ある情報 X を n 個の無機質な暗号化データに分ける（ Line 62: "enc"メソッド ）
③その N個のデータのうちの K 個以上が揃えば元のXを復元できる（Line 71:  "dec"メソッド ）。

 

D's CODEsのJavaに以下のファイルをzipで固めたものを貼り付けておいた(SecretSharing.zip)｡
・Simple.java: 最も単純な秘密共有分散（norを使ったもの）

・K_N.java: (2,n)閾値秘密共有分散法のアルゴリズム

・Main.java: K_N.javaを動かしてみたもの

 

以下はMain.javaの実行結果である｡
 

~~ Main Code's  Result ~~

F(x) = 16x + 23 mod 41

key1: 25

key2: 27

key3: 29

key4: 31

key5: 33

1 & 2: answer: 23

1 & 3: answer: 23

1 & 4: answer: 23

1 & 5: answer: 23

2 & 3: answer: 23

2 & 4: answer: 23

2 & 5: answer: 23

3 & 4: answer: 23

3 & 5: answer: 23

4 & 5: answer: 23