소수 + 소프트웨어 = RSA 암호

누구에게나 비밀이 있습니다. 우리 가족만 간직한 비밀이 있고, 친구끼리만 공유하는 비밀도 있지요. 그래서 SNS나 메일에서 나눈 이야기는 다른 사람이 보지 못하도록 암호화합니다. 스마트폰이나 컴퓨터로 물건을 살 때도 마찬가지입니다. 주소나 전화번호, 계좌번호, 카드번호 등 개인정보를 다른 사람이 보지 못하도록 풀기 어려운 암호를 걸어두지요. 그런데 여기에 쓰이는 암호가 소수와 관련이 있습니다.

현재 가장 널리 쓰이고 있는 RSA 암호는 큰 수를 두 소수의 곱으로 나타내는 것이 어렵다는 원리를 이용한 것입니다. 예를 들어 905220186434063을 소인수분해하라고 하면 어떨까요? 이 수는 인수를 2개밖에 가지고 있지 않아 소인수 분해하기가 어렵습니다. 하지만 두 인수 12049523과 75124981을 알려준 뒤 곱하라고 하는 건 매우 쉽지요. RSA 암호는 이처럼 두 소수를 곱하는 건 쉽지만 인수가 2개인 합성수를 소인수분해하는 건 어렵다는 점을 이용한 암호입니다. 여기서는 8자리 소수를 이용했지만 실제 암호에서는 60자리 이상 소수를 사용하기 때문에 컴퓨터라고 해도 암호를 풀 수가 없는 거지요.

이런 RSA 암호는 소수와 소프트웨어가 만나 만든 걸작품이라고 할 수 있습니다. 이 암호를 개발한 수학자 로널드 라이베스트와 아디 샤미르, 레오나르드 아델만은 1982년 ‘RSA 시큐리티’라는 회사를 세웠고, 이 회사는 매년 1조 원이 넘는 막대한 돈을 벌고 있지요. 세 수학자는 2002년 컴퓨터 과학의 노벨상이라고 불리는 ‘튜링상’도 받았습니다.

소수와 소프트웨어가 만난 또 다른 예는 세상에서 가장 큰 소수를 찾는 일입니다. 소수는 무한히 많기 때문에 가장 큰 소수라는 건 이 세상에 존재하지 않습니다. 다만 현재까지 발견한 소수 중에서 가장 큰 수를 그렇게 부르지요. 현재까지 발견된 소수 중 가장 큰 수는 257885161-1로 무려 1740만 자리입니다. 36만 개의 컴퓨터 프로세서가 초당 150조 회의 연산을 한 결과로, 2013년 미국의 수학자 커티스 쿠퍼가 찾았지요. 지금도 많은 수학자들이 더 큰 소수를 찾기 위해 수십 만 대의 컴퓨터를 돌리고 있습니다.

콘텐츠·도움 : 김재휘(엔트리교육연구소 연구원)