안녕하세요, 계략입니다.
지난 번 알고리즘에 대해서 간략하게 설명을 해 봤습니다.
대부분 잘 읽어주셨다니 다행입니다 :)
분량이 짧다고 하시는 분도 계셨습니다. 아무래도 한 알고리즘에 대해 다루는 글이 아니라 짧게 쓰였던 것 같네요.
- 알고리즘에 대해서 간략하게만 다루는 게시글입니다.
- 비전공자들도 쉽게 이해할 수 있도록 작성해 보았습니다.
- 틀린 내용이 있으면 지적해주시면 감사하겠습니다. 틀린 내용에 대해서는 책임지지 않습니다.
그러면, 잘 부탁드리겠습니다!
저번 시간에 다뤘던 내용은,
'알고리즘' 이란?
이었습니다.
https://steemit.com/kr/@gyeryak/1
알고리즘에 대해서 다루기 전에, 알고리즘이 무엇인지에 대해 다뤄 보았죠.
- 알고리즘은 '문제를 해결하기 위해 사용하는 방식'이다.
- 같은 문제라도 여러가지 알고리즘이 존재할 수 있다.
- 알고리즘을 생각할 때는 효율도 같이 생각해야 한다.
라고 요약을 할 수 있었습니다.
이번 시간에는 가장 간단한, 다시 말하다면 단순무식한 알고리즘을 다뤄 볼 예정입니다.
앞서 나왔던 '효율'의 측면에서 설명하자면,
- 구현 난이도: 문제에 따라 다르지만 대부분 쉬운 편
- 작동 시간: 거의 모든 문제에서 매우 김
- 메모리 사용량: 대부분의 문제에서 매우 큼
이라는 상당히 떨어지는 효율을 가지고 있습니다.
그런데도 왜 이런 알고리즘을 사용하는지, 디테일한 단점은 무엇이 있는지 등에 대해서 더 자세하게 알아봅시다.
이번 시간에 다룰 내용은,
브루트 포스(Brute Force)
입니다.
Brute: 짐승, 동물
Force: 힘
이름에서 느껴지듯, 매우 단순무식한 알고리즘입니다.
문제를 해결하기 위해서,
가능한 모든 경우에 대해 모두 직접 해 보는 방법입니다.
지난 시간의 예시를 가져 와 볼게요.
'1부터 100까지의 합을 구하라'
이 문제에 대해서
1부터 100까지 모두 직접 더한다
와 같은 풀이가 브루트 포스의 예시가 되는 것입니다.
그림에서 볼 수 있듯, 만드는 방법은 매우 간단할 것입니다.
1부터 100까지 차례대로 더해 나가면서 값을 바꾸면 되죠.
그리고, 컴퓨터는 사람들보다는 계산이 빠를 테고, 100까지 다 더하는 데는 시간도 얼마 안 걸릴 것입니다.
하지만, 브루트 포스의 문제점은 숫자가 커지면서 발생합니다.
만약 1부터 100까지가 아닌, 1부터 1000억까지 더한다고 해 봅시다.
숫자 하나를 더하면서 1번의 연산을 하는데, 1000억까지 다 일일이 더해준다면 1000억 번 계산을 하게 되겠죠.
일반적으로 컴퓨터는 1초에 약 1억 번의 연산이 가능합니다.
물론 컴퓨터마다, 프로그래밍 언어마다, 주어진 상황마다 크게 달라질 것입니다.
그래도 앞으로는 1초에 1억 번 연산이라고 가정하고 설명하겠습니다.
그렇다면, 저 문제를 브루트 포스로 해결한다면
1000초 = 약 17분이나 걸리게 됩니다.
단순 더하기 문제인데 말이죠.
브루트 포스를 뉴스 기사 같은 곳에서 접하신 분들도 있으실 겁니다.
*** 사이트, 브루트 포스 공격에 비밀번호 유출되어 같은 기사 말이죠.
그렇다면, 저 사이트가 얼마나 문제가 심각한 것인지 알아봅시다.
브루트 포스로 비밀번호를 알아낸다고 해 봅시다.
지금은 특수문자도 의무적으로 입력하는 사이트도 많지만, 소문자+숫자만 입력이 가능하다고 해 봅시다.
그러면 소문자 26글자(a~z)에 숫자 10글자(0~9) 해서 총 36글자가 될 것입니다.
만약에 암호가 1글자로 되어 있을 경우, 36번만 입력해 보면 되겠죠.
문제는 암호가 2글자가 넘어갈 경우입니다.
2가지가 넘어가면 약간 복잡해집니다.
앞의 글자가 되는 경우의 수가 36가지가 있고, 각각의 경우마다 뒤 글자가 나오는 경우가 36가지가 됩니다.
문자까지 들어가서 복잡하게 생각하실 수 있으니 단순하게 숫자(0~9)만 사용하는 것을 생각해 봅시다.
1자리의 경우는,
0,1,2,3,4,5,6,7,8,9
총 10가지가 되겠죠.
2자리가 되면
00,01,02,03,04,05,06,07,08,09,10,11,...,89,90,91,92,93,94,95,96,97,98,99
해서 총 100개가 나옵니다.
이 100이라는 수는 10*10을 해서 나온 숫자입니다.
3자리가 된다면? 1000개가 되겠죠.
다시 암호로 넘어간다면, 2자리가 됬을 때는 36*36 = 1296가지입니다.
3자리는 46656, 4자리는 1679616, 5자리는 60466176, 6자리는 2176782336.
이런 식으로 숫자가 기하급수적으로 커질 겁니다.
6자리의 경우는, 1초에 암호를 1억 번 확인한다고 했을 경우 22초 가량이 걸릴 것입니다.
6자리 비밀번호는 별다른 보안 장치가 없다면 22초만에 뚫리는 것이죠.
하지만 이런 문제점은 간단하게 막을 수 있습니다.
암호를 5번 틀리면 5분가량 암호를 입력할 수 없다고 해 보죠.
그러면 1분에 1개 꼴로 확인할 수 있는 셈이 됩니다.
이렇게 되면 6자리 암호를 뚫는 데 걸리는 시간은 69년이 됩니다.
저런 안전장치 하나만 있다면, 22초에서 69년이 되는 겁니다.
아마도, 브루트 포스에 해킹을 당한 사이트는 그런 안전장치가 없거나, 그 안전장치를 제거할 방법이 있었을 것입니다.
다시 브루트 포스 알고리즘의 얘기로 돌아와 봅시다.
암호의 예시에서 보았듯, 숫자(자릿수 등)이 커지면 대입해봐야 할 경우의 수가 매우 커집니다. 기하급수적으로요.
1초에 1억번 연산으로 6자리는 22초가 걸리지만, 10자리만 되어도 14개월이 걸립니다.
문제가 조금만 더 복잡해지면, 숫자가 조금 커질수록 엄청나게 많은 시간이 걸립니다.
그래서 브루트 포스 알고리즘은 시간 측면에서 매우 비효율적입니다.
하지만, 브루트 포스 알고리즘은 그만큼 만들기가 쉬운 편입니다.
모두 다 해보게 하면 되니깐요. (문제에 따라 어려운 경우도 있기는 합니다)
그것보다도 브루트 포스 알고리즘의 장점은 다른 데 있습니다.
다른 알고리즘을 생각하기에 앞서 도움이 됩니다.
가령, 브루트 포스 알고리즘으로 암호를 생각한다고 할 때,
몇몇 사전에 있는 단어나 iloveyou, password, 1234 등은 따로 해보도록 할 수 있겠죠.
이런식으로 조금 더 발전된 알고리즘을 생각하는 출발점이 됩니다.
정리
브루트 포스 알고리즘은 모든 경우를 직접 하는 알고리즘이다.
브루트 포스 알고리즘은 시간 면에서 매우 비효율적인 알고리즘이다.
다만 그만큼 만들기도 쉽고, 다른 알고리즘을 생각하는 출발점이 된다.
사실, 1부터 X까지 더하는 문제는 브루트 포스의 예시라고 보기 힘들긴 합니다.
다만 다 해본다는 측면에서 유사성이 있고, 쉬운 예시라서 넣었습니다.
보안 관련 기사에서 보셨을 법한 '브루트 포스' 알고리즘이었습니다.
읽기 불편하거나, 이해하기 어려운 점, 틀린 부분 등은 알려주시면 개선해보도록 하겠습니다.
읽어주셔서 감사합니다.
한 주의 주말이 다 끝나갑니다.
모두 행복한 새로운 한 주 되셨으면 합니다. :)