ssss: シャミアの秘密分散法 (ssss: Shamir's Secret Sharing Scheme)

「秘密分散」とは？

Wikipediaから秘密分散に関する記事を引用すると、

暗号理論における秘密分散法とは、参加者から成るグループに秘密 (secret) を配布する一つの方法であり、参加者はそれぞれ秘密の分散情報（share）を割り当てられる。この秘密は分散情報が組み合わせられたときにのみ再構成でき、個々の分散情報だけでは役に立たない。

もっと形式的に言うと、秘密分散法においては一個のディーラ（dealer）と n 個のプレイヤ（players）を仮定する。ディーラは特定の条件が満たされたときにのみ、プレイヤに一つの秘密を与える。ディーラがそうするためには、個々のプレイヤに一つの分散情報を与えて、あらゆる t（閾値 threshold）のグループ、あるいはそれ以上のプレイヤが分散情報を寄せ集めることで秘密を再構成できるようになっており、閾値 t 以下のプレイヤが分散情報を持ち寄っても秘密を再構成できなくなっている。このような仕組みは (t,n)-閾値分散法と呼ばれる。

閾値分散法を実装するためのよく知られたやり方は、多項式補間（「ラグランジュ補間」）を使うものであり、アディ・シャミア（Adi Shamir）が1979年に考案した。この方法はデモページで試せる。

なお、シャミアの方法はセキュアであると証明されている。つまり或る (t,n) の閾値分散法において、或る攻撃者が t-1 で妥当な分散情報を破棄してしまうことと、その攻撃者が分散情報を全くもっていないことは区別できず、攻撃者が閾値 t よりも少ない分散情報しかもっていないなら、秘密を解読するには閾値 t の情報を得る他によい方法は存在しないのである。

どんな場合に「秘密の分散情報」を使うのか

ありふれた事例としては、

• よいパスワードは覚えておくのが難しい。デキる人なら秘密分散法を使ってパスワードの分散情報を生成し、一つの分散情報を連絡帳へ書き込み、もう一つを銀行の貸し金庫へ保管し、また一つは友達に持ってもらったりするかもしれない。もしその人がパスワードを忘れたときでも、分散情報からパスワードを再構成するのは簡単である。もちろんパスワードを直に連絡帳へ書き込むと「敵」にそれを奪われるかもしれないので、セキュリティ上のリスクがある。対して、秘密分散法を使うと敵は色々な場所に保管してある分散情報を手に入れなくてはならなくなる。

  このような事例の応用としては、暗号化されたバックアップシステムという安全な実装方法がある。データを頻繁に復元しないと仮定すれば、データを公開鍵で暗号化してバックアップでき―これはユーザの手を経ることなく自動的になし得る―、秘密鍵は秘密分散法で保護しておける。

• 「ディーラは元の秘密を復元するのに必要な全ての t 個の分散情報を、t 個の異なるチャネルを使ってたった一人の参加者に渡せる。攻撃者は t 個の分散情報を全て横取りできなくてはならないが、それはたった一つのメッセージを横取りすることに比べると難しい。」（Wikipedia contributors. "Secret sharing." Wikipedia, The Free Encyclopedia. Wikipedia, The Free Encyclopedia, 9 Sep. 2011. Web. 12 Sep. 2011)

• 或る銀行の役員なら金庫の解除コードの分散情報を生成し、複数の従業員に分けて持たせられる。その役員がいないときでも金庫は従業員たちの分散情報を使って開けられるが、それは秘密を復元するのに必要な数の分散情報を持つ従業員が揃ったときだけである。このような状況で従業員が完全に信頼できなくても、秘密分散法が使える。

"ssss" とは何か、どこでダウンロードできるのか

ssss は、シャミアが考案した秘密分散法を UNIX/Linux マシンに実装した一つの例である。これはフリーソフトウェアであり、プログラムコードは GNU GPL ライセンスのもとで配布される。ssss は二つのことをやる。一つは既知の秘密から分散情報を生成すること、そしてもう一つは与えられた分散情報を使って秘密を再構成することである。このソフトウェアは B・ポータリング（B. Poettering）が2006年に書いて、GNU libgmp Multi-Precision Library（バージョン 4.1.4 で正しく動く）をリンクし、/dev/random エントロピープールを必要とする。

• ssss-0.5.tar.gz (SHA1: 3f8f5046c2c5c3a2cf1a93f0a9446681852b190e)
• ssss-0.4.tar.gz (SHA1: 462a4309fabc02abf6f3470c5223f0aea44e2a05)
• ssss-0.3.tar.gz (SHA1: 433590f2c132e0040b13d1c21a2bf55eead6929c)
• ssss-0.2.tar.gz (SHA1: bcfdf3212e461baaa5922193faa1aec2bfffbb9c)
• ssss-0.1.tar.gz (SHA1: 66f8fca5793034fc42032f70de7f9195e4bb4bcd)

何人かの人々が言うには、ssss-0.5 はコンパイルで問題が起こるようだ。これは次回のリリースで修正したい。もしこのコードがあなたのマシンで正しく動かないときは、ssss.c の351 行めを下記と置き換えてもらいたい。

int restore_secret(int n, void *A, mpz_t b[])

man ページは、groff 版と html 版がある。

バージョンごとの違いは、履歴ファイルで確認してほしい。それから ssss には Debian のパッケージがある^*1。新しいバージョンは freshmeat の専用ページでお知らせする。

また、誰かが ssss の古いバージョンの Windows 版を公開している（が、乱数発生の方法が少々荒っぽいと思う）。

ssss はどうやって使うのか、オンラインのデモはあるか

或る既知の秘密から分散情報を生成するには、まず以下を見てもらいたい。ここでは(3,5)-閾値分散法を使う。つまり、五つの分散情報を生成して、任意の三つの分散情報で秘密を再構成できるやり方だ。

% ssss-split -t 3 -n 5
Generating shares using a (3,5) scheme with dynamic security level.
Enter the secret, at most 128 ASCII characters: パスワードとかを入力する
Using a 184 bit security level.
1-1c41ef496eccfbeba439714085df8437236298da8dd824
2-fbc74a03a50e14ab406c225afb5f45c40ae11976d2b665
3-fa1c3a9c6df8af0779c36de6c33f6e36e989d0e0b91309
4-468de7d6eb36674c9cf008c8e8fc8c566537ad6301eb9e
5-4756974923c0dce0a55f4774d09ca7a4865f64f56a4ee0

これらの分散情報の組み合わせで、再び秘密を作り出せる。

% ssss-combine -t 3
Enter 3 shares separated by newlines:
Share [1/3]: 3-fa1c3a9c6df8af0779c36de6c33f6e36e989d0e0b91309
Share [2/3]: 5-4756974923c0dce0a55f4774d09ca7a4865f64f56a4ee0
Share [3/3]: 2-fbc74a03a50e14ab406c225afb5f45c40ae11976d2b665
Resulting secret: さっき入力したパスワードとか

デモページでも ssss を試せる。

もし長い文字列の秘密を分散した場合には、或る複合的な技術が使われる。つまり、秘密をブロック暗号で（openssl や gpg 等を使って）暗号化し、それを復号化するためのまさに鍵として分散情報を出力する。この話題について更に知りたい場合は、man ページを参照してもらいたい。

さいごに

seccure は、同じ著者による別の暗号関連ソフトウェアである。