沙米尔的秘密共享算法 | 密码学

密码学是一种通过使用密码来保护信息和通信安全的技术。只有那些被这些信息所针对的人才能理解和处理这些信息，从而防止未经授权的人员获取这些信息。前缀“crypt”意为“隐藏”，后缀“graphy”则意为“书写”。在本文中，我们将讨论一种密码学技术——Shamir的秘密共享算法。
沙米尔的秘密共享算法：Shamir的秘密共享算法是由Adi Shamir在密码学领域提出的。该算法的核心思想是将需要加密的秘密信息分解为多个独特的部分。
 

• 假设吧S这就是我们想要隐藏的秘密。
• 它被划分为 N 个部分：S1、S2、S3、……、Sn。
• 在将其分割之后，得到的数字就是……K用户可以选择这个选项，以便解密那些部分信息，从而找到原始的秘密。
• 它的选择方式是这样的：如果我们所知道的部件数量少于K个，那么我们就无法找回秘密的S。换句话说，秘密的S是无法用(K-1)个或更少的部件来重建的。
• 如果我们知道的话K如果我们有S1、S2、S3……Sn中的任意多个部分，那么我们就可以轻松地计算出或重建出我们的秘密代码S。这种方案通常被称为(K, N)阈值方案。

接近方式：Shamir的秘密共享算法背后的核心思想在于：对于给定的K个点，我们可以找到一个次数为(K-1)的多项式方程。
示例： 
 

• 对于给定的两个点，(x1, y1)和(x2, y2)，我们可以找到一个线性多项式。ax + by = c.
• 同样地，对于给定的三个点，我们也可以找到一个二次多项式。ax² + bx + cy = d.

所以，我们的想法是构造一个多项式，其次数等于所需的值。(K - 1)也就是说，常数项就是那个秘密代码，而其余的数字都是随机生成的。这个常数项可以通过使用从这个多项式中生成的 N 个点中的任意 K 个点，再结合拉格朗日基多项式的方法来求得。
例如：令秘密密钥为 S = 65，N = 4，K = 2。
 

1. 最初，为了对秘密代码进行加密，我们需要构造一个次数为(K-1)的多项式。
2. 因此，让这个多项式为：y = a + bx在这里，那个常数部分“a”其实就是我们所说的“秘密代码”。
3. 设 b 为任意随机数，比如 b = 15。
4. 因此，对于这个多项式 y = 65 + 15x，我们从中生成了4个点。
5. 让那4个点的坐标分别为：(1, 80)、(2, 95)、(3, 110)、(4, 125)。显然，我们可以从这4个点中的任意两点来构造出初始多项式。在得到的多项式中，常数项a就代表了所需的秘密代码。

为了重新构造给定的多项式，需要使用拉格朗日基多项式。
拉格朗日多项式的核心思想是先构造出拉格朗日恒等式，然后对这些恒等式进行求和，最终得到我们需要的函数。下面这些方程展示了如何计算这些函数：
 

例如，假设我们希望利用所选的四个点中的两个点来计算给定的方程。这四个点是：(1, 80)，(3, 110)。下图展示了如何一步步地完成这个计算过程。
 

以下是上述方法的实现过程：
 

// 这是Shamir算法的C++实现方式// 秘密共享算法#include<bits/stdc++.h>使用命名空间标准;// 用于计算数值的函数// 或者…// y = poly[0] + x * poly[1] + x^2 * poly[2] + …整数计算_Y(整数x,向量<整数>&多聚体){// 初始化 y 的值整数y=0;整数温度=1;// 遍历数组中的元素为了(汽车/车辆系数:多聚体){// 计算 y 的值y=(y+(系数*温度));温度=(温度*x);}返回y;}// 用于执行该秘密操作的函数// 共享算法并对其进行编码处理// 给定的秘密密钥无效/无意义秘密共享(整数S,向量<一对<整数,整数>>&点数/分数,整数N,整数K){// 一个用于存储多项式的向量// K-1阶的系数向量<整数>多聚体(K);// 随机选取 K-1个数字，但是……// 不是零，而且 poly[0] 就是那个秘密值// 为这个创建多项式多聚体[0]=S;为了(整数j=1;j<K;++j){整数p=0;而(p==0)// 为了保持随机值的有效性// 范围不要太高// 我们正在对模数进行运算。// 在1000左右的范围内，质数的数量p=(随机数()%997);// 这样做是为了确保我们没有犯下错误。// 创建一个多项式// 全是零。多聚体[j]=p;}// 从…中生成N个点// 我们创建的多项式为了(整数j=1;j<=N;++j){整数x=j;整数y=计算_Y(x,多聚体);// 分享时所获得的积分点数/指标[j-1]={x,y};}}// 该结构用于处理分数。// 处理乘法运算的部分// 以及分数的相加结构体小数{整数数字/数值,den;// 一个分数由以下部分组成：// 分子和分母小数(整数n,整数d){数字/数值=n,den=d;}// 如果该分数不符合要求的话// 以简化形式表示// 通过除法来将其减少// 与他们一起使用他们的GCD无效/无意义减少小数部分(小数&f){整数GCD=__gcd(f.数字/数值,f.den);f.数字/数值/=gcd,f.den/=GCD;}// 对数据进行乘法运算// 分数小数操作员*(小数f){小数温度(数字/数值*f.数字/数值,den*f.den);减少小数部分(温度);返回温度;}// 对数据进行加法运算// 分数小数操作员+(小数f){小数温度(数字/数值*f.den+den*f.数字/数值,den*f.den);减少分数(温度);返回温度;}};// 用于生成秘密密钥的函数// 从给定的点返回// 该函数将使用拉格朗日基多项式来表示函数的值。// 与其寻找完整的多项式，不如……// 我们只需要使用 poly[0]作为我们的秘密代码即可。// 因此，我们可以消除与x相关的项。整数生成秘密密钥(整数x[]整数y[]整数M){小数ans(0,1);// 循环以遍历给定的内容// 点数为了(整数i=0;i<M;++i){// 初始化分数小数l(y[i],1);为了(整数j=0;j<M;++j){// 计算拉格朗日项if(i!=j){小数温度(-x[j],x[i]-x[j]);l=l*温度;}}ans=ans+l;}// 返回秘密信息返回ans.数字/数值;}// 用于编码和解码数据的函数// 使用上述方法获取了秘密密钥// 定义的函数无效/无意义操作/运作(整数S,整数N,整数K){// 用于存储这些点的向量向量<配对/一对<整数,整数>>点数/指标(N);// 将秘密代码分成N个部分进行共享秘密共享(S,点数/指标,N,K);cout<<“秘密”被分为几部分/类别<<N<<部件——<<结束;为了(整数i=0;i<N;++i){cout<<点数/分数[i].首先<<“ ”<<点数/指标[i].第二<<结束;}cout<<我们可以从任何来源获取“Secret”。<<K<<“零件”<<结束;// 请输入任意M个点。// 为了获取我们的秘密代码。整数M=2;// M可以大于或等于阈值，但是// 在这个示例中，我们使用的阈值是if(M<K){cout<<得分低于阈值。<<K<<“所需积分”<<结束;}整数*x=新的整数[M];整数*y=新的整数[M];// 输入M个点，你就能得到那个“秘密”了。// 让这些点先是从前M个点中选取的。// 我们上面所共享的N个点// 我们可以选择任意数量的M个点。为了(整数i=0;i<M;++i){x[i]=点数/分数[i].首先;y[i]=点数/分数[i].第二;}// 再次获取我们的结果。cout<<我们的“秘密密码”是：<<生成/创造