RSA 암호화 기법 (2): 왜 해독하기 어려운가?

지난 시간에는 RSA 암호 기법 그 자체를 구현하는 실습을 해보았다.

이번엔 좀 더 원론적인 얘기를 할 것이다.

---

그저 있어보이게 3D로 기울여쓴 R S A. 출처: LG CNS. https://www.lgcns.com/blog/cns-tech/security/16037/

RSA 암호는 보안이 특정 문제를 해결하는 수학적 어려움에 의존하기 때문에 해독하기가 어렵습니다. 이러한 문제는 현재 기술을 사용하여 적정한 시간 내에 해결하기가 계산적으로 불가능합니다. RSA가 보안이 뛰어난 주요 이유는 다음과 같습니다.

1. 큰 숫자를 소인수분해하는 어려움

• 핵심 원칙: 
  • RSA의 보안은 두 개의 큰 소수(p 및 q)의 곱인 매우 큰 수(n)를 소인수분해하는 어려움에 기반합니다.
• 어려운 이유:
  • 큰 숫자(예: 2048비트 정수)를 소수 구성요소로 소인수분해하는 것은 계산 시간이 많이 드는 작업입니다.
  • 기존 컴퓨팅에는 이렇게 큰 숫자를 적당한 시간 내에 소인수분해하는 효율적인 알고리즘이 없습니다.
• 예시:
  • 2048비트 RSA 키의 경우 n은 십진수로 약 617개 자릿수를 갖습니다. 가장 빠른 알고리즘이라도 기존 컴퓨팅 성능으로 'n'을 소인수분해하려면 수십억 년이 필요합니다.

2. 키 크기의 유연성

• RSA 키 길이가 커짐에 따라 이를 해독하는 데 필요한 계산 노력은 선형이 아닌 기하급수적으로 증가합니다.
• 예시:
  • 1024비트 RSA 키는 최신 공격 기법에는 약한 것으로 간주됩니다.
  • 2048비트 RSA 키는 대부분의 최신 애플리케이션에서 안전하다고 평가합니다.
  • 4096비트 RSA 키는 가까운 미래에도 안전한 것으로 간주됩니다.
• RSA 키는 임의로 크게 만들어 공격자의 계산 난이도를 높일 수 있습니다. 향후 컴퓨팅 성능이 향상되면 키 크기를 늘리면 보안을 유지할 수 있습니다.

3. 공개 키와 개인 키 관계

• RSA 암호화 및 복호화에는 모듈식 지수화가 포함됩니다. 이는 한 방향(암호화/복호화)으로 계산하는 것은 간단하지만 개인 키 없이는 역방향으로 계산하는 것이 불가능합니다.
• 구체적으로, 공개 키(e, n)는 개인 키 구성 요소(p 및 q)에서 파생되지만, n으로부터 p 와 q를 소인수분해 해내지 않는 이상, 공개 키를 아는 것만으로는 개인 키(d)를 추론할 수 있는 정보가 충분하지 않습니다.
• RSA의 모듈식 산술은 'd'를 모르면 암호문을 해독하거나 서명을 위조하는 것이 불가능함을 보장합니다.
  • 정수론의 기본정리. 소인수분해의 유일성.

4. 패딩 구성표 사용 (실사용시)

• RSA 구현은 보안 패딩 방식(예: PKCS1_OAEP)을 사용하여 공격을 더욱 어렵게 만듭니다.
• 이러한 패딩 구성표는 RSA의 수학적 기반의 일부 약점이 악용되더라도 메시지의 실제 콘텐츠가 보호되도록 보장합니다.

5. 무차별 대입 공격에 대한 저항

• 'n'의 가능한 모든 요소를 ​​시도하여 RSA 키를 무차별 대입하는 것은 다음과 같은 이유로 비실용적입니다.
  • 가능성의 수는 천문학적으로 많습니다.
  • 2048비트 RSA 키의 경우 약 2^{2048} 개의 인자가 있을 수 있는데, 이는 상상할 수 없을 만큼 큰 숫자입니다.

6. 양자 컴퓨터로부터의 보호

• RSA는 기존 컴퓨터에 대해 안전하지만 충분히 큰 양자 컴퓨터의 Shor의 알고리즘은 많은 수를 효율적으로 소인수분해할 수 있습니다.
• 그러나 이 정도 수준의 계산이 가능한 실용적인 양자컴퓨터는 현재 아직은 존재하지 않습니다. 현재 양자 컴퓨터는 실제 RSA 애플리케이션에 사용되는 숫자를 소인수분해하기에는 큐비트가 너무 적고 노이즈가 너무 많습니다.

---

RSA를 깨뜨리기 쉬워질 이유?

위에서 살펴본대로 암호 방식의 견고성에도 불구하고 RSA가 해독될 수 있는 특정 시나리오가 있습니다.

• 작은 키 크기:
  • 1024비트보다 작은 키는 최신 컴퓨터의 소인수분해에 취약합니다.
• 부실한 구현:
  • 키 생성의 약한 무작위성, 잘못된 패딩 또는 부적절한 키 처리로 인해 RSA가 공격에 노출될 수 있습니다.
• 사이드 채널 공격:
  • RSA 구현은 때때로 수학 자체보다는 키가 실제로 처리되는 방식을 이용하는 타이밍 공격이나 전력 분석과 같은 사이드 채널 공격에 취약합니다.
• 양자 컴퓨팅의 발전: 
  • 충분히 강력한 양자 컴퓨터가 개발되면 Shor의 알고리즘을 사용하여 많은 수를 효율적으로 소인수분해하여 RSA를 안전하지 않게 만들 수 있습니다.

---

요약

RSA는 숫자를 소인수분해하는 방법이 어렵다는 견고함을 기반으로 하고 안전한 구현 방식으로 지원되기 때문에 해독하기 어렵습니다. 현재 기술로 RSA를 깨는 데 필요한 엄청난 계산 복잡성은 특히 적절한 키 크기 및 패딩 체계와 함께 사용할 때 안전성을 보장합니다. 그러나 컴퓨팅 능력이 발전함에 따라 이러한 보안 수준을 유지하기 위한 암호화 표준도 발전해야 합니다.