Diffie-Hellman은 공개된 통신만으로 두 사람이 같은 비밀값을 계산하게 한다. 그 기반에는 군의 연산과 이산로그 문제가 있으며, ElGamal 암호도 이 구조를 이용한다.
1. 군(Group)의 정의
집합 G와 이항연산 에 대해 다음 네 가지 조건을 만족하면 를 군이라고 한다.
-
Closure: 모든 에 대해
-
Associativity:
-
Identity: 가 존재하여
-
Inverse: 모든 에 대해 인 역원이 존재
추가로 이면 **Abelian Group(가환군)**이다. 부분집합 가 같은 연산으로 군이면 **Subgroup(부분군)**이다.
군의 예제
-
, , , 는 가환군
-
는 의 부분군
-
, , 는 곱셈에 대한 가환군
-
는 3의 곱셈 역원이 이 집합 안에 없으므로 군이 아님
-
가역 행렬의 곱셈군은 일반적으로 비가환군(AB가 BA와 다름)
-
는 n원소의 가환군
-
는 n과 서로소인 원소만 포함하는 곱셈 가환군이며
2. 원소의 위수와 순환군
2.1 Order of an Element
의 위수는 반복 연산으로 단위원이 처음 나오는 최소 양의 정수다.
예시에서 안의 3은
따라서 다.
2.2 Cyclic Group과 Generator
어떤 의 위수가 이면 G는 순환군이고 g를 생성원(generator, primitive element)이라 한다.
예시:
따라서 이고, 2는 생성원이다. 반면 3은 전체군의 생성원은 아니지만 부분군
의 생성원이다.
3. Discrete Logarithm Problem(DLP)
3.1 정의
군 G의 생성원 g와 가 주어졌을 때 미지의 지수 a를 찾는 문제다.
실수에서의 로그 계산과 달리 충분히 큰 유한군에서의 이산로그 계산은 어려울 수 있다. 단, 작은 군에서는 손으로 거듭제곱을 반복하여 쉽게 구할 수 있다. 예를 들어 에서 일 때, 을 만족하는 a를 찾는 문제다.
3.2 알려진 공격 알고리즘
군의 크기와 구조에 따라 다음 알고리즘을 고려한다.
-
법 p가 충분히 커야 한다. 유한체 곱셈군 전체에 대한 General/Special Number Field Sieve 공격을 고려해야 한다.
-
부분군의 위수 q도 충분히 커야 한다. Pollard rho 같은 generic DLP 공격의 복잡도는 대략 에 비례한다.
NIST(2020)의 보안강도별 크기 비교:
| 목표 강도 | q의 비트 수 | p의 비트 수 |
|---|---|---|
| 80 | 160 | 1024 |
| 112 | 224 | 2048 |
| 128 | 256 | 3072 |
| 192 | 384 | 7680 |
| 256 | 512 | 15360 |
이는 2020년 시점의 보안강도 비교로, 최신 표준 선택을 대체하는 것은 아니다.
4. Diffie-Hellman Key Exchange
4.1 목적과 역사
Alice와 Bob이 공개 채널만 이용해 같은 공유 비밀값을 생성하는 절차다. Whitfield Diffie와 Martin Hellman이 1976년에 발표했다.
4.2 사전 공유 매개변수
-
소수 p
-
또는 선택된 순환 부분군의 생성원 g
-
각 참여자는 별도의 개인 지수 a,b를 선택
4.3 키 교환 절차
Alice
-
비밀 지수 a 선택
-
계산
-
A를 Bob에게 전송
-
Bob의 B를 받아 계산
Bob
-
비밀 지수 b 선택
-
계산
-
B를 Alice에게 전송
-
Alice의 A를 받아 계산
양쪽 결과의 동일성:
4.4 계산 예제
매개변수 , Alice의 , Bob의 일 때
공개값을 교환한 뒤
두 참여자 모두 공유값 4를 얻는다.
5. DH의 안전성과 CDH
공격자 Eve는 를 볼 수 있다. 개인 지수 a 또는 b를 획득하면 공유값을 바로 계산할 수 있다. 개인 지수 복원이 DLP와 연결된다.
CDH(Computational Diffie-Hellman) Problem
CDH는 지수 a 또는 b를 반드시 직접 구하지 않더라도 공유 비밀을 계산할 수 있는지를 묻는다. DLP를 풀 수 있으면 CDH도 풀 수 있지만, 일반적으로 두 문제가 다항시간 동치라고 증명된 것은 아니다.
6. Man-in-the-Middle(MITM) Attack
6.1 문제 상황
인증되지 않은 DH는 중간자 Eve가 Alice에게는 Bob인 척, Bob에게는 Alice인 척할 수 있다.
-
Eve가 비밀 지수 e를 선택하고 계산
-
Alice가 보낸 A와 Bob이 보낸 B를 가로채 양쪽 모두에게 E 전달
-
Alice는 생성
-
Bob은 생성
-
Eve는 A와 B를 알므로 , 를 각각 계산 가능
따라서 Alice와 Bob이 같은 비밀키를 공유하지 못하고 각각 Eve와 다른 비밀키를 공유하게 된다. Eve는 Alice의 메시지를 복호화하고 재암호화하여 Bob에게 전달할 수 있다.
6.2 방어
**참가자 인증(Authentication)**이 필요하다. 공개값을 보낼 때 전자서명을 덧붙여 인증할 수 있다. 단, 서명만 붙이는 것으로 끝나지 않고 검증키가 실제 해당 주체의 것이라는 신뢰 관계도 필요하다.

7. ElGamal Encryption
7.1 역사와 성질
Taher El Gamal이 1985년 제안한 공개키 암호다. Probabilistic Encryption이며 각 암호화에 랜덤 지수 r이 필요하다.
7.2 DDH(Decisional Diffie-Hellman) Problem
가 주어졌을 때
인지를 구분하는 문제다. 후자는 독립적으로 무작위 선택한 c의 거듭제곱이다. 적절한 그룹과 DDH 가정 아래 원래의 ElGamal은 IND-CPA 안전성을 얻는다.
7.3 Key Generation
-
큰 소수 p, 그리고 관련 부분군 위수 q를 선택
-
의 위수 q인 순환 부분군 G의 생성원 g 선택
-
비밀 지수 선택
-
공개 원소 계산
7.4 Encryption
평문 M을 부분군의 원소로 표현해야 한다. 일회용 무작위값 를 선택하여
를 계산하고 암호문은
이다.
7.5 Decryption
정합성 증명:
만으로 메시지를 알아낼 수 없으며, 무작위 r을 선택하므로 같은 메시지에서도 서로 다른 암호문이 나올 수 있다.
8. ElGamal의 곱셈 준동형성과 보안 모델
ElGamal은 원래 구조에서
라는 곱셈 준동형성을 갖는다. 암호문 두 쌍의 각 성분을 곱하면 그 결과는 평문의 곱에 대한 적절한 무작위화된 암호문이 된다. 이 성질은 응용에서 유용하지만, 원래 ElGamal 자체가 IND-CCA2를 제공하지 않음도 뜻한다. 더 강한 보안성을 얻으려면 별도의 안전한 변환이 필요하다.
9. 중요 비교
| 개념 | 질문 | 결과 |
|---|---|---|
| DLP | 에서 a를 계산할 수 있는가? | 개인 지수 복원 문제 |
| CDH | 에서 을 계산할 수 있는가? | 공유 비밀 계산 문제 |
| DDH | 주어진 X가 인지 구별하는가? | 공유 비밀의 무작위성 구별 |
| DH | 공개 채널로 같은 비밀을 공유할 수 있는가? | 가능하지만 인증 없는 MITM에 취약 |
| ElGamal | 공개키로 확률적 메시지 암호화를 할 수 있는가? | DDH 가정 하 IND-CPA |
Comments