希望我没大错误。
代码:
标题：如何破解 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=
....