当前位置：首页 > JavaScript

js实现elgamal

2026-02-01 04:33:31JavaScript

ElGamal 加密算法实现（JavaScript）

ElGamal 是一种基于离散对数问题的非对称加密算法。以下是一个简单的 JavaScript 实现，包含密钥生成、加密和解密功能。

密钥生成

需要生成一个大素数 p、生成元 g 和私钥 x，公钥为 (p, g, y)，其中 y = g^x mod p。

function generateKeys() {
  // 选择一个安全的大素数 p 和生成元 g（这里简化处理，实际需用安全素数）
  const p = 23n; // 示例素数（实际应用需更大）
  const g = 5n;  // 生成元
  const x = 6n;  // 私钥（随机选择，1 < x < p-1）

  // 计算公钥 y = g^x mod p
  const y = modExp(g, x, p);

  return {
    publicKey: { p, g, y },
    privateKey: { p, x }
  };
}

加密函数

加密时需要接收方的公钥 (p, g, y) 和明文消息 m。

function encrypt(publicKey, m) {
  const { p, g, y } = publicKey;
  const k = 3n; // 临时密钥（随机选择，1 < k < p-1）

  // 计算 c1 = g^k mod p
  const c1 = modExp(g, k, p);
  // 计算 c2 = m * y^k mod p
  const c2 = (m * modExp(y, k, p)) % p;

  return { c1, c2 };
}

解密函数

解密时使用私钥 x 和密文 (c1, c2)。

function decrypt(privateKey, ciphertext) {
  const { p, x } = privateKey;
  const { c1, c2 } = ciphertext;

  // 计算 s = c1^x mod p
  const s = modExp(c1, x, p);
  // 计算 s^{-1} mod p（模逆元）
  const sInv = modInv(s, p);
  // 恢复明文 m = c2 * s^{-1} mod p
  const m = (c2 * sInv) % p;

  return m;
}

辅助函数

实现模幂运算和模逆元计算。

// 模幂计算 (base^exp mod mod)
function modExp(base, exp, mod) {
  let result = 1n;
  base = base % mod;
  while (exp > 0n) {
    if (exp % 2n === 1n) {
      result = (result * base) % mod;
    }
    exp = exp >> 1n;
    base = (base * base) % mod;
  }
  return result;
}

// 扩展欧几里得算法求模逆元
function modInv(a, m) {
  let [old_r, r] = [a, m];
  let [old_s, s] = [1n, 0n];

  while (r !== 0n) {
    const quotient = old_r / r;
    [old_r, r] = [r, old_r - quotient * r];
    [old_s, s] = [s, old_s - quotient * s];
  }

  if (old_r !== 1n) throw new Error('Inverse does not exist');
  return (old_s + m) % m; // 保证结果为正
}

示例用法

// 生成密钥对
const { publicKey, privateKey } = generateKeys();

// 加密消息（明文需小于 p）
const message = 12n;
const ciphertext = encrypt(publicKey, message);

// 解密密文
const decrypted = decrypt(privateKey, ciphertext);

console.log('Original:', message);
console.log('Decrypted:', decrypted); // 应输出 12n