[알고리즘] 시디키를 만들어 보자

CD 키


전략 시뮬레이션을 기획 제작하고 있는 게임사 개발팀의 박 팀장.

베틀넷 서비스를 구상하고 있기에 안전한 CD 키를 만들 방법이 없겠냐고 필자에게 물어온 적이 있었다. 아마 조금만 생각하면 쉽게 생각해 낼 수 있었겠지만 마땅히 문서화한 자료를 구하기 힘들었기 때문이었을 것이다. 사실 스타 크래프트의 CD 키 생성툴은 립버전이 활개를 치게 하는데 큰 역할을 했다. 여러 가지 알고리즘이 많이 있겠지만, 보통 이런 번호는 실제 키와 그 키를 암호화한 부분을 합친 것을 생각해 보자. 이 대표적인 예가 주민등록번호다. 주민등록번호는 실제키 12자리에 각 가중치를 줘 더한 값을 10으로 모듈 연산해 얻은 값을 마지막에 붙여 13자리로 이뤄진다.

따라서 12자리를 정한 후 마지막 자리를 10번 반복하면, 주민등록번호에 대한 인증은 뚫리게 된다. 일단 10진수가 위험하다는 것을 느꼈을 것이다. 여기에 알파벳 26자을 동원하면 36가지가 가능한 36진수가 된다. 소문자도 동원할 수 있지만 대소문자 구분까지 하는 것은 유행은 아닌 듯 하니 대소문자 구분은 하지 않고 36진수만 사용하도록 하자.

그리고 생성 규칙은 날짜에 그날 생성된 순서로 하자. 그리고 마지막에 이 값을 모두 더한 값을 끝에 덧붙이도록 하자.

Y0Y1Y2Y3/M0M1/D0D1 S0S1S2S3 H0H1H2

원문은 다음과 같다고 하자. 암호화 알고리즘은 여러 가지가 있지만, 어차피 공개키 방식을 동원할거라면, 어떤 알고리즘을 사용하더라도 어떤 알고리즘을 사용했는지 공개만 하지 않으면 되므로 비교적 구현이 쉬운 DLP(Discrete Logarithm Problem)을 이용하겠다. 지수는 곱셈을 반복하면 되는 것으로 구현이 비교적 간단하다. 다음 식을 보자.

Ax = B (mod n)

간단한 식이지만, 참 많은 규칙이 숨어 있다. A가 소수일때 '0

7x = B (mod 31)

이 정도면 훌륭하다. 36진수를 사용할 것이라고 했는데 31을 사용한 것은 모듈 연산을 소수로 해야 겹치지 않기 때문이다. 예를 들어 다음과 같은 경우를 생각해보자.

31 (mod 8) = 3
32 (mod 8) = 1
33 (mod 8) = 3
...

32가 1이 되면서 계속 3과 1이 반복돼 버린다. 따라서 8이 아닌 소수를 잡아야 한다. 계산을 하기 위한 힌트하나로 다음과 같은식이 성립한다.

Ax+y (mod n) = ( Ax (mod n) )× ( Ay (mod n) )

다음과 같은 예를 들 수 있다.

35(mod 7) = 243 (mod 7) = 5
= 31(mod 7)×34(mod 7) = 3 (mod 7)×11 (mod 7) = 33 (mod 7 ) = 5
= 32(mod 7)×33(mod 7) = 2 (mod 7)×6 (mod 7) = 12 (mod 7 ) = 5
이 속성은 실제 구현시 매우 유용한 속성으로 전값에 곱셈을 하고 바로 모듈연산을 해버리면 값이 작아지므로 작은 범위의 데이터 타입으로도 큰 지수 연산을 가능하게 해준다.

그럼 원문을 200103120003012이라고 해보자. 2001년 3월 12일의 세번째 만들어진 CD 키라는 뜻이다. 그리고 뒤에 012는 앞의 모든 숫자를 더해 만든 해시키다.

70 = 1 (mod 31)
71 = 7 (mod 31)
72 = 18 (mod 31)
73 = 2 (mod 31)
...
따라서 암호문은 다음과 같을 것이다.

( 18, 1, 1, 7, 1, 2, 7, 18, 1, 1, 1, 2, 1, 7, 18)

이 암호문은 아스키 코드 등으로 바꿔 사용하면 될 것이다. 그런데 0이 7개, 1이 4개, 2가 3개이다. 패턴을 읽힐 수 있다. 따라서 자리수별로 가중치를 주자. 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47로 하면 그 문제는 해결될 것이다. 그리고 이렇게 나온 값을 가지고 암호화 패턴을 하나 만들어 뒤에 4자리 정도 붙이자. 그럼 다음과 같은 결과 값이 나올 것이다.

22 = 4 (mod 31)
30 = 1 (mod 31)
50 = 1 (mod 31)
71 = 7 (mod 31)
110 = 1 (mod 31)
133 = 27 (mod 31)
171 = 17 (mod 31)
192 = 20 (mod 31)
230 = 1 (mod 31)
290 = 1 (mod 31)
310 = 1 (mod 31)
373 = 6 (mod 31)
410 = 1 (mod 31)
431 = 12 (mod 31)
472 = 8 (mod 31)

따라서 암호문은 다음과 같다.

( 4, 1, 1, 7, 1, 27, 17, 20, 1, 1, 1, 6, 1, 12, 8 )
( 4, 1, 1, 7, 1, R, H, K, 1, 1, 1, 6, 1, C, 8 )

4117-1RHK-1116-1C8

특성상 지수의 0승이 1이 돼 1이 많은데 실제 사용시에는 지수에 전부 1을 더해서 사용하면, 훨씬 분포도가 좋아 질 것이다. 이 키를 사용자가 입력하면 역으로 로그 연산을 하면 원문을 얻을 수 있다. 앞의 시리얼키를 해시해 나온 값이 해시키와 일치하면 그 키는 유효한 것이다.

네트워크에 연결되지 않은 채 로컬에서만 게임을 즐기는 사람이 많기 때문에 인증서버를 거치지 못하고 단방향 암호함수를 거치는 수밖에 없다.




<출처>
http://www.zdnet.co.kr/