[정보보안] 9. 공개 키 암호

키 배송 문제

지금까지 블록 암호인 DES와 AES를 알아보았다. 이들은 대칭 암호이며 암호화, 복호화 시 같은 키를 사용한다. 그래서 이 키를 비밀 키, 대칭 키, 관용 키 등으로 부른다. 그런데 두 사람이 데이터를 주고 받아야 할 때 이 키를 공유하는 방법은 어떤 것을 사용해야 할까? 바로 옆에 있다면 그냥 말로 할 수도 있고 또는 USB에 담아서 줄 수도 있다. 하지만 멀리 떨어져 있는 상황이라면? 이 문제를 어떻게 해결해야 하는가?

1. 키의 사전 공유

키를 사전에 공유하는 방법이다. 직접 전해주기가 이 방법이다.

2. 키 배포 센터

키를 전문 센터의 데이터베이스에서 관리하며 통신 시에 세션 키를 사용하는 방법이다.

3. Diffie-Hellman 키 교환

송신과 수신 사이에 먼저 특정한 정보를 교환하고 그 정보를 이용한 키를 만드는 방법이다.

4. 공개 키 암호 사용

비대칭 암호로서 수신 측에서 개인 키로 암호화한다.

2. 공개 키 암호 방식의 등장

배낭 암호(Knapsack Cryptosystem)

• 최초의 공개 키 암호화를 적용한 암호 시스템이다.
• Merkle과 Hellman이 제안했다.
• 배낭 속의 수로 만들어진 합만 알고 있는 상태로 그 배낭 속에 어떤 것이 들어있는지 유추하기 어려운 성질을 이용한 방법이다.
• 예제
  • 배낭 속에는 85, 13, 9, 7, 47, 27, 99, 86 이 들어있고 합은 172이다.
  • 172에 해당하는 암호 값은 1 1 0 0 1 1 0 0(85 + 13 + 47 + 27) 이다.
  • 만약 배낭 속의 숫자를 알려주지 않고 172를 가지고 몇 번째 숫자가 쓰였는지 알아내라고 한다면 알 수 있을까?

3. 공개 키 암호의 개념

Shannon이 제안한 양질의 암호 - FIPS에서 정의

1. 암호 해독에 많은 작업량이 요구될 것
2. 키의 크기가 작을 것
3. 암호화, 복호화 과정이 다를 것
   • 입력 $x$에 대해 $y=f(x)$ 로 계산한 후 $y$에 대해 $x=f^{-1}(y)$ 가 어려워야 한다.
   • → 단방향 함수 사용
4. 오류 시 전파도가 적을 것
5. 평문이 암호화 과정에 의해 길어지지 않을 것

1. 공개 키 암호화 = 비대칭 키 암호화 ⇒ 스트림

1. 단방향 함수에 근거한다.
   • 소수, 이산대수, 타원 등
2. 암호화와 복호화 키가 서로 다르다.
3. 공개되는 키와 개인이 보관하는 비밀 키를 사용한다.
4. 복호화 키는 수신자에 의한 비밀보관이 필요하다.
5. 전자 서명에 적용된다.
6. 대표적 사례: RSA

• 장점
  • 키 배송 문제를 해결한다.
  • 안전하다.
• 단점
  • 암호화, 복호화 과정에서 계산이 들어가서 느리다.

2. 난수 발생의 4가지 형태

• 난수의 고려사항
  1. 주기
  2. 복잡성

1. bit stream cipher
   • 암호 키만으로 난수를 발생시킨다.
2. stream cipher
   • 평문과 암호 키를 조합하여 난수를 발생시킨다.
3. 비선형 stream cipher
   • 타원 곡선 암호와 같이 비선형적인 함수로 난수를 발생시킨다. 이때 키가 2개 이상이 나올 수 있다.
4. output feedback stream cipher
   • 암호 문을 다음 난수 발생 시 사용한다.

4. Stream 암호

1. Stream 암호

1. 암호화의 단위가 임의의 bit 또는 character이다.
   • 최근에 character는 거의 쓰이지 않는다. 대부분 bit 또는 byte를 사용한다.
2. 평문의 bit 또는 character가 암호화됨에 따라 상이한 암호화 함수를 적용한다.
   • 송수신자 간 키의 사전 분배
3. 평문, 비밀 키, 현재 스트림 암호 시스템의 상태와 연동하여 동작을 수행한다.
   • 입출력 피드백
4. 비밀 키와 현재 상태 변수로부터 키 스트림이 생성된다.
   • OTP

2. Stream 암호의 안정도 해석

1. 키 수열 주기
2. 무작위성과 다음 발생될 비트 예상 어려움
3. 선행복잡도의 빈약

• 유사 난수열: Golomb의 공리계
  1. 매 주기마다 발생하는 1의 개수와 0의 개수는 1이 바람직하다.
  2. 00 또는 11과 같이 반복되는 연속적인 값의 길이는 짧은 것이 자주 나타는 것이 바람직하다.
  • 예시
    • 다음의 수열은 유사 난수열로 볼 수 있는가?
      • 0 1 1 0 0 1 0 0 0 1 1 1 0 0 1→ 0의 개수: 8개, 1의 개수 7개 ⇒ 바람직
      • → {0}, {1, 1}, {0, 0}, {1}, {0, 0, 0}, {1, 1, 1}, {0, 0}, {1} ⇒ 바람직
• 공개 키 암호의 수학적 배경
  1. RSA: 소인수 분해의 어려움에 기반을 둠
  2. Diffie-Hellman 기법: 이산대수 문제의 어려움에 기반을 둠
  3. 타원 곡선 암호
  4. 확률 암호

5. RSA

MIT 대학의 Rivest, Shamir, Aldemem 등이 개발하여 각 이름의 첫 글자를 딴 RSA로 불리게 되었다.

특징

1. 소인수 분해의 어려움에 기반을 둔 암호 알고리즘이다.
2. 키의 길이와 평문의 길이가 가변적이다.
   • 안정성 - 키의 길이가 길어야 안정적이다.
   • 효율성 - 키의 길이가 짧아아 효율적이다.
   • → 트레이드 오프이므로 상황에 맞게 설정
3. 키의 길이가 평문의 길이보다 길 수도 있다.
4. 수신 측이 주도하는 암호 방식이다(공개 키 - 개인 키)
   • 신용카드번호, 개인 식별번호, 전자 서명 등에 활용

암호화, 복호화 과정

• 암호문 $C =P^e\bmod{n}$
• 평문 $P=C^d\bmod{n}$
• 공개 키 - e와 n의 쌍
• 개인 키 - d와 n의 쌍

1. 키 생성 단계

1. 두 개의 소수 $p$와 $q$를 선정한다.
   • 이 소수들은 공개되지 않는다.
2. $p$와 $q$를 곱하여 $n$을 구한다.
3. 수신자는 $n$을 공개하고 $L=lcm(p-1, q-1)$을 구한다.
   • lcm은 두 수의 최소 공배수를 구하는 함수이다.
4. 수신자는 $n$과 서로소인 $E$를 선택하고 $D*E\bmod{L}=1$를 만족하는 $D$를 구한다.
   • 이때 $1<E<L$의 조건을 만족해야 한다.
   • 이때 $1<D<L$의 조건을 만족해야 한다.
5. 수신자는 4단계에서 계산한 ${n,E}$를 공개한다.

2. 암호화

송신 측은 평문 $P$에 공개 키 ${n,e}$를 이용하여 $C=P^e\bmod{n}$을 계산하여 암호문을 만든다.

3. 복호화

수신 측은 암호문 $C$를 이용하여 $P=C^d\bmod{n}$을 계산하여 평문을 구한다.

1. 키 생성 단계

1. 두 개의 소수 $p$와 $q$를 선정한다.
   • $p=17, q=19$
2. $p$와 $q$를 곱하여 $n$을 구한다.
   • $n=17*19=323$
3. 수신자는 $n$을 공개하고 $L=(p-1)(q-1)$을 구한다.
   • $L=lcm(17-1,19-1)=144$
4. 수신자는 $n$과 서로소인 $E$를 선택하고 $D*E\bmod{L}=1$를 만족하는 $D$를 구한다.
   • 이때 $1<E<L$의 조건을 만족해야 한다.
   • $E$의 후보는 여러 개가 있을 수 있다.
     • 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, ...
     • 이는 모두 소수처럼 보이지만 25처럼 아닌 것도 있으므로 주의한다.
   • 5로 선택하여 계산한다.
   • $D5\bmod{144}=1$이 되려면 $D5$가 145, 299, ...이 되어야 하고 145가 해당되므로 $D=29$이다.
5. 수신자는 4단계에서 계산한 ${n,E}$를 공개한다.
   • ${323, 5}$를 공개 키로 공개한다.
   • 개인 키 ${323,29}$는 절대 외부에 공개하서는 안된다.

2. 암호화

송신 측은 평문 $P$에 공개 키 ${n,e}$를 이용하여 $C=P^e\bmod{n}$을 계산하여 암호문을 만든다.

• 송신자는 보내고자 하는 평문 $P$를 위 공식을 사용해서 암호화하여 전송한다.
• $P=5$라고 한다면 $C=5^5\bmod{323}=218$, 즉 $P$에 대한 암호문 $C=218$로 전송한다.

3. 복호화

수신 측은 암호문 $C$를 이용하여 $P=C^d\bmod{n}$을 계산하여 평문을 구한다.

• 수신자는 받은 암호문 $C$를 위 공식을 사용해서 복호화하여 평문을 구한다.
• $P=218^{29}\bmod{323}=5$, 즉 $C$에 대한 평문 $P=5$로 구할 수 있다.
  • 작은 수로 직접 계산해보는 것을 추천한다. 실제로 218의 29승은 계산하기 어렵다.

정리

• 키 쌍
  • 공개 키: ${E,n}$
  • 개인 키: ${D,n}$
• 암호화
  • $C=P^E\bmod{n}$
  • 평문을 $E$제곱해서 $n$으로 나눈 나머지
• 복호화
  • $P=C^D\bmod{n}$
  • 암호문을 $D$제곱해서 $n$으로 나눈 나머지

6. 공개 키 암호에 대한 의문

1. 공개 키 암호는 대칭 암호보다 기밀성이 높은가?

비교할 수 없다. 키의 길이에 따라 기밀성의 정도는 달라지기 때문이다.

2. 256비트 길이의 키를 갖는 대칭 암호 AES와 1024비트 길이를 갖는 공개 키 암호 RSA 둘 중 비트 길이가 더 긴 RSA가 더 안전한가?

비교할 수 없다. 공개 키 암호의 키 길이와 대칭 키 암호의 키 길이를 직접 비교할 수 없다. 이는 단순한 문제가 아니다.

3. 공개 키 암호에 의해 대칭 암호는 사용하지 않게 되는 것인가?

아니다. 공개 키 암호는 안전하긴 하지만 속도가 대칭 키 암호에 비해 몇 백배나 느리다. 따라서 공개 키 암호는 긴 평문을 암호화하기에 적합하지 않다. 따라서 목적에 따라 맞는 암호 방식을 사용하는 편이 좋다.

4. RSA의 키 쌍을 계속 만들어나가면 더 이상 사용할 소수가 없어지는 것 아닌가? 또는 우연히 일치하게 될 가능성은?

전혀 그럴 일이 없다. 512비트로도 표현할 수 있는 소수의 수는 약 10의 150승이다. 세계 인구가 100억명이라고 하고 각 개인이 1초에 100억개의 키 쌍을 만든다고 하자. 100억년 걸리면 몇 개의 키 쌍을 만들어낼까? 1년동안 만든다고 하면 1년을 초로 바꿔 365246060=31,622,400 초 이므로 100억명100억개31,622,400초100억년=31,622,400,000,000,000,000,000,000,000,000,000,000 개이다. 이는 10의 39제곱보다 적은 수이다. 즉 10의 150승에 훨씬 미치지 못하는 수이다. 이제 질문에 답을 한다면 소수가 없어질 일 또한 없으며 우연히 일치하게 될 가능성 또한 없다고 생각하면 된다.

5. RSA의 소인수 분해 문제

1. RSA로 암호화할 때 키 쌍의 큰 수에 대한 소인수 분해를 할 필요가 있나?
2. → 없다. 소인수 분해는 $n$으로부터 $p,q$를 구하려고 할 때 뿐이다.
3. RSA를 해독하는 방법은 큰 수를 소인수 분해하면 되는 것인가?
4. → 분명 RSA는 소인수 분해를 고속으로 하는 방법이 나온다면 해독된다. 이는 2004년에 알렉산더 메이가 수학적으로 증명했다. 그러나 반드시 RSA의 해독 방법이 소인수 분해인 것은 아닐 수도 있다.

6. 큰 수가 소인수 분해되지 않으려면 n은 길이가 얼마나 되어야 하는가?

아무리 비트 수가 크더라도 언제가는 소인수 분해가 된다. 따라서 충분히 큰 수를 사용해야 한다. RSA 사에 제시한 704비트 짜리 큰 수(212자리 10진수)는 아직 소인수 분해되지 않았다.

7. 암호의 위태성

NIST SP800-57의 보고에 의하면, 컴퓨터 계산 능력의 발달로 현재까지 안전했던 암호가 해독돠는 것을 암호의 위태성이라고 함

• 1024 비트의 RSA는 새로 키를 발급할 때 사용되지 않는다.
• 2048 비트의 RSA는 2030년 이후로는 새로 키를 발급할 때 사용되지 않는다.
• 4096 비트의 RSA는 2031년 이후로도 신규 키를 발급할 때 사용될 수 있다.

7. 대칭 키 암호와 공개 키 암호의 비교