160个CM之081——RSA的初步认识以及注册机的编写
序自从上周做了053之后，便一发不可收拾，一口气又做了纯算法的CM 92和81
092是一个blowfish的对称加密算法，论坛早已经有大佬发过了https://www.52pojie.cn/thread-470028-1-1.html
053论坛上没有搜到，是类MD5的加密，最后有个矩阵的验证，花了差不多整整一周时间才完成https://www.52pojie.cn/thread-921654-1-1.html
081论坛上只搜到一个暴力破解的，大概很多人看了这名字变跳过了，我一开始也以为要很久，但实际上这颗草莓比想象中容易得多，大概只用了一晚上，耗时比53和92都要少得多。（前提是你需要了解RSA的算法，我也花了一个晚上去补课RSA）
算法实现流程并不复杂，比之前做的MD5，blowfish的流程要简单很多，但需要一些数学的知识。想要了解RSA机制的可以去https://www.cnblogs.com/Silenceneo-xw/p/6718334.html
不想去看的话我也做了一些整理：
1、预备知识
这个CM应该是一个很标准的RSA加密，而如果提前了解过下面的知识，那这个程序将会变得非常简单（RSA之所以难以破解在于私钥的获取，而这个程序中所选用的质数并不是非常大，可以比较容易算出私钥）
1.1快速幂算法：
顾名思义，快速幂就是快速算底数的n次幂。其时间复杂度为 O(log₂N)， 与朴素的O(N)相比效率有了极大的提高。（结合模运算就是RSA的加密与解密算法）。
例如：计算a的11次方，11的二进制是1011,11 = 23×1 + 22×0 + 21×1 + 2o×1,因此，我们将a11转化为算https://gss3.bdstatic.com/-Po3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D95/sign=257afe75a8773912c0268964f919a226/e850352ac65c1038803a760ab3119313b17e89b6.jpg。
以上来自百度百科，应该很容易理解，其实就是把幂运算转化为多次的平方运算。
1.2 欧拉函数：
百度百科直接复制过来：在数论，对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目（φ(1)=1）。此函数以其首名研究者欧拉命名(Euler's totient function)，它又称为Euler's totient function、φ函数、欧拉商数等。 例如φ(8) =4，因为1,3,5,7均和8互质。 从欧拉函数引伸出来在环论方面的事实和拉格朗日定理构成了欧拉定理的证明。
只要理解第一句话就可以，φ(n)是小于n的正整数中与n互质的数的数目。当然还得知道一个性质：若N为两个质数p,q的乘积，则φ(N)=φ(pq)=(p-1)(q-1);
1.3 乘法逆元 乘法逆元，是指数学领域群G中任意一个元素a，都在G中有唯一的逆元a‘，具有性质a×a'=a'×a=e，其中e为该群的单位元。
从定义上看你也可以理解成倒数，不过是在模运算下的倒数而已，举个例子：3*5≡1 （mod 14) ,我们可以称5关于模14的乘法逆元为3
这个理解概念就行，因为这个程序完全可以通过概念去求乘法逆元。
2、算法描述
2.1 选取两个大素数p,q，并计算N=p*q 2.2 根据欧拉函数，求得r=φ(N)=φ(pq)=(p-1)(q-1); 2.3 选择一个小于r的整数e，并且使得e与r互质 2.4 计算d，使得e*d≡1 (mod r) 2.5 （N，e）作为公钥，（N，d）作为私钥 2.6 明文n加密成c：（若明文过长需分组）
3、81号草莓 3.1 程序界面：VC程序，无壳无反调试，貌似160当中涉及到算法的都是纯算法的。看似是个name/serial的Crack Me,不过分析后会发现只是serial，和name没半毛钱关系。
3.2定位：
在GetWindowTextA下断，很容易追溯到加密算法附近00402871处 是获取文本框内容，不过是获取的serial的内容，而紧接着下面一个call便是验证算法的函数，调用完后有一个JE判断，也是最终是否成功的跳转。
返回1成功，0失败。
通过修改跳转可以在这暴力破解
直接改了00402884 处的跳转会提示成功，最终会弹出含有name的对话框
为了进一步确定name仅仅是在判断成功后才会弹出，之前加密并未用到。可以查找name编辑框的ID：1001，常量搜索后确定在之前并没有调用
那么接下来只需要分析跳转上方的一个call（ sub_4029B0）即可进入到 sub_4029B0当中，IDA看一下流程，里面调用了许多函数，不过大部分都不怎么需要分析
signed int __stdcall sub_4029B0(int serival)
{
int v1; // ecx@2
char v2; // al@3
char v3; // al@6
char v4; // al@6
int v6; // @6
__int16 v7; // @6
char v8; // @6
char v9; // @6
int v10; // @6
__int16 v11; // @6
char v12; // @6
char v13; // @6
char v14; // @1
int v15; // @1
char v16; // @1
char v17; // @1
char v18; // @6
int v19; // @6
int v20; // @6
char v21; // @6
int v22; // @1
CopyArgToEcx((char *)&v15, a9901);
v22 = 0;
CopyArgToEcx(&v14, a12790891);
LOBYTE(v22) = 1;
CopyArgToEcx(&v17, a8483678);
LOBYTE(v22) = 2;
CopyArgToEcx(&v16, a5666933);
LOBYTE(v22) = 3;
if ( strlen((const char *)serival) == 14 )
{
v1 = 0;
while ( 1 )
{
v2 = *(_BYTE *)(v1 + serival);
if ( v2 < 48 || v2 > 57 )
break;
if ( ++v1 >= 14 )
{
v13 = 0;
v9 = 0;
v10 = *(_DWORD *)serival;
v11 = *(_WORD *)(serival + 4);
v3 = *(_BYTE *)(serival + 6);
v6 = *(_DWORD *)(serival + 7);
v12 = v3;
v4 = *(_BYTE *)(serival + 13);
v7 = *(_WORD *)(serival + 11);
v8 = v4;
CopyArgToEcx(&v21, (const char *)&v10);
LOBYTE(v22) = 4;
sub_402310((int)&v19, (int)&v15, &v14);
LOBYTE(v22) = 5;
CopyArgToEcx(&v18, (const char *)&v6);
LOBYTE(v22) = 6;
sub_402310((int)&v20, (int)&v15, &v14);
LOBYTE(v22) = 7;
if ( sub_401DC0(&v17) && sub_401DC0(&v16) )//cmp
{
LOBYTE(v22) = 6;
nullsub_1(&v20);
LOBYTE(v22) = 5;
nullsub_1(&v18);
LOBYTE(v22) = 4;
nullsub_1(&v19);
LOBYTE(v22) = 3;
nullsub_1(&v21);
break;
}
LOBYTE(v22) = 6;
nullsub_1(&v20);
LOBYTE(v22) = 5;
nullsub_1(&v18);
LOBYTE(v22) = 4;
nullsub_1(&v19);
LOBYTE(v22) = 3;
nullsub_1(&v21);
LOBYTE(v22) = 2;
nullsub_1(&v16);
LOBYTE(v22) = 1;
nullsub_1(&v17);
LOBYTE(v22) = 0;
nullsub_1(&v14);
v22 = -1;
nullsub_1(&v15);
return 1;
}
}
}
LOBYTE(v22) = 2;
nullsub_1(&v16);
LOBYTE(v22) = 1;
nullsub_1(&v17);
LOBYTE(v22) = 0;
nullsub_1(&v14);
v22 = -1;
nullsub_1(&v15);
return 0;
}首先是一开始的四个Call,作用是把参数拷贝到ecx所指空间中。然后还有大量地对于一些标志位的修改，貌似也没啥用，后面还有许多的nullsub_1空函数，里面只有一个ret其他的顺着流程看，在sub_4029B0刚开始的时候进行了一系列的赋值
这里有四个全局变量4200dc下的“9901”，4200d0下的“12790891”，4200c8下的“",4200c0下的”5666933“
重新开程序调试追踪后可以发现，这些全局变量是一开始就设定好的，并不存在之后的修改。
而在决定函数返回值是1还是0的时候，会对最后两个字符串进行判断
只要两个判断中有一个相符，就会验证正确。
而另两个字串目前还不知道什么意思
再往下会验证serival的长度，必须等于0xE。接着一个循环是要保证0xE中每一位都需要为0-9
3.3加密：
验证了serial后，在进行比较之前，还调用了两次sub_402310；而这个函数就是进行RSA加密的函数，其会返回一个密文，若第一次返回等于8483678或者第二次返回5666933则成功。
其实这里调用两次只是将明文分组加密了，长度为14（0xE)的明文分为两组，一组7个进行加密。 sub_402310除了传入了我们分组的明文，还会传入刚刚初始化的9901以及12790891。
到这里结合RSA算法特征，我们基本上就能够确定了这两个数就是公钥，e=9901,N=12790891
实际上如果在这已经猜到这是公钥的话，那么此程序的逆向到这就可以结束了，接下来我们只需要验证一下e和N是否是公钥就OK了
直接写一个或者找一个快速幂的算法，也没几行代码，然后把我们输入的明文前7位和9901，12790891作为参数输入，
DWORD64 quick_pow(DWORD64 x, DWORD64 n, DWORD64 m) {
DWORD64 res = 1;
while (n > 0) {
if (n & 1) res = res * x % m;
x = x * x % m;
n >>= 1;
} return res;
}
最终会发现返回值相同，也就是说e=9901,N=12790891就是我们的公钥。
下一步就是去计算私钥，而该程序私钥的计算量并不是很大，N=12790891我们很容易找到p,q。而如果这是一个几百上千位的数字，那到这也就分析不下去了。
随便写一个循环，除100只是单纯地觉得p,q不会在100以内，当然也是为了效率，几乎可以秒得到p,q为1667，7673。
void fun(DWORD64 arg)
{
DWORD64 end=12790891 / 100;
for (DWORD64 i = 3; i < end; i += 2)
{
for (DWORD64 j = 3; j < end; j += 2)
{
if (i*j == 12790891)
{
printf("i=%lld,j=%lld",i,j);
return;
}
}
}
}
得到p,q后，RSA的就已经告破了。
下面计算一下r=（p-1)(q-1)=12781552;
有了r自然也可以得到d，并不需要什么求逆元的算法，直接根据定义构建一个死循环，也几乎可以秒得到d=10961333;
DWORD64 d = 1;
while (1)
{
if (e*d%r == 1)
break;
d++;
}
最后我们把正确的密文用d去解密，就可以得到正确的密码了
PS：如果在这一步看不出e,N的话，那只能跟进sub_00402310 去，而如果你了解过RSA，也会非常容易地搞定，因为它地加密流程并不复杂，而且特征也很鲜明，跟进去后会发现sub_004020F0 函数，它返回了所传参数地二进制数，实际上就是为了一开始所说地快速幂而准备地，后面自然会有快速幂地计算以及取模地运算，不过它地代码里有很多垃圾代码，实际上并不起任何作用。
PPS：14个10进制数分为2组（一组7个）是因为这个程序的N=12790891，而RSA中，每一组的数十进制形式不能超过N，也就是说每组最多也只能是这么多了
三年三班三井寿 发表于 2019-4-12 08:20
老哥厉害啊，还有啥有意思的CM吗，最近有点没事干
试一下，亲手制作！ solly 发表于 2019-4-11 18:55
来支持一下，我抢了个先手！！！
老哥厉害啊，还有啥有意思的CM吗，最近有点没事干 这也太巧了吧，昨天晚上弄完81，中午睡了个午觉发帖，然后帖子写了一半发现论坛上有人发了{:1_925:} 练练手，谢谢啊～～ 非常感谢，测试一下 非常厉害努力学习中 来支持一下，我抢了个先手！！！ 大神级别的文章。直接看不懂啊 不错的资源 支持原创，谢谢热情分享！
页:
[1]
2