[비대칭키 암호] RSA(Rivest-Shamir-Adleman) 암호시스템

▶ 개요

RSA는 공개키 암호 알고리즘 중 하나이며, 사실상의 표준이다. 인수분해 문제 해결의 높은 난이도를 이용한 가장 대표적인 공개키 암호 알고리즘으로 암호화뿐만 아니라 전자서명의 용도로도 사용된다. SSL 프로토콜을 가진 많은 웹 브라우저, PGP 그리고 공개키 암호시스템을 사용하는 정부시스템 등이 RSA를 사용한다.

 

▶ 키 생성 알고리즘

[1]  p와 q라고 하는 두개의 서로 다른 (p!=q) 소수를 고른다.

[2] 두 수를 곱하여 N=pq를 찾는다.

[3]  Ø(N)=(p-1)(q-1)를 구한다.

[4] Ø(N) 보단 작고, Ø(N)과 서로소인 정수 e를 찾는다.

[5] 확장된 유클리드 호제법을 이용하여 de를 Ø(N)로 나누었을 때 나머지가 1인 정수 d를 구한다. (de≡1(modØ(N)))

※ 만약 공개키 n과 e로부터 비밀키 d를 구할 수 있다면 RSA는 해독되게 된다. 이렇게 되기 위해서는 공개키 n으로부터 Ø(n)=(p-1)(q-1)을 구해내야 한다. Ø(n)을 구하게 되면 유클리드 알고리즘을 이용하여 쉽게 d를 구할 수가  있게 되므로 RSA 알고리즘의 안전성은 n의 소인수분해, 즉 p와 q를 구해내는 것에 달려있다. 안전을 위해서 권장되는 각 소수 p와 q의 크기는 512비트이다. 이 크기는 10진수로 약 154자리수이다. 이런 소수를 사용하면 모듈러로 사용할 n은 1024비트로 십진수 309자리가 된다. 

<예제>

p=5, q=11 이라고 가정할 때 개인키와 공개키를 구하시오.

n= p*q = 5*11 = 55 // Ø(n)=(p-1)(q-1)=40 // gcd(40,e)=1 // e: 3,7,.... // (d*3)mod40=1

공개키 {n,e} = {55,3} // 개인키 {d,n} = {55,27}

 

▶ RSA에 대한 공격

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

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

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

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

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

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

 

▶ 최적 비대칭키 암호 패딩(OAEP, Optimal Asymmetric Encryption Padding)

RSA를 개량한 알고리즘이다. RSA-OAEP의 복호화에서는 평문 해시값과 정해진 개수의 '0' 등으로 만들어진 '인증 정보'를 평문의 앞에 추가하고 RSA로 암호화한다(Padding). RSA-OAEP의 복호화에서는 RSA로 복호화한 후 올바른 '인증 정보'가 나타나지 않으면 'DECRYPTION ERROR'이라는 일종의 오류 메시지를 회신한다.(구체적으로 어떤 오류인지를 알리지 않는 것이 중요하다.) 이러면 복호 오라클로부터 정보를 얻을 수가 없어져 선택 암호문 공격으로부터 안전하게 된다. 실제의 RSA-OAEP에서는 난수를 이용해서 암호문이 매번 다른 패턴이 되도록 하여 보다 안전성을 높이고 있다.

 

▶ 권장사항

[1] N의 비트수는 적어도 1024비트가 되어야 한다. 즉, N은 2^1024 근방에 있는 수거나 309자리 이상의 십진수가 되어야 한다.

[2] 두개의 소수 p와 q는 적어도 512비트가 되어야 한다. 즉, p와 q는 2^512근방에 있는 수거나 154자리 이상의 십진수가 되어야 한다.

[3] p와q는 같지 않고 거의 같은 크기의 소수이어야 한다.

[4] p-1과 q-1은 커다란 소인수를 각각 가져야 한다.

[5] p-1과 q-1의 최대공약수는 작은 수이어야 한다.

[6] 메시지는 OAEP를 사용해서 패딩되어야 한다.