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

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， ...

谢谢，我再看一下