js实现简单rsa

RSA 算法简介

RSA 是一种非对称加密算法，广泛应用于数据加密和数字签名。其核心基于大数分解的数学难题，涉及公钥和私钥的生成。

密钥生成步骤

生成两个大质数 p 和 q，计算 n = p q 和 φ(n) = (p-1)(q-1)

选择一个整数 e 满足 1 < e < φ(n) 且与 φ(n) 互质

计算 d 使得 (d * e) % φ(n) = 1，即 d 是 e 的模反元素

JavaScript 实现

// 简单RSA实现（仅用于教学演示，不适用于生产环境）
function modInverse(e, phi) {
    let m0 = phi, t, q;
    let x0 = 0, x1 = 1;

    if (phi === 1) return 0;

    while (e > 1) {
        q = Math.floor(e / phi);
        t = phi;
        phi = e % phi;
        e = t;
        t = x0;
        x0 = x1 - q * x0;
        x1 = t;
    }

    if (x1 < 0) x1 += m0;
    return x1;
}

function isPrime(num) {
    if (num <= 1) return false;
    if (num <= 3) return true;

    if (num % 2 === 0 || num % 3 === 0) return false;

    for (let i = 5; i * i <= num; i += 6) {
        if (num % i === 0 || num % (i + 2) === 0) return false;
    }

    return true;
}

function generateKeys(p, q) {
    if (!isPrime(p) || !isPrime(q)) {
        throw new Error('Both numbers must be prime.');
    }

    const n = p * q;
    const phi = (p - 1) * (q - 1);
    let e = 2;

    while (e < phi) {
        if (gcd(e, phi) === 1) break;
        e++;
    }

    const d = modInverse(e, phi);

    return {
        publicKey: { e, n },
        privateKey: { d, n }
    };
}

function gcd(a, b) {
    while (b !== 0) {
        let temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

function encrypt(message, publicKey) {
    const { e, n } = publicKey;
    return BigInt(message)  BigInt(e) % BigInt(n);
}

function decrypt(encrypted, privateKey) {
    const { d, n } = privateKey;
    return BigInt(encrypted)  BigInt(d) % BigInt(n);
}

使用示例

// 选择两个质数（实际应用中应使用更大的质数）
const p = 61;
const q = 53;

// 生成密钥对
const keys = generateKeys(p, q);

// 加密消息
const message = 65;
const encrypted = encrypt(message, keys.publicKey);

// 解密消息
const decrypted = decrypt(encrypted, keys.privateKey);

console.log('Original:', message);
console.log('Encrypted:', encrypted);
console.log('Decrypted:', decrypted);

注意事项

该实现仅为教学演示，使用了小质数以便理解。实际RSA应用需要2048位或更大的密钥。

JavaScript的BigInt类型用于处理大整数运算，但性能不如专业加密库。

生产环境应使用成熟的加密库如Web Crypto API或Node.js的crypto模块。