标题：如何破解 RSA-1024？―― Asprotect 1.0/1.1/1.11c

作者：Amenesia//TKM!（翻译：forgot/iPB）

0. 译注
========

        结论如何无所谓，关键是学习研究弱点攻击的方法。
一些代码我调整了缩进，用 notepad 排版，并加入一点注释。
	精力有限，只翻译前半部分，后面基本一样。

1. 引子
=======

        为学习基础知识，我决定研究一些著名的壳及其弱点。

首先是被Recca早在几年前就发现的弱点的ASProtect。我们知

道Recca曾经利用随机数生成器的弱点破解了ASProtect的注册

方案，现在一起看看吧……

2. Asprotect 1.0/1.1 [固定密钥]
===============================

        创建一个项目的时候会产生一些参数并保存在projec

t_name.aspr 文件中。其中比较重要的是用base64算法编码的

A，D，E和N（从右至左保存）。

-------------------------------------------------------
        A = INDtrZliM4t...0czFJpN42UQ==

        D = U2atlST1lQ...kHcbIGwJU8=

        E = EQAAAAAA...AAAAAAAA=

        N = X7lD2zsvq3QW...ha6mOrdvULEAM8=
-------------------------------------------------------

        然后计算注册密钥：

-------------------------------------------------------
        1 - H1 = RipeMD-160(A)

        2 - H2 = MD5(注册信息―H1)

        3 - Key = RSA(D,N, [H2―注册信息―H1])
-------------------------------------------------------

        密钥看起来像这个样子：

-------------------------------------------------------
        PYgt/87koSvbYPluc+/crrilfWI+ssZSU7UhgCLmK3D1C+x+
        EX9n7ukwM5sKmI+nsH66V7L28BFTziNz5DOPLRHAqnI11wN5
        Nd/dm0Esw20mm66V7L28BFTziNz55DOP4kzt+bie/rW4grgG
        +e8/hsIuotMqUXguWKBnOXsoQ89Kg92T0MkB4FCZYuZQo=
-------------------------------------------------------

        这个注册方案似乎很安全。

2.1 如何产生D，N和E？
====================

        这个过程在 RSAVR.dll 实现：

-------------------------------------------------------
        1   -   产生两个素数P和Q（512位）
        1.1 -   产生一个512位随机数
        1.2 -   找到最接近它的下一个素数（很慢）
        2   -   计算 N = P * Q
        3   -   计算 D = E^(-1)phi(N)（E = 17）
-------------------------------------------------------

        所以如果我们能找到P和Q就能分解N。

（译注：^求次方，phi应该是欧拉函数）

2.2 如何产生P和Q？
=================

-------------------------------------------------------
        unsigned long _rand()
        {
        //随机化seed
                Seed *= 214013;
                Seed += 2531011;
                return( ((Seed >> 16) & 0x7FFF) );
        }

        unsigned long RandInt()
        {
        //产生一个随机数
                for ( i=0; i<4; i++)
                {
                        rval = ((rval << 8) +_ rand());
                }
                return(rval);
        }

        //计算 seed！！！关键！！！
        Seed = (time() + ThreadId()) xor TickCount();

        //计算P
        for ( ri=0; ri<16; ri++)
        {
                BigNumber1[ri] = RandInt();
        }
        BigNumber1[ri] = BigNumber1[ri] xor C0000000h;

        P = nextPrime(BigNumber1);
        //计算Q
        for ( ri=0; ri<16; ri++)
        {
                BigNumber2[ri] = RandInt();
        }
        BigNumber2[ri] = BigNumber2[ri] xor C0000000h;

        Q = nextPrime(BigNumber2);
-------------------------------------------------------

        因此若我们能猜到(time() + ThreadId()) xor Tick
Count()的值就能获得P和Q。

（译注：nextPrime() 求离参数最近的下一个素数。）

2.3 攻击
========

        不知Recca是怎么找那个seed的，似乎蛮力攻击是唯
一的方法（有 2^32 种可能）：

-------------------------------------------------------
        1 - 选择一个 seed
        2 - 计算 BigNumber1 和 BigNumber2
        3 - 寻找P = nextPrime(BigNumber1)
                Q = nextPrime(BigNumber2)
        4 - 若 N != P * Q 则换另外的 seed
-------------------------------------------------------

        不过素数测试花费的时间是可怕的，尝试2^32个不同
的 seed 几乎不可能。

2.3.1 缩小范围
==============

        第一个改进方法是基于 ThreadId 和 TickCount 通
常很小的事实。所以 seed 高位一般都是 time() 值。因此，
我们可以只考察接近软件发布日期的 seed。

（译注：忍不住赞）

2.3.2 改进算法
==============

        素数测试很慢，我们不得不找一个并不计算 P 和 Q
值的情况下就能检测是否是正确 seed 的算法。窍门就是修改
nextPrime() 函数使之只计算 BigNumber1 和 BigNumber2 的
低位双字。

        P = BigNumber1 + Delta1 (Delta1 <= 2^64)
        Q = BigNumber2 + Delta2 (Delta2 <= 2^64)
        N = P * Q = (BigNumber1 + Delta1) * (BigNumber2 + Delta2)
        N = BigNumber1 * BigNumber2 + Delta3 (Delta3 <= 2^(512+64+2))
        因此：N高位 = BigNumber1高位 * BigNumber2高位

（译注：Delta是增量，因为 nextPrime 是下一个素数，因此
是数后面加一个增量，至于Delta的范围，我还没想去证明。）

        算法：
-------------------------------------------------------
        1 - 选择一个 seed
        2 - 计算 BigNumber1高位 和 BigNumber2高位
        3 - 若 N高位 != BigNumber1高位 * BigNumber2高位
            换另外的 seed
        4 - 计算 BigNumber1 和 BigNumber2（避免冲撞值）
        5 - 计算 P = nextPrime( BigNumber1 )
                 Q = nextPrime( BigNumber2 )
        6 - 若 N! = P * Q 换另外的 seed
-------------------------------------------------------

2.4 例子
========

        ASProtect 1.1 用它自己加壳，再难找到更好的例子
啦。检查一下我们的的算法是否有效。

        N 和 E 保存在被加密的程序中：

        N = EB1D4EADA4815F6277519791BFFA8B4C0B872D1C436515AB
        D9572B22BF6A03FECB4E5CC49AF1EE35C31344617A1210663056
        90529B9CE7F13ED2D37CD7034A3EDD096853EC61243BCCAC5A58
        800B0330A4DD85E9AA237F2F2AE60CA049B1D2777B2E0C5FF51E
        058382A86C3EC12F7AB41642022772FF2A2D3DBA704725702199

        E = 17

        ASProtect 在 2000 10月 发布，所以我们选择 39000000h
作为最小的 seed。我们找到了一个冲撞值 398BBB72h，一分钟后找
到 399BACC4h（花了一小时检测 2^32 种可能）：

        D = l8F1EGKSQWCw9Et5klCpkm9/TIQFw0xOxibd+bQNndzGYoIX
        4PmHXcdZtN3VWRQfuYS/cLeEf0i+kG3Cd7kaqKCkBO3xiAFgZMf
        vW8D+bov+AfjDICITq5/Lhex7PykLGtUNnH8LSsmIDSWqldwX3Q
        9o8U4HcJSjSJIfS4bumc=


....

[培训]内核驱动高级班，冲击BAT一流互联网大厂工 作，每周日13:00-18:00直播授课