Diffie-hellman

Diffe-hillman 알고리즘

Diffie-Hellman 키 교환은 공개키 암호화 기법 중에서 대칭 키를 공유하기 위해 사용되는 방법입니다.
이 알고리즘의 목적은 두 사용자가 비밀 키를 안전하게 교환하는데 있다
알고리즘 자체는 키를 교환하는데 국한되어서 사용한다

핵심

Diffie-Hellman 키 교환의 핵심은 이산 로그 문제와 모듈러 산술 문제입니다.
이를 이용하여 Alice와 Bob은 비밀 수를 선택하고, 이를 통해 대 키(비밀키)를 생성합니다.

이 알고리즘은 인증 및 기밀성이 보장되지 않으므로, 보안 통신 시스템에서는 이를 보완하기 위해 추가적인 암호화 방법을 사용합니다.
예를 들어, SSL/TLS 프로토콜에서는 Diffie-Hellman 키 교환을 사용하면서, 서버 인증을 위해 디지털 인증서를 사용합니다.

그러나 Diffie-Hellman 키 교환의 약점은 다음과 같습니다.

• 중간자 공격(MITM)에 취약합니다. 중간자가 Alice와 Bob 사이의 통신을 가로채고, 자신이 대신 통신하게 되면, 이 알고리즘으로 생성된 대칭 키는 중간자에게 노출됩니다.
• 공격자가 이산 로그 문제를 해결하는 데 필요한 컴퓨팅 파워를 가지고 있다면, 비밀 키를 추적할 수 있습니다.

알고리즘

1. 먼저, 양쪽(A, B)에서 공통으로 사용할 소수 q와 q의 원시근 알파(alpha)를 정합니다.
2. A는 랜덤한 값 X_A를 선택합니다. 그리고 Y_A = alpha^(X_A) mod q를 계산하여 B와 공유합니다.
3. B는 랜덤한 값 X_B를 선택합니다. 그리고 Y_B = alpha^(X_B) mod q를 계산하여 A와 공유합니다.
4. 이제 A와 B는 각자 계산한 Y_A와 Y_B를 사용하여 공통의 비밀키 K를 계산합니다. 이때, K = Y_B^(X_A) mod q = Y_A^(X_B) mod q로 계산됩니다.
5. 이제 A와 B는 서로 비밀키 K를 공유합니다. 이후에는 이 비밀키 K를 사용하여 대칭키 암호화 방식으로 안전하게 통신할 수 있습니다.

여기서 X_A, X_B는 각각 A와 B만이 알고 있는 비밀값입니다.
Y_A, Y_B는 공개되어도 상관없는 값이며, q와 alpha는 누구나 알고 있어도 상관없는 값입니다.

이렇게 함으로써, A와 B는 각각 계산한 Y_A와 Y_B를 서로 교환하면서 안전하게 K를 계산할 수 있습니다.

디피-헬맨 키의 마법은 이산 대수의 원시근 규칙때문에 발생합니다
이산 대수의 원시근 규칙에 따르면, 소수 P의 한 원시근이 되는 수는 모두 하나의 집합에 속하게 됩니다.
이러한 원시근은 두 사람 간에 서로 다른 비밀값을 공유하는 데 사용됩니다. 이는 치환 가능하다는 것을 의미합니다.

보안

디피-헬만 키 교환 알고리즘의 보안은 이산 로그 문제(discrete logarithm problem)의 어려움에 기반합니다.
이산 로그 문제는 주어진 유한 집합에서 두 개의 원소와 일정한 기저(base)를 사용하여 기저를 얼마나 거듭제곱해야 다른 원소를 얻을 수 있는지를 찾는 문제입니다.

이산 로그 문제가 어렵다는 것의 근거는 다음과 같습니다.

1. 계산 복잡도
   • 현재까지 알려진 대부분의 알고리즘은 이산 로그 문제를 풀기 위해 지수 시간이나 서브 지수 시간이 걸리는 것으로 알려져 있습니다.
   • 이는 큰 소수를 사용할 경우 공격자가 문제를 풀기 위해 막대한 시간이 걸린다는 것을 의미합니다.
2. 알려진 효율적인 알고리즘 부재
   • 이산 로그 문제를 효율적으로 해결할 수 있는 알고리즘이 아직 발견되지 않았습니다.
   • 몇 가지 알고리즘들이 있지만, 일반적으로 큰 소수를 사용할 경우 여전히 매우 느리고 비효율적입니다.
3. 양자 컴퓨팅의 영향
   • 양자 컴퓨터는 이산 로그 문제를 빠르게 해결할 수 있는 알고리즘인 쇼어 알고리즘(Shor’s Algorithm)을 사용할 수 있습니다.
   • 하지만 현재 양자 컴퓨터는 상업적 환경에서 사용하기에는 매우 초기 단계이므로, 이산 로그 문제는 아직 어려운 문제로 남아 있습니다.
     이러한 이유로 인해 디피-헬만 키 교환 알고리즘은 이산 로그 문제의 어려움을 활용하여 안전한 키 교환을 보장합니다.

부족한 점이나 잘못 된 점을 알려주시면 시정하겠습니다 :>