Diffie-Hellman Algorithm

• The discrete logarithm problem | Khan Academy
• Public key cryptography: What is it? | Khan Academy

들어가기 앞서 위의 영상들을 반드시 시청하는 것을 추천한다.

우리가 온라인에서 안전하게 대화를 나누려면, 나와 상대방만 알고 있는 대칭키 를 이용하여 데이터를 암복호화한다.
하지만 여기서 큰 문제가 있다.

우리가 사용할 대칭키를 어떻게 안전하게 상대방에게 전달함?

• 직접 만날 수 있다면: USB에 담아 손으로 직접 전달하면 된다.
• 온라인 통신이라면: 키를 보내는 순간, 중간에서 도청하고 있는 해커에게 키가 그대로 노출됨.

이처럼 공개된 통로에서 어떻게 비밀스러운 키를 나누어 가질 것인가 라는 문제를 해결하기 위해 등장한 것이
디피-헬만(Diffie-Hellman) 알고리즘이다

핵심 원리

디피-헬만은 복잡한 수학(이산 대수 문제)을 기반으로 하지만, 원리는 물감 섞기 와 비슷하다.

1. 공통의 색: 나와 상대방이 똑같은 base 색상을 정한다 (이 색상은 공개되어도 상관없음)
2. 나만의 비밀 색: 각자 자신만 아는 비밀 색상을 고른다.
3. 혼합색 공유: 기본 색상에 내 비밀 색상을 섞어서 상대방에게 보낸다.

• 중간에 이 혼합색을 훔쳐봐도 해커는 어떤 비밀 색상이 들어갔는지 분리해낼 수 없다.

4. 최종 키 생성: 상대방이 보낸 혼합색에 다시 내 비밀색을 섞는다.

결과적으로 나와 상대방은 정확히 똑같은 색상(대칭키)를 갖게 되지만, 중간에 통신을 엿본 사람은 이 색을 만들 수 없다

이산 대수 문제(Discrete Logarithm Problem)

이산 대수 문제는 지수 계산은 쉽지만, 결과값만 보고 지수를 찾는 것은 쉽지 않다는 것임

일반적으로 수학에서 2^X = 16 이라고 하면, 금방 x=4 인 것을 알 수 있음

하지만 디피헬만에서 사용하는 나머지 연산(modulo)가 들어가면,

만약 3^x (mod 17) = 13 일 때 x 의 값은 무엇일까?

x의 값을 알기 위해서는 하나하나 값을 넣어봐야한다.

• 3^1 = 3
• 3^2 = 9
• 3^3 => 27, 27%17=10
• 3^4 => 81, 81%17=13

지금은 숫자가 작아서 금방 풀렸지만, 실제 암호학에서 사용하는 수는 거대한 소수이다.

이산(Discrete) 은 연속적이지 않다 라는 뜻으로, 나머지 연산 값이 3, 9, 10, 13이 나오는 것 처럼 예측 불가능한 형태를 띠는 것을 말함

원시근(Primitive root)

$g^n$ 에 대해 modulo 연산 하는 p 가 있다고 할때

$g^1,g^2,g^3,...,g^{p-1}(\mathrm{mod}p)$

이 값들이 중복 없이 {1,2,3,...p-1} 를 한번씩 만들 수 있다면 g는 p의 원시근이라고 할 수 있다.

영상에서 보면 3은 17의 원시근이다.

수학적 원리

디피-헬만 알고리즘은 이산대수 문제의 어려에 기반하고 있음

• 단방향으로 계산하기는 쉽지만, 거꾸로 되돌리기는 매우 어렵다 라는 성질.

1. 공통 수

• 먼저 통신하려는철수와 영희는 공개된 공간에서 두 개의 숫자를 정한다.(이숫자는 해커가 알아도 상관없음)
• p: 아주 큰 소수
• g: p에 대한 원시근

2. 각자 비밀번호 생성 (private key)

철수와 영희는 외부로 절대 공개하지 않는 본인만 알고 있는 숫자를 고른다.

• 철수: a
• 영희: b

3. 혼합값 계산 후 교환(public key exchange)

이제 각자 자신의 비밀 값을 넣어서 계산한 혼합값을 교환한다.

• 철수가 계산한 값 ($A$): $A=g^a(\mathrm{mod}p)$
• 영희가 계산한 값 ($B$): $B=g^b(\mathrm{mod}p)$

4. 공개키 도출

상대방에게 받은 값에 다시 나의 비밀 값을 거듭제곱하면 똑같은 값이 나온다(대칭키)

• 철수의 계산: $B^a(\mathrm{mod}p)=(g^b{)}^a(\mathrm{mod}p)={\mathbf{g}}^{\mathbf{ab}}\mathbf{(}\mathrm{mod}\mathbf{p}\mathbf{)}$
• 영희의 계산: $A^b(\mathrm{mod}p)=(g^a{)}^b(\mathrm{mod}p)={\mathbf{g}}^{\mathbf{ab}}\mathbf{(}\mathrm{mod}\mathbf{p}\mathbf{)}$
• 대칭키: $g^{ab}(\mathrm{mod}p)$

중간자 공격

디피헬만은 이렇게 보면 매우 안전한 것처럼 보이지만 큰 문제가 있다.

상대방이 진짜 내가 대화하려하는 대상이 맞는지 확인할 수 있는 방법이 없음.

만약 A와 B 사이 통신 구간 사이 해커가 개입한다고 가정해보면,

• A와B가 자신의 혼합값을 보낼 때 해커가 이를 가로채고 임의로 만든 값(E1,E2)를 전달.
• A와B는 서로 통신한다고 착각하지만, 실제론 각각 해커와 만든 대칭키를 통해 통신.
• 해커는 두 키(혼합값)을 알고 있기 때문에 복호화가 가능.

나머지 연산의 성질

$$(g^a(\mathrm{mod}p){)}^b(\mathrm{mod}p)=g^{ab}(\mathrm{mod}p)$$

나머지 연산은 곱셈과 거듭제곱에 대해 순서가 바뀌어도 결과가 같다

숫자를 다 곱한다음 마지막에 나머지를 구하는 것과, 중간중간 나머지를 구하면서 계산하는 것은 같기 때문.