首页
社区
课程
招聘
问答 CTF 排行榜 知识库 工具下载 峰会 看雪商城 证书查询
  1. 社区
  2. CTF对抗
    3. 发新帖
[原创]新手加密算法入门(一)--RSA手记
发表于: 2006-6-10 02:42 28220

[原创]新手加密算法入门(一)--RSA手记

Ryosuke 活跃值
24
2006-6-10 02:42
28220

【作者】ryOsUkE
转载请注明出处来自看雪论坛，以及本文的完整性，谢谢！

最近偷了点闲，再加上得到了一些很不错的Keygenme，想写一个加密算法的入门手记，以飨各位破解爱好者，便于学习交流。

闲话少说，先从RSA说起。
RSA公钥密码是1977年由Ron Rivest、Adi Shamirh和LenAdleman在MIT(美国麻省理工学院〉开发的,1978年首次公布[RIVE78]。它是目前最有影响的公钥加密算法,它能够抵抗到目前为止已知的所有密码攻击。目前它已被ISO推荐为公钥数据加密标准。RSA算法基于一个十分简单的数论事实:将两个大素数相乘十分容易,但是想分解它们的乘积却极端困难,因此可以将乘积公开作为加密密钥。
RSA的算法结构相当简单,整个算法可以描述如下:
(1)选取两个大素数p和q(保密);
(2)计算n=p*q(公开),r=(p-1〉(q-1)(保密);
(3)随机选取整数e(公开,加密密钥),使得gcd(e,r)=1;
(4)计算d(保密,私人密钥),使得ed≡1(mod r),即d=e^-1(mod r);
(5)加密:c=m^e mod n;
(6)解密:m=c^d mod n.

Keygenme见附件，采用了miracl库编程，图方便，自己手工定位找miracl函数了。
【分析】
根据信息来到
004010D6   > \8DBC24 800000>lea     edi, [esp+80]
004010DD   .  83C9 FF       or      ecx, FFFFFFFF
004010E0   .  33C0          xor     eax, eax
004010E2   .  33D2          xor     edx, edx
004010E4   .  F2:AE         repne   scas byte ptr es:[edi]
004010E6   .  F7D1          not     ecx
004010E8   .  49            dec     ecx        ;计算name的长度
004010E9   .  C74424 10 000>mov     dword ptr [esp+10], 0
004010F1   .  85C9          test    ecx, ecx
004010F3   .  7E 3D         jle     short 00401132        ;name长度大于0
004010F5   >  0FBE8C14 8000>movsx   ecx, byte ptr [esp+edx+80]
004010FD   .  8BC1          mov     eax, ecx
004010FF   .  8DBC24 800000>lea     edi, [esp+80]
00401106   .  C1E0 04       shl     eax, 4
00401109   .  03C1          add     eax, ecx
0040110B   .  C1E0 04       shl     eax, 4
0040110E   .  03C1          add     eax, ecx
00401110   .  C1E0 04       shl     eax, 4
00401113   .  03C1          add     eax, ecx
00401115   .  8B4C24 10     mov     ecx, [esp+10]
00401119   .  42            inc     edx
0040111A   .  8D0480        lea     eax, [eax+eax*4]
0040111D   .  8D0441        lea     eax, [ecx+eax*2]
00401120   .  83C9 FF       or      ecx, FFFFFFFF
00401123   .  894424 10     mov     [esp+10], eax
00401127   .  33C0          xor     eax, eax
00401129   .  F2:AE         repne   scas byte ptr es:[edi]
0040112B   .  F7D1          not     ecx
0040112D   .  49            dec     ecx
0040112E   .  3BD1          cmp     edx, ecx
00401130   .^ 7C C3         jl      short 004010F5
//以上是变换name=>dwName
00401132   >  6A 00         push    0
00401134   .  E8 77060000   call    004017B0        ;mirvar(0)
00401139   .  6A 00         push    0
0040113B   .  8BF0          mov     esi, eax
0040113D   .  E8 6E060000   call    004017B0        ;mirvar(0)
00401142   .  6A 00         push    0
00401144   .  8BD8          mov     ebx, eax
00401146   .  E8 65060000   call    004017B0        ;mirvar(0)
0040114B   .  6A 00         push    0
0040114D   .  8BE8          mov     ebp, eax
0040114F   .  E8 5C060000   call    004017B0        ;mirvar(0)
00401154   .  894424 28     mov     [esp+28], eax
00401158   .  8D7C24 2C     lea     edi, [esp+2C]
0040115C   .  83C9 FF       or      ecx, FFFFFFFF
0040115F   .  33C0          xor     eax, eax
00401161   .  83C4 10       add     esp, 10
00401164   .  33D2          xor     edx, edx
00401166   .  F2:AE         repne   scas byte ptr es:[edi]
00401168   .  F7D1          not     ecx
0040116A   .  49            dec     ecx
0040116B   .  85C9          test    ecx, ecx
0040116D   .  7E 37         jle     short 004011A6
0040116F   >  8A4414 1C     mov     al, [esp+edx+1C]
00401173   .  3C 41         cmp     al, 41
00401175   .  7C 04         jl      short 0040117B
00401177   .  3C 5A         cmp     al, 5A
00401179   .  7E 18         jle     short 00401193
0040117B   >  3C 61         cmp     al, 61
0040117D   .  7C 04         jl      short 00401183
0040117F   .  3C 7A         cmp     al, 7A
00401181   .  7E 10         jle     short 00401193
00401183   >  3C 30         cmp     al, 30
00401185   .  0F8C D7000000 jl      00401262
0040118B   .  3C 39         cmp     al, 39
0040118D   .  0F8F CF000000 jg      00401262
00401193   >  8D7C24 1C     lea     edi, [esp+1C]
00401197   .  83C9 FF       or      ecx, FFFFFFFF
0040119A   .  33C0          xor     eax, eax
0040119C   .  42            inc     edx
0040119D   .  F2:AE         repne   scas byte ptr es:[edi]
0040119F   .  F7D1          not     ecx
004011A1   .  49            dec     ecx
004011A2   .  3BD1          cmp     edx, ecx
004011A4   .^ 7C C9         jl      short 0040116F
//serial的格式认证
004011A6   >  8B5424 14     mov     edx, [esp+14]
004011AA   .  8B7C24 18     mov     edi, [esp+18]
004011AE   .  8D4424 1C     lea     eax, [esp+1C]
004011B2   .  50            push    eax        ;serial
004011B3   .  57            push    edi        ;big sn
004011B4   .  C782 38020000>mov     dword ptr [edx+238], 3C ;60进制
004011BE   .  E8 CD240000   call    00403690  ;cinstr
004011C3   .  8B4C24 1C     mov     ecx, [esp+1C]
004011C7   .  68 CCC04000   push 0040C0CC     ;ASCII "7E2BDC8ED8856EE745A9D6F93E143B7ACE202999"
004011CC   .  56            push    esi        ;RSA中的N
004011CD   .  C781 38020000>mov     dword ptr [ecx+238], 10 ;16进制
004011D7   .  E8 B4240000   call    00403690     ;cinstr
004011DC   .  68 C4C04000   push    0040C0C4     ;  ASCII "10001"
004011E1   .  53            push    ebx        ;RSA中的E
004011E2   .  E8 A9240000   call    00403690  ;cinstr
//这里通过RSA2Tool计算，可以算出D=3FC69E031A914000E925FC61F2BF888F410EB07D
004011E7   .  55            push    ebp        ;c
004011E8   .  56            push    esi        ;n
004011E9   .  53            push    ebx        ;e
004011EA   .  57            push    edi        ;sn
004011EB   .  E8 90220000   call    00403480 ;powmod 计算c=sn^e mod n
004011F0   .  8D5424 44     lea     edx, [esp+44]
004011F4   .  6A 00         push    0
004011F6   .  52            push    edx
004011F7   .  55            push    ebp
004011F8   .  6A 00         push    0
004011FA   .  E8 F11C0000   call    00402EF0  ;big_to_bytes sn
004011FF   .  C64404 54 00  mov     byte ptr [esp+eax+54], 0
00401204   .  8B4424 54     mov     eax, [esp+54]
00401208   .  35 21433412   xor     eax, 12344321
0040120D   .  83C4 38       add     esp, 38
00401210   .  3D 670B7754   cmp     eax, 54770B67        ;big_to_bytes的前4位xor 12344321=54770B67
00401215   .  0F85 84000000 jnz     0040129F
0040121B   .  8B4C24 10     mov     ecx, [esp+10]
0040121F   .  8D9424 800000>lea     edx, [esp+80]
00401226   .  51            push    ecx         ;dwName
00401227   .  68 C0C04000   push    0040C0C0                         ;  ASCII "%0x"
0040122C   .  52            push    edx
0040122D   .  E8 7E500000   call    004062B0  ;sprintf  把dwName转成stringdwName       
00401232   .  83C4 0C       add     esp, 0C
00401235   .  8D4424 21     lea     eax, [esp+21]
00401239   .  8D8C24 800000>lea     ecx, [esp+80]
00401240   .  50            push    eax                              ; /String2  big_to_bytes从第六位开始的字符串
00401241   .  51            push    ecx                              ; |String1  stringdwName
00401242   .  FF15 08B04000 call    [<&KERNEL32.lstrcmpA>]           ; \lstrcmpA
00401248   .  85C0          test    eax, eax                                ;比较
0040124A   .  6A 00         push    0
0040124C   .  75 3D         jnz     short 0040128B
0040124E   .  8B9424 EC0000>mov     edx, [esp+EC]
00401255   .  68 B4C04000   push    0040C0B4                         ;  ASCII "Nice job"
0040125A   .  68 98C04000   push    0040C098                         ;  ASCII "Hey!!! Your key is GOOOOD"
0040125F   .  52            push    edx
00401260   .  EB 51         jmp     short 004012B3
00401262   >  8B8C24 E80000>mov     ecx, [esp+E8]
00401269   .  6A 00         push    0                                ; /Style = MB_OK|MB_APPLMODAL
0040126B   .  68 90C04000   push    0040C090                         ; |Title = "error"
00401270   .  68 7CC04000   push    0040C07C                         ; |Text = "Check your serial"
00401275   .  51            push    ecx                              ; |hOwner
00401276   .  FF15 B8B04000 call    [<&USER32.MessageBoxA>]          ; \MessageBoxA
0040127C   .  5F            pop     edi
0040127D   .  5E            pop     esi
0040127E   .  5D            pop     ebp
0040127F   .  33C0          xor     eax, eax
00401281   .  5B            pop     ebx
00401282   .  81C4 D4000000 add     esp, 0D4
00401288   .  C2 1000       retn    10

破解过程：
就是通过12344321 XOR 54770B67加上Name构造dwName=>stringdwName,做成RSA加密后的大数，然后用D进行解密，再还原成60进制字符就可以了，算法很简单，详情见注册机。

未完待续。。。


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

上传的附件：
收藏
免费 ・7
支持
分享
最新回复 (25)
CCDebuger
雪    币： 2506
活跃值： (1030)
能力值： (RANK：990 )
在线值：
发帖
回帖
粉丝
私信
2 楼
支持 Ryosuke 的系列文章！
2006-6-10 03:40
0
Ryosuke
雪    币： 370
活跃值： (78)
能力值： ( LV9，RANK：970 )
在线值：
发帖
回帖
粉丝
私信
3 楼
最初由 CCDebuger 发布
支持 Ryosuke 的系列文章！


谢谢CC兄，我一边看球一边写的，好累了，睡了。
2006-6-10 05:03
0
gkend
雪    币： 203
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
4 楼
"(5)加密:c=m^e mod n;
(6)解密:m=c^d mod n."
写错了还是笔误？应该是：
（5)加密:c=m^d mod n;
(6)解密:m=c^e mod n.
2006-6-10 08:26
0
Ryosuke
雪    币： 370
活跃值： (78)
能力值： ( LV9，RANK：970 )
在线值：
发帖
回帖
粉丝
私信
5 楼
最初由 gkend 发布
"(5)加密:c=m^e mod n;
(6)解密:m=c^d mod n."
写错了还是笔误？应该是：
（5)加密:c=m^d mod n;
(6)解密:m=c^e mod n.


应该没有错，你不妨找一本密码学的书看看。
2006-6-10 09:14
0
dongfeng
雪    币： 237
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
6 楼
很适合我啊,太感谢了.
2006-6-10 09:28
0
gkend
雪    币： 203
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
7 楼
最初由 Ryosuke 发布
应该没有错，你不妨找一本密码学的书看看。

不用看的，肯定你错了。有些不是靠死记的，而是要动脑子的。
RSA已经很熟。既然d(保密,私人密钥),那么肯定是加密时候用，如果解密用，那么岂不是要把D告诉别人？所以E是解密用（公钥）。
2006-6-10 09:56
0
hbqjxhw
雪    币： 313
活跃值： (250)
能力值： ( LV9，RANK：650 )
在线值：
发帖
回帖
粉丝
私信
8 楼
http://pediy.com/tutorial/chap6/Chap6-3-1.htm
不用争论，这里应该有杀伤力
2006-6-10 11:53
0
testyy
雪    币： 433
活跃值： (51)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
9 楼
学习学习
有球看，有知识学，还有笑话看 ，生活过得很滋润啊
2006-6-10 12:19
0
koala
雪    币： 222
活跃值： (40)
能力值： ( LV8，RANK：130 )
在线值：
发帖
回帖
粉丝
私信
10 楼
支持，顶
2006-6-10 12:26
0
4nil
雪    币： 313
活跃值： (440)
能力值： ( LV12，RANK：530 )
在线值：
发帖
回帖
粉丝
私信
11 楼
最初由 gkend 发布
不用看的，肯定你错了。有些不是靠死记的，而是要动脑子的。
RSA已经很熟。既然d(保密,私人密钥),那么肯定是加密时候用，如果解密用，那么岂不是要把D告诉别人？所以E是解密用（公钥）。

这个是keygenme,不是加密数据,公开密钥当然是别人加密,你解密.
e是encypt
d是decypt
不是很对么.哪里错了啊
2006-6-10 13:58
0
riijj
雪    币： 2319
活跃值： (565)
能力值： (RANK：300 )
在线值：
发帖
回帖
粉丝
私信
12 楼
RSA 的 public key (公钥) 是让别人加密资料，给我们
private key (私钥) 是用来把资料解密
2006-6-10 23:06
0
gkend
雪    币： 203
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
13 楼
最初由 4nil 发布
这个是keygenme,不是加密数据,公开密钥当然是别人加密,你解密.
e是encypt
d是decypt
不是很对么.哪里错了啊

前面说了不要生搬硬套，RSA最初目的是信息加密，只有用有私人密钥D才能对信息解密。而现在文中说的是Keygenme，那么应该是反过来，即用私人密钥D对用户名加密，然后用公钥E解密，只有拥有私人密钥D的人才有注册机。
举例：假如你的注册用户名为pediy,那么通过RSA注册机算注册码:
SN=(pediy)**D mod n
E作为公钥，放在程序中作为解密效验用，任何人只要有该程序都知道E。
username=(SN)**E mode n 最后判断解密的用户名是不是等于注册名。
2006-6-11 07:04
0
xiaowei
雪    币： 100
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
14 楼
对算法还不是很有研究  过段时间买本书研究一下
2006-6-11 08:15
0
Ryosuke
雪    币： 370
活跃值： (78)
能力值： ( LV9，RANK：970 )
在线值：
发帖
回帖
粉丝
私信
15 楼
最初由 gkend 发布
前面说了不要生搬硬套，RSA最初目的是信息加密，只有用有私人密钥D才能对信息解密。而现在文中说的是Keygenme，那么应该是反过来，即用私人密钥D对用户名加密，然后用公钥E解密，只有拥有私人密钥D的人才有注册机。
举例：假如你的注册用户名为pediy,那么通过RSA注册机算注册码:
SN=(pediy)**D mod n
E作为公钥，放在程序中作为解密效验用，任何人只要有该程序都知道E。
username=(SN)**E mode n 最后判断解密的用户名是不是等于注册名。

Keygenme中，你认为是加密过程也行，是解密过程也行。我是从一般人的角度看这个问题的，认为公开了一个0x10001，所以就是加密。但你认为是解密也可以，但是有一点，加密的话对应的是E,解密的话对应是D，反正破解RSA不是看这两个东西，是分解n=p*q的，分解了n，给了E,或者给D都能算出另外一个。加密解密是一个对立又统一的过程 一切都看你怎么理解了。所以这个问题不要再争了，你认为加密也好，解密也好，都是对的。但是c=m^e mod n,m=c^d mod n这个是没有错误的。
2006-6-11 09:43
0
gkend
雪    币： 203
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
16 楼
最初由 Ryosuke 发布
Keygenme中，你认为是加密过程也行，是解密过程也行。我是从一般人的角度看这个问题的，认为公开了一个0x10001，所以就是加密。但你认为是解密也可以，但是有一点，加密的话对应的是E,解密的话对应是D，反正破解RSA不是看这两个东西，是分解n=p*q的，分解了n，给了E,或者给D都能算出另外一个。加密解密是一个对立又统一的过程 一切都看你怎么理解了。所以这个问题不要再争了，你认为加密也好，解密也好，都是对的。但是c=m^e mod n,m=c^d mod n这个是没有错误的。

加密和解密绝对不能乱说的。
什么是加密？简单说就是把看得懂的变成别人看不懂的。
什么是解密？那就是把看不懂还原成能懂的。
显然，把看的懂注册名变成了看不懂的注册码过程是加密。
2006-6-11 10:41
0
Ryosuke
雪    币： 370
活跃值： (78)
能力值： ( LV9，RANK：970 )
在线值：
发帖
回帖
粉丝
私信
17 楼
最初由 gkend 发布
加密和解密绝对不能乱说的。
什么是加密？简单说就是把看得懂的变成别人看不懂的。
什么是解密？那就是把看不懂还原成能懂的。
显然，把看的懂注册名变成了看不懂的注册码过程是加密。


我只能说你把加密解密理解的太狭隘了。
2006-6-11 10:54
0
gkend
雪    币： 203
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
18 楼
最初由 Ryosuke 发布
我只能说你把加密解密理解的太狭隘了。

狭隘起码比你不懂好！
2006-6-11 11:04
0
Ryosuke
雪    币： 370
活跃值： (78)
能力值： ( LV9，RANK：970 )
在线值：
发帖
回帖
粉丝
私信
19 楼
最初由 gkend 发布
狭隘起码比你不懂好！


恩，欢迎你写一篇权威的RSA方面的东西。让大家受益一下
2006-6-11 11:11
0
kanxue
雪    币： 47147
活跃值： (20455)
能力值： (RANK：350 )
在线值：
发帖
回帖
粉丝
私信
20 楼
最初由 gkend 发布
狭隘起码比你不懂好！


提醒一下，请勿用攻击性的语言。就事论事，以理服人
2006-6-11 12:02
0
cpshow
雪    币： 202
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
21 楼
最初由 Ryosuke 发布
我只能说你把加密解密理解的太狭隘了。


同意，此所谓 "空寂既是色,色即是空" 也
2006-6-11 13:24
0
gkend
雪    币： 203
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
22 楼
只许州官放火，不许百姓点灯？
他说我狭隘，就可以？我说他不懂就不行？既然坛主认为“狭隘”可以，那么我也可以用了：只能说坛主对攻击性语言的理解是狭隘的。
2006-6-13 20:18
0
happytown
雪    币： 721
活跃值： (350)
能力值： ( LV9，RANK：1250 )
在线值：
发帖
回帖
粉丝
私信
23 楼
为了不和Ryosuke的CrackMe冲突，我就写一个haval的吧！
2006-6-13 20:51
0
逍遥风
雪    币： 2256
活跃值： (941)
能力值： (RANK：2210 )
在线值：
发帖
回帖
粉丝
私信
24 楼
期待happytown兄的作品
2006-6-13 21:01
0
happytown
雪    币： 721
活跃值： (350)
能力值： ( LV9，RANK：1250 )
在线值：
发帖
回帖
粉丝
私信
25 楼
今天就写，晚上放出。
2006-6-14 05:51
0
游客
登录 | 注册 方可回帖
回帖 表情 雪币赚取及消费
高级回复
返回
//