6주차 정리

공개키 암호와 키 교환 알고리즘

---

Diffie-Hellman 알고리즘

 

1. 들어가며

• 대칭키 암호는 임의의 데이터를 안전하게 암호화할 수 있는 암호 기술이지만, 이를 이용하여 수신자와 송신자가 데이터를 주고받으려면, 수신자와 송신자가 같은 키를 공유하고 있다는 전제가 필요하다.
• 즉, 데이터를 교환하기 전에 키 교환(Key Exchange)이 이뤄져야 한다.
• 그런데 아주 먼 거리에 있는 대상과 통신하는 현대 유무선 환경에서는 안전한 키 교환이 쉽지 않다.
• 대칭키 암호의 안전성은 키에서 비롯되므로, 키를 안전하게 공유할 수 없는 환경에서 대칭키 암호는 무용지물이다.
• 그래서 암호학자들은 네트워크 같은 공개된 채널을 통해 키를 교환해도 외부인은 키를 알 수 없게 하는 공개 키 교환 알고리즘을 고안했다.

-> Diffie-Hellman 키 교환 절차(Diffie-Hellman key exchange protocol)

---

2. Diffle-Helman 키 교환

1. 수학적 원리

1976년 Whitfield Diffie와 Martin Hellman은 공개된 채널로 키를 교환할 수 있는 Diffie-Hellman 키 교환 절차를 만들었다.

-> 이걸 이해하기 위해선 다양한 수학적 배경지식이 필요하다. 

 

-모듈로 연산에서의 거듭제곱

• 임의의 합동 항등식에 대해, 양변에 동일한 값을 곱해서 식은 성립한다.
• 따라서 a^k ≡ 1 b 일 때, a^k * a^k ≡ a^2≡b^2(mod m)이 성립한다.
• 이를 이용하여 큰 지수에 대한 합동식을 빠르게 연산하는 알고리즘을 square and multiply라고 부른다.
• Diffie-Hellman 키 교환 알고리즘을 사용하려면 2^2048번 가까이 제곱된 어떤 수의 모듈러 값을 구해야 하는데, 이 방법을 사용하면 2048번 정도만 연산해도 그 값을 구할 수 있다.

 

-페르마의 소정리(Fermat's Little Theorem)

: 페르마의 소정리는 소수 p와 정수 a에 대해 a^p-1 ≡ 1 (mod p)이 성립한다는 정리이다.

 

-이산 로그 문제(Discrete Logarithm Problem)

• 이산 로그 문제는 "자연수 a, m, 정수 b에 대해 a^x ≡ b (mod m)을 만족하는 정수 x를 구하는 문제"이다.
• Diffie-Hellman 알고리즘의 안전성은 이산 로그 문제의 어려움에 바탕을 두고 있다.
• Diffie-Hellman 키 교환 알고리즘에서 키를 모르는 공격자가 키를 구하려면 m이 2^2048 정도 되는 이산 로그 문제를 풀어야한다.
• 이는 현재의 연산능력으로는 불가능하다.

2. 키 교환 절차

• Diffie-Hellman 키 교환에서 통신을 진행하는 가상의 두 인물을 Alice와 Bob라고 가정하자.
• 키를 교환하고자 하는 Alice는 소수 p와 1 <= g <= p-1을 만족하는 적당한 수 g를 정해 Bob에게 전송한다.
• p는 보통 2^1024 이상의 큰 소수로 설정한다.
• 다시 Alice는 1 <= a <= p-1을 만족하는 적당한 수 a를 정하여 A = g^a mod p를 Bob에게 전송한다.
• 공격자는 둘 사이의 통신을 도청하여 p, g, g^a mod p, g^b mod p를 알아낼 수 있다.
• 그러나 이산 로그 문제의 어려움으로 인해 g^a mod p로부터 a를 알아내거나 g^b mod p로부터 b를 알아내는 것은 불가능하며, 결과적으로 K = g^ab mod P를 구할 수 없다.
• 이 알고리즘을 이용하면 Alice와 Bob은 모두에게 공개된 통신 채널을 이용하여도 서로 안전하게 키를 교환할 수 있다.

3. 중간자 공격

• 네트워크로 통신하는 두 주체는 서로의 신원을 확인하기 어렵다.
• 중간자 공격(Man In The Middle attack, MITM)은 네트워크의 이런 특성을 이용한 공격이다.
• 일반적으로 네트워크에서 발생하는 공격은 공격자가 통신에 개입하지 않으면 수동적 공격으로, 직접 개입하면 능동적 공격으로 구분된다.
• 능동적 공격자는 통신을 도청하면서 중간에 데이터를 위변조할 수 있고 중간자 공격이 이에 해당한다.
• Diffie-Hellman 키 교환은 중간자 공격에 취약하다.
• 공격자는 둘 사이에 오가는 정보를 모두 알 수 있으며, 필요하면 이를 변조할 수 있다.
• 이런 취약점으로 인해, Diffie-Hellman 키 교환은 서로의 신원을 확인할 수 있는 추가적인 메커니즘이 동반되어야 안전하게 이뤄질 수 있다.

---

3. 마치며

키 교환 알고리즘의 등장으로, 네트워크를 이용하는 두 통신자는 안전하게 키를 교환할 수 있게 되었다.

현대에는 키 교환 알고리즘으로 대칭키를 교환하고, 교환한 대칭키로 암호화된 통신을 하는 방식이 널리 사용되고 있다.

최근에는 Diffie-Hellman 알고리즘이 더욱 뛰어난 성능을 보여주는 타원 곡선 Diffie-Hellman 알고리즘으로 발전하였다.

 

Textbook-DH 답

DH{6625fe941be9a9ad76f0ca7b3250d83d2f8f33ccee8aa5a55a605a3a8e9b7104}

---

RSA

---

1. 들어가며

RSA 암호 알고리즘의 안전성은 아주 큰 두 소수의 곱으로 이루어진 합성수를 인수분해하기 어렵다는 인수분해 문제의 어려움에 기반한다. 따라서 RSA로 암호화할 때는 합성수의 소인수분해가 어려워지도록 각 인자를 적절히 설정해야 한다.

RSA는 암복호화 과정에서 AES를 비롯한 대칭키 암호 알고리즘보다 훨씬 많은 연산을 필요로 한다. 따라서 많은 데이터를 여러 번 암호화해야 하는 네트워크 통신에서는 잘 사용되지 않는다.

---

2. RSA

1. RSA 암호 알고리즘

• RSA 암호 알고리즘에서는 대칭키 암호와 달리 두 개의 키가 사용된다.
• 하나는 공개키(Public Key)로 모든 사용자에게 공개되며, 평문을 암호화할 때 사용된다. 다른 하나는 개인키(Private Key)로 타인에게 노출되어서는 안 되며, 공개키로 암호화된 암호문을 복호화할 때 사용된다.

2. 오일러 정리

• 오일러 정리는 n과 서로소인 양의 정수 m이 다음 식을 만족한다는 정리이다.
• mφ(n)≡1(modn)
•  \varphi (n)φ(n)는 오일러 파이 함수(Euler's phi function)라고 불리며, n 이하의 양의 정수 중에서 n과 서로소인 수의 개수를 의미한다.

3. 키 생성

• 공개키 암호 알고리즘에서는 공개키와 개인키를 생성하는 키 생성 과정이 필요하다.
• 대칭키 암호 알고리즘에서는 임의의 난수를 선택하기만 하면 됐지만, RSA는 인수분해를 어렵게 만들기 위해 복잡한 연산을 거쳐 키를 생성해야 한다.
• 먼저 서로 다른 두 소수 pp와 qq를 선택한다. 일반적으로 1024비트 이상에서 비트 길이가 같은 수로 생성한다. 그 뒤, pp와 qq를 곱하여 nn을 구하고, \varphi (n)φ(n)을 계산한다.

4. 암호화

공개키 (n,e)로 n보다 작은 평문 m을 암호화할 때, 암호문 c는 다음 식으로 구해진다.

-> c ≡ m^e (mod n)

 

5. 복호화

암호문 c를 개인키 d로 복호화할 때, 평문 m은 다음과 같이 구해질 수 있다.

m ≡ c^d (mod n)

---

3. RSA 공격

1. 작은 e

-Coppersmith 공격

• Coppersmith 정리에 따르면, 차수가 e인 함수 f(x)에서 찾고자 하는 근이 n^{1/e}보다 작을 경우, 복잡도가 O(logn)인 알고리즘을 이용하여 근을 구할 수 있습니다.

2. Hastad's Broadcast 공격

• 이 공격은 한 송신자가 다수의 수신자에게 동일한 평문을 전송할 때, 수신자들에게 모두 동일한 작은 e 값을 사용할 경우 가능한 공격 방법이다.
• m3≡c(modn1​n2​n3​)

3. 공통 n 사용

-Common Modulus Attack

• Common Modulus Attack은 같은 n과 서로소인 두 공개 지수 e1,e2​를 사용하여 같은 평문m을 암호화해서 두 암호문 c1 , c2​을 만들었을 때, 이를 공격하는 기법이다.
• 공격자는 두 공개 지수가 서로소라는 점을 활용해 re1 + se2 = 1이고, r이 음수인 (r,s) 쌍을 확장 유클리드 알고리즘을 통해 구할 수 있다.
• 그 후 확장 유클리드 알고리즘을 사용해 c1 ^ {-1} (mod n)을 구한다.

4. 작은 d

• 비밀 지수 d가 작아도 여러 공격에 취약하다. 
• 비밀 지수를 설정할 때는 n보다 적당히 큰 수가 되도록 해줘야 한다.

---

4. 마치며

• 대칭키 암호와 공개키 암호의 큰 차이점 중 하나는 공개키 암호는 어려운 수학 문제를 기반으로 하여 암호시스템의 안전성을 확보한다는 점이다.
• 인수분해의 어려움을 기반으로 하는 RSA 외에도 이산대수의 어려움을 기반으로 하는 EIGamal 암호, 타원곡성 상에서의 이산대수의 어려움을 기반으로 하는 Elliptic Curve EIGamal 암호 등 다양한 공개키 암호 알고리즘이 존재한다.

 

Textbook-RSA 답

DH{6623c33be90cc27728d4ec7287785992}