商城网站开发视频教程,玉林网站建设,十款app软件下载入口,如何做教育网站1 简介
作者#xff1a;Shamir时间#xff1a;1979年理念#xff1a;基于多项式插值算法
2 具体实现
I 秘密分割算法 #xff08;1#xff09;选择一个随机素数 ppp#xff0c;并产生一个随机的 t−1t-1t−1 次多项式#xff1b; f(x)at−1xt−1⋯a1xa0modpf(x)a_{t-…1 简介
作者Shamir时间1979年理念基于多项式插值算法
2 具体实现
I 秘密分割算法 1选择一个随机素数 ppp并产生一个随机的 t−1t-1t−1 次多项式 f(x)at−1xt−1⋯a1xa0modpf(x)a_{t-1} x^{t-1}\cdotsa_{1} xa_{0} \bmod p f(x)at−1xt−1⋯a1xa0modp 令a0Sa_0 Sa0SSSS为想要分享的秘密则f(0)a0Sf(0) a_0 Sf(0)a0S。f(x)f(x)f(x)的最高次必须设置为xt−1x^{t-1}xt−1。 2选择 nnn 个互不相同的整数 1≤x1,…,xn≤p−11≤ x_1,…,x_n ≤ p-11≤x1,…,xn≤p−1 3第iii 个参与者计算Sif(xi)S_i f(x_i)Sif(xi)作为其分享的秘密 4销毁f(x)f(x)f(x)。
II 秘密重构算法 1ttt 个参与者拿出自己的秘密消息。假设 S1,…,StS_1, …, S_tS1,…,St 是这 ttt 个秘密分别对应 x1,…,xtx_1, …, x_tx1,…,xt。利用这些信息可以重构出 f(x)f(x)f(x) f(x)∑iSi∏j≠i(x−xj)∏j≠i(xi−xj)modporf(x)∑i1tSi∏j∈{1,2,…,t}∖{i}(x−xj)∏j∈{1,2,…,t}∖{i}(xi−xj)modp\begin{array}{l} f(x) \sum_{i} \frac{S_i \prod_{j \neq i} (x - x_j)}{\prod_{j \neq i} (x_i - x_j)} \bmod p \\ \textrm{or} \\ f(x) \sum_{i1}^t \frac{S_i \prod_{j \in \{1, 2, \dots, t\} \setminus \{i\}} (x - x_j)}{\prod_{j \in \{1, 2, \dots, t\} \setminus \{i\}} (x_i - x_j)} \bmod p\\ \end{array} f(x)∑i∏ji(xi−xj)Si∏ji(x−xj)modporf(x)∑i1t∏j∈{1,2,…,t}∖{i}(xi−xj)Si∏j∈{1,2,…,t}∖{i}(x−xj)modp 令a0Sa_0 Sa0SSSS为想要分享的秘密则f(0)a0Sf(0) a_0 Sf(0)a0S。f(x)f(x)f(x)的最高次必须设置为xt−1x^{t-1}xt−1。 2重构出f(x)f(x)f(x)以后计算Sf(0)S f(0)Sf(0), 多于 ttt个参与者重构f(x)f(x)f(x)的过程也是适用的。
3 实例
设秘密S13S 13S13n5n 5n5, t3t 3t3选择模数p17p 17p17。 I 秘密分割
1生成t−1t - 1t−1个小于等于ppp的随机数a110a_1 10a110a22a_2 2a22a0S13a_0 S 13a0S132分别计算
S1(1310∗12∗12)mod178S2(1310∗22∗22)mod177S3(1310∗32∗32)mod1710S4(1310∗42∗42)mod170S5(1310∗52∗52)mod1711\begin{array}{l} S_{1}\left(1310 * 12 * 1^{2}\right) \bmod 178 \\ S_{2}\left(1310 * 22 * 2^{2}\right) \bmod 177 \\ S_{3}\left(1310 * 32 * 3^{2}\right) \bmod 1710 \\ S_{4}\left(1310 * 42 * 4^{2}\right) \bmod 170 \\ S_{5}\left(1310 * 52 * 5^{2}\right) \bmod 1711 \end{array} S1(1310∗12∗12)mod178S2(1310∗22∗22)mod177S3(1310∗32∗32)mod1710S4(1310∗42∗42)mod170S5(1310∗52∗52)mod1711
3将(Si,i)(S_i, i)(Si,i)作为钥匙分发给第iii个参与者。
II 秘密重构
1收集任意t3t 3t3个参与者的钥匙例如第1个人的(8, 1)第2个人的(7, 2)第5个人的(11, 5)
2列出方程 f(x)∑iSi∏j≠i(x−xj)∏j≠i(xi−xj)modp(8(x−2)(x−5)(1−2)(1−5)7(x−1)(x−5)(2−1)(2−5)11(x−1)(x−2)(5−1)(5−2))mod17\begin{array}{l} f(x) \sum_{i} \frac{S_i \prod_{j \neq i} (x - x_j)}{\prod_{j \neq i} (x_i - x_j)} \bmod p \\ (\frac{8(x - 2)(x-5)}{(1-2)(1-5)} \frac{7(x - 1)(x-5)}{(2-1)(2-5)} \frac{11(x - 1)(x-2)}{(5-1)(5-2)}) \bmod 17 \\ \end{array} f(x)∑i∏ji(xi−xj)Si∏ji(x−xj)modp((1−2)(1−5)8(x−2)(x−5)(2−1)(2−5)7(x−1)(x−5)(5−1)(5−2)11(x−1)(x−2))mod17 计算Sf(0)13S f(0) 13Sf(0)13。
或者列出方程组 a0a1∗(1mod17)a2∗(12mod17)8a0a1∗(2mod17)a2∗(22mod17)7a0a1∗(5mod17)a2∗(52mod17)11\begin{array}{l} a_0 a_1 * (1 \bmod 17) a_2 * (1^2 \bmod 17) 8 \\ a_0 a_1 * (2 \bmod 17) a_2 * (2^2 \bmod 17) 7 \\ a_0 a_1 * (5 \bmod 17) a_2 * (5^2 \bmod 17) 11 \\ \end{array} a0a1∗(1mod17)a2∗(12mod17)8a0a1∗(2mod17)a2∗(22mod17)7a0a1∗(5mod17)a2∗(52mod17)11 求解方程组得到a013,a110,a22a_0 13, a_1 10, a_2 2a013,a110,a22则Sa013S a_0 13Sa013。
4 代码
package com.duwei.crypto;import java.math.BigInteger;
import java.util.Random;/*** BelongsProject: Secure_Aggregation* BelongsPackage: com.duwei.crypto* Author: duwei* Date: 2022/4/28 16:37* Description: Shamir秘密共享方法*/
public class SecretShare {private static BigInteger p;private static Random random;/*** 秘密分享算法** param secret 秘密* param m 系统总用户数* param t 秘密分享的阈值* return m个用户的秘密数组*/public static BigInteger[] share(BigInteger secret, int m, int t) {//储存t - 1次多项系系数BigInteger[] coefficients new BigInteger[t];coefficients[0] secret;for (int i 1; i t; i) {coefficients[i] generateRandomBigInteger();}BigInteger[] userShares new BigInteger[m];//进行秘密分享for (int i 0; i m; i) {userShares[i] computeShare(coefficients, (i 1));}return userShares;}/*** 为指定用户计算秘密份额** param coefficients 系数向量* param userIndex 用户索引即对于用户的x值* 这里计算f(x)时x取值为 (下标 1)* 如果直接从下标开始不加1会 直接暴露出 f(0)即秘密* return*/public static BigInteger computeShare(BigInteger[] coefficients, int userIndex) {BigInteger index new BigInteger(String.valueOf(userIndex));int len coefficients.length;BigInteger temp BigInteger.ONE;BigInteger result BigInteger.ZERO;for (int i 0; i len; i) {BigInteger cur coefficients[i].multiply(temp);temp temp.multiply(index);result result.add(cur).mod(p);}return result.mod(p);}/*** 生成小于p的随机数** return*/public static BigInteger generateRandomBigInteger() {BigInteger result;do {result new BigInteger(p.bitLength(), random);} while ((result.compareTo(p) 0) (result.compareTo(BigInteger.ZERO) ! 0));return result;}/*** 初始化方法指定模数的bit长度* param bitLen*/public static void init(int bitLen) {random new Random();p BigInteger.probablePrime(bitLen,random);}/*** 秘密重建算法** param shares 用户输入的秘密* param t 可以恢复秘密的阈值* return*/public static BigInteger reconstruction(BigInteger[] shares, int t) throws Exception {int n shares.length;if (t n) {throw new Exception(你当前收集的秘密份额不足以恢复秘密);}BigInteger result new BigInteger(0);for (int i 0; i t; i) {result result.add(interpolation(shares, i 1, t));}return result.mod(p);}/*** 求第i号用户(xK i 1)的了拉格朗日插值** param values* param t* return*/public static BigInteger interpolation(BigInteger[] values, int xK, int t) {BigInteger result;//常量0计算f(0)BigInteger zero BigInteger.ZERO;BigInteger x_k new BigInteger(String.valueOf(xK));//拉格朗日多项式BigInteger up BigInteger.ONE;BigInteger down BigInteger.ONE;//i代表第i个用户的份额for (int i 0; i t; i) {BigInteger x_i new BigInteger(String.valueOf((i 1)));if (x_i.equals(x_k)) {continue;}up up.multiply(zero.subtract(x_i));down down.multiply(x_k.subtract(x_i));}result up.multiply(down.modInverse(p));result result.multiply(values[xK - 1]);return result;}public static void main(String[] args) throws Exception {init(1024);int times 1000;System.out.println(测试开始.....);for (int i 0;i times;i){//生成小于p的随机秘密BigInteger secret generateRandomBigInteger();int m (int) (Math.random() * 100 ) 5;int t (int) (Math.random() * 50 ) 1;//阈值必须小于总用户数while (t m){t (int) (Math.random() * 50 ) 1;}BigInteger[] shares share(secret, m, t);BigInteger reconstruction reconstruction(shares, t);if (reconstruction.compareTo(secret) ! 0){System.out.println(秘密值恢复错误);}}System.out.println(测试结束.....);}
}
