一文读懂基于Elgaml的数字签名
![6JQ5NHU1M)MD@WQYI)2L9]C.jpg](https://ucc.alicdn.com/pic/developer-ecology/39fa106b2b8740579949db036ee1e7a4.jpg?x-oss-process=image/resize,w_1400/format,webp "6JQ5NHU1M)MD@WQYI)2L9]C.jpg")
基于Elgamal的数字签名方案
本文来先填一下之前挖的坑，简单介绍一个实际的数字签名的方案，给自己挖的坑总是要自己来填的。
知识回顾
在介绍具体的签名算法之前，首先来回顾一下之前讲过的离散对数和数论相关的知识，对于素数p, 如果是p的原根，那么对于取模p之后的值是不同的，然后，我们可以得到下面两个结论。
- 对于任意的整数m, , 当且仅当
- 对于任意整数i, j，, 当且仅当
密钥选择
如果读者看过我之前聊过的基于elgamal的加密，理解后面这些内容相对来说会轻松不少，不过要是没看过也没有关系，我尽量也是把每个细节聊清楚。
基于Elgamal的数字签名，全局元素是p和 , 其中 是p的原根，然后根据下面的方法生成公私钥对。
- 生成随机整数 , 使得
- 计算
- A的私钥是, A的公钥是
签名过程
如果用户A需要对消息M进行签名，则按照如下的步骤进行处理
- 计算消息M的哈希值m = H(M)，其中 m 在
- 随机选择一个整数K, 使 并且 , 也就是K和p-1互素
- 计算
- 计算, 这里可不是普通的指数运算，而是求逆运算这也就是前面要求互素的原因, 因为不互素是没有逆的。
- 计算
- 最终生成的签名(, )
签名验证过程
对于任意的用户, 都能按照如下的方式对签名进行验证
如果, 说明签名有效。
接下来，简单证明一下，为什么上面, 就可以说明签名是有效的吧, 假设这个等式成立，则有。
代码实现
好久没给出具体的实现了，这篇文章回归一下，来用rust简单的实现一下这个数字签名算法。
use std::ops::{Mul, Sub}; use num_bigint::{BigInt, RandBigInt, ToBigInt}; use num_traits::{zero, one}; pub struct Elgamal {} pub struct PublicKey { alpha: BigInt, p: BigInt, y: BigInt, } pub struct PrivateKey { alpha: BigInt, p: BigInt, x: BigInt, } #[derive(Clone, Debug, PartialEq)] pub struct ElGamalSign { s1: BigInt, s2: BigInt, } pub fn mod_inv(u: &BigInt, v: &BigInt) -> BigInt { let mut q: BigInt; let mut t1: BigInt; let mut t3: BigInt; let (mut u1, mut u3, mut v1, mut v3) = (BigInt::from(1u8), u.clone(), BigInt::from(0u8), v.clone()); let mut iter: i8 = 1; while &v3 != &zero() { q = &u3 / &v3; t3 = &u3 % &v3; t1 = &u1 + &q * &v1; u1 = v1; v1 = t1; u3 = v3; v3 = t3; iter = -iter; } if &u3 != &one() { return zero(); } if iter < 0 { return v - u1; } u1 } impl Elgamal { fn sign(m: &BigInt, sk: &PrivateKey) -> ElGamalSign { let mut rng = rand::thread_rng(); let mut k = rng.gen_bigint_range(&BigInt::from(1u8), &(&sk.p - BigInt::from(1u8))); let p_sub_one = &sk.clone().p.clone().sub(1.to_bigint().unwrap()); let mut key_inv = mod_inv(&k, p_sub_one); while key_inv.eq(&zero()) { k = rng.gen_bigint_range(&BigInt::from(1u8), &(&sk.p - BigInt::from(1u8))); key_inv = mod_inv(&k, p_sub_one); } let s1 = sk.alpha.modpow(&k, &sk.p) % &sk.p; let s2 = key_inv.mul(m.sub(&sk.clone().x.clone().mul(&s1))) % &sk.clone().p.clone().sub(1.to_bigint().unwrap()) % (&sk.clone().p.clone().sub(1.to_bigint().unwrap())); ElGamalSign { s1: s1.clone(), s2, } } fn verify(m: &BigInt, s1: &BigInt, s2: &BigInt, pk: &PublicKey) -> bool { let v1 = pk.alpha.modpow(&m, &pk.p); let v2 = pk.y.modpow(&s1, &pk.p).mul(s1.modpow(&s2, &pk.p)) % &pk.p; v1.eq(&v2) } } #[cfg(test)] mod test { use num_bigint::BigInt; use crate::elgamal_sign::{PublicKey, PrivateKey, Elgamal}; #[test] fn test() { let p = BigInt::from(19u8); let alpha = BigInt::from(10u8); let x = BigInt::from(5u8); let y = alpha.modpow(&x, &p); let pk = PublicKey { p: p.clone(), alpha: alpha.clone(), y, }; let sk = PrivateKey { p: p.clone(), alpha: alpha.clone(), x, }; let m = BigInt::from(17u8); let sign = Elgamal::sign(&m, &sk); println!("{:?}", sign); let result = Elgamal::verify(&m, &sign.s1, &sign.s2, &pk); println!("{:?}", result); } }
