이산수학 및 암호학 기초
Discrete Math & Crypto
2단계: 수학으로 자물쇠를 만드는 법 — 정수론, RSA/ECC, 해시와 디지털 서명
1부. 이론적 기초 — "왜 수학이 자물쇠가 되는가?"
1-1. 암호학이 존재하는 이유
인터넷에서 카카오톡 메시지를 보낼 때, 그 메시지는 수십 개의 서버를 물리적으로 거쳐 상대방에게 도달한다. 중간에 누군가 그 패킷을 가로채면 어떻게 될까? 혹은 누군가 당신인 척 메시지를 보낸다면? 이 두 가지 공포, 즉 **기밀성(Confidentiality)**과 **인증(Authentication)**의 문제가 암호학을 탄생시켰다. 고대 로마 시저(Caesar)는 알파벳을 세 칸씩 밀어 쓰는 치환 암호로 기밀성을 지키려 했지만, 그 암호는 26가지 경우의 수를 일일이 시험해보면 5분 만에 뚫린다. 결국 암호학의 역사는 "부수기 더 어려운 자물쇠"를 만드는 역사이며, 현대에 이르러 그 자물쇠의 재료는 다름 아닌 **수학의 난제(Hard Problem)**가 되었다.
그렇다면 '수학적으로 어려운 문제'란 무엇인가? 핵심 아이디어는 이렇다. 어떤 연산은 한 방향으로는 매우 빠르게 계산할 수 있지만, 반대 방향으로 뒤집기는 현재의 컴퓨터로 수십억 년이 걸린다. 이것을 **단방향 함수(One-Way Function)**라고 한다. 예를 들어 두 소수 p = 1,000,033과 q = 999,983을 곱해 n = 999,016,139,039를 만드는 것은 0.0001초면 충분하지만, 반대로 n만 보고 p와 q를 찾아내는 것은 — 이것이 소인수분해(Integer Factorization) 문제인데 — n이 충분히 크면 현존하는 최고 성능의 컴퓨터로도 불가능에 가깝다. 이 비대칭성이 현대 암호학의 출발점이다.
1-2. 모듈러 연산 — 시계 위의 수학
정수론의 문을 열기 위해 가장 먼저 만나야 할 개념은 **모듈러 연산(Modular Arithmetic)**이다. 시계를 떠올려보자. 시계에는 1부터 12까지의 숫자만 있고, 11시에서 3시간이 지나면 14시가 아니라 2시가 된다. 이것이 mod 12 연산이다. 수학적으로는 이렇게 쓴다: 14 ≡ 2 (mod 12). 여기서 ≡ 기호는 '합동(congruent)'을 뜻하며, 두 수가 mod m으로 나눴을 때 같은 나머지를 가진다는 의미다.
더 정확히 정의하면, a ≡ b (mod m) 이란 m이 (a - b)를 나누어 떨어지게 한다는 뜻, 즉 m | (a - b)이다. 이 정의로부터 덧셈, 뺄셈, 곱셈 연산이 모두 mod m 세계 안에서 닫혀 있음을 보일 수 있다. 즉 (a + b) mod m = ((a mod m) + (b mod m)) mod m이 성립한다. 이 성질은 나중에 RSA의 암호화 연산을 가능하게 하는 핵심이다.
[노트 기록] a ≡ b (mod m) 의 정의: m | (a − b). 덧셈과 곱셈의 모듈러 분배 법칙을 손으로 한 번씩 써보자. 예: (17 × 23) mod 7을, 먼저 그대로 계산한 것과 각각 mod 7 후 곱한 것이 같은지 확인하라.
모듈러 세계에서 가장 흥미로운 연산은 **모듈러 역원(Modular Inverse)**이다. 일반 수학에서 5의 역수는 1/5이지만, mod 세계에서는 분수가 없다. 대신 5 × x ≡ 1 (mod 7)을 만족시키는 정수 x를 찾는다. 7의 배수 + 1이 5의 배수인 경우를 찾으면: 5 × 3 = 15 = 2×7 + 1, 즉 x = 3이 5의 mod 7 역원이다. 이 역원이 항상 존재하는 조건은 중요한데, gcd(a, m) = 1, 즉 a와 m이 서로소(coprime)일 때만 존재한다. 이 역원을 효율적으로 찾는 알고리즘이 **확장 유클리드 알고리즘(Extended Euclidean Algorithm)**이며, 이는 RSA에서 개인키(private key)를 계산할 때 실제로 사용된다.
1-3. 소수와 페르마의 소정리
**소수(Prime Number)**는 1과 자기 자신 외에 약수를 갖지 않는 수다. 2, 3, 5, 7, 11, 13... 이 수들은 정수의 "원자(atom)"다 — 모든 정수는 소수들의 곱으로 유일하게 표현된다(이것이 **산술의 기본 정리(Fundamental Theorem of Arithmetic)**다). 소수가 정수론에서 중요한 이유는 이 유일성 때문이고, 암호학에서 중요한 이유는 소인수분해가 매우 어렵기 때문이다.
이제 암호학의 심장부로 들어가는 정리를 소개한다. 페르마의 소정리(Fermat's Little Theorem): p가 소수이고 gcd(a, p) = 1이면, a^(p−1) ≡ 1 (mod p). 왜 이것이 성립하는가? 집합 {1, 2, 3, ..., p−1}에 각 원소에 a를 곱한 집합 {a, 2a, 3a, ..., (p−1)a}을 mod p로 환원하면, p가 소수이므로 이 집합도 역시 {1, 2, ..., p−1}의 순열이 된다. 따라서 두 집합의 모든 원소의 곱이 mod p로 같다 — 이 논증을 전개하면 a^(p−1) ≡ 1 (mod p)이 나온다. 이 정리의 일반화가 오일러의 정리(Euler's Theorem): gcd(a, n) = 1이면 **a^φ(n) ≡ 1 (mod n)**이다. 여기서 φ(n)은 **오일러 파이 함수(Euler's Totient Function)**로, 1부터 n까지 n과 서로소인 정수의 개수다. p, q가 소수이고 n = pq이면 **φ(n) = (p−1)(q−1)**이 됨을 기억해두라 — 이것이 RSA 전체의 뼈대다.
[노트 기록] 페르마 소정리: p 소수, gcd(a,p)=1 → a^(p−1) ≡ 1 (mod p). 오일러 정리: gcd(a,n)=1 → a^φ(n) ≡ 1 (mod n). p,q 소수, n=pq → φ(n)=(p−1)(q−1). 이 세 줄은 RSA의 수학적 증명 전체의 기반이다.
2부. 본 내용 — 공개키 암호의 탄생
2-1. 공개키 혁명: 열쇠 교환 문제
1976년 이전까지 암호학에는 거대한 딜레마가 있었다. 안전하게 통신하려면 먼저 열쇠를 공유해야 하는데, 열쇠를 공유하는 그 과정이 안전하지 않다 — 이것이 **키 배분 문제(Key Distribution Problem)**다. 마치 안전한 상자를 보내려고 열쇠도 같이 보내야 하는 황당한 상황이다. 1976년 Diffie와 Hellman은 *"New Directions in Cryptography"*라는 논문에서 이 딜레마를 근본적으로 뒤집는 아이디어를 발표했다: 열쇠를 두 개 만들어, 하나는 공개하고 하나는 숨기면 된다.
공개키 암호 시스템의 구조는 이렇다. Alice는 한 쌍의 키를 생성한다: 누구에게나 공개하는 **공개키(Public Key)**와 오직 자신만 아는 비밀키(Private Key; 개인키). Bob이 Alice에게 비밀 메시지를 보내고 싶다면, 공개된 Alice의 공개키로 암호화한다. 이렇게 암호화된 메시지는 오직 그에 대응하는 비밀키를 가진 Alice만이 복호화할 수 있다. 왜냐하면 공개키→암호화는 쉽지만, 암호문→메시지 복원은 비밀키 없이는 수학적으로 불가능하기 때문이다. 이 아이디어를 실제 수학으로 구현한 첫 번째 실용적 알고리즘이 바로 RSA다.
2-2. RSA — 소인수분해라는 자물쇠
RSA는 1977년 Rivest, Shamir, Adleman 세 사람이 설계했고, 그들 이름의 앞글자를 딴 것이다(교과서 참조: Introduction to Algorithms, Cormen et al., Chapter 31). RSA의 수학적 구조를 단계별로 분해해보자.
키 생성(Key Generation): 먼저 두 개의 큰 소수 p와 q를 선택한다(현재 권장 보안 수준에서 각 1024비트, 즉 약 300자리 십진수). n = p × q로 모듈러스를 계산하고, φ(n) = (p−1)(q−1)을 구한다. 그 다음 gcd(e, φ(n)) = 1을 만족하는 공개 지수 e를 선택한다(보통 e = 65537 = 2^16 + 1을 사용하는데, 이유는 이진수로 10000000000000001이라 거듭제곱 연산이 빠르기 때문이다). 마지막으로 **d × e ≡ 1 (mod φ(n))**을 만족하는 d를 확장 유클리드 알고리즘으로 계산한다. **(n, e)**가 공개키, **(n, d)**가 비밀키다. p, q, φ(n)은 계산 후 파기한다.
암호화: 메시지 M(0 ≤ M < n)에 대해 암호문 C = M^e mod n. 복호화: 암호문 C로부터 M = C^d mod n.
왜 이것이 작동하는가? C^d = (M^e)^d = M^(ed) (mod n). 그런데 ed ≡ 1 (mod φ(n))이므로 ed = 1 + k·φ(n)이다. 따라서 M^(ed) = M^(1+k·φ(n)) = M × (M^φ(n))^k ≡ M × 1^k = M (mod n) — 마지막 단계에서 오일러 정리를 사용했다. 수학적 난제인 소인수분해가 바로 이 RSA를 깨는 것과 동치라는 것이 핵심이다. n을 보고 p와 q를 분리할 수 없으면 φ(n)을 계산할 수 없고, φ(n) 없이는 d를 구할 수 없으므로 복호화가 불가능하다.
[노트 기록] RSA 전체 플로우: ① p,q 소수 선택 → ② n=pq, φ(n)=(p-1)(q-1) → ③ e 선택(gcd(e,φ(n))=1) → ④ d·e≡1(mod φ(n)) → 공개키(n,e), 비밀키(n,d) → 암호화: C=M^e mod n → 복호화: M=C^d mod n. 증명의 핵심은 오일러 정리.
작은 예시로 직접 확인해보자. p = 61, q = 53을 선택하면 n = 3233, φ(n) = 60 × 52 = 3120. e = 17 (gcd(17, 3120) = 1 확인). 확장 유클리드로 d를 구하면 d = 2753 (17 × 2753 = 46801 = 15 × 3120 + 1, 즉 46801 ≡ 1 (mod 3120) 성립). 메시지 M = 65라면 C = 65^17 mod 3233 = 2790. 복호화: 2790^2753 mod 3233 = 65. 이 계산을 손으로 다 하기엔 너무 크지만, **반복 제곱법(Fast Modular Exponentiation)**을 쓰면 컴퓨터는 이를 매우 빠르게 처리한다.
2-3. 타원곡선 암호 (ECC) — 더 작고 더 강한 자물쇠
RSA가 소인수분해 문제에 의존한다면, **타원곡선 암호(Elliptic Curve Cryptography, ECC)**는 **이산 로그 문제(Discrete Logarithm Problem, DLP)**의 타원곡선 버전에 의존한다. 1985년 Neal Koblitz와 Victor Miller가 독립적으로 제안했으며, 같은 보안 수준에서 RSA보다 훨씬 짧은 키를 사용할 수 있다 — 256비트 ECC 키는 3072비트 RSA와 동등한 보안 강도를 가진다. 이는 스마트폰, IoT 기기 등 자원이 제한된 환경에서 ECC가 압도적으로 선호되는 이유다.
타원곡선은 수식 y² = x³ + ax + b (mod p) (단, 4a³ + 27b² ≠ 0)으로 정의된 점들의 집합이다. 이 곡선 위의 점들에는 덧셈 연산을 정의할 수 있는데, 기하학적으로는 이렇다: 두 점 P, Q를 잇는 직선이 곡선과 만나는 세 번째 점을 x축에 대해 반전시킨 점이 P + Q다. 이 덧셈 연산 아래 타원곡선의 점들은 **아벨 군(Abelian Group)**을 형성한다 — 결합법칙, 교환법칙, 항등원, 역원이 모두 성립한다.
ECC에서 어려운 문제는 이렇다: 점 P에서 시작해 P를 k번 더한 점 Q = kP를 계산하는 것은 쉽다(반복 덧셈). 그런데 Q와 P만 주어졌을 때 k를 찾는 것 — 이것이 **타원곡선 이산 로그 문제(ECDLP)**다 — 은 현재 알려진 어떠한 효율적 알고리즘으로도 풀기 불가능하다. RSA에서 소인수분해가 난제인 것처럼, ECC에서는 ECDLP가 난제다.
실제 ECC 키 교환에서는 **ECDH(Elliptic Curve Diffie-Hellman)**를 사용한다. 공개된 기반점 G와 큰 소수 n이 있을 때, Alice는 비밀 정수 a를 골라 A = aG를 공개하고, Bob은 비밀 정수 b를 골라 B = bG를 공개한다. 그러면 공유 비밀키는 S = aB = a(bG) = abG = b(aG) = bA가 되어, 두 사람만이 동일한 점 S를 알게 된다. 도청자는 A = aG와 B = bG를 보지만 ECDLP 때문에 a나 b를 알 수 없으므로 S를 계산할 수 없다.
[노트 기록] ECC 핵심: ① 타원곡선: y²=x³+ax+b (mod p), 위의 점들이 군 형성 ② 연산: kP = P를 k번 더함 ③ 난제: Q=kP일 때 k 찾기 = ECDLP ④ ECDH: Alice 비밀 a, Bob 비밀 b, 공유비밀 = abG.
2-4. 해시 함수 — 디지털 지문
**해시 함수(Hash Function)**는 임의 길이의 입력을 받아 고정 길이의 출력(해시값, 다이제스트)을 돌려주는 함수다. SHA-256의 경우 입력이 1바이트든 1기가바이트든 항상 256비트(64자리 16진수) 출력을 낸다. 암호학적으로 안전한 해시 함수(Cryptographic Hash Function)는 세 가지 성질을 반드시 만족해야 한다.
첫째, 역상 저항성(Preimage Resistance): 해시값 h가 주어졌을 때 h = H(M)을 만족하는 M을 찾기 불가능해야 한다. 둘째, 제2역상 저항성(Second Preimage Resistance): M과 H(M)이 주어졌을 때, H(M) = H(M')을 만족하는 M' ≠ M을 찾기 불가능해야 한다. 셋째, 충돌 저항성(Collision Resistance): H(M) = H(M')을 만족하는 임의의 두 쌍 M ≠ M'를 찾기 불가능해야 한다. 충돌 저항성은 제2역상 저항성보다 강한 조건이 아닌 것처럼 보이지만, 생일 역설(Birthday Paradox) 때문에 충돌 공격은 역상 공격의 약 절반 작업량으로 가능하다 — 이것이 SHA-256이 256비트를 쓰는 이유 중 하나다.
SHA-256의 내부 구조는 Merkle-Damgård 구조를 기반으로 한다. 입력을 512비트 블록으로 나눠 각 블록을 이전 출력(chaining value)과 함께 압축 함수에 넣어 처리하는 반복적 구조다. 각 라운드에서 32비트 단어들에 대해 비트 회전, XOR, AND, OR, 덧셈의 조합으로 정보를 뒤섞는다. 이 과정이 64라운드 반복되면 입력의 단 1비트만 바꿔도 출력의 절반 이상 비트가 뒤집히는 **눈사태 효과(Avalanche Effect)**가 발생한다 — 이것이 해시 함수의 역상 저항성을 직관적으로 보장해준다.
2-5. 디지털 서명 — 수학으로 도장 찍기
해시와 공개키 암호를 결합하면 **디지털 서명(Digital Signature)**이 탄생한다. 현실에서 서명은 "이 문서를 내가 작성했고, 이후 변조되지 않았음"을 증명한다. 디지털 서명은 이 두 가지 — **인증(Authentication)**과 무결성(Integrity) — 를 수학적으로 보장한다.
RSA 서명의 원리를 먼저 보자. Alice가 문서 M에 서명하려 한다. 먼저 M의 해시를 계산한다: h = H(M). 그 다음 자신의 비밀키로 h를 "암호화"한다: σ = h^d mod n. 이 σ가 서명이다. Alice는 M과 σ를 함께 보낸다. 검증자 Bob은 Alice의 공개키로 서명을 "복호화"한다: h' = σ^e mod n = h. 그리고 자신이 받은 M의 해시 H(M)과 h'를 비교한다. 같으면 (1) 이 서명은 Alice의 비밀키로 만들어졌으므로 Alice가 서명했고, (2) H(M)이 같으므로 문서가 변조되지 않았음이 증명된다.
ECC 기반의 **ECDSA(Elliptic Curve Digital Signature Algorithm)**는 동일한 논리를 타원곡선 위에서 구현한다. 서명 과정에서 무작위 nonce k를 사용해 R = kG의 x좌표 r을 계산하고, s = k⁻¹(H(M) + r·priv) mod n을 서명의 두 번째 성분으로 계산한다. 검증 시에는 공개키를 이용해 역산해 동일한 점 R을 복원할 수 있는지 확인한다. 여기서 nonce k는 절대로 재사용해서는 안 된다 — 같은 k를 두 번 쓰면 대수 방정식 두 개로 비밀키가 바로 노출된다. 2010년 Sony PlayStation 3가 ECDSA에서 고정 k를 사용해 비밀키가 공개된 실제 사례가 있다.
[노트 기록] 디지털 서명 = 해시 + 비밀키 암호화. RSA 서명: σ = H(M)^d mod n. 검증: σ^e mod n == H(M). 무결성 증명 = 해시 일치. 인증 증명 = 비밀키 소유자만 생성 가능.
3부. 테크니컬 심화 — 실제 구현의 세계
3-1. 빠른 모듈러 거듭제곱
M^e mod n을 계산할 때, e가 65537처럼 큰 수라면 M을 65537번 곱하는 것은 불가능하다. 대신 **반복 제곱법(Square-and-Multiply, 혹은 Fast Modular Exponentiation)**을 사용한다. e를 이진수로 표현해(65537 = 10000000000000001₂), 이진수의 각 비트에 따라 제곱과 곱셈을 결정하는 방식으로, O(log e)번의 연산만으로 계산이 끝난다. 65537번 곱셈 대신 17번의 연산으로 처리된다는 것이 핵심이다. Python에서 pow(M, e, n) 함수가 바로 이 알고리즘을 내장하고 있다.
3-2. 소수 판별 — 밀러-라빈 테스트
RSA 키 생성 시 512비트 이상의 소수 p, q를 찾아야 한다. 이 크기에서 에라토스테네스의 체는 메모리조차 부족하다. 실무에서는 **밀러-라빈 소수 판별법(Miller-Rabin Primality Test)**을 사용한다. 이는 페르마 소정리를 확률적으로 확장한 것으로, n이 소수가 아니라면 무작위로 선택한 검증자(witness) a에 대해 특정 조건이 성립하지 않는다는 성질을 이용한다. k번 반복하면 합성수를 소수로 오판할 확률은 최대 4^(-k)로 감소한다 — k=40이면 오류 확률은 2^(-80)으로 우주의 나이 동안 틀릴 가능성이 없는 수준이다.
3-3. 패딩 — 교과서 RSA의 치명적 약점
지금까지 설명한 "교과서 RSA(Textbook RSA)"는 실제로 안전하지 않다. 왜냐하면 결정론적(deterministic)이기 때문이다 — 같은 메시지는 항상 같은 암호문을 만든다. 공격자가 M이 "YES" 또는 "NO" 중 하나임을 알 경우, 각각을 암호화해 비교하면 바로 알아낼 수 있다. 또한 메시지가 작을 경우 e가 작은 값(예: e=3)이면 M^e < n이 되어 단순 세제곱근으로 복호화된다. 이를 막기 위해 실제 RSA는 **OAEP(Optimal Asymmetric Encryption Padding)**를 사용해 암호화 전 메시지에 무작위성을 추가한다. 즉 현실의 RSA는 항상 RSA-OAEP다.
3-4. 타원곡선의 표준 파라미터
ECC를 구현할 때 타원곡선의 파라미터 a, b, p, G, n을 직접 선택하는 것은 극도로 위험하다 — 특별히 약한 구조의 곡선이 존재하기 때문이다. 따라서 NIST, ANSI 등이 검증된 표준 곡선을 제시하고 있으며, 실무에서는 P-256 (secp256r1), secp256k1 (비트코인이 사용), Curve25519 등을 사용한다. Curve25519는 Daniel J. Bernstein이 설계했으며, ECDLP 이외의 부채널 공격(Side-Channel Attack)에도 강인하도록 수학적으로 특별히 설계된 곡선이다. 현재 TLS 1.3, SSH, WhatsApp 등 대부분의 현대 보안 프로토콜이 Curve25519를 기반으로 한다.
4부. 프로젝트 — 손으로 직접 증명하라
지금까지의 이론은 이 프로젝트들을 위한 모든 준비다. 아래 세 가지 프로젝트는 각각 RSA 구현, 디지털 서명 및 해시 무결성, ECC 원리 탐구를 다루며, 전체 약 40분의 사고와 구현 시간을 필요로 한다. 정답은 없다. 스스로 수학적 원리를 코드로 번역하는 것이 목표다.
Project A: Mini RSA 암호 시스템 구현
작은 소수들로 RSA의 완전한 키 생성→암호화→복호화 사이클을 Python으로 구현하라. 모든 계산은 직접 구현해야 하며, rsa, cryptography 등의 라이브러리는 사용할 수 없다. pow(a, b, n) 한 가지는 허용한다.
문제 1: 두 소수 p = 61, q = 53을 입력받아 공개키 (n, e)와 비밀키 (n, d)를 출력하는 함수 generate_rsa_keys(p, q, e=17)를 작성하라. d를 직접 반복문으로 구하되, 확장 유클리드 알고리즘으로도 구현해 결과가 같은지 비교하라.
문제 2: 메시지 정수 M (단, 0 < M < n)을 입력받아 암호문 C를 반환하는 encrypt(M, e, n)과 암호문 C로부터 M을 복원하는 decrypt(C, d, n)을 구현하고, M = 42로 완전한 왕복(encrypt → decrypt)을 검증하라.
문제 3: RSA는 실제로 텍스트 메시지에 직접 적용하지 않는다. 문자열 "HELLO"를 정수로 변환해 각 문자를 개별 암호화하는 간단한 방식을 구현했을 때, 이 방식의 어떤 약점이 있는지 코드로 직접 공격을 시연하라(힌트: 각 문자의 암호문 목록을 미리 계산하면 무엇이 보이는가?). 이것이 앞서 설명한 "교과서 RSA의 결정론적 약점"이다.
문제 4: p × q = n을 알 때, 만약 n의 소인수분해를 직접 시도한다면 어느 크기부터 현실적으로 불가능해지는지 실험하라. n이 15비트, 20비트, 30비트, 40비트일 때 브루트포스(2부터 √n까지 나눠보기)의 실행 시간을 측정해 표로 기록하고, 그 결과로부터 RSA에서 왜 2048비트 이상을 권장하는지 논리적으로 설명하라.
Project B: 해시 기반 디지털 서명 시스템
Python의 hashlib 라이브러리(SHA-256 계산 용도로만 허용)와 Project A에서 만든 RSA 함수를 이용해 디지털 서명 시스템을 구현하라.
문제 1: 문자열 메시지 M을 받아 SHA-256 해시 정수값(16진수 → 정수 변환)을 반환하는 함수를 작성하라. 그 다음 이 해시값을 RSA 비밀키로 "서명"하고, 공개키로 "검증"하는 전체 파이프라인 sign(M, d, n)과 verify(M, signature, e, n)을 구현하라.
문제 2: 원본 메시지 "Transfer 100 to Bob"으로 단 한 글자 바꿨을 때 검증이 어떻게 실패하는지 시연하고, 해시의 눈사태 효과로 두 해시값의 비트 차이가 얼마나 나는지 직접 계산해 출력하라.
문제 3: 서명 검증 시스템에 세 종류의 위변조 시나리오를 설계하고 각각 코드로 구현해 시스템이 올바르게 거부하는지 확인하라: (a) 메시지만 변조된 경우, (b) 서명만 변조된 경우, (c) 다른 사람의 공개키로 검증을 시도하는 경우. 각 경우에 왜 검증이 실패하는지 수학적으로 1~2문장으로 설명하라.
문제 4 (도전): SHA-256이 아닌 SHA-1 (길이 160비트)을 사용했을 때 동일한 보안 수준을 위해 RSA 키 길이를 어떻게 조정해야 하는지, 생일 역설 관점에서 논하라. (힌트: 충돌 찾기 복잡도 = 2^(n/2), 여기서 n은 해시 출력 비트수)
Project C: 타원곡선 위의 점 연산 탐구
주의: 이 프로젝트는 수식과 수학적 탐구 중심이며, 코드보다 수학적 사고를 요구한다. 작은 prime field 위의 타원곡선을 직접 손계산하고, 필요한 부분은 Python으로 검증하라.
문제 1: 타원곡선 E: y² ≡ x³ + x + 6 (mod 11) 위의 모든 점을 직접 열거하라. x = 0, 1, 2, ..., 10에 대해 x³ + x + 6 (mod 11)이 mod 11에서 제곱수인지 확인하고(이를 Legendre Symbol 또는 직접 제곱 열거로 판단), 해당 y 값들을 구하라. 무한원점 O(항등원)를 포함해 이 곡선 위 점의 총 개수를 세라.
문제 2: 위 곡선에서 점 P = (2, 7)에 대해 2P (= P + P)를 직접 계산하라. 접선의 기울기(타원곡선 점 두 배 공식: λ = (3x₁² + a) × (2y₁)⁻¹ mod p)를 이용하라. 역원 (2y₁)⁻¹ mod p는 확장 유클리드 알고리즘으로 구하라. 결과를 Python 코드로 작성한 점 덧셈 함수로 검증하라.
문제 3: 같은 곡선에서 kP (k = 1, 2, 3, ..., n)를 반복 계산해 처음으로 무한원점 O가 나오는 k, 즉 점 P의 **위수(order)**를 구하라. 이 위수 n이 ECDLP 보안과 어떤 관계가 있는지, 위수가 클수록 왜 더 안전한지 설명하라.
문제 4 (통합): Project A에서 구현한 작은 RSA와 이번 Project C에서 계산한 ECC의 보안 수준을 "키 비트 대비 공격 복잡도" 관점에서 비교하라. 각각 어떤 수학적 난제에 의존하는지, 그리고 양자 컴퓨터(Shor 알고리즘)가 두 난제에 어떤 영향을 미치는지 조사해 서술하라. (이것이 3단계 — 포스트 양자 암호학의 필요성을 예고한다.)
평가 기준 (자기 평가용)
프로젝트를 마친 후 아래 기준으로 스스로 점검하라. 암호 시스템 정합성(50점): RSA 왕복 테스트가 모든 입력에서 성립하는가, 서명 검증이 세 위변조 시나리오 모두에서 올바르게 실패하는가. 보안 공격 방어율(30점): 교과서 RSA의 약점 공격을 직접 시연하고 그 이유를 수학으로 설명했는가, 비트 차이와 눈사태 효과를 정량적으로 측정했는가. 기술 문서(20점): 각 함수에 입력/출력/수식을 주석으로 명시하고, 프로젝트 D(도전 문제)에 대한 논리적 서술이 자신의 언어로 작성되어 있는가.
이 세 프로젝트를 완성했다면, 공개키 암호학의 수학적 기반 위에서 실제로 손을 더럽혀 본 것이다. 소인수분해와 이산 로그라는 수학의 "미해결 난제"가 수십억 명의 온라인 통신을 지키고 있다는 사실 — 그 무게를 이제 조금은 체감할 수 있을 것이다. 3단계에서는 이 체계 전체를 무너뜨릴 수도 있는 양자 컴퓨터에 맞서는 격자 암호와 영지식 증명을 탐구하게 된다.