[已解决][求助]一段小算法的逆向求值-编程技术-看雪-安全社区|安全招聘|kanxue.com

[已解决][求助]一段小算法的逆向求值

发表于: 2010-1-26 22:05 4615

[已解决][求助]一段小算法的逆向求值

wqrsksk

2010-1-26 22:05

4615

[B]#include <Windows.h>
#include <stdio.h>
 
__int64 GetDwordValue (__int64 cs) 
{
     
    __int64 ret = 0;
     
[COLOR="DarkGreen"]//cs 参数是任意传入的值 
     
//ret 是返回值
     
/*-----------------------------------------------
     
    ret 是结果,将做为返回值
       
    问题:  如果已知 ret 的值, 逆向求出 cs 的值
         
------------------------------------------------*/
    [/COLOR]
    __int64 c1 = 0x1E389FB; [COLOR="DarkGreen"]//常量1[/COLOR]
    __int64 c2 = 0x160F;    [COLOR="DarkGreen"]//常量2[/COLOR]
     
    __int64 mod  = 0; [COLOR="DarkGreen"]//余数[/COLOR]
    __int64 divn = 0; [COLOR="DarkGreen"]//商[/COLOR]
    __int64 jc   = 1; 
     
    do
    {
        mod = c2 % 2;
        if (!mod)
        {
            do
            {
                divn = c2 / 2;
                c2   =  divn;
                 
                ret  = cs * cs % c1;
                 
                cs   = ret;
                 
                mod = c2 % 2;
                 
            } while ( mod == 0 );
        }
         
        c2--;
         
        ret  = cs *  jc % c1;
        jc   = ret ;
         
    }while(c2 > 0);
     
    return ret;
     
}
 
void main()
{
    __int64 test = GetDwordValue(13137657);
    printf("%X\n",test);[/B]}

[招生]科锐逆向工程师培训(2025年3月11日实地，远程教学同时开班, 第52期)！

收藏・0

免费

支持

最新回复 (6)

yusjoel

雪币： 215

活跃值： (10)

能力值：

( LV6，RANK：90 )

在线值：

发帖

回帖

粉丝

关注

私信

yusjoel 2: 2 楼

分析一下这个算法，首先c2只控制循环和分支，不参与到计算。
cs不停地平方，jc对cs不影响。但是cs参与到jc的计算。

由于c2是固定的，所以整个流程是固定的。你在代码中增加printf可以得到：

jc = ret = cs * jc % c1 (jc = cs * jc = cs ^ 1)
cs = ret = cs * cs % c1 (cs = cs ^ 2)
jc = ret = cs * jc % c1 (jc = cs * jc = cs ^ 3)
cs = ret = cs * cs % c1 (cs = cs ^ 4)
jc = ret = cs * jc % c1 (jc = cs * jc = cs ^ 7)
cs = ret = cs * cs % c1 (cs = cs ^ 8)
jc = ret = cs * jc % c1 (jc = cs * jc = cs ^ 15)
cs = ret = cs * cs % c1 (cs = cs ^ 16)
cs = ret = cs * cs % c1 (cs = cs ^ 32)
cs = ret = cs * cs % c1 (cs = cs ^ 64)
cs = ret = cs * cs % c1 (cs = cs ^ 128)
cs = ret = cs * cs % c1 (cs = cs ^ 256)
cs = ret = cs * cs % c1 (cs = cs ^ 512)
jc = ret = cs * jc % c1 (jc = cs * jc = cs ^ 527)
cs = ret = cs * cs % c1 (cs = cs ^ 1024)
jc = ret = cs * jc % c1 (jc = cs * jc = cs ^ 1551)
cs = ret = cs * cs % c1 (cs = cs ^ 2048)
cs = ret = cs * cs % c1 (cs = cs ^ 4096)
jc = ret = cs * jc % c1 (jc = cs * jc = cs ^ 5647)
c1 = 1e389fb
cs = f39d47
jc = a1c641
ret = a1c641

由于同余的关系，可以忽视每一步的取余，到最后在取余即可。

最后ret = cs ^ 5647d % c1

但是这个仍然不好计算，c1 = 1E389FBh = 31689211d = 5157d * 6133d
就算用欧拉定理也无法是5647d变小。

考虑到对c1取余的关系，cs的取值无非就是[0, c1-1]，外面套个循环来穷举吧。

2010-1-27 09:43

wqrsksk

雪币： 208

活跃值： (10)

能力值：

( LV2，RANK：10 )

在线值：

发帖

回帖

569

粉丝

关注

私信

wqrsksk: 3 楼

我能确定这个算法一定有解哦,而且不需要穷举

谢谢热心的yusjoel

2010-1-27 10:38

asdfslw

雪币： 440

活跃值： (87)

能力值：

( LV9，RANK：200 )

在线值：

发帖

回帖

129

粉丝

关注

私信

asdfslw 3: 4 楼

2楼分析得不错——由于数据不太大，可以用循环来穷举。
另外，也可以这样做：

ret = cs ^ 0x160F mod 0x1E389FB

e = 0x160F
n = 0x1E389FB = 0x142F * 0x17F5 = p * q
phi(n) = (p-1) * (q-1) = 0x1E35DD8

d = e ^ -1 = 0x9E1907 mod phi(n)

所以
cs = ret ^ 0x9E1907 mod 0x1E389FB
即逆算法只需要将上面算法的C代码中