시저 암호의 알파벳 이동에서 타원곡선 위 점들의 덧셈까지, 약 2000년에 걸친 비밀 통신 기술의 흐름을 한 편의 글로 정리한다.
암호의 핵심은 "키를 모르는 사람이 메시지의 어떤 정보도 얻을 수 없게 만드는 것"이다. 이 글은 그 목표가 어떻게 진화해 왔는지를 다룬다. 기원전 50년의 시저 암호에서 시작해, 알파벳 빈도 분석으로 깨지는 단일치환 암호, 그것을 보완한 다중치환의 비즈네르(Vigenère) 암호, 1차 세계대전기의 일회용 패드(One-Time Pad), 2차 세계대전을 뒤흔든 에니그마(Enigma)와 그 해독, 1970년대 표준이 된 DES, 그것을 대체한 AES, 그리고 공개키 시대를 연 RSA와 효율의 정점에 있는 타원곡선 암호(ECC)까지 — 각 단계가 어떤 문제를 풀려고 등장했고, 어떤 새로운 문제를 남겼는지를 차례로 살핀다.
암호의 무대에는 항상 세 인물이 등장한다. 메시지를 보내려는 송신자, 메시지를 받으려는 수신자, 그리고 그 통신을 엿보거나 변조하려는 공격자다. 학계 관행에 따라 이들을 각각 앨리스(Alice), 밥(Bob), 이브(Eve)로 부른다. 이브의 이름은 영어 'eavesdropper(도청자)'에서 따왔다.
앨리스가 밥에게 보내려는 원래 메시지를 평문(plaintext)이라 한다. 평문은 누구나 읽을 수 있는 일반 문장이라서, 통신 회선 위에 그대로 흘리면 이브가 곧바로 내용을 알게 된다. 그래서 앨리스는 평문을 어떤 규칙에 따라 알아볼 수 없는 형태로 바꾼다. 이 변환된 결과가 암호문(ciphertext)이고, 변환 규칙에 사용되는 비밀값이 키(key)다. 밥은 자신이 가진 키로 암호문을 다시 원래 평문으로 되돌리는데 이 과정이 복호화(decryption)다.
암호는 디지털 세계의 자물쇠와 같다. 메시지를 상자에 넣고 자물쇠를 채우는 것이 암호화, 그 상자를 받아서 열쇠로 푸는 것이 복호화다. 이브는 상자를 가로채더라도 열쇠가 없으면 안을 볼 수 없다. 모든 암호 시스템의 목표는 결국 "열쇠 없이는 절대 열리지 않는 자물쇠"를 수학적으로 만드는 것이다.
현대 암호학이 풀고자 하는 문제는 단순한 "내용을 못 보게 만들기"가 아니다. 그것은 출발점일 뿐이다. 진짜 어려운 문제는 "키가 없는 사람이 암호문을 아무리 들여다보아도 평문에 관한 어떤 정보도 얻을 수 없음을 수학적으로 보장하는 것"이다. 이 조건이 만족되어야 비로소 안전한 암호 시스템이라고 말할 수 있다.
암호의 역사는 크게 고전·근대·현대로 나눌 수 있다. 각 시기를 결정지은 사건만 골라서 본다.
최초로 기록된 암호는 시저 암호(Caesar cipher, 기원전 50년경)다. 고대 로마의 카이사르가 사용했다고 전해지며, 알파벳을 일정한 칸수만큼 뒤로 밀어 표기하는 단순한 방식이다. 1558년에는 처음으로 "암호 알고리즘과 키를 분리해서 생각하자"는 개념이 등장했고, 1583년 비즈네르(Vigenère)가 시저 암호를 다중치환으로 확장한 비즈네르 암호를 제안했다.
1917년 번엠(Vernam)이 일회용 패드(One-Time Pad, OTP)를 고안했다. 메시지와 같은 길이의 무작위 키를 한 번만 쓰고 버리는 방식으로, 1940년대에 샤논(Shannon)이 수학적으로 가장 안전한 암호임을 증명한다. 1918년에는 셰르비우스(Scherbius)의 에니그마(Enigma)가 등장했다. 알고리즘 자체에 새로운 원리가 있었다기보다, 다중치환을 기계로 자동화한 것이 핵심 의의였다. 2차 세계대전에서 독일군의 주요 통신에 사용되었고, 영국 블레츨리 파크(Bletchley Park)에서 앨런 튜링(Alan Turing)이 이끄는 팀이 해독에 성공한다. 이 과정에서 최초의 컴퓨터로 평가받는 콜로서스(Colossus, 1943)가 만들어졌다. 컴퓨터가 처음 만들어진 동기가 바로 암호 해독이었다는 사실은 기억해 둘 만하다.
1970년대에 들어서면서 인터넷의 전신이 사용되기 시작했고, 표준화된 암호 알고리즘의 필요성이 절실해진다. 1977년 미국 NBS(현재 NIST, National Institute of Standards and Technology, 국립표준기술연구소)는 IBM이 설계하고 NSA(National Security Agency, 국가안보국)가 검토한 DES(Data Encryption Standard, 데이터 암호화 표준)를 채택했다.
1976년에는 디피(Diffie)와 헬만(Hellman)이 공개키 암호(public-key cryptography) 개념을 처음 제안했다. 그 전까지는 송신자와 수신자가 동일한 키를 미리 공유해야만 통신이 가능했지만, 공개키 방식은 암호화 키와 복호화 키를 분리해서 한쪽은 공개해도 안전성이 유지되는 구조를 갖는다. 2년 뒤 1978년 리베스트(Rivest), 샤미르(Shamir), 애들먼(Adleman) 세 사람이 RSA 암호를 발표했다. 이름은 세 사람 성의 머리글자에서 따왔다. 사실 영국 정보기관 GCHQ의 수학자 엘리스(Ellis)가 1973년에 비슷한 방식을 먼저 고안했으나 기밀로 묶여 1997년에야 공개됐다.
1985년에는 코블리츠(Koblitz)와 밀러(Miller)가 독립적으로 타원곡선 암호(Elliptic Curve Cryptography, ECC)를 제안했다. 같은 안전성을 훨씬 짧은 키로 달성할 수 있어, 자원이 부족한 모바일·임베디드 환경에서 RSA를 대체해 나가고 있다.
이후의 주요 사건은 다음과 같다. 1997~2001년 NIST가 공모를 통해 DES의 후계자로 벨기에 암호학자 데먼(Daemen)과 레이먼(Rijmen)의 레인달(Rijndael)을 선정했고, 이것이 오늘날의 AES(Advanced Encryption Standard, 고급 암호화 표준)다. 2009년에는 젠트리(Gentry)가 박사 학위 논문에서 완전동형암호(Fully Homomorphic Encryption, FHE)를 처음으로 실현했다. 암호화된 데이터를 복호화하지 않고도 그 위에서 덧셈과 곱셈을 자유롭게 수행할 수 있는 암호로, 1970년대부터 40년 가까이 풀리지 않던 숙제였다. 2016년부터는 양자컴퓨터의 등장에 대비한 양자내성암호(Post-Quantum Cryptography, PQC) 표준화 작업이 진행 중이다.
알파벳을 숫자로 매핑해 두면 연산하기가 편하다. A를 0, B를 1, ..., Z를 25로 대응시키면 알파벳 26개는 0~25의 정수 공간에서 살게 된다. 어떤 연산을 하든 결과가 다시 0~25의 범위로 돌아오게 만드는 것이 바로 모듈로 26 연산(mod 26)이다. 예컨대 X(=23)에 3을 더하면 26이 되는데, 26을 26으로 나눈 나머지는 0이므로 결과는 A다. 즉 알파벳을 한 바퀴 돌려서 처음으로 보낸 셈이다.
시저 암호는 평문의 각 문자를 일정 칸수(키)만큼 뒤로 옮긴다. 키가 3이면 A→D, B→E, ..., X→A, Y→B, Z→C가 된다. 평문 "HELLO"를 키 3으로 암호화하면 K, H, O, O, R이 나온다. 복호화는 같은 칸수만큼 거꾸로 옮기면 끝이다.
이 암호의 약점은 명백하다. 키는 0~25 중 하나, 총 26가지뿐이다. 0~25를 모두 시도해 보면(전수 조사, brute-force attack) 의미 있는 문장이 나오는 키 하나가 진짜 키다. 손으로도 수십 분, 컴퓨터로는 1초도 안 걸린다.
시저 암호를 일반화해서 알파벳 26개의 모든 1대1 대응을 키로 삼는 방식을 단일치환 암호(monoalphabetic substitution cipher)라 한다. 가능한 키는 26! ≈ 288개로, 약 13자리 비밀번호와 비슷한 규모다. 전수 조사로는 평생 풀 수 없다. 그럼에도 단일치환 암호는 안전하지 않다.
이유는 단일치환이 결정적(deterministic)이라는 점에 있다. 평문의 E가 항상 같은 암호 문자(예: H)로 매핑되므로, 평문에서 E가 100번 등장하면 암호문에서도 그 특정 문자가 정확히 100번 등장한다. 영어에서 E는 가장 흔한 글자고 Q, J는 가장 드물다. 충분히 긴 암호문이 있다면 빈도 분석(frequency analysis)으로 거의 모든 글자의 대응을 복구할 수 있다. 단어 단위로 보면 "THE", "AND" 같은 빈출 패턴이 단서를 더 준다.
단일치환 암호의 글자는 외출할 때마다 같은 가면을 쓰는 사람과 같다. 가면을 써도 키가 같고, 걸음걸이가 같고, 가는 곳이 같으면 누구인지 금방 들통난다. 빈도 분석은 그 "걸음걸이"를 읽는 기술이다.
빈도 분석을 막으려면 같은 평문 글자가 위치에 따라 다른 암호 문자로 바뀌어야 한다. 이런 방식을 다중치환 암호(polyalphabetic substitution cipher)라 하고, 비즈네르 암호가 대표적이다.
비즈네르 암호는 평문을 일정 크기 m의 블록으로 나누고, 블록 안의 i번째 문자를 키 (k1, k2, ..., km)의 i번째 값만큼 시프트한다. 예를 들어 m=4이고 키가 (21, 4, 2, 19)면, "VISE"를 암호화할 때 V는 21칸, I는 4칸, S는 2칸, E는 19칸씩 이동한다. 그 결과 V→Q, I→M, S→U, E→X로 변환되어 "QMUX"가 된다. 이어지는 "NERA"는 같은 키 (21, 4, 2, 19)로 다시 시프트하여 "IITX"가 된다.
중요한 점은 평문 두 위치의 E가 서로 다른 키 성분에 의해 시프트되므로 다른 암호 문자로 바뀐다는 것이다. 위 예에서 "VISE"의 E와 "NERA"의 E가 그렇다. 단순 빈도 분석으로는 이 구조를 깰 수 없다. 다만 키 길이 m을 추측해 m개의 독립적인 시저 암호로 분해할 수 있다면 빈도 분석이 다시 작동한다. 이걸 방지하려면 키 길이가 평문 길이와 같아야 하는데, 그 극단이 바로 일회용 패드다.
에니그마는 회전자(rotor), 램프 보드, 키보드, 플러그 보드 등 여러 부품을 조합해 키를 누를 때마다 치환 규칙이 바뀌도록 만든 전기 기계식 암호 장비다. 알고리즘적으로는 단일치환과 다중치환의 혼합이지만, 이를 기계로 자동화함으로써 군사 통신에서 실용적으로 사용할 수 있게 한 것이 의의다. 1930년대 폴란드 암호국 수학자 세 사람이 초기 버전을 해독했고, 폴란드 침공 두 달 전 영국에 정보가 전달된다. 이후 블레츨리 파크의 튜링이 이끄는 팀이 본격적으로 해독에 성공하면서 2차 세계대전의 결정적 정보전 우위를 확보한다. 이 해독 사실은 1970년대까지 기밀로 묶여 있었다.
현대 암호학은 암호 시스템을 세 개의 알고리즘으로 정의한다.
대칭키 암호는 한 쌍의 똑같은 열쇠를 미리 나눠 가진 두 사람의 상황이다. 통신을 시작하기 전에 어떻게든 직접 만나서 열쇠를 건네야 한다. 공개키 암호는 다르다. 우편함에 누구나 편지를 넣을 수 있는 투입구가 있지만, 안에서 꺼낼 수 있는 열쇠는 주인만 갖는다. 투입구(공개키)를 아무리 공개해도 안전성이 유지된다.
인터넷 시대에는 수많은 컴퓨터가 일면식 없는 다른 컴퓨터와 통신한다. 모든 쌍에 별도의 알고리즘을 두는 것은 불가능하므로 알고리즘은 표준화될 수밖에 없고, 결국 모든 사람이 알 수 있게 된다. 그래서 현대 암호학은 "알고리즘은 누구나 안다고 가정하되, 키만 안전하게 지키면 안전성이 유지되어야 한다"는 원칙을 따른다. 이 원칙을 케르크호프스 원리(Kerckhoffs's principle)라 부른다. 한 줄로 요약하면 "암호의 안전성은 키의 안전성이다."
안전성을 따지려면 공격자가 무엇을 할 수 있는지를 먼저 정의해야 한다. 공격자가 가질 수 있는 정보와 능력에 따라 네 가지 모델이 있고, 뒤로 갈수록 공격자의 힘이 커진다.
| 약어 | 이름 | 공격자의 능력 |
|---|---|---|
| COA | 암호문 단독 공격 (Ciphertext-Only Attack) | 암호문만 가지고 있음. 평문이나 키를 알아내려 시도. |
| KPA | 기지평문 공격 (Known-Plaintext Attack) | 몇 개의 (평문, 암호문) 쌍을 알고 있음. 예: 이메일 첫 줄이 "Hello"임을 알고 있는 상황. |
| CPA | 선택평문 공격 (Chosen-Plaintext Attack) | 공격자가 임의의 평문을 골라 그에 대한 암호문을 얻을 수 있음. 즉 암호화 기계에 접근 가능. |
| CCA | 선택암호문 공격 (Chosen-Ciphertext Attack) | CPA에 더해, 공격자가 임의의 암호문을 골라 그에 대응되는 평문을 얻을 수 있음. 즉 복호화 기계에도 접근 가능. |
현대 암호학은 COA나 KPA 안전성을 안전하다고 보지 않는다. CPA는 기본이고, 상용 시스템은 CCA 안전성까지 요구한다. 모든 표준 암호 시스템은 적어도 CCA에 대해 안전하게 설계된다.
공개키 암호는 본질적으로 CPA가 항상 가능하다. 공개키가 누구에게나 공개되어 있으므로 공격자도 자신이 원하는 평문에 대한 암호문을 자유롭게 생성할 수 있기 때문이다. 그래서 공개키 암호 설계에서는 처음부터 CPA를 전제로 두고, 그 위에서 CCA 안전성까지 확보하려고 한다.
"안전한 암호란 무엇인가"라는 질문에 1940년대 클로드 샤논(Claude Shannon)이 수학적 답을 제시했다. 그가 정의한 완전 안전성(perfect secrecy)은 다음과 같다.
풀어 말하면, 어떤 암호문 C를 손에 넣은 공격자가 "이게 메시지 M에서 왔을 확률은 얼마인가?"라고 물었을 때, 모든 가능한 메시지 M에 대해 그 확률이 똑같아야 한다는 뜻이다. 공격자는 C가 어떤 평문에서 왔는지 전혀 추측할 수 없다. 직관적으로 표현하면 "암호문을 봤을 때 얻는 정보량과, 안 봤을 때 얻는 정보량이 같다"고 할 수 있다.
완전 안전성을 만족하는 대표적 예가 일회용 패드(One-Time Pad, OTP)다. 1917년 번엠이 고안했고, 1940년대에 샤논이 완전 안전성을 증명했다. 알고리즘은 충격적으로 단순하다.
여기서 ⊕는 XOR(exclusive OR, 배타적 논리합) 연산이다. 비트 단위로 보면 같은 비트는 0, 다른 비트는 1로 결과가 나오는 연산이고, 곧 "모듈로 2 덧셈"과 같다. 같은 값을 두 번 XOR하면 자기 자신으로 돌아오는 성질(A ⊕ K ⊕ K = A)이 있어서, 암호화와 복호화가 정확히 같은 연산이 된다.
일회용 패드의 핵심 조건은 두 가지다. 첫째, 키 K가 평문 M과 같은 길이여야 한다. 둘째, 키는 완전히 무작위로 생성되고 한 번만 사용되어야 한다. 1TB짜리 파일을 암호화하려면 1TB짜리 무작위 키가 필요하다는 뜻이다.
왜 이것이 완전 안전성을 가질까? 직관적으로 보면, 같은 암호문 C가 모든 가능한 평문에서 동일한 확률로 만들어질 수 있기 때문이다. 예를 들어 5글자 암호문을 봤다고 하자. 어떤 키 K에 대해서는 그것이 "APPLE"의 암호문일 수 있고, 다른 키에 대해서는 "SEOUL"의 암호문일 수도 있다. 공격자에게는 둘을 구별할 어떤 단서도 없다.
샤논의 정리에 따르면, 어떤 암호 시스템이 완전 안전성을 가지려면 키 공간의 크기가 메시지 공간의 크기 이상이어야 한다. 즉 |K| ≥ |M|이다. 일회용 패드는 |K| = |M|으로 최적이지만, 이 조건 자체가 현실에서는 거의 사용 불가능하다는 뜻을 갖는다. 1TB 파일을 보내려면 1TB 키를 미리 안전하게 공유해야 한다는 비효율 때문이다. AES가 1TB짜리 파일을 단 128~256비트 키로 암호화하는 것과 비교하면 차이가 명백하다.
여기서 현대 암호학의 실용적 방향이 결정된다. 완전 안전성은 포기하되, 현실적으로 충분히 안전한 것을 추구한다.
완전 안전성은 공격자가 무제한의 계산 능력을 가졌다고 가정한다. 신과 같은 공격자다. 현실의 공격자는 그렇지 않다. 세상의 모든 컴퓨터를 동원하더라도 연산량에는 한계가 있다. 이 점에 주목해서 1980년대 이후 도입된 개념이 의미론적 안전성(semantic security)이다.
의미론적 안전성은 다음과 같은 게임으로 정의한다.
만약 공격자가 2분의 1과 거의 다를 바 없는 확률로만 맞춘다면, 암호문 C는 M0에서 왔는지 M1에서 왔는지 구분할 수 있는 정보를 거의 주지 않는다고 본다. 즉 의미 있는 정보가 새지 않는다. 모든 다항 시간 공격자에 대해 이 성질이 성립하면 그 암호 시스템은 의미론적으로 안전하다고 한다.
의미론적 안전성은 "공격자가 암호문을 봐도 단순히 동전을 던지는 것보다 나을 게 없게 만들자"는 발상이다. 완전 안전성은 0%의 정보 누설을 요구하지만, 의미론적 안전성은 "공격자의 능력 안에서 의미 있는 차이가 없으면 된다"고 본다. 이론적 극한 대신 실용적 충분조건을 채택한 셈이다.
여기서 한 가지 중요한 함의가 나온다. 결정적(deterministic) 공개키 암호는 절대 의미론적 안전성을 만족할 수 없다. 공격자가 자신의 공개키로 M0과 M1을 모두 직접 암호화해서 C와 비교하면 어느 쪽인지 확정할 수 있기 때문이다. 그래서 모든 안전한 공개키 암호는 확률적(probabilistic)이어야 한다. 같은 평문을 같은 키로 암호화해도 매번 다른 암호문이 나와야 한다. 이를 위해 무작위성(랜덤 패딩 등)을 메시지에 첨가하는 기법이 사용된다. RSA의 OAEP(Optimal Asymmetric Encryption Padding, 최적 비대칭 암호화 패딩)가 대표적이다.
공개키 암호는 수학적 구조 위에서 정의된다. 그 출발점이 정수론의 모듈러 연산이다.
정수 a를 자연수 n으로 나눈 나머지를 a mod n이라고 쓴다. 그리고 "a와 b가 mod n으로 같다"는 표현은 a − b가 n의 배수임을 의미한다(=>합동, congruent). 표기로는 a ≡ b (mod n)이지만, 이 글에서는 편의상 a = b (mod n)으로 쓴다.
모듈러 연산의 핵심 성질은 정수의 덧셈·뺄셈·곱셈 모든 규칙이 그대로 통한다는 것이다. 교환법칙, 결합법칙, 분배법칙이 모두 성립한다. 다만 컴퓨터에서 다룰 때는 큰 수를 곧장 계산한 뒤 mod n을 취하기보다, 중간 결과마다 mod n을 적용해 숫자 크기를 작게 유지하는 편이 효율적이다.
0부터 n−1까지의 정수 집합을 Zn이라 한다. 이 집합 위에서 mod n 덧셈과 곱셈이 정의된다. 덧셈에 대한 항등원은 0이고, 곱셈에 대한 항등원은 1이다. 덧셈의 역원은 −a (= n−a)로 항상 존재하지만, 곱셈의 역원은 항상 존재하지 않는다.
예를 들어 Z9에서 2의 곱셈 역원을 찾아보자. 2 × 5 = 10 ≡ 1 (mod 9)이므로 2의 역원은 5다. 반면 3의 곱셈 역원은 존재하지 않는다. 3 × x ≡ 1 (mod 9)을 만족하는 x를 아무리 찾아도 없는데, 그 이유는 3과 9가 공통 약수 3을 갖기 때문이다.
일반화하면 a의 mod n에 대한 곱셈 역원이 존재할 필요충분조건은 gcd(a, n) = 1, 즉 a와 n이 서로소인 것이다. Zn의 원소 중 곱셈 역원을 갖는 것만 모아 놓은 집합을 Zn*이라 한다. 즉 Zn* = {a ∈ Zn : gcd(a, n) = 1}이다.
gcd(a, n) = 1이면, 정수 s와 t가 존재하여 as + nt = 1을 만족한다. 이 식의 양변에 mod n을 취하면 as ≡ 1 (mod n)이 되어, s가 바로 a의 곱셈 역원이다. s와 t를 효율적으로 찾는 방법이 확장 유클리드 알고리즘(Extended Euclidean Algorithm)이다. 일반 유클리드 호제법으로 gcd를 구하면서, 나누기 단계마다 1차 결합의 계수를 추적해 나간다. 입력 크기에 대해 로그 시간이 걸려서, 수천 비트 수에 대해서도 빠르게 작동한다.
Zn*의 원소 개수를 오일러 파이 함수(Euler totient function) φ(n)이라 한다. φ(n)은 n 이하의 자연수 중 n과 서로소인 것의 개수다.
여기서 두 가지 중요한 정리가 나온다.
페르마의 작은 정리(Fermat's Little Theorem): 소수 p와 a (단 p ∤ a)에 대해 ap−1 ≡ 1 (mod p).
오일러 정리(Euler's Theorem): gcd(a, n) = 1일 때 aφ(n) ≡ 1 (mod n).
이 두 정리는 RSA 암호의 정확성을 증명하는 핵심 도구다. "메시지 M에 e승을 한 뒤 다시 d승을 하면 원래 M으로 돌아온다"는 RSA의 마법은 사실 오일러 정리의 직접적 귀결이다.
공개키 암호와 타원곡선 암호를 이해하려면 대수 구조라는 개념이 필요하다. 수학에서 사용하는 기본적인 대수 구조는 세 가지다.
공집합이 아닌 집합 G와 그 위에서 정의된 하나의 연산이 다음 세 조건을 만족하면 G를 군(group)이라 한다.
여기에 교환법칙(a × b = b × a)까지 성립하면 아벨군(abelian group) 또는 가환군이라 한다. 모든 원소가 하나의 원소 g의 거듭제곱(g, g2, g3, ...)으로 표현되면 순환군(cyclic group)이라 하고, g를 생성원(generator)이라 한다.
중요한 정리 하나. p가 소수일 때 Zp*는 항상 순환군이다. 즉 어떤 g가 존재해서 Zp*의 모든 원소를 g의 거듭제곱으로 쓸 수 있다. 이 성질은 다음에 다룰 이산대수 문제와 엘가말(ElGamal) 암호 시스템의 기반이 된다.
군 G의 원소 개수를 G의 위수(order)라 하고 |G|로 쓴다. 한 원소 g에 대해서도 위수를 정의한다. gn = e가 되는 가장 작은 자연수 n을 g의 위수라 한다. 곱셈을 거듭하다 보면 언젠가 항등원으로 돌아오는데, 그때까지의 횟수다.
라그랑주 정리(Lagrange's Theorem)는 부분군 H의 위수가 항상 원래 군 G의 위수의 약수가 됨을 말한다. 이 정리는 타원곡선 암호에서 순환 부분군을 선택할 때 위수의 크기를 보장하는 데 사용된다.
집합 R 위에 두 개의 연산 — 덧셈과 곱셈 — 이 정의되어 있고, 덧셈에 대해 아벨군을 이루며, 곱셈에 대해 결합법칙과 분배법칙이 성립하면 R을 환(ring)이라 한다. Zn은 환의 대표적 예다. 행렬 집합도 환을 이룬다.
환에서 한 걸음 더 나아가, 0이 아닌 모든 원소가 곱셈 역원을 가질 때 그 환을 체(field)라 한다. 사칙연산이 자유롭게 이뤄지는 구조다. 실수, 유리수, 그리고 Zp (p는 소수)가 체의 대표적 예다. 원소가 유한 개인 체를 유한체(finite field)라 부른다.
군은 하나의 연산만 잘 작동하는 작업장이고, 환은 두 연산이 모두 작동하지만 곱셈에는 약간의 제약이 있는 작업장이며, 체는 두 연산 모두 빈틈없이 작동해서 더하기·빼기·곱하기·나누기를 자유롭게 쓸 수 있는 완성된 작업장이다. 같은 수의 집합도 어떤 연산을 정의하느냐에 따라 등급이 달라진다.
AES의 S-box와 MixColumn은 GF(28)이라는 8비트 유한체 위에서 정의된다. RSA는 Zn*(n = pq) 위에서, 엘가말은 Zp* 위에서, 타원곡선 암호는 타원곡선 군 위에서 정의된다. 어떤 대수 구조를 고르느냐가 곧 어떤 암호 시스템을 만드느냐를 결정한다.
대칭키 암호는 평문을 일정 크기의 블록 단위로 잘라 각 블록을 같은 키로 암호화한다. 이런 방식을 블록 암호(block cipher)라 한다. 128비트 블록 암호라면 평문을 128비트씩 끊어 처리한다.
이상적 블록 암호는 n비트 입력을 n비트 출력으로 보내는 모든 1대1 대응(순열, permutation) 중 하나를 키로 갖는다. n비트의 순열 개수는 (2n)!이며, n=40일 때 키를 저장하는 데만 4GB가 필요하다. 키 크기가 너무 커서 실용성이 없다.
그래서 실제 블록 암호는 전체 순열 공간의 극히 일부에서 키를 뽑는다. 잘못 뽑으면 약해지고, 잘 뽑으면 안전하면서도 효율적이다. 어떻게 잘 뽑을지를 두 가지 설계 원리가 알려준다.
1945년 샤논은 블록 암호 설계의 두 원리를 제시했다.
혼돈을 담당하는 부품이 S-box(Substitution box, 치환 박스)이고, 확산을 담당하는 부품이 P-box(Permutation box, 순열 박스)다. 이 둘을 결합한 함수를 라운드(round)라 부르고, 라운드를 여러 번 반복한다. 한 라운드만으로는 부족하지만, 잘 설계된 라운드를 충분히 반복하면 충분한 혼돈과 확산이 누적된다.
DES는 페이스텔 네트워크(Feistel network) 구조를 채택했고, AES는 SPN(Substitution-Permutation Network) 구조를 채택했다. 둘 다 라운드 함수를 반복하지만, SPN은 라운드 안의 S-box들이 병렬로 계산될 수 있어 효율성에서 우위가 있다.
DES는 1990년대 후반에 들어 컴퓨터 성능이 발전하면서 깨지기 시작했다. 1999년 DES Challenge III에서는 22시간 15분 만에 키가 복구되어 사실상 폐기 수순을 밟는다. NIST는 1997년 새로운 표준을 공모했고, 2001년 벨기에 암호학자 데먼과 레이먼이 설계한 레인달(Rijndael)이 AES로 선정된다.
AES는 128비트 블록을 처리하는 SPN 블록 암호다. 키 길이는 128, 192, 256비트 중 선택할 수 있고, 라운드 수는 각각 10, 12, 14라운드다. 내부적으로 128비트(16바이트) 상태를 4×4 바이트 행렬로 표현하고, 이 상태를 라운드마다 변환해 나간다.
한 라운드는 네 가지 변환으로 구성된다.
마지막 라운드만은 MixColumns가 빠지고 세 단계로 이뤄진다. 첫 라운드 전에 AddRoundKey가 한 번 미리 적용되고, 그 뒤로 라운드들이 반복된다.
AES의 안전성은 사실상 S-box에 달려 있다. S-box는 GF(28) 위에서 0이 아닌 원소의 곱셈 역원을 계산하는 함수에 기반한다. 매우 강한 비선형성을 갖고 있어, 평문의 작은 변화가 암호문의 어디로 퍼질지 추적하기가 극도로 어렵다. DES와 달리 AES의 S-box 설계 원리는 처음부터 투명하게 공개되었고, 이것이 암호학자들의 신뢰를 얻는 근거가 되었다.
128비트 마스터 키 하나로부터 11개의 128비트 라운드 키를 만들어 내는 과정이 키 확장(key schedule)이다. 0번째 라운드 키는 마스터 키 그 자체고, 이후 라운드 키는 이전 라운드 키에 RotWord(회전), SubWord(S-box 치환), Rcon(라운드 상수) XOR를 적용해 연쇄적으로 생성한다. S-box가 키 확장 과정에도 들어가기 때문에, 두 마스터 키가 비슷해도 라운드 키들은 완전히 달라진다.
대칭키 암호의 가장 큰 약점은 키 교환이다. 송수신자가 동일한 키를 미리 안전한 경로로 공유해야 한다. 인터넷처럼 무수한 컴퓨터가 임의로 통신해야 하는 환경에서는 사실상 불가능하다. 공개키 암호(public-key cryptography)는 이 문제를 푼다. 수신자가 자신의 공개키를 모두에게 공개하고, 송신자는 그 공개키로 암호화한다. 복호화는 수신자만 가진 개인키로만 가능하다.
1978년 발표된 RSA는 가장 널리 알려진 공개키 암호다. RSA가 안전한 이유는 단 하나의 수학적 사실에 기댄다. "두 개의 큰 소수의 곱은 빠르게 계산할 수 있지만, 그 곱을 다시 두 소수로 분해하는 것은 매우 어렵다"는 사실이다.
밥이 자신의 키 쌍을 만드는 과정은 다음과 같다.
밥의 공개키는 (n, e)이고, 개인키는 (p, q, d)다. n과 e만 알려져도 d를 계산하려면 φ(n)이 필요하고, φ(n)을 계산하려면 n을 p와 q로 인수분해해야 한다. 큰 n에 대한 인수분해가 어렵다는 사실이 RSA의 안전성을 떠받친다.
앨리스가 밥에게 메시지 M (0 ≤ M < n)을 보낼 때 밥의 공개키 (n, e)를 써서 다음을 계산한다.
밥은 자신의 개인키 d로 복호화한다.
왜 이것이 작동하는가? M ∈ Zn*인 경우를 보면, Med = M1+kφ(n) = M · (Mφ(n))k = M · 1k = M (mod n)이다. 오일러 정리가 직접 작동하는 셈이다. M이 Zn*에 속하지 않는 경우(M이 p나 q의 배수)에도 중국인의 나머지 정리(Chinese Remainder Theorem, CRT)를 써서 같은 결론에 도달한다.
실제로 RSA를 구현하려면 몇 가지 알고리즘이 더 필요하다.
위에서 설명한 그대로의 RSA를 교과서 RSA(Textbook RSA)라 한다. 작동은 하지만 절대로 상용 시스템에 그대로 써서는 안 된다. 가장 큰 이유는 RSA가 결정적이라는 데 있다. 같은 평문은 같은 키로 암호화하면 항상 같은 암호문을 낸다. 공격자가 평문 M0과 M1을 알고 있으면 각각을 공개키로 직접 암호화해 받은 암호문 C와 비교만 하면 어느 쪽이었는지 즉시 판단할 수 있다. 즉 의미론적 안전성을 절대 만족할 수 없다.
해결책은 메시지에 무작위성을 첨가하는 것이다. 같은 평문이라도 매번 다른 암호문이 나오게 만들면 된다. 이 패딩 방법이 OAEP(Optimal Asymmetric Encryption Padding)다. 1994년 벨라어(Bellare)와 로개웨이(Rogaway)가 제안했고, CCA 안전성이 증명되어 현재 표준으로 쓰인다.
OAEP의 발상은 단순하다. 원래 RSA 메시지 공간 전체를 다 쓰지 않고, 일부 비트를 무작위 값으로 채우는 것이다. n비트 모듈러스라면 메시지 부분에 (n − k0 − k1)비트, 0 패딩에 k1비트, 무작위 비트에 k0비트를 할당한다. 이 영역들을 해시 함수 두 개로 섞은 뒤 RSA로 암호화한다. 무작위 비트 덕분에 같은 메시지를 보내도 매번 다른 암호문이 나오고, 결정적 공격을 막을 수 있다. 실제 라이브러리(예: Python의 PyCryptodome)에서는 PKCS1_OAEP 모듈로 제공된다.
공개키 암호 자체에는 한 가지 빈틈이 있다. 누군가가 "이것이 내 공개키"라고 주장하더라도, 그 주장이 진짜인지 확인할 방법이 시스템 내부에 없다는 점이다. 공격자 C가 중간에서 가로채 자신의 공개키를 앨리스에게는 "밥의 키"로, 밥에게는 "앨리스의 키"로 전달하면, 두 사람은 C를 통해 모든 통신을 주고받게 된다. 이를 중간자 공격(Man-In-The-Middle, MITM)이라 한다.
해결책은 "이 공개키가 정말 이 사람의 것"이라고 보증해 주는 신뢰할 만한 제3자다. 이 역할을 하는 것이 공개키 인증서(public-key certificate)고, 인증서를 발급·관리하는 체계가 공개키 기반 구조(Public Key Infrastructure, PKI)다. 한국의 공인인증서·금융인증서, 웹사이트의 HTTPS 인증서가 모두 PKI의 산물이다.
지금까지 본 군들은 모두 정수 위에서 정의됐다. 모듈러 연산이 그 기반이었다. 1985년에 등장한 타원곡선은 결이 완전히 다른 군을 제공한다. 평면 위 곡선 위의 점들 사이에 덧셈을 정의해 군을 만드는 방식이다.
유한체 F (보통 F = Zp, p는 큰 소수) 위에서 다음의 바이어슈트라스 방정식(Weierstrass equation)을 만족하는 점 (x, y)들의 집합을 생각한다.
여기에 4a3 + 27b2 ≠ 0 (mod p)이라는 조건을 더 둔다. 이 조건은 곡선이 매끄럽게(특이점 없이) 그려지도록 하는 기술적 요구다. 이 점들에 가상의 무한원점(point at infinity) O를 추가한 것이 타원곡선 집합이다.
타원곡선 위 두 점 P, Q의 덧셈은 다음과 같이 정의된다.
일반 정수의 덧셈처럼 좌표끼리 더하는 게 아니다. 두 점을 잇는 직선을 그어 그 직선이 곡선을 한 번 더 만나는 곳을 찾고, 그 점을 위아래로 뒤집은 곳이 덧셈의 결과다. 같은 점 두 개를 더할 때는 잇는 선이 없으니 그 점에서의 접선을 대신 쓴다. 기하학적으로 단순한 규칙인데, 이 규칙이 군의 모든 조건을 만족시킨다는 사실이 놀라운 점이다.
한 점 P = (x, y)의 덧셈 역원은 단순히 −P = (x, −y)다. y좌표에 음의 부호만 붙이면 끝이다. 정수의 마이너스와 똑같다.
이 덧셈에 대해 결합법칙과 교환법칙이 모두 성립한다는 사실이 (복잡하지만) 증명되어 있다. 따라서 타원곡선 위 점들의 집합은 무한원점을 항등원으로 하는 아벨군을 이룬다. 이것이 타원곡선 군이다.
F = Zp 위에서 정의된 타원곡선의 점 개수에 대해 정확한 공식은 없다. 다만 그 범위를 하세의 정리(Hasse's theorem)가 알려준다.
즉 타원곡선의 점 개수는 대략 p에 가깝다. p의 크기를 키우면 곡선의 위수도 그에 비례해 커지므로, 큰 군을 얻으려면 큰 p를 쓰면 된다. 그러나 일반적인 타원곡선은 순환군이 아니다. 그래서 보통은 큰 위수를 갖는 한 점 G를 선택하고, 그 G가 생성하는 순환 부분군을 암호 시스템의 작업장으로 삼는다. 표준 곡선(예: NIST P-256, secp256k1)은 이 G가 미리 정해져 있다.
순환군 G에서 생성원 g가 주어져 있을 때, 임의의 원소 h ∈ G에 대해 gα = h를 만족하는 α를 찾는 문제를 이산대수 문제(Discrete Logarithm Problem, DLP)라 한다. "g를 몇 번 곱해야 h가 나오는가?"라는 단순한 질문이지만, 적절한 군에서는 이 문제가 매우 어렵다.
대표적으로 Zp*(p가 큰 소수)에서의 DLP가 어렵다는 사실이 잘 알려져 있다. 타원곡선 군 위에서도 DLP를 정의할 수 있는데(곱셈 대신 덧셈이므로 αP = Q에서 α를 찾는 문제), 이것이 ECDLP(Elliptic Curve Discrete Logarithm Problem)다.
같은 안전성을 얻기 위해 필요한 키 크기를 비교해 보면 타원곡선의 강점이 드러난다.
| 알고리즘 | 공개키 크기 | 개인키 크기 |
|---|---|---|
| RSA | 약 3072비트 | 약 3072비트 |
| DLP 기반 (Zp*) | 약 3072비트 | 약 256비트 |
| ECDLP 기반 (ECC) | 약 256비트 | 약 256비트 |
모두 128비트 수준의 안전성을 가정한 추정치다. 차이의 원인은 알려진 공격 알고리즘에 있다. Zp*의 DLP에는 그 군 구조에 특화된 지수 계산법(index calculus)이 알려져 있어, 일반적인 군에 적용 가능한 알고리즘보다 훨씬 효율적이다. 그래서 안전성을 유지하려면 p 자체가 매우 커야 한다. 반면 타원곡선 군에는 그런 특화 알고리즘이 없고, 베이비-스텝 자이언트-스텝(baby-step giant-step)이나 폴라드 로(Pollard's rho) 같은 일반 알고리즘만 적용 가능하다. 이들은 약 √p 정도의 시간이 걸리므로 256비트 곡선이면 128비트 수준의 안전성이 충분히 확보된다.
1985년 엘가말(ElGamal)이 제안한 암호 시스템은 DLP 위에 직접 세워진다. 작동을 Zp* 위에서 보자.
공개 파라미터: 큰 소수 p, Zp*의 생성원 g, 그리고 g의 위수 (= p − 1)가 모든 사용자에게 공개되어 있다.
키 생성: 밥은 무작위로 α ∈ {1, ..., p−2}를 골라 개인키로 삼고, h = gα mod p를 공개키로 공개한다.
암호화: 앨리스가 메시지 M (∈ Zp*)을 보내려면 무작위 r을 골라 다음 두 값을 보낸다.
복호화: 밥은 자신의 개인키 α로 다음을 계산한다.
왜 작동하는가? C1α = (gr)α = (gα)r = hr이다. 따라서 C2 · (C1α)−1 = M · hr · (hr)−1 = M으로 깔끔하게 메시지가 복구된다. RSA와 달리 엘가말은 무작위 r 덕분에 처음부터 확률적이다. 같은 메시지도 매번 다른 (C1, C2)로 암호화된다.
엘가말을 타원곡선 군 위에 옮기는 것은 거의 기계적이다. Zp*의 곱셈을 타원곡선의 덧셈으로, "g의 α승"을 "G의 α배 (= αG)"로 바꾸면 된다. 이런 식으로 만들어진 타원곡선 기반 전자서명이 ECDSA(Elliptic Curve Digital Signature Algorithm)이고, 비트코인·이더리움 등 거의 모든 블록체인이 이 알고리즘으로 서명을 검증한다. 한국의 공인인증서·금융인증서도 RSA나 ECDSA로 전자서명을 생성한다.
약 2000년에 걸친 암호의 흐름을 한 편의 글로 압축했다. 정리해 보면 큰 줄기는 셋이다.
첫째, 고전 암호에서 현대 암호로의 이행은 "안전성을 직관에서 수학으로 옮긴 과정"이다. 시저 암호는 "복잡해 보이니까 안전하겠지"였고, 일회용 패드부터는 "이런 조건이 정확히 만족되니까 안전하다"가 되었다. 의미론적 안전성에 이르러서는 "현실적 공격자가 동전 던지기보다 나을 게 없음을 보장한다"는 정밀한 정의에 도달했다.
둘째, 대칭키와 공개키는 서로의 약점을 보완한다. 대칭키 암호는 빠르지만 키 분배가 어렵고, 공개키 암호는 키 분배 문제는 풀지만 연산이 무겁다. 그래서 실제 시스템은 둘을 결합한 하이브리드 암호(hybrid encryption)를 사용한다. 공개키로 대칭키를 안전하게 교환하고, 그 대칭키로 본격적인 데이터를 암호화한다. HTTPS, TLS, S/MIME, PGP 등이 모두 이런 구조다.
셋째, 수학적 구조의 선택이 곧 암호 시스템의 성격을 결정한다. Zn*를 쓰면 RSA, Zp*를 쓰면 엘가말과 DSA, 타원곡선 군을 쓰면 ECC와 ECDSA가 된다. 같은 "이산대수 문제"라도 어느 군에서 풀려는가에 따라 효율과 안전성이 크게 달라진다.
앞으로의 흐름도 같은 원리를 따른다. 양자컴퓨터가 등장하면 인수분해와 이산대수가 다항 시간에 풀린다. 그래서 양자내성암호는 격자(lattice), 부호(code), 다변수 다항식, 해시 기반 서명 등 양자컴퓨터가 효율적으로 풀지 못하는 새로운 수학적 구조 위에 설계된다. NIST의 표준화 작업이 끝나면 다시 한 번 암호의 토대가 옮겨질 것이다.
암호학의 기본은 "키만 안전하면 모든 것이 안전하다"는 케르크호프스의 원리에서 출발해 "키도 평문도 어떤 정보도 새지 않는다"는 의미론적 안전성으로 이어진다. 시저가 알파벳을 세 칸 옮기던 시점부터 비트코인이 타원곡선 위에서 서명을 검증하는 오늘날까지, 이 원리만큼은 변하지 않았다.