암호학의 수학 (Mathematics of Cryptography)

인터넷 뱅킹, 메신저, 전자서명, 소프트웨어 업데이트, 전자상거래는 모두 "누가 보아도 되는 정보"와 "반드시 숨겨야 하는 정보"를 구분해야 합니다. 이때 필요한 것이 암호학(Cryptography)이며, 그 중심에는 언제나 수학이 있습니다.

암호학은 자물쇠나 비밀번호만의 문제가 아닙니다. 어떤 계산은 빨리 할 수 있는데, 그 계산을 거꾸로 뒤집는 일은 매우 어렵다는 비대칭성을 찾아내고, 그 위에 통신 규칙을 세우는 학문입니다. 소수, 모듈러 산술, 군(Group), 체(Field), 확률, 정보 이론, 격자(Lattice) 같은 수학이 모두 여기에 연결됩니다.

왜 암호학에 수학이 필요합니까

암호학의 목표는 크게 네 가지입니다. 첫째, 제3자가 내용을 읽지 못하게 하는 기밀성(Confidentiality)입니다. 둘째, 내용이 중간에 바뀌지 않았음을 확인하는 무결성(Integrity)입니다. 셋째, 누가 보냈는지 확인하는 인증(Authentication)입니다. 넷째, 처음부터 서로 비밀을 공유하지 않은 두 사람이 안전하게 키를 만드는 키 교환(Key Exchange)입니다.

이 목표들은 직관만으로는 달성되지 않습니다. 암호학은 "공격자가 계산 자원을 얼마나 써도 풀기 어려운가"를 따져야 하므로, 결국 계산 복잡도와 확률, 대수 구조가 필요합니다. 그래서 암호학은 공학이면서 동시에 매우 수학적인 분야입니다.

선수 지식: 정수론, 추상대수학, 선형대수학, 확률론, 이산수학

난이도: ★★★★☆ (대학교 초중반 수준, 다만 직관 위주로 읽을 수 있습니다)

모듈러 산술과 역원

모듈러 산술(Modular Arithmetic)은 "나머지"를 기준으로 수를 다루는 계산입니다. 시계가 12시를 지나면 다시 1시로 돌아오듯이, 법(modulus) $m$을 기준으로 같은 나머지를 갖는 수를 같은 것으로 봅니다.

암호학에서는 수가 너무 커지기 때문에, 대부분의 계산을 $\bmod m$ 환경에서 수행합니다. RSA에서는 $\bmod n$, Diffie-Hellman과 ElGamal에서는 $\bmod p$, AES에서는 유한체 연산이 중심이 됩니다.

합동식은 같은 나머지끼리 묶습니다

예를 들어 법 11에서는 $7, 18, 29, -4$가 모두 같은 나머지 7을 줍니다. 그래서

라고 씁니다. 암호학은 정수 전체를 그대로 들고 다니기보다, 이렇게 같은 나머지끼리 하나의 상태로 압축한 세계에서 계산합니다. 이 생각 덕분에 수가 매우 커져도 결과는 항상 유한한 개수의 잔여류(residue class) 중 하나로 돌아옵니다.

역원은 왜 중요합니까

곱셈의 역연산을 하려면 모듈러 역원(Modular Inverse)이 필요합니다. $a^{-1}$이란

을 만족하는 수입니다. 이 역원은 항상 존재하지 않습니다. $\gcd(a,m)=1$일 때에만 존재합니다. 이 조건이 중요한 이유는, 암호학의 많은 알고리즘이 결국 "곱셈을 되돌리는 일"을 해야 하기 때문입니다. RSA의 비밀 지수 $d$도 $e$의 역원으로 정의되고, ECDSA의 서명 계산에도 난수 $k$의 역원이 필요합니다.

작은 수로 보는 역원 찾기

법 11에서 7의 역원을 직접 구해 보겠습니다. 유클리드 호제법을 먼저 쓰면

입니다. 이제 마지막 식의 1을 앞 식들로 다시 바꾸어 올라가면

을 얻습니다. 따라서

이고, 법 11에서는 $-3 \equiv 8$이므로

입니다. 즉, 모듈러 환경에서 "7로 나눈다"는 말은 실제로는 8을 곱한다는 뜻입니다. 이런 생각이 RSA의 비밀 지수, ECDSA의 nonce 역원 계산으로 이어집니다.

빠른 거듭제곱

암호학은 거듭제곱을 매우 자주 사용합니다. 하지만 $a^{1000000}$을 곧바로 계산하면 너무 느립니다. 그래서 제곱 분할(binary exponentiation)을 사용합니다. 지수를 이진수로 쪼개면 필요한 곱셈 횟수를 크게 줄일 수 있습니다.

function modPow(base, exp, mod) {
  var result = 1;
  base = base % mod;
  while (exp > 0) {
    if (exp % 2 === 1) {
      result = (result * base) % mod;
    }
    base = (base * base) % mod;
    exp = Math.floor(exp / 2);
  }
  return result;
}

이 알고리즘은 RSA의 암호화와 복호화, Diffie-Hellman의 공개값 계산, Miller-Rabin 소수 판정 등에서 반복해서 등장합니다.

function modInverse(a, m) {
  var r0 = m, r1 = a;
  var s0 = 0, s1 = 1;
  while (r1 !== 0) {
    var q = Math.floor(r0 / r1);
    var r2 = r0 - q * r1;
    r0 = r1;
    r1 = r2;
    var s2 = s0 - q * s1;
    s0 = s1;
    s1 = s2;
  }
  if (r0 !== 1) return null;
  return (s0 % m + m) % m;
}

여기서 반환값이 null이면 역원이 존재하지 않는다는 뜻입니다. 즉, 해당 수는 모듈러 환경에서 나눗셈의 대상이 될 수 없습니다.

제곱 분할을 손으로 따라가 봅시다

$7^{13} \bmod 11$을 계산한다고 하겠습니다. 13을 이진수로 쓰면 $1101_2$이고, 이는 $13 = 8 + 4 + 1$이라는 뜻입니다. 따라서 $7^1, 7^2, 7^4, 7^8$만 만들면 충분합니다.

즉, 큰 지수는 "곱셈을 하나씩 모두 수행하는 문제"가 아니라 "몇 번 제곱하고 필요한 항만 선택하는 문제"로 바뀝니다. RSA, Diffie-Hellman, 밀러-라빈 소수 판정이 모두 이 아이디어를 반복 사용합니다.

소수, 소인수분해, RSA

RSA는 소인수분해(Factorization)의 어려움에 기대는 대표적인 공개키 암호입니다. 소수 $p, q$를 곱해 $n=pq$를 만드는 계산은 쉽지만, $n$만 보고 다시 $p, q$를 찾는 계산은 매우 어렵다고 믿습니다. 이 비대칭성이 공개키와 비밀키를 분리하는 근거가 됩니다.

정의와 구조

RSA에서는 두 큰 소수 $p, q$를 골라 $n=pq$를 만들고,

을 계산합니다. 그런 다음 $\gcd(e,\phi(n))=1$인 공개 지수 $e$를 고르고,

을 만족하는 비밀 지수 $d$를 구합니다. 공개키는 $(n,e)$이고 비밀키는 $d$입니다. 암호화는 $C \equiv M^e \pmod{n}$, 복호화는 $M \equiv C^d \pmod{n}$입니다.

왜 작동합니까

$ed = 1 + k\phi(n)$이므로, 오일러 정리(Euler's Theorem) 또는 더 정확하게는 카마이클 함수와 중국인의 나머지 정리(CRT)를 사용하면

이 성립합니다. 즉, 공개키로 올린 거듭제곱을 비밀키로 한 번 더 거듭제곱하면 원래 메시지로 돌아옵니다.

작은 수로 보는 RSA 전체 과정

실제 RSA는 훨씬 더 큰 소수를 쓰지만, 원리를 보기 위해 작은 수로 전체 과정을 따라가 보겠습니다.

function rsaToyRoundTrip() {
  var p = 61;
  var q = 53;
  var n = p * q;
  var phi = (p - 1) * (q - 1);
  var e = 17;
  var d = modInverse(e, phi);
  var message = 65;
  var cipher = modPow(message, e, n);
  var plain = modPow(cipher, d, n);
  return { n: n, e: e, d: d, cipher: cipher, plain: plain };
}

CRT로 복호화를 더 빠르게 할 수 있습니다

실제 구현은 큰 법 $n$에서 한 번에 거듭제곱하기보다, 더 작은 법 $p$와 $q$에서 따로 계산한 뒤 다시 합칩니다.

이 과정은 중국인의 나머지 정리(CRT) 때문에 원래 복호화와 같은 결과를 주면서, 계산은 훨씬 빠르게 만들어 줍니다. 즉, RSA는 단순히 공식 하나를 아는 것이 아니라, 어떤 구조를 이용해 계산을 줄이는지도 중요합니다.

응용과 한계

RSA는 공개키 암호의 고전적인 표준으로서 매우 중요한 역사적 의미를 가집니다. 다만 핵심 난제가 소인수분해이므로, 쇼어 알고리즘을 갖춘 충분히 큰 양자 컴퓨터가 실용화되면 구조적으로 위협을 받습니다. 그래서 오늘날 암호학은 RSA를 이해하는 동시에, 그 이후의 체계도 함께 공부해야 합니다.

쇼어 알고리즘의 핵심은 소인수분해를 정면으로 밀어붙이는 것이 아니라, 함수 $f(x)=a^x \bmod N$의 주기를 찾는 문제로 바꾸는 데 있습니다. 그런 다음 양자 상태의 위상과 양자 푸리에 변환을 이용해 그 주기를 드러냅니다. 계산 관점의 배경은 양자컴퓨팅의 수학에서 이어서 볼 수 있습니다.

군과 이산로그

이산 로그(Discrete Logarithm)는 공개키 암호학의 또 다른 중심 문제입니다. 소인수분해가 "곱하기는 쉽고 분해는 어렵다"라면, 이산 로그는 "거듭제곱은 쉽고 지수 찾기는 어렵다"라고 요약할 수 있습니다.

순환군과 생성원

소수 $p$에 대하여 $\mathbb{F}_p^\times = \{1,2,\dots,p-1\}$는 곱셈에 대해 군을 이룹니다. 이 군이 순환군일 때, 어떤 원소 $g$의 거듭제곱들이 군 전체를 만들어 냅니다. 이런 $g$를 원시근(Primitive Root) 또는 생성원(generator)이라 합니다.

이때 공개값은

의 형태로 만들어집니다. 여기서 $x$는 비밀 지수입니다. $g$와 $y$를 아는 사람은 앞 방향 계산은 볼 수 있지만, 거꾸로 $x$를 찾아내는 문제는 어려운 것으로 여겨집니다.

Diffie-Hellman과 ElGamal

Diffie-Hellman 키 교환은 두 사람이 서로의 비밀 지수를 곱한 효과 $g^{ab}$를 공유하도록 설계됩니다.

1. 공개 매개변수 $p, g$를 정합니다.
2. Alice는 비밀 $a$를 정하고 $A=g^a \bmod p$를 보냅니다.
3. Bob은 비밀 $b$를 정하고 $B=g^b \bmod p$를 보냅니다.
4. Alice는 $B^a$, Bob은 $A^b$를 계산하면 둘 다 $g^{ab} \bmod p$를 얻습니다.

ElGamal은 같은 구조를 이용해 암호화와 서명을 구성합니다. 핵심은 비밀 스칼라를 한 번 곱해서 공개값을 만들기는 쉽지만, 공개값만으로 비밀 스칼라를 복원하기는 어렵다는 점입니다.

키 교환을 눈으로 보면

중요한 점은 Alice와 Bob이 비밀 수 $a, b$를 직접 보내지 않는다는 것입니다. 공개 채널에는 $A = g^a$, $B = g^b$만 지나가고, 각자는 받은 공개값에 자신의 비밀 지수를 한 번 더 적용해 같은 $g^{ab}$를 얻습니다.

작은 수로 보는 Diffie-Hellman 예시

$p=23$, $g=5$를 공개 매개변수로 두고, Alice가 $a=6$, Bob이 $b=15$를 고른다고 하겠습니다.

도청자는 $p, g, A, B$는 볼 수 있지만, 6과 15는 직접 볼 수 없습니다. 따라서 공개값만으로 공유 비밀 2를 얻으려면 결국 이산 로그 또는 그에 가까운 어려운 문제를 풀어야 합니다.

일반군 공격의 시각으로 보면

이산 로그가 "완전히 불가능"한 것은 아닙니다. 다만 현재 알려진 공격들의 비용이 매우 커서 실용적으로 어렵다고 보는 것입니다. 특히 군의 특별한 구조를 쓰지 않는 일반군(generic group) 공격은 다음과 같은 규모를 가집니다.

따라서 공개키 파라미터를 고를 때는 단순히 "숫자가 커 보이는가"보다, 그 군의 크기와 알려진 공격 복잡도를 함께 보아야 합니다. ECC가 짧은 키로도 강한 이유도 바로 이 관점과 연결됩니다.

유한체와 대칭키 암호

체(Field)는 덧셈, 뺄셈, 곱셈, 나눗셈이 모두 잘 정의되는 수 체계입니다. 암호학에서는 원소가 유한 개뿐인 유한체(Finite Field)가 특히 중요합니다. 공개키 암호에서 유한체는 군의 무대가 되고, 대칭키 암호에서는 바이트 단위 연산을 안정적으로 설계하는 재료가 됩니다.

$\mathbb{F}_p$와 $\mathrm{GF}(2^m)$

가장 익숙한 유한체는 소수 $p$를 법으로 하는 $\mathbb{F}_p$입니다. 여기서는 $0,1,\dots,p-1$만 쓰고, 연산 결과도 항상 다시 이 집합 안으로 돌아옵니다. 타원곡선 암호와 Diffie-Hellman은 이런 유한체 위에서 많이 정의됩니다.

반면 컴퓨터는 비트를 다루므로, 실제 구현에서는 $\mathrm{GF}(2^m)$도 매우 중요합니다. 여기서는 덧셈이 사실상 XOR와 같고, 곱셈은 다항식을 곱한 뒤 기약다항식으로 나머지를 취하는 방식으로 정의됩니다.

작은 수로 보는 $\mathrm{GF}(2^8)$ 계산

AES에서는 바이트 하나를 단순한 정수가 아니라 다항식처럼 다룹니다. 예를 들어

처럼 볼 수 있습니다. 이때 덧셈은 자리올림 없는 더하기이므로 XOR와 같습니다. 따라서

입니다. 곱셈은 더 복잡하지만, 핵심 블록은 한 번 왼쪽으로 밀고 필요하면 기약다항식으로 줄이는 xtime 연산입니다.

function xtime(byte) {
  byte = byte << 1;
  if (byte & 0x100) {
    byte = byte ^ 0x11b;
  }
  return byte & 0xff;
}

function gfMultiply(a, b) {
  var result = 0;
  while (b > 0) {
    if (b & 1) {
      result = result ^ a;
    }
    a = xtime(a);
    b = b >> 1;
  }
  return result;
}

즉, AES의 바이트 연산은 단순한 비트 조작이 아니라 유한체 연산입니다. 이 관점 덕분에 역원, 선형 변환, 비선형 변환을 정확한 수학 구조 위에 올릴 수 있습니다.

AES와 유한체

AES는 바이트를 단순한 0부터 255까지의 숫자로만 보는 것이 아니라, $\mathrm{GF}(2^8)$의 원소로 봅니다. 이렇게 하면 각 바이트에 대해 역원을 정의할 수 있고, 선형 변환과 비선형 변환을 안정적으로 설계할 수 있습니다. 특히 S-box는 유한체 역원과 아핀 변환을 조합해 만들어집니다.

즉, 대칭키 암호는 "정수론 기반"이라기보다 "유한체와 선형대수 기반"에 가깝습니다. 여기서 중요한 것은 어떤 계산이 빠른가뿐 아니라, 작은 변화가 전체 상태에 얼마나 잘 퍼지는가, 역연산이 가능한가, 패턴이 얼마나 숨겨지는가입니다.

AES 한 라운드의 수학

AES 한 라운드는 보통 SubBytes, ShiftRows, MixColumns, AddRoundKey 네 단계로 설명합니다. 이 네 단계는 각각 다른 수학적 역할을 맡습니다.

SubBytes는 바이트마다 비선형 변환을 주어 패턴을 깨뜨리고, ShiftRows는 위치를 섞고, MixColumns는 각 열에 행렬을 곱해 정보가 주변 바이트로 퍼지도록 만듭니다. 마지막 AddRoundKey는 비밀키와 XOR해 실제 비밀을 주입합니다.

예를 들어 MixColumns는 각 열 벡터에 다음 행렬을 $\mathrm{GF}(2^8)$ 위에서 곱하는 연산으로 볼 수 있습니다.

여기서 $02, 03, 01$은 십진수 가중치가 아니라 유한체 $\mathrm{GF}(2^8)$의 원소입니다. 즉, 평범한 행렬 곱처럼 보이지만 실제 계산 규칙은 유한체 연산입니다.

타원곡선과 ECC

타원곡선 암호(ECC)는 유한체 위의 타원곡선 점들이 이루는 군을 사용합니다. 곡선 위의 점 $P$를 여러 번 더해 $Q=nP$를 만드는 계산은 빠르지만, $P$와 $Q$가 주어졌을 때 $n$을 찾는 타원곡선 이산로그 문제(ECDLP)는 어려운 것으로 알려져 있습니다.

점 덧셈과 스칼라 곱

실수 위의 타원곡선에서는 직선이 곡선을 만나는 세 번째 점을 이용해 덧셈을 정의할 수 있고, 유한체 위에서는 이 공식이 대수적으로 옮겨집니다. 그 결과 "점 하나를 여러 번 더하는 계산", 즉 스칼라 곱(Scalar Multiplication)이 핵심 연산이 됩니다.

ECC의 장점은 같은 보안 수준을 더 짧은 키 길이로 얻을 수 있다는 점입니다. 이는 저장 공간, 전송량, 모바일 기기 성능 측면에서 큰 장점이 됩니다.

작은 곡선에서 점 덧셈을 계산해 봅시다

유한체 $\mathbb{F}_p$ 위 곡선 $y^2 \equiv x^3 + ax + b \pmod{p}$에서 두 점 $P=(x_1,y_1)$, $Q=(x_2,y_2)$를 더할 때는 먼저 기울기 역할을 하는 값 $\lambda$를 구합니다.

같은 점을 두 번 더하는 경우에는

를 씁니다. 여기서도 핵심은 결국 모듈러 역원입니다.

예를 들어 곡선

위에서 $G=(5,1)$를 잡으면

가 됩니다. 즉, 이 예시에서는 $G$를 19번 더하면 항등원 $\mathcal{O}$로 돌아옵니다.

function mod(value, p) {
  return (value % p + p) % p;
}

function pointAdd(P, Q, a, p) {
  if (P === null) return Q;
  if (Q === null) return P;

  var x1 = P[0];
  var y1 = P[1];
  var x2 = Q[0];
  var y2 = Q[1];
  var lambda;
  var x3;
  var y3;

  if (x1 === x2 && mod(y1 + y2, p) === 0) {
    return null;
  }

  if (x1 === x2 && y1 === y2) {
    if (mod(2 * y1, p) === 0) {
      return null;
    }
    lambda = mod((3 * x1 * x1 + a) * modInverse(mod(2 * y1, p), p), p);
  } else {
    lambda = mod((y2 - y1) * modInverse(mod(x2 - x1, p), p), p);
  }

  x3 = mod(lambda * lambda - x1 - x2, p);
  y3 = mod(lambda * (x1 - x3) - y1, p);
  return [x3, y3];
}

function scalarMultiply(k, P, a, p) {
  var result = null;
  var addend = P;
  while (k > 0) {
    if (k % 2 === 1) {
      result = pointAdd(result, addend, a, p);
    }
    addend = pointAdd(addend, addend, a, p);
    k = Math.floor(k / 2);
  }
  return result;
}

이 알고리즘은 구조적으로 modPow와 매우 닮아 있습니다. 거듭제곱에서 제곱을 반복하듯이, ECC에서는 점 두 배를 반복하면서 필요한 항만 더합니다. 그래서 이를 두 배 후 더하기(double-and-add)라고 부릅니다.

ECDH와 ECDSA

ECDH는 Diffie-Hellman을 타원곡선 위로 옮긴 것이고, ECDSA는 타원곡선 위에서 디지털 서명을 구현한 것입니다. 두 경우 모두 비밀 스칼라와 공개 점의 관계가 핵심입니다.

해시, 충돌, 디지털 서명

해시 함수(Hash Function)는 긴 입력을 짧은 고정 길이 출력으로 압축하는 함수입니다. 좋은 암호학적 해시 함수는 출력만 보고 원래 입력을 찾기 어렵고(역상 저항성), 같은 해시값을 갖는 다른 입력을 찾기 어렵고(충돌 저항성), 한 입력과 같은 해시를 갖는 다른 입력을 찾기 어렵습니다(제2역상 저항성).

충돌과 생일 역설

출력 길이가 $n$비트인 해시 함수에서 무작위 충돌은 대략 $2^{n/2}$번 정도 시도하면 나타날 수 있습니다. 이것이 생일 역설(Birthday Paradox)입니다. 그래서 해시 출력 길이는 충돌 저항성과 직접 연결됩니다.

예를 들어 256비트 해시의 충돌 저항성은 대략 128비트 수준으로 이해합니다. 이 차이는 "출력 길이"와 "실제 보안 비트"를 구분해야 한다는 점을 보여 줍니다.

왜 서명 전에 해시합니까

디지털 서명은 보통 긴 문서 전체를 직접 서명하지 않고, 먼저 해시값을 만든 뒤 그 짧은 요약값에 서명을 합니다. 이렇게 하면 계산이 빠르고, 문서가 조금만 바뀌어도 해시값이 크게 바뀌므로 위조 탐지가 쉬워집니다.

눈사태 효과를 직관으로 봅시다

좋은 해시 함수는 입력이 한 비트만 바뀌어도 출력의 많은 비트가 함께 바뀌게 설계됩니다. 이를 눈사태 효과(Avalanche Effect)라고 합니다. 이 성질이 약하면 비슷한 파일이 비슷한 해시를 내어 패턴이 남게 됩니다.

물론 "출력이 많이 달라 보인다"는 사실만으로 암호학적 안전성이 증명되는 것은 아닙니다. 그래도 좋은 해시가 어떤 모습을 가져야 하는지 감각적으로 이해하는 데는 매우 중요합니다.

엔트로피와 보안 수준

엔트로피(Entropy)는 쉽게 말해 "예측하기 어려운 정도"입니다. 암호학에서 난수는 키, nonce, IV, 서명용 일회성 값 등 여러 곳에 들어가므로, 엔트로피가 부족하면 수학적으로 좋은 체계도 실제로는 쉽게 깨질 수 있습니다.

보안 비트란 무엇입니까

"128비트 보안"이라는 말은, 가장 좋은 알려진 공격을 써도 대략 $2^{128}$ 규모의 작업이 필요하다는 뜻으로 이해합니다. 여기서 중요한 점은 키 길이 자체와 실제 공격 복잡도가 항상 같지 않다는 것입니다. 해시는 생일 경계 때문에 출력 길이의 절반 정도가 충돌 보안 수준이 되고, RSA나 ECC는 각각 다른 수학적 난제에 따라 보안 수준을 해석합니다.

난수의 품질

컴퓨터는 본질적으로 결정적인 기계이므로, 진짜 무작위와 비슷한 값을 만들려면 충분한 초기 엔트로피와 안전한 난수 생성기가 필요합니다. 특히 서명에서 nonce를 재사용하거나 편향된 난수를 쓰면 비밀키가 새어 나갈 수 있습니다.

최소 엔트로피를 함께 봐야 합니다

암호학에서는 평균적인 불확실성보다 "가장 맞히기 쉬운 값이 얼마나 자주 나오는가"가 더 중요할 때가 많습니다. 이를 최소 엔트로피(Min-Entropy)라고 하며

로 정의합니다. 어떤 값이 절반 확률로 나온다면 최소 엔트로피는 1비트뿐입니다. 겉보기 경우의 수가 많아 보여도, 몇몇 값이 지나치게 자주 나오면 실제 보안은 크게 떨어집니다.

검색 공간의 크기를 감각적으로 비교해 봅시다

암호학에서 "충분히 크다"는 말은 막연한 표현이 아닙니다. 가능한 후보의 개수가 얼마나 되는지, 공격자가 그 공간을 얼마나 빨리 뒤질 수 있는지를 같이 봐야 합니다. 다음 비교는 사람이 기억하기 좋은 비밀번호와 암호키가 왜 다른지 잘 보여 줍니다.

즉, 암호학은 단순히 "길어 보이는 문자열"을 쓰는 문제가 아니라, 공격 가능한 후보 공간 자체를 천문학적으로 키우는 문제입니다.

격자와 양자내성 암호

RSA와 ECC는 각각 소인수분해와 이산로그에 기대고 있습니다. 그런데 충분히 큰 양자 컴퓨터가 등장한다면, 쇼어 알고리즘이 이 두 문제를 효율적으로 풀 수 있습니다. 그래서 현대 암호학은 양자내성(Post-Quantum) 구조를 찾고 있으며, 그중 가장 중요한 후보가 격자 기반 암호(Lattice-based Cryptography)입니다.

격자의 기본 직관

격자(Lattice)는 몇 개의 기저 벡터를 정수 계수로 조합해 얻는 점들의 집합입니다. 2차원에서는 바둑판이나 기울어진 그리드처럼 보입니다. 여기서 짧은 벡터를 찾거나, 어떤 점에 가장 가까운 격자점을 찾는 문제는 매우 어렵습니다.

LWE 아이디어

학습과 오차 문제(Learning With Errors, LWE)는 선형 방정식에 작은 잡음을 섞어 비밀을 숨깁니다. 전형적인 모양은

입니다. 여기서 $s$는 비밀 벡터, $a_i$는 공개 벡터, $e_i$는 작은 잡음입니다. 잡음이 없으면 단순한 선형대수 문제이지만, 잡음이 조금만 섞여도 비밀을 안정적으로 분리하기가 매우 어려워집니다.

이 문제는 선형대수, 확률, 기하학이 동시에 만나는 지점입니다. 실제 양자내성 공개키 암호는 이 아이디어를 더 정교한 다항식 구조 위로 옮겨 사용합니다.

잡음이 없으면 선형대수, 잡음이 있으면 암호학

예를 들어 잡음이 없다면

처럼 생긴 식들을 여러 개 모아 가우스 소거법으로 $s_1, s_2$를 풀 수 있습니다. 즉, 그냥 선형대수 문제입니다. 그런데 실제 LWE에서는 오른쪽 값에 작은 오차 $e_i$가 조금씩 붙습니다. 그러면 모든 식을 정확히 만족하는 해가 사라지고, 여러 개의 "거의 맞는 후보"가 생깁니다.

암호는 바로 이 애매함을 이용합니다. 잡음은 작아서 정상 사용자는 구조를 유지할 수 있지만, 공격자에게는 정답을 흐려 놓는 안개처럼 작동합니다. 그래서 LWE는 선형대수만으로 곧바로 풀리지 않고, 격자 문제와 연결되는 훨씬 어려운 문제로 바뀝니다.

작은 수로 보는 LWE 예시

법 $11$에서 비밀 벡터 $s=(3,4)$를 숨긴다고 가정하겠습니다. 다음 표에서 왼쪽 벡터 $a_i$와 오른쪽 값 $b_i$는 공개되고, 비밀은 $s$뿐입니다.

잡음이 없는 열만 보면 선형연립방정식이므로 가우스 소거법으로 비밀을 바로 복원할 수 있습니다. 하지만 잡음이 들어간 열은 어떤 $s$도 식을 정확히 동시에 만족하지 못합니다. 공격자는 "가장 그럴듯한 비밀"을 찾아야 하고, 이 문제가 격자와 가까운 어려운 문제로 바뀝니다.

전체 정리

암호학은 하나의 공식으로 끝나는 과목이 아닙니다. 서로 다른 수학적 구조가 서로 다른 보안 목표를 맡고 있습니다. 중요한 것은 "어떤 문제를 어렵다고 믿는가"와 "그 문제 위에 어떤 프로토콜을 세우는가"를 함께 보는 일입니다.

정리하면, 암호학의 수학은 "어려운 문제를 골라 그 위에 보안 규칙을 세우는 기술"입니다. 소수와 나머지 계산에서 시작해, 유한체와 타원곡선, 해시와 엔트로피, 격자와 양자내성 구조까지 이어지는 큰 지도를 머릿속에 넣어 두면 각 알고리즘이 왜 존재하는지 훨씬 선명하게 보입니다.