2

我正在尝试解密使用 RSA 算法加密的消息

在此处输入图像描述

上面的示例取自Website，所以我尝试在 C# 中实现它：

int msg = 67;

int Ee = 5;
int Nn = 91;
int Dd = 29;

var cipher = Math.Pow(msg, Ee) % Nn;
var msg2 = Math.Pow(cipher, Dd) % Nn;

MessageBox.Show("Msg: " + msg.ToString() + " cipher: " + cipher.ToString() 
                   + " msg: " + msg2.ToString());

输出如下：

消息：67 密码：58 消息：45

如您所见 - 加密工作正常，但解密不是！

所以我去检查了网站，结果发现 Javaspript 使用了另一个公式：

function mod( m, n )
{           
    return m - n*Math.floor(m/n)
}
function PowerMod(x,p,N)
    // Compute x^p mod N
    {
        var A = 1
        var m = p
        var t = x

        while( m > 0 )
        {
            k = Math.floor( m/2 )
            r = m - 2*k
            if( r == 1 )
                A = mod( A*t, N )
            t = mod( t*t, N )
            m = k
        }           
        return A
    }

        var temp = ""
        var e = form.e.value
        var d = form.d.value
        var N = form.N.value
        var M = form.Msg.value

        form.Cipher.value = PowerMod(M,e,N)

        var C = form.Cipher.value
        form.Decipher.value = PowerMod(C,d,N)

而不是复制和粘贴准备好的公式 - 我想知道为什么我的方法不起作用，我宁愿修复我的公式而不仅仅是重写 JS。关于如何修复解密的任何想法？

4

2 回答 2

3

您的逻辑是正确的，但Math.Pow()不会产生精确的结果，因为 58 29太大而无法处理。这最终会破坏您的算法。在实践中，RSA 密钥远大于此，计算b ^ e根本不可行。

PowerMod()JavaScript 函数使用从右到左的二进制方法在不损失精度的情况下执行模幂运算 ( ) b ^ e % m，这就是它起作用的原因。

您可以在 Wikipedia article for modules exponentiation阅读更多关于它的信息。

于 2013-05-13T15:34:18.447 回答
2

密文是58，你的解密密钥是29。

58^29 = 真的，真的很大。大约 1.378516 * 10^51

我认为您的直接方法超出了 Math.Pow 中使用的双精度数据类型的精度。对于模数除法，最重要的是最低有效位，而那些正是被忽略/丢失的位。

在我看来，javascript 算法将 power 操作和 mod 操作合并在一起，因此数据始终保持在底层数据类型精度的范围内。

于 2013-05-13T15:43:30.340 回答