현대 디지털 보안의 핵심은 수학에 있다. 특히 이산수학의 여러 분야가 암호학의 기반이 되는데, 이는 연속적인 수학과 달리 이산적이고 유한한 구조를 다루기 때문이다.
암호학에서 사용되는 수학적 개념들을 살펴보면, 정수론, 조합론, 그래프 이론, 유한체 이론 등이 모두 이산수학의 영역이다. 오늘은 이런 수학적 기초가 어떻게 현대 보안 시스템을 지탱하고 있는지 알아보자.
RSA는 가장 널리 사용되는 공개키 암호화 시스템이다. 그 핵심은 소인수분해의 어려움에 있다.
# RSA 키 생성의 핵심 개념
def generate_rsa_keys():
# 1. 두 개의 큰 소수 p, q 선택
p = 61 # 실제로는 수백 자리 수
q = 53
# 2. n = p * q (공개키의 일부)
n = p * q # 3233
# 3. φ(n) = (p-1)(q-1) (오일러 파이 함수)
phi_n = (p-1) * (q-1) # 3120
# 4. e 선택 (공개 지수, 보통 65537)
e = 17
# 5. d 계산 (개인 지수, e*d ≡ 1 (mod φ(n)))
d = pow(e, -1, phi_n) # 2753
return (n, e), (n, d) # (공개키, 개인키)
왜 이게 안전할까?
암호학에서 모듈러 연산은 핵심이다. 특히 페르마의 소정리와 오일러 정리가 중요하다.
# 모듈러 지수 연산 (빠른 거듭제곱)
def mod_exp(base, exponent, modulus):
result = 1
base = base % modulus
while exponent > 0:
if exponent % 2 == 1:
result = (result * base) % modulus
exponent = exponent >> 1
base = (base * base) % modulus
return result
# 예시: 7^13 mod 11 = ?
print(mod_exp(7, 13, 11)) # 2
SHA-256은 비트 단위로 동작하는 해시 함수다. 이산수학의 비트 연산과 조합론이 핵심이다.
# SHA-256의 핵심 연산들
def rotate_right(value, amount):
"""32비트 우측 회전"""
return ((value >> amount) | (value << (32 - amount))) & 0xFFFFFFFF
def ch(x, y, z):
"""Choice 함수: x가 1이면 y, 0이면 z"""
return (x & y) ^ (~x & z)
def maj(x, y, z):
"""Majority 함수: 다수결"""
return (x & y) ^ (x & z) ^ (y & z)
def sigma0(x):
"""σ0 함수"""
return rotate_right(x, 2) ^ rotate_right(x, 13) ^ rotate_right(x, 22)
def sigma1(x):
"""σ1 함수"""
return rotate_right(x, 6) ^ rotate_right(x, 11) ^ rotate_right(x, 25)
해시 함수의 특징:
타원곡선은 다음과 같은 방정식으로 정의된다: y² = x³ + ax + b (mod p)
# 타원곡선 점 덧셈
class EllipticCurve:
def __init__(self, a, b, p):
self.a = a
self.b = b
self.p = p
def point_add(self, P, Q):
if P is None:
return Q
if Q is None:
return P
x1, y1 = P
x2, y2 = Q
if x1 == x2 and y1 == y2:
# 점 두 배 (point doubling)
s = (3 * x1 * x1 + self.a) * pow(2 * y1, -1, self.p) % self.p
else:
# 점 덧셈 (point addition)
s = (y2 - y1) * pow(x2 - x1, -1, self.p) % self.p
x3 = (s * s - x1 - x2) % self.p
y3 = (s * (x1 - x3) - y1) % self.p
return (x3, y3)
def scalar_multiply(self, k, P):
"""스칼라 곱셈: k * P"""
result = None
addend = P
while k:
if k & 1:
result = self.point_add(result, addend)
addend = self.point_add(addend, addend)
k >>= 1
return result
# secp256k1 곡선 (비트코인에서 사용)
secp256k1 = EllipticCurve(0, 7, 2**256 - 2**32 - 2**9 - 2**8 - 2**7 - 2**6 - 2**4 - 1)
ECC의 장점:
블록체인에서 사용되는 머클 트리는 이진 트리의 응용이다.
import hashlib
class MerkleTree:
def __init__(self, data):
self.data = data
self.tree = self.build_tree()
def build_tree(self):
if len(self.data) == 0:
return []
# 리프 노드들 (데이터의 해시값)
current_level = [hashlib.sha256(str(item).encode()).hexdigest()
for item in self.data]
tree = [current_level]
# 상위 레벨들을 구성
while len(current_level) > 1:
next_level = []
for i in range(0, len(current_level), 2):
left = current_level[i]
right = current_level[i + 1] if i + 1 < len(current_level) else current_level[i]
combined = left + right
next_level.append(hashlib.sha256(combined.encode()).hexdigest())
tree.append(next_level)
current_level = next_level
return tree
def get_root(self):
return self.tree[-1][0] if self.tree else None
def get_proof(self, index):
"""특정 데이터의 증명 경로 생성"""
if index >= len(self.data):
return None
proof = []
current_index = index
for level in self.tree[:-1]:
if current_index % 2 == 0:
# 왼쪽 노드인 경우, 오른쪽 형제 필요
if current_index + 1 < len(level):
proof.append(('right', level[current_index + 1]))
else:
# 오른쪽 노드인 경우, 왼쪽 형제 필요
proof.append(('left', level[current_index - 1]))
current_index //= 2
return proof
# 사용 예시
data = ['transaction1', 'transaction2', 'transaction3', 'transaction4']
tree = MerkleTree(data)
print(f"Root hash: {tree.get_root()}")
print(f"Proof for index 0: {tree.get_proof(0)}")
머클 트리의 장점:
동형암호는 암호화된 상태에서 연산을 수행할 수 있는 암호화 방식이다.
# Paillier 암호화 (덧셈 동형암호)
class PaillierCrypto:
def __init__(self, p, q):
self.p = p
self.q = q
self.n = p * q
self.g = self.n + 1 # g = n + 1
self.lambda_n = (p - 1) * (q - 1) // self.gcd(p - 1, q - 1)
self.mu = pow(self.l_func(pow(self.g, self.lambda_n, self.n * self.n)), -1, self.n)
def gcd(self, a, b):
while b:
a, b = b, a % b
return a
def l_func(self, x):
return (x - 1) // self.n
def encrypt(self, m):
"""암호화: E(m) = g^m * r^n mod n²"""
r = self.random_coprime()
c = (pow(self.g, m, self.n * self.n) * pow(r, self.n, self.n * self.n)) % (self.n * self.n)
return c
def decrypt(self, c):
"""복호화: m = L(c^λ mod n²) * μ mod n"""
u = pow(c, self.lambda_n, self.n * self.n)
m = (self.l_func(u) * self.mu) % self.n
return m
def add_homomorphic(self, c1, c2):
"""동형 덧셈: E(m1) * E(m2) = E(m1 + m2)"""
return (c1 * c2) % (self.n * self.n)
def scalar_multiply(self, c, k):
"""스칼라 곱셈: E(m)^k = E(k * m)"""
return pow(c, k, self.n * self.n)
def random_coprime(self):
"""n과 서로소인 랜덤 수 생성"""
import random
while True:
r = random.randint(1, self.n - 1)
if self.gcd(r, self.n) == 1:
return r
# 사용 예시
crypto = PaillierCrypto(61, 53) # p=61, q=53
# 암호화
m1, m2 = 5, 3
c1 = crypto.encrypt(m1)
c2 = crypto.encrypt(m2)
# 동형 연산 (암호화된 상태에서 덧셈)
c_sum = crypto.add_homomorphic(c1, c2)
result = crypto.decrypt(c_sum)
print(f"{m1} + {m2} = {result}") # 5 + 3 = 8
동형암호의 응용:
현재 사용되는 대부분의 공개키 암호는 양자 컴퓨터에 취약하다.
양자 컴퓨터가 위협하는 암호:
양자 내성 암호 (Post-Quantum Cryptography):
# 간단한 격자 기반 암호 개념
import numpy as np
class LatticeCrypto:
def __init__(self, n, q):
self.n = n # 차원
self.q = q # 모듈러스
def generate_key(self):
"""키 생성: A (공개), s (비밀)"""
A = np.random.randint(0, self.q, (self.n, self.n))
s = np.random.randint(0, self.q, self.n)
return A, s
def encrypt(self, A, s, message):
"""암호화: c = A*s + e + m (mod q)"""
e = np.random.randint(-2, 3, self.n) # 작은 오차
c = (A @ s + e + message) % self.q
return c
def decrypt(self, s, c):
"""복호화: m = c - A*s (mod q)"""
m = (c - A @ s) % self.q
return m
# 사용 예시
lattice = LatticeCrypto(4, 97)
A, s = lattice.generate_key()
message = np.array([1, 0, 1, 1])
ciphertext = lattice.encrypt(A, s, message)
decrypted = lattice.decrypt(s, ciphertext)
print(f"Original: {message}")
print(f"Decrypted: {decrypted}")
암호학을 실무에 적용할 때는 수학적 안전성뿐만 아니라 성능도 고려해야 한다.
키 크기별 성능 비교:
메모리 사용량:
# 안전하지 않은 구현 예시
def bad_hash(password):
"""절대 사용하면 안 되는 해시 함수"""
return hash(password) # 파이썬 내장 hash는 암호학적으로 안전하지 않음
# 안전한 구현
import hashlib
import secrets
def secure_hash(password, salt):
"""안전한 해시 함수"""
return hashlib.pbkdf2_hmac('sha256', password.encode(), salt, 100000)
def generate_salt():
"""안전한 솔트 생성"""
return secrets.token_bytes(32)
# 사용 예시
password = "my_password"
salt = generate_salt()
hashed = secure_hash(password, salt)
보안 원칙:
암호학은 이산수학의 실무 적용 중에서도 가장 직접적이고 중요한 분야다.
핵심 포인트:
현재 사용하는 모든 디지털 보안 시스템은 이런 수학적 기초 위에 구축되어 있다.
양자 컴퓨터 시대가 오면서 새로운 수학적 도전이 시작되고 있지만, 이산수학의 기본 원리는 변하지 않을 것이다.
보안을 다룰 때는 항상 수학적 엄밀성과 실무적 고려사항을 균형 있게 생각해야 한다.