RSA 암호 알고리즘이란?

RSA 암호 알고리즘이란?

Rivet, Shamir, Adelman 세사람의 첫이름을 따 RSA라고 만든 암호 알고리즘이다.

RSA 암호 체계는 미국 MIT에서 개발한 공개키 암호 시스템이다.

이 암호 알고리즘의 핵심은 큰 정수의 소인수 분해가 어렵다는 점을 이용하여 암호화를 시킨다.

이러한 RSA 암호 알고리즘은 전자상거래에서 가장 흔히 쓰고있는 공개키 알고리즘이다.

주로 적은 양의 데이터나 전자서명에 사용한다.또한 RSA 암호는 대칭키인 DES나 AES보다 속도가 느리므로 메시지 암호화에는 쓰이지 않고 주로 키를 암호화하는데 쓰인다.

 

RSA 암호 알고리즘 방식

1. A가 B에게 정보를 안전하게 보내고 싶어한다. 이때 RSA 알고리즘을 이용하고자 한다.

2. B가 공개키와 개인키를 만들어 A에게 공개키를 보낸다. (개인키는 B만 가지고 있다.)

3. A가 B로부터 받은 공개키를 이용하여 보낼 정보를 암호화한다.

4. A가 암호화된 정보를 B에게 보낸다.

5. B가 암호화된 정보를 받고 개인키를 이용하여 암호를 해독한다.

 

RSA 암호 알고리즘 원리

1. 개인키와 공개키 만들기

RSA 암호 알고리즘 첫 단계는 공개키와 개인키를 만드는 것이다.

공개키는 n,e라는 두 정수로 이루어져있고 개인키는 n,d라는 두 정수로 이루어져있다.

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. 암호화하기

STEP 1에서 구한 공개키를 이용해서 정보를 암호화 한다.

원래 정보를 M이라 하고 암호화된 정보를 C라 하자.

위의 식을 이용하여 M을 C로 암호화 하면 된다.

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

 

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

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

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

암호화 할때는 1번식을 사용했으므로 복호화 할때는 위의 식 즉, 2번식을 이용하여 복호화를 한다.

이때 암호화된 정보 C를 M으로 복호화(해독)할 때는 n과 d값을 알아야 한다.

이때 이 값을 아는 사람은 개인키(n, d)를 가진 사람 B 뿐이다.