04. 암호학의 가장 거대한 방패, 소수 (Prime Number)

1. 학습 목표 (Learning Objectives)

• 1과 자기 자신만으로 나누어떨어지는 ‘소수(Prime)’가 왜 현대 암호학을 수호하는 가장 완벽한 수학적 열쇠가 되었는지 이해합니다.
• 파이썬(Python)의 ‘에라토스테네스의 체’ 알고리즘을 이용해 자연수 속에서 소수들의 목록을 빠르게 걸러내는 방식을 실습합니다.

2. 곱하기는 쉽지만, 쪼개기는 불가능한 숫자

2, 3, 5, 7, 11, 13, 17… 이 숫자들의 공통점은 과연 무엇일까요? 바로 약수가 ‘1’과 ‘자기 자신’ 단 2개뿐인 결벽증을 가진 숫자들, 소수(Prime Number)입니다. 다른 자연수들이 섞이고 곱해져서 만들어진 합성수들과 달리, 소수는 수학계의 원자(Atom)로서 절대 더 이상 자를 수 없는 단단한 기둥들입니다.

암호학자들은 이 소수의 독특한 성질(소인수분해의 극악한 비대칭성)에 크게 매료되었습니다. 한 번 상상해 보세요.

• 문제 A (곱하기): 79와 89를 곱하면 얼마일까요? (계산기를 두드리면 1초 만에 7031이 나옵니다. 너무 쉽죠.)
• 문제 B (소인수분해): 무작위 숫자 14,120,497 은 어떤 두 개의 소수를 곱해서 만들어진 숫자일까요?

B번 문제를 풀려면 7, 11, 13 등 수많은 소수들을 일일이 처음부터 대입해서 나눗셈이 맞아 떨어지는지(나머지가 0인지) 평생 동안 수작업을 해야 합니다. 만약 해커가 슈퍼컴퓨터를 들고 와서 풀려 해도, 암호학자가 자릿수가 300자리가 넘는 거대한 소수 두 개를 휙 곱해서 방패를 만들면 컴퓨터가 우주 나이인 138억 년 동안 나눗셈을 쉬지 않고 돌려도 두 소수의 원형을 영원히 찾아내지 못합니다.

이것이 현대 인터넷 뱅킹을 지키는 ‘풀 수 없는 수학적 자물쇠 구조’ 의 탄생 배경입니다.

3. 파이썬 소수 판독기: 에라토스테네스의 체 (Python)

개발자들은 보안 시스템을 짤 때 엄청난 양의 소수 목록이 필요합니다. 이때 고대 그리스 수학자 에라토스테네스가 고안한 ‘배수 지우기’ 알고리즘을 파이썬으로 가볍게 구현합니다.

def sieve_of_eratosthenes(limit):
    # 0부터 limit까지 모든 숫자를 True(소수 후보)로 채운 리스트를 만듭니다.
    primes = [True] * (limit + 1)
    primes[0] = primes[1] = False # 0과 1은 소수가 아닙니다.
    
    # 2부터 루트(limit) 까지만 검사하면 수학적으로 충분합니다.
    for p in range(2, int(limit ** 0.5) + 1):
        if primes[p]:
            # p가 살아남은 소수라면, p의 배수들을 모조리 지워버립니다 (False 처리)
            for i in range(p * p, limit + 1, p):
                primes[i] = False
                
    # True로 살아남은 진짜 소수들만 예쁘게 모아서 반환합니다.
    prime_numbers = [i for i, is_prime in enumerate(primes) if is_prime]
    return prime_numbers

# 1부터 100 사이의 보안 통신망 기초 소수(Prime keys) 목록을 뽑아봅시다.
extracted_primes = sieve_of_eratosthenes(100)
print("■ 100 이하의 소수(Prime) 목록 ■")
print(extracted_primes)
print(f"-> 총 {len(extracted_primes)}개의 소수 열쇠 획득 완료!")

파이썬의 실행 결과 요약:

■ 100 이하의 소수(Prime) 목록 ■
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
-> 총 25개의 소수 열쇠 획득 완료!

이 알고리즘은 2를 남기고 2의 배수 지우기, 3을 남기고 3의 배수 지우기 방식을 파도처럼 순식간에 펼쳐나가며 반복 연산을 획기적으로 줄여주는 프로그래밍의 정수입니다.

4. 학습 정리 (Summary)

1. 소수 (Prime Number): 1과 자신으로만 나눠지는 더 이상 쪼갤 수 없는 수의 원자 조각입니다.
2. 소인수분해의 비대칭성: 두 숫자를 ‘곱하는 것’은 컴퓨터에게 1밀리초도 안 걸리지만, 곱해진 거대한 성을 다시 ‘어떤 소수 두 개로 이뤄져 있는지 쪼개는 것’은 불가능에 가까운 물리적 시간이 소요되는 원터치 방어막입니다.