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

워게임 사이트에서 문제를 풀면서 블라인드 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)의 값으로 구한다는 것이다. 코드를 직접 작성해보면서 이진검색에 대해서 조금이나마 이해를 할 수 있었고, 문제를 해결하는데 알고리즘을 이용하는 습관을 들여 적당할 때 유용하게 쓰였으면 좋겠다. 참고로 패스워드의 랜덤 값으로 사용되는 값은 아래와 같다.

 

#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