타원 곡선 디피-헬만(ECDH) 키 교환은 타원 곡선 암호(ECC)를 이용하여 안전하게 비밀 키를 공유하는 방법입니다. 이 과정의 보안은 '타원 곡선 이산 대수 문제(Elliptic Curve Discrete Logarithm Problem, ECDLP)'라는 수학적 난제에 기반을 둡니다.
쉽게 말해, 타원 곡선 위의 한 점에서 특정 연산을 반복하여 다른 점을 찾는 것은 쉽지만, 결과 점만 가지고 몇 번의 연산을 했는지 알아내는 것은 계산적으로 매우 어렵다는 원리입니다.
ECDH 키 교환 과정
앨리스와 밥이 안전하지 않은 통신 채널을 통해 비밀 키를 공유하려는 상황을 가정해 보겠습니다.
- 초기 설정 공유: 먼저, 앨리스와 밥은 모두가 알아도 되는 공개된 정보 두 가지를 사전에 합의합니다.
- 타원 곡선 ($E$): 사용할 특정 타원 곡선 방정식입니다.
- 기준점 ($G$): 해당 타원 곡선 위의 한 점으로, 모든 계산의 시작점이 됩니다.
- 각자의 비밀 키와 공개 키 생성:
- 앨리스: 임의의 정수 $a$를 자신의 비밀 키로 선택합니다. 그리고 기준점 $G$에 $a$번의 덧셈 연산을 수행하여 새로운 점 $P_A = a · G$를 계산하고, 이 점을 자신의 공개 키로 만들어 밥에게 보냅니다.
- 밥: 마찬가지로 임의의 정수 $b$를 자신의 비밀 키로 선택합니다. 그리고 기준점 $G$에 $b$번의 덧셈 연산을 수행하여 새로운 점 $P_B = b · G$를 계산하고, 이 점을 자신의 공개 키로 만들어 앨리스에게 보냅니다.
- 공유 비밀 키 계산:
- 앨리스: 밥에게서 받은 공개 키 $P_B$에 자신의 비밀 키 $a$를 곱합니다.
- $S = a · P_B = a · (b · G) = (ab) · G$
- 밥: 앨리스에게서 받은 공개 키 $P_A$에 자신의 비밀 키 $b$를 곱합니다.
- $S = b · P_A = b · (a · G) = (ab) · G$
- 키 교환 완료: 앨리스와 밥은 중간에서 통신을 도청한 사람이 있더라도, 각자 동일한 점 $S$를 계산해 낼 수 있습니다. 이 점 $S$의 특정 좌표(예: $x$ 좌표)를 공유 비밀 키로 사용하여 대칭 키 암호 통신을 시작할 수 있습니다.
핵심 보안 원리: 타원 곡선 이산 대수 문제 (ECDLP)
ECDH의 안전성은 중간에 통신을 가로채는 공격자 '이브'가 공유 비밀 키 $S$를 계산할 수 없다는 사실에 달려있습니다.
- 이브는 통신 채널에서 $E, G, P_A, P_B$를 모두 엿볼 수 있습니다.
- 공유 비밀 키 $S$를 계산하려면 앨리스의 비밀 키 $a$ 또는 밥의 비밀 키 $b$를 알아야 합니다.
- $a$를 알아내려면, 이브는 $P_A = a · G$ 라는 수식에서 공개된 값인 $P_A$와 $G$를 보고 $a$를 역으로 계산해야 합니다.
- 이것이 바로 타원 곡선 이산 대수 문제입니다. 타원 곡선 위의 점에서 덧셈 연산을 통해 다른 점을 구하는 것은 쉽지만, 결과 점과 시작점을 안다고 해서 몇 번의 덧셈 연산을 했는지 알아내는 것은 현재의 컴퓨팅 기술로 사실상 불가능에 가깝습니다.
정리하자면, 공격자는 공개된 정보들을 모두 가지고 있어도 비밀 키 $a$나 $b$를 계산할 수 없으므로, 최종 공유 비밀 키인 $S$ 역시 알아낼 수 없습니다. 이 덕분에 ECDH는 매우 안전한 키 교환 방식으로 널리 사용됩니다.
댓글
댓글 쓰기