前言

站长最初接触到秘密共享，是清华树洞为实现匿名性与身份验证相平衡所采用的密钥分发方案Shamir（见：第三代树洞加密算法概述）。其中，每个人不掌握完整私钥，只有$K$个人将密钥聚合在一起的时，才能构造出完整私钥。后续搜索了下相关文章，才知道此类方案已有定义，叫门限方案。

现在回想起来，其实颇有戏剧性，因为这算是最初激发我希望从事隐私计算工作的引子。不过，最后并未如愿。毕业后跨了几次行，多是在后台开发的领域搬砖。即使目前做的是半个FinTech（金融风控）的工作，涉及到的隐私数据也多是监管要求下的「数据脱敏」而非「隐私计算」。

所以，这更多是一篇抱着学习心态写的文章，希望重新学习并分享一下个人对常见门限方案的理解，同时介绍下站长如何使用Shamir算法备份敏感信息（密码库及密钥文件）。后续如有时间，或会再学习分享一下Feldman算法等等。

个人应用场景

门限方案用途很广，在MPC（安全多方计算）领域中可视作「基石」的一部分，并不只能拿来构建所谓匿名论坛。

例如，在加密货币中，为实现更好的兼容性、更小的开销及更高的安全性，MPC钱包是比较常见的。早年，「火币」「币安」「欧易」还比较火热、出入金及虚拟卡服务还不太发达、meme币发行还没那么夸张的时候，站长也在各种链上注册过各路钱包。现在，站长退出「币圈」许久，MPC钱包什么的自然也用不上了。

但于我而言，门限方案还有一个用途：安全地拆分加密密钥，并将各个加密密钥碎片存储到不可信的云服务商中。

如果选择类似Bitwarden、1Password、iCloud钥匙串等在线密码管理器，基本不会遇到这类场景。不过出于个人喜好，站长通常选用离线软件管理密码；同时，为保障密码库不丢失，会将密码库（以及可选的密钥文件）存储到云服务商中进行备份。

经对比，站长最终选择了KeePassXC对各项密码进行离线管理。KeePassXC是一个允许通过主密码、文件等方式安全存储敏感信息的软件。其使用方式，大致可分为以下两种：

• 方案一：仅使用密码进行密码库的加密与解密。 若密码强度低，恶意的云服务商能轻易地解开密码库文件，造成敏感数据的泄露。特别的，当密码含有个人信息，且云服务商收集持有这些个人信息时，密码库的暴力破解难度将大大下降。为规避这点，可使用随机密码。但记忆一个随机密码用于加解密密码库，于我而言极其依靠熟练度。一段时间不输入密码，可能这个密码将遗失，再不记得导致数据丢失（当然，也可以通过打印密码，降低密码丢失而无法解密的风险）。

• 方案二：利用KeePassXC自带的密钥生成器生成的文件密钥配合密码加密密码库文件。 这需要审慎把握存放密码库文件与密钥文件的云服务商。其一，要保障密钥文件和密码库文件不能放在同一云服务中，否则独立的密钥文件将毫无意义；其二，要保障在极端情况下，仍具有对密码库与密钥文件的访问权限。

方案二在提高了安全性的同时，也引入了新的风险。实践中，可能会因为二步验证器硬件损坏，二步验证密钥意外灭失，手机/电脑丢失损坏等原因，丢失某一云服务商的文件访问权限，导致密码库、密钥文件中的某一个无法被访问，使得密码库无法解密。可以通过多云存放（例如：腾讯云对象存储、微软Onedrive、坚果云存放密码库文件，阿里云对象存储、Amazon对象存储存放密钥文件）来降低风险。但从可访问性角度看，用于存储密码库/密钥文件的云服务商需支持通过手机验证码等与实人强关联的方式登录，或选用难以忘记的的密码和不易灭失的二步验证方式。

为了减少管理的心力，灵活调整风险，还可以利用门限方案微调方案二得到方案三：在每个云服务商中都存储密码库文件，且同时存储由门限方案拆分后得到的密钥文件“碎片”（或者称其为“份额”、“信息片”）。此时，只需持有$K$个云服务商的访问权限就能还原出密钥文件。好处有：（一）无须费心费力考虑密钥文件和密码库该如何存放；（二）有效避免恶意或不安全的云服务商导致的敏感信息泄露；（三）有效降低了密码库文件无法访问的风险（密钥可打印离线存放，但密码库太大了不行），并可通过调整$K$值来灵活调整密钥文件的风险值。例如，当$K=2$时，丢失文件导致无法解密的风险相比方案二要低。此时持有任意两个云服务商的访问权限，都可得到完整的密钥文件与密码库文件。目前我正在测试使用的就是方案三，通过Openlist挂载云服务商存储服务，并通过NAS统一进行同步和备份。具体实现路径如下：

相关算法

常见的秘密共享算法有基于多项式的Shamir算法、基于多维欧几里得空间的Blakley算法、基于中国剩余定理的Asmuth-Bloom算法、基于矩阵乘法的Karnin-Greene Hellman算法等。其中Shamir算法最成熟、用途最广，后续基于验证等实际需求衍生出Feldman算法、Benaloh算法等改进方案。本文将选取其中一部分进行介绍。

Shamir 算法

• Adi Shamir. 1979. How to share a secret. Commun. ACM 22, 11 (Nov. 1979), 612–613. https://doi.org/10.1145/359168.359176

构造方式与还原

核心：对于$n$个点$(x_i, y_i)$，若满足$\forall i \neq j, x_i \neq x_j$，则经过这$n$个点可唯一确定一个$n-1$次多项式$p(x)$。（注：满足插值条件的多项式$p(x)$存在且唯一）

构造：采用拉格朗日插值法。设$l_k(x)$是$n$次多项式，且在插值节点$x_0,x_1,…,x_n$上满足：

$$ l_k(x_i)= \begin{cases} 1, \ i = k \\ 0, \ i \neq k \end{cases} \quad i,k=0,1,2,…,n $$

则称$l_k(x)$为节点$x_0,x_1,…,x_n$上的$n$次拉格朗日基函数，此时插值多项式$p(x)$可写成$p(x)=a_0l_0(x)+a_1l_1(x)+…+a_nl_n(x)$，将插值条件$p(x_i)=y_i$代入即得到$a_i=y_i, i=0,1,2,…,n$。

由此，即可构造拉格朗日插值多项式$L_n(x) = \sum_{k=0}^{n}y_k l_k(x) = \sum_{k=0}^{n}y_k\prod_{i = 0, i \neq k}^{n} \frac{x-x_i}{x_k-x_i}$

回到秘密共享场景：设现有一个$(t, w)$门限方案，所需共享的秘密记为$K$。以此构造多项式：$S(x) = K + a_1x + a_2x^2 + … + a_{t - 1}x^{t - 1}$。而后，随机取$w$个不同的正整数{$x_1, x_2, …, x_w$}并随机取一个大素数$p(p > n + 1)$，将$(x_i, S(x_i) \ mod \ p)$发送给第$i$个持有者，即完成秘密分割。

如需还原分割后的秘密，则需至少$t$个参与者将分割的$(x_i, S(x_i) \ mod \ p)$通过拉格朗日插值还原函数$S(x)$。此时只需求解$(0, S(0))$，就能复原得到秘密$K$。

提升方案

• P. Feldman, “A practical scheme for non-interactive verifiable secret sharing,” 28th Annual Symposium on Foundations of Computer Science (sfcs 1987), Los Angeles, CA, USA, 1987, pp. 427-438, doi: 10.1109/SFCS.1987.4.

• J. C. Benaloh, “Secret Sharing Homomorphisms: Keeping Shares of a Secret Secret,” Advances in Cryptology—6th Annual International Cryptology Conference (CRYPTO ‘86), Santa Barbara, 17-21 August 1987, pp. 251-260.

Shamir假定所有参与者都是善意的，不含验证功能。后发布的Feldman算法、Benaloh算法，主要就是从可验证性上优化Shamir及相关算法。知名交易所币安中的BNB-Chain，采用的就为Feldman算法，这里仅摘取部分代码作前文对Shamir算法描述的补充。如有兴趣，完整实现可见bnb-chain/tss-lib/crypto/vss/feldman_vss.go。

 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

// Check share ids of Shamir's Secret Sharing, return error if duplicate or 0 value found
func CheckIndexes(ec elliptic.Curve, indexes []*big.Int) ([]*big.Int, error) {
    visited := make(map[string]struct{})
    for _, v := range indexes {
        vMod := new(big.Int).Mod(v, ec.Params().N)
        if vMod.Cmp(zero) == 0 {
            return nil, errors.New("party index should not be 0")
        }
        vModStr := vMod.String()
        if _, ok := visited[vModStr]; ok {
            return nil, fmt.Errorf("duplicate indexes %s", vModStr)
        }
        visited[vModStr] = struct{}{}
    }
    return indexes, nil
}

// Returns a new array of secret shares created by Shamir's Secret Sharing Algorithm,
// requiring a minimum number of shares to recreate, of length shares, from the input secret
func Create(ec elliptic.Curve, threshold int, secret *big.Int, indexes []*big.Int, rand io.Reader) (Vs, Shares, error) {
    if secret == nil || indexes == nil {
        return nil, nil, fmt.Errorf("vss secret or indexes == nil: %v %v", secret, indexes)
    }
    if threshold < 1 {
        return nil, nil, errors.New("vss threshold < 1")
    }

    ids, err := CheckIndexes(ec, indexes)
    if err != nil {
        return nil, nil, err
    }

    num := len(indexes)
    if num < threshold {
        return nil, nil, ErrNumSharesBelowThreshold
    }

    poly := samplePolynomial(ec, threshold, secret, rand)

    v := make(Vs, len(poly))
    for i, ai := range poly {
        v[i] = crypto.ScalarBaseMult(ec, ai)
    }

    shares := make(Shares, num)
    for i := 0; i < num; i++ {
        share := evaluatePolynomial(ec, threshold, poly, ids[i])
        shares[i] = &Share{Threshold: threshold, ID: ids[i], Share: share}
    }
    return v, shares, nil
}

func samplePolynomial(ec elliptic.Curve, threshold int, secret *big.Int, rand io.Reader) []*big.Int {
    q := ec.Params().N
    v := make([]*big.Int, threshold+1)
    v[0] = secret
    for i := 1; i <= threshold; i++ {
        ai := common.GetRandomPositiveInt(rand, q)
        v[i] = ai
    }
    return v
}

// Evauluates a polynomial with coefficients such that:
// evaluatePolynomial([a, b, c, d], x):
//
//    returns a + bx + cx^2 + dx^3
func evaluatePolynomial(ec elliptic.Curve, threshold int, v []*big.Int, id *big.Int) (result *big.Int) {
    q := ec.Params().N
    modQ := common.ModInt(q)
    result = new(big.Int).Set(v[0])
    X := big.NewInt(int64(1))
    for i := 1; i <= threshold; i++ {
        ai := v[i]
        X = modQ.Mul(X, id)
        aiXi := new(big.Int).Mul(ai, X)
        result = modQ.Add(result, aiXi)
    }
    return
}

Asmuth-Bloom 算法

• C. Asmuth and J. Bloom, “A modular approach to key safeguarding,” in IEEE Transactions on Information Theory, vol. 29, no. 2, pp. 208-210, March 1983, doi: 10.1109/TIT.1983.1056651.

准备工作

设现有一个$(t, w)$门限方案。

选取素数$p$以及$w$个两两互质的正整数（记为：$m_1,m_2,…,m_w$），并在$Z_p$中选取需分割的秘密$K$。所涉及元素还需满足以下条件：

• $K < p$

• $m_1 < m_2 < … < m_w$

• $\forall_{i=1}^{w} \ gcd(p, m_i) = 1$

• $\prod_{i=1}^{t} m_i > p \prod_{i=1}^{t-1} m_{w-i+1}$

设$M=\prod_{i=1}^{t} m_i$，即有$M > p \prod_{i=1}^{t-1} m_{w-i+1}$，易得$\frac{M}{p}$大于${m_1,m_2,…,m_w}$中任意$t-1$个数的乘积。

而后，在区间$[0, \frac{M}{p} - 1]$内取一随机整数$r$，有$r < \frac{M}{p} - 1$。由此，构造辅助值$K^{\prime} = K + r \cdot p$，可得$K^{\prime} = K + r \cdot p < (1 + r) p < M$，此时$K^{\prime} = K + r \cdot p \in Z_M$。

秘密分割

下面将分割后的秘密记为信息片。由如下同余方程，可通过$K^{\prime}, p,${$m_1,m_2,…m_w$}=构造$w$个信息片（记为：$k_1,k_2,…,k_w$）。

$$ \begin{cases} k_1 \equiv K^{\prime} \ (mod \ m_1) \\ k_2 \equiv K^{\prime} \ (mod \ m_2) \\ … \\ k_w \equiv K^{\prime} \ (mod \ m_w) \end{cases} $$

秘密复原

假定当前已拥有$t$个信息片（其对应编号记为：$j_1, j_2, …, j_t$；对应信息片记为：$k_{j_1}, k_{j_2}, …, k_{j_t}$），可得如下同余方程组：

$$ \begin{cases} K^{\prime} \equiv k_{j_1} \ (mod \ m_{j_1}) \\ K^{\prime} \equiv k_{j_2} \ (mod \ m_{j_2}) \\ … \\ K^{\prime} \equiv k_{j_t} \ (mod \ m_{j_t}) \end{cases} $$

即可通过中国剩余定理解出$K^{\prime}$在模$M^{\prime}=\prod_{i=1}^{t} M_{j_i}$下的最小正剩余$a^{\prime}$，即有$K^{\prime} \equiv a (mod \ M^{\prime})$。又因为$K^{\prime} \in Z_M$，有$0 \leq K^{\prime}< M \leq M^{\prime}$，可唯一确定$K^{\prime} = a^{\prime}$，进而可通过$K = K^{\prime} - r \cdot p$复原得到秘密$K$。

假定当前仅拥有$t-1$个信息片（其对应编号记为：$j_1, j_2, …, j_{t - 1}$；对应信息片记为：$k_{j_1}, k_{j_2}, …, k_{j_{t-1}}$）。要证明其无法得到秘密，需证明其无法获得关于原始秘密的任何信息。

首先，基于$t-1$个信息片，同样可解得模$M^{\prime\prime}=\prod_{i=1}^{t-1} m_{i}$下的最小正剩余$a^{\prime\prime}$。又因$\prod_{i=1}^{t} m_i > p \prod_{i=1}^{t-1} m_{w-i+1}$，可知$p < \frac{\prod_{i=1}^{t} m_i}{\prod_{i=1}^{t-1} m_{w-i+1}} = \frac{M}{\prod_{i=1}^{t-1} m_{w-i+1}} \leq \frac{M}{M^{\prime\prime}}$。

此时可设$K^{\prime} = a^{\prime\prime} + cM^{\prime\prime}$。由于$gcd(p, M^{\prime\prime}) = 1$，当枚举$c$以对$K^{\prime}$进行枚举时，所得到的值将会均匀地、循环地覆盖$Z_{p}$中所有$p$个可能的秘密候选值（限定范围后，同余类间元素个数最多相差$1$）。

此外，由于$0 \leq K^{\prime}< M$，可得$0 \leq c < \frac{M}{M^{\prime\prime}}$（未对$M$取模情况下），即$K^{\prime}$至少有$\lceil \frac{M}{M^{\prime\prime}} \rceil$个候选解。又因为$p < \frac{M}{M^{\prime\prime}}$，可得任一$Z_{p}$中的秘密$K$的候选值，均能对应上至少一个候选解。

实践中，可认为以上原始版本的Asmuth-Bloom算法在绝大多数情况下是安全的。少数情况下，可能因概率分布不均匀，而存在极少数信息的泄露。这一情形可通过严格选择参数或改变构造条件（例如：将原构造条件改为$\prod_{i=1}^{t} m_i > p^2 \prod_{i=1}^{t-1} m_{w-i+1}$）等方式规避，且攻击利用难度很高，现未见实操性强的攻击方式。

尾声

本文主要从站长自身需求出发，讨论了如何安全地备份存储密码库，并借此讨论了Shamir、Asmuth-Bloom等算法的实现和部分证明过程。如有表述不当之处，还请读者朋友们指出，谢谢！

（其实这是去年7月29号建的文章草稿，最近忽然发现，重新水一下つ﹏⊂）