Algorithm - Brute force(브루트 포스)

Brute force : 키 전수조사(exhaustive key search), 무차별 대입, 완전탐색 알고리즘

조합 가능한 모든 문자열을 하나씩 대입해 보는 방식으로 암호를 해독하는 방법. 흔히 암호학에서 연구되지만, 알고리즘 분야에서도 사용. (수학 문제를 원시적으로 푸는 방법인 '수 대입 노가다'의 학술적 버전) / 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져옴. 브루트 포스의 강력한 점은 예외없이 100%의 확률로 정답만을 출력한다.

 

Brute force 특징 :

brute-force는 "짐승같은(난폭한) 힘"의 뜻이고 오래 걸리는 데다 자원이 엄청나게 들어서 얼핏 보면 무식해보이지만, 항상 정확도 100%를 보장 한다는 것이 암호 해독법 중 가장 확실하고 무서운 방법. 이론적으로 가능한 모든 경우의 수를 다 검색해 보는 것이라 정확도 100%가 항상 보장되서 암호학에서 가장 확실한 방법으로 통용된다 함. 암호 확인 작업은 손으로 입력한 문자열의 동일 여부를 확인하는거라 가능한 경우의 수를 하나씩 대입하다 보면 언젠가는 암호를 찾을 수 있게 되는 식. 다만 정말로 그냥 무식하게 때려 박는건 아니고, 숫자만 섞어서 대입해 보기 한 번, 로마자만 섞어서 대입해 보기 한 번 이런 식으로 하다가 안 되면 나머지를 순차적으로 하는 식으로 특정 규칙에 따라 우선순위를 두고 하기도 함. / 일반적 방법으로 문제를 해결하기 위해서는 모든 자료를 탐색해야 하기 때문에 특정한 구조를 전체적으로 탐색할 수 있는 방법을 필요로함. / 알고리즘 설계의 가장 기본적인 방법은 해가 존재할 것으로 예상되는 모든 영역을 전체 탐색하는 방법. / 선형 구조를 전체적으로 탐색하는 순차 탐색(Sequential Search), 비선형 구조를 전체적으로 탐색하는 깊이 우선 탐색(Depth-First Search)과 너비 우선 탐색(Breadth-First Search)등이 기본적인 도구 (BFS는 브루트 포스와 관련이 깊고, DFS는 백트래킹과 관련이 깊다고함)

장점 - 거의 완벽하게 병렬 작업이 가능. / 여러 대의 컴퓨터를 연결해서 동시에 작업 가능. 이렇게 하면 투자 자원에 비례해서 문제를 해결하는 시간을 줄일 수 있음. -> 컴퓨터를 10대 쓰면 10일 걸릴작업을 1일만에 완료 가능.

단점 - 자원적 문제 / 브루트 포스 방법은 문제의 복잡도(Complexity)에 매우 민감하다는 치명적 단점이 있음. 

 

예시 :

4자리 숫자로 된 핸드폰의 암호는 0000, 0001, 0002 ... 9999 까지 총 1만개(10^4)의 조합 중 하나이다. 이를 하나씩 대입해 보면 핸드폰의 암호를 통과할 수 있다. 암호 한번 입력하는데 5초가 걸린다면, 5만초(14시간)이면 충분하고 이를 컴퓨터로 처리한다면 1초 이내로 찾을 수 있게 됨.

보통 비밀번호로 자주 쓰이는 자릿수가 최대 8자리인 영문 대소문자, 숫자를 충족하는 사전파일을 만들면 그 텍스트 파일의 용량은 34^8바이트이며 이것은 1663GB이다. 해당 사전파일을 만들때, 4~8GB단위로 끊어서 저장하지 않으면 오버플로우나 저장공간 용량 부족이 일어날 것. -> 웬만한 비밀번호를 다 뚫을 수 있는 사전파일을 만들고 실제 사용하려면 양자컴퓨터 기술과 초고용량 메모리가 대중화 되어야함. -> 이것은 즉, 문제가 조금만 복잡해져도 매우 비효율적인 알고리즘이 될 수 있다는 것. 경우의 수가 문제의 복잡도에 따라 기하급수적으로 증가하는 경우, 문제를 해결하는데 필요한 자원도 기하급수적으로 증가함. / 그래서 체스나 바둑 같은 경우의 수가 많은 경우는, 일반적으로 브루트 포스를 안쓰고 AI나 알고리즘으로 효율적으로 접근한다 함. 

-> 이 때문에 실제로 브루트 포스는 문제의 규모가 현재의 자원으로 충분히 커버가 가능한 경우에만 쓰이고, 대부분은 동적 계획법(DP) 등으로 하는 편. 

단점들은 대부분 암호화 알고리즘에서 역이용하고 있는데, 무어의 법칙 때문에 컴퓨터 성능이 꾸준히 개선되고 있다 해도 그만큼 더 복잡한 암호화 기법을 이용한다함. / 현세대의 암호화 기법을 브루트 포스로 다 뚫는다 해도, 그 시간이 지나고 나면 구식 알고리즘으로 전락할 가능성이 높아서 시간을 벌 수 있음. 무어의 법칙은 경제적인 한계등으로 폐기됬다함.

10의 약수의 합 구하기

거스름돈을 지불할 수 있는 방법의 수와 최소 동전의 개수 구하기

 

문제해결 방법:

주어진 문제를 선형구조로 구조화 함 -> 구조화된 문제공간을 적절한 방법으로 해를 구성할 때까지 탐색 -> 구성된 해를 정리.