首页
社区
课程
招聘
问答 CTF 排行榜 知识库 工具下载 看雪峰会 看雪商城 证书查询
  1. 看雪社区
  2. 软件逆向
    3. 发新帖
[原创]第二题算法－－拨开乌云见月明
2008-10-7 14:33 6488

[原创]第二题算法－－拨开乌云见月明

lelfei 活跃值
23
2008-10-7 14:33
6488
第二题算法－－拨开乌云见月明

怎么找算法位置的过程就略过了，算法会先计算用户名是否为a-y这25个小写字母，长度是否为12。然后用二重循环比较了一下大小，并统计了各字符的大小顺序，保存到数组tbNO[]中。这里会要求用户名中不能有重复的字符。再对注册码进行了转换，要求为0－3这四种数字，长度不小于53。

然后进入到注册码变换过程。我花了N长时间把这个过程用VB描述了一下：

Private Function CheckKey(UN As String, SN As String) As String
    Dim i As Long, j As Long, k As Long, l As Long
    Dim nRowCount As Long, n108 As Long, n10C As Long, n110 As Long, n114 As Long, n118 As Long, n11C As Long, n120 As Long, n124 As Long
    Dim tbTemp40(MAXLEN - 1) As Long
    Dim tbTemp100(100) As Long
    
    
    Dim tbRet(MAXLEN * 2) As Byte '返回字符串
    Dim tbSN(53) As Long '注册码
    Dim tbNO(MAXLEN - 1) As Long '用户名各字符的大小顺序
    
    
    '----init table------
    '这一段是我添加的，作用是对用户名和注册码进行转换。
    For i = 1 To Len(UN)
        For j = 1 To Len(UN)
            If Mid$(UN, i, 1) > Mid$(UN, j, 1) Then
                tbNO(i - 1) = tbNO(i - 1) + 1
            End If
        Next
    Next
    
    
    For i = 1 To Len(SN)
        tbSN(i - 1) = Val(Mid$(SN, i, 1))
        If i > 53 Then Exit For
    Next
    '--------------------
    
    '4022AC:
    i = 0
    j = 0
    k = 0
    l = 0
    
    '4022C8:
    Do Until i >= MAXLEN
        tbTemp40(i) = &H1E
        i = i + 1
    Loop
    
    nRowCount = 0
    n108 = 0
    
    If tbSN(0) > 0 Then
        nRowCount = MAXLEN \ tbSN(0)
    End If
    
    n10C = 0
    
    '40231B:
    Do Until n108 >= 2
        
        If n10C > 0 Then
            tbTemp40(tbNO(n10C - 1)) = &H1E
        End If
        
        n10C = 0
        
        '402350:
        Do Until n10C >= MAXLEN
            
            If n10C > 0 Then
                tbTemp40(tbNO(n10C - 1)) = &H1E
            End If
            
            If n108 = 0 Then
                tbTemp40(tbNO(n10C)) = &H28
                n10C = n10C + 1
            End If
            
            If n108 = 1 Then
                tbTemp40(tbNO(n10C)) = &H14
                n10C = n10C + 1
            End If
            
            '4023D3:
            k = 0
            For i = 0 To tbSN(0) - 1
                For j = 0 To nRowCount - 1
                    tbTemp100(i * 4 + j) = tbTemp40(k)
                    k = k + 1
                Next
            Next
            
            '402448:
            n110 = 0
            n114 = 0
            For i = 0 To nRowCount - 1
                n110 = tbTemp100(tbSN(1) * 4 + i) + n110
                n114 = tbTemp100(tbSN(2) * 4 + i) + n114
            Next
            
            '4024BD:
            If n110 = n114 Then '==============================================================================================
                If (tbTemp100(tbSN(3) * 4 + tbSN(4))) = (tbTemp100(tbSN(5) * 4 + tbSN(6))) Then
                    
                    If (tbTemp100(tbSN(7) * 4 + tbSN(8))) = (tbTemp100(tbSN(9) * 4 + tbSN(10))) Then
                        tbRet(l) = &H6C '"l"
                        l = l + 1
                    Else
                        tbRet(l) = &H6B '"k"
                        l = l + 1
                    End If
                    
                Else
                    
                    If (tbTemp100(tbSN(7) * 4 + tbSN(8))) = (tbTemp100(tbSN(9) * 4 + tbSN(10))) Then
                        tbRet(l) = &H6A '"j"
                        l = l + 1
                    Else
                        tbRet(l) = &H69 '"i"
                        l = l + 1
                    End If
                    
                End If
            End If
            
            '4025B9:
            If n110 > n114 Then '==============================================================================================
                i = 0
                n118 = 0
                n11C = 0
                
                tbTemp100(tbSN(1) * 4 + tbSN(11)) = tbTemp100(tbSN(12) * 4 + tbSN(13))
                tbTemp100(tbSN(1) * 4 + tbSN(14)) = tbTemp100(tbSN(15) * 4 + tbSN(16))
                tbTemp100(tbSN(1) * 4 + tbSN(17)) = tbTemp100(tbSN(18) * 4 + tbSN(19))
                tbTemp100(tbSN(2) * 4 + tbSN(20)) = tbTemp100(tbSN(21) * 4 + tbSN(22))
                tbTemp100(tbSN(2) * 4 + tbSN(23)) = tbTemp100(tbSN(24) * 4 + tbSN(25))
                tbTemp100(tbSN(2) * 4 + tbSN(26)) = tbTemp100(tbSN(27) * 4 + tbSN(28))
                
                '402712:
                For i = 0 To nRowCount - 1
                    n118 = tbTemp100(tbSN(1) * 4 + i) + n118
                    n11C = tbTemp100(tbSN(2) * 4 + i) + n11C
                Next
                
                If n118 > n11C Then '--------------------------------------------------------------------------
                    If (tbTemp100(tbSN(29) * 4 + tbSN(30))) = (tbTemp100(tbSN(31) * 4 + tbSN(32))) Then
                        tbRet(l) = &H65 '"e"
                        l = l + 1
                    Else
                        tbRet(l) = &H61 '"a"
                        l = l + 1
                    End If
                End If
                
                '4027D7:
                If n118 < n11C Then '--------------------------------------------------------------------------
                    If (tbTemp100(tbSN(33) * 4 + tbSN(34))) > (tbTemp100(tbSN(35) * 4 + tbSN(36))) Then
                        tbRet(l) = &H67 '"g"
                        l = l + 1
                    End If
                    
                    If (tbTemp100(tbSN(33) * 4 + tbSN(34))) < (tbTemp100(tbSN(35) * 4 + tbSN(36))) Then
                        tbRet(l) = &H66 '"f"
                        l = l + 1
                    End If
                    
                    If (tbTemp100(tbSN(33) * 4 + tbSN(34))) = (tbTemp100(tbSN(35) * 4 + tbSN(36))) Then
                        tbRet(l) = &H68 '"h"
                        l = l + 1
                    End If
                End If
                
                '4028DF:
                If n118 = n11C Then '--------------------------------------------------------------------------
                    k = 0
                    For i = 0 To tbSN(0) - 1
                        For j = 0 To nRowCount - 1
                            tbTemp100(i * 4 + j) = tbTemp40(k)
                            k = k + 1
                        Next
                    Next
                    
                    '402966:
                    If (tbTemp100(tbSN(37) * 4 + tbSN(38))) > (tbTemp100(tbSN(39) * 4 + tbSN(40))) Then
                        tbRet(l) = &H62 '"b"
                        l = l + 1
                    End If
                    
                    If (tbTemp100(tbSN(37) * 4 + tbSN(38))) < (tbTemp100(tbSN(39) * 4 + tbSN(40))) Then
                        tbRet(l) = &H63 '"c"
                        l = l + 1
                    End If
                    
                    If (tbTemp100(tbSN(37) * 4 + tbSN(38))) = (tbTemp100(tbSN(39) * 4 + tbSN(40))) Then
                        tbRet(l) = &H64 '"d"
                        l = l + 1
                    End If
                End If
            End If
            
            '402A5C:
            If n110 < n114 Then '==============================================================================================
                i = 0
                n120 = 0
                n124 = 0
                
                tbTemp100(tbSN(1) * 4 + tbSN(11)) = tbTemp100(tbSN(12) * 4 + tbSN(13))
                tbTemp100(tbSN(1) * 4 + tbSN(14)) = tbTemp100(tbSN(15) * 4 + tbSN(16))
                tbTemp100(tbSN(1) * 4 + tbSN(17)) = tbTemp100(tbSN(18) * 4 + tbSN(19))
                tbTemp100(tbSN(2) * 4 + tbSN(20)) = tbTemp100(tbSN(21) * 4 + tbSN(22))
                tbTemp100(tbSN(2) * 4 + tbSN(23)) = tbTemp100(tbSN(24) * 4 + tbSN(25))
                tbTemp100(tbSN(2) * 4 + tbSN(26)) = tbTemp100(tbSN(27) * 4 + tbSN(28))
                
                '402BB5:
                For i = 0 To nRowCount - 1
                    n120 = tbTemp100(tbSN(1) * 4 + i) + n120
                    n124 = tbTemp100(tbSN(2) * 4 + i) + n124
                Next
                
                '402C0F:
                If n120 > n124 Then '--------------------------------------------------------------------------
                    If (tbTemp100(tbSN(41) * 4 + tbSN(42))) > (tbTemp100(tbSN(43) * 4 + tbSN(44))) Then
                        tbRet(l) = &H66 '"f"
                        l = l + 1
                    End If
                    
                    If (tbTemp100(tbSN(41) * 4 + tbSN(42))) < (tbTemp100(tbSN(43) * 4 + tbSN(44))) Then
                        tbRet(l) = &H67 '"g"
                        l = l + 1
                    End If
                    
                    If (tbTemp100(tbSN(41) * 4 + tbSN(42))) < (tbTemp100(tbSN(43) * 4 + tbSN(44))) Then
                        tbRet(l) = &H68 '"h"
                        l = l + 1
                    End If
                End If
                
                '402D17:
                If n120 < n124 Then '--------------------------------------------------------------------------
                    If (tbTemp100(tbSN(45) * 4 + tbSN(46))) = (tbTemp100(tbSN(47) * 4 + tbSN(48))) Then
                        tbRet(l) = &H65 '"e"
                        l = l + 1
                    Else
                        tbRet(l) = &H61 '"a"
                        l = l + 1
                    End If
                End If
                
                '402D8B:
                If n120 = n124 Then '--------------------------------------------------------------------------
                    k = 0
                    For i = 0 To tbSN(0) - 1
                        For j = 0 To nRowCount - 1
                            tbTemp100(i * 4 + j) = tbTemp40(k)
                            k = k + 1
                        Next
                    Next
                    
                    '402E12:
                    If (tbTemp100(tbSN(49) * 4 + tbSN(50))) > (tbTemp100(tbSN(51) * 4 + tbSN(52))) Then
                        tbRet(l) = &H63 '"c"
                        l = l + 1
                    End If
                    
                    If (tbTemp100(tbSN(49) * 4 + tbSN(50))) < (tbTemp100(tbSN(51) * 4 + tbSN(52))) Then
                        tbRet(l) = &H62 '"b"
                        l = l + 1
                    End If
                    
                    If (tbTemp100(tbSN(49) * 4 + tbSN(50))) = (tbTemp100(tbSN(51) * 4 + tbSN(52))) Then
                        tbRet(l) = &H64 '"d"
                        l = l + 1
                    End If
                End If
            End If
            
        Loop
        
        n108 = n108 + 1
    Loop
    
    CheckKey = StrConv(tbRet, vbUnicode)
End Function


这时候可以发现有个地方的比较重复了，字符"g"和"h"计算了二次。

别看这段代码这么长，每次循环只会用到很小一个分支，只输出一个字符。

我盯着这段代码看了一整天（功力有限啊），才算是明白大概意思是生成一个3*4填充为0x1E=30的表格，每次循环把表格中的用户名各字符的大小顺序位变换成0x28=40或0x14=20，再判断某些位置的规则，符合其中某条时就将输入一个字符。最后循环24次后生成一个24字节的字符串返回。

返回后会对生成的24字节字符串分二组再次统计各字符的大小顺序，当这二组顺序值与用户名的顺序值tbNO[]都相同时则注册成功。

观察规律可以发现，如果把注册码某些位按规则设置，这个算法是恒成立的！（前提是把其中那个重复的判断修改掉）

于是输入用户名为abcdefghijkl，构造注册码使输入的字符串为abcdefghijklabcdefghijkl，我最后得到的注册码为30120212220111212313121222323000101020102010200010102，这就是这个程序的通用注册码。

对这个注册码简单解释一下：
第1位表示表格的行数，按程序算法中使用的数据看必须为3*4的表格，因此行数必须为3。
第2，3位表示统计每行和值时使用的行号。当输出字符为i,j,k,l时表格第3行值会被更换，但统计和值时要求这二行的和值相同，因此这二个行号必须为第一行与第二行，即这二位的值为0，1。
后面部分按2位分组，每组都指定这个3*4表格的一个行列坐标点。

测试用户名abcdefghijkl和abcghijkldef等，注册码都用30120212220111212313121222323000101020102010200010102，全部通过。

到这里这个CM应该算是结束了，但是由于算法中修改了一个重复的比较，导致用户名又出现变数，当执行到那个比较时，可能会一次输出2个字符，也可能一个字符也没有。比如当使用abcdefgijklh时就会注册失败。

调试发现，当执行到那个重复的比较时，如果输入为g，输出则为gh；输入为h时则没有输出。因此用户名中的h必须紧跟在g之后，注册才能通过。

这是使用a-l这12个字符时的要求。如果扩展到所有合法字符，则要求变为：使用的12个字符中，大小顺序排第8的字符必须紧跟在大小顺序排第7的字符之后。

再总结一下对用户名的限制：
1.长度必须为12位。
2.必须为a-y之间的这25个小写字母。
3.用户名中不能有重复字符。
4.所使用的12个字符中，大小顺序排第8的字符必须紧跟在大小顺序排第7的字符之后。

给出NameGen的VB代码：


Private Function NameGen() As String
Dim i As Long, j As Long, iChar As Long
Dim i7 As Long, i8 As Long
Dim s As String, sTemp As String
Dim tbNO(MAXLEN - 1) As Long

    Randomize Timer
    
    '随机生成12位不重复字符
    For i = 0 To MAXLEN - 1
        iChar = 0
        Do Until iChar > 0
            iChar = Int(Rnd * 25) + 97
            For j = 0 To i - 1
                If iChar = Asc(Mid$(s, j + 1, 1)) Then
                    iChar = 0
                End If
            Next
        Loop
        
        s = s & Chr(iChar)
    Next
    
    '统计各字符的大小顺序
    For i = 1 To MAXLEN
        For j = 1 To MAXLEN
            If Mid$(s, i, 1) > Mid$(s, j, 1) Then
                tbNO(i - 1) = tbNO(i - 1) + 1
            End If
        Next
    Next
    
    '找到排第7和第8的字符位置
    For i = 0 To MAXLEN - 1
        If tbNO(i) = 6 Then i7 = i
        If tbNO(i) = 7 Then i8 = i
    Next
    
    If i7 + 1 <> i8 Then '当第8字符不在第7字符后时
        sTemp = Mid$(s, i8 + 1, 1) '取出第8字符
        s = Mid$(s, 1, i8) & Mid$(s, i8 + 2) '组合除第8字符的字符串
        If i7 > i8 Then i7 = i7 - 1 '调整第7字符的位置
        s = Mid$(s, 1, i7 + 1) & sTemp & Mid$(s, i7 + 2) '把第8字符插入到第7字符后
    End If
    
    NameGen = s
End Function


PS：看这个CM的标题为：拨开乌云见月明，恍然大悟：原来就是指用户名与注册码都被乌云遮住了，注册码为固定值，用户名才是真正的注册码！

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

收藏
点赞・7
打赏
分享
最新回复 (10)
冷血书生
雪    币： 443
活跃值： (200)
能力值： ( LV9，RANK：1140 )
在线值：
发帖
回帖
粉丝
私信
冷血书生 28 2008-10-7 15:49
2 楼
0
原来如此!!!!!!!!!!!!谢谢!!!!
mstwugui
雪    币： 503
活跃值： (80)
能力值： (RANK：280 )
在线值：
发帖
回帖
粉丝
私信
mstwugui 6 2008-10-7 15:58
3 楼
0
注册码不是固定值，也是可以变的
sskey
雪    币： 216
活跃值： (26)
能力值： ( LV4，RANK：50 )
在线值：
发帖
回帖
粉丝
私信
sskey 1 2008-10-7 16:55
4 楼
0
注册码不固定哈,有些地方是可变的,偶就提交了俩组不同的...........
lelfei
雪    币： 6051
活跃值： (1441)
能力值： ( LV15，RANK：1473 )
在线值：
发帖
回帖
粉丝
私信
lelfei 23 2008-10-7 17:09
5 楼
0
注册码不是固定的，但是是通用的，不需要列举多个吧？

所以这题的关键还是要找用户名的算法，这才是那片乌云。
lelfei
雪    币： 6051
活跃值： (1441)
能力值： ( LV15，RANK：1473 )
在线值：
发帖
回帖
粉丝
私信
lelfei 23 2008-10-7 17:10
6 楼
0
注册码不是固定的，但是是通用的，不需要列举多个吧？

所以这题的关键还是要找用户名的算法，这才是那片乌云。
mstwugui
雪    币： 503
活跃值： (80)
能力值： (RANK：280 )
在线值：
发帖
回帖
粉丝
私信
mstwugui 6 2008-10-7 17:16
7 楼
0
把这句话换个角度说也是对的
用户名不是固定的，但是是通用的

这一题实际上是两个strgen
netwind
雪    币： 7474
活跃值： (2689)
能力值： (RANK：520 )
在线值：
发帖
回帖
粉丝
私信
netwind 13 2008-10-7 17:20
8 楼
0
注册码有很多个,我列的图中有13个结点是进行比较的地方,每个结点字符互换可以得一组新的注册码
另外,移动3个球的地方,也可以互换得到新的注册码.
也就是天平左边和右边两个球换个位置就构成了新的注册码
ccfer
雪    币： 8191
活跃值： (4273)
能力值： ( LV15，RANK：2459 )
在线值：
发帖
回帖
粉丝
私信
ccfer 16 2008-10-7 17:27
9 楼
0
请用示例说明
netwind
雪    币： 7474
活跃值： (2689)
能力值： (RANK：520 )
在线值：
发帖
回帖
粉丝
私信
netwind 13 2008-10-7 17:34
10 楼
0
301 20 21 2022111212313120221322001101020102010200200102
看这个注册码，把20 和21 换个位置就又组新的了
301 21 20 2022111212313120221322001101020102010200200102

漏了,补充下,对于只判断等与不等的结点,两个字符互换可以得倒新的注册码
哎...我脑细胞也损失严重!

请ccfer大侠 审阅!
菜的懒猫
雪    币： 249
活跃值： (35)
能力值： ( LV6，RANK：90 )
在线值：
发帖
回帖
粉丝
私信
菜的懒猫 2 2008-10-7 18:51
11 楼
0
我提交的第二个注册码也就是互换了2个字符。不知道算不算通过。
游客
登录 | 注册 方可回帖
　回帖　 表情 雪币赚取及消费
高级回复
返回