맨위로가기

RSA 암호

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

RSA 암호는 1977년 론 리베스트, 아디 샤미르, 레너드 애들먼에 의해 개발된 공개 키 암호 방식이다. 키 생성, 키 배포, 암호화 및 복호화 단계를 거치며, 매우 큰 양의 정수를 이용하여 암호화 및 복호화를 수행한다. RSA의 보안은 큰 수의 소인수분해 문제의 어려움에 기반하며, 키 길이에 따라 안전성이 달라진다. 암호화, 복호화뿐만 아니라 디지털 서명에도 사용될 수 있으며, 패딩 방식을 통해 다양한 취약점을 보완한다.

더 읽어볼만한 페이지

  • 암호학 - 양자 컴퓨터
    양자 컴퓨터는 양자역학적 현상을 이용하여 정보를 처리하는 컴퓨터로, 큐비트를 통해 0과 1을 동시에 표현하여 특정 연산에서 기존 컴퓨터보다 빠른 속도를 보이며 암호 해독, 신약 개발 등 다양한 분야에 혁신을 가져올 것으로 기대된다.
  • 암호학 - 암호화
    암호화는 정보를 보호하기 위해 사용되는 기술로서, 단순한 문자 치환 방식에서 시작하여 현대에는 강력한 암호화 표준과 다양한 종류로 발전했으며, IT 시스템 전반에 적용되지만, 사이버 공격과 양자 컴퓨팅의 발전에 대한 대응이 필요한 기술이다.
RSA 암호

2. 역사

휘트필드 디피와 마틴 헬만이 1976년에 공개 키 암호라는 개념을 처음 발표했다.[4] 이듬해인 1977년, 론 리베스트, 아디 샤미르, 레오나드 애들먼이 RSA 암호 방식을 발명했다.[7] RSA라는 이름은 이들 세 명의 성의 첫 글자를 따서 지어졌다.

아디 샤미르, RSA 공동 발명가 (다른 발명가는 론 리베스트와 레오나드 애들먼)


1983년, RSA 암호 알고리즘은 미국에서 특허를 취득했다.[7] 그러나 특허 기간은 17년으로, 2000년 9월에 만료되어 현재는 누구나 자유롭게 사용할 수 있게 되었다.[14]

한편, 1973년 영국 정부통신본부(GCHQ)의 클리포드 콕스가 내부 문서에서 RSA와 유사한 시스템을 설명한 바 있다.[8] 하지만 이는 기밀로 유지되다가 1997년에야 공개되었다.

3. 방식

RSA는 두 개의 키를 사용하는 암호화 방식이다. 여기서 키는 메시지를 열고 잠그는 상수를 의미한다. 공개키는 모두에게 알려져 메시지를 암호화하는 데 사용되며, 암호화된 메시지는 개인키를 가진 사람만이 복호화하여 열어볼 수 있다.

RSA는 소인수 분해의 어려움을 기반으로 설계되어, 공개키만으로는 개인키를 알아내기 어렵다. 이는 의미론적으로 안전한 암호화 시스템을 보장한다.

예를 들어, B가 A에게 메시지를 보낼 때, B는 A의 공개키(열린 자물쇠)로 메시지를 암호화(봉인)하고, A는 자신의 개인키(열쇠)로 메시지를 복호화(열람)하는 방식이다. 중간에 메시지를 가로채더라도 개인키가 없으면 내용을 알 수 없다.

하지만, 실제로는 수신측의 공개키만으로 암호화하는 경우는 드물다. 송수신 양측의 키쌍을 사용하는 방법이 일반적인데, A의 개인키로 암호화 -> B의 공개키로 암호화 한 메시지를 전달하고, B의 개인키로 복호화 -> A의 공개키로 복호화하는 방식이다.

RSA는 키 생성, 암호화, 복호화의 3가지 알고리즘으로 정의된다.

3. 1. 키 생성

RSA 암호에서 키 생성은 다음과 같은 단계를 거쳐 이루어진다.

1. 두 개의 서로 다른 소수 ''p''와 ''q''를 선택한다.

  • 이 두 소수는 무작위로 선택되며, 크기가 비슷하고 서로 충분히 큰 차이가 나야 소인수 분해가 어렵다.[2]
  • ''p''와 ''q''는 비밀로 유지한다.

2. 두 수를 곱하여 ''N'' = ''pq''를 계산한다.

  • ''N''은 공개 키와 개인 키 모두에서 모듈러 산술 연산의 모듈러스로 사용된다.
  • ''N''의 비트 단위 길이는 키 길이를 나타낸다.
  • ''N''은 공개 키의 일부로 공개된다.

3. 카마이클의 토션 함수 ''λ''(''N'')을 계산한다. ''p''와 ''q''가 소수이므로, ''λ''(''N'') = lcm(''p'' − 1, ''q'' − 1)이다.

  • lcm(''a'', ''b'') = 이므로, 유클리드 호제법을 통해 최소공배수를 계산할 수 있다.
  • ''λ''(''N'')은 비밀로 유지한다.

4. 1 < ''e'' < ''λ''(''N'')이고, ''e''와 ''λ''(''N'')이 서로소인 정수 ''e''를 선택한다.

  • ''e''는 짧은 비트 길이와 작은 해밍 무게를 가지는 것이 암호화 효율을 높인다. 가장 일반적인 ''e'' 값은 65537이다.[15]
  • ''e''는 공개 키의 일부로 공개된다.

5. 확장 유클리드 알고리즘을 사용하여 ''d'' × ''e''를 ''λ''(''N'')로 나누었을 때 나머지가 1인 정수 ''d''를 계산한다. (''d'' ''e'' ≡ 1 (mod ''λ''(''N''))).

  • ''d''는 ''λ''(''N'')을 모듈로 한 ''e''의 모듈러 역수이다.
  • 베주 항등식에 따라, ''d''는 확장 유클리드 알고리즘을 사용하여 효율적으로 계산할 수 있다.
  • ''d''는 개인 키 지수로, 비밀로 유지한다.


공개 키는 ''N''과 ''e''로 구성되며, 개인 키는 ''N''과 ''d''로 구성된다. ''p'', ''q'', ''λ''(''N'')는 ''d''를 계산하는 데 사용되므로 비밀로 유지해야 하며, ''d''가 계산된 후에는 모두 삭제해도 안전하다.[16]

원래 RSA 논문에서는[2] 오일러의 토션 함수 ''φ''(''n'') = (''p'' − 1)(''q'' − 1)을 사용하여 개인 지수 ''d''를 계산했지만, PKCS#1과 같은 현대 RSA 구현에서는 ''λ''(''n'')을 사용한다. ''φ''(''n'')은 항상 ''λ''(''n'')으로 나누어지므로, 두 방법 모두 작동한다. 그러나 ''φ''(''n'')을 사용하면 때때로 필요한 것보다 더 큰 ''d'' 값이 생성될 수 있다. FIPS 186-4(섹션 B.3.1)와 같은 일부 표준에서는 ''d'' < ''λ''(''n'')을 요구할 수 있으며, 이를 만족하지 않는 "과도한" 개인 지수는 ''λ''(''n'')을 모듈로 하여 작고 동등한 지수를 얻을 수 있다.

(''p'' − 1)과 (''q'' − 1)의 공통 인수는 ''n'' − 1 = ''pq'' − 1 = (''p'' − 1)(''q'' − 1) + (''p'' − 1) + (''q'' − 1)의 인수 분해에 존재하므로,[17] (''p'' − 1)과 (''q'' − 1)은 2 외에 매우 작은 공통 인수만 가져야 한다.[2][18][19][20]

원래 RSA 논문에서는 ''d''를 선택하고 ''e''를 계산했지만, 현대 구현에서는 ''e''를 선택하고 ''d''를 계산하는 방식을 사용한다. 선택된 키는 작을 수 있지만, 계산된 키는 그렇지 않으므로, RSA 논문의 알고리즘은 복호화를 최적화하는 반면, 현대 알고리즘은 암호화를 최적화한다.[2][21]

3. 2. 암호화

B가 ''M''이란 메시지를 A에게 보내고 싶어할 때, B는 ''M''을 ''N''보다 작은 숫자 m으로 변환한다. (이 변환법(padding scheme)은 A에게도 미리 알려져 있어야 한다. 예를 들어, 메시지를 토막내어 하나의 메시지가 일정 수의 비트를 넘지 않게 하는 방법이 있다. 하지만 실제로는 이중보안을 위해 더욱 복잡한 변환법이 사용된다.) 그리고 B는 A의 공개키 <''N'', ''e''>를 획득하고, 다음과 같이 ''c''를 계산한다.

: c = m^e \mod{N}

그리고 이 ''c''를 A에게 보낸다.[1]

밥(Bob)이 앨리스(Alice)의 공개 키를 얻은 후, 앨리스에게 메시지 M을 보낼 수 있다.

이를 위해, 밥은 먼저 M (엄밀히 말하면, 패딩되지 않은 평문)을 정수 m (엄밀히 말하면, 패딩된 평문)으로 변환하는데, 이는 합의된 가역적 프로토콜인 패딩 방식을 사용하여 0 \le m < n을 만족한다. 그런 다음 앨리스의 공개 키 e를 사용하여 암호문 c를 계산하는데, 이는 다음과 같다.

c \equiv m^e \pmod{n}.

이것은 모듈러 지수 연산을 사용하여 매우 큰 숫자에서도 상당히 빠르게 수행될 수 있다. 밥은 그런 다음 c를 앨리스에게 전송한다.

a \in \mathbb{Z}_n로, a를 암호화 대상인 평문으로 한다. b = a^e \mod n \in \mathbb{Z}_n을 계산하고, b를 평문 a의 암호문으로 한다.

3. 3. 복호화

RSA영어는 두 개의 키를 사용한다. 공개키는 모두에게 알려져 있으며 메시지를 암호화하는데 쓰인다. 암호화된 메시지는 개인키를 가진 사람만이 복호화하여 열어볼 수 있다.[1]

A는 B에게서 암호화된 메시지 ''c''를 건네받았고, ''N''과 ''d''를 알고 있다. 다음 식을 통해 ''m''을 찾는다.[1]

: m = c^d \mod{N}

''m''을 가지고 A는 ''M''을 찾아낼 수 있는 방법을 알고 있다.[1]

앨리스는 개인 키 지수 ''d''를 사용하여 다음을 계산하여 ''c''에서 ''m''을 복구할 수 있다.[1]

:c^d \equiv (m^e)^d \equiv m \pmod{n}.

''m''이 주어지면, 패딩 방식을 되돌려 원래 메시지 ''M''을 복구할 수 있다.[1]

3. 4. 증명

페르마 소정리 또는 오일러 정리를 이용하여 복호화가 가능함을 증명할 수 있다.

  • 페르마 소정리를 이용한 증명[55]


:c^d \equiv (m^e)^d \equiv m^{ed} \equiv m^{k(p-1)(q-1)+1} \equiv m \pmod{N}.

마지막 등식이 성립하는 이유는 다음과 같다. 위의 식에서 ''mod N'' 대신 ''mod p''를 사용하여 풀이했을 때,

:m^{k(p-1)(q-1)+1} \equiv (m^{p-1})^{k(q-1)}m \pmod{p}

가 된다. ''p''가 소수이므로, m이 p의 배수가 아니라면 서로소이므로 페르마 소정리를 다음 식과 같이 적용할 수 있다.

만약 m이 p의 배수라면 양변이 p의 배수이므로 0과 동치가 되어 역시 다음 식이 성립된다.

:(m^{p-1})^{k(q-1)}m \equiv 1^{k(q-1)}m \equiv m \pmod{p}

''mod q''를 사용하여도 똑같은 풀이가 가능하다. ''N'' = ''pq'' 이므로, ''mod N''에도 같은 식이 성립하게 된다.

  • 오일러 정리를 이용한 증명


:N=pq (두 개의 서로 다른 소수 ''p''와 ''q''의 곱 ''N'')과 ed\equiv 1\pmod{\phi (n)} 를 만족하는 양의 정수 ''e''와 ''d''를 이용해 m^{ed}\equiv m\pmod{n}를 보이고자 한다.

''e''와 ''d''가 양수이기 때문에 ed=1+h\phi(n)라고 쓸 수 있다.(''h''는 음이 아닌 정수)

''m''을 ''n''과 서로소라고 가정하면, m^{ed}=m^{1+h\phi(n)}=m(m^{\phi(n)})^h\equiv m(1)^h\equiv m\pmod{n} 이 성립한다. 끝에서 두번째 합동식 m(m^{\phi(n)})^h\equiv m(1)^h는 오일러 정리에 따른 것이다.

좀 더 일반적으로 ed\equiv1 \pmod{\lambda (n)}를 만족하는 임의의 ''e''와 ''d''에 대해서도, ''n''과 서로소인 ''m''은 m^{\lambda (n)}\equiv1\pmod{n}라고 명시된 카마이클의 '오일러 이론의 일반화'를 통해 같은 결론을 도출할 수 있다.

''m''이 ''n''과 서로소가 아닌 경우 이 이론은 성립하지 않는다. 매우 드문 확률(\frac{1}{p}+\frac{1}{q}-\frac{1}{pq}의 비율)이지만 이 경우에도 합동은 성립한다. m\equiv0\pmod{p}나 m\equiv0\pmod{q}인 경우, 이전의 증명으로 해결할 수 있다.

4. 예제

(오일러 피 함수는 N보다 작은 N과 서로소인 수의 개수를 의미한다.)\phi(3233) = (61 - 1)(53 - 1) = 312041 < e < 3120 범위에서 \phi(N)과 서로소인 임의의 숫자 e를 선택한다.e = 175e\text{ (mod }\phi(N)\text{)}에 대한 곱의 역원, 즉 e d \text{ (mod }\phi(N)\text{)}=1을 만족하는 숫자 d를 계산한다.17 \times 2753 = 46801 \equiv 1 \text{ (mod 3120) }
d = 2753



공개 키는 (N = 3233, e = 17)이며, 평문 m은 m^{17}\text{ (mod }3233\text{)} 함수를 통해 암호화된다.

개인 키는 (N = 3233, d = 2753)이며, 암호문 c는 c^{2753}\text{ (mod }3233\text{)} 함수를 통해 복호화된다.

예를 들어, 평문 m = 65는 다음과 같이 암호화할 수 있다.

:c = 65^{17}\text{ (mod }3233\text{)} = 2790

암호문 c = 2790은 다음과 같이 복호화할 수 있다.

:m = 2790^{2753}\text{ (mod }3233\text{)} = 65

실제 프로그래밍 구현 시에는 큰 수의 연산 부담을 줄이기 위해 중국인의 나머지 정리를 기반으로 한 효율적인 복호화 방법을 사용한다. OpenSSL, Java, .NET 등 주요 암호화 라이브러리들이 이 방식을 채택하고 있다.[27]

이 방법은 p, q 값을 보존하고, d_p, d_q, q_{Inv} 값을 미리 계산하여 복호화 과정에서 활용한다.



암호문은 다음과 같이 복호화된다.

이 방식은 p, q처럼 작은 수를 사용하여 모듈러 연산을 수행하므로 연산 속도가 빨라진다. 또한, m = m_2 + h \times q 의 최대값이 pq보다 작기 때문에, 평문을 얻기 위한 추가적인 나눗셈 과정이 필요 없다.

5. 서명

RSA 암호는 암호화뿐만 아니라 디지털 서명에도 사용될 수 있다. 앨리스가 밥에게 서명된 메시지를 보내려면, 먼저 메시지의 해시 값을 생성하고, 이를 자신의 개인 키 d로 제곱(모듈로 n)하여 "서명"을 만든다. 이 서명은 메시지에 첨부되어 밥에게 전송된다.

밥은 메시지를 받으면 앨리스의 공개 키 e를 사용하여 서명을 검증한다. 서명을 e 제곱(모듈로 n)하고, 결과 해시 값을 메시지의 해시 값과 비교한다. 두 값이 일치하면, 밥은 메시지가 앨리스에게서 왔고, 전송 중에 변경되지 않았음을 확인할 수 있다.

이는 지수 법칙에 따라

h = \operatorname{hash}(m),

(h^e)^d = h^{ed} = h^{de} = (h^d)^e \equiv h \pmod{n}.

이 성립하기 때문이다. 즉, 개인 키를 사용하여 서명을 생성하고, 공개 키를 사용하여 검증할 수 있다.

RSA 암호에서 서명은 다음과 같은 방식으로 이루어진다.[1]



RSA 암호는 평문과 암호문의 정의역이 같기 때문에, 비밀 키를 사용하여 임의의 문서에 대한 서명 값을 생성하고, 공개 키를 사용하여 이 서명 값을 ''암호화''하여 원래 문서와 비교함으로써 서명을 검증할 수 있다. 하지만, 실제로는 RSA 암호의 보안 취약점 때문에 해시 함수와 패딩을 함께 사용하여 서명 위조를 방지한다.[1]

패딩을 포함한 서명 방식의 예로는 RSA_PSS with SHA-1 등이 있다.[1]

6. 패딩

실제 RSA 구현에서는 보안을 위해 패딩을 사용한다. 값을 암호화하기 전에 무작위화된 패딩을 삽입하여, 그 값이 안전하지 않은 평문의 범위에 속하지 않도록 하고, 패딩된 메시지가 다양한 가능한 암호문 중 하나로 암호화되도록 한다.[25]

PKCS#1과 같은 표준은 RSA 암호화 전에 메시지를 안전하게 패딩하도록 설계되었다. 초기 버전(1.5 버전까지)은 실질적인 적응형 선택 암호문 공격에 취약하다는 것이 밝혀졌고, 특정 유형의 메시지에 대해 충분한 보안을 제공하지 못한다는 것도 발견되었다.[25] 이후 버전에는 이러한 공격을 방지하는 최적 비대칭 암호화 패딩(OAEP)이 포함되었다. 따라서 OAEP는 모든 새로운 애플리케이션에서 사용해야 하며, PKCS#1 v1.5 패딩은 가능한 한 교체해야 한다.

OAEP와 RSA 암호를 함께 사용하는 것을 RSA-OAEP라고 부르기도 한다. RSA-OAEP는 공개키 암호에서 가장 높은 안전성인 "적응적 선택 암호문 공격에 대한 식별 불가능성"을 갖는 것으로 나타났다.

7. 안전성

RSA 암호 시스템의 보안은 큰 수의 인수분해 문제와 RSA 문제라는 두 가지 수학적 문제의 어려움에 기반한다. RSA 암호문의 완전한 해독은 이 두 문제가 모두 어렵다는 가정 하에 불가능한 것으로 알려져 있다.[28]

RSA 문제는 합성수 $n$을 모듈로로 하는 $e$ 제곱근을 구하는 문제로 정의된다. 즉, 주어진 RSA 공개 키 $(n, e)$와 암호문 $c$에 대해, $c \equiv m^e \pmod n$을 만족하는 메시지 $m$을 찾는 것이다. 현재 RSA 문제를 해결하는 가장 유망한 방법은 모듈러스 $n$을 인수분해하는 것이다. 만약 공격자가 소인수 $p$와 $q$를 알아낼 수 있다면, 비밀 지수 $d$를 계산하고 암호문 $c$를 복호화할 수 있다.

하지만 고전적인 컴퓨터에서 큰 정수를 인수분해하는 효율적인(다항 시간) 알고리즘은 아직 발견되지 않았으며, 이러한 알고리즘이 존재하지 않는다는 증명도 없다. 정수 인수분해 문제에 대한 자세한 내용은 해당 문서를 참조하면 된다.

쇼어는 1994년에 양자 컴퓨터가 다항 시간 안에 인수분해를 할 수 있음을 보였고, 이는 양자 컴퓨터가 실용화되면 RSA 암호가 깨질 수 있음을 의미한다. 쇼어의 알고리즘을 참조하면 된다.

현재까지 공개적으로 알려진 가장 큰 RSA 숫자의 인수분해는 829비트(250자리, RSA-250)였다.[31] 이 인수분해에는 최첨단 분산 구현을 통해 약 2,700 CPU년이 소요되었다.

일반적으로 RSA 키는 1024~4096비트 길이를 사용한다. RSA 시큐리티(RSA Security)는 2003년에 1024비트 키가 2010년까지 해독될 가능성이 있다고 추정했지만,[32] 2020년 현재 이러한 키를 해독할 수 있는지는 알려져 있지 않다. 현재 권장되는 최소 키 길이는 2048비트이다.[33]

7. 1. 취약점 및 공격

RSA 암호는 여러 가지 취약점과 공격 방법에 노출될 수 있다.

이러한 공격을 방지하기 위해 실제 RSA 구현에서는 패딩을 사용한다.
부채널 공격
잘못된 키 생성 및 난수 생성 문제

8. 구현

RSA 암호를 실제로 구현할 때는 PRNG 강도, 허용 가능한 공개 지수 등 고려해야 할 사항이 많아 구현이 어렵다. 책 《Go를 사용한 실용 암호학》에서는 가능하다면 RSA를 피하는 것을 제안한다.[45]

RSA를 지원하는 암호화 라이브러리는 다음과 같다.

라이브러리
보탄
바운시 캐슬
크립트립
크립토++
Libgcrypt
네틀
OpenSSL
wolfCrypt
GnuTLS
mbed TLS
LibreSSL


9. 성능

보안 매개변수가 1024인 경우, n은 1024비트라는 큰 자릿수의 수가 되며, d도 n과 거의 같은 자릿수의 수가 된다. a = b^d \bmod n을 계산하기 위해, 이진법 알고리즘을 사용하면, 잉여 곱셈(1024\mathrm {bit} \times 1024\mathrm{bit})을 1500회 정도 반복함으로써 실현할 수 있다. 이는 상당한 계산 시간을 필요로 하므로, 중국인의 나머지 정리를 사용하여,

:\begin{align}

ap &= b^{d \bmod \lambda(p)} \bmod p \\

aq &= b^{d \bmod \lambda(q)} \bmod q \\

a' &= ap (q^{-1} \bmod p) q + aq (p^{-1} \bmod q) p

\end{align}

로 구하는 경우가 있다.

큰 자릿수의 수를 다룰 경우, 확실하게 소수임을 보장하는 정수를 찾는 것은 쉽지 않다. 이 때문에 실제로는 소수라고 단언할 수는 없지만, 소수일 가능성이 매우 높은 자연수를 사용한다. 이러한 자연수의 생성은 밀러-라빈 테스트와 같은 확률적 소수 판별법에 의해 빠르게 수행할 수 있다. 확률적 소수 판별법을 통과한 자연수를 확률적 소수라고 한다. 확률적 소수에는 소수 외에 유사 소수가 포함되지만, 그 확률은 판별 횟수를 늘림으로써 매우 낮출 수 있다.

2002년 8월, 인도 공과대학의 아그라왈 등이 소수 판별을 다항 시간 내에 수행하는 AKS 소수 판별법을 발표했으나, 이는 다항식의 차수가 너무 높아 느리므로 아직 RSA 키 생성에 실용적으로 사용하기에는 부족하다.

10. RSA 암호와 소인수분해 문제의 관계

RSA 암호는 소인수분해 문제와 밀접하게 관련되어 있다. RSA 암호의 안전성은 큰 수를 소인수분해하는 것이 어렵다는 것에 기반한다.

RSA 암호 시스템은 두 개의 큰 소수 p와 q를 곱하여 N을 만들고, (p-1)과 (q-1)의 곱보다 작고 서로소인 정수 e를 선택하여 공개키 (N, e)를 생성한다. 비밀키 d는 확장된 유클리드 호제법을 통해 계산된다. 여기서 p와 q의 보안이 매우 중요하며, 공개키와 개인키가 생성된 후에는 이 두 숫자를 안전하게 지우는 것이 좋다.

RSA 암호의 해독은 RSA 문제와 큰 수의 인수분해 문제, 이 두 가지 수학적 문제의 어려움에 기반한다. 만약 이 문제들을 효율적으로 해결할 수 있는 알고리즘이 존재하지 않는다면, RSA 암호문의 완전한 해독은 불가능하다고 여겨진다.[28]

RSA 문제는 주어진 합성수 n을 모듈로 하는 e 제곱근을 구하는 문제이다. 즉, `c ≡ m^e (mod n)`을 만족하는 m을 찾는 것이다. (여기서 (n, e)는 RSA 공개키, c는 RSA 암호문이다.) 현재 RSA 문제를 해결하는 가장 유망한 방법은 n을 인수분해하는 것이다. 만약 공격자가 n을 p와 q로 인수분해할 수 있다면, 비밀 지수 d를 계산하여 암호문 c를 복호화할 수 있다.[28]

현재까지 고전적인 컴퓨터에서 큰 정수를 다항 시간 안에 인수분해하는 방법은 발견되지 않았지만, 이것이 불가능하다는 증명도 없다. 정수 인수분해를 참고하면, 이 문제에 대한 더 자세한 논의를 볼 수 있다.

피터 쇼어가 1994년에 발표한 쇼어의 알고리즘에 따르면, 양자 컴퓨터가 실용화되면 다항 시간 안에 소인수분해가 가능해져 RSA 암호가 깨질 수 있다.

RSA 암호가 선택 평문 공격에 대해 완전 해독될 수 없다는 것은 RSA 가설과 동치이다. 그러나 RSA 암호를 역산하는 것이 인수분해만큼 어렵다는 증거는 아직 발견되지 않았다.[30]

암호 이론 분야에서는 다항 시간 내에 해독할 수 없는 암호 방식을 안전하다고 정의한다. 현재까지 알려진 바로는 RSA 암호는 이러한 의미에서 안전하다고 여겨지며, 그 반증은 없다.

10. 1. 소인수분해 가능한 범위

RSA 암호 시스템의 보안은 큰 수의 인수분해 문제와 RSA 문제라는 두 가지 수학적 문제에 기반을 두고 있다. 이 두 문제가 어렵다는 가정 하에 RSA 암호문의 완전한 해독은 불가능하다고 여겨진다.[28]

RSA 문제는 합성수 n을 모듈로로 하는 e 제곱근을 구하는 문제로 정의된다. 즉, 주어진 RSA 공개 키 (n, e)와 암호문 c에 대해 `c ≡ m^e (mod n)`을 만족하는 m을 찾는 것이다. 현재 RSA 문제를 해결하는 가장 유망한 방법은 n을 인수분해하는 것이다. 공격자가 n을 p와 q로 인수분해하면, `lcm(p-1, q-1)`을 계산하여 비밀 지수 d를 알아내고 c를 복호화할 수 있다.[28]

고전적인 컴퓨터에서 큰 정수를 인수분해하는 다항 시간 알고리즘은 아직 발견되지 않았지만, 존재하지 않는다는 것도 증명되지 않았다. 다중 다항식 2차 체(MPQS)와 같은 알고리즘을 사용하여 공개 모듈러스 n을 인수분해할 수 있다.

1999년에는 수백 대의 컴퓨터를 사용하여 약 7개월 만에 RSA-512를 인수분해하는 데 성공했다.[29] 2009년에는 벤자민 무디가 공개 소프트웨어와 데스크탑 컴퓨터를 사용하여 73일 만에 512비트 RSA 키를 인수분해했다.[29] 2020년 현재까지 공개적으로 알려진 가장 큰 RSA 숫자는 RSA-250으로, 829비트(250자리)이며, 인수분해에 약 2,700 CPU년이 걸렸다.[31]

RSA 키는 일반적으로 1024~4096 비트 길이를 사용한다. 2003년 RSA 시큐리티는 1024비트 키가 2010년까지 해독될 가능성이 있다고 추정했지만,[32] 2020년 현재 이러한 키를 해독할 수 있는지는 알려져 있지 않다. 최소 권장 사항은 2048비트 이상이다.[33] n이 300비트 이하인 경우에는 개인용 컴퓨터에서도 몇 시간 만에 인수분해할 수 있다. 1999년에 RSA-155(512비트)가 인수분해되었고, 2011년에는 512비트 코드 서명 인증서를 사용하는 악용 사례가 보고되었다.[34]

1994년 피터 쇼어는 양자 컴퓨터가 다항 시간 내에 인수분해를 할 수 있어 RSA를 깨뜨릴 수 있음을 보여주었다.[49] 쇼어의 알고리즘은 양자 컴퓨터가 실용화되면 RSA 암호의 안전성을 보장할 수 없음을 시사한다.[49]

RSA사는 1991년부터 2007년까지 "RSA 소인수분해 챌린지"를 실시하여 소인수분해 가능한 정수의 비트 수를 조사했다. 다음은 챌린지에서 소인수분해된 RSA 숫자들이다.

RSA 숫자비트 수10진수 자릿수인수분해 날짜
RSA-1003301991년 4월 1일
RSA-1103641992년 4월 14일
RSA-1203971993년 6월 9일
RSA-1294261994년 4월 26일
RSA-1304301996년 4월 10일
RSA-1404631999년 2월 2일
RSA-1504962004년 4월 16일
RSA-1555121999년 8월 22일
RSA-1605302003년 4월 1일
RSA-1705632009년 12월 29일
RSA-5765761742003년 12월 3일
RSA-1805962010년 5월 8일
RSA-1906292010년 11월 8일
RSA-6406402005년 11월 2일
RSA-2006632002005년 5월 9일
RSA-2106962102013년 9월 26일
RSA-7047042012년 7월 2일
RSA-2207292016년 5월 13일
RSA-2307622018년 8월 15일
RSA-2327682020년 2월 17일
RSA-7687682009년 12월 12일
RSA-2407952019년 12월 2일
RSA-2508292020년 2월 28일



1977년 마틴 가드너는 사이언티픽 아메리칸지에 129자리 수와 공개 지수 e = 9007을 사용한 RSA 암호문을 게재하고, 해독 성공자에게 매사추세츠 공과대학교에서 100 달러를 지급하는 현상금 문제를 제시했다.[51] 당시에는 해독에 4경 년이 필요할 것으로 예측되었으나,[51] 1994년 4월, 국제 협력을 통해 2차 체법으로 해독에 성공했다.[52]

11. RSA 암호의 오용

RSA 암호는 여러 가지 잘못된 사용 방식으로 인해 보안 취약점이 발생할 수 있다.

; 공통 법

: 여러 사용자가 동일한 법 $n$을 공유하고, 각자 다른 개인키 $d$와 공개키 $e$를 사용하는 것은 안전하지 않다. 만약 한 사용자의 $n$, $e$, $d$ 조합을 알게 되면, $n$의 소인수분해가 쉬워져 다른 사용자의 개인키도 알아낼 수 있기 때문이다.

; 동보 통신

: 동일한 평문을 여러 수신자에게 각자의 공개키로 암호화하여 보내는 것도 취약하다. 만약 같은 $e$ 값을 가진 공개키(주로 3 또는 65537이 사용됨)로 암호화된 $e$개 이상의 암호문을 얻으면, 중국인의 나머지 정리를 통해 평문을 복원할 수 있다.[22] 이를 막기 위해, 암호화 전에 난수를 생성하여 평문에 삽입하는 패딩을 사용한다.

; 취약한 평문



; 곱셈 속성

: RSA는 두 암호문의 곱이 해당 평문의 곱의 암호화와 같다는 속성($m_1^e m_2^e \equiv (m_1 m_2)^e \pmod n$)을 갖는다. 이 때문에 선택 암호문 공격이 가능하다. 공격자는 해독하려는 암호문 $c$ 대신, 변형된 암호문 $c' \equiv cr^e \pmod n$ ($r$은 공격자가 선택)을 해독하도록 요청할 수 있다. 해독 결과 $mr \pmod n$을 얻으면, $r$의 역수를 곱해 $m$을 얻을 수 있다.

이러한 취약점을 방지하기 위해 실제 RSA 암호 구현에서는 패딩을 사용한다. PKCS#1 같은 표준은 RSA 암호화 전에 메시지를 안전하게 패딩하도록 설계되었다. 최적 비대칭 암호화 패딩(OAEP)은 이러한 공격을 방지하는 효과적인 방법이며, 최신 응용 프로그램에서 널리 사용된다.

참조

[1] 웹사이트 Dr Clifford Cocks CB http://www.bristol.a[...] Bristol University 2008-02-19
[2] 학술지 A Method for Obtaining Digital Signatures and Public-Key Cryptosystems http://people.csail.[...] 1978-02
[3] 학술지 Quantum-computing pioneer warns of complacency over Internet security https://www.nature.c[...] 2020-10-30
[4] 학술지 New directions in cryptography 1976-11
[5] 웹사이트 The Early Days of RSA – History and Lessons https://people.csail[...]
[6] 웹사이트 The RSA Cryptosystem: History, Algorithm, Primes http://www.math.uchi[...] 2007-08-20
[7] 학술지 Still Guarding Secrets after Years of Attacks, RSA Earns Accolades for its Founders http://www.msri.org/[...] 2003-06
[8] 웹사이트 A Note on Non-Secret Encryption https://www.gchq.gov[...] 1973-11-20
[9] 문서 From Private to Public Key Ciphers in Three Easy Steps https://ww2.amstat.o[...] Jim Sauerberg.
[10] 서적 The Mathematics of Encryption: An Elementary Introduction https://books.google[...] Margaret Cozzens and Steven J. Miller.
[11] 서적 Introduction to Cryptography with Open-Source Software https://books.google[...] Alasdair McAndrew.
[12] 문서 Public key Cryptography https://web.archive.[...] Surender R. Chiluka.
[13] 문서 Cryptography As a Teaching Tool https://sites.math.w[...] Neal Koblitz.
[14] 웹사이트 RSA Security Releases RSA Encryption Algorithm into Public Domain http://www.rsa.com/p[...]
[15] 학술지 Twenty Years of attacks on the RSA Cryptosystem http://crypto.stanfo[...]
[16] 서적 Applied Cryptography Bruce Schneier 1996
[17] 웹사이트 Further Attacks on Server-Aided RSA Cryptosystems https://citeseerx.is[...]
[18] 서적 A Course in Number Theory and Cryptography Neal Koblitz 1987
[19] 간행물 common factors in (''p'' − 1) and (''q'' − 1) https://mta.openssl.[...] 2015-07-31
[20] 간행물 common factors in (''p'' − 1) and (''q'' − 1) https://mta.openssl.[...] 2015-08-01
[21] 간행물 Public-Key Cryptography Standards (PKCS) #1: RSA Cryptography Specifications Version 2.1 Network Working Group 2003-02
[22] 서적 Advances in Cryptology – CRYPTO '85 Proceedings
[23] 학술지 Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities https://www.di.ens.f[...]
[24] 서적 Proceedings of the fourteenth annual ACM symposium on Theory of computing - STOC '82 Association for Computing Machinery 1982-05-05
[25] 서적 Advances in Cryptology — EUROCRYPT 2000 Springer 2000
[26] 웹사이트 RSA Algorithm https://www.di-mgt.c[...]
[27] 웹사이트 OpenSSL bn_s390x.c https://github.com/o[...] 2024-08-02
[28] 서적 Network security traceback attack and react in the United States Department of Defense network https://books.google[...] Trafford 2013-03-29
[29] 웹사이트 Factorization of a 512-bit RSA Modulus https://www.iacr.org[...] Eurocrypt 2000
[30] 컨퍼런스 Riemann's Hypothesis and Tests for Primality https://www.cs.cmu.e[...]
[31] 웹사이트 Factorization of RSA-250 https://lists.gforge[...] Cado-nfs-discuss 2020-02-28
[32] 웹사이트 TWIRL and RSA Key Size http://emc.com/emc-p[...] RSA Laboratories 2003-05-06
[33] 웹사이트 NIST Special Publication 800-57 Part 3 Revision 1: Recommendation for Key Management: Application-Specific Key Management Guidance http://nvlpubs.nist.[...] National Institute of Standards and Technology 2015-01-22
[34] 웹사이트 RSA-512 certificates abused in-the-wild https://blog.fox-it.[...] 2011-11-21
[35] 학술지 Cryptanalysis of short RSA secret exponents http://www.cits.rub.[...] 1990-05
[36] 학회 The Return of Coppersmith's Attack: Practical Factorization of Widely Used RSA Moduli https://crocs.fi.mun[...] 2017-11
[37] 웹사이트 Flaw Found in an Online Encryption Method https://www.nytimes.[...] 2012-02-14
[38] 웹사이트 Ron was wrong, Whit is right http://eprint.iacr.o[...]
[39] 웹사이트 New research: There's no need to panic over factorable keys–just mind your Ps and Qs https://freedom-to-t[...] 2012-02-15
[40] 학회 Remote timing attacks are practical http://crypto.stanfo[...]
[41] 웹사이트 'BERserk' Bug Uncovered In Mozilla NSS Crypto Library Impacts Firefox, Chrome https://www.darkread[...] 2014-09-25
[42] 웹사이트 RSA Signature Forgery in NSS https://www.mozilla.[...]
[43] 학회 On the power of simple branch prediction analysis
[44] 서적 2010 Design, Automation & Test in Europe Conference & Exhibition (DATE 2010) 2024-11-21
[45] 웹사이트 Practical Cryptography With Go https://leanpub.com/[...] 2022-01-04
[46] 문서 cipher
[47] 서적 数学の魔法の宝箱 ソフトバンク クリエイティブ
[48] 문서 유클리드 호제법
[49] 웹사이트 量子コンピューターが暗号技術を「破壊」する？その真偽を検証してみた https://xtech.nikkei[...] 2020-01-30
[50] 간행물 Advances in Cryptology — CRYPTO 2001 http://eprint.iacr.o[...] Springer-Verlag
[51] 학술지 Mathematical Games, August 1977 http://simson.net/re[...]
[52] 뉴스 RSA-129 https://ns1.omnitech[...] Internet news 2020-12-10
[53] 웹사이트 The Magic Words are Squeamish Ossifrage http://bit-player.or[...] Advances in Cryptology - ASIACRYPT'94 1994-07
[54] 웹사이트 http://www.bristol.a[...]
[55] 학술지 A Method for Obtaining Digital Signatures and Public-key Cryptosystems http://doi.acm.org/1[...]


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com