这个函数怎么求逆运算，谢谢

wgz001

从一个软件分析中得到下面一个函数，伪代码如下

[C++] 纯文本查看 复制代码

RSA_POW_MOD(M,e,N)
{
        CONST = N-M;
        CONST2= N-2;   
        RSI =2;
        RDI =M;
        While(e>0)
        {
                if(e and 1 )
                {
                        RSI = (RSI*RDI+CONST)  MOD N;
                        RDI = (RDI*RDI+CONST2) MOD N;
                        e >>= 1;
                         
                
                }
                else
                {
                        RDI = (RSI*RDI+CONST)  MOD N;
                        RSI = (RSI*RSI+CONST2) MOD N;
                        e >>=1;
        }

        return RSI;

}

其中e=65537，只是用来保证循环的次数，已知RSI,e，N(N是一个大数)，能不能求得M，谢谢

y761110576

不一定对
从楼主中代码
             else {
                        RDI = (RSI*RDI+CONST)  MOD N;
                        RSI = (RSI*RSI+CONST2) MOD N;
                        e >>=1;
               }
可知RDI=(2*M+N-M)MOD N即RDI=M是不变的
  RSI=(2*2+N-2)MOD N即RSI=2也是不变的
  只需要分析if里面的内容
                        RSI = (RSI*RDI+CONST)  MOD N;
                        RDI = (RDI*RDI+CONST2) MOD N;
RSI=(2*M+N-M)MOD N=M
RDI=(M*M+N-2)MOD N用不到
知道最后的RSI就知道M了，当然这是有条件的即M<N
不小于的话，那可就不好算了

wgz001

y761110576 发表于 2022-2-9 12:26
不一定对
从楼主中代码
             else {

谢谢您的回答
RSI和RDI都是变化的
要不您空了再看一下，这是一个有趣的话题

lizhirui

这是带求余的快速幂算法，等价于result = M^e mod N，RSA算法的关键运算步骤，想求逆，你需要另一个参数d，明文就是M=result^d mod N，在rsa中，e和d分别是公钥和私钥（或者反过来），M是模数，理论上通过e和M可以推出d，也可以通过d和M推出e，但是，这个问题属于大质数分解难题，对于现在常用的RSA1024-4096来说，这个推导过程需要极大的计算量，是属于计算不可行问题。这也是RSA算法作为少见的非对称密钥算法被使用到今天，广泛用于证书认证和数字签名等领域的原因。

wgz001

lizhirui 发表于 2022-2-10 10:10
这是带求余的快速幂算法，等价于result = M^e mod N，RSA算法的关键运算步骤，想求逆，你需要另一个参数d， ...

谢谢，我再看一下