신용카드 번호가 소수를 이용해서 암호가 된다고 합니다.

안녕하세요?

수학... 그 과목은 중, 고등학교에서 배울때는 이걸 어디에 써먹는가 하는 생각이 드는데, 실제로 생명과학이 전공인 저로서도 중, 고등학교에서 배웠는 수학이 그다지 사용한 적은 없었습니다. 그렇지만 Newton 2017년 8월호에 싣려 있는 [소수의 신비]라는 기사-그 중에서도 통신 보안에 관여한다는 RSA암호라는 것이 있는데, 이에 대한 내용이 상당히 재미 있었기에 이번 포스팅에서 다루고자 합니다.

비록 위 이미지에 '숫자'이미지를 사용하기는 했지만, '소수'라는 것은 아닙니다. 소수란 그 이상의 정수 가운데 1과 자기자신으로 밖에 나누어 지지 않는 수를 이야기 합니다. 이런 소수가 1~100 사이에도 25개만 나온다고 할 정도로 이해하기 난해하며, 소수만 계산하는-공식을 사용해서 소수'만' 만들어 내는 공식이 아직은 없다고 합니다. 그 유명한 '오일러의 이차식'이라는 공식도 41이상의 수를 넣어서 계산하면 '소수가 아닌 수'가 나온다고 합니다.

그럼 본론으로 돌아와서, 이 소수가 어떻게 '신용카드 정보의 통신보안'에 이용이 되는지를 알아보자면, 먼저 '공개열쇄'와 '비밀열쇄'가 있다고 합니다. 이 공개열쇄란 것을 사용해서 자기 신용카드의 번호를 '암호'로 바꾼다고 합니다. 물론 기사에서는 대략적인 내용만 알려주기 때문에 실재로 신용카드의 '카드번호'인지 아니면 '비밀번호'인지 알 수는 없었습니다.

다만, 이름에서 알 수 있듯이 '공개열쇄'란 것은 사용자가 내려받아서 자기 정보를 암호화 하는데 사용할 수 있는 물건이라고 합니다. 이 공개열쇄는 두개의 '정수'로 이러어져 있으며, 암호화된 정보를 받은 쪽에서는 자기들만이 가지고 있는 '비밀열쇄'라는 것을 이용해서 암호를 푼다고 합니다. 내용이 조금은 복잡하기 때문에, 먼저 아래의 그림을 통해서 설명을 드리도록 하겠습니다.

먼저 위 예시에서 공개열쇄는 3과 115라는 두 정수로 이루어져 있습니다. 이 중 2번째 수인 115는 두개의 '소수'인 5와 23에서 곱하기를 하면 나오는 값입니다. 여기서 공개 번호인 115만 보고서 비밀열쇄를 알아내면 어쩌나 하는 분들이 계신텐데, 실제로는 비밀 열쇄의 두 '소수'는 자릿수가 '300자리'정도의 수가 사용이 된다고 합니다. 이 때문에 현재의 컴퓨터 기술로는 상상할 수 없는 세월이 걸린다고 합니다.

여기서 신용카드 번호를 13을 어떻게 계산해서 암호로 만들어 지며, 여기 12라는 나머지가 암호로서 전송이 되는 것을 알아도 역으로 계산해서 알아내기에는 상당한 시간이 걸리게 됩니다. 그런데 실제 카드번호는 14~16자리 숫자이기 때문에, 역으로 계산해서 원래의 카드 번호를 알아내기란 사실상 불가능하다고 보시면 됩니다. 여기서는 이해를 돕기 위해서 3자릿수인 115를 표시했지, 실제로는 600자리의 수가 사용이 된다고 합니다.

그럼 여기서 의문이 드실 것이, 공개열쇄를 이용해서 역으로 암호가 원래 무슨 수인지 알아 내는 것이 어려운데, '비밀열쇄'는 어떤 원리로 저 10의 273승 년이 걸리는 시간을 간단하게 끝낼 수 있는가 하실 겁니다. 실제 위 그림에서 예시를 든 5와 23은 진짜 비밀열쇄가 '아니고' 비밀열쇄를 만드는 데 사용되는 '두 소수'에 불과하다고 합니다.

위 그림을 보면 알 수 있듯이 공개열쇄와 진짜 비밀열쇄가 완전히 떨어져 있지 않은 것인데, 여기서 '88'이라는 숫자가 나오게 됩니다. 즉, 몫 A를 모르는 상태에서 '?'를 구하면 되는데, 이 '?'가 진짜로 작동을 하는 '비밀연쇄'라는 것입니다. 여기서 공개열쇄를 만들때, 3이라는 숫자는 88과 공동으로 나누어 떨어지는 수가 없어야만 합니다. Newton의 기사에서는 자세히 나오지 않았지만, 여기서는 '유클리드의 호제법'이라는 알고리즘이 등장합니다.

일단 이것도 이야기를 시작하면 복잡해지니, 간단하게 설명을 하도록 하겠습니다. '유클리드의 호제법'을 통해서 나오는 수가 59라고 3과 88하고 관계가 되는 수가 나오는데, 이 59가 바로 '진짜 비밀열쇄'라는 것입니다. 그래서 아래의 공식에 넣으면 카드의 원래 번호가 나오게 된다고 합니다. 아래의 공식이 의외로 간단하기에, '진짜 비밀열쇄'는 철저히 숨겨야 겠다는 생각이 듭니다.

마지막으로 여기 소개가 된 것은 'RSA암호'라고 하는 것으로, 저는 잘 모르지만, 암호의 한 종류가 아닐까 합니다. 이런 소수를 뚫기위한 계산에 너무 많은 시간이 걸리기에, 우리가 안전하게 온라인 거래를 할 수 있으나, 이 암호를 순식간에 풀어 버리는 '양자 컴퓨터'는 얼마나 위력적인지 알 수 있다는 생각이 듭니다. 마지막으로 이 암호관련 지식은 각종 '해킹'을 막는 데도 유용하게 쓰이지 않을 까 합니다.