这个函数怎么求逆运算，谢谢
从一个软件分析中得到下面一个函数，伪代码如下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 于 2022-2-9 13:27 编辑
不一定对{:301_998:}
从楼主中代码
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
不小于的话，那可就不好算了 y761110576 发表于 2022-2-9 12:26
不一定对
从楼主中代码
else {
谢谢您的回答
RSI和RDI都是变化的
要不您空了再看一下，这是一个有趣的话题 这是带求余的快速幂算法，等价于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算法作为少见的非对称密钥算法被使用到今天，广泛用于证书认证和数字签名等领域的原因。 lizhirui 发表于 2022-2-10 10:10
这是带求余的快速幂算法，等价于result = M^e mod N，RSA算法的关键运算步骤，想求逆，你需要另一个参数d， ...
谢谢，我再看一下
页:
[1]