Square-and-Multiply algorithm, Diffie-Hellman Key Exchange

Seungyun Lee·2026년 3월 3일

Cybersecurity

목록 보기

10/13

고속 거듭제곱: Square-and-Multiply 알고리즘

지수가 $2^{1024}$ 처럼 거대할 때, 곱셈 횟수를 획기적으로 줄여 컴퓨터가 실시간으로 계산할 수 있게 해주는 마법 같은 알고리즘입니다.

[동작 원리]
1. 이진수 변환: 먼저 지수(Exponent)를 이진수(Binary Number)로 변환합니다. (예: $26 \rightarrow 11010_{(2)}$ )
2. 왼쪽에서 오른쪽으로 스캔 (Scan L to R): 가장 높은 비트(MSB)부터 가장 낮은 비트(LSB)로 한 자리씩 읽어 내려갑니다.
3. 규칙 적용 (핵심):

매 비트를 읽을 때마다 무조건 제곱(Square) 연산을 수행합니다.
만약 현재 읽은 비트가 1이라면, 제곱한 결과에 밑(Base, $X$ )을 한 번 더 곱해줍니다 (Multiply).
만약 현재 읽은 비트가 0이라면, 그냥 제곱만 하고 넘어갑니다.

[계산 예시: $X^{26}$ 구하기]
$26$ 을 이진수로 바꾸면 $1 1 0 1 0$ 입니다.

비트 1 (첫 자리): 초기화 단계이므로 그냥 $X^1$ 에서 시작합니다.
비트 1: (무조건 제곱) $(X^1)^2 = X^2 \rightarrow$ (비트가 1이므로 $X$ 곱하기) $X^2 \cdot X = X^3$
비트 0: (무조건 제곱) $(X^3)^2 = X^6 \rightarrow$ (비트가 0이므로 패스)
비트 1: (무조건 제곱) $(X^6)^2 = X^{12} \rightarrow$ (비트가 1이므로 $X$ 곱하기) $X^{12} \cdot X = X^{13}$
비트 0: (무조건 제곱) $(X^{13})^2 = X^{26} \rightarrow$ (비트가 0이므로 패스) $\rightarrow$ 완성!

단 6번의 연산(제곱 4번 + 곱셈 2번)만으로 $X^{26}$ 을 구했습니다. 만약 일일이 곱했다면 25번의 연산이 필요했을 것입니다.

S-A-M 알고리즘

컴퓨터가 $x^{2048}$ 같은 거듭제곱을 계산할 때, 단순히 $x$ 를 $2048$ 번 곱하는 것(Naive 접근법)은 너무나 비효율적입니다.
이 알고리즘은 지수(Exponent)를 이진수(Binary)로 변환한 뒤, 비트의 패턴(0과 1)에 따라 '제곱(Square)'과 '곱셈(Multiply)' 단 두 가지 연산만 조합하여 계산량을 획기적으로 줄여줍니다.

2. 디피-헬먼 키 교환 (Diffie-Hellman Key Exchange)

1. 디피-헬먼 키 교환 (Diffie-Hellman Key Exchange)

A. 디피-헬먼 키 교환의 목적

이 알고리즘의 목표는 단 하나입니다. "서로 만난 적도 없는 Alice와 Bob이, 해커가 지켜보고 있는 불안전한 인터넷망을 통해 대화를 나누면서도 어떻게 둘만 아는 똑같은 '비밀 키'를 만들어낼 수 있을까?" 입니다.

필기는 이 과정을 크게 키 생성/교환(Key/EXCH) 단계와 암호화/복호화(En/Dec) 단계로 나누어 설명하고 있습니다.

B. 키 교환 과정 (Key & EXCH)

[사전 준비: 공개 파라미터]

통신을 시작하기 전, Alice와 Bob은 누구나 다 볼 수 있게 두 개의 숫자를 정해 네트워크에 공개합니다.

P: 매우 큰 소수 (Prime Number)
α: 생성자 (Generator)

[Step 1. 각자의 개인키(Private Key) 선택]

Alice와 Bob은 누구에게도 알려주지 않을 자신만의 비밀 숫자를 하나씩 고릅니다.

Alice: 개인키 a 를 고릅니다. (범위: 2,3,…,p−2)
Bob: 개인키 b 를 고릅니다. (범위: 2,3,…,p−2)

※ 왜 1이나 P−1은 안 될까요? (빨간색 X 표시)
개인키로 1을 고르면 나중에 계산될 공개키가 $α^1 =α$ 가 되어 해커가 단번에 내 비밀키가 1임을 눈치챕니다. P−1을 고르면 페르마의 소정리에 의해 공개키가 무조건 1이 되어버려서 이 역시 보안상 치명적입니다.

[Step 2. 공개키(Public Key) 계산 및 교환]

각자 고른 개인키를 이용해 밖으로 내보낼 공개키를 계산합니다.

Alice: A= $α^a$ modP 를 계산한 뒤, 결과값 A 를 Bob에게 보냅니다.
Bob: B= $α^b$ modP 를 계산한 뒤, 결과값 B 를 Alice에게 보냅니다.

[Step 3. 비밀 세션 키(Session Key) 합성]

상대방으로부터 받은 숫자에 자신의 비밀키를 한 번 더 거듭제곱합니다.
Alice의 계산: 상대방이 준 B를 가져와 $K_{AB} = B^a \bmod P$ 를 계산합니다.
Bob의 계산: 상대방이 준 A를 가져와 $K_{AB} = A^b \bmod P$ 를 계산합니다.

수학의 지수 법칙에 의해 $B^a = (\alpha^b)^a = \alpha^{ab}$ 이고, $A^b = (\alpha^a)^b = \alpha^{ab}$ 가 되므로, Alice와 Bob은 서로의 비밀키(a,b)를 교환하지 않고도 완벽하게 동일한 비밀 세션 키 $K_{AB}$ 를 갖게 됩니다!

C. 하이브리드 암호화 적용 (En / Dec)

필기의 아래 절반은 이렇게 힘들게 만든 세션 키 $K_{AB}$ 를 실제로 어떻게 써먹는지를 보여줍니다.

디피-헬먼 알고리즘은 거듭제곱 연산이 매우 무겁기 때문에 이 키로 영화나 사진 같은 대용량 데이터를 직접 암호화하지 않습니다. 대신, 암호화 속도가 엄청나게 빠른 대칭키 알고리즘(AES)의 비밀키로 사용합니다.

암호화 (Alice): 평문 x를 방금 만든 세션 키 $K_{AB}$ 를 이용해 AES로 암호화합니다.
$y = AES_{K_{AB}}(x)$

복호화 (Bob): 암호문 y를 똑같은 세션 키 $K_{AB}$ 를 이용해 AES로 복호화합니다.
$x = AES^{-1}_{K_{AB}}(y)$

[키 사이즈 불일치 문제 해결]
여기서 실무적인 문제가 하나 발생합니다. 디피-헬먼으로 만든 세션 키 $K_{AB}$ 는 모듈러 P의 영향을 받아 크기가 무려 1024∼2048 비트나 됩니다. 반면 AES 암호화 모듈은 보통 128 비트 크기의 키만 입력받을 수 있습니다.

교수님은 필기 맨 우측 하단에서 그 해결책을 명확히 제시합니다.
거대한 1024비트짜리 키 값 중에서 앞에서부터 128비트만 뚝 떼어서 쓰거나(first), 뒤에서부터 128비트만 떼어서(Last) AES 모듈에 밀어 넣으면 됩니다.

디피-헬먼 키 교환(Diffie-Hellman Key Exchange)이 수학적으로 왜 완벽하게 성립하는지 보여주는 '정확성 증명 (Proof of Correctness)' 부분입니다.

Alice의 계산 (Alice computes)

Alice는 Bob이 보내준 공개키 $B$ 를 받아서, 자신의 개인키 $a$ 로 거듭제곱합니다. $\rightarrow B^a$
그런데 Bob의 공개키 $B$ 는 애초에 생성자 $\alpha$ 를 $b$ 번 거듭제곱하여 만든 값( $\alpha^b$ )이었습니다.
대입해서 식을 풀어쓰면 $(\alpha^b)^a$ 가 되고, 지수의 곱셈 법칙에 의해 최종적으로 $\alpha^{ab} \pmod P$ 가 됩니다.

Bob의 계산 (Bob computes)

Bob은 Alice가 보내준 공개키 $A$ 를 받아서, 자신의 개인키 $b$ 로 거듭제곱합니다. $\rightarrow A^b$
Alice의 공개키 $A$ 는 애초에 $\alpha$ 를 $a$ 번 거듭제곱하여 만든 값( $\alpha^a$ )이었습니다.
마찬가지로 식을 대입해 풀면 $(\alpha^a)^b$ 가 되고, 지수 법칙에 의해 역시 $\alpha^{ab} \pmod P$ 가 됩니다

[왜 굳이 두 가지를 섞어 쓸까?]

- 공개키 암호화(RSA, 디피-헬먼)는 키 교환이 안전하지만 연산 속도가 너무 느립니다. 반면 대칭키 암호화(AES)는 속도가 엄청나게 빠르지만 키를 안전하게 넘겨줄 방법이 없습니다.

- 따라서 **"키 교환은 디피-헬먼으로 안전하게 하고, 실제 데이터 암/복호화는 그때 만들어진 세션 키를 이용해 AES로 아주 빠르게 처리하자!"**는 것이 현대 하이브리드 암호 시스템의 핵심 아이디어입니다.

유한군 (Finite Group)과 곱셈군

암호학에서 수학 연산을 하려면 숫자들이 무한히 커지지 않고 특정 범위 안에서만 맴돌아야 합니다. 이를 위해 유한군(Finite Group)이라는 개념을 도입합니다.

[유한군의 조건]
어떤 집합 $G$ 와 연산(예: 곱셈)이 '군(Group)'이 되려면 다음 조건들을 만족해야 합니다.
1. 닫힘 (Closeness): 두 원소를 연산한 결과도 항상 집합 안에 있어야 합니다.
2. 결합법칙 (Associativity): $(a \cdot b) \cdot c = a \cdot (b \cdot c)$
3. 항등원 (Neutral element): 곱했을 때 자기 자신이 나오게 하는 수(즉, $1$ )가 존재해야 합니다.
4. 역원 (Inverse element): 곱했을 때 $1$ 이 되게 하는 짝꿍( $a^{-1}$ )이 모든 원소에 대해 존재해야 합니다.

[곱셈군의 예시와 한계]

일반적인 모듈러 $9$ 의 집합 $\mathbb{Z}_9 = {0, 1, 2, 3, 4, 5, 6, 7, 8}$ 은 곱셈에 대해 군이 될 수 없습니다. $3$ 이나 $6$ 같은 수는 $9$ 와 서로소가 아니기 때문에(최대공약수가 $1$ 이 아님) 역원이 존재하지 않기 때문입니다.
따라서 역원이 존재하는(즉, 모듈러 값과 서로소인) 숫자들만 쏙 빼서 곱셈 유한군 $\mathbb{Z}_9^ = {1, 2, 4, 5, 7, 8}$ * 을 만듭니다. (예를 들어 이 집합 안에서 $8$ 의 역원은 $8$ 자신입니다. $8 \cdot 8 = 64 \equiv 1 \pmod 9$ 이기 때문입니다.)
핵심 결론: 만약 모듈러 값이 소수(Prime Number, $P$ )라면, $P$ 보다 작은 모든 수는 $P$ 와 서로소입니다. 따라서 소수 $P$ 에 대한 집합 $\mathbb{Z}_p^ = {1, 2, 3, \dots, P-1}$ 은 그 자체로 완벽한 곱셈 유한군*이 됩니다!

Cardinality, Order of an element

집합의 크기 (Cardinality): 군에 속한 원소의 총개수를 의미하며 $|G|$ 로 표기합니다. 예를 들어 소수 $11$ 의 군인 $|\mathbb{Z}_{11}^*|$ 의 크기는 $10$ 입니다.( $1$ 부터 $10$ 까지의 숫자)
원소의 위수 (Order of an element): 어떤 원소 $a$ 를 계속해서 거듭제곱했을 때, 처음으로 항등원( $1$ )이 나오게 하는 가장 작은 지수 $K$ 를 뜻합니다. ( $a^K = 1$ 일 때, $ord(a) = K$ )

[위수 계산 예시 - 모듈러 11]

$a = 3$ 인 경우: $3^1=3, 3^2=9, 3^3=5, 3^4=4, \mathbf{3^5=1}$ (모듈러 $11$ 기준) $5$ 번 만에 $1$ 이 나왔으므로 $ord(3) = 5$ 입니다.
$a = 2$ 인 경우: $2^1=2, 2^2=4, 2^3=8, 2^4=5, 2^5=10, 2^6=9, 2^7=7, 2^8=3, 2^9=6, \mathbf{2^{10}=1}$ , $10$ 번 만에 $1$ 이 나왔으므로 $ord(2) = 10$ 입니다.

Cyclic Group, Generator

위의 $a=2$ 예시를 보면, $2$ 를 계속 거듭제곱( $1$ 승부터 $10$ 승까지)해서 나온 결과값들이 집합 $\mathbb{Z}_{11}^*$ 의 모든 원소 ${1, 2, 3, 4, 5, 6, 7, 8, 9, 10}$ 을 한 번씩 다 만들어냈습니다!

순환군과 생성자의 정의 (필기 상단 박스)

순환군 (Cyclic Group): 집합 내에 '최대 위수(maximum order)'를 가진 원소 $\alpha$ 가 존재하는 그룹입니다. 수식으로는 $ord(\alpha) = |G|$ (원소 $\alpha$ 의 위수 $=$ 집합의 전체 크기)를 만족할 때 이를 순환군이라고 부릅니다.
생성자 (Generator / Primitive element): 위 조건을 만족하는 바로 그 원소 $\alpha$ 를 부르는 이름입니다. 즉, 이 원소 하나를 계속 거듭제곱( $\alpha^1, \alpha^2, \alpha^3 \dots$ )하면 집합 안의 모든 숫자를 다 만들어낼 수 있다는 뜻입니다.

암호학적 의미 (필기 중간 형광펜)
이러한 순환군의 특성은 디피-헬먼 같은 '이산 대수 암호 시스템(Discrete logarithm cryptosystems)'을 구축하는 가장 중요한 수학적 기초가 됩니다.교수님은 "모든 소수 $P$ 에 대한 곱셈 유한군 $Z_p^*$ 는 항상 순환군이다"라는 법칙을 강조하셨습니다.
이산 대수 문제(DLP)의 예시 (필기 하단)
이 부분이 페이지의 핵심입니다. 교수님이 모듈러 $97$ ( $P=97$ )을 예로 들어 질문을 던지십니다.

가정: 집합 $Z_{97}^*$ 의 생성자가 $a=5$ 라고 합시다.
수식: $5^x \equiv 87 \pmod{97}$

질문 1: 이 식을 만족하는 $x$ 가 존재할까요? (Does $x$ exist?)

정답은 YES 입니다. $5$ 가 '생성자'이기 때문에, $5$ 를 계속 거듭제곱하다 보면 집합 내의 모든 숫자(당연히 $87$ 도 포함)가 반드시 한 번씩은 다 나오게 되어 있습니다.

질문 2: 그렇다면 그 $x$ 값은 도대체 얼마일까요? (What is $x$ value?)

이 $x$ 를 구하는 수식이 바로 $x = \log_5 87 \pmod{97}$ 입니다.
거듭제곱의 결과( $87$ )를 보고 거꾸로 지수( $x$ )를 역추적하는 이 계산을 이산 대수 문제(DLP, Discrete Logarithm Problem)라고 부릅니다.

필기 우측 중간을 보면 조그맣게 $2^{1024} \sim 2^{2048}$ bits 라는 빨간 글씨가 적혀 있습니다.

모듈러가 $97$ 처럼 작을 때는 $x$ 를 쉽게 찾을 수 있습니다. 하지만 실제 인터넷 뱅킹이나 암호 통신(디피-헬먼)에서는 이 모듈러 $P$ 로 $2^{1024}$ 비트에 달하는 엄청나게 거대한 소수를 사용합니다.

이 거대한 우주적 스케일에서는 $x$ (해커가 알아내고 싶어 하는 누군가의 개인키)를 찾는 DLP 연산이 사실상 불가능해집니다. 즉, 순환군과 생성자의 성질 덕분에 식 자체는 완벽히 성립하지만, 그 크기를 무지막지하게 키워버림으로써 시스템을 안전하게 지키는 것입니다.

순환군의 두 가지 중요 성질 (Properties of Cyclic Group)
어떤 원소 $a$ 가 순환군 $G$ 에 속해 있을 때, 다음과 같은 두 가지 절대적인 규칙이 성립합니다.

성질 1: $a^{|G|} \equiv 1 \pmod p$ 그룹 내의 어떤 원소( $a$ )든, 그룹의 전체 크기( $|G|$ )만큼 거듭제곱을 하면 그 결과는 무조건 항등원( $1$ )이 된다는 뜻입니다.
성질 2: $ord(a)$ divides $|G|$ 어떤 원소의 위수(거듭제곱해서 $1$ 이 나오기까지 필요한 최소 횟수, $ord(a)$ )는 반드시 그룹 전체 크기( $|G|$ )의 약수(divisor)여야 한다는 뜻입니다. (예를 들어 그룹 크기가 $10$ 이라면, 어떤 원소의 위수는 $1, 2, 5, 10$ 중 하나만 될 수 있고 절대 $3$ 이나 $7$ 이 될 수 없습니다.)

첫 번째 성질의 증명 (Proof of Property 1)
필기 하단은 교수님이 앞서 배웠던 페르마의 소정리(Fermat's Little Theorem)를 가져와 첫 번째 성질이 진짜로 맞는지 증명하는 과정입니다.

[증명 과정]
1. 페르마의 소정리에 따르면, 소수 $p$ 에 대해 $a^{p-1} \equiv 1 \pmod p$ 가 항상 성립합니다. (예시: $2^{p-1} \equiv 1 \pmod p$ )
2. 소수 $p$ 를 모듈러로 하는 곱셈 유한군 $Z_p^*$ 안에는 $1$ 부터 $p-1$ 까지의 숫자가 들어있습니다. 따라서 이 그룹의 전체 크기 $|Z_p^*|$ 는 $p-1$ 이 됩니다.
3. 위 두 사실을 합치면 마법이 일어납니다. 페르마의 공식에 있는 지수 $p-1$ 자리에, 똑같은 값인 그룹의 크기 $|Z_p^*|$ 를 그대로 대입해 봅니다.
4. 결과적으로 $a^{|Z_p^*|} = 1$ 이라는 식이 자연스럽게 도출되며, 첫 번째 성질이 완벽하게 증명되었습니다!

왜 개인키로 $P-1$ 을 쓰면 해킹당할까?
이 증명은 앞서 디피-헬먼 프로토콜에서 생긴 궁금증을 완벽히 해결해 줍니다.

디피-헬먼에서 공개키를 만드는 공식은 $A = \alpha^a \pmod P$ 입니다.만약 내가 바보같이 개인키 $a$ 를 집합의 가장 마지막 숫자인 $P-1$ 로 골랐다고 가정해 봅시다.

그러면 내 공개키는 $A = \alpha^{P-1} \pmod P$ 가 됩니다.방금 필기에서 증명했듯 $P-1$ 은 그룹의 전체 크기( $|G|$ )와 같습니다. 따라서 밑이 되는 생성자 $\alpha$ 가 무슨 숫자이든 간에, 거듭제곱의 결과(내 공개키 $A$ )는 무조건 $1$ 이 되어버립니다!

해커가 네트워크를 훔쳐보다가 누군가의 공개키가 딱 $1$ 인 것을 발견하면, 수학적 원리에 의해 "이 사람의 개인키는 무조건 $P-1$ 이구나!" 하고 바로 알아채게 되는 것입니다. 그래서 $1$ 과 $P-1$ 은 절대 개인키로 골라서는 안 되는 '금지된 숫자'가 됩니다.

순환군의 두 번째 성질인 "어떤 원소의 위수( $ord(a)$ )는 반드시 그룹 전체 크기( $|G|$ )의 약수여야 한다"를 실제 숫자를 대입하여 증명(확인)해 보는 내용입니다.

그룹의 크기 파악
소수 $11$ 을 모듈러로 하는 집합 $Z_{11}^*$ 안에는 $1$ 부터 $10$ 까지의 숫자가 들어있습니다.따라서 이 그룹의 전체 크기( $|Z_{11}^*|$ )는 $10$ 이 됩니다.
각 원소의 위수(Order) 표 분석
필기의 표는 집합 내의 모든 원소 $a$ (1부터 10)에 대해, 거듭제곱해서 1이 나오기까지 걸리는 최소 횟수인 $ord(a)$ 를 전부 계산해 놓은 것입니다.

$a = 1$ : $1^1 = 1$ 이므로 위수는 1 입니다.
$a = 10$ : $10 \equiv -1 \pmod{11}$ 이고, $(-1)^2 = 1$ 이므로 위수는 2 입니다.
$a = 3, 4, 5, 9$ : 이 숫자들은 5번을 거듭제곱해야 1이 나오므로 위수가 5 입니다.
$a = 2, 6, 7, 8$ : 이 숫자들은 무려 10번을 거듭제곱해야 비로소 1이 나옵니다. 위수가 10 입니다.

표가 알려주는 두 가지 중요한 결론
첫째, 생성자(Generator)의 발견
위 표에서 빨간색 별표( $*$ )가 쳐진 $2, 6, 7, 8$ 은 위수가 그룹 전체 크기인 $10$ 과 똑같습니다. 즉, 이 4개의 숫자는 집합 내의 모든 숫자를 다 만들어낼 수 있는 '생성자(Generators)' 역할을 완벽히 수행합니다. (생성자가 꼭 하나일 필요는 없다는 것을 보여줍니다.)