RSA(암호 시스템)

RSA

장군
디자이너	론 리베스트, 아디 샤미르, 레너드 애들먼
초판	1977
인정.	PKCS#1, ANSI X9.31, IEEE 1363
암호 상세
키 사이즈	2,048 ~ 4,096 비트(표준)
라운드	1
최고의 퍼블릭 암호 분석
일반 컴퓨터용 일반 번호 필드 체 양자 컴퓨터에 대한 쇼어의 알고리즘입니다. 829비트 키가 파손되었습니다.

RSA(Rivest-Shamir-Adleman)는 안전한 데이터 전송에 널리 사용되는 공개 키 암호 시스템입니다.그것은 또한 가장 오래된 것 중 하나이다.약자 "RSA"는 1977년 이 알고리즘을 공개적으로 기술한 론 리베스트, 아디 샤미르, 레너드 애들먼의 성에서 유래했다.1973년 영국의 수학자 클리포드 콕스에 의해 GCHQ(영국의 신호 정보 기관)에서 이와 동등한 시스템이 비밀리에 개발되었습니다.그 시스템은 ^[1]1997년에 기밀 해제되었다.

공개키 암호시스템에서 암호화 키는 공개되며 비밀(개인)으로 유지되는 복호화 키와는 구별됩니다.RSA 사용자는 2개의 큰 소수점과 보조값을 바탕으로 공개키를 작성하고 공개합니다.소수점들은 비밀에 부쳐진다.메시지는 공개키를 통해 누구나 암호화할 수 있지만 소수를 ^[2]아는 사람만이 해독할 수 있습니다.

RSA의 보안은 "팩터링 문제"라는 두 개의 큰 소수 곱을 팩터링하는 실질적인 어려움에 의존합니다.RSA 암호화를 해제하는 것은 RSA 문제로 알려져 있습니다.그것이 인수분해 문제만큼 어려운지는 ^[3]미해결 문제이다.충분히 큰 키를 사용할 경우 시스템을 파괴할 수 있는 공개된 방법은 없습니다.

RSA는 비교적 느린 알고리즘입니다.따라서 일반적으로 사용자 데이터를 직접 암호화하는 데 사용되지 않습니다.RSA는 대칭 키 암호화에 대한 공유 키를 전송하는 데 사용되는 경우가 많습니다. 이 암호는 대량 암호화와 복호화에 사용됩니다.

역사

비대칭 공개-비공개 키 암호 시스템의 아이디어는 Whitfield Diffie와 Martin Hellman이 1976년에 이 개념을 발표했기 때문입니다.그들은 또한 디지털 서명을 도입하고 숫자 이론을 적용하려고 시도했다.그들의 공식은 소수점인 어떤 숫자의 지수화로 만들어진 공유 비밀키를 사용했다.그러나, 그들은 단방향 함수를 실현하는 문제를 열어두었는데, 이는 아마도 ^[4]그 당시 인수 분해의 난이도가 잘 연구되지 않았기 때문이다.

Massachusetts Institute of Technology의 Ron Rivest, Adi Shamir 및 Leonard Adleman은 1년 동안 반전하기 어려운 단방향 함수를 만들기 위해 여러 번 시도했습니다.컴퓨터 과학자였던 Rivest와 Shamir는 많은 잠재적 기능을 제안했고, 수학자인 Adleman은 그들의 약점을 찾는 데 책임이 있었습니다.그들은 "knapsack 기반"과 "변환 다항식"을 포함한 많은 접근법을 시도했다.한동안 그들은 자신들이 원하는 것이 모순된 ^[5]요구 때문에 불가능하다고 생각했다.1977년 4월, 그들은 한 학생의 집에서 유월절을 보내고 자정 ^[6]무렵에 집으로 돌아오기 전에 마니셰비츠 와인을 많이 마셨다.잠이 오지 않은 리베스트는 수학 교과서를 들고 소파에 누워 일방통행 기능에 대해 생각하기 시작했다.그는 그의 생각을 공식화하기 위해 밤을 보냈다. 그리고 그는 새벽까지 많은 서류를 준비했다.이 알고리즘은 현재 ^[7]RSA로 알려져 있습니다.이 알고리즘은 논문과 같은 순서로 성씨의 이니셜입니다.

영국 정부통신본부(GCHQ)에서 일하는 영국 수학자 클리포드 콕스는 1973년 ^[8]내부 문서에 이와 동등한 시스템을 기술했다.그러나, 그 당시에는 비교적 비싼 컴퓨터가 그것을 구현하는데 필요했기 때문에, 그것은 대부분 호기심이라고 여겨졌고, 공개적으로 알려진 한, 결코 배치되지 않았다.그러나 그의 발견은 극비 분류로 인해 1997년까지 밝혀지지 않았다.

Kid-RSA(Kid-RSA)는 1997년에 공개된 단순하고 안전하지 않은 공개키 암호로 교육 목적으로 설계되었습니다.Kid-RSA를 학습하면 RSA 및 기타 공개 키 암호에 대한 통찰력을 얻을 수 있다고 생각하는 사람도 있습니다. 이는 단순화된 ^{[9][10][11][12][13]}DES와 유사합니다.

특허

RSA 알고리즘을 기술하는 특허는 1983년 9월 20일 MIT에 부여되었습니다.U.S. 특허 4,405,829 "암호통신 시스템과 방법"DWPI의 특허 요약에서:

시스템은, 부호화 장치를 가지는 적어도 1개의 단말기와 복호 장치를 가지는 적어도 1개의 단말기에 결합하는 통신 채널을 포함한다.전송 대상 메시지는 소정의 집합의 수 M으로서 부호화함으로써 부호화 단말기의 암호문에 암호화된다.그런 다음 이 숫자는 첫 번째 미리 결정된 전력(대상 수신기에 관련됨)으로 상승하고 최종적으로 계산됩니다.나머지 또는 잔여물인 C는...(대상 수신기와 관련된) 2개의 소정의 소수 곱으로 지수화된 수를 나누었을 때 계산됩니다.

알고리즘에 대한 자세한 설명은 1977년 8월 Scientific American's Mathematical Games ^[7]칼럼에 실렸다.이는 특허출원일인 1977년 12월보다 앞선 것이다.그 결과 특허는 미국 밖에서는 법적 지위를 갖지 못했다.만약 콕스의 작품이 공개적으로 알려졌더라면, 미국에서의 특허 또한 합법적이지는 않았을 것이다.

특허가 발행되었을 때 특허 기간은 17년이었다.특허는 2000년 9월 21일에 만료될 예정이었지만 RSA Security는 2000년 ^[14]9월 6일에 알고리즘을 공개했습니다.

작동

RSA 알고리즘에는 키 생성, 키 배포, 암호화 및 복호화의 4가지 단계가 포함됩니다.

RSA의 이면에 있는 기본 원칙은 모든 정수 m에 대해 모듈러형 지수(0 µm < n)를 사용하여 3개의 매우 큰 양의 정수 e, d 및 n을 찾는 것이 실용적이라는 것입니다.

${{displaystyle(m^{e})^{d}\equiv mcpmod {n}}$

그리고 e와 n, 심지어 m을 아는 것은 d를 찾는 것이 매우 어려울 수 있습니다.여기서 트리플 바(θ)는 모듈러 합치를 나타냅니다.(단순한 용어로 모듈러 일치성은 (m^e)^d을 n으로 나누고 m을 n으로 나누면 각각이 같은 나머지를 갖는다는 것을 의미합니다.)

또한 일부 연산의 경우 두 지수화의 순서를 변경할 수 있고 이 관계가 다음을 의미한다는 것이 편리하다.

${\displaystyle(m^{d})^{e}\equiv mbpmod {n}.}$

RSA에는 공개 키와 개인 키가 포함됩니다.공용 키는 누구나 알 수 있으며 메시지를 암호화하는 데 사용됩니다.공개 키로 암호화된 메시지는 개인 키를 사용하여 적절한 시간 내에 복호화할 수 있습니다.공개키는 정수n과 정수e로, 개인키는 정수d로 표시됩니다(단, n은 복호화 프로세스에서도 사용되고 있기 때문에 개인키의 일부로 간주될 수 있습니다).m은 메시지를 나타냅니다(이전에 아래에 설명되어 있는 특정 기술을 사용하여 작성되었습니다).

키 생성

RSA 알고리즘의 키는 다음과 같은 방법으로 생성됩니다.

1. 두 개의 서로 다른 소수 p와 q를 선택합니다.
   • 보안을 위해 정수 p와 q는 랜덤으로 선택해야 하며 크기가 비슷해야 하지만 팩터링을 ^[2]어렵게 하기 위해 길이가 몇 자리 차이가 있어야 합니다.소수 정수는 소수성 테스트를 사용하여 효율적으로 찾을 수 있습니다.
   • p와 q는 비밀입니다.
2. n = pq를 계산합니다.
   • n은 공개키와 개인키 양쪽의 계수로서 사용됩니다.보통 비트 단위로 표시되는 길이가 키 길이입니다.
   • n은 공개 키의 일부로 해방됩니다.
3. 계산 ((n)은 Carmichael의 전체 함수입니다.n = pq, θ(n) = lcm(p), θ(q)이므로 p와 q는 소수이므로 θ(p) = θ(p) = p - 1, 마찬가지로 θ(q) = q - 1이다.따라서 θ(n) = lcm(p - 1, q - 1)입니다.
   • ((n)은 비밀입니다.
   • lcm(a, b) = ab /gcd(a, b)이므로 lcm는 유클리드 알고리즘을 통해 계산할 수 있다.
4. 1 < e < ((n) 및 gcd(e, ((n) = 1이 되도록 정수e를 선택합니다.즉, e와 ((n)은 공존합니다.
   • e는 비트 길이가 짧고 해밍 무게가 작기 때문에 암호화가 더 효율적입니다. e에 대해 가장 일반적으로 선택되는 값은¹⁶ 2 + 1 = 65537입니다.e에 대해 가능한 최소(빠른) 값은 3이지만, 일부 설정에서는 ^[15]e에 대해 이러한 작은 값이 안전하지 않은 것으로 나타났습니다.
   • e는 공개 키의 일부로 해방됩니다.
5. d를 d µ⁻¹ e(mod µ(n))로 결정한다.즉, d는 e 모듈로 µ(n)의 모듈러 곱셈 역수이다.
   • 즉, d에 대해 방정식 dee ( 1 (mod ( (n)을 풀면 d는 확장 유클리드 알고리즘을 사용하여 효율적으로 계산될 수 있다. 왜냐하면 e와 n (n)이 공역이기 때문에 해당 방정식은 Bézout의 항등식의 한 형태이기 때문이다.여기서 d는 계수 중 하나이다.
   • d는 개인 키 지수로서 기밀로 유지됩니다.

공개키는 계수n과 공개(또는 암호화) 지수e로 구성됩니다.개인 키는 개인(또는 복호화) 지수d로 구성됩니다.이 지수d는 비밀로 해야 합니다.p, q 및 ((n)도 d 계산에 사용할 수 있기 때문에 비밀로 해야 합니다.실제로 d가 ^[16]계산되면 모두 폐기할 수 있습니다.

원래의 RSA 논문에서,^[2] 개인 지수 d를 계산하기 위해 θ(n) 대신 오일러 전체 함수 θ(n) = (p - 1)(q - 1)를 사용한다.θ(n)는 항상 θ(n)로 나누어지기 때문에 알고리즘도 동작합니다.오일러 전체 함수를 사용할 수 있는 가능성은 또한 정수 모듈로 pq의 곱셈군에 적용된 라그랑주의 정리로부터 비롯된다.따라서 dee 1 1(mod ( n)을 만족시키는 모든 d는 d⋅e 1 1(mod ( n)도 만족합니다.그러나 d modulo δ(n)를 계산하면 필요한 것보다 큰 결과가 나올 수 있습니다(즉, d > δ(n)).RSA의 대부분의 구현에서는 (다음 중국어 나머지 정리에 따라 최적화된 복호화 방법을 사용하는 것이 아니라 프라이빗 지수 d를 사용하는 경우) 어느 한 방법으로 생성된 지수를 받아들이지만 FIPS 186-4 등의 일부 표준에서는 d < ( ( n )가 요구될 수 있습니다.이 기준을 충족하지 않는 "초대형" 개인 지수는 더 작은 등가 지수를 얻기 위해 항상 모듈로 δ(n)를 줄일 수 있다.

n - 1 = pq - 1 = (p - 1) (q - 1) + (p - 1) + (q - ^[17]1)의 인수분해에는 (p - 1) 및 (q - 1)의 공통인자는 필요한 ^{[2][18][19][failed verification][20][failed verification]}2 이외에 매우 작은 공통인자만 갖는 것이 좋습니다.

주의: 원본 RSA 논문의 작성자는 d를 선택한 후 d modulo δ(n)의 모듈러 곱셈 역수로서 e를 계산하는 방법으로 키 생성을 수행하지만, PKCS#1 이후의 RSA의 현재 구현의 대부분은 그 역수(e와 compute d를 선택)를 수행합니다.선택한 키는 작을 수 있지만 일반적으로 계산된 키는 작을 수 없기 때문에 RSA 페이퍼의 알고리즘은 암호화에 비해 암호 해독을 최적화하고 최신 알고리즘은 암호화를 최적화합니다.^[2][21]

키 배포

Bob이 Alice에게 정보를 보내려고 한다고 가정합니다.RSA를 사용하기로 결정한 경우 Bob은 메시지를 암호화하기 위해 Alice의 공용 키를 알고 Alice는 개인 키를 사용하여 메시지를 해독해야 합니다.

Bob이 암호화된 메시지를 보낼 수 있도록 Alice는 자신의 공개 키(n, e)를 신뢰할 수 있지만 반드시 비밀은 아닌 경로를 통해 Bob에게 전송합니다.Alice의 개인 키(d)는 배포되지 않습니다.

암호화

밥은 앨리스의 공용 키를 얻은 후 앨리스에게 M 메시지를 보낼 수 있습니다.

이를 위해 먼저 패딩 스킴으로 알려진 합의된 리버서블 프로토콜을 사용하여 M(엄밀히 말하면 패딩되지 않은 평문)을 0 µm < n이 되도록 정수 m(엄밀히 말하면 패딩된 평문)으로 변환한다.그런 다음 그는 앨리스의 공개 키 e를 사용하여 암호문 c를 계산합니다.

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

모듈러형 지수를 사용하면 매우 많은 수의 경우에도 이 작업을 합리적으로 신속하게 수행할 수 있습니다.그런 다음 밥은 앨리스에게 c를 전송합니다.m의 최소9개의 값은 ^[22]m과 같은 암호문 c를 생성하지만 실제로는 거의 발생하지 않습니다.

복호화

Alice는 개인 키 지수 d를 사용하여 c에서 m을 복구할 수 있습니다.

${\displaystyle c^{d}\equiv(m^{e})^{d}\equiv mcpmod {n}.}$

m을 지정하면 패딩 방식을 반대로 함으로써 원래 메시지 M을 복구할 수 있습니다.

예

RSA 암호화 및 복호화의 예를 다음에 나타냅니다.여기서 사용되는 파라미터는 인위적으로 작지만 OpenSSL을 사용하여 실제 키쌍을 생성하고 검사할 수도 있습니다.

1. 다음과 같은 두 개의 서로 다른 소수점을 선택합니다.

   ${\displaystyle p}$ ${\displaystyle =}$ $(디스플레이 스타일$ p$=61)$ $및$ q ${\displaystyle =}$ ${\displaystyle 53.}$$(\displaystyle q=53).$$}$

2. 계산 n = pq 제공

   ${\displaystyle n=61\times 53=3233.}$

3. 제품에 대한 Carmichael의 전체 함수를 θ(n) = lcm(p - 1, q - 1)로 계산합니다.

   $\displaystyle \displayda(3233)=\operatorname {lcm}(60,52)=780.}$

4. 780과 동일한 번호1 < e < 780 을 선택합니다.e의 소수를 선택하면 e가 780의 제수가 아님을 확인할 수 있습니다.

   e ${\displaystyle =}$ $(\displaystyle$ e$=17$로 $합니다{\displaystyle }$.

5. 계산 d, e의 모듈식 곱셈 역수(mod θ(n))를 구하면 다음과 같이 계산됩니다.
   
   $${\displaystyle d=413,}$$

   
   1 ${\displaystyle =}$ ( ${\displaystyle 17}$ ${\displaystyle \times }$ ${\displaystyle 413}$ ${\displaystyle )}$ ${\displaystyle mod\mathrm{}}$ 7 $.$ {\$displaystyle$ 1= ($17\times$ 413$){\bmod {7}80$으로 $지정$합니다$.$$}$

공개 키는 (n = 3233, e = 17)입니다.패딩된 보통 텍스트메시지 m의 경우 암호화 기능은 다음과 같습니다.

${\displaystyle {displaystyle {m}&=m^{e}{n}\&=m^{17}{3}}233.\end { aligned}}$

개인 키는 (n = 3233, d = 413)입니다.암호화된 암호문 c의 경우 복호화 함수는 다음과 같습니다.

${\displaystyle {d}m(c)&=c^{d}{\bmod {n}\&=c^{413}{\bmod {3}233.\end { aligned}}$

예를 들어, m = 65를 암호화하기 위해

${\displaystyle c=65^{17}{\bmod {3}}233=2790.}$

c = 2790의 암호를 해독하려면

${\displaystyle m=2790^{413}{\bmod {3}}233=65.}$

이 두 계산 모두 모듈러형 지수를 위한 제곱 및 배수 알고리즘을 사용하여 효율적으로 계산할 수 있습니다.실제 상황에서는 선택된 소수점이 훨씬 더 클 것이다. 이 예에서는 n = 3233(자유롭게 사용 가능한 공개 키에서 소수점 p로 다시 인수하는 것은 사소한 일일 것이다. 그리고 공개 키에서도 역시 d를 얻기 위해 q가 반전되어 개인 키를 획득한다.

실제 구현에서는 계수(mod p 및 mod q를 사용한 mod pq)를 사용하여 계산 속도를 높이기 위해 중국어 나머지 정리를 사용합니다.

개인 키의 일부인 d, d_q 및_inv q 값은_p 다음과 같이 계산됩니다.

${\displaystyle {signed}d_{p}&=displaybmod {(}p-1)=413gbmod {(}61-1)=53,\d_{q}=413gbmod {(}53-1)=49,\q_{\inv}={q}^1-1}\end { aligned}}$

d, d_q 및_inv q는 효율적인 복호화를 위해 다음과_p 같이 사용됩니다(암호화는 적절한 d와 e 쌍을 선택함으로써 효율적입니다).

${\displaystyle {displaystyle}m_{1}&=c^{d_{p}{\bmod {p}}{\bmod {6}}=4,\m_{2}&=c^{q}{\bmod {5}=312,h(\bmod {p}})\end { aligned}}$

메시지 서명

Alice가 Bob의 공용 키를 사용하여 암호화된 메시지를 보낸다고 가정합니다.메시지에서 그녀는 자신이 앨리스라고 주장할 수 있지만, 밥은 누구나 밥의 공용 키를 사용하여 암호화된 메시지를 보낼 수 있기 때문에 앨리스가 보낸 메시지인지 확인할 방법이 없습니다.메시지 발신지를 확인하기 위해 RSA를 사용하여 메시지에 서명할 수도 있습니다.

앨리스가 밥에게 서명된 메시지를 보내고 싶다고 가정해 보자.그녀는 자신의 개인 키를 사용하여 이를 수행할 수 있습니다.메시지의 해시 값을 생성하여 d(modulo n)의 거듭제곱(메시지 복호화 시처럼)으로 올리고 메시지에 "서명"으로 첨부합니다.Bob은 서명된 메시지를 수신하면 Alice의 공용 키와 함께 동일한 해시 알고리즘을 사용합니다.시그니처를 e(modulo n)의 거듭제곱(메시지를 암호화할 때와 마찬가지로)으로 올리고 그 해시값과 메시지의 해시값을 비교합니다.만약 두 사람이 동의한다면, 그는 메시지 작성자가 앨리스의 개인 키를 가지고 있었고, 메시지가 전송된 이후 변조되지 않았다는 것을 알게 됩니다.

이는 지수규칙에 의해 기능합니다.

${\displaystyle h=\operatorname {display}(m),}$

${{displaystyle (h^{e})^{d}=h^{de}=(h^{d})^{e}\equiv hcpmod {n}}.}$

따라서 범용성을 잃지 않고 키를 교환할 수 있습니다.즉, 키쌍의 개인 키를 사용하여 다음 중 하나를 수행할 수 있습니다.

1. 수신자 전용 메시지를 해독합니다.이 메시지는 공개 키를 가진 모든 사용자가 암호화할 수 있습니다(비대칭 암호화 전송).
2. 누구나 암호를 해독할 수 있지만 한 사람만 암호화할 수 있는 메시지를 암호화합니다. 그러면 디지털 서명이 제공됩니다.

정확성 증명

페르마의 소정리를 이용한 증명

RSA의 정확성에 대한 증명은 페르마의 작은 정리에 기초하며,^{[note 1]} a를 나누는 것이 아니라 정수 a와 소수 p에 대해 θ 1 (mod p)을^{p − 1} 나타낸다.

저희가 보여드리고 싶은 건

${{displaystyle(m^{e})^{d}\equiv mmpmod {pq}}$

모든 정수 m에 대해 p와 q가 구별되는 소수이고 e와 d가 ed ≤ 1(mod δ(pq))을 만족하는 양의 정수일 때.

θ(pq) = lcm(p - 1, q - 1)는 구조상 p - 1과 q - 1로 나누어지기 때문에 다음과 같이 쓸 수 있다.

${\displaystyle ed-1=h(p-1)=k(q-1)}$

음수가 아닌 일부 정수 h와 ^{[note 2]}k에 대해.

m과 m과 같은^ed 두 숫자가 일치 mod pq인지 여부를 확인하려면 mod p와 ^{[note 3]}mod q가 개별적으로 일치하는지 확인하는 것으로 충분합니다.

m µm(mod p)을 표시하려면^ed 다음 두 가지 경우를 고려합니다.

1. m 0 0(mod p)인 경우 m은 p의 배수입니다.따라서^ed m은 p의 배수입니다.m^ed 0 0 m m ( mod p ) 。
2. m ${\$ \ $displaystyle \ equiv }$ 0$$ ( mod p )의 경우

${{displaystyle m^{ed-1}m=m^{h(p-1)}m=(m^{p-1})^{h}m\equiv 1^{h}m\equiv mcpmod {p}}}$

여기서 우리는 m mod p를 1로 대체하기 위해 페르마의^p−1 작은 정리를 사용했다.

m µm(mod q)의^ed 검증도 완전히 같은 방법으로 진행됩니다.

1. m 0 0(mod q)인 경우 m은^ed q의 배수입니다.따라서^ed m 0 0 m m(mod q)입니다.
2. m ${\$ \ $displaystyle \ equiv }$ 0 ( mod q )의 경우

${{displaystyle m^{ed-1}m=m^{k(q-1)}m=(m^{q-1})^{k}m\equiv 1^{k}m\equiv m^{k}m\equiv mgpmod {q}}}}.}$

이로써 ed 1 1(mod ( (pq))이 되는 정수m 및 정수e, d에 대한 증명은 완료됩니다.

${{displaystyle (m^{e})^{d}\equiv mcpmod {pq}}.}$

주의:

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

비록 Rivest, Shamir, Adleman의 원본 논문은 RSA가 왜 작용하는지를 설명하기 위해 페르마의 작은 정리를 사용했지만, 오일러의 정리에 의존하는 증거를 찾는 것은 흔한 일이다.

우리는^ed m µm(mod n)을 보여주고 싶다. 여기서 n = pq는 두 개의 다른 소수의 곱이고 e와 d는 ed µ1(mod µ(n))을 만족하는 양의 정수이다.e와 d가 양수이기 때문에, 우리는 음이 아닌 정수 h에 대해 ed = 1 + hµ(n)로 쓸 수 있다. m이 상대적으로 n에 소수라고 가정하면, 우리는 다음과 같이 된다.

${{displaystyle m^{ed}=m^{1+h\varphi(n)}=m(m^{\varphi(n)})^{h}\equiv m(1)^{h}\equiv mcpmod {n}}}$

여기서 두 번째 마지막 합치는 오일러의 정리로부터 온다.

보다 일반적으로, ed δ 1(mod δ(n))을 만족하는 e와 d에 대해, 카마이클의 오일러 정리 일반화로부터 같은 결론이 뒤따른다. 오일러 정리는 상대적으로 소수에서 n에 대한 모든 m에 대해 m δ 1(mod n)을^λ(n) 말한다.

m이 n에 비해 상대적으로 소수가 아닐 경우 방금 지정한 인수는 유효하지 않습니다.이것은 매우 가능성이 낮습니다(이 성질은 1/p + 1/q - 1/(pq) 숫자의 일부만 가지고 있습니다). 그러나 이 경우에도 원하는 일치성은 여전히 참입니다.m 0 0(mod p) 또는 m 0 0(mod q) 중 하나이며, 이러한 경우는 앞의 증명으로 처리할 수 있습니다.

패딩

플레인 RSA에 대한 공격

플레인 RSA에 대한 공격은 다음과 같습니다.

• 낮은 암호화 지수(예: e = 3)와 m의 작은 값(예: m < n^1/e)으로 암호화하는 경우 m의 결과는^e 계수 n보다 완전히 작습니다.이 경우 암호문의 eth 루트를 정수 위에 두면 암호문을 쉽게 해독할 수 있습니다.
• 같은 클리어 텍스트메시지가 암호화된 방법으로 e 또는 그 이상의 수신자에게 송신되어 수신자가 같은 지수e를 공유하지만 p, q, n이 다르면 중국어 나머지 정리를 통해 원래의 클리어 텍스트메시지를 복호화하기가 쉬워집니다.요한 호스타드는 명확한 텍스트가 동일하지 않더라도 공격이 가능하다는 것을 알아챘지만 공격자는 이들 ^[23]사이의 선형 관계를 알고 있다.이 공격은 나중에 돈 코퍼스미스에 의해 개선되었다(코퍼스미스의 [24]공격 참조).
• RSA 암호화는 결정론적 암호화 알고리즘(즉, 랜덤 컴포넌트가 없음)이기 때문에 공격자는 공개 키로 가능성이 높은 평문을 암호화하여 암호 시스템과 동일한지 여부를 테스트함으로써 암호 시스템에 대해 선택된 평문 공격을 성공적으로 시작할 수 있습니다.공격자가 대응하는 평문을 알고 있거나 선택한 경우에도 공격자가 2개의 암호화를 서로 구별할 수 없는 경우 암호 시스템은 의미론적으로 안전하다고 불립니다.패딩이 없는 RSA는 의미상 ^[25]안전하지 않습니다.
• RSA는 2개의 암호문 곱이 각 평문 곱의 암호화와 같다는 속성을 가지고 있습니다.즉, mm₁^e₂^e µ(mm₁₂)(^emod n).이 곱셈 속성을 통해 선택된 암호문 공격이 발생할 수 있습니다.예를 들어 암호문 c µm^e(mod n)의 복호화를 알고 싶은 공격자가 개인키 d의 보유자에게 공격자가 선택한 값 r에 대해 의심스러워 보이는 암호문 c µcr^e(mod n)의 복호화를 요구할 수 있습니다.곱셈 속성을 위해 c'는 mr(mod n)의 암호화입니다.따라서 공격자가 공격에 성공하면 mr(mod n)을 학습합니다.mr에 r modulo ^{[citation needed]}n의 모듈러 역수를 곱함으로써 메시지 m을 얻을 수 있습니다.
• 개인 지수 d가 주어지면 계수 n = pq를 효율적으로 인수분해할 수 있다.그리고 계수 n = pq의 인수분해가 주어지면 공개키(e), n)^[15]에 대해 생성된 임의의 비밀키(d), n)를 얻을 수 있다.

패딩 방식

이러한 문제를 피하기 위해 실용적인 RSA 구현에서는 일반적으로 m 값을 암호화하기 전에 어떤 형태로든 구조화된 랜덤 패딩을 값 m에 포함합니다.이 패딩에 의해 m은 안전하지 않은 플레인텍스트의 범위에 포함되지 않으며, 패딩된 후 특정 메시지가 다수의 다른 가능한 암호텍스트 중 하나로 암호화됩니다.

PKCS#1 등의 표준은 RSA 암호화 전에 메시지를 안전하게 패딩하도록 신중하게 설계되어 있습니다.이러한 스킴은 평문 m에 몇 개의 추가 비트를 패딩하기 때문에 패딩되지 않은 메시지 M의 크기는 다소 작아야 합니다.RSA 패딩 스킴은 예측 가능한 메시지 구조에 의해 촉진될 가능성이 있는 고도의 공격을 방지할 수 있도록 신중하게 설계해야 합니다.이전 버전의 PKCS#1 표준(버전 1.5까지)에서는 RSA를 의미적으로 안전하게 하는 것으로 보이는 구조를 사용했습니다.단, Crypto 1998에서 Bleichenbacher는 이 버전이 실제 적응형 선택 암호 공격에 취약하다는 것을 보여주었습니다.또한, Eurocrypt 2000에서 Coron ^[26]등은 일부 유형의 메시지에 대해 이 패딩이 충분한 수준의 보안을 제공하지 않는다는 것을 보여주었다.최신 버전의 표준에는 Optimal Asymmetric Encryption Padding(OAEP)이 포함되어 있어 이러한 공격을 방지합니다.따라서 새로운 어플리케이션에서는 OAEP를 사용해야 하며 PKCS#1 v1.5 패딩은 가능한 한 교환해야 합니다.PKCS#1 규격에는 RSA 시그니처의 보안을 강화하기 위한 처리 스킴도 포함되어 있습니다(RSA-PSS(Probabilatic Signature Scheme for RSA)

RSA-PSS 등의 시큐어 패딩 방식은 메시지 암호화와 마찬가지로 메시지 서명 보안에 필수적입니다.PSS에 관한 2개의 미국 특허(U.S.특허 6,266,771개 및 U.S.특허 7,036,014개)가 부여되었지만, 이러한 특허는 각각 2009년 7월 24일과 2010년 4월 25일에 만료되었습니다.PSS의 사용은 ^{[original research?]}더 이상 특허에 의해 방해를 받지 않는 것처럼 보인다.암호화 및 서명에 서로 다른 RSA 키 쌍을 사용하는 것이 잠재적으로 더 ^[27]안전합니다.

보안 및 실제 고려 사항

중국어 나머지 알고리즘 사용

효율성을 높이기 위해 널리 사용되는 암호화 라이브러리(OpenSSL, Java 및 등)를 많이 사용합니다.NET) 중국어 나머지 정리에 기초한 암호 해독 및 다음 최적화 서명에 사용합니다.다음 값은 미리 계산되어 개인 키의 일부로 저장됩니다.

${\displaystyle }$$p{\displaystyle }$$\displaystyle$p 및$$ q$\displaystyle$q – 키 $$생성의 소수,

${\displaystyle d_{P}=d{\pmod {p-1}}$

${\displaystyle d_{Q}=d{\pmod {q-1}}$

${\displaystyle q_{\text{inv}}=q^{-1}{\pmod {p}}.}$

이러한 값을 통해 수신자는 다음과 같이 지수 m = c^d(mod pq)를 보다 효율적으로 계산할 수 있습니다.

${\displaystyle m_{1}=c^{d_{P}} {\pmod {p}}$

${\displaystyle m_{2}=c^{d_{Q}}{\pmod {q}}}$

${\displaystyle h}$ ${\displaystyle =}$ ${\displaystyle {\text{q}}_{}}$inv ( ${\displaystyle {}_{}{1\mathrm{}}_{}}$ - ${\displaystyle {}_{}{2\mathrm{}}_{}}$) ( ${\displaystyle mod}$p$$) { $displaystyle$ h =$$q _ { \$text$ { $inv$} （ $m$_ { $1$} - $m$_ {2$}$ } { \ $pmod${$p$}$$^[28]、

$({displaystyle m=m_{2}+syslogpmod {pq}).}$

두 개의 모듈식 지수를 계산해야 하지만 제곱에 의한 지수를 계산하는 것보다 효율적입니다.그 이유는 이들 2개의 모듈러형 지수는 모두 더 작은 지수와 더 작은 계수를 사용하기 때문입니다.

정수 인수분해 및 RSA 문제

RSA 암호 시스템의 보안은 두 가지 수학적 문제, 즉 많은 수를 고려하는 문제와 RSA 문제를 기반으로 합니다.RSA 암호문의 완전한 복호화는 이 두 가지 문제가 모두 어렵다는 가정 하에 불가능하다고 생각됩니다.즉, 이들 문제를 해결하기 위한 효율적인 알고리즘이 존재하지 않습니다.부분 복호화에 대한 보안을 제공하려면 안전한 패딩 ^[29]방식을 추가해야 할 수 있습니다.

RSA 문제는 eth roots modulo를 복합n으로 취득하는 태스크로 정의됩니다.여기서 (n, e)는 RSA^e 공개키이고, c는 RSA 암호문입니다.현재 RSA 문제를 해결하기 위한 가장 유망한 접근법은 계수 n을 인수화하는 것입니다.주요 요인을 회복하는 기능을 통해 공격자는 공개 키(n, e)에서 비밀 지수 d를 계산하고 표준 절차를 사용하여 c를 복호화할 수 있습니다.이를 위해 공격자는 n을 p와 q로 인수하여 e에서d를 판별할 수 있는lcm(p - 1, q - 1)를 계산합니다.고전적인 컴퓨터에서 큰 정수를 인수분해하는 다항식 시간 방법은 아직 발견되지 않았지만, 존재하지 않는 것으로 증명되지는 않았습니다. 이 문제에 대한 논의는 정수 인수분해를 참조하십시오.

다중 다항식 2차 체(MPQS)를 사용하여 공개 계수 n을 인수분해할 수 있습니다.

1999년의 첫 번째 RSA-512 인수분해에서는 수백 대의 컴퓨터가 사용되었으며 약 7개월의 ^[30]경과기간에 걸쳐 8,400년의 MIPS가 필요했습니다.2009년까지 Benjamin Moody는 퍼블릭 소프트웨어(GGNFS)와 데스크톱 컴퓨터(1,900MHz CPU를 탑재한 듀얼 코어 Athlon64)만을 사용하여 73일 만에 512비트 RSA 키를 인수할 수 있었습니다.필요한 디스크 스토리지는 5기가바이트 미만이며, 체화 프로세스에는 약 2.5기가바이트의 RAM이 필요했습니다.

리베스트, 샤미르, 애들먼은^[2] 밀러가 확장된 리만 가설의 진실이라고 가정할 때 n과 e에서 d를 찾는 것이 n을 p와 ^[31]q로 인수하는 것만큼 어렵다는 것을 보여주었다고 언급했다.그러나 Rivest, Shamir 및 Adleman은 논문의 IX/D 섹션에서 RSA를 뒤집는 것이 팩터링만큼 어렵다는 증거를 찾지 못했다고 지적했습니다.

2020년 현재^[update] 가장 큰 공개 인수 RSA 번호는 829비트(소수 250자리, RSA-250)^[32]입니다.최첨단 분산 구현에 의한 인수분해에는 약 2700년의 CPU가 소요되었습니다.실제로 RSA 키의 길이는 일반적으로 1024 ~4096비트입니다2003년에 RSA Security는 ^[33]1024비트 키가 2010년까지 크래킹이 가능할 것으로 예측했습니다.2020년 현재, 이러한 키가 깨질 수 있을지는 알려지지 않았지만 최소 권장 사항은 최소 2048비트로 ^[34]이동했습니다.일반적으로 n이 충분히 크면 RSA는 양자 컴퓨팅 이외에서 안전하다고 가정합니다.

n이 300비트 이하일 경우 PC에서 몇 시간 이내에 인수분해할 수 있으며, 이미 자유롭게 이용할 수 있는 소프트웨어를 사용할 수 있습니다.RSA-155가 수백 대의 컴퓨터를 사용하여 계수를 정했던 1999년에는 512비트의 키가 사실상 깨지기 쉬운 것으로 나타났습니다.이러한 키는 공통 하드웨어를 사용하여 몇 주 후에 계수를 정하게 되었습니다.512비트 코드 서명 인증서를 사용한 부정 이용은 2011년에 ^[35]보고되었습니다.2003년에 Shamir와 Tromer에 의해 기술된 TWIRL이라는 이름의 이론적인 하드웨어 디바이스는 1024비트 ^[33]키의 보안성에 의문을 제기했습니다.

1994년, Peter Shor는 양자 컴퓨터가 실제로 목적을 위해 만들어질 수 있다면 다항식 시간을 인수하여 RSA를 파괴할 수 있다는 것을 보여주었습니다. Shor의 알고리즘을 참조하십시오.

키 생성 오류

이 섹션은 확인을 위해 추가 인용문이 필요합니다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선하는 데 도움을 주십시오. 조달되지 않은 자재는 제거될 수 있습니다.출처 : 'RSA' 암호 시스템– 뉴스 · 신문 · 서적 · 학자 · JSTOR (2017년 10월) (이 템플릿 메시지 삭제 방법 및 삭제 시기 확인)

큰 소수 p와 q를 찾는 것은 대개 거의 모든 비소수를 신속하게 제거하는 확률론적 소수성 테스트를 사용하여 정확한 크기의 난수를 테스트함으로써 이루어진다.

숫자 p와 q는 n에 대한 페르마 인수분해가 성공하지 않도록 "너무 가까이" 해서는 안 된다.p - q가 2n^1/4 미만일 경우(n = pµq, n의 "작은" 1024비트 값도 3×10⁷⁷) p와 q의 해답은 간단하다.또한 p - 1 또는 q - 1 중 하나의 소인수만 있으면 Pollard의 p - 1 알고리즘에 의해 n을 빠르게 인수분해할 수 있으므로 p 또는 q 값은 폐기해야 한다.

개인 지수 d가 충분히 큰 것이 중요합니다.Michael J. Wiener는 p가 q와 2q 사이(매우 일반적인)와 d < n^1/4/3 사이이면 n과 ^[36]e에서 d를 효율적으로 계산할 수 있음을 보여주었다.

적절한 패딩을 사용할 경우 e = 3과 같은 소규모 공개 지수에 대한 알려진 공격은 없습니다.Coppersmith의 공격은 특히 공개 지수 e가 작거나 암호화된 메시지가 짧고 패딩되지 않은 경우 RSA를 공격하는 데 많은 응용 프로그램이 있습니다.65537은 일반적으로 e에 사용되는 값입니다.이 값은 잠재적인 소규모 일관성 공격을 회피하고 효율적인 암호화(또는 시그니처 검증)를 허용하는 타협으로 간주할 수 있습니다.NIST 컴퓨터 보안에 관한 특별 간행물(2007년 8월 SP 800-78 Rev.1)에서는 65537보다 작은 공개 지수 e를 허용하지 않지만, 이 제한에 대한 이유는 명시되어 있지 않습니다.

2017년 10월 Masaryk University 연구팀은 RSALib로 알려진 Infineon의 라이브러리에 구현된 알고리즘에 의해 생성된 RSA 키에 영향을 미치는 ROCA 취약성을 발표했습니다.다수의 스마트 카드와 Trusted Platform Module(TPM; 신뢰할 수 있는 플랫폼 모듈)이 영향을 받는 것으로 나타났습니다.취약한 RSA 키는 팀이 ^[37]공개한 테스트 프로그램을 사용하여 쉽게 식별할 수 있습니다.

강력한 난수 생성의 중요성

적절한 엔트로피로 적절히 시드된 암호화의 강력한 난수 생성기를 사용하여 소수 p와 q를 생성해야 한다. 인터넷에서 수집된 수백만 개의 공개 키를 비교하는 분석은 2012년 초에 Arjen K에 의해 수행되었다. 렌스트라, 제임스 P휴즈, 맥심 오귀에, 조프 보스, 토르스텐 클라인중, 크리스토퍼 워치터.그들은 유클리드의 ^[38][39]알고리즘만을 사용하여 키의 0.2%를 인수분해할 수 있었다.

정수 인수분해를 기반으로 한 암호 시스템 고유의 약점을 이용했습니다.n = pq가 하나의 공개 키이고 n = p′q가 다른 경우, 우연한 기회에 p = p ((그러나 q는 q),와 동일하지 않음) = p의 단순한 계산은 n과 n의 두 키를 모두 손상시킨다.Lenstra 등은 이 문제가 의도한 보안 수준의 2배의 비트 길이의 강력한 랜덤시드를 사용하거나 p와 q를 독립적으로 선택하는 대신 주어진 p를 선택하는 결정론적 함수를 사용함으로써 최소화될 수 있다는 점에 주목한다.

나디아 헤닝거는 비슷한 실험을 한 그룹의 일부였다.Daniel J. Bernstein의 아이디어를 사용하여 발견된 다른 모든 키 nµ(7억2900만 자리 수)의 곱에 대해 각 RSA 키 n의 GCD를 계산했습니다.각 gcd(n, nµ)를 개별적으로 계산하는 것이 아니라, 결과적으로 GCD의 문제가 1개의 대규모 분할 후에 정상 크기이기 때문입니다.

Henninger는 블로그에서 이 불량 키가 거의 30개 이상의 제조사가 제공하는 "방화벽, 라우터, VPN 디바이스, 리모트 서버 관리 디바이스, 프린터, 프로젝터, VOIP 전화"를 포함한 임베디드 애플리케이션에서 발생했다고 밝혔습니다.Henninger는 두 그룹에 의해 발견된 1개의 공유 프라임 문제는 의사난수 생성기가 처음에 제대로 시드되지 않은 후 첫 번째 소수와 두 번째 소수 생성 사이에 다시 시드되는 상황에서 발생한다고 설명합니다.키 스트로크 타이밍이나 전자 다이오드 노이즈 또는 방송국 간에 튜닝된 라디오 수신기에서 얻은 대기 노이즈에서 충분히 높은 엔트로피의 시드를 사용하면 ^[40]문제를 해결할 수 있습니다.

강력한 난수 생성은 공개키 암호화의 모든 단계에서 중요합니다.예를 들어 RSA에 의해 배포되는 대칭 키에 약한 생성기가 사용되는 경우 도청자는 RSA를 무시하고 대칭 키를 직접 추측할 수 있습니다.

타이밍 공격

Kocher는 1995년에 RSA에 대한 새로운 공격을 설명했습니다.공격자 Eve가 Alice의 하드웨어를 충분히 상세하게 알고 있으며 이미 알려진 여러 암호 텍스트의 암호 해독 시간을 측정할 수 있다면 Eve는 암호 해독 키 d를 빠르게 추론할 수 있습니다.이 공격은 RSA 시그니처 스킴에도 적용할 수 있습니다.2003년에 Boneh와 Brumley는 네트워크 접속(SSL(Secure Sockets Layer) 지원 웹 ^[41]서버 등)을 통해 RSA 인수분해를 복구할 수 있는 보다 실용적인 공격을 시연했습니다.이 공격은 많은 RSA 구현에서 사용되는 중국어 나머지 정리 최적화에 의해 유출된 정보를 활용합니다.

이러한 공격을 저지하는 방법 중 하나는 암호문마다 복호화 조작에 일정한 시간이 소요되도록 하는 것입니다.그러나 이 접근방식은 퍼포먼스를 크게 저하시킬 수 있습니다.대신 대부분의 RSA 구현에서는 암호화 블라인딩이라고 하는 대체 기술을 사용합니다.RSA 블라인딩은 RSA의 승수 속성을 사용합니다.Alice는 c(mod n)를 계산하는^d 대신 먼저 비밀 랜덤 값 r을 선택하고 rc^e(^dmod n)를 계산합니다.이 계산의 결과는, 오일러의 정리를 적용한 후, rc(mod n)이며^d, 따라서 r의 효과는 그것의 역수를 곱함으로써 제거될 수 있다.각 암호 텍스트에 대해 새로운 값 r이 선택됩니다.블라인딩이 적용되면 복호화 시간은 입력 암호문 값과 관련이 없어지기 때문에 타이밍 공격이 실패합니다.

적응형 선택 암호 공격

1998년 Daniel Bleichenbacher는 PKCS #1 v1 패딩 방식을 사용하여 RSA 암호화 메시지에 대한 최초의 적응형 선택 암호 공격에 대해 설명했습니다(패딩 방식은 RSA 암호화 메시지에 구조를 랜덤화하여 추가하므로 복호화된 메시지가 유효한지 여부를 판단할 수 있습니다).PKCS #1 스킴의 결함으로 인해 Bleichenbacher는 Secure Sockets Layer 프로토콜의 RSA 구현에 대해 실제 공격을 가하고 세션 키를 복구할 수 있었습니다.이 작업의 결과, 현재 암호화 기술자들은 Optimal Asymmetric Encryption Padding과 같은 안전한 패딩 방식의 사용을 권장하고 있으며, RSA Laboratories는 이러한 공격에 취약하지 않은 새로운 버전의 PKCS #1을 출시했습니다.

이 공격의 변종인 "BERserk"는 ^[42][43]2014년에 재발했다.Firefox 및 Chrome에서 주로 사용된 Mozilla NSS 암호화 라이브러리에 영향을 미쳤습니다.

사이드 채널 분석 공격

Branch-Prediction Analysis(BPA; 분기 예측 분석)를 사용한 사이드 채널 공격에 대해 설명했습니다.많은 프로세서가 분기 예측 변수를 사용하여 프로그램의 명령 흐름에서 조건부 분기가 실행될지 여부를 결정합니다.대부분의 경우 이러한 프로세서는 동시 멀티스레딩(SMT)도 구현합니다.브런치 예측 분석 공격은 이러한 프로세서를 사용하여 처리될 때 스파이 프로세스를 사용하여 개인 키를 검출(통계적으로)합니다.

SBPA(Simple Branch Prediction Analysis)는 비통계적인 방법으로 BPA를 개선한다고 주장합니다.SBPA(Onur Aciicmez 및 Cetin Kaya Koc)의 저자들은 "단순한 분기 예측 분석의 힘에 대하여"^[44]라는 논문에서 RSA 키의 512비트 중 508비트를 10회 반복하여 발견했다고 주장합니다.

RSA 구현에 대한 전원 장애 공격은 ^[45]2010년에 설명되었습니다.작성자는 CPU 전원전압을 제한치 이상으로 변경하여 키를 회복했습니다.그 때문에, 서버에 복수의 전원 장해가 발생했습니다.

구현이 까다로움

RSA를 안전하게 구현하기 위해서는 많은 세부사항(강력한 PRNG, 허용 가능한 퍼블릭 지수 등)을 염두에 두어야 합니다.이로 인해 구현이 어려워집니다.「Practical Cryptography With Go」라는 책에서는 가능하면 RSA를 피하는 것이 권장되고 있습니다.

실장

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

• 보탄
• 번시 캐슬
• cryptlib의
• 암호++
• libgcrypt
• 쐐기풀
• OpenSSL
• 울프크립트
• GnuTLS
• Mbed TLS
• LibreSSL

「 」를 참조해 주세요.

• 음향 암호 분석
• 계산 복잡도 이론
• 암호 키 길이
• Diffie-Hellman 키 교환
• 키 교환
• 키 관리
• 타원곡선암호법
• 공개키 암호화
• 트랩도어 기능

레퍼런스

추가 정보

• Menezes, Alfred; van Oorschot, Paul C.; Vanstone, Scott A. (October 1996). Handbook of Applied Cryptography. CRC Press. ISBN 978-0-8493-8523-0.
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 881–887. ISBN 978-0-262-03293-3.

외부 링크

• Rivest, Ronald L. (Belmont, MA), Shamir, Adi (Cambridge, MA), Adleman, Leonard M. (Allington, MA), 1977년 12월 14일, 미국 특허청에 제출된 원본 RSA 특허.
• PKCS #1: RSA 암호화 표준 (RSA Laboraties 웹사이트)
  • PKCS #1 규격은 "암호화 프리미티브, 암호화 방식, 부록을 포함한 서명 방식, 키를 표현하고 스킴을 식별하기 위한 ASN.1 구문 등 RSA 알고리즘을 기반으로 한 공개 키 암호화 구현에 대한 권장사항을 제공합니다.
• 유튜브 컬러 램프를 이용한 RSA 설명
• RSA의 상세 설명
• 소수 숨바꼭질:RSA 암호 구조
• 오누르 Aciicmez, Cetin Kaya Koc, Jean-Pierre Seifert: 단순한 분기 예측 분석의 힘
• PKCS#1 패딩을 사용한 RSA 실장의 예(GPL 소스 코드)
• 타이밍 공격에 대한 코처의 기사
• CrypTool의 수학적 배경과 함께 RSA에 대한 애니메이션 설명
• Grime, James. "RSA Encryption". Numberphile. Brady Haran.
• RSA Key를 사용한 실제 암호화 방법