RSA 란?

 

RSA 란?

 RSA는 이전 페이지에서 설명드린대로 공개키 암호시스템의 하나입니다. RSA는 암호화뿐만 아니라 전자서명이 가능한 최초의 알고리즘으로 알려져 있습니다. RSA가 갖는 전자서명 기능은 인증을 요구하는 전자 상거래 등에 RSA의 광범위한 활용을 가능하게 하였습니다.

 1978년 로널드 라이베스트(Ron Rivest), 아디 샤미르(Adi Shamir), 레너드 애들먼(Leonard Adleman)의 연구에 의해 체계화되었으며, RSA라는 이름은 이들 3명의 이름 앞글자를 따서 만들어졌습니다.

RSA 암호체계의 안정성은 큰 숫자를 소인수 분해하는 것이 어렵다는 것에 기반을 두고 있습니다. 그러므로 큰 수의 소인수 분해를 획기적으로 빠르게 할 수 있는 알고리즘이 발견된다면 RSA의 암호 체계는 가치가 떨어질 것입니다. 1993년 피터 쇼어는 쇼어 알고리즘을 발표하여, 양자 컴퓨터를 이용하여 임의의 정수를 다항 시간 안에 소인수 분해하는 방법을 발표하였습니다. 따라서 양자 컴퓨터가 본격적으로 실용화되면 RSA 알고리즘은 무용지물이 될 것입니다. 그러나 양자 컴퓨터가 이 정도 수준으로 실용화되려면 아직 시간이 더 필요할 것으로 보여집니다.

 

RSA의 원리

RSA는 두 개의 키를 사용합니다. 여기서 키란 메시지를 열고 잠그는 상수(변하지 않는 수)를 의미합니다. 일반적으로 많은 공개키 알고리즘의 공개키(public key or pub key)는 모두에게 알려져 있으며 메시지를 암호화(encrypt)하는데 쓰이며, 암호화된 메시지는 개인키(private key or pri key)를 가진 자만이 복호화(decrypt)하여 열어볼 수 있습니다,.

공개키 알고리즘은 누구나 어떤 메시지를 암호화할 수 있지만, 그것을 해독하여 열람할 수 있는 사람은 개인키를 지닌 단 한 사람만이 존재한다는 점에서 대칭키 알고리즘과 차이를 가집니다.

RSA는 소인수 분해의 난해함에 기반하여, 공개키만을 가지고는 개인키의 안전한 암호화 시스템을 보장하도록되어있습니다.

 이해하기 쉬운 예를 들자면, A라는 사람에게 B라는 사람이 메시지를 전하고자 할 때 B는 A의 열린 자물쇠를 들고 와 그의 메시지를 봉인(공개키 암호화 과정에 해당)하고, 그런 다음 A에게 전해 주면, 자물쇠의 열쇠(개인키에 해당)를 가지고 있는 A가 그 메시지를 열어보는(개인키 복호화 과정에 해당) 식이 됩니다. 중간에 그 메시지를 가로채는 사람은 그 열쇠를 가지고 있지 않으므로 메시지를 열람할 수 없습니다. (여기서의 조건은 A 의 열쇠가 안전하다는 조건이 있습니다.)

하지만 실사용에서 메시지와 공개키 모두를 알 수 있다면 변조된 메시지를 보낼 수 있기 때문에, 실제로는 수신측의 공개키만을 사용하여 암호화하는 경우는 드뭅니다. 다음은 실사용시 송수신 양측의 키쌍을 사용하는 방법입니다.

 

1. A의 개인키로 암호화 -> B의 공개키로 암호화 한 메시지를 전달합니다

2. 복호화 과정은 B의 개인키로 복호화 -> A의 공개키로 복호화합니다.

 

위의 구성된 방식이 일반적으로 사용되고있습니다. RSA의 열쇠(개인키에 해당)는 자물쇠의 형태(공개키에 해당)만 보고서는 쉽게 제작할 수가 없게 되어 있습니다.

 

RSA 키의 생성 원리

A와 B가 보안이 보장되어 있지 않은 환경에서 서로 비밀 메시지를 주고 받고 싶다고 가정하겠습니다. B가 A에게 메시지를 전달하기 위해서는 A의 공개키가 필요합니다. A는 아래와 같은 방법을 통해 그만의 공개키와 개인키를 제작합니다.

 

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

2. 두수를 곱하여 N = pq 를 구합니다.

3. ϕ(N) = (p-1)(q-1)를 구합니다.

4. ϕ(N) 보단 작고 , ϕ(N)와 서로소인 정수 e를 찾습니다.

5. 확장된 유클리드 호제법을 이용하여 d x e 를 ϕ(N)로 나누었을 때 나머지가 1인 정수 d를 구합니다. ( de = 1 (mod ϕ(N)) )

 

A의 공개키는 위에서 구한 두 개의 숫자로 이루어진 <N, e>이고, 개인키는 <N, d>입니다다. A는 <N, e>만을 B에게 공개하고, B는 이 공개키를 사용하여 자신의 메시지를 암호화하게 됩니다. p, q를 가지고 d와 e의 계산이 가능하기 때문에 p와 q의 보안은 매우 중요합니다. 그리하여 공개키와 개인키가 생성이 된 후에는 이 두 숫자를 지워버리는 것이 안전합니다.

 

다음으로는 암호화 과정에 설명을 드리겠습니다. 암호화 설명은 쉽게 설명을 드리기 위해 예시로 설명을 드리겠습니다.

 

 

RSA로 암복호화 하는 과정

평문(plain text)을 암호화 하려면 공개키가 필요합니다. N과 e는 공개키이고 복호화할 때 필요한 개인키는 d입니다.

공개키로 암호화 하는 과정은 다음과 같습니다.

1. 평문이 8이라고 하면 8을 e만큼 제곱해줍니다.(참고로 원본값은 n보다 작아야 합니다.)

2. e 는 3이므로 3제곱을 해줍니다.

3. 결과값에 N 값으로 나머지 연산을 해줍니다.

4. 8 x 8 x 8 =512 입니다.

5. 512% 34 = 2 입니다.

그러면 암호화가 된 값은 2입니다.

 

RSA로 복호화 하는 과정

암호문(encryption text)을 복호화 하려면 개인키가 필요합니다. 개인키는 N과 d는가 필요합니다.

개인키로 복호화 하는 과정은 다음과 같습니다.

1. 암화문 2를 개인키만큼 제곱하고 공개키와 개인키에서 필요로하는 N으로 나머지 연산을 합니다.

2. 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2  = 2048 입니다.

3. 2048 % 34 = 입니다.

그러면 원본값인 8이 나오게 됩니다.

 

RSA로 공개키 암호화에 대해 알아보았습니다.

다음시간에는 ElGamal 알고리즘에 대해 알아보겠습니다.