品牌营销战略_在线制作图片透明背景_青岛网站建设制作推广_百度网盘在线登录入口

加密社

概念

门限秘密共享是一种密码学技术，将秘密 S 分割为 n 个部分，并将这些部分分发给 n 个参与者。所谓门限，是在分割这些秘密的时候，设置一个大小位于 1 和 n 之间的 k 值，使得给定任意 k−1 个或更少的秘密份额，都不能够计算得到秘密 S 的任何信息；当给定任意 k 个或更多的秘密份额的时候，就能够计算得到秘密 S。这被称为 (k,n) 门限秘密共享方案。这意味着这 n 个参与者中最多 k−1 个参与者泄露了他们的秘密份额，秘密 S 仍然是安全的。

举一个直观的案例，如下图：

假设E即为共享秘密，A，B，C，D 四个点分别是一个子密钥，需要任意两个子密钥就能得到真正的结果E。按照图示，我们可以通过两个坐标点位，获得一元一次方程的公式，可以反向推导出最终值E的结果。（当然，上述例子只是一个引子，实际的秘密共享算法并不会如此简单，比如：Shamir秘密共享）

Shamir秘密共享

Shamir 秘密共享（Shamir's Secret Sharing）是一种密码学算法，用于将一个秘密（如密码、密钥等）分割成多个部分（称为份额），并且只有当收集到足够多的份额时，才能恢复该秘密。该算法由以色列密码学家 Adi Shamir 于 1979 年提出，是实现密钥分发和分布式存储的经典方法之一。
Shamir 秘密共享和核心数学原理是拉格朗日插值算法，它使用了一个由多项式生成的函数，其中秘密作为多项式的常数项，而每个份额则是该多项式在不同点上的值。通过至少一定数量的份额可以重建这个多项式。

工作原理

一选择多项式
(x)=S+a1x+a2x^2+⋯+at−1x^t−1。其中S是常数，即要共享的秘密

二生成份额
生成 n 个不同的非零值 x_1, x_2, ..., x_n，并计算对应的 y 值，即 f(x_1), f(x_2), ..., f(x_n)，每个x对应一个份额，并将这些份额分发给不同的参与者

三恢复秘密
至少有 t 个份额时，可以使用拉格朗日插值法重建多项式 f(x)，从而求出常数项 S

C# 算法实现

using System;
using System.Collections.Generic;
using System.Linq;
using System.Security.Cryptography;
using System.Numerics;public class ShamirSecretSharing
{// 分享份额类，包含X和Ypublic class Share{public int X { get; }public BigInteger Y { get; }public Share(int x, BigInteger y){X = x;Y = y;}public override string ToString(){return $"Share{{X={X}, Y={Y}}}";}}private readonly RandomNumberGenerator _random = RandomNumberGenerator.Create();private readonly int _threshold;    // 至少需要的份额数量 tprivate readonly int _numShares;    // 份额总数 nprivate readonly BigInteger _prime; // 大素数，保证结果不溢出public ShamirSecretSharing(int threshold, int numShares, BigInteger prime){_threshold = threshold;_numShares = numShares;_prime = prime;}// 生成秘密的份额public List<Share> Split(BigInteger secret){// 随机生成 (t-1) 个系数BigInteger[] coefficients = new BigInteger[_threshold - 1];for (int i = 0; i < _threshold - 1; i++){coefficients[i] = GenerateRandomBigInteger(_prime);}// 生成 n 个份额List<Share> shares = new List<Share>();for (int i = 1; i <= _numShares; i++){BigInteger x = i;BigInteger y = EvaluatePolynomial(secret, coefficients, x);shares.Add(new Share(i, y));}return shares;}// 恢复秘密public BigInteger Combine(List<Share> shares){BigInteger secret = BigInteger.Zero;for (int i = 0; i < shares.Count; i++){Share si = shares[i];BigInteger numerator = BigInteger.One;BigInteger denominator = BigInteger.One;for (int j = 0; j < shares.Count; j++){if (i != j){Share sj = shares[j];numerator = (numerator * (-sj.X)) % _prime;denominator = (denominator * (si.X - sj.X)) % _prime;}}BigInteger value = (si.Y * numerator * BigInteger.ModPow(denominator, _prime - 2, _prime)) % _prime;secret = (secret + value) % _prime;}return secret;}// 计算多项式的值 y = secret + a1*x + a2*x^2 + ... + at-1*x^(t-1)private BigInteger EvaluatePolynomial(BigInteger secret, BigInteger[] coefficients, BigInteger x){BigInteger result = secret;for (int i = 0; i < coefficients.Length; i++){result = (result + coefficients[i] * BigInteger.ModPow(x, i + 1, _prime)) % _prime;}return result;}// 生成一个介于 0 和 prime 之间的随机 BigIntegerprivate BigInteger GenerateRandomBigInteger(BigInteger prime){byte[] bytes = new byte[prime.ToByteArray().Length];_random.GetBytes(bytes);BigInteger randomValue = new BigInteger(bytes);return randomValue % prime;}public static void Main(string[] args){// 大素数 primeBigInteger prime = BigInteger.Parse("208351617316091241234326746312124448251235562226470491514186331217050270460481");// 假设我们要分享的秘密是 123456789BigInteger secret = BigInteger.Parse("123456789");// 创建 ShamirSecretSharing 实例，阈值为 3，总份额为 5ShamirSecretSharing sss = new ShamirSecretSharing(3, 5, prime);// 生成 5 份份额，至少需要 3 份来恢复秘密List<Share> shares = sss.Split(secret);Console.WriteLine("生成的份额:");foreach (Share share in shares){Console.WriteLine(share);}// 恢复秘密，选取前 3 份List<Share> selectedShares = shares.GetRange(0, 3);BigInteger recoveredSecret = sss.Combine(selectedShares);Console.WriteLine("恢复的秘密: " + recoveredSecret);}
}

代码解析

Share 类:
- Share 是一个内部类，用于表示每个份额，包含两个字段：X 和 Y。X 是份额的标识符，通常是一个正整数；Y 是根据秘密和多项式计算出的值。
ShamirSecretSharing 类:
- 构造函数接受三个参数：threshold（恢复秘密所需的最小份额数）、numShares（总共生成的份额数）和 prime（用于模运算的大素数，以确保数值不会溢出）。
- Split 方法用于将秘密分割成多个份额。它首先随机生成多项式的系数（除了常数项即秘密本身），然后使用这些系数计算每个份额的 Y 值。
- Combine 方法用于从给定的一组份额中恢复原始秘密。它实现了拉格朗日插值法来计算原始的秘密值。
- EvaluatePolynomial 是一个辅助方法，用于计算给定点 X 上多项式的值。这个值将作为份额的 Y 值。
- GenerateRandomBigInteger 是一个辅助方法，用于生成一个介于 0 和 prime 之间的随机 BigInteger。
Main 方法:
- 在 Main 方法中，定义了一个大素数 prime 用于模运算，以及要分享的秘密 secret。
- 创建了一个 ShamirSecretSharing 实例，并指定了阈值为 3，总份额数为 5。
- 使用 Split 方法生成 5 个份额，并打印出来。
- 最后，选择前 3 个份额并调用 Combine 方法来恢复秘密，验证算法的正确性。

注意事项

选择的大素数 prime 必须大于秘密值和所有可能的系数值，以避免模运算中的错误。
为了保证安全性，生成的随机系数应该具有足够的随机性，这里使用了 RandomNumberGenerator 类。
这段代码提供了一个简单的实现，适用于学习和理解 Shamir 的秘密共享算法。在实际部署时，还需要考虑更多的安全性和性能优化措施。