Matlab RSA解密模幂脚本结果异常，请求错误排查

问题背景 #

• 给定RSA参数n、e、c，要求不分解n完成解密，可能明文为one（对应数值151405）或two
• 通过二次方程求出p、q，推导得到私钥指数d和欧拉函数phi_n，且已验证参数正确性
• 朋友用Python脚本解密得到正确明文151405，但自己的Matlab脚本得到错误结果690945826910

出错的Matlab代码 #

function decrypt_script()
    % Given values
    C = 273095689186;  % Ciphertext
    d = 368022327335;  % Private key exponent
    n = 712446816787;  % Modulus

    % Decrypt the ciphertext
    plaintext = mod_exp(C, d, n);

    % Output the result
    fprintf('Plaintext: %d\n', plaintext);
end

function result = mod_exp(base, exp, mod_val)
    % Perform modular exponentiation using the method of exponentiation by squaring.
    %
    % Parameters:
    % base (int): The base number to be exponentiated.
    % exp (int): The exponent.
    % mod_val (int): The modulus for the operation.
    %
    % Returns:
    % int: Result of (base^exp) % mod_val

    result = 1;  % Initialize result to 1 (neutral element for multiplication)

    while exp > 0  % While there are still bits in the exponent
        if mod(exp, 2) == 1  % If the current bit of the exponent is 1
            result = mod(result * base, mod_val);  % Multiply result by base and take modulo
        end
        base = mod(base * base, mod_val);  % Square the base and take modulo
        exp = floor(exp / 2);  % Move to the next bit in the exponent
    end
end

问题原因 #

Matlab默认使用双精度浮点数存储数值，而双精度浮点数只能精确表示小于2^53的整数。你的参数n、d、C均远大于这个阈值，在执行result * base或base * base时会发生精度丢失（溢出），导致后续模运算结果完全错误。

修复方案 #

方案1：使用Matlab内置powermod函数 #

直接替换自定义的模幂运算函数，powermod专为大整数模幂运算设计，能避免精度丢失问题：

function decrypt_script()
    % Given values
    C = 273095689186;  % Ciphertext
    d = 368022327335;  % Private key exponent
    n = 712446816787;  % Modulus

    % Decrypt the ciphertext using built-in powermod
    plaintext = powermod(C, d, n);

    % Output the result
    fprintf('Plaintext: %d\n', plaintext);
end

方案2：修改自定义模幂函数为符号运算 #

通过符号变量存储大整数，确保运算精度：

function decrypt_script()
    % Given values
    C = 273095689186;  % Ciphertext
    d = 368022327335;  % Private key exponent
    n = 712446816787;  % Modulus

    % Decrypt the ciphertext
    plaintext = mod_exp(C, d, n);

    % Output the result
    fprintf('Plaintext: %d\n', plaintext);
end

function result = mod_exp(base, exp, mod_val)
    % Convert to symbolic variables to avoid precision loss
    sym_base = sym(base);
    sym_exp = sym(exp);
    sym_mod = sym(mod_val);
    
    % Perform modular exponentiation
    sym_result = powermod(sym_base, sym_exp, sym_mod);
    
    % Convert back to numeric
    result = double(sym_result);
end

验证结果 #

修改后运行脚本，将得到正确明文数值151405，对应字符串one。

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