[아래로 _ ]: [C/C++] 소수, 우주와 네트워크에 채워진 자물쇠 (RSA 공개키 암호화 구현)

Download link :

RSA_console _170202

소수 (prime number) :

1과 그 수 이외의 자연수로는 나눌 수 없는 자연수.

소수의 규칙성을 찾기 위한 연구는 2,300년 전 유클리드의 저서 '원론'에도 적혀 있습니다.

소수가 오래전부터 드러났다는 것보다, 기원전 시대에서 소수의 무한함을

증명한 유클리드의 통찰이 더욱 놀랍네요.

그럼에도 오늘날까지 소수를 판별하는 완전한 규칙성은 나타나지 않았는데요.

여기 그동안의 역사에서 소수의 규칙성을 밝히기 위한 노력 중 몇가지가 있습니다.

1. 에라토스테네스의 체

유클리드 사후 약 10여년 뒤에 태어난 에라토스테네스는 수학자이자 천문학자입니다.

그는 이집트 두 도시의 태양 그림자 차이로 지구의 둘레를 어림 계산한 것으로 유명한데요.

에라토스테네스의 체는 나열된 수에서, 소수의 배수는 소수가 아니라는

규칙으로 합성수를 제거하는 방법입니다. 2를 만난 순간 모든 나머지 짝수가 제외되고

3이라는 소수로 그 배수인 9와 15 등을 소수 리스트에서 제거할 수 있죠.

그렇지만 '확실'할 수 밖에 없는 노가다를 하기에 확실한 방법입니다.

소수의 정의를 그대로 연산에 적용한 것이나 다름 없습니다.

이렇게 해서는 여전히 수십 - 수백자리의 큰 수가 소수인지 아닌지 판별하기 위해

높은 성능의 컴퓨터와 긴 시간에 의존할 수 밖에 없습니다.

그런데도 오늘날까지도 소수를 발견하는 가장 확실한 방법이 에라토스테네스의 체입니다.

2. 가우스의 소수 정리

밤낮없이 게임속 수만의 몬스터를 잡고 있던게 저의 15살인데,

독일의 수학자 가우스는 15세 때 수를 1,000 단위로 나누어 그 안에 있는 소수의 개수를

세었다고 합니다. 수십만이나 되는 수를 조사한 가우스는 일정 구간에 존재하는

소수의 개수를 어림할 수 있는 정리를 발견했습니다.

소수 정리는 특정한 수가 소수인지 직접적으로 판단하는 용도는 아닙니다.

하지만 정체모를 소수의 덩치라도 가늠할 수 있게 되었습니다.

현재는 가우스의 방법보다 좀 더 정확한 방법도 발견되었다고 합니다.

3. 플리히타의 소수 십자가

숫자를 24개 단위로 시계 방향으로 나열하면 십자 모양으로만 소수가 나타남을

알 수 있습니다. 각 선 위에 나타나는 소수는 불규칙하지만 2와 3을 제외하면

소수가 나타나지 않는 선 영역을 구분할 수 있습니다. 소수의 십자가는 소수 규칙성 발견의

가능성 뿐만 아니라 과학의 가능성까지 넓히고 있습니다. 원소 주기율표의 원자,

아미노 산, DNA 나선 구조를 비롯한 물리, 생화학, 핵화학에 필요한 원천 구조에까지

중요성을 가진다고 합니다.

플리히타는 소수의 십자가가 인간의 발명이 아닌,

무한함을 원자 구조 내에서 유한하게 만들기 위한 건설계획일거라 말했습니다.

4. 소인수 분해와 RSA 암호화

하지만 오늘날 정보화시대에서 소수는 신비로움만으로 남지 않았습니다.

어떤 수를 소수의 곱셈으로 나타내는 것을 소인수 분해라고합니다.

420의 경우에는 '420 = 2 x 2 x 3 x 5 x 7'로 소인수 분해됩니다.

특이점은 두 큰 소수끼리의 곱셈에서, 소수의 곱셈은 종이와 펜만 있어도 할 수 있지만

반대로 곱한 수를 만드는데 쓰인 두 소수를 알아내기는 무척 어렵다는 점에 있습니다.

4,391과 8,819는 소수입니다. 이 둘을 곱하면 38,724,229라는 건 초등학생도

알 수 있죠. 하지만 38,724,229를 처음 본 사람은 이 수가 4,391과 8,819라는

소인수로 구성된다는 걸 알아내기 어렵습니다. 불가능한건 아니지만,

에라토스테네스의 체처럼 그 규칙성 없는 소수를 알기 위해 루프를 돌려야겠죠.

현대 네트워크를 지탱하는 RSA 암호체계는 이 소인수 분해의 난해함을 도구로 활용합니다.

38,724,229와 같은 큰 소수의 곱셈결과를 암호체계의 열쇠로 활용합니다.

원소가 되는 두 소수인 4,391, 8,819를 아는 사람만 공유할 있는 열쇠가 생긴 것이죠.

크롬 브라우저의 설정 탭에서 인증서 관리 항목을 보면 특정 사이트에 대해

사용자 자신을 보증하는 인증서에서도 RSA 암호가 활용된다는 걸 알 수 있습니다.

그럼 여기서 소수를 활용하는 RSA 암호화, 즉 공개키 방식이 꼭 필요한가라는 의문이

들 수 있습니다. 공개키 암호의 내구성을 알기 위해 우선 대칭키 암호의 특성부터

살펴봅시다.

_대칭키 스트림 암호방식의 RC4 구현 게시물 link

대칭키 암호는 암호화와 복호화에 같은 키를 사용합니다. 내가 숨기고 싶은 데이터를

암호화하는 키, 암호화된 데이터를 복호화하는 키가 똑같기에 대칭키라고 합니다.

XOR 연산이 대표적인데요, 추가적인 정보는 위의 RC4 게시물 링크로 확인하는게

좋겠습니다.

_RSA 발명 당시의 Adi Shamir, Ronald L. Rivest, Leonard Adelman. (왼쪽부터)

RSA는 암호화에는 공개키, 복호화에는 개인키를 사용하기에 비대칭 암호화입니다.

대칭키로 암호화한 데이터의 평문과 암호문이 유출되면 어떻게 될까요?

암호화된 평문을 훔친 크래커가 암호문을 알게 되면 평문도 바로 해석할 수 있습니다.

공개키는 '나에게 데이터를 전달하고 싶다면 이 키로 암호화하라'라고 공개한 것입니다.

공개키는 정상적 정보교환자인 알라딘 서점이나 옥션은 물론, 나의 거래 데이터를

훔쳐보고 싶은 크래커 또한 알게 됩니다. 하지만 정작 데이터를 복호화해서

이해할 수 있는 개인키는 나만이 알고 있습니다. 그렇기에 크래커가 데이터 신호를

훔쳐서 획득한 암호화된 평문을 누구나 아는 공개키로 풀어서는 평문이 나오지 않습니다.

모두가 아는 열쇠로 나만이 풀 수 있는 자물쇠를 얻어낸 것입니다.

암호열쇠와 복호열쇠가 다른 '일방향성'의 암호화, 여기에 소인수 분해의 기여가 있습니다.

RSA 암호화는 C++ 소스코드와 함께 보려합니다. 사실 저도 기억이 가물가물해서..

준비물로 매우 큰 정수를 다루는 도구가 필요합니다. RSA 암호화에는 데이터를

제곱하는 구간이 있는데, 기본 C++ 데이터 타입의 크기 한계를 쉽게 넘어버립니다.

이전 제가 선택했던 방법은 큰 정수를 다루는 라이브러리를 포함시킨 방법이었습니다.

_Big Integer Library website link

개발자 분이 프로젝트 지원은 끝내셨지만 아직 사이트는 살아있네요.

다운로드 받은 2010년 4월 30일자 버전 압축파일을 풀고 Qt 프로젝트로 인클루드합시다.

저는 그냥 프로젝트 항목을 우클릭해서 'Add Existing Directory...'로 통째로 넣었습니다.

거기에 INCLUDEPATH만 타이핑으로 추가입력했습니다.

'BigInteger' 라이브러리를 인클루드하고 전역변수를 설정합니다. 여기서는 제가 여러분의

컴퓨터에 RSA 암호화한 데이터를 보내는 상황을 가정했습니다. 그렇기에 여러분 컴퓨터의

공개키로 암호화한 데이터를 여러분만이 아는 비밀키로 복호화해야합니다.

공개키는 2개의 수인데, 소수 2개를 곱한 '33'과 20 아래에 존재하는 소수 'e'입니다.

이 제한선인 20은 두 소수에서 1씩을 뺀 뒤 곱한 값입니다.

여기서는 e를 3으로 선택했습니다. 비밀키는 e에 비밀키를 곱하고 20으로 나누었을 때

나머지가 1이 되어야합니다. 따라서 비밀키는 7로 되었습니다.

공개키 (33, 3)은 여러분에게 중요한 메시지를 보내고 싶은 사람이나, 혹은 그걸

훔쳐보고 싶은 사람이나 모두 알 수 있습니다.

하지만 크래커인 트루디가 중간 데이터를 캐치해도 안심입니다. 비밀키는 오직

당신만이 알고 있습니다. 제가 여러분에게 보낼 데이터를 공개키로 암호화하면서

'이렇게 처리해서 보내면 ~씨가 비밀키로 알아서 잘 복호화하겠지.' 하고 안도할 수 있는

이유가 거기에 있습니다.

원본 데이터를 암호화하는 함수입니다. 제곱하면서 커지는 큰 정수를 감당하기 위해

'BigInteger' 타입으로 데이터를 잠시 복사합니다. 원본 데이터를 당신이 공개한 공개키

'e'회만큼 제곱하고, 트루디도 아는 공개키 N (33)으로 나눴을 때 나머지가 암호화된

데이터입니다. 암호화는 누구나 할 수 있는 것이죠.

암호화된 데이터를 복호화하는 함수입니다. 여기서 드디어 소수의 신비로운 마법이

가미됩니다. 암호화 데이터를 당신만이 아는 비밀키의 횟수만큼 제곱하고 공개키

N으로 나눈 나머지가 제가 당신에게 전달하고자 했던 원본 데이터입니다.

제가 보내고자 했던 데이터는 '8', 보내기 위해 암호화한 데이터는 '17',

17을 받아 당신의 비밀키로 복호화한 데이터가 '8'입니다.

제가 단순히 8에다가 10을 곱해서 80으로 만든 뒤, 우리들의 비밀 키워드가 '10'이라고

제안했다면 트루디가 데이터 신호를 훔쳐서 원본에 10이 곱해지고 있다는 걸

알아내기 쉽습니다. 텍스트에서 가장 흔하게 나오는 영어문자가 'e'이기에

가장 흔하게 나오는 데이터를 캐치한 뒤, e의 아스키코드 십진수 값에 해당하는

101에서 10이 곱해지거나 XOR 된 것을 확인할 수 있겠죠. 트루디가 혹시나

10이 키워드인가 싶어 다른 데이터를 모두 10으로 복호화했더니 드러나는 데이터가

'3(dk3fcn6lsh' 같은 게 아니라 'Trudy is an intruder'와 같다면..

그 비밀은 이제 트루디의 재산이 됩니다. 좋은 얼굴로 봐주지는 않겠죠.

이 과정을 통해 반대로 저의 공개키로 여러분이 암호화한 데이터를 제가 비밀키로

복호화하는 상황도 쉽게 그려지실 겁니다.

5. 양자컴퓨터의 소인수분해, RSA의 미래

소수가 크면 클수록 좋은 것은, RSA의 의미가 거기 있기 때문입니다. 견고한 소인수분해

기반의 RSA라도 33과 같은 작은 공개키는 눈으로 봐도 3과 11로 소인수 분해 되버립니다.

그러면 두번째 공개키인 3과 두 소수, 3과 11로 알게 된 20이 비밀키가 7이라는 것을

밝혀버리죠..

그런데 축전기 디지털 비트 단위가 아닌 원자 단위를 논리 연산에 활용하는 양자컴퓨터는

중첩이라는 특성에 의해 RSA에 조금 다른 위기가 될 수 있습니다. 기존 디지털 컴퓨터의

성능향상, 즉 속도에 의해 에라토스테네스의 체와 같은 방법으로 소인수 분해될 위험과

마주했다면 양자컴퓨터는 물리학에서의 진보로 인해 찾아오는 논리적 위기입니다.

양자컴퓨터에 대한 게시물은 '프로그래밍 유니버스'라는 책에 대한 저의 리뷰를

우선 참고해주시면 좋겠습니다.

_'프로그래밍 유니버스' 리뷰 link

디지털 컴퓨터의 병렬성은 별도의 코어가 작업을 '분담'하도록 하지만, 양자컴퓨터의

양자역학적 중첩은 그것과 다릅니다. 양자컴퓨터의 중요한 응용분야가 된 피터 쇼어의

쇼어 알고리즘은 양자적 중첩과 붕괴현상으로 RSA 암호화를 해체할 수 있음을 보였습니다.

관련 도서에서 읽은 메커니즘은 다음과 같습니다.

쇼어의 소인수 분해 알고리즘은 시계판 연산을 사용합니다.

33이라는 수를 굳이 시계판 연산으로 소인수 분해해볼까요?

[1] 33보다 작은 아무 수를 하나 선택한다. 여기서는 5.

[2] 선택한 수 5를 제곱해가며 33으로 나눈 나머지를 구한다.

5 -> 25 -> 26 -> 31 -> 23 -> 16 -> 14 -> 4 -> 20 -> 1 ->
5 -> 25 -> 26

[3] 10을 주기로 반복되는 걸 알 수 있다. 알아낸 주기의 절반인 5로
처음 고른 수, 5를 거듭제곱한다. (5^5 = 3,125)

[4] 3,125의 위아래로 ±1한 값, 3,124와 3,126과 33과의 최대 공약수를 구하면
3,124와는 11, 3,126과는 3이 나온다. 33의 소인수는 3과 11이다.

여기서 가장 번거로운 부분은 5를 거듭해 제곱해가며 10이라는 반복주기를 알아내는

부분입니다. 디지털 컴퓨터는 저 연산에서 이점을 얻지 못하지만,

양자컴퓨터는 큐비트, 즉 양자 간의 얽힘으로 중첩된 10이라는 주기를 관측할 수

있다고 합니다. 25, 31과 같은 특정 수로 붕괴되지 않고 주기만을 관측하기 위해

푸리에 변환이 적용된다고 하네요. 제가 읽은 책에서는 여기까지 소개되어 있었습니다.

이 부분은 눈으로 봐야 알거 같은데. 언제 보게 될 날이 올까요..