sss(Shamir's Secret Sharing)をGolangで実装する
Contents
こんにちは、エンジニアインターンの南条です！
現在大学で、情報セキュリティを専攻しているのですが、その講義内でブロックチェーン界隈でも注目されている秘密分散法について学んだので今回はGolangで実装してみたいと思います！
あくまでも、仕組みを理解するためのコーディングなので、処理速度などは考慮せずに進めていきたいと思います。
コードや内容についてのご指摘やアドバイスなどはTwitter(@nandehu0323)にいただけると非常にありがたいです！
1. 秘密分散法
秘密分散(秘密分割)とは一定の参加者で秘密を分散する方法で、参加者にはそれぞれ秘密を分散したカケラ(share)が配布されます。
秘密を消去してもある一定数のカケラを集めることで、元の秘密を復元することができます。
秘密分散法には色々な種類があり、2017年10月にISOが秘密分散技術の国際標準を発表しました。
- Shamir secret sharing scheme (ssss)
- Ramp Shamir secret sharing scheme
- Additive secret sharing scheme for a general adversary structure
- Additive secret sharing scheme
- Computational additive secret sharing scheme
今回のsssは、その中でもn個に分割した分散値をk個集めると復号できる閾値方式の一種。
RSA暗号やゼロ知識証明の一種であるFeige-Fiat-Shamir Identification Schemeを開発したAdi Shamir氏が発表した方式です。
2. Shamir’s Secret Sharing
まずは簡単に理解するために、Shamir(2,3)閾値秘密分散法を図を使って説明しようと思います！
秘密を3個に分割し、そのうちの分割値2個から復号します。
はじめにY軸との交点がM、傾きがRの直線をグラフ上に引きます。
ここでのMは秘密値を示します。今回はRを3、Mを5として考えていくものとします。
Step1.直線を引く
次に秘密を3個に分割、つまり直線上から3個の点を求めます。
Step2.点を求める
これで秘密値を3個の分散値に分散させることができました。
秘密を分散させたので秘密を含む直線を消します。
Step3.秘密を消去する
この分散値を3人で保持しておきます。
次に3個の分散値から元のMを復号します。
3個の分散値から2つを集め、2点を通る直線を引くと元の直線を復元することができます。
多項式の補間にはラグランジュ補間を用います。
Step4.元の直線を復元する
これで秘密値5を復元することができました。
上図のように3人に分散して2人から復元しようとすると、
1次式の
、
、
を分散値とします。
5人に分散して3人から復元しようすると、
2次式の
、
、
、
、
を分散値とします。
このようにn人に分散して、k人から復元しようとするとk-1次の多項式が必要となります。
仕組みとしては、このように分散値を使って多項式補間をするという単純なものになっています。
では、早速コーディングに移っていきたいと思います！
3. sssの実装
今回の実装では、秘密値を複数の分散値に分割するSplitと、複数の分散値からある一定(閾値)の分散値を集めると復元できるCombineの2つの処理が主な実装となってきます。
実装を進めるにあたってこちらを参考にさせていただきました。
- Divide and Manage Secret Data Securely With Shamir’s Secret Sharing
- Shamir’s Secret Sharing | Wikipedia
- github.com/codahale/sss
3.1. 秘密の分割(Split)
func Split(n, k byte, secret []byte) (map[byte][]byte, error) {
if k <= 1 {
return nil, ErrInvalidThreshold
}
if n < k {
return nil, ErrInvalidCount
}
shares := make(map[byte][]byte, n)
for _, b := range secret {
p, err := GenPoly(k, b, rand.Reader)
if err != nil {
return nil, err
}
for x := byte(1); x <= n; x++ {
shares[x] = append(shares[x], CalcPoint(p, x))
}
}
return shares, nil
}
3.1.1. 多項式の生成
まず分散値を計算するための多項式を生成します。 この多項式は定数項がsecretで、各係数はランダムで大丈夫です。 ただし、次数に関しては閾値-1でないと復号することができません。
この関数ではresult配列の先頭に定数項、次に次数の低い係数から順番に格納していきます。
各係数に関しては上述したようにランダムで係数を決めています。
// GenPoly ...
func GenPoly(k byte, secret byte, rand io.Reader) ([]byte, error) {
result := make([]byte, k) // 定数項、係数を格納するための配列
result[0] = secret // 先頭に定数項を格納
buf := make([]byte, k-1) // ランダムな係数を生成するためのバッファ
_, err := io.ReadFull(rand, buf) // バッファを乱数で埋める
if err != nil {
return nil, err
}
// result配列にランダムに決められた係数を格納
for i := byte(1); i < k; i++ {
result[i] = buf[i-1]
}
return result, nil
}
3.1.2. 点を導出
生成した多項式に値を代入しY座標を導出するための関数を作っていきます。
今回はこの多項式の解を求めるにあたって、ホーナー法と呼ばれる計算法を使っています。
(参考 | Github:codahale/sss)
// CalcPoint ...
func CalcPoint(p []byte, x byte) byte {
y := byte(0)
for i := 1; i <= len(p); i++ {
y = gmul(y, x) ^ p[len(p)-i] //ホーナー法
}
return y
}
sssではガロア体上で計算することが求められています。
理由に関しては調べきれなかったので、自分でも調べてみてますがもしご存知の方がいらっしゃいましたらTwitterの方などでお教えいただけると幸いです。
したがってガロア体上で掛け算、割り算をするための関数も定義しました。
func gdiv(a byte, b byte) byte {
for i := byte(0); i <= 0xff; i++ {
if gmul(i, b) == a {
return i
}
}
return 0
}
func gmul(a byte, b byte) byte {
var counter, hi_bit_set byte
p := byte(0)
for counter = 0; counter < 8; counter++ {
if (b & 1) == 1 {
p ^= a
}
hi_bit_set = a & 0x80
a <<= 1
if hi_bit_set == 0x80 {
a ^= 0x1b
}
b >>= 1
}
return p
}
この計算結果をX座標の値ごとに配列に格納します。
3.1.3. 出力してみる
今回は秘密のデータ”Hello, Shamir!“を分割してみます！
閾値は(3,5)に設定してあります。
Input: Hello, Shamir!
Share1:247b7b1250ca0189bd2aa2b1774f
Share2:34aafdf2c04f2528209abcbac286
Share3:58b4ea8cffa904f2f5d17362c7e8
Share4:16019fd8430c2dd831239f2fd783
Share5:7a1f88a67cea0c02e46850f7d2ed
上手く分散することができました。しかし、これが復元できなければ元も子もありません。
次は、この分散値を復元する関数を作っていきたいと思います。
3.2. 分散値の結合(Combine)
func Combine(shares map[byte][]byte) []byte {
var secret []byte
for _, v := range shares {
secret = make([]byte, len(v))
break
}
points := make([]pair, len(shares))
for i := range secret {
p := 0
for k, v := range shares {
points[p] = pair{x: k, y: v[i]}
p++
}
secret[i] = interpolate(points, 0)
}
return secret
}
3.2.1. 点の復元
ここまで見ていただいた方はわかると思うのですが、分散された秘密は平面上の直交座標系の点で表すことができる数値のペアになっています。 先ほど、分割した秘密のShare1はx=1上に配置された点の集合を表しています。 5つに分割された分散値の中から3個を元の座標(map)に戻していきます。
// 与えられたshare
// map[1:[31 195 26 40 94 25 160 95 49 248 245 63 116 116]
// 2:[219 50 221 61 194 121 103 111 44 245 169 229 208 254]
// 3:[140 148 171 121 243 76 231 99 117 108 49 179 214 171]]
for k, v := range shares {
points[p] = pair{x: k, y: v[i]}
p++
}
// 各座標に変換
// [{1 31} {2 219} {3 140}]
// [{1 195} {2 50} {3 148}]
// [{1 26} {2 221} {3 171}]
// more...
3.2.2. ラグランジュ補間
各座標が復元できたら、次に元の多項式を復元します。
多項式の復元に成功したら、その多項式の定数項が秘密情報の1バイト分ということになります。
多項式のの復元に関してはみんな大好きラグランジュ補間を使っていきます。
ラグランジュ補間の関数に関しましては、参考にさせていただいたリポジトリ内の関数をそのまま使わさせていただいています。
// Lagrange interpolation
func interpolate(points []pair, x byte) (value byte) {
for i, a := range points {
weight := byte(1)
for j, b := range points {
if i != j {
top := x ^ b.x
bottom := a.x ^ b.x
factor := div(top, bottom)
weight = mul(weight, factor)
}
}
value = value ^ mul(weight, a.y)
}
return
}
ラグランジュ補間そのものに関しましてはこのサイトで詳しく説明されています！(大学1年の頃にお世話になりました・・・)
(参考 | 補間（ラグランジュの補間公式、ニュートンの補間公式）)
3.2.3. 出力結果
今回は分割された分散値を復元してみます！
今回必要な分散値は3個です。
Share1:b6ac1ee04636380afcc6dac45c8e
Share2:bfcd28e21c580c830df30b17fc6c
Share3:41045a6e354214da9954bcbad2c3
Share4:fdaa52690ddf087be16fed69109b
Share5:036320e524c5102275c85ac43e34
Output: Hello, Shamir!
無事、分割された分散値から復元することができました！
4. まとめ
今回イチからsssを実装してみて、秘密分散の技術って結構単純なロジックなのだなと感じました。 とは言っても「完全に理解した」わけではないので、まだまだ理解の至っていない奥深いところがあるのかもしれません。
また、色々なsssの実装例を見ていて感じたのですが、各々プログラムによって分散値の形式が違ったり、多項式の生成方法が違っていたので、こういう形式の選定によっても秘匿性などが変わってくるのかなと思い、面白かったです。
大学一年生の頃に習ったラグランジュ補間も当時は「何に使うんやこんなの」と思っていましたが、実際に使ってみて、あの勉強も無駄じゃなかったんだなと再確認することができました。
暗号やっぱり面白い！！！！と改めて感じることができました(๑╹ω╹๑ )
最後まで読んで頂きましてありがとうございました！
Twitter(@nandehu0323)もやっておりますのでぜひご感想やアドバイスお待ちしております！
5. Tip us!
エンジニアチームのブログを書くモチベーションが上がります 💪
0xd6d478dCe4585a394834690158cf83581223C08f
6. 参考文献
Gincoでは、ブロックチェーンやFirebaseなどの最新技術をガンガン使ったサービスを作りたいエンジニアを募集しています。
「ブロックチェーンの開発をガッツリ行いたい」
「普通のWebサービスは飽きた。もっと気合の入る開発がしたい」
といった方、お気軽なご応募お待ちしております。
Author 南条 宏貴
LastMod 2018-12-24