こんにちは、なんぞーです！
現在大学で、情報セキュリティを専攻しているのですが、その講義内でブロックチェーン界隈でも注目されている秘密分散法について学んだので今回は Golang で実装してみたいと思います！

あくまでも、仕組みを理解するためのコーディングなので、処理速度などは考慮せずに進めていきたいと思います。
コードや内容についてのご指摘やアドバイスなどは Twitter(@nandehu0323)にいただけると非常にありがたいです！

秘密分散法

秘密分散(秘密分割)とは一定の参加者で秘密を分散する方法で、参加者にはそれぞれ秘密を分散したカケラ(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 氏が発表した方式です。

Shamir’s Secret Sharing

まずは簡単に理解するために、Shamir(2,3)閾値秘密分散法を図を使って説明しようと思います！
秘密を 3 個に分割し、そのうちの分割値 2 個から復号します。

はじめに Y 軸との交点が M、傾きが R の直線をグラフ上に引きます。
ここでの M は秘密値を示します。今回は R を 3、M を 5 として考えていくものとします。

次に秘密を 3 個に分割、つまり直線上から 3 個の点を求めます。

これで秘密値を 3 個の分散値に分散させることができました。
秘密を分散させたので秘密を含む直線を消します。

この分散値を 3 人で保持しておきます。 次に 3 個の分散値から元の M を復号します。
3 個の分散値から 2 つを集め、2 点を通る直線を引くと元の直線を復元することができます。
多項式の補間にはラグランジュ補間を用います。

これで秘密値 5 を復元することができました。

上図のように 3 人に分散して 2 人から復元しようとすると、
1 次式の、、 を分散値とします。
5 人に分散して 3 人から復元しようすると、
2 次式の、、、、 を分散値とします。
このように n 人に分散して、k 人から復元しようとすると k-1 次の多項式が必要となります。

仕組みとしては、このように分散値を使って多項式補間をするという単純なものになっています。
では、早速コーディングに移っていきたいと思います！

sss の実装

今回の実装では、秘密値を複数の分散値に分割する Split と、複数の分散値からある一定(閾値)の分散値を集めると復元できる Combine の 2 つの処理が主な実装となってきます。

実装を進めるにあたってこちらを参考にさせていただきました。

• Divide and Manage Secret Data Securely With Shamir’s Secret Sharing
  
• Shamir’s Secret Sharing | Wikipedia
  
• github.com/codahale/sss

秘密の分割(Split)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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
}

多項式の生成

まず分散値を計算するための多項式を生成します。 この多項式は定数項が secret で、各係数はランダムで大丈夫です。 ただし、次数に関しては閾値-1 でないと復号することができません。

この関数では result 配列の先頭に定数項、次に次数の低い係数から順番に格納していきます。
各係数に関しては上述したようにランダムで係数を決めています。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

// 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
}

点を導出

生成した多項式に値を代入し Y 座標を導出するための関数を作っていきます 。
今回はこの多項式の解を求めるにあたって、ホーナー法と呼ばれる計算法を使っています。
(参考 | Github:codahale/sss)

1
2
3
4
5
6
7
8

// 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 の方などでお教えいただけると幸いです。
したがってガロア体上で掛け算、割り算をするための関数も定義しました。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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 座標の値ごとに  配列に格納します。

出力してみる

今回は秘密のデータ”Hello, Shamir!“を分割してみます！
閾値は(3,5)に設定してあります。

1
2
3
4
5
6

 Input: Hello, Shamir!
Share1:247b7b1250ca0189bd2aa2b1774f
Share2:34aafdf2c04f2528209abcbac286
Share3:58b4ea8cffa904f2f5d17362c7e8
Share4:16019fd8430c2dd831239f2fd783
Share5:7a1f88a67cea0c02e46850f7d2ed

上手く分散することができました。しかし、これが復元できなければ元も子もありません。
次は、この分散値を復元する関数を作っていきたいと思います。

分散値の結合(Combine)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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
}

点の復元

ここまで見ていただいた方はわかると思うのですが、 分散された秘密は平面上の直交座標系の点で表すことができる数値のペアになっています。 先ほど、分割した秘密の Share1 は x=1 上に配置された点の集合を表しています。 5 つに分割された分散値の中から 3 個を元の座標(map)に戻していきます。

1
2
3
4
5
6
7
8
9
10
11
12
13

// 与えられた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...

ラグランジュ補間

各座標が復元できたら、次に元の多項式を復元します。 多項式の復元に成功したら、その多項式の定数項が秘密情報の 1 バイト分ということになります。
多項式のの復元に関してはみんな大好きラグランジュ補間を使っていきます。
ラグランジュ補間の関数に関しましては、参考にさせていただいたリポジトリ内の関数をそのまま使わさせていただいています。

(参考 | Github:codahale/sss)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

// 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 個です。

1
2
3
4
5
6

Share1:b6ac1ee04636380afcc6dac45c8e
Share2:bfcd28e21c580c830df30b17fc6c
Share3:41045a6e354214da9954bcbad2c3
Share4:fdaa52690ddf087be16fed69109b
Share5:036320e524c5102275c85ac43e34
Output: Hello, Shamir!

無事、分割された分散値から復元することができました！

まとめ

今回イチから sss を実装してみて、秘密分散の技術って結構単純なロジックなのだなと感じました。 とは言っても「完全に理解した」わけではないので、まだまだ理解の至っていない奥深いところがあるのかもしれません。

また、色々な sss の実装例を見ていて感じたのですが、各々プログラムによって分散値の形式が違ったり、多項式の生成方法が違っていたので、こういう形式の選定によっても秘匿性などが変わってくるのかなと思い、面白かったです。

大学一年生の頃に習ったラグランジュ補間も当時は「何に使うんやこんなの」と思っていましたが、実際に使ってみて、あの勉強も無駄じゃなかったんだなと再確認することができました。

暗号やっぱり面白い！！！！と改めて感じることができました(๑╹ω╹๑ )

最後まで読んで頂きましてありがとうございました！

Twitter(@nandehu0323)もやっておりますのでぜひご感想やアドバイスお待ちしております！

参考文献

• http://kimh.github.io/blog/en/security/protect-your-secret-key-with-shamirs-secret-sharing/
• https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing
• https://github.com/codahale/sss