brunch

매거진 무늬만 블랙햇 해커

라이킷 1 댓글

You can make anything
by writing

C.S.Lewis

계정을 잊어버리셨나요?

by Younggi Seo Jun 22. 2018

최대공약수를 구하는 알고리즘

G.C.D.(Greatest Common Division) 코드 디버깅

최대공약수란 두 수의 약수 중에서 공통인 것을 찾아 그중 최댓값을 가지는 수를 말한다. 그리고 소수란 1과 자기 자신 이외에는 약수가 없는 값을 일컫는다. 일전에 1박 2일이라는 예능 프로의 멤버들이 포스텍 대학생들과 함께 변형된 369 게임을 하는 것을 봤다. 3, 6, 9 외에 소수까지 박수를 쳐야 하는 규칙이 추가되었는데 1부터 3까지 박수부터 치고 들어가는 게임에 연예인 멤버들이 처음부터 나가떨어졌다. 포스텍 학생들이 평소에 휴식을 취하며 한다는 게 2진수나 16진수 변환 게임이라고 또 말하여 어이가 없었다.

알고리즘은 비슷한 문제를 풀기 위한 순서나 체계를 가리키는데 보통 처음 코딩을 하는 사람들의 버릇 가운데 하나가 아주 간단한 코딩 정도는 순서를 고려하지 않고 바로 타이핑부터 하는 것이다. 하지만 아무리 간단한 문제라고 하더라도 일련의 순서(Pseudo Code, 의사 코드)를 먼저 적거나 머릿속에서 프로그램 동작 리허설을 하면서 제대로 움직이는지 한 번 상상해 보는 것이 단 번에 끝내는 데 도움이 된다.

정밀한 프로그램을 만들 수 있는 개발자가 보안에 취약한 소스 코드 또한 미리 대처할 수 있다. 그래서 실행이 되는지 무작정 입력하기에 앞서 최대공약수의 성질에 따라 프로그램 순서를 직접 긁적여 봤다.

1) 두 수 중 더 작은 값을 i라는 변수에 저장

2) i가 두 수의 공통된 약수인지 확인

3) 공통된 약수이면 이 값을 결괏값을 돌려주고 종료.

4) 공통된 약수가 아니면 i를 1만큼 감소시키고 2번으로 돌아가 반복.

(1은 모든 정수의 약수이므로 i가 1이 되면 결괏값으로 돌려주고 종료)

본인이 처음 작성한 소스를 디버깅해서 프로그램의 순서가 제대로 흐르는지 확인함.

그런데 일단 소스가 완성되면 디버깅이라는 유용한 테스팅 도구가 있어서 머릿속에서 프로그램의 흐름을 예상하지 않더라도 직접 눈으로 값의 대입과 순서를 확인할 수 있다. 간단한 알고리즘이라서 문제는 해결되었으나, 파이썬 탄생 취지(Zen of Python)에 걸맞은 심플한 코드가 있어서 비교해봤다.

def gcd(a, b):
    i = min(a, b)        # 두 수 중에서 최솟값을 구하는 파이썬 함수
    while True:
        if a % i == 0 and b % i == 0:
            return i
        i = i - 1        # i를 1만큼 감소시킴

print(gcd(1, 5))        # 1
print(gcd(3, 6))        # 3
print(gcd(60, 24))    # 12
print(gcd(81, 27))    # 27

절반 정도의 분량으로 해치울 수 있다는데 자괴감이 들었지만 어이됐든 파이썬에서 min()이라는 math 라이브러리 함수를 통해 두 수 중 최솟값을 바로 구할 수 있고, while 루프문을 통해 간단하게 값의 비교를 반복할 수 있다. 또한 and 비교 연산자를 통해 두 값의 논리곱 연산자로 나처럼 for 문 하위 같은 내용을 두 번 쓸 필요가 없었다.

여기서 보안의 관점으로 유의 깊게 볼 부분이 and와 같은 비트 연산자이다. AND 연산은 '논리곱'이라고도 하며 곱하기처럼 작용한다(Khan, 2018). 이 연산에서는 모든 입력값이 1일 때만 1을 출력한다. 다음은 논리연산자 AND의 진리표이다.

0 AND 0 = 0
0 AND 1 = 0
1 AND 0 = 0
1 AND 1 = 1

두 번째의 간단한 소스 코드에서 a를 1로 나누었을 때의 나머지 값(mod)이 0이면 참, 그리고 b를 1로 나누어 떨어지면 참으로 둘 다 참이 되므로 참(True)값으로 1을 반환한다. 그래서 if 문 하위의 리턴 명령으로 이때의 i값을 돌려(return)줄 수 있다.

AND 연산자 외에 배타적 논리합이라는 연산을 수행하는 XOR 비트 연산자가 있다. 컴퓨터에서 1회용 암호표를 수행할 때 왜 XOR이 사용되어야 하는지 보안 전문가라면 알아야 한다. 비트 연산은 말 그대로 개별적인 비트, 즉 이진수를 다룬다는 뜻이다. 현대의 컴퓨터화된 암호 체계에서는 이진수로 기호를 표현한다(Khan, 2018).