为何未填充RSA密文乘2^e后对小消息解密会偶发失败？

核心问题分析 #

你的代码偶发解密失败的主要原因有三个：

1. Buffer转换的奇数长度十六进制字符串处理缺陷
   Node.js的Buffer.from(hexStr, 'hex')会忽略长度为奇数的十六进制字符串的最后一个字符。当解密得到的2m的十六进制字符串长度为奇数时，生成的Buffer会丢失最后4位数据，导致后续转换回BigInt时数值失真，最终除以2后无法还原正确明文。这种情况偶发出现，取决于2m的二进制位数是否为4的倍数加1。

2. 同态操作未取模n
   你当前的同态加倍操作直接计算ct * (2^e mod n)，未对结果取模n，导致doubled是远大于n的超大数。虽然理论上(超大数)^d mod n等价于(超大数 mod n)^d mod n，但超大数转换为十六进制字符串再转回Buffer的过程中，可能引入额外的解析风险，增加出错概率。

3. 错误的console.assert条件
   RSA的私钥指数d是e关于**卡迈克尔函数λ(n)=lcm(p-1,q-1)**的模逆元，而非欧拉函数φ(n)=(p-1)(q-1)的逆元。因此你代码中的console.assert条件偶发失败是正常现象，不影响解密正确性，但会产生不必要的错误日志。

修复后的代码 #

import {generateKeyPairSync} from "node:crypto";
import * as modAr from "bigint-mod-arith";

// 生成1024位RSA密钥对
const keys = generateKeyPairSync("rsa", {modulusLength: 1024});

let jwk_export = keys.privateKey.export({format: "jwk"});
const n = bigintFromParam(jwk_export.n);
const e = bigintFromParam(jwk_export.e);
const d = bigintFromParam(jwk_export.d);

let pt_test = Buffer.from("Hello World!!");
let ct_test  = naiveEncrypt(pt_test, e, n);
// 同态加倍：密文相乘后取模n
let doubled = (bigintFromBuf(ct_test) * modAr.modPow(2n, e, n)) % n;
let doubled_decr = naiveDecrypt(Buffer.from(doubled.toString(16).padStart(256, '0'), "hex"), d, n);

console.debug(pt_test, "plaintext buffer");
console.debug(doubled_decr, "homomorphically doubled buffer (after decryption)");
console.debug(
    "_Decrypted doubled buffer divided back by 2 and converted to text_:", 
    Buffer.from((bigintFromBuf(doubled_decr) / 2n).toString(16).padStart(26, '0'), "hex").toString()
);

// 工具函数
function bigintFromParam(str) {return bigintFromBuf(Buffer.from(str, "base64url"))}
function bigintFromBuf(buf) {return BigInt("0x" + buf.toString("hex"))}

// 修复后的朴素加密函数
function naiveEncrypt(message, e, n) {
    const m = bigintFromBuf(message);
    const encrypted = modAr.modPow(m, e, n);
    let hexStr = encrypted.toString(16);
    // 补前导零确保偶数长度
    if (hexStr.length % 2 !== 0) hexStr = '0' + hexStr;
    return Buffer.from(hexStr, "hex");
}

// 修复后的朴素解密函数
function naiveDecrypt(message, d, n) {
    const c = bigintFromBuf(message);
    const decrypted = modAr.modPow(c, d, n);
    let hexStr = decrypted.toString(16);
    // 补前导零确保偶数长度
    if (hexStr.length % 2 !== 0) hexStr = '0' + hexStr;
    return Buffer.from(hexStr, "hex");
}

关键修复点说明 #

1. Buffer转换补零：在naiveEncrypt和naiveDecrypt中，对BigInt转十六进制字符串的结果补前导零，确保长度为偶数，避免Buffer解析丢失数据。
2. 同态操作取模n：将加倍后的密文结果取模n，确保数值始终在合理范围内，减少超大数处理风险。
3. 移除错误的assert：删除了验证e与d关于φ(n)互逆的assert，替换为直接传递密钥参数，简化逻辑。

内容的提问来源于stack exchange，提问作者Sergey Kaunov