为何decryptRSA函数返回随机结果？RSA加解密程序异常排查

核心问题1：私钥d的计算完全错误 #

在rsaKeygen函数中，d = 1%totientN/e这行逻辑完全错误。RSA要求私钥d是e在模totientN下的模逆元，即必须满足(e * d) ≡ 1 mod totientN，而非简单的模运算后做除法。Lua没有内置模逆元函数，需通过扩展欧几里得算法实现。

核心问题2：大数运算精度丢失 #

Lua默认使用双精度浮点数，处理1.16e+20这类大数时，直接计算msg^e会触发精度溢出，丢失有效数字，导致加密解密结果完全偏离预期。必须改用快速模幂算法，在计算过程中持续取模，避免大数溢出。

核心问题3：密钥生成逻辑瑕疵（非致命但不合理） #

p和q的随机范围逻辑混乱：初始给p选50000-100000的数，非素数就换成1-1000；q则相反。这会导致其中一个素数大概率过小，降低密钥安全性，建议统一素数随机范围。

修复后的代码 #

1. 实现扩展欧几里得算法求模逆元 #

function modinv(a, m)
    local m0 = m
    local y = 0
    local x = 1
    if m == 1 then
        return 0
    end
    while a > 1 do
        local q = math.floor(a / m)
        local t = m
        m = a % m
        a = t
        t = y
        y = x - q * y
        x = t
    end
    if x < 0 then
        x = x + m0
    end
    return x
end

2. 修复密钥生成函数 #

function rsaKeygen()
    -- 统一素数随机范围，确保p、q均为大素数
    local p = math.random(50000, 100000)
    while not isprime(p) do
        p = math.random(50000, 100000)
    end
    local q = math.random(50000, 100000)
    while not isprime(q) do
        q = math.random(50000, 100000)
    end
    -- 确保p≠q，避免n为平方数
    while p == q do
        q = math.random(50000, 100000)
        while not isprime(q) do
            q = math.random(50000, 100000)
        end
    end
    local n = p * q
    local totientN = carmichael(n)
    local e = 2^16 + 1 -- 65537，常用安全公钥指数
    -- 确保e与totientN互质
    while gcd(e, totientN) ~= 1 do
        e = e + 2
    end
    local d = modinv(e, totientN)
    return e, d, n
end

3. 实现快速模幂算法修复加密解密 #

function modpow(base, exp, mod)
    local result = 1
    base = base % mod
    while exp > 0 do
        if exp % 2 == 1 then
            result = (result * base) % mod
        end
        exp = math.floor(exp / 2)
        base = (base * base) % mod
    end
    return result
end

function encryptRSA(e, n, msg)
    local msgNum = plainToNum(msg)
    -- RSA要求明文数值必须小于n，否则需分段加密
    if msgNum >= n then
        error("明文过大，需分段处理")
    end
    return modpow(msgNum, e, n)
end

function decryptRSA(d, n, msg)
    return modpow(msg, d, n)
end

关键说明 #

• 模逆元是RSA私钥计算的核心，必须通过扩展欧几里得算法实现，不能直接用除法。
• 快速模幂算法通过每一步取模，避免了大数运算的精度损失，保证数值始终在合理范围内。
• 必须确保明文数值小于n，否则需要对明文进行分段处理，这是RSA的基本要求。

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