📚 지식 노트

모듈러 산술과 빠른 거듭제곱

공개키 암호의 계산은 거의 모두 모듈러 산술(나머지 산술)이다. 법(modulus) n을 정하면 수는 0부터 n−1까지만 있고, 넘치면 시계처럼 처음으로 돌아온다. 12시간 시계에서 9시의 5시간 뒤는 (9 + 5) mod 12 = 2시다. 덧셈·뺄셈·곱셈은 계산 중간에 아무 때나 나머지를 취해도 결과가 같아서, 수가 아무리 커져도 n보다 작게 유지할 수 있다. 나눗셈만은 다르다. 'a로 나누기'는 a·x ≡ 1이 되는 역원 x를 곱하는 것이고, 역원은 a와 n이 서로소일 때만 있다(mod 7에서 3의 역원은 5이다).

RSA와 디피–헬먼은 a^e mod n 같은 거듭제곱을 수천 비트 지수로 계산한다. a를 e번 곱하면 우주의 나이로도 모자라지만, 지수를 2진수로 보고 제곱-곱하기를 하면 지수의 비트 수에 비례하는 곱셈만으로 끝난다. 2048비트 지수라면 제곱 2047번과 곱셈 최대 2047번이다.

이 알고리즘은 비트가 1일 때만 곱셈을 한 번 더 하므로, 그대로 구현하면 걸린 시간이나 전력 소모로 비밀 지수의 비트가 새어 나간다(부채널 공격). 실제 라이브러리는 비트와 상관없이 같은 일을 하는 상수 시간 구현(몽고메리 사다리 등)을 쓴다. 암호를 직접 구현하지 말아야 하는 이유 중 하나다.

군, 생성원, 이산 로그

소수 p를 법으로 하면 1부터 p−1까지의 수는 곱셈에 대해 닫혀 있고 모두 역원이 있다. 이렇게 연산 하나와 그 규칙(결합 법칙, 항등원, 역원)을 갖춘 집합을 군이라 하고, 이 경우를 Z_p*라고 쓴다. 원소 g를 거듭 곱해 1로 돌아오기까지의 횟수가 g의 위수이고, 위수가 p−1이라 모든 원소를 한 번씩 지나는 g를 생성원이라 한다. Z₂₃*에서 5는 위수가 22(= p−1)인 생성원이고, 2는 위수가 11뿐이라 절반만 돈다. 위수는 늘 군 크기(p−1 = 22)의 약수다(라그랑주 정리).

g^k ≡ h를 만족하는 k를 찾는 것이 이산 로그 문제다. 위 그림에서 5^k ≡ 8의 답은 k = 6이지만, 이것은 22개를 다 대입해 보고 안 답이다. 알려진 가장 좋은 고전 알고리즘도 큰 p에서는 비현실적으로 느리다. 단, 군의 크기 p−1이 작은 소수들의 곱이면 문제를 쪼개 풀 수 있으므로(폴리그–헬먼) 실제로는 큰 소수 위수의 부분군을 쓴다. 디피–헬먼, DSA, 타원 곡선 암호가 모두 이 '한쪽으로만 쉬운' 성질에 기댄다.

유클리드 호제법과 역원

두 수의 최대공약수(gcd)는 '큰 수를 작은 수로 나눈 나머지'로 바꾸기를 되풀이하면 나온다(유클리드 호제법). 여기에 계수 두 개를 함께 따라가면, gcd(a, b) = s·a + t·b를 만족하는 정수 s, t(베주 계수)도 얻는다. gcd가 1이면 t·b ≡ 1 (mod a)이므로 t가 곧 b의 역원이다. 걸음 수는 작은 수의 자릿수에 비례할 만큼 빨라서 수천 비트 수에도 금방 끝난다.

이 계산은 RSA 키를 만들 때 비밀 지수 d를 구하는 바로 그 단계이고, 타원 곡선에서 점을 더할 때 기울기의 분모를 '나누는' 데도 쓴다. 역원은 페르마의 소정리로 a^p−2 mod p를 계산해 구할 수도 있다. 상수 시간 구현에서는 이쪽을 쓰기도 한다.

RSA: 장난감 수로 따라가기

RSA는 큰 소수 두 개 p, q를 곱한 n을 공개한다. φ(n) = (p−1)(q−1)과 서로소인 e를 고르고, e·d ≡ 1 (mod φ(n))인 d를 비밀로 둔다. 암호화는 c = m^e mod n, 복호화는 m = c^d mod n이다. 오일러 정리 때문에 m^φ(n) ≡ 1 (mod n)이고(예: 65³¹²⁰ mod 3233 = 1), e·d = 1 + k·φ(n)이므로 (m^e)^d = m · (m^φ(n))^k ≡ m이 된다. n을 소인수분해할 수 있으면 φ(n)과 d를 바로 계산할 수 있으므로, RSA의 안전성은 큰 수의 소인수분해가 어렵다는 데 기댄다.

• CRT로 4배 가까이 빠르게: 비밀키를 가진 쪽은 p, q를 알므로 mod n 대신 절반 크기의 mod p, mod q에서 따로 거듭제곱하고 중국인의 나머지 정리로 합친다. 실제 구현은 거의 다 이 방식이다. 대신 둘 중 한쪽 계산이 오류로 틀리면 그 결과로 n이 인수분해될 수 있어, 서명 뒤에 검증을 한 번 더 하는 방어를 둔다.
• 교과서 RSA는 결정적이다: 같은 m은 늘 같은 c가 된다. 후보가 몇 개뿐인 메시지('예'/'아니오')는 공격자가 공개키로 하나씩 암호화해 맞춰 볼 수 있다.
• 교과서 RSA는 곱셈을 보존한다: E(6)·E(7) mod n = 824 × 2369 mod 3233 = 2557이고, 이것을 복호화한 결과는 42 = 6 × 7이다. 평문을 몰라도 암호문을 조작해 관계된 평문을 만들 수 있다는 뜻이다.

그래서 RSA 암호화는 반드시 무작위 패딩과 함께 쓴다. OAEP(RFC 8017)는 메시지에 난수를 섞고 해시 함수 두 번으로 뒤섞어서, 같은 메시지도 매번 다른 암호문이 되고 조작한 암호문은 복호화 때 걸러지게 한다. 옛 PKCS #1 v1.5 패딩은 '패딩이 맞는지'만 알려 줘도 그것을 수십만 번 물어 평문을 되찾는 공격이 있었고(Bleichenbacher 1998), 20년 뒤에도 같은 약점이 주요 제품에서 다시 발견됐다(ROBOT). 오늘날 키 교환에는 RSA 암호화를 거의 쓰지 않고, RSA는 주로 서명(PSS 패딩)에 남아 있다.

타원 곡선: 점을 더하는 군

타원 곡선은 y² = x³ + ax + b를 만족하는 점들이다. 실수 위에서 그리면 매끄러운 곡선이고, 곡선 위의 두 점을 지나는 직선은 곡선과 한 점에서 더 만난다. 그 셋째 점을 x축에 대칭시킨 것을 두 점의 '합'으로 정하면, 무한원점 O를 항등원으로 하는 군이 된다. 같은 점을 두 번 더할 때(두 배)는 접선을 쓴다. 암호에서는 이 규칙을 그대로 mod p 위로 옮겨, 좌표가 0~p−1인 유한한 점들의 군을 쓴다.

• 덧셈: P ≠ Q이면 기울기 λ = (y_Q − y_P) / (x_Q − x_P), 같은 점이면 λ = (3x_P² + a) / 2y_P. 합은 x = λ² − x_P − x_Q, y = λ(x_P − x) − y_P다. 나눗셈은 모두 mod p의 역원 곱하기다.
• 계산해 보기: y² = x³ + 2x + 2 (mod 17)에서 G = (5, 1)이면 2G의 기울기는 13이고 2G = (6, 3), G + 2G의 기울기는 2이고 3G = (10, 6)다.
• 위수: 이 곡선의 점은 O를 포함해 19개이고 G를 19번 더하면 O가 된다. 실제 곡선(P-256, Curve25519)은 점이 약 2²⁵⁶개이고 큰 소수 위수의 기준점을 쓴다.

k·G(G를 k번 더한 점)는 두 배-더하기로 빠르게 구하지만, 점 k·G에서 k를 되찾는 타원 곡선 이산 로그는 어렵다. 유한체의 이산 로그에는 지수 계산법(index calculus) 같은 '약간 빠른' 공격이 있어 큰 법이 필요하지만, 잘 고른 타원 곡선에는 그런 공격이 알려져 있지 않다. 그래서 같은 보안 수준에 훨씬 짧은 키(256비트 대 3072비트)로 충분하다(NIST SP 800-57). 곡선 선택에는 함정이 많아서, 실제로는 Curve25519(RFC 7748)나 NIST P-256처럼 검증된 곡선만 쓴다.

디피–헬먼과 ECDH

디피–헬먼 키 교환은 공개된 g와 p 위에서 앨리스가 g^a, 밥이 g^b를 보내고, 각자 받은 값을 자기 비밀로 한 번 더 거듭제곱해 같은 g^ab에 닿는다. p = 23, g = 5, a = 6, b = 15이면 공개값은 8과 19, 공유 비밀은 2이다. 단계별 흐름은 보안 › 암호 노트의 그림에 있다. 엿보는 쪽은 g^a와 g^b에서 g^ab를 구해야 하는데(계산 디피–헬먼 문제), 이산 로그를 풀 수 있으면 이것도 풀린다.

• 인증이 없으면 중간자에게 진다: 디피–헬먼 자체는 상대가 누구인지 확인하지 않는다. 중간에서 양쪽과 따로 교환하면 그만이다. 그래서 TLS는 교환 값에 서명을 붙이고 인증서로 서명 키를 확인한다.
• 임시 키와 전방 비밀성: 연결마다 새 a, b를 만들고 버리면(ephemeral), 나중에 서버의 장기 키가 새어도 지난 대화를 풀 수 없다. TLS 1.3은 이 방식만 허용한다.
• 받은 값 검증: 상대가 보낸 점이 곡선 위에 있는지, 작은 위수의 부분군에 있지 않은지 확인하지 않으면 비밀 키 조각이 새는 공격이 있다. X25519는 이런 실수가 일어나기 어렵게 설계되었다.

해시 함수의 성질과 생일 한계

암호 해시 함수는 아무 길이의 입력을 고정 길이 출력으로 줄이면서 세 가지를 지켜야 한다. 출력만 보고 입력을 찾을 수 없고(원상 저항), 주어진 입력과 같은 출력을 내는 다른 입력을 찾을 수 없고(제2 원상 저항), 같은 출력을 내는 아무 두 입력도 찾을 수 없어야 한다(충돌 저항). 출력이 n비트면 앞의 둘은 대략 2ⁿ번 시도가 필요하지만, 충돌은 생일 역설 때문에 2^n/2번 근처에서 나온다.

23명만 모여도 생일이 겹칠 확률은 50.7%, 57명이면 99.0%다. 같은 계산을 해시에 하면, 출력의 절반 비트만큼 시도했을 때 충돌 확률이 50%에 닿는다. 64비트 출력은 5.1 × 10^9개, 128비트는 2.2 × 10^19개, 256비트는 4.0 × 10^38개쯤에서다. 64비트 값 수십억 개는 오늘날 컴퓨터로 금방 만들므로 64비트 해시나 블록 크기는 충돌 저항에 쓸 수 없고, SHA-256의 충돌 저항은 128비트 보안으로 센다. MD5와 SHA-1은 이 한계보다도 훨씬 빠르게 충돌을 만드는 공격이 나와 퇴출됐다.

해시의 두 구조: 메르클–담고르와 스펀지

긴 입력을 다루려면 고정 크기를 처리하는 부품을 되풀이해 써야 한다. MD5, SHA-1, SHA-2(FIPS 180-4)는 메르클–담고르 구조로, 압축 함수 f가 '지금까지의 체인 값 + 다음 블록'을 새 체인 값으로 줄이는 일을 반복한다. 압축 함수가 충돌에 강하면 전체도 충돌에 강하다는 증명이 이 구조의 장점이다. SHA-3(FIPS 202)는 스펀지 구조다. 큰 상태를 rate와 capacity로 나눠 rate에만 입력을 섞고 순열 f로 휘저은 뒤, 출력도 rate에서 원하는 만큼 짜낸다(Keccak 팀 설명).

실무에서 중요한 차이는 길이 확장이다. SHA-256(비밀 ‖ 메시지)를 인증 태그로 쓰면, 비밀을 몰라도 해시값에서 이어 계산해 '메시지 ‖ 덧붙인 내용'의 올바른 태그를 만들 수 있다. 그래서 키를 섞은 해시에는 HMAC을 쓴다. SHA-3와 출력 길이를 마음대로 정하는 SHAKE는 이 문제가 없다.

블록 암호의 구조: 페이스텔과 SPN

블록 암호는 키마다 다른 '블록 → 블록' 순열이다. 좋은 블록 암호는 입력의 한 비트만 바꿔도 출력의 절반쯤이 바뀌어야 하고(확산), 키와 출력의 관계가 복잡해야 한다(혼돈). 이것을 간단한 라운드를 여러 번 겹쳐 얻는데, 뼈대는 크게 두 가지다. 페이스텔 구조(DES 등)는 블록을 반으로 나눠 한쪽에 라운드 함수 F의 결과를 XOR하고 자리를 바꾼다. F를 되돌릴 필요가 없어서 F를 마음대로 복잡하게 만들 수 있고, 복호화는 같은 회로에 키 순서만 거꾸로 넣으면 된다.

SPN(치환–순열 네트워크)은 블록 전체를 바이트 치환(S-box)과 섞기 층에 통과시킨다. 각 층이 되돌릴 수 있어야 하는 대신 라운드마다 블록 전체가 섞인다. AES(FIPS 197)가 대표이고, 128비트 블록을 키 길이에 따라 10·12·14 라운드 돌린다. S-box는 GF(2⁸)의 역원 계산에 아핀 변환을 붙여 만들어, 선형·차분 공격에 강하도록 수학적으로 고른 것이다.

블록 암호 하나는 블록 하나만 암호화한다. 긴 메시지를 다루는 운용 모드(ECB를 쓰면 안 되는 이유, CTR, CBC)와, 기밀성과 변조 검사를 함께 주는 AEAD(AES-GCM, ChaCha20-Poly1305)는 보안 › 암호 노트에 그림과 함께 있다. 수학 쪽에서 덧붙일 것은 하나다. CTR·GCM은 블록 암호를 '키로 만든 의사 난수 함수'로만 쓰므로, 같은 키에서 논스(nonce)가 한 번이라도 겹치면 두 평문의 XOR이 드러나고 GCM은 인증 키까지 샌다.

난수: 암호의 숨은 재료

키, 논스, 패딩, 서명의 임시값은 모두 예측할 수 없는 난수여야 한다. 운영체제는 하드웨어 노이즈 같은 엔트로피를 모아 암호용 난수 생성기(CSPRNG)의 씨앗으로 쓰고, 프로그램은 이것을 getrandom(), /dev/urandom, 브라우저의 crypto.getRandomValues()로 받는다. 결정론적 생성기의 설계 기준은 NIST SP 800-90A에 있다. 일반 Math.random()은 출력 몇 개로 다음 값을 예측할 수 있어 암호에 쓰면 안 된다.

좋은 난수를 받아도 쓰는 법에서 새는 경우가 많다. 흔한 실수가 범위를 줄이는 나머지 연산이다. 0~255 바이트를 % 100으로 줄이면 0~55은 3번, 56~99는 2번씩 나와 앞쪽이 1.5배 잦다.

서명에서는 치우침이 더 치명적이다. (EC)DSA 서명마다 쓰는 임시값 k가 한 번 되풀이되면 두 서명에서 비밀 키를 바로 계산할 수 있고, k의 몇 비트만 치우쳐도 서명이 많이 모이면 격자 알고리즘으로 키가 복원된다. 그래서 요즘 구현은 k를 메시지와 비밀 키에서 결정적으로 만들거나(RFC 6979), 처음부터 그렇게 설계된 EdDSA를 쓴다.

양자 컴퓨터와 양자내성 암호

쇼어 알고리즘은 군에서 주기를 찾는 문제를 양자 푸리에 변환으로 효율적으로 풀어, 소인수분해와 (타원 곡선) 이산 로그를 다항 시간에 끝낸다. 충분히 큰 오류 정정 양자 컴퓨터가 생기면 RSA, 디피–헬먼, ECDH, ECDSA가 한꺼번에 무너진다는 뜻이다. 그런 기계는 아직 없지만, 필요한 큐비트 추정은 계속 줄고 있다(Gidney 2025는 노이즈 있는 큐비트 100만 개 미만으로 RSA-2048을 일주일 안에 인수분해하는 설계를 냈다). 지금 엿들어 저장해 둔 암호문을 나중에 푸는 '지금 수집, 나중 해독'도 걱정거리라, 키 교환부터 바꾸는 중이다. 대칭키와 해시는 그로버 알고리즘이 탐색을 제곱근으로 줄이는 정도라 영향이 작다. 그로버는 병렬화가 잘 안 되어 실제 부담은 더 작고, 여유를 원하면 AES-256을 쓴다.

NIST는 2016년부터 공개 공모를 거쳐 2024년 8월 13일 첫 양자내성 표준 셋을 발표했다(NIST 발표). 키 캡슐화 ML-KEM(FIPS 203, CRYSTALS-Kyber에서 옴), 서명 ML-DSA(FIPS 204, CRYSTALS-Dilithium), 해시 기반 서명 SLH-DSA(FIPS 205, SPHINCS+)다. 격자와 다른 수학(부호 이론)에 기댄 예비 키 캡슐화로 HQC가 2025년 3월 선정됐고, Falcon 기반 서명(FN-DSA)과 HQC의 표준화가 진행 중이다(NIST PQC 프로젝트, 2026년 10월 기준). 전환 일정 초안(NIST IR 8547)은 지금의 공개키 알고리즘을 2030년 이후 폐기 예정, 2035년 이후 금지로 제안했다.

ML-KEM과 ML-DSA가 기대는 격자 문제의 직관은 이렇다. 격자는 기저 벡터의 정수 조합으로 생기는 점들이다. 같은 격자를 짧고 거의 직교하는 '좋은 기저'로도, 길고 비스듬한 '나쁜 기저'로도 나타낼 수 있다. 좋은 기저를 알면 아무 점에서 가장 가까운 격자점을 쉽게 찾지만, 나쁜 기저만으로는 차원이 수백일 때 사실상 불가능하다. 비밀 키는 좋은 기저나 짧은 벡터 쪽, 공개 키는 그것을 감춘 나쁜 쪽에 해당한다.

실제 구성은 Regev(2005)의 LWE(learning with errors)를 쓴다. 비밀 벡터 s에 대해 무작위 행렬 A와 b = A·s + e (mod q)를 공개하는데, e는 작은 노이즈다. 노이즈가 없으면 가우스 소거로 s가 바로 나오지만, 노이즈가 섞이면 이것은 격자의 가까운 점 찾기 문제가 된다. ML-KEM은 이것을 다항식 환 위의 작은 행렬로 바꾼 모듈 LWE라 키와 암호문이 수 KB 수준으로 작다. 전환기에는 기존 X25519와 ML-KEM-768을 함께 써서 둘 중 하나만 버텨도 안전한 하이브리드 키 교환이 TLS에 표준으로 정리됐다(RFC 10024).

핵심 문헌

요지는 직접 정리한 한 줄이다. 실무 쪽 정리는 보안 › 암호 노트에, 메모리 안전과 코드 서명은 보안 › 시스템 노트에 있다.