首页
论坛
课程
招聘
[原创]一个基于数字签名的KeygenMe(已增加注册机算法)
2009-11-10 18:00 21891

[原创]一个基于数字签名的KeygenMe(已增加注册机算法)

2009-11-10 18:00
21891
名字 : 基于数字签名的KeygenMe
难度 : 初级
信息 : 无壳、无花、无码、不防爆
描述 : 这是一个基于离散对数的无散列函数和消息冗余数字签名算法的KeygenMe
(此签名算法是与rockinuk 版主共同讨论获得)
一般情况下,为了不被做出注册机都会用RSA、ElGamal等公钥算法,
不过这些算法太简单了一跟踪patch掉公钥就狗屁了~~~
目前来说签名算法种类繁多,随便选个用来做注册算法,破解时patch公钥的方法就不那么好用了。
因为在理解了算法的基础上且获得逆算法的情况下patch公钥才可行。
这个KeygenMe就是用签名算法来防止做出注册机的示例,程序要在没有私钥的情况下作出注册机是不太可能的:
1、很多针对这类签名算法的攻击即使可以伪造有效签名也不能计算任意签名,从而做不出注册机。
2、算法中涉及到多个公钥(如:y1、y2),甚至可以设计成多个公钥和私钥的情况。
   反汇编得到的只是它的验证算法(相当于验证不定方程组的特定解),所以要写出解算法是不容易的。

(为了便于理解程序很多地方都没有优化)
下面是注册机主函数:
/*-------------------------------------------------------------*/
/*                          - 注册机算法主函数                                */
/*-------------------------------------------------------------*/
BOOL GenRegCode( HWND hWnd)
{
        unsigned long  len=0,time_ch=0;
        int i=0,j=0,i_16=16;
        SYSTEMTIME systm;
        big p,y1,y2,g,m,temp,ii,temp1,temp2,bigName,r,s,t,x,k,x_inv;
        miracl *mip=mirsys(2048,16);

        TCHAR szName[MAXINPUTLEN]={0};
        TCHAR szSerial[MAXINPUTLEN]={0};

        len=GetDlgItemText(hWnd, IDC_TXT0, szName, sizeof(szName)/sizeof(TCHAR)+1); // 取姓名
        if (strlen(szName)<6)
        {
                SetDlgItemText(hWnd, IDC_TXT0, "用户名要求6位以上");
                return FALSE;
        }
       
// MIRACL大数运算库运算
//===================================================================================

                  
        mip->IOBASE=16;                                // 16进制模式
        g=mirvar(0);                                   // MIRACL的大数类型
        p=mirvar(0);
        y1=mirvar(0);
        y2=mirvar(0);
        temp=mirvar(0);
        temp1=mirvar(0);
        temp2=mirvar(0);
        ii=mirvar(0);
        m=mirvar(0);
        r=mirvar(0);
        s=mirvar(0);
        t=mirvar(0);
        bigName=mirvar(0);
        x=mirvar(0);
        k=mirvar(0);
        x_inv=mirvar(0);

        cinstr(p,"C7BE40C0925F840E2AD74967C77B449212A086785DD906189EE7B017CBEC9DAE429C1F9716983286555E652DFE671F2A499BF97040EA833080C5E973C09F5D61E4AFC0E919C9842C92536D2A79A785D3D3DD17285270A2E5C6595DB5AC29E44CC23820A7FC625D543756D4289D2F5E5C756919BD4AF6B577975D6B91C28FCDF3");
        cinstr(y1,"6FA878EDB7502A4831896C0B6D86B7EC8F8D02F2A0850DC91527FB5BB4139D23E47A0E3320322573EDDB73D40477D9CE1BD7039E75B710844DECC5ABBEC9F5DD6FB85A0DF6C84CF15148C2B4DA0B842F9834D4633223633D05111C3BDB2D94C615BA24D09DC0F107D4183410DC5255F206BFF113D5642E4E3EDDC67942A9D02F");
        cinstr(y2,"B79743EEB4299D82C231BF5A1EB6535B59DCE35ABF52E8A33A7E6A83CFB0AB78EB8DFBF4AE7A2535B7DC3922FC9F53C694E0B84FDEEE6EFA337E4D9ED904D40C6F0D349A9E1573D64E72E8B92E48C2A0F781D1ADAA03250A396FC758769EE600230990C4971F222DD3A347184388ADC7BB9810DA70EE9FDA33E829843D14DC4A");                                 
        cinstr(g,"2AA12361098628D6E92AC9A75AF621A7633290A30DA48A6884B47963EFD8C3D3A7C02EA34719807484827841B8E8E9815FBC3DF9A131B07A76787CE1246F143F752185B7AFF8C5032458C9AAC5B5A46CB9C7B1EF002A61100BA0382C39CB13FA5CA140EFD96EA7F9CA94F83DD2766AC45C5D006838E43E5A91AC7A7E63467B2");
        cinstr(x,"7940B690E8CF6324681E982AE316E1E9C7B56B80FBC280E36C2FE981C7B7AA53CE27D0B0E38C3207DCCC86633E9F71E72BC529397C5EEB315F16C12E14751497F1950F4F0AB97C5956D02B98F43176DC49E7677B4DDF2CCC1D5CF9F55124D5F200AF585789C7F2CE13A979BB95C8AA8825D8D3B875AD6A4EE4FB014D26D896F3");
        cinstr(x_inv,"70B695769F019679D82B39526267CB17ACD305B4EF13DD0F4A497B204340F40F86E7D230C12FB501C56308B5567067A1A2BB16C59CF3D606F51B75FC2869493964BC8FC8ABD254D81B4E871089BB8632FFB2E3FFDB3558AB87C9B6EB2D08C1171996B60BCE33C2ABF37D86F4121FABBBEA204F89A20C4918607743596ACD07A3");
        cinstr(ii,"1");
// 初始化完成
//m的结构---------|----------|--------|
//256------------200--------100-------0
//------time------|-randomly-|-szName-|
        bytes_to_big(len,szName,bigName);                    // 将姓名转换成大数
        copy(bigName,m);                                                                  // m=bigName
        GetSystemTime(&systm);
        time_ch=systm.wYear;
        if((time_ch<=2000)||(time_ch>=2100)) goto end;
        time_ch=(time_ch-2000)*31536000;
        time_ch=time_ch+systm.wMonth*2592000;
        time_ch=time_ch+systm.wDay*86400;
        time_ch=time_ch+systm.wHour*3600;
        time_ch=time_ch+systm.wMinute*60;
        time_ch=time_ch+systm.wSecond+31536000;                   // i为2000年到现在的秒数+一年
//_asm int 3
        lgconv(time_ch,temp);                               // 将long i 转为 big temp
        i=200;
        expint(i_16,i,temp1);
        multiply(temp1,temp,temp2);                   // temp2为准备加入m的时间截                 
        add(temp2,m,m);                               // m=时间截……bigName
// 时间截计算完成
// temp,temp1,temp2可释放
        zero(temp);
        zero(temp1);
        zero(temp2);
        i=4;
        expint(i_16,i,temp);                                                        // temp为两字节 即 int
        for(j=0;j<25;j++)
        {
                _asm
                {
                        push eax
                        push edx
                        rdtsc
                        mov i,eax
                        pop edx
                        pop eax
                }
                irand(i);
                convert(brand(),temp1);                                                // 将int brand 转为 big temp1
                add(temp2,temp1,temp2);                                                // temp2用来存储随机数
                multiply(temp2,temp,temp2);                                        // temp2右移两个字节,用来存储随机数
        }
        i=100;
        expint(i_16,i,temp);                                                        // temp为100位16进制
        powmod(temp2,ii,temp,temp1);                                        // 保证temp1不超过100位
        multiply(temp1,temp,temp2);                   // temp2为准备加入m的随机数                 
        add(temp2,m,m);                               // m=时间截|随机数|bigName
// m连接完成
        zero(temp);
        zero(temp1);
        zero(temp2);
        i=4;
        expint(i_16,i,temp);                                                        // temp为两字节 即 int
        for(j=0;j<64;j++)                                                                // 256位16进制
        {
                _asm
                {
                        push eax
                        push edx
                        rdtsc
                        mov i,eax
                        pop edx
                        pop eax
                }
                irand(i);
                convert(brand(),temp1);                                                // 将int brand 转为 big temp1
                add(temp2,temp1,temp2);                                                // temp2用来存储随机数
                multiply(temp2,temp,temp2);                                        // temp2右移两个字节,用来存储随机数
        }
        subtract(p,ii,temp);                                                        // 计算p-1
        powmod(temp2,ii,temp,k);                                                // 先求mod p-1 防止溢出
// k计算完成,可释放temp
        powmod(y2,m,p,s);                              // s=y2^m mod p
        subtract(p,ii,temp);
        subtract(temp,k,temp);                         // k必须小于p-1,不然可能为负
        powmod2(y1,temp,m,ii,p,temp1);                 // temp1=m*y1^(-k) mod p
        add(s,temp1,temp2);
        powmod(temp2,ii,p,r);                          // r=temp2 mod p
// r计算完成,temp,temp1,temp2可释放
// powmod2 中p要求是奇数,而powmod没此限制
        multiply(x_inv,s,temp);
        subtract(p,ii,temp1);
        powmod(temp,ii,temp1,temp);                                                // temp=x_inv*s mod p-1
        add(k,temp1,temp2);
        add(temp2,temp1,temp2);                                                        // temp2=k+2(p-1)
        subtract(temp2,temp,temp2);
        subtract(temp2,r,temp2);                                                // temp2=k+2(p-1)-r-x_inv*s mod p-1
        powmod(temp2,ii,temp1,temp2);                   // temp2=temp2 mod p-1
        multiply(temp2,x_inv,temp2);
        powmod(temp2,ii,temp1,t);
// t计算完成,temp,temp1,temp2可释放
        i=256;
        copy(t,temp);                                  // temp=t
        expint(i_16,i,temp1);
        multiply(temp1,s,temp2);
        add(temp2,temp,temp);                          // temp=s连接t
        i=512;
        expint(i_16,i,temp1);
        multiply(temp1,r,temp2);
        add(temp2,temp,temp);                          // temp=rst的链接
        cotstr(temp,szSerial);                         // 将temp的16进制串输出
        SetDlgItemText(hWnd, IDC_TXT1,szSerial);       // 显示正确的序列号
end:
           mirkill(p);
        mirkill(y1);
        mirkill(y2);
        mirkill(m);
        mirkill(g);
        mirkill(ii);
        mirkill(temp);
        mirkill(temp1);
        mirkill(temp2);
        mirkill(r);
        mirkill(s);
        mirkill(t);
        mirkill(bigName);
        mirkill(x);
        mirkill(k);
        mirkill(x_inv);
        mirexit();

        return TRUE;
}

(序列号带有时间截)
pediy-2009

242B2507681E0A99EAF7EAFE84A0E12BB25BBFED30668AE5AC98CC71FC313AD56CBF47B5C79C35E492E8F70B80661632E6EC7E1619C8128CB877316ABEF5295B109D58B1EF94DCB364D4A4AD3015755D77630E13BF7B57B1FA045A3C44E032D93D014C70FAC6A8CE955843640DAA88148ADF8F4F9934FA82E04E414EC8DE2C122719E9A3071762438C0A29D3A664AFD649179455F72FDB04DAC751E2439B8B638CC4F450FA6BB191CB7F04CDD9DDE4C5EDFF941256B3011AEB75063A985817B3D26EAE3499B927B50A3CD2B180B9164E22C8908115FF38A1DAA81FC1A96057BF249BC466BF8DB5303799D30E9A39CF724870FF06A2AC0DC0DBD8EC4C7993D19B444FFD9C124917155AF8822763B6E67FFAFC15C3D9C07C64F6FFEA19F3CDBD0BCFC268CC002B4DC0F0E1BE19A1F10C939ADDFBDBEE68071BF12A4E9C1E065C71A84A85B6C617FF9A49F7D7FB927DD518ECED45C6854AB38443C8BF20CE2429D1CEE1F1BB0B8393AF11CC98F33D7DF55E0A99A4C9F09E8E2986B5413A4E896ABD

已增加算法下载(WORD)

[招生]科锐逆向工程师培训46期预科班将于 2023年02月09日 正式开班

上传的附件:
收藏
点赞0
打赏
分享
最新回复 (52)
雪    币: 1806
活跃值: 活跃值 (39)
能力值: (RANK:420 )
在线值:
发帖
回帖
粉丝
rockinuk 活跃值 8 2009-11-10 18:42
2
0
这个算法是我和 lingyu 一起讨论的内容,lingyu 是最大贡献者

原本的算法( 2000 年) 到现在的算法(2009 年) ,历经多次不同学者改版,并发表到优秀的 journal paper 或是 conference paper 上。

现在把一部分的内容,以 KeygenMe 的方式呈现出来,让大家一窥密码术在 KeygenMe 上的实践。

本次的讨论内容,将有可能成为密码学书中的一部份,如果不愿曝光或是不希望自己的技术被流传的话,请先注明。我将不会把讨论内容放进书本之中。

欢迎大家共同讨论,当然也希望 ccfer 及 sessiondiy 兩位大牛能再次参与本帖内容的讨论与指导。
雪    币: 142
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
TSobo 活跃值 2009-11-10 19:59
3
0
太好了。
雪    币: 1001
活跃值: 活跃值 (31)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
lingyu 活跃值 1 2009-11-10 23:00
4
0
R版过奖了,只不过帮了点小忙而已。
雪    币: 2025
活跃值: 活跃值 (40)
能力值: ( LV9,RANK:180 )
在线值:
发帖
回帖
粉丝
sessiondiy 活跃值 4 2009-11-11 00:57
5
0
看到[描述]...头就晕了
不过..这东西似乎有硬啃的必要,
只能等待各位的讨论从中捡现成的来啃了.
雪    币: 221
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
film 活跃值 2009-11-11 14:31
6
0
看着头都大了,想crack。难啊
雪    币: 340
活跃值: 活跃值 (10)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
asmc 活跃值 1 2009-11-11 17:02
7
0
哎,可惜,我这个爆破手不合适这类CM
雪    币: 145
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
我们闪了 活跃值 2009-11-11 17:50
8
0
期待大牛表演
雪    币: 1806
活跃值: 活跃值 (39)
能力值: (RANK:420 )
在线值:
发帖
回帖
粉丝
rockinuk 活跃值 8 2009-11-11 18:19
9
0
這算是一種 public key cryptosystem,所以某種情況下,公布算法( algorothm) 來接受大家的挑戰,我想也是必要的。
我已請 lingyu 大大整理好算法之後,公布上來,請大家盡情地 enjoy 您的 break/attack。
雪    币: 1331
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
Ivanov 活跃值 2009-11-11 19:41
10
0
总顶几天 促进挑战
雪    币: 2025
活跃值: 活跃值 (40)
能力值: ( LV9,RANK:180 )
在线值:
发帖
回帖
粉丝
sessiondiy 活跃值 4 2009-11-11 19:49
11
0
我提供 sig 档连结一下下. 直视 func name , 免除猜一猜.

0040165B |. E8 D02F0000 call <_powmod>
00401660 |. 83C4 10 add esp, 10
00401663 |. 8B55 AC mov edx, [ebp-54]
00401666 |. 52 push edx
00401667 |. 8B45 C4 mov eax, [ebp-3C]
0040166A |. 50 push eax
0040166B |. E8 A0190000 call <_compare>


CryptoSIG.v2.0.rar
bbs.pediy.com/upload/file/2005/1/CryptoSIG.v2.0.rar_553.rar
雪    币: 1001
活跃值: 活跃值 (31)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
lingyu 活跃值 1 2009-11-11 20:06
12
0
非常感谢,
一般说来,要想不被做出注册机,一般都会使用RSA之类的公钥算法,不过这样就给破解者提供了太多的信息。所以设计自己的基于离散对数或椭圆曲线离散对数的类似于公钥算法的注册机制还是有一定作用的。
雪    币: 106
活跃值: 活跃值 (373)
能力值: ( LV13,RANK:970 )
在线值:
发帖
回帖
粉丝
nbw 活跃值 24 2009-11-11 20:20
13
0
先膜拜一下~
雪    币: 1806
活跃值: 活跃值 (39)
能力值: (RANK:420 )
在线值:
发帖
回帖
粉丝
rockinuk 活跃值 8 2009-11-11 20:25
14
0
sessiondiy 請繼續努力~
雪    币: 2025
活跃值: 活跃值 (40)
能力值: ( LV9,RANK:180 )
在线值:
发帖
回帖
粉丝
sessiondiy 活跃值 4 2009-11-11 20:29
15
0
很显然的....
r 大对"破解"二个字有严重的认知错误.

l 要调教 r 一下才行

我提供本论坛的sig...说我秒破了
雪    币: 1806
活跃值: 活跃值 (39)
能力值: (RANK:420 )
在线值:
发帖
回帖
粉丝
rockinuk 活跃值 8 2009-11-11 20:32
16
0
是的。
對我們來講,有一點點的威脅都是很危險的。
雖然算法沒有被破,可是怕的就是在 practical 上有leakage。
其實我是不擔心算法問題。
畢竟那是自 2000 年至2009 年間,經過 N 個學者改良的,我跟lingyu 討論過這個算法,目前應該是很強悍的。

=====
後記:
果然瞬間覺得自己很丟臉。
sessiondiy 大人不記小人過,哈,就像上次我們在討論那個crackem II的時厚情況有點類似,我真是搞不清楚狀況。
我認錯,我會請教 lingyu 一些基本該要知道的觀念。
不過,真的還要大家幫忙回應這帖,畢竟我也想知道這算法有沒有漏洞。
我跟 lingyu 總會有看不見的盲點,您們參與,是促進我們成長的動力。
雪    币: 1001
活跃值: 活跃值 (31)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
lingyu 活跃值 1 2009-11-11 20:34
17
0
这文件我留意很久了,真是方便分析。
呵呵,sessiondiy兄看汇编和看报纸差不多,所以要想让程序不被爆破是不现实的。
雪    币: 117
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
wqshandian 活跃值 2009-11-12 09:56
18
0
看汇编和看报纸差不多,太强大了。。
雪    币: 2025
活跃值: 活跃值 (40)
能力值: ( LV9,RANK:180 )
在线值:
发帖
回帖
粉丝
sessiondiy 活跃值 4 2009-11-12 10:29
19
0
你们专业的都认为算法可靠了. 所以...
我认为给出源码由密码学小组来讨论,
应该比放在这里成为CM的意义及效果大
放这里只会改 jmp .  改了又会被笑. 就没人有兴趣看了.


回LS. 我不看报
雪    币: 1834
活跃值: 活跃值 (20)
能力值: ( LV3,RANK:30 )
在线值:
发帖
回帖
粉丝
yingyue 活跃值 2009-11-12 11:03
20
0
看见那堆 KEY ,不改 jmp 没人干,要不找火星人来看看
雪    币: 1806
活跃值: 活跃值 (39)
能力值: (RANK:420 )
在线值:
发帖
回帖
粉丝
rockinuk 活跃值 8 2009-11-12 11:14
21
0
我們沒有認為算法可靠。
但是目前卻找不出算法的漏洞,某種層面來說,是危險的。
我個人認為,不至於有人對 sessiondiy 改 jmp 的帖,露出大笑的訊息吧!?
會嗎? 不會吧。
雪    币: 1001
活跃值: 活跃值 (31)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
lingyu 活跃值 1 2009-11-12 11:25
22
0
其实这算法应该是不安全的,只不过暂时还没找到如:
已知g, y1=g^x mod p, y2=g^(x^2) mod p,
求x的难度肯定比求离散对数容易,但目前不清楚能不能求出x。
找了些论文都没结果,如果能求出x的话,这个KeygenMe就彻底破解了。
雪    币: 1001
活跃值: 活跃值 (31)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
lingyu 活跃值 1 2009-11-12 11:26
23
0
KEY看起来长,不过只是三个参数而已。
算法已经附上了,有兴趣可以看看。
雪    币: 2025
活跃值: 活跃值 (40)
能力值: ( LV9,RANK:180 )
在线值:
发帖
回帖
粉丝
sessiondiy 活跃值 4 2009-11-12 11:27
24
0
我是在示说此帖的本质是"算法"
如果改jmp也算是危险的话...那漏洞大了,
变成这论坛几乎所有人都会破这个CM.
雪    币: 2025
活跃值: 活跃值 (40)
能力值: ( LV9,RANK:180 )
在线值:
发帖
回帖
粉丝
sessiondiy 活跃值 4 2009-11-12 11:29
25
0
对了.
就是要听各位大侠讨论这个
(虽然听不懂)

就像是RSA, 没有多少破解者能真正懂这玩意的内涵.
可是被论出来了. Cracker就会用计算器去算key了.
游客
登录 | 注册 方可回帖
返回