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

B. Poettering (translated by Takayuki Kawamoto)

Last modified: Fri Sep 15 22:50:20 CEST 2006
Created: Wed Jul 19 10:25:20 CEST 2006
Last modified as a translation into Japanese:
First published as a translation into Japanese:2011-09-12 17:44:15.
"Shamir's Secret Sharing Scheme" (as of 2013-02-06).
The text of this page is licensed under the GNU General Public License.
Copyright 2005, 2006 by B. Poettering (ssss AT point-at-infinity.org).

「秘密分散」とは?

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

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

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

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

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

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

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

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

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

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

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

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

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

訳註 *12007年に FreeBSD の Ports でも提供されている。また、CentOS の rpm パッケージも提供されている。

また、誰かが 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 は、同じ著者による別の暗号関連ソフトウェアである。

もし ssss あるいは seccure が有用だと思ったら、寄付をご検討ください。

bitcoin logo Bitcoin address: 1BWaryNxvEdkzRMZ6L4y2bgvBwhRyFTHQ2 bitcoin address


The text of this page is licensed under the GNU General Public License. Copyright 2005,2006 by B. Poettering (ssss AT point-at-infinity.org).

訳註この文書は、B. Poettering さんのサイトに掲載されている ssss の解説である。彼の given name はおおよそ見当がついているけれども、何らかの事情で明かしていないものと判断し、翻訳でも敢えてイニシャルのままにしてある。なお、ウィキペディアにリンクしているアンカーについては、英語版の文章そのものに言及したり引用している場合は英語版のままとしてあるが、キーワードにリンクを張っているだけと判断できる場合は日本語版にリンクしてある(もちろん、日本語版が存在しないキーワードは英語版にしかリンクできないが)。

冒頭に戻る


※ 以下の SNS 共有ボタンは JavaScript を使っておらず、ボタンを押すまでは SNS サイトと全く通信しません。

Google+ Twitter Facebook