비대칭키 암호 - RSA (공개키 암호시스템)

1. 개요

• RSA는 공개키 암호 알고리즘 중의 하나이며, 세계적으로 사실상의 표준이다.
• 인수분해 문제 해결의 높은 난이도를 이용한 가장 대표적인 공개키 암호 알고리즘으로 암호화뿐만 아니라 전자서명의 용도로도 사용된다.
• SSL 프로토콜을 가진 많은 웹브라우저, PGP 그리고 공개키 암호 시스템을 사용하는 정부 시스템 등이 RSA를 사용한다.
• RSA는 두 개의 키를 사용하는데, 모두에게 공개하는 공개키(Public Key)와 공개해선 안 되는 개인키(Private Key)로 구성된다.
• 공개키는 메시지를 암호화할 때 사용하고, 개인키는 암호화된 메시지를 복호화할 때 사용한다.

2. 방식

① A가 B에게 정보를 안전하게 보내고 싶어한다. 이때 RSA 알고리즘을 이용하고자 한다.
② B가 공개키와 개인키를 만들어 A에게 공개키를 보낸다. (개인키는 B만 가지고 있다.)
③ A가 B로부터 받은 공개키를 이용하여 보낼 정보를 암호화한다.
④ A가 암호화된 정보를 B에게 보낸다.
⑤ B가 암호화된 정보를 받고 개인키를 이용하여 암호를 해독한다.

3. RSA 암호 알고리즘 

(1) 개인키와 공개키 만들기

• RSA 암호 알고리즘 첫 단계는 공개키와 개인키를 만드는 것이다.
• 공개키는 n, e 라는 두 정수로 이루어져 있고 개인키는 n, d라는 두 정수로 이루어져 있다.

※ p, q의 조건
① p는 q와 거의 같은 크기이다.
② p-1과 q-1은 큰 소인수를 갖는다.
③ p-1과 q-1의 최대공약수는 작은 수 이다.
④ d는 n과 거의 같은 크기이다.

n 구하기

• 임의의 두 소수 p와 q를 정하고 n = p * q를 해주면 n을 구할 수 있다.

e 구하기

• Φ(n) = (p - 1) * (q - 1)식을 이용하여 Φ(n)을 구한다.
• e는 1 < e < Φ(n)로써 1과 Φ(n) 사이에 있고 Φ(n)와 서로소인 e를 정해주면 된다.
• 이러한 e는 공개키에 이용이 될 것이다.

※ 서로소란 1 이외에 공약수를 가지지 않는 수를 의미한다.

d 구하기

• (e * d) mod Φ(n) = 1
• 즉, e*d를 Φ(n)으로 나누었을 때 나머지가 1인 d를 구하면 된다. 이때 d는 개인키에 사용될 숫자이다. 
• 이제 공개키에 이용될 (n, e)와 개인키에 이용될 (n, d)를 모두 구하였다. 즉, 개인키와 공개키가 생성되었다.

(2) 암호화하기

• ① 에서 구한 공개키를 이용해서 정보를 암호화한다.
• 원래 정보를 M이라 하고 암호화된 정보를 C라 하자.

RSA 암호화

• 위의 식을 이용하여 M을 C로 암호화하면 된다.
• 이때 암호화를 할 때 e와 n의 값을 알아야 하므로 공개키(n, e)가 있어야 암호화할 수 있다는 것은 자명하다.

(3) 복호화하기(해독하기)

• 이제 암호화되어 온 정보 C를 복호화(해독)할 순서이다.

RSA 암호화(C), 복호화(M)

• 페르마의 소정리에 의해 1번 식이 성립하면 2 번식도 성립하게 된다.

RSA 복호화

• 암호화할 때는 1 번식을 사용했으므로 복호화 할때는 위의 식 즉, 2번식2 번식을 이용하여 복호화를 한다.
• 이때 암호화된 정보 C를 M으로 복호화(해독)할 때는 n과 d값을 알아야 한다.
• 이때 이 값을 아는 사람은 개인키(n, d)를 가진 사람 B 뿐이다. 

 

4. RSA 알고리즘 예

공개키 n, d // 개인키 n, e를 구하자

① 두 소수 p=17과 q=11을 선택한다.

② N=P*Q=17*11=187을 계산한다.

③ Φ(N)=(p-1)(q-)=16*10=160을 계산한다.

④ 공개키 구하기 -> Φ(N)=160보다 작으면서 Φ(N)과 서로수인 수 e를 선택한다. 여기서는 e=7을 선택한다.

⑤ 개인키 구하기 -> d <160 이면서 d*e mod 160=1 인 수 d를 결정한다. e=7 이므로 d*7 mod 160=1

d=(1+160)/7 하면, d=23이다. 

⑥ 결과로 얻어지는 공개키={187, 7}, 개인키={187, 23}이다.

평문이 88이라고 가정하면

암호화 숫자는 88^7 mod 187 = 11이다.

다시 복호화하면 11^23 mod 187 = 88이다.

RSA 알고리즘 예

 

5. RSA에 대한 공격

(1) 수학적 공격(소인수분해 공격)

• 수학적 공격의 핵심은 두 개의 소수 곱을 인수분해하고자 하는 노력입니다. 수학적 공격을 막으려면 키의 길이가 긴 걸 사용해야 한다. 그래서 개인키 d의 비트 수가 크면 클수록 더 안전하다.
• 하지만 키 생성과 암호학/복호화에서의 계산량을 고려해야 하기 때문에 이는 복잡한 문제다. 키 길이가 길어지면 시스템 처리 속도는 느려진다.
• 현실적인 시간 내에 소인수분해를 마칠 수 있는 효율적인 소인수분해 알고리즘이 개발되지 않는 한 RSA는 안전하다고 말할 수 있는 것이다.

(2) 타이밍 공격(시간 공격)

• 복호화 알고리즘의 실행 시간에 따라 달라진다. (선택-암호문 공격)
• 다양한 방법을 통해 소요되는 시간이 드러나지 않게 막아 키 길이를 추측하는 공격을 막을 수 있다. 예를 들면, 랜덤 지체라는 방법을 이용하여 타이밍 공격을 막는다.

(3) 선택 암호문 공격(CCA, Chosen Ciphertext Attack)과 OAEP

• 선택 암호문 공격이라는 것은 임의의 데이터를 송신하면 그것을 암호문으로 간주하고 회신해 주는 서비스를 공격자가 이용할 수 있다는 것을 가정한 공격이다. 이 서비스를 복호 오라클이라 한다.
• 네트워크에서 통신하는 서버는 송신한 데이터에 형식이 갖추어지지 않으면 데이터 오류라는 오류 메시지를 통신 상대방에 반송하는 경우가 종종 있다. 이와 같은 친절을 공격자가 노리는 것이다.
• 공격자는 자신이 만든 위조 암호문을 서버에 여러 차례 보내고, 서버가 회신해 주는 오류 메시지나 타이밍을 해석해서 키나 평문 정보를 조금이라도 얻으려고 하는 것이다. 이 경우 서버가 복호 오라클과 유사한 움직임을 하게 되어버리는 것이다.
• 정교한 선택 암호문 공격을 막기 위해 RSA Scurity 사에서는 최적 비대칭 암호화 패딩(OAEP, Optimal Asymmetri Encryption Padding)이라고 하는 프로시저를 사용해 평문을 수정할 것을 권장하고 있다.

 

6. 최적 비대칭키 암호 패딩(OAEP)

• RSA-OAEP는 RSA를 개량한 알고리즘이다.
• RSA-OAEP의 복호화에서는 평문 해시값과 정해진 개수의 '0' 등으로 만들어진 "인증 정보"를 평문의 앞에 추가하고 RSA로 암호화한다. (패딩)
• RSA-OAEP의 복호화에서는 RSA로 복호화한 후 올바른 "인증 정보"가 나타나지 않으면 "평문을 알고 있는 사람이 만든 암호문이 아니다"라고 판단해서 오류로서 "decryption error"이라는 일종의 오류 메시지를 회신한다.
• 이와 같이 하면, 공격자가 RSA-OAEP의 복호 오라클로부터 정보를 얻을 수가 없어지기 때문에 선택 암호문 공격으로부터 안전하게 본다.
• 실제의 RSA-OAEP에서는 난수를 이용해서 암호문이 매번 다른 패턴이 되도록 하여 보다 안전성을 높이고 있다.

 

7. 권장사항

다음과 같은 권장사항은 이론적이거나 실험적인 결과에 근거하여 만들어진 것이다.

• n의 비트수는 적어도 1024비트가 되어야 한다. 즉, 2^1024 근방에 있는 수거나 209자리 이상의 십진수가 되어야 한다.
• 두 개의 소수 p와 q는 적어도 512비트가 되어야 한다. 즉, p와 q는 2^512 근방에 있는 수거나 154자리 이상의 십진수가 되어야 한다.
• p와 q는 같지 않고 거의 같은 크기의 소수이어야 한다.
• p-1과 q-1은 커다란 소인수를 각각 가져야 한다.
• p-1과 q-1의 최대 공격수는 작은 수어야 한다.