Algorithm

[Algorithm] 01. 이진 검색 알고리즘 테스트 Binary Search Algorithm Test (python)

hackyu 2018. 8. 25. 22:19

워게임 사이트에서 문제를 풀면서 블라인드 SQL Injection으로 패스워드를 찾는 과정에서 python을 이용하여 문제를 푸는 과정을 반복하게 되는 일이 생겼다. 아직 파이썬이라는 언어에 대해서 자신있게 사용하기 보다는 아는것만 활용할 수 있는 정도에 수준이지만, 효율적으로 패스워드를 찾기 위해 이진검색(Binary Search)라는 알고리즘을 이용하면 좋겠다라고 생각하였다.


이진검색 알고리즘에 대해서 간략하게 설명한다면, "어떤 범위내의 시작 값과 마지막 값이 존재하고 그 사이의 중간값(평균값)을 기준으로 반복적으로 비교하며 찾고자 하는 값의 위치를 찾는 것"이라고 '수알못'이 조심스럽게 정리를 할 수 있다.


ex) "Start 부터 End 까지 원하는 숫자가 위치하는 곳을 알아야 한다."


순차검색: 찾고자 하는 값과 일치할 때 까지 Start ~ End를 순차적으로 검색하고 비교해야함.

이진 검색: log 2^N 횟수 내 검색하여 비교함.


1~100까지의 범위에서 원하는 값을 찾는 경우(Start:1, End:100)


순차검색으로는 원하는 값을 찾기 위해서는 100번을 검색하고 비교하여 원하는 값 찾기 가능 1,2,3,4,5,6,..........100 

이진 검색을 이용할 시에는 1~100의 범위를 포함하는 최소 2의 지수 N=7이라면 log 2^7 즉, 7번 검색 내 찾기 가능


위키피디아에도 이진검색에 대해서 정리가 되어있고, Pseudo Code와 파이썬에서 지원하는 binarySearch 함수가 정의된 것을 볼 수 있다.


위키피디아 이진검색 알고리즘https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%EA%B2%80%EC%83%89_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98


아래의 python 코드는 지정한 임의의 범위 내 패스워드 길이 및 패스워드를 랜덤값으로 설정한 이후, 이진검색을 활용하여 패스워드의 길이와 패스워드를 찾는 코드를 작성한 것이다. 해당 코드에서 중요하게 봐야 할 부분은 아스키 글자로 이루어진 문자열의 한 문자당 표현할 수 있는 범위(0 ~ 255, 0x00 ~ 0x100)의 값으로 구한다는 것이다. 코드를 직접 작성해보면서 이진검색에 대해서 조금이나마 이해를 할 수 있었고, 문제를 해결하는데 알고리즘을 이용하는 습관을 들여 적당할 때 유용하게 쓰였으면 좋겠다. 참고로 패스워드의 랜덤 값으로 사용되는 값은 아래와 같다.

 




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#Code Written by hackyu
#Binary Search Algorithm Test
 
import random
import string
 
#Used Variables 
rand = random.randrange(1,17) # rand value length
start = 1
end = 0x20
password = ""
password_length=0
find_password = "" 
random_list = string.printable
while_break = 0
find_password_length_error_count = 0
 
#Password Initial
for i in range(0,rand):
    password += random.choice(random_list)
 
 
#Find password length
print "PASSWORD LENGTH:",len(password),"\n","PASSWORD:",password,"\n"
print "--------------------------------------------------------\nFind PASSWORD LENGTH PROCESS\n--------------------------------------------------------"
  
while True:
    if while_break == 1:
        break
    
    mid = (start + end) / 2 
    print "start:%d mid:%d end:%d" % (start, mid, end)
 
    #looting start:1 mid:1 end:1
    if start == 1 and mid == 1 and end == 1:
        find_password_length_error_count += 1
        if find_password_length_error_count >= 5:
            start = 1
            end = 0x100
            mid = (start + end) / 2 
 
    # UP
    if len(password) <= mid:
        if len(password) == mid:
            password_length = mid
            print "Find password length:",mid,"\n"
            while_break = 1
        end = mid
 
    # DOWN
    elif len(password) >= mid:
        if start == len(password):
            password_length = mid
            print "Find password length:",mid,"\n"
            while_break = 1
            
        start = mid
 
 
 
#Find password
print "--------------------------------------------------------\nFind PASSWORD PROCESS\n--------------------------------------------------------"
i = 0
while True: # while start
 
    start = 0x00
    end = 0x100 # string.printable range 0 ~ 255
 
    if len(find_password) == len(password):
        print "--------------------------------------------------------"
        print "[END!!!!!!!!!]"
        print "Find PASSWORD LENGTH:",password_length
        print "Find PASSWORD:",password
        print "--------------------------------------------------------"
print password
        print password_length
        exit()
 
    while True:
        mid = (start + end) / 2
        print "start:%d mid:%d end:%d" % (start, mid, end)
 
        if ord(password[i]) <= mid:     
            if ord(password[i]) == mid:
                print "find index:%d value:%c" % (i, mid)
                find_password = find_password+chr(mid)
                print find_password,"\n"
                break
            
            end = mid #end if 
        
        elif ord(password[i]) >= mid:
            if ord(password[i]) == mid:
                print "find index:%d value:%c" % (i, mid)
                find_password = find_password+chr(mid)
                print find_password,"\n"
                break
            
            start = mid #end elif 
            
 
    i=i+1 

cs