密码学门限方案实现
分出来的块
/**
* 块。将密钥按照某种规则分解成的密码片。对应于多项式的坐标，index表示横坐标，value表示纵坐标
*
* @author Seven
* @version 1.0
* @date 2020-09-14 22:18
*/
@Data
public class Piece {
/**
* 块下标，从 1 开始
*/
private int index;
/**
* 块存储的数值
*/
private long value;
/**
* 构造器
*
* @param index 块下标
* @param value 块存储的数值
*/
public Piece(int index, long value) {
this.index = index;
this.value = value;
}
}
一、界面效果
- 输入参数
-
生成密钥
-
选择“恢复密钥“选项卡
-
点击”获取分片”
-
保留任意 3 个分片，可以正常恢复出密钥
-
保留任意两个分片，不能准确恢复密钥
二、Shamir(k, n)门限方案
参考：
[1] Shamir 门限方案介绍：Secret Sharing Explained Visually
1. 密码块生成算法
1）多项式求值算法
/**
* 计算生成多项式 f(x) = secretKey + coefficients[0] * x + coefficients[1] * x ^ 2 + ... + coefficients[n] * x ^ n
* 的值。模运算。
*
* @param coefficients 系数，下标 0 表示 x^1 的系数，下标 n 表示 x^(n + 1) 的系数
* @param x 自变量
* @param c 常数项
* @param mod 模，所有运算为模运算
* @return f(x)
*/
private long fun(int x, long c, long[] coefficients, long mod) {
LinkedList<Long> coefs = new LinkedList<>();
for (long item : coefficients) {
coefs.add(item);
}
return (fun0(x, coefs, mod) + c) % mod;
}
/**
* 多项式算法（模运算）
* f(x) = c + a1 * x^1 + a2 * x^2 + a3 * x^3 + ... + an * x^n
* = c + x(a1 + x(a2 + x(a3 ... + x(an))))
*
* @param x 自变量
* @param coefficients 系数
* @param mod 模
* @return f(x)
*/
private long fun0(int x, LinkedList<Long> coefficients, long mod) {
if (coefficients == null || coefficients.size() == 0) {
return 0;
}
if (coefficients.size() == 1) {
return (long) ((1.0 * coefficients.get(0)) * x % mod);
}
long a0 = coefficients.removeFirst();
LinkedList<Long> list = new LinkedList<>(coefficients);
return (long) ((1.0 * x * (a0 + fun0(x, list, mod))) % mod);
}
2）随机系数生成算法
/**
* 生成随机数
*
* @param coefficients 保存的位置
* @param bound 最大值，不包含
*/
private void genRandomNum(long[] coefficients, long bound) {
Random random = new Random();
for (int i = 0; i < coefficients.length; i++) {
// 这里的随机数可能为负数，需要转成正数
coefficients[i] = Math.floorMod(random.nextLong(), bound);
}
}
3）密钥块生成算法
/**
* 计算分片
*
* @param secretKey 密钥
* @param totalPieceNumber 总分片数（n）
* @param minEffectiveSliceNumber 最小有效分片数（k），取 k 个以上的分片才能还原出密钥
* @param mod 模，所有的运算将在此模下进行。素数，大于 <code>totalPieceNumber</code> 和 <code>secretKey</code>
* @return 分片后的数据
*/
@Override
public Piece[] genPieces(long secretKey, int totalPieceNumber, int minEffectiveSliceNumber, long mod) {
// 1. 随机生成多项式的系数。多项式的项数为：totalPieceNumber - minEffectiveSliceNumber
// 系数，下标 0 表示 x^1 的系数，下标 n 表示 x^(n + 1) 的系数
long[] coefficients = new long[totalPieceNumber - minEffectiveSliceNumber];
// 生成随机数，取值范围为 [0, mod)
genRandomNum(coefficients, mod);
// 生成多项式为 f(x) = secretKey + coefficients[0] * x + coefficients[1] * x ^ 2 + ... + coefficients[n] * x ^ n
// 2. 求每个块，即求 f(1), f(2) ... f(totalPieceNumber)
Piece[] result = new Piece[totalPieceNumber];
for (int i = 0; i < result.length; i++) {
long value = fun(i + 1, secretKey, coefficients, mod);
result[i] = new Piece(i + 1, value);
}
return result;
}
2. 密钥恢复算法
1）欧几里得插值多项式求解
/**
* 根据部分分片，尝试还原出密钥
*
* @param pieces 部分分片
* @param totalPieceNumber 总分片数（n）
* @param minEffectiveSliceNumber 最小有效分片数（k），取 k 个以上的分片才能还原出密钥
* @param mod 模，所有的运算将在此模下进行。素数，大于 <code>totalPieceNumber</code> 和 <code>secretKey</code>
* @return 还原出的密钥，如果分片不充分，则不能还原出正确的密钥
*/
@Override
public long restoreSecretKey(Piece[] pieces, long mod) {
long x = 0;
// 这里使用 double 是为了防止 long 数值溢出
double result = 0;
for (Piece piece : pieces) {
// 这里使用 double 是为了防止 long 数值溢出
double a = piece.getValue();
for (Piece p : pieces) {
if (p != piece) {
long inverse = ModUtil.modInverse(piece.getIndex() - p.getIndex(), mod);
a *= (x - p.getIndex()) * inverse;
a = Math.floorMod((long) (a % mod), mod);
}
}
result += a;
result = Math.floorMod((int) (result % mod), mod);
}
return (long) result;
}