请教如何求“快速幂取模”的底数

zzh90513

如题，现在已知快速幂取模的算法，求“base”底数的算法如何推导，数学都忘光了。。。

1. int PowMod(int base, int pow, int n)
   
2. {
   
3.     int a = base, b = pow, c = 1;
   
4.    
   
5.     while ( b != 0)
   
6.     {
   
7.         while ((b & 1) == 0)
   
8.         {
   
9.             b >>= 1;
   
10.             a = (int)((long)(a * a) % n);
    
11.         }
    
12.         
    
13.         b--;
    
14.         c=(int) ((long)(a * c) % n);
    
15.     }
    
16.    
    
17.     return c;
    
18. }

复制代码

canspider

模幂运算是RSA算法的核心，数学上没有求底公式
目前的方法只有暴力搜索，不过你的底数也就32位，搜索起来也要不了多久

zzh90513

canspider 发表于 2020-1-6 08:16
模幂运算是RSA算法的核心，数学上没有求底公式
目前的方法只有暴力搜索，不过你的底数也就32位，搜索起来也 ...

谢谢，不是反推底数，现在情况是，下位机传入“底数”，上位机PowMod的结果是真实数据，我现在知道pow和n的值；
我有真实数据，想对接上位机，如何能算出符合这个算法的“底数”呢？

canspider

zzh90513 发表于 2020-1-6 08:58
谢谢，不是反推底数，现在情况是，下位机传入“底数”，上位机PowMod的结果是真实数据，我现在知道pow和n ...

按照目前已知的理论算不出来，只能穷举
你还可以反编译上位机软件，做一个补丁绕过这个检测机制