门限密码共享算法Rust实现

背景知识

笔者不是计算机专业科班生，没有离散数学基础，理解起来很吃力，如有笔误见谅

有限域Galios Field 256

常用于多项式计算，数值范围是u8, 通过对数表和指数表将乘法/除法简化为加法/减法运算

galios field 256 多项式运算的简化，类似于 AI model training quantization 减少运算量一样的工程化目的

有限域的应用

1. 错误检测与纠正

• Reed-Solomon编码：广泛应用于光盘（如CD、DVD）、数字电视和QR码等领域，用于检测和纠正数据传输中的错误。
• BCH码：在卫星通信、无线通信和计算机存储等领域，用于提高数据传输的可靠性。

2. 加密算法

• AES（高级加密标准）：在AES加密算法中，GF(256)用于字节替代（S盒）、列混合等关键步骤，确保数据安全。
• Rijndael算法：作为AES的基础算法，也广泛使用GF(256)中的运算。

3. 数据压缩与存储

• LZMA算法：高级压缩算法LZMA使用GF(256)来提高压缩效率和数据恢复能力。
• RAID系统：在RAID 6等存储系统中，GF(256)用于生成校验信息，以提供数据冗余和恢复能力。

4. 网络通信

• FEC（前向纠错）：在网络通信中使用GF(256)进行前向纠错编码，提高数据传输的可靠性和效率，特别是在低质量或高干扰的通信环境中。

5. 分布式存储

• 门限秘密共享：如Shamir秘密共享方案，利用GF(256)将一个秘密分成多份，并且只有在收集到足够数量的分片时才能重构秘密，确保数据安全性。
• 纠删码：在分布式存储系统中使用GF(256)进行纠删码编码，增强数据的可用性和容错能力
• Reed-Solomon编码：广泛应用于光盘（如CD、DVD）、数字电视和QR码等领域，用于检测和纠正数据传输中的错误。
• BCH码：在卫星通信、无线通信和计算机存储等领域，用于提高数据传输的可靠性。

拉格朗日插值

用于密钥分片恢复出完整密钥

Rust代码实现

use rand::Rng;
const MAX_SECRET_BYTES: usize = 65536;
const MAX_SHARES: usize = 255;

fn add(a: u8, b: u8) -> u8 {
    a ^ b
}
// 通过对数表和指数表将乘法转换为加法运算
#[inline]
fn mul(x: u8, y: u8, exp_op: &[u8], log_op: &[u8]) -> u8 {
    if x == 0 || y == 0 {
        return 0;
    }
    let v = log_op[x as usize] as usize + log_op[y as usize] as usize;
    exp_op[v % 255] // wrap-around using mod 255
}
#[inline]
fn div(x: u8, y: u8, exp_op: &[u8], log_op: &[u8]) -> u8 {
    if x == 0 {
        return 0;
    }
    if y == 0 {
        panic!("division by 0");
    }
    let v = 255 + log_op[x as usize] as usize - log_op[y as usize] as usize;
    exp_op[v % 255] // wrap-around using mod 255
}
/// 多项式在特定点x的求值, a为多项式的系数
fn eval(x: u8, a: &[u8], exp_op: &[u8], log_op: &[u8]) -> u8 {
    assert!(x != 0);
    assert!(!a.is_empty());
    let mut r = 0;
    let mut xi = 1;
    for &b in a {
        r = add(r, mul(b, xi, exp_op, log_op));
        xi = mul(xi, x, exp_op, log_op);
    }
    r
}

pub fn create_shares(secret: &[u8], shares: usize, threshold: usize) -> Vec<Vec<u8>> {
    if secret.is_empty() || secret.len() > MAX_SECRET_BYTES {
        panic!("invalid secret length");
    }
    if shares < 1 || shares > MAX_SHARES || threshold > shares {
        panic!("invalid share parameters");
    }

    let mut rng = rand::thread_rng();
    let mut result = vec![vec![0; secret.len() + 1]; shares];

    for i in 0..shares {
        result[i][0] = (i + 1) as u8;
    }

    for i in 0..secret.len() {
        let mut a = vec![0; threshold];
        // 多项式的系数随机化
        rng.fill(&mut a[1..]);
        a[0] = secret[i];
        for j in 0..shares {
            result[j][i + 1] = eval(result[j][0], &a, &EXP_OP, &LOG_OP);
        }
    }
    result
}

pub fn recover_secret(shares: &[Vec<u8>]) -> Vec<u8> {
    if shares.is_empty() || shares.len() > MAX_SHARES {
        panic!("invalid share count");
    }

    let threshold = shares.len();
    let m = shares[0].len() - 1;

    if m == 0 || m > MAX_SECRET_BYTES {
        panic!("invalid share length");
    }

    let mut u = vec![0; threshold];
    let mut v = vec![0; threshold];
    let mut secret = vec![0; m];

    for i in 0..threshold {
        u[i] = shares[i][0];
        for j in 0..i {
            if u[i] == u[j] {
                panic!("duplicated share index");
            }
        }
    }

    for j in 0..m {
        for i in 0..threshold {
            v[i] = shares[i][j + 1];
        }
        secret[j] = lagrange(&u, &v, &EXP_OP, &LOG_OP);
    }
    secret
}
/// 使用拉格朗日插值法恢复秘密 对每个字节的位置进行插值计算，以恢复出原始的密钥
fn lagrange(u: &[u8], v: &[u8], exp_op: &[u8], log_op: &[u8]) -> u8 {
    let mut r = 0;
    for i in 0..u.len() {
        let mut prod = v[i];
        for j in 0..u.len() {
            if i != j {
                prod = mul(
                    prod,
                    div(u[j], add(u[j], u[i]), exp_op, log_op),
                    exp_op,
                    log_op,
                );
            }
        }
        r = add(r, prod);
    }
    r
}

/**
门限密码共享算法中用于实现有限域上的加法、乘法和除法操作
EXP_OP,LOG_OP 实际上是有限域GF(256)上的指数表和对数表。有限域GF(256)是256个元素的有限域，常用于密码学中的许多算法
乘法：通过对数表和指数表将乘法转换为加法运算
除法：通过对数表和指数表将除法转换为减法运算
*/
const EXP_OP: [u8; 510] = [
    0x01, 0x03, 0x05, 0x0f, 0x11, 0x33, 0x55, 0xff, 0x1a, 0x2e, 0x72, 0x96, 0xa1, 0xf8, 0x13, 0x35,
    0x5f, 0xe1, 0x38, 0x48, 0xd8, 0x73, 0x95, 0xa4, 0xf7, 0x02, 0x06, 0x0a, 0x1e, 0x22, 0x66, 0xaa,
    0xe5, 0x34, 0x5c, 0xe4, 0x37, 0x59, 0xeb, 0x26, 0x6a, 0xbe, 0xd9, 0x70, 0x90, 0xab, 0xe6, 0x31,
    0x53, 0xf5, 0x04, 0x0c, 0x14, 0x3c, 0x44, 0xcc, 0x4f, 0xd1, 0x68, 0xb8, 0xd3, 0x6e, 0xb2, 0xcd,
    0x4c, 0xd4, 0x67, 0xa9, 0xe0, 0x3b, 0x4d, 0xd7, 0x62, 0xa6, 0xf1, 0x08, 0x18, 0x28, 0x78, 0x88,
    0x83, 0x9e, 0xb9, 0xd0, 0x6b, 0xbd, 0xdc, 0x7f, 0x81, 0x98, 0xb3, 0xce, 0x49, 0xdb, 0x76, 0x9a,
    0xb5, 0xc4, 0x57, 0xf9, 0x10, 0x30, 0x50, 0xf0, 0x0b, 0x1d, 0x27, 0x69, 0xbb, 0xd6, 0x61, 0xa3,
    0xfe, 0x19, 0x2b, 0x7d, 0x87, 0x92, 0xad, 0xec, 0x2f, 0x71, 0x93, 0xae, 0xe9, 0x20, 0x60, 0xa0,
    0xfb, 0x16, 0x3a, 0x4e, 0xd2, 0x6d, 0xb7, 0xc2, 0x5d, 0xe7, 0x32, 0x56, 0xfa, 0x15, 0x3f, 0x41,
    0xc3, 0x5e, 0xe2, 0x3d, 0x47, 0xc9, 0x40, 0xc0, 0x5b, 0xed, 0x2c, 0x74, 0x9c, 0xbf, 0xda, 0x75,
    0x9f, 0xba, 0xd5, 0x64, 0xac, 0xef, 0x2a, 0x7e, 0x82, 0x9d, 0xbc, 0xdf, 0x7a, 0x8e, 0x89, 0x80,
    0x9b, 0xb6, 0xc1, 0x58, 0xe8, 0x23, 0x65, 0xaf, 0xea, 0x25, 0x6f, 0xb1, 0xc8, 0x43, 0xc5, 0x54,
    0xfc, 0x1f, 0x21, 0x63, 0xa5, 0xf4, 0x07, 0x09, 0x1b, 0x2d, 0x77, 0x99, 0xb0, 0xcb, 0x46, 0xca,
    0x45, 0xcf, 0x4a, 0xde, 0x79, 0x8b, 0x86, 0x91, 0xa8, 0xe3, 0x3e, 0x42, 0xc6, 0x51, 0xf3, 0x0e,
    0x12, 0x36, 0x5a, 0xee, 0x29, 0x7b, 0x8d, 0x8c, 0x8f, 0x8a, 0x85, 0x94, 0xa7, 0xf2, 0x0d, 0x17,
    0x39, 0x4b, 0xdd, 0x7c, 0x84, 0x97, 0xa2, 0xfd, 0x1c, 0x24, 0x6c, 0xb4, 0xc7, 0x52, 0xf6, 0x01,
    0x03, 0x05, 0x0f, 0x11, 0x33, 0x55, 0xff, 0x1a, 0x2e, 0x72, 0x96, 0xa1, 0xf8, 0x13, 0x35, 0x5f,
    0xe1, 0x38, 0x48, 0xd8, 0x73, 0x95, 0xa4, 0xf7, 0x02, 0x06, 0x0a, 0x1e, 0x22, 0x66, 0xaa, 0xe5,
    0x34, 0x5c, 0xe4, 0x37, 0x59, 0xeb, 0x26, 0x6a, 0xbe, 0xd9, 0x70, 0x90, 0xab, 0xe6, 0x31, 0x53,
    0xf5, 0x04, 0x0c, 0x14, 0x3c, 0x44, 0xcc, 0x4f, 0xd1, 0x68, 0xb8, 0xd3, 0x6e, 0xb2, 0xcd, 0x4c,
    0xd4, 0x67, 0xa9, 0xe0, 0x3b, 0x4d, 0xd7, 0x62, 0xa6, 0xf1, 0x08, 0x18, 0x28, 0x78, 0x88, 0x83,
    0x9e, 0xb9, 0xd0, 0x6b, 0xbd, 0xdc, 0x7f, 0x81, 0x98, 0xb3, 0xce, 0x49, 0xdb, 0x76, 0x9a, 0xb5,
    0xc4, 0x57, 0xf9, 0x10, 0x30, 0x50, 0xf0, 0x0b, 0x1d, 0x27, 0x69, 0xbb, 0xd6, 0x61, 0xa3, 0xfe,
    0x19, 0x2b, 0x7d, 0x87, 0x92, 0xad, 0xec, 0x2f, 0x71, 0x93, 0xae, 0xe9, 0x20, 0x60, 0xa0, 0xfb,
    0x16, 0x3a, 0x4e, 0xd2, 0x6d, 0xb7, 0xc2, 0x5d, 0xe7, 0x32, 0x56, 0xfa, 0x15, 0x3f, 0x41, 0xc3,
    0x5e, 0xe2, 0x3d, 0x47, 0xc9, 0x40, 0xc0, 0x5b, 0xed, 0x2c, 0x74, 0x9c, 0xbf, 0xda, 0x75, 0x9f,
    0xba, 0xd5, 0x64, 0xac, 0xef, 0x2a, 0x7e, 0x82, 0x9d, 0xbc, 0xdf, 0x7a, 0x8e, 0x89, 0x80, 0x9b,
    0xb6, 0xc1, 0x58, 0xe8, 0x23, 0x65, 0xaf, 0xea, 0x25, 0x6f, 0xb1, 0xc8, 0x43, 0xc5, 0x54, 0xfc,
    0x1f, 0x21, 0x63, 0xa5, 0xf4, 0x07, 0x09, 0x1b, 0x2d, 0x77, 0x99, 0xb0, 0xcb, 0x46, 0xca, 0x45,
    0xcf, 0x4a, 0xde, 0x79, 0x8b, 0x86, 0x91, 0xa8, 0xe3, 0x3e, 0x42, 0xc6, 0x51, 0xf3, 0x0e, 0x12,
    0x36, 0x5a, 0xee, 0x29, 0x7b, 0x8d, 0x8c, 0x8f, 0x8a, 0x85, 0x94, 0xa7, 0xf2, 0x0d, 0x17, 0x39,
    0x4b, 0xdd, 0x7c, 0x84, 0x97, 0xa2, 0xfd, 0x1c, 0x24, 0x6c, 0xb4, 0xc7, 0x52, 0xf6,
];
const LOG_OP: [u8; 256] = [
    0x00, 0x00, 0x19, 0x01, 0x32, 0x02, 0x1a, 0xc6, 0x4b, 0xc7, 0x1b, 0x68, 0x33, 0xee, 0xdf, 0x03,
    0x64, 0x04, 0xe0, 0x0e, 0x34, 0x8d, 0x81, 0xef, 0x4c, 0x71, 0x08, 0xc8, 0xf8, 0x69, 0x1c, 0xc1,
    0x7d, 0xc2, 0x1d, 0xb5, 0xf9, 0xb9, 0x27, 0x6a, 0x4d, 0xe4, 0xa6, 0x72, 0x9a, 0xc9, 0x09, 0x78,
    0x65, 0x2f, 0x8a, 0x05, 0x21, 0x0f, 0xe1, 0x24, 0x12, 0xf0, 0x82, 0x45, 0x35, 0x93, 0xda, 0x8e,
    0x96, 0x8f, 0xdb, 0xbd, 0x36, 0xd0, 0xce, 0x94, 0x13, 0x5c, 0xd2, 0xf1, 0x40, 0x46, 0x83, 0x38,
    0x66, 0xdd, 0xfd, 0x30, 0xbf, 0x06, 0x8b, 0x62, 0xb3, 0x25, 0xe2, 0x98, 0x22, 0x88, 0x91, 0x10,
    0x7e, 0x6e, 0x48, 0xc3, 0xa3, 0xb6, 0x1e, 0x42, 0x3a, 0x6b, 0x28, 0x54, 0xfa, 0x85, 0x3d, 0xba,
    0x2b, 0x79, 0x0a, 0x15, 0x9b, 0x9f, 0x5e, 0xca, 0x4e, 0xd4, 0xac, 0xe5, 0xf3, 0x73, 0xa7, 0x57,
    0xaf, 0x58, 0xa8, 0x50, 0xf4, 0xea, 0xd6, 0x74, 0x4f, 0xae, 0xe9, 0xd5, 0xe7, 0xe6, 0xad, 0xe8,
    0x2c, 0xd7, 0x75, 0x7a, 0xeb, 0x16, 0x0b, 0xf5, 0x59, 0xcb, 0x5f, 0xb0, 0x9c, 0xa9, 0x51, 0xa0,
    0x7f, 0x0c, 0xf6, 0x6f, 0x17, 0xc4, 0x49, 0xec, 0xd8, 0x43, 0x1f, 0x2d, 0xa4, 0x76, 0x7b, 0xb7,
    0xcc, 0xbb, 0x3e, 0x5a, 0xfb, 0x60, 0xb1, 0x86, 0x3b, 0x52, 0xa1, 0x6c, 0xaa, 0x55, 0x29, 0x9d,
    0x97, 0xb2, 0x87, 0x90, 0x61, 0xbe, 0xdc, 0xfc, 0xbc, 0x95, 0xcf, 0xcd, 0x37, 0x3f, 0x5b, 0xd1,
    0x53, 0x39, 0x84, 0x3c, 0x41, 0xa2, 0x6d, 0x47, 0x14, 0x2a, 0x9e, 0x5d, 0x56, 0xf2, 0xd3, 0xab,
    0x44, 0x11, 0x92, 0xd9, 0x23, 0x20, 0x2e, 0x89, 0xb4, 0x7c, 0xb8, 0x26, 0x77, 0x99, 0xe3, 0xa5,
    0x67, 0x4a, 0xed, 0xde, 0xc5, 0x31, 0xfe, 0x18, 0x0d, 0x63, 0x8c, 0x80, 0xc0, 0xf7, 0x70, 0x07,
];

#[test]
fn test() {
    let secret = b"0958D2BEDFE0EB17BBF6FC";
    let shares = create_shares(secret, 4, 3);
    for (i,share) in shares.iter().enumerate() {
        println!("拆分{} = {}", i+1, hex::encode(share));
    }
    let recover = recover_secret(&shares);
    assert_eq!(secret.to_vec(), recover);
}