当前位置:网站首页>秘密共享方案介绍SS
秘密共享方案介绍SS
2022-08-10 15:58:00 【糖葫芦零零七】
概念
问题1:保险柜中存放有10个人的共有财产,要从保险柜中取出物品,必须有半数以上的人在场才可取出,半数以下则不行。如何构造锁的设计方案?
问题2:导弹的发射控制、重要安保场所的通行检验,通常需要多人同时参与才能生效。因此,需要将秘密分给多人掌管,并且由一定掌管秘密的人数同时到场才能恢复秘密。方案如何设计?
这里我们就需要提出秘密共享的概念。
秘密共享的思想是将秘密进行分割,并把秘密在 n n n个参与者中分享,使得只有多于特定 t t t个参与者合作才可以计算出或恢复出秘密,而少于 t t t个参与者则不可以得到有关秘密。
秘密共享的关键是怎样更好的设计 秘密拆分方式
和 恢复方式
。
秘密共享是一种将秘密分割存储的密码技术,目的是阻止秘密过于集中,以达到分散风险和容忍入侵的目的,是信息安全和数据保密中的重要手段。
注意:
- 在对秘密进行拆分,拆分的方式不一定均匀。
- t t t一定是小于等于 n n n的。
Shamir秘密共享方案
一般的,设 { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . . . . , ( x k , y k ) } \{(x_1, y_1), (x_2, y_2),......, (x_k, y_k)\} {(x1,y1),(x2,y2),......,(xk,yk)}是平面上 k k k个不同的点构成的点集, 那么在平面上存在唯一的 k − 1 k-1 k−1次多项式 f ( x ) = a 0 + a 1 x + a 2 x 2 + . . . . . + a k − 1 x k − 1 f(x) = a_0 + a_1x + a_2x^2 +..... + a_{k-1}x^{k-1} f(x)=a0+a1x+a2x2+.....+ak−1xk−1通过这 k k k个点。
若把秘密 s s s取做 f ( 0 ) f(0) f(0), n n n个份额取做 f ( i ) ( i = 1 , 2 , . . . . , n ) f(i)(i = 1, 2, ...., n) f(i)(i=1,2,....,n), 那么利用其中任意k个份额可以重构 f ( x ) f(x) f(x), 从而可以得到秘密 s s s。
加密
对于待加密的明文 s ∈ Z p s \in Z_p s∈Zp( p p p为大素数且 p > = n + 1 p >= n+1 p>=n+1),在有限群 G F ( p ) GF(p) GF(p)任取 k − 1 个 k−1个 k−1个随机数 a 1 , a 2 , … , a k − 1 a_1, a_2, …, a_{k-1} a1,a2,…,ak−1并令 a 0 = s a_0=s a0=s,从而构造如下的多项式: f ( x ) = a 0 + a 1 x + a 2 x 2 + a 3 x 3 + . . . . . + a k − 1 x k − 1 m o d ( p ) f(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + ..... + a_{k-1}x^{k-1} mod(p) f(x)=a0+a1x+a2x2+a3x3+.....+ak−1xk−1mod(p) 对于这个多项式, 任取 n n n个数 x 1 , x 2 , x 3 , . . . , x n x_1, x_2, x_3, ..., x_n x1,x2,x3,...,xn分别带入多项式得到 n n n个密钥对 ( x i , y i ) (x_i, y_i) (xi,yi): f ( x ) = a 0 + a 1 x + a 2 x 2 + a 3 x 3 + . . . . . + a k − 1 x k − 1 m o d ( p ) f(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + ..... + a_{k-1}x^{k-1} mod(p) f(x)=a0+a1x+a2x2+a3x3+.....+ak−1xk−1mod(p) 分发给 n n n个持有者 P 1 , P 2 , . . . , P n P_1, P_2, ..., P_n P1,P2,...,Pn。
解密
假设得到了 k k k个密钥对 { x 1 , y 1 } , { x 2 , y 2 } , . . … , { x k , y k } \{x_1, y_1\}, \{x_2, y_2\}, ..…,\{x_k,y_k\} { x1,y1},{ x2,y2},..…,{ xk,yk},我们可以得到如下方程(运算均在 G F ( p ) GF(p) GF(p): a 0 + a 1 x 1 + a 2 x 1 2 + . . . . . . . + a k − 1 x 1 k − 1 = y 1 a_0 + a_1x_1 + a_2x^2_1 + ....... + a_{k-1}x^{k-1}_1 = y_1 a0+a1x1+a2x12+.......+ak−1x1k−1=y1 a 0 + a 1 x 2 + a 2 x 2 2 + . . . . . . . + a k − 1 x 2 k − 1 = y 2 a_0 + a_1x_2 + a_2x^2_2 + ....... + a_{k-1}x^{k-1}_2 = y_2 a0+a1x2+a2x22+.......+ak−1x2k−1=y2 a 0 + a 1 x 3 + a 2 x 3 2 + . . . . . . . + a k − 1 x 3 k − 1 = y 3 a_0 + a_1x_3 + a_2x^2_3 + ....... + a_{k-1}x^{k-1}_3 = y_3 a0+a1x3+a2x32+.......+ak−1x3k−1=y3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ............................................. ............................................. a 0 + a 1 x k + a 2 x k 2 + . . . . . . . + a k − 1 x k k − 1 = y k a_0 + a_1x_k + a_2x^2_k + ....... + a_{k-1}x^{k-1}_k = y_k a0+a1xk+a2xk2+.......+ak−1xkk−1=yk 由Lagrange插值公式: f ( x ) = ∑ i = 1 k f ( x i ) ∏ j = 1 , j ≠ i k x − x j x i − x j ( m o d p ) f(x) = \sum_{i=1}^kf(x_i)\prod_{j=1, j \neq i}^k\frac{x - x_j}{x_i - x_j}(modp) f(x)=i=1∑kf(xi)j=1,j=i∏kxi−xjx−xj(modp) 故 f ( 0 ) = a 0 = s = ( − 1 ) k − 1 ∑ i = 1 k f ( x i ) ∏ j = 1 , j ≠ i k x j x i − x j ( m o d p f(0) = a_0 = s = (-1)^{k-1}\sum_{i=1}^kf(x_i)\prod_{j=1, j \neq i}^k\frac{x_j}{x_i - x_j}(modp f(0)=a0=s=(−1)k−1i=1∑kf(xi)j=1,j=i∏kxi−xjxj(modp 可求的 a 0 a_0 a0即为明文 s s s。
示例: ( 3 , 5 ) (3, 5) (3,5)门限方案
设 k = 3 , n = 5 , p = 19 , s = 11 , G F ( 19 ) = { 0 , 1 , 2 , 3 , 4 , . . . . , 18 } k = 3, n = 5, p = 19, s = 11, GF(19) = \{0, 1, 2, 3, 4, ...., 18\} k=3,n=5,p=19,s=11,GF(19)={ 0,1,2,3,4,....,18}, 随机选择系数 a 1 = 2 , a 2 = 7 a_1 = 2, a_2 = 7 a1=2,a2=7.
则 f ( x ) = 11 + 2 x + 7 x 2 m o d 19 f(x) = 11 + 2x + 7x^2 mod 19 f(x)=11+2x+7x2mod19.
计算可知: f ( 1 ) = 1 f(1) = 1 f(1)=1 f ( 2 ) = 5 f(2) = 5 f(2)=5 f ( 3 ) = 4 f(3) = 4 f(3)=4 f ( 4 ) = 17 f(4) = 17 f(4)=17 f ( 5 ) = 6 f(5) = 6 f(5)=6
若已知 f ( 2 ) , f ( 3 ) , f ( 5 ) f(2), f(3), f(5) f(2),f(3),f(5), 有拉格朗日插值公式可知:
f ( x ) = 5 ( x − 3 ) ( x − 5 ) ( 2 − 3 ) ( 2 − 5 ) + 4 ( x − 2 ) ( x − 5 ) ( 3 − 2 ) ( 3 − 5 ) + 6 ( x − 2 ) ( x − 3 ) ( 5 − 2 ) ( 5 − 3 ) f(x) = 5\frac{(x-3)(x-5)}{(2-3)(2-5)} + 4\frac{(x-2)(x-5)}{(3-2)(3-5)} + 6\frac{(x-2)(x-3)}{(5-2)(5-3)} f(x)=5(2−3)(2−5)(x−3)(x−5)+4(3−2)(3−5)(x−2)(x−5)+6(5−2)(5−3)(x−2)(x−3) = 11 + 2 x + 7 x 2 = 11 + 2x + 7x^2 =11+2x+7x2 故, s = f ( 0 ) = 11. 故, s = f(0) = 11. 故,s=f(0)=11.
补充
当 k = n k = n k=n的时候,Shamir算法就变成了 ( n , n ) (n, n) (n,n)门限秘密共享。此种方式可以通过 异或运算 进行实现, 具体实现步骤如下:
- 首先将秘密信息转成 01 01 01字符串 s s s。
- 然后随机选取 n − 1 n−1 n−1个与 s s s长度相同的01字符串 s 1 , s 2 , . . . . , s n − 1 s_1, s_2, ...., s_{n-1} s1,s2,....,sn−1, 将 s s s与 s 1 , s 2 , . . . . , s n − 1 s_1, s_2, ...., s_{n-1} s1,s2,....,sn−1进行 异或操作,得到 s n s_n sn。 s n = s ⊕ s 1 ⊕ s 2 ⊕ . . . . . . . . . ⊕ s n − 1 s_n = s \oplus s_1 \oplus s_2 \oplus ......... \oplus s_{n-1} sn=s⊕s1⊕s2⊕.........⊕sn−1然后将 n n n个秘密信息 s 1 , s 2 , . . . . , s n − 1 , s n s_1, s_2, ...., s_{n-1}, s_n s1,s2,....,sn−1,sn分配给 n n n个人, 只有这n个人的时候才能解得秘密信息: s = s 1 ⊕ s 2 ⊕ . . . . . . . ⊕ s n − 1 ⊕ s n s = s_1 \oplus s_2 \oplus ....... \oplus s_{n-1} \oplus s_n s=s1⊕s2⊕.......⊕sn−1⊕sn
网页参考链接
边栏推荐
- 哈希表应用:只出现一次的数字
- 玩转Redis|学会这10点让你分分钟拿下Redis,满足你的一切疑问
- Mobileye joins hands with Krypton to open a new chapter in advanced driver assistance through OTA upgrade
- 秒杀项目收获
- HUAWEI CLOUD DevCloud received the highest-level certification of the first batch of cloud-native technology architecture maturity assessments by the China Academy of Information and Communications Te
- 颜色空间
- Exchange Online审计和监控
- 使用 ABAP 正则表达式解析 uuid 的值
- Methodology of multi-living in different places
- Software Test Cases
猜你喜欢
app自动化测试webview怎么操作
一文带你了解 HONOR Connect
Allwinner V853 development board transplants LVGL-based 2048 games
FP6378AS5CTR SOT-23-5 高效1MHz2A同步降压调节器
如何将jpg静图做成gif动图?教你1分钟快速合成gif
智为链接,慧享生活,荣耀智慧服务,只为 “懂” 你
A test tool for ABAP Development Tool custom service endpoint
Software Test Cases
如何将静图变gif动图?教你jpg合成gif的方法
简述 Mock 接口测试
随机推荐
商业智能BI行业分析思维框架:铅酸蓄电池行业(二)
26、压缩及解压缩命令
2022 CCF中国开源大会会议通知(第四轮)
关于“算力”,这篇文章值得一看
第叁章模块大全之《 os模块》
怎么截取视频做gif动图?手把手教你视频在线转gif制作
NPM - Cannot read properties of null (reading 'pickAlgorithm') 解决方案
数据治理项目成功的要点,企业培养数据要把握好关键环节
拆分整数为2的幂次项和 → 理解多重背包问题二进制优化的核心思想
第壹章模块大全之《re模块》
铜锁密码库
FFmpeg 交叉编译
全志V853开发板移植基于 LVGL 的 2048 小游戏
x64汇编代码测试 用户模式和内核模式
5G NR MIB详解
请查收 2022华为开发者大赛备赛攻略
一个 ABAP 开发的新浪微博语义情感分析工具
PNG如何变gif?教你一招png秒变gif动图的方法
基础填空以及编程题
商业版SSL证书